进程间互斥、同步与通信.ppt

第六章 进程间互斥、同步与通信,授课教师：付勇智 西南林学院 基础部数理教研室,问题纲要,间接制约和直接制约是什么？ 什么是临界区？ 什么是信号量？ 什么是同步、互斥？ 如何应用信号量实现同步和互斥？ 信号量在Windows编程中是如何实现的？,进程并发运行所带来的问题,由于系统资源的共享性，并发进程的执行结果失去了封闭性和可再现性。 满足Bernstein条件的并发进程能够保持封闭性，但是Bernstein条件限制太过严格，不符合大多数实际环境的需要。 因而，OS需要寻求一种机制，满足进程间共享资源的需要。,进程间通信IPC,在两个或多个进程间传递信息或共享数据的机制，称之为进程间通信（Inter-Process Communication） UNIX操作系统中的管道技术（Pipe）就是一种IPC 在IPC的过程中，主要要解决两类问题：互斥和同步,互斥的需要,void SendPrint() 1 if (in+1)%N=out) 2 exit(0); 3 else 4 in=(in+1)%N; 5 filein=printfile; 6 return; ProcessA() SendPrint() ProcessB() SendPrint() ,临界区（Critical Section),临界资源：一次仅允许一个进程使用的资源称为临界资源。 临界区：进程中对于临界资源访问的程序段称为临界区。 间接制约：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源造成的并发进程执行速度的间接制约，简称间接制约。,互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致他们不能同时进入临界区称为互斥。,互斥（Mutual Exclusion）,互斥方案应满足的4个条件,任何两个进程不能同时处于临界区 不应对CPU的数目和速度做任何假设 临界区外的进程不得阻塞其他进程 不得使进程在临界区外无休止地等待,互斥的实现方案,关中断 锁变量 严格轮换法 Peterson方案 TSL硬件指令（Intel平台为BTS指令） 信号量 管程 消息传递,关中断,处理机的调度都是由中断所引起的（主要是定时器中断） 如果进入临界区前将所有外部中断屏蔽，则在运行临界区时将不会响应所有外部中断事件，也就不可能发生进程切换，待进程执行完临界区后再开中断。 缺点：交由用户进程管理中断的开关是非常不安全的，一旦用户程序关中断后忘记打开，则整个系统将无法响应外部事件而崩溃；另外，在多处理器系统中，关中断也仅屏蔽本处理器的中断响应，对其他处理器中运行的进程无法屏蔽。 因而通常中断屏蔽都由OS进行管理，由OS使用它来保证一些核心操作的不可中断性。,锁变量,int lock=0; /初始情况下没有进程进入临界区 Processi() while (lock=1) ; /当其他进程在临界区工作时，忙等待 lock=1; /设置锁变量，防止其他进程进入 critical_section(); /进行临界区相关操作 lock=0; /退出临界区后解锁，使其他进程可以进入 non_critical_section(); ,严格轮转法,Peterson方案,TSL指令（测试与设置指令）,Intel CPU中对应的TSL指令汇编指令码为BTS,信号量(semaphore),信号量使E.W.Dijkstra在1965年提出的一种方法，他建议引入一个新的变量类型，称作信号量。信号量是一个整数，其值可以为0或某个正整数，分别表示不可进入临界区以及能够进入的进程数目。 信号量：是一个仅能由同步原语对其进行操作的整型变量。 原语（原子操作）：操作过程不可中断，必须以一个整体进行执行地系统基本操作 对于信号量操作的原语只有两个：UP和DOWN,DOWN原语（P操作）,(1)若信号量S大于0，则将S减1，P操作返回，该进程继续执行 (2)若信号量S等于0，则将进程挂入S的等待队列，将进程设置为阻塞状态，并转调度程序,P原语,S0,S=S-1,返回,调用进程进入等待队列,转进程调度,是,否,UP原语（V操作）,(1)若信号量S的等待队列中有等待进程，则取队首进程，将其置为就绪状态并返回。 (2)否则信号量S加1，并放回,V原语,是否有等待进程,S=S+1,返回,取队首进程置为就绪态,否,是,生产者消费者问题,问题描述：两个进程共享一个公共的固定大小的缓冲区。其中的一个，生产者，将信息放入缓冲区；另一个，消费者，从缓冲区中取出信息。 当缓冲区已满，而此时生产者还想向其中放入一个新的信息则让生产者睡眠，待消费者从缓冲区取走一个或多个信息时再唤醒它。 当消费者试图从缓冲区中取信息而发现缓冲区为空时，它就睡眠，直到生产者向其中放入一些消息再将其唤醒。,生产者过程,消费者过程,直接制约与同步,一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。 异步环境下的一组并发进程，因直接制约而互相发送消息而进行相互合作、相互等待，使得各进程按一定的速度执行的过程称为进程间的同步。,生产者消费者问题信号量定义,#define N 100 semaphore mutex=1; /互斥信号量 semaphore empty=N; /开始时候可用的消息缓冲区数为N semaphore full=0; /开始时候可用的消息为0,生产者进程,void producer() int item; while(true) produce-item( /增加一个可用消息 ,消费者进程,void consumer() int item; while(true) down(full); /获得一可用消息 down(mutex); /互斥访问消息缓冲区 get-item( /增加一个空缓冲区 ,哲学家进餐问题,五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉，由于通心粉很滑，所以要两把叉子才能夹住。相邻两盘子之间有一把叉子，餐具摆放如右图所示,哲学家生活的过程,哲学家的生活包括两种活动：即吃饭和思考。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次得到一把，并且不分次序。如果成功的获得两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。 问题：为每一个哲学家写一段程序来描述其行为，要求不能死锁。,不正确解法,#define N 5 void philosopher(int i) while(true) think(); take-fork(i); take-fork(i+1)%N); eat(); put-fork(i); put-fork (i+1)%N); ,低效率的互斥可行解法,#define N 5 semaphor mutex=1; void philosopher(int i) while(true) think(); down(mutex); take-fork(i); take-fork(i+1)%N); eat(); put-fork(i); put-fork (i+1)%N); up(mutex); ,经典解法,#define N 5 #define LEFT (i-1)%N #define RIGHT (i+1)%N #define THINKING 0 #define HUNGRY 1 #define EATING 2 int stateN semaphore mutex=1 semaphore sN=0, 0, ., 0,哲学家过程,void philosopher(int i) while (true) think(); take-forks(i); eat(); put-forks(i); ,void test(i) if (statei=HUNGRY ,哲学家的两个主要动作,void take-forks(int i) down( ,void put-forks(int i) down(mutex); statei=THINKING; test(LEFT); test(RIGHT); up(mutex); ,读者写者问题,设想一个飞机订票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但一个进程正在更新数据库，则所有其他进程都不能访问数据库，即使读操作也不行。 问题：如何对读者和写者编写线程？,semaphore mutex=1; semaphore db=1; int rc=0; void reader() while (true) down(mutex); rc+=1; if (rc=1) down(db); up(mutex); read-data-base();,down(mutex); rc=rc-1; if (rc=0) up(db); up(mutex); use-data-read(); ,写者过程,void writer() while(true) think-up-data(); down(db); write-data-base(); up(db); ,理发师睡觉问题,理发店里有一位理发师、一把理发椅和n把供等候理发顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。 当一个顾客到来时，他必须叫醒理发师；如果一个顾客到来时理发师正在理发，则如果有空椅子可以坐，他们就坐下来等待；如果没有空椅子，他们就离开。 问题：为理发师和顾客各编写一段程序，描述他们的行为，要求不能带有竞争条件。,信号量定义,#define CHAIRS 5 /椅子数目 semaphore customers=0; /顾客数目 semaphore barbers=0; /等候顾客的理发师数目 semaphore mutex=1; /等待队列互斥信号量 int waiting=0; /等待队列,void barber() while(true) down(customers); down(mutex); waiting-; up(barbers); up(mutex); cut-hair(); ,void customer() down(mutex); if (waitingCHAIRS) waiting+; up(customers); up(mutex); down(barbers); get-haircut(); else up(mutex); ,司机售票员问题,一辆公共汽车上有一名司机和一名售票员，司机的工作是不停的循环执行如下步骤：“开车正常行车到站停车”，售票员的工作是不停的执行如下工作：“开车门等候乘客上车关车门售票” 售票员必须等车到站停车后才能开车门；司机也必须等售票员关车门以后才能开车 问题：试写两段程序，分别描述司机和售票员的工作过程。,司机、售票员问题,。 。 。,。 。 。 。,售票员,司机,semaphore driving=0; semaphore door=1; void driver() while(true) down(driving); 开车(); 正常行车(); 到站停车(); up(door); ,void ticket-seller() while(true) down(door); 开门(); 等待乘客上车(); 关门(); up(driving); 售票(); ,两学校交通问题,在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M，可供两辆自行车在从两端进入小路的情况下错车使用，如下图所示，试设计一个算法使来往的自行车均可顺利通过。,学校交通图示,M,天津大学,南开大学,S,K,T,L,semaphore S2T=1; semaphore T2S=1; semaphore SK=1; semaphore TL=1; semaphore M=2; void bikeS2T() down(S2T); down(SK); go-S-K(); down(M); get-in-M(); up(SK); down(TL); up(M); go-L-T(); up(TL); up(S2T); ,void bikeT2S() down(T2S); down(TL); go-T-L(); down(M); get-in-M(); up(TL); down(SK); up(M); go-K-S(); up(SK); up(T2S); ,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操作,BOOL ReleaseSemaphore( HANDLE hSemaphore, / handle to semaphore LONG lReleaseCount, / count increment amount LPLONG lpPreviousCount / previous count );,示例. 打开窗口数目的限制,功能：通过一个循环，打开五个窗口，但同一时刻最多只能有三个窗口打开。 试用DOWN、UP操作先编写程序完成以上要求 semaphore count=3; OpenAction() DOWN(count); DrawWindo