[2021] Imperial College London - Principles of Programming - Q3 Queue Simulator
Question 3 Queue simulator
The objective of this question is to write a simulator for the queues in a shop. The queue_sim.queue_sim module contains:
- A simple Shopper class.
- An abstract base class called MultiQueue, which models several queues.
When you need to use an individual queue in this exercise, it is recommended that you use the collections.deque class.
3 (a)
(i) (3 marks)
Implement a subclass of MultiQueue called PostOfficeQueue. In this MultiQueue, there is just a single queue. When a shopper is popped from any lane, it is the shopper at the head of the single queue which is returned.
(ii) (3 marks)
Implement a subclass of MultiQueue called SupermarketQueue. In this MultiQueue, each lane has its own queue. When a new shopper is appended, they join whichever is the shortest queue. If there is a tie, they can be appended to any of the joint shortest queues.
3 (b)
(i) (1 mark)
Implement a class Checkout whose constructor takes a MultiQueue representing set of queues in the shop, and an integer representing the current lane. The Checkout should also store the current Shopper being served (initially this will be None) and the time at which this shopper will finish being served (initially 0).
(ii) (1 mark)
Implement the __bool__ special method on Checkout so that a Checkout is True if there is currently a Shopper being served, and False otherwise.
(iii) (4 marks)
Implement a method step which takes in a single integer representing the current time in the simulation. step will be called for each checkout each time unit of the simulation. Step does one of two things depending on whether the Checkout is currently serving a Shopper.
If the Checkout is not currently serving a Shopper then the Checkout pops the next Shopper from its lane of the MultiQueue and starts serving it. The Checkout sets its finish time to the current simulated time plus the size of the Shopper. If no Shopper is available in the relevant lane of the MultiQueue then the step simply returns without starting to serve a new Shopper.
If the Checkout is currently serving a Shopper then the Checkout checks if the time has reached its finish time. If it has not then it simply returns without making a change. If it has reached the finish time then the Checkout records that it is no longer serving a shopper, and returns the current Shopper.
3 (c) (4 marks)
Finally we will write a function to run a queue simulation. The interface to a function queue_sim.queue_sim.run_simulation is provided. It takes as input a class, which should be a subclass of MultiQueue, a number of lanes, a list of Shopper objects representing the shoppers in the simulation, and an integer rate at which shoppers join the queue.
The simulation should start by instantiating the MultiQueue subclass with the given number of lanes. It should also instantiate a matching set of Checkouts. A list of exiting shoppers should be created. It should be empty.
The simulation time starts at 0, and increases by 1 time unit each step. Each step, the following happens:
Until the incoming shopper list is empty, rate Shopper objects are popped from this list and appended onto the MultiQueue; and
Each Checkout in turn executes one step by calling its step method on the current simulation time. If a Checkout.step call returns a Shopper then this is appended to the exiting shopper list.
The simulation ends when all of the Shopper objects are on the exiting shopper queue. The function should then return a pair (end_time, shoppers_out) comprising the end time and the exiting shopper list.
3 (d)
(i) (2 marks)
Ensure that your code passes Flake8.
(ii) (2 marks)
Ensure that your code otherwise conforms to good programming style as we have learned in this course.
There is no need to write any docstrings in this exam.
Get the Solution to This Question
WeChat (微信)
WhatsApp
