운영체제 (Operating Systems) CPU 스케줄링 (CPU Scheduling) 문양세 강원대학교 IT대학 컴퓨터과학전공

강의 목표 다중 프로그램 운영체제의 기반인 CPU 스케줄링을 이해한다. 다양한 CPU 스케줄링 알고리즘을 학습한다. CPU 스케줄링(CPU Scheduling) 다중 프로그램 운영체제의 기반인 CPU 스케줄링을 이해한다. 다양한 CPU 스케줄링 알고리즘을 학습한다. CPU 스케줄링 알고리즘을 선택하는 평가 기준을 논의한다.

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

기본 개념(1/2) CPU 스케줄링 (혹은 프로세스 스케줄링) 용어 다중 프로그램 운영체제에서 가장 기본적인 기능이다. CPU 스케줄링(CPU Scheduling) CPU 스케줄링 (혹은 프로세스 스케줄링) 다중 프로그램 운영체제에서 가장 기본적인 기능이다. 용어 일반적으로, CPU 스케줄링, 프로세스 스케줄링, 커널 스레드 스케줄링을 모두 같은 개념 으로 사용한다. 본 교재에서는 CPU 스케줄링과 프로세스 스케줄링의 용어를 사용하며, 특별히 스레드 관련이 있는 경우에만 커널 스레드 스케줄링 용어를 사용한다.

기본 개념(2/2) 단일 프로세서 시스템에서 프로세스 스케줄링은 CPU 이용률의 최대화는 다중 프로그래밍에 의해 가능하다. CPU 스케줄링(CPU Scheduling) 단일 프로세서 시스템에서 상호작용 응용의 다중 스레딩은 하나의 스레드가 일시 봉쇄(blocking)되어도 다른 스레 드는 수행을 계속하게 한다.  사용자 응답성 증가 한번에 오직 하나의 프로세스만 수행된다. 다른 프로세스들은 CPU가 자유로워져 재-스케줄 될 수 있을 때까지 기다린다. 수행 중이던 프로세스가 대기 상태로 이동할 때, 운영체제는 CPU 이용률을 향상시키기 위하여 CPU를 할당할 다른 프로세스를 선택할 수도 있다. 하나의 프로세스가 기다리는 순간, 다른 프로세스는 CPU를 양도 받아 사용할 수 있다. 프로세스 스케줄링은 운영체제의 기본적인 역할이다. 기본 기능은 준비완료 큐에 있는 하나의 프로세스를 선택하여 CPU를 할당한다. CPU 이용률의 최대화는 다중 프로그래밍에 의해 가능하다. 즉, 효율적인 프로세스 스케줄링에 의해 CPU 이용률을 최대화할 수 있다.

프로세스 상태도 – 제3장 어느 한 시점에 프로세서(CPU)에서 실행 중인 프로세스는 1개 뿐이라는 점이 중요하다. CPU 스케줄링(CPU Scheduling) 어느 한 시점에 프로세서(CPU)에서 실행 중인 프로세스는 1개 뿐이라는 점이 중요하다. 많은 프로세스들은 준비완료(ready) 또는 대기(waiting) 상태에 있다.

프로세스 스케줄링의 표현 – 제3장 두 가지 유형의 큐: 1개의 준비완료 큐, 1개의 장치 큐 CPU 스케줄링(CPU Scheduling) 두 가지 유형의 큐: 1개의 준비완료 큐, 1개의 장치 큐 두 가지 유형의 자원: CPU, 입출력(I/O) 화살표는 시스템 내의 프로세스 흐름을 나타낸다.

CPU-입출력 버스트 사이클 (CPU-I/O Burst Cycle) CPU 스케줄링(CPU Scheduling) 프로세스 실행은 두 가지 버스트(burst)의 사이클로 이루어진다. CPU 버스트: CPU에서 실행되는 시간을 의미한다. I/O 버스트: 입출력에 따른 대기 시간을 의미한다. 프로세스는 두 가지 버스트를 번갈아 가며 수행된다. 프로세스 수행은 CPU 버스트로 시작하고, 다음에 입출력 버스트가 뒤따른다. 결론적으로, 마지막 CPU 버스트는 실행을 종료하는 시스템 호출로 끝난다. 프로세스의 CPU 버스트, I/O 버스트 빈도 프로세스마다 컴퓨터마다 크게 차이가 난다.

CPU & I/O 버스트 교환 순서 CPU 스케줄링(CPU Scheduling) CPU 버스트 시간 I/O 버스트 시간

CPU 버스트의 지속 시간 CPU 버스트 시간 분포는 일반적으로 다음 특징을 갖는다. CPU 스케줄링(CPU Scheduling) CPU 버스트 시간 분포는 일반적으로 다음 특징을 갖는다. 지수형(exponential) 혹은 초지수형(hyper-exponential) 형태이다. 많은 수의 짧은 CPU 버스트 + 작은 수의 긴 CPU 버스트를 갖는다. 입출력 중심 프로세스는 많은 수의 짧은 CPU 버스트를 가진다. CPU 중심 프로세스는 몇 개의 긴 CPU 프로세스를 가진다.

CPU 스케줄러(CPU Scheduler) CPU 스케줄링(CPU Scheduling) CPU 스케줄러는 운영체제 모듈의 한 가지이다. 실행할 준비가 되어 메모리에 있는 프로세스들 중에 하나를 선택하여 선택된 프로세스 에게 CPU를 할당한다. CPU 스케줄링은 네 가지 상황에서 발생한다. 실행 상태에서 대기 상태로 전환될 때: 입출력 요구, 다른 프로세스의 종료를 위한 wait() 함수 호출 실행 상태에서 준비완료 상태로 전환될 때: 인터럽트가 발생할 때 (예: 타이머) 대기 상태에서 준비완료 상태로 전환될 때: 입출력이 끝나면 종료될 때 과  수행 중 스케줄링은 비선점(non-preemptive) 방식이다. 와  수행 중 스케줄링은 선점(preemptive) 방식이다.

비선점(Non-preemptive) vs 선점(Preemptive) CPU 스케줄링(CPU Scheduling) 비선점 스케줄링 일단, CPU가 하나의 프로세스에 할당되면, 그 프로세스는 CPU를 놓을 때 때까지는 계속 CPU를 점유하고 있는다. 종료되거나 대기 상태로 전환한다. 선점 스케줄링 현재 수행되고 있는 프로세스는 언제든지 다른 프로세스로 전환될 수 있다. 이유: 인터럽트가 언제든지 발생할 수 있기 때문이다. 현대 운영체제의 대부분은 이 방법을 제공한다. (윈도우 XP, 맥 OS, 유닉스) 프로세스 간에 데이터 공유 시, 일관성 유지에 따른 관련 비용을 발생시킨다. 운영체제의 커널 설계에 영향을 끼친다. 유닉스의 경우, 문맥 전환이 일어나기 전에 시스템 호출의 완료 혹은 입출력 봉쇄(block)가 일 어나기를 기다린다. 중요한 코드의 시작 부분에서는 인터럽트를 비활성화(disable)시키고, 끝 부분에는 활성화 (enable) 시킴으로써 매우 중요한 커널 코드를 보호한다.

디스패처(Dispatcher) 디스패처 모듈은 CPU 스케줄러의 일부분이다. CPU 스케줄링(CPU Scheduling) 디스패처 모듈은 CPU 스케줄러의 일부분이다. 단기 스케줄러에게 선택된 프로세스에게 CPU 제어권을 넘겨주며, 이 과정은 다음 내용을 포함한다. 문맥 전환(switching context) 사용자 모드로 전환(switching to user mode) 선택된 프로그램을 재실행하기 위한 사용자 프로그램의 적당한 위치로 옮긴다. 디스패치 지연(dispatch latency): 디스패처가 실행 중이던 프로세스를 멈추고 다른 프로세스가 실행되게 하는데 걸리는 시간

문맥 전환(Context Switch) – 제3장 CPU 스케줄링(CPU Scheduling) dispatcher latency dispatcher latency

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

스케줄링 기준(Scheduling Criteria) (1/2) CPU 스케줄링(CPU Scheduling) 스케줄링 기준을 기반으로, 다양한 스케줄링 알고리즘에 대한 성능 평가 가 이루어질 수 있다. 서로 다른 스케줄링 알고리즘은 서로 다른 특징(장점)을 가진다. CPU 사용률(utilization): 단위 시간 당 CPU가 작업을 수행하는 총 시간 비율 (%) 처리량(throughput): 단위 시간 당 실행을 완료한 프로세스 개수 총처리 시간(turnaround time): 프로세스가 제출된 시간부터 작업을 완 료하는 시간까지의 간격 메모리에 올라가기 까지 기다린 시간, 준비완료 큐에서 대기한 시간, CPU에서 수행되고, 입출력을 수행하는 모든 시간의 합

스케줄링 기준(Scheduling Criteria) (2/2) CPU 스케줄링(CPU Scheduling) 대기 시간(waiting time): 프로세스가 준비완료 큐에서 대기하면서 보낸 시간의 합계 실행하거나 입출력하는 시간에 영향을 받지 않는다. 오직 프로세스가 준비완료 큐에서 얼마나 대기하느냐가 알고리즘에 영향을 미친다. 응답/반응 시간(response time): 대화형 시스템에서, (시분할 환경을 위해 서) 요청이 제출되고 첫 번째 반응이 돌아오기까지 걸리는 시간의 합계 (총처리 시간과 달리) 출력하는데 걸리는 시간을 포함하진 않는다. 즉, 출력이 시작되는 시점까지 걸리는 시간을 의미한다.

최적화 기준(Optimization Criteria) CPU 스케줄링(CPU Scheduling) 최대화가 바람직한 기준 CPU 사용률(CPU utilization) 처리량(throughput) 최소화가 바람직한 기준 총처리 시간(turnaround time) 대기 시간(waiting time) 응답/반응 시간(response time)

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

CPU 스케줄링 알고리즘 선입 선처리 스케줄링(First-Come, First Served: FCFS) CPU 스케줄링(CPU Scheduling) 선입 선처리 스케줄링(First-Come, First Served: FCFS) 최단 작업 우선 스케줄링(Shortest Job First: SJF) 우선순위 스케줄링(Priority Scheduling) 라운드 로빈 스케줄링(Round Robin Scheduling) 스케줄링 알고리즘 비교를 위한 측정 요소는 평균대기 시간을 주로 사용 한다. 그 외에도 CPU 사용률, 처리량, 총처리 시간, 응답 시간 등도 함께 고려한다.

First-Come, First Served(FCFS) Scheduling CPU 스케줄링(CPU Scheduling) CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당 받는다. FCFS 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리할 수 있다. 프로세스가 준비완료 큐에 진입하면, 이 프로세스의 PCB를 큐의 끝에 연결한다. CPU가 자유상태가 되면, 준비완료 큐의 맨 앞에 있는 프로세스에게 CPU를 할당한다.

FCFS의 대기 시간 분석(1/2) 시간 0에 도착한 오른쪽의 세 프로세스 집합을 고려한다. CPU 스케줄링(CPU Scheduling) 시간 0에 도착한 오른쪽의 세 프로세스 집합을 고려한다. 프로세스 도착순서가 P1, P2, P3라 가정하자. 이 경우, 프로세스 스케줄링을 위한 간트 차트(Gantt chart) 대기 시간 분석 프로세스별 대기 시간: P1 = 0, P2 = 24, P3 = 27 평균 대기 시간: (0 + 24 + 27) / 3 = 17

FCFS의 대기 시간 분석(2/2) 프로세스 도착순서가 P2, P3, P1이라 가정하자. CPU 스케줄링(CPU Scheduling) 프로세스 도착순서가 P2, P3, P1이라 가정하자. 이 경우, 프로세스 스케줄링을 위한 간트 차트 대기 시간 분석 프로세스별 대기 시간: P1 = 6, P2 = 0, P3 = 3 평균 대기 시간: (6 + 0 + 3) / 3 = 3  앞서의 P1, P2, P3에 비해 성능(대기 시간)이 크게 향상됨

FCFS 스케줄링 예제 – 참조 P0 P1 P2 CPU 스케줄링(CPU Scheduling) CPU (10) I/O (20) 10 20 30 40 50 I/O(24) P0 CPU(10) I/O(6) P0 CPU(11) P1 CPU(9) 10 14 20 24 30 41 50 54

FCFS 스케줄링 분석 FCFS 스케줄링은 비선점(non-preemptive) 방식이다. CPU 스케줄링(CPU Scheduling) FCFS 스케줄링은 비선점(non-preemptive) 방식이다. 일단 CPU가 프로세스에게 할당되면, 그 프로세스 종료, 입출력 요구 등에 의해 CPU를 놓을 때까지 CPU를 점유한다. 특히 시분할 시스템에서는 문제가 된다. 호송 효과(convoy effect)가 발생한다. 긴 CPU 버스트를 가진 하나의 CPU 중심 프로세스와 짧은 CPU 버스트를 가진 많은 입 출력 중심 프로세스가 순서대로 수행되고 있을 때, 모든 입출력 중심 프로세스는 입출력 장치들이 놀고 있으면서 CPU 중심 프로세스가 CPU를 놓을 때까지 기다려야 한다. 모든 입출력/CPU 중심 프로세스들은 CPU가 놀고 있으면서 입출력 연산을 수행한다. 결론적으로 낮은 CPU와 장치 사용률을 보인다.

최단 작업 우선(Short Job First:SJF) 스케줄링 CPU 스케줄링(CPU Scheduling) 각 프로세스의 다음(next) CPU 버스트 길이를 스케줄링에 사용한다. 가장 짧은 다음 CPU 버스트를 가진 프로세스에 CPU를 할당한다. 선점(preemptive) vs 비선점(non-preemtive) 비선점: 일단 CPU가 하나의 프로세스에게 주어지면, 그 프로세스가 CPU 버스트를 완료 할 때까지 CPU를 내놓지 않는다. 선점: 만약 새롭게 도착한 프로세스의 CPU 버스트 길이가 현재 수행 중인 프로세스의 남은 CPU 버스트 길이보다 짧다면, 현재 수행 중이던 프로세스는 CPU를 내어준다.  잔여 단기 작업 최우선(Shortest-Remaining-Time-First: SRTF) 알고리즘이라 한다 SJF는 대기 시간에 최적이다. 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 제공한다. 문제점: 다음 CPU 버스트 길이를 어떻게 알지?  추정!?

비선점 SJF 예제 비선점 SJF의 스케줄링 평균 대기 시간 = (0 + 6 + 3 + 7) = 4 CPU 스케줄링(CPU Scheduling) 비선점 SJF의 스케줄링 평균 대기 시간 = (0 + 6 + 3 + 7) = 4 참고: FCFS 스케줄링 시 대기 시간 = (0 + 5 + 7 + 7) = 4.75

선점 SJF 예제 선점 SJF의 스케줄링 평균 대기 시간 = (9 + 1 + 0 + 2) = 3 CPU 스케줄링(CPU Scheduling) 선점 SJF의 스케줄링 평균 대기 시간 = (9 + 1 + 0 + 2) = 3 참고: 비선점 SJF 스케줄링 대기 시간 = 4

선점 SJF 스케줄링 예제 – 참조 P0 P1 P2 CPU 스케줄링(CPU Scheduling) CPU (10) I/O (20) CPU(11) CPU(6) I/O(17) CPU(9) CPU(4) I/O(4) CPU (4) 10 20 30 40 50 I/O(24) CPU(1) P1 CPU(9) I/O(2) I/O(1)

비선점 SJF 스케줄링 예제 – 참조 P0 P1 P2 CPU 스케줄링(CPU Scheduling) 10 20 30 40 50 10 20 30 40 50 P0 CPU (10) I/O (20) CPU(11) P1 CPU(6) I/O(17) CPU(9) P2 CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) P0 CPU(10) P2 CPU(4) P1 CPU(6) P2 CPU(4) Idle (6) P0 CPU(11) P1 CPU(9) P2 CPU(4)

다음 CPU 버스트 길이 결정 미래 시점인 “다음 CPU 버스트 길이”는 추정에 의존해야 한다. CPU 스케줄링(CPU Scheduling) 미래 시점인 “다음 CPU 버스트 길이”는 추정에 의존해야 한다. 일반적으로, 이전 CPU 버스트 길이와 지수 평균(exponential averaging) 법을 사용한다. tn 값은 가장 최근 정보를 포함한다. n+1은 과거 이력(역사)을 저장한다. 매개변수 는 다음 값의 예측에 있어서 현재와 과거 역사 정보의 상대적 가중치를 제어한다.

다음 CPU 버스트 길이 예측 이 예제에서, 0 = 10,  = ½ CPU 스케줄링(CPU Scheduling) 이 예제에서, 0 = 10,  = ½ 1 =  x t0 + (1 – ) x 0 = ½ x 6 + ½ x 10 = 8 2 =  x t1 + (1 – ) x 1 = ½ x 4 + ½ x 8 = 6

지수 평균(Exponential Averaging) 예제 CPU 스케줄링(CPU Scheduling)  = 0 n+1 = n = n-1 = n-2 = … = 0 최근 역사는 전혀 고려하지 않는다. (첫 번째 CPU 버스트 길이가 계속 사용된다.)  = 1 n+1 =   tn 단지 실제 마지막 CPU 버스트 길이만 고려한다. 공식을 확장하여 다음과 같이 일반화할 수 있다. n+1 =   tn + (1 – )  tn - 1 + … + (1 – )j   tn -j + … + (1 – )n +1  0 와 (1 – ) 모두 1보다 작거나 같다.  각 연속적인 항은 전임자보다 더 작은 가중치를 갖게 된다.

우선 순위 스케줄링(Priority Scheduling) CPU 스케줄링(CPU Scheduling) 우선 순위(점수)는 각 프로세스와 관련이 있다. CPU는 가장 높은 우선 순위를 갖는 프로세스에게 할당된다. (일반적으로, 가장 작은 점수 = 0 = 가장 높은 우선 순위) 선점 방식(preemptive): 기존 진행 중인 것을 중지하고 수행된다. 비선점 방식(non-preemptive): 기존 것은 계획대로 수행되고, 다음 차례에 끼어든다. SJF는 우선 순위가 (예측한) 다음 CPU 버스트가 되는 우선 순위 스케줄 링의 한 방법이다. 문제점: 기아(starvation) 낮은 우선 순위를 갖는 프로세스는 결국 수행되지 못할 수도 있다. (예: 1973년 MIT에서 IBM 7904를 폐쇄할 때, 1967년에 입력된 프로세스가 대기 중 이었음) 해결책: 노화(aging) – 시간이 지나면 프로세스의 우선 순위를 높여준다.

비선점 우선 순위 스케줄링 예제 비선점 우선 순위 스케줄링 CPU 스케줄링(CPU Scheduling) 비선점 우선 순위 스케줄링 평균 대기 시간 = (0 + 1 + 6 + 16 + 18)/5 = 8.2

라운드 로빈 스케줄링(Round Robin Scheduling) CPU 스케줄링(CPU Scheduling) 각 프로세스는 작은 단위의 CPU 시간(time quantum or time slice)을 얻 는다.  보통 10-100 밀리세컨드이다 이 시간이 지난 후, 타이머 인터럽트에 의해 이 프로세스는 실행이 중단 되고, 준비완료 큐의 맨 마지막에 추가된다 만약 n개의 프로세스가 준비완료 큐에 있고, 시간 퀀텀이 q라면, 각 프로세스는 CPU 시 간의 1/n 을 얻는다. 시간 단위가 q이므로 한 번씩 수행되는데 최대 n  q 시간 단위가 소비된다. 어떤 프로세스도 (n–1)  q 시간 단위 이상 기다리지 않는다. 성능은 시간 퀀텀 q의 크기에 따라 달라질 수 있다. 만일 q가 크다면, 라운드 로빈은 FIFO와 같아진다. 반대로, q가 작다면, 높은 병렬성을 제공하여 각 프로세스는 1/n 속도로 수행되는 자신 의 프로세서를 가진 것과 같으나, 잦은 문맥 전환으로 오히려 성능이 저하될 수 있다. 경험적으로, CPU 버스트의 80%는 시간 퀀텀보다 짧아야 한다.

라운드 로빈 스케줄링 예제 (시간 퀀텀 = 20) Gantt Chart CPU 스케줄링(CPU Scheduling) Gantt Chart 전형적으로, SJF보다 평균 총 처리 시간은 길지만, 반응성(response)은 더욱 좋다.

RR에서 시간 퀀텀과 문맥 전환 시간 예를 들어, 어떤 프로세스가 10 시간 단위를 필요로 한다 할 때, CPU 스케줄링(CPU Scheduling) 예를 들어, 어떤 프로세스가 10 시간 단위를 필요로 한다 할 때, 타임 퀀텀이 12 시간 단위인 경우가 1시간 단위보다 더 빨리 끝난다.  문맥 전환에 들어가는 시간 때문 타임 퀀텀이 6 시간 단위이면 1번, 1시간 단위이면 9번의 문맥 전환이 발생한다.

RR에서 문맥 전환 오버헤드 CPU 스케줄링(CPU Scheduling) 당연히, 시간 퀀텀 q는 문맥 전환 시간에 비해 커야 한다.  그렇지 않으면 문맥 전환 오버헤드로 인해 성능이 크게 저하된다. 만약 문맥 전환 시간이 시간 퀀텀의 10%라면, CPU 시간의 약 10%가 문 맥 전환에 소비되는 것이다. 대부분의 현대 운영체제는 시간 퀀텀 값이 10-100 밀리세컨드 범위이고, 문맥 전환 시간은 10마이크로세컨드 미만이다.

총처리 시간 vs 시간 퀀텀 - 참조 총처리 시간(turnaround time)은 시간 퀀텀 크기에 따라 달라진다. CPU 스케줄링(CPU Scheduling) 총처리 시간(turnaround time)은 시간 퀀텀 크기에 따라 달라진다. RR과 SJF가 사용될 때, 시간 퀀텀이 6 혹은 7이라면, 평균 총처리 시간 = 10.5 시간 퀀텀이 1이라면, 평균 총처리 시간 = 11.0

다단계 큐 스케줄링(Multilevel Queue Scheduling) (1/2) CPU 스케줄링(CPU Scheduling) 준비 완료 큐는 복수의 개별적인 큐로 나누어질 수 있다. 포그라운드(foreground) 작업을 위한 큐 – 대화형(interactive) 처리에 적합 백그라운드(background) 작업을 위한 큐 – 일괄 처리(batch) 처리에 적합 프로세스들은 유형, 특징에 따라 하나의 큐에 고정적으로 할당된다. 큐들 사이의 스케줄링도 필요하다. 고정 우선 순위 스케줄링(fixed priority scheduling): 우선 순위 높은 큐의 프로세스들이 (무조건) 먼저 수행된다. 타임 슬라이스 스케줄링(time slice scheduling): 각 큐에 일정량의 CPU 시간을 부여한다. 예를 들어, 포그라운드에 80%, 백그라운드에 20%의 CPU 시간을 부여한다.

다단계 큐 스케줄링(Multilevel Queue Scheduling) (2/2) CPU 스케줄링(CPU Scheduling) 다섯 개 큐로 구성된 사례

다단계 피드백 큐(Multilevel Feedback Queue) CPU 스케줄링(CPU Scheduling) 각 프로세스는 여러 큐 사이를 이동할 수 있다. 예를 들어, 어떤 프로세스가 CPU를 너무 많이 사용하면, 낮은 순위의 큐로 이동한다. 노화(aging)가 이 방식으로 구현될 수도 있다. 다단계 피드백 큐 스케줄러는 아래 매개 변수에 의해 정의된다. 큐의 개수 각 큐의 스케줄링 알고리즘 프로세스가 높은 우선 순위 큐로 이동할 시기를 결정하는 방법 프로세스가 낮은 우선 순위 큐로 이동할 시기를 결정하는 방법 프로세스가 서비스를 요청할 때, 그 프로세스가 들어갈 큐를 결정하는 방법

다단계 피드백 큐 예제 세 개의 큐 스케줄링 예제 Q0 – 8밀리세컨드의 퀀텀을 가진 RR CPU 스케줄링(CPU Scheduling) 세 개의 큐 Q0 – 8밀리세컨드의 퀀텀을 가진 RR Q1 – 16밀리세컨드의 퀀텀을 가진 RR Q2 – FCFS 스케줄링 예제 새로운 프로세스가 RR 방식으로 동작하는 큐 Q0에 들어온다. 이 프로세스가 CPU를 획득하면, 8밀리세컨드 동안 서비스를 받는다. 만약 8밀리세컨드 내 에 종료되지 못했다면, 그 작업은 큐 Q1으로 이동한다. Q1에서 그 프로세스가 다시 RR 방식으로 서비스를 받아 16밀리세컨드 동안 CPU를 사용 한다. 만약 그 이후에도 완료되지 않았다면, 다시 CPU를 내어주고 큐 Q2로 이동한다. 이 프로세스는 Q2에서 선입선출(FCFS) 방식으로 서비스 된다.

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

스레드 스케줄링(Thread Scheduling) CPU 스케줄링(CPU Scheduling) 사용자 수준(user-level)과 커널 수준(kernel-level) 스레드로 구분 다대일, 다대다 모델에서, 스레드 라이브러리(thread library)는 사용자 수 준 스레드를 LWP에서 동작하도록 스케줄한다. 이 경우, 스케줄링 경쟁이 프로세스 내에서 발생하기 때문에, 프로세스-경쟁 범위 (process-contention scope: PCS)라 부른다. (라이브러리에서 수행되므로, 사실 커널은 사용자 수준 스레드의 존재를 알지 못한다.) 커널 스레드는 가용한 CPU에 스케줄 되는데, 시스템 내 모든 스레드들을 대상으로 경쟁이 있으므로, 이를 시스템-경쟁 범위(system-contention scope: SCS)라 부른다.

Pthread 스케줄링 스레드 생성 시, PCS 혹은 SCS를 지정하는 API를 제공한다. API 호출 예제 CPU 스케줄링(CPU Scheduling) 스레드 생성 시, PCS 혹은 SCS를 지정하는 API를 제공한다. PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하여 스레드들을 스케줄한다. PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용하여 스레드들을 스케줄한다. API 호출 예제 /* set the scheduling algorithm to PROCESS or SYSTEM */ pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

멀티 프로세서 스케줄링 (1/2) 멀티 CPU 환경에서는 CPU 스케줄링이 보다 복잡해진다. CPU 스케줄링(CPU Scheduling) 멀티 CPU 환경에서는 CPU 스케줄링이 보다 복잡해진다. 동일 기능 프로세서(homogeneous processor)인 경우를 고려한다. 두 가지 스케줄링 접근법이 있다. 비대칭 다중처리(asymmetric multiprocessing): 오직 한 프로세서만 시스템 자료 구조에 접근한다.  자료 공유의 필요성을 감소시키므로 단순하다. 대칭 다중처리(symmetric multiprocessing: SMP): 각 프로세서는 스스로 스케줄링 한다. 공통의 준비완료 큐를 갖거나, 각자 고유(private)의 준비완료 큐를 가질 수 있다. 현대 운영체제는 대부분 SMP를 지원한다.

멀티 프로세서 스케줄링 (2/2) 프로세서 친화성(processor affinity): 프로세스의 프로세서 이주 정도 CPU 스케줄링(CPU Scheduling) 프로세서 친화성(processor affinity): 프로세스의 프로세서 이주 정도 프로세스가 수행될 때는 프로세서(CPU)의 캐시에 올라가므로, 프로세서를 이주하는 것 은 상당한 비용이 드는 작업이다. 약한 친화성(soft affinity): 가급적 동일 프로세서에서 수행하려 하나, 이주할 수도 있다. 강한 친화성(hard affinity): 시스템 호출을 사용하여, 어떤 프로세스는 처리기 사이를 이 주하지 않는다고 명시할 수 있다. NUMA(Non-Uniform Memory Access) 구조인 경우, 프로세서 친화성을 더욱 잘 고려할 필요가 있다.

부하 균등화(Load Balancing) CPU 스케줄링(CPU Scheduling) SMP 시스템에서 여러 프로세서를 최대한 활용하려면 부하를 모든 처리 기에 균등하게 배분하는 것이 중요하다. 하나의 공통 준비완료 큐를 사용하면 부하 균등화가 용이하다. 반면에, SMP를 지원하는 현대 운영체제에서는 각 프로세서가 개별적인 준비완료 큐를 가지고 있다. SMP 구조에서 부하 균등화 접근법 Push 이주(migration): 바쁜 프로세서가 덜 바쁜 프로세서에게 프로세스를 push한다. Pull 이주: 덜 바쁜 프로세서가 바쁜 프로세서로부터 프로세스를 pull한다.

강의 목차 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약 CPU 스케줄링(CPU Scheduling) 기본 개념 스케줄링 기준 스케줄링 알고리즘 스레드 스케줄링 멀티 프로세서 스케줄링 요약

요약 (1/3) CPU 스케줄링은 준비완료 큐에서 기다리는 프로세스를 선택하여 CPU를 할당해주는 작업이다. CPU 스케줄링(CPU Scheduling) CPU 스케줄링은 준비완료 큐에서 기다리는 프로세스를 선택하여 CPU를 할당해주는 작업이다. 디스패처(dispatcher)에 의해 CPU는 선택된 프로세스에게 할당된다. 선입 선처리(FCFS) 스케줄링은 간단하지만 짧은 작업의 프로세스가 오래 기다리는 단점이 있다. 최단 작업 우선(SJF) 스케줄링은 가장 짧은 평균 대기 시간을 제공하는 최적의 방법이다. 그러나 다음 CPU 버스트를 예측하기가 쉽지 않다. 우선 순위(priority) 스케줄링은 우선 순위가 높은 프로세스에게 CPU를 할당한다. 우선 순위와 최단 작업 우선 스케줄링은 둘 다 기아(starvation) 문제를 발생시킬 수 있다.  노화(aging) 기법이 기아를 막을 수 있는 방법이다.

요약 (2/3) CPU 스케줄링(CPU Scheduling) 라운드 로빈(round robin: RR) 스케줄링은 시분할 시스템(time-sharing system)에 보다 적합하다. RR 방식의 주요 이슈는 시간 퀀텀(time quantum)의 크기 결정이다 선점(preemptive), 비선점(non-preemptive) 측면에서 보면, FCFS 스케줄링 방식은 비선점이고, RR 방식은 선점이다. SJF 스케줄링과 우선 순위 스케줄링은 선점과 비선점 방식이 모두 가능하다. 다단계 큐(multilevel queue)는 각 큐별로 다른 스케줄링 알고리즘을 적 용하는 것이 가능하다. 다단계 피드백 큐(multilevel feedback queue)는 프로세스가 하나의 큐 에서 다른 큐로 이동하는 것이 가능하다.

요약 (3/3) 스레드 스케줄링은 크게 두 가지 방식이 있다. CPU 스케줄링(CPU Scheduling) 스레드 스케줄링은 크게 두 가지 방식이 있다. PCS(process-contention scope): 사용자 수준 스레드를 LWP에 스케줄링한다. SCS(system-contention scope): 커널 스레드를 CPU에 스케줄링한다. 멀티 프로세서 스케줄링에서는 여러 프로세스들이 여러 프로세서(코어) 에 의해 처리된다. 대개 SMP 방식으로 지원된다. (각 프로세서는 공통 혹은 개별 준비완료 큐를 갖는다.) 캐시 사용, NUMA 구조 등에 의한 프로세서 친화성(processor affinity) 이슈가 있다. 프로세서들 간 부하 분배를 위한 부하 균등화(load balancing) 이슈가 있다.