操作系统（7）——存储系统（下）

一.页面置换算法

随机置换算法
先进先出算法（\(FIFO\)）
最近最久未使用算法（\(LRU\)）
时钟页面替换算法（\(Clock~Policy\)）
最佳置换算法（\(OPT,optimal\)）

1.先进先出算法（FIFO）

使用一个循环

选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些在\(FIFO\)算法下被反复调入和调出。

并且有\(Belady\)现象

（1）\(Belady\)现象
采用\(FIFO\)算法时，如果对一个进程未分配它所要求的全部页面，有事就会出现分配的页面数增多，缺页率反而提高的异常现象。

描述：一个进程\(P\)要访问\(M\)个页，\(OS\)分配\(N\)个内存页面给进程\(P\)；对一个访问序列\(S\)，发生缺页次数变为\(PE(S,N)\)。当\(N\)增大，\(PE(S,N)\)时而增大，时而减小。

原因：\(FIFO\)的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。

2.最近最久未使用算法（\(LRU\)）

模拟队列，队列长度就是给的内存
该算法淘汰的页面是在最近一段时间里较久未被访问的那一页。

根据程序的局部性来考虑，就是说有一些页面被用过了，之后可能还要被用，较长时间里未使用页面，一般来说不会马上使用。

3.时钟页面替换算法（\(Clock~Policy\)）

一个页面不会连续出现两次
一个页面首次装入主存，其“引用位”为0。在主存中任意一个页面被访问时，“引用位”为1.
淘汰页面时，从当前页面开始扫描循环队列，把“引用位”为1变成0，并且跳过；把“引用位”为0的换掉。
他是\(LRU\)和\(FIFO\)的折衷。

4.最佳算法（\(OPT,optimal\)）

选择“未来不再使用的”或“离当前最远位置上出现的”置换。

影响缺页次数的因素：
（1）分配给进程的物理页面数
（2）页面本身的大小
（3）页面淘汰算法
（4）程序的编制方法

段式存储管理

把程序划分为若干个段，每一段有一个段名和一个段号，段号从0开始，每一段也从0开始编址，段内地址是连续的
逻辑地址（二维地址）

内存划分

空间被动态划分为若干个长度不同的区域，称为物理段，每一个由起始地址和长度确定。

内存分配

以段为单位分配内存，每一段在内存中占据连续空间（随机的，需要多少分配多少），各段之间可以不连续存放。

段式管理

（1）段表：每进程一个
（2）空闲表：系统一个

内存分配

（1）有足够空闲区（同动态分区）
最先，最佳，最坏
（2）没有空闲（请求页式）
\(FIFO\),\(LRU\)
一段不行就多次

页式和段式的比较

（1）分页是出于系统管理的需要，分段是出于用户应用的需要。
（2）分页是一维的，分段是二维的。
（3）通常段比页大，所以段表比页表短，可以缩短查找时间，提高访问速度