linux - 在 Linux 中控制信号量队列中的出队顺序

Question

我想在我想为不同线程分配几个“优先级数字”的地方实现代码。一些线程可能在同一个信号量上等待。假设线程在信号量 S 上排队，另一个线程在信号量 S 上执行 sem_post。一旦执行 sem_post，我希望信号量 S 队列中具有最高“优先级数”的线程获得对信号量的访问权限而不是任何其他线程。据我所知，没有直接的方法来实现这一点，因为选择访问的线程可以是队列中的任何一个元素(不一定是 FIFO 等)。事实上，我尝试增加线程的 pthread 优先级，但我意识到它也不起作用。有人可以指导我如何在 C 中实现这种手动控制信号量队列的设计。提前谢谢。

Answer 1

我可以想到两种方法:

• 使用 condition variable “唤醒部分或所有服务员”，他们将自行安排优先释放；或
• 使用(实时)信号按优先顺序“唤醒单个特定服务员”

在每种情况下，信号量至少有一个 mutex ，一个值，以及一些簿记。如果 value 小于零，它的绝对值就是等待者的数量(例如，value == -3 表示有 3 个线程在等待)。

条件变量方法

信号量跟踪任何给定优先级的等待者数量，以及任何给定优先级释放的等待者数量。在伪 C 中:

typedef struct priority_sem_s {
  int              value;     // if negative, abs(sem->value) == no. of waiting threads
  pthread_mutex_t  mutex;
  pthread_cond_t   cv;
  int              n_waiting[N_PRIORITIES];  // no. waiting (blocked) at each priority
  int              n_released[N_PRIORITIES]; // no. waiters released (unblocked) at each priority
} priosem_t;

void post(priosem_t *sem):
  lock(sem->mutex);
  sem->value++;

  if (sem->value <= 0 && prio_waiting_is_NOT_empty(sem)):
    // someone was waiting; release one of the highest prio
    int prio = fetch_highest_prio_waiting(sem);
    sem->prio_waiting[prio]--;
    sem->prio_released[prio]++;
    cond_broadcast(sem->cv, sem->mutex);

  unlock(sem->mutex);

void wait(priosem_t *sem, int prio):
  lock(sem->mutex);
  sem->value--;

  if (sem->value < 0):
    // get in line
    sem->prio_waiting[prio]++;
    while (sem->prio_released[prio] < 0):
      cond_wait(sem->cv, sem->mutex);
    // ok to leave
    sem->prio_released[prio]--;

  unlock(sem->mutex);

优点:可以跨进程共享(在共享内存中实现)。

缺点:唤醒每个服务员只放一个。 Martin James 建议每个优先级一个条件变量，这将以更多同步原语为代价减少“不必要的”唤醒。

信号方法

使用sigsuspend和一个 realtime signal使用 noop 处理程序来暂停和恢复服务员。在伪 C 中:

typedef struct priority_sem_s {
  int              value;    // if negative, abs(value) == no. of waiting threads
  pthread_mutex_t  mutex;
  void            *waiting;  // ordered list of [priority, thread-id] pairs
} priosem_t;

void post(priosem_t *sem):
  lock(sem->mutex);
  sem->value++;

  if (sem->value <= 0 && waiting_queue_is_NOT_empty(sem)):
    pthread_t tid = pop_highest_prio_waiter(sem);
    pthread_kill(tid, SIGRTMIN+n);

  unlock(sem->mutex);

void wait(priosem_t *sem, int prio):
  // XXX --> PRECONDITION:  SIGRTMIN+n is SIG_BLOCK'd <-- XXX
  // XXX --> PRECONDITION:  SIGRTMIN+n has a no-op handler installed <-- XXX
  lock(sem->mutex);
  sem->value--;

  if (sem->value < 0):
    // get in line
    add_me_to_wait_list(sem, pthread_self(), prio);
    unlock(sem->mutex);
    sigsuspend(full_mask_except_sigrtmin_plus_n);
    return;  // OK!

  unlock(sem->mutex);

优点:概念上更简单；没有不必要的唤醒。

缺点:不能跨进程共享。必须选择或动态选择可用的实时信号(寻找具有 SIG_DFL 处置的未屏蔽信号？)并尽早屏蔽。