[OS] 2-8. 프로세스 스케줄링 알고리즘

공부 스파이럴·2024년 3월 8일

운영체제

목록 보기

14/27

FCFS(First-Come-First-Served) 스케줄링

가장 간단한 스케줄링 방식

프로세스들은 대기 큐에 도착한 순서에 따라 중앙처리장치를 할당 받으며, 일단 프로세스가 중앙처리장치를 차지하면 완료될 때까지 CPU를 점유하며 수행

비선점 스케줄링

모든 프로세스가 동일하게 취급되므로 응답 시간의 차이가 적게 나며, 작업 완료 시간을 예측하기가 용이

convoy effect(호위효과 : 첫번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 되는 것) 가 발생하면 CPU와 장치 이용률이 낮아짐

SJF(Shortest Job First) 스케줄링

기다리고 있는 프로세스 중에서 수행 시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식

FCFS보다 평균 대기 시간을 감소시킴

SJF의 문제점

수행될 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보를 알기 어려움

적절한 응답 시간이 보장되어야 하는 시분할 방식의 시스템 상황에서는 적당하지 못함

SJF의 최선의 방법은 수행 시간의 예측을 사용자에게 의존하는 것으로, 규칙적으로 같은 프로세스들이 수행되는 상황에서는 적당한 예측이 가능하나 개발중인 프로그램의 경우에는 사용자가 자신의 프로그램이 처리되는데 시간이 얼마나 소요될 것인가를 모르는 경우가 대부분

우선순위(Priority) 스케줄링

우선순위가 각 프로세스에게 주어지며, 중앙처리장치는 가장 높은 우선순위를 가진 프로세스로 할당됨

우선순위가 같은 프로세스들은 FCFS 순서로 스케줄됨

내부적 우선 순위

프로세스의 우선순위를 계산하기 위하여 제한 시간, 메모리 요구량, 개방된 파일의 수, 평균 입출력 버스트의 비율 등을 사용

외부적 우선 순위

프로세스의 중요성, 컴퓨터 이용을 위한 자원의 형태와 수량, 프로세스를 지원하는 부서, 정책적인 요인 등을 사용

우선순위 스케줄링은 선점식이거나 비선점식이 될 수 있
음

우선순위 알고리즘의 문제점

무한 대기(indefinite blocking) 또는 기아 현상(starvation)

해결책은 에이징(aging)
-> 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킴

라운드 로빈(Round-Robin) 스케줄링

FCFS + 선점(할당시간(time quantum) 마다)

시분할 시스템을 위하여 고안된 선점 스케줄링 방식

FCFS에 의해서 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당 받음

효율적인 문맥 교환 기법을 쓰고 프로세스들이 동시에 주기억장치 내에 유지될 수 있도록 충분한 기억용량을 준비한다면 선점으로 인한 오버헤드를 최대한 줄일 수 있고 시스템 성능도 높일 수 있음

할당 시간의 크기 : 보통 10 ~ 100ms

할당 시간의 크기는 컴퓨터 시스템의 효과적인 동작에 절대적인 영향을 미침

너무 크면, FCFS와 동일

너무 작으면, 문맥 교환을 위한 오버헤드 때문에 성능 저하

대부분의 대화식 시스템에서는 프로세스가 할당된 시간보다 더 적은 시간 내에 처리될 수 있도록 할당시간이 충분히 크게 결정되며, 일반적으로 대화식 프로세스가 실행을 시작하면 입출력 요구를 발생시킬 때까지 중앙처리장치를 충분히 사용할 수 있도록 함

대화식 사용자들이 다중 프로그래밍 상태에 있을 때는 대화식 응답시간을 적절히 보장하기 위해서 중앙처리장치는 주기적으로 선점되어야 함

SRT(Shortest Remaining Time) 스케줄링

SRT(혹은 선점 SJF) 스케줄링 기법은 SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시분할 시스템에서 유용

SJF와 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료되는 데 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행시킴

SJF에서는 한 번 작업의 처리가 시작되면 완료될 때까지 계속 실행되지만(비선점), SRT에서는 실행 중인 프로세스가 선점될 수 있음

SRT는 SJF 보다 더 많은 비용이 소요되며 수행 중인 각각의 작업들에 대한 실행 간을 추적 보유하고 있으며, 때로는 선점 과정을 수행해야 함

SRT는 각 프로세스가 서비스 받을 시간이 기록 보유되어야 하기 때문에 오버헤드가 늘어남

이론적으로 SRT는 대기시간을 최소로 하지만 선점 오버헤드 때문에 어떤 경우에 는 SJF로 처리하는 것이 나을 수도 있음

(가정) 수행하고 있는 작업이 거의 완료되었고, 추정되는 실행 시간이 아주 적은 새로운 작업이 도착했다면…..선점 혹은 비선점?

이런 상황은 임계치(threshhold value)를 부여하여 조정 가능
-> 만일 수행 중인 작업을 끝내는데 소요되는 시간이 이 임계치보다 적다면 시스템은 중간에 그 작업을 중지하지 않고 완료될 때까지 수행하도록 한다

다단계 큐(Multilevel Queue) 스케줄링

다단계 큐 스케줄링 알고리즘은 준비 큐를 다수의 별개 큐로 나눔

기억장치의 요구량이나 프로세스의 우선순위 혹은 프로세스의 유형과 같은 프로세스의 특성에 근거해 프로세스들은 해당 큐에 할당

각 큐는 자신의 스케줄링 알고리즘을 갖고 있음
-> 고정된 우선순위의 선점식 스케줄링

후면작업(background job: 일괄처리) 큐가 선입선출 알고리즘에 의해 스케줄 되는 반면 전면작업(foreground job: 대화식) 큐는 라운드 로빈 알고리즘에 의해 스케줄 된다.

각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를
가짐
-> 시스템 프로세스, 대화식 프로세스, 대화식 편집 프로세스를 위한 큐들이 모두 비어 있지 않으면, 일괄처리 큐에 있는 프로세스는 실행될 수 없음

일괄처리 프로세스가 실행되는 동안 대화식 프로세스가 준비 큐에 들어가면 일괄처리 프로세스는 선점됨

큐들 사이에 시간을 나누어 사용 가능

각 큐는 중앙처리장치 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄링 할 수 있음

예: 전면작업, 후면작업 큐의 실례에서, 전면작업
큐에는 자신의 프로세스들 사이에서 라운드 로빈 스
케줄링을 위해 중앙처리장치 시간의 80%가 주어지고,
후면작업 큐는 자신의 프로세스들을 선입 선처리 방
식으로 중앙처리장치 시간의 20%를 할당 받아 처리
될 수 있음

다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링

한 프로세스가 중앙처리장치를 차지했을 때, 시스템이 그 프로세스의 체제를 알지 못하는 경우에 스케줄러는 그 프로세스가 필요로 하는 정확한 중앙처리장치 사용 시간을 알 방법이 없음

스케줄링 기법의 기준

짧은 작업에 유리하고

입출력장치를 효과적으로 이용하기 위해 입출력 위주의 작업들에 우선권을 주며

가능한 한 빨리 작업의 특성을 알고 그것에 맞게 그 작업을 스케줄링

다단계 피드백 큐는 위와 같은 목적을 달성할 수 있는 구조를 가진다.

중앙처리장치에 대한 요구량에 따라 프로세스들을 분류하는 데 이상적

일반적으로 시스템의 동적 변환에 적응할 수 있는 적응(adaptive) 기법의 좋은 예

새로운 프로세스는 큐잉 네트워크(queueing network)의 일단계 큐의 뒤쪽에 들어가며, 그 프로세스는 중앙처리장치를 차지할 때까지 큐를 통하여 FCFS에 의하여 이동

만약 프로세스가 끝나기 전에 할당된 시간이 만료되었거나 입출력 혹은 어떤 돌발사건 등으로 인하여 중앙처리장치를 양도한다면 그 작업은 그 다음 하위 단계의 큐로 이동되어 재배치됨
-> 마지막 단계의 큐에서는 그 프로세스가 완료될 때까지 라운드 로빈(RR)으로 순환 (낮은 단계로 갈수록 할당 시간 증가)

어떤 임의의 큐에 있는 프로세스는 모든 상위 단계의 큐가 비어있지 않으면 수행될 수 없으며, 수행 중인 프로세스라도 더 높은 프로세스에 의해 선점될 수 있음

입출력 위주의 프로세스는 매우 높은 우선순위를 가지고 네트워크에 들어가서 중앙처리장치를 빨리 차지하게 됨

일단계 큐에서의 할당시간량은 입출력 위주의 작업들이 입출력 요구를 발생시킬 때까지 연산을 계속할 수 있을 만큼 커야 함

다단계 피드백 큐 기법은 중앙처리장치에 대한 요구량에 따라 프로세스들을 분류하는 데 이상적

시스템이 행동 변화에 민감하게 대응하도록 하는 또 다른 방법은, 할당시간이 만료되기 전에 자진해서 중앙처리장치를 양도하는 프로세스에게는 그 때마다 피드백 큐잉 네트워크에서 한 단계씩 높은 큐로 올라가도록 해주는 것

다단계 피드백 큐잉 기법은 일반적으로 시스템의 동적 변화에 적응할 수 있는 적응 기법의 좋은 예

적응기법은 비적응 기법보다 오버헤드가 크지만 시스템의 동적 변화에 효율적으로 대응하므로 그만한 가치가 있음

다단계 피드백 큐잉 기법을 약간 변화하여 각 프로세스가 다음 하위 단계의 큐로 이동하기 전에 각 큐에서 여러 번 라운드 로빈 방법으로 순환하도록 할 수 있는데, 이 경우 보통 각 큐에서 라운드 로빈 방법으로 순환하는 횟수는 프로세스가 다음 하위 단계의 큐로 이동할 때마다 그만큼 증가

HRN(High Response ratio Next) 스케줄링

SJF의 약점, 특히 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법으로 한 작업이 중앙처리장치를 차지하면 그 작업은 완성될 때까지 실행하며, 대기시간을 고려하여 우선순위 결정

우선순위 계산식은 다음과 같으며, 시스템 응답시간 값이 클수록 우선순위가 높음

짧은 작업일 경우라도 대기 시간이 큰 작업은 우선순위가 높아짐