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

第五章 虚拟存储器

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磁道开始）

被访问的下一个磁道	移动距离（磁道数）
55	45（|100-55|）
58	3（|55-58|）
39	19（|58-38|）
18	21
90	72
160	70
150	10
38	112
184	146
平均寻道长度	55.3

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

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

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

被访问的下一个磁道	移动距离（磁道数）
90	10
58	32
55	3
39	16
38	1
18	20
150	132
160	10
184	24
平均寻道长度	27.5

（3）扫描算法（SCAN）

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

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

被访问的下一个磁道	移动距离（磁道数）
150	50
160	10
184	24
90	94
58	32
55	3
39	16
38	1
18	20
平均寻道长度	27.8

第七章 文件管理

1 文件的逻辑结构（P243）

类型—按是否有结构分类

（1）有结构文件

​ 记录长度

• 定长记录
• 变长记录

（2）无结构文件

类型—*按文件的组织方式分类

（1）顺序文件：

​ 指由一系列记录按某种顺序排列所形成的文件，其中的记录可以时定长记录或可变长记录。

（2）索引文件：

​ 指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。

（3）索引顺序文件：

​ 指为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表项，而是为一组记录的第一个记录建立一个索引表项。

2 文件目录（P249）

文件控制块（FCB）：

​ 为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块。

文件目录：

​ 文件控制块的有序集合称为文件目录。

文件目录作用：

​ 标识系统中的文件及其物理地址，供检索时使用。

目录管理要求：

（1）实现“按名存取”

（2）提高对目录的检索速度

（3）文件共享

（4）允许文件重名

3 树形目录结构（P253）

小规则：

主目录成为根目录，在每个文件目录中，只能有一个根目录，每个文件和每个目录都只能有一个父目录。

第八章 磁盘存储器的管理

1 设备（外存）的组织方式（P268）

（1）连续组织方式

又称为连续分配方式，要求为每一个文件分配一组相邻接的盘块。

优点：

①顺序访问容易

②顺序访问速度快

缺点：

①要求为一个文件分配连续的存储空间

②必须事先知道文件的长度

③不能灵活的删除和插入记录

④对于那些动态增长的文件，由于事先很难知道文件的最终大小，因而很难为其分配空间，而即使是事先知道文件的最终大小，在采取预分配存储空间的方法时，也会使大量的存储空间长期空闲。

（2）链接组织方式

优点：

①消除了磁盘的外部碎片，提高了外存的利用率

②对插入、删除和修改记录都非常容易

③能适应文件的动态增长，无需事先知道文件的大小。

缺点：

①只适合于顺序访问

②对随机访问是极其低效的

（3）FAT技术

利用文件分配表FAT来记录每个文件中所有盘块之间的链接。

发展：

卷：

在FAT中引入了“卷”的概念，支持将一个物理磁盘分成四个逻辑磁盘，每个逻辑磁盘就是一个“卷”。

（4）NTFS（New Technology File System）的文件组织方式

是专门为Windows NT开发的，适用于Windows2000/XP及后续的Windows OS

特性：

①使用了64位磁盘地址。

②更好的支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符。

③具有系统容错性。

④保证系统的数据一致性。

⑤提供了文件加密、文件压缩等功能。

磁盘组织：

NTFS是以簇为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件。

文件的组织：

在NTFS中，以卷为单位，将一个卷中所有的文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT中，该表时NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表占有一行，其中还包括MFT自己的这一行。

（5）*索引组织方式

① 单级索引

优化版的链接组织方式，优点是可以直接访问。

②多级索引

为索引增加索引，优点是大大加快了对大型文件的查找速度。

③增量式索引

更加全面的照顾到小、中、大及特大型作业，可采用多种组织方式来构成文件的物理结构。

2 文件存储空间的管理（P278）

（1）空闲表法和空闲链表法

空闲表法：

属于连续分配方式，与内存的动态分配方式相似，为每个文件分配一块连续的存储空间。

空闲链表法：

​ 将所有的空闲盘区拉成一条空闲链，根据构成链所用的基本元素不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链。

（2）*位示图法

​ 位示图法是利用二进制的一位来表示磁盘中的一个盘块的使用情况，当其值为“0”时，表示对应的盘块空闲，为“1”时表示已分配。磁盘上的所有盘块都有一个二进制位与之对应，所产生的集合就叫做位示图。

​ 借用下书上的图：

盘块的分配（三步）：

① 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位。

② 将找到的一个或一组二进制位转换成与之对应的盘块号。并按如下公式计算：

                         b = n(i-1) + j
                         
 i:其值为“0”的二进制位于位示图的第i行
 j:其值为“0”的二进制位于位示图的第j行
 n:每行的位数

③ 修改位示图，让map[i,j] = 1

盘块的回收（两步）：

①将回收盘块的盘块号转换成位示图中的行号和列号，公式为

                          i = (b-1)DIV n+1
                          j = (b-1)MOD n+1

②修改位示图，让map[i,j] = 0

（3）成组链接法

在UNIX系统中广泛使用，将空闲表法和空闲链表法相结合成的一种空闲盘块管理方法，克服了表太长的缺点。

空闲盘块的组织：

① 空闲盘块号栈，存储当前可以的一种空闲盘块的盘块号（<=100）以及栈中尚有的盘块数N

② 文件区中的所有空闲盘块被分成若干个组

③ 将每一个组含有的总盘块数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)-S.free(99)中

④ 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。

⑤ 最末一组只有99个可用盘块，某盘块号分别记入前一组的S.free(1)~S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。

全部完结！

原文链接：https://blog.csdn.net/Mr_YanMingXin/article/details/117912913

Gitee：https://gitee.com/yan_mingxin/study-notes