Ass2

Homework Assignment 2 Systems Programming – Fall 2005 Due date: 29 Dec 2005

1. General In this assignment, we will build a simulator of a restaurant. We will design a system to reflect the state of clients and their orders at any given time. Given an initial description of the system and a list of events, the simulator updates the states of the objects in the system accordingly. The events include: the arrival of a new group of clients to the restaurant, break-down of an ordering machine, kitchen workers strike and cancellation of order. In addition, the simulator also gets commands according to which it produces reports on the system state. The commands are aimed at monitoring the system, and therefore, have no effect on its state (except for the termination command). The objective of this assignment is to work on the design of an object-oriented system, and gain experience in implementation in C++ using classes and standard STL-based data structures.

2. Detailed Description

Discrete Event Simulation Systems

Simulation systems are used to describe how a complex system of interacting objects can evolve over time. Each object acts according to specific rules, and it can react to external events or to the action of other objects. Simulation systems are important research tools to analyze complex systems when no analytical framework exists to predict the evolution of a system given the rules of the single elements. They are used extensively for digital circuit analysis and weather prediction, for example. In a discrete simulation system, the simulator works according to the following design. The participants are a simulation controller and simulated objects. The state of the system corresponds to the state of all the simulated objects present in the system at any given time. Each simulated object has its own internal state (for example, an order machine includes in its state the time it takes to take an order) and connections to other simulated objects (for example, the kitchen is making the orders that the machines took from the clients). The simulation controller simulates the progress of time as follows: it runs a loop and manages an internal clock. At each iteration, the clock advances by a set amount of time (a measure known as the "time slice" of the simulation). For each time slice, the simulation controller sends an event to all existing simulated objects asking them to "react" to the fact that "time progresses". The simulation controller can also trigger external events according to a simulation script (for example, the event that an ordering machine breaks down). For each time slice, simulated objects recompute their internal state, possibly recompute the set of objects they are connected to, and as they make transitions from

one state to another, they may send events to the objects they are connected to, which in turn will react. The simulation terminates when the controller reaches a set condition (for example after the internal clock has reached a set limit, or when there are no more events and all the clients have left the restaurant).

General description of the restaurant Our restaurant is a self-order restaurant where the clients order their food from ordering machines. The restaurant does not have an ordering machine for each table and not all machines can serve all tables. The initial description of the simulation defines which table can order from which machine. The number of tables in the restaurant is also defined in the initial configuration. Each table has a number of seats. This number determines whether a group of clients can sit at this table or not. In order to organize the restaurant right when a group of clients arrived, we sit them in the smallest table available that is big enough for them to sit together. If there is more than one table of the same size that is suitable for the group of clients, then they sit at the table with the smallest number. If there is no table big enough available for the group of clients, then they wait in queue until a table large enough becomes available. In our restaurant, there are two kinds of courses (Type1 or Type2) which are defined in the simulation configuration. The kitchen in our restaurant can prepare at one time a limited number of courses of each kind (that limited number is defined in the configuration). If the kitchen is already preparing the maximum number of orders and another order arrives, the new order waits in queue until the kitchen is available. Orders are made by clients at the moment they sit at a table. The order is entered on the order-machine assigned to this table. If there is more than one machine available that can serve this table, then you should pick the machine with the smallest serial number. The machine passes the order to the kitchen and the kitchen prepares the courses (the preparation takes a time period that will be defined later). When the courses in the order are ready, the table will get up and take the food. Picking up the food when it is ready takes a time period that will be defined for each table. The clients eat then the courses (the time that it will take to eat each course will be defined later), and as soon as they are done eating, they leave the restaurant and the table is now free again.

Clients waiting for a table

2 seats table

4 seats table

Order machine

8 seats table

4 seats table

Order machine

2 seats table

6 seats table

Order machine

Orders waiting for the kitchen

Kitchen

Simulated Objects

The system we simulate includes three basic types of conceptual objects: Clients, order machine, and order. We highly recommend you to include these three objects in your model. Naturally, you may decide to include more objects – decide in advance which information you think should be an object in your system (restaurant, table, kitchen..).

Clients

The clients come to the restaurant in groups of people. Each group is characterized by: * A unique Serial Number (SN). * Number of clients in the group. * Number of clients that will order course from Type1. * The time it takes for the group to start eating their food after it is ready. The SN will be an int. If the number of clients in a group that will order Type1 course does not match the size of group that mean that the rest of the people in the group will order Type2 course. The last information refers to the number of clock pulses that will pass from the moment that the kitchen is done making the food until the group starts eating.

The queue of clients waiting for a table is managed on a FCFS basis (first come first served), but if for example the first group in the queue is from size 3 and now a 2 seats table becomes available, the next group in the queue with size <= 2 will sit and not the first group in the queue. The machines should also serve the tables in FCFS order.

Order machine

Each order machine is characterized by: * A unique Serial Number (SN). * The time it takes for the machine to get an order from a table. * The time it takes to repair a machine after it is broken. * The list of the tables that it can serve.

Order

Each order is characterized by: * SN – the SN of the ordering group * Number of the table from which the order is taken. * SN of the order machine that took the order. The order object should “live” from the moment that the clients are done giving it to the order machine until the moment the clients leave the restaurant. In addition, the following dynamic information is maintained for each order: * State- WK- while waiting for the kitchen to start making it. K- while the kitchen is making the order. WG- while the food is waiting for the group to take it. E- while the table is eating the food.

We describe here the progression of one group from the moment they arrive to the restaurant and define few more rules: When arriving to the restaurant the group will wait until a table that is big enough for them becomes available. If more than one table is available, they should be seated in the smallest table that is big enough for them to sit. If there is more than one such table, they are seated to the table with the smaller Serial Number. The group will then wait until one of the order machines that can serve their table is available. Tables wait for the machines in first-come first-served (the group waits for all the machines that can serve their table and accesses the first one that becomes available).

When a machine is available, they give their order and it will take the number of pulse that was defined in the machine (time that’s take it to get an order from table). When this time passes, an order object is created and the order is immediately transferred to the kitchen. If the kitchen is available, it makes the order. It will take X pulses to make the order where X=number of Type1 courses in the order*time to make Type1 course + number of Type2 courses in the order*time to make Type2 course. If the kitchen is not available, the order waits in a pure FIFO queue. From the pulse that the order is ready, it takes the clients in the group time to get up and take the food (the time that was defined for each group) and then it will take the group Y pulse to eat the courses, where Y=time to eat Type1 course if time to eat Type1 course>= time to eat Type2 course or Y=time to eat Type2 course if time to eat Type2 course> time to eat Type1 course. After eating their meal, the group leaves the restaurant and the table that they sit around is now free again for a new group of clients.

Initial System Configuration The restaurant simulation is initialized by reading static information from configuration files. It initializes the tables in the restaurant and their sizes by reading the Table.ini file and the order machine and their served tables by reading the Order_machine.ini file. It also gets the following set of constants from the Configuration.ini file: Time to eat type1: the time that it takes to a client to eat Type1 course Time to eat type2 the time that it takes to a client to eat Type2 course. Time to prepare type1: the time that it takes the kitchen to prepare type1 course. Time to prepare type2: the time that it takes the kitchen to prepare type2 course. Max orders in the kitchen: maximum number of courses that the kitchen can make at a time.

Events

There are several types of external events in the system. Each event is characterized by a time slice which is a number of pulses in the simulation since the beginning of the simulation (pulse 0). The possible events are: A. New clients The following information will be given: * Pulse of event * SN of the group.

* Size of the group. * Number of clients in the group that will order Type1 course. * Time that it takes to the group to get their food when ready. B. Machine break-down The following information will be given: * Pulse of event * Machine SN * Break-down duration (in pulse) (how long the break-down will take) If the break-down appears while the machine is taking an order, then the order is “lost”. The table from which the order was taken should go back in Queue for one of the machines that can server the table. If for a specific table the broken machine was the only machine that can serve it, then it should wait until this machine will be fixed. As soon as the machine is fixed it should start taking orders from the right Queue. C. kitchen strike The following information will be given: * Time of event * Strike duration (in pulse)(how long the strike will take) When the kitchen strikes, it stops making the orders and as soon as the strike ends, the work continues from the situation it was when the strike started, i.e., if it takes X time to make an order and the strike happened Y pulse after starting to make it, after the strike there will remain X-Y pulses for this order to be ready.

Commands

The simulation controller can execute commands found in the simulation script. Commands are the way we use to get information on the state of the simulated system. There are 6 types of commands in our system, 5 of them produce a report, and one stops the simulation. Each report has an ID. It will help us connecting the report commands to their output. Each one of the reports should be printed to an output file. The format will be described in the output section. NOTE: your output must match EXACTLY the requirements of this specification including spaces and capital/small letters differences.

Table Report

This command produces a report concerning a given table. The parameters of the command are: * The pulse when the report should be generated * The ID of the report * The table number The report is printed to an output file which we describe later. The output of the report consists of the following: * The report ID.

* Type of report. * The pulse of report. * The table number. * Previous sitting list of clients. * Currently sitting clients (or EMPTY) * Period that the clients currently sitting around this table have been at the table (if empty then this field should be 0) The sitting list of clients will be ordered by ascending order of sitting pulse (that is, the clients that were seated fist will be printed first).

Machine Report

This command produces a report concerning a given order machine. The parameters of the command are: * The pulse when the report should be generated. * The ID of the report. * The machine SN. The report is printed to an output file which we describe later. The report consists of the following: * The report ID. * Type of report. * The pulse of report. * The machine SN. * Previous order list. * SN of order currently taken. You should print EMPTY if the machine is idle or ERROR if the machine is during a break-down. * List of tables from which this machine can take orders. * Errors number (how many times the machine had break-downs). * Average break-down length (how long the machine was down when this time includes the fixing time). * Longest break-down (longest period during which the machine was down when this time include the fixing time) Each of the lists mentioned above will be ordered in ascending order over pulse of event. The tables list will be ordered in ascending order over the number of table. Pay attention that in the previous order list you do not include orders that was stopped in the middle of ordering due to break-down of machines. The error number and information on breakdowns does not include information about current break-downs.

Order report

This command produces a report concerning a given order in the system. The parameters of the command are: * The pulse when the report should be generated. * The ID of the report. * The order SN.

!

The report is printed to output file which we describe later. The report consists of the following: * The report ID. * Type of report. * The pulse of report. * The order SN. * The table SN at which the ordering group is currently sitting. * The number of clients in the ordering group. * The SN of the machine that took the order (or 0 if not ordered yet). * Current state (as described in the order object). * Number of Type1 courses ordered. * Number of Type2 courses ordered. * Waiting time for the kitchen (how long the order had to wait from the moment the machine ends taking it until the moment the kitchen starts making it). * Time in the system (the number of pulses from the creation of this order object until it “dies”). An order report regarding a specific order will be asked only while this specific order is supposed to be in the system, so you don’t need to keep records of old orders in the memory.

Queues Report

This command produces a report concerning all the waiting lists in the system, that is the waiting list for each table and the waiting list for the kitchen. The parameters of the command are: * The pulse when the report should be generated * The ID of the report The report is printed to an output file which we describe later. The report consists of the following: * The report ID. * Type of report. * The pulse of the report. * List of client groups currently waiting for a table. * List of orders currently waiting for the kitchen. * Average waiting time of clients for a table. * Average waiting time of orders for the kitchen. * Longest waiting time of clients for a table. * Longest waiting time of orders for the kitchen. In all four last fields in the Queue report – do not include the waiting times of the objects currently in the queues.

Popularity Report

This command is designed to print popularity data regarding the tables and the courses on the restaurant. The parameters of the command are: * The pulse when the report should be generated * The ID of the report

"

The report is printed to an output file which we describe later. The report consists of the following: * The report ID. * Type of report. * The pulse of the report. * List of all the tables in the restaurant and for each one the number of times that a new group sits at it. * The most popular course in the restaurant with the number of times that it was ordered. * The least popular course in the restaurant with the number of times that it was ordered. The list of the tables should be arranged in descending order over times the tables was seated and as second key, the number of tables in ascending order. Pay attention that the data from cancelled orders should be in this report.

Termination

This command causes the system to stop the simulation at a specified pulse. Note that upon exit, our program should return all resources it uses to the operating system.

Simulation workflow

The system is initialized according to the configuration files. After the system is initialized, it works according to the following algorithm do {

pulse = -1

pulse++ A. Update system B. Execute the events of pulse eventPulse. C. Execute the commands of day commandPulse. } while (termination command has not been found);

(A) Update System.

The simulator updates the states of the objects in the system Don’t misuse the update stage – I mean don'tgo over all clients and machines or orders to check if they need to be updated. You should know from advances which object needs to change its value.

(B) Execution of Events.

During the simulationPulse the system receives the events that related to that pulse (All events contain a pulse field that determines on which simulationPulse they are executed). For all events that have the same pulse field in the simulation script, the order is the one in the events file.

(C) Execute Commands.

#

At this stage, we process the commands associated with this pulse (like in the events, the order between commands of the same pulse will be according to the order in the commands file). An example: Consider the case of one table with 10 seats, and one group sits around it at pulse 4, eating a meal which will be ended at at pulse 5. If a new group of 10 people arrive at pulse 4, they will have to wait, since the first group is still eating. In the next pulse (5) the first group will finish their eating, and the status of the table will be updated at the ‘update system’ of pulse 6, so the new group will sit around the table for a delightful meal, at pulse 6.

3. Input Files

The input for our simulation will be given in 5 different files (which together form the simulation script): 1. Tables.ini: contains the tables in the restaurant and its size (number of sites). 2. Order_machines.ini: contains the order machine in the restaurant and its served tables. 3. Events.ini: contains the event that the simulator should process. 4. Commands.ini: contains the commands that the simulator should execute. You are given a zip file that contains files and directories you must use to start programming your assignment. These files contain the class IniFileReader that you should use to read your input files. An example of this class usage is given in the main.cpp file and IniFileReader.h contains detailed description.

Tables.ini Format

The format of the file- TableExp.txt Example for a possible Tables.ini file- Tables.ini

Order_machines.ini Format

The format of the file- Order-machineExp.txt Example for a possible Order_machines.ini file- OrderMachines.ini

Configuration.ini Format

The format of the file- ConfigurationExp.txt Example for a possible Configuration.ini file- Configuration.ini

Events.ini Format

The format of the file- EventsExp.txt Example for a possible Events.ini file- Events.ini

Commands.ini Format

The format of the file- ComandsExp.txt Example for a possible Commands.ini file- Commands.ini Pay attention: the names of the files are strict. Don' t change them. The formats of the files are exactly as described. Do not assume all events and commands are ordered by pulse. $

4. Output Format

Your output is composed of the reports generated during the simulation as a result of the report commands. The exact format of each report is as follows:

Table Report

The format of the report- TableReportExp.txt

Order-machine Report

The format of the report- MachineReportExp.txt

Queues Report

The format of the report- QueuesReportExp.txt

Popularity Report

The format of the report- PopularityReportExp.txt

Order Report

The format of the report- OrderReportExp.txt

Report.ini

Report.ini is the output file of all the reports. An example of a report file which was produced by running the example filesReport.ini Pay attention, your program might be tested automatically. It will be given as an input the 5 input files and the output of the program will be compared to the output of our implementation. You must recreate the Report.ini file every run. Any mismatch between the outputs will be considered a mistake. Follow the definitions carefully and use our implementation executable to confirm your results.

5. Implementation

Our application must work in the following order: In the first stage we read the data from all the input files and put it into logical data structures. In the second stage, we run the simulation as described above. You can assume that the input files are correct in there format as described, but they are not checked logically and you have to check for that. (A logical error could be for example an event that was not defined, asking for machine SN that was not defined in the .ini file).

6. Data Maintenance and Efficiency

There are basic design issues you must pay attention to, before you start implementing the application.

1. Each data piece should be held exactly once in memory. 2. The events should require poly logarithmic time (meaning log (n) ^k where k is natural). In order to do so you should learn to work with the c++ Map structure. Any exception of that rule should be stated and explained. 3. The total time of the program should be minimal. State A should update only relevant data and there for its total time is proportional to the number of events with few exceptions. The program time can be tested for its time by simply running of more than a 1000 objects and any set of days so don' t make any unnecessary assumptions. 4. We expect GOOD programming practice and it will be a consideration in determine your grade. Think well about your design and be ready to explain it.

7. Framework

In order to ease the technical parts of the assignment, we give you some code to start with. This code does all the dirty work of parsing the input files. We also added an example of using this code. In the zip file- reader.zip you will find a directory called "Assignment 2 framework" which includes: A directory called "Source". This is the only thing you will need from the zip when working on linux / unix. This directory contains: o makefile o Tables.ini, Order-machines.ini, Events.ini, Configuration.ini, Commands.ini: simple examples of the input files. o IniFileReader.cpp, IniFileReader.h: files containing a class named IniFileReader that helps you parse your input files. Read IniFileReader.h for more instructions on how to use it (you don' t have to completely understand the code in order to use it) o main.cpp - a usage example for IniFileReader. o stdafx.h - common header file used by the framework. 2 files and a directory called "ass2" needed to work on Windows Visual C++ 6 (pay attention that your assignment is tested on the host “black” which is a UNIX machine so make sure you test it on this platform before submitting). These files are provided for people that want to develop the application on Windows and test and debug it again on "black".

8. Summary of Requirements

You are required to submit a zip file containing only files (no sub-directories) which contains your source files and makefile that builds your application.

You are also required to submit one cppUnit test class, we will publish later the selected class and the methods to be tested.

9. Test Procedure The test procedure includes the following steps: 1. Run "make" on black: this should produce an executable called "ass2". 2. Put input files in the same directory as the executable, run it. 3. The program should produce on the standard output the contents of all the requested reports in the right format. 4. Compare the output your program produces with the one we expect. Configuration.ini Events.ini Commands.ini Tables.ini Orders-machines.ini Report.ini