process scheduling

앞에서 배운 process에서 cpu는 처리량을 늘리기 위해서 context switch를 한다고 했다.

즉 cpu는 running과 waiting의 2가지 상태가 번갈아가며 수행되는 것이다.

처리하려는 작업에 따라 cpu burst가 길 수도 있고, I/O burst가 길 수도 있다.

cpu burst가 긴 경우가 cpu bound, I/O burst가 긴 경우 I/O bound이다.

I/O burst의 예로는 동영상 재생, 문서 편집 등이 있다. 즉 사용자와 interactive한 것이다.

cpu bound의 예로는 복잡한 수식 계산 등이 있다. 천문학 수식 계산 등등...

그럼 이 작업들을 어떻게 스케쥴링 해야할까?

 

cpu scheduler ( = short-term scheduler)

: ready 상태의 ready queue에서 어떤 것들을 running으로 가져올까

일단 상식적으로 I/O bound process는 사용자와 interacitve이므로 이걸 더 우선순위로 계산해야할 것이다. 따라서 cpu bound 보다 I/O bound가 cpu 점유에서 우선적이다.

 

cpu scheduling은 다음과 같은 상황에서 발생한다.

- running -> ready

- running -> waiting

- waiting -> ready

- terminate

이 경우들은 non-preemptive, 즉 점유권를 내주지 않는다.

 

그렇다면 process를 ready queue에서 cpu로 이동하는 것은 어떻게 이루어질까?

앞에서 process state에서 봤었다.

ready queue에서 cpu로 process를 올리는 행위를 dispatch라고 한다.  또한 dispatch 할 때는 스케쥴링의 순서를 따르게 된다.

dispatcher module은 dispatch를 하며 process에게 cpu control을 넘겨준다. 이를 통해 작업이 수행된다.

 

cpu control에는 다음과 같은 것들이 포함된다.

- switching context

- switching to user mode

- jump to proper location

그렇다면 scheduling의 순서는 한번 정하면 변하지 않는 것일까?

 

preemptive vs non-preemptive, 선점과 비선점

- preemptive

: 중요한 프로세스가 있다면 다른 process를 ready 상태로 바뀌고 중요한 process에게 우선순위를 부여한다.

이는 진행중인 작업을 중단하고 context switch를 강제한다.

 

- non-preemptive

: 현재 수행중인 프로세스는 끝까지 수행한다.

이는 진행중인 작업이 완벽하게 blocked될 때까지 기다린다.

따라서 다음과 같은 상황에서만 scheduling이 발생한다.

- running -> wait

- terminate

이를 제외하고는 하던 작업을 기다린다.

 

선점과 비선점 둘 중에 어떤 것이 더 best일까?

당연하게도 preemptive가 더 좋다. 왜냐햐면 중요한 프로세스에 우선순위를 부여하기 때문에 응답시간이 빠르기 때문이다.

 

---

scheduling criteria

스케쥴링에는 몇가지 원칙이 있다.

- cpu utilization

- throughput

- turnaround time

- waiting time

- response time

 

CPU utilization

: cpu 사용률을 항상 최고로 유지해야한다. 즉 cpu를 쉬지 않게 해야한다.

 

Troughput

: 단위 시간 당 처리량을 높여야 한다. 즉 많은 명령어들을 처리하도록 스케쥴링 해야한다.

 

Trun-around time

: 어떤 프로세스가 작업을 다 수행할 때까지 걸리는 시간이다. 즉 실행 시간을 줄여야 한다.

 

Wating time

: ready queue에서 기다리는 시간이다. 

 

Response time

: 사용자 request에 대해 응답을 주는 시간이다. 즉 wait queue에서 기다리는 시간이다.

 

cpu utilization, throughput => cpu bound process 이므로 이는 높여야 한다.

turnaround time, waiting time, response time =>  I/O bound process 이므로 이는 낮춰야 한다.

하지만 둘은 trade-off 관계이다.

 

cpu bound process scheduling은 context switching을 줄여야 한다. 즉 dispatch latency가 필요하다.

반면에 I/O bound process scheduling은 context switching을 많이 해야 대기시간을 줄일 수 있다.

따라서 이 둘은 trade-off 관계이다. 

 

---

scheduling goals

시스템 종류 별로 스케쥴링의 목표가 다를 수 있다.

 

All system

- fairness: cpu 자원을 process들에게 공정하게 분배

- balance: 모든 시스템이 쉬지 않고 돌아갈 수 있도록 scheduling

 

Batch system

: 한번에 하나의 process만 cpu에 올려서 실행하기 때문에 다른 프로세스 처리를 신경쓰지 않아도 된다.

- throughput

- turn around time

- cpu utilization

 

Interactive system

: 대화형 시스템 등 사용자와 interactive한 시스템들이다.

- response time

- waiting time

- proportionality

 

Real-time system

- deadline

- predictability

 

 

scheduling non-goals

모든 스케쥴링에서 피해야할 부분이 있다.

 

Starvation

- poor scheduling, synchronization 등으로 어떤 한 process가 cpu 자원을 모두 사용하지 않도록 해야한다.

즉 모든 process가 공평하게 실행될 수 있도록 fairness를 지켜야한다.

---

process scheduling algorithms

scheduling의 대표적인 알고리즘들을 살펴보자

- FCFS/ FIFO

- SJF + SRJF

- Priority scheduling

- Round Robin

- Multi-level Queue

- Multi-level Feedback Queue, MLFQ

- Real-time, EOF

 

---

FCFS/ FIFO

: First Come, First Served

가장 먼저 들어온 게, 가장 먼저 처리된다.

 

fairness 관점에서는 가장 좋은 방법이다. 왜냐하면 모든 process가 평등하기 때문에 starvation이 없기 때문이다.

그렇기 때문에 우선순위가 없는  non-preemptive이다.

 

problems

-> average waiting time의 증가

예를 들어 small job이 large job 뒤에 있다면 이 작업은 오래 기다려야한다. 따라서 평균 waiting time은 증가한다.

이는 cpu, I/O의 poor overlap을 유발한다.

 

-> convoy effect

: waiting time이 긴 현상

 

Gantt chart

burst time이 각각 24, 3, 3인 process들이 있다면 FCFS로 처리한 gantt chart는 다음과 같다.

---

SJF

: Shortes Job First

가장 짧은 burst time을 가진 process부터 수행한다.

 

average waiting time이 가장 짧다. 따라서 scheduling에서 waiting time의 관점에서 보면 최적의 방법이다.

non-preemptive, preemptive 두가지의 구현이 가능하다.

 

problems

-> cpu burst time?

cpu burst time은 작업을 수행하기 전까지 알 수가 없다.

 

-> potentially starve

waiting time을 줄일 수 있지만, long process들은 우선순위가 계속 뒤로 밀리는 현상이 발생한다.

따라서 fairness하지 않으므로 starvation의 가능성이 있다.

 

two schemes

- preemptive: 현재 수행하는 시간보다 cpu burst time이 작으면 그 process를 실행 

=> SRTF, Shortes Remaining Time First

- non-preemptive: 일단 하는 프로세스는 다 끝냄

 

 

non-preemptive version

다음 표와 같은 도착 시간과 burst time을 가진 프로세스들이 있다고 하자

non-preemptive는 우선순위를 내주지 않기 때문에 먼저 온 p1을 종료할 때까지 쭉 실행한다.

그러다 시간이 5초가 되면 p2, p3, p4가 다 도착해있기 때문에 7초에서 스케쥴링 할때는 process들의 burst time을 비교하게 된다.

이때 가장 시간이 작은 p3를 먼저 실행한다.

그 후에 스케쥴링 할때는 p2, p4의 burst time이 같으므로 도착한 순서대로 실행하면 된다.

이 경우 average waiting time은 4이다.

 

preemptive version

위에서 본 표와 똑같은 상황이라고 하자.

0초에서는 p1밖에 없기 때문에 이를 실행한다.

그러다 2초가 되면 p2가 도착하는데, 이 경우 p1의 남은 burst time과 p2의 burst time을 비교한다.

즉 p1이 2초동안 작업을 실행했으므로 남은 burst time은 5인데, 이는 p2의 4보다 크기 때문에 p2에게 우선순위를 부여해서 p2를 실행한다.

그 후 4초가 되면 p3가 도착하는데 이 경우 다시 p2와 p3의 burst time을 비교한다.

p2의 남은 시간은 2이고, p3는 1이므로 p3에게 우선순위를 부여하고 실행한다.

이런식으로 진행하면 다음과 같이 average waiting time은 3이다.

 

하지만 cpu burst time은 실행하지 않고는 알아내기 어렵기 때문에 최적이지만, 적용이 힘들다.

 

---

Priority Queue

: 프로세스에 우선순위를 부여해서 처리한다.

cpu가 우선순위가 높은 process부터 자원을 할당한다. 이때 우선순위는 priority number가 작을수록 높다.

 

problems

-> 우선순위가 낮은 process들은 순위가 계속 뒤로 밀린다. 즉 starvation이 발생한다.

이는 프로세스의 우선순위를 시간이 지나면 높여주는 Aging 기법으로 해결 가능하다.

 

priority queue

 

priority number가 같은 순서대로 process를 묶어서 실행한다. 따라서 같은 우선순위를 처리하는 알고리즘도 따로 필요하다. 예를 들면 우선순위 1은 SJF, 우선순위 2는 FCFS 등등

그러나 현실적으로 이들은 적용이 힘들다. 따라서 다음에 배울 RR을 많이 사용한다.

---

Round Robin(RR)

: 프로세스들에게 일정한 time quantum을 주고 번갈아가면서 수행한다.

 

할당된 time이 끝나게 되면 process는 preempted된다. 즉 우선순위를 넘겨준다.

만약 time이 끝났음에도 불구하고 처리할 작업이 남아있는 경우 ready queue의 맨 뒤로 넘어가게 된다. 이는 timer interrupt이다.

따라서 굉장히 fair한 알고리즘이며, waiting time과 response time을 줄여준다.

 

예를 들어 ready queue에 프로세스가 n개 있고, time quantum이 q인 경우 프로세스는 각각 1/n cpu time을 가진다.

그렇다면 time quantum의 크기는 어떻게 설정해야 최적일까?

 

time quantum을 정하는 기준

- I/O bound: time quantum을 작게 해서 waiting time, response time을 줄이는 것을 최대화

- CPU bound: time quantum을 크게 해서 연산을 최대화

하지만 time quantum이 너무 크게되면 FIFO와 다를게 없고, time quantum이 너무 작게 되면 context switch의 횟수가 늘어나므로 오버헤드가 커진다.

따라서 Rule of Thumb 를 적용하여 정하는 경우가 많다.

 

A rule of thumb: 80%의 cpu burst time이 time quantum보다 작아야 한다.

리눅스는 이 rule을 적용하여 60ms의 cpu burst time을 가진다. 즉 리눅스 cpu burst time은 대부분 60ms 이하이다.

대부분 평균 cpu burst time보다 time quantum을 크게 정한다. 아무래도 context switch의 오버헤드가 더 크기 때문인듯하다.

 

다음과 같은 경우를 생각해보자

quantum을 크게 하는 경우 context switch의 오버헤드는 작지만 waiting time, response time이 느려진다.

반대로 quantum을 작게 하는 경우 waiting time, response time은 빠르지만 context switch의 오버헤드는 커진다.

즉 이 둘은 trade-off 관계에 있다.

 

Round Robin Gantt Chart

SJF보다 turn-around time(실행시간)은 길지만 response time은 빠르다.

---

Combining Algorithms

: 여러가지 scheduling algorithms을 섞어서 사용하는 것이다.

multiple queue가 있고, 각 queue마다 다른 algorithm을 적용한다.

 

Multilevel Queue

: 스케쥴링 queue를 하나 두고 그 queue하나에 FCFS 또는 RR같은 scheduling algorithm을 적용하는 것이 아니라 queue자체를 여러개를 두고 각각 특성에 맞게 알고리즘을 선정하는 것이다.

 

ready queue

- foreground (interative): 빠른 응답을 줘야하기 때문에 사용자와 가까운 프로세스를 중요시 한다. RR을 주로 사용

- background (batch): queue를 두 부분으로 나누어서 각각에 다른 알고리즘을 적용한다. 대부분 FCFS

 

하지만 ready queue에서도 scheduling이 일어나야한다.

즉 foreground와 background 사이의 스케쥴링이 우선순위 스케쥴링이 필요하다.

- Fixed priority scheduling: starvation의 가능성이 있다.

- Time Slice: 특정한 cpu time을 받아서 분배한다.

예를 들면 cpu time의

80% RR -> foreground

20% FCFS -> background

이런식으로 주게 되면 foreground에게 우선순위를 주는 것이 된다.

 

Multilevel Queue Scheduling

: 프로세스 성능에 맞게, 또는 queue의 특성에 맞게 여러 queue를 두고 각각은 queue들마다 Algorithms을 다양하게 설정한다.

그런 queue들 간의 scheduling은 우선순위 scheduling이다.

 

system process는 운영체제에서의 process들이므로 종료되어서는 안된다. 따라서 항상 높은 우선순위를 부여한다.

priority가 낮은 process를 그냥 student라고 한다고 배웠는데 교수님께서 설명해주셨던 것 같은데 왜 student인지 까먹었다...

 

 

Multilevel Feedback Queue

multilevel queue의 단점은 한번 queue에 프로세스가 들어가면 다른 queue로 이동할 수 없다는 것이다.

즉 scheduling 오버헤드가 낮지만 유연하지 못하다.

이러한 flexibility를 보완하기 위해 나온것이 multilevel feedback queue이다.

즉 queue와 queue 사이의 이동이 가능하고, 프로세스간의 중요도를 나타내는 방식의 차이이다.

 

Multilevel Feedback Queue Scheduler

- queue를 많이 설정한다.

- 각각 queue마다 scheduling algorithm은 다양하게 설정한다.

- process를 높은 우선순위로 높이는 시기를 설정한다.

- process의 우선순위를 낮추는 시기를 설정한다.

- process를 어떤 queue에 추가할지 결정한다.

(이는 aging에서 많이 활용된다.)

 

 

Multilevel Feedback Queue

처음 queue의 time quantum인 8초동안 process의 작업을 수행하지 못하면 그 다음 level의 queue로 process가 이동한다.

이런식으로 cpu burst time이 길면 자동으로 내려오게 되어있고, 내려올수록 cpu bound process들이다.