CPU 스케쥴링
CPU 스케쥴링
CPU를 어떤 프로세스에 얼마나 할당할지를 정해준다. CPU 스케쥴러는 운영체제 안에 있는 기능 중 하나이다.
프로그램은 IO작업과 CPU의 연산을 돌아가며 수행한다. 아래의 그림과 같다.
CPU burst : CPU의 명령을 처리하는 부분
I/O burst : I/O 요청을 처리하는 부분 (즉 I/O 요청의 처리를 기다리는 시간)
프로그램마다 서로 CPU와 I/O burst를 번갈아가면서 수행되는 수는 물론 다를 것이다. 주로 일반 사용자들이 사용하는 상용 프로그램들은 번갈아가는 수가 굉장히 많을 것이고(I/O 처리가 많이 발생하므로), 엄청난 양의 계산을 해야하는 프로그램은 CPU 수행(CPU burst)이 압도적으로 많을 것이다.
아래는 CPU burst time의 분포이다.
여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케쥴링이 필요하다.
(IO bound job : 중간에 IO가 자주 끼어드는 프로그램, CPU bound job : CPU만 오래 쓰는 프로그램 )
• interactive job에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
프로세스의 특성 분류
프로세스는 그 특성에 따라 다음 두 가지로 나눔
• I/O bound process
-- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
-- (many short CPU bursts)
• CPU bound process
-- 계산 위주의 job
-- (few very long CPU bursts)
CPU Scheduler & Dispatcher
● CPU Scheduler
• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
● Dispatcher
• cpu의 제어권을 CPU 스케쥴러에 의해 선택된 프로세스에게 넘긴다.
• 이 과정을 context switch(문맥 교환)라고 한다.
● CPU 스케쥴링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
1. Running --> Blocked (ex. I/O 요청하는 시스템 콜)
2. Running --> Ready (ex. 할당시간만료로 timer interrupt)
3. Blocked --> Ready (ex. I/O 완료 후 인터럽트)
4. Terminate
* 1, 4에서의 스케쥴링은 nonpreemptive(=강제로 빼앗지 않고 자진 반납)
* 나머지 스케쥴링은 preemptive(=강제로 빼앗음)
CPU 스케쥴링 알고리즘
CPU 스케쥴링에는 아래처럼 다양한 알고리즘들이 있다.
1. FCFS (First-Come First-Served)
2. SJF (Shortest-Job-First)
3. SRTF (Shortest-Remaining-Time-First)
4. Priority Scheduling
5. RR (Round Robin)
6. Multilevel Queue
7. Multilevel Feedback Queue
위와 같은 알고리즘들을 평가하기 위한 5가지 평가 척도가 있는데 이는 아래와 같다.
• CPU utilization (이용률) - 최대한 CPU에게 일을 많이 시켜라!
• Throughput (처리량) - 주어진 시간 동안 얼마나 처리를 했는가?
• Turnaround time (소요시간, 반환시간) - 프로세스가 CPU를 받아서 CPU를 다른 프로세스에게 넘기기까지 얼마나 시간이 걸렸는지
• Waiting time (대기시간) - 프로세스가 CPU를 받기 위해 ready queue에서 기다리는 시간
• Response time (응답 시간) - 프로세스가 맨 처음에 CPU를 받기까지 걸리는 시간
* CPU utilization과 Throughput은 CPU 입장에서의 평가 척도이고,
Turnaround time, Waiting time, Response time 3가지는 프로세스 입장에서의 평가 척도이다.
* 현재 응답 시간, 대기 시간 등 우리가 말하고 있는 시간은 프로세스 하나가 시작되고 전체가 끝날때까지 걸리는 시간을 말하는 것이 아니라 하나의 프로세스가 CPU burst와 I/O burst를 번갈아 하며 걸리는 사이사이의 시간을 의미한다.
중국집을 운영하는 이모씨를 스케쥴링 알고리즘 평가 척도 예시를 들면 아래와 같다.
• 이모씨가 고용한 주방장은 얼마만큼 일을 하는가? <— CPU utilization
• 중국집이 특정 시간 동안 손님을 얼마나 받는가? <— Throughput
• 손님이 주문을 하고 나서 다먹고 나갈때까지 걸리는 시간 <— Turnaround time
• 손님이 기다리는 시간 <— Waiting time
• 첫번째 음식이 나올때까지 기다리는 시간 <— Response time
이제 CPU 스케쥴링 알고리즘들을 하나씩 알아보자.
1. FCFS (First-Come First-Served)
먼저 들어온 프로세스에게 먼저 CPU를 넘겨준다.
해당 알고리즘은 맨 처음에 CPU를 오랜 시간 쓰는 long 프로세스가 오면 모든 프로세스들의 대기 시간이 길어진다는 치명적인 단점이 있는 알고리즘이다.
아래 그림과 같은 경우 CPU를 아주 짧데만 사용하면 되는 프로세스들이 긴 프로세스를 기다려야 한다. 해서 프로세스 평균 대기 시간이 길다.
아래와 같은 경우에는 짧은 프로세스가 먼저 도차가형 프로세스 평균 대기 시간이 짧다.
2. SJF (Shortest-Job-First)
FCFS를 보완한 방법으로 프로세스 수행 시간이 짧은 프로세스에게 먼저 CPU를 준다.
요 SJF를 Nonpreemptive한 방법과 preemptive한 방법으로 나눠볼 수 있다.
Nonpreemptive :
기다리고 있는 프로세스들 중 CPU를 가장 짧게 쓸 수 있는 프로세스A에게 CPU를 할당했는데, 잠시 뒤 프로세스A 보다 더 짧은 수행시간을 가진 프로세스B가 Ready queue에서 대기 중이더라도 이미 CPU를 준 프로세스A가 끝날 때까지는 CPU를 뺏지않고 수행을 보장한다.
Preemptive :
nonpreemptive와 반대로 프로세스A가 CPU를 잡고 있더라도 프로세스B가 수행시간이 더 짧으므로 프로세스A에게서 CPU를 빼앗아 프로세스B에게 준다.
하지만 SJF에도 2가지 문제점이 있다.
1. starvation(기아) : CPU 사용시간이 긴 프로세스는 영원히 실행되지 않을 수 있는 문제. 만약 CPU가 짧은 프로세스들이 우선순위를 높게 배정받았고, CPU 수행시간이 긴 프로세스가 맨 뒤에 배정받은 경우, Long 프로세스가 실행되기도 전에 계속해서 Short 프로세스들이 들어오면 Long프로세스는 실행되지 못할 것이다.
2. CPU 사용시간을 미리 알 수 없음 : 실제로 특정 프로세스의 CPU 사용시간을 알기 어렵다. 예로 제일 오래 걸릴것 같은 프로세스를 제일 뒤제 배정했는데, 막상 if문을 통해 바로 처음 코드부터 종료될 수 있다. 이것은 실제로는 가장 짧은 프로세스를 가장 긴 프로세스로 보고 가장 뒤에 배정한 것이다.
해서 위와 같은 문제를 해결하기 위해 CPU의 Burst Time을 예측하는 방법이 있다.
바로 과거의 CPU burst time을 이용하여 추정하는 것이다. (exponential averaging)
t는 실제 CPU 사용 시간. r은 CPU 사용 예측 시간이라고 한다면 공식은 아래와 같다.
즉 n+1번째 CPU 사용시간은 과거의 실제 사용시간에 적절한 비율을 주고 계산하는 것이다. 이때 최근에 사용한 시간에는 가중치를 높게, 비교적 이전에 사용한 시간은 가중치를 낮게 잡는다.
3. Priority Scheduling
우선 순위가 높은 프로세스에게 먼저 CPU를 주는 것이다.
사실 위에서 살펴본 SJF도(CPU 사용시간이 적은 프로세스가 높은 우선순위를 가지는) 우선 순위 스케쥴링에 해당한다.
우선 순위 스케쥴링도 nonpreemptive와 preemptive로 나눌 수 있다. nonpreemptive는 현재 프로세르가 실행 중인데, 더 높은 우선 순위의 프로세스가 와도 현재 실행 중인 프로세스는 실행시킨다.
반대로 preemptive는 현재 프로세스가 실행 중인데, 더 높은 우선 순위의 프로세스가 오면 더 높은 우선 순위에게 CPU를 준다.
우선 순위 스케쥴링은 역시(SJF와 마찬가지로) starvation문제가 발생한다. 이를 해결하기 위해서는 aging 기법을 사용한다.
aging이란 Long 프로세스라고 하더라도 너무 오랜 시간 CPU를 받지 못했다면 CPU를 받을 수 있도록 우선순위를 올려주는 것이다.
3. Round Robin(RR)
• 요즘 현대의 운영체제의 대부분은 RR을 따른다. 즉 모든 프로세스가 동일한 크기의 할당 시간(time quantum)을 가진다. (일반적으로 10-100 milliseconds가 가장 적당하다고 알려져 있다.)
• RR 방식을 사용하면 사용자에게 응답 시간이 빨라진다는 장점이 있다. 모든 프로세스는 같은 CPU 할당 시간을 가지므로 응답 시간이 빨라지게 되는 것이다.
• CPU를 오래 쓰는 프로세스는 그만큼 기다리는 시간의 총합이 길어지고, 짧은 CPU는 그 반대이다.
• q(할당시간)을 너무 길게 잡으면 그만큼 수행시간이 짧은 프로세스의 대기 시간이 길어지는 문제가 발생하고, q를 너무 짧게 잡으면 context switch의 오버헤드가 커지는 문제가 발생한다.
아래는 RR의 예시이다. (q=20)
지금까지 모든 프로세스가 하나의 줄, 즉 하나의 큐에 줄을 서있다고 가정했는데 이번에는 여러 개의 큐가 있는 경우를 간단하게 살펴보자.
1. Multilevel Queue
위 그림을 보면 여러 개의 프로세스 큐가 존재하고, 각 큐마다 우선순위가 있는 것을 볼 수 있다. 위 그림에선 위에 있을 수록 우선순위가 높은 큐이다. 즉 맨 윗 줄의 system processes 큐에서 대기 중인 프로세스가 있다면 아래에 있는 큐들에 서 대기중인 프로세스들은 실행되지 못한다. system processes 큐에서 대기 중인 프로세스들이 모두 수행되어 큐가 비게 되어야 비로소 interactive processes 큐에서 대기중인 프로세스들이 실행되고 나머지 큐들도 마찬가지이다. 하지만 이러한 방식은 낮은 우선순위의 큐일수록 starvation 문제가 발생할 확률이 높아진다.
위에서는 5개의 큐로 나누었는데 이번에는 2개의 큐로 나누어보자.
• foreground Queue (interactive - 사용자의 개입(I/O)가 많은 프로세스 큐)
• backgornd Queue (batch - no human interaction - 사용자의 개입이 거의 없는 프로세스 큐)
위 2개의 큐에 대한 스케쥴링은 foreground에 우선 순위를 두어 foreground Queue에 있는 프로세스가 모두 수행되어야 backgound Queue에 있는 프로세스들을 수행시키는 것이다. 하지만 이와 같은 우선 순위를 두는 방법은 위에서 언급했듯이 starvation 문제가 발생할 수 있어 각 큐에 적절한 비율로 CPU time을 할당하는 Time Slice 방법을 사용한다.
예로 80%는 foregound에 할당하고 foregound는 RR 스케쥴링 방법을 사용하고, 나머지 20%는 backgound에 할당하고 backgound 프로세스들은 컨텍스트 스위칭 비용을 줄이기 위해 FCFS 스케쥴링을 사용하는 것이다.
2. Multilevel Feedback Queue
이번에는 Multilevel Feedback Queue를 알아보자. 해당 큐는 Multilevel Queue와 달리 비교적 공평한 방법이다. 즉 우선 순위가 처음에는 낮은 프로세스더리도 우선 순위가 높은 큐로 갈 수도 있고, 그 반대도 가능하다. 즉 프로세스들의 큐 라인간의 이동이 가능하다.
위 그림을 보면 맨 처음 우선 순위 프로세스는 우선 순위를 높게, 하지만 CPU를 잡는 시간인 quantum은 매우 짧게 준다. 하지만 그 다음 우선순위 줄은 quantum을 더 길게 준다.
정리하면 아래와 같다.
• Three Queues :
--- Q0 - time quantum 8 milliseconds
--- Q1 - time quantum 16 milliseconds
--- Q2 - FCFS
• Scheduling
--- 1. new job이 queue Q0으로 들어감
--- 2. CPU를 잡도 할당 시간인 8 milliseconds동안 수행
--- 3. Q1에 줄을 서서 기디리다가 CPU를 잡고 16 milliseconds 동안 수행
--- 4. 16 milliseconds에 끝내지 못한 경우 Q로 쫓겨남
Multiprocessor Scheduling
CPU가 여러개 있는 경우 스케쥴링은 더욱 복잡해진다.
• Homogeneous processor인 경우
--- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
--- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load sharing
--- 일부 프로세서 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
--- 별개의 큐를 두는 방법 VS 공동 큐를 두는 방법
• Symmetric Multiprocessing (SMP)
--- 각 프로세서가 각자 알아서 스케쥴링 결정
• Asymmetric multiprocessing
--- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세스는 거기에 따름
Real-Time Scheduing
리얼 타임 스케쥴링은 반드시 한정된 시간 내에 실행되어야하는 프로세스를 스케쥴링 하는 것이다.
• 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 library에 의해 어떤 스케쥴할지 결정. 즉 특정 프로세스 내부에서 해당 스레드들의 스케쥴링을 결정한다.
• Global Scheduling
--- Kernal level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정
Algorithm Evaluation
지끔까지 다양한 알고리즘들을 알아봤는데, 그러면 어떤 알고리즘이 성능이 좋은지 평가할 수 있는 척도가 있어야 한다. 그 것들을 간단하게 알아보자. 알고리즘의 성능을 평가하는 방법에는 크게 3가지 척도가 있다.
1. Queueing models
- 확률분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산
이 방법은 굉장히 이론적인 방법이다. 위 그림에서 CPU가 서버고, CPU를 기다리는 큐의 프로세스들(arrival rate)과 CPU를 사용하고 나가는 프로세스들(service rate) 간의 복잡한 수식을 통해 퍼포먼스 인덱스를 구한다.
2. Implementation(구현) & Measurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
이 방법은 실제로 시스템에 스케쥴 알고리즘을 적용하고 사용해본 뒤 성능을 평가하는 방법이다.
예로 리눅스 운영체제의 스케쥴링 코드를 수정하여 본인이 직접 만든 스케쥴링 코드를 넣고, 커널을 컴파일하여 실제 프로그램을 돌려서 성능을 직접 확인해보는 것이다.
3. Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성후 trace(simulation 프로그램의 input으로 들어갈 데이터)를 입력으로 하여 결과 비교
모의 실험방법은 2번 방법이 직접 구현하기에는 어려워서 하는 방법이다. 예로 SJF 알고리즘을 평가한다면 SJF를 적용한 시나리오를 만들고, 해당 시나리오대로 돌아가는 프로그램을 만들어서 성능을 예측해보는 것이다.
출처 : 이화대학교 반효경 교수님의 운영체제 강의
http://www.kocw.net/home/search/kemView.do?kemId=1046323