Priority Inversion Problem

목표

• Priority donation 구현
• Multiple donation 구현
• Nested donation 구현

Priority Inversion Problem 발생

• 우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 현상
  

해결책

• Priority donation
  

Multiple donation

• 스레드가 두 개 이상의 lock 보유 시, 각 lock에 의해 도네이션이 발생 가능하다. 따라서 이전 상태의 우선순위를 기억하고 있어야 한다.

ex)

• 스레드 L(priority: 31)이 lock A와 lock B를 점유
• 스레드 M(priority: 32)이 lock A를 요청, 우선순위 도네이션 발생(스레드 L, priority = 32)
• 스레드 H(priority: 33)이 lock B를 요청, 다시 우선순위 도네이션 발생(스레드 L, priority = 33)
• 스레드 L이 lock B를 해지하여 스레드 L의 우선순위를 초기화(priority: 31)
  • 아직 lock A를 해지 하지 않았지만 우선순위가 31로 변경
  • 이전 상태의 우선순위 (스레드 M에 의해 도네이션 받은 priority: 32)를 기억 하고 있다가 스레드 L의 우선순위를 32로 변경 해야 한다.
    

Multiple donation 자료구조

Nested donation

• 스레드 H가 lock B(스레드 M 점유)를 얻기 위해 대기. 이때 스레드 M은 lock A(스레드 L 점유)를 얻기 위해 대기 하고 있다.
• 스레드 H의 우선순위는 스레드 L,M에게 모두 도네이션 되어야 한다.
  

Nested donation 자료구조

💻 구현하기

1. struct thread에 priority donation 관련 항목 추가

2. init_thread() 함수 수정

• Priority donation 관련 자료구조 초기화 코드 삽입
  

3. lock_acquire() 함수 수정

4. 구현할 함수 선언

5. donate_priority() 함수 추가

6. lock_release() 함수 수정

7. remove_with_lock() 함수 추가

8. refresh_priority() 함수 추가

9. thread_set_priority() 함수 수정

결과

✔ Project 1 회고

이번 핀토스 프로젝트 1을 진행하면서 이전 부터 진행해왔던 missing-semester와 OS study가 도움이 많이 되었다. 특히 OS study를 진행하면서 세마포어와 뮤텍스의 개념을 이해했던 것을 실제로 synchronization을 위해 lock을 걸고 wait list에서 BLOCK 시키는 등의 일련의 과정들을 직접 구현해 보면서 머릿속에 흩 뿌려져 있던 지식들을 한 곳에 모을 수 있었다.

1. Alarm system call에서는 인터럽트와 context switch에 대한 이해를 할 수 있었다.
2. priority scheduling에서는 우선순위에 따른 list를 정렬을 이용한 구현과 list를 어떻게 thread 구조체로 맵핑하는지 알 수 있었다.
3. priority scheduling with synchronizaion에서는 어떻게 semaphore에서 wait list가 관리되고 어떻게 lock을 acquire하며 특히 condition variable가 세마포어 wait list들을 어떻게 관리하는지 알 수 있었다.
4. priority donation에서 발생하는 lock 점유를 multiple donation과 nested donation을 이용하여 어떻게 리스트 들을 관리하는지 알 수 있었다.

이러한 내용들을 이해하고 구현하면서 Thread의 전반적인 프로세스를 이해할 수 있었다. 또한 구현을 위한 구조체들을 그림으로 정리해 보면서 Thread의 프로세스를 한눈에 이해할 수 있어서 좋았다.

무엇보다도 팀원과 함께 머리 맞대고 고민하면서 서로의 생각들을 공유하고 구현하고 정리하는 과정들을 통해 한층 성장하였다고 생각한다.