# MARCA_Models:

MUTEX --- A Resource Sharing Model

# William J. Stewart

## A Model of Resource Sharing

This model has been discussed in:

* Efficient Descriptor-Vector Multiplication
in Stochastic Automata Networks. *
P. Fernandes, B. Plateau and W.J. Stewart,
Submitted for publication.
[Postscript copy available]

In this model, * N *
distinguishable processes share a certain resource.
Each of these processes alternates between a * sleeping *
state and a resource * using * state.
However, the number of processes that may concurrently use the resource
is limited to * R * where * 1 <= R <= N *
so that when a process
wishing to move from the sleeping state to the resource using state
finds * R * processes already using the resource, that process fails to
access the resource and returns to the sleeping state.
Notice that when * R = 1 * this model reduces
to the usual mutual exclusion problem.
When * R = N * all of the the processes are independent.
We let * lambda_i * denote the rate at which process
* i * awakes from the
sleeping state wishing to access the resource, and
* mu_i, * the rate at which this same process releases the resource
when it has possession of it.

The transition rates,
which are assigned in the subroutine * rate *
of the source code file * mutex.f,* are taken as:

lambda_i = 1/i mu_i = i

In the data set corresponding to this model,
* mutex_in, * the
values of * N * and * R *
are as shown in the table below, along with the size of the
matrix generated and the number of nonzeros in the matrix.

*********************************************
Values of N, R, n and nz for the 15 datasets:
N R n nz
12 1 13 37
12 4 794 6,362
12 8 3,797 47,381
12 11 4,095 53,223
16 1 17 49
16 4 2,517 20,949
16 8 39,203 563,491
16 12 64,839 1,094,983
16 15 65,535 1,114,079
20 1 21 61
20 4 6,196 52,596
20 8 263,950 4,031,310
20 12 910,596 18,114,756
20 16 1,047,225 21,972,345
20 19 1,048,575 22,020,055
*********************************************