Scheduling in Batch Systems

• First-Come First Served (FCFS) (See Fig. 9)
  • FCFS, also known as First-In-First-Out (FIFO), is the simplest scheduling policy
  • Arriving jobs are inserted into the tail of the ready queue and the process to be executed next is removed from the head (front) of the queue
  • FCFS performs better for long jobs
  • Relative importance of jobs measured only by arrival time (poor choice)
  • A long CPU-bound job may take the CPU and may force shorter (or I/O-bound) jobs to wait prolonged periods
  • This in turn may lead to a lengthy queue of ready jobs, and thence to the ``convoy effect

  Figure 9: An example to First-Come First Served.

  
• Shortest Job First (SJF)(See Fig. 10)
  • SJF policy selects the job with the shortest (expected) processing time first
  • Shorter jobs are always executed before long jobs
  • One major difficulty with SJF is the need to know or estimate the processing time of each job (can only predict the future!)
  • Also, long running jobs may starve for the CPU when there is a steady supply of short jobs
  • SJF is optimal  minimum average waiting time for given set of processes
  • nonpreemptive  once CPU given to process, can't be preempted until completes CPU burst

  Figure 10: An example to Shortest Job First.