synchronization 2

지난 포스트에서 동기화 기법인 Lock에 대해서 살펴보았다.

하지만 spinlock이나 disabling interrupt는 short, simple critical section에서만 효과적이다. Mutual exclusion을 제외하고는 별달리 뭘 해주지 않기 때문이다. 따라서 이를 해결하기 위해 동기화 기법들이 여럿 나오게 되었다.

user mode에서 동기화를 해주는 것을 High level synchronization이라고 하며 우리가 자주 쓰는 semaphore, monitor는 여기에 해당한다.

 

High level synchronization

 

semaphore

: shared data의 갯수

semaphore는 사용가능한 shared data의 수를 의미한다. 따라서 semaphore가 있는 경우 critical section에 접근가능한 것이고, semaphore가 없는 경우 critical section에 접근 불가능한 것이다.

이 semaphore는 실행 순서 조절에도 활용이 가능하다.

 

semaphore의 두가지 종류

- counting semaphore: variable 값이 양수

- binary semaphore: variable 값이 0 또는 1

 

wait(), signal() 두 가지의 함수가 필요하다.

 

wait()은 사용 가능한 semaphore를 확보 및 대기하는 곳이고, signal()은 semaphore를 사용 후 반납하는 곳이다.

 

// semaphore structure
typedef struct {
    int value;
    struct process *L;
} s;

// wait
if(s.value == 0)
{
    add process to s.L
    block
}
lock(lock);
s.value--;
unlock(lock);

// signal
lock(lock);
s.value++;
unlock(lock);
if(s.value > 0)
{
    remove a process p from s.L
    wakeup(p)
}

 

structure s

: 구조체의 value는 사용가능한 semaphore의 갯수이고, L은 queue이다. 연결리스트로 구현된다.

 

wait()

: value 값을 확인하여 0인 경우는 사용할 수 있는 semaphore가 없으므로 프로세스를 queue에 넣고 프로세스를 중지한다.

그게 아닌 경우 value값을 -1하여 shared data를 확보한다. 이때 value에 접근하는 것도 lock, unlock으로 보호한다.

 

signal()

: shared data를 반납하기 위해 value값을 +1한다. 이때 wait과 마찬가지로 value에 접근하는 것도 lock, unlock으로 보호한다.

그 후 value의 값이 0보다 큰 경우, 즉 사용가능한 semaphore가 생긴 경우 queue에서 프로세스를 하나 가져와서 그 프로세스에게 자원을 할당하고 실행시킨다. 이것이 wakeup이다.

---

이러한 semaphore를 사용하면 synchronization의 고전적인 문제들을 해결할 수 있다.

그럼 synchronization의 고전적인 문제들이 무엇이며 이를 semaphore로 해결하는 방법을 알아보자.

- bounded buffer problem

- readers and writers problem

- dining philosopher problem

---

bounded buffer ( == producer-consumer problem)

: 이러한 N크기의 circular queuef를 bounded buffer라고 한다.

이때 이 queue에 data를 넣는다면 producer, queue에서 data를 가져온다면 consumer이다.

count는 몇개의 데이터가 queue에 있는지 알려준다.

queue에 data를 넣고 빼는 함수는 다음과 같다.

 

// producer
void produce(data)
{
    while(count == N)
    	;
    buffer[in] = data;
    in = (in + 1) % N;
    count++;
}

// consumer
void consumer(data)
{
    while(count == 0)
    	;
    data = buffer[out];
    out = (out + 1) % N;
    count--;
}

 

이때 bounded buffer의 문제는 두가지이다.

1. busy waiting

2. count에 대한 동기화 없음

 

이를 semaphore로 해결하기 위해서는 semaphore 변수가 총 3개 필요하다.

 

// semaphore
mutex = 1
empty = N
full = 0

 

mutex는 count 변수 동기화를 위한 semaphore이고

empty, full은 busy waiting 해결을 위한 semaphore이다.

처음에는 buffer가 비어있기 때문에 empty = N, full = 0으로 초기화를 해준다. 또한 semaphore도 사용가능하기 때문에 1로 초기화해준다.

 

// semaphore를 사용한 producer
void produce(data)
{
    wait(empty);
    wait(mutex);
    buffer[in] = data;
    in = (in + 1) % N;
    signal(mutex);
    signal(full);
}

// semaphore를 사용한 consumer
void consumer(data)
{
    wait(full);
    wait(mutex);
    data = buffer[out];
    out = (out + 1) % N;
    signal(mutex);
    signal(empty);
}

 

produce()

: 생산하는 함수는 buffer에 빈공간이 있어야하기 때문에 wait(empty)로 비어있다는 것을 확인받는다. data를 넣은 이후는 buffer에 차있는 공간이 늘어난 것이므로 signal(full)을 통해 차있는 공간을 +1해주는 것이다.

 

consumer()

: 소비하는 함수는 buffer에 차있는 공간이 있어야 하기 때문에 wait(full)로 차있는 공간을 확인받는다. data를 뺀 이후는 buffer에 빈 공간이 늘어난 것이므로 signal(empty)를 통해 빈 공간을 +1 하는 것이다.

 

이를 직접 구현한 코드는 다음 포스팅을 참고하면 좋다

Synchronization in LINUX - POSIX Semaphore

 

---

Reader writer problem

: 데이터를 쓰고 있을 때 동시에 읽거나 쓰는 것을 막아야 한다.

즉 write process는 한번에 하나만 실행 가능

반대로 읽는 경우에는 동시에 읽을 수는 있지만 써서는 안된다.

 

semaphore과 shared data

 

// shareddata
readcount	= 0

// semaphore
mutex 		= 1
wrt		= 1

 

mutex는 readcount 보호를 위한 semaphore이며

wrt는 reading/writing의 동기화를 위한 semaphore이다.

 

 

// writer
void writer()
{
    wait(wrt);
    // write
    signal(wrt);
}

// reader
void reader()
{
    wait(mutex);
    readcount++;
    if(readcount == 1)
    	wait(wrt);
    signal(mutex);
    // read
    wait(mutex);
    readcount--;
    if(readcount == 0)
    	signal(wrt);
    signal(mutex);
}

 

writer()

: 다른 함수가 read나 write를 하더라도 먼저 wait(wrt)에서 wrt-1을 하기 때문에 대기하게 되어 접근이 불가능해진다.

write 후에는 signal(wrt)를 하여 wrt+1을 하여 다른 프로세스의 접근을 허용한다.

 

reader()

: 읽고 있는 프로세스의 수를 증가시키기 위해 readcount+1을 해준다. 이때 shared data 보호를 위해 mutex semaphore를 wait 해주어 mutual exclusion을 보장한다.

만약에 readcount의 수가 1이 되었다면 읽고 있는 프로세스가 있다는 뜻이므로 write process의 접근을 막아야한다. 따라서 wait(wrt)를 해주어 wrt-1을 실행하게 되면 다른 프로세스가 writer 함수에 접근하여 wait(wrt)을 할 때 사용할 wrt가 없으므로 자동으로 대기하게 되어 동기화가 이루어진다.

따라서 또 다른 read process는 당연히 접근이 가능하다!

 읽고 난 후에도 마찬가지로 readcount-1을 진행하고, shared data 보호를 위해 mutex semaphore를 wait 해주어 mutual exclusion을 보장한다. 이때 만약에 readcount의 수가 0이 되었다면 더 이상 읽고 있는 프로세스가 없다는 뜻이므로 write process의 접근이 허용된다. 따라서 signal(wrt)로 wrt+1을 실행하여 프로세스의 접근을 허용할 수 있는 것이다.