6 단일 프로세서 스케줄링

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

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

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의 작업 수행시간

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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