[OS] 운영체제 7. Process Synchronization 1 : 프로세스 동기화, 임계영역

[Process Synchronization]

공유 데이터(shared data)의 동시 접근(concurrent acecss)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다

일관성(consistency)를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘이 필요

 

[Race condition]

여러 프로세스들이 동시에 공유데이터를 접근하는 상황

데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다

 

=> race condition을 막기 위해 concurrent process는 동기화(synchronize) 되어야 한다

 

Process 가 한 개 있는 경우

Process가 두 개 있는 경우

S-box(memory address space)를 공유하는 E-box(CPU process)가 여럿 있는 경우,

Race Condition의 가능성이 있다

 

[OS에서 race condition이 발생하는 경우]

1) interrupt handler v.s. kernel

커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행

커널모드 running 중 interrupt 가 발생하여 인터럽트 처리루틴이 수행

해결책 : 처리가 완료되기 전까지 interrupt를 받아주지 않는다

 

2) preempt a process running in kernel

해결책 : 커널모드에서 수행 중일 때는 CPU를 preempt(선점) 하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt

 

3) multiprocessor

multiprocessor의 경우 위의 케이스들과 달리 interrupt enable/disable로 해결되지 않는다.

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

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

 

 

The Critical-Section problem : 임계영역 문제

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

problem : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다

 

 

프로그램적 해결법의 충족 조건

1) Mutual Exclusion (상호배제)

프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다

2) Progress

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

3) Bounded Waiting(유한한 대기)

프로세스가 ciritical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다(starvation 방지)

 

[Critical Section problem 해결 알고리즘 1]

Process0 이 한 번 수행으로 끝이난 경우 Process1 은 다시 들어갈 수 없음

(타 프로세스가 turn 을 내 값으로 바꿔줘야만 내가 들어갈 수 있기 때문) : 과잉양보 발생

-> mutual exclusion 은 만족하나 progress 는 만족하지 않음

 

Process0]

do {
   while(turn != 0);    // my turn?
   critical section
   turn = 1;
   remainder section  // now it's your turn
} while(1)

Process1]

do { 
   while(turn != 1); // my turn?
   critical section 
   turn = 0;
   remainder section  // now it's your turn
} while(1)

[Critical Section problem 해결 알고리즘 2]

두 프로세스가 2행까지(while문) 수행 후 끊임 없이 양보하는 상황 발생 가능

(critical section 진입 후 flag를 false 로 두어 나왔음을 알리지만 2행까지 실행된 경우 두 프로세스가 loop가 돌며 계속 양보하게 되므로)

Process0, Process1]

do {
   flag[i] = true;   //pretend I am in
   while(flag[j]);    //is he also in? then wait
   critical section
   flag[i] = false;   // i am out now
   remainder section
} while(1);

 

[Critical Section problem 해결 알고리즘 3]

Peterson's Algorithm

Mutual Exclusion, Progress, Bounded waiting 을 모두 만족

하지만 Busy waiting(=spin lock=loop) : CPU , memory 를 계속 사용하며 wait 

Process0]

do {
   flag[0] = true;   //My intention is to enter
   turn = 1;          // set to his turn
   while(flag[1] && turn == 1);    // wait only if
   critical section
   flag[0] = false;
   remainder section
} while(1);

Process1]

do {
   flag[1] = true;  //My intention is to enter
   turn = 0;        // set to his turn
   while(flag[0] && turn == 0);     // wait only if
   critical section
   flag[1] = false;
   remainder section
} while(1);

하드웨어적으로 Test와 Modify를 atomic 하게(읽기와 쓰기를 한번에(하나의 instruction으로)) 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

: interrupt 등으로 프로세스가 CPU를 뺏길 때, 실행 하던 instruction은 끝마치고(라인 한 줄) 뺏긴다.

instruction 을 한 줄이 아닌 두개의 instruction 으로 지원하여 instruction+flag처리를 한 번에 다룰 경우, 임계영역에 대한 처리가 간단해진다

Synchronization variable :
boolean lock = false;

do {
   while(Test_and_Set(lock)); 
   critical section
   lock = false;
   remainder section
}

 

※ 이화여대 반효경 교수님의 운영체제 강의 정리