Я думаю, что ваш подход с графом приоритетов верен, но постановка задачи немного неясна, например, из графика выглядит, как B
и C
могут встречаться в любом порядке, но никаких признаковэто в оригинальных а) и б) последовательностях.
( РЕДАКТИРОВАТЬ: становится ясно, что B
и C
должны чередоваться)
Итак, дляслучай а) допустима следующая (бесконечная) последовательность:
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;
}
Я оставлю вас для реализации б) самостоятельно:)