CPU burst : CPU만 연속적으로 사용하며 instruction을 실행하는 단계. 이 단계에서 사용자 프로그램은 cpu 내에서 일어나는 명령이나 메모리에 접근하는 일반 명령을 사용할 수 있다.
I/O burst : I/O를 실행하고 있는 단계. I/O 버스트는 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이다. 이 단계에서는 모든 입출력 명령을 특권 명령으로 규정하여 사용자 프로그램이 직접 수행할 수 없도록 하고, 대신 운영체제를 통해 서비스를 대행하도록 한다
사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다.
📑프로세스의 특성 분류
각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지 않다. 어떤 프로세스는 I/O 버스트가 빈번해 CPU 버스트가 매우 짧은 반면, 어떤 프로세스는 I/O를 거의 하지 않아 CPU 버스트가 매우 길게 나타난다. 이와 같은 기준에서 프로세스를 크게 I/O 바운드 프로세스와 CPU 바운드 프로세스로 나눌 수 있다.
I/O bound process
CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
I/O 요청이 빈번해 CPU 버스트가 짧게 나타난다.
주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행하는 대화형 프로그램이 해당된다.
(many short CPU bursts)
CPU-bound process
계산 위주의 job
I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타난다.
프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램이 해당된다.
(few very long CPU bursts.)
📑CPU-burst Time의 분포
여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.
Interactive job에게 적절한 response 제공 요망
CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
프로그램이 수행되는 구조를 보면 I/O 바운드 프로세스는 짧은 CPU 버스트를 많이 가지고 있는 반면, CPU 바운드 프로세스는 소수의 긴 CPU 버스트로 구성된다는 것을 알 수 있다.
실제로 CPU를 많이 쓰는 것은 CPU bound job, I/O bound job이 CPU를 많이 끊어 쓰기 때문에 빈도가 잦은 것.
I/O bound job은 주로 interactive job(사람과 상호작용하는 작업). CPU bound job이 CPU를 너무 오래 사용하게 되면 I/O bound job이 CPU를 사용하지 못하게 되고, 사용자가 답답함을 느낄 수 있다.
📑CPU Scheduler & Dispatcher
컴퓨터 시스템 내에서 수행되는 프로세스의 CPU 버스트를 분석해 보면 대부분의 경우 짧은 CPU 버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 갖는다. 이는 다시 말해서 CPU를 한 번에 오래 사용하기보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스가 많다는 것이다. 즉 대화형 작업을 많이 수행해야 하는데, 사용자에 대한 빠른 응답을 위해서는 해당 프로세스에게 우선적으로 CPU를 할당하는 것이 바람직하다. 만약 CPU 바운드 프로세스에게 먼저 CPU를 할당한다면 그 프로세스가 CPU를 다 사용할 때까지 수많은 I/O 바운드 프로세스는 기다려야 할 것이다. 이러한 이유로 CPU 스케줄링이 필요해졌다.
CPU Scheduler
Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
Dispatcher
CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
이 과정을 context switch(문맥 교환)라고 한다.
CPU Scheduler는 CPU를 누구에게 줄지 결정하는 과정이라면, dispatcher는 CPU를 실제로 주는 과정
CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
Running → Blocked (예: I/O 요청하는 시스템 콜)
Running → Ready (예: 할당시간만료로 timer interrupt)
Blocked → Ready (예: I/O 완료 후 인터럽트)
Terminate
1, 4에서의 스케줄링은 nonpreemptive (= 강제로 빼앗지 않고 자진 반납, 비선점형)
All other scheduling is preemptive (= 강제로 빼앗음, 선점형)
📑Scheduling Criteria (스케줄링의 성능 평가)
💡 Performance Index (= Performance Measure, 성능 척도)
👉 시스템 입장에서의 성능 척도
CPU utilization (이용률)
전체 시간 중에서 cpu가 일을 한 시간의 비율
keep the CPU as busy as possible → CPU는 비싼 자원이기 때문에 놀리지 말고 가능한 바쁘게 일을 시켜라
Throughput (처리량)
number of processes that complete their execution per time unit → 주어진 시간 동안 몇 개의 작업을 처리했는지를 나타냄
CPU의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비 큐를 떠났지 측정한 것.
더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
👉프로그램 입장에서의 성능 척도
Turnaround time (소요시간, 반환시간)
amount of time to execute a particular process → CPU를 쓰러 들어와서 다 쓰고 나갈 때까지 걸린 시간
(준비 큐에서 기다린 시간) + (실제로 CPU를 사용한 시간)
Waiting time (대기 시간)
amount of time a process has been waiting in the ready queue → ready queue에서 줄서서 CPU를 기다린 시간
CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻한다.
시분할 시스템의 경우, 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다. 이때 대기 시간은 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합을 뜻하게 된다.
Response time (응답 시간)
amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) → ready queue에 들어와서 처음으로 CPU를 쓰기까지 걸린 시간
time-sharing과 같이 CPU를 얻었다 뺏었다 하는 환경에서는 처음으로 CPU를 얻는 시간이 사용자 응답과 관련해서 중요한 시간 개념이다.
응답시간은 대화형 시스템에 적합한 성능 척도로서, 사용자 입장에서 가장 중요한 성능 척도라고 할 수 있다.
Waiting time vs. Response time
선점형 스케줄링에서는 CPU를 한 번 얻었다고 해서 끝까지 사용하는 것이 아니라, CPU를 뺏겼다가 다시 얻었다를 반복한다.
Response time은 처음으로 CPU를 얻기까지 기다린 시간이다. 반면, Waiting time은 CPU를 기다리다 사용하고 빼앗기는 것을 반복할 경우 줄 서서 기다리는 시간이 여러 차례 반복되는데, 이때 이 기다린 시간을 다 합친 시간이다.
위의 시간들은 프로세스의 시작과 종료가 기준이 아닌, CPU를 사용하기 위해 ready queue에 들어온 시간이나 CPU 사용시간이 기준이다.
📑Scheduling Algorithms
👉FCFS (First-Come First-Served)
먼저 온 고객을 먼저 서비스 해주는 방법
비선점형 스케줄링
CPU를 혼자 오래 독점하는 프로그램이 있을 경우 효율적이지 않음.
Example :
첫번 째 경우
프로세스의 도착 순서 $P_{1}$, $P_{2}$, $P_{3}$ 스케줄 순서를 Gantt Chart로 나타내면 다음과 같다.
Waiting time for $P_{1} = 0$, $P_{2} = 24$, $P_{3} = 27$
Average waiting time : (0 + 24 + 27) / 3 = 17
두 번째 경우
프로세스의 도착 순서 $P_{2}$, $P_{3}$, $P_{1}$ 스케줄 순서를 Gantt Chart로 나타내면 다음과 같다.
Waiting time for $P_{1} = 6$, $P_{2} = 0$, $P_{3} = 3$
Average waiting time : (6 + 0 + 3) / 3 = 3
Much better than previous case.
Convoy effect (호위 효과) : short process behind long process → 긴 프로세스 뒤에서 짧은 프로세스들이 지나치게 오래 기다려야 되는 현상
👉SJF (Shortest-Job-First)
각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
Two schemes :
Nonpreemptive (비선점형)
일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음
CPU를 다 사용하고 나가는 시점에 CPU 스케줄링이 이루어짐
Preemptive (선점형)
현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.
average waiting time을 최소화하는 방법
새로운 프로세스가 도착하면 CPU 스케줄링이 이루어짐
SJF is optimal
주어진 프로세스들에 대해 minimum average waiting time을 보장
Example of Non-Preemptive SJF
SJF (non-preemptive)
Average waiting time = (0 + 6 + 3 + 7) / 4 = 4
Example of Preemptive SJF
SJF (preemptive)
Average waiting time = (9 + 1 + 0 + 2) / 4 = 3
어떤 스케줄링 알고리즘을 쓰더라도 이보다 더 짧은 average waiting time을 얻을 수 없다.
SRTF(Shortest-Remaining-Time-First)
Problem 1. Starvation (기아 현상)
SJF는 극단적으로 CPU 사용 시간이 짧은 job을 선호한다. 따라서 CPU 사용 시간이 긴 프로세스는 영원히 서비스를 받지 못할 수도 있다.
Problem 2. 다음 CPU Burst Time 예측
다음 번 CPU burst time을 어떻게 알 수 있는가? (input data, branch, user …)
추정(estimate)만이 가능하다
과거의 CPU burst time을 이용해서 추정 (exponential averaging)
👉Priority Scheduling
A priority number(integer) is associated with each process → 우선 순위를 나타내는 정수가 주어진다. (우선순위가 높은 프로세스를 더 작은 정수로 표현)
highest priority를 가진 프로세스에게 CPU 할당 (smallest integer = highest priority)
nonpreemptive : CPU를 한 번 줬으면 더 높은 우선순위의 프로세스가 들어오더라도 CPU를 다 쓸 때까지는 보장해 준다.
preemptive : 우선순위가 가장 높은 프로세스에게 CPU를 줬을 때 우선 순위가 더 높은 프로세스가 들어온다면 CPU를 빼앗을 수 있다.
SJF는 일종의 priority scheduling이다. priority == predicted next CPU burst time
Problem
Starvation (기아 현상) : low priority processes may never execute → 우선 순위가 낮은 프로세스가 들어오면 영원히 CPU를 얻지 못하는 상황이 발생할 수 있다.
Solution
Aging (노화) : as time progresses increase the priority of the process. → Starvation 현상을 막기 위해 도입되었다. 아무리 우선 순위가 낮더라도, 오래 머무르게 되면 우선순위를 높여준다.
👉Round Robin (RR)
현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 Round Robin에 기반한다.
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 milliseconds)
할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. → CPU를 최초로 얻기까지의 시간(Response time : 응답시간)이 굉장히 빠르다.
누가 CPU를 오래 사용할지 모르는 상황에서 굳이 사용 시간을 예측할 필요 없이 CPU를 짧게 사용하는 프로세스가 CPU를 빨리 사용하고 나갈 수 있게 해 준다.
대기 시간이 CPU 사용시간에 비례한다.
Performance
q large (할당 시간을 아주 크게 잡는 경우) → FCFS
q small (할당 시간을 지나치게 작게 잡는 경우) → context switch 오버헤드가 커진다
일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.
Example : RR with Time Quantum = 20
The Gantt chart is :
Round Robin 알고리즘 사용 시 발생할 수 있는 특이 케이스
CPU 사용시간이 같은 프로세스들이 들어왔을 때, 어느 하나의 프로세스라도 빨리 끝내고 나갈 수 있어야 하는데, RR을 사용하면 모든 프로세스가 동일한 시간 간격으로 CPU를 넘겨 쓰다 마지막 시점에서 한 번에 탈출하는 경우가 생길 수 있다. → 이 경우 time quantum을 아주 크게 하는 게 더 효율적이다.
하지만 일반적으로 짧은 사용 시간을 가진 프로세스와 긴 사용 시간을 가진 프로세스가 섞여있기 때문에 대체적으로 RR이 효과적이다.
👉Multilevel Queue
Ready queue를 우선순위에 따라 여러 개로 분할
foreground (interactive : 사용자와 상호작용하는 job)
background (batch - no human interaction : 사람과 상호작용 없이 CPU만 사용하는 계산 위주의 job)
각 큐는 독립적인 스케줄링 알고리즘을 가짐
foreground - RR
background - FCFS
멀티 레벨 큐 자체에 대한 스케줄링이 필요
Fixed priority scheduling (고정 우선순위 방식)
server all from foreground then from background. → 우선순위가 높은 foreground queue가 비어야만 background queue에게 CPU를 준다.
Possibility of starvation → 이런 경우 starvation(기아 현상)이 발생할 수 있다.
Time slice
각 큐에 CPU time을 적절한 비율로 할당
Eg. 80% to foreground in RR, 20% to background in FCFS → 우선순위가 낮더라도 CPU를 어느 정도 할당 받을 수 있음
👉Multilevel Feedback Queue
프로세스가 다른 큐로 이동 가능
에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
Multilevel-feedback-queue scheduler를 정의하는 파라미터들
Queue의 수
각 큐의 scheduling algorithm
Process를 상위 큐로 보내는 기준
Process를 하위 큐로 내쫓는 기준
프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
보통은 처음 들어오는 프로세스는 우선 순위가 가장 높은 큐에 넣고, 우선순위가 높은 큐는 RR에서 time quantum을 굉장히 짧게 준다.
밑의 큐로 갈수록 RR의 time quantum을 길게 해 주고, 제일 아래 큐는 FCFS 방식을 사용한다.
위에 큐에서 사용 할당 시간이 끝나면 밑의 큐로 강등된다.
CPU burst가 짧은 프로세스는 들어오자마자 CPU를 얻어서 짧은 시간 사용하고 바로 빠져나갈 수 있고, CPU burst가 긴 프로세스는 위의 큐에서 작업을 다 끝내지 못하고 아래 큐로 이동해서 할당 시간을 더 받게 되지만 우선순위에서 밀려난다.
Example of Multilevel Feedback Queue
Three queues:
$Q_{0}$ - time quantum 8 milliseconds
$Q_{1}$ - time quantum 16 milliseconds
$Q_{2}$ - FCFS
Scheduling
new job이 queue $Q_{0}$로 들어감
CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
8 milliseconds 동안 다 끝내지 못했으면 queue $Q_{1}$으로 내려감
$Q_{1}$에 줄 서서 기다렸다가 CPU를 잡아서 16 ms 동안 수행됨
16 ms에 끝내지 못한 경우 queue $Q_{2}$로 쫓겨남
📑Multiple-Processor Scheduling(다중 처리기 스케줄링)
CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
Homogeneous processor인 경우
Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
Load sharing
일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
별 개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
Symmetric Multiprocessing (SMP)
모든 CPU가 대등하므로 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric multiprocessing
하나의 CPU가 시스템 데이터의 접근과 공유를 책임지고 나머지 CPU는 거기에 따름
📑Real-Time Scheduling(실시간 스케줄링)
real-time job은 데드라인이 있는 job이다. 즉, 정해진 시간 안에 반드시 실행이 되어야 한다. 그래서 CPU 스케줄링에서도 real-time job은 반드시 데드라인을 보장해주어야 한다.
Hard real-time systems
Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
Soft real-time computing
데드라인이 존재하기는 하지만 지키지 못했다고 해서 위험한 상황이 생기지 않는다.
Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
📑Thread Scheduling
Local Scheduling
User level thread → 사용자 프로세스가 직접 thread를 관리하고 운영체제는 thread의 존재를 모른다.
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할지 결정
운영체제 입장에서는 thread의 존재를 모르기 때문에 해당 프로세스에게 CPU를 줄지 말지만 결정하고, 해당 프로세스에게 CPU가 갔을 때 프로세스 내부에서 어떤 thread에게 CPU를 줄지는 프로세스 내부에서 결정한다.
Global Scheduling
Kernel level thread → 운영체제가 thread의 존재를 이미 알고 있다.
Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
📑Algorithm Evaluation(알고리즘 성능 척도)
Queueing models
주로 이론가들이 수행하는 방식이다.
확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index를 계산
Implementation(구현) & Measurement(성능 측정)
실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
Simulation(모의실험)
알고리즘을 모의 프로그램으로 작성 후 trace(실제 프로그램에서 추출한 input data)를 입력으로 하여 결과 비교
![[KOCW 반효경 운영체제] 5. CPU Scheduling](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FtUO0p%2FbtsJeTC8YCL%2FAkQLFtTZqlRg5gvV58493K%2Fimg.png)
