목차
- CPU 스케줄링이란?
- CPU 스케줄링이 필요한 상황
- CPU 스케줄링 성능 기준
- CPU 스케줄러 종류
- 장기 스케줄러
- 중기 스케줄러
- 단기 스케줄러
- CPU 스케줄링 알고리즘 분류 : 선점형 비선점형
- 선점형
- 비선점형
- CPU 스케줄링 알고리즘 종류
(1) FCFS (First Come, First Served)
(2) SJF (Shortest Job First)
(3) SRF/SRTF (Shortest Remaining First)
(4) Priority
(5) RR (Round Robin)
(6) MLQ (Multi Level Queue)
(7) MLFQ (Multi Level Feedback Queue)
1. CPU 스케줄링이란?
운영체제는 멀티 스레드를 제공함으로써, 우리가 컴퓨터를 사용할 때 동시에 여러 개의 프로그램이 동작할 수 있는 것처럼 보여준다. 하지만 CPU는 한 번에 하나의 스레드만 처리할 수 있는데, 어떻게 가능한걸까? 그건 바로 빠른 속도로 스레드를 교체하면서 작업을 처리함으로써 가능한 일이다.
이러한 스레드의 교체 작업은 어떤 스레드를 먼저 처리할지, 혹은 하나의 스레드가 CPU를 얼마나 사용하고 있는지 등에 CPU가 작업을 처리하는 양이 달라지며, 이것이 컴퓨터 성능과 직결된다. 따라서 스케줄러를 통해 CPU를 사용할 프로세스나 스레드를 스케줄링하는 것이다.
2. CPU 스케줄링이 필요한 상황
위의 프로세스 상태에 따라 CPU 스케줄링이 필요한 상황이 생긴다. 대부분의 컴퓨터는 CPU가 하나이므로 실행 중인 프로세스는 단 하나지만, 준비(Ready)나 대기(Blocked / Waiting) 상태의 프로세스는 여러 개 존재한다. 따라서 Ready Queue, Blocked Queue(= Waiting Queue)에서 프로세스들이 현태 상태를 벗어날 순서를 기다리고 있다.
- 실행에서 대기 상태가 될 때 (Running -> Blocked)
- 대기에서 준비 상태가 될 때 (Blocked -> Ready)
- 실행에서 준비 상태가 될 때 (Running -> Ready)
- 종료될 때 (Exit)
스케줄링은 우선순위가 존재하는 선점형, 우선순위가 없는 비선점형으로 분류할 수 있다. 1번과 4번의 경우에는 비선점 알고리즘을 사용하고, 그 외에는 선점형 알고리즘을 사용한다.
3. CPU 스케줄링 성능 기준
- CPU 이용률 (CPU Utilization) : 시간당 CPU를 사용한 시간의 비율
- 처리율 (Throughput, Bandwidth) : 시간당 CPU가 처리한 작업의 비율
- 응답 시간 (Response Time) : CPU를 점유하기 위해 걸린 총 시간
4. CPU 스케줄러 종류
CPU 스케줄링이 필요한 상황에서 잠깐 큐에 대한 언급을 했다. CPU 할당을 기다리는 Ready Queue, 자원 할당을 기다리는 Waiting Queue가 존재하며, 이러한 큐를 관리하는 스케줄러가 각각 존재한다.
1) 장기 스케줄러
: Long-term Scheduler, Job Scheduler라고도 부르며, 어떤 프로세스를 Ready Queue에 보낼지를 결정한다. 디스크에 있는 프로그램을 메모리에 올려야 실행 중인 프로그램, 즉 프로세스가 된다. 이때 메모리가 한정적이기 때문에 프로세스 생성에 관한 관리를 해주어야 하며, 이것이 Ready Queue에 들어갈 프로세스를 관리하는 것과 동일하다.
하지만 과거에 비해 메모리 용량이 커졌고, 많은 프로그램이 실행 중에 있더라도 메모리를 꽉 채워서 동작하지는 않는다. 따라서 현대 컴퓨터에서는 잘 사용하지 않는 스케줄러이다.
2) 중기 스케줄러
: 메모리에 올라간 프로세스의 수가 많으면, 실제 프로세스가 동작할 때 필요한 데이터를 저장해 둘 수 없다. 따라서 디스크 I/O에 저장해 데이터를 가져오기 등의 방법을 택하는데, 디스크에서 데이터를 읽고 저장하는 과정은 메모리보다 더 낮은 속도를 가지고 시스템 성능이 저하된다.
따라서 중기 스케줄러를 통해 프로세스 개수에 대한 관리를 하는 것이다. 앞서 장기 스케줄러는 "프로세스 생성"에 관리를 했다면, 중기 스케줄러는 "프로세스 개수"에 대한 관리를 한다.
프로세스 수를 관리하기 위해 메모리가 일정 사용량을 넘어가면, 프로세스를 디스크에 저장해 메모리 공간을 확보한다. 이것을 스왑 아웃(Swap Out)으로 부르며, 일정 시간 동안 사용하지 않았던 프로세스나 우선순위가 낮은 프로세스를 스왑 아웃한다.
3) 단기 스케줄러
: 사실상 장기, 중기 스케줄러 없이 단기 스케줄러를 이용해 CPU 효율을 끌어올리면 큐에 프로세스가 넘칠 일도 발생하지 않을 것이다. CPU의 효율을 끌어올릴 수 있는 단기 스케줄러는 Ready Queue에 있는 프로세스들의 우선순위를 결정하며, 프로세스를 빠르게 처리하기 위한 핵심 스케줄러이다.
미리 설정된 스케줄러 알고리즘에 따라 우선순위가 결정되며, 매우 빠르게 동작해야 하기 때문에 밀리 세컨드(ms) 이하의 시간 단위로 빈번하게 호출된다. 아래에 더 자세한 스케줄러 알고리즘을 설명하겠다.
5. CPU 스케줄링 알고리즘 분류
- 선점형
: 프로세스마다 우선순위가 존재해 더 낮은 우선순위를 가진 프로세스가 CPU를 필요로 한다면, 프로세스가 사용 중이던 CPU를 반환하고 더 낮은 우선순위의 프로세스에게 CPU를 먼저 사용할 수 있도록 한다.
- 비선점형
: 이미 하나의 프로세스가 CPU를 사용 중이라면 다른 프로세스가 CPU를 뺏을 수 없다. 이 때문에 컨텍스트 스위칭에 발생하는 비용은 적지만, 효율성 차이가 많이 나게 된다.
6. CPU 스케줄링 알고리즘 종류
1) FCFS (First Come, First Served)
(특징)
- 비선점형 스케줄링 방법이다.
- Ready Queue에 들어온 순서대로 처리한다.
(장점)
- 구현이 간단하다.
- 컨텍스트 스위칭에 발생하는 비용이 적다.
(단점)
- 응답 시간이 길어져 효율이 떨어질 수 있다.
- 실시간으로 처리해야 하는 대화형 시스템에 적절하지 못하다.
2) SJF (Shortest Job First)
(특징)
- 비선점형 스케줄링 방법이다.
- 실행 시간이 가장 짧다고 판단되는 프로세스를 먼저 처리한다.
(단점)
- 우선순위가 낮아 계속해서 CPU를 할당받지 못하는 기아 현상이 발생할 수 있다.
- CPU를 사용할 수 있는 시간을 예측하기 어렵다.
3) SRTF 혹은 SRF (Shortest Remaining Time First, Shortest Remaining First)
(특징)
- 선점형 스케줄링 방법이다.
- 프로세스가 큐에 들어올 때마다 스케줄링을 다시 한다.
(단점)
- 우선순위가 낮아 계속해서 CPU를 할당받지 못하는 기아 현상이 발생할 수 있다.
- CPU를 사용할 수 있는 시간을 예측하기 어렵다.
4) Priority
(특징)
- 더 높은 우선순위를 가지는 프로세스에게 CPU를 할당한다.
- 선점형은 더 높은 우선순위를 가진 프로세스가 CPU를 선점한다.
- 비선점형은 더 높은 우선순위를 가진 프로세스가 Ready Queue의 헤더 부분에 위치한다.
(단점)
- 우선순위가 낮아 계속해서 CPU를 할당받지 못하는 기아 현상이 발생할 수 있다.
** 대기하는 프로세스들의 우선순위를 점진적으로 높여주는 Againg을 통해 단점을 보완할 수 있다.
4) RR (Round Robin)
(특징)
- 선점형 스케줄링 방법이다.
- 현대에 사용하는 스케줄링 방법이며, 시분할 시스템을 위해 설계되었다.
- 각 프로세스는 동일한 크기의 시간(Time Quantum 혹은 Time Slice)을 할당받고, 할당된 CPU 점유에 대한 시간이 지나면 다시 Ready Queue의 끝으로 들어간다.
(장점)
- CPU 사용 시간이 랜덤할수록 효율적이다.
- 공정성이 보장된다.
(단점)
- CPU를 점유할 수 있는 시간이 길면 FCFS처럼 동작하고, 시간이 짧으면 컨텍스트 스위칭에 발생하는 오버헤드가 커진다. 따라서 적절한 Time Quantum을 설정이 중요하다.
- Time Quantum은 컨텍스트 스위칭에 발생하는 시간보다 길어야 한다. 대개 컨텍스트 스위칭 오버헤드는 10 ~ 20ms로 추측하며, Time Quantum은 10 ~ 100ms로 설정한다.
4) MLQ (Multi Level Queue)
(특징)
- 선점형 스케줄링 방법이다.
- 프로세스 특징에 따른 큐를 여러 개 준비한다. 큐의 우선순위에 따라 CPU를 할당받을 수 있다.
(장점)
- 큐마다 독립적인 스케줄링을 구현할 수 있다.
(단점)
- 큐 사이 프로세스들의 이동이 어렵기 때문에 유연성이 떨어진다.
- 우선순위가 낮아 계속해서 CPU를 할당받지 못하는 기아 현상이 발생할 수 있다.
4) MLFQ (Multi Level Feedback Queue)
(특징)
- 선점형 스케줄링 방법이다.
- MLQ를 개선한 스케줄링 방법으로 큐 사이에 이동이 어려워 유연성이 떨어지는 문제점을 보완했다.
- 각 큐에 CPU 점유에 할당된 시간이 정해져 있으며, 해당 시간에 작업을 마치지 못했을 경우 더 낮은 우선순위를 가지는 다음 큐로 넘어간다. 우선순위가 낮을수록 더 긴 Time Quantum을 가진다.
(단점)
- 긴 작업을 요구하는 프로세스가 많으면 우선순위가 낮은 가장 마지막 큐는 FCFS처럼 동작할 수 있다.
** 대기하는 프로세스들의 우선순위를 점진적으로 높여주는 Againg을 통해 단점을 보완할 수 있다.
댓글