1. 배경지식
Cooperating process, 서로 영향을 주고 받고, 데이터를 주고받는 프로세스들을 살펴 보았다. 하지만 공유 데이터에 동시에 접근할떄는 일관성에 유의해야한다. 따라서 이 프로세스들이 순서대로 실행되어야, 데이터의 일관성을 유지할 수 있다.
데이터의 통일성을 여러 프로세스가 공유하는 경우. 동시에 실행 될 때 임의의 프로세스는 어느 시점에서 인터럽션이 걸려 멈출지 모른다. 병렬 실행될 때에는, 복수의 명령어로 인해 발생할 수 있다.
생산자 소비자 문제를 떠올려 보자, 공유데이터를 사용하고 비 동기화 작동을 한다. 버퍼 내의 아이템을 세고 count 변수를 추가해보자, 새 아이템을 추가하고 뺄 때. count는 증감한다. 이 때 일관성에서 문제가 발생한다. 두 개의 프로세스가 분리되어 있지만 제대로 작동하지는 않는다. count가 5일 때, 생산자와 소비자가 여전히 실행된다고 생각하자. count++와 count--가 동시에 실행되면 4,5,6 뭐가 나올지 모른다.
다른 예를 들어, 복수의 스레드를 생성해서 각 스레드가 i를 가지고 1부터 10000까지 count 한다고 했을때(sum전역변수에 저장함), 두 스레드의 count를 합치면 20000이 나와야 하지만 여러번 실행해보면 결과가 다르게 나올때가 있다. 하나는 감소. 하나는 증가로 설정하고 하면 더 잘 보일 것이다.
count++와 count--는 각각 하나의 명령어처럼 보이지만, 사실은 여러개의 명령어로. 위의 그림처럼 구성되어 있다. 중간에서 context switch가 발생할 수도 있기에 우리의 예상과 다른 결과가 나오는 것이다. 설령 같은 레지스터를 쓰더라도 인터럽트 핸들러(혹은 스케줄러)에 의해 save/load 되기에 같은 문제가 발생한다.
이런 상황을 일반화 시켜 Race Condition라고 부른다. 이 문제는 공유되는 데이터를 동시에 접근/조작하는 경우에 실행 결과는 순서에 따라 달라질 수 있다. 이를 방지하기 위한 방법은. 특정 시점에 한 프로세스만 다루는 다루는 것이다. 따라서 프로세스들이 순차적으로 실행되도록 만들어야한다.
2. 임계영역 문제
n개의 프로세스가 있을때, 코드 세그먼트를 임계영역이라고 부르자. 이 영역에서 다른 프로세스와 공유하는 데이터에 접근, 업데이트를 한다고 하자. 이때, 한 프로세스가 임계영역을 실행하는 경우 다른 프로세스들이 임계영역을 실행하지 못하게 만드는 것이다.
코드 섹션은 다음과 같이 나눌 수 있다.
(1) entry section: 임계영역에 진입하기 위한 허가를 요청하는 부분
(2) critical section: 임계영역
(3) exit-section: 임계영역 뒤에 나오는 부분
(4) remainder-section: 나머지 코드가 위치한 부분
세 가지 요구사항이 있다.
(1) Mutual Exclusion : 임계 영역이 실행중일 때에는 다른 프로세스들은 이 영역에 접근할 수 없다.
(2) Progress(avoid deadlock): 임계영역에 진입한 프로세스가 없을때, 어떤 프로세스도 임계영역에 접근하지 못하는 상황을 지양해야한다.
(3) Bounded Waiting(avoid starvation): 우선순위가 계속 밀려 임계영역에 진입하지 못하는 프로세스가 있으면 안된다.
하지만 이 세 문제를 다 푸는 것은 굉장히 어렵다.
단일 코어를 가정했을 때, 인터럽트를 하지 못하게 하면 임계영역 문제를 해결한다. 하지만 이는 멀티 프로세서 환경에서는 적용할 수 없는 방법이다.
일반적인 접근법으로 두 가지가 있다.
(1) 선점형 커널 : 프로세스는 언제든지 선점될 수 있다. 하지만 응답성이 좋다.
(2) 비선점형 커널 : 어떤 커널 모드가 실행되고 종료, 혹은 자발적으로 CPU할당을 포기한다면, 커널 데이터 구조에서 레이스 컨디션으로부터 자유롭다.
3. solution
3.1 Dekker 알고리즘(6.13)
3.2 Eisenberg and McGuire 알고리즘(6.14)
3.3 Peterson 알고리즘
하지만 이 알고리즘이 제대로 작동할 것이라는 보장이 없다. 왜냐하면 entry section 중간에 context switch가 발생할 수 있기 떄문이다. 하지만 이 알고리즘은 CSP의 세 목표를 달성하는데 아주 좋다. 따라서 피터슨 알고리즘은 이론상 옳은 알고리즘이다.
4. Hardware Support
4.1 Hadware-based Solution
하드웨어 명령어를 통해 임계영역 문제를 해결할 수도 있다. 혹은 다른 방법의 토대가 될 수 있다.
(1) memory barriers or fences
(2) hardware instruction
(3) atomic variables
atomic operation은 더이상 인터럽트가 불가능한 연산(실행) 단위다. 현대 컴퓨터 시스템은 atomic instruction을 활용한다. 개념상 두 유형의 명령어가 있다.
test_and_set()
이 경우 mutual exclusion이 가능하다.
compare_and_swap()
통상적으로 이 명령어는 atomic variable와 같은 도구를 구성한다. atomic variable은 단일 변수에 대한 레이스 컨디션이 발생했을떄, 기본 데이터 자료형에 의한 atomic operation을 제공한다.
4.2 Atomic Variable
