操作系统4-1.ppt

1、第七讲 并发执行问题,目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；同步与互斥问题。了解解决互斥问题的软件算法。 重点与难点：并行程序中的同步与互斥 作业：7，例举两个现实生活中需要同步与互斥的例子。,第四章 进程同步与通讯、进程死锁 并发的需求,操作系统利用进程（线程）机制支持用户态程序最大限度地并行执行。 操作系统核心程序也要尽可能地并发运行,4.1 并发程序,传统的串行程序存在着并行成分 Read (a)； Read (b)； c = a + b； Write (c),Read（a）和Read（b）两个语句如果不通过同一输入设备则可并发执行,识别算法中的并发成分有两种方法

2、： 程序员写顺序程序，用并行识别工具识别并发成分。组织使用操作系统的并发机制。 由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；或直接利用操作系统的系统调用/或高级并发程序库设计并发程序。,并发程序设计语言 - 并发语句,是一种高级语言 语法形式 Parbegin S1；S2； Sn； Parend； Si（i=1，2，n） 是单个语句 Parbegin和Parend之间的语句可以并发执行,并发语句示例,前面那个串行读写程序可以改为 Parbegin read（a）； read（b）； Parend； c= a+b； write（c）；,并发语句描述手段的优缺点,并发

3、语句Parbegin/Parend的结构化特征非常好 但存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系。 若能辅以其它手段（如本章后续将介绍的信号量机制），则并发语句可以大大增加其描述并发的能力。,并发程序实现,前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统的进程机制。 操作系统提供进程创建，结束和同步的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对操作系统的系统调用。,与进程相关的系统调用,Unix操作系统利用进程（或线程）支持并发执行 它提供了如下系统调用： fork（）：创建一个新进程。该

4、系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行，而父进程fork（）调用的返回值是子进程的进程标识号；子进程fork（）调用的返回值是0。,exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。 wait（ N:=N+$100; count:=N; end; Program B: begin M:=count; M:=M-$200; count:=M; end; Pare

5、nd;,例3: 对共享变量count的互斥访问,例4：有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲队列）,共享N个缓冲区,P1 P2 Pm C1 C2 Cn,type item=; #缓冲区中数据的类型 type buffer=record inst: item; next: pointer to buffer; end; var P，C，First：pointer to buffer; nextp，nextc：item; First:= nil;,数据结构,new(P); #获得一空缓冲区 P.inst:=nextp;把数据送到缓冲区 P.next:=First; Firs

6、t:=P; until false; end;,Parbegin Producer： begin repeat produce an item in nextp; ., consume the item in nextc; until false; end; Parend;,Consumer： begin repeat while first=nil do skip; #空循环等 C:=First; first:=first.next; nextc:=C.inst;取出数据 dispose(C); #释放缓冲区,T0：consumer C:= First T1：producer P.next:

7、= First T2：producer First:= P T3：consumer First:= First.next 则会发生生产者加入队列的缓冲区丢失,临界资源（critical resource）：一次仅允许一个进程使用的资源 临界段（critical section) ：各进程必须互斥执行的程序段。,解决临界段问题的软件算法必须遵循： 准则1：不能虚设硬件指令或假设处理机数目。 准则2：不能假设n个进程的相对速度。 准则3：当一个进程未处于其临界段时，不应阻止其它进程进入临界段。 准则4：当若干进程欲进入临界段时，应能在有限时间内选出一个进程进入其临界段。,4.2.2 实现互斥的软件

8、算法,进入临界段之前要申请，获得批准方可进入； 退出临界段之后要声明，以便其他进程进入。,协调各进程入临界段的调度原则： 当无进程处于临界段时，允许一个进程立即进入临界段。 当已有进程进入临界段时， 其它试图进入的进程必须等待 当某进程退出临界段时，若有等待进入临界段的进程，则应选取一个进入临界段。 软件算法举例:,Pi 表示一个进程 Pj 表示另一个进程 （i=0, 1； j=1- i ）,Repeat,While turni do skip ;,turn= j ;,Critical section,Non-ritical section,Until false;,算法1：设一个共享的整型变

9、量turn（0，1）表示轮流进入,不满足准则3:当一个进程未处于其临界段时，不应阻止其它进程进入临界段。,Repeat,While flagj do skip flagi = true；,flagi = false；,Critical section,Non-critical section,Until false;,算法2：设一个表示进程进入否状态的数组 Var flag：array0.1 of boolean,不满足互斥要求：当flag初值为0，两进程同时执行while语句时。,Repeat,flagi = true； While flagj do skip；,flagi = false；

10、,Critical section,Non-ritical section,Until false;,算法3：设一个表示进程状态的数组 Var flag：array0.1 of boolean,不满足准则4：当若干进程欲进入临界段时，应能在有限时间内选出一个进程进入其临界段。（两进程同时置flag),Repeat,flagi = false；,Critical section,Non-ritical section,Until false;,算法4：在标志置true的时候注意一下 对方的状态,不满足准则4（在此被打断后，对方进程可能置上true）,flagi = true；,While flagj do,begin,flagi = false；,While flagj do skip；,flagi = true；,end,turn = j; flagi = false；,算法5：设一个表示进程状态的数组和一个令牌 Var flag：a