[OS] 스케줄링

폐프 2025. 1. 10. 11:40

CPU 스케줄링에 대해 알아보기 전,

지금의 CPU 스케줄링이 있기 전까지 어떤 방식의 스케줄링이 있었고, 결국에 어떤 평가 항목이 지금의 스케줄링을 만들었는지 알아보았다.

먼저 시스템에 실행중인 프로세스에 대해 가장 이상적인 가정을 하고 가정을 하나씩 제거하면서 스케줄링에 대한 역사를 알아보겠다.

가정

반환 시간이라는 개념을 도입한다. 반환시간은 작업이 완료된 시간 ~ 작업이 시스템에 도착한 시간의 차이다.

공정성이라는 개념은, 성능과는 상충되는 개념으로 성능 극대화를 위해 몇몇 작업을 중지시키면 공정성이 악화된다.

모든 작업이 동시에 도착한다면, 당연하게도 선입선출 스케줄링이 좋지 않은 이유는, 평균 반환시간이 좋지 않을 것이다.

작업 B가 시스템에 도착하더라도 긴 작업 A가 먼저 수행중이라면, B가 완료되기까지 오랜 시간이 걸릴 것이다.

가장 짧은 실행시간을 가진 작업을 가장 먼저 실행시키는 스케줄링이다.

모든 작업이 동시에 도착한다는 가정 하에, 반환 시간 측면에서 좋아보인다.

하지만 모든 작업이 동시에 도착한다는 가정을 없앤다면 무용지물이 될 것이다.

이역시 A가 실행중일 때 B와 C가 도착한다면 FIFO 스케줄링과 동일한 문제가 발생할 것이다.

시스템에 작업이 들어오면, 남아있는 작업과 새로운 작업의 잔여 실행시간을 계산해 짧은 작업을 우선 스케줄링한다.

반환 시간이라는 평가 기준에는 아주 훌륭한 기법이 된다.

위 두 기법의 문제점을 해결할 수 있게 된다. 하지만 여기서 새로운 평가 기준이 등장한다.

시분할 컴퓨터의 등장으로, 사용자는 터미널에서 작업하며 시스템과 원활히 상호작용하는 성능을 요구한다.

따라서 자연스럽게 응답시간이라는 새로운 평가 기준이 등장하게 된다.

응답 시간란, 작업이 시스템에 도착한 시간 ~ 작업이 처음 스케줄 될 때 까지의 시간을 뜻한다.

라운드 로빈이라고도 알려진 이 기법은 일정 시간동안 작업을 실행하고, 실행 큐의 다음 작업으로 전환한다.

여기서 작업이 실행되는 일정 시간을 타임 슬라이스라고 하며, 타임 슬라이스가 짧을수록 응답시간이 좋아질 것이다.

하지만 타임 슬라이스를 너무 짧게 설정 시 문맥 교환 비용이 전체 성능에 영향을 미치게 된다.

반환 시간이 유일한 측정 기준일 경우, 타임 슬라이싱은 최악의 정책이다.

공정성을 포기한다면 하나의 작업을 끝까지 실행하고 종료할 수 있지만, 나머지 작업에 대한 응답 시간은 포기해야 한다.

반대로 공정성을 더 중요시 여긴다면 응답 시간은 줄어들지만, 반환 시간이 나빠진다.

지금까지 크게 두 종류의 스케줄러를 보았다.

아직 완화해야할 가정들이 남아있다.

만약 모든 작업이 CPU만 사용한다는 가정을 완화해보자 (모든 프로그램이 입출력을 수행한다)

작업이 입출력 작업을 요청하면 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야한다.

현재 실행중인 작업은 입출력이 완료될 때 까지 CPU를 사용하지 않을 것이기 때문이다.

입출력 요청을 발생시킨 작업은 입출력 작업의 완료를 기다리며 대기상태에 빠지게 되는데, 만약 입출력이 하드 디스크 드라이브로 보내진 경우에는 프로세스가 긴 시간동안 블록될 것이다.

마찬가지로 스케줄러는 입출력 완료 시에도 의사결정을 해야한다. 완료 시 인터럽트가 발생하고, 운영체제가 실행되어 대기상태의 프로세스를 다시 준비 상태로 이동시킨다. (물론 즉시 실행시키는 것도 가능)

예시를 들어보자. 50msec의 CPU시간을 필요로하는 작업 A,B가 있고, 작업 A는 10msec마다 10msec의 입출력 요청을 한다.

위 그림처럼 스케줄링한다면, 딱봐도 CPU를 비효율적으로 사용하는게 보일 것이다.

따라서 이렇게 연산의 중첩을 통해 입출력 요청이 있는 프로세스들을 스케줄링하는 경우 CPU를 더 잘 활용할 수 있게 된다.

아직 완화해보지 않은 마지막 가정이 남아있다. 바로 스케줄러가 각 작업의 실행시간을 알고 있다는 가정이다.

하지만 범용 운영체제에서 이 가정은 말이 안되는 가정일 것이다.

그럼 스케줄러가 작업의 실행시간을 알지도 못하는데 우리가 위에서 본 스케줄링 기법들을 어떤 기준으로 활용해서

응답 시간과 반환 시간을 절충할 수 있을까?

바로 가까운 과거를 이용해 미래를 예측하는 멀티 레벨 피드백 큐라는 스케줄링 기법이 이러한 고민에서 등장한다.