Синхронизация между Семафором / Мьютексом и Printf

Question

Я работаю над упражнением (см. Полужирный текст ниже) по семафорам и синхронизации для моего курса по операционной системе. Текст упражнения таков:

Pthread семафоры и мьютексы

Программа C gen_binary_numbers.c получает в командной строке целое число n и использует рекурсию для генерации и отображения всех двоичных чисел из n битов.Преобразуйте рекурсивную программу в параллельную, заменив рекурсивную процедуру генерацией соответствующего числа процессов, которые отображают двоичные числа (в любом порядке).

На самом деле это мой код:

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

int num, r, c;
pthread_mutex_t mutex;
void *genBin(void *arg);

int main (int argc, char **argv) {
  if (argc != 2) {
    fprintf(stdout, "\nUSAGE: %s <n>\n\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int i;
  num = atoi(argv[1]);
  c = num;
  r = 2;
  for (i=1; i<num; i++) {
    r=r*2;
  }

  pthread_mutex_init(&mutex, NULL);
  pthread_t* p;
  p = malloc(r*sizeof(pthread_t));

  for (i=0;i<r;i++) {
    if (pthread_create(&p[i], NULL, genBin, &i)) {
      fprintf(stderr, "Error creating thread.\n");
      exit(EXIT_FAILURE);
    }
  }
  pthread_exit(0);
}

void *genBin (void *arg) {
  int x;
  int i=0;
  x = *((int*)arg);

  pthread_mutex_lock(&mutex);

  while (i<num) {
    if(x!=0) {
      fprintf(stdout, "%d", x%2);
    }
    else {
      fprintf(stdout, "0");
    }
    i++;
    x/=2;
  }
  fprintf(stdout, "\n");
  pthread_mutex_unlock(&mutex);
  pthread_exit(0);
}

Я думаю, что код должен возвращать правильное решение, но иногда вывод не возвращает правильное число.

Пример правильного вывода:

./genBin 3
100
101
010
110
001
011
111
000

Пример неправильного вывода (из-за дубликатов):

./genBin 3
110
110
110
001
011
111
111
000

Я думаю, что проблема заключается в синхронизации между мьютексом и printf. Есть ли альтернативное решение, чтобы избежать путаницы в результатах?

Answer 1

Ваш код содержит условие гонки. В основном вы передаете адрес вашей итерационной переменной, iв качестве аргумента функции потока. Каждый новый поток затем пересекается с основным потоком, чтобы прочитать значение i (через предоставленный указатель), прежде чем основной поток увеличивает его. Одним из способов решения этой проблемы было бы использование семафора, чтобы заставить главный поток ждать после создания каждого потока, пока этот поток не разыменует свой аргумент.

Кроме того, я не думаю, что вам нужно использовать мьютекс в genBin(), Единственные общие данные, к которым он обращается stdout, с помощью fprintf()и эта функция работает так, как будто она блокирует монопольную блокировку, связанную с указанным потоком. Более того, с мьютексом вы практически не получаете фактического параллелизма, потому что каждый поток удерживает мьютекс заблокированным практически на протяжении всего времени его выполнения.

Answer 2

Проблема в этой части:

  for (i=0;i<r;i++) {
    if (pthread_create(&p[i], NULL, genBin, &i)) {
      fprintf(stderr, "Error creating thread.\n");
      exit(EXIT_FAILURE);
    }
  }

Есть гонка данных, потому что вы передаете адрес i на все темы. Вы можете использовать временный массив для передачи индивидуального номера каждому потоку.

Answer 3

Спасибо всем! Вы решили мою проблему. Это исправленный код:

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

int num, r, c;
pthread_mutex_t mutex;
void *genBin(void *arg);

int main (int argc, char **argv) {
  if (argc != 2) {
    fprintf(stdout, "\nUSAGE: %s <n>\n\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int i;
  int *temp;
  num = atoi(argv[1]);
  c = num;
  r = 2;
  for (i=1; i<num; i++) {
    r=r*2;
  }

  temp = malloc(r*sizeof(int));
  pthread_mutex_init(&mutex, NULL);
  pthread_t* p;
  p = malloc(r*sizeof(pthread_t));

  for (i=0;i<r;i++) {
    temp[i] = i;  
  }

  for (i=0;i<r;i++) {
    if (pthread_create(&p[i], NULL, genBin, &temp[i])) {
      fprintf(stderr, "Error creating thread.\n");
      exit(EXIT_FAILURE);

    }
  }

  for (i=0;i<r;i++) {
    if (pthread_join(p[i], NULL)) {
      fprintf(stderr, "Error creating thread.\n");
      exit(EXIT_FAILURE);
    }
  }

  pthread_mutex_destroy(&mutex);
  free(temp);
  free(p);
  pthread_exit(0);
}

void *genBin (void *arg) {
  int x;
  int i=0;
  int *v;
  v = malloc(num*sizeof(int));
  x = *((int*)arg);

  for (i=0; i<num; i++) {
    v[i] = x%2;
    x/=2;
  }

  pthread_mutex_lock(&mutex);
  for (i=0; i<num; i++) {
    fprintf(stdout, "%d", v[i]);
  }
  fprintf(stdout, "\n");
  pthread_mutex_unlock(&mutex);

  free(v);
  pthread_exit(0);
}