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

5 回答

• 0

  我在Prahbat's上 Build 了以下直觉：

  我们想要复制的内容：

  • 计数信号量意味着最多允许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)
  

  如果我出错了，请告诉我 .

  回复于 2024-04-26T07:52:18+08:00
• 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

  回复于 2024-04-26T07:52:18+08:00
• 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）将所有这些进程放入队列中 .

  回复于 2024-04-26T07:52:18+08:00
• 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)
  

  回复于 2024-04-26T07:52:18+08:00
• 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()
  

  回复于 2024-04-26T07:52:18+08:00