c - 与信号量原语的进程同步

Question

你将如何完成这个方案以及你将使用多少个信号量来获取

a) ABCD ACBD 序列

b) ABCD ABDC 序列

使用这两个进程(考虑使用伪代码 es:wait(s1) signal(s1) 等...)

流程1

P1:while(1){
        .
        printf("A");
        .
        .
        printf("C");
        .
   }       

流程2

 P2:while(1){
        .
        printf("B");
        .
        .
        printf("D");
        .
   }

将点视为可以插入缺失代码(基元)的位置

@杰瑞

经过一些互联网研究，我想我已经解决了第一点(a)，

解决方案是构建一个像这样的优先级图

      A<--(s0)--^
     / \        |
(s1)-- --(s2)   |
(me)-------     |
    /   \       |
   B     C      |
    \   /       |
   -------(s3)  |
     \ /        |
      D-------->|

其中 INIT(s0)=INIT(ME)=1 且 INIT(s1)=INIT(s2)=INIT(s3)=0

因此我有 P1

P1:while(1){
       wait(s0);
       printf("A");
       signal(s2);
       signal(s1);

       wait(s1);
       wait(ME);
       printf("C");
       signal(ME);
       signal(s3)
   }

和P2

P2:while(1){
       wait(s2);
       wait(ME);
       printf("B");
       signal(s3);
       signal(ME);

       wait(s3);
       wait(s3);
       printf("D");
       signal(s0)
   }

您认为我的方法正确吗？我可以减少更多使用的信号量数量吗？ (目前有 5 个(2 个互斥锁和 3 个普通锁))

Answer 1

我确实认为您使用优先级图的方法是正确的，但是 问题陈述有点不清楚，例如从图中是 看起来像 B和C可以以任何顺序发生，但没有指示 这在原始的 a) 和 b) 序列中。

(编辑:很明显 B 和 C 必须交替)

因此，对于情况 a) 以下(无限) 顺序是可以接受的:

ABCD ACBD ABCD ACBD ABCD ACBD ...

  A<--+
 / \  |
B<->C |
 \ /  |
  D---+

A优先于B通过程序逻辑，它们位于同一线程中。 同样C优先于D出于同样的原因。因此，需要信号量来仅沿边缘强制执行优先级A->C , B->D和D->A 。 B之间的边缘和C每个周期都会改变方向，因此我们需要额外的状态位来确定方向:B->C或B<-C可以使用额外的变量来完成，或者我们可以通过复制循环体来隐式维护状态，如下所示:

#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>

#define NLOOPS 100000

sem_t s0, s1, s2, s3;

void *
process_A (void *unused)
{
  int n = NLOOPS;

  while (n--)
    {
      sem_wait (&s0);
      putchar ('A');
      sem_post (&s1);
      putchar ('B');
      sem_post (&s3);
      sem_post (&s2);

      sem_wait (&s0);
      putchar ('A');
      sem_post (&s1);
      sem_wait (&s3);
      putchar ('B');
      sem_post (&s2);
    }

  return 0;
}

void *
process_B (void *unused)
{
  int n = NLOOPS;

  while (n--)
    {
      sem_wait (&s1);
      sem_wait (&s3);
      putchar ('C');
      sem_wait (&s2);
      putchar ('D');
      sem_post (&s0);

      sem_wait (&s1);
      putchar ('C');
      sem_post (&s3);
      sem_wait (&s2);
      putchar ('D');
      sem_post (&s0);
    }

  return 0;
}


int
main ()
{
  pthread_t a, b;

  sem_init (&s0, 0, 1);
  sem_init (&s1, 0, 0);
  sem_init (&s2, 0, 0);
  sem_init (&s3, 0, 0);

  pthread_create (&a, 0, process_A, 0);
  pthread_create (&b, 0, process_B, 0);

  pthread_join (a, 0);
  pthread_join (b, 0);

  putchar ('\n');
  return 0;
}

我会让你自己实现 b) :)