四章节并发处理

1第四章第四章 并发处理并发处理2（一）并发程序及特点（一）并发程序及特点 一个程序由若干个程序段组成，而这些程序段的执行必须按照严格的先后次序顺序的执行。程序的顺序执行也称为顺序程序设计顺序程序设计。顺序环境顺序环境：在单道计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响.32.2.程序顺序执行的特点程序顺序执行的特点（1 1）程序执行的顺序性）程序执行的顺序性（大多数程序都具有）处理机的操作严格按照程序所规定的顺序执行。（2 2）程序执行的封闭性）程序执行的封闭性独占资源，执行过程中不受外界影响（由执行环境保证）（3 3）程序执行结果的可再现性（确定性）程序执行结果的可再现性（确定性）程序执行的结果与初始条件有关，而与执行时间无关与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。（由封闭性保证）4二二.并发程序及特点并发程序及特点并发环境：并发环境：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的BAABBAAB5例：用下图说明在多道批处理系统中，大量例：用下图说明在多道批处理系统中，大量操作执行的先后次序。操作执行的先后次序。n讨论：（1）哪些程序段的执行必须是顺序的？为什么？（2）哪些程序段的执行是可并行的？为什么？I1I2I3I4C1C2C3P1P262.2.什么是程序的并发执行什么是程序的并发执行 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。例：三个并发执行的程序段73.3.并行语句的表示并行语句的表示n程序并发执行的描述 cobegincobegin S1;S2;S3;.;SN coend;coend;n提问：提问：语句语句S S1 1、S S2 2、S S3 3、.、S SN N 谁先执行？谁后执行？谁先执行？谁后执行？8假设有一个程序由假设有一个程序由S S0 0S Sn+1n+1个语句，其中个语句，其中 S S1 1S Sn n语语句是并发执行的，程序如句是并发执行的，程序如下：下：S S0 0;cobegin cobegin S S1 1;S;S2 2;S;S3 3;.;S;.;SN N coend;coend;S Sn+1n+1;94.4.实例：实例：a a 一个循环程序顺序执行的誊抄一个循环程序顺序执行的誊抄算法算法1：输入：输入：f 输出：输出：g while(f 不为空）不为空）input;output;由这个程序完成誊抄工作是不会出错的。由这个程序完成誊抄工作是不会出错的。10实例：实例：b b 两个程序并发执行完成誊抄两个程序并发执行完成誊抄 设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。f缓冲区缓冲区输入程序输输出出程程序序g11算法：算法：2 cobegin cobegin while(while(不为结束符）不为结束符）/*输入程序段输入程序段 */input;/input;/*从标准输入设备读入一个数据从标准输入设备读入一个数据 */send;/send;/*将读入的数据送到将读入的数据送到bufferf bufferf*/while(buffer while(buffer不为空）不为空）/*输出程序段输出程序段 */receive;/receive;/*从从bufferfbufferf中取数据中取数据 */output;/output;/*送打印机输出送打印机输出 */coend coend？存在什么问题？存在什么问题？12n这两个程序段并发执行时可能出现如下情况：这两个程序段并发执行时可能出现如下情况：1 1、输出程序运行的速度比输入程序快时，有、输出程序运行的速度比输入程序快时，有些输出会重复；些输出会重复；2 2、输入程序执行的速度比输出程序快时，有、输入程序执行的速度比输出程序快时，有些数据会丢失。些数据会丢失。13实例：实例：c c 三个并发执行程序的誊抄三个并发执行程序的誊抄f缓冲区缓冲区sgetput缓冲区缓冲区tcopygnget程序负责从输入序列f中读取字符并送到缓冲区s中;ncopy程序把缓冲区s中的数据复制到缓冲区t中去;nput程序从缓冲区t中取出数据打印。14n假定假定f f系列中有记录系列中有记录f=(R1,R2,.,Rn)f=(R1,R2,.,Rn)g=()g=()在誊抄完成后：在誊抄完成后：f=()f=()g=(R1,R2,.,Rn)g=(R1,R2,.,Rn)n算法中的：算法中的：copyt=s copyt=s put put(t,g)put put(t,g)get get(s,f)get get(s,f)15n若程序错写成：若程序错写成：while(while(誊抄未完成）誊抄未完成）cobegin cobegin copy;copy;put;put;get;get;coend coend n初始状态：初始状态：f=(R1,R2,.,Rn)f=(R1,R2,.,Rn)s=()t=()g=()s=()t=()g=()首先执行了首先执行了get(s,f)get(s,f)f=(R1,R2,.,Rn)f=(R1,R2,.,Rn)s=R1,t=(),g=()s=R1,t=(),g=()与时间有关的错误与时间有关的错误16n然后，copy,put,get三个程序段并发执行，就有六种组合：1、copy;put;get 导致结果：g=(R1,R2)2、copy;get;put 导致结果：g=(R1,R2)3、put;copy;get 导致结果：g=(R1,R1)4、put;get;copy 导致结果：g=(R1,R1)5、get;copy;put 导致结果：g=(R1,R3)6、get;put;copy 导致结果：g=(R1,R1)n这就是与时间有关的错误：这就是与时间有关的错误：程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。175.5.并发程序的特点并发程序的特点（1 1）失去了程序的封闭性（程序结果的不可再现性）失去了程序的封闭性（程序结果的不可再现性）如果程序执行的结果是一个与时间无关的函数，即具有封闭性。若一个程序的执行可改变另一个程序的变量，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下结果是不确定的，即失去了程序的封闭性。n例：讨论共享公共变量的两个循环程序，它们执行时可能产生的不同结果。设：程序A每执行一次都要做n加1的操作程序B每隔一段时间打印出n的值，并将n重新置为零18（2 2）程序与计算不再一一对应）程序与计算不再一一对应 一个程序可以对应多个计算：多用户共享使用同一个程序，但处理（计算）的对象却是不同的。例1：例2：L1编译；输入程序段 L2 C编译程序编译；Ln编译。（3 3）程序并发执行的相互制约）程序并发执行的相互制约n直接的相互制约关系公共变量n间接的相互制约关系资源共享196.6.进程的引入进程的引入n并发活动进程的引入并发活动进程的引入 操作系统的特性之一是并发与共享，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。操作系统的第三个特性：不确定性*要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引入新的概念进程进程。20（二）（二）进程的基本概念进程的基本概念一、进程定义一、进程定义n在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新的概念进程。n程序并发执行时，新的活动规律：执行 暂停 执行n 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。1.1.什么是进程什么是进程所谓进程，就是一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。212.2.进程与程序的区别与联系：进程与程序的区别与联系：1、程序是指令的集合，是静态的概念；进程是程序在处理机上的一次执行的过程，是动态的概念。n进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的2、进程是一个独立的运行单位，能与其它进程并行活动。而程序则不是。n进程更能真实地描述并发，而程序不能3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。n进程具有创建其他进程的功能，而程序没有223.3.进程的类型进程的类型n在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程 系统进程起着资源管理和控制的作用。或者：执行操作系统核心代码的进程。2、用户进程 执行用户程序的进程。（系统进程优先于用户进程）23系统进程与用户进程的区别：系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用；2、用户进程不能做直接I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在核态下活动，而用户进程则在用户态下活动。24二、进程的状态二、进程的状态1.进程的基本状态进程在系统中的活动规律是：执行 暂停 执行进程的三种基本状态：运行状态 就绪状态 等待状态（又称阻塞、挂起、睡眠）25（1 1）运行状态）运行状态 （RunningRunning）该进程已获得运行所必需的资源，它的程序正在处理机上执行。（在系统中，总只有一个进程处于此状态）（2 2）等待状态）等待状态 （WaitWait）进程正在等待某个事件的发生而暂停执行。这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。（3 3）就绪状态（）就绪状态（Ready)Ready)进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。（有多个进程处于此状态）26 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：就绪运行 运行就绪 运行等待 等待就绪272.2.进程状态的变迁进程状态的变迁进程的状态不是固定不变的，而是在不断变换，它随着自身的推进和外界条件的变换而发生变化。运行运行就绪就绪等待等待某事件的发生时间片到时间片到服务完成服务完成/事件发生事件发生进程调度进程调度28例例1.设有设有3个排序程序个排序程序程序程序A：采用冒泡排序算法，在屏幕的左1/3处开设一个窗口显示其排序过程。程序程序B：采用堆排序算法，在屏幕的中1/3处开设一个窗口显示其排序过程。程序程序C：采用快速排序算法，在屏幕的右1/3处开设一个窗口显示其排序过程。（1）在不支持进程运行环境的操作系统下运行（2）在支持进程运行环境的操作系统下运行29运运 行行 过过 程程（1）在不支持进程运行的环境下：依次运行程序A、程序B、程序C。（2）在支持进程运行的环境下：建立进程A、B、C，分别对应进程A、B、C。若系统按时间片轮转的调度策略调度这3个进程，则在屏幕上有3个窗口，同时显示3个程序的排序过程。实际上，这3个程序是轮流的占用CPU的时间执行。由于CPU的高速度，使我们看到好像是这3个程序在同时执行。30例2：设有2个程序，程序C是打印工资报表的程序，程序D是计算1000以内所有素数并显示最后结果程序。（1）在不支持进程运行环境的操作系统下运行。（2）在支持进程运行环境的操作系统下运行。31运运 行行 过过 程程（1）在不支持进程运行的环境下：依次执行程序C，程序D。可以看到，先是打印机不停的打印工资报表，打完后，接着运行程序C，不停的计算，最后显示所计算的结果。（2）在支撑进程运行的环境下：创建进程C和进程D。由于进程C是I/O量较大的进程，而进程D是计算量较大的进程，故在系统进程调度的控制下，两个进程并发执行。可以看到打印机不断打印工资报表，而处理机不停的计算，最后屏幕显示计算的结果。32三、进程描述三、进程描述1.什么是进程控制块什么是进程控制块n描述一个进程在各个不同时期所处的状态，与其他进程及系统资源的关系的数据结构称为进程控制块pcb（process control block），也称为进程描述器（process descriptor）。n系统为了管理进程而设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。n系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与进程与PCBPCB是一一对应的是一一对应的332.进程的组成进程的组成n程序与数据：描述进程本身所应完成的功能；nPCB：描述进程的动态特征，该进程与其他进程和系统资源的关系。进程控制块PCB程 序与数 据34n进程的执行程序（一个可执行文件）n进程控制块（数据结构）n进程总是位于某个队列(就绪、等待某事件队列)n处于某种状态（运行、就绪、等待）n占用某些系统资源（内存，打开某些文件、处理机、外设）进程标识信息进程状态信息进程控制信息用户堆栈共享地址空间用户私有地址空间（代码、数据）进程控制块353.PCB的主要内容的主要内容（1）进程标识符：进程符号名或内部id号。（2）进程当前状态：本进程目前处于何种状态（运行、就绪、等待）。（3）当前队列指针next：该项登记了处于同一状态的下一个进程的pcb地址。（4）总链队列指针all_q_next：该项登记了在系统总链队列中，下一个进程的pcb地址。36系统中的进程是很多的，状态也不一样。为了调度和管理进程，需将各进程的PCB用适当的方法组织起来，以下有三种方法：n 把所有的PCB组织在一个表格中（简单，但查找不方便，适用于进程数目少的场合）n 分别把有着相同状态的进程的PCB组织在同一表格中（如就绪进程表，等待进程表，运行进程表）n 分别把具有相同状态的所有进程的PCB按优先级排成一个或多个队列（最常用的方法，如就绪队列，等待队列等，可能等待的资源相同，但优先级不同）37all_q _nextnextnextnextPCBPCBPCBall_q _next总链队列结构总链队列结构383.PCB的主要内容的主要内容（5）程序开始地址：该进程的程序将从此地址开始执行。（6）进程优先级：反映了进程要求CPU的紧迫程度。（7）CPU现场保护区：当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中。（8）通信信息：进程间进行通信时所记录的有关信息。（9）家族联系：指明本进程与家族的联系。（10）占有资源清单39（三）进程控制（三）进程控制一一.进程控制的概念进程控制的概念进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效的管理。进程控制包括：n进程创建、进程撤消、进程阻塞、进程唤醒n改变优先数、调度进程、进程延迟这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语原语（一种特殊的系统调用）。40运行运行就绪就绪等待时间片到时间片到进程调度进程调度进程进程唤醒唤醒进程进程创建创建进程阻塞进程阻塞进程进程撤消撤消41二二.进程创建进程创建1.1.进程创建原语的形式：进程创建原语的形式：create(name,priority,start-addr)create(name,priority,start-addr)入口参数 name：被创建进程的标识符 priority：进程优先级 start-addr：某程序的开始地址。2.2.进程创建原语的功能：进程创建原语的功能：创建一个指定标识符的进程（形成该进程的进程控制块pcb）。UNIX系统：fork()423.3.进程创建原语的实现进程创建原语的实现n创建一个PCBn从PCB池中申请一个空的PCB结构：-1=xn赋予一个统一进程标识符n为进程映象分配空间n初始化进程控制块n许多默认值(如:状态为 New，无I/O设备或文件.)n设置相应的链接n如:把新进程加到就绪队列的链表中4344nextPCB3nextPCB11nextPCB2 PCBnReady-q-startnextPCB67nextPCB22nextPCB34 PCBmall-q-startnextPCBk进程创建后相应数据结构变化进程创建后相应数据结构变化45三三.进程撤消进程撤消当进程完成任务后希望终止自己时使用进程撤销原语。1.进程撤销原语的形式：进程撤销原语的形式：Kill（或exit）该命令没有参数，其执行结果也无返回信息。2.进程撤销原语的功能：进程撤销原语的功能：撤销当前运行的进程。将该进程所占用的资源归还给父进程，从总链队列中摘除pcb结构，归还到pcb资源池，然后转进程调度程序。UNIX系统：exit()463.3.进程撤消原语的实现进程撤消原语的实现n根据撤销进程标识号，从相应队列中找到它的PCBn将该进程拥有的资源归还给父进程或操作系统n若该进程拥有子进程，应先撤销他的所有子孙进程，以防它们脱离控制n被撤销进程出队，将它的PCB归还到PCB池n调用进程调度程序4748四四.进程挂起进程挂起当进程需要等待某一事件完成时，它可以调用等待原语把自己挂起。1.进程等待原语的形式：进程等待原语的形式：susp（chan）入口参数chan：进程等待的原因。2.进程等待原语的功能：进程等待原语的功能：中止调用进程的执行，并加入到等待chan的等待队列中，最后使控制转向进程调度。UNIX：sleep(chan,pri)493.进程等待原语的实现进程等待原语的实现算法 susp（chan）输入：chan 等待的原因 输出：无 进程现场信息PCB；进程状态置为“阻塞”；插入到等待“chan”等待队列；调用进程调度程序；50nextPCB3nextPCB11nextPCB2 PCBnwait-lpt-q-startnextPCBj next 51五五.进程唤醒进程唤醒1.进程唤醒原语的形式：进程唤醒原语的形式：当处于等待状态的进程所期待的事件来到时，由发现者进程使用唤醒原语叫唤醒它。wakeup（chan）入口参数chan：进程等待的原因2.进程唤醒原语的功能：进程唤醒原语的功能：当进程等待的事件发生时，唤醒等待该事件的所有进程或等待该事件的首进程。523.进程唤醒原语的功能进程唤醒原语的功能 n从相应的等待进程队列中取出进程控制块n 修改进程控制块的有关信息，如进程状态等n 把修改后进程控制块加入有关就绪进程队列进程唤醒操作会引起就绪队列和等待进程唤醒操作会引起就绪队列和等待chan事事件的等待队列发生变化。件的等待队列发生变化。