第五章 虚拟存储器
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”，作为空闲盘块链的结束标志。
全部完结！
