Project 1 – Lines, Lines, Lines!
“The Great Single-queue vs. Multi-queue Debate”
“Why the line was invented”.
In the movie “Michael”, John Travolta stars as a cigarette-smoking, beer-swilling archangel (yup, a real archangel, wings and all). At one point in the movie, he says:
…I invented standing in line.
You invented standing in line?
Before, everybody milled around. It was a mess. So one day I said, "Why not make a line?"
To get in.
How many of you have finished shopping at Target, gone up to the front to pay, and been confronted with a gazillion lines, each with two or three customers waiting to pay, and had to deal with picking which line to wait in? To make matter worse, once you pick a line and commit to it, you notice that you seem to have chosen one of the slower lines? Who hasn't had that happen? "There must be a better way", you think. Then, you go to the MVA to renew your license, and get put in a single waiting list to wait for a free agent; they seem to call names quite frequently... but then you notice that they just called #47, and your ticket says "THREE GAZILLION-47"! Sigh. There must be a better way.
Well, maybe you can't think of a better way, but you at least want to figure out whether Target's system--lots of short, individual lines, one per server--is better than the MVA's--one giant line feeding lots of servers one-by-one. Your intuition tells you that getting to choose your line at Target feels more optimal than the bureaucratic "one for all" MVA system--but are you right? You were wrong about that haircut you got last week... How do you prove you are right in this case?
The idea of how to optimally serve a group of people with a set of time-limited resources is important--and interesting--enough that there is a whole field called "queuing theory" dedicated to this subject. In this project, we are going to implement two different models of queuing, and build these into a simulator that runs the two models and collects statistics to compare the performance of the two.
The two models you will implement simulations for are the "multi-queue/multi-server" model and the "single queue/multi-server" model. "What's a queue? You know what a line is? Same thing." (Can you identify that oblique movie reference?)
In a multi-queue/multi-server environment, people arrive to confront multiple choices for servers, each with a dedicated waiting line in front of them. The customers come in one by one and pick a line to wait in—usually, just the shortest. They then do not change lines until they are served. When a server finishes with a customer, the next person in their line immediately goes up to be the next customer served.
In a single-queue/multi-server environment, people arrive and get on the end of one long line. As a server becomes free, the person at the head of the line immediately goes to that free server.
We are making several simplifying assumptions: First, we assume all servers are equivalent; therefore, each will take an identical amount of time to handle any given customer. Second, in the multi-queue case, the customers have no additional information (e.g., looking to see if there's any particularly finicky-looking customer in each line) to consider in deciding which line to pick, so they will each simply pick the shortest line as they come up, the leftmost one if there are several lines tied for shortest.
In order to run a simulation, you have to have a model of how frequently and with what “bunching” you expect customers to arrive, and how long they will take with a server. In our simulation, we will be modeling these two things with carefully chosen statistical distributions. (For those interested in the details, we model the arriving customers as random stochastic processes using an Exponential distribution, and the service times with a combination of 2 different Poisson distributions, with the means chosen so as to keep a certain number of servers busy.) You do not have to think about any of this—we have done that for you. Using reasonable models, we have generated an input file that contains the customer description data that you will use to feed your simulation. The records in this input file describe each arriving customer, following the specific format given below. You must read this data in using the file open and input functions we covered in the File I/O lectures. The input file will specify each arriving customer as an ID#, arrival time, and time-to-serve, already sorted by arrival time. You will read this file in into a Python list, each element of which will be an instance of a class Customer, which you will design. To keep things simple, you should just read this file completely in, and construct the entire list, before you start the actual simulation part of your code. (In other words, do not read a line, then run a cycle of your simulation, then read the next record in, then…)
After reading in and constructing the input list, your code will simulate the following:
From a Customer instance's point of view:
1. When a customer arrives (at their designated time), they will go to the end of a queue—either the shortest if multi-queue, or the one queue if single-queue.
2. As each server finishes with a customer, they will call up the next customer in line, whether the individual line for that server if multi-queue, or the big common line if single-queue.
3. When each given customer finally reaches a server, they will note the time, and compute how long they’ve been waiting in line.
4. They will then spend their pre-determined service time with that server.
5. They will then leave.
From your Simulator’s point of view:
It is important that you do the following in the exact given order:
First, set up all important data structures to keep track of servers, queues, etc.
Then, looping until done:
1. First, scan all the servers to see which will finish with their Customer the earliest, ignoring any server that is currently idle. Note that server# and finish time. (This might be “None” if all the servers are idle, which would be the situation at the very beginning, and possibly also at various points in the middle of the simulation).
2. Then look at the upcoming arrival (the next customer on your arrival list) to see when the next Customer will arrive.
3. Determine what the earliest next event is, and handle it:
a. IF both the arrival list and all of the servers are empty, you are DONE!
b. ELSE IF the next arrival happens before or at the same time as the earliest server-done event, or all of the servers are empty:
• In the single-queue case: Take this next new Customer from head of the arrival list, and put her at the end of the unified queue.
• In the multi-queue case: First search for the shortest queue. A complication: in the case of multiple empty queues, you have to take into account whether the associated server is occupied. In other words, an empty queue with an idle server is “shorter” than an empty queue where the server is busy. In the case of a tie, pick the earlier queue. Add the Customer to the end of the first shortest queue.
c. ELSE: you know the earliest server-done happens before the next arrival, or there are no more arrivals. You should:
• Process the server-done event, i.e., remove the Customer from the server and move them to the "Done" list, and mark the server as being idle (don’t worry about assigning them a new customer yet—that’s in the next step).
4. Scan all of the servers in order. For every idle server assign the next Customer from the appropriate queue (either that server's personal queue in the multi-queue case, or the joint queue in the single-queue case) to the idle server, and record this start-of-service time in the Customer object.
5. Loop back to step 1
Note that with the multi-queue/multi-server model, if a given server actually finishes with their line and is idle, one or more customers will *not* scurry over from other lines. This is a very civilized, polite group, and they would rather have a server sit idle than face a potential fight over who got there first In general, they will never jump from their chosen line to another, shorter line.
So, how should you implement this? The following is a set of requirements on your design, but IS NOT a suggested development order; recall the lectures on top-down design for strategies on incrementally developing this large project.
• First, design and implement a Customer class, with enough attribute fields so that you can store the ID, arrival time, time they finally got served, and any other fields you deem necessary. Create an appropriate constructor, and add all necessary accessor and mutator methods. It should actually be a relatively simple class. You should put the class definition into its own file: “Customer.py”, and import this into your proj2.py program by using:
from Customer import Customer
as per the instructions in the lecture notes. You will also submit Customer.py
NOTE: This is the only class you will implement for this project. All of the other data structures used in this project—the waiting queues, the servers, etc.—can be implemented with existing Python data structures like lists, sets, and dictionaries.
• For dealing with time in this simulation, you can stick with using ints. The arrival times, and service times in the input file will all be integers, and since you will only be adding and subtracting times, those calculations will stay in the integer domain, too. The only time you should switch to floats is in calculating statistics like mean and median times—those need to be exact. Remember: dividing an integer by another integer will give truncation errors.
• An important note about time in the simulator: You will be using “time elapsed in seconds since Start of Simulation”—“SoS” for short—as your timing standard, and not wall clock time. All time data in the input file (arrival times, service durations) are in units of seconds. Let us suppose a sample Customer arrival record in the data file read:
47 1800 120
That means Custome_ID#47 arrives at 1800 SoS (i.e., 30 minutes after start of simulation). If she then waits in line some period of time (depends on your simulator) and finally makes it to a free server at 2100 SoS, she will have waited in line 2100 - 1800 = 300 seconds. If she then takes 120 seconds with the actual server, her finish time will be 2220 seconds SoS, i.e., “2200 seconds after start of simulation”. So you don’t have to worry about minutes or hours or days, or anything else.
• Implement a function called singleQueue(), which takes two parameters: first, the number of servers to simulate, and second, a list of Customer instances. It should implement the single-queue version of the simulation, as described in the previous section of this document (see “From a Simulator point of view” above). It should return a new list containing all of the Customer instances from the original list that was passed in, but now in the order in which they finished being served, and with each Customer instance augmented with it's simulation-computed fields (i.e., those fields you created to keep track of what happened to the Customer as he went through the simulation; most important is the time each customer waited in line). It should implement the single-queue/multi-server simulation. Note that you are allowed to modify the Customer instances, but if you do so, you should either make sure your changes do not affect the next (multiQueue) simulation, or alternatively, provide—and invoke—a method to reset the Customer instance before you do the multiQueue simulation. Also, the returned list should be a new list—do not modify the structure of the list passed in as the parameter. That way, it can be reused in the multiQueue simulation run next.
• Implement a function called multiQueue() which has the same parameters and return type as SingleQueue(), but which implements a multi-server/multi-queue simulation.
• Implement a function called printStats() that takes a list of post-simulation Customer instances, (i.e., the list that was returned by singleQueue() or multiQueue()) which have time data filled in from running the simulation. It should then compute and output the following statistics:
o Mean wait per customer: the wait times averaged across all Customers
o Median wait time: the middle wait time among all Customersi, i.e., half the customers waited longer than this, half less; this would be the middle item in the sorted list of wait times. If there is no exact middle (because there are an even number of entries), you average the values just above and below the middle.
o Maximum wait time: the longest time any Customer had to wait
Important: mean and median wait times must both be floats!
Note that all of these statistics involve wait times, which are measured as the time from when a Customer arrives to when they begin to be served by a server.
• Implement a function called runSimulation() that takes a filename as a parameter, opens that file and reads in the Customer records, then first runs multiQueue(), and passes the returned list to printStats(), then runs singleQueue(), and again calls printStats() to print the new statistics. Additional advice (not a requirement): you might want to implement the file-reading part as a separate function.
• Lastly, write a main() that prints a greeting, prompts the user for the name of the input file, and then calls runSimulation() with this filename.
The rest of the design, including how you structure the internals of singleQueue() and multiQueue(), what subfunctions you implement, etc., are left up to you. Most importantly, an important part of your design will be how you design the data structures for implementing the servers and waiting lines. We have taught you some of the fundamentals of how to use functions to create designs that are modular and reusable--apply them.
Format of Data File
We will provide the input file queue_sim_data.txt The first line of the file is a single number, specifying the number of servers your program should simulate.
The remainder of the input data file will consist of one record per line for each customer arrival. The record will consist of three fields:
The fields will be a unique integer, but don’t assume or depend upon, it being in any particular order—just different. The and will be integers in units of whole seconds. is when they get to the store; they will then immediately get in a line. The is the number of seconds they will need to pay/do their business once they get through the line and actually move up to a server. The file is sorted by ; this field is not necessarily unique. and sequential records might have the identical values for this field.
You should read these records into a list of Customer instances in the order that it appears in the file. If two customers share an identical arrival time, assume the earlier record arrived first.
So, A sample file might look like:
1 100 80
2 100 70
3 110 60
4 140 50
5 140 200
6 230 10
7 235 200
8 240 20
9 240 30
10 240 30
The first line specifies that you should create a simulation of 3 servers. The next line “1 100 80” means the first customer, ID#1, arrives at time=100 seconds SoS (recall that this means “since Start of Simulation”); they will then spend some time in the waiting line, and once they get to a server, will need 80 seconds with the server to pay/get their license/whatever they need to do. The second customer arrives right behind the first (note the identical arrival time), and will need 70 seconds at the server. Also note that customers ID#4 and ID#5 also arrive together, but again, you should assume customer #4 gets in line first.
Note that the Customer ID# is not in any particular order—just guaranteed unique in the file. The file is strictly sorted by arrival time so you can just process it sequentially.
Reminder of Documentation
At the top of each file, we are requiring a file header comment. The format of this header has been described ad nauseum in other homework specifications and in the course programming standards document. Commenting and proper formatting is also critical. Please review the 201 Python standards carefully. A good portion of each of your assignment grades depends upon how well you adhere to these standards.
Submitting your work
When you've finished your homework, use the submit command to submit the two files for this project:
submit cs201 Proj1 proj1.py Customer.py
Don't forget to watch for the confirmation that submit worked correctly. Specifically, the confirmation will say:
The following would be the output of a run with the sample data from the example above:
linux3% cat sample_data.txt
1 100 80
2 100 70
3 110 60
4 140 50
5 140 200
6 230 10
7 235 200
8 240 20
9 240 30
10 240 30
linux3% python proj1.py
This program will run simulations of single-queue/multi-server and
multi-queue/multi-server queuing models.
Please enter the name of the data file: sample_data.txt
The data file specifies a 3-server simulation.
There are 10 arrival events in the data file.
Running single-queue simulation...
Mean wait per customer: 13.0 seconds
Median wait time: 0.0 seconds
Maximum wait time: 50 seconds
Running multi-queue simulation...
Mean wait per customer: 39.5 seconds
Median wait time: 0.0 seconds
Maximum wait time: 195 seconds
A Detailed Explanation of the Sample Run
To help you get started, let’s run through what should happen with the above sample file:
The following simulation runs assume you have already read in all of the customer arrival records from the input file, and have created a list of Customer instances.
For the single-queue simulation:
1. The servers are IDLE. The single queue is empty. the done-list is empty.
2. Peek at the next arrival: the next arrival would be Customer-ID#1 with an arrival time t=100 SoS (from the first customer record in the file). The next server-done time is not set, because there is no occupied server. So, the arrival is the next event.
3. Add the arriving Customer to the end of the single queue (it is now the only entry in the queue).
4. Scan servers in order looking for idle ones; right now, all 3 are idle
o server is first idle one, so remove Customer-ID#1 from head of the queue, move it to server, mark the time. (So, this customer actually waited 0 seconds in the queue!)
o The other 2 idle servers don’t get assigned anything because the queue is now empty.
5. Done with this event—look for next one:
6. Peek at the next arrival: ID#2. Her arrival time is again 100 (so she walked in right behind ID#1). The next server-done time is server, who will finish at t=180 SoS (remember, the server started serving ID#1 at t=100, and ID#1 needs 80 seconds with the server). The next arrival comes before the first server-done, so process the arrival:
7. As in Step 3, add Customer0ID#2 to end of the queue (again, it was empty)
8. Scan for first idle server: both server and server are idle, so pick server. Assign it Customer-ID#2, as in Step 4 above, again record time. This server will finish at t=170 (100 + 70)
9. Done with this event—look for next one:
10. More briefly: Customer-ID#3 arrives at t=110, which is stll earlier than the earliest server-done (server will finish at t=180, server at t=170, so send it to queue; it will then be assigned to server, with finish time t=110 + 60 = 170
11. Next arrival is ID#4, at t=140. Earliest server-done is server (actually, both server and server tie for earliest time, so pick first one: server). The next arrival is still before earliest server-done, so send it to the queue. But this time, when we scan for an idle server, we notice all the servers are busy, so ID#4 stays in the queue.
12. Next arrival is ID#5 at t=140; again, right behind ID#4. Still before earliest server-done, so process arrival: add it to end of queue (which now has 2 Customers). Scan for idle servers: all busy, so do nothing,
13. Next arrival: ID#6 at t=230. First server-done is server at t=170, so server-done comes first--finally!
14. Process server-done by moving Customer-ID#1 from server to the done-list (first one there).
15. Scan for idle servers: guess what: server is now idle, so move first Customer from queue (ID#4) to server, recording the time: t=170. ID#4 arrived at t=140, so they waited in line for 170 – 140 = 30 seconds—we’ll need this number for each processed Customer at the end.
16. Next arrival: still ID#6 at t=230; first server-done: server at t=170, so process server-done
So you see how this goes: we are always first deciding what comes next: an arrival, or a server-done. We handle it, then scan for idle servers in either case (think about why we want to do this for both cases).
For the multi-queue simulation:
It would be very similar to above, but with 3 waiting queues now, one for each server:
1. Next (i.e., first) arrival: t=100; first server-done: none. So, process arrival:
2. NEW: find shortest queue (first one in case of tie): all 3 are empty, so pick add ID#1 to queue
3. Scan for idle servers: first find server: it has non-empty queue, so move 1st item from queue (ID#1) to server, noting time waited (0). Also scan server and server as idle, but do nothing for each because their respective queues are empty.
4. Next arrival: ID#2, t=100. First server-done: server, t=180. Arrival is earlier, so process it:
5. Find shortest queue to put ID#2 into: all three queues are empty, but the server for queue is busy, so queue and queue are considered “shorter”. Pick the first one in a tie: so we put ID#2 in queue.
6. Scan for idle servers: server is idle, and has a non-empty queue, so move ID#2 from the head of queue to server. server is idle, but queue is empty, so do nothing.
7. Next arrival: ID#3, t=110. First server-done: server, t=170. Arrival is earlier, so process it:
8. Find shortest queue to put ID#3 in: all three queues are empty, but the servers for queue and queue are busy, so queue is considered “shorter”. Put ID#3 in queue.
9. Scan for idle servers: server is idle, and has a non-empty queue, so move ID#3 from the head of queue to server. (Now all three servers are busy.)
10. Next arrival: ID#4, t=140. First server-done: server, t=170. Arrival is earlier, so process it:
11. Find shortest queue to put ID#4 in: all three queues are empty, all of their respective servers are busy. Pick the first one in a tie: so we put ID#4 in queue.
12. Scan for idle servers: all three servers are busy.
13. Next arrival: ID#5, t=140. First server-done: server, t=170. Arrival is earlier, so process it:
14. Find shortest queue to put ID#5 in: queue and queue are empty, and both of their respective servers are busy. Pick the first one in a tie: so we put ID#5 in queue.
15. Scan for idle servers: all three servers are busy.
16. Next arrival: ID#6, t=230. First server-done: server, t=170. Server-done is earlier, so process it:
17. Process server-done by moving Customer-ID#1 from server to the done-list (first one there).
18. Scan for idle servers: server is now idle, so move first Customer from its personal queue—ID#5—to server, recording the time: t=170. ID#5 arrived at t=140, so they waited in line for 170 – 140 = 30 seconds—we’ll need this number for each processed Customer at the end.
(Recall that ID#4 got to the store just ahead of ID#5; in the single-queue case, he would have been served first, but here in the multi-queue case, ID#4 is stuck behind a slow-poke (ID#1), glaring at server/ID#5 and thinking it’s not fair!)
19. Next arrival: still ID#6 at t=230; first server-done: server at t=170, so process server-done. More ID#3 to done-list.
20. Scan for idle servers: server is now idle, but queue is empty!
So, the handling is very similar to the single-queue scenario, except that we have to decide what queue to add new customers to. Another interesting note: just after t=170, we have the funny situation of server being idle with no one in its queue, but ID#4 is still waiting in queue, and will be there for another 10 seconds until his server is done with ID#1. Is this realistic? How many of you have been in line, seen a different line open up, and rushed over, only to be beaten out by 10 other people with the exact same idea, and ended up worse off? Yeah, it’s probably realistic…Attachments