[KAIST PintOS Project 1] 3. synchronization

synchronization

 

지난 단계에서는 선입선출의 queue 구조였던 ready_list를 스레드의 priority에 따르는 heap 구조로 바꾸어 보다 효율적인 스케줄링을 하도록 개선했다.

 

그런데 이와 같은 아이디어로 똑같은 개선이 가능한 list가 둘 더 있다. 바로 세마포어의 waiters와 컨디션의 waiters이다. semaphore.waiters는 semaphore를 갖기 위해 대기중인 스레드를 elem으로 갖는 list이고, cond.waiters는 condition을 갖기 위해 대기중인 semaphore의 list인데, 둘 모두 개선 전의 ready_list처럼 선입선출의 구조를 갖고 있다. ready_list때와 마찬가지로 이는 우선도가 높은 스레드가 낮은 스레드를 기다리는 문제를 유발한다.

그렇다면, 이전 단계와 똑같은 방법으로 관계된 스레드의 우선순위를 비교하여 이 두 리스트의 구조도 heap으로 개선할 수 있을 것이다. (실제로 구현하는 과정도 거의 같다.)

 

 

순서 6

 

먼저 이전 단계의 CMP_priority(a, b)와 같은 기능을 수행하는 함수 CMPsem_priority(a, b)을 정의한다. 두 list_elem a, b로부터 스레드를 따와서 둘의 priority를 비교하여 TF를 리턴하는 기능은 완벽히 같지만 새로 정의하는 이유는, list_elem에 entry를 씀으로써 바로 스레드의 포인터를 취할 수 있었던 앞의 상황과는 다르게, cond.waiter의 경우 전처리가 더 필요하기 때문이다.

 

cond.waiter에는 세마포어가 줄서있고, 이 리스트를 줄세우기 위해서는 각 세마포어의 waiters의 가장 앞에 있는 스레드끼리 우선도를 비교해야 할 것이다. 세마포어가 condition을 취할 경우 가장 먼저 실행될 스레드이기 때문이다.

이를 구현하기 위한 과정은 아래와 같다.

cond.waiter list에 들어오는 원소는 스레드의 list_elem이 아니라 세마포어의 list_elem이다. 즉, 두 list_elem a, b에 대해 list_entry를 취할 경우 나오는 원본 스트럭쳐는 스레드가 아니라 세마포어가 된다. 그렇기 때문에 기존 CMP_priority처럼 여기에 대해 ->priority를 요구한다면 에러가 날 것이고, 대신 이 세마포어에 대해 ->waiters->list_bigin->priority의 세 단계가 더 거침으로써 스레드를 추출할 수 있게 된다.

 

 

순서 7

 

CMPsem_priority(a, b)을 구현했다면 나머지는 이전 단계와 똑같다. 선입선출로 리스트에 넣던 라이브러리 함수를 정렬된 위치에 삽입하는 insert_ordered로 바꾸면 된다. 이때 sema는 바로 스레드를 추출 가능하니  CMP_priority를 쓰고, cond의 경우에는 CMPsem_priority를 써야 할 것이다.

 

순서 8 ~ 10

 

여기까지의 구현으로 모든 삽입은 정렬된 상태로 이루어지게 된다. 그런데 이전 단계와 마찬가지로, 삽입 뿐 아니라 기존 리스트에 있던 원소의 값 변화로도 정렬상태는 깨질 수가 있다. 그렇기 때문에 cond_signal을 하는 순간에도 cond.waits을 한번 정렬해준 뒤 sema_up해야 최신화된 정렬상태대로 부여가 가능하고, cond.waits 안의 각 세마포어의 waits에 대해서도 정렬해야 최신화된 정렬상태대로 스레드를 실행할 수 있을 것이다.

마지막으로, sema_up을 마친 뒤에는 새로 unlock된 스레드에게 curr가 yeild해야하는지 체크하는 기능을 추가하는 것으로 synchronization의 구현이 끝난다. 이걸 못찾아서 몇시간을 헤맸다...