两种经典实时调度算法的研究与实现

速率单调（RM）调度和最早截止期限优先（EDF）调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法，并在不同的工作负载下，以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标，对两种算法进行了性能分析和比较。在通常情况下，RM和EDF都可以保证任务成功调度，EDF算法可承受较多的工作负载。但是随着负载的增加，EDF算法性能急剧下降，到一定过载程度，EDF算法性能低于RM算法。     

Real-Time Disk Scheduling for Multimedia Applications with Deadline-Modification-Scan Scheme

Real-timedisk scheduling (RTDS) is important for time-critical multimediaapplications. In conventional approaches of real-time disk scheduling,such as SCAN-EDF, the seek-optimizing SCAN scheme is appliedto reduce the disk service time of the real-time EDF schedule.Since only tasks with the same deadline are seek-optimized, theobtained improvement of SCAN-EDF is limited. In this paper, basedon the maximum-scannable-group (MSG) concept, a deadline-modification-scan (DMS or DM-SCAN) algorithm is proposed.Our algorithm uses MSG to automatically decide the suitable taskgroups for seek-optimizing. Based on the MSG concept, we repeatedlyapply DMS to further increase disk throughput to support moretasks. We have implemented the proposed algorithm on UnixWare2.01. The appropriate problem behaviors and parameter valuesto yield good solutions are investigated. Experiments show thatDMS is better than conventional approaches in both the obtaineddisk throughput and the supported tasks. Moreover, our proposedapproach can schedule task sets that are not schedulable by EDFand SCAN-EDF.     

A Method for Performance Analysis of Earliest-Deadline-First Scheduling Policy

This paper introduces an analytical method to approximate the fraction of jobs missing their deadlines in a soft real-time system when the earliest-deadline-first (EDF) scheduling policy is used. In the system, jobs either all have deadlines until the beginning of service (DBS) and are non-preemptive, or have deadlines until the end of service (DES) and are preemptive. In the former case, the system is represented by an M/M/m/EDF+G model, i.e., a multi-sever queue with Poisson arrival, exponential service, and generally distributed relative deadlines. In the latter case, it is represented by an M/M/1/EDF+G model, i.e., a single-server queue with the same specifications as before. EDF is known to be optimal in both of the above cases. The optimality property of EDF scheduling policy is used for the estimation of a key parameter, namely the loss rate when there are n jobs in the system. The estimation is possible by assuming an upper bound and a lower bound for this parameter and then linearly combining these two bounds together. The resulting Markov chains can then be easily solved numerically. Comparing numerical and simulation results, we find that the existing errors are relatively small.     

Implementation of Hard Real-Time Embedded Control Systems

Although the domain of hard real-time systems has been thoroughly elaborated in the academic sphere, embedded computer control systems –- being an important component in mechatronic designs –- are seldom dealt with consistently. Often, off-the-shelf computer systems are used, with no guarantee that they will be able to meet the requirements specified. In this paper, a design for embedded control systems is presented. Particularly, the paper deals with the hardware architecture and design details, the operating system, and high-level real-time language support. It is shown how estimates of process run-times necessary for schedulability analysis can be acquired on the basis of deterministic behavior of the hardware platform.