Synchronization Hardware

 

Synchronization Hardware

 

synchronization을 지원하는 hw가 있으면 앞의 문제가 수월하게 해결된다.

 

이전까지는 한 사용자가 변경 사항을 저장하지 않은 상태에서 다른 사용자가 읽어갔을 때 불일치하여 생기는 문제였다.

따라서 이 문제는 하드웨어가 test&modify 작업을 원자적으로(atomic하게) 수행하도록 지원하면 해결 가능하다.

 

다음 두 연산을 atomic하게 한 번에 수행 가능하도록 해준다.

1. Read: a값을 읽어가고(0/1)

2. TRUE: a값을 TRUE로 만들기(1로 세팅)

 

예컨대 다음과 같이 빨간 형광펜 부분에서 atomic한 수행이 발생한다.

lock=False일 경우: lock을 read하는 동시에 TRUE로 변경시킴

lock=True일 경우: while문 조건에 만족하지 않으므로 실행x

 

Semaphores와 Monitors는

위처럼 코드를 직접 짜지 않고 추상화시킨 방식들이다.

구조가 어떠한지, 컴퓨터에서 어떻게 표현되는지는 논외로 하고 그냥 객체와 그 객체가 가리키는 연산만 알면 된다.

Semaphores

 

Semaphores란

 

"S"라는 정수형 변수를 사용(Semaphore S)

- atomic 연산에 S를 변수로 넣어 접근 가능

- S값을 통해 lock을 걸어 접근 가능한 프로세스 개수 조절 가능

 

<atomic 연산 2가지 종류>

1. P(S): 공유 데이터를 획득하는 과정을 피연산으로 사용(ex. lock 거는 과정)

- 아직 자원이 다 차지되지 않아 쓸 수 있는 상황(S>0) -> S-- 한 다음 P연산 수행

- 이미 자원이 다 차지된 상황(S<=0) -> P연산을 수행하지 못하고 기다림

 

2. V(S): 공유 데이터를 반납하는 과정을 피연산으로 사용(ex. lock 풀어주는 과정)

다 사용한 다음에 반납하여 다른 사용자가 쓸 수 있도록.

 

=> ex. S=1이면, 하나의 프로세스만 공유 데이터에 접근할 수 있음

=> 실제로 자원을 사용하는 코드는 P와 V 사이에 존재

즉, 공유 자원을 세고, 남은 자원들이 있는지 확인하여 제어 및 관리하는 데 S변수를 사용 가능

 

<코드>

while문을 계속 돌면서 P연산을 못 빠져나감

-> (문제) busy-waiting(spin lock): 자신의 CPU 시간을 쓰면서 while문만 계속 도는 문제

* 계속 while문 spin하며 확인한다는 의미

-> (해결) Block&Wakeup(sleep lock): CPU를 아예 반납하고 blocked 상태로 전환해 낭비 줄임

* lock 이 걸리면 sleep시킴

 

<Block&Wakeup>

: semaphore를 단일값이 아니라 구조체로 정의하는 방법

* 구조체에 들어가는 것: semaphore값 & wait queue

semaphore 구조체

semaphore 구조체 시각화

L이라는 변수를 두어, semaphore을 줄세우는 리스트 구조

- block: block 호출한 프로세스는 suspend되고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

- wakeup(P): block된 프로세스 P를 wakeup시키고 이 프로세스의 PCB를 ready queue에 옮김

 

 

semaphore가 그냥 값일 때는 변수 S가 여분의 자원 수를 말하지만

semaphore가 구조체로 정의된 경우에는 value가 그냥 여분 자원이 있는지(양수) 없는지(음수/0) 여부를 가리키는 것이다.

 

(+)효율적

(-) overhead 존재

critical section의 길이가 길거나 빈번할 경우에는 효율적이지만 

길이가 짧거나 경쟁이 치열하지 않은 경우에는 busy-wait 방식이 나을 수 있다.

하지만 일반적으로는 block&wakeup 방식이 더 좋음.

 

<semaphore의 종류>

 

- Counting semaphore: 자원 개수를 세야할 때 주로 사용(도메인이 0 이상인 임의의 정수값)

- Binary semaphore(=mutex): 주로 mutual exclusion(lock/unlock)에 사용(0/1값만 가질 수 있음)

* 상호배타적 접근 막으려면 1

 

<문제: deadlock & starvation>

semaphore 변수 2개 S, Q를 모두 얻어야만 하는 작업이 있다고 하자.

 

"deadlock이 발생하면 starvation이라는 문제 생김 -> 획득 순서를 만들어주어 해결 가능"

<deadlock>
초기에 P0는 S, P1은 Q라는 작업을 차지한 상태
- P0가 S를 빼앗김 -> Q를 가져와 작업하려고 하지만 이미 P1이 차지한 상태 -> 기다려야 함
- P1이 Q를 빼앗김 -> S를 가져와 작업하려고 하지만 이미 P0가 차지한 상태 -> 기다려야 함
=> (아직 끝나기 전이므로) 영원히 서로에게 필요한 것을 차지하고 안 내어놓기 때문에 제자리걸음

따라서 <starvation>
: indefinite blocking(suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상)
∵ P0은 Q를, P1은 S를 영원히 얻지 못하기 때문

 

<해결책>
Q를 얻기 위해서는 전에 반드시 S를 먼저 획득해야 가능하도록 지정해두기

 

 

Synchronization의 문제점

 

1. Bounded-Buffer Problem(Producer-Consumer Problem)

- 공유데이터: Bounded-Buffer(크기가 유한해서 producer와 consumer이 공유하는 buffer)

- 접근 주체: producer & consumer

- semaphore 변수: counting semaphore

 

(문제 시나리오) 두 producer(consumer)가 빈자리만 보고 데이터를 동시에 입력하(가져가)는 경우

(해결책) 공유 데이터에 넣을(producer)/가져갈(consumer) 예정이라면 lock을 건다.

 

- producer 입장에서 자원: 빈 동그라미(넣어야 하기 때문) 없으면 consumer가 빼갈 때까지 기다림

- consumer 입장에서 자원: 차있는 동그라미(빼가야 하기 때문) 없으면 producer가 넣을 때까지 기다림

 

 

2. Readers and Writers Problem

- 공유데이터: 데이터베이스 & readcount;

- 접근 주체: reader & writer

- semaphore 변수

* db: reader와 writer가 공유 데베를 올바르게 접근하도록 lock 걸어줌

cf) "readcount; " → reader의 경우 특별히 동시에 가능케 하도록 하므로 접근자 수 count

* mutex: "readcount;" 조작(증가/감소) 위해 사용

 

(시나리오)

reader는 혼자 독점하면 비효율적

writer는 독점해서 써야 함

 

(해결책) 

reader가 접근할 때는 다른 reader도 접근 가능하도록

writer가 접근할 때는 아무도 못 쓰도록 

 

 

=> (한계)starvation 발생 가능

(해결책) 신호등의 원리처럼 특정 시간까지 도착한 reader만 읽을 수 있도록 하고 막음 → writer에게 기회 줌 

 

 

3. Dining-Philosophers Problem

 

5명의 철학자가 원탁에 앉아서 생각하고 밥먹고 반복

- 공유데이터: 젓가락

- 접근 주체: 5명의 철학자

 

(문제점) 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우 → deadlock 가능성 있음

(해결 방안) 

1. 4명만 테이블에 동시에 앉을 수 있도록 하기

2. 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있도록 함

3. 비대칭: 짝수 철학자는 왼쪽 젓가락부터, 홀수 철학자는 오른쪽 젓가락부터 집을 수 있도록(아래와 같은 원리)

<semaphore 시나리오>

- semaphore:

* self[5]
** self=0 → 5명이 모두 양쪽 모두는 집을 수 없는 경우
** self=1 → 5명이 모두 양쪽 젓가락 집을 수 있는 경우

* state[5]
: 상태를 나타내는 semaphore(thinking/hungry/eating)

* mutex
state를 건드리기 위해 lock을 걸어주고 풀기 위한 semaphore

 

 

do{
	pickup(i);
    eat();
    putdown(i);
    think();
}while(1);

 

<pickup()>

void pickup(int i){
	P(mutex); //state 건드리기 위해 lock 풀기
    state[i]=hungry; //state hungry로 변경
    test(i); //5명 철학자가 모두 양쪽 젓가락을 잡을 수 있는지 check
    V(mutex); //state 건드리지 못하도록 lock 걸기
    P(self[i]); //test 결과 self[i]=1 -> 젓가락 잡기 끝 -> self[i]=0으로 변경 -> eat()로 넘어감
    //test 결과 self[i]=0 -> 이미 0으로 되어있기 때문에 변경 불가 -> sleep상태
}

 

<test()>

void test(int i) {
	if(state[(i+4)%5]!=eating && state[i]==hungry && state[(i+1)%5]!=eating) { //양쪽 사람들이 밥먹고 있지 않다면
    	state[i]=eating; //먹기
        V(self[i]); // 양쪽 사람이 둘다 먹고 있지 않다면 -> self[i]=1 -> pickup()에서 P(self[i])가 self[i]=0으로 바꿔줌
        //옆사람이 먹고 있어 조건 불만족 -> self[i]=0 -> sleep
    }
}

 

<putdown()>

void putdown(int i){
	P(mutex);//state 변경 위해 lock 풀기
    state[i]=thinking; //다 먹었으므로 젓가락 내려놓고 생각
    test((i+4)%5);//자신 때문에 옆 사람들이 test 통과 못한 것 우려해서 젓가락 내려놓은 후 test 대신 수행해줌
    test((i+1)%5);
    V(mutex);//state lock 걸기
}

 

 

Monitor

 

Semaphore 문제점

 

- 코딩하기 힘들다

- 정확성 입증 어려움

- 자발적 협력 필요

 

- 한 번 실수하면 모든 시스템에 치명적 영향

V(mutex)
Critical Section
P(mutex)

=> critical section에 여러 명 들어갈 수 있게 됨

P(mutex)
Critical Section
P(mutex)

=> 이후에는 어느 누구도 critical section에 들어갈 수 없게 됨

 

==> monitor이 해결해줌

Monitor

 

: 동기화 문제(공유데이터에 대한 동시 접근)를 책임져줌(queue에 놓아줌) → 프로그래머가 할 필요x → 실수 방지

: 오직 모니터 안에 정의된 함수만 실행 가능 → 공유데이터에 lock걸 필요 없음

 

semaphor 변수 대신 "condition variable" 사용

1. 자원 여분 있을 때 → 그냥 수행

2. 자원 여분 없을 때 → queue에 줄세우고 blocked 상태로..(x.wait) → 자원 생기면 깨워라(x.signal)

 

 

semaphor 변수는 원자적으로 1 빼거나 더해야 했지만 monitor은 동시 접근 막는 역할하기 때문에 그런 작업 필요 없음(애초에 한 프로세스만 한 번에 수행하기 때문)

 

	semaphore	monitor
변수 역할	자원 개수 세기 → 원자적으로 1 빼거나 더해야 함	자원 여분 없을 때 잠재워주고 줄 세우는 queue 역할만 수행 → wait / signal로 상태 변경만
함수 형식	P로 자원 빌리고 V로 자원 반납	P와 V같은 것 쓰지 않음 → 자연스럽고 이해 쉬움

monitor bounded_buffer
{
	int buffer[N];
    condition full, empty;
    
    void produce(int x) //데이터 생산해서 buffer에 집어넣음
    {
    	if there is no empty buffer
        	empty.wait(); //빈 버퍼가 없으면 빈 버퍼 생길 때까지 기다림
        add x to an empty buffer
        full.signal(); //빈 버퍼에 데이터 넣음
    }
    
    void consume(int *x) //buffer에서 데이터 꺼내 감
    {
    	if there is no full buffer
        	full.wait(); //차있는 버퍼가 없으면 producer가 채워넣을 때까지 기다림
        remove an item from buffer and store it to *x
        empty.signal(); //찬 버퍼에서 데이터 꺼내감
    }
}

 

실제로 젓가락을 잡는지는 알수 없고

잡을 수 있는지 여부에 대한 공유 변수 존재

 

do{
	pickup(i);
    eat();
    putdown(i);
    think();
}while(1);

 

<pickup()>

void pickup(int i){
    state[i]=hungry; //state hungry로 변경
    test(i); //5명 철학자가 모두 양쪽 젓가락을 잡을 수 있는지 check
    if(state[i]!=eating) //먹을 수 없으면(self[i]=0)
    	self[i].wait(); //젓가락 양쪽 다 잡을 수 있을 때까지 기다림
}

 

<test()>

void test(int i){
	if(state[(i+4)%5]!=eating && state[i]==hungry && state[(i+1)%5]!=eating) { //양쪽 사람들이 밥먹고 있지 않다면
    	state[i]=eating;
		self[i].signal(); // 조건 만족하면(self[i]=1) 냅두고, 조건 만족하지 않으면(self[i]=0) 깨움 -> pickup()에서 wait() 깨져 밥먹을 수 있게 됨
}

 

<putdown()>

void putdown(int i){
	state[i]=thinking;
    test((i+4)%5);
    test((i+1)%5);
}