Page 89 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes Three queues:
1. Q0 - time quantum 8 milliseconds
2. Q1 - time quantum 16 milliseconds

3. Q2 - FCFS
Scheduling:

1. A new job enters queue Q0 which is served FCFS . When it gains
CPU, job receives 8 milliseconds.
If it does not finish in 8 milliseconds, job is moved to queue Q1.

2. At Q1 job is again served FCFS and receives 16 additional
milliseconds. If it still does not complete, it is preempted and
moved to queue Q2.
3.6.1 Conventional Time-share Scheduling

The goals for conventional time-share scheduling are concerned with maximizing CPU utilization
and overall throughput, and minimizing average turn-around time, average waiting time, and
response time. These goals are designed to maximize the use of system resources while appearing
to provide an acceptable level of performance to the user. The algorithms used in conventional
time-share scheduling are generally relatively simple to implement and understand. They try
to effect a balance between system resource utilization and user perception of response and
turn-around time. First Come First Served (FCFS) scheduling is a simple first in, first out queue.
It is simple to implement but it has several deficiencies. Its average wait time is typically quite
long. It is non-preemptive, and it is subject to the convoy effect if there are many I/O bound
processes mixed with a few CPU bound processes. In this case, there can be large amounts of
idle system resource time as the I/O bound processes sit idle waiting for the CPU bound process
to complete. Shortest Job First (SJF) scheduling is provably optimal but requires clairvoyance
to fully implement, since it is usually not possible to know a priori which job in the wait queue
is the shortest job. There are methods, such as using the last processing burst or some function
of the last burst, that allow SJF scheduling to be emulated. SJF can be implemented either
preemptively or non-preemptively and its average waiting time is low. Priority scheduling is
somewhat similar to many real-time scheduling algorithms. Priority scheduling can be preemptive
or non-preemptive. Process starvation can be a problem with priority scheduling when many
high priority processes are competing for time. Process aging can help this situation but aging
effectively modifies the relative priorities of all process in the system and makes the system
non-deterministic. Round Robin scheduling is similar to FCFS scheduling but preemption is
added so that each time quantum a new process receives access to the system resources. This
way each process gets a share of the system resources without having to wait for all processes
in front of it to run to completion. Its average waiting time is typically rather long and its
performance is directly related to the size of the time quantum. Round Robin scheduling is
the degenerative case of preemptive priority scheduling when all priorities are equal. These
scheduling algorithms are all in common use but they have deficiencies when applied to real-
time scheduling. In particular, the lack of determinacy is a serious problem that makes them
unsuitable for real-time scheduling.
3.6.2 Real-time Scheduling

In direct contrast with the goals for time-share scheduling, the goals for real-time scheduling are
concerned with minimizing the time from stimulus to response, completing tasks within specific
time constraints, and providing deterministic performance. Although system resource utilization
is still of interest, it is no longer a primary driver. Determinism and temporal correctness are

82 LOVELY PROFESSIONAL UNIVERSITY