展示如何计数信号可以只使用二进制信号量和普通机器指令实现？

Question

我学习的中期，这是实践中的一个问题：如何显示计数信号（即，可容纳任意值信号灯）可以只使用二进制信号量和普通机器指令实现的？

我甚至不知道从哪里所以开始。我发现这个网上;

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); }

不幸的是，我真的不知道答案是什么告诉我。任何人都可以这样的回答给我解释一下，或者告诉我在伪代码怎么回答？

Answer 1

我建Prahbat's回答以下直觉：

我们正在试图复制：

• 计数信号意味着最多N次线程可以访问的资源

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

• 计数信号量锁访问线程的关键部分，如果有在他们的关键部分已经是N过程 =>我们需要告诉等待的线程，如果他们可以访问他们的临界部（sectionLock = 1）或二进制信号量sectionLock它们不能（sectionLock 0 =）
• 我们必须保持跟踪访问他们的关键部分资源的线程数。让这个计数器是一个整数计数 计数递减上螺纹进入临界区（即较少对该资源的螺纹一个斑点），并递增螺纹离开临界区（即，一个点在该资源释放开螺纹） =>计数是一个共享的资源，只能由一个线程时候访问 =>我们需要一个二进制信号，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)

请让我知道，如果我有什么不对。

Answer 2

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

Answer 3

设x，y为二进制信号。我们要落实代表等待操作和V信号通过it.P计数信号量S上。由于我们正在采取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);} 

注意：由1×的P（x）的下降值，而V（x）的加1，同样用于Y。 y被称为挂信号作为P（Y）把所有那些过程在队列若S <0。

Answer 4

弄清楚了：

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)

Answer 5

我有一个类似的问题，我认为将有相同的答案，即“你怎么能使用互斥实现计数信号”。

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

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()