计算机操作系统杂记
1.操作系统
操作系统的作用：
1.os作为用户与计算机硬件系统之间的接口;
这种接口是软件接口。
用户可以通过3种方式使用计算机：
1.命令方式；
2.系统调用方式；
3.图形、窗口方式。
2.os作为计算机系统资源的管理者
资源分为四类：
处理器、存储器、i/o设备以及信息（数据和程序）
对应的：
处理机管理：用于分配和控制处理机；
存储器管理：主要负责内存的分配和回收；
I/O设备管理：负责I/O设备的分配和操纵；
文件管理：负责文件的存取、共享和保护。
3.os实现了对计算机资源的抽象
分时系统：
分时系统可以很好地将一台计算机提供给多个用户同时
使用，提高计算机的利用率。
分时系统实现中的关键问题：
1.及时接收；
2.及时处理。
为实现人机交互，必须彻底改变原来的批处理系统的
运行方式。
首先，用户作业不能先进入磁盘，然后再调入内存。
因为作业在磁盘上不能运行，当然用户也无法与机器交互，
因此，作业应直接进入内存。
其次，不允许一个作业长期占用处理机，直至它运行结束
或出现I/O请求后，方才调度其他作业运行。
为此，应该规定每个作业只运行一个很短的时间
例如0.1秒，通常把这段时间成为时间片，
然后便暂停该作业的运行，并立即调度下一个程序运行。
如果在不长的时间如3秒内能使所有的用户作业
都执行一次，也就是一个时间片的时间，
便可使每个用户都能及时地与自己的作业交互，从而
可使用户的请求得到及时的响应。
实时系统：
实时系统是指系统能及时响应外部事件的请求，在
规定的时间内完成对该事件的处理，并
控制所有实时任务协调一致地运行。
操作系统的基本特性：
并行和并发：
并行性是指两个或多个事件在同一时刻发生；
而并发性是指两个或多个事件在同一时间间隔内发生。
在多道程序环境下，并发性是指在一段时间内
宏观上有多个程序在同时运行，
但在单处理机系统中，每一时刻仅能有一道程序执行，
故微观上这些程序只能是分时地交替执行。
倘若在计算机系统中有多个处理机，则这些可以
并发执行的程序便可分配到多个处理机上，
实现并行执行，即利用每个处理机来处理一个
可并发执行的程序。
这样，多个程序便可同时执行。
引入进程：
在操作系统中引入进程的目的，就是为了使多个
程度能并发执行。
这样可以极大地提高系统资源的利用率，增加系统的吞吐量。
为使多个程序能并发执行，系统必须分别为每个程序
建立进程。
简单来说，进程是指在系统中能
独立运行 并作为资源分配的基本单位。
他是由一组机器指令、数据和堆栈等组成的，
是一个能独立运行的活动实体。
多个进程之间可以并发执行和交换信息。
引入线程：
进程是操作系统中可以拥有资源并独立运行的基本单位。
当一个进车因故不能继续运行时，操作系统
便调度另一进程运行。
由于进程拥有自己的资源，故使调度的付出的开销较大。
通常在一个进程中包含若干个线程，他们
可以利用进程所拥有的资源。
在引入线程的os中，通常都是把进程作为分配
资源的基本单位，
而把线程作为独立运行和独立调度的基本单位。
由于线程比进程更小，基本上不拥有系统资源，
故对它的调度所付出的开销就会小得多，能更
高效地提高系统内多个程序间并发执行的而程度。
引入线程，进一步提高系统的并发性。
共享性：
系统中的资源供内存中多个并发执行的进程，线程
共同使用，相应的，把这种资源共同使用称为资源共享，
或称为资源复用。
目前主要实现资源共享的方式有如下两种：
1.互斥共享方式
计算机系统中的大多数物理设备，以及
某些软件中所用的栈、变量和表格，
都属于临界资源，他们要求被互斥地共享。
2.同时访问方式
这里所谓的“同时”，宏观上，和微观上。
典型的可供多个进程“同时”访问的资源是磁盘设备，
一些用重入码编写的文件也可以
“同时”共享，即若干个用户同时访问该文件。
虚拟技术：
通过某种技术把一个物理实体变为若干个逻辑上的对应物。
物理实体是实的，即实际存在的，
而后者是虚的，仅是用户感觉上的东西，
相应的，用于实现虚拟的技术成为虚拟技术。
在操作系统中利用了两种方式实现虚拟技术，
就是时分复用技术和空分复用技术。
1.时分复用技术：
时分复用，就是分时使用方式。。
为了提高信道利用率，人们利用时分复用方式，
将一条物理信道虚拟为多条逻辑信道，
将每条信道供一对用户通话。
1.虚拟处理机技术
利用多道程序设计技术，为每道程序建立一个进程，让多道程
序并发地执行，以此来分时使用一台处理机。此时，虽然系统中只有一台处理机，但它却
能同时为多个用户服务，使每个终端用户都认为是有一个处理机在专门为他服务。亦即，
利用多道程序设计技术，把一台物理上的处理机虚拟为多台逻辑上的处理机，在每台逻辑
处理机上运行一道程序。我们把用户所感觉到的处理机称为虚拟处理器
2.虚拟设备技术
我们还可以通过虚拟设备技术，将一台物理 I/O 设备虚拟为多台逻辑上的 I/O 设备，并
允许每个用户占用一台逻辑上的 I/O 设备，这样便可使原来仅允许在一段时间内由一个用户
访问的设备(即临界资源)，变为在一段时间内允许多个用户同时访问的共享设备。例如，原
来的打印机属于临界资源，而通过虚拟设备技术，可以把它变为多台逻辑上的打印机，供
多个用户“同时”打印。
2.空分复用技术
联系频分复用技术。
使用空分复用技术提高存储空间的利用率。
1.虚拟磁盘技术
通常在一台机器上只配置一台硬盘。我们可以通过虚拟磁盘技术将一台硬盘虚拟为多
台虚拟磁盘，这样使用起来既方便又安全。虚拟磁盘技术也是采用了空分复用方式，即它
将硬盘划分为若干个卷，例如 1、2、3、4 四个卷，再通过安装程序将它们分别安装在 C、
D、E、F 四个逻辑驱动器上，这样，机器上便有了四个虚拟磁盘。当用户要访问 D 盘中的
内容时，系统便会访问卷 2 中的内容。
2.虚拟存储器技术
在单道程序环境下，处理机会有很多空闲时间，内存也会有很多空闲空间，显然，这
会使处理机和内存的效率低下。如果说时分复用技术是利用处理机的空闲时间来运行其它
的程序，使处理机的利用率得以提高，那么空分复用则是利用存储器的空闲空间来存放其
它的程序，以提高内存的利用率
但是，单纯的空分复用存储器只能提高
内存的利用率，并不能实现在逻辑上扩大
存储器容量的功能，必须引入虚拟存储技术
才能达到此目的。
虚拟存储技术在本质上就是使内存分时复用。
他可以使一道程序通过时分复用方式，
在远小于它的内存空间中运行。
例如，一个100M的应用程序
可以运行在20M的空间。
异步性：
由于资源等因素的限制，进程的执行通常都不是
“一气呵成”的，而是“走走停停”的。
由于各用户程序性能的不同，比如，
有的侧重于计算而较少需要I/O，
而有的程序其计算少而I/O多。
这样，很可能是先进入内存的作业后完成，
后进入内存的作业先完成。
或者说，进程是以人们不可预知的速度向前推进。
这就是进程的异步性。
尽管如此，但只要在操作系统中配置有完善的
进程同步机制，且运行环境相同，
作业经多次运行都会获得完全相同的结果。
因此，异步运行方式是允许的。
操作系统的主要功能：
1.处理机管理功能：
1.进程控制
主要功能是为作业创建进程，撤销已结束的进程，
以及控制进程在运行过程中的状态转换。
2.进程同步
进程同步的主要任务是为多个进程含线程的运行进行协调。
有两种协调方式：
进程互斥方式、进程同步方式。
3.进程通信
例如，有三个相互合作的进程，
他们是输入进程、计算进程、打印进程。
进程通信的任务是用来实现在相互合作的进程之间的信息交换。
4.调度
在后备队列上等待的每个作业都需经过调度才能执行。
在传统的操作系统中，
包括作业调度和进程调度两步。
1.作业调度。
作业调度的基本任务是从后备队列中按照一定的算法，选择出若干个
作业，为它们分配运行所需的资源(首先是分配内存)。在将它们调入内存后，便分别为它
们建立进程，使它们都成为可能获得处理机的就绪进程，并按照一定的算法将它们插入就
绪队列。
2.进程调度
进程调度的任务是从进程的就绪队列中，按照一定的算法选出一个进程，
把处理机分配给它，并为它设置运行现场，使进程投入执行。值得提出的是，在多线程 OS
中，通常是把线程作为独立运行和分配处理机的基本单位，为此，须把就绪线程排成一个
队列，每次调度时，是从就绪线程队列中选出一个线程，把处理机分配给它。
2.存储器管理功能
存储器管理应该提高存储器的利用率以及
能从逻辑上扩充内存。
为此，存储器管理应具有内存分配、内存保护。
地址映射和内存扩充等功能。
1.内存分配
内存分配的主要任务是为每道程序分配内存空间，
使他们“各得其所”；提高存储器的利用率，
以减少不可用的内存空间；
允许正在运行的程序申请附加的内存空间，
以适应程序和数据动态增长的需要。
OS 在实现内存分配时，可采取静态和动态两种方式。在静态分配方式中，每个作业的
内存空间是在作业装入时确定的；在作业装入后的整个运行期间，不允许该作业再申请新
的内存空间，也不允许作业在内存中“移动”。在动态分配方式中，每个作业所要求的基本
内存空间也是在装入时确定的，但允许作业在运行过程中继续申请新的附加内存空间，以
适应程序和数据的动态增长，也允许作业在内存中“移动”。
1.内存分配数据结构；
2.内存分配功能；
3.内存回收功能。
2.内存保护
内存保护的主要任务是确保每道用户程序都只在自己的内存空间内运行，彼此互不干
扰；绝不允许用户程序访问操作系统的程序和数据；也不允许用户程序转移到非共享的其
它用户程序中去执行。
为了确保每道程序都只在自己的内存区中运行，必须设置内存保护机制。一种比较简
单的内存保护机制是设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。系
统须对每条指令所要访问的地址进行检查，如果发生越界，便发出越界中断请求，以停止
该程序的执行。如果这种检查完全用软件实现，则每执行一条指令，便须增加若干条指令
去进行越界检查，这将显著降低程序的运行速度。因此，越界检查都由硬件实现。当然，
对发生越界后的处理，还须与软件配合来完成。
3.地址映射
一个应用程序(源程序)经编译后，通常会形成若干个目标程序；这些目标程序再经过链
接便形成了可装入程序。这些程序的地址都是从“0”开始的，程序中的其它地址都是相对
于起始地址计算的。由这些地址所形成的地址范围称为“地址空间”，其中的地址称为“逻
辑地址”或“相对地址”。此外，由内存中的一系列单元所限定的地址范围称为“内存空间”，
其中的地址称为“物理地址”。
在多道程序环境下，每道程序不可能都从“0”地址开始装入(内存)，这就致使地址空
间内的逻辑地址和内存空间中的物理地址不相一致。为使程序能正确运行，存储器管理必
须提供地址映射功能，以将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。
该功能应在硬件的支持下完成。
4.内存扩充
存储器管理中的内存扩充任务并非是去扩大物理内存的容量，而是借助于虚拟存储技
术，从逻辑上去扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多，以便
让更多的用户程序并发运行。这样，既满足了用户的需要，又改善了系统的性能。为此，
只需增加少量的硬件。为了能在逻辑上扩充内存，系统必须具有内存扩充机制，用于实现
下述各功能：
1.请求调入功能。
允许在装入一部分用户程序和数据的情况下，
便能启动该程序运行。在程序运行过程中，若发现要继续
运行时所需的程序和数据尚未装入内存，
可向os发出请求，由os从磁盘中将所需部分调入内存，
以便继续运行。程序局部性原理。
2.置换功能
若发现在内存中已无足够的空间来转入需要
调入的程序和数据时，系统应能将内存中
的一部分暂时不用的程序和数据调至磁盘上，
以腾出内存空间，然后再将所需的部分装入内存。
3.设备管理功能
设备管理用于管理计算机系统中所有的外围设备，而设备管理的主要任务是：完成用
户进程提出的 I/O 请求；为用户进程分配其所需的 I/O 设备；提高 CPU 和 I/O 设备的利用
率；提高 I/O 速度；方便用户使用 I/O 设备。为实现上述任务，设备管理应具有缓冲管理、
设备分配和设备处理以及虚拟设备等功能。
1.缓冲管理
CPU 运行的高速性和 I/O 低速性间的矛盾自计算机诞生时起便已存在了。而随着 CPU
速度迅速提高，使得此矛盾更为突出，严重降低了 CPU 的利用率。如果在 I/O 设备和 CPU
之间引入缓冲，则可有效地缓和 CPU 与 I/O 设备速度不匹配的矛盾，提高 CPU 的利用率，
进而提高系统吞吐量。因此，在现代计算机系统中，都无一例外地在内存中设置了缓冲区，
而且还可通过增加缓冲区容量的方法来改善系统的性能。
对于不同的系统，可以采用不同的缓冲区机制。最常见的缓冲区机制有单缓冲机制、
能实现双向同时传送数据的双缓冲机制，以及能供多个设备同时使用的公用缓冲池机制。
上述这些缓冲区都将由 OS 中的缓冲管理机制将它们管理起来。
2.设备分配
设备分配的基本任务是根据用户进程的 I/O 请求、系统的现有资源情况以及按照某种设
备的分配策略，为之分配其所需的设备。如果在 I/O 设备和 CPU 之间还存在着设备控制器
和 I/O 通道时，还须为分配出去的设备分配相应的控制器和通道。
为了实现设备分配，系统中应设置设备控制表、控制器控制表等数据结构，用于记录
设备及控制器的标识符和状态。根据这些表格可以了解指定设备当前是否可用，是否忙碌，
以供进行设备分配时参考。在进行设备分配时，应针对不同的设备类型而采用不同的设备
分配方式。对于独占设备(临界资源)的分配，还应考虑到该设备被分配出去后系统是否安全。
在设备使用完后，应立即由系统回收。
3.设备处理
设备处理程序又称为设备驱动程序。其基本任务是用于实现 CPU 和设备控制器之间的
通信，即由 CPU 向设备控制器发出 I/O 命令，要求它完成指定的 I/O 操作；反之，由 CPU
接收从控制器发来的中断请求，并给予迅速的响应和相应的处理。
处理过程是：设备处理程序首先检查 I/O 请求的合法性，了解设备状态是否是空闲的，
了解有关的传递参数及设置设备的工作方式。然后，便向设备控制器发出 I/O 命令，启动 I/O
设备去完成指定的 I/O 操作。设备驱动程序还应能及时响应由控制器发来的中断请求，并根
据该中断请求的类型，调用相应的中断处理程序进行处理。对于设置了通道的计算机系统，
设备处理程序还应能根据用户的 I/O 请求，自动地构成通道程序。
4.文件管理功能
在现代的计算机管理中，总是把程序和数据以文件的
形式存储在磁盘和磁带上，供所有的或指定的用户使用。
为此，在操作系统中必须配置文件管理机构。
文件管理的主要任务是对用户文件和系统文件进行管理，
以方便用户使用，并保证文件的安全性。
为此，文件管理应具有对文件存储空间的 管理。
目录管理、文件的读写管理、以及
文件的共享和保护等功能。
1.文件存储空间的管理
为了方便用户的使用，对于一些当前需要使用的系统文件和用户文件，都必须放在可
随机存取的磁盘上。在多用户环境下，若由用户自己对文件的存储进行管理，不仅非常困
难，而且也必然是十分低效的。因而，需要由文件系统对诸多文件及文件的存储空间实施
统一的管理。其主要任务是为每个文件分配必要的外存空间，提高外存的利用率，并能有
助于提高文件系统的存、取速度。
为此，系统应设置相应的数据结构，用于记录文件存储空间的使用情况，以供分配存
储空间时参考；系统还应具有对存储空间进行分配和回收的功能。为了提高存储空间的利
用率，对存储空间的分配，通常是采用离散分配方式，以减少外存零头，并以盘块为基本
分配单位。盘块的大小通常为 1～8 KB
2.目录管理
为了使用户能方便地在外存上找到自己所需的文件，通常由系统为每个文件建立一个
目录项。目录项包括文件名、文件属性、文件在磁盘上的物理位置等。由若干个目录项又
可构成一个目录文件。目录管理的主要任务是为每个文件建立其目录项，并对众多的目录
项加以有效的组织，以实现方便的按名存取，即用户只须提供文件名便可对该文件进行存
取。其次，目录管理还应能实现文件共享，这样，只须在外存上保留一份该共享文件的副
本。此外，还应能提供快速的目录查询手段，以提高对文件的检索速度。
3.文件的读写管理和保护
(1) 文件的读/写管理。该功能是根据用户的请求，从外存中读取数据，或将数据写入
外存。在进行文件读(写)时，系统先根据用户给出的文件名去检索文件目录，从中获得文件
在外存中的位置。然后，利用文件读(写)指针，对文件进行读(写)。一旦读(写)完成，便修
改读(写)指针，为下一次读(写)做好准备。由于读和写操作不会同时进行，故可合用一个
读/写指针。
(2) 文件保护。为了防止系统中的文件被非法窃取和破坏，在文件系统中必须提供有效
的存取控制功能，以实现下述目标：
① 防止未经核准的用户存取文件；
② 防止冒名顶替存取文件；
③ 防止以不正确的方式使用文件。
微内核操作系统的优点
由于微内核 OS 结构是建立在模块化、层次化结构的基础上的，并采用了客户/服务器
模式和面向对象的程序设计技术，由此可见，微内核结构的 OS 是集各种技术优点之大成，
因而使之具有如下优点：
1) 提高了系统的可扩展性
由于微内核 OS 的许多功能是由相对独立的服务器软件来实现的，当开发了新的硬件和
软件时，微内核 OS 只须在相应的服务器中增加新的功能，或再增加一个专门的服务器。与
此同时，也必然改善系统的灵活性，不仅可在操作系统中增加新的功能，还可修改原有功
能，以及删除已过时的功能，以形成一个更为精干有效的操作系统。
2) 增强了系统的可靠性
这一方面是由于微内核是出于精心设计和严格测试的，容易保证其正确性；另一方面
是它提供了规范而精简的应用程序接口(API)，为微内核外部的程序编制高质量的代码创造
了条件。此外，由于所有服务器都是运行在用户态，服务器与服务器之间采用的是消息传
递通信机制，因此，当某个服务器出现错误时，不会影响内核，也不会影响其它服务器。
3) 可移植性
随着硬件的快速发展，出现了各种各样的硬件平台，作为一个好的操作系统，必须具
备可移植性，使其能较容易地运行在不同的计算机硬件平台上。在微内核结构的操作系统
中，所有与特定 CPU 和 I/O 设备硬件有关的代码，均放在内核和内核下面的硬件隐藏层中，
而操作系统其它绝大部分(即各种服务器)均与硬件平台无关，因而，把操作系统移植到另一
个计算机硬件平台上所需作的修改是比较小的。
4) 提供了对分布式系统的支持
由于在微内核 OS 中，客户和服务器之间以及服务器和服务器之间的通信，是采用消息
传递通信机制进行的，致使微内核 OS 能很好地支持分布式系统和网络系统。事实上，只要
在分布式系统中赋予所有进程和服务器惟一的标识符，在微内核中再配置一张系统映射表
(即进程和服务器的标识符与它们所驻留的机器之间的对应表)，在进行客户与服务器通信
时，只需在所发送的消息中标上发送进程和接收进程的标识符，微内核便可利用系统映射
表，将消息发往目标，而无论目标是驻留在哪台机器上。
5) 融入了面向对象技术
在设计微内核 OS 时，采用了面向对象的技术，其中的“封装”，“继承”，“对象类”和
“多态性”，以及在对象之间采用消息传递机制等，都十分有利于提高系统的“正确性”、“可
靠性”、“易修改性”、“易扩展性”等，而且还能显著地减少开发系统所付出的开销。
2.进程管理
程序顺序执行。
程序并发执行。结合流水线处理来思考。
例如，输入程序在输入第一个程序后，
在计算程序对该程序进行计算的同时，
可由输入程序再输入第二个程序，
从而使第一个程序的计算操作可与
第二个程序的输入操作并发执行。
进程的特征和定义
1.结构特征：
通常的程序时不能并发执行的。
为使程序含数据能独立运行，应为之
配置一进程控制块PCB；
而由程序段、相关的数据段、PCB
三部分组成的进程实体。
实际上大多数情况下的进程，是指进程实体。
所谓创建进程，实质上是创建进程实体中的PCB；
而撤销进程，实质上是撤销进程的PCB。
2.动态性：
进程的是指是进程实体的一次执行过程，
因此，动态性是进程的最基本的特征。
动态性还表现在：
它由创建而产生，
由调度而执行，
由撤销而消亡。
进程实体具有一定的生命期，
而程序只是一组有序指令的集合，
并存放于某种介质中，
其本身并不具有运动的含义，因而是静态的。
3.并发性：
这是指多个进程实体同存于内存中，
且能在一段时间内同时运行。
没有建立PCB是不能并发执行的。
4.独立性：
独立性是指进程实体是一个
能独立运行、
能独立分配资源、
能独立接受调度的基本单位。
5.异步性：
进程按各自独立的、不可预知的速度向前推进，
或说进程实体按异步方式运行。
进程定义：
(1) 进程是程序的一次执行。
(2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
(3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独
立单位。
进程的3种基本装态：
1) 就绪(Ready)状态
当进程已分配到除 CPU 以外的所有必要资源后，只要再获得 CPU，便可立即执行，进
程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们
排成一个队列，称为就绪队列。
2) 执行状态
进程已获得 CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；
在多处理机系统中，则有多个进程处于执行状态。
3) 阻塞状态
正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，
亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。
致使进程阻塞的典型事件有：请求 I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也
排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。
处于就绪装态的进程，在调度程序为之分配了
处理机之后，该进程便可执行，相应的，它就由就绪装态转变为
执行状态。
正在执行的进程也被称为当前进程，如果
因分配给他的时间片已完而被暂停执行时，
该进程便由执行状态回复到就绪装态；
如果因发生某事件而使进程的执行受阻，
例如，进程请求访问某临界资源，而该资源正在被其他进程访问时，
使之无法继续执行，该进程将由执行状态转变为
阻塞状态。
阻塞状态只能由执行状态变成；
阻塞状态只能变成就绪状态；
就绪状态和执行状态可以互相转换。
另外的为了管理需要增加的状态
挂起状态
创建状态和终止状态
创建状态：
创建一个进程一般要通过两个步骤：
首先，为一个新进程创建PCB，并填写必要的管理信息；
其次，把该进程转入就绪状态并插入就绪队列中。
，一般而言，此时的进程已拥有了自己的 PCB，但进程自身还未进
入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。
引入创建状态，是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控
制块操作的完整性。同时，创建状态的引入，也增加了管理的灵活性，操作系统可以根据
系统性能或主存容量的限制，推迟创建状态进程的提交。对于处于创建状态的进程，获得
了其所必需的资源，以及对其PCB初始化工作完成后，进程状态便可由创建状态转入就绪
状态。
终止状态：
进程的终止也要通过两个步骤：
首先等待操作系统进行善后处理，
然后将将其PCB空间返还系统。
当一个进程到达了自然结束点，
或是出现了无法克服的错误，
或者是被操作系统所终结，
或是被其他有终止权的进程所终结，
他将进入终止状态。
进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计
时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操
作系统将删除该进程。
进程控制块:
os是根据PCB来对并发执行的进程进行控制和管理的。
例如，当 OS 要调度某进程执行时，要从该进程的 PCB
中查出其现行状态及优先级；在调度到某进程后，要根据其 PCB 中所保存的处理机状态信
息，设置该进程恢复运行的现场，并根据其 PCB 中的程序和数据的内存始址，找到其程序
和数据；进程在执行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也
都需要访问 PCB；当进程由于某种原因而暂停执行时，又须将其断点的处理机环境保存在
PCB 中。可见，在进程的整个生命期中，系统总是通过 PCB 对进程进行控制的，亦即，系
统是根据进程的 PCB 而不是任何别的什么而感知到该进程的存在的。所以说，PCB 是进程
存在的惟一标志。
当系统创建一个新进程时，就为它建立了一个 PCB；进程结束时又回收其 PCB，进程
于是也随之消亡。PCB 可以被操作系统中的多个模块读或修改，如被调度程序、资源分配
程序、中断处理程序以及监督和分析程序等读或修改。因为 PCB 经常被系统访问，尤其是
被运行频率很高的进程及分派程序访问，故 PCB 应常驻内存。系统将所有的 PCB 组织成若
干个链表(或队列)，存放在操作系统中专门开辟的 PCB 区内。例如在 Linux 系统中用
task_struct 数据结构来描述每个进程的进程控制块，在 Windows 操作系统中则使用一个执行
体进程块(EPROCESS)来表示进程对象的基本属性
进程控制块中的信息：
1.进程标识符：
进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：
(1) 内部标识符。在所有的操作系统中，都为每一个进程赋予了一个惟一的数字标识符，
它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。
(2) 外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在
访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，
还可设置用户标识，以指示拥有该进程的用户。
2.处理机状态：
处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时，许
多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在 PCB 中，以便在
该进程重新执行时，能从断点继续执行。这些寄存器包括：① 通用寄存器，又称为用户可
视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 8～32 个
通用寄存器，在 RISC 结构的计算机中可超过 100 个；② 指令计数器，其中存放了要访问
的下一条指令的地址；③ 程序状态字 PSW，其中含有状态信息，如条件码、执行方式、中
断屏蔽标志等；④ 用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用
于存放过程和系统调用参数及调用地址，栈指针指向该栈的栈顶。
3.进程调度信息：
在 PCB 中还存放一些与进程调度和进程对换有关的信息，包括：① 进程状态，指明进
程的当前状态，作为进程调度和对换时的依据；② 进程优先级，用于描述进程使用处理机
的优先级别的一个整数，优先级高的进程应优先获得处理机；③ 进程调度所需的其它信息，
它们与所采用的进程调度算法有关，比如，进程已等待 CPU 的时间总和、进程已执行的时
间总和等；④ 事件，指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
4.进程控制信息：
进程控制信息包括：① 程序和数据的地址，指进程的程序和数据所在的内存或外存地
(首)址，以便再调度到该进程执行时，能从 PCB 中找到其程序和数据；② 进程同步和通信
机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能
全部或部分地放在 PCB 中；③ 资源清单，即一张列出了除 CPU 以外的、进程所需的全部
资源及已经分配到该进程的资源的清单；④ 链接指针，它给出了本进程(PCB)所在队列中
的下一个进程的 PCB 的首地址。
进程控制块组织方式：
链接方式
索引方式
进程控制
进程控制一般是由os的内核中的原语来实现的。
原语是由若干条指令组成的额，用于完成一定功能的一个过程。
他与一般过程的区别在于：
所谓原子操作，是指一个操作中的所有动作要么全做，
要么全部做。
换言之，他是一个不可分割的基本单位。
因此，在执行的过程中不允许被中断。
原子操作在管态下执行，常驻内存。
原语的作用是为了实现进程的通信和控制，
系统对进行的控制如不适用原语，
就会造成其状态的不确定性，
从而达不到进程控制的目的。
子进程可以继承父进程所拥有的资源，例
如，继承父进程打开的文件，继承父进程所分配到的缓冲区等。当子进程被撤消时，应将
其从父进程那里获得的资源归还给父进程。此外，在撤消父进程时，也必须同时撤消其所
有的子进程。为了标识进程之间的家族关系，在 PCB 中都设置了家族关系表项，以标明自
己的父进程及所有的子进程。
导致一个进程去创建另一个进程的典型事件
四类：
1.用户登录；
2.作业调度；
3.提供服务；
4.应用请求。
调用进程创建原语Creat（）创建一个新进程：
1.申请空白PCB；
2.为新进程分配资源；
3.初始化进程控制块。
4.将新进程插入就绪队列。
进程的终止：
1.正常结束；
2.异常结束
在进程运行期间，由于出现某些错误和故障而迫使进程终止(Termination of Process)。
这类异常事件很多，常见的有下述几种：
(1) 越界错误。这是指程序所访问的存储区已越出该进程的区域。
(2) 保护错。这是指进程试图去访问一个不允许访问的资源或文件，或者以不适当的方
式进行访问，例如，进程试图去写一个只读文件。
(3) 非法指令。这是指程序试图去执行一条不存在的指令。出现该错误的原因，可能是
程序错误地转移到数据区，把数据当成了指令。
(4) 特权指令错。这是指用户进程试图去执行一条只允许 OS 执行的指令。
(5) 运行超时。这是指进程的执行时间超过了指定的最大值。
(6) 等待超时。这是指进程等待某事件的时间超过了规定的最大值。
(7) 算术运算错。这是指进程试图去执行一个被禁止的运算，例如被 0 除。
(8) I/O 故障。这是指在 I/O 过程中发生了错误等。
3.外界干预
外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运
行。这些干预有：
(1) 操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统
终止该进程。
(2) 父进程请求。由于父进程具有终止自己的任何子孙进程的权力，因而当父进程提出
请求时，系统将终止该进程。
(3) 父进程终止。当父进程终止时，OS 也将它的所有子孙进程终止。
进程的终止过程：
1.根据被终止进程的标识符，
从PCB集合中检索出该进程的PCB，
从中读出该进程的状态；
2.若该终止进程正处于执行状态，
应立即终止该进程的执行，
并置调度标志为真，
用于指示该进程被终止后应重新进行调度；
3.若该进程还有子孙进程，
还应将其子孙进程予以终止，
以防他们成为不可控的进程。
4.将被终止进程所拥有的全部资源，
或者归还给父进程，
或者归还给系统；
5.将被终止进程PCB从所在队列或链表中移出，
等待其他程序来搜集信息。
进程阻塞和唤醒：
进程阻塞过程
正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻
塞原语 block 把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入 block 过程
后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状
态由“执行”改为“阻塞”，并将 PCB 插入阻塞队列。如果系统中设置了因不同事件而阻塞
的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序
进行重新调度，将处理机分配给另一就绪进程并进行切换，亦即，保留被阻塞进程的处理
机状态(在 PCB 中)，再按新进程的 PCB 中的处理机状态设置 CPU 的环境
进程唤醒过程：
当被阻塞进程所期待的事件出现时，如 I/O 完成或其所期待的数据已经到达，则由有关
进程(比如用完并释放了该 I/O 设备的进程)调用唤醒原语 wakeup( )，将等待该事件的进程唤
当被阻塞进程所期待的事件出现时，如 I/O 完成或其所期待的数据已经到达，则由有关
进程(比如用完并释放了该 I/O 设备的进程)调用唤醒原语 wakeup( )，将等待该事件的进程唤
3.进程同步
进程同步的主要任务是对多个相关进程在
执行次序上进行协调，以使并发执行的诸进程之间
能有效地共享资源和相互合作，
从而使程序的执行具有可再现性。
临界资源
生产者-消费者问题：
生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一
群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消
费者进程能并发执行，在两者之间设置了一个具有 n 个缓冲区的缓冲池，生产者进程将它
所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所
有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允
许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被
取走的缓冲区中投放产品。
具体问题及解答可以参看计算机操作系统P58.
关键点还是原子操作。
要把变量counter作为临街资源处理，
令生产者进程和消费者进程互斥地访问变量counter
同步机制应遵循的原则：
同步机制应遵循的规则
为实现进程互斥地进入自已的临界区，可用软件方法，更多的是在系统中设置专门的
同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：
(1) 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求
进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
(2) 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进
入临界区的进程必须等待，以保证对临界资源的互斥访问。
(3) 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，
以免陷入“死等”状态。
(4) 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙
等”状态。
信号量机制：
信号量机制是一种卓有成效的进程同步工具。
信号量的应用
1.利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量 mutex，并设
其初始值为 1，然后将各进程访问该资源的临界区 CS 置于 wait(mutex)和 signal(mutex)操作
之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对 mutex 执行
wait 操作，若该资源此刻未被访问，本次 wait 操作必然成功，进程便可进入自己的临界区，
这时若再有其他进程也欲进入自己的临界区，此时由于对 mutex 执行 wait 操作定会失败，
为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量 mutex，并设
其初始值为 1，然后将各进程访问该资源的临界区 CS 置于 wait(mutex)和 signal(mutex)操作
之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对 mutex 执行
wait 操作，若该资源此刻未被访问，本次 wait 操作必然成功，进程便可进入自己的临界区，
这时若再有其他进程也欲进入自己的临界区，此时由于对 mutex 执行 wait 操作定会失败，
管程机制--一种新的进程同步工具
虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进
程都必须自备同步操作 wait(S)和 signal(S)。这就使大量的同步操作分散在各个进程中。这
不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，
在解决上述问题的过程中，便产生了一种新的进程同步工具——管程(Monitors)。
管程和进程不同，主要体现在以下几个方面：
(1) 虽然二者都定义了数据结构，但进程定义的是私有数据结构 PCB，管程定义的是公
共数据结构，如消息队列等；
(2) 二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关的操作，而管
程主要是进行同步操作和初始化操作；
(3) 设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使
用问题；
(4) 进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一
样被调用，因而管程为被动工作方式，进程则为主动工作方式；
(5) 进程之间能并发执行，而管程则不能与其调用者并发；
(6) 进程具有动态性，由“创建”而诞生，由“撤销”而消亡，而管程则是操作系统中
的一个资源管理模块，供进程调用。
管程好复杂。之后再看，理解。
经典进程的同步问题。
生产者-消费者问题、读者-写者问题、哲学家进餐问题
生产者-消费者问题
1．利用记录型信号量解决生产者—消费者问题
假定在生产者和消费者之间的公用缓冲池中，具有 n 个缓冲区，这时可利用互斥信号
量 mutex 实现诸进程对缓冲池的互斥使用。利用信号量 empty 和 full 分别表示缓冲池中空缓
冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者
便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产
者—消费者问题可描述如下:
Var mutex，empty，full: semaphore:=1,n,0；
buffer:array[0，…，n - 1] of item；
in，out: integer:=0，0；
begin
parbegin
proceducer: begin
repeat
producer an item nextp；
wait(empty)；
wait(mutex)；
buffer(in):=nextp；
in:=(in+1) mod n；
signal(mutex)；
signal(full)；
until false；
end
consumer: begin
repeat
wait(full)；
wait(mutex)；
nextc:=buffer(out)；
out:=(out+1) mod n；
signal(mutex)；
signal(empty)；
consumer the item in nextc；
until false；
end
parend
end
在生产者—消费者问题中应注意：首先，在每个程序中用于实现互斥的 wait(mutex)和
signal(mutex)必须成对地出现；其次，对资源信号量 empty 和 full 的 wait 和 signal 操作，同
样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而
signal(empty)则在打印进程中，计算进程若因执行 wait(empty)而阻塞，则以后将由打印进程
将它唤醒；最后，在每个程序中的多个 wait 操作顺序不能颠倒，应先执行对资源信号量的
wait 操作，然后再执行对互斥信号量的 wait 操作，否则可能引起进程死锁。
利用管程解决生产者—消费者问题
在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命
名为 ProclucerConsumer，或简称为 PC。其中包括两个过程：
(1) put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变
量 count 来表示在缓冲池中已有的产品数目，当 count≥n 时，表示缓冲池已满，生产者须
等待。
(2) get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当 count≤0 时，表示
缓冲池中已无可取用的产品，消费者应等待。
哲学家进餐问题
由 Dijkstra 提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同
步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌
上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进
行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。
进餐完毕，放下筷子继续思考。
1．利用记录型信号量解决哲学家进餐问题
经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。
为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号
量数组。其描述如下：
Var chopstick: array[0，…，4] of semaphore；
所有信号量均被初始化为 1，第 i 位哲学家的活动可描述为：
repeat
wait(chopstick[i])；
wait(chopstick[(i+1)mod 5])；
eat；
signal(chopstick[i])；
signal(chopstick[(i+1)mod 5])；
think；
until false；
在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行 wait(chopstick[i])；
成功后，再去拿他右边的筷子，即执行 wait(chopstick[(i+1)mod 5])；又成功后便可进餐。进
餐完毕，又先放下他左边的筷子，然后再放右边的筷子。虽然，上述解法可保证不会有两
个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边
的筷子时，就会使五个信号量 chopstick 均为 0； 当他们再试图去拿右边的筷子时，都将因
无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：
(1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够
进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则
相反。按此规定，将是 1、2 号哲学家竞争 1 号筷子；3、4 号哲学家竞争 3 号筷子。即五位
哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获
得两只筷子而进餐。
读者—写者问题
一个数据文件或记录，可被多个进程共享，我们把只要求读该文件的进程称为“Reader
进程”，其他进程则称为“Writer 进程”。允许多个进程同时读一个共享对象，因为读操作不
会使数据文件混乱。但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共
享对象，因为这种访问将会引起混乱。所谓“读者—写者问题(Reader-Writer Problem)”是
指保证一个 Writer 进程必须与其他进程互斥地访问共享对象的同步问题。读者—写者问题
常被用来测试新同步原语。
进程通信：
进程通信，是指进程之间的信息交换，其
所交换的信息量少者是一个状态或数值，
多者则是成千上万个字节。进程之间的互斥和同步，
由于其所交换的信息量少而被归结为低级通信。
在进程互斥中，进程通过只修改信号量
来向其他进程表明临界资源是否可用。
在生产者-消费者问题中，
生产者通过缓冲池将所生产的产品传送给消费者。
应当指出，信号量机制作为同步工具是卓有成效的。
但是作为通信工具，不够理想。
主要表现在下面两点：
1.效率低：生产者每次只能向缓冲池投放一个产品；
消费者每次只能从缓冲区中取得一个消息。
2.通信对用户不透明。
进程通信的类型：
目前，高级通信机制可归结为三大类：
共享存储器系统、
消息传递系统、
管道通信系统。
1．共享存储器系统
在共享存储器系统(Shared-Memory System)中，相互通信的进程共享某些数据结构或共
享存储区，进程之间能够通过这些空间进行通信。据此，又可把它们分成以下两种类型：
(1) 基于共享数据结构的通信方式。在这种通信方式中，要求诸进程公用某些数据结构，
借以实现诸进程间的信息交换。如在生产者—消费者问题中，就是用有界缓冲区这种数据
结构来实现通信的。这里，公用数据结构的设置及对进程间同步的处理，都是程序员的职
责。这无疑增加了程序员的负担，而操作系统却只须提供共享存储器。因此，这种通信方
式是低效的，只适于传递相对少量的数据。
(2) 基于共享存储区的通信方式。为了传输大量数据，在存储器中划出了一块共享存储
区，诸进程可通过对共享存储区中数据的读或写来实现通信。这种通信方式属于高级通信。
进程在通信前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字；若
系统已经给其他进程分配了这样的分区，则将该分区的描述符返回给申请者，继之，由申
请者把获得的共享存储分区连接到本进程上；此后，便可像读、写普通存储器一样地读、
写该公用存储分区。
2．消息传递系统
消息传递系统(Message passing system)是当前应用最为广泛的一种进程间的通信机制。
在该机制中，进程间的数据交换是以格式化的消息(message)为单位的；在计算机网络中，
又把 message 称为报文。程序员直接利用操作系统提供的一组通信命令(原语)，不仅能实现
大量数据的传递，而且还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大大
减化了通信程序编制的复杂性，因而获得了广泛的应用。
特别值得一提的是，在当今最为流行的微内核操作系统中，微内核与服务器之间的通
信，无一例外地都采用了消息传递机制。又由于它能很好地支持多处理机系统、分布式系
统和计算机网络，因此它也成为这些领域最主要的通信工具。消息传递系统的通信方式属
于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。
3．管道通信
所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享
文件，又名 pipe 文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将
大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。
由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于
UNIX 系统，由于它能有效地传送大量数据，因而又被引入到许多其它的操作系统中。
为了协调双方的通信，管道机制必须提供以下三方面的协调能力：
(1) 互斥，即当一个进程正在对 pipe 执行读/写操作时，其它(另一)进程必须等待。
(2) 同步，指当写(输入)进程把一定数量(如 4 KB)的数据写入 pipe，便去睡眠等待，直
到读(输出)进程取走数据后，再把它唤醒。当读进程读一空 pipe 时，也应睡眠等待，直至写
进程将数据写入管道后，才将之唤醒。
(3) 确定对方是否存在，只有确定了对方已存在时，才能进行通信。
消息传递通信的实现方法：
在进程之间通信时，源进程可以直接或间接地将消息传送给目标进程，由此可将进程
通信分为直接通信和间接通信两种通信方式。
1．直接通信方式
这是指发送进程利用 OS 所提供的发送命令，直接把消息发送给目标进程。此时，要求
发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令
(原语)：
Send(Receiver，message)； 发送一个消息给接收进程；
Receive(Sender，message)； 接收 Sender 发来的消息；
例如，原语 Send(P 2 ，m 1 )表示将消息 m 1 发送给接收进程 P 2 ；而原语 Receive(P 1 ，m 1 )
则表示接收由 P 1 发来的消息 m 1 。
在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。
例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对
于这样的应用，在接收进程接收消息的原语中，表示源进程的参数，也是完成通信后的返
回值，接收原语可表示为：
Receive (id，message)；
我们还可以利用直接通信原语来解决生产者—消费者问题。当生产者生产出一个产品
(消息)后，便用 Send 原语将消息发送给消费者进程；而消费者进程则利用 Receive 原语来得
到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。
生产者—消费者的通信过程可分别描述如下：
repeat
?
produce an item in nextp；
?
send(consumer，nextp)；
until false；
repeat
receive(producer，nextc)；
?
consume the item in nextc；
until false；
2．间接通信方式
间接通信方式指进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存
发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通
常把这种中间实体称为信箱。消息在信箱中可以安全地保存，只允许核准的目标用户随时
读取。因此，利用信箱通信方式，既可实现实时通信，又可实现非实时通信。
系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。
(1) 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给
出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱，还应给出共享者的名字。当进
程不再需要读信箱时，可用信箱撤消原语将之撤消。
(2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利
用系统提供的下述通信原语进行通信：
Send(mailbox，message)； 将一个消息发送到指定信箱；
Receive(mailbox，message)； 从指定信箱中接收一个消息；
信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把
信箱分为以下三类。
1) 私用信箱
用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信
箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用
单向通信链路的信箱来实现。当拥有该信箱的进程结束时，信箱也随之消失。
2) 公用信箱
它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送
到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路
的信箱来实现。通常，公用信箱在系统运行期间始终存在。
3) 共享信箱
它由某进程创建，在创建时或创建后指明它是可共享的，同时须指出共享进程(用户)
的名字。信箱的拥有者和共享者都有权从信箱中取走发送给自己的消息。
在利用信箱通信时，在发送进程和接收进程之间存在以下四种关系：
(1) 一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者
之间的交互不受其他进程的干扰。
(2) 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服
务器交互(client/server interaction)。
(3) 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方
式向接收者(多个)发送消息。
(4) 多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从
信箱中取走属于自己的消息。
消息传递系统实现中的若干问题
消息缓冲队列通信机制
在这种通信机制中，发送进程利用 Send 原语将消息直
接发送给接收进程；接收进程则利用 Receive 原语接收消息。
1．消息缓冲队列通信机制中的数据结构
1) 消息缓冲区
在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：
type message buffer=record
sender ；发送者进程标识符
size ； 消息长度
text ； 消息正文
next ； 指向下一个消息缓冲区的指针
end
2) PCB 中有关通信的数据项
在操作系统中采用了消息缓冲队列通信机制时，除了需要为进程设置消息缓冲队列外，
还应在进程的 PCB 中增加消息队列队首指针，用于对消息队列进行操作，以及用于实现同
步的互斥信号量 mutex 和资源信号量 sm。在 PCB 中应增加的数据项可描述如下：
type processcontrol block=record
?
mq ； 消息队列队首指针
mutex ； 消息队列互斥信号量
sm ； 消息队列资源信号量
?
end
线程：
如果说，在操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源
利用率和系统吞吐量，那么，在操作系统中再引入线程，则是为了减少程序在并发执行时
所付出的时空开销，使 OS 具有更好的并发性。
由于进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之
付出较大的时空开销。正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的
频率也不宜过高，这也就限制了并发程度的进一步提高。
如何能使多个程序更好地并发执行同时又尽量减少系统的开销？
若能将进程的上述两个
属性分开，由操作系统分开处理，亦即对于作为调度和分派的基本单位，不同时作为拥有
资源的单位，以做到“轻装上阵”；而对于拥有资源的基本单位，又不对之进行频繁的切换。
正是在这种思想的指导下，形成了线程的概念。
比较进程和线程：
从调度性、并发性、系统开销和拥有资源等方面对线程和进程进行比较
1) 调度
在传统的操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进
程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源
拥有的基本单位，把传统进程的两个属性分开，使线程基本上不拥有资源，这样线程便能
轻装前进，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程
的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
2) 并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线
程之间亦可并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源
的利用率和系统的吞吐量。例如，在一个未引入线程的单 CPU 操作系统中，若仅设置一个
文件服务进程，当该进程由于某种原因而被阻塞时，便没有其它的文件服务进程来提供服
务。在引入线程的操作系统中，则可以在一个文件服务进程中设置多个服务线程。当第一
个线程等待时，文件服务进程中的第二个线程可以继续运行，以提供文件服务；当第二个
线程阻塞时，则可由第三个继续执行，提供服务。显然，这样的方法可以显著地提高文件
服务的质量和系统的吞吐量。
3) 拥有资源
不论是传统的操作系统，还是引入了线程的操作系统，进程都可以拥有资源，是系统
中拥有资源的一个基本单位。一般而言，线程自己不拥有系统资源(也有一点必不可少的资
源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，
如已打开的文件、I/O 设备等，可以供该进程中的所有线程所共享。
4) 系统开销
在创建或撤消进程时，系统都要为之创建和回收进程控制块，分配或回收资源，如内
存空间和 I/O 设备等，操作系统所付出的开销明显大于线程创建或撤消时的开销。类似地，
在进程切换时，涉及到当前进程 CPU 环境的保存及新被调度运行进程的 CPU 环境的设置，
而线程的切换则仅需保存和设置少量寄存器内容，不涉及存储器管理方面的操作，所以就
切换代价而言，进程也是远高于线程的。此外，由于一个进程中的多个线程具有相同的地
址空间，在同步和通信的实现方面线程也比进程容易。在一些操作系统中，线程的切换、
同步和通信都无须操作系统内核的干预。
线程的属性
在多线程 OS 中，通常是在一个进程中包括多个线程，每个线程都是作为利用 CPU 的
基本单位，是花费最小开销的实体。线程具有下述属性。
(1) 轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的、 能保
证其独立运行的资源，比如，在每个线程中都应具有一个用于控制线程运行的线程控制块
TCB，用于指示被执行指令序列的程序计数器，保留局部变量、少数状态参数和返回地址
等的一组寄存器和堆栈。
(2) 独立调度和分派的基本单位。在多线程 OS 中，线程是能独立运行的基本单位，因
而也是独立调度和分派的基本单位。由于线程很“轻”，故线程的切换非常迅速且开销小。
(3) 可并发执行。在一个进程中的多个线程之间可以并发执行，甚至允许在一个进程中
的所有线程都能并发执行；同样，不同进程中的线程也能并发执行。
(4) 共享进程资源。在同一进程中的各个线程都可以共享该进程所拥有的资源，这首先
表现在所有线程都具有相同的地址空间(进程的地址空间)。这意味着线程可以访问该地址空
间中的每一个虚地址；此外，还可以访问进程所拥有的已打开文件、定时器、信号量机构
等。
线程的状态
(1) 状态参数。在 OS 中的每一个线程都可以利用线程标识符和一组状态参数进行描述。
状态参数通常有这样几项：① 寄存器状态，它包括程序计数器 PC 和堆栈指针中的内容；
② 堆栈，在堆栈中通常保存有局部变量和返回地址；③ 线程运行状态，用于描述线程正
处于何种运行状态；④ 优先级，描述线程执行的优先程度；⑤ 线程专有存储器，用于保
存线程自己的局部变量拷贝；⑥ 信号屏蔽，即对某些信号加以屏蔽。
(2) 线程运行状态。如同传统的进程一样，在各线程之间也存在着共享资源和相互合作
的制约关系，致使线程在运行时也具有间断性。相应地，线程在运行时也具有下述三种基
本状态: ① 执行状态，表示线程正获得处理机而运行；② 就绪状态，指线程已具备了各种
执行条件，一旦获得 CPU 便可执行的状态；③ 阻塞状态，指线程在执行中因某事件而受
阻，处于暂停执行时的状态。
线程的创建和终止
在多线程 OS 环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称
为“初始化线程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线
程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大
小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后
使用。
如同进程一样，线程也是具有生命期的。终止线程的方式有两种：一种是在线程完成
了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程
强行终止。但有些线程(主要是系统线程)，在它们一旦被建立起来之后，便一直运行下去而
不再被终止。在大多数的 OS 中，线程被中止后并不立即释放它所占有的资源，只有当进程
中的其它线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其它线
程利用。
虽已被终止但尚未释放资源的线程，仍可以被需要它的线程所调用，以使被终止线程
重新恢复运行。为此，调用者线程须调用一条被称为“等待线程终止”的连接命令，来与
该线程进行连接。如果在一个调用者线程调用“等待线程终止”的连接命令试图与指定线
程相连接时，若指定线程尚未被终止，则调用连接命令的线程将会阻塞，直至指定线程被
终止后才能实现它与调用者线程的连接并继续执行；若指定线程已被终止，则调用者线程
不会被阻塞而是继续执行。
线程间的同步和通信
为了支持不同频率的交互操作和不同程度的并行性，在多线程 OS 中通常提供多
种同步机制，如互斥锁、条件变量、计数信号量以及多读、单写锁等。
1．互斥锁(mutex)
互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。由于操作互斥锁
的时间和空间开销都较低，因而较适合于高频度使用的关键共享数据和程序段。互斥锁可
以有两种状态，即开锁(unlock)和关锁(lock)状态。相应地，可用两条命令(函数)对互斥锁进
行操作。其中的关锁 lock 操作用于将 mutex 关上，开锁操作 unlock 则用于打开 mutex。
当一个线程需要读/写一个共享数据段时，线程首先应为该数据段所设置的 mutex 执行
关锁命令。命令首先判别 mutex 的状态，如果它已处于关锁状态，则试图访问该数据段的
线程将被阻塞；而如果 mutex 是处于开锁状态，则将 mutex 关上后便去读/写该数据段。在
线程完成对数据的读/写后，必须再发出开锁命令将 mutex 打开，同时还须将阻塞在该互斥
锁上的一个线程唤醒，其它的线程仍被阻塞在等待 mutex 打开的队列上。
另外，为了减少线程被阻塞的机会，在有的系统中还提供了一种用于 mutex 上的操作
命令 Trylock。当一个线程在利用 Trylock 命令去访问 mutex 时，若 mutex 处于开锁状态，
Trylock 将返回一个指示成功的状态码；反之，若 mutex 处于关锁状态，则 Trylock 并不会
阻塞该线程，而只是返回一个指示操作失败的状态码。
2．条件变量
在许多情况下，只利用 mutex 来实现互斥访问可能会引起死锁，我们通过一个例子来
说明这一点。有一个线程在对 mutex 1 执行关锁操作成功后，便进入一临界区 C，若在临界
区内该线程又须访问某个临界资源 R，同样也为 R 设置另一互斥锁 mutex 2。假如资源 R 此
时正处于忙碌状态，线程在对 mutex 2 执行关锁操作后必将被阻塞，这样将使 mutex 1 一直
保持关锁状态；如果保持了资源 R 的线程也要求进入临界区 C，但由于 mutex 1 一直保持关
锁状态而无法进入临界区，这样便形成了死锁。为了解决这个问题便引入了条件变量。
每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着
一个条件变量。单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条
件变量则用于线程的长期等待，直至所等待的资源成为可用的资源。
现在，我们看看如何利用互斥锁和条件变量来实现对资源 R 的访问。线程首先对 mutex
执行关锁操作，若成功便进入临界区，然后查找用于描述该资源状态的数据结构，以了解
资源的情况。只要发现所需资源 R 正处于忙碌状态，线程便转为等待状态，并对 mutex 执
行开锁操作后，等待该资源被释放；若资源处于空闲状态，表明线程可以使用该资源，于
是将该资源设置为忙碌状态，再对 mutex 执行开锁操作。下面给出了对上述资源的申请(左
半部分)和释放(右半部分)操作的描述。
Lock mutex Lock mutex
check data structures； mark resource as free；
while(resource busy)； unlock mutex；
wait(condition variable)； wakeup(condition variable)；
mark resource as busy；
unlock mutex；
原来占有资源 R 的线程在使用完该资源后，便按照右半部分的描述释放该资源，其中
的 wakeup(condition variable)表示去唤醒在指定条件变量上等待的一个或多个线程。在大多
数情况下，由于所释放的是临界资源，此时所唤醒的只能是在条件变量上等待的某一个线
程，其它线程仍继续在该队列上等待。但如果线程所释放的是一个数据文件，该文件允许
多个线程同时对它执行读操作。在这种情况下，当一个写线程完成写操作并释放该文件后，
如果此时在该条件变量上还有多个读线程在等待，则该线程可以唤醒所有的等待线程。
信号量机制
前面所介绍的用于实现进程同步的最常用工具——信号量机制，也可用于多线程 OS
中，实现诸线程或进程之间的同步。为了提高效率，可为线程和进程分别设置相应的信
号量。
3.处理机调度与死锁
在多道程序环境下，主存中有多个进程，
其数目往往多于处理机数目。
这就要求系统能按某种算法，
动态地把处理机分配给就绪队列中的一个进程，
使之执行。
分配处理机的任务是由处理机调度程序完成的。
1.处理机调度的层次
在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。
对于批量型作业而言，通常需要经历作业调度(又称高级调度或长程调度)和进程调度(又称
低级调度或短程调度)两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程
调度即可获得处理机。在较完善的操作系统中，为提高内存的利用率，往往还设置了中级
调度(又称中程调度)。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。对
于一个批处理型作业，从进入系统并驻留在外存的后备队列开始，直至作业运行完毕，可
能要经历上述的三级调度。本节主要是对处理机调度层次做较详细的介绍。
作业调度
作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源
需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建
进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也
把作业调度称为接纳调度(Admission Scheduling)。
低级调度的功能
低级调度用于决定就绪队列中的哪个进程(或内核级线程，为叙述方便，以后只写进程)
应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。
低级调度的主要功能如下：
(1) 保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机
的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制
块(PCB)中的相应单元。
(2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪
队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。
(3) 把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中
的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器
相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。
进程调度中的三个基本机制
为了实现进程调度，应具有如下三个基本机制：
(1) 排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方
式排成一个或多个队列，以便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出该
进程，然后进行上下文切换，将处理机分配给它。
(3) 上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。在第一对
上下文切换时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派
程序运行；在第二对上下文切换时，将移出分派程序，而把新选进程的 CPU 现场信息装入
到处理机的各个相应寄存器中。
进程调度方式
进程调度可采用下述两种调度方式。
1) 非抢占方式(Nonpreemptive Mode)
在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都
一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许
其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件
而被阻塞时，才再把处理机分配给其他进程。
在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个：
(1) 正在执行的进程执行完毕，或因发生某事件而不能再继续执行；
(2) 执行中的进程因提出 I/O 请求而暂停执行；
(3) 在进程通信或同步过程中执行了某种原语操作，如 P 操作(wait 操作)、Block 原语、
Wakeup 原语等。
这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但
它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求
比较严格的实时系统中，不宜采用这种调度方式。
2) 抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该
进程的处理机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用
处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的
实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。抢占调度方式是基
于一定原则的，主要有如下几条：
(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到
达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机
分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进
程的处理机。
(2) 短作业(进程)优先原则。当新到达的作业(进程)比正在执行的作业(进程)明显的短
时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行；
或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。
(3) 时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执
行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处
理系统。
进程调度的运行频率最高，
为避免进程调度占用太多的CPU时间，
进程调度算法不宜太复杂。
仅有进程调度的调度队列模型
在分时系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。对
于命令，是由 OS 为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个
无序链表，至于到底采用其中哪种形式，则与 OS 类型和所采用的调度算法有关。例如，在
分时系统中，常把就绪进程组织成 FIFO 队列形式。每当 OS 创建一个新进程时，便将它挂
在就绪队列的末尾，然后按时间片轮转方式运行。
每个进程在执行时都可能出现以下三种情况：
(1) 任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态；
(2) 任务在本次分得的时间片内尚未完成，OS 便将该任务再放入就绪队列的末尾；
(3) 在执行期间，进程因为某事件而被阻塞后，被 OS 放入阻塞队列。
具有高级和低级调度的调度队列模型
在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一定的作业调度
算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然
后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。图 3-2 示
出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。
(1) 就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，相应地，
最常用的就绪队列形式是优先权队列。进程在进入优先级队列时，根据其优先权的高低，
被插入具有相应优先权的位置上，这样，调度程序总是把处理机分配给就绪队列中的队首
进程。在最高优先权优先的调度算法中，也可采用无序链表方式，即每次把新到的进程挂
在链尾，而调度程序每次调度时，是依次比较该链中各进程的优先权，从中找出优先权最
高的进程，将之从链中摘下，并把处理机分配给它。显然，无序链表方式与优先权队列相
比，这种方式的调度效率较低。
2) 设置多个阻塞队列。对于小型系统，可以只设置一个阻塞队列；但当系统较大时，
若仍只有一个阻塞队列，其长度必然会很长，队列中的进程数可以达到数百个，这将严重
影响对阻塞队列操作的效率。故在大、中型系统中通常都设置了若干个阻塞队列，每个队
列对应于某一种进程阻塞事件。
调度算法
在 OS 中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所
规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，例如，在
批处理系统中，为了照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时
系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。目前存在的多种调
度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可
用于作业调度，也可用于进程调度。
先来先服务和短作业(进程)优先调度算法
1．先来先服务调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也
可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一
个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放
入就绪队列。在进程调度中采用 FCFS 算法时，则每次调度是从就绪队列中选择一个最先进
入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件
而阻塞后才放弃处理机。
FCFS 算法比较有利于长作业(进程)，而不利于短作业(进程)。下表列出了 A、B、C、
D 四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，
并计算出各自的周转时间和带权周转时间。
短作业(进程)优先调度算法
短作业(进程)优先调度算法 SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以
分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若
干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从
就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直
执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
基于时间片的轮转调度算法
如前所述，在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮
转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法；进入 20 世纪 90
年代后，广泛采用多级反馈队列调度算法。
1．时间片轮转法
1) 基本原理
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，
每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几 ms 到
几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号
来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中
新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一
给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应
所有用户的请求。
2) 时间片大小的确定
在时间片轮转算法中，时间片的大小对系统性能有很大的影响，如选择很小的时间片
将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而
增加系统的开销；反之，如选择太长的时间片，使得每个进程都能在一个时间片内完成，
时间片轮转算法便退化为 FCFS 算法，无法满***互式用户的需求。一个较为可取的大小是，
时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。
实时调度
采用抢占式调度机制
在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达
时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时
任务对截止时间的要求。但这种调度机制比较复杂。
对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采
用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调
度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地
将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的
任务。
产生死锁的原因和必要条件
产生死锁的原因可归结为以下两点：
1.竞争资源。
当系统中供多个进程共享的资源
如打印机、公用队列等，
其数目不足以满足诸进程的需要时，
会引起诸进程对资源的竞争而产生死锁。
2.进程间推进顺序非法。
进程在运行过程中，
请求和释放资源的顺序不当，
也同样会导致产生进程死锁。
1．竞争资源引起进程死锁
1) 可剥夺和非剥夺性资源
可把系统中的资源分成两类，一类是可剥夺性资源，是指某进程在获得这类资源后，
该资源可以再被其他进程或系统剥夺。例如，优先权高的进程可以剥夺优先权低的进程的
处理机。又如，内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，
此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上。可见，CPU
和主存均属于可剥夺性资源。另一类资源是不可剥夺性资源，当系统把这类资源分配给某
进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
2) 竞争非剥夺性资源
在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使
进程在运行过程中，因争夺这些资源而陷入僵局。例如，系统中只有一台打印机 R 1 和一台
磁带机 R 2 ，可供进程 P 1 和 P 2 共享。假定 P 1 已占用了打印机 R 1 ，P 2 已占用了磁带机 R 2 。此
时，若 P 2 继续要求打印机，P 2 将阻塞；P 1 若又要求磁带机，P 1 也将阻塞。于是，在 P 1 与
P 2 之间便形成了僵局，两个进程都在等待对方释
放出自己所需的资源。但它们又都因不能继续获
得自己所需的资源而不能继续推进，从而也不能
释放出自己已占有的资源，以致进入死锁状态。
为便于说明，我们用方块代表资源，用圆圈代表
进程，见图 3-13 所示。当箭头从进程指向资源
时，表示进程请求资源；当箭头从资源指向进程
时，表示该资源已被分配给该进程。从中可以看
出，这时在 P 1 、P 2 及 R 1 和 R 2 之间已经形成了一
个环路，说明已进入死锁状态。
2) 进程推进顺序非法
若并发进程 P 1 和 P 2 按曲线④所示的顺序推进，它们将进入不安全区 D 内。此时 P 1 保
持了资源 R 1 ，P 2 保持了资源 R 2 ，系统处于不安全状态。因为这时两进程再向前推进，便可
能发生死锁。例如，当 P 1 运行到 P 1 ：Request(R 2 )时，将因 R 2 已被 P 2 占用而阻塞；当 P 2 运
行到 P 2 ：Request(R 1 )时，也将因 R 1 已被 P 1 占用而阻塞，于是发生了进程死锁。
产生死锁的必要条件
虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。综上所
述不难看出，死锁的发生必须具备下列四个必要条件。
(1) 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由
一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源
的进程用毕释放。
(2) 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而
该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
(3) 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完
时由自己释放。
(4) 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集
合{P 0 ，P 1 ，P 2 ，…，P n }中的 P 0 正在等待一个 P 1 占用的资源； P 1 正在等待 P 2 占用的资源，……，
P n 正在等待已被 P 0 占用的资源。
处理死锁的基本方法
为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。在系统
中已经出现死锁后，则应及时检测到死锁的发生，并采取适当措施来解除死锁。目前，处
理死锁的方法可归结为以下四种：
(1) 预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制
条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁
是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格，因而可能
会导致系统资源利用率和系统吞吐量降低。
(2) 避免死锁。该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施
去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统
进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件，便可获得
较高的资源利用率及系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中常用
此方法来避免发生死锁。
(3) 检测死锁。这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进
入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及
时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，采取适当措施，
从系统中将已发生的死锁清除掉。
(4) 解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须
将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资
源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁
的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。
利用银行家算法避免死锁
最有代表性的避免死锁的算法，是 Dijkstra 的银行家算法。这是由于该算法能用于银行
系统现金贷款的发放而得名的。为实现银行家算法，系统中必须设置若干数据结构。
详见P120
死锁的检测与解除
(1) 保存有关资源的请求和分配信息；
(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。
死锁定理
我们可以利用把资源分配图加以简化的方法(图 3-21)，来检测当系统处于 S 状态时是否
为死锁状态。简化方法如下：
(1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点 P i 。在顺利的情况下，P i
可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去
p i 所求的请求边和分配边，使之成为孤立的结点。
(2) p 1 释放资源后，便可使 p 2 获得资源而继续运行，直至 p 2 完成后又释放出它所占有
的全部资源，形成图(c)所示的情况。
(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结
点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完
全简化的。
对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化
顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不
可简化图。同样可以证明：S 为死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不
可完全简化的。该充分条件被称为死锁定理。
死锁检测中的数据结构
死锁检测中的数据结构类似于银行家算法中的数据结构：
(1) 可利用资源向量 Available，它表示了 m 类资源中每一类资源的可用数目。
(2) 把不占用资源的进程(向量 Allocation i :=0)记入 L 表中，即 L i ∪L。
(3) 从进程集合中找到一个 Request i ≤Work 的进程，做如下处理：
① 将其资源分配图简化，释放出资源，增加工作向量 Work:=Work + Allocation i 。
② 将它记入 L 表中。
(4) 若不能把所有进程都记入 L 表中，便表明系统状态 S 的资源分配图是不可完全简化
的。因此，该系统状态将发生死锁。
死锁的解除
当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两
种方法是：
(1) 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
(2) 撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的
方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。
在出现死锁时，可采用各种策略来撤消进程。例如，为解除死锁状态所需撤消的进
程数目最小；或者，撤消进程所付出的代价最小等。一种付出最小代价的方法如图 3-22
所示。
4.存储器管理
多级存储器结构：
对于通用计算机而言，存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，
最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓
存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层
主存储器
主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序
和数据，也称可执行存储器，其容量对于当前的微机系统和大中型机，可能一般为数十 MB
到数 GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十 KB 到几 MB。CPU
的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到
寄存器中，或者从寄存器存入到主存储器。CPU 与外围设备交换的信息一般也依托于主存
储器地址空间。由于主存储器的访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，
在计算机系统中引入了寄存器和高速缓存。
寄存器
寄存器访问速度最快，完全能与 CPU 协调工作，但价格却十分昂贵，因此容量不可能
做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大
中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器
用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速
度等。
高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内
存约小两到三个数量级左右，从几十 KB 到几 MB，访问速度快于主存储器。
根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，
程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访
问主存储器的次数，可大幅度提高程序执行速度。通常，进程的程序和数据是存放在主存
储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。当 CPU 访问一组特定信
息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主
存，否则，再从主存中读出信息。如大多数计算机有指令高速缓存，用来暂存下一条欲执
行的指令，如果没有指令高速缓存，CPU 将会空等若干个周期，直到下一条指令从主存中
取出。由于高速缓存的速度越高价格也越贵，故有的计算机系统中设置了两级或多级高速
缓存。紧靠内存的一级高速缓存的速度最高，而容量最小，二级高速缓存的容量稍大，速
度也稍低。
程序的装入和链接
在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，
便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通
常都要经过以下几个步骤：首先是要编译，由编译程序(Compiler)将用户源代码编译成若干
个目标模块(Object Module)；其次是链接，由链接程序(Linker)将编译后形成的一组目标模
块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后
是装入，由装入程序(Loader)将装入模块装入内存。
在将一个装入模块装入内存时，可以有绝对装入方式、可重定位
装入方式和动态运行时装入方式，
1．绝对装入方式(Absolute Loading Mode)
在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址
的目标代码。例如，事先已知用户程序(进程)驻留在从 R 处开始的位置，则编译程序所产生
的目标模块(即装入模块)便从 R 处开始向上扩展。绝对装入程序按照装入模块中的地址，将
程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完
全相同，故不须对程序和数据的地址进行修改。
程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在
由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数
据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，
然后在编译或汇编时，再将这些符号地址转换为绝对地址。
2．可重定位装入方式(Relocation Loading Mode)
绝对装入方式只能将目标模块装入到内存中事先指定的位置。在多道程序环境下，编
译程序不可能预知所编译的目标模块应放在内存的何处，因此，绝对装入方式只适用于单
道程序环境。在多道程序环境下，所得到的目标模块的起始地址通常是从 0 开始的，程序
中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的
当前情况，将装入模块装入到内存的适当位置。
值得注意的是，在采用可重定位装入程序将
装入模块装入内存后，会使装入模块中的所有逻
辑地址与实际装入内存的物理地址不同，图 4-3
示出了这一情况。例如，在用户程序的 1000 号
单元处有一条指令 LOAD 1，2500，该指令的功
能是将 2500 单元中的整数 365 取至寄存器 1。
但若将该用户程序装入到内存的 10000～15000
号单元而不进行地址变换，则在执行 11000 号单
元中的指令时，它将仍从 2500 号单元中把数据
取至寄存器 1 而导致数据错误。由图 4-3 可见，
正确的方法应该是将取数指令中的地址 2500 修
改成 12500，即把指令中的相对地址 2500 与本程序在内存中的起始地址 10000 相加，才得
到正确的物理地址 12500。除了数据地址应修改外，指令地址也须做同样的修改，即将指令
的相对地址 1000 与起始地址 10000 相加，得到绝对地址 11000。通常是把在装入时对目标
程序中指令和数据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，
以后不再改变，故称为静态重定位。
3．动态运行时装入方式(Dynamic Run-time Loading)
可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环
境；但这种方式并不允许程序运行时在内存中移动位置。因为，程序在内存中的移动，意
味着它的物理位置发生了变化，这时必须对程序和数据的地址(是绝对地址)进行修改后方能
运行。然而，实际情况是，在运行过程中它在内存中的位置可能经常要改变，此时就应采
用动态运行时装入的方式。
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址
转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存
后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个
重定位寄存器的支持，
程序的链接
源程序经过编译后，可得到一组目标模块，再利用链接程序将这组目标模块链接，形
成装入模块。根据链接时间的不同，可把链接分成如下三种：
(1) 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完
整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。
(2) 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存
时，采用边装入边链接的链接方式。
(3) 运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模
块时，才对它进行的链接。
运行时动态链接(Run-time Dynamic Linking)
在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先
无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块都全部装入内存，并
在装入时全部链接在一起。显然这是低效的，因为往往会有些目标模块根本就不运行。比
较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，
则显然就不会用到该模块。
近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这
种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，
当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链
接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到
装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
在当前的操作系统中，普遍采用的是下面将要讲述的基于分页和分段
机制的虚拟内存机制，该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系
统仍不失为一种有效的内存分配和释放的方法，得到了大量的应用。
哈希算法
在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，
对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，
需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链
表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应的空闲
分区链表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，
建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一
个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希
表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
可重定位分区分配
1．动态重定位的引入
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统
中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻
接，也无法把该程序装入内存。例如，图 4-9(a)中示出了在内存中现有四个互不邻接的小分
区，它们的容量分别为 10 KB、30 KB、14 KB 和 26 KB，其总容量是 80 KB。但如果现在
有一作业到达，要求获得 40 KB 的内存空间，由于必须为它分配一连续空间，故此作业无
法装入。这种不能被利用的小分区称为“零头”或“碎片”。
若想把作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都
相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该
区。这种通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方
法，称为“拼接”或“紧凑”，见图 4-9(b)。由于经过紧凑后的某些用户程序在内存中的位
置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，
在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
2．动态重定位的实现
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对
地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会
影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位
寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址
是相对地址与重定位寄存器中的地址相加而形成的。图 4-10 示出了动态重定位的实现原理。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态
重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对
程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可
动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配
算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧
凑。
基本分页存储管理方式
连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的
大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接
的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。如果离散分配的
基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存
储管理方式。
在分页存储管理方式中，如果不具备页面对换功能，则称为基本的分页存储管理方式，
或称为纯分页存储管理方式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全
部装入内存后方能运行
页面与页表
1．页面
1) 页面和物理块
分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，
并为各页加以编号，从 0 开始，如第 0 页、第 1 页等。相应地，也把内存空间分成与页面
相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如 0 # 块、
1 # 块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相
邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为
“页内碎片”。
2) 页面大小
在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从
而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较
多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效
率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，
但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是 2 的幂，通常
为 512 B～8 KB。
2．地址结构
分页地址中的地址结构如下：
31 12 11 0
页号 P 位移量 W
它含有两部分：前一部分为页号 P，后一部分为位移量 W(或称为页内地址)。图中的地址长
度为 32 位，其中 0～11 位为页内地址，即每页的大小为 4 KB；12～31 位为页号，地址空
间最多允许有 1 M 页。
对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A，页
面的大小为 L，则页号 P 和页内地址 d 可按下式求得：
P = INT ú
d = [A] MOD L
其中，INT 是整除函数，MOD 是取余函数。例如，其系统的页面大小为 1 KB，设 A = 2170 B，
则由上式可以求得 P = 2，d = 122。
页表
在分页系统中，允许将进程的各个页离散地
存储在内存不同的物理块中，
但系统应能保证进程的正确运行，
即能在内存中找到每个页面所对应的物理块。
为此，系统又为每个进程建立了一张页面映像表，
简称页表。
在进程地址空间内的所有页0~n，
依次在页表中有一页表项，
其中记录了相应页在内存中对应的物理块号，
在配置了页表后，进程执行时，通过查找该表，
即可找到哦啊每页在内存中的物理块号。
可见，页表的作用是实现从页号到物理块号的地址映射。
如果要利用分页系统去实现虚拟存储器，
须增设一数据项。
地址变换机构
为了能将用户地址空间中的逻辑地址变换为
内存空间中的物理地址，在系统中必须设置
地址变换机构。
该机构的基本任务是实现从逻辑地址到物理地址的转换。
由于页内地址和物理地址是一一对应的，
例如，对于页面大小是1kb的页内地址是0~1023，
其相应的物理块内的地址也是0~1023，无须进行转换。
因此，地址变换机构的任务实际上只是将逻辑地址
中的页号，转换为内存中的物理块号。
又因为页面映射表的作用就是用于实现从页号
到物理块号的变换，
因此，地址变换任务是借助于页表来完成的。
当进程要访问某个逻辑地址中的数据时，
分页地址变换机构会自动地将有效哦地址的
分为页号和页内地址两部分，
再以页号为索引去检索页表。
查找操作有硬件执行就。
在执行检索之前，先将页号与页表长度进行比较，
如果页号大于或等于页表长度，
则表示本次所访问的地址已超越进程的地址空间。
于是，这一错误将被系统发现并产生一
地址越界中断。
若未出现越界错误，则将页表始址与页号和
页表项长度的乘积相加，
便得到该表项在页表中的位置，
于是可从中得到该页的物理块号，
将之装入物理地址寄存器中。
与此同时，
再将有效地址寄存器中的业内地址
送入物理地址寄存器的块内地址s
基本分段存储管理方式
如果说推动存储管理方式从固定分区到动态分区分配，
进而又发展到分页存储管理方式的主要动力，
是提高内存利用率，那么引入分段存储管理方式的目的，
则主要是为了满足程序员在编程和使用上多方面的要求，
其中有些要求是其他几种存储管理方式所难以满足的。
因此，这种存储管理方式已成为当今所有存储管理方式的基础。
为了方便和实现下面的要求：
1.方便编程
2.信息共享
3.信息保护
4.动态增长
在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又
无法确切地知道数据段会增长到多大。前述的其它几种存储管理方式，都难以应付这种动
态增长的情况，而分段存储管理方式却能较好地解决这一问题。
5.动态链接
动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主
程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目
标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。
分页和分段的主要区别
(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内
存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的
逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的
需要。
(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是
由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于
用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
(3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆
符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，
既需给出段名，又需给出段内地址。
段页式存储管理方式
分页和分段存储管理方式都各有其优缺点。分页系统能有效地提高内存
利用率，而分段系统则能很好地满足用户需要。如果能对两种存储管理方式“各取所长”，
则可以将两者结合成一种新的存储管理方式系统。这种新系统既具有分段系统的便于实现、
分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样很好地解决内存
的外部碎片问题，以及可为各个分段离散地分配内存等问题。把这种结合起来形成的新系
统称为“段页式系统”。
1．基本原理
段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，
再把每个段分成若干个页，并为每一个段赋予一个段名。图 4-21 示出了一个作业地址空间
的结构。该作业有三个段，页面大小为 4 KB。在段页式系统中，其地址结构由段号、段内
页号及页内地址三部分所组成
虚拟存储器
两种情况：
(1) 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，
致使该作业无法运行。
(2) 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业
装入内存让它们先运行，而将其它大量的作业留在外存上等待。
出现上述两种情况的原因，都是由于内存容量不够大。一个显而易见的解决方法，是
从物理上增加内存容量，但这往往会受到机器自身的限制，而且无疑要增加系统成本，因
此这种方法是受到一定限制的。另一种方法是从逻辑上扩充内存容量，这正是虚拟存储技
术所要解决的主要问题。
局部性原理
早在 1968 年，Denning.P 就曾指出：程序在执行时将呈现出局部性规律，即在一较短
的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区
域。他提出了下述几个论点：
(1) 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行
的。该论点也在后来的许多学者对高级程序设计语言(如 FORTRAN 语言、PASCAL 语言)
及 C 语言规律的研究中被证实。
(2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，
过程调用的深度在大多数情况下都不超过 5。这就是说，程序将会在一段时间内都局限在这
些过程的范围内运行。
(3) 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。
(4) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小
的范围内。
局限性还表现在下述两个方面：
(1) 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；
如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是
由于在程序中存在着大量的循环操作。
(2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将
被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便
是程序的顺序执行。
DMA 工作过程
我们以从磁盘读入数据为例，来说明 DMA 方式的工作流程。当 CPU 要从磁盘读入一
数据块时，便向磁盘控制器发送一条读命令。该命令被送到其中的命令寄存器(CR)中。同
时，还须发送本次要将数据读入的内存起始目标地址，该地址被送入内存地址寄存器（MAR）
中；本次要读数据的字(节)数则送入数据计数器(DC)中，还须将磁盘中的源地址直接送至
DMA 控制器的 I/O 控制逻辑上。然后，启动 DMA 控制器进行数据传送，以后，CPU 便可
去处理其它任务。此后，整个数据传送过程便由 DMA 控制器进行控制。当 DMA 控制器已
从磁盘中读入一个字(节)的数据并送入数据寄存器(DR)后，再挪用一个存储器周期，将该字
(节)传送到 MAR 所指示的内存单元中。接着便对 MAR 内容加 1，将 DC 内容减 1。若减 1
后 DC 内容不为 0，表示传送未完，便继续传送下一个字(节)；否则，由 DMA 控制器发出
中断请求。
5.
京公网安备 11010502036488号