7 Intelligent and Connected Cyber-Physical Systems: A Perspective. . .
365
• Turnaround time: From the point of view of a particular task, the important
criterion is how long it takes to execute that task. The interval from the time
of submission of a task to the time of completion is the turnaround time.
• Waiting time: The processor-scheduling algorithm does not affect the amount of
time during which a task executes. It affects only the amount of time that a task
spends waiting.
It is desirable to maximize the processor utilization and throughput and to
minimize the turnaround time, waiting time, and response time. In most cases, we
optimize the average measure. However, under some circumstances, we prefer to
optimize the minimum or maximum values rather than the average.
There are many different scheduling algorithms. The simplest one is the firstcome, first-served (FCFS) scheduling algorithm. With this scheme, the task that
requests the processor first is allocated the processor first. The average waiting time
under the FCFS policy is often quite long. Note also that the FCFS scheduling
algorithm is nonpreemptive. Once the processor has been allocated to a task, that
task keeps the processor until it releases the processor, often by terminating. The
FCFS algorithm is thus particularly troublesome for time-sharing systems, where it
is important that each task get a share of the processor at regular intervals. It would
be disastrous to allow one task to keep the processor for an extended period.
A different approach to processor scheduling is the shortest-job-first (SJF)
scheduling algorithm. This algorithm associates with each task the length of the
task’s remaining execution time. When the processor is available, it is assigned
to the task that has the shortest remaining execution time. The SJF scheduling
algorithm is provably optimal, in that it gives the minimum average waiting time
for a given set of tasks. Moving a short task before a long one decreases the waiting
time of the short task more than it increases the waiting time of the long task.
Consequently, the average waiting time decreases. The real difficulty with the SJF
algorithm is knowing the length of the remaining execution time, which often has
to be approximated. The SJF algorithm can be either preemptive or nonpreemptive.
If the newly arrived task is shorter than what is left of the currently executing task,
a preemptive SJF algorithm will preempt the currently executing task, whereas a
nonpreemptive SJF algorithm will allow the currently running task to finish.
The SJF algorithm is a special case of the general priority-scheduling algorithm.
A priority is associated with each task, and the processor is allocated to the task with
the highest priority. Equal-priority tasks are scheduled in FCFS order. Priorities
are generally indicated by some fixed range of numbers, such as 0–7 or 0–4095.
However, there is no general agreement on whether 0 is the highest or lowest
priority. Priorities can be defined either internally or externally. Internally defined
priorities use some measurable quantity or quantities to compute the priority of a
task. For example, time limits, memory requirements, and the number of open files
have been used in computing priorities. External priorities are set by criteria outside
the operating system, such as the importance of the task. Priority scheduling can
be either preemptive or nonpreemptive. A major problem with priority scheduling
algorithms is indefinite blocking, or starvation. A priority scheduling algorithm can
365
• Turnaround time: From the point of view of a particular task, the important
criterion is how long it takes to execute that task. The interval from the time
of submission of a task to the time of completion is the turnaround time.
• Waiting time: The processor-scheduling algorithm does not affect the amount of
time during which a task executes. It affects only the amount of time that a task
spends waiting.
It is desirable to maximize the processor utilization and throughput and to
minimize the turnaround time, waiting time, and response time. In most cases, we
optimize the average measure. However, under some circumstances, we prefer to
optimize the minimum or maximum values rather than the average.
There are many different scheduling algorithms. The simplest one is the firstcome, first-served (FCFS) scheduling algorithm. With this scheme, the task that
requests the processor first is allocated the processor first. The average waiting time
under the FCFS policy is often quite long. Note also that the FCFS scheduling
algorithm is nonpreemptive. Once the processor has been allocated to a task, that
task keeps the processor until it releases the processor, often by terminating. The
FCFS algorithm is thus particularly troublesome for time-sharing systems, where it
is important that each task get a share of the processor at regular intervals. It would
be disastrous to allow one task to keep the processor for an extended period.
A different approach to processor scheduling is the shortest-job-first (SJF)
scheduling algorithm. This algorithm associates with each task the length of the
task’s remaining execution time. When the processor is available, it is assigned
to the task that has the shortest remaining execution time. The SJF scheduling
algorithm is provably optimal, in that it gives the minimum average waiting time
for a given set of tasks. Moving a short task before a long one decreases the waiting
time of the short task more than it increases the waiting time of the long task.
Consequently, the average waiting time decreases. The real difficulty with the SJF
algorithm is knowing the length of the remaining execution time, which often has
to be approximated. The SJF algorithm can be either preemptive or nonpreemptive.
If the newly arrived task is shorter than what is left of the currently executing task,
a preemptive SJF algorithm will preempt the currently executing task, whereas a
nonpreemptive SJF algorithm will allow the currently running task to finish.
The SJF algorithm is a special case of the general priority-scheduling algorithm.
A priority is associated with each task, and the processor is allocated to the task with
the highest priority. Equal-priority tasks are scheduled in FCFS order. Priorities
are generally indicated by some fixed range of numbers, such as 0–7 or 0–4095.
However, there is no general agreement on whether 0 is the highest or lowest
priority. Priorities can be defined either internally or externally. Internally defined
priorities use some measurable quantity or quantities to compute the priority of a
task. For example, time limits, memory requirements, and the number of open files
have been used in computing priorities. External priorities are set by criteria outside
the operating system, such as the importance of the task. Priority scheduling can
be either preemptive or nonpreemptive. A major problem with priority scheduling
algorithms is indefinite blocking, or starvation. A priority scheduling algorithm can