A class of real-time multiaccess protocol is investigated in order to achieve the basic goal of fault-free and timely transmission for distributed hard real-time applications. Traditional time window protocol has desirable features such as channel access control based on message arrival times and the best throughput among known contention algorithms. However, the time window protocol is unfortunately subject to deadlock which is a serious drawback for hard real-time communication. In this thesis, a deadlock free window protocol, called limited splitting algorithm, is proposed and generalized to real-time multiaccess scheduling with static and dynamic priority scheduling policies.
The limited splitting algorithm limits total number of window splitting and uses a probabilistic retransmission scheme for deadlock resolution. In this way, the limited splitting algorithm can be deadlock free from various deadlock conditions, either noisy feedback or a simultaneous arrival of messages, with little degradation of maximally achievable throughput. The performance of the limited splitting algorithm is evaluated according to the maximal throughput under a Poisson infinite-user model.
In addition to its traditional role as a channel access protocol, the limited splitting algorithm is generalized for distributed real-time scheduling by explicitly imposing a network-wide transmission order on all message according to their time constraints. The real-time multiaccess scheduling problem arises whenever messages with hard deadlines must communicate over a single multiaccess channel. The desirable features of our real-time multiaccess protocol are the usage of the time constraint of messages to determine channel access right and correct operation in spite of those deadlock conditions.
The performances of the real-time scheduling policies have been studied by simulation method and the results show that, the real-time multiaccess protocol performs well according to the well known real-time scheduling policies such as the first-come-first-served(FCFS), the earliest deadline first, and head of line priority. Real-time performance matrices are message loss ratio and delay performance.
실시간 분산처리 응용에서 시간 제약을 받는 메세지 통신을 위한 채널 공유 방식이 높은 신뢰성과 전송시간 보장성을 기본 목적으로 하여 연구되었다. 기존의 시간격 분할 방식 (time window protocol)은 실시간 채널 공유 방식으로서 메세지 충돌 (contention)의 해결 방식 중 가장 좋은 효율성과 메세지 도착시간을 기준으로 하여 채널 사용권을 결정하는 좋은 장점을 가지고 있다. 그러나, 기존의 방식은 실시간 통신에서 심각한 단점이 되는 교착상태 (deadlock)에 빠지기 쉽다. 본 논문연구에서는 이러한 문제를 해결하기 위해서 제한 분할 알고리즘이라는 교착상태를 극복할 수 있는 시간격 분할 방식의 제안과 실시간 채널 스케쥴링 방식이 가능하도록 일반화 하였다. 제한 분할 알고리즘은 교착상태 해결을 위하여 시간격 분할 횟수를 제한하고 대신에 확률적인 재전송 방식을 도입한다. 이같은 방법으로 하여 제한 분할 방식은 채널 효율성의 작은 손실로서 채널상의 잡음 또는 메세지의 동시 도착 등과 같은 여러가지 교착상태를 만드는 조건들로부터 벗어날 수 있다. 제안된 알고리즘의 성능은 포아슨(Poisson) 메세지 도착과 무한의 전송자 모델하에서 최대 효율성이 해석되었다.
실시간 채널 스케쥴링은 단일 채널에서 여러개의 시간 제약을 받는 메세지들을 전송할 때 요구된다. 제한 분할 알고리즘의 일반화를 통한 실시간 채널 공유 방식은 교착상태에도 불구하고 원할한 채널 이용과 채널 사용을 메세지의 시간 제약에 따라서 결정할 수 있는데에 장점을 같는다. 기존의 여러가지 실시간 스케쥴링 방식의 채널 스케쥴링에 대한 특성은 시뮬레이션 방법을 통하여 연구되었다. 몇가지의 시간 제약에 대해서 도착 순서에 따른 (FCFS) 스케쥴링 방식, 미리 시간 제약에 따라서 결정된 동적 우선 순위(priority) 스케쥴링 방식, 그리고 시간 제약에 따라서 매번 결정하는 동적 우선 순위(deadline) 스케쥴링 방식을 갖는 시뮬레이터를 구성하여 성능 분석이 이루어졌다. 시뮬레이션 결과로부터 각각의 스케쥴러로서 만족되야 할 조건에 대하여 동적 우선 순위 방식이 정적 우선 순위 방식보다 장점을 보이나 지연 시간 및 부하(load) 제어성에 대해서는 정적 우선 순위 방식이 우수함을 보인다. 동적 우선 순위 방식은 과부하 조건에서 지연 또는 버려야 할 메세지 선택에 대해서 미리 결정할 수 없다. 제한 분할 방식의 일반화를 통한 채널 스케쥴링 방식은 내재된 스케쥴링 방식(FCFS, priority, deadline)들에 따라서 각기의 특성을 잘 나타내 준다.
