《第六章 进程间互斥、同步与通信(操作系统原理).ppt》由会员分享，可在线阅读，更多相关《第六章 进程间互斥、同步与通信(操作系统原理).ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 进程间互斥、同步与通信授课教师：付勇智西南林学院 基础部数理教研室问题纲要间接制约和直接制约是什么？什么是临界区？什么是信号量？什么是同步、互斥？如何应用信号量实现同步和互斥？信号量在Windows编程中是如何实现的？进程并发运行所带来的问题由于系统资源的共享性，并发进程的执行结果失去了封闭性和可再现性。满足Bernstein条件的并发进程能够保持封闭性，但是Bernstein条件限制太过严格，不符合大多数实际环境的需要。因而，OS需要寻求一种机制，满足进程间共享资源的需要。进程间通信IPC在两个或多个进程间传递信息或共享数据的机制，称之为进程间通信（Inter-Process Com
2、munication）UNIX操作系统中的管道技术（Pipe）就是一种IPC在IPC的过程中，主要要解决两类问题：互斥和同步互斥的需要void SendPrint()1 if(in+1)%N=out)2 exit(0);3 else4 in=(in+1)%N;5 filein=printfile;6 return;ProcessA()SendPrint()ProcessB()SendPrint()临界区（Critical Section)临界资源：一次仅允许一个进程使用的资源称为临界资源。临界区：进程中对于临界资源访问的程序段称为临界区。间接制约：由于共享某一公有资源而引起的在临界区内不允许并
3、发进程交叉执行的现象，称为由共享公有资源造成的并发进程执行速度的间接制约，简称间接制约。互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致他们不能同时进入临界区称为互斥。互斥（Mutual Exclusion）互斥方案应满足的4个条件任何两个进程不能同时处于临界区不应对CPU的数目和速度做任何假设临界区外的进程不得阻塞其他进程不得使进程在临界区外无休止地等待互斥的实现方案关中断锁变量严格轮换法Peterson方案TSL硬件指令（Intel平台为BTS指令）信号量管程消息传递关中断处理机的调度都是由中断所引起的（主要是定时器中断）处理机的调度都是由中断所引起的（主要是定时器中断）如
4、果进入临界区前将所有外部中断屏蔽，则在运行临界如果进入临界区前将所有外部中断屏蔽，则在运行临界区时将不会响应所有外部中断事件，也就不可能发生进区时将不会响应所有外部中断事件，也就不可能发生进程切换，待进程执行完临界区后再开中断。程切换，待进程执行完临界区后再开中断。缺点：交由用户进程管理中断的开关是非常不安全的，缺点：交由用户进程管理中断的开关是非常不安全的，一旦用户程序关中断后忘记打开，则整个系统将无法响一旦用户程序关中断后忘记打开，则整个系统将无法响应外部事件而崩溃；另外，在多处理器系统中，关中断应外部事件而崩溃；另外，在多处理器系统中，关中断也仅屏蔽本处理器的中断响应，对其他处理器中运行
5、的也仅屏蔽本处理器的中断响应，对其他处理器中运行的进程无法屏蔽。进程无法屏蔽。因而通常中断屏蔽都由因而通常中断屏蔽都由OSOS进行管理，由进行管理，由OSOS使用它来保证使用它来保证一些核心操作的不可中断性。一些核心操作的不可中断性。锁变量intint lock=0;lock=0;/初始情况下没有进程进入临界区初始情况下没有进程进入临界区ProcessiProcessi()()while(lock=1);while(lock=1);/当其他进程在临界区工作时，忙等待当其他进程在临界区工作时，忙等待lock=1;lock=1;/设置锁变量，防止其他进程进入设置锁变量，防止其他进程进入critic
6、al_sectioncritical_section();();/进行临界区相关操作进行临界区相关操作lock=0;lock=0;/退出临界区后解锁，使其他进程可以进入退出临界区后解锁，使其他进程可以进入non_critical_sectionnon_critical_section();();严格轮转法Peterson方案TSL指令（测试与设置指令）Intel CPU中对应的中对应的TSL指令汇编指令码为指令汇编指令码为BTS信号量(semaphore)信号量使信号量使E.W.DijkstraE.W.Dijkstra在在19651965年提出的一种方法，年提出的一种方法，他建议引入一个新的变
7、量类型，称作信号量。信他建议引入一个新的变量类型，称作信号量。信号量是一个整数，其值可以为号量是一个整数，其值可以为0 0或某个正整数，或某个正整数，分别表示不可进入临界区以及能够进入的进程数分别表示不可进入临界区以及能够进入的进程数目。目。信号量：是一个仅能由同步原语对其进行操作的信号量：是一个仅能由同步原语对其进行操作的整型变量。整型变量。原语（原子操作）：操作过程不可中断，必须以原语（原子操作）：操作过程不可中断，必须以一个整体进行执行地系统基本操作一个整体进行执行地系统基本操作对于信号量操作的原语只有两个：对于信号量操作的原语只有两个：UPUP和和DOWNDOWNDOWN原语（P操作）
8、(1)若信号量S大于0，则将S减1，P操作返回，该进程继续执行(2)若信号量S等于0，则将进程挂入S的等待队列，将进程设置为阻塞状态，并转调度程序P原语原语S0S=S-1返回返回调用进程进入等待队列调用进程进入等待队列转进程调度转进程调度是否UP原语（V操作）(1)若信号量S的等待队列中有等待进程，则取队首进程，将其置为就绪状态并返回。(2)否则信号量S加1，并放回V原语原语是否有等待进程是否有等待进程S=S+1返回返回取队首进程置为就绪态取队首进程置为就绪态否是生产者消费者问题问题描述：两个进程共享一个公共的固定大小的缓问题描述：两个进程共享一个公共的固定大小的缓冲区。其中的一个，生产者，将
9、信息放入缓冲区；冲区。其中的一个，生产者，将信息放入缓冲区；另一个，消费者，从缓冲区中取出信息。另一个，消费者，从缓冲区中取出信息。当缓冲区已满，而此时生产者还想向其中放入一个当缓冲区已满，而此时生产者还想向其中放入一个新的信息则让生产者睡眠，待消费者从缓冲区取走新的信息则让生产者睡眠，待消费者从缓冲区取走一个或多个信息时再唤醒它。一个或多个信息时再唤醒它。当消费者试图从缓冲区中取信息而发现缓冲区为空当消费者试图从缓冲区中取信息而发现缓冲区为空时，它就睡眠，直到生产者向其中放入一些消息再时，它就睡眠，直到生产者向其中放入一些消息再将其唤醒。将其唤醒。生产者过程消费者过程直接制约与同步一组在异步
10、环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。异步环境下的一组并发进程，因直接制约而互相发送消息而进行相互合作、相互等待，使得各进程按一定的速度执行的过程称为进程间的同步。生产者消费者问题信号量定义#define N 100semaphore mutex=1;/互斥信号量semaphore empty=N;/开始时候可用的消息缓冲区数为Nsemaphore full=0;/开始时候可用的消息为0生产者进程void producer()void producer()intint item;item;while(truewhile(tr
11、ue)produce-produce-item(&itemitem(&item););/产生消息产生消息down(emptydown(empty););/获得一个消息缓冲块获得一个消息缓冲块down(mutexdown(mutex););/对消息的缓冲要互斥对消息的缓冲要互斥enter-enter-item(itemitem(item););/将消息送入缓冲区将消息送入缓冲区up(mutexup(mutex););/互斥结束互斥结束up(fullup(full););/增加一个可用消息增加一个可用消息 消费者进程void consumer()void consumer()intint item
12、;item;while(truewhile(true)down(fulldown(full););/获得一可用消息获得一可用消息down(mutexdown(mutex););/互斥访问消息缓冲区互斥访问消息缓冲区get-get-item(&itemitem(&item););/取得消息并从队列删除取得消息并从队列删除up(mutexup(mutex););/结束互斥结束互斥up(emptyup(empty););/增加一个空缓冲区增加一个空缓冲区 哲学家进餐问题五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉，由于通心粉很滑，所以要两把叉子才能夹住。相邻两盘子之间有一把叉子，餐具摆
13、放如右图所示哲学家生活的过程哲学家的生活包括两种活动：即吃饭和思考。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次得到一把，并且不分次序。如果成功的获得两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。问题：为每一个哲学家写一段程序来描述其行为，要求不能死锁。不正确解法#define N 5#define N 5void void philosopher(intphilosopher(int i)i)while(truewhile(true)think();think();take-take-fork(ifork(i););take-fork(i+1)%N);take-for
14、k(i+1)%N);eat();eat();put-put-fork(ifork(i););put-fork(i+1)%N);put-fork(i+1)%N);低效率的互斥可行解法#define N 5#define N 5semaphorsemaphor mutexmutex=1;=1;void void philosopher(intphilosopher(int i)i)while(truewhile(true)think();think();down(mutexdown(mutex););take-take-fork(ifork(i););take-fork(i+1)%N);take-
15、fork(i+1)%N);eat();eat();put-put-fork(ifork(i););put-fork(i+1)%N);put-fork(i+1)%N);up(mutexup(mutex););经典解法#define N 5#define N 5#define LEFT(i-1)%N#define LEFT(i-1)%N#define RIGHT(i+1)%N#define RIGHT(i+1)%N#define THINKING 0#define THINKING 0#define HUNGRY 1#define HUNGRY 1#define EATING 2#define E
16、ATING 2intint stateNstateN semaphore semaphore mutexmutex=1=1semaphore semaphore sNsN=0,0,.,0=0,0,.,0哲学家过程void void philosopher(intphilosopher(int i)i)while(true)while(true)think();think();take-take-forks(iforks(i););eat();eat();put-put-forks(iforks(i););void void test(itest(i)if(if(stateistatei=HUN
17、GRY&=HUNGRY&stateLEFTstateLEFT!=!=EATING&EATING&stateRIGHTstateRIGHT!=EATING)!=EATING)stateistatei=EATING;=EATING;up(siup(si););哲学家的两个主要动作void take-void take-forks(intforks(int i)i)down(&mutexdown(&mutex););stateistatei=HUNGRY;=HUNGRY;test(itest(i););up(mutexup(mutex););down(sidown(si););void put-vo
18、id put-forks(intforks(int i)i)down(mutexdown(mutex););stateistatei=THINKING;=THINKING;test(LEFTtest(LEFT););test(RIGHTtest(RIGHT););up(mutexup(mutex););读者写者问题设想一个飞机订票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但一个进程正在更新数据库，则所有其他进程都不能访问数据库，即使读操作也不行。问题：如何对读者和写者编写线程？semaphore semaphore mutexmutex=1;=1;semapho
19、re db=1;semaphore db=1;intint rcrc=0;=0;void reader()void reader()while(true)while(true)down(mutexdown(mutex););rcrc+=1;+=1;if(if(rcrc=1)=1)down(dbdown(db););up(mutexup(mutex););read-data-base();read-data-base();down(mutexdown(mutex););rcrc=rc-1;=rc-1;if(if(rcrc=0)=0)up(dbup(db););up(mutexup(mutex);
20、);use-data-read();use-data-read();写者过程void writer()void writer()while(truewhile(true)think-up-data();think-up-data();down(dbdown(db););write-data-base();write-data-base();up(dbup(db););理发师睡觉问题理发店里有一位理发师、一把理发椅和理发店里有一位理发师、一把理发椅和n n把供等把供等候理发顾客坐的椅子。如果没有顾客，则理发师候理发顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。便在理发椅上睡觉。当一个顾客
21、到来时，他必须叫醒理发师；如果一当一个顾客到来时，他必须叫醒理发师；如果一个顾客到来时理发师正在理发，则如果有空椅子个顾客到来时理发师正在理发，则如果有空椅子可以坐，他们就坐下来等待；如果没有空椅子，可以坐，他们就坐下来等待；如果没有空椅子，他们就离开。他们就离开。问题：为理发师和顾客各编写一段程序，描述他问题：为理发师和顾客各编写一段程序，描述他们的行为，要求不能带有竞争条件。们的行为，要求不能带有竞争条件。信号量定义#define CHAIRS 5/椅子数目semaphore customers=0;/顾客数目semaphore barbers=0;/等候顾客的理发师数目semaphore
22、 mutex=1;/等待队列互斥信号量int waiting=0;/等待队列void barber()void barber()while(truewhile(true)down(customersdown(customers);down(mutexdown(mutex););waiting-;waiting-;up(barbersup(barbers););up(mutexup(mutex););cut-hair();cut-hair();void customer()void customer()down(mutexdown(mutex););if(waitingCHAIRS)if(wai
23、tingCHAIRS)waiting+;waiting+;up(customersup(customers););up(mutexup(mutex););down(barbersdown(barbers););get-haircut();get-haircut();else else up(mutexup(mutex););司机售票员问题一辆公共汽车上有一名司机和一名售票员，司机的工作是不停的循环执行如下步骤：“开车正常行车到站停车”，售票员的工作是不停的执行如下工作：“开车门等候乘客上车关车门售票”售票员必须等车到站停车后才能开车门；司机也必须等售票员关车门以后才能开车问题：试写两段程序，分
24、别描述司机和售票员的工作过程。司机、售票员问题 到站停车到站停车到站停车到站停车 开开开开 车车车车 开开开开 车车车车 门门门门 关关关关 车车车车 门门门门 售售售售 票票票票 正常行车正常行车正常行车正常行车。售票员售票员司机司机semaphore driving=0;semaphore driving=0;semaphore door=1;semaphore door=1;void driver()void driver()while(truewhile(true)down(drivingdown(driving););开车开车();();正常行车正常行车();();到站停车到站停车(
25、);();up(doorup(door););void ticket-seller()void ticket-seller()while(truewhile(true)down(doordown(door););开门开门();();等待乘客上车等待乘客上车();();关门关门();();up(drivingup(driving););售票售票();();两学校交通问题在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M，可供两辆自行车在从两端进入小路的情况下错车使用，如下图所示，试设计一个算法使来往的自行车均可顺利通过。学校交通图示
26、M天津大学天津大学南开大学南开大学SKTLsemaphore S2T=1;semaphore S2T=1;semaphore T2S=1;semaphore T2S=1;semaphore SK=1;semaphore SK=1;semaphore TL=1;semaphore TL=1;semaphore M=2;semaphore M=2;void bikeS2T()void bikeS2T()down(S2T);down(S2T);down(SKdown(SK););go-S-K();go-S-K();down(Mdown(M););get-in-M();get-in-M();up(SK
27、up(SK););down(TLdown(TL););up(Mup(M););go-L-T();go-L-T();up(TLup(TL););up(S2T);up(S2T);void bikeT2S()void bikeT2S()down(T2S);down(T2S);down(TLdown(TL););go-T-L();go-T-L();down(Mdown(M););get-in-M();get-in-M();up(TLup(TL););down(SKdown(SK););up(Mup(M););go-K-S();go-K-S();up(SKup(SK););up(T2S);up(T2S)
28、;Windows中的IPC实现信号量的创建HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,/SD LONG lInitialCount,/initial count LONG lMaximumCount,/maximum count LPCTSTR lpName/object name);DOWN操作DWORD WaitForSingleObject(HANDLE hHandle,/handle to object DWORD dwMilliseconds/time-out interval);UP操作BOO
29、L ReleaseSemaphore(HANDLE hSemaphore,/handle to semaphore LONG lReleaseCount,/count increment amount LPLONG lpPreviousCount/previous count);示例.打开窗口数目的限制功能：通过一个循环，打开五个窗口，但同一时功能：通过一个循环，打开五个窗口，但同一时刻最多只能有三个窗口打开。刻最多只能有三个窗口打开。试用试用DOWNDOWN、UPUP操作先编写程序完成以上要求操作先编写程序完成以上要求semaphore count=3;semaphore count=3;O
30、penActionOpenAction()()DOWN(countDOWN(count););DrawWindowDrawWindow();();while(while(WindowStateWindowState()!=Close);()!=Close);UP(countUP(count););Windows平台实现#include#include stdafx.hstdafx.h HANDLE HANDLE hSemaphorehSemaphore;LONG LONG cMaxcMax=3;=3;DWORD WINAPI DWORD WINAPI thread_func(LPVOIDthr
31、ead_func(LPVOID lpParamlpParam)LONG LONG cPreviousCountcPreviousCount;char outinfo20;char outinfo20;WaitForSingleObject(hSemaphoreWaitForSingleObject(hSemaphore,INFINITE);,INFINITE);MessageBox(NULLMessageBox(NULL,Thread Message,MB_OK);,Thread Message,MB_OK);ReleaseSemaphore(hSemaphoreReleaseSemaphor
32、e(hSemaphore,1,&,1,&cPreviousCountcPreviousCount););sprintf(outinfosprintf(outinfo,Previous Count=%d,Previous Count=%d,cPreviousCountcPreviousCount););MessageBox(NULLMessageBox(NULL,outinfooutinfo,MB_OK);,MB_OK);return 0;return 0;intint APIENTRY APIENTRY WinMain(HINSTANCEWinMain(HINSTANCE hInstanceh
33、Instance,HINSTANCE HINSTANCE hPrevInstancehPrevInstance,LPSTR LPSTR lpCmdLinelpCmdLine,intint nCmdShownCmdShow)intint i;i;hSemaphorehSemaphore=CreateSemaphoreCreateSemaphore(NULL,/no security attributesNULL,/no security attributescMaxcMax,/initial count,/initial countcMaxcMax,/maximum count,/maximum countNULL);/unnamed semaphoreNULL);/unnamed semaphorefor(i=0;i5;i+)for(i=0;i5;i+)CreateThread(NULLCreateThread(NULL,0,0,thread_functhread_func,NULL,0,NULL);,NULL,0,NULL);Sleep(60000);Sleep(60000);return 0;return 0;