Abstract: Tasks of an application program of an embedded system are managed by the scheduler of a real-time operating system
(RTOS). Most RTOSs adopt just fixed priority scheduling, which is not optimal in all cases. Some applications require earliest deadline
first (EDF) scheduling, which is an optimal scheduling algorithm.
In order to develop an efficient real-time embedded system, the
scheduling algorithm of the RTOS should be selectable. The paper presents a method to customize the scheduler using aspectoriented
programming. We define aspects to replace the fixed priority scheduling mechanism of an OSEK OS with an EDF scheduling
mechanism. By using the aspects, we can customize the scheduler
without modifying the original source code. We have applied the
aspects to an OSEK OS and get a customized operating system with
EDF scheduling. The evaluation results show that the overhead of
aspect-oriented programming is small enough.
Abstract: Wireless channels are characterized by more serious
bursty and location-dependent errors. Many packet scheduling
algorithms have been proposed for wireless networks to guarantee
fairness and delay bounds. However, most existing schemes do not
consider the difference of traffic natures among packet flows. This
will cause the delay-weight coupling problem. In particular, serious
queuing delays may be incurred for real-time flows. In this paper, it
is proposed a scheduling algorithm that takes traffic types of flows
into consideration when scheduling packets and also it is provided
scheduling flexibility by trading off video quality to meet the
playback deadline.
Abstract: Scheduling algorithm is a key technology in satellite
switching system with input-buffer. In this paper, a new scheduling
algorithm and its realization are proposed. Based on Crossbar
switching fabric, the algorithm adopts serial scheduling strategy and
adjusts the output port arbitrating strategy for the better equity of every
port. Consequently, it increases the matching probability. The
algorithm can greatly reduce the scheduling delay and cell loss rate.
The analysis and simulation results by OPNET show that the proposed
algorithm has the better performance than others in average delay and
cell loss rate, and has the equivalent complexity. On the basis of these
results, the hardware realization and simulation based on FPGA are
completed, which validate the feasibility of the new scheduling
algorithm.
Abstract: This paper presents a modified version of the
maximum urgency first scheduling algorithm. The maximum
urgency algorithm combines the advantages of fixed and dynamic
scheduling to provide the dynamically changing systems with
flexible scheduling. This algorithm, however, has a major
shortcoming due to its scheduling mechanism which may cause a
critical task to fail. The modified maximum urgency first scheduling
algorithm resolves the mentioned problem. In this paper, we propose
two possible implementations for this algorithm by using either
earliest deadline first or modified least laxity first algorithms for
calculating the dynamic priorities. These two approaches are
compared together by simulating the two algorithms. The earliest
deadline first algorithm as the preferred implementation is then
recommended. Afterwards, we make a comparison between our
proposed algorithm and maximum urgency first algorithm using
simulation and results are presented. It is shown that modified
maximum urgency first is superior to maximum urgency first, since it
usually has less task preemption and hence, less related overhead. It
also leads to less failed non-critical tasks in overloaded situations.
Abstract: In any distributed systems, process scheduling plays a
vital role in determining the efficiency of the system. Process scheduling algorithms are used to ensure that the components of the
system would be able to maximize its utilization and able to complete all the processes assigned in a specified period of time.
This paper focuses on the development of comparative simulator for distributed process scheduling algorithms. The objectives of the works that have been carried out include the development of the
comparative simulator, as well as to implement a comparative study
between three distributed process scheduling algorithms; senderinitiated,
receiver-initiated and hybrid sender-receiver-initiated
algorithms. The comparative study was done based on the Average Waiting Time (AWT) and Average Turnaround Time (ATT) of the
processes involved. The simulation results show that the performance of the algorithms depends on the number of nodes in the system.
Abstract: Grid computing is a form of distributed computing
that involves coordinating and sharing computational power, data
storage and network resources across dynamic and geographically
dispersed organizations. Scheduling onto the Grid is NP-complete,
so there is no best scheduling algorithm for all grid computing
systems. An alternative is to select an appropriate scheduling
algorithm to use in a given grid environment because of the
characteristics of the tasks, machines and network connectivity. Job
and resource scheduling is one of the key research area in grid
computing. The goal of scheduling is to achieve highest possible
system throughput and to match the application need with the
available computing resources. Motivation of the survey is to
encourage the amateur researcher in the field of grid computing, so
that they can understand easily the concept of scheduling and can
contribute in developing more efficient scheduling algorithm. This
will benefit interested researchers to carry out further work in this
thrust area of research.
Abstract: In an open real-time system environment, the coexistence of different kinds of real-time and non real-time applications makes the system scheduling mechanism face new requirements and challenges. One two-level scheduling scheme of the open real-time systems is introduced, and points out that hard and soft real-time applications are scheduled non-distinctively as the same type real-time applications, the Quality of Service (QoS) cannot be guaranteed. It has two flaws: The first, it can not differentiate scheduling priorities of hard and soft real-time applications, that is to say, it neglects characteristic differences between hard real-time applications and soft ones, so it does not suit a more complex real-time environment. The second, the worst case execution time of soft real-time applications cannot be predicted exactly, so it is not worth while to cost much spending in order to assure all soft real-time applications not to miss their deadlines, and doing that may cause resource wasting. In order to solve this problem, a novel two-level real-time scheduling mechanism (including scheduling profile and scheduling algorithm) which adds the process of dealing with soft real-time applications is proposed. Finally, we verify real-time scheduling mechanism from two aspects of theory and experiment. The results indicate that our scheduling mechanism can achieve the following objectives. (1) It can reflect the difference of priority when scheduling hard and soft real-time applications. (2) It can ensure schedulability of hard real-time applications, that is, their rate of missing deadline is 0. (3) The overall rate of missing deadline of soft real-time applications can be less than 1. (4) The deadline of a non-real-time application is not set, whereas the scheduling algorithm that server 0 S uses can avoid the “starvation" of jobs and increase QOS. By doing that, our scheduling mechanism is more compatible with different types of applications and it will be applied more widely.
Abstract: Advances in computing applications in recent years
have prompted the demand for more flexible scheduling models for
QoS demand. Moreover, in practical applications, partly violated
temporal constraints can be tolerated if the violation meets certain
distribution. So we need extend the traditional Liu and Lanland model
to adapt to these circumstances. There are two extensions, which are
the (m, k)-firm model and Window-Constrained model. This paper
researches on weakly hard real-time constraints and their combination
to support QoS. The fact that a practical application can tolerate some
violations of temporal constraint under certain distribution is
employed to support adaptive QoS on the open real-time system. The
experiment results show these approaches are effective compared to
traditional scheduling algorithms.
Abstract: Scheduling algorithms are used in operating systems
to optimize the usage of processors. One of the most efficient
algorithms for scheduling is Multi-Layer Feedback Queue (MLFQ)
algorithm which uses several queues with different quanta. The most
important weakness of this method is the inability to define the
optimized the number of the queues and quantum of each queue. This
weakness has been improved in IMLFQ scheduling algorithm.
Number of the queues and quantum of each queue affect the response
time directly. In this paper, we review the IMLFQ algorithm for
solving these problems and minimizing the response time. In this
algorithm Recurrent Neural Network has been utilized to find both
the number of queues and the optimized quantum of each queue.
Also in order to prevent any probable faults in processes' response
time computation, a new fault tolerant approach has been presented.
In this approach we use combinational software redundancy to
prevent the any probable faults. The experimental results show that
using the IMLFQ algorithm results in better response time in
comparison with other scheduling algorithms also by using fault
tolerant mechanism we improve IMLFQ performance.
Abstract: EDF (Early Deadline First) algorithm is a very important scheduling algorithm for real- time systems . The EDF algorithm assigns priorities to each job according to their absolute deadlines and has good performance when the real-time system is not overloaded. When the real-time system is overloaded, many misdeadlines will be produced. But these misdeadlines are not uniformly distributed, which usually focus on some tasks. In this paper, we present an adaptive fuzzy control scheduling based on EDF algorithm. The improved algorithm can have a rectangular distribution of misdeadline ratios among all real-time tasks when the system is overloaded. To evaluate the effectiveness of the improved algorithm, we have done extensive simulation studies. The simulation results show that the new algorithm is superior to the old algorithm.
Abstract: Grid computing is a high performance computing
environment to solve larger scale computational applications. Grid
computing contains resource management, job scheduling, security
problems, information management and so on. Job scheduling is a
fundamental and important issue in achieving high performance in
grid computing systems. However, it is a big challenge to design an
efficient scheduler and its implementation. In Grid Computing, there
is a need of further improvement in Job Scheduling algorithm to
schedule the light-weight or small jobs into a coarse-grained or
group of jobs, which will reduce the communication time,
processing time and enhance resource utilization. This Grouping
strategy considers the processing power, memory-size and
bandwidth requirements of each job to realize the real grid system.
The experimental results demonstrate that the proposed scheduling
algorithm efficiently reduces the processing time of jobs in
comparison to others.
Abstract: Video sensor networks operate on stringent requirements
of latency. Packets have a deadline within which they have
to be delivered. Violation of the deadline causes a packet to be
treated as lost and the loss of packets ultimately affects the quality
of the application. Network latency is typically a function of many
interacting components. In this paper, we propose ways of reducing
the forwarding latency of a packet at intermediate nodes. The
forwarding latency is caused by a combination of processing delay
and queueing delay. The former is incurred in order to determine the
next hop in dynamic routing. We show that unless link failures in a
very specific and unlikely pattern, a vast majority of these lookups
are redundant. To counter this we propose source routing as the
routing strategy. However, source routing suffers from issues related
to scalability and being impervious to network dynamics. We propose
solutions to counter these and show that source routing is definitely
a viable option in practical sized video networks. We also propose a
fast and fair packet scheduling algorithm that reduces queueing delay
at the nodes. We support our claims through extensive simulation on
realistic topologies with practical traffic loads and failure patterns.
Abstract: All practical real-time scheduling algorithms in multiprocessor systems present a trade-off between their computational complexity and performance. In real-time systems, tasks have to be performed correctly and timely. Finding minimal schedule in multiprocessor systems with real-time constraints is shown to be NP-hard. Although some optimal algorithms have been employed in uni-processor systems, they fail when they are applied in multiprocessor systems. The practical scheduling algorithms in real-time systems have not deterministic response time. Deterministic timing behavior is an important parameter for system robustness analysis. The intrinsic uncertainty in dynamic real-time systems increases the difficulties of scheduling problem. To alleviate these difficulties, we have proposed a fuzzy scheduling approach to arrange real-time periodic and non-periodic tasks in multiprocessor systems. Static and dynamic optimal scheduling algorithms fail with non-critical overload. In contrast, our approach balances task loads of the processors successfully while consider starvation prevention and fairness which cause higher priority tasks have higher running probability. A simulation is conducted to evaluate the performance of the proposed approach. Experimental results have shown that the proposed fuzzy scheduler creates feasible schedules for homogeneous and heterogeneous tasks. It also and considers tasks priorities which cause higher system utilization and lowers deadline miss time. According to the results, it performs very close to optimal schedule of uni-processor systems.