OS-6) 프로세스 스케줄링

topics	700-컴퓨터과학 704 운영체제
types	이론 학습
tags	#scheduling #FCFS #SJF #RR #real-time

프로세스 스케줄링

CPU에서 실행할 프로세스를 선택하는 것이다. 프로세스 실행은 CPU-I/O burst cycle(CPU 다음에 I/O)로 이뤄진다.

스케줄링 목표

CPU 사용을 최대화
- CPU Utilization = ∑ (Process time / period)
처리량 최대화
총처리 시간을 최소화
대기 시간을 최소화
응답 시간을 최소화

스케줄링 큐

큐	설명
Job Queue	모든 프로세스가 올라가 있는 큐 (Long term)
Ready Queue	준비 상태에 있는 프로세스들이 올라가 있음 (Short term)
Device Queue	입출력 장치마다 있는 큐

큐잉 다이어그램

큐, 자원(원 모양), 프로세스의 이동 흐름을 나타낸다.

순서: create → job queue → ready queue

프로세스가 create 되고 나면 바로 job queue에 적재된다. 이 적재된 것 중에 ready queue로 가는 것을 선택한다.

스케줄러

단기 스케줄러 (= CPU 스케줄러)

다음에 CPU에 할당될 프로세스를 선택한다
즉 준비 큐에 있는 프로세스를 선택한다
ms 간격으로 호출 → 빨라야 함

CPU 스케줄링 결정 시점

상태 전이	방식
running → wait	비선점 방식
running → ready	선점 방식
wait → ready	선점 방식
종료될 때	비선점 방식

선점 방식인 이유

공유 데이터 접근 고려
커널 모드에 있는 동안의 선점 고려
OS 작업 중에 인터럽트 발생 고려

Dispatcher

단기 스케줄러가 선택한 프로세스에게 CPU 제어를 주는 모듈이다.

하는 작업

문맥 교환
사용자 모드로 전환
프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동

디스패처 지연: 디스패처가 하나의 프로세스를 중단시키고 다른 프로세스를 실행시키는 데 소요되는 시간

장기 스케줄러 (= Job 스케줄러)

준비 큐로 이동할 프로세스를 선택한다
s, min 간격으로 호출
이 스케줄러가 다중 프로그래밍 정도를 결정
I/O bound와 CPU bound 프로세스가 고루 섞이도록 한다

중기 스케줄러

많은 프로세스가 있을 때(= 다중 프로그래밍 중일 때), 너무 많은 프로세스에게 메모리를 할당해 시스템 성능이 저하되는 것을 방지하기 위함
Swapping 이용
- 물리 메모리 공간이 부족해지면, 물리 메모리의 확장 개념으로 swap area를 사용하고 swap out 시켜 내보냄
- 메모리 ↔ 디스크

스케줄링 알고리즘

FCFS (First Come, First Served)

그냥 Queue 방식
딱 시작하는 타이밍이 waiting 시간
호위 효과(Convoy Effect) 가 발생할 수 있음
- 모든 프로세스가 긴 프로세스 하나가 CPU를 양도하기를 기다리는 것

Priority 스케줄링

우선순위가 높은 것을 먼저 할당한다.

SJF (Shortest Job First)

버스트 길이를 기준으로 가장 짧은 시간을 가진 프로세스를 스케줄
언제나 최소의 평균 대기 시간을 보장
단기 스케줄러에서 구현 못함
BUT, CPU 버스트 시간을 알기 어렵다

대략 예측 방법

t(n): n번째 프로세스 실제 CPU 사용 시간
τ(n+1): (n+1)번째 프로세스 CPU 사용 시간 추정치

SRTF (Shortest Remaining Time First)

선점 방식
진행하다가 그 시간에 burst time이 더 짧은 프로세스가 오면 선점함
==대기시간 = 마지막 조각 프로세스가 실행한 시간 - 프로세스 도착시간 - 이전에 다른 조각 프로세스가 실행한 시간==
==평균대기시간 = 대기시간 / 프로세스 개수==

문제와 해결책

문제	해결책
Starvation	낮은 우선순위 프로세스는 실행되지 않을 수 있다
Aging	시간이 흘러갈수록 프로세스의 우선순위를 증가시킨다

RR (Round Robin)

선점형
프로세스는 적은 양의 CPU 시간을 할당받음 (time quantum)
- 시간이 경과할 때마다 인터럽트
준비 큐에 n개, 시간 할당량 q이면, 각 프로세스는 q(n-1) 이상을 대기하지 않음
- q가 커질수록 FIFO에 가까워짐
- q가 작아지면 오버헤드가 커짐 → 문맥 교환 시간에 비해서는 충분히 커야 함

Multilevel Queue

Ready Queue를 여러 개로 분할한다. 프로세스는 지정된 큐에 영원히 존재한다 (이동 불가). 큐 사이의 스케줄링도 정해야 한다.

대표적인 분할 큐

큐	설명
Foreground Queue	user와의 상호작용을 많이 하는 프로세스 존재. 보통 CPU 시간의 80%를 받아 RR 방식으로 스케줄링
Background Queue	user와 멀리 떨어진 batch system 형태의 프로세스 존재. 보통 CPU 시간의 20%를 받아 FCFS 방식으로 스케줄링

foreground queue 처리 후 background queue 고려 → starvation 야기 → CPU 시분할을 통해 방지

Multilevel Feedback Queue

각 프로세스가 여러 큐로 이동할 수 있다. Aging 기법을 다음과 같은 방식으로 구현할 수 있다. 응답 속도가 빨라진다.

먼저 quantum 8 (RR 방식)의 큐에 넣는다
위의 큐에서 처리 안 되면, 하위 큐에 넣음
최종적으로도 처리 안 될 시 FCFS에 들어가서 처리됨

다중 처리기 스케줄링

Multiple Processor Scheduling (SMP)

예: NUMA

CPU가 여러 개
다중 처리기 접근
- 비대칭 다중처리: 오직 하나의 처리기만이 시스템 자료구조에 접근 가능
- 대칭 다중처리: 각 처리기는 독자적으로 스케줄링, 모든 프로세스는 각각이나 공통의 준비 큐에 있을 수 있다
처리 친화성: 프로세스는 현재 자신이 실행 중인 처리기를 더 선호한다
효율적으로 작동하려면 로드 밸런싱이 있어야 한다
- Push Migration: 각 처리기의 부하를 점검하고 일을 분배
- Pull Migration: 노는 처리기가 바쁜 처리기에서 대기 중인 일을 가져와 실행

Multicore Processors

한 물리적 칩 안에 여러 개의 처리기 코어를 배치
빠르며 더 적은 전력을 소모
코어마다 여러 스레드 지원이 증가하는 추세
메모리 멈춤 상황이 발생할 수 있음 (여러 프로세스가 메모리에 접근)

Real-Time CPU 스케줄링

==Real-Time System은 "Deadline"이 존재하고 해당 Deadline을 지키지 않는다면 시스템에 치명적인 영향을 줄 수 있다. 그래서 반드시 "Deadline" 내에 job을 끝내야 한다.==

선점형, 우선순위 기반(priority-based) 스케줄링을 지원해야 함
마감시간을 충족해야 한다

Deadline

종류	설명
Soft Real Time	중요한 실시간 프로세스가 언제 스케줄될지 보장하지 않음
Hard Real Time	태스크는 마감시간 전까지 반드시 완료

RMS (Rate Monotonic Scheduling)

우선순위가 주기의 역수로 매겨짐
즉, 빠른(짧은) 주기 == 높은 우선순위
예: P1은 주기가 50초이고, 20초 동안 processing 한다. P2는 주기가 100초이고, 35초 동안 processing 한다.

EDF (Earliest Deadline First Scheduling)

우선순위가 마감시간에 따라 부여됨
이 방법은 RMS처럼 static하게 priority를 주는 것이 아니라, task들이 들어올 때마다 deadline을 비교해보고 priority를 정하는 방식이다
예: P1은 주기가 50이고, processing이 25이다. P2는 주기가 80이고, processing이 35이다. 주기가 deadline일 때

Proportional Share Scheduling

n/t 비율로 CPU 시간 할당

지연시간

Deadline을 지키려면 지연시간을 최소화해야 한다. 두 종류의 지연이 성능에 영향을 준다.

지연 종류	설명
인터럽트 지연	인터럽트가 도착해서 인터럽트를 서비스하기 시작할 때까지의 시간
디스패치 지연	프로세스를 중단시키고 새로운 프로세스로 전환하는 데 걸리는 시간 (문맥 전환)

충돌이 될 수 있는 단계

커널 모드에서 실행 중인 프로세스 선점
낮은 우선순위의 프로세스가 높은 우선순위의 프로세스가 요구하는 자원을 방출

알고리즘 평가

결정론적 모델링

특정 예측된 부하를 미리 정해 놓고 그 부하에 대한 각 알고리즘의 성능을 측정한다.

분석적 평가의 한 부류
간단하고 빠르지만 특수한 입력에 대해서만 해당될 수 있음

Queueing Model

프로세스 도착과 CPU, I/O 버스트를 확률적 분포로 설명
- 평균 처리량, 이용률, 대기시간 등을 계산
각 서버는 대기 프로세스를 넣을 큐를 가진다
Little's Law
- n = λ × W
- n: 평균 큐의 길이 (몇 개의 프로세스가 존재 가능하냐)
- λ: 큐에 평균적으로 도착하는 평균 개수
- W: 큐에서 평균적으로 기다리는 시간

Simulation

컴퓨터 시스템의 프로그램 모델이다.

클럭은 가변적
알고리즘 성능을 나타내는 통계 자료를 수집
데이터 수집 방법
- 확률에 기초한 랜덤 넘버 발생
- 수학적 or 경험적으로 정의된 분포
- 실제 시스템의 이벤트를 차례대로 기록한 추적 테이프
위에 것들보단 정확하지만 한계는 있다