Priority and multilevel queue

Priority

•Priority scheduling is a more general case of SJF, in which each job is assigned a priority and the job with the highest priority gets scheduled first. (SJF uses the inverse of the next expected burst time as its priority – The smaller the expected burst, the higher the priority.)
•Note that in practice, priorities are implemented using integers within a fixed range, but there is no agreed-upon convention as to whether “high” priorities use large numbers or small numbers. This book uses low number for high priorities, with 0 being the highest possible priority.
•For example, the following Gantt chart is based upon these process burst times and priorities, and yields an average waiting time of 8.2ms:

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

 Priorities can be assigned either internally or externally. Internal priorities are assigned by the

 

OS using criteria such as average burst time, ratio of CPU to I/O activity, system resource use, and other factors available to the kernel. External priorities are assigned by users, based on the importance of the job, fees paid politics, etc.

•Priority scheduling can be either preemptive or non- preemptive.
•Priority scheduling can suffer from a major problem known as indefinite blocking, or starvation, in which a low-priority task can wait forever because there are always some other joins around that have higher priority.
- If this problem is allowed to occur, then processes will either run eventually when the system load lightens (at say 2.00 a.m.), or will eventually get lost when the system is shut down or crashes. (There are rumors of jobs that has been stuck for years.)
- One common solution to this problem is aging, in which priorities of jobs increase the longer they wait. Under this scheme a low priority job will eventually get its priority raised high enough that it gets run.

 

MULTILEVEL QUEUE

Multilevel Queue Scheduling

•When processes can be readily categorized, then multiple separate queues can be established, each implementing whatever scheduling algorithm is most appropriate for that type of job, and/or with different parametric adjustments.
•Scheduling must also be done between queues that is scheduling one queue to get time relative to other queues. Two common options are strict priority ( No job in a lower priority queues runs until all higher priority queues are empty) and round –robin ( each queue gets a time slice in turn, possibly of different sizes.)
•Note that under this algorithm jons cannot switch from queue to queue – Once they are assigned a queue, that is their queue until finish.

 

 

 Multilevel Feedback Queue Scheduling

 

•Multilevel feedback queue scheduling is similar to the ordinary multilevel queue scheduling described above, except jobs may be moved from one queue to another for a variety of reasons:
-If the characteristics of a job change between CPU-intensive and I/o intensive, then it may be appropriate to switch a job from one queue to another.
- Aging can also be incorporated, so that a job that has waited for a long time can get bumped up into a higher priority queue for a while.
•Multilevel feedback queue scheduling is the most flexible, because it can be tuned for any situation. But it is also the most complex to implement because of all the adjustable parameters: Some of the parameters which define the system include:
-The number of queues
-The scheduling algorithm for each queue
-The methods used to upgrade or demote processes from one queue to another. (Which may be different)
-The method used to determine which queue a process enters initially.