INTRO TO OPERATING SYSTEMS
INTRO TO OPERATING SYSTEMS CS 333
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 72 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 333 at Portland State University taught by Jonathan Walpole in Fall. Since its upload, it has received 36 views. For similar materials see /class/168271/cs-333-portland-state-university in ComputerScienence at Portland State University.
Reviews for INTRO TO OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/01/15
CS 333 Introduction to Operating Systems Class 12 Virtual Memory 2 Jonathan Walpole Computer Science Portland State University Translation Lookaside Buffer TLB a Problem z Unless we have hardware suppor39T for address Tr39ansIaTion CPU would have To go To memory To access The page Table on every memory access a In BliTz This is whaT happens Translation Lookaside Buffer TLB a Problem z Unless we have hardware supporT for address TranslaTion CPU would have To go To memory To access The page Table on every memory access a In real compuTers There is a TLB z Cache The page Table enTries in a hardware cache z Small number of enTries eg 64 z Each enTry conTains Page number OTher sTuff from page Table enTry z AssociaTiver indexed on page number Hardware operation of TLB Key Number Frame Number Other unused 50 unused 24 unused 19 unused 6 unused Hardware operation of TLB virtual address 23 1312 0 D I page number I offset I Key Number Frame Number Other unused 50 unused 24 unused 19 unused 6 unused 31 1312 0 I frame number I offset I physical address Hardware operation of TLB virtual address 23 13 12 o D I page number I offset I Key Frame Number Other unused unused 50 24 19 6 unused unused unused 31 1312 0 I frame number I offset I physical address Hardware operation of TLB virtual address 23 D I page number I offset k 1 L J Key Page Number Frame Number Other 23 37 unused D R w V 17 50 unused D R w V 92 24 unused D R w V 5 19 unused D R w V 12 5 unused D R w v 31 1312 I frame number I offset physical address Hardware operation of TLB virtual address 23 D I page number I offset k 1 L J Key Page Number Frame Number Other 23 37 unused D R w V 17 50 unused D R w V 92 24 unused D R w V 5 19 unused D R w V 12 5 unused D R w v 31 1312 I frame number I offset physical address Hardware operation of TLB virtual address 23 D I page number I offset k 1 L J Key Page Number Frame Number Other 23 37 unused D R w V 17 50 unused D R w V 92 24 unused D R w V 5 V unused D R W V 12 5 I unused D R w v 31 1312 I frame number I offset physical address SofTwor39e operoTion of TLB a WhoT if The enTry is noT in The TLB 4 Go To page Table how Find The r39ighT enTr39y Move iT inTo The TLB Which enTr39y To replace Software operation of TLB u Hardware TLB refill Page tables in specific location and format TLB hardware handles its own misses a Software refill Hardware generates trap TLB miss fault Lets the OS deal with the problem Page tables become entirely a 05 data structure Software operation of TLB a What should we do with the TLB on a context switch a How can we prevent the next process from using the last process39s address mappings Option 1 empty the TLB New process will generate faults until its pulls enough of its own entries into the TLB Option 2 Just clear the Valid Bitquot New process will generate faults until its pulls enough of its own entries into the TLB Option 3 the hardware maintains a process id tag on each TLB entry Hardware compares this to a process id held in a specific register on every translation Page Tables a Do we access a page Table when a process alloca res or39 frees memory Page Tables a Do we access a page Table when a process allocaTes or frees memory z NoT necessarily z Library rouTines malloc can service small requesTs from a pool of free memory already allocaTed wiThin a process address space z When These rouTines run ouT of space a new page musT be allocaTed and iTs enTry inserTed inTo The page Table This allocaTion is requesTed using a sysTem call Malloc is noT a sysTem call Page Tables a We also access a page table during swappingpaging ro disk z We know The page frame we wan r To clear39 z We need To find The right place on disk To store This process memory z Hence page Table needs To be sear39chable using physical addresses Fastest approach index page Table using page frame number39s Page tables a In a well provisioned system TLB miss faults will be the most frequently occurring event a TLB miss fault z Given a virtual page number we must find the right page table entry Fastest approach index the page table using virtual page numbers hmm isn39t that the opposite of what we said last side z Problem how to structure our page tables for efficient access and low space overhead Page Table design issues a Page Table size depends on z Page size z VirTual address lengTh a Memory used for page Tables is overhead 4 How can we save space z and sTill find enTries quickly a Three opTions z Singlelevel page Tables 4 MulTilevel page Tables z InverTed page Tables Singlelevel page Tables A Virtual Address number Singlelevel page Table in gtfr39ames memory Singlelevel page Tables number Singlelevel page Table in gtfr39ames memory Singlelevel page Tables 21b s I page number 11bi l S I offset I J gt Singlelevel page Table Problem requires one page Table entry per vir39l39ual page in gtframes memory Singlelevel page Tables 21bi139s 11bi139s I page number I offset I k J gt Singlelevel page Table 32 bi39l39 addresses and ZKB pages means 221 page Table entries per process in gtframes memory Multi level page Tables in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset in gtfr39ames memory Top level Page Table 2ndlevel Tables Multi level page Tables u A Virtual Address 10bi139s 10bi139s 12bi rs PT1 PT2 offset HJ in gtfr39ames memory Top level Page Table 2ndlevel Tables Mulfi level page Tables a Ok but how exactly does This save space Mulfi level page Tables a Ok but how exactly does This save space a Not all pages within a virtual address space are allocated 4 NOT only do They noT have a page fr39ame buT Tha r range of vir rual addresses is no r being used So no need To mainTain compleTe informaTion abouT iT Some inTermediaTe page Tables are empTy and noT needed a We could also page The page Table This saves space buT slows access a IoT InverTed page Tables a Problem 4 Page Table overhead increases wiTh address space size Page Tables geT Too big To fiT in memory a Consider a compuTer wiTh 64 biT addresses Assume 4 KbyTe pages 12 biTs for The offseT 4 VirTual address space 252 pages 4 Page Table needs 252 enTries This page Table is much Too large for memory D But we only need mappings for pages ThaT are in memory A 256 MbyTe memory can only hold 64 4KbyTe pages Only need 64 page Table enTries on This compuTer Inverted page Tables a An inverted page Table Has one en rry for every frame of memory Tells which page is in Tha r fr ame Is indexed by frame number39 noT page number39 a So how can we search if on a TLB miss faul39l39 Inverted page Tables a If we have a page number from a faulting address and want 1390 find if page table entry do we Do an exhausTive search of all en rr ies Inverted page tables a If we have a page number from a faulting address and want to find it page table entry do we Do an exhaustive search of all entries No that39s too slow 4 Why not maintain a hash table to allow fast access given a page number 01 lookup time with a good hash function Inverted page table Traditional page table with an entry for each of the 252 pages 252 1 256MB physical memory has 216 4KB page frames 216 1 0 I 0 Indexed by virtual Page Hash table 216 1 0 Indexed by hash on Virtual Page virtual page page frame Which page table design is best a The best choice depends on CPU architecture a 64 bit systems need inverted page tables a Some systems use a combination of regular page tables together with segmentation later Memory protection a At what granularity should protection be implemented a pagelevel A lot of overhead for storing protection information for nonresident pages a segment level Coarser grain than pages Makes sense if contiguous groups of pages share the same protection status Memory protection a How is protection checking implemented compare page protection bits with process capabilities and operation types on every loadstore 4 sounds expensive Requires hardware support a How can protection checking be done efficiently Use the TLB as a protection lookaside buffer Use special segment registers Protection lookaside buffer a A TLB is often used for more than just quotTranslationquot a Memory accesses need to be checked for validity Does the address refer to an allocated segment of the address space 39 If not segmentation fault Is this process allowed to access this memory segment 39 If not segmentationprotection fault Is the type of access valid for this segment Read write execute If not protection fault Valid Virtual page Modified Protection Page frame 1 140 1 RW 31 1 20 0 R X 38 1 130 1 RW 29 1 129 1 RW 62 1 19 0 R X 50 1 21 O R X 45 1 860 1 RW 14 1 861 1 RW 75 Page groin protection in a page table Page frame number Referenced Protection A typical page table entry with support for page grain protection Segmentgrain protection a All pages within a segment usually share the same protection status 50 we should be able to batch the protection information a Why not just use segmentsize pages Segments vary in size Segments change size dynamically stack heap etc Segmented address spaces a Tradifiona Virfua Address Space flat address space 1 dimensional a Segmented Address Space Program made of several quotpiecesquot Each segment is like a miniaddress space Addresses within a segment start at zero The program must always say which segment it means either embed a segment id in an address or load a value into a segment register Addresses Segment Offset Each segment can grow independently of others Segmentation in a single address space Virtual address space Example A compiler Call stack Free Address space S ace currentl beln allocated to the Parse tree uged by the par59 trege parse tree Constant table f Source text Symbol table has Symbol table bumped into the source text table Segmented memory a Each space grows shrinks independently 20K 16K 16K 12K 12K 12K 12K Symbol table 8K 8K 8K Parse 8K tree Source Call text stack 4K 4K 4K 4K I Constants I OK OK 0K 0K 0K Segment Segment Segment Segment Segment 0 1 2 3 Separate instruction and data spaces Single address space space D space 232 232 Unused page Data Data Program Program 0 0 One address space Separate I and D spaces Comparison of paging and segmentation Consideration Paging Segmentation Need the programmer be aware No Yes that this technique is being used How many linear address 1 Many spaces are there Can the total address space Yes Yes exceed the size of physical memory Can procedures and data be No Yes distinguished and separately protected Can tables whose size fluctuates No Yes be accommodated easily ls sharing of procedures No Yes between users facilitated Why was this technique To get a large To allow programs invented linear address and data to be broken space without up into logically having to buy independent address more physical spaces and to aid memory sharing and protection Segmentation with paging MULTICS a Each segment is divided up into pages a Each segment descriptor points to a page table 4 35 bits gt i i Page 2 entry v v Page 1 entry Segment 6 descriptor Page 0 entry Segment 5 descriptor Page table for segment 3 Segment 4 descriptor Segment 3 descriptor i i Segment 2 descriptor v N Segment 1 descriptor Page 2 entry Segment 0 descriptor Page 1 entry Descriptor segment Page 0 entry Page table for segment 1 Segmentation with paging MULTICS a Each entry in segment table 18 9 1 1 1 3 Main memory address Segment length ot the page table in pages 6 I ll ll Page Slze 0 1024 words 1 64 words 0 segment is paged 1 segment is not paged Miscellaneous bits Protection bits Segmentation with paging MULTICS M U LTI CS virtual address Segment number Page Offset number Word Descriptor Page frame Segment Page ID set number Descriptor number Page Page segment table Conversion of a 2 part MULTICS address into a main memory address El El Segmentation with Paging TLB operation Comparison 395 this entry used Segment Virtual Page number page frame Protection Age i 4 1 7 Readwrite 13 1 6 O 2 Read only 10 1 12 3 1 Readwrite 2 1 0 2 1 O Execute only 7 1 2 2 12 Execute only 9 1 fv Simplified version of the MULTIcs TLB Existence of 2 page sizes makes actual TLB more complicated Spare Slides Anatomy 01 0 Page fan wNI o Logical memOF Y TLB miss wNI o 0 1 off 2 8 3 Restart Proc 4 5 E Update PTE 6 6 9 v 7 7 Brmg in page i 8 2 V 9 A i Page 10 5 v fan 4 physical memory Find Frame Page Table i O Ge r page from backing STOWa Segmentation amp paging in The Pen39rium Descriptor Base address 0 gt Limit Other fields l 32Bit linear address Conversion of a selector offse39l39 pair 10 a linear address Segmen39ra39rion amp paging in The Pentium Bits 13 12 Index quot O GDT1 LDT Privilege level 03 A Pentium segment selector Segmentation amp paging in The Pentium O lBBit segment 1 32 Bit segment 0 Li is in bytes 1 Li is in pages 0 Segment is absent from memory 1 Segment is present in memory Privilege level CI 3 0 System L 1Appicati0n Se mentt eand rotection V V 9 YP F3 Base 24 31 G D 0 1 1139 P DPL 5 Type Base16 23 4 Base 015 Limit 015 0 32 Bits Relative address a Pentium segment descriptor Implementation Issues Operating System Involvement with Paging Four times when 05 involved with paging Process creation 7 determine program size 7 create page table Process execution 7 MMU reset for new process 7 TLB flushed Page fault time 7 determine virtual address causing fault 7 swap target page out needed page in Process termination time 7 release page table pages CS 333 Introduction to Operating Systems Class 2 OSRelated Hardware amp Software The Process Concept Jonathan Walpole Computer Science Portland State University Lecture overview OSRelafed Hardware amp Software Memory pro rec rion and reloco rion Vir ruol memory amp MMUs IO amp In rerrup rs Processes Process scheduling Process s ro res Process hierarchies Process sys rem calls in Unix Memory protection and relocation a Memory protection basic ideas virtual vs physical addresses address range in each application starts at 0 4 base registerquot used to convert each virtual address to a physical address before main memory is accessed address is compared to a limit register to keep memory references within bounds a Relocation by changing the base register value a Paged virtual memory same basic concept but more powerful and complex Base amp Limit Registers single amp multiple 3 1 Engaa mx biw 371332 395 39m 39quotquotquot u frr Ir39Q r rquot 39 j LquotFq 39 39lh 39 t39 li WJ sr w M quotfr Jquot1 lt mm mgrm4 h Virtual memory and MMUs a Memory management unit MMU hardware provided equivalent of base registers at the granularity of pages of memory say ZkB ie lots of them 4 supports relocation at page granularity applications need not occupy contiguous physical memory a Memory protection limit registers don39t work in this context perpage and perapplication protection registers a Relocation and protection occur at CPU speeds What about IO devices Monitor g 11 9 m i 39 Bus A simplified view of a compu rer39 sys rem Structure of a large Pentium system What about IO devices Monitor g 11 9 m i 39 Bus A simplified view of a compu rer39 sys rem How do programs interact with devices a Devices vs device controllers vs device drivers device drivers are part of the OS programs call the 05 which calls the device driver a Device drivers interact with device controllers either using special IO instructions or by readingwriting controller registers that appear as memory locations a Why protect access to devices by accessing them indirectly via the OS How do devices interact with programs a Interrupts Different types of interrupts I Timer interrupts z Allows OS to maintain control z One way to keep track of time 10 interrupts 4 Keyboard mouse disks etc I u Hardware failures I Program generated traps z Programming errors seg faults divide by zero etc z System calls like read write gettimeofday Timer interrupts a 05 can ask timer device to interrupt after a specified time period has elapse a Interrupt invokes timer interrupt handler which invokes OS quotschedulerquot a 05 can take the opportunity to save the current application and restore a different one 4 context switch Why use traps for system calls u The Operating System is just a program a It must have the privilege to manipulate the hardware z set base and limit registers for memory protection z access devices z set and clear mode bit to enable privilege u If user programs execute with the mode bit clear and do not have privilege to set it how can they invoke the 05 so that it can run with the mode bit set z That39s what traps do set the mode bit and begin execution at a specific point in memory in the OS System calls a System calls are the mechanism by which programs communicate with the 05 u Implemented via a TRAP instruction u Example UNIX system calls open read write close kill signal fork wait exec getpid link unlink mount chdir setuid getuid chown
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'