안녕하세요. 코딩도치입니다~
오늘은 운영체제 내용중에서 CPU 스케줄링에 대해서 공부해보려고 합니다!
CPU 스케줄링은 멀티프로그램 환경에서 기본이 되는 것입니다.
다음과 같이 여러개의 프로세스가 메모리에 로드 되어있고, 각 프로세스는 돌아가면서 CPU를 선점하여 실행되게 됩니다.
이렇게 많은 프로세스 중에서 어떤 프로세스를 실행할 것인지 결정하고, CPU를 할당하는 작업을 CPU 스케줄링이라고 합니다.
CPU는 속도가 매우 빠르기 때문에 어떠한 작업을 처리하고 노는 시간이 많았습니다.
이러한 CPU의 Utilization(사용률)을 높이기 위해서 즉, CPU가 노는 시간이 없도록 하는 데에 필요한 것이 CPU 스케줄링입니다.
결국 CPU 스케줄링의 문제는 대기중인 프로세스 중에서 어떤 프로세를 선택할 것인가 입니다.
스케줄러의 우선순위 부여 방식에는 선점형(Preemptive)과 비선점형(Non-Preemptive)이 있습니다.
선점형(Preemptive) 스케줄링은,
스케줄러가 CPU를 선점중인 프로세를 쫓아내고(Running -> Ready) 새로운 프로세스에 CPU를 할당하는 것입니다.
비선점형(Non-Preemptive) 스케줄링은,
어떤 프로세스가 CPU를 선점하면 그 프로세스가 끝나기 전까지는 간섭하지 않는 것입니다. 즉, 스위칭이 이루어지지 않습니다.
CPU 스케줄링에는 다음과 같은 4가지 경우의 상태 변화가 있습니다.
1. Running -> Waiting
2. Running -> Ready
3. Waiting -> Ready
4. Terminate
1번과 4번의 경우에는 비선점형(Non-Preemptive) 방식입니다.
2번과 3번의 경우에는 선점형(Preemptive) 또는 비선점형(Non-Preemptive) 중에 선택을 할 수 있는데,
효율상 선점형(Preemptive) 방식을 사용하는 것이 대부분입니다.
스케줄링 목표는 다음과 같습니다.
- CPU Utilization : CPU가 노는 꼴은 못봐
- Throughput : 단위시간 내에 완료되는 프로세스의 수를 높여야해
- Turn-around time : 프로세스 실행시간을 최소화시켜야해
- Waiting time : 프로세스가 레디 큐에서 대기하고 있는 시간을 최소화시켜야해
- Response time : 주로 UI(사용자들은 기다리는 거 싫어함)
(여기서 Waiting time을 최소화할 수 있다면 다른 목표들도 자동적으로 이룰 수 있습니다!)
이제부터는 위의 목표를 가능하게 해주는 스케줄링 알고리즘에 대해서 살펴보겠습니다.
스케줄링 알고리즘
- FCFS(First-Come, First-Served)
먼저 요청이 들어온 프로세스가 먼저 할당이 되는 것으로, 비선점형(Non-Preemptive)방식입니다.
아주 간단하기 때문에 구현이 쉽다는 장점이 있지만,
평균 Waiting time이 최소가 아니라는 단점이 있습니다.
각 프로세스의 실행시간에 따라서 프로세스의 실행 순서를 바꾸게 되면 더 효율적일 수 있기 때문입니다.
- SJF(Shortest Job First)
CPU 쓰는 시간이 짧은 프로세스를 먼저 할당하는, Non-Preemptive 방식입니다.
이 알고리즘 같은 경우 평균 Waiting time이 최적인 알고리즘입니다.
하지만 실제로 구현을 할 수 없다는 문제가 있습니다.
미리 프로세스가 '나는 이만큼의 시간을 사용할꺼야' 하고 들어온다면 좋겠지만,
실제로는 다음에 올 프로세스의 CPU 사용 시간(CPU burst time)을 알 수가 없기 때문입니다.
- SRTF(Shortest Remaining Time First)
SJF에 Preemptive 방식을 적용한 것입니다.
그렇게되면 남은 실행시간이 가장 짧은 프로세스를 먼저 할당하게 됩니다.
예를 들어 현재 실행중인 5초의 실행시간이 남은 프로세스가 있다고 해봅시다.
이때, 새로운 1초짜리 프로세스가 레디큐에 들어온다면,
스케줄러는 현재 실행중인 프로세스를 쫓아내고 1초짜리 프로세스를 할당합니다.
이것도 당연히 구현할 수 없겠죠??
또한 SJF와 SRTF 알고리즘은 Starvation 현상이 발생합니다.
게속해서 짧은 시간의 프로세스들이 들어온다면 CPU를 할당받지 못하고 레디큐에 계속해서 남아있는 프로세스가 생길 수 있는 것입니다.
- RR(Round-Robin)
Preemptive FCFS with a time quantum 입니다.
즉, 시분할(time-sharing)을 통해 정해진 시간만큼만 프로세스가 실행되는데 이때 Preemptive 방식으로 스위칭이 일어나고
먼저 들어온 프로세스가 먼저 실행되는 방식(FCFS)입니다.
이러한 구현을 위해서 레디 큐의 경우 Circular Queue로 구현하게 됩니다.
time quantum이 크면 효율성이 떨어지게 되고, 작으면 잦은 Context-Switch로 오버헤드가 커지기 때문에
time quantum의 사이즈를 적절히 잡는 것이 중요합니다.
- Priority-based
앞에서 알아본 SJF, SRTF 알고리즘도 Priority-based 알고리즘의 일종입니다.
프로세스의 중요도에 따라서 다음 프로세스를 선택하는 것이죠.
마찬가지로 Starvation 문제가 발생하게 됩니다.
이러한 Starvation 문제는 시간이 지날 수록 기다리는 프로세스의 우선순위를 점차적으로 높여주는 Aging 기법을 적용하여 해결할 수 있습니다.
- MLQ(Multi-Level Queue)
여러개의 Queue를 사용하는 알고리즘입니다.
각 Queue는 우선순위를 가지고 있고, 우선순위가 높은 Queue에 있는 프로세스들이 먼저 실행되는 것입니다.
이때 각 Queue는 독립적인 스케줄링 알고리즘을 가지고 있습니다.
여기서 발생하는 문제 또한 Starvation입니다.
- MLFQ(Multi-Level Feedback Queue)
MLQ의 Starvation 문제를 보완한 알고리즘입니다.
프로세스는 우선순위가 변경되며 큐 사이를 이동할 수 있습니다.
그래서 한번 cpu를 할당받은 프로세스는 우선순위가 조금 낮은 큐로 이동을 하는 방식입니다.
이때 우선순위에 따라 큐의 time quantum 사이즈를 달리하여, 낮은 우선순위 큐의 프로세스가 cpu를 할당받았을 때 더 오랜시간 사용할 수 있도록 합니다.
현대에 현업에서 가장 많이 쓰이는 방식입니다.
감사합니다.