운영체제 5 - (Process Scheduling)

해당 정리는 youtube HPC Lab. KOREATECH의 OS 강의를 듣고 정리한 내용입니다.

강의 자료는 https://hpclab.tistory.com/1?category=887083 해당 링크에 있습니다.

 

목차

• 스케줄링 목적
• 스케줄링 기준 및 단계
• 스케줄링 정책
• 기본 스케줄링 알고리즘들

스케줄링 목적

여러 개의 프로세스가 시스템 내 존재하기 때문에 자원을 할당할 프로세스를 선택해야 하는데 이것을 스케줄링이라고 한다.

자원을 관리하는 것은 2가지 관점에서 바라볼 수 있는데 시간 분할 관리, 공간 분할 관리 이렇게 2가지 관점에서 볼 수 있다.

 

시간 분할 관리

하나의 자원을 여러 스레드들이 번갈아 가며 사용하는 것을 의미한다. 예를 들어 프로세서가 있다. 프로세서는 한번에 하나의 프로세스만 사용할 수 있기 때문이다.

 

공간 분할 관리

하나의 자원을 분할하여 동시에 사용하는 것을 의미한다. 예를들어 메모리가 있다.

 

스케줄링의 목적은 결국 시스템의 성능 향상을 목적으로 한다.

이러한 성능 향상의 대표적인 지표는 응답시간, 작업 처리량, 자원 활용도 가 있다.

응답시간이 중요한 대표적인 예로는 대화형 시스템, 리얼타임 시스템 이 존재한다.

작업 처리량이 중요한 대표적인 예로는 일괄처리 시스템이 존재한다.

자원 활용도가 중요한 대표적인 예로는 비싼장비를 사용하는 시스템이 존재한다.

 

이번에 알아볼 프로세스 스케줄링은 CPU를 할당받는 것을 스케줄링하는 것을 의미한다.

프로세스 스케줄링을 알아보기 전에 간단하게 용어를 알아보자

• Waiting time : 프로세스가 도착하고 실행까지 걸리는 시간을 의미한다.
• Response time : 프로세스가 도착하고 첫번째 출력까지 걸리는 시간을 의미한다.
• Burst time : 프로세스가 실행하고 종료할때까지 걸리는 시간을 의미한다.
• Turn-around time : 프로세스가 도착하고 실행이 종료될 때까지 걸리는 시간을 의미한다.

스케줄링 기준 및 단계

스케줄링 기법을 고려애햐 하는 항목에는 프로세스의 특성, 시스템 특성, 프로세스의 긴급성, 프로세스 우선순위, 프로세스 총 실행 시간 등등 존재한다.

이 중에서 프로세스 특성에 대해서만 간략하게 알아보자

프로세스 특성

프로세스 특성은 I/O bounded와 CPU compute-bounded로 나눠서 볼 수 있다.

 

I/O bounded : I/O 사용시간(I/O burst)이 더 많은 것을 의미한다.

CPU compute-bounded : CPU 사용시간(CPU burst)이 더 많은 것을 의미한다.

스케줄링 단계

스케줄링 단계는 발생한느 빈도 및 할당 자원에 따라 Long-term scheduling, Mid-term scheduling, Short-term scheduling 이렇게 3개로 구분할 수 있다.

 

Long-term scheduling

job scheduling이 이에 해당한다. job scheduling은 커널에 등록할 작업을 경정하는 스케줄을 의미하는데, 이는 발생 빈도가 매우 낮기 때문이다.

job scheduling은 다중프로그래밍 정도를 조절하는데 이 말은 시스템 내에 프로세스 수를 조절한다는 의미이다.

또한 I/O bounded 와 cpu compute-bounded를 잘 조절해야 하는데 한쪽만 넣게 되면 한쪽만 일을 하게 되는 것이고 이는 시스템 입장서는 비효율적 방식이기 때문이다.

 

Mid-term Scheduling

메모리 할당을 결정하는 것이 이에 해당한다. 즉 suspended ready 상태에서 ready 상태로 갈때 스케줄을 의미한다.

 

Short-term Scheduling

Process scheduling이 이에 해당한다. 즉, 프로세서를 할당할 프로세스를 결정하는 스케줄링이며, ready 상태에서 running 상태로 가는 것을 의미한다.

가장 빈번하게 발생하므로 매우 빨라야 한다.

위 그림은 스케줄링 단계를 표현한 그림이다.

스케줄링 정책

그럼 이제 스케줄링을 수행하기 위한 방법에 대해서 알아볼것이다.

우선 스케줄링 정책에 사용되는 개념으로는 선점/비선점, 우선순위가 존재한다.

 

Preemptive scheduling(선점), Non-Preemptive scheduling(비선점)이라고 하며, CPU를 뺏기지 않는 것을 Preemptive scheduling 뺏기지 않은 것을 Non-Preemptive scheduling이라고 한다.

또한 Priority(우선순위)를 스케줄링에 이용하기도 하다.(프로세스의 우선순위를 둬서 우선순위가 높은 것을 먼저처리)

Preemptive / Non-Preemptive scheduling

Non-preemptive scheduling

위에서 언급드린 것처럼 자원을 스스로 반납할 때까지 사용하는 것을 의미한다.

이를 통한 장점으로는 아무래도 CPU자원을 독점하기 위해 프로세스의 상태 변화가 적다. 이는 곧 Context switch overhead가 적은 장점이 있다.

반변 단점으로는, 우선순위를 먼저 처리하지 못하는 우선순위 역전이 발생하기도 하며, 프로세스가 자원을 반납할 때까지 사용하기 때문에 응답 시간이 증가한다.

 

Preemptive scheduling

위에서 언급드린 것처럼 타인에 의해 자원을 빼앗길 수 있다. 예를 들어 할당시간이 종료되었거나, 우선순위가 높은 프로레스가 오면 자원을 빼앗긴다.

이를 통한 단점으로는 프로세스의 상태가 자주 바뀌게 되고 이는 곧 Context switch overhead가 크다.

그러나 장점으로는 여러 하나의 프로세스가 종료될 때까지 동작하는 것이 아닌 타인에 의해 여러 번 바뀌므로 응답시간이 짧아지는 장점이 있다. 그래서 Time-sharing system, real-time system에 적합하다.

Priority

위에서 언급한 것처럼 프로세스의 우선순위(중요도)를 의미한다.

priority는 Static priority, Dynamic priority가 존재한다.

 

Static priority(정적 우선순위)

말 그대로 프로세스가 생성 시 우선순위가 결정되고 우선순위는 변하지 않는다.

Static priority의 장점으로는 구현이 쉽고, 우선순위가 정해져 있기 때문에 우선순위가 바뀌는 현상이 없기에 overhead가 적다.

단점으로는 시스템 환경 변화에 대해 적응이 어렵다 즉, 적응을 잘 못한다.(어떠한 프로세스가 중요해져도 해당 우선순위를 바꿀 수는 없음)

 

Dynamic priority(동적 우선순위)

프로세스의 상태에 따라 우선순위가 바뀔 수 있다.

단점으로는 우선순위가 바뀌는 프로세스이기에 구현이 복잡하고, 우선순위를 다시 계산을 해야 하기 대문에 그만큼 overhead가 크다.

반면 장점으로는 시스템 변화에 유연한 대응이 가능하다.

스케줄링 알고리즘

앞서 언급한 것처럼 스케줄링은 선점/비선점, 우선순위에 따라 정해진다. 지금부터 알아볼 것은 기본적인 스케줄링 알고리즘에 대해서 알아볼 것이다.

기본적인 알고리즘은 크게 7가지가 존재한다.

Basic Scheduling Algorithms

• FCFS(First-Come-First-Service)
• RR(Round-Robin)
• SPN(Shortest-Process-Next)
• SRTN(Shortest Remaining Time Next)
• HRRN(High-Response-Ratio-Next)
• MLQ(Multi-level Queue)
• MFQ(Multi-level Feedback Queue)

FCFS(First-Come-First-Service)

Non-preemptive scheduling으로 하나의 프로세스가 스스로 반납할 때까지 사용한다. FCFS 기준으로는 Ready Queue에 도착하는 기준을 잡는다. 즉, 선착순이라고 생각하면 된다.

위 방식의 장점으로는 자원을 효율적으로 사용이 가능하다 즉 블필요한 스케줄링이 없으므로 그에 따른 overhead가 적다. → Batch System에 적합하다. interactive System에 부적합하다. (반응이 느리기 때문)

단점으로는 프로세스를 하나씩 처리하기 때문에 응답속도가 느리고 Convoy effect가 발생한다.

Convoy effect란 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 가지게 되는 현상을 말한다.(대기시간 > 실행시간)

쉽게 생각해서 앞에 Burst Time(BT)이 긴 프로세스가 오게 되면 뒤에 BT가 짧은 게 있더라도 먼저처리하지 못하기 때문에 뒤에 있는 프로세스들은 실행시간보다 대기시간이 길다.

RR(Round-Robin)

preemptive scheduling 방식이다.

FCFS와 마찬가지로 Ready Queue에 도착하는 시간을 기준이어서 먼저 도착한 프로세스부터 시작한다. 다만 FCFS와 다른 점은 자원을 사용하는데 시간 제안이 존재한다(시간이 끝나면 자원을 반납해야 한다(preemptive scheduling)

이는 특정 프로세스가 자원을 독점하는 것을 방지할 수 있으나 프로세스 상태 변화가 많기 때문에 그만큼 Context Switch overhead가 크다.

RR은 시간제한마다 프로세스가 자원을 사용하는 방식이기 때문에 응답속도가 높기에 대화형, 시분할 시스템에 적합하다.

RR은 Time quantum 즉 제한시간을 얼마로 설정하느냐에 따라 성능이 결정된다. 만약 제한시간을 무한대에 가깝게 할 경우 FCFS와 같은 방식이 된다. 그렇다고 제한시간을 0에 가깝게 두면 High context switch overhead 가 발생한다.

FCFS, RR 방식 모두 공평성을 초점으로 맞춘 방식이다. 이제 다음 3가지 방식은 시스템 성능과 효율을 초점으로 맞추는 방식에 대해 알아볼 것이다.

SPN(Shortest-Process-Next)

Non-preemptive scheduling 방식이다.

이름처럼 Burst time(BT)이 가장 작은 프로세스를 우선적으로 처리하는 방식이다.

이에 따른 장점으로는 BT가 짧은 프로세스를 우선적으로 처리하기 때문에 평균 대기시간을 최소화할 수 있다.

또한 시스템 내 프로세스 수를 최소화 할 수 있기 때문에, 스케줄링 부하가 감속하게 되고 이는 메모리를 절약할 수 있어서 시스템 성능이 향상될 수 있다.

마지막으로 대기시간을 최소화 할 수 있기 때문에 많은 프로세스에게 빠른 응답 시간을 제공할 수 있다.

반면 단점으로는 Stavation 일명 기아현상이 발생한다. 이 현상은 프로세스가 무한 대기할 수 있는 현상을 의미하는데, BT가 긴 프로세스는 다른 프로세스가 들어올 때마다 우선순위가 밀리게 되고 즉, BT가 긴 프로세스는 자원을 받을 수 없다는 의미이다.

또한 프로세스의 정확한 BT를 알 수 없기 때문에 예측을 해야 한다.

SPTN(Shortest Remaining Time Next)

SPN의 변형으로 Preemptive scheduling 방식이다.

방법으로는 잔여 실행 시간이 더 적은 프로세스가 ready상태가 되면 선점되는 방식이다.

장점으로는 SPN의 장점을 더욱 극대화할 수 있다.

그러나 단점으로는 SPN과 같이 BT를 예측해야 한다. 또한 잔여 실행시간을 계속 추적해야 하는데 이는 Overhead가 발생할 수 있다.

마지막으로 Preemptive scheduling의 단점인 Context switching overhead가 발생한다.

SPTN방식은 구현 및 사용이 비 현실적이다.

HRRN(High-Response-Ratio-Next)

Non-preemptive scheduling 방식이다.

SPN의 변형으로 SPTN보다 조금 더 현실적인 SPN 변형이다.

SPN + Adging concepts가 합쳐진 것으로 여기서 말하는 Age는 나이를 의미하고 나이가 많을수록 배려하는 거와 볼 수 있다.

즉 여기서 말하는 Aging concepts는 프로시간의 대기 시간(WT)을 고려하여 자원을 할당받을 순서를 고르는 방식이다.

HRRN의 스케줄링 기준은 이름에서 적혀있는 거와 같이 Response ratio가 높은 프로세스를 우선적으로 하는데

Response ratio = (WT + BT) / BT이다. 즉 해당 연산을 응답률이라고 하는데 응답률은 BT대비 얼마나 기다렸는가를 의미한다.

위 방식의 장점으로는 SPN의 변형인 것처럼 SPN의 장점을 가지고 있고 또한 Stavation을 방지할 수 있다.

그러나 단점으로는 실행 시간 예측을 해야 하므로 Overhead가 발생한다.

SPN, SPTN , HRRN 3개의 방식 모두 결정적인 단점으로는 실행시간 예측에 대한 overhead가 발생하는 것이고 또한 실행시간 예측은 상당히 어렵고 정확하지가 않다.

이제는 이 문제를 해결할 수 있는 2가지 방식에 대해 알아볼 것이다.

MLQ(Multi-Level-Queue)

이름에서 보이는 Level Queue는 Ready Queue를 의미한다. 즉 여러 Ready Queue를 활용한 방식이라고 볼 수 있다.

작업 별 별도의 ReadyQueue를 가지고 한번 배정된 Queue를 벗어나지 못하는 것이 특징이다. 또한 각각의 Queue는 각각의 스케줄링 기법을 사용한다.

장점으로는 우선순위가 높은 Queue의 응답시간은 빠를 수 있다. 즉, 중요한 건 빠르게 처리해 낼 수 있다.

단점으로는 여러 개의 Queue를 관리하는 것은 기존보다 overhead가 발생할 수 있다.

또한 MLQ의 특징이 최조 배정된 Queue를 벗어나지 못하기 때문에 System이 변화할 경우 이에 적응을 못할 수 있다.

마지막으로 우선순위가 낮은 Queue 같은 경우 Stavation 현상이 발생할 수 있다.

MFQ(Multi-Level Feedback Queue)

MLQ 방식에서 프로세스가 Queue 간 이동이 가능한 방식이다.

즉 이름에서 나와있는 것처럼 피드백을 통해 우선순위 조정이 가능하다. 즉 System 변화에 적응을 잘한다.

이는 프로세스의 사전 정보 없이 SPN, SPTN, HRRN 기법의 효과를 볼 수 있다.

단점으로는 설계와 구현이 복잡하며 스케줄링에서 overhead가 발생할 수 있다. 또한 Stavation 문제 역시 발생할 수 있다.

MFQ 같은 경우 여러 변형이 있는데

1. 각각의 Queue에 할당시간 조정을 프로세스 특성에 맞는 형태로 시스템 운영이 가능하다.
2. 입출력 위주 프로세스를 상위 Queue를 올려서 응답시간을 높일 수 있다(I/O bounded가 높은 프로세스의 경우 CPU를 잠깐만 사용하기 때문)
3. 지정된 대기시간을 초과한 프로세스를 우선순위가 높은 Queue로 이동시켜서 Stavation 문제를 최소화할 수 있다