[OS / 운영체제] The Readers-Writers Problem, The Dining Philosopher's Problems, Synchronization within the Kernel, POSIX Synchronization

 

The Readers-Writers Problem

Writer는 데이터를 바꾸기도 하고 읽어올 수 있는 함수이다. Mutual Exclusion 보장하지 않고 Shared Data를 건드리면 race condition이 발생하고 Debug 하기 굉장히 어렵다. Writer 들이 동시에 들어오면 안된다. Reader 들이 있는데 데이터를 읽어오기는 하지만 수정을 하지 않는다. 동시에 Shard Data에 접근을 하면 문제는 발생하지 않는다. 읽기만 하는 Reader는 여러 개가 있어도 상관이 없다. 

 

 쓰고 있는 중간에 읽어가면 이때는 문제가 발생한다. 이 상황은 위험한 상황이다. 반대의 경우 Reader가 읽어가고 있는데 Writer가 들어와서 내용을 바꾸어 버리면 이것도 문제가 발생하는 상황이다. 총 4가지의 상황이 있을 수 있다. Writer가 들어가 있으면 Writer는 못들어오고 Reader도 못들어온다. Reader가 들어가 있으면 Writer는 못들어오고 Reader는 들어올 수 있다.

 

 Synchronizer의 문제를 푸는 것은 무엇이 발생하지 않도록 하는 것인가?

A) Critical Section Problem이 가져야할 3가지 조건을 만족하기 위함이다. Entry Section과 Exit section의 적절한 조합으로 해결을 할 수 있다. 

 

 

The Readers-Writers Problem

 Writer의 행동

Writer가 들어가 있으면 writer가 들어갈 수 없다. Writer가 들어가고 나서는 아무도 들어오지 못하게 막아야 한다. 

 Reader의 행동

Writer가 없으면 Reader가 들어가 있어도 다른 Reader가 들어올 수 있다. Reader가 들어가면 Writer가 못들어오게 막아야 한다. 첫 번째 Reader의 역할이 매우 중요하다.(*******) 내 앞에 Reader가 있다는 것은 Writer가 없다는 것을 의미한다. 즉, 내 앞에 Reader가 있다는 것은 다음 Reader도 들어와도 된다는 충분조건이 된다. 내가 들어가고 나서는 Writer를 막아야 한다. 나갈 때를 생각해보자. 내가 나가면서 Critical section을 들어갈 때 lock을 걸고 나갈 때 lock을 푼다. Reader가 나올 때 lock을 푸는 것이 가능한가? 다른 Reader 가 남아있을 수 있다. 아무 Reader나 할 수 없다. 들어오는 관점에서 첫 번째 Reader는 Writer를 확인해야 한다. 다음 Reader는 확인할 필요 없다. 나갈 때도 마지막에 나가는 Reader만이 Writer를 풀어줄 수 있다. counter를 이용해서 Reader의 개수를 세주면 편하다. 

 

 

The Readers-Writers Problem

mutex 변수는 mutual exclusion을 위한 변수. wrt는 writer가 공유되지 못하기 위한 변수이다. Writer는 굉장히 단순하다. 

Reader의 경우, 들어가는 첫 번째 Reader의 행동과 나갈 때 마지막 Reader의 행동을 잘 살펴봐야 한다. if(readcount==1) 인 경우 wrt를 기다리게 확인하는 코드를 수행해야 한다. knocking과 locking을 해주는 것은 Semaphore의 wait function이다. (기억할 것!) 

wait()과 signal() 사이에 있는 것이 Critical section이고 해당 부분은 readCount라는 Shared Variable을 건드리고 있으므로 다음처럼 wait과 signal로 막아줘야 한다. wait(wrt)는 현재 Writer가 들어와있는 상황이라면 여기에서 걸리게 된다. 두 번째 Reader는 wait(mutex)에서 기다려야 한다. 첫 번째 Reader가 걸리지 않는다면 다음 Reader들이 해당 Critical section에 들어올 수 있다. 

 

 

 

The Dining Philosopher's Problems

chopstick의 타입은 Semaphore이다. boolean이 아님. deadlock이 발생할 수 있다. 모든 사람이 왼쪽 젓가락을 들고 있고 오른쪽에 있는 젓가락을 기다리는 상황.

 

Deadlock

Hold and Wait이 아까와 같은 젓가락의 상황. 이를 해결하는 방법은 둘 다 들 수 있는 경우에만 집게 해야 한다.

No preemption, 

 

 

Dining Philosopher's Solution Using Monitor

 

Thinking은 Remainder section이다. Eating은 Critical Section이다. dp.pickup(i)은 entry section을 구현한 procedure이고 putdown은 exit section을 구현한다. conditioin variable의 대상은 젓가락이 아니라 self이다. condition variable은 signa과 wait 함수를 가지고 있고 wait을 하는 순간 바로 멈추게 할 수 있다. 여기에서 condition 변수는 나 자신에 대한 wait을 사용하기 위한 변수이다. 

 

 

Dining Philosopher's Solution Using Monitor

 

  변수 선언을 하고 initialize 코드가 있다. 전부다 Thinking 상태로 바꿔주는 함수이다. pickup은 Entry section에 사용되는 함수이다. 그 상황을 Hungry state라고 할 수 있다. 이 때 좌우의 친구들이 먹고 있는지를 확인해야 한다. 먹고 있으면 내가 기다리는 condition variable에 대한 wait을 선언해야 한다. 그 test 함수를 확인해보자. 3개의 If 조건을 확인해봐야 한다. 첫 번째 if문은 왼쪽에 앉은 사람이 먹고 있으면 안된다. 그리고 자기 자신이 Hungry여야 한다. (두 번째 조건은 pickup에서는 무의미한 코드이다) 세 번째 조건은 오른쪽에 앉은 사람이 먹고 있으면 안된다. 조건을 만족했으면 내가 Eating condition을 가진다. 이후 test 아래의 if문을 통과해서 EAT 을 할 수 있다. 만약 test condition을 만족하지 않으면 pickup 함수의 if문을 TRUE로 하여 self[i].wait()을 실행하게 되면서 본인이 멈추게 된다.

  putDown 함수는 내가 이제 THINKING을 하자라고 업데이트를 한다. 내려놓으면서 내 옆에 Hungry인 친구들이 있는지 test를 해야 한다. 내가 putDown을 호출했다면 내가 먹고 있었으므로 내 옆의 사람들은 먹고 있을 수가 없다. 

 

 

Synchronization within the Kernel

 

Windows는 Multithreaded kernel이다. real-time application도 지원을 한다. CPU가 하나 있을 때 Mask Interrupt를 하면 된다. spinlock은 짧은 코드에 대해서만 사용을 해야 한다. 긴 코드에 대해서 사용을 하면 효율이 떨어진다. 누군가 Spinlock을 가지고 있으면 그 친구는 preemted 당하지 않도록 구현을 해야 한다.

 

 

Synchronization within the Kernel

 

Windows에서 Synchronize를 하려면 dispatcher object라는 말을 사용한다. Signaled State와 Nonsignaled State 라는 말을 사용한다. 들어가도 되는 상황이 Signaled State이고 Nonsignaled State는 들어갈 수 없는 상황이다. 

 

 

Synchronization within the Windows

 

spin lock과 block의 Hybrid 한 방법이다. 처음에는 Spinlock을 사용한다. 하지만 시간이 오래 걸린다면 block의 방법을 사용한다. 각각의 장점을 조합해서 사용하는 방법이다.

 

 

Synchronization in Linux Kernel

 

Atomic Set에 의해서 더하고 빼고 집어넣는다. Function에 의해서만 진행이 된다. race condition이 발생하지 않도록 수정할 수 있다.

 

Synchronization in Linux Kernel

 

 

Synchronization in Linux Kernel

 

Spinlock도 지원을 한다. spin_lock(), spin_unlock() 함수가 존재한다. Preempt_disable()은 Interrupt를 중간에 막았다 풀었다 하고 Single Processor 환경에서 사용한다. 

 

 

POSIX Synchronization

 

초기화하는 방식에는 두 가지가 있다. init 함수도 있고 전역 변수로 pthread_mutex_t mutex 선언을 할 수 있다. 사용 전에 항상 초기화를 하고 시작을 해야 한다. 

 

 

POSIX Synchronization

 

semaphore의 종류는 두 가지가 있다. named semaphore는 이름을 지정할 수 있다. 서로 다른 Semaphore간에 해당 semaphore를 사용하게 할 수 있다. sem_open으로 하나를 만들어내고 sem_wait()과 sem_post()를 사용하여 Entry와 Exit section을 구성한다. 두 번 째는 Unnamed Semaphore 함수는 sem_init()으로 초기화를 하고 sem_wait() 과 sem_post() 함수를 사용하지만 파라미터가 다르다. open으로 assign을 하는 경우 & 가 붙지 않지만 unnamed Semaphore의 경우는 & 가 붙는다.