📌 Process Synchronization 3

📖 01. Classical Problems of Synchronization

📖 02. Bounded-Buffer Problem

• Buffer : 임시로 데이터를 저장하는 공간

• Bounded-Buffer : 버퍼의 크기가 유한하다
  -> sircular 형태 (생산자 소비자 문제)

• Producer : 데이터를 만들어서 집어넣는 역할

• 생산자 2개가 비어있는 버퍼에 동시에 데이터를 넣을 때 synchronization문제가 발생한다.

• 소비자도 마찬가지로 데이터를 같이 꺼내가면 문제가 생긴다.
  -> 버퍼에 락을 걸어서 꺼내가고 락을 푸는 과정이 필요하다.

• Bounded-Buffer이기 때문에 생기는 문제점:
  -> 데이터가 꽉 찬 상태에서 생산자가 도착하는 경우
  -> 생산자는 비어있는 데이터의 수를 유지해야 하며 0개일 경우 대기해야하는 상황이 된다.
  -> 소비자가 빼가야만 한다.

• 데이터가 비어있는 상태에서 소비자가 도착하는경우 문제점이 발생한다.
  -> 소비자 입장에서는 자원이 내용이 들어있는 데이터이다.
  -> 생산자가 데이터를 만들어 줄 때까지 기다려야 한다.

• semaphores 변수가 2개 필요하다.

1. lock을 위한 변수
2. 데이터 개수를 유지하기 위한 변수

• shared data에 접근하려면 lock을 걸고 푸는 과정을 거쳐야 한다.
  -> semaphores변수를 통해 lock을 걸고 풀 수 있다.

• 자원의 개수를 카운팅하는 변수로 semaphores변수가 필요하다.

• <Semaphore 변수의 이용을 수도코드로 나타냄>

• lock을 걸기 위한 변수 : mutex = 1

• 데이터가 들어있는 개수를 세기위한 변수 : full

• 비어있는 데이터를 세기위한 변수 : empty

• 생산자 순서

1. 데이터를 만든다
2. 빈 공간이 있는지 확인한다.
   -> 빈 buffer을 획득하는 과정
3. P연산을 통해 lock을 건다.
4. 데이터를 넣는다.
5. V연산을 통해 lock을 푼다.
6. V(full) : 담겨있는 데이터 증가시키기

• 소비자는 생산자의 반대이다.

1. 내용이 들어있는 buffer를 하나 획득한다.
2. buffer 전체에 lock을 건다.
3. 공유 buffer에서 데이터를 하나 꺼내간다.
4. 버퍼조작이 끝나면 lock을 푼다.
5. 비어있는 버퍼의 개수를 하나 증가시킨다.
6. V(empty) : Producer에서 P(empty)로 기다리지 않고 buffer을 획득할 수 있게 해주자.

• 생산자 소비자 문제를 semaphores를 통해 해결하는 방식이다.

📖 03. Readers-Writers Problem

• 2가지의 process가 존재한다. 1개씩 존재하는 것이 아니라 여러개의 reader와 Writer가 존재한다.

• 공유 데이터가 존재하며 DB라고 부른다.

• 어떤 문제가 발생할까?
  -> 공유데이터인 DB를 여러 프로세스가 동시에 접근하면 안된다.
  -> lock을 걸어서 하나의 프로세스만 접근이 가능하도록 해야한다.
  -> 쓰는 작업은 문제가 생기지만 읽는 것은 synchoronization문제가 발생하지 않는다.

• Readers-Writers Problem에서 풀어야 할 문제
  -> 쓸 때는 lock을 걸어야 하지만 읽을 때는 lock을 하지 않아야 한다는 문제를 해결해야 한다.
  -> 누군가가 읽고 있을 때 Reader가 도착하면 '너도 읽어라' 허용해주어야 하고 누군가가 읽고 있는데 Writer가 도착하면 대기 해야한다.
  -> Writer는 아무도 없을 때만 쓸 수 있다.

• 이러한 문제를 해결하는 방법
  

< Writer >

• semaphores P(db)연산을 통해 lock을 걸어야 한다.
  -> 누군가가 이용하고 있다면 대기하고 있는 상태일 것이다.

• Reader도 쉽게 만들려면 Writer의 코드와 똑같이 짜면된다.
  -> 이렇게 하면 비효율적이다. (읽는 작업은 동시에 해도 되기 때문이다.)
  -> 읽을 때도 lock을 걸긴 해야한다. (Writer가 도착했을 때 들어올 수 없게 해야하기 때문이다.)
  -> 읽는 작업은 할 수 있게 해야한다.

< Reader >

• readcount : 공유데이터 (Reader가 지금 몇명이 읽고 있는지 나타내는 변수)
  -> 모든 reader들이 접근할 수 있는 변수
  

• if(readcount == 1) : 내가 처음 들어왔다면 db에다가 lock을 건다
  -> reader가 더 들어왔다면 readcount가 1보다 더 크기 때문에 lock을 걸 필요가 없다.

• readcount를 막 증가시키다보면 두개 증가시켰는데도 하나만 증가될 경우가 존재하는 문제가 생길 것이다.
  -> 이 공유 데이터에 대해서도 lock을 걸 필요가 있다.
  -> 이 공유데이터를 lock시키는 변수가 mutex semaphores 변수이다.

• readcount--;, if (readcount == 0) : readcount를 감소시켰는데 만약 내가 마지막으로 나가는 것이라면 db의 lock을 풀어줘야 한다.
  -> 여기서도 readcount라는 공유변수에 접근하기 때문에 lock을 걸고 푸는 코드가 필요하다.

• Reader의 마지막이 빠져나가야만 Writer는 작업을 진행 할 수 있다.
  -> 그러나 Reader가 계속 도착하게 되면 Writer는 일을 하지 못하고 starvation이 발생할 수 있다.

• Writer나 Reader가 순서대로 처리 할 수 있도록 한다고 하면 Writer뒤에 오는 Reader들은 같이 읽을 수 있는 상황임에도 불구하고 기다려야 하는 상황이 생긴다.
  -> Queue 우선순위를 두는 방법으로 해결 가능하다.

📖 04. Dining-Philosophers Problem

• 생각하거나 밥먹거나 두가지의 일을 할 수 있다.
  -> 배고파지만 자신의 왼쪽과 오른쪽 젓가락이르 집어서 밥을 먹는다.
  -> 배가 부르면 젓가락을 놓고 밥을 먹는다.
  -> 이런일을 무한 반복한다.

• 다음과 같은 solution은 Deadlock 문제점이 발생할 수 있다.
  -> 더이상 아무것도 못하고 막혀있는 상황

• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다는 코드

-> 이 코드가 semaphores에 잘 맞춰진 코드는 아니다.
-> 잘 동작하는지만 파악하자.

• 먹거나 생각하거나 두 가지 일을 한다.

• 젓가락을 들거나 내려놓는 함수가 존재한다.

• semaphore self[5] = 0 : 젓가락을 들을 수 있는 권한
  -> ex) semaphore self[1] = 0 : 1번 철학자는 젓가락을 들을 수 있는 권한이 없다.
  -> semaphore self[3] = 1 : 3번 철학자는 젓가락 두개를 모두 집을 권한이 있다.

• enum{thinking, hungry, eating} state[5] : 철학자의 상태를 나타내는 공유 변수

< pickup(int i) >

• state 공유데이터에 접근하기 때문에 P(mutex)로 lock을 건다.
  -> state[i] = hungry : 본인의 상태를 hungry로 바꾸어 놓고
  -> test[i] : 철학자i가 젓가락을 모두 들을 수있는 상태인지 확인한다.

< test (int i) >

• 왼쪽, 오른쪽 철학자가 밥을 먹고 있지 않고 그리고 본인이 배고프면 i철학자의 상태를 eating을 만들고
  -> V(self[i]) : 젓가락을 잡을 수 있는 권한을 준다.

• 원래 semaphore변수는 자원의 개수를 초깃값으로 하고 자원의 개수가 1이거나 1이상인값을 주어야 한다.
  -> 그러나 이 코드에서 이상한 점은 semaphore 변수 self[]는 0을 초기값으로 하고 test하는 과정에서 주변 철학자들이 밥을 먹지 않고 내가 배고프면 젓가락을 집을 수 있는 권한을 준다.
  -> V연산은 semaphore변수를 1로 만들어주는 것이기 때문이다.

< pickup(int i) >

• V(mutex) 연산을 통해 lock을 풀고
  -> P(self[i])연산을 통해 변수를 0으로 만들어준다.

• 만약 test연산에서 좌,우에서 먹고있다면 if문에 접근하지 못한다.
  -> 젓가락을 집을 수 있는 권한이 없는채로(self 값이 음수가 되고 blocked상태가 된다.) pickup은 끝나게 된다.
  -> 인접한 철학자가 식사가 끝나면 기다리고 있는 철학자의 변수값을 변화시켜 젓가락을 잡을 수 있는 상태로 만들 것이다.

< putdown(int i) >

• state[i] = thinking : 상태를 바꾸고

• test : 좌우의 있는 철학자가 젓가락을 집을 수 있도록 test함수를 실행시킨다.

• 이후에 Monitor라는 것을 배우는데 이 역시 프로그래머 입장에서 synchoronization문제를 해결하기 위한 방법이다.

• semaphores는 프로그래머가 실수하게 되면 큰 문제가 생긴다.
  -> Monitor라는 것을 제공하여 프로그래머를 편하게 해준다.

📖 05. Monitor

• semaphore는 프로그래머한테 P,V연산을 통해서 비교적 쉽게 코딩을 만들어주었지만 문제가 생겼을 때 버그를 잡기가 쉽지 않다.
  -> ex) critical section에 들어가기 전에 P연산을 하고 빠져나올 때 V연산을 해야하는데 실수로 반대로 한다면 critical section에 동시에 들어가는 Mutual exclusion이 깨지게 된다.
  -> ex) P연산을 두번하면 어느 누구도 더이상 critical section에 들어갈 수 없다.(Deadlock)

• 프로그래머가 코드를 잘못 짜게되면 어디서 틀렸는지 입증이 어렵다.
  -> 그래서 synchoronization을 제공하기 위해 나온것이 Monitor!

• 프로그래밍 언어 차원에서 synchonization문제를 해결하는 high-level synchronization construct라고 말할 수 있다.

• 객체 지향 프로그래밍을 보면 객체를 중심으로 오퍼레이션들이 정의되는 것을 볼 수 있다.

• Monitor는 공유데이터를 접근하기 위해서 이 monitor라고 정의된 내부의 프로시저를 통해서만 공유데이터를 접근 할 수 있다.

• 공유데이터가 있다면 밖에서 아무나 접근 할 수 있는 것이 아니라 monitor안에서 공유데이터와 공유데이터를 접근하는 프로시저를 정의해놓고 만약에 공유데이터를 접근하겠다 하면 프로시저를 통해 접근 할 수 있도록 한다.

• 원천적으로 monitor내부에 있는 프로시저는 동시에 여러개가 실행이 안되도록 통제를 하는 권한을 준다.
  -> lock을 걸 필요없이 그냥 접근하면 된다.
  -> 나머지 process는 줄을 선다.

• 프로그래머 입장에선 뭐가 편하냐?
  -> lock을 걸 필요가 없다.
  -> semaphore는 연산(P,V)을 통해 프로그래머가 직접 코드를 적어줘야 한다. (lock을 걸어주고 풀어주고)

• Monitor는 내부에 공유데이터를 선언해놓고 이 공유데이터를 접근하기 위한 프로시저들은 Monitor 내부 함수로 정의해놓는다.

• semaphore에서 자원의 개수를 세는 것이 필요했다.
  -> Monitor에서 lock을 걸 필요는 없지만 자원이 있으면 접근 하고 없으면 접근 할 수 없도록 하는 것은 필요하다.

• semaphore와 비슷하게 자원의 개수를 유지해주는 변수가 Monitor 존재한다.
  -> 'condition' 이라는 변수!

• condition의 여분이 없어서 기다리는 경우에는 기다리는 줄에서 기다리도록 하자. (wait())

• 빠져나갈 때는 signal을 통해 기다리고 있는 process가 있으면 빠져 나갈 수 있도록 한다.

• 생산자 소비자 문제 (Monitor.ver)
  

• 공유 buffer가 내부에 정의되어 있기 때문에 생산하거나 소비하는 작업을 하기 위해선 Monitor내부 코드를 실행해야 하고 생산자든 소비자든 하나의 프로세스만 모니터안에서만 활성화 되기 때문에 굳이 락을 하지 않아도 생산자가 접근하는 동안에 또다른 생산자가 접근하여 생기는 문제에 대해서는 고려할 필요가 없다.

• 생산자 입장에서는 비어있는 buffer가 필요하다. 만약에 비어있는 버퍼가없다면 기다리는 줄에 서서 기다리게 하고 비어있는 버퍼가 있다면 데이터를 넣어주자. 끝이나면 혹시 내용이 들어있는 버퍼가 없어서 잠들어 있는 소비자 프로세스를 꺠워주는 코드이다.

• 소비자 입장에서는 내용이 들어있는 버퍼가 없다면 기다리자.
  -> 버퍼가 있다면 꺼내가자
  -> 비어있는 버퍼를 기다리고 있는 생산자 프로세스가 존재한다면 깨워주자.

• Monitor안에서 하나의 프로세스만 활성화 되기 때문에 나머지 프로세스는 기다리는 것이 있다.

• Monitor 안에서 공유자원의 개수가 없어서 기다려야 된다면 x(비어있는 버퍼가 필요),y(데이터가 들어있는 버퍼 필요)에서 각각 기다리자.
  -> 줄서 있는 프로세스를 꺠워주는 것이 signal연산이다.

[출처] 반효경 교수님 강의