CS 451 - Spring 2011

Project 2+3 - Air Traffic Controller Simulator

Helpful Hints

Version 1.2 (see bottom of the page for changelog)

INPUT

Rate R: rate at which the aircraft generator generates new aircraft.
Average Landing Time ALT: time it takes an aircraft to land. This is the time the aircraft will reserve a runway when it lands. Each aircraft determines its actual LT using the formula: LT = random (0, 2*ALT).
Average Take-off Time ATT: time it takes an aircraft to take-off. This is the time the aircraft will reserve a runway when it takes off. Each aircraft determines its actual TT using the formula: LT = random (0, 2*ATT).
Average Arrival Time AAT: This is on average, the time in the future a newly generated aircraft will arrive at the airport and will need to land. Each aircraft will determine this time after it becomes active according to the following formula: Tnow + random (0, 2*AAT). The aircraft needs to find a slot that starts at least at this time or later when picking a schedule. Thus, the slot will start at time AAT or later, and will block the runway for time LT.
Average Departure Time ADT: This is on average, the time in the future a newly generated aircraft will depart from the airport. Each aircraft will determine this time after it becomes active according to the following formula: Tnow + random (0, 2*ADT)
Halting time HT: This is the time the simulation will end. You may want to start with allowing just a few aircraft to debug, but for the final run you should use at least 1000 aircraft.
(Wind change rate: I am still considering this part of the project, I may remove it. You can skip it for now.)

Note that our time unit in this project is minutes. However, this should make no difference to your program, you may treat these as just "time units" if you like.

INITIALIZATION

Your program should start by performing the necessary initialization steps. For example, it should read all the input parameters, spawn the necessary proceses, create any resources required for inter-process communication (e.g., shared mem, mailboxes, sockets). You should figure out a way to convey that information to the newly created processes. Examples include a reserved shared memory space or a directory server (a new process) running on a fixed port on the machine.

Finally, your program should enter an infinite loop serving events. (This works nicely if the main process becomes the event handler, but clearly it is not necessary)

PROCESSES

Here is a brief, high-level description if the processes we would like you to implement.

Process AircraftGenerator
{
        receive event;
        demultiplex event (e.g., using a case statement)
        case: generate_aircraft
                generate Tinterval random (0, 2*Rate)
                fork aircraft process;
                schedule an aircraft generation event at time Tnow + Tinterval
        case: halt

Print statistics
exit

                (note that no more aircraft need to be generated so
                do not add more generation events)

        wait for next event
}

Process Aircraft
{
        receive event;

        case: new aircraft
                read variables interval and action
                Decide action: is aircraft is landing or taking off

lock schedule; // schedule must be locked before reading Tnow
Pick AT or DT As described above in the INPUT section

find slot and register with scheduler
insert event in the event_queue

unlock schedule;

        case: arrived
                print arrival message and time
                update global stats
                exit
        case: departed
                print departure message and time
                update global stats
                exit
}

Process Event_handler
{
        external event_q; // pointer to the head of the queue
        global Tnow;        // variable that holds the current time

        while (1)
        {
                if event_q = NULL
                        break;
                lock schedule // don't advance time while an aircraft is scheduling itself

new_event = next event from the head of the queue

Tnew_event = time new_event is supposed to happen
make Tnow = Tnew_event

unlock schedule

                deliver new_event to approriate process
                }
        calculate and prinf global stats (see output section);
        exit;
}

Event Handling

Your event handling should include the following operations. These functions MUST lock the event queue before inserting/removing an event! You can accomplish this by putting a lock around the event queue pointer.

int insert_event (ev, ts): this inserts event ev with timestamp ts in the queue. Note that events in the queue are time sorted, so this function needs to traverse the queue in order to put the event at the appropriate place. May return an error if insertion fails
event ev = remove_head(): this removes and returns the event at the head of the queue and makes event_q point to the next event
void dump_evq (): this dumps the contents of the event queue in sequence

Event Format

The event format should contain at least the following items:

Timestamp when the event should occur
A pointer to the process that should receive the event
Any parameters/flags that should also be delivered to the receiving process

The implementation of the pointer to the process that should receive an event is your responsibility. Your program should clearly include a process identifier and a method to notify the process that an event was received. For example, if you choose to use sockets the pointer might be the socket the process is listening on. In that case your process should block reading from that socket. If you use shared memory you can write the event (or a pointer to it) at a specific location in the shared block and then wake up the process.

We ask that you create a common data structure for an event. Thus, all events will share a type variable, and the contents might change based on the type (in C unions are good for implementing such data structures). The event structure definition should go in your header file.

DATA STRUCURES: The Schedule

This is the actual data structure holding the current schedule. It should be implemented in a way that is accessible by all processes (shared memory is probably best). You should provide all the functions or methods needed to access the schedule, and all the necessary locking mechanisms that need to accompany it. Examples include:

slot get_slot (interval): this will return a free slot from the schedule. You should make sure all the locking is done appropriately before the slot is returned. The return structure specifies the actual interval and the runway the slot was assigned to.
void dump_schedule (): this dumps the contents of the schedule. You should use this after each change in the schedule.

A note on the schedule structure:
The schedule is a shared data structure that needs to be locked when accessed. While we could have a single process controlling access to the data, this is not desirable because it delays other aircraft. For example, imagine an aircraft needs a more complex calculation before it can get a slot in the schedule (we are not doing it now, but it is possible under more complex conditions). If that aircraft holds the schedule locked for a long time, it may delay other aircraft from getting scheduled. Thus, implementing the schedule as a shared structure that only gets locked when needed is a more robust design.

OUTPUT

While executing, your program should print a message when events are scheduled and when they occur. For example:

$ + <event name> <timestamp> <originating process or thread> //event added to the queue
$ - <event name> <timestamp> <originating process or thread> // event removed from the queue

If the event is an aircraft being scheduled, you may also want to dump the contents of the schedule:

$ RWY: <Ivl, aircraft#, action>, <Ivl, aircraft#, action>, ...
$ RWY: <Ivl, aircraft#, action>, <Ivl, aircraft#, action>, ...

For example, assuming there are six aircraft in the schedule, three per runway (A: arrival, D: departure):

$ 36L: <0,5, 1, D>, <7,12, 2, D>, <15,20, 3, A>
$ 36R: <0,5, 4, D>, <5,10, 5, A>, <11,16, 6, D>

At the end of the simulation your program should print the following simulation statistics:

Total simulation time (note this may be different that specified, since we wait for the event_q to drain)
# of aircraft generated
# of aircraft arrived
# of aircraft departed
Average waiting time for arriving aircraft
Average waiting time for departing aircraft
Average delay for arriving aircraft //delay = scheduled - actual time
Average delay for departing aircraft

You should run your simulation with different combination of aircraft generation rates and take-off and landing times. The goal is to see what happens when you make the airport busier. Run your simulation with at least five combinations of input.

You should also experiment with the simulation running time as follows. Select a time that seems sufficiently long to you and run the simulation. Note the results. Now run the simulation again by increasing the running time by say 10%. If the results change significantly, then double the simulation time and repeat until you see very little change. When the results do not change significantly, you have reached steady state conditions. Now you can do a binary search by reducing and increasing the simulation time appropriately, to determine the point where steady state conditions begin. This is the time the simulation needs to warm up. Note that time in your report. Then do one more run with simulation time at least 10 times the warm up time.

PROGRAMMING NOTES

My preference is to implement everything as a separate process. However, as long as you have some processes, you may implement part of the project as threads. For example, you may implement aircraft as threads. I would like to see the event handler, aircraft generator and any other processes you design into your program implemented as processes.

If you use sockets:

The nice thing about sockets is that you can run aircraft processes on different machines. If you opt for socket IPC, you need to have a receiving process on the machine the event handler runs on to communicate with the aircraft processes. In this case, you may spawn a thread for each aircraft, whose job is to relay imformation on behalf of the remote aircraft process. For example, when an event needs to me delivered to an aircraft process, it is first delivered to the corresponding thread and then the thread relays the event to the remote process.

Changelog

4/6/11 - V1.2: Changed pseudocode for aircraft and event handler - they must lock the schedule
4/5/11 - V1.1: Added AAT and ADT imput parameters and approriate entries in the aircraft process. Changed input parameters AT and TT from fixed values to averages (AAT and ATT).