Queue

The queue is a restricted form of a deque?you can only enter elements at one end and pull them off the other end. Functionally, you could use a deque anywhere you need a queue, and you would then also have the additional functionality of the deque. The only reason you need to use a queue rather than a deque, then, is if you want to emphasize that you will only be performing queue-like behavior.

The queue is an adapter class like stack, in that it is built on top of another sequence container. As you might guess, the ideal implementation for a queue is a deque, and that is the default template argument for the queue; you?ll rarely need a different implementation.

Queues are often used when modeling systems in which some elements of the system are waiting to be served by other elements in the system. A classic example of this is the ?bank-teller problem?: customers arrive at random intervals, gett into a line, and then are served by a set of tellers. Since the customers arrive randomly and each takes a random amount of time to be served, there?s no way to deterministically know how long the line will be at any time. However, it?s possible to simulate the situation and see what happens.

A problem in performing this simulation is that, in effect, each customer and teller should be run by a separate process. What we?d like is a multithreaded environment so that each customer or teller would have their own thread. However, Standard C++ has no model for multithreading, so there is no standard solution to this problem. On the other hand, with a little adjustment to the code, it?s possible to simulate enough multithreading to provide a satisfactory solution.

In multithreading, multiple threads of control run simultaneously in the same address space. (Multithreading differs from multitasking, in which different processes each run in their own address space.) The trick is that you have fewer CPUs than you do threads (and often only one CPU). To give the illusion that each thread has its own CPU, a time-slicing mechanism says ?OK, current thread, you?ve had enough time. I?m going to stop you and give time to some other thread.? This automatic stopping and starting of threads is called preemptive, and it means you don?t need to manage the threading process at all.

An alternative approach is for each thread to voluntarily yield the CPU to the scheduler, which then finds another thread that needs running. This is easier to synthesize, but it still requires a method of ?swapping? out one thread and swapping in another. So instead, we?ll build the time-slicing into the classes in the system. In this case, it will be the tellers that represent the ?threads,? (the customers will be passive). Each teller will have an infinite-looping run( ) member function that will execute for a certain number of ?time units? and then simply return. By using the ordinary return mechanism, we eliminate the need for any swapping. The resulting program, although small, provides a remarkably reasonable simulation:

Each customer requires a certain amount of service time, which is the number of time units that a teller must spend on the customer in order to serve that customer?s needs. Of course, the amount of service time will be different for each customer and will be determined randomly. In addition, you won?t know how many customers will be arriving in each interval, so this will also be determined randomly.

The Customer objects are kept in a queue<Customer>, and each Teller object keeps a reference to that queue. When a Teller object is finished with its current Customer object, that Teller will get another Customer from the queue and begin working on the new Customer, reducing the Customer?s service time during each time slice that the Teller is allotted. All this logic is in the run( ) member function, which is basically a three-way if statement based on whether the amount of time necessary to serve the customer is less than, greater than, or equal to the amount of time left in the teller?s current time slice. Notice that if the Teller has more time after finishing with a Customer, it gets a new customer and recurses into itself.

Just as with a stack, when you use a queue, it?s only a queue and doesn?t have any of the other functionality of the basic sequence containers. This includes the ability to get an iterator in order to step through the stack. However, the underlying sequence container (that the queue is built upon) is held as a protected member inside the queue, and the identifier for this member is specified in the C++ Standard as ?c?, which means that you can inherit from queue in order to access the underlying implementation. The CustomerQ class does exactly that, for the sole purpose of defining an ostream operator<< that can iterate through the queue and print out its members.

The driver for the simulation is the while loop in main( ), which uses processor ticks (defined in <ctime>) to determine if the simulation has run for at least 5 seconds. At the beginning of each pass through the loop, a random number of customers is added, with random service times. Both the number of tellers and the queue contents are displayed so you can see the state of the system. After running each teller, the display is repeated. At this point, the system adapts by comparing the number of customers and the number of tellers; if the line is too long, another teller is added, and if it is short enough, a teller can be removed. In this adaptation section of the program you can experiment with policies regarding the optimal addition and removal of tellers. If this is the only section that you?re modifying, you might want to encapsulate policies inside different objects.

Share
Tweet
Share
Pin