6. Process Syncronization (2)

Classical Problems of Synchronization

Synchronization Problem으로 대표적인 문제는 다음의 3가지이다.

1. Bounded-Buffer Problem

2. Readers and Writers Problem

3. Dining-Philosophers Problem

 

Bounded-Buffer Problem

일명 Producer & Consumer 문제라고도 불리는 이 문제는 프로듀서가 공유된 버퍼에 데이터를 쓰면 컨슈머가 데이터를 읽어가는 형태이다. 이때 버퍼의 사이즈는 무제한이 아니라 한정되어 있다.

버퍼는 프로듀서와 컨슈머 사이의 공유되는 공간이므로 프로듀서가 버퍼에 값을 쓰는 동안 컨슈머가 값을 읽어가도 안 되고, 컨슈머가 값을 읽고 있는 도중에 프로듀서가 값을 써서도 안 된다.

=> 즉, 버퍼에 대한 접근은 동기화가 되어야 한다.

쉽게 말해서 세마포어를 사용한다고 했을 때, 버퍼에 접근하기 전에 S를 호출하고 버퍼에 접근한 후 빠져나오면서 V를 호출하면 이 문제는 쉽게 해결이 된다.

 

그럼 뭐가 문제일까?

이 버퍼는 한정된 크기를 가진다. 그럼 프로듀서가 버퍼에 항상 데이터를 쓸 수 있는 것은 아니다. 버퍼가 꽉 차있으면 프로듀서는 데이터를 더 이상 쓰지 못한다. 마찬가지로 컨슈머 입장에서 프로듀서가 데이터를 천천히 생산하는 바람에 더 이상 소비할 데이터가 없으면 버퍼에서 값을 읽어가지 못 한다.
무작정 버퍼에 접근해서 데이터를 읽고 쓰는 것이 아니라 버퍼에 접근해도 되는 상황이면 접근하고 아니면 대기하고 이런 게 필요하다.

프로듀서 입장에서는 버퍼의 빈 공간을 나타내는 empty buf가 0보다 크면 값을 써도 되고, 컨슈머 입장에서는 full buf가 0보다 크면 값을 읽어도 된다.
그러면 empty buf와 full buf 라는 변수가 필요한데, full buf를 늘려주는 주체는 프로듀서고 empty buf를 늘려주는 주체는 컨슈머이다. 그러면 이 값 자체가 또 프로듀서와 컨슈머 사이의 공유 변수가 된다.
=> 이 변수에 대한 보호가 또 필요하다. 

물론 별도의 세마포어 변수를 이용해서 empty buf와 full buf를 보호해도 되겠지만, 공유변수 자체를 세마포어 변수로 만들어서 보호하는 방법이 있다.

프로듀서는 buffer에 값을 쓰려고 하기 전에 먼저 empty_buf 가 있는지 먼저 확인을 해야 한다.

반대로 컨슈머는 buffer에서 값을 읽으려고 하기 전에 먼저 full_buf가 있는지 먼저 확인을 해야 한다.

프로듀서는 P(N_empty-buf)를 호출해서 N_empty-buf가 0보다 큰지 확인한다.

그리고 0보다 크면 buf에 값을 쓰기 위해 P(S_mutex)를 호출하여 buf에 접근할 수 있는 권한을 획득한다.

critical section을 빠져 나오면서는 V(N_full-buf)를 호출하여 N_full-buf의 값을 1 증가시켜준다. 이로써 기다리고 있던 컨슈머가 있었다면 빠져나올 수 있게 된다.

 

비어있는 버퍼의 수와, 채워진 버퍼의 수를 counting semaphore를 사용해서 해결을 했다.
왜 이렇게 하면 해결이 될까? empty buf와 full buf가 공유 변수이기 때문에 다른 프로세스가 접근하고 있을 때 보면 안 된다. 예를 들어, empty buf를 프로듀서가 1 증가시키는 도중에 컨슈머가 읽으면 안 된다. 그렇다면 변수 각각을 P, V로 보호해서 동기화 문제를 해결하지 않고 서로 크로스 해서 P, V를 사용하면 해결이 될까? P, V가 "atomic" 하기 때문에 프로듀서와 컨슈머가 동시에 접근하는 것을 원천적으로 봉쇄한다.

=> 그래서 이 방법은 Solution이 될 수 있다.

=> 별도의 변수를 보호하기 위해서 또 다른 세마포어 변수를 선언하기 보다는 그 변수 자체를 세마포어 변수로 사용해서 P,V 함수의 atomic함을 이용해서 스스로 보호하도록 했다.

 

Readers-Writers Probelm

이 문제 역시 프로듀서 컨슈머 문제와 유사하다. Writer가 글을 쓰면 Reader가 글을 읽어가는 형태이다. Writer가 글을 쓸 때 Reader가 글을 읽을 수 없고, Reader가 글을 읽고 있으면 Writer가 글을 쓸 수 없는 것은 똑같다. 그래서 DB에 대한 접근자체는 상호배제가 이루어 져야 하기 때문에 db라는 binary 세마포어 변수를 사용한다.

그런데 차이점이 있다. 컨슈머는 데이터를 소비하는 반면에 Reader들은 값을 읽기만 한다. 즉, Read-only이다.

따라서 Reader들끼리는 DB에 동시에 접근해도 동기화 문제가 발생하지 않는다. 한 Reader가 읽고 있을 때 다른 Reader가 진입을 시도하면 허용해야 한다.

Reader들 사이에는 동시에 접근이 가능한데, 그때 스케줄링은 2가지 방법으로 할 수 있다.

B. Reader들이 글을 읽고 있는데 Writer가 글을 쓰려고 한다면 더 이상은 Reader가 진입을 하지 못 하게 막는다. 그리고 읽고 있던 Reader들이 모두 빠져나가면 Writer가 글을 쓰게 만들어주는 방법.

A. Writer가 와서 Reader들이 다 읽기를 기다리고 있다 하더라도 새로운 Reader가 진입을 시도하면 들어가게 둔다.

그리고 모든 Reader가 빠져나가고 나면 Writer가 글을 쓰게 하는 방법.

이 중 우리는 A 방법을 살펴볼 것이다.

 

Writer는 db 값이 1이면 들어갈 수 있기 때문에, Reader가 한 명이라도 읽고 있으면 db값을 0으로 만들어서 못 들어가게 해야 한다. 따라서 처음 들어가는 Reader는 P(db)를 호출해서 db값을 0으로 만들어준다. 그 뒤로 Writer는 P(db)를 호출해도 db가 0이라서 들어갈 수가 없다.
그런데 두 번째 들어가는 Reader는 굳이 P(db)를 호출하지 않아도 된다. 어짜피 Writer는 못 들어오고 있으니까.
그리고 제일 마지막에 나오는 Reader가 V(db)를 호출해서 db값을 1로 바꾸어준다.

그렇다면 내가 첫 번째 Reader인지 또는 마지막 Reader인지는 어떻게 알 수 있을까? 현재 읽고있는 Reader의 수를 Count하면 된다. readcount라는 변수를 선언해서 현재 글을 읽고 있는 Reader의 수를 파악한다. 글을 읽을 때 +1 시키고 다 읽고 빠져나올 때 -1시킨다.

그러면 readcount라는 변수는 Reader들 사이의 공유 변수가 되는 셈이다. 따라서 readcount 변수도 보호를 해주어야 한다. readcount를 보호하기 위해 mutex 세마포어 변수를 사용한다.

정리하자면 Writer와 Reader 사이의 상호 배제를 시켜주는 db 변수, Reader들 사이에 공유되는 변수 readcount, 그러한 readcount를 보호하기 위한 mutex 변수 이렇게 2개의 세마포어 변수와, 1개의 int 변수가 있다.

Writer는 write하기 전에 현재 읽고 있는 독자가 한 명이라도 있는지만 파악하면 되므로 P(db)를 호출하고 빠져나올 때 V(db)를 호출하기만 하면 된다.

그러나 Reader는 readcount 에도 접근해야 하고 이후 Writer가 글을 쓰고 있는지 확인해야 한다.

P(mutex)를 호출해서 readcount에 접근한다. 그리고 readcount 값을 1 증가시킨다. 그때 readcount값이 1이라면 본인이 처음 들어온 Reader라는 뜻이므로 P(db)를 호출해서 Reader가 있다는 것을 Writer에게 알린다.

만약 readcount가 2 이상이라면 이미 들어간 독자가 1명 이상 존재한다는 뜻이므로 굳이 P(db)를 호출할 필요는 없다.

그리고 readcount에 대한 접근이 끝나면 V(mutex)를 호출해서 다른 Reader들도 들어올 수 있도록 한다.

또한 DB에 접근하고 나서는 P(mutex)를 호출해서 다시 readcount에 대한 접근 권한을 얻는다. readcount 값을 1 감소시키고 그때의 readcount 값이 0이라면 이제 안에는 더 이상 Reader가 없다는 의미이므로 본인이 마지막 Reader가 된다. 따라서 V(db)를 호출하여 Writer가 DB에 접근할 수 있도록 해준다.

 

P(mutex), V(mutex)를 통해 readcount에 대한 접근을 동기화 하지 않으면 어떤 일이 발생할까?

Reader 두 명이 동시에 readcount에 접근해서 값을 증가시키면 readcount가 2가 된다.
그러면 readcount가 2이기 때문에 아무도 P(db)를 호출하지 않고 그냥 들어가버리는 상황이 발생한다.

또는 내가 readcount를 증가시키는 동안 다른 Reader가 readcount를 감소시켜서 잘못된 readcount 값을 읽을 수도 있다.

 

Dining-Philosophers Problem

재밌는 문제가 하나 있다. 원탁에 철학자들이 둘러 앉아있고 앞에 접시가 하나씩 놓여 있다.

그리고 젓가락은 철학자들 사이사이에 하나씩만 놓여 있다.
철학자들은 생각하다가 (철학자니까 하루종일 생각만 하나봄,,,) 배가 고프면 양쪽에 있는 젓가락을 하나씩 들어서 두 젓가락을 모두 확보하면 밥을 먹는다. 그리고 밥을 다 먹으면 양쪽에 다시 젓가락을 내려놓고 다시 생각 모드로 들어간다.

여기서 사이에 놓여있는 젓가락은 젓가락 양쪽의 두 철학자 사이의 공유 변수라고 생각할 수 있다.

=> 두 철학자가 동시에 젓가락을 드는 것을 막아야 한다. 즉, 젓가락을 드는 행위가 동기화가 되어야 한다.

젓가락을 들기 전에 다른 철학자가 젓가락을 들고 있나 확인하는 과정이 필요

젓가락 자체를 세마포어 변수로 두고 들기 전 P를 호출하고 다 사용하고 나면 V를 호출해서 다른 철학자가 사용할 수 있도록 해준다.

양쪽 젓가락을 모두 들어야 밥을 먹을 수 있기 때문에 P(chopstick[i]), P(chopstick[i+1])을 호출해서 둘 다 탈출하면 밥을 먹기 시작한다.

이러한 방법은 Deadlock을 유발하기에 해결책이 될 수 없다.
모든 철학자가 동시에 배가 고파서 동시에 자신의 왼쪽 젓가락을 들었다고 하자. 그럼 P(chopstick[i])는 모두 통과할 것이다. 그런데 모두 젓가락을 한 쪽씩 들고있기 때문에 전부 P(chopstick[(i+1)%5]에 걸리게 된다.
=> 아무도 밥을 못 먹고 대기만 하게 된다.

모두가 왼쪽 젓가락만 가지고 있다면 모두가 자기의 오른쪽 사람을 기다리는 상황이 발생한다. 

=> 이렇게 공유 자원에 대해 원형 대기가 이루어지는 상황을 Deadlock이라고 함.

 

Deadlock & Startvation

Deadlock은 교착상태로 둘 이상의 프로세스가 무한 대기를 하고 있는데,

이러한 무한 대기가 현재 무한 대기를 하고 있는 프로세스에 의해서만 깨질 수 있는 상황.

=> 즉, 무한 대기가 풀릴 수 없는 상태이다.

 

이러한 현상은 Startvation 현상과 유사하다.

예를 들어, Block/Wakeup Semaphore에서 Sleep된 프로세스들은 List에 매달아둔다고 했는데, wakeup이 발생했을 때 제일 늦게 들어온 프로세스를 깨우게 되면(Last In First Out) 새로운 프로세스가 계속 들어오면 처음 들어온 프로세스는 깨어나지 못하게 된다.

Startvation 상황은 그래도 진도를 못 나가는 것은 아니지만, 특정 프로세스의 희생으로 진도가 나가고 있는 것이고

Deadlock은 모든 프로세스가 진도를 나가지 못하고 대기하는 상황

 

Remedies of Deadlock (해결책)

앞의 식사하는 철학자 예에서 Deadlock을 해결하는 방법은 어떤 것들이 있을까?

1. 양쪽에 있는 젓가락을 하나씩 드니까 Deadlock이 발생했다.

두 젓가락을 묶어서 둘 다 들 수 있으면 들고, 아니면 둘 다 내려놓는다. (All or Nothing)

 

2. 홀수번째 앉은 철학자는 왼쪽을 먼저 들고나서 오른쪽을 들게 만든다.

반대로 짝수번째에 앉은 철학자는 오른쪽을 먼저 들고나서 왼쪽을 들게 만든다.

 

3. 가장 간단한 방법으로 최대 4명의 철학자만 식탁에 앉히자.

젓가락은 5갠데 사람은 4명이므로 Deadlock이 발생할 수가 없다.

 

Problems of Semaphore

앞의 Problem들을 Semaphore를 이용해서 해결했었는데 세마포어를 사용하는 것의 여러 단점들이 있다.

1. 세마포어를 사용하면 코딩하기가 어렵다.
2. 그리고 코딩을 했다고 하더라도, 올바르다는 것을 증명하기가 매우 어렵다.
두 프로세스가 동시에 접근하는 상황이 발생해야만 버그가 발생한다.
=> 이런 상황이 항상 발생하는 것이 아니다.
=> 그렇기 때문에 디버깅이 어렵다.
3. 협업해서 코딩을 하는 경우에 내가 P를 호출할테니 너가 V를 호출해 이런 협의를 보고 코딩하는 것이 어렵다.
4. 한 번 잘못 사용하면 전체 시스템이 마비된다.
=> 이론적으로는 가능하지만 정확하게 사용해서 프로그래밍 하기가 어렵다.

 

Monitors

우리가 동기화 문제를 해결할 수 있는 또 다른 방법은 High-level language에서 제공하는 동기화 툴인 Monitor를 사용하는 방법이다.

모니터는 C또는 java의 Class와 굉장히 유사하다.

공유 변수에 해당하는 private data가 있고 private data에 접근은 public methods를 통해서 한다.

근데 이게 어떻게 동기화 문제를 해결한다는 거지?

모니터가 어떤 기능을 제공하길래 동기화 문제를 해결할 수 있을까.
모니터 안에서 활성화 되어 동작하는 프로세스는 하나 밖에 없다는 것을 보장한다.
=> public methods를 호출해서 실행하는 프로세스는 하나 밖에 없음을 보장한다는 뜻. 여러 프로세스가 public methods를 동시에 호출하는 경우에는 어떻게 되냐? 그것을 막아주겠다는 것임.
어떻게?
entry queue를 제공해서 누군가가 public methods를 실행하는 도중에 다른 프로세스가 public methods를 호출하게 되면 entry queue에 매달리게 된다. 그리고 active한 프로세스가 더 이상 존재하지 않으면 큐에서 대기하고 있던 프로세스 하나를 모니터로 넣어서 public methods를 실행할 수 있도록 해준다.

=> private data에 대해서 한 프로세스만 접근할 수 있다는 것을 보장해준다.

 

모니터를 가지고 동기화 문제를 해결하려고 디자인을 하다보면 한 가지 문제가 발생하는 경우가 있다.

모니터 내부의 public method를 호출해서 일을 하던 프로세스가 method안에서 코드를 실행하는 도중에 조건이 만족되지 않아서 더 이상 코드를 수행하지 못하는 경우가 발생했다. 그런데 그 조건이 만족되도록 해주는 프로세스는 자신이 아니라 다른 프로세스라면? Bounded buffer problem에서 consume하는 public method를 만들었다고 치자. 이때 컨슈머는 full buf가 0이면 wait를 해야 한다. 컨슈머는 CPU를 쓰면서 busy waiting을 하고 있다. 그런데 모니터는 다른 프로세스가 진입하는 것을 막는다. full buf를 1 증가시켜 주는 것은 프로듀서인데, 컨슈머 프로세스가 consume을 호출해서 active하게 동작하고 있기 때문에 프로듀서가 produce 메소드를 수행할 수가 없음.

=> 이런 일이 발생해서는 안 됨.
=> 그래서 모니터는 특별한 기능을 제공한다. 모니터 외부가 아닌 내부에서 대기할 수 있는 방법을 제공한다. busy waiting 하지 않고 sleep을 하도록 만듦. sleep을 하게 되면 더 이상 active한 프로세스가 아니기 때문에 새로운 프로세스가 모니터 안으로 들어올 수 있게 된다.

모니터 내부에서 조건 변수를 선언하게 되면 그 변수에서 기다리는 방법과 깨어나는 방법을 제공.
x.wait()를 호출하면, 아 나는 조건을 만족하지 못하기 때문에 x에서 sleep하면서 기다리겠다는 뜻.
entry queue에 있던 프로세스가 들어와서 x 조건을 만족시켜 주게 되면 x에서 잠들어 있는 프로세스를 깨워줘야 한다. 그래서 x.signal()을 호출해서 해당 프로세스를 깨워준다.

조건을 만족하지 못해 더 이상 코드를 수행할 수 없는 프로세스들은 wait를 호출하고 condition 변수 내에서 대기한다.

그러면 모니터는 entry queue에서 새로운 프로세스를 모니터 안으로 들어오게 해서 public method를 수행하도록 한다. 그러다 특정 조건이 만족되어 대기하고 있는 프로세스가 깨어날 조건이 되면, signal을 통해 깨운다. 

모니터를 이용해서 어떻게 "식사하는 철학자 문제"를 해결할까??

젓가락을 한 쪽씩 들어서 Deadlock 상황이 발생되었으므로 굳이 왼쪽, 오른쪽 젓가락으로 나누지 않고 묶어서 State로 표현한다. hungry면 먹고자 하는 의지가 있는 상태, thinking은 식사를 하고 있지 않은 상태, eating은 식사를 하고 있는 상태. 즉, eating이면 양쪽 젓가락을 다 들고 있다고 생각하면 된다.

이러한 State가 공유변수가 되는 셈이다.

또한 먹고자 하는 의지는 있지만 양 옆 사람 중 한 명 이상이 이미 먹고 있어서 먹지 못하는 상황에는 기다릴 수 있도록 self라는 조건 변수를 선언한다.

State라는 공유변수는 init, pickup, putdown, test 라는 public methods를 이용해서 접근할 수 있다. 그러나 init은 초기화용이고 test는 pickup, putdown 내부에서 호출되는 함수이므로 실질적으로 호출할 수 있는 methods는 pickup과 putdown이다.

철학자가 밥을 먹으려고 시도하는 경우 pickup을 호출한다. pickup에서는 state를 hungry로 바꾸고, 현재 양 옆에 있는 철학자 중 아무도 밥을 먹고 있는 사람이 없는지 확인하기 위해 test를 호출한다.

그리고 양 옆 모두 밥을 먹고 있지 않은 경우엔 밥을 먹을 수 있다는 뜻이므로 state를 eating으로 변경한다. 그리고 signal을 보내서 i를 깨워준다.

그런데 사실 pickup에서 test를 호출하는 경우에는 i가 직접 test를 호출하는 것이기 때문에 i는 깨어있는 상태이다. 그래서 signal을 보내도 아무런 일도 일어나지 않는다.

하지만 test method는 putdown에서도 호출되기 때문에 signal을 보내는 코드를 넣은 것이다.

만약 별도의 test 함수를 만들지 않고 pickup과 putdown 내부에 코드를 작성했다면 pickup 내부에는 signal을 보내는 부분을 작성하지 않아도 됐을 것!

 

putdown 함수는 이제 나는 밥을 다 먹었으니 젓가락을 내려놓고 state를 thinking 상태로 바꾼다. 그리고 나로 인해 밥을 먹지 못하고 기다리고 있는 사람이 있을 수 있으므로 양 옆사람에 대해 test 함수를 호출해준다.

조건이 만족되면 signal을 통해 해당 사람을 깨울 것이다.

 

그럼 여기서 의문. putdown 함수에서 test를 호출해서 다른 사람이 깨게 되면 active한 프로세스가 2개가 되는 것이 아닌가?

깨어난 프로세스는 아무것도 하지 않고 pickup을 바로 나간다. 그리고 eat()를 수행한다. 그렇기 때문에 active한 프로세스는 여전히 나 하나 뿐이다. 만약 그 깨어난 프로세스가 public method를 호출하려고 하면 내가 active하기 때문에 entry queue에 매달리게 될 것.

wait() 코드를 method의 가장 마지막에 작성한 이유도 이러한 이유 때문이다. 꼭 wait() 코드가 method의 마지막 부분이어야 하는 것은 아니지만 깨어난 프로세스가 공유 변수에 접근하는 일은 없어야 한다.

=> 모니터는 동기화 문제를 해결할 수 있는 도구를 제공하는 것이지 동기화 문제를 해결해주는 것은 아님. 해결은 개발자가 하는 것이다.

 

이렇게 해서 모니터를 이용해서 Dining philosoper Problem을 해결했다.

처음에 모니터만 머리를 잘 써서 코딩해 놓으면 나중에는 pickup과 putdown을 호출하는 것만으로 동기화 문제를 해결할 수 있게 된다. 

 

이처럼 Programming Language 차원에서 동기화 툴을 제공해주면 문제를 훨씬 더 쉽게 해결할 수 있다. 코드 내에 어떠한 세마포어 변수도 사용하지 않았는데 동기화 문제가 해결이 되었다.

=> 프로그래머 입장에서 훨씬 편하다.

 

Monitor Implementation

모니터에서 signal이 발생하면 모니터 내부에 wait를 호출하고 잠들어 있는 프로세스 중 하나를 깨워야 하는데, 특정 프로세스를 지정해서 깨우고 싶다면 어떻게 해야 할까?

1. wait 호출시에 우선 순위를 나타내는 integer값 C를 전달하는 방법이 있다. 그러면 나중에 signal이 발생하면 이 우선 순위 값이 제일 작은 프로세스를 깨우게 된다.

2. 앞에서의 식사하는 철학자 문제 해결법 처럼, 프로세스마다 대기하는 공간(조건 변수)을 별도로 마련해서 해당 프로세스를 깨운다.

 

동기화 문제를 해결하기 위해 모니터를 사용할 때 2가지 조건만 만족되면 올바른 해결책이라는 것이 증명이 되어 있다.
그럼 이 2가지 조건은 뭘까?

1. function을 올바른 순서로 호출하도록 해라.
앞의 예에서는 pickup을 먼저 호출하고 putdown을 호출해야 한다. putdown을 먼저 호출하는 일이 없도록 프로그래머는 코딩을 해야 한다.

2. 모니터의 private 변수들에 대한 접근을 public method를 통해서만 접근하도록 해라. 즉, 직접 접근하지 못하도록 해라.

모니터는 객체 지향 language가 아니기 때문에 private 변수에 대한 직접적인 접근을 막아주지 않는다.

세마포어 변수에 대한 접근을 P,V로만 해야 하는 것과 같은 제약.

 

※본 내용은 한양대학교 강수용 교수님의 강의를 참고해서 작성되었습니다.