동기화 (Synchronization) - (1)

동기화란 여러 프로세스가 공유하는 자원의 일관성(Consistency)을 유지하는 것이다.

1. 경쟁조건 (Race Condition)

(1) 경쟁 조건

• 여러 프로세스들이 동일한 데이터에 동시에 접근해서 조작할 수 있다.
• 이 경우 실행 결과 값은 접근과 갱신이 일어나는 순서에 따라 달라질 수 있다.

(2) Example

• counter 변수 값이 현재 5이고, 생산자와 소비자가 동시에 "counter++"와 "counter--" 명령을 수행한다고 하자.
• 이 두 명령의 실행 순서에 따라, counter 변수 값을 올바른 값인 5가 될 수 있으나, 원치 않게 4나 6이 될 수 있다.
• counter++ 명령어
  • register1 = counter
  • register1 = register1 + 1
  • counter = register1

• counter-- 명령어
  • register2 = counter
  • register2 = register2 - 1
  • counter = register2
• 위 실행이 "counter = 5"에서 다음과 같이 섞여 수행되었다고 가정
  • S0: 생산자가 수행 register1 = counter {register1 = 5}
  • S1: 생산자가 수행 register1 = register1 + 1 {register1 = 6}
  • S2: 소비자가 수행 register2 = counter {register2 = 5}
  • S3: 소비자가 수행 register2 = register2 - 1 {register2 = 4}
  • S4: 생산자가 수행 counter = register1 {counter = 6}
  • S5: 소비자가 수행 counter = register2 {counter = 4}
  • counter = 4

(3) 동기화의 필요성

• 경쟁 조건에 의해 불확실한 상태에 도달할 수 있다.
• 두 개 이상의 프로세스가 동시에 하나의 변수를 조작하는 것을 허용했기 때문이다.
• 경쟁 조건의 예방을 위하여
  • 한 번에 오직 하나의 프로세스만이 특정 변수를 조작하는 것을 보장할 필요가 있다.
  • 프로세스들은 동기화(Synchronization)될 필요가 있다.

 

2. 임계 구역 문제 (Critical Section Problem)

(1) 임계 구역 (Critical Section)

둘 이상의 process가 동시에 접근해서는 안 되는 공유 자원을 접근하는 코드의 일부

• 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역에 들어갈 수 없다.
• 각 프로세스는 자신의 임계구역으로 진입하려면 집입 허가를 요청해야 한다.

(2) 해결을 위한 세 가지 요구 조건

Critical-Section Problem을 해결하기 위해 3가지 조건을 모두 만족해야 한다.

(i) 상호 배제 (mutual exclusion)

• 프로세스가 자기의 임계 구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.

(ii) 진행 (progress)

• 자기의 임계 구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.

(iii) 한정된 대기 (bounded waiting)

• 프로세스가 자신의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

(3) 운영체제가 임계 구역을 다루는 두 가지 접근법

(i) 비선점형 커널

• 실행 중인 프로세스가 하나밖에 없기 때문에 커널 자료구조에 대한 경쟁조건은 발생하지 않는다.

(ii) 선점형 커널

• 설계하는 것이 매우 어렵지만, 선점형 커널이 응답성이 높고 실시간 프로그래밍에 적당하므로 선점형을 선호