Process Synchronization

독립적으로 존재하는 여러개의 프로세스들이
동작을 맞추고, 서로 정보를 공유하는 것,
즉 프로세스들이 서로 대화를 나누는 것을 동기화Synchronization라고 한다.

프로세스들이 서로에 대해 모르는 것을 비동기적Asynchronous
여러개의 프로세스들이 동시에 시스템에 존재하는것을 병행적Concurrent라 하고
병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있다.

하나의 기계어 명령의 실행 도중에는 방해Inturrupt받지 않지만,(원자성, 분리불가능)
기계어 실행 중간중간엔 다른 프로세스에게 프로세서를 빼앗길 수 있기때문에
명령 수행과정의 순서에 따라 결과값이 달라질 수 있다.

상호 배제Matual exclusion

둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것

공유 데이터Shared data(or Critical data)
여러개의 프로세스들이 공유하는 데이터

임계 영역Critical section
공유 데이터를 접근하는 코드 영역

한 프로세스가 임계영역에 들어와 있으면,
다른 프로세스가 그 임계 영역에 접근하는 것을 막는다.

상호 배제 기본연산Mutual exclusion primitives

enterCS() primitive
critical section 진입 전에 다른 프로세스가 critical section 안에 있는지 검사한다.

exitCS() primitive
critical section을 벗어날 때의 후처리 과정으로,
critical section을 벗어났음을 시스템이 알린다.

상호배제 기본연산의 요구사항Requirements for ME primitive

상호배제Matual exclusion
critical section(CS)에 프로세스가 있으면 다른 프로세스의 진입을 금지

진행Progress
CS안에 있는 프로세스 외에는 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
즉 CS안에 아무도 없으면 들어갈 수 있어야 한다

한정대기Bounded waition
프로세스의 CS진입은 유한시간 내에 허용되어야 함

소프트웨어 솔루션

Dekker's Algorithm - flag와 turn을 사용. 2개 프로세스 상호배제
다익스트라 알고리즘 - 3개의 state를 가지는 flag 사용. n개의 상호배제

하드웨어 솔루션

TestAndSet(TAS) instruction - 기계어 사용. busy waiting임

OS supported 솔루션

spin Lock - 정수형 변수 S를 사용. 초기화, P(), V()연산으로만 접근 가능
Semaphore - Busy waiting을 해결한 방식. 음이 아닌 정수형 변수 S를 사용
EventCount/sequencer - Starvation을 해결. 은행 번호표와 비슷한 방식으로 순서대로 처리

Language-Level solution

Monitor