I. CPU Burst VS I/O Burst
프로세스가 실행 중일 때 CPU 연산을 하는 구간을 CPU Burst, I/O 작업을 처리하는 구간을 I/O Burst라고 한다. 예를 들어 CPU가 Instruction을 Register에 올리고 ALU을 동작하여 연산을 수행하는 구간을 CPU Burst라고 할 수 있고 I/O 작업을 위해 시스템 콜이 발생한 경우는 I/O Burst라고 할 수 있다.
II. CPU Bound Process VS I/O Bound Process
긴 CPU Burst Time을 갖는 프로세스를 CPU Bound Process라고 하고, 긴 I/O Burst Time을 갖는 프로세스는 I/O Bound Process라고 한다. 우리가 쓰는 대부분의 프로그램은 I/O Bound Process이다 (예시: Youtube의 스트리밍을 위한 데이터 통신, 통신 프로토콜은 CPU 연산이 별로 없고 최대한 단순하다) Short Term Scheduler는 CPU Bound Process 대신 I/O Bound Process를 우선적으로 선정한다. 또한 CPU Bound Process의 경우 CPU Utilization과 Throughput을 최대화하기 위해 Context Switching이 적게 일어나는 것이 유리하며, I/O Bound Process의 경우 Turnaround Time, Waiting Time, Response Time을 최소화하는 것이 중요하기 때문에 Context Switching이 많이 발생하는 것이 유리하다.
III. Short Term Scheduler가 CPU Bound Process 대신 I/O Bound Process를 우선적으로 선정하는 이유
유저와의 상호작용이 우선인 I/O Bound Process에 비해 CPU Bound Process는 Timer Interrupt가 없는 경우 유저와의 상호작용 없이 긴 Burst Time동안 연산을 하는 경우가 있기 때문에 우선적으로 I/O Bound Process를 먼저 처리하는 것이 유리하다.
IV. Dispatch
Context Switching이 발생할 경우 현재 CPU를 점유중인 프로세스의 Context(상태정보)를 PCB에 저장하고, 이후 스케줄러가 선택한 프로세스의 Context(상태 정보)를 PCB에서 가져온 뒤 CPU 레지스터에 로드 하여 실행시킬 준비를 하는 과정을 의미한다. Dispatcher는 이러한 Dispatch 동작을 수행하는 주체를 의미한다.
V. Preemptive VS Non-Preemptive
A. Preemptive
Ready Queue에 현재 CPU를 점유 중인 프로세스보다 우선순위가 높은 프로세스가 들어오게 되면 현재 CPU를 점유중인 프로세스를 Ready Queue로 내리고 우선순위가 높은 Process를 Running 시키는 Scheduler가 Preemprive Schduler이다. 현존하는 대부분의 OS들은 Preemptive Scheduling 방식을 채택하고 있다.
B. Non-Preemptive
Preemptive 방식과 달리 현재 CPU를 점유중인 프로세스보다 높은 우선순위를 갖는 프로세스가 Ready Queue에 들어가게 되어도 Context Switching이 발생 하지 않는 Scheduler가 Non-Preemprive Schduler이다.
VI. Scheduling Criteria(스케줄링 기준)
시스템의 종류와 목적에 따라 스케줄링의 기준도 달라지지만 일반적으로는 CPU Utilization과 Throughput을 최대화하고 Turnaround Time, Waiting Time, Response Time을 최소화 하는 것이 좋다.
A. CPU Utilization
CPU의 사용량을 의미하며 스케줄러는 CPU의 사용량을 최대화 하도록 스케줄링 해야 한다.
B. Throughput
단위시간당 처리량(특정 시간동안 수행한 instruction의 수)를 의미한다.
C. Turnaround Time
특정 프로세스가 메모리에 오르고 나서 모든 작업을 끝내고 terminated 상태가 되는 데에 걸리는 시간을 의미한다.
D. Waiting Time
프로세스가 Ready 큐에 진입한 다음 Running이 될 때까지 걸리는 시간을 의미한다.
E..Response Time
응답 시간을 의미하며, 모니터의 경우 화면에 프레임을 출력하는 응답 속도가 빨라서 응답 시간이 적게 걸린다.
VII. Starvation이란?
Ready Queue에 Process1, Process2, Process3, Process4가 들어있고 스케줄러에 의해 Process1, Process2, Process3만 번갈아 가며 선택되어 Running상태가 되지만 Process4만 수행되지 않는다면 Process4는 Starvation 상태에 빠졌다고 할 수 있다. 프로세스 작업 수행의 Fairness를 위해서는 이러한 Starvation이 발생하지 않도록 스케줄링 알고리즘을 잘 적용해야 한다.
VIII. FIFO Scheduling
FIFO(First in First Out)은 Ready Queue 들어온 프로세스를 순서대로 CPU를 점유하게 하는 것을 의미한다. 이 스케줄링 알고리즘은 Fairness를 가장 잘 보장하고 Starvation이 없다는 장점이 존재하지만, 먼저 Running 상태가 된 프로세스의 수행 시간이 길 경우 뒤 프로세스의 대기 시간이 길어진다는 단점이 존재한다.
IX. SJF Scheduling
FIFO Scheduling의 단점을 해결하는 Convoy Effect(시간이 적게 걸리는 프로세스를 먼저 처리하는 것)를 발생시키기 위해 SJF(Shortest Job First) Scheduling이 등장하였다. SJF는 Preemprive 방식과 Non-Preemprive 방식으로 나뉘는데 후자의 방식을 채택한 SJF를 SRTF(Shortest Remaining Time First) Scheduling이라고 한다. SJF는 이상적인 기법이다. 왜냐하면 각 프로세스의 Burst Time은 I/O 작업 요청, IPC등 여러 환경 변수가 존재하기 때문에 정확하게 예측이 불가능하기 때문이다.
X. Priority Scheduling
Priority Scheduling은 프로세스의 우선순위를 기반으로 스케줄링을 수행하는 기법이다. 시스템의 목적에 따라 프로세스의 우선순위를 Flexible하게 부여할 수 있다는 장점이 존재하고, 낮은 우선순위를 갖은 프로세스의 Starvation이 발생할 수 있다는 단점이 존재한다. 이러면 Fairness가 낮아지는 상황이 발생하게 되고, 이를 막기 위해서는 특정 프로세스의 Waiting Time이 길어질수록 우선순위를 점차 높여 나가는 Aging 기법을 적용해야 한다.
XI. RR(Round Robin) Scheduling
RR(Round Robin) Scheduling이란 우선순위가 같은 프로세스들이 Ready Queue에 존재할 때 특정 시간(Time Quantum)이 지날 때마다 프로세스를 번갈아 가면서 CPU를 점유하게 하는 스케줄링 기법을 의미하며 Fairness가 높아진다는 장점을 갖는다.
XII. Time Quantum의 조정 기준
Time Quantum이란 한 프로세스가 스케줄러에 의해 선택되어서 CPU를 최대로 점유할 수 있는 시간을 의미 한다.이 Time Quantum이 커지게 되면 RR 스케줄링 기법은 FCFS(First Come First Serve) 기법이 되게 되며, Time Quantum이 작아지면 Context Switching이 많아지기 때문에 CPU Utilization과 Throughput이 줄어들게 된다. 일반적으로는 프로세스의 CPU Burst 시간의 80% 정도의 Time Quantum을 두는 것이 유리하다.
XIII. Multilevel Queue Scheduling
Multilevel Queue Scheduling은 2개 이상의 Ready Queue를 만들고 각 Ready Queue에 다양한 Scheduling 알고리즘을 적용하는 기법을 의미한다. Foreground Queue에는 I/O Bound Process가 들어가고, Background Queue에는 CPU Bound Process가 들어가게 될 때, 유저와의 상호작용이 중요하고 Response Time을 최소화 해야 하는 Foreground Queue에 존재하는 I/O Bound Process가 높은 우선순위를 가지며, Background에 존재하는 CPU Bound Process는 상대적으로 낮은 우선순위를 가지게 된다.
XIV. Multilevel Queue Scheduling에서의 문제 및 해결 방안
낮은 우선순위와 긴 수행시간을 가진 프로세스의 Starvation이 발생하여서 그 프로세스에 aging을 적용해 우선순위를 높여 CPU를 점유하게 한다면 다른 프로세스들은 긴 시간을 기다려야 하는 문제가 발생하게 된다(Fairness 감소) 따라서 aging 기법을 이용하지 않고, CPU를 점유할 수 있는 시간을 각 Ready Queue마다 나누어 사용하게 하는 Time Slice 기법을 이용해야 한다.
XV. Multilevel Feedback Queue Scheduling
Multilevel Queue Scheduling에서는 어떤 프로세스를 어떤 Ready Queue에 삽입 해야 하는지에 대한 기준이 모호하다. 이러한 상황에서는 Multilevel Feedback Queue Scheduling을 이용하면 된다. 이 스케줄링 기법은 Ready Queue마다 Time Quantum을 다르게 지정한다. 만약 Ready Queue가 2개 존재하고 첫번째 큐의 Time Quantum은 8, 두번째 큐의 Time Quantum은 16인 상황에서 특정 프로세스가 첫번째 큐에 들어간 뒤 스케줄러에 의해 선정되어 Running State가 되게 되었지만 8이라는 Time Quantum을 채우기 전 I/O 작업이 필요해 Waiting State가 되었다고 해보자 이 프로세스는 이후 I/O 작업이 다 끝나게 되어 Ready Queue로 들어갈 때 두번째 큐가 아닌 첫번째 큐로 다시 들어가게 된다. 이에 반해 프로세스가 8이라는 Time Quantum을 초과한다면 I/O Bound Process가 아닌 CPU Bound Process일 확률이 높기 때문에 두번째 큐로 가게 되어 프로세스의 종류에 따라서 들어가게 되는 큐를 자동적으로 결정할 수 있다.
XVI. Hard Real Time VS Soft Real Time
Hard Real Time은 데드라인 내로 특정 작업을 완수하지 못하면 Critical 한 손해가 발생하는 특성을 의미하고 Soft Real Time은 데드라인 내로 특정 작업을 완수하지 못해도 Critical 한 손해가 발생하는 것은 아닌 특성을 의미한다. 대표적인 Real Time System은 임베디드 시스템이며 이 임베디드 시스템 안의 작업들은 주기적(Periodic) 특성을 가진다.
XVII. Real Time Scheduling (Static Priority)
Real Time Scheduling 기법은 Static Priority과 Dynamic Priority로 나뉜다 Static Priority의 대표적인 알고리즘은 Rate-Monotonic Algorithm이며 0.5초의 주기를 갖는 프로세스1, 1시간의 주기를 갖는 프로세스2, 1일의 주기를 갖는 프로세스3이 존재할 때 주기 시간이 적어 자주 실행되는 프로세스1에게 더 높은 우선순위를 부여하여 CPU 자원을 사용하게 하는 알고리즘이다. 현존 하는 모든 Real Time OS는 이 알고리즘을 선택하였지만 데드라인을 초과하는 상황이 발생할 수 있다는 단점이 존재한다.
XVIII. Real Time Scheduling (Dynamic Priority)
Rate-Monotonic Algorithm은 프로세스의 주기에 따라서 우선순위를 정적으로 부여하면서 데드라인을 초과할 수 있다는 단점이 있었다 하지만 이에 반해 Dynamic Priority의 대표적인 알고리즘인 EDF는 데드라인이 얼마나 남았는지를 기준으로 더 적은 데드라인을 가진 프로세스에게 동적으로 높은 우선순위를 부여하여 데드라인을 초과하는 문제를 해결한다.
XIX. 현존하는 RTOS들이 Rate-Monotonic Algorithm을 채택하는 이유
Real-Time System은 하드웨어 자원이 제한적인 임베디드 환경에서 돌아가는 경우가 많기 때문에 Ready Queue에 들어간 모든 프로세스의 데드라인을 전부 다 검토해서 제일 적은 데드라인을 가진 프로세스에게 높은 우선순위를 부여하는 것이 오버헤드이다 따라서 대부분의 RTOS들이 스케줄링 오버헤드가 큰 EDF가 아닌 Rate-Monotonic Algorithm을 채택하게 되었다.
