outline
CPU Scheduler
Scheduling Criteria
Dispatcher
Scheduling Algorithms
FCFS(First-Come First-Served)
SJF(Shortest-Job-First)
SRTF(Shortest-Remaining-Time-First)
Priority Scheduling
RR(Round Robin)
Multilevel Queue
Multilevel Feedback Queue
CPU 스케줄러(CPU Scheduler)
CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 다음 프로세스가 어느 프로세스인지를 선택하는 알고리즘을 'CPU Scheduling' 알고리즘이라고 한다. CPU 스케줄링은 크게 두 가지의 특징으로 나눌 수 있다.
1) 선점(Preemptive)
선점하는 방식은 하나의 프로세스가 CPU를 할당받아 작업을 수행하고 있는 도중에 다른 프로세스가 작업할 수 있는 방식을 말한다. 따라서 선점하는 방식을 사용하면 언제든지 CPU가 다른 프로세스에 할당될 수 있다.
2) 비선점(Non-Preemptive)
비 선점하는 방식을 사용하면 하나의 프로세스가 CPU 할당이 끝이 나야 다른 프로세스가 CPU를 할당받을 수 있는 형식이다.
디스패처(Dispatcher)
현재 실행 중인 프로세스에서 넘어가 다른 프로세스를 실행하기 위해서는 현재 프로세스의 PCB에 내용(context)을 저장해야 한다. 그 후 ready queue에 있던 새로운 프로세스의 PCB 내용을 불러온다. 실행은 해당 프로세스의 PC를 변화시키는 것을 의미한다.
- Dispatcher은 CPU 스케줄러에 의해 선택된 프로세스의 컨트롤을 준다.
- Dispatch latency : dispatcher가 한 프로세스를 멈추고 다른 프로세스를 시작하기까지 걸리는 시간
스케줄링 척도(Scheduling Criteria) - CPU 스케줄러 알고리즘 성능 평가
스케줄링 척도는 스케줄링의 효율을 분석하는 기준이다.
- CPU Utilization :CPU가 수행되는 비율 ( CPU가 놀지 않게 설정해야 한다.)
- Throughput : 단위 시간당 처리하는 작업의 수 ( 많이 끝낼수록 좋다.)
- Turnaround time : 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간.(짧으면 짧을수록 좋다.)
- Waiting time : CPU를 점유하기 위해서 ready queue에서 기다린 시간.
- Response time : 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.
스케줄링 알고리즘(Scheduling Algorithms)
1. FCFS(First-Come First-Served)
FCFS는 먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다. 매우 단순하고 많이 사용하는 방법이지만, 모든 부분에서 효율적인 것은 아니다.
- 위에 예시로 보이는 것처럼 P1, P2, P3 각각의 프로세스가 순서대로 들어왔다고 가정할 때 P1은 먼저 들어왔기 때문에 대기 시간은 0이다. 하지만 P2는 수행 시간이 3초라는 시간밖에 안 걸리지만 P1이 다 끝날 때까지 수행하지 못한다. 그렇기 때문에 대기 시간이 24초이다. 다음으로 들어오는 P3도 수행 시간이 3초 밖에 안 걸리지만 총 대기 시간은 27이 된다. 3개의 프로세스의 평균 대기 시간을 구하면 17이 걸린다.
- 만약 P2, P3, P1 순서대로 프로세스를 진행했다면 평균 대기 시간이 3이 걸린다.
- 위에 예시로 보이는 것처럼 소요시간이 긴 프로세스가 먼저 도달하여 효율성이 낮아지는 현상이 발생된다. 이러한 문제점을 'convoy effect'라고 한다.
2. SJF(Shortest-Job-First)
SJF는 이름에서도 나타나듯이 가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 것을 말한다. FCFS와 달리 평균 대기시간이 짧아진다. SJF는 비선점 방식과 선점 방식으로 나눠진다. 선점 방식은 최소 잔여 시간 우선(Shortest-Remaining-Time-First)라고 부른다.
1) 비선점 방식 (Non-Preemptive)
- 위에 예시를 보면 P1, P2, P3, P4 순서대로 프로세스가 왔다고 가정하자. 초기에 들어오는 P1이 당연히 먼저 시작되면서 대기 시간은 0이다.
- 시간 2일 때 P2 프로세스가 도착하였지만, P1이 실행하고 있기 때문에 P2 프로세스는 ready 상태가 된다. 그 와중에 P3 프로세스가 시간 4일 때 도착하였고 P4 프로세스가 시간 5일 때 도착하였다. P1이 시간 7을 다 사용하고 종료되면 도착한 P2, P3, P4 프로세스 중에서 가장 짧은 시간을 가진 P3가 먼저 실행이 된다.
- SJF를 사용하면 평균 대기 시간이 시간 4가 걸린다.
- 효율성을 추구하는 게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안 된다. 해당 스케줄링은 극단적으로 CPU 사용이 짧은 job을 선호한다. 그래서 사용 시간이 긴 프로세스는 영원히 CPU를 할당받을 수 없다.(starvation)
2) 선점 방식 (Preemptive)
- SRTF(Shortest-Remaining-Time-First)
- P1 프로세스가 먼저 도착하였기 때문에 P1 프로세스가 먼저 시행이 된다. 그 와중에 시간 2일 때 P2 프로세스가 도착했다. P1 프로세스보다 P2 프로세스의 수행 시간이 더 짧기 때문에 P1프로세스는 대기 상태로 변화하면서 P2 프로세스가 먼저 시행된다. P2 프로세스가 실행되고 수행 시간이 더 짧은 P3 프로세스가 시간 4일 때 도착하였기 때문에 마찬가지로 P2 프로세스는 대기 상태가 되고 P3 프로세스가 먼저 시행이 된다.
- SRTF 방식을 사용하면 총 대기 시간은 3이 된다.
- 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 더 빠른 프로세스한테 뺏긴다.
- 새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU burst time을 예측하기 힘들다.
- starvation이라는 문제점을 가진다.
* CPU burst의 길이를 결정하는 방법
SJF와 SRTF는 들어오는 프로세스의 burst time을 가지고 알고리즘을 수행하게 된다. 하지만 어떻게 다음 프로세스의 cpu burst time을 알 수 있을까?
- 다음번 CPU burst time을 예측(estimate)만 가능하다.
- 과거의 CPU burst time을 이용해서 추정(exponential averaging)한다.
tn : 가장 최근의 CPU burst 값
τ(n+1): 다음 CPU burst에 대한 예측 값
τ(n) : 이전의 CPU burst에 대한 예측 값
a : 최근 값과 과거의 값에 대한 가중치
τ(n+1) = at(n) + (1-a)τ(n) 공식을 갖는다
만약 CPU-Burst Time이 전과 비교해서 오차가 크다면 가중치를 0에 가깝게 하고,
오차가 작다면 가중치를 1에 가깝게 한다.
3. Priority Scheduling
- Priority 스케줄링은 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘이다. 운영체제에서 일반적으로 우선순위는 정수 값으로 나타내며, 작은 값이 우선순위가 높다. 우선순위 스케줄링 방식도 선점형(Preemptive)과 비선점형(Non-Preemptive) 방식으로 나뉜다
- 우선순위 스케줄링의 문제점은 Starvation이 있다. 말 그대로 CPU의 점유를 오랫동안 하지 못하는 현상을 말한다.
- Starvation의 해결책으로 ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 aging 방법이 있다.
1) 선점 방식
- 더 높은 우선순위의 프로세스가 도착하면 실행 중인 프로세스를 멈추고 CPU를 선점한다.
2) 비선점 방식
- 더 높은 우선순위 프로세스가 도착하면 Ready Queue의 Head에 넣는다.
4. RR(Round Robin)
RR은 원 모양으로 모든 프로세스가 돌아가며 스케줄링하는 것을 말한다. 이는 시분할 시스템에서 주로 사용하는 방식이다. 일정 시간을 정하여 하나의 프로세스가 이 시간 동안 수행하고 다시 대기 상태로 돌아간다. 그리고 다음 프로세스가 역시 같은 시간 동안 수행한 후 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와서 반복한다.
위에 예시를 보면 모든 프로세서는 수행 시간을 시간 20으로 설정하였기 때문에 프로세스는 들어온 순서대로 시간 20을 수행하고 다음 프로세스에게 CPU를 넘겨준다. 형태를 보면 FCFS와 비슷하게 먼저 들어온 프로세스가 먼저 수행하는 모습을 볼 수 있다. RR과 FCFS는 모든 프로세스에 대해 공평성을 제공해 주고 있다.
만약 RR의 time quantum의 크기를 너무 크게 잡으면 FCFS와 동일하게 동작하게 되며, 만약 크기를 너무 작게 설정하게 된다면 switching overhead가 매우 증가하여 비효율적이다. 이미 많은 개발자분께서 적당한 크기를 구해서 설정되어 있다. (10 ~ 100 msec)
5. Multilevel Queue
멀티 레벨 큐 방식은 위와 같이 여러 성격에 따라 프로세스를 각 그룹에 따라 큐를 두어 여러 개의 큐를 사용하는 것을 말한다. 큐마다 우선순위를 지정되어 있다. 그림과 같이 'System Process'는 커널에서 중요한 작업이므로 우선순위가 높은 그룹으로 설정된 것을 확인할 수 있다.
6. Multilevel Feedback Queue
Multilevel Queue Scheduling과 같이 복수 개의 Queue를 가질 수 있으며 하나의 입구로 프로세스는 해당 큐의 스케줄링을 사용하게 되며 너무 많은 시간의 CPU time을 사용 시 다른 Queue로 이동하게 되고 기아 상태가 되려고 하면 다시 우선순위가 높은 Queue로 이동하게 된다.
위에 그림과 같이 첫 번째와 두 번째 큐를 RR 스케줄링으로 time quantum을 각각 8과 16을 줬다. 첫 번째 RR에서 프로세스가 들어와서 재 시간 안에 수행을 했다면 해당 프로세스는 종료를 시키지만 수행하지 못하면 다음 RR 큐로 넘어간다. 똑같이 해당 프로세스가 수행되지 못하면 마지막 순서대로 FCFS 방식으로 수행되게끔 설정한 멀티 레벨 피드백 큐의 예시를 확인할 수 있다. 이처럼 여러 queue를 사용하여 효율적인 프로세스가 관리를 할 수 있다.
