并发执行问题.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第七讲 并发执行问题,目的与要求,：,了解并行程序的高级语言表示与操作系统支持下的实现；了解同步与互斥问题。,重点与难点,：并行程序中的同步与互斥,作业,：,1,，,2,3,例举两个现实生活中需要同步与互斥的例子。,第四章 进程同步与通讯、进程死锁,并发的需求,操作系统应尽量支持用户态程序最大限度地并行执行。,程序设计要利用操作系统对并行运行的支持（以进程或线程方式），安排并行事务并行执行。,操作系统核心程序也要尽可能地并发运行,4.1,并发编程,计算任务存在并行成分,S1,和,S2,两个子任务可并发执行S1,S3,S2,并发编程有三种方法：,程序员写顺序程序，用识别工具识别并发成分，再组织使用操作系统的并发机制。,由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；,或直接利用操作系统的系统调用,/,高级并发程序库设计并发程序。,并发程序设计语言,-,并发语句,是在传统高级语言基础上增加描述并行的语句。,语法形式,Parbegin S1,；,S2,；,Sn,；,Parend,；,Si,（,i=1,，,2,，,，,n,）是单个语句,Parbegin,和,Parend,之间的语句可以并发执行,并发语句示例,前面那个计算任务可以描述为：,Parbegin,S1,；,S2,；Parend,；,S3,并发语句描述手段的优缺点,并发语句,Parbegin/Parend,的结构化特征非常好,但存在着描述能力不强的缺点，即存在着用,Parbegin/Parend,语句无法描述的并发优先关系（如下图）。,若能辅以其它手段（如本章后续将介绍的信号量机构），则并发语句可以大大增加其描述并发的能力。,S1,S2,S3,S4,S5,S6,S7,并发执行实现,前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统支持的进程（或线程）机制。,操作系统提供,进程（线程）创建，结束和同步,的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对操作系统的系统调用。,与进程相关的系统调用,Unix-alike,操作系统利用进程（或线程）支持并发执行,它提供了如下系统调用：,fork,（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从,fork,（）调用的返回点开始运行，而父进程,fork,（）调用的返回值是子进程的进程标识,pid,；子进程,fork,（）调用的返回值是,0,。,exit,（,status,）：进程结束。该系统调用发出后，操作系统将从系统中删除调用,exit,的进程，并将,status,值传给等待它结束的父进程。,wait,（,&status,）：等待子进程结束。当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用,exit,（,status,）时的,status,值送到,&status,指针所指单元中。在控制返回调用者时，同时将所等到的子进程,pid,作为,wait,（）系统调用函数的返回值。,waitpid,（,pid,，,）：等待,pid,所指定的进程结束。,多进程实现前述的计算任务并发,pid=fork,（,）；,if(pid=0)then,S2,；,exit,（,0,）；,else,S1,；,wait,（）；,S3,；,4.2,进程的互斥与同步,同步关系,（亦称直接制约关系）,指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而等待、传递信息所产生的制约关系。,互斥关系,（亦称间接制约关系）,即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。,4.2.1,同步与临界段问题,例,1,：同步问题。如果进程,P1,执行,S1,，,S3,进程,P2,执行,S2,，则,P1,在执行,S3,之前必须等待,P2,执行完,S2,。,S1,S3,S2,例,2,：,P1,、,P2,两进程使用同一打印机。如果不互斥使用会交叉输出,Entry code,exit code,使用打印机,P1,Entry code,exit code,使用打印机,P2,Parbegin,A(amount),R1=balance;,R2=amount;,R1=R1+R2;,balance=R1;,;,B(amount),R1=balance;,R2=amount;,R1=R1-R2;,balance=R1;,;,Parend;,例,3:,对共享变量,balance,的互斥访问,互斥执行,例,4,：有限缓冲区的生产者,/,消费者问题（生产者和消费者共享一个产品缓冲链）,INST,NEXT,共享,N,个缓冲区,P1 P2 Pm,C1 C2 Cn,INST,Nil,INST,NEXT,First,INST,NEXT,First,typedef struct,item/,消息类型,typedef struct,struct buffer*next;,struct item inst,；,buffer,；,/,缓冲类型,struct buffer *P,，*,C,，*,First;,struct item nextp,，,nextc;,First=nil;,数据结构,new(P);,#,获得一空缓冲区,P.inst=nextp;,P.next=First;,First=P;,while(1);,;,Parbegin,Producer(),do,produce an item in nextp;,.,consume the item in nextc;,while(1);,;,Parend;,Consumer(),do,while(first=nil);,#,空循环等,C=First;,first=first.next;,nextc=C.inst;,dispose(C);,#,释放缓冲区,T0,：,consumer C=First,T1,：,producer P.next=First,T2,：,producer First=P,T3,：,consumer First=First.next,则会发生生产者加入队列的缓冲区丢失,临界资源,（,critical resource,）：,一次仅允许一个进程使用的资源,临界段,（,critical section),：,各进程必须互斥执行的程序段。,