互斥与并发(2)—信号量

小鱼儿 2022-03-15 03:46 255阅读 0赞

#### 1.信号量（Semaphore） ####

为了达到信号量的预期效果，可把信号量看做具有整数值得变量，在它之上定义三个操作：

1）  一个信号量可以初始化为一个非负数

2）  semWait操作使信号量减1（国内的教材将该操作称为P）。如果变成负数，那么执行semWait的进程被阻塞，并被移入阻塞队列。否则该进程继续执行

3）  semSignal操作使信号量加1（国内的教材将该操作称为V）。如果值小于或者等于零，则被semWait阻塞的某一个进程解除阻塞。

对于信号量的值（x）可以这样理解：初值为n表示最多可以有n个进程同时进入临界区；若x>=0表示还可以允许最多x个进程进入临界区；x<0表示有x个进程在阻塞队列中。

看一下信号量的C语言描述：

struct semaphore 
    {
    	int count;
        queueType queue;//用队列来保存信号上等待的进程(阻塞队列)
    };
    
    void semWait(semaphore s)
    {
        s.count--;
    if (s.count < 0) 
    {
    		/*将当前进程放入队列(s.queue)中*/;
    		/*阻塞该进程*/;
    	}
    }
    
    void semSignal(semaphore s)
    {
        s.count++;
    if (s.count <= 0) 
    {
    		/*将阻塞队列中某进程P从队列中移除*/;
    		/*把进程P插入到就绪队列*/;
    	}
    }
    
    struct binary_semaphore 
    {
        enum {zero, one} value;
        queueType queue;
    };
    
    void semWaitB(binary_semaphore s)
    {
        if (s.value == one)   
            s.value = zero;
    else
    {
    		/*将当前进程放入队列(s.queue)中*/;
    		/*阻塞该进程*/;
    	}
    }
    
    void semSignalB(semaphore s)
    {
        if (s.queue is empty())    //如果阻塞队列不空的话，此时二元信号量值是不改变的
            s.value = one;
    else 
    {
    		/*将阻塞队列中某进程P从队列中移除*/;
    		/*把进程P插入到就绪队列*/;
    	}
    }

与二元信号量相关的一个概念是互斥量(Mutex)。两者的关键区别在于为互斥量加锁(设定其值为0)的进程和为互斥量解锁(设定其值为1)的进程必须是同一个进程。相比之下可能由某个进程对二元信号量进行加锁操作，而由另一个进程为其解锁。

下面是信号量解决互斥问题的C语言描述。

const int n = /*进程数*/;
    semaphore s = 1;
    void P(int i)
    {
    	while (true) 
    	{
    		semWait(s);
    		/*临界区*/;
    		semSignal(s);
    		/*其他部分*/;
    	}
    }
    
    void main()
    {
    	parbegin (P(1), P(2), . . ., P(n));
    }

#### 2.信号量的实现 ####

信号量的操作必须是原子操作，可以用硬件方法实现，另外也可以用软件方法实现。下面列出两种硬件实现方法，当然禁用中断的方法只能在单处理器中实现。只是为了实现互斥，因为问题的本质就是互斥。在这个互斥操作中，进程是可以被抢占的，但是其依然占有临界区，因为信号量值的改变，要到进程离开临界区之后才变化。

semWait(s)
    {
    	while (compare_and_swap(s.flag, 0 , 1) == 1)    //内存为新值所以不能进入
    	/*什么都不做*/;
    	s.count--;
    	if (s.count < 0) 
    	{
    		/*该进程进入阻塞队列*/;
    		/*阻塞该进程(也必须将s.flag设置为0) */;			
        }
    	s.flag = 0;
    }
    semSignal(s)
    {
    	while (compare_and_swap(s.flag, 0 , 1) == 1)
    	/*什么都不做*/;
    	s.count++;
    	if (s.count <= 0) 
    	{
    		/*将某个进程P从队列中移除*/;
    		/*将进程P放入就绪队列*/;
    	}
    	s.flag = 0;
    }
    
    semWait(s)
    {
    	禁用中断
    	s.count--;
    	if (s.count < 0) 
    	{
    		/*该进程进入阻塞队列*/;
    		/*阻塞该进程*/;
    		/*允许中断*/；
    	}
    	else
    		允许中断;
    }
    semSignal(s)
    {
    	禁用中断;
    	s.count++;
    	if (s.count <= 0) 
    	{
    		/*将某个进程P从队列中移除*/;
    		/*将进程P放入就绪队列*/;
    	}
    	允许中断;
    }