POAD Beginning -2
Simulation of Waiting Queues
Simulation is a software engineering technique that is commonly used prior to actual implementation for several purposes, including verification of operations or assumptions, estimation of some statistical parameters about the application execution, checking the actual application operation for deadlocks or undesirable states, and studying the application behavior.
In this chapter we discuss the pattern-oriented development (using POAD) of a domain-specific architecture, which is used as reference architecture for the development of applications that simulate the behavior of waiting queues. In these applications we deal with customers lining up for service from one or more service stations. Practical examples for such systems include the checkout counters at supermarkets, the airline check-in counters, immigration posts at the airport, and self-serve carwash stations. The purpose of developing such simulation environments is to be able to get some measurements about systems that implement waiting-queues structures. For instance, using the simulation environment, we are able to measure the quality of service, the fairness in treating customers, efficiency in service warranty, and productivity of the service stations.
We have developed an OO design for this architecture as part of an educational experiment in software reuse [Addy et al. 1999; Mili et al. 2001]. The architecture developed in Addy, Mili, and Yacoub's "A Case Study in Software Reuse" (1999) is not based on design patterns. In this chapter we describe how to use POAD to develop an equivalent pattern-oriented design for the reference architecture. We show how the domain architecture can be constructed using constructional design patterns as its building blocks. First, we explain the domain and application requirements, and then we follow the POAD steps to create a pattern-oriented design for the waiting-queues simulator.
Background and Requirements
The focus of this case study is the domain of waiting-queue simulation. This is a more tightly scoped version of the general domain of discrete-event simulation. Other examples that fall under the general discrete-event simulation domain include communications systems such as telephone networks, where we deal with simulation of network nodes, distribution, packet delays, and other issues. Discrete-event systems also include traffic systems and manufacturing processes. For the purposes of this case study, we limit the discussion to servers, queues, and customers lining up for service.
Domain Engineering
The case study involves developing a domain-specific design for the purpose of producing applications that simulate the behavior of waiting queues. There are several degrees of variances that should be accommodated in the design:
· Topology of service stations. The number of service stations may be fixed or variable (in time). We may have one or more service station. If we have more than one service station, the service stations may be interchangeable (they deliver the same service) or not (e.g., checkout counters for 10 items or less, checkout counters for more than 10 items, etc.).
· Service time. The service time may be constant or variable. If it is variable, it may be determined by the customer, by the service station, or by both (e.g., customer determines amount of service needed, and service station prorates that with its own productivity factor). Also, if it is variable, it may be subject to a maximum service value (as is the case in CPU dispatching algorithms); when the maximum is reached, the customer may be dispatched out, queued at the end of the queue where it was, or considered a new arrival.
· Topology of queues. We may have a single queue, multiple interchangeable queues, or multiple queues with different service categories (each customer may line up at queues of a given category).
· Typology of queues. Queues could be first in, first out (FIFO) queues; last in, first out (LIFO) queues (stacks); priority queues; or limited size queues. Some applications (e.g., checkout counters) where customers may leave the waiting queue either in the order of their arrival (to receive service) or in reverse order (to change queues).
· Arrival distribution. Customers arrive to the system at various rates. The distribution of the customer arrivals in time could be Markovian distribution, Poisson distribution, or clustered distribution (if the service stations are immigration posts at an airport, then passenger arrivals are clustered around after flight arrivals).
· Dispatching policy. Customers are assigned to queues at random and may not change queues after the first assignment. Other policies might be that customers are assigned to the shortest queue upon arrival and may not subsequently change queues, or customers are assigned to the shortest queue upon arrival and subsequently switch queues to take the shortest until they are served.
· Measurements. As a result of the simulation, we are interested in obtaining one or more of the following measurements: the average waiting time (as a measure of quality of service); the standard deviation of waiting time (as a measure of fairness); the maximum waiting time (as a measure of service warranty); and the throughput (as a measure of productivity).
Application Engineering
In order to exercise the domain engineering activity that is carried out according to the requirements discussed above, the domain architecture, design, and components should be easily instantiable in a set of software applications that are all instances of the queue simulation domain. Examples of such applications include the following:
1. CPU dispatching. Simulation of the behavior of a CPU dispatching mechanism. In this application we measure fairness and throughput. There is a single priority queue with maximum service time (quantum service, Q); once a process has exhausted its service time, it is queued back with an increased priority.
2. Self-serve car wash. In this application we have a set of self-serve interchangeable car wash stations. Arriving cars line up at the shortest queue (queues of equal length are interchangeable) and do not subsequently change queues; queues are FIFO. Service is limited to a maximum value (but may take less time), and cars are expected to clear the station once the maximum time has expired. Arrival distribution could be, for instance, Markovian distribution. We are interested in monitoring maximum waiting time (we don't want anybody to leave before being served) and throughput (we want to serve as many people as possible).
3. Checkout counters. We have a number of checkout counters at a supermarket, some of which are reserved for shoppers with 10 items or less. Shoppers with 10 items or less line up in the shortest express checkout queue; others line up in the shortest queue reserved for them. Once they are lined up in some queue, shoppers do not leave the queue until it is their turn. Service time is determined by the shopper and by the productivity of the cash register attendant. Arrival rate is Markovian distribution. The number of stations increases whenever the longest queue exceeds a threshold value L and decreases by one whenever the number of stations of each category is greater than one and the length of the queue is zero. Whenever a new cash register is opened, shoppers at the end of the queue rush to line up at the station until the length of the queue equals the shortest current queue of the same type (express checkout, regular checkout). We are interested in average waiting time and fairness.
4. Immigration posts. We have a number of immigration stations at an airport, some of which are reserved for nationals; the others are for foreign citizens. There are two queues: one for nationals, the other for foreigners; each queue feeds into the corresponding set of stations, and there is no transfer between queues. The number of stations that handle nationals increases by one whenever the length of the nationals' queue exceeds some value, and the number of stations that handle foreigners increases by one whenever the length of the foreigners' queue exceeds some other value. The arrival rate is a clustered distribution, as passengers come by planeloads. Service time for nationals is constant, and service time for foreigners is determined by the passenger and by the productivity of the immigration agent attendant. We are interested in monitoring throughput.
5. Check-in counters. We have two FIFO queues for passengers at an airline check-in station: a queue for first class and a queue for coach. We have two categories of service stations: first class and coach; the number of stations does not change for the length of the experiment. The duration of the service is the same for all passengers and all stations of the same class, but differs from first class to coach. Passengers line up at their designated queue and do not leave it until they are served. Whenever one queue is empty, the corresponding service stations may serve passengers of the other queue (typically, first class stations serve coach passengers when no first-class passengers are awaiting). We are interested in monitoring the average waiting time and the maximum waiting time for each class of passengers.
Additional sets of applications that are considered in the same domain can be found in "A Case Study in Software Reuse" [Addy et al. 1999].
POAD Analysis for the Waiting-Queues Simulation Architecture
Requirements Analysis
Based on the above requirements, we find that the architecture we are developing is specific for simulation. Simulation architectures are often centered around a dynamic event list as the communication vehicle between cooperating components. To reduce interdependency between components, an event-trigger architecture is usually selected. An essential activity of an event-driven environment is identifying possible events, their initiator, and their processing destinations. The simulation advances event by event on a time axis and gathers relevant statistics. Event is one key abstraction in the simulation architecture. The domain analysis identifies a set of events that depict all actions necessary for the execution of the simulation along with the components that generate the event and the components that take action accordingly. Therefore, an event management component is needed to orchestrate the execution and communication of events.
In addition to the event management conceptual component, we can identify several other components from the requirements. For example, any of these simulation applications is used to simulate waiting queues; therefore, the concept of one or more waiting queues should be captured in a conceptual component by itself.
In these simulation applications, customers and their attributes are generated according to some specific arrival distributions. The generation of customers and their attributes could also be captured in another component.
Customers generated by a customer generator component and waiting in one of the queues will eventually be served by some service unit. The attributes and number of the service units will vary from one simulation application to another; however, the concept of a service unit should be captured by a conceptual component by itself.
In the following we summarize the conceptual components that we identify and their responsibilities. Since the size of the application seems manageable at the requirement analysis phase, we will not use any grouping mechanisms (such as subsystems or packages).
· Customer generator. The customer generator component uses one of the distribution functions designated in the domain description to generate the time of arrival of the next customer. Appropriate distributions are used to generate other characteristics of the customer, such as the number of service units (or service time) needed, the type of the customer, and information on the service received. The generation of customer is placed as an event and is introduced to the event management component. The distribution function that determines the time of the next customer arrival varies according to applications, as well as the generation of application-specific attributes for the customer such as the service time needed and the category of service.
· Queue facility. The queue facility component consists of a set of queue categories, where each queue category contains one or more queues. Queue categories are used to capture the different types of queues, such as express or normal queues. The queues are identifiable such that the servers can identify the queue that holds customers for them. Any event that indicates an action for a queue category or a queue is delegated to the queue facility, which passes the event to the appropriate queue category. The queue category delegates events to the appropriate queue.
· Service facility. The service facility component consists of a set of service categories, where each service category contains one or more servers. Service categories are used to capture the different types of servers such as business or economy classes of service. The servers are identifiable and should be attached to one or more queues that they serve. Any event that indicates an action for a service category or a server is delegated to the service facility and in turn passes the event to the server category and to the specified server as appropriate.
· Event manager. The event manager component serves as the main driver for the simulation. We refer to it as the simulation driver or scheduler. It repeatedly processes events and delegates the actions to one or more components. The schedule manager is the most domain-specific of all the reusable components. At the end of the simulation, the schedule manager calculates the metrics for the simulation run and prints a final report. It records the information contained within a customer each time a customer completes its number of service units in a server. It calculates the averages and totals specified in the domain engineering description.
As a result of the requirements analysis activity, we have identified the need for the following conceptual components: a service facility, a queuing facility, a customer generator, and an event manager.
Acquaintance and Retrieval
In POAD, the analyst should consider off-the-shelf design pattern libraries. The analyst browses existing pattern databases for solution fragments (patterns) to use in developing the overall application design. The simulation application domain is a reactive system in which components react to event and generate other events. Therefore, the analyst may want to get acquainted with design patterns for reactive systems, such as those in the works of Schmidt and colleagues (1995b, 1998, 2000). For a list of design patterns that fall under the reactive and real-time system categories, refer to Linda Rising's The Pattern Almanac (2000, pp. xxxix).
Since the simulation architecture is heavily based on queues, we might also want to consider the patterns for designing interactive applications using queues [Wake et al. 1996]. The Event Queue pattern in this pattern collection illustrates common ways of designing the event object to be used in the simulation.
In addition to patterns for reactive systems, we also consider general-purpose design patterns, since some of the problems we are solving are general design problems. For instance, consider the service facility component, which is composed of service categories, which in turn are also composed of server units. This composition and hierarchy could be addressed by general-purpose design patterns that address composition and hierarchy [e.g., Gamma et al. 1995; Buschmann et al. 1996].
Pattern Selection
Based on the responsibilities and functionalities assigned to each conceptual component, we identify and select patterns that could provide solutions to implement these responsibilities.
The Queue Facility component is composed of a set of queue categories, and each queue category is composed of one or more queues. This composite and hierarchical structure is common to many software designs; therefore, we search for a general-purpose design pattern that implements a hierarchical and composite design. We select the Composite pattern [Gamma et al. 1995, pp. 163] to be used in implementing the composite design of the queue facility. The Composite pattern "composes objects into tree structures to represent part-whole hierarchies."
The Service Facility component is composed of a set of service categories, and each service category is composed of one or more servers. Similar to the design of the queue facility, this server composition and hierarchical structure is common to many software designs. We select another Composite pattern to be used in implementing the composite design of the service facility.
In the Customer Generator component, we use a distribution function to generate the next customer to arrive together with the simulation attributes for that customer, such as its type and its service request. Since this common architecture will be instantiated in many waiting-queues simulation applications, the generation of customer should be kept flexible to allow applications to hook in specific generation strategies. There are several patterns that can be used to implement this flexible strategy for customer generation; for instance, we can use the Strategy pattern or the TemplateMethod pattern. For this case study, we select the TemplateMethod pattern [Gamma et al. 1995, pp. 325] as an interface for generating customers. The TemplateMethod pattern defines the skeleton of an algorithm (in our case study the steps required to generate a customer and the associated parameters) and defers the implementation of each step of the algorithms to subclasses without changing the algorithm structure as sequence of steps.
The Event Manager (also called Scheduler) component plays the role of demultiplexing and dispatching of events. It receives events, identifies the appropriate event handler, and dispatches the event to the selected handler. Handling events is a domain-specific function that is related to reactive, distributed, and event-driven systems. In searching for domain-specific libraries of patterns for reactive and event-driven systems, we select the Reactor pattern to implement the design of the Event Manager. The Reactor pattern supports the "de-multiplexing and dispatching of events to multiple event handlers triggered concurrently by multiple events, and simplify event-driven applications by integrating the de-multiplexing of events and the dispatching of the corresponding event handler" [Schmidt 1995b].
In the analysis phase, we have selected a set of patterns that fulfils the responsibilities identified for each conceptual component. In choosing these patterns, we considered how the pattern solves the design problem. In summary, a Composite pattern is selected for the Service Facility component, another Composite pattern is selected for the Queue Facility, a TemplateMethod pattern is selected for the generation of customers, and the Reactor pattern is selected to implement the Event Manager.
POAD Design for the Waiting-Queues Simulation Architecture
Constructing Pattern-Level Diagrams
In this step, we create instances of the selected patterns and identify the relationships between these instances. As a result, a pattern-level logical view of the system is developed.
First, we create pattern instances. In the analysis phase, we selected the Composite pattern to design the queue facility. Therefore, we use the pattern instance name QueuingFacility of type Composite to implement the queue facility. Similarly, we selected the Composite pattern to design the service facility. Therefore, we use the pattern instance name ServiceFacility of type Composite to implement the service facility. We have also selected the TemplateMethod pattern to implement the design for the customer generator. We use the pattern instance name Generator of type TemplateMethod pattern to implement customer generation. We also selected the Reactor pattern to implement the design of the event management components. Therefore, we use the pattern instance name Scheduler of type Reactor pattern to implement the event list and the events scheduling and dispatching. As a result, the Pattern-Level diagram will contain four pattern instances: QueuingFacility, ServiceFacility of type Composite; Generator of type TemplateMethod; and Scheduler of type Reactor.
Second, we define the dependency relationship between the pattern instances. The Scheduler dispatches events to the ServiceFacility and the QueuingFacility to handle relevant events accordingly. In turn, ServiceFacility and QueuingFacility use the Scheduler to schedule new events generated in the course of their processing. The Scheduler uses the Generator to generate new customer arrivals. Finally, we use the pattern instances and their relationships to construct the Pattern-Level diagram, as shown in Figure 12-1.
Figure 12-1. A Pattern-Level diagram for the waiting-queues simulator architecture.
The product of this step is the Pattern-Level diagram of the simulation architecture. It describes the architecture of a waiting-queues simulator using design patterns. This diagram could be revisited at a later phase to iterate on the decisions that we made (as part of an iterative development lifecycle). For instance, the designer might want to emphasize the event object in the Pattern-Level diagram, so the analyst would consider using the EventQueue pattern [Wake et al. 1996] to represent the event object. In this case, another package will be used in Figure 12-1 to represent the EventQueue pattern together with the possible pattern dependencies with the Scheduler pattern instance or other patterns.
Constructing Pattern-Level with Interfaces Diagrams
In this step, we analyze the relationships between pattern instances. The dependency relationship between patterns in the pattern-level view is a conceptual, high-level dependency relationship. We further trace these dependencies to lower-level design.
First, we declare interfaces for the patterns used in the Pattern-Level diagram. The interface of a Composite pattern is the Component class by which its constituting elements, whether simple (leaf child) or composite (parent), interface to other components. Therefore, each of the two pattern instances ServiceFacility and QueuingFacility will have the interface Component. The Reactor pattern has two types of interfaces: the EventHandler interface class for delegating the processing of events to other classes and the Dispatch() interface operation for receiving and scheduling events. The interface of a TemplateMethod pattern is TemplateMethod() of the class AbstractClass, which contains the skeleton of the customer-generation steps implemented by concrete subclasses according to various customer-generation policies.
Then, we identify the relationship between pattern interfaces by translating all dependency relationships between patterns in a Pattern-Level diagram of Figure 12-1 into relationships between interface classes and/or interfaces operations. The Component interface class of the ServiceFacility and the QueuingFacility pattern instances has a relationship with the Dispatch() interface operation of the Scheduler pattern instance to schedule the processing of events. The EventHandler interface class of the Scheduler pattern instance has a dependency relationship with the Component interface classes of the ServiceFacility and the QueuingFacility pattern instances to handle the processing of events. The Dispatch() interface operation of the Scheduler pattern instance has a dependency relationship with the TemplateMethod() interface operation of the Generator pattern instance. The product of this process is the Pattern-Level with Interfaces diagram. Figure 12-2 illustrates the Pattern-Level with Interface diagram for the simulation architecture.
Figure 12-2. A Pattern-Level with Interfaces diagram for the waiting-queues simulator.
Constructing Detailed Pattern-Level Diagrams
To construct the Detailed Pattern-Level diagram, we express the internal parts of each instantiated pattern from the Pattern-Level with Interfaces diagram. Since we use pervasive design patterns in developing the Pattern-Level diagram, their structure can be found in the literature [Gamma et al. 1995; Schmidt 1995b]. Figure 12-3 illustrates the Detailed Pattern-Level diagram.
Figure 12-3. A Detailed Pattern-Level diagram for waiting-queues simulator.
Note that we do not make any additional design decisions in this step. With the appropriate tool support, Figure 12-3 is a direct generation from the Pattern-Level with Interfaces diagram by simply retrieving the internal class diagram model for each pattern from a pattern database.
POAD Design Refinement for the Waiting-Queues Simulation Architecture
Instantiating Pattern Internals
In this step, we add application-specific nature to the Detailed Pattern-Level diagram by renaming internal pattern classes according to the application design environment, choosing names for pattern participants that are meaningful in the application context, and defining application-specific names for operations in patterns.
Instantiating the internals of the ServiceFacility is illustrated in Figure 12-4. The ServiceFacility pattern instance is composed of
· ServiceComponent. A ServiceComponent is an abstract interface for all service elements. A service element can be a Server, a ServiceCategory, or the whole ServiceFacility. It defines the method signatures for serving a customer (Serve()) and completion of the service (ServiceComplete()), which are the Operation() methods in the abstract definition of the Composite pattern. The Add() and Remove() operations in the abstract Composite pattern definitions are now renamed into application-specific methods: the AddServer() and RemoveServer() methods. Methods are implemented in concrete subclasses according to the type of the service component.
· Server. The actual service station that serves a customer. The Server class implements the methods of the abstract class ServiceElement. It contains attributes related to the productivity of the server, its status, and maximum service time. The Server class is the leaf node that does not contain any other service elements.
· ServiceCategory. A ServiceCategory class is a composition of Server classes that are of the same category. The type of the server category depends on the application implementing the simulation architecture. The ServiceCategory contains attributes defining the category and the number of servers. It implements the methods related to adding a server to its pool of servers.
· ServiceFacility. The manager of the whole service station and categories. It is composed of several service categories, each of which is composed of a number of servers. It has attributes defining the number and type of service categories that the facility contains. In each application there will usually be one ServiceFacility that contains the rest of the service elements. It implements the interfaces to add other service components, such as other servers or other service categories.
Figure 12-4. Instantiating the ServiceFacility pattern.
Instantiating the internals of the QueuingFacility is illustrated in Figure 12-5. The QueuingFacility pattern instance is composed of
· QueuingComponent. An abstract interface for all queuing elements. A QueueingElement can be a Queue, a QueueCategory, or the whole QueueFacility. It defines the interface for queuing (Enqueue()) and dequeuing (Dequeue()) a customer, which are the Operation() methods in the abstract definition of the Composite pattern. The Add() and Remove() operations in the abstract Composite pattern definitions are now renamed into application-specific methods: the AddQueuingElem() and RemoveQueuingElem() methods. Methods are implemented in concrete subclasses according to the type of the queuing component.
· Queue. The actual queue that holds a customer. The Queue class implements the methods of the abstract class QueuingElement. It contains attributes related to the size of queue and its type. The Queue class can be further subclassed to implement different types of queues such as FIFO, LIFO, or priority queues.
· QueueCategory. A composition of queues that are of the same category. It contains attributes defining the category and number queues in this category. The type of the queue category depends on the application implementing the simulation architecture. The QueueCategory class implements the methods related to adding a queue to its pool of queues.
· QueueFacility. The manager of the whole queuing system. It is composed of several queue categories, each of which is composed of number of queues. It has attributes defining the number and type of queue categories that the facility contains. In each application there will usually be one QueueFacility that contains the rest of the queuing elements. It implements the interfaces to add other queue components such as other queues or other queue categories.
Figure 12-5. Instantiating the QueuingFacility pattern.
Instantiating the internals of the Scheduler is illustrated in Figure 12-6. The Scheduler pattern instance is composed of
· EventList. The Reactor class in the Reactor pattern is renamed to EventList. The EventList is the main component of the scheduler that holds a repository of all events that occur in the system. Events in the EventList are time ordered. The EventList supports scheduling of new events and dispatching events to be processed to the appropriate event handler. There are several other attributes and methods of the EventList that are not shown in the diagram for simplicity. Moreover, we are only interested at this level in design elements that are crucial for integration with elements of other patterns.
· EventHandler. An EventHandler is an abstract interface to all possible concrete event handlers that can process and handle events. It defines interfaces to query the status of the handler, initiate the handling of events, or terminate the handling of events.
· ConcreteEventHandler. A ConcreteEventHandler class is the concrete implementation of the EventHandler interface. In this waiting-queues simulation architecture, the concrete event handlers are those handlers that handle simulation events, which are the two interfaces QueuingComponent and ServiceComponent.
Figure 12-6. Instantiating the Scheduler pattern.
Instantiating the internals of the Generator is illustrated in Figure 12-7. The Generator pattern instance is composed of
· AbstractGenerator.AbstractGenerator is the interface class that defines the steps for generating a customer arrival event. The TemplateMethod() in the abstract TemplateMethod pattern is renamed to GenerateArrival(). The GenerateArrival() method is the template method that defines the procedures for generating a customer-arrival event object. GenerateArrival() method delegates the generation of specific customer attributes to concrete classes by calling abstract methods, which are implemented in subclasses such as ArrivalTimePolicy(), ArrivalCategoryPolicy(), and ServiceUnitsPolicy().
· RandomArrival and MarkovianArrivals. These are concrete implementations of the arrival policies. They provide several concrete implementations of the arrival generator based on an arrival policy and variations in the techniques used to generate the customer attributes.
Figure 12-7. Instantiating the Generator pattern.
Developing an Initial Class Diagram
Starting from the Detailed Pattern-Level diagram in Figure 12-3, we use pattern interfaces and the instantiated details of pattern internals to construct a UML class diagram. This is a simple process of combining the domain-specific details with the Detailed Pattern-Level diagram. The class diagram developed at this phase is an initial step to develop the static design model of the pattern-oriented architecture for the waiting queues simulation applications. In this step we convert relationships between pattern interfaces in the Detailed Pattern-Level to relationships between internal classes of instantiated patterns.
First, we convert the class/class relationship between pattern interfaces by tracing each of the two class interfaces to the internal classes of the pattern instances. For example, Figure 12-8(a) is taken from Figure 12-3 to illustrate the class/class relationship between the EventHandler interface class of the Scheduler pattern instance of type Reactor and the Component interface class of the ServiceFacility pattern instance of type Composite. Figure 12-8(b) illustrates the same relationship after instantiating the internal details of each of the two patterns which has now become a relationship between the two interface classes EventHandler and ServiceComponent (after renaming the internal details of the two patterns). We then translate this relationship into UML class association relationships between internal classes of both patterns. The EventHandler interface is traced inside the instantiated Scheduler to the internal class EventHandler, and the ServiceComponent interface class is traced inside the instantiated ServiceFacility to the ServiceComponent class. Hence, a UML class association relationship is established between the class EventHandler and the class ServiceComponent, as shown in Figure 12-8(c).
Figure 12-8. Converting the class/class pattern interface relationship into UML class association.
Similarly, we convert the class/class relationship between the EventHandler interface class of the Scheduler pattern instance of type Reactor and the Component interface class of the QueuingFacility pattern instance of type Composite. As a result, a UML class association relationship is established between the class EventHandler of the Scheduler pattern instance and the class QueuingComponent of the Queuing Facility pattern instance.
Second, we convert the operation/class relationship between pattern interfaces by tracing each interface operation to the internal pattern class that implements the operation. The interface class is also traced to the pattern's internal class, and hence a class relationship is established between internal classes of the two interfacing patterns. For example, Figure 12-9(a) is taken from Figure 12-3 to illustrate the operation/class relationship between the Dispatch() interface operation of the Scheduler pattern instance of type Reactor and the Component interface class of the ServiceFacility pattern instance of type Composite. Figure 12-9(b) illustrates the same relationship after instantiating the internal details of each of the two patterns, which has now become a relationship between the interface operation Dispatch()and the interface class ServiceComponent (after renaming the internal details of the two patterns). We then translate this relationship into UML class association relationships between internal classes of both patterns. The Dispatch() interface operation is traced inside the instantiated Scheduler to the internal class EventList, and the ServiceComponent interface class is traced inside the instantiated ServiceFacility to the ServiceComponent class. Hence, a UML class association relationship is established between the class ServiceComponent and the class EventList, as shown in Figure 12-9(c).
Figure 12-9. Converting the operation/class pattern interface relationship into UML class association.
Third, we convert the operation/operation relationship by tracing each interface operation to the internal class of the pattern. These internal classes of the two interfacing patterns will have a class association relationship. For example, Figure 12-10(a) is taken from Figure 12-3 to illustrate the operation/operation relationship between the Dispatch() interface operation of the Scheduler pattern instance of type Reactor and the TemplateMethod() interface operation of the Generator pattern instance of type TemplateMethod. Figure 12-10(b) illustrates the same relationship after instantiating the internal details of each of the two patterns, as discussed in section 12.4.1, which has now become a relationship between the interface operation Dispatch()and the interface operation GenerateArrival() (after renaming the internal details of the two patterns). We then translate this relationship into UML class association relationships between internal classes of both patterns. The Dispatch() interface operation is traced inside the instantiated Scheduler to the internal class EventList, and the GenerateArrival() interface operation is traced inside the instantiated Generator to the AbstractGenerator class. Hence, a UML class association relationship is established between the class AbstractGenerator and the class EventList, as shown in Figure 12-10(c).
Figure 12-10. Converting the operation/operation pattern interface relationship into UML class association.
As a result, the design is now viewed as a UML class diagram, as shown in Figure 12-11. The class diagram that is produced is an initial step to develop the static design model of the simulator.
Figure 12-11. The initial class diagram for the waiting queues simulator.
It can be easily recognized that the patterns are still notable in the class diagram as shown by the dotted boxes around the classes. We recall that we do not discard earlier diagrams. As part of POAD, all the models in figures 12-1 through 12-11 are saved as analysis and design models. It is the role of a tool support to save these models and provide the necessary traceability mechanisms between them.
How About Code Generation?
In the above process, we do not generate code at each level and keep it in synchronization with other levels. The process is mostly about manipulating the design elements (patterns, classes, methods, etc.) at that analysis and design level. Code generation comes later, after the refined design is complete. It is also unnecessary to generate code from the initial class diagram, because in the following phases the designer will change the design of the system by merging and grouping several classes together. So, if you are eager to see code samples, wait until you have completed the following phase.
Design Optimization
The class diagram obtained from gluing patterns together at the high-level design may not be dense or profound because we just strung the patterns together. It could possibly have replicated abstract classes due to the fact that we use multiple instances of the same pattern type. For example, we used the ServiceFacility and the QueuingFacility instances of type Composite pattern. The design could also have some classes with trivial responsibilities because these classes are there in the design to forward messages to internal participants of the pattern. Therefore, in this step we use reduction and grouping mechanisms to optimize the UML design diagrams obtained in the previous step.
The design obtained in Figure 12-11 can be further refined using reduction or grouping. Let's consider first the possibility of reduction by removing replicated abstract classes. The Composite pattern is instantiated twice, once for the ServiceFacility and again for the QueuingFacility. The Composite pattern has an abstract class Component, which could have two occurrences because we use two instances of the same pattern type Composite. However, for this application, the two Component classes—ServiceComponent and QueuingComponent—of the two pattern instances cannot be merged together because the interfaces offered by the two abstract classes differ from being a service component to a queuing component; hence, we cannot merge these two abstract classes into one class.
Next, we consider the possibility of optimizing the design by merging classes with trivial responsibilities. The EventHandler class of the Scheduler pattern instance is the interface for the concrete event handlers that handle specific events. In this application, the event handlers are either the QueuingFacility pattern instance or the ServiceFacility pattern instance. The two abstract classes ServiceComponent and QueuingComponent can play the role of event handlers, and hence the EventHandler class and the ConcreteEventHandlers can be replaced by the two classes ServiceComponent and QueuingComponent. Events are dispatched from the EventList to either of the two classes such that the HandleEvent() method is an actual domain-specific method, such as Serve() or ServiceComplete() methods in the ServiceComponent class and Enqueue() or Dequeue() methods in the QueuingComponent class. As another design alternative, the designer might want to keep the EventHandler interface explicit; hence, the EventHandler class becomes the interface class that the two classes ServiceComponent and QueuingComponent implement. In the following design diagrams, we use the first design (replace the EventHandler classes with the ServiceComponent and QueuingComponent classes) to reduce the inheritance hierarchy.
We can further refine the design by using a SimulatorDriver class that continuously retrieves events from the EventList and delegates its processing to the appropriate component. In this case, the EventList is considered a passive, time-ordered list. It provides two methods: getNextEvent() to get the top element of the timely ordered list and Dispatch(), which is used by a ServiceElement or a QueuingElement to schedule an event in the list. The refined class diagram is shown in Figure 12-12.
Figure 12-12. The refined class diagram for the waiting queues simulator.
As mentioned in Chapter 9, it could become difficult to identify the patterns at this level because the design is now represented in terms of domain-specific classes. This problem has always existed in many techniques that use patterns directly at the class diagram level without developing higher-level design models. POAD has one particular advantage. When applying POAD, the designer keeps all the models developed throughout the development lifecycle. These models are traceable bottom-up from the class level (Figure 12-12) to the pattern level (figure 12-1) and top-down from the pattern level to the class level. With the appropriate tools, this traceability can be automated in a design environment.
As an example of top-down traceability, the Reactor pattern in Figure 12-1 is traced to the classes EventList (as a Reactor), ServiceComponent (as an Event-Handler), and QueuingComponent (as an EventHandler) in Figure 12-12.
As an example of a bottom-up traceability, the QueuingComponent in Figure 12-12 is traced up to be the Component of the QueuingFacility pattern instance and the EventHandler of the Scheduler pattern instance in Figure 12-1.
Sample Implementation
The final class diagram from Figure 12-12 can be instantiated in many applications that simulate the behavior of waiting queues. This section gives the reader the complete model and sample code in Java for an application that utilizes the above framework in simulating the behavior of check-in waiting queues in airports. We will use one queue and one server for business-class service and one queue and one server for coach-class service. The instantiated model for the application is illustrated in Figure 12-13 and the Java implementation follows.
[View full width]
/************************************
*
* SimulatorDriver.java
*
***********************************/
package WaitingQueue;
public class SimulatorDriver
{
protected EventList eventlist;
protected AbstractGenerator customerGen;
protected Measurement TheMeasurement;
public SimulatorDriver()
{
eventlist = EventList.getInstance();
TheMeasurement = Measurement.getInstance();
customerGen = new RandomArrivals();
}
public void runSimulation()
{
// Create the application by:
// 1) Instantiating the domain components
// 2) Establishing the relationship between components
// Create basic components: ServiceFacility, QueueFacility
QueueFacility q_facility = new QueueFacility (2 /*Maximum Number of Queue
Categories in the Facility*/ );
ServiceFacility s_facility = new ServiceFacility(2 /*Maximum Number of Service
Categories in the Facility*/);
// Create Service Categories and add them to the service facility
s_facility.addServiceCategory(1 /*MaximumNum of Servers in this Category*/,
AllowedCategoriesEnum.COACH);
s_facility.addServiceCategory(1 /*MaximumNum of Servers in this Category*/,
AllowedCategoriesEnum.BUSINESS);
// Create Queue Categories and add them to the queuing facility
q_facility.addQueueCategory (AllowedCategoriesEnum.COACH , false /*Non
REORDABLE*/);
q_facility.addQueueCategory (AllowedCategoriesEnum.BUSINESS, false /*Non
REORDABLE*/);
// Add queues to the queuing facility; one queue for COAH and one for BUSINESS
int TheQueueID_1 = q_facility.addQueue (AllowedCategoriesEnum.COACH);
int TheQueueID_2 = q_facility.addQueue (AllowedCategoriesEnum.BUSINESS);
// Add servers to the service facility;
// one server for COACH and one for BUSINESS
s_facility.addServer(AllowedCategoriesEnum.COACH , 1 /* Productivity*/, 30 /
*Maximum Service Time*/, TheQueueID_1 );
s_facility.addServer(AllowedCategoriesEnum.BUSINESS, 1 /* Productivity*/, 30 /
*Maximum Service Time*/, TheQueueID_2 );;
// Initialization:
Event firstevent = new Event();
firstevent.Type = EventTypeEnum.ARRIVAL;
firstevent.EventTime = 0; // Initially at zero time
firstevent.Category = AllowedCategoriesEnum.COACH;
Customer aCustomer = new Customer(0 /*ArrivalTime*/, 5 /*SerivceUnits*/,
AllowedCategoriesEnum.COACH/*Category*/);
firstevent.CarriedCustomer = aCustomer;
eventlist.Dispatch(firstevent);
// Initialize a simulation period
long TotalSimulationTime = 100;
// Run the simulation
// 1. Dispatch an event from the eventlist
// 2. Increment the simulation time to the event time.
// 3. Call the simulate function of the node specified in
// the event body.
// 4. Repeat from step 1 unless the simulation time is over.
Event sim_event;
while(true)
{
sim_event = eventlist.GetNextEvent();
if(sim_event.EventTime > TotalSimulationTime )
break;
// Simulate the event according to the event type.
if(sim_event.Type == EventTypeEnum.ARRIVAL)
{ //Generate another ARRIVAL
aCustomer = new Customer(0,0,AllowedCategoriesEnum.COACH);
customerGen.generateArrival(sim_event.EventTime, aCustomer);
q_facility.Enqueue(sim_event.CarriedCustomer);
}
if(sim_event.Type == EventTypeEnum.SERVE)
{
s_facility.serve(sim_event.CarriedCustomer, sim_event.EventTime, sim_event.
ServerID, sim_event.Category);
}
if(sim_event.Type == EventTypeEnum.DEQUEUE)
{
q_facility.Dequeue (sim_event.Category, sim_event.FromQueueID, sim_event.
EventTime,sim_event.ServerID);
}
if(sim_event.Type == EventTypeEnum.SERVICE_COMPLETE)
{
s_facility.serviceComplete(sim_event.EventTime, sim_event.ServerID,sim_event.
Category);
}
if(sim_event.Type == EventTypeEnum.CHECK_SERVER)
{
s_facility.checkServer(sim_event.EventTime, sim_event.FromQueueID, sim_event.
Category);
}
if(sim_event.Type == EventTypeEnum.REORDER)
{
q_facility.ReorderCategory(sim_event.Category);
}
}
// Print Statistics
System.out.println("Number of Customers Served : " + TheMeasurement.NumCustomers + ""
n");
System.out.println("Average Waiting Time : " + TheMeasurement.
AverageWaitingTime() + ""n");
System.out.println("Maximum Waiting Time: " + TheMeasurement.MaxWaitingTime() + ""n");
System.out.println("Standard Deviation of Waiting Time : " + TheMeasurement.
StdWaitingTime() + ""n");
System.out.println("Throughput : " + (float)((float)TheMeasurement.
NumCustomers/(float)TotalSimulationTime) + ""n");
}
public static void main(String[] argc)
{
SimulatorDriver aSimulator = new SimulatorDriver();
aSimulator.runSimulation();
}
}
/************************************
*
* ServiceComponent.java
*
***********************************/
package WaitingQueue;
public class ServiceComponent
{
public void addServiceCategory(int maxNumberOfServers, AllowedCategoriesEnum
aCategory){}
public void removeServiceCategory(AllowedCategoriesEnum aCategory) {}
public void addServer(AllowedCategoriesEnum aCategory, float productivity, long
maxServiceTime, int queueID) {}
public void removeServer(AllowedCategoriesEnum aCategory, int queueID) {}
public void serve(Customer aCustomer, long currentTime, int serverID,
AllowedCategoriesEnum aCategory) {}
public void serviceComplete(long currentTime, int serverID, AllowedCategoriesEnum
aCategory) {}
public void checkServer(long currentTime, int fromQueueID, AllowedCategoriesEnum
aCategory) {}
public ServiceComponent() {}
}
/************************************
*
* ServiceFacility.java
*
***********************************/
package WaitingQueue;
public class ServiceFacility extends ServiceComponent
{
protected ServiceComponent serviceCategories[];
protected int MaxNumCategories;
protected int NumCategories;
public ServiceFacility(int _MaxNumCategories)
{
MaxNumCategories = _MaxNumCategories;
serviceCategories = new ServiceCategory[MaxNumCategories];
NumCategories = 0 ;
}
public void addServiceCategory(int maxNumberOfServers, AllowedCategoriesEnum aCategory)
{
if(NumCategories < MaxNumCategories)
{
serviceCategories[NumCategories] = new ServiceCategory(maxNumberOfServers,
aCategory);
NumCategories++;
}
}
public void addServer(AllowedCategoriesEnum aCategory, float productivity, long
maxServiceTime, int queueID)
{
int i=0;
for(i=0;i<NumCategories;i++)
if(((ServiceCategory) serviceCategories[i]).GetCategory() == aCategory)
{ ((ServiceCategory) serviceCategories[i]).addServer(aCategory, productivity,
maxServiceTime, queueID);
break;
}
}
public void removeServer(AllowedCategoriesEnum aCategory, int queueID) {}
public void serve(Customer aCustomer, long currentTime, int serverID,
AllowedCategoriesEnum aCategory)
{
int i=0;
for(i=0;i<NumCategories;i++)
if(((ServiceCategory) serviceCategories[i]).GetCategory() == aCategory)
{((ServiceCategory) serviceCategories[i]).serve(aCustomer, currentTime,
serverID, aCategory);
break;
}
}
public void serviceComplete(long currentTime, int serverID, AllowedCategoriesEnum
aCategory)
{
int i=0;
for(i=0;i<NumCategories;i++)
if(((ServiceCategory) serviceCategories[i]).GetCategory() == aCategory)
{ ((ServiceCategory) serviceCategories[i]).serviceComplete (currentTime,
serverID, aCategory);
break;
}
}
public void checkServer(long currentTime, int fromQueueID, AllowedCategoriesEnum
aCategory)
{
int i=0;
for(i=0;i<NumCategories;i++)
if(((ServiceCategory) serviceCategories[i]).GetCategory() == aCategory)
{ ((ServiceCategory) serviceCategories[i]).checkServer (currentTime,
fromQueueID,aCategory);
break;
}
}
}
/************************************
*
* ServiceCategory.java
*
***********************************/
package WaitingQueue;
public class ServiceCategory extends ServiceComponent
{
protected EventList eventlist;
protected ServiceComponent servers[];
protected int MaxNumServers;
protected int NumServers;
protected int ServerIDs;
protected AllowedCategoriesEnum Category;
public ServiceCategory(int _MaxNumServers, AllowedCategoriesEnum _Category)
{
Category = _Category;
MaxNumServers = _MaxNumServers;
servers = new Server[MaxNumServers];
NumServers = 0 ;
ServerIDs = 0;
eventlist = EventList.getInstance();
}
public void addServer(AllowedCategoriesEnum aCategory, float productivity, long
maxServiceTime, int queueID)
{
if(NumServers!=MaxNumServers)
{
servers[NumServers] = new Server(productivity, maxServiceTime, queueID);
((Server) servers[NumServers]).ServerID = ServerIDs;
((Server) servers[NumServers]).myCategory = Category;
ServerIDs++; // To guarantee uniqueness
NumServers++;
}
}
public void removeServer(AllowedCategoriesEnum aCategory, int queueID) { }
public void serve(Customer aCustomer, long currentTime, int serverID,
AllowedCategoriesEnum aCategory)
{
int i=0;
for(i=0;i<NumServers;i++)
if(((Server) servers[i]).ServerID == serverID)
{ ((Server) servers[i]).serve( aCustomer, currentTime, serverID, aCategory);
break;
}
}
public void serviceComplete(long currentTime, int serverID, AllowedCategoriesEnum
aCategory)
{
int i=0;
for(i=0;i<NumServers;i++)
if(((Server) servers[i]).ServerID == serverID)
{ ((Server) servers[i]).serviceComplete(currentTime, serverID, aCategory);
break;
}
}
public void checkServer(long currentTime, int FromQueueID, AllowedCategoriesEnum
aCategory)
{
int i=0;
for(i=0;i<NumServers;i++)
if(((Server) servers[i]).FromQueueID == FromQueueID &&
((Server) servers[i]).ServerBusy == false )
{
Event DequeueEvent = new Event();
DequeueEvent.Type = EventTypeEnum.DEQUEUE;
DequeueEvent.EventTime = currentTime;
DequeueEvent.Category = aCategory ;
DequeueEvent.ServerID = ((Server) servers[i]).ServerID;
DequeueEvent.FromQueueID = FromQueueID;
eventlist.Dispatch(DequeueEvent);
break;
}
}
public AllowedCategoriesEnum GetCategory()
{ return Category ; }
}
/************************************
*
* Server.java
*
***********************************/
package WaitingQueue;
public class Server extends ServiceComponent
{
protected EventList eventlist;
protected Measurement TheMeasurement;
protected float Productivity;
protected long MaximumServiceTime;
public int ServerID;
public int FromQueueID;
public boolean ServerBusy;
public boolean EndOfService;
public AllowedCategoriesEnum myCategory;
public Customer CustomerToBeServed;
public Server(float _Productivity, long _MaximumServicTime, int _QueueID)
{
// Initializing the parameters of the server
Productivity = _Productivity;
MaximumServiceTime = _MaximumServicTime;
FromQueueID = _QueueID;
/// Initializing the status of the server
EndOfService = false;
ServerBusy = false;
// Initialize no customer in the Server
CustomerToBeServed = null;
// get the singleton instance
eventlist = EventList.getInstance();
TheMeasurement = Measurement.getInstance();
}
public void EndService()
{
EndOfService = true;
}
public void serve(Customer aCustomer, long currentTime, int serverID,
AllowedCategoriesEnum aCategory)
{
// Those are possibly generated events
Event ReorderEvent = new Event() ;
Event ServiceCompleteEvent = new Event() ;
long IntermediateTime;
// Copy the customer from the event and place it in the server.
CustomerToBeServed = aCustomer;
ServerBusy = true;
// Schedule a REORDER Event
ReorderEvent.Type = EventTypeEnum.REORDER;
ReorderEvent.Category = myCategory;
ReorderEvent.EventTime = currentTime;
eventlist.Dispatch(ReorderEvent);
// Schedule a SERVICE_COMPLETE Event
IntermediateTime = (long) ((CustomerToBeServed.Remaining
ServiceUnits)*Productivity);
if(IntermediateTime< MaximumServiceTime)
{
ServiceCompleteEvent.EventTime = currentTime + IntermediateTime;
CustomerToBeServed.ServiceTime += IntermediateTime;
}else
{ServiceCompleteEvent.EventTime = currentTime + MaximumServiceTime;
CustomerToBeServed.ServiceTime += MaximumServiceTime;
}
ServiceCompleteEvent.Type = EventTypeEnum.SERVICE_COMPLETE;
ServiceCompleteEvent.Category = myCategory;
ServiceCompleteEvent.ServerID = ServerID;
eventlist.Dispatch(ServiceCompleteEvent);
}
public void serviceComplete(long currentTime, int serverID, AllowedCategoriesEnum
aCategory)
{
Event DeactivateOrDequeueEvent = new Event();
long IntermediateTime;
ServerBusy = false;
IntermediateTime = (long) ((CustomerToBeServed.Remaining ServiceUnits)*Productivity);
if(IntermediateTime> MaximumServiceTime)
{
Event ArrivalEvent = new Event();
IntermediateTime = IntermediateTime - MaximumServiceTime;
CustomerToBeServed.RemainingServiceUnits = (int) (IntermediateTime/Productivity);
// Schedule an arrival event to complete the customer service
ArrivalEvent.EventTime = currentTime;
ArrivalEvent.CarriedCustomer = CustomerToBeServed;
ArrivalEvent.Type= EventTypeEnum.ARRIVAL;
ArrivalEvent.Category = myCategory;
eventlist.Dispatch(ArrivalEvent);
}
else // The customer is serviced now
{
// Accumulate Statistics
TheMeasurement.AddFinishTime(currentTime);
TheMeasurement.AddArrivalTime(CustomerToBeServed.ArrivalTime);
TheMeasurement.AddRequiredServiceUnits(CustomerToBeServed.RequiredServiceUnits);
TheMeasurement.AddServiceTime(CustomerToBeServed.ServiceTime);
TheMeasurement.NumCustomers++;
}
if(EndOfService==true)
{ // Schedule a deactivate event to shutdown this server
DeactivateOrDequeueEvent.Type=EventTypeEnum.DEACTIVATE_SERVER;
DeactivateOrDequeueEvent.Category = myCategory;
DeactivateOrDequeueEvent.ServerID= ServerID;
DeactivateOrDequeueEvent.EventTime = currentTime;
eventlist.Dispatch(DeactivateOrDequeueEvent);
}else
{
DeactivateOrDequeueEvent.Type= EventTypeEnum.DEQUEUE;
DeactivateOrDequeueEvent.Category = myCategory;
DeactivateOrDequeueEvent.FromQueueID = FromQueueID;
DeactivateOrDequeueEvent.ServerID= ServerID;
DeactivateOrDequeueEvent.EventTime = currentTime;
eventlist.Dispatch(DeactivateOrDequeueEvent);
}
}
}
/************************************
*
* QueuingComponent.java
*
***********************************/
package WaitingQueue;
public abstract class QueuingComponent
{
protected int NumCategories;
public void addQueueCategory(AllowedCategoriesEnum CatID, boolean
ReorderFlag){ }
public void removeQueueCategory(AllowedCategoriesEnum aCategory) { }
public int addQueue(AllowedCategoriesEnum aCategory) {return -1;}
public void removeQueue(AllowedCategoriesEnum aCategory, int queueID) {}
public int getNumberOfCategories() {return NumCategories; }
public QueuingComponent() {NumCategories = 0 ; }
public abstract void Enqueue(Customer aCustomer);
public abstract Customer Dequeue(AllowedCategoriesEnum CatID, int QID, long
CurrentTime, int ServerID);
}
/************************************
*
* QueueFacility.java
*
***********************************/
package WaitingQueue;
public class QueueFacility extends QueuingComponent
{
protected EventList eventlist;
protected QueuingComponent queueCategories[];
protected int MaxNumCategories;
protected int NumCategories;
public QueueFacility(int _MaxNumCategories)
{
MaxNumCategories = _MaxNumCategories;
queueCategories = new QueueCategory[MaxNumCategories];
NumCategories = 0 ;
eventlist = EventList.getInstance();
}
public Customer Dequeue(AllowedCategoriesEnum CatID, int QID, long CurrentTime, int
ServerID)
{
Customer ctemp;
for (int i=0; i < NumCategories; i++)
{
if (((QueueCategory) queueCategories[i]).Category == CatID)
{
ctemp = ((QueueCategory) queueCategories[i]).Dequeue(CatID, QID, CurrentTime,
ServerID);
if( ctemp != null )
{ // Schedule a SERVE event to that customer
Event ServeEvent = new Event();
ServeEvent.CarriedCustomer = ctemp;
ServeEvent.Type = EventTypeEnum.SERVE;
ServeEvent.Category = CatID;
ServeEvent.ServerID = ServerID;
ServeEvent.EventTime = CurrentTime;
eventlist.Dispatch(ServeEvent); return ctemp;
}
}
}
return null;
}
public void Enqueue(Customer aCustomer)
{
for (int i=0; i < NumCategories; i++)
{
if (((QueueCategory) queueCategories[i]).Category == aCustomer.Category )
{
((QueueCategory) queueCategories[i]).Enqueue(aCustomer);
break;
}
}
}
public void addQueueCategory(AllowedCategoriesEnum CatID, boolean ReorderFlag)
{
queueCategories[NumCategories] = new QueueCategory(SimGlobals. MaxQueuesInCat,
CatID);
((QueueCategory) queueCategories[NumCategories]).Category = CatID;
((QueueCategory) queueCategories[NumCategories]).Reorderable = ReorderFlag;
NumCategories++;
};
public int addQueue(AllowedCategoriesEnum aCategory)
{
for (int i=0; i<NumCategories; i++)
{
if (((QueueCategory) queueCategories[i]).Category == aCategory)
return ((QueueCategory) queueCategories[i]).addQueue(aCategory);
}
return -1;
};
public void removeQueue(AllowedCategoriesEnum CatID, int QID)
{
for (int i=0; i < NumCategories; i++)
{
if (((QueueCategory) queueCategories[i]).Category == CatID)
{
((QueueCategory) queueCategories[i]).removeQueue(CatID, QID);
break;
}
}
}
public void ReorderCategory(AllowedCategoriesEnum CatID)
{
for (int i=0; i < NumCategories; i++)
{
if (((QueueCategory) queueCategories[i]).Category == CatID)
{
((QueueCategory) queueCategories[i]).Reorder();
break;
}
}
};
public int getNumberOfCategories(){ return NumCategories; };
}
/************************************
*
* QueueCategory.java
*
***********************************/
package WaitingQueue;
public class QueueCategory extends QueuingComponent
{
protected EventList eventlist;
protected QueuingComponent queues[];
protected int MaxNumQueues;
protected int NumQueues;
protected int QueueIDs; //unique IDs for members of this category
protected AllowedCategoriesEnum Category;
public boolean Reorderable;
public QueueCategory(int _MaxNumQueues, AllowedCategoriesEnum _Category)
{
Category = _Category;
MaxNumQueues = _MaxNumQueues;
queues = new Queue[MaxNumQueues];
NumQueues= 0 ;
QueueIDs = 0;
Reorderable = false;
eventlist = EventList.getInstance();
}
public int addQueue(AllowedCategoriesEnum aCategory)
{
if(NumQueues!=MaxNumQueues)
{
queues[NumQueues] = new Queue(SimGlobals.MaxQueueLength);
((Queue) queues[NumQueues]).myCategory = aCategory;
((Queue) queues[NumQueues]).QueueID = QueueIDs;
QueueIDs++;
NumQueues++;
return QueueIDs-1;
}
return -1;
}
public Customer Dequeue(AllowedCategoriesEnum CatID, int queueID, long currentTime, int
serverID)
{
int i=0;
Customer dequeuedCustomer = null ;
for(i=0;i<NumQueues;i++)
if( Category==CatID && ((Queue) queues[i]).QueueID == queueID && ((Queue)
queues[i]).getLengthOf()!= 0 )
{
dequeuedCustomer = ((Queue) queues[i]).Dequeue( CatID, queueID ,
currentTime, serverID);
break;
}
return dequeuedCustomer;
}
public void Enqueue(Customer aCustomer)
{
int min = 0;
// Select the queue with the minimum number of customers lining up.
for (int i=1; i < NumQueues; i++)
{
if (((Queue) queues[i]).getLengthOf() < ((Queue) queues[min]).getLengthOf())
{ min = i;
}
}
queues[min].Enqueue (aCustomer);
if(((Queue) queues[min]).getLengthOf() == 1)
{
Event CheckServerEvent = new Event();
CheckServerEvent.Type = EventTypeEnum.CHECK_SERVER;
CheckServerEvent.EventTime = aCustomer.ArrivalTime;
CheckServerEvent.Category = Category;
CheckServerEvent.FromQueueID = ((Queue) queues[min]).QueueID;
eventlist.Dispatch(CheckServerEvent);
};
}
public void Reorder()
{
Customer c;
int min = 0;
int max = 0;
for (int i=1; i < NumQueues; i++)
{
if (((Queue) queues[i]).getLengthOf() < ((Queue) queues[min]).getLengthOf()) {
min = i;
}
if (((Queue) queues[i]).getLengthOf() > ((Queue) queues[max]).getLengthOf()) {
max = i;
}
}
while (((Queue) queues[max]).getLengthOf() - ((Queue) queues[min]).getLengthOf()
> 1)
{
c = ((Queue) queues[max]).removeLast();
((Queue) queues[min]).Enqueue (c);
min = 0;
max = 0;
for (int i=1; i < NumQueues; i++)
{
if (((Queue) queues[i]).getLengthOf() < ((Queue) queues[min]).getLengthOf()) {
min = i;
}
if (((Queue) queues[i]).getLengthOf() > ((Queue) queues[max]).getLengthOf()) {
max = i;
}
}
}
}
}
/************************************
*
* Queue.java
*
***********************************/
package WaitingQueue;
public class Queue extends QueuingComponent
{
Customer[] contents;
int front;
int length;
int MaxLength;
public AllowedCategoriesEnum myCategory;
public int QueueID;
public Queue(int maxQueueLength)
{
contents = new Customer[maxQueueLength];
front = 0 ;
length = 0 ;
MaxLength = maxQueueLength;
}
public Customer removeLast()
{
Customer lastCustomer;
lastCustomer = contents [(front+length)%MaxLength - 1];
length—;
return lastCustomer;
}
public int getLengthOf (){return length; }
public int getMaxLength (){ return MaxLength; }
public void Copy (Queue cq)
{
Customer ctemp;
int len = getLengthOf();
for (int i = 0; i < len; i++)
{
ctemp = Dequeue(myCategory, QueueID, 0,0);
cq.Enqueue(ctemp);
}
cq.QueueID = QueueID;
}
public void Enqueue(Customer aCustomer)
{
contents [(front+length)%MaxLength] = aCustomer;
length++;
}
public Customer Dequeue(AllowedCategoriesEnum CatID, int QID, long CurrentTime, int
ServerID)
{
Customer currentCustomer;
currentCustomer = contents [front];
front = (++front)%MaxLength;
length—;
return currentCustomer;
}
}
/************************************
*
* AbstractGenerator.java
*
***********************************/
package WaitingQueue;
public abstract class AbstractGenerator
{
protected EventList eventlist = EventList.getInstance();
public void generateArrival(long currentTime, Customer new_customer)
{
Event new_event = new Event();
new_event.Type = EventTypeEnum.ARRIVAL;
// Set the time of the next arrival
long TimeIncrement = ArrivalTimePolicy(currentTime);
new_event.EventTime = currentTime + TimeIncrement;
new_customer.ArrivalTime = new_event.EventTime;
// Set the type of the customer
AllowedCategoriesEnum customerCategory = ArrivalCategoryPolicy();
new_event.Category = customerCategory;
new_customer.Category = customerCategory;
// Set the service units for the customer
int serviceUnits = ServiceUnitsPolicy();
new_customer.RequiredServiceUnits = serviceUnits;
new_customer.RemainingServiceUnits = new_customer.RequiredServiceUnits;
// Add the event to the event list handler
new_event.CarriedCustomer = new_customer;
eventlist.Dispatch(new_event);
}
public abstract long ArrivalTimePolicy(long currentTime);
public abstract AllowedCategoriesEnum ArrivalCategoryPolicy();
public abstract int ServiceUnitsPolicy();
}
/************************************
*
* RandomArrivals.java
*
***********************************/
package WaitingQueue;
public class RandomArrivals extends AbstractGenerator
{
public long ArrivalTimePolicy(long currentTime)
{
double randomNumber = Math.random();
return (long) ( randomNumber * (double) 5 );
}
public AllowedCategoriesEnum ArrivalCategoryPolicy()
{
double randomNumber = Math.random();
if(randomNumber < 0.5 )
return AllowedCategoriesEnum.COACH;
else return AllowedCategoriesEnum.BUSINESS;
}
public int ServiceUnitsPolicy()
{
double randomNumber = Math.random();
return (int) ( randomNumber * (double) 15 ) ;
}
}
/************************************
*
* EventList.java
*
***********************************/
package WaitingQueue;
public class EventList
{
private event_node head_event;
static private EventList theInstance = null;
static public EventList getInstance()
{
if(null == theInstance) {
theInstance = new EventList();
}
return theInstance;
}
protected EventList() { head_event = null; }
public void clear()
{
event_node top_node ;
while( head_event != null) // Repeat till the list is empty
{
head_event.ptr_event_object = null;
top_node = head_event;
head_event = head_event.next_event_node;
top_node = null;
}
}
public void Dispatch(Event new_event)
{
// If the event list is empty , then it is the first event in the
// list , add a new node and make it the head of the list
if(head_event == null )
{
head_event = new event_node();
head_event.ptr_event_object= new_event ;
head_event.next_event_node = null ;
return ;
}
// There is already events in the list , then search for the
// place to add the event according to the time of the event to
// be added compared with the time of the events already in the
// existing nodes.
event_node current = head_event;
// check if the node we want to add will be the first node in the
// event list , because its time is less than the time of the
// head node.
if ( new_event.EventTime <= head_event.ptr_event_object.EventTime )
{
event_node new_node = new event_node();
new_node.ptr_event_object = new_event;
new_node.next_event_node = head_event;
head_event = new_node;
return;
}
// Search until we reach the end of the event list
while(current.next_event_node != null)
{
if( new_event.EventTime <= (current.next_event_node). ptr_event_object.
EventTime )
{
// Add the new node with the new event between the
// current and the next node
event_node new_node = new event_node();
new_node.ptr_event_object = new_event;
new_node.next_event_node = current.next_event_node;
current.next_event_node = new_node;
return;
}
current = current.next_event_node ;
};
// We searched the list and we did not find an event whose time
// is larger than the time of the event we want to schedule, that
// means the event we want to schedule is the last event we will
// add to the list
current.next_event_node = new event_node();
current = current.next_event_node;
current.ptr_event_object = new_event ;
current.next_event_node = null;
}
public Event GetNextEvent()
{
// If there is no events in the event_list queue , return NULL
if( head_event == null ) return null ;
// Create a pointer to point to the event to be returned
Event event_to_dispatch = head_event.ptr_event_object;
// Create a node pointer to point to the node to be deleted from the
// event list
event_node top_node = head_event;
// Make the next node to be the head node
head_event = head_event.next_event_node ;
// Delete the top_node
top_node = null;
// return the required event to be simulated
return event_to_dispatch;
}
}
/************************************
*
* event_node.java
*
***********************************/
package WaitingQueue;
public class event_node
{
public event_node next_event_node;
public Event ptr_event_object;
public event_node()
{
next_event_node = null;
ptr_event_object = null;
}
}
/************************************
*
* Event.java
*
***********************************/
package WaitingQueue;
public class Event
{
public long EventTime;
public EventTypeEnum Type;
public AllowedCategoriesEnum Category;
public Customer CarriedCustomer;
public int FromQueueID;
public int ServerID;
public Event() { CarriedCustomer = null; }
}
/************************************
*
* EventTypeEnum.java
*
***********************************/
package WaitingQueue;
import java.io.*;
import javax.print.*;
import javax.print.attribute.*;
import javax.print.attribute.standard.*;
import javax.print.event.*;
public class EventTypeEnum
{
public static final EventTypeEnum ARRIVAL = new EventTypeEnum();
public static final EventTypeEnum REORDER = new EventTypeEnum();
public static final EventTypeEnum DEQUEUE = new EventTypeEnum();
public static final EventTypeEnum SERVE = new EventTypeEnum();
public static final EventTypeEnum SERVICE_COMPLETE = new EventTypeEnum();
public static final EventTypeEnum CHECK_SERVER = new EventTypeEnum();
public static final EventTypeEnum ACTIVATE_SERVER = new EventTypeEnum();
public static final EventTypeEnum DEACTIVATE_SERVER = new EventTypeEnum();
private static final String[] stringTable = {
"ARRIVAL",
"REORDER",
"DEQUEUE",
"SERVE",
"SERVICE_COMPLETE",
"CHECK_SERVER",
"ACTIVATE_SERVER",
"DEACTIVATE_SERVER"
};
protected String[] getStringTable() {
return stringTable;
}
private static final EventTypeEnum[] enumValueTable = {
ARRIVAL,
REORDER,
DEQUEUE,
SERVE,
SERVICE_COMPLETE,
CHECK_SERVER,
ACTIVATE_SERVER,
DEACTIVATE_SERVER
};
protected EventTypeEnum[] getEnumValueTable() {
return enumValueTable;
}
}
/************************************
*
* AllowedCategoriesEnum.java
*
***********************************/
package WaitingQueue;
import java.io.*;
import javax.print.*;
import javax.print.attribute.*;
import javax.print.attribute.standard.*;
import javax.print.event.*;
public class AllowedCategoriesEnum
{
public static final AllowedCategoriesEnum COACH = new AllowedCategoriesEnum();
public static final AllowedCategoriesEnum BUSINESS = new AllowedCategoriesEnum();
private static final String[] stringTable = {
"COACH",
"BUSINESS"
};
protected String[] getStringTable() {
return stringTable;
}
private static final AllowedCategoriesEnum[] enumValueTable = {
COACH,
BUSINESS
};
protected AllowedCategoriesEnum[] getEnumValueTable() {
return enumValueTable;
}
}
/************************************
*
* Customer.java
*
***********************************/
package WaitingQueue;
public class Customer
{
public long ArrivalTime;
public long ServiceTime;
public int RequiredServiceUnits;
public int Priority;
public AllowedCategoriesEnum Category;
public long FinishTime;
public int RemainingServiceUnits;
public Customer()
{
}
public Customer(long CurrentTime, int RequiredUnits, AllowedCategories Enum _Category)
{
FinishTime =0 ;
ArrivalTime =CurrentTime ;
RequiredServiceUnits=RequiredUnits;
RemainingServiceUnits = RequiredUnits;
ServiceTime = 0 ;
Category = _Category;
Priority = 0 ;
}
}
/**************************************
* Measurement.java
*
*************************************/
package WaitingQueue;
public class Measurement
{
public int NumCustomers;
public long ArrivalTime[];
public long FinishTime[];
public long RequiredServiceUnits[];
public long ServiceTime[];
static private Measurement theInstance = null;
static public Measurement getInstance()
{
if(null == theInstance) {
theInstance = new Measurement();
}
return theInstance;
}
protected Measurement()
{
NumCustomers=0;
ArrivalTime = new long[SimGlobals.MaxNumOfCustomers];
FinishTime = new long [SimGlobals.MaxNumOfCustomers];
RequiredServiceUnits = new long [SimGlobals.MaxNumOfCustomers];
ServiceTime = new long [SimGlobals.MaxNumOfCustomers];
}
public long AverageWaitingTime()
{
long Average = 0;
for(int i=0;i<NumCustomers;i++)
Average += (FinishTime[i]-ArrivalTime[i] - ServiceTime[i]);
Average = Average/NumCustomers;
return Average;
}
public double StdWaitingTime()
{
long Average=0;
Average = AverageWaitingTime();
double Std=0;
long Diff=0;
for(int i=0;i<NumCustomers;i++)
{
Diff = (FinishTime[i]-ArrivalTime[i]-ServiceTime[i]-Average);
Diff = Diff*Diff;
Std += Diff;
}
Std = Std/(NumCustomers-1);
Std = Math.sqrt(Std);
return Std;
}
public long MaxWaitingTime()
{
long Max=0;
for(int i=0;i<NumCustomers;i++)
if((FinishTime[i]-ArrivalTime[i]-ServiceTime[i]) > Max) Max = (
FinishTime[i]-ArrivalTime[i]-ServiceTime[i]) ;
return Max;
}
public void AddArrivalTime(long arrival) { ArrivalTime[NumCustomers] = arrival;};
public void AddFinishTime(long finish) { FinishTime[NumCustomers] = finish;};
public void AddServiceTime(long Service) { ServiceTime[NumCustomers] = Service; };
public void AddRequiredServiceUnits(int service) { RequiredServiceUnits[NumCustomers]
= service;};
}
/**************************************
* SimGlobals.java
*
*************************************/
package WaitingQueue;
public class SimGlobals
{
public long SimTime;
public EventTypeEnum EventType;
public static final int MaxNumOfCustomers = 1000 ;
public AllowedCategoriesEnum AllowedCategories;
public static final int MaxQueueLength = 10 ;
public static final int MaxCategoriesInFac = 2 ;
public static final int MaxQueuesInCat = 1 ;
}
Figure 12-13. A UML class diagram model for the check-in counters example.