并发执行问题

第七讲并发执行问题目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；同步与互斥问题。重点与难点：并行程序中的同步与互斥作业：例举两个现实生活中需要同步与互斥的例子。第4章进程同步与通讯、进程死锁并发的需求操作系统应尽量支持用户态程序最大限度地并行执行。程序设计要利用OS对并行运行的支持，安排并行事务并行执行。操作系统核心程序也要尽可能地并发运行4.1并发程序传统的串行程序存在着并行成分：Read(a)；Read(b)；c=a+b；Write(c)Read（a）和Read（b）两个语句可并发执行。识别程序中的并发成分有两种方法：–程序员写顺序程序，用识别工具识别并发成分。再组织使用操作系统的并发机制。–由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；或直接利用操作系统的系统调用/或高级并发程序库设计并发程序。并发程序设计语言---并发语句它是一种高级语言；语法形式：ParbeginS1；S2；…Sn；Parend；Si（i=1，2，…，n）是单个语句。Parbegin和Parend之间的语句可以并发执行。并发语句示例前面那个串行读写程序可以改为：Parbeginread（a）；read（b）；Parend；c=a+b；write（c）；并发语句描述手段的优缺点并发语句Parbegin/Parend的结构化特征非常好。但存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系。若能辅以其他手段（如本章后续将介绍的信号量机构），则并发语句可以大大增加其描述并发的能力。并发程序实现前面是对并发的高级语言描述，要真正实现并发执行，需要通过OS支持的进程机制。OS提供进程创建，结束和同步的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对OS的系统调用。与进程相关的系统调用UNIX操作系统利用进程支持并发执行；它提供了如下系统调用：–fork（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行，而父进程fork（）调用的返回值是子进程的进程标识pid；子进程fork（）调用的返回值是0。–exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。–wait（&status）：等待子进程结束。当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用exit（status）时的status值送到&status指针所指单元中。在控制返回调用者时，同时将所等到的子进程pid作为wait（）系统调用函数的返回值。–waitpid（pid，…）：等待pid所指定的进程结束。多进程实现前述的读写并发程序pid=fork（）ifpid==0then{read（b）；exit（0）；}elseread（a）；return_pid=wait（&status）；c=a+b；write（c）；4.2进程的互斥与同步互斥关系（亦称间接制约关系）:即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。同步关系（亦称直接制约关系）:指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而相互等待、相互交换信息所产生的制约关系。4.2.1临界段问题（互斥问题）例1：P1,P2两进程使用同一打印机。如果不互斥使用会交叉输出。Entrycodeexitcode使用打印机P1Entrycodeexitcode使用打印机P2ParbeginProgramA:beginN:=count;N:=N+$100;count:=N;end;ProgramB:beginM:=count;M:=M+$200;count:=M;end;Parend;例2:对共享变量count的互斥访问。互斥执行例3：有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲队列)。INSTNEXT共享N个缓冲区P1P2…PmC1C2…CnINSTNilINSTNEXTFirstINSTNEXTFirsttypeitem=…;#缓冲区中数据的类型typebuffer=recordinst:item;next:pointertobuffer;end;varP，C，First：pointertobuffer;nextp，nextc：item;First:=nil;数据结构new(P);#获得一空缓冲区P.inst:=nextp;P.next:=First;First:=P;untilfalse;end;ParbeginProducer：beginrepeat…produceaniteminnextp;...…consumetheiteminnextc;…untilfalse;end;Parend;Consumer：beginrepeatwhilefirst=nildoskip;#空循环等C:=First;first:=first.next;nextc:=C.inst;dispose(C);#释放缓冲区T0：consumerC:=FirstT1：producerP.next:=FirstT2：producerFirst:=PT3：consumerFirst:=First.next则会发生生产者加入队列的缓冲区丢失。临界资源（criticalresource）：一次仅允许一个进程使用的资源。临界段（criticalsection)：各进程必须互斥执行的程序段。