컴퓨터에서의 데이터 접근

데이터를 가져와 연산 하고, 연산 결과를 다시 반환한다.
컴퓨터 구조에서 배운 방식을 떠올리면된다.

경쟁상태(Race condition)

여럿의 프로세스(CPU)가 하나의 저장장치를 공유하면, 문제가 생길수 있다.

• 같은 메모리를 공유하는 멀티 프로세서 시스템
• 공유 메모리를 사용하는 프로세스들
• 커널 내부 데이터를 접근할때

이처럼 연산 결과를 받지 못하고 선점, 인터럽트 당한다면, 예상치 못한 연산결과를 받을 수 있다.

해결방법

count++란 연산이 실행된다고 가정해보자.

1. 커널모드에서count에 1을 더하는 연산이 실행되려 한다.
2. 인터럽트 요청이 들어와 count에 1을 빼는 연산이 들어왔다.

이렇게 되면 count에 1을 빼는 연산이 추가돼 원치 않는 결과를 얻는다.
이를 막는 방법은 count에 1을 더하는 연산을 할 때, 작업 도중에 인터럽트 자체를 막아버리는 것이다.
뭔가 비효율적인데...?

---

아무튼, 문제가 있다.

위의 해결방법도 썩 깔끔해보이진 않는다.
아래와 같은 문제들을 해결하기에 좋은 방법은 뭐가있을까?

프로세스 동기화 문제 해결법의 충족 조건들

강의에선 이렇게 얘기한다

• 한 프로세스가 공유데이터를 접근하고있을때(ciritical section) 다른 모든 프로세스는 그 프로세스의 ciritical section에 접근 x
• ciritical section이 비어있다면, 접근하려할때 내주어야 한다
• 프로세스가 critical section에 들어가려고 요청했고, 요청 허용될때까지 다른 프로세스들이 ciritical section에 들어가는 횟수에 한계가 있어야함.(시간때문인가?)

음...말만 늘어놓으니 생각보다 머리에 안들어온다. 해결법들을 직접 보자!

---

프로세스 동기화 문제 해결법

Peterson's algorithm

피터슨씨가 개발한 프로세스 동기화 알고리즘이다.

1. boolean타입 flag배열을 설정.
2. turn이라는 변수도 설정
   2-1. boolean과 turn이 상대 CPU면, 무한대기한다.
3. ciritical section에 들어갔다 나와서, boolean을 false로 바꾼다.

같은 알고리즘이지만, 하드웨어적 기능을 이용한 방법도 있다.
lock을 걸어버려 아무도 못들어오게 하는것이다.

둘 다 프로세스 동기화 문제의 두가지 요건을 충족한다.(mutal exclusion, progress))
하지만 단점도 있다. 계속 while문을 돌면서 기다려야 하기때문에, 자원 낭비가 심하다.
즉, bounded waiting은 충족하지 못한다.

당연히 보완한 방법도 있겠지...?

Semaphore

보완한 방법은 아니고, 위의 test and lock 방법을 추상화 시킨 자료형
semaphore이 있다. 이걸 사용하면 코드가 더 간단해진다.
그래도 busy-waiting 문제는 해결하지 못한다.

Semaphore 파고들기

semaphore엔 사실 두가지 방식이 있다.
1. Binary semaphore(0 또는 1) : 이방식은 위에 봤던것 처럼, mutex(mutual exclusion)방식에 사용한다. lock/unlcok을 구현 할때. 즉, busy-waiting 방식이다.
2. Counting semaphore : 아래 소개할 방식이다. 여러개 프로세스를 관리하거나, block/wakeup방식을 사용할때 쓴다.

Block And Wakeup with Semaphore

semaphore의 코드를 이렇게 바꾼다.

1. value와 프로세스 가 기다릴 Queue를 정의함.
2. block()이라는 함수를 만든다. 커널이 block을 호출한 프로세스를 suspend시키고, PCB를 semaphore의 wait Queue(위에 정의한)에 넣는다
3. wakeup(arg)이라는 함수를 만든다. 여기 들어온 인자는 block된것임. 인자를 깨우고, 깨운 프로세스 의 PCB를 readyQUeue로 옮긴다.

이런 방식으로 구현된다.

1. P로 입장해서 자원획득을 시도한다.
   1-1. 자원이 음수라면, L queue(wait queue)에 대기시키고, 블락한다.
   아니라면, critical section에서 연산 진행 후 V를 호출.
2. V를 호출해서 자원을 반납한다.
   2-1. 자원 반납을 시도했을때, 0이하라면, 대기큐에서 기다리는 프로세스를 지우고, wakeup(P)를 호출한다.
   어라 왜 0이하일때 호출하지? => P에서 어떤 프로세스가 S.value--연산을 실행했으니, 다른 프로세스가 기다리고 있다는 뜻이다.
   
   

---

busy-wait VS block/wakeup

결론적으로, 당연히 후자가 좋다. 자원의 낭비 차이가 심하기 때문이다.
물론 busy-wait이 좋을때가 있지만, 일반적으론 block/wakeup을 사용한다!

...라고 했지만. Counting Semaphore에도 허점이 존재한다.
바로 Starvation(기아상태) 와 관련된 DeadLock이라는 현상이다.
어디선가 들어봤는데...음!

DeadLock이란?

1. P0과 P1은 S,Q semaphore을 필요로 하는 상태다.
2. P0이 CPU를 선점해 P(S)로 'S'자원을 획득했다.
3. 그러던 중, P1이 CPU를 선점해 P(Q)로 'Q'자원을 획득했다.
   3-1. 그 다음 P1은 P(S)로 'S'자원을 획득하려하지만, 없다. block상태로 들어간다.
4. P0이 CPU를 선점해, P(Q)로 'Q'자원을 획득하렿지만, 없다. block상태로 들어간다.
5. 짜잔, Deadlock 완성!

간단한 해결방법은, P0과 P1이 S와 Q를 획득하는 순서를 동일하게 만드는 것이다.

1. P0과 P1은 S,Q semaphore을 필요로 하는 상태다.
2. P0이 CPU를 선점해 P(S)로 'S'자원을 획득했다.
3. 그러던 중, P1이 CPU를 선점해 P(S)로 'S'자원을 획득...하지못했다. => block상태
4. P0이 CPU를 선점해, P(Q)로 'Q'자원을 획득했다.
   ...V(S),V(Q)로 반환!
5. P1도 낭낭하게 S,Q를 받아 연산 끝!
6. no more deadlock.

참고로 deadlock과 starvation은 혼동의 여지가 있다.

deadlock? starvation?

• Deadlock : 둘 이상의 프로세스가, 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는것.
• Starvation : 프로세스가 suspend된 이유에 해당하는 semaphore Queue에서 빠져나갈 수 없는 현상.

아하. 그러니까, 데드락은 절대 일어날 일이 없는 이벤트를 기다리는 것이고, 스타베이션은 CPU를 독점한 상대에게서 프로세스가 기다리는 거구나!

즉, 스타베이션은 레디상태. 데드락은 슬립상태인 것이다!

이를 쉽게 설명하기 위한 그림이 있다.ㅋㅋ

식사하는 철학자 문제!

5명의 철학자가 원형 테이블에 앉았다. 이들은 특이한 방법으로 밥을 먹는다.
양 손에 식기를 하나씩 들어야 식사를 할 수있고, 식사를 해야 식기를 내려놓는다
제일 좋은 방법은, 순서대로 두 개의 식기를 들어 식사를 하는거다. 그렇게 되면, 5명 다 먹을 수 있다.

하지만 현자 지로보 선생님의 말씀에 따르면...

그렇다. 철학자 5명이 모여버렸으니, 최소 한명은 나쁜놈이다.
이번엔 설상가상으로 두 명이 나쁜놈이라 생각해보자

(왼쪽 위부터 11시, 1시, 4시, 6시, 8시)

11시와 4시가 나쁜놈이 됐다.
이 나쁜놈들은 양보없이 자신의 양쪽 식기를 들어서 음식을 먹는다.
내려놓는가 싶더니, 다시 들어서 먹는다.
이렇게 되면 11시와 4시를 제외한 명은 밥을 먹을 수 없다
이를 startvation(기아상태)라고 한다. 비유가 적절하구만!

이번엔 5명 전부 배고픔에 미친 나머지 우측 식기를 들었다.
식기를 한짝식 갖고 있지만, 먹질 못한다. 먹질 못하니, 식기를 내려놓지 못한다.
이를 deadlock이라고 한다.

---

참고로 데드락을 위한 챕터가 따로 있으니, 나중에 더 자세히 알아보자!