《操作系统》课程笔记

一、导论

1. 计算机系统的组成部分

2. 操作系统的概念

操作系统(OS)也称内核(Kernel)，是一直运行在计算机上的程序。

四大特征：并发、共享、虚拟、异步

作用(系统视角)：

• 资源分配器：为各用户和进程分配资源，提高资源利用率
• 控制程序：控制各个进程的执行，确保系统稳定运行

功能：

1. 进程管理：创建、删除、挂起、重启进程；提供进程同步机制、进程通信机制、死锁处理机制
2. 内存管理：记录内存分配情况；决定哪些进程可以进入内存；提供内存分配和回收机制
3. 存储管理

3. 存储层次

寄存器(Register)、高速缓存(Cache)、内存(Memory)、磁盘(Disk)、硬盘、光盘、磁带

• 内存：CPU可直接访问的唯一大容量存储区域
• Cache：CPU-内存存储层次

属性：容量、速度、价格、易失性

4. 多道程序设计

多道程序设计(Multiprogramming)是操作系统最重要的特点，通过组织作业使CPU总有一个作业可以执行。

在内存中同时存放多个程序，使得CPU可以在一个程序等待I/O操作时，切换到另一个程序执行，从而提高CPU的利用率。

5. 双重模式和特权指令

双重模式：

为了区分操作系统代码和用户代码执行，至少需要两种模式：内核模式（又称管理模式、系统模式、特权模式）和用户模式，通过模式位（0/1）来区分。

当应用程序需要操作系统的服务时，必须从用户模式切换到内核模式。

特权指令(Privileged Instructions)：

只有在内核模式下才能执行的指令。

特权指令：切换到用户模式、I/O控制相关、访问特殊寄存器的指令、定时器管理、中断管理、内存管理（如改变内存分配图）、设置时钟日期等

易混淆的非特权指令：

• 访管指令：由用户程序发起的一种特殊指令，用于请求操作系统执行某些需要特殊权限才能访问的操作，会从内核模式切换到内核模式，将控制权交给操作系统内核执行相应操作，然后再返回用户模式
• 主机和磁盘间通过DMA传送数据的指令
• 改变磁盘空间分配图（区别于改变内存分配图）
• 写程序计数器PC、寄存器清0、取指令、取操作数、写内存

6. 定时器

定时器(Timer)确保操作系统维持对CPU的控制，防止用户程序：

1. 陷入死循环
2. 不调用系统服务，但不将控制返还给操作系统

操作系统在将控制权交给用户之前，应确保设置好定时器以便产生中断。

二、操作系统结构

1. 操作系统服务

1~6方便用户使用；7~9提高系统效率。

1. 用户界面(User Interface)：提供用户与操作系统交互的方式。
2. 程序执行：加载程序到内存并运行，能结束执行（不论是正常还是异常）
3. I/O操作：提供对I/O设备的访问和控制
4. 文件系统操作：创建、删除、读写文件和目录
5. 通信：提供进程间通信机制，如管道、消息队列、共享内存等
   • 方式：共享内存、消息交换
6. 错误检测：检测和处理错误，确保系统稳定运行
7. 资源分配：为各个进程分配CPU时间、内存空间、I/O设备等资源
8. 记账：记录资源使用类型和数量
9. 保护与安全：确保系统资源的安全性和完整性，防止未授权访问

2. 命令解释程序

命令解释程序(Command Interpreter)也被称为外壳(Shell)，用于获取并执行用户的下一条指令的程序/

• 命令行界面(Command Line Interface, CLI)
• 图形用户界面(Graphical User Interface, GUI)
• 批处理(Batch)

3. 系统调用类型

系统调用是操作系统提供给应用程序的唯一程序接口

类型：进程控制;文件管理;设备管理;信息维护;通信。

三、进程(Process)

1. 进程

进程是正在执行的程序的实例，包括：代码段、数据段、堆栈段、堆、进程控制块(PCB)。

进程控制块(PCB)

进程存在的唯一标识，包含：

• 进程状态(State)：新的、运行、等待、就绪、终止
• 程序计数器(Program Counter, PC)：指向下一条要执行的指令
• CPU寄存器(Registers)：保存进程执行时的寄存器状态
• CPU调度信息：进程优先级，调度队列指针等
• 内存管理信息：页表、段表、基地址等
• 记账信息、I/O信息

上下文切换

上下文切换：进程间切换的过程，保存当前进程的状态到PCB1中，并从PCB2中恢复下一个进程的状态。

2. 进程状态与转换

• 新的(new)：进程正在创建中
• 运行(running)：指令正在执行（一次只能有一个进程可在一个CPU上运行）
• 等待(waiting)：进程正在等待某个事件发生（如I/O操作完成、收到信号等）
• 就绪(ready)：进程已准备好运行，等待分配处理器
• 终止(terminated)：进程已完成执行

• 因时间片用完暂停：运行->就绪
• 因I/O操作暂停：运行->等待
• 进程打印结束：等待->就绪

3. 进程调度

调度队列：

• 作业队列：系统中的所有进程
• 就绪队列：处于就绪状态等待运行的进程
• 设备队列：等待特定I/O设备的进程

调度程序：

• 短期调度（CPU调度）：从队列中选择一个进程并为之分配CPU
  • 快速执行，频繁发生，通常每隔几毫秒
• 长期调度（作业调度）：从磁盘缓冲池中选择进程并将其加载到内存以便执行
  • 控制多道程序程度（内存中的进程数）
  • 选择进程：合理搭配CPU密集型和I/O密集型进程
• 中期调度：将进程从内存或CPU竞争中移出
  • 降低多道程序程度

4. 进程创建/终止

进程创建：fork()、vfork()、clone()等系统调用

• 创建新进程时，父进程的所有资源（代码、数据、堆栈）都被复制到子进程中
• 子进程fork()返回值为0，父进程返回子进程的PID
• 子进程拥有自己的PCB和独立的地址空间

进程终止：正常结束exit()；异常结束abort()

级联终止：当父进程终止时，所有子进程也会被终止

父进程等待：wait()系统调用

• 注意：exec()系列函数会用新程序替换当前进程的代码段、数据段和堆栈段，但保留PCB和进程ID，不会创建新进程。

5. 进程协作/通信

如果一个进程能影响其他进程或被其他进程影响，那么该进程就是协作的，否则就是独立的。

协作进程需要一种进程间通信机制（Inter-Process Communication, IPC）来交换信息，有2种基本方式：

• 共享内存：多个进程可以访问同一块内存区域
  • 快，仅在建立共享内存时需要系统调用
• 消息传递：通过发送和接收消息来交换信息
  • 交换少量数据时有用，无需避免冲突

生产者-消费者模型：

//生产者
while (true) {
    while(((in+1) % N) == out); //等待缓冲区有空位
    buffer[in] = produce_item(); //生产一个项目
    in = (in + 1) % N; //更新输入指针
}
// 消费者
while (true) {
    while (in == out); //等待缓冲区有项目
    consume_item(buffer[out]); //消费一个项目
    out = (out + 1) % N; //更新输出指针
}

四、线程(Thread)

1. 线程

线程是CPU处理的基本单位，由：线程ID、程序计数器、寄存器集合和栈组成

2. 线程与进程

进程是操作系统分配资源的基本单位，而线程是CPU处理的基本单位

同一进程 的 不同线程 之间共享代码段、数据段、文件等，私有寄存器和栈。

3. 多线程的优点

1. 响应度高：即使部分阻塞或执行冗长操作，仍然可以继续执行，增加对用户的响应程度
2. 资源共享：进程只能通过（共享内存、消息传递）等方式共享资源，而线程默认允许共享内存和资源
3. 经济：进程创建所需的内存和资源分配高，线程共享资源，创建和切换开销小
4. 可伸缩性：多线程程序可以更好地利用多核处理器的并行处理能力

4. 用户线程和内核线程

用户线程在内核之上支持，并通过用户级线程库来实现。
线程库提供对用户线程的创建、调度和管理的支持，而无需内核支持。

三种基本的用户级线程库：POSIX Pthreads、Win32 Threads、Java Threads。

内核由操作系统直接支持，内核在其空间内执行内核线程的创建、调度和管理。

实例：Windows XP/2000、Solaris、Linux等操作系统都支持内核线程。

多线程模型：用户线程和内核线程的映射关系（1:1、M:1、M:N）

五、进程调度

1. 基本概念

1.1 CPU-I/O执行周期

进程执行包括周期地交替进行：CPU执行和I/O等待

短CPU区间出现的频率较高，长CPU区间则很少。
I/O为主的程序通常短CPU区间很多，而CPU为主的程序可能有少量的长CPU区间。

1.2 CPU调度程序

当CPU变为空闲时，操作系统就必须从就绪队列中选择一个进程来执行。
进程的选择由短期调度程序（Short-term scheduler,或CPU调度程序）执行。

当出现下面任何情形之一时，需要CPU调度：

1. 进程从运行状态转入等待状态（I/O请求）
2. 进程从运行状态转入就绪状态（出现中断）
3. 进程从等待状态转入就绪状态（I/O完成）
4. 进程终止

如果调度只发生在1,4情形，则称为非抢占式调度；
如果在2,3情形发生调度，则称为抢占式调度。

1.3 调度程序/分派程序

调度程序（Dispatcher，又称分派程序）是一个模块，用来将CPU控制权交给短期调度程序选择的进程，功能包括：

1. 切换上下文：保存当前进程的状态，并加载新进程的状态
2. 切换到用户模式
3. 跳转到用户程序的合适位置，以便重新启动程序

每次进程切换都需要使用调度程序，速度应尽可能快。

调度延迟/分派延迟：停止一个进程而启动另一个进程所需的时间。

2. 调度准则

• 最大化：CPU利用率、吞吐量
• 最小化：
  • 平均周转时间：从进程提交到进程完成的时间
  • 平均等待时间：程在就绪队列中等待所花的时间，平均等待时间=平均周转时间-平均执行时间
  • 平均响应时间：从进程提交到进程第一次开始执行的时间

3. 调度算法

• 非抢占式：一旦进程开始执行，除非它完成，否则不会被抢占
• 抢占式：如果一个新到达的进程满足抢占条件，则抢占当前进程

3.1 先到先服务（FCFS）

先到先服务（First-Come, First-Served, FCFS）是最简单的调度算法。

按照进程到达就绪队列的顺序进行调度。

问题：护航效应：长进程可能会阻塞短进程，导致平均等待时间增加。

3.2 最短作业优先

最短作业优先（Shortest Job First, SJF），是最佳的调度算法之一。

基于进程执行时间的调度算法，选择预计执行时间最短的进程进行调度。

分为非抢占式（最短作业优先SJF）和抢占式（最短剩余时间调度SRTF）

SJF算法是最佳的，但是它不能在短期CPU调度的层次上实现，因为没有办法知道下一个CPU请求的长度。

问题：饥饿现象/无穷阻塞：长进程可能永远得不到执行。

3.3 优先级调度

优先级调度（Priority Scheduling）为每个进程分配一个优先级，调度时选择优先级最高的进程。

分为非抢占式和抢占式。

SJF算法是通用优先级调度算法的一个特例，只不过SJF算法的优先级是通过预测CPU区间的长短来实现的。

问题：饥饿现象/无穷阻塞

解决办法：老化：逐渐增大在系统中等待很长时间的进程的优先级。

3.4 轮转调度（RR）

轮转调度（Round Robin, RR）是最常用的抢占式调度算法。

将一个较小的时间单元定义为时间片（Time Quantum），每个进程在时间片内执行。

如果时间片用完，进程被抢占并放回就绪队列的末尾。

优点：响应时间小、不会出现护航效应和饥饿现象。

RR依赖于时间片大小，过大则和FCFS相同，过小则会导致频繁的上下文切换

注：考试中时间片默认为2s

3.5 多级队列调度

将就绪队列划分为多个独立队列，根据进程的某些属性分配到不同队列，每个队列有自己的调度算法。

队列之间也需要优先级，可以是固定优先级或划分时间片

3.6 多级反馈队列调度

根据不同CPU区间特点以区分进程，允许进程在队列之间移动。

如果进程使用过多的CPU时间，那么它会被移到更低优先级队列，这一方案会将I/O为主和交互式进程留在较高优先级队列。

在较低优先级队列中等待过长的进程会被转移到较高优先级队列，这种形式的老化能够阻止饥饿的发生。

4. 调度算法计算题

进程	到达时间	执行时间	优先级
P1	0	10	2
P2	1	4	5
P3	2	9	3
P4	3	5	1
P5	4	2	4

4.1 FCFS调度

甘特图：

| P1 | P2 | P3 | P4 | P5 |
0    10   14   23   28   30 

• 平均等待时间：$(0+(10-1)+(14-2)+(23-3)+(28-4))\div 5 = 13$
• 平均周转时间：$(10+(14-1)+(23-2)+(28-3)+(30-4))\div 5 = 19$
• 平均响应时间=平均等待时间

4.2 SJF调度

由于P1先到，所以P1先执行，非抢占式

甘特图：

| P1 | P5 | P2 | P4 | P3 |
0    10   12   16   21   30

• 平均等待时间：$(0+(12-1)+(21-2)+(16-3)+(10-4))\div 5 = 9.8$
• 平均周转时间：$(10+(16-1)+(30-2)+(21-3)+(12-4))\div 5 = 15.8$
• 平均响应时间=平均等待时间

4.3 SRTF调度

甘特图：

| P1 | P2 | P5 | P4 | P1 | P3 |
0    1    5    7    12   21   30

• 平均等待时间：$((0+(12-1))+(1-1)+(21-2)+(7-3)+(5-4))\div 5 = 7$
• 平均周转时间：$(21+(5-1)+(30-2)+(12-3)+(7-4))\div 5 = 13$
• 平均响应时间：$(0+(1-1)+(21-2)+(7-3)+(5-4))\div 5 = 4.8$

4.4 优先级调度（非抢占式）

由于P1先到，所以P1先执行，非抢占式

甘特图：

| P1 | P4 | P3 | P5 | P2 |
0    10   15   24   26   30

• 平均等待时间：$(0+(24-1)+(15-2)+(10-3)+(26-4))\div 5 = 13$
• 平均周转时间：$(10+(30-1)+(26-2)+(15-3)+(24-4))\div 5 = 19$
• 平均响应时间=平均等待时间

4.5 优先级调度（抢占式）

甘特图：

| P1 | P4 | P1 | P3 | P5 | P2 |
0    3    8    15   24   26   30

• 平均等待时间：$((0+(8-3))+(26-1)+(15-2)+(4-3)+(24-4))\div 5 = 12.6$
• 平均周转时间：$(15+(30-1)+(24-2)+(8-3)+(26-4))\div 5 = 18.6$
• 平均响应时间：$(0+(26-1)+(15-2)+(4-3)+(24-4))\div 5 = 11.6$

4.6 轮转调度（RR）

假设时间片为2s，进程到达入队 优先于 时间片到入队

运行流程

时间	CPU执行	就绪队列	备注
0	P1(0/10)	[]	P1到达，P1执行
1	P1(1/10)	[P2(0/4) ]	P2到达，P1继续执行
2	P2(0/4)	[P3(0/9), P1(2/10)]	P3到达，P1时间片到，P2执行
3	P2(1/4)	[P3(0/9), P1(2/10), P4(0/5)]	P4到达，P2继续执行
4	P3(0/9)	[P1(2/10), P4(0/5), P5(0/2), P2(2/4)]	P5到达，P2时间片到，P3执行
6	P1(2/10)	[P4(0/5), P5(0/2), P2(2/4), P3(2/9)]	P3时间片到，P1执行
8	P4(0/5)	[P5(0/2), P2(2/4), P3(2/9), P1(4/10)]	P1时间片到，P4执行
10	P5(0/2)	[P2(2/4), P3(2/9), P1(4/10), P4(2/5)]	P4时间片到，P5执行
12	P2(2/4)	[P3(2/9), P1(4/10), P4(2/5)]	P5完成，P2执行
14	P3(2/9)	[P1(4/10), P4(2/5)]	P2完成，P3执行
16	P1(4/10)	[P4(2/5), P3(4/9)]	P3时间片到，P1执行
18	P4(2/5)	[P3(4/9), P1(6/10)]	P1时间片到，P4执行
20	P3(4/9)	[P1(6/10), P4(4/5)]	P4时间片到，P3执行
22	P1(6/10)	[P4(4/5), P3(6/9)]	P3时间片到，P1执行
24	P4(4/5)	[P3(6/9), P1(8/10)]	P1时间片到，P4执行
25	P3(6/9)	[P1(8/10) ]	P4完成，P3执行
27	P1(8/10)	[P3(8/9) ]	P3时间片到，P1执行
29	P3(8/9)	[]	P1完成，P3执行
30	P3(9/9)	[]	P3完成，所有进程执行完毕

甘特图：

| P1 | P2 | P3 | P1 | P4 | P5 | P2 | P3 | P1 | P4 | P3 | P1 | P4 | P3 | P1 | P3 |
0    2    4    6    8    10   12   14   16   18   20   22   24   25   27   29   30

• 平均等待时间=周转时间-执行时间=$((29-0-10)+(14-1-4)+(30-2-9)+(23-3-5)+(25-4-2))/5=14$
• 平均周转时间=$(29+(14-1)+(30-2)+(23-3)+(25-4))/5=20$
• 平均响应时间=$(0+(2-1)+(4-2)+(8-3)+(10-4))/5=2.8$

六、进程同步

1. 竞争条件

多个进程并发访问和操作同一数据时，执行结果和访问发生的特定顺序有关，这种情况称为竞争条件。

例如：赋值语句和自增语句

2. 临界区问题

临界区(Critical Section)：并发过程中可能访问/修改共享数据的代码段。

临界区问题：确保在任何时刻，只有一个进程可以进入临界区。

解决临界区问题必须满足的3个条件：

1. 互斥：进程在临界区，其他进程不能进入临界区
2. 前进：没有进程在临界区，允许其他进程进入临界区，不能无限等待
3. 有限等待：从一个进程作出进入临界区的请求到该进程进入临界区之间，其他进程进入临界区的请求个数有限

忙则等待；空则让进；等则有限；等则让权

3. Peterson算法

适用于两个进程的临界区问题。

int flag[2] = {0, 0}; // 表示哪个进程想要进入临界区,默认为false
int turn; // 表示当前轮到哪个进程进入临界区
// P0
while(1){
    flag[0] = 1; // 表示进程0想进入临界区
    turn = 1; // 让进程1先进入临界区（等则让权）
    while(flag[1] && turn == 1); // 等待进程1退出临界区
    // 临界区代码
    flag[0] = 0; // 退出临界区
}
// P1
while(1){
    flag[1] = 1; // 表示进程1想进入临界区
    turn = 0; // 让进程0先进入临界区
    while(flag[0] && turn == 0); // 等待进程0退出临界区
    // 临界区代码
    flag[1] = 0; // 退出临界区
}

4. 硬件同步

许多系统为解决临界区问题提供了硬件支持

1. 修改共享变量禁止中断
   • 正在运行的指令不被其他指令抢占CPU
   • 适用于单处理器环境，非抢占内核（不允许内核模式进程被抢占，同时刻只有一个内核模式进程）
2. 使用原子操作：不能被中断的原子指令

5. 信号量(Semaphore)

信号量是一种不需要忙等的进程同步机制（空则让进），本质是一个整数变量。

除初始化外，只能通过两个原子操作来修改：P（wait）和V（signal）。

• P操作：如果信号量值大于0，则将其减1并继续执行；如果信号量值为0，则阻塞进程，直到信号量值大于0。
• V操作：将信号量值加1，如果有进程在等待，则唤醒一个等待的进程。

信号量分为两种类型：

1. 二进制信号量（Binary Semaphore）：值只能为0或1，通常用于互斥访问临界区，又被称为互斥锁（Mutex）。
2. 计数信号量（Counting Semaphore）：值可以为任意非负整数，通常用于控制对有限资源的访问。

实现方案：忙等实现（S>=0）和阻塞实现（S可以为负数，绝对值表示等待的进程数）。

忙等实现-自旋锁(Spinlock)：

• 当一个进程位于其临界区时，其它任何试图进入临界区的进程都必须在其进入区的代码中连续循环
• 不用阻塞进程、不必上下文切换
• 临界区代码短时效率高
• 适合多处理器环境（单处理器可以通过简单的禁止中断实现wait和signal的原子执行）
• 单处理器系统忙等时不会释放CPU，也没有其他进程能够运行以获得CPU控制权

6. 死锁和饥饿

死锁（Deadlock）：两个或多个进程互相等待对方释放资源，导致所有进程都无法继续执行。

饥饿（Starvation）：进程无限等待信号量。对信号量有关的链表LIFO顺序增删进程可能导致。

7. 经典同步问题

7.1 存在先后关系的简单同步问题

将不同进程间的代码块的执行顺序视为DAG，进行拓扑排序：

记信号量Sij表示进程j等待进程i的信号量（进程i执行完后才能执行进程j）

// P1
while(1){
    wait(S21);
    // 临界区1代码
    signal(S15);

    wait(S54);
    // 临界区4代码
    signal(S47);
}
// P2
while(1){
    // 代码块2
    signal(S21);
    
    wait(S15);
    wait(S35);
    // 临界区5代码
    signal(S54);
    signal(S56);

    wait(S47);
    wait(S67);
    // 代码块7
}
// P3略

7.2 生产者-消费者问题

生产者-消费者问题是经典的进程同步问题，涉及到两个进程：生产者和消费者。

生产者进程生成数据并将其放入缓冲区，消费者进程从缓冲区中取出数据进行处理。

// 生产者
while(1){
    wait(empty); // 等待缓冲区有空位

    wait(mutex); // 进入临界区
    buffer[in] = produce_item(); // 生产一个项目
    in = (in + 1) % N; // 更新输入指针
    signal(mutex); // 离开临界区

    signal(full); // 增加缓冲区满的计数
}
// 消费者
while(1){
    wait(full); // 等待缓冲区有项目

    wait(mutex); // 进入临界区
    consume_item(buffer[out]); // 消费一个项目
    out = (out + 1) % N; // 更新输出指针
    signal(mutex); // 离开临界区

    signal(empty); // 增加缓冲区空的计数
}

7.3 读者-写者问题

读者-写者问题是经典的进程同步问题，涉及到多个读者和一个写者。

• 读者：并发读取数据，不修改数据
• 写者：独占访问数据，修改数据

// 读者
while(1){
    wait(read_mutex); // 进入读者临界区
    read_count++; // 增加读者计数
    if (read_count == 1) wait(write_mutex); // 第一个读者阻塞写者
    signal(read_mutex); // 离开读者临界区

    // 读取数据
    read_data();

    wait(read_mutex); // 进入读者临界区
    read_count--; // 减少读者计数
    if (read_count == 0) signal(write_mutex); // 最后一个读者释放写者
    signal(read_mutex); // 离开读者临界区
}
// 写者
while(1){
    wait(write_mutex); // 进入写者临界区

    // 写入数据
    write_data();

    signal(write_mutex); // 离开写者临界区
}

进一步的：

• 读者优先：直到无读者等待，写者才能进入临界区
• 写者优先：有写者等待时，读者不能进入临界区

7.4 哲学家就餐问题

哲学家就餐问题是经典的进程同步问题，涉及到5个哲学家和5个叉子。

如果所有哲学家都拿起左边的叉子，那么就会发生死锁。

解决思路：

1. 当4个叉子被拿起时，没有叉子的哲学家不能拿起叉子
2. 任一哲学家拿起两个叉子前时，其他哲学家不能拿起叉子
3. …

七、死锁(Deadlock)

1. 死锁的4个必要条件

1. 互斥：至少有一个资源不能共享
2. 占有并等待：一个进程至少持有一个资源，并等待其他资源（被其他进程持有）
3. 非抢占：资源不能被抢占，只能由持有该资源的进程释放
4. 循环等待：存在一个进程等待环，其中每个进程都在等待下一个进程持有的资源

必须同时满足这四个条件才能发生死锁。

例题

假设有4个相同类型的资源被3个进程共享，每个进程最多需要2个资源，试证明这个系统不会死锁。

在任何情况下，即使所有进程都持有最大“不完全”资源（每个进程1个资源），系统中也总会剩下至少1个资源。这个剩余的资源足以让其中一个进程获得并完成任务，然后释放其占有的资源。

随着资源的释放，其他被阻塞的进程也能依次获得资源并完成任务。

因此，系统永远不会进入所有进程都无法继续执行的死锁状态。

2. 资源分配图

方形R表示资源，内部点个数表示资源数量；圆形P表示进程。

• P->R：表示进程P请求资源R
• R->P：表示资源R被进程P占用

死锁判断：

1. 根据资源R的出边，划掉已被分配的资源
2. 找到一个进程P，其所有请求（出边）都可被满足
3. 释放进程P占用的资源R，并将其边从图中删除
4. 重复步骤2和3，直到没有进程满足条件或所有进程都被释放

3. 死锁的预防

否定死锁的四个必要条件之一：

1. 互斥：非共享资源必须要有互斥条件，不能否定
2. 占有并等待：降低资源利用率，并且可能导致饥饿
   1. 执行前必须申请到所有资源
   2. 申请新资源前必须释放所有已占有的资源
3. 非抢占：使用范围有限，只能用于可保存和恢复的资源（寄存器、内存等）
   1. 如果一个进程申请的资源不能立刻分配，已分配资源可被抢占
4. 循环等待：对所有资源的类型进行完全排序，要求每个进程按递增顺序申请资源

4. 死锁的避免

安全状态：存在一种顺序为所有进程分配资源，能够避免死锁

4.1 资源分配图算法

[资源分配图]算法(#2-资源分配图)适用于每种资源类型只有一个实例的情况，核心思想是检测图中是否存在环路。

算法机制：

1. 除申请边和分配边外，引入一种新类型的边，称为需求边。
   • 需求边Pi->Rj 表示进程Pi可能在将来某个时候申请资源Rj。
   • 需求边类似于申请边，但用虚线表示。
2. 当进程申请资源时，需求边变成申请边。
3. 当资源分配给进程时，申请边变成分配边。
4. 当进程释放资源时，分配边变成需求边。
5. 系统必须事先要求资源，即当进程Pi开始执行时，所有需求边必须处于资源分配图。

假设进程Pi申请资源Rj，只有在将申请边Pi->Rj变成分配边Rj->Pi，且不会导致资源分配图形成环时才允许申请。

4.2 银行家算法

适用于每种资源类型有多个实例的情况。

当进程申请一组资源时，系统必须确定分配这些资源后系统是否仍处于安全状态。
如果是，就分配资源，否则，进程必须等待直到其他进程释放足够的资源。

// 银行家算法
int n,m; // n为进程数，m为资源种类数
int available[m]; // 可用资源向量
int max[n][m]; // 最大需求矩阵
int allocation[n][m]; // 当前分配矩阵
int need[n][m]; // 需求矩阵，need[i][j] = max[i][j] - allocation[i][j]

// 安全性检查 
bool is_safe(){
    auto work = available; // 可用资源向量
    auto finish = vector<bool>(n, false); // 进程完成标志
    for(int i = 0; i < n; ++i)
        // 进程i未完成且需求小于等于可用资源
        if(finish[i]==false && need[i] <= work) {
            work += allocation[i]; // 完成，释放资源
            finish[i] = true; // 标记进程i完成
            i = -1; // 重置i，重新检查所有进程
        }
    // 检查是否所有进程都完成
    for(int i = 0; i < n; ++i) {
        if(finish[i] == false) return false; // 存在未完成进程，系统不安全
    }
    return true; // 所有进程都完成，系统安全
}

// 资源请求算法
bool request_resources(int i, vector<int> request) {
    if (!(request<= need[i])) return false; // 请求超过需求
    if (!(request <= available)) return false; // 请求超过可用资源
    // 假设分配资源
    available -= request; // 更新可用资源
    allocation[i] += request; // 更新分配矩阵
    need[i] -= request; // 更新需求矩阵
    if (!is_safe()) { // 检查是否安全
        // 如果不安全，回滚分配
        available += request; // 恢复可用资源
        allocation[i] -= request; // 恢复分配矩阵
        need[i] += request; // 恢复需求矩阵
        return false; // 请求失败
    }
}

5. 死锁的检测和恢复

死锁检测算法：检测系统状态，确定系统是否出现了死锁。（原理类似于死锁避免）

恢复机制：终止（代价大）、资源抢占

八、主存管理

1. 内存管理单元MMU

在运行时完成逻辑地址到物理地址的转换的硬件被称为内存管理单元（Memory Management Unit, MMU）。

三种实现方法：连续内存分配、分页和分段

2. 连续内存分配

内存保护：通过基址寄存器和界限寄存器来实现。

• 基址寄存器：存储逻辑地址空间的起始地址
• 界限寄存器：存储逻辑地址空间的大小

多分区方法：固定分区、可变分区

孔：可用的内存块。
一开始整个内存是一个孔，随着进程的进入和中止，整个内存将遍布着许多大小不同的孔。

动态存储分配问题：根据一组空闲的孔和一个请求的大小，选择一个孔来满足请求。

三种分配策略：

1. 首次适应（First Fit）：从头开始搜索，找到第一个足够大的孔分配给进程。
2. 最佳适应（Best Fit）：搜索所有孔，找到最小的足够大的孔分配给进程。
3. 最差适应（Worst Fit）：搜索所有孔，找到最大的孔分配给进程。

• 首次适应和最佳适应在执行时间和利用空间方面都好于最差适应。
• 首次适应比最佳适应要快

碎片：因太小而无法分配给任何进程的孔。

• 外部碎片：由于分配和释放内存块后，剩余的内存块太小而无法满足新的请求，三种分配策略都可能导致外部碎片。
• 内部碎片：固定分区（分页）方法的问题，进程分配到的内存块比实际需要的要大，导致未使用的内存空间。

解决外部碎片的方法：

1. 紧缩：移动内存内容，将所有空闲空间合并成一整块
   • 缺点：有条件限制（要求重定位是动态的）、开销大
2. 允许物理地址空间为非连续的（分页和分段）

3. 分页（Paging）

3.1 基本方法

物理地址分为固定大小的块，称为帧(Frame)，逻辑地址分为同样大小的块，称为页(Page)。

内存的分配信息保存在称为帧表(frame table)的数据结构中

如果一个进程需要x页，则在内存在寻找x个空闲帧，如果有，则分配。

为进程分配内存时建立一个页表，用于将逻辑地址转换成物理地址，页表的指针与其他信息一起存入进程控制块。

页表基寄存器(PTBR)指向页表，切换页表只需改变PTBR的值即可。

页表长度寄存器(PTLB)表示页表的长度。

采用分页技术不会产生外部碎片，但是会有内部碎片。

分页的优点之一是可以共享共同代码：多个进程之间可以共享同一只读代码（重入代码）段的拷贝；私有独占代码和数据

记块大小$2^n$，物理内存大小为$2^k$，进程逻辑地址大小为$2^m$。

帧数：$2^{k-n}$，页数：$2^{m-n}$

逻辑地址高m-n位为§页表索引，低n位(d)为页偏移

假设每页4B：

3.2 转换表缓冲TLB

页表存储在内存中，每访问一个字节，需要两次访问内存（查找页表、找到需要的信息），针对这一问题的标准解决方案是关联内存(TLB)。

当关联内存根据给定值（页号）查找时，它会同时与所有键进行比较，如果找到条目，就得到相应的值域（帧号）

相当于页表的一个缓存，TLB的大小通常很小（几十个条目），因此需要使用替换算法

有效内存访问时间(Effective Memory Access Time, EMAT)：

$$
EMAT = (T+\epsilon)\alpha + (2T+\epsilon)(1-\alpha)
$$

• T：访问一次内存的时间
• ε：访问一次TLB的时间
• α：TLB命中率
• 第一项：TLB命中，访问一次内存
• 第二项：TLB未命中，访问两次内存

3.3 页表的结构

1. 层次化页表：将页表分为多个层次，每个层次的页表只包含一部分页表项，减少内存占用。
2. 哈希页表：使用哈希函数将页号映射到页表项，减少内存占用
3. 反向页表：每个物理帧对应一个页表项，记录哪个进程的哪个页映射到该帧

3.4 例题1

页面大小为4KB，逻辑地址24KB，页表的内容为：[2,5,6,8,3,11]。
则逻辑地址12293转换成物理地址为多少？给出计算过程。

12293D=011|0000,0000,0101B

页号p=011=3 => 帧号8

页内偏移d=101=5

物理地址=帧号页大小+页内偏移=84KB+5=32768+5=32773

3.5 例题2

如果访问一次内存要1.5ns，快表的命中率为85%，查找快表的时间为0.5ns。计算该系统的有效访问时间。

EMAT = (T + ε)α + (2T + ε)(1 - α) = (1.5 + 0.5) * 0.85 + (2 * 1.5 + 0.5) * (1 - 0.85)

4. 分段（Segmentation）

分段是指将逻辑地址空间划分成一组段，每个段都有名称和长度。
地址指定了段名和段内偏移。
因此用户可通过两个量来指定地址段名和偏移，编译器会自动根据用户程序构造段。

逻辑地址由两个元素组成：<段号s，段内偏移d>

段表：将二维的用户定义地址映射为一维物理地址。段表的每个条目都包含：

• 基地址：包含段的起始地址
• 界限：指定段的长度

段表基地址寄存器（STBR）指向内存中的段表所在的物理地址

段表界限寄存器（STLR）指示程序所用的段的个数，段号S小于STLR的时候才是有效的

5. 比较

	连续内存分配	分页	分段
外部碎片	有	无	有
内部碎片	无	有	无
代码共享	不可以	可以	可以

6. 其他

地址映射是指将程序中的逻辑地址转换为内存中的物理地址。

在分页管理系统中，为实现地址转换设置了控制寄存器，其中存放的是页表在内存中的起始地址。

存储管理应具有的功能包括：内存分配与回收，地址映射，内存保护和内存扩充。

在分页式虚拟内存中，当发现某页不在页表中，将产生缺页中断。若内存没有空闲帧，则需要进行页面置换。如果算法选择不合理，可能会出现频繁的页面调度，系统产生抖动现象。

九、虚拟内存

1. 有效访问时间

有效访问时间（Effective Access Time, EAT）是指在虚拟内存系统中，平均每次访问内存所需的时间。

EAT的计算公式为：
$$
EAT = (1 - p) \times T + p \times S
$$

• p：缺页率（Page Fault Rate），表示访问内存时发生缺页的概率
• T：平均内存访问时间
• S：平均页错误处理时间

实现按需页面调度要解决的两个问题：

1. 帧分配：内存中存在多个进程，需要决定每个进程分配多少帧
2. 页面置换：当内存满时，需要决定将哪个页面换出，原则：最小页错误率

2. 页面置换算法

页面置换的基本方法：

1. 查找所需页在磁盘上的位置。
2. 查找空闲帧
   • 如果有空闲帧，那么就使用它；
   • 如果没有空闲帧，就使用页面置换算法选择一个“牺牲”帧。
   • 将“牺牲”帧的内容写到磁盘上，修改页表和帧表。
3. 将所需的页读入空闲帧，修改页表和帧表。
4. 重启进程。

3. FIFO页面置换算法

FIFO（First In First Out）页面置换算法是最简单的页面置换算法。

  1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5

| 1*| 1 | 1 | 4*| 4 | 4 | 5*|   |   | 5 | 5 | H |
|   | 2*| 2 | 2 | 1*| 1 | 1 | H |   | 3*| 3 |   |
|   |   | 3*| 3 | 3 | 2*| 2 |   | H | 2 | 4*|   |

页错误次数：9

规律：不计命中，自某帧进入内存开始会出现n次，n为内存帧数

Belady异常：页错误率可能会随着所分配的帧数的增加而增加，如上例增加为4帧时：

  1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5

| 1*| 1 | 1 | 1 | H |   | 5*| 5 | 5 | 5 | 4*| 4 |
|   | 2*| 2 | 2 |   | H | 2 | 1*| 1 | 1 | 1 | 5*|
|   |   | 3*| 3 |   |   | 3 | 3 | 2*| 2 | 2 | 2 |
|   |   |   | 4*|   |   | 4 | 4 | 4 | 3*| 3 | 3 |

4. 最优页面置换OPT

最优页面置换算法（Optimal Page Replacement）是理论上最好的页面置换算法。

选择将来最长时间不被访问的页面进行置换。

  1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5

| 1*| 1 | 1 | 1 | H |   | 1 | H |   | 3*| 3 |   |
|   | 2*| 2 | 2 |   | H | 2 |   | H | 2 | 4*|   |
|   |   | 3*| 4*|   |   | 5*|   |   | 5 | 5 | H |

页错误次数：7

5. LRU页面置换算法

LRU（Least Recently Used）页面置换算法是基于最近最少使用原则的页面置换算法。

LRU算法选择最久未被访问的页面进行置换。

  1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5

| 1*| 1 | 1 | 4*| 4 | 4 | 5*|   |   | 3*| 5 | H |
|   | 2*| 2 | 2 | 1*| 1 | 1 | H |   | 1 | 4*|   |
|   |   | 3*| 3 | 3 | 2*| 2 |   | H | 2 | 2 |   |

页错误次数：9

OPT和LRU没有Belady异常。

十、文件系统

1. 概念

• 文件属性：名称、类型、位置、大小、时间戳、权限等
• 文件操作：创建、删除、读、写、重定位等
• 文件类型：扩展名

2. 访问方法

1. 顺序访问：从头到尾依次访问文件内容
   • read_next(), write_next(), reset()等
2. 直接访问（随机访问、相对访问）：可以直接跳转到文件的任意位置进行读写操作
   • read(n), write(n), position_to(n)等
3. 索引访问：使用索引表来快速定位文件中的数据块

3. 文件的路径名

盘符:\目录1\目录2\...\文件名.扩展名

相对路径、绝对路径

4. 目录与磁盘结构

1. 单层目录：所有文件都在同一目录下，命名冲突、分组问题
2. 双层目录：每个用户有自己的目录，用户目录下有文件
3. 树形目录：典型，相对路径、绝对路径都唯一
4. 无环图目录：有多条路径访问同一文件
   • 命名：一个文件可有多个绝对路径名，不同文件名可能表示同一文件
   • 删除：删除文件导致悬挂指针（指向不存在的文件或者执行了其他文件）
5. 通用图目录：有多条路径访问同一文件或目录

十一、文件系统实现（磁盘分配方法）

1. 连续分配

每个文件在磁盘上占用一组连续的块。

优点：

1. 简单：只需要块起始地址和块长度（占用几个块）就能访问文件
2. 访问连续分配的文件所需的寻道时间最小
3. 支持随机访问

缺点：

1. 外部碎片：随着文件的创建和删除，磁盘上会产生外部碎片，导致无法分配连续空间
2. 有时创建文件时不能确定文件的大小
3. 文件不能动态扩展

2. 链接分配

每个文件是磁盘块的链表，每个块包含下一个块的地址。

优点：

1. 简单：只需要起始地址；
2. 利用率高：没有外部碎片，只要有空闲块，文件就能增大

缺点：

1. 只能用于文件的顺序访问，不支持文件的直接访问。
2. 指针需要空间，磁盘空间有一部分用于存储指针。
3. 可靠性低：如果指针丢失或损坏可能牵连到空闲空间列表。

3. 索引分配（散列分配）

将所有指针放在一起，形成一个索引块，索引块包含文件的所有块的地址。

索引块方案：链接索引、多级索引、组合方案

十二、大容量存储结构（磁盘）

1. 磁盘速度

磁盘的访问时间：

• 数据传输时间：驱动器与计算机之间的数据传输速率
• 定位时间/随机访问时间
  • 寻道时间：磁头移动到柱面所需的时间
  • 旋转延时：等待扇区旋转到磁头下所需的时间

2. 磁盘调度

假设有一个磁盘队列，其I/O对各个柱面上块的请求顺序：98, 183, 37, 122, 14, 124, 65, 67，磁头位于53号柱面

寻道距离：寻道顺序下，相邻项序号之差的绝对值之和

调度时间=寻道距离×平均寻道时间+旋转延时×旋转次数

2.1 FCFS

寻道顺序：53->98->183->37->122->14->124->65->67

寻道距离：640

2.2 SSTF 最短寻道时间优先

优先前往距离当前磁头位置最近的请求。

寻道顺序：53->65->67->37->14->98->122->124->183

寻道距离：236

2.3 SCAN 扫描算法

磁臂丛磁盘的一端移动到另一端，当磁头移过每个柱面时，处理该柱面上的请求；到达另一端时返回并依次处理柱面上的请求。

寻道顺序：53->37->14->(0)->65->67->98->122->124->183

寻道距离：208+28(到达0造成的多余寻道距离)=236

2.4 C-SCAN 循环扫描算法

提供更加均匀的等待时间，磁头移动到另一端后立即返回磁盘开始，返回时不处理请求。

寻道顺序：53->65->67->98->122->124->183->(199)->(0)->14->37

寻道距离：382

2.5 LOOK/C-LOOK 调度算法

和SCAN/C-SCAN对应，LOOK调度算法只扫描到最后一个请求的柱面，然后返回。

C-LOOK寻道顺序：53->65->67->98->122->124->183->14->37

寻道距离：322

十三、I/O系统

1. I/O硬件

1. 轮询（Polling）：I/O设备传输数据时CPU处于忙等状态，CPU不断检查设备状态，直到设备准备好数据。
   • 并发性差、I/O效率低。
2. 中断（Interrupt）：I/O设备传输数据时，CPU可以为其它进程服务，每传输完一个字节，由I/O设备向CPU发送中断请求信号。
   • 并发性好，传送大批数据时I/O效率低。
   • 适用于低速外设，如键盘、鼠标等
3. 内存直接访问(DMA)：CPU提供源地址、目标地址以及字节数，完成整块数据传输后产生一次中断
   • 并发性好，可一次性传送大批数据，效率高
   • 适用于高速外设，如磁盘、网络等

2. 中断和陷阱

中断：操作系统中发生某一事件时，硬件将触发一个中断，中断信号通过中断向量将控制程序转移到合适的终端服务程序，以改变CPU的执行过程

陷阱：陷阱是由软件产生的，一般由用户请求或者错误引起，主要用于调用操作系统服务或者捕捉算法错误。