[Operating System] Synchronization Tools - Background

Background

• 앞선 예시로 원형 큐가 있었는데, BUFFER_SIZE - 1개만 담을 수 있었다. 이 문제를 해결하기 위해 count라는 변수를 사용해서 해결할 수 있다.
• producer process
  
• consumer process
  
• 각각은 괜찮아 보이지만, 동시에 실행되었을 때 문제가 발생할 수 있다.
• machine language에서는 count++는 다음과 같다.
  
• 마찬가지로, count--는 다음과 같다.
  
• 위 두 연산이 순서대로 처리되어 5 -> 6 -> 5가 될 것 같지만, (혹은 5 -> 4 -> 5) 순서가 임의로 섞여버릴 가능성이 존재해서 아래처럼 될 가능성이 존재한다.
  
• 동시에 count라는 변수에 접근해서 바꾸도록 했기 때문에 이러한 문제가 발생했다.
• race condition : 같은 데이터를 동시에 접근하고 바꾸어서 실행 순서에 따라 결과값이 바뀔 수 있는 상황을 지칭한다.
• 해결 방법 : 동시에 한 프로세스만 count 변수를 바꾸도록 해야 한다.

The Critical-Section Problem

• critical section?
  • 공유되는 데이터에 접근하거나 그 값을 변경하는 코드 영역.
• system이 n개의 프로세스$\{P_0,P_1,...,P_{n-1}\}$로 구성되었다고 가정해 보자.
• entry section : critical section에 들어가기 위해 권한을 요청하는 부분.
• exit section: critical section이 끝난 부분
• remainder section : 말 그대로 나머지.
• general structure of a typical process
  
• critical-section problem의 해결책
  1. Mutual exclusion : $P_i$가 자신의 critical section에서 실행중이면, 다른 어떠한 프로세스도 그들의 critical section에서 실행될 수 없다.
  2. Progress : 어떠한 프로세스도 자신의 critical section에서 실행중이지 않고, 몇몇 프로세스가 자신의 critical section에 들어가고자 한다면, remainder에서 실행중이지 않은 프로세스들만 critical section에 들어갈 자격이 된다. 어느 프로세스로 결정할 것인지는 무기한으로 연기되서는 안 된다.
  3. Bounded waiting : 프로세스가 자신의 critical section에 들어가고자 요청한 시점과 요청이 받아들여지는 시점 사이에 다른 프로세스들이 자신의 critical section에 들어가는 횟수는 제한되어있다.
• 각 프로세스는 nonzero speed로 실행된다고 가정하지만, 그들 사이의 상대적인 속도는 고려하지 않는다.(?)
• 한 시점에, 운영체제에서 실행되고 있는 여러 커널모드 프로세스들을 고려해 보자. -> 이 경우 발생할 수 있는 race condition들 :
  • 파일을 동시에 열어서 수정
  • 동시에 fork() 실행 -> pid값이 같은 두 프로세스가 만들어져버림
• single-core 환경에서는 shared variable이 변경되는 도중에 interrupt를 막아버리면 간단히 해결 가능하지만, multi-core에서는 그렇지 않다. interrupt를 막아버리는 행위 자체가 cost가 대단히 높다.
• 운영체제에서 critical section을 다루는 두 가지 방법
  • preemptive kernels
    • 커널모드에서 실행중인 프로세스가 preempt되는 것을 허용한다.
    • race condition이 발생하지 않게 잘 설계되어야 한다. (SMP architecture의 경우 매우 힘듬)
  • nonpreemptive kernels
    • 커널모드에서 실행중인 프로세스가 preempt되는 것을 허용하지 않는다.
    • 동시에 하나의 커널 프로세스만 실행될 수 있으므로 race condition은 발생하지 않는다.
• preemptive kernel이 더 선호되는데, 그 이유는 반응성이 좋고, real-time programming에 더 적합하기 때문이다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition