Real-time systems are characterized by the fact that severe consequences will result if neither logical nor timing correctness of the system are satisfied. Task scheduling is one of the most important problem since scheduling algorithms ensure that tasks meet their deadlines. If a schedule is not feasible, then the executions of tasks can not meet their deadlines. In most time-critical systems, not only timing correctness of results but also fault-tolerance of the system are required. So, scheduling algorithms should consider the occurrences of faults, which has the objective to optimize both timeliness and reliability.
Recently, it has been noted in many researches that real-time engineering is essential in multimedia computing. For example, in a tele-conferencing system in Local Area Network(LAN) of workstations, multiple streams of motion videos and audios should be handled continuously and synchronized temporally when they are captured, transmitted, and modified in the network. since the data streams of videos and audios should be presented to a CRT at a certain constant rate. All processing units like the storage unit, the computation unit, and the communication unit in a workstation should complete their processing as timely as possible.
In this dissertation, we propose two algorithms, one of which is targeted to the scheduling of nonpreemptive real-time tasks and the other tries to optimize both the timeliness and the reliability. We also indicate that multimedia computing requires real-time engineerings to satisfy the timeliness and apply our scheduling algorithms to solve the scheduling problems inherent in multimedia computing. In addition, we suggest a new specification method based on Milner's CCS.
We propose a new scheduling algorithm called OFOG in the meaning that it inserts one floor to one gap and show that it is optimal for scheduling a subset among whole sets of periodic tasks and the time complexity of OFOG algorithm is analyzed to be equal to EDF algorithm. We also propose a scheduling algorithm called LGF which inserts a floor to the largest gap first and show that it is optimal for scheduling tasks more generalized than those of OFOG. Although OFOG algorithm is a special case of LGF algorithm, OFOG algorithm is preferred in the practical applications because of the simplicity.
We discuss the scheduling of real-time tasks considering the occurrence of faults, which is called responsive scheduling. We propose the definition of the responsiveness in responsive scheduling and suggest a scheduling algorithm called Responsive Earliest Deadline First(R-EDF). We illustrate how we compute the responsiveness of the scheduling with some examples.
We apply our scheduling algorithms to resolve the bandwidth allocation problems in a LAN based multimedia information system. We suggest Extended OFOG algorithm and an admission control algorithm to schedule continuous media like motion videos and sounds in the communication channel. The algorithm has the merit that it is optimal in some restricted environment. Hence, it can produce about twice times higher throughput than EDF algorithm. Considering the transient faults in a faulty communication system, we also propose a recovery policy based on our R-EDF algorithm. While other flow control algorithms did not suggest the admission control strategy, our recovery policy can suggest the admission control quantitatively.
We propose a specification method based on Milner's Calculus of Communicating Systems(CCS) We also describe the design and implementation of an authoring system called Eventor(Event Editor), which is based on CCS and composed of three tools, Temporal Synchronizer, Spatial Synchronizer, and User Interaction Builder. A simple CAI courseware written by our programming environment is depicted to illustrate the efficiency of Eventor. Our specification mechanism is well suited to handling the interactivity of multimedia applications and it can be used as a framework of other interactive multimedia applications.
실시간 시스템에서는 수행결과의 정확성외에도 지정된 시간내에 결과가 생성되어 야 한다는 시간제약 준수성이 요구된다. 이러한 시간제약을 준수하려면 결과를 생성하는 태스크들을 주어진 시간제약에 따라 적절히 스케쥴해야 한다. 만약 가능한 스케쥴이 만들어지지 않으면 태스크들의 수행도 시간제약을 지킬 수가 없다. 또한, 시스템에 고장이 발생하더라도 시간제약을 준수하려면 고장시에 시간지연 없이 복구해야 할 필요가 있다. 경제적인 이유나 고장의 성격상 복구에 시간이 걸리는 시스템에서는 스케쥴을 만들때 고장복구를 위한 시간도 고려해야 한다.
최근들어 음성 및 동영상등을 다루는 멀티미디어 시스템에서도 실시간 기법이 필수적이라는 연구들이 많이 발표되고 있다. 예를 들어, 원격 영상 회의의 경우에 다수의 동영상 및 음성 데이타 스트림들이 통신망에서 전송되고 CRT나 스피커에 출력될 때 시간적으로 동기화되어야 하고 연속적으로 처리되어야 한다. 이러한 시간적 동기화를 기술하기 위하여 실시간 형식 명세 기법이 이용되고 있으며 시간제약을 준수하기 위하여 자원들을 실시간 제약에 맞게 스케쥴하는 스케쥴링 기법들이 이용된다.
본 논문에서는 비선점적 태스크의 스케쥴링을 위한 스케쥴링 알고리즘과 고장을 고려할때의 스케쥴링 알고리즘을 각각 개발하고 멀티미디어 응용의 시간적 동기를 기술하기 위한 새로운 기법을 제안하며 LAN 에 기초한 멀티미디어 정보 시스템을 구현할 때에 발생하는 실시간 스케쥴링 문제를 본 논문에서 제안한 스케쥴링 알고리즘을 이용하여 해결한다.
각각을 살펴보면, 첫째, 본논문에서는 비선점적, 주기적 태스크를 제한된 영역에서 최적으로 스케쥴하는 OFOG라는 알고리즘을 제안한다. 기존의 알고리즘들은 최적의 해를 구하지 못하거나, 좀 더 제한된 영역에서 문제를 풀고 있다. 또한, OFOG보다 덜 제한된 영역에서 최적으로 스케쥴하는 LGF 알고리즘도 제안한다. OFOG가 LGF 알고리즘의 특수한 경우이지만 스케쥴링 복잡도가 더 작다는 장점이 있다.
둘째, 본 논문에서는 고장을 고려하였을 때 신뢰도와 스케쥴 가능성을 모두 최적화하는 스케쥴링 알고리즘을 제안한다. 기존의 연구들에서는 신뢰도를 어느 정도 가정한 후 스케쥴 가능성을 최대화하는 접근법을 쓰고 있으나 실지 응용에서 가정된 신뢰도를 유지하기 어렵다는 문제점이 있다. 본 논문에서는 신뢰도를 확률로 표현했을 때 스케쥴 가능성을 계산하는 새로운 알고리즘을 제안한다. 그 알고리즘의 성능척도로서 적응성(responsiveness)을 정의하고 이를 최대화하도록 스케쥴하는 R-EDF 알고리즘을 제안한다.
세째, LAN에 기초한 멀티미디어 정보 시스템의 통신채널에서 다수의 동영상 전송요구를 시간제약을 지키면서 전송하는 문제를 OFOG 알고리즘과 R-EDF 알고리즘을 이용하여 해결한다. 즉, 동영상등의 데이타 전송요구가 비선점적, 주기적임을 보이고 OFOG 알고리즘이 이들 데이타 전송요구를 시간제약에 맞게 스케쥴할 수 있음을 제시한다. 실험을 통하여 EDF에 비해 두배 정도로 스케쥴 가능성이 향상됨을 보였다. 또한, 통신채널상의 일시적 고장을 재전송에 의하여 복구할 때 재전송비용을 고려하여 전송요구를 승인하는 승인전략을 제안한다. 즉, 전송요구에 대하여 R-EDF 알고리즘을 이용하여 적응성(responsiveness)을 계산하고 이 적응성이 한계값(threshold)을 넘으면 승인하고 그렇지 않으면 거부한다.
끝으로, 본 논문에서는 멀티미디어 응용을 형식명세하는 기존의 연구들이 사용자와의 대화(interaction)를 간과하고 있다는 문제점을 해결하기 위하여 Milner의 CCS(Calculus of Communicating Systems)에 기반을 둔 새로운 형식명세 기법을 제안하고 이 명세기법에 준하여 멀티미디어 저작시스템을 설계하고 구현한다. 간단한 CAI(Computer Aided Instruction) 응용을 제작하여 명세기법의 유용성을 보인다.
