작년 학교수업에서 CPU 스케쥴링에 대해서 한번 배웠다.
솔직히 디테일하게 들어가면 너무 어려워 뭔 소린지는 모르겠고 그냥 뭐 프로세스들에게 스케쥴을 짜주는거겠지 이 정도 느낌만 있었다. 하드웨어적인 부분은 확실히 재미가 없었다 ㅠㅠ
오늘 한번 파헤쳐 보자!

우선, 결론적으로만 말하자면 CPU 스케쥴링을 하는 이유는 무한하지 않은 한정된 자원을 효율적인으로 사용을 위한 이유라고 생각하면된다.

잠깐! 스케쥴링을 알기전에 컨텍스트 스위칭(Context Switching)을 알아야한다.
그 이유는 서로 밀접하게 관련이 되어있기 때문이다. 스케쥴링은 CPU를 사용하는 프로세스나 스레드를 선택하는 과정인데, CPU는 시간적으로 한번에 하나의 프로세스 또는 스레드만 실행할 수 있기 때문에, 여러개의 프로세스 또는 스레드가 실행되야할 때 이들 사이에서 우선순위나 작업량을 고려하여 CPU 시간을 분배하는 작업을 수행한다.
이때! OS는 현재 CPU를 점유하고 있는 프로세스나 스레드를 변경해야할 경우가 많은데 이 작업이 컨텍스트 스위칭이다. 컨텍스트 스위칭에 대해서 설명해보겠다.

컨텍스트 스위칭은 운영체제에서 CPU를 할당 하기 위해 실행중인 프로세스나 스레드의 상태 정보를 저장하고, 다음에 실행할 다른 프로세스나 스레드의 상태 정보를 읽어들어 CPU를 할당하면서 전환하는 과정이다.

컨텍스트 스위칭은 CPU에서 실행 중인 현재 프로세스나 스레드가 I/O 작업 등을 수행하거나, 인터럽트가 발생하거나, 프로세스나 스레드의 우선순위 등이 변경할 때 발생한다. 이러한 상황엔 운영체제는 해당 프로세스나 스레의 상태 정보를 PCB(Process Control Block)이라는 자료구조에 정보를 저장한다. PCB는 해당 프로세스나 스레드의 프로세스 ID, PC(Program Counter) 값, 메모리 주소공간, 스택 포인터, 레지스터 값 등을 PCB에 저장하며 이를 통해 다음 컨텍스트 스위칭에 복원되다어 이전 실행 상태를 유지하면서 계속 실행된다.

컨텍스트 스위칭은 수 없이 매우 빠르게 빈번하게 발생하여, CPU를 많이 사용하고 그에 따라 오버헤드도 발생할 가능성이 있어 직접적으로 성능에 미치는 중요한 요소 중 하나이다. 따라서 운영체제는 컨텍스트 스위칭의 최소화를 위해 다양한 기법을 사용한다.

몇 가지의 스케쥴링의 알고리즘이 있는데 어떤 알고리즘을 선택하는지, 프로세스나 스레드의 우선순위 결정, I/O 작업 처리 등이 OS 스케쥴링을 최적화 시키는 방법 중 하나이다. 이를 통해 CPU 사용률을 최적화 시키고 컨텍스트 스위칭을 최소화 시켜 시스템 성능을 향상 시킨다.

이러한 이유로 Context Swtiching을 할 때 어떤 프로세스 또는 스레드에게 CPU 점유를 하게 결정할지 많이 고민이 될것이다. 어떤 방식으로 CPU 사용권을 주는지 따라서 시스템 성능 차이가 좌지우지하기 때문이다. 이것을 결정하는게 스케줄링 알고리즘에 따라 바뀐다.

그럼 도대체 어떤 스케줄링 알고리즘이 있어?

운영체제에서 스케쥴링(Scheduling)은 CPU 자원의 사용을 조절하여 시스템의 성능을 최적화하는 프로세스이다. 이를 위해서는 여러 가지 알고리즘이 사용된다.

크게 비선점 스케줄링과 선점 스케줄링이 있다.

비선점 스케줄링에 대해서 설명하자면

비선점 스케쥴링 방식은 프로세스가 CPU를 할당 받으면 해당 프로세스가 완료될 때까지 CPU를 반환하지 않는다. 이 방식은 간단하고 구현이 쉽지만, 실행시간이 긴 프로세스가 CPU를 점유했을 때 독점할 위험이 있기때문에 다른 프로세스의 응답시간이 길어질 위험이 있다.

그럼 선점 스케줄링 알고리즘은 뭘까?

선점 방식은 프로세스가 CPU를 할당받아 점유하고 실행 중에 있어도, 다른 우선 순위가 높은 프로세스가 도착하면 점유 중인 CPU를 빼앗길 수 있는 방식이다. 이 방식은 응답 시간을 최소화 할 수있으며, 실시간 시스템에서 많이 사용된다.

이제 비선점 스케줄링이 어떤것이 있는지 보자

FCFS(First Come First Service)

이 방식은 자료구조를 공부한 사람이라면 큐가 떠오를 것이다. FIFO 방식인 큐와 사실 똑같은 로직이다. 프로세스가 Ready Queue에 도착한 순서대로 CPU에 할당하는 방식이다. 작업 완료 시간을 예측하기 용이하다는 장점이 있으나 CPU 처리 시간이 길고 별로 중요하지 않는 프로세스가 선점하고 있으면 뒤에 기다리는 중요한 작업이 기다리게 된다. 이러한 상태를 호위 상태(convoy Effect)라고 한다.

SJF(Shortest Job First)

프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다. 장점은 점유시간이 긴 프로세스가 자리 차지할 수 있는 FCFS 방식의 단점을 좀 더 개선한 점이라고 볼 수 있다. 평균 대기시간이 짧아지기 때문에 시스템의 응답 시간이 개선되고, 빠른 작업들이 먼저 실행되기 때문에 빠른 응답시간을 필요로하는 작업들의 성능이 개선이 된다. 하지만, 단점은 실행 시간을 예측할수 없는 작업이 많은 경우 오버헤드가 발생할수 있으며 불공평성을 초래할 수 있다. 그리고 CPU처리 시간이 긴 프로세스는 전체 시스템 성능 향상을 위해 Ready Queue 뒤에 계속 밀려나다 보면 무한정 기다려야하는 상황이 발생할 수 있고 이 상태를 기아 상태(Starvation)이라고 한다. 이 방식은 사실 선점 방식으로도 구현이 가능하다. 선점 방식으로 구현한 SJF를 SRT라고 부르는데 작업 중 우선순위가 더 높은(작업 시간이 더작은) 작업이 들어오면 점유중인 CPU를 뺴앗기며 교체한다.(이럴 때 context swiching)이 발생한다.)

HRN(Highest Response Ratio Next)

이 방식은 SJF 스케쥴링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식이다. 우선순위를 단순히 CPU 처리 시간을 결정하지 않고, Ready Queue에서 대기한 시간까지 고려한 것이다. 대부분 우선순위를 (대기 시간 + CPU처리 시간)/CPU 처리시간)으로 계산하여 결정한다. 이러한 방식을 aging(에이징)기법이라고 한다. HRN 방식 중 장점은 응답시간이 짧고, 대기 시간이 긴 프로세스에게 우선권이 부여되므로, 대기시간이 짧은 프로세스에 비해 응답 시간이 더 짧아진다. 그리고 높은 처리율을 보인다. HRN은 대기 시간이 긴 프로세스에게 우선권을 부여하므로, CPU 활용도가 높아져서 처리율이 향상된다. 우선순위가 공정하다. HRN은 대기 시간이 긴 프로세스에게 우선순위를 부여하지만, 다른 프로세스에게도 실행될 기회를 가질 수 있도록 공정성을 보여준다.
단점도 있다. 단점은 오버헤드가 크다. HRN 프로세스의 response ratio를 계산해야 하므로, CPU 오버헤드가 발생한다. 그리고 다음에 실행될 프로세스의 예측이 어렵다. response ratio를 계산해야하기 때문에 이전에 실행한 프로세스의 정보를 사용해야 하기 때문이다.

다음은 선점 스케줄링에 대해서

RR(Round Robin)

가장 기본적인 선점 스케줄링 알고리즘으로는 Round Robin(라운드 로빈) 방식이 있다. 이 방식은 FCFS 스케줄링 방식에 선전 스케줄링 방식과 Time Quantum(타임슬라이스)의 개념을 추가한 방식이다. 각 프로세스에 일정 시간(타임 슬라이스)을 할당하고, 그 시간이 지나면 다른 프로세스로 CPU 자원을 전환하는 방식이다. 그리고 CPU를 양도한 프로세스는 준비 큐 맨뒤로 이동하는 방식이다. 라운드 로빈 방식은 Time Quantum을 얼마로 둘지 잘 결정해야한다. 너무 크게 잡으면 FCFS 방식과 거의 동일하게 되므로 호위 상태가 또 발생하게 되며, 너무 작게 둔다면 context swticing이 자주 발생하기 때문에 오버헤드가 커진다.

SRT(Shortest Remaining Time)

SJF 스케줄링 방식에서 간단하게 설명했는데 SJF 스케줄링 방식에서 선점 스케줄링 방식으로 변경함 기법이다. CPU를 점유중이 프로세스보다 남은 CPU 처리시간이 짧은 프로세스가 준비 큐에 들어올 경우 실행 중인 작업을 뺏아와 점유할 수 있다.

다단계 큐(Multi Level Queue)

프로세스를 어떤 프로세스냐 따라 다수의 그룹을 나누고 각 그룹마다 Queue를 두는 방식이다. 즉, 준비 큐를 여러 개로 나누어서 사용하는 방식이다. 각각의 큐마다 서로 다른 방식의 스케쥴링을 둘 수 있다. 이러한 방식에 대해서 이해하려면 먼저 Foreground queue 와 Backgrond queue를 알아한다. OS 에서는 프로세스를 분류할 때 사용자와 직접 상호작용하는 프로세스와 백그라운드에서 돌아가는 프로세스랑 서로 중요도를 다르게 생각한다. 사용자와 직접적으로 상호작용하는 프로세스를 더 중요하게 여기고, 백그라운드에서 일괄처리가 되는 경우는 덜 중요하게 처리되어도 된다고 생각해서 서로 다르게 분류한다. 보통 Foreground queue에서는 라운드 로빈 스케줄링 방식이 적용되고 그 아래 Background queue에서는 FCFS 스케줄링 방식이 적용된다. 항상 그런 경우는 아니고 OS마다 다르니 참고하기 바란다.

결론

운영체제는 여러 개의 프로세스가 동시에 실행될 때, 수많은 문맥교환(Context Swtiching)이 일어나며 이로인해 오버헤드가 발생하기 쉬움으로 한정적인 자원에 대해 효율적으로 관리하고 시스템 성능을 높이기 위해 스케줄링이 필요하다.

스케줄링은 CPU에 할당되는 프로세스를 결정하는 알고리즘이며 프로세스가 요청한 CPU 시간을 조절하고, 다음에 실행될 프로세스를 결정하는 역할을 한다.

실제로 적용하는 알고리즘은 각각 프로세스의 특성, 운영체제의 목적에 따라 선택이되며, 시스템의 성능과 안정성을 보장하기 위해서 고려되어야한다. 또한, 보통은 다양한 스케줄링 알고리즘을 조합하여 사용하는 경우가 많다.