The model illustrated below represents the system architecture
of a time-shared, multiprogrammed, paged, virtual memory computer.
It has been discussed in several papers including:
Numerical Methods in Markov Chain Modelling.
B. Philippe, Y. Saad and W.J. Stewart,
Operations Research, Vol. 40, No. 6, pp. 1156-1179, 1992.
[Postscript copy available]
The system consists of
A queue of requests is associated with each device and the scheduling is taken to be FCFS (First Come First Served). All service times are assumed to be exponentially distributed. When a command is generated, the user at the terminal who generated the command remains inactive until the system responds. Symbolically, a user having generated a command enters the CPU queue. The behavior of the process in the system is characterized by a compute time followed either by a page fault, after which the process enters the SM queue, or an input/output (file request) in which case the process enters the FD queue. Processes which terminate their service at the SM or FD queue return to the CPU queue. Symbolically, completion of a command is represented by the departure of the process from the CPU to the terminals. The degree of multiprogramming at any time is given by eta = n_0 + n_1 + n_2, where n_0, n_1 and n_2 are respectively the number of processes in the CPU, SM and FD queues at that moment.
The following transition rates are used. They are assigned in the subroutine rate in the source code file, ncd.f.
Transition from: To: Transition rate:
CPU SM r = 100.0d0*(eta/128.0d0)^1.5d0
CPU FD r = 0.05d0
CPU Terminals r = 0.002d0
SM CPU r = 0.2d0
FD CPU r = 30.0d0
Terminals CPU r = 0.0001d0*(N - eta)
In the dataset corresponding to this model, ncd_in, the values of N, along with the size of the matrix generated and the number of nonzeros in the matrix, are shown in the table below.
*******************************************
Values of N, n and nz for the 10 datasets:
N n nz
10 286 1,606
20 1,771 11,011
30 5,456 35,216
40 12,341 81,221
50 23,426 156,026
60 39,711 266,631
70 62,196 420,036
80 91,881 623,241
90 129,766 883,246
100 176,851 1,207,051
*******************************************