Most of the process-schedulingalgorithms, which can be exploited by spacecraft avionics systems, fall into one of the two main categories: static algorithms and dynamicalgorithms. 12 Static algorithms assign priorit...
详细信息
ISBN:
(纸本)0780381556
Most of the process-schedulingalgorithms, which can be exploited by spacecraft avionics systems, fall into one of the two main categories: static algorithms and dynamicalgorithms. 12 Static algorithms assign priorities to processes before runtime. These algorithms bound the CPU utilization and require considerable information about the runtime parameters of processes in advance. These disadvantages encourage the spacecraft avionics system designers to exploit dynamicalgorithms instead. But these algorithms have their own disadvantages. For example, these algorithms require so many context switches to schedule the processes. This causes a notable overhead in the runtime. One of the well-known dynamicalgorithms is the MLF (Minimum Laxity First) algorithm. The MLF algorithm suffers from a serious problem (in addition to the need for so many context switches). This paper proposes a novel dynamicalgorithm called Optimized MLF which is an attempt to solve the problems of the MLF algorithm in order to make it more applicable to spacecraft avionics systems. The performance of the proposed schedulingalgorithm is evaluated through the use of mathematical modeling as well as simulation results. Both the mathematical model and simulation results show that the optimized MLF algorithm requires less context switches than the traditional MLF and makes the MLF algorithm more applicable to spacecraft avionics systems.
A hard real-time system is usually subject to stringent reliability and timing constraints due to the fact that failure to produce correct results in a timely manner may lead to a disaster. Almost all fault-tolerant s...
详细信息
A hard real-time system is usually subject to stringent reliability and timing constraints due to the fact that failure to produce correct results in a timely manner may lead to a disaster. Almost all fault-tolerant schedulingalgorithms at present are designed to deal with hardware faults, while less of those take possible software faults into account. Presented in this paper is a new software fault-tolerant real-time schedulingalgorithm that is similar to EOF, called EBPA (expectation-based probing algorithm). The important contributions of the algorithm are probing a certain steps during the executions of primaries, which leads to improving the predictive quality of canceling ineffective primaries when heavy workload occurs and preventing early failures in execution from triggering failures in the subsequent primary executions as soon as possible. Therefore, the algorithm increases the successful percentage of tasks' completion, and meanwhile decreases the wasted CPU time slots. The simulation experiments show that the algorithm has a better trade-offs between scheduling costs and scheduling performance than the well-known algorithms so far. Moreover, some experimental parameters, such as the number of probing steps and failure probability, are also taken into account.
It is shown that the problem of maximising the total reward of online tasks can be solved by finding the minimum of the maximum derivatives of the reward functions. Based on the modified approach and a close observati...
详细信息
It is shown that the problem of maximising the total reward of online tasks can be solved by finding the minimum of the maximum derivatives of the reward functions. Based on the modified approach and a close observation of task arrival characteristics, a heuristic algorithm with average complexity close to O(N) is presented.
This research addresses the timeliness of task execution in real-time systems. Specifically, we investigate the dynamicscheduling of tasks with well-defined timing constraints. We present a dynamic uniprocessor sched...
详细信息
This research addresses the timeliness of task execution in real-time systems. Specifically, we investigate the dynamicscheduling of tasks with well-defined timing constraints. We present a dynamic uniprocessor schedulingalgorithm with an O(n log n) worst case complexity. The preemptive scheduling performed by our algorithm is shown to be of higher efficiency than that of other known algorithms. Furthermore, tasks may be related by precedence constraints, and they may have arbitrary deadlines and start times (which need not equal their arrival times). An experimental evaluation or the algorithm compares its average case behavior to the worst case. An analytic model also presented in this paper is used for explanation of the experimental results and is validated with actual system measurements. The dynamic scheduling algorithm is the basis of a real-time multiprocessor operating system kernel developed in conjunction with this research. Specifically, this algorithm is used. at the lowest, threads-based layer of the kernel whenever threads are created.
暂无评论