5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle) 제 5 장 중앙처리장치 스케쥴링 5.1 기본 개념 (Basic Concepts) 다중 프로그래밍의 목적: CPU 활용의 극대화 한 순간에 실행 상태인 프로세스는 하나 나머지는 dispatch될 때까지 대기→ CPU 스케쥴링 5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle) 프로세스는 대개 CPU 버스트와 I/O버스트를 반복 (CPU burst에서 시작하여 CPU burst에서 종료) 그림 5.1 버스트 분포를 CPU 스케쥴링에 활용

5.1.2 CPU 스케쥴러 (CPU Scheduler) 준비 큐는 PCB들의 FIFO 큐, 우선순위 큐, 트리... 5.1.3 선점 스케쥴링 (Preemptive Scheduling) CPU 스케쥴링(프로세스 선택)은 언제 가능?  (1) “실행” -> “대기” (예: I/O를 요청, 자식의 종료 대기) (2) “실행” -> “준비” (예: 인터럽트 발생) (3) “대기” -> “준비” (예: I/O 종료) (4) 수행 종료

비선점(nonpreemptive) 스케쥴링 1,4 완료 후 1과 4에 한하여 스케쥴링 (예: MS Window 3.1) no timer, 하드웨어와 거의 무관 선점(preemptive) 스케쥴링 문제: 공유 데이터 변경 중 선점 “일관성” 문제 발생 : 6장 공유 데이터가 커널 데이터인 경우 문제가 심각 대안 임계 구역(critical section)에서는 선점 불가 시스템 호출이나 I/O가 완료될 때까지 선점을 유보

5.1.4 디스패처 (Dispatcher) 디스패처: 선택된 프로세스에 CPU제어를 넘기는 모듈 가능한 한 빨라야 한다 문맥 교환, 사용자 모드로 전환, 이전 위치로 이동 디스패치 지연: “중단” 이후 (다른 프로세스의) “수행 시작” 에 걸리는 시간

5.2 스케쥴링 기준 (Scheduling Criteria) (1) CPU 이용률 (2) 처리율(throughput): 시간 단위 당 완료된 프로세스 수 (3) 반환(turnaround) 시간: 완료 시간  진입 시간 (4) 대기(waiting) 시간 : 준비 큐에 있었던 시간 (5) 응답(response) 시간(대화식 시스템) : 요청 후 최초 응답까지의 시간 스케쥴링의 목적 CPU 활용과 처리율의 극대화 반환, 대기, 응답 시간의 극소화 1~5를 평균적으로 최적화하거나 분산이 작아지게 대화식의 경우에는 분산의 최소화가 더욱 중요 본 교재에서는 “대기 시간” 중심으로 비교

5.3 스케쥴링 알고리즘 (Scheduling Algorithms) 5.3.1 선입 선처리 (First-Come First-Served) 스케쥴링 FIFO 큐로 구현 평균 대기 시간이 상당히 길어질 수 있다(not optimal) p. 142 Gant 차트 작업의 진입 순서에 따라 평균 대기 시간에 큰 차이 비선점 방식임  : 일단 CPU를 할당받으면 수행 종료나 I/O 시에만 CPU 양도 시분할 시스템에서는 사용 곤란

5.3.2 최소 작업 우선 (Shortest-Job-First) 스케쥴링 각 프로세스의 “다음 CPU 버스트 시간” 이 기준 시간이 같으면 FCFS 알고리즘 적용 평균 대기 시간이 가장 짧다(optimal) 평균 대기 시간 계산 예 (143 페이지 참조) SJF 알고리즘의 문제점 “다음 CPU 버스트 시간”의 예측이 어려움 단기 스케쥴링에 활용하기 어려움 일괄 처리 시스템의 장기 스케쥴링에 주로 활용

(대기시간) 선점 : ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5 프로세스 도착시간 버스트 시간 P1 0 8 P2 1 4 P3 2 9 P4 3 5 P1 P2 P4 P1 P3 0 1 5 10 17 26 (대기시간) 선점 : ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5  비선점 : ((8-1) + (12-3) + (17-2)) / 4 = 7.75

n+1 = tn + (1–)tn-1 +... + (1–)jtn-j +... + (1–)n+10 단기 스케쥴링에 활용하기 위해 “예측”을 시도 지수 평균(exponential average) 그림 5.3  SJF는 선점(최소 잔여 시간 우선)/비선점 방식 모두 가능 n+1 = tn + (1–) n  n+1 = tn + (1–)tn-1 +... + (1–)jtn-j +... + (1–)n+10

n+1 = tn + (1–)(tn-1 + (1- ) n-1) CPU버스트(ti): 6 4 6 4 13 13 13 … “추정”(i) :10 8 6 6 5 9 11 12 … n+1 = tn + (1–)(tn-1 + (1- ) n-1)

5.3.3 우선순위(Priority) 스케쥴링 각 프로세스에 우선순위 부여(SJF도 한 종류) 우선 순위가 같으면 FCFS 적용 우선 순위 내부적(수량으로 측정 가능) 시간 제한, 메모리 요구량, 개방 파일의 수, 평균 I/O버스트 : 평균 CPU버스트... 외부적(정책적으로 주어지는 것들) 프로세스의 중요도, 예치액... 무한 대기(indefinite blocking) / 기아(starvation)  우선 순위가 낮은 프로세스가 무한히 대기하는 현상 해결 → aging 기법(일정 시간마다 우선 순위를 높임)

5.3.4 라운드 로빈(Round-Robin) 스케쥴링 시분할 시스템에 적합, FCFS에 “선점”을 가미 일정한 시간(time quantum/slice)마다 준비 큐(순환 큐)의 다른 프로세스에 CPU 할당 평균 대기 시간은 비교적 긴 편 RR의 성능은 시간 할당량의 크기와 밀접한 연관 크면, FCFS 작으면, "처리기 공유(processor sharing)” 문맥 교환 횟수 증가 (그림 5.4) “시간 할당량 >> 문맥 교환 시간”이 바람직 P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30

[그림 5.6] 반환시간은 시간할당량에 따라 다양함을 예시

할당량 ① 1 2 3 4 1 2 4 1 2 4 1 4 1 4 1 4 4 ② 1 2 3 4 1 2 4 1 4 4 ③ 1 2 3 4 1 4 4 …… 2의 입장 3의 입장

*전체적 평균 효율(FCFS) vs. 형평성(RR)  시간 할당량이 크다고 반드시 평균 반환 시간이 감소하지는 않음 그림 5.5 그러나 할당량이 너무 작으면 문맥 교환 시간 증가 -> 반환 시간 증가 평균 반환 시간을 줄이려면, 많은(약80%) 버스트(프로세스)가 할당량 내에 종료 *전체적 평균 효율(FCFS) vs. 형평성(RR) 

5.3.5 다단계 큐 (Multilevel Queue) 스케쥴링 프로세스의 특성에 따라 (그룹별) 우선 순위 부여 (예) 후면 작업 vs. 전면 작업 준비 큐를 여러 개 (우선 순위에 따라) : 그림 5.6 기억장치 요구량, 우선 순위, 유형에 따라 하나의 큐에 “영구 할당” 각기 다른 스케쥴링 알고리즘 적용 가능 (예) 전면 작업은 RR, 후면 작업은 FCFS 서로 다른 큐간에는 “고정 우선 순위-선점” 알고리즘 적용 (상위 큐가 모두 비어야 하위 큐가 실행)

5.3.6 다단계 피드백 큐 (Multilevel Feedback Queue) 스케쥴링 가장 일반적, 가장 복잡 (큐의 개수, 큐별 알고리즘, 상하 이동 시기...) 상황에 따라 준비 큐를 바꿈 CPU 사용 시간을 기준으로 하는 예 I/O-bound, 대화식 프로세스는 상위 큐로 이동 하위 큐에 오래 있으면 상위 큐로 이동: 기아 방지(aging) 알고리즘 처음 오면 최상위 큐를 할당 상위 큐가 비어야만 하위 큐의 프로세스 실행 실행 중 상위 큐에 새 프로세스가 오면 CPU 양도 선점 스케쥴링 최하위 큐는 FCFS

5.5 실시간 (Real-Time) 스케쥴링 5.4 다중 프로세서 (Multiple-Processor) 스케쥴링 동종(homogeneous) 시스템 하나의 준비 큐로 부하 공유(load sharing) 각 프로세서에 별도의 스케쥴링 알고리즘 적용 가능 비대칭(asymmetric) 다중처리: 한 프로세서만 OS 수행, 구조 간단 이기종(heterogeneous) 시스템 (분산 환경) 별도의 대기 큐 (기계어가 다르므로): 스케쥴링 복잡 5.5 실시간 (Real-Time) 스케쥴링 경성(hard) 실시간 시스템 시간 내에 마칠 수 있으면 요구 접수, 아니면 거절 보조 기억 장치/가상 기억 장치 사용 곤란

연성(soft) 실시간 시스템 디스패치 지연(그림 5.8)의 최소화 방안 실시간 작업은 최상의 우선 순위 (우선 순위 스케쥴링) 다른 작업의 피해(starvation) 멀티미디어, 고속 대화형 그래픽 등에 적합 디스패치 지연(그림 5.8)의 최소화 방안 선점 지점(preemption point) 시스템 호출 중간중간에 실시간 프로세스 대기 여부 점검 커널 전체를 선점 가능하게 커널 데이터 구조의 “보호”가 필요 “우선 순위 역전” 가능 => 우선 순위 상속

5.6 알고리즘의 평가 (Algorithm Evaluation) OS 구현 시 스케쥴링 알고리즘의 선택 기준 5.6.1 결정성 모형화 (Deterministic Modeling) 미리 정해진 작업 부하에 대해 각 알고리즘 비교 평가는 간단하지만 비현실적 5.6.2 큐잉 모형 (Queueing Model) 큐잉 네트워크 분석(수학적으로) 서버: CPU(+대기 큐), I/O 시스템(+장치 큐) 도착률, 서비스율 -> 이용율, 평균 큐 길이, 평균 대기 시간

5.6.3 모의 실험 (Simulations) 5.6.4 구현 (Implementation) 리틀(Little)의 공식: n =   W (n: 평균 큐 길이, : 평균 도착율, W: 평균 대기시간) 한계: 복잡한 분포 계산, 분포가 비현실적(근사치) 5.6.3 모의 실험 (Simulations) 컴퓨터 모델을 프로그래밍으로 흉내(난수 발생기...) 추적 테이프(trace tape):실제 시스템을 모니터하여 작성 문제점: 비용, 프로그래밍 작업의 복잡도 5.6.4 구현 (Implementation) 알고리즘을 구현하여 OS에 넣고 돌려봄 정확한 평가 가능, 가장 많은 비용