操作系统 o((>ω< ))o 一呼百应 | SLie's Blog|琴弦之轮

操作系统的基本概念

操作系统（Operating System，OS）是控制和管理整个计算机系统硬件与软件资源，合理地组织、调度计算机的工作与资源分配，进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统最基本的系统软件。

操作系统的特征

并发性| Concurrence

并发是指两个或多个事件在同一时间间隔内发生。

OS 的并发性就是指在计算机系统中同时存在多个运行的程序，因此它具有处理和调度多个程序同时执行的能力。这也是在 OS 中引入进程的目的。

应区别同一时间间隔（并发）与同一时刻（并行）的区别

OS 的共享性是指系统中的资源可供内存中多个并发执行的进程共同使用。

为了结果不造成混淆，规定一段时间内只允许一个进程访问该资源，其他进程在此时需要访问同样的资源时只能等待，知道前一个访问资源的进程访问完并释放资源后，才能得以访问。这样的共享方式称为 互斥共享方式，这样的资源被称 临界资源。
允许一段时间内被多个进程“同时”（分时共享）的资源满足的共享方式则为 同时访问方式。

并发与共享是 OS 的两个最基本特征。
若系统不允许并发执行，则不存在资源共享的问题；
若系统没有实施有效的资源共享管理，则会影响到并发执行，甚至无法并发执行。

虚拟性| Vitual

OS 中利用多种虚拟技术（如：时分复用技术、空分复用技术）来实现把一个物理实体在逻辑上变为若干对应物的能力（如：虚拟处理器、虚拟内存、虚拟外设等）

异步性| Asynchronism

多道程序环境允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底而是走走停停的，它以不可预知的速度向前推进，这就是进程的异步性。

异步性使 OS 运行在一种随机的环境下，可能导致进程产生与时间有关的错误。因此，OS 必须保证多次运行进程后都能获得相同的结果。

操作系统的接口

命令接口

用户利用命令接口来组织和控制作业的执行。
命令接口又有两种方式：联机控制方式 和 脱机控制方式。

联机命令接口又称 交互式命令接口，适用于分时或实时系统，是“说一句话，做一件事”。
脱机命令接口又称 批处理命令接口，适用于批处理系统，由一组作业控制命令组成，脱机用户事先给定一份作业操作说明书，连同作业交给系统后，脱机用户则不能再直接干预作业的运行。

程序接口

程序接口由一组 系统调用（也称广义指令） 组成。
用户通过程序接口向 OS 请求提供相应的服务，如使用各种外设、申请分配和回收内存等。

由于系统中的缓存全部由操作系统管理，所以系统调用不提供关于系统缓存的管理，这对用户是透明的。

图形用户界面 GUI 最终也是通过调用程序接口实现的。

操作系统发展历程

操作系统发展史（图源:王道）

操作系统的基本类型主要有：批处理操作系统、分时操作系统和实时操作系统。

批处理：用户脱机，作业成批，多道并发，交互力差；
分时：用户同时，用户“独占”，响应及时，交互力强；
实时：可靠性强，响应及时，利用率低。

注：多道批处理系统的 I/O 设备可与 CPU 并行工作，这是借助于中断技术实现的。

操作系统运行环境

处理器运行模式

计算机系统中，CPU 通常执行两种不同性质的程序：OS 内核程序与用户自编程序。
二者作用不同且前者是后者的管理者，所以内核程序需要执行一些特权指令，用户程序则不被允许执行。
常见的特权指令有：I/O 指令、置中断指令等。

为了实现这种划分，CPU 的运行模式被分为 用户态（目态） 以及 核心态（管态）。

内核是计算机上配置的底层软件，管理着系统的各种资源。主要包括 4 方面的内容：

时钟管理
中断机制
原语
系统控制的数据结构及处理（包括：进程管理、存储器管理和设备管理）

中断和异常

中断（Interruption）也称外中断，是指来自 CPU 执行指令外部的事件。
异常（Exception）也称内中断，来自 CPU 执行指令内部，如非法操作码、地址越界、运算溢出以及专门的陷入指令等引起的事件。异常不能屏蔽，一旦出现必须立即处理。

中断和异常又有着如下分类：
内外中断的联系与区别

自陷(Trap)是一种事先安排的“异常”事件。
在用户态需要通过系统调用使用内核服务时，用户程序执行”陷入指令“（又称访管指令、trap指令）使得 CPU 的使用权转交给了操作系统内核程序，这实现了 CPU状态从用户态进入核心态。如下图所示：

系统调用的执行过程

在中断处理时，前三个步骤由硬件（隐指令）直接实现。
中断处理时，不仅要保存 PC 断点还要保存程序状态字寄存器（PSW）的内容。前者由隐指令自动保存，后者则是操作系统保存。

中断处理过程

操作系统结构

分层式架构与模块化架构

宏内核架构与微内核架构

操作系统引导

虚拟机

同步与互斥

临界资源

一次仅允许一个进程使用的资源成为 临界资源。临界资源的访问必须是互斥地进行。
临界资源的访问过程分为 4 部分：

进入区 为进入临界区使用临界资源，需要在此前检查能否进入临界区；
临界区 是进程访问临界资源以进行各种操作的那段代码，也被称为临界段；
退出区 将正在访问的临界区标志清除；
剩余区 代码中的其余部分。

进程的制约

进程之间存在同步与互斥的制约关系。

同步是指为完成某种任务而建立的两个或多个进程，这些进程需要在某些位置上协调工作次序而等待、传递信息，因此而产生的制约关系。
互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问。

为此，同步机制应遵循以下准则：

空闲让进。临界区空闲时可允许一个请求进入临界区的进程立即进入。
忙则等待。
有限等待。对请求访问的进程应保证能在有限时间内进入临界区。
让权等待。当进程不能进入临界区时，应当立即释放处理器防止进程忙等待。

软件实现互斥

由软件实现临界区互斥的基本方法中，遵循“让权等待”并且无“饥饿”现象的算法有：Peterson’s Algorithm.

其基本思想如下：

void P_i(){
	flag[i] = True; turn = j;
	while(flag[j] && turn==j);
	//critical section 临界区
	flag[i] = False;
	//remainder section 剩余区
}

void P_j(){
	flag[j] = True; turn = i;
	while(flag[i] && turn==i);
	//critical section 临界区
	flag[j] = False;
	//remainder section 剩余区
}

考虑进程 $P_i$ ，一旦设置 $flag[i]=True$ 就表示它想进入临界区，同时 $turn=j$ ，因此如果此时 $P_j$ 已经在临界区中则 $P_i$ 就一直等待。

硬件实现互斥

通过硬件支持实现临界区问题的方法称为低级方法，或元方法。

中断屏蔽方法
硬件指令方法
- TestAndSet 指令
- Swap 指令

硬件方法的优点：适用于任意数目的进程，而不管是单处理机和多处理机；简单、容易验证其正确性；
硬件方法的缺点：进程等待进入临界区时要耗费处理机的时间，不能让权等待。

互斥锁

解决临界区的制约问题，最简单的工具就是 互斥锁（mutex lock）

一个进程进入临界区时应该获得锁，利用函数 acquire()；在退出临界区时释放锁，利用函数 release()。（均为不可被中断的原子操作）

每个互斥锁有一个布尔变量 available 表示锁是否可用。锁可用时 acquire() 可调用成功，且锁不再可用。逻辑正如下面的代码所示：

void acquire(){
	while(!available); //忙等待
	available = False; //获得锁
}

void release(){
	available = True; //释放锁
}

当多个进程共享同一 CPU 时，就浪费了 CPU 周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

信号量

信号量机制是一种功能较强的机制。可用来解决互斥与同步问题，它只能被两个标准原语 wait(S),signal(S) 访问。也记为“P操作”和“V操作”。通常用硬件实现。

下面给出一种整型信号量的定义。定义一个用于表示资源数目的整型量 $S$ ，从而 PV 操作可描述为：


global semaphore S;

void P(semaphore S){
	while(S <= 0); //资源还有剩余时退出循环
	S--; //允许当前进程访问资源，剩余资源数-1
}
void V(semaphore S){
	S++; //访问资源结束，释放资源给其他进程，剩余资源数+1
}

当 $S\leq0$ 时，说明此时资源真正被占用。

若将条件变为 $S\lt0$ ，则 $S$ 为负数时其负数的绝对值还可以用于表示当前正请求访问资源的进程个数。当然， $S=S-1$ 的操作就得提前：

void P(semaphore S){
	S--;
	while(S < 0);
}

void V(semaphore S){
	S++;
	while(S <= 0);
}

信号量实现同步

为了协调进程 $P_1$ 和进程 $P_2$ 之间的同步关系，例如 $P_2$ 进程中的 $B$ 语句需要在 $P_1$ 的 $A$ 语句的变量，或者需要发生在 $A$ 之后执行才能得到正确结果，出现这种情况时，我们可以通过 PV 操作，使得在 $P_2$ 执行 $B$ 语句之前必须获得资源才能进行，而这个资源的释放应该放在 $A$ 语句执行完毕之后。

具体实现如下：

semaphore S = 0; //初始化信号量
void P1(){
	A; //A语句
	V(S);
	...
}
void P2(){
	...
	P(S);
	B; //B语句
}

信号量实现互斥

为了协调进程 $P_1$ 和进程 $P_2$ 之间的互斥关系，例如 $P_1,P_2$ 进程中的 $A,B$ 语句需要同时访问某资源（限额1），出现这种情况时，我们可以通过 PV 操作，使得在执行 $A,B$ 语句之前必须获得资源才能进行，执行完毕之后再释放。这样在 $P_1$ 执行 $A$ 语句时， $P_2$ 只能等待，以实现互斥。

具体实现如下：

semaphore S = 1; //初始化信号量
void P1(){
	...
	P(S);
	A; //A语句
	V(S);
	...
}
void P2(){
	...
	P(S);
	B; //B语句
	V(S);
	...
}

管程

当共享资源用共享数据结构表示时，资源管理程序可用对于该数据结构进行操作的一组过程来表示，如资源的请求与释放过程。把这些数据结构和过程一并归为管程。

管程的引入是为了解决临界区分散所带来的管理和控制问题。管程一次只允许一个进程进入管程内，从而既便于系统管理共享资源，又能保证互斥。

下面仅给出管程的类C伪代码，事实上不具备实际用处，只作为感性认识。


class monitor{ //管程类
	private:
		sharesource S; //共享数据 S 
		condition x; //定义条件变量 x
	public:
		void init_code(){ // 初始化资源数
			this->S = 5;
		}
		void take_away(){
			if(S <= 0) x.wait(); //资源不够时阻塞等待
		}
		void give_back(){
			... //归还资源
			if(有进程等待) x.signal(); //唤醒阻塞的进程
		}
	
};

上述出现的 x.wait(),x.signal() 称为条件变量。
每个条件变量保存了一个等待队列，用于记录因某个条件 x 而阻塞的所以进程。

x.wait 实现将进程插入 x 条件不足时的等待队列，并释放之，使得其他进程使用管程；
x.signal 用于唤醒之前阻塞，但因 x 条件满足后的进程。

这与信号量有所不同，共同点是都能实现进程的阻塞与唤醒，不同点是条件变量没有“值”，仅实现了“排队等待”的功能。

经典同步问题

如果进程之间还具有前驱后继关系，也相应需要设置复数个信号量予以实现同步关系。

在实际设置信号量时，我们应该学会区分进程与进程之间的制约关系是互斥还是同步，从而用以解决实际问题。
下面列举几个经典的同步问题作为分析问题和设置信号量的示例。

生产者-消费者问题

读者-写者问题

哲学家进餐问题

假设有 $n$ 个哲学家， $n$ 根筷子， $m$ 个碗。

semaphore bow;
semaphore chopsticks[n];
for(int i = 0; i < n; i++)
    chopsticks[i] = 1;
bow = min(n-1,m); //利用碗数量限制不大于 n-1，确保不死锁

CoBegin
    while(True){ //哲学家 i 的进程
       Thinking; //思考
       P(bow); //拿碗
       P(chopsticks[i]); //取左筷子
       P(chopsticks[(i+1)%n]); //取右筷子
       eating; //就餐
       V(chopsticks[i]); //取左筷子
       V(chopsticks[(i+1)%n]); //取右筷子
       V(bow); //拿碗
    }
CoEnd

吸烟者问题

关于教科书略过的叫号问题


customer{
	...
	
	while(True){
		P(call);
		if(List.search(i) == True){
			进餐;
			V(empty);
			离开;
			break;
		}else{
			V(call);
		}
	}
}

windows{
	...
	m++;
	List.push(m);
	V(call);
}

死锁

在多道程序系统中，由于多个进程并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而多个进程并发执行也将带来名为“死锁”的问题。即多个进程因竞争资源而造成的一种僵局（互相等待）。

死锁产生的原因

系统资源的竞争：系统中的不可剥夺资源，其数量不足以满足多个进程运行的需要，从而陷入争夺资源僵局；
进程推进顺序非法：请求和释放资源的顺序不当，信号量使用不当等也会引发死锁。
死锁产生的必要条件

当系统出现死锁时，必然有两个或者两个以上的进程处于阻塞态

死锁的必要条件

产生死锁必须同时满足以下 4 个条件，只要其中一个不成立，死锁就不会发生。

互斥条件 进程要求对所分配的资源进行排他性使用
不剥夺条件 进程所获得的资源在未使用完之前不能被其他进程剥夺
请求并保持条件 进程已经保持至少一个资源，但又请求其他资源，并且要请求的资源又被其他进程占用，此时本进程只能被阻塞，但对自己已获得的资源保持不放
循环等待条件 存在一种进程资源的循环等待链。链中的每个进程已获得的资源同时被链中下一进程请求。

注意，循环等待条件本身并不一定导致死锁，死锁对等待环的要求更严格。
资源分配图含圈而系统又不一定是死锁的原因是：同类资源数大于 1.

极端死锁情况

系统有同类资源 m 个，供 n 个进程共享，若每个进程 i 对资源的最大需求量为 k_i，则该系统不发生死锁的条件为：

$\sum_{i=1}^n(k_i-1)+1\leq m$

死锁的处理策略

对死锁的处理有 4 种方式：忽略、检测与恢复、避免和预防。
每种方法对死锁的处理从宽到严，同时，系统的并发性也由大到小。
例如，银行家算法处于死锁避免方法，比起属于死锁预防的资源预分配法，并发性更高。

死锁预防

通过设置某些限制条件，破坏产生死锁的 4 个必要条件的一个或几个。

破坏互斥条件（考虑实际运行的正确，不允破坏）
破坏不剥夺条件
破坏请求并保持条件（采用预先静态分配方法，进程运行前实现一次性全加载）
破坏循环等待条件（采用循环资源分配法）

死锁避免

避免死锁同样是事先预防策略，但区别于死锁预防，它是在资源动态分配的过程中，防止系统进入不安全状态以避免发生死锁。这种方法所施加的限制条件较弱。

为此，我们需要在分配资源前，分析系统当前的安全性。值得注意的是，系统进入不安全状态不等于系统陷入死锁，二者是包含关系。

对于安全性检验，以及如何进行避免的算法将在下一节的银行家算法中详细阐述。

死锁检测与解除

资源分配图

死锁定理

死锁解除

银行家算法

内存管理

内存管理是OS设计中最重要和最复杂的内容之一。操作系统必须对内存空间进行合理的划分和有效的动态分配，提高内存的利用率。其主要功能有：

内存分配与回收；
地址转换；
内存空间扩充；
内存共享；
存储保护

程序链接与装入

为了将用户源程序变为可在内存中执行的程序，通常需要经过：编译、链接和装入三个步骤。

编译就是由编译程序将源代码编译成若干目标模块的过程。
链接需要完成将目标模块与其所需库函数链接形成一个完整的装入模块。
装入则顾名思义，将装入模块装入内存执行。

程序的链接有以下三种方式：

静态链接：在程序运行前直接链接，之后不再拆开，该过程实现修改相对地址和变换外部调用符号。
装入时动态链接：在装入内存时，边装入边链接，优点是便于修改和更新，便于实现目标模块的共享。
运行时动态链接：在程序执行中需要某目标模块时才进行链接，优点是加快了装入过程，节省内存空间。

内存的装入有以下三种方式：

绝对装入：只适用于单道程序环境，直接产生绝对地址。
可重定位装入：在装入时对目标程序地址进行修改，利用相对地址。该过程在装入时一次完成，也被称为 静态重定位。
动态运行时装入：也称动态重定位。不立即把相对地址转为绝对地址，而推迟到真正运行时才进行，该方法需要一个重定位寄存器支持。优点是可以将程序分配到不连续的存储区，根据需要动态申请分配内存，便于程序段共享。

连续分配管理方式

连续分配方式是指为一个用户程序分配一块连续的内存空间。主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配

内存在该方式下被分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分。而在用户区内存中，仅有一道用户程序。

该方式简单、无外部碎片、无须内存保护。但只能用于单用户、单任务的操作系统，有内部碎片，利用率低。

固定分区分配

内存在该方式下被分为若干固定大小的区域，每个分区只装入一个作业。当分区空闲时即可从后备作业队列中选择适当大小的作业装入。是多道程序设计中最简单的分配方式。

该方式存在两个问题：一是程序太大时可能无法装入任何分区，这是就需要利用覆盖技术；二是程序太小时仍然装入某个分区中，造成空间浪费，存在内部碎片。

动态分区分配

又称可变分区分配。它在进程装入内存时，根据实际需要动态地为之分配内存，使得分区大小正好适合进程所需。

动态分区在开始时效果较好，但随着时间的推移，内存中会出现越来越多的小内存块无法被利用，产生外部碎片，从而降低利用率。可以通过紧凑技术克服，但是需要额外的动态重定位寄存器支持，并且相对耗时。

动态分区分配

在进程换入/装入内存是，若内存中有若干足够大的空闲区，则操作系统有如下几种算法对其进行分配：

首次适应（First Fit）：空闲分区按地址从低到高排序，选择第一个足够放入的区域。
邻近适应（Next Fit）：又称循环首次适应算法，由首次适应算法演变得来，不同的是在分配内存时是从上次查找结束的位置开始继续查找。
最佳适应（Best Fit）：空闲分区按容量从小到大排序，选择第一个足够放入的区域。
最坏适应（Worst Fit）：空闲分区按容量从大到大排序，选择第一个足够放入的区域。

首次适应算法是最简单，通常也是最好和最快的算法。但是会使得低地址部分出现很多闲置的小空闲区，且每次分配都要经过，增加了开销。
邻近适应算法试图解决这个问题，但内存空间尾部也会因此分裂成小碎片，通常反而不如首次适应。
最佳适应算法虽然名字叫“最佳”，但实际表现却是最差的，会产生最多的外部碎片。
最坏适应算法看起来不容易产生外部碎片，但是会把大区域划分开来，会导致没有足够可用的大内存快使用，性能也非常差。

基本分页存储管理

把主存空间划分为大小相等且固定的块，并且块相对较小，以此作为主存的基本单位。每个进程也以块为单位进行划分，申请内存时也以此逐个申请块空间。这样的存储管理方式称为分页管理。

由于块的大小与分区分配相比小得多，进程也以此为单位划分，所以分页管理不会产生外部碎片，进程只在最后一个不完整块申请主存块时才产生内部碎片。

每个进程平均只产生半块大小的内部碎片（也称页内碎片）。

页表

进程内的块称为页（Page），内存中的块称为页框或页帧（Page Frame），外存也以同样的单位进行划分，直接称为块或盘块（Block）。

综上所述，有：页大小=块大小=内存大小/页数

进程执行时需要申请主存空间，即为每一个页分配可用的页框，这就产生了页与页框的一一对应。这个对应关系由系统为每个进程建立的页表体现。

地址变换机构

分页系统的逻辑地址由页号和页内偏移量组成。

地址变换机构的任务是将逻辑地址转换为内存中的物理地址。地址变换借助页表实现。如下图所示：

分页管理的地址变换机构

在系统中通常设置一个页表寄存器（PTR)，存放着页表在内存的起始地址 $F$ 和页表长度 $M$ 。

进程未执行时，页表的始址和页表长度存放在本进程的 $PCB$ 中
当进程被调度执行时，才将页表始址和页表长度装入页表寄存器中

设页面大小为 $L$ ，逻辑地址 $A$ 到物理地址 $E$ 的变换过程如下（假设逻辑地址、页号、每页的长度都是十进制数）：

计算页号 $P\quad(P= A/L)$ 和页内偏移量 $W\quad(W=A\%L)$ 。
比较页号 $P$ 和页表长度 $M$ ，若 $P≥M$ ，则产生越界中断，否则继续执行。
页表中页号 $P$ 对应的页表项地址=页表始址 $F$ ＋页号 $P$ × 页表项长度，取出该页表项内容 $b$ ，即为物理块号。
计算 $E=b×L+W$ ，用得到的物理地址 $E$ 去访问内存。

注意区分页表长度和页表项长度。
页表长度是指一共有多少页，页表项长度是指页地址占多大的存储空间。

快表

不难得出：页式管理在存取数据或指令时至少要访问 2 次内存。第一次访问页表，第二次通过页表得到的物理地址去访问内存。
为了解决两次访存降低效率的问题，可在地址变换机构中增设一个具有并行查找能力的高速缓存——快表。又称 相联存储器（TLB）。对应地，主存中的页表称为慢表。

在有快表的分页管理机制中，CPU给出逻辑地址后，由硬件进行地址转换，先将页号送入高速缓冲存储器，将页号与快表中的所有页号进行比较。
如果找到，就可直接拼接得到物理地址，对内存进行一次访存就能实现存取。
否则，访问慢表读出页表项之后，访问物理地址的同时，还将其存入快表，以便后续可能再次访问。若快表已满，则须按一定的算法淘汰一个旧的页表项。

一般快表的命中率达90%以上，其有效性基于著名的局部性原理。我们会在之后具体讨论。

由此可看出，当快表中查找不到时，需要 一次访问高速缓存+两次访问内存 才能实现存取。而有些处理机设计为快表慢表同时查找，快表成功就终止慢表查询。
如果题目并没有给出该处理机可同时处理，则按前者计算。

多级页表

当页数过多、页表过大时，如果要求页表同样进入内存以便查找，这同样会造成内存利用率的降低。（因为页表占用的是内存中一片连续的区域）
因此，为了压缩页表，我们进一步延申页表映射的思想，考虑建立页表的页表，即二级页表来实现页表的映射关系，使得页表内容也可以分散存储。如果二级页表还是很大，就建立三级页表，以此类推。

为查询方便，我们规定顶级页表最多只能占一个页面。

若页表划分为 $N$ 级，则需要访存 $N+1$ 次，同样地，引入快表后最少只需 1 次。

基本分段存储管理

分页管理方式是从计算机的角度考虑设计的，目的是提高内存利用率，提升计算机性能，由硬件实现，对用户透明。
而分段管理方式则考虑到了用户和程序员，以满足方便编程、信息保护与共享、动态增长及动态链接等多方面的需求。

段式管理按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序段、两个子程序段、栈段和数据段组成，则可将其划分为5段，每段都从0开始编址并分配一段连续的地址空间。

段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的

地址变换机构

分段系统的逻辑地址由段号和段内偏移量组成。

地址变换机构通过段表对其进行地址转换，其中，段表又由段号、段长和本段在主存中的始址组成。相比页表，新增了段长这个字段，这是因为其空间大小各不相同导致的。

分段系统的地址变换机构

在系统中设置了段表寄存器，用于存放段表始址 $F$ 和段表长度 $M$ 。从逻辑地址 $A$ 到物理地址 $E$ 之间的地址变换过程如下:

从逻辑地址 $A$ 中取出前几位为段号 $S$ ，后几位为段内偏移量 $W$ 。
比较段号 $S$ 和段表长度 $M$ ，若 $S>M$ ，则产生越界中断，否则继续执行。
段表中段号 $S$ 对应的段表项地址=段表始址 $F$ ＋段号 $S$ ×段表项长度，取出该段表项的前几位得到段长 $C$ 。
若段内偏移量 $W≥C$ ，则产生越界中断，否则继续执行。
取出段表项中该段的始址 $b$ ，计算 $E=b+W$ ，用得到的物理地址 $E$ 去访问内存。

段页式管理

分页管理提高了内存利用率，分段管理反应了程序的逻辑结构，利于段的共享与保护。于是，将二者结合起来就形成了段页式管理。

在段页式管理系统中，作业的地址空间首先被划分为若干逻辑段，每段都有自己的段号，然后每个段又被划分成若干大小固定的页。
根据以上逻辑，作业的逻辑地址便为 (段号, 页号, 页内偏移量)，由三部分组成。

我们规定，一个进程中段表只有一个，而页表可以有多个。

在进行地址变换时，首先根据段表查页表始址，然后再通过页表找到块号，最后形成物理地址。由此可见，段页式管理需要进行三次访存。

一道综合题

已知系统为 32 位实地址，采用 48 位虚拟地址，页面大小为 4KB，页表项大小为 8B，每段最大为 4GB。

1）假设系统使用纯页式存储，则要采用多少级页表？页内偏移多少位？

2）假设系统采用一级页表， $TLB$ 命中率为 98%， $TLB$ 访问时间为10ns，内存访问时间为 100ns，并假设当 $TLB$ 访问失败时才开始访问内存，问平均页面访问时间是多少？

3）若是二级页表，页面平均访问时间是多少？

4）上题中，若要满足访问时间小于 120ns，则命中率 $p$ 至少需要为多少？

5）若系统采用段页式存储，则每用户最多可以有多少个段？段内采用几级页表？

答案解析

虚拟内存管理

虚拟内存技术允许将一个作业分多次调入内存，其实现需要建立在离散分配的内存管理方式上。因此有如下几种方式：请求分页存储管理、请求分段存储管理、请求段页式存储管理。

无论是哪一种方式，都需要一定的硬件支持。一般包括以下几个方面：

一定容量的内存和外存；
页表或段表机制，作为主要的数据结构；
中断机构，当用户程序要访问的部分未调入主存时则产生中断；
地址变换机构，逻辑地址到物理地址的变换。

请求分页管理方式

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能、页面置换功能。

请求分页是目前最常用的一种实现虚拟存储器的方法。

页表机制

为了发现和处理要访问的页面当前不在内存中的情况，在页式管理的页表项基础上新增4个字段：

状态位 $P$ ：指示该页是否已调入内存，供程序访问时参考；
访问字段 $A$ ：记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，供置换算法换出页面时参考；
修改位 $M$ ：标识该页在调入内存后是否被修改，以确定页面置换时是否写回外存；
外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入时参考。

最终得到请求分页系统下的页表项：

1	[页号, 物理块号, 状态位 P, 访问字段 A, 修改位 M, 外存地址]

缺页中断

当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺页面调入内存。

缺页中断作为中断，同样要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等步骤。但值得注意的是：

缺页中断属于内部异常。它在指令执行期间产生
一条指令在执行期间可能产生多次缺页中断

地址变换机构

请求分页管理的地址变换流程图

页框分配

内存分配策略

对于分页式虚拟内存，在进程准备执行时，不需要也不可能把一个进程的所有页都读入内存，因此操作系统必须决定“读多少页”，即决定给特定的进程分配多少页框。

给一个进程分配的物理页框的集合就是这个进程的驻留集。

内存分配有固定和可变分配两种策略，而页面置换又有全局和局部置换两种策略。我们可以组合得出以下三种适用策略：

固定分配局部置换。每个进程分配固定数目的物理块，置换时从该进程内部选择页面进行置换
可变分配全局置换。先每个进程分配一定数目的物理块，在执行过程中可适当增减，发售缺页时从空闲块队列中选择
可变分配局部置换。可变分配，只在内部置换。若频繁缺页则操作系统为该进程再分配物理块，直到缺页率趋于适当程度；反之，若缺页率很低亦可适当减少分配给该进程的物理块，但不能引起缺页率的明显增加。

虽然第三种方法实现起来较为复杂，也需要开销，但相比其频繁的页面置换所浪费的资源，这种牺牲是值得的。

物理块调入算法

采用固定分配策略是，将系统中空闲物理块分配给各进程的算法有如下几种：

平均分配算法。
按比例分配算法。
优先权分配算法。为重要和紧迫的进程分配较多的物理块，通常是将所有空闲区分成两部分，一部分按比例分配，一部分根据优先权分配。

调入页面的时机

预调页策略。根据局部性原理，一次调入若干相邻页比一次调入一页更高效，但若调入的一批页面大多数都不被访问又是低效的。因此需要采用以预测为基础的预调页策略，将预计在不久后便会被访问的页面预先调入内存。但事实上目前预调页的成功率仅 50%，因此这种策略主要用于进程的首次调入，由程序员指出先调入哪些页。
请求调页策略。进程在运行中需要访问的页面不在内存时则提出请求，操作系统再相应地调入页面。这种策略可以保证调入的页面一定会被访问，也容易实现，因此目前的虚拟存储器大多采用这种策略。其缺点是一次仅调入一页，增加了磁盘 I/O 的开销。

预调页就是运行前的调入，请求调页就是运行期间的调入

页面置换算法

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。（属于内部异常或称内中断）

当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

好的页面置换算法应有较低的页面置换频率。常见的页面置换算法有以下四种。

最佳置换算法 (Optimal, OPT)

最佳置换算法的核心是从当前存入物理块的页面中将以后永远不会再被访问，或者距离下一次访问所需时间最长的页面淘汰。

例如：假设系统为某进程分配了三个物理块，并考虑到有以下页面号引用串（即会依次访问这些页面）：

$7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1$

开始运行时，先将 7, 0, 1 三个页面装入内存（由于一开始三个物理块内均没有页面，所以这三次均产生缺页中断）。
当进程要访问页面 2 时，产生缺页中断，根据最佳置换算法，页面 7 在第18次访问才需要调入，再次被访问的时间最长，因此会将页面 7 换出，后面的过程以此类推，具体过程如下图：

OPT置换算法示意图

可见，最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。

虽然该算法是一种理论上的算法，但是它可以用来评价其他算法。

先进先出置换算法 (First In First Out, FIFO)

先进先出置换算法的核心很简单，即每次选择淘汰的页面是最早进入内存的页面。

我们同样用上面的例子，当进程访问页面 2 时，把最早调入的页面 7 换出。之后访问页面 3 时把当前的 2,0,1 中最早进入的页面 0 换出，以此类推。具体过程如下图：

FIFO置换算法示意图

FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此，算法性能差。

当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为贝莱迪（Belay）异常。

FIFO算法可能出现 Belady 异常，而 LRU 和 OPT 算法永远不会出现该异常。

为了说明 Belady 异常，我们考虑以下这种情况。页面访问顺序为：

$3,2,1,0,3,2,4,3,2,1,0,4$

物理块分别为 3 和 4，则 FIFO 算法表现如下：

Belady 异常示意

可见，增加物理块反而造成更多次的缺页。

最近最久未使用置换算法 (Least Recently Used, LRU)

算法思想：每次淘汰的页面是最近最久未使用的页面。

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 $t$ ，当需要淘汰一个页面时，选择现有页面中 $t$ 最大的页面，即最近最久未使用。

LRU还有另一种实现方法：在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

使用和上面同样的实例，采用LRU算法进行页面置换：

LRU置换算法示意图

LRU 性能较好，但需要寄存器和栈的硬件支持，LRU是堆栈类的算法。

理论上可以证明，堆栈类算法不可能出现 Belady 异常，FIFO算法基于队列实现，不是堆栈类算法。

CLOCK算法 (Not Recently Used, NRU）

最佳置换算法那性能最好，但无法实现。
先进先出置换算法实现简单，但是算法性能差。
最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

而时钟置换算法则是一种性能和开销均平衡的算法。又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）

👉🏻 简单CLOCK算法算法思想：

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列，并用一个替换指针与之相联。

初始时，指针依次往后移，并对访问到的帧置 1；
物理块填满后，若某页被访问且它在内存中时，置1 ，但指针不动；
当需要淘汰一个页面时，检查指针当前所指的页的访问位：
- 如果是 0，就选择该页换出，指针后移；
- 如果是 1，暂不换出，将访问位改为 0，指针后移并继续检查下一个页面.

由此可见，简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描。

现假设页面访问顺序： $7,0,1,2,0,3,0,4,2,3,0,3,2,1,3,2$

利用 NRU 算法处理结果如下图所示：
NRU 置换算法示意图

其中，指针的移动已用黄色标注。不难发现，只有当缺页中断产生的时候指针才会发生移动。

改进型CLOCK算法

当发生缺页中断时，操作系统会把未修改过的页面替换进外存，因为内存和外存中所对应的该页面的内容相同，处理时间只有一次缺页中断访问外存的时间。但是修改过的页面则还需要向外存中写入一次，再加上缺页中断的时间，相当于访问了两次外存，是上述未修改的两倍。所以避免把修改过的页面替换下去可以提高性能。

改进型的 CLCOK 算法为此除了访问位之外，还增加了修改位，加以决策是否换出、怎么换出。

由访问位 $A$ 和修改位 $M$ 可以组合成下面四种类型的页面：

$A=0, M=0$ ：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
$A=0, M=1$ ：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
$A=1, M=0$ ：最近已被访问，但未被修改，该页有可能再被访问。
$A=1, M=1$ ：最近已被访问且被修改，该页可能再被访问。

可能有人会发现第 2 类这种情况理应不会出现。因为如果一个页帧被修改，其修改位会被置1，同时它也被使用了，其访问位也会被置1。即不会出现被修改但是没有被使用的情况。
但事实上，页帧的访问位是可能会被清零，这样第 3 类经过一次清零就会变成第 2 类了。

算法具体步骤如下：

从指针的当前位置开始，扫描循环队列。寻找 $AM=00$ 的第一类页面作为淘汰页。在第一次扫描过程中，不改变访问位 $A$ 。
若第(1)步失败，则开始第二轮扫描，查找 $AM=01$ 的第二类页面，将遇到的第一个这样的页作为淘汰页。在这个扫描过程中，将所有经过的页的访问位 $A$ 置 0。
若第(2)步失败，指针将回到它的最初位置，并且将所有页的访问位 $A$ 均置 0。重复第(1)步，并且如果有必要，重复第(2)步。这样一定可以找到淘汰页。

改进型的 CLOCK 算法优于简单 CLOCK 算法之处在于替换时首选没有变化的页，减少了磁盘 I/O 的操作次数。但为了找到一个可置换页可能需要经过几轮的扫描，算法本身的实现也会增加部分开销。

页故障的上下限

在虚拟页式管理系统中，设驻留集大小为 $m$ ，初始时所有页帧均为空。若长为 $p$ 的引用串中具有 $n$ 个不同页号（ $n\gt m$ ），对 FIFO、LRU置换算法来说，此情况下发生页故障次数的上下限分别为： $p,n$ .

上限为 $p$ ，因为存在每次访问的页号当前已经被换出的情况
下限为 $n$ ，因为无论如何安排总有 $n$ 个不同的页号首次进入主存时产生的缺页

几种不同置换算法的比较

抖动与工作集

抖动的含义与原因

在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。

发生抖动的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进／调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进／换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于 0 的情况。我们称此时的进程是处于抖动状态。

抖动是在进程运行中出现的严重问题，必须采取相应的措施来解决它。为此有不少学者对它进行了深入的研究，提出了许多非常有效的解决方法。由于抖动的发生与系统为进程分配物理块的多少有关，于是有人提出了关于进程工作集的概念。

工作集的概念

关于工作集的理论是1968年由 Denning 提出并推广的。 Denning 认为，基于程序运行时的局部性原理得知，程序在运行期间，对页面的访问是不均匀的，在一段时间内仅局限于较少的页面，在另一段时间内，又可能仅局限于对另一些较少的页面进行访问。这些页面被称为活跃页面。
如果能够预知程序在某段时间间隔内要访问哪些页面，并将它们调入内存，将会大大降低缺页率，从而可显著地提高处理机的利用率。当然，我们自然是无法预知的。

我们称在某个时刻 $t$ 之前所访问过的 $\Delta$ 个页面构成的集合为工作集 $W$ 。

工作集 $W(t,\Delta)$ 是二元函数，即在不同时间 $t$ 的工作集大小不同，所含的页面数也不同；工作集与窗口尺寸 $\Delta$ 有关，是窗口尺寸 $\Delta$ 的非降函数（nondecreasing function)，有 $W(t,\Delta)\subseteq W(t,\Delta+1)$ .

预防抖动的方法

工作集模型预防抖动的原理是：
让操作系统跟踪每一个进程的工作集，为之分配数目大于工作集大小的物理块。落在工作集内的页面调入驻留集，落在工作集外的页面可以从驻留集换出。若还有空闲物理块，则可以再调入另一个进程到内存中来。若所有进程的工作集之和超过可用物理块总数，则操作系统暂停一个进程，将其页面换出并把物理块分配给其他进程，由此可用防止抖动现象。

当前可以利用哪几种方法来防止“抖动”？

采取局部置换策略
把工作集算法融入到处理机调度中
利用“L=S”准则调节缺页率
选择暂停的进程

更多相关内容参考：https://blog.csdn.net/weixin_45798993/article/details/122825207

内存映射文件

内存映射文件(Memeory-Mapped File) 是操作系统本身内存管理的一种机制，它的思想就是将磁盘文件中的全部或部分内容与进程的虚拟地址空间的某个区域建立映射关系。

一旦映射某个文件就进程就可以直接在内存中访问这个文件，而不必对文件执行 I/O 操作，并且可以不必对文件内容进行缓存。此外，使用内存映射文件，可以使多个进程之间并发地共享该文件，实现数据共享。如一个进程在共享内存上完成了写操作，此时另一个进程在映射到该文件的虚拟地址空间上执行读操作时，便能立刻看到上一个进程写操作的结果。这使得内存映射文件成为单台机器上的多个进程之间进行通信的最有效的方法。

更多相关内容参考：https://javaforall.cn/149900.html

虚拟存储器的性能

虚拟存储器的最大容量 $\leq$ 计算机地址位数 $b$ 所能容纳的最大容量 $2^bB$ (字节编址)
虚拟存储器的实际容量 $=\min\{$ 主存容量+外存容量，最大容量 $\}.$

若某计算机采用请求分页存储管理系统，某时刻测得其各设备的利用率如下：

$CPU:10\%$
磁盘交换区 $:99.7\%$
其他 I/O 设备 $:5\%$

则可以改善 $CPU$ 利用率的措施有：

增大内存容量。这会使得每个进程得到更多的页框，减少缺页率，以减少换入换出过程，降低磁盘交换情况，提升 CPU 利用率。
减少多道程序度数。从已知条件知当前系统正处去频繁换入换出的状况，减少主存中运行的程序可适当减少磁盘交换，提升 CPU 利用率。

增大磁盘交换区容量、使用更快的磁盘交换区、使用更快速的CPU 均不能改善此情况。

文件管理

文件的定义与组成

概念：文件 (file) 是以计算机硬盘为载体的存储在计算机上的信息集合。

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

组成形式：
- 数据项：数据项是文件最低级的数据组成形式，主要可分为：基本数据项（用来描述一个对象的某种属性的一个值，是数据中最小的逻辑单位)、组合数据项（由多个基本对象组成）
- 记录：记录是一组相关的数据项的集合，由于描述一个对象在某方面的属性。
- 文件：文件是创建者所定义的、具有文件名的一组相关元素的集合。

文件的属性

名称：文件名称唯一，以容易读取的形式保存
标识符：文件的唯一标签，通常为数字，是对人不可读的一种内部名称
类型：被支持不同类型的文件系统所使用
位置：指向设备和设备上文件的指针
大小：文件当前的大小(字节、字或块表示)，包含文件允许的最大值
保护：对文件进行保护的访问控制信息，比如：只读、可读可写、拒绝访问等
时间、日期和用户标识：文件创建、修改和上次访问的相关信息，用于保护和跟踪文件的使用

文件控制块 (FCB)

概念：文件控制块是用来存储控制文件需要的各种信息的数据结构，以实现“ 按名存取 ”。

FCB 是一个有序集合称为目录文件，一个 FCB 就是一个文件目录项。
创建一个新的文件，系统会分配一个 FCB 存放在文件目录中，成为目录项。

特点：FCB 必须连续存放

FCB 主要包括以下信息：

基本信息：比如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构。
存取控制信息：文件存取的权限
使用信息：文件建立时间、文件修改时间

注1：一个文件目录本身也被视为一个文件，称为目录文件
注2：UNIX 操作系统把所有设备都视为特殊的文件，控制和访问外设都相当于在访问文件

索引结点

文件目录通常存放在磁盘中。在查找目录时，我们通常是按存储顺序逐个查找分块存在磁盘中的FCB目录，用文件名进行一一对比。
也就是说，实际上在查找时我们并未利用到 FCB 中一个文件的其他描述信息，因此有些系统（如 UNIX）便采用了文件名与文件描述信息分开存储的方式以减少查找开销。其中，采用索引结点这样的数据结构，利用指针指向实际文件描述信息的位置。

在考虑系统创建最多文件数量的问题时，只需要考虑索引结点的个数。
即：索引结点数量上限 = 创建文件数量的上限

磁盘索引结点

磁盘索引结点是存放在磁盘上的索引结点。UNIX 中每个文件都有一个唯一的磁盘索引结点。它主要包括以下内容：

文件主标识符：拥有该文件的个人或小组的标识符
文件类型：普通文件、目录文件、特别文件
文件存取权限：各类用户对该文件的存取权限
文件物理地址：每个索引结点中含有13个地址项，iaddr(0) 到 iaddr(12) . 直接或者间接的方式给出数据文件所在盘块的编号
文件长度：字节为单位
文件链接计数：本文件系统中所有指向该文件的文件名的指针计数
文件存取时间：文件最近被进程存取，修改以及索引结点最近被修改的时间

内存索引结点

内存索引结点则是存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点的内容复制到内存中，并且还需增加部分内容，如下：

索引结点编号：用于标识内存索引结点
状态：指示 i 结点是否被上锁或者被修改
访问计数：每当有一个进程要访问此 i 结点时，计数加1，访问结束减1
逻辑设备号：文件所属文件系统的逻辑设备号
链接指针：设置分别指向空闲链表和散列队列的指针

文件的操作

创建文件：create系统调用

系统调用参数：所需要的大小空间、文件存放路径、文件名
系统调用步骤：在外存中找到文件申请的存储空间；系统调用根据文件路径找到该目录对于的目录表，插入目录项

删除文件：delete系统调用

系统调用参数：文件路径、文件名
系统调用步骤：根据文件路径找到目录表；根据文件名找到目录项；回收文件占用磁盘块；删除目录项

读文件：read系统调用

系统调用参数：文件名、读入多少数据；读入数据放在内存什么位置
系统调用步骤：读文件的时候已经打开文件了，所以进程只用提供文件在打开文件表中的索引号即可；操作系统读出进程指定大小的数据存到进程指定的区域

写文件：write系统调用

系统调用参数：文件名、写多少数据、写到什么位置
系统调用步骤：将进程指定文件数据写到指定大小的外存中

打开文件：open系统调用

系统调用参数：文件名、文件路径、打开之后对文件的操作
系统调用步骤：根据路径找到目录表；根据文件名找到目录项；根据目录项检查用户是否有操作权限；有的话操作系统会把文件的目录项复制到“打开文件表”(两种，系统文件表：系统记录所有打开的文件；进程文件表：进程记录自己打开的文件)中；用户根据编号打开文件

删除文件：delete系统调用

系统调用参数：文件存放路径、文件名
系统调用步骤：从目录中找到文件名对应的目录项；回收目标文件占用的磁盘块；从目录表中删除文件对应的目录项

关闭文件：close系统调用

系统调用参数：文件路径、文件名
系统调用步骤：将进程打开文件表中相应表项删除；回收分配给该文件的内存空间；系统打开文件表的计数器：count-1，如果count==0，页删除表项

文件重定位（文件寻址）

流程：按照某种文件搜索目录，将当前文件位置设为定值。并且不会读、写文件

截断文件

流程：允许文件的所有属性不变，并删除文件内容，即将其长度设为0并释放其空间

文件保护

文件保护主要是为了解决对文件的读、写、执行的许可问题（即，访问权限的保护）

实现方式有：口令保护、加密保护和访问控制等。

对文件的保护可从限制对文件的访问类型出发。可以加以控制的访问类型有：
读、写、执行、添加、删除、列表清单(列出文件名和文件属性)、文件重命名、复制、编辑等（通过低层系统调用实现，保护可以只在低层提供）

访问控制

解决访问控制最常用的方法是根据用户身份进行控制。

根据用户身份进行控制的最普通的方法就是：为每个文件和目录增加一个访问控制列表（Access-Control List，ACL）规定每个用户名及其所允许的访问类型。

优点：灵活性高，可以使用复杂的访问方法
缺点：长度无法预计且可能导致复杂的空间管理

为了规避这样的缺点，可以采用精简访问列表（UNIX系统）解决。精简访问列表采用如下三种用户类型：

拥有者：创建文件的用户
组：一组需要共享文件且具有类似访问的用户
其他：系统内的所有其他用户

此外，还有另外两种访问控制方法，分别是口令和密码。二者均是防止用户文件被他人窃取或者存取的，并没有控制用户对文件的访问类型。

口令指用户请求访问时需要提供相应的口令。优点是时间和空间开销不多；缺点是口令直接存储在系统内部，不安全。
密码是用户对文件进行加密，用户访问需要密钥解密。优点是保密性强，节省了存储空间；缺点是加密和解密需要花费一定时间。

访问控制机制的安全性差，但灵活性较高。
访问控制由系统实现，否则系统本身的安全性就无法保证。
加密机制由用户实现，否则加密方式无法扩展。

文件的逻辑结构

文件的逻辑结构是从用户的角度出发看到文件的组织形式；
文件的物理结构(存储结构)是从实现观点出发看文件在外存上的存储形式。

按照逻辑结构可以划分成无结构文件和有结构文件两种。

无结构文件 (流式文件)

无结构文件又叫做流式文件，是最简单的文件组织形式。将数据桉顺序组织、记录、积累保存，以字节(byte)为单位，是有序信息项的集合。

因为没有结构，只能通过穷举搜索的方式查找，查找非常低效率。
但字符流的无结构文件管理简单，用户可方便对其进行操作。所以较适用于对基本信息单位操作不多的文件，如文本文件、源程序文件等。

有结构文件 (记录式文件)

有结构文件按照记录的组成形式可以分成顺序文件、索引文件、索引顺序文件。

顺序文件

顺序文件的文件记录是一个接一个的顺序排列，通常是定长的。可以顺序存储或链表形式存储。

通常以下两种结构：

串结构：按照记录之间的顺序排列与关键字无关，通常按存入时间的先后顺序进行排序。检索时必须从头开始顺序查找；
顺序结构：文件中的记录按照关键字来排序。检索时可采用折半查找法提高效率。

顺序文件的特点是在文件中对记录批量修改，顺序文件效率较高，但是增删改查单条记录效率比较低。

索引文件

索引文件由逻辑文件和索引表组成。

主文件的每个记录都在索引表中设置一个表项，包含指向变长记录的指针(即存放该记录的逻辑地址)和记录的长度。索引表按关键字排序，其本身也是一个定长记录的顺序文件。

如果是定长的记录索引表中只需要有索引号(按顺序排列，二分查找)和对应指向逻辑文件的指针，即可计算出第 $i$ 条记录相对于第一条记录的地址：

$A_i=i\times L$

式中， $L$ 是记录的定长.

如果是变长的记录，索引表会有索引号(按顺序排列，二分查找)、记录长度和执行逻辑地址的指针，第 $i$ 条记录的地址是前 $i-1$ 条记录地址之和+1，即：

$A_i=\sum_{j=0}^{i-1}L_j+1$

如果索引表项比较大的，比如文件为 8B，索引表项就占32个字节。这样对存储空间利用率太低了。

索引顺序文件

索引顺序文件是顺序和索引文件二者的结合。
将文件的所有记录分成若干组，为顺序文件建立一张索引表，在表中为每组的第一条记录建立索引项(该记录的关键字和指向该记录的指针)。这样一来查找的时候就先根据索引表找到它所对应的组，然后再在组中顺序查找。

对于含有 $N$ 条记录的顺序文件，查找某关键字的记录平均需要 $N/2$ 次。
对于含有 $N$ 条记录，分为 $\sqrt N$ 组，每组 $\sqrt N$ 条记录的 索引顺序文件，先顺序查找索引表，平均 $\sqrt N/2$ 次，再在组内顺序查找记录，平均 $\sqrt N/2$ 次，一共平均 $\sqrt N$ 次。

显然，相比之下索引顺序文件提高了存取速度。

直接文件或散列文件(Hash File)

给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。
这种映射结构不同于顺序文件或索引文件，他没有顺序的特性。

散列文件有很高的存取速度，但是会引起冲突，即不同的关键字的散列值相同。

文件的物理结构

文件的无物理结构就是研究文件的实现。即文件数据在物理存储设备上是如何分布和组织的。
这个问题我们要分为两个方向：一是文件的分配方式，即对磁盘非空闲块的管理；二是文件存储空间管理，即对磁盘空闲块的管理。

文件分配方式

连续分配

分配方法：要求每个文件在磁盘上占有一组连续的块，磁盘地址是线性排序的。比如一个文件长 $n$ 块，从位置 $b$ 开始，那么必须在磁盘上划分出 $n$ 块连续空间存储文件，且该文件占用 $b,b+1,b+2,\cdots,b+n-1$ 的块。
特点：实现简单、存取速度快；文件大小不能动态增加，并且会产生外部碎片。

链接分配

链接分配采用的是离散分配方式。它消除了磁盘的外部碎片，提高了磁盘利用率。
可以动态为文件分配盘块，也无须事先清楚文件的大小。此外对文件的增删改查非常方便。

链接分配又分成隐式链接分配和显式链接分配。

一、隐式链接

分配方式：每个文件对应一个磁盘块的链表，文件块在磁盘中以链表的方式链接。添加文件的时候会在目录项中存储指向该文件首地址的指针和尾地址的指针。写文件的时候，系统会在磁盘中找到空闲块然后将这一块插入到文件里面。
特点：增删改查比较方便，不会产生外部碎片；但是只能顺序访问文件，磁盘块中的指针会消耗空间，稳定性不好，如果指针丢失文件就会被破坏

二、显式链接

分配方式：把链接文件各个物理块的指针，从每个物理块末尾提取出来，显式地存放在内存的一张链接表(文件分配表 FileAllocation Table，FAT)中。FAT 是由盘块号和指向下一块的指针构成，表头：(盘块号,下一块号)。
以 -1 表示文件到达结尾。-2/-3/-4 等表示磁盘块空闲。
这张表存放在内存中，系统启动就调入内存。
特点：因为表在内存中，提高了查找速度，减少访问磁盘的次数。

索引分配

链接分配解决了外部碎片和文件大小管理的问题，但是其不支持有效的直接访问、FAT需要占用较大的内存空间。

注意到在打开文件时并不需要将完整的 FAT 调入内存，为此，索引分配提供下述分配方法：
把每个文件的所有盘块都存储在索引块中，在目录项中存储指向该文件索引块的指针。

特点：没有外部碎片，支持直接访问文件的任意块。

注意：当文件过大的时候索引块可能存储不了一个文件的所有块号，所以索引块很难解决大的文件，但是可以引入以下三种机制解决

链接方案：将多个索引块链接起来
多层索引：第一层索引块存储第二层索引块的信息，第二层索引块存储文件信息，或者更多层。
混合索引：将多种索引方式混合使用，一个索引块中可以有直接地址、一级索引块的信息、二级索引块的信息。

混合索引分配

为了更全面地照顾小、中、大乃至特大型文件，可采用混合索引分配。

假如每个盘块大小 4KB，盘号长 4B，设置 10 个直接地址项、1 个一级索引、1 个二级索引和 1 个三级索引。（一个盘块可存 4K/4 = 1024 个地址）则：

对于小型文件（≤4KB×10=40KB），为了提高其访问速度，最好让它们的每个盘块地址直接放入 FCB 中。例如我们直接在索引结点中设置 10 个直接地址项。用 i.addr(0),...,i.addr(9) 存放。这实现了直接寻址。

对于中型文件（≤4KB×1024=4MB），可以采用单索引方式。访问时先从 FCB 中得到索引表（利用 i.addr(10)），再从中获得该文件的盘块地址。这实现 一次间接寻址。

对于长度大于 40KB+4MB 的文件，采用二次间接地址分配模式。用地址项 i.addr(11) 提供。可计算得出二级间接寻址的文件最大可达 1024×4MB=4GB 。

对于更大的文件（达 4TB 大小）则采用三级间接寻址。用地址项 i.addr(12) 提供。

UNIX 系统采用的就是上述分配方法，示意图如下：

UNIX系统的inode结构

各种分配的比较

三种分配方式的比较

目录结构

目录的操作主要有：搜索、创建文件、删除文件、显示目录、修改目录

单级目录：查找速度慢、文件不允许重名、不便于文件共享、不适合多用户操作。
两级目录：将文件目录分成主文件目录和用户文件目录。用户文件目录记录该用户的FCB信息，先被检索；主文件目录存储用户名和用户目录所在的存储位置。缺乏灵活性，不能对文件进行分类。
树形目录：树形目录是两级目录进行的推广，能够实现多级文件目录。

对于树形目录，用户操作的时候根据文件路径来标识想要的文件，文件路径是一个字符串，目录名和数据文件之间用 / 分开。
从根目录开始的路径叫做绝对路径；从“当前目录”出发到所找文件的路径叫做相对路径。

树形目录可以很方便的对文件进行分类，层次结构清晰，便于文件管理与保护。但是查找文件，需要按照路径名(中间可能有很多文件目录)去寻找，增加了磁盘的访问次数。

无环图目录：在树形结构的基础上增加了一些指向同一个节点的边，让整个目录成为了一个有向无环图。

无环图目录结构如多个用户指向一个共享结点，结点对应的文件设置一个共享计数器，有新用户访问时计数器+1，当有用户需要删除文件的时候，计数器-1。文件被修改则每个用户看到的信息都是修改后的。直到计数器的值为0后才真正实现对文件的删除。

特点：方便了文件的共享，但是让文件管理系统变得更加复杂。

文件共享

文件共享就是让多个用户共享使用一个文件，系统中只保存一个文件的副本，不需要每个用户都复制一份。

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

每个用户的文件目录中只设置文件名和相应的索引结点的指针。索引结点指针，指向同一个文件的索引结点，从而读取文件信息。
该文件的索引结点里面还应有一个链接计数器 counter，用来记录当前访问文件的用户目录数量。如果此时有两个用户访问，用户A想要删除共享文件，而此时用户B还在使用，用户A只能删除它目录中的关于共享文件的目录项，不能删除共享文件。

软连接：利用符号链实现文件共享

如果用户B 想共享访问用户A 的中的文件 F。系统会创建一个 LINK 类型的新文件，也取名叫 F，并将其写入 B 的目录下。新文件 F 中存储的只是 A 中文件 F 的文件路径。（快捷方式）

当 B 想要访问 F 且正要读取 LINK 文件时，操作系统据此找到 F 的路径名然后对其进行读，这样实现共享的方式就是符号链接。

由此可见，在符号链共享方式下，每次访问共享文件时系统都需要逐个查找目录直到找到目标文件的索引结点，这个过程会产生多次读盘，增加了启动磁盘的频率。

显然，只有文件主才拥有指向目标文件的索引结点指针，其他用户只有文件路径名。因此不会发生删除文件后留下悬空指针的情况。文件主删除共享文件后，其他用户再访问时就会访问失败，并将符号链删除。

注意：软硬链接都是文件系统的静态共享方法。而两个进程同时对一个文件操作的共享，称为 动态共享。

外存空闲空间管理

逻辑格式化

文件存储在一个文件卷中，文件卷可以是物理盘的一部分，也可以是整个物理盘。

在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目录区）是分离的。

划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
初始化：划分好目录区和文件区，建立空闲空间管理表格及存放逻辑卷信息的超级块

空闲表法

空闲表法是连续的分配方式，他与内存的动态分配方式相似。为文件划分一块连续的空间。系统为外存上的所有空闲区域建立一张空闲盘块表(序号，空闲盘块的第一块号，空闲盘块数)。

同样可以使用首次适应，最佳适应等算法。

空闲链表法

空闲链表法就是根据构成链表的基本元素不同，分成空闲盘块链和空闲盘区链，对空闲区域进行管理。

空闲盘块链：将磁盘上所有的空闲空间以盘块为单位拉成一条链。创建文件时，系统从链首开始依次给文件分配块。回收式，系统依次将被回收的盘块插入到空闲盘块链的末尾。
特点：分配与回收简单，没有碎片产生；但是分配空间的时候要产生多次重复的操作。

空闲盘区链：将外存上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。每个盘区上存储指向下一个盘区的指针，和这个盘区的大小信息。当需要分配的时候会根据文件的大小和一定的算法(一般是首次适应算法)找到合适区域。当回收的时候要注意与相邻的空闲盘区合并。
特点：可以用作连续分配，也可以离散分配；可以一次给一个文件分配一个区域，分配效率高，且空闲盘区链较短；但分配与回收的过程比较复杂。

位示图法

采用二进制的一位来表示一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。其中，值为 1 表示该盘块已被分配。
这样，一个 $m\times n$ 位组成的位示图就可以表示 $m\times n$ 个盘块的使用情况。

下面我们给出一个有 $m$ 行 $n$ 列的位示图，其盘块的具体分配方法。其中，我们规定行列数均是从 1 开始编号的，盘块号也是从 1 开始计算。请注意，这只适用于下面的计算式，如果具体题目中有所变动应当自行调整。

盘块的分配逻辑如下：

顺序扫描位示图，找出一个或一组值为 0 的二进制位。
将找出一个或一组值为 0 的二进制位转换成与之对应的盘块号。例如找到当前 $map[i][j]=0$ ，则其盘块号为 $b=n(i-1)+j$
修改找到的二进制位的标志为1，即 $map[i][j]\leftarrow 1$

盘块的回收：
将需要回收的盘块的盘块号转化为具体的位示图坐标，并还原标识。即：

$\begin{aligned} i&=(b-1)/n+1\\j&=(b-1)\% n+1\\\\ &map[i][j]\leftarrow0 \end{aligned}$

成组链接法

空闲表法和空闲链表法都不适用于大型文件系统，这会使得其本身就占用过大空间。
而在 UNIX 系统中，对于外存空闲空间的分配，采用的是成组链接法。这种方法结合了以上两种方法的优点，又克服了他们都有的“表太长了”的缺点。

待更

虚拟文件系统

待更

分区与安装

I/O 管理

I/O软件层次结构

（1）用户层软件：实现用户交互接口，通过库函数实现系统调用
（2）设备独立性软件：与硬件底层无关的操作，对上层的封装操作，向上一层提供调用接口，设备保护，容错处理，设备分配与回收，数据缓冲区管理，逻辑设备与物理设备映射映射
（3）设备驱动程序：CPU指令相同，负责控制硬件设备，将CPU指令转成设备操作，驱动程序以独立进程的形式存在
（4）中断处理程序（I/O中断的应答）：IO完成后发送中断信号，执行中断处理程序，会直接操作硬件

高速缓存与缓冲区

在块设备输入时，假设一块磁盘数据写入缓冲区的时间为 $T$ ，操作系统将该缓冲区的数据传送到用户区的时间为 $M$ ，CPU 对数据进行处理的时间为 $C$ ，则：

单缓冲： $\max(C,T)+M$
双缓冲： $\max(C+M,T)$

SPOOLing 技术

利用外存/磁盘存储区域，将独占设备共享

磁盘和固态硬盘

磁盘调度算法

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

寻道时间 $T_s=m\times n+s$ $T_{s} = m \times n + s$ .
- 活动头磁盘在读写信息前，将磁头移动到指定磁道所需的时间。其中， $m$ 是磁盘驱动器速度有关的常数，约为 0.2ms； $s$ 是磁臂的启动时间，约为 2ms； $n$ 是所需跨越的磁道数。
旋转延迟时间 $T_r=1/2r$ $T_{r} = 1/2 r$
- 磁头定位到某一磁道的扇区所需要的时间。设磁盘的旋转速度为 $r$ 。
传输时间 $T_t=b/rN$ $T_{t} = b / r N$
- 从磁盘读出或写入数据所经历的时间，取决于每次读写的字节数 $b$ 、磁盘每秒转数 $r$ 和每一个磁道上的字节数 $N$ 。

FCFS 先来先服务

SSTF 最短寻道时间优先

SCAN 扫描/电梯调度

LOOK改进

CSCAN 循环扫描算法

CLOOK改进

物理与逻辑初始化

一个新的磁盘是一个空白板，必须分成扇区以便磁盘控制器能读写，这个过程称为低级格式化，也叫物理格式化。

物理格式化为每个磁盘的每个扇区采用特别的数据结构，包括校验码。

为了使用磁盘存储文件，操作系统还需要将其数据结构记录在磁盘上，这个过程分为两步：

将磁盘分为一个或多个柱面组成的分区，每个分区可作为一个独立的磁盘
操作系统将初始文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间及一个初始为空的目录。这个是逻辑初始化。

操作系统的基本概念

操作系统的特征

并发性| Concurrence

共享性| Sharing

虚拟性| Vitual

异步性| Asynchronism

操作系统的接口

命令接口

程序接口

操作系统发展历程

操作系统运行环境

处理器运行模式

中断和异常

操作系统结构

分层式架构与模块化架构

宏内核架构与微内核架构

操作系统引导

虚拟机

同步与互斥

临界资源

进程的制约

软件实现互斥

硬件实现互斥

互斥锁

信号量

信号量实现同步

信号量实现互斥

管程

经典同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

吸烟者问题

关于教科书略过的叫号问题

死锁

死锁产生的原因

死锁的必要条件

极端死锁情况

死锁的处理策略

死锁预防

死锁避免

死锁检测与解除

银行家算法

内存管理

程序链接与装入

连续分配管理方式

单一连续分配

固定分区分配

动态分区分配

基本分页存储管理

页表

地址变换机构

快表

多级页表

基本分段存储管理

地址变换机构

段页式管理

一道综合题

虚拟内存管理

请求分页管理方式

页表机制

缺页中断

地址变换机构

页框分配

内存分配策略

物理块调入算法

调入页面的时机

页面置换算法

最佳置换算法 (Optimal, OPT)

先进先出置换算法 (First In First Out, FIFO)

最近最久未使用置换算法 (Least Recently Used, LRU)

CLOCK算法 (Not Recently Used, NRU）

改进型CLOCK算法

页故障的上下限

抖动与工作集

抖动的含义与原因

工作集的概念

预防抖动的方法

内存映射文件

虚拟存储器的性能