Abstract.

This report describes the design and implementation of the logic part of the
application "The Green Elevator". The elevator application is based on the 
design pattern Model-View-Controller (MVC). We designed and implemented the 
Controller part (and a little of the Model) of the pattern both in Java (with 
RMI used to tie it together with the View) and in C with Pthreads (and TCP 
sockets to communicate with the other parts of the elevator application).

1. The Green Elevator application.

The Green Elevator application is a software simulation of a system of 
elevators. It follows the Model-View-Controller design pattern that separates 
the user interface (the View) with the application logic (the Model and the
Controller). The Model keeps track of the state of the application, for 
example which elevator buttons that has been pushed. The Controller defines 
the behavior of the application, i.e. what to do when a button has been 
pushed.

As the application uses Remote Method Invocation (RMI) in Java, the different
parts of the program (the user interface and the application logic) can
exist on different computers. Method references on objects are made just
like they would be if they were local calls inside the program. RMI handles 
the underlying plumbing (network and/or interprocess communication). As a
result an instance of an object running in one Java Virtual Machine (JVM) can 
invoke methods in an object running in a different machine.

Our Java version of the application logic uses RMI to communicate with
the graphical user interface and the C version accomplishes this by
sending (and recieving) messages through an ordinary TCP socket.

To be able to control several elevators at the same time in realtime, the 
application has to make use of threads (via java.lang.Thread in Java and
in C, the Pthreads library). Code running in a thread, runs in its own 
process in the operating system, with its own program counter and stack, 
but with shared memory. When more than one thread runs on a single
CPU, the application is said to be multithreaded.

Each of the elevators in The Green Elevator is controlled by an individual
thread. Also the part of the program that schedules (the scheduler) what
elevator should go where when, runs in a thread. The application is therefore
multithreaded.

When many processes share the same memory pages it often becomes neccessary
to control execution of certain sections of the code, so that only one process 
at a time can manipulate critical data in memory. One way to achive this is 
through mutal exclusion. In Java this is done by marking critical methods with 
the synchronized keyword and i C with Pthreads by calling mutex_lock() and 
mutex_unlock().

1.1 The elevator algorithm.

In a system of elevators we have several elevator cars that serve several
floors. If possible, we want to minimize the waiting time for a customer (a 
person who use the elevator system), minimize the time a customer has to 
ride the elevator until reaching his or her destination and minimize the 
power consumtion of the elevators (no unneccessary elevator movements).

A problem is that these constraints are in contradiction of each other, so 
we had to find a solution that was a reasonable compromise. We choose to 
implement the so called elevator algorithm. The main idea behind the 
algorithm is that each elevator serves all requests in one direction 
first, before changing direction. This minimizes the distance of travel for 
the passengers and avoids the problem of elevator starvation. Starvation 
is when an elevator rapidly changes direction to try and serve customers 
both above and below the car. This can lead to a customer far away from 
the elevator car's position never is served.

We also had to consider how to pick which elevator (when there are more
than one of course) that would go and pick up a person on a specific floor
and what direction that person wanted to go (i.e. if he requested an elevator 
moving up or down). The implementation tries to calculate a cost for an 
elevator to go to the requested floor and pick up the passenger. Then the 
scheduler picks the elevator with the lowest cost to serve the request (please 
see below for an explanation of what parameters are considered when calculating
the cost).

2. Elevator controller implemented in Java and RMI.

Our Java implementation of the application logic has two major parts, the
scheduler (control.Scheduler) and the elevator controller (control.Controller).
A simple linked list implementation of a queue is used by both the controller
and the scheduler (control.Queue).

2.1 The scheduler.

The control.Scheduler class' first task is to get RMI references to all
the elevators in the application and connect each elevator to its own
control.Controller object (which takes care of calculating the cost to
go to floors, moving the elevator car, opening the elevator doors etc etc).

After this initial phase, the scheduler's main task is to listen to the 
buttons on the different floors and if one is pushed, try to find the
best possible elevator (the one with the lowest cost) to serve that
customer. The scheduler runs in its own thread and waits for floor
button events in the control.Scheduler.run() method.

When such an event occurs the control.Scheduler.schedule() method asks
all the elevator controllers what the cost would be to move to the
requested floor and move the passenger in the requested direction (i.e.
if the customer wants to go up or down). The cost is returned by 
control.Controller.getCost() and the scheduler picks the elevator with 
the minimum cost (more information about the control.Controller.schedule() 
method below).

2.2 The controller.

The control.Controller class, as its name implies, controls an elevator's
actions (moving the elevator car, opening the doors and so on) and also
keeps track of its state. The elevator's state are things like its position,
direction of movement and planned floor stops. The floor stops are 
represented by two integer arrays, one for up stops and one for down stops. 
For example, if the third element of the array with the up stops is a 1, then
the elevator is going to make a stop at the third floor if it is moving up.
Likewise, 0's in the array mean "don't stop at this floor".

Like the scheduler, the controller runs in its own thread and the main
loop in the run() method waits for either position changes or pushed buttons 
inside the elevator car. If the position has changed, it checks if the
elevator is at a floor and if it should make a stop there (by looking in the 
stop arrays).

When a floor button inside the elevator is pushed, the controller handles
this by sending the request to the control.Controller.schedule() method
(just like the Scheduler does after it has figured out which elevator
to send the request to).

2.3 Calculating the cost of moving the elevator.

(HÄR SKA DET IN EN FÖRKLARING FÖR control.Controller.getCost())

2.4 The simple queue.

The control.Queue class is a small and simple java.util.LinkedList implementation 
of a queue. It is used by both the Scheduler and the Controllers to queue
java.awt.event.ActionEvents (in our case elevator position changes and different
button events) to be handled by their respective run() methods.

Both the control.Queue.enQueue() and the control.Queue.deQueue() methods needs
to use mutual exclusion (via the synchronized keyword in Java) to avoid any
possiblity of conflict. (ÄR DET VERKLIGEN SANT? JAG ÄR OSÄKER NÄR JAG 
TÄNKER NÄRMARE PÅ DET!)

3. Controller implemented in C with pthreads.

The C version of the elevator control mechanism mirrors the Java
version in that it uses the same basic algorithm and the same strategy
for calculating the cost of moving an elevator car to a specific
floor. Also, in both implementations the scheduler and each elevator 
controller (*) runs in its own thread. The C version does this by using 
the Pthreads library.

Most of the differences between the programs are due to the significant
difference in programming paradigm between the object oriented, data
centric Java and the imperative, top-down C. When we in Java could describe 
each elevators individual state (the up and down stop arrays, the car's 
position etc etc) in a well defined object, in C we have to keep track of 
the states of all elevators in global datastructures.

Another difference is that the C version has to use an ordinary TCP socket
to communicate with the rest of the application.

4. Performance of system.

5. Conclusions and lessons learned.

6. References.

7. Class documentation for Java Controller.

8. Source code for Java Controller.

9. Source code for C Controller.