💻 CPU 스케줄링 알고리즘

 

운영체제는 CPU를 효율적으로 사용하기 위해 다양한 CPU 스케줄링 알고리즘을 사용합니다. 각각의 알고리즘은 서로 다른 특징과 장단점을 가지고 있어, 상황에 따라 적절한 선택이 필요합니다. 이번 글에서는 주요 CPU 스케줄링 알고리즘을 빠짐없이 정리해 보았습니다.

본 내용은 <혼자 공부하는 컴퓨터 구조 + 운영체제>를 바탕으로 만들어졌습니다.

---

📌 1. 선입 선처리 스케줄링 (First Come First Served, FCFS)

방식: 비선점형
특징: 준비 큐에 도착한 순서대로 처리

• 가장 단순한 스케줄링 방식입니다.
• CPU 요청 순서대로 프로세스를 처리하여 공정하게 보이지만, 긴 작업이 먼저 도착할 경우 나중에 도착한 짧은 작업이 오래 기다리는 호위 효과(convoy effect) 현상이 발생합니다.
• 예시:
  • 프로세스 A(17ms), B(5ms), C(2ms)가 차례로 들어온 경우, C는 2ms의 작업을 위해 22ms를 기다려야 합니다.

---

📌 2. 최단 작업 우선 스케줄링 (Shortest Job First, SJF)

방식: 기본적으로 비선점형 (선점형 구현도 가능)
특징: CPU 이용 시간이 가장 짧은 프로세스를 우선 처리

• 호위 효과를 방지할 수 있습니다.
• 짧은 프로세스를 먼저 처리하여 평균 대기 시간이 가장 짧습니다.
• 선점형으로 구현하면 **최소 잔여 시간 우선(SRT)**이 됩니다.

---

📌 3. 라운드 로빈 스케줄링 (Round Robin)

방식: 선점형
특징: 각 프로세스에 일정한 타임 슬라이스(quantum)를 부여하고 순환 처리

• 모든 프로세스에 균등한 CPU 사용 기회를 제공합니다.
• 타임 슬라이스가 너무 크면 FCFS와 비슷한 문제가 발생하며, 너무 작으면 잦은 문맥 교환으로 CPU 효율이 떨어집니다.
• 예시:
  • 프로세스 A(11ms), B(3ms), C(7ms)이고 타임 슬라이스가 4ms라면, 순차적으로 실행되고 남은 작업은 큐 뒤로 돌아가 처리됩니다.

---

📌 4. 최소 잔여 시간 우선 스케줄링 (Shortest Remaining Time, SRT)

방식: 선점형
특징: 최단 작업 우선 스케줄링과 라운드 로빈의 혼합형

• 남은 작업 시간이 가장 짧은 프로세스를 우선적으로 선택합니다.
• 라운드 로빈처럼 타임 슬라이스를 적용하지만, 매번 작업 시간이 짧은 프로세스부터 처리합니다.

---

📌 5. 우선순위 스케줄링 (Priority Scheduling)

방식: 선점형 또는 비선점형 가능
특징: 우선순위가 높은 프로세스부터 처리

• 프로세스에 우선순위를 부여해 우선순위가 높은 작업을 먼저 실행합니다.
• 단점은 우선순위가 낮은 프로세스가 계속 밀려나는 기아(starvation) 현상이 발생할 수 있다는 점입니다.
• 이를 방지하기 위해 오래 기다린 프로세스의 우선순위를 높이는 에이징(aging) 기법을 사용합니다.

<기아 현상>

<에이징 기법>

---

📌 6. 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

방식: 큐별로 우선순위를 나눔
특징: 여러 개의 큐를 사용하여 프로세스를 분류하여 처리

• 프로세스 유형에 따라 여러 준비 큐를 만들어 우선순위가 높은 큐부터 순차적으로 처리합니다.
• 큐마다 서로 다른 타임 슬라이스나 스케줄링 알고리즘을 적용할 수 있습니다.
• CPU 집중형, 입출력 집중형, 사용자 상호작용형 등 다양한 프로세스 분류에 적합합니다.

---

📌 7. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

방식: 큐 간 이동이 가능한 방식
특징: 프로세스의 특성에 따라 큐 간 이동과 우선순위 조정

• 다단계 큐 스케줄링을 발전시킨 형태로, 프로세스가 큐 사이를 이동할 수 있습니다.
• 프로세스가 긴 CPU 시간을 사용하면 점차 낮은 우선순위 큐로 내려가고, 너무 오래 기다리면 다시 높은 우선순위 큐로 올라가 에이징 효과를 냅니다.
• 프로세스의 성격에 따라 유연하게 우선순위를 관리할 수 있어 가장 일반적으로 사용되는 방식 중 하나입니다.

---

🔖 요약 및 활용 팁

 

알고리즘	방식	주요 특징	장점	단점
FCFS	비선점형	FIFO 방식	단순	호위효과
SJF	비선점형/선점형	작업 시간이 짧은 프로세스 우선	평균 대기시간 단축	긴 프로세스 기아 가능성
Round Robin	선점형	타임 슬라이스 기반	공정성	잦은 문맥교환
SRT	선점형	잔여 작업 시간 짧은 순서	높은 응답성	관리 복잡성
Priority	선점형/비선점형	우선순위 기반	중요 작업 우선 처리	기아 현상
Multilevel Queue	큐 우선순위	여러 큐 사용	분류 관리 효율적	큐 간 이동 불가
Multilevel Feedback Queue	큐 간 이동 가능	유연한 우선순위 관리	기아 방지 가능	복잡한 구현