4.5   Bag of Tasks

• Simple model that provides load balancing
• Given a list of jobs and a set of workers, how to schedule all the jobs?
  

foreach job J 
   J.state <- UNSTARTED
foreach worker W
   W.state <- IDLE
forever do 
   while (E(J:J.state=UNSTARTED) & E(W:W.state=IDLE))
      J.state <- RUNNING
      W.job   <- J
      W.state <- BUSY
   if (!E(W:W.state=BUSY))
      break
   wait for reply from worker (W)
   W.job.state <- FINISHED
   W.state     <- IDLE
      

• Bag of Tasks (BoT) can be modified in many ways
• Adjust size of jobs
  • Smaller workers get smaller jobs
  • Start bigger jobs first
• BoT can also be used when workers must communicate between themselves
  • Have to take this into account when scheduling
  • May need a special constraint system
• Refinements can improve performance greatly but may make the code very convoluted
• Queue manager library or system needed