计算机操作系统课件第2章进程管理

1、进程管理,进程的描述,进程是资源分配和独立运行的基本单位。操作系统所具有的四大特征也是基于进程形成的，即所谓进程观点。 显然，进程在操作系统中是个极其重要的概念。,内容提要,进程的概念 进程的状态及其转换 进程控制 进程的同步和互斥 临界资源和临界区 进程同步机制 管程机制 线程,程序的顺序执行,在任何时刻，机器只执行一个操作，只有在前一个操作执行完后，才能执行后继操作。如下图：,程序顺序执行的特点,顺序性 封闭性 可再现性,程序的并发执行,若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开

2、始。,多道技术下作业执行过程,作业A,作业B,开始,开始,空转 输入,空转 输入,空转 输入,空转 输入,停止,停止,程序并发执行的特点,间断性 失去封闭性 不可再现性,不可再现性举例之一,S1,S2,S3,S4,可能的执行序列为：,S1 S2 S3 S4,S2 S1 S3 S4,不可再现性举例之二,例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次都做N=N+1的操作，程序B每执行一次都打印N的值，并将N置为0。A和B的执行速度不同。,不可再现性举例之二,打印的结果为N+1，N=0,NN+1,Print(N),N0,程序A,程序B,不可再现性举例之二,打印的结果为N，N=1,N

3、N+1,Print(N),N0,程序A,程序B,不可再现性举例之二,打印的结果为N，N=0,NN+1,Print(N),N0,程序A,程序B,进程概念的引入,多道程序设计技术引入后，程序在系统中的执行是并发执行。并发程序在系统中执行时，和顺序程序相比，失去了封闭性，程序与CPU执行的活动之间不再一一对应，这样就使系统中的活动以及各种活动之间的相互关系非常复杂，从而程序这个静态的概念已不能如实地反映系统中的活动情况，为此，现代操作系统引入进程概念。,进程的特征,进程的定义,进程是程序的一次执行 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是程序在一个数据集合上运行的过程，它是系统

4、进行资源分配和调度的一个独立单位 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位,从操作的角度理解进程,图形窗口界面：一个窗口就是一个进程。打开窗口：建立一个进程；关闭窗口：一个进程结束。 字符命令界面：一条命令一般就是一个进程。命令行尾回车：一个进程开始；命令执行结束(下一命令提示符出现)：一个进程结束。,从编程的角度理解进程,进程建立：“建立进程”函数或系统调用 进程结束：“撤消进程”函数或系统调用，或者程序的正常或非正常结束。,进程与程序,在并发环境下，一个正在执行中的程序称为进程。 内存中的进程（动态）比外存上的程序（静态）要多很多内容（栈，动态数据，状态信息等）。

5、一个进程可对应多个程序（代码覆盖） 一个程序可对应多个进程（例如开两个WORD窗口）,进程与程序的比较,进程是动态的；程序是静态的 进程具有并发性；程序本身具有顺序性，程序的并发执行是通过进程实现的 进程具有独立性，是能独立运行的单位 程序可作为一种软件资源而长期保存；进程是程序的一次执行，是动态的，具有临时有限的生命期 进程具有结构性，从结构上看，进程是由程序、数据和进程控制块三部分组成的,进程组成模型,PCB,程序部分,数据集合,进程的组成,PCB,进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构 PCB中记录了操作系统所需的、用于描述进程情况及控制进程运行所需的全部信息

6、OS根据PCB来对并发执行的进程进行控制和管理,PCB的结构,进程与PCB的关系,每个进程有惟一的PCB 操作系统依靠PCB管理进程 利用PCB实现进程的动态并发 PCB是进程存在的惟一标志,进程的三种基本状态,万事俱备，就差CPU,就绪状态,正在CPU上运行,执行状态,等待事件，无法运行,阻塞状态,新状态和终止状态,新状态是一个进程刚刚建立，但还未进入就绪队列的状态； 终止状态是当一个进程已经正常或异常结束，OS已经将它从就绪队列中移出，但尚未被撤销时的状态； 在进程管理中，新状态和终止状态是非常有用的。,进程状态转换的意义,进程在运行期间，不断地从一个状态转换到另一个状态，体现出了进程的动

7、态性。从进程的创建，到执行，再到进程的撤销，组成了进程的整个生命周期。,进程状态图,接纳,中断,完成,进程调度,I/O请求或等待某事件,I/O完成或事件发生,几点说明,进程间的状态转换并非都是可逆的 对于一个进程来说，它处于新状态和终止状态都只有一次 进程间的状态转换并非都是主动的 进程在执行态才是真正运行,进程控制,进程控制是指系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程运行中的状态转换。这些功能的实现由原语完成。,原语,由若干条指令组成。这些指令，要么全做，要么全不做，不允许中断。是不可分割的操作，具有原子操作的性质。,进程的创建,一旦操作系统发现了要求创建新进程的事件后，

8、便调用进程创建原语Creat( )，步骤如下：,申请空白PCB,为新进程分配资源,初始化PCB,插入就绪队列,进程树体现进程间的关系,引起创建进程的事件,用户登录 作业调度 提供服务 应用请求,引起进程终止的事件,正常结束 异常结束 外界干预，包括：操作员或OS干预、父进程请求、父进程终止,进程终止的过程,根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态； 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度； 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程； 将被终止进程所拥有

9、的全部资源，或者归还给其父进程， 或者归还给系统； 将被终止进程(它的PCB)从所在队列(或链表)中移出。,引起进程阻塞和唤醒的事件,请求系统服务 启动某种操作 新数据尚未到达 无新工作可做,进程阻塞的过程,中断CPU 将其运行现场保存在其PCB中 置进程状态为阻塞态 插入阻塞队列 转进程调度,进程唤醒的过程,把被阻塞进程从阻塞队列中移出 将其PCB的现行状态改为就绪状态 插入就绪队列中,进程挂起的过程,系统利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起； 运行态 静止就绪 活动就绪静止就绪 活动阻塞静止阻塞,进程激活的过程,系统利用激活原语active( )将指定进程激活

10、； 静止就绪活动就绪 静止阻塞活动阻塞,进程同步,进程同步的主要任务，是使并发执行的多个进程之间能有效地共享资源和互相合作，从而使程序的执行具有可再现性。,进程间存在的两种关系,资源共享关系 互相合作关系,临界资源与临界区,临界资源：一次仅允许一个进程使用的共享资源，如打印机、磁带机、共享变量等 临界区：在每个进程中访问临界资源的那段程序，简称CS区,生产者消费者举例,1,n,设置整型变量counter，记录可以消费的消息数。设它的初值为5。,执行举例,P1: register1=counter; P2: register1=register1+1; P3: counter=register1

11、;,C1: register2=counter; C2: register2=register2-1; C3: counter=register2;,执行序列一： P1,P2,P3,C1,C2,C3，则最后结果为counter=5,执行序列二： C1,C2,C3,P1,P2,P3 ，则最后结果为counter=5,执行序列三： P1,P2,C1,C2,P3,C3，则最后结果为counter=4,具有临界区的进程结构,一个访问临界资源的循环进程可描述如下：,repeat,entry section,critical section,exit section,remainder section,u

12、ntil false;,结果分析,执行序列三最后结果counter的值为4，是错误的，这表明程序的执行不能具有可再现性。为了预防发生这种错误，解决此问题的关键，是应把变量counter设为临界资源，令生产者和消费者进程互斥访问变量counter。,同步机制应遵循的机制,空闲让进 忙则等待 有限等待 让权等待,用软件方法解决进程互斥问题,利用软件方法来解决进程互斥问题，可以在很大程度上体现进程互斥问题的复杂度，现在已经很少使用软件方法来解决进程互斥了。,算法一,设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号。,repeat,while turni do no_op;,criti

13、cal section,turn=j;,remainder section,until false;,算法1不能保证实现“空闲让进”的准则。,算法二,repeat,while flagj do no_op;,critical section,flagi=false;,remainder section,until false;,算法2违背了“忙则等待”的准则。,Boolean flagn;,flagi=true;,算法三,repeat,while flagj do no_op;,critical section,flagi=false;,remainder section,until fals

14、e;,算法3违背了“有空让进”的准则。,Boolean flagn;,flagi=true;,算法四,repeat,while(flagj and turn=j) do no_op;,critical section,flagi=false;,remainder section,until false;,算法4结合了算法2和算法3各自的优点，是一种成功的算法。,Boolean flagn;,flagi=true; turn=j;,用硬件方法解决进程互斥问题,利用Test-and-Set指令实现互斥 利用Swap指令实现互斥,Test-and-Set指令,boolean TS(boolean l

15、ock),lock=true;,其中，lock有两种状态： lock=false，表示该资源空闲； lock=true，表示该资源正被使用。,Test-and-Set指令可定义为：,TS=lock;,利用TS实现进程互斥,利用TS实现进程互斥的循环进程可描述如下：,repeat,while TS(lock) do-skip;,critical section,lock=false;,remainder section,until false;,Swap指令,Swap(boolean a, boolean b),a=b;,Test-and-Set指令可定义为：,temp=a;,b=temp;,利

16、用Swap实现进程互斥,利用Swap实现进程互斥的循环进程可描述如下：,repeat,key=true;,critical section,lock=false;,remainder section,until false;,repeat,Swap(lock, key);,until key=false;,信号量机制,1965年，荷兰计算机学家Dijkstra提出了一种卓有成效的进程同步工具信号量机制。在应用中，信号量机制又发展为信号量集机制，现在已被广泛应用于单处理机和多处理机以及计算机网络中。,整型信号量,Dijkstra最初将信号量定义为依个整型量，除初始化外，只能通过两个标准原子操作w

17、ait(s)和signal(s)来访问。这两个操作被称为P、V操作。可描述为： wait(s): while s0 do no_op; s=s-1; signal(s): s=s+1;,利用信号量实现互斥,为使多个进程互斥访问某临界资源，只需为该资源定义一个互斥信号量mutex，并设其初始值为1。然后将各进程的临界区CS置于wait(mutex)和signal(mutex)操作之间即可实现互斥。,利用信号量实现进程互斥,利用信号量实现进程互斥的循环进程可描述如下：,P1: repeat wait(mutex); critical section signal(mutex); remainder

18、 section until false;,P2: repeat wait(mutex); critical section signal(mutex); remainder section until false;,利用信号量描述前驱关系,设有两个并发执行的进程P1和P2。P1中有语句S1，P2中有语句S2。若希望先执行S1，再执行S2，只需使进程P1和P2共享一个公用信号量S，并赋予初值为0。描述如下： P1： S1； signal(S); P2: wait(S); S2;,利用信号量描述前驱关系举例,已知有前驱关系，如下图：,利用信号量描述前驱关系举例,a=b=c=d=e=f=g=0;,

19、begin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; end;,记录型信号量机制,整型信号量机制不能遵循“让权等待”的原则。因此除了需要代表资源数目的整型变量value之外，还应增加

20、一个进程链表L，用于链接所有等待的进程。可描述为： type record value: integer; L: list of process; end,记录型信号量机制,相应地，wait(S)和signal(S)操作可描述为： wait(S) signal(S) Begin begin S.value=S.value-1; S.value=S.value+1; if S.value0 if S.value0 block(S, L); wakeup(S, L); End end,经典进程同步问题,在多道程序设计环境下，进程同步问题是十分重要的。由此产生了许多经典的进程同步问题，比较有代表性的

21、有“生产者消费者问题”、“读者写者问题” 、“哲学家进餐问题”等。通过研究这些问题，可以更好地帮助我们理解进程同步的概念和实现方法。,生产者消费者问题,在生产者和消费者进程之间存在一个具有n个缓冲区的公用缓冲池。可利用信号量mutex实现对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。变量定义如下： mutex=1, empty=n, full=0; item buffern; in=0, out=0;,生产者进程,Producer:,begin repeat produce an item in nextp wait(empty); wait(mu

22、tex); bufferin=nextp; in=(in+1) mod n; signal(mutex); signal(full); until false; end;,消费者进程,Consumer:,begin repeat wait(full); wait(mutex); nextc=bufferout; out=(out+1) mod n; signal(mutex); signal(empty); consume the item in nextc until false; end;,读者写者问题,文件或记录可被多个进程共享。将只要求读的进程称为“reader进程”，其它称为“wri

23、ter进程” 。允许多个reader进程同时读一个共享对象，却不允许writer进程和其它reader进程或writer进程同时访问。,读者写者问题,为实现读写互斥，可设置互斥信号量wmutex。再设置一个整型信号量readcount，记录正在读的进程数目。由于readcount可被多个reader进程访问，所以是个临界资源，可为它设置一个互斥信号量rmutex。,读者进程,Reader:,begin repeat wait(mutex); if readcount=0 wait(wmutex); readcount=readcount+1; signal(rmutex); Perform r

24、ead operation wait(rmutex); readcount=readcount+1; if readcount=0 signal(wmutex); signal(rmutex); until false; end;,写进程,Writer:,begin repeat wait(wmutex); perform write operation signal(wmutex); until false; end;,哲学家进餐问题,哲学家进餐问题由Dijkstra提出并解决的。该问题描述了5个哲学家共用一张圆桌，桌子上放着5只碗和5只筷子。一个哲学家饥饿时，试图取左右最靠近他的两只筷子。只有在他取得两只筷子后才能进餐。进餐完毕，他可以放下筷子继续思