Full Writeup

CS164 Final Project Writeup

The Problem
Real-time programming can be difficult enough ensuring the code actually can complete running within the time limit, without worrying about ensuring the time itself is correct as well. There is also the alert system to deal with, should the deadline actually be reached - what kind of message should be sent? What is the right alert to help the programmer fix the issue?

The Idea
Our final project seeks to alleviate the real-time programmer's workload regarding deadlines. Rather than having the programmer deal with the messy plumping of creating a deadline timer each time, we intend to extend the Project 3 code and create a generalized deadline construct that will wrap around whatever code is real-time dependent and set off a notice if the deadline is reached before the code has finished running. The programmer merely needs to provide the time-sensitive code he or she wants to wrap, as well as the amount of time in milliseconds said code can take the run.

Roadblocks
Timers themselves can be potentially tricky business, but when one throws in code to keep track of on top of that, the construct will need to ensure it has everything straight. In addition, if the deadline is hit and the code has not finished running, the construct must deal with interrupting the code, and dealing with the consequences as the programmer would like to. Too, one must have some simple and straightforward message system to alert the user when the deadline is hit.

Why?
This project is worth working on because real-time computing itself is important, and any steps to make it easier can only help the larger issue.

Comparisons Against Current Solutions
For Java, RTSJ has introduced two new thread types, RealtimeThread and NoHeapRealtimeThread, as an extension of Java's Thread class. RTSJ also creates two timer classes - OneShotTimer and PeriodicTimer - in which the thread is then managed.

Why create our solution then, which seemingly does the same thing? Issues of Java aside, the timer and thread classes RTSJ provides still necessitate a lot of busy work and ugly plumbing, where a coder can easily make an error. We seek not only to offer a solution, but provide a clean, elegant solution that is simple to use.

Test code
import javax.realtime.PeriodicParameters;
import javax.realtime.RealtimeThread;
import javax.realtime.RelativeTime;

public class PeriodicHello extends RealtimeThread { //Set up task to be completed within deadline

PeriodicHello(PeriodicParameters pp){ //Time limit

super(null, pp);

}

public void run(){ //Run for 30 periods, for consistency

for (int i = 0; i < 30; ++i) {

System.out.println("Hello periodic world!");
waitForNextPeriod();

}

}

public static void main(String [] args){

PeriodicParameters pp = new PeriodicParameters(

new RelativeTime(500, 0));

PeriodicHello rtt = new PeriodicHello(pp);
rtt.start(); //Start thread to print periodically
try {

rtt.join();

} catch (InterruptedException ie) {

// ignore

}

}

}

Features
The domain of our language will be real-time programs that needs some sort of deadline enforced. For example, there could be a program that controls a mechanical arm that reacts to a sensor input. However, if for some reason the arm does not react fast enough, the safety of the system cannot be guaranteed and the arm needs to reset to a default position or shut down.

We will extend the 164 language to have a sense of execution time. We can encapsulate code into deadline structures which are essentially functions that check the time before each instruction. If it reaches the deadline before the function returns, then we throw an exception that the programmer must handle.

Sample Code

1. Infinite loop detection

def x = input()

deadline (1000) {
    while (x != 0) { # We forget to check if x is positive
        print x
        x = x - 1
    }
} catch {
    print "Infinite loop detected"
}


2. Nested deadlines

def x = input()
def y = input()
def z = input()

#Outer Deadline
deadline(4000){
    def i = 0
    while (x > i) {
        i = i + 1
        def j = 0
        
        #Caught Inner deadline
        deadline(1000){
            while (y > j) {
                j = j + 1
            }
            print "y is small enough"
        } catch {
            print "y is too large"
        }
        
    }
    i = 0
    
    #Uncaught inner deadline
    deadline(500){
        while (z > i){
            i = i + 1
        }
    }
    
    print "x*y+z is small enough"
} catch {
    print "x*y+z is too large"
}


3. Emergency Shutdown

# define classes
def Object = {}
Object.new = lambda(self,o) {
    o = cond(o != null, o, {})
    o.__mt = self
    self.__index = self
    o
}
# A device is connected to the hub.
def Device = Object:new({})
# Device.shutdown is a method that safely shuts down the device.
Device.shutdown = lambda(self){
    def i = 0
    # Waste some time in a loop to simulate a delay.
    while (i < 1000){
        i = i + 1
    }
    print "Device has safely shutdown"
}

# Add devices to the hub
def i = 0
def x = input()
def deviceHub = {}
while (x > i){
    deviceHub[i] = Device:new({})
    i = i + 1
}

# Error detected in system. We need to shut everything down.

# First try to shut everything down safely
deadline(1000){
    for device in listIter(deviceHub){
        device:shutdown()
    }
} catch { # If it takes too long, immediately cut power to everything to prevent further damage.
    print "Cutting power to all devices. Devices may be left in a bad state."
}
print "All devices shutdown."

Implementation Ideas

1. Create a deadline clause that includes the code needed to run within the deadline. These clauses will have associated "catch" that will execute if the deadline is not met.
   
• Frontend: We will parse and interpret our code using the Project 3 language parser and interpreter
• Core Language: We will be extending the function objects of the Project 3 language to allow for timers to run in parallel to the code that will ensure deadlines are kept track of. The deadline clauses will be sugar for argument-less, return-less functions and an immediate call.
• Internal Representation: This will be kept in byte code similar to Project 3.
  
• Interpreter/Compiler: We will use the same tool chain as the 164 language we developed in Project 3. The new clause requires that we build it into the language and the 164 language is simple to modify since we already have a good understanding of how it works.
• Debugging: We will test the code using small programs and using infinite loops to test deadline functionality.
  


2. Create a special deadline object that starts a timer and interrupts the control flow if the timer goes off. When it goes off, the object will call a function that it was built with.
   
• Frontend: We will parse and interpret our code using the Project 3 language parser and interpreter.
• Core Language: We will be extending the Project 3 language with new deadline objects. These objects will be similiar to coroutines in that they will be executed outside of the normal control flow and will return the control after it completes.
  
• Internal Representation: This will be kept in byte code similiar to Project 3.
• Interpreter/Compiler: We will use the same tool chain as the 164 language we developed in Project 3. The new internal objects require that we build it into the language and the 164 language is simple to modify since we already have a good understanding of how it works.
• Debugging: We will test the code using small programs and using infinite loops to test deadline functionality.

Actual Implementation
The syntax we chose for this implementation was to make deadline a structure like if statements and while loops. The grammar is 'deadline' E '{' S_list '}' 'catch' '{' S_list '}' though the catch statement is optional. Code within the deadline structure executes in the environment that the deadline is executed in. This is the natural semantics that come from this sort of syntax as it is the same for if statements and while loops. If a deadline is not met within the loop, the execution of the statements in it is immediately halted. No guarantees can be made about the state of the execution and environment when the exception occurs. It is up to the programmer to either make the program fail safely or fix the state of the environment. We chose to do this because we would take a performance hit if we tried to restore the state of the environment and possibly cause the deadline problem to be worse. It is also expected that programmers understand that an exception is a large issue that implies that a function is in an unexpected state and not safe anymore.

We also had to decide on the semantics of uncaught exceptions. We had three choices, we could halt the execution of the statements in the deadline and go on to the next statement outside the deadline but that would lead to many unsafe states that the programmer would have to take into account before continuing. We could force the program to terminate immediately, but that would probably be overkill. We chose to instead escalate the exception up the call stack until it reached a catch statement or the top level. This mimics the behavior of exceptions in Java and allows the programmer more freedom and requires less plumbing.

Our current implementation runs into some limitations. First, we do not support the timing out on the expression input() statement and I/O in general. This is because check the deadline only at the beginning of execution. Since input() blocks, it will stay there indefinitely and we will not get a chance to check the deadline. Second, we do not yet support catch structures without an associated deadline. Including this would allow for more flexible exception handling similiar to that of Java. Finally, on a more theoretical note, any code that is run within a deadline structure is not Turing-complete because the deadline enforces a limit on the number of steps that can be done in the code. This is expected since any code within a deadline structure is guaranteed to halt which would solve the halting problem for this code. This is a case where we trade in power for safety and reliability.