Operating System 简明教程
Operating System - Virtual Memory
计算机可以寻址比系统物理安装量更多的内存。此额外内存实际上称为 virtual memory ,它是设置用于模拟计算机 RAM 的硬盘一部分。
A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that’s set up to emulate the computer’s RAM.
此方案的主要明显优点在于程序可以比物理内存更大。虚拟内存有两个用途。首先,它允许我们通过使用磁盘来扩展物理内存的使用。其次,它允许我们具有内存保护,因为每个虚拟地址都转换为一个物理地址。
The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using disk. Second, it allows us to have memory protection, because each virtual address is translated to a physical address.
以下情况不需要将整个程序完全加载到主内存中。
Following are the situations, when entire program is not required to be loaded fully in main memory.
-
User written error handling routines are used only when an error occurred in the data or computation.
-
Certain options and features of a program may be used rarely.
-
Many tables are assigned a fixed amount of address space even though only a small amount of the table is actually used.
-
The ability to execute a program that is only partially in memory would counter many benefits.
-
Less number of I/O would be needed to load or swap each user program into memory.
-
A program would no longer be constrained by the amount of physical memory that is available.
-
Each user program could take less physical memory, more programs could be run the same time, with a corresponding increase in CPU utilization and throughput.
面向通用用途的现代微处理器,内存管理单元或 MMU 已内置到硬件中。MMU 的工作是将虚拟地址转换为物理地址。以下是一个基本示例:
Modern microprocessors intended for general-purpose use, a memory management unit, or MMU, is built into the hardware. The MMU’s job is to translate virtual addresses into physical addresses. A basic example is given below −

虚拟内存通常通过按需分页实现。它也可以在分段系统中实现。按需分段也可以用于提供虚拟内存。
Virtual memory is commonly implemented by demand paging. It can also be implemented in a segmentation system. Demand segmentation can also be used to provide virtual memory.
Demand Paging
按需分页系统与交换分页系统非常相似,其中进程驻留在辅助内存中,并且仅在需要时加载页面,而不是预先加载。当发生上下文切换时,操作系统不会将任何旧程序的页面复制到磁盘或将任何新程序的页面复制到主内存。相反,它只在加载第一页后开始执行新程序,并在引用时获取该程序的页面。
A demand paging system is quite similar to a paging system with swapping where processes reside in secondary memory and pages are loaded only on demand, not in advance. When a context switch occurs, the operating system does not copy any of the old program’s pages out to the disk or any of the new program’s pages into the main memory Instead, it just begins executing the new program after loading the first page and fetches that program’s pages as they are referenced.

在执行程序时,如果程序引用了由于不久前交换出去而不在主内存中的页面,则处理器将这种无效内存引用视为 page fault ,并将控制权从程序转移到操作系统以要求将页面调回到内存。
While executing a program, if the program references a page which is not available in the main memory because it was swapped out a little ago, the processor treats this invalid memory reference as a page fault and transfers control from the program to the operating system to demand the page back into the memory.
Page Replacement Algorithm
页面替换算法是操作系统用来决定将哪些内存页面换出、在需要分配内存页时写入磁盘的技术。分页发生在页面错误发生且不能将空闲页面用于分配目的时,原因是页面不可用或空闲页面的数量低于所需页面。
Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages.
当选择了要替换并换出的页面后,如果再次引用该页面,则必须从磁盘中读入,这需要 I/O 完成。此过程决定了页面替换算法的质量:等待页面输入所需的时间越少,算法就越好。
When the page that was selected for replacement and was paged out, is referenced again, it has to read in from disk, and this requires for I/O completion. This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
页面替换算法会查看硬件提供的有关访问页面的有限信息,并尝试选择应替换的页面以最小化页面缺失总数,同时平衡算法本身的存储器和处理器时间成本。存在许多不同的页面替换算法。我们通过在特定的内存引用字符串上运行算法并计算页面错误数来评估算法。
A page replacement algorithm looks at the limited information about accessing the pages provided by hardware, and tries to select which pages should be replaced to minimize the total number of page misses, while balancing it with the costs of primary storage and processor time of the algorithm itself. There are many different page replacement algorithms. We evaluate an algorithm by running it on a particular string of memory reference and computing the number of page faults,
Reference String
内存引用字符串称为引用字符串。引用字符串是人工生成的,或通过跟踪给定系统并记录每个内存引用的地址而生成的。后一种选择会产生大量的数据,我们注意到两件事。
The string of memory references is called reference string. Reference strings are generated artificially or by tracing a given system and recording the address of each memory reference. The latter choice produces a large number of data, where we note two things.
-
For a given page size, we need to consider only the page number, not the entire address.
-
If we have a reference to a page p, then any immediately following references to page p will never cause a page fault. Page p will be in memory after the first reference; the immediately following references will not fault.
-
For example, consider the following sequence of addresses − 123,215,600,1234,76,96
-
If page size is 100, then the reference string is 1,2,6,12,0,0
First In First Out (FIFO) algorithm
-
Oldest page in main memory is the one which will be selected for replacement.
-
Easy to implement, keep a list, replace pages from the tail and add new pages at the head.

Optimal Page algorithm
-
An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An optimal page-replacement algorithm exists, and has been called OPT or MIN.
-
Replace the page that will not be used for the longest period of time. Use the time when a page is to be used.

Least Recently Used (LRU) algorithm
-
Page which has not been used for the longest time in main memory is the one which will be selected for replacement.
-
Easy to implement, keep a list, replace pages by looking back into time.

Page Buffering algorithm
-
To get a process start quickly, keep a pool of free frames.
-
On page fault, select a page to be replaced.
-
Write the new page in the frame of free pool, mark the page table and restart the process.
-
Now write the dirty page out of disk and place the frame holding replaced page in free pool.