프로세스 동기화 & 동기화 기법
- 동시다발적으로 실행되는 프로세스들은 공동의 목적으로 서로 협력하는데 프로세스들은 실행 순서와 자원의 일관성을 보장하기 위해 동기화를 함
Q) 동기화 왜 필요한가?
공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다. 따라서, Race condition을 막고 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘인 동기화(Synchronization)가 필요하다.
1. Race Condition (임계조건)
✅ Race-Condition
: race-condition이란 두 개 이상의 프로세스가 공통 자원을 병행적(concurrently)으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.
🗣️ 경쟁 프로세스는 세 가지 제어 문제에 직면한다. Mutual exclusion, deadlock, starvation
[Multual exclusion(상호 배제)]
- 하나의 프로세스만 임계구역을 사용할 수 있도록 다른 프로세스의 접근을 차단하는 것이다.
- 상호배제를 위한 4가지의 요구조건이 충족되어야 한다.
- 두 개 이상의 프로세스들이 동시에 임계구역에 있으면 안 됨
- 어떤 프로세스도 임계구역에 진입하는 것이 무한정 연기되면 안 됨
- 임계구역 안에 있는 프로세스가 다른 프로세스의 임계구역 진입을 막을 수 있어야 함
- 프로세스들의 상대적인 속도(각 프로세스들의 처리 속도, 접근 방법, 상태)에 대해 어떠한 가정을 하면 안 됨
[Dead Lock(교착 상태)]
프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때 프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않는다. 이러한 상황에서 두 프로세스는 교착 상태에 빠지게 되는 문제
다음 네 가지 조건이 모두 성립할 때 교착상태 발생 가능성이 있다.
- 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다. 즉 ,한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
- 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
- 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
- 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
[Starvation(기아 상태)]
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말한다.
2. Critical Section (임계구역)
Critical Section(임계 구역) : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
2. Synchronization(동기화)
- 정의 : 다중 프로세스 환경에서 자원에 데이터 일관성을 유지하도록 하는 것
- 필요성 : 데이터에 동시 접근시 데이터 일관성이 깨지거나 결과가 잘못될 가능성이 있다.=
[동기화 2가지]
1) 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
→ 실행의 순서가 있기 때문에 무작정 아무렇게나 실행되서는 안된다.
대표 예시) reader writer problem
2) 상호 배제 : 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기
대표 예시) Bank account problem
✅ [Critical Section 문제 해결 3가지 조건] ⇒ 동기화를 위한 조건
1. Mutual Exclusion (상호 배제)
- 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입하면 안 된다.
2. Progress (진행)
- Critical Section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다.
3. Bounded Waiting (유한 대기) → 언젠간 들어가야한다.
- 프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다. 쉽게 말해, Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안 된다.
========================================================================
동기화 기법
: 동기화 문제를 해결하기 위한 방법
뮤텍스 락(Mutex Lock) 세마포어(Semaphore) 모니터
교착상태란?
- 교착상태(Dead Lock)은 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.
교착상태 발생 조건
주로 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황에서 발생한다.
교착상태가 발생하기 위해서는 다음의 네가지 조건이 충족되어야 하는데, 이 네가지 조건중 하나라도 충족되지 않으면 교착상태가 발생하지 않는다.
🗣️ 상호배제(Mutual Exclusion)
자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다. 상호 배제 기법에는 뮤텍스, 세마포어 등이 있다.
점유와 대기(Hold and Wait)
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
비선점(Non-preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
환경 대기(Circular Wait)
서로 다른 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구한다.
교착상태 해결 방안
🗣️ ✅ 예방(Prevention)
교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로 교착상태 발생의 네가지 조건 중에서 어느 하나를 제거한다. 단, 자원 낭비가 가장 심한 해결 방법이다.
- 상호 배제(Mutual Exclusion)부정 : 한번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
- 점유 및 대기(Hold and Wait) 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구한다.
- 비선점(Non-preemption)부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다린다.
- 환형 대기(Circular Wait)부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 한다.
✅ 회피(Avoidance)
교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.
**은행원 알고리즘**
- 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법이다.
- 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 한다.
- 은행은 자원을 할당한 후에도 안정 상태로 남아있는지 검사하여 안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기한다.
- 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.
✅ 탐지(Detection)
시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
- 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용 할 수 있다.
✅ 복구(Recovery)
교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
프로세스 종료
- 교착상태에 있는 프로세스를 종료
- 교착상태에 있는 프로세스들을 하나씩 종료
자원선점
- 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법입니다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점한다.
뮤텍스 락(Mutex Lock)
- 뮤텍스 락 : 하나의 공유자원에 접근하는 프로세스를 상정한 방식
- 상호 배제를 위한 동기화 도구(자물쇠 역할)
- 이진 세마포어의 일종으로 자원에 Lock을 걸면서 동기화 문제를 해결
- 좌물쇠의 유무에 따라 임계구역 이용 가능 여부를 표시
- 좌물쇠 역할: 프로세스들이 공유하는 전역변수 Lock
- 임계구역 잠그는 역할: acquire 함수
- 임계구역의 잠금을 해제하는 역할: release 함수
🗣️ 과정
1번 프로세스가 자원을 접근하기 위해 Key를 점유한다.
1번 프로세스는 키를 점유했기 때문에 공유 자원을 사용한다.
2번 프로세스가 공유 자원을 사용하기를 원한다.
2번 프로세스는 키를 점유하기 위해 대기한다.
3번 프로세스 또한 공유 자원을 사용하기 위해 2번 프로세스 다음 순번으로 대기한다.
1번 프로세스가 공유 자원을 다 사용하고 Key를 반환한다.
2번 프로세스는 대기하고 있다가 반환된 Key를 점유하고 공유 자원을 사용한다.
🔑
acquire 함수: 프로세스가 임계구역에 진입하기 전에 호출하는 함수
- 만일 임계 구역이 잠겨 있다면 임계구역이 열릴때까지 (lock이 false 가 될 때까지) 임계 구역을 반복적으로 확인하고,
- 임계 구역이 열려 있다면 임계 구역을 잠그는(lock을 true로 바꾸는) 함수
release 함수: 임계 구역에서의 작업이 끝나고 호출하는 함수.
- 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수임
Busy waiting: CPU를 선점하고 있는 상태
- 무한히 반복하면서 잠겨있는지 확인 → 바쁜 대기
세마포어(Semaphore)
- 세마포어 : 여러 개의 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구
- 뮤텍스 락과 비슷하지만, 좀 더 일반화된 방식의 동기화 도구
- 철도 신호기 : 올라가있으면 GO / 내려가있으면 STOP
- 뮤텍스 락 : 하나의 공유자원에 접근하는 프로세스를 상정한 방식인 반면, 세마포어는 여러 개의 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구
🗣️
전역 변수 S: 임계 구역에 진입할 수 있는 프로세스의 개수 (사용 가능한 공유 자원의 개수)
wait 함수: 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수
signal 함수: 임계 구역 앞에서 기다리는 프로세스에 ‘이제 가도 좋다’고 신호를 주는 함수→ process가 끝나고 호출됨
🗣️ 과정
Busy Wait ⇒ CPU 사이클 낭비! (계속 반복적으로 확인해야 하므로)
- Busy Wait 해결 방법
- 사용할 수 있는 자원이 없을 경우 대기 상태를 만듬 (해당 프로세스의 PCB를 대기 큐에 삽입)
- 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 많듦 (해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입 )
모니터 (Monitor)
- 세마포는 아래와 같은 문제가 있음
모니터 ⇒ 사용자(개발자)가 다루기 편리한 동기화 도구
상호 배제를 위한 동기화
- 인터페이스를 위한 큐
- 공유 자원에 접근하고자 하는 프로세스 (인터페이스를 위한) 큐에 삽입
- 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용
실행 순서 제어를 위한 동기화
- 조건 변수 condition variable 이용
- 프로세스나 스레드의 실행 순서를 제어하기 위한 특별한 변수
- 조건변수.wait(): 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
- 조건변수.signal(): wait()으로 대기 상태로 접어든 조건변수를 실행 상태로 변경
- 모니터 안에는 하나의 프로세스만이 있을 수 있다.
- wait()를 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개
- signal()을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개
뮤텍스와 세마포어의 차이
- 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
- 세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 그에 대한 책임을 가진다.
- 세마포어는 동기화 대상이 여러개 일 때 사용하고, 뮤텍스는 동기화 대상이 오로지 하나 일 때 사용된다.
