电子科技大学 - 操作系统复习题纲

教材：操作系统 - 精髓与设计原理（第八版）
Operating Systems Internals and Design Principles, Eighth Edition
主编：[美] William Stallings
译：陈向群、陈渝 等

2 进程

定义：正在运行的程序的一个抽象。

2.1 进程的执行模型

1. 顺序执行模型：做完一件事，再接着做另外的事；

2. 并行执行模型：几件事情同时做；

3. 并发执行模型：微观上的顺序执行，宏观上的并行执行。

   

2.2 进程的状态

1. 就绪态：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。

2. 执行态：进程已获得CPU，其程序正在执行。

3. 阻塞态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。

   进程的状态转换

   

4. 挂起态：使执行的进程暂停执行,静止下来,我们把这种静止状态称为挂起状态。

   

2.3 进程的控制

进程创建要做的事情：

1. 申请空白PCB；

2. 为新进程分配资源：为新进程的程序和数据以及用户栈分配必要的内存空间；

3. 初始化PCB；

   a. 初始化标识信息；

   b. 初始化处理机状态信息：使程序计数器指向程序的入口地址，使栈指针指向栈顶；

   c. 初始化处理机控制信息：进程的状态、优先级。

4. 将新进程插入就绪队列。

进程终止要做的事情：

1. 检索将被终止的进程PCB；
2. 终止该进程的执行（若有子进程，一并终止）；
3. 回收资源；
4. 将该进程PCB从当前队列中移除。

2.4 线程

• 线程是调度的最小单位；
• 进程是资源拥有的最小单位。

2.5 进程的并发

• 临界资源：一次仅允许一个进程访问的资源为临界资源；
• 临界区：
  • 把在每个进程中访问临界资源的那段代码称为临界区；
  • 代码作为一个共享资源，一次只能允许一个进程访问。
• 死锁：两个或两个以上的进程相互等待导致都不能执行；
• 活锁：由于某些条件不满足，导致进程不断重复尝试而不能正常推进执行；
• 互斥：当一个进程在临界区访问临界资源时，其他进程不能进入该临界区访问共享资源；
• 竞争：多个进程读写一个共享数据时依赖它们执行的相对时间；
• 饥饿：一个进程得不到执行机会。

同步机制遵循的准则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

信号量的应用

1. 利用信号量实现进程互斥

2. 利用信号量实现前驱关系

3. 生产者和消费者问题

   • **互斥：**共享缓冲区（缓冲区作为一种临界资源）
   • **同步：**相互等待（有产品才能消费，有消费才能不断生产）

   因为互斥，所以利用互斥信号量Mutex实现诸进程对缓冲池的互斥使用;

   因为同步，所以利用信号量Empty和Full分别表示缓冲池中空缓冲区和满缓冲区的数量。

注意：

• 互斥信号量Mutex初始化永远为 1；
• Full = 0 表示满缓冲区数量为 0；
• Empty = n 表示空缓冲区数量为 n。

核心代码：

**注意：**上述核心代码中，P操作顺序颠倒会导致死锁！

4. 读者/写者问题

多个进程对同一个文件进行读写，要求：

• 不能同时写文件
• 不能同时读和写文件
• 可以同时读文件

核心代码（读者优先）：

注意：

• 为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex；
• Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。

2.6 管程 Monitor

定义： 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

主要特点：

• 局部数据变量只能被管程的过程访问，任何外部过程都不能访问；
• 一个进程通过调用管程的一个过程进入管程；
• 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的。

2.7 进程间通信

1. 消息传递

   • 直接传递
   • 间接传递

2. 共享存储器

   • 共享存储区

   • 共享数据结构

3. pipe

2.8 进程调度

短程调度：给就绪队列中的进程分配CPU；

中程调度：决定把哪些暂时不用的代码或数据唤到外存，把紧急的唤进来，也即是挂起；

长程调度：决定为哪些后备作业创建相应的进程，通常也称为作业调度。

调度算法

1. FCFS (First-Come-First-Served) 先来先服务 FIFO 不抢占
2. RR (Round-Robin) 时间片轮转 抢占
3. SPN (Shortest Process Next) 短进程优先 不抢占
4. SRT (Shortest Remaining Time) 最短剩余时间优先（抢占式短进程优先） 抢占，其平均周转时间最短
5. HRRN (Highest Response Ratio Next) 高响应比优先 不抢占
6. Feedback 反馈 抢占

注意： RR中，上一个进程A刚结束，下一个进程B到来，此时就绪队列中，B应该排在A的前面。

注意：通常抢占式短进程优先算法的平均周转时间最小（也即是性能最好）！

高响应比的计算公式：

w：等待时间

s：服务时间

2.9 死锁

• 避免：不破坏产生死锁的3个必要条件P1、P2、P3，通过一定的策略防止系统进入死锁区
  • P1·P2·P3 => ~P4 => ~DeadLock
• 预防：破坏P2、P3、P4（P1不能破坏）
  • P2·P3·P4 => ~DeadLock

银行家算法

属于“避免”，不属于“预防”！！！

示例（书本199页习题6.5）：

6.5 在如下条件下考虑银行家算法。

​ 6 个进程： P0~P5

​ 4 种资源：A（15单位），B（6单位），C（9单位），D（10单位）

​ 时间 T0 时的情况：

1. 验证可用资源向量的正确性。
2. 计算需求矩阵。
3. 证明当前状态是安全的，即给出一个安全的进程序列。（工作数组）在每个进程终止时的变化情况。
4. 假设进程P5的请求为（3，2，3，3）。该请求应被允许吗？请说明理由。

解：

思路： 一开始，可用资源为（6，3，5，4），从P0开始分配，发现不够分配（看需求矩阵，P0需求量比当前可用资源数目大），转而尝试P1，发现够分，于是分给P1，P1执行完，回收P1已分配的资源（0，1，1，1），加到当前可用的资源数目中，为（6，4，6，5），也即是P1进程结束时可用资源数量，接着分P2…

---

3 内存管理

3.1 程序的装入和链接

1. 编译：由编译程序（Compiler）将用户源代码编译成若个目标模块；
2. 链接：由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块；
   • 静态链接
   • 装入时链接
   • 运行时动态链接
3. 装入：由装入程序（Loader）将装入模块装入内存。
   • 绝对装入
   • 重定位装入：重定位就是说目标程序在内存中地址发生变化，也称为静态重定位
   • 运行时装入：也称为动态重定位

3.2 连续分配方式

1. 单一连续分配

2. 固定分区分配

   • 优点：可运行多道程序的存储管理方式；
   • 缺点：存在“内零头”（在分区内没有利用的部分），会造成存储空间的浪费。

3. 动态分区分配

   注意：在分区内无法利用的小存储块称为“外零头”。

   示例（书中217页习题7.6）：

   

   解：

   a. 8MB

   b. 1 + 2 + 5 = 8MB

   c.

   ​ 最佳适配：空闲空间与请求的最接近分区块；此题为 3MB

   ​ 首次适配：此题为第一个 4MB

   ​ 下次适配：接着上次的位置往后找；此题为 5MB

   ​ 最差适配：此题为 8MB

4. 可重定位分区分配

   紧凑：

   

   分配算法：

   

5. 伙伴系统

   特点：一种不需要紧凑的动态分区算法。

   

3.3 离散分配方式

3.3.1 分页存储管理

基本思想：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页（Page）；相应地，也把内存空间分成与页面相同大小的若干个存储块，称为**（物理）块（Block）或页框（Frame）**，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

空间的组织

分页的地址结构（逻辑地址空间）

页表

**作用：**记录页面与物理块的对应关系！

页表长度：一个进程包含的页面数目，在页表寄存器中；

页表宽度：页表中任何一项的位数

页表的空间大小 = 页表长度 * 页表宽度

地址变换机构

作用：将逻辑地址（在用户地址空间中）变换为物理地址（在内存空间中）

示例：

考虑一个简单分页系统，物理存储器大小为4GB,页大小为1KB,逻辑地址空间分为2^16个页

1. 逻辑地址空间包含多少位？

   

   页号为16位，偏移位为10位（因为页大小为1KB），所以总共包含26位。

2. 一个帧中包含多少字节？

   一个帧（也就是物理块）包含的字节应该等于一个页面包含的字节，为1KB。

3. 物理地址中指定一个帧需要多少位？

   4GB / 1KB = 2^22，所以 4GB = 2^22 块，故一个帧（也即是物理块）需要22位。

4. 页表中包含多少个页表项？

   每个页表项都存了页号和块号的对应关系，所以每个页面都对应一个页表项，页面有2^{16个，页表项就有2}16个。

5. 每个页表项包含多少位？

多级页表

---

3.3.2 段式存储管理

3.3.3 段页式存储管理

3.4 对换

3.5 虚拟存储器

基本概念（重点！！！）：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

3.5.1 虚拟存储管理的实现方法

• 请求分页存储管理方式

  核心思想：系统运行时只加载必要的页，运行过程中若需访问其他页面，则触发“缺页中断”，调入该页面，若内存不够，则要做交换。

  页面的调入：

  • 预调页策略

  • 请求调页策略

    ---

  1. **最佳置换算法（OPT）：**选择被淘汰的页面，将是以后永不使用的，或许是在最长时间内不再被访问的页面。

     示例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

     7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

     采用最佳置换算法发生了6次页面置换。

     

     注意：一般考试中还会出现两个词，缺页次数和缺页率。

     缺页次数：此处为9次；

     缺页率：此处为 9 / 20 = 45%。

  2. **先进先出（FIFO）页面置换算法：**该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

     

  3. **最近最久未使用（LRU）置换算法：**选择最近最久未使用的页面予以淘汰。

     

  4. （常考！）简单的Clock置换算法：只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。

     

  5. （常考！）改进的Clock置换算法：

     

  示例（书本255页习题8.4）：

  

  题c解法：

  

  另外，记得看复习材料3的简答题！！

• 请求分段系统

  核心思想：它允许只装入若干段的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能，将暂不运行的段调出，同时调入即将运行的段。