41并发执行问题

1、第七讲第七讲 并发执行问题并发执行问题 目的与要求目的与要求：了解并行程序的高级语言了解并行程序的高级语言表示与操作系统支持下的实现；了解同表示与操作系统支持下的实现；了解同步与互斥问题。步与互斥问题。重点与难点重点与难点：并行程序中的同步与互斥：并行程序中的同步与互斥作业作业：1，2, 3, 例举两个现实生活中需要例举两个现实生活中需要同步与互斥的例子。同步与互斥的例子。第四章第四章 进程同步与通讯、进程死锁进程同步与通讯、进程死锁 并发的需求并发的需求操作系统应尽量支持用户态程序最大限操作系统应尽量支持用户态程序最大限度地并行执行。度地并行执行。程序设计要利用操作系统对并行运行的程序设计要

2、利用操作系统对并行运行的支持（以进程或线程方式），安排并行支持（以进程或线程方式），安排并行事务并行执行。事务并行执行。操作系统核心程序也要尽可能地并发运操作系统核心程序也要尽可能地并发运行行4.1 4.1 并发编程并发编程计算任务存在并行成分计算任务存在并行成分s1s1和和s2s2两个子任务可并发执行两个子任务可并发执行 s1s3s2并发编程有三种方法：并发编程有三种方法：程序员写顺序程序，用识别工具识别程序员写顺序程序，用识别工具识别并发成分，再组织使用操作系统的并并发成分，再组织使用操作系统的并发机制。发机制。由程序员识别并发成分，用并发程序由程序员识别并发成分，用并发程序设计语言设计并

3、发程序，由编译系统设计语言设计并发程序，由编译系统安排并发；安排并发；或直接利用操作系统的系统调用或直接利用操作系统的系统调用/ /高级高级并发程序库设计并发程序。并发程序库设计并发程序。并发程序设计语言并发程序设计语言 - - 并发语句并发语句是在传统高级语言基础上增加描述并行是在传统高级语言基础上增加描述并行的语句。的语句。 语法形式语法形式 parbegin s1parbegin s1；s2s2； snsn； parendparend； sisi（i=1i=1，2 2，n n） 是单个语句是单个语句 parbeginparbegin和和parendparend之间的语句可以并发执之间的语

4、句可以并发执行行并发语句示例并发语句示例前面那个计算任务可以描述为：前面那个计算任务可以描述为：parbeginparbegin s1s1； s2s2； parendparend； s3s3并发语句描述手段的优缺点并发语句描述手段的优缺点并发语句并发语句parbegin/parendparbegin/parend的结构化特征的结构化特征非常好非常好但存在着描述能力不强的缺点，即存在但存在着描述能力不强的缺点，即存在着用着用parbegin/parendparbegin/parend语句无法描述的并语句无法描述的并发优先关系（如下图）。发优先关系（如下图）。若能辅以其它手段（如本章后续将介绍若能

5、辅以其它手段（如本章后续将介绍的信号量机构），则并发语句可以大大的信号量机构），则并发语句可以大大增加其描述并发的能力。增加其描述并发的能力。 s1s2s3s4s5s6s7并发执行实现并发执行实现前面是对并发的高级语言描述，要真正前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统支持实现并发执行，需要通过操作系统支持的进程（或线程）机制。的进程（或线程）机制。操作系统提供操作系统提供进程（线程）创建，结束进程（线程）创建，结束和同步和同步的系统调用，可直接提供给用户的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将编写并行程序；或由并行语言编译器将并发语言的语句转化为

6、对操作系统的系并发语言的语句转化为对操作系统的系统调用。统调用。与进程相关的系统调用与进程相关的系统调用unix-alikeunix-alike操作系统利用进程（或线程）操作系统利用进程（或线程）支持并发执行支持并发执行它提供了如下系统调用：它提供了如下系统调用： forkfork（）：创建一个新进程。该系统调用执（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理

7、机后，都从还是子进程，在占有处理机后，都从forkfork（）（）调用的返回点开始运行，而父进程调用的返回点开始运行，而父进程forkfork（）（）调用的返回值是子进程的进程标识调用的返回值是子进程的进程标识pidpid；子；子进程进程forkfork（）调用的返回值是（）调用的返回值是0 0。 exitexit（statusstatus）：进程结束。该系统调用发）：进程结束。该系统调用发出后，操作系统将从系统中删除调用出后，操作系统将从系统中删除调用exitexit的的进程，并将进程，并将statusstatus值传给等待它结束的父进值传给等待它结束的父进程。程。 waitwait（&st

8、atus&status）：等待子进程结束。当有）：等待子进程结束。当有多个子进程时，任一个子进程结束即将控制多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用返回调用者，并将子进程调用exitexit（statusstatus）时的时的statusstatus值送到值送到&status&status指针所指单元中。指针所指单元中。在控制返回调用者时，同时将所等到的子进在控制返回调用者时，同时将所等到的子进程程pidpid作为作为waitwait（）系统调用函数的返回值。（）系统调用函数的返回值。 waitpidwaitpid（pidpid，）：等待）：等待pidpid所指定的进所

9、指定的进程结束。程结束。多进程实现前述的计算任务并发多进程实现前述的计算任务并发pid =forkpid =fork（ ）；）；if (pid =0 )thenif (pid =0 )then s2s2；exitexit（0 0）；）； elseelses1s1；waitwait（）；（）；s3s3；4.2 4.2 进程的互斥与同步进程的互斥与同步同步关系同步关系（亦称直接制约关系）（亦称直接制约关系） 指完成同一任务的伙伴进程间，因需要指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而等待、在某些位置上协调它们的工作而等待、传递信息所产生的制约关系。传递信息所产生的制约关系。互斥

10、关系互斥关系（亦称间接制约关系）（亦称间接制约关系） 即进程间因相互竞争使用独占型资源即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。（互斥资源）所产生的制约关系。4.2.1 4.2.1 同步与临界段问题同步与临界段问题例例1 1：同步问题。如果进程：同步问题。如果进程p1p1执行执行s1s1，s3s3进程进程p2p2执行执行s2s2，则，则p1p1在执行在执行s3s3之前必须等之前必须等待待p2p2执行完执行完s2s2。s1s3s2例例2 2： p1p1、p2p2两进程使用同一打印机。如两进程使用同一打印机。如果不互斥使用会交叉输出果不互斥使用会交叉输出entry codeen

11、try codeexit codeexit code使用打印机使用打印机p1p1entry codeentry codeexit codeexit code使用打印机使用打印机p2p2parbegin a(amount) r1=balance; r2=amount; r1=r1+r2; balance=r1; ; b(amount) r1=balance; r2=amount; r1=r1-r2; balance=r1; ;parend;例例3: 3: 对共享变量对共享变量balancebalance的互斥访问的互斥访问互斥执行互斥执行例例4 4：有限缓冲区的生产者：有限缓冲区的生产者/ /消

12、费者问题消费者问题（生产者和消费者共享一个产品缓冲链）（生产者和消费者共享一个产品缓冲链）instnext共享n个缓冲区p1 p2 pm c1 c2 cninstnilinstnextfirstinstnextfirst typedef structtypedef struct item item； / / 消息类型消息类型 typedef structtypedef structstruct buffer struct buffer * *next;next;struct item inststruct item inst； buffer buffer； / / 缓冲类型缓冲类型struct

13、 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= firstt1