Case Study 2: Simulating a Print Queue

The Problem

An office has a single shared printer. Print jobs arrive at random intervals from multiple workstations. Each job has a different number of pages, and the printer processes one page every 6 seconds. Jobs are printed in the order they arrive — First In, First Out.

We want to simulate this system over one hour (3600 seconds) and answer:

  1. What is the average wait time for a print job?
  2. What is the maximum wait time?
  3. How many jobs complete versus how many are still waiting at the end?

This is a classic discrete event simulation — a technique used in operations research, network engineering, and computer science to model systems where events (job arrivals, job completions) happen at specific points in time.

The Queue in Action

The shared printer is a FIFO queue. When a job arrives, it enters the rear of the queue. The printer always works on the job at the front of the queue. When the front job finishes printing, the next job begins immediately.

This is exactly the behavior of our TQueue from Section 15.5, except now the data stored in each node is not just an integer — it is a structured print job record.

Design

Data Structures

program PrinterSimulation;

uses SysUtils;

type
  PPrintJob = ^TPrintJob;
  TPrintJob = record
    JobID: Integer;
    Pages: Integer;
    ArrivalTime: Integer;    { Second when the job was submitted }
    StartTime: Integer;      { Second when printing began }
    FinishTime: Integer;     { Second when printing completed }
    Next: PPrintJob;
  end;

  TPrintQueue = record
    Front: PPrintJob;
    Rear: PPrintJob;
    Count: Integer;
  end;

Queue Operations

procedure InitQueue(var Q: TPrintQueue);
begin
  Q.Front := nil;
  Q.Rear := nil;
  Q.Count := 0;
end;

function QueueIsEmpty(const Q: TPrintQueue): Boolean;
begin
  QueueIsEmpty := (Q.Front = nil);
end;

procedure Enqueue(var Q: TPrintQueue; Job: TPrintJob);
var
  NewNode: PPrintJob;
begin
  New(NewNode);
  NewNode^ := Job;
  NewNode^.Next := nil;

  if Q.Rear = nil then
  begin
    Q.Front := NewNode;
    Q.Rear := NewNode;
  end
  else
  begin
    Q.Rear^.Next := NewNode;
    Q.Rear := NewNode;
  end;
  Inc(Q.Count);
end;

function Dequeue(var Q: TPrintQueue): TPrintJob;
var
  Temp: PPrintJob;
begin
  if QueueIsEmpty(Q) then
  begin
    WriteLn('Error: Queue underflow');
    Halt(1);
  end;
  Dequeue := Q.Front^;
  Temp := Q.Front;
  Q.Front := Q.Front^.Next;
  if Q.Front = nil then
    Q.Rear := nil;
  Dispose(Temp);
  Dec(Q.Count);
end;

procedure FreeQueue(var Q: TPrintQueue);
var
  Temp: PPrintJob;
begin
  while Q.Front <> nil do
  begin
    Temp := Q.Front;
    Q.Front := Q.Front^.Next;
    Dispose(Temp);
  end;
  Q.Rear := nil;
  Q.Count := 0;
end;

Simulation Parameters

const
  SIM_DURATION = 3600;      { Simulate 1 hour (seconds) }
  SECONDS_PER_PAGE = 6;     { Printer speed }
  JOB_ARRIVAL_PROB = 0.03;  { ~3% chance of a new job each second }
  MIN_PAGES = 1;            { Minimum pages per job }
  MAX_PAGES = 20;           { Maximum pages per job }
  MAX_JOBS = 500;           { Maximum jobs to track for statistics }

The JOB_ARRIVAL_PROB of 0.03 means that, on average, a new job arrives every ~33 seconds, giving us roughly 108 jobs per hour. Each job has between 1 and 20 pages. At 6 seconds per page, a 20-page job takes 2 minutes; a 1-page job takes 6 seconds.

The Simulation Loop

var
  Queue: TPrintQueue;
  CurrentJob: TPrintJob;
  JobCounter: Integer;
  CurrentSecond: Integer;
  RemainingTime: Integer;    { Seconds left on current job }
  PrinterBusy: Boolean;

  { Statistics arrays }
  WaitTimes: array[1..MAX_JOBS] of Integer;
  TotalJobs: Integer;
  CompletedJobs: Integer;

procedure RunSimulation;
var
  NewJob: TPrintJob;
  Pages: Integer;
begin
  InitQueue(Queue);
  JobCounter := 0;
  TotalJobs := 0;
  CompletedJobs := 0;
  PrinterBusy := False;
  RemainingTime := 0;
  Randomize;

  for CurrentSecond := 1 to SIM_DURATION do
  begin
    { --- Event 1: Check for new job arrival --- }
    if Random < JOB_ARRIVAL_PROB then
    begin
      Inc(JobCounter);
      Pages := MIN_PAGES + Random(MAX_PAGES - MIN_PAGES + 1);

      NewJob.JobID := JobCounter;
      NewJob.Pages := Pages;
      NewJob.ArrivalTime := CurrentSecond;
      NewJob.StartTime := 0;
      NewJob.FinishTime := 0;

      Enqueue(Queue, NewJob);
      Inc(TotalJobs);
    end;

    { --- Event 2: Printer processing --- }
    if PrinterBusy then
    begin
      Dec(RemainingTime);
      if RemainingTime = 0 then
      begin
        { Current job finished }
        CurrentJob.FinishTime := CurrentSecond;
        Inc(CompletedJobs);
        if CompletedJobs <= MAX_JOBS then
          WaitTimes[CompletedJobs] :=
            CurrentJob.StartTime - CurrentJob.ArrivalTime;
        PrinterBusy := False;
      end;
    end;

    { --- Event 3: Start next job if printer is free --- }
    if (not PrinterBusy) and (not QueueIsEmpty(Queue)) then
    begin
      CurrentJob := Dequeue(Queue);
      CurrentJob.StartTime := CurrentSecond;
      RemainingTime := CurrentJob.Pages * SECONDS_PER_PAGE;
      PrinterBusy := True;
    end;
  end;
end;

The simulation advances second by second. Each second, three things can happen:

  1. A new job might arrive. We use Random < JOB_ARRIVAL_PROB as a Bernoulli trial — a coin flip with 3% probability.

  2. The printer continues its current job. If the remaining time reaches zero, the job is complete and we record statistics.

  3. If the printer is idle and the queue is not empty, start the next job.

The order of these checks matters. We check arrivals first (so a job that arrives and finds an empty printer still waits one tick), process the current job second, and start a new job third.

Collecting and Reporting Statistics

procedure ReportStatistics;
var
  i: Integer;
  TotalWait, MaxWait: Integer;
  AvgWait: Real;
begin
  WriteLn;
  WriteLn('========================================');
  WriteLn('     PRINTER SIMULATION RESULTS');
  WriteLn('========================================');
  WriteLn('Simulation duration: ', SIM_DURATION, ' seconds (',
          SIM_DURATION div 60, ' minutes)');
  WriteLn('Printer speed: ', SECONDS_PER_PAGE, ' seconds/page');
  WriteLn;
  WriteLn('--- Job Statistics ---');
  WriteLn('Total jobs submitted:  ', TotalJobs);
  WriteLn('Jobs completed:        ', CompletedJobs);
  WriteLn('Jobs still in queue:   ', Queue.Count);
  if PrinterBusy then
    WriteLn('Printer status:        BUSY (', RemainingTime, 's remaining)')
  else
    WriteLn('Printer status:        IDLE');
  WriteLn;

  { Calculate wait time statistics }
  if CompletedJobs > 0 then
  begin
    TotalWait := 0;
    MaxWait := 0;
    for i := 1 to CompletedJobs do
    begin
      TotalWait := TotalWait + WaitTimes[i];
      if WaitTimes[i] > MaxWait then
        MaxWait := WaitTimes[i];
    end;
    AvgWait := TotalWait / CompletedJobs;

    WriteLn('--- Wait Time Statistics ---');
    WriteLn('Average wait time:     ', AvgWait:0:1, ' seconds (',
            AvgWait / 60:0:1, ' minutes)');
    WriteLn('Maximum wait time:     ', MaxWait, ' seconds (',
            MaxWait div 60, ' min ', MaxWait mod 60, ' sec)');
  end;

  WriteLn('========================================');
end;

Running the Simulation

{ Main program }
begin
  WriteLn('Starting printer simulation...');
  WriteLn('Parameters:');
  WriteLn('  Duration:          ', SIM_DURATION div 60, ' minutes');
  WriteLn('  Pages per job:     ', MIN_PAGES, '-', MAX_PAGES);
  WriteLn('  Arrival rate:      ~', Round(JOB_ARRIVAL_PROB * 60),
          ' jobs/minute');
  WriteLn('  Print speed:       ', SECONDS_PER_PAGE, ' sec/page');
  WriteLn;

  RunSimulation;
  ReportStatistics;

  { Clean up }
  FreeQueue(Queue);
end.

Sample Output

Starting printer simulation...
Parameters:
  Duration:          60 minutes
  Pages per job:     1-20
  Arrival rate:      ~2 jobs/minute
  Print speed:       6 sec/page

========================================
     PRINTER SIMULATION RESULTS
========================================
Simulation duration: 3600 seconds (60 minutes)
Printer speed: 6 seconds/page

--- Job Statistics ---
Total jobs submitted:  112
Jobs completed:        97
Jobs still in queue:   14
Printer status:        BUSY (42s remaining)

--- Wait Time Statistics ---
Average wait time:     187.3 seconds (3.1 minutes)
Maximum wait time:     623 seconds (10 min 23 sec)
========================================

Since the simulation uses random numbers, your results will vary. Run it several times to see the range of outcomes.

Experiments

Experiment 1: Change the Arrival Rate

Modify JOB_ARRIVAL_PROB and observe:

Arrival Prob Jobs/Min Avg Wait Max Wait Queue at End
0.01 ~0.6 ~5 sec ~30 sec 0
0.03 ~1.8 ~180 sec ~600 sec ~15
0.05 ~3.0 Queue explodes > 30 min > 80

When the arrival rate exceeds the service rate, the queue grows without bound. This is a fundamental result in queuing theory: if the arrival rate exceeds the service capacity, average wait time approaches infinity.

Experiment 2: Faster Printer

Change SECONDS_PER_PAGE from 6 to 3 (doubling the speed). With the same arrival rate of 0.03, the average wait drops dramatically because the printer can now keep up with incoming jobs.

Experiment 3: Two Printers

Modify the simulation to use two print queues (or one queue feeding two printers). Does this halve the wait time? (Not exactly — it depends on the utilization factor. But it helps significantly.)

Analysis: Why Queues Are the Right Model

This simulation works because the FIFO discipline matches the real-world fairness requirement: no job should be starved while later-arriving jobs get printed. The queue guarantees this.

We could have used an array to simulate the queue — shifting elements left on each dequeue. But that would make each dequeue O(n), and over thousands of seconds with hundreds of jobs, the performance difference would be measurable. Our linked-list queue gives O(1) enqueue and dequeue, making the simulation scale cleanly.

Connection to Queuing Theory

This simulation is a simplified version of an M/M/1 queue — a fundamental model in operations research. "M/M/1" means: - M: Arrivals follow a Markov (memoryless/random) process - M: Service times are also Markov - 1: There is one server (one printer)

Queuing theory gives us closed-form formulas for average wait time, queue length, and utilization. But simulations like this one are invaluable when the assumptions of the mathematical model do not hold — for example, when job sizes are not exponentially distributed, or when the printer has maintenance downtime.

Key Takeaways

  1. The queue data structure directly models FIFO processing systems — printers, ticket counters, network routers, and CPU schedulers all follow this pattern.

  2. Discrete event simulation advances time step by step, checking for events at each tick. It is a powerful technique for understanding system behavior that is too complex for analytical solutions.

  3. When the arrival rate exceeds the service rate, the queue grows without bound and wait times explode. This is the fundamental lesson of queuing theory.

  4. Linked-list queues give O(1) enqueue and dequeue, making them ideal for simulations with many events.

  5. Running experiments — changing parameters and observing outcomes — is how simulation delivers insight. A single run tells you little; many runs reveal patterns.

  6. Memory management matters: the FreeQueue procedure at the end ensures no memory is leaked, even when jobs remain in the queue at simulation end.