[OS] Chapter 6 : Process Synchronization

Background

 

공유 데이터에 대한 동시 접근은 데이터 불일치를 일으킬 수 있다 -> 데이터를 수정하는 과정에서 문제가 된다. 

 

데이터 일관성을 유지하기 위해서는 협력 프로세스(데이터를 공유하고 있는 프로세스)의 순차적 실행을 보장하는 메커니즘이 필요하다.

 

 

Producer-Consumer 문제를 가정한다. 

• 정수 count는 버퍼 안에 있는 항목의 수를 추적
  처음에 count는 0으로 설정
  생산자(Producer)에 의해 증가
  소비자(Consumer)에 의해 감소

 

Code for Producer

 

 

while (true) {
 /* produce an item and put in nextProduced */
while (count == BUFFER_SIZE) ; // do nothing
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++; // critical section 
}

 

Code for Consumer

 

 

while (1) {
while (count == 0) ; // do nothing
nextConsumed = buffer[out]; // 데이터를 꺼내간다 (내용이 바뀌는 건 아니다)
out = (out + 1) % BUFFER_SIZE; 
count--; // critical secton 
 /* consume the item in nextConsumed */
}

 

Race Condition

 

count++는 다음과 같이 구현될 수 있습니다:

 

• register1 = count
  register1 = register1 + 1
  count = register1

count--는 다음과 같이 구현될 수 있습니다:

 

• register2 = count
  register2 = register2 - 1
  count = register2

 

이때 명령어가 완결되기 전에 context switch가 일어나면 오류가 난다. 

그것을 해결하기 위해서 race condition이 나온다. 

 

 

 

 

Race condition 

 

• 여러 프로세스가 동시에 동일한(즉, 공유된) 데이터에 접근하고 조작하는 상황
• 실행 결과가 액세스 순서에 따라 다르게 나타날 수 있는 상황
• 경쟁 상태(Race Condition)는 다양한 시스템 구성 요소가 리소스를 조작하면서 운영 체제에서 빈번하게 발생한다, 
  
  
  

* interrupt 기반으로 함수들이 실행된다 따라서 두 함수가 접근해서 내용을 바꾸는 경우가 일어날 수도 있다 

 

• 다중 스레드 애플리케이션을 개발할 때 주의가 필요합니다.
  
  이러한 애플리케이션은 데이터를 공유하고 있을 가능성이 매우 높다.
  다중 스레드는 멀티코어 시스템의 서로 다른 코어에서 병렬로 실행될 수 있다.

이것은 멀티스레드 환경에서 데이터 무결성과 동기화에 대한 중요성을 강조하며, 데이터 무결성을 위반하는 경쟁 상태나 다른 문제를 방지하기 위해 주의 깊게 고려해야한다.

 

 

 

Critical Section

임계 구역이라고도 말함 

공유 데이터를 수정하는 코드 세그먼트 (예: 공통 변수, 테이블, 파일 등)

공유하는 데이터의 값을 변경하고 수정하는 부분을 말한다 (읽어오는 건 아니다)

코드에서 데이터의 내용을 바꾸는 코드가 들어있으면 그 부분이 critical section이 된다.

 

한 프로세스가 임계 영역(critical section)에서 실행 중일 때, 다른 프로세스는 임계 영역에서 실행되지 않도록 허용되지 않아야 한다.

각 프로세스는 임계 영역에 진입하기 위한 허가를 요청해야한다. 

 

Solution to Critical Section Problem

 

상호배타(Mutual Exclusion):

프로세스 Pi가 임계 영역에서 실행 중이면 다른 프로세스들은 그들의 임계 영역에서 실행되지 않아야 한다.

 

진행(Progress):

 임계영역에서 작업 중인 프로세스가 없다면, 임계영역에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다. 


한정 대기(Bounded Waiting):

프로세스가 임계 영역에 들어가려고 요청을 한 후, 그 요청이 승인되기 전에 다른 프로세스가 임계 영역에 들어가는 횟수에 대한 제한이 있어야한다. 

 

Peterson’s Solution

 

이 두 프로세스 솔루션에서, 두 프로세스는 두 개의 변수를 공유한다:

int turn: 누가 임계 영역에 들어가는 차례인지를 나타낸다.
boolean flag[2]: flag 배열은 프로세스가 임계 영역에 들어갈 준비가 되었는지를 나타낸다.

 

flag[i] = true: 프로세스 Pi가 준비가 되었다는 것을 나타낸다.

 

Code for Producer

while (true) {
 /* produce an item and put in nextProduced */
while (count == BUFFER_SIZE) ; // do nothing
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
 flag[i] = true; // entry 
 turn = j;// entry
 while (flag[j] && turn == j);// entry
count++; // critical 
 flag[i] = false; // exit 
}

Code for Consumer

 

while (1) {
while (count == 0) ; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
 flag[j] = true; //entry 
 turn = i;//entry 
 while (flag[i] && turn == i);//entry 
count--;//critical 
 flag[j] = false; //exit 
 /* consume the item in nextConsumed */
}

 

피터슨(Peterson)의 해결책은 다음 요구 사항을 충족시킨다

상호 배타(Mutual Exclusion): Pi가 임계 영역에서 실행 중일 때 Pj는 Pi가 임계 영역에서 나올 때까지 기다려야 한다. (중요)

Pi는 Pj가 지난번에 진입했다면 이번에는 자기도 한 번은(따라서 대기 시간이 한없이 길어지지 않음) 들어갈 수 있게(progess 보장) 된다. 

 

 

Synchronization Hardware

현대의 기계는 특수한 원자적(atomic) 하드웨어 명령어를 제공한다. 원자적이란 인터럽트가 발생하지 않는 것을 의미한다

TestAndSet 명령어: 메모리 워드를 테스트하고 값을 설정하는 명령어
Swap 명령어: 두 개의 메모리 워드의 내용을 교환하는 명령어

 

 

TestAndSet 명령어

 bool TestAndSet(bool &target)
 {
 bool rv = target;
 target = true; // 값을 true로 바꾼다 
 return rv:
 }

Swap 명령어

 

void Swap(bool &a, bool &b)
 {
 bool temp = a;
 a = b;
 b = temp:
 }

 

 

 

TestAndSet Instruction 

 

bool TestAndSet(bool &target)
{
 bool rv = target;
 target = true;
 return rv:

}

 

이 명령은 원자적으로 실행된다.
만약 두 개의 TestAndSet 명령이 동시에 실행되면, 이들은 어떤 임의의 순서대로도 순차적으로 실행될 것이다.
제한된 대기 요구 사항이 충족되지 않는다.

 

 

Solution using TestAndSet

공유 부울 변수 lock가 false로 초기화됩니다.

 

 

lock이 false면 열려있다는 뜻, True면 잠겨있다는 뜻이다 

따라서 lock이 false일 때만 진입가능하다. 

 

Swap Instruction

void Swap(bool &a, bool &b)
{
 bool temp = a;
 a = b;
 b = temp:
}

이 명령은 원자적으로 실행된다

만약 두 개의 Swap 명령이 동시에 실행되면, 이들은 어떤 임의의 순서대로도 순차적으로 실행될 것이다.
제한된 대기 요구 사항이 충족되지 않는다. 

 

Solution using Swap

공유 부울 변수 lock는 false로 초기화되고, 각 프로세스는 지역 부울 변수 key를 가지고 있다.

 

Lock이 False, Key true가 되면 critical section에 진입한다. 

 

lock이 True고 key도 true면 swap 해도 아무런 변화가 없기 때문에 다른 프로세스는 임계구역에  접근 불가능하다 

 

 

Mutex Locks

임계 영역 문제를 해결하기 위한 가장 간단한 소프트웨어 도구:

acquire()를 호출하여 잠금을 얻는다.
release()를 호출하여 잠금을 반환한다.
이것을 "뮤텍스(Mutex) 락"이라고 부르며, 상호 배타성을 제공한다.

 

acquire() {
 while (!available) ; /* busy waiting */  // available이 false면 루프를 돌린다. 
 available = false; 
} 
release() { 
 available = true; 
}

이 해결책은 활동 대기(busy waiting)를 필요로 한다.

acquire()를 호출할 때, 잠금이 사용 가능해질 때까지 스핀하며 대기한다.
이러한 종류의 잠금을 "스핀락(Spinlock)"이라고 부른다.

 

available이 false면 이미 다른 프로세서가 임계구역에 있기 때문에 루프를 돌려서 대기한다. 이때 cpu를 쓰면서 대기하기 때문에  활동대기가 발생한다 -> 활동 대기(busy waiting)는 CPU 사이클을 낭비할 수 있다.

하지만 활동 대기가 매우 짧은 경우, 활동 대기가 유용할 수 있으며 시간 소모적인 컨텍스트 스위치를 피할 수 있다.

 

 

 

Semaphore

Semaphore는 동기화 도구다.

Semaphore  S는 정수 변수이며 두 가지 연산을 통해 액세스할 수 있습니다.

wait(S) { // also called P() operation - Proberen
 while (S <= 0) ; // NO-OP
 S--;
}
signal(S) { // also called V() operation - Verhogen
 S++;
}

카운팅 세마포어(Counting semaphore):

값은 제한 없는 도메인에서 범위를 가질 수 있다.이용가능한 자원 수를 나타낸다 

이진 세마포어(Binary semaphore):
값은 0과 1 사이에서만 범위를 가질 수 있다.
뮤텍스 락과 유사하다.
세마포어를 사용한 상호 배타성 구현과 유사하다.

semaphore를 사용한 동기화:
C1가 완료된 후에만 C2가 실행되도록 하려면 semaphore를 사용한다. 

 

 

Semaphore Implementation with no Busy Waiting

세마포어와 관련된 대기 큐(waiting queue)가 있다.

대기 큐에 대한 작업:
block(): 프로세스를 적절한 대기 큐에 넣는다.
wakeup(): 대기 큐에서 대기 중인 프로세스 중 하나를 제거하고 준비 큐(ready queue)에 넣는다.

 

음수 세마포어 값은 해당 세마포어를 기다리는 프로세스의 수를 나타낸다.

Problems with Semaphores

 

 

세마포어는 동기화에 편리하고 효과적인 메커니즘을 제공한다. 

세마포어 연산의 잘못된 사용은 문제를 발생시킬 수 있다.

세마포어 S가 1로 초기화된 경우:

wait(S) ...c.s... signal(S) // 올바른 사용

 

signal(S) ...c.s... wait(S) // 잘못된 사용
wait(S) ...c.s... wait(S) // 잘못된 사용
wait(S) 또는 signal(S)를 누락하는 경우 // 잘못된 사용

모니터(Monitor)는 이러한 문제를 다루는 고수준 언어 구조이다. 

Monitors

모니터(Monitor)는 프로세스 동기화를 위한 고수준 메커니즘이다.

모니터는 한 번에 하나의 프로세스만 모니터 내에서 활성화될 수 있도록 보장한다 (상호 배타성 보장).
프로그래머는 동기화 제약을 명시적으로 코딩할 필요가 없다.

monitor monitor-name
{
// shared variable declarations
procedure P1
(…) { …. } …
procedure Pn
(…) {……}
initialization code ( ….) { … } …
}
}

 

Schematic view of a Monitor

Condition Variables

모니터 자체는 프로세스 동기화에 충분히 강력하지 않기 때문에 추가적인 동기화 메커니즘이 도입된다.

조건 구조 (condition construct)가 도입된다.
조건 변수(condition variables)인 x와 y를 가진다.
조건 변수에 대한 작업을 수행할 수 있다.

 

 

x.wait()

이 작업을 호출한 프로세스는 다른 프로세스가 x.signal() 작업을 호출할 때까지 일시 중지된다

 

x.signal()

일시 중지된 프로세스 중 하나를 정확히 다시 시작한다 (한 개 이상의 프로세스 중 하나).
일시 중지된 프로세스가 없는 경우, x.signal() 작업은 효과가 없다

 

 

Dining-Philosophers Problem

생각하고 먹는 삶을 산다. (철학자가 프로세스) 

이웃과 젓가락을 공유한다. (젓가락이 자원)
배가 고파지면 한 번에 한 개의 젓가락만 집어들어야 한다.
두 개의 젓가락을 손에 들고 있으면 놓지 않고 먹다.
먹기가 끝나면 젓가락을 내려놓고 다시 생각하기 시작한다.

 

Solution to Dining Philosophers Problem

monitor DP
{ 
enum { THINKING, HUNGRY, EATING } state[5];
condition self[5];
void pickup(int i) { 
 state[i] = HUNGRY;
 test(i);
 if (state[i] != EATING) self[i].wait();
}
 void putdown(int i) { 
 state[i] = THINKING;
 test((i + 4) % 5);
 test((i + 1) % 5);
 }

void test(int i) { 
 if ((state[(i + 4) % 5] != EATING) &&
 (state[i] == HUNGRY) && 
 (state[(i + 1) % 5] != EATING)) 
 { 
 state[i] = EATING;
 self[i].signal();
 }
}
 initialization_code() { 
 for (int i = 0; i < 5; i++) state[i] = THINKING;
}
}