[운영체제] 6. Synchronization Tools

jungizz_·2025년 4월 26일

Operating Systems

목록 보기

6/15

💡6장 목표

Critical-section problem와 해결책

전통적인 Process Synchronization 문제

Process Synchronization 해결 도구

프로세스 또는 thread는 동시에 실행될 수 있으며, 언제든지 interrupt가 발생할 수 있어 실행이 부분적으로 완료될 수 있다. 또한, 동시 실행은 공유 데이터에 대한 data inconsistency(데이터 불일치)를 초래할 수 있다. 데이터의 일관성을 유지하려면 협력 프로세스의 순차적 실행을 보장하는 메커니즘이 필요하다.

예를 들어, comsumer-producer문제를 해결하기 위해 모든 버퍼를 채운다고 생각하자. 전체 버퍼 수를 추적하기 위해 integer counter를 사용한다. 초기 counter는 0으로 설정하고, 생산자는 새로운 버퍼를 생산한 후 counter를 증가시키고, 소비자는 버퍼를 소비한 후 counter를 감소시킨다.

// producer
while (true) {
		 /* produce an item in next produced */ 
		while (counter == BUFFER_SIZE)  
				; /* do nothing */ 
		buffer[in] = next_produced; 
		in = (in + 1) % BUFFER_SIZE; 
		counter++; 
} 

// consumer
while (true) {
		 while (counter == 0) 
				; /* do nothing */ 
		next_consumed = buffer[out]; 
		out = (out + 1) % BUFFER_SIZE; 
		counter--; 
		/* consume the item in next consumed */ 
}

counter를 증감하는 과정은 machine instruction관점에서 register를 사용한 여러 과정을 거친다. 이 과정에서 순서가 보장되지 않으면, counter의 값이 일관성을 잃을 수 있다. (아래 예시는 이상적으로 5의 값을 가져야할 counter가 실행 순서에 따라 4의 값을 갖게됨) → race condition

또 다른 Race condition의 예시는 아래와 같다.

프로세스 P0과 P1이 fork()로 자식 프로세스를 생성할 때, kernel variable ‘next_available_pid’가 다음 사용가능한 pid를 나타냄
이때, mutual exclusion(상호 배제)가 없는데 fork()가 동시에 호출되면 서로 다른 프로세스에 동일한 pid가 할당될 수 있음 → Race condition
즉, 여러 개의 프로세스가 동일한 data에 접근하여 변경하고, 그 결과가 접근이 발생한 순서에 의존하는 상황을 의미

이러한 상황을 방지하기 위해 한순간에 하나의 프로세스만이 data를 변경하도록 보장해야함

Critical Section

각 프로세스는 critical section(임계 구역)이라는 민감한 segment를 가짐
한 프로세스가 critical section에 있을 때, 다른 어떤 프로세스도 그 critical section에 들어갈 수 없음 (thread도 마찬가지)
- 이러한 프로토콜을 설계하는 것이 Critical-section problem
각 프로세스는 자신의 critical section으로 진입하기 위해 허가를 요청
- 이러한 요청을 구현하는 Entry Section 코드
- critical section 뒤에는 Exit Section 코드가 존재할 수 있음
- 코드의 나머지 부분은 remainder section이라고 함
프로세스의 일반적인 구조

Condition

Critical-section problem에 대한 해결안은 아래 세 가지 조건을 충족시켜야 한다.

각 프로세스는 nonzero speed로 실행된다고 가정
n개의 프로세스 간 상대속도에 대한 가정은 없음

Mutual Exclusion (상호 배제)
- critical section의 독점권 차지
Progress (진행)
- cirtical section에 들어간 프로세스가 없는 경우, 들어가려는 프로세스를 막으면 안됨
Bounded Waiting (한정된 대기)
- critical section에 프로세스가 들어가있는 경우, 다른 프로세스가 들어가려고 할 때 대기 시간이 무한히 지연되면 안됨

Handling in OS

OS에 존재하는 critical-section은 커널이 선점형인지 비선점형인지에 따라 handling 방식이 다르다. 예를 들어, critical section이 보호되지 못하는 선점형의 경우는 Mutual Exclusion을 보장해주는 코드를 구현해야한다.

Preemptive (선점형)
- 커널 모드에서 실행 중인 프로세스가 선점되는 것을 허용
  - 우선순위가 높은 프로세스가 CPU사용권을 뺏을 수 있음
- race condition이 발생할 수 있어 신중한 설계 필요
Non-preemptive (비선점형)
- 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않음
- 커널 모드 프로세스는 커널 모드가 종료될 때까지, 블록될 때까지, 자발적으로 CPU를 양보할 때까지 실행
- 경쟁 조건에 대해 고려하지 않아도 됨

Critical-section을 보호하기 위한 여러 Solution에 대해 소개한다. 이 Solution들은 아래와 같이 분류할 수 있따.

software 기반 Peterson’s Solution
hardware 기반 Uni Processor, Memory barrier, Hardware instruction, Atomic vairable
hardware를 쉽게 사용할 수 있도록 도와주는 API Mutex Lock, Semaphore


software 기반	Peterson’s Solution
hardware 기반	Uni Processor, Memory barrier, Hardware instruction, Atomic vairable
hardware를 쉽게 사용할 수 있도록 도와주는 API	Mutex Lock, Semaphore

Peterson’s Solution

critical section problem을 해결하는 고전적인 소프트웨어 기반 해결책이다. 현대 컴퓨터 구조에서 항상 올바르게 작동한다고 보장할 수 없다.

While문을 통해 critical section을 보호하는 해결책
Load와 Store machine language instruction이 atomic이라고 가정
- 즉, 중단될 수 없는 instruction
두 프로세스는 2개의 변수를 공유
- int turn: 어떤 프로세스가 critical section에 들어갈 차례인지를 나타냄
- boolena flag[2]: 각 프로세스가 critical section에 들어갈 준비가 되었는지를 나타냄
```
   while (true){ 
  		flag[i] = true; // i프로세스가 들어갈 준비가 됨
  		turn = j; // 자신이 아닌 상태 프로세스로 설정
  		while (flag[j] && turn == j)
  					 ; /* critical section에 들어갈 수 없어 대기 */ 
  		 /* critical section */
  		 flag[i] = false;
  		 /* remainder section */
   }
```
❗turn을 상대 프로세스로 설정하는 이유: 두 프로세스가 동시에 접근하려고 하는 경우에 turn을 각자 자신으로 설정한다고 가정해보자. i가 먼저 turn을 i로 해서 critical section에 들어가려고하는데, 그 사이에 j가 turn을 j로 바꾸면 덮어씌워지면서 j가 critical section에 들어가게 된다. 늦게 온 프로세스가 들어가게 되는 불공정함이 발생하게 된다. 그래서 이를 반대로 구현해야 한다. 즉, i가 들어가려고 시작했고, j도 들어가려고 시작하면 그때 i가 들어가는 것이다.

증명: Critical section problem의 세가지 조건과 비교

Mutual exclusion
- 프로세스 Pi가 critical section에 들어가기 위해 반드시 flag[j]=false 또는 turn=i이어야 함
- 만약 flag[0]과 flag[1]이 모두 true여도, turn의 값에 따라 critical section에 동시 진입 불가능
Progress
- Pj가 들어가지 않은 flag[j] = false인 상태면 Pi가 들어갈 수 있음
Bounded waiting
- while문을 수행하는 동안 turn값을 바꾸지 않음 → 한 번은(Bounded waiting) 들어갈 수 있게 보장(Progress)

현대 컴퓨터 구조에서 올바르게 동작됨을 보장할 수 없는 이유

성능을 향상시키기 위해(optimize), 프로세스나 컴파일러는 dependencies(종속성)이 없는 operation(연산)을 reorder(재정렬)할 수 있음
이는 Single-thread 환경에서는 괜찮은데, multi-thread 환경에서는 결과에 영향(inconsistent)을 미칠 수 있음

reordered example

두 thread의 공유 데이터
```
boolean flag = false;
int x = 0;
```
thread 1 performs
```
while (!flag); 
print x;
```
thread 2 performs
```
x = 100; 
flag = true;
```
expected output
- thread 1은 flag가 true가 될 때까지 기다림
- thread 2가 x에 100을 할당한 후, flag = true로 설정
- thread 1은 while문을 빠져나와 print x
- 100이 expected output

하지만, thread 2의 operation이 재정렬 된다면?

reordered thread 2
- x에 100이 할당되기 전에 thread 1이 실행돼서 0이 출력됨 → race condition
```
flag = true;
x = 100; 
```
  이러한 문제는 두 프로세스가 동시에 critical section에 들어가도록 허락할 수 있다.

Peterson’s Solution에서도 turn과 flag 세팅 순서가 바뀌면 critical section에 동시에 들어가게 될 수도 있다.

Synchronization Hardware

Peterson’s Solution과 같은 소프트웨어 기반 해결책은 현대의 컴퓨터 구조에서 올바른 작동을 보장하지 못하며 속도가 느리다. 많은 시스템은 critical section 구현을 위한 하드웨어를 지원한다. 하드웨어를 사용하는 해결책들은 critical section을 보호하기 위해 Lock을 사용한다는 점에 기반을 둔다.

Uniprocessors

single processor환경에서는 공유 변수가 변경되는 동안 interrupt 발생을 허용하지 않음으로써 해결한다.

Uniprocessors: critical section을 수행 중인 경우, interrupts를 비활성화하여 현재 실행 중인 코드가 중단되지 않도록 한다. cs 실행이 끝나면 다시 interrupt를 활성화한다.
- 이는 preemption(선점)을 방지하여 critical section내에서의 안전성을 보장 → Nonpressmptive kernel이 사용하는 방법
- 하지만 multiprocessor 시스템에서는 비효율적

하드웨어 지원에는 Memory barriers, Hardware instructions, Atomic variables의 세가지 형태가 존재한다.

Memory barriers

Memory model
- Strongly ordered: 한 프로세스의 수정이 다른 모든 프로세스에 즉시 알려지게하는 모델 → 성능에 영향
- Weakly ordered: 한 프로세스의 수정이 다른 모든 프로세스에 즉시 알려지지 않는 모델 → 필요할 때 알림
Memory barriers는 Weakly ordered 모델을 사용
- memory_barrier()라는 명령어를 사용할 때 메모리의 변화를 모든 다른 프로세스에게 알림
- 이를 통해 성능에 덜 영향을 미치면서 메모리 연산의 순서를 보장함 → 다른 프로세스가 메모리의 상태를 일관되게 유지할 수 있도록 함

ex) 100 출력을 보장하는 thread 1

thread 1 performs

while (!flag)
		memory_barrier();
print x;

thread 2 performs

x = 100;
memory_barrier(); // reorder 방지
flag = true;

Hardware instructions

특정 atomic 하드웨어 명령을 사용하여 control section 접근 제어
- Test-and-Set(읽고 쓰기) instrction, Compare-and-Swap(비교하고 바꾸기) instrction
- 이 instrction은 아래 Definition의 일을 수행하는 건 맞는데, 함수는 아니고 CPU에서 지원하는 Atomic Machine instruction 자체 (Definition은 무슨 일을 하는지 보여주려고 적은 것 뿐~)

Test-and-Set

특정 변수의 값을 읽고, 그 값을 수정하는 Atomic 작업 수행
Definition
```
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}
```
- Atomic하게 실행
- 전달된 매개변수의 원래 값을 반환
- 전달된 매개변수의 새로운 값을 true로 설정
Solution
- 공유 변수: boolean lock (초기값은 false)
```
  do {
      while (test_and_set(&lock)) 
          ; /* do nothing */ 
      /* critical section */ 
      lock = false; 
      /* remainder section */ 
  } while (true);
```
lock이 false이면 잠겨있지 않아서 critical section에 들어갈 수 있음을 의미한다. test_and_set에서는 false를 반환하고 lock의 값을 true로 바꿔 잠군다. while 루프에서 나와 critical section을 수행하고 난 뒤에는 lock을 false로 바꿔 잠금을 해제한다. critical section에 들어올 수 있는 상태로 만든다.

Compare-and-Swap

Definition

int compare_and_swap(int *value, int expected, int new_value) { 
    int temp = *value; 
    if (*value == expected) 
        *value = new_value; 
    return temp; 
}

Atomic하게 실행
전달된 매개변수의 원래 값을 반환
*value가 expected와 같을 때만 value를 new_value로 설정 → 즉, 이 조건을 만족할 때만 교환 발생

Solution 1
- 공유 변수: int lock (초기값은 0)
```
  while (true) {
      while (compare_and_swap(&lock, 0, 1) != 0) 
          ; /* do nothing */ 
      /* critical section */ 
      lock = 0; 
      /* remainder section */ 
  }
```
lock이 0이면 잠겨있지 않아서 critical section에 들어갈 수 있음을 의미한다. compare_and_swap에서는 0을 반환하고, *value(0)가 expected(0)과 동일하므로 value(0)를 new_value(1)로 설정한다. 즉, lock이 잠겨있지 않음을 확인하고, 1로 바꿔 잠구는 과정이다. while 루프에서 나와 critical section을 수행하고 난 뒤에는 lock을 다시 0으로 설정하여 잠금을 해제한다.
이 알고리즘은 Mutual Exclusion 조건은 만족하지만, Bounded Waiting을 만족하지 못한다…. 프로세스가 3개라면 p1이 cs를 탈출한 뒤 p2와 p3 중 어떤것을 선택할지 보장할 수 없기 때문이다.. 이를 만족시키기 위해 아래와 같은 알고리즘을 사용할 수 있다.
Solution 2: Bounded-waiting Mutual Exclusion(유한 대기 상호 배제)
- 공유변수: boolean waiting[n], lock (초기값은 false)
- 여러 노드(프로세스 혹은 쓰레드)들이 있을 때, 우선순위가 낮아서 CPU scheduling을 못받은 노드도 고려해주기 위해 공평하게 번갈아가면서 사용권을 가질 수 있도록 한다.
```
  while (true) {
      waiting[i] = true;
      key = 1;
      while (waiting[i] && key == 1) 
          key = compare_and_swap(&lock, 0, 1); 
      waiting[i] = false; 
      /* critical section */ 
      j = (i + 1) % n; 
      while ((j != i) && !waiting[j]) 
          j = (j + 1) % n; 
      if (j == i) 
          lock = 0; 
      else 
          waiting[j] = false; 
      /* remainder section */ 
  }
```
첫 while문에 들어온 경우 critical section에 들어가려고 시도하는 것이므로 waiting을 true로 설정한다. 그러면 다음 while문에 들어가게 되고, lock이 false인 상태로 compare_and_swap을 호출한다. false가 반환되어 key는 0이 돼서 critical section에 들어오지 못하도록 잠기고, lock은 true로 바뀐다. 이제 들어온 프로세스는 기다리는 상황도 아니니까 waiting도 false로 바꾸고, critical section을 수행한다.

Pi가 critical section을 수행하고 나오면 i+1해서 j를 만든다. j에게 우선권을 주며 Pj가 waiting상태인지 확인한다. waiting상태가 아니라면 j+1해서 또 다음 노드로 넘어가 우선권을 준다. Pj가 waiting상태라면 lock을 false로 해서 잠금을 해제하고, waiting[j]를 false로 바꾸며 critical section에 들어갈 수 있도록 해준다.

결국 프로세스는 Lock==0&& waiting[i]==true && thread[i-1]이 cs를 나온 경우에 들어갈 수 있다는 것이다.

Atomic variables

int, boolean과 같은 data type에게 atomic한 업데이트를 보장한다. (중단되지 않는다)
ex) atomic variable ‘sequence'를 사용해서 ‘increment(&sequence)’ 명령어를 실행하는 경우
- compare_and_swap에서 v가 temp와 달라졌다는 것은, 또 다른 프로세스가 이에 접근하여 v를 증가시켰다는 것이다. 그럼 현재 프로세스는 v를 증가시킬 필요가 없고, 다시 temp에 v를 담아서 compare_and_swap을 실행한다. 즉, 다른 프로세스가 v를 증가시키지 않은 상태임을 확인하고 v를 증가시키는 것이다.
```
  void increment(atomic_int *v)
   {
  		 int temp;
  		 do {
  				 temp = *v;
  		 }
  		 while (temp != (compare_and_swap(v,temp,temp+1));
   } 
```

위의 하드웨어 기반 해결책은 복잡한 형태를 가진다. 이를 프로그래머가 쉽게 사용할 수 있도록 간단한 API들이 개발되었으며, 대표적으로 Mutex Lock과 Semaphore가 있다.

Mutex Locks

critical section을 보호하기 위해 acquire()로 lock을 얻고, relase()로 lock을 해제한다.
- boolean acailable 변수가 lock의 상태를 나타낸다.

acquire()과 release() 호출은 atomic해야한다.

compare-and-swap과 같은 하드웨어 atomic instruction으로 구현된다.

  while (true) { 
  	acquire lock 
  	/* critical section */ 
  	release lock 
  	/* remainder section */ 
  } 
  
  acquire() {
  		 while (!available) 
  				; /* busy wait */ 
  		available = false;
  } 
  
  release() { 
  		available = true; 
  }

하지만, Busy waiting을 해야한다는 단점을 가진다. 이는 한 프로세스가 critical section에 있는 동안 다른 프로세스들은 acquire()로 lock을 얻기 위해 계속해서 반복문을 호출한다(CPU사용권을 놓지 않음). lock이 풀리길 기다리며 계속 회전하므로 spinlock이라고도 부른다. 이는 multiprogramming system에서 CPU사이클을 낭비하게 만든다.

그러나, 이는 lock을 기다리는동안 시간을 소모하는 context switch를 전혀 필요로 하지 않는다는 장점을 가져다주기도 한다. 그래서 프로세스들이 짧은 시간 동안만 lock을 소유할 것이라고 예상되면, spinlock이 적절할 수 있다.

Semaphore

Mutex lock보다 더 정교한 방법을 제공하는 동기화 도구이다.

interger 변수로 정의된 Semaphore S

Semaphore는 오직 wait()와 signal()을 통해 접근할 수 있다. (atomic operation)

  wait(S) { 
  		while (S <= 0)
  				 ; // busy wait
  		 S--; // 자원을 하나 사용하겠다
   }
  
   signal(S) { 
  		S++; // 자원 사용을 끝마쳤다
   }

Semaphore에는 2가지 종류가 존재한다.
- Counting semaphore: 제한 없는 domain을 가지는 integer 값
- Binary semaphore: 0과 1의 값을 가지는 interager 값 (Mutex lock과 유사)

example of counting semaphore

프로세스 P1의 작업 S1이 P2의 S2보다 먼저 수행되어야 하는 문제
- critical section 뿐만 아니라, 작업 순서의 보장을 필요로하는 경우에도 사용 가능

semaphore ‘synch’를 만들고 초기값을 0으로 설정한다.

P1:
	 S1;
	 signal(synch);
	 // 작업 S1을 수행하고 semaphore를 증가하여 P2를 깨움(interrupt처럼)
 
P2:
	 wait(synch);
	 S2;
	 // signal interrupt 대기하다가 신호가 오면 작업 S2를 수행

signal()과 wait()두 함수는 동시에 두 개의 프로세스가 실행할 수 없도록 보장해야한다. 이를 위해 두 함수는 critical section 내에서 실행되어야 한다. 하지만, 이는 Busy waiting을 하게 만든다. 다른 프로세스가 이미 critical section에 있을 경우 계속 기다려야한다.

그래도 두 함수 구현 코드 자체가 짧아서 busy waiting 시간이 짧을 수 있다. 그러나 critical section이 자주 차지되는 경우는 application은 많은 시간을 기다리게되고 CPU 사용권을 놓지 않아 성능 저하가 발생할 수 있다.

이를 해결하기 위해 아래와 같은 방법을 고려한다.

Semaphore implementation with no Busy waiting

각 semaphore를 waiting queue에 담아 busy waiting과정을 없앤다.
- waiting queue는 정수형 value와 다음 항목을 가리키는 pointer를 가진다.
- 이를 구현하기 위해 semaphore의 구조는 아래와 같이 구현된다.
```
typedef struct {
    int value;              // 세마포어의 현재 값
    struct process *list;   // 대기 큐의 첫 번째 프로세스를 가리키는 포인터
} semaphore;
```

두 가지 주요 연산:

block: wait()함수가 호출될 때, 해당 프로세스를 적절한 waiting queue에 추가

wakeup: signal()함수가 호출될 때, waiting queue에서 프로세스를 빼고 ready queue로 옮긴다.

 wait(semaphore *S) {
     S->value--;  // 세마포어의 값을 감소시킴 (자원 사용)
     if (S->value < 0) { // 사용할 자원이 없으면(크리티컬 섹션에 들어갈 수 없으면)
         add this process to S->list;  // 대기 큐에 현재 프로세스를 추가
         block();  // 프로세스를 블록 상태로 전환
     }
 }
 
 signal(semaphore *S) {
     S->value++;  // 세마포어의 값을 증가시킴 (자원 반납)
     if (S->value <= 0) { // 반납해도 음수라는 것은 기다리는 애들이 있다는 것(크리티컬 섹션에 들어가고 싶은 애들이 있음)
         remove a process P from S->list;  // 대기 큐에서 프로세스를 제거
         wakeup(P);  // 제거한 프로세스를 준비 큐로 옮김
     }
 }

semaphore와 같은 동기화 도구를 잘못 사용하면 여러가지 문제를 초래할 수 있다.

// 1. 잘못된 순서로 Semaphore 연산 사용
signal(mutex);
. . .
wait(mutex);

// 2. 중복 호출
wait(mutex);
. . .
wait(mutex);

// 3. 생략
wait(mutex); 
. . .
//signal(mutex) -> 생략

Monitors

middleware(complier)가 제공하는 동기화 메커니즘
한 번에 하나의 프로세스만 모니터에 들어갈 수 있다
critical section 보호하는 것 이외에도 특정 조건을 기다리는 것도 가능하다 (ex-버퍼에 자리가 날 때까지 기다림)
- x.wait(): x.signal()이 호출될 때까지 기다림
- x.signal(): x.wait()를 호출한 프로세스 중 하나를 깨운다.
  - 이때, 우선순위에 따라 깨울 프로세스를 결정
만약 프로세스 P는 x.signal()로 특정 컨디션에 깨우고, 프로세스 Q는 x.wait()로 특정 컨디션을 기다린다면, P가 Q에게 신호를 주는 셈이다.
- 이때, P가 Q를 깨우고 Q가 모니터 코드를 실행하면 signal and wait
- P가 Q를 꺠우고 P가 모니터 코드를 실행하면 signal and continue

세마포를 사용해서 monitor를 구현하면 아래와 같다.

1. F함수 보호

2. 조건 변수 사용 (뭘 깨우고 어떤걸 기다리는지~)

단일 리소스를 경쟁하는 경우, 프로세스가 리소스를 사용할 최대 시간을 지정할 수 있다. (Single resource allocation)

Liveness

보통 동기화 프로그램은 ‘기다리고-깨우고’하는 형태이다. 이때, 프로그램이 계속 실행되기 위해서 무한정 기다리는 상황이 발생하면 안된다. → Liveness failure

Deadlock: 두 개 이상의 프로세스가 서로를 기다리는 상황으로 프로세스가 진행되지 않는다.
Starvation: 우선순위가 낮은 프로세스가 계속 기다리는 상황
Priority Inversion: 우선순위 역전
- 낮은 우선순위가 특정 리소스를 점유하고 있고, 높은 우선순위가 그 리소스를 원해서 기다리고 있다. 그때, 그 리소스가 필요없는 중간 우선순위가 CPU를 할당받아버리는 경우 → 높은 우선순위는 낮은 우선순위한테 리소스도 밀리고, 중간 우선순위한테 CPU할당도 밀림
- 리소스로 인해 문제가 발생한 경우, 낮은 우선순위는 리소스를 해제하지 않고 / 기다리는 프로세스 중 가장 높은 우선순위의 프로세스를 상속받아 / 리소스를 사용하여 프로세스를 수행하는 Priority-inheritance protocol로 해결할 수 있다.

jungizz_

( •̀ .̫ •́ )✧

이전 포스트

[운영체제] 5. CPU Scheduling

다음 포스트