In this thesis, we propose several techniques that aim to minimize the scheduling latency of high-priority interrupt-driven tasks in the general-purpose operating systems. First, we propose a novel scheduling technique to improve the responsiveness of a real-time process while maintaining relative execution rates of non-real-time processes, called the $\textit{prediction-based micro-scheduler}$. It runs upon existing macro-scheduler and it conditionally rearranges the scheduling pattern generated by the macro-scheduler based on urgent interval prediction and lock hold time prediction. The rearrangement occurs if one process seeks to enter a long non-preemptible section and the operation is predicted to significantly disturb the future execution of a real-time process. To build a theoretical guideline for using the micro-scheduler, we derive a sufficient condition under which the starvation problem does not arise and the relative execution rates can be maintained.
We implemented the prototype on Linux 2.6.19. Experimental results show that the average OS latency of a real-time process is reduced up to 34% of the original one while still maintaining relative execution rates of non-real-time processes. Moreover, the performance degradation caused by the micro-scheduler does not exceed 5%.
One of key advantages of the micro-scheduler is that it is orthogonal to most related techniques, and this advantage is demonstrated experimentally by combining it with two widely used techniques.
Next, we propose two techniques that also aim to minimize the scheduling latency of high-priority interrupt-driven tasks, named the $\textit{interrupt handler migration}$ (IHM) and $\textit{direct interrupt scheduling}$ (DIS). The IHM allows the interrupt handler to be migrated from the interrupt handler thread to the corresponding target process so that additional context switch can be avoided and the cache hit ratio with respect to the data generated by the interrupt handler can be improved. In addition, the DIS allows the shortest path reserved for urgent interrupt-process pairs to be laid between the interrupt arrival and target process by dividing a series of interrupt-driven operations into non-deferrable and deferrable operations. The proposed techniques not only reduce the scheduling latency, but also resolve the interrupt-driven priority inversion problem by coordinating the priority level of the interrupt handler with that of the target process.
We implemented a prototype in the Linux 2.6.19 kernel after adding state-of-the-art real-time patches. Experimental results show that the scheduling latency is significantly reduced by up to 84.2% when both techniques are applied together. When the Linux OS runs on an ARM-based embedded CPU running at 200MHz, the scheduling latency can become as low as 30 usec, which is much closer to the hardware-specific limitations. By lowering the scheduling latency, the limited CPU cycles can be consumed more for user-level processes and less for system-level tasks such as interrupt handling and scheduling.
본 논문에서는 범용 운영체제에서 우선순위가 높은 인터럽트 구동 태스크의 스케쥴링 지연시간을 최소화하기 위한 세 가지 기법들이 제안되었다. 첫번째로, 실시간 프로세스의 응답성을 향상시키면서 동시에 비실시간 프로세스들의 상대적 실행비율을 유지시켜주는 임계영역 진입 지연기법, 그리고 이에 기반한 예측기반의 마이크로 스케쥴러가 제안되었다. 이 마이크로 스케쥴러는 기존의 매크로 스케쥴러 상에서 구동되며 긴급구간 예측과 락 보유시간 예측에 기반하여 매크로 스케쥴러의 스케쥴링 패턴을 조건부로 재배열한다. 이 재배열은 하나의 비실시간 프로세스가 긴 비선점구간으로 진입하고 이 연산이 미래의 실시간 프로세스의 실행에 심각한 영향을 끼침이 예측되는 경우 실시된다. 이 마이크로 스케쥴러 사용에 대한 이론적인 가이드라인을 제공하기 위해 스타베이션 문제가 발생하지 않고 상대적 실행비율이 유지되지 않기 위한 충분조건을 유도하여 제시하였다.
본 마이크로 스케쥴러는 리눅스 2.6.19 상에서 구현되어 그 성능이 평가되었다. 실험결과 실시간 프로세스의 평균 스케쥴링 지연시간이 기존의 34% 수준까지 줄어들고, 또한 비실시간 프로세스들의 상대적 실행비율이 유지됨을 확인할 수 있었다. 또한 마이크로 스케쥴러 구동에 의한 성능저하가 5%를 넘지 않음을 확인할 수 있었다.
마이크로 스케쥴러 기법의 대표적인 장점은 이 기법이 우선순위상속기법, 스핀락기반 기법, 뮤텍스컨버전 기법 등 대부분의 기존의 기법들과 독립적인 기법이기 때문에 기존의 기법들과 자연스럽게 융합되어 같이 사용될 수 있다는 점이다. 이러한 장점은 본 기법을 기존의 대표적인 두 가지 기법 - 스핀락기반 기법과 뮤텍스컨버전 기법 - 과 결합하여 실제로 구동해 봄으로써 실험적으로 증명되었다.
두번째로, 인터럽트 핸들러 마이그레이션 기법이 제안되었다. 이 기법은 인터럽트 핸들러가 인터럽트 핸들러 쓰레드 컨텍스트가 아닌 목적 프로세스 컨텍스트에서 실행되게 함으로써 추가적인 컨텍스트 전환을 회피하게 한다. 또한 부가적으로 이 기법은 인터럽트 핸들러와 연관된 데이터에 대한 캐시 적중율을 높이고, 인터럽트 핸들러에 대한 우선순위와 목적 프로세스에 대한 우선순위를 연관시킴으로써 인터럽트에 의한 우선순위 역전 문제를 해결시켜 준다.
세번째로, 다이렉트 인터럽트 스케쥴링 기법이 제안되었다. 이 기법은 긴급 인터럽트 발생과 이에 해당하는 목적 프로세스 사이의 일련의 작업을 지연가능한 작업과 지연불가한 작업으로 나누고, 긴급 인터럽트 발생시 지연불가한 작업만을 허용하고 지연가능한 작업은 인터럽트 구동 프로세스의 종료 후로 지연시킴으로써, 긴급 인터럽트와 목적 프로세스 사이에 최소 실행 경로를 찾게 해 준다.
인터럽트 핸들러 마이그레이션 기법과 다이렉트 인터럽트 스케쥴링 기법은 예측기반 마이크로 스케쥴러 기법과 마찬가지로 리눅스 2.6.19 상에서 구현되어 그 성능이 평가되었다. 실험결과 두 기법이 동시에 사용될 때 인터럽트 구동 실시간 프로세스에 대한 스케쥴링 지연시간이 기존의 84.2% 수준까지 감소됨을 확인할 수 있었다. 리눅스 운영체제가 200MHz로 구동되는 ARM기반 임베디드 프로세서 상에서 구동될 경우, 스케쥴링 지연시간은 30 $\textit{usec}$ 까지 줄어들었는데, 이는 하드웨어적인 한계치에 매우 가까운 수준이었다. 스케쥴링 지연시간을 이와 같이 최소화함으로써, 제한된 CPU 시간이 사용자 수준 프로세스들을 위해서는 더 많이 사용되고 인터럽트 핸들링이나 스케쥴링같은 시스템 수준 태스크들을 위해서는 더 적게 사용되게 된다. 즉 제안된 기법들은 스케쥴링 지연시간을 최소화시킴으로써, 제한된 CPU 시간을 보다 효율적으로 사용할 수 있게 한다.
