5장: 프로세스 스케줄링

5장: 프로세스 스케줄링 기본 개념 스케줄링 기준(Criteria) 스케줄링 알고리즘 다중 프로세스 스케줄링 실시간 스케줄링 쓰레드 스케줄링

기본 개념 프로세스 스케줄링은 용어(Terminology) 다중 프로그램 운영체제의 기본이다 CPU 스케줄링, 프로세스 스케줄링, 커널 쓰레드 스케줄링 번갈아 가며 사용된다, 우리는 프로세스 스케줄링이라는 용어를 사용한다

기본 개념 단일 프로세서 시스템에서 프로세스 스케줄링은 최대 CPU 이용률은 다중 프로그래밍에 의해 가능하다 한번에 오직 하나의 프로세스만 수행된다 다른 프로세스들은 CPU가 자유로워져 재스케줄 될 수 있을 때까지 기다린다 수행중이던 프로세스가 대기 상태로 이동할 때, 운영체제는 CPU의 이용률을 향상시키기 위하여 CPU를 할당할 다른 프로세스를 선택할 수도 있다 하나의 프로세스가 기다리는 순간, 다른 프로세스는 CPU를 양도 받아 사용할 수 있다 프로세스 스케줄링은 운영체제의 기본적인 역할이다 준비 큐에 있는 하나의 프로세스를 선택하여 CPU를 할당한다 최대 CPU 이용률은 다중 프로그래밍에 의해 가능하다 프로세스 스케줄링에 의하여 How to calculate CPU utilization?

프로세스 상태 전이도 (3장) 특정 시점에 어떤 프로세서에서도 수행중인 프로세스는 1개 뿐이라는 것이 중요하다 많은 프로세스들은 준비(ready) 또는 대기(waiting) 상태에 있다

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

CPU - 입출력 버스트 싸이클 프로세스 실행은 다음으로 이루어진다 프로세스는 아래 두 상태를 번갈아 가며 수행한다 CPU 실행(CPU burst)와 입출력 대기(I/O burst) 싸이클 프로세스는 아래 두 상태를 번갈아 가며 수행한다 프로세스 수행은 CPU 버스트로 시작한다, 다음에 입출력 버스트가 뒤따른다 결론적으로, 마지막 CPU 버스트는 실행을 종료하는 시스템 호출로 끝난다 프로세스의 CPU 버스트 분산 프로세스마다 컴퓨터마다 크게 차이가 난다

CPU & 입출력 버스트 교환 순서 CPU 버스트 시간 입출력 버스트 시간

CPU 버스트 시간의 그래프 CPU 버스트 분산은 일반적으로 다음과 같은 특징을 갖는다 기하급수적이거나(hyper-exponential) 많은 수의 짧은 CPU 버스트나 작은 수의 긴 CPU 버스트를 가지고 있다 입출력 종속 프로세스는 많은 수의 짧은 CPU 버스트를 가진다 CPU 종속 프로세스는 몇 개의 긴 CPU 프로세스를 가진다

프로세스 스케줄러 운영체제 모듈의 한 가지이다 실행할 준비가 되어있는 메모리에 있는 프로세스들 중에 하나를 선택하여 선택된 프로세스에게 CPU를 할당한다 CPU 스케줄링 결정은 프로세스가 다음과 같은 경우에 일어날 수 있다: 1. 실행 상태에서 대기 상태로 전환된다: 입출력 요구, 다른 프로세스의 수행을 위한 wait() 함수 호출 2. 수행 상태에서 준비 상태로 전환된다: 인터럽트가 발생할 때 3. 대기 상태에서 준비 상태로 전환된다: 입출력이 끝나면 4. 종료된다 1과 4 수행 중 스케줄링은 비선점(non-preemptive) 방식이다 2와 3 수행 중 스케줄링은 선점(preemptive) 방식이다

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

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

내용 전환(Context Switch) – 3장 Dispatcher latency

스케줄링 기준(Scheduling Criteria) 스케줄링 기준을 기반으로, 다양한 스케줄링 알고리즘에 대한 성능 평가가 이루어질 수 있다 다른 스케줄링 알고리즘은 다른 특성을 가진다 CPU 사용률(utilization) – 단위 시간 당 CPU가 작업을 수행하는 총 시간 비율 (%) 처리량(Throughput ) – 단위 시간 당 실행을 완료한 프로세스 수 총처리 시간(Turnaround time) – 프로세스가 제출된 시간부터 작업을 완료하는 시간까지의 간격, 메모리에 올라가기 까지 기다린 시간, 준비큐에서 대기한 시간, CPU에서 수행되고, 입출력을 수행하는 모든 기간의 합 대기 시간(Waiting time) – 프로세스가 준비 큐에서 대기한 시간의 합계, 이 시간은 스케줄링 알고리즘에 영향을 받는다 반응 시간(Response time) – 대화형 시스템에서, (시분할 환경을 위해서) 요청이 제출되고 첫 번째 반응이 돌아오기까지 (결과 출력은 아니다) 걸리는 시간의 합계

최적화 기준(Optimization Criteria) 다음은 최대화 하는 것이 바람직하다: CPU 사용률(utilization) 처리량(throughput) 다음은 최소화 하는 것이 바람직하다: 총처리 시간(turnaround time) 대기 시간(waiting time) 반응 시간(response time) 그러나 어떤 경우에는, 평균보다 최소값이나 최대값을 최적화하는 것이 바람직하다 대화형 시스템은, 평균 반응 시간을 최소화하는 것보다 반응 시간의 변동량을 최소화하는 것이 더 중요하다

프로세스 스케줄링 알고리즘 선착순 스케줄링(First-Come, First-Served Scheduling: FCFS) 최단기 작업 최우선 스케줄링(Shortest-Job-First Scheduling: SJF) 우선순위 스케줄링(Priority Scheduling) 순차 순환 대기 방식 스케줄링(Round-Robin Scheduling) 스케줄링 알고리즘의 비교를 위한 측정 요소는 평균대기 시간이다 CPU 사용률(utilization), 처리량(throughput), 총처리 시간(turn around time),

선착순(FCFS) 스케줄링 프로세스 버스트 시간 P1 24 P2 3 P3 3 프로세스가 다음 순서로 도착했다고 가정하자: P1 , P2 , P3 스케줄링을 위한 간트 도표(Gantt Chart): 프로세스별 대기 시간 P1 = 0; P2 = 24; P3 = 27 평균 대기 시간: (0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 30 Q: Is it preempted or non-preempted? Q: CPU utilization, Throughput, waiting time, turnaround time

FCFS 스케줄링 프로세스들이 다음과 같은 순서로 도착했다고 가정하자 P2 , P3 , P1 스케줄링을 위한 간트 도표(Gantt Chart): 프로세스별 대기 시간 P1 = 6; P2 = 0; P3 = 3 평균 대기 시간: (6 + 0 + 3)/3 = 3 이전 경우보다 성능이 향상 됨 P1 P3 P2 6 3 30 P0 ( 5, 10, 10) P1 (5, 20, 10) P3 (5, 30, 10)

FCFS 스케줄링 P0 P1 P2 CPU (10) I/O (20) CPU(11) CPU(6) I/O(17) CPU(9) 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 스케줄링 선착순 스케줄링 알고리즘은 비선점 방식이다 호송 효과(Convoy effect)가 발생한다 일단 CPU가 프로세스에게 할당이 되면, 그 프로세스가 종료되거나 입출력을 요구하는 등 CPU를 놓을 때까지 CPU를 잡고 있는다 특별히 시분할 시스템에서는 문제가 된다 호송 효과(Convoy effect)가 발생한다 긴 CPU 버스트를 가진 하나의 CPU 종속 프로세스와 짧은 CPU 버스트를 가진 많은 입출력 종속 프로세스가 순서대로 수행되고있을 때 모든 입출력 종속 프로세스는 입출력 장치들이 놀고 있으면서 CPU 종속 프로세스가 CPU를 놓을 때까지 기다린다 모든 입출력/CPU 종속 프로세스들은 CPU가 놀고 있으면서 입출력 연산을 수행한다 결론적으로 낮은 CPU와 장치 사용률을 보인다

단기 작업 최우선(SJF) 스케줄링 각 프로세스들은 다음 CPU 버스트 길이와 관계된다 가장 짧은 시간을 가진 프로세스를 스케줄 하는데 이 시간을 사용한다 두 가지 방법: 비선점(non-preemptive) – 일단 CPU가 하나의 프로세스에게 주어지면, 그 프로세스가 CPU 버스트를 완료할 때까지 CPU를 내놓지 않는다 선점(preemptive) – 만약 도착한 프로세스의 CPU 버스트 길이가 현재 수행중인 프로세스의 남은 CPU 버스트 길이보다 짧다면, 현재 수행중이던 프로세스는 CPU를 내어준다. 이 방법이 잔여 단기 작업 최우선(Shortest-Remaining-Time-First: SRTF) 알고리즘이다 SJF은 최적이다 – 주어진 프로세스 집합에 최소의 평균 대기 시간을 제공한다

비선점 SJF 예 프로세스 도착시간 버스트 시간 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 프로세스 도착시간 버스트 시간 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (비선점) 평균 대기 시간 = (0 + 6 + 3 + 7)/4 = 4 P1 P3 P2 7 3 16 P4 8 12

선점 SJF 예 프로세스 도착 시간 버스트 시간 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 프로세스 도착 시간 버스트 시간 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (선점) 평균 대기 시간 = (9 + 1 + 0 +2)/4 = 3 P1 P3 P2 4 2 11 P4 5 7 16 Q: CPU utilization, Throughput, waiting time, turnaround time

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

비선점 SJF 스케줄링 P0 P1 P2 10 20 30 40 50 CPU (10) I/O (20) CPU(11) CPU(6) 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 버스트 길이와 기하급수 평균법을 사용하여 구한다 tn 값은 가장 최근 정보를 포함한다 n+1은 과거 이력(역사)을 저장한다 매개변수 는 다음 값의 예측에 있어서 현재와 과거 역사 정보의 상대적 가중치를 제어한다

다음 CPU 버스트 길이 예측 이 예제에서, 0 = 10,  = ½ 1 =  x t0 + (1- ) x 0 = ½ x 6 + ½ x 10 = 8 2 =  x t2 + (1- ) x 2 = ½ x 4 + ½ x 8 = 6

기하 급수 평균법 예제  = 0  = 1 만약 우리가 공식을 확장한다면, 우리는 다음과 같은 값을 얻을 수 있다: n+1 = n = n-1 = n-2 . … = 0 최근 역사는 전혀 고려하지 않는다  = 1 n+1 =  tn 단지 실제 마지막 CPU 버스트만 고려한다 만약 우리가 공식을 확장한다면, 우리는 다음과 같은 값을 얻을 수 있다: n+1 =  tn + (1 - ) tn - 1 + … + (1 -  )j  tn -j + … + (1 -  )n +1 0 와 (1 - ) 모두 1보다 작거나 같기 때문에, 각 연속적인 항은 전임자보다 더 작은 가중치를 갖게 된다

우선 순위 스케줄링 우선 순위(정수)는 각 프로세스와 관련있다 CPU는 가장 높은 우선 순위를 갖는 프로세스에게 할당된다 (가장 작은 정수  가장 높은 우선 순위) 선점 방식(Preemptive) 비선점 방식(Non-preemptive) SJF는 우선순위가 예측한 다음 CPU 버스트가 되는 우선순위 스케줄링 방법이다 문제점  기아(Starvation) – 낮은 우선순위를 갖는 프로세스는 결코 실행되지 않을 수도 있다 해결책  노화(Aging) – 시간이 지나면, 프로세스의 우선순위를 높여준다

비선점 우선순위 예 프로세스 버스트 시간 우선순위 P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 프로세스 버스트 시간 우선순위 P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 우선순위 스케줄링 (비선점) 평균 대기 시간 = (0 + 1 + 6 + 16 + 18)/5 = 8.2 P2 P5 P1 P3 P4 16 1 6 18 19

선점 우선 순위 스케줄링 P0(1) P1(2) P2(3) CPU (10) I/O (20) CPU(11) CPU(6) 10 20 30 40 50 I/O(24) P0 CPU(10) P2 P1 Idle: P2(I/O4) I/O(2) P1 CPU(9) 원래 I/O에는 idle이 들어가야 합니다

이 경우는 특수 case로 preemptive나 non-preemptive나 답이 같습니다. (즉 앞장과 답이 같습니다.) 비선점 우선 순위 스케줄링 10 20 30 40 50 P0 (1) CPU (10) I/O (20) CPU(11) P1 (2) CPU(6) I/O(17) CPU(9) P2 (3) CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) 이 경우는 특수 case로 preemptive나 non-preemptive나 답이 같습니다. (즉 앞장과 답이 같습니다.)

순차 순환 대기 방식 스케줄링 각 프로세스는 작은 단위의 CPU 시간을 얻는다(time quantum), 보통 10-100 밀리세컨드이다 이 시간이 지난 후에, 프로세스는 놓여지고, 준비 큐의 맨 마지막에 추가된다 만약 n개의 프로세스가 준비 큐에 있고 시간 퀀텀(time quantum) 값이 q라면, 각 프로세스는 CPU 시간의 1/n 을 얻는다. 시간 단위가 q이므로 한 번씩 수행되는데 최대 n x q 시간 단위가 소비된다 어떤 프로세스도 (n-1) x q 시간 단위 이상 기다리지 않는다 성능은 시간 퀀텀 크기에 달려 있다 q가 크면  RR은 FIFO와 같다 q가 작으면  높은 병렬성을 제공한다: n개의 각 프로세스는 실제 프로세서의 1/n 속도로 수행되는 각자의 프로세스를 가진 것과 같다

시간 퀀텀 값이 20인 RR 예제 프로세스 버스트 시간 P1 53 P2 17 P3 68 P4 24 간트 도표: 프로세스 버스트 시간 P1 53 P2 17 P3 68 P4 24 간트 도표: 전형적으로, SJF보다 평균 총처리 시간은 길지만, 반응성은 더 좋다 P1 P2 P3 P4 20 37 57 77 97 117 121 134 154 162

RR 스케줄링 Time Quantum = 2 (9번째 P1과 10번째 P2는 바뀌어도 상관 없음) 10 20 30 40 50 P0(1) CPU (10) I/O (20) CPU(11) P1(2) CPU(6) I/O(17) CPU(9) P2(3) CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) P0 CPU(2) P2 CPU(2) P0 CPU(2) P1 CPU(2) P2 CPU(2) P0 CPU(2) P1 CPU(2) P0 CPU(2) P1 CPU(2) P2 CPU(2) P0 CPU(2) P2 CPU(2) Idle P1 I/O (11) P1 CPU(2) P1 CPU(2) P1 CPU(2) P1 CPU(2) P0 CPU(2) P1 CPU1) P0 CPU(2) P0 CPU(2) P2 CPU(2) P0 CPU(2) P2 CPU(2) P0 CPU(2) P0 CPU(1) Time Quantum = 2 (9번째 P1과 10번째 P2는 바뀌어도 상관 없음) (20번째 P0와 21번째 P2도 바뀌어도 상관 없음)

RR 스케줄링 Time Quantum = 5 P0(1) P1(2) P2(3) 10 20 30 40 50 CPU (10) 10 20 30 40 50 P0(1) CPU (10) I/O (20) CPU(11) P1(2) CPU(6) I/O(17) CPU(9) P2(3) CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) P0 CPU(5) P2 CPU(4) P1 CPU(5) P0 CPU(5) P2 CPU(4) P1 CPU(1) Idle P1 I/O(15) P0 CPU(5) P1 CPU(5) P0 CPU(5) P2 CPU(4) P1 CPU(4) P0 CPU(1) Time Quantum = 5

시간 퀀텀과 내용 전환 시간 RR 스케줄링의 성능에 대한 내용 전환 효과, 예를 들면 10 타임 퀀텀을 갖는 하나의 프로세스는 퀀텀 = 12 시간 단위, 1 시간 퀀텀 보다 더 빨리 끝난다 퀀텀 = 6시간 단위, 2개의 퀀타가 필요하고, 1번의 내용전환이 일어남 퀀텀 = 1시간 단위, 10개의 퀀타가 필요하고, 9번 내용전환이 일어남

순차 순환 대기 방식 알고리즘 시간 퀀텀 q는 내용 전환에 비해 커야 한다, 그렇지 않으면 내용 전환의 오버헤드가 크다 만약 내용 전환 시간이 시간 퀀텀의 10%라면, CPU 시간의 약 10%가 내용 전환에 소비되는 것이다 대부분의 현대 운영체제는 시간 퀀타 값이 10에서 100 밀리세컨드 범위이다, 내용 전환에 필요한 시간은 전형적으로 10 밀리세컨드 이하이다; 따라서 내용 전환 시간은 시간 퀀텀의 작은 부분이다

총처리 시간은 시간 퀀텀에 따라 다르다 총처리 시간은 시간 퀀텀 크기에 의존한다 평균 총처리 시간은 만약 대부분의 프로세스가 하나의 시간 퀀텀내에서 다음 CPU 버스트를 끝낸다면 향상될 수 있다 SJF와 RR이 사용될 때 만약 퀀텀 = 6과 7이면, 평균 총처리 시간 = 10.5 만약 퀀텀 = 1, 평균 총처리 시간 = 11

다중 큐를 갖는 스케줄링 알고리즘 다중 레벨 큐 스케줄링 다중 레벨 피드백 큐 스케줄링

다중 단계 큐 (Multilevel Queue) 준비 큐는 개별적인 큐로 나뉜다: 전경(foreground) (대화형:interactive) 후경(background) (일괄 처리: batch) 프로세스들은 일반적으로 몇 가지 특징이나 프로세스 유형에 따라 영구적으로 하나의 큐에 할당된다 각 큐는 자신만의 스케줄링 알고리즘을 갖는다 전경(foreground) – RR 후경(background) – FCFS 스케줄링은 큐 사이에서 이루어져야 한다 고정 우선순위 스케줄링(Fixed priority scheduling) – 전경에 있는 모든 프로세스가 처리되고 후경의 프로세스가 처리됨. 기아 발생 가능 시간 부분 스케줄링(Time slice scheduling) – 각 큐는 일정 양의 CPU 시간을 획득하여 프로세스들 사이에 스케줄 되게 한다. 예로, RR 방식의 전경 프로세스: 80%, FCFS 방식의 후경 프로세스: 20%

다중 단계 큐 스케줄링 일괄처리에 있는 어떤 프로세스도 상위 우선순위에 있는 모든 큐가 비어있지 않으면 수행될 수 없다 일괄 처리 프로세스가 수행 중에 대화형 편집 프로세스가 들어오면, 일괄 처리 프로세스는 우선권을 내어준다

다중 단계 큐 스케줄링 두 단계 큐: 우선 순위가 0인 SJF, 우선 순위가 1인 FCFS 고정 우선순위 큐 선점 방식 10 20 30 40 50 P0 (1) CPU (10) I/O (20) CPU(11) P1 (0) CPU(6) I/O(17) CPU(9) P2 (0) CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) 두 단계 큐: 우선 순위가 0인 SJF, 우선 순위가 1인 FCFS 고정 우선순위 큐 선점 방식

다중 단계 피드백 큐 각 프로세스는 다양한 큐 사이를 옮겨 다닐 수 있다; 나이 들기(aging)가 이 방식으로 구현될 수 있다 다중 단계 피드백 큐 스케줄러는 아래 매개 변수에 의해 정의된다: 큐의 개수 각 큐의 스케줄링 알고리즘 프로세스가 개선되는 시기를 결정할 때 사용되는 방법 프로세스가 좌천되는 시기를 결정할 때 사용되는 방법 프로세스가 서비스를 요청할 때, 그 프로세스가 들어가는 큐를 결정할 때 사용되는 방법

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

다중 단계 피드백 큐

다중 단계 피드백 큐 스케줄링 세 단계 큐: 퀀텀 3인 RR, 퀀텀 6인 RR, 우선 순위 1인 FCFS P0 (1) 10 20 30 40 50 P0 (1) CPU (10) I/O (20) CPU(11) P1 (0) CPU(6) I/O(17) CPU(9) P2 (0) CPU(4) I/O(4) CPU (4) I/O(24) CPU (4) 세 단계 큐: 퀀텀 3인 RR, 퀀텀 6인 RR, 우선 순위 1인 FCFS

다중 프로세서 스케줄링 다중 CPU가 제공되면 CPU 스케줄링은 더 복잡하다 하나의 시스템 내의 동일 프로세서나 하나의 시스템 내의 다른 종류의 프로세서 비대칭 다중처리 대 대칭 다중처리(Symmetric multiprocessing: SMP) 대칭 다중처리 (SMP) – 각 프로세서는 자기 자신만의 스케줄링 결정권을 갖는다 비대칭 다중처리 – 데이터 공유의 필요성을 완화하기 위해서 하나의 프로세서만이 시스템의 데이터 구조에 접근한다 SMP 시스템에서의 부하(Load) 공유 작업은 SMP 시스템의 모든 프로세서에게 공평하게 분배된다 Push 이주(migration) 대 Pull 이주(migration)

실시간 스케줄링 강한 실시간(Hard real-time) 시스템 – 주요 임무가 보장된 시간 내에 완료되어야만 한다 약한 실시간(Soft real-time) 컴퓨팅 – 주요 프로세스는 다른 덜 주요한 프로세스보다 우선권을 받도록 한다

쓰레드 스케줄링 커널 레벨 쓰레드를 지원하는 운영체제에서, 운영체제에 의해 스케줄 되는 것은 프로세스가 아니라 커널 레벨 쓰레드 이다 지역 스케줄링(Local Scheduling) – 쓰레드 라이브러리가 어떤 쓰레드에게 가용 LWP를 할당할 것인가를 결정한다 전역 스케줄링(Global Scheduling) – 커널이 다음에 어떤 커널이 수행될 것인가를 결정한다

요약 (1) CPU 스케줄링은 준비 큐에서 기다리고 있는 프로세스를 선 택하여 CPU를 할당해주는 작업이다 디스패처(dispatcher)에 의해 CPU가 선택된 프로세스에게 할당된다 선착순(FCFS) 스케줄링은 간단하나 짧은 작업의 프로세스 가 길게 기다릴 수도 있다 단기 작업 우선(SJF) 스케줄링은 가장 짧은 평균 대기 시간 을 제공하는 최적의 방법이다. 그러나 다음 CPU 버스트를 예측하는 것은 어렵다 우선순위(Priority) 스케줄링은 최우선순위 프로세스에게 CPU를 할당한다 우선순위와 단기 작업 우선 스케줄링 방법은 둘 다 기아로 고 통 받는다. 나이들기(aging)가 기아를 막을 수 있는 방법이다

요약 (2) 순차 순환 대기 방식(RR) 스케줄링은 시분할 시스템(time- shared system)에 더 적합하다 선착순(FCFS) 스케줄링 방식은 비선점이고, 순차 순환 대기 (RR) 방식은 선점이고, 단기 작업 우선(SJF) 스케줄링과 우 선 순위(Priority) 방식은 선점과 비선점 방식이 모두 가능하 다 다중 단계 큐(Multilevel queue)는 각 큐별로 다른 스케줄링 알고리즘을 적용하는 것이 가능하다 다중 단계 피드백 큐(Multilevel feedback queue)는 프로세스 가 하나의 큐에서 다른 큐로 이동하는 것이 가능하다