页数：50页文件大小：194.2 KB来源： 操作系统ppt课件
本课件讲解操作系统中的并行性与进程同步互斥问题。先对比顺序程序设计与并行程序设计，介绍程序并行性的有向图与并行语言表示；随后重点展开临界段概念与设计原则、中断屏蔽与硬件指令等互斥实现方法、信号量及 wait/signal 操作的物理意义与实现方式；进而用信号量求解生产者与消费者、阅读者与写入者等经典同步问题；最后介绍进程通信、管程概念及 Windows NT 的同步和互斥机制。
第五章 并行性：互斥和同步：为了充分利用计算机各部分的能力，使之并行运行以提高计算机系统的效率和性能，计算机界一直在坚持不懈地、不遗余力地发展并行技术。
多道程序设计基础——并行程序设计
5.1 顺序程序设计和并行程序设计
传统程序设计方法：顺序程序设计
多道程序环境程序设计方法：并行程序设计
程序并行性的表示之一：有向图。本页以有向图方式表示程序的并行性，给出串行、并行与一般三种前趋关系示意（S 起始、F 终止，中间为 P1～P7 各程序段）。
程序并行性的表示之二：并行语言。并行语言包括并行 PASCAL、CSP/K 语言、MODULA 语言、扩充的 Ada 等；并行语句记号使用 COBEGIN / COEND 表示可并行执行的语句块。
SF+***/--BEGINCOBEGINt1=a-bt2=c-dt3=e/fCOENDCOBEGINt4=t1*t2t5=t3**2COENDt6=t4+t5END程序并行性表示举例算数表达式求值:(a-b)*(c-d)+(e/f)**2t5t1t3t2t4t6a b c d e f2并行程序设计的特点
5.2 进程间的同步与互斥
进程间的关系
临界段（Critical Section）问题：当两个以上进程共享某个变量时，一次只能允许一个进程对共享变量进行写操作（即互斥地进行），否则共享变量的值将取决于各进程访问它的先后次序，从而产生错误结果。
临界段设计原则
临界段实现方法
中断屏蔽方法：一个进程正使用处理器执行它的临界段代码，为防止其他进程进入它们的临界段的简单直接的方法是禁止一切的中断发生，即为中断屏蔽。
中断屏蔽的典型模式屏蔽中断（disable interrupts）；进程的Pi的临界段代码CSi；开中断（enable interrupts）;硬件指令
硬件指令的优点
检测和设置指令(功能描述)functionTest_and_Set(varflag:boolean):booleanbeginTest_and_Set:=flag;flag:=true;endZ-8000:TEST;IBM370: TS交换指令(功能描述)交换两个字的内容.procedureSwap(vara,b:boolean)vartemp:boolean;begintemp:=a;a:=b;b:=temp;endIntel 8086/8088: XCHG用硬件指令实现进程互斥：加锁／解锁。为每个临界段或其它互斥资源设置一个布尔变量，如 lock：false 表示临界段未被使用，true 表示正在使用；进程进入临界段前用硬件指令测试并设置 lock，退出时将其清为 false。
“忙等待”问题：一个进程为进入正处于“忙状态”的临界段中（即已有进程在该共享变量的临界段中执行），需要不停地测试临界段代码，从而浪费 CPU 时间。
信号量（semaphore）
wait、signal 操作的实现：依进程等待方式不同，wait 操作的执行方式也不同。
Wait，signal操作的“忙等待”执行方式Wait(S):While S<=0 do skip;S: =S-1;Signals(S):S: =S+1;Wait，signal操作的“阻塞等待”执行方式wait(S):S.value:=S.value-1;ifS.value<0then beginInsert(CALLER,S.L);Block(CALLER);endsignal(S):S.value:=S.value+1;ifS.value<=0then beginRemove(S.L,id);Wakeup(id);end5.3 同步机构应用
用信号量实现进程间的互斥：资源为临界段，可用单位数为 1。mutex 为互斥信号量（mutual exclusion），最多只允许一个进程进入临界段。
互斥信号量mutex在n个进程间实现互斥varmutex:Shared Semaphore;beginmutex:=1;begincobeginrepeatP1:…;wait(mutex);...进程Pi的临界段代码CS;Pi:signal(mutex);...进程Pi的其它代码Pn:…;forevercoendendend信号量实现进程的阻塞和唤醒：资源的分配和释放是指进程所等待的资源被其他进程释放成为可用（互斥）。信号量按每类资源设置一个，初值等于该类资源的单位数；进程申请时执行 wait，释放时执行 signal 并唤醒等待者。
协同进程举例进程i要等待j的计算结果进程i进程j进行计算;进行计算;wait(Proc_sem(i));signal(Proc_sem(i));继续计算；继续计算；阻塞：自己阻塞自己，不能阻塞其他进程（进程自己在非正信号量上执行wait操作）；唤醒：由其他进程唤醒，不能自己唤醒自己（其他进程在信号量为-1时执行signal操作）。生产者和消费者问题是计算机系统中的常见问题：输入进程 Pi 把数据送入缓冲区，计算进程 Pc 从缓冲区取出数据加工，打印进程 Pp 再把结果输出。输入时缓冲区为空才能送入，输出时缓冲区为满才能取出。
问题的处理
生产者／消费者问题————进程同步关系的描述varE,F: Semaphore；muntex: binary Semaphore;Procedure producerbeginrepeatwait(E);wait(mutex);“分给空缓冲区并调整指针P的临界段”；Signal(mutex);“向缓冲区中装入数据”；Signal(F);foreverendProcedure Consumersbegin repeatwait(F);wait(mutex);“分给满缓冲区并调整指针C的临界段”；signal(mutex);“从缓冲区中取出数据”；signal(E);foreverendvarmutex，empty,full:Shared Semaphore;buffer:array[0..n-1] of message;mutex:=1;empty:=n;full:=0;in,out:0..n-1;begincobeginproducer:beginrepeat... Produce message m;P(empty); P(mutex);buffer(in):=m;in:=(in+1) mod n;V(mutex);V(full);foreverendconsumer:beginrepeat…P(full); P(mutex);m:=buffer(out);out:=(out+1) mod n;V(mutex);V(empty);consume message m;foreverendcoendend阅读者和写入者问题：N 个并行进程共享一个数据集，有些进程只要求读（阅读者），而另一些进程要求修改（写入者）。要求多个阅读者可同时读，写入者必须独占访问。
varmutex,wrt:Semaphore;readcount:integer;mutex:=wrt:=1;readcount:=0;cobeginReaderi:beginP(mutex);readcount:=readcount+1;ifreadcount=1thenP(wrt);V(mutex);读数据集；P(mutex);readcount:=readcount-1;ifreadcount=0thenV(wrt);V(mutex);endWriteri:beginP(wrt);写数据集；V(wrt);end;coend练习：读者优先=>写入者优先写入优先Varm,w,s,mutwx,k:semaphore;RC,WC:integer;beginm:=w:=s:=mutex:=k:=1;RC:=WC:=0;cobeginREADER:repeatP(m);P(w);P(mutex);if RC=0 then P(s);RC:=RC+1;V(mutex);V(w);V(m);阅读；P(mutex);RC:=RC-1;if RC=0 then V(s);V(mutex);foreverWRITER:repeatP(k);if WC=0 then P(w);WC:=WC+1;V(k);P(s);写入；V(s);P(k);WC:=WC-1;if WC=0 then V(w);V(k);forevercoendend5.4 进程间的通信：一个作业可划分为若干个可并行执行的进程，它们协同完成一个工作（同步），为此需要在进程之间交换一定数量的信息，这就是进程通信。
5.5 管程的概念：互斥手段（测试和设置命令、P、V 操作）的不足在于由用户编写控制代码，加重了用户负担；P、V 操作分散在用户程序中，不易管理和维护。为此引入管程，把共享资源及其操作集中封装起来。
五位就餐的哲学家问题
数据描述：管程的构成包括描述共享资源（叉子状态）的数据结构，Forks(i) 指第 i 个哲学家可用叉子数，取值为 0、1、2；以及描述对叉子进行操作的一组过程。
管程问题描述框架ForksControl:monitortypeT=array[0..4]of integer;B=array[0..4]of boolean;varForks,Right,Left:T;Ready:B;i:integer;procedure entryPickUp(varme:integer);begin ifForks(me)<>2thenwait(Ready(me));Forks(Right(me)):=Forks(Right(me))-1;Forks(Left(me)):=Forks(Left(me))-1;endprocedure entryPutDown(varme:integer);beginForks(Right(me)):=Forks(Right(me))+1;Forks(Left(me)):=Forks(Left(me))+1;ifForks(Right(me))=2thenSignal(Right(me));ifForks(Left(me))=2then Signal(Left(me));end40213过程描述begin fori=0to4do beginForks(i):=2;Right(i):=[i+1]mod5;Left(i):=[i+4]mod5;Ready(i):=false;endcobeginPhilosopher 0:Process（varhungry:boolean）;begin repeat ifhungry=true then beginForksControl.PickUp(0);吃通心粉；ForksControl.PutDown(0);endforeverendPhilosopher 1:Process;…...Philosopher 4:Process;…coendend赋初值402135.6 Windows NT 中的同步和互斥机制：NT 是多机操作系统，支持对称多处理模式，同步和互斥由多种机制实现。内核中的同步和互斥机制用于保护内核数据结构在多线程环境下的正确访问。
Windows NT 的同步与通信机制
下载地址：202.114.22.9:21//incoming/other/课件 共享帐号：HUST 密码：HUST
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}