[pintOS] Project1-4. Priority Inversion Problem

📅 기간 : 2021.02.08(월) ~ 2021.02.10(수)

1. 과제 목표

1-1. 문제 상황

우선순위가 높은 쓰레드가 우선순위 낮은 쓰레드를 기다리는 현상인
Priority inversion 문제를 해결하자!!

문제 상황

L이 락을 점유하고 있는데, H가 와서 락을 요청한다면 현재 상황에서는 L이 락을 반환할때까지 H가 waiter에서 대기해야 한다.
근데 만약 H가 대기하고 있는데, 락을 필요로 하지 않는 스레드 M이 등장한다면, L은 M에게 CPU를 넘겨주고, M과 L이 모두 실행된 후에야 H가 실행된다.
우선순위대로 스레드를 실행시켜주고 싶은 우리에게 이 상황은 그야말로 우선순위 역전 상태이다.

1-2. 솔루션

솔루션

우선순위가 높은 H가 자신이 락을 요청하면서 L에게 자신의 우선순위를 기부해준다.
그러면 M이 등장했을 때, L이 밀리고 M이 실행되버릴 일도 없고, L이 다 실행된 후에 H가 실행될 수 있다.

2. 배경지식

Donation 방식에는 multiple donation, nested donation 이렇게 두가지가 있다. 나는 donation이 너무 어렵고 헷갈려서 완전 반대로 개념을 이해한 적도 있었고, 고생을 많이 했다. 그러다가 유튜브에서 이 영상을 보고 priority donation을 완전히 이해해버렸다. 핀토스 priority donation에서 고통받고 있는 분들은 꼭 이 영상을 봤으면 좋겠다.
유튜브 pintos donation 1,2,3
5분씩 3편으로 이루어진 강의인데, 반드시 들으면서 직접 그려보고 생각해볼 것을 추천!

2-1. Multiple donation

스레드가 두개 이상의 lock 보유 시, 각 lock에 의해 도네이션이 발생 가능하다. 그러므로, 이전 상태의 우선순위를 기억하고 있어야 한다!
예시는 위 영상을 보면 아주 잘 나온다.
이 상황에서 스레드, 락 구조체를 도식화해보면 아래 그림과 같다.

2-2. Nested donation

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

이 상황에서 스레드, 락 구조체를 도식화해보면 아래 그림과 같다.

헷갈린다면! 반드시 영상을 보고오자! 삶이 행복해진다!

3. 회고

리스트가 너무 많아서 헷갈렸다.
세마포어 안의 waiters list, 도네이션끼리 연결하는 d_elem, 나한테 기부한 애들 관리하는 donations list 등.. 원래도 스레드들이 리스트 구조체로 관리되었는데 donation list까지 추가되면서, 순회하며 찾을 때 elem을 사용해야하는지 d_elem을 사용해야하는지 구분을 못해서 힘들었다.
하지만, donation 관련된 경우 모두 d_elem을 이용한다는 것을 차차 알게 됐고, 하다보니 익숙해졌다. 글이나 말로 보면 할 게 많지 않아보이지만, 직접 구현해보면 따줘져야하는 사항들이 꽤 많다. 쉽지 않은 과제였다..
만약 pintos donation 유튜브 강의를 몰랐다면 나는 아직도 donation을 제대로 이해하지 못했을 것이다. 참담하고 막막할 땐 반드시 찾아보는 습관을 들이자!
정말 많이 고생했지만, 결국은 해냈다! 뿌-듯