第4章 进程及进程管理

1、1 / 71第4章 进程及进程管理4.1 并发活动进程的引入4.2 进程概念4.3 进程控制4.4 进程的相互制约关系4.5 进程互斥4.6 信号灯和、V操作4.7 进程同步4.8 进程通信4.9 线程2 / 714.1.1 程序的顺序执行（一）数据、操作数据：用来表现人们思维对象的抽象概念的物理表现操作：数据处理的规则。3 / 71（二）什么是程序的顺序执行（二）什么是程序的顺序执行程序的顺序执行程序的顺序执行：4 / 71I1 I2C2C1P1P2作业1作业2图4.1 程序段的顺序执行5 / 711、顺序性：2、封闭性：3、可再现性： （三）顺序程序的特点6 / 714.1.24.1.2程

2、序的并发执行程序的并发执行并发环境：并发环境： 在一定时间内物理机器上有两个或在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事尚未结束的状态，并且次序不是事先确定的。先确定的。7 / 71引入并发的目的：引入并发的目的： 并发程序：并发程序：8 / 71图4.2 并行计算的先后次序I1I2I3I4C1C2C3P1P29 / 71例：例：图4.2 10 / 71图 4.311 / 71并发执行的算法表示：1、语句表示 s0 ; cobegin S1; S2; ; Sn coend; sn+1; 12 / 712.流程图表示。

3、s0s1s2SnSn+113 / 71例4.1 假设一个飞机订票系统有两个终端，分别运行进程T1和T2且同处于运行之中，其程序如下(类C代码）其运行情况如图3.1所示。T1( ) T2( ) while(未下班） while(未下班） read(x); read(x); if x=1 if x=1 x-; x-; write(x); write(x); Main( ) Cobegin T1( ); T2( ); Coend int x;图4.44.1.3并发执行的例子14 / 71时间时间 t0t1t2t3t4t5X 1 1 0 0 0 0T1read(x)x- -write(x) T2 re

4、ad(x)write(x)(a)时间时间 t0t1t2t3t4t5X 1 1 1 0 0 0T1read(x) x- - write(x) T2 read(x) x- - write(x)(b)15 / 71结果分析： 按照(a)的序列执行时，系统中仅有的一张票售给了一位旅客，这是正确的。 按照(b)的序列执行时，尽管T1和T2均无非法操作，但却把一张票售给了两位旅客。 在(b)情况下发生的错误，称为 与时间有关的错误。16 / 71特征：（1）失去程序的封闭性（2）程序和计算不再一一对应（3）程序并发执行时存在相互制约关系17 / 714.2 进程概念4.2.1 进程的引入和定义程序的顺序执

5、行、程序的并发执行特征比较程序的顺序执行 程序的并发执行1 顺序性 1 间断性2 封闭性 2 失去封闭性3可再现性 3 不可再现性18 / 7119 / 714.2.1 进程的引入 程序并发执行时所产生的一系列新的特点是传统的静态的“程序”的概念，已不足以描述程序的并发执行，为此引入了“进程”的概念。 进程的定义： 一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。20 / 71定义：定义：ProcessProcess 进程是具有独立功能的程序关于进程是具有独立功能的程序关于某个数据集合上的一次运行活动，某个数据集合上的一次运行活动，是系统进行资源分配和是系统进行资源分配和调度调度

6、的独立的独立单位单位2 2、进程的定义、进程的定义21 / 7122 / 7123 / 71系统进程系统进程用户进程用户进程（系统进程优先于用户进程（系统进程优先于用户进程) )进程的分类进程的分类: :24 / 714.2.3 进程的状态图图4.8 4.8 进程状态变迁图进程状态变迁图25 / 71进程状态变迁（1）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。（2）阻塞状态：进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。（3）就

7、绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入运行。26 / 71状态变迁的方向：（1）就绪状态变化到运行状态 。（2）运行状态变化到就绪状态。 （3）运行状态变化到阻塞状态。 （4）阻塞状态变化到就绪状态。 27 / 714.2.4 进程控制块 为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成，如图4.9（a）所示。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系

8、统时（运行），进程控制块就标识了这个进程。如图4.9（b）所示。 28 / 7129 / 71（1）进程标识符： 进程符号名或内部id号。（2）进程当前状态： 本进程目前处于何种状态（运行、就绪、等待）。（3）当前队列指针next： 该项登记了处于同一状态的下一个进程的pcb地址。（4）总链队列指针all_q_next： 该项登记了在系统总链队列中，下一个进程的pcb地址。（5）程序开始地址： 该进程的程序将从此地址开始执行。（6）进程优先级： 反映了进程要求CPU的紧迫程度。（7）CPU现场保护区： 当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中。（8）通信信息： 进

9、程间进行通信时所记录的有关信息。（9）家族联系： 指明本进程与家族的联系。（10）占有资源清单30 / 71运行就绪等待时间片到进程调度进程创建进程阻塞进程撤消31 / 7131all_q _nextnextnextnextPCBPCBPCBall_q _next总链队列结构32 / 71进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。 进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。进程控制块的作用：进程控制块的作用：33 / 71

10、4.3 进程控制 4.3.1 进程控制的概念 4.3.2 进程创建4.3.3 进程撤消4.3.4 进程等待4.3.5 进程唤醒4.3.6 进程延迟 34 / 714.3.1 进程控制的概念一、原语在操作系统中，某些被进程调用的操作，例如队列操作、对锁的操作、检查启动外设操作等，一旦开始执行就不能被中断，否则就会出现“与时间有关的错误”（如例4.1）。原语就是为实现这些操作而设置的。原语是一种特殊的系统调用命令，它可以完成一个特定的功能。其特点是原语执行时不可中断，所以原语操作具有原子性，它是不可再分的。35 / 71用于进程控制的原语用于进程控制的原语1创建原语2撤消原语3阻塞原语4唤醒原语3

11、6 / 714.3.2 进程创建MODULE 4.5 进程创建Creat(name,priority,start-addr) 在总链队列上查找有无同名的进程； if (有同名进程）return (错误码）； 从pcb资源池申请一个空闲的pcb结构； if （无空pcb结构） return(错误码）； 用入口参数设置pcb内容； 置进程为“就绪”态； 将新进程的pcb入就绪队列； 将新进程的pcb入总链队列； return(新进程的pid); 37 / 714.3.3 进程撤消MODULE 4.6 进程撤消kill( ) 由运行指针得当前进程的pid;释放本进程所占用得资源给父进程； 该进程从总

12、链队列中摘除；释放此pcb结构；转进程调度程序； 用途：进程完成任务后撤消自己。38 / 714.3.4 进程等待Susp(进程等待的原因） 保护现行进程的CPU现场到pcb结构中；置该进程为“等待”态；将该进程pcb插入到指定等待队列中去；转进程调度； 用途：当进程需要等待某一事件完成时，它可以调用等待原语把自己挂起。39 / 714.3.5 进程唤醒MODULE 4.8 进程唤醒Wakeup(等待原因） 保护现行进程的CPU现场；置该进程为“就绪”态；将该进程入就绪队列；找到该等待队列原因的队列指针；for(该队列上第一个等待的进程） 将该进程移出此等待队列；置该进程状态为“就绪”；将该进

13、程入就绪队列；转进程调度； 用途：进程所等待的事件出现时，由发现者（合作者）用唤醒 原语唤醒它。40 / 714.4 进程的相互制约关系4.4.1 资源共享共享资源的方式由系统统一分配由程序自行使用由系统提供同步协调工具4.4.2 进程合作合作的方法进程通信41 / 714.5 进程互斥4.5.1 互斥的概念同步：对进程操作的时间顺序所加的某种限制。互斥：同步的一种，多个操作决不能在同一时 刻执行。进程互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥42 / 71临界资源：一次仅允许一个进程使用的公共资源。即: 并发进程对其操作会使其状态发

14、生改变的公共资源。临界区/临界段：进程中对公共变量（或存储区）进行修改的程序段。即：在进程中涉及到临界资源的程序段叫临界区。 多个进程的相对于某一个临界资源的临界区称为相关临界区 （参看教材P79图4.13）43 / 71同步准则：1、每次至多有一个进程处于临界区。2、进程在临界区内仅逗留有限的时间3、当有若干进程欲进入它的临界区时，应在有限时间内使进程进入临界区。换言之，它们不应相互阻塞而致使彼此都不能进入临界区。44 / 714.5.2 锁和上锁、开锁操作 1 闭锁变量 W= 0 开上锁原语： 开锁原语： lock(w) unlock(W) test: if (w为1） goto test

15、; W=0; else w=1; 45 / 714.5.3 用上锁原语和开锁原语实现进程互斥MODULE 4.14 进程互斥 main()ppa() ppb() int w=0; cobegin lock(w); lock(w); ppa(); csa ; csb ; PPB(); unlock(w); unlock(w); coend 46 / 71思考题：1. 前述飞机订票系统例子中的“与时间有关的错误如何解决？47 / 714.6. 信号灯和P、V操作4.6.1 信号灯的概念信号灯的概念 信号灯是铁路交通管理中的一种常用设备，操作系统中使用的信号灯正是从交通管理中引用过来的一个术语。 信

16、号灯是一个确定的二元组（s, q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的等待队列的头指针。整型变量S代表资源的实体或并发进程的状态，它的值可以改变，以反映资源或并发进程状态的改变。为了对信号等的值进行修改，一般采用称为P、V操作的一对原语来进行。 S的物理含义为： S 0 时的值是其所代表的资源的可用数目。 S 0 时的绝对值是等待使用资源的进程数目。48 / 71P、V操作：信号灯的初值仅能由P、V操作原语加以改变。对信号灯的P、V操作分别记为p(s)、v(s),其功能如下：p(s)v(s) s-; s+; if (s0) if (sp(s)，释放资源-v(s)6.同一信号

17、量的P 、V 操作要成对出现，除“互斥”情 况外，它们一般分别出现在不同的进程代码中7. 写出类C代码8. 校验：对同一信号量的p、v操作是否同样多？ 各进程同步？ 53 / 71MODULE 4.18 Main() int s1=0; /* 化验单*/ int s2=0; /* 化验结果*/ cobegin diagnosis()labora(); while (未下班）diagnosis(); 看病； coend v(s1); p(s2);Labora() 开药方； while (未下班） p(s1); 化验； v(s2); 54 / 71一、合作进程的执行次序图的连接描述了进程间开始和结

18、束的次序约束，此图称为进程流图。sfs P2fP1P1 P2 P2P3 P3 P4 P455 / 71例：Pa、Pb、Pc为一组合作进程，其进程流图如图4.16所示。使用信号灯的P、V操作实现这三个进程的同步。PaPbPc解1：main() int S = 0; /*Pa 结束否*/ cobegin Pa( ) Pb( ) Pc( ) Pa( ); P(s); P(s)Pb( ); v(s); Pc( ); coend 问：此种解法对吗？56 / 71解2：main() int Sb = 0; /*Pb可开始否*/ int Sc = 0; /*Pc可开始否*/ cobegin Pa( ) Pb

19、( ) Pc( ) Pa( ); P(Sb); P(Sc);Pb( ); v(Sb); Pc( ); v(Sc) coend 57 / 71二、共享缓冲区的同步CPIOPbuf58 / 71MODULE 4.20Main( ) int Sa = 0; /* buf中的数据*/int Sb = 1; /* buf 中的空位置*/cobeginCP( ); IOP( ); coend CP( ) while(未完成) 计算出一个数据；P(Sb); 将数送到缓冲区中； V(Sa); IOP( ) while(未完成) P(Sa); 从缓冲区中取一数； V(Sb); 从打印机上输出； 59 / 711

20、生产者与消费者问题 Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个有界缓冲区（见图4.8）联系起来，有界缓冲区由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲区中送一个生产产品，而每个消费者则可不断地每次从缓冲区中取出一个产品。 60 / 71.P1p2p3PmC1C2Ck图图4.18 4.18 生产者生产者- -消费者问题消费者问题61 / 71下面给出基于有界缓冲区的生产者与消费者关

21、系的形式描述，设：（1）互斥信号灯mutex：初值为1，用于实现临界区互斥。（2）信号灯empty：初值为n，指示空缓冲块数目。（3）信号灯full：初值为0，指示满缓冲块数目。（4）整型量i和j初值均为0，i指示第一块空缓冲块序号，j指示第一块满缓冲块序号。v其同步算法设计如下： 62 / 71main() int full=0; /*满缓冲的数目*/ int empty=n; /*空缓冲的数目*/ int mutex = 1; /*对有界缓冲区进行操作的互斥信号灯*/ cobegin producer(); consumer(); coend生产者消费者问题63 / 71生产者消费者问题（

22、续）Producer( ) consumer( ) while(生产未完成） while(还要消费） p(full);生产一个产品； p(mutex); p(empty); 从缓冲区中取产品； p(mutex); v(mutex); 送一个产品到缓冲区； v(empty); v(mutex); v(full); 消费一个产品； 64 / 71例 题用PV操作解决下面问题：司机进程：Repeat启动车辆；正常行驶；到站停车；Until 售票员进程：Repeat关门；售票；开门；Until 65 / 7165同步要求：先关门，后开车；同步要求：先关门，后开车； 先停车，后开门；先停车，后开门；信号

23、灯：信号灯：S_Door, 初值为初值为0 S_Stop, 初值为初值为0司机进程：司机进程：Begin RepeatP(S_Door);启动；启动；驾驶；驾驶；停车；停车；V(S_Stop); Until false;End售票员进程：售票员进程：Begin Repeat关门；关门；V(S_Door);售票；售票；P(S_Door);开门；开门； Until false；End66 / 7166补充题：有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的；若有读者正在读，编辑就不能工作；若编辑正在处理，读者就不能读，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作描述读者与编辑

24、之间协同工作，并给出类C程序。67 / 7167main（）（） int mutex=1，couter=0； cobegin readi（）；（）；(i=1-10) editerj（）；（）；(j=1,2) coend readi() if(couter = = 0) p(mutex); couter +; 读文章；读文章； couter -; if(couter = 0) v(mutex); editerj() p(mutex); 处理文章处理文章; v(mutex); mutexmutex：互斥信：互斥信号灯，初值为号灯，初值为1 1。一种解法，一种解法，正确吗？正确吗？68 / 71读者

25、、编辑问题正解mutex:用于读者与编辑、编辑与编辑的互斥信号灯，初值为1mutex1:用于对couter操作的互斥的信号灯，初值为1。6869 / 7169main（）（） int mutex1= mutex=1， couter=0； cobegin readi（）；（）； editeri（）；（）； coend readi() p(mutex1); couter +; if (couter = = 1) p(mutex); v(mutex1); 读文章；读文章； p(mutex1); couter -; if (couter = 0) v(mutex); v(mutex1); editj(

26、) p(mutex); 处理文章处理文章; v(mutex); 70 / 71(六)线程的基本概念在OS中，进程的引入提高了系统资源的利用率。进一步提高进程的并发性时产生问题：n进程切换开销越来越大n进程间通信效率受限n多处理机系统调度71 / 71在只有进程概念的操作系统中进程是：系统资源分配的单位处理器调度的对象在引入线程的操作系统中：n线程是处理机调度的对象；n进程是系统资源的分配单位；n一个进程可同时具有多个线程。72 / 71(六)线程的基本概念1. 什么是线程线程是比进程更小的活动单位，它是进程中的一个执行路径。线程可以这样来描述：n进程中的一条执行路径；n它有自己私用的堆栈和处理

27、机执行环境；n它与父进程共享分配给父进程的主存；n它是单个进程所创建的许多个同时存在的线程中的一个。73 / 712. 线程的特点n创建一个线程比创建一个进程开销要小得多。n线程（Thread）是一个动态的对象，是处理机调度的基本单位，表示一个进程中的一个控制点，执行一系列的指令。n实现线程间通信十分方便，因为一个进程创建的多个线程可以访问整个进程的所有资源，包括共享地址区域和数据，因此，线程间通信比较简单方便。n在进程内创建多线程，可以提高系统的并行处理能力，加快进程的处理速度。n同一个进程中线程切换简单。进程中所有线程是共享一个进程图像的。74 / 71单进单进程程单进单进程程多线多线程程

28、多进程多进程 单线程单线程每个进程只有一个线每个进程只有一个线程程多进程多进程 多线程多线程每个进程只有多个线每个进程只有多个线程程75 / 71线程的实现机制内核线程（内核线程（Kernel-Level Thread）n在OS内核完成创建、撤消、执行一个指定的函数线程。n在支持内核线程OS中，内核维护进程和线程上下文，线程切换由内核完成。处理机分配对象是线程。某个线程因中断阻塞不影响其它线程的执行。n多线程的进程可获得更多的处理机时间。Windows Server 2003支支持内核线程。持内核线程。用户线程用户线程（User-Level Thread）n不依赖OS核心，由应用进程利用线程库

29、提供创建、同步、调度和管理线程。n由于不需要操作系统支持，任何操作系统都可以支持。甚至单用户操作系统。76 / 71线程实现的机制 轻量级进程轻量级进程（Light weight process） 由内核支持的用户线程。一个进程可有一个或多个轻量级进程。每个轻量级进程由一个单独的内核线程来支持。由于同时提供内核线程控制机制和用户线程库，可以很好地把内核线程和用户线程的优点结合起来。77 / 71概述概述消息缓冲通信方式消息缓冲通信方式4.7.4 4.7.4 进程通信进程通信78 / 711 1、概述、概述 P.V P.V操作实现的是进程之间的低级通讯，所以操作实现的是进程之间的低级通讯，所以P.VP.V为为低级通讯原语。它只能传递简单的信号，不能传递交低级通讯原语。它只能传递简单的信号，不能传递交换大量信息换大量信息如果要在进程间传递大量信息则要用如果要在进程间传递大量信息则要用 Send / Receive Send / Receive原语（高级通讯原语）原语（高级通讯原语）79 / 71共享内存共享内存： 相互通信的进程间设有公共相互通信的进程间设有公共内存，一组进程向该公共内存中写，另内存，一组进程向该公共内存中写，另一组进