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

*********************************************
```