CPU Scheduling

Short-term scheduler라고 생각하면 된다.

현재 cpu 자원을 수행중인 프로세스 중 누구에게 줄지 결정하는 것

 

I/O bound job의 경우 입출력 위주의 작업으로 cpu를 짧게 여러번 사용한다. 반면에 cpu bound job은 계산 위주의 job으로 빈도는 작지만 한번 사용시 오래 사용하는 특징이 있다.

-> 사용자와의 interactive를 위해 i/o bound job에 cpu를 빨리 할당해줘야 한다.

 

State Transition Diagram

long-term scheduling은 new 를 편입시켜주는 역할을 한다. midium-term scheduling은 suspend되는 경우 사용된다. short-term scheduling은 흔히 cpu scheduling으로 어떤 process에게 cpu를 할당할지 결정해준다.

CPU Scheduler

:어떤 process에게 cpu를 줘서 실행할 것인가를 결정 (Multiprogramming environment)

cpu scheduler는 메모리에서 프로세스를 선택한다. 

cpu scheduling이 일어나는 4가지 경우

1. running 상태에서 waiting 상태로 바뀌는 경우 (i/o request)

2. running 상태에서 ready 상태로 바뀌는 경우 (timerunout)

3. waiting 상태에서 ready 상태로 바뀌는 경우 (i/o finished interrupt)

4.terminated

 

3의 경우는 interrupt 가 끝난뒤 원래 실행 program으로 돌아오는것이 아니기에 다시 cpu scheduling을 시작

1,4의 경우 nonpreemptive, 2,3은 preempive 경우이다.

 

Dispatcher

:  결정된 process에게 cpu를 주는 과정을 수행한다.

Dispatcher module

-switching context, switching to user mode, 사용자 프로그램의 적절한 위치로 jump 하고 재시작

 

dispatch latency

기존 프로세서를 중단하고 새로운 프로세서를 실행하는데 걸리는 시간 -> context switch overhead

 

Scheduling Criteria (기준)

CPU utilization : cpu가 계속 동작하도록 하는 것이 좋음 

Throughput : 단위 시간당 처리하는 작업의 양 -> maximize

Turnaround time : process 시작부터 끝까지 걸리는 시간 -> minimize

Waiting time : ready queue 에서 프로세스가 기다리는 시간

Response time : interactivity

 

Scheduling Algorithms

FCFS Scheduling

: First Come First Served ->먼저 온 process에게 먼저 cpu를 할당해주겠다. (공평성이 강점)

->실행시간이 짧은 프로세스가 먼저 들어오는 경우 waiting time이 줄어듬 -> convoy effect!

 

Shortest-Job-First(SJF) Scheduling

: 빠른 것을 앞으로 보내서 wait 시간을 줄이자 (average waiting time 측면에서 optimal)

두 가지가 존재

1. Nonpreemptive :더 짧은 것이 들어오더라도 기존의 실행이 끝난 후 실행

2. Preemptive : SRTF(Shortest-Remaining-Time-First), 더 짧은 프로세스가 들어오면 기존의 것을 중지하고 짧은 것을 먼저 실행

 

SJF와 SRTF의 예시

 

Determining Length of Next CPU Burst

: 알고리즘 사용을 위해 process의cpu 사용시간을 알아야함 -> 알수없음

estimate 하는 방식!

기존의 값들을 참고하여 예측하는 방식을 사용한다.

a값이 작아질수록 과거의 데이터가 공평하게 반영되고 값이 커질수록 최근에 대한 가중치가 높아진다. 최근 데이터에 가중치를 높게 주면 정확도가 높아지는 것을 확인 할 수 있다. 증감이 일정한 경우에는 정확도가 높은 값을 가질수 있다.

 

증감이 일정하지 않고 증감이 수시로 반복되는 경우 완전히 잘못된 결과를 가져올 수 있음 -> why?

최근 데이터에 가중치가 높으면 증가하다가 감소로 변하는 지점에서 감소에 대한 데이터 대신에 직전에 증가하던 데이터에 가중치가 높아져 정확도가 떨어지는 결과를 낼 수 있음

 

Priority Scheduling

:우선순위를 고려한 Scheduling 방식

각 process 에 priority number가 부여되고 이 번호에 따라 실행 (작은수가 높은 우선순위)

문제 : Starvation, 낮은 우선순위 프로세스는 계속 뒤로 밀려남

해결 : Aging, 대기시간이 길어짐에 따라 우선순위를 높여줌

 

Round Robin(RR)

: time quantum(cpu사용 가능 최대시간)을 설정하여 모든 프로세스가 돌아가면서 한번식 실행될 수 있도록 함 -> multiprogramming 목적으로 나온 방식

단점 :  time quantum 이 너무 작은 경우 context switch overhead 발생

higher average turnaround 이지만 response가 뛰어나다.

time quantum = 20인 RR 예시

 

Multilevel Queue

Ready queue를 나눈다.

forground(interactive) : RR -> i/o bound job

background(batch - no human interaction) : FCFS -> cpu bound job

 

RR자체로만 쓰기에는 부족하여 Multi level queue 사용

 

Scheduling 은 queue 사이에서 진행

1.Fixed priority scheduling : 모든 forground 를 수행 한 뒤에 background 수행 -> starvation 문제 발생

2.Time slice : 조금씩 나눠서 starvation 문제를 해결 eg. forground in RR 80%, background in FCFS 20%

 

Multilevel Feedback Queue

I/O bound job, CPU bound job을 어떻게 구분하기 위함

process들은 queue 간 이동을 함

 

MLFQ의 5가지 정책

1. queue의 개수

2. 각 queue에 해당하는 scheduling algorithms

3. upgrade 방식

4. demote 방식

5. 어떤 queue에 process를 넣을 것인지

MLFQ 예시

Real-Time Scheduling

Hard real-time systems

: guaranteed amount of time (deadline) 내에 반드시 수행되어야 함