操作系统讲课大赛信号量

1操作系统申丰山郑州大学信息工程学院信号量和PV操作2主要内容：一、提出信号量的目的二、信号量的概念及PV操作定义三、信号量及PV操作在进程互斥中的应用四、信号量及PV操作在进程同步中的应用信号量和PV操作3一、提出信号量的目的(1)

1、信号量的用途信号量用于管理临界资源，控制临界区的互斥访问，实现进程之间的互斥和同步关系。4一、提出信号量的目的(2)

2、信号量及PV操作的特征和优点前面章节已经介绍了临界区、临界资源的软件及硬件管理尝试方法，这些方法的缺点有（1）忙等待。当临界资源被占用时，进程不断测试忙闲标志位，造成处理机时间的浪费。（2）这些方法多用来实现两个进程之间的互斥关系，难以推广到任意多个进程之间的同步、互斥问题上。（3）有些方法是错误的，不符合临界区管理的原则。5一、提出信号量的目的(3)

信号量及PV操作的特征和优点（1）消除忙等待。当临界资源被占用时，进程阻塞睡眠，待资源可用时被唤醒，避免了处理机时间的浪费。（2）可用来实现任意多个进程之间的同步、互斥关系。6二、信号量的概念及PV操作定义(1)

1、信号量的提出信号量及PV操作是荷兰计算机科学家E.W.Dijkstra1965年提出的同步工具，该工具的提出受启发于交通管制中多种颜色的信号灯，两个或多个进程根据信号量的状态决定自己的运行和暂停。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)。进程可以使用P、V两个特殊操作来发送和接收信号。7二、信号量的概念及PV操作定义(2)

2、信号量及PV操作的物理含义一种信号量代表一种物理资源的可用数量，在这种信号量上的P操作代表进程申请这种物理资源，V操作代表进程释放这种物理资源。在某一时刻或某一时间段内，申请这种物理资源的进程可能有多个，而资源是有限的，一旦没有资源可用，申请资源的进程需等待，因此信号量还维护一个进程等待队列。执行V操作释放资源的进程负责唤醒队列中的进程以便使用资源。信号量还有一个计数器用于记录它所维护的资源队列中的等待进程数，以便判断资源利用状况和控制进程阻塞或唤醒动作。8二、信号量的概念及PV操作定义(3)

实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。除赋初值外，信号量仅能由同步原语对其进行操作，没有任何其他方法可以检查和操作信号量。也即P、V操作是原子的，由OS内核原语实现。信号量的值(-2)

信号量队列指针信号量的结构9二、信号量的概念及PV操作定义(4)

3、信号量及PV操作的定义设s为一个记录型数据结构，一个分量为整型量value,另一个为信号量队列list，P和V操作原语定义：

P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。

V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。10二、信号量的概念及PV操作定义(5)

typedefstructsemaphore{ intvalue;//信号量值

structpcb*list;//信号量队列指针

};voidP(semaphore&s){ s.value--; if(s.value<0) W(s.list);/*将P操作调用者进程置为阻塞状 态并移入s信号量队列，转进程调度*/}voidV(semaphore&s){ s.value++; if(s.value<=0) R(s.list);/*从信号量s队列中释放一个等待信号量s的进程并转换成就绪态，自己则继续执行*/}11二、信号量的概念及PV操作定义(6)

P(s)和V(s)中的s为两个过程的共享变量。s的取值：信号量s的初值在初始化时，根据其用途进行设置。通常，P操作意味着请求一个资源，V操作意味着释放一个资源。12二、信号量的概念及PV操作定义(7)

W(s.list)和R(s.list)是操作系统的基本系统调用。进程A调用W(s.list)将转为等待s的状态，移入s信号量队列，同时释放CPU，转向进程调度。进程A调用R(s.list)，将释放一个等待信号量s的进程B，将B从s信号量队列中移出，B转为就绪态并移入就绪队列。A继续执行或转向进程调度。进程从信号量队列中移出的次序应遵循的公平策略是FCFS算法。13二、信号量的概念及PV操作定义(8)

推论1：若信号量s为正值，则该值等于s所代表的实际还可以使用的物理资源数推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作14三、信号量及PV操作在进程互斥中的应用(1)

1、方法为临界资源设一互斥信号量mutex，初值为1，将临界区置于P(mutex)和V(mutex)之间，P(mutex)和V(mutex)一定成对出现在同一个进程中。2、应用模式15三、信号量及PV操作在进程互斥中的应用(2)

semaphoremutex;mutex=1;cobeginprocessPi(){//i=1,…,n P(mutex); {临界区}; V(mutex);}coend16三、信号量及PV操作在进程互斥中的应用(3)(3)一个并发实例决不会有两个或多个进程同时处于临界区中。全局共享变量：mutex.value=1，0,-1,0,1mutex.list=P2,空P1P2P(mutex);//mutex.value=0,成功,mutex.list=空临界区;//切换P(mutex);//mutex.value=-1,mutex.list=P2,阻塞,切换V(mutex);//mutex.value=0,唤醒P2,mutex.list=空临界区;V(mutex);//mutex.value=1,mutex.list=空17四、信号量及PV操作在进程同步中的应用(1)

有几个经典的进程同步问题：（1）哲学家进餐问题（2）生产者-----消费者问题（3）读者------写者问题（4）理发师问题这里先以哲学家进餐问题为例说明信号量及PV操作在进程同步中的应用。18四、信号量及PV操作在进程同步中的应用(2)

1、哲学家进餐问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。19四、信号量及PV操作在进程同步中的应用(3)

哲学家叉子001122334420四、信号量及PV操作在进程同步中的应用(4)

2、算法设计（1）数据结构设计每把叉子都应互斥使用，因此每把叉子都是一个临界资源，都应定义一个信号量fork[i](i=0,1,2,3,4)，每个信号量的初值为1。哲学家吃东西之前必须同时拿起左右两边的叉子，因此需要执行两次P操作。21四、信号量及PV操作在进程同步中的应用(5)

（2）算法设计semaphorefork[5];for(inti=0;i<5;i++)fork[i]=1;cobegin processphilosopher_i(){//i=0,1,2,3,4 while(true){ think(); P(fork[i]); P(fork[(i+1)%5]); eat(); V(fork[i]); V(fork[(i+1)%5]); } }coend22四、信号量及PV操作在进程同步中的应用(6)

2、算法分析若每个哲学家都各自拿起他左边的一把叉子，然后再去拿他右边的叉子时，将都拿不到右边的叉子，大家又都不会放下手中的叉子，大家在相互等待别人释放叉子，系统于是进入死锁状态。23四、信号量及PV操作在进程同步中的应用(7)

3、死锁问题解决方案1）至多允许有四位哲学家同时去拿左边的叉子，最终保证至少有一位哲学家能够进餐，（至多可以有两位哲学家能够进餐）。24四、信号量及PV操作在进程同步中的应用(8)

semaphorefork[5];semaphorefour=4;//用于获得拿叉子的资格，最多4人有资格for(inti=0;i<5;i++)fork[i]=1;cobegin processphilosopher_i(){//i=0,1,2,3,4 while(true){ think();P(four);/*获得拿叉子的资格，若four<=0，则阻塞*/ P(fork[i]); P(fork[(i+1)%5]); eat(); V(fork[i]); V(fork[(i+1)%5]);V(four); } }coend25四、信号量及PV操作在进程同步中的应用(9)

2）规定奇数号哲学家先拿他左边的叉子，然后再去拿右边的叉子；偶数号哲学家先拿他右边的叉子，然后再去拿左边的叉子。26四、信号量及PV操作在进程同步中的应用(10)semaphorefork[5];for(inti=0;i<5;i++)fork[i]=1;cobegin processphilosopher_i(){/*i=0,2,4，偶数号哲学家操作*/ while(true){ think(); P(fork[i]); P(fork[(i+1)%5]); eat(); V(fork[i]); V(fork[(i+1)%5]); } }27四、信号量及PV操作在进程同步中的应用(11) processphilosopher_i(){/*i=1,3，奇数号哲学家操作*/ while(true){ think(); P(fork[(i+1)%5]); P(fork[i]); eat(); V(fork[(i+1)%5]); V(fork[i]); } }coend28四、信号量及PV操作在进程同步中的应用(12)

3）仅当哲学家的左右两根叉子均可用时，才允许他拿起叉子进餐，否则一把叉子也不取。29四、信号量及PV操作在进程同步中的应用(13)第三种策略：先占有空闲叉子，占有后再拿起semaphorefork[5];intfork_state[5];//取值1表示叉子空闲，为0表示叉子已被拿起semaphoremutex=1;//用于互斥访问整型变量fork_statesemaphorewait_fork[5];//用于阻塞进程intwaits[5];//记录等待叉子i和(i+1)%5的进程数目for(inti=0;i<5;i++){fork[i]=1;fork_state[i]=1;waits[i]=0;wait_fork[i]=0;}cobegin processphilosopher_i(){//i=0,1,2,3,4 while(true){ think();P(mutex);/*试图占有空闲的叉子*/30四、信号量及PV操作在进程同步中的应用(14) if((fork_state[i]==1)&&(fork_state[(i+1)%5]==1) { fork_state[i]--;//先占有叉子

fork_state[(i+1)%5]--; V(mutex); } else { V(mutex);/*释放互斥信号量mutex，以便其它进程使用mutex进入自己的临界区*/ P(wait_fork[i]);//本进程等待

P(mu