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

进程管理,进程的描述,进程是资源分配和独立运行的基本单位。操作系统所具有的四大特征也是基于进程形成的，即所谓进程观点。 显然，进程在操作系统中是个极其重要的概念。,内容提要,进程的概念进程的状态及其转换进程控制进程的同步和互斥临界资源和临界区进程同步机制管程机制线程,程序的顺序执行,在任何时刻，机器只执行一个操作，只有在前一个操作执行完后，才能执行后继操作。如下图：,程序顺序执行的特点,顺序性封闭性可再现性,程序的并发执行,若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。,多道技术下作业执行过程,作业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,NN+1,Print(N),N0,程序A,程序B,不可再现性举例之二,打印的结果为N，N=0,NN+1,Print(N),N0,程序A,程序B,进程概念的引入,多道程序设计技术引入后，程序在系统中的执行是并发执行。并发程序在系统中执行时，和顺序程序相比，失去了封闭性，程序与CPU执行的活动之间不再一一对应，这样就使系统中的活动以及各种活动之间的相互关系非常复杂，从而程序这个静态的概念已不能如实地反映系统中的活动情况，为此，现代操作系统引入进程概念。,进程的特征,进程的定义,进程是程序的一次执行进程是一个程序及其数据在处理机上顺序执行时所发生的活动进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位,从操作的角度理解进程,图形窗口界面：一个窗口就是一个进程。打开窗口：建立一个进程；关闭窗口：一个进程结束。字符命令界面：一条命令一般就是一个进程。命令行尾回车：一个进程开始；命令执行结束(下一命令提示符出现)：一个进程结束。,从编程的角度理解进程,进程建立：“建立进程”函数或系统调用进程结束：“撤消进程”函数或系统调用，或者程序的正常或非正常结束。,进程与程序,在并发环境下，一个正在执行中的程序称为进程。内存中的进程（动态）比外存上的程序（静态）要多很多内容（栈，动态数据，状态信息等）。一个进程可对应多个程序（代码覆盖）一个程序可对应多个进程（例如开两个WORD窗口）,进程与程序的比较,进程是动态的；程序是静态的进程具有并发性；程序本身具有顺序性，程序的并发执行是通过进程实现的进程具有独立性，是能独立运行的单位程序可作为一种软件资源而长期保存；进程是程序的一次执行，是动态的，具有临时有限的生命期进程具有结构性，从结构上看，进程是由程序、数据和进程控制块三部分组成的,进程组成模型,PCB,程序部分,数据集合,进程的组成,PCB,进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构PCB中记录了操作系统所需的、用于描述进程情况及控制进程运行所需的全部信息OS根据PCB来对并发执行的进程进行控制和管理,PCB的结构,进程与PCB的关系,每个进程有惟一的PCB操作系统依靠PCB管理进程利用PCB实现进程的动态并发PCB是进程存在的惟一标志,进程的三种基本状态,万事俱备，就差CPU,就绪状态,正在CPU上运行,执行状态,等待事件，无法运行,阻塞状态,新状态和终止状态,新状态是一个进程刚刚建立，但还未进入就绪队列的状态；终止状态是当一个进程已经正常或异常结束，OS已经将它从就绪队列中移出，但尚未被撤销时的状态；在进程管理中，新状态和终止状态是非常有用的。,进程状态转换的意义,进程在运行期间，不断地从一个状态转换到另一个状态，体现出了进程的动态性。从进程的创建，到执行，再到进程的撤销，组成了进程的整个生命周期。,进程状态图,接纳,中断,完成,进程调度,I/O请求或等待某事件,I/O完成或事件发生,几点说明,进程间的状态转换并非都是可逆的对于一个进程来说，它处于新状态和终止状态都只有一次进程间的状态转换并非都是主动的进程在执行态才是真正运行,进程控制,进程控制是指系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程运行中的状态转换。这些功能的实现由原语完成。,原语,由若干条指令组成。这些指令，要么全做，要么全不做，不允许中断。是不可分割的操作，具有原子操作的性质。,进程的创建,一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语Creat( )，步骤如下：,申请空白PCB,为新进程分配资源,初始化PCB,插入就绪队列,进程树体现进程间的关系,引起创建进程的事件,用户登录作业调度提供服务应用请求,引起进程终止的事件,正常结束异常结束外界干预，包括：操作员或OS干预、父进程请求、父进程终止,进程终止的过程,根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度；若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程；将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统；将被终止进程(它的PCB)从所在队列(或链表)中移出。,引起进程阻塞和唤醒的事件,请求系统服务启动某种操作新数据尚未到达无新工作可做,进程阻塞的过程,中断CPU将其运行现场保存在其PCB中置进程状态为阻塞态插入阻塞队列转进程调度,进程唤醒的过程,把被阻塞进程从阻塞队列中移出将其PCB的现行状态改为就绪状态插入就绪队列中,进程挂起的过程,系统利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起；运行态 静止就绪活动就绪静止就绪活动阻塞静止阻塞,进程激活的过程,系统利用激活原语active( )将指定进程激活；静止就绪活动就绪静止阻塞活动阻塞,进程同步,进程同步的主要任务，是使并发执行的多个进程之间能有效地共享资源和互相合作，从而使程序的执行具有可再现性。,进程间存在的两种关系,资源共享关系互相合作关系,临界资源与临界区,临界资源：一次仅允许一个进程使用的共享资源，如打印机、磁带机、共享变量等临界区：在每个进程中访问临界资源的那段程序，简称CS区,生产者消费者举例,1,n,设置整型变量counter，记录可以消费的消息数。设它的初值为5。,执行举例,P1: register1=counter;P2: register1=register1+1;P3: counter=register1;,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,until false;,结果分析,执行序列三最后结果counter的值为4，是错误的，这表明程序的执行不能具有可再现性。为了预防发生这种错误，解决此问题的关键，是应把变量counter设为临界资源，令生产者和消费者进程互斥访问变量counter。,同步机制应遵循的机制,空闲让进忙则等待有限等待让权等待,用软件方法解决进程互斥问题,利用软件方法来解决进程互斥问题，可以在很大程度上体现进程互斥问题的复杂度，现在已经很少使用软件方法来解决进程互斥了。,算法一,设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号。,repeat,while turni do no_op;,critical 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 false;,算法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 lock),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;,利用Swap实现进程互斥,利用Swap实现进程互斥的循环进程可描述如下：,repeat,key=true;,critical section,lock=false;,remainder section,until false;,repeat,Swap(lock, key);,until key=false;,信号量机制,1965年，荷兰计算机学家Dijkstra提出了一种卓有成效的进程同步工具信号量机制。在应用中，信号量机制又发展为信号量集机制，现在已被广泛应用于单处理机和多处理机以及计算机网络中。,整型信号量,Dijkstra最初将信号量定义为依个整型量，除初始化外，只能通过两个标准原子操作wait(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 sectionuntil false;,P2:repeat wait(mutex); critical section signal(mutex); remainder sectionuntil 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;,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之外，还应增加一个进程链表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,经典进程同步问题,在多道程序设计环境下，进程同步问题是十分重要的。由此产生了许多经典的进程同步问题，比较有代表性的有“生产者消费者问题”、“读者写者问题” 、“哲学家进餐问题”等。通过研究这些问题，可以更好地帮助我们理解进程同步的概念和实现方法。,生产者消费者问题,在生产者和消费者进程之间存在一个具有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(mutex); 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进程”，其它称为“writer进程” 。允许多个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 read 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只筷子。一个哲学家饥饿时，试图取左右最靠近他的两只筷子。只有在他取得两只筷子后才能进餐。进餐完毕，他可以放下筷子继续思考。,哲学家进餐问题,begin repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat: signal(chopsticki); signal(chopstick(i+1) mod 5); think: until false;end;,信号量机制的缺点,同步操作分散易读性差不便于维护和修改正确性难以保证,管程的引入,管程的基本思想：把信号量及其操作原语封装在一个对象内部，即将共享变量以及对共享变量的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句。,管程的特征,模块化抽象数据类型信息掩蔽,管程的实现要素,管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程必须互斥进入管程通常是用来管理资源的，因而在管程中设有进程等待队列以及相应的等待及唤醒操作,进程的弊端,由于进程是一个资源的拥有者，因而在创建、撤销和切换中，系统必须为之付出较大的时空开销。因此，系统中的进程数目不宜过多，进程切换的频率也不宜过高，从而限制了并发程序的进一步提高。,线程的引入,引入线程的目的：为了使多个程序更好的并发执行，同时又尽量减少系统的开销将进程的两个基本属性（资源的拥有者和可独立调度和分派的基本单位）分开，进程只做为资源的拥有者，而线程作为处理机调度的和分派的基本单位线程是进程中的一个执行单位,线程的属性,轻型实体线程是进程中的一个可执行实体，是可独立调度和分派的基本单位可并发执行共享进程资源,进程与线程的比较,调度并发性拥有资源系统开销,