Gentle Introduction to Operating System

  • Published on
    04-Jan-2016

  • View
    21

  • Download
    4

Embed Size (px)

DESCRIPTION

Gentle Introduction to Operating System. Anthony K. H. Tung( Associate Professor Department of Computer Science. http://www.comp.nus.edu.sg/~atung http://www.renren.com/profile.do?id=313870900&_ua_flag=93w. Objectives. - PowerPoint PPT Presentation

Transcript

  • Gentle Introduction to Operating SystemAnthony K. H. Tung(Associate ProfessorDepartment of Computer Science

    http://www.comp.nus.edu.sg/~atunghttp://www.renren.com/profile.do?id=313870900&_ua_flag=93w

  • ObjectivesOperating System in SOC is a second year course(CS2106) which have prerequisites of eitherCS1104/ CS2100 : Computer OrganizationEE2007: Microprocessor SystemsAim of this talk:Provide some hardware background so that you can understand OS betterExplain why instead of just how and what?Provide a framework that can merge different concepts together

  • ApproachWe will design an OS together, starting from a simple one and finally to a complex one:Single user, single processSingle user, multiple processesMultiple users, multiple processesWhile designing, we will take into consideration various desiderataEfficiencyRobustness to changesRobustness to errorsConsistencyIsolation

  • What is OS?As the name implied, operating system is a software system that operate something? What is that something?something=hardwareWhy do we need to put in a software layer that operate the hardware?To appreciate something, we need to ask ourselves what is something do not exist

  • In the beginningThere is no such thing as an OS, each user write their own program to control the hardware which have their own control code or instruction setExample: hard diskHave many tracksEach track have many sectorsData are stored in each sector as binary bits

    1010010100.

  • Eg. of Instruction Set for Hard DiskPhysically the disk is control by electronic circuitinstruction sector no. memory loc. 1 0 0 1 0 1 1 1 0 1 1 0

    CodeDescriptionBinary00Reset Disk Drives0001Check Drive Status0102Read Sectors From Drive1003Write Sectors To Drive11

  • Storing Data as FilesWhen there was no OS(i.e. no fgets, fopen), programmers have to organize the sectors into files in their programsExample: Use the first sector as file directory and indicate what are the sectors use to store data for each file. Figure on the right show file directory for two files, numbers and lettersnumbers, 2, 5, 8, -1letters, 3, 6, 1023, -1 . . .20, 4, 100, A, Z, B, H, .900, 1000, 50, B, C, I, A, .54, 20, 10,.O, R, Q, G Sector 2Sector 3Sector 4Sector 5Sector 6Sector 7Sector 8Sector 9Sector 1023Sector 1024Sector 1filenameEnd markerFile directory sector..

  • Storing Data as Files(II)How to read the file numbers?numbers, 2, 5, 8, -1letters, 3, 6, 1023, -1 . . .20, 4, 100, A, Z, B, H, .900, 1000, 50, B, C, I, A, .54, 20, 10,.O, R, Q, G Sector 2Sector 3Sector 4Sector 5Sector 6Sector 7Sector 8Sector 9Sector 1023Sector 1024Sector 1filenameEnd markerStep 1: 10, Sector 1, Mem. Location 20 // Read Sector 1 // into memory location 20Step 2: Search location 20 for filename=numbers;Step 3: sector_num = first sector of numbers;Step 3: While (sector_num-1) doStep 4: { 10, Sector sector_num, Mem. Location 21;Step 5: process data in mem. Location 21;Step 6: }

    Note: 10 is the hardware code for reading a sector of the disk..

  • What is the problem of such an approach?Difficulty in programming. Have to remember the command code and repeat the same thing in every program.Different programmers might implement the file differently. What if one of them resign?Not robust to change: What if a different brand of disk with different instruction code is used? i.e. 01 is used to read a sector instead?

  • Having an OS avoid these problemsIn its most basic form, OS provide a list of routines or services that are called by application programs to perform certain tasks through software interruptsDetails of such call involve three concepts:Program Counter (PC)Interrupt Vector Table (IVT)Context Switch

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to Printer . .For (i=0;i

  • Program Counter (PC)The program counter(PC) is a register that store the address of the next instruction to be executed by the CPUint i=5, j=6, k=7;i=i+1;j=j+2;k=i+j;i=0;end10001002100310041005100610071008Memory address1001ProgramvariablesijkPC: 1000CPU:At the start, PC point to start of program

  • Program Counter (PC)The program counter(PC) is a register that store the address of the next instruction to be executed by the CPUint i=5, j=6, k=7;i=i+1;j=j+2;k=i+ji=0;end56710001002100310041005100610071008Memory address1001ProgramvariablesijkPC: 1001CPU:int i=5, j=6, k=7;Fetch instruction at 1000 and execute. Increment PC to 1001

  • Program Counter (PC)The program counter(PC) is a register that store the address of the next instruction to be executed by the CPUint i=5, j=6, k=7;i=i+1;j=j+2;k=i+ji=0;end66710001002100310041005100610071008Memory address1001ProgramvariablesijkPC: 1002CPU:i=i+1Fetch instruction at 1001 and execute. Increment PC to 1002

  • Program Counter (PC)The program counter(PC) is a register that store the address of the next instruction to be executed by the CPUint i=5, j=6, k=7;i=i+1;j=j+2;k=i+ji=0;end68710001002100310041005100610071008Memory address1001ProgramvariablesijkPC: 1003CPU:j=j+2Fetch instruction at 1002 and execute. Increment PC to 1003

  • Program Counter (PC)The program counter(PC) is a register that store the address of the next instruction to be executed by the CPUint i=5, j=6, k=7;i=i+1;j=j+2;k=i+ji=0;end081410001002100310041005100610071008Memory address1001ProgramvariablesijkPC: 1005CPU:k=i+j;Fetch instruction at 1004 and execute. Increment PC to 1005 and end program

  • Interrupt Vector Table(IVT)During interrupt, the program counter(PC) must be set to point to the address of the OS service in order to execute the routine there. How do the program know where is the address?IVT: store the location of each interrupt service

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to Printer . .For (i=0;i

  • Let see how a software interrupt happen now! (User Mode)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 1002CPU:Interrupt Vector TableLet say the application program is running and the PC is pointing at location 1002i=i+1;1003

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

  • Let see how a software interrupt happen now! (User Mode)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 1003CPU:INT 01, numbersInterrupt Vector TableIt load in the instruction and see that it is an interrupt command(INT) asking for interrupt service 01i=i+1;1003

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

  • Let see how a software interrupt happen now! (User Mode)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 1003CPU:INT 01, numbersInterrupt Vector TableIt look up the IVT and see that the service Open File is locate at address 0001i=i+1;1003

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

  • Let see how a software interrupt happen now! (Kernel Mode)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 0001CPU:Interrupt Vector TableIt then set PC to 0001 and start fetching instructions from the Open File service therei=i+1;1003

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

  • Let see how a software interrupt happen now! (Kernel Mode)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 0005CPU: End of Open FileInterrupt Vector TableAssuming we reach the end of Open File routine, then how do we know where we should continue next?i=i+1;1003

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

  • Context(I): User Mode

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 1003CPU:INT 01, numbersInterrupt Vector TableActually, when an interrupt happens, we need to save the context of the application program before we jump to the interrupt service routine!i=i+1;1003Context stack

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

    Program XXX1003

  • Context(II): Kernel Mode

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 0005CPU: End of Open FileInterrupt Vector TableSo when read the end of Open File, we look at the context stack and jump back to the place where interrupt occurs!i=i+1;1003Context stack

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

    Program XXX1003

  • Context(III): return from interrupt(User mode again!)

    Open FileClose FileGet System DataGet/Set File AttributeRead fileWrite fileAllocate MemoryWrite to ScreenWrite to PrinterINT 01, numbers0001-0050021-00280029-00350036-00420043-00550056-00680069-00800036-0042Memory address0006-00201002OS ServicesApplicationProgramPC: 1003CPU:Interrupt Vector TableSo when read the end of Open File, we look at the context stack and jump back to the place where interrupt occurs!i=i+1;1003Context stack

    Interrupt No.ServiceAddress01Open File000102Close File000603Get SD002104Get/Set File Attribute002905Read file003606Write file0043

    Program XXX1003

  • Context(IV): Final NotesNote that in a context stack, there can be many entries as if many different processes/programs are running at the same time and issues different interrupts at different point in timeContext stackprogramaddress

    Program XXX1003

    Process YYY2500

    Process ZZZ0500

    Program AAA0700

  • Making OS more efficientSince the OS provide a set of routines/services that are called by all application programs, it make sense to ensure that these routines/services are efficient so that the whole computer system is efficient as a wholeWe will next look at two concepts that make the OS more efficient in using the CPU:CachingHardware interrupts

  • Caching(Motivation)CPUDiskWe wish to read 100 numbers from the disk and sum them up. These are the time that is need for each operations:Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5ms

    How long will it take to finish what we want to do?

    Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5 ms

  • Caching(Motivation)CPUDiskAssuming no cache/bufferInitialize 100 times for 100 numbers: 5 x 100 ms = 500 msRead 100 numbers: 2 x 100ms = 200msTransfer 100 numbers: 2 x 100ms = 200msSum 100 numbers: 100 x 0.5 = 50msTotal = 950ms

    Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5 ms

  • Caching(Motivation)CPUDiskAssuming we DO have cache that can store all 100 numbersInitialize 1 times for 100 numbers: 5 x 1 ms = 5 msRead 100 numbers: 2 x 100ms = 200msTransfer 100 numbers: 2 x 100ms = 200msSum 100 numbers: 100 x 0.5 = 50msTotal = 455ms

    Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5 ms100, 29, 50, 200,, 90Local buffer of 100 numbers100, 29, 50, 200,, 90CPU Memory Cache

  • Caching(Motivation)CPUDiskBecause of this, data on hard disk are stored as a block called sector. One sector can contain one set of numbers. Only the first read of the sector will cause access to the disk. If the sector is stored in the memory cache, subsequent read will be from the cache.Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5 ms100, 29, 50, 200,, 90Local buffer of 100 numbers100, 29, 50, 200,, 90CPU Memory Cache

  • Caching(Motivation)CPUDiskCan we do better? If we are summing N numbers, does it always make sense to have a local buffer or sector of N numbers for the disk?

    How about first loading 50 numbers, let the CPU start to compute and then CURRENTLY load the other 50 numbers?Initialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5 ms100, 29, 50, 200,, 90Local buffer of 100 numbers100, 29, 50, 200,, 90CPU Memory Cache

  • Caching & Interrupt (Motivation)Concurrent reading and calculatingCPUInitialize hard disk: 5msRead 1 number: 2 msTransfer 1 number: 2 msSum 2 numbers: 0.5msDisk(205ms)idleInitialize (5ms)hardware disk interruptRead 50 No. (100ms)Transfer 50 No. (100ms)Initialize command ( 25ms)Sum first 50 No.Initialize 2 (5ms)Harkware disk interruptRead 50 No. (100ms)Initialize command 2Transfer 50 No. (100ms) ( 25ms)Sum next 50 No.(180ms)idleidle (25ms)Total time = 205ms + 205ms + 25ms = 435ms

    Time is saved since summing the first 50 numbers is done concurrent with disk I/O

    What if we divide the numbers into 4 blocks of 25 numbers ? Optimal number of blocks?

  • Interrupt and CurrencyThe concurrent execution in previous example is possible because of hardware interrupt AND caching. The CPU leave the task of reading data to the hard disk and perform other task(adding number). The disk inform the CPU using interrupt when it complete its reading and transferring of dataNotice that we have more from single program, single process to single program with 2 processes (multi-threaded)Total = 0;For (i=0; i
  • Memory Hierarchy for CachingIn general, CPU only read data from the processor registers and CPU cacheCache miss result in fetching from the next layerPipelining()In general, caching and buffering serve to coordinate devices with different speed

  • Who handle hardware interrup?Same as in software interrupt!Hardware interrupt sent signal to CPU which will then give control to one of the OS in...