6 단일 프로세서 스케줄링.

Presentation on theme: "6 단일 프로세서 스케줄링."— Presentation transcript:

1 6 단일 프로세서 스케줄링

2 학습목표 내용 스케줄링의 단계를 이해한다. 장기 스케줄러와 단기 스케줄러의 역할을 알아본다.
여러 프로세스 스케줄링 알고리즘의 특성을 이해한다. 알고리즘의 성능을 알아본다. 내용 스케줄링 개요 스케줄링 알고리즘 알고리즘의 평가

3 1. 스케줄링 개요 스케줄링 개념 스케줄링은 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정.
프로세서의 효율성을 높이고 시스템의 작업 처리 능력을 향상시키며 작업의 응답 시간을 최소화함. 각 프로세스의 실행 여부를 결정하므로 시스템 성능에 영향을 미침. 다중 프로그래밍 운영체제에서 가장 중요한 개념으로 여러 작업을 동시에 처리. 여러 프로그램을 메인 메모리에 적재, 프로세서를 분할하여 시스템 효율성을 향상시킴. 다중 프로그래밍의 장점 - 프로세서 이용률을 높일 수 있음. - 프로세서 처리율(주어진 시간에만 처리되는 작업량) 증가. [그림 6-1] 프로세스 실행 과정 예 - 프로세스 A, B가 각각 1초씩 실행하고 1초를 기다리는 것을 60회 반복한다 가정함. [그림 6-1] 프로세스 A와 B의 실행 과정

4 1. 스케줄링 개요 [그림 6-2] 프로세스 작업 수행 시간 예
- 프로세스 A를 모두 처리한 후 프로세스 B를 처리하면, 작업에 4분 소요. - 컴퓨터가 실제 작업을 처리하는 시간 2분, 쉬는 시간 2분 소요. - 프로세서 이용률은 50%. [그림 6-2] 프로세스 A와 B의 작업 수행시간 [그림 6-3] 다중 프로그래밍을 활용한 프로세스 작업 수행 시간 예 - 프로세스 A와 B를 다중 프로그래밍하여 시스템 성능 향상. - A를 먼저 실행하고 1초 후에 B를 실행. - 작업을 끝내는데 소요한 시간은 2분이며, 프로세서 사용률은 50%에서 100%로 향상되고 처리율도 증가함. [그림 6-3] 다중 프로그래밍을 이용한 프로세스 A와 B의 작업 수행시간

5 1. 스케줄링 개요 스케줄링 기본 요소 프로세스 실행
컴퓨터 시스템에서 발생한 다양한 프로세스는 스케줄링 해야 하는 것과 그렇지 않은 것으로 구분. 스케줄링 하지 않고 실행. - 예 : 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 등의 사전 처리. 스케줄링 해야 하는 것. - 예 : 사용자 프로세스, 시스템 프로세스. 다중 작업(Multi Task) - 다중 프로그래밍과 상관 없이 여러 개의 프로세스가 동시에 실행되는 경우. - 스풀링 등의 시스템 프로세스에 의해 단일 사용자 시스템에서도 여러 개의 프로세스가 동시에 실행 가능. 프로세스의 실행은 실행(프로세서 버스트)과 입출력 대기(입출력 버스트)의 순환으로 구성 - 프로세스들은 이들 두 상태 사이에서 교대로 진행. - 프로세서 버스트, 즉 프로세서에서 실행되고 있는 프로세스의 상태로 시작하고 끝남. [그림 6-4] 프로세스의 실행(왼쪽)과 버스트 순환(오른쪽)

6 1. 스케줄링 개요 프로세서 버스트 프로세서 버스트 지속시간을 측정하면 전체적인 발생 시간은 다음 [그림 6-5]와 같은 빈도 곡선으로 표시됨(프로세스마다 다양함). 이 곡선은 일반적으로 지수의 성질을 가짐. [그림 6-6] 프로세스의 입출력 대기시간 - 긴 프로세서 버스트(a)와 짧은 프로세서 버스트(b)를 갖는 전형적인 입출력 대기시간을 나타냄. - 입출력 중심의 프로그램은 전형적으로 매우 짧은 프로세스 버스트를 가짐(입출력 중심 작업). - 프로세서 중심의 프로그램은 매우 긴 프로세서 버스트를 가짐(프로세서 중심 작업). - 이러한 분포는 적절한 프로세서 스케줄링 알고리즘을 선택하는 데 매우 중요한 기준이 됨. [그림 6-5] 프로세스 버스트 시간의 그래프 [그림 6-6] 전형적인 프로세스의 입출력 대기시간

7 1. 스케줄링 개요 스케줄링 단계 세 단계를 중요하게 고려함. 프로세서들을 언제, 어느 프로세서에 할당할 것인가를 결정.
1단계 : 작업 스케줄링(작업 선택) – 승인 스케줄링 - 시스템 자원을 실제 사용할 작업을 결정하는 단계. - 수행 빈도로 표현하여 장기 스케줄링임. - 새로운 프로세스가 생성되면 실행되고, 작업 스케줄링이 수행되면 작업은 프로세스들로 나누어짐. 2단계 : 작업 승인과 프로세서 할당(사용권한) - 어느 프로세스에 프로세서를 사용할 수 있는 권한을 줄 지 결정. - 시스템의 부하가 변동함에 따라 어느 프로세스를 잠정적으로 연기시킬 것인지 결정. - 시스템의 작업 승인과 작업들에 대한 프로세서 배당 사이의 완충 역할. - 수행 빈도로 표현하여 중기 스케줄링으로 교체(Swapping) 기능의 일부로 이해 가능. - 실행 가능한 프로세스에 어떤 프로세스를 추가할 것인지 결정. 3단계 : 준비상태의 프로세서에 프로세스 할당(디스패칭) - 디스패처에 의해 준비상태에 있는 프로세스의 프로세서를 어느 프로세스에 할당할 지 결정. - 수행 빈도로 표현하여 단기 스케줄링으로, 빈번한 실행을 통해 다음 실행할 프로세스를 결정. [그림 6-7] 스케줄링 단계

8 1. 스케줄링 개요 스케줄링 시 고려사항 대기(보류)중인 프로세스 선택과 프로세스에 프로세서를 할당하는 작업으로 다음 사항을 고려해야 함. 자원 할당의 공정성. - 모든 프로세스를 공평하게 취급해야 하며 어느 프로세스도 무한정 실행이 연기되어서는 안됨. 단위 시간당 처리량. - 단위 시간당 유효시간을 줄이고 프로세서의 처리량을 최대화하여 가능한 많은 프로세스에 서비스를 제공. 응답시간. - 적절한 시간 내에 응답을 하며, 대화식 사용자에게는 적어도 2~3초 이내에 응답해야 함. 예측 가능성. - 시스템 부하에 관계없이 작업은 거의 같은 시간 내에 거의 같은 비용으로 실행 가능해야 함. 과부하. - 과부하가 발생하면 자원이 낭비되므로 과부화를 줄여야 함. - 그러나 과부하는 시스템의 전반적인 성능을 향상시킬 수 있음. 자원사용의 균형 - 시스템 내의 자원들은 가능한 쉬지 않고 사용할 수 있도록 스케줄링 해야 함. - 유휴상태의 자원을 사용하려는 프로세스에 특별한 혜택 부여 가능

9 1. 스케줄링 개요 응답시간과 자원의 활용 간에 균형 유지. 실행 대기. 우선순위. 서비스 사용 기회. 서비스 수.
- 응답시간(Turn-around Time)을 빠르게 하는 방법은 자원들이 필요할 때마다 이용할 수 있도록 충분한 자원을 확보하는 것이나, 자원이 충분할 경우 자원 활용도가 낮아짐. - 실시간 시스템에서는 빠른 응답이 필수라 자원 활용이 덜 중요하나, 다른 형태의 시스템에서는 경제성으로 인해 효과적인 자원 활용이 중요함. 실행 대기. - 실행의 무한정 연기는 교착상태만큼 나쁜 영향을 끼치므로 실행이 연기되는 것을 피해야 함. - 자원을 오래 기다릴 수록 높은 우선순위를 부여하여, 자원을 확보하게 해주는 에이징(Aging) 방법을 통해 해결 가능. 우선순위. - 프로세스들에 우선순위를 부여, 우선순위가 높은 프로세스를 먼저 실행시킬 수 있도록 우선순위 제도를 실행. - 비선점 자원일 경우, 스케줄링 기법은 프로세스에 주요 자원을 넘겨주기 보다 우선순위에 따라 처리해야 함. 서비스 사용 기회. - 프로세스에 서비스 사용 기회를 자주 제공해야 함. - 특히 페이지 부재율이 적은 프로세스들에 대해 서비스가 확대되어야 함. 서비스 수. - 시스템에 부하가 많이 걸린 경우에 갑자기 서비스 수가 감소하면 안됨. - 과부하를 방지하던지, 프로세스들의 서비스를 줄여 과부하에 대처. - 서로 모순되는 면이 많이 있어 스케줄링 문제를 어렵게 만드는 원인 중 하나임.

10 1. 스케줄링 개요 스케줄링 큐 스케줄링을 위한 데이터베이스는 큐로 구성, PCB가 리스트 형태로 연결됨.
프로세서 사용의 극대화를 위해 프로세스가 항상 실행될 수 있도록 준비 큐에 프로세스 적재. 단일 프로세서 시스템에서는 프로세스 하나만 수행되므로 여러 프로세스가 준비 큐에 저장. 준비 큐 : 프로세스를 선택하는 큐로서 시스템에 하나 존재함. 일반적으로 준비 큐는 연결 리스트로 머리(Head)와 꼬리 (Tail) 부분은 PCB 목록의 첫 번째 항목과 마지막 항목의 포인터를 가리킴. PCB에는 준비 큐에 있는 다음 프로세스를 가리키는 포인터 필드가 있음. 시스템에는 장치와 연결된 다른 큐들이 존재. 프로세스가 프로세서를 할당 받으면 실행을 완료하고 종료 또는 입출력을 요청할 경우 대기함. 디스크는 동시에 많은 프로세스의 입출력 요청을 받을 수 있으나, 이 경우 프로세스 대기 발생. 장치 큐 - 입출력장치를 사용하기 위해 대기하는 프로세스들의 리스트. - 전용장치 일 경우 장치 큐는 프로세스를 한 개 이상 가질 수 없음. [그림 6-8] 준비 큐와 다양한 입출력 장치 큐

11 1. 스케줄링 개요 큐잉 도표 프로세서 스케줄링을 설명하기 위해 사용.
큐잉 도표에서 사각형은 큐로 준비 큐와 장치 큐의 집합을 의미함. 원은 큐를 서비스하는 자원, 화살표는 시스템에서 프로세스들의 흐름(진행방향)을 표현. [그림 6-9] 프로세서 스케줄링 큐잉 도표 작업 스케줄러가 작업을 받아들일 때, 작업의 PCB가 생성, PCB는 작업이 시작되어 종료될 때까지 내용이 갱신됨. 실행 준비가 된 PCB, 즉 해당 프로세스는 준비 큐에 놓임. 프로세스는 프로세서를 할당 받을 때까지 준비 큐에서 대기.

12 1. 스케줄링 개요 [그림 6-10] 프로세서 스케줄링 과정 설명.
프로세스에 프로세서가 할당되면 다음과 같은 경우 발행 가능. ① 프로세스는 입출력 요청을 발신하고 입출력 큐에 놓임. ② 프로세스는 새로운 프로세서를 생성(Fork)하고 생성한 프로세스의 종료를 기다림. ③ 인터럽트에 의해 프로세서에서 강제로 제거된 프로세스는 준비 큐에 다시 놓일 수 있음. ①,②의 경우 프로세스는 대기상태에서 준비상태로 전환, 다시 준비 큐에 놓임. 프로세스는 종료되어 시스템을 떠날 때까지 순환을 계속함. [그림 6-10] 프로세서 스케줄링 과정 설명. 입출력장치(I/O) 한 개와 입출력 대기 큐 한 개를 갖는 단순한 구조의 큐잉 도표. [그림 6-10] 간략한 큐잉 도표

13 1. 스케줄링 개요 스케줄러 스케줄링 큐에서 프로세스들을 선택하기 위해 스케줄러 사용.
프로세스는 실행되는 동안 다양한 스케줄링 큐 사이를 이동함. 운영체제는 많은 스케줄러를 가지며, 주요 스케줄러는 장기 스케줄러와 단기 스케줄러임. 장기 스케줄러(작업 스케줄러). - 스케줄링 원칙에 따라 디스크 내의 작업을 어떤 순서로 메모리에 가져와서 처리할 것인지 결정하는 프로그램. - 필요한 정보는 제출시간, 작업 이름, 작업의 길이(용량) 등. - 프로세서 스케줄링 : 메인 메모리에 적재되어 있는 프로세스를 할당 받아 실행상태가 되도록 결정. - 프로세스가 실행하는데 필요한 자원의 요청은 만족되어야 함. [그림6-11] 프로세스 스케줄링

14 1. 스케줄링 개요 [그림 6-12] 일괄처리 시스템에서 장기 스케줄러와 단기 스케줄러 비교.
일괄처리 시스템에서는 즉시 처리할 수 있는 양보다 많은 작업이 들어옴. 작업들은 저장 용량이 큰 저장장치에 저장되어 있음. 장기 스케줄러. - 실행할 작업을 준비 큐(입력 큐)에서 꺼내 메인 메모리에 적재함. 단기 스케줄러(프로세서 스케줄러). - 메인 메모리의 준비 상태에 있는 작업 중에서 실행할 작업을 선택, 프로세서를 배당함. [그림6-12] 작업(장기) 스케줄러와 프로세서(단기) 스케줄러

15 1. 스케줄링 개요 장기 스케줄러와 단기 스케줄러의 차이점. 근본적인 차이점은 실행 빈도임. 단기 스케줄러 장기 스케줄러
- 실행할 프로세스를 수시로 선택. - 프로세서에서 실행시간은 100만 분의 수초 정도이므로, 최소한 100만 분의 10초 단위로 스케줄러가 실행된다 가정하였을 때, - 프로세스를 선택하는데 100만 분의 1초가 걸릴 때, 전체 시간의 9%(≒ 1/(10+1)) 정도가 프로세서의 스케줄링에 소비됨. 장기 스케줄러 - 시스템에 새로운 작업이 들어오는 것은 분(Minute) 단위이므로, 단기 스케줄러에 비해 상대적으로 드물게 수행됨. - 다중 프로그래밍의 정도(Multiprogramming Degree, 메인 메모리에 있는 프로세스의 수)를 결정. - 작업이 시스템에 들어오는 정도가 일정할 경우, 작업의 도착률과 작업을 끝내고 나가는 정도는 같게 됨. - 작업이 시스템을 나갈 때만 실행되며 실행 간격이 상대적으로 길어, 실행시간이 길어도 영향을 별로 받지 않음. ※ 대부분의 작업들은 입출력 중심 작업과 프로세서 중심 작업으로 구성. ※ 시스템의 성능을 좋게 하려면 두 종류의 작업을 적절히 혼합하여 선택해야 함.

16 1. 스케줄링 개요 중기 스케줄러 시스템에 장기 스케줄러가 없거나 작은 경우도 있으며, 시분할 시스템은 장기 스케줄러 없이 새로운 프로세스를 메인 메모리에 넣어주기만 함. 가상 메모리 체제나 시분할 기법을 사용하는 시스템은 중기 스케줄러를 추가로 사용. [그림6-13] 중간 단계 스케줄링을 큐잉 도표에 추가 교체(Swapping) 작업 가능 - 프로세스들이 프로세서를 서로 차지하려고 할 때, 프로세스를 기억장소에서 빼낼 수 있어(교체작업) 다중 프로그래밍의 정도를 줄일 수 있음. - 빼낸 프로세스는 시간이 흐른 후 다시 메인 메모리에 들어가 수행이 중단되었던 곳에서부터 계속 수행됨. - 중기 스케줄러가 교체되어 나가고 들어오는 스케줄을 결정함. - 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용 가능하게 하기 위해 필요함.

17 1. 스케줄링 개요 디스패처(Dispatcher) 프로세서 스케줄러(단기 스케줄러)에 포함된 요소로, 분배기.
단기 스케줄러가 선택한 프로세스에 실질적으로 프로세서를 할당. 프로세스의 레지스터를 적재(문맥교환)하고, 사용자 상태(User Mode)로 전환, 다시 시작할 때 사용자 프로그램이 올바른 위치를 찾을 수 있도록 도와줌. 디스패처의 처리 속도는 빠를수록 좋음. [그림6-14] 스케줄러(디스패처)

18 1. 스케줄링 개요 [그림 6-15] 스케줄링과 프로세스 상태 변환 장기 스케줄러. 중기 스케줄러. 단기 스케줄러.
- 프로세스의 생성 과정에서 프로세스의 준비상태에 무엇을 추가할 지 결정하고, 메인 메모리의 사용가능 공간 확인과 자원 확인. 중기 스케줄러. - 교체 기능의 일부로 메인 메모리에 부분적으로 프로세스를 적재, 일시 중지된 프로세서의 원인이 해결되면 다시 준비 상태로 만듦. 단기 스케줄러. - 미리 정해진 정책(알고리즘)에 따라 실행할 프로세스를 선택. [그림6-15] 스케줄링과 프로세스 상태 변환 ※ 프로세스의 실행 상태 → 대기, 대기상태 → 준비 : 단기 스케줄러. ※ 실행 → 종료상태 : 단/장기 스케줄러

19 1. 스케줄링 개요 선점 스케줄링과 비선점 스케줄링
“실행 중인 작업이나 프로세스를 실행 중 중단할 것인가?”의 관점을 기반으로 선점 스 케줄링과 비선점 스케줄링으로 구분. 비선점 스케줄링(Nonpreemptive Scheduling). - 한 프로세스가 자원(프로세서) 선택 시, 다른 프로세스에 할당된 자원을 빼앗을 수 없는 스케줄링. - 모든 프로세서를 공정하게 관리하여 실행시간이 짧은 작업들을 기다리게 되는 경우가 있음. - 우선순위가 높은 작업들이 중간에 입력되어도 대기중인 작업들은 영향을 받지 않아 응답시간 예측이 쉬움. 선점 스케줄링(Preemptive Scheduling). - 현재 실행 중인 프로세스를 인터럽트 할 수 있거나 준비상태로 이동시킬 수 있는 스케줄링. - 하나의 프로세스가 장시간 동안 프로세서를 독점하는 것을 방지. - 우선순위가 높은 프로세스들이 긴급한 처리를 요청할 때 유용함. - 선점을 효과적으로 하기 위해 메인 메모리에 많은 프로세스들이 저장되어 있어야 하므로 많은 오버헤드를 초래함. - 설계 시 우선순위 개념을 반드시 고려하여 의미 있게 배당해야 함.

20 1. 스케줄링 개요 알고리즘 성능 평가 기준 스케줄링 알고리즘 선택 시, 각 알고리즘의 특성을 고려해야 함.
다음과 같은 기준으로 프로세스 알고리즘을 비교. 프로세서 사용률. - 프로세서를 실행상태로 항상 유지하여 유휴상태가 되지 않도록 함. - 가능한 입출력 중심의 작업보다 프로세서 중심의 작업을 실행. 처리율. - 단위 시간당 완료되는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행. 반환시간. - 작업이 시스템에 맡겨져 메인 메모리에 들어가기까지의 시간, 준비 큐에 있는 시간, 실행시간, 입출력 시간 등 작업 제출 후 완료되는 순간까지의 소요시간이 최소화되도록 일괄처리 작업을 우선 처리함. 대기시간. - 작업의 실행시간이나 입출력시간에는 실제적인 영향을 미치지 못하므로 준비 큐에서 기다리는 시간이 최소화되도록 사용자 수를 제한함. 반응시간. - 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격. - 대화형 시스템에 중요한 사항으로, 대화식 작업을 우선 처리하고 일괄처리 작업은 대화식 작업의 요구가 없을 때 처리함. ※ 스케줄링 시 프로세서 사용률과 처리율을 최대화하고, 반환시간, 대기시간, 반응시간 은 최소화하는 것이 바람직함.

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

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

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

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

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

26 2. 스케줄링 알고리즘 아래의 간트 도표는 선점과 비선점 최소 작업 우선 스케줄링을 나타냄. 선점인 경우. 비선점인 경우.
[그림6-26] 선점과 비선점 최소 작업 우선 스케줄링을 사용한 간트 도표 선점인 경우. - 평균 반환시간은 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).

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

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

29 2. 스케줄링 알고리즘 문제점. 해결 방법. [표 6-4] 다음과 같은 프로세스들이 같은 시간에 도착했다 가정함.
우선순위 스케줄링을 이용하여 스케줄링한 결과는 아래의 간트 도표와 같으며, 평균 대기 시간은 8.2임. [표6-4] 프로세스 도착 시간 [그림6-29] 우선순위 스케줄링을 이용한 간트 도표 문제점. 주요 문제는 무한정지와 기아. - 우선 순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스들은 무한정 기다려야 함. 해결 방법. 에이징(Aging). - 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법.

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

31 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이 실행됨.

32 2. 스케줄링 알고리즘 프로세스 반환시간은 작업 완료 시간에서 도착 시간을 뺀 값. 순환 할당 알고리즘은 선점 알고리즘임.
평균 반환시간은 18.25(=( )/4). 평균 대기시간은 11.75(=( )/4). 순환 할당 알고리즘은 선점 알고리즘임. 프로세스가 규정 시간량보다 많은 실행시간 요청 시 스케줄러가 프로세스를 중단, 다음 프로세스로 대치함. 순환 할당 알고리즘의 성능은 규정 시간량의 크기에 영향을 받음. 준비 큐에 프로세스가 n개 있고 규정 시간량이 q이면, 각 프로세스는 최대로 q시간 단위로 프로세서 시간의 1/n을 얻음. 각 프로세스는 자신의 다음 규정 시간량이 할당될 때까지 ‘(n-1)ⅹ q’시간 이상을 대기하지 않음. ex: 규정 시간량 20을 가진 프로세스 5개가 있는 경우, 각 프로세스는 100마다 20의 시간을 할당받음.

33 2. 스케줄링 알고리즘 대화식 프로세스는 규정 시간량보다 짧은 시간을 요구함. 프로세서 공유 방식.
실행을 시작할 때, 입출력 요청을 할 정도만 프로세서를 잠시 사용한 후 보류되고, 다음 프로세스에 프로세서를 양보함. 규정 시간량이 입출력까지의 계산시간보다 커야 입출력 활용도를 극대화하고 대화식 프로세스에 빠르게 반응 가능함. 규정 시간량이 아주 클 경우. - 작업을 완료할 충분한 시간을 얻고 순환 할당 방식이 선입 선처리 방식으로 변함. - 작업시간이 긴 프로세스들 때문에 작업시간이 짧은 프로세스들이 대기, 평균 대기시간이 길어짐. 규정 시간량이 매우 작은 경우(ex: 1μsec) . - 순환 할당을 프로세서 공유(Processor Sharing)라 부름. - 이론적으로 마치 n개의 프로세스가 실제 프로세서 속도의 1/n의 속도로 실행되는 것처럼 보임. 프로세서 공유 방식. CDC(Control Data Corporation)에서 하드웨어 한 세트와 레지스터 10세트로 주변장치 프로세서 10개를 구현하는데 사용됨. 빠른 프로세스 하나가 아닌 느린 프로세서 10개를 이용하여 처리하는 것과 같음. 실제로 프로세서가 메모리보다 빠르고 각 명령어가 메모리 참조 시 프로세서들은 단일 프로세서보다 그리 늦지 않음.

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

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

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

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

38 2. 스케줄링 알고리즘 문제점 및 해결 방법. 프로세서를 할당 받을 시 규정 시간량을 더 얻음.
기아상태에 빠질 가능성이 있음. - 프로세서 버스트 시간이 작은 프로세스에 우선권을 주어 일찍 종료시키고 다음 입출력 버스트를 실행하며, 이는 입출력 위주의 프로세스에 우선권을 주는 기법임. - 높은 우선순위의 큐가 완전히 비어야 낮은 우선순위의 준비 큐에 있는 작업이 실행될 수 있음. - 낮은 우선순위의 큐에 입력된 작업이 기아상태에 빠질 수 있음. 에이징 방법을 활용. - 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동, 프로세서 점유 시간이 긴 작업을 우선순위가 낮은 큐로 이동시켜 기아상태 예방. 프로세서를 할당 받을 시 규정 시간량을 더 얻음. 프로세스들이 더 낮은 수준의 큐로 이동 시, 스케줄러는 해당 프로세스들의 규정 시간량을 증가시켜 프로세스가 더 오래 작업할 수 있도록 함. [그림 6-38] 다단계 피드백 큐 - 큐 4개가 있는 다단계 피드백 큐 스케줄러. - 각 큐는 0~3까지의 번호를 가짐. [그림6-38] 다단계 피드백 큐

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

40 2. 스케줄링 알고리즘 순환할당 알고리즘과의 비교.
동일한 시간(t=0)에 프로세서 중심의 프로세스 시스템이 3개 있다고 가정. 프로세서 버스트 길이는 각각 P1(30), P2(20), P3(10). 시스템은 각각 큐 1(1), 큐 2(2), 큐 3(4)의 규정 시간량을 할당하며, 순환할당 알고리즘의 규정 시간량은 1임. [그림 6-39] 반환시간 및 대기시간을 계산하기 위한 다단계 피드백 큐의 간트 도표. [그림6-39] 다단계 피드백 큐의 간트 도표 36 순환할당(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

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

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

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

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

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

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

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

48