OS-7) 프로세스 동기화

topics	700-컴퓨터과학 704 운영체제
types	이론 학습
tags	#synchronization #mutex #semaphore #critical-section

프로세스 동기화

데이터의 일관성을 유지할 수 있게 해야 한다. 통신 과정에서 생기는 생산자-소비자 문제를 해결해야 한다.

생산자-소비자 문제(producer-consumer problem): 여러 개의 프로세스를 어떻게 동기화할 것인가에 관한 고전적인 문제다. 한정 버퍼 문제(bounded-buffer problem)라고도 한다.

임계 영역 (Critical Section)

용어	설명
임계 영역	공유하는 데이터에 접근하고 갱신할 수 있는 코드 영역
임계 영역 문제	해당 영역에 하나의 프로세스만 있어야 한다

==동기화 문제 해결 == 임계 영역 문제 해결==

임계 영역에는 진입 영역(허가 받는), 퇴출 영역, 나머지 영역이 있다.

임계 영역 문제 해결을 위한 3가지 필수 조건

조건	설명
상호 배제 (Mutual Exclusion)	프로세스 하나가 임계 영역에서 실행 중이라면 다른 프로세스는 임계 영역에서 실행될 수 없다
진행 (Progress)	현재 임계 영역에서 실행되는 프로세스가 없고, 그 임계 영역에 진입하려는 프로세스가 있다면, 임계 영역에 들어올 다른 프로세스를 선택하는 걸 무기한 연기할 수 없다
한정된 대기 (Bounded Waiting)	프로세스가 임계 구역에 진입하려는 요청을 한 후 그 요청이 허용될 때까지 다른 프로세스들의 진입 허용 횟수를 제한한다

동기화 해결책

해결하기 위한 하드웨어도 제공되어야 한다.

하드웨어적 해결책

방식	설명
단일 처리기	실행 중인 코드는 선점 없이 실행된다. 일반적으로 다중 처리기 시스템에서는 너무 비효율적
원자적 하드웨어 명령	원자성(인터럽트가 불가능한 연산 단위)을 제공하는 특별한 명령

이후 해결책은 소프트웨어 해결책이다.

Peterson 해결책

전통적인 소프트웨어적인 해결책이다. 두 개의 변수(데이터)를 필요로 한다.

// 최대 2번째 프로세스까지 있음

boolean flag[2];
// flag[n] == true, n번째 프로세스가 임계 구역을 사용하고 싶다
int turn;
// 프로세스 차례, turn = n이면 n번째 프로세스 차례

while(flag[n] && turn == n) {
    // 임계 영역
    flag[n] = false;
    // remain 영역
}

주의: 다중 프로그램 시스템에서 사용할 수 없다. 이외에도 Compare-and-Swap이라는 해결책이 있다.

Mutex Locks

임계 구역을 보호하고 경쟁 상태를 예방
임계 구역 입장 전 Lock을 얻어야 하고 퇴장 시 Lock을 해제하여야 함
뮤텍스는 오브젝트다

연산

연산	설명
`acquire()`	lock을 얻음 (입장)
`release()`	lock 해제 (퇴장), signal이라고 표현할 수 있음
`available`	lock을 얻을 수 있는가?

단점

Busy Waiting 문제가 있다. lock을 얻을 때까지 계속 접근을 시도한다 (이걸 spinlock이라 함).

Semaphore

고수준 소프트웨어 도구들의 종류다. Busy-waiting 하지 않는 동기화 도구다.

어떻게? 프로세스를 일시 정지하면 된다. 그리고 대기 큐에 집어넣음

원자적 연산에 의해서만 접근 가능하다
동시에 여러 프로세스 접근 가능 = 한정 버퍼 문제 해결 가능 = 생산자 소비자 문제

Busy Waiting Semaphore

원자적 연산 wait(입장하려는), signal(퇴장하려는) 사용

종류	설명
Binary Semaphore	값 0이면 대기, 1이면 입장. mutex lock 대신 사용 가능
Counting Semaphore	공유 자원이 여러 개일 때 사용

Non-Busy Waiting Semaphore

구현 방법

각 세마포어에 대해 연관된 대기 큐가 있다
- 세마포어 값과 이 세마포어에 대기하는 프로세스 리스트의 포인터를 저장한다
프로세스를 세마포어와 연관된 대기 큐에 넣고 프로세스 상태를 대기(waiting)로 변경한다

연산

연산	설명
block	대기 큐에 넣는다
wakeup	대기 큐 프로세스 중 하나를 준비 큐에 넣는다

발생할 수 있는 문제

문제	설명
Deadlock	한 프로세스만 야기할 수 있는 이벤트를 무한정 기다림. 모두 wait 상태일 때 발생 → OS-8) 프로세스 교착상태-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C.html)
Starvation	우선순위가 낮아서 자원을 계속 할당받지 못하는 상태
Priority Inversion (우선순위 역전)	높은 순위가 필요로 하는 lock(자원)을 낮은 우선순위의 프로세스가 가지고 있을 때. 우선순위 상속 프로토콜로 해결

프로세서 코어별 동기화 방법

프로세서	동기화 방법
싱글 코어	원자적 연산(인터럽트를 금지함)들을 이용해서 해결할 수 있다. 예: 세마포어
멀티 코어	모든 코어에서의 인터럽트 금지는 성능 저하를 발생시킨다. 따라서 spin lock이나 compare_and_swap을 사용한다