[운영체제] Ch2.3. Synchronization

여러 쓰레드가 공유된 데이터들에 동시에 접근하려 할 때, 그 실행들을 제어해주어야 한다. 실행되는 여러 작업들이 문제가 없게끔 맞춰주는 걸 Synchronization 이라고 한다.

Race Condition

똑같은 수행을 하는데 매번 결과가 다르게 나오는 것 (타이밍에 따라서)

• 초록색 리턴된 다음에 빨간색 실행된 거

• put_balance에 값 넣기 전에 Context Switch가 발생한 경우
• 초록색은 9000원, 빨간색은 8000원 리턴.
• 빨간색 리턴(8000)한 다음에 다시 초록색 풋 밸런스로 돌아가서 초록색 리턴(9000).
• 총 삼천원 빼간건데 결과적으론 1000원만 없어짐. 개꿀? -> 이게 race condition

 

Critical Regions

• 프로그램 코드 중 공유된 자원에 접근하는 부분
• 해당 자원에 동시에 access할때는 synchronization이 필요하다
• Critical Region에 진입할때는 mutual exclustion하게 수행한다.

Critical Section Problem (CSP)

critical section 문제를 해결하기 위해서는 아래의 조건을 만족해야 한다.

1. Mutual exclusion
2. No Starvation
3. Progress : T가 CR 바깥에 있을 때, S가 T때문에 CR에 못들어오면 안된다.
4. CPU의 속도에 대해선 어떠한 가정도 해선 안된다

 

Mechanisms for Solving the CSP

• with Busy Waiting
  • Disabling Interrupt
  • Lock Variables -> 중간에 꼬이면 CR에서 충돌
  • Strict Alteration -> 중간에 꼬이면 아무도 CR 못들어감
  • Peterson's Solution -> 되긴 하는데 복잡하고 성능 안좋음
  • TSL => 아토믹하게, 하드웨어 설계로
• Sleep and Wakeup => busy waiting 단점 줄임 (깨워줘), 얘도 지연생기면 꼬일 수 있음
• Semaphores => 해결 가능 but 코딩 어려움
• Montiors

-> 두꺼운 글씨로 되어있는게 shared memory라고 강의록에 써있음.
sleep and wakeup도 공유메모리 맞는거같음.

• Message Passing : 얘는 non-shared memory

 

---

 

1. Busy Waiting

a) Disabling Interrupt

Critigcal region을 지나는 동안 interrupt가 발생하면 무시한다. 방해받지 않고 끝까지 수행한 뒤에 enable시킴. OS로 안넘어가도록. 즉, Context Switch를 일어나지 않게 한다.

• 애초에 context switch가 일어나지 않으니까 다른 프로세스가 CR을 수행하지 못한다.
• 위의 문장은.. CPU가 하나일때만 해당되는 말!! 멀티 프로세서 환경에서는 다른 CPU에 의해 다른 프로세스가 CR을 수행할 수 있기 때문에.
• User-process에서는 불가능한 방법 : 이런건 권한이 필요한 작업 (privilege instruction).

b) Lock Variables

while ( lock == 1 );  // Waiting

// 하지만 여기서!! Context Switch가 된다면?
// A는 while 루프를 통과했는데 lock을 미쳐 1로 바꾸지 못한 경우
// : B도 수행 가능해진다. CR에 둘이 들어갈 수 있게 됨.
lock = 1;
Critical_Region();
lock = 0;

여러 프로세스가 접근 가능한 global 변수를 사용한다.

• 0 : 접근 가능
• 1 : 누가 쓰는 중 -> 기다린다
• lock값이 0이 될때 여러 프로세스가 Critical Region에 동시에 진입하는 문제가 생길 수 있다.

c) Strict Alteration

위의 문제를 해결하기 위해 turn 이라는 변수를 도입함.

• 한쪽은 turn이 1일때 수행, 다른쪽은 0일때 수행.
• turn이 동시에 0 또는 1일 수 없으므로, 무조건 CR에는 하나의 프로세스만 진입할 수 있다.

문제점

• 하지만 무조건 ababab 이렇게 번갈아가며 수행해야 한다. CR이 비어있다 하더라도, 두번 이상 연속적으로 접근하지 못함. (CSP 3번 조건을 만족하지 않음 : 밖에 있는 나때문에 다른애가 못들어가면 안됨)
• critical_region() 하고 turn 1로 바꾸기 직전에 멈췄을때!! -> CR은 비어있는데 turn = 0이라 아무도 못들어가는 상황이다.

Busy Waiting

• 이렇게, while loop 돌면서 계속 검사하면서 기다리는걸 Busy Waiting이라고 함.
• spin lock : lock variable에 대한 busy waiting. CPU 낭비!!

d) Peterson Solution

지금까지 나온 여러 방법들의 software적인 해결 방법.

되긴 하는데 오버헤드가 만만치 않은 해결책이다.

e) TSL instructionv (Test and Set Lock)

CPU가 제공하는 하드웨어적인 방법이다. Atomic하게 수행된다.

• Atomic instrunction : instruction이 시작하면 끝날때까지 interrupt를 받지 않는다.

bool TSL(bool *flag)
{
    bool old = *flag;
    *flag = true;
    return old;
}

• 함수로 표현되어 있지만 하드웨어로 구현되어 있다.
• 인자로 들어온 flag의 값을 리턴하고, 1로 세팅한다. (세팅 전의 값을 리턴해주는 것)

• TSL 명령 사용하는 예시

TSL 구현

• lock 변수는 메모리에 저장되어 있고, CPU와는 메모리 버스로 연결되어 있다.
• CPU에서 lock에 접근하기 위해서는 - 메모리 버스의 사용권을 얻어내야 한다.
  즉, 한번에 한 CPU만 메모리에 접근할 수 있다. HW적으로 처리.
• CRITICAL_REGION이 끝나면 다음에 leave_region 이 나오는 형태.

spinlock의 문제점

• CPU 낭비
• A가 lock 0이 될때까지 계속 CPU를 사용하며 기다리는데, 막상 B는 우선순위가 낮아서 CPU 할당을 못받아 leave_region을 수행할 수 없는 경우.. 결국 아무도 못쓴다.

 

2. Sleep and Wakeup

• busy waiting을 대체하기 위해 sleep()과 wakeup을 사용한다. 프로세스 자기 자신을 Block시키거나, 자고 있는 (인자로 넣은) 프로세스를 wakeup으로 호출해서 깨울 수 있다.
• sleep과 wakeup도 시스템 콜.

Producer - Consumer Problem

• Producer는 Item을 만들어서 Buffer로 넣고, Consumer는 Buffer에서 Item을 꺼내서 사용
• Producer는 버퍼가 꽉차면, Consumer는 버퍼가 비면 sleep
• Producer는 빈 버퍼에 item을 하나 추가하면 wakeup(Consumer),
  Consumer는 꽉 찬 버퍼의 item을 하나 사용하면 wakeup(Producer)

빨간색은 Producer-Consumer의 실행과정, 보라색은 문제점.

1. count = count + 1 또는 - 1 하는 부분이 Atomic하지 않기 때문에, Mutual Exclusive 하지 않음. 이 과정에서 어셈블리 명령어들이 순서가 꼬여 문제가 생길 수 있다.
2. P에서 count == N 조건을 통과해서 sleep 하려는 사이에 Context switch가 발생하고 C가 수행된다면 : C에서는 버퍼에 아이템이 있으므로 계속 count를 줄여나감.
   그러다가 count = 0 이 돼서 C도 자버린다. 둘다 Sleep하게 됨. 영원히!
   • 근데 여기서 wakeup()을 저장했다가 나중에 다 sleep했을때 꺼내서 쓸수도..?

 

3. Semaphores

Sleep and Wait의 데드락 문제를 해결하기 위해!

• 세마포어는 변수야.
• Atomic하게 동작하는 다운과 업 연산으로 조작함 (아토믹하다!)
• Down(semaphore) : 0보다 크면 sem--; / 0이면 wait(블락 처리)
• Up(semaphore) : sem++; / wait중인 스레드가 있으면 하나를 wakeup

세마포어 두 종류

• Binary semaphore (mutex semaphore) : 0과 1 (버퍼가 1인거?)
• Counting Semaphore (N까지). synchronization을 구현할때 이용

이 두가지 세마포어를 이용해서 Producer-Consumer 문제를 해결해볼거야.

var mutex: semaphore = 1    // mutex (lock과 비슷하게 사용)
    empty: semaphore = n    // 버퍼의 빈 공간 "empty"
    full : semaphore = 0    // 버퍼가 찬 공간 "full"
                            // empty + full == N

producer:
        <produce item>
    down(empty)
    down(mutex)
        <add item to buffer>   
    up(mutex)
    up(full)

consumer:
    down(full)
    down(mutex)
        <remove item from buffer>
    up(mutex)
    up(empty)    
        <use item>     

 

Mutex

add나 remove같이 버퍼(공유데이터)에 접근하는 부분에

• 들어갈때 : down(mutex) 1 -> 0
• 나갈때 : up(mutex) 0 -> 1

 

Synchronization

• Producer
  • Item 하나 만들고 down(empty) : 비어있는 버퍼수--;
    (CR작업 끝나면);
    up(full) : 차있는 버퍼수++;
  • 컨슈머에서는 처음에 차있는 버퍼수를 보고 CR진입하기 때문에, 버퍼에 입력하는 작업이 끝난 다음에 full 세마포어를 올려주는 듯
  • 처음에 empty = 0 이면 down(empty) 할 때 블락됨
• Consumer
  • 바로 down(full) : 차있는 버퍼수--; (CR작업 끝나면); up(empty) : 비어있는 버퍼수++;
  • empty 올려준 다음에, 가져온 item을 사용한다.
  • 처음에 full = 0 이면 down(full)할 때 블락됨

 

장점단점

• Busy Waiting을 하지 않는다.
• 코딩하기 어려워서 버그가 있을 가능성이 높다.
• down(mutex)와 down(empty)의 순서를 바꾸면 데드락 일어날 가능성.

 

4. Monitors

• shared data mutex 지원
• Critical Region에 비정상적으로 접근하는 것을 원천적으로 막는다!

monitor example
    integer i;
    condition c;

    procedure producer();   // CR
        ...
    end;

    procedure consumer();   // CR
        ...
    end;
end monitor;    

• 한번에 하나의 process만 해당 모니터의 procedure를 사용할 수 있다.

 

Condition Variables

모니터 안에서만 접근 가능한 condition variables을 이용해서 시그널을 주고받을 수 있다. 이를 이용해 sleep and wakeup을 구현한다.

count 변수는 monitor안에 있음. 그래서 그 count 변수에 접근하려면 monitor 안에 있는 procedure로 밖에 접근할 수 없다!!

 

컨디션이라는건 그 변수마다 큐가 있는건데.. 여기선 괜히 이름을 full empty라고 해가지고 헷갈리는 것.

 

• wait(c)
  • wait 걸리면 모니터 안에서 빠져나오고, 다른 애가 들어와서 쓸 수 있도록 열어준다
    : release monitor lock
  • 누가 모니터 안의 프로시저를 사용하면 다른 사람들이 못들어오게 모니터를 잠가준다
    : monitor lock
  • if count = N then wait(full)
    만약에 프로듀서가 여러개면, p1 - p2 - p3 이렇게 큐에서 대기한다.
    그리고 그 큐의 이름이 full이라고 생각하면 됨. 프로듀서는 항상 full 큐에서 대기하고 있고, 컨슈머는 항상 empty 큐에서 대기하고 있다. 프로듀서가 count 0 에서 1로 만들어주면 signal(empty)를 해주는 이유도, empty 큐에 대기하고 있는 컨슈머를 깨우기 위해서!!
• signal(c)
  • 해당 컨디션 변수에 wait중인 프로세스나 쓰레드를 깨운다.
  • 좀더 쉽게 쓰자면.. (c) 상태에서 대기중인 놈을 깨운다

모니터로 구현한 sleep & wake

• 모니터에선 한번에 오직 하나의 프로시저만 돌아간다. 만약 어떤 프로듀서가 item을 만들고 있으면, 다른 컨슈머가 remove를 하고 싶어도 못한다.
• mutex하기때문에.. Race Condition은 발생하지 않아!
• 보라색 글씨 : signal()을 호출한 뒤에 어디서 다시 수행을 하나?
  • Hoare monitors : 새로 wakeup된 프로세스가 바로 모니터에 들어가서 수행된다. 그 다음에 signaler가 블락됨. 바로 버퍼 바뀌는 일 없이 들어가므로, Condition은 바뀌지 않음이 보장
  • Hansen monitors : signal이 발생하더라도 수행중인 프로세스를 계속 수행하고, 작
  • Mesa monitors : signaler가 다 수행되고 빠져나가고 나서 waiter가 수행된다. waiter가 수행될때 condition이 달라져있을수도 있음.

monitor 문제점

• 모니터는 OS 아니라 프로그래밍 언어단에서 지원하는 것 c/c++에선 안된대
• 분산 시스템(메모리 공유를 안함. 네트워크를 통해 받음)에서는 사용할 수 없다.
• 분산시스템에서는 message passing으로 구현!!

 

5. Message Passing

• 메모리를 직접적으로 공유할 수 없는 환경에선 send, receive system call 사용해서 받는다
• P와 C가 각각 독립적인 머신에서 각자의 메모리를 이용하기 때문에 공유 리소스 없음. CR 없다.
• send(dest, &message) : 메시지를 전송한다
• Receive(src, &message) : 메시지를 받는다. 리시버는 메세지를 수신할때까지 블락됨.