제 5 장 프로세스 스케줄링

프로세스의 스케줄링 다중 프로그래밍(Multi-Programming) 프로세스의 상태 변화 스케줄링 현대 운영체제에서 가장 중요한 개념 동시에 여러 프로그램을 메모리에 적재하고 자원을 사용하게 하여 전반적인 시스템의 효율을 향상 I/O(입출력)와 CPU(계산)의 동시 사용 프로세스의 상태 변화 실행  대기(blocked): 입출력 시스템 호출 후 그 완료를 기다림 실행  준비(ready): time slice가 소진 스케줄링 단순 정의: 준비 상태의 프로세스 중 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 과정 심화 정의: 프로세스의 동적 우선순위를 언제 어디서 어떻게 설정하고 언제 context switching을 실행하는지 결정하는 정책

Model of Process Execution Preemption or voluntary yield New Process Ready List Scheduler CPU Done job job “Running” job “Ready” Resource Manager Allocate Request job job “Blocked” Resources

스케줄링 개념 스케줄링의 대상 스케줄러 스케줄러의 구성/형태 준비 상태의 사용자 및 시스템 프로세스 (Thread) 오류에 의한 trap이나 인터럽트 처리 작업은 대상이 아님 스케줄러 장기 스케줄러 (Long-Term Scheduler) 새로운 작업을 시스템에 적재하기 위한 스케줄러 Degree of Multiprogramming이 증가함 단기 스케줄러 (Short-Term Scheduler) 준비 큐에서 CPU 사용을 기다리는 프로세스를 선택하는 스케줄러 스케줄러의 구성/형태 디스패처(Dispatcher): 문맥 교환(context switch) 실행 장기/단기 스케줄러 선점/비선점 스케줄링

장기/중기/단기 스케줄러 스케줄러(Scheduler)의 종류 장기 스케줄러 (Long-Term Scheduler, Job Scheduler) 어떤 작업이 시스템에서 처리될 것인지 결정 후 메모리에 적재 멀티 프로그래밍의 정도(degree)를 조절함 작업이 시스템을 떠날 때 한번 실행됨 CPU 중심작업과 I/O 중심작업을 적절히 혼합하도록 함 단기 스케줄러 (Short-Term Scheduler, CPU Scheduler) 메모리 내의 준비 상태에 있는 작업을 선택해 CPU 할당 문맥교환이 자주 일어나기 때문에 효율적으로 실행되어야 함 중기 스케줄러 (Mid-Term Scheduler) Thrashing 등의 이유로 일부 프로세스를 메모리에서 디스크로 보내 다중 프로그래밍의 정도를 조정 단기 스케줄링을 받지 않게 됨 Thrashing: 메모리 부족 디스크 입출력 과다  시스템 정지 Swap in/out을 통해 메모리와 디스크로 프로세스가 이동

장기/중기/단기 스케줄러 프로세스 상태와 스케줄링 유형과의 관계 스케줄링 단계와 프로세스 상태와의 관계

스케줄링 알고리즘 비선점(Non-preemption) 스케줄링 시분할 시스템에서의 선점(preemption) 스케줄링 현재 실행중인 프로세스의 CPU를 강제로 빼앗지 않는 스케줄링 Time Slice를 적용하지 않는 경우 CPU를 자진 반납할 때 까지 CPU의 사용을 보장함 FCFS (First-Come-First-Served) 최단 작업 우선 (Shortest Job First; SJF) 시분할 시스템에서의 선점(preemption) 스케줄링 현재 실행중인 프로세스의 CPU를 강제로 빼앗는 스케줄링 라운드 로빈 스케줄링 (RR) Shortest Remaining Time First (SRTF) 다단계 큐 스케줄링 다단계 피드백 큐 스케줄링

스케줄링 알고리즘 알고리즘 비교를 위한 성능 평가의 기준 시스템의 형태에 따라 기준이 달라짐 CPU 사용율 (CPU utilization) 처리율 (throughput): 단위 시간당 완료되는 작업 수 반환 시간(turnaround time): 시스템 입력 후 출력 때 까지 시간 대기 시간(waiting time): 준비 큐에서 CPU를 기다리는 시간 반응 시간(response time): 요구 의뢰부터 반환 까지 시간 시스템의 형태에 따라 기준이 달라짐 Time Sharing은 반응 시간이 가장 중요 기준 간에 trade-off 가 있음 기준 평균치의 최적화(효율성)와 편차의 최소화(공평성)을 함께 고려해야 함 짧은 시간 작업 우선 처리 시 (SJF) 평균 반환시간 (효율성)은 감소, 처리율 증가 긴 작업 완료시간 증가로 반환시간 편차 증가 및 공평성 상실

FCFS 스케줄링 비선점(non-preemption) 스케줄링 프로세스 도착순으로 CPU 배정 장기 스케줄러 또는 시분할 시스템에서 Time Slice를 적용하지 않는 프로세스에 대해 사용할 수 있음 배치, 백 그라운드 또는 실시간 프로세스 등 호위 효과(Convoy Effect)의 문제 수행 중인 긴 작업을 여러 개의 짧은 작업이 기다리는 현상 CPU 버스트 시간을 어떻게 예측할 것인가?

FCFS 스케줄링 세 작업의 평균 반환 시간 계산 작업번호 전체 실행 시간 1 2 3 24 작업이 1, 2, 3 순서로 들어온 경우 (호위 효과: Convoy Effect) 작업 1 작업 2 작업 3 24 27 30 평균 대기 시간: (0 + 24 + 27) / 3 = 17 평균 반환 시간: (24 + 27 + 30) / 3 = 27 작업이 2, 3, 1 순서로 들어온 경우 작업 2 작업 3 작업 1 3 6 30 평균 대기 시간: (0 + 3 + 6) / 3 = 3 평균 반환 시간: (3+6+30) / 3 = 13

최단 작업 우선(Shortest Job First; SJF) 각 작업의 다음 CPU burst 시간이 가장 작은 작업에 CPU를 할당하는 기법 (non-preemptive) CPU가 한번 할당된 후 입출력 요구 때까지 프로세스가 사용하는 CPU의 사용 시간 작업번호 CPU Burst 시간 1 2 3 4 6 8 7 모든 작업은 시간 0에 도착했다고 가정함 작업 2 작업 1 작업 4 작업 3 3 9 16 24 평균 반환 시간: (3+9+16+24) / 4 = 13 FCFS 인 경우 평균 반환시간: (6+9+17+24) / 4 = 14

SRTF: Shortest Remaining Time First Preemptive: SRTF (Shortest Remaining Time First) Non-Preemptive: SJF 작업번호 도착 시간 1 2 3 4 CPU Burst 시간 8 9 5 <Non-Preemptive> 작업 1 작업 2 작업 4 작업 3 8 12 17 26 평균 반환 시간: {8 + (12-1) + (17-3) + (26-2)} / 4 = 14.25 <Preemptive> 1 작업 2 작업 4 작업 1 작업 3 1 5 10 17 26 평균 반환 시간: {(5-1) + (10-3) + 17 + (26-2)} / 4 = 13

최단 작업 우선(Shortest Job First; SJF) 평균 대기 시간에 있어서 최적 알고리즘 문제점: 차기 CPU 요구 시간을 알기가 어려움 일괄 처리 시스템의 장기 스케줄링의 경우, 작업 시간 예측치를 제출함. (실제 시간 초과 시에는 다시 제출) 단기 스케줄링의 경우 다음 CPU 버스트(Burst) 시간 예측이 어려움 이전 버스트 시간들을 통해 다음 버스트 시간을 예측해서 활용함 이전 버스트 시간과 유사할 것이라는 가정

CPU Burst time duration

CPU Burst 시간 예측 차기 버스트 시간 계산 τn+1 = αtn + (1-α)τn (0≤α≤1) tn : n번째 실제 사용한 CPU 버스트 시간 τn : n 번째 예상했던 CPU 버스트 시간 τn+1 : 앞으로의 예상 CPU 버스트 시간 일반적으로 이전 버스트 시간의 평균으로 생각함 α= 0 이면 τn+1 = τn 이 되어 실제 burst 시간 값은 무시됨 α= 1 이면 τn+1 = tn 이 되어 최근 burst 시간만 영향 미침 α= 1/2 이면 현재의 상황과 과거의 상황이 동일하게 영향을 줌 α> ½ 이면? α< ½ 이면?

우선 순위 (Priority) 알고리즘 우선순위는 모든 프로세스에게 주어지며, CPU는 우선순위가 제일 높은 프로세스에 할당되고, 우선순위가 같은 경우 FCFS로 처리됨 SJF는 우선순위 스케줄링 알고리즘의 특수한 형태임 CPU burst time이 적을수록 높은 우선순위가 부여됨 우선순위의 설정 내부적 우선순위 제한 시간, 기억 장소 요구량, 사용하는 파일 수, 평균 CPU 버스트에 대한 평균 입출력 시행 비율 등 외부적 우선순위 높은 사용료 지불자 우선, 정책적인 변수 등 문제점 기아 상태 유발 : 에이징(aging)으로 해결 CPU 할당 받지 못하고 기다리면 우선순위가 점차 증가함

시분할 시스템에서의 선점 스케줄링 용어 선점 (preemption) 연산 위주 프로세스(CPU-bound process) Time Slice 소진 시 CPU를 강제로 회수하는 행위 연산 위주 프로세스(CPU-bound process) CPU 연산을 많이 하는 프로세스: 우주선 궤도 계산, 그래픽 처리 입출력 위주 프로세스(I/O-bound process) 입출력이 주된 작업: 간단한 입출금 처리 평균 CPU 반환 시간 (CPU burst) CPU가 할당되고 입출력을 위해 CPU를 반환할 때까지의 평균 시간 실시간 프로세스 (Real Time Process) 주어진 시간 내에 처리를 하지 않으면 치명적인 일이 발생하는 작업 스케줄링 각 프로세스에 언제 어떻게 우선순위를 주고 각 프로세스의 우선순위를 조정하는 작업

시분할 시스템에서의 선점 스케줄링 일반적 원칙 입출력 위주의 프로세스에게 연산 위주의 프로세스 보다 높은 우선순위를 주어야 한다 CPU-bound 작업과 I/O-bound 작업이 동시에 작동됨 입출력 위주의 프로세스는 일반적으로 대화형 프로세스임 Time Slice는 프로세스들의 평균 CPU 반환 시간 보다 약간 큰 것이 좋다 작으면 선점에 의한 문맥 교환 오버헤드가 발생할 수 있음 실시간 프로세스는 일반적인 프로세스 및 대부분의 커널 실행 작업보다도 우선순위가 높다 재앙적인 결과가 일어나지 않도록 해야 함 일반적으로 프로세스가 커널 모드에 있을 때, 프로세스가 대기상태 전이의 이유로 CPU를 스스로 반환하기 이전에는 선점이 일어나지 않는다 사용자 모드에 있는 프로세스에 대해서만 선점(Preemption)이 발생 커널 모드 시 선점을 하게 되면 복잡한 상호배제 문제 발생 가능

라운드 로빈 (Round Robin) 스케줄링 프로세스의 Time Slice 소진 시 준비 큐의 맨 뒤로 보내짐 클럭 인터럽트 처리기에 의해 타임 슬라이스 소진이 확인됨 타임 슬라이스 소진 전에 입출력을 요구하면 CPU를 반납하고 대기(Blocked) 상태로 전이됨 우선 순위가 같은 프로세스(스레드)들인 경우에 의미 있는 스케줄링 기법임 타임 슬라이스 값이 매우 크면 : FCFS와 동일 매우 작으면 : 문맥 교환 오버헤드가 커짐 작은 Time Slice의 경우 문맥 교환이 증가 됨

라운드 로빈 (Round Robin) 스케줄링 세 작업의 평균 반환 시간 계산 작업번호 전체 실행 시간 1 2 3 24 모든 작업은 시간 0에 도착 하였다고 가정함 Time Slice = 4 작업 1 작업 2 작업 3 작업 1 작업 1 작업 1 작업 1 작업 1 4 7 10 14 18 22 26 30 평균 반환 시간: (7+10+30) / 3 = 16 Time Slice 값을 q, 프로세스가 n 개 있을 경우 CPU 할당 받기 위해 기다리는 최대 시간은? (n-1) * q

알고리즘의 비교 각 알고리즘 별로 평균 반환 시간을 계산하세요 FCFS? SJF? RR? 작업번호 Burst Time 1 2 3 4 5 10 29 7 12 모든 작업은 시간 0에 도착 하였다고 가정함 평균 반환시간: 시스템 입력 후 출력 때 까지 걸리는 시간 Time Slice (Quantum) = 10 FCFS? SJF? RR?

알고리즘의 비교 각 알고리즘 별로 평균 대기 시간을 계산하세요 FCFS: 작업번호 Burst Time 1 2 3 4 5 10 29 7 12 모든 작업은 시간 0에 도착 하였다고 가정함 평균 대기시간: CPU를 할당 받기 위해 기다리는 시간 Time Slice (Quantum) = 10 FCFS: (0 + 10 + 39 + 42 + 49) / 5 = 28 SJF: (10 + 32 + 0 + 3 + 20) / 5 = 13 RR: (0 + 32 + 20 + 23 + 40) / 5 = 23 10 + 20 + 2

다단계 큐 스케줄링 Multi-Level Queue Scheduling 각 프로세스들을 서로 다른 우선순위의 묶음으로 분류 대화형 프로세스는 Foreground Group 일괄 처리형 프로세스는 Background Group 등으로 분류 우선 순위별로 준비 큐 형성 항상 가장 높은 우선 순위 큐의 프로세스에 CPU 할당 각 큐는 Round Robin이나 FCFS 사용 대화형, 배치(background) 등의 프로세스 성격에 따라 우선 순위 부여 프로세스가 하나의 큐에 할당되면 그 큐에 계속 귀속됨

다단계 큐 스케줄링 IBM OS/MFT 의 다단계 큐 스케줄링 최고 우선순위 시스템 관련 태스크 대화형 작업 편집 관리자의 일괄처리 작업 학생들의 일괄처리 작업 최저 우선순위

다단계 피드백 큐 스케줄링 Multi-Level Feedback Queue Scheduling 다 단계 큐 + 동적으로 프로세스의 우선 순위를 변화 CPU를 사용하다가 Time Slice를 소진하면 아래 단계 큐의 가장 뒤에 삽입됨 CPU-bound 성격의 작업일 것이라 예측되므로 우선순위를 낮춤 CPU를 오래 대기 하면 다시 상위 큐로 이동 기아 상태 (starvation)를 막기위해 aging 방법 사용 하위 큐에는 큰 Time Slice를 주는 경우도 있음 하위 큐에 CPU-bound 작업들이 있으므로 Context Switch 횟수를 줄일 필요가 있음 CPU 사용 도중 상위 우선순위 프로세스가 발생해 선점 당해 Time Slice를 다 채우지 못한 경우 우선순위가 유지되며 해당 순위 준비 큐의 가장 앞으로 다시 삽입 가장 하위 큐는 라운드 로빈 방식으로 운영

다단계 피드백 큐 스케줄링 IO-bound process CPU-bound process 타임 슬라이스 소진 CPU-bound process CPU 반환시간이 8 이하인 작업에 가장 높은 우선권 부여 CPU 반환시간이 8~24 인 작업에 다음으로 높은 우선권 부여

다단계 피드백 큐 스케줄링 다단계 피드백 큐 스케줄링 알고리즘의 구성요소 CPU 스케줄링 알고리즘 중에서 가장 일반적임 큐의 수 각 큐에 대한 스케줄링 알고리즘 작업을 보다 높은 우선순위 큐로 올리는 시기를 결정하는 방법 작업을 보다 낮은 우선순위 큐로 내리는 시기를 결정하는 방법 어떤 프로세스가 어느 큐에 들어갈 것인가를 결정하는 방법 모든 프로세스가 최상위 큐에서 시작되지 않을 수 있음 CPU 스케줄링 알고리즘 중에서 가장 일반적임 설계중인 어떤 특정한 시스템에도 맞게 적용될 수 있음 최상의 스케줄러를 정의하기 위한 위의 평가치를 찾는 것이 복잡하다

유닉스/리눅스 계열 스케줄링 유닉스 계열에서는 세 가지 우선순위 그룹으로 분류 실시간 프로세스 커널 모드 우선 순위 최상위 우선 순위 FCFS와 라운드 로빈 중에서 선택적으로 사용가능 커널 모드 우선 순위 프로세스가 커널 내에서 입출력 요구하여 대기하다, 입출력이 완료된 후 준비 상태로 되었을 때의 우선 순위 커널 모드에서는 Time Slice에 의한 선점은 없음 사용자 모드 우선 순위 user mode 에서 실행되는 경우 적용되는 우선 순위로 다단계 피드백 스케줄링이 적용됨 CPU를 많이 사용할수록 우선순위가 낮아지며, CPU 대기 상태가 길어질수록 우선순위가 높아진다

다중 처리기 스케줄링 CPU가 여러 개 존재하는 경우 대칭 다중 처리 (Symmetric multi-processing) 최적의 알고리즘은 없음 대칭 다중 처리 (Symmetric multi-processing) 같은 형태의 CPU인 경우 특정 CPU에 부하가 많은 상황이 발생할 가능성이 있음 일반적으로 공통의 큐 사용 처리기 자신이 스스로 스케줄링을 함 공통 자료구조 접근/변경 시 주의가 필요함 두 CPU가 같은 프로세스를 선택하지 않도록 함 어떤 프로세스도 스케줄링에서 누락되지 않도록 함 비대칭 다중 처리 (Asymmetric multi-processing) 하나의 CPU는 전적으로 스케줄링 작업을 담당함 Master processor 가 slave processor 들에게 작업 할당

스케줄링 연습 예제 (참고자료) 도착시간을 고려하여 여러분도 스스로 풀어보세요

FCFS: Non-Preemptive 5 10 15 20 A B C D E 실행시간이 오래 걸리는 프로세스인 경우 선호함(기다리는 시간이 오래 걸려도 대기 하는 부담이 적음) CPU-bound 작업인 경우 선호함 (I/O-bound 프로세스인 경우 CPU-bound 작업들이 끝나고 나서 다시 처리됨)

Shortest Job First: Non-Preemptive 5 10 15 20 A B C D E 현재 시점에서 가장 적은 Service Time이 남은 프로세스에게 CPU를 할당함 긴 Service Time을 가진 프로세스는 기아 상태(Starvation)에 빠질 염려가 있음

Shortest Remaining Time First: Preemptive 5 10 15 20 A B C D E Shortest Job First의 Preemptive 버전 현재 시점에서 Service Time이 가장 작은 프로세스에게 CPU 할당

Round Robin: Preemptive 5 10 15 20 A B C D E Time Slice(Quantum) = 1 Timer Interrupt에 의해 Ready Queue에 있는 다음 프로세스가 선택되어 실행됨 새로 도착한 프로세스와 Time Slice를 소모한 프로세스가 같은 시간에 준비큐에 입력될 때, 새로 도착한 프로세스가 먼저 준비큐에 입력된다고 가정함