7

我正在为期中考试而学习，这是练习题之一：展示如何仅使用二进制信号量和普通机器指令来实现计数信号量（即可以保存任意值的信号量）？

我什至不确定从哪里开始。我在网上找到了这个；

P(s) { Pb(mutex_s); s = s-1; if(s < 0) {Vb(mutex_s); Pb(delay_s);} Vb(mutex_s); }
V(s) { Pb(mutex_s); s = s+1; if(s <= 0) Vb(delay_s); else Vb(mutex_s); }

不幸的是，我真的不明白答案告诉我什么。谁能向我解释这个答案，或者用伪代码告诉我如何回答？

4

5 回答 5

6

我根据Prahbat 的回答建立了以下直觉：

我们试图复制的内容：

  • 计数信号量意味着最多允许 N 个线程访问资源

我们可以使用二进制信号量来做到这一点：

  • 如果已经有 N 个进程在其临界区中，则计数信号量锁定对线程临界区的访问
    • => 我们需要一个二进制信号量sectionLock，它告诉等待线程它们是否可以访问它们的临界区（sectionLock = 1）或者它们不能（sectionLock = 0）
  • 我们必须跟踪访问临界区资源的线程数。让这个计数器是一个整数计数
    • count在线程进入临界区时减少（即该资源中的线程少一个点）并在线程退出临界区时增加（即为该资源中的线程释放一个点）
    • => count是共享资源，一次只能由一个线程访问
    • => 我们需要一个二进制信号量countLock用于计数
  • 如果count <= 0那么我们不能再允许线程进入临界区并且必须等待sectionLock被退出线程释放

因此，以下伪代码暗示了自己

P_counting( int count )
   P( countLock )        // Acquire lock to count: countLock <- 0
   count--
   if( count <= 0 )      // If no more threads allowed into critical section
      P( sectionLock )   // Resource full => Acquire section lock: sectionLock <- 0
      V( countLock )     // Release lock to count: countLock <- 1
   else
      V( countLock)

V_counting( int count )
   P( countLock )
   count++
   if( count > 0)        // Release sectionLock if resource is freed up
      V(sectionLock)     // countLock released after sectionLock so that waiting
      V(countLock)       // threads do not jump in when before resource is available
   else
      V(countLock)

如果我有什么问题，请告诉我。

于 2018-02-03T18:28:34.557 回答
3 
CSem(K) cs { // counting semaphore initialized to K
    int val ← K; // the value of csem
    BSem gate(min(1,val)); // 1 if val > 0; 0 if val = 0
    BSem mutex(1); // protects val

    Pc(cs) {
        P(gate)
        a1: P(mutex);
        val ← val − 1;
        if val > 0
        V(gate);
        V(mutex);
    }

    Vc(cs) {
        P(mutex);
        val ← val + 1;
        if val = 1
        V(gate);
        V(mutex);
    }
}

来源：http ://www.cs.umd.edu/~shankar/412-Notes/10x-countingSemUsingBinarySem.pdf

于 2015-01-11T22:16:31.243 回答
2

令 x, y 为二进制信号量。我们将通过它来实现计数信号量S。P代表等待操作，V代表信号。由于我们采用 S=4，所以只有 4 个进程可以进入临界区。

S = 4, x = 1, y = 0;

/*---P(S)---*/
{P(x);S--;if(s<=0){V(x);P(y);}else V(x); }

/*--CRITICAL SECTION--*/

/*--V(S) ---*/
  { P(x); S++;IF(S>0){ V(y);V(x); }else V(x);}

注意：P(x) 将 x 的值减少 1，而 V(x) 增加 1，对于 y 也是如此。y 被称为挂起信号量，因为如果 S<0，P(y) 将所有这些进程放入队列中。

于 2014-08-09T16:33:53.060 回答
0

弄清楚了：

int s = N;
semaphore mutex_s = 1;
semaphore delay_s = 0;

p(s) = down
  down(mutex_x);
  s--;

  if (s< n)
    up(mutex_s)
    down(delay_s)
  up(mutex_s)

V(s) = up
  down(mutex_s)
  s++
  if (s<=0)
    up(delay_s)
  up(mutex_s)
于 2013-02-28T00:53:25.650 回答
0

我有一个类似的问题，我认为会有相同的答案，即“如何使用互斥锁实现计数信号量”。

请注意，二进制信号量可以被认为是互斥体。事实上，在不提供互斥锁的系统上，可以使用二进制信号量来提供互斥。

Mutex counting_mutex;    // used for accessing the shared variable count
Integer count = n;       // number of resource instances
Mutex mutex;             // the counting semaphore as mutex/binary semaphore
List waiting_list = [];  // list of waiting processes

/* ... */

// Entry Section
acquire(counting_mutex);
count--;
release(counting_mutex);

if (count < 0)
    add this process to waiting_list and have it sleep()

acquire(mutex);
/* ... Critical Section ... */
release(mutex);

// Exit Section
acquire(counting_mutex);
count++;
release(counting_mutex);

if (count <= 0)
    pull a process from waiting_list and call wakeup()
于 2017-11-15T04:34:00.937 回答