进程的描述与控制.ppt

1,第二章 进程的描述与控制,2.1 前趋图和程序执行2.2 进程的描述2.3 进程控制2.4 线程的基本概念,2,2.1 前趋图和程序执行,一、前趋图的定义二、程序的顺序执行三、程序的并发执行四、程序并发执行的条件,3,一、前趋图的定义,前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。=(Pi,Pj)|Pi must complete before Pj may start,如果(Pi,Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。如：IiCiPi和S1S2S3,4,DAG定义续,对于上图(a)所示的前趋图，存在下述前趋关系：P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应当注意，前趋图中必须不存在循环，但在上图(b)中却有着下述的前趋关系：S2S3,S3S2,5,二、程序的顺序执行,1、程序的顺序执行2、程序顺序执行时的特征,6,1、程序的顺序执行,仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。再如：S1：a:=x+y;S2：b:=a-5;S3：c:=b+1;,7,2、程序顺序执行时的特征,顺序性；封闭性；可再现性。,8,三、程序的并发执行,1、程序的并发执行2、程序并发执行时的特征,9,1、程序的并发执行,在上图(a)例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段，可用上图(b)表示。S1：a:=x+2S2：b:=y+4S3：c:=a+bS4：d:=c+b,10,2、程序并发执行时的特征,1)间断性2)失去封闭性3)不可再现性例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。N:=N+1在Print(N)和N:=0之前，此时N的值分别为n+1,n+1,0。N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n,0,1。N:=N+1在Print(N)和N:=0之间，此时的N值分别为n,n+1,0。,11,四、程序并发执行的条件,1、读、写集的概念2、Bernstein条件3、程序并发执行的判定,12,1、读、写集的概念,读集R(pi)=a1,a2,am表示程序pi在执行期间所要参考的所需参考的所有变量的集合。写集W(pi)=b1,b2,bn表示程序pi在执行期间要改变的所有变量的集合。如c:=a-b和w:=c+1两条语句，其读、写集分别为：R(c:=a-b)=a,bW(c:=a-b)=cR(w:=c-1)=cW(w:=c-1)=w,13,2、Bernstein条件,1966年Bernstein首先提出了p1、p2并发执行的条件，又称为Bernstein条件。若两个程序p1、p2能满足下述条件，他们便能并发执行，且具有可再现性。R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=,14,3、程序并发执行的判定,例如，有四条语句：S1：a:=x+yS2：b:=z+1S3：c:=a-bS4：w:=c+1利用Bernstein条件判定R(S1)=x,yR(S2)=zR(S3)=a,bR(S4)=cW(S1)=aW(S2)=bW(S3)=cW(S4)=w容易判定S1与S2可并发执行，而S1与S3、S2与S3、S3与S4不能并发执行。考虑S1与S4能不能并发执行？利用前趋图判定无前趋后继关系的两个节点可并发执行，如上图所示。,15,2.2 进程的描述,一、进程的定义与特征二、进程的基本状态三、进程的挂起状态四、进程控制块PCB,16,一、进程的定义与特征,1、进程的定义2、进程的特征,17,1、进程的定义,较典型的进程定义有：进程是程序的一次执行。进程是可以和别的计算并发执行的计算。进程可定义为一个数据结构及能在其上进行操作的一个程序。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，我们可以把传统OS中的进程理解为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。定义：可并发执行的程序在一个数据集合上的运行过程，或者说进程是进程实体的运行过程。,18,2、进程的特征,1)动态性2)并发性3)独立性4)异步性5)结构特征,19,二、进程的基本状态,1、进程的三种基本状态2、新状态和终止状态3、进程状态的转换,20,1、进程的三种基本状态,1)就绪(Ready)状态2)执行状态3)阻塞状态,21,2、新状态和终止状态,1)新(New)状态2)终止(Terminated)状态3)引入新状态和终止状态的原因,22,3、进程状态的转换,1)新就绪状态2)就绪执行状态3)执行阻塞状态4)执行就绪状态5)执行终止状态6)阻塞就绪状态,23,三、进程的挂起状态,1、引入挂起状态的原因2、进程状态的转换,24,1、引入挂起状态的原因,1)终端用户的请求。2)父进程请求。3)操作系统的需要。4)对换的需要。5)负荷调节的需要。,25,2、进程状态的转换,1)活动就绪静止就绪。2)活动阻塞静止阻塞。3)静止就绪活动就绪。4)静止阻塞活动阻塞。5)执行静止就绪。6)静止阻塞静止就绪。,26,四、进程控制块PCB,1、进程控制块的作用2、进程控制块中的信息3、进程控制块的组织方式,27,1、进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。进程控制块的作用：记录进程信息进程存在的唯一标志操作系统调度进程的数据结构,28,2、进程控制块中的信息,1)进程标识符2)处理机状态3)进程调度信息4)进程控制信息,29,1)进程标识符,进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。,30,2)处理机状态,处理机状态信息主要是由处理机的各种寄存器中的内容组成的：通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,31,3)进程调度信息,在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,32,4)进程控制信息,进程控制信息包括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,33,3、进程控制块的组织方式,1)链接方式2)索引方式,34,2.3 进程控制,一、操作系统内核二、进程的创建三、进程的终止四、进程的阻塞与唤醒五、进程的挂起与激活,35,处理机的执行状态,为防止操作系统及关键数据如PCB等受到用户程序有意或无意的破坏，通常将处理机的执行状态划分成系统态和用户态：系统态：又称核心态，具有较高的特权，能执行一切指令，可以访问所有寄存器和存储器。用户态：具有较低的执行权限，只能执行规定的指令，访问指定的寄存器和存储器。通常用户程序运行于用户态，OS内核运行于系统态。,36,一、操作系统内核,内核是计算机硬件的第一层扩充软件，为系统对进程控制、存储器管理等提供了有效的机制。内核常驻内存，紧靠硬件，运行效率较高。在不同操作系统中，内核所包含的功能不尽相同，但一般应包含下述功能：1、支撑功能2、资源管理功能,37,1、支撑功能,1)中断处理2)时钟管理3)原语操作原语是由若干条指令构成、用于完成一定功能的过程。与一般过程的区别在于原语是一种“原子操作(Atomic Operation)”。原子操作：一个操作中的所有动作，要么全做，要么全不做。即原子操作是一个不可分割的操作。,38,2、资源管理功能,1)进程管理2)存储器管理3)设备管理,39,二、进程的创建,1、进程图2、进程创建(Creation of Progress)过程3、引起创建进程的事件,40,1、进程图,进程图是用于描述进程家族关系的有向树。图中的节点代表进程。进程pi创建了进程pj后就成pi是pj的父进程(Parent Process)，pj是pi的子进程(Progeny Process)。用pi指向pj的有向边描述它们之间的父子关系。创建父进程的进程称为祖父进程，从而一个进程家族就形成了一棵进程树，其中根节点成为进程家族的祖先(Ancestor)。进程间的这种关系是非常有用处的：子进程继承父进程的资源。子进程被撤消时，要归还从父进程获得的资源。撤消一个进程时，必须同时/事先撤消其多有子孙进程。,41,2、进程创建过程,1)申请空白PCB。2)为新进程分配资源。3)初始化进程控制块。初始化标志符信息初始化处理机状态信息初始化处理机控制信息4)将新进程插入就绪队列如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。,42,3、引起创建进程的事件,1)用户登录。2)作业调度。3)提供服务。4)应用请求。,43,三、进程的终止,1、进程终止(Termination of Process)的过程2、引起进程终止的事件,44,1、进程终止的过程,1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,45,2、引起进程终止的事件,1)正常结束：在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。2)异常结束：在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：越界错误。这是指程序所访问的存储区，已越出该进程的区域；保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；特权指令错。用户进程试图去执行一条只允许OS执行的指令；运行超时。进程的执行时间超过了指定的最大值；等待超时。进程等待某事件的时间，超过了规定的最大值；算术运算错。进程试图去执行一个被禁止的运算，例如，被0除；I/O故障。这是指在I/O过程中发生了错误等。3)外界干预：外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；父进程请求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；父进程终止。当父进程终止时，OS也将他的所有子孙进程终止。,46,四、进程的阻塞与唤醒,1、进程阻塞过程2、进程唤醒过程3、引起进程阻塞和唤醒的事件,47,1、进程阻塞过程,正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。,48,2、进程唤醒过程,当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。,49,3、引起进程阻塞和唤醒的事件,1)请求系统服务2)启动某种操作3)新数据尚未到达4)无新工作可做,50,五、进程的挂起与激活,1、进程的挂起2、进程的激活过程,51,1、进程的挂起,当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。,52,2、进程的激活过程,当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。,53,2.4 线程的基本概念,一、线程的基本概念二、线程间的同步和通信三、内核级线程和用户级线程四、线程控制,54,一、线程的基本概念,1、线程的引入2、线程的属性3、线程的状态4、线程的创建和终止5、多线程OS中的进程,55,1、线程的引入,为使程序能并发执行，系统还必须进行以下的一系列操作。1)创建进程2)撤消进程3)进程切换,56,2、线程的属性,1)轻型实体。2)独立调度和分派的基本单位。3)可并发执行。4)共享进程资源。,57,3、线程的状态,1)状态参数在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项：寄存器状态，它包括程序计数器PC和堆栈指针中的内容；堆栈，在堆栈中通常保存有局部变量和返回地址；线程运行状态，用于描述线程正处于何种运行状态；优先级，描述线程执行的优先程度；线程专有存储器，用于保存线程自己的局部变量拷贝；信号屏蔽，即对某些信号加以屏蔽。2)线程运行状态如同传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。相应地，线程在运行时，也具有下述三种基本状态：执行状态，表示线程正获得处理机而运行；就绪状态，指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。,58,4、线程的创建和终止,在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后使用。终止线程的方式有两种：一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。,59,5、多线程OS中的进程,在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：1)作为系统资源分配的单位。2)可包括多个线程。3)进程不是一个可执行的实体。,60,6、线程与进程的比较,1、调度2、并发行3、拥有资源4、系统开销,61,二、线程间的同步和通信,1、互斥锁(mutex)2、条件变量3、信号量机制,62,1、互斥锁,互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。由于操作互斥锁的时间和空间开锁都较低，因而较适合于高频度使用的关键共享数据和程序段。互斥锁可以有两种状态，即开锁(unlock)和关锁(lock)状态。相应地，可用两条命令(函数)对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。,63,2、条件变量,每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着一个条件变量。单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待，直至所等待的资源成为可用的。线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。只要发现所需资源R正处于忙碌状态，线程便转为等待状态，并对mutex执行开锁操作后，等待该资源被释放；若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。,64,3、信号量机制,1)私用信号量(private samephore)当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使它恢复为0(空)，也不能将它传送给下一个请求它的线程。2)公用信号量(public semaphort)公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。由于它有着一个公开的名字供所有的进程使用，故而把它称为公用信号量。其数据结构是存放在受保护的系统存储区中，由OS为它分配空间并进行管理，故也称为系统信号量。如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收，并通知下一进程。可见，公用信号量是一种比较安全的同步机制。,65,三、内核级线程和用户级线程,1、内核支持线程2、用户级线程3、内核支持线程与用户级线程的比较,66,1、内核支持线程,这里所谓的内核支持线程，也都同样是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。此外，在内核空间还为每一个内核支持线程设置了一个线程控制块，内核是根据该控制块而感知某线程的存在的，并对其加以控制。,67,2、用户级线程,用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单，因而使线程的切换速度特别快。可见，这种线程是与内核无关的。,68,3、内核支持线程与用户级线程的比较,1)线程的调度与切换速度2)系统调用3)线程执行时间,69,四、线程控制,1、内核支持线程的实现2、用户级线程的实现,70,1、内核支持线程的实现,任务数据区空间,71,2、用户级线程的实现,1)运行时系统(Runtime System)所谓“运行时系统”，实质上是用于管理和控制线程的函数(过程)的集合，其中包括用于创建和撤消线程的函数、线程同步和通信的函数以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。2)内核控制线程这种线程又称为轻型进程LWP(Light Weight Process)。每一个进程都可拥有多个LWP，同用户级线程一样，每个LWP都有自己的数据结构(如TCB)，其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。它们也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务，这样，当一个用户级线程运行时，只要将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。上图是利用轻型进程作为中间系统的示例。,72,本章小结,自学并了解“2.6 OS/2操作系统中进程的描述与控制”一节内容。复习本章内容，找出P60课后练习题答案，其中尤其注意1、3、8、16四个小题参考：http:/,73,