Explore chapters and articles related to this topic
Embedded Computing Systems and Hardware/Software Codesign
Published in Wai-Kai Chen, Computer Aided Design and Design Automation, 2018
A fundamental result in real-time scheduling is known as rate-monotonic scheduling. This technique schedules a set of processes which run independently on a single CPU. Each process has its own period, with the deadline happening at the end of each period. There can be arbitrary relationships between the periods of the processes. It is assumed that data does not in general arrive at the beginning of the period, so there are no assumptions about when a process goes from waiting to ready within a period. This scheduling policy uses static priorities—the priorities for the processes are assigned before execution begins and do not change. It can be shown that the optimal priority assignment is based on period—the shorter the period, the higher the priority. This priority assignment ensures that all processes will meet their deadlines on every period. It can also be shown that at most, 69% of the CPU is used by this scheduling policy. The remaining cycles are spent waiting for activities to happen—since data arrival times are not known, it is not possible to utilize 100% of the CPU cycles.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
We use τi to represent a periodic task and Ji to represent a job, i.e., an instance of τi. In addition, we use πi to represent the priority of job Ji. In static priority scheduling such as rate monotonic scheduling (RMS) (or deadline monotonic scheduling), every job of a task has the same priority. In dynamic priority scheduling such as earliest deadline first (EDF) scheduling, different jobs in a task have different priorities. Also, in our notation for a pair of jobs Ji,Jj,i<j, we assume that job Ji has higher priority. We now describe three basic assumptions used by the priority inheritance approach.
Software Design Considerations for Real-Time DSP Systems
Published in Gillian M. Davis, Noise Reduction in Speech Applications, 2018
Rate-monotonic scheduling is an optimal fixed priority policy where the higher the frequency (1/period) of a task, the higher is its priority. This approach can be implemented in any OS supporting the fixed priority preemptive scheme, such as DSP/BIOS. Rate-monotonic scheduling assumes the deadline of a periodic task is the same as its period.
TDCS: a new scheduling framework for real-time multimedia OS
Published in International Journal of Parallel, Emergent and Distributed Systems, 2020
Wei Hu, Tianao Ma, Yonghao Wang, Fangfang Xu, Joshua Reiss
For each task, the CPU utilisation is , so the total utilisation is Normally we have . The rate monotonic scheduling (RMS) algorithm assigns the task priority according to the task period. The task with a shorter period has a higher priority. Liu and Layland [24] proved that the sufficient condition of scheduling of RMS is where n is the number of tasks. This condition is sufficient but not necessary based on the tasks that are preemptible. Lehoczky 1989 [30] showed the sufficient and necessary condition of schedulability of RMS with less up bond CPU utilisation but more complex schedulability test formula.