Explain the Priority CPU scheduling algorithm

A number of scheduling algorithms are available today and all are appropriate for some different kinds of scheduling environments. In this article we give a brief explanation about the ‘priority CPU scheduling algorithm’. 

For those who are not familiar with this scheduling algorithm, a special case of the priority algorithm is the shortest job first scheduling algorithm (SJF). 

- This algorithm involves associating a priority with each and every thread or process. 

- Out of all the processes, the one with the highest priority is chosen and given to the processor for execution. 

- Thus, it is decided by the priority that which process has to be executed first. 

- There are cases when the two or more processes might have the same priority. 

- In such case FCFS (first come first served) scheduling algorithm is applied. 

- The process first in the queue is then executed first. 

- The SJF is essentially a modification of the priority algorithm. 

- Here, the priority of a process (indicated by p) is simply taken as the inverse of the following CPU burst as predicted. 

- This implies if a process is having a large CPU burst, then its priority will be low accordingly and similarly if the CPU burst is small, the priority will be high. 

- Numbers in some fixed range are used for indicating the priorities such as from 0 to 4095 or from 0 to 7 etc. 

- One thing to be noted is that there has been no general agreement up on whether the number 0 indicates lowest priority or highest priority.

- In some systems the lower priorities are indicated by the low numbers while in some systems low numbers mean higher priorities. 

- The latter case i.e., using low numbers for representing high priorities is more common.

For example, consider the 5 processes P1, P2, P3, P4 and P5 having CPU burst as 10, 1, 2, 1, 5 respectively and priority also respectively as 3, 1, 4, 5, 2. Using the priority scheduling algorithms, the processes will be executed in the following order:

P2, P5, P1, P3, P4

There are two ways of defining the priorities i.e., either externally or internally. This gives two types of priorities:

1. Internally defined priorities: These priorities make use of some quantities that can be measured for computing a process’s priority. These quantities include memory requirements, time limits, ration of the I/O burst and CPU burst, number of files and so on.
2. Externally defined priorities: These priorities are defined by some criteria that are external to the operating system. Such factors include political factors, department leading the work; importance of the process, amount of money paid and so on.

The priority scheduling can be itself divided in to two types namely non – preemptive or preemptive. The priority of the process waiting in the ready queue is compared with that of the executing process.

Ø  Preemptive priority scheduling: Here the CPU is preempted if the waiting process has a priority higher than that of the currently executing process.

Ø  Non – preemptive priority scheduling: Here the new process will be let waiting in the ready queue till the execution of the current process is complete.

Starvation or the indefinite blocking presents a major problem in priority scheduling. A process will be considered blocked if it is ready for execution but has to wait for CPU. It is very likely that the low priority processes will be left waiting indefinitely for CPU. In a system that is heavily loaded most of the time, if the number of high priority processes is large, the low priority processes will be prevented from getting processor. 

Explain the Round Robin CPU scheduling algorithm

There are number of CPU scheduling algorithms, all having different properties thus making them appropriate for different conditions. 

- Round robin scheduling algorithm or RR is commonly used in the time sharing systems. 

- This is the most appropriate scheduling algorithm for time sharing operating systems. 

- This algorithm shares many similarities with the FCFS scheduling algorithm but there is an additional feature to it. 

- This feature is preemption in the context switch occurring between two processes. 

- In this algorithm a small unit of time is defined and is termed as the time slice or the time quantum. 

- These time slices or quantum range from 10ms to 100 ms.

- The ready queue in round robin scheduling is implemented in a circular fashion. 

How to implement Round Robin CPU scheduling algorithm

Now we shall see about the implementation of the round robin scheduling:

1. The ready queue is maintained as the FIFO (first in first out) queue of the processes.
2. Addition of new processes is made at the rear end of the ready queue and selection of the process for execution by the processor is made at the front end.
3. The process first in the ready queue is thus picked by the CPU scheduler. A timer is set that will interrupt the processor when the time slice elapses. When this happens the process will be dispatched.
4. In some cases the CPU burst of some processes may be less than the size of the time slice. If this is the case, the process will be voluntarily released by the CPU. The scheduler will then jump to the process next in the ready queue and fetch it for execution.
5. While in other cases the CPU burst for some processes might be higher than the size of the time slice. In this case the timer set will send an interrupt to the processor, thus dispatching the process and putting it at the rear end of the ready queue. The scheduler will then jump to the next process in the queue.

- The waiting time in round robin scheduling algorithm has been observed to be quite long at an average rate. 

- In this algorithm, not more than one time slice can be allocated to any process under any conditions in a row. 

- However, there is an exception to this if there is only one process to be executed.

- If the CPU burst is exceeded by the process, the process is put back at the tail of the queue after preemption.

- Thus, we can call this algorithm as a preemptive algorithm also. 

- The size of the time quantum greatly affects the performance of the round robin algorithm.

- If the size of the time quantum is kept too large then it resembles the FCFS algorithm. 

- On the other hand if the quantum is of too small size, then this RR approach is called the processor sharing approach. 

- An illusion is created in which it seems every process has its own processor that runs at the fraction of the speed of the actual processor. 

- Further, the effect of the context switching up on the performance of the RR scheduling algorithm.

- A certain amount of time is utilized in switching from one process to another. 

- In this time the registers and the memory maps are loaded, a number of lists and tables are updated; memory cache is flushed and reloaded etc.

- Lesser the size of the time quantum, context switching will occur more number of times. 

What is Process State Diagram?

In the systems where multiple processors or multitasking is involved, a process has to go through a number of states. In this article we shall discuss about these states. 

The kernel of the operating system may not recognize these states distinctly but still for the understanding of how the processes are executed they act as useful abstractions. 

These various states can be looked up in a process state diagram for a systematic view. This diagram shows the transitions of the process between various states with arrows. Processes can be stored both in the secondary or virtual memory and in the main memory as per the situation.

Process States

- The primary process states occur in all types of the systems. 

- Processes in these states are usually stored in the main memory. 

Basically there are 5 major states of any process as discussed below:

Ø  Created: 

- It is also known as the ‘new’ state. 

- A process occupies this state up on it creation. 

- While waiting for being admitted to the next ready state this process lies in this state. 

- The admission scheduler will decide whether to admit the process to next state or to delay it on a short or long term. 

- However, this admission is approved in an automatic way in most of the desktop computers. 

- But in the systems with real time operating systems this is not true. 

- Here, the admission might be delayed by a certain amount of time.

- If too many states are admitted to the ready state in a real time operating system, condition of over contention and over saturation might occur disabling the system to meet its deadlines.

Ø  Ready or Waiting: 

- This state is taken up a process when it has been loaded in to the physical memory of the system and is waiting to be executed by the processor or precisely waiting to be context switched by the dispatcher. 

- At any instant of time there might be a number of processes waiting for their execution. 

- Here the processes have to wait in a queue called the run queue out of which only one process will be taken up by a processor. 

- Processes that are waiting for obtaining input from some event are not put in to this ready queue.

Ø  Running: 

- When a process is selected by the CPU for execution, its state is changed to running. 

- One of the processors executes the instructions of the process one by one. 

- Only one process can be run by the process at a time.

Ø Blocked: 

- When a process is blocked because of some event such as I/O operations is put in to the blocked state. 

- Another reason for a process being a blocked state can be its running out of the CPU time allocated to it.

Ø  Terminated: 

- Termination of a process may occur when either its execution is complete or it has been explicitly killed.

- This state is called the terminated or halted. 

- This process is called a zombie process if after coming in the terminated state it is not removed from the main memory. 

There are two additional states for supporting the virtual memory. In these states the process is usually stored in the secondary memory of the system:

Ø Swapped out or Waiting: 

- A process is said to be swapped out when it is removed from the primary memory and placed in the secondary memory. 

- This is done by the mid - term scheduler. 

- After this the state of this process changes to waiting.  

Ø  Swapped out and Blocked:

- In some cases, the processes that were in blocked state might be swapped out. 

- The same process might be again swapped in providing the conditions remain the same.

What is CPU Scheduling Criteria?

Scheduling is an essential concept that serves in the multitasking, multiprocessor and distributed systems. There are several schedulers available for this purpose. But these schedulers also require a criterion up on which they can decide how to schedule the processes. In this article we discuss about these scheduling criteria. Today a number of scheduling algorithms are available and all these have different properties. This is why these may work up on different scheduling criteria. Also the chosen algorithm may favor one class of processes more than the other.

What Criteria is used by algorithms for Scheduling?

Below mentioned are some of the criteria used by these algorithms for scheduling:
1. CPU utilization:
- It is a property of a good system to keep the CPU as busy as possible all the time.
- Thus, this utilization ranges from 0 percent to 100 percent.
- However, in the systems that are loaded lightly, the range is around 40 percent and for the systems heavily loaded it ranges around 90 percent.

2. Throughput:
- The work is said to be done if the CPU is busy with the execution of the processes.
- Throughput is one measure of CPU performance and can be defined as the number of processes being executed completely in a certain unit of time.
- For example, in short transactions throughput might range around like 10 processes per second.
- In longer transactions this may range around only one process being executed in one hour.

3. Turnaround time:
- This is an important criterion from the point of view of a process.
- This tells how much time the processor has taken for execution of  a processor.
- The turnaround time can be defined as the time duration elapsed from the submission of the process till its completion.

4. Waiting time:
- The amount of time taken for the process for its completion is not affected by the CPU scheduling algorithms.
- Rather, these algorithms only affects the time when the process is in waiting state.
- The time for which the process waits is called the waiting time.

5. Response time:
- The turnaround is not a good criterion in all the situations.
- The response time is favorable in the case of the interactive systems.
- It happens many a times that a process is able to produce the output in a fairly short time compared to the expected time.
- This process then can continue with the next instructions.
- The time taken for a process from its submission till production of the first response is calculated as the response time and is another criterion for the CPU scheduling algorithms.

All these are the primary performance criteria out of which one or more can be selected by a typical CPU scheduler. These criteria might be ranked by the scheduler depending up on their importance. One common problem in the selection of performance criteria is the possibility of conflict ion between them.
For example, increasing the number of active processes will increase the CPU utilization but at the same time will decrease the response time. This is often desirable to produce reduction in waiting time and turnaround time also. In a number of cases the average measure is optimized. But there are certain cases also where it is more beneficial to optimize the maximum or the minimum values.
It is not necessary that a scheduling algorithm that maximizes the throughput will decrease the turnaround time. Out of a mix of short and long jobs, if a scheduler runs only the short jobs, it will produce the best throughput. But at the same time the turnaround time for the long jobs will be so high which is not desirable.

What is meant by Deadlock? List the necessary conditions for arising deadlocks?

Consider two competing processes or actions in a situation where both of them wait for each other to be done and so neither of them ever finish. Such a situation is called a deadlock. 

- When the number of competing processes is exactly two, then it is said to be a ‘deadly embrace’. 

- The two involved competing actions tend to move towards some sort of tragedy which might be mutual extinction or mutual death. 

"In operating systems a situation occurs where two threads or processes enter the waiting state at the same time because of the resource that they both want is being used by some other process that also in waiting state for some resource being held by another process in waiting state and so on". 

- It so happens that the process is then unable to change its state since the resources it requires are being used by the other processes which is then keeping the process in waiting state indefinitely. 

- The system is now in a deadlock. 

- Systems such as the distributed systems, parallel computing systems, multi-processing systems face the problem of being in a deadlock quite often. 

- This is so because here the hardware and software locks are purposed for handling the resources that are shared and implementing the process synchronization. 

- Deadlocks may also occur in telecommunication systems because of the corrupt signals and their loss rather than resource contention. 

- A deadlock situation can be compared to problems such as that of the catch-22 or chicken or egg problem. 

- A deadlock can also occur in a circular chain pattern. 

- For example, consider a computer having 3 processes and corresponding 3 CD drives i.e., one held by each process. 

- Now all the three processes would be in a deadlock if they all request another drive.

Conditions for a Deadlock to arise

There are certain conditions that should be there for a deadlock to arise:

1. Mutual exclusion: There has to be at least one resource that cannot be shared. So that only one process would use at any given time.
2. Resource holding (or hold and wait): There should be at least one resource held by a process that in turn should be request more resources that are being held by other processes.
3. No preemption: Once the resources have been allocated, they should not de-allocated by the operating system. The condition is that the process holding the resource must release it voluntarily.
4. Circular wait: A circular chain of processes must be formed as explained in the earlier example.

"These 4 conditions for deadlock are collectively called the ‘Coffman conditions’. If any of these conditions is not met, a deadlock can’t occur".

- Handling a deadlock is an important capability of the operating systems. 

- However, there are many modern operating systems that still cannot avoid deadlocks. 

- On occurrence of a deadlock many non-standard approaches are followed by different operating systems for handling it. 

- Many of these approaches try to avoid at least one of the Coffman conditions (generally the 4^th one). 

- Below we discuss some of the approaches:

1. Ignoring deadlock
2. Detection
3. Prevention
4. Avoidance

- There is a second kind of deadlocks called the ‘distributed deadlock’ and it is common where concurrency control is used or we can say in the distributed systems.