课件：进程与并发程序设计

1、第3章 进程机制与并发程序设计引言进程的引入和定义进程的状态和进程控制块进程控制线程的基本概念进程调度进程通信死锁Linux中的进程并发程序设计实例小结引言并发与并行概念同时进行多个任务的需求举例 解决需求采用的技术处理机分配问题进程概念和基本状态作业概念并发与并行首先声明：此处的系统是计算机软件系统或者是计算机控制环境中运行的软件系统。定义1 设System代表系统，则系统表示为：System = (S,Int,R)其中， S ： 软件集合； Int： 软件系统与硬件环境的交互关系集合； R：软件子系统之间的交互关系集合。定义2 如果考虑两个程序,它们在同一时间度量下同时运行在不同的处理机上

2、，则称这两个程序是并行执行的。定义3 设有两个活动a1和a2，如果在某一指定的时间t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。定义4 如果一个软件系统的行为由许多活动构成，假设其中至少有两个活动是并发执行的，则称该软件系统为并发系统。同时进行多个任务的需求举例编辑文档运行程序网上浏览CD音乐欣赏解决需求采用的技术问题：单处理机如何同时执行多个任务？PCB1PCB2PCB3程序1程序2程序3CPU分时：每个程序运行相等的时间片，轮流运行轮转。手段：采用进程概念，构造进程控制块，记录程序运行信息，建立进程

3、运行机制。程序进程控制块PCB数据处理机分配 为进程分配处理机，为进程分配使用CPU的时间段（时间片）按照系统服务的目标选择优先级最高的进程运行 优先级的计算依据程序的运行、等待、以及中断现场的保护区问题。进程概念和基本状态程序进程控制块PCB数据进程程序运行状态运行状态程序被中断时钟中断其它中断程序性中断外部中断基本状态分析程序等待CPU的状态就绪状态程序等待I/O设备的状态阻塞状态作业概念作业：用户提交的任务，包括作业步以及每一作业步要求的程序和数据。例如：用户要运行程序：第一步：编辑文件vi第二步：编译cc第三步：运行a.out第四步：得到结果这些就是作业步。作业与进程的关系includ

4、e “stdio.h”main()printf(“C programn”)initshellvicca.outchild创建关系进程的引入和定义顺序程序的特点并发系统概述并发程序的特点进程的引入进程的定义顺序程序及其特点程序执行的顺序性、环境的封闭性、结果的可再现性。图3-1 顺序处理操作的先后次序I1P1O1I2P2O2作业1作业2并发系统硬件环境概略展示的所有网络中，节点计算机可以是任何类型。单处理机新体系结构：数据流与函数语言机器单CPU，具有专用前端与后端处理机共享存储器多处理机（对称或专用处理机）LAN本地互连网向量与阵列处理机多计算机多处理机LAN/WAN系统并发（子）系统与并发活

5、动业务过程处理系统并发应用操作系统存储管理（子）系统通信处理（子）系统硬件事件操作系统存储管理（子）系统通信处理（子）系统业务处理系统其他应用并发算法客户需求并发（子）系统 并发活动文件管理（子）系统文件管理（子）系统并发程序及其特点并发意指“同时”。更准确地说，在某一时间里如果两个活动都处在各自的起点与终点之间，则认为这两个活动是并发的。 我们把在逻辑上的并行称之为并发。 例子：变量X为共享变量，程序1和程序2都要对X进行访问，当两个程序执行的速度变化时可得到不同的结果。程序2 X=X+1 R2=XR2=R2+1X=R2程序1 X=X+1 R1=XR1=R1+1X=R1 目标程序段 x=x+

6、1程序2 R2=XR2=R2+1X=R2 程序1 R1=XR1=R1+1X=R1 执行顺序1：程序1程序2 结果为：X增加2。执行顺序2： R1=X; R2=X; R1=R1+1; R2=R2+1; X=R1; X=R2 结果为： X 增加1。 还可有许多其它组合解决问题的手段 总 线中央处理机单元 内存储器磁盘适配器输入/输出接口其他外设接口通信线路接口磁盘驱动器输入/输出设备各种外设通信线路引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量，用进程代表运行的程序。建立进程的同步机制，对并发程序之间的相互牵连加以控制。P(mutex)V(mutex)P(mutex)

7、V(mutex)信号量初值mutex=1互斥进程的定义进程的参考定义有如下几种：1、进程是程序的一次执行；2、进程=PCB+程序+数据；3、进程是一个可拥有资源的独立实体，同时又是一个可以独立调度的基本单位。PCB程序段私有数据块进程的定义进程的状态和进程控制块PCB程序段私有数据块进程的定义运行就绪阻塞进程调度I/O完成时间片用完等待I/O完成进程的状态进程名当前状态优先数现场保留区指示处于同一状态进程的链指针资源清单进程起始地址家族关系其他进程控制块进程控制原语 进程控制原语 创建原语 撤销原语 阻塞原语 唤醒原语 控制原语与进程状态的转换祖先进程用户进程系统进程用户进程用户进程进程家族树

8、置状态为“阻塞”插入等待队列停止程序运行释放PCB释放内存释放所有资源申请空白PCB填PCB置状态为“就绪”插入就绪队列置状态为“就绪”插入就绪队列不可中断的系统程序。进程控制原语以及进程的状态转换运行就绪阻塞进程调度I/O完成时间片用完等待I/O完成创建进程撤销进程唤醒进程阻塞进程结束开始线程的基本概念引入线程的目的：则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。线程的定义：是进程中的一个实体，是被系统独立调度的基本单位。进程线程1线程2线程3进程1 分配处理机资源分配进程调度进程调度的职能 进程调度亦可称为处理机调度，它协调和控制各进程对CPU的使用。 进程调度算

9、法先来先服务FCFS 轮转调度 分级轮转法 优先数法 进程调度时的状态图FCFSP1P2 链头Pn就绪队列按进程创建的时间先后排序程序2程序1程序nPCB集合就绪状态创建时间就绪状态创建时间就绪状态创建时间中断现场保护区中断现场保护区中断现场保护区轮转调度最初的队列形成可按照FCFS或者按照优先级排队为每个进程分配一个时间片，轮流运行P1P2 链头Pn程序2程序1程序n刚从CPU上退下来的进程就绪状态调度信息就绪状态调度信息就绪状态调度信息中断现场保护区中断现场保护区中断现场保护区分级轮转法轮转链头指针FCFS最高优先级最低优先级次高优先级刚从CPU上退下来的进程优先数法P1P2 链头Pn就绪

10、队列按进程的优先级排序程序2程序1程序n中断现场保护区就绪状态优先级就绪状态优先级就绪状态优先级中断现场保护区中断现场保护区进程调度时的状态图3-6 调度时的进程状态变迁图低优先数就绪高优先数就绪运行因等待I/O而阻塞请求I/O首先选择超过时间片I/O完成其次选择挂起进程模型进程通信临界资源和临界区同步与互斥两个经典的同步/互斥问题其他同步例子管程消息缓冲临界资源和临界区临界资源critical resource临界区 critical section程序1Y=Y+1output程序2Y=Y+2output内存共享区Ypcb1pcb2同步与互斥基本概念同步工具硬件指令信号量与P、V操作并发程序

11、共享资源问题的解决基本概念同步进程之间的一种通信方式，有时序上的制约关系，或者说是进程之间为了协同工作而存在的一种等待关系。互斥进程之间对临界资源的一种竞争关系，排他性地对资源的访问方式。同步工具同步机制：用于控制进程之间的同步与互斥。硬件指令：test-and-set（lock）功能表示如下：test-and-set(lock)begina:=lock;If lock=0 then lock :=1;reutrn(a)end其中：lock是内存单元。举例应用举例程序1初始化lock=0程序的其它部分代码开锁lock=0test-and-set（lock）访问临界资源代码程序的其它部分lock

12、=1lock=0程序2初始化lock=0程序的其它部分代码开锁lock=0test-and-set（lock）访问临界资源代码程序的其它部分lock=1lock=0信号量信号量：仅能由P、V操作修改的整型变量。整型值 S队列指针 NextP操作P操作：申请资源操作(1)S:=S-1；(2)如果S0，则表示有资源，该进程继续执行；如果S0，则该进程继续执行；如果S0，则释放S信号量队列的排头等待者并清除其阻塞状态，即从阻塞状态转变到就绪状态，执行V(S)者继续执行。 两个经典的同步/互斥问题生产者与消费者读者与写者生产者与消费者问题模型的抽象化与进程分析(p99)生产者进程临界资源消费者进程信号

13、量的设置Mutex=1 临界资源Empty=n空缓冲区的个数Full=0满缓冲区的个数生产者/消费者算法描述1var mutex，empty，full：psemaphore； i,j，goods：integer；buffer：array 0n-1 of item；procedure producer； 生产者进程 begin while true do begin produce next product； P(empty)； P(mutex)； buffer(i):=product； i:=(i+1) mod(n)； V(mutex)； V(full)； endend；满空ij图3-8 环形

14、缓冲区procedure consumer； 消费者进程 begin while true do begin P(full)； P(mutex)； goods：= buffer(j)； j:=(j+1) mod(n)； V(mutex)； V(empty)； consume product； end end；生产者/消费者算法描述2begin seminitial (mutex.v，1；empty.v，n；full.v，0)； i：=j：=0； cobegin producer； consumer； coendend读者与写者问题模型的抽象化与进程分析(p100)文件写者进程读者进程读者进程.

15、信号量的设置R-mutex=1 临界资源1Rw-mutex=1 临界资源2临界资源：读者计数器r-counter文件写者进程实例读者与写者算法描述var mutex，wrt：psemaphore；readcount：integer；begin seminit(mutex.v，1；wrt.v，1)； readcount：= 0； cobegin procedure reader； begin P(mutex)； readcount:=readcount+1； if readcount =1 then P(wrt)； V(mutex)； reading is performing； P(mutex

16、)； readcount:=readcount-1； if readcount =0 then V(wrt)； V(mutex)； end procedure writer； begin P(wrt)； writing is performing； V(wrt)； end coendend；哲学家就餐第 i 个哲学家活动描述信号量初值：FORKSi=1，其中i=0、1、2、3、4BEGIN思考饥饿P(FORKSi mod(5)P(FORKS(i+1)mod(5)）吃面条V(FORKSi mod(5)V(FORKS(i+1)mod(5)）END没有考虑死锁问题五个哲学家就餐信号量：c0c4,初值

17、均为1；整型变量I=0,1,2,3,4；Philosopher(I)Begin if I mod 2 = 0 thenbeginP(cI);P(cI+1mod 5);吃V(cI);V(cI+1mod 5);endelsebeginP(cI+1mod 5); P(cI);吃V(cI+1mod 5); V(cI);endEnd实例没有考虑饥饿问题睡觉的理发师算法描述信号量：customers=0;barbers=0;mutex=1整型变量：waiting=0;理发师：Begin While(true)then Begin P(customers); P(mutex); Waiting=waitin

18、g-1; V(barbers); V(mutex); Cut hair(); End End 顾客：Begin P(mutex); If （waitingCHIRS) then Begin Waiting=waiting+1; V(customers); V(mutex); P(barbers); Get_haircut(); End Else Begin V(mutex); EndEnd管程把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的机构来统一管理各进程对该资源的访问，这个专门机构称为管程。Hansen在并发PASCAL语言中首先引入了管程，将它作为语言中的一个并发数据结构

19、类型。主控程序M. Entry1M. Entry1Monitor MEntry1Entry2P(mutext)V(mutext)管程的组成管程主要由两部分组成(p102)l 局部于该管程的共享数据，这些数据表示了相应资源的状态；l 局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。条件变量每个独立的条件变量是和进程需要等待的某种原因(或说条件)相联系的，当定义一个条件变量时，系统就建立一个相应的等待队列。关于条件变量有两种操作：wait(x)和signal(x)，其中x为条件变量。wait把调用者进程挂在与x相应的等待队列上，signal唤醒相应等待队列上的一个进程。管程描述pr

20、oducer: begin repeatproduce an item ;ringbuffer.put(item); until false;end consumer: begin repeatringbuffer.get(item);consume the item; until falseendmonitor ringbuffer；var rbuffer：array 0. n-1 of item； k ，nextempty，nextfull：integer； empty，full：condition；procedure entry put (var product：item)； begin

21、 if k=n then wait(empty)； rbuffernextempty:=product； k:=k+1； nextempty:=（nextempty+1) mod（n）； signal(full)； end；procedure entry get(var goods：item)； begin if k =0 then wait(full)； goods：=rbuffernextfull； k:=k-1； nextfull:=(nextfull+1) mod（n）； signal(empty)； end；begin k := 0； nextempty：=0；nextfull：=0

22、；end；消息缓冲:mq消息队列mutex互斥指针sm同步指针PCB(B)Sender:ASize:5Text:HelloNptr:receive(b):发送者：A 长度：5 正文：Hellob 0:send(B,a):发送者：A 长度：5 正文：Helloa发送接收图3-9 发送与接收消息过程。进程A进程B消息系统Receive 和 sendProcedure send(receiver,a)Begingetbuf(a,size,i);i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCB,receiver,j

23、);P(j.mutext);insert(j.mq,i);V(j.mutext);V(j.sm);EndProcedure receive(b)BeginP(j.sm);P(j.mutext);remove(j.mq,i);V(j.mutext);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;putbuf(i);End死锁死锁原因和必要条件死锁例子 产生死锁的原因和必要条件 预防死锁 资源独占(静态分配）资源顺序分配 资源受控动态分配 （避免死锁）发现死锁 （死锁检测）解除死锁 死锁举例死锁例子 进程P1 进程P2 ： ： 申请文件F申请磁带

24、机Tr1 ：申请磁带机T r2: 申请文件F 释放磁带机T 释放文件F释放文件F释放磁带机T产生死锁的原因和必要条件原因：系统资源不足；进程推进顺序不合适；必要条件互斥条件不剥夺条件请求和保持条件环路等待条件进程资源图 P1 P2F申请不同类型的资源T简单的死锁例子FTP2P1请求已分配请求配分已银行家算法10 (0)P 8Q 8R 7P 4Q 7R 64 (6)P 0Q 7R 60 (10)PQ 7R 68 (2)PQ 0R 50 (10)PQR 58 (2)PQR 03 (7)PQR10 (0)有顾客P、Q、和R，总共需要贷款23个货币单位，银行家有10个货币单位。死锁检测检测算法如下:

25、（进程资源图的化简）(1) 把未阻塞(Ci=0)的进程Pi记录在L表中(其全部资源请求已得到满足的进程)；(2) 从L表中选择一进程，根据资源分配表S释放分配给该进程的所有资源；(3) 由进程等待表W依次检查和修改需要该进程释放资源的每一个进程的等待计数器Cj；(4) 若Cj=0，则表示该进程所请求的资源已得到满足，不再阻塞，将Pj记入L表中；(5)再从L表中选取另一进程，重复上述操作；(6) 若所有的进程都记入L表中，则系统初始状态为非死锁状态，否则为死锁状态。表示进程资源图的数据结构表示请求边：请求矩阵表示分配遍：分配矩阵行下标表示进程Pi列下标表示资源Rj通过化简进程资源图断定是否存在死

26、锁。p1r1p2r2r3请求矩阵Request 资源进程R 1R2RjRmP1 b11b21b1jbm1P2b12b22b2jbm2Pib1jb2jbijbmjPm bm1bm2 bmjbmn 资源 R1R2RjRnP1a11a12a1ja1nP2a21a22a2ja2nPiai1ai2aijainPman1an2 amjamn进程分配矩阵Allocation死锁检测中的数据结构1、可用资源向量Available：表示m类资源中，每一类的可用数目。2、请求矩阵Request：是n m 矩阵，表示进程当前对各类资源的请求数目。3、分配矩阵Allocation：是 n m矩阵，用以表示进程某一时刻

27、的资源分配情况。4、工作向量Work：表示系统可提供给进程继续运行的各类资源数目。5、进程向量L：记录当前已不占有资源的诸进程。算法描述算法描述Work:=Available;L:= Li | Allocationi=0 Requesti=0 ;For all LiL dobeginfor all Requesti WorkbeginWork = Work +Allocationi Li Lendenddeadlock:=(L=P1,P2,Pn 解除死锁撤销死锁中的进程，释放出资源。撤销进程的代价进程优先级进程运行代价（已运行的%）进程类型等等交通死锁死锁图示无死锁例子有死锁Linux中的进程

28、Linux启动过程Linux进程控制块PCB简介 进程的创建 相关系统调用信号量与P、V操作等待队列进程调度管道Linux内核体系结构Linux启动过程引导扇区未分区分过区getty程序CPU执行轨迹0#idleLinux进程抽象Linux进程控制块PCB简介task 数组:进程控制块指针的集合（512个）task_struct结构进程标识进程状态调度信息进程链时间片进程通信信息内存资源信息文件资源信息进程上下文stoppedreadyrunningsuspendedzombie创建信号调度IO 结束IO 请求结束进程状态值说明TASK_RUNNING0就绪TASK_INTERRUPTIBLE

29、1浅度睡眠TASK_UNINTERRUPTIBLE2深度睡眠TASK_ZOMBIE4僵死TASK_STOPPED8暂停Linux进程状态表Linux进程状态转换Linux进程家谱Linux进程的生命周期进程的创建PCB1PCB2程序fork()采用Copy on write写时再复制 0#1#gettyloginshellshellgetty父进程fork()返回pid子进程fork()返回0tss线程clone()返回0struct pt_regsstruct reg64 eax;struct reg64 esp;当从fork()返回时，eax寄存器存放返回值。通用寄存器组的定义子进程系统空

30、间堆栈示意图系统调用返回时父子进程系统堆栈对照进程与线程本质区别进程地址空间独立线程共享地址空间线程堆栈执行上下文TSS进程代码数据堆栈文件IO虚存进程线程进程调度调度策略SCHED_OTHER普通进程SCHED_FIFO执行时间不长的实时进程（更高优先级可抢占CPU)SCHED_RR轮转的实时进程（相同优先级进程之间用时间片调度）weight权值priority静态优先级(时间片大小)缺省值为DEF_PRIORITY=20个时标（每个时标10ms）counter动态优先级，当前的时间配额（初值为DEF_PRIORITY)rt_priority相对优先级（0-99）#define DEF_PR

31、IORITY(20*HZ / 100) / 其中：HZ=100几个计算式子：普通进程的权值：counter = counter / 2 + priority weight=counter+prinority 当前进程的权值：weight=counter+priority+1实时进程的权值：weight = 1000+rt_priority Weight是linux系统在进程调度过程中选择进程的唯一标准 Linux内核的任务控制流相关系统调用以下简要列出了和进程及进程间通信相关的系统调用。在标志列中，各字母的意义为：m：手册页可查；+：POSIX 兼容；-：Linux 特有；c：libc 包含该

32、系统调用；!：该系统调用和其他系统调用类似， 应改用其他 POSIX 兼容系统调用。系统调用:广义指令，操作系统提供给用户使用的程序界面。系统调用表系统调用说明标志alarm在指定时间之后发送SIGALRM 信号m+cclone创建子进程m-execl, execlp, execle, .执行映象m+!cexit终止进程m+cfork创建子进程m+cgeteuid获取有效用户标识符m+cgetpid获取当前进程的进程标识符m+cipc进程间通信-ckill向进程发送信号m+c续表一msgctl消息队列控制m!cmsgget获取消息队列标识符m!cmsgrcv接收消息m!cmsgsnd发送消息m

33、!cnice修改进程优先级mcpause进程进入休眠，等待信号m+cpipe创建管道m+c续表二semctl信号量控制m!csemget获取某信号量数组的标识符m!csemop在信号量数组成员上的操作m!csetitimer设置间隔定时器mcshmat附加共享内存m!cshmctl共享内存控制m!cshmdt移去共享内存m!cshmget获取/建立共享内存m!csignal设置信号处理器mc续表三system执行 shell 命令m!ctime获取自 1970.1.1 以来的秒数m+ctimes获取进程的 CPU 时间m+cvfork见 forkm!cwait等待进程终止m+cwait3, w

34、ait4等待指定进程终止 （BSD）mcwaitpid等待指定进程终止m+cvm86进入虚拟 8086 模式m-cLinux信号量定义Linux 信号量数据结构中包含的信息count（计数）该域用来跟踪希望访问该资源的进程个数。正值表示资源是可用的，而负值或零表示有进程正在等待该资源。该计数的初始值为 1，表明同一时刻有且只能有一个进程可访问该资源。进程要访问该资源时，对该计数减 1，结束对该资源的访问时，对该计数加 1。sleepers（等待唤醒计数）等待该资源的进程个数，也是当该资源空闲时等待唤醒的进程个数。Wait(等待队列)某个进程等待该资源时被添加到该等待队列中。lock（锁）用来实

35、现对 waking 域的互斥访问的 Buzz 锁（自旋锁spin lock ）。Linux互斥操作进程标识调度信息时间片进程通信信息进程状态进程链内存资源信息文件资源信息进程上下文Linux进程控制块逻辑结构task_struct结构等待队列Linux 中的等待队列wait_queuewait_queuetask_structtask_structwait_queuetask_structtasktask.task.nextnextnexttask_structwait_queue_head_t Linux虚存管理数据结构进程控制块与文件系统数据结构关系管道 管道示意图进程 1file 结构（

36、files_struct） 进程 2file 结构inode数据页管道写操作集管道读操作集 f_mode f_pos f_flags f_count f_owner f_inode f_version f_op f_mode f_pos f_flags f_count f_owner f_inode f_version f_op 信号检测与处理流程图进程控制并发程序设计实例fildes1Father1.c进程1Child1.c进程2fildes0进程的建立fork()的使用main() int i; i=fork(); if(i) printf(“parent”); else printf(“

37、child”); main() int i; i=fork(); if(i) printf(“parent”); else printf(“child”); fork()PCB1PCB2pipe系统调用说明int pipe(fildes)int fildes2Pipe建立一个I/O机制称为管道，并且返回两个文件描述符：files0管道读指针files1 管道写指针管道（FIFO缓冲区）大小为6kfiles0专门读取由files1 写入管道的数据。当pipe执行失败时，返回-1。dup系统调用说明int dup(files)int fildesfildes 是文件描述符，由creat,open,dup,fcntl,或者pipe系统调用提供。dup返回一个新的文件描述符，与原始描述符具有如下共同点：相同的打开文件（或管道文件）相同文件指针（即：两个文件描述符共享一个文件指针）相同的访问权限（读、写、或读/写）返回的文件描述符是空闲描述符中序号最小的那个。执行成功则返回非负整数，即文件描述符。执行失败则返回-1。execl系统调用说明int execl(path,arg