PintOS project01-3) priority Inversion Problem & donation
문제 상황
-
H 스레드는 L의 작업이 끝날때 까지 lock을 얻지 못해 기다리는데 L 작업 중 M에 의해 선점당하면서 H는 더 오랜 시간을 기다려야 한다.
-
H 스레드가 M 스레드보다 우선 순위가 높은 상황인데도 위와 같은 상황에서 우선 순위가 더 낮은 M 스레드가 먼저 처리되는 불합리한 상황이 벌어진다.
http://jake.dothome.co.kr/priority-inheritance/
해결 방법
- H 스레드가 자신의 우선순위를 실행 중인 L 스레드에게 기부해서 L이 실행을 완료한 후에 공유자원을 반납하면 우선순위에 의해 H가 cpu를 선점할 수 있게 만들어 줘야한다.
- 주의해야할 점은, 스레드가 두 개 이상의 lock(공유자원)을 보유하고 있을 경우 각 lock에 의해 여러번 donation을 받을 수 있다.
- 여러개의 lock을 보유하고 있을 경우, 하나의 lock을 반환하고나서 남은 lock에 의해 donation받은 우선순위를 기억하고 있어야한다.
- 이 부분을 해결하기 위해서(doantion 받은 우선순위를 기억하기 위해서) thread 마다 각각의 donations 리스트를 가지고 있도록 수정해주었다.
구현을 위해 고려해야하는 상황
init_priority : donation을 받기 전 원래 가지고 있던 우선 순위
wait_on_lock : 해당 스레드가 기다리고있는 lock
donations : 해당 스레드에게 우선순위를 donate 해준 스레드를 저장하는 리스트donation이 발생하는 상황 시뮬레이션
1-1 a 스레드가 lock A를 점유하려는 상황. lock A는 소유자고 있는 스레드가 없다.
1-2 a보다 우선순위가 높은 b가 lock A를 점유하려고 봤더니 이미 누군가가 lock A를 가지고 있다. lock A의 holder의 우선순위는 b보다 작다. 따라서 우선순위 donation이 이루어진다.
그림에서 수정해야할 부분 :
init_priority는 스레드를 초기화할 때 자신의 우선순위 값을 넣어서 초기화해준다. 따라서 모든 스레드의 init_priority 는 원래 자신의 priority로 초기화 되어 있다고 생각해야한다.
1-3 c도 lock A를 점유하려고 봤더니 이미 누군가가 점유해있고 나보다 우선순위가 작다. donation 해줘야한다.
1-4 같은 순서로 a가 lock A와 lock B를 모두 점유하고 있다고 하면 다음과 같은 상황이 발생한다.
1-5 이때 a가 lock A에 대한 실행을 종료하고나면 donations에서 이러한 경우에 a의 실행이 종료되고나면 donations에 있는 b와 c를 삭제해줘야한다. 그리고 donation에 남아있는 스레드들 중에 가장 우선순위가 큰 스레드의 우선순위를 다시 받아와야한다.
PintOS 1주차 회고
어렵기로 유명한 핀토스 프로젝트 주간이 다가왔다. 마음의 준비를 단단히하고 시작해서 그런지 막상 프로젝트를 시작하니 이전에 했던 과제들과 그렇게 크게 다르다는 느낌은 받지 못했다.
다른 과제들과 마찬가지로 시작할 때는 막막하지만 공부를 하다보면 하나씩 문제가 해결된다. 어느정도 이해했다고 생각할 때 쯤 예상치못한 문제가 터지고, 놓치고 있던 부분을 발견하고, 잘못 이해하고 있던 부분을 바로잡는 과정을 거치고나면 결국 목적했던 곳에 다다르게된다.
이번 주는 특히 더 재미있게 이 과정을 거쳐온 것 같다. 첫번 째는 좋은 팀원들을 만났기 때문이고, 두번 째는 그동안 궁금했던 부분에 대한 깊이있는 공부였기 때문이다. 혼자 공부한 내용을 기반으로 코드를 구현할 때에는 스레드와 스케쥴링에 대해서 글로 배운 지식을 눈으로 확인하는 과정이 즐거웠다. 하지만 그 과정 중에 항상 이해가 잘 되지 않는 부분이 생기는데 그때마다 팀원들과 함께 서로 아는 것을 얘기하면서 부족한 부분을 채워가다보면 또 이해가되고 문제가 풀리고 그런다. 신기하다.
2주차도 지금과 같이 재미있게 과제를 수행해나갈 수 있도록 더 공부하고 고민해야겠다.
