CPU Scheduling
cpu 스케줄링이 필요한 이유는 cpu가 필요한 시간이 짧은 I/O bound job과 cpu가 오랫동안 필요한 cpu bound job에 효율적으로 cpu를 분배하기 위함이다. I/O작업의 경우 interactive한 작업으로 빠른 응답성을 사용자에게 제공해야 하기 때문에 형평성있으면서도 효율적으로 cpu를 분배해야 한다.
따라서, 효율적으로 스케쥴링을 하고 있는지 평가할 척도가 필요하다.
Scheduling Creteria
1. 시스템 입장에서의 성능척도
- 얼마나 cpu를 많이 사용했는지
cpu utilization(cpu 이용률) / Throughput(처리율)
2. 프로세스 입장에서의 성능척도
(프로세스가 시작되고 끝날때까지를 의미하는 것이 아니라 cpu를 사용하기 위해 ready queue상태에 있다가 I/O를 쓰러 나갈때까지의 시간을 의미 )
- 얼마나 빨리 cpu를 사용했는지
Turnaround time(반환시간)/ Waiting time(대기시간) / Response time(응답시간)
Scheduling Algorithem
1. FCFS(First-Come First-Served)
문제점
Convoy effect : cpu를 오래 잡는 프로세스일 경우, 인터렉티브한 작업이 오래 기다려야 하기 때문에 비효율적일 수 있음.
2. SJF(Shortest-Job-First)
cpu burst time이 가장 짧은 프로세스를 제일 먼저 스케줄링.
nonpreemptive / preemptive한 방법으로 나뉨.
*nonpreemptive한 방식은 더 짧은 프로세스가 와도 이미 차지하고 있는 cpu를 넘겨주지 않는다.
-cpu 대기시간이 가장 짧은 방식
문제점
1. starvation: cpu burst time이 긴 프로세스들은 스케줄링이 되지 않을 수 있다.
2. cpu burst time을 예측하기 어렵다. (과거의 사용시간을 보고 추정함 *exponential averaging)
3. Priority Scheduling
우선순위가 가장 높은 프로세스에게 cpu를 주어짐.
nonpreemptive/ preemptive한 방법으로 나뉨. sjf도 하나의 priority scheduling이라고 할 수 있음.
문제점
starvation
solution: Aging - 오래 기다릴 경우 우선순위를 높여주는 방법
4. Round Robin(RR)
- 각 프로세스는 동일한 크기의 할당 시간을 가짐.
- 할당 시간이 지나면 timer interrupt에 의해서 preempted당하고 ready queue의 제일 뒤에 가서 다시 줄을 서게 된다.
round robin은 응답시간이 짧아진다는 장점이 있다.
- 할당 시간을 길게 하면 FCFS와 같아지고,
할당 시간을 짧게 잡으면 context switch 오버헤드가 커져서 시스템 성능이 떨어지게 된다.
- turnaround time이 아닌 response time이 짧아진다!
- 프로세스 처리시간이 긴 경우 여러번 나눠서 할당되기 때문에 기다리는 시간이 오래걸릴 수 있다.
즉, cpu burst time이 짧을수록 대기시간이 짧고, 길 수록 대기시간이 길어지는 공정한 스케줄링이라고 할 수 있다.
Multilevel Queue
queue가 한 줄이 아닌 여러줄일 경우
- Ready queue를 여러개로 분할
foreground(interactive)--RR(응답시간이 짧음)
background(batch - no human interaction) --FCFS
큐에 대한 스케줄링이 필요
- Fixed priority scheduling
: interactive한 작업인 foreground에 먼저 우선순위를 부여하는 경우
- Time slice
: 각 큐에 cpu time을 적절한 비율로 할당
Multilevel Feedback Queue
Multiple-Processor Scheduling
- queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음.
- load sharing : 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- Symmetric Multiprocessing(SMP) : 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric Multiprocessing : 하나의 프로세서가 데이터 접근과 공유를 담당하여 나머지 프로세서는 이에 따름.
Real-time Scheduling
-hard real-time => task는 정해진 시간안에 반드시 끝내도록 스케줄링이 필요.
-soft real-time computing => 일반 프로세스에 비해 높은 priority를 갖도록 함.
Thread Scheduling
local scheduling: 프로세스가 직접 어떤 스레드에게 cpu를 줄 지 내부에서 결정하는 경우
Algorithm Evaluation
1. Queueing models
확률 분포로 주어지는 arrival rate(프로세스 도착율), service rate(cpu 처리율)을 통해 값을 계산
2. Implementation(구현) & Measurement(성능 측정)
실제로 구현해서 실제 작업에 대해 성능을 측정 비교
3. Simulation(모의 실험)
알고리즘을 모의 프로그램으로 작성후 trace를 입력하여 결과 비교