오퍼레이팅 시스템 : Synchronization Ⅱ

1. Condition Synchronization

1) Condition Synchronization

• 이제 Mutual Exclusion를 보았으니, 그게 전부일까?
  • Mutual exclusion는 단일 스레드만 특정 시점에 공유 리소스에 액세스할 수 있어야 함을 의미("data is available")
  • concurrent programs을 구축하는 데 필요한 기본 요소는 Mutex뿐만이 아니다.
• Condition Synchronization
  • 조건에 따라 동기화하려면 어떻게 해야 할까?
  • 시스템 상태가 지정된 조건을 충족할 때까지 대기하여 여러 스레드의 실행 순서 지정

2. Condition Variables

1) Introducing Condition Variables

• 조건부 동기화를 지원하는 추상화
• 멀티 스레드 프로그램에서 스레드가 실행을 계속하기 전에 condition을 기다리려는 경우가 많음

2) Condition Variables

• 특정 조건이 충족될 때까지 프로세스 또는 스레드를 차단하는 데 사용되는 데이터 타입이다.
  • Condition variable(CV)
    • CV는 조건부 queue이다(아이디어는 Dijkstra로 돌아간다.)
    • CV는 Mutex와 연관되어 있으며 개념적으로 어떤 조건과 연관되어 있다.
  • Operations
    • 스레드는 다른 스레드가 조건을 알릴 때 깨우기 위해 condition variables에서 대기할 수 있다.
    • waiting on the condition : wait()
      • go to sleep(조건이 충족되지 않을 때)
    • Signaling on the condition : signal()
      • waiting인 스레드 중 하나를 깨운다.
      • waiting 중인 모든 스레드를 깨우는 명령어 broadcast()

(1) pthread API : Condition Variables

• Implementation(구현)
  • 구체적으로, POSIX 호출은 다음과 같다.
    • pthread_cond_wait : 호출 스레드를 sleep로 전환
    • pthread_cond_signal : condition variable에서 차단된 스레드 중 하나
    • Mutex와 함께 사용화도록 설계되었다.

#include <pthread.h>
int pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);	// wait()이 호출될 때 스레드가 mutex를 연결한다고 가정
int pthread_cond_signal(pthread_cond_t *c);

Returns: 0 if OK, error number on error

• condition variable는 java에서 모니터의 context 내에서 사용할 수 있다.

Class Object{
…
void wait();
void notify();
…
}

 

간단히 wait() 및 signal()이라고도 함

(2) join() Example

• 단순 join() 예제는 conditino variable를 올바르게 사용하기 위한 기본 요구 사항을 보여준다.
  • state variable → done
  • lock for the state variable
  • loop checking a condition using state variable

(3) Scenario(1)

• Thread-1은 join()을 먼저 실행한 다음, Thread-2는 exit()를 실행
  1. Thread-1
     • lock을 획득하고 wait()을 호출
     • 스스로를 sleep 모드로 전환하고 lock을 원자적으로 해제
  2. Thread-2
     • lock을 획득하고 state variable(done)을 1로 설정
     • signal()을 호출
       • Thread-1이 활성화되고 lock이 원자적으로 다시 획득되면 loop하는 동안 종료된다.

pthread_cond_wait(&c, &m) : unlock을 해주기 때문에 그 사이에 다른 스레드가 접근 가능

(4) Scenario(2)

• Thread-2는 exit()을 먼저 실행한 다음, thread-1은 join()을 실행
  1. Thread-2
     • lock을 획득하고 state variable(done)을 1로 설정한 다음 signal()을 호출
       • signal()은 condition에 sleep인 스레드가 없기 때문에 영향을 주지 않음
  2. Thread-1
     • lock, set state variable를 1로 가져옴
     • done이 이미 1로 설정되어 있으므로 loop로 들어가지 않음

(5) Broken Solution(1)

• mutex를 사용하지 않는 대체 구현
  • thread-2가 done 값을 1로 설정하고 thread-1 state variable을 확인한 후 바로 CV로 신호를 보내면,
    • wait()을 호출한 후 Thread-1이 고착됨
• Tip
  • signal() 또는 wait()를 호출할 때 lock을 유지

(6) Broken Soluction(2)

• state variable이 없는 대체 구현
  • thread-1이 CV에서 sleep하기 전에 Thread-2가 CV에서 신호를 보내면,
    • Thread-1은 wait()을 호출한 후 영원히 sleep 모드로 전환됨
• state variable의 중요성

3. Semaphore As Condition Variables

1) Semaphore As Condition Vairables

• Semaphore는 스레드가 condition을 충족되기를 기다리는 동안 진행을 중지하려는 경우에도 유용하다.
  • semaphore의 값을 변경하는 데 사용할 수 있는 작업은 P()와 V()뿐이다.(초기설정 제외)
  • P()는 block할 수 있지만 V()은 block할 수 없음
• Semaphore는 두 가지 용도로 모두 사용됨
  1. Mutual exclusion
  2. Condition synchronization
     • 스레드가 condition이 true가 되기를 기다림 → waiting
     • 다른 스레드가 waiting 스레드를 깨움 → signaling

(1) 예시

• 스레드가 다른 스레드를 생성한 다음 실행이 완료될 때까지 wait하려고 한다고 가정
• 이 semahpore의 초기 값은 얼마여야 할까? → 0이어야 함 / 1인 경우 실행이 그냥 종료
  • condition variable로서의 semaphore

4. Producer and Consumer Problem

1) Producer/Consumer Problem

• 다음에 직면할 동기화 문제는 producer/consumer 문제로 알려져 있다.
  • Dijkstra에 의해 처음 제기된 bounded buffer problem이라고도 함
  • 일반화된 semaphore를 이해하기 위해
• 예제 : Multi-threaded web server
  • producer와 consumer 간 HTTP 요청의 work queue(bounded buffer)

buffer 크기를 1로 가정한 상황

Producer : 자원의 생성•추가하는 일을 함 → buffer가 꽉 찼을 때를 고려
Consumer : 자원의 해제•삭제하는 일을 함 → 공유자원(buffer)이 없을 때를 고려
* 다수의 쓰레드로 구성된 프로그램에서 공유자원(ex. buffer etc.)에 동시접근 시 발생할 수 잇는 실행 제어 문제

2) Producer/Consumer Problem using CV

• Infinite Buffer(무한 버퍼)를 가정하면!

결과적으로 문제가 있는 코드

• 이 해결책은 single consumer와 single producer에서만 작동
• consumer가 둘이고 producer가 하나라고 가정(MAX = 1)
• 다음은 문제가 발생하는 경우를 보여줌
  • consumer1이 최초 실행되다가 최초 count = 0이므로 wait()을 만나 sleep 상태가 됨
  • producer는 running 상태가 되고 put(value)를 통해 count = 1로 바뀌고 signal()을 통해 신호를 보내 consumer1이 ready 상태가 됨
  • producer는 다시 반복되다가 count = 1이므로 wait()을 만나 sleep 상태가 됨
  • 이때 우리는 consumer1을 깨우기 위해 ready state로 주었지만 먼저 ready state였던 consumer2가 running 상태가 됨
  • consumer1이 get해야 하는 것을 consumer2가 get하게 되는 상황이 발생할 수 잇음!!!

(1) Re-checking the condition!

• waiting thread는 간단히 if 구문 대신 잠시 동안 루프에서 condition을 다시 확인함
• rechecking을 하지 않으면 waiting thread는 condition이 변경되지 않았음에도 불구하고 condition이 변경되었다고 생각하며 계속 진행됨

• 더 낫지만, 여전히 문제 발생
  • 여러 스레드가 CV에서 waiting 상태인 경우, wait queue에 따라 깨울 스레드가 달라짐

Tc1이 Tc2를 깨우게 된 상황에서 Tc1이 get()을 통해 count == 0으로 만들었기 때문에 Tc2는 wait상태로 모두가 sleep 상태가 된 상황

3) Producer/Consumer Problem Solution

• consumer는 producer만 깨워야 하며, 그 반대도 동일
• Solution : 두개의 condition variable을 사용
  1. Empty condition
  2. Fill condition
• 보다 효율적인 동기화를 가능하게 함

• Semaphore fill, empty, m
  • 초기 : fill = 0, empty = MAX, m = 1

consumer는 mutex를 잡고 누군가가 signal full을 보내기를 기다리고 있

• 이제, 효과적인 해결책
• 초기 : fill = 0, empty = N, m = 1

(1) 코드

(2) 세마포어 메커니즘

• Consumer : A, B, C
• Producer : D

(3) Semaphore의 단점

• wait 및 signal 작업을 프로그램에서 분산할 수 있음
  • Unstructured construct
  • 디버깅 및 correctness 문제
• 예제 : Deadlock
  • 2개 이상의 process가 각각 다른 프로세스 중 하나가 작업을 수행하기를 기다리고 있어 진행할 수 없는 경우
    • S와 Q가 1로 초기화된 두 개의 Semaphore라고 하자

5. Readers and Writers Problem

1) Readers-Writers Problem

• 여러 개의 동시 프로세스 간에 data set 공유
  1. Readers : data set만 읽을 수 있음 → 업데이트를 수행하지 않음
  2. Writers : 읽고 쓸 수 있음
• 문제
  • 한 명의 Writer만 동시에 공유 데이터를 접근할 수 있음
  • 여러 Readers가 동시에 읽을 수 있도록 허용
  • 하나 이상의 reader 읽고 잇는 경우, subsequent reader들은 입력하기 전에 기다릴 필요가 없음
• Shared Data(공유 데이터)
  • DB
  • int readcount = 0;  → reader의 수의 추적함
• Synchronization variable(동기화 변수)
  • DB의 경우 Semaphore wsem이 1로 초기화됨
  • readcount에 대해 Semahore x는 1로 초기화됨

reader preference 코드 → reader에 더 우선권을 줌

<세마포어를 이용한 readers/writers 문제 해결: reader에게 우선권이 있음

• 읽기 중인 reader가 하나 이상 있는 한 reader가 데이터 영역을 제어할 수 있음
  • reader는 우선권이 있고 writer는 starvation의 대상이다.

/* program readersandwriters */
int readcount;
semaphore x = 1, wsem = 1;
void reader() 
{
	while(true){
    	seeWait	(x);
        readcount++;
        if(readcount == 1)
        	seeWait (wsem);
        semSignal (x);
        READUNIT();
        seeWait	(x);
        readcount;
        if(readcount == 0)
        	semSignal	(wsem);
        semSignal	(x);
    }
}
void writers()
{
	while(true) {
    	seeWait	(wsem);
        WRITEUNIT();
        seeSignal	(wsem);
    }
}
void main()
{
	readcount = 0;
    parbegin (reader,writer);
}

• 새로운 reader가 데이터에 접근할 수 없도록 보장하기 위해 적어도 하나의 writer가 쓰기 의사를 선언
  • 접근을 원하는 writer가 하나 이상 있는 동안 모든 reader를 금지하는 세마포어 rsem
  • rsem 설정을 제어하는  변수 writecount

• reader의 경우, 하나의 추가적인 세마포어가 필요하다 : z
  • rsem에 빌드할 수 없도록 해야 함
  • 하나의 reader에마 rsem에서 queue에 넣을 수 있음

<Semaphore를 이용한 Bounded-buffer Producer/Consumer 문제의 해결책>

/* prgram boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        semWait(e);
        semWait(s);
        append();
        semSignal(s);
        semSignal(n);
    }
 }
 void consumer()
 {
 	while(true) {
    	semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e);
        consume();
    }
 }
 void main()
 {
 	parbegin(producer, consumer);
 }

<Semaphore를 이용한 readers/writers 문제 해결 : writer에게 우선권이 잇음>

/* program readersandwriters */
int readcount, writecount;
void reader()
{
	while(true) {
    	semWait(z);
       	semWait(rsem);
        semWait(x);
        readcount++;
        if(readcount == 1)
        	seeWait(wsem);
        semSignal(x);
        semSignal(rsem);
        semSignal(z);
        READUNIT();
        semWait(x);
        readcount--;
        if(readcount == 0) semSignal(wsem);
        semSignal(x);
    }
}
void writer()
{
	while(true) {
    	semWait(y);
        writecount++;
        if(writecount == 1)
        	semWait(rsem);
        semSignal(y);
        semWait(wsem);
        WRITEUNIT();
        semSignal(wsem);
        semWait(y);
        writecount;
        if(writecount == 0) semSignal(rsem);
        semSignal(y);
    }
}
void main()
{
	readcount = writecount = 0;
    parbegin(reader, writer);
}