5주차. 프로세스 동기화 (2) - Critical Section Problem & Sloving Algorithm

Critical Section이란?

공유자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역

Critical-Section Problem

n개의 프로세스가 공유 데이터를 동시에 접근하려는 경우 프로세스의 code Segment에는 공유 데이터를 접근하는 코드인 Critical-Section이 존재한다.

• 하나의 프로세스가 Critical Section에 있을 때, 다른 모든 프로세스는 Critical Section에 들어갈 수 없어야 한다.

X는 공유데이터, X에 대한 연산이 Critical Section

프로세스의 일반적인 구조

do {
    entry section; // Critical Section으로 들어감
    ~
    Critical Section;
    ~
    exit section; // Critical Section에서 나옴
    remainder section;
} while(1);

• Critical Section에 들어갈 때 entry section, 나올 때 exit section으로 명시
• 두개의 프로세스가 있다고 가정하자 : P0, P1
• 프로세스들은 수행의 동기화를 위해 몇가지 변수를 공유할 수 있다.

문제 해결을 위한 조건

Mutual Exclusion (상호배제)

• 프로세스 P(i)가 critical section을 수행하는 중이라면 다른 모든 프로세스는 해당 critical section에 들어가면 안된다.

Progress (진행)

• 아무도 critical section에 들어가 있지 않은 상황이라면 들어가고자 하는 P(i)는 들어갈 수 있어야 한다.

Bounded Wating (한정대기)

• 프로세스가 critical section에 들어가려고 요청하고, 허용될 때까지 대기하는 동안 다른 프로세스가 critical section에 들어가는 횟수에 한계가 있어야한다.

 

Sovle Algorithm 1 (Turn 사용)

int turn;
initially turn = 0; // P(i)는 turn == i 인 경우에 수행 가능하다.

// Process P(0)
do {
    while(turn != 0); // turn이 자신의 번호가 아닐 때 까지 대기함
    CRITICAL_SECTION;
    trun = 1; // turn을 상대 프로세스 번호로 변경
    remainder section;
} while(1);

// Process P(1)
do {
    while(turn != 1);
    CRITICAL_SECTION;
    turn = 0;
    remainder section;
}

로직

1. P(1) 프로세스가 수행을 마치면 "turn = 0"으로 바꿔준다.
2. 0번 프로세스는 while문을 탈출하고 다음 코드인 Critical Section부분을 수행한다.
3. 0번 프로세스가 수행을 마치고 나오면서 다시 "turn = 1"로 변경하게된다.
4. 똑같이 1번프로세스는 while문을 탈출하고, 0번 프로세스는 entry section 루프문에서 기다리게 된다.

문제점 (Progress 문제)

• 프로세스간 critical section 수행횟수에 차이가 있다면 한쪽이 영원히 못들어가는 현상이 발생한다. 반드시 교대로 들어가야 서로가 들어갈 수 있는 구조이다.
  만약 P(0) 프로세스는 1회, P(1) 프로세스는 100회 들어가려고 하는 상황일 경우에 P(0) 프로세스가 1번 프로세스로 turn을 넘겨주고 P(1) 프로세스가 수행 후 다시 P(0) 프로세스로 넘겨주고 기다리는데, P(0) 프로세스는 더이상 수행을 원치 않아서 critical section에 더이상 들어가지 않는다면 1번 프로세스는 turn을 받지 못해서 계속 기다리는 상황이 나오게 된다.

 

Solve Algorithm 2 (Flag 사용)

boolean flag[2]; // 자신이 Critical Section에 들어가겠다는 여부를 담은 값
initially flag[모두] = false; // P(i)는 flag[i] == ture 인 경우에 수행 가능

// Process P(i)
do {
   flag[i] = true; // P(i) : critical section 수행할게요 ~
   while(flag[j]); // if P(j) Running: wating
   CRITICAL_SECTION;
   falg[i] = false; // P(i) : critical section 수행종료!
   remainder section;
} while(true);

로직

1. P(i) 프로세스는 critical section에 들어가고자 하면 먼저 "flag[i] = true"로 변경하고,
   P(j) 프로세스가 critical section에 들어가고자 하는지 확인한다.
2. 만약 "flag[j] == true"라면 P(i)는 기다리다가 P(j) 프로세스가 수행 후 flag[j]를 false로 바꾸면 그때 P(i) 프로세스가 들어가서 수행하게된다.

문제점 (Bounded Wating 문제)

• 둘다 깃발을 드는 상황이 발생하면 끊임없이 양보만하면서 대기하는 상황이 나올수 있다.
  • P(I) 프로세스가 "FLAG[i] = TRUE"를 수행하고 CPU를 뺏긴다.
  • P(J) 프로세스가 실행 되어 "FLAG[j] = TURE"를 한다.
  • P(I) 프로세스는 P(J)의 깃발을 보고 자신의 깃발만 들고 코드 실행을 하지 못하게 된다.
    즉, 둘다 들어가지 못하고 깃발만 들게 되는 상황이 나오게 된다. CPU가 i, j 누구에게 가더라도 해결되지 못한다.

 

Solve Algorithm 3 - Perterson's Algorithm (피터슨 알고리즘, Turn & Flag 사용)

• Algorithm 1, 2 방식을 합친 방법.

int turn;			// 자신이 수행할 때 상대방에게 턴을 준다.
boolean[] flag;		// 자신이 수행할것이라는 여부를 표시한다.

// Process(i)
do {
    flag[i] = true; // 프로세스 I : 나 Critical Section 들어갈게요!
    turn = j;		// 프로세스 J에게 turn을 줌.
    while (flag[j] && turn == j); // J 프로세스의 깃발이 올라가 있고 && turn도 J차례인 경우 대기
    CRITICAL_SECTION;
    flag[i] = false; // 프로세스 I : 나 Critical Section 끝났어
    remainder section;
} while(true);

// Process (j)
do {
    flag[j] = true; // 프로세스 J : 나 Critical Section 들어갈게요!
    turn = i;		// 프로세스 I에게 turn을 줌.
    while (flag[i] && turn == i); // I 프로세스의 깃발이 올라가 있고 && turn도 I차례인 경우 대기
    CRITICAL_SECTION;
    flag[j] = false; // 프로세스 J : 나 Critical Section 끝났어
    remainder section;
} while(true);

// 프로세스 I가 flag[i] = true만 수행하고 종료될 경우 흐름
process I : flag[i] = true 수행, 인터럽트
process J : flag[j] = true, turn = i 수행, while (flag[i] && turn == i) 대기, 타이머 인터럽트 (Busy Wating)
process I : turn = j 수행, while (flag[j] = true && turn == j) 대기, 타이머 인터럽트 (Busy Wating)
process J : while (flag[i] = true && turn == i) 조건문 탈출, TURN == J 이므로. Ciritical Section 수행

로직

→ P(i) 프로세스가 들어가고자 하는 경우

1. 먼저 flag[i] == true로 변경하여 들어가고자하는 의사표시를 한다.
2. turn = j로 turn을 다음 프로세스로 바꿔준다.
3. 다음 프로세스 j가 들어가고자하는 의사표시를 했고 && turn이 j차례 인 경우 j프로세스가 critical section을 수행 후 나올 때까지 기다린다.
4. j 프로세스가 수행을 마쳤다면 flag[j] = false로 바꿔준다.
5. 프로세스 i는 while문을 탈출 후 critical section을 수행하러 가게 된다. i 프로세스도 수행을 마치면 flag[i]를 false로 변경한다.

즉, 상대방이 의사표시도 했고, 차례도 상대방의 차례인 경우에만 대기해주고, 아니라면 자신이 들어가서 수행을 진행하게 된다. 만약 자신이 수행 후 turn이 상대방으로 바뀌더라도 상대방이 더이상 한다는 의사표시가 없다면 조건 두개 다 충족되는 것이 아니므로 자신이 수행할 수 있게 된다. 따라서 끊임없는 양보 상황이 발생하지 않는다. (progress 문제 해결)

 

문제점

• Busy Wating (= spin lock)의 문제점이 있다.
• 상대 프로세스가 critical section을 수행중에 cpu를 쫒겨나게 되어 상대방 프로세스가 cpu에 오더라도 while 조건문이 참이므로 계속 루프를 돌면서 대기하게된다.
  이때 아무리 루프를 돌아도 값의 변화는 없으므로 쓸데없이 cpu 시간만 잡아먹으면서 대기한다는 단점이 있다.
• 이것을 해결방법으로는 sleep & wakeup 방식이 있다.

 

Synchronization Hardware

위와같이 복잡한 조건이 필요로하는 이유는 CPU가 하나의 instruction을 수행하다가 언제든지 점유한 CPU를 뺏길수 있기 때문이다.
어떤 명령을 수행중에 뺏겼더라도 다시 정상적인 수행이 가능하도록 하기 위한 것.

 

만약 하드웨어적으로 Atomic하게 (분할되지 않고 동시적으로) Text & Modify가 가능하다면 (동시에 읽고 쓰는 것이 가능하다면) 문제는 쉽게 해결된다.

 

Atomic한 수행

boolean A;
TestAndSet(A)
{
	1. READ -> A;
	2. TURE -> A;
}
// TestAndSet을 Atomic하게 수행

a를 읽고 → True로 쓰기 (를 하나의 instruction으로 수행)

 

Atomic한 TestAndSet(LOCK)을 이용하여 Ciritcal Section 문제 해결

//Synchronization variable
boolean lock = false;

TestAndSet(lock):
  if lock:
      lock = true;
      return true;
  else // unlock
      lock = true;
      return false;

// Process P(i)
do {
    while(TestAndSet(lock)); // lock이 True인지 확인 후 True로 변경.
    CRITICAL_SECTION;
    lock = false; // unlock
    remainder_section;
} while(true);

1. if (lock == true) → while문 내에서 lock에 true를 쓰기를 반복하며 대기한다. 이때는 다른 프로세스가 critical section을 수행중.
2. critical section을 수행하고 나오면 lock = flase로 변경해준다.
3. TestAndSet(lock)은 false가 되어, while문에 갇혀 대기중인 프로세스는 탈출하게 되고, 동시에 lock = true 로 변경한다.
   그렇게 critical section에 들어가서 수행하게 된다.