운영체제 - CPU 스케쥴링(3)

2020-09-23

OS를 공부하면서 정리를 한 내용들 입니다.

이번 챕터는 CPU 스케쥴링에 관련해 정리한 챕터입니다.

지난 시간에 SJF(Shortest-Job-First)라는 것에 대해서 알아봤습니다.

SJF는 Optimal한 방법인데 이것말고 다른 알고리즘들은 왜 있을까요?

그이유로 SJF에는 치명적인 약점이 2가지가 있습니다.

치명적인 약점

  • Starvation을 발생시킵니다.

Starvation : 굶어 죽는것, SJF는 짧은 CPU burst를 우선순위로 주다보니 long한 Job은 Queue가 계속 쌓였을 때 CPU가 할당이 오랫동안 되지 않는 경우

  • CPU burst time을 처음엔 명확하게 알 수 없습니다.

추정(estimate)만이 가능하다. 과거의 CPU burst time을 이용해서 추정한다.

Priority Scheduling

우선순위가 높은 프로세스에게 CPU를 먼저주는 방식입니다.

SJF도 일종의 Priority Scheduling.

우선순위 값을 Integer형으로 주어지는데 값이 작을수록 높은 우선순위를 가집니다.

이것 또한 preemptive와 nonpreemptive 2가지가 있습니다.

우선순위가 높을 때 프로세스에게서 CPU를 빼앗을지 아닌지로 구별합니다.

Priority Scheduling의 약점

Starvation을 발생시킵니다.

이것에 대한 해결책으로 Aging을 합니다.

Aging : 프로세스의 우선순위를 시간이 진행됨에 따라 높여주는 것 입니다.

Round-Robin(RR)

실제로 CPU 스케쥴링에서 제일 많이 사용되는 방법의 근간이되는 방식 입니다.

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가집니다.(일반적으로 10~100 milliseconds)

할당 시간이 끝나면 프로세스는 선점(preempted)당하고, ready queue의 제일 뒤에 가서 다시 대기합니다.

n 개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우,

각 프로세스의 최대 q time unit 단위로 CPU 시간의 1/n을 얻습니다.

즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않습니다.

  • Performances

    할당시간이 길다면? FCFS와 똑같습니다.

    할당시간이 너무 짧다면? context swtich 오버헤드가 커집니다.

일반적으로 SJF보다 average turnaround time(평균 소요시간)은 길지만 response time은 더 짧습니다.

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의