TSEA81 - Datorteknik och realtidssystem

TSEA81 - Computer Engineering and Real-time Systems

Assignment 4 : Lift with Message Passing

Introduction

In this assignment, a real-time program for simulation of an elevator system is developed. The program shall use message passing for task communication and task synchronization.

A graphical user interface is used for presentation of lift movements between different floors in the building, and for visualisation of persons waiting for the lift, and persons travelling with the lift.

The purpose of the assignment is to provide skills and knowledge for implementation of a real-time program with message passing, using the C programming language and a real-time operating system.

Requirements to pass

The requirements to pass this assignment are:

• The developed software as required in Section Assignment tasks is demonstrated.
• The source code of the developed software is described verbally. The source code shall be well structured, and commented.

Preparations

As a preparation for the assignment, it is recommended to study the lecture note 4 - Monitors, Message passing. It is also recommended to revisit the design and implementation done in in Assignment 3 - Lift with Monitors, for evaluation of possible re-use of code. Typically the files lift.c and lift.h from Assignment 3 will be useful, though they need modification.

Required software

The assignment uses C and a message passing implementation based on POSIX Message Queues under Linux (although most of the details of the message queue implementation is hidden behind the messages.c wrapper). The assignment will also be evaluated during a lesson in the course, using computers running Linux. It is unlikely that this lab will work on either Windows or MacOS X due to the lack of the POSIX message queue standard on those platforms. You can download the following lab skeleton which is suitable for assignment: assignment4_20201109.tar.gz

Assignment tasks

A real-time program implementing a lift shall be developed.

Real-time program requirements

The program shall fulfil the following requirements:

• A lift shall move between floors in a building. The building contains floors, numbered from 0 (the top floor) to N_FLOORS-1 (the bottom floor).
• The lift shall move, repeatedly, from one floor to the next floor. The next floor is determined by the current direction of the lift.
• The lift shall change direction when it has arrived at the top floor, and when it has arrived at the bottom floor.
• The lift shall stop at every floor, here denoted the current floor. If one or more persons are standing at the current floor, or if one or more lift passengers would like to leave the lift at the current floor, the lift will shall wait. While none of these conditions are fulfilled, the lift shall continue its movement to the next floor (after the time period used in the lift_move function).
• There shall be functionality which allows a user to create a person, which then shall be placed on a randomly chosen floor. When the lift arrives at this floor, the person shall, if there is room in the lift, enter the lift, thereby starting a journey to another floor, here denoted the destination floor, which also is chosen randomly. When the lift arrives at the destination floor, the person shall leave the lift, and disappear. After a specified amount of time, e.g. 5 seconds, the person shall reappear, and start a new journey, again from a randomly chosen floor to a randomly chosen destination floor.
• It shall be possible to create at most MAX_N_PERSONS persons.
• There may be at most MAX_N_PASSENGERS passengers in the lift at a given time instant.
• A unique identity shall be assigned to every person. The identity shall be an integer number, between 0 and MAX_N_PERSONS-1.
• When a person is waiting for the lift, the identity of the person shall be displayed.
• When a person is travelling with the lift, the identity of the person and the destination floor for the person's lift journey, shall be displayed.
• Observe, that all waiting periods caused by sleep functions (e.g. usleep) is only there for us humans to be able to see what is happening. Meaning, if all sleep functions were to be removed (as shall be done in assignment 5 Performance analysis) everything shall still work (passengers being able to enter/exit lift without any problems).

Implementation requirements

The program shall be written in C, using POSIX message queues and processes for handling of parallel activities.

• There shall be one process, called lift_process, for the lift. This process is responsible for making sure that the lift moves to the appropriate floor, whenever appropriate, and also that passengers embark and disembarks from the lift, as appropriately.
• There shall be one process, called liftmove_process, that controls when the lift should move.
• The shall be one process for each person. All person tasks shall be implemented by the same C function, called person_process.
• There shall be one process, called uicommand_process, which receives commands from the graphical user interface. This task shall create new person processes. A new person process shall be created when the text string new is received. The task uicommand_process shall also contain functionality for termination of the program. The program shall be terminated when the text string exit is received.
• There shall be a uidraw_process which is responsible for sending draw commands to the Java GUI

The program shall use message passing, with the following defined message types:

/* message types for lift simulation */ 



typedef enum {LIFT_TRAVEL, // A travel message is sent to the list process when a person would
	                   // like to make a lift travel
	      LIFT_TRAVEL_DONE, // A travel done message is sent to a person process when a
	                        // lift travel is finished
	      LIFT_MOVE         // A move message is sent to the lift task when the lift shall move
	                        // to the next floor
} lift_msg_type; 

struct lift_msg{
	lift_msg_type type;  // Type of message
	int person_id;       // Specifies the person
	int from_floor;      // Specify source and destion for the LIFT_TRAVEL message.
	int to_floor;
};

A data type for the lift shall be defined, as follows:

/* definition of data type for lift */

typedef struct
{
    /* the floor where the lift is positioned */ 
    int floor; 
		
    /* a flag to indicate if the lift is moving */
    int moving;

    /* variable to indicate if the lift is travelling in the up 
       direction, which is defined as the direction where the 
       floor number is increasing */
    int up;

    /* persons on each floor waiting to enter */ 
    person_data_type persons_to_enter[N_FLOORS][MAX_N_PERSONS];

    /* passengers in the lift */
    person_data_type passengers_in_lift[MAX_N_PASSENGERS];

} lift_data_type;

typedef lift_data_type* lift_type;

The data type person_data_type, which is used in the above data structure, defines the identity of a person, and the number of the floor to which the person shall travel, according to

/* data structure for person information */ 
typedef struct
{
    /* identity */ 
    int id; 
    /* destination floor */ 
    int to_floor; 
} person_data_type; 

There shall be functions associated with the data type for the lift. Among these functions, one may have e.g.

/* lift_create: creates and initialises a variable of type lift_type */
lift_type lift_create(void); 

/* lift_next_floor: computes the floor to which 
   the lift shall travel. The parameter *change_direction 
   indicates if the direction shall be changed */
void lift_next_floor(
    lift_type lift, int *next_floor, int *change_direction); 

/* lift_move: makes the lift move from its current 
   floor to next_floor. The parameter change_direction indicates if 
   the move includes a change of direction. */ 
void lift_move(
    lift_type lift, int next_floor, int change_direction); 

/* get_current_floor: returns the floor on which the lift is positioned */ 
int get_current_floor(lift_type lift); 

/* enter_floor: makes the person with id id and destination to_floor stand 
   at floor floor */ 
void enter_floor(lift_type lift, int id, int floor, int to_floor); 

/* leave_floor: makes a person, standing at floor floor, leave the  
   floor. The id and destination of the person are returned in the 
   parameters *id and *to_floor */ 
void leave_floor(lift_type lift, int floor, int *id, int *to_floor); 

/* enter_lift: makes the person with id id and destination to_floor 
   enter the lift */ 
void enter_lift(lift_type lift, int id, int to_floor); 

/* leave_lift: makes a person, standing inside the lift and having 
   destination floor equal to floor, leave the lift. The id of the 
   person is returned in the parameter *id */ 
void leave_lift(lift_type lift, int floor, int *id); 

/* n_passengers_to_leave: returns the number of passengers in the 
   lift having the destination floor equal to floor */
int n_passengers_to_leave(lift_type lift, int floor); 

/* n_persons_to_enter: returns the number of persons standing on 
   floor floor */ 
int n_persons_to_enter(lift_type lift, int floor); 

/* lift_is_full: returns nonzero if the lift is full, returns zero 
   otherwise */ 
int lift_is_full(lift_type lift); 

The data type for the lift, and the associated functions, shall be implemented in two files, lift.h and lift.c. The remaining functionality of the program, e.g. the tasks, shall be implemented in one or more additional files. It is e.g. possible to use a file, denoted main.c, which contains code for all processes and the main-function of the program, and which includes the file lift.h. The file main.c can also contain other functions, which are used by the tasks e.g. for generation of a randomly selected floor number.

The data type for the lift shall be used as an abstract data type. This means that the data which belong to the data type are read and written only via functions, with function prototypes placed in the file lift.h. Additional functions, declared in lift.c but not visible via lift.h, can also be useful. These functions shall be defined using the reserved word static, in order to ensure that they are not visible outside the file lift.c.

Note that the requirements on lift.c and lift.h are partly fulfilled simply by copying these files from the previous assignment and removing all traces of pthread related code from them. There are also some functions that should no longer be static in these files (e.g. enter_lift and leave_lift).

Communication with a graphical user interface

Messages from the graphical user interface to the real-time program shall be sent as the text strings new and exit, according to the specification in Section Implementation requirements.

Messages from the real-time program to the graphical user interface shall be sent by calling a function which draws the lift, the persons that are waiting, and the passengers in the lift. The drawing shall be done in the same way as in Assignment 3 - Lift with Monitors, using the files draw.h and draw.c. Note that only one process (the uidraw_process) is allowed to call the draw_lift function. To ensure that this process gets the information required to draw the lift, a the lift_type data structure needs to be sent via a message to this process. (Code for sending such a message and acting upon it is already present in the lab skeleton.)

The graphical user interface uses image files which are loaded into the graphical user interface program, for the purpose of displaying the lift, the building in which the lift is moving, and the persons. This assignment uses the same image files as were introduced in Assignment 3 - Lift with Monitors.

For visual purposes, the liftmove_process sleeps for a certain amount of time between sending messages, about moving the lift, to the lift_process. The lift_process having received such a messages is also sleeping for a short time to visually display that the elevator doors are "closing and opening". Changing the timing of these sleeping periods may have undesired effects. For instance, if the liftmove_process sends messages more often, the lift_process might not have time to act upon these messages before more liftmove-messages arrive.

Implementation recommendations

The following recommendations may be useful.

Develop the program incrementally, in a step-by-step manner. A first step can e.g. be to create a lift which moves between the floors. A next step could be to introduce a person which travels between two specific floors. Then, more persons can be introduced, and random choice of floors can be implemented.

A unique identity between 0 and MAX_N_PERSONS-1 should be assigned to each person process. Unlike assignment 3 - Lift with Monitors, this identity can be passed directly as a paramter to the person_process function rather than a pointer to an int.

Processes and message passing

Unlike earlier assignments, this assignment will use processes rather than threads. The main difference between processes and threads is that a process doesn't share its memory space with other processes.

To create a process, the fork() function is used. When this function is run, an additional copy of the currently running process is made and the execution of both processes continue at the same location in the program (i.e. on the line after the call to fork()). The only difference is that the return value from fork() is zero in the newly created process and the return value from fork() in the original process is the process ID of the newly created process. (See the main() process in the lab skeleton for assignment 4 for an example of how a new process can be created.) The original process is usually called parent and the new process is called a child process.

Since a process does not share memory with its child processes it is not possible to communicate simply by making changes to a shared data structure. In this assignment we will instead use message passing to communicate between processes using an interface called POSIX Message Queues. However, to avoid unnecessary complications, wrapper functions in the file messages.c will be used. They are:

• message_init(void): Initialize the message wrapper
• message_send(char *msg, unsigned int length, unsigned int queueid, unsigned int priority): Sends a message of the specified length (in bytes) pointed to by the msg parameter to a receiver listening to the specified queue id. A priority can be used here, but in this lab it is recommended to set the priority to 0. If the receiving message queue is full, message_send will wait until there is space available for this message.
• message_receive(char *msg, unsigned int max_length, unsigned int queueid): Receive a message from the specified queue id. The caller is responsible for passing in a valid pointer to a buffer which is at least max_length bytes long here.

It is recommended that the following queue id:s are used for messages:

• #define QUEUE_UI 0: This queue id is used by the uidraw process to receive the lift_type data structure which is should draw with the draw_lift function. (This part is already implemented.)
• #define QUEUE_LIFT 1: This queue is used to send messages to the lift process.
• #define QUEUE_FIRSTPERSON 10: This queue is used to send messages to the person processes. QUEUE_FIRSTPERSON+0 corresponds to the person with id 0 and QUEUE_FIRSTPERSON+MAX_N_PERSONS-1 corresponds to the last person