6장 단일 프로세서 스케줄링

학습목표 스케줄링 단계를 이해한다. 장기 스케줄러와 단기 스케줄러의 역할을 알아본다. 여러 프로세스 스케줄링 알고리즘의 특성을 이해한다. 알고리즘의 성능 평가를 이해한다.

1. 스케줄링 개념 다중 프로그래밍 기본 개념 동시에 다수 개의 프로그램을 메인 메모리에 적재 입출력 요구시 프로세스 대기 동시에 다수 개의 프로그램을 메인 메모리에 적재 입출력 요구시 프로세스 대기 프로세스 대기시 다른 프로세스를 수행함으로써 프로세서(CPU) 유휴 시간 감소 프로세서 이용율의 증대

스케줄링 개념(2/15) 다중 프로그래밍(계속) 사례 : A, B 두 프로세스가 있을 때 각 작업을 1초 동안 실행하고 1초 동안 기다리는 것을 반복할 때 이 시스템의 효율은?

스케줄링 개념(3/15) 다중 프로그래밍(계속) 사례 1 : 일괄처리 시스템에서는? 프로세스 A를 모두 처리한 후 B를 처리하는 경우 : 전체 4분 소요 프로세스 A는 실행하는데 2분, 프로세스 B에서 2분 소요 실제 계산시간 2분, 쉬는 시간 2분이므로 프로세서 이용률은 50%

스케줄링 개념(4/15) 다중 프로그래밍(계속) 사례 2 : 다중 프로그래밍 경우 A를 실행하고 1초 후 A가 기다릴 때 B를 실행 프로세스 A 유휴; 입력 시작 프로세스 B 종료 [그림 6-3] 다중 프로그래밍을 하는 작업의 수행시간 두 프로세스에 대한 실행시간 : 2분, 프로세서는 쉬지 않게 됨(효율증가) - 프로세서 사용률은 50%에서 100%로 향상 - A는 시간상의 절약이 없지만 B는 처리시간이 반으로 줄어들게 됨

스케줄링 개념(5/15) 프로세스 실행 기본요소 프로세서 실행과 입출력 대기의 순환으로 구성 프로세서 버스트 입출력 버스트 프로세스 들은 프로세서 실행과 입출력 대기 두 상태 사이에서 교대로 진행되며 프로세서 버스트로 시작되고 끝남  [그림 6-4] 프로세스 실행

스케줄링 개념(6/15) 기본요소(계속) 프로세서 버스트 짧은 프로세서 버스트가 많으며 긴 프로세서 버스트는 적음 긴 프로세서 버스트 ⇒ 프로세서 중심 작업 짧은 프로세서 버스트 ⇒ 입출력 중심 작업 프로세서 스케줄링 알고리즘 선택 기준  버스트 지속 시간 빈도 [그림6-5] 프로세서 버스트 시간의 그래프

스케줄링 개념(7/15) 정의 프로세서를 프로세스에게 할당할 시기 결정 장기 스케줄링 중기 스케줄링 단기 스케줄링

스케줄링 개념(8/15) 스케줄링 목적 공정해야 함 단위시간당 처리량 최대화 대화식 사용자에게는 적절한 시간내에 응답 예측 가능해야 함 오버헤드 최소화 무한정으로 실행 연기 피해야 함 …

스케줄링 개념(9/15) 스케줄링 큐 준비 큐 (Ready queue) 준비 상태에 있는 프로세스 리스트 자기 테이프 장치 1 준비 큐 장치 0 디스크 단말기 레지스터 큐 헤더 준비 큐 (Ready queue) 준비 상태에 있는 프로세스 리스트 장치 큐(Device queue) 대기 상태에 있는 프로세스 리스트

스케줄링 개념(9/15) 큐잉 도표 목적 : 프로세서 스케줄링 설명을 위하여 사용 큐 : 사각형(준비 큐와 장치 큐의 집합) 큐잉 도표  목적 : 프로세서 스케줄링 설명을 위하여 사용 큐 : 사각형(준비 큐와 장치 큐의 집합) 원 : 큐를 서비스하는 자원 화살표 : 시스템에서 프로세스들의 흐름(진행방향) 표현 [그림6-10]간략한 큐잉 도표

스케줄링 개념(10/15) 스케줄러 장기 스케줄러 - 실행될 작업을 꺼내서 메인 메모리에 적재 단기 스케줄러 - 프로세서 스케줄러(프로세서 배당 ) ⇒ 준비 상태에 있는 작업들 중 실행할 작업 선택 [그림6-12]작업(장기) 스케줄러와 프로세서(단기) 스케줄러

스케줄링 개념(11/15) 스케줄러(계속) 중간 단계 스케줄러 프로세서를 서로 차지하려고 할 때 프로세스를 기억장소로부터 빼낼 수가 있어서 다중 프로그래밍의 정도를 줄일 수 있음 수행이 중단되었던 곳으로부터 계속 수행 - 교체(swapping) [그림6-13]중간 단계 스케줄링을 큐잉 도표에 추가

스케줄링 개념(12/15) 스케줄러(계속) 단기 스케쥴러 디스패처(dispatcher) 기능 프로세스의 레지스터 적재(문맥교환) 준비 프로세스 프로세서 문맥교환기 디스패처 준비 큐 실행프로세스로부터 이동 다른 상태로부터 전환

스케줄링 개념(12/15) 스케줄러(계속)

스케줄링 개념(13/15) 선점 스케줄링과 비선점 스케줄링 실행중인 프로세스의 중지 가능 여부로 구분 실행중인 프로세스의 중지 가능 여부로 구분 비선점(Non-preemptive) : 실행중인 프로세스 중지 불가능 짧은 작업이 긴 작업을 기다릴 수 있음 응답시간 예측이 쉬움 선점(Preemptive) : 실행중인 프로세스 중지 가능 높은 우선순위의 프로세스 - 긴급 처리 유용 비용 초래

스케줄링 개념(14/15) Nonpreemptive: • Preemptive: once started runs as long as logically possible scheduler called when process terminates or blocks generally not useful in time-shared or real-time systems • Preemptive: stops running process and re-assigns CPU to other scheduler called when system state changes new or activated task (message or interrupt) or periodically (quantum-oriented)

스케줄링 개념(15/15) 성능의 기준 프로세서 스케줄링 알고리즘 비교 기준 처리율 최대화 반환 시간(반응 시간) 최소화 단위 시간당 완료되는 작업수가 많도록 유지 반환 시간(반응 시간) 최소화 대화식 작업 우선 처리 대기 시간의 최소화 …

2. 스케줄링 비교 선입 선처리(FCFS;First-Come-First-Served) 간단한 알고리즘, 비선점(Non-preemptive) 기법 사용 프로세서를 요구하는 순서로 할당하는 방법 시분할 시스템 사용 곤란 선입선출(FIFO) 큐로 구현 알고리즘 성능 : 좋지 않은 경우가 많으며, 평균 대기시간이 긴 경우 발생 프로세서 P1 P2 P3 P4 완료 준비 큐 선입 선처리 스케줄링

스케줄링 비교(2/16) 선입 선처리(계속) 예 프로세스 실행시간 P1 p2 p3 24 3  평균 반환 시간 : (24+27+30)/3 = 27 평균 대기 시간 : (0+24+27)/3 = 17 작업이 1,2,3의 순서  간트 도표(Gantt chart) 30 27 24 P3 P2 P1  평균 반환 시간 : (3+6+30)/3 = 13 평균 대기 시간 : (6+0+3)/3 = 3 작업이 P2, P3, P1 의 순서  간트 도표 30 6 3 P3 P2 P1

스케줄링 비교(3/16) 최소 작업 우선(SJF;Shortest Job First) 프로세서 버스트 시간이 가장 작은 작업에 할당하는 기법 프로세스가 동일한 프로세서 버스트 : 선입 선처리 스케줄링 프로세스 실행시간 P1 p2 p3 p4 6 3 8 7 평균 대기 시간 : (3+0+16+9)/4 = 7 평균 반환 시간 : (3+9+16+24) / 4 = 13

스케줄링 비교(4/16) 최소 작업 우선(계속) 1 2 3 8 4 9 5 평균반환시간 : 프로세스 실행시간 P1 p2 p3 p4 1 2 3 도착시간 8 4 9 5 평균반환시간 : 선점 : ((17-0)+(5-1)+(26-2)+(10-3))/4 = 13 비선점 : ((8-0)+(12-1)+(17-3)+(26-2))/4 = 14.25 평균 대기시간 : 선점 : ((10-0)+(1-1)+(17-2)+(5-3))/4 = 6.75 비선점 :((0+(8-1)+(12-3)+ (17-2))/4 = 7.75 26 17 12 8 P4 P3 P2 P1 비선점

스케줄링 비교(5/16) 우선순위 스케줄링 우선 순위가 각 프로세스에게 주어지면 프로세서는 최고 우선 순위를 가진 프로세스에 할당 우선 순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄링

스케줄링 비교(6/16) 우선순위 스케줄링(계속) 우선순위는 내부적/외부적 우선순위로 정의가능 내부적 정의 우선 순위 제한 시간, 기억장소 요구량, 사용파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율 등 외부적 우선순위 프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적인 요인 등 우선순위 스케줄링은 선점식이거나 비선점식 가능 P 258

스케줄링 비교(7/16) 우선순위 스케줄링(계속) 프로세스 우선순위 P1 p2 p3 p4 p5 버스트시간 3 1 4 2 10 2 1 5 평균 대기시간 : 8.2 문제점 : 무한 정지(Indefinite Blocking)와 기아(Starvation) 발생 우선순위가 높은 프로세스들이 계속 들어오면 낮은 우선순위의 프로세스들은 무한정 기다림 – 수명(Aging) 기법 해결 Aging 기법 : 대기 프로세스들의 우선 순위를 점진적 증가시키는 기법 [예] 우선 순위가 0(낮음)에서 127(높음) 까지의 범위 매 15분마다 대기중인 프로세스의 우선순위를 1씩 증가 우선 순위( 0) ⇒ 우선순위(127) : 32시간 소요 P 259

스케줄링 비교(8/16) 순환 할당 스케줄링(Round-Robin) 선점 알고리즘, 시분할 시스템(Time-Sharing System)에 적용 시간량(Time quantum), 시간 할당량(Time slice) 단위 시간 정의 준비 큐 : 순환 큐(Circular queue)로 설계, 선입선출(FIFO) 구조 프로세서 스케줄러 - 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 시간량 만큼 프로세서를 제공 알고리즘 성능 - 시간량의 크기에 영향 받음(시간량 무한대  선입 선처리) 현재 프로세스 다음 [그림6-24] 프로세스 B가 실행된 후의 준비 큐 P 259

스케줄링 비교(9/16) 순환 할당 스케줄링(계속) 1 2 3 8 4 9 5 프로세스 실행시간 P1 p2 p3 p4 1 2 3 도착시간 8 4 9 5 반환 시간 = 작업 완료 시간 - 도착 시간 평균 반환시간 : (20+7+24+22)/4 =18.25 평균 대기시간 : (12+3+15+17) =47÷4=11.75 규정 시간량 : 4 26 20 12 8 P4 P3 P2 P1 4 16 24 25

스케줄링 비교(10/16) 다단계 큐 (multi-level queue) 준비상태 큐를 여러 단계 종류로 분할하여 사용 기억장치의 크기나 프로세스의 형태에 따라 어느 한 큐에 지정 각 큐는 독자적인 스케줄링 알고리즘 소유 전면 작업과 후면 작업은 서로 분할된 큐에 지정 전면 작업 큐는 순환 할당 알고리즘에 의해 스케줄링 후면 작업 큐는 선입선처리(FCFS)로 스케줄링 큐 사이에는 고정된 우선순위의 선점식 스케줄링 사용 전면 작업 큐는 후면 작업 큐보다 절대적 우선 순위 가질 수 있음

스케줄링 비교(11/16) 다단계 큐 (계속) 5개 큐를 가진 다단계 큐 스케줄링 알고리즘 예 최고의 우선순위 최저의 우선순위 일괄 프로세스 학생의 프로세스 대화형 편집 프로세스 대화형 프로세스 시스템 프로세스 큐는 프로세서 시간 일정량 받아, 자기 큐에 있는 프로세스들을 스케줄링 [그림6-30] 다단계 큐 스케줄링

스케줄링 비교(12/16) 다단계 피드백 큐(Multi-Level Feedback Queue) 다단계 큐 스케줄링 알고리즘 분석 작업이 한 큐에서만 고정되어 실행되며 큐 사이에 옮겨지지 않음 전면 작업과 후면 작업의 성질을 바꿀 수 없음 스케줄링 부담이 적은 장점은 있으나 융통성이 적음 다단계 피드백 큐 작업이 큐 사이를 이동 가능 서로 다른 프로세서 버스트 특성에 따라 분리 구분 작업이 요구하는 프로세서 시간이 너무 크면 낮은 단계 큐로 이동 입출력 중심작업과 전면(대화식 작업) 작업을 높은 우선순위 큐로 이동 낮은 우선 순위 큐에서 오래 기다린 작업은 높은 우선 순위 큐로 이동 기아 상태 예방 : 에이징(aging) 사용

스케줄링 비교(13/16) Like ML, but priority changes dynamically decreases every process enters at highest level n each level P prescribes maximum time tP tP increases as P decreases Typically: tn = T (constant) tP = 2 × tP+1

스케줄링 비교(14/16) MLF priority function given by P = n–i for given a

스케줄링 비교(15/16) RR or FIFO decision within each priority level Given: tn = 1, tn-1 = 2, tn-2 = 4, … p1 runs for 2 time units until … - for 1 unit on level n and 1 unit on level n-1 p2 preempts at time 2 and runs for 1 time unit … - then changes to level n-1 p1 preempts at time 3 and runs for 1 time unit … - then changes to level n-2 p2 preempts at time 4 and completes (by 5) p1 resumes at time 5 and completes (by 7)

스케줄링 비교(16/16) RR and MLF: good for time-sharing systems response time is critical RR or MLF with RR within each queue are suitable choice of quantum determines overhead when q → ∞, RR approaches FIFO when q → 0, context switch overhead → 100% when q >> context switch overhead, -> n processes run concurrently at 1/n CPU speed