𝐎(𝟏) 스케줄러 구현

본 프로젝트는 Stanford University에서 개발된 교육용 운영체제인 Pintos의 Alarm-priority Test를 통과하기 위해 O(1) Scheduler를 구현하는 것이 목표입니다. 저는 이 수업에서 해당 테스트를 통과한 유일한 수강생으로, 최고점을 받았습니다.

O(1) Scheduler는 우선순위 단계의 수와 같은 크기를 가지며 Run Queue를 원소로 하는 2개의 배열로 구성됩니다. 두 배열은 각각 Active와 Expired 작업 목록을 나타냅니다. Active 배열에서 우선순위가 높은 Run Queue의 프로세스부터 CPU를 점유하며, Task가 끝난 프로세스는 Expired 배열로 이동됩니다. Active 배열의 모든 Run Queue가 비게 되면 두 배열이 교체됩니다. 비어있지 않은 Run Queue를 찾을 때, 배열을 순회하게 될 경우 O(N)이지만, Bitmap을 이용하면 O(1)으로 찾을 수 있게 됩니다.