The queue is a FIFO (First in first out) structure. In daily life, you have also seen that it is not true that a person, who comes first, leaves first from the queue. Let’s take the example of traffic. Traffic is stopped at the signal. The vehicles are in a queue. When the signal turns green, vehicles starts moving. The vehicles which are at the front of the queue will cross the crossing first. Suppose an ambulance comes from behind. Here ambulance should be given priority. It will bypass the queue and cross the intersection. Sometimes, we have queues that are not FIFO i.e. the person who comes first may not leave first. We can develop such queues in which the condition for leaving the queue is not to enter first. There may be some priority. Here we will also see the events of future like the customer is coming at what time and leaving at what time. We will arrange all these events and insert them in a priority queue. We will develop the queue in such a way that we will get the event which is going to happen first of all in the future. This data structure is known as priority queue. In a sense, FIFO is a special case of priority queue in which priority is given to the time of arrival. That means the person who comes first has the higher priority while the one who comes later, has the low priority. You will see the priority queue being used at many places especially in the operating systems. In operating systems, we have queue of different processes. If some process comes with higher priority, it will be processed first. Here we have seen a variation of queue. We will use the priority queue in the simulation. The events will be inserted in the queue and the event going to occur first in future, will be popped.
What are the requirements to develop this simulation? We need the C++ code for the simulation. There will be a need of the queue data structure and obviously, the priority queue. Information about the arrival of the customers will be placed in an input file. Each line of the file contains the items (arrival time, transaction duration).
Here are a few lines from the input file.
| 00 30 10 <- customer 1 00 35 05 <- customer 2 00 40 08 00 45 02 00 50 05 00 55 12 01 00 13 01 01 09 |
The first line shows the customer 1. “00 30 10” means Customer 1 arrives 30 minutes after the opening of the bank. He will need 10 minutes for his transaction. The last entry “01 01 09” means customer arrives one hour and one minute after the bank opened and his transaction will take 9 minutes and so on. The file contains similar information about the other customers. We will collect the events now. The first event to occur is the arrival of the first customer. This event is placed in the priority queue. Initially, the four teller queues are empty. The simulation proceeds as follows: when an arrival event is removed from the priority queue, a node representing the customer is placed on the shortest teller queue. Here we are trying to develop an algorithm while maintaining the events queue.
After the opening of the bank, the arrival of the first customer is the first event. When he enters the bank all the four tellers are free. Suppose he goes to the first teller and starts his transaction. After the conclusion of his transaction, he leaves the bank. With respect to events, we have only two events, one is at what time he enters the bank and other is at what time he leaves the bank. When other customers arrive, we have to maintain their events.
If the customer is the only one on a teller queue, an event for his departure is placed on the priority queue. At the same time, the next input line is read and an arrival event is placed in the priority queue. When a departure event is removed from the event priority queue, the customer node is removed from the teller queue. Here we are dealing with the events, not with the clock. When we come to know that a person is coming at say 9:20am, we make an event object and place it in the priority queue. Similarly if we know the time of leaving of the customer from the bank, we will make an event and insert it into the priority queue. When the next customer in the queue is served by the teller, a departure event is placed on the event priority queue. When the other customer arrives, we make an event object and insert it into the priority queue. Now the events are generated and inserted when the customer arrives. But the de-queue is not in the same fashion. When we de-queue, we will get the event which is going to occur first.
When a customer leaves the bank, the total time is computed. The total time spent by the customer is the time spent in the queue waiting and the time taken for the transaction. This time is added to the total time spent by all customers. At the end of the simulation, this total time divided by the total customers served will be average time consumed by customers. Suppose that 300 customers were served, then we will divide the total time by 300 to get the average time. So with the help of simulation technique, we will get the result that x customers came today and spent y time in the bank and the average time spent by a customer is z.
Code of the Bank Simulation
Let’s have a look on the C+ code of this simulation.
| #include <iostream> #include <string> #include <strstream.h> #include "Customer.cpp" #include "Queue.h" #include "PriorityQueue.cpp" #include "Event.cpp" Queue q[4]; // teller queues PriorityQueue pq; //eventList; int totalTime; int count = 0; int customerNo = 0; main (int argc, char *argv[]) { Customer* c; Event* nextEvent; // open customer arrival file ifstream data("customer.dat", ios::in); // initialize with the first arriving customer. ReadNewCustomer(data); While( pq.length() > 0 ) { nextEvent = pq.remove(); c = nextEvent->getCustomer(); if( c->getStatus() == -1 ){ // arrival event int arrTime = nextEvent->getEventTime(); int duration = c->getTransactionDuration(); int customerNo = c->getCustomerNumber(); processArrival(data, customerNo, arrTime, duration , nextEvent); } else { // departure event int qindex = c->getStatus(); int departTime = nextEvent->getEventTime(); processDeparture(qindex, departTime, nextEvent); } } |
We have included lot of files in the program. Other than the standard libraries, we have Customer.cpp, Queue.h, PriorityQueue.cpp and Event.cpp. With the help of these four files, we will create Customer object, Queue object, PriorityQueue object and Event object. You may think that these are four factories, creating objects for us.
As there are four tellers, so we will create equal number of queues (Queue q[4]). Then we create a priority queue object pq from the PriorityQueue factory. We declare totalTime, count and customerNo as int. These are global variables.
In the main method, we declare some local variables of customer and event. Afterwards, the customer.dat file for the input data is opened as:
ifstream data("customer.dat", ios::in);
We read the first customers data from this file as:
readNewCustomer(data);
Here data is the input file stream associated to customer.dat. We will read the arrival time and time of transaction from the file of the first customer. After reading it, we will process this information.
Now there is the while loop i.e. the main driver loop. It will run the simulation. First thing to note is that it is not clock-based which is that the loop will execute for 24 hours. Here we have the condition of priority queue’s length. The variable pq represents the event queue. If there are some events to be processed, the queue pq will not be empty. Its length will not be zero. We get the next event from the priority queue, not from the queue. The method pq.remove() (de-queue method) will give us the event which is going to happen first in future. The priority of events is according the time. In the event object we have the customerNo. In the if statement, we check the status of the customer. If the status is –1, it will reflect that this is the new customer arrival event.
We know that when a new customer enters the bank, he will look at the four tellers and go to the teller where the queue is smallest. Therefore in the program, we will check which is the smallest queue and insert the customer in that queue. If the event is about the new customer, the if statement returns true. We will get its arrival time, duration and customer number and assign it to the variables arrTime, duration and customerNo respectively. We will call the method processArrival() and pass it the above information.
If the status of the customer is not equal to –1, it means that the customer is in one of the four queues. The control will go to else part. We will get the status of the customer which can be 0, 1, 2 and 3. Assign this value to qindex. Later on, we will see how these values are assigned to the status. We will get the departure time of the customer and call the processDeparture() method.
In the main driver loop, we will get the next event from the event queue. In this case, events can be of two types i.e. arrival event and the departure event. When the person enters the bank, it is the arrival event. If any queue is empty, he will go to the teller. Otherwise, he will wait in the queue. After the completion of the transaction, the customer will leave the bank. It is the departure event.
Let’s discuss the function readNewCustomer(). This function is used to read the data from the file.
| void readNewCustomer(ifstream& data) { int hour,min,duration; if (data >> hour >> min >> duration) { customerNo++; Customer* c = new Customer(customerNo, hour*60+min, duration); c->setStatus( -1 ); // new arrival Event* e = new Event(c, hour*60+min ); pq.insert( e ); // insert the arrival event } else { data.close(); // close customer file } } |
Here, we have used the >> to read the hour, minute and duration from the file. Then we create a customer object c from the customer factory with the new keyword. We pass the customerNo, arrival time and transaction duration to the constructor of the customer object. After the object creation, it is time to set its status to –1. This means that it is an arriving customer. Then we create an event object e passing it the customer c and the arrival time. We insert this event into the priority queue pq. If there is no more data to read, we go into the else part and close the data file.
Let’s see the function processArrival(). We have decided that when the customer arrives and no teller is available, he will go to the shortest queue.
| int processArrival(ifstream &data, int customerNo, int arrTime, int duration, Event* event) { int i, small, j = 0; // find smallest teller queue small = q[0].length(); for(i=1; i < 4; i++ ) if( q[i].length() < small ){ small = q[i].length(); j = i; } // put arriving customer in smallest queue Customer* c = new Customer(customerNo, arrTime, duration ); c->setStatus(j); // remember which queue the customer goes in q[j].enqueue(c); // check if this is the only customer in the. // queue. If so, the customer must be marked for // departure by placing him on the event queue. if( q[j].length() == 1 ) { c->setDepartureTime( arrTime+duration); Event* e = new Event(c, arrTime+duration ); pq.insert(e); } // get another customer from the input readNewCustomer(data); } |
First of all, we will search for the smallest queue. For this purpose, there is a for loop in the method. We will check the length of all the four queues and get the smallest one. We store the index of the smallest queue in the variable j. Then we create a customer object. We set its status to j, which is the queue no. Then we insert the customer in the smallest queue of the four. The customer may be alone in the queue. In this case, he does not need to wait and goes directly to the teller. This is the real life scenario. When we go to bank, we also do the same. In the banks, there are queues and everyone has to enter in the queue. If the queue is empty, the customers go straight to the teller. Here we are trying to simulate the real life scenario. Therefore if the length of the queue is one, it will mean that the customer is alone in the queue and he can go to the teller. We calculate his departure time by adding the arrival time and transaction time. At this time, the person can leave the bank. We create a departure event and insert it into the priority queue. In the end, we read a new customer. This is the way; a programmer handles the new customers. Whenever a new person enters the bank, we create an event and insert it into the smallest queue. If he is alone in the queue, we create a departure event and insert it into the priority queue. In the main while loop, when we remove the event, in case of first future event, it will be processed. After the completion of the transaction, the person leaves the bank.
We may encounter another case. There may be a case that before leaving the bank, more persons arrive and they have to wait in the queue for their turn. We handle this scenario in the departure routine. The code is:
| int processDeparture( int qindex, int departTime, Event* event) { Customer* cinq = q[qindex].dequeue(); int waitTime = departTime - cinq->getArrivalTime(); totalTime = totalTime + waitTime; count = count + 1; // if there are any more customers on the queue, mark the // next customer at the head of the queue for departure // and place him on the eventList. if( q[qindex].length() > 0 ) { cinq = q[qindex].front(); int etime = departTime + cinq->getTransactionDuration(); Event* e = new Event( cinq, etime); pq.insert( e ); } } |
In this method, we get the information about the qindex, departTime and event from the main method. We get the customer by using the qindex. Then we calculate the wait time of the customer. The wait time is the difference of departure time and the arrival time. The total time holds the time of all the customers. We added the wait time to the total time. We incremented the variable count by one. After the departure of this customer, next customer is ready for his transaction. The if statement is doing this. We check the length of the queue, in case of presence of any customer in the queue, we will check the customer with the front() method. We set its departure time (etime) by adding the depart time of the previous customer and his transaction time. Then we create an event and insert it in the priority queue.
In the end, we calculate the average time in the main loop and print it on the screen. Average time is calculated by dividing the total time to total customer.
| // print the final average wait time. double avgWait = (totalTime*1.0) / count; cout << "Total time: " << totalTime << endl; cout << “Customer: " << count << endl; cout << "Average wait: " << avgWait << endl; |
You may be thinking that the complete picture of simulation is not visible. How will we run this simulation? Another important tool in the simulation is animation. You have seen the animation of traffic. Cars are moving and stopping on the signals. Signals are turning into red, green and yellow. You can easily understand from the animation. If the animation is combined with the simulation, it is easily understood.
We have an animated tool here that shows the animation of the events. A programmer can see the animation of the bank simulation. With the help of this animation, you can better understand the simulation.
In this animation, you can see the Entrance of the customers, four tellers, priority queue and the Exit. The customers enter the queue and as the tellers are free. They go to the teller straight. Customer C1<30, 10> enters the bank. The customer C1 enters after 30 mins and he needs 10 mins for the transaction. He goes to the teller 1. Then customer C2 enters the bank and goes to teller 2. When the transaction ends, the customer leaves the bank. When tellers are not free, customer will wait in the queue. In the event priority queue, we have different events. The entries in the priority queue are like arr, 76 (arrival event at 76 min) or q1, 80 (event in q1 at 80 min) etc. Let’s see the statistics when a customer leaves the bank. At exit, you see the customer leaving the bank as C15<68, 3><77, 3>, it means that the customer C15 enters the bank at 68 mins and requires 3 mins for his transaction. He goes to the teller 4 but the teller is not free, so the customer has to wait in the queue. He leaves the bank at 77 mins.
Implementation of Priority Queue
In the priority queue, we put the elements in the queue to get them from the queue with a priority of the elements. Following is the C++ code of the priority queue.
| #include "Event.cpp" #define PQMAX 30 class PriorityQueue { public: PriorityQueue() { size = 0; rear = -1; }; ~PriorityQueue() {}; int full(void) { return ( size == PQMAX ) ? 1 : 0; }; Event* remove() { if( size > 0 ) { Event* e = nodes[0]; for(int j=0; j < size-2; j++ ) nodes[j] = nodes[j+1]; size = size-1; rear=rear-1; if( size == 0 ) rear = -1; return e; } return (Event*)NULL; cout << "remove - queue is empty." << endl; }; int insert(Event* e) { if( !full() ) { rear = rear+1; nodes[rear] = e; size = size + 1; sortElements(); // in ascending order return 1; } cout << "insert queue is full." << endl; return 0; }; int length() { return size; }; }; |
In this code, the file Events.cpp has been included. Here we use events to store in the queue. To cater to the need of storing other data types too, we can write the PriorityQueue class as a template class.
In the above code, we declare the class PriorityQueue. Then there is the public part of the class. In the public part, at first a programmer encounters the constructor of the class. In the constructor, we assign the value 0 to size and –1 to rear variables. A destructor, whose body is empty, follows this. Later, we employ the method full() which checks the size equal to the PQMAX to see whether the queue is full. If the size is equal to PQMAX, the function returns 1 i.e. TRUE. Otherwise, it returns 0 i.e. FALSE. We are going to implement the priority queue with an array. We can also use linked list to implement the priority queue. However, in the example of simulation studied in the previous lecture, we implemented the queue by using an array. We have seen in the simulation example that there may be a maximum of five events. These events include one arrival event and four departure events. That means four queues from where the customers go to the teller and one to go out of the bank after the completion of the transaction. As we know that there is a need of only five queues, so it was decided to use the array instead of dynamic memory allocation and manipulating the pointers.
In the remove() method, there are some things which are the property of the priority queue. We don’t have these in the queue. In this method, first of all we check the size of the priority queue to see whether there is something in the queue or not. If size is greater than 0 i.e. there are items in the queue then we get the event pointer (pointer to the object Event) e from the first position (i.e. at index 0) of the array, which we are using internally to implement the queue. At the end of the method, we return this event object e. This means that we are removing the first object from the internal array. We already know that the removal of an item from the start of an array is very time consuming as we have to shift all the remaining items one position to the left. Thus the remove() method of the queue will execute slowly. We solved this problem by removing the item from the position where the front pointer is pointing. As the front and rear went ahead and we got empty spaces in the beginning, the circular array was used. Here, the remove() method is not removing the element from the front. Rather, it is removing element from the first position (i.e. index 0). Then we execute a for loop. This for loop starts from 0 and executes to size-2. We can notice that in this for loop, we are shifting the elements of the array one position left to fill the space that has been created by removing the element from the first position. Thus the element of index 1 becomes at index 0 and element of index 2 becomes at index 1 and so on. Afterwards, we decrease size and rear by 1. By decreasing the size 1 if it becomes zero, we will set rear to –1. Now by the statement
return e ;
We return the element (object e), got from the array. The outer part of the if block
return (Event*)NULL;
cout << "remove - queue is empty." << endl;
is executed if there is nothing in the queue i.e. size is less than 0. Here we return NULL pointer and display a message on the screen to show that the queue is empty.
Now let’s look at the insert() method. In this method, first of all we check whether the array (we are using internally) is full or not. In case, it is not full, we increase the value of rear by 1. Then we insert the object e in the nodes array at the position rear. Then the size is increased by 1 as we have inserted (added) one element to the queue. Now we call a method sortElements() that sorts the elements of the array in an order. We will read different algorithms of sorting later in this course.
We have said that when we remove an element from a priority queue, it is not according to the FIFO rule. We will remove elements by some other rule. In the simulation, we had decided to remove the element from the priority queue with respect to the time of occurrence of an event (arrival or departure). We will remove the element (event) whose time of occurrence is before other events. This can be understood from the example of the traffic over a bridge or crossing. We will give higher priority to an ambulance as compared to a bus. The cars will have the lower priority. Thus when a vehicle has gone across then after it we will see if there is any ambulance in the queue. If it is there, we will remove it from the queue and let go across the bridge. Afterwards, we will allow a bus to go and then the cars. In our simulation example, we put a number i.e. time of occurrence, with the object when we add it to the queue. Then after each insertion, we sort the queue with these numbers in ascending order. Thus the objects in the nodes array get into an order with respect to the time of their occurrence. After sorting, the first element in the array is the event, going to be occurring earliest in the future. Now after sorting the queue we return 1 that shows the insert operation has been successful. If the queue is full, we display a message to show that the queue is full and return 0, indicating that the insert operation had failed.
Then there comes the length() method, having a single statement i.e.
return size ;
This method returns the size of the queue, reflecting the number of elements in the queue. It is not the size of the array used internally to store the elements of the queue.
We have seen the implementation of the priority queue by using an array. We will use the priority queue in some other algorithms later. Now, we will see another implementation of the priority queue using some thing other than array, which is much better than using an array. This will be more efficient. Its remove and insert methods will be faster than the ones in array technique. Here in the simulation, we were making only five queues for the events. Suppose, if these go to hundreds or thousands, a lot of time will be spent to remove an element from the queue. Similarly, when an element is added, after adding the element, to sort the whole array will be a time consuming process. Thus the application, with the use of the priority queue, will not be more efficient with respect to the time.
No comments:
Post a Comment