Scheduling.md

이전 포스팅과 연결되는 부분이 많아서 이전 포스팅을 읽고 오면 이해하기 좋습니다.

이전 포스팅에서 운영체제의 스케줄링 방식과 Context Switching에 대한 글을 쓰겠다고 했다. 따라서 이번 포스팅의 주제로는 스케줄링 알고리즘을 선정했다.

스케줄링?

먼저 스케줄링이 무엇이고, 왜 이런 게 필요한지 알아보도록 하자. 사실 이번 글 뒷부분에서 언급할 여러 가지 스케줄링 알고리즘을 달달달 외우는 것보다 어쩌면 스케줄링이 왜 필요한지 그 이유를 아는 것이 더 중요할 수도 있다.

스케줄(Schedule)이라는 단어에서 알 수 있듯, 운영체제에서 말하는 스케줄링은 운영체제가 CPU의 자원을 어떤 프로세스에게 할당해 줄 지 그 일정을 짜는 것이라고 이해하면 쉽다. 이전 포스팅에서 언급했던 대로 프로세스 간의 Context Switching 과정은 많은 자원 손실을 발생시킨다. 따라서 이 일정을 어떻게 짰는지에 따라 CPU의 자원을 얼마나 효율적으로 사용하게 되는지가 결정된다. 한 마디로 스케줄링은 운영체제 입장에서 매우 중요한 과정이라고 할 수 있다.

Context Switching

본격적으로 스케줄링에 대해 설명하기 전에 Context Switching에 대해 알고 가야 할 필요가 있다. 방금처럼 단어 하나하나 생각해보자. Switch라는 단어의 뜻을 안다면 Context라는 단어를 모른다고 하더라도 "일단 그 Context라는 것을 Switching(교체, 전환)하는 것이겠구나" 하고 생각할 수 있을 것이다. 그럼 Context는 뭘까? 흔히들 '문맥'이라는 단어로 번역하는데 여기서는 이렇게 번역하는 것이 좋은 방법이 아니다. 운영체제에서 말하는 Context라는 건 문맥 같은 게 아니고 CPU가 프로세스를 실행하기 위한 (프로세스에 대한) 정보를 말한다. 더 자세히 말하면 Context는 현재 프로세스의 상태, 프로세스가 다음에 실행할 명령어, 레지스터 값, 프로세스 번호 등의 정보를 담고 있으며 이는 운영체제의 PCB(Process Control Block)에 저장된다. 왜 이 글 쓴 녀석이 문맥이라고 안 쓰고 계속 Context라고 귀찮게 영어로 썼는지 이제는 이해가 갈 것이다.

이전 포스팅에서도 언급했듯이 멀티프로세스 환경에서는 여러 프로세스가 동시에(?) 실행된다. 이 환경에서는 필연적으로 프로세스 간 CPU 자원 할당 이동이 일어날 수 밖에 없다. 이 이동 과정을 Context Switching이라고 하며, CPU는 기존 할당된 프로세스의 Context를 저장하고, 새로 자원을 할당할 프로세스의 Context로 교체하는 과정을 거치면서 자원을 새로운 프로세스에게 할당하게 된다. 여기서 주의해야 할 점이 있다. Context Switching 중에는 CPU의 자원이 어떤 프로세스에게 할당된 상태가 아니기 때문에 CPU가 아무 일도 하지 못 한다*****. 따라서 Context Switching 과정이 너무 자주 발생하면 오히려 CPU 성능이 떨어지게 된다.

스케줄링 궁금해서 들어왔더니 지금까지 스케줄링에 대한 설명은 하나도 안 나오고 Context Switching 얘기만 줄줄이 나와서 답답했을 수도 있다. 그러나 앞서 말했듯 스케줄링 알고리즘 달달달 외우는 것보다 왜 스케줄링이 필요한지 아는 것이 더 중요하다고 생각했기 때문에 이에 대해 설명하기 위해서 어쩔 수 없었다.

운영체제가 왜 있는걸까? 갑자기 왜 또 이걸 물어보는 건지 의아할 수도 있겠지만 결국 운영체제라는 건 컴퓨터가 효율적으로 일을 하게 만들기 위한 시스템이다. 그런데 방금 위에서 Context Switching 과정이 너무 자주 발생하면 오히려 CPU 성능이 떨어지게 된다고 언급했었다. 이 말은 바로 Context Switching 과정을 쓸데없이 자주 반복하지 않도록 하고, 필요한 순간에 적절하게 하도록 하는 알고리즘이 필요하다는 뜻이다. 그리고 이 알고리즘을 사용하는 주체가 바로 운영체제 스케줄러다. 드디어 Context Switching과 스케줄링이 연결되는 순간이다. 야호!

이해하기 쉽도록 설명하기 위해 어쩌면 잘못 설명했을 수도 있는 부분에 대해 보강하도록 하겠다. Context Switching 중에는 CPU의 자원이 어떤 프로세스에게 할당된 상태가 아니라고 했는데, 사실 할당이라는 단어를 썼지만 정확히는 프로세스가 점유 중이지만 사용 중은 아닌 상태다. 특정 프로세스에 의해 CPU 자원이 점유되고는 있는데, Context Switching 중이기 때문에 실제로 사용되는 프로세스가 없는 상태인 것이다. CPU가 아무 일도 하지 못한다는 것은 결국 CPU 자원을 아무 프로세스도 사용하지 못한다는 말이고 이는 오버헤드가 발생되었다는 뜻이다.

스케줄링 알고리즘의 종류

Context Switching을 할 때 새로 자원을 할당할 프로세스는 누가 결정할까? 자원을 달라는 프로세스는 엄청 많을 텐데, 어떤 프로세스에게 자원을 얼만큼 주어야 효율적으로 일할 수 있을까? 앞서 말했듯 이를 결정하는 정책을 만드는 것을 스케줄링이라고 한다. 프로세스 간 우선순위를 두고, Context Switching을 할 때 우선순위가 가장 높은 프로세스에게 CPU 자원을 할당해 주는 것이다. 이 우선순위를 결정하는 방법은 크게 두 가지로 분류할 수 있는데, 지금부터 그것들에 대해 알아보도록 하겠다.

비선점 스케줄링

비선점 스케줄링의 특징은 아래와 같다.

어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료될 때까지 다른 프로세스는 CPU를 사용할 수 없음.

프로세스가 CPU를 놓아주는 시점까지 스케줄링이 일어나지 않는다. 프로세스 일괄 처리에 적합하고 Context Switching을 최소화할 수 있다는 장점이 있다. 다만 긴급히 처리되어야 할 프로세스가 처리되지 못할 수 있다는 문제점이 발생할 수 있다.

FCFS (First Come First Service)

프로세스가 Ready Queue에 도착한 순서대로 CPU에 할당하는 방식이다. 작업 완료 시간을 예측하기 용이하다는 장점이 있다. 그러나 CPU 처리 시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있다. 이 상태를 호위 상태(콘보이 이펙트; Convoy Effect)라고 한다.

SJF (Shortest Job First)

프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다. 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식으로 알려져 있다. 그러나 CPU 처리 시간이 긴 프로세스는 전체 시스템 성능 향상을 위해 희생하며 계속 Ready Queue의 뒤로 밀려나기 때문에 무한정 기다려야 하는 상황이 발생할 수 있다. 이 상태를 기아 상태(스타베이션; Starvation)라고 한다.

HRN (Highest Response Ratio Next)

SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식이다. 우선순위를 단순히 CPU 처리 시간으로 결정하지 않고, Ready Queue에서 대기한 시간까지 고려하여 결정한다. 대부분 우선순위를 ((대기 시간 + CPU 처리 시간) / CPU 처리 시간)으로 결정한다. 이처럼 기다린 시간에 비례하여 우선순위를 높이는 기법을 에이징(Aging) 기법이라고 한다.

HRN 스케줄링 방식이 선점일 경우엔 우선순위가 높은 다른 프로세스들이 너무 자주 생기기 때문에 Context Switching이 너무 자주 발생한다. 이에 따라 스케줄러의 일이 너무 늘어나기 때문에 HRN 스케줄링 방식은 비선점 방식으로 이루어진다.

지금까지의 설명만 읽어봤다면 FCFS 스케줄링 방식을 사용할 하등의 이유가 존재하지 않는 것처럼 보인다. HRN 스케줄링 방식이 다른 비선점 스케줄링 방식에 비해 이상적으로는 훨씬 우월해 보이기 때문이다. 그러나 실제로 SJF, HRN 등의 방식을 사용하기 어려운 이유가 있는데, 현실적인 상황에서는 프로세스마다 CPU 처리 시간이 얼마나 걸릴지 알 수 있는 방법이 없기 때문이다. 이는 아래에서 설명할 SRT 스케줄링 방식에서도 동일하게 적용되는 부분이다.

우선순위 (Priority)

대기 중인 프로세스들에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리한다. 선점형으로도 구현할 수 있으며 여기서도 에이징 기법이 사용된다. 왜냐하면 우선순위가 낮은 프로세스에게 기아 상태가 생길 수 있기 때문이다. 우선순위는 정적 혹은 동적으로 부여될 수 있다. 동적으로 부여할 경우 구현이 복잡하고 오버헤드가 많다는 단점이 있으나, 시스템의 응답속도를 증가시킨다. 정적의 경우는 이 반대다.

선점 스케줄링

선점 스케줄링의 특징은 아래와 같다.

어떤 프로세스가 CPU를 점유하고 있을 때 우선순위가 높은 다른 프로세스가 점유를 빼앗아 CPU를 점유할 수 있음.

프로세스의 I/O 요청, I/O 응답, Interrupt 발생, 작업 완료 등의 특별한 상황에서 스케줄링이 발생한다. 긴급히 처리되어야 할 프로세스를 처리할 수 있다는 장점이 있지만 비선점 스케줄링 방식에 비해 Context Switching이 자주 일어날 수 있다는 단점이 있다.

SRT (Shortest Remaining Time)

SJF 스케줄링 방식을 선점 스케줄링 방식으로 변경한 기법. SJF 스케줄링 방식과 마찬가지로 프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다. 위에서 설명했던 SJF 방식과 동일해 보이지만, 선점 스케줄링 방식이기 때문에 CPU를 점유 중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 기존 프로세스의 CPU 점유를 빼앗아 점유할 수 있다.

우선순위 (Priority)

SJF와 SRT의 관계와 마찬가지로 비선점 우선순위 스케줄링 방식의 선점 방식인 선점 우선순위 스케줄링 방식이 있다.

라운드로빈 (Round-Robin)

FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식이다. 각 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 두고, 이 시간을 Time Quantum이라고 한다. 어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나면 이 프로세스로부터 CPU 자원을 회수하고, 이 프로세스를 Ready Queue의 가장 뒤로 보내는 것이다.

라운드로빈 스케줄링 방식에선 Time Quantum을 얼마로 둘 지 잘 결정해야 한다. 만약 Time Quantum이 너무 크다면, CPU 처리 시간이 긴 프로세스가 CPU를 오래 점유하며 정작 다른 프로세스들은 이 프로세스의 작업이 끝날 때까지 기다려야 하기 때문에 결국 FCFS 스케줄링 방식에서 발생하던 호위 상태가 또 발생하기 때문이다. 그렇다고 Time Quantum을 너무 작게 두면, Context Switching이 너무 자주 발생하기 때문에 오버헤드가 커진다.

다단계 큐 (Multi-Level Queue)

프로세스를 어떤 프로세스냐에 따라서 여러 종류의 그룹으로 나누고, 그룹마다 Queue를 두는 방식이다. 한 마디로 Ready Queue를 여러 개로 나누어 사용하는 방식이다. 각각의 Queue마다 서로 다른 스케줄링 방식을 적용할 수도 있다. 이 방식에 대해서 이해하려면 먼저 Foreground Queue와 Background Queue에 대해서 알고 가야 한다.

운영체제는 프로세스를 분류할 때 사용자와 직접 상호작용하는 프로세스와 백그라운드에서 돌아가는 프로세스의 중요도를 다르게 분류한다. 사용자와 직접 상호작용하는 프로세스는 빠르게 처리되어야 하고, 백그라운드에서 일괄 처리되는 프로세스의 경우 덜 빠르게 처리되어도 괜찮다고 분류하는 것이다. 사람들은 대부분 지금 내가 보고 있는 프로세스와의 상호작용이 빠르게 처리되기를 바라지 일단 켜두고 오래 방치한 프로세스와 상호작용하느라고 내가 보고 있는 프로세스에 렉이 걸리는 상황을 바라지는 않는다.

따라서 사용자와 직접 상호작용하는 프로세스가 모인 Foreground Queue에는 응답 시간을 줄이기 위해 라운드로빈 스케줄링 방식을 적용하고, 백그라운드에서 돌아가는 프로세스가 모인 Background Queue에는 응답 시간이 큰 의미가 없기 때문에 FCFS 스케줄링 방식을 적용하는 등 각 Queue마다 운영체제가 가장 적절하다고 판단하는 방식을 사용하게 된다.

위 사진을 예로 들어 이해해보자. 위 사진에서 대화형 프로세스를 담기 위한 Foreground Queue에는 라운드로빈 스케줄링 방식을 적용하고, 프로세스 일괄 처리가 필요한 Background Queue에는 일괄 처리에 적합하다고 했던 비선점 방식 중 하나를 적용하면 될 것이다.

다만 다단계 큐 스케줄링 방식은 여러 개의 Queue를 사용하기 때문에 고려해야 할 점이 하나 더 생긴다. 바로 어떤 Queue에 얼마나 CPU를 오래 할당할 지 결정하는 스케줄링이 필요하게 된다. 이 스케줄링은 크게 두 가지 정도를 떠올릴 수 있다.

고정 우선순위 (Fixed Priority)

Queue마다 우선순위를 두는 방식이다. 우선순위가 높은 Queue에 처리해야 할 프로세스가 남아 있다면, 무조건 그 Queue에 남아 있는 프로세스를 처리한 뒤에 다음 우선순위의 Queue를 서비스한다. 이 방식은 사용자가 직접 원하는 프로세스에 CPU 자원을 우선 할당하기 때문에 좋아 보이지만 SJF 스케줄링 방식처럼 결국 우선순위가 낮은 Queue에 있는 프로세스는 무한정 기다려야 하는 상황이 발생할 수 있다. 모두들 기억하겠지만 이런 상태를 기아 상태라고 한다.

타임 슬라이스 (Time Slice)

고정 우선순위 스케줄링 방식에서 기아 상태가 발생할 수 있기 때문에 이를 해결하고자 생긴 스케줄링 방식이다. 운영체제가 Time Slice를 두고, 이 시간 비율에 따라서 각각의 Queue를 서비스하게 된다. 예를 들어 CPU 자원의 75%는 Foreground Queue, 25%는 Background Queue를 서비스하는 데 할당할 수 있다.

다단계 피드백 큐 (Multi-Level Feedback Queue)

다단계 피드백 큐 스케줄링 방식은 다단계 큐 스케줄링 방식에 에이징 기법을 적용한 방식이다. 다단계 피드백 큐 스케줄링 방식에서는 다단계 큐 스케줄링 방식과 다르게 프로세스가 다른 큐로 이동할 수 있다. 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스의 우선순위를 점점 올려서 우선순위가 높은 큐로 옮겨주는 방식이다. 이를 통해 다단계 큐 고정 우선순위 스케줄링 방식에서 발생할 수 있었던 기아 상태를 어느 정도 해결할 수 있게 된다.

결론

이렇게 스케줄링이 왜 필요한지부터, 실제로 스케줄링이 어떤 방식으로 진행되는지까지 알아보았다. 지금까지 배운 내용을 요약해보자.

우리는 컴퓨터를 사용할 때 수많은 프로세스를 동시에 실행하게 된다. CPU는 한 번에 한 가지 작업만 처리할 수 있기 때문에, 이 프로세스들을 동시에 처리하(는 것처럼 보이게 하)기 위해 CPU는 어떤 프로세스에게 얼마나 많은 자원을, 얼마나 긴 시간 동안 할당해야 할 지 결정해야 한다. 프로세스를 빠르게 번갈아 처리해서 마치 동시에 프로세스가 실행되는 것처럼 보이게 하기 위해서다. 이를 결정하기 위한 방식, 즉 CPU 스케줄링 방식은 비선점, 선점 방식으로 분류할 수 있는 수많은 방식이 존재한다.

이전 포스팅에서 멀티스레드의 스케줄링은 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응할 수 있어야 한다고 언급했었다. 그러나 CPU 스케줄링은 멀티스레드와 다르게 운영체제가 사용자도 모르는 사이 자동으로 진행하는 작업이다. 이전 포스팅과 이번 포스팅 모두를 잘 이해했다면, 멀티프로세스와 멀티스레드의 원리적 차이부터 왜 프로세스와 스레드라는 방식으로 메모리를 공유하는지까지 어느 정도 알게 되었으리라 생각한다.

References

평범한개발자노트
Preamtree의 행복로그
양햄찌가 만드는 세상
기본기를 쌓는 정아마추어 코딩블로그

이미지 출처

pa324.log
윤자이 기술블로그