1. 스케줄링 개요 [그림 6-16] 프로세스의 반환, 대기, 반응 시간 프로세스 A, B, C가 A, B, C 순으로 같은 시간에 도착했다 가정함. [그림6-16] 프로세스 C의 반환시간, 대기시간, 반응시간

2. 스케줄링 알고리즘 선입 선처리 스케줄링(FCFS, First-Come-First-Served) 스케줄링 알고리즘 대부분의 알고리즘은 대화식 사용자 환경과 빠른 응답시간을 구현하는데 집중. 프로세스 스케줄러는 프로세스 스케줄링 알고리즘에 따라 프로세서를 할당, 작업을 완료. 여기서는 단일 프로세서로 구성된 시스템의 스케줄링 알고리즘을 살펴봄. 선입 선처리 스케줄링(FCFS, First-Come-First-Served) 프로세서를 요구하는 순서대로 할당하는 기법. 비선점 기법으로 프로세서 스케줄링 알고리즘 중 가장 간단함. 선입선출(FIFO, First-In First-Out) 큐로 구현. 일괄처리 시스템에서는 효율적이나, 대화식 시스템에서는 사용자의 빠른 응답 요구에 적합 하지 않음. [그림6-17] 선입 선처리 스케줄링 - 프로세스가 준비큐에 들어오면 즉, 새로운 작업이 시스템에 들어오면 프로세스의 PCB는 준비 큐의 마지막에 연결됨. - 차례가 되면 준비 큐의 앞부분에 있는 프로세스는 프로세서 를 할당 받고 준비 큐에서 삭제. - 성능이 좋지 않는 경우가 많으며 평균 대기시간이 긴 경우 도 있음.

2. 스케줄링 알고리즘 [표6-1] 작업의 평균 변환 시간 계산 프로세서 버스트 시간을 알고 있는 다음 세 가지 작업 의 평균 변환 시간을 계산. 작업이 P1, P2, P3의 순서로 들어왔다면, 다음과 같은 간트 도표(Gantt Chart)로 나타냄. [표 6-1] 평균 변환 시간 계산 (1) [그림 6-18] P1, P2, P3의 순서로 들어왔을 경우의 간트 도표 - 반환시간은 P1이 24, P2가 27, P3가 30이므로, 평균 반환시간은 27(=(24+27+30)/3). - 대기시간은 P1 이 0, P2 가 24, P3 가 27이므로, 평균 대기시간은 17(=(0+24+27)/3). 작업이 P2, P3, P1의 순서로 들어온 경우 간트 도표는 아래와 같음. [그림 6-19] P2, P3, P1의 순서로 들어왔을 경우의 간트 도표 - 평균 반환시간은 13(=(3+6+30)/3)이 되고, 평균 대기시간은 3(=(0+3+6)/3)으로 단축됨. ※ 프로세스의 실행시간에 따라 평균 반환시간과 평균 대기시간은 큰 폭으로 변화함.

2. 스케줄링 알고리즘 [그림 6-20] 동적 상황에서의 성능. 프로세서 중심 작업 1개와 입출력 중심 작업 3개가 있다고 가정함. [그림6-20] 호위 효과 ① 프로세서 중심 프로세스가 프로세서를 할당 받아 실행되는 동안, 입출력 프로세스들은 입출력을 끝내 고 준비 큐로 이동하여 프로세서를 기다림. 이때 입출력장치들은 쉼(입출력장치 비어 있음). ② 프로세서 중심 프로세스는 프로세서 작업을 끝내고 입출력장치로 이동. 짧은 프로세서 버스트를 가진 입출력 중심 작업들은 프로세서 작업을 신속히 끝내고 다시 입출력 큐 로 이동. 이때 프로세서는 쉼(프로세서 비어 있음). ③ 프로세서 중심 프로세스는 다시 준비 큐로 이동하여 프로세서를 할당 받고 다시 모든 입출력 중심의 프로세스들은 프로세서 중심 프로세스가 처리될 때까지 준비 큐에서 대기(반복처리). 호위효과(Convoy Effect) - 하나의 프로세서 중심 프로세스가 프로세서를 떠나기를 기다리는 현상. - 결과적으로 프로세서 중심 작업과 입출력 중심 작업의 불균형 상태를 의미함. ※ 선입 선처리 스케줄링 알고리즘은 비선점식으로 정기적으로 프로세서를 공유하는 시분할 시스템에서 사 용하기 힘듦. - 프로세서를 점유한 프로세스가 종료하든지 또는 입출력을 요구하여 자신의 프로세서를 해제하기 전까 지는 프로세서를 계속 점유하기 때문.

2. 스케줄링 알고리즘 최소 작업 우선 스케줄링(SJF, Shortest Job First) 프로세서 버스트 시간이 가장 짧은 작업에 프로세서를 할당하는 기법. 이때 두 프로세스가 다음 순서로 동일한 프로세서 버스트를 가진다면 선입 선처리 스케줄 링을 적용함. [그림 6-21] 최소 작업 우선 스케줄링 다음과 같은 작업들이 준비상태 큐에 있을 때, 최소 작업 우선 스케줄링을 사용하면 [그림 6-22]와 같은 간트 도표가 이루어지며, 평균 반환시간은 13(=(3+9+16+24)/4). [표6-2] 평균 변환 시간 계산 (2) [그림 6-22] 최소 작업 우선 스케줄링을 사용한 간트 도표

2. 스케줄링 알고리즘 대기시간은 P2가 0, P1은 3, P4는 9, P3은 16이므로 평균 대기시간은 7(=(0+3+9+16)/4). [그림 6-23] 선입 선처리 스케줄링 사용 시 간트 도표. [그림6-23] 선입 선처리 스케줄링을 사용한 간트 도표 - 평균 반환시간은 14(=(6+9+17+24)/4)이며, 평균 대기시간은 8(=(0+6+9+17)/4). 최소 작업 우선 알고리즘은 주어진 작업 집합에 대해 평균 대기시간이 최소이므로 최적 알 고리즘. - [그림 6-24]실행시간이 짧은 작업(Short)을 실행시간이 긴 작업(Long) 앞에 놓음. - 긴 작업의 대기시간은 증가하였으나, 짧은 작업의 대기시간이 줄어 평균 대기시간은 감소함. - [그림 6-25] 프로세스 실행시간이 각각 5, 11, 7, 3인 경우. (짧은 작업 우선 처리시 평균 대기시간 감 소) [그림6-25] 최소 작업 우선 스케줄링이 최적임을 증명 [그림6-24] 짧은 작업 우선 처리

2. 스케줄링 알고리즘 일괄 처리 시스템에서 장기 스케줄링. 최소 작업 우선 스케줄링은 작업 스케줄링에서 많이 사용됨. 작업의 제한 시간이 짧은 경우 빠른 반환을 요구하므로 사용자는 시간 한계를 정확하게 예 상해야 함. - 시간 한계가 너무 짧을 경우 실행시간이 제한시간을 초과하여 다시 작업을 입력해야 함. 최소 작업 우선 스케줄링은 작업 스케줄링에서 많이 사용됨. 단기 스케줄링에서는 다음 프로세스의 프로세서 버스트 시간을 예상할 수 없으므로 하드웨 어 구성이 어려움. 이를 해결하기 위해 최소 작업 우선 스케줄링 근사치 사용. 최소 작업 우선 스케줄링은 선점 또는 비선점이 가능함. 비선점 스케줄링 알고리즘은 시분할 시스템에 사용하기 힘듦. 시분할 시스템에서는 각 사용자들이 일정한 간격으로 프로세서 사용을 원하기 때문.

2. 스케줄링 알고리즘 [표 6-3] 작업 4개의 평균 변환 시간 계산 아래의 간트 도표는 선점과 비선점 최소 작업 우선 스케줄링을 나타냄. [그림6-26] 선점과 비선점 최소 작업 우선 스케줄링을 사용한 간트 도표 [표6-3] 평균 변환 시간 계산 (3) 선점인 경우. - 평균 반환시간은 13(=(P1+P2+P3+P4)/4 = ((17-0)+(5-1)+(26-2)+(10-3))/4 = 52/4). - 평균 대기시간은 6.5(=(P1+P2+P3+P4)/4 =(10-1)+(1-1)+(17-2)+(5-3))/4). - 문맥교환 시간이 소요됨. (반드시 비선점에 비해 유리하다고 할 수 없음.) - 최소 잔여시간 우선 스케줄링(Shortest-Remaining-Time-First Scheduling)이라고 함. 비선점인 경우. - 평균 반환시간은 14.25(=(P1+P2+P3+P4)/4 =(8-0)+(12-1)+(26-2)+(17-3))/4 = 57/4). - 평균 대기시간은 7.75(=(P1+P2+P3+P4)/4 =(0+(8-1)+(17-2)+(12-3))/4).

2. 스케줄링 알고리즘 우선순위 스케줄링(Priority Scheduling) 준비 큐에 도착한 프로세스와 현재 실행 중인 프로세스의 우선순위를 비교. 프로세스들의 우선순위를 비교하여 최고 우선순위를 가진 프로세스에 프로세서를 할당. 우선순위가 같은 프로세스들은 선입 선처리 순으로 스케줄 됨. [그림6-27] 우선순위 스케줄링 최소 작업 우선 알고리즘은 우선순위 알고리즘에 속함. 우선순위(P)는 예측된 다음 프로세서 버스트의 역(τ), 즉 ‘P = 1/ τ’. 프로세서 버스트가 클수록 우선순위가 낮으며, 그 반대도 성립됨.

2. 스케줄링 알고리즘 내부적 또는 외부적으로 우선순위 정의 가능. 선점 또는 비선점이 가능함. 우선순위는 정해진 범위의 수 0~7 또는 0~4,095를 사용. - 0이 최상위이거나 최하위라고 정해지지는 않음. 내부적으로 정의된 우선순위 - 프로세스의 우선순위 연산을 위해 제한시간, 기억장소 요구량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율 등이 사용됨. 외부적인 우선순위 - 프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적인 요인 등 운영체제 외적 인 요소에 의해 결정됨. 선점 또는 비선점이 가능함. 선점 우선순위 스케줄링 알고리즘. - 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 프로세서를 선점함. 비선점 우선순위 스케줄링 알고리즘. - 단순히 준비 큐의 머리 부분에 새로운 프로세스를 넣음. [그림 6-28] 4단계 우선순위를 갖는 준비 큐에서 실행 가능한 프로세스를 나타냄. - 우선순위가 가장 높은 큐(4)의 프로세스가 실행된 후 큐(3)에 저장된 프로세스가 실행된다. [그림6-28] 4단계 우선순위를 갖는 스케줄링 알고리즘

2. 스케줄링 알고리즘 문제점. 해결 방법. [표 6-4] 다음과 같은 프로세스들이 같은 시간에 도착했다 가정함. 우선순위 스케줄링을 이용하여 스케줄링한 결과는 아래의 간트 도표와 같으며, 평균 대기 시간은 8.2 (=(0+1+6+16+18)/5) 임. [표6-4] 프로세스 도착 시간 [그림6-29] 우선순위 스케줄링을 이용한 간트 도표 문제점. 주요 문제는 무한정지와 기아상태. - 우선 순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스들은 무한정 기다려야 함. 해결 방법. 에이징(Aging). - 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법. - 예를 들어, 매15분마다 대기중인 프로세스의 우선순위를 1씩 증가시키면 초기의 우선순위가 0이였던 프로세스도 시스템에서 최고의 우선순위로 증가하여 처리될 수 있음.

2. 스케줄링 알고리즘 순환 할당(Round-Robin) 스케줄링 시분할 시스템을 위해 특별히 설계됨. FIFO기법을 선점 형태로 변형한 기법. 규정 시간량(Time Quantum) 또는 시간 할당량(Time Slice)라 하는 작은 단위의 시간을 정 의. 준비 큐는 순환 큐(Circular Queue)로 설계하여 프로세서 스케줄러가 준비 큐를 돌아가면 서 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공. 준비 큐는 FIFO 큐임. - 새로운 프로세스가 추가될 때는 준비큐의 맨 뒤에 덧붙여짐. [그림6-30] 프로세스 B가 실행된 후의 준비 큐 프로세서 스케줄러는 준비 큐의 앞부분에 있는 프로세스에 프로세서를 할당(디스패치). 규정 시간량이 지나면 인터럽트가 발생되며, 다음 두 가지 경우에 발생함. ① 규정 시간 내에 일을 끝내는 경우. - 프로세서는 자유로워지며 준비 큐에 있는 다음 프로세스를 진행. ② 현재 실행하고 있는 프로세스가 규정 시간량보다 긴 경우. - 운영체제에 의해 인터럽트 되며 중단된 프로세스의 레지스터들은 프로세스의 PCB에 저장되고 프로 세스는 준비 큐의 마지막 위치에 입력됨.

2. 스케줄링 알고리즘 스케줄러는 준비 큐에서 다음 작업을 가져와 실행시킴. [그림6-31] 순환 할당 스케줄링 [표 6-5] 이전의 최소 작업 우선 알고리즘의 작업을 적용한 예. 규정 시간량을 4로 한 경우 순환 할당 스케줄링의 간트 도표는 [그림 6-32]와 같음. [표6-5] 우선순위 알고리즘의 작업 정리 [그림6-32] 규정 시간량을 4로 한 순환 할당 스케줄링의 간트 도표 - P1은 처음 4만큼의 시간을 실행한 후 아직 4가 남아 있지만 P2가 프로세서를 선점하여 실행됨. - P2는 시간을 4만큼만 원하므로 4시간 후 종료되며 P3이 들어옴. - P3은 4시간을 실행한 후 P4에 프로세서를 넘겨 줌. - 이후 앞서 종료되지 않은 P1이 실행됨.

2. 스케줄링 알고리즘 프로세스 반환시간은 작업 완료 시간에서 도착 시간을 뺀 값. 순환 할당 알고리즘은 선점 알고리즘임. 평균 반환시간은 18.25(=(20+7+24+22)/4). 평균 대기시간은 11.75(=(12+3+15+17)/4). 순환 할당 알고리즘은 선점 알고리즘임. 프로세스가 규정 시간량보다 많은 실행시간 요청 시 스케줄러는 프로세스를 중단시키고 다음 프로세스로 대치함.

2. 스케줄링 알고리즘 대화식 프로세스는 규정 시간량보다 짧은 시간을 요구함. 실행을 시작할 때, 입출력 요청을 할 정도만 프로세서를 잠시 사용한 후 보류되고, 다음 프로세스에 프로세서를 양보함. 규정 시간량이 입출력까지의 계산시간보다 커야 입출력 활용도를 극대화하고 대화식 프로 세스에 빠르게 반응 가능함. 규정 시간량이 아주 클 경우. - 작업을 완료할 충분한 시간을 얻고 순환 할당 방식이 선입 선처리 방식으로 변함. - 작업시간이 긴 프로세스들 때문에 작업시간이 짧은 프로세스들이 대기, 평균 대기시간이 길어짐. 규정 시간량이 매우 작은 경우(ex: 1μsec) . - 순환 할당을 프로세서 공유(Processor Sharing)라 부름. - 이론적으로 마치 n개의 프로세스가 실제 프로세서 속도의 1/n의 속도로 실행되는 것처럼 보임. - 문맥교환에 따른 오버헤드가 발생.

2. 스케줄링 알고리즘 최적의 규정 시간량 결정. 문제점. 규정 시간량의 크기는 시스템 특성 및 오버헤드, 프로세스에 따라 다름. 문제점. 프로세서 중심 프로세스에서 대화식 프로세스를 지원하므로 선점을 통해 대화식 프로세스 가 도착할 때 적절한 시간에 반응을 보여주도록 보장하는 것이 프로세스들의 규정 시간량 차이보다 중요함. 소프트웨어 측면에서 문맥교환의 문제. - 문맥교환 : 규정 시간량만큼 수행하고 프로세서를 다른 프로세스에 넘겨줄 때, 이전 프로세스의 레지 스터들은 저장되어야 하고 수행될 프로세스의 레지스터는 시스템에 적재되어야 함. - 문맥교환 때문에 발생하는 오버헤드가 커지면, 시스템 성능 감소와 의미 있는 일의 수행보다 대부분의 시간을 문맥 전환에 사용. [그림 6-33] 문맥교환 시간이 미치는 영향 예. - 시간 10을 소비하는 작업 수행 시, 규정 시간량이 12일 경우, 작업은 규정 시간 내에 끝남. - 규정 시간량이 6일 경우, 작업은 규정 시간량을 2번 요구, 1번의 문맥교환을 요청함. - 규정 시간량이 1일 겨우, 문맥교환은 9번, 실행속도가 늦어지게 됨. - 규정 시간량이 작을 수록 문맥교환 횟수는 많아지게 되므로 규정 시간량을 문맥교환에 소요되는 시간 보다 충분히 크게 해야 함. [그림6-33] 문맥교환 횟수를 증가시키는 작은 시간 할당량

2. 스케줄링 알고리즘 반환시간도 규정 시간량의 크기에 영향을 받음. [그림 6-34] 규정 시간량에 따른 반환시간의 변화. - 한 프로세스 집합의 평균 반환시간은 규정 시간량의 크기가 증가하더라도 반드시 개선되지는 않음. - 대부분의 프로세스들이 단일 규정 시간량 안에 작업을 끝마치면 평균 반환시간은 좀 더 개선됨. [그림 6-35] 시간 규정량에 따른 프로세스의 반환 시간. - 실행시간이 10인 3개의 프로세스들이 있고 규정 시간량이 1시간일 경우, 평균 반환시간은 29(=(28+29+30)/3). - 규정 시간량이 10인 경우 평균 반환시간은 20(=(10+20+30)/3)으로 떨어짐. - 규정 시간이 작을 경우 문맥교환이 많이 일어나므로 평균 반환시간이 좋지 않음. [그림6-34] 규정 시간량에 따른 반환시간의 변화 [그림6-35] 시간 규정량에 따른 프로세스의 반환시간

2. 스케줄링 알고리즘 다단계 큐(Multi-Level Queue) 스케줄링 각 작업들을 서로 다른 묶음(그룹)으로 분류할 수 있을 때 사용. 분류 예 - 작업을 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법. - 작업을 전면작업(대화형, Foreground Task)과 후면작업(일괄처리형, Background Task)으로 분류 시, 두 유형의 요구 반응 시간이 다르므로 서로 다르게 스케줄링 해야 함. - 전면작업은 후면작업에 비해 높은 우선순위를 가짐. 준비상태 큐를 종류별로 여러 단계로 분할해 둠(그림 6-36 참조). - 작업이 특정 그룹의 준비상태 큐에 들어갈 경우, 다른 준비상태 큐로 이동할 수 없음. 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 가짐. 큐 사이에도 스케줄링이 있어야 하며, 이는 고정된 우선순위의 선점식 스케줄링임. 큐들 사이에 시간을 나누어 사용 가능. - 각 큐는 프로세서 시간의 일정량을 받아서 큐에 있는 프로세스들을 스케줄링 할 수 있음.

2. 스케줄링 알고리즘 다단계 큐(Multi-Level Queue) 스케줄링 상위큐 중위큐 하위큐 [그림 6-36] 큐 5개를 가진 다단계 큐 스케줄링 알고리즘 - 각 큐는 순서대로 절대적인 우선순위를 가짐. - 앞의 세 가지 큐가 비어있어야, 네 번째 일괄 처리 큐에 있는 프로세스가 실행됨. - 일괄 처리 프로세스가 실행되는 동안에 대화식 편집 프로세스가 준비큐에 들어오면, 일괄처리 프로세스는 프로세서를 반납해야 함.  즉, 하위 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비상태 큐에 프로세스 가 들어오 면 상위 프로세스에게 CPU를 할당해야 함.(선점형) [그림6-36] 다단계 큐 스케줄링 상위큐 중위큐 하위큐 19