Skip to content

OOP HandsOnSession

Jump to bottom
Óscar Nájera edited this page Mar 11, 2014 · 14 revisions

Object Oriented Programming

This is a refresher on the main idea you should have acquired during the lectures on OOP. We try to humanize how we deal with our code. We would say that we delegate certain tasks to whom can do them best and reliably. In such same way classes in OOP are entities with their own attributes and methods to perform a certain task.

Implementing a Queuing simulation in python

The objective of this session in to train you into Object Oriented Programming in Python. We are bored of the standard example of implementing a matrix multiplication, so we though for you to work on a discrete event simulation to analyze the behavior of a bank queue. To manage the time of in this session, various aspects of the modeling process are already developed for you, so you can focus on the implementation of your code. Nevertheless if your skill level allows, various exercises are proposed to challenge your modeling and programing skills.

The problem: Queues in the bank

Place yourself in a bank. What do you see? The bank has its employees taking care of one single customer each. Then there are customers waiting in line, since they outnumber the available bank employees, and there are new customers arriving at any time and placing themselves in the queue until they are also attended.

If everything goes well, the bank employees will deal with the amount of customers and their requests in a reasonable amount of time, and every customer will wait a reasonable amount of time until being served. But how do we set up this environment, for everything to work well? How many bank employees do we need?, is one single queue better than many queues?, How is the behavior of the customers, do they arrive more during a certain period, or their traffic is more uniform? This characteristics, and many others impact the performance of the queuing system, and we will need to simulate to get a wide view on its behavior.

The modeling method: Discrete Event Simulation

Abstractly, a discrete event simulation consists of a bunch of events and a central simulator object that executes these events in order. The most important characteristics of a queuing system are explained below:

  • Arrival Process: The probability density distribution that determines the customer arrivals in the system.

  • Service Process: The probability density distribution that determines the customer service times in the system.

  • Number of Servers: Number of servers available to service the customers.

Hopefully you have noticed by now that OOP will facilitate your developing process, if you start treating every element as a separate entity that can interact with the others. That's what classes are for.

Hands On work

You already know what we want you to do, get the bank simulation working. For this we present some tutorial like steps for you to get started and easy going. Then problems will get more challenging and fewer instructions will be available. Enjoy!!

Getting started

  • First download our supplied code from this link
  • Unpack it you will find 2 python files. The simulation engine and a template file to get you started

We won't cover the simulation engine inner workings in this tutorial, since our main aim is for you to be able to use foreign code for your applications. That is what collaborative programming is about, we just agree on the interface of the code, how it is meant to be used. If you feel curious of course you can have a look at it. It was specially developed for this school as a very simple discrete event simulation engine. You can learn about it here

Modeling a single customer arrival

First we'll implement a single customer arriving to the bank, to introduce to you how our simulation engine is to be used. Start with the file customer.py Here you will find some written(not yet working) code to complete with this guide.

The first line imports our needed classes from the simulation module des_engine.

from des_engine import Event, Simulator
  • Event is just the base class for any object that will have a time assigned
  • Simulator is the main class that will execute all the events in order

We now continue with our first Object, the customer itself. It inherits from the class Event since the customer arrives at a certain time, and that is the event in time we need to record.

The first method def __init__(self, time): defines the constructor for the object. Here it will assign to the class instance a time, when it is created. The second method def execute(self, simulator): defines what this class does when the simulator gets to it and needs to execute that event. In our case, it will just print into the python terminal a message.

class Customer(Event):
    """Represents the customer visiting the Bank"""
    def __init__(self, time):
        self.time = time
    def execute(self, simulator):
        """Event class required action"""
        print "I'm a customer and arrived at t=" + str(self.time)

The second Object we need to implement is the BankSimulator which is the central simulator that executes the events in order. For it we don't require to implement a constructor now. What we do need is the run method which has the instructions for the simulator. Our first instruction is to add the customer to the simulation

class BankSimulator(Simulator):
    """Simulates the Workday of a Bank"""
    def run(self):
        """Runs simulation"""

        self.insert(Customer(5))

        self.do_all_events()

The last part of the file is just a standard way of implementing the default execution instruction in python when the file is called. Here we instance the Bank UBS(very swiss and neutral, no preference) and let it execute.

if __name__ == "__main__":
    UBS = BankSimulator()
    UBS.run()

Test your code and see how it works!!

Adding more customers

The next step would be to put more customers in the bank so we can change the BankSimulator class to include more customer like this.

self.insert(Customer(5))
self.insert(Customer(1))
self.insert(Customer(8.9))
self.insert(Customer(0.5))

Test how this new code chunk works, are the customers arrivals ordered when running the simulation, despite being created in other order? Are non integer arrival times accepted? Test your own values and amount of customers.

Many customers

Of course if we want a simulation to be useful, we should allow for a new class to generate our customers arriving and not put all the customers manually as we have been doing. We will call it NewArrival, and since it will be dealing with the customer's arrival time, it would be a good idea to inherit it also from the Event class, for it to keep an internal clock. Have a look at the presented code. Can you understand what it does? Or just give it a try modifying your already implemented code.

class NewArrival(Event):
    """Simulates the arrival of customers"""
    def __init__(self, time):
        self.time = time

    def execute(self, simulator):
        """Generates new customer at given time"""
        for i in range(4):
            customer = Customer(self.time+i)
            simulator.insert(customer)

class BankSimulator(Simulator):
    """Simulates the Workday of a Bank"""
    def run(self):
        """Runs simulation"""

        self.insert(NewArrival(0))
        self.do_all_events()

Well it just created 4 new customers arriving at equally spaced time intervals. Now it's your turn to do some coding.

Tasks

  • Modify your code to allow customers to arrive at a random time
    • Hint: Have a look at the python module random
  • Does a Bank always welcome a fixed number of customer a day? Modify the code to generate customers arriving at random times until a maximum time is reached. The Bank closes at some time right?
    • Hint: Can you make the NewArrival class create new events on its own think what the statement simulator.insert(self) would do.

Now the interactions. Putting the bank teller and the queue

To still keep things simple we'll start with a single queue and one bank assistant. You should have discovered from the previous task, how a class can schedule new events. That is good, now you need to get some new classes communicating with each other.

Implement a class Queue

This will hold the customers that arrived and wait to be served. It appears reasonable that:

  • It contains a list that holds the customers
  • One method that tells how many customers are waiting
  • One method that takes arriving customers and puts them at the end of the queue
  • One method that takes the first customer in line to send
  • Hint: have a look at the methods append and pop for lists

Also think on how to communicate the customer NewArrival and the Queue and who and how will schedule new events. Test your code, and have it output events to the terminal so you can follow what is happening. You can start with the next template.

class Queue(object):
    """Waiting Queue in the Bank"""
#Implement the list for the customers
#Implement a size function
#Implement an insert method
#Implement a method to send customer out of the line

Implement a class Server

This class will hold the bank cashier that serves the customer waiting in line. Then you will need it to be able to communicate to the Queue class to call the customers when the Server becomes free from the last customer and in the same way the Queue should communicate to the Server. Then it appears reasonable to implement for this class in a way:

  • It inherits from the Event class, because the Server has an activity in time. When it receives a customer, and when he has finished.
  • It should store the customer being served
  • It should have a method to tell if it's busy with a customer or free to receive one
  • It should have a method to receive a customer and schedule in the main simulator the time when it will finish.
  • Event have the execute method, that gets executed when the simulator arrives to the event

You can start with the next template.

class Server(Event):
    """Simulates the cashier"""
#Implement a constructor that holds time and the customer served variable
#Implement a method to tell availability
#Implement a method to receive a customer and schedule a finish time event

    def execute(self, simulator):
        """Completes serving customer and takes new one if waiting"""
#Implement the execute method

Check that your code runs a full simulation:

  • Customers arriving at a random times and lining up in the Queue.
  • The bank employee serving each customer in order.

Now some more tasks

  • Consider changing the frequency at which customers arrive and form into the queue
  • Consider a random amount of time that the bank employee needs to dispatch every customer. Or the other way around, customers arriving with different workloads for the bank employee.
  • Prepare yourself for the next Hands on session on data plotting and change your program so it records the customer's time waiting in the bank for futures statistics
  • Try to find the point relating the average customer arrival frequency and the average server dispatch time. When does it all stops working smoothly and you have a lot of angry customers waiting.

Done!

You can continue challenging yourself. Think about

  • Having now multiple bank employees serving the customers in line. Perhaps with multiple service time performance.
  • How about having multiple queues? Do you think there's a reason why banks use single queues while supermarkets use multiple queues? What happens in every case?
  • Let customers choose from the multiple queue. Even allow then to change queues while waiting.
  • Supermarkets open new lines when more than a certain amount of customers wait in line, model this behavior.

References

[1] http://pythonhosted.org/SimPy/Tutorials/TheBank.html

[2] http://home.ubalt.edu/ntsbarsh/ECON/QS.html

[3] http://www.cs.northwestern.edu/~agupta/_projects/networking/QueueSimulation/mm1.html

Clone this wiki locally