============================ CS 452 Real-Time Programming

This is the source code for a real-time operating system written by Robert Elder and Christopher Foo for CS452. This operating system was written for the purpose of runnings a set of user tasks that control a model train set. The operating system is cross-compiled and downloaded to a TS-7200 board attached to a peripheral on the main computers in the CS452 lab.

You can read more about this project and see pictures here:

http://www.robertelder.ca/my-uw-journey/#cs452

This repo contains folders for each milestone of the project. The final project source code is located at io/project-final

========= CS 452 PF

:Names: Robert Elder, Christopher Foo :Date due: July 31, 2013

Running

The executable is located at /u/cs452/tftp/ARM/relder-chfoo/pf-submit/kern.elf.

The entry point is located at 0x00045000 or %{FREEMEMLO} It must be executed with caching enabled. (Caches not enabled by the program itself due to time contraints)::

load -b %{FREEMEMLO} -h 10.15.167.4 ARM/relder-chfoo/pf-submit/kern.elf
go -c

Commands ++++++++

tr TRAIN SPEED Set the train speed.

rv TRAIN Slows, stops, and reverses train. The final speed is hard coded to 5.

sw SWITCH DIRECTION Changes the turnout direction. DIRECTION is either S or C.

q Quits the program.

map NAME Sets the current track. NAME should be A or B.

Figure 2 and Figure 3 show different map configurations.

.. figure:: io/project-final/figure2.png

Figure 2

go TRAIN Begins the train route finding process. The train should start up, find position, and go to a random destination.

gf TRAIN Like go, however, this make the train go forever by running go in an continuous loop.

num TRAINS Set the number of trains to be used.

paint Causes the interface to redraw itself.

rt Resets the train system by stopping the trains, clearing reservations, and clearing train engine states.

rps Runs Rock Paper Scissors program.

Pressing 'CTRL+Z' will cause the program to dump out a list of tasks information and statistics. This is considered a debug operation, and as such it can cause future instability in the program.

Pressing CTRL+C will cause the program to exit immediately without shutting down the tasks.

Getting Started Quickly

To start up two trains

1. Select the appropriate map using the map command.
2. Set the number of trains to be used using num command.
3. Enter the first train using go TRAINNUM1 0
4. Enter the second train using go TRAINNUM2 1
5. If things go wrong, use the rt command

Description

Kernel ++++++

• No kernel changes since last deliverable.

.. figure:: io/project-final/figure1.jpg

System Calls

• System calls support up to 5 arguments.
• No changes since last deliverable.

Create Returns the new task id, ERR_K_INVALID_PRIORITY -1, or ERR_K_OUT_OF_TD -2

MyTid Returns the current task id

MyParentTid Returns the parent task id. The parent task id is always returned regardless of the parent's state.

Pass (Rescheduling happens as normal in the background.)

Exit Task is marked as ZOMBIE (and rescheduling happens as normal in the background).

Send Sends a message to the given task ID. -3 code is not implemented.

Receive Blocks until a message is received. Returns the size of the message which will be typically MESSAGE_SIZE 16

Reply Replies a message to the task. On errors -3 -4, an assert will fire before returning to aid in debugging.

RegisterAs Prepares a NameServerMessage structure with a message type of REGISTER_AS and sends the message to the Name Server. 0 is always returned because the Task ID is hard-coded and the call should never send to the wrong task.

WhoIs Prepares a WHO_IS message type and sends it to the Name Server. As noted in RegisterAs, we either return a Task ID or 0 if the task has not been created. However, the task ID returned may be in a zombie state.

AwaitEvent Marks the task as EVENT_BLOCKED. The task will be unblocked by the Scheduler. This call always returns 0 and the user task will be responsible for obtaining the data themselves. AwaitEvent supports only 1 task per event type.

Time Wraps a Send to the Clock Server. It first queries the Name Server for the Clock Server and then sends a TIME_REQUEST message. It expects back a TIME_REPLY message and returns the time.

Delay Similar to Time, it sends a DELAY_REQUEST message and expects back a DELAY_REPLY message.

DelayUntil Similar to Time, it sends a DELAY_UNTIL_REQUEST message and expects back a DELAY_REPLY message.

TimeSeconds, DelaySeconds, DelayUntilSeconds Same as above but in seconds. It simply converts the ticks into seconds before calling the system calls. These calls are simply for convenience.

Getc Sends a message to either Keyboard Input Server or Train Input Server. It will block until the servers have a character to return.

Putc Sends a message to either Screen Output Server or Train Output Server. The servers will place the character into the server's Char Buffer.

PutString Formats the string and calls Putc for every character.

PutcAtomic Like Putc, but accepts multiple characters and guarantees the characters are placed into the queue sequentially. This call is useful to ensure that two byte commands are not separated by a single byte command.

SendTrainCommand Sends a message type TRAIN_COMMAND to the Train Command Server. The call is for convenience.

PrintMessage Similar to PrintMessage, but this sends the string to the UI Print Server to be displayed on the lower half of the screen using a UI_PRINT_MESSAGE message type

Watchdog

The watchdog has been changed to report starvation after 500,000 schedules to be more strict in detecting this problem.

Scheduler

The scheduler now calculates the system load by counting the number of low priority schedules per 1,000,000 schedules. This may not reflect the true load as the Idle Task may take a long time slice before rescheduling. In the future deliverable, we may implement counting the time each task is scheduled.

Priorities

For this deliverable, we have thought carefully about the priorities of each task.

======================== ========== Task Priority ======================== ========== Clock Notifier 0 Clock Server 0 First Task 0 Name Server 1 Administrator 2 UART Bootstrap 3 Train IO Notifier 4 Train Input Notifier 4 Train Output Notifier 4 Keyboard Input Notifier 4 Screen Output Notifier 4 Train Input Server 5 Train Output Server 5 Screen Output Server 6 Keyboard Input Server 6 Train Server 7 UI Print Task 7 Train Command Server 8 Train Switch Master 8 UI Server 8 Train Sensor Reader 9 Train Engine 9 Train Server Timer 10 UI Keyboard Input 12 UI Timer 13 RPS Test Start 15 RPS Server 16 RPS Client 31 Idle Task 31 ======================== ==========

For more info, see Performance.

Assert ++++++

The assert statement, as usual, is enhanced to show Thomas The Tank Engine. Please do not be alarmed when you see it.

When an assertion failure occurs, the Stop command will be sent to avoid train collisions.

Serial IO +++++++++

File: uart.c

• FIFOs are now used for the terminal input/output.

Train Navigation ++++++++++++++++

File: route.c, tracks/track_data.c, train_logic.c, train_data_structures.h

Train navigation is currently accomplished using naive graph search algorithms, as well as a server called the SwitchMaster that is responsible for updating the positions of switches.

We have broken down the problem of navigation to anywhere on the map into two basic problems: The first is navigation to a point while considering the map as a directed graph. In this situation we only consider moving in the forward direction. In this context, it is not possible to navigate to anywhere on the map from all nodes because the graph is considered to be a directed one. In the second case, we consider the map as an undirected graph, where any shortest path can be found by finding the shortest route in the undirected graph. We can then express the problem of navigation between two points in the undirected graph as multiple navigations in a directed graph, while adding direction reversals in the middle.

To find a destination, a simple depth first recursive algorithm is used to build up a Route Info array. The Route Info array contains information about each track node and the switches it needs to switch. The algorithm avoids blacklisted switches.

Undirected Graph Model ++++++++++++++++++++++

In order to accurately model the train and its motion around the track, as well as predicted future positions on the track, we required another representation of the track to complemented the directed model that was provided. It is for this reason that we have created a undirected graph model of the track based on the directed graph model. This model also includes the trains as nodes, which enables us to apply standard graph-based algorithms to any nodes on the track graph, including the trains themselves. This has significant advantages for tasks such as sensor attribution, collision detection, and route planning. The advantage of including the trains as nodes in this model means that in this representation, we do no