互斥信号量初值不同情况分析

2022-08-29李洁

电脑知识与技术 2022年20期

李洁

(宿迁学院信息工程学院，江苏宿迁223800)

进程中存在两种制约关系，一种为直接制约关系即同步，主要是由于执行时序上的限制而形成的相互合作的制约关系；另一种为间接制约关系即互斥，主要是由于共享资源而形成的关系，这种共享的资源其特殊性在于一次仅允许一个进程使用，称为临界资源，访问临界资源的程序代码称为临界区。在进程互斥关系中，信号量初值一般为1，含义为使用的临界资源的数量为1 个，一次仅允许一个进程使用，但也存在特殊情况其初值不为1，下面就来讨论下互斥信号量的不同取值情况。

1 互斥描述

多个程序在并发执行时，由于共享系统资源，如CPU、I/O设备等会形成相互制约的间接关系，这种间接制约关系称之为互斥。为了保证这些进程能有序地运行，对于系统中的这类共享资源，必须由系统实施统一分配，即用户在要使用这些资源之前应先提出申请，而不能直接使用[1]，使用结束后要释放资源。

1.1 信号量机制

信号量机制指两个或两个以上进程利用彼此之间收发的简单信号来实现并发执行，是一种卓有成效的进程同步机制，被广泛应用于各种系统[2]。信号量被定义为含有整型数据项的结构变量，其数据结构定义如下：

typedef struct semaphore

{

int value;

PCB*pointer;

};

其中value 是信号量的值，pointer 是信号量的等待队列指针。其值大于等于零表示可供并发进程使用的某类资源数量，其值小于零表示该类资源已分配完，请求该资源的进程被阻塞，其绝对值表示等待该资源的进程数。

1.2 P、V原语

信号量的值仅能通过两个标准的原子操作来访问，即P操作和V 操作。P 操作和V 操作是两条原语，执行时是不可中断的。每执行一次P 操作，就是请求一个单位的该类资源，系统中可供分配的该类资源数减少一个；每执行一个V 操作，就是释放一个单位的源源，系统中可供分配的该类资源数增加一个。使用信号量机制和P、V原语描述进程同步互斥关系时，首先要分析进程间存在的哪些同步和互斥关系；其次，针对分析的同步和互斥分别设定同步和互斥信号量，并且说明各信号量的含义和初值；最后使用P、V原语描述进程的活动。

1.3 描述进程间互斥关系所遵循的规律

使用信号量和P、V原语可以方便有效地解决临界区问题。进程间存在互斥关系，进程活动用P、V 原语描述时，先执行P操作，后执行V操作，临界区在P、V操作中间，同一个互斥信号量的P、V操作必须成对出现在同一个进程的代码中，缺少P操作将会导致系统混乱，无法保证对临界资源的互斥访问；缺少V操作将会导致资源永远不被释放，从而使因等待改资源而阻塞的进程不能被唤醒[3]。

1.4 互斥信号量初值

互斥信号量初值一般情况下为1，表示一次仅允许一个进程使用，比如n个进程互斥访问共享资源，只能有1个进程获得资源，剩余进程将进入等待状态，信号量取值范围为-n~1[4]。若有特殊说明即允许多个进程共享一个互斥段，比如n个进程共享资源，允许m个进程进入该互斥段，则信号量的初值为m，取值范围为-(n-m)~m。

2 互斥信号量不同取值情况分析

2.1 初值为1的情况举例

进程间互斥最典型的例子就是多个进程共享一台打印机，打印机是临界资源，多个进程之间的关系就是互斥，假定互斥信号量为mutex，每次只允许一个进程使用，由信号量的物理含义可知，mutex初值应为1，各并发进程的程序描述如下：

semaphore mutex;

mutex=1;

…

Process Pi

{…

P(mutex);

进程Pi的临界区代码；

V(mutex);

…}

分析此进程活动描述，互斥信号量mutex初值为1，表示共享的打印机只有一台，第一个进程要打印，首先申请打印机，执行P(mutex)，信号量值减1，mutex=0，若此时又一进程申请打印机，仍执行P(mutex)，信号量值再减1，mutex=-1，表示此进程进入等待状态，符合进程互斥的关系。

2.2 初值不为1 的情况举例

在经典的同步问题——哲学家进餐问题出现的死锁情况可以用互斥信号量来解决。哲学家进餐问题描述五位哲学家围坐在一张圆桌前用餐，分别在其周围放置五只筷子，且每只筷子只允许一个人使用。当一位哲学家需要用餐时，就去取其左右两边的筷子，只有拿到两只筷子，方可就餐[5]。假设五位哲学家用五个进程表示，五只筷子为临界资源，设互斥信号量为c[i](i=0,…,4)，左边筷子为c[i]，右边筷子为c[(i+1)%5]，初始值为1，表示每只筷子只允许一个人使用。哲学家进餐问题的算法描述如下：

struct semaphore c[5]={1,1,1,1,1};

void philosopher(inti)

{

while(true)

{

P(c[i]);

P(c[(i+1)%5]);

…;

进餐；

…;

V(c[i]);

V(c[(i+1)%5]);

…;

}}

在上述描述中，虽然解决了两个相邻的哲学家不会同时进餐的问题，但若五位哲学家同时拿起左边的筷子，再拿右边的筷子时，都将因无筷子可用而陷入死锁状态。可以用增加一个互斥信号量的方法来解决此死锁问题。设互斥信号量count，表示最多允许4位哲学家同时申请左边的筷子，从而保证任何情况下至少有一位哲学家能同时拿到两边的筷子进餐，使得每个哲学家均有进餐的可能，所以count 初值为4，此时改进的算法描述如下：

struct semaphore c[5]={1,1,1,1,1};

struct semaphore count=4;

void philosopher(int i)

{

while(true)

{P(count);

P(c[i]);

P(c[(i+1)%5]);

…;

进餐；

…;

V(c[i]);

V(c[(i+1)%5]);

V(count);

…;

}}

分析此改进算法，在原先算法基础上只加了两句原语P(count)和V(count)。count 和c[i]均为互斥信号量，c[i]初值为1，表示每只筷子只允许一位哲学家使用，count 初值为4，表示最多允许4 位哲学家同时使用，假设第一位哲学家想进餐，在申请左边筷子之前，首先执行P(count)，count 值减1，count 值从4变为3，表示还允许3位哲学家执行，其他哲学家同样申请左边筷子之前都要先执行P(count)，执行P 操作，count 值减1 ，当count 值为0 时，若再有哲学家申请，执行P(count)，count 值从0变为-1，说明此哲学家进入等待状态，这样就可以保证只能有4位哲学家同时执行，一位哲学家可以拿到左右两边的筷子，结束后释放资源，从而保证其他所有哲学家都可以执行。