6. Operating Systems Simulations

Some programs inspired from tasks that could be a part of an operating system.

• Pool of tasks

• Client-server

• Producers and consumers

6.1 Pool of Tasks

• A model in which several processes must execute a number of independent tasks with no special needs for synchronization.
• A task is an independent unit of work.
• The tasks are placed in a pool that is shared among several processes (workers).
• For the message-passing models, the pool of tasks is managed by the master.
• For the shared-memory model, the pool may be self-organizing.

Fig. 6.1 Pool of tasks

Method Features

• Easy to use, just define what a task is.
• Scalable, easy to adapt to any number of processes.
• A good example for studying the load balancing, since the tasks can be of variable size. The load balancing is dynamic.
• The specific work assigned to processes is determined at run time.

General Algorithm

for each worker
  while (true) {
    get a task from the pool;
    if (no more tasks)
      break;
    execute task, possibly generating new ones;
  }

The simple model

The master generates one task at a time and assigns it to the first available worker.

The workers wait for a task and execute it while they are not told to stop.

Master() 
{
  do {
    task = Generate_task();
    if (task != done) {
      Recv(worker, any_process);
      Send(task, worker);
    }
  } while (task != done);
  Finish_all();
}

Finish_all() 
{
  for(i=1, i<=nb_workers; i++) { // nb_workers = nb_proc-1
    Recv(worker, any_process);
    Send(done, worker);
  }
}

Worker() 
{
  do {
    Send(proc_id, master);
    Recv(task, master);
    if (task != done)
      Execute_task(task);
  } while (task != done);
} 

Example: Chess

• A computer is playing chess. To choose the next move, it analyzes the outcome of all possible moves.
• Different moves require different amounts of computation. One may result in checkmate or could be evaluated by a heuristic immediately. Others may require projection further into the future.
• When analyzing one move, no information is needed about other moves.
• Technique: the master process distributes data on possible moves to the workers.
• The workers are analyzing the moves as they receive them.
• When a worker is finished analyzing a move, it returns the estimation to the master who assigns it another move to analyze.

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.

Master() 
{
  Queue q;
  while (tasks not finished) {
    choose randomly between    
      Generate_store_task(q);
      Assign_task(q);
  }
  while (!q.is_empty())
    Assign_task(q);
  Finish_all();
}

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

Assign_task(q)
{
  Recv(result, any_process);
  worker = which; // status.MPI_Source
  if (q.is_empty())
    Generate_store_task(q);
  task = q.dequeue();
  Send(task, worker);
}

Worker() 
{
  result = none;
  do {
    Send(result, master);
    Recv(task, master);
    if (task != done)
      result = Execute_task(task);
  } while (task != done);
}

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.

Fig 6.2 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(q); 
      Get_free_worker(task_q, worker_q);
  } while (worker_q.size() != nb_proc-1)

    Get_free_worker(task_q, worker_q);
  Finish_all();
}

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

Get_free_worker(task_q, worker_q) 
{
  Recv(task, any_process);
  worker = which; // status.MPI_Source
  worker_q.enqueue(worker);
  if (To_be_assigned(task))
    task_q.enqueue(task);
}

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