操作系统期末复习

第一章

操作系统目标

方便性
有效性
可扩充性
开放性

操作系统作用

计算机系统资源的管理者

处理器管理
存储器管理
I/O设备管理
文件管理

用户与计算机硬件系统之间的接口

实现对计算机资源的抽象

发展历史

无OS机器

人工操作方式

脱机I/O方式

单道批处理系统

多道批处理系统

分时系统

操作系统基本特征

并发
共享
虚拟
异步

并发与并行

并行性：多个事件在同一时刻发生

并发性：多个事件在同一时间间隔发生

并发与并行

并发针对单核CPU，并行针对多核CPU

单核CPU同一时刻只能运行一个程序，多核CPU同一时刻可以执行多个程序

并发对应时分复用技术，并行对应空分复用技术

操作系统内核主要功能

支撑功能：中断处理、时钟管理、原语操作

资源管理功能：进程管理、存储器管理、设备管理

操作系统主要功能

处理机管理功能：进程控制、进程同步、进程通信、调度

存储器管理功能

文件管理功能

设备管理功能

OS与用户接口

为什么操作系统是中断驱动的

操作系统依赖中断机制，高效响应外部事件，避免轮询消耗资源，实现多任务切换和实时处理，确保系统核心调度。

操作系统结构

简单结构

模块化结构

分层式结构

系统调用与过程调用的区别

系统调用需切换至内核态，由操作系统执行，权限高、开销大；过程调用在用户态执行，无权限切换，效率高。

运行在不同系统状态
状态的转换
返回问题
嵌套调用

微内核OS

定义：内核只保留必不可少的部分，基于C/S模型，将机制与策略分离，面向对象

优点：提高系统可扩展性、增强可靠性、可移植性强、提供对分布式系统支持，面向对象

第二章

程序顺序执行和并发执行的特征

前趋图

程序顺序执行

一个较大的程序通常都由若干个程序段组成
程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。

程序并发执行特征

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

进程：程序+数据+PCB

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程是程序的执行过程，也是CPU和资源调度的单位。

进程控制块PCB：专门的数据结构，与进程一一对应。进程存在的唯一标志，常驻内存

进程的特性

动态性（最基本）

并发性

独立性

异步性

进程与程序的区别

进程是程序的一个实例，是程序的一次执行

进程是活动的，有生命周期的。程序是静态的，是一段代码

程序是进程的代码部分，进程还包括数据、PCB等

进程在内存中，程序在外存中

一个程序可以对应多个进程

一个进程可以包含多个程序

进程基本状态及转换

最基本：运⾏态、就绪态、等待态

就绪状态

执行状态

阻塞状态

创建状态

终止状态

为什么引入挂起

终端用户的需要：运行期间发现问题想要暂停
父进程请求：挂起并修改子进程
负荷调节需要
OS的需要

PCB的作用

作为独立运行基本单位的标志
能实现间断性运行方式
提供进程管理所需要的信息
提供进程调度所需要的信息
实现与其他进程的同步与通信

PCB中信息

进程标识符
处理机状态
进程调度信息
进程控制信息

PCB组织方式

线性方式
链接方式
索引方式

进程的状态及转换

进程创建、终止过程

进程创建过程

申请空白PCB
分配所需资源
初始化PCB
插入就绪队列

终止过程

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
若被终止进程正处于执行状态，应立即终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后重新进行调度
若该进程还有子进程，应将所有子进程终止
将该进程所拥有的全部资源，归还给其父进程或系统
将被终止进程（PCB）从所在队列中移去

进程阻塞与唤醒

进程阻塞过程

原语Block()
进程的阻塞是进程自身的一种主动行为
具体过程：停止执行；状态由执行改为阻塞；将PCB插入阻塞队列

进程唤醒过程

原语Wakeup()
具体过程：从阻塞队列中移出；状态由阻塞改为就绪；将PCB插入就绪队列

进程挂起与激活

挂起：Suspend()
激活：Active()

什么是进程上下文切换，什么事件导致上下文切换

进程上下⽂切换是指操作系统将CPU从⼀个进程切换到另⼀个进程时，需要保存当前进程的运⾏状态（上下⽂），并加载下⼀个进程的上下⽂，使其能够继续执⾏。

事件：时间片用完、进程阻塞、高优先级进程就绪、中断触发、进程终止

进程的四种通信方式

共享存储器系统

主要思想：进程之间通过共享某些数据结构或存储区实现信息传送

基于共享数据结构的通信方式 - 效率低（低级通信）
基于共享存储区的通信方式 - 高级（高级通信）

管道通信系统

用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件

向管道提供输入的发送进程（写进程），以字符流形式将大量的数据送入管道；接收进程（读进程），可从管道中接收数据

消息传递系统

最广泛

系统提供发送信息与接收信息，进程间通过使用这两个操作进行通讯，无需共享任何变量
进程间的数据交换，以格式化的信息为单位
消息由消息头和消息正文构成
必须要有通信线路

直接通信方式

发送原语send(receiver,message)
接收原语receive(sender,message)

间接通信方式

发送原语：send(mailbox,message)
接收原语：receive(mailbox,message)

进程与线程对比

线程和进程
调度的基本单位

传统OS中，拥有资源、独立调度和分派的基本单位都是进程

引入线程的OS中，线程作为调度和分派的基本单位，进程作为拥有资源的基本单位

同一进程，线程切换不会引起进程切换；不同进程，线程切换会引起进程切换

并发性

引入线程的OS中，进程可以并发执行，同一进程多个线程之间也可并发执行

拥有资源

进程是系统中拥有资源的一个基本单位，拥有资源

线程本身并不拥有系统资源，仅有保证独立运行的资源

独立性

同一进程中的不同线程之间的独立性要比不同进程之间的独立性低很多

系统开销

创建或撤销进程时，OS付出的开销大于创建或撤销线程时的开销

线程切换的代价远低于进程切换的代价

同一进程中的多个线程之间的同步和通信也比进程的简单

支持多处理机系统

线程的状态和线程控制块TCB

线程的状态

执行态、就绪态、阻塞态
状态转换与进程状态转换一样

线程控制块TCB

KST与ULT对应关系（线程的实现方式）

内核支持线程KST
用户级线程ULT

多对一：多个用户级线程映射到一个内核线程，高效

一对一：每个用户级线程映射到一个内核线程，允许并行

多对多：多个用户级线程映射为相等或小于数目的内核线程

第三章

处理机三级调度

高级调度（作业调度）

调度对象：作业
将外存上处于后备队列中的作业调入内存，并创建进程、分配必要的资源。将新创建的进程排在就绪队列上等待调度
主要用于多道批处理系统
每个作业只调入一次，调出一次

作业调度算法

先来先服务
短作业优先
优先权高优先
高响应比优先

中级调度（内存调度）

为提高内存利用率和系统吞吐量而引入，将暂时不能运行的进程调至外存等待，此时进程状态称为就绪驻外存状态或挂起状态
当这些进程具备运行条件且内存空闲，中级调度把就绪进程重新调入内存，修改状态为就绪状态
对换功能：短期调整系统负荷

低级调度（进程调度）

调度对象：进程
决定就绪队列中哪个进程获得处理机
应用于多道批处理、分时和实时OS

进程调度任务、机制、方式

进程调度的任务

保存处理机现场信息
按某种算法挑选进程
把处理器分配给进程

进程调度机制

排队器：将就绪进程按一定方式排成队列
分派器：把进程调度程序选定的进程从就绪队列中取出，进行上下文切换，把处理器分配给它
- 进行进程切换
- 转到用户态
- 开始执行被选中的进程
上下文切换机制：
- 保存当前进程上下文，装入分派程序上下文，分派程序运行
- 移出分派程序，装入新选进程上下文

进程调度方式

非抢占方式：进程完成或被阻塞才分配给其他进程
抢占方式：允许暂停正在执行的进程

调度准则

进程执行由CPU执行和I/O等待周期组成
进程执行在CPU区间和I/O区间之间切换

处理机调度算法的目标

普遍目标：资源利用率、公平性、平衡性、策略强制执行

批处理系统目标：平均周转时间短、系统吞吐量高、处理机利用率高
分时系统目标：响应时间快、均衡性
实时系统目标：截止时间的保证、可预测性

评价指标

批处理系统的目标

周转时间：从作业提交给系统到作业完成为止的这段时间间隔
- $周转时间=完成时间-到达时间$
- 平均周转时间： $T=\frac{1}{n}(\sum^n_{i=1}T_i)$
- 带权周转时间：权值为作业周转时间T与系统为之服务时间 $T_s$ $T_{s}$ 之比
  - $带权周转时间=周转时间/运行时间$
- 平均带权周转时间： $W=\frac{1}{n}(\sum^n_{i=1}\frac{T_i}{T_{s_i}})$
吞吐量：单位时间内完成的作业数
- $系统吞吐量=\frac{总共完成多少道作业}{总共花了多少时间}$
等待时间（进程调度）：进程在就绪队列中等待调度的所有时间之和
$等待时间=进程结束时间-进程到达时间-期间进程占用CPU的时间$ （若有I/O操作，还要减去I/O操作时间）
CPU利用率
$CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$

作业=程序+数据+作业说明书

作业调度：FCFS、SJF、PR、HRRN

作业调度

先来先服务调度算法FCFS
短作业优先调度算法SJF
优先级调度算法PR
高响应比优先调度算法HRRN

先来先服务调度算法FCFS

只考虑等待时间
公平

按照作业到达后备队列/进程到达就绪队列的先后次序来调度
非抢占方式
利于长作业/进程，不利于短作业
利于CPU繁忙型作业，不利于I/O繁忙作业/进程
不会导致饥饿

短作业优先调度算法SJF

只考虑执行时间
最优平均等待时间、最优平均周转时间

用于进程调度时称为短进程优先SPF算法

两种模式

非抢占式SJF：选择当前已到达且运行时间最短的
抢占式SJF：抢占发生在有比当前进程剩余时间片更短的进程到达时，也称最短剩余时间优先调度
- 有进程加入就绪队列时、一个进程完成时都需要调度

非抢占式SJF

抢占式SJF

优点：保证CPU的利用效率
缺点

只能估算进程的运行时间（估值不准确），所以常用于作业调度
对长作业不利
人-机无法实现交互
完全未考虑作业的紧迫程度
饥饿

优先级调度算法PR

既可用于作业调度，也可用于进程调度
基于作业/进程的紧迫程度，由外部赋予作业相应的优先级
- 每个进程都有一个优先数（整数）
- 小的优先数具有高优先级
- 目前主流的操作系统调度算法

优先级调度算法类型

非抢占式
抢占式

优先级类型

静态优先级：创建进程时确定优先数，在进程运行期间保持不变
动态优先级：创建进程时先赋予一个优先级，其值随进程的推进或等待时间的增加而改变

非抢占式优先级调度算法

优点：实现简单、考虑紧迫程度、灵活、响应时间快
缺点：饥饿-低优先级进程可能永远得不到运行
解决方法：老化-视进程等待时间的延长提高其优先数

高响应比优先调度算法HRRN

优先级： $优先级=\frac{等待时间+要求服务时间}{要求服务时间}$
响应比： $R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$
若等待时间相同，取运行时间短的，类似SJF
若运行时间相同，取等待时间长的，类似FCFS
非抢占式

进程调度：RR、多级反馈优先级队列

考量标准

等待时间：进程自进入就绪队列开始至进程占用CPU之间的时间间隔
$等待时间=进程结束时间-进程到达时间-期间进程占用CPU的时间$
周转时间：进程自进入就绪队列开始至进程结束之间的时间间隔
$周转时间=进程结束时间-进程到达时间$
CPU吞吐量：单位时间内运行结束的进程个数
响应时间
$响应时间 = 第一次被CPU调度执行的时刻 - 到达时间$

时间片轮转RR调度算法

机会均等

专为分时系统设计，类似FCFS，但增加抢占

每次取就绪队列队头的进程执行一个时间片，执行后将该进程插入队尾
若同时有新进程到达，则新进程先进入就绪队列

一般准则： $时间片/10>进程上下文切换时间内$

多级反馈队列调度FB算法

q=1的多级反馈队列就按时间片轮转方式算

若没有规定就绪队列数量，则算累计执行时间，累计到达该级时间片后强制放到下一级队尾，不断延申就绪队列数量
若规定了就绪队列数量为N，则在前N-1队列采用累计。第N个队列采用时间片轮转，每次被抢占后放回队尾，下一次仍执行时间片长度

按两级队列算，第二级队列采用时间片轮转

按不限队列数算，每个队列达到累计放入下一个队列

基于公平原则的调度算法

主要考虑调度的公平性
保证调度算法
- 性能保证，而非优先运行
- 保证处理机分配的公平性（处理机时间为 $\frac{1}{n}$ ）
公平分享调度算法
- 调度的公平性主要针对用户而言
- 使所有用户能获得相同的处理机时间或时间比例

实时调度

最早截止时间优先EDF调度算法

截止时间越早，优先级越高
既可用于抢占式调度，也可用于非抢占式调度

非抢占式调度用于非周期实时任务

抢占式调度用于周期实时任务

最低松弛度优先LLF算法

$松弛度=必须完成时间-剩余执行时间-当前时间$
紧急程度越高（松弛度越低），优先级越高

死锁

定义：指多个进程在运行过程中因争夺资源而造成的一种僵局，无外力作用不能再向前推进。

资源分配图

三种引起原因

竞争不可抢占资源
竞争可消耗性资源
进程推进顺序不当

四种必要条件

互斥
请求和保持
不可抢占
循环等待

预防中的三种破坏

破坏请求和保持：
要求进程在执行前一次性申请全部资源，只有没有占有资源时才可以分配资源
破坏非抢占：
- 若一个进程的申请没有实现，则它释放所有占有资源
- 先占的资源放入进程等待资源列表中
- 进程在重新得到旧的资源时可以重新开始
破坏循环等待：
对多种资源类型线性排序，并赋予不同序号，要求进程按照递增顺序申请资源

互斥不能改变

死锁避免：银行家算法

针对资源有多个实例
每一个进程必须事先声明使用的最大量
当一个进程请求资源，可能需要等待
当一个进程得到所有资源，必须在有限时间内释放

判断安全性

系统处于安全状态，因为 $<P_1,P_3,P_4,P_2,P_0>$ 满足安全标准

判断请求是否通过

死锁的检测和解除

简化进程资源图

解除

抢占资源：从一个或多个进程中抢占足够数量的资源给死锁进程
终止或撤销进程：终止系统中一个或多个死锁进程，直到打破循环环路，使死锁状态消除为止
- 终止所有死锁进程- 最简单
- 逐个终止进程

选择中断顺序

进程的优先级
进程需要的时间
进程使用的资源
进程是交互的还是批处理的

第四章

临界区的问题

临界资源

系统中某些资源一次只允许一个进程使用

临界区问题
临界区：进程中涉及临界资源的代码段
进入区：用于检查是否可以进入临界区的代码段
退出区：将临界区正被访问的标志恢复为未被访问标志
剩余区：其他代码

同步机制遵循准则

空闲让进
忙则等待
有限等待
让权等待（选）

进入区和退出区是负责实现互斥的代码段

软件同步机制-Peterson

$P_i$ 的进程：

do {
    flag[i] = TRUE;  // 表示进程P_i准备进入临界区
    turn = j;       // 让另一个进程有机会进入临界区
    while (flag[j] && turn == j);  // 如果另一个进程也在准备进入并且轮到了它，就等待
    临界区；        // 进入临界区执行代码
    flag[i] = FALSE; // 退出临界区，表示不再需要进入
    剩余区；        // 执行非临界区的代码
} while (TRUE);

turn：哪个进程可以进入临界区
flag：哪个进程想要进入临界区

共享变量

int turn=0;
turn==i  //Pi进入临界区
j=1-i;
boolean flag[2];
flag[0]=flag[1]=false; //初值
flag[i]=true;  //Pi准备进入临界区

硬件同步机制

进入锁测试之前关闭中断，完成锁测试并上锁之后才打开中断

Test-and-Set指令

当lock=FALSE时，表示该资源空闲；当lock=TRUE时，表示该资源正在被使用。
为每个临界资源设置一个布尔变量lock，初值为FALSE表示空闲

Boolean TS（Boolean *lock） {
	Boolean old ；
	old = *lock ；
	*lock = TRUE ；
	return old;
}

//共享数据
Boolean lock = FALSE;
//进程Pi
do{
	...
	while TS(lock);
	临界区;
	lock=FALSE;
	剩余区;
}while(1);

Swap指令

为每个临界资源设置一个全局的布尔变量lock，初值为FALSE。
每个进程中再设置一个局部的布尔变量key，通过交换来判断lock的取值

void swap（Boolean *a, Boolean *b）{
	Boolean temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
//共享数据
Boolean lock;
Boolean waiting[n];
//进程Pi
do{
	key=TRUE;
	do{
		swap(lock,key);
	}while(key!=FALSE);
	临界区操作;
	lock=FALSE;
	剩余区
}while(TRUE);

信号量机制

整型信号量

只能通过wait(S)（又称P(S)）和signal(S)（又称V(S)）来访问
忙等

wait(S){
	while(S<=0);
	S--;
}
signal(S){
	S++;
}

记录型信号量

去除忙等
信号量S有一个整数值S.value和一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB
初始化为一个非负整数值，表示空闲资源总数。非负值表示当前的空闲资源数，负值的绝对值表示当前等待临界区的进程数

typedef struct{
	int value;
	stuct process_control_block *list;
}semaphore;

wait(semaphore *S){  //请求一个单位的资源
	S->value--;  // 资源减少一个
	if(S->value<0) block(S->list); // 自我阻塞，放弃处理机
}
signal(semaphore *S){ //释放一个单位资源
	S->value++;   //资源增加一个
	if(S->value<=0) wakeup(S->list);   //唤醒等待队列中的一个进程
}

And型信号量

将进程在整个运行过程中需要的所有资源==一次性==全部分配给进程，进程使用完后一起释放

Swait(S1, S2, ..., Sn) {
    while (TRUE) {
        // 检查所有信号量 S1, S2, ..., Sn 是否都大于等于 1
        if (S1 >= 1 && ... && Sn >= 1) {
            // 如果所有信号量都满足条件，递减每个信号量的值
            for (i = 1; i <= n; i++) Si--;
            // 退出循环，进程可以继续执行
            break;
        } else {
            // 如果至少有一个信号量不满足条件（Si < 1）
            // 将进程放入第一个不满足条件的信号量 Si 的等待队列中
            place the process in the waiting queue associated 
            with the first Si found with Si < 1, and set the 
            program count of this process to the beginning of 
            Swait operation;
            // 进程进入等待状态，直到信号量条件满足
        }
    }
}

Ssignal(S1, S2, ..., Sn) {
    while (TRUE) {
        // 遍历所有信号量 S1, S2, ..., Sn
        for (i = 1; i <= n; i++) {
            // 递增每个信号量的值
            Si++;
            // 将所有等待在该信号量 Si 的队列中的进程移到就绪队列
            Remove all the process waiting in the queue 
            associated with Si into the ready queue;
        }
        // 退出循环，操作完成
        break;
    }
}

信号量集

是对AND信号量机制的扩充
信号量 $S_i$ 的测试值改为分配下限值 $t_i$ ，若 $S_i<t_i$ 则不予分配
分配后，进程对该资源的占用量为 $d_i$ ，进行 $S_i:=S_i-d_i$ 操作

1 2	Swait(S1，t1，d1 ；… ；Sn，tn，dn); Ssignal(S1，d1 ；… ；Sn，dn);

$(S_i, t_i, d_i)$

S_i（信号量标识）
t_i（分配下限值/测试值）
d_i（分配占用量）

应用

第五章

存储层次结构

CPU能访问的存储器只有内存和处理器的寄存器

存储管理的功能

内存分配和回收
内存保护
地址映射
内存扩充（逻辑扩充）

地址映射（地址变换、地址重定位）：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。

CPU执行指令按物理地址进行

物理地址（内存地址，绝对地址，实地址），可直接寻址，内存以字节为单位编址
逻辑地址（相对地址，虚地址）由CPU产生的地址

程序的装入和链接

内存保护的实现：硬件

基地址寄存器：保存最小合法物理内存地址（基地址）
界限寄存器：保存合法的地址范围大小（界限地址）
基地址≤物理地址＜（基地址+界限地址）

装入

绝对装入方式：逻辑地址和物理地址完全相同，连续空间
重定位装入方式：不需要硬件支持，装入时地址映射，静态
动态运行时装入方式：需要硬件支持，分散存放，利于共享

链接

经过编译得到的目标模块及库函数装配成装入模块

实现链接方式

静态链接
- 时间：生成可执行文件时
- 链接地址类型：在目标模块中记录符号地址，在可执行文件中改写为指令直接使用的逻辑地址
动态链接（装入时）：边装入边链接，便于修改、更新、共享
动态链接（运行时）：未被用到的目标模块都不会被调入内存，加快装入过程

对换与覆盖

对换

内存中暂时不能运行的调出到外存上，把已具备运行条件的调入内存
提高内存利用率

类型

整体对换：以整个进程为单位（处理机中级调度）
页面（分段）对换（部分对换）：以“页”或“段”为单位

对换区的管理

提高进程换入和换出的速度
采用连续分配方式

覆盖

解决问题：程序大小超过物理内存总和
只在内存中保留在任何时间都需要的指令和数据，不同部分相互替换

连续分配存储管理方式

为一个用户程序分配空间时，将所有程序装入到一段连续的物理内存中

单一连续分配

单道程序环境下，仅装有一道用户程序（整个内存的用户空间由该程序独占）

固定分区分配

划分分区

动态分区分配

可变分区分配，按进程大小动态划分分区大小

空闲分区表、空闲分区链

分配内存

按分配算法寻找空闲分区，若＞要求，分割，一个为要求的大小并分配，另一个分区留在空闲分区链（表）
有分区最小值size下限

内存回收

合并：首先检查回收区是否与其他空闲区相邻
- 若相邻则合并成一个空闲区，否则插入到空闲分区表
回收情况
- 只有前邻空闲区
- 只有后邻空闲区
- 既有前邻空闲区又有后邻空闲区
- 没有邻接空闲区：建立一个新表项，填写回收区起始地址和大小

基于顺序搜索的动态分区分配算法

依次搜索空闲分区链上的空闲分区

分配算法

首次适应算法
- 从头查找、第一个
下次适应算法（循环首次适应法）
- 从上次找到的空闲分区的下一个开始查找
最佳适应算法
- 按空闲区大小升序方式组织空闲分区表
- 从头查找，找到第一个合适分区（最佳）
最坏适应算法
- 按空闲区大小降序方式组织空闲分区表
- 分配时取第一项，若大小不能满足说明系统中无满足要求的空闲区，分配失败

基于索引的动态分区分配算法

快速适应算法

将空闲分区按容量大小进行分类，每一类具有相同容量，每一类单独设立一个空闲分区链表
在内存中设立管理索引表，每个表项对应一类空闲分区，并记录该类空闲分区链表表头指针

伙伴系统

分区大小为2的k次幂
将空闲分区按大小分类，每一类单独设立一个空闲分区双向链表
当需要为进程分配长度为n的存储空间时，先计算 i 的值，使 $2^{i-1} < n\leq 2^i$ ，在空闲分区大小为 $2^i$ 的空闲分区双向链表中寻找
若满足空间已用完：若存在大小为 $2^{i+1}$ 的空闲分区，则将该分区分为相等的两个分区，其中一个用于分配，另一个加入大小为 $2^i$ 的空闲分区的双向链表。若大小为 $2^{i+1}$ 的空闲分区也不存在，则查找大小为 $2^{i+2}$ 的分区并分割两次。以此类推
多次分割和多次合并：一次分配可能要进行多次分割，一次回收也可能进行多次合并
性能：分配和回收的性能取决于查找空闲分区的位置和分割、合并空闲分区的时间
- 时间性能：比分类搜索算法差，比顺序搜索算法好
- 空间性能：远优于分类搜索算法，比顺序算法略差

哈希算法

建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表对应于一个空闲分区链表的头指针
根据空闲区大小，通过计算哈希函数，得到在哈希表中的位置，找到对应的空闲分区链表

动态可重定位分区分配

连续分配方式存在的问题：碎片/零头问题

紧凑：向一个方向移动已分配的作业，使零散的小空闲区在另一方向连成一片

需硬件支持：重定位寄存器R存放程序的内存始址
进行紧凑处理时，不需对程序进行改动，只要修改重定位寄存器的值（即程序在内存中新的起始地址）
执行时，访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的
动态重定位：在指令运（程序执行期间）时，实现地址转换（相对地址转换为绝对地址）
所有分区都没有大于等于需求空间大小的，才进行重定位

分区的存储保护

上下界限寄存器
基址、限长寄存器
保护键

分页存储管理方式

物理块：把物理内存分成大小固定的块（大小为2的幂，通常1KB~8KB）
页：把逻辑内存分成相同固定大小的块
运行一个有N页大小的程序，需要找到N个空的页来装入程序
建立页表：翻译逻辑内存 → 物理内存
存在页内碎片：进程最后一页经常装不满，形成不可利用的碎片

若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址d公式为
$P=INT[\frac{A}{L}]$ ，INT为下取整函数
$d=[A]\mod L$ ，MOD为取余函数

系统页面大小L为1KB，设 A=2170B，则得到P=2,d=122。

页表

系统为每个进程建立了一张页表，记录在该进程的PCB中
页表作用：实现从页号到块号的地址映射
页表被保存在主存中

（页号+页内地址 → 块号+页内地址）
页表寄存器：存放页表在内存的始址和页表的长度
每一次的数据/指令存取需要两次内存访问，一次访问页表，一次访问数据/指令

快表（转换表缓冲器TLB）
有效访问时间EAT

查找快表需要的时间 $\lambda$
访问内存一次需要的时间为 $t$
命中率-在联想寄存器中找到页号的百分比，与联想寄存器大小有关， $a$

没有引入快表的有效访问时间 $EAT=2t$
引入快表后的有效访问时间 $EAT=\lambda ×a+(t+\lambda)(1-a)+t=2t+\lambda -t×a$

页表结构

两级页表
多级页表
反置页表

分段存储管理方式（大概率不考）

段页式存储管理方式

第六章虚拟存储器

常规存储器管理方式的特征：一次性、驻留性

虚拟存储器：调入功能、置换功能
虚拟存储器特征

多次性
对换性
虚拟性
离散性

实现方式

请求分页系统
请求分段系统
段页式虚拟存储器

请求分页存储管理方式

优点

可提供多个大容量的虚拟存储器
主存利用率大大提高
多道作业同时运行

缺点

缺页中断处理增加系统开销
页面的调入调出增加I/O系统的负担

硬件支持

请求页表机制

页表项：页号+物理块号+状态位P+访问字段A(访问次数)+修改位M+外存地址

缺页中断机构

缺页中断：发现缺页→调出缺页中断处理程序→根据外存地址将页调入内存
分配：内存有空闲块分配一页，调入页装入内存，修改页表对应项状态位和内存块号
淘汰：内存没有空闲块，淘汰某页，若被修改过写回外存
处理过程：保护CPU现场 → 分析中断原因 → 转入缺页中断处理程序 → 恢复CPU环境

缺页中断发生在指令执行期间，检查中断请求在CPU指令执行完成后

地址变换机构：与分页内存管理方式类似

内存分配

最少物理块数
分配策略
分配算法

最少物理块数确定

取决于硬件，取决于指令的格式、功能和寻址方式

分配策略

请求分页：固定/可变分配策略
置换分页：全局/局部置换
组合使用
- 固定分配，局部置换：固定分配，缺页直接换
- 可变分配，全局置换：预留空闲块队列，缺页先用空闲块，用完再换
- 可变分配，局部置换：根据缺页率调整，保持缺页率较低

分配算法

固定分配策略时
- 平均分配算法
- 按比例分配算法
  - $n$ 个进程，每个进程的页面数为 $S_i$
  - 页面数的总和为： $S=\sum^{n}_{i=1}S_i$
  - 可用的物理块总数为 $m$ ，每个进程分到的物理块数为 $b_i$
  - $b_i=S_i/S \times m$ ， $b_i$ 要取整，必须大于最小物理块数
- 考虑优先权的分配算法：一部分比例分配，一部分根据优先级，增加分配

页面调入策略

何时：预先分配、缺页时
何处：对换区、文件区(对换区不够时不会修改的文件)
调入方法：查找位置→查找空闲块(没有就使用页面置换算法)→读入空闲块，更新页表→重启用户进程

指标
访问页面成功(在内存)的次数 $S$
访问页面失败(不在内存)的次数 $F$
总访问次数 $A=S+F$
缺页率 $f=\frac{F}{A}=\frac{F}{S+F}$
缺页中断处理的时间 $t=f \times t_a +(1-f)\times t_b$

存取内存时间=200ns，平均缺页处理时间=8ms，若每1000次访问中有一个缺页中断，则t=?
$缺页率f=0.001$ ， $t=(1-f)\times 200ns+f \times 8ms=8.198ms$

页面置换算法

最佳置换算法OPT

理想状态
可保证获得最低的缺页率
被置换的是哪页：往后看，最久用不到的

最近最久未使用算法LRU

被置换的是哪页：往前看最久没有用过的

最少使用算法LFU

被置换的是哪页：往前看用的最少的

Clock置换算法

简单的Clock算法

改进型Clock算法

考虑页面的使用情况和置换代价
淘汰时，同时检查访问位A与修改位M

第1类(A=0，M=0)：最近既未被访问、又未被修改，是最佳淘汰页
第2类(A=0，M=1)：最近未被访问、但已被修改，并不是很好的淘汰页
第3类(A=1，M=0)：最近已被访问、但未被修改，该页有可能再被访问
第4类(A=1，M=1)：最近已被访问且被修改，该页有可能再被访问

页面缓冲算法PBA

空闲页面链表：保存空闲物理块
修改页面链表：保存已修改且需要被换出的页面，等被换出的页面数目达到一定值时，再一起换出外存

访问内存的有效时间EAT

$f$ 为缺页率， $\varphi$ 为缺页中断处理时间
$\text{EAT} =2t+f\times \varphi$
理解：不缺页的时候时间为 $2t$ ，缺页时额外加上中断处理时间 $\varphi$

抖动与工作集

抖动：一个进程的页面经常换入换出
根本原因：

同时在系统中运行的进程太多
分配给每一个进程的物理块太少，不能满足进程运行的基本要求

工作集：指在某段时间间隔 $\Delta$ 里进程实际要访问页面的集合

抖动预防方法：

采取局部置换策略（对于可变分配方式）：将抖动限制在较小范围
把工作集算法融入到处理机调度中
- 检查每个进程在内存中的驻留页面是否足够
- 足够则调入新的作业；不够则先为缺页率高的作业增加新的物理块
利用“L=S”准则调节缺页率
- L为缺页之间的平均时间，S为平均缺页服务时间
- L与S接近，磁盘和处理机才能都达到最大利用率
选择暂停进程

请求分段存储管理方式

硬件支持

请求段表机制
多了增补位和存取方式位
缺段中断机构
地址变换机构

分段的共享与保护

第七章输入/输出系统

I/O系统的功能、模型和接口

管理的主要对象：I/O设备和对应的设备控制器
主要任务

完成用户提出的I/O请求
提高I/O速率
改善I/O设备的利用率

基本功能

隐藏物理设备细节
保证OS与设备无关
提高处理机和I/O设备的利用率
对I/O设备进行控制
确保对设备的正确共享
处理错误

I/O系统所在层

中断处理程序
设备驱动程序
与设备无关的I/O软件

I/O系统接口

块设备接口
流设备接口
网络通信接口

I/O设备和设备控制器

I/O设备

按使用特性分类：存储设备、I/O设备
按传输速率分类：低速/中速/高速设备
按信息交换单位分类：块设备/字符设备
按设备共享属性分类：独占/共享设备

设备控制器

功能：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
设备控制器是CPU与I/O设备之间的接口
设备控制器是一个可编址的设备
基本功能
- 接收和识别命令
- 数据交换
- 标识和报告设备的状态
- 地址识别
- 数据缓冲区
- 差错控制
组成
- 设备控制器与处理机的接口
- 设备控制器与设备的接口
- I/O逻辑

驱动程序将抽象I/O命令转换成具体的命令和参数等装入设备控制器的相应寄存器，由控制器执行命令、实施对I/O设备的控制。

具体方法：采用特定I/O指令、采用内存映像I/O形式

I/O通道
使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来

通道指令类型单一、没有独立的内存
类型：字节多路/数组选择/数组多路
单通道I/O系统、多通道I/O系统

I/O设备的控制方式

使用轮询的可编程I/O方式
使用中断的可编程I/O方式
直接存储器访问（DMA）方式
I/O通道控制方式

通道程序：由一系列通道指令构成的

中断

中断：指CPU对I/O设备发来的中断信号的一种响应
陷入：指CPU内部事件所引起的中断
中断向量表：存放每个设备的中断处理程序的入口地址，为每个设备的中断请求作为一个中断号
中断源：引起中断的事件
处理多中断信号源：屏蔽/嵌套
中断处理程序：有无中断信号→保护CPU现场→转入处理程序→处理中断→恢复CPU现场并退出中断

设备驱动程序

功能

接收由与设备无关的软件发来的命令和参数，并将命令中的抽象I/O要求转换为与设备相关的低层操作序列
检查用户I/O请求的合法性
发出I/O命令
及时响应由设备控制器发来的中断请求

特点

实现与设备无关的软件和设备控制器直接通信和转换的程序
与设备控制器以及I/O设备特性紧密相关
基本部分固化在ROM中
允许可重入

设备处理方式

为每类设备设置一个进程，专门用于执行这类设备的I/O操作
在整个系统中设置一个I/O进程，专门用于执行系统中各类设备的I/O操作
不设置专门的设备处理进程，而只为各类设备设置相应的设备驱动程序

执行过程

将抽象要求转换为具体要求
对服务请求进行校验
检查设备的状态
传送必要的参数
启动I/O设备

框架
设备驱动程序与外界的接口

与操作系统内核的接口
与系统引导的接口
与设备的接口

设备驱动程序的组成

设备驱动程序的注册与注销
设备的打开与释放
设备的读/写操作
设备的控制操作
设备的中断与轮询

与设备无关的I/O软件

实现设备独立性

设备分配与回收

逻辑设备名映射到物理设备名

在应用程序中请求使用I/O设备时，应使用逻辑设备名；而系统只识别物理设备名
逻辑设备表LUT

I/O调度

用户层的I/O软件

大部分I/O软件都放在OS内部，仍有一小部分在用户层

系统调用与库函数

假脱机系统

假脱机技术（SPOOLing）

为了缓和CPU的高速性与I/O设备的低速性间的矛盾而引入了脱机输入、脱机输出技术

外围操作与CPU对数据的处理同时进行，这种在联机情况下实现的同时外围操作称为SPOOLing
输入井和输出井

在磁盘上开辟的两个大存储空间
输入井：模拟脱机输入时的磁盘设备，用于暂存输入设备输入的数据
输出井：模拟脱机输出时的磁盘，用于暂存用户程序的输出数据

输入缓冲区和输出缓冲区

缓和CPU和磁盘之间速度不匹配的矛盾
输入缓冲区：用于暂存由输入设备送来的数据，以后再传送到输入井
输出缓冲区：用于暂存从输出井送来的数据，以后再传送给输出设备

输入进程Sp_i、输出进程Sp_o

井管理程序
用于控制作业与磁盘井之间信息的交换

特点

提高了I/O速度
将独占设备改造为共享设备
实现了虚拟设备功能

假脱机打印机系统

缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件组成；更多的是利用内存

引入原因

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

单缓冲区（单向传输）

双缓冲区（双向传输）

环形缓冲区

多个缓冲区

空缓冲区R
已装满数据的缓冲区G
正在使用的现行工作缓冲区C

多个指针

指示计算进程下一个可用缓冲区G的指针Nextg
指示输入进程下次可用的空缓冲区R的指针Nexti
指示计算进程正在使用的缓冲区C的指针Current

Nextg追上Nexti，输入小于计算，受I/O限制
Nexti追上Nextg，计算小于输入，受计算限制

缓冲池

空闲缓冲队列emq
输入队列inq
输出队列out
4种工作缓冲区

缓存Cache

磁盘

结构

盘面（磁头）
磁道（柱面）
扇区：标识符字段、数据字段
磁盘密度

磁盘的类型

硬盘/软盘
单片盘/多片盘
固定头磁盘/移动头磁盘

磁盘容量

硬盘容量=柱面 × 磁头 × 扇区 × 扇区容量
软盘容量=面 × 磁道 × 扇区 × 扇区容量

磁盘访问时间

寻道时间 $T_s$
$T_s=m\times n+k$

启动磁臂的时间 $k$
磁头移动 $n$ 条磁道所花费的时间
$m$ 为常数，与磁盘驱动器的速度有关。
一般磁盘 $m=0.2$ ，高速磁盘 $m≤0.1$
$k$ 约为2ms

旋转延迟时间 $T_{\tau}$ （扇区转到磁头下）
$T_{\tau}=\frac{1}{2r}$

r 为磁盘每秒的转数

传输时间 $T_t$
$T_t=\frac{b}{rN}$

N为一条磁道上的字节数，b为读/写的字节数，r为磁盘每秒的转数

访问时间 $T_a$
$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$

磁盘调度方法

目标：使磁盘平均寻道时间最小

先来先服务FCFS

最短寻道时间优先SSTF

基于扫描的磁盘调度算法（SCAN/电梯调度算法）

考虑距离和当前移动方向

循环扫描算法CSCAN

磁头从磁盘一端移到另一端（该方向最远的请求），随着移动不断的处理请求。
当磁头移到另一端时，马上返回到磁盘开始（反方向最远的请求），返回时并不处理请求

NStepSCAN算法

按FCFS算法依次处理子队列
每个子队列使用SCAN算法

FSCAN算法

一是当前所有请求队列，按SCAN算法调度
二是扫描期间，新出现的请求队列，推迟到下一次扫描时处理

第八章文件管理

文件和文件系统

数据项

基本数据项（字段）：描述一个对象的某种属性
组合数据项：由若干个基本数据项组成

记录

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性
关键字：唯一能标识一个记录的数据项

文件：具有文件名的一组相关元素的集合

有结构文件（记录）、无结构文件（字符流）
文件系统中文件是最大的数据单位

文件名和文件类型

扩展名：文件名后面的若干个附加字符
文件类型

按用途分类：系统/用户/库文件
按文件中数据的形式分类：源/目标/可执行文件
按存取控制属性分类：只执行/只读/读写文件
按组织形式和处理方式分类：普通/目录/特殊文件

文件系统的层次结构

后面的来不及整理了~