Objectives

• critical-section problem 이 뭔지? 왜 생기는지?
  process 여러 개가 공유 데이터를 가지고 있을 때 문제 발생.
  
• 어떻게 안생기게 하는지?
  
• sw and hw solution of the critical-section problem
• several classical process-synchronization problems

Background

Bounded-Buffer

• 우리는 이미 process가 병렬로 실행될 수 있다는 것을 알고 있다.

• producer-consumer 문제를 보자.

  • producer 입장 : producer는 data를 buffer에 추가할 때마다 count++ 시킨다.
    또한, counter == BUFFER_SIZE
    ➡️ buffer가 가득 차있을 때, data를 넣을 수 없음. while문으로 blocking.
    하지만 어느 순간 consumer가 buffer에서 data를 읽어서 count--시켜주면,
    while문을 깨고 나와서 다음 data를 buffer에 추가할 수 있게 된다.
    
    
  • consumer 입장 : consumer는 data를 buffer에서 꺼낼 때마다 count-- 시킨다.
    또한, counter == 0
    ➡️ buffer가 비었을 때, data를 가져올 수 없음. while문으로 blocking.
    하지만 어느 순간 producer가 buffer에서 data를 읽어서 count++시켜주면,
    while문을 깨고 나와서 다음 data를 buffer에서 가져올 수 있게 된다.
    

위와 같은 producer-consumer 구조의 counter++;와 counter--;에 문제가 있다.
그 문제가 발생할 확률은 매우 낮은데, 발생할 가능성이 없진 않으니 무시할 수 없는 문제이다.
그 문제는 무엇일까?

Race Condition

• 초기 counter값이 0에서
  producer가 counter++; 연산을 했고,
  consumer가 counter--; 연산을 했다.
  우리는 counter가 1이 되었다가 최종적으로 0이 될 것이라는 예상을 할 수 있다.
  하지만 아주 작은 확률로 0이 되지 않을 수도 있다는 문제점이 있다.
  왜 그럴까? 다음을 살펴보자.

  • ➡️ counter++;는 다음과 같은 기계어로 구현된다.
    여기서 $register_1$은 한 CPU만 접근할 수 있는 local register 중 하나이다.

  • ➡️ counter--;는 다음과 같은 기계어로 구현된다.
    여기서 $register_2$은 한 CPU만 접근할 수 있는 local register 중 하나이다.

  • producer와 consumer가 병렬적으로 실행되기 때문에 다음과 같은 상황이 발생할 수 있다.
    (counter 초기값 = 5)

  • counter++과 counter-- 연산 = 5 or 4 or 6
    
    ➡️ 이처럼 동시에 여러 process가 동일한 자료를 접근하여 조작하고,
    그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을
    Race Condition(경쟁 상황)이라고 한다.
    ➡️ 위와 같은 Race Condition으로부터 보호하기 위해,
    우리는 하나의 process만이 counter 변수를 조작하도록 보장해야 한다.
    이러한 보장을 위해, counter++;와 counter--; 연산이
    Atomically(원자적으로) 동작하도록 해야 한다.
    ➡️ 문제를 해결하기 위해서 섞이지 않도록 따로따로 수행되도록 해야한다
    == must be performed atomically
    == 원자적으로 수행되어야 한다.
    == 코드 3줄이 1줄로 더이상 분리되지 않고 3줄이 하나처럼 실행되어야 한다.
    == process들이 Synchronization(동기화)되도록할 필요가 있다.

• Race Condition의 또 다른 예시 >
  

  • 두 개의 process가 있다.
    두 process는 각각 fork()를 통해 자식 process를 만든다.
    OS가 하나의 프로그램을 실행시킬 때는 fork()한 후에 exec()를 한다.
  • 두 process가 동시에 fork()를 한다.
    자식 process가 만들어질텐데, OS는 그 process를 관리해야 한다
    관리를 위해 부여한 번호를 pid라고 한다.
  • OS 관점에서 $P_0$의 child process와 $P_1$의 child process가 동시에 왔기 때문에
    두 child process에게 똑같은 pid(2615)를 부여한다.
    
    ➡️ 둘 중 하나의 process에는 Race Condition으로 인한 문제가 생길 것이다.
    따라서 Synchronization(동기화)를 해줘야 한다.

---

The Critical-Section Problem

Critical-Section

• Critical-Section(임계영역) :
  코드가 분리되지 않도록 atomically하게 묶어서 실행되도록 지정해주는 영역.

• 여러 개(N개)의 process가 있을 때,
  각 process는 각각의 critical-section이 있을 수 있다.
  

  1. entry section : 각 process는 자신의 critical-section으로 진입하기 위한 허가를 요청해야 한다. 이러한 요청을 구현하는 code 부분이다.
  2. critical section : 해당 code가 Atomic하게 수행되도록 개발자가 지정한 곳. critical section에 한 process가 들어가면 다른 process는 들어오지 못함.
  3. exit section : critical-section에 대한 설정을 정리하는 부분
  4. remainder section : critical section과 관련없는 그냥 나머지 code.

Critical-Section Problem

• Critical-Section Problem :
  코드가 Atomic하게 수행되어 코드가 서로 섞이며
  shared memory에 Race Condition이 일어나는 상황은 해결할 수 있다.
  하지만 그래도 문제가 생길 수 있다.
  각 process가 critical section을 가지고 있다보니까
  OS 관점에서 운영에 있어서 문제가 발생할 수 있다.

Solution to Critical-Section Problem

• Solution to Critical-Section Problem :
  critical-section에 대한 solution은 다음의 3가지 요구 조건을 충족해야 한다.

1. Mutual Exclusion :
   process $P_i$가 자신의 critical-section에서 실행된다면,
   다른 process들은 그들 자신의 critical-section에서 실행될 수 없다.
2. Progress :
   아무도 critical-section에 들어가 있지 않을 때,
   어떤 process가 critical-section에 들어가려고 하면 들어갈 수 있어야 한다.
3. Bounded Waiting :
   어떠한 process가 critical section에 있다.
   또 다른 process가 critical-section에 들어가고 싶을 때, 기다려야 하는데 그 기다림이 유한해야 한다.
   언제 끝날지 모르고 무한히 기다리도록 하면 안 된다.
   

---

Peterson's Solution

잘못된 Solution 1

• 다음 Algorithm1은 문제 없이 잘 돌아가는가?
  문제가 있다면 3가지 Solution to Critical-Section Problem에서 어떠한 것을 만족시키지 못하는가?

  • Algorithm 설명 :
    turn은 i, j를 동시에 가질 수 없다.
    따라서 critical section은 $P_i$나 $P_j$ 둘 중 하나만 들어갈 수 있도록 동작하는 것이다.
    예를 들어,
    turn = i라서 $P_i$의 critical-section이 실행되고, 끝나면 turn = j
    turn = j라서 $P_j$의 critical-section이 실행되고, 끝나면 turn = i
    ...
    (반복)
    이렇게 critical-section이 반드시 번갈아 실행되야지만 실행되도록 만들었다.

    1. Mutual Exclusion :
       turn 변수 때문에 critical-section에 하나만 들어갈 수 있다.
       ➡️ 따라서 Mutual Exclusion을 만족한다.
    2. Progress : $P_j$가 $P_i$보다 while문에 한참 일찍 도착했다고 가정.
       하지만 초기값이 turn=i 이기 때문에
       $P_j$는 $P_i$가 도착해서 critical section을 끝낸 후 turn=j; 연산을 할 때까지 기다려야
       그제서야 critical-section에 들어갈 수 있다.
       즉, $P_j$는 critical-section에 있는 process가 없는데도 불구하고 critical-section에 진입하지 못하고 기다려야 하는 상황이 존재하기 때문에
       ➡️ Progress를 만족하지 못한다.
    3. Bounded waiting :
       $P_i$의 critical-section이 매우 길고, $P_j$의 critical-section은 매우 짧다고 가정하자.
       $P_j$는 $P_i$가 critical-section이 끝나고 turn=j를 해줘야 하는데
       $P_i$의 critical-section이 매우 길기 때문에 무한히 대기해야 할 수도 있다.
       또한 $P_i$가 critical-section에서 잘못된다면(deadlock) $P_j$는 무한히 대기해야 한다.
       ➡️ 따라서 Bounded waiting을 만족하지 못한다.

잘못된 Solution 2

• 다음 Algorithm2은 문제 없이 잘 돌아가는가?
  문제가 있다면 3가지 Solution to Critical-Section Problem에서 어떠한 것을 만족시키지 못하는가?
  • Algorithm 설명 :
    ➡️ turn 변수 하나 대신에,
    각각의 process에 대한 flag를 만들었다.
    ➡️ 각각의 process들은 do while에 도착해서 자신의 flag를 True로 만들어서
    어떠한 것이 자신에게 turn을 넘겨주지 않아도 스스로 while()에 진입할 수 있다.
    (Algorithm 1에서는 $P_i$가 critical-section을 한 번이라도 수행했어야
    $P_j$가 수행할 수 있었던 문제점을 극복하였다.)
    ➡️ while()에서는 다른 process가 현재 critical-section에 진입하기 위해 또는 critical-section을 실행중인지 확인하기 위해,
    flag를 True로 만들었는지 확인하고, True라면 대기한다.
    ➡️ 다른 process가 critical-section에 진입할 의사가 없거나 진행중이지 않은 경우 while()을 탈출하여 자신의 critical-section을 수행한다.
    ➡️ 자신의 critical-section이 끝나면 flag를 False로 하여
    자신은 critical-section이 끝났다고 상태를 표시한다.
    
    
  • 문제점 :
    $P_i$의 remainder section이 길고, $P_j$의 remainder section이 짧다고 가정.
    $P_i$이 critical-section을 마치고 False로 한 후 remainder section 수행 중에,
    $P_j$가 critical section을 하고 remainder section이 짧기 때문에 다시 위로 올라가서 flag[j]=True로 했다.
    마침 $P_i$의 길었던 remainder section이 끝나고 동시에 flag[i]=True로 했다면,
    동시에 flag가 True로 되어 둘 다 while()에서 blocking되어 무한 대기하는 상황이 생길 수 있다.
    flag[i]=True를 하고 while()로 가는 순간에 scheduling이 일어났다고 가정.

Peterson's Solution

• Peterson Solution : critical-section problem에 대한 고전적인 SW기반 solution.
  잘못된 solution 1, 2를 합쳐서 critical-section problem을 정상적으로 해결할 수 있다.
  하나의 process가 비정상적이면, 나머지는 멈추고 하나는 동작하게
  

Bakery Algorithm

• Critical-Section for N processes :
  
  • process들은 critical-section에 들어가기 전에 번호를 받는다.
    가장 작은 번호를 받은 process가 critical-section에 들어간다.
  • 여러 process가 동시에 critical-section을 요청할 때,
    $i<j$면 $P_i$가 먼저 critical-section에 들어간다
• Bakery Algorithm :
  • Shared Data :
    choosing과 number 배열을 각각 False, 0 으로 초기화
  • main code :
    총 n개의 process {$P_0$, $P_1$, ..., $P_{n-1}$}가 있다.
    그 중에서 나는 $P_i$ 이다.
    코드 설명은 다음과 같다.
    ➡️ 나는 critical-section에 진입하기 위해서 for 위의 3줄의 code를 거쳐야 한다.
    ➡️ (1) choosing[i] = True : critical section에 진입하고 싶어서 number를 부여받는 중인 것을 다른 process들한테 알리기 위해 True로 전환.
    ➡️ (2) number[i] = max(..)+1 : 현재 각 process마다 부여된 번호 중의 최대값+1을 부여받는다.
    이미 할당 받은 process들이 critical-section에 먼저 진입해야 하므로
    나는 맨 마지막 번호표를 부여받는다.
    ➡️ (3) choosing[i] = False : 나는 critical-section에 진입하기 위해 number를 부여받았으므로 choosing을 false로 전환한다.
    ➡️ for() : 나와 함께 실행 중인 나머지 n-1개의 process들에 대해서 각각 확인해야 할 내용이 있다.
    ➡️ while(choosing[j]) : $P_j$가 critical-section에 진입하기 위해서 number를 부여받는 중이라면, 기다려준다.
    어차피 나의 number보다 큰 number를 부여받을 것이므로 n-1개의 process에 대해서 기다려줘도 내가 critical-section에 들어가는 우선순위는 가장 높다고 보장된다.
    ➡️ while((number[j] != 0) && ( (number[j], j) < (number[i], i) )) :
    (number[j] != 0) : 해당 process가 critical-section이 끝나서 number=0이 된 process라면 더 이상 보지 않고 critical-section에 진입할 수 있음,
    (&& (number[j], j) < (number[i], i) ) :
    만약 $P_j$의 number가 나($P_i$)의 number보다 작다면?
    $P_j$가 critical-section에 진입하기 위해 나보다 먼저 number를 부여 받았기 때문에 대기한다.
    매우 희박한 확률이지만 만약 나의 number와 같다면, process 고유 번호인 j와 i로 비교.
    
    (요약) 번호표 뽑기
    지금 뽑는 사람 있나요? 기다려 줄게요.
    일이 끝난 사람은 비키세요.
    나보다 번호 빠른 사람있나요? 없으면 나 할게요.
    (나 진행)
    끝났으니 번호표 폐기할게요.
    다시 위로 가서 번호표 뽑으러 가기.
    
    
• Bakery Algorithm의 단점 : n개의 process들이 있기 때문에
  시간복잡도가 for문의 n번. 근데 그 안에서 while() 2n번 하기 때문에
  총 $O(2*N^2) = O(N^2)$이다.
  하나의 process가 critical-section에 들어가기 위한 시간 복잡도가 $O(N^2)$이다.
  이는 SW적으로 효율이 매우 떨어지게 된다.
  또한 process가 너무 많으면 scheduling이 많아지고
  동시에 choosing하여 number가 같아지는 문제, deadlock 문제, 등등의
  여러 문제가 발생할 가능성이 있다.
  ➡️ 그래서 이러한 기능을 하는 HW를 만들게 된다.
  이 HW를 Synchronization Hardware라고 한다.
  

---

Hardware Support for Synchronization

• 앞서 나온 Algorithm들의 가장 큰 문제점은 Algorithm이라는 것이다.
  하나를 해결하기 위한 과정이 아니라 OS 안에서 매번 일어나야 한다.
  매 Process에 대해서 적용돼야 한다.
  하지만 앞서 나온 Algorithm들은 어떠한 것을 판단하기 위해서 loop(for, while)가 쌓였있었다.

  지극히 SW적 관점이었다.
  하지만 OS에서 일어나야 하기 때문에 의도와 방법은 좋긴 하나,
  더욱 복잡하고 어느 순간 엉키게 되면 deadlock 등 여러 문제가 발생할 수 있다.

• 따라서 SW로는 복잡하니까 HW까지 필요로 한다.
  많은 현대 기계들은 한 word의 내용을 검사하고 변경하거나, 두 word의 내용을 atmoic하게 swap할 수 있는, 즉 interrupt되지 않는 하나의 단위로서, 특별한 HW Instruction들을 제공한다.

Mutex Exclusion with HW Instructions

• HW Instruction의 예시로 test_and_set이 있다.
  test_and_set은 두 process의 Mutual Exclusion(=Mutex)을 위한 HW Instruction이다.
  
  • (기본 흐름) test_and_set도 SW로 사용하면 atomic하지 않을 수 있는데,
    test_and_set을 CPU한테 MOV, ADD처럼 하나의 명령어로 처리하도록 요청할 수 있다.
    ➡️ 이처럼 HW의 도움을 받으면 atomic하고, Simple하게 정상적으로 수행되도록 할 수 있다.
  • (더 생각해볼 점) 하지만 function에 return이 있다.
    == 함수 결과가 어딘가에 저장이 된다 == bus를 이용해서 memory에 세팅한다.
    return이 있다는 의미는 명령 자체는 atomic하지만 return값을 받아서 저장하고 while을 하며 읽는 것까지는 atomic하지 않다는 것이다.
    ➡️ 파고 들면 문제가 꼭 해결되지 않을 수도 있다는 것이다.
  • 또한 어떤 process가 critical section을 진행하고 있는 동안,
    다른 process는 못 들어가고 기다리고 있어야 하는데,
    기다릴 때마다 while(test_and_set(&lock))을 하며 계속 기다리고 있다.
    즉 나머지 Process는 Critical Section에 들어가기 위해 순서를 기다리면서 계속해서 Check를 한다.
    ➡️ 이를 Spinlock(= Busy Waiting)이라고 한다.
    Critical Section에 들어갈 수 있는 권한인 lock을 획득하기 위해 기다리며
    계속해서 check해야 하느라 바쁜 상태.
    ➡️ Busy Waiting은 다른 process가 생산적으로 사용할 수 있는 CPU 주기를 낭비하게 되어 문제가 된다.
    ➡️ 그러나 Busy Waiting은 process가 lock을 기다려야 하고 context switching에 상당한 시간이 소요될 때, context switching이 필요하지 않다는 장점이 있어서,
    Multi Core System의 특정 상황에서는 실제로 lock이 필요할 때, spinlock을 선호

    CS에 들어가기 위한 문제..
    하나만 들어가기 위해 여러가지 알고리즘.. 그것에 대한 문제
    mutex를 이용하여 하나만 들어갈 수 있고 빠르게 할 수 있는 HW Instruction.. 그것에 대한 문제(busy waiting)
    ➡️ 문제가 꼬리를 물며 계속해서 발생..
    ➡️ 이제 문제를 없애보자 ➡️ Semaphores

Semaphores

• Semaphores :
  OS가 CS에 진입하기 위해 Lock 획득을 기다리는 Process들에 대해서 busy waiting하지 않도록 하겠다.
  == 기다리게 하되, busy하지 않게 하겠다. (CPU, power, memory, bus 등을 쓰지 않도록)
  

Semaphore Usage

• S라는 숫자를 갖고 권한을 획득하는 과정.
  • Semaphore S : integer variable
  • wait(S) : S가 0 이하면 가만히 있어라. no operation
  • no-op : 내가 너를 부를테니 ready queue에서 가만히 있어라.
  • signal(S) : S를 증가시킴.
    
    권한을 획득하면 S를 0 미만으로 만들어서 다른 process들이 권한을 못 가져가도록.
    끝나면 signal(S)을 통해 S++;
    CPU를 차지 않는 process들은 ready queue에 있었고,
    그 process들은 동작하지 않고 가만히 있었다.
    no operation
    == OS의 scheduler가 선택할 때까지 그냥 그 자리에 가만히 있음
    == busy waiting 해결

앞서 했던 방법들은 서로 Process들끼리 판단하였다 == User Level(Program Level)이었다.
Semaphore는 OS가 개입하기 때문에 Kernel Level이다.

Semaphore Implementation

• Semaphore는 가용한 resource의 개수로 초기화.
• 각 자원을 사용하려는 process는 Semaphores에 wait() 연산을 수행, 이때 Semaphore값은 감소.
• process가 resource를 방출할 때는 signal() 연산을 수행, 이때 Semaphore값은 증가.
  ➡️ Semaphore값이 0이 되면 모든 resource가 사용 중임을 나타냄.
  ➡️ 이후 resource를 사용하려는 process는 Semaphore값이 0보다 커질 때까지 중지됨.
  
  
• process가 wait()연산을 실행하고 Semaphore값이 양수가 아닌 것을 발견하면, process는 반드시 대기해야하는데, busy waiting하지 않고, 자신을 suspend시킬 수 있다.
  suspend operation은 process를 Semaphore에 연관된 waiting queue에 넣고,
  process state를 waiting state로 변경한다.
• Semaphore S를 대기하면서 suspend된 process는
  다른 process가 signal()연산을 실행하면 재시작되어야 한다.
  process는 wakeup()연산에 의하여 재시작되는데,
  이것은 process state를 waiting에서 ready state로 변경한다.
  
  
• Semaphore List에 add하여 process들 줄 세우기
• block : no operation
• wakeup : Process 하나 골라서 CS에 진입시키기
  
  • 예를 들어, 사용 가능한 resourece개수는 3개 == Semaphore 초기값은 3이라고 하자.
  • P1, P2, P3가 모두 resource를 얻기 위해 wait()를 하여 S=0이 되었다.
  • 여기서 P4가 resource를 요구하여 wait()를 하여 S=-1이 되었다.(하지만 resource는 0임을 유의)
    그래서 P4는 Waiting Queue에서 대기하여 suspend되었다.
  • P1이 terminated되어 resource를 반환하기 위해 signal()을 호출하였다.
    S=0이 되었고, resource는 P1에 의해 반환되어 1개가 남았다.
    S.value<=0이 만족되므로 Waiting Queue에서 P4를 wakeup()하여 실행시킨다.
    따라서 현재 실행중인 process는 P2, P3, P4이며
    S=0이고, 사용 가능 resource = 0개이다.

Deadlock and Starvatoin

• Deadlock : 두 개의 process와 두 개의 semaphore가 있을 때,
  아래와 같이 두 process가 번갈아 실행되는 경우에는 wait(S), wait(Q)가 되어
  $P_0$와 $P_1$이 모두 blocking 상태가 되어 하염없이 기다리고 있는 상태가 된다.
  ➡️ 이 process들은 모두 자신의 차례가 오지 않아 계속 block되어 starvation 문제가 발생.
  ➡️ OS의 잘못이 아니라 process를 만들 때, semaphore의 구조를 잘못 만들면,
  우연히 잘못된다면 deadlock이 발생할 수 있다.
  
  

Two Types of Semaphores

1. Counting semaphore : 정수값이 제한 없는 영역의 범위를 가지는 것.
2. Binary semaphore : 정수값의 범위가 0~1로 한정되는 것. 구현하기 어려움.