(2021.10.06) Priority Scheduling 가이드라인

드디어 역겨운 Priority를 뜯어고칠 시간이 돌아왔다. 역겹다 해도 4천왕 중 최약체지만...

 

아무튼, 처음 이 프로젝트를 접하면 "엥. 그냥 priority 관련 함수 구현하고 넣는 순서만 바꿔주면 알아서 될 것 같은데 뭐가 문제임?" 이라고 생각할 수 있다. 그러나 프로젝트 설명에서도 나와 있듯 Priority 스케줄링의 복병은 Priority Inversion을 해결하는 것이다.

 

Priority Inversion을 이해하기 위해서는 lock과 semaphore의 개념을 이해해야 한다. lock과 semaphore를 이해하기 위해서는 동기화 문제의 개념을 알아야 한다. 동기화 문제의 자세한 내용은 수업에서 배울테지만 간략히 설명하자면, 하나의 자원을 여러 개의 작업이 동시에 접근할 때 생기는 문제이다. CPU는 한 번에 하나의 작업의 명령밖에 처리하지 못하고, 동시에 여러 개의 작업을 처리하는 것처럼 보이는 것은 OS가 만들어낸 착각에 불과하기 때문에 여러 Process/Thread가 "동시에" 동일한 자원에 접근하는 것은 문제를 야기할 수 있다. 

 

이해를 돕기 위해 간단한 예시를 들어보자. 철수와 영희는 공용 냉장고를 사용하고 있고, 우유 1개가 필요하다. 냉장고가 비어있을 때 둘 모두 바로 마트에 우유를 사러 갔다온다. 냉장고가 지금 비어있다고 하면 얼마 뒤 우유는 몇 개가 될까? 물론 둘 모두에게 행복한 답안은 1개이고 다음의 과정을 거친 뒤일 것이다.

 

• 철수가 빈 냉장고를 보고 마트에 다녀온다. (우유 1)
• 영희가 볼 때는 냉장고가 비어있지 않으므로 그대로 둔다. (우유 1)

문제는 현실에는 이렇게 행복한 시나리오 뿐만 아니라 다른 경우도 존재한다는 것이다.

 

• 철수가 빈 냉장고를 보고 마트로 출발한다. (우유 0)
• 철수가 마트를 간 사이 영희도 빈 냉장고를 보고 마트로 출발한다. (우유 0)
• 철수가 도착해 우유를 냉장고에 넣는다. (우유 1)
• 영희가 도착해 우유를 냉장고에 넣는다. (우유 2)

덕분에 우유가 2개가 생겼다. 물론 풍족하다고 좋아할 수는 있겠지만 운영체제 입장에서는 이것은 예상치 못한 동작이기에 이러한 상황을 막아야 한다. 연구 결과 나온 해결책은 공통으로 사용하는 영역 또는 자원에 1번에 1개의 작업만 접근하도록 만드는 것이다. 이러한 영역을 critical section, 또는 임계 영역으로 부르기로 했고, 이 임계 영역에 1번에 1개의 작업만 접근하도록 해 주는 것이 semaphore와 lock 등의 개념이다. 어떠한 Thread가 임계 영역에 접근하기 위해서는 우선 이 lock 또는 semaphore를 먼저 Acquire(획득)해야 하며, 해당 영역에서의 작업을 끝내면 이들을 다른 Thread가 사용할 수 있도록 Release(반환)시켜야 한다. 필요한 lock/semaphore를 다른 Thread가 이미 가지고 있을 경우, Thread는 필요한 lock/semaphore가 해방되기까지 잠시 Block 상태가 된다. 여기까지의 과정을 이해했다면 왜 Priority Inversion 문제가 발생하는지 이해할 수 있다.

 

다음 3개의 Thread가 돌아가는 상황을 예로 들어보자.

 

• 5ms동안 진행되어야 하는 우선도가 낮은 Thread L은 자원 A에 접근하기 위해 Lock_A를 습득했다.
• 1ms 후, 3ms동안 진행되어야 하는 우선도가 높은 Thread H가 자원 A에 접근하기 위해 Lock_A를 요청하나, Thread L이 이미 습득 중이므로 Block된다.
• 1ms 후, 1000ms동안 진행되어야 하는 우선도가 중간인 Thread M이 실행된다. Thread M은 딱히 어떤 자원을 요청한 것이 아니며, Priority 스케줄링에 의해 Thread L보다 먼저 실행되어야 하므로, CPU를 뺏어 1000ms 동안 실행된다.
• Thread M이 종료된 후, Thread L이 다시 작업을 시작한다. 자원 A와 관련된 작업이 끝난 뒤 Lock_A를 반환한다.
• Lock_A가 반환되면 OS는 Thread H를 Unblock한다. Thread H가 Thread L보다 우선도가 높기 때문에 CPU를 뺏어 실행을 마친다.
• 남은 Thread L의 작업이 실행된다. 

출처 : https://dev.to/hatsugai/prioriy-inversion-and-priority-inheritance-nl3

 

여기서 Thread M은 Thread H가 있음에도 불구하고, 자원의 접근이 없기 때문에 무제한적으로 계속 CPU에 남아있게 된다. 일정 시간마다 끊어서 다시 스케줄하는 것도 여기서는 소용이 없다. Thread H는 Block되어 있으며, Thread L과 Thread M을 비교하면 우선도가 Thread M이 더 높기 때문에 항상 스케줄러에 의해 선택되기 때문이다. 덕분에 Thread H는 자원 하나 때문에 Thread M을 무한정 기다리는 신세가 되었다. 이는 옛날 화성 탐사 로봇인 패스파인더에서도 발생했던 유서깊은 문제이다.

 

문제는 자원 A를 가지고 있는 Thread L의 우선도가 낮다는 데에 있다. 만약 Thread L이 Thread H만큼 우선도가 높았다면 Thread M에게 CPU를 뺏기지 않고 작업을 완료한 뒤, Thread H에게 Lock을 넘겼을 것이다. 그럼 우선도를 높이면 문제가 해결되지 않을까? 이 점에서 착안한 것이 바로 Priority Donation이다. 높은 우선도의 Thread가 낮은 우선도의 Thread가 가진 lock으로 인해 Block될 경우, 높은 우선도를 잠시 낮은 우선도 Thread에게 빌려주는 것이다. 물론 고려해야 할 세부 사항들이 있다.

 

• 체인 형태로 이어진 donation의 경우
• 한 thread에 두 개 이상의 thread가 donation을 하는 경우
• lock을 release할 때의 priority 책정
• donation이 일어나고 있을 때, thread의 priority 변화

등등 이러한 세부적인 사항은 구현할 때 테스트 케이스로 하나씩 보면 된다. 결론적으로 Priority Inversion 문제는 Priority Donation으로 해결하면 될 것이다.

 

정리하자면 최종적으로 구현해야 할 사항들은 다음과 같다.

 

• priority 관련 변수 추가 및 함수 구현
• synch.c에 구현된 lock 등에서 priority 반영
• priority donation 관련 함수 구현