Queue system example

This is a small toy example of a queue system. This example illustrates how Data collector monitors can be used for performance analysis of a system. The CPN for the system also includes breakpoint monitors, a write-in-file monitor and a user-defined monitor.

In this system, two kinds of jobs are processed by a server. New jobs arrive periodically in the system. If the server is busy when a job arrives, the job is added to the end of a queue. The queuing strategy for the queue is first-in-first-out (FIFO). If the server is idle when a job arrives, then job passes immediately through the (empty) queue, and the server begins to process the job. When the server finishes processing a job, it becomes idle. If the server is idle and there are jobs waiting in the queue, then the server will immediately begin to process the job at the head of the queue.

This is a CPN of the queue system.

CP-net of a queue system

Several different performance measures can be calculated for this system. This example will show how monitors can be used to calculate different kinds of statistics regarding, e.g., the length of the queue of jobs, the amount of time that jobs spend in the queue, and the percentage of time that the server is busy processing jobs.

This net can be found in <cpntoolsdir>/Samples/QueueSystem/QueueSystem.cpn where <cpntoolsdir> is the directory in which CPN Tools is installed.

The net can also be downloaded from here.

Declarations

The declarations for the net are organized in two declaration blocks. One declaration block, named SYSTEM DECLS, contains the declarations that are used in the net structure. The other block, named MONITOR DECLS, contains declarations that are used either only in monitors or to change options in the performance facilities.

All declarations for the net are shown below. Some of the important declarations are briefly explained.

SYSTEM DECLS

colset UNIT = unit timed;
colset INT = int;
colset Server = with server timed;
colset JobType = with A | B;
colset Job = record jobType : JobType * 
                         AT : INT;
colset Jobs = list Job;
colset ServerxJob = product Server * Job timed;

var proctime : INT;
var job: Job;
var jobs: Jobs;

fun expTime (mean: int) = 
    let
        val realMean = Real.fromInt mean
        val rv = exponential((1.0/realMean))
    in
        floor (rv+0.5)
    end;

fun intTime() = IntInf.toInt (time());

fun newJob() = {jobType = JobType.ran(),
                AT      = intTime()}

In this system there are two types of jobs. The color set JobType is an enumeration color set that defines the two types of jobs: A and B.

The color set Job models a job as a record consisting of two fields. The field named jobType determines the type of the job since it has type JobType. The AT field is of type INT, and it is used to store the arrival time of the job, i.e. the time at which the job arrived in the system.

The color set ServerxJob a product color set that is used to represent the server when it is busy processing a job.

The function expTime is used to generate integer values that are approximately exponentially distributed with a mean value determined by the parameter mean. The function uses the exponential random distribution function.

The function intTime converts the current model time to an integer value. The type of model time values is described on the help page for simulator functions.

The function newJob returns a value from the color set Job. The JobType.ran() is a color set function that returns a random value from the color set JobType, i.e. it will return either A or B when it is invoked. The value of the AT field is set using the intTime function which is used to store the model time at which the job was created.

MONITOR DECLS

globref longdelaytime = 200;

globref fileid = (NONE : TextIO.outstream option);

fun getfid () = 
    (* this will raise Option exception if fileid = NONE *)
    Option.valOf(!fileid)

fun initfile () =
    let
        val filename = OS.Path.concat (Output.getSimOutputDir(), 
                                       "Trans_Log_File.txt")
    in  
        Output.initSimOutputDir();
        fileid := SOME (TextIO.openOut filename)
    end

The reference variable longdelaytime is used to indicate the lower limit for what will be considered long waiting times for jobs in the queue.

The reference variable fileid is used in a user-defined monitor that is described on the help page for Queue System Miscellaneous Monitors. The variable is a reference to a TextIO.outstream option. For more information about TextIO.outstream and option values, see the online help pages for the TextIO structure and the Option structure in the SML Basis Library.

The function getfid will return the file identifier that fileid refers to, assuming that fileid does not refer to the value NONE.

The function initfile initializes a file that a user-defined monitor will update during simulations. The name of the file is Trans_Log_File.txt, and it will be saved in a simulation output directory. The name of the simulation output directory is accessed via the function Output.getSimOutputDir which is one of the output management functions.

Model overview

The System page provides the most abstract representation of the queue system.

System page

The system consists of two modules that are modeled by the two substitution transitions Arrivals and Server. These two modules are described in detail below.

The place Queue models the queue of jobs. The color set of the place is a list color set. There is a single token on the place in the initial marking of the net, and there is be a single token on the place in every reachable marking. The single token on the place represents the queue of jobs. In the initial marking the list is empty, i.e. the queue of jobs is empty in the initial marking. Jobs are added to the queue in the Arrivals module, and jobs are removed from the queue in the Server module.

Job arrivals

The arrival of jobs to the system is modeled on the page Arrivals.

Arrivals page

A token on the place Next is used to determine when new jobs arrive. The color set for the place is a timed color set, and the time stamp of the token on the place will determine when the Arrive transition can occur. There is no token on the place in the initial marking.

The Init transition is the only transition that is enabled in the initial marking. The transition is used to put a token on the place Next. The time inscription @+expTime(100) on the arc from the transition Init to the place Next is used to create a time stamp for the token that is added to the place Next. The expTime function will return a value from the exponential random distribution function. This time stamp is used to ensure that the first job will not always arrive at time 0 for different simulations.

The transition Arrive will occur when the time stamp of the token on the place Next is equal to current model time. When the transition occurs, a new job is created and bound to the variable job via the code segment of the transition. The new job is then added to end of the queue of jobs, as determined by the arc inscription jobs^^[job] on the arc from Arrive to place Queue. The time inscription @+expTime(100) on the arc to place Next is used to determine the time at which the next job will arrive. The inter-arrival times are exponentially distributed with a mean of 100 time units.

Server

The server in the system is modeled by the Server page in the net.

Server page

The places Idle and Busy are used to represent the status of the server. A token on place Idle indicates that the server is not processing a job. There is a single token on the place Idle in the initial marking. A token on place Busy indicates that the server is processing a job, and the value of the token indicates which job is being processed. The initial marking of Busy is empty.

The server can start processing a job (transition Start), if the server is idle and if there is at least one job in the queue of jobs (job::jobs on the arc from place Queue). When the transition Start occurs, the expTime function is called in the code segment, and the value that it returns is bound to the variable proctime which determines the processing time for the job that is removed from the head of the queue. Processing times for jobs are exponentially distributed with a mean processing time of 90 time units.

The Stop transition will become enabled when a server finishes processing a job. The transition will become enabled when the time stamp of a token on place Busy is equal to current model time. When the transition occurs, the job will be added to the place Completed and the server will become idle.

Monitors

Several monitors have been created for the CPN of the queue system. These monitors are described on the help pages mentioned below.

It is assumed that the reader is somewhat familiar with the concepts of Monitors, Data collector monitors, and Monitoring functions. The net contains data collector monitors that calculate untimed and timed statistics which are described on the help page for Calculating statistics.

Queue system queue delay
describes data collector monitors for measuring the amount of time jobs wait in the queue.
Queue system queue length
describes data collector monitors for measuring the length of the queue of jobs.
Queue system server utilization
describes data collector monitors for measuring the percentage of time that the server is busy processing jobs during a simulation.
Queue system miscellaneous monitors
describes additional data collector monitors, breakpoint monitors, a write-in-file monitor, and a user-defined monitor for the queue system.