pintOS - Alarm Clock. Explicit Global Tick 고찰

배경

• 대부분의 PintOS 자료에서 sleep_list를 매번 순회하지 않기 위해서 next_tick_to_awake(이하 ‘글로벌 틱’)라는 전역변수를 하나 더 지정하여 sleep_list의 tick 최소 값을 표시하도록 한다.[Explicit]
• 이를 위해서는, sleep_list 전체 순회(thread_awake)를 할 때마다 ‘글로벌 틱’을 갱신한다.
• 전체 순회를 조금이라도 줄이기 위해서는 sleep_list에 넣을 때부터 깨야 하는 tick의 오름차순으로 정렬되게 삽입하여, 순회 중 깨우지 못하는 쓰레드를 만나면 순회를 중단시킬 수 있다.
• 이를 좀 더 생각해보면, sleep_list의 첫번째 요소는 항상 ‘글로벌 틱’이므로 get_next_tick_to_awake가 이를 활용하게 작성할 수도 있다.[Implicit]

성능 고찰

• 삽입을 위한 함수 list_insert_orderd는 O(n)이다. 여기까지는 [Explicit]도 마찬가지 효용이 있다.
• [Explicit]을 구현하려면 awake가 끝났을 때 깨우지 못하는 쓰레드를 만났을 때, 해당 쓰레드의 awake_tick을 ‘글로벌 틱’으로 설정해준다. 이후 getter는 이 int형만 반환하면 된다. 새로운 thread가 잠들때도 '글로벌 틱'을 갱신한다.
• [Implicit] 구현의 경우 awake 중단 시에 아무것도 하지 않는다.(set을 안한다.) 이후 get 마다 sleep_list의 첫번째 요소로 접근해 elem을 가져온 다음 entry_list로 thread로 들어가 wake_tick을 반환하는 작업을 해야한다.

결론

• Implicit은 변수 선언이 없어서 얻을 수 있는 공간적 이득보다 시간적 손해가 훨씬 커 보인다.
• 추천하는 데는 다 이유가 있다.