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.
- ./arrival prints to standard output when a job arrives and how much time it takes to service the job.
- 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?
- Uniform arrival:
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.