[운영체제] CPU 스케줄링 정리
🎯 CPU 스케줄링이란
CPU 스케줄링 은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분합니다. 이러한 스케줄링은 스케줄러(Scheduler) 라는 모듈을 사용합니다.
기본적으로 프로세스는 CPU 만 사용하는 단계 (CPU burst) 와 I/O 만 작업하는 단계 (I/O burst) 의 반복으로 구성된 사이클의 형태로 구성됩니다.
운영체제는 여러개의 프로세스를 효율적으로 실행시키기 위해 스케줄링 큐 라는 자료구조를 사용합니다. 스케줄링 큐는 프로세스를 실행시키기 위해 프로세스들을 잠시 보관하는 역할을 담당하고, 스케줄링 큐에 들어간 프로세스들을 실행시킵니다.
(단 스케줄링 큐는 선입선출(FIFO) 방식으로 실행되는건 아닙니다.)
스케줄링 큐에는 준비 큐(Ready Queue) 와 대기 큐(Waiting Queue) 가 있습니다. 준비 큐는 CPU 를 이용하기 위해 기다리는 줄이고, 대기 큐는 입출력 장치를 이용하기 위해 프로세스가 기다리는 줄 이라 생각하면 됩니다.
CPU 스케줄링은 규모에 따라 장기, 중기, 단기 스케줄링으로 구분됩니다. 이에 대해 먼저 알아보도록 합시다.
✅ 장기 스케줄링 (Long-term scheduler)
장기 스케줄링은 시스템으로 돌아오는 작업 (Job) 을 선택해 어떤 작업을 메모리에 올릴지 결정하는 과정입니다. 주로 배치 시스템에서 사용되며, 작업의 도착 시점과 빈도에 따라 작업 큐에 있는 작업을 선택합니다.
✅ 중기 스케줄링 (Medium - term Scheduling)
중기 스케줄링은 메모리에 올라와 있는 프로세스 중 일부를 swap out(스왑 아웃) 하거나 swap in(스왑 인) 하여 메모리의 사용을 최적화 하는 과정입니다. 주로 멀티 태스킹 환경에서 메모리 관리의 일환으로 수행됩니다.
✅ 단기 스케줄링 (Short-term Scheduling)
단기 스케줄링은 CPU 스케줄링이라고도 하며, 준비 상태의 프로세스 중에서 어느 프로세스를 다음에 실행할지를 결정하는 과정입니다. 주로 운영체제의 커널에서 수행됩니다.
이러한 CPU 스케줄링은 모든 프로세스가 공평하게, 효율적으로 자원이 할당 될 수 있게 도와주는것을 목적으로 합니다. 하지만 다양한 상황에서 프로세스를 공평하게 할당되는건 쉽지 않습니다. 때문에 다음과 같은 고려사항들을 이해하고 그에 맞는 알고리즘들이 설계됐습니다.
- 공평성 : 프로세스에게 자원을 배분하는 과정이 공평해야 합니다.
- 효율성 : 시스템 자원이 쉬는 시간이 없어야 합니다.
- 안정성 : 중요 프로세스들은 우선권을 주어야 합니다. 또한 프로세스가 증가해도 안정적으로 동작해야 합니다.
- 확장성 : 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되어야 합니다.
🎯 스케줄링 고려 사항
선점형 스케줄링과 비 선점형 스케줄링에 대해 먼저 설명드리겠습니다.
✅ 선점형 스케줄링이란 과 비 선점형 스케줄링
선점 (preemptive) 이란 빼앗을 수 있음을 말합니다. 즉 선점형 스케줄링은 A 라는 프로세스가 CPU 를 할당받으면 이렐 운영체제가 강제로 회수해 다른 B 프로세스를 실행할 수 있음을 뜻합니다.
반대로 비 선점 은 한 프로세스의 동작이 끝날때까지 다른 프로세스가 실행될 수 없음을 뜻합니다.
선점형 스케줄링 : 실행 상태에 있는 프로세스의 작업을 중답하고 새로운 작업(프로세스) 가 실행될 수 있습니다. 하지만 선점형 프로세스는 프로세스가 교체되는 과정 (Context switch) 에서 오베헤드가 발생할 수 있는 문제점이 있습니다.
비 선점형 스케줄링 : 어떤 프로세스가 실행 상태에 들어가면 그 프로세스가 끝나거나 CPU 를 자진 반납하는 경우가 아니면 계속 실행되는 것을 말합니다. 이는 Context switch 에 대한 오버헤드도 없고 스케줄러가 할 일도 적어져 효율적일 수 있으나 전체 시스템의 처리율이 떨어지게 됩니다.
✅ 프로세스 우선순위
프로세스간에도 우선순위가 존재할 수 있습니다. 프로세스는 크게 커널 프로세스와 일반 프로세스로 나위는데 CPU 스케줄러는 보통 커널 프로세스를 높은 우선순위에 둡니다. 커널과 관련된 작업들은 보통 일반 프로세스보다 중요하기 때문입니다. 여기서 우선순위가 높다는 것은 일반적으로 더 빨리 자주 실행된다는 의미입니다.
🎯 CPU 스케줄링 알고리즘
다양한 CPU 스케줄링 알고리즘이 있습니다. 각각의 스케줄링 알고리즘에 대해 알아보겠습니다.
✅ FCFS(First Come First Served) 선입 선처리 스케줄링 알고리즘
FCFS 알고리즘은 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링 입니다. 먼저 CPU 를 요청한 프로세스부터 CPU 에 할당합니다.
하지만 이러한 방식의 스케줄링은 호위 효과라는 부작용을 야기할 수 있습니다.
호위 효과란?
호위 효과 란 프로세스들이 기다리는 시간이 매우 길어질 수 있음을 말합니다.
(선입 선처리 스케줄링 알고리즘에서 마지막에 삽입된 프로세스는 대기 시간이 길어집니다.)
✅ SJF(Shortest Job First) 최단 작업 우선 스케줄링
SJF 스케줄링은 선입 선처리 스케줄링에서 발생하는 호위 효과를 방지하기 위해 프로세스 처리 시간이 짧은 프로세스부터 우선적으로 실행시키는 스케줄링 방식입니다.
즉, CPU 사용시간이 긴 프로세스는 나중에 실행하고 CPU 사용 시간이 짧은 프로세스는 먼저 실행합니다.
✅ RR(Round Robin) 라운드 로빈 스케줄링
선입 선처리 스케줄링 + 타임 슬라이스(Time Slice) 가 합쳐진 스케줄링 알고리즘입니다. 타임 슬라이스란 각각의 프로세스가 CPU 를 사용할 수 있는 정해진 시간입니다. 즉, 정해진 시간(타임 슬라이스) 만큼 돌아가며 CPU 를 이용하는 선점형 스케줄링 입니다.
정리하자면 라운드 로빈 스케줄링은 큐에 삽입된 프로세스들이 순서대로 CPU 를 이용하되 정해진 시간만큼 이용합니다. 정해진 시간을 모두 사용했음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입합니다.(문맥 교환)
하지만 RR 에서 주의해야할 점이 하나 있습니다. 만약 타임 슬라이스가 너무 커져버리면 선입 선처리 스케줄링에서 언급했던 호위효과라는 부작용을 야기할 수 있기때문에 타임 슬라이스에 대한 시간 설정을 잘 고려해야합니다.
✅ SRT(Shortest Remaining Time) 최소 잔여 시간 우선 스케줄링
최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링을 합친 알고리즘입니다. 즉, 정해진 시간만큼 CPU 를 이용하되, 다음으로 CPU 를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택하는 스케줄링 방식입니다.
✅ 우선순위 스케줄링
프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 알고리즘입니다. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링 합니다. 이러한 스케줄링 기법은 우선순위가 낮은 프로세스는 실행을 연기합니다.
이를 방지하기 위한 기법을 에이징(againg) 이라 합니다. 오랫동안 대기한 프로세스의 우선순위를 점차 높여, 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 기법입니다. 이러한 기법은 우선순위가 낮은 프로세시일지라도 언젠가는 우선순위가 높아져 프로세스가 정상적으로 실행될 수 있습니다.
정리하자면, 우선순위 스케줄링은 기하 현상(스타베이션) 이라는 우선순위가 낮은 프로세스가 실행될 수 없는 문제를 내포하고 있는데, 이를 에이징 기법을 이용해 해결했습니다.
✅ 다단계 큐 스케줄링
우선순위 스케줄링의 발전된 형태입니다. 우선순위 별로 준비 큐를 여러개 사용하는 스케줄링 방식입니다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리합니다. 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리합니다.
하지만 이러한 방식은 프로세스가 큐 간에 이동을 할 수 없는 문제가 있습니다. 즉 우선순위가 낮은 큐는 기하 현상이 발생할 수 있습니다. 이 문제를 해결하기 위해 등장한 것이 바로 아래에서 설명할 다단계 피드백 큐 스케줄링입니다.
✅ 다단계 피드백 큐 스케줄링
Multilevel feedback queue 스케줄링, 다단계 큐 스케줄링의 발전된 형태입니다. 큐 간의 이동이 가능한 다단계 큐 스케줄링입니다.
다단계 피드백 큐 스케줄링은 어떤 프로세스의 CPU 사용 시간이 길어지면 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에 너무 오래 있으면 우선순위를 높이는 방식을 사용합니다.
CPU 스케줄링의 가장 일반적인 형태입니다.
참고 자료 : https://www.youtube.com/watch?v=isj4sZhoxjk&list=PLYH7OjNUOWLUz15j4Q9M6INxK5J3-59GC&index=2