Module 10: Virtual Memory Background(背景) Demand Paging(请求页式) ° Performance of Demand Paging(请求页式的性能) Page Replacement(页置换) Page-Replacement Algorithms(页置换算法) ● Alocation of frames(页框的分配) ° Thrashing(簸) Other Considerations(其他考虑) Demand Segmenation(请求段式) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.1 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Module 10: Virtual Memory • Background（背景） • Demand Paging（请求页式） • Performance of Demand Paging（请求页式的性能） • Page Replacement（页置换） • Page-Replacement Algorithms（页置换算法） • Allocation of Frames （页框的分配） • Thrashing（颠簸） • Other Considerations（其他考虑） • Demand Segmenation（请求段式）
Background Virtual memory -separation of user logical memory from physical memory.(虚拟内存一物理内存和用户逻辑内存的区分) Only part of the program needs to be in memory for execution(只有部分运行的程序需要在内存中) Logical address space can therefore be much larger than physical address space(因此,逻辑地址空间能够比物理地 址空间大) Need to allow pages to be swapped in and out(必须允许页 面能够被换入和换出) rtual| memory can be implemented via(虚拟内存能够通过以下 手段来执行) Demand paging(请求页式 Demand segmentation(请求段式 Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.2 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Background • Virtual memory – separation of user logical memory from physical memory.（虚拟内存—物理内存和用户逻辑内存的区分） – Only part of the program needs to be in memory for execution（只有部分运行的程序需要在内存中）. – Logical address space can therefore be much larger than physical address space（因此，逻辑地址空间能够比物理地 址空间大）. – Need to allow pages to be swapped in and out（必须允许页 面能够被换入和换出）. • Virtual memory can be implemented via（虚拟内存能够通过以下 手段来执行）: – Demand paging （请求页式） – Demand segmentation（请求段式）
Demand Paging Bring a page into memory only when it is needed(只有在一个页 需要的时候才把它换入内存) Less vo needed(需要很少的lo) Less memory needed(需要很少的内存) Faster response(快速响应) More users(多用户) ° Page is needed(需要页)→ reference to it(查阅此页) invalid reference(无效的访问)→abot(中止) not-in-memo(不在内存)= bring to memo(换入内存 Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.3 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Demand Paging • Bring a page into memory only when it is needed（只有在一个页 需要的时候才把它换入内存）. – Less I/O needed（需要很少的I/O） – Less memory needed （需要很少的内存） – Faster response（快速响应） – More users（多用户） • Page is needed （需要页） reference to it（查阅此页） – invalid reference（无效的访问） abort（中止） – not-in-memory（不在内存） bring to memory（换入内存 ）
Valid-Invalid Bit With each page table entry a valid-invalid bit is associated 1→in- memory,0→ not-in-memory)(在每一个页表的表项有一个有 效-无效位相关联,1表示在内存,0表示不内存) nitially valid- invalid but is set to0 on all entries(在所有的表项,这 个位被初始化为0) Example of a page table snapshot(一个页表映象的例子) Frame #t valid-invalid bit 0 page table During address translation, if valid-invalid bit in page table entry is 0(在地址转换中,如果页表表项位的值是0)→ page fault(缺页) Applied Operating System Concepts 10.4 Silberschatz, Galvin, and Gagne @1999
10.4 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Valid-Invalid Bit • With each page table entry a valid–invalid bit is associated (1 in-memory, 0 not-in-memory)（在每一个页表的表项有一个有 效- 无效位相关联，1表示在内存，0表示不内存） • Initially valid–invalid but is set to 0 on all entries（在所有的表项，这 个位被初始化为0）. • Example of a page table snapshot（一个页表映象的例子）. • During address translation, if valid–invalid bit in page table entry is 0（在地址转换中，如果页表表项位的值是0） page fault（缺页）. 1 1 1 1 0 0 0 Frame # valid-invalid bit page table
Page Fault If there is ever a reference to a page, first reference will trap to os(n 果有对一个页的访问,第一个访问要陷入0s)→ page fault(缺页) os looks at another table to decide(OS查看另一个表来决定): - Invalid reference(无效引用)→ abort(终止) Just not in memory(仅仅不在内存) Get empty frame(得到空的页框). Swap page into frame(把页换入页框) Reset tables, validation bit=1(重新设置页表,把位设为1) ° Restart instruction(重启指令): Least Recently Used(最近未使用) block move(块移动) auto increment/decrement location (区域自动增长/缩减) Applied Operating System Concepts 10.5 Silberschatz, Galvin, and Gagne @1999
10.5 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Page Fault • If there is ever a reference to a page, first reference will trap to OS（如 果有对一个页的访问，第一个访问要陷入OS） page fault（缺页） • OS looks at another table to decide（OS查看另一个表来决定）: – Invalid reference（无效引用） abort（终止）. – Just not in memory（仅仅不在内存）. • Get empty frame（得到空的页框）. • Swap page into frame（把页换入页框）. • Reset tables, validation bit = 1（重新设置页表，把位设为1）. • Restart instruction（重启指令）: Least Recently Used （最近未使用） – block move（块移动） – auto increment/decrement location （区域自动增长/缩减）
What happens if there is no free frame? Page replacement -find some page in memory, but not really in use, swap it out(页置换一找到内存中并没有使用的一些页,换出) Algorithm(算法) Performance(1A)want an algorithm which will result in minimum number of page faults(找出一个导致最小缺页数的 算法). Same page may be brought into memory several times(同一个页可 能会被装入内存多次) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.6 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts What happens if there is no free frame? • Page replacement – find some page in memory, but not really in use, swap it out（页置换—找到内存中并没有使用的一些页，换出） . – Algorithm（算法） – Performance（性能） – want an algorithm which will result in minimum number of page faults（找出一个导致最小缺页数的 算法）. • Same page may be brought into memory several times（同一个页可 能会被装入内存多次）
Performance of Demand Paging ° Page Fault Rate0Sp≤1.0(缺页率0≤p≤10) ifp=0 no page faults(如果p=0,没有缺页) ifp=1, every reference is a fault(每次访问都缺页) Effective Access Time(EAT)(有效存取时间) EAT=(1-p)x memory access p(page fault overhead [swap page out] t swap page in restart overhead) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.7 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Performance of Demand Paging • Page Fault Rate 0 p 1.0（缺页率0 p 1.0） – if p = 0 no page faults （如果p = 0 ，没有缺页） – if p = 1, every reference is a fault（每次访问都缺页） • Effective Access Time (EAT)（有效存取时间） EAT = (1 – p) x memory access + p (page fault overhead + [swap page out ] + swap page in + restart overhead)
Demand Paging EXample ° Memory access time=1 microsecond(存取内存的时间) 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out(50%的时间, 所置换的页被修改,因此需要被换出) · Swap Page Time=10msec=10,000msec(交换页的时间) EAT=(1-p)×1+p(15000 1+ 15000P(in msec) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.8 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Demand Paging Example • Memory access time = 1 microsecond （存取内存的时间） • 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out（ 50%的时间， 所置换的页被修改，因此需要被换出）. • Swap Page Time = 10 msec = 10,000 msec（交换页的时间） EAT = (1 – p) x 1 + p (15000) 1 + 15000P (in msec)
Page Replacement Prevent over-allocation of memory by modifying page-fault service routine to include page replacement(通过修改缺页服务 例程,来包含页置换,防止分配过多) Use modify(dirty) bit to reduce overhead of page transfers-only modified pages are written to disk(修改(脏)位来防止页面转 移过多一只有被修改的页面才写入磁盘) Page replacement completes separation between logical memory and physical memory -large virtual memory can be provided on a smaller physical memory(页置换完善了逻辑内存和物理内存 的划分一在一个较小的物理内存基础之上可以提供一个大的虚拟 内存 Applied Operating System Concepts 10.9 Silberschatz, Galvin, and Gagne @1999
10.9 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Page Replacement • Prevent over-allocation of memory by modifying page-fault service routine to include page replacement（通过修改缺页服务 例程，来包含页置换，防止分配过多）. • Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk（修改（脏）位来防止页面转 移过多—只有被修改的页面才写入磁盘）. • Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory（页置换完善了逻辑内存和物理内存 的划分—在一个较小的物理内存基础之上可以提供一个大的虚拟 内存
Page-Replacement Algorithms ° Want lowest page-fault rate(需要一个最小的缺页率) Evaluate algorithm by running it on a particular string of memory references(reference string) and computing the number of page faults on that string(通过运行一个内存访问的特殊序列(访问序 列),计算这个序列的缺页次数) n all our examples, the reference string is(在所有的例子中,访一 问序列是) 1,2,3,4,1,2,5,1,2,3,4,5 Applied Operating System Concepts 10.10 Silberschatz, Galvin, and Gagne @1999
10.10 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Page-Replacement Algorithms • Want lowest page-fault rate（需要一个最小的缺页率）. • Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string（通过运行一个内存访问的特殊序列（访问序 列），计算这个序列的缺页次数）. • In all our examples, the reference string is （在所有的例子中，访 问序列是） 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5