操作系统原理-庞丽萍-第四章并发处理

1第四章并发处理(一)并发程序及特点(二)进程的基本概念(三)进程控制(四)进程互斥(五)进程同步(六)线程的基本概念2(一)并发程序及特点一.顺序程序及特点1.什么是计算程序的一次执行过程称为一个计算，它由许多简单操作所组成。2.什么是程序的顺序执行一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。32.例：讨论单道系统的工作情况对用户作业的处理——首先输入用户的程序和数据然后进行计算最后打印计算结果即有三个顺序执行的操作——I：输入操作C：计算操作P：输出操作P2C2I2P1C1I143.顺序程序的特点(1)顺序性处理机的操作严格按照程序所规定的顺序执行。(2)封闭性程序一旦开始执行，其计算结果不受外界因素的影响。独占资源(3)可再现性程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。5二.并发程序及特点1.例：讨论在多道批处理系统中，对大量作业的处理。对作业1、作业2、┅作业n的处理：作业1：I1C1P1作业2：I2C2P2┇作业n：InCnPn6用下图说明在多道批处理系统中，大量操作执行的先后次序。I1I2I3I4C1C3C2P1P2讨论：(1)哪些程序段的执行必须是顺序的？为什么？(2)哪些程序段的执行是并行的？为什么？72.什么是程序的并发执行若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。例：三个并发执行的程序段。PQR83.并行语句记号可以用语句cobeginS1；S2；┅；Sncoend来表示语句S1，S2，┅，Sn可以并发执行。三.与时间有关的错误什么是与时间有关的错误程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。9四.并发程序的特点1.失去程序的封闭性和可再现性如果一个程序的执行可以改变另一个程序的变量，那么，后者的输出就可能有赖于各程序执行的相对速度，也就是失去了程序的封闭性特点。例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。设：程序A每执行一次都要做n加1的操作，程序B每隔一定时间打印出n值，并将它重新置为零。10程序A┆n:=n+1;┆程序B┆print(n);n:=0;程序A的n:=n+1与程序B的两个语句的关系n的赋值打印的结果n的最终赋值之前10110之后10101之间1010011(2)程序与计算不再一一对应一个程序可以对应多个计算例1：I1输入程序段I2┆In例2：编译1C编译程序编译2┆编译n12(3)程序并发执行的相互制约直接的相互制约关系—公共变量间接的相互制约关系—资源共享主机终端1终端2终端n13(二)进程的基本概念一.进程定义程序并发执行时，新的活动规律：执行暂停执行1.什么是进程所谓进程，就是一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。142.进程与程序的区别(1)程序是静态的概念；进程是动态的概念。(2)进程是一个独立运行的活动单位。(3)进程是竞争系统资源的基本单位。(4)一个程序可以对应多个进程；一个进程至少包含一个程序。15二.进程状态1.进程的基本状态(1)运行状态(running)该进程已获得运行所必需的资源，它的程序正在处理机上执行。(2)等待状态(wait)进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行，则称该进程处于等待态。(3)就绪状态(ready)进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。162.进程状态的变迁进程的状态随着自身的推进和外界条件的变化而发生变化。运行等待就绪服务请求(请求I/O等)服务完成/事件来到进程调度时间片到17三.进程描述当某程序和其他程序并发执行时，产生了动态特征，并由于并发程序之间的相互制约关系而造成了比较复杂的一个外界环境。1.什么是进程控制块描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构，称为进程控制块pcb(processcontrolblock)或称为进程描述器(processdescriptor)。182.进程的组成进程控制块PCB程序与数据程序与数据：描述进程本身所应完成的功能；PCB：进程的动态特征，该进程与其他进程和系统资源的关系。193.PCB的主要内容(1)进程标识符：进程符号名或内部id号。(2)进程当前状态：本进程目前处于何种状态(运行、就绪、等待)。(3)当前队列指针next：该项登记了处于同一状态的下一个进程的pcb地址。(4)总链队列指针all_q_next：该项登记了在系统总链队列中，下一个进程的pcb地址。进程标识符进程当前状态当前队列指针总链队列指针程序开始地址进程优先级CPU现场保护区通信信息家族联系占有资源清单20ready_q_startready_q_startpcb1pcb2pcb9就绪队列结构nextwait_lpt_q_startpcb3pcb7next打印机等待队列结构runningpcb4next运行指针all_q_startpcb1pcb2pcbn总链队列结构all_q_next21(5)程序开始地址：该进程的程序将从此地址开始执行。(6)进程优先级：反映了进程要求CPU的紧迫程度.(7)CPU现场保护区：当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中。(8)通信信息：进程间进行通信时所记录的有关信息。(9)家族联系：指明本进程与家族的联系(10)占有资源清单22(三)进程控制一.进程控制的概念1.进程控制的职责对系统中的全部进程实施有效的管理，负责进程状态的改变。进程状态变化：无——有——消亡运行——等待就绪———等待等待唤醒创建撤消232.常用的进程控制原语创建原语、撤消原语、阻塞原语、唤醒原语等。二.进程创建1.进程创建原语的形式create(name，priority，start_addr)name为被创建进程的标识符priority为进程优先级start_addr为某程序的开始地址。242.进程创建原语的功能创建一个具有指定标识符的进程，建立进程的PCB结构。3.进程创建原语的实现(1)PCB池ab1┇25(3)程序描述算法create输入：新进程的符号名，优先级，开始执行地址输出：新创建进程的内部标识符pid{在总链队列上查找有无同名的进程；if(有同名进程)return(错误码)；∕**∕从pcb资源池申请一个空闲的pcb结构；if(无空pcb结构)return(错误码)；∕**∕用入口参数设置pcb内容；置进程为“就绪”态；将新进程的pcb入就绪队列；将新进程的pcb入总链队列；return(新进程的pid)；}26三.进程撤消1.进程撤消原语的形式当进程完成任务后希望终止自己时使用进程撤消原语。Kill(或exit)该命令没有参数，其执行结果也无返回信息。2.进程撤消原语的功能撤消当前运行的进程。将该进程的pcb结构归还到pcb资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。273.进程撤消原语的实现算法kill输入：无输出：无{由运行指针得当前进程的pid；释放本进程所占用的资源给父进程；该进程从总链队列中摘除；释放此pcb结构；转进程调度程序；}28四.进程等待1.进程等待原语的形式当进程需要等待某一事件完成时，它可以调用等待原语把自己挂起。susp(chan)入口参数chan：进程等待的原因。2.进程等待原语的功能中止调用进程的执行，并加入到等待chan的等待队列中；最后使控制转向进程调度。293.进程等待原语的描述算法susp输入：chan等待的事件(阻塞原因)输出：无{保护现行进程的CPU现场到pcb结构中；置该进程为“阻塞”态；将该进程pcb插入到等chan的等待队列；转进程调度；}303.进程等待原语的描述算法susp输入：chan等待的事件(阻塞原因)输出：无{保护现行进程的CPU现场到pcb结构中；置该进程为“阻塞”态；将该进程pcb插入到等chan的等待队列；转进程调度；}313.进程等待原语的描述算法susp输入：chan等待的事件(阻塞原因)输出：无{保护现行进程的CPU现场到pcb结构中；置该进程为“阻塞”态；将该进程pcb插入到等chan的等待队列；转进程调度；}32五.进程唤醒1.进程唤醒原语的形式当处于等待状态的进程所期待的事件来到时，由发现者进程使用唤醒原语叫唤醒它。wakeup(chan)入口参数chan：进程等待的原因。2.进程唤醒原语的功能当进程等待的事件发生时，唤醒等待该事件的所有进程或等待该事件的首进程。333.进程唤醒原语的描述算法wakeup输入：chan等待的事件(阻塞原因)输出：无{保护现行进程的CPU现场；找到该阻塞原因的队列指针；找到该等待进程;将进程移出此等待队列；置进程状态为“就绪”；将进程入就绪队列；}34(四)进程互斥一.进程互斥的概念1.临界资源(1)例1：两个进程A、B共享一台打印机若不加以控制，两个进程的输出结果可能交织在一起，很难区分。(2)例2：两个进程共享一个变量x设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2，35两个进程共享一个变量x时，两种可能的执行次序：A：p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；B：p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；设x的初值为10，两种情况下的执行结果：情况A为x=10+2情况B为x=10+136特点：当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。(3)什么是临界资源我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备，如输入机、打印机、磁带机等都具有这种性质。软件资源，如公用变量、数据、表格、队列等也都具有这一特点。37(4)什么是临界区在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称为临界区或临界段。它就是进程中对公共变量(或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。进程A┆x:=x+1;┆csa{进程B┆x:=x+1;┆csb{38(5)什么是互斥在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。例如：进程A正在执行csa段时，进程B就不能进入csb段执行。进程A┆x:=x+1;┆csa{进程B┆x:=x+1;┆csb{39二.锁和上锁、开锁操作1.什么是锁用变量w代表某种资源的状态，w称为“锁”。2.上锁操作和开锁操作检测w的值(是0还是1)如果w的值为1，继续检测；如果w的值为0，将锁位置1(表示占用资源)，进入临界区执行。(此为上锁操作)临界资源使用完毕，将锁位置0。(此为开锁操作)403.上锁原语和开锁原语(1)上锁原语算法lock输入：锁变量w输出：无{test：if(w为1)gototest；∕**∕elsew=1；∕**∕}(2)开锁原语算法unlock输入：锁变量w输出：无{w=0；∕**∕}414.用上锁原语和开锁原语实现进程互斥上锁原语进入临界区csb开锁原语进程B上锁原语进入临界区csa开锁原语进程A42三.信号灯和p、v操作1.什么是信号灯信号灯是整型变量。变量值≥0时，表示绿灯，进程执行；变量值0时，表示红灯，进程停止执行。信号灯是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理