操作系统教程(第二章)

第二章进程及处理机管理§2.1进程的提出§2.2进程的定义和特征§2.3进程状态和进程控制块§2.4线程的基本概念§2.5进程控制§2.6进程同步§2.7经典进程同步问题§2.8进程的通信§2.9处理机调度§2.10死锁第二章进程及处理机管理第二章进程及处理机管理——§2.1进程的提出一、程序的执行1前趋图前趋图指的是有向无循环图。在这里，我们用前趋图表示系统在某个时间完成工作的流程。在图中，结点表示一条语句、一个程序段落或一个程序。有向边表示结点之间的偏序或前趋关系。前趋图是无循环的图。必然有一个结点没有前趋，一个结点没有后继

第二章进程及处理机管理——§2.1进程的提出一、程序的执行2程序顺序执行（1）顺序性：（2）封闭型（3）程序的执行结果与速度和时间没有关系。（4）可再现性3程序并发执行（1）间断性（2）失去封闭性（3）不可再现性（4）．通信性

（5）．程序与执行过程不再一一对应二、进程的引入资源分配的单位不再是程序程序与执行过程不再是一一对应一个程序的多个运行过程中资源分配第二章进程及处理机管理——

§2.2进程的定义和特征一、进程的定义1进程是指程序的一次执行过程。2进程定义为一个数据结构和能在其上进行操作。3进程是程序在一个数据集合上运行的过程。4进程是系统资源进行分配和调度的一个独立单位。5指可并发执行的程序，在一个数据集合上运行过程。进程是一个正在执行中的程序

（不正确的一个意思，但可以作为一种今后学习上的参考解释）第二章进程及处理机管理——

§2.2进程的定义和特征二、进程的特征1动态性：指的是程序的一次执行过程，是一个动态的概念，而程序只是指的指令序列的集合，没有运行（运动）的含义。因此，程序是静态的。2并发性：指进程之间是可以并发执行的。3独立性：指进程是一个独立运行的、独立分配资源的单位。4异步性：进程之间按各自的、不可预知的速度向前推进。5结构特征：进程是有一定的组成成分，而且有一定的结构形式，简单地说进程是由程序+数据+进程控制块组成的，而进程控制块是使计算机系统识别该进程、运行该进程的一个唯一标志，这在后面我们将要提到。第二章进程及处理机管理——

§2.2进程的定义和特征进程树在这里，我们还应该注意到，进程是一个程序的运行过程，这其中会包含两种情况：一是该进程是系统要求执行的。另一个是该进程所包含的程序是另一个程序的子程序，该进程的执行是另一个程序要求执行的。所以，在系统中，进程和进程之间是有一定关联的。这种关联的形式我们可以用进程树来表示。第二章进程及处理机管理——

§2.3进程的状态和进程控制块一、进程的状态1基本状态（1）执行状态进程已经获得了处理机（CPU），其程序正在运行。（2）阻塞状态（等待状态）正在执行的进程，由于发生某事件而暂时无法执行时，而放弃处理进入暂停状态。（3）就绪状态已经完成暂停，在没有得到CPU前所处的状态2扩充状态（1）执行状态（2）活动阻塞状态（3）静止阻塞状态（4）活动就绪状态（5）静止就绪状态第二章进程及处理机管理——

§2.3进程的状态和进程控制块二、进程控制块1进程控制块进程控制块其英文名称为ProcessControlBlock，简称PCB。是使计算机系统感知进程存在的唯一依据，是描述和控制进程的执行过程的一个数据结构。2进程控制块的结构（1）．进程标识符（进程内部名称）（2）．现行状态（3）．现场保留区（4）．程序和数据地址（5）．互斥与同步结构：（6）．进程通信机制：（7）．优先级（8）．资源清单（9）．链接字（队列指针）（10）．家族联系第二章进程及处理机管理——

§2.3进程的状态和进程控制块三、进程控制块组织结构1链接方式2索引方式第二章进程及处理机管理——§2.4线程一、线程的引入进程拥有资源在进程运行过程中，资源需要被处理进程整体的过程可以由调度、控制、资源处理等组成分离后，将调度单独完成二、线程的概念线程是进程中的一个实体，是被系统独立调度和分派的基本单位。三、线程与进程（见书P53页）1调度

2并发性

3拥有资源

4系统开销

第二章进程及处理机管理——

§2.5进程控制进程的控制指的是进程的创建和撤消，以及实现进程的状态转换。进程控制一般是由操作系统的内核完成。内核（Kernel）是指基于硬件的第一层软件，完成操作系统的基本功能的进程集合。是由原语设计的原语（Primitive）是指机器指令的延伸，是由若干条机器指令构成的，不可中断的程序代码。实现对进程的控制在多数系统中都提供了六个原语实现的。第二章进程及处理机管理——

§2.5进程控制创建、撤销、激活、阻塞、唤醒、挂起第二章进程及处理机管理——

§2.5进程控制一、进程的创建原语（CreatePrimitive） 1调用创建原语的情况用户登录程序执行用户提出请求而为之提供的服务应用请求 2创建原语描述第二章进程及处理机管理——

§2.5进程控制二、进程的撤消原语（Destroy

Primitive） 1引起进程撤消的情况正常结束异常结束外界干扰 2撤消原语描述第二章进程及处理机管理——

§2.5进程控制三、进程的阻塞原语（Block

Primitive） 1引起进程阻塞的原因

（1）请求系统服务，但没有得到及时的响应（2）启动某种Ｉ／Ｏ （3）新数据还没有到来（4）没有新的工作

2阻塞原语描述第二章进程及处理机管理——

§2.5进程控制四、进程的唤醒原语（Wakeup

Primitive） 1、某进程所请求的事件完成，从阻塞状态到就绪状态

2、唤醒原语描述第二章进程及处理机管理——

§2.5进程控制五、进程的挂起原语（Suspend

Primitive） 1当需要对正在运行的程序进行调试时，通过挂起原语使其变成静止的某一种状态

2挂起原语描述第二章进程及处理机管理——

§2.5进程控制六、进程的激活原语（Active

Primitive） 1当进程调试完成后，通过激活原语将其投入参与运行

2激活原语描述第二章进程及处理机管理——

§2.6进程同步进程同步是由于进程之间的并发执行造成的一种相互制约、相互协调，按一定次序进行的现象根据相互制约的不同形式，可以分为两种形式的同步：互斥同步和依赖同步。简称互斥和同步第二章进程及处理机管理——

§2.6进程同步一、基本概念1临界资源（CriticalResource）临界资源指的是计算机系统中每次只允许一个进程访问的资源。计算机系统中大部分资源属于临界资源。显示器？键盘？2临界区（Criticalsection）临界区指的是在一个进程中访问临界资源的那段代码。3对于临界资源的使用两个或两个以上进程不能同时进入自己的临界区，访问临界资源。这就要求有一个同步机制来制约各个进程的执行，这个同步机制应该遵循以下四条准则：空闲让进。②忙则等待，③有限等待。④让权等待。第二章进程及处理机管理——

§2.6进程同步二、互斥同步定义指的是两个或两个以上的进程在共享某一临界资源时，所采取的一种协调制约形式，即互相排斥地使用临界资源。实现方法：硬件机制信号量机制管程第二章进程及处理机管理——

§2.6进程同步（互斥）硬件机制利用计算机系统中提供的硬件操作指令来实现。主要有TS指令和Swap指令1TS指令2Swap指令第二章进程及处理机管理——

§2.6进程同步（互斥）信号量机制1经典信号量机制（1）信号量（Semaphore）表示资源的物理实体。定义为一个整形变量，它的值除初值外只能由P-V操作完成。可以看作是反映资源的数目。也可以看作反映资源可被共享的次数。

（2）P-V操作P-V操作是两个原子操作（Atomicoperation）P（S）和V（S）。利用对信号量S的操作来实现互斥。

（3）实现互斥（4）缺陷当S<=0时执行P操作，必将使进程处于“忙等”状态。所谓“忙等”指的是该进程无法向下进行.但还占用CPU时间。第二章进程及处理机管理——

§2.6进程同步（互斥）信号量机制2记录型信号量机制（1）信号量（2）P-V操作（3）实现（4）特点：改进了系统运行的效率，在进程被阻塞的时候，可以使处理机继续完成其它的任务，而不是等待第二章进程及处理机管理——

§2.6进程同步（互斥）信号量机制3信号量集机制（1）提出的原因（2）解决方案强制资源访问顺序一次性申请（信号量集机制）第二章进程及处理机管理——

§2.6进程同步三、依赖同步（同步）1概念指的是两个合作进程，当某一进程未得到另一个进程发出来的消息之前处于等待，直到另一个进程发出来消息后，该进程继续向下执行。2举例3实现P-V操作和信号量机制第二章进程及处理机管理——

§2.6进程同步四、说明1进程同步是进程低级通信的一种形式。

2P-V操作实质和信号量的物理意义

信号量的物理意义是：信号量S表示资源的数目。当S>0时，S的数值表示可用资源的个数当S=0时，表示当前系统已经没有可用资源当S<0时，S的数值表示当前系统缺少的资源个数，也可以表示当前因为没有申请到资源而被阻塞的进程个数。P-V操作的实质：在互斥中，P操作表示请求分配一个资源，V操作表示请求释放一个资源在同步中，P操作表示检测消息是否到来，V操作表示发送消息。经典信号量机制实现互斥可以为临界资源先设置一个互斥信号量S，其初始值为该临界资源的数目。在进程对这个临界资源进行访问之前，先执行P操作；在退出临界区之后执行V操做。记录型信号量机制实现互斥记录型信号量机制存在的问题信号量集机制第二章进程及处理机管理——

§2.7几个经典的进程同步问题一、生产者与消费者问题其主要思想是一组生产者向一组消费者提供信息。他们之间共用同一个有界缓冲区

1、有一个缓冲池，一次只能让一个进入，不论是生产者还是消费者。2、在一个缓冲池中有多个缓冲区，每个缓冲区一次也只能由一个使用3、生产者可以把它的产品放在任何一个空的缓冲区中4、消费者可以到任何一个已有产品的缓冲区中取产品5、生产者只有等到缓冲区有空的时候才可以放产品，消费者只有当缓冲区有产品的时候才可以把产品取走生产者与消费者问题生产者与消费者存在的问题第二章进程及处理机管理——

§2.7几个经典的进程同步问题二、读者-写者问题一个数据文件或记录（统称为数据对象），可被多个进程共享。其中有些进程要求读，而另一些进程要求写或修改。我们把只要求读的进程称为“读者”。其他进程称为“写者”。允许多个读者可同时访问一个共享对象，而不允许一个写者和其他进程（可能是读者，也可能是写者）同时访问同一个共享对象。1、读者之间可以共享使用这个文件对象2、写者之间只能有一个使用这个文件对象3、当一个写者在使用的时候，读者也不能使用这个文件读者-写者问题解决方案第二章进程及处理机管理——

§2.7几个经典的进程同步问题三、哲学家进餐的问题有五个哲学家，他们的生活方式是交替的进行思考和进餐，哲学家们共用一张圆桌，周围放五张椅子，每人坐一张。在圆桌上有五个碗和五只筷子，当一个哲学家思考时，他不与同事交谈，饥饿时便试图取其左右最靠近他的筷子，但有可能一支都拿不到，只有在他拿到两支筷子才能进餐。餐毕，放下筷子又继续思考。哲学家进餐问题解决方案1、用一个信号量表示一只筷子，共有五个信号量构成信号量数组2、需要加上一些限制条件，否则容易出现错误。3、限制条件比如是：至多允许四个哲学家同时进餐；仅当哲学家左右两支筷子都可以用时，才能拿起进餐第二章进程及处理机管理——

§2.7几个经典的进程同步问题四、司机和售票员问题司机负责汽车的启动、运行和停止；售票员负责车门的打开和关闭。当司机在汽车启动工作中，售票员是不允许打开车门的；当汽车停止的时候，售票员可以把车门打开；当售票员把车门关闭后，司机可以启动汽车。第二章进程及处理机管理——

§2.7几个经典的进程同步问题五、读、计算和打印三个进程问题司机和售票员问题第二章进程及处理机管理——

§2.7几个经典的进程同步问题六、十字路口问题1、东西和南北走向要分开2、在中心有共享区3、如果有左转问题，解决方案比较复杂第二章进程及处理机管理——

§2.8进程通信在前面我们所介绍的进程同步中，不论是互斥还是同步，都可以理解为双方相互之间的信息传递，但传递的信息只是一个消息，没有数据信息的概念，为此，我们把这样的消息传递称为“低级通信”一、进程通信方式1共享存储的系统（sharedmemorysystem）在这种方式中，相互通信的进程共享某些数据结构或共享存储区基于共享数据结构的通信方式基于共享存储区的通信方式

第二章进程及处理机管理——

§2.8进程通信一、进程通信方式2信息系统（Messagesystem）

在这种方式中，进程之间通过消息或报只交换信息，并提供相应一组通信命令来实现通信直接通信方式指发送进程通过系统原语，直接将消息发送给接收进程。通常使用的系统原语是：send（receiver，message）和receive（sender，message）。间接通信方式指进程之间的通信，需要借助一个数据结构来实现。3利用共享文件的通信方式

间接通信中的数据结构——信箱信箱头包含信箱的名称、大小、安全等信息；信箱体是用来存放通信数据的。信箱通信是根据系统提供的一些控制原语来完成。这些控制原语包括创建和撤消信箱、发送和接收消息等。例如：send（mailbox，message）、receive（mailbox，message）。信箱分为：私有信箱、公用信箱、共享信箱。根据信箱通信的方式，通信进程之间存在有：一对一关系、多对一关系、一对多关系和多对多关系实际例子1、每个接收者都有一个以自己ID为标识的信箱2、每个发送者都可以把信件放在接收者的信箱中3、与其它共享存储区不同的是信箱是统一管理的，发送者和接收者都不需要考虑对信箱的管理问题第二章进程及处理机管理——

§2.8进程通信二、进程通信实例-消息缓冲队列通信机制

第二章进程及处理机管理——

§2.9处理机调度处理机调度是进程及处理机管理功能中的最后一个。由于在计算机系统中处于就绪状态的进程很多，如何调度它们使之运行，并且还能充分提高处理机的利用率和改善系统性能，成为现代操作系统中的一个中心问题。

一、进程调度的功能和方式1进程调度的功能：i.记住进程的状态ii.决定某个进程什么时候得到处理机，占用多长时间iii.执行把处理机分配进程iv.让出处理机2进程调度方式：指的是当一进程正在处理机上运行时，若有某个更为重要的或紧迫的进程到来时，该如何分配处理机通常有两种调度方式：i.非剥夺方式ii.

剥夺方式第二章进程及处理机管理——

§2.9处理机调度二、调度算法1先进先出（FIFO）算法2最短cup运行期优先调度算法（SCBF）3最高优先权（FPF）优先调度算法静态优先级动态优先级4轮转法简单轮转法多级队列轮转法多级反馈队列轮转法第二章进程及处理机管理——§2.10死锁死锁指的是当某个进程提出资源申请后，使得若干进程在无外力作用下永远不能继续执行。产生死锁的原因和条件如何解除和预防避免出现死锁。

第二章进程及处理机管理——§2.10死锁一、产生死锁的原因和必要条件1产生死锁的原因：资源引起死锁：由于共享资源数目不够。进程推进顺序不当引起死锁2产生死锁的必要条件：互斥条件：即共享资源一次只能为一个进程占有。请求与保持条件：即进程一旦拥有某一共享资源，就不会在使用过程中自动释放，即使在被阻塞时也不释放。不剥夺条件：即进程已获得某一资源，在未使用完之前不能被剥夺。环路条件：在发生死锁时，必然会出现进程——资源的环形链。注意：环路条件既是必要条件，又是充分条件。

第二章进程及处理机管理——§2.10死锁二、预防死锁1屏弃‘请求和保持’条件：采取系统要求进程一次性的申请所需的所有资源。2屏弃‘不剥夺’条件：采取进程得不到新请求的资源，则将已请求到的资源释放。3屏弃‘环路条件’采取系统中所有资源排队排号，进程在请求资源时要严格按照资源序号递增的顺序。第二章进程及处理机管理——§2.10死锁三、避免死锁1安全状态：指系统能按某种进程顺序如（P1，P2，P3．．．Pn），来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。这时（P1，P2，P3．．．Pn）序列我们称为安全序列。2不安全状态：若系统中不存在一个安全序列，则称系统处于不安全状态。银行家算法1数据结构2银行家算法描述设request(j)是进程P(i)的请求向量。如果request[j]=k，表示进程P(i)需要k个R(j)类资源。

3安全性算法设置两个向量Work和FinishWork表示可提供给进程继续运行所需的各类资源数目，它含有m个元素。其初始值work=available。finish表示是否有足够的资源分配给进程。其初始值finish[i]=false.

银行家算法——举例假定系统中有五个进程{p0,p1,p2,p3,p4}和三类资源{a,b,c},各类资源总数量分别为10，5，7。在t0时刻的资源分配情况如下MaxAllocationNeedavailableABCABCABCABcP0753010743332P1322200122P2902302600P3222211011p44330024311t0时刻是否安全？2P1发出请求向量request(p1)={1,0,2}，是否进行分配？3P4发出请求向量request(p4)={3,3,0}，是否进行分配？4P0发出请求向量request(p0)={0,2,0}，是否进行分配？5P0发出请求向量request(p0)={0,1,0}，是否进行分配？第二章进程及处理机管理——§2.10死锁四、检测死锁1资源状态图该图n各结点和f组边构成，G(N,E)具有如下定义：n被分成两个独立的子集，一组为进程结点Ｐ＝（p1，p2，p3．．．Pn)，一组为资源结点Ｒ＝（r1，r2，r3．．．rn）对于边e∈E，都连接着Ｐ中的一个