NCD --- An Interactive Computer System Model

William J. Stewart

Billy's Home Page,   MARCA-Models Home Page

An NCD Queueing Network of the Central Server Type

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               Terminals        r = 0.2d0
             FD               Terminals        r = 1.0d0/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

Billy's Home Page,   MARCA-Models Home Page