1.Process scheduling

process가 CPU를 할당받는 과정에 어떤 스케줄링 기법이 존재하는지에 대한 파트다.

Multiprogramming (Multi-tasking)

• Process scheduling은 multiprogramming을 대상으로 한다.

• 하나 이상의 CPU를 갖는 시스템에서 여러개의 프로세스가 동시에 운영되는 상황이다.

• CPU를 놀고있게 만들지 말자는 개념에서 탄생했다.

• Resource management : CPU, Memory 두 가지의 중요한 자원이있다.

  • Resources for time sharing <- CPU 대상으로 Process scheduling
    

  • Resources for space sharing <- Memory 대상
    

Goals of Scheduling

system performance 전체를 향상시키기 위할 뿐만이 아니라, 프로세스 각각을 위해서도 필요하다. 시스템 전체를 위해서만 스케줄링을 하다보면 어떤 프로세스는 CPU 할당을 대기만 하게되는 상황이 발생할 수도 있기 때문이다.
system performance (시스템 성능)은 구체적으로 어떤 성능을 말하는 걸까? 아래의 performance indices이 시스템 성능을 판단하는 지표들이다.

Typical performance indices

하나하나 간단하게 살펴보자

• Mean response time
  • 사용자가 어떤 요청을 submission하는 시점부터 첫 번째 response가 나올때까지의 시간이다. 간단히 말해서 응답이 나올때까지 걸리는 시간이다. 보통은 여러개의 프로세스가 동시에 실행되기 때문에, mean을 사용한다.
  • Interactive systems (시스템에 명령을 내리고 사용자가 기다리는 시스템)에서 중요하다.
• Throughput (처리량)
  • 단위시간당 종료하고 나가는 프로세스의 개수.
  • batch systems (사람이 명령을 돌려놓고 보고있지 않는 시스템) 에서 중요하다.
• Resouce utilization
  • 주어진 구간동안 특정 resouce가 얼마나 많이 사용됐는지에 대한 지표이다.
  • batch systems에서 주로 활용된다.
• Turnaround time
  • 어떤 요청이 submission 된 후에 실행을 마칠때까지의 시간. mean response time과 달리 실행을 완전히 마칠때까지의 시간이므로 몇 시간이 될 수도 있다.
• Waiting time
  • 어떤 프로세스가 ready queue에서 대기하는 시간의 합이다.
• Predictability

Mean response time, Resouce utilization은 동시에 좋아질 수 없다. 예를 들어 수강신청 할 때를 생각해보면 사람이 몰리는 정각에는 resouce utilization이 좋다고 말할 수 있다. 하지만 대기시간이 길어지기 때문에 mean response time은 느려질 수 밖에 없다.

Scheduling Criteria

어떤 기준으로 스케줄링을 해야할까? 어떤 성질을 갖는 프로세스를 먼저 스케줄링을 해줄까

• Process characteristics
  • I/O-bound , compute-bound
  • 보통 I/O-bound 프로세스를 먼저 스케줄링 해주는데, 이유는 먼저 스케줄링된 I/O-bound 프로세스는 CPU를 할당받고 time quantum을 아주 조금 쓴다. 다시말해서 running 상태에서 얼마 지나지 않아 I/O request를 받고 CPU를 반납하기 때문에 compute-bound가 이어서 CPU를 할당받을 수 있다. I/O-bound는 I/O device를 활용하고 compute-bound는 CPU를 병렬로 사용하는 상황이 되므로 일반적으로 선호된다.
  • Batch or interactive (background or foreground)
• Urgency of the process
  • Hard real-time(딱 맞춰야함), soft real-time, non-real-time(deadline 없음)
• Process type and importance
  • Importance and domain of the application (중요한 프로그램 먼저)
• Service time of the process
  • CPU burst time
  • busrt time이 짧은 프로세스를 먼저 처리하면 유리하다.
• Process priority
  • Priority-based scheduling

Scheduling Level

2장에서 잠깐 봤던 내용을 간단히 살펴보자. CPU를 할당하는 Short-term scheduling이 4장의 주 내용이다.

• Long-term scheduling
  • Job scheduling, admission scheduling, high-level scheduling이라고도 한다.
  • Job들을 대상으로 누굴먼저 kernel에 등록시켜 process로 탄생시킬까
    • Control multiprogramming degree (multiprogramming degree가 너무 높은 상태면 long temr scheduler가 새로운 process등록을 차단한다)
    • Control process mix (I/O-bound 와 compute-bound 프로세스를 적절히 선택한다)
  • 대부분의 time-sharing systems에서는 바로 프로세스로 등록돼서 long-term scheduling을 하지 않는다.
• Medium-term scheduling
  • Memory allocation : swapping(swap-in/swap-out) 관련
  • memory management scheme 부분에서 자세히 다룰 예정이다.
• Short-term scheduling
  • Process scheduling, low-level scheduling이라고도 한다.
  • Ready queue에 있는 프로세스 중 누구에게 CPU를 할당해줄지 스케줄링.
  • 빈도수가 높기 때문에 스케줄링을 빨리해야한다.

Scheduling Policies

• Preemptive/non-preemptive scheduling

  • Preemptive scheduling
    • 현재 실행중인 프로세스의 의도와 관계없이 쫓아내고 다른 프로세스에게 CPU 할당한다.
    • Time-sharing systems은 preemptive이다.
    • flexibility, adaptability, performance improvements의 장점 때문에 대부분 사용한다.
  • Non-preemptive scheduling
    • running인 프로세스가 자발적으로 CPU를 반납할때까지 작동한다.
    • 장점 : context switch overhead가 적다.
    • 단점 : priority inversions이 잦다.

• Priority

  • Static priority (external priority)
    • 고정된 우선순위로 프로세스가 생성되고 종료될때까지 우선순위가 바뀌지 않는다.
    • 외부에서 주어지는 경우가 많다.
  • Dynamic priority (internal priority)
    • 프로세스의 상태가 바뀜에 따라 우선순위가 바뀐다.
    • kernel안에서 내부적으로 결정되는 경우가 많다.
    • 일반적으로 많이 쓴다.

Terminologies

• CPU burst vs I/O burst : 각각 번갈아가며 나타난다.
  

2. Scheduling Schemes

8가지의 스케줄링 기법들을 하나하나 살펴보자.

• FCFS
• RR
• SPN
• SRTN
• HRRN
• Priority
• MLQ
• MFQ

FCFS (First-Come-First-Service) scheduling

• Non-preemptive scheduling -> time quantum 없음
• Scheduling criteria
  • Arrival time (at the ready queue) : ready queue에 먼저 도착한 프로세스를 먼저 실행한다.
  • Faster arrival time process first
• Resource utilization이 좋다
• batch system에는 적절하지만, interactive systems에는 적합하지 않다.
• 단점
  • Convoy effect : 많은 프로세스가 big process때문에 기다려야한다.
  • Mean response time이 길다.

RR (Round-Robin) scheduling

CPU를 사용하는 시간이 time quantum인 2보다 크지 않은 것을 볼 수 있다.

• Preemptive scheduling
• Time quantum을 각각의 프로세스에 적용한다.
  • System parameter
  • Time quantum을 모두 소모한 프로세스는 CPU는 releases하고 ready state로 돌아간다.(timerrunout)
• Scheduling criteria
  • Arrival time (at the ready queue) : ready queue에 먼저 도착한 프로세스를 먼저 실행한다.
  • Faster arrival time process first
• preemption 때문에 context switching overhead가 커진다. 그럼 time quantum을 크게 하면 되겠다라는 생각이 드는데 그럼 결국 FCFS와 비슷한 성능을 내게 된다.
• Interactive/time-sharing system에 적합하다.
• RR기법은 time quantum의 사이즈에 성능 영향을 많이 받는다.
  • Very large time quantum -> FCFS
  • Very small time quantum -> process sharing (n개의 프로세스가 CPU를 공평하게 나눠쓰게 되는 현상), context switching overhead가 너무 커진다.

SPN (Shortest-Process-Next) scheduling

• Non-preemptive scheduling
• SJF (Shortest Job First) scheduling이라고도 한다.
• Scheduling criteria
  • Burst time (at the ready queue) : ready queue에 있는 프로세스들 중 burst time이 짧은 프로세스를 먼저 실행한다.
  • Shortest next CPU burst time first scheduling
• 장점
  • average waiting time을 최소화할 수 있다.
  • 어떤 순간에 시스템에 존재하는 프로세스 개수를 최소화한다. -> ready queue, overall space가 줄어든다.
  • 많은 프로세스들의 response time이 줄어든다. (위 예제를 보면 waiting time이 0인 프로세스가 많다)
• 단점
  • Starvation, 무기한 지연 현상(blocking) -> 예제에서 P2는 제일 먼저 도착했지만 가장 늦게 스케줄링됐다.
    • Long burst-time process를 처리할 방법이 필요하다.
    • aging으로 해결가능함 <- HRRN에서 공부
  • 사실 프로세스를 실행한 다음에야 burst time을 알 수 있기 때문에 정확한 burst time을 기반으로 스케줄링 하는 것은 불가능하다. 대신 프로세스가 앞서 burst한 시간을 기반으로 한 추정치를 기반으로 Burst time을 설정한 후 스케줄링한다.CPU는 최근 burst time과 비슷하게 burst할 가능성이 높기 때문에 최근 burst time에 더 가중치를 부여하는 방식으로 추정치를 계산한다.

SRTN (Shortest Remaining Time Next) scheduling

• SPN의 preemptive 버전이다.
• Preemptive scheduling
  • running 중인 프로세스의 남은 burst time보다 더 짧은 burst time을 가진 프로세스가 들어올 때 preemption 된다.
• 단점
  • SPN과 마찬가지로 kernel에서의 burst time estimation overhead가 발생한다.
  • 추가로 남은 burst time을 체크하는 overhead가 있다.
  • context switching overhead도 있다.

HRRN (High-Response-Ratio-Next) scheduling

• SPN의 starvation을 aging으로 해결한다.
  • Response ratio라는 새로운 개념을 도입해 long burst time process에게 기회를 준다.
  • ready queue에서 기다리는 프로세스들의 우선순위를 증가시킨다.
• Response ratio
  
• Scheduling criteria
  • Response ratio : response-ratio 가 높은 프로세스를 먼저 실행한다.
• burst time이 짧으면 우선순위가 높아지므로 SPN과 유사한 면이 있다.
• 단점 : SPN과 마찬가지로 burst time estimation overhead가 있다.

Priority scheduling

• Either preemptive or non-preemptive
• Scheduling criteria : 프로세스의 우선순위 (Process priority) 에 따라 스케줄링한다. 우선순위가 같은 경우에는 FCFS로 스케줄링한다.
• Priority가 부여되는 방식이 시스템마다 다르다.
• 단점 : Starvation <- aging을 활용해 해결 가능하다.

MLQ (Multi-level Queue) scheduling

• Ready queue를 여러개두고, queue에 우선순위를 둔다.
• 모든 프로세스들은 특정 queue에 영구적으로 배정된다.
• 각각의 큐는 스케줄링 기법을 따로 가질 수 있다.
• 큐들 간의 스케줄링은 fixed-priority preemptive 기법으로 한다.

MFQ (Multi-level Feedback Queue) scheduling

• Arrival time, burst time 등의 정보가 필요없다.
• Process가 Feedback 정보를 통해 dynamic하게 ready queue로 들어간다.
• Feedback
  • 프로세스의 CPU 사용 패턴 , I/O 사용 패턴에 대한 정보를 가지고있다.
• MFQ의 목적
  • Burst time이 짧은 프로세스 ( I/O bound process) 를 선호하자.<-SPN/SRTN/HRRN과 같다.
  • Adaptability를 향상시키자.
• MFQ의 특징
  • Dynamic priority
  • Preemptive scheduling
  • Favor short burst-time processes ( I/O-bound processes)
  • Improved adaptability
  • 프로세스의 어떤 정보도 없이 SPN, SRTN, HRRN의 효과를 낸다.
• MFQ의 원칙
  • 처음 생성되는 프로세스는 제일 우선순위가 높은 RQ0로 들어간다.
  • sleep state에 있던 프로세스가 wakeup으로 돌아올 땐 원래 큐로 들어간다. -> I/O bound 선호하게 됨
  • running state에 있던 프로세스가 preemption으로 timerrunout되면, RQi+1로 한 단계 아래 큐로 들어간다. -> I/O bound 선호하게 됨
  • 가장 아래 큐에서 나갔다온 프로세스는 가장 아래 큐로 다시 들어간다.
• MFQ의 variations
  • 낮은 우선순위에 있는 프로세스들과 compute-bound process들에게 나타나는 starvation 해소하기 위해서 낮은 우선순위 queue의 time quantum을 길게 줘서 큐가 한 번 실행될 때 CPU를 오래 사용할 수 있도록 해준다.
  • 낮은 우선순위에 있는 프로세스들과 compute-bound process들에게 나타나는 starvation 해소하기 위해서 waiting time이 길어지면 큐의 우선순위를 높여주는 aging 기법 적용이 가능하다.
  • I/O -> CPU -> I/O 이런식의 cycle을 가지고 있는 process의 경우 CPU burst를 하는 도중에 우선순위가 계속 떨어지게 된다. 후에 I/O를 하기 위해서 우선순위를 올릴 수 있는 방법이 없기 때문에 I/O bound process는 move up 시켜서 해결할 수 있다. (I/O를 하고 돌아오는 프로세스는 RQi-1로 돌아오게 해서 구현가능)
• MFQ 구현을 위한 parameter
  • queue를 몇 개 둘까
  • queue마다의 scheduling algorithm
  • process를 higher-queue로 언제 업그레이드 할까
  • process를 lower-queue로 언제 내릴까
  • 첫 번째 프로세스는 어느 큐로 넣을까

3. Case Studies

Unix

• Interactive system -> priority-based scheduling

• Priority

  • Kernel priority (0~59)
  • User priority (60~119)

• Clock handler : clock handler가 주기적으로 CPU에 interrupt해서, 우선순위를 바꿔준다.

• Scheduling 원칙

  • MFQ와 마찬가지로 우선순위가 높은 큐를 먼저 스케줄링한다.
  • 프로세스의 우선순위는 계속 변한다.

• Scheduling mechanism

  • Priority adjustment
    Unix에선 1/60s마다 CPU count가 1씩 증가한다. time slice는 1이고, 모든 프로세스들이 CPU만 사용한다고 가정하고 다음 예시를 보자. Ready queue에 3개의 프로세스가 있다. 3개 모두 Priority가 60인 상태이므로 random하게 하나의 프로세스를 고른다. P1이 선택되고 time quantum = 1만큼 CPU burst한다. 그 동안 CPU count 값은 0에서 60으로 증가한다. time quantum이 끝나고, clock handler가 CPU에 interrupt를 넣어 우선순위를 재조정하게된다. Unix의 Priority adjustment 원칙에 따라서, P1은 60/2 + basePriority + niceValue = 75의 우선순위를 갖는다. 이제 3개의 프로세스가 75/60/60의 Priority를 가지고, P2와 P3중 랜덤으로 선택해 방금 과정을 다시 반복한다.
    -> CPU를 사용한 프로세스는 Priority가 떨어지고, CPU를 사용하지 않은 프로세스는 우선순위에 변동이 없거나 올라가기 때문에 Fair하다.

• FSS 기법

  • Fair Share Scheduling으로, 프로세스들을 fair share group으로 분할하는 것이다.
  • 분할된 그룹 단위로 CPU time을 공평하게 분배하겠다는 원리이다. 프로세스 관점에서 보면 1/3로 공평하지만, User의 입장에서보면 불공평하기 때문에 사용자 단위로 group을 나눠서 User가 공평하게 스케줄링한다. 2s를 보면, B가 CPU를 사용해서 같은 그룹에 속해있는 C의 group count가 같이 증가하는 것을 볼 수 있다. A->B->A->C 순서로 실행된다. Group1 Group2가 딱 반반 사용했다.
  • CPU count, Group count 같은 값은 Unix의 PCB 영역의 일부인 U-area에서 유지된다.

Windows OS

• Thread scheduling (Process라는 용어보단 Thread라고 한다)
• Priority-based, preemptive scheduling
• MFQ 기법에 근간을 두고있다.
• Priority
  • Variable class : 15 ~ 1 (1이 가장 낮음)
    • HIGH_PRIORITY_CLASS
    • ABOVE_NORMAL_PRIORITY_CLASS
    • NORMAL_PRIORITY_CLASS
    • BELOW_NORMAL_PRIORITY_CLASS
    • IDLE_PRIORITY_CLASS
  • Real-time class : 32 ~ 16
    • REALTIME_PRIORITY_CLASS
• Relative priorities in each class
  • TIME_CRITICAL
  • HIGHEST
  • ABOVE_NORMAL
  • NORMAL
  • BELOW_NORMAL
  • LOWEST
  • IDLE 42단계의 ready queue를 갖는 MFQ 기법으로 이해하면 된다.
• 특징
  • Thead가 time quantum을 다 쓰면 우선순위는 떨어지게 된다. (단, Real-time class의 thread는 우선순위가 낮아지지 않는다)
  • Variable class에 있는 우선순위 thread가 wait operation에서 released 됐을 때(sleep -> ready) scheduler가 우선순위를 올려준다.
    • keyboard / mouse I/O -> large increase (사용자와의 interaction이기 때문에 크게 올려 빠르게 사용할 수 있도록 한다.)
    • Disk I/O -> moderate increase
  • Thread가 background에서 foreground로 돌아오면 그 thread의 time quantum이 3배 증가한다. <- 사용자 중시
• UMS (User-Mode Scheduling)
  • kernel이 스케줄링을 하는 동안 overhead가 생기기 때문에 시스템 전체의 성능이 하락하는 것을 방지하기 위해서 user mode에서도 스케줄링할 수 있게 만든 기법이다.

Linux

• process보다 task라고 한다.

• Version 2.4 이전

  • Priority-based scheduling 과 RR scheduling, MFQ를 사용하는 Unix와 유사했다.
  • 문제점
    • SMP ( Symmetrical multi-processor) 일 때 여러개의 CPU를 잘 활용하지 못했다.
    • task의 많아질수록 스케줄링하는데 너무 오래걸린다. (No scalability)

• Version 2.4~2.6.22

  • O(n), O(1) scheduling
  • SMP support
    • Load balancing (부하균형) : 모든 CPU에 동일하게 task를 배분했다.
    • Processor affinity : 특정 CPU에서 실행되던 프로세스는 그 CPU에서만 running한다. CPU의 cache를 최대한 활용하기 위함이다.
  • Fairness
  • Ideal for large server workloads
  • interactive application (interaction이 많은 데스크탑) 에서는 좋지 않았다.

• Version 2.6.23 ~

  • Scheduler classes를 둬서 여러개의 scheduling 기법을 같이 사용할 수 있다.
  • CFS (Completely Fair Scheduler) <- 대표적인 scheduler class
    • red-black tree로 ready queue를 만들어서 scalable하고 O(logN)의 time complexity를 갖도록 했다.

• Linux scheduler

  • I/O-bound vs CPU-bound : IO를 선호하지만 cpu-bound를 무시하진 않는다.

  • Preemptive scheduling

  • Priority

    • Real-time range : 0 ~ 99 <- Kernel mode ( SCHED_FIFO, SCHED_RR )
    • Nice value range : 100 ~ 139 <- User mode ( SCHED_OTHER 보통 CFS )
      

  • Scheduler classes

    • 각각의 sheduler class 마다 다른 스케줄링 알고리즘을 사용한다.
    • Default scheduling class : CFS scheduling algorithm
    • Real-time scheduling class : Another algorithm(간단한 RR같은 알고리즘 사용)(Run queue가 Ready queue다)

  • Priority 배정 방법

    • Real-time tasks : 높은 우선순위를 받고 변하지 않는다.
    • All other tasks : longer sleep time 이면 more I/O-bound로 보고 more interactive라고 보기 때문에 우선순위를 올린다. nice values사용한다.

4. Multicore processor Scheduling

SMP architecture는 어떤 점들을 고려해야하는지 알아보자.

• Multicore processors : 하나의 chip안에 여러개의 core가 존재해 병렬처리가 가능한 경우로 각각 register set, cache를 가지고 있다. 운영체제 입장에서는 각각 다른 physical processor로 보인다.
• 2단계 스케줄링
  1. process를 어느 core에 배정할지 선택 (processor affinity에 의해 쭉 그 core에 있게 된다) -> Load balancing 고려
  2. 그 코어에서 어떤 process를 실행할지 선택
• Processor affinity
  • 항상 같은 코어에 프로세스를 위치시킨다.
  • Soft affinity : 같은 processor에 위치시키도록 최대한 보장한다.
  • Hard affinity : 무조건 한 processor에 위치시킨다.
• Load balancing
  • workload를 시스템에 있는 모든 CPU에 공평하게 나눠갖게 하는것이다.
  • Push migration : processor들의 load를 모니터하다가 overloaded -> underloaded로 프로세스를 push해준다.
  • Pull migration : Idel processor가 busy processor로부터 process를 pull해온다.
  • 보통 push, pull 둘 다 사용한다.

++ Real time system : task들이 모두 deadline을 가지고 들어온다. Priority-based scheduling(preemptive). static priority를 갖는 RM(Rate-Monotonice) scheduling과 dynamic priority를 갖는 EDF(Earliest-Deadline-First) scheduling 기법이 있다.