5)프로세스 스케쥴링

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

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

- 자원을 할당 할 프로세스를 선택해야 한다.

> 스케쥴링(Scheduling)

- 자원 관리

> 시간 분할 (time sharing) 관리

 > 하나의 자원을 여러 스레드들이 번갈아 가면서 사용한다.

 > 예) 프로세서(Processor)

 > 프로세스 스케쥴링(Process scheduling)(프로세서 사용 시간을 프로세스들에게 분배)

> 공간 분할 (space sharing) 관리

 > 하나의 자원을 분할하여 동시에 사용한다.

 > 예) 메모리(memory)

 

2)스케줄링(Scheduling)의 목적

- 시스템의 성능 (performance) 향상

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

> 응답시간(response)

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

 > Interactive system, real-time system에서 중요하다.

> 작업 처리량(throughput)

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

 > batch system에서 중요하다.

> 자원 활용도(resource utilization)

 > 주어진 시간 동안 자원이 활용된 시간

 

시스템의 성능 지표들

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

> 사용자 지향적

> 예) Interactive systems

- 처리량 (throughput)

> 시스템 지향적

> 예) batch systems

- 자원 활용도 (resource utilization)

- 공평성(fairness)

> 예) FIFO

- 실행 대기 방지

> 무기한 대기 방지

- 예측 가능성(predictability)

> 적절한 시간 안에 응답을 보장하는가

 

3)스케줄링 기준 (Criteria)

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

- 프로세스(process)의 특성

> I/O bounded or compute-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

> CPU 사용 시간

> compute-bounded

- I/O burst

> I/O 대기 시간

> I/O bounded

- burst time은 스케쥴링의 중요한 기준 중 하나이다.

 

4)스케줄링의 단계 (Level)

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

- Long-term scheduling

> 장기 스케줄링

> Job scheduling

- Mid-term scheduling

> 중기 스케줄링

> Memory allocation

- Short-term scheduling

> 단기 스케줄링

> Process scheduling

 

Long-term Scheduling

- Job scheduling

> 시스템에 제출 할 (kernel에 등록 할) 작업(Job) 결정

 > Admission scheduling, High-level scheduling

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

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

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

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

> Time sharing system에서는 시간을 나누어서 사용하기 때문에 Long-term scheduling이 상대적으로 덜 중요하다

 

Mid-term Scheduling

- 메모리 할당 결정 (memory allocation)

> Intermediate-level scheduling

> Swapping(swap-in/swap-out)

 

Short-term Scheduling

- Process scheduling

> Low-level scheduling

> 프로세서(processor)를 할당할 프로세스(process)를 결정한다.

 > Processor scheduler, dispatcher

 

- 가장 빈번하게 발생

> Interrupt, block(I/O), time-out 등

- 매우 빨라야 한다.

 

5)스케줄링 정책 (Policy)

- 선점 vs 비선점

> Preemptive scheduling, Non-preemptive scheduling

- 우선 순위

> Prioirity

 

Preemptive/Non-preemptive scheduling

- Non-preemptive scheduling (비선점 -> 뺏을 수 없다)

> 할당 받을 자원을 스스로 반납할 때까지 사용한다.

> ex) system call, I/O 등

> 장점

 > Context switch overhead가 적다.

> 단점

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

 

- Preemptive scheduling

> 타의에 의해 자원을 빼앗길 수 있다.

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

> Context switch overhead가 크다.

> Time-sharing system, real-time system 등에 적합하다.

 

Priority

- 프로세스의 중요도

- Static priority (정적 우선순위)

> 프로세스 생성시 결정된 prioirty가 유지 된다.

> 구현이 쉽고, overhead가 적다.

> 시스템 환경 변화에 대한 대응이 어렵다.

- Dynamic prioirty (동적 우선순위)

> 프로세스의 상태 변화에 따라 priority가 변경된다.

> 구현이 복잡, prioirty 재계산 overhead가 크다.

> 시스템 환경 변화에 유연한 대응이 가능하다.

 

6)기본 스케줄링 알고리즘

- 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 기준)

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

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

> scheduling overhead가 낮고 cpu가 계속 일할 수 있다.

> High rsource utilization

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

- 단점

> Convoy effect

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

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

 

RR (Round-Robin)

 

- Preemptive scheduling

- 스케줄링 기준 (Criteria)

> 도착 시간 (ready queue 기준)

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

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

> System parameter

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

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

> Context switch overhead가 크다.

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

- Time quantum이 시스템 성능을 결정하는 핵심 요소이다.

> 사용 제한 시간이 무제한에 가깝게 길다면 FCFS와 가깝다.

> 매우 작은 사용 제한시간은 processor sharing이다.

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

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

 > High context switch overhead

 

SPN (Shortest-Process-Next)

- Non-preemptive scheduling

- 스케줄링 기준 (Criteria)

> 실행시간 (burst time 기준)

> burst time이 가장 작은 프로세스를 먼저 처리한다.

- 장점

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

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

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

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

- 단점

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

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

  > Aging 등으로 해결 (ex. HRRN)

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

 > 실행시간 예측 기법이 필요하다.

 

SRTN (Shortest Remaining Time Next)

- SPN의 변형

- Preemptive scheduling

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

- 장점

> SPN의 장점 극대화

- 단점

> 프로세스 생성시, 총 실행 시간 예측이 필요하다.

> 잔여 실행을 계속 추적해야 한다. 이에 대한 overhead가 발생한다.

> Context switching overhead가 발생한다.

> 구현 및 사용이 비현실적이다.

 

HRRN(High-Response-Ratio-Next)

- SPN의 변형

> SPN + Aging concepts, Non-preemptive scheduling

- Aging concepts

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

- 스케줄링 기준 (Criteria)

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

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

> SPN의 장점 + Starvation 방지

> 실행 시간 예측 기법이 필요하다. (overhead)

 

MLQ (Multi-level Queue)

 - 작업 (or 우선순위)별 별도의 ready queue를 가진다.

> 최초 배정된 queue를 벗어나지 못한다.

> 각각의 queue는 자신만의 스케줄링 기법을 사용한다.

- Queue 사이에는 우선순위 기반의 스케줄링을 사용한다.

> ex) fixed-priority preemptive scheduling

- 장점

> 빠른 응답시간

- 단점

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

> 우선순위가 낮은 queue는 starvation 현상이 발생 가능하다.

 

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기법의 효과를 볼 수 있다.

- 단점

> 설계 및 구현이 복잡, 스케줄링 overhead가 크다.

> Starvation 문제가 발생한다.

- 변형

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

 > 프로세스의 특성에 맞는 형태로 시스템 운영이 가능하다.

> 입출력 위주 프로세스들을 상위 단계의 큐로 이동, 우선 순위를 높인다.

 > 프로세스가 block될 때 상위의 준비 큐로 진입하게 한다.

 > 시스템 전체의 평균 응답 시간을 줄이고 입출력 작업을 분산 시킨다.

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

 > Aging 기법

 

요약