处理机是计算机系统的核心资源。操作系统的功能之一就是处理机管理。随着计算机的迅速发展,处理机管理显得更为重要,这主要由于计算机的速度越来越快,处理机的充分利用有利于系统效率的大大提高;处理机管理是整个操作系统的重心所在,其管理的好坏直接影响到整个系统的运行效率;而且操作系统中并发活动的管理和控制是在处理机管理下实现的,处理机管理集中了操作系统中最复杂的部分,它设计的好坏关系到整个系统的成败。进程是处理机管理中最基本的、最重要的概念。进程是系统并发执行的体现。由于在多道程序系统中,众多的计算机用户都以各种各样的任务,随时随地争夺使用处理机。为了动态地看待操作系统,则以进程作为独立运行的基本单位,以进程作为分配资源的基本单位, 从进程的角度来研究操作系统。因此,处理机管理也被称为进程管理。处理机管理的功能就是组织和协调用户对处理机的争夺使用,把处理机分配给进程,对进程进行管理和控制,最大限度也发挥处理机的作用。
1.进程的概念用静态的观点看,操作系统是一组程序和表格的集合。用动态的观点看, 操作系统是进程的动态和并发执行的。而进程的概念实际上是程序这一概念发展的产物。因此,可以从分析程序的基本特征入手,引出“进程”的概念。
顺序程序是指程序中若干操作必须按照某种先后次序来执行,并且每次操作前和操作后的数据、状态之间都有一定的关系。在早期的程序设计中,程序一般都是按顺序执行的。
在多道程序系统中,程序的运行环境发生了很大的变化。主要体现在:
(1)资源共享。为了提高资源的利用率,计算机系统中的资源不再由一道程序专用, 而是由多道程序共同使用。
(2)程序的并发执行或并行执行。逻辑上讲允许多道不同用户的程序并行运行;允许一个用户程序内部完成不同操作的程序段之间并行运行;允许操作系统内部不同的程序之间并行运行。物理上讲:内存储器中保存多个程序,I/O 设备被多个程序交替地共享使用;在多处理机系统的情形下,表现为多个程序在各自的处理机上运行,执行时间是重叠的。单处理机系统时,程序的执行表现为多道程序交替地在处理机上相互空插运行。
实际上,在多道程序系统中,程序的并行执行和资源共享之间是相辅相成的。一方面, 只有允许程序并行执行,才可能存在资源共享的问题;另一方面,只有有效地实现资源共享, 才可能使得程序并行执行。
这样,可增强计算机系统的处理能力和提高机器的利用率。并发操作实际上是这样的:大多数程序段只要求操作在时间上是有序的,也就是有些操作必须在其他操作之前,这是有序的, 但其中有些操作却可以同时进行。
2.进程的状态转换
由进程运行的间断性,决定了进程至少具有以下三种状态:
(1)就绪状态。当进程已分配了除 CPU 以外的所有必要的资源后,只要能再获得处理机,便能立即执行,把这时的进程状态称为就绪状态。在一个系统中,可以有多个进程同时处于就绪状态,通常把它们排成一个队列,称为就绪队列。
(2)执行状态指进程已获得处理机,其程序正在执行。在单处理机系统中,只能有一个进程处于执行状态。
(3)阻塞状态指进程因发生某事件(如请求 I/O、申请缓冲空间等)而暂停执行时的状态,亦即进程的执行受到阻塞,故称这种暂停状态为阻塞状态,有时也称为“等待”状态, 或“睡眠”状态。通常将处于阻塞状态的进程排成一个队列,称为阻塞队列。
进程的状态随着自身的推进和外界的变化而变化。例如,就绪状态的进程被进程调度程序选中进入执行状态;执行状态的进程因等待某一事件的发生转入等待状态;等待状态的进程所等待事件来到便进入就绪状态。进程的状态可以动态地相互转换,但阻塞状态的进程不能直接进入执行状态,就绪状态的进程不能直接进入阻塞状态。在任何时刻,任何进程都处于且只能处于这其中一种状态。进程状态的变化情况如下:
(1)运行态→等待态:一个进程运行中启动了外围设备,它就变成等待外围设备传输信息的状态;进程在运行中申请资源(主存储空间及外围设备因得不到满足)时,变成等待资源状态,进程在运行中出现了故障(程序出错或主存储器读写错误等),变成等待干预状态。
(2)等待态→就绪态:外围设备工作结束后等待外围设备传输信息的进程结束等待; 等待的资源能得到满足时(另一个进程归还了资源),则等待资源者就结束等待;故障排队后让等待干预的进程结束等待,任何一个结束等待的进程必须先变成就绪状态,待分配到处理器后才能运行。
(3)运行态→就绪态:进程用完了一个使用处理器的时间后强迫该进程暂时让出处理器,当有更优先权的进程要运行时也迫使正在运行的进程让出处理器。由于自身或外界原因成为等待状态的进程让出处理器时,它的状态就变成就绪状态。
(4)就绪态→运行态:等待分配处理器的进程,系统按一种选定的策略从处于就绪状态的进程中选择一个进程,让它占用处理器,那个被选中的进程就变成了运行态。
下图所示为进程的三种基本状态及各状态之间的转换。

3.关于挂起状态
在不少系统中,进程只有上图所示的三种状态。但在另一些系统中,又增加了一些新状态,其中最重要的是挂起状态。引入挂起状态的原因有:
(1)对换的需要。为了缓和内存紧张的情况,而将内存中处于阻塞状态的进程换至外存上,使进程又处于一种有别于阻塞状态的新状态。因为即使该进程所期待的事件发生,该进程仍不具备执行条件而不能进入就绪队列,称这种状态为挂起状态。
(2)终端用户的请求。当终端用户在自己的程序运行期间,发现有可疑问题时,往往希望使自己的进程暂停下来。也就是说,使正在执行的进程暂停执行,若是就绪进程,则不接受调度以便研究其执行情况或对程序进行修改。把这种静止状态也称为挂起状态。
(3)父进程请求。父进程常希望挂起自己的子进程,以便考查和修改子进程,或者协调各子进程间的活动。
(4)负荷调节的需要。当实时系统中的工作负荷较重,有可能影响到对实时任务的控制时,可由系统把一些不重要的进程挂起,以保证系统正常运行。
(5)操作系统的需要。操作系统希望挂起某些进程,以便检查运行中资源的使用情况及进行记账。
综上所述,不难了解挂起状态具有以下三个属性。
(1)被挂起的进程,原来可能处于就绪状态,此时进程(被挂起)的状态称为挂起就绪;若被挂起的进程原来处于阻塞状态,此时的状态称为挂起阻塞。不论哪种状态,该进程都是不可能被调度而执行的。
(2)处于挂起阻塞状态的进程,其阻塞条件与挂起条件无关;当进程所期待的事件出现后,进程虽不再被阻塞,但仍不能运行,这时,应将该进程从静止阻塞状态转换为挂起就绪状态。

(3)进程可以由其自身挂起,也可由用户或操作系统等将之挂起。其目的都在于阻止
进程继续运行,被挂起的进程只能用显式方式来激活,以便从挂起状态中解脱出来。如下图 所示为具有挂起操作的进程状态的演变情况。

4.进程互斥与同步进程互斥定义为:一组并发进程中一个或多个程序段,因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说互斥是要保证临界资源在某一时刻只被一个进程访问。
进程同步定义为:把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待,使得各进程按一定的速度执行的过程称为进程同步。也就是说进程之间是异步执行的,同步即是使各进程按一定的制约顺序和速度执行。
希赛教育专家提示:简单一点来说,互斥是资源的竞争关系,而同步是进程间的协作关系。
系统中有些资源可以供多个进程同时使用,有些资源则一次仅允许一个进程使用,将一次仅允许一个进程使用的资源称为临界资源,很多物理设备如打印机、磁带机等都属于临界资源,某些软件的变量、数据、表格也不允许两个进程同时使用,所以也是临界资源。
进程在并发执行中可以共享系统中的资源。但是临界资源的访问则必须互斥进行,即各 进程对临界资源进行操作的那段程序的执行也必须是互斥的,只有这样才能保证对临界资源的互斥访问。把一个进程访问临界资源的那段程序代码称为临界区,有了临界区的概念,进 程间的互斥就可以描述为:禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。为此,必须有专门的同步机构来协调它们,协调准则如下:

(1)空闲让进。无进程处于临界区时,若有进程要求进入临界区则立即允许其进入;
(2)忙则等待。当已有进程进入其临界区时,其他试图进入各自临界区的进程必须等待,以保证诸进程互斥地进入临界区;
(3)有限等待。有若干进程要求进入临界区时,应在有限时间内使一进程进入临界区, 即它们不应相互等待而谁也不进入临界区;
(4)让权等待。对于等待进入临界区的进程必须释放其占有的 CPU。信号量可以有效地实现进程的同步和互斥。在操作系统中,信号量是一个整数。当信号量大于等于 0 时, 代表可供并发进程使用的资源实体数,当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量代表的意义和设置初值,以及建立相应的数据结构, 以便指向那些等待使用该临界区的进程。
对信号量只能施加特殊的操作:P 操作和 V 操作。P 操作和 V 操作都是不可分割的原子操作,也称为原语。因此,P 原语和 V 原语执行期间不允许中断发生。
P(sem)操作的过程是将信号量 sem 值减 l,若 sem 的值成负数,则调用 P 操作的进程暂停执行,直到另一个进程对同一信号量做 V 操作。V(sem)操作的过程是将信号量sem 值加 1,若 sem 的值小于等于 0,从相应队列(与 sem 有关的队列)中选一个进程, 唤醒它。
一般 P 操作与 V 操作的定义如下所述。
P 操作:
P(sem){
sem = sem - 1;
if(sem < 0)进程进入等待状态; else 继续进行;
}
V 操作:
V(sem){
sem = sem + 1;
if(sem ≤ 0)唤醒队列中的一个等待进程; else 继续进行;
}
为了保护共享资源(如公共变量),使它们不被多个进程同时访问,就要阻止这些进程同时执行访问这些资源(临界资源)的代码段(临界区);进程互斥不允许两个以上共享临界资源的并发进程同时进入临界区。利用 P、V 原语和信号量可以方便地解决并发进程对临界区的进程互斥问题。

设信号量 mutex 是用于互斥的信号量,初值为 1,表示没有并发进程使用该临界区。
于是各并发进程的临界区可改写成下列形式的代码段:
P(mutex);临界区V(mutex);
要用 P,V 操作实现进程同步,需要引进私用信号量。私用信号量只与制约进程和被制约进程有关,而不是与整组并发进程相关。与此相对,进程互斥使用的信号量为公用信号量。首先为各并发进程设置私用信号量,然后为私用信号量赋初值,最后利用 P,V 原语和私用信号量规定各进程的执行顺序。
经典同步问题的例子是“生产者-消费者”问题。这要求存后再取,取后再存,即有两 个制约关系,为此,需要两个信号量,表示缓冲区中的空单元数和非空单元数,记为 Bufempty 和 Buffull,它们的初值分别是 1 和 0,相应的程序段形式是:

5.前趋图
前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程,结点间的有向边表示两个结点之间存在的前趋关系。
例:在计算机中,经常采用流水线方式执行指令,每一条指令都可以分解为取指、分析和执行三步。取指操作为 Ai,分析操作为 Bi 和执行操作为 Ci(i=1,2,3)。如下图所示为三个任务各程序段并发执行的前驱图。

图中 A1 没有前趋结点,称为开始结点,它不受任何制约,可以直接执行;而 B1 与 A2 只能在 A1 执行完成之后才能开始,而 B2 必须在 B1 与 A2 完成之后才能开始;C3 没有后继结点,称为终止结点。
在前趋图中,执行先后顺序的制约关系可分为两种:直接制约和间接制约。
直接制约通常是指一个操作中,多个步骤之间的制约关系,也可以说是“同步的进程之间的制约关系”。如图 2-4 所示,A1、B1、C1 是一条指令的取指、分析、执行的三个步骤, 所以它们之间的关系是直接制约。
间接制约通常是指多个操作之间相同步骤的制约关系,也可以说是“互斥的进程之间的制约关系”。如图 2-4 所示,A1、A2、A3 之间就存在间接制约的关系。
前趋图的应用广泛,在项目开发中,可用前趋图来分析哪些活动可以并行完成。同时项目管理工具:Pert 图,单(双)代号网络图等都融入了前趋图的思想。
6.进程调度与死锁
进程调度即处理器调度(又称上下文转换),它的主要功能是确定在什么时候分配处理器,并确定分给哪一个进程,即让正在执行的进程改变状态并转入就绪队列的队尾,再由调度原语将就绪队列的队首进程取出,投入执行。
引起进程调度的原因有以下几类:
(1)正在执行的进程执行完毕。
(2)执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态。
(3)执行中的进程调用了 P 原语操作,从而因资源不足而阻塞;或调用 V 原语操作激活了等待资源的进程队列。

(4)在分时系统中,当一进程用完一个时间片。
(5)就绪队列中某进程的优先级变得高于当前执行进程的优先级,也将引起进程调度。进程调度的方式有两类:剥夺方式与非剥夺方式。所谓非剥夺方式是指,一旦某个作业
或进程占用了处理器,别的进程就不能把处理器从这个进程手中夺走,直到该进程自己因调用原语操作而进入阻塞状态,或时间片用完而让出处理机;剥夺方式是指,当就绪队列中有进程的优先级高于当前执行进程的优先级时,便立即发生进程调度,转让处理机。
进程调度的算法是服务于系统目标的策略,对于不同的系统与系统目标,常采用不同的调度算法:
(1)先来先服务(First Come and First Serverd,FCFS)调度算法,又称先进先出(First In and First Out,FIFO)。就绪队列按先来后到原则排队。
(2)优先数调度。优先数反映了进程优先级,就绪队列按优先数排队。有两种确定优先级的方法,即静态优先级和动态优先级。静态优先级是指进程的优先级在进程开始执行前确定,执行过程中不变,而动态优先级则可以在进程执行过程中改变。
(3)轮转法(Round Robin)。就绪队列按 FCFS 方式排队。每个进程执行一次占有处理器时间都不超过规定的时间单位(时间片),若超过,则自行释放自己所占有的 CPU 而排到就绪队列的末尾,等待下一次调度。同时,进程调度程序又去调度当前就绪队列中的第一个进程。
进程管理是操作系统的核心,在进程管理的实现中,如果设计不当,会出现一种尴尬的局面——死锁。
当若干个进程互相竞争对方已占有的资源,无限期地等待,不能向前推进时会造成“死锁”。例如,P1 进程占有资源 R1,P2 进程占有资源 R2,这时,P1 又需要资源 R2,P2 也需要资源 R1,它们在等待对方占有的资源时,又不会释放自己占有的资源,因而使双方都进入了无限等待状态。
死锁是系统的一种出错状态,它不仅会浪费大量的系统资源,甚至还会导致整个系统的崩溃,所以死锁是应该尽量预防和避免的。
(1)死锁条件。产生死锁的主要原因是供共享的系统资源不足,资源分配策略和进程的推进顺序不当。系统资源既可能是可重复使用的永久性资源,也可能是消耗性的临时资源。产生死锁的必要条件是:互斥条件、保持和等待条件、不剥夺条件和环路等待条件。
(2)解决死锁的策略。处于死锁状态的进程不能继续执行但又占用了系统资源,从而阻碍其他作业的执行。

解决死锁有两种策略:一种是在死锁发生前采用的预防和避免策略;另一种是在死锁发生后采用的检测与恢复策略。
死锁的预防主要是通过打破死锁产生的 4 个必要条件之一来保证不会产生死锁。采用的死锁预防策略通常有资源的静态分配法或有序分配法,它们分别打破了资源动态分配条件和循环等待条件,因此不会发生死锁。但这样做会大大降低系统资源的利用率和进程之间的并行程度。
死锁避免策略,则是在系统进行资源分配时,先执行一个死锁避免算法(典型的如银行家算法),以保证本次分配不会导致死锁发生。由于资源分配很频繁,因此死锁避免策略要耗费大量的 CPU 和时间。