Applied Operating System Concepts Chap 10 Virtual Memory 虚 存 编写：王红玲 Applied Operating System Concepts

Applied Operating System Concepts 内容 Background（背景） Demand Paging（请求页式） Performance of Demand Paging（请求页式的性能） Page Replacement（页置换） Page-Replacement Algorithms（页置换算法） Allocation of Frames （页框的分配） Thrashing（颠簸） Other Considerations（其他考虑） Demand Segmentation（请求段式） Summary（总结） Applied Operating System Concepts

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（请求段式） Applied Operating System Concepts

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（换入内存） 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（缺页）. Frame # valid-invalid bit 1 1 1 1  page table Applied Operating System Concepts

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 （区域自动增长/缩减） 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（同一个页可能会被装入内存多次）. 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) 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) Applied Operating System Concepts

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（页置换完善了逻辑内存和物理内存的划分—在一个较小的物理内存基础之上可以提供一个大的虚拟内存. 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. Applied Operating System Concepts

First-In-First-Out (FIFO) Algorithm 先进先出算法 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement – Belady’s Anomaly（FIFO算法可能会产生Belady异常） more frames  less page faults（页就是更多的页框相反会产生更多的缺页） 1 1 4 5 2 2 1 3 9 page faults 3 3 2 4 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 4 3 Applied Operating System Concepts

Optimal Algorithm 最优算法 Replace page that will not be used for longest period of time（被置换的页将是之前最长时间不被使用的页）. 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How do you know this?（怎样知道的） Used for measuring how well your algorithm performs（用来衡量你的算法的效率）. 1 4 2 6 page faults 3 4 5 Applied Operating System Concepts

Least Recently Used (LRU) Algorithm 最近最少使用算法 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Counter implementation（计数器的实现） Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter（每一个页表项 有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中）. When a page needs to be changed, look at the counters to determine which are to change（当一个页需要改变是，查看计数器来觉得改变哪一个页0.） 1 5 2 3 5 4 4 3 Applied Operating System Concepts

LRU Algorithm (Cont.) 最近最少使用算法（续） Stack implementation – keep a stack of page numbers in a double link form（栈实现—在一个双链表中保留一个记录页数目的栈）: Page referenced（被访问的页）: move it to the top（移到栈顶） requires 6 pointers to be changed（需要改变6个指针） No search for replacement（没有为置换进行查找） Applied Operating System Concepts

Applied Operating System Concepts 页面置换算法－动画演示 Applied Operating System Concepts

LRU Approximation Algorithms LRU近似算法 Reference bit（访问位） With each page associate a bit, initially -= 0（每个页都与一个位相关联，初始值位0） When page is referenced bit set to 1（当页是访问位是设位1）. Replace the one which is 0 (if one exists). We do not know the order, however（，如果存在的话置换位为0的页。然而我们并不知道这个置换顺序）. Second chance（二次机会） Need reference bit.（需要访问位） Clock replacement.（时钟置换） If page to be replaced (in clock order) has reference bit = 1. Then（如果将要（以顺时针）交换的访问位是1，则）: set reference bit 0（把访问位设位0）. leave page in memory（把页留在内存中）. replace next page (in clock order), subject to same rules（以同样的规则，替换下一个页）. Applied Operating System Concepts

Counting Algorithms 计数算法 Keep a counter of the number of references that have been made to each page.（用一个计数器记录对每一个页的访问次数。） LFU Algorithm: replaces page with smallest count（以最小的计数置换一个页）. MFU Algorithm: based on the argument that the page with the smallest count was probably just brought in and has yet to be used（以下面的观点为基础，最小计数的页也许刚刚被换入和使用）. Applied Operating System Concepts

Allocation of Frames 页框的分配 Each process needs minimum number of pages（每个进程所需要的最少的页的数目）. Example: IBM 370 – 6 pages to handle SS MOVE instruction: instruction is 6 bytes, might span 2 pages. 2 pages to handle from. 2 pages to handle to. Two major allocation schemes（两个主要的分配策略）. fixed allocation（固定分配） priority allocation（优先分配） Applied Operating System Concepts

Applied Operating System Concepts Fixed Allocation 固定分配 Equal allocation（平均分配） – e.g., if 100 frames and 5 processes, give each 20 pages（例：如果有100个页框，和5个进程，则每个进程分给20个页）. Proportional allocation（按比率分配） – Allocate according to the size of process（根据每个进程的大小来分配）. Applied Operating System Concepts

Priority Allocation 优先级分配 Use a proportional allocation scheme using priorities rather than size（根据优先级而不是大小来使用比率分配策略）. If process Pi generates a page fault,（如果进程Pi产生一个缺页） select for replacement one of its frames（选择替换其中的一个页框）. select for replacement a frame from a process with lower priority number（从一个较低优先级的进程中选择一个页面来替换）. Applied Operating System Concepts

Global vs. Local Allocation 全局分配和局部分配 Global replacement（全局替换） – process selects a replacement frame from the set of all frames; one process can take a frame from another（进程在所有的页中选择一个替换页面；一个进程可以从另一个进程中获得页面）. Local replacement （局部替换）– each process selects from only its own set of allocated frames（每个进程只从属于它自己的页中选择）. Applied Operating System Concepts

Applied Operating System Concepts Thrashing 颠簸 If a process does not have “enough” pages, the page-fault rate is very high. This leads to（如果一个进程没有足够的页，那么缺页率将很高，这将导致）: low CPU utilization（CPU利用率低下）. operating system thinks that it needs to increase the degree of multiprogramming（操作系统认为需要增加多道程序设计的道数）. another process added to the system（系统中将加入一个新的进程）. Thrashing（颠簸）  a process is busy swapping pages in and out（一个进程的页面经常换入换出）. Applied Operating System Concepts

Thrashing Diagram 颠簸图示 Why does paging work?（为什么分页工作） Locality model（位置模式） Process migrates from one locality to another（进程从一个位置移到另一个位置）. Localities may overlap（位置可能重叠）. Why does thrashing occur?（为什么颠簸会发生）  size of locality > total memory size Applied Operating System Concepts

Working-Set Model 工作集模型   working-set window  a fixed number of page references Example: 10,000 instruction WSSi (working set of Process Pi) = total number of pages referenced in the most recent  (varies in time) if  too small will not encompass entire locality. if  too large will encompass several localities. if  =   will encompass entire program. D =  WSSi  total demand frames if D > m  Thrashing Policy if D > m, then suspend one of the processes. Applied Operating System Concepts

Keeping Track of the Working Set 理解工作集 Approximate with interval timer + a reference bit（近似的一个内部时钟和一个访问位） Example:  = 10,000 Timer interrupts after every 5000 time units.（每5000个时钟单位时钟中断） Keep in memory 2 bits for each page.（为每个页在内存中保留两个位） Whenever a timer interrupts copy and sets the values of all reference bits to 0.（任何时候一个时钟中断拷贝，把所有访问位设为0） If one of the bits in memory = 1  page in working set.（如果一个在内存中的位是0，说明页在工作集） Why is this not completely accurate?（为什么不是非常的精确） Improvement = 10 bits and interrupt every 1000 time units.（提高：用10个位，以及每1000个时钟单位中断） Applied Operating System Concepts

Page-Fault Frequency Scheme 缺页率策略 Establish “acceptable” page-fault rate（设置可接受的缺页率）. If actual rate too low, process loses frame（如果缺页率太低，回收一些进程的页框）. If actual rate too high, process gains frame（如果缺页率太高，就分给进程一些页框）. Applied Operating System Concepts

Other Considerations 其他的一些考虑 Prepaging （预先调页） Page size selection（页面尺寸选择） Fragmentation（碎片） table size （表大小） I/O overhead（I/O开销） Locality（位置） Applied Operating System Concepts

Other Consideration (Cont.) 其他的一些考虑（续） Program structure（程序结构） Array A[1024, 1024] of integer Each row is stored in one page One frame Program 1 for j := 1 to 1024 do for i := 1 to 1024 do A[i,j] := 0; 1024 x 1024 page faults Program 2 for i := 1 to 1024 do for j := 1 to 1024 do A[i,j] := 0; 1024 page faults I/O interlock and addressing（I/O连接和地址） Applied Operating System Concepts

Demand Segmentation 请求分段 Used when insufficient hardware to implement demand paging（当请页的硬件不充足时使用）. OS/2 allocates memory in segments, which it keeps track of through segment descriptors（操作系统以段来分配内存，它通过段描述符来进行跟踪） Segment descriptor contains a valid bit to indicate whether the segment is currently in memory（段描述符有一个有效位来说明段是否以在内存）. If segment is in main memory, access continues（如果段已在主存中，继续存取）, If not in memory, segment fault（如果不在内存中，缺段中断）. Applied Operating System Concepts

Applied Operating System Concepts Summary总结 Virtual memory can be a very interesting subject since it has so many different aspects: page faults, managing the backing store, page replacement, frame allocation, thrashing, page size. The objectives of this chapter are to explain these concepts and show how paging works. A simulation is probably the easiest way to allow the students to program several of the page-replacement algorithms and see how they really work. If an interactive graphics display can be used to display the simulation as it works, the students may be better able to understand how paging works. We also present an exercise that asks the student to develop a Java program that implements the FIFO and LRU page replacement algorithms. Applied Operating System Concepts

Applied Operating System Concepts 作业 P339 10.3 10.4 P340 10.5 10.8 P341 10.9 10.10 P342 10.11 10.16 Applied Operating System Concepts