CPU Scheduling

Scheduling Metrics

Turnaround time

\[T_{turnaround} = T_{completion} - T_{arrival}\]

프로세스가 생성된 시간부터 종료된 시간까지 걸린 시간으로 기다린 시간까지 포함

Response time

\[T_{response} = T_{firstrun} - T_{arrival}\]

처음 실행때까지 걸린 시간 / 즉 요청을 보낸 후 처음 프로세스가 실행된 시간

 

 

---

Workload Assumptions 

cpu의 운영 방식을 가정하면서 가장 효율적인 CPU scheduling 방식이 무엇인지 찾아보고자 한다.

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

이러한 불가능한 가정을 하나씩 지워나가며 과거 운영체제의 CPU Scheduling 방식과 효율 비교

 

---

 

FIFO (First in, First out) = FCFS (First Come, First Served)

FIFO(1)

cpu 스케줄링 방식을 아래처럼 가정했을 때 그림과 같은 실행이 가능하다.

현재 세개의 프로세스는 동시에 도착했고, 완전히 동시에 도착한 경우 랜덤한 프로세스부터 실행함

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

 

Metrics

Average Turnaround time = 2t

\(\frac{t+2t+3t}{3} =2t\)

Average Response time = t

\(\frac{0+t+2t}{3} = t\)

 

cpu 운영 방식이 아래와 같아진다면 FIFO 방식에 문제가 생기게 된다

 

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

FIFO(2)

위 그림은 모든 프로세스가 같은 시간이 소요된다는 가정을 제외하고 실행했을 때의 한 예시

동시에 도착한 프로세스는 랜덤으로 실행되기 때문에, 만약 가장 오래 걸리는 프로세스가 먼저 실행된다면 성능이 굉장히 크게 떨어진다

 

Metrics

Average Turnaround time = 6t 

\(\frac{5t+6t+7t}{3} = 6t\)

Average Response time = 3.666t

\(\frac{0+5t+6t}{3}=3.666t\)

 

Metrics가 전체적으로 증가한 것을 확인할 수 있음

이를 통해 FIFO가 효율적인 방법과 거리가 멀다는 것을 알 수 있음 사실 애초부터 불가능한 가정

이를 해결하기 위해서 가장 짧은 프로세스부터 실행하도록 할 수 있음 (현재 프로세스의 길이를 안다는 가정)

 

SFJ (Shortest Job First)

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

위와 같은 가정에서 SFJ에 대한 예시를 볼 수 있다.

 

SFJ(1)

현재 세개의 프로세스가 동시에 실행된 상태이며, 가장 길이가 짧은 프로세스들을 랜덤으로 실행시킴

 

Metrics

Average Turnaround time = 3.333t

\(\frac{t+2t+7t}{3} = 3.333t\)

Average Response time = 0.333t 

\(\frac{0+t+0}{3} = 0.333t\)

 

FIFO 방식보다 Metrics가 전체적으로 줄어든 것을 볼 수 있다.

아래와 같이 workload assumption을 변경한다면 SFJ에서도 문제가 발생할 수 있다.

 

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

SFJ(2)

현재 가장 긴 프로세스가 제일 먼저 도착했고, 그 뒤에 짧은 프로세스가 동시에 도착하였다.

현재 Workload Assumption에서는 프로세스가 끝날 때까지 CPU를 점유하고 있으므로, 중간에 짧은 프로세스가 도착했다고 해서 이를 넘겨줄 수 없다.

 

Metrics

Average Trunaround time = 4.333t

\(\frac{5t+5t+6t}{3}=4.333t\)

Average Response time = 3t

\(\frac{0+4t+5t}{3}=3t\)

 

이러한 문제점이 발생하면 성능이 줄어드는 것을 확인할 수 있음

 

STCF (Shortest Time-to-Completion First) 

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

 

Preemptive Scheduler

• Context switch 가능
• Stop one process from running in order to run another (CPU 자원을 선점할 수 있음)

STCF

 preemptive 한 shortest job first와 같다.

 

Metrics

Average Turnaround time = 3.333t

\(\frac{7t + t+ 2t}{3} = 3.333t\)

Average Response time = 0.333t

\(\frac{0+0+t}{3} = 0.333t\)

 

 

RR (Round-Robin)

Time Slicing : Runs a job for a time slice 아주 작은 단위로 cpu 자원을 나눠줌

RR

time slice를 0.2t로 두었을 때

Metrics

Average Turnaround time는 다른 경우보다 증가함 - 끝나는 시간이 늦어짐

Average Response time = 0.2t

\(\frac{0+0.2t+0.4t}{3} = 0.2t\)

 

 

Incorporating I/O

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

Incorporating I/O

disk 자원을 프로세스가 사용중일 때 그 빈 공간에 다른 프로세스가 cpu를 사용할 수 있도록 함

파란색 프로세스가 CPU 점유를 넘겨준 이유는 여러가지가 존재할 수 있다. I/O 요청이 있거나, time slice 등

Workload Assumptions

• Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )
• All jobs arrive at the same time ( 여러개의 프로세스가 동시에 실행된다 / PCB가 동시에 생성된다 )
• Once started, each job runs to completion ( 프로세스가 끝날 때까지 CPU를 점유한다 )
• All jobs only use the CPU no I/O ( CPU의 상태가 blocked 되는 등 CPU가 자원을 양보하는 경우는 없다 )
• The run-time of each job is known ( 프로세스의 시간이 얼마나 소요될지 미리 알고 있다 )

모든 가정을 없애면 SFJ, SCTF는 사용할 수 없다 - 프로세스의 시간이 얼마나 소요될지 알아야하므로

하지만, job의 길이를 모르지만 이러한 metrics를 가장 최소화할 방법이 무엇일까?

→ MLFQ