[OS] Ch6. Process Synchronization

Background

Race Condition

• 여러 프로세스가 동시에 같은 데이터를 접근하고 조작하는 상황
• 실행 결과는 접근 순서에 따라 달라질 수 있음

Synchronization

• 한 번에 하나의 프로세스만 공유 데이터를 접근할 수 있도록 보장

The critical-section problem

• N개의 프로세스가 shared data에 접근하고자 할 때 발생하는 문제

• Critical Section : 공유 자원(공통 변수, 파일 등)을 접근하거나 변경할 수 있는 코드 부분
• Remainder Section : 나머지 구역 (Remainder section): 공유 자원을 변경하지 않는 코드 부분
• Entry Section : 임계 구역에 들어가기 위해 허가를 요청하는 코드 부분
• Exit Section : 임계 구역을 떠났음을 알리는 코드 부분

Critical Section Rule

Mutual exclusion

한 프로세스가 리소스를 수정하는 동안 다른 프로세스는 해당 리소스에 접근하지 못하도록 함

Progress

어떤 프로세스도 임계 구역에서 실행 중이지 않고, 어떤 프로세스들이 임계 구역에 들어가고자 할 때
Remainder Section에서 실행 중이지 않은 프로세스들만 다음에 Critical Section에 들어갈 프로세스를 지목

Bounded waiting

Critical Section에 진입하려는 프로세스가 무한정 기다리면 안 되고, 얼마나 기다려야 하는지가 필요함

Case of Critical-Section Problem

• Non-preemptive kernel은 Conext Switching이 발생하지 않는 한, 프로세스를 계속 실행하므로 Race Condition으로부터 자유로움

• Preemptive kernel은 운영 체제가 필요할 때 현재 실행 중인 작업을 중지시키고, 다른 작업으로 전환할 수 있으므로, Real-Time Programming에 적합하고, Non-preemptive 보다 Reponsive 함

• 하지만 Race Condition 발생 가능

Peterson’s Solution

int turn; // Critical Section에서 실행할 수 있는 프로세스 ID
boolean flag[2]; // flag[i]가 True면 Process_i가 Critical Section에 들어갈 준비가 됨

Erroneous Algorithm 1 [TURN]

• 서로 바톤을 터치하며 넘겨줌
  

Mutual exclusion은 보장되지만, Progress는 보장 안 됨

• P0가 끝나고 Remainder Section에 머무르고, P1이 끝나고 나면, Critical Section에는 아무것도 안 들어가게 됨

Erroneous Algorithm 2 [FLAG]

• 자기가 서로 하겠다는 의사를 나타냄
  

Mutual exclusion은 보장되지만, Progress는 보장 안 됨

• P0과 P1이 동시에 들어오면, Flag가 둘 다 True가 되어 Critical Section에 진입하지 못함

Erroneous Algorithm 3 [Bounded Waiting]

// Process_i
do {
    while (flag[k]); // 상대방이 Critical Section에 있으면 대기
    flag[i] = true; // Critical Section 진입 의사 표시
    /* critical section */
    flag[i] = false; // process 수행 이후 진입 의사 제거
    /* remainder section */
} while (1);

Process_i 가 매우 빠르게 critical section에 진입하고 나오는 것이 진행된다면, Process_k는 Process_i가 더 이상 진행되지 않을 때까지 무한정 대기하게 됨

Peterson’s Algorithm

do
{
	flag[i] = true; // Critical Section 진입 의사 표시
    turn = k; // 상대방을 먼저 들여보냄
    while(flag[k] && turn == k); // 상대방 대기
    /* critical section */
    flag[i] = false; // process 수행 이후 진입 의사 제거
    /* remainder section */
}while(1);

• Mutual Exclusion, Progress, Bounded waiting 모두 만족
• Process가 While() 대기하며 발생하는 CPU, Memory Cost에 대한 Busy Waiting 문제 발생

Peterson’s Algorithm Ordering Error

do
{
    // turn = k, flag[i] 두 줄 순서 변경
    turn = k; // 상대방을 먼저 들여보냄**
    flag[i] = true; // Critical Section 진입 의사 표시**
    while(flag[k] && turn == k); // 상대방 대기
    /* critical section */
    flag[i] = false; // process 수행 이후 진입 의사 제거
    /* remainder section */
}while(1);

P_0 의 turn = 1 -> P_1의 turn = 0, flag[1] = true
-> P_1의 while(flag[0] == ?? && 0 == 0) -> P_1 Critical Section 진입 -> P_0의 flag[0] = true -> P_0의 while(flag[1] == true && 0 == 1) -> P_0 도 Critical Section 진입

Modern Computer Architectures

• Process 혹은 Compiler는 의존성 없는 명령어들을 재정렬해서 실행하기도 하기에
  모든 명령어의 순서가 중요한 Peterson’s Algorithm은 사용하기 어려움
• 멀티스레드가 shared data를 사용하면서, 위와 마찬가지로 명령어들을 재정렬하며 비일관적인 결과가 나타날 수 있음

H/W Support for Synchronization

Memory Model

메모리 모델은 컴퓨터 아키텍처가 애플리케이션 프로그램에 제공하는 메모리 보장을 어떻게 결정하는지에 관한 것

Strongly orderd

• 어떤 프로세서가 메모리를 수정하면 다른 프로세서들은 그 변경사항을 즉시 확인할 수 있음
• 메모리 일관성이 강하게 보장되기 때문에 동기화 문제를 줄일 수 있음

Weakly ordered

• 어떤 프로세서가 메모리를 수정하더라도 다른 프로세서들은 그 변경사항을 바로 알지 못할 수 있음
• 메모리 수정이 다른 프로세서에 반영되는 데 시간이 걸릴 수 있기 때문에 추가적인 동기화 메커니즘이 필요할 수 있음

Memory Barrier (Memory Fences)

메모리의 변경 사항을 모든 다른 프로세서에 전파하도록 강제하는 명령어

• 모든 로드와 스토어 작업이 완료된 후에 다음 로드 또는 스토어 작업이 수행되도록 함

// thread 1
while (!flag)
    memory_barrier();
print x;

// thread 2
x = 100;
memory_barrier(); // x = 100 변경을 모든 프로세스에 적용
flag = true;

Mutual Exclusion by Lock variable

• Lock == False 인 경우, Process는 critical section에 들어갈 수 있음
• Lock == True 인 경우, 임의의 Process_i는 critical section에 들어가 있음, 다른 Process들은 Lock이 풀릴 때까지 기다려야함

Interrupt Disable

Single Processor System에서는 Critical Section 문제 (Mutual Exclusion, Process, Bounded Waiting)을 Interrupt를 비활성화함으로써 단순히 해결할 수 있음 (Non-preemptive kernel)

하지만 멀티프로세서 환경에서는 한 프로세서에서 인터럽트를 비활성화해도 다른 프로세서들은 여전히 작업을 수행하므로 비효율적임

Atomic Instructions

TestAndSet

Lock을 설정하고 이전 상태를 확인하기 위해 사용됨
이를 통해 임계 구역에 대한 접근을 제어할 수 있음

// 변수의 값을 true로 설정하고 이전 값을 반환
boolean TestAndSet(boolean *target) 
{
    boolean rv = *target;
    *target = true;
    return rv;
}

// Process P_i
boolean lock = false;

do
{	// P_i가 들어가고 Lock 활성화(True) 시킴
	while(TestAndSet(&lock));
    
    /* Critical Section */
    
    lock = false; // Exit Section
    
    /* Remainder Section */
}while(1);

Swap

두 변수의 값을 교환하여 Lock을 구현하는 데 사용될 수 있음

void Swap(boolean *a, boolean *b) 
{
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

// Process P_i
boolean lock = false;

do
{
	key = true; // 문 들어갈 열쇠가 있어
    while(key == true) 
    	Swap(&lock, &key); 
        // lock이 true인지 확인해서 (lock이 false 라면 key를 넣고 들어가)
        // 누가 있는지 계속 노트하는거라 보면 됨
    /* Critical Section */
    
    lock = false; // Exit Section
    
    /* Remainder Section */
}while(1);

Compare and Swap (CAS)

경쟁 조건을 방지하기 위해 사용되며, 주로 Lock을 설정하거나 조건부 업데이트를 할 때 사용

// 주어진 값이 기대한 값과 같으면 새로운 값으로 설정하고, 그렇지 않으면 주어진 값 return
int compare_and_swap(int *value, int expected, int new_value) 
{
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

// Process P_i
boolean lock = false;

while (true) 
{
  // lock이 false이면 lock true로 설정 (진입) 후 false return
  // lock이 true면 lock false return
  while(compare_and_swap(&lock, 0, 1) != 0);
  /* critical section */
  lock = 0;
  /* remainder section */
}

Bounded Waiting Mutual Exclusion

Process가 Critical Section을 떠날 때, 다음 어떤 Process가 Critical Section에 진입할지 지정함

Using TestAndSet

/*Shared Variables*/

boolean lock; // mutual exclusion
boolean waiting[n];

while(TRUE)
{
	waiting[i] = TRUE;
	key = TRUE;
    
    while(waiting[i] && key) 
    	key = TestAndSet(&lock) 
        // lock을 true 설정하고 이전 값을 key에 저장
        // CS에 들어감으로써 쥐고 있던 key를 반납함 == key가 없다는 것은 들어감을 의미
    waiting[i] = FALSE;
    
    /* critical section */
    
    j = (i+1) % n;
    while(j != i && !waiting[j])
    	j = (j+1) % n;
    
    if(j == i)
    	lock = FALSE;
    else
    	waiting[j] = FALSE;
        
    /* remainer section */
}

Using CAS

while(true) 
{
  waiting[i] = true;
  key = true;
  
  while (waiting[i] && key)
  	key = compare_and_swap(&lock,0,1);
  waiting[i] = false;
  
}

Using Swap

while (waiting[i] && key) 
{
        Swap(&lock, &key);
        // lock과 key의 값을 교환
        // key가 TRUE에서 FALSE로 변경되면 임계 구역에 진입할 수 있음
}

Atomic Variables

Atomic : 공유 데이터를 '더 이상 분할이 불가능' 한 상태로 만들어서 데이터의 일관성을 유지

void increment(atomic int *v) 
{
    int temp = 0;
    do {
        temp = *v;  // 현재 값을 읽어 temp에 저장
    } while (temp != compare_and_swap(v, temp, temp + 1));
}

• Thread에서 주로 사용
• mutual exclusion 보장

Mutex and Semaphore

Mutex

synchronization tool to implement mutual exclusion

• available : lock의 반대 의미

/* Atomic operations */ 
acquire() 
{
	// 이용 불가능하면 무한 대기
    // busy waiting 발생
    while (!available);
    // Enter C.S.
    available = false;
}

release() 
{	
	// lock 해제
    available = true;
}


do 
{
  mutex.acquire()
  /* critical section */
  mutex.release()
  /* remainder section */
  
} while(TRUE);

Semaphore

an integer variable accessed only through two atomic operations: wait() and signal()

• 세마포어 변수 S는 임계 구역에 진입하기 위한 재사용 가능한 티켓의 수와 유사

/* Atomic operations */ 
wait(S) 
{
    while(S <= 0);  // 락을 기다림
    S--;            // 락을 획득
}

signal(S) 
{
    S++;  // 락을 해제
}

do
{
	wait(S);
    
    signal(S);

}while(1);

Spinlock

waiting에서 while을 계속 돌면서 발생하는 비효율적인 CPU 자원 발생 현상

typedef struct 
{
    int value;
    struct process *list;  // head of linked list for waiting queue
} semaphore;
//  value와 대기 큐를 위한 링크드 리스트의 헤드 포인터 list를 포함

wait(semaphore *S) 
{
    S->value--;
    if (S->value < 0) 
    {
        add this process to S->list;
        block();  // suspend
    }
}

signal(semaphore *S)
{
  S->value++;
  if(S->value <= 0)
  {
    remove a process P from S->list;
    wakeup(P); // resume
  }
}

Monitors

Reference

Condition Variable

/* Producer */

x++;
cond.signal();
cond.wait();
print(x);
 

/* Consumer */

cond.wait();
x++;
cond.signal();

// 결과 짝수만 출력

Condition Variable

모니터 내에서 P와 Q가 있는데, 실행 중인 P가 대기 중인 Q를 호출한 경우, P와 Q는 monitor에서 같이 실행되는 문제가 발생하게 됨

Signal and Wait

실행 중인 P가 대기 상태로 들어가고 Q가 실행되게 함

Signal and Continue

실행 중인 P가 계속 돌아가고, Q는 P가 모니터를 떠나거나 wait 상태가 될 때까지 대기

필독!!

https://stackoverflow.com/questions/30838223/s-value-0-signal-implementation-in-semaphore-with-no-busy-waiting