비선점 스케쥴링(Non-preemptive Scheduling) 🔗
비선점 스케쥴링(Non-preemptive Scheduling)은 프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때까지 계속 그 자원을 사용하도록 허용하는 정책이다. 적용할 때는 현재 프로세서를 사용하는 프로세스가 생성되거나 현재 프로세스 작업을 종료할 때 입출력하기 위해 스스로 프로세서를 반납할 때까지 우선 순위가 높은 프로세스의 비선점 정책을 적용하면 프로세스의 종료 시간을 비교적 정확하게 예측할 수 있다.
설명하기 전에 🔗
프로세스가 입출력 중심의 대화형 프로세스인지, 프로세서 실행 중심의 프로세스인지를 먼저 구분하는 것이 스케쥴링 정책을 적용하는 단계의 첫 번째이다. 물론 두 가지 특성은 상호 배타적이지 않기 때문에 입출력 중심이면서 프로세서를 많이 사용하는 프로세스일 수 있다. 가령, X Window Server의 경우 프로세서와 입출력 모두를 많이 사용한다. 워드프레스의 경우도 마찬가지이다. 보통은 키 입력을 기다리고 있지만 철자법 검사나 매크로 계산 같은 복잡한 기능을 사용하는 순간에는 프로세서를 많이 사용한다.
스케쥴링의 목적 상충되는 두 가지 목적을 달성하는 것이 스케쥴링의 목적이다. 프로세스 응답시간을 빠르게 하는 것과 시스템 사용률을 최대화하는 것이 그것이다. 이런 모순된 요구사항을 만족시키기 위해 스케쥴러는 복잡한 알고리즘을 사용해 우선순위가 낮은 프로세스에게 공정함을 보장하면서도 순간순간 실행 가치가 가장 높은 프로세스를 선택한다.
비선점 스케쥴링 정책 종류 🔗
정책(Policy)은 스케쥴러가 무엇을 언제 실행할 것인지를 정하는 동작을 말한다. 스케쥴러의 정책을 통해 시스템의 전체적인 느낌이 정해지는 경우가 많으며 프로세서 사용 시간을 최적화하는 책임이 있기 때문에 매우 중요하다.
아래부터는 비선점 스케쥴링 정책 각각에 대해 좀 더 자세히
기술한다. 처음 문서 작성 시에는 스케쥴링의 알고리즘이라고 기술했지만
정책(policy)이라는 용어가 더 적합하여 수정하였다.
1. 우선순위 스케쥴링(Priority Scheduling) 🔗
우선순위 스케쥴링은 간단하다. 각각의 프로세스에 우선순위가 있고 이 우선순위를 판별하여 우선순위가 더 높다고 판단되는 프로세스가 가장 먼저 프로세서를 할당받는다. 프로세스 우선순위는 커널이 결정하거나 커널 외부에서 결정하기도 하며, 우선순위를 나타내는 값이 작은 수를 지향하는지 큰 수를 지향하는 지는 운영체제에 따라 다르다.
이런 우선순위 스케쥴링의 가장 큰 문제점은 기아 현상이다. 나중에 소개할 SJF(Shortest Job First)에도 공통적인 문제로서 우선순위가 상대적으로 낮은 프로세스가 계속해서 실행되지 못하는 현상이다.
예를 들어, 아래와 같이 각 프로세스에 우선순위가 할당되어 있다고 가정해보자.
이를 해결하는 기법은 에이징(Aging) 기법으로, 일정 시간이 지나면 기아 상태에 빠질 것으로 예상되는 프로세스의 우선순위를 높이는 기법이다.
2. SJF(Shortest Job First), SRTF(Shortest Remaining Time First) 🔗
출처의 내용을 정리한 것이다. 원래 SJF만을 다루려 했지만 SRTF라는 정책이 추가로 정리되어 있기에 포스팅에 추가하였다.
SJF(Shortest Job First)는 CPU의 Burst Time이 짧은 프로세스에게
프로세서를 우선 할당하는 정책이다. 중요한 것은 Burst Time을
이용한다는 점으로, 프로세스의 전반적인 실행시간이 아니라 실제로
프로세서를 이용하는 시간이 가장 짧은 프로세스부터 실행하여 효율을 높인
정책이다. 만약 스케쥴링 대상의 프로세스들이 모두 같은 Burst Time을
갖고 있다면 FCFS(First-Come-First-Served) 정책을 따른다. FCFS에
대한 설명은 바로 다음에서 기술하겠다.
SRTF(Shortest Remaining Time First)는 SJF에 선점 정책을 도입한 것이라 이해한다. 아래 다이어그램은 SJF(Shortest Job First)를 이용했을 때의 결과이다. 우선순위와 마찬가지로 기아 현상이 나타날 수 있기 때문에 Aging 기법을 이용하여 해결 가능하다.
아래는 SRTF 스케쥴링을 같은 프로세스에 적용할 때를 나타낸 것이다. SJF(Shortest Job First)와는 다르게 P1 실행 도중 P2, P3, P4가 선점하여 실행되는 것을 확인할 수 있다. 하지만 여기서 예상할 수 있듯이 잦은 프로세스 잔여 실행시간을 계산해야 하고 이에 따른 컨텍스트 전환이 발생하면 그로 인한 오버헤드가 증가할 수 밖에 없다. 따라서 현실적으로 구현 및 사용이 어려운 정책이다.
3. FCFS(First-Come-First-Served), FIFO Scheduling 🔗
가장 간단한 스케쥴링 정책이다. 프로세서를 먼저 요청한 프로세스에게 할당하는 방식이다. 비선점인 데다 실행 순서에 대한 정책이 없어 스케쥴러 큐에 들어온 순서대로 프로세스를 실행한다. 너무 간단하기 때문에 여기에 대한 별도의 다이어그램은 추가하지 않겠다.
4. 기한부 스케쥴링(Deadline Scheduling) 🔗
Deadline 스케쥴링 정책은 실시간을 위한 비선점형 스케쥴링 정책이다.
실시간 시스템에서 “Correct behavior"란 논리적인 행동 뿐만 아니라 사용자 또는 시스템이 원하는 deadline 이내에 결과를 도출하는 것이다. 만약 설정한 deadline 이내에 결과를 도출하여 전달하지 못한다면 시스템은 결함이 있다고 보여질 것이다.
특히 리눅스와 같은 멀티태스킹 운영체제에서 realtime schedular는 모든
실시간 작업들이 deadline 안에 끝나는 것을 보장해야 한다. 그리고 이러한
타이밍에 대한 요구사항을 만족시키기 위해서 리눅스에서는 두 가지
스케쥴러를 제공하는데 바로 POSIX Realtime Schedular와 Deadline Schedular가 그것이다.
Deadline 스케쥴러는 EDF(Earliest Deadline First) + CBS(Constant
Bandwidth Server) 알고리즘 기반으로 동작한다. 처음 UP 시스템용으로
구현되었다가 SMP 시스템에서는 이를 더 발전시켜 각 CPU의 earliest deadline을 관리하고 다른 CPU로 전달하여 더욱 효과적으로 스케쥴링한다.