background

CH8的内存管理方案需要将整个进程放入内存，动态载入只能减轻这一限制

Code needs to be in memory to execute, but entire program rarely used.

execute partially-loaded program

• 程序不受现有物理内存大小限制，可以为virtual address space编写程序
• 更多程序可以同时执行，CPU利用率增加，而响应时间、周转时间不增加
• 载入或交换程序所需IO变少，用户程序运行更快

Virtual memory – separation of user logical memory from physical memory.

动态内存分配，堆向上增长；子程序调用，栈向下增长。包括洞的虚拟地址空间是稀地址空间。

Enables sparse address spaces with holes left for growth, dynamically linked libraries, etc.

Virtual memory allows files and memory to be shared by two or more processes through page sharing.

虚拟内存实现：

• demand paging
• demand segmentation

demand paging 按需调页

Lazy swapper: never swaps a page into memory unless that page will be needed.

swapper对整个进程进行操作，pager只对进程的单个页进行操作

页表条目，valid-invalid bit: valid-合法也在内存 invalid-无效(不在逻辑地址空间) 或 有效但在磁盘

pure demand paging: 只有在需要时才将页调入内存

单个指令可能访问多个页的内存(一页指令，其他页数据)，一个指令可能产生多个page fault. 不过由于locality of reference, 按需调页的性能还算合理。

按需调页的硬件支持：

• Page table with valid-Invalid bit
• Secondary memory (swap device with swap space)

请求调页的关键要求是能够在页错误后instruction restart

如果页错误在获取操作数时，再次获取指令，再次译码指令，再次获取操作数。

一个指令可能改变多个不同位置。若源和目的块有重叠，源块可能已修改，不能简单地再次执行。(微码计算试图访问两块的两端；临时寄存器保存覆盖位置的值)

EAT = (1– p) * memory access time + p * page fault service time

page fault service time = page fault overhead+[ swap page out ]+swap page in+restart overhead

处理页错误中断和重新启动进程可以通过仔细编码降低开销

EAT与页错误率直接相关

与文件无关的页需要使用交换空间

Copy-on-Write 写时复制

fork()使用写时复制技术

父子进程开始时共享同一页面。这些页面标记为写时复制页(只有可能修改的页需要标记)。如果任一进程对页进行写，创建一个共享页的副本。

COW allows more efficient process creation as only modified pages are copied.

free pages are allocated from a pool of free pages. 采用按需填零(zero-fill-on-demand)技术分配这些页，需要分配前先填零，因此清除了以前的内容。

vfork()，不采用copy-on-write，vfork()将父进程挂起，子进程使用父进程的地址空间。如果子进程修改父进程地址空间的任何页， 父进程重启时可见。主要用于子进程被创建后立即调用exec()的情况。比较高效。用于实现UNIX命令行shell的接口。

page replacement

Use modify bit (dirty bit) to reduce overhead of page transfers. 不修改的话不需要写回磁盘

Page replacement completes separation between logical memory and physical memory.

frame-allocation algorithm

page replacement algorithm

reference string: 内存的引用序列

FIFO

Belady’s anomaly: 页错误率可能会随着所分配的帧数的增加而增加

OPT/MIN

置换最长时间不会使用的页

未来知识

LRU

最长时间没有使用的页

By the principle of locality, this should be the page least likely to be referenced in the near future.

Associates with each page the time of that page’s last use.

两种可行实现：

• counter

  每个页表项关联一个使用时间域。对每次引用，计数器增加。置换具有最小时间的页。

• stack

  没引用一个页，页就从栈中删除并放在顶部

  No search for replacement, LRU page is at the bottom.

LRU Approximation Algorithms

LRU needs special hardware and still slow.所以用近似算法

页表每项都关联一个reference bit, 每引用一个页(读or写)，引用位被硬件置1

Reference bit algorithm

When page is referenced, the bit is set to 1 by the hardware.

Replace the one which is 0 (if one exists).

Problem ：We do not know the order.

Additional-reference-bits algorithm

Keep an 8-bit byte for each page in a table in memory.

规定时间间隔里记录引用位

At regular intervals, a timer interrupts, OS shifts the reference bit for each page into the high-order bit of its 8- bit byte, shifting the other bits right by 1 bit and discarding the low-order bit.

将这8位看作无符号整数，置换具有最小值的页

Second chance / Clock

Basic algorithm: FIFO

循环队列，指针向前移动直到找到一个引用位为0的页，在向前移动时，清除引用位。

如果所有位均已设置，会遍历整个队列。成了FIFO

Enhanced Second-Chance Algorithm

(reference bit, modify bit)

(0,0)最好 (0,1) (1,0) (1,1)

降低IO

Counting-based page replacement

每个页保留一个用于记录引用次数的计数器。

LFU: replaces page with the smallest count

MFU: page with the smallest count was probably just brought in and has yet to be used.

page allocation 帧分配

分配至少最少数量的帧。必须有足够的帧容纳所有单个指令所引用的页。

每个进程的帧的最少数量由体系结构决定，最大数量由可用物理内存的数量决定。

• fixed allocation

  高低优先级一样处理

  when a page fault occurs, one of the pages of that process must be replaced. – Local replacement

  固定分配必须局部置换(置换自己进程里的页)

  • equal allocation

    n个进程之间分配m个帧，每个m/n帧

  • proportional allocation

    根据进程大小比例地分配内存

    进程pi的虚拟内存大小si

    a i = s i /S * m

• priority allocation

  Use a proportional allocation scheme using priorities rather than size, or on a combination of size and priority.

Local replacement: select for replacement one of its frames

​ 分配每个进程的帧的数量不变

Global replacement: select for replacement a frame from a process with lower priority number

​ 易于实现。更好的系统吞吐量，常用。

​ OS keeps list of free frames.

​ 进程不能控制其页错误率(受其他进程调页行为影响)

thrashing 系统颠簸

thrashing: 频繁的页调度行为

如果一个进程在换页上用的时间多于执行时间，这个进程就在颠簸

CPU调度程序发现CPU使用率降低，增加多道程序程度…更多页错误，CPU使用率更低

颠簸时，为了增加CPU使用率和降低系统颠簸，必须降低多道程序的程度

采用局部置换，一个进程颠簸不会使其他进程颠簸

Why does thrashing occur? Σ locality size > total memory size

using a local (or priority) replacement algorithm, Can limit the effect of thrashing.

为了防止颠簸，必须提供进程所需的足够多的帧。

Locality: a set of pages that are actively used together. Process migrates from one locality to another. Localities may overlap.

Working-Set Model 工作集合模型

基于局部性假设

参数Δ定义working-set window：a fixed number of page references

Working Set: the set of pages in the most recent Δ page references.

WSS i (working set size of Process P i ) : (varies in time) the number of pages in Working Set of process P i .

工作集合的精度与Δ的选择有关，太小不能包含整个局部，太大包含多个局部

总的帧需求量 D =Σ WSS i 总的需求大于帧的数量，会出现颠簸

OS跟踪每个进程的工作集合，如果D > m，暂停一个进程，该进程的页被写出，且其帧可分配给其他进程

通过固定定时中断(interval timer)和引用位(reference bit)可以近似模拟工作集合模型

Page-Fault Frequency Scheme(PPF) 页错误频率

为所期望的页错误率设置上限和下限。超过上限，为进程分配更多的帧；低于下限，从该进程中移走帧。

如果页错误率增加且没有可用帧，必须选择一个进程暂停，可将释放的帧分配给具有高页错误率的进程

最后修改于 2020-02-28