操作系统期末复习

操作系统概述

操作系统的定义与特征

• 定义：操作系统是计算机系统资源的管理者，处于裸机之上的第一层软件.
• 特征：
  • 并发性
  • 共享性
  • 虚拟性
  • 不确定性

操作系统的基本类型

• 实时系统：对响应时间有严格要求，分为硬实时和软实时两种.
• 分时系统：在一台主机上同时连接多台终端，允许多个用户同时使用计算机，但每个用户的响应时间会随着用户数的增加而变长.
• 批处理系统：把多个作业同时提交给计算机，作业之间无须进行交互，系统按照一定的顺序依次执行作业.
• 分布式系统：由多台计算机组成的系统.

单道与多道程序

• 单道程序：内存中只有一个程序，CPU 与 I/O 设备串行工作，即在一个程序的输入、计算和输出阶段完成后，才能开始下一个程序的执行.
• 多道程序：
  • 宏观上并行 微观上串行
  • 实现前提：系统具有中断功能
  • 资源分配单位：操作系统是以进程为单位分配资源的.

例题

假设程序 P1、P2 和 P3 的执行时间如下：

• P1: 输入 5ms，计算 3ms，输出 4ms.
• P2: 输入 4ms，计算 1ms，输出 3ms.
• P3: 输入 5ms，计算 3ms，输出 4ms.

1. 在单道批处理环境下，计算完成 3 道程序运行需要的最少时间。
2. 在多道批处理环境下，计算完成 3 道程序运行需要的最少时间。

单道批处理环境

• 输入时间：5 + 4 + 5 = 14 ms
• 计算时间：3 + 1 + 3 = 7 ms
• 输出时间：4 + 3 + 4 = 11 ms

总时间 = 14 + 7 + 11 = 32 ms

多道批处理环境

• 输入时间：5 + 4 + 5 = 14 ms
• 计算时间：最长的计算时间是 3ms
• 输出时间：4 + 3 + 4 = 11 ms

总时间 = 14 + 3 + 11 = 28 ms

进程管理

程序并发执行的特征

• 间断性
• 失去了封闭性
• 不可再现性

并发

• 定义：是指宏观上可同时执行的进程，即多个进程在时间上交替执行，从宏观上看它们是同时进行的，但实际上是交替占用 CPU 资源的.
• 并发执行的程序具有不可再现性，因为它们的执行结果可能受到其他并发程序的影响，且执行顺序和时间不确定.
• 并发进程之间可能需要同步或互斥，以协调它们之间的执行顺序或防止对共享资源的冲突访问.

进程与线程

• 多道程序环境中操作系统分配资源是以进程为单位的，进程是程序在执行过程中的动态实体，拥有独立的地址空间和系统资源.
• 操作系统用 PCB（进程控制块） 来管理与控制进程，PCB 记录了进程的运行状态、优先级、资源使用情况等信息.
• 管理和控制是通过原语来实现的，原语是操作系统提供的一组低级系统调用，用于创建、撤销、挂起、唤醒等进程操作.
• 线程：是进程中的一个执行流，是 CPU 调度和执行的最小单位，线程之间共享进程的资源，但每个线程有自己的栈和寄存器等局部状态.
• 线程与进程的区别主要在于是否拥有独立的资源，进程拥有独立的地址空间和资源，而线程共享进程的资源，但有自己的局部状态.

同步与互斥

• 同步：是指进程之间逻辑上的制约关系，即某些进程的执行必须等待其他进程完成某些操作后才能继续执行，以保证程序的逻辑正确性.
• 互斥：是指同一时间内只能允许一个进程访问临界资源，临界区是访问临界资源的一段程序，通过互斥机制可以防止多个进程同时访问临界资源导致的数据不一致等问题.
• 资源的有序分配策略：可以破坏循环等待资源条件，从而预防死锁的发生，例如按照资源编号顺序申请资源等.

死锁

• 预防死锁：可以通过破坏死锁产生的四个必要条件之一来实现，这四个条件是互斥条件、请求和保持条件、不剥夺条件、循环等待条件.
• 避免死锁：是避免系统进入不安全状态，即在资源分配过程中，始终确保系统处于安全状态，不会发生死锁，银行家算法是一种常用的避免死锁的算法，通过模拟资源分配过程来判断系统是否安全.

例题 1

系统有 4 个进程 P1、P2、P3、P4，它们的到达时间和服务时间（或处理时间）如下表所示：

进程名	到达时间	处理时间	开始时间	完成时间
P1	0	2	0	2
P2	2	6	2	8
P3	4	4	10	14
P4	6	2	8	10

1. 各个进程的周转时间？
2. 所有进程的平均周转时间是多少？

周转时间

周转时间 = 完成时间 - 到达时间

• P1：周转时间 = 2 - 0 = 2
• P2：周转时间 = 8 - 2 = 6
• P3：周转时间 = 14 - 4 = 10
• P4：周转时间 = 10 - 6 = 4

平均周转时间

平均周转时间 = (所有进程的周转时间之和) / (进程数)

• 所有进程的周转时间之和 = 2 + 6 + 10 + 4 = 22
• 进程数 = 4

平均周转时间 = 22 / 4 = 5.5

例题 2

假设系统中有 5 个进程 P1、P2、P3、P4 和 P5，有 3 种类型的资源 A、B 和 C。初始资源分配情况如下：

进程	已分配资源数量	最大资源需求量
P1	0 0 3	0 0 4
P2	0 7 5	0 6 0
P3	5 3 5	2 3 5
P4	0 2 0	0 6 6
P5	0 0 6	5 5 2

初始可用资源数为 (x, y, z)。
请问当 x，y，z 取值分别为 0，5，8 和 1，5，2 时，系统是否处于安全状态？为什么？

银行家算法

1. 计算 Need 矩阵：
   {Need} = {最大资源需求量} - {已分配资源数量}

   • P1: Need = (0 0 4) - (0 0 3) = (0 0 1)
   • P2: Need = (0 6 0) - (0 7 5) = (0 -1 -5)
   • P3: Need = (2 3 5) - (5 3 5) = (-3 0 0)
   • P4: Need = (0 6 6) - (0 2 0) = (0 4 6)
   • P5: Need = (5 5 2) - (0 0 6) = (5 5 -4)

2. 判断系统是否处于安全状态：

   • 从可用资源数开始，检查是否存在一个进程，其 Need 小于或等于可用资源数.
   • 如果存在这样的进程，假设该进程获得资源并执行完毕，然后释放其所有资源，更新可用资源数.
   • 重复上述步骤，直到所有进程都能获得资源并执行完毕，或者没有进程可以满足条件.

当 x，y，z 取值分别为 0，5，8

• 可用资源数 = (0 5 8)
• 检查 Need 矩阵：
  • P1: Need(0 0 1) <= Available(0 5 8)？是的，因为 0 <= 0, 0 <= 5, 1 <= 8.
  • P1 可以执行，执行后释放资源，可用资源数变为 (0+0, 5+0, 8+3) = (0 5 11).
  • 此时，没有其他进程的 Need 可以被满足（P2、P3、P4、P5 的 Need 都包含负数或超过可用资源），因此系统处于不安全状态.

当 x，y，z 取值分别为 1，5，2

• 可用资源数 = (1 5 2)
• 检查 Need 矩阵：
  • P1: Need(0 0 1) <= Available(1 5 2)？是的，因为 0 <= 1, 0 <= 5, 1 <= 2.
  • P1 可以执行，执行后释放资源，可用资源数变为 (1+0, 5+0, 2+3) = (1 5 5).
  • P3: Need(-3 0 0) <= Available(1 5 5)？是的，因为-3 <= 1, 0 <= 5, 0 <= 5.
  • P3 可以执行，执行后释放资源，可用资源数变为 (1+5, 5+3, 5+5) = (6 8 10).
  • 此时，所有进程的 Need 都可以被满足，因此系统处于安全状态.

例题 3

桌上有一个盘子，最多可存放两个水果。
妈妈向盘子中放苹果或桔子。
儿子专吃盘子中的桔子，女儿专吃盘子里的苹果。
取、放水果不能同时 进行。试用 PV 操作实现三个人的同步，并写出程序描述。

在这个问题中，我们需要使用信号量（semaphores）来实现妈妈、儿子和女儿之间的同步。信号量用于控制对共享资源的访问，确保在任何时刻只有一个操作可以进行。

信号量说明

• mutex：用于互斥访问盘子，初始值为 1.
• Sd：表示盘子中水果的总数，初始值为 2（因为盘子最多可放两个水果）.
• So：表示盘子中桔子的数量，初始值为 0.
• Sa：表示盘子中苹果的数量，初始值为 0.

操作说明

• P 操作（wait）：用于等待信号量的值大于 0，然后将其减 1，表示正在使用资源.
• V 操作（signal）：用于将信号量的值加 1，表示释放资源.
• mutex信号量用于互斥访问盘子，确保在任何时刻只有一个操作（放入或取出水果）可以进行.
• Sd信号量用于控制盘子的容量，确保盘子不会超过两个水果.
• So和Sa信号量分别用于同步桔子和苹果的数量，确保儿子和女儿能够正确地取出他们想要的水果.

程序描述

妈妈（Mother）

妈妈的任务是向盘子中放入水果（苹果或桔子），并确保盘子不会超过容量限制.

void Mother() {
    while (true) {
        // 选择放入水果的类型
        if (放入桔子) {
            P(Sd);  // 等待盘子有空位
            P(mutex);  // 获取对盘子的互斥访问
            // 放入桔子
            V(mutex);  // 释放对盘子的互斥访问
            V(So);  // 增加盘子中桔子的数量
        } else {
            P(Sd);  // 等待盘子有空位
            P(mutex);  // 获取对盘子的互斥访问
            // 放入苹果
            V(mutex);  // 释放对盘子的互斥访问
            V(Sa);  // 增加盘子中苹果的数量
        }
    }
}

儿子（Son）

儿子的任务是取出盘子中的桔子.

void Son() {
    while (true) {
        P(So);  // 等待盘子中有桔子
        P(mutex);  // 获取对盘子的互斥访问
        // 取出桔子
        V(mutex);  // 释放对盘子的互斥访问
        V(Sd);  // 增加盘子的空位
    }
}

女儿（Daughter）

女儿的任务是取出盘子中的苹果.

void Daughter() {
    while (true) {
        P(Sa);  // 等待盘子中有苹果
        P(mutex);  // 获取对盘子的互斥访问
        // 取出苹果
        V(mutex);  // 释放对盘子的互斥访问
        V(Sd);  // 增加盘子的空位
    }
}

存储器原理

例题 1

如果页面访问序列 0、3、6、5、6、2、4、3、2、5，且进程开始执行时，内 存中没有页面（初始为空），若给该进程分配驻留集为 3 个物理块，如下所示： 使用先进先出（FIFO）置换算法和用 LRU 置换算法。

1. 缺页中断次数、页面置换次数、缺页率分别是多少？
2. 如果进程开始执行前，将最开始的 3 页先装入内存，会产生多少次缺页中断？

页面置换算法的基本概念

在虚拟存储器中，当一个进程访问的页面不在内存中时，会发生缺页中断。此时，操作系统需要从磁盘中将该页面调入内存。如果内存已满，就需要选择一个页面将其置换出内存，以便为新页面腾出空间。页面置换算法就是用来决定哪个页面应该被置换出内存的规则.

操作过程

题目关键信息:

• 页面访问序列为：0、3、6、5、6、2、4、3、2、5，内存块数为 3，初始时内存为空.

FIFO 算法（先进先出）

• 基本原理：FIFO 算法按照页面进入内存的顺序来决定置换顺序，即最早进入内存的页面最先被置换出.
• 工作过程：
  1. 当发生缺页中断时，检查内存中是否有空闲的内存块.
  2. 如果有空闲内存块，直接将缺失的页面装入空闲内存块中.
  3. 如果没有空闲内存块，选择最早进入内存的页面将其置换出，然后将缺失的页面装入该内存块中.

FIFO 算法操作过程

• 访问 0：缺页，装入内存块 1，内存状态：[0, -, -].
• 访问 3：缺页，装入内存块 2，内存状态：[0, 3, -].
• 访问 6：缺页，装入内存块 3，内存状态：[0, 3, 6].
• 访问 5：缺页，置换内存块 1（0 -> 5），内存状态：[5, 3, 6].
• 访问 6：不缺页，内存状态：[5, 3, 6].
• 访问 2：缺页，置换内存块 2（3 -> 2），内存状态：[5, 2, 6].
• 访问 4：缺页，置换内存块 3（6 -> 4），内存状态：[5, 2, 4].
• 访问 3：缺页，置换内存块 1（5 -> 3），内存状态：[3, 2, 4].
• 访问 2：不缺页，内存状态：[3, 2, 4].
• 访问 5：缺页，置换内存块 2（2 -> 5），内存状态：[3, 5, 4].

LRU 算法（最近最少使用）

• 基本原理：LRU 算法根据页面最近的使用情况来决定置换顺序，即最近最少使用的页面最先被置换出.
• 工作过程：
  1. 当发生缺页中断时，检查内存中是否有空闲的内存块.
  2. 如果有空闲内存块，直接将缺失的页面装入空闲内存块中.
  3. 如果没有空闲内存块，选择最后面的页面，即最久未被访问的页面将其置换出，然后将缺失的页面装入该内存块中.

LRU 算法操作过程

• 访问 0：缺页，装入内存块 1，内存状态：[0, -, -].
• 访问 3：缺页，装入内存块 2，内存状态：[0, 3, -].
• 访问 6：缺页，装入内存块 3，内存状态：[0, 3, 6].
• 访问 5：缺页，置换内存块 1（0 -> 5），内存状态：[5, 3, 6].
• 访问 6：不缺页，内存状态：[5, 3, 6].
• 访问 2：缺页，置换内存块 2（3 -> 2），内存状态：[5, 2, 6].
• 访问 4：缺页，置换内存块 3（6 -> 4），内存状态：[5, 2, 4].
• 访问 3：缺页，置换内存块 1（5 -> 3），内存状态：[3, 2, 4].
• 访问 2：不缺页，内存状态：[3, 2, 4].
• 访问 5：缺页，置换内存块 2（2 -> 5），内存状态：[3, 5, 4].

总结

• FIFO 算法：
  • 初始为空时：缺页中断次数=8，页面置换次数=5，缺页率=80%.
• LRU 算法：
  • 初始为空时：缺页中断次数=8，页面置换次数=5，缺页率=80%.

例题 2

某虚拟存储器（采用请求页式存储管理）的用户空间共有 64 个页面，每页 1KB，内存 32KB。假定某用户作业的长度为 6 页，进程驻留集为 3 个内存块。
某时刻系统为用户的第 0、1、2 页分配的内存块号分别为 4、5、6。
假设逻辑地址(或虚拟地址)的访问序列 0A2DH、106FH、1A33H（H 表示十六进制），将 3 个逻辑地址转换成物理地址，若能够转换，则说明转换过程，并给出具体的物理地址;若不能转换，则说明原因。

题目关键信息:

• 用户空间共有 64 个页面，每页 1KB.
• 内存为 32KB.
• 进程驻留集为 3 个内存块，系统为用户的第 0、1、2 页分配的内存块号分别为 4、5、6.
• 逻辑地址的访问序列：0A2DH、106FH、1A33H.

地址转换

1. 确定页号和偏移量：

   • 由于每页 1KB，即(2^{10})字节，因此偏移量占 10 位.
   • 用户空间有 64 个页面，即(2^6)页，因此页号占 6 位.

2. 转换逻辑地址到物理地址：

   • 将逻辑地址转换为二进制形式.
   • 分离出页号和偏移量，页号位于二进制表示的高位，偏移量位于低位.
   • 检查页号是否合法（是否小于 64）.
   • 检查该页是否已装入内存.
     • 如果该页已装入内存，将页号替换为对应的物理块号，拼接偏移量得到物理地址.
     • 如果该页未装入内存，产生缺页中断.
     • 如果页号不合法，访问越界.

示例计算

逻辑地址 0A2DH

• 转换为二进制：0A2DH = 000010 1000101101B
• 分离页号和偏移量：
  • 页号(高位) = 000010B（或 2 号页）
  • 偏移量(低位) = 1000101101B
• 检查页号合法性：2 号页 < 64，页号合法.
• 检查内存块：2 号页已装入内存，对应物理块号为 6（0110B）.
• 计算物理地址：将页号替换为对应的物理块号，物理地址 = 011010 00101101B，即 1A2DH.

逻辑地址 106FH

• 转换为二进制：106FH = 000100 0001101111B
• 分离页号和偏移量：
  • 页号(高位) = 000100B（或 4 号页）
  • 偏移量(低位) = 00001101111B
• 检查页号合法性：4 号页 < 64，页号合法.
• 检查内存块：4 号页未装入内存，故产生缺页中断.

逻辑地址 1A33H

• 转换为二进制：1A33H = 0001101000110011B
• 分离页号和偏移量：
  • 页号 = 000110B（或 6 号页）
  • 偏移量 = 001000110011B
• 检查页号合法性：6 号页 < 64，页号合法.
• 检查内存块：6 号页未装入内存，故产生缺页中断.

结论

• 逻辑地址 0A2DH：可以转换为物理地址 1A2DH.
• 逻辑地址 106FH：不能转换，因为该页未装入内存，产生缺页中断.
• 逻辑地址 1A33H：不能转换，因为该页未装入内存，产生缺页中断.

例题 3

假设一次内存的访问时间是 80ns,一次快表的访问时间是 10ns，采用最 近最久未使用（LRU）页面置换算法，处理一次缺页中断的平均时间是 200ns (包括更新快表和页表的时间）。
访问逻辑地址(或虚拟地址) 106FH 的物理地址和时间分别是多少？

题目关键信息:

• 一次内存的访问时间是 80ns.
• 一次快表的访问时间是 10ns.
• 处理一次缺页中断的平均时间是 200ns (包括更新快表和页表的时间).
• 采用最近最久未使用（LRU）页面置换算法.

页表信息

页号	内存块号	状态位	访问字段	装入内存时间	上次访问时间	修改位	外存地址
0	4	1	0:20:16	10:20:16	10:20:20	1	123
1	5	1	0:20:14	10:20:14	10:20:18	0	47
2	6	1	0:20:11	10:20:11	10:20:21	1	23

地址转换步骤

1. 确定页号和偏移量：

   • 逻辑地址 106FH = 000100 0001101111B.
   • 页号 = 000100B（或 4 号页）.
   • 偏移量 = 00001101111B.

2. 检查页号合法性：

   • 4 号页 < 6，不越界.

3. 检查内存块：

   • 4 号页未装入内存，故产生缺页中断.

4. 处理缺页中断：

   • 根据 LRU 置换算法，查表得应淘汰 1 号页.
   • 4 号页存放在 5 号块的位置，块号是 0101.
   • 偏移量：00001101111B.
   • 物理地址：010100 0001101111B，即 146FH.

5. 计算访问时间：

   • 一次快表的访问时间是 10ns.
   • 一次内存的访问时间是 80ns.
   • 处理一次缺页中断的平均时间是 200ns.
   • 总时间 = 快表访问时间 + 内存访问时间 + 缺页中断处理时间.
   • 总时间 = 10ns + 80ns + 200ns = 290ns.

结论

• 物理地址：146FH.
• 访问时间：290ns.

设备管理

虚拟存储管理

1. 虚拟存储器：通过将主存和辅存结合起来，为用户提供一个比实际主存空间大得多的存储空间。
2. 请求页式管理：一种虚拟存储管理方式，当进程运行时，只有部分页面被调入内存，其余页面存放在辅存中，当需要访问不在内存中的页面时，发生缺页中断，操作系统会将该页面调入内存。
3. 页表：用于记录虚拟页号到物理块号的映射关系，是实现虚拟地址到物理地址转换的关键数据结构。
4. 缺页中断：当访问的页面不在内存中时，系统会触发缺页中断，将该页面从辅存调入内存，可能需要替换内存中的某些页面。
5. 页面置换算法：当内存空间不足时，选择一个页面将其移出内存，以便为新页面腾出空间。常见的算法有 FIFO、LRU 等.
6. 局部性原理：程序在运行过程中，其访问的地址空间具有时间局部性和空间局部性，即在一段时间内，程序倾向于访问相近的地址和重复访问某些地址，这为虚拟存储管理提供了理论基础.

文件系统

1. 文件的存取方式：顺序存取 随机存取 .
2. 文件的逻辑结构：从用户的角度看到的文件组织方式，常见的有无结构文件和有结构文件（如顺序文件、索引文件、索引顺序文件等）.
3. 文件的物理结构：指文件在外存上的存储形式，常见的有连续分配、链接分配和索引分配等.
4. 文件控制块（FCB）：用于存储文件的基本信息、存取控制信息和文件的使用信息等，是文件系统管理文件的重要数据结构.
5. 文件目录：是文件控制块的集合，用于实现文件的符号名与物理地址的转换，方便用户管理和访问文件.
6. 多级目录结构：采用多级目录结构可以解决命名冲突问题，允许多个用户使用相同的文件名，同时提高了文件系统的灵活性和安全性.
7. 目录的功能：实现“按名存取”，提高文件检索速度，允许文件同名等.
8. 文件系统的安全性：通过设置文件的访问权限、密码保护等措施，确保文件系统的安全性，防止未授权访问和数据泄露等.
9. 文件系统的可靠性：采用文件备份、日志记录等技术手段，提高文件系统的可靠性，防止因系统故障等原因导致数据丢失或损坏.