Ch12. 프로세스 동기화
동기화
동기화: 특정 자원에 접근할 때 한 개의 프로세스만 접근하게 하거나, 프로세스를 올바른 순서로 실행하게 하는 것
- 실행 순서 제어를 위한 동기화: 프로세스들이 특정 순서대로 실행되도록 조정함.
ex) reader 프로세스는 writer 프로세스 실행이 끝나야 실행될 수 있음. - 상호 배제 (mutual exclusion)를 위한 동기화: 동시에 여러 프로세스가 공유 자원에 접근하는 것을 방지함.
공유 자원과 임계 구역
공유 자원 (shared resource): 여러 프로세스가 공동으로 사용하는 변수, 메모리, 파일 등의 자원
임계 구역 (critical section): 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 영역
레이스 컨디션 (race cindution): 여러 프로세스가 공유 자원에 동시에 접근하는 상황.
여러 프로세스가 동시에 임계구역의 코드를 실행하는 상황.
임계 구역 문제 해결 조건:
- 상호 배제 (mutual exclusion): 한 프로세스가 임계 구역에 진입한 동안 다른 프로세스는 해당 구역에 진입할 수 없음.
- 잔행 (progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함.
자원을 필요로 하는 프로세스는 계속해서 진입할 수 있어야 함. - 유한 대기 (bounded waiting): 어떤 프로세스도 임계 구역에 들어오기 위해 무한 대기해서는 안 됨.
동기화 기법
- 뮤텍스 락 (Mutex lock; MUTual EXclousion lock)
- 상호 배제를 위한 동기화 도구로, 하나의 공유 자원에 하나의 프로세스만 접근할 수 있도록 보장함.
- 형태:
- 전역 변수 lock: 공유 자원을 보호하기 위해 사용되는 자물쇠 역할의 변수
- acquire 함수: 임계 구역에 들어가기 전에 호출되며, lock이 잠겨 있는지 확인한 후, 잠겨 있지 않으면 lock을 잠그고 진입함.
- release 함수: 임계 구역에서 작업이 끝난 후 호출되며, lock을 해제하여 다른 프로세스가 접근할 수 있도록 함.
- 바쁜 대기 (busy waiting): acquire 함수가 반복적으로 lock의 상태를 확인하면서 대기하는 방식. CPU 자원을 지속적으로 소모하므로 비효율적임.
acquire() {
while (S == true)
; // 바쁜 대기
lock = true;
}
release() {
lock = false;
}
acquire();
// 임계 구역
release();
- 세마포 (semaphore)
- 공유 자원이 여러 개 있는 상황에서도 적용 가능한 동기화 도구
- 형태:
- 전역 변수 S: 현재 사용 가능한 자원의 수를 나타냄.
- wait 함수 (P): 프로세스가 임계 구역에 진입하기 전에 호출되며, 자원이 있으면 S를 감소시키고 진입, 자원이 없으면 대기 큐에 프로세스를 추가하고 프로세스 상태를 대기 상태로 전환함.
- signal 함수 (V): 임계 구역에서 작업이 끝난 후 호출되며, S를 증가시키고 대기 중인 프로세스를 준비 상태로 전환하여 준비 큐에 추가함.
wait() {
while (S <= 0)
;
S--;
if (S < 0) {
add this process to Queue;
sleep; // 바쁜 대기 없이 프로세스를 대기 상태로 전환
}
}
signal() {
S++;
if (S <= 0) {
remove a process p from Queue;
wakeup(p); // 대기 중인 프로세스를 깨움
}
}
wait();
// 임계 구역
signal();
- 모니터 (monitor)
- 프로세스가 인터페이스를 통해서만 공유 자원에 접근 가능하도록 하여 자원을 보호하고 프로세스 간에 동기화 제공함. 이는 세마포의 잘못된 코드 사용으로 발생할 수 있는 문제를 개선함.
- 작동 원리:
1. 임계 구역에 접근하고자 하는 프로세스는 모니터에 작업을 요청함.
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고, 결과만 해당 프로세스에 알림.
- 조건 변수: 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 변수로, 모니터가 실행 순서 제어를 위한 동기화에 사용함.
- wait와 signal 연산을 수행
- 모니터 큐와는 별개로, 조건 변수에 대한 큐를 사용함. 이 큐는 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행을 중단시키기 위한 큐임.
- 작동 원리: 조건 변수에 대한 wait 연산이 호출되면 해당 프로세스는 조건 변수 큐에 삽입되며, signal 연산이 호출되면 큐에 대기 중이던 프로세스가 실행을 재개함.
Ch13. 교착 상태
교착 상태
교착 상태 (deadlock): 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상. 여러 프로세스가 작업을 진행하면서 발생하는 자연적인 현상임.
자원 할당 그래프
자원 할당 그래프 (resource-allocation graph): 프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 기다리고 있는지 표현하는 방향성이 있는 그래프
- 프로세스는 원, 자원은 사각형으로 표현함.
- 자원 사각형 내에 사용할 수 있는 자원 개수를 점으로 표현함.
- 프로세스가 자원을 할당받은 경우, 자원에서 프로세스를 향해 화살표로 표시함.
- 프로세스가 자원을 기다리는 경우, 프로세스에서 자원을 향해 화살표로 표시함.
교착 상태 발생 필요 조건
- 상호 배제 (mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 동시에 사용할 수 없는 경우, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있음.
- 점유와 대기 (hold and wait): 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 경우 교착 상태가 발생할 수 있음.
- 비선점 (nonpreemptive): 한 프로세스가 점유 중인 자원을 다른 프로세스가 강제로 빼앗을 수 없는 경우 교착 상태가 발생할 수 있음.
- 원형 대기 (circular wait): 자원을 점유한 프로세스들이 서로 다른 자원을 기다리며 원형으로 대기하는 경우 교착 상태가 발생할 수 있음.
교착 상태 해결 방법
-
교착 상태 예방: 교착 상태 발생 피료 조건 네 가지 중 하나를 충족하지 못하게 하는 방법. 현실적으로 여러 제약이 있어 사용이 어렵거나 부작용이 있을 수 있음.
- 상호 배제 예방: 모든 자원을 공유 가능하게 함
-> 현실적으로 자원을 보호해야 하므로 대부분의 자원은 상호 배제가 필요 - 점유와 대기 예방: 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않음
-> 자원의 활용률이 낮아지고, 기아 현상이 발생할 수 있음. - 비선점 예방: 모든 자원을 빼앗을 수 있도록 함
-> 비선점 조건의 무력화 어려움. - 원형 대기 예방: 모든 자원에 숫자를 부여하여 오름차순으로 자원 할당
-> 자원에 번호를 부여하는 게 복잡하고, 특정 순서로만 자원을 요청할 수 있어 유연성이 떨어질 수 있음.
- 상호 배제 예방: 모든 자원을 공유 가능하게 함
-
교착 상태 회피: 프로세스에 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법.
자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눔.
- 안정 상태: 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 (안전 순서열 존재)
- 불안전 상태: 교착 상태가 발생할 수도 있는 상태 (안전 순서열 없음)
- 안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
=> 시스템이 안정 상태를 유지하도록 자원을 할당하는 방법
-
교착 상태 검출 후 회복: 교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 이를 회복하는 방법
- 선점을 통한 회복: 교착 상태가 해결될 때까지 다른 프로세스의 자원을 빼앗아 한 프로세스에 자원을 몰아주는 방식
- 프로세스 강제 종료를 통한 회복: 교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 없어질 때까지 순차적으로 프로세스를 종료하는 방식
기본 문제
p.363 확인 문제 1번
- 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다.
세마포는 대기 큐를 사용해 자원이 사용 가능해질 때까지 프로세스를 대기 상태로 전환하여 관리하기 때문에 바쁜 대기가 필수적이지 않음.
