CPU Scheduling에 대해 설명해보세요.
CPU Scheduling
- CPU 스케줄링은 멀티 프로그래밍 시스템에서 CPU의 사용을 최대화하기 위해 Ready Queue에 들어온 프로세스에게 자원을 적절히 할당하는 과정을 말한다. 따라서 CPU 스케줄링은 운영체제의 핵심 기능이다.
CPU-I/O Burst Cycle(CPU-입출력 버스트 사이클)
-
프로세스의 실행은 CPU 실행과 입출력 대기 상태의 순환으로 이루어져있다.
-
Burst(버스트)는 어떤 현상이 짧은 시간 안에 집중적으로 일어나는 것을 의미한다. 따라서 CPU 실행이 연속적인 구간을 CPU Burst, 입출력 대기가 연속적인 구간을 I/O Burst라고 하며, CPU 입장에서는 이 CPU Burst와 I/O Burst가 번갈아가며 나타나게 된다. 이 순환을 CPU-I/O Burst Cycle이라고 한다.
-
CPU 지향 프로그램은 CPU 버스트 시간이 길고, 입출력 중심의 프로그램은 CPU 버스트 시간이 짧다. 이는 CPU 스케줄링 알고리즘을 선택할 때 중요하다.
Preemptive and Nonpreemptive Scheduling(선점 및 비선점 스케줄링)
-
CPU 스케줄링은 다음 네 가지 상황에서 결정된다.
- 프로세스가 Running 상태에서 Waiting 상태로 전환될 때(I/O 발생)
- 프로세스가 Running 상태에서 Ready 상태로 전환될 때(인터럽트 발생)
- 프로세스가 Waiting 상태에서 Ready 상태로 전환될 때(I/O 발생)
- 프로세스가 Terminate될 때
-
실행 중인 작업이나 프로세스가 중단될 수 있는 여부에 따라 선점 스케줄링과 비선점 스케줄링으로 나뉜다.
-
Preemptive Scheduling(선점 스케줄링)
: 선점 스케줄링은 프로세스가 CPU를 점유하고 있는 가운데 더 높은 우선 순위의 다른 프로세스가 CPU를 강제로 점유하여 실행하는 것을 말한다.(2, 3번 상황)- 한 프로세스가 장기간 프로세서를 독점하는 것을 방지
- 실시간 처리 시스템에 유용
- 오버헤드가 커질 수 있음
-
Nonpreemptive Scheduling(비선점 스케줄링)
: 비선점 스케줄링은 반대로 프로세스가 한 번 CPU를 점유했다면, I/O(프로세스 상태가 실행에서 대기로 변경되는 경우) 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것을 말한다.(1, 4번 상황)- 한 프로세스가 장기간 자원 독점할 수 있음
- 응답시간 예측에 유용
-
Scheduling Criteria(스케줄링 기준)
-
다양한 CPU 스케줄링 알고리즘 중에서 다음 기준에 따라 선택하게 된다.
-
CPU Utilization(CPU 이용률)
: CPU가 수행되는 비율이다. CPU를 최대한 바쁘게 유지하는 것이 좋다. -
Throughput(처리량)
: 단위 시간 당 처리된 프로세스의 개수이다. 처리량을 늘리기 위해서 CPU 버스트가 짧은 프로세스를 우선적으로 CPU를 할당하는 것이 유리하다. -
Turnaround Time(반환 시간)
: 프로세스에 일이 할당되고 그 일이 종료되는데 걸린 시간이다. 반환 시간은 짧을 수록 좋다. -
Waiting Time(대기 시간)
: CPU를 점유하기 위해 Ready Queue에서 대기한 시간이다. 대기 시간은 짧을 수록 좋다. -
Response Time(응답 시간)
: 프로세스가 Ready Queue에 들어온 후 첫 CPU를 획득하기까지 걸린 시간이다. 응답 시간은 대화형 시스템에 적합한 성능 척도로서, 사용자 입장에서 가장 중요한 성능 척도이다.
-
Scheduling Algorithms(스케줄링 알고리즘)
-
CPU 스케줄링 알고리즘은 Ready Queue에 있는 프로세스들 중 어떤 프로세스를 CPU에 할당할지 결정한다.
-
비선점 스케줄링
-
FCFS(First-Come, First-Served)
: 가장 간단한 CPU 스케줄링 알고리즘이다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 방식이다. Queue 자료 구조를 이용하여 쉽게 구현할 수 있다. 하지만 버스트가 큰 작업이 먼저 들어오게 될 경우 뒤에 작업들의 대기시간이 길어지게 되는 Convey Effect(호위효과)를 야기한다. 따라서 비효율적일 수 있고, 호위효과는 작을수록 좋다. -
SJF(Shortest Job First)
-
남은 CPU 버스트 길이가 가장 작은 프로세스부터 CPU를 할당하는 방식이다. SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적의 알고리즘임을 증명할 수 있다. 하지만 현실적인 컴퓨터 환경에서는 프로세스의 CPU 버스트 시간을 알 수 없기 때문에 CPU 버스트의 길이를 예측해서 스케줄링을 해야 하고, 이는 오버헤드가 매우 큰 작업이다.
-
SJF 알고리즘은 상황에 따라 선점, 비선점이 모두 가능하다. 이전의 프로세스가 아직 실행중일 때, Ready queue에 새로 도착한 프로세스의 버스트 길이가 더 짧은 경우, 이를 다루는 방식에 따라 선점, 비선점이 구분된다. 선점형의 경우에는 원래 실행 중이던 프로세스를 내리고 더 짧은 프로세스를 CPU에 할당한다. SRTF(Shortest Remaining Time First)라고 불리기도 한다. 비선점형의 경우에는 더 짧은 프로세스가 들어왔다 하더라도 현재 실행중인 CPU 버스트가 완료될 때까지 CPU를 뺏기지 않는다.
-
CPU 버스트 길이가 짧은 프로세스부터 CPU를 할당하기 때문에 길이가 긴 프로세스는 영원히 CPU를 못잡는 Starvation(기아)현상이 발생할 수 있는 문제점이 있다.
-
-
-
선점 스케줄링
-
Priority
-
각 프로세스에 우선도를 선정하여 우선 순위가 높은(작은 숫자의 우선도) 프로세스를 CPU에 우선 할당하는 방식이다(우선도가 남은 Burst 시간이 짧은 것이라면 SJF 알고리즘과 동일해짐). 동일한 우선도에 대해서는 FCFS 알고리즘을 적용한다.
-
Priority도 SJF와 마찬가지로 상황에 따라 선점, 비선점이 모두 가능하다. 또한 주요 문제도 마찬가지로 기아 현상이 발생한다는 것이다.
-
기아 현상을 해결하기 위해 오랜 시간 시스템에서 대기한 프로세스들의 우선 순위를 점진적으로 증가시키는 Aging(노화)라는 방식을 도입한다.
-
-
RR(Round Robin)
-
RR 스케줄링 알고리즘은 FCFS 스케줄링 알고리즘과 유사하지만 선점이 가능하도록 해서 프로세스의 교체가 가능한 방식이다. 이는 시분할 시스템을 위해 설계되었다.
-
각 프로세스는 동일한 크기의 할당 시간인 Time Quantum을 가진다. 프로세스가 이 단위 시간을 지나면, Ready Queue의 마지막으로 돌아가고 다른 프로세스에게 선점시킨다. 따라서 특정 프로세스가 CPU를 독점하지 못하도록 한다.
-
이 방식의 성능은 Time Quantum의 크기에 많은 영향을 받는다. 만약 Time Quantum의 크기가 매우 크다면 FCFS와 유사하게 작동할 것이고, 매우 작게 설정한다면 잦은 문맥 교환으로 overhead가 매우 증가하여 비효율적이다.
-
-
Multilevel Queue(다단계 큐)
-
다단계 큐 스케줄링 알고리즘은 Ready Queue를 프로세스 유형에 따라 여러 큐로 나누어 각각에 알맞는 스케줄링을 적용하는 방식이다.
-
큐마다 우선순위를 지정할 수 있으며, 위 그림에서 위쪽에 있을 수록 우선 순위가 높다. Systme Process는 커널 수준에서 중요한 작업이므로 높은 우선 순위를 가진다. 높은 우선 순위의 큐에 있는 프로세스들이 처리되어야 낮은 순위의 큐에 잇는 프로세스들이 처리될 수 있다.
-
-
Multilevel Feedback Queue(다단계 피드백 큐)
-
다단계 피드백 큐는 여러 개의 큐를 사용한다는 점에서 다단계 큐와 비슷하지만, 프로세스가 큐를 이동할 수 있다는 점에서 차이가 있다.
-
모든 프로세스는 가장 높은 우선 순위 큐에서 CPU의 점유를 대기하다가, 대기 시간이 길어지게 되면 다음 우선 순위 큐로 이동한다. 이를 통해 대기 시간을 조정하고, 기아 현상이 발생하면 Aging을 통해 해결할 수 있다.
-
-
-
