- 프로세스는 여러개가 동시에 실행될 수 있고, I/O 요청시 CPU는 idle하지 않고 다른 프로세스의 일을 처리한다.
- 동기화를 통해서 여러개의 프로세스가 CPU를 공유하면서 데이터를 수정한다.
- 이때 수행중인 퀀텀(quantum)이 끝나면, 수정 도중에 나가야 한다.
- 이후 다른 프로세스가 공유 데이터에 접근하여 데이터를 사용하면, 수정중이었던 불안정한 데이터를 사용하게 되고 그 결과 예상치 못한 데이터가 산출된다.
🧨 따라서 프로세스의 최종 결과가 잘못된다.
🧨 데이터의 비일관성을 해소하기 위해서, 순차적으로 수행하는 매커니즘이 필요하다.
Race Condition
- 공유 영역(critical-section)에서 프로세스들의 사이에 제어가 없어 예측하지 못한 값이 발생하는 상태
Critical Serction Problem
- 각 프로세스들은 critical section segment의 코드를 가진다.
- 하나의 프로세스가 공유 영역에 들어가면, 다른 프로세스는 공유 영역에 들어갈 수 없다. (한 번에 하나의 프로세스)
- 문제의 해결을 위해서는 각 프로세스는 반드시 공유 영역에 진입하기 위해서 권한을 요청해야 하고, 공유 영역에 프로세스가 있다면(Lock), 그 프로세스가 공유 영역에서 나온 후에야 진입할 수 있다.
Critical Serction Problem에 대한 해결책
⚽ Mutual Exclusion
- 한번에 하나의 프로세스만 들어갈 수 있게 프로세스가 들어오면 공유 영역을 Lock한다.
⚾ Bounded Waiting
- 공유 영역 바깥에서 공유 데이터 사용을 위해 기다리는 프로세스는 영원히 기다리면 안된다.
- 각 프로세스가 0이 아닌 속도로 실행될 때, 즉 공유 영역에 진입하려는 프로세스와 공유 영역에서 수행중인 프로세스들은 모두 실행중이어야 한다.
- 공유 영역에 들어가는 프로세스에 대해서는 어떠한 전제조건도 없어야 한다. 할당되는 CPU 속도도 차별이 있으면 안된다.
🏀 Progress
- 공유 영역이 비어있으면, 공유 영역 바깥에서 기다리는 대기중인 프로세스는 아무런 이유없이 못들어가면 안된다.
- 즉, 공유 영역이 비어있으면 대기중인 프로세스는 즉시 공유 영역에 진입해야 한다.
- Preemptive : kernel 모드에서 다른 프로세스에게 CPU를 강제로 내준다.
이때는 일관된 데이터를 사용하지 못할 수 있기에 동기화가 필요하다. - Non-Preemptive : 공유 영역에서 실행중인 프로세스가 스스로 공유 영역에서 나올때까지 CPU를 다른 프로세스에 빼앗기지 않는다.
수행속도가 느릴 수 있다.
Petersion's Solution
- 소프트웨어로 구성된 해결책이다.
- 하드웨어로 된 해결책보다는 느리다.
- while문을 사용하여 기다리는 중이라면, 진행을 하지 못하고 루프에 갇힌다. (busy waiting)
- 따라서 overhead가 발생하는 방법이다.
- flag[i]를 사용하여 프로세스 i가 공유 영역에 들어가려고 하면 true, 아니면 flase로 표기한다.
- 한 번에 하나의 프로세스만이 공유 영역에 들어갈 수 있다.
🎈 하드웨어로 동기화하면 cs(critical-section)이 사용중이라면, interrupt를 disable해야 한다.
왜냐하면, 만약 cs에서 오류가 발생하면 빠져나올 수 없기에 위험하다. (interrupt를 enable할 수 없다.)
- 다만, CUP가 여러개인 멀티 프로세스에서 다른 CPU의 프로세스는 disable interrupt의 영향을 받지 않기에 여전히 cs에 진입할 수 있다.
따라서 모든 CPU에게 이 사실을 알려야 하고 이 과정에서 overhead가 발생한다. - interrupt가 없는 상태를 Atomic으로 표현한다. (All or Noting)
Mutex Locks
- Petersion's Solution보다 빠르다.
- low level, 즉 하드웨어에 좀 더 가깝기 때문에 더 빠르다.
- boolean 변수를 이용해서 cs를 보호하고 release한다.
- 이때, boolean 변수는 true로 시작하고 항상 atomic하다.
(수행중 다른 프로세스의 인터럽트를 걸 수 없다.)- 하지만, 여전히 busy waiting이 있고(while loop) check, wait를 하며 시간낭비가 발생한다. (overhead)
🎩 context switching이 필요하지 않아 잠깐 Lock을 유지할 경우 사용한다.
context switching가 굉장히 짧은 경우 state wait보다 busy waiting이 더 빠르기 때문이다. (여전히 running 상태)
하지만, context switching가 더 길면 CPU 퀀텀이 낭비되고 block한 후에 다른 프로세스를 구동하는 것이 더 효율적이다.
그리고 이것을 Semaphore를 통해 구현한다.
Semaphore
- busy waiting이 없다. CPU는 자발적으로 포기되고 waiting state로 상태가 전환된다.
- wait와 signal의 두 개의 atomic 함수만 존재한다.
- semaphore는 임의의 정수이거나 binary일 수 있다.
- 반드시 wait와 signal은 동시에 실행될 수 없다.
- 따라서 이 둘은 cs에 구현되는데 이러한 경우 busy waiting이 발생할 수 있다. (overhead)
- busy waiting을 없애기 위해서 각 semaphore에 연결된 queue를 사용한다. (integer와 next list의 pointer를 가짐)
- 큐가 기다리게 하는 block(CPU를 자발적으로 내줌)과 waiting 큐에서 프로세스를 하나 제거해 ready 큐로 보내는 wakeup이 있다.
(ready 큐의 프로세스는 CPU를 할당받으면 cs를 이용 가능하다.) - semaphore에서 deadlock과 starvation이 발생할 수 있다.
Deadlock
- 결코 일어나지 않을 이벤트를 무한히 기다려 결국 시스템이 다운된다.
Starvation
- 낮은 우선순위의 프로세스가 계속해서 높은 우선순위를 갖는 프로세스의 유입때문에 오랜 시간 기다렸지만, 실행되지 못하는 상태를 의미한다.
🤿 위의 두 문제를 해결하기 위해서 우선순위를 반전시키는 해결책이 있을 수 있다. 임시적으로 우선순위를 높여 프로세스가 실행될 수 있도록 한다.
Monitors
- object-oriented 동기화이다.
- 세마포어의 단점을 보완한 매커니즘이다.
- 모니터 안에 구현된 변수는 모니터 안에서 정의된 함수에서만 사용이 가능하며, 한번에 한 프로세스만 이 함수에 출입가능하다.
- 하지만 모니터가 완벽한 동기화를 제공하는가? 그것은 아니다.
따라서, wait와 siganl이 필요할 수 있다. - 따라서 모니터는 condition variables이나 세마포어를 함께 사용하기도 한다.
🙌🙌🙌🙌