Deadlock and Starvation | 세마포어는 원치않는 문제가 생길 수 있다.

---

Deadlock 문제

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

세마포어 S와 Q가 두개 있는데, 두개를 다 획득해야지만 일을 할 수 있는 환경이라 치자.(예를들어 하드디스크 A에 있는걸 B로 카피하고 싶다면, A라는 하드디스크와 B라는 하드디스크를 두개 다 보유하고 있어야 함.)
S와 Q가 배타적으로 프로세스 1개만 쓸 수 있는 세마포어라고 하면 문제가 생길 수 있다.

S라는 세마포어를 P0가 먼저 획득, P1은 Q라는 세마포어를 획득할 수 있다. P0이 CPU를 뺏겨서 P1이 CPU를 얻는다면?
그리고 P1이 S를 획득하려고 봤더니, S는 이미 P0가 가지고 있기 때문에 획득을 못하고 기다리고 있어야 한다. 영원히..... ~
S를 획득할려면 P0이 S를 내놔야 하는데, P0는 Q까지 획득하고 나중에 반환할 때 S를 내놓기 때문에. 결국 둘다 상대방의 것을 기다리고 있다. 이러한 상태를 데드락이라고 한다.

• 해결 방법
  자원 획득 순서를 똑같이 맞춰주면 된다.
  

Q를 획들할려면 S먼저 얻고 Q를 획득해라. 그러면 P0에서 CPU를 빼앗겼을 때 P1에서 S를 얻지 못하고 기다리게 된다.
이런 경우는 프로그래머가 유의해서 작성해야 한다.

Starvation 문제

• indefinite blocking
• 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
• 무한히 자원을 기다림

Classical Problems of Synchronization

• Bounded-Buffer Problem (Producer-Consumer Problem)
• Readers and Writers Problem
• Dining-Philosophers Problem

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

버퍼의 크기가 유한한 문제 (생산자 소비자 문제 )

---

프로세스가 두가지 종류가 있다. Producer, Consumer 프로세스
하나씩만 있는게 아니라 프로듀서 여러개, 컨슈머 여러개 있는 상황이다.

이런 상황에서 프로듀서는 공유 버퍼에 데이터를 하나 만들어서 집어넣는 역할을 한다.

주황색 표시 - 생산자가 데이터를 만들어서 집어 넣은 상태
구멍 뚫린 표시 - 비어있었던 것 또는 생산자가 데이터 집어넣었는데 컨슈머가 데이터 꺼내가서 비어있는 것.

여기서 synchronization과 관련해서 어떤 문제가 생길수 있을까?

1. 공유 버퍼이기 때문에 생산자가 둘이 동시에 도착해서 비어있는 버퍼를 둘이서 데이터를 집어 넣으면 문제가 생긴다.
   → 그냥 하는게 아니라 락을 걸어서 다른 프로세스의 접근을 막은 다음에 데이터를 집어 넣고, 락을 풀어서 다른 생산자나 소비자가 공유 버퍼를 접근할 수 있게 해야 한다.
2. 소비자도 마찬가지로 소비자가 둘이서 동시에 데이터를 꺼내가려고 하면 문제가 생긴다.
   → 그래서 소비자가 데이터 꺼내기 전에 버퍼에 락 걸고 데이터 꺼내고 락 푼다.

Bounded buffer이기 때문에 생기는 문제?

1. 만약 버퍼가 다 찬 상황에서 생산자가 또 도착해서 데이터를 만들어 집어 넣으려고 한다면 버퍼는 이미 다 찼기 때문에 생산자는 사용할 수 있는 자원이 없는 상태이다.
   소비자가 나타나서 내용을 꺼내가야지만 빈 버퍼가 생기고, 데이터를 넣을 수 있다.
   생산자 입장에서의 자원은 비어있는 버퍼이다.
2. 소비자 입장에서는 데이터가 없다면 꺼내갈 게 없다.
   소비자 입장에서 자원내용이 들어있는 버퍼이다. 생산자 프로세스가 내용을 만들어서 집어넣어줄 때까지 기다려야 한다.

세마포어를 사용해서 할 업무

1. 공유 버퍼 전체에 락을 걸어서 혼자 배타적으로 접근 가능하게 하고, 접근 끝나면 락을 해제해야함
2. 버퍼가 가득 차거나 비었을 때 가용 자원의 갯수를 세는 카운팅 용으로 세마포어 변수가 필요하다.

Shared data 공유데이터

• buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치 포인터 변수)

Synchronization variables

• mutual exclusion (락 걸고 푸는 용) → Need binary semaphore (shared data의 mutual exclusion을 위해)
• resource count (자원 카운트) → Need integer semaphore (남은 full/empty buffer의 수 표시)

세마포어를 이용한 슈도코드

semaphore full = 0 (내용 들어있는 버퍼 세는 변수)
empty = n (비어있는 버퍼 세는 변수)
mutex = 1 (락 거는 용)

<생산자>
item x를 만들고 빈 버퍼가 있나 확인 P(empty) 빈 버퍼가 있다면 획득함
그 후 버퍼에 데이터를 집어넣기 위해 버퍼전체에 락을 검 P(empty)
버퍼에 데이터를 집어 넣은 후 버퍼에 걸었던 락을 품 V(mutex)
그 후 내용 있는 버퍼의 수 하나 늘림 V(full)

<소비자>
내용이 들어있는 버퍼가 있는지 확인 P(full) 있다면 획득, 없다면 기다려야함
그 후 락을 걸고 P(mutex) 공유 버퍼에서 데이터를 하나 꺼낸 후 락을 품 V(mutex) 그 후 비어있는 버퍼의 수 하나 늘림 V(empty)

2. Readers and Writers Problem

---

프로세스가 두 종류이다. 읽는 프로세스, 쓰는 프로세스

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안된다
• read는 동시에 여럿이 해도 된다.
• solution
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
  • Writer는 대기중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

Shared data 공유데이터

• DB 자체
• readcount; → 현재 DB에 접근중인 Reader의 수

Synchronization variables

• mutex → 공유 변수 readcount를 접근하는 코드 (critical section)의 mutal exclusion 보장을 위해 사용
• db → Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

세마포어를 이용한 슈도코드

Writer
P(db) 락을 걸고 DB에 쓰는 작업을 함 그 후 V(db)락을 풀어줌

Reader
읽는 작업은 여럿이 동시에 해도 된다.
여럿이 동시에 해도 되는데 락을 거는 이유는 Writer가 못쓰게 하기 위해서이다.

readcount++ 한다. Reader가 몇개가 읽고 있는지 체크. 내가 최초의 Reader면 if(readcount==1) DB에 락을 걸고 P(db), 최초가 아니면 넘어간다.
readcount도 공유 변수이기 때문에 동시에 접근하면 문제가 생길 수 있다. 그래서 이러한 readcount를 위한 락이 P(mutex)

그 후 DB를 읽는다. 내가 마지막으로 읽는 Reader 프로세스라면 DB에 건 락을 풀어줘야 한다. Writer가 기다리고 있기 때문에 V(db)

이때도 readcount를 건들이기 때문에 P(mutex), V(mutex)를 readcount 전 후로 해줘야 한다.

Starvation이 생길 수 있다

• 리더들이 다 빠져나가서 마지막으로 빠져나가는 리더가 락을 풀때까지 라이터는 기다려야 한다.
  리더들이 100개 도착해서 읽고있는 동안 라이터는 기다리는데, 리더 99 개에서 새로운 리더들이 또 도착한다면 라이터는 기다려야함.
• Starvation 해결 하는 방법 ?
  • queue에 우선순위를 둬서 writer가 일정시간 이상 기다리지 않게 해줄 수 있다.

3. Dining-Philosophers Problem

식사하는 철학자 문제

---

다섯명의 철학자 두가지 업무
1. 생각 2. 밥먹기
밥먹기 위해선 젓가락 두개를 잡아야함.

세마포어를 이용한 슈도코드

왼쪽 젓가락을 잡고 싶은데 옆에 있는 철학자가 밥을 먹고있다면 그 젓가락을 쓰지 못함. 여기서 젓가락은 공유 자원인 것.

양쪽 젓가락을 잡았으면 밥을 먹고, 다 먹었으면 젓가락을 놓음.

위 솔루션의 문제점

• Deadlock 가능성이 있다.
• 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

해결방안

1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. (밥을 먹는 철학자만 앉게 함)
2. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

semaphore self[3]==1 이면 3번 철학자가 젓가락 두개 다 잡을 수 있는 권한이 있는것, 0 이면 젓가락 두개 다 잡을 수 없는 상태

철학자 i가 젓가락을 잡는 함수를 호출하면
락을 걸고 P(mutex) 자신의 상태를 헝그리로 바꾸고,
test함수로 젓가락 두개를 다 잡을 수 있는지 체크한다.
왼쪽 철학자도 밥먹고 있지 않고, 오른쪽 철학자도 밥먹고 있지 않고, 내가 배가 고픈 상태이면 철학자의 상태를 밥먹는 상태로 바꾸고,
V(self[i])로 권한을 준다. 0→1
그 후 테스트가 끝나면 P(slif[i])를 통해 1→0으로 바꾼다.

만약 test 연산중에 젓가락 두개를 다 잡을 수 없는 상태이면 권한을 얻지 못하고 테스트 함수가 끝나게 된다. 그 경우에는 P연산을 할 때 self[i]가 1이 될때까지 기다려야 한다. 인접한 철학자가 젓가락을 내려놓았을 때까지.

젓가락 두개 다 잡았으면 밥을 먹고, 젓가락 내려놓을 때는
왼쪽과 오른쪽에 대한 테스트를 해준다.

3. 비대칭
   • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Monitor

세마포어와 모니터는 프로세스 싱크로나이제이션 문제를 프로그래머 입장에서 어떻게하면 더 쉽게 할수 있는가를 제공해주는 것.

세마포어를 사용할 때 불편한 점이 있다. 그래서 모니터를 제공해서 더 편하게 할 수 있다.

세마포어의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한번의 실수가 모든 시스템에 치명적 영향을 미친다.

만약 개발자가 실수를 하면 세마포어로 문제를 제대로 해결못할 수 있다.

모니터는 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

추상적인 구조체 형태. 객체지향 프로그래밍 쪽에서 모니터를 지원해준다. 프로그래밍 언어마다 구현 형태는 다르다.

공유데이터에 접근할 때 모니터라는 정의된 내부의 프로시저를 통해서만 접근 할 수 있다.

모니터가 원천적으로 모니터 내부의 프로시저는 동시에 여러개가 실행이 안되도록 통제를 하는 권한이 부여된다.

프로그래머 입장에서 락을 걸 필요가 없어진다. 나머지 프로세스들은 줄서서 기다린다. 줄서있는 프로세스는 안에 active한 프로세스가 0이 될때, (지금 모니터를 쓰고있던 프로세스가 cpu를 얻어서 다쓰고 나가던지, 이 프로세스가 내부에서 뭔가 충족되지 않아서 잠들 경우) 기다리던 프로세스가 들어와서 코드를 실행할 수 있게 된다.

어떤 조건이 해당이 안돼서 잠들게 했는지에 따라 조건을 변수로 둔다. (condition variable) 이는 세마포어에서 처럼 어떤값을 가지는 변수가 아니라 어떤 프로세스를 잠들게 하고, 줄세우기 위한 변수이다.

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음

• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

  • condition x,y;
    세마포어 변수와 비슷한 역할. 자원의 여분이 있으면 바로 접근하게 해줌

• Condition variable은 wait와 signal 연산에 의해서만 접근 가능

  • x.wait();
    x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
    
  • x.signal();
    x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

생산자 소비자 문제를 모니터로

Bounded-Buffer Problem (Producer-Consumer Problem)

위 : 세마포어
아래 : 모니터

모니터에선 락을 걸거나 푸는 코드가 없다. 공유 버퍼가 모니터 안에 정의된다.
생산자든 소비자든 하나의 프로세스가 모니터 안에서 활성화되기 때문에 락을 걸지 않아도 동시에 접근 하는 문제를 고려할 필요가 없다.

생산자 입장에서는 비어있는 버퍼가 필요한데, 비어있는 버퍼가 없다면 wait()기다리게 하고, 비어있는 버퍼가 있다면 데이터 추가함.
그리고 소비자에게 signal. 소비자는 그 반대

모니터 안에서 하나의 프로세스만 활성화되기 때문에 나머지 프로세스는 기다린다.

식사하는 철학자 문제를 모니터로

Dining-Philosophers Problem

각각의 철학자들은 밥을 먹기 위해서는 양쪽에 있는 젓가락을 잡아야하고 pickup() 밥을 다 먹고나면 젓가락을 놔야함 putdown()

젓가락을 잡는 부분에서 상태를 state[i] = hungry state는 공유 데이터임.

test(i)로 젓가락을 두개 다 잡을 수 있는지 테스트.
왼, 오 철학자가 밥을 먹지 않고 있고 , 내가 배고픈 상태를 만족하면 철학자의 상태를 eating으로 만들어준다.
self[i].signal() 철학자 i가 잠들어 있다면, signal로 꺠워줌. 조건을 만족 못했으면 self[i].wait()으로 잠들게 된다.

젓가락을 잡고 다 밥을 먹었으면 putdown으로 젓가락 내려놓음.
그리고 인접 철학자를 깨워줌 왼쪽에 대한 테스트, 오른쪽에 대한 테스트로 들어가서 또 test 코드가 진행된다.

세마포어 코드와 거의 비슷함.