📌 스케줄링이 나오게 된 배경
🖥️ CPU I/O 버스트 사이클
프로세스의 실행은 CPU 실행과 I/O 대기 과정이 반복되는 사이클로 구성됩니다.
- 실행과 함께 CPU 버스트 발생
- I/O 버스트 발생하여 CPU 대기
- 다시 CPU 버스트 실행 (버스트로 종료)
➡ 버스트 지속 시간이 짧고 반복이 많다면 빈번한 작업, 지속 시간이 길다면 드문 작업이 됨.
⚡ 다중 프로그래밍(Multiprogramming)
프로세스가 I/O 요청 등의 대기 시간이 생길 때, CPU가 놀게 되는 문제 발생
➡ 이를 해결하기 위해 CPU 이용률을 높여 대기 시간을 최소화하는 스케줄링이 필요함.
다중 프로그래밍의 목표
- CPU를 최대한 바쁘게 유지
- 다수의 프로세스를 메모리에 유지
- CPU가 대기 상태에 빠지면 즉시 다른 프로세스를 실행
- 프로세스가 대기할 때마다 다른 프로세스가 CPU를 양도받도록 스케줄링
➡ 이를 "스케줄링(Scheduling)"이라고 함.
⚠ CPU-I/O 버스트 분포를 잘 분석하여 최적의 스케줄링을 수행해야 함.
🚀 스케줄링
운영체제의 핵심 기능 중 하나로, 모든 컴퓨터 자원은 사용되기 전에 스케줄링됨.
🎯 CPU 스케줄러
운영체제가 준비 큐(Ready Queue) 에 있는 프로세스 중 어떤 프로세스를 실행할지 선택하는 기능을 수행하는 곳
- CPU가 대기 상태(유휴 상태)가 되면 준비 큐에서 하나의 프로세스를 선택하여 실행
- 준비 큐는 프로세스들의 PCB(Process Control Block, 프로세스 제어 블록)로 구성됨
📌 CPU 스케줄링 발생 상황
-
실행 상태 → 대기 상태 (비선점 스케줄링)
- I/O 요청 or 자식 프로세스 종료 대기
- CPU를 놓을 때까지 다른 프로세스가 실행되지 않음
- 대기 상태는 CPU를 받을 수 없는 상태
-
실행 상태 → 준비 완료 상태 (선점 스케줄링 가능)
- 인터럽트(Interrupt) 발생 → 다른 프로세스에게 CPU 양도
- 스케줄링 가능 → 선점 스케줄링 적용 가능
- 준비 완료 상태는 CPU를 받을 수 있는 상태
-
대기 상태 → 준비 완료 상태
- I/O 작업 종료 시 실행 가능
- 스케줄링 가능 → 선점 스케줄링 적용 가능
-
프로세스 종료 (비선점 스케줄링)
⚖️ 비선점(Non-preemptive) vs. 선점(Preemptive) 스케줄링
1️⃣ 비선점 스케줄링
✔ 프로세스가 종료하거나 대기 상태가 될 때까지 CPU를 점유
✔ Context Switching(문맥 교환)이 적어 오버헤드가 낮음
✔ 하지만, 긴급한 프로세스가 대기해야 하는 단점 발생
2️⃣ 선점 스케줄링
✔ 운영체제가 CPU를 강제로 빼앗고 다른 프로세스에 할당 가능
✔ 우선순위가 높은 프로세스를 즉시 실행 가능
✔ 하지만, 빈번한 Context Switching으로 인해 오버헤드 증가
✔ 데이터 일관성이 깨질 수 있는 경쟁 상태(Race Condition) 발생 가능
➡ 현대 운영체제는 대부분 선점 스케줄링을 사용!
🎛 디스패처(Dispatcher)
CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 제공하는 역할
-
Context Switching(문맥 교환) 수행
- 자발적 문맥 교환: 프로세스가 스스로 CPU를 포기 (예: I/O 요청)
- 비자발적 문맥 교환: 운영체제가 강제로 CPU를 빼앗음
-
사용자 모드 전환 수행
-
프로세스 재시작 위치 결정
⏳ 디스패치 지연(Dispatch Latency)
✔ 하나의 프로세스를 중지하고 다른 프로세스를 실행하는데 걸리는 시간
✔ 최대한 짧아야 함!
📊 스케줄링 기준(성능 측정)
CPU 스케줄링 알고리즘 평가 기준
✔ CPU 이용률 → CPU를 최대한 바쁘게 유지
✔ 처리량(Throughput) → 단위 시간당 완료된 프로세스 개수
✔ 총 처리 시간 → 프로세스 시작부터 완료까지 걸리는 시간
✔ 대기 시간 → 준비 큐에서 기다린 총 시간
✔ 응답 시간 → 처음 응답이 시작되는 데 걸리는 시간
➡ 이러한 기준을 만족하는 스케줄링 알고리즘이 바람직함.
📌 스케줄링 알고리즘 종류
✔ 준비 큐에서 어떤 프로세스를 CPU에 할당할지 결정하는 알고리즘
✔ 단일 CPU 코어 환경을 가정하여 설명
🟢 비선점 스케줄링
✔ 프로세스가 CPU를 점유하면 놓아줄 때까지 스케줄링 변경 없음
✔ Context Switching이 적어 오버헤드 최소화 가능
✔ 하지만, 긴급한 프로세스 처리가 어려운 단점 존재
🔹 FCFS (First-Come First-Served)
✔ 도착 순서대로 CPU 할당
✔ 단순하고 구현이 쉬움
✔ 하지만, 중요한 작업이 오래 대기하는 문제 발생 (Convoy Effect)
🔹 SJF (Shortest Job First)
✔ 실행 시간이 가장 짧은 프로세스를 먼저 실행
✔ 평균 대기 시간을 최소화할 수 있는 알고리즘
✔ 하지만 실행 시간을 정확하게 예측하기 어려움
✔ 긴 실행 시간을 가진 프로세스가 계속 대기하는 기아 현상(Starvation) 발생 가능
🔹 HRN (Highest Response Ratio Next)
✔ SJF의 기아 현상을 해결하기 위한 방식
✔ 응답 비율(대기 시간 + 실행 시간 / 실행 시간)이 높은 순서로 실행
✔ 기다린 시간이 길수록 우선순위 상승 (Aging 기법 적용)
✔ 하지만, 계산량이 많아 스케줄링 비용 증가 가능
🔹 우선순위 스케줄링 (Priority Scheduling)
✔ 프로세스마다 우선순위를 부여하여 실행 순서 결정
✔ 높은 우선순위 프로세스를 먼저 실행 가능
✔ 하지만 기아 현상 발생 가능 (낮은 우선순위 프로세스가 계속 대기)
✔ 해결책 → Aging 기법을 사용하여 대기 시간이 길어지면 우선순위 증가
🟠 선점 스케줄링
✔ 운영체제가 CPU를 강제로 할당 변경 가능
✔ 긴급한 프로세스를 빠르게 실행 가능
✔ 하지만, 빈번한 Context Switching으로 인한 오버헤드 증가
🔹 SRT (Shortest Remaining Time)
✔ SJF를 선점형으로 변경한 방식
✔ 현재 실행 중인 프로세스보다 더 짧은 실행 시간을 가진 프로세스가 도착하면 CPU 양보
🔹 우선순위 스케줄링 (Priority Scheduling, Preemptive)
✔ 더 높은 우선순위의 프로세스가 도착하면 실행 중인 프로세스를 중단하고 CPU를 할당
✔ 긴급한 작업을 즉시 처리할 수 있음
✔ 하지만, 낮은 우선순위 프로세스가 무한정 대기하는 기아 현상(Starvation) 발생 가능
✔ Aging 기법을 적용하여 해결 가능
🔹 Round-Robin (RR)
✔ 일정 시간(Time Quantum) 동안만 실행 후 다음 프로세스로 교체
✔ 모든 프로세스가 공평하게 CPU를 사용할 수 있도록 보장
✔ Time Quantum이 너무 짧으면 Context Switching이 빈번해져 오버헤드 증가
✔ 너무 길면 FCFS와 다를 바 없음
🔵 다단계 큐(MLQ) vs. 다단계 피드백 큐(MLFQ)
🔹 MLQ (Multi-Level Queue)
✔ 여러 개의 대기 큐를 사용하여 프로세스를 그룹으로 나누어 처리
✔ 각 큐는 서로 다른 스케줄링 알고리즘을 적용 가능
✔ 하지만, 한 번 배정된 큐에서 이동 불가 → 기아 현상 발생 가능
🔹 MLFQ (Multi-Level Feedback Queue)
✔ CPU 사용 시간에 따라 자동으로 우선순위 조정 가능
✔ 오래 대기한 프로세스를 높은 우선순위 큐로 이동 가능 (Aging 기법 활용)
✔ 우선순위가 낮을수록 Time Quantum 증가
✔ 긴 프로세스는 낮은 우선순위로 이동, 짧은 프로세스는 높은 우선순위 유지
✔ 기아 현상 방지 가능
➡ 현대 운영체제에서는 대부분 MLFQ를 사용! 🚀
