프로세스 동기화, Perterson's, Atomic

1. 프로세스 동기화란?

• 공유 메모리에 존재하는 데이타에 여러 개의 실행(다수의 cpu, 다수의 프로세스, 다수의 스레드 등)이 발생하는 경우 해당 값이 원치 않는 방식으로 수정되고 출력될 수 있음. 데이타의 완전성integrity을 보장하는 것을 동기화라고 함. 공유 메모리에 여러 실행이 발생하는 경우를 경쟁 상태 Race Condition 라고 함. 경쟁 상태에 놓이는 공유 데이타를 임계 지역Cretical section이라 함.

2. 임계지역 동기화 문제 해결을 위한 세 가지의 요구 사항
   1) 상호배제 Mutual Exclusion

• 임계 지역에 접근 할 때는 단 하나의 프로세스만 진입한다.
• 임계 지역은 단순하게 데이타라 하여 하나의 변수(int x;)를 의미하지 않고, 해당 변수가 수정되는 코드(x++;)를 의미한다.

2) 진행 Progress (avoid deadlock)

• 임계 지역이 사용되고 아무도 사용하지 않을 경우, 다른 프로세서가 진입할 수 있어야 한다.
• 임계 지역이 비어있는데도 아무도 사용하지 못하면 데드락 문제가 발생한다.

3) 유한 대기 Bounded Waiting (avoid starvation)

• 임계 지역에 접근하려는 모든 프로세스가 해당 임계지역에 들어갈 수 있어야 한다.
• 임계 지역에 접근하지 못하는 프로세스가 발생할 경우 기아 현상이 발생한다.

3. 해결을 위한 세 가지의 접근
   1) 해결책 1. 방해 금지 Prevent interrupts

• 데이타에 접근은 kernel만 가능. 커널이 프로세스 작업 중간에 인터럽트를 불가능하게 하여, 문제 발생 여지를 제거. 프로세스가 해당 값을 store하는 이후 접근.
• 가장 간단한 해결책으로 인터럽트가 발생하지 않도록 한다.
• interrupt를 막으며 생기는 효율성 문제가 발생.
• 임계지역을 접근해야 하는 프로세스가 많고, 멀티프로세서(다중 cpu)가 해당 임계지역에 접근하는 경우, 모든 프로세서가 멈춰 버리는 상황이 발생할 수 있다.

2) 해결책 2. Non-preemtive kernel

• 커널 모드로 진입한다 하더라도 문맥 교환을 막아버림.
• 문맥 교환이 발생하지 않으므로 경쟁 상태에 놓이지 않음.

3) 해결책 3. Preemtive kernel

• 효율적인 cpu활용을 위하여, 디자인이 어렵고, 완벽한 해결책이 없음에도 불구하고, preemptive 스케줄링으로 문제를 해결.
• 피터슨 알고리즘 Peterson's Algorithm 을 통해 이론적인 해결책과 Atomic Operation 을통해 하드웨어적인 방법으로 문제에 접근.

4. 피터슨 알고리즘 Peterson's Algorithm
   

• 임계지역에 접근함에 있어서, 자신의 flag를 true로 하여 임계지역에 접근을 원하다는 것을 밝히고, turn을 상대방에게 먼저 넘긴다. 만약 상대방이 임계지역에 접근하려는 의사가 없거나(상대방의 flag =false), 해당 기회가 자신에게 넘어왔다면(turn = 자신의 번호), 임계지역에 접근한다.
• 앞서의 알고리즘에서 flag만 존재할 경우, 하나의 프로세스가 flag를 true로 한 상태에서 cpu를 빼앗기면, 해당 작업은 계속 true로 남기 되어, 아무도 진입(progress)하지 못하는 상황이 발생한다.
• 앞서의 알고리즘에서 turn만 존재할 경우, 상대방이 자신의 turn을 넘기지 않으면, 결코 해당 임계지역에 진입(progress)하지 못하는 상황이 발생한다.
• Mutual Exclusion 에 대한 이론적인 완벽한 해결책.
• 다만 loop로 cpu를 낭비하는 오버헤드 발생. Busy Waiting(Spin Lock)
• 알고리즘은 완벽하나, 알고리즘 중간에 발생하는 인터럽트에는 대응할 수 없음.

5. Atomic Operation

• cpu의 작동의 최소한의 단위인 클럭은 분해할 수 없는 atomic 작업임. 경쟁 상태를 해결하기 위하여 결코 분해할 수 없는 물리적인 작업을 마련함. 이를 Atomic Operation이라 하며 해당 작업을 Atomic instructions라 함.
• 이러한 오퍼레이션은 test_and_set()과 compare_and_swap() 등 있음.
• 해당 오퍼레이션의 개발과 이해는 어렵지만, 개발자는 해당 오퍼레이션을 활용할 수 있음. 자바에서는 java.util.concurrent.atomic.AtomicBoolean 클래스가 바로 그것임.

사진 등 자료의 출처, 참고 자료 :
http://www.kocw.net/home/search/kemView.do?kemId=1046323
https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog
이화여대 반효경 교수와 주니온TV의 영상강의를 주요자료로 하여 운영체제를 학습하고 정리하고 있습니다.