理论知识

计算机学科理论

发布日期: 2022-08-14

更新日期: 2023-09-11

文章字数: 41.9k

阅读时长: 153 分

Chapter 1.操作系统概述

1.1 操作系统的类型

1.1.1 基本类型

(单道/多道)批处理系统

批处理(batch processing)，即将作业按照它们的性质分组(批)，然后成组(批)提交给计算机系统。

多道批处理系统出现的前提：通道技术、中断技术

通道：专门用于负责输入输出的硬件装置(输入输出处理机，IOP)。

通道思想：用户提交的作业先在外存排成一个队列（后备队列），由作业调度程序按照一定的算法从中选择若干作业调入内存，共享系统中的各种资源。

多道批处理系统的特征：

多道性

无序性

调度性（两级）

多道批处理系统的优缺点：

优点：

资源利用率高

系统吞吐量大

缺点：

平均周转时间长

无交互能力

分时系统
实时系统

1.1.2 分时系统

一台主机周围联接多个终端，多个用户通过不同的终端共享使用主机资源。

分时系统的特征：

多路性
独立性
及时性
交互性

分时系统实现的关键问题：

及时接收：及时接收来自终端用户的命令
及时处理：及时响应用户输入的命令，即响应时间要短

实现方法：

简单分时系统：单道，时间片（Time Slice）
具有前后台的分时系统
- 前台存放分时作业，后台存放批处理作业。
- 仅当前台无作业处理时，才运行后台作业。
多道分时系统：目前采用较多的分时系统。

影响响应时间的因素：

时间片一定
用户数一定
系统开销
对换信息量

1.1.3 实时系统

实时系统的分类：

实时过程控制
实时信息处理

实时系统的类型：

周期性实时任务/非周期性实时任务
每一个任务都有一个截止时间（deadline）：开始截止时间、完成截止时间
根据对截止时间的要求划分：硬实时任务/软实时任务

实时系统的特征：

多路性
交互性
独立性
及时性
可靠性

实时系统与批处理、分时系统的区别：

属“专用系统”，处理程序常驻主存

有较强的中断处理机构、分析机构

有较高的精度和可靠性

1.2 操作系统的工作控制方式

中断（Interrupt）【硬件】——中断向量、中断驱动
陷入（trap）【软件】

1.3 操作系统的硬件保护

双模式：内核模式（或称系统模式/内核态/系统态）、用户模式（或称用户态）

I/O保护：特权指令（只在内核模式下才允许执行的指令）和非特权指令
CPU保护：定时器（设置中断计算机的周期时间，可固定/可变）——CPU Interval
内存保护：基址寄存器（存放程序基本地址值）、限长寄存器、越界检测

1.4 操作系统的设置目标、功能和特征

设置目标：

管理系统资源，达到系统资源的有效利用和共享。（主要目标）
合理组织计算机的工作流程，改善系统性能（响应时间、吞吐量）。（主要目标）
提供用户接口，简化用户使用操作。（主要目标）
可扩展——满足计算机硬件与体系结构的发展及应用不断扩大的要求，能扩展新的功能
开放——遵循世界标准规范，特别是开放系统互连OSI国际标准；凡遵循国际标准所开发的硬件和软件，都能彼此兼容
安全可靠

功能：

存储管理：内存分配、内存保护、地址映射、内存扩充
处理机管理：进程控制、进程同步、进程通信、进程调度
设备管理：缓冲管理、设备分配、设备处理、设备独立性和虚拟设备
文件管理：外存管理、目录管理、文件操作
用户接口：命令接口、程序接口、图形接口

注：

当用户程序需要使用操作系统所提供的服务时，采用系统调用接口来完成，系统调用是程序调用的一种。

特征：

并发性
共享性
异步性
随机性
虚拟性

各特征解释如下：

1.5 操作系统安全相关概念

操作系统安全的目标：

控制哪些人来用操作系统
控制合法用户使用哪些程序
控制进程能访问哪些数据或资源
保护用户之间的资源共享

操作系统安全的需求：

系统边界安全
系统权限管理
应用和数据的访问控制
可信通路
安全审计和管理

操作系统安全的内容：

Authentication（认证）：who are you？
Access Control/Authorisation（访问控制/授权）： How to use？
Auditing（审计）： What have you done?
Action（响应）：How to response your actions？

Chapter 2.进程与线程

2.1 程序执行方式

程序的顺序执行：顺序性、封闭性、可再现性（只要程序执行环境和初始条件相同，重复执行时结果都将相同）。

程序的并发执行：间断性（每个程序都是“执行-停止-执行”）、失去封闭性（一个程序执行期间，另一个程序可以插入执行）、不可再现性。

2.2 前趋图

由多个结点构成的有向无循环图，用于描述程序中操作间的关系。

若两个结点 $P_i$、$P_j$，仅当 $P_i$ 操作完成后，才能执行 $P_j$ 结点的操作，称 $P_i$，$P_j$ 之间存在前趋关系。表示为：$P_i \rightarrow P_j$。

集合表示：${(P_i,P_j)|仅当P_i完成，才能执行P_j }$

程序 $P_i$ 和 $P_j$ 并发执行的Bernstein条件：

$ (R(P_i) ∩ W(P_j))∪ (R(P_j) ∩ W(P_i))∪(W(P_i) ∩W(P_j))= { }$

其中：

$R(P_i)={a_1,…,a_m}$：进程 $P_i$ 执行其间所需参考的所有变量的集合——读集
$W(P_i)={b_1,…,b_n}$：进程 $P_i$ 执行其间所要改变的所有变量的集合——写集

2.3 进程的概念和特征

进程(Process)是一个具有一定独立功能的可并发执行的程序，在一个数据集合上的运行过程。进程的特征有：

并发性：可并发执行
制约性：对资源争用而相互制约
结构特征：==进程=程序+数据+PCB==（进程控制块）
动态性：有生命周期
独立性
异步性：进程按照各自不可预知的速度向前推进

进程和程序的区别：

进程是程序的一次运行过程，是一个动态实体，而程序是一个指令的集合，是静态实体

进程具有生命周期，具有创建、执行和撤销的过程，而程序一旦创建，可以永远存在

进程实体由程序段、数据段及进程控制块组成

进程与程序之间不存在一一对应的关系，不同的进程可以对应相同的程序，一个进程中还可以同时调用多个程序

进程实体是一个能独立运行的基本单位，可独立获得资源和独立调度；而程序不能作为独立的单位参加运行

进程可按异步方式运行；程序不是运行实体，故不能异步执行

2.4 进程控制块PCB

2.4.1 主要内容

进程标识信息：

（1）进程本身：外标识、内标识（PID）

（2）家族信息：父进程、子进程信息
处理机状态信息：中断现场保留区（PSW程序状态字）
进程调度信息：状态、优先级、入主存
进程控制信息：

（1）程序、数据的外存/内存地址

（2）进程同步和通信机制：消息队列、信号量

（3）资源清单

（4）链接指针

注：

PCB不包含页面大小信息

PCB在进程被创建时建立，在进程被撤销时删除

进程只能有唯一的进程控制块

2.4.2 组织方式

线性方式：系统中所有PCB都组织在一个线性表中，表的首地址存放在内存专用区
链接方式：具有相同状态进程的PCB通过PCB中的链接字链接成一个队列
索引方式：系统根据进程状态的不同，建立索引表，根据索引值查找进程。

2.5 进程的状态

2.5.1 进程的三个基本状态

运行状态（Running）：指令被执行
就绪状态（Ready）：进程等待分配CPU
阻塞状态（Blocked/Waiting）：进程等待事件（I/O事件）的发生

2.5.2 新建状态和终止状态

新建状态（New）：刚被创建，尚未进入就绪队列时的状态
终止状态（Terminated）：进程正常/异常结束，移出就绪队列，但尚未撤销时的状态

注意：

这幅图中状态转换的前驱、后继，比如“等待->运行”、“就绪->等待”状态是不存在的，因为运行只认识就绪状态，等待只认识输入/输出状态；

当进程从执行状态转换为就绪状态，则表示时间片用完。

2.5.3 挂起/解挂状态

设置进程挂起/解挂状态的原因：

用户需要：中间结果与预期不符；
操作系统需要：系统某些功能故障；
系统负荷过重
父进程请求：修改或协调子进程
对换的需要

设置挂起状态后进程状态的转换：

设置挂起状态后，进程的就绪分为活动就绪（Readya）和静止就绪（Readys）
进程的阻塞状态分为活动阻塞（Blockeda）、静止阻塞（Blockeds）

2.6 进程控制

2.6.1 内核定义

现代操作系统设计采用层次结构，往往将一些与硬件紧密相关的模块或运行频率较高的模块设置在第一层软件中，称为操作系统的内核。

2.6.2 内核基本功能

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

原语是指在操作系统内核中，由若干条指令构成、用于完成一个特定功能的一个过程；

原语在一个操作中的所有动作不可分割。

管理功能：

进程管理：调度、创建、同步等
存储器管理
设备管理

2.6.3 进程创建——进程图

定义：用于描述进程家族关系的有向树。

与前趋图的区别：

含义不同：有向树/有向无环图；
执行时处理不同：进程图父子进程可同时执行，前趋图父子不可并发执行（即前趋图代表的是执行顺序，进程图代表的是父子关系）。

引发进程创建的事件：

用户登录
作业调度
提供服务
应用请求

创建完成的工作：

申请空白PCB
初始化PCB
为新进程分配资源
将新进程插入就绪队列

2.7 线程

2.7.1 概述

定义：

线程是进程中的一个实体，是能被系统（处理机）独立调度和分派的基本单位。在同一进程中，线程的切换不会引起进程切换。线程共享进程的资源，自己不拥有。线程也称轻型进程（Light-Weight Process），进程也称重型进程（Heavy-Weight Process）。线程的概念是由微内核方法引入的。

组成：
- 线程ID
- 寄存器集合
- 程序计数器
- 栈
类型：
- 内核支持线程KST：
又叫内核线程，由内核管理，内核空间里为每个内核支持线程都设置了一个线程控制块（TCB），并通过TCB感知和控制线程。
- 用户级线程ULT：
又叫用户线程，对该类线程的创建、切换由用户完成，不利用系统调用。系统未建立该线程的控制块，不知道其存在。

2.7.2 多线程的优点

系统开销小
响应度高：只需要阻塞部分线程，提高了用户的响应
资源共享：默认共享所属进程的内存和资源
多处理器体系结构的利用

Chapter 3.进程调度

3.1 调度的类型

高级调度(作业调度)：按照一定的算法从后备作业队列中选择满足条件的作业，分配一定资源，创建PCB，入主存就绪队列；
中级调度(内存调度)：将在主存中长期得不到执行的进程，按照一定的算法入盘交换区（先由内存调至外存），满足执行条件后再入主存；
低级调度(进程调度)：按照一定的算法从就绪队列中选择满足条件的进程，分配CPU运行。分抢占/非抢占两种形式。低级调度算法简单，目的是使内存中的内存不至于太多，不浪费使用CPU资源的时间。

3.2 调度方法选择准则

3.2.1 面向用户（4准则）

==响应时间==
- 请求传到CPU延时
- CPU执行时间
- 结果回传延时
==周转时间==
- 作业从提交到完成所经过的时间，包括后备队列延时、就绪队列延时、CPU执行时间、等待I/O时间。

==截止时间保证==：开始/完成截止时间
==优先权准则==

3.2.2 面向系统（3准则）

==系统吞吐量==：单位时间内系统所能处理的任务数越多越好
==CPU利用率==
==各类资源的平均利用==

3.3 调度算法

Process	Burst Time
$P_1$	24
$P_2$	3
$P_3$	3

假定进程都是在第 $0$ 秒到达，顺序如下：$P_1$ , $P_2$ , $P_3$。试计算采用各种算法的平均周转时间和平均等待时间。

进程调度算法中，若算法选择不当，会出现进程长期等待的问题。

3.3.1 先来先服务FCFS

First Come First Serve，思想是选择最先进入后备/就绪队列的作业/进程，入主存/分配CPU。

优点：简单、易于实现；公平；
缺点：平均等待时间长；短作业不利（使用CPU时间少，等待时间长）；紧迫型作业不利。

对于题干，

(1) 平均周转时间： ((24-0)+(27-0)+(30-0))/3=81/3=27

(2) 平均等待时间：((24-0-24))+(27-0-3)+(30-0-3))/3=51/3=17

3.3.2 短作业优先SJF

Shortest Job First，思想是选择后备/就绪队列中执行时间最短的作业/进程，入主存/分配CPU。

优点：平均等待时间最小；系统吞吐量增加（各调度策略中的吞吐量最高）；

缺点：长作业不利（长作业饿死现象）；需要知道每个作业所需的执行时间。

对于题干，

(1) 平均周转时间： ((30-0)+(3-0)+(6-0))/3=39/3=13

(2) 平均等待时间：((30-0-24))+(3-0-3)+(6-0-3))/3=9/3=3

3.3.3 时间片轮转RR

思想是设置使用CPU时间长度（时间片time slice），就绪队列中的进程依次轮流分配一个时间片的CPU。分时系统中的进程调度算法通常采用时间片轮转法。

优点：平均响应时间短；

缺点：性能依赖时间片的大小。

当时间片用完而暂停运行时，进程状态应从运行态变为就绪态（而非进入等待队列/阻塞状态）。

对于题干，

(1) 平均周转时间：((30-0)+(7-0)+(10-0))/3=47/3 ≈ 15.7

(2) 平均等待时间：((30-0-24))+(7-0-3)+(10-0-3))/3=17/3 ≈ 5.7

3.3.4 优先权调度Priority

思想：选择优先权最高的后备/就绪队列的作业/进程，入主存/分配CPU。

类型：抢占式、非抢占式；

优先权类型：静态优先权、动态优先权。

抢占式静态优先权算法可能引起进程长时间得不到运行。

优点：能处理实时事件（提高对紧迫型任务的响应度）。

进程	到达时间	运行时间	优先权
$P_1$	0	24	4
$P_2$	2	3	2
$P_3$	3	3	3
$P_4$	4	7	1

试计算采用抢占式优先权算法的平均周转时间和平均等待时间。

(1) 平均周转时间：((37-0)+(12-2)+(15-3)+(11-4))/4=66/4=16.5

(2) 平均等待时间：((37-0-24))+(12-2-3)+(15-3-3)+(11-4-7))/4=29/4=7.25

3.3.5 高响应比优先HRRN

Highest Response Ratio Next，思想：选择响应比最高的后备/就绪队列的作业/进程，入主存/分配CPU。

响应比 $Rp =1+(等待时间/要求运行时间) >1$

在该算法中，优先级动态变化，开始是短作业进入进程，随着时间的推移，长作业等待时间逐渐增加，响应比变大，转而长作业的优先级变高。

3.3.6 多级队列调度

Multilevel Queue

思想：系统设置多个就绪队列，分配不同优先权（节省选的时间），先调度优先权高的进程，只有高优先权队列为空时才调度低一级优先权队列中的进程。

3.3.7 多级反馈队列

Multilevel Feedback Queue

思想：

设置多个就绪队列，每队分配不同的优先权；

各队规定一时间片，并各队列随着优先权的降低时间片逐渐增大；

新入就绪队列的进程先入高优先权队列，按FIFO执行规定时间片，未完成，入下一级队尾；

高优先权队列为空，执行次一级队列进程…；

若有新入就绪队列的进程，中止低优先权队列进程执行。被中止进程入本队队尾；

最后一级队列采用时间片轮转；

响应比 $Rp$：$Rp=1+(等待时间/要求运行时间)$。

[例]下列每对调度准则在何种情况下会发生冲突：

CPU利用率和响应时间：若上下文切换所产生的系统开销减小，CPU利用率就会增加，但上下文切换执行次数减小会导致进程平均效应时间减小。

平均响应时间和最大等待时间：可以通过短作业优先来减小平均周转时间，但会导致长作业长时间处于等待状态，从而增加他们的等待时间。

3.4 实时系统调度

调度要求：

提供必要的调度信息
- 任务就绪时间
- 开始/完成截止时间
- 处理所需时间
- 资源要求
- 优先级
调度方式：抢占式
有较强的中断处理机构
具有快速任务分配机制，任务切换开销小

注：

当若干任务是可调度时，可得出结论：$\left. {\sum\limits_{i = 1}^{n}\frac{R_{i}}{T_{i}}} \leq 1\rightarrow n\left( 2^{\frac{1}{n}} - 1 \right) \right.$（$R_{i}$ 为运行时间，$T_{i}$ 为周期）。

3.5 多核系统调度

进程调度与系统结构相关：

同构型系统（系统处理能力一致）：静态分配、动态分配、自调度
异构型系统：主从式

常见调度方式：

自调度Self Scheduling
成组调度Gang Scheduling：同种作业分配仅在一组执行（针对保存现场的问题），减少调度频率。
专用处理机分配

注：

进程调度中“可抢占”和“非抢占”两种方式，可抢占式系统的开销更大。

[解释]可抢占式调度是严格保证任何时刻，让具有最高优先权的进程占有处理机运行，因此增加了处理机调度的时机，引起为退出处理机的进程保留现场，为占有处理机的进程恢复现场等时间(和空间)开销增大。

Chapter 4.进程同步和通信

4.1 进程同步的概念

进程间的关系：

间接制约：互斥关系（进程共享资源）
直接制约：同步关系（进程之间存在联系——接力赛）

进程同步：

两个进程所表示事件的发生有着某种时序上的关系。

临界资源（Critical Resource）：

一次仅允许一个进程使用的资源，如慢速设备、共享变量、数据结构、缓冲区等。

多道系统中，为保证进程并发执行且结果确定，必须互斥使用临界资源。

临界区：

定义：进程中访问临界资源的代码段。
使用原则：互斥使用，先申请、判断。
临界资源的循环进程结构：

while(true){
    entry section;            // 进入区，作判断
    critical section;         // 临界区
    exit section;             // 退出区
    remainder section;        // 剩余区
}

4.2 进程同步机制应遵循的原则

空闲让进
忙则等待
有限等待：任何进入临界区的进程将会等待有限时间
让权等待：放弃CPU时间，即：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

忙等，即进程在循环等待中，同时还在不断竞争处理器(如while循环)；忙等是可以消除的，可以通过阻塞等待的进程，然后在合适的时候唤醒该进程。

4.3 解决进程互斥问题

4.3.1 软件方法

（1）==设置标志位 flag[i],flag[j]==

标志 $P_{i}$ 和 $P_{j}$ 进程是否在临界区，初值为 false。

Pi: while(true){
      while(flag[j]) {no operation};
      flag[i]="true";                // 进入区
      critical section;              // 临界区
      flag[i]="false";               // 退出区
      remainder section;             // 剩余区
    }

（2）==设置整型变量 turn==

标志 turn 表示哪个进程可进入临界区，flag[i] 和 flag[j] 表示哪个进程要进入，初值为 true。

Pi: while(true){
      while(turn!=i) {no op};   	 // 进入区
      critical section;         	 // 临界区
      turn=j;                        // 退出区（"谦让动作"）
      remainder section;             // 剩余区
}

缺点：当 $P_j$ 进程还没进去，而 $P_i$ 进程又想进入却发现无法进入，违背“空闲让进”的规则。

（3）==Peterson算法==

设置 turn 表示哪个进程可进入临界区，flag[i] 和 flag[j] 表示哪个进程要进入，初值为 true。

Pi: while(true){
     flag[i]=true;					  // 表示我（i）想使用该资源（表达意愿）
     turn=j;						  // 愿意优先让j使用（表示谦让）
     while(flag[j] && turn==j) {no op}  // 如果j想用而且是自己（i）最后表达的谦让，则等待，否则i先执行
     critical section;         			// 临界区
     flag[i]=false;                 	// 退出区
     remainder section;             	// 剩余区
}

Pj: while(true){
     flag[j]=true;
     turn=i;
     while(flag[i] && turn==i) {no op}   
     critical section;        	   		// 临界区
     flag[j]=false;                		// 退出区
     remainder section;           		// 剩余区
}

缺点：仍未遵循让权等待的原则（一直 while 循环消耗资源）。

4.3.2 硬件方法

特点：指令操作只需一个指令周期就能完成（原子性的操作）

4.3.2.1 检测和设置指令TS

TS又称Test-and-Set。

boolean TS (boolean *target) {
    boolean rv = *target;	// 存放lock原来的值
    *target = TRUE;			// 无论之前是否被加锁，都将lock设为true
    return rv:       		// 返回lock原来的值，若lock原来未加锁即可进入临界区，否则等待
}

while (true) {
    while (TS(&lock))   {no op}		 // do nothing
    critical section;				// 临界区
    lock = FALSE;					// 退出区，将lock解锁，使别的进程可以进行访问
    remainder section;				// 剩余区
}

[例] 利用 TS 指令实现多处理器环境中的 wait() 和 signal() 信号量操作。

int guard = 0;
int semaphore value = 0;

wait(){
    while(TS(&guard) == 1);
    if(semaphore value == 0){
        //automatically add process to a queue of processes waiting for the semaphore and set guard to -
    }else{
        semaphore value--;
        guard=0;
    }
}

signal(){
    while(TS(&guard) == 1);
    if(semaphore value == 0 && there is a process on the wait queue){
        //wake up the first process in the queue of waiting processes
    }else{
        semaphore value++;
    }
    guard = 0;
}

4.3.2.2 Swap指令

void Swap (boolean *a, boolean *b){
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
while (true) {
     key = TRUE;
     while (key == TRUE)	 // 直到lock被设为false，则执行lock交换指令后会使得key为false，使得程序可以进入临界区
       Swap (&lock, &key);
     ......   				// critical section
     lock = FALSE;
     ......   	  	    	// remainder section
}

4.4 信号量机制

4.4.1 信号量机制的一些概念

信号量：信号量是一个变量（整数、记录型变量等），可以用一个信号量来表示系统中某种资源的数量。比如系统中只有一台打印机，就可以设置一个初值为 $1$ 的信号量。

同步原语：P() / wait() 操作、V() / signal() 操作。

注：

信号量每执行一次 P 操作，意味着要求分配一个资源

用 V 操作唤醒一个等待进程时，被唤醒的进程的状态应变为就绪状态

4.4.2 整型信号量机制

semaphore  s;
wait(s) :   {  while (s<=0) {no op;}
               s--;
            }
signal(s):  {  s++;  }

整型信号量的分类：

==二元信号量==：实现互斥。s 的取值为 $1$ 和 $0$，初值为 $1$；（mutex：互斥元，如对同一个缓冲区进行操作应采用互斥元进行操作）
==一般信号量==：描述前趋关系。用于一般同步，初值为共享资源初始数量。

在实际解决进程同步问题时，可通过前趋图表示出各个进程的前趋关系，然后将各个操作封装，封装后的程序可以并发执行。如下例：

描述 (a+b)*(c-d)-e/f：

p1:a+b, p2:c-d, p3:e/f, p4:p1*p2, p5:p4-p3。画出前趋图：

semaphore S1,S2,S3,S4 = 0;
{--
	{P1;V(S1);}					// V表示释放信号
    {P2;V(S2);}
    {P3;V(S4);}
    {P(S1);P(S2);P4;V(S3);}		 // P(S1),P(S2)为wait信号
 	{P(S3);P(S4);P5;}
--}

[注] -- 应画在 { 上，表示并发。

4.4.3 记录型信号量机制

引入目的：克服整型信号量机制存在的“忙等”（Busy waiting）现象，提高资源利用率。引入结构体 semaphore：

typedef struct
{
   int value;
   struct process *list;   // list是进程列表
}semaphore;

P(semaphore s):
{  
    s.value--;
    if (s.value < 0) {
       insert(caller,s.list);
       block(caller); 
    }
}

若 s.value < 0，表示系统已无该类资源，申请者阻塞，其中 |s.value| 表示该信号量上阻塞的进程数。

V(semaphore s):
{  
    s.value++;
    if (s.value <= 0) {
        remove(s.list, id);
        wakeup(id);
    }
}

若 s.value <= 0，表示尚有进程因等待 S 代表的资源而处于阻塞状态，所以应唤醒其中之一。

4.3.4 AND信号量集机制

称为同时wait操作，即 swait（simultaneous wait），目的是避免死锁。在这里，要么把进程在整个运行过程中所请求的资源全部分配到进程（进程使用完成后一起释放），要么一个也不分配。

死锁原因：

有两个进程A、B。两个临界资源D、E，互斥信号量(初值为1)分别是 Dmutex、Emutex。

按下面执行次序，A获得了D等待E，B获得了E等待D，就处于了僵持状态，无外界干预，A、B就陷入了死锁状态。共享资源越多，进程死锁可能越大。

process A: wait(Dmutex)；于是 Dmutex=0

process B: wait(Emutex)；于是 Emutex=0

process A: wait(Emutex)；于是 Emutex=-1，A 阻塞

process B: wait(Dmutex)；于是 Dmutex=-1，B 阻塞

swait(semaphore s[n]):
{ 
    while(true)
    {
        if ((s[1]>=1) && (s[2]>=1) && …… && (s[n]>=1)) {
            for (i=1; i<=n; i++)
            {
                s[i]=s[i]-1;		//访问到资源，全部减1，然后退出，否则等待
                break;
            }
        }
    }
}
ssignal(semaphore s[n]):
{  
    for (i=1; i<=n; i++)
        s[i]=s[i]+1;
    //唤醒等待s[i]的进程;
}

4.3.5 一般信号量集机制

一次可给进程分配多种临界资源，且同类临界资源一次可分配多个。

swait(semaphore s[n],int t[n], int d[n]):
{
    if ((s[1]>=t[1]) && (s[2]>=t[2]) && …… && (s[n]>=t[n])) {
        for (i=1; i<=n; i++)
          s[i]=s[i]-d[i];
    }
    else
         insert (caller, s[i].list);  //插入到不满足的队列中
}
ssignal(semaphore s[n],int d[n]):
{  
    for (i=1; i<=n; i++)
       s[i]=s[i]+d[i];
    //唤醒等待s[i]的进程;
}

特殊情况：

swait(s,d,d): 不设下限，此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不予分配；
swait(s,1,1)：就是wait(s)；
swait(s,1,0): 可控开关（当S≥1时,允许多个进程进入临界区；当S=0时禁止任何进程进入临界区）。

[例]设有一个售票厅，可容纳100人购票。如果厅内不足100人则允许进入，进入后购票，购票后退出。如果厅内已有100人，则在厅外等候。试问：

（1）购票者之间是同步还是互斥；

（2）用P、V操作表达购票者的工作流程。

[解](1)互斥；

(2)

semaphore empty=100,mutex=1;
{
    P(empty);
	P(mutex);
	//进入购票区购票，购票后退出
	V(mutex);
	V(empty);
}

4.5 经典进程同步问题

4.5.1 生产者-消费者问题

特点：一类临界资源，多个，每个临界资源必须互斥使用；

典型示例：有限缓冲区的使用。

【问题描述】

若干生产者、消费者，共享N个缓冲区；

生产者：每次产生一个数据，放入到一个空缓冲区。若无空缓冲区，则阻塞。

消费者：每次从有数据的缓冲区取一个数据，进行使用；若无满缓冲区，则阻塞。

【分析】

==同步==：若所有缓冲区皆空，消费者阻塞等待生产者生产；若所有缓冲区皆满，生产者阻塞等待消费者消费。设置一般信号量：

empty 表示现有空缓冲区数，初值为M;

full 表示现有满缓冲区数，初值为0。

==互斥==：生产者、消费者对同一个缓冲区的操作必须互斥。设置互斥信号量 mutex，初值：

生产者行为：产生数据，将数据存入到缓冲区；

消费者行为：从缓冲区取出数据，消费数据；

定义变量：buffer[n]、in 和 out 指针。

【注】由于循环队列的特性，实际上会牺牲一个存储单元（必有1个单元为空），队列已满的条件为队尾指针的下一个位置是队头，即(Q.rear + 1) % MaxSize == Q.front。

伪代码实现方案如下：

semaphore mutex =1,empty=n, full=0;
int buffer[n];
int in=out=0;
{--
	Producer: 
        while (true) {
           produce an item in nextp;
           wait(empty);
           wait(mutex);
           buffer[in]=nextp;
           in=(in+1) mod n;
           signal(mutex);
           signal(full);
          }
	Consumer: 
        while (true) {
           wait(full);
           wait(mutex);
           nextc=buffer[out];
           out=(out+1) mod n;
           signal(mutex);
           signal(empty);
           consume the item;
        }
--}

【例】假设有3个并发进程P，Q，R，其中P负责从输入设备上读入信息，并传送给Q，Q将信息加工后传送给R，R负责打印输出。进程P，Q共享一个有m 个缓冲区组成的缓冲池；进程Q，R共享一个有n个缓冲区组成的缓冲池（假设缓冲池足够大，进程间每次传输信息的单位均小于等于缓冲区长度），请写出满足上述条件的并发程序。

【分析】设置六个信号量 empty1、full1、mutex1、empty2、full2、mutex2，

empty1 表示P、Q共享的缓冲池中空缓冲区数，初值为m；

full1 表示P、Q共享的缓冲池中中满缓冲区数，初值为0；

mutex1 表示P、Q对同一缓冲区操作的互斥信号量，初值为1；

empty2 表示Q、R共享的缓冲池中空缓冲区数，初值为n；

full2 表示Q、R共享的缓冲池中中满缓冲区数，初值为0；

mutex2 表示Q、R对同一缓冲区操作的互斥信号量，初值为1；

同步描述为：

empty1,empty2,full1,full2,mutex1,mutex2:semaphore=m,n,0,0,1,1；
P: {
    while(1){
        read a message;
        wait(empty1);
        wait(mutex1);
        store to buffer1;
        signal(mutex1);
        signal(full1);
	}
}

Q: {
    while(1){
        wait(full1);
        wait(mutex1);
        get from buffer1;
        signal(mutex1);
        signal(empty1);
        work with massage;
        wait(empty2);
        wait(mutex2);
        store to buffer2;
        signal(mutex2);
        signal(full2);
    }
}

R: {
    while(1){
        wait(full2);
        wait(mutex2);
        Get from buffer2;
        print;
        signal(mutex2);
        signal(empty2);
	}
}

4.5.2 读者-写者问题

【问题描述】

若干读者、写者，共享文件/数据；

读者：可以同时读数据，不可修改数据。

写者：修改数据，不能同时修改同一份数据，进行修改时读者不能读。

【分析】

采用记录型信号量

互斥：为保证写者进程与其它进程互斥访问共享对象，设置互斥信号量 wmutex，初值：

互斥：由于允许有多个读者，为了解目前的读者数量，设置一读者计数变量 readcount。多个读者都对 readcount 进行操作，须设置对其操作的互斥信号量 rmutex。

**[注]**每当一个读者开始读文件时，必须修改 readcount 变量。因此需要一个互斥对象 rmutex 来实现对全局变量 readcount 修改时的互斥。

读者行为：读之前 readcount 加 $1$，读数据，读完，readcount 减 $1$；

写者行为：修改数据。

==【读者优先方案】==

要等所有读进程执行完后，使得信号量 wmutex 为 $1$ 时，才能访问临界资源。

semaphore rmutex = wmutex=1; int readcount = 0
{--
     reader: 
       while (true) {
             wait(rmutex);
             if (readcount==0) wait(wmutex);
             readcount++;
             signal(rmutex);
             reading;
             wait(rmutex); 
             readcount--;
             if (readcount==0) signal(wmutex);        
             signal(rmutex);
          }
      writer: 
         while (true) {
             wait(wmutex);
             writting;
             signal(wmutex);
          }
--}

==【写者优先方案】==

semaphore rmutex = wmutex = wwmutex = 1; int readcount = writecount = 0
{--
    reader: 
      	 while (true) {
          	 while(writercount>0) {do nothing}
          	 wait(rmutex);
             if (readcount==0) wait(wmutex);
             readcount++;
         	 signal(rmutex);
             reading;
         	 wait(rmutex); 
             readcount--;
             if (readcount==0) signal(wmutex);
          	 signal(rmutex);
          }
	writer: 
         while (true) {
             wait(wwmutex);
             writercount++;
             signal(wwmutex);
             wait(wmutex);
             writting;
             wait(wwmutex);
             writercount--;
             signal(wwmutex);
             signal(wmutex); 
         }
--}

4.5.3 哲学家进餐问题

【问题描述】

五个哲学家同座一张圆桌，每人一个碗，左右各一只筷子；

哲学家的行为：思考-吃饭-思考……。

前提：只有拿到左右两只筷子才开始吃饭。

semaphore chopstick[0……4]=1
{--
    Pi: while (true) {
      	   wait(chopstick[i]);
    	   wait(chopstick[(i+1) mod 5]);
           eating;
      	   signal(chopstick[i]);
     	   signal(chopstick[(i+1) mod 5]);
           think;
       }
--}

防止死锁的解决方案：

最多允许 $4$ 个哲学家同时坐在桌子周围；
仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；（提高资源利用率）
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之；
把哲学家分为三种状态，思考，饥饿（加一状态），进食，并且一次拿到两只筷子，否则不拿。

4.6 管程机制

4.6.1 管程组成

信号量机制的不足：
- critical section、entry section和exit section都由用户编写；
- 信号量原语分散在各程序代码中由进程执行，系统无法有效控制、管理；
- wait 和 signal 操作的错误使用，编译程序和操作系统都无法发现、纠正，可导致死锁。
1971年，Dijkstra引入管程机制，即“秘书”进程：
- 临界资源的同步操作集中；
- 访问需先报告“秘书”；
- “秘书”实现进程同步，从而保证互斥使用；
- 管程有生命周期（与操作系统相同）。
管程组成：
- 局部于管程的共享变量说明 （数据结构）；
- 对该数据结构进行操作的一组过程；
- 局部于管程数据的初始化语句。

typedef monitor {
    variable declarations;
    condition x,y;
    void P1(...) {... ...};
    void P2(...) {... ...};
    ... ...
    void Pn(...) {... ...};
    // initialization code
} monitor-name

条件变量：
- 用条件变量类型 condition 来定义条件变量，在管程中声明条件变量；
- 每个条件变量对应一个等待队列，进程通过管程请求临界资源未满足时，管程将其入等待队列；
- 当进程通过管程请求临界资源未满足时，调用同步原语 wait() 将其放入等待队列；
- 当进程可以访问临界资源时，管程调用同步原语 signal() 唤醒等待进程。

【例1】利用管程解决生产者-消费者问题。

共享变量：缓冲区 buffer[n]，指针 in、out；对产生的数据进行计数 count；

条件变量：

若没有空缓冲区，需要阻塞生产者进程 ——notfull（不满条件）

若全部都是空缓冲区，则需要阻塞消费者进程——notempty（不空条件）

局限于管程内的操作：

put(data)：检查是否全满，若不满，放入，数据计数 count $+1$；
get(data)：检查是否全空，若不空，取出，数据计数 count $-1$。

Monitor PC{ 
    int in,out,count; 
    item buffer[0..n-1];    
    condition  notfull,notempty;
    put(item) {
        if (count>=n) notfull.wait;		// 阻塞
        buffer(in)=nextp;
        in=(in+1) mod n;
        count++;
        if (notempty.queue) 
            notempty.signal; 			// 唤醒
    }
    get(item) {
        if (count<=0)  notempty.wait;
        nextc=buffer(out);
        out=(out+1) mod n;
        count--;
        if (notfull.queue)
            notfull.signal;  
    }
}

Producer() {		// 生产者进程
    while (true) {
            produce an item in nextp;
            PC.put(item); 
       }
}

Consumer() {		// 消费者进程
    while (true) {
        PC.get(item);
        consume the item in nextc;
    }
}

4.6.2 管程和进程的比较

设置目的不同：
- 进程：并发、共享
- 管程：管理临界资源
系统管理的结构不同：
- 进程：PCB
- 管程：等待队列
管程是OS固有成分，有生命周期（与操作系统相同）
管程被进程调用。

注：

信号量可以并发，并发量是取决于 s 的初始值，而管程则是在任意时刻都是只能有一个

信号量的 P 操作在操作之前不知道是否会被阻塞，而管程的 wait 操作则是一定会被阻塞

4.7 进程通信

IPC(Inter-Process Communication)：协作进程间用来交换数据与信息的机制。

4.7.1 进程间通信类型

分类：==管道、共享存储器、消息队列、信号量、套接字==

低级通信：

交换信息量少，仅是数据和状态的变化
通信由程序员完成

高级通信：

交换信息量大
系统提供高效简捷的传输命令
高级通信类型
- 共享存储器系统（Shared-Memory System）——共享数据结构、共享存储区
- 消息传递系统（Message Passing System）
- 管道通信（Pipe Communication）

4.7.2 消息传递系统

利用系统提供的通信原语，以消息或报文为单位进行信息交换。

4.7.2.1 直接通信方式

进程直接把消息发送给目标进程
通信原语
- Send(Receiver, message);
- Receive(Sender, message);

[例]生产者-消费者问题的直接通信方式。

Producer() {
   produce an item in nextp;
   Send(C, nextp); 
}

Consumer() {
   Receive(P, nextc);
   consume the item in nextc;
}

4.7.2.2 间接通信方式(信箱)

进程间通过某种共享的数据结构（如信箱）进行通信。
通信原语
- 信箱的创建、撤销；
- 消息的发送和接收
  - Send(mailbox,message)
  - Receive(mailbox,message)
信箱的类型（根据创建者和共用关系不同进行分类）
- 私用信箱(Private Mailbox)：一对一，单向通信链路
- 共用信箱(Public Mailbox)：由操作系统创建
- 共享信箱(Shared Mailbox)：多对多，由某进程创建

进程间用信件传递信息时，信件中应含有信箱名。

4.7.2.3 消息传递系统其他概念

通信链路问题：

显式建立/隐式建立
点-点/多点链接
单向链路/双向链路
无容量/有容量链路（有无缓冲机制）

消息格式问题：

消息头：发送和接收进程名、消息长度、类型（与所处环境有关）
消息正文

==进程的同步方式==（三种）：

发送者、接收者进程阻塞（紧密同步）
发送者不阻塞（一直发）、接收者阻塞（反馈信息）

发送者、接收者都不阻塞

特点：利用率最高，需缓存机制（排序后才可接收）

消息缓冲队列通信机制：

4.7.3 管道通信

管道通信是UNIX系统的重要特色之一。管道是指用于连接一个读进程和一个写进程，以实现进程间通信的共享文件，又叫Pipe文件。
进程直接把消息发送给目标进程的命令格式为：Command1 | Command 2（管道：|）
功能：Command1 进程以字符流的形式向管道发送大量的数据，Command2 进程则从管道接收数据。两进程实现单向、同步、互斥运行。
- 单向：Command1 只能发送；…
- 同步：管道满时，Command1 等待；…
- 互斥：同一时刻，只能有一个进程对管道操作。

Chapter 5.死锁

5.1 死锁(Deadlock)概述

5.1.1 死锁定义

多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程将永远无法推进。

5.1.2 死锁产生的原因及必要条件

产生原因：

竞争资源
进程推进顺序不合理

必要条件：

互斥条件（Mutual exclusion）
占有并等待（Hold and wait）
不可抢占（No preemption）
环路等待（Circular wait）

注：

出现环路不一定发生死锁。只有在每个资源实体只有一个的情况下，出现环是出现死锁的充要条件。

5.2 资源分配图

由节点集合 $V$ 和边集合 $E$ 组成的有向图 $G=(N,E)$，用于表示某时刻系统资源与进程之间的状态。

**节点集合 $V$**：

进程集合 $P={P_{1},P_{2},…, P_{n}}$ ；
资源类型集合 $R={R_{1}, R_{2},…, R_{m}}$，其中黑点数表示资源个数。

**边集合 $E$**：

申请边$P_{i} →R_{j}$ ——由进程 $P_{i}$ 指向资源 $R_{j}$ 的有向边，表示还要请求；
分配边$R_{j}→P_{i}$——由资源 $R_{j}$ 指向进程 $P_{i}$ 的有向边，表示已经分配。

5.3 死锁的处理办法

设计无死锁的系统（系统运行前或运行中）
- 死锁预防（破坏死锁存在的四个必要条件）
- 死锁避免（保证系统随时处于安全状态）
允许系统出现死锁，提供处理方法排除（系统或进程运行后）
- 死锁检测（通过化简资源分配图）
- 死锁恢复（通过破坏死锁的必要条件）
忽视死锁

5.3.1 死锁的预防

死锁的预防指系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。

==预先静态分配法==：

破坏“占有并等待”条件
思想：作业调度时，仅将系统能满足运行所需全部资源的作业调入内存运行。
缺点：
- 资源利用率低
- 作业周转时间长，不利于“并发”

==有序资源使用法==：

破坏“环路等待”条件
思想：将系统中所有临界资源分配唯一的序号，进程严格按序号递增次序申请使用资源。在任何一个时刻，总有一个进程拥有的资源编写是最大的，那这个进程申请之后的资源必然畅通无阻，因此不可能出现所有进程都阻塞的死锁现象。
如果进程需要同一资源类型的多个实例（也就是序号相同的资源），则必须对它们一起进行申请；如果进程后面又想申请序号低的资源（比如5），那就必须把现在拥有的序号为5及其以上的资源全部释放。
例如：输入机=1，打印机=2，穿孔机=3，磁带=4。

A：R2…R1（在这里A需要重编译，优先调用R1，浪费R2资源【R2不能利用】）

B：R1（已运行）…R2
缺点：
- 临界资源的顺序定义随时变化（很难定下顺序）
- 为资源编号限制新设备的增加
- 资源的排序会占用系统开销

5.3.2 死锁的避免(银行家算法)

基本思想：在执行过程中，采用一些算法规避不安全状态（检查资源的分配情况），确保系统始终处于安全状态。

系统的安全状态：

安全状态的定义：系统按某一顺序$<P_{2},P_{1},P_{3}>$(安全序列)为每个进程分配所需资源，使每个进程都可顺序完成，则称系统在该时刻处于安全状态。
要考虑的因素为：最大需求、目前已经分配的资源、目前可用的空闲资源。当一个进程获得了它运行所需的最大资源后，将释放资源供给其他进程使用。
$m$ 个进程共享 $n$ 个同类型资源，每个进程至少 $1$ 个资源，保证不死锁的条件是：$\left. {\sum\limits_{i = 1}^{m}{\left( {R_{P_{i}} - 1} \right) + 1}} \leq n\rightarrow总需求量{\sum\limits_{i = 1}^{m}R_{P_{i}}} \leq n + m - 1 \right.$

例如，$5$ 个相同类型资源组成的系统，系统中有 $3$ 个进程，每个进程最多需要 $2$ 个资源，该系统不会发生死锁。为每个进程先分配一个资源，然后再给其中任意一个进程分配一个资源，则一个进程将得以运行，且运行完毕后将释放这两个资源供给其他进程使用。在这个问题中最少需要 $4$ 个进程即可保证不死锁。

银行家算法描述如下：

数据结构：
- 可用资源向量 Available[m]：是一个数组，表示现在系统中每个类型的资源还有多少可用的资源
- 最大需求矩阵 Max[n,m]：表示某进程最多需要多少某资源，一行代表一个进程，一列代表一个资源
- 分配矩阵 Allocation[n,m]：表示系统中现在某类资源分配给某进程的数量
- 需求矩阵 Need[n,m]：表示现在进程中尚需的各类资源数
资源请求处理：

设 request 是进程 P 的请求向量，request[A] = K 表示进程 P 需要 A 类资源 K 个。当 P 发出资源请求后，系统按照以下步骤进行检查。
1. 如果 request[A] 的值小于 need[P,A]，也就是说如果现在请求的数量小于 need 矩阵中规定的它所需要的数量，那么就转到步骤 2 ；否则认为出错，因为他所请求的数量已经超过了他所宣布的最大值。
2. 如果 request[A] 的值小于 available[A]，也就是说请求的值小于现在系统中有的值，则转向步骤 3 ；否则表示资源尚不足，进程 P 需要等待。
3. 系统试探着把资源分配给进程 P，并修改下面数据结构中的值：
- 更新可用：Available = Available - request
- 更新已分配：Allocation[P,A] = Allocation[P,A] + request[A]
- 更新所需：Need[P,A] = Need[P,A] - request[A]
1. 系统执行安全性检测，检查此次资源分配后，系统是否处于安全状态，若安全才将资源分配给进程 P；否则此次的试探分配作废，恢复原来的资源分配状态，让进程 P 等待。
安全性检测算法：
1. 初始时安全序列为空；
2. 从 Need 矩阵中找到符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤 4。
3. 进程 P 进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，故应执行 Available = Available + Allocation[P]，其中 Allocation[P] 表示进程 P 在 Allocation 矩阵中对应的行，返回步骤 2 。
4. 若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态。

银行家算法例题如下。

5.3.3 死锁的检测

死锁检测的2个前提：

保存有关资源的请求和分配信息
提供一种检测系统是否已进入死锁的算法

==资源分配图简化算法==：

由进程指向资源的边是请求边，由资源指向进程的边是分配边。当资源包中的可用资源数大于0，则响应请求，画出分配边（删去请求边），当一个进程没有请求边时，即可孤立。
如果化简后所有的顶点都成了孤立点，则称该图可完全化简；否则称该图是不可完全化简的。
若经过化简后还存在非孤立点，则非孤立点的进程处于死锁状态。

资源分配图简化算法示意图

5.3.4 死锁的恢复与解除

法1：剥夺资源
- 从一部分进程剥夺资源给其他进程，直到死锁解除；
- 具体方法：一次终止一个进程直到死锁循环被解除，选择终止“代价最小”的进程。
法2：撤销进程

按照不同策略撤销一个或多个进程，回收资源给其他进程，直到死锁解除；具体考虑有以下几种：
- 选择一个牺牲品：确定抢占顺序以使代价最小。
- 回滚：抢占资源，将进程回滚到某个安全状态。
- 饥饿：防止进程饥饿，让进程有限地被选定。

Chapter 6.内存管理

6.1 内存管理的基本概念

6.1.1 内存管理的功能

主存空间的分配与回收
地址转换与重定位
存储保护与共享
存储扩充：使用虚拟存储器，扩充主存空间。CPU能直接访问的存储设备只有内存和寄存器，其中内存访问需要占用几个CPU时钟周期，寄存器则内置在CPU中，访问只需要只用1个CPU时钟周期。

6.1.2 地址的相关概念

逻辑地址：虚地址，用户程序中使用的地址
物理地址：系统中内存单元的地址
==重定位==（Relocation）：将相对地址变为绝对地址的过程，即将逻辑地址转变为内存的物理地址
MMU：内存管理单元，实现重定位的硬件设备

6.2 地址绑定

6.2.1 地址绑定的时期

指令和数据绑定到存储器地址可在下面任意时期进行：

编译时期：符号绑定，各 Obj 模块的相对虚拟地址空间 –>统一的虚拟地址空间
装入时期：程序装入内存
执行时期：通过 MMU 将虚拟地址空间 $\rightarrow$ 物理地址空间

链接完成的功能：

由链接程序（Linker）将编译后形成的一组目标模块（程序段），以及它们所需要的库函数链接在一起，形成一个完整的装入模块。

6.2.2 重定位的方式

静态重定位：程序入主存之前由编译/链接程序完成重定位，入主存可立即执行。
- 场景：管程（系统固有成分，常驻内存）、嵌入式环境（如刷卡）
- 优点：操作简单，不需要额外的机构或操作。
- 缺点：
  - 程序不能进出（程序一旦装入后地址就不可再改变，程序也不可以再移动，不利于内存空间的有效使用）
  - 需一次加载所有代码
动态重定位：程序入主存之前不进行重定位，入主存执行到与地址相关项时，再进行重定位。
- 实现方法：
  
  当某个进程取得CPU控制权时，操作系统应负责把该作业程序在主存中的起始地址送入重定位寄存器中，每次访问存储器时，重定位寄存器中的内容将被自动加到逻辑地址中去，经该种变换后执行结果是正确的。
- 优点：
  - 程序占用的内存空间可变，能提高内存的利用效率
  - 容易实现不同程序对同一副本的共同使用
- 缺点：
  - 执行速度变慢，占用CPU时间
  - 需要额外的硬件支持

注：

静态重定位是在作业的装入过程中进行的，动态重定位是在作业的执行过程中进行的；

链接可以分为静态链接和动态链接，装入时链接叫装入时动态链接（在作业装入时进行重定位，属于静态重定位）；

在编译时静态重定位就是已知程序进入内存后的起始地址然后再编译。一般现在的操作系统不会采用这种方式，链接时静态重定位也是在链接的时候就确定了将进入内存的起始地址。

装入和链接方式：

动态运行时装入方式：
- 装入程序按照装入模块中的地址，将程序和数据装入内存，执行时重定位。
- 优点：内存利用率高；大规模程序有利；可通过程序设计来实现；无需操作系统的额外支持；
运行时动态链接方式：
- 将编译后的目标模块及库函数，在程序执行时进行链接。
- **存根程序 stub**：用于指出如何定位适当的内存驻留库程序，或者在程序不在内存时如何加载库
- 特点：可节省内存空间；可用于系统类库的更新（如修改bug）；需要操作系统的支持。

6.3 交换与覆盖技术

6.3.1 交换技术(Swapping)

引入目的：解决由于内存不足而无法同时调入多个作业的问题。
多道程序环境下的交换
- 实现：中级调度
- 类别：进程对换、页/段对换；
对换空间管理
- 外存设置交换区
- 设置数据结构记录外存空间使用情况

6.3.2 覆盖技术(Overlay)

用于解决程序大小超过物理内存总和的问题。
将程序分为多个段（多个模块）。常用的段常驻内存,不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中,调入后就不再调出(除非运行结束)。不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

[注]覆盖、交换的比较：

目的是一样的；

覆盖发生在一个进程中的程序内部没有调用关系的模块之间，代价是程序员手动指定和划分逻辑覆盖结构；交换是内存中程序与管理程序或OS之间发生的，以进程作为交换的单位，需要把进程的整个地址空间都换进换出，对程序员是透明的，开销相对较大。

6.4 连续分配存储管理技术

6.4.1 单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区的低地址存放中断向量、操作系统内核代码，高地址存放设备驱动程序；内存中只能由一道用户程序，用户程序独占整个用户区空间。这种分配方式实现简单，无外部碎片，但有内部碎片，且存储器利用率极低。

6.4.2 固定分区分配

在固定分区分配方式中，操作系统需要建立一个数据结构（分区说明表），来实现各个分区的分配与回收。每个表项对应一个分区，通常按照分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

固定分区分配的优缺点如下：

优点：实现简单，无外部碎片。
缺点：
- 当用户程序太大时，可能所有分区都不能满足需求，此时必须采用覆盖技术解决，但会降低性能
- 会产生内部碎片（每个分区内部存在空闲空间），内存利用率低

6.4.3 动态分区分配

动态分区分配使用空闲分区表，每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。

6.4.3.1 动态分区分配算法

首次适应算法：每次都从低地址以地址递增的次序排列，直至找到第一个大小能满足要求的空闲分区。该算法倾向于优先使用低地址部分空闲区。
循环首次适应算法：为了解决上一个算法导致低地址部分出现很多小的空闲分区，且每次分配查找由于要经过这些分区而增加查找开销。该算法设定一个指针，每次都从指针位置（即上次查找结束的位置）往后查找，直至找到第一个大小能满足要求的空闲分区。该算法能使内存空间中空闲区分布较均匀。
最佳适应算法：从头扫到尾，找到能满足要求且大小最小的（即最合适的）空闲分区。
最坏适应算法：为了解决上一个算法导致留下太多难以利用的小碎片，其在每次分配时优先使用空间最大的空闲分区，使分配后剩余的空闲区不会太小，更方便使用。

下面列出空闲分区表变动的两种情况：

空闲分区大小比申请空间大小大，则分区数量不改变

分区号	分区大小（MB）	起始地址（M）	状态
1	20	8	空闲
2	10	32	空闲
3	4	60	空闲

分区1有进程5申请4MB的内存空间，则空闲分区表变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	16	12	空闲
2	10	32	空闲
3	4	60	空闲

空闲分区大小和申请空间大小相同，则分区数量减一

分区号	分区大小（MB）	起始地址（M）	状态
1	20	8	空闲
2	10	32	空闲
3	4	60	空闲

分区3有进程5申请4MB的内存空间，则空闲分区表变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	20	8	空闲
2	10	32	空闲

6.4.3.2 回收问题

下面列出空闲分区回收时可能发生的四种情况：

回收区的后面有一个相邻的空闲分区，则将该分区的分区大小和起始地址进行改变

分区号	分区大小（MB）	起始地址（M）	状态
1	10	32	空闲
2	14	60	空闲

变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	14	28	空闲
2	14	60	空闲

回收区的前面有一个相邻分区（与上面一种情况同理，起始地址不发生变化）
回收区的前、后各有一个相邻的空闲分区（造成空闲区间减一）

分区号	分区大小（MB）	起始地址（M）	状态
1	20	8	空闲
2	10	32	空闲
3	4	60	空闲

变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	34	8	空闲
2	4	60	空闲

回收区的前、后都没有相邻的空闲分区，则分区数量加一，然后填充信息即可。

6.4.3.3 紧凑技术

动态分区分配无内部碎片，有外部碎片。==外部碎片可以通过“紧凑”技术来解决==。

紧凑技术是通过移动内存中作业，将分散的多个分区合并成一个大的分区；
由于紧凑时，作业要在内存中移动位置，故紧凑技术的前提是采用动态重定位，这种分区分配方式称为可重定位分区分配方式；
动态重定位分区分配的思想是：当作业需进入主存时，若主存每一个可用分区都不能满足要求，而可用分区总和又可满足要求时，首先完成内存的“紧凑”，然后调入。在每个分区都不能满足要求的情况下才紧凑，是因为紧凑操作会耗时，==时间代价较大==。

分区管理方案算法较简单，实现较容易，内存开销较少，存储保护措施简单，但内存使用不充分，存在较严重的碎片问题。

下面章节介绍的都是离散分配存储管理技术。

6.5 分页存储管理(Paging)

6.5.1 基本内容

6.5.1.1 概述

基本思想：逻辑地址空间在内存中可以不连续。
将内存空间分为一个个大小相等的分区（比如每个分区 $4$ KB），每个分区就是一个“==页框==”（Frame，内存物理地址空间按 $2^{n}$ 等分，也即页帧、内存块、物理页面），页框的编号称为页框号，从 $0$ 开始编号。
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“==页==”或“==页面==” 。页面的编号称为页号，也从 $0$ 开始编号。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
页表（PMT）(Page Mapping Table)

通常存在于PCB（进程控制块）中，如图：

页表项占用的字节数的计算：

[例]假设某系统物理内存大小为 $4GB$，页面大小为 $4KB$，则每个页表项至少应该为多少字节？

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）。假设页表中的各页表项从内存地址为 $X$ 的地方开始连续存放，则页号为 $i$ 的页表项的存放地址 = $X+3*i$。
计算机中内存块的数量->页表项中块号至少占多少字节
- 内存块大小 = 页面大小 = $4KB=2^{12}B$，故 $4GB$ 的内存总共会被分为 $2^{32}/2^{12}=2^{20}$ 个内存块，故内存块号的范围应是 $0$ 到 $2^{20}-1$
- 内存块号至少要用 $20;bit$ 来表示，则至少要用 $3B$（ $3*8=24;bit$ ）

6.5.1.2 实现地址转换的方法

实现地址转换的思路：

若要访问逻辑地址 $A$，则要先确定逻辑地址 $A$ 对应的页号 $P$，然后找到 $P$ 号页面在内存中的起始地址（查页表），最后确定逻辑地址 $A$ 的页内偏移量 $W$，则**逻辑地址 $A$ 对应的物理地址 = $P$ 号页面在内存中的起始地址 + 页内偏移量 $W$**。其中：

页号 = 逻辑地址 / 页面长度（除法的整数部分），页内偏移量 = 逻辑地址 $%$ 页面长度（除法的余数部分），则逻辑地址可以表示为：**(页号,页内偏移量)**，或写作 $(P,d)$ 。
由于在计算机内部地址是用二进制表示的，故页面大小设定为 $2$ 的整数幂。假设某计算机用 $32$ 个二进制位表示逻辑地址，则页面大小为 $4KB=2^{12}B=4096B$，则有：（红色 $20$ 位代表页号，黑色 $12$ 位代表页内偏移量）

故如果每个页面大小为 $2^{k}B$，用二进制数表示逻辑地址，则末尾 $k$ 位即为页内偏移量，其余部分就是页号。即页面大小和页内偏移量位数可以相互转换，互相推出。

==注意==：

内存地址是以字节编址的，每个地址的存储单元可以存放 $8;bit$ 的数据。一个字节就是一个房间，然后给这个房间编址。

页表地址寄存器（PTR）：保存当前执行进程页表的起始地址和页表长度，从而计算页表项。

页表长度可以判断页号是否越界，通过比较页号 $P$ 和页表长度 $M$，若$P\ge M$，则产生越界中断（内中断）。在这里 $P=M$ 也会发生越界，因为页号从 $0$ 开始，而页表长度至少是 $1$。
页表中页号 $P$ 对应的页表项地址=页表起始地址 $F$ + 页号 $P$ * 页表项长度，取出该页表项内容 $b$，即为内存块号。
计算 $E = b * L + W$（其中 $L$ 为页表大小，$W$ 为页内偏移量），用得到的物理地址 $E$ 去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址）

【注意】页表长度指的是这个页表中总共有几个页表项，即总共有几个页；而页表项长度指的是每个页表项占多大的存储空间（存储块号）；页面大小指的是一个页面占多大的存储空间。

基本地址变换机构：

重定位寄存器指明进程在内存中的起始位置。

【例】若页面大小 $L$ 为 $1K$ 字节，页号2对应的内存块号 $b = 8$，将逻辑地址 $A=2500$ 转换为物理地址 $E$。

等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占 $10$ 位，页号2对应的内存块号 $b = 8$，将逻辑地址 $A=2500$ 转换为物理地址 $E$。

①计算页号、页内偏移量：页号 $P = A/L = 2500/1024 = 2$；页内偏移量 $W = A%L = 2500%1024 = 452$

②根据题中条件可知，页号2没有越界，其存放的内存块号 $b = 8$

③物理地址 $E = b * L + W = 8 * 1024 + 425 = 8644$

注：

在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

地址变换过程总共需要访问 $2$ 次内存。第一次访问内存是查页表时进行的，而第二次访问内存是在访问目标内存单元时进行的。

6.5.2 具有快表的地址变换机构

快表，又称联想寄存器（TLB, Translation Lookaside Buffer），是一种访问速度比内存快很多的高速缓冲寄存器，用来存放最近访问的页表项的副本，可以加速地址变换的速度，具有高速、有并行查询能力的特征。与此对应，内存中的页表常称为慢表。存储机构从快到慢依次是：寄存器、高速缓存（Cache）、内存（RAM）、外存（硬盘）。

引入快表后的访存变化：
- 若快表命中，则访问某个逻辑地址对应的物理地址仅需==一次访存==即可；
- 若没有找到匹配的页号，需访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。故需要访问某个逻辑地址对应的物理地址在未命中情况下需要==两次访存==。
- 注意：在第二种情况下，在找到页表项后，应同时将其存入快表，以便后面可能的再次访问；但若快表已满，则必须按照一定的算法对旧的页表项进行替换。
- 快表的实现依赖于时间局部性（同个数据再次被访问）和空间局部性（由于很多数据在内存中是连续存放的，附近的存储单元很可能被访问）。
有效访问时间（Effective Access Time）：

联想寄存器访问时间为 $\varepsilon$，内存访问时间为 $t$，联想寄存器中的命中率为 $\alpha$，则有效访问时间 EAT 为：

$EAT=(t+\varepsilon) \alpha+(2 t+\varepsilon)(1-\alpha)=2 t+\varepsilon-t \alpha.$

若系统支持快表、慢表同时查询，则未命中情况下时间是 $2t$（无 $\varepsilon$），可以参考下面的甘特图：

6.5.3 两级页表与多级页表

单级页表存在的问题：

页表必须连续存放，当页表很大时，需要占用很多个连续的页框（引入两级（多级）页表的原因）
进程在一段时间内只需要访问某几个页面就可以正常运行，没有必要让整个页面都常驻内存（引入虚拟存储技术，可以在需要访问页面时才把页面调入内存，在页表项中增加一个标志位，用于表示该页面是否已经调入内存）

由此，为离散分配的页表再建立一张页表，称为页目录表（外层页表）。

页目录表（存放外层页号+内层页表存放位置）

两级页表示意图

对于 $32$ 位逻辑地址空间，页面大小为 $4KB$，则可以设置如下：

将逻辑地址转换为物理地址分为以下步骤：

按照地址结构将逻辑地址拆分为三部分
从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置（每个页表项记录页表页面的物理块号）
根据二级页号查表，找到最终想访问的内存块号
结合页内偏移量得到物理地址
若采用多级页表机制，则各级页表的大小不能超过一个页面。

[例]某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用____级页表，页内偏移量为____位。

[解]页面大小$=4KB=2^{12}B$，按照字节编址，因此页内偏移量为12位，页号为40-12=28位。又页表项大小为4B，则每个页面可以存放$2^{12}/4=2^{10}$个页表项。因此各级页表最多包含$2^{10}$个页表项，需要10位二进制位才能映射到$2^{10}$个页表项，故每一级的页表对应页号应为10位。故28位的页号至少要分为3级。

两级页表的访存次数分析（假设没有快表机构）：

第一次访存：访问内存中的页目录表
第二次访存：访问内存中的二级页表
第三次访存：访问目标内存单元

$n$ 级页表的访存次数是 $n+1$ 次。

6.6 分段存储管理(Segmentation)

6.6.1 基本内容

进程地址空间的概念：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
优点：用户编程更方便，程序的可读性更高。也可描述为：方便编程；分段共享保护；动态链接；动态增长。

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成。段号的位数决定了每个进程最多可以分几个段；段内地址位数决定了每个段的最大长度是多少。

6.6.2 段表

程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。段表中包含段号、段长、基址。

段表的结构

段表寄存器：段表始址 $F$ | 段表长度 $M$
作业逻辑地址表示：段号 $S$ | 段内地址 $W$

段寄存器用于存储代码或数据段的起始地址，段表寄存器用于存储段表地址。

段表执行流程

6.6.3 分段的保护与共享

段的保护
- 段表基址寄存器 STBR 和段表长度寄存器 STLR
- 与段相关的保护位：只读、只写、只执行
- 与段相关的 Validation 位：为 $0$ 表示不合法段
段的共享
- 设置共享段表
- 第一个请求使用共享段的进程申请内存分区，调入，修改共享段表内容
- 后续进程使用共享段，在本进程段表填入共享段物理地址；在共享段表中增加表目，将共享段计数 $count$ 加 $1$
- 回收执行 $count-1$；$count=0$ 时撤销该共享段

6.6.4 分页与分段的对比

页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。
段是信息的逻辑单位，分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定，段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员再表示一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源）。

类型	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片(分配给进程的最后一个页面不一定100%被利用)	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便地按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续空间会很不方便；另外，段式管理会产生外部碎片

6.7 段页式管理方式

段页式系统的逻辑地址结构由==段号、页号、页内地址（页内偏移量）==组成；用户只需提供段号和段内地址，系统自动将段内地址拆分为页号和页内偏移量，因此段页式管理的地址结构是二维的。段页式存储管理存在内碎片，无外碎片[因为页表的存放地址可以不连续]。

设置段表地址寄存器，保存当前执行进程段表的起始地址和段表的长度。段表和页表的构成如下：
- 每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放地址组成（与分段存储管理不同）；
- 每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成（与分页存储管理相同）。
在不引入快表的情况下，访问一个逻辑地址所需访存次数为3次，第一次查段表，第二次查页表，第三次访问目标单元。

段页式管理方式的基本思想是用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。

Chapter 7.虚存管理

7.1 局部性原理(Locality)

时间局部性：刚刚访问过的指令或数据，不久又会被再次访问。
空间局部性：刚刚访问过的指令或数据，其邻近单元不久会被访问。
顺序局部性（程序的顺序执行）：

通常情况下，CPU跟踪程序的执行是按照在主存中的连续地址进行的。只有在遇到转移指令时，才发生跳转。

7.2 虚拟存储器

定义：从用户角度，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。

实现方式：请求分页系统、请求分段系统

硬件支持：页/段表扩充，缺页/段中断，地址变换

特征：

虚拟性：即不是物理上而是逻辑上扩充了内存容量
离散性：采用离散分配方式
多次性：一个作业分成多次调入主存运行
对换性：将得不到运行的程序、数据调至外存交换区

虚存的优势：

比物理内存大的程序可以运行，编程人员无需考虑内存的限制；
可以让更多的程序同时运行，系统吞吐量提高；
更容易实现文件共享；
加载或交换程序到内存所需的I/O更少，程序运行更快。

注：

虚拟内存的容量受计算机地址位数的限制。

7.3 请求分页机制

7.3.1 概述

请求分页机制的英文名为Demand Paging，页面仅在需要的时候加载进入内存。
惰性交换器Lazy swapper——进程驻留在外存，执行时所需要的页面交换到内存。
调页程序：pager
为进程分配的最小页框数（物理块数）：$3$ 个
- 数据段
- 代码段（指令）
- 间接寻址
页表内容：

页号页框号 ==状态位 $P$== ==访问位 $A$== ==修改位 $M$== 外存地址

访问位表示其是否被访问过，修改位表示其是否被修改过（多为数据）
缺页中断机构与一般中断的2点区别：
- 是在指令执行期间，发现指令/数据不在主存时产生并处理；
- 一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中断的状态。
基本地址变换：

7.3.2 页面分配与置换策略

页面分配策略：

内存记录空闲页框情况——位示图 bitmap
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

驻留集指请求分页存储管理中给进程分配的物理块的集合。
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

页面置换策略：

局部置换：发生缺页时只能选进程自己的物理块进行置换。
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
与分配策略组合，有以下三种算法：固定分配局部置换、可变分配全局置换、可变分配局部置换

	局部置换	全局置换
固定分配	√	—
可变分配	√	√

注：

全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配。

7.4 页面置换算法

在实际操作中，遇到缺页情况可以在下面标记”+”号。

7.4.1 先进先出置换算法

First In First Out
先进入内存的页面，先置换出内存。
缺页率高
存在==Belady 现象==，即分配页框数多，反而缺页率高。

Belady 现象实例：

7.4.2 最佳置换算法(Optimal)

以后一段很长时间不用的页面先置换
理想算法，不能实际实现

7.4.3 最近最久未使用算法(LRU)

英文为Least Recently Used，最近很长时间不用的页面先置换
在操作中，若发现要访问的页面在页框内，需要将其放到最前面；到要置换页框中某个页面时，将最后的移出页框。
计算机中的实现
- 计数法实现：
  
  每个页表项设置一个计数器，若页面被访问，则将当前时间复制到计数器中。
  
  当需要置换时，查找计数器，离当前时间最远的先淘汰。
- 堆栈法实现：
  
  维护一个页号的堆栈，当被访问，就将其移动到 top 位置；
  
  淘汰堆栈最 bottom 的页号。

注：

若程序本身没有局部性的特征，LRU 算法将退化为 FIFO 算法。

7.4.4 Clock置换算法

LRU 近似算法
**简单 Clock NRU**（Not Recently Used）：
- 内存中所有页面组成循环队列（设置指针），当需要置换时，依次检查访问位：
  
  为 $0$，置换；
  
  为 $1$，重置为 $0$，继续检查下一个页面。
- 如访问序列为123412512345，则：
改进型Clock算法：
- 考虑到仅被淘汰过的页面被修改过，才需写回内存。故在其他条件相同时，应先淘汰未修改过的页面，避免I/O操作。
- 设置==(淘汰位A,修改位M)==，A=1表示近期访问过，M=1表示近期修改过，(0,0)应优先淘汰，淘汰优先级为：**==(0,0)==,(0,1),(1,0),(1,1)**。

7.4.5 其他算法

最少使用置换算法（Least Frequently Used）：选择近期使用次数最少的页面淘汰；类似还有最多使用置换算法。

页面缓冲算法（Page Buffering Algorithm）：

思想：采用可变分配、局部置换方式。置换算法FIFO，被置换的页按是否被修改过而入系统设置的两个链表队列：修改页面链表、空闲页面链表。
如果再次产生缺页中断，首先检查链表队列：

有，恢复到进程驻留集中；

无，取空闲页面链表中第一页分配。

修改页面链表中页面达到一定数量时，集中回写，减少I/O次数。

[例1]分页管理系统计算题：https://blog.csdn.net/qq_26816591/article/details/51910518

[例2]某虚拟存储器的用户空间共有 $32$ 个页面，每页 $1KB$，主存 $16KB$。假定某时刻系统为用户的第 $0$、$1$、$2$、$3$ 页分配的物理块号为 $5$、$10$、$4$、$7$，而该用户作业的长度为 $6$ 页，试将十六进制的虚拟地址 $093C$ 转物理地址。

[解]（1）$16$ 进制数据：$093C$

0 9 3 C

0000 1001 0011 1100（C=12）

转成 $2$ 进制数据：0000-1001-0011-1100

（2）确定页号和页内地址

页内地址看每页大小：$1KB=2^{10}B$,

页号看页的数量：$32=2^5$

取 $16$ 进制的后 $10$ 位作为页地址。$\rightarrow 01-0011-1100$

取 $16$ 进制的前 $5$ 位作为页号。$\rightarrow 0000-1$

（3）页号变块号

$2$ 进制转 $10$ 进制

页号 $0000-1$ 转成页号 $1$

页号 $1$ 查表得块号 $10$

（4）计算物理地址位数

主存 $16KB=2^{14}B$，物理地址 $14$ 位 = 块号 + 页地址

块号 $10$ 转 $2$ 进制 1010

$093C$ 转物理地址：

$1010 01-0011-1100$

7.5 请求分页系统性能分析

7.5.1 缺页率与有效访问时间

有效访问时间（Effective Access Time）：

EAT = $(1-p);$ 内存访问时间 + $p;$ 缺页中断时间

缺页中断时间包括以下项：

缺页中断服务时间
页面置换出去的时间（可选，若未被修改，直接覆盖即可）
缺页读入时间
进程恢复执行时间

影响缺页率的因素有：

分配给程序的主存块数
页面的大小
程序编制方法
页面置换算法

7.5.2 工作集/驻留集模型

工作集：指在某段时间间隔里，进程实际访问页面的集合。英文为Working Set Model，是Denning根据程序的局部性理论提出，以解决缺页率高的问题。其可用一个二元函数 $W(t, \Delta)$ 来表示：

$t$ 是当前的执行时刻
$\Delta$ 称为工作集窗口（Working-set window），即一个定长的页面访问的时间窗口（“时间段”）；$\Delta$ 不应过大或过小，过小会导致频繁缺页。
$W(t, \Delta)$ = 进程在当前时刻 $t$ 之前的 $\Delta$ 时间窗口（在 $t-\Delta$ 到 $t$ 时间段）当中的所有页面所组成的集合（随着$t$的变化，该集合也在不断地变化）；$W$ 是 $\Delta$ 的非降函数。
$|W(t, \Delta)|$ 为工作集中包含的页面数

注：

工作集大小的变化与程序的局部性有关，开始局部性较差，工作集急剧上升。

驻留集：指请求分页存储管理中给进程分配的物理块（物理空间）的集合，即进程实际驻留在内存当中的页面集合。

工作集和驻留集不同，驻留集表示当前要访问的页面在内存中的集合，工作集表示当程序运行过程中要访问的页的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。如果一个进程的整个工作集都在内存中，即驻留集 $\supseteq$ 工作集，则进程将很顺利的进行，不会造成太多的缺页中断。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。

7.5.3 抖动现象

刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页面的置换，称进程发生了“抖动”。

==预防抖动的方法==：

采用局部置换策略，使抖动控制在局部范围
在CPU调度程序中引入工作集算法，控制道数
调整道数，使产生缺页频率的平均时间=系统处理缺页的平均时间（**L=S 准则**）
挂起若干进程
增大页面大小（页面大小的选择）
预调页面

7.6 请求分段机制

英文名为Demand Segmentation
段表机制：

段名	段长	内存地址	状态位（该段在不在内存）	存取方式（可读/可写/可执行）	访问位（是否被访问）	修改位	增补位（如该段是否可以动态增长）	外存地址

缺段中断：在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。可采用紧凑技术/淘汰几个段（多为代码段）。
请求分段的共享和保护：
- 共享方式为：每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。系统实现方式为：
  - 设置共享段表/现行分段表
  - 建立共享段分配、回收操作过程
- 完善分段保护机制，有3种常用措施：越界检查，存取控制检查，环保护机构（即软件层次结构设置优先规则，外环访问内环需系统调用，内环可以直接访问外环）。

Chapter 8.文件系统接口

8.1 文件系统概念

8.1.1 文件的概念及逻辑结构

文件是具有文件名的一组相关信息的集合(按名存取的数据集合)，是一个由操作系统定义和实现的抽象数据类型；其组成的大小关系为文件—–记录—–数据项（组成文件的原子性数据，如类型、值）。

数据项：最低级的数据组织形式

记录：一组相关的数据项的集合

文件：由创建者所定义的一组相关信息的集合

文件逻辑结构是指从用户观点出发，所观察到的文件组织形式。它是用户可以直接处理的数据和结构，独立于物理特性。

文件逻辑结构分为以下几种结构：

无结构：字或字节的序列（字符流式文件，如记事本）
简单记录结构：行、固定长度记录文件、可变长度记录文件
复杂结构：
- 格式化文档
- 可重定位加载文件

8.1.2 有结构文件分类

操作系统、程序决定文件的逻辑结构。有结构文件按记录的组织形式可分为：

顺序文件：

文件记录的排列、存取按顺序进行。
适用场合：对记录批量存取（大量文件的备份）；顺序介质（磁带）
缺点：增删不方便、读取慢、查找性能差

索引文件：

为变长记录文件建立一张索引表（或多级索引），用户通过关键字访问记录。
适用场合：对信息处理及时性要求高的场合。
优点：随机存取
缺点：索引需要额外开销

索引文件

索引顺序文件：

索引文件将每条记录对应一个索引表项，因此索引表可能会很大。针对索引文件的缺点，引入索引顺序文件。索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但是不同的是，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

如下图，顺序文件记录分组，并建立索引表，索引表项为各组的第一记录指针：

索引顺序文件

8.1.3 文件属性及操作

文件的属性有：

名称：人类可读形式保存的唯一信息
标识符：唯一标记文件系统的文件，通常是数字
类型：支持不同类型文件的系统所需要的信息
位置：指向设备与设备上文件位置的指针
大小：当前文件的尺寸及最大尺寸
- 总大小：文件内容的总大小
- 总计文件大小：文件信息和文件内容的总大小
保护：确定谁能读写执行操作的访问控制信息
- 可读
- 可写
- 可执行
时间、日期和用户标识（谁创建、修改）
扩展文件属性

文件的操作有：

对记录的操作：增、删、改、查；
对文件本身的操作：
- 新建
- 读、写
- 查找
- 删除
- 截断（truncate，分成两个文件）
- 打开、关闭文件——把文件属性等信息调入内存
- 设置读写位置

8.1.4 文件类型

文件按不同划分方式可以分为：

按用途分：系统文件、用户文件、库文件（标准子程序、常用例程，.lib）
按存取控制属性：只读文件、读写文件、只执行文件
按文件逻辑结构：有结构、无结构文件
按文件物理结构：顺序、链接、索引文件
按文件中数据形式：源文件、目标文件、可执行文件
按信息存储的期限：临时文件、永久文件、档案文件

UNIX系统内的文件类型：

普通文件（r）
目录文件（d）
特殊文件（s），即设备文件，分为块设备文件和字符型设备文件
- 块设备文件描述的是以随机访问的数据库为单元的设备。在打开一个块设备文件后。可以直接去访问它的某一个数据块，而不用管其文件系统的内部结构，如硬盘。
- 字符设备文件指以字符流方式进行操作的设备，如打印机、调制解调器。

8.1.5 文件系统的结构和功能

文件系统是用于操纵和管理各种文件，方便用户使用文件的软件集合。

文件系统的功能有：

文件管理（创建/删除文件，对文件的各种操作等）
目录管理（创建/删除目录项，权限验证等）
文件存储空间的管理
文件的共享和保护
提供方便的接口（如实现按名存取，文件系统调用等）

8.2 文件访问方法

8.2.1 顺序访问

文件信息按顺序（如一条一条记录）进行处理，用于归档等场合。

Read_next()：读取文件的下一部分
Write_next()
reset

8.2.2 直接访问

允许程序按任意顺序进行读取和写入，用于磁盘等场合。磁盘上的文件可以通过顺序或直接访问。

Read(n)：读取文件的第n条记录
Write(n)
Position_file(n)：定位（查找）文件

8.3 文件目录结构

8.3.1 概述

文件目录结构是用于有效管理和组织文件的结构。借助于文件目录，可将每个文件的符号名与其所在存储空间地址联系起来。目录结构和文件都驻留在外存（如磁盘）上。

对目录管理的要求有：

实现“按名存取”（目录的主要作用）
有较高的目录检索速度：合理组织文件目录
允许文件重名
提供文件共享功能

文件的地址以其磁盘位置开始。
设备目录需要提供以下信息：名称、类型、地址、当前长度、最大长度、最后访问时间、最后更新时间、创建者，保护信息等。
对目录的操作有：创建、删除、重命名、查找、列表内容、遍历文件系统（ls）、复制、设置目录权限等。

8.3.2 常见目录结构

8.3.2.1 单级目录结构

Single Level Directory
整个系统只建立一张目录表，为每个文件分配一个目录项。

单级目录结构

优点：
- 空间开销小
- 可以实现“按名存取”
缺点：
- 查找速度慢（线性表需遍历）： N个目录，平均查找N/2个目录项
- 不允许重名
- 不能实现共享

8.3.2.2 两级目录结构

Two-Level Directory
系统建立一张主文件目录 MFD，为每个用户建立用户文件目录 UFD，每个用户文件目录在 MFD 中分配一个目录项。

两级目录结构

优点：
- 提高了查找速度：
  
  设共 $n$ 个用户，每个用户 $m$ 个文件，则二级目录需查找 $(n+m)/2$ 个目录项（若 $n=m$，则共 $n$ 个）；
  
  而如果设一级目录，则需查找 $(n*m)/2$ 个目录项（若 $n=m$，共 $n^{2}/2$ 个）。
- 不同用户文件允许重名
缺点：不能文件共享。

8.3.2.3 树形目录结构

Tree-Structured Directories，是目前广泛采用的文件目录结构。
在两级目录基础上，允许用户创建自己的子目录并组织其文件。

树形目录结构

路径名：从根目录到文件之间的通路。
当前目录：
- 相对路径：从当前目录到文件之间的路径
- 绝对路径：从根目录到文件之间的路径
目录的增加和删除：
- 增加：无重名 mkdir <dir-name>
- 删除：不删除非空目录/可删除非空目录
优点：
- 有效提高对目录的检索速度
- 允许文件重名
- 便于实现文件共享

8.3.2.4 无环图目录结构

Acyclic-Graph Directories
目录结构中有共享的子目录和文件，如“快捷方式”。
优点：
- 可共享：链接方式实现、复制文件信息
- 更灵活
- 遍历图相对简单
其他需要考虑的问题：
- 多个绝对路径名？——别名问题
- 删除——悬挂指针问题

8.3.2.5 通用文件结构

General Graph Directory
允许系统中存在环。

如何保证无环结构：
- 仅可 link 到文件，不能 link 到目录
- 增加新链接时，采用检测算法
缺点：
- 查找时对环要进行必要处理
- 删除：garbage collection

8.4 文件共享

文件共享是指多个用户（进程）共享同一份文件，系统只保存文件的一个副本。

8.4.1 早期文件共享方法

基本文件目录：

实现：将源文件目录分为基本文件目录 BFD 和符号文件目录 SFD
- BFD：每个文件/目录有一个目录项，文件标识数、其他信息
- SFD：每个用户一个，目录项只是其文件名和文件标识数
提高文件访问速度：系统设置**活动文件表 AFT，用户设置活动名字表 ANT**；用户执行 OPEN 操作时，将 SFD 内容入 ANT，BFD 内容入 AFT。

连访法：

建立目录间的链接，使目录项直接指向另一个目录项
在文件说明中增设“连访”属性，标识文件说明中的物理地址是一文件或目录项的指针
增设“用户计数”标识共享文件的用户数（当用户计数 count = 0 时，才能删除文件内容）

绕弯路法：

实现：系统设置当前目录指针，用户对当前目录下的文件直接访问，当需访问其它目录下文件时，通过指定路径完成。

8.4.2 现今常用文件共享方式

多个用户（进程）共享同一份文件，系统只保存文件的一个副本。

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

实现：设置索引结点，存储文件的物理地址、链接计数（共享计数）及其它文件属性；文件目录只包括文件名和该文件对应索引结点的指针。
优点：任何对索引结点内容的修改对其它共享用户都是透明的。

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

实现：设 B 为了共享 C 的文件 F，在 B 中创建一个Link类型的新文件，新文件目录中只包含被链接文件F的路径名，称这种链接方法为符号链接(symbolic Linking)。
说明：只有文件主人的目录中有文件索引结点的指针，其它用户目录中只有路径名。

试比较维护文件单一副本提供文件共享和为每个共享文件的用户维护一个文件副本两种方式的优缺点。

对于单个副本的情况，对同一文件的并行更新可能导致用户获得不正确的信息，并使文件处于错误状态；

对于多个副本的情况，会带来一些存储浪费，不同副本之间还存在一致性问题。

8.5 文件保护

8.5.1 概述

影响文件系统安全性的主要因素
- 人为因素
- 系统因素：系统部分软件、介质故障
- 自然因素：存放在磁盘中的数据，随时间变化发生溢出或消失
文件保护功能：
- 防止未核准用户存取文件（文件保密）
- 防止一个用户冒充另一个用户存取文件
- 防止核准用户误用文件
保护措施：
- 存取控制机制
- 容错技术
- 后备系统

8.5.2 存取控制机制的概念及实现

8.5.2.1 保护域

指进程可访问的对象。

访问权：一个进程对某对象可执行操作的权限，表示为**有序对==(对象名,权集)==**，权限有R（可读）、W（可写）、E（可执行）
域：一组对象访问权的集合
进程与域的联系方式：
- 静态联系：进程可用资源集是固定的
- 动态联系：进程可用资源集是可变的，需提供域转换机制、read to know须知原则。

8.5.2.2 访问矩阵(Access Matrix)

描述域及所属对象的矩阵（Lampson矩阵）。

访问矩阵中对象访问权由资源拥有者或管理者确定。
通过设置域间切换开关实现进程与域的动态联系。
为满足修改的需要，增设：
- 拷贝权（权限 copy）
- 所有权（标明 owner）
- 控制权

拷贝权的应用：将具有拷贝权的对象访问权拷贝到其他域中，使其他域中进程对同一对象具有相同访问权。

访问矩阵为稀疏矩阵，所以实现上可以采用：
- 访问控制表(Access Control List)——按列划分，用**(域,权集)表示，设置到文件对象中（文件[属性]控制块FCB**）
- 权能表(Access Capability List)——按行划分，用**(对象,权集)表示，设置到进程控制块 PCB** 中
对一个文件的访问，常由用户访问权限和文件属性共同限制。
文件拥有者对文件进行保护：
- 访问模式：读、写、执行
- 用户分类：文件拥有者（owner）、和文件同属于一组的用户（group）、其他用户（other）
- 构成 $9$ 位权限位

文件系统是所有文件、目录的集合，操作系统一般采用层次型模型对文件系统进行管理。分级安全管理有如下几个层次：

系统级安全管理：注册、登录
用户级安全管理：用户分类、文件访问权限
目录级安全管理：文件目录访问权限、用户分别设置
文件级安全管理：每个文件访问存取控制权限机制

Chapter 9.文件系统实现

9.1 磁盘的结构及功能实现

磁盘的表面被划分成一个个磁道（track），一个磁道又被划分成一个个扇区（sector），可以给每个扇区进行编号，各个扇区存放的数据量相同（如 $1KB$）。由于最内侧磁道上的扇区面积最小，因此数据密度最大。
一个盘片可能有两个盘面；所有的磁头都是连在同一个磁臂上的，所有磁头“共进退”。所有盘面中相对位置相同的磁道（如上图的三个蓝色磁道）组成柱面。
可用**(柱面号,盘面号,扇区号)**来定位任意一个“磁盘块”。根据该地址可以读取一个“块”：
- 根据“柱面号”移动磁臂，让磁头指向指定柱面；
- 激活指定盘面对应的磁头；
- 磁盘旋转的过程中，指定的扇区会从磁头下面划过，由此完成对指定扇区的读/写。

9.2 磁盘访问时间

寻道时间 $Ts$(主导磁盘读写时间的因素)

移动磁臂到预期读取的柱面（磁道）所需要的时间。假设移动（跨越）一个柱面（磁道）所需时间为 $t$，需要移动 $n$个磁道，则 $Ts=nt$。

旋转延迟时间 $Tr$

磁盘旋转使磁头定位到目标扇区所需要的时间，设磁盘转速为 $r$（单位：转/秒或转/分），$1/r$ 为转一圈需要的时间，找到目标扇区平均需要转半圈，故 $Tr=(1/2)*(1/r)=1/2r$。若前面单位为分，后面单位为秒，则需要$Tr=30/r(s)$（如转换成 $ms$ 还需要再 $*1000$）。

数据传输时间 $Tt$

从磁盘读出或向磁盘写入数据所经过的时间，设传输的字节总数 $Total$，磁盘转速为 $r$ 转/分，一转的字节数（每个磁道上的字节数）为 $b$；则有：每个磁道可以存 $b$ 个字节，则 $Total$ 字节的数据需要 $Total/b$ 个磁道才能存储。而读/写一个磁道所需时间刚好是转一圈所需要的时间 $1/r$，则 $Tt=读写一个磁道时间*磁道数=Total/rb$。

总平均存取时间为三个时间之和。

**[例]**设某磁盘平均寻道时间为 $10ms$，转速为 $10000r/m$，每个磁道有 $320$ 个扇区，每个扇区 $512$ 字节。求读取一个包含 $2560$ 个扇区、大小为 $1.2MB$ 的文件所需的时间。

假设文件顺序存储：

$Ts=10ms$，$Tr=3ms$，读取 $320$ 个扇区的时间 $Tt=1/r*60000=6ms$ ，则 $T_{总}=19+7×9=82ms$；（需要换道 $7$ 次，每次换道还需旋转找到该磁道的第一号扇区）；

假设文件随机存储：

$T_{总}=2560×(10+3+60000/10000/320)=33328ms$（每个扇区中的数据传输时间为：$1/r$(读一磁道) * $1/320$(读一扇区)[*60000是分与微秒的单位换算]）。

注：

文件内容所占用的空间要比真实的文件所占用空间要小，扇区是磁盘读写的最小单位。

9.3 磁盘调度算法

目标：最小化寻道时间。

9.3.1 先来先服务FCFS

英文为First Come First Served

思想：选择等待队列中最先到达的访问请求，作为下一次的访问对象。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面。

9.3.2 最短寻道时间优先SSTF

英文为Shortest Seek Time First

思想：选择等待队列中离当前磁道最近的访问请求，作为下一次的访问对象。注意此算法是局部优，最终不一定是最优的。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面。

优点：吞吐量大，任务平均响应时间更快；

缺点：任务响应机会不均等（低磁道、高磁道两边的请求无限滞后）。

9.3.3 扫描算法

**扫描算法 SCAN**（也称电梯调度法）：

思想：选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面，设磁头向磁道增加的方向移动。

原始算法需到最高磁道才会返回，改进LOOK则到序列中最高的磁道后即返回。题目中扫描算法默认是改进LOOK算法。

缺点：存在armstickiness（磁臂黏着）现象，一个或多个进程反复请求某个磁道，从而垄断整个磁道，导致”饥饿“。

**循环扫描算法 C-SCAN**：

SCAN 算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题，其规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

思想：单向扫描，选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象，直到该方向最后一个请求，反向。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面，设磁头向磁道增加的方向移动。

**N 步扫描算法 N-SCAN**：

思想：将磁盘请求队列分为若干长度为 N 的子队列，并按 FCFS 算法依次处理这些队列，在处理每一个子队列时，采用 SCAN 算法。(当 N = 1 时等价于先来先服务算法，N 为无穷时等价于 SCAN 算法)

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），当前磁头位置在100号柱面，设磁头向磁道增加的方向移动，采用 N = 3 的 N 步扫描算法。

FSCAN 扫描算法：

思想：将磁盘请求队列分为 $2$ 个子队列，其中一个为当前所有请求构成的队列，另一个为扫描期间新到达的请求构成的队列，并按 N 步扫描处理。

[总结]各种算法比较：

SSTF 较为常用
SCAN 和 C-SCAN 在负载较重的情况（输入/输出任务较多）下性能更好
性能的取得一般依赖请求序列，而请求序列与文件分配方式相关
SSTF 和 LOOK 常会选为缺省算法

9.4 文件物理结构

分为顺序结构、链接结构、索引结构。

9.4.1 连续分配

文件在外存分配连续的磁盘块。

优点：支持顺序访问、直接访问；磁头定位时间短，顺序访问速度快。
缺点：要求连续盘块，易产生碎片（外碎片）；需预知文件长度。

顺序文件中的逻辑记录依次存储在连续的磁盘块。

9.4.2 链接分配

9.4.2.1 单向链表

通过磁盘块中的链接指针，将文件所属盘块链成链表。

隐式链接的实现：文件目录中只给出文件第一、最后一个盘块的指针，其余由链接指针给出。

显式链接的实现：系统设置一张链接表（FAT），对每个物理块，存放的是与该物理块链接的下一个物理块号，文件目录中保存第一块的盘块号。

文件分配表FAT(File Allocation Table)是用来描述文件系统内存储单元的分配状态及文件内容的前后链接关系的表格。

缺点：不支持直接访问，FAT需要磁盘空间。

串联/链接文件中的逻辑记录存储的磁盘块中设指针指向下一条记录所在物理块号。

优点：简单、记录数可任意增减；

缺点：查找只能单向查找，不能直接找某个磁盘块；可靠性差（1个出错整个文件的存储均会出现问题）；磁盘块中会少一个链接指针对应的空间（链接指针占用的空间）。

9.4.2.2 异或双向链表

设文件A有三个记录，存储在4，12，8三个物理块中。

查找过程：

向下查找：本记录链表指针值与上记录块号“异或”
向上查找：本记录链表指针值与下记录块号“异或”

付出时间（计算）代价。

9.4.3 索引分配

建立索引表保存文件所分配的磁盘块号。

单级索引分配：只有一个磁盘块存放索引表
多级索引分配：多个磁盘块存放索引表

混合索引分配：结合直接地址和多级索引分配的方式

索引文件：每个索引文件建立一张索引表，每一个表目指向记录所在的物理块号。

优点：可支持直接访问、顺序访问；无外部碎片；

缺点：索引表需要额外开销。

【例】某文件有1000条记录，文件采用索引分配，设每一个盘块存放一个记录，每一盘块可以存放10个索引表目。

（1）保存该文件需要建立几级索引？（2）共需要多少磁盘块？

【解】（1）三级索引；（2）共需要1+10+100+1000=1111块。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

9.5 空闲空间管理方法

主要功能：

设置相应数据结构，记录空闲存储空间的分配情况
实现存储空间的分配与回收

9.5.1 空闲表法

设定空白文件目录

管理：系统为每一个空白文件（一个连续未分配的区域）建立一个目录，每个空闲区有一个表目。
数据结构：第一个空白块地址，空白块数
分配：系统依次扫描空白文件目录，找到一个合适的空白文件分配（方法可用首次适应、最佳适应、最坏适应等算法）
回收：动态修改空白文件表（合并）
特点：
- 适用于建立顺序文件（连续分配方式）
- 当有大量小的空白文件时，效率降低

9.5.2 空闲块链

管理：将所有空闲块链接在一起，组成队列。
数据结构：链表
分配：从链首依次摘取 $1$ 块或 $n$ 块；
回收：回收块入链尾，并修改空闲链的链尾指针。
特点：
- 操作简单
- 当链较长时，效率较低
改进：空闲盘区链
- 操作系统保存着链头、链尾指针。
- 如何分配：若某文件申请 $K$ 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
- 如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

注：

空闲块链法以盘块为单位组成一条空闲链；空闲盘区链法以盘区为单位组成一条空闲链。

假设指向空闲空间链表的指针丢失，系统将搜索整个目录结构以确定哪些页面已分配给作业，剩下的未分配的页面将重新链接起来组成空闲链表。

9.5.3 位示图

管理：系统专设几个字，字中每一位对应一个磁盘块。
数据结构：字；位—— $1$ 表示已分配；$0$ 表示空闲
分配：找到 $0$ 所指示的空闲块进行分配；每位对应的盘块号$b=i*n+j$（$b,i,j$ 从 $0$ 开始计数；$i,j$ 分别为行列值，$n$ 表示每行位数）
特点：位示图尺寸固定；可常驻内存，分配回收块
注意：第 $x$ 块 = 块号 $+;1$

9.5.4 成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读取内存，并要保证内存与外存中的“超级块”数据一致。
管理：设置空闲盘块号栈，存放当前可用的一组空闲盘块的盘块号（最多存放 $100$ 个号），以及堆栈中尚有的空闲块数。
数据结构：堆栈
说明：
- 栈属于临界资源，应互斥使用
- S.free(0) 是栈底，堆栈的首空间记录该组空闲盘块数，“超级块”充当链头的作用。最后一组记录的盘块数要少一块，因为要有一块用于标记已经是最后一组。
- 栈满时，栈顶为 S.free(99)。

分配方式：需要 $100$ 个空闲块：
- 检查第一个分组的块数是否足够。$100=100$，是足够的。
- 分配第一个分组中的 $100$ 个空闲块。但是由于 $300$ 号块内存放了再下一组的信息，因此 $300$ 号块的数据需要复制到超级块中。

回收方式：

假设每个分组最多为 $100$ 个空闲块，此时第一个分组已有 $100$ 个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

9.6 文件及目录的实现

9.6.1 文件的实现

一个文件的信息用文件控制块FCB(File Control Block)来存储。为提高查找速度，可将FCB分为两部分：文件名和文件描述。

文件控制块：一个文件目录项。其包含的内容有：
- 基本信息：文件名、外存物理位置、逻辑结构、物理结构
- 存取控制信息：文件主、核准用户、一般用户的存取权限
- 管理信息：创建日期/时间、上次修改的日期/时间、要求保留的时间等
索引节点：记录文件描述信息的数据结构，称为inode。
- 减少磁盘I/O，提高目录查找速度而引入。
- 磁盘索引结点：存放在磁盘上的索引结点，系统中每个文件都由唯一的磁盘索引结点及编号（外存inode区的顺序号）。其内容有：
  - 文件主标识/组标识
  - 文件类型：普通文件/目录文件/块设备文件/字符设备文件
  - 文件存取权限
  - 文件物理地址：数据文件的盘块号
  - 文件长度
  - 文件连接计数：文件在目录中具有的路径名数
  - 文件存取时间：文件最近被存取、修改时间，索引结点修改时间。
- 内存索引结点：存放在内存的索引结点。当文件被打开时，将磁盘索引结点的内容复制到内存索引结点中。其在磁盘索引结点基础上，增加部分内容：
  - 外存索引结点编号
  - 状态：指示结点是否被修改、上锁
  - 访问计数：共享该结点的进程数
  - 文件所在设备的逻辑设备号
  - 链接指针：空闲/散列队列指针

例：

在UNIX系统中，设一个FCB为64B，一个Block为1KB，则磁盘块中可存放16个目录项，若共有3200个FCB，则查找一个文件平均启动磁盘100次；若FCB内容分开，一个文件名14B，2B存放inode结点指针，在1KB的盘块中可存放64个目录项，则可将平均启动磁盘次数减少到1/4。

9.6.2 目录的实现

考虑目录分配和目录管理算法的选择——目录文件
线性列表：
- 包含内容：文件名列表，指向数据块的指针
- 优点：简单
- 缺点：
  - 执行时时间开销较大
  - 线性搜索
- 改进：cache 存储最近使用的目录项内容；
哈希表：
- 包含内容：从文件名计算的哈希值，指向文件名的指针
- 优点：搜索时间减少；但要处理冲突问题
- 缺点：
  - 哈希表的大小与哈希函数有关，即可管理的文件数与哈希函数有关
  - 搜索需要计算时间

9.7 容错技术

9.7.1 容错技术的概念

用于提高磁盘系统可靠性的技术。

物理格式化（formatting）：
- 将硬盘空间分区，分区控制读写操作；
- 分区组成：头部Header（引导代码、分区表信息、C盘位置），数据区和Trailer（包含ECC）；
- ECC（error-correcting code）
  - 写和更新时
  - 读、计算和检查时
磁盘容错技术/系统容错技术SFT（System Fault Tolerance）的三个级别：
- SFT-1：低级，防止磁盘表面缺陷而引起的数据丢失。
- SFT-2：中级，防止驱动器、控制器故障引起的不正常。
- SFT-3：高级，利用冗余的存储信息作错误校正。

9.7.2 SFT的三个级别

==SFT-1==

写后读校验（Read After Write Verfication）：

实现：将写入磁盘的数据立即读入内存另一缓冲区，并与原数据比较是否一致。
防止将数据写入有缺陷的盘块中。

热修复重定向（Hex-Fix Redirection）：

实现：磁盘设置热修复重定向区，存放发现盘块有缺陷时的待写数据，并登记。
防止将数据写入有缺陷的盘块中。

双目录和双FAT：

实现：在不同盘或同一盘的不同区域，建立2份目录和FAT。
系统初启时验证一致性。

==STF-2==

磁盘镜像（Disk Mirroring）：

实现：用同一磁盘控制器来控制2个完全相同的驱动器，每次对主磁盘写入数据后，采用写后读校验方式，写入备份盘。
缺点：
- 磁盘利用率低
- 无法处理控制器故障

磁盘双工（Disk Duplexing）：

实现：将2台磁盘驱动器分别连到2个磁盘控制器、通道上，并镜像成对。
优缺点：
- 2个独立通道，可并行写操作
- 读数据时，可采用分离搜索技术，从响应快的通道取数据。

==STF-3==

廉价磁盘冗余阵列RAID（Redundant Array of Inexpensive Disk）

思想：用1台磁盘阵列控制器，管理、控制一组磁盘驱动器，组成高度可靠、快速的大容量磁盘系统。
基础：并行交叉存取，提高速度

为提高磁盘的访问速度，在多磁盘驱动器系统中，将每一盘块中的数据分成若干部分，分别存储到各个不同磁盘的相同位置，达到并行存取的目的。

RAID分级——8级

RAID优点：
- 高可靠性。除 RAID0 外，都采用了冗错技术。
- 采用磁盘并行交叉存取，I/O速度快。
- 与大型磁盘系统相比，有较高的性能/价格（Performance /Cost）比。

后备系统：

==三种类型==：
- 磁带机：适用于存储顺序文件
  
  优缺点：容量大；价格低；速度慢。
- 磁盘机：
  
  利用活动盘，速度快，费用高；
  
  大容量磁盘兼做后备系统。
- 光盘：
  
  优缺点：容量大，保存期长，费用适中；速度较慢；
==二种后备方法==：
- 全量转储
- 增量转储：设置转储时间表，记录每个文件最后一次的转储时间。每次转储时，判断在最后一次转储后是否发生变化

9.8 性能改善

改善性能，提高文件访问的快速性和数据一致性等指标。

衡量文件系统性能的主要指标：
- 文件访问的快速性
- 文件数据的可共享性
- 文件系统使用的方便性
- 数据的安全性
- 数据的一致性
快速性的3个层次：
- 改进文件的目录结构及目录检索算法，减少对文件的查找时间
- 选择好的文件存储结构，提高访问速度
- 提高磁盘I/O速度，以提高数据传输速度
方法：
- 设置磁盘高速缓冲（Disk Cache）
- 优化磁盘的数据分布
- 预读/延迟写

Chapter 10. I/O设备管理

10.1 I/O设备管理概述

设备管理的目的是为了合理地利用外部设备和实现虚拟设备。

10.1.1 I/O设备类型

==按信息组织特征分==：

块设备：硬盘、U盘
字符设备：键盘、鼠标
网络设备：网卡（以包(packet)为基本单位）

==按使用特性分==：

输入设备
输出设备
存储设备：硬盘、网卡

==按交互对象分==：

人机交互设备
与CPU交互的设备：硬盘、控制器、时钟（Timer/Clock）
计算机间交互的设备：网卡、路由器、交换机

==按共享属性分==：

独占设备【程序独占】：人机交互设备、输出设备
共享设备：硬盘
虚拟设备：虚拟网卡、虚拟键盘

==按传输速率分==：

低速设备：键盘、鼠标（几~几百KB）
中速设备：打印机（几千KB）
高速设备：硬盘（ms级）

注：

在Linux系统中，文件的类型包含普通文件、目录文件、特殊文件。通常把设备作为特殊文件来处理。

10.1.2 设备管理器（DC）

Device Controller，能操作端口、总线或设备的电子设备，是CPU与I/O设备间的接口，属于可编址设备，可具有多个设备地址，分为字符设备控制器和块设备控制器。

功能：

接收和识别CPU发出的命令（通过I/O逻辑）
完成数据的存储转发
记录连接设备的状态
识别所连接设备的地址

组成：

与CPU的接口
与设备的接口
I/O逻辑

10.1.3 I/O端口及通道

==I/O端口==（port）：

是可编址设备的另外一种。

功能：

完成数据的存储转发；
记录连接设备的状态；
识别所连接设备的地址。

组成——四个寄存器：

Data-in 寄存器：主机程序获取输入
Data-out 寄存器：主机程序输出数据
状态寄存器
控制寄存器

==通道==：

虽然在CPU与I/O设备之间增加了设备控制器后，可以大大减少CPU对I/O的干预，但是当主机所配置的外设很多时，CPU的负担仍然很重，因此，在CPU和设备控制器之间又增设了通道。I/O通道是一种输入输出处理机，是为了提高CPU利用率而引入的。

有题库说法：

通道是独立于CPU的，专门负责数据输入输出传输工作的处理单元。

与CPU的区别：

仅能执行与I/O有关指令
无独立主存，与CPU共享

类型：

字节多路通道（Byte Multiplexor Channel）
数组选择通道（Block Selector Channel）
数组多路通道（Block Multiplexor Channel）

由于通道成本较高，并非每一个I/O设备都由自己的独立控制器和通道，会造成系统吞吐量下降，带来I/O的瓶颈问题。

10.1.4 I/O系统的结构与功能

==I/O系统的结构==：

微型机I/O系统
- 无通道的I/O系统
- 以CPU为中心
下图bus指总线。

串行端口并行端口

主机I/O系统
- 有通道的I/O系统
- 以主存为中心
- 属于四级结构

==I/O系统的功能==：

设备分配：按照一定策略，为申请设备的进程分配设备；
==设备映射==：（如用户程序所写的打印机—–>Epson/Hp，方便用户使用）
- 隐藏物理设备的细节
  
  对设备进行抽象，隐藏物理设备的实现细节，向上层提供少量、抽象的读/写命令
- 实现设备的无关性
  
  用户不仅可以使用抽象的I/O命令，还可以使用抽象的逻辑设备名来使用设备
提高处理机和I/O设备的利用率：I/O设备之间（缓冲）、I/O设备与处理机之间应该能够并行操作
对I/O设备进行控制
确保对设备的正确共享：独占设备/共享设备
错误处理

10.1.5 I/O系统软件结构

设备独立性软件可以提供统一接口
中断处理程序直接与I/O硬件进行交互
设备驱动程序是进程和设备控制器之间的通信程序，实现上次抽象I/O请求到I/O设备具体命令和参数的转换，由设备制造厂商提供
设备独立性软件：现代OS中的I/O系统基本上都实现了与设备无关性；I/O软件独立于具体使用的物理设备，包括设备命名、设备分配、数据缓冲和数据高速缓冲等软件

10.2 I/O控制方式

I/O控制方式发展宗旨：尽量减少CPU对I/O的干预，提高CPU利用率。

10.2.1 早期I/O控制方式（轮询）

早期无中断系统，CPU对I/O设备的控制采取轮询（polling）的可编程I/O方式，每次传输一个字（符）

==“忙测试”==过程：

CPU向I/O控制器发一条I/O命令，启动I/O设备
置设备状态寄存器中busy为1
循环测试busy，直到busy=0

缺点：CPU的绝大部分时间都处于等待I/O设备完成数据I/O的循环测试中。

10.2.2 中断驱动I/O控制方式

有中断系统
工作过程：
- CPU向设备控制器DC发一条I/O命令，并继续执行
- DC接到命令，控制设备I/O
- I/O完成，DC向CPU发中断信号
- CPU检查I/O中是否有错：有：处理；无：继续
每次传输一个字（符）

10.2.3 DMA控制方式

DMA即Direct Memory Access(直接存储器访问)，DMA方式中，传输将数据从一个地址空间复制到另一个地址空间。DMA方式每次传输一个块或几个连续块，常用于块设备的I/O控制。

DMA控制器的组成：

DR：数据寄存器
MAR：内存地址寄存器
DC：数据计数器（count），存放多少字节
CR：命令寄存器

特点：

I/O基本单位是数据块(Block)
I/O是直接从设备入内存，或相反
一块/多块完成后，CPU才干预

工作过程：

进程I/O，CPU给控制器发送：I/O命令、内存/外存起址、传输字节数
CPU启动控制器进行数据I/O
I/O完成，DMA向CPU发送中断信号

DMA控制方式采用的是cycle steeling（周期窃取）技术【周期指CPU周期】。

10.2.4 通道控制方式

工作过程：

进程I/O，CPU向通道发送I/O命令，给出通道程序的起址、需访问的设备等；
通道执行通道程序，完成I/O，并中断通知CPU。
每次传输一组数据块

与DMA相比：

通道所需要CPU干预更少；
多个不连续块的传递和存储；
减轻CPU的负载。

注：

该方式数据传送的效率最高。

通道程序：由一系列通道指令组成，包括有关操作码、内存地址、计数、结束位P等

操作	R	计数	内存地址
WRITE	0	80	813
WRITE	0	140	1034
WRITE	1	60	5830
WRITE	1	300	2000
WRITE	0	50	1650
WRITE	1	250	2720

10.3 缓冲管理

缓冲引入的原因：

缓和CPU与I/O设备间速度不匹配的矛盾
减少CPU对I/O的干预
提高CPU和I/O设备之间的并行程度（主要目的）

缓冲的种类：

单缓冲
双缓冲
循环缓冲
缓冲池

10.3.1 单缓冲(Single Buffer)

工作方式：进程发出I/O请求时，操作系统在主存分配一个缓冲区，通过缓冲区完成I/O。

将一块输入数据输入缓冲区，时间T
系统将缓冲区数据复制到用户区，时间M
CPU对输入的数据处理，时间C

[例]从块设备输入处理

性能分析：

无缓冲区时，每一块数据的处理时间为： T+C
单缓冲区时，每一块数据的处理时间为：MAX(C,T)+M

由于M<<T或C，所以上式近似为：MAX(C,T)

10.3.2 双缓冲(Double Buffer)

为了加快输入和输出速度，提高设备利用率，引入了双缓冲机制，也称为缓冲对换（Buffer Swapping）。

每一块数据的处理时间为：MAX(C,T)。

10.3.3 循环缓冲

循环缓冲区中包含多个大小相同的缓冲区，可分为三类：

装输入数据的空缓冲区R
已装满数据的缓冲区G
计算进程正在使用的现行工作缓冲区C

循环缓冲区的使用：

Getbuf过程
Releasebuf过程

存在P-C问题（生产者Producer-消费者Consumer问题）。

10.3.4 缓冲池

单、双、循环缓冲都属专用缓冲。缓冲池是公用缓冲，包含了一个管理的数据结构及一组操作函数的管理机制，用于管理多个缓冲区

目的：提高缓冲区的利用率，供多个进程共享

循环池的组成：

用户管理缓冲区的队列：==空缓冲队列emq、输入队列inq、输出队列outq（CPU—>输出设备）==
用于标识缓冲池中各缓冲区动态过程的工作缓冲区
- 用于收容输入数据的工作缓冲区hin
- 用于收容输出数据的工作缓冲区hout
- 用于提取输入数据的工作缓冲区sin
- 用于提取输出数据的工作缓冲区sout

两个过程：

Getbuf(type)过程：用于从type指定的队列中得到一个缓冲区
Putbuf(type,number)：用于将参数number所指示的缓冲区，挂在type所指队列的队尾
每个队列type设置2个信号量：资源信号量RS(type)和互斥信号量MS(type)——用于出入队列的控制

void Getbuf(unsigned type) {
    wait(RS(type)); //RS是用来线程同步信号量，初始值是缓冲区的大小
    wait(MS(type));        
    B(number)=Takebuf(type); 
    //number是指缓冲队列对应的位置，获得缓冲队列的缓冲区
    signal(MS(type));
}

void Putbuf(type, number) {
    wait(MS(type));
    Addbuf(type, number); //释放后归还缓冲区
    signal(MS(type));
    signal(RS(type));
}

工作方式：

收容输入（从I/O设备输入到缓冲）：

进程需输入数据时，调用Getbuf(emq)【emq—empty-queue】，得到一个空缓冲作为收容输入的工作缓冲区hin
将数据输入到hin中
调用**Putbuf(inq,hin)**，将hin入inq的队尾

提取输入（从inq提取所需数据）：

计算进程需输入数据时，调用**Getbuf(inq)**，取得一个缓冲区作为提取输入工作缓冲区sin
sin—>计算进程
计算进程使用完成后，调用**Putbuf(emq,sin)**，将缓冲区挂到emq队尾

类似地，有：

收容输出：

hout<—Getbuf(emq)
将data存在到hout中
putbuf(outq,hout)

提取输出：

sout<—Getbuf(outq)
sout—>输出设备
putbuf(emq,sout)

10.4 设备分配

功能：进程发出I/O请求时，按照一定的策略将I/O所需设备分配给进程。

10.4.1 设备分配的过程

设备分配中的数据结构：

设备控制表DCT(Device Control Table)：系统为每个设备配置一张DCT,用于记录该设备的相关参数。
控制器控制表COCT(Controller Control Table)
通道控制表CHCT(Channel Control Table)
系统设备表SDT(System Device Table)

进程需要使用设备时，若忙，会挂起进程（挂在设备的等待队列）。

设备分配应考虑的因素：

设备的固有属性
- 独占设备：设备一旦分配，进程独占直至完成
- 共享设备：分配给多个进程，合理调度
- 虚拟设备：虚拟设备属于可共享设备，分配给多个进程
设备分配算法
- 先来先服务
- 优先级高者优先
设备分配中的安全性———->即==不能出现死锁==
- 安全分配方式：进程发出I/O请求后就进入阻塞状态，直至I/O操作完成，CPU与I/O设备顺序工作
- 不安全分配方式：进程发出I/O请求后继续运行，可以继续发出其他I/O请求，直到因等待设备而进入阻塞状态；为了避免死锁，进行设备分配之前要进行安全性计算

设备分配的过程：

分配设备
- 根据I/O请求中的物理设备名查找系统设备表SDT，找到该设备的DCT，判断DCT的状态
- 若忙，将请求I/O进程的PCB挂在设备队列上；否则计算设备分配的安全性，保证安全的前提下分配给进程
分配控制器
- 给请求I/O的进程分配设备后，在DCT中找到与该设备连接的控制器的COCT（控制器控制表,Controller Control Table），判断COCT的状态
- 若忙，将请求I/O进程的PCB挂在控制器等待队列上，否则将控制器分配给进程
分配通道
- 在COCT中找到与控制器连接的通道的CHCT，判断CHCT的状态
- 若忙，将请求I/O进程的PCB挂在通道等待队列上，否则将通道分配给进程

只有在==设备、控制器、通道==都分配成功时，设备分配才成功，可启动I/O设备进行数据传送。

10.4.2 设备独立性

也称为设备无关性：应用程序独立于具体使用的物理设备。

引入设备独立性的好处：

增加设备分配时的灵活性
- 某设备被占用，可分配其它同类空闲设备；
- 系统增加同类外设时，无需修改源程序即可使用；
- 进程使用设备故障时，系统可分配其它同类设备给进程；
易于实现I/O重定向

重定向(redirection)：I/O进程，不改变应用程序即可改变设备完成数据的I/O，例：dir>prn（输出至打印机）

设备独立性的实现：

==逻辑设备==：用户程序中使用某类设备名称（PRN）来使用该类设备；

==物理设备==：系统I/O进程实际执行I/O操作时，使用的设备名称（整数编码），物理设备直接指向某台具体设备。

逻辑设备到物理设备的映射采用逻辑设备表LUT（Logical Unit Table）。

逻辑设备名	物理设备名	驱动程序入口地址
/dev/sdb1	8，17	1024

LUT设置方式：

整个系统设置一张

特点：
- 统一管理，维护方便
- 每个进程都要去查，会产生“读者-写者”问题（即数据更新、数据查找同时进行会产生瓶颈，光是查找可以同时查找，只要一份数据copy多份即可）
- 整个系统仅设置一张，查找时间长
每个用户进程设置一张，置于进程PCB中
设置到用户中（目前操作系统采用的方式）

10.4.3 SPOOLing系统

10.4.3.1 脱机技术的概念

引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带（通过外围控制机）；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

10.4.3.2 假脱机技术

通过在高速外存设置I/O缓冲，将独占型设备改造成为可共享的虚设备。

注：

独占型设备：只允许各个进程串行使用的设备，一段时间内只能满足一个进程的请求。

可共享的虚设备：允许多个进程”同时“使用的设备（宏观上同时使用，微观上可能是”交替使用”），可以同时满足多个进程的使用请求。

SPOOLing系统即在线同时外围操作（假脱机技术），英文是Simultaneous Peripheral Operation On-Line。

注：

”输出进程“模拟脱机输出时的输出设备；

SPOOLing技术是操作系统中采用的以空间换取时间的技术，通过预输入及缓输出来减少CPU等待慢速设备的时间，将独享设备改造成共享设备。

输入井/输出井
- 磁盘上开辟的存储区域，分别容纳输入/输出数据
- 井文件：数据一般以==文件形式==组织管理
- 所有进程的数据文件链接成为队列
输入缓冲区/输出缓冲区
- 内存设置缓冲区，用于缓和CPU和磁盘之间速度不匹配的矛盾
- 分别作为输入设备输入或输出井到输出设备之间的缓冲
输入进程/输出进程
井管理程序：控制作业与磁盘井之间的信息交换

SPOOLing系统的工作过程：

输入过程：SPOOLing输入程序Spi主要工作是负责将输入设备上的作业以作业为单位通过内存缓冲区传输至输入井，并建立JCB，同时维持后备队列。
Spi是系统中一个独立的进程，无任务时，处于等待状态（睡眠状态）。Spi被唤醒的时机有3个， Spi被唤醒后，根据收到的信号作相应的工作：
- 当输入设备上有作业输入请求时：Spi启动相应通道，将作业输入到内存输入缓冲区，自身进入等待；
- 当输入设备工作结束时： Spi根据输入缓冲区中的内容，建立JCB（Job Control Block，记录作业的有关信息），并在输入井中为作业分配空间，启动磁盘通道将输入缓冲区中作业输到输入井，自身进入等待；
- 向磁盘输入井传输一道作业结束时：Spi将作业JCB加入后备队列，并向作业调度程序发信号，引起作业调度，自身进入等待。

利用SPOOLing系统完成打印工作（共享打印机原理分析）：

利用假脱机技术将独占型的打印机改造成为了一台供多个用户共享的打印设备

注：

虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。
系统组成：磁盘缓冲区、打印缓冲区、工作进程
当用户进程请求打印时， SPOOLing系统（存在spo）为它做两件事：
- 在输出井中为之申请一个空闲磁盘分区，并将要打印的数据送入其中；
- 再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到打印请求队列上。
打印机空闲时：输出进程取出一张打印请求表，再从输出井中取出打印数据到输出缓冲区，通过打印机进行打印（会发出信号是否还要继续打印）。

10.4.3.3 SPOOLing系统及守护进程

SPOOLing系统的特点：

提高了I/O速度：由对低速设备的I/O改为对输入/输出井的存取，缓和了CPU与低速设备的矛盾
将独占型设备改造为共享设备（变为硬盘空间）
实现了虚拟设备功能：多个进程同时（并发）地从输入/输出井存取数据

守护进程（Daemon）：

守护进程取代假脱机管理进程，是允许使用打印机的唯一进程
所有需要使用打印机进行打印的进程都需要将一份要求打印的文件放在假脱机文件队列（目录）中
如果守护进程正在睡眠，则将它唤醒，由它按照目录逐个打印，直到完成所有打印作业，然后继续睡眠

10.5 设备处理

10.5.1 设备驱动程序

设备驱动程序的功能：

接收上层软件的I/O命令，转化为具体的I/O要求，控制设备完成I/O操作
完成I/O操作的初始化工作：检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式
发出I/O命令，启动I/O设备
及时响应由控制器或通道发来的中断请求
根据用户的I/O请求，自动地构成通道程序

设备驱动程序的处理过程：

将抽象要求转换为具体要求；即将I/O命令转换为控制器可接受的命令格式；例如磁盘块号转换为盘面、道号、扇区
检查I/O请求的合法性
读出和检查设备状态
传送必要的参数；如传输字节数、内存地址（块设备的DMA方式）
设置工作方式（进程和设备控制器之间的异步/同步通信）
启动I/O设备，完成I/O

设备驱动程序的特点：

设备驱动程序与硬件密切相关
每类设备都要配置特定的驱动程序（如块设备、字符设备）
驱动程序一般由设备厂商根据操作系统要求编写
操作系统仅对设备驱动的接口提出要求

10.5.2 用户层I/O软件

系统调用：应用程序通过系统调用间接调用OS中的I/O过程，对I/O设备进行操作
库函数：用户程序通过调用对应的库函数使用系统调用

C语言中的提供的I/O方面的库函数也是I/O系统的组成部分，主要包括对文件和设备进行读/写的库函数、控制/检查设备状态的库函数等
假脱机系统（Simultaneous Peripheral Operation On-Line）：将一台物理I/O设备虚拟为多台逻辑I/O设备

注：

Posix规范：Posix规范定义了操作系统(很多时候针对的是类Unix操作系统)应该为应用程序提供的接口标准,从而保证了应用程序在源码层次的可移植性。

Chapter 11.操作系统的安全机制

11.1 安全威胁及现状

操作系统面临的攻击方法：

伪装（masquerading）：指参与通信的一方假装是合法用户，获得通常不被允许的访问权限或特权。
重放攻击（replay attack）：恶意或欺诈的有效数据重播。重放攻击可以由发起者，也可以由拦截并重发该数据的敌方进行。攻击者利用网络监听或者其他方式盗取认证凭据，之后再把它重新发给认证服务器。
消息篡改（message modification）：替换授权用户所传递的消息。
中间人攻击（man-in-middle attack）：攻击者伪装成接收者的发送者，反之亦然

威胁手段：

蠕虫、计算机病毒、特洛伊木马、后门/天窗、逻辑炸弹、内部/外部泄密
堆栈和缓冲区溢出
- 利用程序中的bug来获得目标系统的未经授权访问或特权升级
- 对目标系统是致命的攻击，难检测和防止
隐蔽通道（covert channel）：
- 不受安全策略控制、违反安全策略的信息泄露路径
- 分为隐蔽存储通道、隐蔽定时通道
拒绝服务攻击：
- 破坏系统或设施的合法使用的手段，常基于网络
- 不可能防止和解决，难以确定造成系统减速的原因

操作系统安全基础：

Lampson访问矩阵：

保护域Protection domain
访问控制列表Access Control list(ACL)
权能列表Capability list(C_list)

强制保护系统(Mandatory Protection System)：

访问矩阵——不信任的进程能篡改保护系统——未授权访问的安全问题
仅由可信管理员通过可信软件来修改状态的保护系统
包含状态：强制保护状态、标记状态、Transition state

引用监视器（Reference Monitor）：

解决用户程序的运行控制问题引入的，目的是在用户与系统资源之间实施一种授权访问关系
J.P. Anderson的定义：以主体（用户等）所获得的引用权限为基准，验证运行中的程序（对程序、数据、设备等）的所有引用
监控主体和客体之间授权访问关系的部件：
- 引用监视器接口Reference Monitor Interface
- 授权模块Authorization Module
- 策略存储Policy Store

可信计算基（Trust Computing Base）：

计算机系统内保护装置的总体，包括硬件、固件、软件和负责执行安全策略的组合体。
组成：
- 操作系统安全内核
- 具有特权的程序和命令
- 处理敏感信息的程序
- 与TCB实施安全策略有关的文件，如：进程创建、进程切换、内存页面管理、部分的文件、I/O管理
特点：尽可能小、尽可能trustworthy

11.2 安全机制概述

ISO：是一种技术、一些软件或实施一个或更多安全服务的过程。

普通的安全机制
- 信任的功能性
- 事件检测
- 审计跟踪
- 安全恢复
[注]操作系统安全目标：
- 依据系统安全策略对用户的操作进行存取控制，防止用户对计算机资源的非法存取
- 标识系统中的用户并进行身份鉴别
- 监督系统运行的安全性
- 保证系统自身的安全性和完整性
特殊的安全机制
- 硬件安全机制
  - 存储保护：保护存储器中的数据
  - 运行保护：分层保护环
  - I/O保护：I/O读写操作保护
- 标识与鉴别
- 访问控制
- 最小特权管理
- 可信通路
- 安全审计

11.3 标识与鉴别

标识（identify）：用户向系统表明身份
- 系统可以识别的用户内部名称：用户名、登录ID
- 具有唯一性、不可伪造
鉴别：对用户宣称的身份标识有效性进行校验和测试的过程。
- 鉴别方法：
  - 口令——账号、密码——所知
    
    存在的问题：弱口令、缺省密码、简单密码、密码的存储——sniffer、keylogger、爆破
  - 密码验证：PKI、磁卡、认证令牌等——所有
  - 生物鉴别方法：面部、指纹、虹膜、声音等特征——所是
  - IP地址、地理位置——所在
  - 可信计算基：与鉴别相关的认证机制
- 防止假冒攻击的重要技术
UNIX/Linux系统标识：

存放在/etc/passwd和/etc/shadow中

基于口令的鉴别方法
- UNIX的密码系统：
  - Hash密码——one way、计算代价大
  - 所存在的问题：密码不是真正意义上的随机——52个大小写字母+10个数字+32个特殊字符=94——字典攻击（人类大约有1，000，000通用的密码）
- 口令空间大小：字母表规模和口令长度的函数
  
  设S：口令空间，L：口令的最大有效期，R：单位时间内可能的口令猜测数，P：口令有效期内被猜出的可能性，则：
  
  $P＝(L×R)/S$。
- 口令长度计算：
  
  设S：口令空间，A：字母表大小，M：口令长度，则：$M=\left\lfloor\log _{A} S\right\rfloor$。
- 破解口令的方法：
  - 社会工程学方法
  - 字典程序
  - 口令文件窃取
  - 暴力破解
- 口令安全性的维护：系统管理员和用户
  - 系统管理员：初始化系统口令、初始口令分配、口令更改认证、用户ID、使用户ID重新生效、培训用户
  - 用户：安全意识、更改口令
- 基于PKI的鉴别方法
  - PKI：Public Key Infrastructure，公开密钥基础设施
  - 用于保证网上传递信息的安全、真实、完整和不可抵赖
Windows系统身份鉴别过程：
在网络环境中实现用户身份鉴别，要求同一合法用户可以在不同主机上执行身份鉴别。分三步走：
- 身份认证信息管理
- 客户机软件功能
- 服务器软件功能

11.4 访问控制

基本任务：防止用户对系统资源的非法使用，保证对客体的所有直接访问都是被认可的。

保护存储在计算机上的个人信息
保护重要信息的机密性
维护计算机内信息的完整性
减少病毒感染机会，从而延缓这种感染的传播
保证系统的安全性和有效性，以免受到偶然的和蓄意的侵犯

措施：

确定要保护的资源
授权
确定访问权限
实施访问权限

访问控制技术：

自主访问控制（Discretionary Access Control）

允许对象的属主制定对该对象的保护策略。
强制访问控制（Mandatory Access Control）

用于保护系统确定的对象，对此对象，用户不能进行更改。
基于角色的访问控制（Role Based Access Control）

引入角色，通过对角色设置权限来规范用户和权限之间的关系。
基于属性的访问控制（Attribute Based Access Control）
- 通过动态计算一个或一组属性是否满足某种条件来进行授权判断
- 可实现不同粒度的权限控制
- 规则复杂，给管理员带来维护和追查方面的代价

11.4.1 自主访问控制(DAC)

基于对主体(属主)或主体所属组(属组)的识别来限制对客体的访问。
基于行的自主访问控制机制（跟着主体[用户]走）
- 能力表：权限字
- 前缀表：包括受保护的客体名和主体对它的访问权限
- 口令：每个客体有一个
基于列的自主访问控制机制（跟着客体[文件、资源]走）
- 保护位：对客体的拥有者及其他主体、主体组，规定的对该客体访问模式的集合
- 访问控制表：对某个特定资源制定任意用户的访问权限
基于权限位的访问控制

==实现——基于权限位的访问控制==

访问权限的定义与表示：读、写、执行——三位二进制
用户划分为组，文件由属主（owner）、属组（group）、其他（others）控制。

基本访问控制判断算法：判断用户U是否可对文件F执行a（r、w、x或-）操作。

设：F的属主和属组分别为Uo和Go。
当U等于Uo时，如果F的左3权限位串中与a对应的位为1，则允许U对F执行a操作，否则，不允许U对F执行a操作，判定结束。
当Go是U的属组时，如果F的中3权限位串中与a对应的位为1，则允许U对F执行a操作，否则，不允许U对F进行a操作，判定结束。
如果F的右3权限位串中与a对应的位为1，则允许U对F执行a操作，否则，不允许U对F进行a操作。

==进程与用户和文件的关系==：

进程p是用户Up的化身；
进程P的行为逻辑由文件F来确定
真实用户属性：RUID+RGID
有效用户属性：EUID+EGID
进程访问判定时：g(进程) —> EUID+EGID

==执行过程==：

用户U启动进程P时：
- 进程P的RUID和EUID <— 用户U的ID
- 进程P的RGID和EGID <— 用户U的属组ID
进程P变身且映像文件F允许时：
- 进程P的EUID <— 文件F的属主ID——（1）【条件：文件F有SETUID标记】
- 进程P的EGID <— 文件F的属组ID——（2）【条件：文件F有SETGID标记】

进程的有效身份变化：

[例]（1）假设用户启动进程proc1，执行程序progf1。进程proc1的运行将显示什么信息？

结果：China – England – Australia– Canada – America。

==（2）==进程P显示England时，对文件filex的权限？

进程P执行到程序progf2时，文件progf2的属组ID变为grp2，对文件filex拥有读、执行（rx）权限。

自主访问控制的缺陷：

合法用户的修改授权，操作系统无法却分是用户的正常行为还是恶意攻击者的非法操作
攻击者可以利用DAC完成秘密信息的窃取

11.4.2 强制访问控制(MAC)

对系统中的每个进程、文件、IPC客体赋予相应安全属性，当进程访问客体时，调用其安全属性和访问方法，比较进程的安全属性与客体的安全属性，确定是否允许访问（大于则允许访问）。

三种方法：

限制访问控制：限制用户程序修改其拥有的访问控制权限
过程控制：对系统用户编程过程采取措施
系统限制：通过系统自动完成对系统功能实时的一些限制

强制访问控制对用户和文件两个方面：BLP—–>MLS层级安全

用户下级对上级具有汇报权限。

实例：Multics方案

用户和文件（包括目录文件）都有相应的安全级
用户对文件的访问遵循下述安全策略：
- 仅当用户的安全级别不低于文件的安全级别时，用户才可以读文件；
- 仅当用户的安全级别不高于文件的安全级别时，用于才可以写文件；
常用于政府部门、军事和金融等领域，一般和自主访问控制结合使用

11.4.3 其他访问控制方法

基于角色的访问控制（RBAC）：

基于任务的访问控制——93～97年R.K.Thomas等人提出的（TBAC）

基本思想：从任务角度进行授权控制，在任务执行前授予权限，在任务完成后回收权限。
主动安全模型

基于角色-任务的访问控制——98年G.Coulouria等人提出的T-RBAC

基于规则策略的访问控制E.Bertino等人提出的

面向服务的工作流访问控制（SOWAC）

基于状态的访问控制

基于行为属性的访问控制（ABAC）

11.5 最小特权管理

特权（Privilege）是进程执行一些安全相关操作所必须具备的权限。

滥用特权将导致非常严重的后果。特权进程的可信性面临巨大的挑战：

漏洞
恶意代码
缓冲区溢出

解决方法：有效支持最小特权原则（Principle of Least Privilege）

11.5.1 最小特权原则概述

是系统安全中最基本的原则之一，要求赋予系统中每个使用者执行授权任务所需的限制性最强的一组特权，即最低许可。其常见的形式有：

基于文件的特权机制
- 固定特权集
- 可继承特权集
基于进程的特权机制

三大特权集：

最大特权集
可继承特权集
有效特权集

要较好地支持最小特权原则，应遵循以下原则：

以进程（程序）逻辑为中心进行特权控制；
以进程特权相关属性为依据对进程生命周期进行划分，进程在各个阶段中根据进程逻辑分配不同的特权；
用户特权属性仅作为一种全局性的约束；
在部分特权中引入特权参数提供更细粒度的特权控制；
与原有机制的尽量兼容，对应用程序透明。

11.5.2 特权管理职责

系统安全管理员SSO：对系统资源和应用定义安全级、定义用户组、为所有用户赋予安全级、限制隐蔽通道活动的机制
审计员AUD：设置审计参数、修改和删除审计信息
操作员OP：启动或停止系统、设置终端参数、允许或不允许登录
网络管理员NET：管理网络软件，配置网络协议

11.6 可信通路和审计机制

可信通路：

是用户能借以直接同可信计算基（TCB）通信的一种机制
建立可信通路的方法：安全注意键（在Windows中是Ctrl+Alt+System Request）

审计机制：

日志：记录的事件或统计数据
安全审计：对日志记录的分析并以清晰的、能理解的方式表述系统信息，即对系统中有关安全的活动进行记录、检查及审核
作用：审计事件：主体、客体
类型：
- 系统级审计：登录情况、登录识别号、每次登录尝试的日期和具体时间、每次退出的日期和时间、所使用的设备、登录后运行的内容
- 应用级审计：打开和关闭数据文件、读取、编辑和删除记录或字段的特定操作、打印报告等用户活动
- 用户级审计：用户直接启动的所有命令、用户所有鉴别和认证尝试、用户所访问的文件和资源等方面

组成：

日志记录器：收集数据——系统日志、应用程序日志、安全日志
分析器：分析数据
通告器：通报结果

审计日志格式：

Chapter 12.操作系统的安全模型

12.1 安全模型概述

安全模型的定义：

对安全策略所表达的安全需求进行简单、抽象和无歧义的描述

安全策略即有关管理、保护和发布敏感信息的法律、规定和实施细则。

即描述对某个安全策略需要用哪种机制来满足
描述安全策略和它实现机制之间关联的框架

安全策略的目标：

明确表达安全需求
为设计开发安全系统提供方针

安全策略的分类：

形式化安全模型（例：BLP模型）
非形式化安全模型

安全策略的特点：

精确、无歧义
易理解
一般性
安全策略的显式表示

开发安全模型的一般性步骤：

确定外部接口需求（用户）
确定内部安全需求（内部安全策略、机制）
设计策略执行的操作规则
确定已知元素（保护内容）
论述一致性和正确性：形式化验证
- 归纳验证
- 模型检验
论述关联性

安全模型的分类：

按实现策略分：保密性模型、完整性模型、混合性模型
按实现方式分：访问控制模型、信息流模型

12.2 访问控制模型

12.2.1 组成元素及操作

==组成元素==：

对象集$O$，主体集$S$。
实体间的关系——存放在矩阵$A$中，用$a[s,o]$表示。
系统的保护状态集是三元关系$(S,O,A)$
操作集$T_{1},T_{2}$
原始状态$X_{0}=(S_{0},O_{0},A_{0})$，连续状态：$X_{1},X_{2},……$

==操作指令及结果的形式化表达==：

创建一个新主体$s$：$s$不属于$S$

指令：createsubjects
结果：$S^{\prime}=S \cup{s}$，$O^{\prime}=O \cup{s}$，（进程属于主体、客体）

$(∀y∈O’)[a’[s，y]=\varnothing],(∀x∈S’)[a’[x，s]=\varnothing],(∀x∈S)(∀y∈O)[a’[x,y]=a[x,y]]$

创建一个新对象$o$：

$O^{\prime}=O \cup{o}$，
$(∀x∈S)(∀y∈O)[a’[x，y]=a[x，y]],(∀x∈S)[a’[x，{o}]=\varnothing]]$

向$a[s,o]$中加入权限$r$：

$(∀x∈S)(∀y∈O)[a’[x,y]=a[x,y]]$
对$x=s,y=o,[a’[x,y]=a[x,y]\cup{r}]$

删除主体$s$：

$S^{\prime}=S -{s}$，$O^{\prime}=O -{s}$
对$(∀x∈S’)(∀y∈O’)[a’[x，y]=a[x，y]]$

12.2.2 模型总结

访问控制矩阵是计算机安全中的原始抽象机制，可以表达任何可以表达的安全规则
可以采用命令形式改变、转换系统的状态
特权弱化法可以产生条件，规定如果主体不拥有权限，就不能把这个权力授予任何人

注：

特权包括switch、copy、owner等；

特权弱化法指主体不把自己不拥有的特权给其他主体。

BLP模型：机密性模型

包括有两部分安全策略：自主安全策略和强制安全策略；

Biba模型：完整性模型

实现：对系统每个主体和每个客体分配一个完整级别（包含两部分——密级和范畴）；安全策略分为非自主策略与自主策略；

Clark-Wilson模型：完整性模型

核心：良构事务（well-formal transaction）和任务分离机制

良构事务：指一个用户不能任意操作数据，只能用一种能够确保数据完整性的受控方式操作数据；
良构事务处理机制：用户不能任意处理数据，而必须以确保数据完整性的受限方式来对数据进行处理
任务分离机制：将任务分成多个子集，不同的子集由不同的人来完成。

中国墙模型：混合性模型

非形式化描述：层次结构

最底层：标识单个企业的数据项
中间层：企业数据集，客体按所属的企业分组
最高层：利益冲突类，由具有竞争关系的企业数据集组成。

ShiQuLiZhi

https://www.qqzzss.top/2022/08/14/theory/li-lun-01-cao-zuo-xi-tong-li-lun/

本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShiQuLiZhi !

理论知识

Python基础

2022-08-14 Python与数据处理

程序设计 Python

计算机网络理论

2022-08-13 计算机学科理论

理论知识计算机网络

操作系统理论

Chapter 1.操作系统概述

1.1 操作系统的类型

1.1.1 基本类型

1.1.2 分时系统

1.1.3 实时系统

1.2 操作系统的工作控制方式

1.3 操作系统的硬件保护

1.4 操作系统的设置目标、功能和特征

1.5 操作系统安全相关概念

Chapter 2.进程与线程

2.1 程序执行方式

2.2 前趋图

2.3 进程的概念和特征

2.4 进程控制块PCB

2.4.1 主要内容

2.4.2 组织方式

2.5 进程的状态

2.5.1 进程的三个基本状态

2.5.2 新建状态和终止状态

2.5.3 挂起/解挂状态

2.6 进程控制

2.6.1 内核定义

2.6.2 内核基本功能

2.6.3 进程创建——进程图

2.7 线程

2.7.1 概述

2.7.2 多线程的优点

Chapter 3.进程调度

3.1 调度的类型

3.2 调度方法选择准则

3.2.1 面向用户（4准则）

3.2.2 面向系统（3准则）

3.3 调度算法

3.3.1 先来先服务FCFS

3.3.2 短作业优先SJF

3.3.3 时间片轮转RR

3.3.4 优先权调度Priority

3.3.5 高响应比优先HRRN

3.3.6 多级队列调度

3.3.7 多级反馈队列

3.4 实时系统调度

3.5 多核系统调度

Chapter 4.进程同步和通信

4.1 进程同步的概念

4.2 进程同步机制应遵循的原则

4.3 解决进程互斥问题

4.3.1 软件方法

4.3.2 硬件方法

4.3.2.1 检测和设置指令TS

4.3.2.2 Swap指令

4.4 信号量机制

4.4.1 信号量机制的一些概念

4.4.2 整型信号量机制

4.4.3 记录型信号量机制

4.3.4 AND信号量集机制

4.3.5 一般信号量集机制

4.5 经典进程同步问题

4.5.1 生产者-消费者问题

4.5.2 读者-写者问题

4.5.3 哲学家进餐问题

4.6 管程机制

4.6.1 管程组成

4.6.2 管程和进程的比较

4.7 进程通信

4.7.1 进程间通信类型

4.7.2 消息传递系统

4.7.2.1 直接通信方式

4.7.2.2 间接通信方式(信箱)

4.7.2.3 消息传递系统其他概念

4.7.3 管道通信

Chapter 5.死锁

5.1 死锁(Deadlock)概述

5.1.1 死锁定义

5.1.2 死锁产生的原因及必要条件

5.2 资源分配图

5.3 死锁的处理办法

5.3.1 死锁的预防

5.3.2 死锁的避免(银行家算法)

5.3.3 死锁的检测