CPU Scheduling Algorithm

CPU 스케줄링 알고리즘

• FCFS : first come first served

• SJF : shortest job first

• SRTF : shortest remaining time first

• Priority Scheduling

• RR : round robin

• Multilevel Queue

• Multilevel Feedback Queue

• Multiple-Processor Scheduling

• Real-time scheduling

• thread scheduling

FCFS : first come first served

• 프로세스의 도착 순서대로 스케줄링된다.

• 단점은 짧은 수행시간을 가진 프로세스라도 늦게 도착하면 오랜 시간을 대기해야한다는 것이다.

SJF : shortest job first

• 각 프로세스의 다음번 CPU burst time 을 가지고 스케줄링에 활용한다.

• CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄한다.

• 종류

  • non-preemptive

    • 일단 CPU 를 잡으면 이번 CPU burst 가 완료될 때까지 CPU 를 선점당하지 않는다.

  • preemptive

    • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면, CPU 빼앗긴다.

    • 이 방법을 SRTF 하고 한다. → SRTF : shortest remaining time first

• optimal

  • 주어진 프로세스들에 대해서 minimum average waiting time 을 보장한다.

• 다음 CPU burst time은 어떻게 알 수 있는가?

  • 추정만 가능하다.

  • 과거의 CPU burst time 을 이용해서 추정한다.

Priority Scheduling

• 우선순위 번호가 각 프로세스에게 할당된다.

• 가장 높은 우선순위를 가진 프로세스에게 CPU 를 할당한다.

• smallest integer = highest priority

  • preemptive

  • nonpreemptive

• SJF 는 일종의 priority scheduling 이라고 할 수 있다.

  • priority = predicted next CPU burst time

• 문제점

  • starvation : 낮은 우선순위를 가진 프로세스들은 아마 시작도 못해볼 것이다.

• 해결책

  • aging : 대기 시간이 흐를수록 우선순위를 높여주는 방법

RR : round robin

• 각 프로세스는 동일한 크기의 할당시간 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 이상 기다리지 않는다.

• 퍼포먼스

  • q large → FCFS

  • q small → context switch 오버헤드가 커진다.

• 할당 시간이 넘어가서 다시 queue의 제일 뒤로 가야할 때, 다시 마지막 시점부터 정확하게 시작할 수 있다면, 굉장히 효과적인 방법이 될 수 있다.

Multilevel Queue

• ready queue 를 여러개로 분할한다.

  • foreground - interactive

  • background - batch, no human interaction

• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.

  • foreground - RR

  • background - FCFS

• 큐에 대한 스케줄링이 필요

  • fixed priority scheduling

    • foreground 를 항상 먼저 serve 하고 background 를 나중에 하는 방법

    • 단점 : background 는 오랜 시간 대기해야한다.

  • time slice

    • 각 큐에 CPU time 을 적적한 비율로 할당한다.

    • foreground : 80%, RR

    • background : 20%, FCFS

• 줄마다 우선순위가 다르다.

• 우선순위대로 나열하자면 다음과 같다.

  • system → interactive → interactive editing → batch → student

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동이 가능하다.

• 에이징을 이와 같은 방식으로 구현할 수 있다.

• multilevel feedback queue scheduler 를 정의하는 파라미터들

  • queue 의 수

  • 각 큐의 scheduling algorithm

  • process 를 상위 큐로 보내는 기준

  • process 를 하위 큐로 내쫗는 기준

  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

• 보통은 처음 들어오는 프로세스를 첫 queue 에 할당하고 밑으로 갈수록 시간을 길게 둔다.

  • CPU 이용 시간이 짧은 프로세스는 첫줄에 들어와서 바로 끝날 수 있도록하고

  • 이용 시간이 길수록 낮은 queue 로 이동하여 좀 더 기다리도록 한다.

  • CPU 버스트가 짧은 프로세스에게 운영시간을 많이 주는 방식이다.

• 스케줄링

  • 새로운 job은 제일 윗쪽 queue, Q0에 들어가게 된다.

  • CPU 를 잡아서 할당시간 8 millisec 안에 수행된다.

  • 할당 시간안에 다 끝내지 못했다면, 그 아래 queue 로 내려간다.

  • Q1에 줄서서 기다렸다가 CPU 를 잡아서 16ms 동안 수행이 되고

  • 그 안에도 다 못끝냈다면 Q2로 쫓겨난다.

Multiple-Processor Scheduling

• cpu 가 여러개인 경우, 스케줄링은 더욱 복잡해진다.

• homogeneous processor

  • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.

  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더욱 복잡해진다.

• load sharing

  • 일부 프로세서에 job 이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.

  • 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

• symmetric multiprocessing, SMP

  • 각 프로세서가 각자 알아서 스케줄링 결정

• asymmetric multiprocessing

  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.

  • CPU가 여러개이고, 하나의 CPU가 책임을 진다.

Real-time scheduling

• hard real time systems

  • 정해진 시간안에 반드시 끝내도록 스케줄링해야한다.

  • 보통 periodical 하게 수행되는 경우가 많다.

• soft real time systems

  • 일반 프로세스에 비해 높은 priority를 갖도록 해야한다.

Thread scheduling

• local scheduling

  • user level thread

  • 운영체제가 thread의 존재를 모름

  • 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지를 결정한다.

• global scheduling

  • kernel level thread

  • 운영체제가 thread의 존재를 알고 있음

  • 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.

그렇다면, 어떤 알고리즘이 가장 적절할까?

Algorithm Evaluation

• queueing models

  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다.

• implementation & measurement

  • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교한다.

  • 하지만 이 방법은 수행하기에 어렵다.

• simulation

  • 알고리즘을 모의 프로그램으로 작성 후, trace(시뮬레이션 프로그램에 input으로 들어갈 데이터)를 입력으로 하여 결과를 비교한다.