Skip to main content

Scheduling Algorithms

    Scheduling Algorithms

CPU scheduling algorithm deal with the problem of deciding which of the processes in the ready queue is to be allocated the CPU . six commonly used scheduling algorithms are:

1. first-come First-served(FCFS)

2. Shortest job First(SJF)

3. Priority scheduling

4. Round-Robin Scheduling(RR)

5. Multi-Level Queue Scheduling(MLQ)

6. Multi-Level Feedback Queue Scheduling (MFQ)

     

First-Come First-Served Scheduling (FCFS)

·      It is simplest and the most straight forward of all scheduling algorithms.

·      In this scheduling, the process that request the CPU first is allocated CPU first. Thus  the name first come first served.

·      We can say that in FCFS scheduling, a process is allocated CPU time according to the arrival time of a process.

·      The implementation of FCFS policy is easily manged with a FIFO queue

·      When a process enters the ready queue, its PCB is linked onto tail of the queue.

·      When CPU is free, it is allocated to the head of ready queue.the running process is then removed from the queue.

·      FCFS scheduling algorithm is non-preemptive. Once the CPU is allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O

 

1.     FCFS tends to favour CPU-bound processes. Consider . in system with one CPU bound process  and a number of I/O bound processes. In such as system, the following scenario may arise:

·      The CPU bound process will get the CPU and holds it.

·      During this all the other processes will finish their I/O and move  into the ready queue, waitin for CPU. When these processes are waiting in ready queue, the I/O devices are idle.

·      After some time, the CPU-bound process finishes its CPU burst (CPU burst time indicates for how much time . the process needs the CPU)and moves to an I/o devices . at this time all the I/O bound processes.

·      The CPU-bound process will then move back to ready queue and be allocated the CPU. Again all the I/O processes end up waiting in the ready queue until the CPU-bound process is done.


  • Advantages –
    1. It is simple and easy to understand.
  • Disadvantages –
    1. The process with less execution time suffer i.e. waiting time is often quite long.
    2. Favors CPU Bound process then I/O bound process.
    3. Here, first process will get the CPU first, other processes can get CPU only after the current process has finished it’s execution. Now, suppose the first process has large burst time, and other processes have less burst time, then the processes will have to wait more unnecessarily, this will result in more average waiting time, i.e., Convey effect.
    4. This effect results in lower CPU and device utilization.
    5. FCFS algorithm is particularly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals.

  • Example of FCFS scheduling

    A real-life example of the FCFS method is buying a movie ticket on the ticket counter. In this scheduling algorithm, a person is served according to the queue manner. The person who arrives first in the queue first buys the ticket and then the next one. This will continue until the last person in the queue purchases the ticket. Using this algorithm, the CPU process works in a similar manner.

  • How FCFS Works? Calculating Average Waiting Time

    Here is an example of five processes arriving at different times. Each process has a different burst time.

    ProcessBurst timeArrival time
    P162
    P235
    P381
    P430
    P544

    Using the FCFS scheduling algorithm, these processes are handled as follows.

    Step 0) The process begins with P4 which has arrival time 0

    Step 1) At time=1, P3 arrives. P4 is still executing. Hence, P3 is kept in a queue.

    ProcessBurst timeArrival time
    P162
    P235
    P381
    P430
    P544

    Step 2) At time= 2, P1 arrives which is kept in the queue.

    ProcessBurst timeArrival time
    P162
    P235
    P381
    P430
    P544

    Step 3) At time=3, P4 process completes its execution.

    Step 4) At time=4, P3, which is first in the queue, starts execution.

    ProcessBurst timeArrival time
    P162
    P235
    P381
    P430
    P544

    Step 5) At time =5, P2 arrives, and it is kept in a queue.

    ProcessBurst timeArrival time
    P162
    P235
    P381
    P430
    P544

    Step 6) At time 11, P3 completes its execution.

    Step 7) At time=11, P1 starts execution. It has a burst time of 6. It completes execution at time interval 17

    Step 8) At time=17, P5 starts execution. It has a burst time of 4. It completes execution at time=21

    Step 9) At time=21, P2 starts execution. It has a burst time of 2. It completes execution at time interval 23

    Step 10) Let's calculate the average waiting time for above example.

    Waiting time = Start time - Arrival time

    P4 = 0-0 = 0

    P3 = 3-1 = 2

    PI = 11-2 = 9

    P5= 17-4 = 13

    P2= 21-5= 16

    Average Waiting Time

    = 40/5= 8

 

 

Comments

Post a Comment

Popular posts from this blog

Multilevel Feedback queue scheduling (MFQ)

  Multilevel Feedback queue scheduling (MFQ) ·          Multilevel feedback queue scheduling is an enhancement of multi-levelqueue scheduling. In this scheme, processes can move between the different queue ·          The various processes are separates in different queue on the basis of their CPU Burst Char characteristics ·          If a process consumes a lot of CPU time , it is placed into a lower priority queue. Thus I/O bound and interactive process are placed in the higher priority queue and CPU bound pricesses are in lower priority ·          If a processes waits too long in a lower priority queue it is moved higher priority queue. Such an aging prevents starvation. ·          The top priority queue is given smallest CPU time Quantum ·      ...
Post a Comment
Read more

ENTERPROCESS COMMUNICATION AND SYNCHRONIZATION

      ENTERPROCESS COMMUNICATION AND SYNCHRONIZATION ·          In multi programming environment multiple process co-exit . a single   program may be broken into number of processes. ·          The process are classified into two categories : independent processes and cooperating processes. ·          An independent process is a standalone process that does not share any data with any other process. It cannot affect or be affected by the other processes executing   in the system. In other words, the modification made to an independent process does not affect the functioning of other process. ·          A cooperating processes is a process that shares data with other processes in a system it can affect or be affectedly the other processes executing in the system ·      ...
Post a Comment
Read more

Round Robin

   Round Robin ·          Round robin Scheduling is similar to FCFS but preemption is addede to switch between processes. ·          In RR scheduling, processes are dispatched in FIFO but given a small amount of CPU time. This small amount of CPU time this small amount of time is known as time quantum or time slice. A time quantum is generally from 10 to 100 milliseconds ·          If a process does not complete before its time slice expires, the CPU is time slice and is given to the next waiting process in ready queue. ·          The preempted process in then places at the   tail of the ready queue. ·          If a process is completed before its time slice expires, the process itself release the CPU. The scheduler then proceeds to the next process in ready queue. ...
Post a Comment
Read more

Multi Level Queue Scheduling (MLQ)

  Multi Level Queue Scheduling (MLQ) ·          Multilevel queue scheduling classifies the processes according to their types for example, a multilevel queue scheduling algorithm makes a common. ·          In this scheduling ready queue is divided into various queue that are called sub queues. A subqueue is a distinct operational queue ·          The process are permanently assigned to subqueues, generally based on some property of the process such as memory size,priority or process type ·          Each subqueue has its process sucheduling algorithm. For example interactive process at the foreground may use round robin scheduling while batch jobs at the background may use the FCFS method ·          For example, consider a system with four different queues 1.   ...
Post a Comment
Read more

Direct Communicationand Indirect communication

  Direct Communication ·          Direct communication establishes a link between two processes. A communication link is a unidirectional path along which information flows. ·          two processes use single communication link to share information. ·          In this   metod, there cannot be more that one link between two processes                                                     direct communication ·          Send and receive function used in direct communication are given below : ·          Send(process name , message ,(receive(process name , message)             Send(A, message...
Post a Comment
Read more