운영체제 OS - 프로세스 스케줄링 (Process Scheduling)

프로세스 스케줄링

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

여러개의 프로세스가 시스템 내 존재
자원을 할당 할 프로세스를 선택 해야 함 - Scheduling
자원 관리
- 시간 분할 관리
하나의 자원을 여러 스레드들이 번갈아 가며 사용 (프로세스 스케줄링)
- 공간 분할 관리
하나의 자원을 분할하여 동시에 사용 (메모리)

스케줄링의 목적

시스템의 성능 향상

대표적 시스템 성능 지표
- 응답시간
- 작업처리량
- 자원 활용도 --> 주어진 시간(Tc)동안 자원이 활용된 시간 (Tr) = Utilization

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

스케줄링 기준 및 단계

스케줄링 기법이 고려한느 항목들, 프로세스의 특성, 시스템 특성,
프로세스의 긴급성, 프로세스 우선순위, 프로세스 총 실행 시간

- CPU burst vs I/O burst
프로세스 수행 = CPU사용 (Compute-bounded) + I/O대기(I/O-bounded)
Burst time은 스케줄링의 중요한 기준 중 하나

스케줄링의 단계
Long-term scheduling - Job Scheduling
다중 프로그래밍 정도 조절 : 시스템 내에 프로세스 수 조절
I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택
시분할 시스템에서는 모든 작업을 시스템에 등록 덜 중요하다.

Mid-term scheduling - Memory allocation
메모리 할당 결정 (Swapping)

Short-term scheduling - Process scheduling
프로세서를 할당할 프로세스를 결정
가장 빈번하게 발생 매우 빨라야 한다.

스케줄링 정책 (Policy)

선점 vs 비선점 
비선점(Non-Preemptive scheduling)
할당 받을 자원을 스스로 반남할 때까지 사용
Context switch overhead가 적음 / 잦은 우선순위 역전, 평균 응답 시간 증가

선점(Preemptive scheduling)
타의에 의해 자원을 빼앗길 수 있음
할당 시간 종료, 우선순위가 높은 프로세스 등장
Context switch overhead가 큼 / Time-sharing system, real-time system에 적합

우선순위 -> 작업관리자에서 우선 순위를 실제로 사용한다.
프로세스의 중요도
Static priority
프로세스 생성시 결정된 priority가 유지 됨

Dynamic priority
프로세스의 상태 변화에 따라 priority변경
재계산 overhead가 큼, 시스템 환경 변화에 유연한 대응 가능

기본 스케줄링 알고리즘

FCFS (Frist-Come-First-Service)
Non-Preemptive scheduling, 스케줄링 기준 도착시간, Batch system에 적합, 긴 평균 응답시간
Scheduling Overhead가 낮음

RR (Round-Robin)
Preemptive scheduling, 스케줄링 기준 도착시간, 자원 사용 제한 시간이 있음, 대화형 시분할 시스템에 적합
특정 프로세스의 자원 독점 방지, Context switch overhead가 큼, Time quantum이 시스템 성능을 결정
Time quantum (infinite) -> FCFS
Time quantum (very samll) -> processor sharing

SPN (Shortest-Process-Next)
Non-preemptive scheduling, 스케줄링 기준 실행시간 Burst time 가장 짧은 순
장점 : 평균 대기시간 최소화, 시스템 내 프로세스 수 최소화, 많은 프로세스들에게 빠른 응답 시간 제공
단점 : Starvation (무한대기) 현상 발생==>Aging등으로 해결, 정확한 실행시간을 알 수 없음

SRTN (Shortest Remaining Time Next)
Preemptive scheduling 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
장점 SPN의 장점 극대화
단점 프로세스 생성시, 총 실행 시간 예측이 필요(BT), Context switching overhead

HRRN (High-Response-Ratio-Next)
SPN+Aging concepts
Aging concepts
프로세스의 대기 시간을 고려하여 기회를 제공
스케줄링 기준 Response ratio가 높은 프로세스 우선
Response ratio = (WT+BT)/BT 응답률

MLQ (Multi-level Queue)
작업 (or 우선순위)별 별도의 ready queue를 가짐
최초 배정 된 queue를 벗어나지 못함
각각의 queue는 자신만의 스케줄링 기법 사용
Queue사이에는 우선순위 기반의 스케줄링 사용 / fixed-priority, preemptive scheduling
여러 개의 queue를 관리 overhead, 우선순위가 낮은 queue는 starvation현상 발생 가능

MFQ (Multi-level Feedback Queue)
프로세스의 queue간 이동이 허용된 MLQ
Dynamic priority, Preemptive scheduling, Favor short burst-time processes
Favor I/O vounded processes, Improve adaptability
프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN기법의 효과를 볼 수 있음

단점 overhead, starvation
변형
각 준비 큐마다 시간 할당량을 다르게 배정
입출력 위주 프로세스를 우선순위로 배치
대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동 (에이징)