1 计算机系统概述
1.1 操作系统的基本概念
1.1.1 操作系统的概念
操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件。
1.1.2 操作系统的功能和目标
1.1.2.1 作为系统资源的管理者
处理机管理
在多道程序环境下，处理机的分配和运行都以进程（或线程）为基本单位，因而对处理机的管理可归结为对进程的管理。并发是指在计算机内同时运行多个进程，因此进程何时创建、何时撤销、如何管理、如何避免冲突、合理共享就是进程管理的最主要的任务。进程管理的主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。
存储器管理
存储器管理是为了给多道程序的运行提供良好的环境，方便用户使用及提高内存的利用率，主要包括内存分配与回收、地址映射、内存保护与共享和内存扩充等功能。
文件管理
计算机中的信息都是以文件的形式存在的，操作系统中负贲文件管理的部分称为文件系统。文件管理包括文件存储空间的管理、目录管理及文件读写管理和保护等。
设备管理
设备管理的主要任务是完成用户的IO请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓冲管理、设备分配、设备处理和虚拟设备等功能。
1.1.2.2 向上层提供方便易用的服务
命令接口
使用命令接口进行作业控制的主要方式有两种，即联机控制方式和脱机控制方式。按作业控制方式的不同，可将命令接口分为联机命令接口和脱机命令接口。
联机命令接口，用户说一句，系统跟着做一句。如命令行CMD等等
脱机命令接口，用户说一堆，系统跟着做一堆。如批处理命令接口bat等等
程序接口
程序接口由一组系统调用（也称广义指令）组成。用户通过在程序中使用这些系统调用来请求操作系统为其提供服务、如使用各种外部设备、申请分配和回收内存及其他各种要求。
普通用户不能直接使用程序接口，只能通过程序代码简介使用
1.1.2.3 对硬件机器的拓展
没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器
通常把覆盖了软件的机器成为扩充机器，又称之为虚拟机
1.1.3 操作系统的特征
1.1.3.1 并发
并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。
注意区别并行和并发的区别
并行：指两个或多个事件在同一时刻同时发生。
操作系统的并发性指计算机系统中“同时”运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。操作系统就是伴随着“多道程序技术”而出现的。因此，操作系统和程序并发是一起诞生的。
单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行
多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行
如4 核CPU，意味着可以并行地执行4个程序
1.1.3.2 共享
共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的,即分时共享
并发和共享是操作系统两个最基本的特征，两者之间互为存在的条件:①资源共享是以程序的并发为条件的，若系统不允许程序并发执行，则自然不存在资源共享问题;②若系统不能对资源共享实施有效的管理，则必将影响到程序的并发执行，甚至根本无法并发执行。
1.1.3.3 虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。
操作系统的虚拟技术可归纳为:时分复用技术，如处理器的分时共享:空分复用技术,如虚拟存储器。
1.1.3.4 异步
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
1.2 操作系统的发展与分类
1.2.1 手工操作阶段
用户在计算机上算题的所有工作都要人工千预，如程序的装入、运行、结果的输出等。
主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低
1.2.2 批处理阶段
1.2.2.1 单道批处理系统
引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出
主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。
主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。
1.2.2.2 多道批处理系统
多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU中交替地运行，这些程序共享系统中的各种硬/软件资源。
主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。
主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。注）
[注] 无法调试程序/无法在程序运行过程中输入一些参数
操作系统正式诞生，用于支持多道程序并发运行
1.2.3 分时操作系统
分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。
主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。
1.2.4实时操作系统
为了能在某个时间限制内完成某些紧急任务而不需要时间片排队，诞生了实时操作系统。根据时间限制可分为两种情况
硬实时系统：必须在绝对严格的规定时间内完成处理，如：导弹控制系统、自动驾驶系统
软实时系统：能接受偶尔违反时间规定，如：12306火车订票系统
在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性
1.2.5 其他几种操作系统
网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机之间的通信。（如：Windows NT 就是一种典型的网络操作系统，网站服务器就可以使用）
分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。
个人计算机操作系统：如Windows XP、MacOS，方便个人使用。
1.3 操作系统的运行环境
1.3.1 操作系统的运行机制
CPU 上会运行两种程序，一种是操作系统内核程序，一种是应用程序
内核是操作系统最重要最核心的部分，也是最接近硬件的部分
操作系统的功能未必都在内核中，如图形化用户界面GUI
应用程序只能使用“非特权指令”，如：加法指令、减法指令等
操作系统内核作为“管理者”，有时会让CPU执行一些“特权指令”，如：内存清零指令。这些指令影响重大，只允许“管理者”——即操作系统内核来使用
CPU 有两种状态，“内核态”和“用户态”
处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
内核态→用户态：执行一条特权指令——修改PSW的标志位为“用户态”，这个动作意味着操作系统将主动让出CPU使用权
用户态→内核态：由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权
1.3.2 中断和异常的概念
“中断”会使CPU由用户态变为内核态，使操作系统重新夺回对CPU的控制权
“中断”是让操作系统内核夺回CPU使用权的唯一途径
中断可以分为内中断和外中断
内中断：与当前执行的指令有关，中断信号来源于CPU内部，也称异常、例外
陷阱、陷入：由陷入指令引发，是应用程序故意引发的
故障：由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去。如：缺页故障。
终止：由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。如：整数除0、非法使用特权指令
外中断：与当前执行的指令无关，中断信号来源于CPU外部
时钟中断：由时钟部件发来的中断信号
I/O中断请求：由输入/输出设备发来的中断信号
中断处理过程见计组第七章
1.3.3 系统调用
“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务
系统调用的功能可以分为
设备管理：完成设备的请求/释放/启动等功能
文件管理：完成文件的读/写/创建/删除等功能
进程控制：完成进程的创建/撤销/阻塞/唤醒等功能
进程通信：完成进程之间的消息传递/信号传递等功能
内存管理：完成内存的分配/回收等功能
应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。
陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态
发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行
1.4 操作系统的体系结构
原语是一种特殊的程序，具有原子性。也就是说，这段程序的运行必须一气呵成，不可被“中断”
大内核和微内核
大内核：将操作系统的主要功能模块都作为系统内核，运行在核心态
优点:高性能
缺点:内核代码庞大，结构混乱，难以维护
微内核：只把最基本的功能保留在内核
优点:内核功能少，结构清晰，方便维护
缺点:需要频繁地在核心态和用户态之间切换，性能低
变态的过程是有成本的，要消耗不少时间，频繁地变态会降低系统性能
2 进程管理
2.1 进程与线程
2.1.1 进程的概念和特征
2.1.1.1 进程的概念
程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
进程（Process）：是动态的，是程序的一次执行过程。同一个程序多次执行会对应多个进程
动态性是进程最基本的特征
异步性会导致并发程序执行结果的不确定性。
当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）这些信息都被保存在一个数据结构PCB （Process Control Block）中，即进程控制块操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中
PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。其需要保存的信息大致分为
进程描述信息
进程标识符PID
用户标识符UID
进程控制和管理信息
CPU、磁盘、网络流量使用情况统计...
进程当前状态:就绪态/阻塞态/运行态...
资源分配清单
正在使用哪些文件
正在使用哪些内存区域
正在使用哪些I/O设备
处理机相关信息
如PSW、PC等等各种寄存器的值（用于实现进程切换)
进程的组成
PCB
程序段：程序的代码(指令序列)
数据段：运行过程中产生的各种数据
程序段、数据段、PCB三部分组成了进程实体（进程映像）
引入进程实体的概念后，可把进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
2.1.1.2 进程的特征
相比于程序，进程有以下特征：
动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的
并发性：内存中有多个进程实体，各进程可并发执行
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"“进程同步机制"来解决异步问题
结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成
2.1.2 进程的状态与转化
进程的状态如下
进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB
当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行
如果一个进程此时在CPU上运行，那么这个进程处于“运行态”。CPU会执行该进程对应的程序（执行指令序列）
在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行
一个进程可以执行exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。
其中，运行态、就绪态和阻塞态是进程的三个基本状态
单CPU情况下，同一时刻只会有一个进程处于运行态，多核CPU情况下，可能有多个进程处于运行态
2.1.3 进程组织
在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应该用适当的方式把这些PCB组织起来。
进程的组织方式分为两种
链接方式
按照进程状态将PCB分为多个队列
操作系统持有指向各个队列的指针
索引方式
根据进程状态的不同，建立几张索引表
操作系统持有指向各个索引表的指针
2.1.4 进程控制
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
实现进程控制用“原语”实现。原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断
2.1.4.1 进程的创建
创建原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入就绪队列
引起进程创建的事件
用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程
作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
应用请求：由用户进程主动请求创建一个子进程
2.1.4.2 进程的终止
撤销原语
从PCB集合中找到终止进程的PCB
若进程正在运行，立即剥夺CPu，将CPU分配给其他进程
终止其所有子进程
将该进程拥有的所有资源归还给父进程或操作系统
删除PCB
引起进程终止的事件
正常结束，如进程自己请求终止(exit系统调用)
异常结束，如整数除以o、非法使用特权指令，然后被操作系统强行杀掉
外界干预，如Ctrl+Alt+delete，用户选择杀掉进程
2.1.4.3 进程的阻塞和唤醒
进程的阻塞
阻塞原语
找到要阻塞的进程对应的PCB
保护进程运行现场，将PCB状态信息设置为"阻塞态"，暂时停止进程运行
将PCB插入相应事件的等待队列
引起进程阻塞的事件
需要等待系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语
在事件等待队列中找到PCB
将PCB从等待队列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调度
引起进程唤醒的事件——等待的事件发生
因何事阻塞，就应由何事唤醒，因此阻塞原语唤醒原语必须成对使用
2.1.4.4 进程切换
切换原语
将运行环境信息存入PCB
PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境
引起进程切换的事件
当前进程时间片到
有更高优先级的进程到达
当前进程主动阻塞
当前进程终止
2.1.5 进程的通信
进程通信就是指进程之间的信息交换。进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。
2.1.5.1 共享存储
基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。
两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）。操作系统只负责提供共享空间和同步互斥工具（如P、V操作）
2.1.5.2 消息传递
进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
直接通信方式：消息直接挂到接收进程的消息缓冲队列上
间接通信方式：消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。Eg
[Eg] 计网中的电子邮件系统
2.1.5.3 管道通信
“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区
管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道。
数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
如果没写满，就不允许读。如果没读空，就不允许写。
数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。
2.1.6 线程的概念和多线程模型
2.1.6.1 线程的基本概念
有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
可以把线程理解为“轻量级进程”。线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。线程则作为处理机的分配单元。
传统进程机制中、进程是资源分配、调度的基本单位，引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
2.1.6.2 线程的属性
线程几乎不拥有系统资源，每个线程都有一个线程ID、线程控制块(TCB)
不同线程可以执行相同的程序，同一个服务程序被不同的用户调用时，操作系统把他们创建不同的线程
同一进程的不同线程间共享进程的资源
线程是处理机调度的单位，多个线程可以并发执行。多CPU计算机中，各个线程可占用不同的CPU
一个线程被创建后，便开始了它的生命周期，直到终止。线程也有就绪、阻塞、运行三种基本状态
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预，同一进程中的线程切换，不会引起进程切换，不同进程中的线程切换，会引起进程切换。切换同进程内的线程，系统开销很小，切换进程，系统开销较大
2.1.6.3 线程的实现方式
线程的实现方式可以分为用户级线程和内核级线程
2.1.6.3.1 用户级线程
用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
2.1.6.3.2 内核级线程
内核级线程的管理工作由操作系统内核完成。
线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
操作系统会为每个内核级线程建立相应的TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
2.1.6.4 多线程模型
一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
多对多模型：n 用户及线程映射到m 个内核级线程（n >= m）。每个用户进程对应m 个内核级线程。
克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞
2.2 处理机调度
2.2.1 调度的概念
2.2.1.1 调度的基本概念
当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。
2.2.1.2 调度的层次
一个作业从提交开始直到完成，往往要经历以下三级调度
高级调度（作业调度）。按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
中级调度（内存调度）。按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
低级调度（进程调度/处理机调度）。按照某种策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。
2.2.1.3 三级调度的联系
2.2.2 调度的时机、切换和过程
2.2.2.1 进程调度的时机
需要进行进程调度与切换的情况
当前运行的进程主动放弃处理机
进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞（如等待I/O）
当前运行的进程被动放弃处理机
分给进程的时间片用完
有更紧急的事需要处理（如I/O中断）
有更高优先级的进程进入就绪队列
不能进行进程调度与切换的情况
在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区中。
在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）
2.2.2.2 进程调度方式
非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统
2.2.2.3 进程切换与过程
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了：
对原来运行进程各种数据的保存
对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）
进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
2.2.3 调度的基本准则
2.2.3.1 CPU利用率
CPU利用率：指CPU “忙碌”的时间占总时间的比例。
式中，t1为忙碌的时间，t2为总时间,η为利用率
Eg：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？
CPU利用率=(5+5)/(5+5+5)= 66.66% 打印机利用率=5/15= 33.33%
2.2.3.2 系统吞吐量
系统吞吐量：单位时间内完成作业的数量，其等于总共完成了多少作业除以总共花了多少时间
Eg：某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？
10/100 = 0.1 道/秒
2.2.3.3 周转时间
周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。（周转时间= 作业完成时间– 作业提交时间）它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
平均周转时间=各作业周转时间之和 \ 作业数
带权周转时间=作业周转时间 \ 作业实际运行的时 = (作业完成时间– 作业提交时间) \ 作业实际运行的时间
平均带权周转时间= 各作业带权周转时间之和 \作业数
2.2.3.4 等待时间
等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。
2.2.3.5 响应时间
响应时间，指从用户提交请求到首次产生响应所用的时间。
2.2.4 典型的调度算法
2.2.4.1 先来先服务(FCFS)调度算法
按照作业/进程到达的先后顺序进行服务，用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列，属于非抢占式的算法
优点：公平、算法实现简单，不会导致饥饿
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利
周转时间= 完成时间- 到达时间P1=7-0=7；P2=11-2=9；P3=12-4=8；P4=16-5=11 带权周转时间= 周转时间/运行时间P1=7/7=1；P2=9/4=2.25；P3=8/1=8；P4=11/4=2.75 等待时间= 周转时间– 运行时间P1=7-7=0；P2=9-4=5；P3=8-1=7；P4=11-4=7 平均周转时间= (7+9+8+11)/4 = 8.75 平均带权周转时间= (1+2.25+8+2.75)/4 = 3.5 平均等待时间= (0+5+7+7)/4 = 4.75
2.2.4.2 短作业优先(SJF)
最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法”SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
周转时间= 完成时间- 到达时间P1=7-0=7；P3=8-4=4；P2=12-2=10；P4=16-5=11 带权周转时间= 周转时间/运行时间P1=7/7=1；P3=4/1=4；P2=10/4=2.5；P4=11/4=2.75 等待时间= 周转时间– 运行时间P1=7-7=0；P3=4-1=3；P2=10-4=6；P4=11-4=7 平均周转时间= (7+4+10+11)/4 = 8 平均带权周转时间= (1+4+2.5+2.75)/4 = 2.56 平均等待时间= (0+3+6+7)/4 = 4
最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度
周转时间= 完成时间- 到达时间P1=16-0=16；P2=7-2=5；P3=5-4=1；P4=11-5=6 带权周转时间= 周转时间/运行时间P1=16/7=2.28；P2=5/4=1.25；P3=1/1=1；P4=6/4=1.5 等待时间= 周转时间– 运行时间P1=16-7=9；P2=5-4=1；P3=1-1=0；P4=6-4=2 平均周转时间= (16+5+1+6)/4 = 7 平均带权周转时间= (2.28+1.25+1+1.5)/4 = 1.50 平均等待时间= (9+1+0+2)/4 = 3
2.2.4.3 高响应比优先(HRRN)算法
在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务即可用于作业调度，也可用于进程调度。非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
响应比={等待时间+要求服务时间} \ {要求服务时间}
综合考虑了等待时间和运行时间（要求服务时间）等待时间相同时，要求服务时间短的优先（SJF 的优点）要求服务时间相同时，等待时间长的优先（FCFS 的优点）对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
0时刻：只有P1 到达就绪队列，P1上处理机 7时刻（P1主动放弃CPU）： 就绪队列中有P2 (响应比=(5+4)/4=2.25)、P3((3+1)/1=4)、P4((2+4)/4=1.5)， 8时刻（P3完成）： P2(2.5)、P4(1.75) 12时刻（P2完成）：就绪队列中只剩下P4
2.2.4.4 时间片轮转(RR)
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
优点：公平；响应快，适用于分时操作系统；不会导致饥饿
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
时间片大小为2
0时刻（P1(5)）:0时刻只有P1到达就绪队列，让P1上处理机运行一个时间片 2时刻（P2(4)→P1(3)）:2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。 此时P2排在队头，因此让P2上处理机。（注意： 2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列） 4时刻（P1(3)→P3(1)→P2(2)）:4时刻，P3到达，先插到就绪队尾，紧接着，P2下处理机也插到队尾 5时刻（P3(1)→P2(2)→P4(6)）:5时刻，P4到达插到就绪队尾（注意：由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中） 6时刻（P3(1)→P2(2)→P4(6)→P1(1)）：6时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度 7时刻（P2(2)→P4(6)→P1(1)）：虽然P3的时间片没用完，但是由于P3只需运行1个单位的时间，运行完了会主动放弃处理机，因此也会发生调度。队头进程P2上处理机。 9时刻（P4(6)→P1(1)）：进程P2时间片用完，并刚好运行完，发生调度，P4上处理机 11时刻（P1(1)→P4(4) ）：P4时间片用完，重新回到就绪队列。P1上处理机 12时刻（P4(4) ）：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机 14时刻（）：就绪队列为空，因此让P4接着运行一个时间片。 16时刻：所有进程运行结束
如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
一般来说，设计时间片时要让切换进程的开销占比不超过1%
2.2.4.5 优先级调度算法
每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中。抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
通常
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好I/O型进程（或称I/O繁忙型进程）
2.2.4.6 多级反馈队列调度算法
规则：
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
只有第k 级队列为空时，才会为k+1 级队头的进程分配时间片
用于进程调度。抢占式的算法。在k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k 级队列队尾。
对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾
只有第k 级队列为空时，才会为k+1 级队头的进程分配时间片,被抢占处理机的进程重新放回原队列队尾
2.3 进程同步
2.3.1 进程同步的基本概念
2.3.1.1 进程同步
进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
2.3.1.1 临界资源
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源，两种资源共享方式为
互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源
对临界资源的互斥访问，可以在逻辑上分为如下四个部分：
do {
/*
进入区,负责检查是否可进入临界区，
若可进入，则应设置正在访问临界资
源的标志（可理解为“上锁”），以阻
止其他进程同时进入临界区
*/
entry section;
critical section; //临界区,访问临界资源的那段代码
exit section; //退出去,负责解除正在访问临界资源的标志（可理解为“解锁”）
remainder section; //剩余区,做其他处理
} while(true)临界区也可称为“临界段”,是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段.
2.3.1.2 进程互斥
当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程推出临界区后，另一经常才允许区访问次临界资源。为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
2.3.2 实现临界区互斥的基本方法
2.3.2.1 软件实现方法
2.3.2.1.1 单标志法
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
int turn = 0; //turn表示当前允许进入临界区的进程号
//P0进程
while (turn != 0); //进入区
critical section; //临界区
turn = 1; //退出区
remainder section; //剩余区
//P1进程
while (turn != 1); //进入区
critical section; //临界区
turn = 0; //退出区
remainder section; //剩余区该算法可以实现“同一时刻最多只允许一个进程访问临界区”，单标志法存在的主要问题是：违背“空闲让进”原则。
2.3.2.1.2 双标志先检查法
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0 号进程P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i] 设为true，之后开始访问临界区。
bool flag[2]; //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;
flag[1] = false;
//P0进程
while(flag[1]); //进入区
flag[0] = true; //进入区
critical section; //临界区
flag[0] = false; //退出区
remainder section; //剩余区
//P1进程
while(flag[0]); //如果此时P0想进入临界区，P1就循环等待
flag[1] = true; //标记为P1进程想要进入临界区
critical section; //访问临界区
flag[1] = false; //访问完临界区，修改标记为P1不想使用临界区
remainder section;双标志先检查法优点：不用交替进入，可连续使用；主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
2.3.2.1.3 双标志后检查法
算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
bool flag[2]; //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;
flag[1] = false;
//P0进程
flag[0] = true; //进入区
while(flag[1]); //进入区
critical section; //临界区
flag[0] = false; //退出区
remainder section; //剩余区
//P1进程
flag[1] = true; //标记为P1进程想要进入临界区
while(flag[0]); //如果此时P0想进入临界区，P1就循环等待
critical section; //访问临界区
flag[1] = false; //访问完临界区，修改标记为P1不想使用临界区
remainder section;因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
2.3.2.1.4 Peterson 算法
算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
bool flag[2]; //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;
flag[1] = false;
int turn = 0; //turn表示优先让哪个进程进入临界区
//P0进程
flag[0] = true; //进入区
turn = 1; //进入区
while (flag[1] && turn == 1); //进入区
critical section; //临界区
flag[0] = false; //退出区
remainder section; //剩余区
//P1进程
flag[1] = true; //表示自己想进入临界区
turn = 0; //可以优先让对方进入临界区
while (flag[0] && turn == 0); //对方详尽，且最后一次是自己礼让，那就循环等待
critical section;
flag[1] = false; //访问完临界区，表示不想访问临界区
remainder section;Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。
2.3.2.2 硬件实现方法
2.3.2.2.1 中断屏蔽方法
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)
2.3.2.2.2 TestAndSet指令
简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑
//布尔型共享变量lock表示当前临界区是否被加锁，true表示已加锁
bool TestAndSet(bool *lock){
bool old;
old = *lock; //old用来存放lock原来的值
*lock = true; //无论之前是否已经加锁，都设置为true
return old; //返回lock原来的值
}该指令实现进程互斥的算法描述为
while TestAndSet(&lock); //上锁并检查
... //临界区代码段
lock = false; //解锁
... //剩余区代码段若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境；缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
2.3.2.2.3 Swap指令
有的地方也叫 Exchange指令，或简称XCHG指令。Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑
// 交换两个字的内容
void swap(boolean *a, boolean *b){
boolean temp;
temp = *a;
*a = *b;
*b = temp;
}Swap指令实现进程互斥的代码
key = true;
while(key != false)
Swap(&lock, &key);
... //进程的临界区代码段
lock = false;
... //进程的其他代码逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为 false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境；缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
2.3.3 信号量
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1 的信号量。只能被一对原语所访问：wait(S) 原语和signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为P、V操作（来自荷兰语proberen 和verhogen）。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为P(S)、V(S)
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
2.3.3.1 整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
int S = 1; //初始化整型信号量S，表示当前可用资源数
void wait(int S){ //wait原语，相当于进入区
while (S <= 0); //如果资源数不够，就循环等待
S = S - 1; //如果资源数够，则占用一个资源
}
void signal(int S){ //signal原语，相当于退出区
S = S + 1; //使用完资源后，在退出区释放资源
}存在的问题：不满足“让权等待”原则，会发生“忙等”
2.3.3.2 记录型信号量
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量
// 记录型信号量的定义
typedef struct{
int value; //剩余资源数
struct process *L //等待队列
}semaphore;
//某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
S.value--;
if (S.value < 0){
/*
如果剩余资源数不够，使用block原语使进程从
运行态进入阻塞态，并把挂到信号量S 的等待
队列（即阻塞队列）中
*/
block(S.L)
}
}
//进程使用完资源后，通过signal原语释放
void signal(semaphore S){
S.value ++ ;
if (S.value <= 0){.
/*
释放资源后，若还有别的进程在等待这种资源，则使用
wakeup 原语唤醒等待队列中的一个进程，该进程从阻
塞态变为就绪态
*/
wakeup(S.L);
}
}2.3.3.3 利用信号量实现进程互斥
分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
设置互斥信号量mutex，初值为1
在进入区P(mutex)——申请资源
在退出区V(mutex)——释放资源
// 记录型信号量的定义
typedef struct{
int value; //剩余资源数
struct process *L //等待队列
}semaphore;
semaphore mutex = 1;
P1(){
...;
P(mutex); //使用临界资源前需要加锁
...; //临界区代码段
V(mutex); //使用临界资源后需要解锁
...;
}
P2(){
...;
P(mutex); //使用临界资源前需要加锁
...; //临界区代码段
V(mutex); //使用临界资源后需要解锁
...;
}对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
2.3.3.4 利用信号量实现进程同步
进程同步：要让各并发进程按要求有序地推进。
分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量S, 初始为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)
semaphore S = 0;
P1(){
代码1;
代码2;
V(S);
代码3;
}
P2(){
P(S);
代码4;
代码5;
代码6;
}上述代码保证了代码4 一定是在代码2 之后执行
利用信号量实现前驱关系实际上可以理解为每两个之间的同步，即对每一对关系设置一个信号量，分别做上述操作即可
PV操作题目分析步骤：
关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）
2.3.4 经典同步问题
2.3.4.1 生产者-消费者问题
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。
semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量
producer (){
while(1){
生产一个产品;
P(empty); //消耗一个空闲缓冲区
P(mutex);
把产品放入缓冲区;
V(mutex);
V(full); //增加一个产品
}
}
consumer (){
while(1){
P(full); //消耗一个产品（非空缓冲区）
P(mutex);
从缓冲区取出一个产品;
V(mutex);
V(empty); //增加一个空闲缓冲区
使用产品;
}
}实现互斥是在同一进程中进行一对PV操作
实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V
实现互斥的P操作一定要在实现同步的P操作之后,否则可能导致死锁。两个V操作顺序可以交换。
2.3.4.2 多生产者-多消费者问题
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。
semaphore apple = 0; //盘子中有几个苹果
semaphore orange = 0; //盘子中有几个橘子
semaphore plate = 1; //盘子中还可以放多少个水果
dad (){
while(1){
准备一个苹果;
P(plate);
P(mutex);
把苹果放入盘子;
V(mutex);
V(apple);
}
}
mom (){
while(1){
准备一个橘子;
P(plate);
P(mutex);
把橘子放入盘子;
V(mutex);
V(orange);
}
}
daughter (){
while(1){
P(apple);
P(mutex);
从盘中取出苹果;
V(mutex);
V(plate);
吃掉苹果;
}
}
son (){
while(1){
P(orange);
P(mutex);
从盘中取出橘子;
V(mutex);
V(plate);
吃掉橘子;
}
}本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区，因此即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象
2.3.4.3 吸烟者问题
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟)
semaphore offer1 = 0; //桌上组合一的数量
semaphore offer2 = 0; //桌上组合二的数量
semaphore offer3 = 0; //桌上组合三的数量
semaphore finish = 0; //抽烟是否完成
int i = 0; //用于实现“三个抽烟者轮流抽烟”
provider (){
while(1){
if(i==0) {
将组合一放桌上;
V(offer1);
} else if(i==1){
将组合二放桌上;
V(offer2);
} else if(i==2){
将组合三放桌上;
V(offer3);
}
i = (i+1)%3;
P(finish);
}
}
smoker1 (){
while(1){
P(offer1);
从桌上拿走组合一；卷烟；抽掉；
V(finish);
}
}
smoker2 (){
while(1){
P(offer2);
从桌上拿走组合二；卷烟；抽掉；
V(finish);
}
}
smoker3 (){
while(1){
P(offer2);
从桌上拿走组合三；卷烟；抽掉；
V(finish);
}
}2.3.4.4 读者-写者问题
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出。
semaphore rw=1; //用于实现对共享文件的互斥访问
int count = 0; //记录当前有几个读进程在访问文件
semaphore mutex = 1; //用于保证对count变量的互斥访问
//semaphore w = 1; //用于实现"写优先"
writer (){
while(1){
//P(W); //设置另一个互斥信号量,在无写进程时请求加入
P(rw); //写之前“加锁”
写文件…
V(rw); //写完了“解锁”
//V(W); //设置另一个互斥信号量,恢复对共享文件的访问
}
}
reader (){
while(1){
P(mutex); //各读进程互斥访问count
if(count==0) //由第一个读进程负责
P(rw); //读之前“加锁”
count++; //访问文件的读进程数+1
V(mutex);
读文件…
P(mutex); //各读进程互斥访问count
count--; //访问文件的读进程数-1
if(count==0) //由最后一个读进程负责
V(rw); //读完了“解锁”
V(mutex);
}
}若两个读进程并发执行，则count=o时两个进程也许都能满足if条件，都会执行P(rw)，从而使第二个读进程阻塞的情况。出现上述问题的原因在于对count变量的检查和赋值无法一气呵成，因此可以设置另一个互斥信号量来保证各读进程对count的访问是互斥的。
2.3.4.5 哲学家进餐问题
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i 左边的筷子编号为i，右边的筷子编号为(i+1)%5。
semaphore chopstick[5]={1,1,1,1,1}; //初始化信号量
semaphore mutex = 1; //互斥地取筷子
Pi (){ //i号哲学家的进程
while(1){
P(mutex); //在取筷子前获得互斥量
P(chopstick[i]); //拿左
P(chopstick[(i+1)%5]); //拿右
V(mutex); //释放取筷子的信号量
吃饭…
V(chopstick[i]); //放左
V(chopstick[(i+1)%5]); //放右
思考…
}
}2.3.4 管程
信号量机制存在的问题:编写程序困难、易出错1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分――一种高级同步机制。管程是一种特殊的软件模块，有这些部分组成:
局部于管程的共享数据结构说明;
对该数据结构进行操作的一组过程;
对局部于管程的共享数据设置初始值的语句;
管程有一个名字。
管程的基本特征:
局部于管程的数据只能被局部于管程的过程所访问;
一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
每次仅允许一个进程在管程内执行某个内部过程。
2.4 死锁
2.4.1 死锁的概念
2.4.1.1 死锁的定义
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。
2.4.1.2 死锁、饥饿、死循环的区别
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。
2.4.1.3 死锁产生的必要条件
产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）。如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
2.4.1.4 发生死锁的时机
对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2 分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
2.4.2 死锁的处理策略
预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
2.4.3 预防死锁
破坏互斥条件
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
破坏不剥夺条件
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。破坏不剥夺条件有以下两种方案：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
该策略的缺点：
实现起来比较复杂。
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
反复地申请和释放资源会增加系统开销，降低系统吞吐量。
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
破坏请求和保持条件
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。该策略实现起来简单，但也有明显的缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
破坏循环等待条件
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
该策略的缺点：
不方便增加新的设备，因为可能需要重新分配所有的编号；
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
必须按规定次序申请资源，用户编程麻烦。
2.4.4 避免死锁
2.4.4.1 系统安全状态
所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配咨源之前总是要考虑到最坏的情况
如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
2.4.4.2 银行家算法
核心思想:在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
假设系统中有n个进程，m种资源。每个进程在运行前先声明对各种资源的最大需求数，则可用一个n×m的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K表示进程Pi最多需要K个资源Rj。同理，系统可以用一个n×m的分配矩阵Allocation表示对所有进程的资源分配情况。Max - Allocation =Need矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。某进程Pi向系统申请资源，可用一个长度为m的一维数组Request,表示本次申请的各种资源量。
银行家算法步骤:
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配，更改各数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态
具体如下：
如果便转向2.;否则认为出错。
如果，便转向3.﹔否则表示尚无足够资源，Pi必须等待。
系统试探着把资源分配给进程Pi，并修改相应的数据〈并非真的分配，修改数值只是为了做预判):
Available = Available - Request_i;
Allocation[i, j] = Allocation[i, j] + Request_i[j];
Need[i, j] = Need[i, j]-Request,[i]操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配;否则，恢复相应数据，让进程阻塞等待。
安全性算法步骤:
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
不断重复上述过程，看最终是否能让所有进程都加入安全序列。
2.4.5 死锁的检测和解除
如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：
①死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
②死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。
2.4.5.1 死锁的检测
2.4.5.1.1 资源分配图
为了能对系统是否已发生了死锁进行检测，必须：
用某种数据结构来保存资源的请求和分配信息；
提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
系统死锁可以利用资源分配图来描述
含有两个结点：
进程结点:对应一个进程；
资源结点:对应一类资源，一类资源可能有多个；
含有两种边：
进程结点—>资源结点:表示进程想申请几个资源(每条边代表一个)；
资源节点—>进程结点∶表示已经为进程分配了几个资源（每条边代表一个)
2.4.5.1.2 死锁定理
如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…
如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）；如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程。
检测死锁的算法：
在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。
进程Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2 就满足这样的条件。根据1）中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
2.4.5.2 死锁的解除
一旦检测出死锁的发生，就应该立即解除死锁。
解除死锁的主要方法有：
资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
3 内存管理
3.1 内存管理概念
3.1.1 内存管理的基本原理和要求
内存可存放数据。程序执行前需要先放到内存中才能被CPU处理，主要作用是缓和CPU与硬盘之间的速度矛盾
内存管理的功能有
操作系统负责内存空间的分配与回收
操作系统需要提供某种技术从逻辑上对内存空间进行扩充
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰
为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。
3.1.1.1 内存的装入和连接
创建进程首先要将程序和数据装入内存，将用户源程序变为可在内存中执行的程序，通常需要以下步骤
编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）
链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
装入（装载）：由装入程序将装入模块装入内存运行
内存的装入模块在装入内存时，有以下三种方式
绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。绝对装入只适用于单道程序环境。程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。
静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。采用动态重定位时允许程序在内存中发生移动。
链接的三种方式：
静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。
3.1.1.2 内存保护
在内存分配前，需要保护操作系统不受用户的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法：
在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。
3.1.2 连续分配管理方式
连续分配：指为用户进程分配的必须是一个连续的内存空间。
3.1.2.1 单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护注。
缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
[注] eg：早期的PC操作系统MS-DOS
3.1.2.2 固定分区分配
为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合例1
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分例2
[例1] 钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序
[例2] 划分多个小分区、适量中等分区、少量大分区
操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。
优点：实现简单，无外部碎片。
缺点：a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b.会产生内部碎片，内存利用率低。
3.1.2.3 动态分区分配
动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。例
[例] 假设某计算机内存大小为64MB，系统区8MB，用户区共56 MB…
把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。
动态分区分配没有内部碎片，但是有外部碎片。如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。
内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。 外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配
首次适应算法
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
最佳适应算法
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。
最坏适应算法，又称最大适应算法（Largest Fit）
算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
邻近适应算法
算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）综合来看，四种算法中，首次适应算法的效果反而更好
3.1.3 非连续分配管理方式
非连续分配：为用户进程分配的可以是一些分散的内存空间。
3.1.3.1 基本分页存储管理方式
3.1.3.1.1 分页存储的几个基本概念
将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。注2
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。（注：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费）
[注2] 初学易混——页、页面vs页框、页帧、物理页
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表通常存在PCB（进程控制块）中
一个进程对应一张页表
进程的每个页面对应一个页表项
每个页表项由“页号”和“块号”组成
页表记录进程页面和实际存放的内存块之间的映射关系
每个页表项的长度是相同的
Eg：假设某系统物理内存大小为4GB，页面大小为4KB，则 每个页表项至少应该为多少字节？ 内存块大小=页面大小=4KB= 212 B 4GB的内存总共会被分为232 / 212 = 220个内存块 内存块号的范围应该是0 ~ 220 -1 内存块号至少要用20 bit来表示 至少要用3B来表示块号（3*8=24bit）
页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）
J号内存块的起始地址= J * 内存块大小
i号页表项的存放地址= X + 3*I
3.1.3.1.2 基本地址变换机构
特点：虽然进程的各个页面是离散存放的，但是页面内部是连续存放的
通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
如果要访问逻辑地址A，则
确定逻辑地址A对应的“页号”P,页号=逻辑地址/页面长度（取除法的整数部分），即
找到P号页面在内存中的起始地址（需要查页表）
确定逻辑地址A的“页内偏移量”W,页内偏移量=逻辑地址%页面长度（取除法的余数部分）,即
逻辑地址A对应的物理地址= P号页面在内存中的起始地址+页内偏移量W
若页面大小L为1KB，页号2对应的物理块b=8，计算逻辑地址A=2500的物理地址E
P=2500/1K=2 W=2500%1K=452 E=8×1024+452=8644
在计算机内部，地址是用二进制表示的，如果页面大小刚好是2的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成（页号，页内偏移量）
假设某计算机用32个二进制位表示逻辑地址，页面大小为4KB = 212B = 4096B 0号页的逻辑地址范围应该是0~4095，用二进制表示应该是： 00000000000000000000000000000000 ~ 00000000000000000000111111111111 1号页的逻辑地址范围应该是4096~8191，用二进制表示应该是： 00000000000000000001000000000000 ~ 00000000000000000001111111111111 2号页的逻辑地址范围应该是8192~12287，用二进制表示应该是： 00000000000000000010000000000000 ~ 00000000000000000010111111111111
Eg：逻辑地址2，用二进制表示应该是00000000000000000000000000000010 页号= 2/4096 = 0 = 00000000000000000000，页内偏移量= 2%4096 = 2 = 000000000010 Eg：逻辑地址4097，用二进制表示应该是00000000000000000001000000000001 页号= 4097/4096 = 1 = 00000000000000000001，页内偏移量= 4097%4096 = 1 = 000000000001
如果每个页面大小为2KB，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
假设物理地址也用32个二进制位表示，则由于内存块的大小=页面大小，因此： 0号内存块的起始物理地址是00000000000000000000000000000000 1号内存块的起始物理地址是00000000000000000001000000000000 2号内存块的起始物理地址是00000000000000000010000000000000 3号内存块的起始物理地址是00000000000000000011000000000000
根据页号可以查询页表，而页表中记录的只是内存块号，而不是内存块的起始地址！
号内存块的起始地址内存块大小
假设通过查询页表得知1号页面存放的内存块号是9（1001），则 9号内存块的起始地址= 9*4096 = 00000000000000001001000000000000 则逻辑地址4097对应的物理地址=页面在内存中存放的起始地址+页内偏移量=（00000000000000001001000000000001）
如果页面大小刚好是2的整数幂，则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址
如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是2K个内存单元 如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有2M个页面
理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。
3.1.3.1.3 具有快表的地址变换机构
快表，又称联想寄存器（TLB，translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
引入快表后，地址的变换过程如下，
CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）
由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）
例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？ (1+100) 0.9 + (1+100+100) 0.1 = 111 us 有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100) 0.9 + (100+100) 0.1 =110.9 us 若未采用快表机制，则访问一个逻辑地址需要100+100 = 200us 显然，引入快表机制后，访问一个逻辑地址的速度快多了。
3.1.3.1.4 两级页表
单极页表存在以下问题
页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
为了解决以上问题，把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表
若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面
例：某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位？
页面大小= 4KB =212B，按字节编址，因此页内偏移量为12位 页号= 40 - 12 = 28位 页面大小= 212B，页表项大小= 4B ，则每个页面可存放212 / 4 = 210 个页表项 因此各级页表最多包含210 个页表项，需要10 位二进制位才能映射到210 个页表项，因此每一级的页 表对应页号应为10位。总共28位的页号至少要分为三级
两级页表的访存次数分析（假设没有快表机构）
第一次访存：访问内存中的页目录表
第二次访存：访问内存中的二级页表
第三次访存：访问目标内存单元
3.1.3.2 基本分段存储管理方式
基本分段存储管理方式与“分页”最大的区别就是离散分配时所分配地址空间的基本单位不同
3.1.3.2.1 分段
进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址。分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。
在上述例子中，若系统是按字节寻址的，则 段号占16位，因此在该系统中，每个进程最多有216 = 64K个段 段内地址占16位，因此每个段的最大长度是216 = 64KB。
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高
段号的位数决定了每个进程最多可以分几个段 段内地址位数决定了每个段的最大长度是多少
3.1.3.2.2 段表
程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称“基址”）和段的长度。各个段表项的长度是相同的
例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号16位,段内地址16位），因此用16位即可表示最大段长。物理内存大小为4GB（可用32位表示整个物理内存地址空间）。因此，可以让每个段表项占16+32 = 48位，即6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M + K*6
3.1.3.2.3 地址变换
根据逻辑地址得到段号、段内地址
判断段号是否越界。若S≥M，则产生越界中断，否则继续执行
查询段表，找到对应的段表项，段表项的存放地址为F+S*段表项长度，检查段内地址是否超过段长。若W≥C，则产生越界中断，否则继续执行
计算得到物理地址，访问目标内存单元
3.1.3.3 分段、分页管理的对比
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的；段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址；分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的
分页（单级页表）：第一次访存—查内存中的页表，第二次访存—访问目标内存单元。总共两次访存；分段：第一次访存—查内存中的段表，第二次访存—访问目标内存单元，总共两次访存。与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。
3.1.3.4 段页式管理方式
段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成
段号的位数决定了每个进程最多可以分几个段 页号位数决定了每个段最大有多少页 页内偏移量决定了页面大小、内存块大小是多少
在上述例子中，若系统是按字节寻址的，则 段号占16位，因此在该系统中，每个进程最多有216 = 64K个段 页号占4位，因此每个段最多有24 = 16页 页内偏移量占12位，因此每个页面\每个内存块大小为212 = 4096 = 4KB
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，段号是隐含的。
每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。
实现地址变换的过程：
根据逻辑地址得到段号、页号、页内偏移量
判断段号是否越界。若S≥M，则产生越界中断，否则继续执行
查询段表，找到对应的段表项，段表项的存放地址为F+S*段表项长度
检查页号是否越界，若页号≥页表长度，则发生越界中断，否则继续执行
根据页表存放块号、页号查询页表，找到对应页表项
根据内存块号、页内偏移量得到最终的物理地址，访问目标内存单元
3.2 虚拟内存管理
3.2.1 虚拟内存的基本概念
3.2.1.1 传统存储管理方式的特征
传统存储管理很多暂时用不到的数据也会长期占用内存，导致内存利用率不高，他们具有以下两个特征
一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
3.2.1.2 局部性原理
高速缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。快表机构就是将近期常访问的页表项副本放到更高速的联想寄存器中，其依赖的就是局部性原理
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的）
3.2.1.3 虚拟存储器的定义和特征
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。虚拟内存是操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。
虚拟内存有以下三个主要特征：
多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
3.2.1.4 实现虚拟内存技术
虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。
虚拟内存的实现有以下三种方式
请求分页存储管理
请求分段存储管理
请求段页式存储管理
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。注1若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。注3
[注1] 操作系统要提供请求调页（或请求调段）功能
[注3] 操作系统要提供页面置换（或段置换）的功能
3.2.2 请求分页管理方式
请求分页系统建立在基本分页系统之上，为了支持虚拟存储器功能而增加了请求调页和页面置换功能
3.2.2.1 页表机制
与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。因此，请求页表项增加了四个字段
状态位：是否已调入内存
访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位：页面调入内存后是否被修改过
外存地址：页面在外存中的存放位置
3.2.2.2 缺页中断机构
在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断
一条指令在执行期间，可能产生多次缺页中断。
3.2.2.3 地址变换机构
找到对应页表项后，若对应页面未调入内存，则产生缺页中断，之后由操作系统的缺页中断处理程序进行处理
快表中有的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面
只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
需要用某种“页面置换算法”来决定一个换出页面
换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/换出太频繁，会有很大的开销。
页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。
3.2.3 页面置换算法
页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
3.2.3.1 最佳置换算法(OPT)
最佳置换算法（OPT，Optimal）：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
例：假设系统为某进程分配了三个内存块，并考虑到有一下页面号引用串（会依次访问这些页面）：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
整个过程缺页中断发生了9次，页面置换发生了6次。
缺页率= 9/20 = 45%
3.2.3.2 先进先出(FIFO)置换算法
先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面。把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
例：假设系统为某进程分配了三个内存块，并考虑到有以下页面号引用串：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
分配四个内存块时，缺页次数：10次
分配三个内存块时，缺页次数：9次
只有FIFO算法会产生Belady异常解释。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差
[解释] Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
3.2.3.3 最近最久未使用(LRU)置换算法
最近最久未使用置换算法（LRU，least recently used）：每次淘汰的页面是最近最久未使用的页面。赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。
例：假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7
该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
3.2.3.4 时钟(CLOCK)置换算法
时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，NotRecently Used）简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）
改进型的时钟置换算法：
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位——第一优先级：最近没访问，且没修改的页面
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0——第二优先级：最近没访问，但修改过的页面
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位——第三优先级：最近访问过，但没修改的页面
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。——第四优先级：最近访问过，且修改过的页面
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
3.2.4 页面分配策略
3.2.4.1 驻留集大小
对于分页式的虚拟内存，在进程准备执行时，不需要也不可能把-一个进程的所有页都读入主存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。
若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少
驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小
分配方式有
固定分配:操作系统为每个进程分配一组固定数目的物理块，在进程运行其间不再改变，即大小不变
可变分配:先为每个进程分配一定数目的物理块，在进程运行期间，可即，驻留集大小可变
置换方式有
局部置换:发生缺页时只能选进程自己的物理块进行置换。
全局置换:可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
根据以上，现代操作系统通常采用三种策略：
固定分配局部置换:系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
可变分配全局置换:刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
可变分配局部置换:刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理课，直至该进程缺页率趋势适当当程度;反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块
可变分配全局置换:只要缺页就给分配新物理块 可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块
3.2.4.2 调入页面的时机
预调页策略:根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。
请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘l/O操作，因此I/O开销较大。
3.2.4.3 从何处调入页面
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区通常采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘I/O速度比文件去的更快
系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
UNIX方式:运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
3.2.5 抖动
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
3.2.6 工作集
工作集:指在某段时间间隔里，进程实际访问页面的集合。
区别驻留集:指请求分页存储管理中给进程分配的内存块的集合。
操作系统会根据“窗口尺寸”来算出工作集。
工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如 一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法――选择一个不在工作集中的页面进行淘汰。
[如] 窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
4 文件管理
4.1 文件系统基础
文件—就是一组有意义的信息/数据集合
4.1.1 文件的概念
4.1.1.1 文件的属性
文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
类型：指明文件的类型
位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
大小：指明文件大小
保护：对文件进行保护的访问控制信息
时间、日期、用户标识：创建时间、上次修改时间，文件所有者信息
4.1.1.2 文件的基本操作
文件属于抽象数据类型。为了恰当地定义文件，需要考虑有关文件的操作。操作系统提供系统调用，它对文件进行创建、写、读、重定位、搠除和截断等操作。
创建文件。创建文件有两个必要步骤:一是在文件系统中为文件找到空间;二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能的信息。
写文件。为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作时，便更新写指针。
读文件。为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，因此当前操作位置可作为每个进程当前文件位置的指针。由于读和写操作都使用同一指针，因此节省了空间，也降低了系统复杂度。
文件重定位(文件寻址)。按某条件搜索目录，将当前文件位置设为给定值，并且不会读、写文件。
删除文件。先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
截断文件。允许文件所有属性不变，并删除文件内容，即将其长度设为О并释放其空间。这6个基本操作可以组合起来执行其他文件操作。例如，一个文件的复制，可以创建新文件、从旧文件读出并写入新文件。
4.1.2 文件的逻辑结构
所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。
4.1.2.1 无结构文件
无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”
文件内部的数据其实就是一系列字符流，没有明显的结构特性。因此也不用探讨无结构文件的“逻辑结构”问题。
4.1.2.2 有结构文件
有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。1一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。有结构文件按记录的组织形式可以分为：
顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。顺序文件有以下两种结构：第一种是串结构，记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序；第二个是顺序结构，指文件中的所有记录按关键字顺序排序
索引文件：索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。另外，可以用不同的数据项建立多个索引表。2
索引顺序文件:索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
对于含有N条记录的顺序文件，查找某关键字值的记录时，平均需要查找N/2次。在索引顺序文件中，假设N条记录分为√N组，索引表中有√N个表项，每组有√N条记录，在查找某关键字值的记录时，先顺序查找索引表，需要查找√N /2次，然后在主文件中对应的组中顺序查找，也需要查找√N/2次，因此共需查找√N/2+√N/2=√N次。显然，索引顺序文件提高了查找效率，若记录数很多，则可采用两级或多级索引
顺序文件对查找、修改、增加或删除单条记录的操作比较困难
索引文件每个记录对应一个索引表项，因此索引表可能会很大。
[1] 如：数据库表文件。
[2] 如：学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。
4.1.3 目录结构
4.1.3.1 文件控制块
FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要，最基本的还是文件名、文件存放的物理地址。
4.1.3.2 目录结构
对目录的操作如下：
搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件：当删除一个文件时，需要在目录中删除相应的目录项
显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项
操作的时候，可以有以下几种目录结构：
单级目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
单级目录实现了“按名存取”，但是不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适用于多用户操作系统。
两级目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。
允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件。两级目录结构允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类
多级目录结构
用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。
系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到目录的存放位置后，从外存读入对应的目录表；再找到目录的存放位置，再从外存读入对应目录表；最后才找到文件的存放位置。整个过程需要3次读磁盘I/O操作。
很多时候，用户会连续访问同一目录内的多个文件，显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。此时已经打开了的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”
可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。
无环图目录结构
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。
共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
4.1.3.3 索引结点
其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。
假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16 = 40个盘块。因此按照某文件名检索该目录，平均需要查询320个目录项，平均需要启动磁盘20次（每次磁盘I/O读入一块）。
若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入320/64 = 5个磁盘块。
显然，这将大大提升文件检索速度。
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
4.1.3.4 文件保护
口令保护
为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。
优点：保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的“口令”存放在系统内部，不够安全。
加密保护
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。Eg
优点：保密性强，不需要在系统中存储“密码”
缺点：编码/译码，或者说加密/解密要花费一定时间。
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。
有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题
精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。
[Eg] 如加密算法—异或加密
4.1.3.5 文件共享
4.1.3.5.1 基于索引结点的共享方式(硬链接)
索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。
索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。
若count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。
若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
当count = 0时系统负责删除文件。
4.1.3.5.2 基于符号链的共享方式（软链接）
当User3访问“ccc”时，操作系统判断文件“ccc”属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的“aaa”表项，于是就找到了文件1的索引结点。
4.2 文件系统实现
4.2.1 文件的物理结构（文件分配方式）
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换（即读/写操作、磁盘I/O）都是以“块”为单位进行的。即每次读入一块，或每次写出一块
在内存管理中，进程的逻辑地址空间被分为一个一个页面同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射
4.2.1.1 连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）——可以直接算出逻辑块号对应的物理块号，物理块号=起始块号+逻辑块号。还需要检查用户提供的逻辑块号是否合法（逻辑块号≥ 长度就不合法）因此连续分配支持顺序访问和直接访问（即随机访问）
读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。连续分配的文件在顺序读/写时速度最快，物理上采用连续分配的文件不方便拓展，且存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。。
4.2.1.2 链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
4.2.1.2.1 隐式链接
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）…从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推。因此，读入i号逻辑块，总共需要i+1次磁盘I/O。
采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。但是，采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。
4.2.1.2.2 显式链接
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table）
一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。
从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0 ~ i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。
4.2.1.3 索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。可以用固定的长度表示物理块号3，因此，索引表中的“逻辑块号”可以是隐含的。
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）…从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。
可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间
索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件，可以采用以下机制：
链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K + 1次读磁盘操作
混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。
若某文件采用两层索引，则该文件的最大长度可以到256×256×1KB = 65,536 KB = 64MB
可根据逻辑块号算出应该查找索引表中的哪个表项。如：要访问1026号逻辑块，则1026/256 = 4，1026%256 = 2
因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。
访问目标数据块，需要3次磁盘I/O。若采用三层索引，则文件的最大长度为256×256×256×1KB = 16GB
类似的，访问目标数据块，需要4次磁盘I/O
[3] 如：假设磁盘总容量为1TB=240B，磁盘块大小为1KB，则共有230个磁盘块，则可用4B表示磁盘块号
①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）
4.2.2 文件存储空间管理
4.2.2.1 存储空间的划分与初始化
4.2.2.2 文件存储器空间管理
4.2.2.2.1 空闲表法
空闲表法适用于“连续分配方式”。分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
4.2.2.2.2 空闲链表法
操作系统保存着链头、链尾指针。如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
操作系统保存着链头、链尾指针。如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高
4.2.2.2.3 位示图法
位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）
盘块号、字号、位号从0开始，若n表示字长，则
(字号,位号)=(i, j)的二进制位对应的盘块号b = ni + j
b号盘块对应的字号i = b/n，位号j = b%n
如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”
4.2.2.2.4 成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
4.2.3 文件的基本操作
4.2.3.1 创建文件
进行Create系统调用时，需要提供的几个主要参数：
所需的外存空间大小（如：一个盘块，即1KB）
文件存放路径（“D:/Demo”）
文件名（这个地方默认为“新建文本文档.txt”）
操作系统在处理Create系统调用时，主要做了两件事：
在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
根据文件存放路径的信息找到该目录对应的目录文件（此处就是D:/Demo目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
4.2.3.2 删除文件
进行Delete系统调用时，需要提供的几个主要参数：
文件存放路径（“D:/Demo”）
文件名（“test.txt”）
操作系统在处理Delete系统调用时，主要做了几件 事：
根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）
从目录表中删除文件对应的目录项。
4.2.3.3 打开文件
在很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用“打开文件”，需要提供的几个主要参数：
文件存放路径（“D:/Demo”）
文件名（“test.txt”）
要对文件的操作类型（如：r只读；rw读写等）
操作系统在处理open系统调用时，主要做了几件事：
根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。
4.2.3.4 关闭文件
进程使用完文件后，要“关闭文件”
操作系统在处理Close系统调用时，主要做了几件事：
将进程的打开文件表相应表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器count减1，若count =0，则删除对应表项。
4.2.3.5 读文件
进程使用read系统调用完成写操作。需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据（如：读入1KB）、指明读入的数据要放在内存中的什么位置。操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
4.2.3.6写文件
进程使用write系统调用完成写操作，需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如：写出1KB）、写回外存的数据放在内存中的什么位置操作系统在处理write系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
4.2.4 文件系统的层次结构
用户接口：文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（Read、Write、Open、Close等系统调用）
文件目录系统：用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等。
存取控制模块：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。
逻辑文件系统与文件信息缓冲区：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址
物理文件系统：这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址
辅助分配模块：负责文件存储空间的管理，即负责分配和回收存储空间
设备管理模块：直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等
4.3 磁盘组织及管理
4.3.1磁盘见计组第七章
4.3.2 磁盘调度算法
寻找时间（寻道时间）TS：在读/写数据前，将磁头移动到指定磁道所花的时间。
启动磁头臂是需要时间的。假设耗时为s；
移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则：
延迟时间TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间
传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则
总的平均存取时间Ta
延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间，但是操作系统的磁盘调度算法会直接影响寻道时间
4.3.2.1 先来先服务算法（FCFS）
根据进程请求访问磁盘的先后顺序进行调度。
优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
4.3.2.2 最短寻找时间优先（SSTF）
SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
优点：性能较好，平均寻道时间短 缺点：可能产生“饥饿”现象
4.3.2.3 扫描算法（SCAN）
SSTF算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
优点：性能较好，平均寻道时间较短，不会产生饥饿现象 缺点：①只有到达最边上的磁道时才能改变磁头移动方向②SCAN算法对于各个位置磁道的响应频率不平均
4.3.2.4 LOOK调度算法
扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫LOOK）
优点：比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
4.3.2.5 循环扫描算法（C-SCAN）
SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
优点：比起SCAN来，对于各个位置磁道的响应频率很平均。 缺点：只有到达最边上的磁道时才能改变磁头移动方向，另外，比起SCAN算法来，平均寻道时间更长。
4.3.2.6 C-LOOK调度算法
C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
优点：比起C-SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
4.3.3 减少延迟时间的方法
磁盘地址结构的设计：
Q：磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）
A：读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间
减少延迟时间的方法：
交替编号：若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
错位命名：让相邻盘面的扇区编号“错位”，与"交替编号"的原理相同。“错位命名法"可降低延迟时间
4.3.4 磁盘管理
4.3.4.1 磁盘初始化
Step 1：进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）
Step 2：将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘）
Step 3：进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表）
4.3.4.2 引导块
计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的
初始化程序可以放在ROM（只读存储器）中。ROM中的数据在出厂时就写入了，并且以后不能再修改。ROM中只存放很小的“自举装入程序”，完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置，开机时计算机先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存，完成初始化。拥有启动分区的磁盘称为启动磁盘或系统磁盘（C:盘）
4.3.4.3 坏块
对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。（在这种方式中，坏块对操作系统不透明）。
对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明
5 输入输出管理
5.1 I/O管理概述
5.1.1 I/O设备
“I/O”就是“输入/输出”（Input/Output）I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。
计算机系统中的I/O设备按使用特性可分为
人机交互类外部设备，如鼠标、键盘，用于人机交互，数据传输速度慢
存储设备，如移动硬盘、光盘等，用于数据存储，数据传输速度快
网络通信设备，如调制解调器等，用于网络通信，数据传输速度介于上述二者之间
按传输速率分类可分为
低速设备，鼠标、键盘等，传输速率为每秒几个到几百字节
中速设备，如激光打印机等，传输速率为每秒数千至上万个字节
高速设备，如磁盘等，传输速率为每秒数千字节至千兆字节的设备
按信息交换的单位分类
块设备：如磁盘等，数据传输的基本单位是“块”，传输速率较高，可寻址，即对它可随机地读/写任一块
字符设备：鼠标、键盘等，数据传输的基本单位是字符。传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式
5.1.2 I/O控制方式
5.1.2.1 程序直接控制方式
完成一次读/写操作的流程（以读操作为例）
CPU向控制器发出读指令。于是设备启动，并且状态寄存器设为1（未就绪）
轮询检查控制器的状态（其实就是在不断地执行程序的循环，若状态位一直是1，说明设备还没准备好要输入的数据，于是CPU会不断地轮询）
输入设备准备好数据后将数据传给控制器，并报告自身状态
控制器将输入的数据放到数据寄存器中，并将状态改为0（已就绪）
CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU的寄存器中，再把CPU寄存器中的内容放入内存
若还要继续读入数据，则CPU继续发出读指令
读操作（数据输入）：I/O设备→CPU→内存 写操作（数据输出）：内存→CPU→I/O设备 每个字的读/写都需要CPU的帮助
优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”） 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低。
5.1.2.2 中断驱动方式
引入中断机制。由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。
①CPU会在每个指令周期的末尾检查中断； ②中断处理过程中需要保存、恢复进程的运行环境， 这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能
读操作（数据输入）：I/O设备→CPU→内存 写操作（数据输出）：内存→CPU→I/O设备
优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。 缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
5.1.2.3 DMA方式
与“中断驱动方式”相比，DMA方式（Direct Memory Access，直接存储器存取。主要用于块设备的I/O控制）有这样几个改进：
数据的传送单位是“块”。不再是一个字、一个字的传送；
数据的流向是从设备直接放入内存，或者从内存直接到设备。
仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。
具体见计组第七章
优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。
5.1.2.4 通道控制方式
通道：一种硬件，可以理解为是“小型CPU”。通道可以识别并执行一系列通道指令
与CPU相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道与CPU共享内存，CPU干预的频率 极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求CPU干预。
缺点：实现复杂，需要专门的通道硬件支持 优点：CPU、通道、I/O设备可并行工作，资源利用率很高。
5.1.3 I/O子系统的层次结构
用户层软件：用户层软件实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作。操作系统向外提供的一系列系统调用，但是由于系统调用的格式严格，使用麻烦，因此在用户层上封装了一系列更方便的库函数接口供用户使用
设备独立性软件：设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。主要实现的功能：①向上层提供统一的调用接口②设备的保护③差错处理④设备的分配与回收⑤数据缓冲区管理⑥建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
操作系统系统可以采用两种方式管理逻辑设备表（LUT）：
第一种方式，整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。 第二种方式，为每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中。
设备驱动程序：主要负责对硬件设备的具体控制，将上层发出的一系列命令（如read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等.不同的I/O设备有不同的硬件特性，具体细节只有设备的厂家才知道。因此厂家需要根据设备的硬件特性设计并提供相应的驱动程序。
中断处理程序:当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。
硬件：执行I/O操作，有机械部件、电子部件组成
直接涉及到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层完成的；没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层完成的）
5.2 I/O核心子系统
5.2.1 I/O调度
II/O调度：用某种算法确定一个好的顺序来处理各个I/O请求。
如：磁盘调度（先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。当多个磁盘I/O请求到来时，用某种调度算法确定满足I/O请求的顺序。同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定I/O调度顺序。
5.2.2 设备保护
操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限（如：只读、读和写等）。在UNIX系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。
5.2.3 假脱机技术（SPOOLing技术）
批处理阶段引入了脱机输入/输出技术（用磁带完成）：引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。
在外围控制机的控制下，慢速输入设备的数据先被输入到更快速的磁带上。之后主机可以从快速的磁带上读入数据，从而缓解了速度矛盾
“假脱机技术”，又称“SPOOLing技术”是用软件的方式模拟脱机技术。SPOOLing系统的组成如下：
要实现SPOOLing技术，必须要有多道程序技术的支持。系统会建立“输入进程”和“输出进程”。
“输入进程”模拟脱机输入时的外围控制机，在输入进程的控制下，“输入缓冲区”用于暂存从输入设备输入的数据，之后再转存到输入井中
“输出进程”模拟脱机输出时的外围控制机，在输出进程的控制下，“输出缓冲区”用于暂存从输出井送来的数据，之后再传送到输出设备上
在磁盘上开辟出两个存储区域——“输入井”和“输出井”
“输入井”模拟脱机输入时的磁带，用于收容I/O设备输入的数据
“输出井”模拟脱机输出时的磁带，用于收容用户进程输出的数据
SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。
独占式设备——只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。 共享设备——允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。
5.2.4 设备的分配与回收
5.2.4.1 设备的固有属性
设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。
独占设备：一个时段只能分配给一个进程（如打印机）
共享设备：可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。
虚拟设备：用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用SPOOLing技术实现的共享打印机）
5.2.4.2 设备分配
从进程运行的安全性上考虑，设备分配有两种方式：
安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。一个时段内每个进程只能使用一个设备
优点：破坏了“请求和保持”条件，不会死锁 缺点：对于一个进程来说，CPU和I/O设备只能串行工作
不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。一个进程可以同时使用多个设备
优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进 缺点：有可能发生死锁（死锁避免、死锁的检测和解除）
设备的分配方式：
静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了“请求和保持”条件，不会发生死锁
动态分配：进程运行过程中动态申请设备资源
5.2.4.3 设备分配管理中的数据结构
设备分配管理中的数据结构有
设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况
控制器控制表（COCT）：每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
通道控制表（CHCT）：每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。
5.2.4.4 设备分配步骤的步骤及改进
设备分配步骤的步骤：
根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）
根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。
根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
缺点：
用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
若换了一个物理设备，则程序无法运行
若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名
根据进程请求的逻辑设备名查找SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）
查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。
根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。
整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统
5.2.5 缓冲区管理
5.2.5.1 缓冲区的概念
缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）
一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区
缓冲区的作用
缓和CPU与I/O设备之间速度不匹配的矛盾
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU与I/O设备之间的并行性
根据系统设置的缓冲区个数，缓冲技术可以分为单缓冲、双缓冲、循环缓冲区
5.2.5.2 单缓冲
假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。
注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
T>C，因此CPU处理完数据后暂时不能将下一块数据传送到工作区，必须等待缓冲区中冲满数据
单缓冲区处理每块数据的用时为
5.2.5.3 双缓冲
假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）
双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空，假设T>C+M，时间为T
假设T<C+M，时间为C+M
采用双缓冲策略，处理一个数据块的平均耗时为
若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。
管道通信中的“管道”其实就是缓冲区。要实现数据的双向传输，必须设置两个管道
5.2.5.4 循环缓冲区
将多个大小相等的缓冲区链接成一个循环队列。
5.2.5.5 缓冲池
缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。
另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：用于收容输入数据的工作缓冲区（hin）、用于提取输入数据的工作缓冲区（sin）、用于收容输出数据的工作缓冲区（hout）、用于提取输出数据的工作缓冲区（sout）
从空缓冲队列中取出一块作为收容输入数据的工作缓冲区（hin）。冲满数据后将缓冲区挂到输入队列队尾