2.2 CPU 스케줄링의 목적과 유형 2.2.1 스케줄링의 목적 1) 시스템 측면의 목적 ① 모든 프로세스에 대한 공평성(fairness) 유지. ② 처리 능력(throughput)의 극대화. ③ 중요 프로세스에 대해서는 우선 처리(priority)가 가능토록 함. ④ 시스템 내 자원의 공평한 할당.

2) 사용자 측면의 목적 ① 대화식 프로세스의 경우, 응답 시간(response time)이 최소. ② 일괄처리 작업의 경우, ① 대화식 프로세스의 경우, 응답 시간(response time)이 최소. ② 일괄처리 작업의 경우, 반환 시간(turnaround time)이 최소. ③ 처리되는 작업이 무한 대기 (infinite postponement) 되지 않도록. ④ 처리 작업의 완료시간 예측이 가능 하여야 함.

▶ 스케줄링 목적의 상반성 . <예 1> 응답시간의 최소화를 위한 CPU의 계속 할당 ▶ 스케줄링 목적의 상반성 . <예 1> 응답시간의 최소화를 위한 CPU의 계속 할당 은 전체적인 처리 능력이 떨어질 수도 있다. <예 2> 중요 프로세스에 대해 처리의 우선권을 계속 부여하다 보면, 무한 대기되는 프로세스가 나타날 수도 있다.

▶ CPU 스케줄링의 정책을 결정하거나, 스케줄링 알고리즘을 구현할 때의 고려사항 ① 프로세스의 형태? - 일괄 처리 (Batch) 형태인가? 대화형 (TSS) 형태인가? ② 프로세스의 CPU 사용 비율과 I / O 사용 비율? - 연산 위주의 프로세스인가? 또는 I/O 위주의 프로세스인가?

③ 프로세스에게 우선 순위 는 부여하는가? ④ 우선 순위가 높은 프로세스에 의해서 선점(preempt) 되는 빈도는 어떠한가? ⑤ 페이지 부재(page fault)의 발생 빈도는?

2.2.2 CPU 스케줄링의 3가지 유형 ■ 장기, 중기, 단기 : 그 기능이 수행되는 주기가 짧은가(단기), 긴가(장기), 그 중간 정도의 주기( 중기)인 가에 따라서 붙인 것임. ▶ 장기 스케줄링 (long-term scheduling) ▶ 중기 스케줄링 (medium-term scheduling) ▶ 단기 스케줄링 (short-term scheduling)

■ 장기 스케줄링 ■ 중기 스케줄링 ■ 단기 스케줄링 ▶ 상위 단계(high-level) 스케줄링, ■ 장기 스케줄링 ▶ 상위 단계(high-level) 스케줄링, ▶ 작업 스케줄링 (job scheduling) 이라고도 함. ▶ “어떤 작업”이 시스템에 들어와서 처리될 것인가를 결정 하고, 해당 작업을 주기억 공간으로 적재하는 일을 담당. ■ 중기 스케줄링 ▶ 중간 단계 (intermediate-level) 스케줄링 ▶ “연기된 대기와 연기된 준비” 등의 교체 작업” (Swap in 또는 Swap out) 을 담당. ■ 단기 스케줄링 ▶ 하위 단계 (low-level) 스케줄링 ▶ “준비, 실행, 대기”의 기본적 상태 전이 를 담당.

(그림 2.10) CPU 스케줄링의 3가지 유형과 단계 장 기 중 기 단 기 RUN (실행) READY (준비) NEW (생성) EXIT (종료) BLOCK (대기) SUSPENDED BLOCK (연기된 대기) SUSPENDED READY (연기된 준비)

1) 장기 스케줄링 ▶ 일괄 처리되는 작업들은 CPU의 처리 능력과 관계없이, 실제로 시행이 되기 전에 디스크와 같은 보조기억 장치에 저장(Spooling 개념) 됨. ▶ 장기 스케줄러(Long-term Scheduler)는 보조기억 장치에 저장되어, 처리를 원하는 여러 작업들 중에서 어떤 작업을, 몇 개나 주기억 장치에 적재 시킬 것인가를 담당.

▶ 장기 스케줄러는 시스템의 다중 프로그래밍의 정도를 담당. ▶ 어떤 작업이 장기 스케줄러에 의해서 받아들여 졌다는 것은 , 그 작업이 하나의 프로세스가 되어 "단기 스케줄러(short-term scheduler)의 준비 큐 (ready queue)” 에 들어 갔다는 것을 의미함. JOB 큐 NEW 큐 준비 큐 (READY)

▶ 일부의 시스템의 경우, 새롭게 생성된 프로세스를 "교체 (swap out)의 의미를 갖고 있는 연기된 준비 큐"에 넣어 두기도 함. ▶ 대화형 처리(interactive job)를 하는 시분할 시스템(TSS)의 경우는 대부분 장기 스케줄러가 없으며, 발생되는 프로세스를 단지 준비 큐에 넣어 주는 역할만 하게 됨.

▶ 프로세스의 선택에 100만분의 수초 단위로 선택하는 단기 스케줄러에 비해 작업의 선택 시간이 아주 긴 주기임. ▶ 시스템에 새롭게 들어 오는 “작업의 시간 주기” 는 분 단위이며, 하나의 작업이 시스템을 빠져 나갈 때 (종료 상태에서 해제시)에만 장기 스케줄러가 작동되어, 새로운 작업을 선택하여 시스템 내에 적재 시키게 됨.

2) 중기 스케줄링 ▶ 프로세스를 교체하여 주기억 공간 내에 들어오게 하거나(swap in), 나가게 하는(swap out) 일을 담당. ▶ 프로세스를 주기억 장치로부터 빼낼 수 있기 때문에, 필요한 경우에 다중 프로그래밍의 정도를 낮출 수 있음. (시스템의 처리 효율 중시) ▶ 교체 작업의 효과 : 교체되어 나간 프로세스가 소유하던 모든 자원(예 : 주기억 공간 등)을 다른 프로세스가 사용할 수 있게 해주는 효과를 기대.

3) 단기 스케줄링 ▶ 분배기(dispatcher)라고도 함. 주기억 장치 내의 준비 상태에 들어와 있는 프로세스들 중에서 다음에 실행시킬 프로세스를 선택하여 CPU를 할당 시켜 주는 일을 담당. ▶ CPU를 사용하고 있는 프로세스가 연기(suspension)나, 선점(preemption)을 당하는 경우에, 다음에 CPU를 할당 시킬 프로세스를 선택해 주는 일을 시작하게 됨. ( 대기 로 갈 때 포함)

CPU의 사용시간 초과(time out), I/O 인터럽트, ▶ 프로세스의 선점이나 연기의 요인 CPU의 사용시간 초과(time out), I/O 인터럽트, OS나 오퍼레이터의 요청 등. ▶ 단기 스케줄러는 CPU의 할당 작업과 관련하여, 해당 프로세스가 갖고 있는 프로세스 제어 블록(PCB)의 정보 적재와 사용자 모드(user mode)로의 전환 작업 등도 담당함.

CPU 스케줄링의 큐 모형 예 CPU “단기 스케줄러 담당” 준비(Ready) 큐 일괄 작업 큐 종료 (EXIT) 일괄 처리 연기된 준비 큐 대화형 작업 * 참고 : 연기된 대기 큐 선은 중기 스케줄러가 담당함. “장기 스케줄러 담당” 대기(Block) 큐

2.3 비선점 단기 스케줄링 알고리즘 2.3.1 선점과 비선점의 개념 2.3 비선점 단기 스케줄링 알고리즘 2.3.1 선점과 비선점의 개념 ■ 선점(preemption) : 어떤 프로세스가 CPU를 사용하고 있을 때, 그보다 높은 우선 순위를 갖는 프로세스에게 CPU를 양보함(선점 당함). ▶ 대화형으로 처리되는 “시분할 시스템” 일정시간이 지나면 무조건 다른 프로세스에게 CPU의 사용을 양보하므로 근본적으로 "선점 알고리즘"을 사용하는 시스템이라고 할 수 있음.

■ 비선점(non-preemption)의 의미 : ▶ 문맥 교환, 상황교환 선점의 경우에는 CPU의 사용을 일시 중단하고, 다른 프로세스에게 CPU의 사용권을 넘겨주므로, 지금까지 수행한 모든 내용들을 보관하여 둔 후, 새로 시작되는 프로세스와 관련된 내용을 시스템에 새로 적재 시켜 주어야 함. < Context Switching > 많은 시간과 경제적 손실 (overhead) ■ 비선점(non-preemption)의 의미 : 하나의 프로세스가 CPU를 할당 받은 후에는, 스스로 CPU를 반납할 때까지 다른 프로세스가 CPU를 선점할 수 없는 것.

▶ 비선점 방식의 잇점 CPU를 할당 받은 순서대로 차례차례 처리되는 공정성, 대기중인 프로세스와 관계없이 응답 시간 예측 가능성. ▶ 비선점 방식의 문제점 1) CPU의 사용시간이 짧은 프로세스들이 사용시간이 긴 프로세스들로 인하여 오래 기다리게 되는 문제. 2) 무한대기 : 어떤 프로세스가 오류로 인하여 CPU 를 계속 사용하게 될 때, 발생.

2.3.2 FCFS(First Come First Service) 알고리즘 ■ 가장 간단한 기법의 비선점 스케줄링 알고리즘. FIFO(First In First Out) 알고리즘 이라고도 함. ▶ 프로세스가 준비 큐에 도착한 순서에 따라 CPU를 할당 받게 되고, 일단 CPU를 차지하고 난 후에는 그 프로세스가 CPU를 반납할 때까지, 다른 프로세스가 CPU를 선점할 수 없게 됨.

^ ▶ 준비 큐(ready queue)는 FIFO 큐 의 형태 준비 큐 실행 CPU 선택 가장최근에 들어온 프로세스 가장 먼저 PCB3 PCB2 PCB1 선택 가장최근에 들어온 프로세스 가장 먼저 들어온 프로세스

▶ 모든 프로세스를 동등하게 취급하는 공평성을 가짐 ▶ 작업의 완료시간을 예측하기가 용이함 ▶ 각 프로세스 간에 있어서 응답 시간의 차이가 적어짐 <문제점> CPU의 사용이 아주 긴 프로세스가 CPU를 먼저 할당 받은 경우 : 짧은 CPU 사용을 요구하는 프로세스들이 오래 기다리게 됨. - FCFS 알고리즘은 CPU의 사용이 긴 프로세스에게 유리한 알고리즘임.

■ 다음 표에서 ‘ CPU 반환시간 / CPU 요구시간 ‘ 의 비는 프로세스 1과 프로세스 2는 1 이 되며, 프로세스 3은 10, 프로세스 4는 1.9가 된다. ( 편차가 큼 )

4.3.2 FCFS 알고리즘(계속) ▶ 평균 반환시간 : Ta = ( Ti) / n ▶ 대화식 시스템에는 부적합. 실제의 적용은 다른 스케줄링 알고리즘에 보조적으로 사용 ■ 반환 시간(turn-around time)과 평균 반환 시간. ▶ Pf 는 프로세스 종료시간, Pa 는 프로세스 도착시간, Ps 는 CPU 시작시간, n 은 프로세스의 수. ▶ 반환 시간 : T = Pf - Pa ▶ 대기 시간 : W = Ps - Pa ▶ 평균 반환시간 : Ta = ( Ti) / n ▶ 평균 대기시간 : Tw = ( Wi) / n 4.3.2 FCFS 알고리즘(계속) n  i=1 n  i=1

■ CPU 사용 요구시간을 알고 있는 4개의 프로세스에 대한 평균 반환시간과 평균 대기시간의 계산. [예 1] 처리 순서 : P1(26)  P2(3)  P3(4)  P4(5) 대기시간 25 27 30 P1 0 1 2 3 26 P1 종료 29 P2 종료 33 P3 종료 38 P4 종료 대기시간(27) 대기시간(25) 처리시간(26) 대기시간(30) 처리시간(3) 처리시간(4) 처리시간(5) P2 P3 P4 평균 반환시간 = (26 + 28 + 31 + 35) / 4 = 30.0 평균 대기시간 = (0 + 25 + 27 + 30) / 4 = 20.5

[예 2] 처리 순서 : P2(3)  P3(4)  P4(5)  P1(26) 대기시간 2 5 9 P2 처리시간(3) 대기시간(2) 처리시간(4) P3 대기시간(5) 처리시간(5) P4 P1 대기시간(9) 처리시간(26) 0 1 2 3 P2종료 7 P3종료 12 P4종료 38 P1종료 평균 반환시간 = (3 + 6+ 10+ 35) / 4 = 13.5 평균 대기시간 = (0 + 2 + 5 + 9) / 4 = 4.0

▶ 입력되는 프로세스의 순서에 따라 평균 반환/대기 시간이 크게 달라질 수 있다 ▶ 입력되는 프로세스의 순서에 따라 평균 반환/대기 시간이 크게 달라질 수 있다. ▶ 평균 반환시간을 짧게 하기 위해서는 CPU 사용시간이 짧은 프로세스를 먼저 처리하는 것이 좋다는 것을 알 수 있음.

2.3.3 SJF 알고리즘 : SPN, SJN ▶ 준비 큐에 있는 프로세스(혹은 작업) 중에서 ■ Shortest Job First 스케줄링 알고리즘 짧은 작업 우선' 알고리즘 , SPN(shortest process next) 짧은 프로세스 다음 선택 ▶ 준비 큐에 있는 프로세스(혹은 작업) 중에서 CPU 수행시간이 가장 짧다고 판단되는 프로세스를 준비 큐의 헤드로 이동시켜, 다음의 CPU 시간을 차지하도록 하는 비선점 스케줄링 기법.

▶ CPU 수행시간이 가장 짧은 프로세스에게 CPU 사용권을 우선적으로 부여하므로, 주어진 프로세스의 집합에 대해서 평균 대기시간이 최소가 되는 최적 알고리즘이 됨. ▶ 대기하고 있는 프로세스의 수를 줄여 주는 효과도 있으며, CPU 사용을 짧게 요구하는 프로세스에게 CPU 사용의 우선권을 주는 알고리즘.

▶ 문제점 : CPU 사용시간이 긴 프로세스가 기아 상태(starvation)에 빠질 수 있다. 정보를 얻기 어렵다. - SJF 알고리즘은 CPU 사용시간의 예측을 사용자에게 의존하게 되며, 규칙적으로 같은 작업이 수행되는 상황 하에서는 적당한 예측이 가능하다.

▶ SJF 알고리즘은 일괄처리 시스템의 장기 스케줄링 (job 스케줄링)에는 유리하게 사용될 수 있으나, 단기 스케줄링에는 적용하기가 어렵다. ▶ 단기 스케줄링에 적용하는 경우에는, 차기의 CPU 버스트 시간을 정확히 알 수 없으므로 이전의 CPU 버스트 시간과 비슷할 것이라는 가정하에 시간을 예상하여 처리할 수 있음.

n + 1 번째의 CPU 사용 시간 C n+1 은 다음과 같이 예측할 수 있다. C n+1 =  Ti ------ (식 1) ▶ Ti 를 이 프로세스의 i 번째 CPU 수행 시간이고, n을 지금까지 CPU를 차지했던 횟수라고 하면, n + 1 번째의 CPU 사용 시간 C n+1 은 다음과 같이 예측할 수 있다. 1 n C n+1 =  Ti ------ (식 1) n i = 1

<식 1>에서 바로 이전의 Cn과 Tn이 이미 계산된 결과로 저장되어 있다면, 다음과 같은 식으로 바꾸어 계산량을 줄일 수 있다. C n+1 = T n + C n n n

Cn+1 =  Tn + (1 -  )Cn (단, 0    1) ▶ 차기의 CPU 버스트 시간을, 앞서 이미 수행된 CPU 버스트 시간의 지수적 평균(exponential average)으로 생각해 보자. <식의 재정의>  는 예상치에 대한 가중값 조절치 Cn+1 =  Tn + (1 -  )Cn (단, 0    1)

▶  = 0 이면 ‘Cn+1 = Cn’이 되어, 가장 최근의 CPU 버스트 시간이 영향을 끼치지 않음을 의미, ▶  = 1이 되면 'Cn+1 = Tn'이 되어, 가장 최근의 CPU 버스트 시간만 영향을 끼치게 됨을 의미함. ▶ 평균적으로 a = 1 / 2 로 간주하는 경우 : 과거의 전체 상황과 현재의 가장 최근 상황이 동일 하게 영향을 주는 것으로 사용.

▶ 지수적 평균의 성격은 Cn+1을 Cn으로 계속 치환할 때, 이 되며, a와 (1- a )는 1보다 작은 값이므로 연속되는 각 항의 가중치는 점점 작아져서 앞 항보다 영향을 덜 미치게 됨을 알 수 있다. ▶ 그림 3.14는 a = 0.5 로 하였을 때의 CPU 버스트를 예측해 본 것이다. C n+1= aTn + (1-a) a Tn-1 + (1-a)2a Tn-2 + … + (1-a)ja Tn-j + ...

< 차기 CPU 버스트 시간의 예측 >

평균 반환시간(FCFS) = (9 + 14 + 16 + 23) / 4 = 15.5 <예 1> CPU 사용 요구시간을 알고 있는 4개의 프로세스에 대해서 SJF와 FCFS 알고리즘의 비교 (4개의 프로세스는 거의 동일한 시간에 준비 큐에 도착한 것으로 간주함) FCFS의 처리 순서 : P1  P2  P3  P4 SJF의 처리 순서 : P3  P2  P4  P1 평균 반환시간(FCFS) = (9 + 14 + 16 + 23) / 4 = 15.5 평균 반환시간(SJF) = (2 + 7 + 14 + 23) / 4 = 11.5 프로세스 번호 CPU 버스트 시간 1 9 2 5 3 4 7

<예 2> CPU 사용시간을 알고 있고, 준비 큐에 도착하는 시간이 각기 다른 4개의 프로세스에 대한 평균 반환시간과 평균 대기시간의 계산. 처리시간(6) 대기시간(8) 처리시간(4) 대기시간(4) 처리시간(1) 대기시간(4) 처리시간(2) 0 1 2 3 6 P1 종료 7 P2 종료 9 P3 종료 12 P4 종료 평균 반환시간 = (6 + 12 + 5 + 6) / 4 = 7.25 평균 대기시간 = (0 + 8 + 4 + 4) / 4 = 4.0

2.3.4 HRRN 알고리즘(시작) SJF 알고리즘의 단점을 보완한 기법. ■ HRRN (highest response ratio next) : HRN SJF 알고리즘의 단점을 보완한 기법. SJF : CPU 요구시간 이 짧은것 우선, 평균 대기시간이 최소. <SJF 알고리즘의 단점> CPU 버스트가 짧은 작업에 우선권을 주기 때문에 대기 시간(waiting time)이 긴 작업에 대해서는 불평등을 초래하게 되는 문제가 있음.

2.3.4 HRRN 알고리즘(계속) CPU 요구시간 ▶ SJF 알고리즘과 마찬가지로 비선점 방식수행. ▶ 각 작업에 대한 처리의 우선순위를 결정 방법 : 해당 작업이 요구하는 CPU 버스트 시간 이외에, 대기하고 있는 시간까지도 고려하여 선정. ▶ HRRN 알고리즘의 우선 순위 결정 처리의 우선순위 값 = CPU 요구시간 대기시간 + CPU 요구시간

▶ 이 식의 결과값을 응답 비율(response ratio)이라고 하며, 그 결과가 1 일 때 최소값이 됨. ▶ 식의 결과가 1 이라는 것은 제일 처음으로 시스템에 들어온 작업(또는 ?)에 해당되며, CPU 요구 시간의 크기에 관계없이 대기한 시간이 없기 때문에 그 결과는 1 이 됨. ▶ 대기 시간이 있는 작업간에는 식의 결과값이 큰 프로세스에 대해서 높은 우선 순위를 부여함.

▶ 분모에 CPU 요구 시간이 있으므로, 똑같은 대기 시간을 갖는 작업간에는 CPU 요구 시간이 짧은 것이 우선 순위가 높게 된다.

▶ 예 1 : 같은 대기 시간을 가지면서, CPU의 요구 시간이 다른 경우에 대한 CPU 할당의 우선 순위 계산. 5 10 + 5 3 = P2의 우선순위 = 2 10 +2 6 P2가 먼저 선택됨(CPU 요구시간이 P1보다 짧다)

▶ 예 2 : 같은 CPU 요구 시간을 가지면서, 대기 시간이 다른 경우의 우선 순위 계산. 5 10 + 5 3 = P4의 우선순위 = 20 +5 P4가 먼저 선택됨(대기시간이 P3보다 짧다)

2.3.5 우선 순위(Priority) 알고리즘 ■ 처리될 작업에 대해, 우선 순위(일반적으로 숫자의 범위)를 부여하여 우선 순위가 높은 작업에게 처리의 우선권을 주는 방법. ▶ 우선 순위가 같은 경우에는 FCFS 정책을 따름. ▶ 기본적으로 비선점 정책으로 수행. ▶ 우선 순위의 등급은 내부적 요인과 외부적 요인에 따라 부여 함.

▶ 내부적 우선 순위 : ▶ 외부적 우선 순위 : 기계 내부의 성능에 영향을 미치는 작업 처리의 제한시간, 기계 내부의 성능에 영향을 미치는 작업 처리의 제한시간, 기억장소 요구량, 사용되는 화일의 수, 평균 CPU 버스트에 대한 평균 I/O 버스트의 비율 등을 고려하여 정함. ▶ 외부적 우선 순위 : 기계 외적인 요인으로 인한 정책적 배려. ▶ 우선 순위가 높은 작업이 계속해서 들어오게 되면, 우선 순위가 낮은 작업이 준비 큐(ready queue)에서 무한정 기다리게 되는 현상인 기아 상태(starvation)가 발생할 수 있음.

<기아상태 해결 방안> 우선 순위가 가장 낮은 작업이더라도 준비 큐에 입력된 시간이 경과함에 따라 우선 순위를 한 단계씩 높여 주어 언젠가는 실행이 될 수 있도록, 동적으로 우선 순위(dynamic priority)를 높여 주는 방법을 적용. ( Priority Aging ) ▶ 기본적으로는 비선점 형태로 수행되지만, 새롭게 준비 큐에 입력된 프로세스와 현재 CPU를 수행중인 프로세스 의 우선 순위를 계속적으로 비교하여, 우선 순위가 높은 프로세스에게 CPU를 선점 시키는 기법으로 알고리즘을 수정할 수도 있음. ( 선점 우선순위 정책 )

2.3.6 기한부 스케줄링 알고리즘 - 시스템에 제출된 작업의 최종 처리시간을 명시. 2.3.6 기한부 스케줄링 알고리즘 ■ 기한부(deadline) 스케줄링 알고리즘 - 시스템에 제출된 작업의 최종 처리시간을 명시. - 명시된 기한 내에 처리되지 못하면 작업 처리 실패. - 실시간 처리 시스템(real-time processing system)과 같은 분야에서 유용하게 적용됨. ▶ 하드 실시간 시스템(hard real-time system) - 한 작업에 대한 엄격한 시간 제한을 가짐. - 제 시간 내에 처리되도록, 모든 요청이 완료될 때까지 독점적으로 CPU를 사용하도록 한다. - 비선점형으로 운영.

▶ 소프트 실시간 시스템(soft real-time system) - 시간적 제약이 다소 약한 형태로 중요 작업에 대해서는 다른 작업에 비해 높은 우선순위를 부여하여 이 작업이 끝날 때까지 높은 우선순위를 계속 유지시키는 방식임. - 다른 스케줄링 알고리즘(예 : 라운드 로빈, 우선순위 등) 과의 복합적 사용을 목표로 하고 있고, 엄격한 시간 제 약을 받지 않는다는 면에서는 기한부 스케줄링으로 보 기에는 무리가 있을 수 있음. ■ 기한부 알고리즘의 전제사항     ‧ 자원 요구를 정확히 미리 제시하여야 함    ‧ 다른 사용자에 대한 서비스 감소, 기아상태를 예방      ‧ 다른 기한부 작업들의 동시 제출로 인한 문제를 해결