MARCA_Models:
MUTEX --- A Resource Sharing Model

William J. Stewart

Billy's Home Page,   MARCA-Models Home Page


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
    
   *********************************************

Billy's Home Page,   MARCA-Models Home Page