A multimedia server requires a real-time disk-scheduling algorithm to deliver isochronous data for real-time streams. Traditional disk-scheduling algorithms focus on providing good quality in a best effort manner. In this paper, we propose a novel real-time disk-scheduling algorithm called WRR-SCAN (weighted-round-robin-SCAN) to provide quality guarantees for all in-service streams encoded at variable bit rates and bounded response times for aperiodic jobs. WRR-SCAN divides a real-time stream into guaranteed jobs and optional jobs. The admission control admits a stream as long as its guaranteed jobs are satisfied. Such a decision is made in 0(1) time as WRR-SCAN reserves a fixed weight for each stream. WRR-SCAN incorporates an aggressive policy to dynamically reclaim unused bandwidth during runtime. The reclaimed bandwidth is used to serve optional jobs or more aperiodic jobs. We conducted a set of simulations to compare WRR-SCAN with a set of referred disk-scheduling algorithms. The evaluations are conducted on a commonly used disk simulator with traces from a real multimedia server. The experimental results show that WRR-SCAN provides significantly better quality for real-time streams and yields considerably shorter response times for aperiodic jobs.

A number of fault localization techniques have been developed to reduce the time in manually debugging a faulty program. The technique of code coverage [8] has been recognized by its effectiveness in identifying suspicious statements that may contain the fault. However, a programmer still needs to manually examine each variable referenced in a suspicious statement and such a process can become extremely time-consuming if this suspicious statement is part of a loop. In this paper, we propose a novel technique called state coverage to significantly reduce the time in examining variables. We first insert a set of checkpoints to record the state of each variable referenced in a branching statement. We next execute the faulty program by a test suite consisting of both passed and failed cases. A state is statistically considered to be more suspicious if it appears more in failed cases and less in passed cases. We implemented both code coverage and state coverage in a debugging tool and used a commonly-used benchmark consisting of 58 faulty programs to evaluate their performance. For 34% of these programs, their faults are within 20 statement steps of the most suspicious statement identified by code coverage. By adding state coverage and breaking at the most suspicious state, we increase this ratio to 64%, an 88% performance improvement. Finally, we also explain a few cases in which both state coverage and code coverage cannot perform well.

Traditional real-time disk-scheduling algorithms service real-time tasks according to their deadlines. Such a priority-based algorithm, although satisfying real-time constraints, yields low disk utilization due to the excessive disk-seek time. Furthermore, it results in prolonged response time or even starvation for aperiodic tasks. In this paper, we propose a novel rate-based real-time disk-scheduling algorithm called WRR-SCAN (Weighted-Round-Robin SCAN). WRR-SCAN guarantees to meet the deadline of a real-time task by reserving disk bandwidth according to its real-time constraints. WRR-SCAN services scheduled tasks in scan order to minimize the disk-seek time. In addition, WRR-SCAN delivers better response time for aperiodic tasks which are served in best-effort manner by priority based algorithms. We conducted a set of extensive experiments to compare WRR-SCAN and SCAN-EDF, a priority-based algorithm studied extensively in literature. The experimental results show that WRR-SCAN reduces non-transmission overhead significantly and produces a guaranteed minimum data rate for aperiodic tasks while keeping the deadlines of real-time tasks.