Teaching‎ > ‎CS350 Spring 2009 TF‎ > ‎


posted Feb 6, 2009, 10:55 AM by Site Admin Role   [ updated Feb 6, 2009, 11:14 AM ]
  • Review a system with a queue and one server.
  • Design a discrete event simulator, usage: ./arrival args... | ./service-process.
    • ./arrival prints to standard output when a job arrives and how much time it takes to service the job.
      job:%d arrival:%ld duration:%ld
    • ./service-process parses standard input, simulates the running of the tasks, and prints to standard output:
      job:%d arrival:%ld duration:%ld finish:%ld busy:%ld
      where "finish" is the time the job leaves the system, and "busy" is the cumulative time the server has been working so far.
  • How to compute various metrics:
    • finish: the current time of the server.
    • finish - duration: the service start time when the job is being served.
    • finish - arrival: the response time for a given job.
    • busy / finish: the utilization of the system up until the current time.
  • This simple design does not really track the queue length, but it can be derived as follows: if job j arrives right after job i finishes, then j - i is the queue length.
  • Experimented with various cases:
    • Uniform arrival:
      • ./uniform-arrival 10 100 50 | ./service-process
      • ./uniform-arrival 10 100 200 | ./service-process
      • ./uniform-arrival 100 100 200 | ./service-process
    • Poisson arrival
      • ./poisson-arrival 10 100 50 | ./service-process
      • ./poisson-arrival 10 100 100 | ./service-process (why is utilization not 100%?)
      • ./poisson-arrival 100 100 200 | ./service-process (how many jobs are in the system when the last job arrives? what is the utilization?)
    • Plot q = ρ/(1-ρ), does it affirm our findings?

Code is provided in simulator.tar.gz below, with a Makefile. To unpack and compile:

tar zxf simulator.tar.gz
cd simulator
A uniform arrival process is provided. Also a skeleton of poisson arrival is provided (plug in the code you wrote for Homework #1 problem 5) to simulate M/M/1 queue.
Site Admin Role,
Feb 26, 2009, 4:25 PM