操作系统
操作系统概述
操作系统的作用和功能
系统资源的管理者，向上层提供方便易用的服务。
管理系统资源
- 处理机管理
- 储存器管理
- 文件管理
- 设备管理
向上层提供的功能
命令接口
联机命令接口实例（交互式命令接口）：在控制面板，用户输入一条指令，计算机执行一条
脱机命令接口实例（批处理） ：多条命令写在文件中，一同执行
图形化界面
程序接口：普通用户不能直接使用程序接口，只能通过程序代码间接使用。
操作系统基本特征
并发
- 并发：指两个或多个事件在同一时间间隔内发生。宏观上同时，微观上交替。
- 并行：指两个或多个事件在同一时刻同时发生（几核CPU可以并行执行几个程序）。
共享
- 资源互斥共享：可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。（摄像头的使用）
- 资源同时共享：允许一个时间段内由多个进程交替对它们进行访问。（两个进程交替着访问硬盘）
虚拟
- 时分复用：通过将时间划分成多个片段，让多个任务轮流使用同一个资源（比如 CPU）。
- 空分复用：通过将资源划分成多个独立的部分，让多个任务同时使用不同的资源（比如内存）
异步
在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的， 而是走走停停
操作系统发展与分类
手工操作阶段
批处理阶段
单道批处理
引入脱机输入/输出技术，通过外围机将纸带数据提前储存到磁带中，并由监督程序负责控制作业的输入、输出
- 联机批处理：CPU直接控制作业输入输出
- 脱机批处理：由外围机控制作业输入输出
内存中仅能有一道程序运行，当该程序进行I/O时，CPU将会空闲，利用率低
多道批处理
每次往内存中读入多道程序，一个程序运算结束进入I/O 操作时，让出CPU，由其他程序进行运算。
没有人机交互功能，提交作业后只能等待 计算机处理完成，无法进行调试、参数输入
分时/实时操作系统
分时操作系统
计算机以时间片为单位轮流为各个用户/作业服务，不能优先处理一些紧急任务
实时操作系统
能够优先响应一些紧急任务，某些紧急任务不需时间片排队。
- 硬实时系统：必须在绝对严格的时间内完成处理
- 软实时系统：能偶尔违反规定
其他操作系统
- 网络操作系统：多台计算机通过网络进行通信和资源共享，但是控制功能集中在某个或某些主机或服务器上
- 分布式操作系统：建立在网络操作系统之上，且控制功能是分布式的，每台计算机都可以参与管理和协调任务。
操作系统运行机制
基本概念
应用程序：操作系统上运行的普通程序。
内核程序：实现操作系统内核功能的程序，是整个系统的管理者
内核态，运行的是内核程序，此时可以执行特权指令
用户态，运行的是应用程序，此时只能执行非特权指令
内核态/用户态切换
CPU中存在一个程序状态字寄存器（PSW），其中有个二进制位用于表示当前处于内核态或者用户态
- 内核态—>用户态：内核程序将会执行一条特权指令——修改PSW的标志位为“用户态”，让出CPU使用权给用户程序。
- 用户态—>内核态：CPU检测到中断信号后，硬件自动完成内核态转化过程，转而运行处理中断信号的内核程序
中断与异常
内中断
与当前执行的指令有关， 中断信号来源于CPU内部。CPU执行指令时会检查是否存在异常。
- 例子1：试图在用户态下执行特权指令 。
- 例子2：执行除法指令时发现除数为0。
- 例子3：应用程序执行陷入指令，引发一个内部中断信号，切换至内核态，将CPU让给操作系统内核，完成系统调用。
外中断
与当前执行的指令无关， 中断信号来源于CPU外部，每一条指令执行结束 时，CPU都会例行检查 是否有外中断信号
- 时钟中断——由时钟部件发来的中断信号
- I/O中断——由输入/输出设备发来的中断信号
中断流程
不同的中断信号，需要用不同的中断处理程序来处理。
当CPU检测到中断信号后，会根据中断信号的类型去查询“中断向量表”，以此来找到相应的中断处理程序（内核程序）在内存中的存放位置。
系统调用
操作系统提供给应用程序使用的接口，应用程序可以通过系统调用来请求获得操作系统内核的服务。共享资源有关的操作，都必须通过系统调用的方式向操作系统内核提出服务请求(如存储分配、I/O操作、文件管理等)
调用流程
传递系统调用参数至寄存器——>执行陷入指令切换内核态（用户态）——>执行相应的内核程序处理系统调用（内核态）——>返回应用程序
操作系统体系结构
内核是操作系统最核心的部分，与硬件关联较紧密的模块。如Ubuntu、CentOS 的开发团队，其主要工作是实现非内核功能，而内核都是用了Linux内核
大内核/微内核
变态的过程是有成本的，要消耗不少时间，频繁地变态会降低系统性能
- 大内核：将操作系统的主要功能模块都做为系统内核，高性能，但是内核维护难度高（Linux、UNIX都是）
- 微内核：仅保留最基本的功能在内核，需要频繁切换用户态/内核态，性能较低，但是功能少，易于维护
分层结构
内核由多层组成，每一层仅能调用下一层接口。
- 层次分明，便于调试，且每一层只需要关注其自身的功能和与相邻层的接口，易于实现
- 多层调用效率较低，且难以合理定义不同层
模块化结构
根据操作系统功能划分为若干模块，模块还可进一步细分若干子模块，并规定好接口，各个模块通过接口通信
- 分模块易于维护，可以动态加载新模块到内核
- 模块间相互依赖，不利于调试。合理规划模块存在难度
外核结构
内核只提供最基本的硬件抽象和资源管理功能，由外核负责为进程分配未经抽象的硬件资源，只保证被请求的资源当前是空闲的，应用程序就允许直接存取它
- 减少了虚拟硬件资源的“映射层”，提升效率
- 应用程序需要处理更多的底层细节，增加了开发的复杂性
操作系统引导程序
下方流程为（Legacy）BIOS+MBR传统模式，现在操作系统基本上都是uefi+GPT模式。（legcay因为无法保存硬件的内存分配信息，所以每一次启动都要执行自查，uefi可以保存这些信息，所以可以不自检，直到用出问题再重新执行自检，所以uefi会比legcay快）
①CPU从BIOS（储存在主板的ROM上，而不是内存条中）中读取引导程序，用于进行硬件自检
②将磁盘的第一块（主引导记录）读入内存，执行磁盘引导程序，扫描分区表（存放则各个分区的位置信息）
③从活动分区（又称主分区，安装了操作系统的分区）读入分区引导记录，执行其中的程序
④从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作
虚拟机
使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统
第一类虚拟机：
直接运行在硬件上，由虚拟机管理程序直接将未经抽象的硬件资源划分给各个虚拟机使用。
性能更好，但是可迁移性较差。
虚拟机运行在用户态，虚拟机管理程序运行在内核态。 可以将特权/非特权指令更详细的划分为多个级别，虚拟机上的用户进程运行最低权限的指令，虚拟机上的操作系统可以运行一些权限更高的指令，而少数核心指令才需要通过虚拟机管理程序来协助完成，减少交互。
第二类虚拟机：
- 运行在宿主机操作系统上，由其为虚拟机管理程序分配经过抽象的硬件资源。
- 性能较差，但是迁移性强（导出镜像即可）。
- 虚拟机运行在用户态，虚拟机管理程序部分运行在内核态，部分运行在用户态，GuestOS发出的系统调用，会被VMM截获，转化为VMM对HostOS的调用
进程与线程
进程
进程（实体）组成
程序的一次执行过程即为一个进程，同一个程序多次执行会对应多个进程。
进程是能独立运行、独立获得资源、独立接受调度的基本单位。内存中存在多个进程，各进程并发执行。
进程状态
进程PCB中，会有一个变量state来表示进程的当前状态
进程控制
原语
具有原子性，需一次性完成，不能被打断的操作集合。多处理机条件下，同一时刻只有一个处理器能够执行该操作
在开始原语前执行关中断，在完成原语后执行开中断。两个指令都是特权指令
假设需要将阻塞队列中的某一个进程切换至就绪队列，如果在执行完①后被中断，那么就会在阻塞队列出现状态为就绪态的进程。
- ①修改对应进程的PCB的state为就绪态
- ②将对应PCB从阻塞队列放到就绪队列
原语主要完成以下三个任务：
更新PCB中的信息
a. 所有的进程控制原语一定都会修改进程状态标志
b. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c. 某进程开始运行前必然要恢复期运行环境
将PCB插入合适的队列
分配/回收资源
进程通信
进程是分配系统资源的单位，因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。
线程
线程概述
- 引入进程可以使得多个程序并发运行，但是对于一个程序只能串行执行，而引入线程后，同一个程序也能并发执行了
- 引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间（同一进程下的线程通过共享内存可以直接进行通信）），线程则作为CPU的分配单元。
- 同一进程内的线程切换，不需要切换进程环境，所以开销较小（除CPU外的资源都是分给进程的，而同一进程下的线程是共享这些资源的，切换时只需要保存CPU的几个寄存器信息）。而切换非同一进程内的线程切换，会引起进程的切换，开销较大
线程状态转化
与进程基本类似（下方仅展示出了最核心的几个状态），TCB和PCB类似。
线程的实现
用户级线程
由应用程序通过线程库实现， 线程切换可以在用户态下即可完成，无需操作系统干预，在操作系统内核看来，并意识不到线程的存在。
- 优点：不需要切换至内核态，线程管理的系统开销小，效率高
- 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
// 一个简单的模型，在while中通过if分支，实现多任务的并发，但实际上，仅对应操作系统中的一个进程。
int main() {
int i = 0 ;
while (true) {
if (i==0){处理视频聊天的代码;}
if(i==1){处理文字聊天的代码;}
if (i==2){处理文件传输的代码;}
i =(i+1)%3;
}
}内核级线程（Kernel-LevelThread）
内核支持的线程，由操作系统内核实现。 线程切换需要在核心态下才能完成，操作系统通过为每一个线程创建一个TCB结构来进行管理。
- 缺点：一个用户进程会占用多个内核级线程， 线程切换需要切换到核心态，管理的成本高，开销大。
- 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
多线程模型
处理机调度
调度概述
高级调度（作业调度）
按一定的原则从外存的作业（一个具体的任务） 后备队列中挑选一个作业调入内存，并创建进程。
外存——>内存
中级调度（内存调度）
内存不够时，可将某些进程的数据调出外存（称为挂起，被挂起的进程PCB会被组织成挂起队列）。等内存空闲或者进程需要运行时，按照某种策略决定将哪个处于挂起状态的进程重新调入内存。 一个进程可能会被多次调出、调入内存。
外存——>内存
低级调度（进程调度/处理机调度）
按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
内存——>CPU
调度算法的评价指标
进程调度的时间、过程与方式
选择要调度的进程（狭义的进程的调度）
进程切换（广义的进程调度在1的基础上还包括2）
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
闲逛进程
没有其他就绪进程时，运行闲逛进程
- 优先级最低
- 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
- 能耗低
调度算法
适用早期批处理系统算法
关心对用户的公平性、平均周转时间、平均等待时间等整体指标，但不关心“响应时间”，也并不区分任务的紧急程度，交互性很糟糕。
适用于交互式操作系统
更注重系统的响应时间、公平性、平衡性等指标
多级队列调度算法
系统中按进程类型设置多个队列，进程创建成功后插入某个队列
队列调度
- 固定优先级：高优先级空时低优先级进程才能被调度
- 时间片划分：如三个队列分配时间50%、40%、10%
队列调度调度策略：各队列可采用不同的调度策略，如：
- 系统进程队列采用优先级调度
- 交互式队列采用RR
- 批处理队列采用FCFS
同步与互斥
基本概述
进程同步
指多个进程在执行时需要协调，以确保它们按照一定的顺序执行，确保多个进程都能正确执行完成。
进程互斥
对临界资源的访问，需要互斥的进行。
进程互斥的实现
进程互斥的软件实现方式
下列方法一般是用于解决两个进程的互斥
单标志检查法
使用一个变量表示当前允许进入临界区的进程号（P1），当这个进程访问完临界区后，其会修改变量为另一个进程号（P2），即将使用临界区权限转交给P2
当P1访问完成后吗，将访问权限转让给P2，若P2未访问临界区，则P1即使再次需要也无法访问。可能导致其空闲，违背“空闲让进”原则。
// 伪代码
int turn = 0; // turn 表示当前允许进入临界区的进程号
// P0 进程
while (turn != 0); // 进入区
critical section; // 临界区
turn = 1; // 退出区，将其修改为另一个进程
remainder section; // 剩余区
// P1进程
while (turn != 1);
critical section;
turn = 0;
remainder section;双标志先检查法
设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。
如果P0判断成功进入，在更新前，CPU切换运行P1，此时P0还未更新状态，P1也可以判断成功进入，即P0和P1都可以访问临界资源。违反“忙则等待”原则。
// 伪代码
bool flag[2]; // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置为两个进程都不想进入临界区
// P0 进程
while (flag[1]); // 如果P1没有意愿进入，则进入，反之则阻塞
flag[0] = true; // 设置当前进程想进入临界区
critical section; // 访问临界区
flag[0] = false; // 访问完成，修改状态
remainder section; // 剩余区
// P1进程
while (flag[0]);
flag[1] = true;
critical section;
flag[1] = false;
remainder section;双标志后检查法
先上锁后检查
P0设置意愿后，CPU切换运行P1，同样设置意愿。此时两个进程将会陷入死锁，违背了“空闲让进”和“有限等待”
// 伪代码
bool flag[2]; // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置为两个进程都不想进入临界区
// P0 进程
flag[0] = true;
while (flag[1]);
critical section;
flag[0] = false;
remainder section;
// P1进程
flag[1] = true;
while (flag[0]);
critical section;
flag[1] = false;
remainder section;Peterson算法
遵循了空闲让进、忙则等待、有限等待三个原则，但是 依然未遵循让权等待的原则
// 伪代码
bool flag[2];// 表示进入临界区意愿的数组
int turn = 0;// 表示优先让哪个进程进入临界区
// P0 进程
flag[0] = true;
turn = 1;
while (flag[1] && turn==1);
critical section;
flag[0] = false;
remainder section;
// P1进程
flag[1] = true;
turn = 0;
while (flag[0] && turn==0);
critical section;
flag[1] = false;
remainder section;进程互斥的硬件实现方式
可以用于多个进程。
中断屏蔽方法
利用“开/关中断指令”，在某进程开始访问临界区到结束访问为止都不允许被中断。
- 不适用于多处理机，因为一个处理机开关中断，其他处理机还是可以访问。
- 只适用于操作系统内核进程，不适用于用户进程。
TestAndSet指令
也称为TestAndSetLock（TSL指令），通过硬件实现的，把“上锁”和“检查”变成了原子操作，执行的过程不允许被中断
适用于多处理机环境，不满足“让权等待”原则
// 伪代码，实际上是硬件层面实现的
// 布尔型共享变量 lock（全局） 表示当前临界区是否已被加锁
// true 表示已加锁，false 表示未加锁
bool TestAndSet (bool *lock){
bool old; // 存储 lock 原来的值
old = *lock; // old 用来存放 lock 原来的值
*lock = true; // 无论之前是否已加锁，都设置 lock 为 true
return old; // 返回 lock 原来的值
}
// 在实际使用时，通常会将 TestAndSet() 函数与 while 循环结合使用来确保只有当临界区解锁后才会再次允许其他线程进入临界区。
while (TestAndSet(&lock)); // 上锁"并"检查"
// 临界区代码段...
lock = false; // "解锁"
// 剩余区代码段...swap指令
// Swap 指令的作用是交换两个变量的值
void Swap (bool *a, bool *b) {
bool temp;
temp = *a;
*a = *b;
*b = temp;
}
// lock 表示当前临界区是否被加锁
// 使用 Swap 指令实现互斥的算法逻辑
bool old = true;
//循环，直到另一个进程执行完临界区代码，将lock设为false，和old交换
while (old == true)
Swap (&lock, &old);
// 临界区代码段...
lock = false;
// 剩余区代码段...互斥锁
一个进程在进入临界区时应获得锁，若锁不可用则阻塞，反之则设置锁变量为不可用，访问临界区。在退出临界区时释放锁，设置锁变量为可用。（获得锁和释放锁的操作都应该是原子性的）
需要连续循环忙等的互斥锁，都可称为自旋锁（spinlock），如TSL指令、swap指令、单标志法
- 需忙等，违反“让权等待”
- 常用于多处理器系统
- 一个核忙等，其他核照常工作
- 不用切换进程上下文，若上锁的时间短，则等待代价很低
信号量机制
使用某个变量表示系统中某种资源的数量，使用操作系统提供的一对原语来对这个信号量进行操作。
- P操作：申请一个资源
- V操作：使用完后释放一个资源
- 初始化操作：完成信号量初始的赋值（如设置资源的数量）
// 整数型信号量：仅使用一个整数表示资源，阻塞后会一直自旋
// 记录型信号量：使用结构体中的一个元素表示资源，结构体其他属性可以记录其他东西，如等待队列，阻塞后加入等待队列后挂起进程，而不是自旋
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
// P操作，检查与上锁一次性完成
void wait(semaphore S) {
S.value--;
// 如果资源不够，将其加入等待队列后挂起，此时value的绝对值就是阻塞队列中等待进程的数量
if (S.value < 0 ) {
block(S.L);
}
}
// V操作
void signal(semaphore S) {
// 释放一个资源
S.value++;
// 如果还是小于等于0，证明队列中还有未处理的进程，唤醒一个
if (S.value <= 0) {
wakeup(S.L);
}
}信号量机制实现进程互斥
临界区前执行P操作，临界区后执行V操作
semaphore mutex=1; // 初始化信号量
// P、V操作需要成对出现
P1(){
...
P(mutex); // 使用临界资源前需要加锁
临界区代码段... // 进行临界区操作
V(mutex); // 使用临界资源后需要解锁
...
}信号量机制实现进程同步
- 要为每一对前驱关系各设置一个同步信号量 0（表示不存在这种资源），需要前驱V操作添加资源。
- 在“前操作”之后对相应的同步信号量执行V操作 。
- 在“后操作”之前对相应的同步信号量执行P操作。
进程同步与互斥经典问题
生产者消费者问题
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。
实现
//互斥信号量，实现对缓冲区的互斥访问
semaphore mutex = l;
//同步信号量，表示空闲缓冲区的数量
semaphore empty-number = n;
//同步信号量，也即非空缓冲区的数量（即产品）
semaphore full-number = 0 ;
//先写操作（如生产者生产一个产品、把产品放入缓冲区），然后再填充PV操作。
// 生产者进程
producer () {
while(1){
生产一个产品
// 申请一个空白缓冲区
P(empty-number);
// 添加互斥锁
P(mutex);
把产品放入缓冲区
// 释放互斥锁
V(mutex);
// 增加一个产品
V(full-number); // 表明缓冲区中有一个新的产品可供消费
}
}
// 消费者进程
consumer () {
while(1){
P(full-number);
P(mutex);
从缓存区取出产品
V(mutex);
V(empty-number);
使用产品
}
} PV操作顺序
- 实现互斥的P操作一定要在实现同步的P操作之后。
- V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
// 若此时缓冲区内已经放满产品，则empty=0，full=n。
// 则生产者进程执行①使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。
// 由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，因此消费者也被阻塞。
producer () {
while(1){
生产一个产品
P(mutex); //①
P(empty-number); //②
把产品放入缓冲区
V(mutex);
V(full-number);
}
}
consumer () {
while(1){
P(full-number); //③
P(mutex); //④
从缓存区取出产品
V(mutex);
V(empty-number);
使用产品
}
} 多生产者——多消费者
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放 橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量
缓冲区（plate）大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。
//实现互斥访问盘子（缓冲区）
semaphore mutex = 1;
//盘子中有几个苹果
semaphore apple = 0;
//盘子中有几个橘子
semaphore orange = 0;
//盘子中还可以放多少个水果
semaphore plate = 1;
dad () {
while(1){
准备一个苹果;
P(plate);
P(mutex);
把苹果放入盘子;
V(mutex);
V(apple);
}
}
mom () {
while(1){
准备一个橘子;
P(plate);
P(mutex);
把橘子放入盘子;
V(mutex);
V(orange);
}
}
daughter () {
while(1){
P(apple);
P(mutex);
从盘中取出苹果;
V(mutex);
V(plate);
吃掉苹果;
}
}
son () {
while(1){
P(orange);
P(mutex);
从盘中取出橘子;
V(mutex);
V(plate);
吃掉橘子;
}
}吸烟者问题
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、 第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌 子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
// 桌上组合一的数量
semaphore offer1 = 0;
// 桌上组合二的数量
semaphore offer2 = 0;
// 桌上组合三的数量
semaphore offer3 = 0;
// 抽烟是否完成
semaphore finish = 0;
// 用于实现“三个抽烟者轮流抽烟”
int i = 0;
provider () {
while(1) {
P(finish);
if(i==0) {
将组合一放桌上；
V(offer1);
} else if(i==1) {
将组合二放桌上；
V(offer2);
} else if(i==2) {
将组合三放桌上；
V(offer3);
}
//根据需求选择，如轮询、随机
i = (i+1)%3;
}
}
smoker1 () {
while(1) {
P(offer1);
从桌上拿走组合一；卷烟；抽掉；
V(finish);
}
}
smoker2 () {
while(1) {
P(offer2);
从桌上拿走组合二；卷烟；抽掉；
V(finish);
}
}
smoker3 () {
while(1) {
P(offer3);
从桌上拿走组合三；卷烟；抽掉；
V(finish);
}
}读者-写者问题
- ①允许多个读操作同时执行，但同时仅允许一个写操作执行
- ②写操作不能与其他操作（写/读操作）同时执行
读进程是优先的
只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。
semaphore rw=1; //用于实现对共享文件的互斥访问
int count = 0; //记录当前有几个读进程在访问文件
semaphore mutex=1; //用于保证对count变量的互斥访问
writer () {
while(1){
P(rw); //写之前"加锁"
写文件...
V(rw); //写完了"解锁"
}
}
reader () {
while(1){
P(mutex); //各读进程互斥访问count
if(count==0) { //由第一个读进程负责
P(rw); //读之前"加锁"
count++; //访问文件的读进程数++
}
V(mutex);
读文件...
P(mutex); //各读进程互斥访问count
count--; //访问文件的读进程数--
if(count==0) { //由最后一个读进程负责
V(rw); //读完了"解锁"
}
V(mutex);
}
}读写公平算法
如果是多个读进程的话，由于锁上的w在修改完count后会释放锁，所以不会阻塞。
若存在写进程，为w加上锁后，由于rw被读进程阻塞，所以w不会释放，此时新执行的读进程也将阻塞。直到原有的所有读进程执行完后，rw释放，此时写进程将会获得rw，开始执行。
semaphore rw=1; //用于实现对共享文件的互斥访问
int count = 0; //记录当前有几个读进程在访问文件
semaphore mutex=1; //用于保证对count变量的互斥访问
semaphore w = 1; //用于实现“写优先”
writer () {
while(1){
P(w); //写之前"加锁"
P(rw); //写之前再次"加锁"
写文件...
V(rw); //写完了"解锁"
V(w); //写完了释放写锁
}
}
reader () {
while(1){
P(w); //读之前也要尝试获取写锁，实现“写优先”
P(mutex); //各读进程互斥访问count
if(count==0)
P(rw); //只有当没有其他读进程时才获取rw锁
count++; //访问文件的读进程数++
V(mutex);
V(w)
读文件...
P(mutex); //各读进程互斥访问count
count--; //访问文件的读进程数--
if(count==0) //由最后一个读进程负责
V(rw); //读完了"解锁"
V(mutex);
}
}哲学家进餐问题
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学 家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时， 才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲 学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
// 第三种解决方案
// 各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。
// 这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。
semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1; // 互斥地取筷子
//i号哲学家的进程
Pi (){
while(1){
P(mutex);
//拿左
P(chopstick[i]);
//拿右
P(chopstick[(i+1)%5]);
V(mutex);
吃饭...
//放左
V(chopstick[i]);
//放右
V(chopstick[(i+1)%5]);
思考...
}
}管程
可以看作是一个对象，封装了共享资源和对这些资源进行操作的方法，同时还提供了同步机制来确保线程安全。
死锁
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。
死锁产生的必要条件
对不可剥夺资源的不合理分配，可能导致死锁
静态策略预防死锁
死锁的产生必须满足四个必要条件，只要其中一个或者几个条件不满足，死锁就不会发生。
破坏互斥条件
把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如:SPOOLing技术，添加新的一层接受其他进程的资源请求。
- 缺点： 并不是所有的资源都可以改造成可共享使用的资源
破坏不可剥夺条件
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级。
缺点：
- 实现复杂
- 申请和释放资源需要开销，且释放已获得的资源可能造成前一阶段工作的失效（所以一般只适用于易保存和恢复状态的资源，如CPU）。
- 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
破坏请求和保持条件
在运行前一次申请完它所需要的全部资源，在它的资源未满足前， 不让它投入运行。一旦投入运行后，这些资源就一直归它所有。
缺点
- 进程可能在运行初期仅需要一部分资源，但在整个生命周期中却持续占用所有申请的资源。这会导致大量的资源闲置，降低了资源的总体利用率。
- 如果某些进程因为无法一次性获得所有资源而一直处于等待状态，那么这些进程可能会出现饥饿现象。
破坏循环等待条件
顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源， 同类资源（即编号相同的资源）一次申请完。
如：进程A申请资源顺序为1和2，进程B申请资源顺序为2和1，就容易造成死锁。而使用顺序资源分配法，进程A、B都以1、2的顺序申请资源，无论谁申请成功，都仅仅只会阻塞另一个进程，而不会造成死锁。
缺点
- 不方便增加新的设备，因为可能需要重新分配所有的编号；
- 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
动态策略避免死锁（银行家算法）
安全序列
- 指如果系统按照这种序列分配资源，则每个进程都能顺利完成。
- 只要能找出一个安全序列，系统就是安全状态（不会发生死锁）。安全序列可能有多个
不安全状态
- 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态（可能发生死锁）。
- 这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态。
核心思想
在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
算法实现
结构定义
n表示进程，m表示资源数（n、m都大于实际的进程和资源数）。
- 长度为m的一维数组Available表示还有多少可用资源
- n*m矩阵Max表示各进程对资源的最大需求数
- n*m矩阵Allocation 表示已经给各进程分配了多少资源
- Max–Allocation = Need 矩阵表示各进程最多还需要多少资源
- 用长度为m的一位数组Request表示进程此次申请的各种资源数
算法步骤：
①检查进程 i 此次申请是否超过了之前声明的最大需求数（Request[j]<Need[i][j]（0≤j≤m均要满足）），超过则报错
②检查此时系统剩余的可用资源是否还能满足这次请求（Request[j]≤Available[j] （0≤j≤m 均要满足）），不足则阻塞当前进程
③试探着分配，更改各数据结构（预分配，进程并未真正得到资源）
④用安全性算法检查此次分配是否会导致系统进入不安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待
安全性检测
检查当前的剩余可用资源是否能满足某个进程的最大需求（进程请求分配时是多次分配的，不是按照最大需求一次分配的），如果可以，就把该进程加入安全序列， 并把该进程持有的资源全部回收。 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
计算时，可一次性将最大需求资源小于系统可用资源的进程全部分配（因为它们一定是可以依次被满足的），回收这些进程的资源，再次重复前一次的分配规则，直到无法分配或者分配完成。
死锁的检测和处理
死锁检测算法
1）在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量）。消去它所有的请求边和分配边，使之称为孤立的结点，释放资源。
2）进程Pi释放资源后，在重复进行一系列简化，若最后能消去图中所有的边，则称该图是可完全简化的。若不能，则还连着边的 那些进程就是死锁进程。
死锁解除算法
- 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
- 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
- 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
内存管理
概述
基本概念
- 程序执行前需要先放到内存中才能被CPU处理，目的是缓和CPU与硬盘之间的速度矛盾。
- 内存划分为一个个小的储存单元，从零开始编址
- 按字节编址：则每个存储单元大小为1字节
- 按字编址：则每个存储单元大小为1个字
- 逻辑地址与物理地址
- 逻辑地址（相对地址）：相对于 进程的起始地址而言 的地址
- 物理地址（绝对地址）：在内存中的实际地址
- 程序运行流程：编译——>链接——>装入——>运行
- 编译：由编译程序将程序编译成若干个目标模块（机器语言形式）
- 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
- 装入：由装入程序将装入模块从存储设备（如硬盘）加载到内存中，完成逻辑地址到物理地址的转换。
装入方式
链接方式
内存保护
- 方案一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
- 方案二：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄 存器中存放的是进程的最大逻辑地址。
覆盖与交换
覆盖技术
- 将程序分为多个段（多个模块）。 常用的段常驻内存的固定区，不常用的段在需要时调入内存的覆盖区，不需要时调出内存。
- 必须由程序员声明覆盖结构，操作系统完成自动覆盖。增加了用户编程负担。 只用于早期的操作系统中。
交换技术
内存空间紧张时，系统将内存中某些进程暂时换出外存挂起（就绪挂起、阻塞挂起），把外存中某些已具备运行条件的进程换入内存。
换出外存数据的储存位置：
文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；
对换区主要用于作为内存扩展，被换出的进程数据就存放在对换区（PCB会常驻内存，不会被换出外存），空间较小，主要追求换入换出速度，因此通常对换区采用连续分配方式
交换发生时机：
- 内存空间紧张时，例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程； 如果缺页率明显下降，就可以暂停换出。
被选中换出的进程：
优先换出阻塞进程
优先换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，可以考虑进程在内存的驻留时间…
传统内存分配
内部碎片：进程内部有未利用的内存片段。
外部碎片：内存中的某些空闲分区由于太小而难以利用，通过紧凑技术（将已分配的内存块移动到一起，消除间隔）来解决外部碎片。
单一连续分（连续）
内存划分为系统区和用户区。 系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。 内存中只能有一道用户程序，用户程序独占整个用户区空间。
- 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
- 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低
固定分区分配（连续）
将整个用户空间划分为若干个固定大小的分区（可以划分大小为相等或不相等），在每个分区中只装入一道作业。
当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索分区说明表， 从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。
- 优点：实现简单，无外部碎片。
- 缺点：当程序需求超过所有分区大小，不得不采用覆盖技术来解决，会降低性能；会产生内部碎片，内存利用率低。
| 分区号 | 大小（MB） | 起始地址（M） | 状态 |
|---|---|---|---|
| 1 | 2 | 8 | 未分配 |
| 2 | 2 | 10 | 未分配 |
| 3 | 4 | 12 | 已分配 |
| …… | …… | …… | …… |
动态分区分配（连续）
不会预先划分内存分区，而是在进程装入内存时， 根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。
没有内部碎片，但是有外部碎片。
分区数据结构
- 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、 分区大小、分区起始地址等信息。
- 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。
分配与回收操作
- 分配：找到一个足够大的空闲分区，将其分配，修改其起始地址和分区大小（为0后将当前分区信息移出空闲分区表/链）
- 回收：回收后将分区信息添加到空闲分区表中（根据回收的位置，分配算法，可能添加到不同位置），如果前后有其他空闲分区，则将他们合并为一个。
分配算法
| 算法 | 算法思想 | 分区排列顺序 | 优点 | 缺点 |
|---|---|---|---|---|
| 首次适应 | 每次都从头到尾找合适的分区 | 空闲分区以地址递增次序排列 | 综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排 | 每次都从低地址的分区开始检索 |
| 最佳适应 | 优先使用更小的分区，以保留更多的大分区 | 空闲分区以容量递增次序排列 | 会有更多大的分区被保留下来，更能满足大进程需求 | 会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序 |
| 最坏适应 | 优先使用更大的分区，以防止产生太小的不可用的碎片 | 空闲分区以容量递减次序排列 | 可以减少难以利用的小碎片 | 大分区容易被用完，不利于大进程：算法开销大，回收分区后可能需要对空闲分区队列重新排序 |
| 邻近适应 | 由首次适应演变而来，每次从上次查找结束位置开始查找 | 空闲分区以地址递增次序排列（可排列成循环链表） | 不用每次都从低地址的分区开始检索。算法开销小（原因同首次适应算法） | 会使高地址的大分区也被用完 |
基本分页存储管理（离散）
基本分页存储逻辑地址划分：页号 + 页内偏移量
将内存空间编号划分为一个个大小相等的分区，每个分区就是一个页框（页框=页帧=内存块=物理块=物理页面）。
将进程的逻辑地址空间也编号分为与页框大小相等的一个个部分， 每个部分称为一个页或页面，进程的最后一页未必可以填完页框，为了减少内部碎片，需要选择合适的页框大小。
页表
页表用于记录进程页面和内存物理块号的映射关系，一个进程对应一张页表。页表存储在内存中，页表起始地址存储在对应的PCB中
假设内存大小为4GB，页面大小为4KB，页表中的页表项连续存放（一般设置页框可以存放整数个页表项），因此页号可以是隐含的，不占存储空间（类比数组），内存块数=内存大小/页面大小，块号至少需要20bit来表示，即3字节。
- i 号页表项的存放地址：X（页表起始地址）+3*I
- J 号内存块的起始地址=J * 内存块大小（记录的是块号，不是内存地址）
基本地址变换机构
页式管理中地址是一维的。即只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量。
通常会在系统中设置一个页表寄存器（PTR），进程执行时，存放页表在内存中的起始地址F和页表长度M。 进程未执行时，其储存在进程控制块（PCB）中。
若要访问逻辑地址A
- 确定逻辑地址A对应的页号P（页号=逻辑地址/页面长度）
- 查页表，找到P号页面在内存中的起始地址
- 确定逻辑地址A的页内偏移量W（逻辑地址%页面长度），A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W。
计算机内地址转换
- 如果每个页面大小为2^K（2的整数幂）字节，则逻辑地址末尾K位为页内偏移量，剩余部分为页号。
- 通过页号查找页表，可以得到块号。
- 将块号拼接上K位业内偏移量，即可以找到物理地址
具有快表的地址变换机构
快表，又称联想寄存器（TLB），仅用于存放最近访问的页表项副本的Cache（存满后通过置换算法淘汰一些），使用快表命中仅需访存一次，未命中需要两次。与此对应，内存中的页表常称为慢表。
访问一次快表耗时1us，访 问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？
- 若未采用快表机制：100+100=200us
- 先查快表，未命中再查页表：(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us
- 快表和慢表同时查找：(1+100)* 0.9+(100+100)* 0.1= 110.9 us
时间局部性
因为程序中存在大量的循环：执行过的指令、访问过的数据，很可能再次被执行，访问
空间局部性
很多数据在内存中都是连续存放的：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
两级页表
把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表（外层页表、顶层页表）
单级页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
使用多级页表（N级页表，访问逻辑地址需要N+1次访存）解决这个问题，但各级页表的大小不能超过一个页面
①按照地址结构将逻辑地址拆分成三部分
②从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
③根据二级页号查下一级页表，找到最终想访问的内存块号
④结合页内偏移量得到物理地址
若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面
例：某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式 存储，则要采用（）级页表，页内偏移量为（）位？
页面大小= 4KB =2^12B，按字节编址，因此页内偏移量为12位
页号 = 40-12 = 28位
页面大小= 2^12B，页表项大小= 4B ，则每个页面可存放2^12 / 4 = 2^10 个页表项
因此各级页表最多包含2^10 个页表项，需要10 位二进制位才能映射到2^10 个页表项，因此每一级的页 表对应页号应为10位。总共28位的页号至少要分为三级
单级页表需要整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
使用虚拟存储技术解决这个问题，需要访问页面时才把页面调入内存，通过页表项中标志位，确认其是否在内存中（不在则产生缺页中断，需目标页调入内存）。
<div style="display: flex;"> <table style="width: 50%; margin-right: 2%;"> <caption>一级页表</caption> <thead> <tr> <th>一级页号</th> <th>内存块号</th> <th>是否在内存中</th> </tr> </thead> <tbody> <tr> <td>0</td> <td>3</td> <td>是</td> </tr> <tr> <td>1</td> <td>无</td> <td>否</td> </tr> <tr> <td>...</td> <td>...</td> <td>...</td> </tr> <tr> <td>1023</td> <td>...</td> <td>...</td> </tr> </tbody> </table> <table style="width: 50%;"> <caption>二级页表</caption> <thead> <tr> <th>二级页号</th> <th>内存块号</th> <th>是否在内存中</th> </tr> </thead> <tbody> <tr> <td>0</td> <td>2</td> <td>是</td> </tr> <tr> <td>1</td> <td>4</td> <td>是</td> </tr> <tr> <td>...</td> <td>...</td> <td>...</td> </tr> <tr> <td>1023</td> <td>...</td> <td>...</td> </tr> </tbody> </table> </div>
基本分段存储管理（离散）
分段系统的逻辑地址结构：段号（段名）和段内地址（段内偏移量）所组成。（分段系统中也可以引入快表）
段表
按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。内存以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻，一个进程一个段表。
某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号16位,段内地址16位），因此用16位即可表示最大段长。物理内存大小为4GB（可用32位表示）。因此，可以让每个段表项占16+32=48位，即6B。由于段表项长度相同，因此段号可以是隐含的。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M+K*6。
分段、分页管理的对比
- 分页对用户是不可见的；分段对用户是可见的。
- 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
- 分段比分页更容易实现信息的共享和保护。因为分页不是按逻辑模块划分的，一个页面可能会有多个模块，部分需要保护，部分不需要；而分段只需要在段表上添加一个字段表示是否允 许其他进程访问即可。
- 分页管理内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片。分段管理，若段长过大，连续大空间分配不便，且会产生外部碎片（可以紧凑处理）
段页式存储管理（离散）
段页式系统的逻辑地址结构：段号、页号、页内地址（页内偏移量）组成。也可引入快表机构，用段号和页号作为查询快表的关键字。
将进程按逻辑模块分段，再将各段分页，进程运行前将各页面分别装入各内存块中。
虚拟内存管理
传统内存分配中，作业必须一次性全部装入内存后才能开始运行，且运行结束前需要长期驻留。
虚拟内存管理中（需在离散分配的基础上，对应请求分页、分段、段页式储存管理），程序不需要全部装入即可运行，运行时动态调入、调出数据。
多次性： 无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性： 在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
- 请求调页： 当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
- 页面置换： 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
虚拟性： 从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的
虚拟内存的实际容量= min（内存和外存容量之和，CPU寻址范围）
如：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。 则虚拟内存的最大容量为2^32 B=4GB，虚拟内存的实际容量=min(2^32B,512MB+2GB)=2GB+512MB
请求分页管理方式
与基本分页存储管理的主要区别： 在程序执行过程中，当所访问的信息不在内存时，由操作系统请求调页， 若内存空间不够，由操作系统进行页面置换。
- 状态位：是否已调入内存
- 访问字段：可记录最近是否被访问，访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
- 修改位：页面调入内存后是否被 修改过
- 外存地址：页面在外存中的存放位置
| 页号 | 内存块号 | 状态位 | 访问字段 | 修改位 | 外存地址 |
|---|---|---|---|---|---|
| 0 | 无 | 0 | 0 | 0 | x |
| 1 | b | 1 | 10 | 0 | y |
| 2 | c | 1 | 6 | 1 | z |
当访问页面不在内存时，便产生一个缺页中断（内中断），然后由操作系统的缺页中断处理程序处理中断，将此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元
页面置换算法
页面的换入、换出需要磁盘 I/O，因此好的页面置换算法应该追求更少的缺页率。
最佳置换算法（OPT）
每次淘汰当前内存中，在未来最久时间内不被访问的页面。可以保证最低的缺页率，但实际上，操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法（FIFO）
创建一个队列，大小为系统为进程分配内存块数量，每次选择淘汰最早进入内存的页面。
存在Belady 异常（当为进程分配的物理块数增大时，缺页次数不减反增的异常现象），因为先进入的页面也有可能最经常被访问
最近最久未使用算法（LRU）
淘汰最近最久未使用的页面，性能好，但需要专门的硬件支持。
寄存器实现
为每个在内存中的页面配置一个移位寄存器，可表示为R = Rn-1 Rn-2 Rn-3 … R2 R1 R0，当进程访问某物理块时，将其寄存器最高位设置1。且使用一个定时信号，每隔一定时间(例如 100 ms)将内存中所有页面的寄存器右移一位，当发生缺页中断时，选择寄存器值最小的页面替换至硬存中。
| R7 | R6 | R5 | R4 | R3 | R2 | R1 | R0 | |
|---|---|---|---|---|---|---|---|---|
| 页面1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 页面2 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 页面3 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 页面4 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 页面6 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 页面7 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | x |
| 页面8 | 0 | 1 | 1 | x | 1 | 1 | 1 | 1 |
软件算法实现
结构类似LinkedHashMap，常用于缓存的实现
- 新访问页面直接插入到列表头部
- 列表中的页面被访问，将数据移动到列表头部
- 列表已满，移除列表尾部数据
双向链表：将数据移动到列表头部时，需要修改当前节点的前一个节点的next指针，所以使用双向链表，便于获得前一个节点。每个节点储存key和value，储存key的目的是淘汰末尾数据时可以将其从散列表中
散列表：使用散列表存储节点，获取节点的复杂度将会降低为 O(1)
时钟置换算法（CLOCK）
也成为最近未用算法（NRU），将所有可能被置换的页面排成一个循环队列。
简单的时钟置换算法
为每个页面设置一个访问位（1为访问过，0为未访问过）。当需要淘汰一个页面时，选择一个淘汰页面最多会经过两轮扫描。
- 从上次扫描位置开始扫描检查页的访问位，如果是0，就选择该页换出，结束扫描；如果是1，则将它置为0，暂不换出，继续检查下一个页面。
- 若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描，选择为0的页面置换出。
改进型的时钟置换算法
在简单时钟置换算法的基础上，优先淘汰没有修改过的页面（因为修改后的页面需要I/O操作写回内存）
为每个页面设置（访问位，修改位），当需要淘汰一个页面时，选择一个淘汰页面最多会经过四轮扫描。
- 第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换，本轮扫描不修改任何标志位 。
- 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0 。
- 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位 。
- 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。
页面分配策略
驻留集
指请求分页存储管理中操作系统给进程分配的物理块的集合，采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
- 若驻留集太小，会导致缺页频繁。
- 若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。
页面分配、置换策略
固定分配：驻留集大小不变
可变分配：在进程运行期间， 即驻留集大小可变。
局部置换：发生缺页时只能置换当前进程的物理块。
全局置换：发生缺页时，可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
固定分配局部置换
驻留集大小不变，缺页时，只能选择该进程在内存中的页面进行置换。
很难确定为进程分配的物理块，可以根据进程大小、优先级、进程要求确认为进程分配的块数。
可变分配全局置换
驻留集大小可变，当某进程发生缺页时（只要缺页就给分配新物理块），从操作系统空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定（如内核数据等都是锁定的）的页面置换。
被选择调出的页可能是系统中任何一个进程中的页，被选中的进程拥有的物理块会减少，缺页率会增加。
可变分配局部置换
驻留集大小可变，当某进程发生缺页时，只允许从该进程的物理块中选出一个置换。
如果进程频繁缺页，系统会为其多分配几个物理块，直至该进程缺页率适当；反之，如果进程缺页率极低，则可适当减少分配（根据缺页率动态调整物理块）。
固定分配全局置换
不存在，全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配。
页面调入时机、位置
页面调入时机
预调页策略：基于局部性原理。因为调入的页面并不一定被访问，所以主要用于进程运行前的首次调入， 由程序员指出应该先调入哪些部分。
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。
页面调入位置
系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，在进程运行前， 需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，下次同样；而对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
UNIX方式：第一次使用的页面都从文件区调入，调出的页面都写回对换区，再次使用时从对换区调入。
工作集
抖动现象： 同一页面的置换频繁进行，主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
工作集： 指在某段时间间隔里，进程实际访问页面的集合。
- 驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页
- 可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法——选择一个不在工作 集中的页面进行淘汰
内存映射文件
传统文件调用
open 系统调用——打开文件
seek 系统调用——将读写指针移到某个位置
read 系统调用——从读写指针所指位置读入若干数据（从磁盘读入内存）
write 系统调用——将内存中的指定数据，写回磁盘（根据读写 指针确定要写回什么位置）
内存映射文件
open 系统调用——打开文件
mmap系统调用——将文件映射到进程的虚拟地址空间（在页表中为其创建页表项，指向硬盘中的位置，但并未将文件数据读入内存）
- 以访问内存的方式访问文件数据，访问的数据不在内存时，发生缺页中断，由操作系统将缺页调入。
- 进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘
优点
- 文件读入/写出由操作系统负责，编码者仅需映射文件后按访问内存的方式读写即可。
- 懒加载，只有访问到才将对应页加载到内存，而不是在映射后将整个文件读入内存。
- 因为加载入内存，多次访问文件同一页内容时，可以避免IO操作。
- 多个进程可以映射同一个文件，实现共享。
文件管理
文件结构
“逻辑结构”，指在用户看来， 文件内部的数据应该是如何组织起来的。
“物理结构”，指在操作系统看来，文件的数据是如何存放在外存中的。
文件的逻辑结构
无结构文件
二进制流或字符流组成。又称“流式文件”，如txt，wav文件。
有结构文件
一组相似的记录组成，每条记录由若干个数据项组成，又称“记录式文件”，如数据库表文件。
根据各条记录在逻辑上如何组织，可以分为三类
顺序文件
索引文件
创建索引表（定长记录的顺序文件），将关键字作为索引号内容，指针指向实际记录（每条记录对应一个索引项）。对于可变长记录可以实现快速查找，但修改增删记录时需要修改索引表。
可以用不同的数据项建立多个索引表，也可以使用多个数据项作为关键词建立一个索引表。
索引顺序文件
每个记录对应一个索引表项，因此索引表可能会很大，使用索引顺序文件，即一组记录对应一个索引表项，若是记录数过多，可以采用多级索引顺序文件。
文件物理结构
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”，读出写入都以块作为单位，操作系统为文件分配存储空间也以块作为单位。一般来说，磁盘块与内存块大小相等。
连续分配
每个文件在磁盘上占有一组连续的块，用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）获取起始块号，文件长度（用于验证逻辑块号是否合法）等，计算出实际地址=起始块号+逻辑块号+块内地址。
- 支持顺序访问和直接访问（即随机访问），读写速度块（因为如果不是连续的磁盘块，磁头移动需要消耗时间）。
- 会产生难以利用的磁盘碎片（可以紧凑处理），文件拓展麻烦（如果后方不存在空闲块，就需要整体移动文件）
隐式链接分配
- 目录中记录了文件存放的起始块号和结束块号。
- 除了文件最后一个磁盘块，其余磁盘块中都会保存指向下一个盘块的指针（对用户不可见）。
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB），从目录项中找到起始块号（即0号块），将其读入内存，通过上面的指针找到1号逻辑块读入，以此类推，读入i号逻辑块时，总共需要i+1次磁盘 I/O。
- 只支持顺序访问，不支持随机访问，查找效率低，且指向下一个盘块的指针也需要耗费少量的存储空间。
- 不会有碎片问题， 拓展文件时只需要修改FCB即可
显示链接分配
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table），开机时读入内存，且常驻，在目录项中储存起始块号即可。
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项 （FCB），从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT， 往后找到i号逻辑块对应的物理块号（无需IO操作）。
- 支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1 号逻辑块），且块号转换不需要访问磁盘，访问速度较快。
- 不会有碎片问题，拓展文件时只需要修改FCB即可
索引分配
系统会为每个文件建立一张索引表，记录了文件的各个逻辑块对应的物理块（类似页表），索引表存放的磁盘块称为索引块（地址记录在目录项中）。文件数据存放的磁盘块称为数据块。
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB），从目录项得到索引表存放位置，将其读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。
- 支持顺序访问，也支持随机访问。
- 不会有碎片问题，文件拓展也很容易实现（分配空闲块后增加一个索引表项即可）
假设磁盘总容量为1TB，磁盘块大小为1KB，则共有2^30个磁盘块，则可用 4B 表示磁盘块号，即一个索引表项为4B，则一个磁盘块只能存放256个索引项。若超过了这个数，可以使用以下方式构建索引：
链接
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
多层索引
建立多层索引（原理类似于多级页表），各层索引表大小不能超过一个磁盘块
假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若某文件采用两层索引，则该文件的最大长度可以到 256 * 256 * 1KB = = 64MB
若访问1026号逻辑块，则 1026/256 = 4，1026%256 = 2 ，因此可以先将一级索引表调入内存，查询4号表项， 将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。 访问目标数据块，需要3次磁盘I/O。
采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次 读磁盘操作
混合索引
若顶级索引表还没读入内存
- 访问0~7号逻辑块：两次读磁盘
- 访问8~263：三次读磁盘
- 访问264~65799：四次读磁盘
对于小文件，可以使用直接索引（占用数据块少，相同的索引项可以指向的小文件数更多）；对于大文件，可以使用间接索引或多级索引
文件目录
文件控制块（FCB）
目录本身就是一种有结构文件，每一条记录就是一个FCB，对应一个文件目录项。
FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）,实现了文件名和文件之间的映射。
目录结构
单级目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，在创建一个文件后（不允许文件重名），会将文件对应目录项插入目录表中，不适用于多用户操作系统。
两级目录结构
早期的多用户操作系统，采用两级目录结构，允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。但是两级目录结构依然 缺乏灵活性，用户不能对自己的文件进行分类。
多级目录结构(树形结构)
以绝对路径是“/照片/2015-08/自拍.jpg”的文件为例
首先读入根目录表；找到“照片”目录位置后，从外存读入对应的目录表；从该目录表找到“2015-08”目录的存放位置，再从外存读入对应目录表； 最后才找到文件“自拍.jpg”的存放位置。
以相对路径是“./2015-08/自拍.jpg”的文件为例
此时已经打开了“照片”的目录文件，即其目录表已调入内存，将其设置为 “当前目录”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。
树形目录结构便于分类以及对文件的管理和保护。但是不便于实现文件的共享，为此，提出了“无环图目录结构”。
无环图目录结构
在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。 可以更方便地实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件（或目录，即共享同一目录下的所有内容），一处修改，其他处可见。
每个共享结点设置有一个共享计数器，记录其被共享的数量。提出删除结点的请求时，只是删除该对应文件夹下的FCB、并使共享计数器减1，并不会直接删除共享结点。 只有共享计数器减为0时，才删除结点。
索引节点
查询各级目录的过程中，实际上仅需要文件名，FCB中的大部分信息是多余的，因此在目录项中，可以仅存放文件名和索引节点指针。
当找到文件名对应的目录项时，再通过索引节点指针将索引结点调入内存，根据其记录的信息查找文件位置，或进行其他操作。
| 文件名 | 索引节点指针 |
|---|---|
| 用于查询 | 指向除了文件名外的文件描述信息 |
文件储存空间管理
空闲表法
适用于“连续分配方式”，类似内存管理中的动态分区分配，分配（同样可采用首次适应等）和回收方式都一样。
| 开始空闲盘块号 | 连续空闲盘块数 |
|---|---|
| 0 | 2 |
| 5 | 1 |
| 13 | 2 |
| 18 | 3 |
| 23 | 1 |
空闲链表法
操作系统保存着链头、链尾指针。
空闲盘块链
分配：若某文件申请K个盘块，则从链头开始依次摘 下K个盘块分配，并修改空闲链的链头指针。
回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
空闲盘区链：
分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索， 找到一个大小符合要求的空闲盘区， 分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，分配后要修改相应的链指针、盘区大小等数据。
回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和 任何空闲区相邻，将回收区作为单独的一个空闲 盘区挂到链尾。
位视图法
用连续的“字”来表示，字中的每一位对应一个盘块，可以设置“0”代表盘块空闲， “1”代表盘块已分配。
- (字号,位号)=(i,j) 的二进制位对应的盘块号b=ni+j。
- b号盘块对应的字号i=b/n，位号j=b%n。
分配（若文件需要K个块）
①顺序扫描位示图，找到K个相邻或不相邻 的“0”；
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
③将相应位设置为“1”
回收
- ①根据回收的盘块号计算出对应的字号、位号
- ②将相应二进制位设为“0”
成组链表法
文件卷的目录区中专门用一个磁盘块作为“超级块”,开机时读入内存，要求内外存的一致性，用于存储成组链表法中的第一个节点。
如果一个组的第二个空闲块号等于-1（也可以设为其他特殊值），则意味着该组是最后一组，即无下一个空闲块。
释放空闲块时，先将释放的空闲块放到第一组，若第一组满后有新来的空闲块，则将第一组内的数据拷贝至新来的空闲块中后，再将其指向新来的空闲块。
分配空闲块的时候，先从第一组开始分配，若是第一组分配完后，但还剩下指向下一组的地址。则通过该地址，将下一组的数据拷贝至第一组，空闲出的物理块分配出去，以此类推。
文件基本操作
创建文件(create系统调用)
- 在外存中找到文件所需的空间。
- 根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项（包含了文件名、文件在外存中的存放位置等信息）。
删除文件(delete系统调用)
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
- 根据该目录项记录的文件在外存的存放位置、 文件大小等信息，回收文件占用的磁盘块（空闲表、位图等不同策略，采用不同回收方法）。
- 从目录表中删除文件对应的目录项。
打开文件(open系统调用)
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限（读、写、执行等）。
- 如果系统文件打开表中已存在该目录项，则将其count+1，否则将目录项复制到系统打开文件表中，count设为1，并将对应表目的编号返回给用户。并将对应表项添加到对应进程的打开文件表中。
- 读入内存之后，通过编号（文件描述符）就不需要每次都重新查目录了。
- 删除文件要确定当前文件未被进程使用，即打开计数器为0。
关闭文件(close系统调用)
- 将进程的打开文件表中相应表项删除。
- 回收分配给该文件的内存空间等资源
- 系统打开文件表的打开计数器count减1，若count= 0，则删除对应表项。
读/写文件(read/write系统调用)
“读/写文件”用文件描述符（即打开文件表的编号）即可指明文件，不再需要用到“文件名”
- 根据读指针、读入数据量、内存位置将文件数据从外存读入内存
- 根据写指针、写出数据量、内存位置将文件数据从内存写出外存
文件共享
基于索引结点的共享方式（硬链接）
多个目录项的索引节点指针，指向同一个索引节点（即同一份文件），在索引节点上设置计数器count，记录其正在被共享的数量。
删除文件/目录时，仅会删除其对应的目录项，并将指向的索引节点count-1，直到count为0，系统才会删除索引节点和文件。
共享方式（软链接）
文件2中存储的是文件1的文件路径，当操作系统访问文件2时，发现其是Link类型文件，则会根据记录的路径找到文件1访问。类似Windows的快件方式。
- 即使文件已经被删除了，但是link类型文件依旧会存在，只是查找会失败。
- 使用软链接需要先找到文件2，在通过其记录的路径找文件1，需要更多次数的IO
文件保护
口令保护
口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，对比正确才允许该用户访问文件。
- 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
- 缺点：正确的“口令”存放在系统内部，不够安全。
加密保护
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
- 优点：保密性强。
- 缺点：加密/解密要花费一定时间。
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-ControlList,ACL），该表中记录了各个用户可以对该文件执行哪些操作。
文件系统结构
层次结构
系统布局
物理格式化
即低级格式化，进行划分扇区，检测坏扇区，并用备用扇区替换坏扇区。
逻辑格式化
逻辑格式化后，灰色部分就有实际数据了，白色部分还没有数据
- i节点区（inode）：储存文件索引节点信息
- 超级块：储存成组链接法中的第一块数据
- 根目录：储存根目录的目录项和索引节点信息
open调用流程
近期访问过的目录文件会缓存在内存中
虚拟文件系统
虚拟文件系统功能
对于上层：提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
对于下层：要求各种文件系统必须实现某些规定的函数功能，如：open/read/write。
不同文件系统的目录项结构不一致，为了屏蔽这种差异，每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，将文件的信息赋值到vnode中。
以UFS为例，通过索引节点指针，将对应的inode读入，通过VFS，将inode中的信息赋值到vnode中。
文件挂载
即将一个文件系统挂载到操作系统中
①在VFS中注册新挂载的文件系统。 内存中的挂载表（mounttable）包含每个文件系统的相关信息，包括文件系统类型、容量大小等。
②新挂载的文件系统，要向VFS提供 一个函数地址列表
③将新文件系统加到挂载点（mount point），也就是将新文件系统挂载在某个父目录下
输入输出（I/O）管理
I/O管理概述
I/O设备概述
I/O 设备：可将数据输入到计算机，或可接收计算机输出数据的外部设备，UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。
I/O控制器
I/O设备由机械部件和电子部件（即I/O控制器或设备控制器，充当CPU和I/O设备的中介）组成。
可以位于计算机内部的主板上（如硬盘控制器）、外部设备内部（如打印机控制器）或作为独立的扩展卡（如显卡）。
功能
接受和识别CPU发出的命令
CPU通过控制线向IO逻辑发出指令，并在地址线中指明要操作的IO设备及地址，并使用相应的控制寄存器来存放命令的相关参数。
向CPU报告设备的状态
I/O控制器中会有相应的状态寄存器， 用于记录I/O设备的当前状态。如： 1表示空闲，0表示忙碌
数据交换
I/O控制器中会设置相应的数据寄存器。输入/输出时暂存数据。
地址识别
I/O控制器中各个寄存器分配有地址，其需要通过CPU提供的“地址”来判断要读/写的是哪个寄存器
组成
- 一个I/O控制器可能会对应多个设备
- 数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备）
IO控制器寄存器编址
内存映射I/O：控制器中的寄存器与内存统一编制，可以采用对内存进行操作的指令来对控制器进行操作。
寄存器独立编制：控制器中的寄存器独立编制，需要设置专门的指令来操作控制器，不仅要指明寄存器的地址， 还要指明控制器的编号。
IO控制方式
程序直接控制方式
每次读/写一个字，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。
- 优点：实现简单
- 缺点：CPU和I/O设备只能串行工作，且CPU需要一直轮询检查， 利用率低
中断驱动方式
在CPU发出读/写命令后，将等待I/O的进程阻塞。当I/O 完成后，控制器会向CPU发出一个中断信号，CPU在每个指令周期末尾检查中断，检测到后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。
每次读/写一个字，每次I/O操作开始之前、完成之后需要CPU介入。 等待I/O完成的过程中CPU可以切换到别的进程执行。
优点：CPU和I/O设备可并行工作，利用率提升。
缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU，中断处理过程中需要保存、恢复进程的运行环境，频率太高，会降低系统性能。
DMA方式（Direct Memory Access）
CPU指明此次要进行的操作，并说明要读入多少数据、数据要存放在内存的什么位置、数据在外部设备上的地址。控制器会根据CPU提出的要求完成数据的读/写工作， 整块数据的传输完成后，才向CPU发出中断信号。
数据的传送单位是“块”，数据直接在内存和设备之间进行流动，仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。
- 优点：数据传输以“块”为单位，且其传输不经过CPU，提高CPU利用率
- 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条 I/O指令，进行多次中断处理才能完成。
- DR（DataRegister，数据寄存器）：暂存从设备到内存，或从内存到设备的数据。
- MAR（Memory Address Register，内存地址寄存器）：在输入时，MAR表示数据应放到内存中的什么位置；输出时MAR表示要输出的数据放在内存中的什么位置。
- DC（DataCounter，数据计数器）：表示剩余要读/写的字节数
- CR（Command Register，命令/状态寄存器）：用于存放CPU发来的I/O命令，或设备的状态信息
通道控制方式
一台电脑可以有多个通道，一个通道可控制多个I/O控制器，每个I/O控制器可控制多个设备。
当应用程序发起I/O请求时，操作系统会将这个请求交给通道来处理，通道根据通道程序中的指令，选择合适的I/O控制器对对应设备进行操作。
通道可以看做功能单一的CPU，可以识别并执行一系列通道指令。
通道会根据CPU的指令执行相应的通道程序，只有完成一组数据块（可离散分布）的读/写后才需要发出中断信号，数据直接在内存和设备之间进行流动
- 缺点：实现复杂，需要专门的通道硬件支持
- 优点：CPU、通道、I/O设备可并行工作，资源利用率很高。
I/O软件的层次结构
用户层软件
库函数，封装了操作系统提供的API，如printf(“hello, world!”); 会被翻译成等价的write系统调用。
设备独立性软件
与设备的硬件特性无关的功能几乎都在这一层实现。
向上层提供统一的调用接口（如read/write系统调用）
设备的保护，不同用户对设备的访问权限不一样，类似文件保护（设备被看做是一种特殊的文件）。
差错处理，对一些设备的错误进行处理。
设备的分配与回收
数据缓冲区管理
建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序（因为不同设备的硬件设计不一样，需要专门设计响应的驱动程序）
I/O调度：用某种算法确定一个好的顺序来处理各个I/O请求。
- 打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法
- 磁盘调度可以选择先来先服务、最短寻道优先、SCAN等算法
设备驱动程序
直接涉及到硬件具体细节，主要负责对硬件设备的具体控制，将上层发出的一系列命令（如 read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等
中断处理程序
当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。
执行流程
- 用户通过调用用户层软件提供的库函数发出的I/O请求。
- 用户层软件通过“系统调用”请求设备独立性软件层的服务。
- 设备独立性软件层根据LUT调用设备对应的驱动程序。
- 驱动程序向I/O控制器发出具体命令。
- 等待I/O完成的进程应该被阻塞，因此需要进程切换，而进程切换必然需要中断处理。
接口
输入/输出应用程序接口
对于不同类型的接口，操作系统无法提供一个统一的系统调用接口来进行调用。
字符设备接口（不可寻址）
- 使用get/put系统调用，向字符设备读/写一个字符。
块设备接口（可寻址）
- 使用read/write系统调用，向块设备的读写指针位置读/写多个字符；使用seek系统调用，修改读写指针位置。
网络设备接口（网络套接字接口）
- 使用socket系统调用:创建一个网络套接字（申请一片内核空间，用于存放接受或发送的数据），需指明网络协议(TCP? UDP? )。
- 使用bind：将套接字绑定到某个本地“端口”。
- 使用connect：将套接字连接到远程地址。
- 使用read/write：从套接字读/写数据。
阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。 eg：字符设备接口——从键盘读一个字符get
非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。 eg：块设备接口——往磁盘写数据write
设备驱动程序接口
由操作系统提供统一的接口，设备厂商在各自驱动程序中分别实现。
设备独立性软件
假脱机技术（SPOOLing技术）
将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用，以共享打印机为例，当多个用户进程提出输出打印的请求时，系统将会接受全部请求，并为每个请求做如下操作：
（1）在磁盘输出井中为进程申请一个空闲缓冲区，并将要打印的数据送入其中；
（2）为用户进程申请一张空白的打印请求表，记录打印数据存放等相关打印信息，再将该表挂到假脱机文件队列上。
当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。
设备的分配与回收
相关概念
控制表
设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况
控制器控制表（COCT）：每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
通道控制表（CHCT）：每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。
设备分配
分配步骤
只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送
①根据进程请求的逻辑设备名查找LUT，如果LUT中存在对应的逻辑设备名，则通过其物理设备名找SDT中指定表项。如果不存在，直接查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。
②根据SDT找到DCT，若设备忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系。
- 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
- 每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统
多个设备的逻辑设备名，一般以编号递增的方式：
- 磁盘设备：
disk0,disk1 - 网络设备：
eth0,eth1 - 打印机设备：
lp0,lp1
逻辑设备表作用
操作系统检查对应的逻辑设备名，如果发现其对应的物理设备忙碌或者不存在，则操作系统可以通过逻辑设备表查找其他空闲的同类型设备，并将请求重定向到这些设备。
- 解决使用物理设备名，换了一个物理设备，则程序无法运行
- 解决使用物理设备名，进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待。
缓冲区管理
可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
单缓冲（专用）
操作系统在主存中为其分配一个缓冲区，缓冲区非空时仅能读出，不能写入；当缓冲区为空，只有写满才能开始读出。
处理一块数据平均耗时Max(C,T)+M。
双缓冲（专用）
操作系统会在主存中为其分配两个缓冲区。
采用双缓冲策略，处理一个数据块的平均耗时为Max(T,C+M)。
若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输；设置双缓冲区，则同一时刻可以实现双向的数据传输。
循环缓存（专用）
将多个大小相等的缓冲区链接成一个循环队列。
缓存池（共用）
缓冲池由系统中许多共用的缓冲区组成，注意队列需要互斥访问。
缓冲区的按逻辑构成队列分为：
- 空缓冲队列(emq)：包含所有空闲的缓冲区。
- 输入队列(inq)：包含所有装满输入数据的缓冲区。
- 输出队列(outq)：包含所有装满输出数据的缓冲区。
缓冲区根据其作用不同，可以分为四种工作缓冲区：
- 输入工作缓冲区（hin）：输入进程从 emq 取空缓冲区，作为 hin，存入数据后放入 inq。
- 提取输入工作缓冲区（sin）：计算进程从 inq 取装满数据的缓冲区，作为 sin，提取数据后放回 emq。
- 收容输出工作缓冲区（hout）：计算进程从 emq 取空缓冲区，作为 hout，存入输出数据后放入 outq。
- 提取输出工作缓冲区（sout）：输出进程从 outq 取装满数据的缓冲区，作为 sout，提取数据后放回 emq。
每个缓冲区都分为两部分，标识作用的缓冲首部和存放数据的缓冲体，在缓冲首部如设备号等信息，确保数据可以被正确的进程取走。
磁盘和固态硬盘
磁盘的结构
磁盘的盘面按圈划分为许多磁道，一个磁道又被划分成一个个扇区（一个扇区对应一个磁盘块），各个扇区存放的数据量相同（如1KB）。最内侧磁道上的扇区面积最小，因此数据密度最大。
（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”，即磁盘块号
- ①根据柱面号移动磁臂，让磁头指向指定柱面；
- ②根据盘面号，激活指定盘面对应的磁头；
- ③根据扇区号，在磁盘旋转的过程中，使磁头从对应扇区划过完成读写。
磁盘调度
磁盘读写时间
寻道时间 Ts=s+m*n：在读/写数据前，将磁头移动到指定磁道所花的时间。
- 启动磁头的时间：假设耗时为s；
- 移动磁头的时间：假设磁头匀速移动，每跨越一 个磁道耗时为m，总共需要跨越n条磁道，耗时n*m。
延迟时间 Tr：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。
- 设磁盘转速为r，则平均所需的延迟时间Tr = 平均寻找转动圈数 * = (1/2)*(1/r) = 1/2r
传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间
- 假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则： 传输时间Tt=转一圈所需时间 * 读取字节数占几圈 = (1/r)* (b/N) = b/(rN)（读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r）
磁盘调度算法
延迟时间与传输时间都与转速相关，操作系统无法影响硬件的固有属性，仅能从寻道时间入手。
先来先服务算法（ FCFS）
根据进程请求访问磁盘的先后顺序进行调度。
- 优点：公平；
- 缺点：请求访问的磁道分散时，性能差，寻道时间长。
最短寻找时间优先（ SSTF）
优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（贪心）
- 优点：性能较好，平均寻道时间短
- 缺点：可能产生“饥饿”现象
扫描算法（ SCAN）
在最短寻找时间优先算法的基础上，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移 动。
- 优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
- 缺点
- 只有到达最边上的磁道时才能改变磁头移动方向，即使当前位置到最边不存在请求的磁道。
- 对于各个位置磁道的响应频率不平均。假设扫描A和扫描B是连续的两次扫描，对于100而言，扫描A刚经过，扫描B就会再次扫描；而对于50而言，扫描A经过后，等等扫描B经过，之间需要耗费更长时间等待。
LOOK 调度算法
在扫描算法的基础上，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。
- 优点：比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
- 缺点：未解决扫描算法对于各个位置磁道的响应频率不平均。
C-SCAN
在扫描算法的基础上，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
- 优点：比起SCAN来，对于各个位置磁道的响应频率很平均。
- 缺点：未解决扫描算法只有到达最边上的磁道时才能改变磁头移动方向。
C-LOOK 调度算法
在C-SCAN算法的基础上，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
减少延迟时间的方法
交替编号
磁头读入一个扇区数据后需要一小段时间处理，如果扇区连续分布，在读完1之后，无法立刻读2，需要等待。而盘片不能停止，所以只能等盘片下次旋转到2时才可以读取。使用扇区交替编号可以解决这个问题。
因为是交替编号，所以读取连续的一圈扇区，磁针需要转两圈。
磁盘地址结构的设计
假设某磁盘有8个柱面/磁道（假设最内侧柱面/磁道号为0 ）， 4个盘面，8个扇区。且需要连续读取物理地址（00,000,000）~（00,001,111）的扇区
- 盘面号，柱面号，扇区号编址，（00, 000, 000）~（00,000,111 ）转两圈可读完，（00, 001, 000）~（00,001,111 ），需要启动磁头臂，将磁 头移动到下一个磁道
- 柱面号，盘面号，扇区号编址，（00, 000, 000）~（00,000,111 ）转两圈可读完，（000, 01, 000）~（000,01,111 ），由于柱面号/磁道号相同， 只是盘面号不同，因此不需要移动磁头臂。只需要激活相邻 盘面的磁头即可
读取地址连续的磁盘块时，采用（柱面号， 盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间。
错位命名
所有盘面都是一起连轴转的，若相邻的盘面相对位置相同处扇区编号相同，读取完磁盘块（000, 00, 111）之后，需要短暂的时间处理，而盘面又在不停地转动，所以只能等到下一次磁针划过才可以读取（000,01,000），相邻盘块间采用错位命名可以解决这个问题。
磁盘的管理
磁盘初始化
- 进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大 小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（用于校验扇区中的数据是否发生错误）
- 将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘）
- 进行逻辑格式化，创建文件系统。包括创建文件系统 的根目录、初始化存储空间管理所用的数据结构（如位示图、 空闲分区表）
引导块
计算机开机时，通过执行初始化程序（自举程序）完成进行一系列初始化的工作。
- ROM（只读存储器，集成在主板上）存放完整的初始化程序，在出厂时写入了，不能修改。（即无法对初始化程序更新）
- ROM中只存放很小的自举装入程序，完整的自举程序放在磁盘的启动块（即引导块 /启动分区）上，位于磁盘的固定位置。 开机时先运行自举装入程序，通过执行该程序就可找到引导块，并将完整的自举程序读入内存执行。
坏块的管理
- 对于简单的磁盘：可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区， 比如：在FAT表上标明。（坏块对操作系统可见）
- 对于复杂的磁盘：磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。 在磁盘出厂前进行物理格式化时就将坏块链进行初始化。 会保留一些“备用扇区”，用于替换坏块。这种方案称 为扇区备用。（坏块对操作系统不可见）
固态硬盘SSD
每个页仅可以写一次，如果某块已经写入数据的页需要修改，需要将这一块的其他数据移动到新块，在新块对应的页写入修改后的数据。由闪存翻译层进行逻辑地址的重新映射。
