41并发执行问题.ppt

第七讲 并发执行问题 目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；同步与互斥问题。了解解决互斥问题的软件算法。 重点与难点：并行程序中的同步与互斥 作业：7，例举两个现实生活中需要同步与互斥的例子。 第四章 进程同步与通讯、进程死锁 并发的需求 操作系统利用进程（线程）机制支持用户态程序最大限度地并行执行。 操作系统核心程序也要尽可能地并发运行 4.1 并发程序 传统的串行程序存在着并行成分 Read (a)； Read (b)； c = a + b； Write (c) Read（a）和Read（b）两个语句如果不通过同一输入设备则可并发执行 并发成分 识别算法中的并发成分有两种方法： 程序员写顺序程序，用并行识别工具识别并发成分。组织使用操作系统的并发机制。 由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；或直接利用操作系统的系统调用/或高级并发程序库设计并发程序。 并发程序设计语言 --- 并发语句 是一种高级语言 语法形式 Parbegin S1；S2； …Sn； Parend； Si（i=1，2，…，n） 是单个语句 Parbegin和Parend之间的语句可以并发执行 并发语句示例 前面那个串行读写程序可以改为 Parbegin read（a）； read（b）； Parend； c= a+b； write（c）； 并发语句描述手段的优缺点 并发语句Parbegin/Parend的结构化特征非常好 但存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系。 若能辅以其它手段（如本章后续将介绍的信号量机制），则并发语句可以大大增加其描述并发的能力。 并发程序实现 前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统的进程机制。 操作系统提供进程创建，结束和同步的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对操作系统的系统调用。 与进程相关的系统调用 Unix操作系统利用进程（或线程）支持并发执行 它提供了如下系统调用： fork（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行，而父进程fork（）调用的返回值是子进程的进程标识号；子进程fork（）调用的返回值是0。 exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。 wait（status）：等待子进程结束。当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用exit（status）时的status值送到status指针所指单元中。在控制返回调用者时，同时将所等到的子进程pid作为wait（）系统调用函数的返回值。 waitpid（pid，…）：等待pid所指定的进程结束。 多进程实现前述的读写并发程序示意 （假设a，b都在两进程都可访问的共享区） pid = fork（ ）； if pid = = 0 then { read（b）； exit（0）；} else read（a）； return_pid = wait（status）； c = a+b； write（c）； 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 Program A: begin N:=count; N:=N+$100; count:=N; end; Program