Operating System Ch14: Semaphore

Layfort·2023년 11월 14일
Operating SystemSemaphore세마포어운영체제
0

Operating System

목록 보기
2/7

Semaphore

  • lock을 사용하는 이유 → Mutual exclusion

    • 그리고 이러한 lock을 지금까지는 spinlock으로 구현했다...

  • spinlock의 단점

    • 1번에 1개의 thread만이 들어올 수 있다.
      • 아니 그럼 critical section에 한명만 들어와야지!
      • 이야기를 더 들어보면 이게 이 소리가 아니란 것을 알 수 있을 것이다.
    • 여러 개의 thread들이 대기하고 있다면, 다음에 누가 들어올지 알 수 없다!
      • spinlock은 결국 busy-waiting이기 때문이다...
      • Only OS know

1. Concepts of Semaphores

  • Semaphore는 lock의 기능을 수행할 수도 있지만, 기본적으로는 lock뿐만 아니라 event-waiting이라는 목적을 가지고 있기도 하다.(N > 1 case)

1-1. Implementing Semaphore

typedef struct {
  int value;			// number of task that could access to CS
  struct process *Q;	// task that currently wait for CS
} semaphore;

void wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {			// if already 
    add this process to S->Q;	// add to waiting queue
    block();					// sleep(pass to OS?)
  }
}

void signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {			// if waiting queue is exist...
    remove a process P from S->Q;
    wakeup(P);					// wake OS
  }
}
  • 일단 확실하게 해야하는 것은 이 wait와 signal함수는 반드시 atomic하게 동작해야 한다는 것이다!
    • 이는 추후에 다루겠지만, 분명 기억해야 한다.
  • Code Flow는 wait() → CS → signal() 순서로 이루어 질 것이다.
    • wait(): semaphore의 대기명단에 등록한다(S->value--).
      • if (S->value < 0): CS에 들어간 task가 꽉 차버렸기 때문에 일단 대기한다.
    • CS: CS를 실행한다.
    • signal(): 이제 나는 더이상 대기 명단에도 없고 CS를 쓰지도 않으므로 명단에서 제거한다(S->value++).
      • if (S->value <= 0): 대기열이 존재하므로, queue에서 한명을 빼서 해당 task를 깨운다.

1-2. Types of Semaphores

  1. N == 1 semaphore 영역에 들어갈 수 있는 thread가 단 1개. mutex와 동작이 거의 다를 것이 없다.

  2. N > 1 semaphore 영역에 들어갈 수 있는 thread가 여러개인 경우. 이 경우에는 CV와 동작이 비슷하다.

2. Case Studies

2-1. Bounded Buffer Problem(Producer/consumer problem)

  • System Programming에서도 배운 사례...
    • N개의 Producer task들이 buffer에 object를 채워 넣으면
    • M개의 Consumer task들이 해당 object를 buffer에서 빼와서 처리한다.
    • Unlimited, Bounded, Zero Buffer case가 있는데 일단 여기서는 Buffer의 크기가 유한한 Bounded Case를 중심적으로 다루자.

2-1-1. No synchronization

void produce(data)
{
  while (count==N); // wait until buffer have empty cell
  buffer[in] = data;
  in = (in+1) % N;
  count++;
}

void consume(&data)
{
  while (count==0);	// wait until buffer have object
  *data = buffer[out];
  out = (out+1) % N;
  count--;
}
  • 이젠 딱봐도 알수 있을 것이다... in도 CS, out도 CS, buffer도 CS, 심지어 lock이랍시고 걸어놓은 count조차 CS...

2-1-2. Synchronization

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가 무려 3개나 사용되는데...
    1. mutex: binary semaphore → buffer와 같이 반드시 1개의 task만이 건드려야하는 CS에 대해서 lock이 필요한 경우
    2. empty, fulll: condition semaphore → 이 2개 변수는 일종의 trigger 역할을 수행한다. 즉, 기존 code의 count에 대응하는 semaphore이다.
  • 2개의 semaphore의 wait와 signal이 서로 cross되어 있는 점을 주목하라.
    • producer는 empty의 value를 한개 줄이고 들어간다. 반면에 consumer는 full의 value를 한개 줄이고 들어간다.
    • 반대로 나올 때는 producer가 full을 한개 늘리고, consumer는 empty를 늘린다.
    • 즉, full = 쓰여진 cell의 개수, empty = 빈 cell의 개수
    • empty는 full을 trigger하고 full은 empty를 trigger한다.
      • empty상황에서 write를 하면 더 이상 empty하지 않기 때문에, full을 trigger하여 consumer가 들어올 수 있게 한다.
      • full상황에서는 반대로 empty를 trigger해서 producer를 작동시켜 buffer를 채운다.

2-2. Readers-Writers Problem

  • Reader와 Writer들(threads) 사이에 공유되는 resource가 있다고 하자

    • 당연하겠지만 Readers(Reading Threads)는 resource를 읽는 thread고 Writer(Writing Threads)는 resource에 쓰는 thread이다.
    • reading은 여러 명이 읽을 수 있지만, 쓰는 것은 한 명만 해야한다.
      • 다만, 여려명이 동시에 읽는 것은 괜찮지만, 읽고 쓰기가 동시에 이루어져서는 안될 것이다.
    • 이런 구조를 지니는 대표적인 사용처가 System programming에서 배웠던 IPC method중 하나인 mailslot(window에서는 MailBox).

  • Implementation with semaphores

    • readcount: # of threads reading object
    • mutex: control access to readcount
    • rw: exclusive writing or reading

2-2-1. Implementation

// number of readers
int readcount = 0;

// mutex for readcount
Semaphore mutex = 1;

// mutex for reading/writing
Semaphore rw = 1;

void Writer() {
  wait(&rw);			// nothing special... only one writer could access to resource
  ...
  // Write
  ...
  signal(&rw);
}

void Reader() {
  wait(&mutex);			// semaphore를 이용해서 readcount라는 CS에 대한 lock을 구현하고 있는 것
  readcount++;			
  if (readcount == 1)	// 현재 reading중인 reader가 나만이라면...
  	wait(&rw);			
  signal(&mutex);		
  
  ...
  // Read
  ...
  
  wait(&mutex);			// 마찬가지의 역할을 수행하고 있음
  readcount--;
  if (readcount == 0)	// 현재 더이상 read하려는 reader가 없는 경우
  	signal(&rw);
  signal(&mutex);
}

  • Writer()는 전혀 새로울 것이 없다.

  • Reader()의 구현은 Writer()에 비해서 흥미로운 문제를 하나 가지고 있다.

    • 여러 명의 reader는 혀용하면서 동시에 writing과 mutual exclusion해야 한다!
    • 이를 해결하기 위해서 있는 것이 readcount.
    • readcount == 1: 현재 reading을 시도하는 reader는 나뿐이면, rw check를 실행한다.
      • writer가 rw를 가지고 있을 수도 있기 때문이다.
      • 반면 readcount > 1이면 반드시 reader가 rw를 가지고 있다는 것이 보장된다.
      • 당연하겠지만, readcount가 동시에 2이 되는 경우는 없다. 이를 방지하기 위해서 있는 것이 mutex semaphore이기 때문
    • readcount == 0: 현재 모든 reader가 reading을 마쳤기 때문에 writer들에게 rw를 넘기겠다.
      • readcount > 0이면 현재 reader중에 하나가 reading을 하고 있는 과정이기 때문에 rw를 넘겨서는 안된다!

  • 문제점: starvation → 한번 reading이 시작되면 writer의 차례가 돌아오기 위해서는 모든 reader가 reading을 멈추는 경우에만 가능하다!

    • 반면에 reader는 writer와 동등하게 lock을 얻을 수 있다...
    • writer에게 굉장히 불리한 조건

2-3. Dinning Philosophers Problem

  • 간단히 말해서... philosopher한명이 noodle을 먹는데에는 양쪽의 chopstick이 필요한 경우이다.
    • 따라서 양 옆에 위치한 2개의 task가 동시에 작업을 수행할 수 없는 경우에 해당한다!

2-3-1. First Try

// semaphore for each fork for 
// initialized to 1
Semaphore forks[N];

#define L(i) (i)
#define R(i) ((i + 1) % N)

void philosopher(int i)
{
  while (1) {
    think();
    pickup(i);
    eat();
    putdown(i);
  }
}

// get fork pair lock
void pickup(int i) {
  wait(&forks[L(i)]);
  wait(&forks[R(i)]);
}

// release fork pair lock 
void putdown(int i) {
  signal(&forks[L(i)]);
  signal(&forks[R(i)]);
}
  • 각 philosopher는 먹기전에 pickup을 통해서 lock을 잡고 먹은 후 putdown을 통해서 lock을 푼다.
    • 문제없이 동작할 것처럼 보이지만...
  • 실재로는 deadlock에 걸릴 가능성이 있다.(극히 드물게 일어나지만...)
    • 모든 philosopher가 동시에 자신의 왼쪽에 있는 포크를 집었다고 가정해보자
    • 그렇다면 모든 philosopher는 자신의 오른쪽에 있는 포크를 집기 전까지는 대기하는데, 그 누구도 먼저 놓아줄 생각을 하지 않는다...
    • 그렇기 때문에 아무도 pickup을 끝내지 못한채로 작업이 끝나게 되버리는 현상을 볼 수 있다.

2-3-2. Complete Solution

// semaphore for each fork for 
// initialized to 1
Semaphore forks[N];

#define L(i) (i)
#define R(i) ((i + 1) % N)

void philosopher(int i)
{
  while (1) {
    think();
    pickup(i);
    eat();
    putdown(i);
  }
}

// get fork pair lock
void pickup(int i) {
  if (i == (N-1)) {
    wait(&forks[R(i)]);
    wait(&forks[L(i)]);
  } else {
    wait(&forks[L(i)]);
    wait(&forks[R(i)]);
  }
}


// release fork pair lock 
void putdown(int i) {
  signal(&forks[L(i)]);
  signal(&forks[R(i)]);
}
  • 한명만 반대로 집도록 하면 해결되는 놀라운 현상!

3. Summary

  • Pros
    • 간단하지만 강력하다.
    • Same primitive can be used for both critical sections (mutual exclusion) and coordination among threads (scheduling)
  • Cons
    • 결국 semaphore 자체가 global shared variable이라는 문제가 있다.
    • semaphore와 semaphore가 control하려는 data 사이에 관계를 이해하기 쉽지 않다.
    • 프로그래머가 모든 lock에 대해서 책임을 지는데, 전술한 이유 때문에 프로그래밍 난이도가 올라간다.

4. Semaphore implementation in xv6

typedef struct semaphore {
  unsigned int val;
  struct spinlock lock;
  void * thread[NPROC];
  unsigned int next;
  unsigned int end;
} semaphore;
void sem_init(struct semaphore * s, uint i) {
  int j;
  s->val = i;
  
  initlock(&s->lock, (char*)s);
  for (j = 0; j < NPROC; j++)
    s->thread[j] = 0;
  s->next = s->end = 0;
}
void sem_wait(struct semaphore * s) {
  acquire(&s->lock);
  
  while (s->val == 0) {
    s->thread[s->end] = proc;
    s->end = (s->end + 1) % NPROC;
    sleep(proc, &s->lock);
  }
  s->val = s->val - 1;
  
  release(&s->lock);
}
void sem_signal(struct semaphore * s) {
  acquire(&s->lock);
  s->val = s->val + 1;
  
  if (s->thread[s->next]) {
    wakeup(s->thread[s->next]);
    s->thread[s->next] = 0;
    s->next = (s->next + 1) % NPROC;
  }
  release(&s->lock);
}
profile
Layfort
물리와 컴퓨터
이전 포스트

Operating System Ch12: Threads

다음 포스트

Operating System Ch15: Monitors

0개의 댓글