MicroC/OS-II 실시간 운영체제에서의 우선순위 역전현상 해결을 위한 일시적 우선순위 교환 프로토콜 설계 및 구현 Design and Implementation of a Temporary Priority Swapping Protocol for Solving Priority Inversion Problems in MicroC/OS-II Real-time Operating System원문보기
실시간 운영체제는 효율적인 스케줄링, 최소화된 인터럽트 지연, 우선순위 역전현상 해결 등의 다양한 조건을 만족시킴과 동시에, 응용프로 그램이 정해진 기한 내에 수행되는 것을 보장하여야 한다. 따라서 실시간 운영체제는 상기 조건을 만족시킬 수 있도록 설계/개발되어야 한다. 대중적인 실시간 커널의 한 종류인 MicroC/OS-II에서는 우선순위 역전 현상에 대한 해결 기법으로 뮤텍스(Mutex)를 사용한 기본적인 우선순 위 상속(Basic Priority Inheritance) 프로토콜을 사용한다. 뮤텍스를 구현하려면 우선순위가 같은 여러 태스크를 사용할 수 있도록 커널이 지원 해야 하나 MicroC/OS-II 운영체제는 우선순위가 같은 여러 태스크의 동시 사용을 지원하지 않는다. 이를 해결하기 위해 추가적인 우선순위 예 약을 사용할 수밖에 없게 되고, 결과적으로 제한된 우선순위 자원을 낭비하게 된다. 본 논문에서는 MicroC/OS-II의 불필요한 우선순위 자원을 낭비하는 문제점을 해결할 수 있는 일시적 우선순위 교환 프로토콜(Temporary Priority Swapping Protocol; TPSP)을 설계 및 구현하여, 한정 된 자원 환경을 가진 임베디드 장비에 효율적으로 운용되도록 하는데 목적을 둔다.
실시간 운영체제는 효율적인 스케줄링, 최소화된 인터럽트 지연, 우선순위 역전현상 해결 등의 다양한 조건을 만족시킴과 동시에, 응용프로 그램이 정해진 기한 내에 수행되는 것을 보장하여야 한다. 따라서 실시간 운영체제는 상기 조건을 만족시킬 수 있도록 설계/개발되어야 한다. 대중적인 실시간 커널의 한 종류인 MicroC/OS-II에서는 우선순위 역전 현상에 대한 해결 기법으로 뮤텍스(Mutex)를 사용한 기본적인 우선순 위 상속(Basic Priority Inheritance) 프로토콜을 사용한다. 뮤텍스를 구현하려면 우선순위가 같은 여러 태스크를 사용할 수 있도록 커널이 지원 해야 하나 MicroC/OS-II 운영체제는 우선순위가 같은 여러 태스크의 동시 사용을 지원하지 않는다. 이를 해결하기 위해 추가적인 우선순위 예 약을 사용할 수밖에 없게 되고, 결과적으로 제한된 우선순위 자원을 낭비하게 된다. 본 논문에서는 MicroC/OS-II의 불필요한 우선순위 자원을 낭비하는 문제점을 해결할 수 있는 일시적 우선순위 교환 프로토콜(Temporary Priority Swapping Protocol; TPSP)을 설계 및 구현하여, 한정 된 자원 환경을 가진 임베디드 장비에 효율적으로 운용되도록 하는데 목적을 둔다.
Real-time operating systems must have satisfying various conditions such as effective scheduling policies, minimized interrupt delay, resolved priority inversion problems, and its applications to be completed within desired deadline. The real-time operating systems, therefore, should be designed and...
Real-time operating systems must have satisfying various conditions such as effective scheduling policies, minimized interrupt delay, resolved priority inversion problems, and its applications to be completed within desired deadline. The real-time operating systems, therefore, should be designed and developed to be optimal for these requirements. MicroC/OS-II, a kind of Real-time operating systems, uses the basic priority inheritance with a mutex to solve priority inversion problems. For the implementation of mutex, the kernel in an operating system should provide supports for numerous tasks with same priority. However, MicroC/OS-II does not provide this support for the numerous tasks of same priority. To solve this problem, MicroC/OS-II cannot but using priority reservation, which leads to the waste of unnecessary resources. In this study, we have dealt with new design a protocol, so called TPSP(Temporary Priority Swap Protocol), by an effective solution for above-mentioned problem, eventually enabling embedded systems with constrained resources environments to run applications.
Real-time operating systems must have satisfying various conditions such as effective scheduling policies, minimized interrupt delay, resolved priority inversion problems, and its applications to be completed within desired deadline. The real-time operating systems, therefore, should be designed and developed to be optimal for these requirements. MicroC/OS-II, a kind of Real-time operating systems, uses the basic priority inheritance with a mutex to solve priority inversion problems. For the implementation of mutex, the kernel in an operating system should provide supports for numerous tasks with same priority. However, MicroC/OS-II does not provide this support for the numerous tasks of same priority. To solve this problem, MicroC/OS-II cannot but using priority reservation, which leads to the waste of unnecessary resources. In this study, we have dealt with new design a protocol, so called TPSP(Temporary Priority Swap Protocol), by an effective solution for above-mentioned problem, eventually enabling embedded systems with constrained resources environments to run applications.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 이런 문제점을 해결할 수 있는 우선순위교환 프로토콜(Temporary Priority Swap Protocol; 이하 TPSP)을 제안하고자 한다. TPSP는 동기화를 요구하는 두 태스크 간의 우선순위 역전현상이 발생할 경우, 두 태스크 간의 우선순위를 서로 교환하는 방식을 사용한다.
본 실험은 TPSP가 우선순위 예약을 하지 않고도 올바른 동작을 수행하는지 테스트한다. 커널 상에서 변화된 부분만을 테스트하는 것이 순수 목적이므로, 실제 임베디드 장비에 포팅하지 않고 Windows XP 운영 체제상에서 가상 머신으로 동작되도록 프로그램으로 시뮬레이션 하였다.
가설 설정
1. N개의 태스크중 가장 우선순위가 낮은 태스크가 먼저 뮤텍스를 소유한다.
1. T3가 뮤텍스를 요청. BPI 적용.
같다. TPSP의 경우도 마찬가지로, 우선순위 교환, 복귀하는데 걸리는 시간을 각각 t로 가정하였다.
기존 프로토콜에서의 우선순위 상속과 복귀의 시간복잡도는 <표 3>과 같다. 뮤텍스를 소유한 태스크가 예약된 우선순위 값을 상속받고, 원래의 우선순위로 복귀할 때 걸리는 수행 시간을 각각 t라고 가정하였다.
제안 방법
4.3절의 응용프로그램을 포함한 전체 소스를 컴파일하고, 그 결과로 생성된 Object 파일과 Binary 파일을 비교하고자 한다.
복귀해야 한다. 그 후 새로 뮤텍스를 요청한 태스크와 TPSP를 적용 한다.
그러므로 MicroC/OS-II와 같은 특성을 가지는 경우에 적용될 수 있는 새로운 기법인 TPSP를 제안하게 되었다. TPSP를 적용함으로써 공유자원에 의한 교착상태를 방지할 수 있고, 추가의 우선순위를 미리 할당할 필요가 없다.
그리고 실시간 운영체제인 MicroC/OS-II에서 우선순위 역전현상 해결을 하기위해 사용하는 BPM〕기초한 우선순위 예약 방식을 살펴보았다. 이 방식은 한 번에 한 개의 자원 소유가 가능한 MicroC/OS-II가 가지는 특성으로 인해 교착상태를 방지할 수 있다.
요청한다. 먼저, 뮤텍스 M을 소유하고 있는 태스크 Tm의 우선순위 값이 Th가 아닌 다른 태스크 Tl의 우선순위로 이미 바뀌어 있는 경우가 아닌지를 검사한다.
<코드 3>의 OSMutexDel 함수는 공유자원을 사용한 후, ECB를 반환하는 기존의 함수를 일부 수정하였다. OSMutexCreate 함수와 마찬가지로, TPSP는 우선순위 예약을 사용하지 않으므로 기존의 함수 안에 있는 우선순위 예약에 관련된 코드들을 제거한다.
수행하는지 테스트한다. 커널 상에서 변화된 부분만을 테스트하는 것이 순수 목적이므로, 실제 임베디드 장비에 포팅하지 않고 Windows XP 운영 체제상에서 가상 머신으로 동작되도록 프로그램으로 시뮬레이션 하였다.
이론/모형
TPSP를 적용하기 위해 ECB(Event Control Block으로 Mutex정보를 저장하는 구조체)의 변수인 OSEventCnt를 사용한다. OSEventCnt는 Mutex를 소유한 태스크의 우선순위값을 저장하기 위한 16비트 int형 변수이다.
실시간 운영체제는 최적의 실시간 시스템에 맞도록 설계되고 개발되어야 하몌1], 이를 위해서는 효율적인 스케줄링 정책, 인터럽트 지연 최소화, 우선순위 역전현상 해결 등의 조건을 만족시켜야 한다. 실시간 운영체제의 한 종류인 MicroC/OS-II에서는 태스크간 동기화를 위해 뮤텍스(Mutex)를 사용하며, 우선순위 역전현상에 대한 해결기법으로 기본적인 우선순위 상속(Basic Priority Inheritance; BPI) 프로토콜[2]을 사용한다.
성능/효과
3. 처음 뮤텍스를 소유한 태스크는 최소한 가장 높은 우선순위를 가지는 태스크가 뮤텍스를 요청할 때까지 뮤텍스를 소유한다.
두 번째, 우선순위 역전현상이 중첩하여 발생될 경우에 함수가 호출된다.
본 논문에서 제안하는 TPSP는 기존의 우선순위 예약을 사용하는 BPI방식에서 사용한 함수들을 그대로 사용해도 구현이 가능하다. 즉, 뮤텍스를 사용하여 우선순위 역전현상을 해결하는 것 자체는 동일하기 때문에 함수의 이름들을 동일하게 사용한다.
<표 1>에서처럼 뮤텍스 서비스 Object 파일은 기존의 BPI를 적용한 것보다 약 3KB가, 응용프로그램을 포함한 전체 Binary 파일은 약 12KB가 감소되었다. 크기 감소의 주된 원인은 우선순위 예약을 구현하기위해 사용된 모든 변수와 명령들이 제거되었기 때문이다.
후속연구
향후 연구에는 우선순위 중복 불가능한 태스크의 문제 해결과 동시에 여러 자원의 소유 가능한 태스크 생성, 보다 향상되고 이식성 높은 우선순위 역전현상 해결 알고리즘을 적용하는 것이 필요할 것이다.
참고문헌 (11)
J. Stankovic, “Real-Time Computing”, BYTE, invited paper, pp.155-160, August, 1992
L. Sha, R. Rajkumar, and J. P. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”, IEEE Transactions on Computers Vol.39, No.9, pp.1175-1185, Sep., 1990
Jean J. Labrosse, “MicroC/OS-II 실시간 커널 2판”, 에이콘, 2007, ISBN 89-89975-60-3
J. B. Goodenough and L. Sha, “The Priority Ceiling Protocol”, Special Report CMU/SEI-88-SR-4, Mar. 1998
Qing Li, “RTOS를 이용한 실시간 임베디드 시스템 디자인”, 에이콘, 2005, ISBN 89-89975-42-5
김주용, 고건, “개선된 우선순위 상한 프로토콜의 구현”, 한국정보과학회 가을 학술발표논문집 제 20권 제2호 pp.565- 568, 1993
Min-Ih Chen, and Kwei-Jay Lin, “Dynamic Priority Ceilings: A concurrency Control Protocol for Real-Time Systems”, The Journal of Real-Time Systems, 2, 1990, pp.325-346
※ AI-Helper는 부적절한 답변을 할 수 있습니다.