《计算机操作系统》重点知识笔记整理（二）（上）

第五章 虚拟存储器

1 特征和局部性原理（P164）

（1）特征：

一次性、驻留性

（2）局部性原理：

原理概述：

程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应的，它所访问的存储空间也局限于某个区域。

论点：

• 程序执行时，除了少部分的转移过程调用指令之外，在大多数情况下是顺序执行的。
  
• 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域。但经研究看出，过程调用的深度在大多数情况下都不超过5。
  
• 程序中存在许多循环结构，这些结构虽然只由少数指令构成，但是他们将被多次执行。
  
• 程序中还包括许多对数据结构的处理，比如对数组进行操作，但是这些操作都被局限在很小的范围内。
  局限性表现的两个方面：
  （1）时间局限性 （2）空间局限性
  

2 请求分页存储管理方式（P168）

概念：

建立在基本分页的基础之上，为了能支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。

（1）页表和相关概念

（2）地址变换过程

请求分页和基本分页有什么不同？

请求分页不要求资源一次性全部装入内容，而普通分页则不需要。

3 *页面的置换算法（P174）

（1）最佳置换算法(OPT)和先进先出置换算法(FIFO)

①OPT

核心思想：选择的被淘汰页面将是以后永不使用的，也可能是在最长（未来）时间内不再被访问的页面。 [无法实现]

实例：系统分配给一个作业的物理块为3，并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5，画出页面的变化过程

②FIFO

核心思想：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面给予淘汰。

实例：系统分配给一个作业的物理块为3，并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5，画出页面的变化过程

（2）最近最久未使用*(LRU重点)和最少使用置换算法(LFU)

① *LRU

核心思想：根据页面调入内存后的使用情况做决定，选择最近最久未使用的页面给予淘汰。利用最近的过去，给每个字段赋予上次被访问以来所经历的时间t，当有页面需要淘汰时选择t值最大的给予淘汰。 [性能较好]

实例：系统分配给一个作业的物理块为3，并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5，画出页面的变化过程。

②LFU

核心思想：选择最近时期最少使用的页面给予淘汰，为每个页面设置一个移位寄存器（访问计数器），用来记录页面的被访问频率，认为"如果数据过去访问频率很高,那么将来被访问的频率也很高"

实例：系统分配给一个作业的物理块为3，并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5，画出页面的变化过程

（3）Clock置换算法

核心思想：[LRU和FIFO的折中] ，为每一页设置一个访问位，再讲内存中所有的页面都通过链接指针链接成一个循环队列。当页面被访问时，其访问位被置为1，置换算法在选择被淘汰的页面时只检查该页的访问位。如果是0，就选择该页换出，若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一页面。

实例：系统分配给一个作业的物理块为3，并且作业的页面走向为1、2、4、1、5、3、2、5（比较复杂在这里就简单举例下）画出页面的变化过程

4 请求分段存储管理方式（P185）

（1）硬件支持—段表

（2）硬件支持—缺页中断机构

请求分段的系统中采用的是请求调段的策略，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后，由缺段中断处理程序将所需的段调入内存。

在这里就借用下教科书上的图吧：

（3）硬件支持—地址变换机构

因为被访问的段并非全在内存，所以在地址变换时，若发现所要的访问的段不在内存，必须先将所缺页的段调入内存，并修改段表，然后才能再利用段表进行地址变换。

在这里也借用下教科书的图（教科书真的太棒了！）

第六章 输入输出系统

申请设备时使用逻辑地址

1 设备分配（P215）

设备分配中的数据结构（4个）：

（1）设备控制表DTC：用于记录设备情况。

（2）控制器控制表COCT：用于记录控制器情况。

（3）通道控制表CHCT

（4）系统设备表SDT：记录系统中全部设备的情况。

2 假脱机（Spooling）系统（P220）

假脱机技术用途：将一台物理I/O设备虚拟为多台逻辑I/O设备，可以允许多个用户共享一台物理I/O设备。

目的：为了缓和CPU的高速性与I/O设备的低速性间的矛盾。

概念：SPOOLing是Simultaneous Peripheral Operation On-Line （即外部设备联机并行操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为"假脱机技术"。

特点： SPOOLing技术是在通道技术和多道程序设计基础上产生的，它由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作。

组成：

• 输入井和输出井
• 输入缓冲区和输出缓冲区
• 输入进程和输出进程
• 井管理程序
  
  网络异常，图片无法展示

  |
• 
  原理：
  
  网络异常，图片无法展示

  |
• 
  

3 *缓冲管理（P223）

引入缓冲区的原因

（1）缓和CPU与I/O设备间速度的不匹配问题

（2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制

（3）解决数据粒度不匹配的问题

（4）提高CPU和I/O设备间的并行性

缓冲区种类

（1）单缓冲

每当用户进程发出一个I/O请求，操作系统便在主存之中为之分配一个缓冲区。

（2）双缓冲（也称为缓冲对换）

在设备输入时现将数据送入第一缓冲区，装满后便转向第二缓冲区。

（3）环形缓冲

（4）缓存池

4 磁盘调度算法（P233）

（1）先来先服务（FCFS）

根据进程请求访问磁盘的先后次序进行调度。

例如：进程请求顺序为55、58、39、18、90、160、150、38、184（从100磁道开始）

（2）最短寻道时间优先（SSTF）

要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但不能保证平均寻道时间变短。

例如：进程请求顺序为55、58、39、18、90、160、150、38、184（从100磁道开始）

（3）扫描算法（SCAN）

又称为电梯调度算法，该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。

例如：进程请求顺序为55、58、39、18、90、160、150、38、184（从100磁道开始）