CPU 스케줄링

                                     CPU

 

어떤 프로그램이든 프로그램이 실행되는 것은 CPU burst와 I/O burst를 반복하며 실행된다,

단 프로그램이 종류에 따라 반복될 수도 있고 CPU burst만 나올수도 있다.

 

 

 

 

 

 

 

 

프로세스의 특성 분류

 

프로세스는 그 특성에 따라 다음 두가지로 나눔

- I/O-bound process

- cpu를 잡고 계산하는 시간보다 I/o에 많은 시간이 필요한 job

- many sort CPU bursts

 

- CPU-bound process

- 계산 위주의 job

- few very long CPU bursts

 

 

 

 

 

 

 

 

 

CPU scheduler & dispatcher (소프트웨어나 하드웨어가 따로 존재하는게 아니라 운영체제 안에 있는거임, 운영체제 안에 존재하는 기능임)

 

CPU scheduler : ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

dispatcher : cpu의 제어권을 cpu scheduler에 의해 선택된 프로세스에게 넘긴다

: 이 과정을 context switch(문맥 교환)라고 한다.

 

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태변화가 있는 경우이다.

1. Running -> Blocked (예: I/O 요청하는 시스템 콜)

2. Running -> Ready (예: 할당시간 만료로 timer interrupt)

3. Blocked -> Ready (예: I/O 완료 후 인터럽트)

4. Terminate

 

1,4 에서의 스케줄링은 nonpreemptive (=강제로 빼앗지 않고 자진 반납) 비선점형

All other scheduling is preemptive (=강제로 빼앗음) 선점형

*preemptive 라는 용어는 중요하니 외워두도록

 

 

scheduling algorithm이 여러개가 있는데 그중에 뭐가 효과적인지 판단하는 성능 척도

 

 

 

scheduling criteria (성능 척도)

(= performance Index, Performance Measure)

 

 

CPU utilization (이용률) : keep the CPU as busy as possible

throughput (처리량) : # of processes that complate their execution per time unit

( 여기까지 시스템 입장의 성능척도)

Turnaround time (소요시간, 반환시간) : amount of time to execute a particular process

waiting time (대기 시간) : amount of time a process has been waiting in the ready queue

response time (응답 시간) : amount of time it takes from when a request was submitted until the first response is produced. not output

(for time-sharing environment)

( 프로세스 입장의 성능척도)

 

 

 

 

중국집 예시

사장 입장에서 주방장의 성능척도를 평가한다.

이용률 : 주방장이 놀지않고 계속 일하는가

처리량 : 주방장이 단위시간당 얼마나 많은 요리를 만드는가

소요시간, 반환시간 : 손님이 음식이 나오는데 기다리는시간, 먹는시간도 합쳐서 (코스요리)

대기시간 : 손님이 기다린 시간

응답시간 : 손님이 처음 응대 받는 시간

 

 

 

scheduling Algorithms

 

FCFS (First-Come First Served)

먼저 온 순서대로 처리 (비선점형)

효율적인 것은 아님

convoy effect : 시간이 오래걸리는 프로세스가 먼저 도착해서 뒤에온 짧게 끝나는 프로세스들이 앞의 프로세스가 끝날때까지 기다려야 하는 현상

 

SJF (Shortest-Job-First)

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

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

Two schemes:

- Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음

- Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

: 이 방법을 shortest-Remaining-Time-First (SRTF) 이라고도 부른다.

SJF is optimal, 주어진 프로세스들에 대해 minimum avarage waiting time을 보장

 

문제가 있다.

1. starvation (기아 현상) : CPU burst time이 긴 프로세스는 짧은 프로세스가 계속 들어오면 영원히 CPU를 갖지 못한다.

2. 다음 CPU burst time을 어떻게 판단? 미리 판단이 어렵다. 추정은 가능

과거의 CPU burst time을 이용해서 추정

(exponential averaging)

 

 

 

 

exponential averaging 점화식

Exponential Averaging

 

a =0

tn+1 = tn

Recent history does not count

 

​

 

a =1

tn+1 = tn

Only the actual last CPU burst counts

 

If we expand the formula, we get:

tn+1 = a tn+(1 - a) a tn -1 + …

+(1 - a )j a tn -1 + …

+(1 - a )n=1 tn t0

(약간 재귀식 –내생각)

 

Since both a and (1 - a) are less than or equal to 1, each successive term has less weight than its predecessor.

->이를 SJF 스케줄링해야할때마다 계산해야하는데 정확하지도 않고 복잡함

 

 

 

 

 

 

 

 

 

 

 

 

Priority scheduling (우선순위)

A priority number(integer) is associated with each process

highest priority를 가진 프로세스에게 CPU 할당

(smalliest integer = highest priority)

- preemptive

- nonpreemptive

SJF는 일종의 priority scheduling 이다.

- priority = predicted next CPU burst time

Problem

- Staration(기아 현상) : low priority processes my never execute.

Soultion

- Aging(노화) : as time progresses increase the priority of the process

 

 

Round Robin(RR) 현대에서 사용되는 알고리즘

각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가짐

(일반적으로 10-100 밀리세컨즈)

할당 시간이 지나면 프로세스는 (preempted)당하고 ready queue에 제일 뒤에가서 다시 줄을 선다.

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

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

performance

q large => FCFS (FIFO)

q small => context switch 오버헤드가 커진다.

 

일반적으로 SJF보다 avarage turnaround time이 길지만 response time은 더 짧다

(프로세스의 CPU 사용시간이 모두 같다면 SJF가 빠르다. avarae turnaround time에서)

 

 

 

turnaround time varies with time quantum

 

 

 

Multilevel Queue

계급제 같은 느낌

위로 갈수록 중요성이 큼

 

• Ready queue를 여러개로 분할
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • serve all from foreground then from background.
    • possiblilty of starvation
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • Eg. 80% to foreground in RR, 20% to background in FCFS

 

 

 

 

현대사회같은

중요성이 낮아도 먼저 실행될 수 있음

 

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • process를 상위 큐로 보내는 기준
  • process를 하위 큐로 보내는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

Example of Multilevel Feedback Queue

 

• Three queues:
  • Q0 - time quantum 8 miliseconds
  • Q1 - time quantum 16 miliseconds
  • Q2 - FCFS
• Scheduling
  • new job이 queue Q0으로 들어감
  • CPU를 잡아서 할당시간 8 miliseconds 동안 수행됨
  • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
  • Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
  • 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨남

 

 

 

Multiple-Processor Scheduling

• CPU가 여러개인 경우 스케줄링은 더욱 복잡해짐

• Homogeneous processor인 경우

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

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

• Load sharing

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

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

• Symmetric Multiprocessing (SMP)

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

• Asymmetric multiprocessing

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

 

 

Real-Time Scheduling

• Hard real-time system
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
• Soft real-time computing
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함

 

 

 

Thread Scheduling

• Local Scheduling(사용자프로세스가 수행)
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling(커널의단기스케줄러가 수행)
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 아닌 어떤 thread를 스케줄할지 결정

 

 

 

 

Algorithm Evaluation

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산
• Implementation(구현) & Measurement (성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation (모의 실험)
  • 알고리즘을 모의 프로그램으로 작성후 trace(시뮬레이션에 들어갈 input data)를 입력으로 하여 결과 비교