오늘날의 내장형 시스템은 군사 무기체계, 로봇, 인공위성 등과 같이 전통적인 내장형 시스템에서 휴대폰, 디지털 캠코더, PMP, MP3플레이어와 같은 보다 복잡한 응용프로그램 구동을 필요로 하는 휴대용 시스템으로 그 영역을 넓혀가고 있다. 이런 내장형 실시간 시스템은 내장형 시스템의 한정된 자원을 효율적으로 관리하고 시간적 논리적 정확성을 보장하기 위해 실시간 운영체제를 사용한다. 실시간 운영체제의 서비스를 통해 응용프로그래머는 응용프로그램을 구성하는 각 태스크가 시간 결정성에 위배되지 않도록 응용프로그램을 구현할 수 있다. 더욱이, 실시간 운영체제는 시간 결정성 보장을 위해 스케줄링과 문맥교환에 사용되는 시간을 예측할 수 있어야 한다. 본 논문에서는 추가적인 메모리 오버헤드 없이 22r 레벨의 우선순위를 갖는 시스템에서 고정 상수 시간 내에 가장 높은 우선순위를 갖는 태스크를 결정할 수 있는 알고리즘에 대해 기술한다.
오늘날의 내장형 시스템은 군사 무기체계, 로봇, 인공위성 등과 같이 전통적인 내장형 시스템에서 휴대폰, 디지털 캠코더, PMP, MP3플레이어와 같은 보다 복잡한 응용프로그램 구동을 필요로 하는 휴대용 시스템으로 그 영역을 넓혀가고 있다. 이런 내장형 실시간 시스템은 내장형 시스템의 한정된 자원을 효율적으로 관리하고 시간적 논리적 정확성을 보장하기 위해 실시간 운영체제를 사용한다. 실시간 운영체제의 서비스를 통해 응용프로그래머는 응용프로그램을 구성하는 각 태스크가 시간 결정성에 위배되지 않도록 응용프로그램을 구현할 수 있다. 더욱이, 실시간 운영체제는 시간 결정성 보장을 위해 스케줄링과 문맥교환에 사용되는 시간을 예측할 수 있어야 한다. 본 논문에서는 추가적인 메모리 오버헤드 없이 22r 레벨의 우선순위를 갖는 시스템에서 고정 상수 시간 내에 가장 높은 우선순위를 갖는 태스크를 결정할 수 있는 알고리즘에 대해 기술한다.
In recent years, embedded systems have been expanding their application domains from traditional applications (such as defense, robots, and artificial satellites) to portable devices which execute more complicated applications such as cellular phones, digital camcoders, PMPs, and MP3 players. So as ...
In recent years, embedded systems have been expanding their application domains from traditional applications (such as defense, robots, and artificial satellites) to portable devices which execute more complicated applications such as cellular phones, digital camcoders, PMPs, and MP3 players. So as to manage restricted hardware resources efficiently and to guarantee both temporal and logical correctness, every embedded system use a real-time operating system (RTOS). Only when the RTOS makes kernel services deterministic in time by specifying how long each service call will take to execute, application programers can write predictable applications. Moreover, so as for an RTOS to be deterministic, its scheduling and context switch overhead should also be predictable. In this paper, we present the complete generalized algorithm to determine the highest priority in the ready list with 22r levels of priorities in a constant time without additional memory overhead.
In recent years, embedded systems have been expanding their application domains from traditional applications (such as defense, robots, and artificial satellites) to portable devices which execute more complicated applications such as cellular phones, digital camcoders, PMPs, and MP3 players. So as to manage restricted hardware resources efficiently and to guarantee both temporal and logical correctness, every embedded system use a real-time operating system (RTOS). Only when the RTOS makes kernel services deterministic in time by specifying how long each service call will take to execute, application programers can write predictable applications. Moreover, so as for an RTOS to be deterministic, its scheduling and context switch overhead should also be predictable. In this paper, we present the complete generalized algorithm to determine the highest priority in the ready list with 22r levels of priorities in a constant time without additional memory overhead.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이러한 제한은 최근의 다양한 응용프로그램을 지원하기에는 여러 가지로 제약이 있을 수 있다. 따라서 본 논문에서는 기존의 비트맵을 이용한 연산이 갖는 시간결정성을 갖는 태스크 스케줄링의 장점을 유지하면서 태스크가 가질 수 있는 우선순위의 수가 증가할 경우 발생하는 기하급수적인 메모리 증가의 문제점을 보완한 일반화된 시간결정성을 갖는 스케줄링 방법을 제안한다.
알고리즘에 대해 소개한다. 마지막으로, 결론에서는 본 논문의 완전히 일반화된 시간 결정성을 갖는 스케줄링 알고리즘에 대해 소개한다.
본 논문에서는 언맵 테이블의 크기를 줄이는 방법으로 64개의 우선순위에 적용하였던 2%개의 언맵 테이블을 이용하는 방법으로 임의의 수에 대하여서도 확장이 가능함을 예를 통해 보인다.
본 논문의 구성은, 본론에서 우선순위 선택을 위한 일반적인 탐색 알고리즘의 스케줄링 오버헤드와 11C/0S에서 제안한 시간 결정성을 갖는 스케줄링 알고리즘에 대해 간략히 소개하고[3], 생성 가능한 태스크 수에 제한이 있는 iiC/OS의 제약사항을 해결한 본 논문의 22r 레벨의 우선순위 상에서 실행 준비 상태의 태스크들 중 가장 높은 우선순위를 결정하는 완전히 일반화된 시간 결정적인 스케줄링 알고리즘에 대해 소개한다. 마지막으로, 결론에서는 본 논문의 완전히 일반화된 시간 결정성을 갖는 스케줄링 알고리즘에 대해 소개한다.
앞 장에서 시간 결정성은 보장하지만 최대 우선순위가 64로 제한된 μC/OS의 스케줄링 기법과 이런 제한 사항을 제거하기 위한 스케줄링 기법에 대해서 살펴 보았다. 하지만, 태스크가 가질 수 있는 우선순위의 수를 증가시켰을 때, 단순한 계산만으로 최고의 우선순위를 찾는데 사용되었던 언맵 테이블의 크기가 기하급수적으로 증가하여 메모리 크기가 많이 요구되는 문제점이 있었다.
제안 방법
그러나 이를 위해서는 2t개의 언맵 테이블이 필요하다. 따라서 본 논문 에서는 언맵 테이블의 크기가 태스크가 가질 수 있는 우선순위의 수인 준비리스트의 크기에 비례하여 0(2") 으로 늘어나는 방법 대신에 약간의 시간적인 부담을 지불하여 언맵 테이블의 크기를 0(2")로 줄이는 방법을 제안한다. 기존의 방법이 준비리스트의 크기에 따라서 언맵 테이블의 크기를 맞추었던 방식이라면 제안한 방식은 언맵 테이블의 크기에 맞추어 준비리스트의 크기를 분할하는 방식이다.
시간복잡도。(1) 의시간에 우선순위를 결정하는 방법을 제안하였다. 또한, 태스크의 우선순위 수의 증가가 미치는 메모리의 공간복잡도O(22) 형태로 기하급수적인 증가를 가져오는 제한사항을 기존의 스케줄링 방법이 갖는 시간결정성의 장점을 그대로 유지하면서, 추가적인 메모리 사용 없이 기존의 최대 태스크 수에 의한 제약을 제거한 일반화된 시간 결정성을 갖는 스케줄링 방법을 제안하였다.
256개의 우선순위(22r 우선순위에서r을 4로 설정)를갖는 태스크 스케줄링을 살펴보자. 수행준비 상태가 된 우선순위가 p인 태스크를 준비리스트에 삽입하는 경우에는, 태스크의 우선순위에 대응하는 준비그룹 (OSRdyGrp, 한 그룹당 16개의 태스크)과 준비테이블 (OSRdyTbl[16])에 1로 세팅하고 준비 큐[p]에 삽입한다.
[그림 3]에서와 같이 준비테이블 (OSRdyTbl[2r])은 2t.개의 비트를 가진 2i개의 이진수로 구성된 배열을 갖는 구조로써 각 각의 비트는 우선순위를 나타내고, 준비그룹은 각 준비테이블의 이진수에 대응하는 비트로 구성되며, 준비 리스트는 준비 테이블과 준비그룹 이외에 [그림 3]과 같이 준비리스트 각 비트에 대응하는 22ㄱ개의 준비 큐(queue)를 포함하여 여러 개의 태스크들이 동일한 우선권을 가질 수 있도록 한다. 태스크의 우선순위(p)는 2i.
k번째 이진수는 k번째 비트만이 '1, 이고 나머지 비트는 '0'인 2i.개의 비트를 가진 2r개의 이진수로 구성되어 맵 테이블(OSMapTbl[16])을 이용하여, 다음 식에 따라 태스크의 우선순위(p)어] 대응하는 준비그룹 및 준비 테이블 비트를 1로 세팅한다.
먼저 사용 가능한 우선순위 수를 [그림 2] 와같이정방형의 테이블을 갖는 형태로 표시하고 각각의 열을 하나의 그룹(ReadyGrp)으로 정의한다. 그리고 각각의 그룹을 주어진 우선순위를 갖는 태스크가 존재하는 우선순위 비트를 T로 설정한 후 그들 중에서 가장 우측에 있는 비트가 '1'인 곳을 찾아내는 방법을 사용한다.
또한, 태스크의 우선순위 수의 증가가 미치는 메모리의 공간복잡도O(22) 형태로 기하급수적인 증가를 가져오는 제한사항을 기존의 스케줄링 방법이 갖는 시간결정성의 장점을 그대로 유지하면서, 추가적인 메모리 사용 없이 기존의 최대 태스크 수에 의한 제약을 제거한 일반화된 시간 결정성을 갖는 스케줄링 방법을 제안하였다.
기존의 방법이 준비리스트의 크기에 따라서 언맵 테이블의 크기를 맞추었던 방식이라면 제안한 방식은 언맵 테이블의 크기에 맞추어 준비리스트의 크기를 분할하는 방식이다. 즉, 준비그룹의 비트들을 2등분하여 우반부가 '0'이면 좌반부를, '0'이 아니면 우반부를 택하는 단계를 루프(loop)로 형성하여, r보다 작은 임의의 양의 정수 k값에 따라 채택된 좌 반 부 또는 우반부를 다시 2등분하는 단계를 (r-k)번 반복하는 단계를 거쳐, 작은 크기의 언맵 테이블을 이용 할 수 있도록 [그림 5]의 흐름도와 같이 재구성하였다. [표 5]는 [그림 5]의 흐름도에 따라 최상위 우선순위 선택을 위해 준비 그룹과 준비 테이블의 값을 계산하는 알고리즘이다.
대상 데이터
그러나 태스크가 가질 수 있는 우선순위의 확장을 위하여 128개의 우선순위 사용을 가정 한다면 priority = readygroup(y) X readytable(x) 의 조합에 의하여 16비트의 준비그룹과 8비트의 준비테이블 또는 8비트 준비그룹과 16비트 준비 테이블의 조합으로 확장할 수 있다. 64개의 우선순위를 예를 들어 설명한 것과 같이 준비그룹과 준비 테이블의 비트 중에서 가장 우선권이 높은 비트를 찾는 문제, 즉 가장 왼쪽 비트를 찾는 문제는 256개의 기존의 언맵 테이블을 이용하였다. 그러나 128개의 우선순위에 대해서는 128=16 X 8 로 인하여, 준비그룹을 위한 216개의 언맵 테이블과 준비테이블을 위한 28개의 언 맵 테이블이 각각 필요하다.
성능/효과
증가해 시간이 지연된다. 또한 제안된 방법에서는 최고 우선순위 결정단계에서 k값을 적당히 조정함으로써 소요되는 시간과 메모리 공간사용 사이에서의 응용시스템의 요구에 따라서 절충이 가능하다.
. 본 논문에서 제안한 알고리즘은 우선순위의 증가에 따른 실행 명령어 수는 증가하지만 이것 또한 시스템상에서의 우선순위 수가 정해지면 명령어 수도 정해지므로 시간 결정성을 보장한다. 예를들어, 우선숭위의 수가 1024인 경우 제안한 알고리즘에서는 최상위 우선순위를 결정하기 위해서 19개의 명령어를 수행하면 된다.
참고문헌 (5)
K G. Shin and P. Ramanathan, "Real-time computing: a new discipline of computer scienceand engineering，" Proc. of the IEEE, Vol.82, No.1, pp.6-24, 1994.
K M Zuberi, P. Pillai, and K G. Shin, ''EMERALDS: A small-memory real-time microkemel," Proc. 17th ACM Symposium on Operating Systems Principles, 1999.
J. J. Labrosse, C/OS: The Real-Time Kernel，R&D Pub, 1993.
K Ramanlritham and J. A Stankovic，"Scheduling algorithms and operating system support for real-time systems," Proc. of IEEE，Vol.82, No.1, pp.55-67, 1996.
S. J. Oh, J. N. Kim, Y. R Seong, and C. H. Lee, ''Deterrninistic Task Scheduling for Embedded Real Time Operating Systems," IEICE Trans. Inf.&Syst., Vol. E87，No.2, pp.123-126, 2004.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.