2. 스케줄링 알고리즘 다단계 피드백 큐 스케줄링 다단계 큐 스케줄링 : 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행 됨. 전면작업과 후면작업에 대한 독립된 큐가 있어도 작업은 한 큐에서 다른 큐로 옮겨지지 않 음. (작업이 시스템에 들어가면 한 큐에서만 고정되어.

Presentation on theme: "2. 스케줄링 알고리즘 다단계 피드백 큐 스케줄링 다단계 큐 스케줄링 : 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행 됨. 전면작업과 후면작업에 대한 독립된 큐가 있어도 작업은 한 큐에서 다른 큐로 옮겨지지 않 음. (작업이 시스템에 들어가면 한 큐에서만 고정되어."— Presentation transcript:

1 2. 스케줄링 알고리즘 다단계 피드백 큐 스케줄링 다단계 큐 스케줄링 : 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행 됨. 전면작업과 후면작업에 대한 독립된 큐가 있어도 작업은 한 큐에서 다른 큐로 옮겨지지 않 음. (작업이 시스템에 들어가면 한 큐에서만 고정되어 실행됨) 작업은 그 성격상 전면작업과 후면작업의 성질을 바꿀 수 있는 것이 아니기 때문. 스케줄링 부담이 적으나 융통성이 떨어짐. 다단계 피드백 큐(Multi Level Feedback Queue) 프로세서 버스트의 특성에 따라 분리하여 구분하며, 작업이 큐 사이를 이동 가능함. [그림 6-37] 다단계 피드백 구조 - 어떤 작업이 요구하는 프로세서 시간이 너무 길면 작업을 낮은 단계 큐로 옮김 - 입출력 중심 작업과 전면작업(대화식 작업)을 높은 우선순위 큐에 놓고 프로세서 중심 프로세스는 낮 은 우선순위 큐에 놓음. [그림6-37] 다단계 피드백 큐 구조

2 2. 스케줄링 알고리즘 문제점 해결 방법 프로세서들이 더 낮은 수준의 큐로 이동할 경우. 기아상태에 빠질 가능성이 있음.
- 프로세서 버스트 시간이 작은 프로세스에 우선권을 주어 일찍 종료시키고 다음 입출력 버스트를 실행 하며, 이는 입출력 위주의 프로세스에 우선권을 주는 기법임. - 높은 우선순위의 큐가 완전히 비어야 낮은 우선순위의 준비 큐에 있는 작업이 실행될 수 있음. - 낮은 우선순위의 큐에 입력된 작업이 무한정 기다리게 되는 기아상태에 빠질 수 있음. 해결 방법 에이징 방법을 활용. - 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동. - 프로세서 점유 시간이 긴 작업을 우선순위가 낮은 큐로 이동시켜 기아상태 예방. 프로세서들이 더 낮은 수준의 큐로 이동할 경우. 스케줄러는 해당 프로세스들의 규정 시간량을 증가시켜 프로세스가 더 오래 작업할 수 있 도록 함. - 즉, 프로세서를 할당 받을 때마다 규정 시간량을 더 얻음.

3 2. 스케줄링 알고리즘 [그림 6-38] 다단계 피드백 큐 - 큐 4개가 있는 다단계 피드백 큐 스케줄러.
- 각 큐는 0~3까지의 번호를 가짐. - 처음에 스케줄러는 큐0에 있는 작업을 실행하고, 큐0이 다 끝나면 큐1의 작업을 실행. - 큐0과 큐1이 비어 있을 때만 큐2에 있는 프로세스들이 실행. - 큐1에 도착한 프로세스는 큐2에 있는 프로세스를 선점하고, 큐1에 있는 프로세스는 큐0에 도착한 프로세 스에 의해 선점됨. [그림6-38] 다단계 피드백 큐 3

4 2. 스케줄링 알고리즘 다단계 피드백 큐 스케줄링 알고리즘의 우선순위. 다단계 피드백 큐 스케줄링 알고리즘의 정의.
프로세서 버스트가 2 이하인 모든 프로세스에 최고의 우선순위를 부여함. - 최고의 우선순위를 부여받은 프로세스는 프로세서를 할당받아 프로세서 버스트를 끝내고 다음 입출력 버스트로 이동함. 4 이상 16 이하의 규정 시간량이 필요한 프로세스들은 규정시간이 더 짧은 프로세스들보 다는 낮은 우선순위를 받으나 역시 서비스를 빨리 받을 수 있음. 규정시간이 긴 프로세스들은 자동적으로 큐 3으로 가며, 큐 1과 큐 2의 프로세서 주기에 여유가 생기면 선입 선처리 방식으로 처리됨. 다단계 피드백 큐 스케줄링 알고리즘의 정의. 큐(Queue)의 수. 각 큐에 대한 스케줄링 알고리즘. 작업을 좀 더 높은 우선순위의 큐로 격상시키는 시기를 결정하는 방법. 작업을 좀 더 낮은 우선순위의 큐로 격하시키는 시기를 결정하는 방법. 프로세스들이 어느 큐에 들어갈 것인가를 결정하는 방법. 프로세스가 서비스를 받는 시기를 결정하는 방법. ※ 다단계 피드백 큐 스케줄러의 정의에 의해 프로세서 스케줄링 알고리즘 중 가장 일반적인 기법이며, 이 정의들은 특정 시스템에 맞게 적용 가능함.

5 2. 스케줄링 알고리즘 순환할당 알고리즘과의 비교.
동일한 시간(t=0)에 프로세서 중심의 프로세스 시스템이 3개 있다고 가정. 프로세서 버스트 길이는 각각 P1(30), P2(20), P3(10). 시스템은 각각 큐 1(1), 큐 2(2), 큐 3(4)의 규정 시간량을 할당하며, 순환할당 알고리즘의 규정 시간량은 1임. [그림 6-39] 반환시간 및 대기시간을 계산하기 위한 다단계 피드백 큐의 간트 도표. [그림6-39] 다단계 피드백 큐의 간트 도표 순환할당(RR) 및 다단계 피드백 큐(MLFQ) 스케줄링 알고리즘의 반환시간 및 대기시간은 아래와 같음. 반환시간 RR : P1: 60, P2: 50, P3: 평균 : ( )/3 = 46 2/3 MFLQ : P1: 60, P2: 53, P3: 평균 : ( )/3 = 48 1/3 대기시간 RR : P1: 30, P2: 30, P3: 평균 : ( )/3 = 26 2/3 MFLQ : P1(53-23), P2(52-19), P3(29-7) 평균 : ( )/3 = 28 1/3

6 2. 스케줄링 알고리즘 HRN(Highest Response-Rate Next) 스케줄링
한슨(Brinch Hansen)이 개발. 최소 작업 우선(SJF) 기법의 약점이었던 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법. - 실행시간이 짧은 프로세스를 계속 할당하다보면, 실행시간이 긴 프로세스는 계속 기다리게 되는 무한 대기상태 즉, 기아상태에 빠짐. 비선점 스케줄링 기법으로 각 작업의 우선순위는 작업이 서비스 받을 시간 뿐만 아니라 서비스를 기다린 시간(대기시간) 등, 두 가지의 함수로 나타냄. 한 작업이 프로세서를 차지하면 작업이 종료될 때까지 실행됨. HRN 기법의 가변적 우선순위는 다음 식에 따라 계산됨. -‘서비스를 받을 시간’이 분모에 있으므로 ‘서비스를 받을 시간’이 짧은 작업이 우선순위가 높음. - ‘대기한 시간’이 분자에 있으므로 ‘서비스를 받을 시간’이 긴 작업도 ‘대기한 시간’이 큰 경우에 우선순위가 높아짐. 따라서 시스템의 응답시간은 다음과 같이 나타낼 수 있음.

7 2. 스케줄링 알고리즘 [표 6-6]의 작업 5개를 이용한 HRN 스케줄링.
[그림 6-42] 순환할당 스케줄링의 간트 도표(규정 시간량=1). [그림6-42] 순환할당 스케줄링의 간트 도표

8 2. 스케줄링 알고리즘 다중 처리기 스케줄링 강결합 다중처리기 시스템을 중심으로 다중 프로세스의 구조를 살펴봄.
각 프로세서들은 독자적인 큐와 독자적인 알고리즘을 가지므로 프로세서가 다르면 선택의 여지는 상대적으로 제한됨. 작업은 프로세스의 구조에 따라 특정하게 지정되며 특정 프로세서의 의해 실행되어야 함. 같은 종류의 프로세서가 한 시스템에 여러 개 있다면 부하 공유가 발생함. 이를 방지하기 위해 각 프로세서에 서로 독립된 큐를 제공. - 프로세서의 할당이 모든 프로세스에 한 번만 이루어지므로 스케줄링 오버헤드가 적음. - 어떤 프로세서는 큐가 비어 아무 일도 하지 않을 수도, 다른 프로세서는 처리할 작업이 준비 큐에 가득 차 매우 바쁠 수 있다는 단점이 있음. 공동의 준비 큐를 통해 모든 작업이 이용 가능한 프로세서 큐로 가도록 스케줄 함. - 프로세스가 메모리에 적재되는 동안 다른 프로세서에서 작업을 실행 가능.

9 2. 스케줄링 알고리즘 두 가지 스케줄링 방법 사용. 프로세서 자신이 스스로 스케줄링하는 것.
- 각 프로세서는 공통의 준비 상태 큐에서 실행시킬 프로세스 하나를 선택. - 두 프로세서가 같은 프로세스를 선택하지 않아야 하며, 프로세스가 큐에서 누락되지 않도록 해야 함. - 단일 프로세서 스케줄링(우선순위, 순환할당 등) 기법의 활용이 가능하나, 스케줄링이 복잡하여 오버 헤드를 증가시킬 수 있음. 한 프로세서를 다른 모든 프로세서의 스케줄러로 지정하고 주/종(Master/Slave) 구조를 갖게 함. - 비대칭 다중 프로세싱(Asymmetric Multiprocessing). - 운영체제의 핵심 커널 기능들은 특정 프로세서에서 수행하고 다른 프로세서들은 사용자 프로그램들만 수행함. - 주 프로세서는 프로세스들을 스케줄링하여 프로세스를 활성화시킴. - 종 프로세스가 입출력 호출 등의 서비스가 필요할 때 주 프로세서에 요청하여 서비스의 처리가 완료되 길 기다림. - 주 프로세서의 오류는 시스템 전체를 정지시키며, 주 프로세서의 과중한 오버헤드는 성능의 병목지점 이 될 수 있다는 단점이 존재함.

10 2. 스케줄링 알고리즘 스레드 스케줄링 스레드 실행의 개념 부하 공유(Load Sharing)
어플리케이션과 같은 주소 공간에서 동시에 실행하고 협동하는 스레드들로 구현 가능. 스레드 교환은 프로세스 교환보다 오버헤드가 적어 성능을 향상시킬 수 있음. 부하 공유(Load Sharing) 프로세서를 특정 프로세스 하나에 할당하지 않고 전역 큐에서 프로세서를 유지. 쉬고 있는 프로세스는 전역 큐에서 스레드 하나를 선택함. 단일 프로세서 환경에서 사용한 기법을 그대로 채택한 가장 간단한 다중 프로세서 기법. 부하공유의 장점. - 부하는 프로세서들에 균등하게 분산되며 실행 대기 중인 작업에는 분산되지 않음. - 스레드 제어를 위한 중앙 제어 스케줄러 없이 사용 시, 현재 작업을 진행한 프로세서에서 다음 작업 선 정. - 전역(공유) 큐는 선입선처리(FCFS)나 우선순위 기법을 이용하여 구성 가능. 부하공유의 단점. - 중앙 큐는 상호 배제 방식으로 접근되는 메모리 영역으로 많은 프로세서가 동시에 작업을 찾을 시 병 목지점이 될 수 있음. - 선점된 스레드들은 동일한 프로세서 상에서 실행을 재개하기 어려움. - 프로그램의 스레드들 사이에 밀접한 협조가 요구된다면 관련된 프로세스 교환은 성능을 저하시킬 수 있음.

11 2. 스케줄링 알고리즘 갱(Gang) 스케줄링 전용 프로세서 할당. 동적 스케줄링.
관련된 스레드의 집합이 일대일 대응 원칙에 따라 프로세서 집합에서 동시에 실행될 수 있 도록 스케줄링하는 기법. 단일 프로세스에 속한 스레드들이 동시에 스케줄링됨. 동기화 보류 및 프로세스 문맥교환의 횟수를 최소화하여 성능을 향상시킬 수 있음. 스케줄링 오버헤드를 감소시킬 수 있음. 전용 프로세서 할당. 스레드들을 실행 전담 프로세서에 할당하여 정의된 스케줄링을 제공. 각 프로그램은 실행되는 동안 프로그램 내의 스레드 개수와 동일한 수의 프로세스를 할당 받으므로 프로세스가 낭비될 수 있음. 프로세서의 합리적인 이용의 지원이 필요함. - 활성화된 스레드의 개수를 시스템상의 프로세서와 동일한 개수로 제한하여 효율성을 높임. 동적 스케줄링. 프로세스 내의 스레드 수를 동적으로 변경하여 운영체제가 시스템 이용률을 높일 수 있도 록 부하 조절을 허용한 기법. ※ 동적 스케줄링 기법이 갱 스케줄링, 전용 프로세서 할당 기법보다 우수하나 오버헤드로 인 한 성능 감소가 발생할 수 있음.

12 3. 알고리즘 평가 분석적(해석적) 평가 알고리즘 선택 기준
알고리즘 선택 시 사용할 기준의 정의가 모호함으로 인해 선택이 어려움. 일반적으로 프로세스 이용률, 응답시간, 처리율을 선택 기준으로 이용하나, 이들의 기준을 정의하는 것이 어려움. 이 기준을 이용하기 위해선 측정한 내용의 상대적인 중요성을 정의하는 것이 필요함. 아래의 예가 기준이 되며, 선택 기준이 정의되면 다양한 알고리즘을 평가할 수 있음 - 최대 응답시간이 1초라는 제약 조건에서 프로세서 이용률 - 평균 반환시간이 전체 실행 시간에 선형적으로 비례하는 처리율 분석적(해석적) 평가 작업 부하(Workload)를 줄이기 위해 알고리즘의 성능을 평가하는 공식, 값을 생성 하기 위한 알고리즘, 시스템 작업 부하를 이용. 결정성 모형화 : 분석적 평가의 한 형태로 이 방식은 사전에 정의된 특정한 작업에 대하여 각 알고리즘의 성능을 평가. - 다섯 개의 모든 프로세스가 시간 0을 기준으로 다음 [표 6-7]과 같이 도착했다 가정함. - 프로세스 P1, P2, P3, P4에 대하여 선입 선처리, 최소작업 우선, 순환할당(시간 할당량=10) 스케줄링에 대하여 평균 대기시간을 조사. [표6-7] 프로세스의 버스트 시간

13 3. 알고리즘 평가 선입 선처리 평가 비선점 최소 작업 우선 스케줄링 평가
P1 대기시간은 0, P2는 10, P3는 39, P4는 42, P5는 49. 평균 대기시간은 28(=(P1+P2+P3+P4+P5)/5 = ( )/5). [그림6-43] 선입 선처리 간트 도표 비선점 최소 작업 우선 스케줄링 평가 P1 대기시간은 10, P2는 20, P3는 0, P4는 3, P5 는 32. 평균 대기시간은 13(=(P1+P2+P3+P4+P5)/5 = ( )/5). [그림6-44] 비선점 최소 작업 우선 스케줄링 간트 도표

14 3. 알고리즘 평가 순환 할당 평가 프로세스 P2는 10단위 이후에 선점되어 큐의 뒤에 넣음.
P1은 대기시간이 0, P2는 32(=10+20(=40-20)+2(=52-50)), P3는 20, P4는 23, P5는 40. 평균 대기시간은 23(=( )/5) [그림6-45] 순환 할당 간트 도표 최소 작업 우선순위 알고리즘은 선입 선처리 스케줄링으로 얻은 평균 대기시간의 1/2정도 가 됨. 순환 할당 알고리즘은 중간 정도. ※ 결정성 모형화는 간단하고 신속하며, 알고리즘들을 비교할 수 있도록 정확한 값을 제공.

15 SUMMARY 스케줄링 다중 프로그래밍 스케줄러 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정.
프로세서의 효율성을 높이고 시스템의 작업 처리 능력을 향상시키며 작업의 응답시간을 최소화함. 각 프로세스의 실행 여부를 결정하므로 시스템 성능에 영향을 미침. 다중 프로그래밍 프로세서의 이용률을 높이고 처리율을 증대시켜 시스템의 효율을 높이려는 목적을 가짐. 여러 프로그램을 메인 메모리에 적재, 프로세서를 분할하여 짧은 시간에 많은 작업을 처리할 수 있도록 해줌. 스케줄러 장기 스케줄러(작업 스케줄링)와 단기 스케줄러(프로세스 스케줄링)가 있으며, 시분할이나 가상 메모리 시스템은 중기 스케줄러를 가짐. 장기 스케줄러 : 스케줄링 원칙에 따라 디스크 내의 작업을 어떤 순서로 메모리에 가져와 처리할 것인지 결정. 단기 스케줄러 : 메인 메모리의 준비 상태에 있는 작업 중에서 실행할 작업을 선택, 프로세서 배당.

16 SUMMARY 입출력 큐와 준비 큐 작업 스케줄링 프로세스 스케줄링 선입 선처리(FCFS) 스케줄링
운영체제에 있는 두 가지 중요한 큐로, 준비 큐는 실행할 준비가 되어 있고 프로세서를 대기하는 모든 프로세스를 저장함. 작업 스케줄링 프로세서를 사용하기 위해 경쟁할 프로세스들을 선택. 작업 특성에 따라 선택하여 준비 큐로 이동. 자원-할당을 고려, 기억장치 관리에 의해 크게 영향을 받음. 프로세스 스케줄링 대기 프로세스를 선택하는 작업과 준비 큐에서 프로세서를 할당할 프로세스를 선택. 각 프로세스는 PCB로 표현되며, 프로세스들의 큐들을 형성하기 위해 함께 연결 가능. 선입 선처리(FCFS) 스케줄링 가장 간단한 스케줄링 알고리즘. 작은 프로세스들이 매우 긴 프로세스들을 끝날 때 까지 기다려야 하는 경우 발생.

17 SUMMARY 최소 작업 우선(SJF) 스케줄링 순환 할당 스케줄링(Round-Robin Scheduling)
가장 작은 평균 대기시간을 제공하지만, 다음 프로세스의 프로세서 버스트의 길이를 예측하기 어려워 기아상태가 발생할 수 있음. 순환 할당 스케줄링(Round-Robin Scheduling) 시분할 시스템에 적합한 스케줄링 기법으로 규정 시간량 또는 시간 할당량이라 하는 작은 단위의 시간 정의. 시간 할당량은 일반적으로10ⅹ10 밀리 초에서 100 ⅹ 10 밀리 초 범위로 함. 다단계 큐 스케줄링 다양한 종류의 프로세스들에 대하여 상이한 알고리즘들을 사용. 가장 보편적인 것은 전면작업 대화식 큐로 순환 할당 스케줄링을 사용. 후면작업 대화식 큐로 선입 선처리 스케줄링을 이용함.

18