6. 프로세스 동기화

0. 서론

데이터의 접근은 다음과 같은 순서로 일어남

• 1. 저장 공간에 접근한다.
• 2. 연산할 데이터를 가져온다.
• 3. 연산을 실행한다.
• 4. 연산 결과를 다시 저장한다.

 

여러 프로그램이 하나의 저장 공간을 공유하는 경우 경쟁 상태가 발생할 수 있음

• 경쟁 상태 (Race Condition)
  → 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결괏값에 영향을 줄 수 있는 상태
  

 

운영체제에서 경쟁 상태는 언제 발생하는가?

• 1. 커널이 작업 수행 중 인터럽트가 발생하는 경우
  → 예) 커널이 count++ 연산 수행 중 인터럽트가 발생하고, 인터럽트 서비스 루틴이 count-- 연산 수행 후 복귀 시 커널은 count-- 수행 전 데이터를 가지고 있음
  → 해결 : 커널이 작업 수행 중 인터럽트가 발생하더라도 수행 중인 작업을 전부 끝낸 뒤 인터럽트 서비스 루틴을 실행하도록 설계
  
• 2. 프로세스가 커널 모드로 수행 중 문맥 교환이 발생하는 경우
  → 예) A 프로세스가 커널 모드로 count++ 연산 수행 중 타이머 인터럽트가 발생하여 문맥 교환이 발생하고, B 프로세스가 count-- 연산 수행 후 복귀 시 A 프로세스는 count-- 수행 전 데이터를 가지고 있음
  → 해결 : 커널 모드로 수행 중일 때는 CPU 선점이 불가능하지만 사용자 모드로 돌아갈 때 CPU 선점이 가능하도록 설계
  
• 3. 멀티 프로세서 환경에서 커널 데이터에 접근하는 경우
  → 예) CPU1과 CPU2가 커널 데이터를 각각 접근 시 어떤 CPU가 마지막으로 데이터를 저장했는가에 따라 어느 한쪽의 연산 결과가 무시됨
  → 해결1 : 한 번에 하나의 CPU만이 커널 모드로 수행 가능하도록 설계 (비효율적)
  → 해결2 : 커널 데이터에 대한 Lock/Unlock을 하도록 설계 (효율적)

 

이렇듯 경쟁 상태는 데이터의 불일치 문제를 발생시킬 수 있으므로 프로세스 사이의 수행 시기를 맞추는 프로세스 동기화가 필요

 

1. 임계 구역 (Critical Section)

동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역

 

임계 구역 문제 해결 3원칙

• 상호 배제 (Mutual exclusion)
  → 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어갈 수 없음
• 진행 (Progress)
  → 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함
• 유한 대기 (Bounded waiting)
  → 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 함

 

2. Peterson's Algorithm

 

turn 변수와 flag 변수를 동시에 사용

• turn 변수 : 프로세스 간 차례 저장
  → turn 변수만 사용한다면 진행을 만족하지 못함
  
• flag 변수 : 각 프로세스의 임계 구역 진입 의도를 저장
  → flag 변수만 사용한다면 진행을 만족하지 못함
  

 

임계 구역 해결 3원칙을 모두 만족하지만, Busy Waiting 문제가 발생

• Busy Waiting (= Spin Lock)
  → 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 상황
  → CPU를 계속 사용하므로 비효율적
  → 위 예시의 경우 while문에서 발생

 

3. 세마포 (Semaphores)

프로세스 동기화를 위한 추상 자료형

• Semaphore S (S는 정수) : 사용 가능한 공유 자원의 개수
• P(S) : 자원이 있으면 하나 가져가고 없으면 루프를 돌며 기다리는 과정
• V(S) : 자원을 전부 사용하고 반납하는 과정
• 위 두 연산은 전부 Atomic

 

종류

• Binary Semaphore (Mutex Lock)
  → 세마포의 S가 0 또는 1의 값만 가질 수 있음
  → 주로 Mutex Lock에 사용
• Counting Semaphore
  → 세마포의 S가 0 이상의 값을 가질 수 있음
  → 주로 Resource Counting에 사용

 

Mutex Lock 구현 코드

 

• Busy Waiting 문제가 발생하므로 Block/Wakeup 방식이 등장

 

Block/Wakeup 방식 구현 코드

 

• P(S)
  → S의 value를 1 감소시킴
  → S의 value가 음수라면 호출한 프로세스를 Blocked 상태로 만듦
  → 즉, 호출한 프로세스의 PCB를 세마포에 대한 Wait Queue에 삽입
  → 더 이상 임계 구역에 진입이 가능할 때까지 루프를 돌지 않음
  
  
• V(S)
  → S의 value를 1 증가시킴
  → S의 value가 음수 또는 0이라면 특정 프로세스를 Ready 상태로 만듦
  → 즉, 특정 프로세스의 PCB를 Ready Queue에 삽입

 

Busy Waiting vs Block/Wakeup

• 일반적으로 Block/Wakeup 방식이 유리
• 그러나 임계 구역의 길이가 매우 짧은 경우 Block/Wakeup 방식의 오버헤드가 더 커질 수 있음

 

4. 모니터 (Monitor)

세마포의 단점

• 코딩하기 어려움
• 정확성 (Correctness)의 입증이 어려움
• 자발적 협력 (Voluntary Cooperation)이 필요
• 한 번의 실수가 시스템 전체에 치명적인 영향을 끼침

 

따라서 프로그래밍 언어 차원에서 공유 데이터 접근 문제를 해결해주는 프로그램인 모니터가 등장

• 프로그래머는 모니터 내부에 공유 데이터 접근 관련 코드를 정의해서 프로세스가 모니터 내부의 코드만을 이용해서 공유 데이터에 접근할 수 있게 함
• 모니터는 하나의 프로세스만이 모니터 내부의 코드를 실행할 수 있게 제어 (상호 배제 보장)
• 즉, Mutex Lock이 필요 없음

 

Condition Variable

• Condition x;
  → 특정 조건에 의해 중지된 프로세스를 모니터 내부에서 대기시키기 위해 사용
  → 해당 변수는 wait와 signal 연산에 의해서만 접근 가능
  
• x.wait();
  → 해당 함수를 호출한 프로세스는 다른 프로세스가 x.signal() 함수를 호출하기 전까지 중지
  
• x.signal();
  → 해당 함수를 호출 시 정확하게 하나의 중지된 프로세스를 재개
  → 중지된 프로세스가 없다면 아무 일도 일어나지 않음 

 

5. 생산자-소비자 문제 (Bounded-Buffer Problem)

유한한 개수의 버퍼 (공유 데이터)에 여러 명의 생산자와 소비자가 접근

• 생산자는 데이터를 버퍼에 채우고, 소비자는 데이터가 쓰인 버퍼를 비움

 

모든 버퍼가 채워져 있어 생산할 수 없거나 모든 버퍼가 비어있어 소비할 수 없는 문제가 발생 가능

• 해결 : 생산자는 빈 버퍼가 없으면 빈 버퍼가 생길 때까지 대기 후 채우고 소비자는 채워진 버퍼가 없으면 채워진 버퍼가 생길 때까지 대기 후 비우도록 설계
• 이때 Resource Counting을 위해 Counting Semaphore 사용 가능

 

여러 명의 생산자 또는 소비자가 하나의 버퍼에 동시에 접근하는 문제가 발생 가능

• 해결 : 생산자와 소비자가 버퍼에 접근할 때 해당 버퍼에 Mutex Lock을 이용하도록 설계
• 이때 Mutex Lock을 위해 Binary Semaphore 사용 가능

 

6. Readers-Writers Problem

DB (공유 데이터)에 Reader 프로세스와 Writer 프로세스가 접근

• Reader는 데이터를 읽기만 하고, Writer는 데이터를 쓰기만 함
• Read의 경우 여러 Reader가 동시 접근 가능

 

한 프로세스가 Write 중일 때 다른 프로세스가 접근 시 문제가 발생

 

해결

• Writer가 DB에 접근 허가를 얻지 못한 상태에서는 Reader가 접근 가능
• Writer는 대기 중인 Reader가 없을 경우 DB에 접근 가능
• Writer가 DB에 접근 중이면 Reader는 접근 불가
• Writer의 DB 접근이 완료된 후 Reader 접근 가능

 

이때 Reader가 쉬지 않고 접근한다면 Writer는 접근 허가를 얻지 못해 기아 상태에 빠질 수 있음

 

7. 식사하는 철학자 문제

 

철학자는 아래와 같은 순서로 식사함

• 계속 생각하다가 왼쪽 또는 오른쪽 젓가락이 사용 가능하면 집어 듦
• 양쪽 젓가락을 모두 집어 들면 정해진 시간 동안 식사함
• 식사 시간이 끝나면 오른쪽 젓가락을 내려놓음
• 그 후 왼쪽 젓가락을 내려놓음

 

모든 철학자가 동시에 하나의 젓가락을 집은 경우 문제가 발생

• 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상을 교착 상태 (Deadlock)라고 함

 

해결

• 1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 함
• 2. 젓가락을 두 개 모두 집을 수 있을 때만 집도록 함
• 3. 짝수 철학자는 왼쪽 젓가락부터, 홀수 철학자는 오른쪽 젓가락부터 집도록 함
• 4. 젓가락의 개수를 늘림

 

이화여자대학교 반효경 교수님의 운영체제 강의를 정리한 글입니다.

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

또한 반효경 교수님의 "운영체제와 정보기술의 원리" 책을 참고하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=238716482

운영체제와 정보기술의 원리