5. CPU 스케줄링
스케줄링의 개념과 중요성
스케줄링의 개념: CPU 스케줄링은 운영 체제가 여러 프로세스 또는 스레드에 CPU 시간을 할당하는 방식. CPU 스케줄러는 준비 상태의 프로세스 중에서 어떤 프로세스를 다음에 실행할지 결정하는 역할을 한다.
스케줄링의 중요성:
- 효율성 극대화: CPU 자원을 효율적으로 사용하여 시스템의 전체 성능을 향상.
- 공정성 보장: 모든 프로세스가 공정하게 CPU 시간을 할당받을 수 있도록 한다.
- 반응 시간 개선: 사용자 상호작용이 필요한 시스템에서 응답 시간을 최소화하여 사용자 경험을 개선.
- 처리량 최대화: 단위 시간당 처리할 수 있는 작업의 수를 최대화.
스케줄링 기준
스케줄링 성능을 평가하기 위해 다양한 기준이 사용된다.
- CPU 이용률: CPU가 작업을 처리하는 시간의 비율. 최대한 높이는 것이 목표.
- 처리량(Throughput): 단위 시간당 처리되는 작업의 수. 처리량이 높을수록 성능이 좋다.
- 대기 시간(Waiting Time): 프로세스가 준비 큐에서 대기하는 시간의 총합. 대기 시간을 최소화하는 것이 목표.
- 응답 시간(Response Time): 프로세스가 처음 요청을 제출한 후 첫 번째 응답을 받을 때까지의 시간. 반응형 시스템에서는 응답 시간을 최소화하는 것이 중요.
스케줄링 알고리즘
다양한 스케줄링 알고리즘이 있으며, 각각의 장단점이 있다
-
FCFS (First-Come, First-Served): 먼저 도착한 프로세스가 먼저 CPU를 할당. 단순하지만, 비효율적일 수 있다(예: Convoy Effect).
-
SJF (Shortest Job First): 가장 짧은 실행 시간을 가진 프로세스에 CPU를 할당. 이론적으로 대기 시간을 최소화하지만, 실행 시간을 미리 알기 어렵다.
-
우선순위 스케줄링 (Priority Scheduling): 우선순위가 높은 프로세스에 CPU를 할당. 우선순위가 낮은 프로세스가 기아 상태에 빠질 수 있다.
-
라운드 로빈 (Round Robin): 각 프로세스에 동일한 시간 할당량(퀀텀)을 주고, 순환하면서 CPU를 할당. 공정하고 응답 시간이 일정하지만, 퀀텀 크기에 따라 성능이 달라질 수 있다.
-
멀티레벨 큐 (Multilevel Queue): 여러 개의 큐를 사용하여 프로세스를 분류하고 각 큐에 대해 다른 스케줄링 알고리즘을 적용. 예: 시스템 프로세스와 사용자 프로세스를 별도의 큐로 분리.
-
멀티레벨 피드백 큐 (Multilevel Feedback Queue): 프로세스의 상태 변화에 따라 큐 간 이동이 가능한 스케줄링 알고리즘. CPU 사용 패턴에 따라 프로세스를 동적으로 조정.
6. 동기화
동기화 문제
경쟁 상태(Race Condition): 두 개 이상의 프로세스 또는 스레드가 동일한 자원에 접근할 때, 접근 순서에 따라 결과가 달라지는 상황.
교착 상태(Deadlock): 두 개 이상의 프로세스가 서로가 필요한 자원을 점유하고 있어 아무도 진행할 수 없는 상태.
상호 배제와 임계 구역 문제
상호 배제(Mutual Exclusion): 한 번에 하나의 프로세스만이 임계 구역(Critical Section)에 접근할 수 있도록 보장하는 방법.
임계 구역(Critical Section): 공유 자원에 접근하는 코드 영역으로, 동시 접근이 발생하면 문제가 생길 수 있다.
세마포어와 모니터
세마포어(Semaphore): 동기화를 위한 추상 데이터 타입으로, 두 가지 주요 연산인 P(wait)와 V(signal)를 제공. 세마포어는 자원의 개수를 카운트하여 자원 접근을 제어.
모니터(Monitor): 상호 배제를 위한 고수준의 추상화 기법으로, 객체 기반의 동기화 메커니즘을 제공. 모니터는 임계 구역을 자동으로 관리하며, 상호 배제와 조건 변수를 제공.
교착 상태의 개념과 조건
교착 상태의 개념: 두 개 이상의 프로세스가 서로의 자원을 기다리면서 무한정 대기하는 상태.
교착 상태의 조건 (Coffman 조건):
1. 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
2. 점유 및 대기(Hold and Wait): 자원을 점유한 프로세스가 다른 자원을 기다린다.
3. 비선점(No Preemption): 자원을 강제로 빼앗을 수 없다.
4. 환형 대기(Circular Wait): 프로세스들이 자원을 대기하면서 원형으로 서로를 기다린다.
교착 상태의 예방, 회피, 탐지, 복구
교착 상태 예방: Coffman 조건 중 하나를 제거하여 교착 상태가 발생하지 않도록 한다. 예: 모든 자원을 한꺼번에 할당하거나, 자원을 강제로 빼앗기.
교착 상태 회피: 시스템 상태를 감시하여 안전 상태에서만 자원을 할당. 대표적인 알고리즘은 은행원 알고리즘.
교착 상태 탐지: 주기적으로 시스템을 검사하여 교착 상태를 탐지하고, 탐지된 경우 이를 복구. 자원 할당 그래프를 통해 탐지할 수 있다.
교착 상태 복구: 교착 상태가 발생하면 이를 해결하기 위한 방법. 예: 프로세스를 강제로 종료하거나, 자원을 선점하여 다른 프로세스에 할당.
