운영체제 #5

CPU 스케줄링 개요

• 역할: 준비 큐(Ready Queue)에 있는 프로세스 중 하나를 선택하여 CPU를 할당.
• 디스패처(Dispatcher): 선택된 프로세스에 실제로 CPU 제어권을 넘겨주는 모듈.
• 선점(Preemptive) vs 비선점(Non-preemptive)
  • 선점: 실행 중인 프로세스를 중단시키고 CPU를 다른 프로세스에 할당 가능. (현대 OS 대부분 채택)
  • 비선점: 실행 중인 프로세스가 자발적으로 CPU를 반납해야 다른 프로세스 실행 가능.

 

스케줄링 성능 평가 기준 (5가지)

1. CPU 이용률 (CPU Utilization) – CPU가 쉬지 않고 일하는 비율.
2. 처리량 (Throughput) – 단위 시간당 완료된 프로세스 개수.
3. 총 처리 시간 (Turnaround Time) – 프로세스 제출 시점부터 종료까지 걸린 시간.
4. 대기 시간 (Waiting Time) – 준비 큐에서 CPU 할당을 기다린 총 시간.
5. 응답 시간 (Response Time) – 요청 제출 후 처음 응답을 받을 때까지의 시간.

 

주요 스케줄링 알고리즘

1. FCFS (First-Come, First-Served)
   • 가장 먼저 도착한 프로세스를 먼저 실행.
   • 구현 간단, 하지만 긴 프로세스 때문에 짧은 프로세스가 오래 기다릴 수 있음 (Convoy Effect).
2. SJF (Shortest Job First)
   • CPU 버스트가 가장 짧은 프로세스를 먼저 실행.
   • 이론적으로 평균 대기 시간이 최소가 되는 최적 알고리즘.
   • 단점: CPU 버스트 길이를 미리 알기 어려움.
   • CPU 버스트 길이 즉정 방법
     • 이전 실행 기록을 기반으로 다음 CPU 버스트를 예측
     • 이때 흔히 쓰이는 방식이 지수 평균(Exponential Averaging)
3. RR (Round Robin)
   • 시간 할당량(Time Quantum)을 정하고, 각 프로세스가 해당 시간만큼 CPU를 차례대로 사용.
   • 선점형 알고리즘.
   • 시간 할당량이 너무 크면 FCFS와 유사, 너무 작으면 문맥 교환(Overhead) 증가.
4. Priority Scheduling
   • 각 프로세스에 우선순위를 두고, 가장 높은 우선순위 프로세스에 CPU 할당.
   • 동일 우선순위에서는 FCFS 또는 RR 사용.
   • 문제: 낮은 우선순위 프로세스가 무한정 대기할 수 있음(Starvation). → Aging 기법으로 해결.
   • 우선순위 결정 기준
     • Static Priority
       • 운영체제 또는 사용자가 프로세스 생성 시에 고정해서 부여
       • 예. OS 내부적으로 시스템 프로세스가 사용자 프로세스 보다 더 우선순위 높음
       • 예. 실시간 프로세스가 일반 프로세스보다 우선순위 높음
       • 예. 사용자 읿력으로 nice 값 설정 
       • 단점: 한 번 정해지면 실행 중에 변하지 않아 Starvation 발생 가능
     • Dynamic Priority
       • 프로세스의 상태에 따라 우선순위를 운영체제가 실행 중에 변경
       • 예. 오래 기다린 프로세스 > 우선순위를 점점 높임 (Aging 기법)
       • CPU를 많이 쓰는 프로세스 > 우선순위 낮춤
       • I/O 중심 프로세스(짧게 CPU 쓰고 자주 I/O 요청) > 우선순위를 높여 반응성을 보장
5. Multilevel Queue Scheduling
   • 프로세스를 여러 개의 큐로 나누고, 각 큐마다 다른 알고리즘 적용.
   • 큐 간 우선순위 고정.
6. Multilevel Feedback Queue Scheduling
   • 다단계 큐와 비슷하지만 프로세스가 큐 간에 이동 가능.
   • CPU 버스트가 짧은 프로세스는 상위 큐에서 빠르게 처리, 긴 프로세스는 하위 큐로 내려가 점진적으로 처리.

다중 코어 스케줄링

• 부하 균등화 (Load Balancing): 코어 간의 작업을 균등하게 분배.
• 문제: 스레드를 다른 코어로 옮기면 캐시 무효화(Cache Invalidations)로 메모리 접근 비용 증가.

실시간 스케줄링

• 연성 실시간 (Soft Real-Time): 마감 시한을 지키는 것을 최대한 보장하지만 반드시 지킬 필요는 없음.
• 경성 실시간 (Hard Real-Time): 반드시 마감 시한을 지켜야 함.

1. Rate-Monotonic (RM)
   • 주기가 짧은 작업에 높은 우선순위 부여.
   • 정적 우선순위 기반, 선점형.
2. Earliest Deadline First (EDF)
   • 마감 시간이 가장 가까운 작업부터 실행.
   • 동적 우선순위 기반, 선점형.

비례 공유 스케줄링 (Proportional Share)

• 각 응용 프로그램에 일정 비율의 CPU 시간을 보장.
• N/T 시간 보장 방식 → 가상 CPU 개념과 유사.

 

Linux 스케줄러

• CFS (Completely Fair Scheduler) 사용.
• 각 태스크에 "가상 실행 시간(vruntime)"을 부여.
• vruntime이 작은 프로세스일수록 더 자주 CPU를 할당받음 → CPU 시간을 공정하게 분배.