Process Synchronization - Race Condition, 임계구역 문제와 Semaphore

http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323

해당 강의를 보고 개인적으로 정리를 하는 포스팅 입니다.

운영체제

---

 

일반적으로 작업은 데이터를 저장하는 공간에서 데이터를 받아와, 작업 처리를 담당하는 프로세서가 처리하고

그 처리 결과를 다시 저장소에 저장하는 형식으로 동작한다.

 

Race Condition

Race Condition 이란 두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다.

 

-> 공유자원에 여러 프로세스가 동시에 접근할 경우 발생

 

OS 에서 Race Condition 이 발생할 여지가 있는 경우

• Kernel 수행 중, 인터럽트 발생시
  -> 커널 수행이 완료 된 후, 인터럽트 핸들러로 넘기도록 제어하여 해결
• Process 가 System call 하여 kernel 모드로 수행중인데, context switching이 일어나는 경우
  -> 커널 모드에서 수행중인 경우 CPU preempt 를 하지 않음. 커널 모드에서 사용자모드로 돌아갈때 preempt 하도록 하여 해결
• Multi Processor 에서 Shared Memory 내의 Kernel data
  -> 위 두가지 방법처럼 단순히 접근제어만으로 해결 불가. Lock 필요
  1. 한번에 하나의 CPU 만이 커널에 들어갈수 있도록 제어 (커널 Lock)
  2.커널 내부에 있는 각 공유 데이터에 접근할때마다 그 데이터에 Lock 
  당연히 2번 방법이 좋을 것이다.

 

Critical Section Problem 임계구역 문제

다수의 프로세스가 공유 데이터를 동시에 사용하길 원할 때, 각 프로세스의 code segment 에

공유 데이터를 접근하는 code 를 critical section(임계구역) 이라고 한다.

 

임계 구역 문제를 해결을 위한 선행 조건.

•  Mutual Exclusion (상호 배제): 하나의 프로세스가 임계구역에 있을 때, 다른 모든 프로세스는 임계구역에 접근할 수 없어야한다.
•  Progress : 아무도 임계구역에 있지 않은 상태에서 한 프로세스가 임계 구역에 접근하고자 하면, 접근할 수 있어야한다.
•  Bounded Waiting (유한 대기): 프로세스가 Critical Section 에 들어가려고 요청한 후 부터 그 요청이 허용될 때 까지, 다른 프로세스가 critical section 에 접근하는 횟수에 제한이 있어야한다 (Starvation 이 해결되어야 한다.)

 

Peterson's Algoritm

 

do {
    flag[i] = true; // -> 나 임계구역에 들어가고 싶어
    turn = j; // -> 일단 턴은 너 가져..
    while (flag[j] && turn == j); // -> 너가 턴이고, 임계구역에 들어갈 의사까지 있으면 나는 대기할게
    // do critical secction
    flag[i] = false
} while(1)

flag 나 turn 하나만 사용하면, 특정 상황에서 Process 조건이 만족되지 않아 무한 대기를하여 나온 알고리즘

모든 조건을 만족하나, Busy Waiting ( 메모리와 CPU 를 계속 사용하면서 대기하는) 문제점이 있다.

 

이렇게 복잡한 방법을 사용하지 않아도, 하드웨어 적으로 Test & modifiy 를 atomic 하게 수행할 수 있도록 지원하는 경우 간단히 해결된다. (한 instruction 에서 읽고 쓰기를 모두 하면 중간에 interuppt 가 생길 일 이 없다.)

 

만약 Test&Modify 가 지원 된다면 아래와 같이 간단하게 작성할 수 있을 것이다.

boolean lock = false;

do {
 while (Test_And_Set(lock); // lock 의 atomic 이 보장된다.
 // do critical section
 lock = false;
 ...
}

 

 

Semaphore 세마포어

앞에서 소개한 임계구역 문제를 해결하기 위한 방법들을 추상화 한 것은 Semaphore 라고 한다.

 

Semaphore S

자원의 수를 나타내는 정수 타입의 변수이다.

두가지 atomic 한 연산에 의해서만 접근이 가능하다.

 

여기서 자원의 수를 활용하는 정수가 1 과 0 밖에 없는 boolean 타입을 사용하는 세마포어는 뮤텍스로 사용할 수 있다.

 

mutex

Mutual Exclusion 즉 상호배제를 달성하기 위한 동기화 혹은 락을 거는 알고리즘을 뜻한다.

Boolean 세마포어는 뮤텍스가 될 수 있고, 뮤텍스는 세마포어가 될 수는 없다.

 

Semaphore 의 atomic 연산 (Busy Wait)

• P 연산 P(S) 

while (S <= 0) do no-op; // S 가 0보다 작을때 대기
S--; // 공유 데이터를 획득하고 S(자원의 수) 를 감소 시킴

• V 연산 V(S)

S++ (공유 데이터의 반납)

 

Block & wake up (= sleep lock)

앞에서 쭉 소개했던 Busy wait 방식의 락은 비효율적이다. 그래서 Block & wake up 방식이 등장함.

 

구현 

Semaphore 를 다음과 같이 정의한다.

typedef struct 
{
    int value;
    struct process *L;
} semaphore

그리고 block() 과 wake up(P) 를 다음과 같이 정의한다.

block : 호출한 프로세스는 suspend, 프로세스의 PCB 를 세마포어에 대한 wait queue 로 보낸다.

wake up(P): block 된 프로세스 P를  깨운다. 이 프로세스의 PCB 를 ready queue 로 보낸다.

 

• P(S)

S.value--;
if (S.value < 0) 
{
    add this to S.C
    block()l
}

• V(S)

S.value++;
if (S.value <= 0) {
    remove a process P from S.L;
    wakeUp(P);
}

P(S) 를 호출하면, 세마포어의 값(= 자원의 수)를 감소시키고, 자원의 수가 음수라면, 가져올 자원이 없으므로 대기 프로세스 목록 List L에 등록한 후 Block() 시킨다.

V(S) 를 호출하면, 자원의 수를 증가시키고, 자원의 수를 증가 시켰음에도 0 이하라면 자원을 얻기위해 대기하는 프로세스가 있다는 뜻이므로, L에 등록된 대기하는 프로세스를 꺠운다.

 

Blocked 상태를 활용하므로, 메모리를 항상 점유하고 있는 Busy wait 보다 

critical section 의 매우 짧은 경우를 제외하면 성능이 일반적으로 좋다.