Синхронизация процессов с семафорными примитивами - PullRequest
0 голосов
/ 23 ноября 2011

Как бы вы завершили эту схему и сколько семафоров вы бы использовали, чтобы получить

а) ABCD ACBD последовательность

b) ABCD ABDC последовательность

с использованием этих двух процессов (рассмотрите возможность использования псевдокодов es: сигнал ожидания (s1) (s1) и т. Д ...)

Процесс 1

* * 1010

Процесс 2

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

Рассматривать точки как места, где можно вставить отсутствующий код (примитивы)

@ Джерри

После некоторых исследований в Интернете, я думаю, что мой первый пункт (а) решен,

решением было бы построить граф приоритетов, подобный этому

      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 нормальных))

1 Ответ

1 голос
/ 23 ноября 2011

Я думаю, что ваш подход с графом приоритетов верен, но постановка задачи немного неясна, например, из графика выглядит, как 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;
}

Я оставлю вас для реализации б) самостоятельно:)

...