[Operating System] CPU 스케줄링 : 알고리즘

다양한 CPU 스케줄링 알고리즘에 대해 정리하였습니다.

참조 : 인프런 '개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제'

---

< 선입 선처리 스케줄링 >

FCFS (First Come First Served) 스케줄링

• 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링 방식
• 먼저 CPU를 요청한 프로세스부터 CPU 할당

 

선입 선처리 스케줄링 이미지

 

[ 단점 ] : 프로세스들이 기다리는 시간이 매우 길어질 수 있다( = 호위 효과)는 부작용이 있습니다.

 

 

---

< 최단 작업 우선 스케줄링 >

SJF (Shortest Job First) 스케줄링

• 선입 선처리 스케줄링의 호위 효과를 방지하기 위한 스케줄링
• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
• 기본적으로 비선점형 스케줄링이지만, 선점형 스케줄링 방식으로도 구현할 수 있습니다.

 

최단 작업 우선 스케줄링 이미지

 

[ 장점 ] : 호위 효과를 방지할 수 있습니다.

 

 

---

 

< 라운드 로빈 스케줄링 >

RR (Round Robin) 스케줄링

• 선입 선처리 + 타임 슬라이스 (time slie) 방식의 선점형 스케줄링
  (타임 슬라이스 : 각 프로세스가 cpu를 사용할 수 있는 정해신 시간)
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 방식
• 정해진 시간동안에 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)

 

라운드 로빈 스케줄링 이미지

 

: 라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 중요합니다.

 

 

---

< 최소 잔여 시간 우선 스케줄링 >

SRT (Shortest Remaining Time) 스케줄링

• 최단 작업 우선 + 라운드 로빈 방식의 선점형 스케줄링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

 

 

---

< 우선순위 스케줄링 >

PS ( Priority Scheduling ) 스케줄링

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
  (우선순위가 같은 프로세스들은 선입 선처리로 스케줄링)
• 최단작업 우선 스케줄링과 최소잔여 시간 스케줄링 방식은 모두 우선순위 스케줄링 방식에 포함됩니다.
• 선점형 스케줄링과 비선점형 스케줄링 방식 모두 구현이 가능합니다.

 

우선순위 스케줄링 이미지

 

[ 단점 ] : 우선순위 높은 프로세스 먼저 실행하기 때문에, 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 기아(starvation) 현상이 발생할 수 있습니다. 이를 방지하기 위해 에이징(Aging) 기법을 도입할 수 있습니다.

 

---

[ 에이징(Aging) 기법 ]

: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

에이징 기법 이미지

 

 

---

< 다단계 큐 스케줄링 >

MQS ( Multilevel Queue Scheduling ) 스케줄링

• 우선순위별로 준비 큐를 여러 개 사용하는 우선순위 스케줄링의 발전된 형태
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 보통 비선점형 스케줄링으로 구현되지만, 큐 간 우선순위에 따라 선점형 스케줄링으로도 구현될 수 있습니다.

 

다단계 큐 스케줄링 이미지

 

[ 장점 ] : 프로세스를 유형별로 처리하기 쉬워집니다.

[ 단점 ] : 이 또한 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 기아(starvation) 현상이 발생할 수 있습니다.

 

 

---

< 다단계 피드백 큐 스케줄링 >

MFQS ( Multilevel Feedback Queue Scheduling ) 스케줄링

• 큐 간의 이동이 가능한 다단계 큐 스케줄링입니다.
• 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는( = 에이징) 방식입니다.
• 선점형 스케줄링입니다.
• CPU 스케줄링 방식의 가장 일반적인 형태입니다.

012

다단계 피드백 큐 스케줄링 동작 과정

: 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아집니다.

 

 

---

 

다단계 피드백 큐 스케줄링 이미지