week08-10 2조 git repo

• https://github.com/JahunSeo/pintos-kaist/tree/master

참고자료

• https://web.stanford.edu/class/cs140/projects/pintos/
• https://oslab.kaist.ac.kr/pintosslides/
• https://oslab.kaist.ac.kr/ee415-spring-2020/

Alarm Clock

문제점

Pintos는 기본적으로 알람(alarm) 기능이 Busy waiting을 이용하여 구현돼 있다.

• Alarm : 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수

Busy waiting

Busy waiting : Thread가 CPU를 점유한 상태로 대기하여 소모전력 등 자원이 불필요하게 낭비되는 상황

개선방법

sleep/wake up

기존의 loop 기반 wait() 방식 대신 sleep_list(queue)를 만들어서 timer_sleep() 함수 호출 시 running 중인 thread를 blocked 상태로 만들고(ready_list에서 제거) sleep_list에 넣어준다.
그러고 timer interrupt가 발생하면 tick을 체크해서 시간이 다 된 thread를 sleep_list에서 삭제하고 ready_list에 넣어준다.

결과 확인

 pintos -- -q run alarm-multiple

busy waiting에서 sleep/wake up 방식으로 변경하면 결과적으로, idle ticks가 늘어나고 kernel ticks가 줄어든다. busy waiting 방식은 sleep 상태에서도 thread가 CPU를 점유하고 있기 때문에 idle상태가 될 수 없기 때문이다.

Priority Scheduling

문제점

기존 pintos 스케줄러는 RR으로 구현되어 있다. 그래서 ready_list에 삽입된 순으로 thread가 CPU를 점유한다.

• Round Robin : RR은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice)라 부른다. 작업이 완료될 때까지 이런 식으로 계속 진행되기 때문에 RR은 때때로 타임 슬라이싱이라고 불린다.

그렇기 때문에 thread의 우선순위(priority)를 고려하여 스케줄링 하도록 수정해야 한다.

개선방법

• ready_list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인(running) thread의 우선순위보다 높으면 기존 thread를 밀어내고 점유하도록 한다.

• 여러 thread가 lock과 semaphore를 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유한다.

• PRI_MIN : 0

• PRI_MAX : 63

• PRI_DEFAULT : 31

• thread_create() : thread가 ready_list에 들어가면 running thread와 우선순위를 비교한 뒤, 새로 생성된 thread의 우선순위가 더 높다면 thread_yield()를 통해 CPU 선점을 양보하도록 수정한다.

• thread_unblock() : thread가 unblock 될 때 push_back이 아닌 우선순위 순으로 정렬(ordered)한 후에 ready_list에 추가되도록 수정한다.

• thread_yield() : curr_thread가 cpu를 선점을 양보하여 ready_list에 삽입될 때 push_back이 아닌 우선순위 순으로 정렬(ordered)한 후 삽입되도록 수정한다.

• thread_set_priority() : thread의 우선순위가 변경되었을 때 우선순위에 따라 선점이 발생하도록 수정한다.

• test_max_priority() : ready_list에서 우선순위가 가장 높은 thread와 curr_thread의 우선순위를 비교하여 스케줄링(yield)해주는 함수를 추가한다.

• thread_compare_priority() : list_insert_ordered()에서 사용하기 위해 bool 타입의 함수를 추가한다. 첫 번째 인자(thread)의 우선순위가 높으면 1을 반환하고 두 번째 인자의 우선순위가 높으면 0을 반환한다.

결과 확인

# 먼저 test.c 파일에서 mlfqs 관련 테스트 라인을 주석처리 해야 함 먽 
make check

개선했다면 alarm-priority, fifo, preempt가 pass하게 된다.

Synchronization

문제점

기존 pintos는 waiters(semaphore를 대기하고 있는 theread list)가 FIFO로 구현되어 있다.

개선방법

여러 thread가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유하도록 해야 한다.

• sema_down() : semaphore를 얻고 waiters 리스트 삽입 시 기존 pushback이 아닌 우선순위를 기준으로 정렬(ordered)하도록 수정한다.

• sema_up() : thread가 waiters 리스트에 있을 때(waiting 중) 우선순위가 변경될 수도 있기 때문에 waiters 리스트를 내림차순(우선순위 높은 순)으로 정렬하는 코드를 추가해준다.

• sema_compare_priority() : semaphore element 구조체의 list elem 멤버를 인자로 받아 나머지 멤버인 semaphore에 속하는 thread의 prioity 사이의 우선순위를 비교하기 위해 함수를 추가해준다.

• cond_wait() : condition waiters 리스트에 기존 pushback이 아닌 cond waiters 의 element에 대응하는 쓰레드간의 priority 순서로 삽입되도록 수정한다.

• cond_signal() : condition waiters 리스트에 있을 때(waiting 중) 우선순위가 변경될 수도 있기 때문에 우선순위 기준으로 재정렬(list_sort())한다.

결과 확인

make check

위와 같이 개선한다면 priority-sema, condvar가 pass한다.

Priority Inversion Problem

문제점

우선순위가 높은 thread가 낮은 thread를 기다리게 되어 우선순위가 역전(Inversion)되는 현상이다.

개선방법

우선순위는 자기보다 낮은 thread지만 본인이 필요한 lock을 얻기 위해 일시적으로 낮은 thread의 우선순위를 높여줘서(donation) 해당 lock을 받는다.

• Multiple donation : donation 받기 이전 상태의 우선순위를 기억하고 있어야 한다.

• Nested donation : 필요한 lock과 연관된 thread들의 우선순위를 모두 높여준다.
  

• lock_acquire() : lock holder가 존재하면 현재 thread의 wait_on_lock 변수에 획득하기를 기다리는 lock의 주소를 저장한다. multiple donation을 고려하기 위해 이전상태의 우선순위를 기억하고 donation을 받은 thread를 thread 구조체 list로 관리한다. lock을 획득한 후 lock holder에는 curr thread를 넣어준다.

• donate_priority() : 최대 DONATE_MAX_DEPTH(nested depth)까지 우선순위를 양도하는 코드를 작성한다. wait_on_lock의 holder를 찾아서 holder의 우선순위를 업데이트 해준다. 이 때, holder의 우선순위보다 curr thread의 우선순위가 높은 경우에만 업데이트 해준다.

• remove_with_lock() : curr thread의 donations(리스트)를 확인하여 lock이 반환되기를 기다리는 thread를 제거하는 함수를 작성해준다.

• refresh_priority() : curr thread의 우선순위를 업데이트하는 함수로써, 이전 priority와 donations 리스트에 있는 우선순위와 비교하여 더 높은 값으로 업데이트 해준다. 이 때, donations 리스트를 우선순위 높은 순으로 정렬(list_sort)해서 begin의 우선순위를 확인한다.

• thread_set_priority() : curr thread의 우선순위가 donation에 의해 변경돼있을 수 있으므로 init_priority를 갱신해준다. 이후에는 refresh_priority()를 해준다.

결과 확인

make check

위 사항을 적용하면 priority-donate-one, multiple, multiple2, nest, sema, lower, chain이 pass하게 된다.