Race Condition 경쟁 상태
- 여러 개의 프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과값이 달라질 수 있는 현상
- 경쟁 상태를 예방하기 위해서 경쟁 상태의 프로세스들은 동기화되어야 한다.
- 단일 프로세서 환경에서 경쟁 상태는 CPU 스케줄러에 의해 발생할 수 있다.
Critical Section Problem 임계 구역 문제
- n 개의 프로세스 {P0, P1, ..., Pn-1} 이 있는 시스템이 있을 때, 각 프로세스는 임계구역이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.
- 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다
- Entry sectin : 임계구역에 들어가기 위해 허락을 요청하는 코드
- Exit section : 임계구역에서 나감을 알리는 코드
Requisites for solution 해답을 위한 필수 조건
Mutual Exclusion 상호 배제
- 하나의 자원에는 하나의 프로세스만 접근할 수 있다.
Progress 진행
- 임계구역이 비어있으면(임계구역에서 실행 중인 프로세스가 없으면) 다른 프로세스가 자원을 사용할 수 있어야한다.
Bounding Waiting 한계 대기
- 기다리면 언젠가는 임계구역에 진입할 수 있어야 한다.
Critical-Section Handling 임계 구역 처리
- 커널이 선점인지 비선점인지에 따라 두가지의 접근법이 있다.
-
선점 -> 커널 모드에서 실행 중일 때 프로세스 선점이 가능
-
비선전 -> 커널 모드를 종료하거나 차단하거나 자발적으로 CPU를 양보할 때까지 실행된다.
- 커널모드의 경쟁 상태로부터 자유롭다.
-
Peterson's Solution
- 두 개의 프로세스 동기화에 대한 해결법
- 두 프로세스들이 두 가지의 변수를 공유한다
- int turn; - 임계구역에 들어갈 차례가 누구인가 - boolean flag[2]; - 프로세스가 임계구역에 들어갈 준비가 되었는지 알림 - flag[i] == true이면 Pi는 준비됨
- flag 값이 True이며, turn이 본인일 때 임계구역에 들어갈 수 있도록 한다.
Synchronization Hardware
Simple tool - lock
- 임계구역에 진입할 때 lock을 걸고 퇴장할 때 lock을 풀어준다.
TestAndSet instruction
- 입력 값의 상태를 반환하고, 입력값은 True로 갱신함
- lock이 false면(다른 프로세스가 임계구역에 있음) while문을 돌면서 true가 될 때까지 기다린다.
- true가 되면 임계구역에 진입
- lock을 false로 만들고 퇴장
Swap instruction
- 입력값을 서로 바꿈
- 각각의 프로세스는 key라는 boolean 값을 가짐
- key가 true면 임계구역에 들어가고 싶어하는 것을 의미
- lock이 true면 프로세스가 이미 임계구역에 있음을 의미
Semaphore
- Semaphore란 정수형의 값임
- 0이면 쓸 수 있는 자원이 0, 1이면 쓸 수 있는 자원이 있다는 것을 의미
P(S){
while(S<=0)
S--;
}
V(S){
S++
}- S가 1이면 임계구역 입장 가능
- S가 0이면 다른 프로세스가 임계구역에 있음을 의미
- P(S)는 S가 0이면 기다렸다가 1이 되면 입장, S를 0으로 만들어 다른 프로세스의 접근을 막음
- V(S)는 임계구역에서 퇴장할 때 자원을 반납한다는 것을 의미
- 이처럼 0 또는 1만 가지는 semaphore를 Binary semaphore라고 한다.
Semaphore implementation
- Busy waiting
- 프로세스가 임계구역에 있을 때, 다른 프로세스는 지속해서 루프를 돌게 된다.
- 이는 CPU cycle을 낭비하는 것이다.
- Spinlock이라 부른다.
- Block and wakeup
- Block
- P(S) 자체를 호출한 프로세스를 일시 중단한다.
- 프로세스의 PCB를 S의 wait queue에 추가한다.
- Wakeup
- 프로세스의 PCB를 S의 wait queue에서 제거한다.
- 프로세스를 실행한다.
- Block
