Scheduling (Algorithms) Policies (Priority)

Scheduling (Algorithms) Policies (Priority):

These are the following different types  of common policies or algorithms:

1)      First Come First Served (FCFS) scheduling: This is non-preemptive technique. A single queue of ready processes is maintained, and the dispatcher always picks the first one. This method does not emphasize throughput, since long processes are allowed to monopolize CPU, For the same reason, the response time with FCFS can be high (with respect to execution time), especially if there is a high variance in process execution times. This is also known FCFS scheduling.

Consider the following example of two processes-

In the several processes come on different job p1, p2 and p3 respectively, here p2 and p3 jobs required less than or comparatively p1 process (job), but computer run p1 process in the process of FCFS scheduler. P2 and p3 process has in ready queue in waiting process state.

Advantages: These are the following advantages of FCFS-

·         It is Simple policy.

·         It is easy to understand

·         It follows the First come first served method.

           Disadvantages: These are the following disadvantages of FCFS-

·         This scheduling method is non-preemptive, the process will run until it finishes.

·         Because of this non-preemptive scheduling, short processes which are at the back of the queue have to wait for the long process at the front to finish.

 

 Shortest job first (SJF) scheduling: It is known as the shorted job first. In this policy shortest job is selected in READY state and execute it. Here job or process is done on the basis of it having shortest execution time. If two processes have the same CPU time then FCFS is followed. As an example, consider the following set of processes.


Using shortest job scheduling this process would be scheduled in the P4-P1-P3-P2 waiting time is 0+3+8+16/4=6.75 units of time.

            If we were using the FCFS scheduling policy then the average waiting time will be -0+3+15+23/4=10.75 units of time. Shortest job first may implement in either non-preemptive or preemptive variety.

 

Round robin scheduling: Round robin schedule is oldest method. It is simplest widely used scheduling policy. This policy is first used in a time sharing and multi-user system. In the round robin scheme, a process is selected for running from the READY queue in FIFO sequence. In round robin scheme the CPU time is divided into time slices. Each process is allocated a small time slice (from 1 to 100 milliseconds) while it is running. No process can run for more than one time slice when there are others waiting in the READY queue. If a process needs more CPU time to complete after using one time slice, it goes to the end of READY queue to wait the next allocation. Round robin scheduling utilizes the system resources in any equitable manner.

For example: There are three processes P1, P2 and P3 with required the following CPU time.

 


 

If we use a time slice of 5 units of time, then P1 gets the first 5 units, of time. Since it requires another 20 units of time, it is preempted after the first time slice and CPU is given to the next process that is P2. Since P2 just needs 5 units of time it terminates as time slice expires. The CPU is then given to the next process P3. Once each process is receive one time slice, the CPU running to P1 for an additional time slice.

 

1.      Shortest Remaining Time: It is the preemptive counterpart of SJF and useful in time-sharing environment. In SRT scheduling, the process with the smallest estimate run-time to completion is run next, including new arrivals. In SJF scheme, once a job begins executing, it runs to completion.

In SJF scheme, a running process may be preempted by a new arrival process with shortest estimated run-time. The algorithm SRT has higher overhead than its counterpart SJF. The SRT must keep track of the elapsed time of the running process and must handle occasional preemptions. In this scheme, arrival of small processes will run almost immediately. However, longer jobs have even longer mean waiting time.

2.      Priority Scheduler: The basic idea is straightforward each process is assigned a priority, and priority is allowed to run. Equal-Priority processes are scheduled in FCFS order. The shortest-Job-First (SJF) algorithm is a special case of general priority scheduling algorithm. An SJF algorithm is simply a priority algorithm where the priority is the inverse of the (predicted) next CPU burst. That is, the longer the CPU burst, the lower the priority and vice versa. Priority can be defined either internally or externally. Internally defined priorities use some measurable quantities or qualities to compute priority of a process.

Examples of Internal priorities are-

·         Time limits.

·         Memory requirements.

·         File requirements, for example, number of open files.

·         CPU Vs I/O requirements.

Externally defined priorities are set by criteria that are external to operating system such as-

·         The importance of process.

·         Type or amount of funds being paid for computer use.

·         The department sponsoring the work.

·         Politics.

·         Priority scheduling can be either preemptive or non-preemptive

·         A preemptive priority algorithm will preemptive the CPU if the priority of the newly arrival process is higher than the priority of the currently running process.

·         A non-preemptive priority algorithm will simply put the new process at the head of the ready queue.

 

A major problem with priority scheduling is indefinite blocking or starvation. A solution to the problem of indefinite blockage of the low-priority process is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long period of time.

 

3.      Multilevel queue scheduling: A multilevel queue scheduling algorithm partitions the ready queue in several separate queues, for instance

 

 

In a multilevel queue scheduling processes are permanently assigned to one queue. The processes are permanently assigned to one another, based on some property of the process, such as

·         Memory size

·         Process priority

·         Process type

Algorithms choose 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: If 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 above figure 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;

·         80% of the CPU time to foreground queue using RR.

·         20% of the CPU time to background queues using FCFS.

Since processes do not move between queues so, this policy has the advantage of low scheduling overhead, but it is inflexible.

 

4.      Multi-level Feedback scheduling: Multilevel feedback queue-scheduling algorithm allows a process to move between queues. It uses many ready queues and associates a different priority with each queue. The Algorithm chooses to process with highest priority from the occupied queue and run that process either preemptively or un-preemptively. If the process uses too much CPU time it will move to a lower-priority queue. Similarly, a process that wait too long in the lower-priority queue may be moved to a higher-priority queue.

Figure: Multilevel Feedback Queue Scheduling

 

Example:

·         A process entering the ready queue is placed in queue 0.

·         If it does not finish within 8 milliseconds time, it is moved to the tail of queue 1.

·         If it does not complete, it is preempted and placed into queue 2.

·         Processes in queue 2 run on a FCFS basis, only when 2 run on a FCFS basis queue, only when queue 0 and queue 1 are empty.

  

Comments

Post a Comment

Thank you for message

https://asp-net22-23.blogspot.com/

classification of operating System

  Types of Operating System: There are many different Operating Systems. But operating systems are mainly classified in several categories. These are the following – 1)       Single user and single tasking operating system   2)       Single user and multitasking operating system 3)       Multiuser multitasking Operating System   1) Single user single tasking operating system: This operating system is very popular on personal computers. In this system one user works on a machine at a time. One program can be executed at a time. So this operating system is known as ‘Single user operating system’. If you have a large number of jobs to be executed on such a system, then you have to execute them one after another in sequence. For example: Input and output devices like the printer are very slow as compared to the speed of a CPU. When, you give the printing command a CPU reads a file ...
Read more

What is an operating System

Image
  What is an operating System?             An operating system is an essential component of a computer system. The primary objectives of an operating system are to make computer system suitable to use and utilized computer hardware. An operating system is a program designed to run other programs on a computer. A computer’s operating system is its most important program. It is considered the backbone of a computer, managing both software and hardware resources. Operating systems are responsible for everything from the control and allocation of memory to recognizing input from external devices and transmitting output to computer displays. They also manage files on computer hard drives and control peripherals, like printers and scanners. The operating system of a large computer system has even more work to do. Such operating systems monitor different programs and users, making sure everything runs smoothly, without interference,...
Read more

Functions of Operating System

  Functions of Operating System: There are many functions those are performed by the operating system, but the main goal of operating system is to provide the interface between the user and the hardware means provides the interface for working on the system by the user. The various functions those are performed by the operating system, these are the following:- 1)       Input/ Output device management: In a process program takes an input and then produces an output. It takes the input through input devices and produces output through output devices. Thus, it has to handle input and output devices during program execution. It is very tedious to write instructions to directly handle the input and output devices through the user program. Therefore operating system provides device driver to handle input and output devices. Programmers can user these derivers in their program to control the input/output devices. The interaction of the program wit...
Read more

Layered Systems

Image
  Layered Systems: In the layered system structure, operating system is organized as hierarchy of layers, each of the layers is constructed upon one another. The first system constructed in this way was the THE system built at the Technische Hogeschool Eindhoven in the Netherlands by E. W. Dijkstra and his students. The THE system was a simple batch system for a Dutch computer. Layer 0 assign with allocation of the processor, switching between processes when timers expired.    Above layer 0, the system consisted of sequential processes, each of which could be programmed without having to worry about the fact that multiple processes were running on a single processor. In other words, layer 0 provided the basic multiprogramming of the CPU. Layer 1 was used to the memory management. It distributed space for processes in main memory used for holding parts of processes. Layer 1 was taking care of making sure pages are transport into memory whenever they are needed....
Read more

operating system components

Image
Operating System components : An Operating system is an interface between users and the hardware of a computer system. It is system software that is viewed as an organized collection of software consisting of procedures and functions, providing an environment for the execution of programs. The operating system manages resources of system software and computer hardware resources. It allows computing resources to be used in an efficient way. Programs interact with computer hardware with the help of operating system. These are the important component of operating system as follows:               Process Management: The operating system manages many types of activities ranging from user programs to system programs like printer spoiler, name servers, file server etc. Each of these activities is summarize in a process. The five major activities of an operating system in regard to process management are : Creation and deletion of user and sys...
Read more

Services Provided by Operating System

Image
Services Provided by Operating System: An operating system provides an environment for the execution of user programs. It provides certain services to programs and to the users of those programs. The specific services provided, of course, differ from one operating system to another operating system. These operating system services are provided for the convenience of the programmer, to make the programming task easier and more efficiently. The following diagram is shows various operating system-                                Figure: Operating System Services These are the following services provided by operating system- User Interface : Almost all operating systems have a user interface. This interface can take several forms. One is a command-line interface, which uses text commands and a methods for entering them. Another is a batch interface, in which commands and di...
Read more

Batch Operating System

Image
Batch Operating System : In the early days this system was used. Those days,  the jobs were placed in a job queue and the memory allocate managed the primary memory space, when space was available in the main memory, a job was selected from the job queue and it was loaded into memory. Once the job loaded into primary memory, it competes for the processor. When the processor became available, the processor scheduler selects job that was loaded in the memory and execute it. In batch processing is implemented to provide a batch file processing. So in this approach files of the similar batch are processed to speed up the task. It resulted in improved system utilization and performance of machine,  due to reduced turnaround time of execution job.               In batch processing system, earlier the jobs were scheduled in the order of their arrival that first comes first out(FIFO) / FCFS.  This scheduling method was easy and simple to i...
Read more