Synchronization: Working with Mutexes And Semaphores(2)

Stack Semaphores

How can I force my threads to wait if the stack is empty or full?

counting semaphore를 이용합니다. counting semaphore를 이용해 공간이 얼마나 남았는지 확인하고, 또 다른 세마포어를 이용해 스택의 아이템 수를 알 수 있습니다. 이러한 두 세마포어를 sremain, sitems로 부릅니다. sem_wait은 다른 스레드가 sem_post를 호출해 semaphore의 수가 0으로 감소될 때까지 기다린다는 것을 기억해두세요.

// Sketch #1

sem_t sitems;
sem_t sremain;
void stack_init(){
  sem_init(&sitems, 0, 0);
  sem_init(&sremain, 0, 10);
}


double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);
  ...

void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);
  ...

아래의 Sketch #2는 post를 너무 빨리 구현했습니다. push에서 기다리는 다른 스레드가 실수로 가득 찬 스택에 쓰려고 시도할 수 있습니다.(유사하게 pop에서 기다리는 스레드도 너무 빨리 continue할수 있게 허가받음)

// Sketch #2 (Error!)
double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);
  sem_post(&sremain); // error! wakes up pushing() thread too early
  return values[--count];
}
void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);
  sem_post(&sitems); // error! wakes up a popping() thread too early
  values[count++] = v;
}

아래의 Sketch #3는 semaphore 수정을 했는데 어디가 틀렸는지 찾을수 있을까요?

// Sketch #3 (Error!)
double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);
  double v= values[--count];
  sem_post(&sremain);
  return v;
}

void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);
  values[count++] = v;
  sem_post(&sitems); 
}

Sketch 3는 세마포어를 이용해 버퍼가 가득찬 상황이나 비어있는 상황으로 강제시킵니다. 하지만 mutual exclusion이 없어 두개의 스레드가 CS에 동시에 진입할해 자료구조를 오염시킬 수 있습니다(또는 데이터 손실이 일어납니다). 해결법은 critical section을  mutex로 감싸는 것입니다.

// Simple single stack - see above example on how to convert this into a multiple stacks.
// Also a robust POSIX implementation would check for EINTR and error codes of sem_wait.

// PTHREAD_MUTEX_INITIALIZER for statics (use pthread_mutex_init() for stack/heap memory)

pthread_mutex_t m= PTHREAD_MUTEX_INITIALIZER; 
int count = 0;
double values[10];
sem_t sitems, sremain;

void init() {
  sem_init(&sitems, 0, 0);
  sem_init(&sremains, 0, 10); // 10 spaces
}

double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);

  pthread_mutex_lock(&m); // CRITICAL SECTION
  double v= values[--count];
  pthread_mutex_unlock(&m);

  sem_post(&sremain); // Hey world, there's at least one space
  return v;
}

void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);

  pthread_mutex_lock(&m); // CRITICAL SECTION
  values[count++] = v;
  pthread_mutex_unlock(&m);

  sem_post(&sitems); // Hey world, there's at least one item
}
// Note a robust solution will need to check sem_wait's result for EINTR (more about this later)

What are the common Mutex Gotchas?

• 잘못된 mutex를 lock/ unlock
• mutex를 unlock하지 않음
• resource leak ( pthread_mutex_destroy 호출을 하지 않음)
• 초기화하지 않은 mutex 사용( 또는 이미 destroy된 mutex 사용)
• 스레드의 mutex를 두번 lock(unlock하지 않고 두번 연속)
• deadlock, 우선순위 역전(나중에 더 살펴봄)