Operating System Ch16: Condition Variables and Mutexes

Layfort·2023년 11월 16일
Operating Systemcondition variablesmutex뮤텍스운영체제
0

Operating System

목록 보기
4/7

Condition Variables and Mutex

  • Monitor는 결국 언어가 지원을 해야한다.

1. Condition Variables

1-1. Operations

  1. wait(cond_t *cv, mutex_t *mutex)
  • mutex는 왜 필요한 것인가?
    • 당연하겠지만, CV에 접근(확인도 포함)하려면 당연히 mutex를 잡았어야 한다.
    • 그렇기 때문에, waiting에 들어가려면 일단 지금 가지고 있는 mutex를 풀어야 한다.
    • 또한 waiting에서 나온다 하더라도 아직 CS 내부에 있기 때문에... mutex를 또 잡아야 한다.
  1. signal(cond_t *cv)
  • CV를 기다리는 thread가 있으면 깨운다.
  • Semaphore와 다르게 signal은 history를 남기지 않는다!
    • 즉, waiting queue에 아무도 없으면 signal은 낭비된다.(이게 문제가 되는 것은 아니다.)
  • Mesa semantics: signal()을 보냈다고 하더라도 thread는 진행된다.
  1. broadcast(cond_t *cv)
  • 모든 thread를 다 깨운다.
    • 이렇게 깨워진 thread들은 다시 경쟁상태에 돌입한다.(scheduler의 선택을 기다린다!)
  • waiting이 아무도 없으면 아무것도 하지 않는다.(정확히는 못한다.)

2. Examples

2-1. Joining Thread

2-1-1. Initial Attempt

mutex_t m = MUTEX_INITIALIZER;	// mutex
cond_t c = COND_INITIALIZER;	// child의 역할이 끝났는지에 대한 CV

void *child(void *arg) {
  ...
  // do something...
  ...

  thread_exit();
  return NULL;
}

int main(int argc, char *argv[]) {
  thread_t p;
  thread_create(&p, NULL, child, NULL);
  thread_join();		// child가 끝날때까지 대기하기
  return 0;
}

void thread_exit() {
  mutex_lock(&m);		// CV에 대한 mutex를 acquire
  cond_signal(&c);		// parent에 child가 종료되었음을 알리세요
  mutex_unlock(&m);	
}

void thread_join() {
  mutex_lock(&m);		// CV에 대한 mutex를 acquire
  cond_wait(&c, &m);	// child가 끝나면 cv를 통해서 signal이 올 것... 그 전까지는 mutex를 풀고 대기상태로 진입(sleep)
  mutex_unlock(&m);
}
  • 좋아 보인다. 하지만 큰 문제가 있다...
    • signal()은 history를 남기지 않는다!
    • 다시말해서 child가 먼저 cond_signal()에 도입하면 parent는 cond_wait()에서 나올 방법이 없다.
  • 따라서 우리는 이 순서를 교정해줄 필요가 있다.

2-1-2. Solution

mutex_t m = MUTEX_INITIALIZER;	// mutex
cond_t c = COND_INITIALIZER;	// child의 역할이 끝났는지에 대한 CV
int done = 0;

void *child(void *arg) {
  ...
  // do something...
  ...

  thread_exit();
  return NULL;
}

int main(int argc, char *argv[]) {
  thread_t p;
  thread_create(&p, NULL, child, NULL);
  thread_join();		// child가 끝날때까지 대기하기
  return 0;
}

void thread_exit() {
  mutex_lock(&m);		// CV에 대한 mutex를 acquire
  done = 1;				// 당연하지만 done도 CS다... 
  cond_signal(&c);		// parent에 child가 종료되었음을 알리세요
  mutex_unlock(&m);	
}

void thread_join() {
  mutex_lock(&m);		// CV에 대한 mutex를 acquire
  while(done == 0)		// 완료가 되지 않았으면... wait로 넘어간다.
    cond_wait(&c, &m);	// CV는 mesa semantics! - 반드시 while로 double check해야함
  mutex_unlock(&m);
}
  • done을 추가해서 child_thread의 종료 여부에 대한 history를 남긴다.

2-2. Bounded Buffer

mutex_t m;
cond_t notfull, notempty;
int in, out, count;

void produce(data) {
  mutex_lock(&m);				// mutex!
  while (count == N)			// while(mesa semantics)
  	cond_wait(&not_full, &m);	// 꽉 차있으면 대기(mutex넘김)
    
  buffer[in] = data;
  in = (in+1) % N;
  count++; 
  
  cond_signal(&not_empty);		// empty를 깨운다.
  mutex_unlock(&m);
}

void consume(data) {
  mutex_lock(&m);
  while (count == 0)			// while(mesa semantics)
  	cond_wait(&not_empty, &m);	// 비어있으면 대기
    
  data = buffer[out];
  out = (out+1) % N;
  count--; 
  
  cond_signal(&not_full);		// full을 깨운다.
  mutex_unlock(&m);
}

  • mutex 내부에 있는 code들은 atomic하게 동작해야하는 code임을 명심하라

  • Semaphore랑 비교해보자.

Semaphore mutex = 1;	// mutex for CS(access to buffer)
		  empty = N; 	// trigger producer(is buffer full?)
		  full = 0;		// trigger consumer(is buffer empty?)

void produce(data)
{
  wait(&empty);			// check buffer empty
  wait(&mutex);			// enter to CS
  buffer[in] = data;
  in = (in+1) % N;
  signal(&mutex);
  signal(&full);		// signal full(buffer is no more empty)
}

void consume(&data)
{
  wait(&full);			// wait until buffer is not empty
  wait(&mutex);			// enter to CS
  *data = buffer[out];
  out = (out+1) % N;
  signal(&mutex);
  signal(&empty);		// signal empty(buffer is no more full)
}
  • Semaphore는 기본적으로 내부 int를 이용해서 Semaphore 자체가 Counting을 한다(이게 history를 남긴다의 의미이다.

2-3. Using Broadcast

  • 일반적인 CV는 queue를 쓰기 때문에 FIFO로 동작한다...

    • 하지만 일부 프로그램중에서 FIFO가 효율적이지 않은 경우도 있다.
    • memory allocate는 남은 bytes에 따라서 동작이 되는데... 이 경우 CV나 semaphore로는 이러한 byte에 따라 일부 lock을 해제하는 algorithm이 불가능하다.
    • 이 경우 그냥 모든 waiter를 wake up 시켜서 전부 다시 try해보게 만드는 것이 필요한 경우가 있다.
    • 이러한 것을 Covering Condition이라고 부른다.

  • e.g. memory allocation

mutex_t m;
cond_t c;
int bytesLeft = MAX_HEAP_SIZE;

void free(void *p, int size) {
  mutex_lock(&m);
  bytesLeft += size;
  cond_broadcast(&c);	// wake all allocate function waiter
  mutex_unlock(&m);
}

void *allocate (int size) {
  mutex_lock(&m);
  while (bytesLeft < size)	// size check! 
  	cond_wait(&c, &m);
    
  void *ptr = ...;
  bytesLeft -= size;
  mutex_unlock(&m);
  return ptr;
}

2-4. Semaphores vs. Mutexes + CVs

  • 이론적으로 이 두 방법은 완벽히 동일한 기능을 가지고 있다.
    • 즉, semaphore로 구현된 것은 mutexed + CV로도 구현이 가능하고 반대도 성립한다.
    • 또한... mutex + CV를 semaphore로 구현할 수도 있고, semaphore로 Mutex + CV 구현도 가능하다.(후자는 이미 우리가 제법 많이 봐왔다.)
  • e.g. Semaphore implementation by using mutex + CV
typedef struct sema_t {
  int v;
  cond_t c;
  mutex_t m;
} sema_t;

void sema_init(sema_t *s, int v) {
  s->v = v;
  cond_init(&s->c);
  mutex_init(&s->m);
}

void sema_wait(sema_t *s) {
  mutex_lock(&s->m);
  while (s->v <= 0)
  cond_wait(&s->c, &s->m);
  	s->v--;
  mutex_unlock(&s->m);
}

void sema_signal(sema_t *s) {
  mutex_lock(&s->m);
  s->v++;
  cond_signal(&s->c);
  mutex_unlock(&s->m);
}

3. Xv6

3-1. Sleeplock

struct sleeplock {
  uint locked;			// locked or not
  struct spinlock lk;	// spinlock worked as mutex
  char *name;
  int pid;				// process that currently get lock
};

void initsleeplock(struct sleeplock *lk, char *name) {
  initlock(&lk->lk, “sleep lock”);
  lk->name = name;
  lk->locked = 0;
  lk->pid = 0;
}

void acquiresleep(struct sleeplock *lk) {
  acquire(&lk->lk);			// enter CS zone
  while (lk->locked)
  	sleep(lk, &lk->lk);		// if locked that go to sleep
  
  // get lock
  lk->locked = 1;
  lk->pid = myproc()->pid;
  release(&lk->lk);			// out to CS zone
}

void releasesleep(struct sleeplock *lk) {
  acquire(&lk->lk);		// enter CS zone
  
  // release lock
  lk->locked = 0;
  lk->pid = 0;
  wakeup(lk);			// wake all proc that try to access lk
  
  release(&lk->lk);		// out to CS zone
}

3-2. Sleep & Wakeup

void sleep(void *chan, struct spinlock *lk) {
  struct proc *p = myproc();	// get current process
  if (lk != &p->lock) {			// if lock is not gee
    acquire(&p->lock);			// get process lock
    							// we have to modify process state
    release(lk);				// release mutex
  }
  
  p->chan = chan;				// which lock block this process?
  p->state = SLEEPING;			// sleeping!!!
  sched();						// yield to sched
  
  p->chan = 0;
  if (lk != &p->lock) {			
    release(&p->lock);			//release process lock
    acquire(lk);				// reacquire spinlock
  }
}

void wakeup(void *chan) {
  struct proc *p;
  
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == SLEEPING && p->chan == chan) // change all proc state that locked by spinlock
    	p->state = RUNNABLE;
    
    release(&p->lock);
  }
}
profile
Layfort
물리와 컴퓨터
이전 포스트

Operating System Ch15: Monitors

다음 포스트

Operating System Ch18: File System

0개의 댓글