CPU 스케줄링(2014, 9월모평A)

Photo by Caspar Camille Rubin on Unsplash

우리는 컴퓨터에서 음악을 들으면서 문서를 작성할 때 두 가지 프로그램이 동시에 실행되고 있다고 생각한다. 그러나 실제로는 아주 짧은 시간 간격으로 그 프로그램들이 번갈아 실행되고 있다. 이는 컴퓨터 운영 체제의 일부인 CPU(중앙 처 리 장치) 스케줄링 때문이다. 어떤 프로그램이 실행될 때 컴퓨터 운영 체제는 실행할 프로그램을 주기억 장치에 저장하고 실행 대기 프로그램의 목록인 ‘작업큐’에 등록한다. 운영 체제는 실행할 하나의 프로그램을 작업큐에서 선택하여 CPU에서 실행하고 실행이 종료되면 작업큐에서 지운다.

한 개의 CPU는 한 번에 하나의 프로그램만을 실행할 수 있다. 그러면 A와 B 두 개의 프로그램이 동시에 실행되는 것처럼 보이게 하려면 어떻게 해야 할까? 프로그램은 실행을 요청한 순서대로 작업큐에 등록되고 이 순서에 따라 A와 B는 차례로 실행된다. 이때 A의 실행 시간이 길어지면 B가 기다려야 하는 ‘대기 시간’이 길어지므로 동시에 두 프로그램이 실행되고 있는 것처럼 보이지 않는다. 그러나 A와 B를 일정한 시간 간격을 두고 번갈아 실행하면 두 프로그램이 동시에 실행되는 것처럼 보인다.

이를 위해서 CPU의 실행 시간을 여러 개의 짧은 구간으로 나누어 놓고 각각의 구간마다 하나의 프로그램이 실행되도록 한다. 여기서 한 구간에서 프로그램이 실행되는 것을 ‘구간 실 행’이라 하며, 각각의 구간에서 프로그램이 실행되는 시간을 ‘구간 시간’이라고 하는데 구간 시간의 길이는 일정하게 정한 다. A와 B의 구간 실행은 원칙적으로 두 프로그램이 종료될 때까지 번갈아 반복되지만 하나의 프로그램이 먼저 종료되면 나머지 프로그램이 계속 실행된다.

한편, 어떤 프로그램의 구간 실행이 진행되는 동안, 다른 프로그램은 작업큐에서 대기한다. A의 구간 실행이 끝나면 A의 실행이 정지되고 다음번 구간 시간 동안 실행할 프로그램을 선택한다. 이때 A가 정지한 후 B의 실행을 준비하는 데 필요한 시간을 ‘교체 시간’이라고 하는데 교체 시간은 구간 시간에 비해 매우 짧다. 교체 시간에는 그때까지 실행된 A의 상태를 저장하고 B를 실행하기 위해 B의 이전 상태를 가져온다. 그뿐만 아니라 같은 프로그램이 이어서 실행되더라도 운영 체제가 다음에 실행되어야 할 프로그램을 판단해야 하므로 구간 실행 사이에는 반드시 교체 시간이 필요하다.

하나의 프로그램이 작업큐에 등록될 때부터 종료될 때까지 걸리는 시간을 ‘총처리 시간’이라고 하는데 이 시간은 순수하게 프로그램의 실행에만 소요된 시간인 ‘총실행 시간’에 ‘교체 시간’과 작업큐에서 실행을 기다리는 ‘대기 시간’을 모두 합한 것이다. ㉠ 총실행 시간이 구간 시간보다 긴 프로그램이 실행 될 때는 구간 실행 횟수가 많아져서 교체 시간의 총합은 늘어난다. 그러나 총실행 시간이 구간 시간보다 짧거나 같은 프로그램은 한 번의 구간 시간 내에 종료되고 곧바로 다음 프로그램이 실행된다.

이제 프로그램 A, B, C가 실행되는 경우를 생각해 보자. A가 실행되고 있고 B가 작업큐에서 대기 중인 상태에서 새로운 프로그램 C를 실행할 경우, C는 B 다음에 등록되므로 A와 B의 구간 실행이 끝난 후 C가 실행된다. A와 B가 종료되지 않아 추가적인 구간 실행이 필요하면 작업큐에서 C의 뒤로 다시 등록되므로 C, A, B의 상태가 되고 결과적으로 세 프로그램은 등록되는 순서대로 반복해서 실행된다.

이처럼 작업큐에 등록된 프로그램의 수가 많아지면 각 프로그램의 대기 시간은 그에 비례하여 늘어난다. 따라서 작업큐에 등록할 수 있는 프로그램의 수를 제한해 대기 시간이 일정 수 준 이상으로 길어지는 것을 막을 필요가 있다.

― CPU 스케줄링