We are suppose to find a monitor for two processes/resources and
expand it to work for many processes/resources.
Write in C Lanuguage a specialised monitor capable of acquring and
releasing a resource in a system with R resources and N processes,
each having a unique priority number, following the rule that the
lowest priority number gets the resource
 
Start by defining 
#define MAXRESOURCES R 
#define MAXPROCESSES N

---

Request for Question Clarification by maniac-ga on 01 Apr 2003 18:28 PST

Hello Teddy78,

Just to be sure, you are looking for a monitor as described in
  http://www.mozilla.org/projects/nspr/reference/html/printro.html#13407

and in similar references where only one process at a time is allowed
into a monitor (by mutual exclusion). Inside the monitor, the code
will review the list of waiting processes / resources and make the
appropriate assignments based on priority.

Since C does not have the appropriate synchronization primitives
directly, would an implementation using pthreads be acceptable [or is
something else needed]?

  --Maniac

---

Clarification of Question by teddy78-ga on 03 Apr 2003 05:10 PST

Hi Maniac!

That's the one I am looking for where the code will review the list of
waiting processes/resources and make the appropriate assignments based
on priority.

But the question strictly needs the solution in C Language whether it
has the appropriate synchronization primitives directly or not.

It does make sense the web page you have suggested. All I need from
you is to suggest me an idea by assuming the solution under any
condition you prefer.
I mean it could be a piece of algorithm in C with appropriate
explanation about its functions to get an overall idea.

Thank you

Hello Teddy78,

Based on your original explanation, I'll assume the following
procedures are available:

 - waitc( condition ) - to specify you want to wait for a condition
(resource is available)
 - signalc( condition ) - to wake a waiting process

I took the names for these from the BACI description at
  http://www.mines.edu/fs_home/tcamp/baci/

I will also assume that these work with two processes / resources
(conditions). We need to write functions:

 - waitr (resource, priority) - to specify you want to wait for a
resource w/ a priority; lower is a higher priority task
 - signalr (resource) - to wake a waiting process

To write these functions, we need to have a priority queue -
essentially a list or array for each resource that indicates the tasks
waiting for a resource. Each priority queue needs to be protected by a
monitor (to ensure insert / removal from the queue is atomic) - that
implies an array of MAXRESOURCES monitors, one for each queue. Since
we have a set of processes (>2), we can also have an array of
MAXPROCESSES monitors, basically to suspend and resume each process.

Initialization becomes
 - create each of MAXRESOURCES monitors, one for each queue
 - create each of MAXPROCESSES monitors, one for each process
 - do a waitc for each process monitor (so a subsequent waitc will
wait)
 - initialize each queue to be empty (e.g., queue index is zero)

The waitr procedure then becomes
  waitc(this_resource_monitor);
  if (!resource) {
    resource = 1;
    signalc(this_resource_monitor);
    return;
    }
  insert the task onto the queue;
  signalc(this_resource_monitor);
  waitc (process_monitor[task #]); // wait here until resource is
available
  return;

The signalr procedure then becomes
  waitc(this_resource_monitor);
  if (queue is empty) {
    resource = 0;
    signalc(this_resource_monitor);
    }
  remove highest priority task from queue;
  signalc(this_resource_monitor);
  signalc(process_monitor[task #]); // will wake up the waiting
process
  return;

The waitc / signalc pair on the resource monitor protects the resource
in use variable (resource) and the queue of waiting tasks. The
resource variable indicates if the resource is in use (non zero means
in use). The task queue can be implemented in a variety of ways; a
simple implementation would be an array of MAXPROCESSES long with two
elements each:
 - task # of the waiting task
 - priority of the waiting task
plus an index indicating the number of entries in use.

You could implement the priority queue with sorted entries - say,
lowest priority process first. The queue removal operation would then
simply remove the last used item of the array (highest priority) and
decrement the index of # of entries. The insert would scan the list
linearly for the appropriate location, move the higher priority (lower
#) entries down the array and insert this task into the array at the
appropriate location. If two processes have the same priority, insert
before the matching priority to ensure FIFO removal of tasks with
equal priority.

I have described the code to this point - do you want an
implementation or is the above description sufficient?

  --Maniac