2009-02-06

Post date: Feb 6, 2009 6:55:15 PM

    • 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

make

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.