[OS] CPU 스케줄링 알고리즘의 종류

CPU 스케줄링 알고리즘은 매우 다양해서 운영체제 저마다 서로 다른 스케줄링 알고리즘을 사용하고 있어요. 오늘은 각 스케줄링 알고리즘을 통해 프로세스들을 스케줄링 하는 실질적인 방법을 알아봅시당.🧐

---

 

스케줄링 알고리즘의 종류

🧶 선입 선처리 스케줄링

• FCFS(First Come First Served) 스케줄링이라고도 부름
• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링 방식
• 때때로 비효율적인 호위효과가 발생함

🙋🏻‍♀️ 호위효과가 뭐죠?

예를 들어, 17ms 동안 CPU를 이용하는 프로세스 A, 5ms 동안 CPU를 이용하는 프로세스 B, 2ms 동안 CPU를 이용하는 프로세스 C가 순서대로 있다면 C는 고작 2ms를 실행하기 위해 22ms(17ms+5ms)라는 긴 시간을 기다려야만 하는데, 이를 호위효과(convoy effect)라고 합니다.

🧶 최단 작업 우선 스케줄링

• 호위 효과를 방지하기 위해 CPU 이용 시간이 짧은 프로세스부터 실행하는 방식
• SJF(Shortest Job First) 스케줄링으로도 불림
• 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음(최소 잔여 시간 우선 스케줄링)

 

 

🧶 라운드 로빈 스케줄링

• 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식
• 타임 슬라이스란, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 방식
• 선점형 스케줄링
• 타임 슬라이스 크기가 중요함. 너무 크면 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 발생하고, 너무 작으면 문맥 교환에 발생하는 비용이 커 비효율적

 

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

• SRT(Shortest Remaining Time) 스케줄링으로도 불림
• 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식
• 최소 잔여 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, 남은 작업 시간이 가장 적은 프로세스 순서대로 사용됨

 

 

🧶 우선순위 스케줄링

• 프로세스들에 우선순위를 부여함
• 가장 높은 우선순위를 가진 프로세스부터 실행함
• 우선순위 스케줄링은 우선순위가 낮은 프로세스는 계속해서 연기되는 기아(starvation) 현상이 발생함
• 기아 현상을 방지하기 위해 에이징(aging)기법을 사용하는데, 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

 

 

🧶 다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리함
• 큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있음

 

 

🧶 다단계 피드백 큐 스케줄링

• 다단계 큐 스케줄링의 발전된 형태
• 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없기 때문에 우선순위가 낮은 프로세스는 계속 연기되는 기아 현상이 발생할 수 있음
• 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있음
• 새로 준비 상태가 된 프로세스는 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스)동안 실행됨
• 타임 슬라이스 동안 작업이 모두 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행됨
• 즉, 다단계 피드백 큐 스케줄링 알고리즘은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘임
• 가장 일반적인 CPU 스케줄링 알고리즘