우선순위 스케줄링 aging 처리를 구현해 봅시다.

 제가 세터였던 대회 문제들 중에서는 가희와 프로세스 시리즈가 있었습니다. 문제 제목을 보면 알 수 있듯, 해당 문제들은 cs 과목도 같이 복기하시면서, 코딩 테스트도 같이 준비하면 좋겠다고 생각해서 출제하게 되었습니다. 무엇을 물어보려고 저는 이 문제를 냈을까요? 눈치가 빠르신 분들은 아셨을 지도 모르겠지만, 영상에서 언급된 aging에 대해서 냈음을 알 수 있습니다. 여기서 조금 더 나가서, 상황을 일반화 시킬 수 있는지 묻기 위해서, 7번과 8번 문제도 같이 냈습니다.

 

---

 기술 면접을 준비하시기 위해서 cs 과목들을 보셨다면, 우선순위 큐를 들어보셨을 겁니다. 문제에서 우선순위가 가장 높은 것을 선택한다는 것이 언급되었으니, 먼저 의심해 봐야 할 것은 우선 순위 큐를 써야 하나? 입니다. 혹은 정렬을 쓸 수도 있습니다. 문제는, 1초마다 스케쥴러가 우선 순위가 가장 높으면서 id가 가장 작은 것을 선택해서 실행시킨다는 것입니다. 선점형 스케쥴링인 셈입니다.

 

 게다가 아래 조건까지 붙어 있습니다.

 

 업데이트가 일어난다는 조건이 붙어 있으므로, 정렬 전처리는 탈락입니다. insert, delete 등의 업데이트가 일어날 때, 우선 순위를 빠르게 판단할 수 있는 priority queue를 어떻게 잘 쓰냐로 바뀌었는데요. 나머지 프로세스들의 우선 순위가 1 증가한다는 조건이 있습니다. 이런 이상한 조건은 왜 붙어있을까요?

 

 이 문제에서는 스케쥴러가 처리하는 도중에 새로운 task를 처리해야 할 일이 없습니다. 그러니, 모든 프로세스는 언젠가는 실행을 끝낼 수 있게 됩니다. 그런데, 중간에 새로운 task가 들어오는 경우에는 어떨까요?

 

 P는 우선순위, T는 프로세스가 실행을 마치는 데 필요한 시간이라 해 봅시다. 처음에 우선 순위가 20이고, 실행을 끝내는 데 필요한 시간이 5인 프로세스 1과, 우선 순위가 3이고, 실행을 끝내는 데 필요한 시간이 5인 프로세스 2가 들어왔습니다.

 

 

 4초가 지난 후에, 또 다시 우선 순위가 20이고, 필요 시간이 5인 것이 들어왔다 해 봅시다. 1번이 실행을 끝낸 후에는 2번이 아니라 3번 프로세스가 올라가게 됩니다.

 

 

 이 상태에서 4초가 지난 후에, 똑같이 실행을 마치는 데 필요한 시간이 5이면서 우선 순위가 20인 녀석이 들어왔다고 해 봅시다. 또 똑같은 상황이 반복될 겁니다. 이런 경우가 계속 반복되면, 우선 순위가 3인 프로세스는 priority가 높은 process에 밀려서 계속 실행되지 못하는 상황이 발생합니다. 이를 starvation이라고 합니다.

 

 

 y=3 그래프하고 y=20 그래프를 생각해 보면 쉽습니다.

 

---

 이러한 상황을 방지하기 위해 aging이라는 기법을 씁니다. 이 문제에서는 실행 되지 않은 프로세스는 1초가 지날 때 마다 우선 순위가 1씩 증가한다고 주어졌습니다.

 

 

 처음 상황은 같습니다. 그런데, P가 3이고 T가 5인 것은 4초 동안 실행되지 않습니다.

 

 

 이 프로세스의 우선 순위는 3에서 7로 바뀝니다. 실행 되지 않았기 때문입니다. 4초가 지난 시점에서, 우선 순위가 20이고 T가 5인 것이 새로 들어왔는데요. 1초가 지나면 이것도 우선 순위가 21이고, T가 5인 것으로 바뀔 겁니다.

 

 

 5초가 지난 상황입니다. 이 시점으로부터 다시 4초가 지난 후에, P가 20이고 T가 5인 것이 새로 들어왔다고 해 보겠습니다.

 

 그러면 그림은 위와 같이 그려질 겁니다. 핵심은, 처음에 priority가 3이였던 것이 12로 증가했다는 점입니다.

 

 

 우선 순위가 낮았던 프로세스가 오랫동안 실행이 안 되었다면, aging이 됨에 따라 우선 순위가 높아질 겁니다. 천천히라도 증가한다면, 언젠가는 20보다는 높아질 겁니다. 없을 때와 다른 점이 명확합니다. 없을 때에는, 우선 순위가 3인 건 계속 실행이 안 되도 여전히 3이였기 때문에, 3보다 높은 것이 계속 들어온다면 실행이 안 되었습니다. 그 부분과 비교하시면 됩니다.

 

---

 이제 문제를 풀어 봅시다.

 

 이것을 어떻게 바꾸면 될까요? 계속 실행이 안 된 프로세스를 기준으로 삼으면 됩니다. 어짜피, T초 동안 프로세스는 T번 실행이 될 것이기 때문입니다. 계속 실행이 안 된 프로세스를 기준으로 삼으면, 실행이 된 프로세스는 우선 순위가 1 감소하는 것과 동치임을 알 수 있어요. 상대 속도와 비슷한 개념인가요? 어떻게 보면 비슷한 개념일 수도 있겠습니다.

 

 예를 들어, 아래와 같은 상황을 생각해 봅시다.

 

 우선 순위가 21, 6, 20인 것이 있었어요. 21인 것이 선택될 겁니다.

 

 1초가 지난 후에 나머지가 하나씩 증가했어요. 그런데, n이 10만개라면 우선 순위가 변경되는 프로세스 갯수가 너무 큽니다. 대신에, 우리는 프로세스들의 우선 순위의 상대성이 중요합니다. 정확한 값을 몰라도 됨을 알 수 있습니다. 1번과 2번의 차이가 14, 1번과 3번의 차이가 0이였다는 사실에 주목해 봅시다. 그렇다면, 이렇게 시뮬레이션 하면 어떨까요?

 

 실행된 프로세스의 우선 순위가 하나 감소한다. 얼핏 보면 다른 것 같지만, 사실 동일한 상황임을 알 수 있어요. 1번과 2번의 차이와 1번과 3번의 차이를 보면 이 경우도 14, 0이 됩니다. 결론적으로, 프로세스가 선택해서 실행한 프로세스는 우선 순위를 하나 감소시키면 됩니다.

 

 그런데 원래는, 특정 시점에 우선 순위가 p이고, 실행을 마치는 데 필요한 시간이 t인 프로세스가 들어오는 상황까지 추가하려고 했습니다. 이 경우까지 추가되면 어떻게 해야 할까요?

 

 

 똑같이 생각하시면 됩니다. 우선 순위가 0인 프로세스가 계속 실행이 되지 않았다고 생각해 봅시다. 그러면 y=x꼴로 우선 순위가 올라갈 겁니다. 이것과의 상대적인 거리를 생각하면 되는데요. 5초일 때, 우선 순위가 20인 프로세스가 넣어졌다고 해 봅시다. 이것은 0초일 때 우선 순위가 0이였던 프로세스가, 계속 실행이 안 되었다면 해당 프로세스는 priority가 5가 되었을 겁니다.

 

 5하고 20하고 상대적인 거리는 15입니다. 따라서, 5초일 때, 우선 순위가 20인 프로세스가 들어온 이벤트는 단지, 우선 순위가 15인 것이 들어왔다고 처리하면 됩니다. 일반화 시켜서, t초일 때, 우선 순위가 p인 것이 들어온 이벤트는 priority가 p-t인 것이 들어왔다고 처리하시면 됩니다. 남은 것은 자료 구조를 잘 이용하는 것입니다.