Lecture 5 : Process Scheduling

 

다중 프로그래밍

- 여러 개의 프로세스가 시스템 내 존재

- 자원을 할당 할 프로세스를 선택해야 함 : Scheduling

 

- 자원관리

  ㆍ시간 분할 (Time sharing) 관리

     -> 하나의 자원을 여러 스레드들이 번갈아 가며 사용

     -> 예) 프로세서

     -> 프로세스 스케줄링 (Process Scheduling) : 프로세서 사용시간을 프로세스들에게 분배

 

  ㆍ공간 분할 (Space Sharing) 관리

     -> 하나의 자원을 분할하여 동시에 사용

     -> 예) 메모리

 

 

스케줄링의 목적

- 시스템의 성능 향상

- 대표적 시스템 성능 지표 (index)

  ㆍ응답시간 : 작업 요청으로부터 응답을 받을 때까지의 시간

  ㆍ작업 처리량 : 단위 시간동안 완료된 작업의 수

  ㆍ자원 활용도 : 주어진 시간동안 자원이 활용된 시간 (Utilization = 자원이 활용된 시간 (Tr) / 주어진 시간 (Tc))

   -> 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

 

 

반환시간, 대기시간, 응답시간의 관계

 

스케줄링의 기준 (Criteria)

스케줄링 기법이 고려하는 항목들

프로세스의 특성 (IO bounded, compute-bounded)

시스템 특성 (Batch system, Interactive system)

프로세스의 긴급성 (hard- or soft- real time, non-real time systems)

프로세스 우선순위

프로세스 총 실행 시간 등.... 

 

 

CPU burst vs IO burst

- 프로세스 수행 = CPU 사용 (CPU 사용 시간) + IO 대기 (IO 대기 시간)

Burst Time의 구성

 

스케줄링의 단계 (Level)

- 발생하는 빈도 및 할당 자원에 따른 구분

- Long-term scheduling

   ㆍ장기 스케줄링

   ㆍJob scheduling

 - Mid-term scheduling

   ㆍ중기 스케줄링

   ㆍMemory Allocation

 - Short-term scheduling

   ㆍ단기 스케줄링

   ㆍProcess scheduling

 

 

Long-term scheduling

- Job scheduling : 시스템에 제출 할 (Kernal에 등록 할) 작업 (Job) 결정

  예) Admission schduling, High-level scheduling

- 다중프로그래밍 정도(degree) 조절

  ㆍ시스템 내의 프로세스 수 조절

- I/O bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야한다 : 시스템의 효율성 향상 목적

- 시분할 시스템에서는 모든 작업을 시스템에 등록

 

Mid-term scheduling

- 메모리 할당 결정

  ㆍIntermediat-level scheduling

  ㆍSwapping (swap-in / swap-out )

 

Short-term scheduling

- Process scheduling

- 프로세서를 할당할 프로세스를 결정

  예) Processor scheduler, dispatcher

- 가장 빈번하게 발생한다.

  ㆍInterrupt, block (I/O), time-out etc.

- 매우 빨라야한다.

 

 

스케줄링 정책

- 선점 (Preemptive) vs 비선점 (Non-preemptive)

- 우선순위 (Priority)

 

비선점 스케줄링 (Non-preemptive scheduling)

- 할당받을 자원을 스스로 반납할 때까지 사용

- 장점 : Context switch overhead가 적음

- 단점 : 잦은 우선순위 역전, 평균 응답시간 증가

 

선점 스케줄링 (Preemptive scheduling)

- 타의에 의해 자원을 빼앗길 수 있음

  예) 할당 시간 종료, 우선순위가 높은 프로세스 등장

- Contetxt swtich overhead가 큼

- Time-sharing system, real-time system에 적합 : 응답성이 높아짐

 

우선순위 (Priority)

프로세스의 중요도

- Static priority (정적 우선순위)

  ㆍ프로세스 생성 시, 결정된 priority가 유지됨

  ㆍ구현이 쉽고, overhead가 적음

  ㆍ시스템 환경 변화에 대한 대응이 어려움

- Dynamic priority (동적 우선순위)

  ㆍ프로세스의 상태 변화에 따라 priority 변경

  ㆍ구현이 복잡, priority 재계산, overhead가 큼

  ㆍ시스템 환경 변화에 유연한 대응 가능

 

 

 

스케줄링 알고리즘

 

 

FCFS (Firest-Come-First-Service)

FCFS

- Non-preemptive scheduling 

- 도착 시간 기준 : 먼저 도착한 프로세스를 먼저 처리

- 자원을 효율적으로 사용 가능

- Batch system에 적합, interactive system에 부적합

- 단점

  ㆍConvoy effect

     하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기시간 >> 실행시간)

  ㆍ긴 평균 응답시간

 

FCFS의 예

 

 

 

RR (Round-Robin)

Round Robin의 도식도

- Preemptive scheduling

- 스케줄링 기준

  ㆍ도착 시간 기준

  ㆍ먼저 도착한 프로세스를 먼저 처리

- 자원 사용 제한 시간(time quantum)이 있음

  ㆍSystem parameter

  ㆍ프로세스는 할당된 시간이 지나면 자원 반납 (Timer-runout)

  ㆍ특정 프로세스의 자원 독점 방지

  ㆍContext switch overhead가 큼

- 대화형, 시분할 시스템에 적합 

- Time quantum(δ)이 시스템 성능을 결정하는 핵심 요소

  ㆍδ가 매우 크다면 : FCFS

  ㆍδ가 매우 작다면 : Processor sharing

    -> 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌

    -> 체감 프로세서 속도 = 실제 프로세서 성능의 1/n

    -> 매우 높은 context switch

 

 

 

SPN (Shortest-Process-Next)

- Non-preemptive scheduling

- 스케줄링 기준

  ㆍ실행 시간 (burst time) 기준

  ㆍburst time 가장 작은 프로세스를 먼저 처리

  ㆍSFJ (Shortest Job First) Scheduling

 

- 장점 :

  ㆍ평균대기시간(WT) 최소화

  ㆍ시스템 내 프로세스 수 최소화 : 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상 

  ㆍ많은 프로세스들에게 빠른 응답 시간 제공

- 단점 :

  ㆍStarvation (무한대기) 현상 발생

    -> Burst Time;BT이 긴 프로세스는 자원을 할당 받지 못할 수 있음 : Aging 등으로 해결

  ㆍ정확한 실행시간을 알 수 없음

    -> 실행시간 예측 기법이 필요

 

 

 

 

SRTN (Shortest Remaining Time Next)

- SPN의 변형

- Preemptive scheduling : 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨

 

- 장점 :

  ㆍSPN의 장점 극대화

- 단점 :

  ㆍ프로세스 생성 시, 총 실행 시간 예측이 필요함

  ㆍ잔여 실행을 계속 추적해야함 = overhead

  ㆍContext switching overhead

-> 구현 및 사용이 비현실적 (총 실행 시간 예측, 잔여 실행 추적이 힘듬)

 

 

 

HRRN (High Response Ratio Next)

- SPN의 현실적인 변형 (SPN + Aging, Non-preemptive scheduling)

- Aging concepts : 프로세스의 대기 시간(WT)를 고려하여 기회를 제공

- 스케줄링 기준

  ㆍ Response ratio가 높은 프로세스 우선

- 응답률;Response ratio = (WT + BT) / (BT)  : BT 대비 얼마나 기다렸는가

  ㆍSPN의 장점 + Starvation 방지

  ㆍ실행 시간 예측 기법 필요 (overhead)

 

 

 

 

 

MLQ (Multi-level Queue)

- 작업(or 우선순위)별로 별도의 ready queue를 가짐

  ㆍ최초 배정 된 queue를 벗어나지 못함

  ㆍ각각의 queue는 자신만의 스케줄링 기법 사용

- Queue 사이에는 우선순위 기반의 스케줄링 사용 -> Fixed-priority preemptive scheduling

- 장점 :

  ㆍ빠른 응답시간 (우선순위가 높은 프로세스에 한정)

- 단점 : 

  ㆍ여러 개의 queue 관리 등 스케줄링 overhead

  ㆍ우선순위가 낮은 queue는 starvation 현상 발생 가능

MLQ

 

 

 

 

MFQ (Multi-level Feedback Queue)

- 프로세스의 Queue 간 이동이 허용된 MLQ

- Feedback을 통해 우선 순위 조정 : 현재까지의 프로세서 사용 정보(패턴) 활용

- 특성

  ㆍDynamic priority

  ㆍPreemptive scheduling

  ㆍFavor short burst-time processes

  ㆍFavor I/O bounded processes

  ㆍImprove adaptability

- 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음

 

- 단점 :

   ㆍ설계 및 구현이 복잡

   ㆍ스케줄링 overehead가 큼

   ㆍStarvation 문제

- 변형 : 

   ㆍ각 준비 큐마다 시간 할당량을 다르게 배정

       -> 프로세스의 특성에 맞는 형태로 시스템 운영 가능

   ㆍ입출력 위주 프로세스들을 상위  단계 큐로 이동, 우선 순위 높음

       -> 프로세스가 block될 때, 상위의 준비 큐로 진입하게 함

       -> 시스템 전체의 평균 응답 시간을 줄임, 입출력 작업 분산 시킴

   ㆍ대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동

       -> Aging 기법

MFQ

- IO bounded는 긴급성은 높으나, BT가 짧아 우선순위를 높게 해주는 것이 좋음 : 시스템의 평균 응답시간 단축 가능

- Computed bounded : IO bounded와 반대로 BT는 기나 긴급성이 높지 않기에 우선순위를 낮게 해주는 것이 좋음