5 프로세스 스케줄링

다중프로그래밍(Multi-programming)

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

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

- 스케쥴링

자원 관리

- 시간 분할(time sharing) 관리

   * 하나의 자원을 여러 스레드들이 번가아 사용

   * 예) 프로세서(Processor)

   * 프로세스 스케줄링(Process scheduling)

      프로세서 사용시간을 프로세스들에게 분배

- 공간 분할(space sharing) 관리

  * 하나의 자원을 분할

  * 예) 메모리(memory)

 

스케줄링(Scheduling)의 목적

시스템의 성능(performance) 향상

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

- 응답시간(response time) → Interface system, real-time

   * 작업 요청(submission)으로부터 응답을 받을때까지의 시간

- 작업 처리량(throghput)  → batch system

  * 단위 시간 동안 완료된 작업의 수

- 자원 활용도(resource utilization) → $$$

  * 주어진 시간(Tc)동안 자원이 활용된 시간(Tr)

Utilization = Tr / Tc

 

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

 

시스템 성능 지표들 (in textbook)

자원 할당의 공정성 보장

단위시간당 처리량 최대화

적절한 반환시간 보장

예측 가능성 보장

오버헤드 최소화

자원 사용의 균형 유지

반환시간과 자원의 활용 간에 균형 유지

실행 대기 방지

우선순위

서비스 사용 기회 확대

서비스 수 감소 방지

 

대기시간, 응답시간, 반환시간

                               작업

도착                실행 시작              첫 번째 출력                 실행 종료

                                                                                                           시간→

 ←대기시간        →  ←                 실행시간                            →

  Waiting time                  Burst time

 ←                 응답시간                      →

                 Response time

 ←                                         반환시간                                  →

                             Turn-around time

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

 

개요

스케줄링의 목적

스케줄링의 기준 및 단계

스케줄링 정책

기본 스케줄링 알고리즘들

Case study

 

스케줄링 기준 (Criteria)

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

프로세스(process)의 특성

I/O-bounded or computed-bounded

시스템 특성

Batch system or interactive system

프로세스의 긴급성(urgency)

Hard- or soft- real time, non-real time systems

프로세스 우선순위(priority)

프로세서 총 실행 시간 (total service time)

 

CPU burst vs I/O burst

프로세스 수행

= CPU 사용 + I/O 대기

CPU burst Compute-bounded process

CPU 사용시간

I/O burst > CPU -> I/O bounded process

I/O 대기 시간

 

Burst time은 스케줄링의 중요한 기준 중 하나

 

Pi

load store

add store              프로세서 버스트

read from file

입출력 대기             입출력 버스트

store increment

index                    프로세서 버스트

write to file

입출력 대기             입출력 버스트

load store

add store              프로세서 버스트

read from file

입출력 대기             입출력 버스트

 

스케줄링의 단계(Level)

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

- Long-term scheduling 가끔

   * 장기 스케줄링

  * Job scheduling

- Mid-term scheduling 종종

   * 중기 스케줄링

  * Memory allocation

- Long-term scheduling 자주

   * 단기 스케줄링

  * Process scheduling

 

Long-term scheduling

Job scheduling

- 시스템에 제출할 (Kernel에 등록할) 직업(Job) 결정

   * Admission scheduling, High-level scheduling

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

- 시스템 내에 프로세스 수 조절

I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함

- why?

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

- Long-term scheduling이 불필요

 

100

System

100

 

Job -Submit→ Process created

 

메모리 할당 결정 (memory allocation)

Intermediate-level scheduling

Swapping (swap-in/swap-out)

 

ready

↑swap-in

 |(resume)

                 

 |

suspended

ready

 

Process scheduling (CPU 할당)

Low-level scheduling

프로세서(processor)를 할당할 프로세스(process)를 결정

Processor scheduler, dispatch

 

가장 빈번하게 발생

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

매우 빨라야 함

- e.g.

- average CPU burst = 100ms

   scheduling decision = 10ms

- 10 x (100 + 10) = 9%

   of the CPU is being used simply for scheduling

 

ready - dispatch(schedule)→ running

             Processor(CPU)

 

Long-term scheduling

 

스케줄링 정책 (Policy)(방법)

선점 vs 비선점

Preemptive scheduling, Non-preemptive scheduling

 

우선순위

Priority

 

Preemptive/Non-preemptive scheduling

선점(빼앗을 수 있다)                비선점(뺏을 수 없다)

Non-preemptive scheduling

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

   예) system call, I/O, Etc.

- 장점

   Context switch overhead가 적음

- 단점

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

100

Pi   Ri

 

P0 Pk

 

Preemptive scheduling

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

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

- Context switch overhead가 큼 → System overhead 가 큼

- Time sharing shstem, real-time system 등에 적합 → 응답성 ↑

 

Priority

우선순위

프로세스의 중요도

Static priority (정적 우선순위)

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

- 장점: 구현이 쉽고, overhead가 적음

- 단점: 시스템 환경 변화에 대한 대응이 어려움

Dynamic priority (동적 우선순위)

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

- 단점: 구현이 복잡, priority 재계산 overhead가 큼

- 장점: 시스템 환경 변화에 대한 유연한 대응 가능

 

예시)

Windows 작업 관리자

프로세스 탭 → 마우스우클릭→ 우선순위 설정

 

요약: Scheduling Concepts

멀티프로그래밍 (멀티테스킹)

스케줄링 개념

- 목적

- 성능 지표 (index)

  * CPU burst vs I/O burst

- 스케줄링 기준(Criteria)

스케줄링 레벨

- Long-term, Mid-term, Short-term

스케줄링 정책

- Preemptive/ non-preemptive

- Priority

 

개요

스케줄링의 목적

스케줄링 기준 및 단계

스케줄링 정책

기본 스케줄링 알고리즘들

Case study

 

Basic Scheduling algorithms

FCFS (First-Come-First-Service)

RR (Round-Robin)

SPN (Shortest-Process-Next)

SRTN (Shortest Remaining Time Next)

HRRN (High-Response-Ratio-Next)

MLQ (Multi-level Queue)

MFQ (Multi-level Feedback Queue)

 

FCFS (First-Come-First-Service)

선착순 알고리즘

Non-preemptive scheduling

스케줄링 기준(Criteria)

- 도착시간(ready queue 기준)

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

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

- High resource utilization / why? scheduling overhead ↓ 따라서 CPU가 계속 일할 수 있다

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

단점

- Convoy effect

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

- 긴 평균 응답시간(response time)

 

P4 P3 P2 P1 → Processor(CPU) → Computation of CPU burst time

 

P1(0) P2(1) P3(3) P4(5) P5(6)

P1(0-3) P2(3-10) P3(10-12) P4(12-17)P5(17-20)

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT)	Normalized(정규화) TT (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	2	9	9/7 = 1.3
P3	3	2	7	9	9/2 = 4.5
P4	5	5	7	12	12/5 = 2.4
P5	6	3	11	14	14/3 = 4.7

 

RR (Round-Robin)

Preemptive scheduling

스케줄링 기준 (Criteria)

- 도착 시간 (ready queue 기준)

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

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

- System parameter (δ)

- 프로세스는 할당된 시간이 지나면 자원 반납

  * Timer-runout

- 특정 프로세스의 자원 독점(monopoly) 방지

- Context switch overhead가 큼

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

 

RR (Round-Robin)

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

- Very large (infinite) δ → FCFS

- Very small time quantum → processor sharing

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

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

   * High context switch overhead

 

P4 P3 P2 P1 → Processor(CPU) → Computation of CPU burst time

 

        ↑                       Time -runout                      ↓

 

RR (Round-Robin), δ = 2

P1(0) P2(1) P3(3) P1(5) P4(5) P5(6) P3(7) P5(18) P2(19) P4(20)

P1(0-2) P2(2-4) P1(4-5) P3(5-7) P2(7-9) P4(9-11) P5(11-13) P2(13-15) P4(15-17) P5(17-18) P2(18-19) P4(19-20)

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT) = Response time	Normalized(정규화) TT (NTT) = TT/BT
P1	0	3 (1)	2	5	5/3 = 1.7
P2	1	7 (5, 3, 1)	11	18	18/7 = 2.6
P3	3	2 (0)	2	4	4/2 = 2
P4	5	5 (3)	10	15	15/5 = 3
P5	6	3 (1)	9	12	12/3 = 4

 

Average response time(TT) = (5 + 18 + 4 + 15 + 12) / 5 = 10.8

 

RR (Round-Robin), δ = 3

P1(0) P2(1) P(3) P3(3) P4(5) P5(6) P3(8) P5(14) P4(19)

P1(0-3) P2(3-6) P3(6-8) P4(8-11) P5(11-14) P2(14-17) P4(17-19)

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT) = Response time	Normalized(정규화) TT (NTT) = TT/BT
P1	0	3 (0)	0	3	3/3 = 1
P2	1	7 (4, 1)	12	19	19/7 = 2.7
P3	3	2 (0)	3	5	5/2 = 2.5
P4	5	5 (2)	9	14	14/5 = 2.8
P5	6	3 (0)	5	8	8/3 = 2.7

 

Average response time(TT) = (3 + 19 + 5 + 14 + 8) / 5 = 9.8

 

RR (Round-Robin), δ = 4

 

Basic Scheduling algorithms

FCFS (First-Come-First-Service)

RR (Round-Robin)

SPN (Shortest-Process-Next)

SRTN (Shortest Remaining Time Next)

HRRN (High-Response-Ratio-Next)

MLQ (Multi-level Queue)

MFQ (Multi-level Feedback Queue)

 

SPN (Shortest-Process-Next)

Non-preemptive scheduling

스케줄링 기준 (Criteria)

- 실행시간(burst time 기준)

- Burst time 가장 작은 프로세스를 먼저 처리

   * SJF(Shortest Job First) scheduling

마트 소량상품 전용계산대

 

장점

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

- 시스템 내 프로세스 수 최소화

   * 스케줄링 부하 감소, 메모리 절약 → 시스템 효율 향상 ↑

- 많은 프로세스들에게 빠른 응답 제공

 

단점

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

   * BT가 긴 프로세스는 자원을 할당 받지 못할 수 있음

      Aging 등으로 해결 (e.g., HRRN)

- 많은 프로세스들에게 빠른 응답 제공

   * 실행시간 예측 기법이 필요

 

SPN (Shortest-Process-Next)

P1(0) P2(1) P1(3) P3(3) P4(5) P5(6) P4(10) P5(13) P2(20)

P1(0-3) P2(3-6) P3(6-8) P4(8-11) P5(11-14) P2(14-17) P4(17-19)

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT)	Normalized TT (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	12	19	19/7 = 2.7
P3	3	2	0	2	1
P4	5	5	0	5	1
P5	6	3	4	7	7/3 = 2.3

 

SRTN (Shortest Remaining Time Next)

                               남은시간

SPN의 변형

Preemptive scheduling

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

장점

- SPN의 장점 극대화

단점

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

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

- Context switching overhead

→ 구현 및 사용이 비현실적

 

P1(0) P2(1) P3(3) P4(5) P5(6)

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT)	Normalized TT (NTT) = TT/BT
P1	0	3
P2	1	7
P3	3	2
P4	5	5
P5	6	3

 

HRRN (High-Response-Ratio-Next)

SPN의 문제점: 기아현상

SPN의 변형

- SPN + Aging concepts, Non-preemptive scheduling

Aging concepts   Age 나이↑ → 배려

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

스케줄링 기준 (Criteria)

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

Response ratio = (WT + BT) / BT (응답률)

- SPN의 장점 + Starvation 방지   BT 대비 얼마나 WT(기다렸는가)

- 실행 시간 예측 기법 필요 (overhead)   BT를 예측해야함.

 

HRRN (High-Response-Ratio-Next)

                 P3: (2+7) / 2 = 4.5

                 P4: (5+5) / 2 = 2

                 P5: (3 +4) / 3 = 2.3

P1(0) P2(1) P3(3) P4(5) P5(6)

P1(0-3) P2(3-10) P3(10-12) P5(12-15) P4(15-20) 

P2: (7 + 2) / 7 = 1.29                  P4: (5+7)/ 5 = 2.4

P3: 2/2 = 1                                   P5: (3+6) / 3 = 3

Processor ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT - BT	Turnaround time (TT)	Normalized TT (NTT) = TT/BT
P1	0	3	0	3	1
P2	1	7	2	19	19/7 = 2.7
P3	3	2	0	2	1
P4	5	5	0	5	1
P5	6	3	4	7	7/3 = 2.3

 

Basic Scheduling algorithms

Fairness(공평성)

- FCFS(First-come-First-Service)

- RR(Round-Robin)

↕

Efficiency/Performance(효율성, 성능)

문제점: 실행시간(BT) 예측 부하 (힘들다, 정확하지 않다)

- SPN(Shortest-Process-Next)

- SRTN(Shortest Remaining Time Next)

- HRRN (High-Response-Ratio-Next)

↓

해결책

- MLQ(Multi-level Queue)

- MFQ(Multi-level Feedback Queue)

 

MLQ(Multi-level Queue)

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

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

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

Queue 사이에는 우선순위 기반의 스케줄링 사용

- E.g., fixed-priority preemptive scheduling

장점

- 빠른 응답시간 (?) 우선순위 높은 큐는 응답시간이 빠르고 아닌 큐는 응답시간이 느리다.

단점

- 여러 개의 Queue 관리 등 스케줄링 overhead

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

 

최고 우선순위

→ 시스템 프로세스

→ 대화식 프로세스

→ 대화식 편집 프로세스

→ 일괄 처리 프로세스

→ 학생 프로세스

최저 우선순위

 

MFQ(Multi-level Feedback Queue)

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

Feeback을 통한 우선순위 조정

- 현재까지의 프로세서 사용 정보(패턴) 활용

특성

- Dynamic priority

- Preemptive scheduling

- Favor short burst-time processes

- Favor I/O bounded processes

- Improve adaptability

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

BT를 예상하지 않고도 비슷한 효과를 낸다.

 

                                             우선순위 높음

                          FCFS(규정 시간량 = 무한)

선택기                                                  큐3

(우선순위비교)    규정 시간량 = 16밀리초

                                                           큐2        Computed-bounded

                          규정 시간량 = 4밀리초

                                                           큐1

                          규정 시간량 = 2밀리초

                                                           큐0

                                           우선순위 낮음

Aging

I/O-bounded

 

단점

설계 및 구현이 복잡, 스케줄링 overhead가 큼

Starvation 문제 등

 

변형

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

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

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

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

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

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

- 에이징 (aging) 기법

 

Parameters for MFQ scheduling

- Queue의 수

- Queue별 스케줄링 알고리즘

- 우선 순위 조정 기준

- 최초 Queue 배정 방법

 

요약: Basic Scheduling algorithms

FCFS (First-Come-First-Service)

RR (Round-Robin)

SPN (Shortest-Process-Next)

SRTN (Shortest Remaining Time Next)

HRRN (High-Response-Ratio-Next)

MLQ (Multi-level Queue)

MFQ (Multi-level Feedback Queue)