Process Synchronization

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

KOCW 반효경 교수님의 운영 체제 강의를 수강하면서 작성한 포스트입니다. 😁

Race Condition

S-box (Memory Address space)를 공유하는 E-box(데이터 연산을 하는 부분)가 여러 개가 있는 경우 Race Condition의 가능성이 있습니다. (이 부분은 교수님이 임의로 붙인 이름이라고 합니다.)

* Multiprocessor system에서 공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴들 간에서 발생할 수 있습니다. 

E-box	S-box
CPU	Memory
컴퓨터 내부	디스크
프로세스	해당 프로세스의 주소 공간

 

OS에서의 Race Condition

1. kernel 수행 중 인터럽트 발생 시

커널 모드 running 중 인터럽트가 발생해서 인터럽트 처리 루틴이 수행합니다. 양쪽 다 커널 코드이므로 kernel address space를 공유합니다.

 

2. process가 system call을 해서 kernel mode로 수행 중인데 context switch가 일어나는 경우

보통 context switch가 이렇게 이루어진다고 할 수 있지만

커널이 실행되고 있는 와중에 다른 프로세스에 선점되는 경우 race condition이 발생할 수 있습니다. 이 문제는 커널 모드에서 수행 중일 때는 CPU를 선점하지 않음으로 해결합니다. 커널 모드에서 다시 사용자 모드로 돌아갈 때 선점되는 방식을 이용합니다. time sharing system은 real time system이 아니기 때문에 이런 문제를 쉽게 해결할 수 있습니다.

 

3. multi processor에서 shared memory의 kernel data

CPU가 여러 개 있는 환경입니다. 이런 경우는 작업 주체가 여럿이기 때문에 문제가 발생합니다.

 

방법 1) 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

 

Process Synchronization 문제

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있습니다. 일관성(consistency)을 유지하기 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)을 정해주는 메커니즘이 필요합니다.

 

Race condition

여러 프로세스들이 동시에 공유 데이터를 접근하는 상황에서 발생합니다. 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라집니다. race condition을 막기 위해서는 concurrent process는 동기화 되어야 합니다.

 

Critical Section Problem

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우에 발생할 수 있는 문제입니다. 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재합니다. 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 합니다. 

 

이 문제를 해결하기 위해 충족시켜야 하는 조건 세 가지가 있습니다. 

* Mutual Exclusion: 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 단 됩니다. 

* Progress: 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해 주어야 합니다.

* Bounded Waiting: 프로세스가 critical section에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에는 한계가 있어야 합니다.

 

이 때, 모든 프로세스의 수행 속도는 0보다 크고 프로세스들 간의 상대적인 수행 속도는 가정하지 않습니다.

 

Algorithm 1

// 프로세스 0번의 케이스
do {
    while (turn != 0);
    critical section
    turn = 1;
    remainder section
} while (1);

Pi can enter its critical section if (turn == i)

이 코드의 문제점은 교대로 들어갔다 나오게 짜여져 있다는 것입니다. 위에서 보았던 progress 조건을 만족시키지 못할 가능성이 높습니다. 

 

Algorithm 2

do {
    flag[i] = true; 	// 의사 표시
    while (flag[j]); 	// 상대방의 의사 확인
    critical section
    flag[i] = false;
    remainder section
} while (1);

이 경우 아무도 critical section에 들어가지 못했는데 flag만 들게 된 상황이 발생할 수 있습니다.

 

Algorithm 3 (Peterson's Algorithm)

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while (1);

algorithm 1과 algorithm 2를 합친 형태입니다. 위에서 언급한 세 가지 조건을 모두 충족하는 알고리즘입니다. 하지만 이 코드에는 busy waiting(=spin lock) 이라는 문제점이 있습니다. 계속해서 CPU와 메모리를 이용해서 검사를 하게 되기 때문에 이런 이름이 붙었습니다. busy wait을 해결할 수 있는 방법은 뒤에서 알아보도록 하겠습니다. 

 

하드웨어적으로 문제 해결

하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우에는 앞에서 언급되었던 문제는 간단하게 해결이 됩니다. 데이터를 읽고 쓰는 것이 하나의 instruction으로 실행이 가능하지 않기 때문에 위의 문제가 발생하게 됩니다. 그래서 하드웨어적으로 이 작업을 atomic하게 수행하게 해 주면 문제를 쉽게 해결할 수 있습니다.