1. CPU Scheduling 이란?
여러 프로세스가 cpu 코어를 공유하며 실행될 때, 어떤 프로세스가 cpu를 선점할지 결정하는 방법
프로그램을 실행할 때 디스크에서 가져와서 메모리에 프로그램을 넣습니다. cpu에서 메모리에 있는 프로그램을 실행하면 프로세스가 됩니다. 이때 어떤 프로세스를 수행할 지를 결정을 해야하는데 이것을 스케줄러가 도와줍니다.
우리가 프로세스 수행순서를 결정하는 이유는 cpu의 코어개수보다 프로세스가 더 많다면 한 번에 모든 프로세스를 수행할 수 없으므로 운선순위(프로세스 중요도), 작업크기, 대기시간을 고려하여 프로세스를 실행시킬 수 있습니다.
우선순위는 기준에 따라 다를 수 있습니다. 예를 들어 가게에서 음식을 먹기위해 사람들이 줄을 기다리고 있다면 먼저 온 손님을 받아야 합니다. 하지만 자리가 2자리만 있고 기다리는 인원 수가 4명, 3명, 2명, 4명 이러한 순서로 있다면 4명과 3명은 먼저 왔지만 먹을 수 없으므로 효율적으로 운영하기 위해 적은 인원이 2명이 먼저 들어갈 수 있습니다.
비슷한 원리로 프로그램도 작업 크기가 작은 프로세스가 먼저 cpu를 선점할 수 도 있고, 대기 시간이 짧은 작업이 먼저 cpu를 선점할 수 있습니다.
2. CPU Scheduling의 목적
아래는 프로세스 생명주기 입니다.
최고의 성능을 위해 어떤 프로세스에 cpu를 선점할지가 중요합니다. 스케줄링 관점에서 가장 중요한 단계는 waiting입니다. 이 단계에서 여러 프로세스가 대기 중일텐데 이 중 어떤 것을 선택하는지가 중요합니다.
즉 프로세스가 안정적이고 효율적으로 수행하기 위해서는 중요도에 따라 우선순위를 배정해야합니다.
cpu Scheduling의 목적을 정리하면 다음과 같습니다.
- 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 그 과정에서 특정 프로세스가 배제되면 안된다.
- 효율성 : 시스템 자원이 유휴 시간이 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 준다.
- 안정성 : 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호한다.
- 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
- 반응 시간 보정 : 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지 : 특정 프로세스 작업이 무한히 연기되면 안된다.
3. CPU Scheduling 종류 및 동작방식
비선점과 선점으로 구별할 수 있습니다.
비선점 스케줄링은 작업을 하는 도중 다른 프로세스가 작업을 중단시킬 수 없습니다.
- 비선점 스케줄링 특징
- 일괄 처리 방식에 유용
- 공정
선점 스케줄링은 작업을 하는 도중 다른 프로세스가 작업을 중단 시키고 cpu를 차지할 수 있습니다.
- 선점 스케줄링 특징
- 많은 오버해드
- 시분할 시스템에 유용
아래의 방법은 각 작업시간을 알고 있다는 가정이 있습니다.
평가 항목으로는 응답시간, 반환시간으로 두겠습니다.
비선점 스케줄링
-
First In First Out
FIFO 스케줄링 기법은 먼저 들어온 작업이 먼저 수행되는 기법입니다.
작업이 순서대로 A, B, C로 들어온다면 A가 가장 빨리 왔으므로 먼저 cpu를 점유합니다. 그 후에는 마찬가지로 작업이 먼저 온 순서대로 cpu를 점유합니다.
반환시간 : (10 + 20 + 30) / 3 = 20
응답시간 : (0 + 10 + 20) / 3 = 10
- Shortest Job First
SJF 스케줄링 기법은 짧은 수행시간을 가진 작업이 먼저 수행되는 기법입니다.
작업이 A, B, C로 0초에 동시에 온다면 수행시간이 짧은 작업이 먼저 cpu를 선점합니다.
반환시간 : (10 + 20 + 120) / 3 = 50
응답시간 : (0 + 10 + 20) / 3 = 10
선점 스케줄링
-
SRT
Shortest Remain Time
SJF를 보완한 기법으로 수행시간이 가장 적은 작업이 우선적으로 cpu를 점유합니다.
작업이 A가 먼저오고 B,C가 후에 옵니다. A가 우선 cpu를 점유하고 있다가 B, C가 올 때 A의 작업을 중단하고 B, C의 작업이 수행됩니다. 작업이 끝나면 다시 A가 작업을 시작합니다.
반환시간 : (10 + 10 + 20 + 110) / 3 = 50
응답시간 : (0 + 10 + 20) / 3 = 10
- RR
Round - Robin
시분할 기법을 사용해 작업이 cpu를 선점합니다.
일정 시간이 지나면 작업을 중단하고 다음 작업을 진행합니다.
반환시간 : (13 + 14 + 15 ) / 3 = 14
응답시간 : (0 + 1 + 2) / 3 = 1
정리를 하면 다음과 같습니다.
4. 현대의 CPU Scheduling
위의 4종류에는 문제점은 각 프로세스의 작업시간을 알고있다는 가정하에 평가한 것입니다.
만약 각 작업시간을 모른다면 위의 방법들을 사용하기에는 까다롭습니다.
그래서 나온 기법이 멀티 레벨 피드백 큐(multi-level-feedback-queue)입니다.
멀티 레벨 피드백 큐
이름에서 알 수 있듯이 여러 단계의 큐가 존재합니다. 또한 각 큐마다 우선순위가 달리 부여됩니다.
멀티 레벨 피드백 큐의 규칙은 다음과 같습니다.
- 규칙1: 우선순위(A) > 우선순위(B)일 경우, A가실행
- 규칙2: 우선순위(A) = 우선순위(B), A와B는 RR방식으로 실행
- 규칙3: 작업이 시스템에 들어가면 최상위 큐에배치
- 규칙4: 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 낮은 우선순위로 작업 이동
- 규칙5: 일정주기 S가 지난 후,시스템의 모든작업을 최상위큐로 이동
MLFQ는 다양한 우선순위의 프로세스를 공정하게 처리하면서도 중요한 프로세스에 우선권을 부여하고 CPU 사용을 효율적으로 관리하는 데 효과적인 방법 중 하나입니다. 그러나 적절한 파라미터 설정 및 조절이 필요하며, 과도한 큐 이동이나 설정 오류로 인해 부정확한 동작을 할 수도 있으므로 조심해야 합니다.
