Hard real-time systems are characterized by the fact that the execution of the tasks must be completed in time and must be done correctly. Thus, the task scheduling which allocates tasks to resources in such a way that their executions are being completed before the deadlines, is one of the most important activities in real-time systems, such as multimedia applications. Many of multimedia applications in distributed systems should transmit continuous audio/video non-preemptively to preserve the continuity across networks when clients request. Typically, messages for continuous media are heterogeneous and are split into periodic, different sized packets with deadlines.
In this thesis, we present a static scheduling strategy and a dynamic scheduling algorithm to improve the schedulability of non-preemptive scheduling for periodic tasks with specified release times, known as a NP-hard problem. Moreover, we apply them to multimedia applications in distributed systems.
First, we present the Time-Division Scheduling Strategy (TDSS) for the static non-preemptive scheduling. The TDSS transforms the given problem of non-preemptive scheduling for periodic tasks with specified release times into two subproblems of that with same release times within specific time intervals. Two time intervals for scheduling are computed with release times and periods. The TDSS finds two subsolutions for two respective subproblems and combines them into a complete solution of the given problem by using the repetitiveness and the predictability of periodic tasks. Therefore, the TDSS makes the previous optimal algorithm to find optimal solutions for the restricted periodic tasks with specified release times. For the general periodic tasks with specified release times, the TDSS gives higher schedulabilities than the previous scheduling strategy by the forward or the backward scheduling.
Second, we present the Precalculated Deadline-Miss Avoidance (PDMA) algorithm which is a heuristic algorithm based on the EDF policy for the dynamic non-preemptive scheduling. The PDMA algorithm selects the task with the earliest deadline. And then it precalculates if the scheduling of the selected task leads to the case that a task misses its deadline when tasks are scheduled by the non-preemptive EDF algorithm. If so, it defers the scheduling of the selected task to avoid the precalculated deadline-missing. The PDMA algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm.
Third, we apply the PDMA algorithm to the network packet scheduling in multimedia applications, such as video-on-demand, in distributed systems. Moreover, we present admission control to control traffic loads on a communication link, to guarantee the quality of service of the currently transmitted messages, and to guarantee the timely delivery of messages. The admission control is given as sufficient conditions for a set of messages to be schedulable by the PDMA algorithm. If a new request and the previous messages satisfy these conditions, it accepts the new request. Otherwise, it denies the newly arrived request.
We show the improvements in performance of the TDSS and the PDMA algorithm by respective simulation results.
실시간 시스템 (real-time system)에서의 태스크는 반드시 주어진 마감시간 (deadline) 내에 처리 완료되어야 한다는 시간적 제약성이 있다. 따라서, 모든 태스크들의 시간적 제약성을 만족하도록 하는 실시간 태스크 스케쥴링 (real-time task scheduling)은 실시간 시스템에서 가장 중요한 작업이다. 특히, 컴퓨터 및 통신 기술이 발달함에 따라 최근, 그 수요가 급증하고 있는 분산 시스템 상에서의 멀티미디어 시스템은 마감시간이 지정되어 있고, 요구자가 원하는 시간 이후부터, 주기적으로 발생하는 연속매체 정보를 비선점적으로 제공하여야 한다는 실시간 시스템의 특성을 가진다. 결국, 이러한 멀티미디어 시스템의 연속매체 정보의 만족스러운 처리를 위하여 실시간 주기적 태스크의 비선점적 스케쥴링이 반드시 필요하다.
본 논문에서는 NP-hard 문제로 알려져 있는 초기호출시간이 지정된 주기적 태스크 집합의 비선점적 스케쥴링 문제의 스케쥴링 성공율을 향상시키기 위한 스케쥴링 기법들을 제안하고, 이들을 분산시스템 환경의 멀티미디어 응용 시스템에 적용한다.
먼저, 정적 비선점적 스케쥴링을 위하여 시구간 분할 스케쥴링 전략 (Time-Division Scheduling Strategy, TDSS)을 제안한다. TDSS는 초기호출시간이 임의의 음이 아닌 정수 값으로 주어진 주기적 태스크들의 비선점적 스케쥴링 문제를 두 개의, 지정된 시간 구간 내에서의 모든 초기호출시간이 동일한 주기적 태스크 집합에 대한 비선점적 스케쥴링 문제들로 변형한다. 이 때의 스케쥴링 시간 구간은 주어진 태스크 집합 내의 초기호출시간과 주기 값들을 이용하여 구한다. 각각의 변형된 스케쥴링 문제에 대하여 구하여진 부-해들은 주기적 태스크들의 발생 형태가 순환한다는 특성과 예측이 가능하다는 특성을 이용하여 주어진 문제에 대한 완전한 해가 되도록 재 결합한다. 따라서, 제한된 주기적 태스크 집합의 경우, 기존의 최적 알고리즘을 사용하여 최적의 해를 구할 수 있다. 또한, 일반적인 주기적 태스크 집합의 경우에는 순방향 또는 역방향 스케쥴링으로 인하여 보다 향상된 스케쥴링 성공율을 기대할 수 있다.
둘째, 동적 비선점적 스케쥴링의 스케쥴링 성공율을 향상시키기 위하여 최소 마감시간 우선 (earliest-deadline first, EDF) 정책에 기반하는 휴리스틱 알고리즘인 예상된 마감시간-초과 회피 알고리즘 (Precalculated Deadline-Miss Avoidance algorithm, PDMA)을 제안한다. PDMA 알고리즘은 먼저, EDF 정책에 따라 태스크를 선택한다. 이 때, 선택한 태스크를 현 시점에서 비선점적 스케쥴링하게 될 경우의 다른 태스크들의 마감시간 초과 발생 가능성을 미리 계산한다. 다른 태스크의 마감시간 초과가 예상될 경우, 선택한 태스크의 스케쥴링을 연기하므로써 예상되는 다른 태스크의 마감시간 초과 발생을 회피한다. PDMA 알고리즘은 비선점적 EDF 알고리즘으로 실행 가능한 스케쥴을 찾을 수 있는 태스크 집합에 대해서는 항상 실행 가능한 스케쥴을 찾을 수 있다.
셋째, PDMA 알고리즘을 분산 시스템 환경 상에서의 video-on-demand 등의 멀티미디어 응용 시스템의 네트워크 관리자 유니트의 네트워크 패킷 스케쥴링을 위하여 적용한다. 이 때, 통신 링크의 부하를 조절하고, 현재 전송 중인 메시지들의 서비스 질 (quality-of-service)을 보장함과 동시에 승인된 메시지 패킷들의 마감시간 이전까지의 전송을 보장하기 위하여 새로운 전송 요구에 대한 승인 전략을 제안한다. 즉, PDMA 알고리즘에 의하여 성공적으로 스케쥴링되기 위한 충분조건을 제안하므로써 전송하고자 하는 모든 메시지들이 이 조건을 만족하면 통신 링크의 사용을 승인하고, 그렇지 않으면 거부하도록 한다.
본 논문에서 제안하는 TDSS 및 PDMA 알고리즘으로 기대할 수 있는 향상된 스케쥴링 성공율은 각각에 대한 모의 실험의 결과로써 나타내 보인다.
