[OS] 2-7. 프로세스 스케줄링

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

운영체제

목록 보기

13/27

스케줄링의 목적 및 기준

목적

공정성

모든 프로세스들이 공평하게 취급되어야 함

어떤 프로세스도 무한대기 상태가 되어서는 안됨

처리 능력의 최대화

단위 시간 내에 최대한의 프로세스들이 수행될 수 있도록 스케줄링 되어야 함

응답 시간의 최소화

대화식 사용자들에 대한 응답 시간을 최대한 빠르게 해야 함

예측 가능

주어진 작업은 시스템 내부의 부하(load)에 상관없이 거의 같은 비용, 같은 시간 내에 수행되어야 함

오버헤드(overhead)의 최소화

자원 사용의 균형 유지

스케줄링 메커니즘들은 해당 시스템의 자원들을 쉬게 해서는 안되며, 프로세스들이 사용되지 않는 자원들을 사용하도록 해야 함

응답과 이용 간의 균형 유지

실시간 시스템

응답 시간을 빠르게 하기 위해 충분한 자원을 갖게 되어 자원의 활용도 낮아짐

다른 시스템

경제성 때문에 효과적인 자원 활용이 더 중요시 됨

실행의 무한한 지연을 피할 것

무한 지연은 교착 상태 만큼 나쁠 수 있음

이를 피하기 위한 방법은 에이징(aging)인데, 이것은 프로세스(infinite postponement)가 오래 기다릴수록 그 우선순위를 높이는 것

우선순위제의 실시

주요 자원들을 차지하고 있는 프로세스에게 우선권을 주게 함

하위 순서를 가진 프로세스가 주요자원을 차지하고 있다고 할지라도 그 자원이 다른 프로세스에게 양보될 수 없다면 스케줄링 기법은 그 프로세스로 하여금 주요자원을 양보하기 보다는 우선적으로 처리토록 함

좀더 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스를 제공함

예: 페이지 부재(page fault)율이 낮은 프로세스들

과중한 부하를 완만히 줄임

부하가 과중하면 새로운 프로세스들이 더 생성되지 않도록 하여 과다한 부하를 방지하거나 모든 프로세스들에 대한 서비스를 적당히 줄임으로써 과다한 부하를 감소시킴

-> 이러한 많은 목적들은 서로 상충되는 결과를 발생함으로써 스케줄링을 복잡하게 만드는 원인이 될 수 있음

기준

언급된 스케줄링의 목적들을 실현하기 위한 스케줄링 기법은 아래와 같은 사항들을 고려해야 함

입출력 위주의 프로세스인가?

연산 위주의 프로세스인가?

프로세스가 일괄처리형인가 대화형인가?

긴급한 응답이 요구되는가? (실시간 처리 시스템 vs. 일괄처리 시스템)

프로세스의 우선순위

프로세스가 페이지 부재를 얼마나 자주 발생시키는가?

높은 우선순위를 지니는 프로세스에 의해서 얼마나 자주 프로세스가 선점(preempted) 되는가?

자주 선점되는 프로세스들은 보다 좋지 않은 대우를 받게 한다.

오버헤드 증가시키기 때문

프로세스가 받은 실행 시간은 얼마나 되는가?

프로세스가 완전히 처리되는 데 필요한 시간은 얼마나 더 요구되는가?

모든 프로세스의 평균 대기 시간을 최소화하기 위하여 최소의 실행 시간을 남긴 프로세스부터 먼저 실행시킴

그러나 각 프로세스의 처리완료를 위해 필요한 시간을 정확히 예측하기가 어려운 일임

단계별 분류

1. 상위 단계 스케줄링(high level scheduling)

작업 스케줄링(Job Scheduling)이라고도 함

어떤 작업에게 시스템의 자원들을 차지할 수 있도록 할 것인가를 결정

어떤 작업들이 그 시스템에 들어오는 것을 승인하는 것(승인 스케줄링, admission scheduling)

2. 중간 단계 스케줄링(intermediate level scheduling)

어떤 프로세스들에게 중앙처리장치를 차지할 수 있도록 할 것인가를 결정

시스템 전체의 성능향상을 위하여 허용되는 시스템 부하(load) 내에서 짧은 순간에 프로세스들에 대한 일시적인 활동의 중단 및 재개를 수행

그 시스템에서의 작업 승인과 이들 작업들에 대한 중앙처리장치 할당 사이에서 버퍼(buffer) 역할을 함

3. 하위 단계 스케줄링(low level scheduling)

중앙처리장치가 다음 프로세스를 받아들일 수 있을 때 어떤 준비완료(ready) 프로세스에게
CPU를 차지할 수 있도록 할 것인가를 결정하고 이 프로세스에게 할당해 줌

하위 단계 스케줄링은 디스패처(dispatcher )에 의해서 매초 여러 번 작동(디스패처는 주기억
장치 내에 항상 적재되어 있어야 함)

방법 • 환경별 분류

1. 선점/비선점(preemptive/non-preemptive) 스케줄링

비선점

하나의 프로세스에 중앙처리장치가 할당되면 그 프로세스의 수행이 끝날 때까지 중앙처리장치는 그 프로세스로부터 빠져 나올 수 없음

짧은 작업들이 긴 작업들에 의해서 기다리게 되지만, 모든 프로세스들에 대한 대우는 공정

도중에 높은 우선순위의 작업이 입력되더라도 대기 중인 작업들이 영향을 받지 않으므로 응답 시간을 쉽게 예측할 수 있음

선점

하나의 프로세스가 중앙처리장치를 차지하고 있을 때 다른 프로세스가 현재 수행 중인 프로세스를 중지시키고 자신이 중앙처리장치를 차지할 수 있는 경우

높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용

실시간 시스템에서 인터럽트가 받아들여지지 않음으로써 발생하는 결과는 대단히 좋지 못한 것

대화식 시분할 시스템에서는 선점 스케줄링으로 빠른 응답 시간을 보장해 주는 것이 중요함

문맥 교환(context switching) 등으로 인한 오버헤드를 초래

선점을 효과적으로 하기 위해서는 많은 프로세스들이 주기억장치 내에 있어야 함

CPU가 사용 가능해질 때마다 준비완료(ready) 상태에 있는 프로세스가 있어야 함

2. 우선순위(priority) 스케줄링

각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방법

정적(static) 우선순위

실행이 쉽고 오버헤드 적음

주위 여건 변화에 적응 않고 우선순위 바뀌지 않음

동적(dynamic) 우선 순위

변화에 적응

각 프로세스에 부여된 처음의 우선순위는 필요에 따라 재구성되어 잠시 동안만 그 순위를 가질 뿐 다시 조정될 수 있음

오버헤드 많지만, 시스템의 응답도를 증가시켜 처리 효율을 높임

3. 기한부(deadline) 스케줄링

작업들이 명시된 시간이나 기한 내에 완료되도록 계획됨(실시간 시스템)

작업들의 결과가 시간 구간 내에 구해지면 매우 효용성이 높지만 제한 시간이 지난 후에 결과가 구해지면 쓸모가 없게 됨

적용이 어려운 이유

사용자는 사전에 작업이 요구하는 정확한 자원을 제시해야 하나, 그런 정보를 예측하기 어려움

시스템은 다른 사용자들에 대한 서비스를 감소시키지 않으면서 기한부 작업을 실행할 수 있어야 함

시스템은 기한까지 일을 끝내기 위하여 자신의 자원 안배를 주의 깊게 계획해야 하는데, 새로운 작업들이 계속 입력되고, 또 이러한 작업들이 시스템에 대하여 예기치 못한 요구를 하는 경우에 상당히 어려운 스케줄링이 요구됨

많은 기한부 작업들이 동시에 실행된다면 스케줄링이 너무 복잡해짐

기한부 스케줄링에 의해서 요구되는 집중적인 자원 운영은 많은 오버헤드를 초래

실시간 시스템의 종류

경성 실시간 시스템(hard real-time system)

중요한 태스크를 정한 시간 내에 완료할 수 있도록 해주는 강한 형태의 실시간 시스템

목적: 운영체제가 저장된 자료의 검색에서부터 시작하여 발생된 모든 요청을 완료할 때까지의 시스템 내의 모든 지연이 제한되도록 하는 데 있음
-> 이러한 엄격한 시간 제한은 경성 실시간 시스템에서의 스케줄링에 적용
-> 따라서 경성 실시간 시스템에서 사용되는 스케줄링은 라운드로빈 스케줄링의 동작과 상충되므로, 이 두 가지 스케줄링은 혼용될 수 없음

연성 실시간 시스템(soft real-time system)

시간적 제한이 다소 약한 형태의 실시간 시스템

중요한 실시간 태스크가 다른 태스크보다 높은 우선순위를 얻고, 태스크가 완료될 때까지 이 우선순위를 계속 유지

커널은 경성 실시간 시스템에서처럼 반응이 올 때까지 지연이 제한될 필요가 있다. 실시간 태스크는 커널이 그것을 수행하도록 무기한 기다릴 수 없음

Deadline 스케줄링을 지원하지 않기에, 산업용 제어나 로봇 공학에 사용되지 못함
-> 하지만 가상현실, 해저탐사 등과 같은 더욱 진보된 과학 프로젝트 등의 분야에 유용

연성 실시간 시스템은 다른 형태의 시스템과 혼용할 수 있도록 하는 것이 목표이다.

실시간 스케줄링 방식

정적 스케줄링 방식

시스템에 의해 실행되는 태스크의 집합이 미리 정의되어 있는 경우를 의미
-> 주기적인 연성 실시간 태스크 집합에 유용

동적인 스케줄링 방식

태스크의 발생 시간이나 특성을 미리 예측할 수 없을 경우에 유용하며, 태스크 발생이 가변적이어서 태스크 수는 실행 시에 정해짐

멀티미디어 시스템의 경우 긴급한 태스크가 보장된 주기의 시간 내에 서비스를 보장받기 위해서는 경성 실시간 스케줄링이 요구됨

RM(Rate Monotonic) 알고리즘

대표적인 정적 스케줄링 방식

각 태스크 주기가 짧을수록 더 높은 우선순위를 부여

태스크를 실행하는 프로세스들은 자신의 우선순위를 갖고 있으며 이 우선순위를 기준으로 높은 태스크가 먼저 스케줄링 됨

EDF(Earliest –Deadline First) 알고리즘

대표적인 동적 스케줄링 방식

임계 시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식

4. 다중 프로세서(Multiple Processor) 스케줄링

여러 개의 중앙처리장치가 사용 가능하게 되면, 스케줄링 문제는 더욱 복잡해짐

프로세서들의 형태

이질 시스템

각 프로세서는 자신의 큐가 있으며 자신의 스케줄링 알고리즘을 갖음

각 프로세서는 고유한 구조 형태를 가짐

해당 프로세서의 명령어로 작성된 프로그램은 그 프로세서에서만 실행

동질 시스템

부하 공유(load sharing)를 하게 됨

각 프로세서마다 별개의 큐를 제공하는 것이 가능하나 큐가 비어 있는 프로세서는 쉬게 되며, 다른 프로세서들은 매우 바쁘게 되므로 공동의 큐를 사용

프로세스들은 한 개의 공동 큐로 들어가서 실행 가능한 프로세서에서 스케줄 됨

스케줄링 방식

각 프로세서가 스스로 스케줄링하며, 공동 준비 큐를 조사하여 실행할 프로세서를 선택

한 프로세서가 다른 프로세서를 위한 스케줄러로서 지정되어 주-종 구조(master –slave structure)를 구성