OS理论笔记

\(\mathcal{Author:gpf}\)

引论

操作系统的作用

用户与计算机硬件系统的接口（API/GUI）
系统资源的管理
- 分配、控制处理机
- 内存的分配与回收
- I/O设备的分配与操纵
- 文件的存取、共享和保护
实现对计算机资源的抽象

UI：User Interface，用户界面

API：Application Programming Interface，应用程序编程接口。API相同，同一源码重新编译后即可运行

ABI：Application Binary Interface，应用程序二进制接口。ABI相同，同一源码无须重新编译即可运行

ISA：Instruction Set Architecture，指令集架构。

操作系统的进化

批处理

把用户提交的作业成批送入计算机，由作业调度程序自动选择作业运行。

无须人工参与，节省排队时间
同一时刻仅一个软件（作业）独占所有资源
CPU等待IO完成，浪费时间

联机批处理：主机高速CPU运行监督程序，负责IO

脱机批处理：增加一台不与主机直接相连而专门用于与输入/输出设备打交道的卫星机

多道程序设计

允许多个程序同时进入内存并运行。使CPU得到充分利用，同时也改善I/O设备和内存的利用率，从而提高了整个系统的资源利用率和系统吞吐量（即单位时间内处理作业（程序）的个数），最终提高了整个系统的效率。

系统吞吐量大
资源利用率高
平均周转时间长
无法提供交互能力

分时系统

多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源。

支持多用户、多程序同时运行

分时技术：把处理机的运行时间分成很短的时间片，时间片轮流把处理机分配给各联机作业使用

其他

微内核：内核中只包括中断处理、进程通信（IPC）、基本调度等。文件系统、网络功能、内存管理、设备管理等作为服务在微内核上运行。

易于实现、可靠性高、可移植性好、配置灵活、适应分布式环境
速度较慢

系统引导

Bootloader

引导加载程序是系统加电后运行的第一段软件代码，称为Bootloader，是在操作系统内核运行之前运行的一段小程序

Booter:初始化系统硬件使之运行起来，至少是部分运行起来
Loader:将操作系统映像加载到内存中，并跳转到操作系统的代码运行

Bootloader的实现严重依赖于具体硬件，难以用一个Bootloader支持所有CPU和系统

U-Boot等Bootloader大多分为stage1和stage2两大阶段

stage1：依赖于CPU体系结构的代码（如设备初始化），可用汇编语言实现
stage2：通常C语言实现，可读性、移植性更好

MIPS

32位下，共有4G程序地址空间

kuseg(0x0000_0000-0x7FFF_FFFF)：用户可用的地址，需经过MMU转换
kseg0(0x8000_0000-0x9FFF_FFFF)：清零最高位即可映射到物理地址，需通过cache
kseg1(0xA000_0000-0xBFFF_FFFF)：清零高三位即可映射到物理地址，无须cache
kseg2(0xC000_0000-0xFFFF_FFFF)：核心态可用，需经过MMU转换

内存管理

地址空间：程序使用的逻辑地址的集合

存储空间：存储信息的物理地址的集合

单道程序环境下，可进行静态地址翻译（程序运行之前确定所有物理地址），且地址独立、地址保护

多道程序的存储管理

内碎片：指分配给作业的存储空间中未被利用的部分

外碎片：指系统中无法利用的小的空闲分区

跟踪内存：

位图表示法，每个分配单元赋予一个字位，记录该分配单元是否闲置
链表表示法，将空闲单元用链表连接起来

固定式分区

把内存划分为若干个固定大小的连续分区。

易于实现，开销小。
内碎片造成浪费，分区总数固定，限制了并发执行的程序数目。

可变式分区

分区的边界可以移动，即分区的大小可变。

无内碎片
有外碎片

分配算法

首次适应算法（First Fit）：从空白区域链的始端开始查找，选择第一个足以满足请求的空白块。——低地址留下很多难以利用的小的空闲分区
下次适应算法（Next Fit）：从上次查找结束的地方开始，只要找到一个足够大的空白区。——缺乏大的空闲分区
最佳适应算法（Best Fit）：寻找大小最接近于作业所要求的存储区域——剩下的空闲区太小
最坏适应算法（Worst Fit）：总是寻找最大的空白区——需要大空间的作业得不到满足
快速适应算法：把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。——查找效率高，不会对任何分区分割；算法复杂，系统开销大
伙伴系统：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴” 。具体实现如下

程序的存储分配

分配方式

直接指定。程序员在编写程序时指定
静态分配。程序员编程时,或由编译程序产生的目的程序,均可从其地址空间的零地址开始；当装配程序对其进行链接装入时才确定它们在主存中的地址。
动态分配。作业在存储空间中的位置,在其装入时确定,在其执行过程中可根据需要申请附加的存储空间,而且一个作业已占用的部分区域不再需要时,可以要求归还给系统。

由源码到可执行

编译：用户源程序->若干个目标模块
链接：目标模块+库函数->可装载模块（通常是单一可执行文件）
- 静态链接：用户一个工程中所需的多个程序采用静态链接的方式链接在一起。当我们希望共享库的函数代码直接链接入程序代码中，也采用静态链接方式
- 动态链接：用于链接共享库代码。当程序运行中需要某些目标模块时，才对它们进行链接，具有高效且节省内存空间的优点。但相比静态链接，使用动态链接库的程序相对慢。
装入：可装载模块->装入内存
- 一般采用动态运行时装入方式

为了保证程序在内存中的位置可以改变。装入程序把装入模块装入内存后，并不立即把装入模块中相对地址转换为绝对地址，而是在程序运行时才进行

程序段

一个程序主要由 bss段、data段、text段三个组成的。在C语言之类的程序编译完成之后，已初始化的全局变量保存在data 段中，未初始化的全局变量保存在bss 段中。

bss段（bss segment）：用来存放程序中未初始化的全局变量的一块内存区域。属于静态内存分配。
data段（data segment）：用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
text段（code segment/text segment）：用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读(某些架构也允许代码段为可写，即允许修改程序)

text和data段在链接后的可执行文件中

gcc:

cc1：预处理器和编译器
as：汇编器
collect2：链接器

程序运行

栈帧与调用规范

当前函数A调用子函数B，会将子函数B的参数压到自己的栈帧里，并且先压最后一个参数。

装载

一个segment在文件中的大小小于等于其在内存中的大小

作业、进程和程序

一个作业通常包括程序、数据和操作说明书3部分。每一个进程由进程控制块PCB、程序和数据集合组成。这说明程序是进程的一部分，是进程的实体。因此，一个作业可划分为若干个进程来完成，而每一个进程由其实体——程序和数据集合。一个程序可以作为多个进程的运行程序；一个进程也可以运行多个程序

页式存储

机制

以32位逻辑地址、二级页表、每级页表大小4KB为例

虚拟地址分为3部分，31-22位这10位代表一级页表的第几项，21-12位这10位代表二级页表的第几项，页内偏移量则是对应的物理页中的偏移。

设虚拟地址为 va ，一级页表基地址为 pgdir ， PDX(va) 代表高10位，PTX(va) 代表中间10位。

存取过程先拿到一级页表基地址和虚拟地址高10位，从而找到对应的一级页表表项。即 pgdir+PDX(va) 为对应表项的物理地址，*(pgdir+PDX(va)) 为一级页表表项的内容，记为 pde=*(pgdir+PDX(va))

然后，pde 是二级页表的基地址，从而通过 pde+PTX(va) 拿到对应的二级页表表项的物理地址，*(pde+PTX(va)) 为二级页表表项的内容，记为 pte

pte 就是虚拟地址对应的物理页的地址，此时只需将 pte 低12位换成 va 的低12位就拿到 va 对应的物理地址了。

使得逻辑地址可以大于物理地址大小
多级页表可解决一级页表占用存储空间较大的问题
MMU可解决内存访问效率下降的问题（不分页访存1次，二级页表访存3次）

页目录自映射

仍然以32位逻辑地址、二级页表、每级页表大小4KB为例

32位逻辑地址->2^{20个页表->每个页表项4字节->4MB->2}10个一级页表->4KB

其中，一级页表称页目录，所有页目录项共占用4KB空间，刚好和页表大小一致。因此，可以将页目录项作为特殊的页表，放入二级页表项中

设所有页表（二级页表）的基地址为 PTbase ，共2^20个页表项，总共占用4MB空间。其中有一个页表大小（4KB）放的是页目录，它的基地址设为 PDbase ，是页表基地址在整个逻辑地址中的相对位置映射到4MB中的位置，即 PDbase=(PTbase>>22)<<12+PTbase 。右移22，得到页表基地址是逻辑空间中的第几页，左移12，乘以每页的大小。自映射目录表项 PDE=(PDbase>>22)<<12+PDbase

缺页错误处理过程

当进程执行过程中需访问的页面不在物理存储器（内存）中时，会引发发生缺页中断，进行所需页面换入，步骤如下：

陷入内核态，保存必要的信息（OS及用户进程状态相关的信息）。（现场保护）
查找出来发生页面中断的虚拟页面（进程地址空间中的页面）。这个虚拟页面的信息通常会保存在一个硬件寄存器中，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析该指令，通过分析找出发生页面中断的虚拟页面。（页面定位）
检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程。（权限检查）缺页错误处理过程
查找一个空闲的页框(物理内存中的页面)，如果没有空闲页框则需要通过页面置换算法找到一个需要换出的页框。
如果找的页框中的内容被修改了，则需要将修改的内容保存到磁盘上。（注：此时需要将页框置为忙状态，以防页框被其它进程抢占掉）（旧页面写回）
页框“干净”后，操作系统将保存在磁盘上的页面内容复制到该页框中。
当磁盘中的页面内容全部装入页框后，向操作系统发送一个中断。操作系统更新内存中的页表项，将虚拟页面映射的页框号更新为写入的页框，并将页框标记为正常状态。（更新页表）
恢复缺页中断发生前的状态，将程序指针重新指向引起缺页中断的指令。（恢复现场）
程序重新执行引发缺页中断的指令，进行存储访问。（继续执行）

页面置换算法

先进先出（First-in, First-out）：先调入内存的页面先被置换出去

改进的FIFO：A是FIFO队列中最旧的页面，且其放入队列后没有被再次访问，则A被立刻淘汰；否则如果放入队列后被访问过，则将A移到FIFO队列头，并且将访问标志位清除。

改进的FIFO之Clock：环形队列，产生缺页错误时，当前指针指向C，如果C被访问过，则清除C的访问标志，并将指针指向下一位；如果C没有被访问过，则将新页面放入到C的位置, 置访问标志，并将指针指向下一位。

最近最少使用（LRU）：设置一个特殊的栈，保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈底始终是最近最久未使用页面的页面号

老化算法（AGING）：为每个页面设置一个移位寄存器，并设置一位访问位R，每隔一段时间，所有寄存器右移1位，并将R值从左移入

段式存储

每个作业的地址空间是由一些分段构成的，每段都有自己的名字（通常是段号），且都是一段连续的地址空间。逻辑地址结构为段号+位移量（加起来不一定是32位）

段表

• 段表记录了段与内存位置的对应关系。

• 段表保存在内存中。

• 段表的基址及长度由段表寄存器给出。

• 访问一个字节的数据/指令需访问内存两次 (段表一次，内存一次)

地址变换过程

系统将逻辑地址中的段号 S 与段表长度 TL 进行比较。
- 若 S>TL，表示段号太大，是访问越界，于是产生越界中断信号。
- 若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的始址。
再检查段内地址 d，是否超过该段的段长 SL。
- 若超过，即 d >SL，同样发出越界中断信号。
- 若未越界，则将该段的基址与段内地址 d 相加，即可得到要访问的内存物理地址

优缺点

分段系统易于实现段的共享，对段的保护也十分简单。
处理机要为地址变换花费时间；要为表格提供附加的存储空间。
为满足分段的动态增长和减少外碎片，要采用拼接手段。
在辅存中管理不定长度的分段困难较多。
分段的最大尺寸受到主存可用空间的限制。

段页式

将用户程序分成若干个段（段式），并为每一个段赋一个段名，再把每个段分成若干个页（页式）。地址结构由段号、段内页号、及页内位移三部分所组成

进程与并发程序设计

一些概念

并发：两个活动在某一指定时间下，无论在同一处理机还是不同处理机，都在各自的起点和终点之间的某一处

并行：两个程序在同一时间度量下同时运行在不同的处理机上

进程特征：

并发
共享
不确定性

并发条件——Bernstein条件：

定义 \(R(S_i)\) 为进程 \(S_i\) 的读子集，\(W(S_i)\) 为 \(S_i\) 的写子集，则当一下条件同时成立时，进程 \(S_1\) 和 \(S_2\) 可并发

\(R(S_1)\cap W(S_2)=\emptyset\)
\(W(S_1)\cap R(S_2)=\emptyset\)
\(W(S_1)\cap W(S_2)=\emptyset\)

原语：由若干条指令所组成的指令序列，来实现某个特定的操作功能。

连续不可分割
操作系统核心组成部分
内核态下执行，且常驻内存

竞争：两个或多个进程对同一共享数据同时进行访问，而最后的结果是不可预测的，它取决于各个进程对共享数据访问的相对次序。这种情形叫做竞争。

竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关

临界资源：我们将一次仅允许一个进程访问的资源称为临界资源

临界区：每个进程中访问临界资源的那段代码称为临界区。

互斥：某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但无法限制访问者对资源的访问顺序

同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。

互斥机制设计上的原则：

空闲让进：临界资源处于空闲状态，允许进入临界区
忙则等待：临界区有正在执行的进程，所有其他进程不可进入临界区
有限等待：对要求访问临界区的进程应在保证在有限时间内进入自己的临界区，避免死等
让权等待：当进程（长时间）不能进入自己的临界区时，应立即释放处理机，尽量避免忙等。

线程

进程是资源分配的基本单位，线程是处理机调度的基本单位

每个线程由自己的堆栈

线程安全!=可重入

用户级线程：线程在用户空间，通过Library模拟，不需要或仅需极少的内核支持

优点：
- 线程切换与内核无关
- 线程调度由应用决定，易优化
- 可运行在任何操作系统上
缺点：
- 系统调用时阻塞所有属于此进程的线程
- 线程间无法并行

内核级线程：

优点：
- 可并行
- 内核中的一些处理可以通过多线程实现
- 涉及两种模式的切换

互斥的实现

忙等

Dekker

//进程P
pturn=true;
while(qturn){
    if(turn==1){
		pturn=false;
        while(turn==1);
        pturn=true;
    }
}
/*临界区*/
turn=1;
pturn=false;

//进程Q
qturn=true;
while(pturn){
    if(turn==0){
		qturn=false;
        while(turn==0);
        qturn=true;
    }
}
/*临界区*/
turn=0;
qturn=false;

信号量

使用一种新的变量类型（semaphore）作为信号量。信号量使用前必须初始化，初始化后只能通过PV操作访问，PV操作不受进程调度的打断。

Type semaphore = record
	value : integer;
	L : list of process;
end
Procedure P(S)
	var S : semaphore;
	begin 
		S.value := S.value -1;
		if S.value<0 then block(S.L);
	end
procedure V(S)
	var S : semaphore;
	begin
		S.value := S.value + 1;
		if S.value<=0 then wakeup(S.L)
	end

P操作分配资源，V操作释放资源。

经典进程同步问题

生产者-消费者

问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。

semaphore mutex =1;	//互斥
semaphore empty=N;	//空闲数量
semaphore full=0;	//产品数量
ItemType buffer[0..n-1];
int in = 0, out =0;
producer() {
	while(true){
		生产产品nextp;
		P(empty);
		P(mutex);
		buffer[in] = nextp;
		in = (in + 1) MOD n;
		V(mutex);
		V(full);
	}
}
consumer() {
	while(true){
		P(full);
		P(mutex);
		nextc = buffer[out];
		out = (out + 1) MOD n;
		V(mutex);
		V(empty);
		消费nextc中的产品
	}
}

读者-写者问题

问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个，即“读－写”互斥，“写－写”互斥，“读－读”允许

读者优先

semaphore wmutex =1;	//允许写
int readcount=0;	//正在读的数量
semaphore mutex =1;	//对readcount的互斥

//Writer
P(wmutex);
	write;
V(wmutex);

//Reader
P(mutex);
	if readcount=0 then P(wmutex);
	readcount := readcount +1;
V(mutex);
read
P(mutex)
	readcount := readcount -1;
if readcount=0 then V(wmutex);
V(mutex)

读写公平

semaphore wmutex =1;	//允许写
int readcount=0;	//正在读的数量
semaphore mutex =1;	//对readcount的互斥
semaphore rwmutex =1;	//对readcount的互斥

//Writer
P(rwmutex);
P(wmutex);
	write;
V(wmutex);
V(rwmutex);

//Reader
P(rwmutex);
P(mutex);
	if readcount=0 then P(wmutex);
	readcount := readcount +1;
V(mutex);
V(rwmutex);
read
P(mutex)
	readcount := readcount -1;
if readcount=0 then V(wmutex);
V(mutex)

写者优先

哲学家进餐问题

问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。

如何保证哲学家们的动作有序进行？如：不出现相邻者同时进餐；不出现有人永远拿不到筷子

思路：

至多只允许四个哲学家同时（尝试）进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。设置信号量room=4。（破除资源互斥）
对筷子进行编号，奇数号先拿左，再拿右；偶数号相反。（破除循环等待）
同时拿起两根筷子，否则不拿起。（破除保持等待）

理发师问题

理发店里有1位理发师、1把理发椅和n把供等候理发的顾客坐的椅子；如果没有顾客，理发师便在理发椅上睡觉，当一个顾客到来时，叫醒理发师；如果理发师正在理发时，又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

int waiting = 0;
semaphore mutex=1;
semaphore custormers=0;
semaphore barber=0;

Barber:
while(true) {
	P(custormers);
	P(mutex);
	waiting --;
	V(mutex);
	V(barber);
	CutHair();
}

Custom_i:
P(mutex);
if (waiting < N) {
	waiting ++;
	V(mutex);
	V(custormers);
	P(barber);
	GetCutHair();
}
else {
	V(mutex);
}

进程调度

进程切换步骤：

保存处理器的上下文，包括程序计数器和其它寄存器
用新状态和其它相关信息更新正在运行进程的PCB
把进程移至合适的队列：就绪、阻塞
选择另一个要执行的进程更新被选中进程的PCB（新状态等）
从被选中进程中重装入CPU 上下文

评价指标

周转时间：作业从提交到完成所经历的时间，包括执行、等待时间

平均周转时间：所有作业周转时间的平均值

带权周转时间：周转时间/服务时间

响应时间：用户输入一个请求，系统首次给出响应的时间

吞吐量：单位时间内所完成的作业数（不等于平均周转时间的倒数）

处理机利用率：忙碌时间/总时间

调度细节

进程优先级：

静态优先级：运行过程中不再改变
动态优先级：运行过程中可以动态变化

进程就绪队列：

按优先级排队，CPU调度优先级较高的进程执行
创建时都进入第一级，随进程运行，可能降低某些进程的优先级

占用CPU的方式：

不可抢占式：一旦处理器被分配给一个进程，就死赖着不走，直到进程调度
抢占式：就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时，让位

进程分类：

CPU密集/IO密集

批处理/交互式进程/实时进程

批处理调度算法

特点：不要求交互、实时性不强

先来先服务FCFS

字面意思

短作业优先SJF

对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业

优点：

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
提高系统吞吐量

缺点：

对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级
难以准确估计作业（进程）的执行时间，从而影响调度性能。

最短剩余时间SRTF

将SJF改为抢占式

缺点：源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象

最高响应比优先HRRF

在每次选择作业投入运行时，先计算后备作业队列中每个作业的响应比RP(响应优先级)，然后选择其值最大的作业投入运行。

\(\text{RR}=\dfrac{\text{已等待时间+要求运行时间}}{要求运行时间}\)

短作业容易得到较高的响应比，长作业等待时间足够长后，也将获得足够高的响应比。饥饿现象不会发生

缺点：每次计算各道作业的响应比会有一定的时间开销，性能比SJF略差。

交互式系统的调度算法

时间片轮转(Round Robin)算法

【排队】将系统中所有的就绪进程按照FCFS原则，排成一个队列。

【轮转】每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。

【中断】在一个时间片结束时，发生时钟中断。

【抢占】调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。

【出让】进程可以未使用完一个时间片，就出让CPU（如阻塞）。

多级队列算法

引入多个就绪队列，每个队列固定归入一个队列，不同队列可有不同的优先级、时间片长度、调度策略等。

多级反馈队列算法

设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍

新进程进入内存后，先投入队列1的末尾，按“时间片轮转”算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按“时间片轮转”算法调度；如此下去，降低到最后的队列，则按“FCFS”算法调度直到完成。

仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾

问题：优先级倒置（高优先级进程被低优先级进程阻塞）。解决：优先级置顶、优先级继承（同一临界资源）

实时系统的调度算法

特点：实时性强

静态表调度

事先确定固定的调度方案

单调速率调度

优先级静态固定分配：优先级与周期成反比，周期越短优先级越高。优先级高的任务先被调度。如果两个任务的优先级一样，当调度它们时，RM算法将随机选择一个调度

任务在周期起点释放，高优先级任务可抢占低优先级任务的执行

最早截止时间优先算法

任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度（动态优先级）

如果两个任务的优先级一样，当调度它们时，EDF算法将随机选择一个调度

最低松弛度优先算法LLF

根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急度越高，其优先级越高，并使之优先执行。

松弛度=进程截止时间-本身剩余运行时间-当前时间

=进程最晚开始时间-当前时间

多处理机调度

（对称式多处理系统SMP）

集中控制：静态、动态分配。分散控制：自调度

静态分配：每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。
- 优点：调度算法开销小。
- 缺点：容易出现忙闲不均
动态分配：所有CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。可防止系统中多个处理器忙闲不均。
自调度：整个系统采用一个公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。可采用单处理机的（成熟）调度技术，是最常用的算法，实现时易于移植。
- 优点：不需要专门的处理机从事任务分派工作。
- 缺点：队列同步开销：各处理机共享就绪队列；缓存更新开销：被阻塞的进程重新运行时不一定仍在阻塞前的处理机上运行，那么高速缓存中的内容需要重置；线程协作开销：由于合作中的几个线程没有同时运行而受阻，进而被切换下来
成组调度：将一个进程中的一组线程，每次分派时同时到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行
- 优点：通常这样的一组线程在应用逻辑上相互合作，成组调度提高了这些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统吞吐量。每次调度可以完成多个线程的分派，在系统内线程总数相同时能够减少调度次数，从而减少调度算法的开销
专用处理机调度：为进程中的每个线程都固定分配一个CPU，直到该线程执行完成（多用于CPU数量众多的高度并行系统）
- 优点：线程执行时不需切换，相应的开销可以大大减小，推进速度更快。
- 缺点：线程阻塞时，造成CPU的闲置。

死锁

定义：一组进程中，每个进程都无限等待被该组进程中其它进程所占有的资源，在无外力介入的条件下，将因永远分配不到资源而无法运行的现象。

发生原因：资源竞争、并发执行的顺序不当

发生的必要条件

互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
请求且占有条件：指进程已经占有至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
环路等待条件：
指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

活锁：任务一直尝试、失败、尝试、失败，但没有被阻塞

饥饿：资源分配不公导致长时间等待

死锁预防

破坏死锁的产生条件

某系统中有n个进程和m台打印机，系统约定：打印机只能一台一台地申请、一台一台地释放，每个进程需要同时使用的打印机台数不超过m。如果n个进程同时需要使用打印机的总数小于m+n，试讨论，该系统可能发生死锁吗? 并简述理由。

答：不可能。最坏情况下，n个进程同时申请了m+n-1台打印机，但每个进程都1差台才能完成，则实际已经分配了m-1台，还剩一台打印机可分配给任意进程解除等待状态，因此不会死锁

死锁避免

在资源分配之前进行判断

安全序列：一个进程序列<P1，P2，...，Pn>是安全的，是指若对于每一个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj（j < i）当前占有资源之和所满足，则<P1，P2，...，Pn>为一个安全序列

安全状态：系统存在一个安全序列。否则为不安全状态（但不一定死锁，但死锁必不安全）。

银行家算法：假定顾客借款分成若干次进行；并在第一次借款时，能说明他的最大借款额。具体算法：顾客的借款操作依次顺序进行，直到全部操作完成；银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；安全时，贷款；否则，暂不贷款

死锁检测

死锁解除

撤销进程：使全部死锁的进程夭折掉；按照某种顺序逐个地撤消（回退）进程，直至有足够的资源可用，死锁状态消除为止。
剥夺资源：使用挂起/激活挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程

IO

IO设备分为块设备和字符设备

IO控制技术

程序控制

称轮询或查询方式I/O，它由CPU代表进程向I/O模块发出指令，然后进入忙等状态，直到操作完成之后进程才能够继续执行。

中断驱动

当I/O操作结束后由设备控制器主动地来通知设备驱动程序说这次结束，而不是设备驱动程序不断地去轮询看看设备的状态。

优点：CPU不必忙等，提高CPU利用率，可以处理不确定事件
缺点：每次输入、输出一个数据都要中断CPU，多次中断浪费CPU时间

DMA

直接存储器访问方式，是由一个专门的控制器来完成数据从内存到设备或者是从设备到内存的传输工作。

优点：CPU只需干预I/O操作的开始和结束，而其中的一批数据读写无需CPU控制，适于高速设备。
缺点：数据传送的方向、存放数据的内存地址及传送数据的长度等都由CPU控制，占用了CPU时间。而且每个设备占用一个DMA控制器，当设备增加时，需要增加新的DMA控制器

与中断区别：

中断控制方式在每个数据传送完成后中断CPU；DMA控制方式是在要求传送的一批数据完成之后中断CPU。
中断控制方式的数据传送是在中断处理时由CPU控制完成的，由于程序陷入内核，需要保护和恢复现场。DMA方式下是由DMA控制器控制完成的，在传输过程中不需要CPU干预，DMA控制器直接在主存和I/O设备之间传送数据，只有开始和结束才需要CPU干预。
程序中断方式具有对异常事件的处理能力，而DMA控制方式适用于数据块的传输。

通道

与DMA的原理几乎是一样的，通道是一个特殊功能的处理器，它有自己的指令和程序专门负责数据输入输出的传输控制。CPU将“传输控制”的功能下放给通道后只负责“数据处理”功能。这样，通道与CPU分时使用内存，实现了CPU内部运算与I/O设备的并行工作。

DMA方式的发展，进一步减少CPU干预。把对一个数据块的读写干预，减少为对一组数据块读写的干预。
I/O通道是专门负责输入输出的处理器，独立于CPU，有自己的指令体系。可执行由通道指令组成的通道程序，因此可以进行较为复杂的I/O控制。通道程序通常由操作系统所构造，放在内存里。
优点：执行一个通道程序可以完成几组I/O操作，与DMA相比，减少了CPU干预。
缺点：费用较高。

与DMA区别：

DMA方式下，数据的传送方向、存放数据的内存起始地址和数据块长度都由CPU控制；而通道是一个特殊的处理器，有自己的指令和程序，通过执行通道程序实现对数据传输的控制，所以通道具有更强的独立处理I/O的功能。
DMA控制器通常只能控制一台或者少数几台同类设备；而一个通道可同时控制多种设备

缓冲

匹配CPU与外设的不同处理速度
减少对CPU的中断次数。
提高CPU和I/O设备之间的并行性。

种类：单缓冲、双缓冲、环形缓冲、缓冲池

设备分配

DCT：设备控制表，每个设备一张，描述设备的特性和状态
COCT：控制器控制表（如DMA控制器，描述DMA占用的中断号……）。
CHCT：通道控制表，描述通道工作状态
SDT：系统设备表，系统内一张，记录所有设备相关信息。包括DCT指针等

分配过程：

根据物理设备名查SDT，找到对应的DCT，若设备忙则等待，否则计算是否死锁然后进行分配
将设备分配给进程后，找到DCT所属的COCT，空闲则分配，否则等待
找到COCT所属CHCT，空闲则分配，否则等待

假脱机技术

把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。

应用程序进行I/O操作时，只是和SPOOLing程序交换数据，可以称为虚拟I/O

特点：

高速。应用程序的虚拟I/O比实际I/O速度提高
独享设备的共享。由SPOOLing程序提供虚拟设备，可以对独享设备依次共享使用

磁盘存储管理

基本概念

磁盘访问时间=寻道时间+旋转延迟时间+传输时间

寻道时间

把磁头从当前位置移动到指定磁道上所经历的时间。该时间是启动磁盘的时间s与磁头移动n条磁道所花费的时间之和

\(T_s=m\times n+s\)

旋转延迟时间

3600RPM即每分钟3600转——每秒60转——每转16.7ms——平均旋转延迟时间 \(T_r\) 为8.3ms

传输时间

指把数据从磁盘读出，或向磁盘写入数据所经历的时间，与每次所读／写的字节数b，旋转速度r以及磁道上的字节数N有关

\(T_t=\dfrac{b}{rN}\)

磁盘调度算法

先来先服务（FCFS）

按访问请求到达的先后次序服务

最短寻道时间优先算法（SSTF）

优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。

优点：改善了磁盘平均服务时间
缺点：可能产生“饥饿” 现象，造成某些访问请求长期等待得不到服务。

扫描算法（SCAN）

类似电梯调度中的LOOK算法，但是要到边界才返回

当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。

优点：既考虑了距离，又考虑了方向
缺点：摆动式扫描，两侧磁道访问概率仍低于中间磁道

循环扫描算法（CSCAN）

按照所要访问的柱面位置的次序去选择访问者。移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描。

LOOK

把到边界才返回的scan类算法改成到离边界最近的请求处返回，就产生了LOOK、C-LOOK算法

N-Step-SCAN

将请求队列分成分成长度为N的子队列，队列之间采用FCFS，队列内部采用SCAN

可以解决“磁壁粘着”问题：一个或几个进程对某个磁道有较高的访问频率，从而垄断了整个磁盘设备

N=2时成为FSCAN

RAID

一种把多块独立的硬盘（物理硬盘）按照不同方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据冗余的技术。

成本低、功耗小、传输速率高、可提供容错功能

RAID0

仅提供了并行交叉存取，提高IO速度，但无冗余功能

RAID1

镜像磁盘冗余阵列，将每一数据块重复存入镜像磁盘

读性能好，写性能由最差磁盘决定
有效容量减半

RAID 01

综合RAID0和RAID1的特点

其中RAID 0+1指先分块后镜像，物理磁盘与镜像磁盘间无明显一一对应关系

RAID 1+0指先镜像后分块，物理磁盘与镜像磁盘间一一对应关系

RAID2

采用海明码纠错的磁盘阵列，将数据位交叉写入几个磁盘中。按位条带化。

并行存取，各个驱动器同步工作。
使用海明编码来进行错误检测和纠正，数据传输率高。
需要多个磁盘来存放海明校验码信息，冗余磁盘数量与数据磁盘数量的对数成正比。

RAID3

将磁盘分组，采用字节级别的条带，读写要访问组中所有盘，每组中有一个盘作为校验盘。校验盘一般采用奇偶校验

恢复时间较长
读写性能的水桶效应瓶颈

RAID4

并行处理磁盘阵列：一种独立传送磁盘阵列，采用数据块交叉，用一个校验盘。将数据按块交叉存储在多个磁盘上

冗余代价与RAID3相同
访问数据的方法与RAID3不同。在RAID3中，一次磁盘访问将对磁盘阵列中的所有磁盘进行（同步）操作。
RAID4出现的原因：希望使用较少的磁盘参与操作，以使磁盘阵列可以并行进行多个数据的磁盘操作。
随机读快，随机写慢（竞争同一个校验盘）

RAID5

一种独立传送磁盘阵列，采用数据块交叉和分布的冗余校验，将数据和校验都分布在各个磁盘中，没有专门的奇偶校验驱动器

RAID6

双维校验独立存取盘阵列，数据以块（块大小可变）交叉方式存于各盘，检、纠错信息均匀分布在所有磁盘上。

写入数据要访问1个数据盘和2个冗余盘；
可容忍双盘出错；
存储开销是RAID5的两倍（多一个冗余盘）。

提高IO速度

选择性能好的磁盘
并行化
采用适当的调度算法
设置磁盘高速缓冲区

文件管理

基本概念

需求：存储大量数据、长期保存、可共享

文件：一种抽象机制，可以视为一个单独的连续的逻辑地址空间，其大小即为文件的大小，与进程的地址空间无关。或：信息项的序列（信息项是构成文件的基本单位，由单个字节或多个字节构成）

文件系统：本质为操作系统中统一管理信息资源的一个软件

Unix将文件分为普通文件、目录文件、特殊文件

普通文件：用户自己建立的文件
目录文件：管理文件系统的系统文件
特殊文件：字符设备文件（和输入输出有关，如中断、打印机等）、块设备文件（磁带、磁盘等）

文件系统模型的三个层次分别为文件系统接口、对象操作管理的软件集合、对象及其属性

提高文件系统性能：磁盘碎片整理、块高速缓存、RAID

文件结构

逻辑结构上，有字节序列、记录序列、树等

流式文件：基本单位为字符，有逻辑意义无结构
记录式文件：由若干条记录组成，可以按记录进行读写、查找等操作。每条记录有其内部结构

文件控制块（FCB）

基本信息：文件名、物理位置、文件逻辑结构、物理结构等
访问控制信息：文件所有者、访问权限等
使用信息：创建时间、上一次修改时间等

文件物理结构

文件在存储介质上的存放方式

连续结构

优点：
- 结构简单、实现容易、没有额外开销
- 支持顺序存取、随机存取
缺点：
- 文件长度不易改变
- 不利于文件的动态增加和修改

适用于变化不大的顺序访问的文件

串联/链接文件结构

优点：
- 空间利用率高；能较好的利用辅存空间
- 文件动态扩充和修改容易
- 顺序存取效率高
缺点：
- 随机存取效率太低
- 可靠性问题，如指针出错
- 链接指针占用一定的空间

索引结构

索引文件在存储区中占两个区：索引区和数据区。索引区存放索引表，数据区存放数据文件本身。

访问索引文件需要两步操作：查文件索引号，由逻辑块号查得物理块号；由此磁盘物理块号而获得所要求的信息

优点：
- 既能顺序存取，又能随机存取
- 满足了文件动态增长、插入删除的要求
- 能充分利用外存空间
缺点：索引表本身带来了系统开销

磁盘空间的管理

空闲表

序号	第一块空闲盘块号	空闲盘块数
1	2	4
2	9	3
3	15	5
4	-	-

空闲链表

将所有的空闲盘区连成一条空闲链，可有两种方式：空闲盘块链（可能很长）、空闲盘区链（不会很长，但回收复杂）。

位图

成组链接

文件保护

方法：

建立副本
定时转储(Unix)
规定文件的权限

文件一致性检查：

磁盘块的一致性：每个磁盘块设置两个计数器，一个记录在文件中出现的次数，另一个记录在空闲块中出现的次数，最终检查两个计数器是否存在不一致问题。
文件的一致性：每个文件设置两个计数器，一个记录其i节点被引用的次数，另一个记录文件目录中引用它的次数，最终检查两个计数器是否存在不一致问题

文件系统实例

FAT文件系统（MS DOS）

主引导记录(MBR)+分区表+分区

分区中，引导区（文件系统数据）+文件分配表FAT（描述簇的分配状态、下一簇簇号等等）

目录项大小为32字节，包括文件名、子目录、文件长度、第一簇的编号。文件名不区分大小写

ext2文件系统

利用索引节点(inode)来描述，每个文件对应一个inode，inode对应一个标识符，inode保存在索引节点表中。

文件系统的超块包含文件系统基本形式

组描述符

OS理论笔记

https://solor-wind.github.io/2024/07/02/OS理论笔记/

作者

gpf

发布于

2024年7月2日

许可协议

OS挑战性任务设计文档下一篇