Process Synchronization-1

February 21, 2023

Process Synchronization-1

Race Condition

여러 프로세스가 공유하는 데이터에 concurrent하게 접근하는 상황에서, 접근하는 순서에 따라 결과가 달라지는 현상
실행할 때 마다 결과가 달라질 수 있기 때문에 발생하면 안됨
방지하기 위해 프로세스간의 동기화(synchronization)가 필요

Critical Section

프로세스간 공유 변수를 사용하거나 파일을 쓰는 등의 역할을 하는 코드 구역
두 개 이상의 프로세스가 critical section (임계 영역)에서 실행되면 race condition이 발생됨
Race condition을 방지하고 임계 영역을 보호하기 위해서는 다음 조건들을 만족해야 함
1. Mutual Exclustion
  - 한번에 한 프로세스만 임계 영역에서 실행 가능
  - 임계 영역에서 실행 중인 프로세스가 있다면 다른 프로세스는 임계 영역에서 실행 불가
2. Progress
  - 임계 영역에 실행 중인 프로세스가 없는 경우, 임계 영역에 들어갈 수 있는 프로세스 중 하나를 선택해서 진입시켜야 함
  - 이 결정이 무한히 연기되면 안 됨
3. Bounded Waiting
  - 한 프로세스가 임계 영역에 진입 요청을 한 경우, 요청이 허가되기 전에 다른 프로세스들이 임계 영역에 진입할 수 있는 횟수 제한 존재
  - 즉, 언젠가는 임계 영역에 언젠가는 들어갈 수 있다는 의미

Peterson’s solution

// Process i의 경우
do {
   flag[i] = true;               // Process i 가 임계 영역에 입장 가능한 상태
   turn = j                      // Process j에게 입장 기회를 넘김
   while(flag[j] && turn == j);  // Process j가 임계 영역에 입장 가능하고 입장 기회가 있다면 대기

   /** Critical section **/

   flag[i] = false;              // Process i가 임계 영역을 다 사용함을 표시

   /** Remainder section **/
}

프로세스가 두 개(i, j)일 때 임계 영역을 보호하기 위해 사용 가능한 방법
turn 과 flag 라는 공유 변수를 이용하며, 세 가지 조건을 모두 만족
- flag[i]: i번째 프로세스가 임계 영역에 입장 가능한 상태 여부
- turn: 임계 영역에 우선적으로 입장할 프로세스 (i 혹은 j)
다른 프로세스에게 임계 영역에 우선적으로 입장할 기회를 양보하고 대기
Busy waiting 문제가 존재

Busy Waiting

프로세스가 임계 영역에 입장 가능해 질 때 까지 while loop를 계속 도는 현상
계속 loop를 도므로 임계 영역이 긴 경우 CPU 사이클을 낭비한다는 단점이 존재
임계 영역이 짧은 경우에는 효율적일 수 있음

References

https://jooona.tistory.com/12

기타

2022-07-30에 작성된 Process Synchronization 문서를 정리하고 보완하는 중