operation_system_第三章.ppt

1、1,第三章 进程管理,教学内容 *3.1 进程的基本概念 *3.2 进程的描述 *3.3 进程状态及其转换 *3.4 进程控制 *3.5 进程互斥与同步 *3.6 进程间通信 *3.7 线程的概念,2,3.1 进程的基本概念,一、进程的引入 1、程序的顺序执行与并发执行 单道系统中，一段时间内只有一个用户程序运行，我们把一个具有独立功能的程序独占CPU直至得到最终结果的过程称为程序的顺序执行。其特征如下： 1）顺序性 处理机操作严格按照程序所规定的顺序执行，每个动作的执行都以前一个动作的结尾为前提条件。即程序执行在时间上严格按前后相继的次序操作。 2）封闭性 程序执行的最终结果只由给定的初始条

2、件决定，不受外界因素的影响。程序独占资源，只有程序本身所规定的操作才能改变这些资源的状况。 3）可再现性 顺序执行的最终结果与程序运行的速度无关，无论何时执行程序，只要输入的初始条件相同，都能得到相同的结果，与执行过程是否停顿无关。,3,多道程序系统中，程序的并发执行是指在逻辑上相互独立的一组程序在执行时间上的相互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始。程序的并发执行具有与程序的顺序执行完全不同的特征。主要表现在： 1）并发执行的程序间相互约束性 并发执行的程序共享计算机的资源，所以本来并无逻辑关系的程序之间产生了相互制约的关系。而有些并发执行的程序需要相互通信共同协作完

3、成同一任务，程序间的相互依赖，相互制约的关系使并发执行的程序具有“执行暂停执行”的活动规律，相互穿插交替运行。 2）资源的争夺与共享 系统中的资源不再为单个程序所独占，而由若干道并发执行的程序所共享。资源需要动态分配，资源的状态是由多道程序的活动所共同决定的，程序的运行不再具有封闭性和可再现性，并发程序的执行结果与其执行的相对速度有关。,4,Int N=0; cobegin void program A(void) while(TRUE) N=N+1; void program B(void) while(TRUE) print(N); N=0; coend,;N=N+1;print(N);N

4、=0; 打印的N值为n+1,循环结束后N=0 ;print(N);N=0;N=N+1; 打印的N值为n,循环结束后N=1 ;print(N);N=N+1;N=0; 打印的N值为n,循环结束后N=0,5,从上述程序并发执行的特点可见，程序的概念已无法描述程序动态执行过程中的并发活动，故需要引入一个新的概念来描述，这就是进程。 2、进程概念 多种定义，如： 进程是程序的一次执行； 进程是可以和别的计算并发执行的计算； 进程可定义为一个数据结构，及能在其上进行操作的一个程序； 进程是一个程序及其数据，在处理机上顺序执行时所发生的活动； 进程是程序在一个数据集合上运行的进程，它是系统进行资源分配和调度

5、的一个独立单位。 综上，我们可以把进程定义为：“可并发执行的程序，系统进行资源分配和调度的一个独立单位”。,6,进程的特征,动态性 进程的实质是程序的一次执行过程，因此，动态特征是进程最重要的特征。还表现为它由“创建”而产生，由“调度”而执行，因得不到资源而暂停执行，最后由“撤销”而消亡。故进程有一定的生命周期。而程序只是指令的集合，本身无运动含义，所以程序是静态的。 并发性 没有为之建立进程的程序是不能并发执行的，仅当为之建立一个进程后才能参加并发执行。因此，并发性是进程的第二个特征。引入进程的目的正是为了使其程序能和其他程序并发执行。 独立性 进程是一个能独立运行的基本单位，同时也是系统分

6、配资源和调度的独立单位。进程在获得其所必须的一切资源后便可执行；因不能得到某资源时，便暂停执行。在具有并发活动的系统中，未建立进程的程序，不能作为一个独立单位而运行。,7,异步性 由于进程间的相互制约，使得进程具有执行的间断性。即进程按各自独立的、不可预知的速度向前推进。为此，系统必须提供某些设施，来保证程序之间能协调操作和共享资源。 结构特征 为了描述进程的运动变化过程，并使之能独立运行，应为每个进程配置一个进程控制块PCB。 这样从结构上看，每个进程都是由程序段、数据段以及进程控制块三个部分组成。,程序段,进程控制块,数据段 和 堆栈,8,引入进程的利弊：,引入进程是基于多道程序和分时系统

7、的需要，因为只有每道程序建立了进程之后，它们才能并发执行。 优点： 改善了系统的资源利用率和提高了系统的吞吐量。故在目前几乎所有微机中都引入了进程。 缺点： 空间开销增大。系统必须为每个进程建立PCB，它要占用几十到几百个内存单元；此外，为了协调诸进程的并发执行，系统还必须设置相应的进程管理机构，这些也必然占用可观的内存单元； 时间开销增大。为了协调诸进程的运行，也必须付出时间开销。如，进行进程切换时，系统必须保存正在运行进程的现场，为即将运行的进程设置新现场，都需要花费CPU时间。,9,进程控制块（PCB）,作用 为了描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块PCB（P

8、rocess Control Block）。 所谓系统创建一个进程，就是由系统为某个程序设置一个PCB，用于对该进程进行控制和管理。 进程任务完成，由系统收回其PCB，该进程便消亡。系统是根据某PCB而感知相应进程的存在，所以说：PCB是进程存在的唯一标志。,3.2 进程的描述,10,内容,PCB中包含了进程的描述信息、调度信息、上下文和控制信息。,11,PCB的组织方式 链接方式 把具有相同状态的PCB，用其中的链接字，链接成一个队列。对其中的就绪队列按进程优先级排列。,执行进程指针,就绪队列指针,阻塞队列指针,空闲队列指针,0,12,索引方式 系统根据所有进程的状态，建立几张索引表。并把各

9、索引表在内存的首地址记录于内存中的一些专用单元中。在索引表目中，记录具有相应状态的某个PCB在PCB表中的地址。,执行指针,就绪表指针,阻塞表指针,就绪索引表,阻塞索引表,13,3.3 进程的状态及转换,进程执行时的间断性，决定了进程具有多种状态 就绪状态 当进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。 执行状态 进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；多处理机系统中则有多个。 阻塞状态 正在执行的进程，由于发生某事件而暂时无法执行时，

10、便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，故把这种暂停状态称为阻塞状态，也称等待状态。通常将处于阻塞状态的进程也排成一个队列。,14,进程的三种基本状态及其转换,就绪,阻塞,执行,进程调度,I/O完成,I/O请求,注意：正当在执行的进程A变为阻塞状态后，调度程序立即把处理机分配给另一个就绪进程；当阻塞进程A的事件消失后，进程A不会立即恢复到执行状态，而是转变为就绪状态，重新获得处理机。,创建,撤消,时间片用完,15,挂起状态,人为的把正在执行或没有执行的进程挂起，使之处于静止状态。 对正在执行的进程暂停执行； 对就绪的进程暂时不接受调度； 对阻塞的进程，即使引起阻塞的事件消失，也不能

11、被调度。 目的：以便研究其执行情况或对它进行修改。 一个进程或者是活动的，或者是静止的（即被挂起），未被挂起的就绪状态和阻塞状态，分别称为活动就绪和活动阻塞；而被挂起的就绪和阻塞状态，则分别称为静止就绪和静止阻塞。,16,具有挂起操作的进程状态演变图,执行 状态,活动 阻塞,活动 就绪,调度,I/O请求,释放,静止 阻塞,静止 就绪,挂起,激活,释放,激活,挂起,挂起,时间片用完,17,3.4 进程控制,进程控制的主要任务是创建和撤销进程，以及实现进程的状态转换。进程控制一般是由操作系统的内核来实现的。 1、内核 1）什么是内核 现代操作系统广泛采用层次式结构。在进行层次式设置时，往往把一些与

12、硬件紧密相关的模块或运行频率较高的模块，以及为许多模块所公用的一些基本操作，安排在靠近硬件的层次中，并使它们常驻内存，以提高操作系统的运行效率，通常把这部分称为操作系统的内核。 内核是基于硬件的第一层软件扩充，它为系统对进程进行控制和管理提供了良好的环境。,18,2）内核的基本功能 中断处理 中断处理功能在操作系统中，既是内核的基本功能，也是整个操作系统赖以活动的基础，即操作系统的重要活动最终都依赖于中断。通常，内核只对中断进行有限的处理，然后转由有关进程继续处理。这不仅可以减少中断处理机的时间，也可以提高程序执行的并发性。 进程管理 进程的建立和撤销； 进程状态的转换； 进程调度； 控制进程

13、的并发执行。 资源管理的基本操作 包括对时钟、I/O设备和文件系统进行控制和管理的基本操作。,19,3）原语 内核在执行上述操作时，是通过执行各种原语操作来实现的。它是机器指令的延伸，是由若干条机器指令构成用以完成特定功能的一段程序。 为保证操作的正确性，它应该是原子操作。即一个操作中的所有动作，要么都做，要么都不做。换言之，原子操作是一个不可分割的操作。 内核中可能有许多原语，主要有进程控制原语、进程通讯原语、资源管理原语等。,20,进程控制原语： 创建原语(page 42-43) 向PCB集合申请一个空闲PCB，并获得其内部标识； 将有关信息填入PCB； 将该进程设置为就绪状态，并插入就绪

14、队列。 撤销原语 根据进程的外部标识检索PCB集，找到要撤销的PCB； 从队列中撤销该进程及其子、孙进程； 释放被撤销进程所占有的所有资源，撤销PCB。 阻塞原语 中断PCB执行，将CPU的当前状态保存到PCB的现场信息中； 将进程的当前状态置为阻塞状态； 将进程的PCB插入到该事件的阻塞队列中。 唤醒原语 在等待队列中找到该进程，将其PCB的当前状态置为就绪； 将进程从等待队列中撤销，并插入到就绪队列。,21,3.5 进程的互斥与同步,在操作系统中，资源是可以共享的，如：多个进程可共享硬盘、文件，变量甚至可执行程序段。然而，系统中的所有进程都是相互独立、以异步的方式并发执行的，所以进程间共享

15、资源可能导致问题 进程共享的资源不允许被同时访问，称为进程的互斥 以互斥关系使用的共享资源，叫做临界资源 操作系统必须提供一种机制对共享临界资源的进程进行协调，以保证这些进程能够“有序”地执行，这就是进程同步,22,为了保证对临界资源的互斥访问，进程的代码由以下几个部分组成： 进入区申请进入临界区 临界区访问临界资源 退出区退出对临界资源的访问 剩留区进程的其他部分,23,一个简单的互斥例子,临界资源,临界区,24,A进程 （负责从键盘写数据到缓冲区）,等待B进程发缓冲区数据已取走的信号,写数据到缓冲区,向B进程发数据已写入缓冲区的信号,B进程 （负责从缓冲区读数据进行计算）,等待A进程发数据

16、已写入缓冲区的信号,读缓冲区数据 并计算,向A进程发缓冲区数据已取走的信号,两进程并发执行过程,25,并发进程互斥时遵循的4条准则： 空闲让进：无进程处于临界区内，可让一申请进入临界区的进程进入，以有效利用临界资源 忙则等待：若已有进程进入临界区时，其余试图进入临界区的进程必须等待，以保证它们互斥的进入临界区 有限等待：对要求进入临界区的进程，应在有限时间内使之进入，以免陷入“死等” 让权等待：等待进入临界区的进程，它必须立即释放处理机，以免进程“忙等”,26,同步与互斥的联系与区别： 联系：进程互斥是进程同步的一种特例。 区别：进程互斥是并发进程因共享临界资源所产生的间接制约关系。（间接依赖

17、） 进程同步是合作进程之间因执行顺序所产生的直接制约关系。（直接依赖）,27,Pc,B,计算进程,Po,打印进程,一个简单的同步例子,缓冲区,28,29,P、V操作原语(互斥与同步机制),P等待V发信号 S信号量（共享资源使用情况） 1.记录型信号量的结构 typedef struct semaphore int value; /信号量的值 PCB *p; /等待该信号量的进程队列 ,30,2.PV原语 struct semaphore s; P操作 void P(s) s.value=s.value-1; if (s.value0) block(s.L); V操作 void V(s) s.v

18、alue=s.value+1; if (s.value=0) wakeup(s.L); ,31,进程A P（mutex）； 进入A临界区； V（mutex）； ,进程B P（mutex）； 进入B临界区； V（mutex）； ,利用P、V操作实现进程的互斥模型,申请获取资源；释放资源； 在进入临界区时，执行操作，获取对临界资源的控制权； 离开时，执行操作，释放对临界资源的控制权。,32,利用P、V操作实现进程的同步例子,计算进程（CP） 计算下一个结果； P（Sc）； B计算结果； V（So）； ,打印进程（IOP） P（So）； 从缓冲区取结果； V（Sc）； 打印取出的数据； ,缓冲区B,

19、计算进程,打印进程,Sc,So,33,进程的互斥与同步举例,34,35,P甲： . P（S） 分配凳子 V（S） .,设公有信号量S，初始为2。,P乙： . P（S） 分配凳子 V（S） .,P丙： . P（S） 分配凳子 V（S） .,P丁： . P（S） 分配凳子 V（S） .,36,用P.V操作解决司机与售票员的问题,司机进程： while(true) 启动车辆 正常驾驶 到站停车 ,售票员进程： while(true) 关门 售票 开门 ,37,设有两个信号量S1，S2，初值均为0。P操作表示等待或者检查某信号，V操作表示发信号。,38,一家人吃水果问题,桌上有一空盘，最多允许存放一只

20、水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。,son,daughter,39,设置三个信号量S,So,Sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。,40,试用信号量实现这三个进程的同步。,设有两个信号量Sb、Sc，初值均为 Pa： Pb： Pc： P(Sb); P(Sc); V(Sb); V(Sc); ,41,【思考题1】,如图，试用信号量实现这三个进程的同步。,42,【解】,设有两个信号量S1、S2，初值均为 P1： P2： P3： P(S1) V(S1); V(S

21、2); P(S2),43,【思考题2】,如图，试用信号量实现这6个进程的同步。,44,【解】,设有5个信号量S2、S3、S4、S5、S6，初值均为 P1： P2： P3： P4: P5: P6: P(S2); P(S3) P(S4) P(S5); P(S6); V(S2); P(S5); P(S6); V(S3)； V(S4); V(S6); V(S5) V(S5) V(S6),45,生产者消费者问题,生产者释放某一资源的进程 消费者使用同类资源的进程 制约关系： 1、缓冲池未满时，生产者进 程才能放入“产品”； 2、缓冲池未空时，消费者进 程才能取出“产品”； 3、各消费者进程与各生产者进程

22、 只能互斥的使用缓冲池。,消费者进程P1,P2,Pk,生产者进程C1,C2,Cm,in,out,46,信号量： 1、公有信号量Sg=1；互斥访问缓冲池。 2、消费者私有信号量Sc=0; 缓冲池的产品数目。 3、生产者私有信号量Sp=n; 缓冲池的空缓冲分区个数。,47,生产消费指针： 1、生产产品指针in; 开始指向第1个空缓冲分区, in=0 ； 到达第n个空缓冲区时，in=n-1; 在前进时，又指向第1个空缓冲分区, 就取余，in=(in+1) mod n, 这时in=0。 2、消费产品指针out; 开始指向第1个满缓冲分区, out=0 ； 到达第n个满缓冲区时，out=n-1; 在前进

23、时，又指向第1个满缓冲分区, 就取余，out=(out+1) mod n, 这时out=0。,48,生产者消费者进程的模型,生产者进程 生产一个产品； P（Sp）； P（Sg）； 将产品放入in指向的缓冲区Bin； in=(in+1) mod n; V（Sg）； V（Sc）； ,消费者进程 P（Sc）； P（Sg）； 从out指向的缓冲区Bout取产品； out=(out+1) mod n; V（Sg）； V（Sp）； ,检查是否有空缓冲区,申请进入临界区,进程退出临界区，即释放临界资源,产品数量1，发信号给消费者进程,49,生产者消费者进程的模型,生产者进程 生产一个产品； P（Sp）； P

24、（Sg）； 将产品放入in指向的缓冲区Bin； in=(in+1) mod n; V（Sg）； V（Sc）； ,消费者进程 P（Sc）； P（Sg）； 从out指向的缓冲区Bout取产品； out=(out+1) mod n; V（Sg）； V（Sp）； ,检查缓冲池内是否有产品,申请进入临界区,进程退出临界区，即释放临界资源,空缓冲区数量1，发信号给生产者进程,50,生产者消费者进程的模型,注意：该进程中，P操作的次序不允许颠倒，否则可能死锁。,生产者进程 生产一个产品； P（Sp）； P（Sg）； 将产品放入in指向的缓冲区Bin； in=(in+1) mod n; V（Sg）； V（Sc

25、）； ,消费者进程 P（Sc）； P（Sg）； 从out指向的缓冲区Bout取产品； out=(out+1) mod n; V（Sg）； V（Sp）； ,51,读者写者问题,制约关系： 1、允许多个读者同时读一个共享对象； 2、不允许一个写者和其他读者同时访问一个共享对象； 3、不允许多个写者访问一个共享对象。 如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,52,设有两个信号量w=1，mutex=1 另设一个全局变量readco

26、unt =0 w用于读者和写者、写者和写者之间对共享对象的互斥访问 readcount表示正在读的读者数目 mutex用于对readcount 这个临界资源的互斥访问,53,申请获得共享对象 释放共享对象,读者： while (true) P(mutex); if (readcount=0) P (w); readcount +; V(mutex); 读共享对象 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;,写者： while (true) P(w); 写共享对象 V(w); ;,54,哲学家进餐问题,有五个哲学家围坐在一圆

27、桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。 每个哲学家的行为是思考，感到饥饿，然后吃通心粉。 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。,55,设chopstick5为5 个信号量，初值为均1 Philosopheri： while (true) /哲学家i 思考； P(chopsticki)； /检查左边的筷子 P(chopstick(i+1) mod 5)；/检查右边的筷子 进餐； V(chopsticki)； /放下左边的筷子 V(chopstick(i+1) mod 5)；/放下右边的筷子 ,56,假设5位哲学家

28、同时拿起左边的筷子，则会出现死锁，为防止死锁发生可采取的措施： 最多允许4个哲学家同时拿起左边的筷子 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之,57,chopstick5=1,1,1,1,1； count=4； Philosopheri： while (true) /哲学家i 思考； P(count)； P(chopsticki)； /检查左边的筷子 P(chopstick(i+1) mod 5)；/检查右边的筷子 进餐； V(chopsticki)； /放下左边的筷子 V(chopstick(i+1) m

29、od 5)；/放下右边的筷子 V(count)； ,58,进程通信 进程间信息传送与交换。 操作系统可以被看作是各种进程组成的，例如用户进程、计算进程、打印进程等。这些进程都具有各自独立的功能，且大多数被外部需要而启动执行。 一般来说，进程间的通信根据通信的内容可以划分为两种： 控制信息的传送(低级通信,主要用于互斥与同步) 大批量数据传送(高级通信,主要用于信息交换),3.6 进程间通信,59,进程通信的类型： (1)共享存储器：基于共享数据结构或共享内存进行通信 (2)消息传递：利用消息进行通信 a.直接通信方式（消息缓冲通信） b.间接通信方式（信箱通信） (3)管道通信：利用共享文件进

30、行通信,3.6.1 进程间通信的类型（高级通信）,60,3.6.2 消息缓冲通信1.发送与接收原语,发送进程调用发送原语send(m)将消息m送往缓冲区。 接收进程调用接收原语receive(m)将消息m从缓冲区读往自己的数据区。 公有信号量mutex为控制对缓冲区访问的互斥信号量，其初值为1。SM为接收进程的私有信号量，表示等待接收的消息个数，其初值为0。,61,3.6.2 消息缓冲通信2.数据结构,为了实现消息缓冲队列通信，需要设置相关的数据结构，其中主要利用的数据结构是消息缓冲区。它可描述如下： typedef struct message_Buffer char sender ; /

31、发送消息的进程名或标识符 int size ; / 发送的消息长度 char text ; / 发送的消息正文 struct message_Buffer * next ; / 指向下一个消息缓冲区的指针 end 除此之外，在设置消息缓冲区队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在进程的PCB中涉及通信的数据结构有： mptr：消息队列队首指针 mutex：消息队列访问互斥信号量, 初值为1 SM：表示接收进程消息队列上消息的个数，初值为0，是控制收发进程同步的信号量,62,3.6.2 消息缓冲通信,接收进程名:Q 信件长:5 正文: ABCDE,Send(a),发送区a,消息队列首指针,mutex,SM,发送进程名:P 信件长:5 正文:ABCDE,后继信件 缓冲指针,0,进程Q的PCB,发送进程名:P 信件长:5 正文: ABCDE,receive(b),接收区b,进程P,进程Q,Send(m):begin 向系统申请一个消息缓冲区P