Scheduling in Batch Systems

• First-Come First Served (FCFS) (See Fig. 2.22)
  • 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 2.22: An example to First-Come First Served.

  
• Shortest Job First (SJF)(See Fig. 2.23)
  • 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 2.23: An example to Shortest Job First.

  

• Shortest Remaining Time Next (SRTF)
  • preemptive version of the SJF
  • if new process arrives with CPU burst length remaining time of current executing process, preempt: Shortest-Remaining-Time-First

Figure 2.24: Example of non-preemptive SJF and example of preemptive SJF.