[운영체제] 06. Synchronization Tools

Race Condition

: 공유 데이터에 대한 동시 접근은 data inconsistency(불일치)를 초래할 수 있다.

Race condition

• 여러 프로세스가 공유 데이터를 동시에 접근 및 조작할 때 발생하는 상황.
• race condition을 방지하기 위해서는, concurrent processes는 반드시 동기화되어야 한다.
• 단일 프로세서 환경에서도 CPU scheduler에 의해 race condition이 발생할 수 있습니다.

Critical Section Problem

Critical section(임계 구역)

• 공유 데이터에 접근하는 코드 세그먼트.
  • 공유 데이터로 접근되는 코드 세그먼트를 말하는 듯

Critical section problem

• 한 프로세스가 critical section에서 실행 중일때, 다른 프로세스는 critical section에서 실행하지 않도록 보장해야 한다.
• 프로세스가 협력할 수 있도록 프로토콜을 설계해야 한다

Typical process Pi의 일반적인 구조

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

• Entry section
  • critical section에 들어가기 위한 권한을 요청하는 코드 세그먼트.
• Exit section
  • critical section을 나왔음을 알리는 코드 세그먼트.

---

Requisites for solution

Mutual Exclusion(상호 배제)

• 프로세스 Pi가 critical section에서 실행 중이라면, 다른 프로세스는 critical section에서 실행될 수 없다.

Progress

• 어떠한 프로세스도 critical section에서 실행되지 않고 있고, critical section에 들어가고자 하는 프로세스가 존재하면,
• 다음에 critical section에 들어갈 프로세스의 선택은 무한정 연기될 수 없습니다.

Bounded Waiting

• Staration를 방지하기 위해 time bound(시간 제한)이 존재해야 합니다.

---

Critical-Section Handling

커널이 preemptive인지 non-preemptive인지에 따라 두 가지 접근 방식이 있습니다.

• Preemptive - 커널 모드에서 실행 중일 때 프로세스의 선점을 허용합니다.
• Non-preemptive - 커널 모드를 종료할 때까지, 블록되거나 자발적으로 CPU를 양보할 때까지 실행됩니다.
  • 커널 모드에서 사실상 race condition이 없다. 중간에 중단이 어렵다

---

Peterson's Solution

두 프로세스 동기화를 위한 솔루션으로, 두 프로세스는 두 개의 변수를 공유합니다.

• int turn;
  • 누구의 차례인지 나타냅니다.
• boolean flag[2];
  • 프로세스가 critical section에 들어갈 준비가 되었는지 나타냅니다.
  • flag[i] = true는 프로세스 Pi가 준비되었음을 의미합니다.

 

 

 

Synchronization Hardware

간단한 도구 - lock

 

• Critical section 들어갈 때 요청, 나갈 때 release

최신 기계는 특수한 atomic hardware instructions을 제공한다.

• Atomic = non-interruptable
• Memory word를 test하고 set 하거나, 두 Memory word의 contents를 교환

TestAndSet instruction

• word의 contents를 원자적으로 테스트하고 수정합니다.

공유 boolean 변수 lock은 false로 초기화됩니다.

Solution

 

 

Swap instruction

• 두 단어의 값을 바꿉니다.

공유 boolean 변수 lock은 FALSE로 초기화됩니다.

 

각 프로세스는 로컬 boolean 변수 key를 가집니다.

 

Semaphore(세마포어)

Semaphore S

• 단순한 integer 변수
• 공유된 데이터에 현재 접근 가능한 Data/Thread 수

S를 수정하는 두 가지 표준 연산

• wait()와 signal()
  • 원래 P()와 V()라고 불렸습니다

 

 

Usage of semaphore

• 두 프로세스 Pi, Pj가 있고, 두 critical section A & B가 있다고 하자.
• 세마포어 변수 S는 1로 초기화된다 

 

• Binary semaphore
  • 정수 값 범위가 0과 1 사이. 즉 0과 1 만 존재
  • mutual exclusion을 제공한다
• Counting semaphore
  • 정수 값의 범위는 제한이 없는 domain에 걸쳐있을 수 있다.

Semaphore implementation

Busy waiting

• 한 프로세스가 critical section에 있을 때, 다른 프로세스는 계속해서 loop를 돌아야 합니다.
• spinlock이라고도 불립니다.
• CPU cycles를 낭비합니다.

Block and wakeup

번호표를 받고 기다리는 동안 다른 일을 한다고 생각하면 된다. 

Cf) Busy watining의 Spinlock은 번호표를 받고 loop를 돌면서 낭비를 하는 것과는 다르다.

• 각 semaphore에는 연관된 waiting queue가 있습니다.

두 가지 연산

• Block
  • P(S)를 호출한 프로세스를 중단시키고, 이 프로세스의 PCB를 semaphore S의 wait queue에 삽입합니다.
• Wakeup(P)
  • 프로세스 P의 PCB를 semaphore S의 wait queue에서 제거하고, P의 실행을 재개합니다.

block and wakeup을 사용한 semaphore 구현

P(S) {
  S.value--;
  if (S.value < 0) {
    add this process to waiting queue;
    block();
  }
}

V(S) {
  S.value++;
  if (S.value <= 0) {
    remove a process P from the waiting queue;
    wakeup(P);
  }
}

 

둘 중 어떤 것이 더 나을까?

• Busy-waiting : Context switching이 필요 없을 때, Critical section의 길이가 짧을 때 좋다
• Block-wakeup : Context switching이 필요할 때, Critial section의 길이가 길 때 좋다