《进程的互斥同步通信与死锁讲义》由会员分享，可在线阅读，更多相关《进程的互斥同步通信与死锁讲义（88页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学,第八章 进程的互斥、同步、通信与死锁,南京邮电大学,第八章 进程的互斥、同步、通信与死锁,8.1 进程同步 8.2 进程通信 8.3 产生死锁的原因和条件,南京邮电大学,8.1 进程的同步,在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。 进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作， 进程的同步机制信号量及P.V操作（解决进程同步互斥问题）,南京邮电大学,直接作用(相互合作）：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间 间接作用（资源共享）：进程间要通过某种中
2、介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间,1. 进程间的关系,南京邮电大学,南京邮电大学,2. 进程的同步（直接作用）,指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态,南京邮电大学,由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。 临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,3. 进程的互斥（间接作用）
3、,南京邮电大学,4. 基本概念,进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。 进程同步：指多个相关进程在执行次序上的协调。 临界资源:一次仅供一个进程使用的资源。 在进程中涉及到临界资源的程序段叫临界区 多个进程的临界区称为相关临界区,南京邮电大学,南京邮电大学,5.使用互斥区的原则,空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 忙则等待：不允许两个以上的进程同时进入互斥区 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权,南京邮电大学,5.使用互斥区的原则,前提：
4、任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定 进程互斥的解决有两种做法: 由竞争各方平等协商 引入进程管理者，由管理者来协调竞争各方对互斥资源的使用 具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）,南京邮电大学,6.进程互斥的软件方法,通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志 软件解法的缺点：1. 忙等待2. 实现过于复杂3. 需要高的编程技巧,南京邮电大学,软件解法
5、 (1),1.方法1：考虑用标志位来实现判别和处理用标志位flagi来标示进程i是否在临界段中执行，当flagi为真，则表示它正在执行临界段；反之不在临界段中执行。那么我们的临界区就可以如下设计：,南京邮电大学,软件解法 (2),#define false 0 #define true 1 int flag2=0,0; Pi: do | While(flagj) ； flagi=true; Pi的临界段代码CSi； flagi=false； | while（true）；,南京邮电大学,软件解法(3),2.方法2用一个指针turn来指示应该哪个进程进入临界段。若turn=i,则进程Pi进入临界段
6、。 Pi： int turn=0; do | While (turn!=i); Pi的临界段代码Csi； turn=j; | whiletrue;,南京邮电大学,硬件解法（1）,实现功能的硬件指令： （1）TS指令，其功能描述如下：int TestandSet(int *flag) int tmp;tmp=*flag;*flag=true;return (tmp); 注意：其功能是由一条处理机指令完成的，其执 行过程是连续的。,南京邮电大学,用指令实现互斥的程序结构为：为临界资源设置一个锁变量lock,lock的值为true时表示临界资源正被访问，为false时空闲。 do while (TS
7、 (*lock); 进程的临界段代码； lock=false; while(true),南京邮电大学,硬件解法 (2) “交换”指令,void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp; ,key = true;do SWAP(,南京邮电大学,7. 信号量和P、V原语,1.信号量（信号灯） 1）问题的引入：为临界资源S设置锁key，当key为1时，资源可用，否则不可用。lock（keyS）测试key，若key为1，则将key赋值为0并退出，unlock（keyS）则将key赋值为1。 PA： PB： A：lock（
8、keyS） B：lock（keyS）Unlock（keyS） Unlock（keyS） GOTO A GOTO B 结果：容易导致一个进程饥饿,南京邮电大学,2）信号量定义： 信号量：除赋初值外仅能由同步原语（P、V操作）对其操作的整型变量，其值与其所代表的资源使用情况有关。 信号量的物理意义： 当其值=0时，代表可用资源的数量 当其值=0，则返回 否则调用阻塞原语把当前进程阻塞 转进程调度程序 2）V（sem）原语的主要动作： sem=sem+1 若sem0，则返回 否则调用唤醒原语把当前阻塞队列中的对首进程唤醒或全部唤醒 转进程调度程序或返回,南京邮电大学,P、V原语的实现,P原语的实现P
9、(sem): 关中断 lock（lockbit）/用于防止多个进程同时调用P，V操作 valsem=valsem-1 if valsem0 调用阻塞原语相关功能 unlock（lockbit） 开中断,南京邮电大学,V原语的实现V（sem） 关中断 lock（lockbit）/用于防止多个进程同时调用P，V操作 valsem=valsem+1 if valsem=0 调用唤醒原语相关功能 unlock（lockbit） 开中断,南京邮电大学,P、V原语实现互斥,用P、V原语实现进程互斥： （1） 定义信号量，必须说明其所代表的资源 （2） 设定信号量的初值：1 （3） 在临界段进入区执行：（信
10、号量）操作 （）在临界段进入区执行：（信号量）操作,南京邮电大学,8 进程同步,一、同步的引入 Pc: Pp: C: P:Do Do外部读一组数据存入 从BUF读一组数据存入局部变量Cbuf中； 局部变量Pbuf中；while(Cbuf!=Null) while(Pbuf!=Null)计算； 打印；计算结果送BUF 清除buf;GOTO C GOTO P,南京邮电大学,二、同步的定义： 同步的定义：一组并发进程由于相互合作共同完成某种任务，因而相互等待，使得各进程按一定的速度执行的过程。 互斥也是一种特殊的同步。 私用信号量：只与制约和被制约进程有关的信号量。用于同步的信号量。 例：分析： 根
11、据题意可知： 只有当缓冲队列中有一个及一个以上满缓冲时，Pb才可以继续执行，否则等待Pa发送数据；,南京邮电大学,同理只有当缓冲队列中有一个及一个以上空缓冲时，Pa才可以继续执行，否则等待Pb取走数据； 因此，Pa和Pb之间存在同步关系。 信号量的设定： 设代表满缓冲区数量的信号量为BufFull 设代表空缓冲区数量的信号量为BufEmpty 设初值：BufFull=0，BufEmpty=n 三、同步的实现 1、用消息通信实现进程的同步：Wait（消息名）和Signal（消息名）实现。Wait（消息名）功能：若消息名变量为true，则退出Wait过程继续执行，若消息名变量为false，则等待，
12、直到消息变量为true。Signal（消息名）功能：向合作进程发消息，并将其消息变量置为true。,南京邮电大学,消息变量的设置： 设消息名Bufempty表示Buf空,消息名Buffull表示Buf满 设Bufempty=true,Buffull=false Pc: Pp: . . A:wait(Bufempty) B:wait(Buffull) 计算 打印Buf中的数据Buf计算结果 清除Buf中的数据Bufemptyfalse Buffullfalse signal(Buffull) signal(Bufempty)GOTO A GOTO B,南京邮电大学,9 用P、V实现进程同步示例,
13、生产者-消费者问题分析分析生产者进程和消费者进程间的同步互斥关系 1）生产者进程间（互斥） 2）消费者进程间（互斥） 3）生产者-消费者之间（同步互斥）,南京邮电大学,信号量设定：设代表非空缓冲区数量的信号量为full，代表空缓冲区数量的信号量为avail，代表缓冲区资源使用情况的信号量为mutex（互斥） 设定初值：full=0，avail=n，mutex=1 书写算法： 1.生产者： -首先申请空缓冲资源，若无则等待 -申请占用缓冲区（why） -查找空闲的缓冲区，在找到的空缓冲区中填入数据，置满缓冲标志 -放弃对缓冲区的占用，增加可用满缓冲数量,南京邮电大学,2.消费者：-首先申请满缓冲资源，若无则等待-申请占用缓冲区（why）-查找满缓冲区，从找到的满缓冲区中取走数据，置空缓冲标志-放弃对缓冲区的占用，增加可用空缓冲数量信号量初值设定原则（用于同步和互斥）：进程执行之前该信号量所代表的资源的可用数量就是该信号量的初值。,南京邮电大学,南京邮电大学,第八章 进程的互斥、同步、通信与死锁8.2 进程通信,南京邮电大学,
