[운영체제] Chapter 6. Synchronization Tools

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Background 

• Processes는 concurrent하게 실행됨
• data에 대한 Concurrent한 접근은 data inconsistency를 유발함
• data consistency -> cooperating processes의 orderly execution이 보장돼야 함

 

Race Condition

• Race Condition -> 통제되지 않는 shared data에 대한 접근이 발생할 때 존재
• 두 개 이상의 프로세스가 공통 자원을 concurrent하게 읽거나 쓰는 동작을 할 때, shared data에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황

 

Critical Section

• 각 process는 code의 critical section segment를 가짐
  • process의 동작 -> 공용 변수 변경, table 업데이트, file 작성, ...
  • 한 프로세스가 critical section에 위치할 때 -> 어떤 process도 critical section에 접근할 수 없음
• 각 process는 critical section에 진입하기 위한 permission을 요청해야 함

 

1. Critical Section Problem

• system에 n개의 processes {P0, P1, ..., Pn-1}이 존재한다고 가정
• Critical Section Problem: 프로세스들이 데이터를 협력적으로 공유하기 위하여 그들의 activity를 동기화할 수 있는 protocol을 설계하는 것

- Requirements for solution to critical-section problem

1. Mutual Exclusion
   • process P_i가 critical section에 존재할 때, 다른 어떤 processes도 critical section 내부에서 실행될 수 없음
2. Progress 
   • 아무 process도 critical section 내에서 실행되지 않고, 몇몇 processes가 진입을 시도 -> selection of the process that will enter critical section next는 무기한으로 연기될 수 없다.
   • deadlock 방지
3. Bounded Waiting 
   •  각 프로세스는 유한한 횟수의 시도 후에, critical section에 진입할 수 있어야 한다.
     • each process는 nonzero speed로 실행
     • n processes 간에 상대 속도에 대한 어떤 가정도 없어야 함
   • starvation 방지

 

2. Interrupt-based Solution

• Entry section: disable interrupts
• Exit section: enable interrupts
• Will this solve the problem?
  • critical section이 1시간 동안 작동하는 code라면?
  • stravation 문제가 발생할 수 있음
  • multiprocessor environment에서 해당 방식을 사용하려면, entry 진입 전에 모든 processor에게 "interrupt를 비활성화하라"는 message를 전달해야 함 -> 이때 message를 전달하는 데 걸리는 시간에 의해 시스템 속도가 저하

 

3. Preemptive vs. Nonpreemptive kernels

• critical section 문제를 해결하는 일반적인 접근 방법으로 Preemptive, Nonpreemptive kernels가 존재
• Preemptive Kernel: process가 kernel mode에서 작동 중일 때, preemption을 허용
• Nonpreemptive Kernel: process가 kernel mode에서 작동 중일 때, preemption 허용 X -> process가 kernel mode를 벗어나거나, block되거나, CPU 제어를 자발적으로 놓기 전까지 작동
• Nonpreemptive kernel에서는 race condition 발생 X 
• preemptive kernel은 race condition이 발생하지 않도록 신경써서 설계해야 함
• 그렇다면 왜 preemptive kernel을 사용해야 하는가? 
  
  • more responsive
  • real-time programming에 더 적합함

 

Peterson's Solution

1. One Software Solution

• Two process solution -> load & store instructions가 atomic(작동하는 중 interrupt 불가능)한 특성을 가졌다고 가정
• two process는 one variable 공유
  • int turn: critical section에 진입하는 turn이 누구에게 있는지 결정

while(true) {
    while(turn == j);
        
        /* critical section */
        
    turn = j;
    
        /* remainder section */
}

-> turn이 Pj에게 있으면 while문을 계속 돌면서 turn을 기다림 -> turn이 i로 바뀌는 순간 critical section 진입

-> critical section이 끝나고 나면 turn을 j에게 다시 넘김

2. Peterson's Solution

• Two process solution -> load & store instructions가 atomic(작동하는 중 interrupt 불가능)한 특성을 가졌다고 가정
• two process는 two variables 공유
  • int turn: critical section에 진입하는 turn이 누구에게 있는지 결정
  • bool flag[2]: process가 critical section에 진입할 준비가 되었는지 나타냄

while(true) {
    flag[i] = true;
    turn = j;
    while(flag[j] && turn == j)
        ;
        
        /* critical section */
        
    flag[i] = false;
    
        /* remainder section */
}

-> turn이 i에게 있거나, j가 준비되지 않았거나, 둘 중 하나만 만족해도 critical section 진입

 

이제 3가지를 보여야 함

1. Mutual exclusion is preserved.
   • Pi는 flag[j]가 false이거나 turn이 i일 때만 진입 
   • 두 개의 프로세스가 같은 순간에 동작할 수 없음
2. The Progress requirement is satisfied.
3. The Bounded-waiting requirement is met.

 

3. Peterson's Solution - Problem

• Peterson's Solution은 modern architectures에서 이점을 얻지 못한다.
  • 프로세서나 컴파일러가 명령어 순서대로 실행되지 않을 수 있음 -> instructions가 순서대로 실행된다는 가정이 있어야 solution 성립
• For a single threaded program -> result는 항상 동일 -> 문제 X
• For a multithreaded program with shared data -> reorderding이 inconsistent or unexpected results 초래할 수 있음

-> 2개의 processes가 동시에 critical section에 진입할 수 있음

 

Hardware Support for Synchronization

• software-based solution은 modern computer architecture에서 이점을 가지지 못함
• 여기서는 3가지 주요 hardware support를 다룰 예정
  • Memory barriers
  • Atomic instructions
  • Atomic variables

1. Memory Barriers

• Memory model: computer architecture가 application programs에 제공하는 memory를 의미
  • Strongly ordered: 한 processor의 memory 수정이 all other processors에게 즉시 전달되는 memory
  • Weakly ordered: 한 processor의 memory 수정이 all other processors에게 즉시 전달되지 않는 memory
• Memory barrier: memory 내부의 어떤 변화든 all other processors에 전달되도록 하는 명령어
  •  Memory barrier를 사용함으로써, system은 load & store 명령어가 완수되기 전에 어떤 이어지는 load or store operation도 동작되지 않음을 보장

 

-> x의 할당은 반드시 flag의 할당 이전에 발생

 

• Memory barrier는 아주 low-level operations -> 일반적으로 mutual exclusion을 보장하는 특정 코드를 작성하기 위해 kernel 개발자들이 사용

2. Hardware Instructions

• Atomic Instructions: word의 content를 test-modify 혹은 두 개 words의 content를 swap하는 행위를 atomical하게 수행하는 명령어 -> uninterruptedly
  
  • test-and-set() instruction
  • compare-and-swap() instruction

- test-and-set()

• atomical하게 실행
• passed parameter의 original value를 반환 -> 변환 이전의 value
• passed parameter의 value를 true로 설정

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    
    return rv;
}

do {
    while (test_and_set(&lock));
        /* do nothing */
        
      /* critical section */
      
    lock = false;
    
      /* remainder section */
} while(true);

-> target이 원래 false였다면, lock을 test_and_set 내부에서 lock을 true로 설정하고 false를 return

-> lock으로 while문 부분을 걸어잠그고, 자신은 critical section에 진입하는 구조

-> 해당 process가 critical section을 완수하면 lock을 false로 설정하여, 대기하고 있던 process가 이전 단계와 같이 critical section에 진입

 

- compare-and-swap()

• atomical하게 실행
• passed parameter의 original value 반환
• *value == expected를 만족하는 경우에만 value를 new_value로 설정

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

while(true) {
    while(compare_and_swap(&lock, 0, 1) != 0); /* do nothing */
    
      /* critical section */
    
    lock = 0;
    
      /* remainder section */
}

-> 전역변수 lock의 초기 setting은 0

-> 해당 process는 0을 반환하고, lock은 new_value인 1로 설정됨

-> critical section에 진입 

-> 빠져나올때 다시 lock을 0으로 setting

 

• mutual-exclusion은 만족하지만, bounded-waiting은 만족하지 못한다!!

3. Atomic Variables

• compare-and-swap() instruction은 일반적으로 다른 sunchronization tools를 구축하기 위해 사용됨
• 그런 tools 중 하나로 atomic variable이 존재
• atomic variable: integers, booleans와 같은 basic data types를 atomic하게 update하는 데에 사용됨

void increment(atomic_int *v) {
    int temp;
    do {
        temp = *v;
    } while(temp != (compare_and_swap(v, temp, temp + 1));
}

 

Mutex Locks

• Hardware 측면의 solutions는 application programmers에게 복잡하고 접근이 나쁘게 느껴질 수 있음
• OS designer들은 critical section problem을 해결하기 위한 software tools를 구축
• simplest is Mutext Lock: lock이 이용 가능한지 확인하는 boolean variable
• Protect a critical section by 
  • First acquire() a lock
  • Then release() the lock

 

 

• acquire() & release()를 호출하는 행위는 atomical해야 함
  
  • 보통 hardware atomic instructions(CAS, ...)에 의해 구현됨
• But this solution requires busy waiting -> 이런 lock을 spinlock이라 부름
• bool available 
  • ture -> unlocked
  • false -> locked

-> critical section에 process가 진입했으면, 그동안 다른 process는 acquire에서 대기하다가, critical section을 통과한 process가 release를 통과하면서 lock을 풀게 되고, 이때 대기하던 process는 critical section에 진입하면서 다시 lock을 걺

-> pair로 acquire와 release를 잘 사용하지 않으면, 무한정으로 기다릴 수 있음

 

Semaphore

• mutex lock보다 더 복잡한 방식으로 process activities를 synchronize하는 도구
• semaphore S - integer variable(number of resources)
• 2개의 보이지 않는 atomic operations에 의해서 접근될 수 있음
  • wait() & signal() - originally called P() & V()

1. Semaphore Usage

• Counting semaphore: 범위가 무제한인 integer value
  
  • 유한한 개수의 instances를 가진 특정 reousrces에 접근하기 위해 사용
  • semaphore - 이용 가능한 resource의 수로 초기화
• Binary semaphore: 0과 1만 가질 수 있는 integer valule
  
  • = mutex lock
• semaphore를 이용하여 synchronization problems를 해결하는 건 programmer의 몫
• semaphore operations의 잘못된 사용
  • signal(mutex) ... wait(mutex)
  • wait(mutex) ... wait(mutex)
  • wait or signal을 생략
• semaphore는 signal 방식, mutext는 lock 방식

Semaphore - Usage

• semaphore "mutex"를 1로 초기화

wait(mutex);
/* critical section */
signal(mutex)

 

• S1이 S2 이전에 수행되도록 보장하려면
  • semaphore "synch"를 0으로 초기화 했을 때

 

2. Semaphore Implementation

- Semaphore without Busy Waiting

• 각 semaphore에는 개별적으로 waiting queue가 존재함
• 각 waiting queue의 entry는 2개의 data item을 가짐
  • Value(of type integer)
  • Pointer to next record in the list
• 2개의 operations
  • block: operation을 호출하는 process를 적절한 waiting queue에 배치 -> 불러야 하는데, 자원이 모자라서 기다려야 하는 프로세스
  • wakeup: waiting queue에서 대기하던 processes 중 하나를 제거하고, ready queue에 위치하게 함 -> waiting queue에서 대기하던 process를 깨우는 명령어

-> wait()에서 사용할 수 있는 자원이 없으면, 해당 process는 waiting queue에 진입하여 block() 즉 대기함

-> 대기 중인 process가 존재하면, 해당 process를 ready queue에서 꺼내서, wakeup()

 

+ process state를 바꿔서 가져오려면 overhead가 발생, 

-> 짧게 사용할 거면 busy waiting이 훨씬 효율적

-> spinlock의 경우 busy waiting을 사용하여 빠르게 context switching

 

• 2개 이상의 processes가 같은 세마포어의 wait()과 signal() 함수를 동시에 실행할 수 없도록 해야함
• implementation -> wait()과 signal()의 code가 같은 critical section 내부에 위치  -> atomic
• 원하는 자원의 권한을 얻을 때까지 계속해서 확인하는 방식인 busy waiting -> critical section에 많은 시간을 머무는 code의 경우 cpu 자원 낭비가 심함
  • critical section의 구현 code가 짧은 경우 좋을 수 있긴 함

 

Monitor Usage

• Monitor: 편하고 효과적인 process synchronization을 위한 high-level abstraction
  
  • 한 순간에 오직 하나의 프로세스만 monitor 내부에 존재
  • programmer는 명시적으로 synchronization 제약조건을 코딩하지 않아도 됨
• Monitor type이라는 ADT 존재

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

-> 내부에 있는 것들이 동시에 접근되지 않도록 보호

 

 

 

- Condition Variables

• programmers들은 맞춤형 synchronization scheme을 작성하길 원함
• define one or more variables of type condition
  • condition x, y;
• condition variable에서 2개의 operation 사용 가능
  • x.wait() - operation을 호출하는 process는 x.signal()까지 미뤄짐
  • x.signal() - x.wait()을 호출했던 processes 중 하나의 process를 재개(resume)함 -> 기다리는 process 없으면 그냥 넘어감

 

- Condition Variables - example

• statement S1과 S2를 실행해야 하는 P1과 P2를 가정 -> S1이 S2 이전에 실행돼야 함
  • P1과 P2에 의해 호출되는 F1과 F2 procedures에 대한 monitor를 생성 
  • condition variable 'x'는 0으로 초기화
  • boolean variable "done"

---

참고자료

• https://iredays.tistory.com/125

[운영체제] Race Condition과 예방할 방법(세마포어, 뮤텍스)

• https://choiblack.tistory.com/21

[OS] Synchronization과 Critical-Section Problem