10.1 워크로드에 대한 가정
워크로드의 정의
- 워크로드(workload): 시스템에서 실행 중인 프로세스나 작업(job)의 집합.
- 정책을 설계하고 평가하기 위해 워크로드에 대한 가정을 설정함.
가정 목록
- 모든 작업은 같은 시간 동안 실행된다.
- 모든 작업이 동시에 도착한다.
- 각 작업은 시작되면 완료될 때까지 중단되지 않는다.
- 모든 작업은 CPU만 사용하며, 입출력을 수행하지 않는다.
- 각 작업의 실행 시간이 사전에 알려져 있다.
비현실적인 가정
- 이 가정들은 논의를 단순화하기 위한 것이며, 실제 상황과는 다름.
- 특히, 작업 실행 시간이 미리 알려져 있다는 가정은 현실적이지 않음:
- 스케줄러가 모든 정보를 알고 있어야 하는데, 이는 이상적인 가정에 가까움.
10.2 스케줄링 평가 항목
1. 반환 시간 (Turnaround Time)
- 정의:
- 작업 반환 시간은 작업이 완료된 시각(Tcompletion)에서 작업이 시스템에 도착한 시각(Tarrival)을 뺀 값.
- 수식:
2. 공정성 (Fairness)
- 정의:
- 시스템이 모든 작업을 얼마나 공정하게 처리했는지를 평가.
- Jain’s Fairness Index와 같은 지표로 측정 가능.
- 성능과 공정성의 상충:
- 성능을 극대화하려면 일부 작업의 실행이 지연될 수 있음 → 공정성 저하.
- 스케줄링에서 성능과 공정성 간의 균형이 중요.
10.3 선입선출 (First In First Out, FIFO) 스케줄링
FIFO 스케줄링의 정의
- FIFO(First In First Out)는 가장 먼저 도착한 작업을 가장 먼저 처리하는 방식.
- 장점:
- 단순하고 구현하기 쉬움.
- 동작 방식이 직관적이고 예측 가능.
- 가정:
- 모든 작업이 동시에 도착(Tarrival = 0)하고, 실행 시간을 미리 알 수 있다고 가정.
예제 1: 모든 작업의 실행 시간이 동일한 경우
- 워크로드:
- 작업 A, B, C가 순서대로 도착 (Tarrival = 0).
- 각 작업의 실행 시간 = 10초.
- 결과:
예제 2: 실행 시간이 서로 다른 경우
- 워크로드:
- 작업 A(100초), B(10초), C(10초)가 순서대로 도착 (Tarrival = 0).
- 결과:
문제점: 컨보이 효과 (Convoy Effect)
- 정의:
- 실행 시간이 긴 작업이 앞에 있을 경우, 짧은 작업들이 긴 대기 시간 동안 자원을 사용하지 못하는 현상.
- 결과:
- 전체 시스템 성능 저하.
- 작업 완료까지의 시간이 불필요하게 증가.
FIFO의 한계와 대안
한계
- 실행 시간이 긴 작업이 앞에 위치하면 반환 시간이 비효율적으로 증가.
- 짧은 작업의 대기 시간이 길어짐 → 공정성 저하.
10.4 최단 작업 우선 (Shortest Job First, SJF)
SJF의 정의
- Shortest Job First (SJF):
- 실행 시간이 가장 짧은 작업을 먼저 실행.
- 평균 반환 시간 기준으로 최적의 성능을 제공.
SJF 예제
-
워크로드 (작업 A, B, C의 실행 시간):
- A = 100초, B = 10초, C = 10초.
- 모든 작업이 동시에 도착(Tarrival = 0).
-
SJF 스케줄링:
- 결과:
- SJF는 FIFO의 평균 반환 시간(110초)보다 성능이 2배 이상 향상됨.
SJF의 최적성
- 모든 작업이 동시에 도착하는 경우:
- SJF는 평균 반환 시간 기준으로 최적의 스케줄링 알고리즘임이 증명 가능.
- 단, 현실적인 제약 조건이 존재:
- 실행 시간이 미리 알려져야 함.
가정 완화: 작업이 임의 시간에 도착
- 워크로드:
-
SJF 스케줄링:
- A가 먼저 실행되기 시작 → B와 C는 A가 끝날 때까지 기다림.
- 작업 실행 순서: A → B → C.
-
결과:
- A의 긴 실행 시간으로 인해 B와 C가 불필요하게 대기 → 컨보이 효과 발생.
문제점: 동적 작업 도착 시 컨보이 효과
- 문제 정의:
- SJF는 긴 작업이 먼저 실행되기 시작하면 이후 도착한 짧은 작업들이 대기해야 하는 상황 발생.
- 원인:
- SJF는 새로운 작업이 도착할 때마다 즉시 재평가하지 않음.
해결책
-
동적 SJF (Preemptive SJF):
- 새로운 작업이 도착하면 현재 실행 중인 작업을 중단(preempt)하고 재평가.
- 현재 실행 중인 작업보다 실행 시간이 짧은 작업이 있다면 우선 처리.
-
결과:
- 동적 SJF는 도착 시간에 관계없이 평균 반환 시간을 최소화.
- 컨보이 효과 완화 가능.
10.5 최소 잔여시간 우선 (Shortest Time-to-Completion First, STCF)
STCF의 정의
- STCF는 SJF(Shortest Job First)에 선점 기능을 추가한 스케줄링 알고리즘.
- 작동 원리:
- 시스템에 새로운 작업이 도착하면, 현재 실행 중인 작업과 새 작업의 잔여 실행 시간을 비교.
- 잔여 시간이 더 짧은 작업을 선택하여 실행.
- 기존 작업은 선점되었다가 나중에 다시 실행.
10.6 응답 시간
응답 시간의 정의
- 응답 시간 (Response Time):
- 작업이 도착한 시점(T_arrival)부터 처음 실행된 시점(T_firstrun)까지의 시간.
- 수식:
문제점
- STCF는 반환 시간을 최소화하지만, 응답 시간이 길어질 수 있음.
- 상호작용이 필요한 작업(예: 터미널 입력)에서는 응답 지연이 발생하여 사용자 경험이 저하됨.
10.7 라운드 로빈 (Round Robin, RR)
라운드 로빈의 정의
- RR은 작업을 짧은 시간 단위(타임 슬라이스)로 번갈아 실행.
- 한 작업이 타임 슬라이스 동안 실행된 후 다음 작업으로 전환.
- 타임 슬라이스는 타이머 인터럽트 주기의 배수로 설정.
요약
- 스케줄링 목표:
- 반환 시간 최소화: STCF, SJF.
- 응답 시간 최소화: RR.
- 절충:
- 반환 시간과 응답 시간은 상충 관계에 있음.
- 시스템의 목적에 따라 적절한 스케줄링 정책을 선택해야 함.
- 다음 주제:
- 미래를 예측하지 못하는 스케줄링 문제 해결을 위한 멀티 레벨 피드백 큐.
