Scheduling algorithms: O.S

Scheduling algorithms:

 Process Queues:The Operating system manages various types of queues for each of the process states. The PCB related to the process is also stored in the queue of the same state Process scheduling is an essential part of a Multiprogramming operating systems.


Times related to the Process
1. Arrival Time
The time at which the process enters into the ready queue is called the arrival time.

2. Burst Time
The total amount of time required by the CPU to execute the whole process is called the Burst Time.

3. Completion Time
The Time at which the process enters into the completion state or the time at which the process completes its execution, is called completion time.

4. Turnaround time The total amount of time spent by the process from its arrival to its completion, is called Turnaround time.

 5. Waiting Time The Total amount of time for which the process waits for the CPU to be assigned is called waiting time.

 6. Response Time The difference between the arrival time and the time at which the process first gets the CPU is called Response Time.

CT-AT=WT+BT
TAT=CT-AT
Waiting time=TAT-BT

 TAT=Turn Around TIME
BT=Burst Time or Service Time
AT=Arrival Time
CT=Completion Time
In Multiprogramming, if the long term scheduler picks more I/O bound processes then most of the time, the CPU remains idol. The task of Operating system is to optimize the utilization of resources.


The Purpose of a Scheduling algorithm

 Maximum CPU utilization
Fare allocation of CPU
Maximum throughput
Minimum turnaround time
Minimum waiting time
Minimum response time

Scheduling algorithms FCFS Scheduling (non preemptive) First come first serve (FCFS) scheduling algorithm simply schedules the jobs according to their arrival time. The job which comes first in the ready queue will get the CPU first.
Advantages of FCFS Simple Easy First come, First serv Disadvantages of FCFS The scheduling method is non preemptive, the process will run to the completion. convoy effect or starvation. If the CPU gets the processes of the higher burst time at the front end of the ready queue then the processes of lower burst time may get blocked which means they may never get the CPU if the job in the execution has a very high burst time. This is called convoy effect or starvation.


Shortest Job First (SJF) Scheduling (non preemptive) SJF scheduling algorithm, schedules the processes according to their burst time. In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next. Advantages of SJF Maximum throughput Minimum average waiting and turnaround time Disadvantages of SJF: It is also a non preemptive. May suffer with the problem of starvation It is not implementable because the exact Burst time for a process can't be known in advance.


Shortest Remaining Time First (SRTF) Scheduling Algorithm (preemptive) This Algorithm is the preemptive version of SJF scheduling. Once all the processes are available in the ready queue, No preemption will be done and the algorithm will work as SJF scheduling. The context of the process is saved in the Process Control Block when the process is removed from the execution and the next process is scheduled

 Since, at time 0, the only available process is P1 with CPU burst time 8. This is the only available process in the list therefore it is scheduled. 2. The next process arrives at time unit 1. Since the algorithm we are using is SRTF which is a preemptive one, the current execution is stopped and the scheduler checks for the process with the least burst time. Till now, there are two processes available in the ready queue.

The OS has executed P1 for one unit of time till now; the remaining burst time of P1 is 7 units. The burst time of Process P2 is 4 units. Hence Process P2 is scheduled on the CPU according to the algorithm. 3. The next process P3 arrives at time unit 2. At this time, the execution of process P3 is stopped and the process with the least remaining burst time is searched. Since the process P3 has 2 unit of burst time hence it will be given priority over others. 4.

The Next Process P4 arrives at time unit 3. At this arrival, the scheduler will stop the execution of P4 and check which process is having least burst time among the available processes (P1, P2, P3 and P4). P1 and P2 are having the remaining burst time 7 units and 3 units respectively. P3 and P4 are having the remaining burst time 1 unit each. Since, both are equal hence the scheduling will be done according to their arrival time. P3 arrives earlier than P4 and therefore it will be scheduled again. 5.


The Next Process P5 arrives at time unit 4. Till this time, the Process P3 has completed its execution and it is no more in the list. The scheduler will compare the remaining burst time of all the available processes. Since the burst time of process P4 is 1 which is least among all hence this will be scheduled. 6. The Next Process P6 arrives at time unit 5, till this time, the Process P4 has completed its execution. We have 4 available processes till now, that are P1 (7), P2 (3), P5 (3) and P6 (2). The Burst time of P6 is the least among all hence P6 is scheduled. Since, now, all the processes are available hence the algorithm will now work same as SJF. P6 will be executed till its completion and then the process with the least remaining time will be scheduled.


 Round Robin Scheduling Algorithm (preemptive ) Round Robin scheduling algorithm is one of the most popular scheduling algorithm which can actually be implemented in most of the operating systems. This is the preemptive version of first come first serve scheduling. The Algorithm focuses on Time Sharing. In this algorithm, every process gets executed in a cyclic way. A certain time slice is defined in the system which is called time quantum.


Each process present in the ready queue is assigned the CPU for that time quantum, if the execution of the process is completed during that time then the process will terminate else the process will go back to the ready queue and waits for the next turn to complete the execution. Example: Initially, at time 0, process P1 arrives which will be scheduled for the time slice 2 units. Avg Waiting Time =



Highest Response Ratio Next (HRRN) Scheduling (non-preemptive) Highest Response Ratio Next (HRNN) is one of the most optimal scheduling algorithms. This is a non-preemptive algorithm in which, the scheduling is done on the basis of an extra parameter called Response Ratio. Response Ratio is calculated by the given formula. Response Ratio = (W+S)/S
Where, W → Waiting Time S → Service Time or Burst Time
If we look at the formula, we will notice that the job with the shorter burst time will be given priority but it is also including an extra factor called waiting time.

 Example: P0 is executed for 3 units, meanwhile, only one process P1 arrives at time 3. This will get scheduled immediately since the OS doesn't have a choice. P1 is executed for 5 units. Meanwhile, all the processes get available. We have to calculate the Response Ratio for all the remaining jobs.


Response Ratio = (W+S)/S RR (P2) = ((8-4) +4)/4 = 2 RR (P3) = ((8-6)+1)/1 = 3 RR (P4) = ((8-8)+2)/2 = 1





Priority Scheduling In the Non Preemptive Priority scheduling, The Processes are scheduled according to the priority number assigned to them.


Multilevel-Queue and Multilevel Feedback Queue Scheduling In a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system. Processes do not move between queues. Multilevel feedback queue scheduling, however, allows a process to move between queues.
Multilevel Feedback Queue Scheduling multilevel feedback queue scheduler is defined by the following parameters: The number of queues. The scheduling algorithm for each queue. The method used to determine when to upgrade a process to a higher-priority queue. The method used to determine when to demote a process to a lower-priority queue. The method used to determine which queue a process will enter when that process needs service.

Comments

Post a Comment

Popular posts from this blog

Multitasking,Multi programming & Multiprocessing

Home Multitasking (Time sharing) Multitasking has the same meaning of multiprogramming but in a more general sense, as it refers to having multiple (programs, processes, tasks, threads) running at the same time.  This term is used in modern operating systems when multiple tasks share a common processing resource (e.g., CPU and Memory). Multitasking:As the name itself suggests, multi tasking refers to execution of multiple tasks (say processes, programs, threads etc.) at a time.  Ex: In the modern operating systems, we are able to play MP3 music, edit documents in Microsoft Word, surf the Google Chrome all simultaneously, this is accomplished by means of multi tasking. Multitasking is a logical extension of multi programming. Multi programming  In a modern computing system, there are usually several concurrent application processes which want to execute.  Now it is the responsibility of the Operating System to manage all the processes effe
Read more

(PCB) or Task Control Block (TCB)

Home (PCB)   or   Task   Control   Block   (TCB) •   As   the   operating   system   supports   multi-programmin g ,   it   needs   to keep track of all the processes •   T he   process   control   block   (PCB)   is   used   to   track   the   proces s ’s execution status. •   Each   block   of   memory   contains   information   about   the   process   state,   program   counter,   stack   pointe r ,   status   of   opened   files, scheduling algorithms, etc. •   All   these   information   is   required   and   must   be   saved   when   the  process   is   switched   from one state to anothe r . •   The   process   table   is   an   array   of   PCB’s,   that   means   logically contains a PCB for all of the current processes in the system. (PCB) •   P rocess   table   is   an   array   or   linked   list •   The process table is an  a rray of PCB’s, that means logically contains a PCB for all of the current proce
Read more

Buffering, Polling & Spooling

Home Buffering Kernels provide many services related to I/O.  Several services—scheduling, buffering, caching, spooling, device reservation, and error handling—are provided by the kernel’s I/O subsystem and build on the hardware and device-driver infrastructure. A buffer, of course, is a memory area that stores data being transferred between two devices or between a device and an application. Caching: A cache is a region of fast memory that holds copies of data or cache is a temporary storage area where frequently accessed data can be stored for rapid access.  What does Buffer mean? A buffer is a temporary holding area for data while it's waiting to be transferred to another location. It is usually located in the RAM. The concept of the buffer has developed in order to prevent data congestion from an incoming to an outgoing port of transfer.  Computers have many different devices that all operate at varying speeds, and a buffer is needed to act as a sort of te
Read more