어떻게 누구를 먼저 부를까

누구를 먼저 부를까

창구는 하나인데 기다리는 사람은 여럿이다. 한 번에 한 명만 부를 수 있으니 누구를 먼저 부를지 정해야 한다. 먼저 온 사람일까, 볼일이 금방 끝날 사람일까, 급한 사람일까?
이렇게 부르는 순서를 정하는 일이 스케줄링이다. CPU 앞에도 일들이 줄을 서 있어서, 누구를 먼저 처리할지 누군가 정해 줘야 해요.
응급실이나 은행 창구가 누구를 먼저 부를지 늘 고민하는 것과 똑같은 문제다.

자리는 하나, 기다리는 일은 여럿. 부르는 순서를 정한다.

순서를 바꾸면 기다림도 바뀐다

똑같은 손님 셋이 있다. 한 명은 일이 길고, 둘은 짧다.
위쪽은 온 순서대로 부른다. 긴 일이 맨 앞이면 뒤의 짧은 둘은 그 일이 끝날 때까지 한참 기다린다. 아래쪽은 짧은 일을 먼저 부른다. 짧은 둘이 금방 끝나고 긴 하나만 남는다.
손님도 일도 똑같은데 순서만 바꿨더니 모두가 기다린 시간의 평균이 달라졌어요.
긴 일을 앞에 두면 뒤에 선 사람마다 그 긴 시간을 고스란히 기다려야 해서 평균이 확 늘어난다.

같은 셋이라도 부르는 순서에 따라 평균 기다림이 달라진다.

직접 순서를 정해 본다

손님 넷이 기다리고, 저마다 일의 길이가 다르다.
부르는 순서를 바꾸면 아래에 모두가 기다린 시간의 평균이 바로 나온다. 짧은 일을 앞에 두면 평균이 줄고, 긴 일을 앞에 두면 평균이 는다.
이리저리 바꿔 가며 어떤 순서가 평균을 가장 줄이는지 찾아보자.
사실 남은 일 가운데 늘 가장 짧은 일을 먼저 부르는 것이 평균 기다림을 가장 낮추는 방법이에요.

순서를 바꿀 때마다 평균 기다림이 어떻게 변하는지 보인다.

빠른 것이 늘 좋지는 않다

짧은 일만 계속 먼저 부르면 평균은 준다. 그런데 일이 아주 긴 손님은 차례가 계속 밀려 한없이 기다릴 수도 있다.
그래서 다른 방법도 있다. 한 명에게 몰아주지 않고 모두에게 조금씩 번갈아 기회를 주면 아무도 끝없이 밀리지 않는다.
대신 자주 번갈면 그만큼 자리를 바꾸는 비용이 든다. 빠름과 공평함 가운데 무엇을 고르든 공짜인 선택은 없어요.
곧바로 반응해야 하는 영상 통화와 조금 늦어도 되는 큰 파일 내려받기를 다르게 대접하듯, 상황마다 저울질이 달라진다.

짧은 일 우선은 빠르지만, 긴 일이 계속 밀릴 수 있다.

한 장으로 정리

기억할 것은 셋이다.
첫째, 스케줄링은 부르는 순서를 정하는 일이다. 자리는 하나고 기다리는 일은 여럿이기 때문이다.
둘째, 순서를 바꾸면 평균 기다림이 바뀐다. 짧은 일을 앞세우면 평균이 준다. 셋째, 그래도 정답은 하나가 아니다. 빠름과 공평함은 맞바꿔야 하고, 자주 번갈면 바꾸는 비용도 든다.
순서를 아무리 잘 정해도 없던 시간이 새로 생기지는 않는다. 그 기다림을 누구에게 얼마나 나눠 지울지 정할 뿐이에요.

순서가 평균을 바꾸고, 빠름과 공평함은 맞바꾼다.