REAL-TIME SCHEDULING AND SCHEDULABILITY ANALYSIS As in preparing a schedule of to-do tasks in everyday life, scheduling a set of computer tasks (also known as processes) is to determine when to execute which task, thus determining the execution order of these tasks; and in the case of a multiprocessor or distributed system, to also determine an assignment of these tasks to specific processors. This task assignment is analogous to assigning tasks to a specific person in a team of people. Scheduling is a central activity of a computer system, usually performed by the operating system | Real-Time Systems Scheduling Analysis and Verification. Albert M. K. Cheng Copyright 2002 John Wiley Sons Inc. ISBN 0-471-18406-3 CHAPTER 3 REAL-TIME SCHEDULING AND SCHEDULABILITY ANALYSIS As in preparing a schedule of to-do tasks in everyday life scheduling a set of computer tasks also known as processes is to determine when to execute which task thus determining the execution order of these tasks and in the case of a multiprocessor or distributed system to also determine an assignment of these tasks to specific processors. This task assignment is analogous to assigning tasks to a specific person in a team of people. Scheduling is a central activity of a computer system usually performed by the operating system. Scheduling is also necessary in many non-computer systems such as assembly lines. In non-real-time systems the typical goal of scheduling is to maximize average throughput number of tasks completed per unit time and or to minimize average waiting time of the tasks. In the case of real-time scheduling the goal is to meet the deadline of every task by ensuring that each task can complete execution by its specified deadline. This deadline is derived from environmental constraints imposed by the application. Schedulability analysis is to determine whether a specific set of tasks or a set of tasks satisfying certain constraints can be successfully scheduled completing execution of every task by its specified deadline using a specific scheduler. Schedulability Test A schedulability test is used to validate that a given application can satisfy its specified deadlines when scheduled according to a specific scheduling algorithm. This schedulability test is often done at compile time before the computer system and its tasks start their execution. If the test can be performed efficiently then it can be done at run-time as an on-line test. 41 42 REAL-TIME SCHEDULING AND SCHEDULABILITY ANALYSIS Schedulable Utilization A schedulable utilization is the maximum .
