OS | Rayee's Blog

操作系统（Operating System）是计算机系统中最基本的系统软件，它负责控制管理计算机的所有软硬件资源，对工作、资源进行调度和分配，并为用户和其他软硬件提供相应接口。它提供了三个基本的抽象：1）文件是对 I / O 设备的抽象；2）虚拟内存是对主存和磁盘的抽象；3）进程是对处理器、主存和 I / O 设备的抽象。

本文将着重记述 进程管理、存储管理、文件系统 及 输入/输出 相关内容。

一、进程管理

进程（Process）是操作系统对一个正在运行的程序的一种抽象（通俗来说，是程序的一次执行）。系统使用 进程控制块 PCB（Process Control Block，也称 process table）来描述进程的基本情况和运行状态，从而对各进程进行控制和管理。创建、撤销进程的本质是创建、撤销 PCB，因此 PCB 是进程存在的唯一标志。

进程映像（进程实体）= 程序段 + 相关数据段 + PCB

一个 CPU 看上去在并发地执行多个进程，其实是通过处理器在进程间的切换来实现的（一个进程的指令和另一个进程的指令是交错执行的）。进程间的转换是由操作系统内核（kernel）进行管理的，这个内核是操作系统代码常驻主存的部分。当应用程序需要操作系统的某些操作时，它将通过执行特殊的 系统调用（system call）指令，将控制权传递给内核，内核执行完相应操作后再将权限归还。

并发（concurrency）	并行（parallelism）
指一个同时具有多个活动的系统	指用并发来使一个系统运行得更快

1.1 进程 & 线程

在现代操作系统中，一个进程实际上可以由多个称为线程（Thread）的执行单元组成，线程也是程序执行流的最小单元。每个线程都共享相同的代码和全局数据，因而多线程之间往往比多进程之间更容易共享数据（线程一般也比进程更为高效）。

进程（Process）	线程（Thread）
为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量；是拥有资源的基本单位	减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能；是独立调度的基本单位

因为进程拥有资源而线程不持有资源，所以切换线程的时空开销要小于切换进程

创建一个线程较创建一个进程要快10~100倍

线程的实现分为 用户级线程（User-Level Thread，ULT）和 内核级线程 （Kernel-Level Thread，KLT）两种。在用户级线程中，有关线程管理的所有工作都由应用程序完成；在内核级线程中，线程管理的所有工作都由内核完成。

在同时支持用户线程和内核线程的系统中，有多种多线程模型，统一形式为将 n 个用户级线程映射到 m 个内核级线程上（m ≤ n）。

1.2 进程控制之 fork & execve （UNIX）

每个进程都有一个唯一的正数进程 ID （PID，Process ID）。使用 pid_t getpid(void) 和 pid_t getppid(void)可以分别获得进程和其父进程的 PID（在Linux系统中 pid_t 在 types.h 中被定义为 int。

#include<sys/types.h>
#include<unistd.h>

pid_t fork(void);

父进程 可以通过调用 fork 函数创建一个新的运行的 子进程，子进程获得父进程持有的所有资源的副本，两者的最大区别在于它们有不同的 PID。

特别的，fork 函数被父进程调用一次，将会返回两次，它在父进程中返回子进程的 PID，在子进程中返回 0。

回收子进程：当一个进程终止时（被称为 zombie process），内核并不会立即将其清除，而是等待它被父进程回收（reaped）后再将其抛弃。如果一个父进程没有回收其 zobime 子进程就终止了，那么内核会安排 init 进程去回收它们。父进程可以通过调用 waitpid 函数来等待它的子进程终止或停止。

init 进程的 PID 为1，它是在系统启动时由内核创建的，它不会终止，是所有进程的祖先。

1
2
3

#include<unistd.h>
//成功则不返回，错误则返回-1
int execve(const char *filename, const char *argv[], const char *envp[]);

调用 execve 函数将基于当前进程的 context 加载并运行一个新程序；与 fork 调用一次返回两次不同，execve 调用一次从不返回（特指 PID）。在 execve 加载了 filename 并调用启动代码设置栈后，将会把控制权交给新程序的主函数：

1	int main(int argc, char argv[], char envp[]);

程序与进程：进程是执行中程序的一个具体实例；程序总是运行在某个进程的 context 中。

fork 函数在新的子进程中运行与父进程相同的程序；execve 函数在当前进程的 context 中加载并运行一个新的程序（没有创建新进程）。

1.3 进程调度

在多道程序系统中，进程的数量往往多于处理机的数量，因此就需要在多进程竞争处理机时采用一定的算法进行调度以实现进程的并发执行。

由于 CPU 在各进程之间来回快速切换，所以每个进程执行其运算的速度是不确定的。通常，进程的运算速度与时序是难以复现的，所以，在对进程编程时不能对时序做任何假设。

（1）先来先服务（FCFS）调度算法

在进程调度中，FCFS 调度算法每次从就绪队列中选择最先进入该队列的进程。该算法的特点是算法简单但效率低；对长作业比较有利，但对短作业不利（相对 SJF 和高响应比）；有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。

（2）短作业优先（SJF）调度算法

短作业优先（SJF）调度算法从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行。该算法的特点是对长作业不利（可能导致 “饥饿” 现象——长作业长期不被调度）；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。优点是：SJF 调度算法的平均等待时间和平均周转时间最少。

（3）优先级调度算法

该算法中的优先级用于描述作业的紧迫程度。优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存运行。（又可细分为非抢占式优先级与抢占式优先级调度算法、静态优先级与动态优先级）

一些进程优先级的设置原则（供参考）：

系统进程＞用户进程
交互型进程＞非交互型进程
I/O 型进程＞计算型进程

（4）高相应比优先调度算法

高响应比优先调度算法是对 FCFS 调度算法和 SJF 调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。

响应比的变化规律可描述为：$响应比\ R_P\ =\frac{等待时间+要求服务时间}{要求服务时间}$

作业的等待时间相同时，要求服务时间越短，响应比越高
要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长其响应比越高
对于长作业，作业的响应比可以随等待时间的增加而提高，一定程度上克服了 “饥饿” 现象

（5）时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。系统将所有就绪进程按 FCFS 策略排成一个就绪队列，调度程序总是选择就绪队列中的第一个进程执行，但仅让其运行一个时间片（如 50ms），在使用完一个时间片后如果进程未运行完成则被剥夺并加入就绪队列队尾等待再次运行。

时间片的长短往往对系统性能影响很大（在进程间进行频繁的切换会增大处理机的开销），它通常由系统的响应时间、就绪队列中的进程数目和系统的处理能力共同确定。

（6）多级队列调度算法

该算法在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列中，每个队列可以实施不同的调度算法。

（7）多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展，它可以动态调整进程优先级和时间片的大小。

multiQueue

该算法实现思想如下：

设置多个就绪队列，为每个队列赋予不同的优先级
赋予各个队列的进程运行时间片的大小各不相同，在优先级越高的队列中，每个进程的时间片就越小（例如第 i+1 级队列的时间片要比第 i 级队列的时间片长 1 倍）
每个队列都采用 FCFS 算法。当新进程进入内存后首先将其放入第一级队列的队尾，若第 i 次执行未在时间片内完成，则将其加入第 i+1 级就绪队列的末尾，以此类推，在被降到最后的 n 级队列后便采用单纯的时间片轮转算法进行调度
按队列优先级调度。仅当第 1 级队列为空时才调度第 2 级队列中的进程运行；仅当第 1 至 i-1 级队列均为空时才调度第 i 级队列中的进程运行。若处理机正在执行第 i 级队列中的某进程时，又有新进程进入任一优先级较高的队列，此刻须立即把正在运行的进程放回到第 i 级队列的末尾，把处理机分配给这个新的高优先级进程

该算法的优势如下：

终端型作业用户：短作业优先
短批处理作业用户：周转时间较短
长批处理作业用户：经过前面几个队列得到部分执行，不会长期完全得不到处理

常见进程调度算法的横向对比

schedCompare

1.4 同步互斥

临界资源：一次仅允许一个进程使用的资源称为临界资源。

同步：等待获取资源（待同步进程间存在逻辑关联）

互斥：等待使用资源（互斥进程间无逻辑关联）

软件实现临界区互斥（Peterson’s Algorithm）

Process_i{
    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    process(i);
    flag[i] = FALSE;
}

Process_j{
    flag[j] = TRUE;
    turn = i;
    while(flag[i] && turn == i);
    process(j);
    flag[j] = FALSE;
}

硬件实现方法

中断屏蔽方法
硬件指令方法（硬件指令为原子操作，可以有效实现互斥）

信号量（semaphore）

信号量机制可以用来解决互斥与同步问题，它只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可以分别记作 P 操作和 V 操作。

信号量是 E.W.Dijkstra 在1965年提出的一种方法，它使用一个整型变量来累计唤醒次数。其中，检查数值、修改变量值以及可能发生的睡眠操作均为由硬件实现的单一的、不可分割的原子操作完成。

在 Dijkstra 原来的论文中，他分别使用名称 P（Proberen：尝试）和 V（Verhogen 增加）来表示对信号量的操作，P 操作将信号量减一（占用），V 操作将信号量加一（释放）。

管程（monitor）

利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程，这种数据结构与对应的操作被合称为管程。

当一个进程进入管程后被阻塞，直到阻塞原因解除之前其他进程都无法进入管程。为此，将阻塞原因定义为条件变量 condition，对条件变量只能进行两种操作：wait 和 signal。

条件变量和信号量的异同：

相似点：wait/signal 与 P/V 均可实现进程的阻塞/唤醒
不同点：信号量用其数值表示剩余资源数，而条件变量仅实现 ”排队等待“ 功能，没有数值，管程种的剩余资源数用共享数据结构来进行记录

1.5 死锁问题

死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

死锁的四个必要条件：

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

二、存储管理

鉴于此部分内容与 CO 有些许重叠，故不再赘述整体框架，这里只记述一些特别的内容。

2.1 多级页表 & 自映射

首先来看看多级页表，考虑一个采用二级页表机制的 $32$ 位虚拟存储系统，字长 $4$ 字节，虚拟地址结构如下：

一级页表（页目录）	二级页表	页内偏移
$22-31$位	$12-21$位	$0-11$位

可见，这样的页式虚拟存储系统页面大小为 $ 2^{12}B=4KB $ ，每一级页表 $10$ 位，每个页表项占一个字，即页表大小和页面大小相同，也为 $4KB$。此外，有一页一级页表，有 $2^{10}=1K$ 页二级页表，由此可知一级页表共占据内存空间 $4KB$，二级页表共占据内存空间 $4MB$。

那么这些页表该存放在哪儿呢？如果将一级页表与二级页表分别存储，显然，就需要引入额外的判断逻辑来区分当前地址含义为1）普通页面；2）二级页表页面；3）一级页表页面，这不仅会增加硬件设计的复杂性，也会使用额外的位来存储页面种类信息；同时，如果要在位宽更大的虚拟存储系统中使用更多级的页表（比如 RISC-V SV39分页硬件机制在 $64$ 位机器上使用 $39$ 位虚拟地址和三级页表（ $9×3+12$ ）来进行内存管理），就意味着随页表级数线性增加的额外开销，系统的复杂性也随着提升。

因此，为了统一虚实地址转换机制（使之可以共用一套映射硬件），一些 OS 采用了 自映射 的方式，将 $K$ 级页表嵌入 $K + 1$ 级页表，即在连续存储的 $K+1$ 级页表中有一页表的所有页表项所映射页面依次为连续存储的 $K+1$ 级页表，它就是 $K$ 级页表（$K$ 级页表中的首个页表项映射到连续存储的 $K+1$ 级页表中的首个 $K+1$ 级页表）。

下图以一个进程有 $4GB$ 地址空间为例，记所有二级页表所在的连续的 $4MB$ 空间的起始地址为 $PT_{Base}$ （Base Address of Page Table），一级页表（也称页目录）的起始地址为 $PD_{Base}$ （Base Address of Page Directory）。

二级页表

于是，根据 自映射 的定义，就可以得到 $PT_{Base}$ 和 $PD_{Base}$ 之间的关系：

$ PT_{Base}>>22<<(10+2)=PT_{Base}>>10=PD_{Base}-PT_{Base}$

即：$PD_{Base}=PT_{Base}+(PT_{Base}>>10)$

这里对上述关系的推导稍作解释：

$PT_{Base}>>22$ 得到映射到首个二级页表的二级页表页表号
$PT_{Base}>>22<<(10+2)$ 得到上述页表号对应二级页表相对首个二级页表的地址偏移（$2$ 为页表项位宽，此处一个字表示一个页表项，位宽为 $\log_24=2$ ；$10$ 为二级页表位宽）
所得即为 $PD_{Base}$ 相对 $PT_{Base}$ 的偏移量

2.2 页面置换算法

有几种典型的页面置换算法：FIFO、LRU 、OPT 和 CLOCK。

FIFO: First In First Out，优先换出最早进入内存的页面
LRU: Least Recently Used，优先换出最后一次使用时间距今最长的页面
OPT: Optimal，优先换出以后再不使用的页面，若无则换出下次使用距今时间最长的页面（理想算法）
CLOCK：又称 最近未用（NRU） 算法，为每个页面设置一个访问位，换入时置1，初次换出将访问位置0，若访问位为0则换出（为每个页面提供 ”第二条命“ ）；CLOCK 算法的改进版在此基础上加上修改位，根据修改位和访问位的几种情况分别设置页面换出优先级

用 C 简单实现 FIFO、LRU 和 OPT，并以 $100$ 个页面请求、$1-10$ 个页框为例计算缺页次数：

#include<stdio.h>
#define npage 10
int request[] = {0, 9, 8, 4, 4, 3, 6, 5, 1, 5, 0, 2, 1, 1, 1, 1, 8, 8, 5,
				 3, 9, 8, 9, 9, 6, 1, 8, 4, 6, 4, 3, 7, 1, 3, 2, 9, 8, 6, 2, 9, 2, 7, 2, 7, 8, 4, 2, 3, 0, 1, 9, 4,
				 7, 1, 5, 9, 1, 7, 3, 4, 3, 7, 1, 0, 3, 5, 9, 9, 4, 9, 6, 1, 7, 5, 9, 4, 9, 7, 3, 6, 7, 7, 4, 5, 3, 5, 3, 1, 5, 6, 1,
				 1, 9, 6, 6, 4, 0, 9, 4, 3};
int requestNum = sizeof(request) / sizeof(int);
int pn;
int opt_ans[npage];
int opt_pages[npage];
int lru_ans[npage];
int lru_pages[npage];
int fifo_ans[npage];
int fifo_pages[npage];
int opt_cnt, lru_cnt, fifo_cnt;
int lru_weight[npage];
int lru_order[npage];
int fifo_order[npage];
void opt_find(int cur){
	int pos = requestNum - 1;
	int book[npage], i;
	for (i = 0; i < pn;i++){
		if(request[cur]==opt_pages[i]){
			return;
		}
		if(opt_pages[i]==-1){
			book[i] = __INT_MAX__;
		}else{
			book[i] = requestNum + 2;
		}
	}
	for (; pos > cur; pos--){
		for (i = 0; i < pn;i++){
			if(opt_pages[i]==request[pos]){
				book[i] = pos;
			}
		}
	}
	int tag = 0;
	for (i = 1; i < pn;i++){
		if(book[tag] < book[i]){
			tag = i;
		}
	}
	opt_pages[tag] = request[cur];
	opt_cnt++;
	return;
}
void lru_find(int cur){
	int i;
	for (i = 0; i < pn;i++){
		if(lru_pages[i]==request[cur]){
			lru_weight[i]++;
			lru_order[i] = cur;
			return;
		}
	}
	int tag = 0;
	for (i = 1; i < pn;i++){
		if(lru_order[i]<lru_order[tag]){
			tag = i;
		}else if(lru_order[i] == lru_order[tag] && lru_weight[i]<lru_weight[tag]){
			tag = i;
		}
	}
	lru_weight[tag] = -1;
	lru_pages[tag] = request[cur];
	lru_order[tag] = cur;
	lru_cnt++;
	return;
}
void fifo_find(int cur){
	int i;
	for (i = 0; i < pn;i++){
		if(fifo_pages[i]==request[cur]){
			return;
		}
	}
	int tag;
	for (i = 0; i < pn;i++){
		if(fifo_order[i]<fifo_order[tag]){
			tag = i;
		}
	}
	fifo_order[tag] = 2 + cur;
	fifo_pages[tag] = request[cur];
	fifo_cnt++;
	return;
}
void resetPages(int val){
	int j;
	for (j = 0; j < npage;j++){
		opt_pages[j] = val;
		lru_pages[j] = val;
		fifo_pages[j] = val;
		lru_weight[j] = val;
		lru_order[j] = val;
		fifo_order[j] = val;
	}
	opt_cnt = 0;
	lru_cnt = 0;
	fifo_cnt = 0;
	return;
}
void find(int curRequest){
	opt_find(curRequest);
	lru_find(curRequest);
	fifo_find(curRequest);
	return;
}
void printAns(){
	FILE *opt_output = fopen("opt_ans.txt", "w");
	FILE *lru_output = fopen("lru_ans.txt", "w");
	FILE *fifo_output = fopen("fifo_ans.txt", "w");
	int i;
	for (i = 0; i < npage;i++){
		fprintf(opt_output, "%d\n", opt_ans[i]);
		fprintf(lru_output, "%d\n", lru_ans[i]);
		fprintf(fifo_output, "%d\n", fifo_ans[i]);
	}
	fclose(opt_output);
	fclose(lru_output);
	fclose(fifo_output);
}
int main()
{
	int curRequest;
	for (pn = 1; pn <= npage;pn++){
		resetPages(-1);
		for (curRequest = 0; curRequest < requestNum; curRequest++){
			find(curRequest);
		}
		opt_ans[pn - 1] = opt_cnt;
		lru_ans[pn - 1] = lru_cnt;
		fifo_ans[pn - 1] = fifo_cnt;
	}
	printAns();
	return 0;
}

缺页次数统计：

页框数	OPT	LRU	FIFO
1	90	90	90
2	64	79	80
3	48	71	67
4	37	58	59
5	29	52	47
6	22	42	39
7	16	28	30
8	12	17	20
9	11	13	12
10	10	10	10

简单做个图对比一下：

页面置换算法对比

2.3 段式存储管理

段式管理方式按照用户进程中的自然段划分逻辑空间。用户进程被划分为多段（如主程序段、子程序段、栈段和数据段），每一段都从 0 开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续），其逻辑地址由段号 S 与段内偏移量 W 两部分组成。

分段系统中段的共享是通过两个作业的段表中相应表项指向被共享的段的同一物理副本来实现的。其中，不能修改的代码称为纯代码或可重入代码（不属于临界资源）只有这种代码和不能被修改的数据可以被共享。

由于段的长度不固定，需要同时给出段号和段内偏移才可确定对应地物理地址。

分页存储管理可以有效提高内存利用率，而分段存储管理可以反映程序的逻辑结构并有利于段的共享和保护

在段页式系统中，段表只有一个，而页表可能有多个

2.4 其他内容

内存抖动

在页面置换过程中，如果刚换出的页面立刻又要换入主存，而刚换入的页面立刻又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。

缺页率（缺页率高即为抖动）是影响虚拟存储器性能地主要因素

内存抖动的解决方案：将分配给进程的物理块的集合称为驻留集，在驻留集中设置工作集（通常远小于驻留集大小），工作集反映了进程在接下来一段时间内很有可能会频繁访问的页面集合（基于局部性原理），工作集中的页面被换出则会调入驻留集中的非工作集部分，只有驻留集中非工作集部分的页面才会被真正换出主存。

内存映射文件（Memory-Mapped Files）

将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系便可以直接访问被映射的文件。多个进程允许并发地映射同一文件以便数据共享，进程也可以通过共享内存来进行通信。

三、文件系统

在系统运行时，计算机以进程为基本单位进行资源的调度和分配；而在用户进行的输入、输出中，则以文件为基本单位。

操作系统通过文件控制块（File Control Block，FCB）来维护文件元数据，FCB 的有序集合称为文件目录，一个 FCB 就是一个文件目录项，其主要包含<基本信息（如文件名、文件的物理位置、文件的逻辑与物理结构等），存取控制信息（如不同用户的存取权限），使用信息（如文件的建立时间、最近修改时间）>。

有些系统（如 UNIX）会采用文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引节点的数据结构，简称 i 结点（inode）。在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针构成。

3.1 文件的组织结构

逻辑结构

文件的逻辑结构是指在文件的内部，数据逻辑上是如何组织起来的，按逻辑结构，文件可划分为无结构文件和有结构文件两大类。

无结构文件又称流式文件，将数据按顺序组织成记录并积累保存，以字节为单位。

有结构文件又称记录式文件，分为顺序文件、索引文件、索引顺序文件（在索引顺序文件中，将 $N$ 条记录分为 $\sqrt{N}$ 组，索引表中有 $\sqrt{N}$ 个表项，每组有 $\sqrt{N}$ 条记录，在查找某关键字的记录时，先顺序查找索引表平均 $\frac{\sqrt{N}}{2}$ 次，然后在主文件对应的组中顺序查找平均 $\frac{\sqrt{N}}{2}$ 次，平均 $\sqrt{N}$ 次查找即可；本质上为分块查找）及散列文件（利用 Hash 的特性，缺点是需要处理 Hash 冲突）。

物理组织

文件的物理组织关注文件数据在物理存储设备上的分布和组织方式，分为文件的分配方式和文件存储空间的管理两个方面。

常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。

连续分配方法要求每个文件在磁盘上占有一组连续的块，逻辑文件中的记录顺序也存储在相邻接的块中。其缺点是文件长度不宜动态增加；反复增删文件会产生外部碎片；很难确定未知文件所需空间大小，因而只适用于长度固定的文件。
链接分配可以动态地为文件分配盘块，消除了磁盘的外部碎片，但增加了内部碎片。它有分为隐式链接（只适合顺序访问）和显式链接（采用文件分配表 File Allocation Table，FAT 用于记录文件各块之间的先后链接关系，并对空闲磁盘块进行标记，该方法还可显著减少访问磁盘的次数，但 FAT 需要占用较大的内存空间）。
索引分配将每个文件所有的盘块号都集中放在一起构成索引表，一般采用多级索引或者混合索引的访问方式来尽可能减小索引表对系统存储空间的开销。

3.2 文件目录

单级目录结构：整个文件系统只建立一张目录表，每个文件占一个目录项。

两级目录结构：将文件目录分为主文件目录（Master File Directory，MFD）和用户文件目录（User File Directory，UFD）两级，这种结构解决了多用户之间的文件重名问题，但不能对文件进行分类。

树形目录结构：可以显著提高对目录的检索速度和文件系统的性能，从根目录出发的路径为绝对路径，从当前目录出发的路径为相对路径。树形目录的缺点是在查找文件时需要按路径名逐级访问中间节点，增加了磁盘访问次数。目前，大多数操作系统采（UNIX，Linux 和 Windows）用树形文件目录。

无环图目录结构：在树形目录结构的基础上增加一些指向同一结点的有向边，使整个目录成为一个有向无环图，便可以较为容易地实现文件共享，这种结构为每个共享结点设置一个共享计数器来判断多用户的增删操作以决定是否真正删除该共享结点。无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂。

3.3 文件共享

文件共享使多用户共享同一文件，系统中只需保留文件的一个副本以节省存储空间。

基于索引节点的共享方式（硬链接）

在树形结构目录中，将共享文件的索引节点链接到多个用户的目录中，在索引节点中设置链接计数器来判断多用户下共享文件的持有者数目。

利用符号链实现文件共享（软链接）

在进行文件共享时，系统为用户创建一个 LINK 类型的新文件写入用户目录，LINK 文件记录了共享文件的路径，用户在删除文件时只需删除自己的 LINK 文件即可，多用户对共享文件的访问路径互不相同。这样的链接方式被称为符号链接。

硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，即两个进程同时对一个文件进行操作，这样的共享称为动态共享。此外，硬链接的查找速度要快于软链接。

四、输入/输出

4.1 IO 设备

按信息交换单位可划分为 块设备 与 字符设备，前者以数据块为单位进行信息交换，可寻址即随机读写任一块，后者以字符为单位进行信息交换，不可寻址并时常采用中断 IO 方式。前者的传输速率较后者更高。

IO 接口（设备控制器）位于 CPU 与设备之间，用于沟通彼此。该接口主要由三部分组成：

设备控制器与 CPU 的接口：数据线、地址线和控制线。
设备控制器与设备的接口：每个设备对应一个此类接口，存在数据、控制和状态三种类型的信号。
IO 逻辑：对 CPU 的命令进行译码并据此实现对设备的控制。

IO 端口指设备控制器中可以被 CPU 直接访问的寄存器，分为三类：

数据寄存器：缓冲 CPU 与外设之间的数据。
状态寄存器：获取执行结果与设备状态信息。
控制寄存器：由 CPU 写入以执行启动命令或更改设备模式。

4.2 IO 控制方式

IO 控制方式主要分为四类：程序直接控制方式、中断驱动方式 、 DMA 方式 和 通道控制方式 。

程序直接控制方式即简单的串行执行：CPU 向 IO 设备发出读写命令后一直轮询 IO 设备的状态检查命令是否完成，直到完成再执行下一条指令。考虑到 IO 设备的速度远低于 CPU 的速度，这样会大量浪费 CPU 资源。

中断驱动方式较程序直接控制方式稍好一些：CPU 向 IO 设备发出读写命令后便转去执行其他程序，IO 设备在完成以字为单位的读写任务后会向 CPU 发出中断信号表示数据已准备好，所以 CPU 需在每个指令周期的末尾检查是否有中断信号。然而，中断驱动方式下的数据传输必须经过 CPU，其实还是会消耗较多的 CPU 时间。

DMA 方式下的数据传输不再经过 CPU，相较中断驱动方式仅使用寄存器存取以字为单位的 IO 数据而言，DMA 方式在其 DMA 控制器中使用了更多的寄存器存取了更多的数据——以块为单位的 IO 数据、数据长度（字数）、内存地址。因此， DMA 控制器将独立于 CPU 完成与存储器的数据交互，并在完成读写任务后采用与中断驱动方式一致的方式——发送中断信号来通知 CPU。整个过程，CPU 仅需在数据传输的起始与结束阶段进行干预（不包括每个指令周期末尾检查中断信号）。

IO 通道方式是 DMA 方式的进一步发展，它将进一步减少 CPU 的干预。某种程度上来说，IO 通道方式引入了 IO 通道作为 CPU 与 DMA 控制器之间的缓存，原先在 DMA 方式中需要由 CPU 给出数据块大小、传输内存位置等信息，但 IO 通道方式使用了 IO 通道来统一完成这部分工作及后续 DMA 控制器的工作。此外，每个 DMA 控制器仅对应一台外设，而一个 IO 通道可以对应多台外设。

4.3 磁盘高速缓存与缓冲区

磁盘高速缓存（Disk Cache）：利用内存中的存储空间暂存从磁盘中读出的信息（逻辑上属于磁盘，物理上则是驻留在内存中的盘块）

缓冲区（Buffer）：分为单缓冲、双缓冲、循环缓冲与缓冲池几种模式。

引入缓冲区的主要目的：

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

约定：从磁盘中把一块数据输入到缓冲区的时间为 T ，操作系统将该缓冲区中的数据传送到用户区的时间为 M，CPU 对这一块数据处理的时间为 C ，通常认为缓冲区的大小与工作区的大小相等。

buffer

单缓冲

单缓冲区处理每块数据的用时为 $max(C,T)+M$

（图为 T ＞ C 的示意图）

singleBuffer

双缓冲

双缓冲区处理每块数据的用时为 $max(C+M,T)$

（图为 T > C + M 的示意图）

doubleBuffer

循环缓冲

包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个环形。此外，循环缓冲还需要两个指针 in 和 out，in 指向第一个空缓冲区，out 指向第一个装满数据的缓冲区。

缓冲池

缓冲池有三个队列（空缓冲队列、输入缓冲队列和输出缓冲队列），有四种缓冲区（用于收容输入数据、用于提取输入数据、用于收容输出数据、用于提取输出数据），示意图如下：

bufferPool

高速缓存与缓冲区的对比

bufferCompare

4.4 设备分配与回收

设备使用方式分三种：

独占式使用设备。进程分配到独占设备后，便由其独占，直至该进程释放该设备。
分时式共享使用设备。对于共享设备，可同时分配给多个进程，通过分时共享使用。
以 SPOOLing 方式使用外部设备。SPOOLing 技术实现了虚拟设备功能，可以将设备同时分配给多个进程，这种技术实质上就是实现了对设备的 I/O 操作的批处理。

SPOOLing 技术（假脱机技术）是操作系统中采用的一项将独占设备改造成共享设备的技术。

SPOOLing

在磁盘上开辟 输入井 和 输出井 分别用于模拟脱机时输入、输出的磁盘。

在内存中开辟两个缓冲区分别暂存由输入设备、输出井送来的数据。

输入/输出进程用于模拟脱机输入/输出时的外围控制机。

共享打印机是使用 SPOOLing 技术的一个实例

SPOOLing 系统的特点如下：

提高了 I/O 的速度，将对低速 I/O 设备执行的 I/O 操作演变为对磁盘缓冲区中数据的存取，如同脱机输入/输出一样，缓和了 CPU 和低速 I/O 之间的速度不匹配的矛盾。
将独占设备改造为共享设备，在假脱机打印系统中，实际上并没有为任何进程分配设备。
实现了虚拟设备功能，对每个进程而言，它们都认为自己独占了一个设备。

SPOOLing 技术是一种用空间换时间的技术，因为 CPU 向磁盘输出数据的速度要快于向打印机等低速设备输出数据的速度。

4.5 磁盘工作原理

磁盘（Disk）是表面涂有磁性物质的物理盘片，通过一个称为磁头的导体线圈从磁盘存取数据。磁盘盘面上的数据存储在一组同心圆中，称为磁道，每个磁道又划分为几百个扇区（每个扇区的数据区域大小通常为 512B），每个扇区固定存储大小，一个扇区又称为一个盘块。由于扇区按圆心角划分，所以密度从最外道向内道增加，磁盘的存储能力受限于最内道的最大记录密度。磁盘地址 用 ”柱面号-盘面号-扇区号“ 表示。

一次磁盘读写操作的时间由寻道时间、旋转延迟时间和传输时间决定。

寻道时间 $T_s=m\times n+s$。指活动头磁盘在读写信息前将磁头移动到指定磁道所需的时间。n 为跨越磁道数，m 为磁盘驱动器速度有关的常数，约为 0.2ms，s 为磁臂启动时间，约 2ms。
旋转延迟时间 $T_r=\frac{1}{2r}$。指磁头定位道某一磁道的扇区所需的时间。r 为磁盘的旋转速度，对硬盘来说，典型的旋转速度为 5400 转/分，相当于一周 11.1ms，$T_r=5.55ms$；对软盘来说，其旋转速度约为 300-600 转/分，$T_r$ 为 50-100 ms。
传输时间 $T_t=\frac{b}{rN}$。指从磁盘读出或向磁盘写入数据所经历的时间。其中，b 为每次读写的字节数，r 为磁盘每秒的转速，N 为一个磁道上的字节数。

综上可得出总平均存取时间 $T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$

然而在实际的磁盘 I/O 操作中，存取时间和磁盘调度算法密切相关。

4.6 磁盘调度算法

（1）先来先服务（First Come First Served，FCFS）算法

优点是具有公平性，但若有大量进程需要访问，该算法在性能上往往接近于随机调度。

（2）最短寻找时间优先（Shortest Seek Time First, SSTF）算法

SSTF 算法选择处理当前距离磁头最近的磁道，使每次的寻道时间最短，这种算法的缺点是会产生 ”饥饿“ 现象。

（3）扫描（SCAN）算法

SCAN 算法在磁头当前移动方向上选择与当前磁头所在的磁道距离最近的请求作为下一次服务的对象，在到达最外（内）侧时调转磁头移动方向。

（4）循环扫描（Circular SCAN, C-SCAN）算法

在 SCAN 算法的基础上规定磁头到达最外侧时径直返回起始端（途中不处理任何访问请求），重复执行单向扫描。

（5）LOOK 算法

在 SCAN 算法的基础上规定磁头无需移动到最外（内）侧再调转方向，而是在相应距最外（内）侧最近的请求后调转磁头移动方向。

参考资料

Computer Systems: A Programmer’s Perspective (3rd Edition)
Modern Operating Systems (4th Edition)
See Mips Run Linux (2nd Edition)

页框数	OPT	LRU	FIFO
1	90	90	90
2	64	79	80
3	48	71	67
4	37	58	59
5	29	52	47
6	22	42	39
7	16	28	30
8	12	17	20
9	11	13	12
10	10	10	10

页框数	OPT	LRU	FIFO
1	90	90	90
2	64	79	80
3	48	71	67
4	37	58	59
5	29	52	47
6	22	42	39
7	16	28	30
8	12	17	20
9	11	13	12
10	10	10	10

页框数	OPT	LRU	FIFO
1	90	90	90
2	64	79	80
3	48	71	67
4	37	58	59
5	29	52	47
6	22	42	39
7	16	28	30
8	12	17	20
9	11	13	12
10	10	10	10