4.1并发执行问题

第七讲并发执行问题,目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；了解同步与互斥问题。重点与难点：并行程序中的同步与互斥作业：1，2,3,例举两个现实生活中需要同步与互斥的例子。,第四章进程同步与通讯、进程死锁并发的需求,操作系统应尽量支持用户态程序最大限度地并行执行。程序设计要利用操作系统对并行运行的支持（以进程或线程方式），安排并行事务并行执行。操作系统核心程序也要尽可能地并发运行,4.1并发编程,计算任务存在并行成分,S1和S2两个子任务可并发执行,S1,S3,S2,并发编程有三种方法：程序员写顺序程序，用识别工具识别并发成分，再组织使用操作系统的并发机制。由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；或直接利用操作系统的系统调用/高级并发程序库设计并发程序。,并发程序设计语言-并发语句,是在传统高级语言基础上增加描述并行的语句。语法形式ParbeginS1；S2；Sn；Parend；Si（i=1，2，n）是单个语句Parbegin和Parend之间的语句可以并发执行,并发语句示例,前面那个计算任务可以描述为：ParbeginS1；S2；Parend；S3,并发语句描述手段的优缺点,并发语句Parbegin/Parend的结构化特征非常好但存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系（如下图）。若能辅以其它手段（如本章后续将介绍的信号量机构），则并发语句可以大大增加其描述并发的能力。,并发执行实现,前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统支持的进程（或线程）机制。操作系统提供进程（线程）创建，结束和同步的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对操作系统的系统调用。,与进程相关的系统调用,Unix-alike操作系统利用进程（或线程）支持并发执行它提供了如下系统调用：fork（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行，而父进程fork（）调用的返回值是子进程的进程标识pid；子进程fork（）调用的返回值是0。,exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。wait（R2=amount;R1=R1+R2;balance=R1;B(amount)R1=balance;R2=amount;R1=R1-R2;balance=R1;Parend;,例3:对共享变量balance的互斥访问,例4：有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲链）,共享N个缓冲区,P1P2PmC1C2Cn,typedefstructitem；/消息类型typedefstructstructbuffer*next;structiteminst；buffer；/缓冲类型structbuffer*P，*C，*First;structitemnextp，nextc;First=nil;,数据结构,new(P);#获得一空缓冲区P.inst=nextp;P.next=First;First=P;while(1);,ParbeginProducer()doproduceaniteminnextp;.,consumetheiteminnextc;while(1);Parend;,Consumer()dowhile(first=nil);#空循环等C=First;first=first.next;nextc=C.inst;dispose(C);#释放缓冲区,T0：consumerC=FirstT1：producerP.next=FirstT2：producerFirst=PT3：consumerFirst=First.next则会发