[운영체제] 3-4. (2) CPU 스케줄링 (CPU Scheduling)

CPU 스케줄링 알고리즘

 

 운영체제는 여러 프로세스/스레드에 CPU를 할당할 때 여러 가지 스케줄링 알고리즘을 사용한다. 다음은 가장 대표적인 7가지 스케줄링 알고리즘에 대한 설명이다.

 

💡FCFS (First Come First Served)

 

FCFS

• 특징 : 준비 큐에 먼저 들어온 순서대로 CPU를 할당
• 장점 : 구현이 매우 단순, 공정하게 보임
• 단점 : 긴 작업이 앞에 있으면 전체가 지연되는 호위 효과(Convoy Effect) 발생

 

💡SJF (Shortest Job First)

 

SJF

•  특징
  • 준비 큐에 들어온 프로세스 중 실행 시간이 가장 짧은 프로세스를 먼저 실행
  • 비선점/선점형 모두 구현 가능 : 뒤에서 설명할 SRT(최소 잔여 시간 우선)는 SJF의 선점형 버전
• 장점 : 평균 대기 시간 최소화
• 단점 : 실행 시간이 긴 프로세스가 계속 밀리는 기아 현상(starvation) 발생 가능

 

💡RR (Round Robin)

• 특징
  • 대표적인 선점형 스케줄링
  • 준비 큐에 들어온 순서대로 정해진 시간(타임 슬라이스, time slice)만큼 CPU 할당
  • 정해진 시간 모두 사용하고도 완료되지 않으면 문맥 교환이 발생해 다시 큐의 맨 뒤에 삽입된다.
• 장점 : 공정성/응답성 우수, 여러 프로세스가 번갈아 실행됨
• 단점 : 타임 슬라이스가 너무 짧으면 오버헤드 증가, 너무 길면 FCFS와 유사

 

💡SRT (Shortest Remaining Time)

• 특징 : SJF의 선점형 버전
  
  • 남아 있는 실행 시간이 가장 짧은 프로세스를 실행
  • 새로운 프로세스가 들어올 때마다 남은 시간 비교해 더 짧으면 바로 선점
• 장점 : 평균 대기 시간 최소화
• 단점 : 긴 작업 기아(starvation) 발생 가능, 구현 복잡

 

💡우선순위 (Priority)

• 특징 : 각 프로세스에 우선순위를 부여, 가장 높은 우선순위 프로세스부터 실행
• 단점 : 낮은 우선순위 프로세스가 계속 밀릴 수 있음(기아/starvation)
• 해결 : 에이징(Aging) 기법 적용—오랫동안 대기한 프로세스의 우선순위 점진적으로 상승
• 선점/비선점형 모두 가능

 

💡MLQ (Multilevel Queue)

• 특징 : 우선순위/특성에 따라 여러 개의 준비 큐 사용, 각 큐는 고정된 우선순위를 가짐
• 실행 방식
  1. 가장 높은 우선순위 큐의 프로세스를 먼저 모두 실행
  2. 그 다음 큐, ... 순으로 실행
• 단점 : 큐 사이 이동이 불가해, 낮은 우선순위 큐에 있는 프로세스가 오랫동안 실행 못할 수 있음(기아).

 

💡MLFQ (Multilevel Feedback Queue)

• 특징 : 여러 개의 준비 큐를 두고, 프로세스가 실행 특성에 따라 큐 사이를 이동할 수 있음
  • CPU를 오래 사용하면 → 낮은 우선순위 큐로 이동
  • 짧게 사용/오래 기다리면 → 높은 우선순위 큐로 이동(에이징 적용)
• 장점 : 다양한 프로세스 특성을 효율적으로 관리, 기아 문제 해결 가능
• 운영체제에서 많이 사용되는 고급 스케줄링 알고리즘

---

출처

https://www.hanbit.co.kr/store/books/look.php?p_code=B3079890360

이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접