chapter2-1new第二章

第二章进程管理(1),东北师范大学计算机学院,1,第二章进程管理（1）,2.1进程的概念和PCB2.2进程控制2.3线程,东北师范大学计算机学院,2,2.1进程的基本概念,2.1.1程序的顺序执行及其特征2.1.2前驱图2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块（PCB）,东北师范大学计算机学院,3,2.1.1程序的顺序执行及特征,1.基本概念程序：一个在时间上按严格次序、顺序执行的操作序列。程序的顺序执行：一个具有独立功能的程序独占处理机，直至得到最终结果的过程。操作：数据处理的一种规则，一经启动就需要在有限时间内完成。计算：若干操作严格顺序执行的集合。,东北师范大学计算机学院,4,2.程序的顺序执行,在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。通常一个程序可分成若干个程序段，它们必须按照某种先后次序执行，仅当前一操作执行后，才能执行后继操作。例如：进行计算。I:输入操作C:计算操作P:打印操作。在进行计算时，总是先输入用户的程序和数据，然后进行计算，最后将结果打印出来。,东北师范大学计算机学院,5,3.语句的顺序执行,S1：a:=x+yS2：b:=a-5S3：c:=b+1如下图，语句S2必须在a被赋值后才能执行；S3也只能在b被赋值后才能执行。,东北师范大学计算机学院,6,4.程序的顺序执行的特征,顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行；封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源；可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。程序顺序执行的特性，为程序员检测和校正程序的错误带来很大方便。,东北师范大学计算机学院,7,2.1.2.前趋图,为了描述一个程序的各部分(程序段或语句)间的依赖关系，或者是一个大的计算的各个子任务间的因果关系，我们常常采用前趋图方式。,图2-1九个结点的前趋图,东北师范大学计算机学院,8,前趋图（续）,P1为初始结点，P9为终止结点每个结点还具有一个重量。该前趋图，存在下面的前趋关系：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),东北师范大学计算机学院,9,前趋图（续）,前趋图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个结点之间存在的偏序(Partial_Order)或前趋关系(Precedence_Relation)“”(Pi,Pj)|在Pj开始前Pi必须完成如果(Pi,Pj)，可写成PiPj，Pi是Pj的直接前趋，Pj是Pi的直接后继。前趋图中必须不存在循环，如下图不是前趋图。,东北师范大学计算机学院,10,2.1.3程序并发执行及特征,1.并发环境：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的,东北师范大学计算机学院,11,东北师范大学计算机学院,12,BeginintergerN:N:=0;CobeginprogramA:beginL1:programA;N:=N+1;gotoL1endprogramB:beginL2:programB;print(N);N:=0;gotoL2endCoendend,例子：,2.程序的并发执行,在对一批程序进行处理时，可以并发执行。例如，输入、计算、打印三个程序对一批作业进行处理时，存在以下的前趋关系：IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1,图2-2并发执行时的前趋图,东北师范大学计算机学院,13,在上例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b,图2-3四条语句的前趋关系,东北师范大学计算机学院,14,15,Bernstein条件（1966年两相邻语句可以并发执行的条件）程序并发执行时出现的“与时间有关的错误”时绝对不允许的，为此，应采取某种措施使并发程序的执行保持其“可再现性”。只有满足下列条件，才允许并发执行，否则按序进行。,首先，定义一些符号,R(Si)=a1,a2,am,aj(j=1,m),表示程序Si在执行程序其间所需引用的变量的集合，称为“读集”,W(Si)=b1,b2,bm,bj(j=1,m),表示程序Si在执行程序其间要改变的所有变量的集合，称为“写集”,若有两条语句P1：Ci=a-bP2：Wi=c+1,则它们的读写集分别为R(P1)=a,bR(P2)=cW(P1)=cW(P2)=w,R(P1)W(P1)=R(P2)W(P2)=,16,读集与写集的交集，也可能不是空集P：X：=X+1R（P）=XW（P）=XR（P）W（P）=X结论:若两个程序P1和P2能满足下述条件，它们便能并发执行，否则不能R（P1）W（P2）R（P2）W（P1）W（P1）W（P2）=上面提到的有如下四条语句S1：a=x+yR(S1)=x,yW(S1)=aS2：b=z+1R(S2)=zW(S2)=bS3：c=a-bR(S3)=a,bW(S3)=cS4：w=c+1R(S4)=cW(S4)=wS1与S2满足Bernstein条件，可并行执行，数据无关*S1与S3S2与S3S3与S4，不能并发执行,四个节点的前趋图,S1,S2,S3,S4,3.程序的并发执行的特征,间断性：程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约。失去封闭性：程序在并发执行时，多个程序共享系统中的各种资源，这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。不可再现性：由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性。通信性：对于相互合作的程序，为了更有效地协调运行，相互之间进行通信。独立性：并发程序在运行过程中，既然是作为一个独立的运行实体，它也必然具有作为一个单位去获得资源的独立性。,东北师范大学计算机学院,17,4.多道程序设计,定义：Multiprogramming多道程序设计是指允许多个程序同时进入内存并运行（引入目的是为了提高系统效率）与并发不完全是一个概念，但效果相似考虑因素：在多道程序环境下如何向用户提供服务在并发程序之间如何正确传递消息（通讯）如何对CPU进行调度，保证每个用户相对公平地得到CPU如何管理其他资源当各用户对资源使用上发生冲突时，如何处理竞争对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请分配使用回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候,东北师范大学计算机学院,18,2.1.4进程的特征与状态,1.进程的概念进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位进程是可与其他程序并发执行的程序，在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。,东北师范大学计算机学院,19,2.进程的特征,动态性：进程的实质是程序的一次执行过程，进程是动态产生，动态消亡的，进程在其生命周期内，在三种基本状态之间转换并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。任何进程都可以同其他进程一起向前推进独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进结构特征：为了控制和管理进程，系统为每个进程设立一个进程控制块PCB。进程实体：程序段、相关数据段和PCB。所说的进程实际上指进程实体。,东北师范大学计算机学院,20,3.进程与程序的区别,程序是静态的，进程是动态的;进程更能真实地描述并发,而程序不能;一个程序可对应多个进程，反之亦然;进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的;程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的；进程是系统分配调度的独立单位，能与其他进程并发执行;进程是由程序和数据两部分组成的进程具有创建其他进程的功能，而程序没有,东北师范大学计算机学院,21,4.进程创建与中止,1）进程何时创建提交一个批处理作业用户登录由OS创建，用以向一用户提供服务(如：打印文件)由已存在的一进程创建一个用户程序可创建成多个进程进程何时中止批处理作业发出暂停（Halt）指令用户退出登录进程执行一中止服务请求出错及失败因素,东北师范大学计算机学院,22,5.进程中止的原因,正常结束给定时限到缺少内存存储器出界保护性出错：例子:写只读文件算术错超出时间：进程等待超过对某事件的最大值I/O失败无效指令：如试图执行数据特权指令操作系统干预：如当死锁发生时父进程请求中止某一子进程父进程中止，所以子进程也中止,东北师范大学计算机学院,23,6.进程状态,1）进程的三种基本状态（进程执行时的间断性）当进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。已获得CPU的进程进入执行状态。正在执行的进程，由于发生某个事件而暂时无法执行时，便放弃处理机而进入阻塞状态。由于执行的进程变为阻塞状态后，调度程序立即把处理机分配给另一个就绪进程；因此，阻塞进程的事件消失后，进程不会立即恢复到执行状态，而转变为就绪状态，重新等待处理机。,东北师范大学计算机学院,24,运行,就绪,等待,图24进程的状态及其转换,东北师范大学计算机学院,25,2）进程状态转换条件,在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：就绪-运行调度程序选择一个新的进程运行运行-就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态,东北师范大学计算机学院,26,进程状态转换条件（续）,运行-等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入(IPC)等待-就绪当所等待的事件发生时,东北师范大学计算机学院,27,创建状态终止状态挂起状态（调节负载，对换，父进程，操作系统，终端用户）,3）其他状态,东北师范大学计算机学院,28,创建(新new)状态,OS已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格但还没有允许执行该进程(尚未同意)因为资源有限,东北师范大学计算机学院,29,终止（退出exit)状态,中止后进程移入该状态它不再有执行资格表格和其它信息暂时由辅助程序保留例子:为处理用户帐单而累计资源使用情况的财务程序当数据不再需要后，进程(和它的表格)被删除,东北师范大学计算机学院,30,4）具有挂起操作的进程状态转换图,有的系统有时希望能人为地把进程挂起，使之处于静止状态，以便研究其执行情况或对它进行修改。下图示出了具有挂起状态的进程状态演变图。,图25具有挂起状态的进程状态演变图,东北师范大学计算机学院,31,五状态进程模型,准备退出：父进程可中止子进程,东北师范大学计算机学院,32,七状态进程模型,东北师范大学计算机学院,33,5）新状态转换(中期调度),阻塞-阻塞挂起当所有进程都阻塞，OS会安排空间让一就绪进程进入内存阻塞挂起-就绪挂起当等待的事件发生时(状态信息已在OS中)就绪挂起-就绪当内存中没有就绪进程时就绪-就绪挂起(较少见)当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时,东北师范大学计算机学院,34,2.1.5进程控制块（PCB）,系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,东北师范大学计算机学院,35,1进程控制块的内容,进程标识符：标识一个进程的编号，也称为进程的内部名；现性状态：说明进程的当前状态；现场保留区：保存进程由执行状态变为其它状态时的CPU现场信息；程序与数据地址：该进程的程序和数据所在位置信息；互斥与同步机构：实现进程间互斥与同步时所必须的机构；,东北师范大学计算机学院,36,进程控制块的内容（续）,进程通信机制：用于实现进程间的通信所需的数据结构；优先级：表示进程使用CPU时优先级别的一个整数；资源清单：列出进程拥有的资源的记录；连接字：给出本进程所在队列中的下一个进程的PCB首址；家族联系：用于说明本进程与其它家族成员间的关系。,东北师范大学计算机学院,37,2进程映象(进程要素),用户程序用户数据栈用于过程调用和参数传递进程控制块PCB(执行上下文)控制进程所需的数据(进程属性)，包括:进程标识符信息处理器状态信息进程控制信息,东北师范大学计算机学院,38,东北师范大学计算机学院,39,3进程控制块的组织方式,为了有效地对进程控制块进行管理，应该采用适当的方式把它们组织起来。目前常用的组织方式有以下两种：按链接方式组织PCB(队列)不同状态进程分别组成队列运行队列、就绪队列、等待队列按索引方式组织PCB(表)对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址（其他方式：线性表或链表）,东北师范大学计算机学院,40,按索引方式组织PCB,东北师范大学计算机学院,41,按链接方式组织PCB,东北师范大学计算机学院,42,东北师范大学计算机学院,43,2.2进程控制,1.进程控制的主要任务进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。,东北师范大学计算机学院,44,2.进程图,进程图是一棵有向树(如下图)，结点代表进程。一棵树表示一个家族，根结点为该家族的祖先(Ancestor)。,东北师范大学计算机学院,45,3.进程图和前趋图之间的差异,前趋图描述的是任务(或进程)之间的前趋关系；只有在前趋进程完成后，其后继进程才能运行；在进程图中，创建者和被创建者可以并发执行，也可以父进程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要。,东北师范大学计算机学院,46,4.内核与原语,内核：加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建、撤消、进程通信、资源管理的功能。内核的基本功能支撑功能：中断处理、时钟管理、原语操作资源管理功能：进程管理、存贮管理、设备管理原语：是由若干条机器指令所构成，用以完成特定功能的一段程序。,东北师范大学计算机学院,47,5.进程控制,创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活原语,东北师范大学计算机学院,48,1)创建原语,功能：创建一个具有指定标识符进程入口信息：进程标识符、优先级、进程开始地址、初始CPU状态、资源清单等。,东北师范大学计算机学院,49,进程创建过程,创建一个PCB赋予一个统一进程标识符为进程映象分配空间初始化进程控制块许多默认值(如:状态为New，无I/O设备或文件.)设置相应的链接如:把新进程加到就绪队列的链表中,东北师范大学计算机学院,50,创建原语的实现过程,东北师范大学计算机学院,51,2)进程的撤消原语,功能：撤消一个指定的进程入口信息：被撤消的进程名实现:收回进程所占有的资源,撤消该进程的PCB,东北师范大学计算机学院,52,引起撤消的原因,正常结束异常结束（越界错、保护错、特权指令错、非法指令、运行超时、I/O故障等）外界干预（操作员干预、父进程请父进程终止）,东北师范大学计算机学院,53,撤消原语的实现过程,东北师范大学计算机学院,54,3)进程阻塞,处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。,东北师范大学计算机学院,55,进程的阻塞原语,功能：停止调用进程的执行，变为等待。入口信息：可省阻塞原语的实现过程,东北师范大学计算机学院,56,4)进程的唤醒原语,功能：唤醒某一处于等待队列当中的进程。入口信息：被唤醒进程的名字引起唤醒的原因系统服务由不满足到满足I/O完成新数据到达进程提出新请求（服务）,东北师范大学计算机学院,57,唤醒原语的实现过程,东北师范大学计算机学院,58,5)进程的挂起与激活,挂起原语的功能：自身挂起、挂起具有指定标识符的进程、将其进程及其全部或部分“子孙”挂起。激活原语功能：使处于静止状态的进程变为活动。,东北师范大学计算机学院,59,6.系统核心,1)系统核心：向上提供多个无中断的虚拟机器在核心内不允许中断2)特点：为进程运行提供一个舞台核心常驻内存设计短小精焊,东北师范大学计算机学院,60,3)核心的组成,中断处理进程管理:调度控制通讯互斥同步等原语管理:在核心中提供一系列原语，同步,通信，创建，撤消等,东北师范大学计算机学院,61,4)队列管理,队列数据结构:指向队首的表指针三个队列:运行，就绪，等待队列排队方式:排队首排队尾插队出队方式:队首出队/队中出队队列管理:中断之后，进程调度之前,东北师范大学计算机学院,62,5)现场管理,保存现场;注意顺序,中断之后第一步恢复现场:恢复时机，进程调度最后一步时钟管理:以固定频率+1-1用途:进入绝对时钟间隔时钟进行分析比较,东北师范大学计算机学院,63,6)虚时钟,每个进程分配给一个虚时钟来记录CPU时间,这个时钟称为虚时钟。虚时钟存放在PCB中，属于现场的一部分，进程运行时，将虚时钟放入内存开辟的专门单元，离开CPU则放在PCB中。,东北师范大学计算机学院,64,东北师范大学计算机学院,65,核心处理流程:,东北师范大学计算机学院,66,7)内核的执行特点,由中断驱动的:中断内核退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令,东北师范大学计算机学院,67,思考题,1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个,最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待运行；就绪等待3.一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能4.举3个日常生活中类似进程的例子,东北师范大学计算机学院,68,第二章进程管理2.3线程,东北师范大学计算机学院,69,20世纪60年代提出了进程的概念，在OS中一直都是以进程作为能拥有资源和独立运行的基本单位。到了80年代，提出了比进程更小的能独立运行的基本单位线程（Threads）。提高系统内程序并发执行的程度，提高系统吞吐量。特别是90年代后，多处理机系统得到迅速发展，线程能比进程更好地提高程序的并行执行速度，充分地发挥多处理机的优越性。,东北师范大学计算机学院,70,东北师范大学计算机学院,71,引入进程的目的？,多个程序并发执行，改善资源利用率及提高系统效率,在OS系统中再引入线程？,减少程序并发执行时所付出的时间和空间开销，使操作系统具有更好的并发性,2.3线程,1.进程的两个基本属性：资源的拥有者：给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备等调度单位：进程是一个执行轨迹以上两个属性构成进程并发执行的基础,东北师范大学计算机学院,72,2.线程的引入,对进程系统必须完成的操作：创建进程撤消进程进程切换缺点：时间空间开销大，进程数目不宜过多，进程切换频率不宜过高，限制并发度的提高,东北师范大学计算机学院,73,线程的引入（续1）,在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度线程：有时称轻量级进程，进程中的一个运行实体，是一个CPU调度单位，资源的拥有者还是进程或称任务,东北师范大学计算机学院,74,线程的引入（续2）,线程：有执行状态（状态转换）不运行时保存上下文有一个执行栈有一些局部变量的静态存储可存取所在进程的内存和其他资源可以创建、撤消另一个线程,东北师范大学计算机学院,75,3.线程的特点,是进程的一个实体，可作为系统独立调度和分派的基本单位。不拥有系统资源（只拥有从属进程的全部资源，资源是分配给进程）一个进程中的多个线程可并发执行。（进程可创建线程执行同一程序的不同部分）系统开销小、切换快。（进程的多个线程都在进程的地址空间活动）,东北师范大学计算机学院,76,单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程,4.线程和进程的关系,东北师范大学计算机学院,77,东北师范大学计算机学院,78,东北师范大学计算机学院,79,5.引入线程的好处,创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少（如果机器设有“存储恢复所有寄存器”指令，则整个切换过程用几条指令即可完成）因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统,东北师范大学计算机学院,80,例子1：,LAN中的一个文件服务器，在一段时间内需要处理几个文件请求因此有效的方法是：为每一个请求创建一个线程在一个SMP机器上：多个线程可以同时在不同的处理器上运行,东北师范大学计算机学院,81,例子2：,一个线程显示菜单，并读入用户输入；另一个线程执行用户命令考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分可以以线程方式实现当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程,东北师范大学计算机学院,82,6.线程与进程的比较,调度：线程作为调度的基本单位，同进程中线程切换不引起进程，当不同进程的线程切换才引起进程切换；进程作为拥有资源的基本单位。并发性：一个进程间的多个线程可并发。拥有资源：线程仅拥有隶属进程的资源；进程是拥有资源的独立单位。系统开销：进程大；线程小。,东北师范大学计算机学院,83,7.线程的实现机制,用户级线程核心级线程两者结合方法,东北师范大学计算机学院,84,1)用户级线程（ULT）,由应用程序完成所