[운영체제] 동기화 (1)

Bounded-Buffer 문제 (유한 버퍼 문제)

---

생산자와 소비자

생산자(Producer)는 데이터를 생성하고, 소비자(Consumer)는 데이터를 소비한다.

생산자가 데이터를 생산하면 in이 증가하고, 소비자가 데이터를 소비하면 out이 증가한다. in과 out이 같은 경우, 버퍼가 가득 찼는지 비어있는지 확인할 수 없다.

in과 out의 값으로는 버퍼에 있는 데이터의 양을 알 수가 없다. (위의 그림 참조) 따라서 counter 변수를 사용한다. 하지만 counter 변수는 생산자와 소비자가 동시에 접근하므로 Race condition이 발생한다. 따라서 동기화가 필요하다.

• Race condition
  • 여러 프로세스(또는 스레드)가 공유자원에 동시에 접근할 때, 접근 순서에 따라 결과가 달라질 수 있는 상황

 

 

Synchronizaiton (동기화)

---

• Multi-threaded application
  • 스레드는 프로세스 안에서 메모리를 공유한다. (스택은 별개로 가진다.) 데이터 손상을 막기 위해서는 동기화가 필요하다.
    • 특히, Silent corruption에 주의가 필요하다.
      • OS나 디스크 펌웨어가 데이터가 잘못됐다고 인식하지 못하는 corruption. 심각한 에러를 초래할 수 있다.
• Kernel mode
  • 커널 자료구조 업데이트
    • 여러 프로세스가 동시에 커널 모드로 들어갈 수는 있지만 동시에 커널 데이터는 수정이 불가능해야 한다.
  • Preemptive 커널 vs. Nonpreemtive 커널
    • Nonpreemtive 커널
      • Race condition이 없다.
      • 대신 반응이 느리다.
    • Preemptive 커널
      • Real time system에서 빠른 응답이 필요하기 때문에 사용한다.

 

 

Critical Section 문제 (임계구역 문제)

---

일반적인 프로세스의 실행구조

• Entry section
  • 임계구역으로 진입하기 전의 구역
• Critical section (임계구역)
  • 여러 프로세스들이 공유자원을 수정할 가능성이 있는 코드 구역
  • 만약 하나의 프로세스가 임계구역에 있다면, 다른 어떤 프로세스도 진입해서는 안된다.
• Exit section
  • 임계구역을 벗어남을 알리기 위한 구역
• Remainder section
  • 코드의 나머지 부분

 

Critical Section 문제의 3가지 해결 조건

• 아래 3가지 요구사항을 만족시켜서 Critical Section 문제를 해결하겠다.
  • Mutual exclusion (상호배제)
    • 임계구역에서 한 개의 프로세스가 작업 중일 때, 다른 프로세스는 접근할 수 없다.
  • Progress (진행)
    • 임계구역에서 작업 중인 프로세스가 없고, 임계구역으로 진입하려는 프로세스가 있다면 하나를 적절히 선택하여 진입할 수 있게 한다. 선택은 즉각적이다.
  • Bounded waiting (유한대기)
    • 다른 프로세스들의 Starvation을 방지하기 위해, 한 번 임계구역에 들어간 프로세스는 다시 임계구역에 들어갈 때 횟수에 제한을 두어야 한다.

 

 

Critical Section의 소프트웨어적 해결방법

---

Peterson's Algorithm

프로세스 i의 실행구조

• 프로세스가 2개일 때만 사용 가능
• 프로세스 i와 프로세스 j가 공유하는 자원
  
  • int turn: 임계구역에 진입할 프로세스는 누구인가
  • boolean flag[2]: 임계구역에 프로세스가 진입할 준비가 되어있는가
• Mutual exclusion (상호배제) - 만족
  • 프로세스 i가 임계구역의 진입할 준비가 되었고, turn = j로 설정함으로써 프로세스 i는 무한루프에 빠져 대기상태가 되고, 프로세스 j가 임계구역에 진입한다.
• Progress (진행) - 만족
  • 프로세스 j가 임계구역에서 작업을 마치고 flag[j] = false가 되면 프로세스 i는 곧바로 임계구역으로 진입한다.
• Bounded waiting (유한대기) - 만족
  • 프로세스 j가 임계구역에서 작업을 마치면 프로세스 i가 임계구역으로 진입하여 기아 현상이 사라진다.

피터슨 알고리즘의 단점으로는 아무 일도 안 하는 대기상태를 while문으로 구현하였는데, 이는 busy waiting으로써 CPU 자원을 낭비한다.

 

 

Critical Section의 하드웨어적 해결방법

---

test_and_set

임계구역에 프로세스가 있을 때 lock은 true, 프로세스가 없으면 lock은 false이다.

test_and_set 인스트럭션 구조

test_and_set을 사용한 프로세스의 실행구조

만약 임계구역에 어떤 프로세스도 없는 상태에서 test_and_set을 호출하면 결괏값은 false를 반환하고, lock은 true가 된다. 따라서 임계구역의 진입하려는 프로세스는 while문을 빠져나오고 임계구역에 진입하게 된다.

임계구역에서 작업을 마친 프로세스는 lock = false를 통하여 다른 프로세스가 임계구역에 진입하기 위해 경쟁할 수 있도록 해준다.

위의 코드는 starvation의 가능성이 있다.

 

compare_and_swap

임계구역에 프로세스가 있을 때 lock은 1, 프로세스가 없을 때 lock은 0이다.

compare_and_swap 인스트럭션 구조

compare_and_swap을 사용한 프로세스의 실행구조

test_and_set과 다르게 3개의 매개변수가 필요하다. lock의 메모리 주소, lock의 기댓값 그리고 lock을 설정할 값이다.

만약 임계구역에 프로세스가 없다면 compare_and_swap은 0을 반환하고, lock을 1로 설정한다. 따라서 임계구역에 진입하려는 프로세스는 while문을 빠져나오고 임계구역에 진입하게 된다.

임계구역에서 작업을 마친 프로세스는 lock = 0를 통하여 다른 프로세스가 임계구역에 진입하기 위해 경쟁할 수 있도록 해준다.

위의 코드는 starvation의 가능성이 있다.

 

 

Mutex와 Semaphore

---

Mutex

위에서 설명한 하드웨어적 해결방법들은 프로그래머가 다루기 어렵고, 플랫폼에 종속적이다.

따라서 대부분의 운영체제는 프로그래머를 위해 API를 제공해주는데, mutex이다.

acquire와 release, 그리고 프로세스의 실행구조

Mutex도 test_and_set과 비슷한 구조로 작동함을 알 수 있다.

Mutex의 acquire 함수를 보면, 임계구역에 진입하려는 프로세스들을 blocking 하기 위해 busy waiting을 사용하는 것을 알 수 있다. 이를 spinlock이라고 부르며 마찬가지로 CPU 사이클을 낭비한다.

 

Semaphore

Mutex보다 조금 더 강력한 대안으로 semaphore가 있다. Semaphore는 정수형 변수 S에 대해 wait, signal이라는 atomic 한 함수를 사용한다.

Semaphore에는 2가지가 있다.

• Binary semaphore
  • S의 값으로 0과 1만 사용하며, mutex lock과 비슷하게 사용한다.
• Counting semaphore
  • S는 사용 가능한 자원의 개수를 나타내며, 2 이상의 정수 값을 가진다.

wait와 signal 그리고 프로세스의 실행구조

사용 가능한 자원 S가 0보다 크다면 임계구역에 진입할 수 있고, 프로세스가 임계구역에 진입한다면 S를 감소시킨다.

만약 프로세스가 임계구역에 진입하려고 할 때 S가 0보다 같거나 작다면(= 사용 가능한 자원이 없다면) 프로세스는 block 된다.

하지만 위의 semaphore의 문제점 역시 spinlock으로 인한 CPU 사이클 낭비이다.

따라서 semaphore에 큐를 만들고, 이 큐를 통해 CPU가 스케줄링을 하도록 조작하는 방법이 있다.

 

변경된 wait와 signal

• wait()
  • 프로세스를 semaphore의 waiting queue에 넣는다.
  • 프로세스를 waiting state로 바꾼다.
  • CPU 스케줄러는 semaphore의 waiting queue에 없는, 다음에 실행할 프로세스를 선택한다.
• signal()
  
  • Semaphore의 waiting queue 안에 있는 프로세스 한 개를 ready state로 바꾼다.
  • 프로세스를 ready queue로 삽입하여 CPU가 스케줄링할 수 있도록 한다.

 

Mutex와 Semaphore의 문제점

아래와 같은 경우 Deadlock이 발생할 수 있다.

Mutex와 Semaphore의 Deadlock 발생조건

또는, Semaphore의 ready queue가 FIFO가 아닌 LIFO로 구현되어 있다면 starvation이 발생할 수 있다.