操作系统考点复习

💡整理不易，先赞后看，养成习惯💡

申明

💡这里都是根据老师说的重点作者自己整理的，不一定全，详细可以看后面的笔记和课件。 后续部分大题参照物联网2001@我是小鸟buyingbuying同学给出作业整理，特此感谢🎉。 复习建议：先过一遍后面的笔记 -> 本文档 -> 课件PPT+书本课后总结

选择和判断(20 1分 + 10 1分)

操作系统引论

进程相关

处理机调度与死锁

存储器管理

虚拟存储器

输入输出系统

后面两张内容不多就不整理了，可以过一遍笔记

名词解释(7 * 2分)

1. 并发：两个或多个事件在同一时间间隔发生
2. 并行：两个或多个事件在同一时刻发生
3. 作业：一个完整任务,由若干进程组成
4. 进程：程序在执行过程中的一个实例，是计算机资源分配和调度的基本单位
5. 线程：进程内的一个独立执行流，与同一进程内的其他线程共享地址空间和系统资源
6. 时分复用系统：一种操作系统架构,它可以让多个用户同时使用计算机系统。每个用户都被分配若干时间片,在自己的时间片内执行自己的程序
7. 临界资源：在⼀段时间内只允许⼀个进程访问的资源，即仅当⼀个进程访问完并释放该资后，才允许另⼀个进程访问的资源，称为临界资源或独占资源
8. 临界区：程序中访问临界资源的代码段或者数据区域
9. 进程同步：多个进程之间协调和控制它们的执⾏顺序，以避免出现竞争条件和死锁等问题
10. 进程调度：根据某种规则来决定处理进程任务的顺序
11. 前驱图：一个有向无循环图,记为 DAG(Directed Acyclic Graph) ，用于描述进程之间执行的前后顺序
12. 调度算法：用于决定处理器如何选择下一个要运行的进程或线程的算法。
13. PCB：进程控制块，用于管理和控制进程的数据机构
14. TCB：线程控制块，用于管理和控制线程的数据机构
15. FCB：文件控制块，用于管理和控制文件的数据机构
16. ICB：索引控制块用于管理文件系统中的索引结构
17. MCB：内存控制块，用于管理内存分配和释放的数据结构
18. DCB：设备控制块，用于管理计算机系统中的设备的数据结构
19. 用户态：一种特权级别，具有相对较低的特权，只能执行规定的指令，访问指定的寄存器和存储区
20. 内核态：一种特权级别，具有最高的指令执行权，能执行一切指令，访问所有的寄存器和存储区
21. 抢占式：一种调度策略，它允许一个正在运行的任务（进程或线程）被强制中断并暂停，以便其他任务能够获得执行机会
22. 可重用资源：可供用户重复使用的资源，一个可重用性资源只能分配一个进程使用，不允许多个进程共享
23. 消耗性资源：由进程动态创建和消耗的资源
24. 死锁：指两个或多个进程因等待对方释放所占有的资源而陷入无限阻塞的状态
25. 优先级倒置：一个具有较低优先级的任务阻塞了一个具有较高优先级的任务的执行
26. 页面：虚拟内存管理中的基本单位，也是物理内存与虚拟内存之间的映射单元
27. 对换：将一个正在内存中执行的进程或程序从主存交换到辅助存储设备
28. 快表：一种高速缓存，通常位于CPU硬件中，用于加速虚拟地址转换为物理地址的过程
29. 动态重定位：一种内存管理技术，用于在程序执行期间将程序的逻辑地址（虚拟地址）映射到真实的物理地址上
30. 内存管理：操作系统管理物理内存和虚拟内存的分配、映射和回收的方式和策略
31. 抖动：在虚拟内存系统中，由于频繁的页面置换操作而导致性能急剧下降的现象
32. 虚拟存储器：将物理内存和辅助存储设备（如硬盘）结合起来，为每个进程提供了一个看似连续且较大的地址空间
33. 工作集：进程当前正在使用的页面集合或者是进程在一段时间内访问过的页面的集合
34. 设备无关性：程序或者系统可以在不考虑特定硬件设备差异的情况下进行开发、运行和移植的能力
35. DMA：一种计算机系统中的数据传输技术，它允许外部设备直接访问主存（或系统总线）上的数据，而不需要经过 CPU 的干预
36. 设备驱动程序：用于控制和管理硬件设备的软件模块，使其能够与操作系统和应用程序进行交互。
37. 页面置换算法：操作系统在虚拟内存管理中使用的算法，用于决定页面调出和替换的策略。
38. 数据项：计算机中表示数据的最基本单位
39. 记录：一组相关数据项组成的数据结构
40. 文件：由一组相关记录组成，用于组织和存储数据
41. 保护域：用于实现安全访问控制的一种机制
42. 多道程序设计：允许多个程序同时驻留在主存中并能交替运行的技术
43. 中断：是指计算机在正常执行过程中，由硬件或软件发出的一个信号，用于打断当前程序的执行，并转而处理相关的事件

简答题(4 * 5分)

1. 操作系统的定义是什么？

答：操作系统是属于系统程序的一种。操作系统的地位可以理解为系统硬件之上的第一层软件，为其他软件提供单向支撑作用。用来管理和控制计算机系统中的全部软、硬件资源，可以合理地组织计算机的⼯作流程为⽤户应⽤程序的运⾏提供⼀个友好的界⾯和良好的⼯作环境。

1. 操作系统的基本功能是什么？

答：从资源管理的⻆度看，操作系统的功能是协调、管理计算机的软硬件资源，提⾼其利⽤率；从⽤户⻆度看，操作系统的功能是提供使⽤计算机的环 境和服务，⽅便⽤户使⽤。
如果问的是主要功能（4+1），答案如下：

• 管理处理机
• 管理存储器
• 管理文件
• 管理设备
• 作为用户和操作系统的接口

1. 进程和程序有什么不同?为什么需要进程?

答：进程与程序的区别：

• 进程是动态的，程序是静态的
• 程序是有序代码的集合，进程是程序的执⾏
• 进程是暂时的，程序是永久的
• 进程是⼀个状态变化的过程，程序可⻓久保存
• 进程与程序的组成不同。进程的组成包括程序、数据和系统数据及资源

通常的程序不能参与并发执⾏，为了让程序能并发执⾏，引入进程的概念对并发执⾏的程序加以描述和控制。

1. 进程同步应遵循的基本准则是什么？

答：

• 空闲让进：当临界资源空闲时，允许一个进程进入临界区。
• 忙则等待：临界资源正被访问时，其它进程必须等待，以保证对临界资源的互斥访问。
• 有限等待：应保证进程能在有限时间内能进入自己的临界区，以免陷入“死等”
• 让权等待：如果进程不能进入自己的临界区、应立即释放处理机，以免陷入“忙等”

1. 在一个单CPU系统中，现在两道进程同时执行，一道以计算为主，另一道以输入输出为主，怎样赋予进程占有处理机的优先级，为什么？

答：由于优先级高的进程能够优先占用处理机，以计算为主的作业需要占用大部分的处理时间，而以输入输出为主的作业，占用处理机的时间相对较少，因此在赋予优先级的时候，以输入输出为主的作业优先级要高于计算为主的作业。

1. 产生死锁的必要条件

• 互斥条件：竞争的资源必须被互斥的使用
• 请求和保持条件：进程需要不断请求需要的资源并且保持已有的资源不释放
• 不剥夺条件：进程已获得的资源，只能在使用完时自行释放资源
• 循环等待条件：存在一个至少包括两个进程的循环等待链，链中的每个进程都正在等待下一个进程所占有的资源

1. 处理死锁的办法

• 预防死锁：设置限制条件，破坏产生死锁的四个必要条件中的一个或几个条件 。
• 避免死锁：在每次的资源动态分配过程中，对系统能够满足的资源申请进行安全性检查 ，根据结果决定是否进行此次分配。
• 检测死锁：允许系统发生死锁，但设置检测机构，及时检测出死锁的发生。
• 解除死锁：外力推动解除死锁。具体方法有：撤消或挂起死锁进程、剥夺资源等。

1. 具有快表的地址变换过程

• 在CPU给出有效地址后，由地址变换机构自动地将页号送入快表中。
• 若快表中有此页号，则直接从快表中读出该页对应的物理块号，送到物理地址寄存器。否则，再访问内存中的页表，从页表项中读出物理块号送到地址寄存器，同时，将此页表项放入快表中。
• 若快表已满，OS找到一个被认为不再需要的表项，将它换出。

1. 简述常见的四种连续内存管理⽅案及其优缺点

• 单一连续分配：这种分配方式把内存分为两个区域：系统区，用户区,地址重定位时，只要将指令或数据的逻辑地址加上用户区基地址，就可以形成物理地址。
  • 优点：容易管理、不设置存储保护
  • 缺点：程序全部装入，要求内存空间少的程序
• 固定分区分配：固定式分区是在作业装入之前，将内存空间划分为若干个固定大小的区域，每个分区中可以装入一道作业。
  • 分区大小相同的时候，操作简单但是缺乏灵活性
  • 分区大小不同的时候，内存利用率高但是难实现
• 动态分区分配：动态分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。
  • 分区的大小和个数都是可变的
  • 有较大的灵活性，提高了内存的利用率
• 动态重定位分区分配：动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于，在动态重定位算法中增加了紧凑的功能。
  • 优点：更加灵活
  • 缺点：实现困难

1. 简述I/O系统的六大基本功能

• 隐藏物理设备的细节
• 与设备的无关性
• 提高处理机和I/O的利用率
• 对I/O设备进行控制
• 确保对设备的正确共享
• 错误处理

1. 简述四种常见的I/O控制方式

• 轮询的可编程I/O：利用I/O测试指令测试设备的闲忙
• 中断的可编程的I/O：当设备完成I/O操作的时候，就发送中断请求通知CPU，再进行相应的处理
• 直接存储器访问：由DMA控制器送出内存地址和发出内存读、设备写等控制信息，设备和内存直接交换数据，无需CPU干预
• I/O通道：通道一个独立于CPU的、专门负责数据的输入输出传输工作的处理器，用于对外部设备实施统一的管理，代替CPU对I/O操作进行控制

1. 什么是通道，引入通道的原因是什么？

通道：用于在计算机系统和主存储器之间进行数据传输的处理器
原因：解脱CPU对于I/O的组织和管理，数据传输工作可以交给通道完成，减轻CPU的负担

1. 什么是设备无关性？为什么需要设备无关性？

设备独立性：计算机中软件和硬件之间的关系是抽象的，与具体的硬件设备无关，软件可以通过接口访问不同类型的硬件设备而无需考虑硬件的具体实现。
原因：提高计算机系统的可移植性和可扩展性

1. 简述用户发起对逻辑I/O设备的请求操作之后，独占设备的分配过程

• 根据进程请求的物理设备名查找系统设备表（SDT）
• 根据SDT中唯一的设备标识符找到对应的设备控制表（DCT），设备不忙碌的情况下，把该设备分配给进程
• 根据DCT找到唯一的控制器控制表（COCT），控制器不忙碌的情况下，把该控制器分配给进程
• 根据COCT找到通道控制表（CHCT），通道不忙碌的情况下，把该通道分配给进程

1. 以假脱机打印机为例，简述SPOOLING系统的工作过程。

当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事:

1. 在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的)，并将要打印的数据送入其中;
2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中(其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。

当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务

综合应用题(6 * 6分)

调度算法

先来先服务调度算法（FCFS）

当系统有多个作业请求 CPU 处理时，FCFS 调度算法会按照它们被提交的时间顺序依次得到 CPU 时间片，并执行对应的进程。
如果当前进程执行完了，但仍有其他作业等待 CPU 时间片，则根据他们的进入时间，按照 FCFS 的方式进行排序，然后依次分配 CPU 时间片给这些进程。
举个例子：

相关名词解释：

• 服务时间：指进程执行的时间
• 周转时间：完成时间 - 到达时间
• 带权周转时间：（完成时间 - 到达时间）/ 服务时间

这上面这个表格中，四个进程就是按照到达时间以此进入CPU执行。

考试大题大概率会考平均周转时间和平均带权周转时间，只需要列表求解对应均值即可。

短作业优先调度算法（SJF）

短作业优先调度算法（Shortest Job First，简称SJF）是一种根据进程预计执行时间来进行调度的算法，即预测 cpu 执行时间最短的进程先执行。
还是上面那个例子：

按照短作业优先调度进程执行的顺序如下：

1. 0时刻只有A进程在就绪队列中，所以先执行A进程，此时时间来到1，进程B进入就绪队列
2. 1时刻就绪队列只有B，所以再执行B进程，此时时间来到101，进程C和进程D进入就绪队列
3. 101时刻就绪队列有两个，其中D的服务时间最短，所以先执行D，此时时间来到111，无后续进程
4. 111时刻只有C进程，最后执行C进程

综上，在这个例子中采用短作业优先的顺序为：A->B->D->C。

优先级调度算法（PSA）

优先级调度算法是从后备队列中选择若干个优先级最高的作业，调入内存运行。
从就绪队列中选择一个优先级最高的进程，让其获得处理器并执行。
看下面这个简化的例子：

在0时刻四个进程都存在，也就是说四个进程都在就绪队列当中，此时按照优先级大小从小到大依次执行进程，所以进程的执行顺序为：A->C->B->D。

当然如果进程在某一时刻还没到达则不参与优先级次序的比较。

高响应比调度算法（HRRN）

高响应比优先调度算法综合考虑等待时间和服务时间为调度指标。其衡量的指标为响应比，计算方式如下：

Rp=（等待时间＋服务时间）/ 服务时间 = 1+ tw/ts

1. tw（等待时间）相同的进程，短作业RP大
2. ts（服务时间）相同的进程间相当于FCFS

没调度进程都优先选择响应比较高的作业（进程）运行。

这种调度算法可用于作业调度，也可用于进程调度。

举个例子：

1. 首先肯定还是执行A，此时时间来到4。
2. 时间为1的时候，BCD三个进程都已经到了所以：twB = twC = twD = 3
3. 三个进程的响应比为：
   1. RpB = 1 + 3/2 = 2.5
   2. RpC = 1 + 3/3 = 2
   3. RpD = 1 + 3/4 = 1.75
4. 此时响应比最高是B，所以先执行B
5. 后续类推….

银行家算法

主要考察安全状态转换：

安全状态

:::info 安全状态是指系统能按某种顺序如 (P1、P2… 、Pn) 来为每个进程 Pi 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列 ( P1、P2、…、Pn ) 为安全序列。 ::: 若某一时刻系统中无法找到这样一个安全序列，则称此时的系统状态为不安全状态。

不是说所有的不安全状态都会造成死锁，但是安全状态一定不会造成死锁。

安全状态的例子

假定系统中有三个进程P1，P2和P3，共有12台磁带机。进程P1共需要10台，P2和P3各需要4台和9台。假设在T0时刻，进程的资源分配情况如下：

从上面的表中我们可以知道三个进程分别需要的资源数量是5、2、7，那么此时可以先给P2分配资源，P2获取资源完成任务之后，就可以回收其所有的资源，此时：

以此类推，可以找到一个安全序列：（P2,P1,P3）。

注意：安全序列不是唯一的，比如这里其实（P2,P3,P1）也是一个安全序列。

由安全状态向不安全状态的转换

在上面的例子中如果改一点数据：

首先资源只能分配给P2，此时即使P2完成任务之后回收了所有资源，资源也只有4个，不满足P1和P3的其中任意一个的需求，因此此时就是不安全状态，有可能会造成死锁。 :::info 一个系统开始处于安全状态，当有进程请求一个可用资源时，系统需对该进程的请求进行检测，若将资源分配给进程后系统仍然处于安全状态，才将该资源分配给进程。 :::

死锁的检测

资源分配图

系统死锁，可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个二元组G=（N, E），它具有下述的形式定义和限制：

• N：结点集，分为P，R两部分，
• P={P1,P2,…,Pn}：进程结点
• R={R1,R2,…,Rm}：资源结点

如图所示：

• 其中r中的圆圈的个数表示资源的个数（比如这里的r1资源总共有3个）
• 进程需要的总的资源量是其所有入度和出度（比如P1实际需要2个r1和一个r2）
• P->r：表示P需要申请一个资源R，但是这个资源还没有被分配出去

• r->R：表示r分配给了P一个资源，并且这个资源已经分配出去了

  死锁定理

  首先我们需要化简资源图，以此图为例：
  
  第一步：找一个既不阻塞又非孤立点进程结点
  不孤立很好理解，就是这个结点必须和其他结点有关联即可。不阻塞需要进一部分析整个资源图，假设我们找到的是P，分析：

• P是否可以获得请求的资源

• P是否可以获得被分配的资源

那么首先一律把图中的资源先分配，再请求。如果先分配的话，那么：

• P1获得了两个r1
• P2获得了一个r1，一个r2
• 此时r1剩下0个
• 此时r2剩下1个

P1和P2明显都可以获得被分配的资源，但是：

• P1请求一个r2资源，此时r2资源剩余1个，所以请求成功
• P2请求一个r1资源，此时r2资源剩余0个，所以请求失败

那么综上可以知道：

• P1可以顺利运行
• **P2**被阻塞

所以第一步要找的结点是P1。

第二步：再把被请求的资源分配给这个进程吗，让他执行完毕。此时返回用完的资源，并且消除相应的边。
第三步：重复上述两边，直到所有的结点都孤立或者所有的结点都阻塞。

这就是完整的化简流程。

页面存储管理

虚地址转为内存地址

有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。

由题意可知，页大小为2KB，所以页内偏移的位数就应该是11位，地址0AFEH，1ADDH都是十六进制，又四位，所以化为二进制为16位。
所以：

• 虚地址：0AFEH
• 转为二进制：0000 1010 1111 1110
• P＝1 W＝010 1111 1110
• 对应块号是9
• PA＝0100 1010 1111 1110
• 物理地址：4AFEH

  其中P表示页号，PA表示物理地址的二进制，W表示偏移量 对应实际物理地址：偏移量不变，页号根据页表映射修改。

求解内存空间

设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048个字节，内存总共有8个存储块，是问逻辑地址至少多少位？内存空间多大？

答：逻辑地址需要分别表示页号以及页内编号，对应2**4** = 16，2**11** = 2048，所以总共需要逻辑地址11 + 4 = 15位。
一个存储块对应一页，所以需要大小为：8 * 2048B = 16KB大小

作业

已知某分页系统，主存容量为64K，页面大小为1 K，对一个4页大的作业，各页被分配到主存的2，4，6，7块中。 （1）将十进制的逻辑地址 2000和4500转换成对应的物理地址。 （2）将十六进制的逻辑地址 00ACH和02BEH转换成对应的物理地址。 （3）如果访问内存需要1μs，有效访问时间为多少? （4）如果加一快表，且假定在快表中找到页表的几率高达90%，则有效访问时间又是多少（假定查快表需花的时间为0）？

（1）

页面大小为1K = 1024，那么2000/1024 = 1 ... 976，也就是第**1 + 1 = 2**页（页号从0开始）中的第976号位置，逻辑地址第**2**页对应主存的块为**4**。所以物理地址为：4 * 1024 + 976 = 5072。
同理4500/1024 = 4 ... 404，由于4+1 > 4，所以地址超出范围，发出越界中断。
（2）
首先转为二进制：(00AC H)16 = (0000 0000 1010 1100)2
一页大小为 (1024)10 = (0000 0100 0000 0000)2
对比可以知道逻辑页号为**0**，对应物理块号为**2**即：2 * 1024 = (0000 1000 0000 0000)2，加上偏移量得到物理地址：
(0000 1000 0000 0000)2+ (0000 0000 1010 1100)2 = (0000 1000 1010 1100)2= **(08AC)****16**
同理(02BE H)16 = (0000 0010 1011 1110)2 对应物理块号也为2，物理地址为**(0ABE H)****16**
（3）
由于这个作业总共4页，没有说内存和其他时间损耗，所以所有访问内存的时间都是有效访问时间，即：
有效访存时间：4 * 1μs = 4μs
（4）
这里分两种情况：缺页和不缺页

• 不缺页：

说明此时页面可以直接从内存中获得，所以直接花费1μs从内存取页即可。由于查询页表的时间近似为0，所以整体的时间就是：
90%*(0 + 1μs)

• 缺页：

此时的页面不在内存中，注意，此时先把外存中的页面调入到内存中的快表，而不是直接调用外存中的页面，所以此时还需要从内存中再调用已经被置换过的物理块，那么整体时间为：
（1 - 90%)*(0+1μs + 1μs)

查表有两次，第一次查表没有查到，第二次是在页面置换结束之后再次查表，此时从内存调用。

总的时间就是缺页时间 + 不缺页时间 = 1.1 μs。

某计算机主存分页内存管理方式，逻辑地址是32位，页内偏移量占12位。页表项大小为4字节，请问，则页的大小是多少字节？页表最大占用多少字节？内存最大容量是多少？

答：
逻辑地址32位，页内偏移量12位，所以一共有20位表示页面号，则一共最多支持220 = 1M个页面。
页面大小为212 = 4KB
一个页表项大小是4B总共有1M个页面，所以页表项最大占用4 * 1M = 4MB
页表中的页表项个数为2^20个，每个页面大小为4096字节，所以内存最大容量为：
内存最大容量 = 2^20 4096 字节 = 4096 1024 * 1024 字节 = 4GB

页面置换算法

最佳置换算法（Opt）

选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。

举个例子：

假定系统为进程分配了三个物理块， 页面号引用序列为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1. 采用最佳置换算法，其置换过程如下：

首先我们记住这个引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
内存分配了三个物理块，所以前三个引用可以依次进入：

此时序列为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
下面就需要引入页面2，此时在物理块中的三个页面分别是**7、0、1**，所以观察在后续序列中不存在的或者最晚出现的页面：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
这里用高亮标出最晚出现的页面，明显是7，所以这个时候把7置换出去，此时的物理块分配情况如下：

这个时候引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
需要引入0，此时0又在物理块中，所以无需置换，继续。
此时引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
引入3，同理查找并置换，这里就是需要置换1：

后续同理，不再赘述。
它是一种理想化的算法，性能最好，但难以实现。

因为需要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。

先进先出置换算法（FIFO）

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

还是用上述例子，引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
最终的置换结果如下：

前三步还是正常按序引入即可，从第四步开始，每次替换当前物理块中最先被引入的页，比如第四步中替换最先被引入的7。后续同理。

最近最久未使用置换算法（LRU）

LRU算法是根据页面调入内存后的使用情况作出决策的。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面淘汰。
同样的例子，引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
首先还是引入前三页，引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

7最大，所以替换7，引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

0在内存中，无需置换，引用序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

1最大，页面3和1进行置换：

后续同理，不再赘述。

动态分区分配算法

首次适应算法FF (first-fit)

首次适应算法（First-Fit）从链表头开始查找，选择第一个大小大于或等于所需内存大小的空闲块进行分配。由于该算法实现简单、容易理解，因此被广泛使用。
下面是一个例子，假设内存初始状态如下表：

进程 A、B、C 按顺序请求内存空间为 160、64 和 256。使用首次适应算法进行分配，步骤如下：

1. 进程 A 请求内存 160，算法找到第一个可用空间为 **256** 的内存块，分配前 160 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 可用 | 96 | | 384 | 已占据 | 64 | | 448 | 可用 | 512 | | 960 | 已占据 | 128 |

2. 进程 B 请求内存 64，算法找到第一个可用空间为 96 的内存块，分配前 64 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 已占据 | 64 | | 352 | 可用 | 32 | | 384 | 已占据 | 64 | | 448 | 可用 | 512 | | 960 | 已占据 | 128 |

3. 进程 C 请求内存 256，算法找到第一个可用空间为 512 的内存块，分配前 256 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 已占据 | 64 | | 352 | 可用 | 32 | | 384 | 已占据 | 64 | | 448 | 已占据 | 256 | | 704 | 可用 | 256 | | 960 | 已占据 | 128 |

用图表示另一个例子：

• 回收过程：若有相邻空闲区，则合并。否则，将释放区按首地址升序的规则插入到空闲区表适当的位置。
• 优点：保留高地址大空闲区，利于大作业。
• 缺点：容易产生碎片。低地址端过多小空闲区，增加查找开销

  循环首次适应算法NF

  该算法与首次适应算法相似，但是查找的位置从上一次分配的下一个地址开始查找，找到第一个适合的空闲区。
  还是上面的例子。

进程 A、B、C 按顺序请求内存空间为 12、10 和 3。使用循环首次适应算法进行分配，简要步骤如下：

• 首先A从头开始寻找，区块1合适，所以装入，此时区块1剩余8k空间，空闲地址的起始地址变为128+12 = 140
• 接下来B从140开始寻找，后续空闲地址为8，装不下，所以寻找到了区块2，占用10，区块2的空闲地址的起始地址变为212+10 = 222
• 最后C从222开始寻找，后续空闲地址为7，可以装入，占用区块2

• 优点：使存储空间更均衡，便于查找
• 缺点：缺乏大的空闲分区，不利于大作业。

  最佳适应算法BF

  该算法以容量递增的次序链接，从表(链)首开始顺序查找，直到找到第一个适合的空闲分区。若该空闲区大于作业，则划出适当空间分配出去，剩余空闲区仍留在空闲分区表(链)中。
  
  这里A从头开始找，两个区块都可以装入，但此时区块2更小，所以优先装入区块2中，后面两个区块装入同理。
  优点：找到的空闲区总既满足要求又是最小的。
  缺点：留下较小的无法利用的外碎片。

  最坏适应算法WF

  要求空闲分区按容量递减排列。从表(链)首开始顺序查找，若第一个表目都不能满足要求，分配失败；否则，划出适当分区给申请者，剩余空闲区插入空闲区表适当位置。
  
  这里A从头开始找，两个区块都可以装入，但此时区块1更大，所以优先装入区块1中，后面两个区块装入同理。
  优点：基本不留小分区
  缺点：较大的空闲分区不被保留。

  磁盘调度算法

  在后面的讲解中，我们设定一个实例的场景，假设需要读取以下编号的磁道上的数据：
  55、58、39、18、90、160、150、38、184
  读取磁道数的请求按照顺序依次到来，在读取前所有的请求都已经到达了。
  初始情况下磁头在**100号磁道**。

  先来先服务（FCFS）

  顾名思义，我们需要根据读取请求的顺序来访问磁道的数据：

优点：公平;如果请求访问的磁道比较集中的话，算法性能还算过的去
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

最短寻道优先（SSTF）

首先选择要求访问的磁道与当前磁头所在的磁道，距离最近的进程，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

从100开始移动的话，在55、58、39、18、90、160、150、38、184这个队列中，90距离100最近，所以优先访问90，后续同理。

优点：性能较好，平均寻道时间短
缺点：可能产生“饥饿”现象

例如：在本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话，150、160、184号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象。

扫描算法（SCAN）

扫描算法是对短寻道优先算法的改进，防止老进程出现饥饿现象。
这种算法需要自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，自外向里移动。

由于需要自里向外访问，所以第一个找的是比100大，且距离100最近的磁道，也就是150，接着依次向外扩展，直到184，没有比184更大的编号了之后，再不断向内部扩展。

优点：性能较好，平均寻道时间较短，不会产生饥饿现象
缺点：SCAN算法对于各个位置磁道的响应频率不平均（如:假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后，很快又可以再次响应184号磁道的请求了)

循环扫描算法

算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

如图所示：

磁盘管理

计算FAT存储大小

假定盘块的大小为1KB，硬盘的大小为512MB(不考虑分卷)，采用显示链接分配方式时，（系统以盘块为分配单位，其中FAT只能应用现有技术），其FAT需要占用多少存储空间？

首先计算盘块数，磁盘大小512MB，每个盘块1KB，那么就有512M/1K = 2**19**个。
为了存取方便，FAT中的表目一般占一个字节或半个字节，即其位数是4的倍数，所以想要存储2**19**个盘块就FAT至少需要20b = 2.5B，
整个FAT占用的空间就是一个表项的大小*总盘块数，也就是2.5B * 219 = 1.25MB

计算最大文件长度

某系统中磁盘的每个盘块大小为1KB，外存分配方法采用索引分配方式中的混合分配方式，其中索引节点中直接地址**4项**，一次间接地址**2项**，二次间接地址**1项**，每个盘块号占用4个字节，请问该系统中允许的文件最大长度是多少？

因为每个盘块号占用4个字节，所以一个磁盘最多存储1KB / 4B = **256**个目录项。一个目录项又可以指向一个磁盘块。所以：
直接地址：4 1KB
一次间接地址：2 256 1KB
二次间接地址：1 256 256 1KB
总计：66052KB

成组链接

1. UNIX系统采用空闲块成组链接的方法管理磁盘空闲空间，图中是采用UNIX操作系统的某系统的空闲块成组链接示意图，问此时若一个文件A需要5个盘块，则系统会将哪些盘块分配给它？若之后有个文件B被删除，它占用的盘块块号为333、334、404、405、782，则回收这些盘块后专用块的内容如何？

过程参照第八章：磁盘存储器的管理。