Abstract comparisons between the
multilevel queue and Multilevel Feedback Queue CPU scheduling algorithm.
It is a long time running discussion in scheduling algorithms to decide
which of the processes in the ready queue is to be allocated the
CPU first. However there exist some problems with these
algorithms when facing the fast growth of real-time systems and
handhelds, in which requirements for interactivity and the growth of
system loads need to be taken into corresponding consideration and in
my approach I proposed which is best.
I. INTRODUCTION
When a computer is multi programmed, it frequently has
multiple processes competing for the CPU at the same time. This
situation occurs whenever two or more processes are simultaneously in
the ready state. If only one CPU is available, a choice has to be made
which process to run next. The part of the operating system
that makes the choice is called the scheduler and the algorithm it
uses is called the scheduling algorithm [1].
In a single-processor system, only one process can run at a time, any
others must wait until the CPU is free and can be rescheduled. The
objective of multiprogramming is to have some process running at all
times, to maximize CPU utilization [2]. Many criteria have been
suggested for comparing CPU scheduling algorithms. Which
characteristics are used for comparison can make a substantial
difference in which algorithm is judged to be best in CPU Utilization,
Throughput, Turnaround time and Response time [2].
A. CPU utilization
We want to keep the CPU as busy as possible. Conceptually, CPU
utilization can range from 0 to 100 %. In a real system, it should range
from 40 % (for alightly loaded system) to 90 % (for a heavily used
system).
B. Throughput:
If the CPU is busy executing processes, then work is being done. One
measure of work is the number of processes that are completed per time
unit, called throughput.
C. Turnaround time:
The interval from the time of submission of a process to the
time of completion is the turnaround time. Turnaround time is the sum of
the periods spent waiting to get into memory, waiting in the
ready queue, executing on the CPU, and doing I/O.
D. Waiting time:
Waiting time is the sum of the periods spent waiting in the ready queue.
E. Response time:
In an interactive system, turnaround time may not be the best criterion.
Often, a process can produce some output fairly early and can continue
computing new results while previous results are being output to the
user. Thus, another measure is the time from the submission of a request
until the first response is produced. This measure, called response
time, is the time it takes to start responding, not the time it takes
to output the response. The turnaround time is generally limited by the
speed of the output device [2]. It is desirable to maximize CPU
utilization and throughput and to minimize turnaround time, waiting
time, and response time. In most cases, we optimize the average measure.
However, under some circumstances, it is desirable to optimize the
minimum or maximum values rather than the average.
II. ESSENTIAL DIFFERENCES BETWEEN MULTILEVEL QUEUE (MLQ) AND MULTILEVEL FEEDBACK QUEUE (MLFQ)
1.In Multilevel queue (MLQ) processes are classified into different
groups. For example, common division is made between foreground
(interactive) processes and background (batch) processes which
have different response time and scheduling needs. In
addition In Multilevel Feedback queue (MLFQ) it allows a process to move
between the queues, according to the characteristics of their CPU
burst.
2. `In Multilevel queue (MLQ) the foreground queue might be scheduled by
Round Robin algorithm while the back ground queue is scheduled by
First Come First Serve algorithm. There is possibility of starvation.
But in Multilevel Feedback queue (MLFQ) if a process uses too much CPU
time it will be moved to a lower-priority queue. This schema leaves I/O
bound and interactive processes in the higher priority queues. In
addition, a process that waits too long in a lower priority queue may be
moved to a higher-priority queue preventing starvation.
III. EXAMPLES
Multilevel queue (MLQ) algorithm with five queues, listed below with order of priority:
a) System processes
b) Interactive processes
c) Interactive editing processes d) Batch processes
e) Student processes
Algorithm chooses the process from the occupied queue that has the
highest priority, and run that process either Preemptive or
Non-preemptively Each queue has its own scheduling algorithm or policy.
Possibility-I Each queue has absolute priority over lower-priority
queues then no process in the queue could run unless the queues for the
highest-priority processes were all empty. For example, in the below
Fig.
1 no process in the batch queue could run unless the queues for system
processes, interactive processes and interactive editing processes will
all empty. Possibility-II
if there is a time slice between the queues then each queue gets a
certain amount of CPU times, which it can then schedule among the
processes in its queue. For instance; foreground processes may
have priority over background [2].
But, in Multilevel Feedback queue (MLFQ), it contains two queues,
lower-priority queues and higher- priority queues. In this the
separation of processes are done according to the characteristics
of their CPU bursts.
3. In Multilevel queue (MLQ) the processes are permanently assigned to
one queue based on their memory size, process priority or process type.
80% of the CPU time to fore ground queue using Round Robin (RR).
20% of the CPU time to back ground queue using First Come First Serve (FCFS).
Since processes do not move between queues so, this policy has the advantage of low scheduling overhead, but it is inflexible.
Highest priority
System processes
Interactive processes
Interactive editing processes
Batch processes
Student processes
Lowest priority
Fig. 1: Multilevel queue scheduling
No process in the batch queue could run unless the queue for system
processes and interactive processes were all empty. If an
interactive process enters the ready queue while a batch process
was running, the batch would be preempted
Now we will see the example to explain multilevel feedback queue (MLFQ). It contains three queues numbered from 0 to 2.
Three queues:
Q0 - Round Robin (RR) with time quantum 8 milliseconds
Q1 - Round Robin (RR) time quantum 16 milliseconds
Q2 - First Come First Serve (FCFS)
Scheduling
A new job enters queue Q0 which is served Q2.
When it gains CPU, job receives 8 milliseconds. If
it does not finish in 8 milliseconds, job is moved to queue Q
At Q1 job is again served Q2 and receives 16 additional milliseconds. If
it still does not complete, it is preempted and moved to queue.
Q
IV. CONCLUSION
Multilevel Feedback Queue (MLFQ) is interestingbecause instead of demanding a priori knowledge of the
nature of a job, it instead observes the execution of a joband
prioritizes it accordingly. In this way, it manages toachieve the best
of both worlds, it can deliver excellentoverall performance (similar to
SJF/STCF) for shortrunning interactive jobs, and is fair and makes
progress for long-running CPU-intensive workloads. For this reason, many
systems, including BSD UNIX derivatives [LM+89, B86], Solaris [M06] and
Windows NT and subsequent Windows operating systems [CS97] use a form
of MLFQ as their base scheduler.
ACKNOWLEDGMENT
I thankful to The Principal, St. Pious X Degree & P.G. College for
Women for providing literaturefacilities and also I thankful to my
colleagues for encouraging me in this work.
REFERENCES
[1] S. Andrew Tanenbaum, Modern Operating Systems, 2nd ed., Prentice-Hall of India Private Limited, New Delhi
[2] Abraham Silberschatz, Peter Baer Galvin and Greg Gagne, Operating
System Concepts, 7th ed., John Wiley & Sons (Asia) Pvt. Ltd.,
Singapore.
Tidak ada komentar:
Posting Komentar