*** An Efficient Scheduling Algorithm for Seuss Programs v1.5 ***


We would like to devise a static distributed scheduling algorithm for
programs written in the Seuss programming language [Information about
the Seuss progamming language can be found in the "Seuss Language
Reference" by Rajeev Joshi].  The algorithm must schedule Seuss
"actions" in a non-preemptive manner such that fairness is guaranteed
and overhead is kept to a minimum.  The algorithm initially used by
the Seuss scheduler was a simple token-based static algorithm with a
limited ability to exploit concurrency.  The algorithm presented in
this document is slightly more complicated but does a much better job
at exploiting concurrency.  The new algorithm is also a token-based
static algorithm and is a variation of the tree-locking protocol by
Silberschatz and Kedem [A. Selberschatz and Z. Kedem, "Consistency in
Hierarchical Database Systems," Journal of the ACM, Volume 27, Number
1 (January 1980), pages 72-80].

We first assign a unique ID to every action in the system.  For a system
consisting of n actions, each action will be assigned an ID in the
range 0 to n-1.  Let A[i] denote the action whose ID is i.  The set of
all actions with which action A[i] is incompatible will be known as
the "incompatibility set of i."

An action shares a token with each action with which it is
incompatible.  An action that holds all its shared tokens executes.
Let us also assign a unique ID to every token.  Let t[x] denote the
token with token ID x.  Initially, the action with the smaller ID
holds the shared token.  Hence if actions A[i] and A[j] share a token
t[x] and i < j, then A[i] gets to hold t[x] initially.


[English Description of Algorithm]

When an action is not executing, it makes token requests for its
shared tokens from the actions holding on to those tokens.  The
requests are made in increasing order of the IDs of the tokens.  An
action can have at most one outstanding request.

When an action A[i] receives a request from an action A[j] for a token
t[x], one of two things happen:  1) If A[i] is currently executing,
then A[i] notes the request.  2) If A[i] is not currently executing,
then A[i] would check if it has acquired all of its shared tokens with
IDs less than x.  If all those shared tokens have been acquired, then
A[i] notes the request.  Otherwise, A[i] sends t[x] to A[j].

After an action executes, it sends each of its requested shared tokens
to the requester.  The action piggybacks a token request onto the
smallest token that it gives away.


[Pseudo-code Description of Algorithm]

Each processor has the following data structures.

markedForExecution[i]; /* array of booleans; each boolean indicates
whether action i has been marked for execution */

rcvdRequest[i]; /* array of sets; each set contains the IDs of the
tokens requested from action i */

sentRequest[i]; /* array of integers; each integer corresponds to
the ID of the token that action i has most recently requested */

Algorithm for processor x:

for (each action i managed by processor x)
{
	let B be the box (thread) containing i;

	/* Action i has recently finished executing */
	if (markedForExecution[i]
		AND B is not executing i)
	{
		markedForExecution[i] := false;
		send out the tokens in rcvdRequest[i], and piggyback
			a token request with the smallest token
			being sent out;
		rcvdRequest[i] := {};
	}

	/* Action i is ready to execute */
	if (i is holding all of its shared tokens
		AND !markedForExecution[i])
	{
		markedForExecution[i] := true;
		tell B to execute i;
	}

	/* Action i is not executing */
	if (!markedForExecution[i])
	{
		let N denote i's set of shared tokens;
		let H denote the set of shared tokens that are
			being held by i;
		let s denote the smallest token ID of all the tokens
			in N-H;

		if (N = H OR H = {}) /* has all shared tokens or no tokens */
		{
			skip;
		}
		else
		{
			if (sentRequest[i] == s) /* already requested */
			{
				skip;
			}
			else
			{
				sentRequest[i] := s;
				request token s from the action holding s;
			}
		}
	}

	/* Received a request for i's token x */
	if (received a request for i's token x)
	{
		if(!markedForExecution[i]
			AND an action is holding one of i's shared tokens
				whose token ID is less than x)

		{
			send x to the action sharing x;
		}
		else
		{
			add x to the rcvdRequest[i] set;
		}
	}

	/* Received i's token x from j */
	if (received i's token x from j)
	{
		if (a request has been piggybacked with token x)
		{
			add x to the rcvdRequest[i] set;
		}

		sentRequest[i] := -1;
		save token;
	}
}


[Proof of Fairness]

Lemma:  Each starving action must have made exactly one indefinitely
outstanding token request to some other action.

Proof of Lemma:  By the algorithm, we see that an action that has all
of its shared tokens would execute.  Hence a starving action does not
have all of its shared tokens.  In a single iteration of the
algorithm, a token request would be made for every action needing a
token on the condition that the request hasn't been made just before.
So if an action does not have all of its shared tokens, a request
would be made in a finite amount of time.  Therefore, if an action
does not have an indefinitely outstanding token request, it will
execute (not starve).  The contra-positive of this statement is also
true, and hence the lemma is proven.

Suppose that in a system of n actions, there exists a non-empty set S
of actions that are starving.  By our lemma, we know that each
starving action must have made exactly one indefinitely outstanding
token request to some other action.  Let A[i] be the action in S whose
requested token has the greatest token ID.  Let T denote the set of
actions in the system to which the actions in S made indefinitely
outstanding requests.  Let A[j] be the action in T that received the
indefinitely outstanding request from A[i].  By the definition of
shared tokens, i != j.  Let us denote the token shared between A[i]
and A[j] as t[x].  Note that since A[j] did not give t[x] to A[i],
A[j] must have all of its shared tokens whose IDs are less than x.

We now wish to show that A[i] will eventually receive t[x] from A[j].
If we assume that A[j] is not starving, then A[j] will execute and
terminate (by the definition of a Seuss action) and relinquish t[x] to
A[i].  So let us assume that A[j] is starving.  Let A[k] be an action
to which A[j] has made an indefinitely outstanding request.  Let t[y]
be the token shared between A[j] and A[k].  By the algorithm, we know
that y must be greater than x.  This is a contradiction because of the
criteria with which we chose A[i] and the fact that i != j.  This
implies that A[j]'s request to A[k] was not indefinitely outstanding.
Hence A[j] is not starving.  A[j] will execute and send its token to
A[i].  Therefore, A[i]'s token request was not indefinitely
outstanding and we have thus shown that A[i] was not starving.  This
contradiction proves that the algorithm is fair.