CPU 스케쥴링 알고리즘(2) - SJF, Priority, Round-Robin

1. SJF(Shortest-Job-First)

SJF란 CPU 시간이 적게 드는 순으로 처리하는 스케쥴링 방식이다.

1) 특징

• Probably optimal : AWT를 최소화하는데 가장 적합한 방법이다.
• Not realistic, prediction may be needed : 실제로 프로세스가 얼마나 CPU 시간을 사용할 지 모르기 때문에 비현실적인 방법이다. 그래서 CPU 시간이 얼마나 들지 예상해서 순서를 정해야 한다.
• Preemptive or Non-preeptive : 선점으로도, 비선점으로 구현할 수 있다.
• cf. Shortest-Remaining-Time-First(최소잔여시간우선) : Preeptive SJF 의 방법 중 하나이다.

2) Example

다음 프로세스를 SJF의 선점방식, 비선점 방식으로 풀어볼 수 있다.

SJF의 선점, 비선점 방식 경우 AWT

비선점 방식(Non-preemptive)으로 풀 경우 0msec 에는 P1만이 도착했으므로 P1을 처리한다. 나머지 프로세스가 차례로 도착해도 아직 P1이 처리 중이므로 P1이 끝난 뒤에 CPU 처리 시간이 짧은 순으로 처리한다.

 

선점 방식(Preemptive)으로 풀 경우, 비선점방식과 동일하게 0msec에는 P1만이 도착했으므로 P1을 처리한다. 그러나 P2가 도착했을 경우, P1=7msec 와 P2=4msec를 비교하여 더 짧은 프로세스인 P2를 먼저 처리한다. P3, P4가 차례로 도착했을 경우에도 P2가 가장 적은 처리시간을 가지므로 P2를 계속 처리한다. 그 후 CPU 처리 시간이 짧은 순으로 처리한다.

---

---

2. Priority Scheduling

우선순위(Priority)란 전형적으로 Integer number이다. 일반적으로 작은 수가 높은 우선순위를 나타낸다.(Unix/Linux)

1) 특징

• Preemptive or Non-preemptive : 선점 또는 비선점 방식으로 스케쥴링 할 수 있다.

2) 문제점

Indefinite blocking : starvation (기아), 프로세스의 우선순위가 낮을 경우 아무리 기다려도 차례가 오지 않아 CPU 처리를 못받는 현상이 발생할 수 있다. 서버 컴퓨터와 같이 새로운 요청이 계속해서 들어올 경우 발생한다.

=> Solution : againg, 프로세스가 오래 기다리면 우선순위를 점차 높여주는 방식으로 해결할 수 있다.

3)우선 순위를 결정하는 방법

-Internal : time limit, memory requirement, I/O to CPU burst ...

-External : amount of funds being paid : 돈 많이낸 순으로, political factors, ...

3)Example

우선 순위가 높은 순으로 프로세스를 처리하면 된다.

---

---

3. Round-Robin

Robin이란 작은 새를 의미한다. Round-Robin이란 마치 어지러울 때 머리 위에 별이 빙빙 도는 모습을 상상하면 된다.

즉, 프로세스를 계속해서 순환하면서 처리해주는 방식을 말한다.

Round-Robin

1) 특징

• Time-Sharing-System (시분할/시공유 시스템) : TSS에서 사용하는 스케쥴링 방식이다.
• Time quantum(시간 양자) = time slice(10~100msec)
• Preemptive scheduling : 계속해서 다른 프로세스로 바꿔주는 선점 방식이다.
• Performance depends on the size of the time quantum : Time quantum 델타(Δ)가 얼마인지에 따라 효율성이 바뀐다.

=> 델타가 무한대에 수렴하면 프로세스가 끝날 때까지 바뀌지 않으므로 FCFS이다.

=> 델타가 0에 수렴하면 Processor sharing 이라 한다. 즉, 여러 프로세스가 동시에 처리되는 것과 같다. 그러나 context switching overhead가 발생하여 프로세스에서 다른 프로세스로 넘어갈 때 시간이 발생한다.

2) Example : Average turnaround time(ATT)

- ATT = 11.0msec(Δ = 1), 12.25msec(Δ=5)