프로그램이 실행된다는것은 CPU버스트와 IO버스트를 번갈아가면서 실행되는 것
CPU 스케줄링의 기본개념
프로그램은 CPU Burst와 I/O Burst를 번갈아가며 실행된다. 이때 I/O Burst가 완료될 때까지 기다려야만 한다면, CPU를 낭비하게 된다.
때문에 운영체제는 프로세스가 대기할 때마다, 다른 프로세스가 CPU를 사용하도록 할당한다.
운영체제가 프로세스에게 CPU를 할당하는 선택절차를 CPU 스케줄러라고 한다.
CPU - I/O 버스트 사이클
CPU - I/O 버스트 사이클
CPU 버스트 지속시간의 히스토그램
•
프로세스는 CPU - I/O Burst의 사이클로 구성된다.
•
일반적으로 짧은 CPU버스트를 가지고, I/O 중심의 프로그램들은 전형적으로 짧은 CPU버스트를 가진다.
•
CPU 지향 프로그램은 다수의 긴 CPU버스트를 가질 수 잇다.
•
이러한 분포는 CPU 스케줄링을 구현할 때 매우 중요할 수 잇다.
선점(preemptive) 및 비선점(nonpreemptive) 스케줄링
CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.
1.
한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (예를 들어 입출력 요청이 들어왔을 때)
Running → Blocked
2.
프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (예를 들어 인터럽트가 발생할 때)
Running → Ready
3.
프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (예를 들어 입출력 종료 시)
Blocked → Ready
4.
프로세스가 종료할 때
Terminate
1번과 4번 상황에서만 스케줄링이 발생할 경우는 시선점 혹은 협조적 스케줄링이라 한다.
그렇지 않다면 선점형 스케줄링이라 한다.
디스패처
디스패처의 역할
디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다.
•
문맥을 교환하는 일
•
사용자 모드로 전환하는 일
•
프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일
디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 최고로 빨리 수행되어야 한다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)라고 한다.
스케줄링의 기준(= 성능척도)
CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준을 제시하고 사용되는 특성에 따라 최선의 알고리즘을 결장하는데 큰 차이가 발생한다.
•
CPU 이용률(utilization)
◦
우리는 가능한 한 CPU를 최대한 빠르게 유지하길 원한다.
◦
CPU가 실제로 몇 퍼센트 이용되고 있는지를 판단하고, 이 이용률을 최대화 해야한다.
•
처리량(throughput)
◦
CPU가 프로세스를 수행하느라 바쁘다면, 작업이 진행되고 있는 것이다.
◦
작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이를 처리량(throughput)이라 한다.
◦
주어진 시간동안 얼마나 많은 처리가 가능한것인가.
•
총 처리 시간(turnaround time)
◦
프로세스를 실행하는 데 소요된 시간
◦
프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라 한다.
◦
총처리 시간은 메모리에 들어가기 위해 기다리며 소비한 시간, Ready Queue에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한 시간
•
대기 시간(waiting time)
◦
대기 시간은 Ready Queue에서 대기하며 보낸 시간의 합
◦
CPU 스케줄링 알고리즘은 프로세스가 실행하거나 입출력을 하는 시간의 양에 영향을 미치지 않는다.
•
응답 시간(response time)
◦
하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간
◦
대화식 시스템에서, 총처리 시간은 최선의 기준이 아닐 수도 있습니다. 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간입니다. 응답 시간이라고 하는 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는 데 걸리는 시간이 아닙니다.
시스템 입장에서 성능 척도는 CPU 이용률과 처리량
프로세스 입장에서 성능 척도는 처리 시간, 대시 시간, 응답 시간
스케줄링 알고리즘
선입 선출 스케줄링(First Come, First-Served Scheduling, FIFO)
•
가장 간단한 스케줄링 알고리즘으로, 선입 선처리 스케줄링 방식이다.
•
CPU를 먼저 요청하는 프로세스가 먼저 CPU를 할당받는다.
•
프로세스 처리 순서에 따라서 대기시간이 길어질 수도, 짧아질 수도있다.
•
때문에 비효율적인 대기가 계속될 수 있다.
•
하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(Convoy Effect) 라고 한다.
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)
•
CPU 이용이 가능해지면 가장 작은 CPU 버스트를 가진 프로세스부터 할당한다.
•
평균 대기시간을 최소화하는 알고리즘으로 알려져 있음
•
비선점형 스케줄링 방식 - CPU를 잡으면 CPU 버스트가 완료될 때까지 선점 당하지 않음
•
선점형 스케줄링 방식 - 수행중인 프로세스의 남은 CPU 버스트 타임보다 짧은 프로세스가 도악하면 CPU를 빼앗긴다.
•
SJF는 일종의 우선순위 스케줄링이다.
◦
문제점: 기아 상태(Starvation)가 발생할 수 있다.
◦
해결: 노화(Aging)을 이용해 오래된 프로세스는 우선순위를 높혀주어 해결한다.
•
다음번 CPU 버스트 시간을 어떻게 알 수 있는가?
◦
추정(Estimate)만이 가능하다.
◦
과거의 CPU 버스트 시간을 이용해서 추정한다. (Exponential Averaging)
우선순위 스케줄링(Priority Scheduling)
•
특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.
•
프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.
•
SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.
•
다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.
•
문제점: 기아 상태(Starvation)가 발생할 수 있다.
•
해결: 노화(Aging)을 이용해 오래된 프로세스는 우선순위를 높혀주어 해결한다.
라운드 로빈 스케줄링(Round-Robin Scheduling)
•
일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
•
시스템의 time-sharing과 같은 방식이다.
•
반응성이 좋다.
•
시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.
•
다만 시간을 길게 준다면 FIFO와 다를것이 없고, 너무 짧게 준다면 문맥교환이 너무 자주 발생해 오버헤드가 커진다.
다단계 큐 스케줄링(Multilevel Queue Scheduling)
•
우선순위 기준이 다른 분리된 큐들을 두어서, 그 우선순위에 맞게 스케쥴링을 하는 것이 훨씬 쉬울 것이다. 이러한 접근방법을 multilevel queue라 한다.
•
일반적으로 포그라운드(foreground, 대화형) 프로세스들과 백그라운드(background, 일괄처리) 프로세스들을 구분
•
포그라운드는 RR 알고리즘에 의해 스케줄링되고, 백그라운드는 FCFS 알고리즘에 의해 스케줄될 수 있다.
다단계 큐 피드백 스케줄링(Multilevel Feedback Queue Scheduling)
•
New Job이 Queue Q0으로 들어감
•
CPU를 잡아서 할당시간 8ms 동안 수행됨
•
8ms 동안 다 끝내지 못하면 Q1으로 내려감
•
Q1에서 기다리다가 CPU를 할당받아 16ms 동안 수행됨
•
그동안 끝내지 못할경우 Q2로 쫓겨남
멀티 프로세서 스케줄링
CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
•
Homogeneouse Processor의 경우
◦
Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
◦
반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
•
Load Balancing
◦
일부 프로세서에 job이 물리지 않도록 부하를 적절히 공유하는 메커니즘 필요
◦
별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
•
Symmetric Multiprocessing (SMP)
◦
각 프로세서가 각자 알아서 스케줄링 결정
•
Asymmetric Multiprocessing
◦
하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
실시간 CPU 스케줄링
•
Hard real-time systems
◦
Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
•
Soft real-time computing
◦
Soft real time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
스레드 스케줄링
•
Local Scheduling
◦
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
•
Global Scheduling
◦
Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
알고리즘의 평가
•
Queueing models
◦
확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
•
Implementation(구현) & Measurement(성능 측정)
◦
실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
•
Simulation(모의 실험)
◦
알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
