2023-12-13

虚拟内存二

一、读取策略

读取策略决定某页合适读入内存

1.请求分页

请求分页是只有当访问到某页中的一个单元时才将页读入内存。进程开始时会出现大量缺页中断，随着读入页的增加，根据局部性原理，要访问的数据多数是最近读取的页，缺页中断率会减少到一个稳定水平。

2.预先分页

预先分页是一次读取包含请求页的多个页。因为通常磁盘中一个进程的页是连续存储的，连续读取比单次读取效率高。但如果大多额外读取的页没被cpu使用，那就是低效的。

通常进程启动时使用预先分页，读取一定的页。发生缺页中断时使用请求分页。

二、置换策略

置换策略在决定置换的页集中，选择换出哪一页。所有策略的目标都是换出最近最不可能访问的页。

页框锁定：内存中某些页框被锁定，无法置换。如内核页框

1.最佳（OPT）策略

OPT策略选择置换下次访问距离当前时间最长的那些页，这种算法造成的缺页中断最少，但由于它需要预知未来，因此不可实现。但它可以作为衡量标准。

2.最近最少使用（LRU）策略

LRU策略置换内存中最长时间未被引用的页。这种方法实现起来比较困难，开销大。

一种是给每页添加一个最后一次访问的时间戳，每次访问的时候更新；另一个是维护访问页的栈。

3.先进先出（FIFO）策略

FIFO策略把分配给进程的页框视为一个循环缓冲区，并按循环的方式移动页。

它使用一个指针，每次对页框进行读入或置换的时候指针都往下移动，当移动到边界时循环到开头。每次读入或置换页面都对指针所指的页框进行操作。

它的隐含的逻辑是置换驻留在内存中时间最长的页。

这个方法性能最差。

4.时钟（Clock）策略

Clock策略给每个页框增加一个称为使用位的附件位。每次cpu读取其中内容时，附加位置为1。对于用于置换的页框集，它被视为一个循环缓冲区，并有一个指针与其关联。需要置换一页时，操作系统扫描缓冲区，查找一个使用位为0的页框并置换。若途中遇到使用位为1的页框，则将其使用位置为0。若所有页框使用位都为1，则算法把所有使用位都置为0，并停留在初始位置上，置换该页框中的页。

这个策略优于FIFO，差于LRU，若增加使用位的位数，可以提高效率。

三、页缓冲

置换一个修改过的页，比置换未修改过的页的代价更大。因为修改过的页要写回给磁盘。

为了提高效率，页缓冲算法不丢弃置换出的页。而是将它们分配到两个表中。

若未被修改，则分配到空闲页链表中，若被修改，则分配到修改页链表中。注意：内存中的页不会物理移动，移动的是页表项。

页缓冲技术在任何时候保留一小部分空闲页框。

空闲页链表里包含一系列可以读入的页框。需要从虚存读入一页时，使用位于空闲页链表头部的页框，置换原本在那个位置的页。

由于被置换的页仍然留在内存中，当进程再次访问时，效率很高。当修改队列达到一定长度时，集体写回修改页，它一次性写回多个页，减少了IO操作的次数，进而减少了磁盘访问的时间。

四、驻留集管理

驻留集管理考虑两个问题：驻留集大小和置换范围。

驻留集大小

驻留集大小即分配给进程的内存空间。分配的内存越少，驻留在内存中的进程越多，增加了操作系统至少找到一个就绪进程的可能性，减少了由于交换而消耗的处理器时间，但缺页率高。

固定分配策略:为一个进程分配固定数量的页框。一旦发生缺页中断，该进程的一页就被它所需要的页面置换

可变分配策略：运行分配给进程的页框不断变化。

置换范围

局部置换：仅在发生缺页中断的进程的驻留集中选择页来置换。

全局置换：把内存中所有未锁定的页都作为置换的候选页。

1.固定分配，局部范围置换

缺点：一个进程的总页数分配过少时，产生很高缺页率。分配过多时，内存中进程太少，cpu把大量时间浪费在交换上。

2.可变分配，全局范围

这种方式最容易实现。每个进程分配到一定页框，操作系统维护一个空闲页框列表。发生一次缺页中断时，一个空闲页框被添加进进程的驻留集，并读入该页。

这种方式的难点在于如何选择置换页。引入页缓冲技术可以解决这个问题。

3.可变分配，局部范围

这种方法的关键是不停地重新评估进程页框的分配情况，增加或减少分配该它的页框，以此来提高性能。

比较常见方案的是工作集策略。但是它的开销比较大，一般使用近似算法替代。

通过监视缺页率来评估进程的运行情况。若一个进程的缺页率低于某个最小阈值，则可以给进程分配一个较小的驻留集，但并不降低进程的性能（缺页率增加），使系统中其他进程受益；若进程的缺页率高于某个最高阈值，则在不降低整个系统性能的情况下，增大进程的驻留集。

遵循该策略的一种算法是缺页中断频率算法。

缺页中断频率算法

某页被访问时，使用位置为1。发生一次缺页中断时，操作系统记录该进程从上次缺页中断到现在的虚拟时间，这通过维护一个页访问计数器实现。定义阈值F，若从上一次缺页中断到这次缺页中断时间小于F，则把该页加到进程的驻留集中；否则淘汰所有使用位为0的页，缩减驻留集大小。同时，把其余页的使用位重新置为0。

五、清除策略

清除策略用于确定何时将已修改的一页写回辅存。

1.请求式清除

只有当一页被选择用于置换的时候才被写回辅存。

缺点：写回一页和读入一页是成对出现的，虽然这样可以减少写回操作。但发生缺页中断的进程在接触阻塞之前必须等待两次页传送（写回一次，读入一次），降低处理器利用率。

2.预约式请除

将已经修改的多页在需要使用它们所占据的页框之前成批写回辅存。

缺点:写回的页可能仍然在驻留集中，可能之后又被修改，会造成无意义的磁盘IO。

一种较好的方式是结合使用页缓冲技术。只清除用于置换的页，但去除了清除和置换操作的成对关系，即异步写回。被置换的页可以放在两个表（队列）中：修改表和未修改表。修改表中的页周期性地成批写出，并移到未修改表中。未修改表中的一页要么因为被访问而被回收到驻留集，要么在其页框分配给另一页时被淘汰。