[OS] Synchronization과 Critical-Section Problem

🔍 Background

process synchronization이 필요한 이유!

❗️ 다수의 프로세스/스레드가 공유 데이터에 동시(concurency -> single core), 병렬(parallel -> multicore) 접근으로 인한 데이터 불일치(inconsistency)가 발생할 수 있다.

 

Example - Producer-Consumer problem

• Producer: 데이터 생성 스레드
• Consumer: 데이터 소비 스레드

👉 이 두 스레드는 같은 데이터를 생산하고 소비하는 스레드이기 때문에 반드시 동기화되어야 한다!!!

두 thread가 각각 이러한 코드를 가지고 있다고 생각해보자.

global variable로 선언되어 있는 counter 변수는 두 thread가 공유하는 변수이다.

그리고 이 counter 변수를 사용하는 counter++, counter--를 assembly code로 나타내면 아래와 같다.

Assembly code

counter++;
=>
register1 = counter
register1 = register1 + 1
counter = register1

counter--;
=>
register2 = counter
register2 = register2 - 1
counter = register2

counter 변수가 5로 초기화되어 있고, 두 코드가 실행된다고 가정을 해보자.

우리는 아래와 같이 producer의 counter++이 먼저 실행되고 consumer의 counter--가 이후에 실행되어 최종 counter 값은 5가 된다고 생각할 수 있다.

T0: producer execute register1 = counter (register1 = 5)
T1: producer execute register1 = register1 + 1 (register1 = 6)
T2: producer execute counter = register1 (counter = 6)
T3: consumer execute register2 = counter (register2 = 6)
T4: consumer execute register2 = register2 - 1 (register2 = 5)
T5: consumer execute counter = register2 (counter = 5)

하지만 interrupt는 언제든지 일어날 수 있기 때문에 다음과 같이 producer와 consumer의 instruction 뒤죽박죽 실행될 수 있다.

T0: producer execute register1 = counter (register1 = 5)
T1: producer execute register1 = register1 + 1 (register1 = 6)
T3: consumer execute register2 = counter (register2 = 5)
T4: consumer execute register2 = register2 - 1 (register2 = 4)
T2: producer execute counter = register1 (counter = 6)
T5: consumer execute counter = register2 (counter = 4)

위와 같이 실행된다면 최종 counter 값은 4가 된다.

👉 이렇게 다수의 스레드가 공유 데이터(counter)에 동시/병렬 접근함으로써 데이터 불일치가 발생하게 된다.

👉 이를 race condition이라고 부른다.

race condition이란??

여러 프로세스가 동일한 데이터에 동시에 액세스하고 조작해 실행 결과가 액세스가 발생하는 특정 순서에 따라 달라지는 것
👉 race condition을 막기 위해서는 동시에 데이터에 접근하는 프로세스(concurrent process)를 동기화해야 한다.

---

🔍 Critical Section Problem

Critical section이란?

각 프로세스가 가지고 있는 공유 리소스에 접근하는 코드를 말한다.

Critical section은 반드시 한 프로세스만 실행되어야 한다.

critical section problem이란?

프로세스들이 협력해서 리소스를 사용할 수 있도록 프로토콜을 설계하는 것!

👉 race condition이 발생하지 않도록 설계하는 것!

 

Critical section의 기본 조건

1. Mutual Exclusion

어떤 프로세스가 Critical section을 실행 중이라면, 다른 프로세스는 Critical section을 실행할 수 없다!

2. Progress

어떠한 프로세스도 critical section을 실행하지 않고, critical section을 실행하려는 프로세스가 있다면, 다음 critical section을 실행하는 프로세스가 무기한 연기되어선 안 된다!

👉 deadlock 방지

3. Bounded Waiting

각 프로세스는 유한한 횟수의 시도 후에 critical section에 들어갈 수 있어야 한다.

👉 starvation 방지

---

다음 포스팅에서 Critical Section Problem의 Solution에 대해 알아보겠습니다 😁