操作系统课件08.pdf

Introduction to Operating Systems Lecture 8: Virtual MemoryQIAN Weining wnqian@Institute of Massive Computing East China Normal University0846／ ／2os@sei.ecnuOutline●Observations on programs●Demand paging●Page replacement●Frame allocation●Issues0846／ ／3os@sei.ecnuObservations on programs●Modern programs require a lot of physical memory–Memory per system growing faster than 25%-30%/year●But they don’t use all their memory all of the time–90-10 rule: programs spend 90% of their time in 10% of their code–Wasteful to require all of user’s code to be in memory●Solution: use main memory as cache for Solution: use main memory as cache for diskdisk0846／ ／4os@sei.ecnuMemory hierarchy revisitedmagnetic tapesoptical diskmagnetic diskelectronic diskmain memorycacheregisterslow price large volumehigh speed0846／ ／5os@sei.ecnuDemand paging: Why?●Disk is larger than physical memory:–In-use virtual memory can be bigger than physical memory–Combined memory of running processes much larger than physical memory●More programs fit into memory, allowing more concurrency ●Principle: Transparent Level of Indirection (page table) –Supports flexible placement of physical data●Data could be on disk or somewhere across network–Variable location of data transparent to user program●Performance issue, not correctness issue04/06/086os@sei.ecnuDemand paging as caching: Issues●What is block size?–1 page●What is organization of this cache?–Arbitrary virtual-to-physical mapping●How do we find a page in the cache when look for it?–First check TLB, then page- table traversal●What is page replacement policy?–This requires more explanation…●What happens on a miss?–Go to lower level to fill miss (i.e. disk)●What happens on a write? (write-through, write back)–Definitely write-back. Need dirty bit!04/06/087os@sei.ecnuWhat's in a page table?●Page table entries (PTE)–Pointer to next-level page table or to actual page–Permission bits: valid, read-only, read-write, write-only●PTE for demand paging–Valid: Page in memory, PTE points at physical page–Not Valid: Page not in memory; use info in PTE to find it on disk when necessary04/06/088os@sei.ecnuDemand paging: How?●When page reference is valid: easy●When it is invalid in PTE–Memory Management Unit (MMU) traps to OS: Page FaultPage Fault–What does OS do on a Page Fault?: 1. 1. Choose an old page to replace: who? (discussed later)Choose an old page to replace: who? (discussed later) 2. If old page modified (“D=1”), write contents back to disk 3.Change its PTE and any cached TLB to be invalid 4.Load new page into memory from disk 5. Update page table entry, invalidate TLB for new entry 6. 6.Continue thread from original faulting location: Can we?Continue thread from original faulting location: Can we?–TLB for new page will be loaded when thread continued!–While pulling pages off disk for one process, OS runs another process from ready queue●Suspended process sits on wait queue04/06/089os@sei.ecnuSide effect of an instruction●Example 1: mov (sp)+, 10–What if page fault occurs when write to stack pointer?–Did sp get incremented before or after the page fault?●Example 2: strcpy (r1), (r2)–Source and destination overlap: can’t unwind in principle!–IBM S/370 and VAX solution: execute twice (once read-only)04/06/0810os@sei.ecnuDemand paging evaluation●As caching: EAT = Hit Rate x Hit Time + Miss Rate x Miss Time–Memory access time = 200 nanoseconds–Average page-fault service time = 8 milliseconds–Suppose p = Probability of miss, 1-p = Probably of hitEAT = (1 – p) x 200ns + p x 8 ms= (1 – p) x 200ns + p x 8,000,000ns= 200ns + p x 7,999,800ns●If one access out of 1,000 causes a page fault, then EAT = 8.2 sμ :–This is a slowdown by a factor of 4040!●What if want slowdown by less than 10%?–200ns x 1.1 m: Thrashing–Policy: if D > m, then suspend one of the processes–This can improve overall system behavior by a lot!04/06/0831os@sei.ecnuMore on VM●Compulsory missesCompulsory misses: misses that occur the first time that a page is seen–Pages that are touched for the first time–Pages that are touched after process is swapped out/swapped back in●ClusteringClustering:–On a page-fault, bring in multiple pages “around” the faulting page–Since efficiency of disk reads increases with sequential reads, makes sense to read several sequential pages●Working Set TrackingWorking Set Tracking:–Use algorithm to try to track working set of application–When swapping process back in, swap in working set04/06/0832os@sei.ecnuTake-home message●Why VM?●The basic model: demand paging●Issues–page replacement: measurements, optimal solution, approximation, implementation–frame allocation: program behavior, models–sum them up!04/06/0833os@sei.ecnuHomework●Read book●8.11●9.904/06/0834os@sei.ecnuTerm translation●virtual memory: 虚存／虚拟内存●demand paging: 按需分页／按需调页／按需请页／请求式分页 ...●thrashing: 颠簸●frame: 页框／桢●page: 页面●page fault: 缺页●First-in-first-out: 先进先出●Least recently used (LRU): 最近最少使用●Least frequently used (LFU):。