Embedded Real-time Systems, Task Scheduling And Resource Sharing Model And Algorithm

Tasks must execute correctly and timely in a embedded real-time system. They may also access resources mutual exclusively. In general, the process and memory of a embedded real-time system are limited. In order to get an appropriate execution order of the tasks, the scheduling algorithm must be integrated with resource access control protocol correctly. In practice, the priority levels of embedded real-time system are insufficient. A proper priority mapping algorithm is needed to solve this problem. Many of the component-based embedded real-time software methodologies that decompose software into components and reuse these components from structural view fail to address issues of mapping components to tasks and using proper real-time scheduling algorithms from temporal view.In this dissertation, some important scheduling algorithms and resource protocols are studied. The faults of the way integrating preemption threshold scheduling algorithm with priority ceiling protocol and the increasing priority assignment (IPA) and decreasing priority assignment (DPA) algorithms are discussed. We attempt to find out a proper way to integrate scheduling algorithm and resource protocol, a mapping algorithm without affecting the schedulability of tasks set and a proper way mapping software component to task. We also want to select a proper scheduling model for component embedded real-time operating systems.We deduce that preemption threshold scheduling algorithm and stack resource policy (SRP) are suitable for embedded real-time systems. They both ensure that once a task is started, it cannot be blocked until completion. A new schedulability conditions for SRP is deduced through level-i busy period. Basing on new formulae, the properties of SRP are deduced, a priority assignment algorithm is also presented. It is deduced that preemption threshold shcheduling is a particular case for real-time system using stack resource policy. So, it is valid to integrate preemption threshold scheduling algorithm with stack resource policy. The stack resource policy-preemption threshold (SRP-PT) scheduling model is introduced by adding pseudo resource in SRP. The threshold over-high is avoided in SRP-PT by prohibiting tasks accessing real resources from accessing pseudo ones. It is showed that SRP-PT model is better than priority ceiling-priority ceiling protocol (PC-PCP). Simulation results show that the schedulability of SPR-PT is higher than that of SRP.Through analyzing the properties of non-preemption groups, it is proved that priority values increase successively in a group, and don't overlap between different groups. So, threshold section mapping (TSM) algorithm and a thread implementation architecture with event-driven are presented. Basing on properties of preemption threshold scheduling, they can improve schedulability of tasks set with less priority levels than IPA and DPA algorithms for independent tasks set. It is proved by simulation results.In this dissertation, a component model and a way mapping component to task are presented. A design idea is also presented. The capabilities of four kinds of scheduling algorithms are compared through simulation. It is proved that preemption threshold scheduling algorithm and SRP-PT model are proper for component embedded real-time operating systems.