A second model with a queue of tasks

• Assume that the tasks are generated much faster than they are executed.
• Some of the workers may also generate new tasks that the master has to store before it can send them to other workers.
• The master will have a queue of tasks in which it adds new tasks to be assigned at a later point.
• At every execution of the loop, the master will either generate a new task or assign one to the next available process.

Function generating the next task and storing it in the queue:

Generate_store_task(q) {
  task = Generate_task();
  q.enqueue(task);
}

Function collecting the result from the first process that has a result to report, getting the id of the process from the returned value, and assigning it the next task from the task queue.
Assign_task(q)
{
  worker = Collect(result, any_process);
  if (q.Is_empty())
    Generate_store_task(q);
  task = q.dequeue();
  Assign(task, worker);
}

Function Worker. It loops over reporting the result to the master, gettting a new task from the master, and executing the task, until it receives a task flagged as "none" signifying the end of the operation.

Worker() {
  result = NULL;
  do {
    Report(result, master);
    Get(task, master);
    if (task != none)
      task = Execute_task(task);
  } while (task != none);
}

The complete model

• Assume that we don't know which one takes longer, to generate tasks or to assign them.
• Both the free processes and the tasks to be assigned are stored in queues.
• At every execution of the loop, the master chooses between generating a new task, getting the result from another process, and assigning an already stored task to a free process.

Pool of tasks, complete model

Master() {
  Queue task_q, worker_q;
  while (tasks not finished) {
    choose randomly between
      Generate_store_task(task_q);
      Get_free_worker(task_q, worker_q);
      Assign_task(task_q, worker_q);
  }
  while (!task_q.is_empty()) {
    choose randomly between
      Assign_task(task_q, worker_q); 
      Get_free_worker(task_q, worker_q);
  }
  while (worker_q.size() != nb_proc-1)
    Get_free_worker(task_q, worker_q);
  Finish_all();
}

The function Assign_task gets the next available task form the task queue and the next available worker from the worker queue (if neither of them is empty), and assigns the task to the worker.

Assign_task(task_q, worker_q)
{
  if (!task_q.is_empty() and
      !worker_q.is_empty()) {
    task = task_q.dequeue();
    worker = worker_q.dequeue();
    Assign(task, worker);
  }
}

Function collecting the result from the first process that has one to report, and enqueuing the worker that has reported the result inthe worker queue.

Get_free_worker(task_q, worker_q) 
{
  worker = Collect(result, any_process);
  worker_q.enqueue(worker);
}

Note. The implementation of this model can be a project.