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

Multitasking System

  Multitasking system ·           Technically , multitasking is same as multi programming ·           In a multitasking operating system, s single user can execute multiple programs at the same time ·           We can also say, multitasking is the system capability to work on more than one job or process at the same time. ·           It means that whenever a job needs to perform I/O operation, the cpu can be used for execting some other job                                                        diagram of multi tasking     ·           There are two type of multitasking : 1.       ...
Post a Comment
Read more

Monolithic Architecture

  Monolithic Architecture Monolith means composed all in one piece. The  Monolithic  application describes a single-tiered  software  application in which different components combined into a single program from a single platform. Components can be: Authorization — responsible for authorizing a user Presentation — responsible for handling HTTP requests and responding with either HTML or JSON/XML (for web services APIs). Business logic — the application’s business logic. Database layer — data access objects responsible for accessing the database. Application integration — integration with other services (e.g. via messaging or REST API). Or integration with any other Data sources. Notification module — responsible for sending email notifications whenever needed. Example for Monolithic Approach Consider an example of Ecommerce application, that authorizes customer, takes an order, check products inventory, authorize payment and ships ordered products. This applicat...
Post a Comment
Read more

Change the priority of a process

  Change the priority of a process You can tell the computer that certain processes should have a higher priority than others, and so should be given a bigger share of the available computing time. This can make them run faster, but only in certain cases. You can also give a process a  lower  priority if you think it is taking up too much processing power. Go to the  Processes  tab and click on the process you want to have a different priority. Right-click the process, and use the  Change Priority  menu to assign the process a higher or lower priority. There is typically little need to change process priorities manually. The computer will usually do a good job of managing them itself. (The system for managing the priority of processes is called  nice .) Does higher priority make a process run faster? The computer shares its processing time between all of the running processes. This is normally shared intelligently, so programs that are doing more ...
Post a Comment
Read more

Batch Processing Operating System

  Batch processing system ·           Batch processing is one of the oldest method    of running the programs ·           The computer in the past were very large in size and their I/O devices were very different from those that are used today. The job processing was not interactive as it is today. ·           The user did not interact directly with computer system.   ·           The process scheduling , memory management, file management and I/Omanagement functions are quite simple in batch processing system   1.         Process scheduling (i.e. allocation strategy for a processor is typically in order of their arrival i.e. first come first served(FCFS)basis.   2.         Memory management  is done by divi...
Post a Comment
Read more
 C omparison between real time and time sharing operating system P rotection and s ecurity  • Protection refers to a mechanism for controlling the access of program s processes, or users to the resources defined by computer system. • The concept of protection came with the advent of multiprogramming where several processes compete for the use of CPU. • the purpose was to confine each users program to its assigned areaof memory so that the programs cannot interface and harm each other. • Protection in main memory is particularly important because of address translation. The purpose of protection is to allow concurrently running process to share the common physical address space. • Protection also ensure that only process that have gained proper authorization from the operating system can operate on memory segment , the CPU, files and other resources.
Post a Comment
Read more