从前慢

操作系统

1.1 操作系统的概念、特征、功能、目标

操作系统（ Operating System，OS）是指控制和管理整个计算机
系统的硬件和软件资源，并合理地组织调度计算机的工作和资源
的分配，以提供给用户和其他软件方便的接口和环境的程序集合。
计算机操作系统是随着计算机研究和应用的发展逐步形成并发展
起来的，它是计算机系统中最基本的系统软件。

1.1.1 操作系统的特征

操作系统的基本特征包括并发、共享、虚拟和异步。

1.1.1.1 并发（ Concurrence）

并发是指两个或多个事件在同一时间间隔内发生。在多道程序环
境下，一段时间内
宏观上有多道程序在同时执行，而在每一时刻，单处理机环境
下实际仅能有一道程序执行，故微观上这些程序还是在分时地
交替执行。操作系统的并发性是通过分时得以实现的。

虽然现在CPU很多都是多核的,但是程序有可能很多,所以并发
还是很重要.

1.1.1.2 共享（ Sharing）

资源共享即共享，是指系统中的资源可供内存中多个并发执行的
进程共同使用。共享可分为
以下两种资源共享方式：
（1）互斥共享方式
系统中的某些资源，如打印机、磁带机，虽然它们可以提供给
多个进程使用，但为使所打印或记录的结果不致造成混淆，应
规定在一段时间内只允许一个进程访问该资源。为此，当进程
A访问某资源时，必须先提出请求，如果此时该资源空闲，系
统便可将之分配给进程A使用，此后若再有其他进程也要访问
该资源时（只要A未用完）则必须等待。仅当进程A访问完并
释放该资源后，才允许另一进程对该资源进行访问。我们把
这种资源共享方式称为互斥式共享，而把在一段时间内只允
许一个进程访问的资源称为临界资源或独占资源。计算机系
统中的大多数物理设备，以及某些软件中所用的栈、变量和
表格，都属于临界资源，它们都要求被互斥地共享
（2）同时共享方式
系统中还有另一类资源，允许在一段时间内由多个进
程“同时”对它们进行访问。这里所谓的“同时”往往是宏观
上的，而在微观上，这些进程可能是交替地对该资源进行
访问，即“分时共享”,典型的可供多个进程“同时”访问的资源
是磁盘设备，一些用重入码编写的文件也可以被“同时”共享，
即若干个用户同时访问该文件.
要注意到，互斥共享，是因为一种资源在一段时间内（哪怕
是一段很小的时间）只能满足一个请求，否则就会出现严重
的问题（如打印机，第一行打印A文档的内容，第二行打印
B文档的内容，你能想象是什么效果吗？）.而同时共享方式
，通常要求，一个请求分几个时间片段间隔地完成的效果，
与连续完成的效果相同

并发和共享是操作系统两个最基本的特征，这两者之间又
是互为存在条件的：①资源共享是以程序的并发为条件的，
若系统不允许程序并发执行，则自然不存在资源共享问题：
②若系统不能对资源共享实施有效的管理，也必将影响到
程序的并发执行，甚至根本无法并发执行

1.1.1.3 虚拟（ Virtual）

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。
物理实体（前者）是实的，即实际存在的；而后者是虚的，
是用户感觉上的事物。用于实现虚拟的技术，称为虚拟技
术。在操作系统中利用了多种虚拟技术，分别用来实现虚
拟处理器、虚拟内存和虚拟外部设备等。
在虚拟处理器技术中，是通过多道程序设计技术，让多道
程序并发执行的方法，来分时使用一个处理器的。此时，
虽然只有一个处理器，但它能同时为多个用户服务，使每
个终端用户都感觉有一个中央处理器（CPU）在专门为它
服务。利用多道程序设计技术，把一个物理上的CPU虚
拟为多个逻辑上的CPU，称为虚拟处理器
类似地，可以通过虚拟存储器技术，将一台机器的物理存
储器变为虚拟存储器，以便从逻辑上来扩充存储器的容量。
当然，这时用户所感觉到的内存容量是虚的。我们把用户
所感觉到的存储器（实际是不存在的）称为虚拟存储器。
还可以通过虚拟设备技术，将一台物理I/O设备虚拟为多
台逻辑上的I/O设备，并允许每个用户占用一台逻辑上的
I/O设备，这样便可以使原来仅允许在一段时间内由一个
用户访问的设备（即临界资源），变为在一段时间内允许
多个用户同时访问的共享设备.因此，操作系统的虚拟技
术可归纳为：时分复用技术，如处理器的分时共享；空分
复用技术，如虚拟存储器.

把CPU抽象成进程，把磁盘抽象成文件，把内存抽象成地址空间

1.1.1.4 异步（(Asynchronism)

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

1.1.2 操作系统的目标和功能

1.1.2.1 操作系统作为计算机系统资源的管理者

（1）处理机管理
在多道程序环境下，处理机的分配和运行都以进程（或线程）
为基本单位，因而对处理机的管理可归结为对进程的管理。
并发时在计算机内同时运行多个进程，所以，进程何时创
建、何时撤销、如何管理、如何避免冲突、合理共享就是进
程管理的最主要的任务。进程管理的主要功能
有：进程控制、进程同步、进程通信、死锁处理、处理机调度等。
（2）存储器管理
存储器管理是为了给多道程序的运行提供良好的环境，方便
用户使用以及提高内存的利用率，主要包括内存分配、地址
映射、内存保护与共享和内存扩充等功能
（3）文件管理
计算机中的信息都是以文件的形式存在的，操作系统中负责文
件管理的部分称为文件系统。
文件管理包括文件存储空间的管理、目录管理及文件读写管
理和保护等。
（4）设备管理
设备管理的主要任务是完成用户的I/O请求，方便用户使用各
种设备，并提高设备的利用率.主要包括缓冲管理、设备分配、
设备处理和虚拟设备等功能。

1.1.2.2 操作系统作为用户与计算机硬件系统之间的接口

操作系统提供的接口主要分为两类
一类是命令接口，用户利用这些操作命令来组织和控制作业
的执行；另一类是程序接口，编程人员可以使用它们来请求操
作系统服务。
（1）命令接口
使用命令接口进行作业控制的主要方式有两种，即联机控
制方式和脱机控制方式。按作业控制方式的不同，可以将命
令接口分为联机命令接口和脱机命令接口
联机命令接口又称交互式命令接口，适用于分时或实时系统
的接口。它由一组键盘操作命令组成。用户通过控制台或终
端输入操作命令，向系统提出各种服务要求。用户每输入
完一条命令，控制权就转入操作系统的命令解释程序，然
后由命令解释程序对输入的命令解释并执行，完成指定的功
能。之后，控制权又转回到控制台或终端，此时用户又可以
输入下一条命令.
脱机命令接口又称批处理命令接口，即适用于批处理系统，
它由一组作业控制命令（或称作业控制语句）组成。脱机用户
不能直接干预作业的运行，应事先用相应的作业控制命令写成
一份作业操作说明书，连同作业一起提交给系统。当系统调
度到该作业时，由系统中的命令解释程序.对作业说明书上的
命令或作业控制语句逐条解释执行，从而间接地控制作业的运行.
联机命令接口可以理解为：“雇主”说一句话，“工人”做一件事，
并做出反馈，这就强调了
交互性。
（2）程序接口
程序接口由一组系统调用命令（简称系统调用，也称广义指令）
组成。用户通过在程序中使用这些系统调用命令来请求操作系
统为其提供服务。用户在程序中可以直接使用这组系统调用
命令向系统提出各种服务要求，如使用各种外部设备，进行
有关磁盘文件的操作，申请分配和回收内存以及其他各种控
制要求

操作系统不允许用户直接操作各种硬件资源，因此用户程序
只能通过系统调用的方式来请求内核为其服务，间接地使用
各种资源
(3)GUI
图形用户界面（GUI）即图形接口，用户通过鼠标和键盘，
在图形界面上单击或使用快捷键就能很方便地使用操作系
统。有些系统提供了上述三种接口，但GUI最终是
通过调用程序接口实现的，严格地说GUI图形接口不属于操
作系统的一部分，但图形接口所调用的系统调用命令，
属于操作系统的一部分.

1.1.2.3 操作系统用做扩充机器

没有任何软件支持的计算机称为裸机，它仅构成计算机系
统的物质基础，而实际呈现在用户面前的计算机系统是
经过若干层软件改造的计算机。裸机在最里层，它的外
面是操作系统，由操作系统提供的资源管理功能和方便
用户的各种服务功能，将裸机改造成功能更强、使用更方
便的机器，通常把覆盖了软件的机器称为扩充机器，又称
之为虚拟机.

单处理机系统中，可并行的是（D）.
I.进程与进程Ⅱ.处理机与设备Ⅲ.处理机与通道Ⅳ.设备与设备
A.I、Ⅱ、Ⅲ
B.I、Ⅱ、Ⅳ
C.I、Ⅲ、Ⅳ
D.Ⅱ、Ⅲ、Ⅳ
在单处理机系统（不包含多核的情况）中，同一时刻只能有
一个进程占用处理机，因此进程之间不能并行执行。通道是
独立于CPU的控制输入输出的设备，两者可以并行，显然，
处理器与设备是可以并行的，难道CPU和显示屏不能并行
工作？设备与设备是可以并行的，难道显示屏与打印机不
能并行工作？

1.2 操作系统的发展与分类

1.2.1 手工操作阶段（此阶段无操作系统）

用户在计算机上算题的所有工作都要人工干预，如程序的装
入、运行、结果的输出等。随着计算机硬件的发展，人机矛
盾（速度和资源利用）越来越大，必须寻求新的解决办法。
手工操作阶段有两个突出的缺点：
1 用户独占全机。不会出现因资源已被其他用户占用而等待的
现象，但资源利用率低。
2 CPU等待手工操作，CPU的利用不充分。唯一的解决办法就
是用高速的机器代替相对较慢的手工操作来对作业进行控制

1.2.2 批处理阶段（操作系统开始出现）

为了解决人机矛盾及CPU和I/O设备之间速度不匹配的矛盾，出
现了批处理系统。它按发
展历程又分为单道批处理系统、多道批处理系统（多道程序设
计技术出现以后）.
1 单道批处理系统
系统对作业的处理是成批进行的，但内存中始终保持一道作业。
该系统是在解决人机矛盾和CPU与I/O设备速率不匹配的矛盾
中形成的。单道批处理系统的主要特征如下
1）自动性。在顺利的情况下，在磁带上的一批作业能自动地逐个依次运行，而无需人工
2）顺序性。磁带上的各道作业是顺序地进入内存，各道作业的完成
顺序与它们进入内存的顺序，在正常情况下应完全相同，亦即先调
入内存的作业先完成
3）单道性。内存中仅有一道程序运行，即监督程序每次从磁带上
只调入一道程序进入内存运行，当该程序完成或发生异常情况时，
才换入其后继程序进入内存运行
此时面临的问题是：每次主机内存中仅存放一道作业，每当它
运行期间（注意这里是“运行时”，并不是“完成后”）发出输入输
出请求后，高速的CPU便处于等待低速的I/O完成状态.为了进一
步提高资源的利用率和系统的吞吐量，引入了多道程序技术.
2 多道批处理系统
多道程序设计技术允许多个程序同时进入内存并运行。即同
时把多个程序放入内存，并允许们交替在CPU中运行，它们
共享系统中的各种硬、软件资源。当一道程序因I/O请求而暂
停运行时，CPU便立即转去运行另一道程序。
多道程序设计的特点有：多道、宏观上并行、微观上串行。
1）多道：计算机内存中同时存放多道相互独立的程序。
2）宏观上并行：同时进入系统的多道程序都处于运行过
程中，即它们先后开始了各自的运行，但都未运行完毕。
3）微观上串行：内存中的多道程序轮流占有CPU，交替
执行
多道程序设计技术的实现需要解决下列问题
1）如何分配处理器
2）多道程序的内存分配问题。
3）I/O设备如何分配。
4）如何组织和存放大量的程序和数据，以便于用户使用和
保证其安全性与一致性。
优点是资源利用率高，多道程序共享计算机资源，从而
使各种资源得到充分利用：系统吞吐量大，CPU和其他
资源保持“忙碌”状态。缺点是用户响应的时间较长。不提
供人机交互能力，用户既不能了解自己程序的运行情况，
也不能控制计算机.

1.2.3 分时操作系统

在操作系统中采用分时技术就形成了分时系统。所谓分时
技术就是把处理器的运行时间分成很短的时间片，按时间
片轮流把处理器分配给各联机作业使用。若某个作业在分
配给它的时间片内不能完成其计算，则该作业暂时停止运
行，把处理器让给其他作业使用，等待下一轮再继续运
行。由于计算机速度很快，作业运行轮转得很快，给每
个用户的感觉好像是自己独占一台计算机.
分时操作系统是多个用户通过终端同时共享一台主机，
这些终端连接在主机上，用户可以同时与主机进行交互
操作而互不干扰。分时系统也是支持多道程序设计的系
统，但它不同于多道批处理系统。多道批处理是实现作
业自动控制而无需人工干预的系统，而分时系统是实现
人机交互的系统，这使得分时系统具有与批处理系统
不同的特征，其主要特征如下：
1）同时性。同时性也称多路性，指允许多个终端用户
同时使用一台计算机，即一台计算机与若干台终端相
连接，终端上的这些用户可以同时或基本同时使用计算机。
2）交互性。用户能够方便地与系统进行人机对话，即用
户通过终端采用人机对话的方式直接控制程序运行，与
同程序进行交互。
3）独立性。系统中多个用户可以彼此独立地进行操作，
互不干扰，单个用户感觉不到别人也在使用这台计算机，
好像只有自己单独使用这台计算机一样
4）及时性。用户请求能在很短时间内获得响应。分时
系统采用时间片轮转方式使一台计算机同时为多个终端
服务，使用户能够对系统的及时响应感到满意
虽然分时操作系统比较好地解决了人机交互问题，但是
在一些应用场合，需要系统能对外部的信息在规定的
时间（比时间片的时间还短）内作出处理（比如飞机
订票系统或导弹制导系统）.因此，实时系统应运而生。

1.2.4 实时操作系统

为了能在某个时间限制内完成某些紧急任务而不
需时间片排队，诞生了实时操作系统。这里的时
间限制可以分为两种情况：如果某个动作必须绝
对地在规定的时刻（或规定的时间范围）发生，
则称为硬实时系统。例如，飞行器的飞行自动控
制系统，这类系统必须提供绝对保证，让某个特
定的动作在规定的时间内完成。如果能够接受偶
尔违反时间规定，并且不会引起任何永久性的损
害，则称为软实时系统，如飞机订票系统、银行
管理系统.在实时操作系统的控制下，计算机系
统接收到外部信号后及时进行处理，并且要在严格
的时限内处理完接收的事件。实时操作系统的主要
特点是及时性和可靠性。

1.2.5 网络操作系统和分布式计算机系统

网络操作系统把计算机网络中的各台计算机有机地结合
起来，提供一种统一、经济而有效的使用各台计算机的
方法，实现各个计算机之间的互相传送数据。网络操作
系统最主要的特点是网络中各种资源的共享以及各台计
算机之间的通信.分布式计算机系统是由多台计算机组成
并满足下列条件的系统：系统中任意两台计算机通过通
信方式交换信息：系统中的每一台计算机都具有同等的
地位，即没有主机也没有从机；每台计算机上的资源
为所有用户共享；系统中的任意若干台计算机都可以构
成一个子系统，并且还能重构；任何工作都可以分布
在几台计算机上，由它们并行工作、协同完成。用于管
理分布式计算机系统的操作系统称为分布式计算机系统
。该系统的主要特点是：分布性和并行性。分布式操作
系统与网络操作系统本质上的不同之处在于分布式操作
系统中，若干台计算机相互协同完成同一任务。

1.2.6 个人计算机操作系统

个人计算机操作系统是目前使用最广泛的操作系统，
广泛应用于文字处理、电子表格、游戏等。常见的有 
Windows、 Linux和 Macintosh等

1.3 操作系统的运行机制跟体系结构

1.3.1 操作系统的运行机制

计算机系统中，通常CPU执行两种不同性质的程序：一种是
操作系统内核程序；另一种是用户自编程序或系统外层的
应用程序。对操作系统而言，这两种程序的作用不同，前
者是后者的管理者，因此“管理程序”要执行一些特权指令，
而“被管理程序”出于安全考虑不能执行这些指令。操作系
统在具体实现上划分了用户态（目态）和核心态（管态），
以严格区分两类程序.操作系统的各项功能分别被设置在不
同的层次上。一些与硬件关联较紧密的模块，诸如时钟管
理、中断处理、设备驱动等处于最底层。其次是运行频率
较高的程序，诸如进程管理、存储器管理和设备管理等。
这两部分内容构成了操作系统的内核。这部分内容的指
令操作工作在核心态。
内核是计算机上配置的底层软件，是计算机功能的延伸。
不同系统对内核的定义稍有区别。大多数操作系统内核
包括四个方面的内容
1 时钟管理
在计算机的各种部件中，时钟是最关键的设备。时钟的第
一功能是计时，操作系统需要通过时钟管理，向用户提
供标准的系统时间。另外，通过时钟中断的管理，可以
实现进程的切换。诸如，在分时操作系统中，采用时间片
轮转调度的实现；在实时系统中，按截止时间控制运行
的实现；在批处理系统中，通过时钟管理来衡量一个作
业的运行程度等。因此，系统管理的方方面无不依赖于时钟。
2 中断机制
引入中断技术的初衷是提高多道程序运行环境中CPU的利
用率，而且主要是针对外部设备的。例如，键盘或鼠标信息
的输入、进程的管理和调度、系统功能的调用、设备驱动、
文件访问等，无不依赖于中断机制。可以说，现代操作系
统是靠中断驱动的软件。
中断机制中，只有一小部分功能属于内核，负责保护和恢复
中断现场的信息，转移控制权到相关的处理程序。这样可以
减少中断的处理时间，提高系统的并行处理能力

3 原语
按层次结构设计的操作系统，底层必然是一些可被调用的公用
小程序，它们各自完成一个规定的操作。其特点是：
1）它们处于操作系统的最底层，是最接近硬件的部分。
2）这些程序的运行具有原子性—其操作只能一气呵成（这主
要是从系统的安全性和便于管理考虑的）
3）这些程序的运行时间都较短，而且调用频繁。
通常把具有这些特点的程序称为原语（ Atomic Operation）.
定义原语的直接方法是关闭中断，让它的所有动作不可分割
地进行完，再打开中断。
系统中的设备驱动、CPU切换、进程通信等功能中的部分
操作都可以定义为原语，使它们成为内核的组成部分

4 系统控制的数据结构及处理
系统来登记状态信息的数据结构很多，比如作业控制块、进程控制
块（PCB）、设备控制块、各类链表、消息队列、缓冲区、空
闲区登记表、内存分配表等。为了实现有效的管理，系统需
要一些基本的操作，常见的操作有以下三种
1）进程管理：进程状态管理、进程调度和分派、创建
与撤销进程控制块等
2）存储器管理：存储器的空间分配和回收、内存信息保
护程序、代码对换程序等

5 系统控制的数据结构及处理
系统中用来登记状态信息的数据结构很多，比如
作业控制块、进程控制块（PCB）、设备控制块、
各类链表、消息队列、缓冲区、空闲区登记表、内存
分配表等。为了实现有效的管理，系统需要一些基
本的操作，常见的操作有以下三种
1）进程管理：进程状态管理、进程调度和分派、
创建与撤销进程控制块等
2）存储器管理：存储器的空间分配和回收、内存
信息保护程序、代码对换程序等
3）设备管理：缓冲区管理、设备分配和回收等
从上述内容可以了解，核心态指令实际上包括系统调
用类指令和一些针对时钟、中断和原语的操作指令

1.3.2 中断和异常

中断（ Interruption），也称外中断，指来自CPU执行指
令以外的事件的发生，如设备发出的I/O结束中断，表示
设备输入输出处理已经完成，希望处理机能够向设备发下
一个输入输出请求,同时让完成输入输出后的程序继续运
行。时钟中断，表示一个固定的时间片已到，让处理机
处理计时、启动定时运行的任务等。这一类中断通常是
与当前程序运行无关的事件，即它们与当前处理机运行的程序无关

异常（ Exception），也称内中断、例外或陷入（Trap），
指源自CPU执行指令内部的事件，如程序的非法操作码、
地址越界、算术溢出、虚存系统的缺页以及专门的陷入指
令等引起的事件。对异常的处理一般要依赖于当前程序
的运行现场，而且异常不能被屏蔽，一但出现应立即处理。

1.3.3 系统调用

所谓系统调用就是用户在程序中调用操作系统提供的一些子
功能，系统调用可以被看做特殊的公共子程序。系统中的各种
共享资源都由操作系统统一掌管，因此在用户程序中，凡
是与资源有关的操作（如存储分配、进行I/O传输以及管理
文件等），都必须通过系统调用方式向操作系统提出服务
请求，并由操作系统代为完成。通常，一个操作系统提供
的系统调用命令有几十乃至上百条之多,这些系统调用按功
能大致可分为如下几类

设备管理。完成设备的请求或释放，以及设备启动等功能
文件管理。完成文件的读、写、创建及删除等功能
进程控制。完成进程的创建、撤销、阻塞及唤醒等功能
进程通信。完成进程之间的消息传递或信号传递等功能
内存管理。完成内存的分配、回收以及获取作业占用内
存区大小及始址等功能。显然，系统调用运行在系统的
核心态。通过系统调用的
方式来使用系统功能，可以保证系统的稳定性和安全性，
防止用户随意更改或访问系统的数据或命令。系统调用
命令是由操作系统提供的一个或多个子程序模块实现的。
下面列举一些由用户态转向核心态的例子：

1.3.4 操作系统的体系结构

2.1 进程与线程

2.1.1 进程的概念和特征

1 进程的概念
进程（ Process）以便更好地描述和控制程序的并发执行，实
现操作系统的并发性和共享性（最基本的两个特性）
为了使参与并发执行的程序（含数据）能独立地运行，必须
为之配置一个专门的数据结构，
称为进程控制块（ Process Control Block，PCB）.系统利用PCB
来描述进程的基本情况和运行状
态，进而控制和管理进程。相应地，由程序段、相关数据段和
PCB三部分构成了进程映像（进程
实体）.所谓创建进程，实质上是创建进程映像中的PCB：而撤
销进程，实质上是撤销进程的PCB
值得注意的是，进程映像是静态的，进程则是动态的。

从不同的角度，进程可以有不同的定义，比较典型的定义有：
1）进程是程序的一次执行过程
2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
3）进程是具有独立功能的程序在一个数据集合上运行的过程，
它是系统进行资源分配和调
度的一个独立单位。
在引入进程实体的概念后，我们可以把传统操作系统中的进程
定义为：“进程是进程实体的
运行过程，是系统进行资源分配和调度的一个独立单位
这里的系统资源，指的是处理机、存储器和其他设备服务
于某进程的“时间”，比如，把处理机资源理解为处理机的
时间片才是准确的。因为进程是这些资源分配和调度的独
立单位，即“时间片”分配的独立单位，这就决定了，进程
一定是一个动态的、过程性的概念。

2 进程的特征
进程是由多程序的并发执行而引出的，它和程序是两个截然不同
的概念。进程的基本特征是
对比单个程序的顺序执行提出的，也是对进程管理提出的基本要求
1）动态性：进程是程序的一次执行，它有着创建、活动、暂停、
终止等过程，具有一定的
生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征
2）并发性：指多个进程实体，同存于内存中，能在一段时间
内同时运行，并发性是进程的
重要特征，同时也是操作系统的重要特征。引入进程的目的就是
为了使程序能与其他进程的程序并发执行，以提高资源利用率
3）独立性：指进程实体是一个能独立运行、独立获得资源和独立
接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立
的单位参与运行。
4）异步性：由于进程的相互制约，使进程具有执行的间断性，即
进程按各自独立的、不可
预知的速度向前推进。异步性会导致执行结果的不可再现性，为
此，在操作系统中必须配置相应的进程同步机制
5）结构性：每个进程都配置一个PCB对其进行描述。从结构上
看，进程实体是由程序段
数据段和进程控制段三部分组成的

2.1.2 进程的状态与转换

通常进程有以下五种状态，前三种是进程的基本状态
1）运行状态：进程正在处理机上运行。在单处理机环境下，
每一时刻最多只有一个进程处
于运行状态。
2）就绪状态：进程已处于准备运行的状态，即进程获得了除
处理机之外的一切所需资源,
一旦得到处理机即可运行
3）阻塞状态，又称等待状态：进程正在等待某一事件而暂
停运行，如等待某资源为可用（不包括处理机）或等待输入
输出完成。即使处理机空闲，该进程也不能运行。
4）创建状态：进程正在被创建，尚未转到就绪状态。创建进
程通常需要多个步骤：首先申请一个空白的PCB，并向PCB
中填写一些控制和管理进程的信息；然后由系统为该进程分配
运行时所必需的资源：最后把该进程转入到就绪状态
5）结束状态：进程正从系统中消失，这可能是进程正常结
束或其他原因中断退出运行。当进程需要结束运行时，系统
首先必须置该进程为结束状态，然后再进一步处理资源释放
和回收等工作注意区别就绪状态和等待状态：就绪状态是指
进程仅缺少处理机，只要获得处理机资源就立即执行；而等
待状态是指进程需要其他资源（除了处理机）或等待某一事
件。之所以把处理机和其他资源划分开，是因为在分时系
统的时间片轮转机制中，每个进程分到的时间片是若干毫秒。
也就是说，进程得到处理机的时间很短且非常频繁，进程
在运行过程中实际上是频繁地转换到就绪状态的：而其他
资源（如外设）的使用和分配或者某一事件的发生（如I/O操
作的完成）对应的时间相对来说很长，进程转换到等待
状态的次数也相对较少。这样来看，就绪状态和等待状态
是进程生命周期中两个完全不同的状态，很显然需要加以区分。

就绪状态→运行状态：处于就绪状态的进程被调度后，获得处
理机资源（分派处理机时间片）于是进程由就绪状态转换为运行状态
运行状态→就绪状态：处于运行状态的进程在时间片用完后，不
得不让出处理机，从而进程由运行状态转换为就绪状态。此外，
在可剥夺的操作系统中，当有更高优先级的进程就绪时，调
度程度将正执行的进程转换为就绪状态，让更高优先级的进程执行。
运行状态→阻塞状态：当进程请求某一资源（如外设）的使用和
分配或等待某一事件的发生（如IO操作的完成）时，它就从运行
状态转换为阻塞状态。进程以系统调用的形式请求操作系统
提供服务，这是一种特殊的、由运行用户态程序调用操作系统
内核过程的形式阻塞状态→就绪状态：当进程等待的事件到来时，
如I/O操作结束或中断结束时，中断处理
程序必须把相应进程的状态由阻塞状态转换为就绪状态
需要注意的是，一个进程从运行状态变成阻塞状态是一个主
动的行为，而从阻塞状态变到就就绪状态是一个被动的
行为，需要其他相关进程的协助

2.1.3 进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它
具有创建新进程、撤销已有
进程、实现进程状态转换等功能。在操作系统中，一般把进程
控制用的程序段称为原语，原语的
特点是执行期间不允许中断，它是一个不可分割的基本单位。
1 进程的创建
允许一个进程创建另一个进程。此时创建者称为父进程，被创
建的进程称为子进程。子进程
可以继承父进程所拥有的资源。当子进程被撤销时，应将其从
父进程那里获得的资源归还给父进
程。此外，在撤销父进程时，也必须同时撤销其所有的子进程
在操作系统中，终端用户登录系统、作业调度、系统提供服务、
用户程序的应用请求等都会
引起进程的创建。操作系统创建一个新进程的过程如下（创建原语）：
1）为新进程分配一个唯一的进程标识号，并申请一个空白的PCB
（PCB是有限的）.若PCB
申请失败则创建失败。
2）为进程分配资源，为新进程的程序和数据，以及用户栈分配必
要的内存空间（在PCB中
体现）.注意：这里如果资源不足（比如内存空间），并不是创建
失败，而是处于“等待状态
或称为“阻塞状态”，等待的是内存这个资源
3）初始化PCB，主要包括初始化标志信息、初始化处理机状态
信息和初始化处理机控制信
息，以及设置进程的优先级等
4）如果进程就绪队列能够接纳新进程，就将新进程插入到就绪
队列，等待被调度运行。
2 进程的终止
引起进程终止的事件主要有：正常结束，表示进程的任务已经
完成和准备退出运行。异常结
束，表示进程在运行时，发生了某种异常事件，使程序无法继
续运行，如存储区越界、保护错、
非法指令、特权指令错、I/O故障等。外界干预是指进程应
外界的请求而终止运行，如操作员或
操作系统干预、父进程请求和父进程终止
操作系统终止进程的过程如下（撤销原语）
1）根据被终止进程的标识符，检索PCB，从中读出该进程的状态
2）若被终止进程处于执行状态，立即终止该进程的执行，将处理
机资源分配给其他进程
3）若该进程还有子进程，则应将其所有子进程终止
4）将该进程所拥有的全部资源，或归还给其父进程或归还
给操作系统。
5）将该PCB从所在队列（链表）中删除

3 进程的阻塞和唤醒
正在执行的进程，由于期待的某些事件未发生，如请求系统
资源失败、等待某种操作的完成
数据尚未到达或无新工作可做等，则由系统自动执行阻塞
原语（ Block），使自己由运行状态变
为阻塞状态。可见，进程的阻塞是进程自身的一种主动行
为，也因此只有处于运行态的进程（获
得CPU），才可能将其转为阻塞状态。阻塞原语的执行过程是
1）找到将要被阻塞进程的标识号对应的PCB.
2）若该进程为运行状态，则保护其现场，将其状态转为阻塞
状态，停止运行。
3）把该PCB插入到相应事件的等待队列中去
当被阻塞进程所期待的事件出现时，如它所启动的IO操作已
完成或其所期待的数据已到达
则由有关进程（比如，提供数据的进程）调用喚醒原语（ Wakeup），
将等待该事件的进程唤醒
唤醒原语的执行过程是
1）在该事件的等待队列中找到相应进程的PCB
2）将其从等待队列中移出，并置其状态为就绪状态
3）把该PCB插入就绪队列中，等待调度程序调度
需要注意的是，Block原语和 Wakeup原语是一对作用刚好
相反的原语，必须成对使用。 Block原语是由被阻塞进程
自我调用实现的，而 Wakeup原语则是由一个与被唤醒进
程相合作或被其他相关的进程调用实现的。


4 进程切换
对于通常的进程，其创建、撤销以及要求由系统设备完成
的IO操作都是利用系统调用而进入内核，再由内核中相应
处理程序予以完成的。进程切换同样是在内核的支持下实
现的，因此可以说，任何进程都是在操作系统内核的支
持下运行的，是与内核紧密相关的进程切换是指处理机
从一个进程的运行转到另一个进程上运行，这个过程中，
进程的运行环境产生了实质性的变化。进程切换的过
程如下
1）保存处理机上下文，包括程序计数器和其他寄存器。
2）更新PCB信息
3）把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4）选择另一个进程执行，并更新其PCB
5）更新内存管理的数据结构
6）恢复处理机上下文
注意，进程切换与处理机模式切换是不同的，模式切换时，
处理机逻辑上可能还在同一进程中运行。如果进程因中断
或异常进入到核心态运行，执行完后又回到用户态刚被中
断的程序运行则操作系统只需恢复进程进入内核时所保
存的CPU现场，无需改变当前进程的环境信息。但若要
切换进程，当前运行进程改变了，则当前进程的环境信息
也需要改变。
注意：“调度”和“切换”的区别，调度是指决定资源分配给哪个
进程的行为，是一种决策行为
切换是指实际分配的行为，是执行行为。一般来说，
先有资源的调度，然后才有进程的切换。

2.1.4 进程的组织

进程是操作系统的资源分配和独立运行的基本单位。它
一般由以下三个部分组成
1 进程控制块
进程创建时，操作系统就新建一个PCB结构，它之
后就常驻内存，任一时刻可以存取，在进程结束
时删除。PCB是进程实体的一部分，是进程存在的
唯一标志。当创建一个进程时，系统为该进程建立一
个PCB：当进程执行时，系统通过其PCB了解进程
的现行状态信息，以便对其进行控制和管理；当进程
结束时，系统收回其PCB，该进程随之消
亡。操作系统通过PCB表来管理和控制进程
PCB主要包括进程描述信息、进程控制和管理信
息、资源分配清单和处理机相关信息等。各部分的主要说明如下：

1）进程描述信息
进程标识符：标志各个进程，每个进程都有一个并且是唯一的标识号。
用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
2）进程控制和管理信息
进程当前状态：描述进程的状态信息，作为处理机分配调度的依据
进程优先级：描述进程抢占处理机的优先级，优先级高的
进程可以优先获得处理机。
3）资源分配清单，用于说明有关内存地址空间或虚拟地址空
间的状况：所打开文件的列表
和所使用的输入输出设备信息。
4）处理机相关信息，主要指处理机中各寄存器值，当进程
被切换时，处理机状态信息都必须保存在相应的PCB中，
以便在该进程重新执行时，能再从断点继续执行
在一个系统中，通常存在着许多进程，有的处于就绪状
态，有的处于阻塞状态，而且阻塞的
原因各不相同。为了方便进程的调度和管理，需要将
各进程的PCB用适当的方法组织起来。目前
常用的组织方式有链接方式和索引方式两种。
链接方式将同一状态的PCB链接成一个队列，不同
状态对应不同的队列，也可以把处于阻塞状态的进程的
PCB，根据其阻塞原因的不同，排成多个阻塞队列。
索引方式是将同一状态的进程组织在一个索引表中，
索引表的表项指向相应的PCB。不同状态对应不同的
索引表，如就绪索引表和阻塞索引表等

2 程序段
程序段就是能被进程调度程序调度到CPU执行的程
序代码段。注意，程序可以被多个进程
共享，就是说多个进程可以运行同一个程序
3 数据段
一个进程的数据段，可以是进程对应的程序加工处理的原始
数据，也可以是程序执行时产生的中间或最终结果

2.1.5 进程的通信

进程通信是指进程之间的信息交换。PV操作是低级通
信方式，高级通信方式是指以较高的效率传输大量数
据的通信方式。高级通信方法主要有以下三个类。

2.1.5.1 共享存储

2.1.5.2 消息传递

2.1.5.3 管道通信

2.1.6 线程概念和多线程模型

2.1.6.1 线程的基本概念

引入进程的目的，是为了更好地使多道程序并发执行，以
提高资源利用率和系统吞吐量，增
加并发程度；而引入线程，则是为了减小程序在并发执行
时所付出的时空开销，提高操作系统的并发性能
线程最直接的理解就是“轻量级进程”，它是一个基本的C
PU执行单元，也是程序执行流的最小单元，由线程ID、
程序计数器、寄存器集合和堆栈组成。线程是进程中
的一个实体，是被系统独立调度和分派的基本单位，线程自
己不拥有系统资源，只拥有一点在运行中必不可少的资源
但它可与同属一个进程的其他线程共享进程所拥有的全
部资源。一个线程可以创建和撤销另一个线程，同一进程
中的多个线程之间可以并发执行。由于线程之间的相互
制约，致使线程在运行中呈现出间断性。线程也有就绪、
阻塞和运行三种基本状态。引入线程后，进程的内涵发生
了改变，进程只作为除CPU以外系统资源的分配单元，线程
则作为处理机的分配单元。由于一个进程内部有多个线程，
如果线程的切换发生在同一个进程内部，则只需要很少
的时空开销

2.1.6.2 线程与进程的比较

1）调度。在传统的操作系统中，拥有资源和独立调度的基本单
位都是进程。在引入线程的操作系统中，线程是独立调度的基本
单位，进程是拥有资源的基本单位。在同一进程中，线程的切
换不会引起进程切换。在不同进程中进行线程切换，如从一个进
程内的线程切换到另一个进程中的线程时，会引起进程切换。
2）拥有资源。不论是传统操作系统还是设有线程的操作系统，
进程都是拥有资源的基本单位，而线程不拥有系统资源（也有
一点必不可少的资源），但线程可以访问其隶属进程的系统
资源。我们要知道，如果线程也是拥有资源的单位，那么，
切换线程也需要较大的时空开销，线程这个概念的提出就没有意义了。
3）并发性。在引入线程的操作系统中，不仅进程之间可以并
发执行，而且多个线程之间也可以并发执行，从而使操作系统
具有更好的并发性，提高了系统的吞吐量。
4）系统开销。由于创建或撤销进程时，系统都要为之
分配或回收资源，如内存空间、IO设备等，因此操作系
统所付出的开销远大于创建或撤销线程时的开销。类似
地，在进行进程切换时，涉及当前执行进程CPU环境的
保存及新调度到进程CPU环境的设置，而线程切换时
只需保存和设置少量寄存器内容，开销很小。此外，
由于同一进程内的多个线程共享进程的地址空间，因
此，这些线程之间的同步与通信非常容易实现，甚
至无需操作系统的干预
5）地址空间和其他资源（如打开的文件）：进程的地
址空间之间互相独立，同一进程的各线程间共享进程的
资源，某进程内的线程对于其他进程不可见
6）通信方面：进程间通信（IPC）需要进程同步和互
斥手段的辅助，以保证数据的一致性而线程间可以直
接读/写进程数据段（如全局变量）来进行通信。

2.1.6.3 线程的属性

在多线程操作系统中，把线程作为独立运行（或调度）
的基本单位，此时的进程，已不再是个基本的可执行实
体。但进程仍具有与执行相关的状态，所谓进程处于“
执行”状态，实际上是指该进程中某线程正在执行。线
程的主要属性如下
1）线程是一个轻型实体，它不拥有系统资源，但每个
线程都应有一个唯一的标识符和一个线程控制块，线
程控制块记录了线程执行的寄存器和栈等现场状态
2）不同的线程可以执行相同的程序，即同一个服
务程序被不同的用户调用时，操作系统为它们创建成
不同的线程
3）同一进程中的各个线程共享该进程所拥有的资源
4）线程是处理机的独立调度单位，多个线程是可以
并发执行的。在单CPU的计算机系统中各线程可交
替地占用CPU；在多CPU的计算机系统中，各线程可
同时占用不同的CPU，若各个CPU同时为一个进程
内的各线程服务则可缩短进程的处理时间。
5）一个线程被创建后便开始了它的生命周期，直
至终止，线程在生命周期内会经历阻塞态
就绪态和运行态等各种状态变化
为什么线程的提出有利于提高系统并发性？可以
这样来理解：由于有了线程，线程切换时
有可能会发生进程切换，也有可能不发生进
程的切换，那么平均下来，每次切换所需要的开销就
小了，因而，就能够让更多的线程参与并发，也不
会影响到响应时间等问题了

2.1.6.4 线程的实现方式

线程的实现可以分为两类：用户级线程（ User-Level Thre
ad，ULT）和内核级线程（ Kernel-Lev Thread，KLT）.内核
级线程又称为内核支持的线程。在用户级线程中，有关线
程管理的所有工作都由应用程序完成，内核意识不到线程
的存在应用程序可以通过使用线程库设计成多线程程序。
通常，应用程序从单线程起始，在该线程中开始运行，在其
运行的任何时刻，可以通过调用线程库中的派生例程创建
一个在相同进程中运行的新线程。图（a）说明了用户级
线程的实现方式在内核级线程中，线程管理的所有工
作由内核完成，应用程序没有进行线程管理的代码，只有
一个到内核级线程的编程接口。内核为进程及其内部的每
个线程维护上下文信息，调度也是在内核基于线程架构的基础
上完成。图（b）说明了内核级线程的实现方式
在一些系统中，使用组合方式的多线程实现。线程创建完
全在用户空间中完成，线程的调度和同步也在应用程序中进
行。一个应用程序中的多个用户级线程被映射到一些（小于
或等于用户级线程的数目）内核级线程上。图（c）说明
了用户级与内核级的组合实现方式

2.1.6.5 多线程模型

有些系统同时支持用户线程和内核线程，由此产生了不同的多线
程模型，即实现用户级线程和内核级线程的连接方式
1）多对一模型。将多个用户级线程映射到一个内核级线程，线
程管理在用户空完成。此模式中，用户级线程对操作系统不可
见（即透明）.
优点：线程管理是在用户空间进行的，因而效率比较高。
缺点：当一个线程在使用内核服务时被阻塞，那么整个进
程都会被阻塞：多个线程不能并行地运行在多处理机上。
2）一对一模型。将每个用户级线程映射到一个内核级线程。
优点：当一个线程被阻塞后，允许另一个线程继续执行，所
以并发能力较强
缺点：每创建一个用户级线程都需要创建一个内核级线
程与其对应，这样创建线程的开销比
较大，会影响到应用程序的性能
3）多对多模型。将n个用户级线程映射到m个内核级线程上，要求m≤n
特点：在多对一模型和一对一模型中取了个折中，克服了
多对一模型的并发度不高的缺点又克服了一对一模型的一个
用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型
和一对一模型各自的优点，可谓集两者之所长

2.1.7 处理机调度的概念、层次

高级调度

中级调度

1 调度的基本概念
在多道程序系统中，进程的数量往往多于处理机的个数，进程争用处理机的情况就在所难免。
处理机调度是对处理机进行分配，就是从就绪队列中，按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行

处理机调度是多道程序操作系统的基础，它是操作系统设计的核心问题

2 调度的层次
作业从提交开始直到完成，往往要经历以下三级调度
1）作业调度。又称高级调度，其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利。简言之，就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次
多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。
2）中级调度。又称内存调度。引入中级调度是为了提高内存利用率和系统吞吐量。为此应使那些暂时不能运行的进程，调至外存等待，把此时的进程状态称为挂起状态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待
3）进程调度。又称为低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次

3 三级调度的联系
作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行状态，把CPU分配给它。
中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒
1）作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
2）作业调度次数少，中级调度次数略多，进程调度频率最高。
3）进程调度是最基本的，不可或缺

低级调度

2.1.8 进程调度的时机、切换与过程、方式

进程调度的时机

进程调度和切换程序是操作系统内核程序。当请求调度的事件发生后，才可能会运行进程调度程序，当调度了新的就绪进程后，才会去进行进程间的切换。理论上这三件事情应该顺序执行，但在实际设计中，在操作系统内核程序运行时，如果某时发生了引起进程调度的因素，并不一定能够马上进行调度与切换。
现代操作系统中，不能进行进程的调度与切换的情况有以下几种情况
1）在处理中断的过程中：中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
2）进程在操作系统内核程序临界区中：进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放。
3）其他需要完全屏蔽中断的原子操作过程中：如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。如果在上述过程中发生了引起调度的条件，并不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。
应该进行进程调度与切换的情况有：
1）当发生引起调度条件，且当前进程无法继续运行下去时，可以马上进行调度与切换。如果操作系统只在这种情况下进行进程调度，就是非剥夺调度
2）当中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。如果操作系统支持这种情况下的运行调度程序，就实现了剥夺方式的调度。
进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入到当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

进程调度方式

所谓进程调度方式是指当某一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。
通常有以下两种进程调度方式
1）非剥夺调度方式，又称非抢占方式。是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重要或紧迫的进程。
在非剥夺调度方式下，一旦把CPU分配给一个进程，那么该进程就会保持CPU直到终止或转换到等待状态。这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。
2）剥夺调度方式，又称抢占方式。是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。
采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。但“剥夺”不是一种任意性行为，必须遵循一定的原则，主要有：优先权、短进程优先和时间片原则等。

进程的切换与过程

2.1.9 调度算法的评价指标

CPU利用率

系统吞吐量

周转时间

等待时间

响应时间

不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法所具有的特性。为了比较处理机调度算法的性能，人们提出很多评价准则，下面介绍主要的几种
1）CPU利用率。CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使CPU保持“忙”状态，使这一资源利用率最高
2）系统吞吐量。表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。而对于短作业，它们所需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。
3）周转时间。是指从作业提交到作业完成所经历的时间，包括作业等待、在就绪队列中排队、在处理机上运行以及进行输入输出操作所花费时间的总和。
4）等待时间。是指进程处于等处理机状态时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
5）响应时间。是指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一

2.1.10 FCFS、SJF、HRRN调度算法

在操作系统中存在多种调度算法，其中有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法。

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

FCFS调度算法是一种最简单的调度算法，该调度算法既可以用于作业调度也可以用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

FCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。FCFS调度算法的特点是算法简单，但效率低：对长作业比较有利，但对短作业不利（相对SJF和高响应比）：有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

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

短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短作业优先（SJF）调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法，则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。

SJF调度算法也存在不容忽视的缺点：
1）该算法对长作业不利，SJF调度算法中长作业的周转时间会增加。更严重的是，如果有一长作业进入系统的后备队列，由于调度程序总是优先调度那些（即使是后进来的）短作业，将导致长作业长期不被调度（“饥饿”现象，注意区分“死锁”.后者是系统环形等待，前者是调度策略问题）.
2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。
3）由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
注意，SJF调度算法的平均等待时间、平均周转时间最少

高响应比优先调度算法HRRN

高响应比优先调度算法主要用于作业调度，该算法是对FCFS调度算法和SJF调度算法的种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行

2.1.11 时间片轮转、优先级、多级反馈队列

时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms.在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。
在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小，那么处理机将在进程间过于频繁切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此时间片的大小应选择适当。时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

优先级调度算法

多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级
调度算法的综合和发展，如图2-5所示。通过动态调整
进程优先级和时间片大小，多级反馈队列调度算法可以
兼顾多方面的系统目标。例如，为提高系统吞吐量和缩
短平均周转时间而照顾短进程；为获得较好的I/O设备利
用率和缩短响应时间而照顾I/O型进程；同时，也不必事
先估计进程的执行时间。

多级反馈队列调度算法的实现思想如下：
1）应设置多个就绪队列，并为各个队列赋予不同的优先
级，第1级队列的优先级最高，第2级队列次之，其余队
列的优先级逐次降低。
2）赋予各个队列中进程执行时间片的大小也各不相同，
在优先级越高的队列中，每个进程的运行时间片就越小。
例如，第2级队列的时间片要比第1级队列的时间片长1
倍…第计+1级队列的时间片要比第i级队列的时间片长1倍。
3）当一个新进程进入内存后，首先将它放入第1级队列
的末尾，按FCFS原则排队等待调度。当轮到该进程执
行时，如它能在该时间片内完成，便可准备撤离系统；
如果它在一个时间片结束时尚未完成，调度程序便将该
进程转入第2级队列的末尾，再同样地按FCFS原则等
待调度执行；如果它在第2级队列中运行一个时间片后
仍未完成，再以同样的方法放入第3级队列
如此下去，当一个长进程从第1级队列依次降到第n级队
列后，在第n级队列中便釆用时间片轮转的方式运行。
4）仅当第1级队列为空时，调度程序才调度第2级队
列中的进程运行；仅当第1~（-1）级队列均为空时，
才会调度第i级队列中的进程运行。如果处理机正在
执行第i级队列中的某进程时又有新进程进入优先级
较高的队列（第1~（-1）中的任何一个队列），则
此时新进程将抢占正在运行进程的处理机，即由调
度程序把正在运行的进程放回到第i级队列的末尾，
把处理机分配给新到的更高优先级的进程
多级反馈队列的优势有以下几点。
1）终端型作业用户：短作业优先。
2）短批处理作业用户：周转时间较短
3）长批处理作业用户：经过前面几个队列
得到部分执行，不会长期得不到处理

2.1.12 进程同步、互斥

1 临界资源
虽然多个进程可以共享系统中的各种资源，但其中许多
资源一次只能为一个进程所使用，我们把一次仅允许一
个进程使用的资源称为临界资源。许多物理设备都属于
临界资源，如打印机等.此外，还有许多变量、数据等都
可以被若干进程共享，也属于临界资源.
对临界资源的访问，必须互斥地进行，在每个进程中，访
问临界资源的那段代码称为临界区。
2 同步
同步亦称直接制约关系，它是指为完成某种任务而建立的
两个或多个进程，这些进程因为需要在某些位置上协调它
们的工作次序而等待、传递信息所产生的制约关系。进
程间的直接制约关系就是源于它们之间的相互合作
例如，输入进程A通过单缓冲向进程B提供数据。当该缓
冲区空时，进程B不能获得所需数据而阻塞，一旦进程A
将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，
进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A
3 互斥
互斥亦称间接制约关系。当一个进程进入临界区使用临界
资源时，另一个进程必须等待，当占用临界资源的进程退
出临界区后，另一进程才允许去访问此临界资源
例如，在仅有一台打印机的系统中，有两个进程A和进
程B，如果进程A需要打印时，系统已将打印机分配给进
程B，则进程A必须阻塞。一旦进程B将打印机释放，系
统便将进程A唤醒，并将其由阻塞状态变为就绪状态。
为禁止两个进程同时进入临界区，同步机制应遵循以下准则：
1）空闲让进。临界区空闲时，可以允许一个请求进入临
界区的进程立即进入临界区
2）忙则等待。当已有进程进入临界区时，其他试图进入临
界区的进程必须等待。
3）有限等待。对请求访问的进程，应保证能在有限时
间内进入临界区
4）让权等待。当进程不能进入临界区时，应立即释放
处理器，防止进程忙等待

2.1.12.1 实现临界区互斥的基本方法

1 软件实现方法
单标志法。
双标志法先检查
双标志法后检查。
Peterson's Algorithm
2 硬件实现方法
1）中断屏蔽方法
当一个进程正在使用处理机执行它的临界区代码时，要
防止其他进程再进入其临界区访问的最简单方法是禁止
一切中断发生，或称之为屏蔽中断、关中断。因为CPU只
在发生中断时引起进程切换，这样屏蔽中断就能保证当前
运行进程将临界区代码顺利地执行完，从而保证了互斥
的正确实现，然后再执行开中断。其典型模式
...
关中断；
临界区；
开中断；
...
这种方法限制了处理机交替执行程序的能力，因此执行的
效率将会明显降低。对内核来说当它执行更新变量或列表
的几条指令期间关中断是很方便的，但将关中断的权力
交给用户则很不明智，若一个进程关中断之后不再开中
断，则系统可能会因此终止。

2）硬件指令方法
TestAndSet指令
Swap指令

2.1.13 信号量

信号量机构是一种功能较强的机制，可用来解决互斥与同步的
问题，它只能被两个标准的原语wait(S)和 signal(S)来访问，
也可以记为“P操作”和“V操作”.
原语是指完成某种功能且不被分割不被中断执行的操作序列，
通常可由硬件来实现完成不被分割执行特性的功能。如前述
的“ Test-and-Set”和“Swap”指令，就是由硬件实现的原子操
作。原语功能的不被中断执行特性在单处理机时可由软件
通过屏蔽中断方法实现。原语之所以不能被中断执行，是
因为原语对变量的操作过程如果被打断，可能会去运行另
个对同一变量的操作过程，从而出现临界段问题。如果能
够找到一种解决临界段问题的元方法，就可以实现对共享
变量操作的原子性。

1 整型信号量
2 记录型信号量
3 利用信号量实现同步
4 利用信号量实现进程互斥
5 利用信号量实现前驱关系

2.1.14 经典同步问题

1 生产者-消费者问题
问题描述：一组生产者进程和一组消费者进程共享一个初始
为空、大小为n的缓冲区，只有
缓冲区没满时，生产者才能把消息放入到缓冲区，否则
必须等待：只有缓冲区不空时，消费者才能从中取出
消息，否则必须等待。由于缓冲区是临界资源，它只允
许一个生产者放入消息，或者个消费者从中取出消息。
2 读者-写者问题
问题描述：有读者和写者两组并发进程，共享一个文
件，当两个或以上的读进程同时访问共享数据时不会
产生副作用，但若某个写进程和其他进程（读进程或写
进程）同时访问共享数据时则可能导致数据不一致
的错误。因此要求：
1 允许多个读者可以同时对文件执行读操作：
2 只允许一个写者往文件中写信息：
3 任一写者在完成写操作之前不允许其他读者或写者工作；
4 写者行写操作前，应让已有的读者和写者全部退出

3 哲学家进餐问题
问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌
上摆一根筷子，桌子的中间是一碗米饭.哲学家们倾注毕生精力
用于思考和进餐，哲学家在思考时，并不影响他人。只有当晢
学家饥饿的时候，才试图拿起左、右两根筷子（一根一根地拿起）
.如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到
了两根筷子才可以开始进餐，当进餐完毕筷子继续思考
4 吸烟者问题
问题描述：假设一个系统有三个抽烟者进程和一个供应者
进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽
掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三
个抽烟者中，第一个拥有烟草、第二个拥有纸，第三个
拥有胶水。供应者进程无限地提供三种材料，供应者每
次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷
一根烟并抽掉它，并给供应者一个信号告诉完成了，供应
者就会放另外两种材料在桌上，这种过程一直重复（让三
个抽烟者轮流地抽烟）

2.1.15 管程

1 管程的定义
系统中的各种硬件资源和软件资源，均可用数据结构抽象地
描述其资源特性，即用少量信息和对资源所执行的操作来表
征该资源，而忽略了它们的内部结构和实现细节。管程是由
一组数据以及定义在这组数据之上的对这组数据的操作组
成的软件模块，这组操作能初始化并改变管程中的数据和同步进程.

2 管程的纽成
1）局部于管程的共享结构数据说明
2）对该数据结构进行操作的一组过程。
3）对局部于管程的共享数据设置初始值的语句

3 管程的基本特性
1）局部于管程的数据只能被局部于管程内的过程所访问
2）一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3）每次仅允许一个进程在管程内执行某个内部过程。
由于管程是一个语言成分，所以管程的互斥访问完全由编译程
序在编译时自动添加，无需程序员关注，而且保证正确.

这里，我们再用生活化的语言介绍什么是管程。
管程实质上是一个抽象类，这个抽象类有好几个成员变量，
系统中任何设备都可以通过这几成员变量进行区分和
描述：管程中还有对这些成员变量进行操作的一组成员
函数，例如，对外设的操作中，会有read，write这一类
函数。假如，进程P0要使用一台打印机，于是管程这个
抽象类就会利用初始值语句对自身的几个成员变量赋初
值（这个行为不需要程序员关注），特定的几个初值可
以让管程表示成一台打印机，进程P0进入管程后，通过
调用管程中的成员函数（即上面所说的过程）对这台打
印机进行操作。每次进入这个管程的，只能是一个进程

2.1.16 死锁

1 死锁的定义
在多道程序系统中，由于多个进程的并发执行，改善了系统资
源的利用率并提高了系统的处理能力。然而，多个进程的并发
执行也带来了新的问题—死锁。所谓死锁是指多个进程因竞
争资源而造成的一种僵局（互相等待），若无外力作用，这
些进程都将无法向前推进.在计算机系统中也存在类似的情
况。例如，某计算机系统中只有一台打印机和一台输入设备
进程P1正占用输入设备，同时又提出使用打印机的请求，
但此时打印机正被进程P2所占用，而P2在未释放打印机
之前，又提出请求使用正被P1占用着的输入设备。这样两
个进程相互无休止地等待下去，均无法继续执行，此时两
个进程陷入死锁状态。

2 死锁产生的原因
（1）系统资源的竞争
通常系统中拥有的不可剥夺资源，其数量不足以满足
多个进程运行的需要，使得进程在运行过程中，会因
争夺资源而陷入僵局，如磁带机、打印机等。只有对
不可剥夺资源的竞争才可能产生死锁，对可剥夺资源
的竞争是不会引起死锁的。
（2）进程推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，也同
样会导致死锁。例如，并发进程P1、P2分别保持了资
源R1、R2，而进程Pl申请资源R2，进程P2申请资源R1
时，两者都会因为所需资源被占用而阻塞。
信号量使用不当也会造成死锁。进程间彼此相互等待
对方发来的消息，结果也会使得这些进程间无法继续向
前推进。例如，进程A等待进程B发的消息，进程B又在
等待进程A发的消息可以看出进程A和B不是因为竞争同
一资源，而是在等待对方的资源导致死锁.
（3）死锁产生的必要条件
产生死锁必须同时满足以下四个条件，只要其中任一条件
不成立，死锁就不会发生互斥条件：进程要求对所分配
的资源（如打印机）进行排他性控制，即在一段时间内
某资源仅为一个进程所占有。此时若有其他进程请求
该资源，则请求进程只能等待。
不剥夺条件：进程所获得的资源在未使用完毕之前，
不能被其他进程强行夺走，即只能由获得该资源的进
程自己来释放（只能是主动释放）.请求和保持条
件：进程已经保持了至少一个资源，但又提出了新的资
源请求，而该资源已被其他进程占有，此时请求进程被
阻塞，但对自己已获得的资源保持不放

资源分配图含圈而系统又不一定有死锁的原因是同类资
源数大于1.但若系统中每类资源都只有一个资源，则资
源分配图含圈就变成了系统出现死锁的充分必要条件。
要注意区分不可剥夺条件与请求和保持条件，用一个简
单的例子来说明：如果你手上拿个苹果（即便你不打
算吃），别人不能把你手上的苹果拿走，那就是不可剥夺
条件；如果你左手拿着一个苹果，允许你右手再去拿一个
苹果，那就是请求和保持条件。

2.1.17 死锁的处理策略

为使系统不发生死锁，必须设法破坏产生死锁的四个必要条
件之一，或者允许死锁产生，但当死锁发生时能检测出
死锁，并有能力实现恢复
1 预防死锁
设置某些限制条件，破坏产生死锁的四个必要条件中的一
个或几个，以防止发生死锁
2 避免死锁
在资源的动态分配过程中，用某种方法防止系统进入不
安全状态，从而避免死锁
3 死锁的检测及解除
无需采取任何限制性措施，允许进程在运行过程中发
生死锁。通过系统的检测机构及时地检
测出死锁的发生，然后采取某种措施解除死锁。
预防死锁和避免死锁都属于事先预防策略，但预防死
锁的限制条件比较严格，实现起来较为简单，但往往
导致系统的效率低，资源利用率低：避免死锁的限制条
件相对宽松，资源分配后需
要通过算法来判断是否进入不安全状态，实现起来较为复杂。

2.1.17.1 死锁预防

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可
1 破坏互斥条件
如果允许系统资源都能共享使用，则系统不会进入死锁
状态。但有些资源根本不能同时访问，如打印机等临界
资源只能互斥使用。所以，破坏互斥条件而预防死锁的方
法不太可行，而且在有的场合应该保护这种互斥性
2 破坏不剥夺条件
当一个已保持了某些不可剥夺资源的进程，请求新的资
源而得不到满足时，它必须释放已经保持的所有资源，
待以后需要时再重新申请。这意味着，一个进程已占有
的资源会被暂时释放或者说是被剥夺了，或从而破坏
了不可剥夺条件该策略实现起来比较复杂，释放已获得
的资源可能造成前一阶段工作的失效，反复地申请和释
放资源会增加系统开销，降低系统吞吐量.这种方法常
用于状态易于保存和恢复的资源，如CPU的寄存器及内
存资源，一般不能用于打印机之类的资源

3 破坏请求和保持条件
采用预先静态分配方法，即进程在运行前一次申请完它所
需要的全部资源，在它的资源未满足前，不把它投入运
行。一旦投入运行后，这些资源就一直归它所有，也不
再提出其他资源请求这样就可以保证系统不会发生死锁
这种方式实现简单，但缺点也显而易见，系统资源被
严重浪费，其中有些资源可能仅在运行初期或运行快结
束时才使用，甚至根本不使用。而且还会导致“饥饿”现
象，当由于个别资源长期被其他进程占用时，将致使等
待该资源的进程迟迟不能开始运行。

4 破坏循环等待条件
为了破坏循环等待条件，可采用顺序资源分配法。首先
给系统中的资源编号，规定每个进程必须按编号递增的
顺序请求资源，同类资源一次申请完。也就是说，只要
进程提出申请分配资源Ri，则该进程在以后的资源申请
中，只能申请编号大于Ri的资源.这种方法存在的问题
是，编号必须相对稳定，这就限制了新类型设备的增
加：尽管在为资源编号时已考虑到大多数作业实际使
用这些资源的顺序，但也经常会发生作业使用资源的
顺序与系统规定顺序不同的情况，造成资源的浪费：
此外，这种按规定次序申请资源的方法，也必然会给
用户的编程带来麻烦.

2.1.17.2 死锁避免

并非所有的不安全状态都是死锁状态，但当系统进入不安
全状态后，便可能进入死锁状态。反之，只要系统处于安
全状态，系统便可以避免进入死锁状态

2.1.17.3 死锁检测和解除

前面介绍的死锁预防和避免算法，都是在为进程分配资源
时施加限制条件或进行检测，若系统为进程分配资源时
不采取任何措施，则应该提供死锁检测和解除的手段。

3.1 内存管理

3.1.1 内存管理的概念

内存管理（ Memory Management）是操作系统设计中最重要和
最复杂的内容之一。操作系统对内存的划分和动态分配，就是内
存管理的概念

内存管理的功能有：
内存空间的分配与回收：由操作系统完成主存储器空
间的分配和管理，使程序员摆脱存储分配的麻烦，提高
编程效率。

地址转换：在多道程序环境下，程序中的逻辑地址与内
存中的物理地址不可能一致，因此存储管理必须提供地
址变换功能，把逻辑地址转换成相应的物理地址。

内存空间的扩充：利用虚拟存储技术或自动覆盖技术，
从逻辑上扩充内存

存储保护：保证各道作业在各自的存储空间内运行，
互不干扰。
在进行具体的内存管理之前，需要了解进程运行的
基本原理和要求。

程序装入和链接
创建进程首先要将程序和数据装入内存。将用户源程
序变为可在内存中执行的程序，通常需要以下几个步骤
编译：由编译程序将用户源代码编译成若干个目标模块
链接：由链接程序将编译后形成的一组目标模块，以及
所需库函数链接在一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存运行。
这三步过程如图所示。
程序的链接有以下三种方式
静态链接：在程序运行之前，先将各目标模块及它们所需
的库函数链接成一个完整的可执行程序，以后不再拆开。

装入时动态链接：将用户源程序编译后所得到的一组目
标模块，在装入内存时，采用边装入边链接的链接方式

运行时动态链接：对某些目标模块的链接，是在程序执
行中需要该目标模块时，才对它进行的链接。其优点是
便于修改和更新，便于实现对目标模块的共享

内存的装入模块在装入内存时，同样有以下三种方式：
1）绝对装入。在编译时，如果知道程序将驻留在内存的
某个位置，编译程序将产生绝对地址的目标代码。绝对
装入程序按照装入模块中的地址，将程序和数据装入内
存。由于程序中的逻辑地址与实际内存地址完全相同，
故不需对程序和数据的地址进行修改。绝对装入方式
只适用于单道程序环境。另外，程序中所使用的绝对
地址，可在编译或汇编时给出，也可由程序员直接赋
予。而通常情况下在程序中采用的是符号地址，编译
或汇编时再转换为绝对地址。
2）可重定位装入。在多道程序环境下，多个目标模块
的起始地址通常都是从0开始，程序中的其他地址都是
相对于起始地址的，此时应采用可重定位装入方式。
根据内存的当前情况，将装入模块装入到内存的适当
位置。装入时对目标程序中指令和数据的修改过程称为
重定位，地址变换通常是在装入时一次完成的，所以
又称为静态重定位，如图（a）所示。

静态重定位的特点是在一个作业装入内存时，必须分
配其要求的全部内存空间，如果没有足够的内存，就
不能装入该作业。此外，作业一旦进入内存后，在整
个运行期间不能在内存中移动，也不能再申请内存空间

动态运行时装入，也称为动态重定位，程序在内存中
如果发生移动，就需要采用动态的装入方式。装入程
序在把装入模块装入内存后，并不立即把装入模块中
的相对地址转换为绝对地址，而是把这种地址转换推
迟到程序真正要执行时才进行。因此，装入内存后
的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持，如图（b）所示
动态重定位的特点是可以将程序分配到不连续的存储
区中：在程序运行之前可以只装入它的部分代码即可
投入运行，然后在程序运行期间，根据需要动态申请
分配内存：便于程序段的共享,可以向用户提供一个
比存储空间大得多的地址空间

逻辑地扯空间与物理地址空间

编译后，每个目标模块都是从0号单元开始编址，称为该
目标模块的相对地址（或逻辑地址）.
链接程序将各个模块链接成一个完整的可执行目标程序
时，链接程序顺序依次按各个模块的相对地址构成统一
的从0号单元开始编址的逻辑地址空间。用户程序和程
序员只需知道逻辑地址而内存管理的具体机制则是完
全透明的，它们只有系统编程人员才会涉及。不同进
程可以有相同的逻辑地址，因为这些相同的逻辑地
址可以映射到主存的不同位置.物理地址空间是指内
存中物理单元的集合，它是地址转换的最终地址，
进程在运行时执行指令和访问数据最后都要通过物
理地址从主存中存取。当装入程序将可执行代码装入
内存时，必须通过地址转换将逻辑地址转换成物理地
址，这个过程称为地址重定位

内存保护

内存分配前，需要保护操作系统不受用户进程的影响，
同时保护用户进程不受其他用户进程的影响。内存保护
可采取两种方法
（1）在CPU中设置一对上、下限寄存器，存放用户
作业在主存中的下限和上限地址，每当CPU要访问一
个地址时，分别和两个寄存器的值相比，判断有无越界
（2）通过采用重定位寄存器（或基址寄存器）和界地
址寄存器（又称限长寄存器）来实现这种保护。重定
位寄存器含最小的物理地址值，界地址寄存器含逻辑
地址的最大值。每个逻辑地址值必须小于界地址寄存
器；内存管理机构动态地将逻辑地址与界地址寄存
器进行比较，如果未发生地址越界，则加上重定位
寄存器的值后映射成物理地址，再送交内存单元，
如图3-3所示

当CPU调度程序选择进程执行时，派遣程序会初始化重
定位寄存器和界地址寄存器。每个逻辑地址都需要与这
两个寄存器进行核对，以保证操作系统和其他用户程序
及数据不被该进程的运行所影响.实现内存保护需要重
定位寄存器和界地址寄存器，注意两者的区别。重定
位寄存器是用来“加”的，逻辑地址加上重定位寄存器中
的值就能得到物理地址;界地址寄存器是用来“比”的
通过比较界地址寄存器中的值与重定位寄存器加上逻
辑地址的值来判断是否越界

3.1.2 覆盖与交换

覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法
1 覆盖
早期的计算机系统中，主存容量很小，虽然主存中仅存放
一道用户程序，但是存储空间放不下用户进程的现象也经
常发生，这一矛盾可以用覆盖技术来解决。
覆盖的基本思想是：由于程序运行时并非任何时候都要访
问程序及数据的各个部分（尤其是大程序），因此可以把
用户空间分成一个固定区和若干个覆盖区。将经常活跃的
部分放在固定区.其余部分按调用关系分段。首先将那些
即将要访问的段放入覆盖区，其他段放在外存中，在需
要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段.
覆盖技术的特点是打破了必须将一个进程的全部信息装
入主存后才能运行的限制，但当同时运行程序的代码量
大于主存时仍不能运行，再而，大家要注意到，内存中
能够更新的地方只有覆准区的段，不在覆盖区中的段
会常驻内存

2 交换
交换（对换）的基本思想是，把处于等待状态（或在
CPU调度原则下被剥夺运行权利）的程序从内存移到
辅存，把内存空间腾出来，这一过程又叫换出：把准
备好竞争CPU运行的程序从辅存移到内存，这一过程
又称为换入。
例如，有一个CPU采用时间片轮转调度算法的多道程
序环境。时间片到，内存管理器将刚刚执行过的进程
换出，将另一进程换入到刚刚释放的内存空间中。同
时，CPU调度器可以将时间片分配给其他已在内存
中的进程。每个进程用完时间片都与另一进程交换。
理想情况下，内存管理器的交换过程速度足够快，总
有进程在内存中可以执行.

有关交换需要注意以下几个问题
交换需要备份存储，通常是快速磁盘。它必须足够
大，并且提供对这些内存映像的直接访问。
为了有效使用CPU，需要每个进程的执行时间比交换
时间长，而影响交换时间的主要是转移时间。转移时
间与所交换的内存空间成正比.
如果换出进程，必须确保该进程是完全处于空闲状态.
交换空间通常作为磁盘的一整块，且独立于文件系统，
因此使用就可能很快交换通常在有许多进程运行且
内存空间吃紧时开始启动，而系统负荷降低就暂停。

普通的交换使用不多，但交换策略的某些变种在许多
系统中（如UNⅨ系统）仍发挥作用

交换技术主要是在不同进程（或作业）之间进行，而覆盖
则用于同一个程序或进程中。由于覆盖技术要求给出程序
段之间的覆盖结构，使得其对用户和程序员不透明，所
以对于主存无法存放用户程序的矛盾，现代操作系统是
通过虚拟内存技术来解决的，覆盖技术则已成为历史：而
交换技术在现代操作系统中仍具有较强的生命力

3.1.3 连续分配管理方式

连续分配方式，是指为一个用户程序分配一个连续的内
存空间，比如说某用户需要1GB的内存空间，它就在内
存空间中分配一块连续的1GB的空间给用户。它主要包
括单一连续分配/固定分区分配和动态分区分

1 单一连续分配
内存在此方式下分为系统区和用户区，系统区仅提供
给操作系统使用，通常在低地址部分.用户区是为用
户提供的、除系统区之外的内存空间。这种方式无
需进行内存保护。因为内存中永远只有一道程序，肯
定不会因为访问越界而干扰其他程序。这种方式的优
点是简单、无外部碎片，可以采用覆盖技术，不需要
额外的技术支持。缺点是只能用于单用户、单任务的
操作系统中，有内部碎片，存储器的利用率极低
2 固定分区分配
固定分区分配是最简单的一种多道程序存储管理方
式，它将用户内存空间划分为若干个固定大小的区
域，每个分区只装入一道作业。当有空闲分区时，
便可以再从外存的后备作业队列中，选择适当大小的
作业装入该分区，如此循环，固定分区分配在划分分区
时，有两种不同的方法，如图3-4所示

分区大小相等：用于利用一台计算机去控制多个相同对象的场合，
缺乏灵活性

分区大小不等：划分为含有多个较小的分区、适量的中等分区及
少量的大分区。为便于内存分配，通常将分区按大小排队，并为
之建立一张分区说明表，其中各表项包括每个分区的起始地
址、大小及状态（是否已分配），如图3-5（a）所示。当有用
户程序要装入时，便检索该表，以找到合适的分区给予分配
并将其状态置为“已分配”,未找到合适分区则拒绝为该用户程
序分配内存。存储空间的分配情况如图3-5（b）所示
这种分区方式存在两个问题：一是程序可能太大而放不进
任何一个分区中，这时用户不得不使用覆盖技术来使用内存
空间：二是主存利用率低，当程序小于固定分区大小时，也
占用了一个完整的内存分区空间，这样分区内部有空间浪
费，这种现象称为内部碎片。
固定分区是可用于多道程序设计最简单的存储分配，无
外部碎片，但不能实现多进程共享一个主存区，所以存
储空间利用率低。固定分区分配很少用于现在通用的操
作系统中，但在某些用于控制多个相同对象的控制系统
中仍发挥着一定的作用。

3.1.4 动态分区分配

动态分区分配又称为可变分区分配，是一种动态划分内
存的分区方法。这种分区方法不预先将内存划分，而是
在进程装入内存时，根据进程的大小动态地建立分区，
并使分区的大小正好适合进程的需要。因此系统中分
区的大小和数目是可变的。

如图所示，系统有64MB内存空间，其中低8MB固定分
配给操作系统，其余为用户可用内存。开始时装入前三
个进程，在它们分别分配到所需空间后，内存只剩下
4MB，进程4无法装入。在某个时刻，内存中没有一
个就绪进程，CPU出现空闲，操作系统就换出进程2，
换入进程4.由于进程4比进程2小，这样在主存中就产
生了一个6MB的内存块。之后CPU又出现空闲，而主
存无法容纳进程2，操作系统就换出进程1，换入进程2.
动态分区在开始分配时是很好的，但是之后会导致内
存中出现许多小的内存块。随着时间的推移，内存中
会产生越来越多的碎片（图3-6中最后的4MB和中间
的6MB，且随着进程的换入换出,很可能会出现更多
更小的内存块），内存的利用率随之下降。这些小
的内存块称为外部碎片，指在所有分区外的存储空间
会变成越来越多的碎片，这与固定分区中的内部碎片
正好相对。克服外部碎片可以通过紧凑（ Compaction）技
术来解决，就是操作系统不时地对进程进行移动和整理
但是这需要动态重定位寄存器的支持，且相对费时。紧
凑的过程实际上类似于 Windows系统中的磁盘整理程序，
只不过后者是对外存空间的紧凑.
在进程装入或换入主存时，如果内存中有多个足够大的
空闲块，操作系统必须确定分配哪个内存块给进程使
用，这就是动态分区的分配策略，考虑以下几种算法

1）首次适应（ First Fit）算法：空闲分区以地址递增的
次序链接。分配内存时顺序查找，找到大小能满足要求
的第一个空闲分区
2）最佳适应（ Best Fit）算法：空闲分区按容量递增形
成分区链，找到第一个能满足要求的空闲分区
最坏适应（ Worst Fit）算法：又称最大适应（ Largest Fit）算
法，空闲分区以容量递减的次序链接。找到第一个能满足要求
的空闲分区，也就是挑选出最大的分区
3）邻近适应（ Next Fit）算法：又称循环首次适应算法，由
首次适应算法演变而成。不同之处是分配内存时从上次查找结
束的位置开始继续查找。
在这几种方法中，首次适应算法不仅是最简单的，而且通
常也是最好和最快的。在UNIX系统的最初版本中，就是使
用首次适应算法为进程分配内存空间，其中使用数组的数
据结构（而非链表）来实现。不过，首次适应算法会使得
内存的低地址部分出现很多小的空闲分区,而每次分配查找
时，都要经过这些分区，因此也增加了查找的开销。
邻近适应算法试图解决这个问题，但实际上，它常常会导
致在内存的末尾分配空间（因为在遍扫描中，内存前面部分
使用后再释放时，不会参与分配），分裂成小碎片。它通常
比首次适应算法的结果要差
最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每
次最佳的分配会留下很小的难以利用的内存块，它会产生最
多的外部碎片
最坏适应算法与最佳适应算法相反，选择最大的可用块，
这看起来最不容易产生碎片，但是却把最大的连续内存划
分开，会很快导致没有可用的大的内存块，因此性能也非常差
Knuth和 Shore分别就前三种方法对内存空间的利用情况做
了模拟实验，结果表明首次适应算法可能比最佳适应
法效果好，而它们两者一定比最大适应法效果好。另外
注意，
在算法实现时，分配操作中最佳适应法和最大适应法需
要对可用块进行排序或遍历查找，而首次适应法和邻近
适应法只需要简单查找：回收操作中，当回收的块与原
来的空闲块相邻时（有三种相邻的情况，比较复杂），
需要将这些块合并。在算法实现时，使用数组或链表进
行管理。除了内存的利用率，这里的算法开销也是操作
系统设计需要考虑的一个因素

3.1.5 基本分页存储管理的基本概念

非连续分配管理方式
非连续分配允许一个程序分散地装入到不相邻的内存分区
中。在连续分配管理方式中我们发现，即使内存有超过1GB的
空闲空间，但如果没有连续的1GB的空间，需要1GB空间的作
业仍然是无法运行的；但如果采用非连续分配管理方式，作
业所要求的1GB内存空间可以分散地分配在内存的各个区
域，当然，这也需要额外的空间去存储它们（分散区域）的
索引，使得非连续分配方式的存储密度低于连续存储方式
非连续分配管理方式根据分区的大小是否固定分为分页存储管
理方式和分段存储管理方式
分页存储管理方式中，又根据运行作业时是否要把作业
的所有页面都装入内存才能运行分为基本分页存储管理
方式和请求分页存储管理方式。下面介绍基本分页存储
管理方式。

基本分页存储管理方式

固定分区会产生内部碎片，动态分区会产生外部碎片，这
两种技术对内存的利用率都比较低.我们希望内存的使用
能尽量避免碎片的产生，这就引入了分页的思想：把主
存空间划分为大小相等且固定的块，块相对较小，作为
主存的基本单位。每个进程也以块为单位进行划分，进
程在执行时，以块为单位逐个申请主存中的块空间。分
页的方法从形式上看，像分区相等的固定分区技术，分
页管理不会产生外部碎片。但它又有本质的不同点：块
的大小相对分区要小很多，而且进程也按照块进行划
分，进程运行时按块申请主存可用空间并执行。这样，
进程只会在为最后一个不完整的块申请一个主存块空间
时，才生成主存碎片，所以尽管会产生内部碎片，但是
这种碎片相对于进程来说也是很小的，每个进程平
均只产生半个块大小的内部碎片（也称页内碎片）.

*

3.1.6 基本地址变换机构

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

3.1.8 两级页表

3.1.9 基本分段存储管理方式

3.1.10 段页式管理方式

3.1.11 虚拟内存的基本概念

1 传统存储管理方式的特征
2 局部性原理
1）时间局部性
2）空间局部性
3 虚拟存储器的定义和特征
1）多次性，是指无需在作业运行时一次性地全部装入内存，而
是允许被分成多次调入内存
2）对换性，是指无需在作业运行时一直常驻内存，而是允许
在作业的运行过程中，进行换进和换出。
3）虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内
存容量，远大于实际的内存容量。
4 虚拟内存技术的实现
虚拟内存的实现有以下三种方式
请求分页存储管理。
请求分段存储管理
请求段页式存储管理
不管哪种方式，都需要有一定的硬件支持。一般需要的支
持有以下几个方面
定容量的内存和外存
页表机制（或段表机制），作为主要的数据结构。
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
地址变换机构，逻辑地址到物理地址的变换。

3.1.12 请求分页管理方式

3.1.13 页面置换算法（决定应该换入哪页换出哪页）

3.1.14 页面分配策略

3.1.15 抖动

3.1.16 工作集

4.1 文件

4.1.1 初识文件管理

1.1 文件（File）是操作系统中的一个重要概念。文件是以计
算机硬盘为载体存储在计算机上的信息集合，文件可以是文
本文档、图片、程序，等等。

1）数据项。数据项是文件系统中最低级的数据组织形式，可
分为以下两种类型：
基本数据项：用于描述一个对象的某种属性的一个值，如
姓名、日期或证件号等，是数据中可命名的最小逻辑数据单
位，即原子数据
组合数据项：由多个基本数据项组成。
2）记录。记录是一组相关的数据项的集合，用于描述一个
对象在某方面的属性，如一个考生报名记录包括考生姓
名、出生日期、报考学校代号、身份证号等一系列域
3）文件。文件是指由创建者所定义的一组相关信息的
集合，逻辑上可分为有结构文件和无结构文件两种。
在有结构文件中，文件由一组相似记录组成，如报考
某学校的所有考生的报考信息记录，又称记录式文
件：而无结构文件则被看成是一个字符流，比如一个
二进制文件或字符文件，又称流式文件.

2 文件的属性
文件有一定的属性，这根据系统的不同而有所不同，但
是通常都包括如下属性。
1 名称：文件名称唯一，以容易读取的形式保存
2 标识符：标识文件系统内文件的唯一标签，通常
为数字，它是对人不可读的一种内部名称。
3 类型：被支持不同类型的文件系统所使用
4 位置：指向设备和设备上文件的指针。
5 大小：文件当前大小（用字节、字或块表示），也可
包含文件允许的最大值。
6 保护：对文件进行保护的访问控制信息
7 时间、日期和用户标识：文件创建、上次修改和上次
访问的相关信息，用于保护、安全跟踪文件的使用.
所有文件的信息都保存在目录结构中，而目录结构也保
存在外存上。文件信息当需要时再调入内存。通常，
目录条目包括文件名称及其唯一标识符，而标识符定
位其他属性的信息.

3 文件的基本操作
文件属于抽象数据类型。为了恰当地定义文件，就需
要考虑有关文件的操作。操作系统提供系统调用，它
对文件进行创建、写、读、定位和截断。
1 创建文件：创建文件有两个必要步骤，一是在文
件系统中为文件找到空间：二是在目录中为新文
件创建条目，该条目记录文件名称、在文件系统
中的位置及其他可能信息
2 写文件：为了写文件，执行一个系统调用，指
明文件名称和要写入文件的内容。对于给定文件名
称，系统搜索目录以查找文件位置。系统必须为该
文件维护一个写位置的指针。每当发生写操作，便更新写指针
3 读文件：为了读文件，执行一个系统调用，指明文件名称和
要读入文件块的内存位置。
同样，需要搜索目录以找到相关目录项，系统维护一个读
位置的指针。每当发生读操作时，更新读指针。一个进程
通常只对一个文件读或写，所以当前操作位置可作为每
个进程当前文件位置指针。由于读和写操作都使用同一
指针，节省了空间也降低了系统复杂度。
4 文件重定位（文件寻址）：按某条件搜索目录，将当前
文件位置设为给定值，并且不会读写文件
5 删除文件：先从目录中找到要删除文件的目录项，使之
成为空项，然后回收该文件所占用的存储空间
6 截断文件：允许文件所有属性不变，并删除文件内容，
即将其长度设为0并释放其空间
这6个基本操作可以组合执行其他文件操作。例如，一
个文件的复制，可以创建新文件、从旧文件读出并写入到新文件

4 文件的打开与关闭

4.1.2 文件的逻辑结构

按逻辑结构，文件有无结构文件和有结构文件两种类型：
1 无结构文件（流式文件）
2.有结构文件（记录式文件）
1）顺序文件。
2）索引文件
3）索引顺序文件是顺序和索引两种组织形式的结合.
4）直接文件或散列文件（ Hash File）.

4.1.3 文件目录

1 文件控制块和索引结点
1）文件控制块。文件控制块（FCB）是用来存放控制文件
需要的各种信息的数据结构，以实现“按名存取”.FCB的有
序集合称为文件目录，一个FCB就是一个文件目录项。
为了创建配一个FCB并存放在文件目录中，成为目录项
FCB主要包含以下信息：
基本信息，如文件名、文件的物理位置、文件的逻辑结
构、文件的物理结构等。
存取控制信息，如文件存取权限等
使用信息，如文件建立时间、修改时间等
2）索引结点。

目录结构

4.1.4 文件物理结构

4.1.4.1 链接分配

4.1.4.2 索引分配

4.1.5 文件存储空间管理

4.1.6 文件的基本操作

4.1.7 文件共享

4.1.8 文件保护

4.1.9 文件系统层次结构

5.1 磁盘

5.1.1 磁盘的结构

5.1.2 磁盘调度算法

5.1.3 减少磁盘延迟时间的方法

5.1.4 磁盘的管理

6.1 输入输出（I/O）管理

6.1.1 I-O设备的概念和分类

按使用特性可分为以下类型
1）人机交互类外部设备：用于与计算机用户之间交互的设备，如
打印机、显示器、鼠标、键盘等。这类设备数据交换速度相对较
慢，通常是以字节为单位进行数据交换的。

2）存储设备：用于存储程序和数据的设备，如磁盘、磁带、光
盘等。这类设备用于数据交换，速度较快，通常以多字节组成
的块为单位进行数据交换。

3）网络通信设备：用于与远程设备通信的设备，如各种网
络接口、调制解调器等。其速度介于前两类设备之间。
除了上面最常见的分类方法，I/O设备还可以按以下方法分类
1 按传输速率分类
1）低速设备：传输速率仅为每秒几个到数百个字节的一类设
备，如键盘、鼠标等。
2）中速设备：传输速率在每秒数千个字节至数万个字节的
一类设备，如行式打印机、激光打印机等
3）高速设备：传输速率在数百个千字节至千兆字节的一
类设备，如磁带机、磁盘机、光盘机等。

2 按信息交换的单位分类
1）块设备：由于信息的存取总是以数据块为单位的，所以
存储信息的设备称为块设备。它属于有结构设备，如磁盘
等。磁盘设备的基本特征是传输速率较高，以及可寻址，
即对它可随机地读/写任一块
2）字符设备：用于数据输入输出的设备为字符设备，因
为其传输的基本单位是字符。它属于无结构类型，如交互
式终端机、打印机等。它们的基本特征是传输速率低、不
可寻址，并且在输入输出时常采用中断驱动方式。

6.1.2 I-O控制器

6.1.3 I-O控制方式

设备管理的主要任务之一是控制设备和内存或处理机之间
的数据传送。外围设备和内存之间的输入输出控制方式有
四种，下面分别介绍。
1 程序直接控制方式
如图5-1（a）所示，计算机从外部设备读取数据到存储
器，每次读一个字的数据。对读入的每个字，CPU需要
对外设状态进行循环检查，直到确定该字已经在IO控
制器的数据寄存器中。在程序直接控制方式中，由于
CPU的高速性和I/O设备的低速性，致使CPU的绝大部
分时间都处于等待I/O设备完成数据I/O的循环测试中，
造成了CPU资源的极大浪费。在该方式中，CPU之所
以要不断地测试I/O设备的状态，就是因为在CPU中没有
采用中断机构，使I/O设备无法向CPU报告它已完成了
一个字符的输入操作。

2 中断驱动方式
中断驱动方式的思想是，允许I/O设备主动打断CPU的运行
并请求服务，从而“解放”CPU，使得其向I/O控制器发送读
命令后可以继续做其他有用的工作。如图5-1（b）所示，
我们从I/O控制器和CPU两个角度分别来看中断驱动方式的工作过程：
从I/O控制器的角度来看，I/O控制器从CPU接收一个读命
令，然后从外围设备读数据，一旦数据读入到该I/O控制
器的数据寄存器，便通过控制线给CPU发出一个中断信
号，表示数据已准备好，然后等待CPU请求该数据。I/O
控制器收到CPU发出的取数据请求后，将数据放到数据
总线上，传到CPU的寄存器中。至此，本次I/O操作完
成，I/O控制器又可开始下一次I/O操作。
从CPU的角度来看，CPU发出读命令，然后保存当前运
行程序的上下文（现场，包括程序计数器及处理机寄存
器），转去执行其他程序。在每个指令周期的末尾，CPU
检查中断。当有来自I/O控制器的中断时，CPU保存当
前正在运行程序的上下文，转去执行中断处理程序处理
该中断。这时，CPU从I/O控制器读一个字的数据传送到
寄存器，并存入主存。接着，CPU恢复发出
I/O命令的程序（或其他程序）的上下文，然后继续运行。
中断驱动方式比程序直接控制方式有效，但由于数据
中的每个字在存储器与I/O控制器之间的传输都必须经过
CPU，这就导致了中断驱动方式仍然会消耗较多的CPU时间。

3 DMA方式
在中断驱动方式中，I/O设备与内存之间的数据交换必须
要经过CPU中的寄存器，所以速度还是受限，而DMA
（直接存储器存取）方式的基本思想是在I/O设备和内存
之间开辟直接的数据交换通路，彻底“解放”CPU.DMA方式的特点是
1）基本单位是数据块
2）所传送的数据，是从设备直接送入内存的，或者相反。
3）仅在传送一个或多个数据块的开始和结束时，才需CPU
干预，整块数据的传送是在DMA控制器的控制下完成的。

4 通道控制方式

6.1.4 I-O软件层次结构

6.1.5 I-O核心子系统

由于I/O设备种类繁多，功能和传输速率差异巨大，需要多种方法来进行设备控制。这些方法共同组成了操作系统内核的I/O子系统，它将内核的其他方面从繁重的I/O设备管理中解放出来。I/O核心子系统提供的服务主要有：IO调度、缓冲与高速缓存、设备分配与回收、假脱机、设备保护和差错处理等。

6.1.6 假脱机技术

为了缓和CPU的高速性与I/O设备低速性之间的矛盾而引
入了脱机输入/输出技术。该技术是利用专门的外围控制
机，将低速I/O设备上的数据传送到高速磁盘上；或者相
反。 SPOOLing的意思是外部设备同时联机操作，又称为
假脱机输入输出操作，是操作系统中采用的一项将独占设
备改造成共享设备的技术。

1 输入井和输出井

2 输入缓冲区和输出缓冲区

在内存中开辟的两个缓冲区。输入缓冲区用于暂存由输
入设备送来的数据，以后再传送到输入井。输出缓冲区
用于暂存从输出井送来的数据，以后再传送到输出设备。

3 输入进程和输出进程

输入进程模拟脱机输入时的外围控制机，将用户要求
的数据从输入机通过输入缓冲区再送到输入井。当C
PU需要输入数据时，直接将数据从输入井读入内存。
输出进程模拟脱机输出时的外围控制机，把用户要求
输出的数据先从内存送到输出井，待输出设备空闲
时，再将输出井中的数据经过输出缓冲区送到输出设备

6.1.7 设备的分配与回收

1 设备分配概述
设备分配是指根据用户的I/O请求分配所需的设备。分配的
总原则是充分发挥设备的使用效率，尽可能地让设备忙碌，
又要避免由于不合理的分配方法造成进程死锁。从设备的
特性来看，采用下述三种使用方式的设备分别称为独占
设备、共享设备和虚拟设备。
1）独占式使用设备。指在申请设备时，如果设备空闲，就
将其独占，不再允许其他进程申请使用，一直等到该设备
被释放才允许其他进程申请使用。例如，打印机，在使用
它打印时，只能独占式使用，否则在同一张纸上交替打
印不同任务的内容，无法正常阅读。
2）分时式共享使用设备。独占式使用设备时，设备利用率很
低，当设备没有独占使用的要求时，可以通过分时共享使用
提高利用率。例如，对磁盘设备的I/O操作，各进程的每
次I/O操作请求可以通过分时来交替进行。
3）以 SPOOLing方式使用外部设备。 
SPOOLing（ Simultaneous Peripheral Operation On-Line）技术
是在批处理操作系统时代引入的，即假脱机IO技术。这种技术
用于对设备的操作，实质上就是对I/O操作进行批处理。
SPOOLing技术实质上是一种以空间换时间的技术，而我们
熟悉的请求分页系统中的页面调度算法就刚好相反，是以时
间换空间的技术。

2 设备分配的数据结构

3 设备分配的策略
1）设备分配原则：设备分配应根据设备特性、用户要求和
系统配置情况。分配的总原则：既要充分发挥设备的使
用效率，又要避免造成进程死锁，还要将用户程序和具体
设备隔离开。
2）设备分配方式：设备分配方式有静态分配和动态分配两种：
静态分配主要用于对独占设备的分配，它在用户作业开
始执行前，由系统一次性分配该作业所要求的全部设备、
控制器（如通道等）.一旦分配后，这些设备、控制器
（和通道）就一直为该作业所占用，直到该作业被撤销。
静态分配方式不会出现死锁，但设备的使用效率低。因
此，静态分配方式并不符合分配的总原则。
动态分配是在进程执行过程中根据执行需要进行。当进
程需要设备时，通过系统调用命令向系统提出设备请
求，由系统按照事先规定的策略给进程分配所需要的设
备、IO控制器，一旦用完之后，便立即释放。动态分
配方式有利于提高设备的利用率，但如果分配算法使用
不当，则有可能造成进程死锁。

3）设备分配算法：常用的动态设备分配算法有先请求先
分配、优先级高者优先等。
对于独占设备，既可以采用动态分配方式也可以采用静
态分配方式，往往采用静态分配方式，即在作业执行
前，将作业所要用的这一类设备分配给它。共享设备可
被多个进程所共享，一般采用动态分配方式，但在每
个I/O传输的单位时间内只被一个进程所占有，通常采
用先请求先分配和优先级高者优先的分配算法

4 设备分配的安全性
设备分配的安全性是指设备分配中应防止发生进程死锁。
1）安全分配方式：每当进程发出I/O请求后便进入
阻塞状态，直到其I/O操作完成时才被唤醒。这样，
一旦进程已经获得某种设备后便阻塞，不能再请求
任何资源，而且在它阻塞时也不保持任何资源。优
点是设备分配安全：缺点是CPU和I/O设备是串行工作
的（对同一进程而言）
2）不安全分配方式：进程在发出I/O请求后继续
运行，需要时又发出第二个、第三个I/O请求等。仅当
进程所请求的设备已被另一进程占用时，才进入阻塞状
态。优点是一个进程可同时操作多个设备，从而使进程
推进迅速；缺点是这种设备分配有可能产生死锁。

5 逻辑设备名到物理设备名的映射
为了提高设备分配的灵活性和设备的利用率、方便实
现I/O重定向，因此引入了设备独立性。设备独立性
是指应用程序独立于具体使用的物理设备。
为了实现设备独立性，在应用程序中使用逻辑设备名来
请求使用某类设备，在系统中设置张逻辑设备
表（ Logical Unit Table，LUT），用于将逻辑设备名
映射为物理设备名。LUT表项包括逻辑设备名、物理设备
名和设备驱动程序入口地址；当进程用逻辑设备名来请
求分配设备时，系统为它分配相应的物理设备，并在LUT中
建立一个表项，以后进程再利用逻辑设备名请求IO操作时，系统
通过查找LUT来寻找相应的物理设备和驱动程序。
在系统中可采取两种方式建立逻辑设备表
1）在整个系统中只设置一张LUT.这样，所有进程的设
备分配情况都记录在这张表中，故不允许有相同的逻辑
设备名，主要适用于单用户系统中。
2）为每个用户设置一张LUT.当用户登录时，系统便
为该用户建立一个进程，同时也为之建立一张
LUT，并将该表放入进程的PCB中。

6.1.8 缓冲区管理

1 磁盘高速缓存（ Disk Cache）
操作系统中使用磁盘高速缓存技术来提高磁盘的I/O速度，对
高速缓存复制的访问要比原始数据访问更为高效。例如，正
在运行的进程的指令既存储在磁盘上，也存储在物理内存
上，也被复制到CPU的二级和一级高速缓存中。
不过，磁盘高速缓存技术不同于通常意义下的介于CPU与
内存之间的小容量高速存储器，而是指利用内存中的存储
空间来暂存从磁盘中读出的一系列盘块中的信息。因此，磁
盘高速缓存在逻辑上属于磁盘，物理上则是驻留在内存中的
盘块。高速缓存在内存中分为两种形式：一种是在内存
中开辟一个单独的存储空间作为磁盘高速缓存，大小固
定；另一种是把未利用的内存空间作为一个缓冲池，供请
求分页系统和磁盘I/O时共享。

2 缓冲区（ Buffer）
在设备管理子系统中，引入缓冲区的目的主要有：
1）缓和CPU与I/O设备间速度不匹配的矛盾。
2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制
3）解决基本数据单元大小（即数据粒度）不匹配的问题。
4）提高CPU和I/O设备之间的并行性
其实现方法有：
1）采用硬件缓冲器，但由于成本太高，除一些关键部位外，一般不采用硬件缓冲器。
2）采用缓冲区（位于内存区域）.
缓冲区有一个特点，当缓冲区的数据非空的时候，不
能往缓冲区冲入数据，只能从缓冲区把数据传出；当
缓冲区为空时，可以往缓冲区冲入数据，但必须把
缓冲区充满以后，才能从缓冲区把数据传出。
根据系统设置缓冲器的个数，缓冲技术可以分为
1）单缓冲：在设备和处理机之间设置一个缓冲区。设
备和处理机交换数据时，先把被交换
数据写入缓冲区，然后需要数据的设备或处理机从缓
冲区取走数据。
2）双缓冲：根据单缓冲的特点，CPU在传送时间M内处
于空闲状态，由此引入双缓冲。I/O设备输入数据时先装
填到缓冲区1，在缓冲区1填满后才开始装填缓冲区2，与
此同时处理机可
以从缓冲区1中取出数据放入用户进程处理，当缓冲区1中
的数据处理完后，若缓冲区2已填满，则处理机又从缓冲
区2中取出数据放入用户进程处理，而IO设备又可以装填
缓冲区1.要注意，必须等缓冲区2充满才能让处理机从缓
冲区2取出数据。双缓冲机制提高了处理机和输入设备的
并行操作的程度

3）循环缓冲：包含多个大小相等的缓冲区，每个缓冲区
中有一个链接指针指向下一个缓冲，最后一个缓冲区指针
指向第一个缓冲区，多个缓冲区构成一个环形。
循环缓冲用于输入输出时，还需要有两个指针in和out对输
入而言，首先要从设备接收数据到缓冲区中，in指针指向
可以输入数据的第一个空缓冲区；当运行进程需要数据
时，从循环缓冲区中取一个装满数据的缓冲区，并从此
缓冲区中提取数据，out指针指向可以提取数据的第一
个满缓冲区。输出则正好相反.

4）缓冲池：由多个系统公用的缓冲区组成，缓冲区按其
使用状况可以形成三个队列：空缓冲队列、装满输入数
据的缓冲队列（输入队列）和装满输出数据的缓冲
队列（输出队列）.还应具有四种缓冲区：用于收容输入数
据的工作缓冲区、用于提取输入数据的工作缓冲区、用于
收容输出数据的工作缓冲区及用于提取输出数据的工作缓冲区.

想要获取该该课程markdown笔记（脑图+笔记）。可以扫描以下
微信公众号二维码。或者搜索微信公众号-Java大世界。回复
操作系统，即可获取笔记获取方式。