CHAPTER 8 VIRTUAL MEMORY Simple Memory Management Techniques 当进程运行时，该进程相关的程序和数据全部驻留内存

8.1 Hardware and Control Structures Two characteristics of paging and segmentation are the keys to this breakthrough: (最重要的是分页和分段的两个特点) All memory references within a process are logical addresses that are dynamically translated into physical addresses at run time. This means that a process may be swapped in and out of main memory such that it occupies different regions.(进程中的所有存储器访问都是逻辑地址，这些逻辑地址在运行时动态地被转换成物理地址。这意味着一个进程可以被换入或换出主存，因此，在执行过程中的不同时刻，它占据了主存中的不同区域)

2. A process may be broken up into pieces that do not need to located contiguously in main memory during execution. (一个进程可以划分成许多块（页和段），在执行过程中，这些块不需要连续地位于主存中 )

★由于以上两个特点，可以实现虚拟存储管理，其工作原理： 假设把一个新进程取进存储器时，操作系统仅取进包含程序开始处的一个或几个块到主存中（任何时候都在主存中的部分被定义成进程常驻集），当进程执行时，只要所有的存储器访问都是访问常驻集中的单元，执行就可以顺利进行；如果处理器遇到了一个不在主存中的逻辑地址，则它产生一个中断，操作系统把被中断的进程置于阻塞状态，把引发访问故障的逻辑地址的进程块取进主存，操作系统把受到影响的进程置回就绪状态。

★由于采用部分块就可以运行，则会提高系统的使用率，其理由如下： 1.主存中保留多个进程 由于对任何特定的进程都仅仅装入它的某些块，因此就有足够的 空间可以放置更多的进程。这使得可以更有效地利用处理器. 2.进程可以比主存的全部空间还大 通过基于分页或分段的虚拟存储器，这项工作可以由操作系统和硬件完成。

由于一个进程只能在主存中执行，因此这个存储器称作实存（real memory）。但是程序员或用户感觉到的是一个更大的存储器，通常是被分配在磁盘上，这称作虚拟存储器（virtual memory），简称虚存。 表8．1总结了使用虚存和不使用虚存的情况下分页和分段的特点。 (P322)

Locality and Virtual Memory The benefits of virtual memory are attractive, but is the scheme practical ?(虚存的优点是很具有吸引力的，但这个方案切实可行吗？ ) Consider a large process, consisting of a long program plus a number of arrays of data. Over any short period of time, execution may be confined to a small section of the program (e.g.,subroutine) and access to perhaps only one or two arrays of data. (考虑由一个很长的程序和许多数据数组组成的大进程，在任何一段很短的时间内，执行可能会局限在很小的一段程序中（例如一个子程序），并且可能仅仅会访问一个或两个数据数组)

Principle of Locality (局部性原理) The principle of locality states that program and data references within a process tend to cluster.(局部性原理描述了一个进程中程序和数据引用的簇聚性倾向) The assumption that only a few pieces of a process will be needed over a short period of time is valid.(假设在很短的时间内仅需要进程的一部分块是合理的)

One way to confirm the principle of locality is to look at the performance of processes in a virtual memory environment .(see figure 8.1 P323) (证实局部性原理的一种方法是在虚存环境中查看进程的执行情况)

Thrashing The processor spends most of its time swapping pieces rather than executing user instructions.(处理器的大部分时间都用于交换块，而不是执行指令的这种情况称作系统抖动 ) 利用局部性原理对将来可能需要的块进行明智的猜测，从而可避免系统抖动。

Support Needed for Virtual Memory Hardware must support paging and segmentation Operating system must be able to management the movement of pages and/or segments between secondary memory and main memory

Paging The same device， a page table， is needed when we consider a virtual memory scheme based on paging ． (当我们考虑基于分页的虚拟存储器方案，也需要同样的设备——页表) The page table entries become more complex． (页表项变得更复杂。) Because only some of the pages of a process may be in main memory. (由于一个进程可能只有一些页在主存)

A bit is needed in each page table entry in indicate whether the corresponding page is present(p)in main memory or not . (因而每个页表项需要有一位（P）来表示它所对应的页当前是否在主存中 )

Modify Bit in Page Table Another modify bit is needed to indicate if the page has been altered since it was last loaded into main memory If no change has been made, the page does not have to be written to the disk when it needs to be swapped out

Page Table Entries

Page Table Structure 现代的大多数计算机系统，都支持非常大的逻辑地址空间，页表就变得非常大 ，又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用大的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用多种方法来解决这一问题： ①采用离散分配方式来解决难以找到一块连续的大内存空间的问题。 ②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

Virtual Page Tables The entire page table may take up too much main memory Page tables are also stored in virtual memory When a process is running, part of its page table is in main memory.

Two-Level Scheme for 32-bit Address

Inverted Page Table (反置页表)

Virtual Memory 使用虚拟存储管理技术，用户将会感觉到系统的内存空间比实际内存大。 系统的可用内存空间并非计算机系统中的实际物理内存，它包含物理内存及一部分磁盘空间。 习惯上，人们把这种用户感觉上存在但实际上并不存在的内存称为虚拟内存。

Translation Lookaside Buffer (快表) Each virtual memory reference can cause two physical memory accesses（每个虚存访问可能引起两次主存的访问） one to fetch the page table one to fetch the data

Contains page table entries that have been most recently used in TLB。 To overcome this problem a high-speed cache is set up for page table entries （为了克服这个问题，建立了页表项的高速缓存） called the TLB - Translation Lookaside Buffer Contains page table entries that have been most recently used in TLB。 （在TLB中，包含最近用过的页表项）

Operation of Page and TLB 1. Given a virtual address, processor examines the TLB 2. If page table entry is present (a hit), the frame number is retrieved and the real address is formed。 (如果命中，则页帧号形成实地址) 3. If page table entry is not found in the TLB (a miss), the page number is used to index the process page table。

4. First checks if page is already in main memory . if not in main memory a page fault （缺页）is issued 5. The TLB is updated to include the new page entry

Page Size 分页系统中，页面的大小总是与页框的尺寸相等；页框的尺寸则由CPU硬件逻辑定义。 较小的页面有利于减少内零头，有利于提高内存的利用率；然而，较小的页面将导致页表过大，从而降低CPU 访问页表时的命中率(Hit Rate)。 通常，内外存之间的数据交换以块(Block)为单位；块越大，内外存之间的数据交换效率越高。因此，较大的页面有利于提高页面换进换出内存的效率

Example Page Sizes

Segmentation （分段） Virtual-Memory Implication（虚拟存储器） May be unequal, dynamic size (段可以不相等，动态尺寸变化） Simplifies handling of growing data structures（简化不断增长的数据结构） Allows programs to be altered and recompiled independently （允许程序独立地改变或重新编译） Lends itself to sharing data among processes （有助于进程间的共享） Lends itself to protection （有助于进程间的保护）

Segment Tables corresponding segment in main memory Each entry contains the length of the segment A bit is needed to determine if segment is already in main memory Another bit is needed to determine if the segment has been modified since it was loaded in main memory

Segment Table Entries

Segment Protection 越界检查 存取控制 为了进行越界检查，系统在段表寄存器中保存当前进程的段表长度并在每个段表入口中保存各个段的长度。 存取控制 为了进行存取控制，系统在每个段表入口中设置一个 “存取控制”字段，用于规定进程对段的访问权限

Segment Protection 为了进行环保护，系统将在每个段表入口中保存各个段所在环的特权级别。 环保护通常遵循以下保护规则： 一个程序可以调用驻留在同级环或较高特权环中的服务； 一个程序可以访问驻留在同级环或较低特权环中的数据

环0 环0 调用 ⊙ 返回 环1 环1 数据访问 ⊙ 调用 ⊙ 返回 环2 环2 ⊙ 数据访问 返回⊙调用 环保护机制

Combined Paging and Segmentation 在使用简单段页存储管理技术的系统中，每个进程均被编程人员分割成多个Segment， 每个段又被系统分割成多个Page 相应地，物理内存被系统划分成多个Frame。 当一个进程被装入物理内存时，系统为该进程的每个段的各页面独立地分配一个Frame；一个进程的同一段的多个页面不必存放在连续的多个Frame中。

Combined Segmentation and Paging

Address Translation

Combined Paging and Segmentation 分页系统中，内零头得到了有效的抑制，外零头则完全被消除；因此，使用分页技术可以提高物理内存的利用率。 分段系统中，动态数据结构、程序和数据共享、程序和数据保护等问题得到了妥善解决；因此，分段技术有利于模块化程序设计。 段页技术汲取了分页技术和分段技术的上述优点

8.2 Operating System Software OS存储管理子系统的设计要素 是否使用虚拟存储管理技术 选用分页技术、分段技术还是段页技术 采用什么样的存储管理算法 其中， 前两个问题属于CPU硬件设计范畴；从OS设计者的角度看，它们相当于“选用什么样的硬件平台作为 OS的运行平台”。 最后一个问题属于OS软件设计范畴；该问题是后面讨论的重点内容

除了一些老的个人计算机 OS（比如 MS-DOS）以及专用OS外，绝大多数 OS 均使用了虚拟存储管理技术。 因此，我们主要讨论虚拟存储分页技术中的软件策略

Placement Policy(放置策略) Fetch Policy(获取策略) Replacement Policy(置换策略) Cleaning Policy(清除策略) Load Control(负载控制)

Placement Policy (放置策略) 解决的基本问题： 系统应当在内存的什么位置为活动进程分配frame？

Placement Policy (放置策略) 绝大多数使用虚拟存储分页技术的系统可以在内存中的任何位置为活动进程分配frame。 但是，有些系统需要专门技术解决内存中页面的放置问题。 顺便指出，在使用虚拟存储分段技术的系统中，放置策略所要解决的问题同样十分重要

Fetch Policy (获取策略) Determines when a page should be brought into memory？ （决定什么时候提取页到主存？）

Fetch Policy (放置策略) Demand paging（请求调页） only brings pages into main memory when a reference is made to a location on the page （当访问到该页时，才请求调页） - Many page faults when process first started Prepaging（预调页） brings in more pages than needed More efficient to bring in pages that reside contiguously on the disk （将磁盘上相近的页面调入主存）

Replacement Policy （置换策略） Which page is replaced? 当一个页面欲装入内存时，系统应当在什么范围内判断已经没有空闲frame分配给新的页面？ 当系统在指定的范围内发现已经没有空闲frame分配给新的页面时，系统应当从指定的范围内选择哪个页面移出内存？ 有两种策略：① 可变分配，全局置换； ② 可变分配，局部置换；

Variable Allocation,Global Scope（可变分配，全局置换） 采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。这样，凡产生缺页（中断）的进程，都将获得新的物理块；仅当空闲物理块队列中的物理块用完时， OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。

★可变分配，全局置换的主要特点： Easiest to implement Adopted by many operating systems Operating system keeps list of free frames Free frame is added to resident set of process when a page fault occurs If no free frame, replaces one from another process

Variable Allocation,Local Scope （可变分配，局部置换) When new process added, allocate number of page frames based on application type, program request, or other criteria （当新进程加载时，根据应用类型、程序请求或其它标准来分配页帧）

When page fault occurs, select page from among the resident set of the process that suffers the fault （当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出） 采用可变分配，局部置换算法就不会影响其它进程的运行。

驻留集尺寸与置换范围 固定分配策略将导致系统必须使用局部置换策略；反之，全局置换策略将导致系统必须使用可变分配策略 可变分配策略与局部置换策略也可组合，即系统可根据性能的需要增加或减少分配给每个活动进程的frame数；当进程的frame全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一 个页面移出内存

Replacement Policy （置换注意事项） Frame Locking If frame is locked, it may not be replaced Kernel of the operating system Control structures I/O buffers Associate a lock bit with each frame

Basic Replacement Algorithms Optimal Algorithm(最佳算法) Least Recently Used Algorithm(最近最少使用算法) First-in First-out Algorithm(先进先出算法) Clock Algorithm(时钟算法)

Optimal Algorithm (最佳置换算法) 置换在将来再也不被访问的页面 置换在最远的将来才被访问的页面

Optimal Algorithm

Optimal Algorithm 从原理上讲，OPT算法在所有置换算法中具有最佳性能；但，Impossible to have perfect knowledge of future events 在OS研究领域，OPT算法常常被用作比较各种置换算法性能的参照标准。

Least Recently Used (LRU) (最近最少使用置换算法) Replaces the page that has not been referenced for the longest time By the principle of locality, this should be the page least likely to be referenced in the near future Each page could be tagged with the time of last reference. This would require a great deal of overhead.

Least Recently Used (LRU)

Least Recently Used (LRU) 从原理上讲，LRU算法可以被实现；但任何一种实现方法都将产生很大的系统开销。因此，许多OS均使用近似LRU算法。 一些应用程序具有很强的非局部存储引用（比如顺序存储引用）特征。对于此类应用程序，LRU算法将有很差的表现。

First-in, first-out (FIFO) Treats page frames allocated to a process as a circular buffer Pages are removed in round-robin style Simplest replacement policy to implement Page that has been in memory the longest is replaced These pages may be needed again very soon

First-in, first-out (FIFO)

First-in, first-out (FIFO)

Clock Policy (时钟置换算法) Additional bit called a use bit When a page is first loaded in memory, the use bit is set to 1 When the page is referenced, the use bit is set to 1 When it is time to replace a page, the first frame encountered with the use bit set to 0 is replaced. During the search for replacement, each use bit set to 1 is changed to 0

Clock Policy CLOCK算法中，系统将置换范围内的所有frame 组成一 个环形缓冲区，并为其设置一个扫描指针 没有进行页面置换时，扫描指针总是指向上一次进行页面置换时被置换页面所在位置的下一个位置。

Clock Policy 当需要进行页面置换时，系统将移动扫描指针搜索置换范围内的各个frame以便找到一个U位为0的frame： 如果当前扫描指针所指向的frame其U位为1，那么系统将该frame的U位设置为0，扫描指针移到下一个位置，继续搜索； 如果当前扫描指针所指向的frame其U位为0，则系统将该frame中的页面作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。

Clock Policy