CPU 스케줄링
CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 하는데, 이 때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 말한다. 상황에 맞게 CPU를 어떤 프로세스에게 할당하여 효율적으로 처리하는지가 관건이다.
- CPU 스케줄링이 이루어지는 경우
running→blockedrunning→ready(CPU를 뺏기는 것으로 자발적인 상태전이가 아니다.)blocked→ready(이 경우 스케줄링이 일어날 수도 안일어날 수도 있다.)running→terminated
Non-Preemptive(비선점형)
현재 실행중인 프로세스가 자발적으로 실행을 그만두는 경우(위의 1, 4)에만 스케줄링이 일어나면 비선점형 스케줄링이다. 한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때 까지 다른 프로세스가 CPU를 점유하지 못한다. CPU독점을 제어할 방법이 없다는 단점이 있다.
Preemptive(선점형)
프로세스가 CPU를 점유하고 있는 동안 입출력이나 인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행중인 동안 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.
스케줄링 척도 (Scheduling criteria)
스케줄링의 효율을 분석하는 기준들이다.
-
CPU 이용률(utilization) : CPU가 수행(사용자 프로그램을 실행)되는 비율. (최대화)
-
처리량(throughput) : 단위시간 당 실행을 완료하는 프로세스의 수 (최대화)
-
반환시간(turnaround time) : 프로세스의 실행시작에서 끝날때 까지의 시간.
blocked,ready,I/O등 모든 시간을 포함한다. (최소화) -
대기시간(waiting time) : 프로세스가 Ready Queue에 머무른 시간. CPU 사용 순서를 기다리는 스케줄링 대기시간. (최소화)
-
응답시간(response time) : 프로세스의 첫 출력이 나오기까지의 시간. 일반적으로 대화형 시스템에서 입력에 대한 반응시간을 의미한다 (최소화)
비선점형 스케줄링
FCFS (First-Come First-Served)
먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식
매우 단순하고 많이 사용하는 방법이지만 모든 부분에서 효율적이진 않다.
한 번 CPU를 할당 받으면 CPU burst(프로그램의 수행중에 연속적으로 CPU를 사용하는 단절된 구간. CPU 스케줄링의 단위가 된다)가 완료될 때 까지 CPU를 반환하지 않고, 할당되었던 CPU가 반환될 때만 스케줄링이 이루어지는 비선점형 스케줄링 방식이다.
SJF (Shortest-Job-First)
가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 방식
FCFS에서 보았듯 수행시간이 짧은 프로세스가 먼저 오는 것이 평균 대기시간이 짧은 것을 알 수 있었는데 이것을 이용한 것이 SJF이다. CPU burst는 정확히 알 수 없어서 추정치를 사용하게 되는데 이는 오버헤드가 매우 큰 작업이므로 사용되지 않으며 수행시간이 긴 프로세스에 대해 기아현상이 발생할 수 있따. 선점과 비선점 모두 가능하다. (선점형 SJF = SRT)
Priority
우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 방식
우선순위는 정수값으로 나타내며 Linux, Unix를 기준으로 숫자가 작은 값이 우선순위가 높다. 선점형 방식으로도 가능하다.
SJF는 CPU busrt 추정치를 우선순위로 하는 우선순위 스케줄링 방식이라고 할 수 있다.
우선순위가 낮으면 오랫동안 선정되지 않는 기아 현상이 발생할 수 있으며 이를 해결하는 방식으로 Ready Queue에 오래 머무르면 우선순위를 높여주는 aging 기법을 사용한다.
선점형 스케줄링
SRT (Shortest Remaining Time)
선점형 방식의 SJF 스케줄링 방식
CPU burst가 짧은 순서대로 프로세스를 수행하며 현재 CPU에서 실행중인 프로세스의 남은 CPU burst보다 더 짧은 CPU burst를 가지는 프로세스가 도착하면 CPU가 선점된다.
RR (Round-Robin)
기본적으로 도착한 순서대로 실행하며 한번에 CPU를 사용할 수 있는 시간을 정해놓는 스케줄링 방식
시분할 시스템을 위해 설계된 스케줄링 알고리즘이다. CPU를 사용할 수 있는 시간을 Time Quantum이라고 하며 일반적으로 10~100msec으로 정한다.
프로세스에 CPU를 할당하면 최대 주어진 Time Quantum(q)만큼만 사용가능 하도록 한다.
(n-1)q 이상 기다리는 프로세스는 없으며 CPU를 선점당한 프로세스는 다시 Ready Queue로 들어온다.
q의 값이 전체 성능에 영향을 미치는데, 너무 작으면 불필요한 문맥 교환이 자주 일어나게 되고, 너무 크면 FCFS와 동일하게 동작하므로 q를 사용하는 이유가 없게 된다.
따라서 q는 보통 긴 CPU burst를 끊는 것을 목표로 하여 대부분의 짧은 CPU burst를 커버할 수 있는 정도의 길이로 설정한다.
Multi-level Queue
프로세스를 그룹으로 나누어 각 그룹에 따라 여러개의 Ready Queue를 사용하는 방식
Ready Queue를 여러개로 분할해 관리하는 스케줄링 방법이며 프로세스들이 CPU를 기다리기 위해 여러 줄로 기다리게 되는 것이다.
각 큐마다 별도의 스케줄링 방식을 적용할 수 있다.
Multi-level Feedback Queue
큐와 큐 사이를 이동할 수 있는 Multi-level Queue
먼저 모든 프로세스는 가장 위의 큐에서 CPU 할당을 대기한다. 이 상태로 진행하다가, 이 큐에서 기다리는 시간이 길어진다면 아래의 큐로 프로세스를 옮긴다.
이와 같은 방식으로 대기 시간을 조정하며 각 큐마다 별도의 스케줄링, 우선순위, Time Quantum 등을 사용할 수 있다.
대부분의 운영체제는 여러 개의 큐를 사용하고 각 큐마다 프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.
