University of Victoria Faculty of Engineering

Lab 3 : Project 3
CENG 455 : REAL TIME COMPUTER SYSTEMS Faculty of Engineering University of Victoria Victoria, British Columbia

Michael Ryan K. April 10, 2011 Submitted to:

In partial fulfilment of the requirements of the [Link]. Degree

Introduction
The objective of this lab was to develop a real-time system capable of handling soft and hard periodic or aperiodic deadlines. For this lab, it was decided to model the real-time system based off of an elevator control system. Sporadic hard deadlines would be set for the top and bottommost floors, in which those floors must be serviced within 15 seconds of when the button was pressed. Aperiodic soft deadlines would be used for the floors in between, in which these floors are allowed to surpass their 15 second deadlines, but would merely increase in priority if they did. This lab report will discuss briefly the requirements set for the elevator control system, the highlevel design decisions that were made and the some of the important low-level implementation details.

Requirements
The project was expected to implement the basic functionality of an elevator control system. It needed to demonstrate both hard and soft deadlines for periodic or aperiodic tasks. Additionally it was expected that at least a minimal amount of hardware would be interfaced into the design. The proposal for the elevator system is attached as an appendix. However a general overview of the proposed design is provided as follows. The simulated elevator was to have a total of 8 floors. The elevator starts at the ground floor after a system reset. There are three different ways to request a floor to be serviced. From each floor, a user can request to be picked up by the elevator to travel up or down. Also from inside the elevator, a user may request to travel to any floor. These service requests simulate the interfaces available on a typical elevator system. A hold button will also be provided to simulate the doors hold functionality. When this button is pressed the elevator will wait at a floor until the button is released to allow passengers to load. When requests are received by the elevator they will be serviced in the order of priority. The priority of the floors is manipulated such that the elevator will follow a pattern when servicing the floors. The elevator has two traveling states- either up or down. When the elevator is traveling up it will stop to pick up any requests for upwards travel that originate from a floor above its current location. It will also drop off any goto requests for floors above its current location; however, it will not stop for a floor with a down request until it has completed its upward path. Similarly if it is traveling downwards it will pick up down but not up requests. If the elevator has serviced all requests it stops at the current floor and sits idle until a new request is received.

All floors have a soft deadline which when exceeded will increase the priority of the request slightly so that the floor is serviced sooner. The first and the topmost floor instead have hard deadlines, which must be serviced before they are exceeded. This is because it was assumed that the top most and bottom most floors will have the largest amount of traffic. Once the basic functionality was implemented the elevator hold function was added. This would allow the elevator to be held at a floor to simulate the door hold button which is typically found in an elevator. This functionality could also be easily expanded such that an emergency stop button or other high priority inputs could be added. Initially the interface of the elevator was to be the computer terminal where the commands UP, DOWN, GOTO HOLD and UNHOLD are to be implemented. Also output indicating the current state of the elevator was to be displayed using the terminal. The final functionality to be implemented was to add pushbutton inputs which would be serviced using an interrupt service routine. Also the current location of the elevator and which floors were requesting service was to be shown using LEDs.

Design Discussion
Many different high level design approaches were explored. Block diagrams of several possible solutions are attached in appendix D. The final design block diagram is shown in the following figure.

Fig 1: Block Diagram of System

Input to the system can be from either the computer terminal or the pushbuttons on the development board. Output which shows the current state of the system is provided both on the serial terminal and the LEDs on the development board. As shown in the block diagram, the real time system comprises of the following main components which will be discussed more in detail in their corresponding sections. The UART ISR and the Pushbutton ISR which provide input to the system. The UART ISR also serves a second purpose of sending output text to the serial terminal. The handler task accepts characters from the UART and also provides basic text editing capabilities. If an input command is recognised, the handler sends it to the scheduler task. The scheduler task accepts input commands from the handler task and the push button ISR. It also maintains the priority queue which is used to organise the priority of the tasks and to provide information about the next action to the elevator task. The elevator task maintains the state of the elevator and performs the process of moving the elevator between floors. The action tasks are created by the scheduler and maintain timing information about each floor request. If a floor request deadline is approaching the action tasks notify the scheduler to modify the priority queue.

UART ISR
The UART ISR is responsible for two things-- reading the received input from the Computer Terminal to send to the handler input queue, and sending data from the output queue to the serial channels transmit buffer. The UART ISR was almost unchanged from project 2.

Handler Task
The handler task is designed to handle input from the UART interrupt service routine through an input queue, and send any recognized requests to the Scheduler task. Depending on the character received, the handler task will either send the output to the output queue to be printed by the serial channel, or send a stream of characters to clear messages from the terminal. Although the main input driving the elevator control system comes from push buttons, if a return character is received from the UART ISR, the Handler Task will interpret the command in the line buffer by calling the read input function and send any recognised commands to the scheduler task.

Scheduler Task
The scheduler task waits for requests on its input queue, and performs the correct action from the type of input received. If the input is a new floor request, the scheduler is responsible of adding new requests to the Elevator tasks priority queue and spawning a new action task to monitor the time the request takes. If the request is the hold button, the scheduler signals the Elevator to stay at the floor if it is stopped. The scheduler will also receive responses from the

action task if a hard deadline is approaching or if a soft deadline is reached; in which case it will increase the priority of its associated item in the Elevators priority queue. After it is done servicing the request, it will check to see if there are entries in the priority queue, and alert the Elevator task that a new request has arrived.

Action Tasks
Action tasks are created by the scheduler every time a floor request is made. They can either represent soft or hard deadline actions. If it is a soft deadline, the task waits for the duration of the soft deadline timeout before it notifies the schedule and gets its priority raised. If it is a hard deadline, the scheduler is notified the moment it recognizes it might not have enough time to complete its request, to raise its priority to a maximum. When the request is finished being serviced, the Elevator task is responsible for destroying the associated action task.

Elevator Task
The elevator task monitors the priority queue for the next floor request and maintains the current state of the elevator. When there are no floor requests in the priority queue, the elevator waits until a new request arrives. When a floor request is received, the elevator will begin moving towards the appropriate floor. The elevator mimics reaching floors by waiting for one second to travel one floor, and at each moment it reaches a floor, the elevator checks to make sure a higher priority request hasnt arrived. Eventually it will reach the highest priority floor to be serviced, in which it will remove the request from the priority queue, destroy its associated action task and wait at the floor for 4 seconds as it services new passengers. At this point it checks to see if a hold request was received before attempting to service a new request.

Pushbutton ISR
Input from the pushbuttons was handled using an ISR. It was found that it would only be possible to implement pushbutton inputs for 4 floors instead of 8. A total of 11 inputs were needed to implement 4 floors-- 3 for up request buttons, 3 for down request buttons, 4 for goto buttons and one for the hold button. A block diagram describing the Pushbuttons interaction with the ISR is seen below.

Fig 2: Block Diagram of Push Button Inputs

Implementation Discussion
The implementation of the Elevator Control System involved first porting the UART ISR and Handler Task code into our system. Next, the Scheduler was implemented to verify the correctness of the input received by the Handler Task, along with the priority queue to verify that requests are queued properly. This was followed by implementing the Action Tasks to verify a tasks behaviour once it is suspended, and both the verified task suspending behaviour and priority queue implementation was used to implement the Elevator task. Finally, the Pushbutton ISR was implemented to provide proper interfacing with the Elevator Control System.

UART ISR and Handler Task

As mentioned before, the UART ISR and Handler task implementations were pulled directly from the previous work done in lab 2. In lab 2 however, the Handler task was designed to interface with a master task, which was designed to interpret the input before spawning user tasks to handle the request. In this system, the Scheduler task does all of the work of creating new action tasks and maintaining the elevator; therefore, a master task is not needed. In this case, the Handler Task code was modified to deal with interpreting the command before sending a command request to the Scheduler.

Priority Queue
Due to the complexity of the messages that are sent to the Elevator task, a simple message queue to pass messages to the Elevator task does not suffice. Therefore, a Priority Queue was custom implemented for the system, and it plays an integral part in making sure the correct

request gets serviced by the Elevator. This was designed alongside development of the Scheduler task, and the behaviour was verified by creating the queue in a separate application before porting it to the Elevator Control System. By implementing it in a separate application, the priority queue can be developed without making the behaviour of the Elevator Control System unpredictable. The priority queue had to be designed such that the top-most item was always the item with the largest key, items can be pulled from anywhere within the queue and have their priorities change dynamically, while keeping its sorting maintained. For this application, the queue was designed as a binary max-heap using an array. Enqueuing was performed by adding the bottom to the bottom of the queue and sifting up until it is in its right sorted place. Deleting an entry in the queue is done by replacing it with the bottom-most entry in the queue and sifting down until it is in its right sorted place. A function to recalculate all of the entries in the queue was implemented by changing all the keys in the queue and resorting only the parent entries rather than removing all the items and putting them into another queue. By only resorting the parent entries, the queue can be recalculated as fast as possible, in linear time. A separate function to change the priority of only one entry was also created, in the case where the priority of one task needs to be raised. Changing the priority of only one entry is done by sifting up and sifting down to maintain its ordering, and this allows priority changing of one item to take only logarithmic time, rather than the linear time spent to resort the whole queue. Once the functionality of all these priority queue methods are confirmed, they were ported to the Elevator Control System. The Scheduler task will be responsible for placing requests onto the queue and changing their priorities on the fly, while the Elevator task will be responsible for removing requests from the queue and reading their priorities at any given time. Since it is possible for both of these tasks to be doing any of these operations at the same time, a mutex lock was created to serialize the actions made to the queue. The key used on the entries within the priority queue are made in such a way so that high priority requests get serviced first, followed by requests in the same orientation of the elevator, followed by requests with the shortest distance. If the distance to the requested floor is negative (in the situation where the floor was already passed), the priority of these requests must be made the lowest.

Action Tasks
Action tasks are created by the Scheduler task with the requests direction and designated floor. To ensure this data is provided to the action task when it is created, this information is passed through the initial_data parameter of the task. When the initial data is interpreted from the task, in the case of a soft deadline, the task is blocked for the soft deadline timeout time and is awaken to notify the scheduler to change its priority.

In the case of a hard deadline, the task is blocked and awaken every second to make sure there is enough slack time remaining for the task to complete, given the time remaining to complete the task and the current destination the elevator is servicing. Unfortunately, due to the Elevators ability to preempt itself when a task of higher priority arrives and the cases which the Elevator is held for long durations, the time required to service the current request is often unpredictable, and the time remaining for hard deadlines will often surpass the time required. Therefore, it is possible for these hard deadlines to get passed. In cases where the hard deadline is about to be passed, the scheduler is notified so that these requests get serviced as soon as possible.

Elevator Task
The state of the elevator is maintained through several global variables which define the elevators current floor, orientation, destination floor and action. When the Elevator is in its idle state, the Elevator task is suspended until the Scheduler task alerts the Elevator that a new request has arrived. The Elevator task then peeks at the entry from the top of the priority queue to know which request it needs to service and changes to a moving state. In its moving state, the elevator is suspended periodically in one-second intervals in which it changes the Elevators current floor, recalculates the priority queue to update all the keys to consider the new current floor, and checks if a new request of higher priority has arrived. However, the request of higher priority only preempts the old request as long as it doesnt suddenly change the orientation of the Elevator. Once the Elevator task has reached its destination floor, the elevator state is changed to at floor. At this moment, it destroys the associated action task and deletes it from the priority queue to signify the request being serviced. The task waits 4 seconds to mimic passengers being serviced by the elevator and afterwards, determines whether the elevator should be held by the hold button state. if it does, the Elevator task is suspended until an unhold command is received by the Scheduler.

Pushbutton ISR
The edgeport of the processor allows for rising, falling or level-sensitive interrupts. Unfortunately, only two edge port pins are available on the development board. This presented a problem in implementing the pushbutton inputs. To work around this a circuit was designed which is shown in figure 2. This circuit connects the pushbuttons to both the IRQ1 pin and the GPIO pins of ports TC, TA and QS. The IRQ1 interrupt was setup to be sensitive to rising edges in the pin IRQ1. When the ISR runs it first disables interrupts then immediately records the state of the three input ports. As long as the pushbutton is not released before the ISR runs then the correct input is recorded. To help ensure that the ISR runs before the input changes a simple debouncing circuit was added to the inputs, this consists of an inexpensive resistor and capacitor lowpass filter. If a valid input is detected when the ISr runs then the corresponding UP, DOWN, GOTO or HOLD request is sent to the scheduler task.

Conclusion
An elevator control real-time system capable of handling soft and hard aperiodic deadlines was successfully implemented and demonstrated using Action tasks, a Scheduling task and an Elevator task. Since a simple message queue was unable to handle the changing priorities of requests within the system, a custom priority queue was designed to organize which request the Elevator serviced. Several challenges were encountered during the implementation of the design. There was too few edgeport pins available available on the development board so it was necessary to develop additional external circuitry. Due to the Elevators heavy variation in slack time and the Elevator needing to service people before servicing itself (e.g. the hold button, being unable to change orientation while moving), the Elevator was also prone to missing deadlines. Despite these issues, the system was generally able to successfully service the requests it was given.

Appendix
Appendix A: Pseudocode
Action Task Interpret the parameter passed to the action task. if hard deadline set hard timeout else set soft timeout Set direction of travel of elevator light up LED corresponding to floor request print message indicating floor request if hard deadline suspend until there is only the minimum amount of time available to complete the hard deadline send message to scheduler to notify that the hard deadline is approaching. else suspend for soft deadline timeout send message to scheduler to notify that a soft deadline has passed. block task Elevator Task Loop if PQ empty then suspend, wait to be readied by scheduler else check PQ elevator is moving print message indicating direction of travel and destination floor while current floor is not destination floor wait 1 second move one floor update LEDs using functions

recalculate PQ check for preemption of task end while Remove task from PQ wait 4 seconds print servicing passenger at floor # if HOLD suspend, wait to be readied by UNHOLD cmd from scheduler End Loop Scheduler Task Loop Receive message from queue Switch Case CMD_UP Create Request Parameters to pass to Action Task Create Action Task Add to PQ Case CMD_DOWN Create Request Parameters to pass to Action Task Create Action Task Add to PQ Case CMD_GOTO Create Request Parameters to pass to Action Task Create Action Task Add to PQ Case CMD_HOLD hold elevator Case CMD_UNHOLD unhold elevator make elevator task ready Case RESP_UP_TO_CRITICAL: update priority of task to critical Case RESP_DOWN_TO_CRITICAL: update priority of task to critical Case RESP_UP_TO_HI: update priority of task to hi Case RESP_DOWN_TO_HI: update priority of task to hi End Switch if elevator idle and PQ size > 0 then make elevator task ready

End Loop Main Function Initialize mutex attributes Initialize the priority queue mutex Initialize the print queue mutex creatoutput_queue creat h_message_pool creat scheduler_message_pool Setup UART_ISR Setup input Setup output Create Handler Task Create Scheduler Task loop forever delay end loop UART_ISR Loop: If there is a new character received Send character to handler task If there is a new character to send and UART is ready to send Send character to over serial channel End Loop IRQ1_ISR Check the input ports .... Case: No Pushbutton pressed if hold state exit hold state send to Schedular message DOWN else enter hold state send to Schedular message DOWN

Pushbutton 1: Down 4 send to Schedular message DOWN to 4 Pushbutton 2: Down 3 send to Schedular message DOWN to 3 Pushbutton 3: Down 2 send to Schedular message DOWN to 2 Pushbutton 6: UP 3 send to Schedular message UP to 3 Pushbutton 7: UP 2 send to Schedular message UP to 2 Pushbutton 8: UP 1 send to Schedular message UP to 1 Pushbutton 9: GOTO 1 send to Schedular message GOTO to 1 Pushbutton 10: GOTO 2 send to Schedular message GOTO to 2 Pushbutton 11: GOTO 3 send to Schedular message GOTO to 3 Pushbutton 12: GOTO 4 send to Schedular message GOTO to 4 default: do nothing End Case Handler Task Loop: Wait for new command message Case: Message is a new character If the character is printable Add character to line buffer Echo the character to the UART ISR Else if the character is a special character Handle it appropriately Else if the character is backspace Echo backspace character to the UART ISR Else if the character is a carriage return Call readInput(Line_buffer) to send command to scheduler Clear line buffer Echo newline character to the UART ISR Else if the character is none of the above Ignore it and discard the character

End Case End Loop readInput(line_buffer) function Parse command and floor number Interpret command if UP send to Scheduler message UP to Floor number else if DOWN send to Scheduler message DOWN to Floor number else if GOTO send to Scheduler message GOTO to Floor number else if HOLD send to Scheduler message HOLD else if UNHOLD send to Scheduler message UNHOLD else if EXIT exit MQX setup Input function UNMASK (IRQ1) INTERRUPT SET INTERRUPT LEVEL 3 PRIORITY 3 ENABLED INTERRUPT FOR EPORT0 PIN 1 DATA DIRECTION (INPUT) FOR PORT RISING EDGE SENSITIVE LOCATE ISR ROUTINE // GPIO Input SETUP /// //PORT TC Set to GPIO Set to inputs //PORT TA Set to GPIO Set to inputs //PORT QS Set to GPIO Set to inputs

} Setup Output //PORT AN Make Port AN Outputs Turn off all LEDS

LED_at_floor(int floor_number) Turn on only LED that corresponds to floor_number turn others off LED_floor_req(int floor_number) Turn on LED that corresponds to floor_number LED_floor_serviced(int floor_number) Turn off LED that corresponds to floor_number getPriorityWeight(Priority Type) Calculates the priority weight based on the orientation of the elevator and the weight of the request. Returns the following: 0-1: UP and DOWN (based on orientation) 2-3: HIGH_UP and HIGH_DOWN (based on orientation) 4: CRITICAL -1: Otherwise (error.) calculateKey(PRIORITY_TYPE p, int floor) Get distance (from orientation of elevator) The shorter the distance, the higher the priority If the distance is negative, the request would have just missed the elevator's oriented path. Therefore, the distance would lower the priority. return key print(string) Global function designed to send streams of output to the serial channel, since using printf() yields unexpected behaviour.

Priority Queue Functions pqueue_init() allocate memory for Priority Queue pqueue_siftUp(int i) pqueue_siftDown(int i) pqueue_enqueue(int floor, PRIORITY_TYPE p, _task_id task) insert element into the queue pqueue_delete(int i) remove element i in queue pqueue_dequeue() remove top element pqueue_peek() show top element pqueue_resort() resort PQ pqueue_recalculate() recalculate all keys of elements in PQ pqueue_cmpKeys(PQ_NODE_PTR p1, PQ_NODE_PTR p2) compare the keys of two nodes pqueue_changePriority(int floor, PRIORITY_TYPE old_p, PRIORITY_TYPE new_p) Finds the node, changes its priority, resorts the queue pqueue_nodeExists(int floor, PRIORITY_TYPE p) checks to see if a node exists

Appendix B: Example Input and Output

ELEVATOR: Sitting idle. Make a request. down 4 Floor 4 (DOWN): Action Task Created. ELEVATOR: Moving to floor 4 (from floor 1) down 2 Floor 2 (DOWN): Action Task Created. up 3 Floor 3 (UP): Action Task Created. ELEVATOR: Servicing passengers at floor 4... up 1 Floor 1 (UP): Action Task Created. ELEVATOR: Moving to floor 3 (from floor 4) ELEVATOR: Pre-emption! Now moving to floor 2 (from floor 3) ELEVATOR: Servicing passengers at floor 2... down 2 Floor 2 (DOWN): Action Task Created. ELEVATOR: Moving to floor 2 (from floor 2) ELEVATOR: Servicing passengers at floor 2... Floor 1 (UP): Hard Deadline approaching. Alerting Scheduler... down 4 Floor 4 (DOWN): Action Task Created. ELEVATOR: Moving to floor 1 (from floor 2) Floor 3 (UP): Soft Deadline passed. Alerting Scheduler... ELEVATOR: Servicing passengers at floor 1... ELEVATOR: Moving to floor 3 (from floor 1) ELEVATOR: Servicing passengers at floor 3... Floor 4 (DOWN): Hard Deadline approaching. Alerting Scheduler... ELEVATOR: Moving to floor 4 (from floor 3) ELEVATOR: Servicing passengers at floor 4... ELEVATOR: Sitting idle. Make a request.

Appendix C: Design Block Diagrams

Appendix D: Source Code