라운드 로빈 스케줄링 알고리즘을 구현해 봅시다.

 코딩 테스트를 개최하고, 다른 분들의 코드를 검토하다 보면, 어느 포인트에서 헤매시는지 알 수 있습니다. 이 중에, 가희와 은행은 면접 대비하시면 한 번 정도는 들어보셨을 법한 라운드 로빈 스케줄링을 물어본 문제입니다. 자세한 건 링크 참고하세요.

 

---

 이 문제에서 크게 어려워 할 만한 포인트는 없어 보였습니다. 저는 출제자였으니, 쉽게 생각했을 수도 있습니다. 그리고 이 정도는 os 수업 들으셨다면 과제로도 나올 법한 문제라 익숙했을 거라 생각했습니다. 그런데, 문제를 푸시는 분들 중 몇 분이 빠지셨던 함정이 있었습니다. 그 분들이 어떤 발상으로 접근을 하셨고, 어떤 부분 때문에, 잘못된 답을 도출했는지 복기해 보도록 하겠습니다. 그리고, 의도한 풀이를 설명하도록 하겠습니다.

 

 n명의 사람들은 0초일 때 오고, m명의 사람들은 은행이 문을 연 후에 오게 됩니다. 그래서, n+m명의 사람들을 들어온 순서대로 정렬한 다음에, 차례대로 큐에 넣고 빼면서 탐색한다. 여기서 제가 넣었던 조건은 은행이 문을 연 후에 온 사람들은 같은 시각에 둘 이상 오지 않는다. 였습니다.

 

 come_time은 은행에 들어온 시간을 의미합니다. time은 업무를 처리하는 데 필요한 시간을 의미해요. 그래서 cmp는, 은행에 들어온 시간 오름차순으로 정렬하게끔 만듭니다.

 

 

 다음에, n명의 사람들은 come_time이 0입니다. 다음 m명의 사람들은 come_time이 주어지는데요. 여기에서는 인위적으로 2i초에 들어왔다고 하였습니다. 그리고 27번째 줄에서 sort 메서드를 호출하였습니다. 잘 동작할 거 같습니다.

 

 

 그런데, 0번부터 n-1번까지 순서가 유지되지 않아서, assert가 실패합니다. 들어온 시간 별로 정렬하는 것은 맞습니다. 그런데, 간과하지 말아야 할 사실 중 하나는, 0초일 때 들어온 n명의 손님에 대한 정보는 대기 큐의 맨 앞에서부터 주어졌다는 것입니다. 제가 테스트 한 프로그램은 id가 1번부터 n번까지인 손님이 차례대로 서 있었다는 것입니다.

 

 

 즉, 노란색으로 칠한 부분은 come_time이 모두 같으므로, 우선 순위가 모두 같습니다. 노란색보다 하늘색이 우선 순위가 더 낮고요. 문제는, 우선 순위가 같은 것들의 순서가 변했느냐 안 변했느냐인데요.

 

 

 정렬이 된 후에 앞에 2개의 id만 뽑아보니까 133339, 133327이 되었습니다. 순서가 바뀌었음을 의미합니다.

 

 즉, 1번이 맨 앞에 있다는 정보가 사라집니다. 이렇게 되면 올바른 답을 구할 수 없게 됩니다. 원인이 무엇일까요? sort 함수는 stable 하지 않기 때문입니다. 처음 0초일 때 1번이 맨 앞에 있고, 399998번이 맨 뒤에 있었다는 정보를 유지하려면 어떻게 하면 될까요? 우선 순위가 같은 경우에, 정렬 전과 후에 배열 순서를 바꾸지 않으면 됩니다. 즉, stable sort를 이용하시면 됩니다.

 

27번째 줄에, stable_sort로 바꾸었습니다. 테스트 결과는 어떻게 될까요?

 

 

 통과가 됩니다.

 

---

 이제, 제가 의도한 풀이를 설명하겠습니다. 먼저, 대기 큐의 맨 앞에서 맨 뒤로 이동한다. 등이 있으므로, Queue를 이용하면 된다는 것은 쉽게 알 수 있습니다. 이 문제에서 처리해야 할 것은 크게 3가지입니다. 먼저, 10억초와 같이 매우 먼 미래에 들어오는 사람에 대해서는 어떻게 처리해야 할까요?

 

 문제에서는 20만초 정도까지만 알면 되므로, 은행에 온 시간이 20만초가 넘어가는 사람들에 대해서는 그냥 무시하시면 됩니다. 고객이 일을 처리하는 데 걸리는 시간은 1 이상이고, 정보를 알아와야 하는 시간동안 대기 큐가 빌 일은 없기 때문입니다. 20만초까지에 대한 정보가 필요하다면, 아래와 같이 설계하실 수 있습니다.

 

 

 여기서 ev[t]는 t초일 때 들어온 사람의 id를 의미합니다. 이 값이 -1이라면 들어온 사람이 없다는 것을, -1이 아니라면 들어온 사람이 있다는 것을 의미합니다. 도착한 손님이 대기 큐의 맨 뒤로 가는 것이, t초만큼 일을 처리하고 대기 큐의 맨 뒤로 가는 것보다는 먼저 일어나므로, 도착한 손님이 있다면, 대기 큐의 맨 뒤에 넣는 작업부터 수행해야 합니다.

 

 다음에는 어떤 것을 고려해야 할까요?

 

 먼저, 어떤 사람이 일을 끝내는 데 필요한 시간이 0만큼 남았다면 어떻게 해야 할까요? 이 경우에는 그냥 wait_Q에서 제거하면 됩니다. 왜냐하면, 해당 시점에서 그 사람이 일을 모두 마쳤기 때문입니다.

 

 

 만약에 대기 큐의 맨 앞에 있는 손님이 업무를 T초동안 처리했다면 어떨까요? 이 때에는 대기 큐의 맨 뒤로 가게 되므로, work_time을 0으로 초기화 하고 wait_queue의 맨 뒤로 보내버리면 됩니다.

 

 

 그리고 나서, 맨 앞에 있는 사람에 대해서 일을 1초 처리하면 됩니다. 그러면 맨 앞에 있는 사람은 일을 처리하는 데 필요한 시간이 1초 감소하고, 대기 큐의 맨 앞에서 일한 시간은 1초 늘어나게 됩니다. 제가 설명한 부분을 그대로 구현한 코드를 보겠습니다.

 

 

 처리 순서를 보시면, 유저가 들어온 경우부터 처리하였습니다. 예를 들어 i초일 때 id가 ev[i]인 유저가 들어왔다면 wait_q에 먼저 넣게 됩니다. 다음에, 맨 앞에 있었던 사람에 대해서 처리를 하는데요. 일 처리가 모두 끝났는지 먼저 검사하게 됩니다.

 

 

 다음에, 일 처리가 끝나지는 않았는데, 대기 큐의 맨 앞에 t초 동안 있었던 경우를 처리합니다. 만약에 맨 앞에 t초동안 있었다면, 대기 큐의 맨 뒤로 가야 합니다. 다음에, 1초 동안 대기 큐의 맨 앞에 있는 사람에 대해서 업무를 처리합니다. 48번째 줄에 업데이트라고 주석으로 달려있는 부분입니다. 22234번 문제에 대한 솔루션은 여기에 있습니다.

 

 만약에, 같은 시간에 여러 사람이 들어왔다면 어떻게  처리하면 될까요? 이벤트 배열을, 이벤트 list 배열로 만들면 됩니다. ev[t]를 t초에 들어온 사람들이라고 하면, 사람들은 list로 처리하면 되기 때문입니다.