11. Process Synchronization 2

이화여자대학교 반효경 교수님의 운영체제 강의 12강을 듣고 정리한 내용이다.

 

✏️ Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 $P_0, P_1$
• 프로세스들의 일반적인 구조

do {
    entry section
    critical section
    exit section
    remainder section
} while(1);

• critical section - 공유데이터를 접근하는 구역
• entry section을 통해 다른 데이터들이 critical section이 실행되는 동안 접근하지 못하도록 막음(lock)

📌 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다. → Synchronization Variable

---

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

Mutual Exclusion (상호 배제)

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

Progress

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

Bounded Waiting (유한 대기)

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

 

📌 가정

• 모든 프로세스의 수행 속도는 0보다 크다
• 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

---

✏️ Algorithm 1

• Synchronization variable
  • $P_i$ can enter its critical section if (turn == i)
  • initially turn = 0; = 프로세스가 몇 번 들어갈 수 있는지 알려줌

int turn;
initially turn = 0;

• Process $P_0$
  • turn 변수가 0이 아닌 동안 while문을 계속 돌면서 자기 차례를 기다림

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

• Satisfies mutual exclusion, but not progress (즉, 과잉양보 : 반드시 한번씩 교대로 들어가야만 함. swap-turn. 그가 turn을 내 값으로 바꿔줘야만 내가 들어갈 수 있음. 특정 프로세스가 더 빈번히 critical section을 들어가야 한다면?)

---

✏️ Algorithm 2

• Synchronization variable
  • boolean flag[2];  /* 프로세스는 각각 자신의 플래그를 가지고 있으며, critical section에 들어가고자 하는 의중을 표시 */
  • initially flag[모두] = false;   /* no one is in CS */
  • "$P_i$ ready to enter its critical section" if (flag[i] == true)
• Process $P_i$

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);

• Satisfies mutual exclusion, but not progress requirement
• 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능

---

✏️ Algorithm 3 (Peterson's Algorithm)

• Combined synchronization variables of algorithms 1 and 2.
• Process $P_i$

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

• Meets all three requirements; Solves the critical section problem for two processes.
• Busy Waiting!(=spin lock) (계속 CPU와 Memory를 쓰면서 wait); 비효율적 방법

---

✏️ Synchronization Hardware

하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우, 앞의 문제는 간단히 해결

• Mutual Exclusion with Test & Set
  • Synchronization variable: boolean lock = false;
• Process $P_i$

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

📌Test_and_Set() 함수는 매개 변수를 읽어내고, 그 변수를 1(또는 0)로 바꿔 주는 역할을 한다.