时钟置换算法口诀

❶ 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

❷ 求2011考研计算机专业课大纲！

2010年计算机考研专业课大纲（三）

操作系统
【考查目标】
1. 了解操作系统在计算机系统中的作用、地位、发展和特点。
2. 理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。
3. 能够运用所学的操作系统原理、方法与技术分析问题和解决问题。

一、 操作系统概述
(一) 操作系统的概念、特征、功能和提供的服务
(二) 操作系统的发展与分类
(三) 操作系统的运行环境

二、 进程管理
(一) 进程与线程
1. 进程概念
2. 进程的状态与转换
3. 进程控制
4. 进程组织
5. 进程通信
共享存储系统;消息传递系统;管道通信。
6.线程概念与多线程模型
(二)处理机调度
1.调度的基本概念
2.调度时机、切换与过程
3.调度的基本准则
4.调度方式
5.典型调度算法
先来先服务调度算法;短作业(短任务、短进程、短线程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法。
(三)进程同步
1. 进程同步的基本概念
2. 实现临界区互斥的基本方法
软件实现方法;硬件实现方法
3. 信号量
4. 管程
5. 经典同步问题
生产者-消费者问题;读者-写者问题;哲学家进餐问题。
(四) 死锁
1. 死锁的概念
2. 死锁处理策略
3. 死锁预防
4. 死锁避免
系统安全状态：银行家算法。
5. 死锁检测和解除

三、 内存管理
(一) 内存管理基础
1. 内存管理概念
程序装入与链接;逻辑地址与物理地址空间;内存保护。
2. 交换与覆盖
3. 连续分配管理方式
单一连续分配;分区分配。
4. 非连续分配管理方式
分页管理方式;分段管理方式;段页式管理方式。
(二) 虚拟内存管理
1. 虚拟内存基本概念
2. 请求分页管理方式
3. 页面置换算法
最佳置换算法(OPT);先进先出置换算法(FIFO);最近最少使用置换算法(LRU);时钟置换算法(CLOCK)。
4. 页面分配策略
5. 抖动
抖动现象;工作集。
6. 请求分段管理方式
7. 请求段页式管理方式

四、 文件管理
(一) 文件系统基础
1. 文件概念
2. 文件结构
顺序文件;索引文件;索引顺序文件。
3. 目录结构
文件控制块和索引节点;单级目录结构和两级目录结构;树形目录结构;图形目录结构。
4. 文件共享
共享动机;共享方式;共享语义。
5. 文件保护
访问类型;访问控制。
(二) 文件系统实现
1. 文件系统层次结构
2. 目录实现
3. 文件实现
(三) 磁盘组织与管理
1. 磁盘的结构
2. 磁盘调度算法
3. 磁盘的管理

五、 输入输出(I/O)管理
(一) I/O管理概述
1. I/O设备
2. I/O管理目标
3. I/O管理功能
4. I/O应用接口
5. I/O控制方式
(二) I/O核心子系统
1. I/O调度概念
2. 高速缓存与缓冲区
3. 设备分配与回收
4. 假脱机技术(SPOOLing)
5. 出错处理

计算机网络

【考查目标】
1. 掌握计算机网络的基本概念、基本原理和基本方法。
2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理
3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用

一、 计算机网络体系结构
(一) 计算机网络概述
1. 计算机网络的概念、组成与功能
2. 计算机网络的分类
3. 计算机网络与互联网的发展历史
4. 计算机网络的标准化工作及相关组织
(二) 计算机网络体系结构与参考模型
1. 计算机网络分层结构
2. 计算机网络协议、接口、服务等概念
3. ISO/OSI参考模型和TCP/IP模型

二、 物理层
(一) 通信基础
1. 信道、信号、宽带、码元、波特、速率等基本概念
2. 奈奎斯特定理与香农定理
3. 信源与信宿
4. 编码与调制
5. 电路交换、报文交换与分组交换
6. 数据报与虚电路
(二) 传输介质
1. 双绞线、同轴电缆、光纤与无线传输介质
2. 物理层接口的特性
(三) 物理层设备
1. 中继器
2. 集线器

三、 数据链路层
(一) 数据链路层的功能
(二) 组帧
(三) 差错控制
1. 检错编码
2. 纠错编码
(四) 流量控制与可靠传输机制
1. 流量控制、可靠传输与滑轮窗口机制
2. 单帧滑动窗口与停止-等待协议
3. 多帧滑动窗口与后退N帧协议(GBN)
4. 多帧滑动窗口与选择重传协议(SR)
(五) 介质访问控制
1. 信道划分介质访问控制
频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。
2. 随即访问介质访问控制
ALOHA协议;CSMA协议;CSMA/CD协议;CSMA/CA协议。
3. 轮询访问介质访问控制：令牌传递协议
(六) 局域网
1. 局域网的基本概念与体系结构
2. 以太网与IEEE 802.3
3. IEEE 802.11
4. 令牌环网的基本原理
(七) 广域网
1. 广域网的基本概念
2. PPP协议
3. HDLC协议
4. ATM网络基本原理
(八) 数据链路层设备
1. 网桥
网桥的概念;透明网桥与生成树算饭;源选径网桥与源选径算法。
2. 局域网交换机及其工作原理。

四、 网络层
(一) 网络层的功能
1. 异构网络互联
2. 路由与转发
3. 拥塞控制
(二) 路由算法
1. 静态路由与动态路由
2. 距离-向量路由算法
3. 链路状态路由算法
4. 层次路由
(三) IPv4
1. IPv4分组
2. IPv4地址与NAT
3. 子网划分与子网掩码、CIDR
4. ARP协议、DHCP协议与ICMP协议
(四) IPv6
1. IPv6的主要特点
2. IPv6地址
(五) 路由协议
1. 自治系统
2. 域内路由与域间路由
3. RIP路由协议
4. OSPF路由协议
5. BGP路由协议
(六) IP组播
1. 组播的概念
2. IP组播地址
3. 组播路由算法
(七) 移动IP
1. 移动IP的概念
2. 移动IP的通信过程
(八) 网络层设备
1. 路由器的组成和功能
2. 路由表与路由转发

五、 传输层
(一) 传输层提供的服务
1. 传输层的功能
2. 传输层寻址与端口
3. 无连接服务与面向连接服务
(二) UDP协议
1. UDP数据报
2. UDP校验
(三) TCP协议
1. TCP段
2. TCP连接管理
3. TCP可靠传输
4. TCP流量控制与拥塞控制

六、 应用层
(一) 网络应用模型
1. 客户/服务器模型
2. P2P模型
(二) DNS系统
1. 层次域名空间
2. 域名服务器
3. 域名解析过程
(三) FTP
1. FTP协议的工作原理
2. 控制连接与数据连接
(四) 电子邮件
1. 电子邮件系统的组成结构
2. 电子邮件格式与MIME
3. SMTP协议与POP3协议
(五) WWW
1. WWW的概念与组成结构
2. HTTP协议

❸ 简单时钟置换算法（NLU）当不发生页面置换也就是命中时，循环队列中的扫描指针跟着命中的页移动不

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

❹ 页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。