5. Processor Scheduling

Basic Concepts in Scheduling

서버가 어떤 job을 pick해서 돌릴 것인가에 대한 이슈가 scheduling

서버 : CPU-process, Disk-I/O, Printer-jobs

Nonpreemptible vs Preemptible

Nonpreemptible : 뺏을 수 없는 것

ex) Disk, Printer (생각해보면 자명함)

Preemptible : 뺏을 수 있음을 허용함.

ex) CPU

CPU Scheduling

Long term scheduling

The long-term scheduler, also known as the admission scheduler, is responsible for selecting which processes or jobs should be admitted into the system. It decides which jobs to add to the ready queue based on system resources availability and user priority.

Middle term scheduling

The middle-term scheduler is a type of scheduler that is not always present in all operating systems, and it sits between the long-term scheduler and the short-term scheduler. It is sometimes referred to as the swapping or swapping scheduler.

The primary function of the middle-term scheduler is to manage the processes that are already in memory. When the long-term scheduler admits a process, the middle-term scheduler decides which processes should be swapped out of the memory to the secondary storage (e.g., hard disk) to make room for the newly admitted process.

Short term scheduling

The short-term scheduler selects processes from the ready queue that are residing in the main memory and allocates CPU to one of them.

(통상적으로 이야기하는 스케줄링)

Dispatcher

Ths dispathcer is the module that gives control of the CPU’s core to the process selected by the CPU scheduler

• Switching context from on process to another

• Switching to user mode

• Jumping to the proper location in the user program to resume that program

→ context switch마다 필요하므로 빠를수록 좋음

이때, 한 프로세스를 멈추고 다른 프로세스를 시작하기까지 걸리는 시간을 dispatch latency 라고 부름

CPU Scheduling Criteria

policy : 정책 (어느 것을 고를 것인가)

좋은 스케쥴러라는 것이 무엇인가?라는 문제가 있음

CPU oriented criteria

1. CPU utilization : CPU의 활용을 가장 극대화

2. throughput : 단위 시간당 얼마나 많은 프로세스가 끝날 수 있는지

Process oriented criteria

1. turnaround time : 해당 프로세스를 돌리기 위해서 얼마나 많은 시간이 걸리는지 (ready queue에서 기다리는데 걸린 시간, 실제 실행시간, IO때문에 wait한 시간 모두 포함)

2. waiting time : 미시적으로 가서 ready queue에서 기다리는 시간이 얼마나 긴지

3. response time : 최초의 output이 나오기까지 걸리는 시간 (interactive system에서는 turnaround time보다는 response time이 중요하다.)

Process Behavior : CPU-bound or I/O-bound

Process의 behavior를 보면 어떤 부분은 cpu를 돌리고, 어떤 부분은 io를 처리함

CPU burst : I/O 없이 cpu instruction을 수행

결과적으로 CPU-burst와 I/O burst 가 반복되는 양상

💡

CPU-bound processes : longer CPU bursts hand I/O burst

하지만, 어떤 process가 CPU-bound process인지 I/O bound process인지 미리 알기 힘들기 때문에 절대적인 policy를 정하기는 힘듦

Notion of Priority

Reqeusts are serviced according to their priorities

→ 위급한 정도를 반영해서 response 시간을 결정

즉, 위급도라는 것을 잘 정의하는 것이 중요.

이 과정을 preemptive 로 할 수도 있고, nonpreemptive 로 할 수 있다.

• Low priority의 경우는 계속 선택되지 않을 수 있음 (Starvation problem). 이를 어떻게 해결할 것인가?

  Aging : as time progresses, increase the priority

Characterization of Scheduling Policies

The selection function

어떤 것을 고를 것인가 (Determines which processes in the ready queue is selected next for execution)

The decision mode

언제 스케줄 할 것 인가를 골라야 한다.

1. Nonpreemptive

2. preemptive : 강제로 뺐을 수 있음

사실 2개를 같이 고려해야 한다. 굉장히 중요한 개념이다.

1번과 4번을 제외하고는 cpu 스케줄링을 뺏기지 않음

→ 만약 IO를 하지 않으면 뺏기지 않음

Timeout에 의해서 cpu가 뺐는 것 : preemptive인 것! (내가 time quantum을 다 썼으므로)

3번 case : IO opeation이 끝나서 cpu한테 interrupt를 걸음 → kernel이 interrupt handler가 돌음 → 이에 따라 해당 process가 ready상태로 바뀜. 만약 해당 proess가 현재 돌고 있는 process보다 prioirty가 높고, preemptive인 경우 해당 프로세스를 돌릴 수도 있음

(즉 현재 돌고 있는 process의 작업을 뺐을 수도 있음)

→ 이렇게 돌리는 형태를 preemptive라고 한다.

즉 non-preemptive인 경우는 1번과 4번의 경우에만 스케줄러를 고려한다고 생각해주면 된다. (스스로 내려놓기 전까지는 계속 돌음)

→ 리눅스가 window의 경우는 preemptive임. 즉 blocked된 process가 깨어났을 때 우선순위가 더 높으면 해당 process를 돌린다.

Scheduling Algorithm

FCFS Scheduling

• 특징이 무엇인가?

  먼저 들어온 process가 먼저 처리됨

  Decision mode : 일반적으로 nonpreemptive (Time quantum이 없음) → 그런 측면에서는 interactive system에서는 문제가 발생

• 문제가 무엇인가?

  1. 한번 cpu를 잡으면 block되거나 끝날 때까지 는 수행됨. 따라서 blocked 된 process는 오래 기다기게 될 가능성이 존재함. (IO bound process가 오래 기다릴 가능성이 있음)

  2. 따라서 CPU-bound process가 한번 잡으면 쭉 쓰게 된다. (IO-bound process의 경우 오래동안 wait하게 됨). CPU-bound process가 유리

  3. average waiting time이 긴 편

• Convoy effect

  All the other processes wait for the one big process to get off the cpu. This effect result in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first

• Round robin의 motivation

  만약 여기에 Time sharing을 주면 해결되지 않을까?

• Waiting time 연습

  

  

Round Robin

• FCFS에서 개선된 점

  Time quantum을 줘서 독점을 하지 못하게끔 하겠다.

  일반적으로 time quantum은 10~100 millisecond를 준다. 즉 preemptive 한 방식

• 특징이 무엇인가

  1. FIFO에 비해서 process switch이 빈번하게 발생

  2. 이러한 지점에서 overhead가 발생

  3. Time quantum을 아주 늘려버리면 FIFO와 같음

  즉, 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU를 독점하지 않고 공평하게 이용될 수 있게 한다. (time-sharing environment에 적합한 방식)

• 문제가 무엇인가

  1. time quantum을 어떻게 줄 것인가? : 성능에 영향을 많이 줌
     1. Time quantum이 작을 때 : system의 overhead가 커짐
     2. Time quantum이 클 때 : individual process의 response가 느려짐

     일반적으로 80%의 cpu burst가 1 time quantum보다 작은 것이 좋다고 알려져 있음

  2. 여전히 CPU-bound favor

     계속 cpu-bound process가 cpu를 많이 쓰게 되는 문제점이 발생. I/O bound process는 주어진 quantum을 다 못쓰고 block되는 반면, cpu bound process는 주어진 time quantum을 다 사용하므로

  3. average waiting time이 긴 편

  4. Turnaround time도 time quantum의 사이즈에 영향을 받음

• Waiting time 연습

  

→ 아직 CPU bound favor라는 것이 가장 큰 문제점

→ 그래서 다른 관점으로 접근해보자고 시작하게 됨

Shortest Job First (SJF) Scheduling

• 특징이 무엇인가

  1. process의 next cpu burst 가 작은 process를 고르는 것. 만약 동일하다면 FCFS

     💡

     주의 : 전체 cpu burst가 아닌 next cpu burst를 기준으로 고르는 것이다.

  2. I/O bound processes가 우선적으로 pick 된다. (기존의 문제점들을 해결)

• Decision mode (2가지 존재)

  1. Nonpreemptive

     고른 것을 계속 돌림

  2. Preemptive

     만약 새로운 job이 들어왔는데, 해당 job이 cpu burst가 더 작으면 뺐기게끔 할 수도 있음. 이러한 정책을 Shortest-Remaining-Time-First (SRTF) 이라고 부른다. (대신 switching은 자주 발생함)

Optimal algorithm : 평균적으로 기다리게끔하는 것이 가장 작은 알고리즘. (optimizes the average waiting time)

• 문제는 없는가?

  1. Starvation problem

     a request with a long CPU burst may wait indefinitely

  2. next CPU burst를 예측하는 것이 힘듦

• Waiting time 연습

  Non-preemptive case

  

  Preemptive case

  

  2시점에서는 P1의 burst time이 5이고, P2는 4이므로 P2가 선택되는 것

  → 즉 새로운 process가 생길때마다 running 하고 있는 것과 새로운 것을 검토

Estimating CPU Burst

그래서 next cpu burst 예측할 것인가 (최적화 문제를 푸는 것)

→ CPU burst를 예측한 알고리즘 결과에 기반해서 SJF

과거는 알고 있기 때문에, 결국 이전까지의 cpu burst를 활용해서 미래의 cpu burst를 예측하는 것

• 방법 2가지

  1. Simple averaging

     평균을 침

  2. Exponential averaging

     사실 locality가 있기 때문에, 단순 평균을 치는 것보다는 최근의 수행한 cpu burst에 weight를 조금 더 주는 것이 좀 더 타당함.

     $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

     ($\tau_n$ : stores the past history, $t_n$ : recent information)

     → 이렇게 함으로써 과거의 정보에 대한 가중치가 기하급수적으로 감소하게 됨.

사실 SJF는 Priority scheduling의 예시 중 하나이다.

일반적으로 priority는 internally, 혹은 externally하게 정의 될 수 있다.

• Internally

  Internally defined priorities use some measurable quantity or quantities to compute the priority of a process

• Externally

  External priorities are set by criteria outside the operating system.

• Priority scheduling의 문제점

  Starvation problem

  • 그렇다면 해결책은 무엇인가?

    1. Aging 즉, 지속적으로 우선순위를 올려주면 된다.

    2. RR과 priority scheduling를 결합 (동일한 priority면 RR방식으로)

Multilevel Queue Scheduling

이전까지는 하나의 큐만 이용했는데, 여러 개의 ready queue를 둬서 큐마다 다른 스케줄링 정책을 이용하는 등의 변주가 가능. 그 방법론 중 하나임.

• 문제

  1. 몇 개의 ready를 둘 것인지

  2. 각 큐마다 어떤 스케줄링 정책을 펼 것인가

  3. 어느 큐부터 우선적으로 고려해야하는가 (각 큐별로 time-slice를 주는 방식도 고려할 수 있음)

Multilevel Feedback Queue Scheduling (MLFQ)

일반적으로 multilevel queue scheduling의 경우 들어갈 때 permanently queue에 assign된다. (즉 queue가 중간에 바뀌지 않는다.) 반면 MLFP는 중간에 다른 queue로 변경될 수 있다.

• 왜 일반적으로 들어갈 때 고정되는 방식으로 설계를 했는가?

  low scheduling overhead때문

• 특징이 무엇인가

  1. 기본적으로 CPU burst에 의거해서 process들을 여러 queue에 넣고, 만약 특정 process가 너무 많은 CPU time을 쓴다면 lower-priority queue에다가 옮긴다. 이 과정을 통해 I/O bound인 process와 interactive process가 favor된다.

  2. 너무 오래 기다린 프로세스의 경우에도 higher-priority queue로 옮긴다. 위 과정을 통해 starvation 문제를 해결할 수 있다. (위 과정을 Aging이라고도 하기도 한다.)

• 문제

  자기보다 위에 있는 큐들이 모두 다 비어야 돌릴 수 있음. 이를 preemptive scheduling with dynamic priorities라고 부름. 만약 자기보다 위에 있는 ready queue에 process가 들어오면 해당 process를 우선적으로 처리. 물론 앞서 설명한 것처럼 Aging을 통해 위 문제를 해결할 수 있음.

Fair Share Scheduling (FSS)

다양한 user가 사용하는 상황에서 fair하게 CPU를 사용하고 싶은 것.

Multiple-Processor Scheduling

이제는 cpu의 개수가 많아진 상황. 그래서 CPU scheduling은 더욱 복잡해짐.

→ 성능도 문제지만 소모 전력/발열도 고려대상에 들어감

UNIX Scheduler

Batch system : 모았다가 수행

출발 : interactive system (shell 같은 느낌으로 이해하면 됨)

→ Interactive하게 하는 IO bound process를 고려하는 process에 favor를 주려고하는 것이 목표가 됨

1. Interactive processes typically run using short CPU bursts

2. Want to minimize response time

Real-Time Scheduling

Required to complete a critical task within a guaranteed amount of time.

• 범용 os와의 차이가 무엇인가?

  범용 os는 계산만 잘 해주면 됨. 근데, real-time os는 주어진 시간 안에 computation을 수행해야함.

ex) 전쟁 무기

1. HW time : 진짜 시간을 맞춰야하는 상황 (아주 critical)

   완전히 다른 scheduling을 씀 : EDF, RM

2. SW time : 하드웨어만큼은 아님. 예를 들어 video streaming을 생각하면 이해가 쉬움
   1. SCHED_FIFO
   2. SCHED_RR

   이 2개를 쓰면 real-time scheduling

Priority inversion problem

p3가 mutex를 먼저 걸고 p2가 돌게 됨.

그리고 p1이 공유 데이터 접근을 원함. 근데 mutex를 걸어둔 상황이므로 p2를 진행.

→ 우선순위가 낮은 process가 먼저 돌고 있는 문제가 발생하게 됨

아래가 priority inheritance solution

p3에게 순간적으로 p1의 priority를 inheritance

→ 그리고 p3를 작업을 마치고 p1을 돌 수 있음.

(시험에는 x)

Algorithm Evaluation

Deterministic Modeling

Takes a particular predetermined work load

→ Too specific and require too much exact knowledge

Queuing Models

Insight를 가지기는 좋음

Problem : 제한이 많음 (job이 poisson distribution 가정 등등)

(Trace-Driven) Simulation Analysis

A simulation using a trace as its input

• Trace가 무엇인가

  a time-ordered record of events on a real system

Real process를 추적해서 trace하고 그걸 simulator의 input으로 줌.

Solaris Scheduling

• 특징

  Priority-based

  Time-sharing

  Preemptive scheduling

4개의 prioirty로 나눔 (Multi-level queue랑 유사)

1. Real-time class : soft real-time scheduling

2. System class : no time-slice

3. Time sharing

4. Interactive class

Fully Preemptable Kernel

→ kernel이 preemptable하냐 안하냐 (system call handling하는 도중에도 바꿀 수 있음) 예를 들어 system call handler가 돌아가는 도중에도 다른 process를 돌릴 수도 있음

이전까지는 kernel이 non-preemptive임. 즉 예를 들어 특정 process의 system call handler를 처리하고 난 뒤에야 scheduling을 통해 이후의 process를 돌릴 수 있음

Windows Scheduling

Static priority : priority가 고정된 multi-level queue (Multi-level queue)

Dynamic priority : run-time에 유저의 우선순위가 바뀌는 것 (Multi-level feedback queue)

Linux Scheduling

Priority-based, time sharing, preemptive scheduling

1. Time sharing

2. Ranking process : 우선 순위에 따라서 스케줄러에 의해 선택

3. Supports both static and dynamic process priority

   윈도우 케이스 참고

4. Linux processes are preemptive

검색해 볼 것

SCHED_FIFO : 우선순위는 고정이고, 우선순위가 높은 친구가 오면 뻇김

SCHED_RR : time-sharing만 더 추가함

하지만, 위 2개는 일반 유저가 이용불가

SCHED_OTHER : SCHED_FIFO랑 SCED_RR보다는 우선순위가 더 높을 수는 없음.

상위 100개까지는 SCHED_FIFO, SCHED_RR이 사용

→ 위부터 우선순위를 계속 보는 것 (항상 top부터 봄)

하위 40개에 있는 process는 이동할 수 있음

→ kernel이 해당 process가 wait된 시간을 체크하고(cpu bound인지 io bound인지 파악) 만약 cpu bound process인 경우에는 하위로 내림, 반대로 i/o bound process인 경우에는 상위로 올림.

→ Fairness is guaranteed only for SCHED_OTHER (우선 순위를 조정함) ; 커널 입장에서의 fairness

• Time quantum을 어떻게 설정해야 하는가?

  해당 process의 priority에 의해 time quantum이 결정

  (올라갈수록 time quantum을 많이 줌)

  → 그래서 문제가 발생했고, 그것때문에 등장한 것이 CFS Scheduling Algorithm

Direct invocation

current process가 바로 block되어야 할 때 scheduler가 바로 불림

(즉, block되어야 할 때 바로 scheduler를 바로 부름)

read/write할 때

Lazy invocation

timer interrupt를 처리할 때 해당 함수의 time quantum이 남았는지 여부를 관리하는 flag에 정보를 담음

timer handler에서 일을 다 처리하고 해당 process가 flag를 점검하고 그때 부름

💡

Checks before resuming the execution of a User Mode process