컴퓨터 스케줄링 알고리즘

OS-스케줄링

스케줄링

 

컴퓨터는 종종 다수의 프로세스 또는 스레드가 동시에 CPU를 사용하기 위해서 경쟁하는 경우가 발생한다. 이런 상황에서는 둘 또는 그 이상이 준비 상태인 경우에 항상 발생하게 된다. 단 하나의 CPU만 사용할 수가 있다면 다음에 실행할 프로세스를 선택해야만 한다. 이와 같은 선택을 하는 운영체제의 일부분을 스케줄러라고 부르며 스케줄러의 알고리즘을 스케줄링 알고리즘이라고 한다.

 

과거에 자기 테이프에 담긴 카드 이미지 형태로 입력을 받는 배치 시스템 시대로 되돌아가 보면 스케줄링 알고리즘은 상당히 단순했다. 테이프의 다음 작업만을 실행하면 되었다. 다중프로그래밍 시스템에서는 보통 서비스를 기다리는 여러 명의 사용자가 있기 때문에 스케줄링 알고리즘은 훨씬 더 복잡하다. 몇몇 메인 프레임에선 여전히 배치와 시분할 서비스를 혼합해서 사용하고 스케줄러는 배치 작업, 그리고 터미널에서 작업하는 대화식 사용자 중 어떤 것을 먼저 서비스해야 하는지 선택해야 한다.

 

개인용 컴퓨터의 등장으로 상황은 다음과 같이 크게 두 개의 형태로 바뀌었다. 첫째로, 대부분의 경우 하나의 활성화된 프로세스만 존재한다. 사용자가 워드 프로세서에서 문서를 입력하는 동시에 백그라운드로 프로그램을 컴파일하는 경우는 잘 없다. 워드프로세스가 유일한 후보인데 사용자가 워드프로세스에서 입력하는 동안 스케줄러가 다음에 어떤 프로그램을 실행할지 판단하는 것은 상당히 쉽다.

 

둘째로, 컴퓨터는 해마다 급속도로 발전해서 더 이상 CPU가 희소성을 띄지 않는다. 개인 컴퓨터에서 수행하는 대부분의 프로그램들은 CPU 속도의 제약을 받기보다는 사용자가 입력하는 속도에 제한을 받는다. 심지어 과거에 CPU 사이클을 소요하는 주된 원인이었던 컴파일까지도 대부분의 경우 요즘은 몇 초 정도밖에 걸리지 않는다.

 

두 개의 프로그램이 동시에 실행하고 있는 경우라고 해도 어느 것이 먼저 수행하는지는 그다지 중요하지 않는데 이는 사용자는 두 프로그램이 모두 끝나기를 기다리기 때문이다. 결론적으로, 단순한 PC에서 스케줄링은 그다지 문제가 되지 않는다.

 

네트워크 서버로 살펴보면 훨씬 더 변화를 빠르게 감지할 수가 있다. 이 경우 다수의 프로세스가 자주 CPU를 놓고 경쟁하기 때문에 스케줄링이 다시 문제가 된다. 예를 들어 일일 통계를 수집하는 프로세스와 사용자 요청을 서비스하는 프로세스 중 다음에 CPU에서 수행될 프로세스를 골라야 한다면 후자를 선택해야 사용자를 훨씬 더 행복하게 만들 것이다.

 

프로세스간 문맥교환은 다소 높은 비용이 동반되기 때문에 다음에 수행할 적당한 프로세스를 선정하는 것 외에 스케줄러는 CPU를 효율적으로 사용하도록 관심을 기울일 필요가 있다. 문맥교환을 위해 먼저 사용자 모드에서 커널 모드로 전환되어야 한다. 그리고 연이어 나중에 재적재할 수 있도록 하기 위해서 프로세스 테이블에 레지스터를 저장하는 것을 포함해서 현재 프로세스의 상태를 저장해야만 한다. 많은 시스템에서 메모리 맵도 역시 저장되어야만 한다.

 

다음으로 스케줄링 알고리즘을 실행해서 새 프로세스를 선택하고, 새로운 프로세스의 메모리 맵을 MMU로 다시 적재한다. 끝으로, 새로운 프로세스가 수행을 시작한다. 이 모든 것들 외에도 프로세스 간 문맥 교환은 모든 메모리 캐시를 무효화하여 두 번 이들이 다시 동적으로 적재되도록 만든다. 전체적으로 초당 프로세스 간 문맥 교환 횟수가 너무 많으면 문맥 교환이 CPU 시간의 상당 부분을 소비하게 되므로 주의해야 한다.

 

거의 모든 프로세스는 한동안 계산을 수행하다가 다시 한동안 I/O를 요청하는 행동을 반복하곤 한다. 보통 CPU는 한동안 계산을 수행하다가 파일을 읽거나 쓰기 위해 시스템 호출을 진행한다. 시스템 호출이 완료되면 다시 데이터가 필요하거나 데이터를 기록해야 할 때까지 CPU는 계산을 수행하며 이러한 과정이 계속 반복된다고 보면 된다. 일부 I/O 행위는 계산으로 간주되기도 한다. I/O는 외부 장치가 작업을 마칠 때까지 프로세스가 대기 상태로 있음을 의미한다.