操作系统复习

# 概论

# 操作系统的定义和功能

# 操作系统的定义

一组计算机程序的集合，主要用以控制和管理计算机的硬件和软件资源，合理地组织计算机的工作流程，向应用程序和用户提供方便、快捷、友好的使用接口

# 操作系统的功能 😊

进程管理
存储管理
文件管理
设备管理

# 操作系统的特征 😎

并发
共享
虚拟
异步

# 操作系统的发展

手工操作时代
早期单道批处理系统时代
多道批处理系统时代

# 操作系统的分类 😊

# 批处理操作系统

主要特征
- 用户脱机工作
- 成批处理作业
- 单 / 多道程序运行
- 作业周转时间长

# 分时操作系统

主要特征：
- 同时性。允许各终端用户同时工作，系统分时响应用户请求（使用 CPU 并不同时）
- 交互性。支持联机的操作方式，用户可以在终端上通过操作系统进行人 - 机对话，随时控制和调试程序，以交互的方式工作
- 独立性。用户之间彼此独立的工作，好象独占一台计算机系统一样，互不干扰
- 及时性。用户请求能在较短的时间内得到响应

# 实时操作系统

系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

# 个人计算机操作系统

主要特点：
- 图形用户接口
- 开放性
- 多媒体支持
- 应用软件丰富
- 操作系统管理性能高

# 网络操作系统

除具备通常操作系统功能外，还具备联网功能，支持网络体系结构和各种网络通信协议，提供网络互连能力，支持可靠、有效、安全的数据传输
主要采用客户机 / 服务器 (C/S) 工作方式
- 客户机一般由微型计算机承担，主动从本地向服务器提出服务请求
- 服务器接收客户机请求、处理请求的服务、返回服务结果。一般由高档微机、小、中、大型机承担
对等模式：网络中的每台计算机同时具有客户端和服务器两种功能

# 分布式操作系统

特点：
- 计算机网络系统的高级形式，由多台计算机组成，计算机之间没有主次之分
- 数据和控制及任务的分布性、整体性、资源共享的透明性、各节点的自制性和协同性

# 嵌入式操作系统

指运行在嵌入式 (计算机) 环境中，对整个系统各种部件和资源进行统一协调、处理、指挥和控制的系统软件。它具有通常操作系统的基本功能
与一般操作系统有很大不同，主要体现在微型化、可定制、实时性、可靠性、易移植、开发工具与使用环境密切相关等特点

# 操作系统的接口

# 程序接口

系统调用：“系统调用” 可以获得操作系统的底层服务，从而进一步使用或访问系统管理的各种软硬件资源。不同的操作系统提供的系统调用的种类、数量和名字不尽相同
API（application programming interface）
- 常用的 Windows 系统，微软公司只公布了相关的 API，它是一种应用程序编程接口，是在操作系统系统调用的基础经过规范整理出来，面向社会公布的唯一的接口方式
- 由于不是直接的系统调用，其效率有所损失。微软公司没有发布全部的 API，也为开发程序带来了一定的难度
系统调用 & POSIX 标准
- 系统调用内部的具体实现与硬件相关，直接使用会产生问题：
  - 接口复杂，使用困难
  - 应用程序的跨平台可移植性受到很大限制
- POSIX 标准：专门规定内核的系统调用接口标准，操作系统若遵循此标准，则应用程序在不同操作系统之间就具有可移植性
  - Unix/Linux 遵循此标准
  - Windows NT-based 系统不能直接支持新版 POSIX 接口
系统调用的处理过程
1. 应用程序使用系统调用时会产生一条指令（陷入指令或访管指令），该指令中存放了对应系统调用的功能号，有时还附带传递给内核的参数： 系统调用—功能号—入口地址表—入口地址
2. 处理机在执行到该访管指令时发出相应的中断信号给 “陷阱处理机制”
3. 陷阱处理机制启动相关的内核函数完成该系统调用所要求的功能：保护 CPU 现场、获取功能号、根据功能号查找对应内核函数入口地址表、转到入口地址执行内核函数、内核函数执行完，中断处理结束
4. 恢复 CPU 现场，继续执行中断点的下一条指令
注意：执行系统调用时，应用程序从用户态（目态）转到了核心态（管态），即执行内核函数时必须在核心态下运行，但访管指令本身是在用户态下执行的

# 操作接口

命令界面（CLI，Command Line Interface ）
- 简单命令的一般形式：命令参数 1 参数 2 … 参数 n
- Windows 操作系统的基本命令：type、erase、attrib、copy、xcopy、dir、cd、md、rd、tree、ver 等
图形界面（ GUI，Graphics User Interface ）
作业控制命令
- 专为批处理作业的用户提供的，所以也称批处理用户接口。操作系统提供一个作业控制语言 JCL（Job Control Language），它由一组作业控制语句、作业控制操作命令及相应语法规范组成
- 用户利用作业控制语言书写批处理作业控制说明书，操作系统解释作业控制说明书，按其要求一步步地运行用户作业。
  - DOS 下的批处理命令是一种简单的作业控制语言（.bat）
  - UNIX 的 Shell 语言是现代计算机一种功能强大的作业控制语言

# 操作系统的设计实现方法

# 操作系统设计与开发

操作系统设计与开发特点
- 与硬件关联
- 复杂程度高
- 生产周期长
操作系统的设计原则
- 可靠性
- 方便性
- 高效率
- 易维护性
- 可扩充性
- 开放性

# 操作系统的体系结构

无结构操作系统
模块化结构
分层结构
客户 / 服务器结构（微内核）
虚拟机结构
面向对象结构

# 进程管理

# 程序的执行方式

# 程序的顺序执行 😊

一个具有独立功能的程序独占处理器直至最终结束的过程称为程序的顺序执行
- 程序设计中的顺序控制结构仅能控制程序内部指令的执行序列
- 程序的顺序执行意味着运行时程序间的执行序列也是顺序的 —— 一个程序执行完了，才能执行另一个程序
顺序执行的特性：
- 顺序性
- 封闭性
- 可再现性
- 程序的顺序执行方式便于程序的编制与调试，但不利于充分利用计算机系统资源，运行效率低下

# 程序的并发执行与并行执行 😎

为了提高系统的运行效率，允许 “同时” 执行多个程序
并行（parallel）：多个事件在同一时刻发生
并发（concurrent）：多个事件在同一时期内发生
显然，并行是并发的特例，程序并行执行的硬件前提是系统中有多个 CPU
并发的本质是一个 CPU 在多个程序运行过程中的时分复用
并发执行的特性：
- 间断性
- 开放 / 交互性
- 不可再现性
- 进行并发程序设计时应当避免由于程序间开放交互引起的不可再现性而产生运行时错误

# 进程概念的引入

程序（program）：静态的代码文件（*.exe）
进程（process）：程序在某个数据集合上的一次执行，系统资源分配的基本单位
作业（job）：批处理系统要装入系统运行处理的一系列程序步骤和数据

# 进程的特征与控制

# 进程的相关概念

进程有以下特征
- 结构性
- 动态性
- 独立性
- 并发性
进程分类：系统进程、用户进程

进程上下文（process context）

用户级上下文（user-level context）：进程的代码区、数据区、用户栈区和共享存储区
系统级上下文（system-level context）：PCB、内存管理信息、进程环境块、系统栈
寄存器上下文（register context）
一个进程被系统调度而占有 CPU 时，会发生 CPU 在新老进程之间切换，切换的内容是进程上下文，进程运行是在进程的上下文中执行的
一个典型的上下文切换过程

	context_switch( ){
	Push registers onto stack
	Save ptrs to code and data.
	Save stack pointer // 以上语句保护当前进程上下文
	Pick next process to execute // 选中 / 调度新进程
	// 以下语句恢复所选中 / 调度的进程的上下文
	Restore stack ptr of that process
	Restore ptrs to code and data.
	Pop registers
	Return
	}

# 进程状态及转换 😎

进程的状态
- 就绪状态（ready）：进程在内存中已经具备执行的条件，等待分配 CPU
- 运行状态（running）：进程占用 CPU 并正在执行
- 阻塞状态（blocked）：也称为等待（waiting）状态 —— 运行的进程由于发生某事件而放弃 CPU
有挂起功能的进程状态：
- 挂起就绪（ready suspended）
- 挂起阻塞（blocked suspended）
- 进程在运行态也可以被挂起，转换为挂起就绪状态
- 阻塞状态的进程被挂起后，若阻塞事件或 I/O 请求完成，则进程状态转换为挂起就绪状态 —— 仍然是挂起状态
- 创建进程时若没有足够的内存空间，则转入挂起就绪状态
- 只有处于就绪态的进程才有可能被调度分配 CPU 运行

# 进程控制块 PCB

为了描述和控制进程运行的数据结构 —— 进程控制块（Process Control Block），或称为进程描述符（Process Descriptor），进程存在的惟一标志
1. 进程标识信息 —— 内部标识符（PID）和外部标识符（进程名）
2. 现场信息 —— 进程运行时 CPU 的即时状态 —— 各寄存器的值
3. 控制信息 —— 程序和数据地址、进程同步和通信机制信息、进程的资源清单和链接指针，进程状态、进程优先级……
操作系统根据 PCB 对进程进行控制和管理
- 查询进程现行状态及优先级
- 恢复现场
- 相关进程同步、通信
创建新进程时，建立 / 分配 PCB，进程结束时回收 PCB
PCB 由系统多个功能模块读写，须常驻内存，并进一步组织形成队列

# 进程控制 😊

CPU 的运行模式
- 核心态（内核态），也称为管态（supervisor mode），Ring 0：内核代码、设备驱动、特权指令、直接访问物理内存空间、设备端口
- 用户态，也称为目态，Ring 3：普通指令、保护模式安全限制、访问映射的虚拟地址空间、系统许可的映射端口
不同于进程切换，也不一定引起进程切换或状态转换
一般来说，当发生中断或系统调用时，用户进程暂停，CPU 模式从用户态切换到核心态，执行系统服务例程，此时进程仍在原上下文中运行，仅模式变化
进程控制 —— 系统对进程生命周期的各个环节进行控制
- 进程控制的职能是对系统中的所有进程实行有效的管理 —— 对一个进程进行创建、撤销或终止，以及在某些进程状态间的转换控制
- 允许一个进程创建和控制另一个进程，前者为父进程，后者为子进程
进程控制通常由 原语（primitive） 完成。
原语的特性：
- 由若干条指令组成，实现某个特定功能，在执行过程中不可被中断的程序段
- 不可分割的执行单位，不能并发执行
- 是操作系统核心（不是由进程而是由一组程序模块所组成）的一个组成部分，且常驻内存
- 通常在核心态 / 管态下执行
进程控制原语
1. 创建进程：建立 PCB、填入信息、插入就绪队列，操作系统创建进程主要步骤
  （1）命名进程：为新进程设置进程标志符；
  （2）从 PCB 集合中为新进程申请一个空 PCB；
  （3）确定新进程的优先级；
  （4）为新进程的程序段、数据段和用户栈分配内存空间；如果进程中需要共享某个已在内存的程序段，则必须建立共享程序段的链接指针；
  （5）为新进程分配除内存外的其它各种资源；
  （6）初始化 PCB，将新进程的初始化信息写入进程控制块；
  （7）如果就绪队列能够接纳新创建的进程，则将新进程插入到就绪队列；
  （8）通知操作系统的记账、性能监控等管理模块
  导致创建进程的事件：登录、作业调度、提供服务 —— 系统内核直接调用创建原语创建新进程、应用请求 —— 由用户调用操作系统提供的系统调用完成（Windows 的 API：CreateProcess）
2. 撤消与终止进程：进程完成后，应退出系统而消亡，系统及时收回占有的全部资源以便其它进程使用，撤销原语撤销的是 PCB，而非进程的程序段
3. 阻塞与唤醒进程：进程阻塞是进程的自主行为，唤醒则是被动的
4. 挂起与激活进程：既可以由该进程自己调用，也可由其它进程或系统调用，但激活原语只能由其它进程或系统调用

# 进程的互斥与同步

# 竞争和协作

竞争，会引发以下两种极端情况：
- 死锁（deadlock）：一组进程都陷入永远等待的状态
- 饥饿（starvation）：被调度程序长期忽视
协作 —— 同步（synchronization）
- 一个进程的执行依赖于其协作进程的消息或信号
竞争 —— 互斥（mutual exclusion）
- 互斥也是一种特殊的同步 —— 以一定次序协调地使用共享资源

# 与时间有关的错误

Bernstein 条件
- $R(p_i)=\{a_1,a_2,…,a_n\}$ ，程序 $p_i$ 在执行期间引用的变量集
- $W(p_i)=\{b_1,b_2,…,b_m\}$ ，程序 $p_i$ 在执行期间改变的变量集
- 若两个程序的变量集交集之和为空集： $R(p_1)∩W(p_2)∪R(p_2)∩W(p_1)∪W(p_1)∩W(p_2)=\{ \}$ ，则并发进程的执行与时间无关
若两个进程共享了数据集，则可能存在制约关系，形成交互的并发进程
执行的相对速度无法相互控制，可能会出现所谓与时间有关的错误

# 临界资源与临界区 😊

临界资源：在某段时间内只能允许一个进程使用的资源 (打印机、磁带机等硬件设备和变量、队列等数据结构)
临界区：进程中访问临界资源的代码段，几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源
临界区调度原则：
1）一次至多一个进程能够执行其临界区代码；
2）如果已有进程在临界区运行，其它试图进入的进程应等待；
3）进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入
选择临界区调度策略时，不能因为该原则而造成进程饥饿或死锁
实现临界区管理有软件和硬件两种方式

# 软件方法管理临界区

实施依据是内存访问的基本互斥性 —— 对内存同一地址的并发访问将被存储管理器序列化，而访问的顺序并无需事先指定，不需要硬件、操作系统或程序设计语言的任何支持
Peterson 算法（1981 年）
- 为每个进程设置标志 flag 用于表示该进程是否有意访问临界资源（进入临界区），又设置标志 turn 用于表示临界资源此时是否有其它进程在访问
- 只有在对方进程的访问标志 flag 为 true 并且 turn 也为该进程标识时，才表明对方进程在访问临界资源，需要等待对方进程访问完并释放资源后才能访问；否则本进程不需要等待对方进程即可访问临界资源
软件方法管理临界区的标志算法比较容易出现标志逻辑混乱的情况，其根本原因在于管理临界区标志要用两条指令：
- 一条指令是看对方的标志
- 一条指令是设置自己的标志
进程并发可能导致进程在执行这两条指令时被另一个进程中断
保证进程在执行这两条指令时不被中断，即可很容易地进行临界区管理

# 硬件方式管理临界区

禁止中断法
- 在检查临界区标志的两条指令之前将中断关上，临界区访问完后系统才打开中断
- 缺点：影响计算机效率、不能及时处理重要程序、对多 CPU 系统无效
特殊指令法
- 特殊的硬件指令保证几个动作的原子性 —— 不会被中断，不受到其它指令的干扰
- “测试并设置（Test and Set）” 指令 TS ，或者交换（exchange）指令 SWAP / xchg
TS 指令：将布尔变量 x 与临界区关联起来 —— 如果 x 为真，表示没有进程在临界区内，临界资源可用，并立即将 x 置为 false，即阻止其它进程进入临界区，访问临界资源；若 x 为假，则表示有其它进程进入临界区，本进程需要等待。

	bool TS (bool & x) {
	if (x == true) {
	x = false;
	return true;
	}
	else return false;
	}

TS 指令实现互斥：

	bool x = true；
	cobegin
	process Pi ( ) {
	while (!TS(x));
	临界区 i
	x = true;
	}
	coend

用交换指令实现互斥：

	bool lock = false;
	cobegin
	process Pi() {
	bool ki = true;
	do {
	SWAP(ki, lock);
	} while(ki);
	临界区i
	SWAP(ki, lock);
	}
	coend

# 进程同步机制 😎

常见的同步机制有锁、信号量、管程和消息传递

# 信号量机制

在这一体制下，进程在某一特殊点上被迫停止执行（阻塞）直到接收到一个对应的特殊变量值，这种特殊变量就是信号量 (semaphore)，除了赋初值外，信号量的值只能由 P 操作和 V 操作进行修改，进程通过 P、V 这两个特殊操作在信号量所关联的系统资源上实现同步与互斥
信号量表示系统资源的实体
具体实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是在信号量关联资源上阻塞的进程队列的队头指针
信号量在操作系统中的主要作用是封锁临界区、进程同步和维护资源计数。
P 操作和 V 操作原语的功能：
- P(s) ：将信号量 s 的值减 1，若结果小于 0，则调用 P(s) 的进程被阻塞，并进入信号量 s 的阻塞队列中；若结果不小于 0，则调用 P(s) 的进程继续运行
- V(s) ：将信号量 s 的值加 1，若结果不大于 0，则调用 V(s) 的进程从该信号量阻塞队列中释放、唤醒一个处于等待状态的进程，将其转换为就绪状态，调用 V(s) 的进程继续运行；若结果大于 0，则调用 V(s) 的进程继续运行
信号量的数据类型以及 P、V 操作原语的定义

	typedef struct semaphore {
	int value;
	struct pcb *list;
	};
	void P(semaphore &s) {
	s.value--;
	if (s.value < 0) block(s.list);
	}
	void V(semaphore &s) {
	s.value++;
	if (s.value <= 0) wakeup(s.list);
	}

P 操作意味进程申请一个资源，求而不得则阻塞进程，V 操作意味着释放一个资源，若此时还有进程在等待获取该资源，则被唤醒
若信号量的值为正数，该正数表示可对信号量可进行的 P 操作的次数，即可用的资源数。信号量的初值一般设为系统中相关资源的总数，对于互斥信号量，初值一般设为 1
若信号量的值为负，其绝对值表示有多个进程申请该资源而又不能得到，在阻塞队列等待，即在信号量阻塞队列中等待该资源的进程个数
信号量机制实现进程互斥进入临界区

	semaphore mutex = 1;
	cobegin
	process Pi( ) {
	P(mutex);
	临界区i
	V(mutex);
	}
	coend

# 进程同步的经典问题

# 生产者 - 消费者问题

$n$ 个生产者进程和 $m$ 个消费者进程，连接在一块长度为 $k$ 个单位的有界缓冲区上（故此问题又称有界缓冲问题）。其中， $P_i$ 和 $C_j$ 都是并发进程，只要缓冲区未满，生产者 $P_i$ 生产的产品就可送入缓冲区；只要缓冲区不空，消费者进程 $C_j$ 就可从缓冲区取走并消耗产品
在并发环境下生产者、消费者进程访问缓冲区的速度不协调、不匹配 —— 不同步，或者没有做到互不影响地使用、更新缓冲区 —— 互斥，所以会出现运行错误甚至是死锁
信号量机制解决多个生产者 - 消费者、共享多个缓冲区的生产者 - 消费者问题

	item B[k];// 缓冲区，长度 k
	semaphore empty = k;// 可用的空缓冲区数
	semaphore full = 0;// 缓冲区内可用的产品数
	semaphore m1 = m2 = 1;// 互斥信号量
	int in = 0;// 缓冲区放入位置
	int out = 0;// 缓冲区取出位置
	cobegin
	process producer_i() {
	while (true) {
	produce( );// 生产一个产品
	P(empty);/申请空缓冲区
	P(m1);// 申请互斥使用缓冲区
	append to B[in]; // 产品放入缓冲
	in = (in + 1) % k; // 更新缓冲区指针
	V(m1);
	V(full);
	}
	}
	process consumer_j() {
	while (true) {
	P(full);
	P(m2);
	take( ) from B[out];
	out = (out + 1) % k;
	V(m2);
	V(empty);
	consume();
	}
	}
	coend

# 读者 - 写者问题

两组并发进程，读者和写者，共享一个文件 F，要求：
- 允许多个读者进程同时读文件
- 只允许一个写者进程写文件
- 任何一个写者进程在完成写操作之前不允许其它读者或写者工作
- 写者执行写操作前，应让已有的写者和读者全部退出
信号量机制解决读者 - 写者问题

	int readcount = 0; // 读进程计数器
	semaphore ws = 1, mutex = 1;
	cobegin
	process reader_i() {
	P(mutex);
	readcount++;
	if(readcount == 1) P(ws);
	V(mutex);
	读文件;
	P(mutex);
	readcount--;
	if(readcount == 0) V(ws);
	V(mutex);
	}
	process writer_j() {
	P(ws);
	写文件;
	V(ws);
	}
	coend

写者优先算法

	semaphore rmutex, wmutex, S; // S 在写者到达后封锁读者
	rmutex = 1; wmutex = 1; S = 1;
	int count = 0;
	cobegin
	process reader {
	P(S);
	P(rmutex)
	if (count == 0) P(wmutex)；
	count++;
	V(rmutex);
	V(S);
	READ FILE;
	P(rmutex)；
	count--;
	if (count == 0) V(wmutex);
	V(rmutex);
	}
	process writer{
	P(S);
	P(wmutex)；
	WRITE the FILE;
	V(wmutex);
	V(S);
	}
	coend

# 哲学家就餐问题

五个哲学家围坐在一张圆桌前，每个哲学家面前有一碗意大利面和一只叉子，哲学家的生活由思考和进餐两个活动组成，进餐时需要两只叉子，但每个哲学家只有两只叉子，所以他们需要共享叉子
算法 1：给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。

	semaphore chopsticks [5];
	for (int i = 0; i < 5; i++) chopsticks[i] = 1;
	cobegin
	process philmac_i() {//i=0,1,2,3,4
	while (true) {
	think()；
	if(i % 2 == 0) {
	P(chopsticks[i])；
	P(chopsticks[(i + 1) % 5])；
	}
	else{
	P(chopsticks[(i + l) % 5]);
	P(chopsticks[i]);
	}
	eat()；
	V(chopsticks[i])；
	V(chopsticks([i + 1] % 5))；
	}
	}
	coend

算法 2：通过发放令牌最多允许 4 个哲学家同时吃面

	semaphore chopsticks[5] = {1, 1, 1, 1, 1};
	semaphore token = 4;//4 个令牌
	int i;
	cobegin
	process philmac_i() {//i=0,1,2,3,4
	while (true) {
	think();
	P(token);
	P(chopsticks[i]);
	P(chopsticks[(i + l) % 5]);
	eat();
	V(chopsticks[(i + l) % 5]);
	V(chopsticks[i]);
	V(token);
	}
	}
	coend

管程解决哲学家就餐问题的算法：

采用 Hoare 管程实现，算法思想是将哲学家的状态分为思考、饥饿、吃面，并且仅当哲学家左右两边的筷子都可用才允许他拿筷子，否则一只筷子也不拿

# 睡眠理发师问题

理发店里有一个理发师，一把理发椅，N 个供等候顾客休息的椅子。若无顾客，理发师躺在理发椅上睡觉。顾客到来时唤醒理发师，若理发师正在理发，新来的顾客坐在空闲的休息椅上等候，如果没有空椅子，顾客离开。
进程 Barber() 和 Customer() 分别描述理发师和顾客，理发师和顾客之间是同步的关系，顾客之间是互斥关系，竞争理发师和休息椅。
算法采用信号量机制，引入一个控制变量和 3 个信号量：
- 控制变量 waiting 用来记录等候理发的顾客数，初值为 0；
- 信号量 customers 用来关联表达等候理发的顾客数，并用作阻塞理发师进程，初值为 0；
- 信号量 barbers 用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为 0；
- 信号量 mutex 用于互斥，初值为 1。

# 进程通信 😊

进程通信（IPC：Inter-Process Communication）是进程之间数据的相互交换和信息的相互传递，是一种 高级通信机制

# 消息传递通信

进程将通信数据封装在消息中，消息通过消息缓冲区在进程之间互相传递
消息是指进程之间以不连续的成组方式发送的信息
消息缓冲区应包含消息发送进程标识、消息接收进程标识、指向下一个消息缓冲区的指针、消息长度、消息正文等。缓冲区构成了进程通信的一个基本单位

# 直接通信

在直接通信方式下，发送进程将发送的数据封装到消息正文后，发送进程必须给出接收进程的标识，然后用发送原语将消息发送给接收进程
收发消息的原语：
- send （接收进程标识，消息队列首指针）
- receive （发送进程标识，接收区首地址指针）
在直接通信中隐含着发送进程与接收进程之间的同步问题
send() ：
- 查找接收进程的 PCB，存在，则申请一个存放消息的缓冲区，若消息缓冲区已满，则返回到非同步错误处理程序入口，进行特殊处理
- 若接收进程因等待此消息的到来而处于阻塞状态，则唤醒此进程。将存放消息的缓冲区连接到接收进程的消息队列上
- 两种同步方式
  - 发送进程阻塞等待接收进程发回的确认信息
  - 发送进程发送完消息后，不阻塞等待接收进程的回送信息，而是继续执行；限定时间到仍未收到确认消息，重发或放弃
receive() ：
- 接收进程在其进程空间中确定一个接收区，复制 / 读取消息缓冲区中的内容，释放消息缓冲区
- 若无消息可读，则阻塞接收进程至有消息发送来为止
- 两种同步方式
  - 接收进程调用 receive 原语并一直阻塞等待发送来的消息，直到接收到消息 —— 与发送进程的第二种同步方式匹配
  - 接收进程调用 receive 原语后，不阻塞等待发送来的消息，而是继续执行 —— 与发送进程的第一种同步方式匹配

# 间接通信

消息传递的间接通信方式是指发送进程与接收进程之间通过邮箱来进行通信，发送进程将消息发送到邮箱，接收进程从邮箱接收消息
- 发送原语： send(mailboxname, message) ;
- 接收原语： receive(mailboxname, message) ;
与直接通信比较，间接通信灵活性更大，不需要发送进程与接收进程同步，是一种方便、可靠的进程通信方式

# 共享内存通信

共享内存通信分为
- 基于共享数据结构的通信方式 —— 比较低效，只适于传递少量数据
- 基于共享存储区的通信方式
共享内存通信的实现过程如下：
- 建立共享内存区 —— 标识和长度等参数
- 共享内存区的管理
- 共享内存区的映射与断开
允许多个进程将共享内存映射到自己的地址空间，进程对各自所映射的地址段的读写操作代码应纳入临界区管理

# 管道通信

管道是连接读、写进程的一个特殊文件，允许进程按 FIFO 方式传送数据，也能使进程同步执行操作。发送进程以字符流形式把数据送入管道，接收进程从管道中接收数据
管道的实质是一个共享文件（文件系统的高速缓冲区中），进程对管道应该互斥使用
写进程把一定数量的数据写入 pipe ，就去睡眠等待，直到读进程取走数据后，将其唤醒
命名管道（named pipe）用来在不同的地址空间之间进行通信，不仅可以在本机上实现两个进程间的通信，还可以跨网络实现两个进程间的通信，特别为服务器通过网络与客户端交互而设计，是一种永久通信机制
每一个命名管道都有一个唯一的名字

# 进程调度

由于进程总数一般多于 CPU 数，必然会出现竞争 CPU 的情况。进程调度的功能就是按一定策略、动态地把 CPU 分配给处于就绪队列中的某一进程执行
两种基本的进程调度方式，抢占方式和非抢占方式，也称剥夺式（preemptive）和非剥夺式（non_preemptive） 调度
剥夺原则有：优先权原则、短进程优先原则、时间片原则等
可能引发进程调度的时机：
- 正在运行的进程运行完毕；
- 运行中的进程要求 I/O 操作；
- 执行某种原语操作 (如 P 操作) 导致进程阻塞；
- 比正在运行的进程优先级更高的进程进入就绪队列；
- 分配给运行进程的时间片已经用完

# 进程调度模型 😎

三级调度
- 高级调度（High-Level Scheduling），作业调度
  - 从后备作业中选若干个作业，分配必要的资源，建立相应的用户作业进程和系统服务进程（如输人、输出进程），将其程序和数据调入内存……
- 中级调度（Intermediate-Level Scheduling），平衡调度
  - 在内存紧张时，将一些暂时不能运行的进程对换到外存。当内存有空间时，再将其重新调入内存
- 低级调度（Low-Level Scheduling），进程调度
  - 根据一定的算法将 CPU 分派给就绪队列中的一进程
  - 最基本的、必须的一种调度

# 调度算法选择 / 评价准则

调度算法也称为调度策略，评价调度算法的参数：
- 处理器利用率（CPU utilization）= CPU 有效工作时间 / CPU 总的运行时间
- 响应时间（response time）：交互环境下用户从键盘提交请求开始，到系统首次产生响应为止的时间；是分时和实时系统调度性能重要指标。
- 周转时间（turnaround time）： $T_i = T_f – T_s$ ，即：周转时间 = 完成时刻 - 提交时刻；批处理系统重要指标
- 带权周转时间： $W_i = 作业的周转时间T_i / 系统为作业提供的服务时间Ts_i$ ，显然带权周转时间总大于 1 。实质是，周转时间与系统为其提供服务的时间之比
- 平均作业周转时间： $T = (ΣT_i) / n$
- 平均作业带权周转时间： $W = (ΣW_i) / n$
- 系统吞吐量（throughput）：单位时间内完成的进程（任务 / 交易）数目
- 公平性：不出现饥饿情况

# 调度算法 😎

# 先来先服务（First-Come First-Served，FCFS）

按进程就绪的先后顺序来调度，到达得越早，就越先执行
获得 CPU 的进程，未遇到其它情况时，一直运行下去
是一种非抢占式算法，简单易实现
没有考虑执行时间长短、运行特性和资源的要求
FCFS 调度算法适用性
- 对长作业非常有利，对短作业不利
- 对 CPU 繁忙型的作业非常有利，对 I/O 繁忙型作业非常不利 —— 进程 I/O 阻塞结束后需再次排队
- 非抢占式算法，对响应时间要求高的进程不利
- 平均作业周转时间与作业提交的顺序有关

# 短作业优先（Shortest-Job-First，SJF）

以进入系统的作业所要求的 CPU 服务时间为标准，总选取估计所需 CPU 时间最短的作业优先投入运行。
- 算法易于实现，效率不高，主要弱点是忽视了作业等待时间。
- 对长作业不利，如果系统不断接收短作业，可能会出现饥饿现象。
- 非抢占式算法，对响应时间要求高的进程不利。
- SJF 的平均作业周转时间比 FCFS 要小，故它的调度性能比 FCFS 好。
- 实现 SJF 调度算法需要知道作业所需运行时间，而要精确知道一个作业的运行时间是办不到的。

# 最短剩余时间优先（Shortest Remaining Time First，SRTF）

若一就绪状态的新作业所需的 CPU 时间比当前正在执行的作业剩余任务所需 CPU 时间还短，SRTF 将打断正在执行作业，将执行权分配给新作业
SRTF 将 SJF 算法改为抢占式，因此只要有新作业进入就绪队列，就可能会引发进程切换。
SRTF 调度算法适用性：
- 长进程仍有可能出现饥饿现象
- 必须计算运行、剩余时间，系统开销增大
- 因抢占式调度，系统性能会比 SJF 要好

# 高响应比优先（Highest Response Ratio First，HRRF）

是 FCFS 与 SJF 两种算法的折衷，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业等待过久，改善了调度性能，仍属于非抢占式算法
- 响应比为作业的响应时间与作业所需运行时间之比，简化为：响应比＝ 1 +（已等待的时间 / 估计运行时间）
HRRF 算法适用性：
- 由定义可知，短作业容易得到较高响应比，长作业在等待了足够长的时间后，也将获得足够高的响应比，因此不会发生饥饿现象
- 需要经常计算作业的响应比，导致额外的开销
- HRRF 算法的平均周转时间和平均带权周转时间都介于 FCFS 与 SJF 算法之间，比 SJF 算法差，比 FCFS 算法优
- 虽然 HRRF 算法的平均周转时间和平均带权周转时间不及 SJF 算法，但是，在现实中其可以实现，结果也比较可靠
- 如果在算法中引入抢占调度，则算法过程会更复杂。因为所有作业的响应比是动态变化的，抢占时间的计算需要解多个方程得到

# 优先权（Highest-Priority-First，HPF）

根据进程的优先权进行进程调度，每次总是选取优先权高的进程调度，也称优先级调度算法，一般是抢占式调度
- 优先权通常用一个整数表示，也叫优先数
  - Windows 系统中有 0~31 共 32 个优先级，31 最高
  - Unix 系统中，使用数值 - 20~+19 来表示优先级，-20 优先级最高
- 优先权可由系统或用户给定
  - 静态优先权
  - 动态优先权

# 时间片轮转（Round-Ribon，RR）

调度程序把 CPU 分配给进程使用一个规定的时段，称为一个时间片（如 100ms），就绪队列中的进程轮流获得 CPU 的一个时间片。当一个时间片结束时，系统剥夺该进程执行权，等候下一轮调度，属于抢占式调度
- 时间片的长短，影响进程的进度
- 需要从进程数、切换开销、系统效率和响应时间等方面综合考虑，确定时间片大小

# 多级反馈队列（Multilevel-Feed-Queue，MFQ）

又称反馈循环队列，是一种基于时间片的进程多级队列调度算法的改进算法。系统设置多个就绪队列，最高级就绪队列的优先级最高，随着就绪队列级别的降低优先级依次下降，较高级就绪队列的进程获得较短的时间片
不需事先知道各进程所需运行时间，因而可行性较高，同时综合考虑了进程的时间和优先权因素，既照顾了短进程，又照顾了长进程，是一种综合调度算法，被广泛应用于各种操作系统中

# 多 CPU 系统中的调度

多处理器系统的作用是利用系统内的多个 CPU 来并行执行用户进程，以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性
系统的多个处理器在物理上处于同一机壳中，有一个单一的系统物理地址空间，多个处理器共享系统内存、外设等资源
多 CPU 系统的类型主要有两种：
- 主 - 从模式，只有一个主处理器，运行操作系统，管理整个系统资源，并负责为各从处理器分配任务，从处理器有多个，执行预先规定的任务及由主处理器分配的任务。这种类型的系统无法做到负载平衡，可靠性不高，很少使用。
- 对称处理器模式 SMP（Symmetric MultiProcessor），所有处理器都是相同的、平等的，共享一个操作系统，每个处理器都可以运行操作系统代码，管理系统资源。是目前比较常见的多 CPU 系统类型。
多处理器系统中，比较有代表性的进（线）程调度方式有以下几种方式：
- 自调度
  - 设置一个公共的进程或线程的就绪队列
  - 不会出现处理器空闲
  - 处理器互斥访问该队列，容易形成系统瓶颈
  - 高速缓存的使用效率很低
  - 协作线程很难同时运行
- 组调度 / 群调度（Gang Scheduling）
- 专用处理器分配
- 动态调度
  - 操作系统和进程共同进行调度

# 多核 CPU 中的调度

多核处理器是指在一枚处理器中集成两个或多个计算引擎（内核 /core），称为 CMP（Chip multiprocessors）结构，可在特定的时钟周期内执行更多任务，通常采用共享二级 Cache 的结构
对于多核 CPU，优化操作系统任务调度算法是保证效率的关键
- 全局队列调度（多数系统）
- 局部队列调度
中断处理 —— 全局中断控制器也需要封装在芯片内部
系统提供同步与互斥机制 —— 需要利用硬件提供的 “读－修改－写” 的原子操作或其他同步互斥机制

# 死锁 😎

一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，则称一组进程或系统此时发生了死锁
死锁一旦发生，会使整个系统瘫痪而无法工作。因此，必须想办法解决死锁问题

# 死锁产生的原因

并发进程对临界资源的竞争
并发进程推进顺序不当

# 死锁产生的必要条件 😎

互斥条件（Mutual exclusion）：资源的使用是互斥的
请求与保持条件（Hold and wait）：已经得到某些资源的进程可以再申请新的资源。
不剥夺条件（No pre-emption）：系统或其它进程不能剥夺进程已经获得的资源。
环路等待条件（Circular wait）：系统中若干进程间形成等待环路
只要破坏上述几个条件之一，即可防止死锁
- 破坏第 1 个条件，使资源可同时访问而不是互斥使用，可行性较差
- 破坏第 2 个条件，进程必须获得所需的所有资源才能运行 —— 静态分配，严重降低资源利用效率。
- 破坏第 3 个条件，采用剥夺式调度方法，只适用于 CPU 和内存分配
- 破坏条件 4，采用层次分配策略 —— 按此策略分配资源时系统不会发生死锁
- 资源按序分配策略：进程不得在占用资源 $r_j(1≤j≤m)$ 后再申请 $r_i(i<j)$
进程 - 资源分配图
- 圆圈表示进程，资源类用方框表示，框中的圆点代表单个该类资源，有向边连接进程和资源
- 申请边从进程指向资源类方框，表示进程正在等待资源；分配边从单个资源圆点指向进程，表示进程已经获得资源
根据进程 - 资源分配图定义个得出如下结论：
- 如果进程 - 资源分配图中无环路，则此时系统没有发生死锁
- 如果进程 - 资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程
- 如果进程 - 资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件
进程 - 资源分配图可用以下步骤化简：
- 在资源分配图中，找出一个既非等待又非孤立的进程结点 $P_i$ ，由于 $P_i$ 可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去 $P_i$ 所有的申请边和分配边，使之成为既无申请边又无分配边的孤立结点；
- 将 $P_i$ 所释放的资源分配给申请它们的进程，即在资源分配图中将这些进程对资源的申请边改为分配边；
- 重复前两步骤，直到找不到符合条件的进程结点。
经过化简后，若能消去资源分配图中的所有边，使所有进程都成为孤立结点，则称该图是可完全化简的，否则为不可化简的
系统为死锁状态的充分条件是：当且仅当该状态的进程 - 资源分配图是不可完全简化的 —— 死锁定理。

# 死锁的避免 😎

死锁避免法是通过资源分配算法分析系统是否存在一个并发进程的状态序列，在确定不会进程循环等待的情况下，才将资源真正分配给进程，以保证并发进程不会产生死锁。
死锁避免法能支持更高的进程并发度，动态地决定是否给进程分配资源 —— 如果进程的资源请求方案会导致死锁，系统拒绝执行，反之，如果一个资源的分配会导致死锁，系统拒绝分配。

# 银行家调度算法 😎

Dijkstra 在 1965 年提出了避免死锁的银行家调度算法，该算法是以银行系统所采用的借贷策略（尽可能放贷、尽快回收资金）为基础而建立的算法模型。在此模型中，进程相当于贷款客户，系统资源相当于资金，调度程序相当于银行家（贷款经理）。
进程约束条件：
- 进程必须事先声明其资源需求
- 进程每次提出部分资源申请并获得分配
- 进程获得所需资源，执行完毕后，必须及时归还所占资源
系统约束条件：
- 若进程所请求得最大资源数不超过系统所有的资源总数，则系统一定分配资源给进程；
- 系统保证在有限的时间内使资源不足而等待的进程获得资源
思路
- 在某一时刻，各进程已获得所需的部分资源。有一进程提出新的资源请求，系统将剩余资源试探性地分配给该进程。
- 如果此时剩余资源能够满足余下的某些进程的需求，则将剩余资源分配给能充分满足的、资源需求缺口最大的进程，运行结束后释放的资源再并入系统的剩余资源集合。
- 反复执行第 2 步，直到所有的进程都能够获得所需而运行结束。说明第 1 步的进程请求是可行的，系统处于安全状态，相应的进程执行序列称为系统的安全序列。
- 如果所有的进程都试探过而不能将资源分配给进程，即不存在安全序列，则系统是不安全的。
银行家算法所需的数据结构：假设系统中有 n 个进程，m 类资源；
- 系统当前资源剩余量向量 Available[m] = { R1，R2，……，Rm } ；
- n 个进程对 m 类资源的需求声明矩阵 Claim[n][m] ， Claim[i][j] 的值表示进程 i 对 j 类资源的总需求量；
- n 个进程已获得的各类资源数量矩阵 Possession[n][m] ， Possession[i][j] 的值 k 表示进程 i 已获得 k 个 j 类资源；
- n 个进程的各类资源需求缺口矩阵 Shortage[n][m] = Claim – Possession ， Shortage[i][j] 的值 s 表示进程 i 还需要（缺） s 个 j 类资源；
- 某进程 i 在某时刻发出的资源请求向量 Request[m] ，取值随具体情况而定。

前 4 个数据结构及其取值确定了系统在某一时刻的状态，如果算法尝试资源分配方案能够使得所有进程安全运行完毕，则说明该状态安全，资源分配方案可行。

银行家算法细化说明
- 判断请求向量 Request 的有效性 —— 超过相应进程总需求量则报错，超过系统目前剩余量则阻塞；
- 就系统资源剩余量对 Request 进行试分配：
  Available[*] = Available[*] - Request[*] ；
  Possession[i][*] = Possession[i][*] + Request[*] ；
  Shortage[i][*] = Shortage[i][*] - Request[*] ；
- 执行安全性测试算法，若安全则确认试分配方案，否则进程 i 阻塞；
执行安全性测试算法细化说明：
- 定义工作向量 Rest[*] = Available[*] ，进程集合 Running{*} ，布尔量 possible = true ；
- 从 Running 集合中找出 Pk ，满足条件 Shortage[k][*] < Rest[*] ；
- 找到合格的进程 Pk ，则释放其占用资源（ Rest[*] = Rest[*] + Possession[k][*] ），将其从 Running 集合中去掉，重复步骤②；
- 找不到合格的进程 Pk ， possible 为 false ，退出安全性测试算法；
- 最终检查 Running 集合，为空则返回安全，非空则不安全。
银行家算法是一个很经典的死锁避免算法，理论性很强，看起来似乎很完美，但其实现要求进程不相关，并且事先要知道进程总数和各进程所需资源情况，所以可行性并不高。

# 检测与解除

死锁的检测算法可以采用基于死锁定理的检测（进程 - 资源分配图化简），也可以采用类似于银行家算法中的安全性测试算法，如果算法退出时仍有未结束的进程，则系统不安全，那些未结束的进程就是死锁的进程。
只不过死锁检测的不是试分配之后的系统状态，而是系统当前状态，需要考虑检查每个进程还需要的资源能否满足要求。
在系统中，需要决定死锁检测的频率。如果检测太频繁，会花大量的时间检测死锁，浪费 CPU 的处理时间；如果检测的频率太低，死锁进程和系统资源被锁定的时间过长，资源浪费大。
通常的方法是在 CPU 的使用率下降到一定的阈值时实施检测。当死锁发生次数多，死锁进程数增加到一定程度时，CPU 的处理任务减少，CPU 空闲时间增多。
在系统成功地检测到死锁后，常用的死锁解除方法有以下几种：
- 重启：重新启动死锁进程，甚至重启操作系统。
- 撤销：撤销死锁进程，回收资源，优先选择占用资源最多或者撤销代价最小的，撤销一个不行就继续选择撤销进程，直至解除死锁。
- 剥夺：剥夺死锁进程资源再分配，选择原则同上。
- 回滚：根据系统保存的检查点，使进程或系统回退到死锁前的状态。

# 线程的基本概念

# 线程的引入

在操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统并发粒度更小、并发性更好。
线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位
线程是进程的组成部分，线程只拥有一些在运行中必不可少的资源（如程序计数器、一组寄存器和栈），与同属一个进程的其它线程共享进程所拥有的全部资源
多个线程间可并发执行
不同进程间的线程互不可见，同一进程内的线程间通信主要基于全局变量

# 线程与进程的区别与联系

线程具有许多传统进程所具有的特征，故又称为轻型进程 (Light-Weight Process) 或进程元；而把传统的进程称为重型进程 (Heavy-Weight Process)，它相当于只有一个线程的任务。
在引入了线程的操作系统中，通常一个进程都有若干个线程，至少需要有一个主线程。
进程的再定义：进程是操作系统中进行除处理器外的资源分配和保护的基本单位，它有一个独立的虚拟地址空间，用来容纳进程映像 (如与进程关联的程序与数据)，并以进程为单位对各种资源实施保护，如受保护地访问处理器、文件、外部设备及其它进程 (进程间通信)
线程与进程在调度、并发性、系统开销、拥有资源等方面有所区别
在传统的操作系统中，拥有资源的基本单位和独立调度的基本单位都是进程。而在引入线程的操作系统中，则把线程作为 CPU 调度和分配的基本单位，而把进程作为拥有资源的基本单位，使传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。
在同一进程中，线程的切换不会引起进程的切换，在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
不论是传统的操作系统，还是支持线程的操作系统，进程都是拥有资源的独立单位，拥有自己的资源。
一般地说，线程自己不拥有系统资源 (只有一些必不可少的资源)，但可以访问、共享其隶属进程的资源 —— 进程的代码段、数据段以及打开的文件、I/O 设备等。
在进行进程切换时，涉及到当前进程整个 CPU 环境的保存以及新被调度运行的进程的 CPU 环境的设置。
而线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销

# 线程的三种模式

在操作系统内核实现的内核级线程（Kernel Level Thread，KLT），如 Windows，OS/2 等：线程管理的全部工作由操作系统内核在内核空间实现。系统为应用开发使用内核级线程提供了 API，除了 API 函数调用外，应用程序不需要编写任何线程管理的其它代码，通过调用 API 函数，实现线程的创建和控制管理
在用户空间实现的用户级线程（User Level Thread，ULT），如 Java 的线程库等：线程管理的全部工作由应用程序在用户空间实现，内核不知道线程的存在。用户级线程由用户空间运行的用户级线程库实现，应用开发通过线程库进行程序设计，用户级线程库是线程运行的支撑环境
同时支持两种线程的混合式线程实现，如 Solaris 系统。设计恰当的话，混合式线程既可以具备内核级线程实现的优点，又可以具备用户级线程实现的优点。用户级线程与内核级线程之间的关系可以有三种模型表示：一对一模型、多对一模型、多对多模型

# 管程的基本概念

管程是一种比信号量机制更先进的进程同步机制
基本思想：把分散在各进程中的控制和管理临界资源的临界区集中起来统一管理
实质上是把临界区集中并封装成抽象数据类型，其中包括与临界资源相关、仅限管程内部访问的公共变量，供管程外的进程调用以访问这些公共变量的接口过程，并提供互斥机制确保进程互斥地使用管程
管程具有以下特点：
- 模块化 —— 管程是一个基本程序单位，其中不仅有数据，还有对数据的操作；
- 隐蔽性 —— 管程内与临界资源相关的数据相当于是管程的私有成员，仅限管程内部访问，通过管程申请使用该资源的进程无法直接访问，只能调用管程提供的接口过程；
- 互斥性 —— 任一时刻只能有一个进程真正进入管程内部使用相应系统资源，其它进程必须等待，直至管程再次可用
管程采用条件变量（condition variable）实现同步机制：
- 让进入管程却因资源不足而阻塞的进程暂时放弃管程控制权（开放管程），进入该条件变量的等待队列
- 条件变量只能在管程中通过两个原语操作 —— wait 原语和 signal 原语
- 一个进程已进入管程但无法继续执行，便在相应的条件变量 x 上调用 x.wait() ，将自己阻塞并移入 x 的等待队列中，放弃管程控制权（开放管程），另一进程可以通过对同一个条件变量执行 x.signal() 来唤醒之前在 x 上等待的进程
- 条件变量仅起到维护等待队列的作用，不存在相关的值，也不能像信号量那样加减累计
管程与进程的区别：
- 管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；
- 管程是为管理共享资源而建立的，进程主要是为实现系统并发性而引入的；
- 管程被进程调用，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；
- 管程是语言或操作系统的组成部分，不必创建或撤销，而进程有生命周期
阻塞进程被另一进程以 signal 原语唤醒时的管程互斥协调方法：
- 执行 signal 的进程等待，直到被释放的进程退出管程或因等待另一个条件而阻塞
- 被释放进程等待，直到执行 signal 的进程退出管程或因等待另一个条件而阻塞
Hoare 采用了第一种办法，Hansen 选择了两者的折衷，规定 signal 原语必须位于管程过程的最后一步，于是当一个进程调用管程过程时执行了 signal 原语，也就意味着该进程立即退出管程
Hoare 方法使用信号量和 P、V 操作来实现对管程中过程的互斥调用，从而实现对共享资源互斥使用。
Hoare 管程的基本思路为：
- 管程中设一互斥信号量 mutex (初值为 1)，用于进程互斥调用管程内部过程
- 设置信号量 urgent （初值为 0）和计数器 urgent_count （初值为 0）
- 设置信号量 x （初值为 0）用于阻塞等待资源的进程及相应的计数器 x_count （初值为 0）
在管程的实现中，将上述 1、2 两条所引入的量封装在一个结构中，称为 InterfaceModule 。
Hoare 管程实现的主要代码：

	typedef struct InterfaceModule{
	semaphore mutex = 1;// 进程调用管程过程前使用的互斥信号量
	semaphore urgent = 0;// 发出 signal 的进程挂起自己的信号量
	int urgent_count = 0 ;// 在 urgent 上等待的进程数
	};
	InterfaceModule IM;
	semaphore x;
	int x_count,
	void enter(){
	P(IM.mutex);
	}
	void leave(){
	if (IM.urgent _count > 0) // 是否存在因执行 signal 而阻塞在 urgent 上的进程
	V(IM.urgent);// 有的话先唤醒一个阻塞在 urgent 上的进程
	else V(IM.mutex); // 没有的话直接开放管程
	}
	void wait (){
	x_count++;
	if (IM. urgent_count > 0) V(IM.urgent);
	else V(IM.urgent);
	P(x);
	x_count--;
	}
	void signal(){
	if (x_count > 0){
	IM.urgent_count++;V(x);
	P(IM.urgent);IM.urgent_count--;
	}
	}

# 进程同步的几个经典问题，用管程来解决

# 管程解决生产者 - 消费者问题

采用 Hoare 管程实现，继承 Monitor 中原有的定义（如 wait 、 signal 等），自定义可供生产者、消费者进程调用的接口 put 和 get 过程。
由于管程本身具备互斥机制，所以代码中没有针对多个生产者、消费者竞争使用缓冲区的信号量及操作，直接使用管程中的 enter 和 leave 。

	Monitor p_c_mon{
	item B[k];// 缓冲区，长度 k
	condition empty, full;// 缓冲区空满对应的条件变量
	int in, out, count; // 缓冲区存取位置，内容产品数
	void put(item px){
	if ( count >= k ) empty.wait(); // 缓冲区已满，在 empty 上阻塞调用 put 的进程
	B[in] = px; in =(in + 1) % k;count++;
	if (full.queue) full.signal();
	}
	void get(item & gx){
	if ( count <= 0 ) full.wait();
	gx = B[out]; out = (out + 1) % k; count--;
	if (empty.queue) empty.signal( );
	}
	void init(){ in = out = count = 0;}
	void enter() {………}
	void leave() {………}
	}
	cobegin
	process producer_i () {
	while(true) {
	生产一个产品x
	p_c_mon.enter();
	p_c_mon.put(x);
	p_c_mon.leave();
	}
	}
	process consumer_j () {
	while(true) {
	p_c_mon.enter();
	p_c_mon.get(x);
	p_c_mon.leave();
	消费 x;
	}
	}
	coend

# 管程解决哲学家就餐问题的算法

采用 Hoare 管程实现，算法思想是将哲学家的状态分为思考、饥饿、吃面，并且仅当哲学家左右两边的筷子都可用才允许他拿筷子，否则一只筷子也不拿。

	Monitor phil_mac_mon{
	enum { thinking, hungry, eating } state[5];
	semaphore self[5];
	int self_count[5];
	InterfaceModule IM;
	for (int i = 0; i < 5; i++) {
	state[i] = thinking;
	self_count[i] = 0;
	}
	void test(int k) {
	if ((state[(k - 1) % 5] != eating) && (state[k] == hungry) &&(state[(k + 1) % 5] != eating)){
	state[k] = eating;
	signal();
	}
	}
	void pickup(int i) {
	enter(IM);
	state[i] = hungry;
	test(i);
	if(state[i] != eating) wait();
	leave(IM);
	}
	void putdown(int i) {
	enter(IM);
	state[i] = thinking;
	test((i - 1) % 5);
	test((i + 1) % 5);
	leave(IM);
	}
	}
	cobegin
	process philmac_i() {
	while (true) {
	think();
	phil_mac_mon.pickup(i);
	eat();
	phil_mac_mon.putdown(i);
	}
	}
	coend

# 内存管理

# 内存管理概述

# 计算机存储系统的组成

内存储器（Memory），是处理器能直接寻址的存储空间，由半导体器件制成，用来存放处理器执行时所需要的程序和数据，以及与硬盘等外部存储器交换的数据，程序和数据只有在内存中才能被处理器直接访问。
外存储器也叫辅助存储器，用来存放需要长期保存的数据，外存储器的管理属于文件系统的范畴。
内存储器分两部分：
- 一部分是系统区，用来存放操作系统以及一些标准子程序、例行程序等，这些是长驻内存的部分，系统区用户不能使用；
- 另一部分称为用户区，分配给用户使用，用来存放用户的程序和数据等。内存管理的主要工作就是对内存储器中的用户区进行管理。

# 内存管理的功能

内存的分配和回收：操作系统根据用户程序的请求，在内存中按照一定算法把找到一块空闲，将其分配给申请者；并负责把释放的内存空间收回，使之变为空闲区。
实现地址转换：用户程序中使用逻辑地址，而 CPU 访问内存时则按物理地址进行，内存管理必须进行地址转换工作，把逻辑地址转换成物理内存中与之对应的物理地址，这种地址转换工作也称为地址重定位。
内存的共享和保护：内存中不仅有系统程序，还有多个用户程序，为了防止各用户程序相互干扰和保护各用户区的信息不受破坏，系统必须负责隔离分配给各用户的内存区，保证各个用户程序或进程在各自规定的存储区域内操作，不破坏操作系统区的信息，并且互不干扰。
内存扩充：内存管理允许通过虚拟存储技术 “扩充” 内存容量。在计算机软、硬件系统的支持下，可以把磁盘等辅助存储器作为内存的扩充部分使用，使用户程序在所需内存在比实际物理内存容量大的情况下，也能在内存中运行。

# 计算机存储系统的结构

# 处理器寄存器和高速缓存

处理器寄存器主要包括通用寄存器、指令寄存器、地址寄存器和数据缓冲寄存器等一系列寄存器，用于存储器中与控制流和数据流相关的信息。它容量小处，速度快，一般以字（word）为单位。一个计算机系统一般包括几十个甚至上百个寄存器。
高速缓存（Cache）是为了解决处理器与内存之间速度不匹配而引入的。其存储容量比处理器寄存器大，访问速度比寄存器慢，但远比内存快。
当处理器要读取数据时，首先访问高速缓存，如果所要访问的数据已经在高速缓存中，则直接从高速缓存中读取信息；如果要访问的数据不在高速缓存中，那就需要从内存中读取信息。随着硬件技术的发展，现在已经将高速缓存封装在处理器芯片中，所以常将高速缓存与处理器寄存器归到一个层次。

# 内存储器

内存储器也称为内存，属于主机范畴。内存中存储处理器执行时所需要的代码和数据。内存的空间远大于高速缓存，但内存中的数据断电即消失，无法永久储存。一个计算机系统中所配备的内存容量是衡量计算机性能的一个重要的指标，计算机最大内存容量受到计算机系统结构的限制。

# 外存储器

外存储器是计算机系统中最大规模的存储器，用来存储各种数据和软件。外存储器容量巨大并能够永久存储信息，断电后数据不会丢失，外存储器的价格低但是访问速度慢。外存储器包括各种磁盘、磁带、光盘以及其他移动存储设备。磁盘中的硬盘是计算机系统中大量联机信息的保存者，硬盘常常作为内存的补充，用来实现虚拟存储系统。

# 地址的表示与地址转换 😎

# 物理地址空间

当程序运行时，它将被装入内存中的某段空间内，此时程序和数据的实际地址不可能同原来的逻辑地址一致，程序在物理内存中的实际存储单元称为物理地址，也叫绝对地址，物理地址的总体就构成了用户程序实际运行的物理地址空间。不同程序的物理地址空间绝对不能冲突。
在以下章节中，如无特别说明，地址编址和地址长度的单位都是字节（Byte）。

# 逻辑地址空间

高级语言编写的源程序通过编译或汇编后得到目标程序。目标程序使用的地址称为逻辑地址，也叫相对地址，一个用户作业的目标程序的逻辑地址集合称为该作业的逻辑地址空间。作业的逻辑地址空间可以是一维的，这时逻辑地址限制在从 0 开始顺序排列的地址空间内；也可以是二维的，这时整个用户作业被分为若干段，每段有不同的段号，段内地址从 0 开始。

# 地址转换

只有把程序和数据的逻辑地址转换为物理地址，程序才能正确运行，该过程称为地址转换或地址重定位。地址转换有静态重定位和动态重定位两种方式。

# 静态重定位

这种方式是在用户作业装入内存时由装入程序 (装配程序) 实现从逻辑地址到物理地址的转换，地址转换在作业执行前一次完成
静态重定位方式的优点是实现简单，从逻辑地址到物理地址变换不需要专门的硬件便能完成；缺点是必须为程序分配一段连续的存储空间，并且程序在执行过程中不能在内存中移动。

# 动态重定位

在程序执行过程中，CPU 在访问程序和数据之前才实现从逻辑地址到物理地址的转换，称为动态重定位。动态重定位必须借助于硬件地址转换机构来实现。硬件系统中设置了一个定位寄存器，当操作系统为某程序分配了一块内存区域后，装入程序直接把用户程序装入到所分配的区域中，然后把该内存区域的起始地址置入定位寄存器中。在程序执行过程中随着每条指令或数据的访问，需要进行地址转换时，只需将逻辑地址与定位寄存器中的值相加就可得到物理地址。这种地址转换方式是在程序执行过程中动态进行的，所以称动态重定位。
采用动态重定位时，由于装入内存的用户程序仍保持逻辑地址，所以可以实现程序在内存中的移动。在程序执行过程中，若把程序移动到另一块内存区域后，只要改变定位寄存器中的内容，该程序仍可正确执行。但采用静态定位时，程序在执行过程中是不能移动的。
动态重定位的优点是内存的使用更加灵活，容易实现内存的动态扩充和共享；缺点是实现过程中需要附加硬件支持，内存的管理也更加复杂。

# 覆盖与交换技术

# 覆盖技术

一个程序通常由若干个功能上独立的程序段组成，在运行时，并不是所有的程序段都同时进入内存执行。这样，我们就可以按照程序自身的逻辑结构，让不同时执行的程序段先后共享同一块内存区域，这就是覆盖技术。
覆盖技术先将程序必需的部分代码和数据调入内存，其余部分先放在外存中，当要访问的程序或数据不在内存时，由操作系统负责将其从外存中调入，这就解决了在较小的内存空间中运行较大程序的问题。
覆盖技术首先将大的用户程序划分为一个个相对独立的程序单位，将程序执行时不需要同时装入内存的程序单位组成一个个覆盖段，每个覆盖段的长度不能超过已有内存空间大小。各个覆盖段分先后顺序进入到所分配的内存空间中，后进入内存的覆盖段将先进入的段覆盖。
覆盖技术的缺点：
- 覆盖技术对用户不透明，用户在编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加了编程复杂度。
- 从外存装入覆盖文件，是以时间的延长来换取空间的节省。

# 交换技术

为了释放部分内存空间，由操作系统根据需要，将某些暂时不运行的进程或程序段从内存移到外存的交换区中；当内存空间富余时再给被移出的进程或程序段重新分配内存，让其进入内存，这就是交换技术，又称为 “对换” 或 “滚进 / 滚出 (roll-in/roll-out)。
交换技术能够提高系统的性能和多道度，从内存到外存的交换为换出，从外存到内存的交换为换入。通过不断的换入、换出，使得用户看来好像内存扩大了，从而实现了内存扩充的目的。
根据每次交换的单位不同，交换技术在实现中有种情况：
- 以整个进程为单位的交换：每次换入或换出的是一个进程，此策略多用于早期的分时系统中，以实现在小型机上的分时运行。
- 以进程的一部分为单位的交换：在现代操作系统中，借助于页式或段式内存管理，先将进程的内存空间划分为若干页面或段，然后以页面或段为基本单位进行交换。在操作系统中，常见的有页面置换（在页式存储管理中介绍）和段置换（在段式存储管理中介绍），这也是虚拟存储技术的基础。

# 覆盖技术和交换技术的比较

与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。
交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。
覆盖只能覆盖那些与覆盖段无关的程序段。

# 分区内存管理

# 单一连续内存管理

# 单一连续内存管理基本思想

单一连续内存管理适用于单用户单任务操作系统，是最简单的内存管理方式。单一连续内存管理将内存空间分为系统区和用户区，系统区存放操作系统常驻内存的代码和数据，用户区全部分配给一个用户作业使用。在这种方式下，在任一时刻主存储器最多只有一道程序，各个作业只能按次序一个一个地装入主存储器运行。
通常，系统区位于内存底部的低地址部分，用户区位于内存顶部的高地址部分。

# 单一连续内存管理内存的分配与回收

由于内存中的用户区只能装入一个程序运行，所以该程序被装入内存时，就从内存用户区的基地址开始，连续存放。在运行过程中，该程序独占内存，直到退出，操作系统收回内存再分配给下一个程序使用

# 单一连续内存管理地址转换与内存保护

单一连续内存管理多采用静态重定位来进行地址转换。操作系统设置一个界限寄存器用来设置内存中系统区和用户区的地址界限；通过装入程序把目标模块装入到从界限地址开始的区域
内存保护由装入程序来执行，装入时由装入程序检查物理地址是否超过界限地址，超过则可以装入；否则产生地址错误，不能装入。这样，用户的程序总是被装入到合法的用户区域内，而不会进入系统区。
采用静态重定位的优点是实现简单，无需硬件地址变换机构支持。缺点是作业只能分配到一个连续存储区域中，程序执行期间不能在内存中移动，无法实现程序共享。
单一连续内存管理也可以采用动态重定位方式来转换地址。系统设置一个定位寄存器，它既用来指出内存中的系统区和用户区的地址界限，又作为用户区的基地址；装入程序把程序装入到从界限地址开始的区域，但不同时进行地址转换；而是在程序执行过程中动态地将逻辑地址与定位寄存器中的值相加就可得到绝对地址

# 单一连续内存管理缺点

内存利用率低。用户程序所需空间一般均小于内存用户区空间，剩余的内存空间也不能被其它用户使用。
CPU 利用率低。当运行中的程序进行 I/O 操作时，CPU 会处于空闲等待状态。
外设利用率低。用户控制所有资源，有些资源在运行期间可能并不使用，也不能为其它用户使用。
不能进行内存扩充。当内存容量小于某一程序所需要的内存空间时，该程序便无法运行。

# 固定分区内存管理

# 固定分区内存管理基本思想

固定分区内存管理是预先把可分配的内存空间分割成若干个大小固定的连续区域，每个区域的大小可以相同，也可以不同，每个区域称为一个分区。每个分区可以装入且只能装入一个用户作业。这样，分区后的内存中就可以装入多道程序，从而支持多道程序并发设计。

# 固定分区内存管理分区的划分

分区大小相等
- 所有分区的大小都相等，这种方式适合计算机工业控制系统。因为在计算机工业控制系统中，所有控制对象都具有相同的条件，完成相同的控制任务和控制指标。
- 该方式的缺点是：因为分区大小都一样，所以较小的进程装在分区里会浪费内存，而较大的进程则无法装入内存运行。
分区大小不等
- 把可分配的内存空间分割为大小不等的多个分区，大的分区可以分配给大的进程，小的分区可以分配给小的进程。与分区大小相等分配方式比较，分区大小不等的分配方式使得内存的分配更加灵活，内存的浪费更少。

# 固定分区的内存分配

为了说明各分区的分配和使用情况，系统设置一张 “内存分配表”
内存分配表指出了各分区的起始地址和分区的长度，占用标志位指示该分区是否被使用，当占用的标志位为 “0” 时，表示该分区尚未被占用。
只能将那些占用标志为 “0” 的分区分配给用户作业使用，当某一分区被分配给一个作业后，就在占用标志栏填上占用该分区的作业名

# 固定分区的地址转换与内存保护

静态重定位：装入程序在进行地址转换时检查其绝对地址是否在指定的分区中，若是，则可把程序装入，否则不能装入。固定分区方式的内存回收很简单，只需 ** 将内存分配表中相应分区的占用标志位置成 “0”** 即可。
动态重定位：计算机系统设置了一对地址寄存器 —— 上限 / 下限寄存器；当一个进程占有 CPU 执行时，操作系统就从内存分配表中取出相应的地址放进上限 / 下限寄存器；硬件的地址转换机构根据下限寄存器中保存的基地址 B1 与逻辑地址相加就得到绝对地址；硬件的地址转换机构同时把绝对地址和上限 / 下限寄存器中保存的地址进行比较，就可以实现存储保护。

# 固定分区分配的优点和缺点

固定分区的划分在操作系统初始化时完成。在系统启动时，系统管理员根据系统要运行的作业的需要来划分分区。当用户作业进入分区时，按照用户作业的大小从分区表中选择适当的空闲分区。
优点：
- 与单一连续分配方式比较，固定分区分配方式使得系统资源的利用率和吞吐量有一定的提高。
缺点：
- 内存空间的利用率不高
- 由于每个分区大小固定，这样就限制了可容纳的程序的大小。在装入一个程序时，若找不到足够大的分区，则无法装入。

# 可变分区内存管理

# 可变分区内存管理基本思想

事先不确定分区的大小，也不确定分区的数目。当某一用户作业申请内存时，检查内存中是否有一块能满足该作业的连续存储空间，若有就把这一空间划出一块区域给该用户使用，这种方式就称作可变分区内存管理。
分区的大小是按作业的实际需要量来定的，分区的个数也是随机的，所以可变分区内存分配可以克服固定分区方式中的内存的浪费现象。
可变分区克服了固定分区内存利用率低的问题，更适合多道程序环境。
操作系统也可以通过链表方式来管理空闲分区，将所有的空闲分区通过前向和后向指针串在一起组成双向空闲分区链
空闲区链表管理比空闲区表格管理较为复杂但其优点是链表自身不占用存储单元。为了方便检索空闲分区链，每个空闲分区的首部还设置有分区状态和分区大小标志，这样，系统查找分区链时可直接得知分区的大小和分配情况，省去了查询空闲分区表的时间。
不论是空闲区链表管理还是空闲区表格管理，链和表中的空闲区都可按一定规则排列，例如，按空闲区从大到小排列或从小到大排列，以方便空闲区的查找和回收。

# 可变分区的内存分配算法

# 最先适应分配算法

每次分配时，总是从头顺序查找未分配区表或空闲区链表，将找到的第一个能满足长度要求的空闲区分配给用户作业使用。从该空闲分区中分割一部分给作业，另一部分仍作为空闲分区；如果空闲分区全部查找完也不能满足该作业要求，则系统不能为该作业分配内存。
首先利用内存中的低地址空闲分区，保留了大的高地址空闲分区，以便能容纳大的用户作业。
缺点：每次都是从未分配分区表或空闲区链表的开始查找空闲分区，低地址段的空闲分区被不断分割，形成了许多小的、难以利用的空闲分区，称为 “碎片”；同时每次都从开始查找，花费时间较长。

# 循环首次适应分配算法

循环首次适应法是对最先适应法的改进。为作业分配内存时，系统不是从空闲分区表的开始处开始查找，而是从上次为作业分配分区后的位置开始查找，找到第一个满足作业大小的空闲分区，分配并分割该空闲分区。
该分区分配算法克服了首次适应算法的缺点，使得空闲分区的分布更加均匀，查找空闲分区所需要的时间更短。但是，小分区或 “碎片” 问题仍然不能解决。

# 最优适应分配算法

从空闲区中挑选一个能满足作业要求的最小分区，这样可以避免分割一个更大的区域，使大作业比较容易装入。
可把空闲区按长度递增排列，查找时总是从最小的一个区开始，直到找到一个满足要求的区为止。
收回一个分区时也必须对空闲区链重新排列。
最优适应分配算法找出的分区一般都是无法正好满足作业的内存要求，分割后剩下的空闲区很小，无法再次使用，成为 “碎片”。另外，这些小的空闲区占据了空闲区表的开始部分，增加了查找空闲区表或空闲区链的时间开销。

# 最坏适应分配算法

从空闲区中挑选一个最大的区给作业使用，这样可使分割后剩下的空闲区仍然比较大，仍然能满足以后的作业装入要求，也减少了内存中 “碎片” 的大小和个数。
可把空闲区按长度以递减顺序排列，查找时只要看第一个分区能否满足作业要求，若能满足，则分配给该作业使用。
最坏适应分配算法的查找效率很高，对中、小作业有利。
最坏适应分配算法缺点：随着系统的运行，大空闲区会不断减少，这样，大的作业可能会无法装入内存。

# 快速适应算法

把不同长度的空闲区归类，为每种长度的空闲区设立单独的空闲区链表。这样，系统中存在多个空闲分区链。
为作业分配内存时，根据作业大小查找空闲分区表，找到能够容纳它的最小的空闲分区链表的起始指针，然后再从相应的空闲分区链中取第一个空闲分区分配给该作业即可。
优点是查找空闲分区迅速，找到的空闲分区是能容纳它的最小空闲区，这样能够保留大的空闲分区。
缺点是回收分区较困难，算法复杂，系统开销大。

# 对比分析

从搜索空闲区速度及内存利用率来看，每种算法各有其优劣势。如果空闲区按从小到大排列，则最先适应分配算法等于最优适应分配算法。反之，如果空闲区按从大到小排列，则最先适用分配算法等于最坏适应分配算法。空闲区按从小到大排列时，最先适应分配算法能尽可能使用低地址区，从而，在高地址空间有较多较大的空闲区来容纳大的作业。循环首次适应分配算法会使存储器空间得到均衡使用。最优适应分配算法的内存利用率最好，因为，它把刚好或最接近申请要求的空闲区分给作业；但是它可能会导致空闲区分割下来的部分很小。

# 可变分区的地址转换与内存保护

可变分区内存管理是采用动态重定位方式来装入作业的，其地址转换由硬件机构完成。硬件设置了两个专门的寄存器：基址寄存器和限长寄存器。
基址寄存器存放分配给作业使用的分区的起始地址
限长寄存器存放该分区的存储空间的长度。
当用户作业占有 CPU 运行时，操作系统把分配给该作业的分区的起始地址和长度送入基址寄存器和限长寄存器，启动作业执行时由硬件根据基址寄存器进行地址转换得到绝对地址
当逻辑地址小于限长值时，则由逻辑地址加基址寄存器的值就可得到绝对地址；当逻辑地址大于限长值时，就表示作业欲访问的内存地址超出了所分得的内存区域，禁止访问该地址，起到了存储保护的目的。
在多道程序系统中，只需要一对基址 / 限长寄存器就足够了。因为当作业在执行过程中出现等待时，操作系统把基址 / 限长寄存器的内容随同该作业的其它信息，如 PSW，通用寄存器的内容等一起保存起来。当作业 - 被选中执行时，则把选中作业的基址 / 限长值再送入基址 / 限长寄存器。
世界上最早的巨型机 CDC6600 便采用这一方案
系统运行一段时间后，内存被多次分配和回收，会产生许多不连续的空闲空间。有可能出现这样的现象：内存中每一块空闲空间都不能满足某一作业的内存请求，而所有空闲空间的总和却能满足该作业。这时可采用紧凑技术把内存中的作业改变存放区域，使分散的空闲区能够汇聚成一个大的空闲区，从而有利于大作业的装入
紧凑技术可以汇聚内存中的空闲区，但也增加了系统的开销，而且不是任何时候都能对一道程序进行移动的。

# 页式内存管理 😎

# 页式内存管理基本思想

页：将用户进程的逻辑地址空间划分为大小相等的区，每一个区称为一页或一个页面，并对各页从 0 开始编号，如第 0 页、第 1 页等。
物理块：将物理内存也划分成与页大小相等的区，每一个区称为一个物理块 (block)，或称为块、页框，也同样对它们加以编号，如 0 号块、1 号块等。
物理块的尺寸大小通常会取 2 的幂次。物理块的大小由计算机硬件决定，页的大小由物理块的大小决定。如 Intel 80386 系列处理器系统和 Motorola 68030 处理器系统的块的大小为 4096B，IBM AS/400 的块的大小为 512B
内存分配的基本单位是页，当装入一个用户程序时，按页为单位，每一页装入一个物理块中，一个用户进程装入到内存中时各个物理块之间不需要连续。
进程的最后一页经常装不满一块，所以会在最后一块内形成不可利用的碎片，称之为 “页内碎片”。而其他页在装入内存时，都能填满所在的物理块。
逻辑地址形式：进程的逻辑地址可以用页号和页内偏移表示，页的大小与物理块的大小相等。
如果进程的逻辑地址是 A，页面大小是 L，则页号 P 和页内偏移 d 为： $P=INT[A/L]\ \ \ d = [A] \% L$

# 页式存储管理的内存的分配与回收

页式存储管理在进行内存分配时，以物理块为单位进行分配，一个作业有多少页，在装入内存时就必须给它分配多少个物理块。但是，和分区式内存管理不同的是分配给作业的物理块可以是不连续的。
在进行内存分配时，首先，操作系统为进入内存的每个用户作业建立一张页表，页表用来指出逻辑地址中的页号与内存中物理块号的对应关系。
同时，在页式存储管理系统中还存在一张作业表，作业表中的每个登记项登记了每个作业的页表始址和长度
页表的表项中除了有页号和块号外，还有存取控制字段，用于实现对内存物理块的保护。页表的长度由用户进程的长度决定，每个在内存中的用户进程都会建立一张页表。如果进程不处于运行状态，页表的起始地址和长度存放在进程的 PCB 中。
只有某一进程被调度运行时，系统才会从运行进程的 PCB 中将页表起始地址和长度装入页表寄存器。所以，一个处理器只需要一个页表寄存器。

# 页式存储管理的地址转换 😎

在页式存储管理中，进程的逻辑地址到物理地址的转换需要硬件来完成，该硬件为地址转换机构
当处理器要访问某逻辑地址时，地址转换机构自动从逻辑地址的低地址部分得到页内偏移，从高地址部分得到页号。
将页号与页表寄存器中的页表长度比较，如果页号大于或等于页表长度，表示该页在页表中没有相应项，本次所访问的地址已经超越进程的地址空间，则产生地址越界中断；否则，从页表寄存器得到页表在内存中的起始地址。用页号作为索引查找页表，得到页表项，从而可以查到该页在内存中的物理块号。
最后，将页内偏移装入物理地址寄存器的低位字段中，将物理块号装入物理地址寄存器的高位字段中，此时物理地址寄存器中的内容就是物理地址

# 快表 😎

由地址转换过程可见，处理器每运行一条指令总是先根据指令的逻辑地址，通过访问内存中的页表才能得到物理地址，根据物理地址再去访问内存才能得到需要的指令，即处理器需要两次访问内存。同样，处理器要访问一个数据也需要两次访问内存。
为了提高程序的运行速度，可以将最近访问过的页的页表项信息存放在高速缓存中，高速缓存也称为 “联想存储器”，其中的页表称为 “快表”。
计算机系统中通常都设置一个专用的高速缓冲存储器，用来存放页表的一部分，称为相联存储器（associative memory），存放在相联存储器中的页表称快表。
相联存储器的访问速度比内存快，但造价高，故一般都是小容量的，例如 8~16 个单元。高速缓冲存储器由半导体实现，其工作周期与 CPU 的工作周期接近，所以访问快表的速度远快于访问内存中页表的速度。
借助于快表，物理地址形成的过程是：
- 按逻辑地址中的页号查快表，若该页已登记在快表中，则由块号和块内偏移形成绝对地址；
- 若快表中查不到页号，则只能再查内存中的页表来形成绝对地址，同时将该页登记到快表中。
- 当快表填满后，又要在快表中登记新页时，则需在快表中按一定策略淘汰一个旧的登记项，最简单的策略是 “先进先出”，即总是淘汰最先登记的那一页。
多道程序中，当某道程序让出处理器时，应同时让出相联存储器。由于快表是动态变化的，所以让出相联存储器时应把快表保护好以便再执行时使用。当一道程序占用处理器时，除设置页表寄存器外还应将它的快表送入相联存储器中。

# 页的共享和保护

页式存储管理有利于实现多个作业共享程序和数据。在多道程序系统中，编译程序、编辑程序、解释程序、公共子程序、公用数据等都是可共享的，这些共享的信息在内存中只要保留一个副本。
在实现共享时，必须区分数据的共享和程序的共享。
实现数据共享时，可允许不同的作业对共享的数据页使用不同的页号，只要让各自页表中的有关表目指向共享的数据物理块。
实现程序共享时，由于页式存储的逻辑地址空间是连续的，所以程序运行前它们的页号应该是确定的。
实现信息共享必须解决信息的保护问题。常用的办法是在页表中增加一些标志位，用来指出该页的信息是：读 / 写；只读；只可执行；不可访问等，在指令执行时进行核对。

# 多级页表

为了快速查找页表页在内存中的物理块号，为这些页表页再设计一个地址索引表，即页目录表。页目录表的表项中包含每个页表页所在的内存物理块号和相关信息。
页表页中的每个表项记录了每个页的页号和对应的物理块号
二级页表的逻辑地址被划分为三部分：页目录、页表页、页内偏移
地址转换过程：
- 首先由页目录表寄存器提供当前运行进程的页目录表（一级页表）在内存中的起始地址；
- 由页目录表（一级页表）在内存中的起始地址加上页目录号（即需要查找的页表某页在页目录中的编号）, 得到页表某页的物理块号；
- 通过页表某页的物理块号得到该页表页（二级页表中的一页），由页表页号（某页在页表页中的编号）查询该页表页（二级页表中的一页）项，得到对应的物理块号；
- 最后将该物理块号加上页内偏移，最终得到物理地址
二级页表地址变换获取内存信息需要三次访问内存：第一次访问的是页目录表，第二次访问的是页表页，第三次访问通过物理地址获取内存信息。

# 段式存储管理

# 段式存储管理的基本原理

事实上，一个程序往往由一个程序段、若干子程序数组段和工作区段所组成，每个段都从 “0” 开始编址，段内地址是连续的。因此，可以按照程序的逻辑段结构，将一个程序按段为单位来分配内存，一段占用一块连续的内存地址空间，段与段之间不需要连续。
分段式存储管理是以段为单位进行内存分配，逻辑地址空间是一个二维空间，分为段号和段内偏移两部分
页式存储管理中，逻辑地址分页用户不可见，连续的逻辑地址空间根据内存物理块的大小自动分页。
段式存储管理中，由用户来决定逻辑地址如何分段。用户在编程时，每个段的最大长度受到地址结构的限制，每个程序中允许的最多段数也受限制。
分段存储管理中操作系统为每个作业创建一张段表，每个段在段表中占有一项。段表中有段号、段长、段在内存的起始地址和存取控制字段等信息。
段式存储管理系统还包括一张作业表，每个作业在作业表中有一个登记项。
在段式存储管理中，对内存的分配类似于可变分区内存分配方式，因此其内存分配算法可以参照可变分区内存分配算法来设计

# 段式存储管理的地址转换和内存保护

段地址转换借助于段表完成。段表寄存器用来存放当前占用处理器的作业的段表始址和长度，查询段表得到每段在内存的起始地址，将段的起始地址加上段内偏移则得到物理地址
段地址转换过程如下：
- 将 CPU 给出的逻辑地址由段号和段内地址（即段内偏移）构成；
- 查询段表寄存器得到段表在内存的起始地址；
- 将段号带入查询段表，得到该段在内存的起始地址和段长；
- 将段内地址与段长比较，如果段内地址大于段长，则发出越界中断；否则合法。段在内存的起始地址与段内地址相加，就为该逻辑地址对应的内存物理地址。
利用段表寄存器中的段表长度与逻辑地址中的段号比较，若段号超过段表长则产生越界中断，再利用段表项中的段长与逻辑地址中的段内偏移比较，检查是否产生越界中断。
对段的越权保护可通过在段表中增加相应的存取控制权限字段来实现。权限字段显示对段的读、写是否允许，用它来检查对该段内地址的访问操作是否合法。只有当每次操作都在合法的权限范围内，才能正常完成访问操作，否则出错。

# 段的共享

在段式存储管理中，所谓段的共享，事实上就是共享分区，为此计算机系统要提供多对基址 / 限长寄存器。这样，几个作业所共享的例行程序就可放在一个公共的分区中，只要让各道的共享部分有相同的基址 / 限长值。
由于段号仅仅用于段之间的相互访问，段内程序的执行和访问只使用段内地址，因此不会出现页共享时出现的问题，对数据段和代码段的共享都不要求段号相同。当然对共享区的信息必须进行保护，如规定只能读出不能写入，欲想往该区域写入信息时将遭到拒绝并产生中断

# 分段和分页的比较

段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，段长可根据用户需要来规定，段起始地址可以从任何地址开始。在分段方式中，源程序 (段号，段内偏移) 经连结装配后仍保持二维结构。
页是信息的物理单位，与源程序的逻辑结构无关，用户不可见，页长由系统确定，页面只能以页大小的整倍数地址开始。在分页方式中，源程序 (页号，页内偏移) 经连结装配后变成了一维结构。

# 段页式存储管理

页式存储基于存储器的物理结构，存储利用率高，便于管理，但难以实现存储共享、保护和动态扩充；段式存储基于应用程序的结构，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护，但往往会形成段之间的碎片，浪费存储空间。
可以把两者结合起来，在分段式存储管理的基础上实现分页式存储管理，这就是段页式存储管理。
段页式存储管理的基本原理：
- 程序根据自身的逻辑结构划分成若干段，这是段页式存储管理的段式特征。
- 内存的物理地址空间划分成大小相等的物理块，这是段页式存储管理的页式特征。
- 将每一段的线性地址空间划分成与物理块大小相等的页面，于是形成了段页式存储管理。
- 逻辑地址分 3 个部分：段号、段内页号和页内位移，对于用户来说，虚拟地址应该由段号 $s$ 和段内位移 $d'$ 组成，用户看不到如何分页。而是由操作系统自动把 $d'$ 解释成两部分：段内页号 $p$ 和页内位移 $d$ ，也就是说， $d'=p×块长+d$ 。
- 段页式存储管理的数据结构包括段表和页表，段表中包括段号、该段页表的起始地址、页表长度等信息，页表中包括页号、对应的物理块号等信息
- 段页式存储管理的动态地址转换机构由段表、页表和快表构成，操作系统把正在运行的作业的段表起始地址装入段表寄存器中，操作系统从逻辑地址中取出段号和段内页号，用段号作为索引查询快表中的段表，如果从快表得到页表起始地址和页表长度，再查询快表中的页表，从而得到所在页面对应的内存物理块号，将该物理块号与页内位移拼接，即为所需要的物理地址。如果不能从快表得到段和页的信息，则需要用段号作为索引查询内存中的段表，得到页表长度和页表的起始地址。再以页号作为索引查询页表，得到该页所对应的物理块号，同时将段表中的相应段信息和页表中的相应信息写入快表，并将物理块号与页内位移拼接，就可以得到物理地址。

# 虚拟存储技术

# 程序局部性原理

即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理表现在时间局部性和空间局部性两个方面。
时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。例如，很多程序中存在大量的循环、临时变量和子程序调用等。
空间局部性是指一旦程序访问了某个存储单元，则不久之后其附近的存储单元也将被访问。例如程序中对数组、链表或堆栈进行操作。
程序的局部性原理说明：程序的一次性装入内存与全部驻留内存都是不必要的。

# 虚拟存储技术的基本思想 😎

虚拟存储技术的思想：将外存作为内存的扩充，作业运行不需要将作业的全部信息放入内存，将暂时不运行的作业信息放在外存，通过内存与外存之间的对换，使系统逐步将作业信息放入内存，最终达到能够运行整个作业，从逻辑上扩充内存的目的。
虚拟存储器定义：虚拟存储器是指具有请求调入功能和置换功能，能够从逻辑上对内存空间进行扩展，允许用户的逻辑地址空间大于物理内存地址空间的存储器系统
虚拟存储器的容量由计算机的地址结构和辅助存储器的容量决定，与实际的主存储器的容量无关。
虚拟存储技术的实现基础是内存的分页或分段管理，采用的是进程的分页或分段在内存与外存之间对换
虚拟存储技术允许进程的逻辑地址空间比物理内存空间大，即小空间能够运行大程序，打破了程序运行受内存空间的约束，使操作系统不但能够接纳更大的作业，而且还能接纳更多的作业，提高了系统的多道度和性能。

# 请求分页虚拟存储管理

# 请求分页虚拟存储管理的基本原理

请求分页虚拟存储管理是在页式存储管理的基础上增加了请求调页和页面置换功能，其基本原理如下：
- 首先，物理的内存空间被划分为等长的物理块，并对块编号。同时，用户程序也进行分页，这些与页式存储管理相同。
- 在用户程序开始执行前，不将该程序的所有页都一次性装入内存，而是先放在外存。当程序被调度投入运行时，系统先将少数页装入内存，随着程序运行，如果所访问的页在内存中，则对其管理与分页存储管理情况相同。
- 若发现所要访问的数据或指令不在内存中，就会产生缺页中断，到外存寻找包含所需数据或指令的页，并将其装入到内存的空闲块中。
- 在装入一页的过程中，若发现内存无空闲块或分配给该进程的物理块已用完，则需要通过页面置换功能从已在内存的页中挑选一个将其淘汰，释放所占用的物理块后将新的页面装入该块，进程继续运行。
- 被淘汰的页面如果刚才被修改过，则还需要将其回写到外存，以保留其最新内容。

# 请求分页虚拟存储管理的硬件支持

# 请求分页的页表机制

在虚拟存储管理中，页表除了要完成从逻辑地址到物理地址的转换外，还需要提供页面置换的相关信息。因此，页表中除了有页号和物理块号等信息外，还增加了页的状态位、外存地址、修改位、访问字段等信息
状态位：用于标志一页是否已装入内存。如果该页已在内存，则该页所对应的状态位置 “1”；否则置 “0”。
外存地址：页在外存中的地址。当需要将某页调入内存时，需要查询页表中的外存地址项得到该页在外存的地址，在外存找到该页。
修改位：页在内存中是否被修改过的标志，用来确定如果该页被换出内存时，是否需要再回写入外存。如果该页在内存里没有被修改过，那么该页中的内容和在外存中的内容是一致的，则被换出内存时不需要再写入外存，节约了写入外存的时间。如果该页在内存中已经被修改过了，被换出内存时需要再写入外存。
访问字段：标志页在内存时是否被访问过。用于进行页面置换时考虑是否将该页换出内存。如果该页被访问过，在进行页面置换时，系统会考虑该页可能以后会被再次访问而不将其换出。

# 缺页中断机构

在进程运行过程中，当发现所访问的页不在内存时，缺页中断机构便产生一个缺页（Page fault）中断信号，操作系统接到此信号后，就运行缺页中断处理程序，将所需要的页调入内存。缺页中断与一般中断类似，都需要经历保护 CPU 环境、分析中断原因、转入中断程序处理、中断处理后恢复 CPU 环境等步骤。
但缺页中断与一般中断也有不同：
- CPU 检测中断的时间不同。对一般的中断信号，CPU 是在一条指令执行完后检测其是否存在，检测时间以一个指令周期为间隔。而对缺页中断信号，CPU 在一条指令执行期间，只要有中断信息就可检测，不需要等待一个指令周期。因此，CPU 检测缺页中断更及时。
- CPU 可以多次处理。如果在一个指令周期中多次检测到缺页中断，CPU 都会及时处理。
缺页中断处理流程：
- 先查看内存是否有空闲块，若有则按该页在外存中的地址将该页找出并装入内存，在页表中填上它占用的块号且修改标志位。
- 若内存已没有空闲块，则必须先淘汰已在内存中的某一页，再将所需的页装入，对页表和内存分配表作相应的修改。
淘汰某页时，要查看该页的修改位来判断该页是否修改过，若该页在执行过程中没有被修改过，那么不必重新写回到存储器中，而已修改过的页调出时必须再将该页写回到外存中。

# 地址转换机构

请求分页虚拟存储技术是在程序执行过程中逐步将程序页面调入内存的，所以从逻辑地址到物理地址的转换是在程序运行过程中完成的，是动态重定位装入
当进程被调度时，操作系统将进程 PCB 中的页表起始地址和长度装入页表寄存器中。
CPU 从逻辑地址中取得页号，根据页号查询快表，如果快表中有该页的内存块号，则将内存块号与页内偏移一起作为该页在内存的物理地址；如果快表中没有该页的内存块号，则 CPU 从页表寄存器得到页表在内存中的起始地址，查询页表，得到该页的内存块号，则将该块号与页内偏移一起作为该页在内存中的物理地址，同时将该页的页号和内存块号写入快表，以备下次查询时使用。
如果查询页表而没有得到该页的内存块号，即表示该页不在内存，产生一个缺页中断信号，请求操作系统将该页调入内存。
在调入一页的过程中，如果进程空间没有空余的物理块，则系统需要调出一页后再将该新页调入内存。同时系统修改页表，从页表中去除调出的页面，加上调入的页面。当这些工作完成后，处理器返回用户进程，继续执行被中断的指令。

# 页面分配策略与页面调度算法 😎

请求分页虚拟存储管理支持多个进程同时装入内存，操作系统为各个进程分别分配部分物理块，并将各自的部分页调入内存，在实施中涉及到以下三个策略：
- 页面分配策略：分配策略决定系统应该给一个进程分配多少物理块，进程才能运行。
- 页面调入策略：页面调入策略决定如何将进程所需要的页面调入到内存。
- 页面置换策略：页面置换策略决定内存中的哪些页面被换出内存。

# 页面分配策略

# 固定分配方式

为每个进程分配固定数量的物理块，其数量在进程创建时，由进程的类型（交互性、批处理或应用性）或根据用户的要求确定，在进程的整个运行期间都不再改变。
具体的分配方式包括按进程平均分配法、进程按比例分配法和进程优先权分配法等。
进程平均分配法：将内存中所有可分配的物理块平均分配给进入系统的各个进程。如果有 m 个内存物理块，n 个进程，则每个进程分得的内存物理块数为 m/n 取整数（小数部分不计）。
- 该分配方法实现简单，但没考虑各个进程大小不一，常常会造成内存的浪费。
- 该分配方式另一个特点：分配给每个进程的物理块数会随着内存中进程数的多少而变化。
进程按比例分配法：根据进程的大小，进程按照比例分配内存物理块数。如果系统中有 m 个内存物理块，n 个并发进程，每个进程的页面数为 S_i。则系统中每个进程能够分得的内存物理块数 b_i 为（b_i 取整）： $b_i=(mS_i)\div(\sum\limits_{i=1}^n S_i)$
进程优先权分配法：高优先级的、时间要求紧迫的进程，操作系统给其分配较多的内存物理块，使其能够快速完成。在实际应用中，将按比例分配法和进程优先级结合起来考虑，系统把内存中可以分配的物理块分为两部分，一部分按照比例分配给各并发进程，另一部分根据进程的优先级进行适当增加。

# 可变分配方式

可变分配方式是指分配给进程的物理块数，在该进程的运行期间可以动态变化。它用来解决由于事先分配给进程的物理块太少而导致的频繁缺页问题。
具体实现时，先为每一进程分配必要数量的物理块，使之可以开始运行，系统中余下的空闲物理块组成一个空闲物理块队列，当某一进程在运行过程中发生缺页时，系统从空闲物理块队列中取出一个空闲块分配给该进程。只要该空闲队列中还有物理块，凡发生缺页的进程都可以才该队列中申请并获得物理块。

# 进程的最小物理块数

最小物理块数是保证进程正常运行所需要的最小内存块数。进程需要的最小物理块数与计算机的硬件结构有关，取决于计算机的指令格式、功能和寻址方式。

# 页面调入策略

# 请求页调入

请求页调入简称请调，是指在 CPU 需要访问进程某页面时，发现所访问的页面不在内存，CPU 发出缺页中断信号，请求将该页调入内存。操作系统接收到缺页中断请求后，为之分配物理块并从外存将该页调入内存。
每个进程在刚开始执行时，所需的页面很多，会产生多次缺页中断，页面被逐一调入内存。根据程序的局部性原理，当进程运行一段时间后，所需要的页面会逐步减少，缺页中断次数会逐渐下降，最后趋向于很低的水平，进程运行进入相对平稳阶段。
请求页调入策略的优点是只有在需要时才将页面调入内存，节省了内存空间。
请求页调入策略的缺点：
- 在进程初次执行时，开始阶段会有大量的页调入内存，这时的进程切换开销很大。
- 发生缺页中断时操作系统会调入页面，而每次又仅调入一个页面，启动磁盘作 I/O 的频率很高。由于每次启动磁盘时会产生一个时间延迟，因此，会造成系统用于 I/O 的时间增长，系统效率降低。
- 对于执行顺序跳跃性大的程序，缺页情况变化大，难以趋向稳定的水平，从而引起系统不稳定。

# 预先页调入

预先页调入简称预调，是指由操作系统根据某种算法，预先估计进程可能要访问的页面，并在处理器需要访问页面之前先将页面预先调入内存。
该调入策略的优点是一次可将多个页面调入内存，减少了缺页中断的次数和 I/O 操作次数，系统付出的开销减少。如果预先动态估计准确率高，该调入策略会大大提高系统效率。
调入策略的缺点：
- 如果预先动态估计准确率较低，调入的页面不被使用的可能性大，系统效率较低。
- 如果程序员不能预先提供所需程序部分的信息，则该调度策略难以实施。
在实际应用中，页面调入会将请求页调入和预先页调入结合起来。在进程刚开始执行时或每次缺页中断时，采用预先页调入。在进程运行稳定后，如果发现缺页，系统可采用请求页调入

# 页面置换策略

当需要从外存调入页到内存时，如果当前内存没有空闲物理块，则操作系统需要将某些页置换出内存，再将新的页面换入内存。选择被置换出的页有两种策略：全局置换和局部置换

# 全局置换

全局置换是指操作系统从所有当前位于内存的页面中选择一个页面淘汰，释放出对应的物理块，而不是仅从需要该页的进程的物理块换出。这种置换方法会影响大多数进程的运行，是一种动态方法

# 局部置换

局部置换是指当某进程有页面需要换入到内存时，只能从该进程目前已在内存的页面中选择一页淘汰，该置换方法对其它进程没有影响。
局部置换与全局置换比较有明显的缺点：如果进程在执行期间所需要的内存物理块数发生变化，页面置换发生频繁，即使系统有空闲的物理块，也不可能增加给该进程；另外，如果系统给某进程分配的物理块数太多，系统不会收回，最终会造成内存空间浪费。

# 页面置换与页面分配的关联

# 固定分配局部置换

为每个进程分配固定数量的物理块，在进程的整个运行期间都不再改变。当一个进程运行中发生缺页中断时，操作系统只从该进程在内存中的页面中选择一页淘汰。
该策略不足在于：应为每个进程分配多少物理块数难以确定。如果分配给进程的物理块太少，缺页中断率高，进而导致整个多道程序系统运行缓慢；给多了，会使内存中能同时执行的进程数减少，进而造成处理器空闲和其他设备空闲，浪费资源。

# 可变分配全局置换

先为每一进程分配必要数量的物理块，使之可以开始运行，系统中余下的空闲物理块组成一个空闲物理块队列，当某一进程在运行中发生缺页时，系统从空闲物理块队列中取出一个空闲块分配给该进程。直到系统拥有的空闲物理块耗尽，才会从内存中选择一页淘汰，该页可以是内存中任一进程的页面。
该策略易于实现，且可以有效地减少缺页中断率，是采用得较多的一种分配和置换策略。

# 可变分配局部置换

新进程装入内存时，根据应用类型、程序要求，先分配给一定数目物理块。当产生缺页中断时，系统只能从产生缺页中断的进程的页面中选一个页面淘汰，不能影响其他进程的运行。操作系统要不时重新评价进程的物理块分配情况，增加或减少分配给进程的物理块以改善系统总的性能。

# 页面置换算法 😎

# 缺页率

一个进程或一个作业在运行中成功的页面访问次数为 S，即所访问的页面在内存中；不成功的页面访问次数为 F，即访问的页面不在内存，需要缺页中断并调入内存；需要访问的页面的总次数为 $A = S + F$ 。则缺页率 f 为： $f = F / A$
影响缺页率的因素如下：
- 进程分得的内存物理块数越多，缺页率越低。
- 划分的页面越大，缺页率越低。
- 如果程序局部性好，则缺页率低。
- 如果选取的置换算法优，则缺页率低。
在进程的内存物理块数和页面大小不能改变的情况下，要减少缺页率，就要考虑选择合适的页面置换算法。

# 先进先出（FIFO）页面置换算法

先进先出（Fist In First Out）算法的基本思想：总是选择最先进入内存的页面或驻留时间最长的页面先淘汰。该算法最早出现，易于实现。
实现：可以将所有页面按照进入内存的次序排成一个队列，设置一个替换指针指向队头的一页。当需要进行页面淘汰时，替换指针指向的即为当前最先进入内存的页面，该页被淘汰，然后修改指针指向淘汰页后一个页面即可，调入的新的页面排入队尾。
先进先出页面置换算法开销低、容易编程实现，适合于线性顺序特性好的程序。但是该算法没有考虑到页面的访问频率，很可能刚被换出的页面马上又要被访问，使得缺页率偏高
为了改善 FIFO 算法，减少缺页率，科学家尝试在进程发生缺页时给进程增加物理块。在实验中，Belady 发现了一个奇怪的现象，该现象也被称为 Belady 异常现象。即：当页数在一定范围内时，缺页率反而随分配给进程的物理块数的增加而增加

# 最佳（OPT）页面置换算法

最佳（optimal）页面置换算法由 Belady 在 1966 年提出，基本思想：在选择页面置换时应该考虑该页面将来使用的情况，将来最长时间不用的页面被淘汰。在进程采用固定页面分配的情况下，最佳页面置换算法具有最低的缺页率。

# 最近最少使用（LRU）页面置换算法

实现方法：系统须维护一个页面淘汰队列，该队列中存放当前在内存中的页号，每当访问一页时就调整一次，使队尾总指向最近访问的页，而队列头部就是最近最少用的页，发生缺页中断时总淘汰队列头所指示的页；而执行一次页面访问后，需要从队列中把该页调整到队列尾。

# 时钟（clock）置换算法

时钟置换算法的基本思想是：
- 将内存中所有的页面组织成一个循环队列，形成一个类似于时钟表面的环形表，循环队列指针类似于钟的指针，用来指向可能被淘汰的页面，指针开始时指向最先进入内存的页面。
- 时钟置换算法需要在页表中为每一页增加一个访问位 R 。当页面首次装入内存时， R 的初值设置为 “0”。当某个页面被访问过后， R 的值被设置为 “1”。
- 选择淘汰页面的方法是从指针当前指向的页面位置开始扫描时钟环，如果某个页面页表中的 R 为 “1”，表明该页被访问过，将 R 清 “0”，并跳过该页；如果某个页面页表中的 R 为 “0”，表明该页没有被访问过，该页被淘汰，指针推进一步；如果所有的页面都被访问过，指针绕环一圈，将所有页面的 R 清 “0”，指针回到起始位置，选择该页淘汰，指针推进一步。
为了提高置换效率，在页面置换时，如果被淘汰的页面没有被修改过，则不需写回外存。这样，将页表中的访问位 R 和页表中的修改位 M 配合，产生改进的时钟置换算法。
访问位 R 和修改位 M 的组合有下面四种情况：
- 最近没有被访问（ R = 0 ），没有被修改（ M = 0 ）：从指针当前位置开始，选择第一个 R = 0 ， M = 0 的页面淘汰。
- 最近没有被访问（ R = 0 ），但是被修改过（ M = 1 ）：如果没有 R = 0 ， M = 0 的页面，则从开始位置重新开始查找第一个 R = 0 ， M = 1 的页面并淘汰之。
- 最近被访问（ R = 1 ），没有被修改（ M = 0 ）：如果没有 R = 0 ， M = 1 的页面，表示所有的页面 R = 1 。在再次回到开始位置时，所有页面的访问位 R 都被清 “0”。从开始位置查找第一个 M = 0 的页面并淘汰之，此时不用将淘汰页面 “写” 回外存。
- 最近被访问（ R = 1 ），被修改（ M = 1 ）：当前面三种情况都不存在时才考虑 R = 1 ， M = 1 的情况。
该策略的主要优点是没有被修改过的页面会被淘汰，但不必写回外存，节省了 I/O 时间。但是查找淘汰页面可能需要多次扫描时钟，增加了算法的开销。

# 影响请求页式存储管理性能的因素

# 分配给进程的内存块数与缺页率的关系

实验结果表明，对每个进程来说，为其分配进程空间页面数约一半的物理块时，请求页式的效果最好

# 页面大小对系统性能的影响

从页表大小考虑：如果页面较小，页数就要增加，页表也随之扩大，为了控制页表所占的内存空间，应选择较大的页面尺寸。
从内存利用率考虑：内存以块为单位，一般情况下进程的最后一个页面总是装不满一个物理块，会产生内部碎片，为了减少内部碎片，应选择小的页面尺寸。
从读写一个页面所需的时间考虑：作业存放在辅助存储器上，从磁盘读入一个页面的时间包括等待时间（移臂时间 + 旋转时间）和传输时间，通常等待时间远大于传输时间。显然，加大页面的尺寸，有利于提高 I/O 的效率。

页面长度是由 CPU 中的 MMU 规定的，操作系统通过特定寄存器的指示位来指定当前选用的页面长度。

# 缺页率对系统性能的影响

用 p 表示缺页率，如果 p = 0 ，则不缺页；如果 p = 1 ，则始终缺页。
抖动：由于缺页而引起的一种系统现象，即处理器频繁地处理页面的换出和调入，使得处理器实际处理程序的能力大大减小。“抖动” 现象常在缺页率非常高时发生。
用 st 表示缺页处理时间。缺页处理时间包括从外存取相关页面并将其放入内存的时间。
用 ma 表示对内存一个页面的访问时间。
用 vt 表示有效访问时间。
在非缺页的情况下， vt = ma
在缺页率为 p 的情况下， vt = (1 − p) × ma + p × st
在任何情况下，缺页处理时间由下面三个主要部分构成：
- 缺页中断服务时间；
- 读页面时间；
- 恢复进程时间。

有效访问时间直接正比于缺页率

# 请求分段虚拟存储管理

# 请求分段虚拟存储管理的基本原理

请求分段的基本思想：将用户程序的所有段首先放在辅助存储器中，当用户程序被调度投入运行时，首先把当前需要的一段或几段装入内存，在执行过程中访问到不在内存的段时再把它们从外存装入。
请求分段的段表包括：段号、段长、存取权限、在内存中的起始地址、在外存中的起始地址、是否在内存、修改标志、共享标志和扩充位等。
在程序执行中需要访问某段时，查段表，若该段在内存，则按段式存储管理进行地址转换得到绝对地址。
若该段不在内存中，则硬件发出一个缺段中断。操作系统处理这个中断时，先查找内存分配表，找出一个足够大的连续区域容纳该分段。如果找不到足够大的连续区域则检查空闲区的总和，若空闲区总和能满足该分段要求，那么进行适当移动后，再将该段装入内存。若空闲区总和不能满足要求，则可调出一个或几个分段在辅助存储器上，再将该分段装入内存。
在执行过程中，有些数据段的大小会随输入数据多少而变化。这就需要在该分段尾部添加新信息，但添加后的段的总长度不应超过硬件允许的每段最大长度。对于这种变化的数据段，当要往其中添加新数据时，由于欲访问的地址超出原有的段长，硬件首先会产生一个越界中断。操作系统处理这个中断时，先去判断该段的 “扩充位” 标志，如可以扩充，则允许增加段的长度，如该段不允许扩充，那么这个越界中断就表示程序出错。

# 请求分段虚拟存储管理的段的共享和保护

请求分段虚拟存储管理为了实现段的共享，除了原有的进程段表外，还要在系统中建立一张段共享表，每个共享分段占一个表项，每个表项包含两部分内容：
- 第一部分包含共享段名、段长、内存起址、状态位（如在不在内存）、辅存地址、共享进程个数计数器。
- 第二部分包含共享该段的所有进程名、状态、段号、存取控制位（通常为只读）。
当出现笫一个要使用某个共享段的进程时，操作系统为此共享段分配一块内存，再将共享段装入该区。同时将共享段在内存的起始地址填入共享段表中对应项的内存始址处，共享进程个数计数器加 1，修改状态位为 1（在内存），填写使用该共享段的进程的有关信息（进程名、使用共享段的段号、存取控制等）。而进程段表中共享段的表项指向内存共享段表地址。此后，当又有进程要使用该共享段时，仅需直接填写共享段表和进程段表，以及把共享进程个数计数器加 1 就可以了。
当进程不再使用共享段时，应释放该共享段，除了在共享段表中删去进程占用项外，还要把共享进程个数计数器减 1。共享进程个数计数器为 0 时，说明已没有进程使用此共享段了，系统需要回收该共享段的物理内存，并把占用表项也取消。
优点：不同进程可以用不同段号使用同一个共享段；由于进程段表中共享段的表项指向内存共享段表地址，所以，每当共享段被移动、调出或再装入时，只要修改共享段表的项目，不必要修改共享该段的每个进程的段表。
由于每个分段在逻辑上是独立的，实现存储保护很方便：
- 越界检查：在段表寄存器中存放了段长信息，在进程段表中存放了每个段的段长。在存储访问时，首先，把指令逻辑地址中的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断；其次，还需检查段内地址是否大于段长，若是的话将产生地址越界中断，从而确保每个进程只在自己的地址空间内运行。
- 存取控制检查：在段表的每个表项中，均设有存取控制字段，用于规定此段的访问方式，通常设置的访问方式有：只读、读写、只执行等。

# 请求段页式虚拟存储管理

请求段页式虚拟存储管理是在段页式存储管理的基础上增加了用以实现虚拟存储的缺页中断机制、缺段中断机制来实现的。
与传统的段页式存储管理一样，用户的逻辑地址空间被划分为段号、段内页号与页内偏移。但是，请求段页式管理并没有将一个作业的所有段在作业运行前全部装入内存，只是部分段装入内存，因此，还需要有作业表来记载进入内存的作业段的情况。

# 设备管理

# 设备管理概述

# 设备管理的逻辑结构

图 19

# 设备控制器

图 20

# 设备控制方法 😎

# 程序循环查询方式

图 21

CPU 要不断的发送 I/O 测试指令用以测试设备控制器的忙 / 闲（busy）标志位，若设备不忙，则主存与外部设备交换一个字符或一个字。若设备忙，则 I/O 测试指令不断对它进行测试，直到设备空闲为止。
由于 CPU 的速度远高于 I/O 设备的速度，使得 CPU 绝大部分时间都处于等待 I/O 完成的循环测试之中。显然，这对 CPU 是极大的浪费。但是，它的控制简单，在 CPU 速度慢、要求不高的场合下常被采用。

# 中断驱动方式

图 22

引入中断机构是为了消除设备驱动程序不断地轮询控制器状态寄存器的开销，当 I/O 操作结束后，由设备控制器 “自动地” 通知设备驱动程序

# 直接内存访问方式

图 23

数据传输的基本单位是数据块，即每次传送至少一个数据块。
所传送的数据是从设备直接送入内存，或者直接读出内存的。
在传输时 CPU 参与更少，仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。

# 通道方式

I/O 通道方式是 DMA 方式的发展，它可进一步减少 CPU 的干预，即把对一个数据块的读 (或写) 为单位的干预，减少为对一组数据块的读 (或写) 及有关的控制和管理为单位的干预
有专门用于 I/O 的处理单元。在进行 I/O 操作时，接受 CPU 的委托，独立地执行自己的通道程序来实现内存与外设之间的数据传输。
使 CPU 从对 I/O 设备的繁忙直接控制中解脱出来，极大地提高了 CPU 与外设并行工作的程度，从而更有效地提高整个系统的资源利用率

# 通道分类

字节多路通道
选择通道
成组多路通道

# 通道工作方式

图 24

通道 I/O 操作由两种命令实现控制：CPU 的 I/O 指令和通道本身提供的通道程序。
CPU 的 I/O 指令的功能一般包括有：清除、停止、启动、查询等功能，除了操作码之外，I/O 指令中还有通道地址和设备地址域。I/O 指令属特权指令，只能由操作系统使用。
通道程序一般有读、写、查询、控制和转移等功能
在通道 I/O 工作过程中，CPU 对通道的通信是向通道发出启动、查询和停止通道指令；而通道向 CPU 的通信则采用中断方式向 CPU 汇报。

# 缓冲技术

# 缓冲技术的作用

它能改善中央处理器与外围设备之间速度不匹配的矛盾，提高 CPU 和 I/O 设备的并行性。
它能减少 I/O 对 CPU 的中断次数和放宽对 CPU 中断响应时间的要求
缓冲技术还能协调逻辑记录大小与物理记录大小不一致的问题

# 缓冲的分类

# 单缓冲

单缓冲指当一个进程发出 I/O 请求时，操作系统便在主存中为之分配一个缓冲区，用来临时存放输入／输出数据。它是操作系统提供的一种简单的缓冲形式。
在数据的输入或者过程中，在某一时刻该缓冲区只能存放输入数据或输出数据，而不能既是输入数据又是输出数据，否则会引起缓冲区中数据的混乱。对缓冲区来说，信息的输入和输出实际上是串行工作的。

图 25

# 双缓冲

图 26

双缓冲指在操作系统中为某一设备设置两个缓冲区，当一个缓冲区中的数据尚未被处理时可使用另一个缓冲区存放从设备读入或读出的数据，以此来进一步提高 CPU 和外设的并行程度。
在输入数据时，首先填满缓冲区 1，操作系统可从缓冲区 1 把数据送到用户进程区，用户进程便可对数据进行加工计算；与此同时，输入设备填充缓冲区 2。
当缓冲区 1 空出后，输入设备再次向缓冲区 1 输入。操作系统又可以把缓冲区 2 的数据传送到用户进程区，用户进程开始加工缓冲区 2 的数据。
这样两个缓冲区交替使用，使 CPU 和 I/O 设备的并行性进一步提高。仅当两个缓冲区都空或者都满，进程还要提取数据或者写入数据时，它才被迫等待

# 多缓冲

# 循环缓冲

为了使缓冲区资源得到充分利用，操作系统从主存区域中分配一组缓冲区，如图，根据用途分为：输入缓冲区组和输出缓冲区组。
每个缓冲区有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，组成了循环缓冲。每个缓冲区的大小可以等于物理记录的大小
这种循环式的多缓冲区是系统的公共资源，并由系统统一分配和管理，可供各个进程共享。为了管理各缓冲区，进行统一调度和管理，操作系统中通常要设立专门的机构来管理它们。

图 27

# 缓冲池

缓冲池由内存中的一组缓冲区构成，各缓冲区之间并不一定采用循环链表的方式进行链接，操作系统与用户进程将轮流地使用各个缓冲区，以改善系统性能。
缓冲池中多个缓冲区可供多个进程使用，既可用于输出又可用于输入，是一种现代操作系统经常采用的一种公用缓冲技术
缓冲池中的缓冲区一般按照内容被组织成三个队列：空闲缓冲区队列 emq 、输入缓冲区队列 inq 、输出缓冲区队列 outq 。
每个缓冲区根据其当前的工作性质不同，分为四种状态：收容输入、提取输入、收容输出、提取输出。
对缓冲池的管理，有两个基本操作 Getbuf 过程和 Putbuf 过程。 Getbuf（type） 用于从 type 所指定的队列的队首摘下一个缓冲区； Putbuf（type，number） 用于将由参数 number 所指示的缓冲区挂在 type 队列上。

图 28

# 输入输出软件

图 29

# 中断处理程序

凡是涉及到输入 / 输出设备开始、结束或者异常时，一般都会发生中断信号。
当一个中断信号发生时，若能及时得到相应，则正在运行的进程将被挂起，直到 I/O 操作结束并发出一个中断请求，CPU 响应后便转向中断处理程序，然后解除相应进程的阻塞状态。

图 30

# 设备驱动程序

所谓设备驱动程序是指驱动物理设备和 DMA 控制器或 I/O 控制等直接进行 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 控制方式紧密相关

# 设备独立性程序

所谓设备独立性，也称为设备无关性，是指在用户程序中不要直接使用物理设备名（或设备的物理地址），而只能使用逻辑设备名。
逻辑设备是实际物理设备属性的抽象，它不限于某类具体设备。逻辑设备究竟和哪一个具体的物理设备相对应，还要由系统根据当时的设备忙、闲情况来决定或由系统管理员指定
在应用程序中使用逻辑设备名来请求使用某类设备，而系统在实际执行时，使用物理设备名。
系统必须根据对应关系将逻辑设备名转换成物理设备名，进一步找到物理设备的驱动程序地址

图 31

引入设备独立性这一概念，使得用户程序可使用逻辑设备名，而不必使用物理设备名，有以下优点：
- 使得设备分配更加灵活，提高了设备的利用率。当多用户多进程请求分配设备时，系统可根据设备当时的忙闲情况，合理调整逻辑设备名与物理设备名之间的对应情况，以保证设备的充分使用。
- 可以实现 I/O 重定向。所谓 I/O 重定向是指可以更换 I/O 操作的设备而不必改变应用程序
设备驱动程序是一个与硬件（或设备）紧密相关的软件，为了实现设备独立性，就必须在驱动程序之上设置一层与设备无关的软件，其主要功能如下：
- 向用户层软件提供统一接口。
- 设备无关程序负责将设备名映射到相应的设备驱动程序。
- 设备保护。
- 协调不同设备数据块的差异。
- 差错控制。

# 用户层软件

用户层的 I/O 软件实际上就是面向设备具体应用的软件，它是 I/O 系统软件的最上层软件

# 设备分配与回收

# 设备信息描述

# 系统设备表 SDT

系统设备表记录系统中所有设备资源的状态。在整个系统中设置惟一的系统设备表 SDT ，是系统范围的数据结构，记录了系统中全部设备情况，并为每个设备设置了一个表项。 SDT 的每个表项主要包括：设备类型、设备标识符、指向 DCT 的指针以及驱动程序入口。

图 32

# 设备控制表 DCT

对系统范围内的任何一台设备，操作系统都配置了一张设备控制表 DCT ，用来记录设备的特性、设备和 I/O 控制器的连接情况以及设备的分配和使用情况。 DCT 在系统生成时或在该设备和系统连接时创建，但表中的内容则可根据系统执行情况动态修改。

图 33

# 控制器控制表 COCT

系统为每个控制器都设置了一个 COCT ，用它来反映 I/O 控制器的使用情况以及所连接的通道情况
主要包括：控制器标识符、控制器的状态、与控制器相连接的通道表指针、控制器队列的队首指针、控制器队列的队尾指针，各相应项意义与 DCT 类似。

# 通道控制表 CHCT

在设置有通道的系统中，操作系统为每个通道都配有一张通道控制表，它与 COCT 类似。

图 34

# 设备分配策略

独占方式就是把一台设备固定地分配给一个用户或进程，直到它运行结束。这种方式对用户来说是方便的，管理起来也简单，但资源往往造成浪费。因为用户程序或进程运行过程中不会自始至终都使用像打印机这类设备
共享方式是指设备可以在多个用户（或进程）“交替” 使用，即一个进程需要时，便申请它，获得后使用它，用完就释放它。其他进程也如此方式使用。磁盘、磁带就是可共享方式分配、使用的设备。
虚拟方式：为了提高独占设备的利用率，提高进程并行程度，引入了虚拟设备技术。虚拟设备技术就是利用快速、共享设备（例如磁盘）把慢速、独占设备模拟成为同类物理设备。

# SPOOLing 技术

# SPOOLing 系统的组成

输入井模拟假脱机输入，用于收容输入的数据。
输出井模拟脱机输出，用于收容用户程序的输出数据。
预输入程序模拟脱机输入时的外围控制机，将输入设备的输入信息送到输入井，当相关进程需要输入数据时，直接从输入井读入到内存中的用户程序区。
缓输出程序模拟脱机输出时的外围控制机，把用户要求输出的信息从用户程序区送到输出井，待输出设备空闲时，将输出井中的信息送到输出设备上。
井管理程序负责管理输入井与输出井的协调工作。在进程执行过程中，如果请求启动某台设备的输入或者输出工作，操作系统得到该请求并调出井管理程序，控制从相应输入井读取信息或将信息送至输出井内。

图 35

# 共享打印机

为了实现打印机的虚拟共享，应创建一个特殊的守护进程以及一个特殊的目录 —— SPOOLing 目录。
当用户进程请求打印输出时， SPOOLing 系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事：
- 由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中。
- 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。
实际上，当进程把该文件放到 SPOOLing 系统中之后就可以认为打印过程已经完成，虽然打印机还没有进行该文件的打印，因此 SPOOLing 也称为打印的 “假脱机” 过程。
而整个的打印作业由该守护进程进行处理，只有该守护进程能够真正使用打印机设备文件

# SPOOLing 技术的特点

提高了 I/O 的速度，缓和了高速的处理器与低速输入输出设备之间的矛盾。
将独占设备改造为共享设备，提高了设备的利用率。
实现了虚拟设备功能，将物理的单个设备变换为多个对应的逻辑设备。

# 设备分配算法

先来先服务算法。系统允许多个进程请求同一个设备，也允许一个进程请求多个设备。当有多个进程对同一设备提出 I/O 请求时，或者是在同一设备上进行多次 I/O 操作时，系统按照提出请求的先后顺序，将对应进程组织成一个设备请求队列。当设备空闲时，设备分配程序总是把此设备首先分配给队首进程
优先级高者优先算法。首先对有 I/O 的进程按照其优先级的高低进行排列，高优先级进程排在设备队列前面，低优先级进程排在后面。当有一个新进程要加入设备请求队列中时，并不是简单地把它挂在队尾，而是根据进程的优先级插在适当的位置。这样就能保证在该设备空闲时，系统能从 I/O 请求队列的队首取下一个具有最高优先级进程，并将设备分配给它。

# 设备分配

当系统中已经具备了设备分配的数据结构，而且在设备分配总原则下确定了一定分配算法后，若某进程提出 I/O 请求，设备分配程序便可进行分配。
设备分配过程是逐步由抽象信息表格到具体物理设备的过程，首先使用了管理逻辑设备信息的系统设备表，继而查找设备控制表，然后通过设备控制器利用通道启动设备，传输信息。

# 设备回收

当某一作业（或进程）使用完设备后，则需 “释放设备”，设备回收过程是设备分配过程的逆过程。
回收时，要请求操作系统依次修改与设备有关的通道控制表、设备控制器控制表、设备控制表和系统设备表，主要是修改其中的状态信息，以使设备能够及时被下一个进程使用。

# 文件系统

# 文件系统概述

# 文件的概念

在计算机系统中，文件是指存储在外部存储介质上的、由文件名标识的一组相关信息的集合。

# 文件系统的概念

操作系统中负责管理和存取文件信息的软件机构叫做文件管理
文件系统：操作系统中与文件管理有关的那部分软件和被管理的文件，以及实现管理所需要的一些数据结构的总体。
文件系统的功能
- 实现文件的 “按名存取” 功能。
- 实现能够快速定位文件的目录结构；考虑如何组织目录文件。
- 向用户提供一套使用方便、简单的操作命令。
- 管理磁盘、磁带等组成的文件存储器。
- 实现逻辑文件到物理文件的转换。
- 保证文件信息的安全可靠。
- 便于文件的共享。
常用文件系统举例
- EXT2：Linux 最为常用的文件系统，设计易于向后兼容，所以新版的文件系统代码无需改动就可以支持已有的文件系统。
- NFS：网络文件系统，允许多台计算机之间共享文件系统，易于从网络中的计算机上存取文件。
- HPFS：高性能文件系统，是 IBM OS/2 的文件系统。
- FAT：经过了 MS-DOS，Windows 3.x，Windows 9x，Windows NT，Windows 2000/XP 和 OS/2 等操作系统的不断改进，它已经发展成为包含 FAT12，FAT16 和 FAT32 的庞大家族。
- NTFS：NTFS 是微软为了配合 Windows NT 的推出而设计的文件系统，为系统提供了极大的安全性和可靠性。

# 文件的属性

一个文件包括文件体和文件属性两个部分：文件体是一系列的记录或字符流，以物理块存放在外存上，也叫文件内容。文件属性是对文件进行说明的信息。
主要属性：
- 文件名称：文件名称是供用户使用的外部标识，也是文件最基本的属性。
- 文件物理位置：具体标明文件在存储介质上所存放的物理位置。
- 文件拥有者：通常文件创建者对自己所建的文件拥有一切权限，而对其它用户所建的文件则拥有有限的权限。
- 文件权限：通过文件权限，文件拥有者可以为自己的文件赋予各种权限，如可允许自己读写和执行，允许同组的用户读写，而只允许其它用户读。
- 文件类型：可以从不同的角度来对文件进行分类，例如普通文件或是设备文件，可执行文件或是文本文件，等等。
- 文件长度：长度单位通常是字节。
- 文件时间：最初创建时间，最后一次的修改时间，最后一次的执行时间，最后一次的读时间等。

# 文件的分类

为了有效、方便地组织和管理文件，常按照不同的观点对文件进行分类。常用的几种文件分类方法：
- 按照文件的逻辑结构的不同：流式文件和纪录式文件。
- 按照用途：系统文件、库文件和用户文件。
- 按照性质：可以把文件分为普通文件、目录文件和特殊文件。

# 文件的使用

两类操作接口：
- 第一类是与文件有关的操作命令或作业控制语言中与文件有关的 JCL 语句
- 第二类是提供给用户程序使用的文件类系统调用
主要的系统调用：
- 文件创建
- 文件删除
- 文件截断
- 文件读
- 文件写
- 文件的读写定位
- 文件打开
- 文件关闭

# 文件的组织

存储介质：用来存储文件信息的载体，例如，磁带、磁盘和光盘等。
块：存储介质上连续信息所组成的一个区域，也叫做物理记录。
- 文件的内容及相关信息都是以 “块” 为单位存放在外存上的
- 外存物理空间的分配是以块为单位的。
- 块也是内存和外存进行信息交换的物理单位，每次总是交换一块或整数块信息。
文件组织：文件中信息的配置和构造方式，同一个文件应该从两个侧面来观察它的文件组织方式：
文件的逻辑结构：从用户的观点出发观察到的文件组织形式，用户可以直接处理，独立于文件的物理特性。
文件的物理结构：逻辑文件在物理存储空间中存放方法和组织关系，又称文件的存储结构

# 文件的逻辑结构 😎

# 流式文件

流式文件：文件内的数据不组成记录，只是依次的一串信息集合，如字节流或字符流，它也可以看成是无结构的或只有一个记录的记录式文件，所以也称作无结构文件
字节或字符是访问流式文件的基本单位，顺序存取时读 / 写指针每次步进 1 个字节或 1 个字符长度。
流式文件举例：源程序文件、可执行文件和库函数文件等
这些类型的文件并不需要分记录
没有结构并非意味着该类型的文件不能有结构，处理该文件的软件可以按照用户定义的结构来操作文件。

图 37

# 记录式文件

记录式文件：一种有结构的文件，指文件中的数据由若干条定长或不定长的记录构成，每条记录又由若干数据项构成。
记录是记录式文件进行存取的基本单位，顺序访问时文件读 / 写指针每次步进一条记录长度。
定长记录文件和不定长记录文件：记录式文件中的所有记录长度一般都相等，也可以不等
纪录式文件中记录之间的组织方式非常重要，设计时要综合考虑很多因素，例如，如何提高检索速度，如何便于记录的增删改等。

# 顺序文件

顺序文件：记录之间按某种顺序排列组织所形成的文件
在顺序文件中的记录可以按照不同的顺序进行排列。
- 一种是按照存入的时间先后排序：各记录之间的顺序与记录的关键字或内容无关。（日志文件和各种现场记录文件等场合）；
- 一种是按照记录中的关键字排序。
顺序文件的存取方式：
- 顺序存取：只要在系统中分别设置读写指针 Rptr 和 Wptr ，读完或写完一条记录后修改该指针指向下一条记录。
- 直接存取：也叫随机存取。主要适用于定长记录的顺序文件（任何记录的位置都很容易通过记录长度计算出来）。
优点：
- 适合大量记录批量存取的场合，此时对顺序文件的存取效率是所有逻辑文件中最高的。
- 只有顺序文件才能被存储在磁带上
缺点：
- 不适合交互系统中用户要求查找或修改单个记录的情况（但是给出记录位置查找定长记录除外）
- 增删记录比较困难，因为增加或删除记录后需要重新组织记录的顺序和关键字。

图 38

# 索引文件

索引文件：为变长记录的顺序文件再建立一张索引表，对主文件中的每个记录在索引表中都有相应的表项，用于记录该记录的长度以及指向该记录的指针。
索引文件可以根据不同的关键字建立索引，形成包含多个索引表的索引文件。
主要优点：
- 通过建立索引极大地提高了对文件的查找速度
- 对增加和删除记录也非常方便
主要缺点：存储开销变大，增删记录时还需要修改索引表

图 39

# 索引顺序文件

将顺序文件中的多个记录组合成一组，并对每一组记录建立一个索引，通过索引指针指向该记录组中的第一条记录
索引顺序文件是顺序文件和索引文件相结合的产物，结合两者的优点，同时又能有效克服变长记录文件的缺点，而且所付出的代价也小。
查找方法：首先也是利用用户（程序）所提供的关键字，以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置。再利用顺序查找法去查找主文件，从中找到所要求的记录。
主要优点：索引表占用空间小，同时查找效率比顺序文件又高，因此在文件记录比较多时采用索引顺序文件比较适合。

图 40

# 记录的成组与分解

逻辑记录：记录式文件的逻辑结构中的每条记录描述（用户看到的），按信息在逻辑上的独立含义划分的单位
物理记录：即 “块”，存储介质上连续信息所组成的区域，文件的内容及相关信息都是以 “块” 为单位存放在外存上的（外存存放的单位）
当一个物理块包含多个逻辑记录时需要进行记录的成组和分解
记录的成组：若干个逻辑记录合并成一组，写入一个块。
每块中的逻辑记录的个数称块因子。
成组操作一般先在输出缓冲区内进行，凑满一块后才将缓冲区内的信息写到存储介质上。
记录的分解：当存储介质上的一个物理记录读进输入缓冲区后，把逻辑记录从块中分离出来的操作叫记录的分解。
文件被打开后，在主存中分配相应的输入输出缓冲区，用于成组和分解。由于容量有限，操作系统限定同时打开的文件个数，以防止文件缓冲区太多而挤占紧张的主存空间。

图 41

# 文件的物理结构 😎

文件的物理结构不仅取决于存储介质的存储特性，还与采用的外存分配方式有关。
考察文件的物理结构时应该把文件看作相关物理块的集合以及如何给文件分配所需要的物理块

# 连续文件

把一个逻辑上连续的文件信息存放在依次相邻的物理块中的组织形式。
连续文件是基于磁带设备的最简单的物理结构，也适合其它各种外存设备。
文件物理地址的存储方式：目录项的 “文件物理地址” 字段中，记录该文件第一个记录所在的盘块号和文件长度（以盘块为单位）
优点：在顺序存取时速度较快，非常便于顺序访问。（因为只要在目录中找到顺序文件所在的第一个盘块号，就可以从此开始逐个盘块往下读写。）
应用场合：常用于存放系统文件，如操作系统文件、编译程序文件和其它由系统提供的实用程序文件，因为这类文件往往被从头至尾依次存取

图 42

# 链接文件

非连续分配：把一个逻辑上连续的文件分散地存放在不同的物理块中，这些物理块既不要求连续，也不必按规则排列。
链接分配是非连续分配的一种。
链接文件（链接分配）：通过每个物理块上的链接指针将同属于一个文件的多个离散的盘块链结成一个链表的组织形式，实现了离散分配
优点：
- 能适应文件的动态增长
- 消除了磁盘的外部碎片
- 添加、删除和修改记录也更方便。

# 隐式链接

每个物理块自身存放下一物理块的链接指针
目录项的 “物理地址” 字段中只要保存该文件的起始块号和结束块号的指针
主要缺点：
- 只适合于顺序访问，对随机访问是极其低效
- 每个物理块上增加了一个链接信息，为信息管理添加了一些麻烦。
- 通过链接指针将一大批离散的物理块链接起来，可靠性差，只要其中任何一个指针出现问题，都会导致整个文件信息丢失或出错。

图 43

# 显式链接

把用于链接文件的各物理块指针显式地放在内存的一张表格中，表格的序号是物理块号，从 0 开始，直到 N-1，N 为整个磁盘的盘块的总数，表格的每个表项中存放链接指针即下一个盘块号。
该表格就是 FAT（12,16,36）文件系统中的 FAT 表
MS-DOS 和 windows 早中期操作系统一直采用的文件系统技术。
在文件的目录项的 “物理地址” 字段中只要保存该文件的起始块号
缺点
- 不支持高效的直接存取，对一个较大的文件进行存取时，须在 FAT 中顺序地查找许多盘块号；
- FAT 表本身需要占用较大的内存空间

图 44

# 索引分配文件

索引分配结构：系统为每个文件建立一个索引表，集中记录该文件占用的盘块号。索引表可以直接存放在文件控制块 FCB 中，但是，大文件的索引表往往很大，所以大多数文件系统让索引表置于单独的物理块中且可驻留在磁盘的任意位置，文件控制块的 “物理地址” 字段只要保存该索引表所在的盘块号（即索引表地址）
无键索引表：索引表记录的是组成指定文件的磁盘块号，这种索引只是盘块号的序列，适用于流式文件；
有键索引表：该索引表的索引表项包含逻辑记录键及其磁盘块号，指出了每条逻辑记录在磁盘上的存放地址，即物理块号，适用于纪录式文件。
优点
- 实现了离散分配
- 有利于直接存取
缺点
- 索引表增加了空间开销，
- 不适合中小型文件，对于中小型文件会有空间的浪费。因为往往一个盘块能存放数百个盘块号，但对于中小型文件，本身通常只占用数个到数十个盘块，甚至更少，但仍须为之分配以索引块。
- 索引表的查找增加了时间开销。

# 多级索引文件

以上索引文件为一级索引文件：存放文件内容所占物理块号的盘块也称作一级索引块
一级索引存在的问题：当索引表本身占用许多物理块时，在查找某键对应的索引项时，可能依次需交换很多块。若索引表占用 n 块，则平均要交换 (n+1)／２次，才能找到所需记录的物理地址，当 n 很大时，这是很费时间的操作。
解决方法：为了提高大文件的查找速度，可以为这些一级索引块再建立一个索引，称为二级索引，即系统再分配一个盘块记录一级索引块的块号。
如果文件再大，还可以建立三级、四级索引，依次类推。
在 Unix 系统中，为了能兼顾到小、中、大以及特大型文件，采取了混合索引结构。
它在文件控制块的地址部分设置了 13 个地址项，即 iaddr(0) - iaddr(12) ，混合了四种寻址方式：直接寻址、一级索引寻址、二级索引寻址和三级索引寻址。
iaddr(0) - iaddr(9) 存放了直接寻址指针，即该指针指向的盘块直接存放了该文件的数据内容，如果文件再大就可以用到第 11、12 和 13 个地址项（ iaddr(10) - iaddr(12) ），分别存放的是一级索引地址、二级索引地址和三级索引地址。

图 47

# 直接文件

利用哈希函数直接建立逻辑记录的关键字与其物理地址的对应关系的文件组织形式。
直接文件只能在直接存取的存储设备（如磁盘）上实现，并且主要用于记录式文件。
优点：
- 记录在介质上不需要按序存放，因为它能根据关键字直接计算出物理地址，所以最适合直接存取；
- 相对于索引文件，它不需索引，节省了索引存储空间和索引查找时间。
适用场合：直接文件在不能采用顺序组织方法、次序较乱、又需在极短时间内存取的场合下极为适合，例如操作系统目录文件、实时处理文件、存储管理的页表查找、编译程序变量名表等采用直接文件特别有效。
主要缺点：需要解决冲突问题。因为地址的总数和关键字之间不存在一一对应关系。

# 文件的存取方法

存取方法：如何存储和检索文件数据的方法，它是操作系统为用户程序提供的使用文件的技术和手段。
存取方法和文件的逻辑结构、物理结构以及存储介质有密切的关系，许多操作系统都提供多种存取方法，而在一些文件处理密集的系统软件中，如数据库管理系统，文件存取的方法就更加丰富。
常用的方法：顺序存取，直接存取，按键存取

# 文件存储空间管理

文件管理的主要功能之一是如何在外部存储介质上为创建或扩充文件而分配空间，为删除文件而回收空间以及对空闲空间的管理。
磁盘可以随机存取的特性非常适合文件系统的实现，因此磁盘是最常用的文件外部存储介质
文件存储空间管理主要涉及两个问题：
- 磁盘空间的分配
- 磁盘空闲空间的有效管理

# 磁盘空间的分配

# 连续分配

文件被存放在外存空间连续存储区 (连续的物理块号) 中，在建立文件时，用户必须给出文件大小，然后，查找到能满足的连续存储区供使用，否则文件不能建立，用户进程必须等待。
优点：顺序访问时通常无需移动磁头，文件查找速度快，管理较为简单
缺点：为了获得足够大的连续存储区，需定时进行‘碎片’收集。因而，不适宜于文件频繁动态增长和收缩的情况，用户事先不知道文件长度也无法进行分配

# 非连续分配

非连续分配是指以物理块（扇区）为单位，按文件动态要求分配物理块，这些物理块不一定要连续，属于同一文件的块按文件记录的逻辑次序用链接指针连接或用索引表指示，即链接分配和索引分配。
优点：辅存空间管理效率高，便于文件动态增长和收缩，访问文件执行速度快，特别是以簇为单位的分配方法已被广泛使用。

# 磁盘空闲空间的管理

# 空闲区表法

系统为外存上的所有空闲块建立一张空闲区表，每个表项记录了一个空闲区，主要包括该空闲区的第一个空闲盘块号、该区的空闲盘块和状态等信息，再将所有的空闲区按其起始盘块号递增的次序排列。

# 空闲块链表法

空闲块链表法是将所有空闲块连接在一起，组成一个空闲块链表
空闲块链表的一个变种是空闲盘区链，将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）组成一个链表，也适合连续文件的组织形式。

图 48

# 位示图法

空闲空间表还可由位图或位矢量的方法来实现。每一个磁盘块由 1 位（bit）来表示。如果该磁盘块是空闲的，这个位就置 0；否则，就置 1

# 文件目录

# 文件目录的基本概念 😊

# 文件控制块

为了能对文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块（File Control Block， FCB ）。
每当创建一个文件，系统都要为其建立一个 FCB ， FCB 和文件是一一对应的。每个文件有两部分组成：
- FCB （文件属性信息）
- 文件体（文件内容信息）
FCB 一般包括以下文件属性信息：
- 有关文件存取控制的信息。
- 有关文件结构的信息。文件的逻辑结构，如记录类型、记录个数、记录长度、成组因子数等。文件的物理结构，如文件所在设备名，文件物理结构类型，记录存放在外存的相对位置或文件第一块的物理块号，也可指出文件索引的存放位置等。
- 有关文件使用的信息。已打开该文件的进程数，文件被修改的情况，文件最大和当前大小等。
- 有关文件管理的信息。如文件建立日期、文件最近修改日期、文件访问日期、文件保留期限、记帐信息等
FCB 的重要作用：建立文件名与外存空间中的物理地址的对应关系，从而实现 “按名存取”。
主要过程：系统存取文件时，先找到其 FCB ，从 FCB 中再找到文件信息盘块号或首块物理位置等物理地址信息就能存取文件信息。

为了加快文件的查找速度，通常把 FCB 集中起来进行管理，文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。
文件目录也是以文件的形式保存在外存上的，这就形成了目录文件。
因此，文件目录的目录项有两种，一种是用于描述子目录（即目录文件）的 FCB ，一种是普通文件的 FCB 。
目录文件与普通文件不同之处：
目录文件永远不会空，它至少包含两个目录项
- 当前目录项 “.”
- 父目录项 “..”

注意：要搜索到某个文件的外存物理地址，必须先从文件的最外层目录逐层搜索匹配比较。文件目录和 FCB 是现实 “按名存取” 的重要数据结构

# 目录文件的组织 😊

# `FCB` 线性表

目录文件中直接存放该目录下所有文件和子目录的 FCB 信息，组成了一个 FCB 线性表，即每个目录项记录了该文件或子目录对应的完整 FCB 信息
缺点：这样组织 FCB ，当文件很多时，目录文件本身可能要占用大量的盘块数，使得目录检索的速度很慢。

# 索引节点

基本思想：在检索目录文件的过程中，其实只用到了文件名，仅当找到一个目录项（即其中的文件名与指定要查找的文件名相匹配）时，才需从该目录项中读出该文件的物理地址。而其他一些对该文件进行描述的信息，在检索目录时一概不用。显然，这些信息在检索目录时，不需要调入内存。
索引节点：把文件目录项中的文件名和其它描述信息分开，后者单独组成定长的一个数据结构，称为索引节点（ i-node 或 inode 也称 i 节点）
索引节点号：一个文件系统中的所有文件的索引节点都集中存放在外存上的索引节点区，并对每个索引节点进行编号（i 节点号）。
文件目录项：不再是完整的 FCB ，只要存放 14 个字节的文件名和 2 个字节的 i 节点号
优点：通过索引节点的组织方式大大提高了目录的检索速度
外存索引节点存在的问题：由于访问某一文件的过程中，会频繁地涉及到文件的索引节点，不断在内、外存之间引用它，系统消耗很大。
解决方法：内存（活动）索引节点表，正在被使用的索引节点信息保存到内存索引节点表。
在系统占用的内存区里专门开辟一张表（例如 100 个表目）每个表目称为一个内存活动 i 节点。

图 49

检索文件的过程：检索文件时，先从目录文件中找到文件名匹配的目录项，在目录项中找到该文件的索引节点号，根据索引节点号就可以在索引节点区中找到该文件的索引节点，找到了 i 节点，就获得了它所对应的文件的一切必要属性信息。

# 哈希表组织

具体实现：目录文件每个目录项中存放一个块号，每个目录项都设一个序号（类似于数组下标），哈希函数以文件名作为自变量计算散列函数的值，以该值作为序号直接定位的目录文件中的目录项，然后在目录项中找到块号，该块号所指的块内就存放了该文件的 FCB 。
具有相同散列值的文件的 FCB 放在一个物理块内，如果相同散列值的文件数目超过一个物理块能存放 FCB 的数目就产生冲突，需要作溢出处理。

图 50

该方法可以大幅度地减少目录搜索时间。插入和删除目录项都很简单，只需要考虑两个目录项冲突的情况，即两个文件名返回的数值一样的情形。哈希表的主要难点是选择合适的哈希表长度与适当的哈希函数。

# 目录的结构

# 单级目录结构

整个文件系统中仅建立和维护一张总的目录表，系统中所有文件都在该表中占有一项。
优点：实现简单
缺点：
- 不允许文件重名。
- 文件查找速度慢。
- 不便于实现文件共享。单级目录结构只适合于单用户操作系统。

图 51

# 两级目录结构

二级目录可以解决文件重名，即把系统中的目录分为一个主目录（Master File Directory，MFD）和多个次目录（User File Directory，UFD）。
在多用户系统中，一般每个用户都拥有一个属于自己的次目录 UFD，而主目录 MFD 则存储着各个 UFD 的信息，标明各个 UFD 的名称、物理位置等。
当使用文件时，用户必须给出用户名和文件名。系统根据用户名在主目录中找到该用户目录，再根据文件名在用户目录中找到文件的物理地址。
优点：
- 提高了文件检索速度（用户名大大缩小了需要检索的文件数量）
- 部分地允许文件名重名。
缺点：对同一用户，也不能有两个同名的文件存在，限制了共享；多个用户完全隔离开来不便于实现多个用户协同完成任务。

图 53

# 多级层次目录

多级层次目录（树形目录）可以明显地提高对目录的检索速度和文件系统的性能。
在多级层次目录结构中，有一个根目录和许多分目录，根目录是唯一的，每一级目录不但可以包含文件，而且还可以包含下一级的分目录，从而形成了树状目录结构
几个概念：
- 路径名（ path name ）
- 绝对路径（ absolute path name ）
- 当前目录（ current directory ）
- 相对路径名（ relative path name ）
优点：
- 既可方便用户查找文件，又可以把不同类型和不同用途的文件分类。
- 允许文件重名。
- 利用多级层次结构关系，可以更方便地制定保护文件的存取权限
缺点：不能直接支持文件或目录的共享，因为这种纯树型目录中每个文件只能有一个父目录

图 54

# 图状目录结构

有向无环图目录结构：允许一个文件有多个父目录，不同的目录可以以相同或不同的文件名共享同一个文件，形成的目录结构图不会出现环（因为不支持目录共享）
有环图目录结构：除了允许文件被共享，还支持目录被共享，则目录结构图中就有可能出现环

# 目录的检索

在采用树形目录结构的文件系统中，要根据用户提供的文件路径名，从根目录或当前目录开始，逐级查找路径名中的各子目录名，用它们作为索引，逐层搜索各个目录文件，最后找到匹配的文件目录项

# 文件目录操作

创建目录：在外部存储介质中，创建一个目录文件以备存取文件属性信息。
删除目录：从外部存储介质中，删除一个目录文件。只有当目录为空时，才能删除。
改变目录：用户可利用改变目录的命令，通过指定目录的绝对或相对路径名，设置当前目录。
检索目录：首先，系统利用用户提供的文件名，对文件目录进行查询，以找到相应的属性信息；然后，根据这些属性信息，得出文件所在外部存储介质的物理位置；最后，如果需要，可启动磁盘驱动程序，将所需的文件数据读到内存中。
移动目录：允许文件或子目录在不同的父目录之间移动，文件或子目录经移动后，其文件的路径名将随之改变。
链接操作：通过链接操作，让指定文件具有多个父目录，从而实现文件共享。
打开目录：如要使用的目录不在内存中，则需要打开目录，从外存上读入相应的目录文件。
关闭目录：当所用目录使用结束后，应关闭目录以释放内存空间。

# 文件系统调用的实现

# 实现系统调用的相关数据结构

# 用户打开文件表

进程 PCB 结构中保留一个 files_struct ，称为用户打开文件表或文件描述符表。表项的序号是文件描述符 fd ，此登记项内登记系统打开文件表的一个入口指针 fp ，通过此系统打开文件表项连接到打开文件的活动 inode

# 系统打开文件表

为解决多用户进程共享文件、父子进程共享文件而设置的系统数据结构 file_struct 。主存专门开辟最多登记 256 项的系统打开文件表区，当打开一个文件时，通过此表项把用户打开文件表的表项与文件活动 inode 连接起来，以实现数据的访问和信息共享

图 58

# 活动索引节点表

由于文件的索引节点中保存的信息非常重要，当系统需要对文件进行各种操作时，都离不开文件系统的索引节点表中指出的文件属性信息。因此，在实现中也将被访问文件在磁盘中的索引节点复制到内存中，构成了活动索引节点表，从而使对文件的访问更加便利和快捷

图 59

# 内存各数据结构之间的关系

图 60

# 创建文件

int fd = create(char *pathname, int mode);

fd=create(“/home/zhao/file1.c”,0775) 执行的具体过程：
- 为新文件 file1.c 分配磁盘 inode 和活动 inode ，并把 inode 号与文件分量名 file1.c 组成新的目录项，记录到该文件目录路径 /home/zhao 的目录文件中。显然，在这一过程中，需要执行目录检索程序。
- 在新文件所对应的活动 inode 中置初值，包括把存取权限 i_mode 置为 0775 ，链接计数 i_count 置为 “1” 等。
- 为新文件分配用户打开文件表项和系统打开文件表项，置系统打开文件表项的初值，包括在 f_flag 中置 “写” 标志，读写位移 f_offset 清 0，等等；把用户打开文件表项、系统打开文件表项及 file1.c 所对应的活动 inode 用指针连接起来，最后，把文件描述符 fd 返回给调用者。

# 文件的链接、解除链接和删除

link 和 unlink
- link : 链接文件，实现文件共享， i_nlink+1
- unlink ：删除文件或解除链接， i_nlink-1

注意：删除的任务是把指定文件从所在的目录文件中去除，删除时如果没有链接用户（即 i_nlink 为 “1”），还要把文件占用的存储空间释放。

# 打开文件

int fd = open(char *pathname, int flags);

打开：文件在使用之前必须先 “打开”，以建立进程与文件之间的联系，而文件描述符唯一地标识了这样一种连接，其任务是把文件的磁盘索引节点复制到主存的活动索引节点表中，同时建立一个独立的读写文件数据结构，即系统打开文件表的一个表项。
实现过程：
- 检查是否有其他进程已经打开该文件，如果有，则活动 inode 表中已有此文件的 inode ，只要把对应的活动 inode 中的 i_count 加 1， i_count 反映了通过不同的系统打开文件表项来共享同一活动 inode 的进程数目，它是以后执行文件关闭操作时，活动 inode 能否被释放的依据。
- 如果是第一次打开该文件，则检索目录，要求打开的文件应该是已经创建的文件，它应登记在文件目录中，否则会出错。在检索到指定文件之后，就把它的磁盘索引节点复制到活动索引节点表中。
- 根据参数 flags 所给出的打开方式与活动索引节点中在创建文件时所记录的文件访问权限相比较，如果非法，则这次打开失败。
- 当 “打开” 合法时，为文件分配用户打开文件表项和系统打开文件表项，并为表项设置初值。通过指针建立这些表项与活动索引节点间的联系。把文件描述符 fd （即用户打开文件表中相应文件表项的序号）返回给调用者。

# 关闭文件

int close(int fd);

关闭：活动索引节点表的大小受到容量的限制，这就要求用户一旦不再对文件进行操作时，应立即释放相应的活动索引节点，以便让其他进程使用
实现过程
- 根据 fd 找到用户打开文件表项，再找到系统打开文件表项。释放用户打开文件表项。
- 把对应系统打开文件表项中的 f_count 减 “1”，如果非 “0”，说明进程族（例如父子进程）中还有进程共享这一表项，不用释放此表项直接返回；否则释放表项，并找到与之连接的活动索引节点。
- 把活动索引节点中的 i_count 减 “1”，若不为 “0”，表明还有其他用户进程正在使用该文件，不用释放而直接返回，否则在把该活动索引节点中的内容复制回磁盘上的相应索引节点中后，释放该活动索引节点。
关于 f_count 和 i_count (实现动态共享)
- f_count 反映不同进程通过同一个系统打开文件表项共享一个文件的情况；
- i_count 反映不同进程通过不同系统打开文件表项共享一个文件的情况。
- 由于文件的读写位移指针是存放在系统打开文件表项中的，所以前者实现的是使用相同位移指针的动态共享文件方式，主要适合同一进程族中的进程之间，即父子进程之间共享文件；后者实现的是使用不同读写位移指针的动态共享文件方式。

# 读文件

int nr = read(int fd, char *buf, int count);

实现过程：首先根据 f_flag 中的信息，检查读操作合法性，如果读操作合法，按活动索引节点中 i_addr 指出的文件物理块存放地址，从文件的当前位移量 f_offset 处开始，读出所要求的字节数到块设备缓冲区中，然后再送到 bufp 指向的用户主存区中。

# 写文件

int nw = write(int fd, char *buf, int count);

其中 fd 、 count 和 nw 的含义类似于 read 中的含义， buf 是信息传送的源地址，即把 buf 所指向的用户数据区中的信息写入文件中。

# 随机存取

lseek(int fe, int offset, int whence);

其中，当 whence 值为 0 时，则 f_offset 被置为参数 offset 的值；当 whence 值为 1 是，则 f_offset 被置为文件当前位置值加上 offset 的值
关于 f_offset : 在文件初次 “打开” 时，文件的位移量 f_offset 清空为 0，以后的文件读写操作总是根据 offset 的当前值来顺序地读写文件。
为了支持文件的随机访问，文件系统提供了系统调用 lseek ，允许用户在读写文件之前，事先改变 f_offset 的指向。

# 文件共享

# 静态共享

静态共享：文件或目录的共享关系不管用户是否正在使用系统都存在的共享方式。
文件链接：允许一个文件或目录有多个父目录，实际上仅有一处物理存储
静态共享主要有两种方式实现链接：一种是基于索引节点的方式，一般不适合目录共享，另一种是符号链接共享的方式，适合于文件也适合于目录

# 基于索引节点的链接共享

通过索引节点实现链接：多个目录共享一个文件，只要把被共享文件的目录项指向同一个索引节点，即存放相同的索引节点号，被共享的文件可以同名，也可以不同名。
只适合文件共享

图 61

# 符号链接共享

符号链接：只有原文件的目录项才拥有指向其索引结点的指针，而共享该文件的其他链接文件只有该文件的路径名，并不拥有指向其索引结点的指针，这个保存的路径名也称作符号，所以叫符号链接。
不但可以用于文件共享，也可用于目录共享
符号链接本身是一种只有文件名，不指向 inode 的文件，是一种 link 类型的特殊文件。

图 62

# 动态共享

动态共享：就系统中不同的用户进程或同一用户的不同进程并发地访问同一文件。这种共享关系只有当用户进程存在时才可能出现，一旦用户的进程消亡，其共享关系也就自动消失。
用户打开文件表、系统打开文件表和内存活动索引节点表是实现动态文件共享的重要数据结构
根据是否共享读写位移指针，动态共享分为两种方式：共享位移指针的动态共享方式、不共享位移指针的动态共享方式

# 文件系统体系结构

文件系统的体系结构通常采用分层结构，有以下三部分组成:
- 文件管理层：实现文件的逻辑结构，为用户提供各种文件系统调用，及文件访问权限的设置等工作；
- 目录管理：负责查找文件描述符，进而找到需要访问的文件，并进行访问权限检查等工作；
- 磁盘主存映射管理：将文件的逻辑地址转换成磁盘的物理地址，即由逻辑块号找到柱面号、磁道号和扇区号，具体的数据传输操作由设备管理实现。

# 文件系统的层次结构模型

文件系统接口层：主要用于接收用户对文件的操作命令或系统调用，根据用户对文件的存取要求将其转换为统一格式的文件系统内部调用。
文件目录管理层：根据文件名或文件路径名建立或搜索文件目录，获得文件内部标志和目录中的文件属性。从目录中的文件属性确定访问文件的用户身份，验证存取权限，判定本次文件操作的合法性，实现文件的存取、共享、保护。如果不允许当前用户访问，则发出操作失败信息。
基本文件系统层：根据文件内部标志将文件说明信息调入内存，即打开文件，为访问文件做准备。该层根据文件的逻辑结构和存取方法等信息，把指定的逻辑记录地址变换成相应的物理块地址。对于流式文件，只要把用户指定的逻辑地址按块长计算出相对块号；对纪录式文件，先把记录号转换成逻辑地址，再把逻辑地址转换成相对块号。
物理文件系统层：根据文件在内存中的物理结构信息，将相对块号和块内地址变换成文件存储器的物理块号和块内地址。
设备分配控制层：负责文件存储空间的分配，动态地为文件的写操作申请物理块，实现文件缓冲区的管理。该层根据申请的物理块号生成 I/O 控制系统的地址格式。
输入 / 输出接口层：执行 I/O 操作，为文件分配磁盘等物理介质空间，实现文件信息的存取，与设备管理功能相联系。

图 64

# 文件操作的执行过程

根据上面文件系统的层次结构，以写一个文件为例简要说明文件写操作发出时，各层是如何工作和相互衔接的。
- 当用户写一个文件时，应用程序首先调用文件系统提供的接口，将写文件的请求转换为统一格式的文件系统内部调用。
- 文件系统管理根据写文件的文件名和文件路径读内存中相应的目录，修改并更新文件目录。
- 基本文件系统根据文件内部标志将文件说明信息放入内存，写入内存中的打开文件表，打开文件，为访问文件做准备。
- 物理文件系统根据写文件的结构和存取方法等逻辑结构信息，把指定的逻辑记录地址变换成相应的物理块地址。对于流式文件，只要把用户指定的逻辑地址按块长计算出相对块号；对记录式文件，先把记录号变换成逻辑地址，再把逻辑地址按块长计算出相对块号。
- 物理文件系统将相对块号和块内地址变换为文件存储器的物理块号和块内地址。
- 设备分配控制为文件的写操作申请物理块，实现文件缓冲区的管理。系统根据申请的物理块号生成 I/O 控制系统的地址格式。
- 输入 / 输出接口执行 I/O 操作，为文件分配磁盘等物理介质空间，并将对磁盘的请求信息传递给磁盘管理。

# 虚拟文件系统

为了同时支持多种文件系统，不同的操作系统采用不同的技术方案提供了虚拟文件系统。
目标：
- 把多种文件系统纳入统一框架，不同的磁盘分区可包含不同的文件系统，对它们的使用和传统的单一文件系统并无区别；
- 用户可通过一组系统调用对不同的文件系统及文件进行操作，系统调用可以跨物理介质和跨文件系统执行，如从一个文件系统复制或移动数据到另一个文件系统中，即提供对不同文件系统透明的相互访问；
- 对网络文件提供完全的支持，访问远程节点上的文件应与访问本地节点的文件一致；
- 提供对特殊文件系统的支持
虚拟文件系统也称虚拟文件系统系统开关（Virtual File System，VFS），它是内核的一个子系统，提供一个通用文件系统模型，概括所能见到的文件系统的常用功能和行为，处理一切与底层设备管理相关的细节，为应用程序提供标准接口。具体设计时在原有的具体文件系统层次结构上增加应用层、虚拟层和实现层。各层的功能如下：
- 应用层：VFS 模型源于 UNIX 文件系统，使得用户可以直接使用标准 UNIX 文件系统调用来操作文件，无须考虑具体文件系统的特性和物理存储介质，通过 VFS 访问文件系统，才使得不同文件系统之间的协作性和通用性成为可能。
- 虚拟层：在对具体文件系统的共同特性进行抽象的基础上，形成与具体文件系统的实现无关的虚拟层，并在其上定义与用户的一致性接口。
- 实现层：使用类似于开关表的技术进行具体文件系统的转接，实现各种文件系统的细节。