程序员考试考点：处理机管理（进程管理）
进程管理是操作系统部分的核心内容，也是历年的考试重点，从1991-2003年，共有10道题涉及进程管理的知识点，占操作系统总题量的50%。从历年的考查情况看，主要偏重于进程的同步与互斥、信号量和P-V操作、进程的基本概念、管程及线程等方面。考生对进程部分的知识点应全面掌握。
1.进程的概念
进程是可以与其他程序并发执行的段程序的一次执行过程，是系统进行资源分配和调度的基本单位。进程是一个程序关于某个数据集的一次运行，也就是说，进程是运行中的程序，是程序的一次运行活动。相对于程序，进程是一个动态的概念，而程序是静态的概念，是指令的集合。因此，进程具有动态性和并发性。
从静态的角度看，进程实体由程序块、进程控制块(简称PCB)和数据块3部分组成。程序块描述该进程所要完成的任务;数据块包括程序在执行时所需要的数据和工作区。进程控制块包括进程的描述信息、控制信息、资源管理信息和CPU现场保护信息等，反映了进程的动态特性，如图3-2所示。
图3-2 进程控制块PCB
PCB是进程存在的唯一标志，PCB描述了进程的基本情况。系统根据PCB感知进程的存在和通过PCB中所包含各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。在创建一个进程时，首先创建其PCB,然后才能根据PCB中的信息对进程实施有效的管理和控制。当一个进程完成其功能后，系统则释放PCB,进程也随之消亡。在一般情况下，进程的PCB结构都是全部或部分常驻内存的。
2.进程的状态转换与控制
1)进程的状态及其转化
就绪状态：指进程分配到除处理机以外的必需资源(已经具备了执行的条件)的状态。进程被创建后处于就绪状态，处于就绪状态的进程可以有多个。
执行状态：指进程占有处理机正在CPU上执行的状态。在单CPU系统中，每一时刻只有一个进程处于执行状态。
阻塞状态：指进程因等待某个事件的发生而放弃处理机进入等待状态。系统中处于这种状态的进程可以有多个。
现代操作系统还有挂起状态，进程的状态及转换如图3-3所示。
图3-3 进程状态转换
进程的状态随着自身的推进和外界的变化而变化。比如，就绪状态的进程被进程调度程序选中进入执行状态;执行状态的进程因等待某一事件的发生转入等待状态;等待状态的进程所等待事件来到便进入就绪状态。进程的状态可以动态地相互转换，但阻塞状态的进程不能直接进入执行状态，就绪状态的进程不能直接进入阻塞状态。在任何时刻，任何进程都处于且只能处于某一状态。
2)进程控制
进程控制是通过进程控制原语实现的。用于进程控制的原语主要包括创建原语、阻塞原语、撤销原语、唤醒原语、优先级原语和调度原语。在操作系统中，原语是一个不可分割的基本单位。它们可以被系统本身调用，有的也以软中断形式供用户进程调用。
创建原语创建一个进程，包括系统创建和父进程创建都必须调用创建原语。新建立的进程开始处于就绪状态。调度原语是按照确定的算法，从就绪队列中选择一个就绪进程，将处理器分配给它，修改这个进程的PCB内容。唤醒原语负责叫醒阻塞队列具备运行条件的某进程，使其回到就绪队列。撤销原语将执行完毕的进程登记、回收资源并撤销这个进程及其子进程。
通常操作系统中设置3种队列：执行队列、就绪队列和阻塞队列。在单处理器系统中执行队列只有一个成员，一般阻塞队列的个数取决于等待事件(原因)的个数，新创建的进程处于就绪队列。
3.进程互斥与同步及P、V操作
1)进程互斥与同步的定义
进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，互斥是要保证临界资源在某一时刻只被一个进程访问。
进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。也就是说，进程之间是异步执行的，同步即是使各进程按一定的制约顺序和速度执行。
2)信号量(Semaphore)与P、V操作
信号量可以有效地实现进程的同步和互斥。在操作系统中，信号量是一个整数。当信号量大于等于零时，代表可供并发进程使用的资源实体数，当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量所代表的意义和设置初值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。
对信号量只能施加特殊的操作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 继续进行;}
3)用P、V操作实现进程互斥
为了保护共享资源(如公共变量等)，使它们不被多个进程同时访问，就要阻止这些进程同时执行访问这些资源的代码段，这些代码段称为临界区，这些资源称为临界资源。进程互斥不允许两个以上共享临界资源的并发进程同时进入临界区。利用P、V原语和信号量可以方便地解决并发进程对临界区的进程互斥问题。
设信号量mutex是用于互斥的信号量，初值为1.表示没有并发进程使用该临界区。于是各并发进程的临界区可改写成下列形式的代码段：
P(mutex);
临界区
V(mutex);
4)用P、V操作实现进程同步
要用P、V操作实现进程同步，需要引进私用信号量，私用信号量只与制约进程和被制约进程有关，而不是与整组并发进程相关。与此相对，进程互斥使用的信号量为公用信号量。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用P、V原语和私用信号量规定各进程的执行顺序。
经典同步问题的例子是生产者-消费者问题。这要求存后再取，取后再存，即有两个制约关系，为此，需要两个信号量，记为Bufempty和Buffull,它们的初值分别是1和0.相应的程序段形式如下。
生产者：
oop
生产一产品next;
P(Bufempty);
next产品存缓冲区;
V(Buffull);
endloop
消费者：
oop
P(Buffulll);
V(Bufempty);
从缓冲区中取产品;
使用产品
endloop
4.进程通信与管程
1)进程通信
通信(Communication)就是在进程间传送数据。一般来说，进程间的通信根据通信内容可以划分为两种：控制信息的传送和大批量数据的传送。把控制信息的传送称为低级通信，而把大批量数据的传送称为高级通信。进程的同步和互斥是通过信号量进行通信来实现的，属于低级通信。高级通信原语则提供两种通信方式，即有缓冲区的通信和无缓冲区的通信。
2)管程
汉森(Brinch Hansen)和霍尔(Hoare)提出了一个新的同步机制--管程。管程是一个由过程、变量及数据结构等组成的集合，即把系统中的资源用数据抽象地表示出来。这样，对资源的管理就可以用数据及在其上实施操作的若干过程来表示，而代表共享资源的数据及在其上操作的一组过程就构成了管程。进程可以在任何需要资源的时候调用管程，且在任一时刻最多只有一个进程能够真正地进入管程，而其他调用进程则只能等待。由此看来，管程实现了进程之间的互斥，使临界区互斥实现了自动化，它比信号量更容易保证并发进程的正确性。管程结构如图3-4所示。
图3-4 管程结构
5.进程调度与死锁
1)进程调度
进程调度即处理器调度(又称上下文转换)，它由调度原语实现。进程调度的方式有两类：剥夺方式与非剥夺方式。所谓非剥夺方式是指一旦某个作业或进程占有了处理器，别的进程就不能把处理器从这个进程手中夺走，直到该进程自己因调用原语操作而进入阻塞状态，或时间片用完而让出处理机。剥夺方式即就绪队列中一旦有进程优先级高于当前执行进程优先级时，便立即发生进程调度，转让处理机。
2)进程调度算法
进程调度的算法是服务于系统目标的策略，对于不同的系统与系统目标，常采用不同的调度算法，如：
先来先服务(FCFS)调度算法，又称先进先出(FIFO)。就绪队列按先来后到原则排队。
优先数调度。优先数反映了进程优先级，就绪队列按优先数排队，有两种确定优先级的方法，即静态优先级和动态优先级。静态优先级是指进程的优先级在进程开始执行前确定，执行过程中不变，而动态优先级则可以在进程执行过程中改变。
轮转法(Round Robin)。就绪队列按FCFS方式排队，每个进程执行一次占有处理器的时间都不超过规定的时间单位(时间片)。若超过，则自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。
(3)死锁
当若干个进程互相竞争对方已占有的资源，无限期地等待，不能向前推进时，会造成"死锁".死锁是系统的一种出错状态，应该尽量预防和避免。产生死锁的主要原因是供共享的系统资源不足、资源分配策略和进程的推进顺序不当。
产生死锁的必要条件是互斥条件、保持和等待条件、不剥夺条件及环路等待条件。
解决死锁有两种策略，一种是在死锁发生前采用的预防和避免策略，另一种是在死锁发生后采用的检测与恢复策略。
死锁的预防主要是通过打破死锁产生的4个必要条件之一来保证不会产生死锁。死锁避免策略，则是在系统进行资源分配时，先执行一个死锁避免算法(典型的如银行家算法)，来保证本次分配不会导致死锁的发生。实际上系统出现死锁的概率很小，故从系统所花的代价上看，采用死锁发生后的检测与恢复策略要比采用死锁发生前的预防与避免策略代价小一些。
6.线程
在支持线程的操作系统中，线程是进程中的一个实体，是系统实施调度的独立单位。线程只拥有-些在运行中必不可少的资源，它与属于同一个进程的其他线程共享该进程所拥有的资源，各线程之间可以并发地运行。线程切换时只需保存和设置少量寄存器的内容，而并不涉及存储器管理方面的操作，所以线程切换的开销远远小于进程的切换(原运行进程状态的切换还要引起资源转移及现场保护等问题)。同一个进程中的多个线程共享同一个地址空间，这使得线程之间同步和通信的实现也比较容易。
