스케쥴링 알고리즘

프로세스 실행 순서를 정하는 알고리즘이에요. 이렇게만 말하면 이해하기 어려우니 우선 미리 알아둬야하는 개념이 있어요. 그것부터 알아봐요.

프로세스

프로그램 실행 단위입니다. 메모리에 올려져 실행 중인 프로그램을 말하죠. 프로세스와 응용 프로그램을 혼용하는 경우가 있는데, 프로세스와 응용 프로그램은 서로 다른 개념이에요. 왜냐하면 응용 프로그램은 여러 개의 프로세스가 상호작용하면서 실행될 수 있기 때문이에요.

스케쥴러와의 관계는?

그리고 CPU 스케쥴러는 이 프로세스의 실행을 관리해요. 각 프로세스가 CPU의 자원을 어떻게 사용할지에 대한 '스케쥴'을 지정하는거죠.

알고리즘 종류

자 그럼 다시 돌아와서 스케쥴링 알고리즘은 어느 순서대로 프로세스를 실행시킬지는 정하는 것이라 했어요. 순서 알고리즘을 정해야 하는 이유는,

1. 프로세스 응답 시간을 가능한 짧게 하기 위해서에요.
2. CPU의 활용도를 최대한 높여서 프로세스를 빨리 실행하기 위해서에요.

이제 어떤 알고리즘들이 존재하는지 알아봐요.

그전에 알아야할 개념(feat. 선점/비선점, 프로세스 상태)

알고리즘을 선점형 스케쥴러와 비선점형 스케쥴러로 분류할 수 있어요. 그리고 프로세스는 이러한 스케쥴러로 인해 상태가 바뀌게 되요. 이에 대해 먼저 알아봐요.

프로세스 상태

New, Exit

처음 프로세스가 생성New 상태와 종료Exit 상태가 있어요.

Ready

CPU에서 실행 가능 상태에요. 즉, 실행 대기 상태죠.

Running

현재 CPU의 자원을 점유한 상태, 즉 실행 중이죠.

Block(Wait)

특정 이벤트가 발생해서 실행 중인 상태를 멈춘 대기 상태에요. 대표적인 예가 프로세스가 저장매체에 접근하는 경우에요. C언어로 치면 파일 입출력 함수인 fopen 함수가 있어요.

프로세스 상태간 관계

프로세스 상태의 관계는 아래와 같은 흐름을 가지고 있어요.

상태 관계
1. 프로세스가 특정 작업(ex. 파일 처리)을 처리하거나 순서를 뺏기면 Block 상태로 변해요.
2. 스케쥴러는 다른 Ready 상태 프로세스를 Running 상태로 만들어 CPU에서 해당 프로세스를 수행시켜요.
3. 이후에 스케쥴링 알고리즘으로 인해 Running 상태의 프로세스를 Ready 상태로 바꾸고 다음 프로세스를 Ready에서 Running 상태로 만들어요.
4. 여기서 Block 상태였던 프로세스가 특정 작업을 완료하게 되거나, 본인 순서가 오면 해당 프로세스 상태를 Ready 상태로 변환시켜요.

프로세스 상태에 대해 정리해봤어요. 이제 선점형과 비선점형 스케쥴러에 대한 개념을 알아봐요.

선점형(Preemptive)

하나의 프로세스가 다른 프로세스 대신에 프로세서CPU를 차지할 수 있는 스케쥴러에요. 이때 CPU 자원을 뺏긴 프로세스 상태를 Running에서 Block 상태로 바꾸게 되요.

비선점형(Non-preemptive)

하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수가 없어요. 즉, CPU 자원 점유 중인 프로세스 상태가 Block 또는 Exit 상태가 되어야만 스케쥴러가 나타나서 다른 프로세스를 점유시켜요.

스케쥴링 알고리즘을 이해하기 위한 선수 개념은 여기까지에요. 이제 알고리즘에 대해 알아봐요.

FCFS(First Come First Served)

프로세스가 저장매체를 읽거나 프린팅하는 등 작업 없이 쭉 CPU를 처음부터 끝까지 사용해요. 점유 중인 프로세스가 종료될 때까지 계속 점유하는 알고리즘이에요. 배치 처리 시스템과 유사하고 가장 간단한 알고리즘이에요. 해당 알고리즘은 비선점형이에요.

SJF(Shortest Job First)

프로세스 실행 시간이 가장 짧은 프로세스부터 실행시켜요. 비선점형 알고리즘이며 실행 시간이 큰 프로세스는 뒤로 밀려 수행되지 않는 단점이 존재해요.

우선순위 기반 알고리즘

프로세스에 우선순위를 매겨서 높은 순서대로 CPU에 실행시키는 알고리즘이에요. 우선순위는 정의하기 나름이고 2가지 종류가 있어요.

정적 우선순위

프로세스마다 우선순위를 미리 지정하는 방식이에요.

동적 우선순위

프로세스가 상황에 따라 우선순위를 동적으로 변경해요. 상황은 많지만 몇 가지를 말하자면,

동적 우선순위
1. 응답시간이 빨라야하는 시스템의 경우 우선순위로 높여요.
2. 프로세스 우선순위가 너무 낮아 응답시간이 느린 경우, 에이징 기법을 통해 대기 시간이 길수록 우선순위를 점점 높여요.

우선순위 기반 알고리즘은 선점형 알고리즘에 속해요.

Round Robin

CPU 점유 시간을 지정해서 프로세스가 해당 시간동안만 작업해요. 시간이 되면 프로세스를 RR Ready Queue에 넣고 다음 프로세스를 해당 시간 동안 작업하는 것을 반복하죠. 시분할 시스템 기반 알고리즘이에요.

이 알고리즘은 점유 시간을 정할때 주의해야 해요. 점유 시간이 너무 길면 FCFS 알고리즘처럼 프로세스 점유 시간이 너무 길어져 비효율적이고, 점유 시간이 너무 짧으면 점유 프로세스 교체 과정에서 발생하는 오버헤드, 문맥 교환(Context Switching)이 자주 발생하게 되요.

알고리즘 조합

CPU 스케쥴링 알고리즘에 대해 알아봤어요. 그리고 이 알고리즘들은 하나만 사용하는게 아니라, 상황에 따라 조합해서 사용해서 효율성을 높여요. 예를 들면 이런 거죠.

스케쥴러 정책

• Round Robin 스케쥴링 정책
  • 100ms 마다 다음 프로세스로 교체
  • Ready Queue, Running Queue, Block Queue 존재
  • 각 Queue 는 FIFO 정책으로 동작함
• 선점형 스케쥴링 기능 지원

보다 이해하기 쉽게 예제를 통해 알아봐요.

예제
1. CPU에서만 실행하는 A, B, C 프로세스가 Ready Queue 에 A,B,C 순서대로 들어간 상태임
2. 각 프로세스가 총 실행해야 하는 시간은 다음과 같음
3. A 는 200ms, B 는 500ms, C 는 300ms
4. 파일 I/O는 발생하지 않음

이를 전제로 수행한 결과는 아래와 같아요.

우선 파일 I/O는 발생하지 않고 오로지 CPU에서만 실행하기 때문에 Block 큐에 들어가는 프로세스는 존재하지 않아요. Round Robin으로 수행하고 100 ms 단위로 교체를 수행하니 위와 같은 방식으로 진행하게 됩니다.

강의 들을 때 시험 그대로 베꼈어요. 예제 만들기 어렵...;

스케쥴링 알고리즘과 이를 이해하기 위한 선수 개념에 대한 정리는 여기까지입니다!