[Operating Systems] Synchronization

멀티 프로세싱, 혹은 멀티 스레딩 환경에서는 어떠한 데이터를 공유하여 작업을 하는 경우가 생긴다.
하지만 멀티 프로세싱을 위해 컨텍스트 스위칭을 하며 실행하다 보면 원하는 결과를 보장하지 못할 수 있다.
실행 순서에 따라 결과가 다르게 나오는 상황을 race condition이라고 한다. 

여러개의 프로세스가 공유 자원을 동시에 접근하여 race condition이 생길수 있는 코드를 critical section이라고 하며,
Synchronization, 즉 동기화는 critical section에서 항상 같은 순서로 실행될 수 있도록 하여 race condition이 생기지 않도록 하여 data consistency를 유지시켜 주는 과정을 말한다.
이러한 동기화 메커니즘은 크리티컬 섹션의 입구와 출구에서 동작하며
바람직한 동기화는 다음과 같은 특성을 가진다.
1. Mutual Exclusion : 특정 시간에 CS에 하나의 프로세스만 들어가도록 한다.
2. Progress : CS에 아무도 없다면 CS로 들어가기 원하는 프로세스는 바로 들어간다.
3. Bounded Waiting : 유한 시간 대기 후 CS에 들어갈 수 있도록 한다.

1번 조건만 만족해도 동기화 자체는 성립하지만 바람직한 동기화가 되기 위해서는 1,2,3 조건을 모두 만족해야 한다.

동기화 메카니즘의 종류로
Peterson's solution, Hardware support, Semaphore, Monitor가 있다.
각각에 대해서 간단히 설명하면
Peterson's solution은 순서를 나타내는 turn과 CS로 들어가기를 원하는 변수인 flag를 이용하여 동기화를 구현하는 방법이다.
Hardware support는 TestAndSet 혹은 Swap을 이용하는데 이러한 함수들을 하드웨어 적으로 atomic operation이 되는 것을 요구하기 때문에 hardware support라 한다. atomic operation은 그 operation을 실행을 끝마칠 것을 보장해 주는 오퍼레이션인데 오퍼레이션 실행 중에 컨텍스트 스위칭일 일어나지 않음을 보장할 수 있다.
Semaphore는 변수와 wait(), signal() 두 개의 연산으로 이루어지는데 wait()의 경우에는 변수 값이 0보다 크면 1 감소시키며 자원을 획득하고, 0이하이면 대기한다. signal()은 정수값을 1 증가시키거나 대기 중인 프로세스에게 자원을 건네준다.
구현 방법으로는 첫째로 loop를 돌며 대기하는 busy-waiting 방식이 있는데 이 경우에는 time quantum 만큼을 낭비할 수 있으므로 비효율적이다. 따라서  block(), signal() 함수를 도입하여 대기중인 프로세스를 리스트 형태로 관리하고 자원을 획득할 수 없을 경우에는 타임 퀀텀을 다 사용하지 않고 바로 다른 프로세스에게 실행 권한을 줌으로써 효율성을 극대화 시킬 수 있다.
Monitor는 높은 수준의 추상화라고 볼 수 있는데 CS를 어떠한 객체처럼 취급하고 그 객체에는 단 하나의 프로세스만 들어갈 수 있도록 관리한다.

동기화의 전통적인 문제로써
Bounded-Buffer Problem, Readers and Writers Problem, Dining-Philosophers problem이 있다.
이게 동기화로 풀 수 있는 '문제'라는 것인지 아니면 동기화를 사용했을 때의 '문제'인지는 확실히 모르겠는데
아마 전자 측인 듯 하다.

이것의 해결책은 Deadlock 개념과 함께 다음 장에서 나온다.