OS_08_2_Synchronization

1. Synchronization with OS Support

1) Semaphores

• 이전의 해결책들은 더 복잡한 synchronization problem에서는 적용하기가 어려움
• 그래서 semaphore를 사용
  • Semaphore S - integer variable
  • 2개의 atomic한 명령을 통해서만 접근할 수 있다.
    • P(proberren, wait) and V(verhogen, signal)
  • Hardware나 software구현이 가능하다.

wait(S):
	while S<=0 do no-op; //양수가 아니면 반복
		S--; //양수면 감소 즉, wait와 signal사이에 atomic함이 보장된다.

signal(S):
	S++; //끝나면 증가

a) Critical Section of n Processed

• Shared data:
  • semaphore S; //initially S = 1
• Process Pi

do{
	wait(S);
		critical section
	signal(S);
		remainder section
} while(1);

b) Atomicity and Bounded Waiting

• Atomicity
  • OS는 S 접근에 대해서 atomic함을 보장한다.
• Bounded waiting
  • OS는 bounded wating을 wait(S)에서 return되는 순서를 통제함으로써 보장한다.

c) Busy Waiting Semaphore

• 이전에 봤던 모든 solution은 busy waiting을 필요로한다.
  • process가 critical section에 존재한다면, 다른 process들은 loop를 진행하면서 critical section에 들어가기를 원한다.
  • CPU가 소득없이 사용되므로 CPU가 낭비된다.
• 단일 CPU가 다른 여러 process와 공유되는 multiprogramming system에서는
  • busy waiting은 CPU cycle의 낭비를 초래한다.
  • 이러한 유형의 semaphore를 spinlock이라고 칭한다.
  • lock이 짧은 시간동안 유지될 것으로 예상될 때, spinlock은 유용하다.

d) Semaphore Implementation to Avoid Busy Waiting

• 주요 아이디어
  • semaphore에서 기다리고 있는 process는 busy waiting을 시키는 것보다 block한다.
  • 다른 Process가 signal 명령(critical section이 끝남)을 실행한다면 process를 깨운다.
• Semaphore 구조체

typedef struct{
	int value;
	struct process *L;
}semaphore;

• 2가지 operation
  • Block : process를 중단시킨다 (running을 waiting으로 강제로 바꾼다.)
  • Wakeup : blocked process P를 수행시키기 위해 깨운다.

e) Blocking Semaphore

• Semaphore의 operation

wait(S):
		S.value--;
		if(S.value <0){
			add this process to S.L;
			block; //process state -> waiting

signal(S):
		S.value++;
		if(S.value <=0){
			remove a process P from S.L;
			wakeup(P);
		}

• negative semaphore values
  • busy waiting으로 구현된 semaphore은 negative value를 가질 수 없다.
  • 하지만 blocking and waking-up으로 구현된 semaphore는 negative value를 가질 수 있다.
  • 음수 개 만큼의 process가 waiting하고 있다고 할 수 있다.
  • value를 먼저 감소시킨 결과값이다.
• list of waiting process
  • 각 PCB에 link field를 사용하여 쉽게 구현할 수 있다.
  • bounded waiting을 보장하기 위해서 FIFO queue를 사용한다.
  • 그러나 세마포어의 올바른 사용은 특정한 대기 큐 전략에 의존하지 않는다.

f) Two Types of Semaphores

• Binary semaphore
  • semaphore는 0과 1사이의 값만 가질 수 있다.
    • 초기값은 보통 1
  • Blocking semaphore는 음수 값을 가질 수 있기에, value가 1을 넘지 않는 다면 binary semaphore라고 칭한다.
• Counting semaphore
  • semaphore는 1보다 큰 값을 가질 수 있다.
  • counting semaphore는 여러개의 process가 critical section에 동시에 실행될 수 있도록 한다.
    • 초기 값은 process들의 최대 값이며, 이 값이 critical section에 실행됨을 허용하는 값이다.
  • 이는 binary semaphore를 사용하여 구현이 가능.

g) Semaphore as a General Synchronization Tool

• Semaphore는 general synchronization tool로 사용 가능하다.
  • mutual exclusion 뿐 아니라 cooperating process들의 원하는 실행을 보장하기 위해서 사용가능하다.
• Excute B in Pj only after A executed in Pi
  • semaphore flag는 처음에 0이다.

signal로 끝났음을 알려줌, wait에서 A가 끝나야 B가 실행됌.

h) Deadlocks and Starvation

• Deadlock
  • 두 개 이상의 프로세스가 서로가 기다리는 이벤트로 인해 무기한으로 대기하는 상태.
  • S와 Q가 두 개의 semaphore, 초기값은 1.

• P0에서 S→0 Q→-1, P1에서 Q→0 S→-1 즉, P0, P1 모두 진행하기 못하고 기다리기만 한다.

• P0에서 Q는 -1, P1에서 S는 -1 signal이 발생해야 wait를 중단하는데 그러지 못함.

• Starvation (indefinite blocking)

  • 중단 된(blocking) process는 semaphore queue에서 나오지 않을 수 있다. (LIFO queueing)
  • 나중에 들어온 process를 먼저 스케줄링 하기에, block된 것은 영원히 block이 가능

2) Mutex

• Mutex는 종종 semaphore의 동의어로 사용된다.
  • MUTual EXclusion
• Mutex와 Semaphore의 차이점
  • Mutex는 binary semaphore이다.
  • Mutex는 소유 개념을 가지고 있다.
    • 즉, 뮤텍스를 잠근 작업만이 해당 뮤텍스를 해제할 수 있다.
• POSIX APIs for Mutexes
  • int pthread_mutex_init(pthread_mutex_t mutex, const pthread_mutexattr_t mutex_attr) → mutex를 초기화 하는 함수
  • int pthread_mutex_destroy(pthread_mutex_t *mutex) → mutex를 제거하는 함수
  • int pthread_mutex_lock(pthread_mutex_t *mutex) → Mutex를 잠그는 함수. 다른 스레드가 이미 잠근 경우 해당 스레드는 뮤텍스가 해제될 때까지 대기.
  • int pthread_mutex_unlock(pthread_mutex_t *mutex) → Mutex를 해제하는 함수.
  • int pthread_mutex_trylock(pthread_mutex_t *mutex) → Mutex를 잠그는 것을 시도하는 함수.
    • to see whether a mutex is locked, but doesn't block

2. Classical Synchronization Problems

1) Classical Problems

• Semaphore와 Mutex는 primitives(기본적인 도구(?))로 사용한다.
  • 하지만, 이 primitive를 사용하여 올바른 동기화를 시키는 것은 프로그래머의 책임이다.
• Non-trivial and classic synchronization problems
  • Readers and Writers Problem
  • Dining-Philosophers Problem

2) Readers-Writers Problem

• Readers-Writers problem
  • single buffer에 multiple reader과 multiple write가 접근하는 경우를 가정하자.
  • 동시에 write에 access하는 경우에만 race가 발생한다.
    • writer는 shared object에 대해 독점 access가 필요하다.
    • “Single writer in CS” or “multiple readers in CS”

왼쪽은 한 개가 읽고, 한 개가 씀. 오른쪽은 여러개가 읽고, 한개가 씀

• 2가지의 경우가 있다 (둘 다 starvation 문제를 가지고 있음)
  • First readers-writers problem → reader에게 특혜
    • reader는 writer가 shared object에 대한 접근 권한을 얻기 전까지 기다리지 않는다.
    • reader들은 다른 reader들을 기다리지 않음.
  • Second readers-writers problem → writer에게 특혜
    • write가 준비가 되면, writer는 가능한 빨리 일을 수행한다.
    • writer가 shared object에 접근을 대기하고 있다면, 새로운 reader는 일을 수행하지 않는다.

a) First Readers-Writers Problem

• The First readers-writers problem
  • reader에게 특혜를 준다.
  • writer는 unbounded waiting을 겪는다.
• Shared data
  • semaphore S, wrt;
  • initially, S = 1, wrt = 1, readcount = 0

wait(wrt);
	...
	/* writing is performed */
	glob_x++;
	glob_y++;
	...
signal(wrt);

wait(S);
readcount++;
if(readcount == 1)
	wait(wrt);
signal(S);
	...
	/*reading is performed */
	temp1 = glob_x;
	temp2 = glob_y;
	...
wait(S);
readcount--;
if(readcount == 0)
	signal(wrt);
signal(S);

• writer는 reader가 모두 나가야 수행 할 수 있다.
• reader는 처음 들어올 때, writer의 signal을 1로 바꾼다.
• readcount 변수 변경을 atomic하게 진행하기 위해 wait(S), signal(S)를 사용한다.

보통 writer가 많을 때 쓴다. (그래서 reader에게 특혜를 줌)

b) Second Readers-Writers Problem

• The second readers-writers problem
  • writer에게 특혜를 준다.
  • reader는 unbounded waiting을 겪는다.
• Shared data
  • semaphore S1, S2, wrt, rd, wrtpending;
  • Initially,
    • S1 = 1, S2 = 1, wrt = 1, rd = 1, wrtpending = 1,
    • readcount = 0, writecount = 0

wait(S2);
writecount++;
if(writecount == 1)
	wait(rd);
signal(S2);
wait(wrt)
	...
	writing is performed
	...
signal(wrt);
wait(S2);
writecount--;
if(writecount == 0)
	signal(rd);
signal(S2);

wait(wrtpending);
wait(rd);
wait(S1);
readcount++;
if(readcount == 1)
	wait(wrt);
signal(S1);
signal(rd);
signal(wrtpending);
	...
	reading is performed
	...
wait(S1);
readcount--;
if(readcount == 0)
signal(wrt);
signal(S1);

• writer는 writecount에 작업을 수행하기 전에 S2를 통해 atomic을 보장함.
• writecount(writer의 개수)를 늘리고, 처음 writer가 들어왔다면 rd semaphore에 대해서 wait를 수행
  • 다른 reader가 read를 수행할 수 없음.
• wrt semaphore를 통해서 읽기작업을 수행
• reader는 wrtpending semaphore를 사용하여 writer가 작업중인 경우 reader가 작업을 못하도록 막음.

• 즉, read작업이 끝나고, write 작업을 시작한다면 write작업이 모두 끝나야 read작업 시작

c) The Third Readers-Writers Problem?

• The third readers-writers problem
  • 둘 다에게 priority를 준다.
    • 도착순서에 따라 reader와 writer가 우선순위를 가진다.
  • 만약 reader들이 자원에 접근중인 동안 writer가 도착한다면, writer는 reader들이 resouce를 free할 때 까지 기다린 후, resource를 변경한다.
  • 이와 동시에 도착하는 reader들은 기다려야한다.

4) Dining-Philosophers Problem

• 생각하고 먹는 5명의 철학자를 고려한다.
  • circular table에 5개의 single chopsticks이 잇다.
  • 철학자들은 가끔 배가 고파지고, 자신에게 가장 가까운 두개의 젓가락을 집으려고 한다.
  • 철학자는 한 번에 한 개의 chopstick만 집을 수 있다.
• DP problem
  • concurrency-control의 문제이다.
  • deadlock and starvation free 방식으로 여러 프로세스 사이에 여러 자원을 할당해야함을 나타내는 예제

• 5개의 semaphore를 사용한 간단한 solution

  • 철학자들은 wait 명령을 수행함으로써 chopstick을 집으려고 한다.

  • 철학자는 signal 명령을 수행함으로써 chopstick을 내려놓는다.

  • Declare : semaphore chopstick[5];

  • philosopher i의 구조

    do {
        wait(chopstick[i]);
        wait(chopstick[(i+1) % 5]);
    			    eat ...
        signal(chopstick[i]);
        signal(chopstick[(i+1) % 5]);
    			    think ...
    } while (1);

  • wait(chopstick[i]) → 자신의 왼쪽에 있는 젓가락을 기다림.

  • wait(chopstick[(i+1) % 5] → 자신의 오른쪽에 있는 젓가락을 기다린다.

  • signal(chopstick[i]) → 자신의 왼쪽에 있는 젓가락을 내려놓음.

  • signal(chopstick[(i+1) % 5)] → 자신의 오른쪽에 있는 젓가락을 내려놓음.

• 방금의 해결책은 deadlock을 발생시킬 가능성이 있다.
• Possible solutions
  • 최대 4명의 philosophers가 동시에 table에 앉을 수 있도록 허용한다.
  • philosopher가 두 개의 젓가락을 모두 사용 할 수 있을 때만 젓가락을 집을 수 있도록 한다.
  • 비대칭적인 solution 사용 → 홀수 번호의 철학자는 왼쪽의 젓가락을 먼저 집고 오른쪽의 젓가락을 집는다, 반대로 짝수 번호의 철학자는 오른쪽의 젓가락을 먼저 집고 왼쪽의 젓가락을 집는다.
• deadlock-free solution은 starvation의 가능성을 반드시 제거하는 것이 아니다. 즉, 교착 상태가 발생하지 않더라도, 철학자 중 일부는 우선권을 얻지 못하고 무한이 대기할 수 있다.