Abstract
Real-time operating systems have been used in various computing environments, where a job must be completed in its deadline, with various conditions, such as effective scheduling policies, the minimum of an interrupt delay, and the solutions of priority inversion problems, that should be perfectly satisfied to design and develop optimal real-time operating systems. Up to now, in order to solve priority inversion problems among several those conditions. There have been two representative protocols: basic priority inheritance protocol and priority ceiling emulation protocol. However, these protocols cannot solve complicated priority inversion problems. In this paper, we design a protocol, called recursive priority inheritance (RPI), protocol that effectively solves the complicated priority inversion problems. Our proposed protocol is also implemented in the Linux kernel and is compared with other existing protocols in the aspect of qualitative analysis.
실시간 운영체제는 정해진 시간 내에 작업처리를 완료해야 하는 분야에 주로 사용되고 있으며, 최적의 실시간 운영체제를 설계하고 개발하기 위해서는 효과적인 스케줄링 정책, 인터럽트 지연 최소화, 우선순위 역전현상 해결 등의 조건을 만족시켜야한다. 이러한 조건들 중에서 우선순위 역전현상을 해결하기 위해 지금까지 basic priority inheritance 프로토콜, priority ceiling emulation 프로토콜 등이 제안되었으나, 하나의 프로세스가 동시에 다수의 자원을 소유하는 경우 또는 재귀적으로 자원을 소유하거나 요청하는 경우와 같이 대표적인 두 가지 복잡한 우선순위 역전현상에 대해서는 해결이 불가능하다. 이에 본 논문에서는 재귀적 자료구조를 기반으로 다양한 우선순위 역전현상을 효과적으로 해결할 수 있는 RPI(Recursive Priority Inheritance) 프로토콜을 설계하고, 이를 리눅스 커널에 구현하여 검증한 내용을 보인다.
