[Study]操作系统

一、概述

1.1 操作系统概述

1. 操作系统的概念：操作系统（Operating System）控制和管理整个计算机系统的硬件和软件资源，合理地调度计算机的工作和资源，提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件

2. 操作系统应具有的功能：

   • 操作系统作为系统资源的管理者：处理机（进程）管理、存储器（内存）管理、文件管理、设备管理

   • 操作系统作为用户与计算机硬件之间的接口：命令接口（允许用户直接使用）、程序接口（由一组系统调用组成，程序接口 = 系统调用 = 系统调用命令 = 广义指令）、图形用户界面

   • 操作系统作为最接近硬件的层次：实现对硬件机器的扩展（裸机上安装操作系统便可以提供资源管理功能以方便用户使用）

3. 操作系统的特征：

   • 并发（并发与并行）
   • 共享（互斥与同时）
   • 虚拟（空分虚拟和时分虚拟）
   • 异步

   其中 并发和共享 是两个最基本的特征，二者互为存在条件

4. 操作系统的发展和分类：

   • 手工操作阶段

   • 批处理阶段（单、多道批处理）

   • 分时操作系统：计算机以时间片为单位轮流为各个用户 / 作业服务，各个用户可通过终端与计算机进行交互

   • 实时操作系统（硬、软实时系统）

   • 网络操作系统

   • 分布式操作系统

   • 个人计算机操作系统

   其中 多道批处理系统 的出现标志着操作系统开始出现

1.2 运行机制

1. 两种指令

   • 特权指令：运行在核心态
   • 非特权指令：运行在核心态或用户态

2. 两种处理器状态：用程序状态字寄存器（PSW）的某个标志位标识当前处理器状态

   • 用户态（目态）
   • 核心态（管态）

3. 两种程序

   • 内核程序：需要使用特权指令的程序
   • 应用程序：无需使用特权指令的程序

4. 操作系统内核：细分为大内核与微内核。内核是计算机上配置的底层软件，是操作系统最基本、最核心的部分，需要实现时钟管理、中断管理、原语等核心功能。对系统资源进行管理时还需要实现进程管理、内存管理、设备管理、文件管理等功能

   • 原语是一种特殊的程序，处于操作系统最底层，是最接近硬件的部分，这种程序运行时间较短、调用频繁且具有原子性（一气呵成，不可中断）

1.3 中断与异常

1. 中断机制的诞生：为了实现多道应用程序并发执行而引入的一种技术。中断可以使 CPU 从 用户态 -> 核心态，使操作系统获得计算机的控制权，从而开展一系列的管理工作

2. 中断的分类：

   • 内中断：也称 异常、陷入、例外。信号来源于 CPU 内部，与当前执行的指令有关
   • 外中断：简称中断。信号来源于 CPU 外部，与当前执行的指令无关

3. 用户态与核心态的切换：

   • 用户态 -> 核心态：中断 是唯一途径
   • 核心态 -> 用户态：执行一个特权指令将程序状态字（PSW）标志位设置为 “用户态”

1.4 系统调用

1. 系统调用概念：系统调用是操作系统提供给应用程序（编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。系统调用发生在用户态，对系统调用的处理发生在核心态

2. 系统调用按功能分类：设备管理、文件管理、进程控制、进程通信、内存管理

3. 系统调用与库函数的区别：

4. 系统调用过程：传递系统调用参数 -> 执行陷入指令（用户态）-> 执行系统调用（核心态）-> 返回用户程序
   • 陷入指令在用户态下执行，执行后立即引发一个 内中断 从而使 CPU 进入核心态
   • 陷入指令是 唯一 一个只能在 用户态 下执行而不能在核心态下执行的指令

二、进程管理

2.1 进程定义及特征

1. PCB：系统为每个运行的程序配置一个数据结构称为进程控制块（PCB），用来描述进程的各种信息（指令和数据）。其中包括了进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息等

2. 进程与进程实体：

   • PCB、程序段、数据段三部分构成了进程实体（进程映像）
   • 进程（动态）是进程实体（静态）的运行过程，是系统进行资源分配和调度的一个独立单位

3. 进程的组织方式：

   • 链接方式：按照进程状态将 PCB 分为多个队列，操作系统持有指向各个队列的指针
   • 索引方式：按照进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针

4. 进程的特征：动态性、并发性、独立性、异步性、结构性

2.2 进程状态与转换

1. 进程的三种基本状态：运行态（Running）、就绪态（Ready）、阻塞态（Waiting/Blocking）

2. 进程的另外两种状态：新建（New）、终止态（Terminated）

3. 进程状态间转换过程：

   • 运行态 -> 阻塞态：进程自身做出的主动行为
   • 阻塞态 -> 就绪态：不是进程自身能够控制的，是一种被动行为

2.3 进程控制

1. 进程控制概念：主要目的是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能
2. 进程控制实现：操作系统中使用原语来实现进程控制。原语的特点是执行期间不允许中断、只能一气呵成，这种不能被中断的操作称为原子操作，具体采用 “关中断指令” 和 “开中断指令” 实现
3. 原语实现进程控制的职责：
   • 更新 PCB 中的信息：修改进程状态标志、将运行环境保存到 PCB、从 PCB 恢复运行环境
   • 将 PCB 插入到合适的队列
   • 分配 / 回收资源

2.4 进程通信的三种方式

1. 共享存储：两个进程对数据结构或存储区的访问必须是互斥的
2. 消息传递：进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的 “发送消息 / 接收消息” 两个原语进行数据交换
3. 管道通信：管道只能采用 半双工通信 即某一时间段内只能实现单向数据传输
   • 各个进程需要 互斥 地访问管道
   • 数据以字符流的形式写入管道，当管道写满时写进程的 write() 系统调用将被阻塞，等待中的读进程将数据读走。当读进程将数据全部取走后，管道变空，此时读进程的 read() 系统调用将被阻塞
   • 如果管道未写满则不允许读，同理未读空则不允许写
   • 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会导致数据读取错误

2.5 线程概念

1. 线程概念：线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位。引入线程之后，进程只作为除 CPU 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。进程是 资源分配 的基本单位，而线程是 处理机调度 的基本单位

2. 线程的属性：

   • 线程是处理机调度的基本单位
   • 线程也有就绪、运行、阻塞三种基本状态
   • 每个线程都有一个线程 ID、线程控制块（TCB）
   • 多 CPU 计算机中，各个线程可占用不同的 CPU
   • 同一进程的不同线程间共享进程资源，线程间通信甚至无需系统干预
   • 同一进程中的线程切换，不会引起进程切换，系统开销小；不同进程中的线程切换，会引起进程切换，系统开销大

3. 线程的实现方式：

   • 用户级线程（User-Level Thread，ULT）：“从用户视角能看到的线程”，由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责，在用户态下即可完成，无需操作系统的干预

     

   • 内核级线程（Kernel-Level Thread，KLT）：“从操作系统内核视角能看到的线程”，又称内核支持的线程。内核级线程的管理工作由操作系统内核完成，因而内核级线程的切换必然需要在核心态下才能完成

     

2.6 三种多线程模型

1. 多对一模型：多个用户级线程映射到一个内核级线程，即每个用户进程只对应一个内核级线程

   • 优点：用户级线程的切换在用户态即可完成，无需切换到核心态，线程管理开销小，效率高
   • 缺点：当一个用户级线程被阻塞后，整个用户进程都会被阻塞，并发度不高，多个用户线程不可在多核处理机上并行执行

   

2. 一对一模型：一个用户级线程映射到一个内核级线程，即一个用户进程对应多个内核级线程

   • 优点：当一个线程被阻塞后，别的线程可以继续执行，并发能力强，可在多核处理机上并行执行
   • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到内核态下进行管理，成本高，开销大

   

3. 多对多模型：n 个用户级线程映射到 m 个内核级线程（n >= m），即每个用户进程对应多个内核级线程

   • 克服了多对一模型并发度不高的缺点
   • 克服了一对一模型中一个用户进程占用过多内核级线程的缺点

   

2.7 处理机调度的三个层次

1. 高级调度（作业调度）：外存与内存之间的调度

   • 每个作业只调入一次，调出一次
   • 作业调入时建立相应的 PCB，调出时撤销 PCB

2. 中级调度（内存调度）：决定将哪个处于 挂起状态 的进程重新调入内存

   • 一个进程可能会被多次调入、调出内存，因而中级调度发生的频率要比高级调度更高

• 引入虚拟存储技术之后，可以将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存空闲时重新调入内存，这么做的目的是为了提高内存利用率和系统吞吐量。值得注意的是，进程的 PCB 并不会一起调到外存，而是会常驻内存。PCB 中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的 PCB 来保持对各个进程的监控和管理

• 挂起状态：暂时调到外存等待的进程状态称为 挂起状态（suspend）。“挂起” 和 “阻塞” 的区别：挂起态将进程映像调到外存，阻塞态下进程映像仍在内存中

3. 低级调度（进程调度）：主要任务是按照某种方法或策略从就绪队列中选取一个进程，并将处理器分配给它。进程调度是操作系统中最基本的一种调度，频率很高，一般几十毫秒调度一次

三种处理机调度层次的联系和对比：

2.8 进程调度概述

1. 进程调度的方式：非剥夺调度方式（非抢占）和剥夺调度方式（抢占）

2. 不能进行进程调度与切换的情况：

   • 在处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
   • 进程在操作系统 内核程序临界区 中：
     • 内核程序临界区：一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）
     • 临界区：访问临界资源的那段代码
     • 临界资源：一段时间内只允许一个进程使用的资源，各个进程需要互斥地访问临界资源
   • 在原子操作过程中（原语操作应一气呵成，不可中断）

2.9 调度算法的评价指标

1. CPU 利用率：指 CPU “忙碌” 时间占总时间的比例

2. 系统吞吐量：单位时间内完成的作业数量

3. 周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔，由以下各部分时间组成：高级调度时间 + 低级调度时间 + CPU 上执行时间 + 等待 I/O 完成的时间

   • 平均周转时间 = 各作业周转时间之和 / 作业数
   • 带权周转时间 = 作业周转时间 / 作业实际运行的时间 = （作业完成时间 - 作业提交时间）/ 作业实际运行的时间
   • 平均带权周转时间：各作业带权周转时间之和 / 作业数

2.10 六种进程调度算法

1. 先来先服务（FCFS，First Come First Service）：非抢占式调度算法，不会导致饥饿现象（某进程/作业长期得不到服务）

   • 优点：公平、算法实现简单
   • 缺点：对长作业有利，短作业不利（等待很长时间而执行时间很短）

2. 短作业优先（SJF，Shortest Job First）：存在抢占式和非抢占式会，产生饥饿现象

   • 非抢占式短作业优先
     • 优点：“最短的” 平均等待时间、平均周转时间
     • 缺点：对短作业有利，长作业不利，可能产生饥饿现象（短作业源源不断地到来）
   • 抢占式短作业优先（最短剩余时间优先）：每当有 进程加入 就绪队列或当前 进程已完成 时就需要调度，如果新到达的进程的剩余时间比当前运行的进程的剩余时间更短，则由新进程抢占处理器，当前进程重新回到就绪队列

3. 高响应比优先（HRRN，Highest Response Ratio Next）：非抢占式的调度算法，会产生饥饿现象

   • 只有当前运行的进程主动放弃 CPU 时才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程运行
   • 响应比 = （等待时间 + 要求服务时间）/ 要求服务时间

4. 时间片轮转（Round-Robin）：抢占式调度算法，不会产生饥饿问题

   • 时间片选择：如时间片过大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务算法，并且会增大进程被处理机响应的时间（等待较长时间），因而时间片的选择不能太大。时间片的选择也不应过小，因为频繁地切换进程会耗费过多的处理时间。一般来说，时间片的选择要让切换进程的开销占比不超过 1%

5. 优先级：抢占式调度算法，会导致饥饿问题（高优先级的进程/作业源源不断到来）

   • 系统进程优先级高于用户进程
   • 前台进程优先级高于后台进程（给用户以友好体验）
   • 操作系统更偏好 I/O 型进程（I/O 型进程可与 CPU 并行执行）

6. 多级反馈队列：抢占式调度算法，会导致饥饿问题

   • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
   • 新进程到达时先进入 第 1 级 队列，按 FCFS 原则排队等待被分配时间片，若用完时间片但进程还未结束，则进程进入下一级队列队尾（若已经是最下级队列，则重新放入该队列队尾）
   • 只有 第 k 级 队列为空时，才会为 k+1 级队头的进程分配时间片
   • 在第 k 级队列中的进程运行时，若更高级的 （1 ~ k-1）队列中进入了新进程，则原来运行的进程放回 k 级队列队尾，转而执行优先级更高的进程

2.11 进程同步与互斥

1. 同步：亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的 工作次序 而产生的制约关系
2. 实现进程互斥需要遵循的原则：
   • 空闲让进
   • 忙则等待
   • 有限等待
   • 让权等待：当进程不能进入临界区时，应立即释放处理机

2.12 进程互斥的三种软件实现方法

1. 单标志法：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
   • 缺点：不遵循空闲让进原则
2. 双标志检查法：设置一个布尔数组 boolean flag[];，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = true” 意味着 0 号进程想要进入临界区。细分为双标志先检查法和双标志后检查法：区别在于前者 “检查后上锁”，后者 “上锁后检查”
   • 缺点：双标志先检查法不遵循忙则等待原则；双标志后检查法不遵循空闲让进、有限等待原则并可能导致饥饿问题
3. Peterson 算法：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson 想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试 “孔融让梨”，主动让对方先使用临界区
   • 缺点：不遵循让权等待原则并可能会导致处理机 “忙等”

2.13 进程互斥的三种硬件实现方法

1. 中断屏蔽方法：利用 “开/关中断指令” 实现，即在某进程开始访问临界区到结束访问为止都不允许被中断，也即不能发生进程切换

   • 优点：简单、高效
   • 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程

2. TestAndSet（TS）或 TestAndSetLock（TSL）指令：使用硬件实现，执行的过程不允许被中断，只能一气呵成（原子操作）

   • 优点：实现简单，无需像软件实现方法那样严格检查是否存在逻辑漏洞；适用于多处理机环境
   • 缺点：不满足 “让权等待” 原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令从而导致 “忙等”

3. Swap 指令：也称 Exchange（XCHG） 指令。使用硬件的方式实现，执行过程不允许被中断，只能一气呵成。优缺点同 TSL 方式一致

2.14 信号量机制

1. 定义：信号量其实就是一个变量（可以是一个整数或是更复杂的记录型变量），可以用一个信号量来标识系统中某种资源的数量

2. 一对原语：wait(W) 和 signal(S) 常简称为 P、V 操作

   • P：proberen，荷兰语，有 test 的意思，即尝试消费一个信号量
   • V：verhogen，荷兰语，有 increase 的意思，即增加、释放一个信号量

3. 记录型信号量：

   // 信号量定义
   typedef struct {
       int value;			// 剩余资源数
       struct process *L;	// 等待队列
   } semaphore;
   1
   2
   3
   4
   5

   // wite 原语申请资源，P 操作
   void wait (semaphore S) {
       S.value--;
       if (S.value < 0) {
           // 当前线程阻塞并挂到 S 等待队列队尾
           block(S.L);
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8

   // singal 原语释放资源，V 操作
   void signal(semaphore S) {
       S.value++;
       // singal 释放资源后 S.value 仍小于 0，说明仍然存在等待资源的进程在阻塞，则唤醒它
       if (S.value <= 0) {
           // 存在可用资源且等待队列中存在阻塞线程，唤醒队头线程
           wakeup(S.L);
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9

4. 信号量机制实现互斥：

   • 分析并发进程的关键活动，划定临界区
   • 设置互斥信号量 mutex，初值为 1
   • 在临界区之前执行 P(mutex)
   • 在临界区之后执行 V(mutext)

5. 信号量实现进程同步：

   • 分析什么地方需要实现 “同步关系”，即需要保证 “一前一后” 执行的操作
   • 设置同步信号量 S，初值为 0
   • 在 “前操作” 之后执行 V(S)
   • 在 “后操作” 之前执行 P(S)

6. 信号量机制实现前驱关系：

   • 分析问题，画出前驱图，把每一对前驱关系都看作一个同步问题
   • 为每一对前驱关系设置同步信号量，初值为 0
   • 在 “前操作” 之后执行 V(S)
   • 在 “后操作” 之前执行 P(S)

2.15 信号量机制之生产者 - 消费者问题

生产者、消费者共享一个初始为空、大小为 n 的缓冲区

只有缓冲区未满时，生产者才能将产品放入缓冲区，否则阻塞等待

只有缓冲区非空时，消费者才能从缓冲区消费产品，否则阻塞等待

缓冲区是临界资源，各进程必须互斥地访问

信号量定义：

semaphore mutex = 1;	// 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;	// 同步信号量，表示空闲缓冲区的数量
semaphore full = 0;		// 同步信号量，表示非空缓冲区的数量
1
2
3

生产者：

producer() {
    while (1) {
        生产一个产品;
        P(empty);	// 消耗一个空闲缓冲区
        P(mutex);	// 互斥访问缓冲区
        将产品放入缓冲区;
        V(mutex);	// 释放缓冲区
        V(full);	// 增加一个产品
    }
}
1
2
3
4
5
6
7
8
9
10

消费者：

consumer() {
    while (1) {
        P(full);	// 消耗一个非空缓冲区
        P(mutext);	// 互斥访问缓冲区
        从缓冲区取走一个产品;
        V(mutex);	// 释放缓冲区
        V(empty);	// 增加一个空闲缓冲区
        使用产品;
    }
}
1
2
3
4
5
6
7
8
9
10

注：实现互斥的 P 操作一定要放在实现同步的 P 操作之后，否则会产生死锁

2.16 信号量机制之多生产者 - 多消费者问题

桌子上有一个盘子，每次只能向其中放入一个水果

爸爸专向盘子中放入苹果，女儿专等着吃盘子中的苹果

妈妈专向盘子中放入橘子，儿子专等着吃盘子中的橘子

只有盘子为空时，爸爸或妈妈才能向盘子中放入一个水果

只有盘子中存在自己需要的水果时，儿子或女儿才能从盘子中取走自己需要的水果

信号量定义：

semaphore mutext = 1;	// 互斥信号量，互斥地访问盘子
semaphore plate = 1;	// 同步信号量，盘子可放的水果个数
semaphore apple = 0;	// 同步信号量，盘子中的苹果个数
semaphore orange = 0;	// 同步信号量，盘子中的橘子个数
1
2
3
4

爸爸：

dad() {
    while (1) {
        准备一个苹果;
        P(plate);
        P(mutex);
        将苹果放入盘子;
        V(mutex);
        V(apple);
    }
}
1
2
3
4
5
6
7
8
9
10

妈妈：

mom() {
    while (1) {
        准备一个橘子;
        P(plate);
        P(mutex);
        将橘子放入盘子;
        V(mutex);
        V(orange);
    }
}
1
2
3
4
5
6
7
8
9
10

女儿：

daughter() {
    while (1) {
        P(apple);
        P(mutex);
        从盘子中取出苹果;
        V(mutex);
        V(plate);
        吃掉苹果;
    }
}
1
2
3
4
5
6
7
8
9
10

儿子：

son() {
    while (1) {
        P(orange);
        P(mutex);
        从盘子中取走橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}
1
2
3
4
5
6
7
8
9
10

注：实现互斥的 P 操作一定要放在实现同步的 P 操作之后，否则会产生死锁

2.17 信号量机制之吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程

香烟由三种材料组成：烟草、纸、胶水，每个抽烟者不停地卷烟并抽掉

三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水

供应者每次将两种材料放在桌上，拥有剩余那种材料的抽烟者拿走桌上的材料后卷起香烟抽掉，并通知供应者完成了

供应者接着便会在桌上放入另外两种材料，如此往复从而实现让三个抽烟者轮流抽烟

信号量定义：

semaphore offer1 = 0;	// 同步信号量，桌上材料组合一的数量
semaphore offer2 = 0;	// 同步信号量，桌上材料组合二的数量
semaphore offer3 = 0;	// 同步信号量，桌上材料组合三的数量
semaphore finish = 0;	// 抽烟是否完成
int i = 0;				// 用于实现抽烟者轮流抽烟
1
2
3
4
5

供应者：

provider() {
    while (1) {
        if (i == 0) {
            将组合一放在桌上;
            V(offer1);
        } else if (i == 1) {
            将组合二放在桌上;
            V(offer2);
        } else if (i == 2) {
            将组合三放在桌上;
            V(offer3);
        }
        i = (i + 1) % 3;
        P(finish);	// 等待来自吸烟者的完成信号
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

吸烟者：

smoker1() {
    while (1) {
        P(offer1);
        从桌上拿走组合一;
        卷烟;
        抽掉;
        V(finish);
    }
}

smoker2() {
    while (1) {
        P(offer2);
        从桌上拿走组合二;
        卷烟;
        抽掉;
        V(finish);
    }
}

smoker3() {
    while (1) {
        P(offer3);
        从桌上拿走组合三;
        卷烟;
        抽掉;
        V(finish);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注：缓冲区大小为 1，同一时刻 4 个同步信号量中至多有一个值为 1，不会被 P 操作阻塞，因而无需设置专门的互斥信号量实现对缓冲区的互斥访问

2.18 信号量机制之读者 - 写者问题

有读者和写者两组并发进程共享一个文件

当两个及以上读进程同时访问共享数据时不会导致数据不一致的问题

当某个写进程和其它进程同时访问共享数据则可能导致数据不一致的错误。因此要求：

1. 允许多个读者同时对文件执行读操作
2. 同一时刻只允许一个写者往文件中写入信息
3. 任一写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的读者和写者全部退出

信号量定义：

semaphore rw = 1;		// 用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件
int count = 0;			// 用于记录当前有几个进程在访问共享文件
semaphore mutext = 1;	// 用于保证对 count 变量的互斥访问
semaphore w = 1; 		// 用于实现 “写优先”，保证写进程不会饿死
1
2
3
4

写者：

writer() {
    while (1) {
        P(w);
        P(rw);		// 写之前加锁
        写文件;
        V(rw);		// 写之后解锁
        V(w);
    }
}
1
2
3
4
5
6
7
8
9

读者：

reader() {
    while (1) {
        P(w);
        P(mutex);		// 各都进程间互斥访问 count
        if (count == 0) {
            P(rw);		// 第一个读进程负责 “加锁”
        }
        count++;
        V(mutex);
        V(w);
        
        读文件;
        
        P(mutex);
        count--;
        if (count == 0) {
            V(rw);	// 最后一个读进程负责 “解锁”
        }
        V(mutex);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.19 信号量机制之哲学家进餐问题

一张圆桌上坐着 5 位哲学家，每两个哲学家之间摆一根筷子，桌子中间是一碗米饭

哲学家们倾注毕生的经历用于思考和进餐，哲学家在思考时，并不影响其他人

只有当哲学家饥饿时，才试图拿起左、右两个筷子（一根一根地拿起），如果筷子已经在他人手中则等待

饥饿的哲学家只有成功拿到两根筷子时才可以开始进餐，进餐完毕后继续思考

如何避免死锁现象的发生呢？

1. 最多允许四个哲学家拿筷子，这样就可以保证至少有一个哲学家可以拿到两根筷子从而进餐
2. 要求奇数号哲学家先拿左边，再拿右边筷子，偶数号哲学家则相反
3. 使用互斥信号量

// 信号量定义
semaphore chopsticks[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

Pi() {
    while (1) {
        P(mutex);
        P(chopsticks[i]);				// 拿左
        P(chopsticks[(i + 1) % 5]);		// 拿右
        V(mutex);
        
        吃饭;
        
        V(chopsticks[i]);				// 放左
        V(chopsticks[(i + 1) % 5]);		// 放右
        思考;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.20 管程

1. 为什么要引入管程：解决信号量机制编程麻烦、易出错的问题

2. 管程是一种特殊的软件模块（类比 类），由以下部分组成：

   • 局部于管程的共享数据结构说明（类字段）
   • 对该数据结构进行操作的一组过程（类方法）
   • 对局部于管程的共享数据设置初始值的语句（构造器、代码块）
   • 管程有一个名字（类名）

3. 管程的基本特征：

   • 局部于管程的数据只能被局部于管程的过程所访问（封装）
   • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据（通过类提供的方法访问类字段）
   • 每次仅允许一个进程在管程内执行某个内部过程（互斥）

4. 管程的补充说明：

   • 各进程必须互斥访问管程的特性是由 编译器 实现的
   • 可在管程中 设置条件变量 及 等待/唤醒 操作以解决同步问题

2.21 死锁

1. 死锁、饥饿与死循环：

   • 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞而无法向前推进的现象
   • 饥饿：由于长期得不到想要的资源而导致进程无法向前推进的现象
   • 死循环：某进程执行过程中一直跳不出某个循环的现象

2. 产生死锁必须满足的四个条件：

   • 互斥条件：只有对需要互斥使用的资源的争夺才会发生死锁
   • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放
   • 请求和保持条件：进程已经保持了至少一个资源并持有不放，但又提出了新的资源请求，而该资源被其它进程占有，此时请求进程将被阻塞
   • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求（循环等待未必死锁，死锁一定有循环等待）

3. 死锁的发生时机：

   • 对不可剥夺资源的竞争
   • 进程推进顺序不合理
   • 信号量使用不当

4. 死锁的处理：

   • 预防死锁
   • 避免死锁
   • 检测和解除

2.22 死锁处理之预防死锁

1. 破坏互斥条件（SPOOLing 技术）：把只能互斥使用的资源改造为允许共享使用
   • 缺点：可行性不高，很多时候无法破坏互斥条件
2. 破坏不剥夺条件：进程请求新资源得不到满足时则立即释放保持的所有资源，过后再重新申请
   • 缺点：实现复杂、剥夺资源可能导致部分进程服务正常工作、反复申请和释放资源系统开销大、可能导致饥饿
3. 破坏请求和保持条件：采取 静态分配方法，进程在运行前一次性申请完它所需的全部资源
   • 缺点：资源利用率低、可能导致饥饿
4. 破坏循环等待条件：采用 顺序资源分配法，给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次性申请完
   • 缺点：不方便增加新设备、会导致资源浪费、用户编程麻烦

2.23 死锁处理之避免死锁（银行家算法）

1. 安全序列：所谓安全序列，是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就处于安全状态，否则系统就进入了不安全状态

2. 使用银行家算法避免死锁：

   • 银行家算法数据结构：

     public class Banker {
         // 各种可用资源数量
         int[] available = new int[m];
         // 各进程对资源的最大需求数
         int[][] max = new int[n][m];
         // 已经给个进程分配的资源
         int[][] allocatI/On = new int[n][m];
         // 各进程最多还需要的资源数（max - allocatI/On）
         int[][] need = new int[n][m];
         // 进程此次申请的各种资源数
         int[] request = new int[m];
     }
     1
     2
     3
     4
     5
     6
     7
     8
     9
     10
     11
     12

   • 银行家算法步骤：

     • 检查此次申请是否超过了之前声明的最大需求数
     • 检查系统可用资源数是否能满足此次申请
     • 试探着分配，改变各种数据结构
     • 用 安全性算法 检查此次分配是否会导致系统进入不安全状态

3. 安全性算法：检查当前剩余可用资源是否能满足某个进程的最大需求，如果可以就把该进程加入安全序列并将其持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都进入安全序列

2.24 死锁处理之检测和解除

1. 死锁的检测：

   • 用某种数据结构（资源分配图）来保存资源的请求和分配信息

   • 提供一种算法，利用上述信息来检测系统是否已进入死锁状态（依次消除与不阻塞进程相连的边，直到无边可消）

     资源分配图：包含两种节点和两种边

     • 进程节点（P1、P2）：对应一个进程
     • 资源节点（R1、R2）：对应一类资源，包含多个资源
     • 进程节点 -> 资源节点：表示进程想要申请几个资源（每条边代表一个）
     • 资源节点 -> 进程节点：表示已经为进程分配了几个资源（每条边代表一个）

     

2. 死锁的解除：

   • 资源剥夺法：挂起某些死锁进程并抢占它的资源，将这些资源分配给其它的死锁进程。应防止被挂起的进程长时间得不到资源而导致饥饿
   • 终止进程法：强制撤销部分、甚至是全部死锁进程，并剥夺这些进程的资源
   • 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步，这要求操作系统记录进程的历史信息，设置还原点

三、内存管理

3.1 内存管理概述

1. 程序的编译运行步骤：

   1. 编译：由编译程序将用户源代码编译成若干个 目标模块（高级语言翻译为机器语言）
   2. 链接：由链接程序将编译后的一组 目标模块 以及所需 库函数 链接在一起，形成一个完整的 装入模块
   3. 装载：由装入程序将装入模块装入内存运行

   

2. 三种链接方式：静态链接、装入时动态链接、运行时动态链接

3. 模块装入的三种方式：即使用三种不同的方法完成逻辑地址到物理地址的转换

   • 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址将程序和数据装入内存
   • 静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从 0 开始，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。装入程序可根据当前的内存情况，将装入模块装入到内存的适当位置，装入时对地址进行重定位，将逻辑地址转换为物理地址
     • 特点：在一个作业装入内存时，必须分配其所要求的全部内存空间大小，若内存不足则作业不能装入。作业一旦装入成功后，在运行期间就不能再移动，也不能再申请内存空间
   • 动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从 0 开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因而装入内存后所有的地址依然是逻辑地址，这种方式需要一个 重定位寄存器 的支持

4. 内存管理需要实现的功能：

   • 内存空间的分配与回收

   • 内存空间的扩充：操作系统需要提供某种技术从逻辑上对内存空间进行扩充

   • 地址转换：操作系统需要提供地址转换功能，负责将程序的逻辑地址转换为物理地址（绝对装入、静态重定位、动态重定位）

   • 存储保护：操作系统需要提供内存保护功能，保证个进程在各自存储空间内运行，互不干扰。具体实现方式分以下两种：

     • 上、下限寄存器
     • 重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。基址寄存器存放的是进程的 起始物理地址，限长寄存器存放的是进程的 最大逻辑地址

   

3.2 内存空间扩充之覆盖与交换技术

1. 覆盖技术：用来解决 “程序大小超过物理内存总和” 的问题，思想是将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个 “固定区” 和若干个 “覆盖区”

2. 交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存（进程挂起），把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

   

   在具有交换功能的操作系统中，通常将磁盘空间划分为 文件区 和 对换区 两部分

   • 文件区：用于存放文件，主要追求存储空间的利用率，采用 离散分配 方式
   • 对换区：占磁盘空间的一小部分，存放换出的进程数据，追求换入换出速度，采用 连续分配 方式

3.3 内存分配与回收之连续分配管理方式

1. 单一连续分配：内存被分为 系统区 和 用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据

   • 优点：实现简单、无外部碎片（内存中的某些空闲分区由于太小而难以利用 ）、可以采用覆盖技术扩充内存、不一定需要采取内存保护
   • 缺点：只能用于单用户、单任务的操作系统中，有内部碎片（分配给某进程的内存区域中，未利用上的内存空间），存储器利用率极低

2. 固定分区分配：将整个用户空间划分为多干个的分区，每个分区中只能装入一道作业。操作系统需要建立一个数据结构（分区说明表）来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态

   • 优点：实现简单、无外部碎片
   • 缺点：用户程序过大时导致无分区可用，此时不得不采用覆盖技术扩充内存，降低了程序性能；会产生内部碎片，内存利用率低

3. 动态分区分配：也称可变分区分配。不需要预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的。操作系统需要采用 空闲分区表 或 空闲分区链 的数据结构来记录分区的使用情况

   • 优点：无内部碎片
   • 缺点：有外部碎片

4. 动态分区分配算法：

   • 首次适应算法（First Fit）：空闲分区以 地址递增 的次序排列，每次分配内存都从低地址开始查找

   • 邻近适应算法（Next Fit）：空闲分区以 地址递增 的次序排列（可排成循环链表），每次分配从上次结束的位置开始查找

   • 最佳适应算法（Best Fit）：空闲分区按 容量递增 的次序链接。每次分配内存时顺序查找空闲分区表（或空闲分区链）

   • 最坏适应算法（Worst Fit）：空闲分区按 容量递减 次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表）
     | 算法 | 思想 | 分区排列顺序 | 优点 | 缺点 |
     | :------- | :------------------------------------------- | :----------- | :----------------- | :----------------------- |
     | 首次适应 | 从头到尾查找合适的分区 | 地址递增 | 性能好、算法开销小 | |
     | 邻近适应 | 由最佳适应演变而来，每次从上次结束的位置查找 | 地址递增 | 算法开销小 | 高地址的大分区被用完 |
     | 最佳适应 | 优先使用更小的分区以保留更多大的分区 | 容量递增 | 保留更多的大分区 | 外部碎片多、算法开销大 |
     | 最坏适应 | 优先使用更大的分区以产生太多小的外部碎片 | 容量递减 | 减少了外部碎片 | 不利于大进程、算法开销大 |

3.4 基本分页存储管理的基本概念

1. 页框：也称页帧、内存块、物理块。将 内存空间 分为一个个大小相等的分区（4KB/分区），每个分区就是一个 “页框”。每个页框有一个 “页框号”，也称页帧号、内存块号、物理块号。页框号由低地址向高地址从 0 开始编号

2. 页：也称页面。将 用户进程的地址空间` 分为与页框大小相等的一个个区域即为页。每个页有一个 “页号”，页号从 0 开始编号。操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中。换言之，进程的页面与内存空间的页框有着一一对应的关系

3. 基本分页存储管理如何实现逻辑地址到物理地址的转换：

   • 计算逻辑地址对应的页号：页号 = 逻辑地址 / 页面大小
   • 知道该页号对应页面在内存中的起始物理地址
   • 计算逻辑地址的页内偏移量：偏移量 = 逻辑地址 % 页面大小
   • 物理地址 = 页面起始地址 + 页内偏移量

   如果让每个页面的大小为 2 的整数幂，计算机可以很方便地得出一个逻辑地址对应页号和页内偏移量。每个页面大小为 2^kB，用二进制数表示逻辑地址：则末尾 k 位即为页内偏移量，其余部分为页号

   如果有 K 位表示 “页内偏移量”，则说明系统中一个页面的大小是 2^K 个内存单元

   如果有 M 位标识 “页号”，则说明系统中一个进程最多允许有 2^M 个页面

   

4. 页表：操作系统需要为每个进程建立一张页表用于记录进程页面与实际存放的内存块之间的对应关系

   • 一个进程对应一张页表
   • 进程每一页对应一个页表项
   • 每个页表项由 “页号” 和 “块号” 组成
   • 每个页的大小是相同的，实际上页表中页号是 “隐含的”

   

3.5 基本分页存储管理之地址转换

通常会在系统中设置一个 页表寄存器（PTR）存放页表在内存中的起始地址 F 和页面长度 M。进程未执行时，页面的始址和页面长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把他们放到页表寄存器中

设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下；

1. 计算页号 P 和页内偏移量 W
2. 比较页号 P 和页面长度 M，若 P >= M 则抛出越界中断，否则继续执行
3. 计算页号 P 对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度，根据页表项地址取出内存块号 b
   • 页表长度：页表中总共有几个页表项，即总共有多少页
   • 页表项长度：每个页表项占用多大的存储空间
   • 页面大小：一个页面占用多大的存储空间
4. 物理地址 E = 内存块号b * 页面大小L + 页内偏移量W

3.6 基本分页存储管理之快表地址变换

1. 两个局部性原理说明：

   • 时间局部性原理：如果执行了程序中的某条指令，那么不久后这条指令很可能会被再次执行；如果某个数据被访问过，那么不久后该数据很可能会被再次访问

   • 空间局部性原理：一旦程序访问了某个存储单元，在不久之后其附近的单元也很有可能被访问

2. 快表：又称为 联想寄存器（TLB），是一种访问速度比内存快很多的 高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。具有快表的地址变换机制如下：

   • 计算页号、页内偏移量
   • 检查页号合法性
   • 查快表。若命中，则可知道页面存放的内存块号，直接进行步骤 5；若未命中则进行 4
   • 查页表。找到页面存放的内存块号，并将该页表项复制到快表中
   • 根据内存块号和页内偏移量得到物理地址
   • 访问目标内存单元

3.7 基本分页存储管理之两级页表地址转换

1. 单级页表存在的问题：

   • 页表必须连续存放，当页表很大时，需要占用许多个连续的页框

   • 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面就可运行

2. 分级页表：将长长的页表进行分组，使每个内存块刚好可以放入一个分组。分组后需要为离散分配的页表项分组再建立一张页表，称为页目录表，或称外层页表、顶层页表

3. 两级页表结构如何实现逻辑地址到物理地址的转换：

   • 按照地址结构将逻辑地址拆分为三部分【一级页号，二级页号，页内偏移量】

   • 从 PCB 中读出页目录表起始地址，再根据一级页号查页目录表，找到二级页表在内存中的存放位置

   • 根据二级页号查页表，找到最终想访问的内存块号

   • 结合页内偏移量得到物理地址

   例如：将逻辑地址（0000000000，0000000001，111111111111）转化为物理地址（使用十进制表示）

   • 将逻辑地址划分为三级机构【一级页号，二级页号，页内偏移量】即【0，1，1023】
   • 查页目录表知 0# 页表存放在内存块号为 3 的内存块中，从中取出二级页表
   • 查二级页表，根据二级页号 1 知最终想访问的内存块号为 4
   • 结合页内偏移量 1023 得到最终的物理地址为 4 * 4096(4KB/块) + 1023 = 17407

   

4. 多级页表分级主要注意的小细节：

   • 多级页表中，各级页表的大小不能超过一个页面(4KB)。若两级页表不够，可以分更多级

   • 多级页表的访存次数：N 级页表访问一个逻辑地址需要 N+1 次访存（无快表机制）

3.8 基本分段存储管理方式

1. 进程的地址空间：按照程序自身的逻辑关系划分为若干段，每段都有一个段名（低级语言中程序员使用段名来编程），每段从 0 开始编址

2. 内存分配规则：以段为单位进行分配，每个段在内存中占据 连续 空间，各段之间可以不相邻

3. 分段系统的逻辑地址结构由 段号（段名）和 段内地址（段内偏移量）所组成

   • 段号的位数决定了每个进程最多可以分几个段
   • 段内地址位数决定了每个段的最大长度是多少

4. 段表：

   • 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 ”基址“）和段的长度
   • 每个段表项的长度是相同的

   

5. 分段与分页存储管理的对比：

   • 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，具体细节对用户不可见；段是信息的逻辑单位。分段的主要目的是为了更好地满足用户需求。一个端通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。分段比分页更容易实现信息的共享和保护
   • 页的大小固定且由操作系统决定；段的长度不固定，取决于用户编写的程序
   • 分页的用户进程地址空间是一维的，程序只需给出一个记忆符即可表示一个地址；分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

   	优点	缺点
   分页	内存空间利用率高，不会产生外部碎片，只有少量的内部碎片	不方便按照逻辑模块实现信息的共享和保护

| 分段 | 很方便按照逻辑模块实现信息的共享和保护 | 如果段长很大，为其分配很大的连续空间会很不方便，段式管理会产生外部碎片 |

3.9 段页式存储管理方式

1. 段页式管理：将程序按照逻辑模块分段，对各段进行分页（如 4KB/页），再将内存空间分为大小相同的页框（内存块），新建进程时将各页面分别装入各内存块中

   • 段号位数决定每个进程最多可以分为几个段；页号位数决定每个段最大有多少页；页内偏移量决定页面大小、内存块大小
   • 每个段对应一个段表项，段表项由段号、页表长度、页表存放块号（起始地址）组成。每个段表项长度相等，段号是隐含的
   • 每个页对应一个页表项，页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的

   

2. 段页式管理的地址转换：

   • 由逻辑地址得到段号、页号、页内偏移量
   • 段号与段表寄存器中的段长度比较，检查段号是否越界
   • 由段表始址、段号找到对应段表项
   • 根据段表项中记录的页表长度，检查页号是否越界
   • 由段表中的页表地址、页号查询页表，找到对应的页表项
   • 由页表项存放的内存块号、页内偏移量得到最终的物理地址
   • 访问目标单元

3.10 内存空间扩充之虚拟内存技术

1. 传统存储管理（连续分配与非连续分配）存在的问题：

   • 一次性：作业必须一次性全部装入内存后才能开始运行，这将导致作业过大时无法装入内存而不能运行；大量作业需要运行时无法容纳所有作业，导致只有少量作业能够运行，多道程序并发度下降
   • 驻留性：一旦作业被装入内存就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内只需要访问作业的一小部分数据就可以正常运行作业，这就导致了内存中会驻留大量的、暂时用不到的的数据，浪费了宝贵的内存资源

2. 虚拟内存的三个主要特征：

   • 多次性：作业运行时无需一次性全部装入内存，而是允许被划分为多次调入内存
   • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中将作业换入、换出
   • 虚拟性：从逻辑上扩充了内存的容量

3. 虚拟内存的容量：

   • 虚拟内存的 最大容量 是由计算机的地址结构（CPU 寻址范围）确定的
   • 虚拟内存的 实际容量 = min (内存和外存容量之和，CPU 寻址范围)

4. 虚拟内存的实现：请求分页存储管理、请求分段存储管理、请求段页式存储管理。操作系统需要提供请求调页和页面置换功能

5. 缺页中断：是因为当前执行的指令想要访问的目标页面未调入内存而产生的中断，因此属于内中断

3.11 四种页面置换算法

1. 最佳置换算法（OPT，Optimal）：每次选择淘汰的页面将是以后永不使用，或者在很长时间内不再被访问的页面，这样可以保证最低的缺页率

   • 特点：理想算法，无法实现

2. 先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面，将调入内存的页面按序排成队列，置换队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块

   • 特点：实现简单，但性能差，会产生 Belady 异常
   • Belady 异常：当为进程分配的内存块数增大时，缺页次数不减反增的异常现象

3. 最近最久未使用置换算法（LRU，Least Recently Used）：每次淘汰最近最久未使用的页面，在请求分页管理页表项中用访问字段记录该页面自上次被访问以来所经历的时间

   • 特点：需要硬件支持，开销大

4. 时钟置换算法：又称 CLOCK 算法或最近未用算法（NRU，Not Recently Used）

   • 简单 CLOCK 算法：为每个页面设置一个 访问位，再将内存中的页面通过链接指针链接成一个循环队列。当某页被访问时，访问位设置为 1。当需要一个淘汰页面时，检查页面的访问位，如果是 0 则将该页换出；如果是 1 则不换出，但需将访问位设置为 0，继续检查下一个页面。简单的 CLOCK 算法选择淘汰一个页面最多会经历两轮扫描（所有页面访问位均为 1）

   • 改进型时钟置换算法：除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面是否被修改过。在其它条件相同时，应优先淘汰没有被修改过的页面（无需 I/O 写入外存）。对页面引入 访问位 和 修改位 并将所有可能被置换的页面排成一个循环队列。

     1. 第一轮：扫描第一个（0，0）页面用于替换（未访问，未修改）
     2. 第二轮：扫描第一个（0，1）页面用于替换，将扫描过的页面访问位设置为 0
     3. 第三轮：扫描第一个（0，0）页面用于替换
     4. 第四轮：扫描第一个（0，1）页面用于替换

3.12 页面分配策略

1. 页面调入策略：

   • 预调页策略：这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分
   • 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存

2. 从何处调入页面；

   • 足够的对换区空间：内存 <-> 对换区，进程运行前需将相关数据从文件区拷贝到对换区
   • 缺失足够的对换区：不会被修改的数据直接从文件区调入，对于可能被修改的部分换出时写入磁盘对换区
   • UNIX 方式：进程运行前数据全部在文件区，第一次调用直接从充文件区调入，换出时从写入对换区，下次需要时直接从对换区调入

3. 抖动（颠簸）现象：刚刚换出的页面马上又要调入内存，刚刚调入的页面马上又要换出外存。主要原因是分配给进程的内存块不足

4. 驻留集与工作集：

   • 驻留集：指请求分页存储管理中给进程分配的内存块的集合
   • 工作集：指在某段时间间隔内，进程实际访问页面的集合。一般来说，驻留集的大小不能小于工作集大小，否则进程运行过程中将频繁缺页

四、文件管理

4.1 文件的逻辑结构

1. 无结构文件：文件内部的数据就是一系列二进制流或字符流，又称 “流式文件”

2. 有结构文件：由一组相似的记录组成，又称 “记录式文件”，每条记录由若干个数据项组成

   • 顺序文件：文件中的记录在逻辑上一个接一个地顺序排列，记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储
   • 索引文件：为逻辑文件建立一张索引表以加快文件检索速度，每条记录对应一个索引项
   • 索引顺序文件：同样会为文件建立一张索引表，与索引文件略显不同的是，索引顺序文件并不是每条记录对应一个索引表项，而是一组记录对应一个索引表项

   

4.2 文件目录

1. 文件控制块（FCB）：FCB 中包含了文件的基本信息、存取控制信息、使用信息等。一个 FCB 就是一个文件目录项，FCB 的有序集合称为 “文件目录”

2. 文件的目录结构：

   • 单级目录结构：整个系统只建立一张目录表，每个文件占一个目录项。单级目录结构要求文件不能重名

   • 两级目录结构：分为主文件目录（Master File Directory）和用户文件目录（User File Directory）。允许不同用户的文件重名，实现了文件访问权限控制。两级目录结构用户不能对文件进行分类管理

   • 树形目录结构：不便于实现文件的共享

   • 无环图目录结构：在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以很方便地实现多个用户间的文件共享。需为共享节点设置一个共享计数器，计数器为 0 时才真正删除该节点

3. 索引结点：除文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点。目录项中只包含文件名、索引结点指针，因而每个目录项的长度大幅减小。由于目录项长度减小，每个磁盘块可以存放更多个目录项，因此检索文件时磁盘 I/O 次数就减少了很多

4.3 文件的物理结构（分配方式）

类似于内存分页，磁盘中的存储单元也会被划分为一个个 “块/磁盘块/物理块”。许多操作系统中将磁盘块的大小设为内存块（页帧）、页面（页）的大小

1. 连续分配：要求每个文件在磁盘上占有一组连续的块，并且文件目录的 FCB 中需记录文件的起始块号和块长度

   • 优点：支持顺序访问和随机访问，I/O 速度块（块距小，磁头移动时间短）
   • 缺点：物理上采用连续分配的文件不方便扩展，易产生磁盘碎片、空间利用率低

   

2. 链接分配：

   • 隐式链接分配方式：文件目录的 FCB 中记录文件存放的起始块号号结束块号，每个磁盘块中都会保存指向下一盘块的指针

     

   • 显式链接分配方式：把用于连接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File AllocatI/On Table）。一个磁盘只会建立一张文件分配表，开机时文件分配表载入内存后常驻内存

     • 优点：很方便文件扩展、不会产生碎片问题、外存利用率高、支持随机访问、对比隐式链接方式地址转换时不需要访问磁盘，因而文件的访问效率更高
     • 缺点：文件分配表（FAT）需要占用一定的内存空间

     

3. 索引分配：文件离散地分配在各磁盘块中，系统会为每个文件建立一张 索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块

   

4. 文件太大，索引表项 过多的解决方案：

   • 链接方案：如果索引表过大，一个索引块装不下，那么可以将多个索引块链接起来存放
     • 缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来，想要找到 i 号索引块必须先依次读入 0 ~ i-1 号索引块，磁盘 I/O 次数过多，查找效率低
   • 多层索引：建立多层索引（类似于多级页表），使第一层索引块指向第二层的索引块，还可根据文件大小再建立第三层、第四层索引块。采用 K 层索引结构，且顶级索引表为调入内存，则访问一个数据块只需要 K+1 次磁盘 I/O 操作
     • 缺点：即使是小文件，访问一个数据块依然需要 K+1 次 I/O
   • 混合索引：多层索引分配方式的优化。例如，一个文件的顶级索引表中，既包含直接地址索引又包含一级简介索引、还包含两级间接索引。对于小文件来说，访问一个数据块所需的 I/O 次数减少

4.4 文件存储空间管理

1. 磁盘空间的划分与初始化：将物理磁盘划分一个个的文件卷，又称逻辑卷或逻辑盘（C 盘、D 盘）。文件卷包含了目录区和文件区两部分：

   • 目录区：存放文件目录信息（FCB）、磁盘空间管理信息等
   • 文件区：存放文件数据

2. 对空闲磁盘块的管理：

   • 空闲表法：记录第一个空闲盘的块号和空闲盘块数，适用于连续分配方式

   • 空闲链表法：

     • 空闲盘块链：空闲表中存储着下一个空闲块的指针
     • 空闲盘区链：空闲盘区（连续的空闲盘块组成区）中的第一个盘块内记录了盘区的长度以及指向下一空闲盘区的指针

   • 位示图法：每个二进制位对应一个盘块。使用 0 代表盘块空闲，1 代表盘块已分配。位示图一般用连续的 “字” 来表示，字 中的每一位对应一个盘块

     

   • 成组链接法：文件卷的目录区中专门用一个磁盘块作为 “超级块”，当系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致。超级块中记录了下一组空闲盘块的数量以及空闲块号，依据此空闲盘块号可找到下一个 “超级块”，依次类推

4.5 文件的基本操作

1. 创建文件（create 系统调用）：在外存中找到文件所需的空间、创建该文件所对应的目录项
2. 删除文件（delete 系统调用）：找到文件名对应的目录项、回收文件占用的磁盘块、删除文件对应的目录项
3. 修改文件（write 系统调用）：提供文件在打开文件表中的索引号、指明要修改多少数据以及数据放在内存中的什么位置
4. 读取文件（read 系统调用）：提供文件在打开文件表中的索引号、指明需要读入的数据量以及存放的内存位置
5. 打开文件（open 系统调用）：找到文件名对应的目录项并检查该用户的操作权限、将目录项复制到内存的 “打开文件表” 并将对应表目的编号返回给用户
6. 关闭文件（close 系统调用）：将进程的打开文件表相应表项删除、回收分配给该文件的内存空间等资源、系统打开文件表的 打开计数器 count–，若 count == 0 则删除对应表项

4.6 文件的共享与保护

1. 文件共享的两种方式：

   • 基于索引结点的共享方式（硬链接）：将除文件名之外的其它信息放到索引节点中，目录项只需要存储文件名和指向索引节点的指针。索引结点中需设置一个链接计数变量 count，用于表示链接到本索引节点上的用户目录项的数量
   • 基于符号链的共享方式（软链接）：Link 类型文件，类似于 Windows 中的快捷方式

2. 文件保护的三种方式：

   • 口令保护：口令一般存放在文件对应的 FCB 或索引节点中
   • 加密保护：对原始二进制数据进行加密
   • 访问控制：在每个文件的 FCB（或索引结点）中增加一个访问控制列表（Access-Control List，ACL），该表中记录了各个用户可以对文件执行的操作

4.7 文件系统的层次结构

1. 用户接口：向上层的用户或应用程序提供一些简单易用的功能接口。如 open, read, write, close 等系统调用
2. 文件目录系统：用户通过文件路径来访问文件，因而文件目录系统需要根据用户给出的路径找到对应的 FCB 或索引结点
3. 存取控制模块：验证用户是否具有相关文件操作权限，提供文件保护相关功能
4. 逻辑文件系统与文件信息缓冲区：用户指明想要访问的文件记录号，需要将记录号转换为对应的逻辑地址
5. 物理文件系统：需要将上一层提供的文件逻辑地址转换为实际的物理地址
6. 辅助分配模块：负责文件存储空间的管理，即负责分配和回收存储空间
7. 设备管理模块：直接与硬件交互，负责和硬件直接相关的一些管理工作，如分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等

4.8 磁盘结构

1. 磁盘的分类：

   • 活动头磁盘与固定头磁盘：根据磁头是否一块在盘面上移动进行划分
   • 可换盘磁盘与固定盘磁盘：根据盘片是否可以更换进行划分

2. 磁盘结构：

   • 磁盘：磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据
   • 磁道：磁盘的表面被划分为一个个磁道（同心圆）
   • 扇区：一个磁道又被划分为一个个扇区，每个扇区就是一个磁盘块，各个扇区存放的数据量相同
   • 盘面：磁盘面，一块磁盘可能有两个盘面（正反两面）
   • 柱面：所有盘面中相对位置相同的磁道组成柱面
   • 磁盘块的坐标表示：（柱面号，盘面号，扇区号）。为什么磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）：读取地址连续的磁盘块时，采用前者可以减少磁头更换磁道消耗的时间

   

4.9 六种磁盘调度算法

1. 先来先服务（FCFS）

2. 最短寻找优先（SSTF）：优先处理与当前磁头最近的磁道，保证每次寻道时间最短

   

3. 扫描算法（SCAN）：只有磁头移动到最外侧磁道时才能往内移动，移动到最内侧磁道时才能往外移动（电梯算法）

   

4. LOOK 调度算法：在 SCAN 算法的基础上，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向

   

5. 循环扫描算法（C-SCAN）：只有磁头朝某个特定方向移动时才处理磁道访问请求，返回时直接快速移动至起始端而不处理任何请求

   

6. C-LOOK 调度算法：在 C-SCAN 算法的基础上，如果磁头移动的方向上已经没有任何磁道访问请求，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可

   

4.10 磁盘时间

1. 一次磁盘 I/O 操作所需时间： T = T_S + 1/2r + b/(rN)

   • 寻道时间 T_S = s + m * n：在读写数据前，将磁头移动到指定磁道所花的时间
     • 启动磁头臂所需时间 s
     • 移动磁头所需时间：假设磁头匀速移动，每跨越一条磁道耗时 m，需跨越 n 条磁道，则磁头移动时间为 m*n
   • 延迟时间 T_R = (1/2) * (1/r) = 1/(2r)：通过旋转磁盘，使磁头定位到目标扇区所需时间。设磁盘转速为 r
   • 传输时间 T_t = (1/r) * (b/N) = b/(rN)：设磁盘转入为 r，此次 I/O 的字节数为 b，每个磁道上的字节数为 N

2. 减少磁盘延迟时间的方法：磁头读入一个扇区数据后需要一小段时间进行处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区可能需要很长的 “延迟时间”（需要盘片持续旋转）

   • 磁道交替编号：让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小
   • 盘面错位命名：让相邻盘面的扇区编号 “错位”，可以使读取连续的逻辑扇区所需要的延迟时间更小

4.11 磁盘管理

1. 磁盘的初始化：

   • 低级格式化：亦称物理格式化。将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域、尾三个部分。管理扇区所需要的各种数据结构一般存放在头、尾两个部分
   • 磁盘分区：每个分区由若干柱面组成（C盘、D盘）
   • 逻辑格式化：创建文件系统，包括创建文件系统的根目录、初始化存储空间管理所需的数据结构（如位示图、空闲分区表）等

2. 引导块：计算机开机时需要进行一系列初始化工作，这些初始化工作是通过执行初始化程序（自举程序）完成的。通常在只读存储器（ROM）中存放很小的 “自举程序”，完整的自举程序放在系统磁盘的 引导块 上，引导块位于磁盘的固定位置。开机时计算机先运行 ROM 中的 “自举程序”，通过执行该程序就可以找到引导块，并将完整的 “自举程序” 读入内存，完成系统初始化

五、设备管理

5.1 I/O 设备分类

5.2 I/O 控制器

1. I/O 控制器概念：CPU 无法直接控制 I/O 设备的机械部件，因此 I/O 设备还要有一个电子部件作为 CPU 与 I/O 设备机械部件之间的 ”中介“，用于实现 CPU 对设备的控制。这个电子部件就是 I/O 控制器，又称设备控制器

2. I/O 控制器的功能：

   • 接收和识别 CPU 发出的命令（控制寄存器）
   • 向 CPU 报告设备的状态（状态寄存器）
   • 数据交换（数据寄存器）
   • 地址识别

3. I/O 控制器的组成：

   • CPU 与控制器的接口
   • I/O 逻辑
   • 控制器与设备的接口

   

4. 对 I/O 设备寄存器的编址方式：

   • 内存映像 I/O：控制器中的寄存器与内存地址统一编码
   • 寄存器独立编址：控制器中的寄存器使用单独的地址

5.3 I/O 控制方式

1. 程序直接控制方式：CPU 首先向 I/O 控制器发出读指令，在 I/O 控制器的控制下 I/O 设备启动， I/O 控制器中状态寄存器的值设为 1（未就绪）；之后 CPU 轮询检查控制器的状态；输入设备将准备好的数据传给 I/O 控制器，并报告自身状态；控制器将输入数据放到数据寄存器中，并将状态寄存器的值修改为 0（已就绪）；CPU 轮询发现设备已就绪，将 I/O 控制器中数据寄存器中的内容读入自己的寄存器，而后再放入内存；若还要继续读入数据，则 CPU 继续发出读指令

   • CPU 干预频率：很频繁，I/O 操作开始之前、完成之后都需要 CPU 介入，并且在等待 I/O 完成的过程中需要不断地轮询检查
   • 数据传送单位：每次读/写一个字
   • 数据流向：I/O 设备 -> I/O 控制器数据寄存器 -> CPU 数据寄存器 -> 内存（读）
   • 优点：实现简单
   • 缺点：CPU 和 I/O 设备只能串行工作，CPU 需要轮询检查导致长期处于 “忙等” 状态，利用率低

2. 中断驱动方式：由于 I/O 设备速度很慢，因此在 CPU 发出读/写命令后，可将等待 I/O 的进程阻塞，切换运行别的进程。当 I/O 完成后，控制器会向 CPU 发出一个中断信号，CPU 在每一条指令完成后均会检测是否存在中断信号，若存在则会保存当前进程的运行环境，转而执行中断处理程序处理该中断。CPU 从 I/O 控制器的数据寄存器中读一个字的数据传送到 CPU 寄存器，而后再写入内存。接着 CPU 恢复等待 I/O 进程的运行环境，然后执行该进程

   • CPU 干预频率：每次 I/O 操作开始之前、完成之后需要 CPU 介入
   • 数据传送单位：每次读/写一个字
   • 数据流向：I/O 设备 -> I/O 控制器数据寄存器 -> CPU 数据寄存器 -> 内存（读）
   • 优点：CPU 和 I/O 设备可并行运行，利用率明显提升
   • 缺点：每个字在 I/O 设备和内存之间的传输都需要经过 CPU，频繁的中断处理耗费大量 CPU 时间

3. 直接存取控制方式：Direct Memory Access（DMA），主要用于块设备的 I/O 控制。数据传送的单位是 “块”，数据流向是从 I/O 控制器的数据寄存器直接流向内存，不再需要 CPU 的中介处理，仅在传送数据块的开始和结束时才需要 CPU 干预

   • CPU 干预频率：只在传送数据块的开始和结束需要 CPU 干预
   • 数据传送单位：每次读/写一个或多个块（读取多个块时只能是连续的多个块，并且在内存中的存放位置也必须是连续的）
   • 数据流向：I/O 设备 -> I/O 控制器数据寄存器 -> 内存（读），不再需要 CPU 充当 “快递小哥”
   • 优点：以 “块” 为单位进行数据传输，不再需要 CPU 的数据暂存，数据传输效率进一步提升，CPU 和 I/O 设备的并行性得到提升
   • 缺点：CPU 每发出一条 I/O 指令，只能读/写一个或多连续的数据块，并且只能写到连续的内存地址中

   

4. 通道控制方式：通道是一种硬件（“弱鸡版” CPU），可以识别并执行一系列的通道指令

   • CPU 干预频率：极低，通道会根据 CPU 指示执行相应的通道程序，只有完成一组数据块的读/写后才发出中断信号请求 CPU 干预
   • 数据读写单位：一组数据块
   • 数据流向：I/O 设备 -> 通道数据寄存器 -> 内存
   • 优点：CPU、通道、I/O 设备可并行工作，资源利用率很高
   • 缺点：实现复杂，需要专门的通道硬件支持

   

5.4 I/O 软件的层次结构

1. 用户层软件：实现与用户交互，用户可直接使用该层提供的与 I/O 操作相关的库函数对设备进行操作
2. 设备独立性软件：
   • 向上层提供统一的调用接口（如 read/write 系统调用）
   • 设备保护功能
   • 差错处理
   • 设备的分配与回收
   • 数据缓冲区管理：通过缓冲技术屏蔽设备之间数据交互单位大小和传输速度的差异
   • 设备名称转换：建立逻辑设备名到物理设备名之间的映射关系，根据设备类型选择调用相应的驱动程序。设备独立性软件需要通过 “逻辑设备表（LUT，Logical Unit Table）” 来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序

3. I/O 核心子系统：设备独立性软件、设备驱动程序、中断处理程序属于操作系统的内核部分即 I/O 系统，或称 I/O 核心子系统

5.5 用户层软件之假脱机技术

1. 假脱机技术：又称 “SPOOLing 技术”，是用软件的方式模拟脱机技术。SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。由以下几部分组成：

   • 输入井：模拟脱机输入时的磁带，用于收容 I/O 设备输入的数据
   • 输出井：模拟脱机输出时的磁带，用于收容用户进程输出的数据
   • 输入进程：模拟脱机输入时的外围控制机
   • 输出进程：模拟脱机输出时的外围控制机

   

2. 共享打印机原理分析：当多个用户进程提出打印的请求时，系统会答应它们的请求，但是并没有真正意义上把打印机分配给他们，而是由假脱机管理进程为每个进程服务：

   • 在磁盘输出井中为进程申请一个空闲缓冲区，并将要打印的数据送入其中
   • 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中，再将该表挂到假脱机文件队列上

5.6 设备独立性软件之设备的分配与回收

1. 设备分配时应考虑的因素：

   • 设备的固有属性：独占设备、共享设备、虚拟设备
   • 设备分配算法：先来先服务、短作业优先、优先级
   • 设备分配安全性：
     • 安全分配方式：为进程分配一个设备后就将其它进程阻塞，本次 I/O 完成后才将进程唤醒
     • 不安全分配方式：只有某个 I/O 请求得不到满足时才将进程阻塞

2. 设备分配的两种方式：

   • 静态分配：进程运行前为其分配所需的全部资源，运行结束后归还资源
   • 动态分配：进程运行过程中动态申请设备资源

3. 设备分配管理中的数据结构：

   • 设备控制表（Device Control Table）：设备类型、设备标识符、设备状态、指向控制器表的指针、重复执行次数或时间、设备队列的队首指针

   • 控制器控制表（COCT）：控制器标识符、控制器状态、指向通道表的指针、控制器队列的队首指针、控制器队列的队首指针

   • 通道控制表（CHCT）：通道标识符、通道状态、与通道连接的控制器表首址、通道队列的队首指针、通道队列的队尾指针

   • 系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目（设备类型、设备标识符、设备控制表、驱动程序入口）

   

4. 设备分配的步骤：

   • 根据进程请求的物理设备名查找 SDT
   • 根据 SDT 找到 DCT，若设备忙碌则将进程 PCB 挂到设备等待队列队尾
   • 根据 DCT 找到 COCT，若控制器忙碌则将进程 PCB 挂到控制器等待队列队尾
   • 根据 COCT 找到 CHCT，若通道忙碌则将进程 PCB 挂到通道等待队列队尾

   只有设备、控制器、通道三者都分配成功时才算本次设备分配成功，之后便可启动 I/O 设备进行数据传输。“设备、控制器、通道” 之间的关系：一个通道可控制多个设备控制器，每个设备控制器可控制多个设备

5.7 设备独立性软件之缓冲区管理

1. 缓冲区的作用：

   • 缓和 CPU 与 I/O 设备之间速度不匹配的矛盾
   • 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制
   • 解决数据粒度不匹配的问题
   • 提高 CPU 和 I/O 设备之间的并行性

2. 缓冲区管理的策略：

   • 单缓冲：操作系统在主存中分配一个缓冲区（非满不可取，非空不可放），一个缓冲区的大小就是一个内存块
   • 双缓冲：操作系统在主存中分配两个缓冲区， 一个缓冲区的大小就是一个块
   • 循环缓冲区：将多个大小相等的缓冲区链接成一个循环队列

3. 缓冲池：由系统中共用的缓冲区组成。这些缓冲区按使用状态可分为：

   • 空缓冲队列
   • 装满输入数据的缓冲队列（输入队列）
   • 装满输出数据的缓冲队列（输出队列）

   根据一个缓冲区在实际运算过程中扮演的功能不同，又设置了四种工作缓冲区：

   • 用于收容输入数据的缓冲区（hin）
   • 用于提取输入数据的缓冲区（sin）
   • 用于收容输出数据的缓冲区（hout）
   • 用于提取输出数据的缓冲区（sout）