Department of Electrical and Computer Engineering
Dalhousie University

ECED 4402 - Real Time Systems

Fall 2018

Last updated: 8 December 2018


Instructor

Dr. Larry Hughes
Department of Electrical and Computer Engineering
Dalhousie University

Room C-369
Telephone: +1.902.494.3950
E-mail: larry.hughes [at] dal.ca
URL: http://lh.ece.dal.ca

Assignment submissions

The only day for demonstrating assignments is 6 December 2018. Demonstrations will begin at 1pm. All assignments must be submitted by 430pm.

Final Examination

The examination will be 3 hours in length.

The final examination will be held in the Sexton Gym on 11 December 2018. The examination is 3 hours long, starting at 830am and finishing at 1130am. It is open book and open notes.

The following is a sample question from a previous examination:

In most implementations of UNIX, processes can block on more than one event. That is, rather than waiting on a single semaphore or receiving from a single message queue, the process can wait on multiple semaphores or multiple message queues. What advantage does such a capability offer? What changes would be required to the second assignment’s single message-queue recv() to extend it into a multiple message-queue recv()?

Course overview

ECED 4402 covers many issues relating to the design and implementation of a real-time system, a messaging-passing system, and a real-time application. The hardware being used in the course is the TI TM4C1294NCPDT (Tiva) microcontroller which has the ARM (Advanced RISC Machine) Cortex-M4 as its core.

Course outline

A copy of the course outline is available here.

A copy of Dalhousie's academic regulations is available here.

Class times and room

Tuesday: 11:35 to 12:55 in room D501
Thursdays: 11:35 to 12:55 in room D501

Lab times and room

Until further notice, labs will be held in D501 between 9am and 11am on Tuesdays.

Office hours

Tuesday: 10:00am to 11:30am and 1:00pm to 2:45pm
Thursday: 10:00am to 11:30am and 1:00pm to 5:00pm

Outside office-hours or class-time, contact me by email.

Tiva

The course processor, the TI Tiva, is included in your course fee. The processor is available from the electronic workshop.

Using the Tiva:

TI has some tutorials for the Tiva that can be accessed here. (Thanks to Sean for pointing this out.)

Assignments

The course's testing requirements are explained in the following document ECED3403-SoftwareTestingRequirements.pdf

Assignment 1

Assignment 2

  • Assignment 2 is now due on 6 November 2018.

  • For a copy of assignment 2, click here.

  • Accessing a process stack
    Structures and functions useful for accessing a process stack (to be discussed in class on 4 October 2018):
  • Starting the first process (Part I)
    Before the first process can be started, it is necessary to initialize all stacks and PCBs. The first process can then be started by forcing an SVC exception and passing control the SVC handler (part of the kernel). The SVC exception is simply a "call" to the SVC using the macro SVC() (see process.h).

    SVC() generates an SVC trap to the kernel via the SVC handler vector to the entry point, SVCall(). Note that since this is an exception entry point, it is necessary that the startup_ccs file be updated to include the address of the entry point in the SVC vector location. This change need only be done once.

    SVCall() is not the handler proper; its responsibility is to determine the stack (MSP or PSP), save state on the appropriate stack, and then call the handler, SVCHandler(). Since this is an exception, xPSR through R12 and R3 through R0 are pushed onto the stack by the hardware. Registers R4 through R11 are pushed using software.

    The first call to SVCHandler() starts the first process. Subsequent calls expect an argument to be passed (this will be discussed later).

    The following is required for compiling the code and starting the first process:


    Important: if SVCall() is called directly, your startup code will not work. It must be called "indirectly" as an exception using the macro SVC().

  • Starting the first process (Part II)
    Starting the first process requires:
    1. The PSP set to the first process's stack-pointer, found in the process's PCB. However, since the stack pointer in the PCB points to the registers to be pulled by software (i.e., registers R4 through R11), it is necessary to change the stack pointer so it has the address of the first register to be pulled when the LR indicates that the stack is to change to the PSP and thread mode.
      The stack pointer (in the PCB) must be incremented so that it avoids these eight registers. This value can be assigned to the PCB using set_PSP():
      set_PSP(running -> sp + 8 * sizeof(unsigned int));
      
    2. The initialization and starting of the system clock so that the next SysTick interrupt will preempt this process:
      systick_init();
      
    3. Putting the CPU into thread mode and making the PSP the active stack; this requires the LR value to be changed to the EXC_RETURN (exception return) value of FFFF.FFFD. This action overwrites the current LR value; however, since control is never to return to this location, it is not an issue.
      Explicitly changing the LR requires the use of two assembler instructions MOVW, moves 16-bit value to lower (least significant) 16-bits of a register, and MOVT, moves a 16-bit value to the top (most significant) 16-bits of a register. In this case, the register is LR:
      __asm(" movw     LR,#0xFFFD");    /* Lower 16 [and clear top 16] */
      __asm(" movt     LR,#0xFFFF");    /* Upper 16 only */
      
    4. Forcing a return via the value in the LR (0xFFFF.FFFD); this can be done with the assembler instruction BX:
      __asm(" bx     LR");          /* Force return to PSP */
      
      Note that since this is an EXC_RETURN, the eight registers on the stack ( R0..R3, R12, LR, PC, and PSR) are pulled from the active stack. Since the active stack is the process stack (using the PSP as the active stack pointer) and the registers pulled include the PC, execution will begin at the address specified in the PC.

    The above instructions must be done while the machine in the privileged state (i.e., the CPU is in handler mode using either stack (PSP or MSP)). There are at least three possible ways this can be done:

    1. Use the code supplied in SVC_example.c, with the initialization mainline executing the SVC() macro after the system is initialized.

    2. Execute the following instructions in the initialization mainline after all the system is initialized:
      set_PSP(running -> sp + 8 * sizeof(unsigned int));
      systick_init();
      __asm(" movw     LR,#0xFFFD");   /* Lower 16 [and clear top 16] */
      __asm(" movt     LR,#0xFFFF");   /* Upper 16 only */
      __asm(" bx       LR");           /* Force return to PSP */
      
    3. Make a kernel command, STARTUP, which is passed as a kernel argument by the initialization mainline to the kernel (see the assignment for examples). Inside SVC_Handler(), another case would be added, notably:
      case STARTUP:
      set_PSP(running -> sp + 8 * sizeof(unsigned int));
      systick_init();
      __asm(" movw     LR,#0xFFFD");   /* Lower 16 [and clear top 16] */
      __asm(" movt     LR,#0xFFFF");   /* Upper 16 only */
      __asm(" bx       LR");           /* Force return to PSP */
      break;
      
      It might be worthwhile including a sanity check to ensure that this is only executed once.
  • Passing arguments to/from the kernel
    Processes communicate with the kernel by passing arguments via the active stack (either the PSP or MSP). A detailed discussion of how the above code passes arguments to the kernel can be found here.
    The following functions will prove useful when passing arguments to the kernel from a process: The function assignR7() can be copied from SVCandKernelArgumentsv3.pdf.

  • Message passing
    For a process to bind to a message queue, send a message, or receive a message, the functions bind(), p_send_message(), or p_recv_message() should be called (note, you are not required to use these names).
    In the assignment, each of these functions creates the arguments required by the kernel's message handling software. The arguments are on the stack. For example, p_send_message(), is written as follows:
    void p_send_message(unsigned mq_id, void *msg, unsigned size)
    {
    /*
    Update the message queue for the process associated with ‘mq_id’
    with the address of the message, ‘msg’. ‘Size’ indicates the number of
    bytes in the message. This is interruptible.
    */
    struct p_msg_struct pmsg;
    pmsg . mqid = mq_id;
    pmsg . msg = msg;
    pmsg . sz = size;
    pkcall(SEND_MESSAGE, &pmsg);
    ...
    }
    
    The function then calls pkcall() (process-kernel call) with two arguments, the name of the kernel action to be performed (in this case, SEND_MESSAGE and the address of the structure containing the data regarding the message (here, &pmsg).
    The function pkcall() is responsible for setting up the kernel call arguments (the code assigned SEND_MESSAGE and arg1 assigned &pmsg). After assigning the address of the kernel call structure to R7, pkcall() should call the kernel (using SVC). (A detailed explanation of pkcall() is given below).
    Since this is an SVC, control eventually passes to SVCHandler(), which can then call the specified kernel function after extracting the arguments on the process stack:
    kcaptr = (struct kcallargs *) argptr -> r7;
    switch(kcaptr -> code)
    {
    case SEND_MESSAGE:
    struct p_msg_struct *pmsgptr;
    pmsgptr = (struct p_msg_struct *) kcaptr -> arg1;
    kcaptr -> rtnvalue =
            k_send_message(pmsgptr -> mqid, pmsgptr -> msg, pmsgptr -> sz);
    break;
    case RECV_MESSAGE:
    ...
    }
    
    If the above isn't clear, draw a map of memory, identifying where the relevant structures are stored. Then link things together with the various pointers used.

  • Possible changes to the recv() primitive
    The recv() specifies the queue from which it expects to receive a message, the address of the message structure, and the maximum size of the message (this assumes recv() is defined as p_get_message()):
    void p_get_message(unsigned mq_id, void *msg, unsigned size)
    
    This implementation means that the receiving process does not know the id of the sender or the size of the returned message. This shortcoming can be rectified by modifying p_get_message() as follows:
    int p_get_message(unsigned dqid, unsigned *sqid, unsigned void *msg, unsigned size);
    
    In this case, p_get_message() returns the size of the message (which must be less-than-or-equal to the maximum size specified in the argument size; a negative value can indicate an error) and passes the address of sqid, the queue number of the sender:
    The modified p_get_message() can be written as follows:
    int p_get_message(unsigned mqid, unsigned *sqid, void *msg, unsigned size)
    {
    /* Return the message when it arrives */
    struct p_msg_struct pmsg;
    pmsg . mqid = mqid;
    pmsg . sqid = sqid;
    pmsg . msg = msg;
    pmsg . sz = size;
    return pkcall(GET_MESSAGE, &pmsg);
    }
    
    Note that in both p_get_message() and p_send_message(), the function pkcall() returns the value returned by the kernel function.

  • The pkcall() function
    The pkcall() function is responsible for calling the kernel with the arguments supplied by the calling function (such as p_get_message()) and returning the value to the function (this is a kernel request):
    int pkcall(int code, void *pkmsg)
    {
    /*
    Process-kernel call function.  Supplies code and kernel message to the
    kernel is a kernel request.  Returns the result (return code) to the caller.
    */
    volatile struct krequest arglist;
    /* Pass code and pkmsg to kernel in arglist structure */
    arglist . code = code;
    arglist . pkmsg = pkmsg;
    /* R7 = address of arglist structure */
    assignR7((unsigned long) &arglist);
    /* Call kernel */
    SVC();
    /* Return result of request to caller */
    return arglist . rtnvalue;
    }
    
    The krequest structure can be defined as follows:
    struct krequest
    {
    int code;      /* Unique (and defined) kernel code */
    int rtnvalue;  /* Result of operation (specific to each code) */
    void *pkmsg;   /* Address (32-bit value) of process message */
    };
    
    Pkcall() offers a uniform way of calling the kernel, avoiding the need to write repeated SVC() calls.
    SVCHandler() in the kernel will need to be modified to handle kernel request messages. The approach simplifies the design of SVCHandler().

  • More on pkcall()
    Pkcall() is used to supply the kernel with arguments from a primitive function such as send() or recv(). For example, an application could call send() with the following arguments:
    struct time_request request;
    ...
    send(TIME_SERVER, &request, sizeof(struct time_request));
    ...
    /* There should be a corresponding receive here, waiting for the response */
    
    Send() is to take the arguments and package them in a way that can be examined by the kernel send function as if the process called the kernel send function directly (rather than having to use pkcall()). This requires send() to put the arguments into a structure that can be read by the kernel and then call the kernel using pkcall(). This should be done on the stack (notice, this is the stack of the process that called send()):
    int send(int dstqid, void *msg, int size)
    {
    truct sendargs args;
    args . dst = dstqid;
    args . mptr = msg;
    args . sz = size;
    pkcall(SEND, &args);  /* pkcall() return code ignored */
    return args . rtncode;
    
    The structure sendargs has the following fields:
    struct sendargs
    {
    int dst;       /* Destination queue */
    void *msg;     /* Pointer to message to be supplied to the receiver */
    int sz;        /* Number of bytes in the message (pointed to by msg) */
    int rtncode;   /* Result of send() */
    };
    
    Pkcall() passes the SEND code and the address of the structure args to the kernel, pointed to by R7.
    Inside the kernel, R7 points to the kernel request. The send arguments can be accessed as follows in SVCHandler():
    struct krequest *arglistptr;   /* Pointer to krequest from pkcall() */
    struct sendargs *sendargptr;   /* Pointer to sendargs from send() */
    int dst;
    char *msgptr;
    int sz;
    ...
    arglistptr = (struct krequest *) argptr -> r7;
    switch(arglistptr -> code)
    {
    case SEND:
    /* Sendargptr points to the send arguments */
    sendargptr = (struct sendargs *) arglistptr -> pkmsg;
    /* Each field in the send() argument list can be extracted */
    dst = sendargptr -> dst;              /* TIME_SERVER in this example */
    msgptr = (char *) sendargptr -> msg;  /* &request in this example */
    sz = sendargptr -> sz;                /* sizeof(struct time_request) in this example */
    ...
    /* Write result of operation to rtncode */
    sendargptr -> rtncode = SUCCESS;
    break;
    ...
    default:
    /* Invalid code */
    arglistptr -> rtnvalue = BADCODE;
    

  • Device interrupts
    When any device interrupts, it is necessary for the device's ISR to save the state of the interrupted activity (be it a process or a lower-priority ISR) on the activity's stack (PSP or MSP). This means that exiting requires the ISR restore the state from either stack.

  • UART output
    Output to the UART should not be done directly by processes, it should be done by the kernel. This requires any process needing to send a message to pass its arguments to the kernel using pkcall().

    For outputting a single character to a specific location, processes require a line (row) number, a column number, and a character. By using the process id as the row number, multiple processes can be run and watched simultaneously. For example, a process could repeatedly write the characters ‘1’ through ‘9’ to the screen as follows:

    row = pid;
    col = 1;
    ch = ‘1’;
    while (1)
    {
    	uart_output_ch(row, col++, ch++);
    	if (col > 80)
    		col = 1;
    	if (ch > ‘9’)
    		ch = ‘1’;
    }
    
    The function uart_output_ch() must pass its arguments to the kernel by putting them onto the stack (i.e., the currently running process):
    int uart_output_ch(int row, int col, char ch)
    {
    /* Output a single character to specified screen position */
    /* CUP (Cursor position) command plus character to display */
    /* Assumes row and col are valid (1 through 24 and 1 through 80, respectively) */
    struct CUPch uart_data;  
    /* Since globals aren’t permitted, this must be done each call */
    uart_data . esc = ESC;
    uart_data . sqrbrkt = ‘[‘;
    uart_data . line[0] = ‘0’ + row / 10;
    uart_data . line[1] = ‘0’ + row % 10;
    uart_data . semicolon = ‘;’
    uart_data . col[0] = ‘0’ + col / 10;
    uart_data . line[1] = ‘0’ + col % 10;
    uart_data . ch = ch; 
    return pkcall(UART_OUT_CH, &uart_data);
    }
    

    Struct CUPch is defined as follows and should be available in a header file to both processes and the kernel:

    struct CUPch
    {
    char esc;
    char sqrbrkt;
    char line[2];	/* 01 through 24 */
    char semicolon;
    char col[2];	/* 01 through 80 */
    char cmdchar;
    char nul;
    };
    

    Pkcall() passes the command and the address of the supplied structure to the kernel using R7 (pointing to the kcallargs structure) and SVC();

    The SVCHandler() can access the uart_data argument list in pspace via the kernel call arguments:

    struct kcallargs *kcaptr;
    struct CUPch *ud_ptr;
    …
    kcaptr = (struct kcallargs *) argptr -> r7;
    switch(kcaptr -> code)
    {
    …
    case UART_OUT_CH:
    	ud_ptr = kcaptr -> arglistptr;  /* ud_ptr points to the process’s argument list */
    

    Outputting a string may require some form of queuing.

  • Testing ideas
    If you're unsure what to test for this assignment, ask yourself, what does the software do? For example, does is support: The above list isn't exhaustive, but it should give you some ideas.

    Assignment 3

  • For a copy of assignment 3, click here.
  • Details of the trainset protocol can be found here.
  • For a copy of the layout, click here. (JPG)
  • For a copy of the UART registers and their addresses, click here. (PDF)
  • Trainset and lab space:
  • Trainset virtual machine
    Rather than writing specific code to perform a task, a virtual machine can be created that responds to different events. The following example TrainMachineExample.c shows how the routing table can be populated with programs that dictate the actions of the train (RDC) when it reaches different Hall sensors.
    Although functional, the example is not complete. For instance, rather than having specific instructions for each switch, it is possible to make a number of generic instructions that can operate on any switch.
    Similarly, it is possible to take this idea and expand it to allow Mr. Conductor (?) to specify a series of stations (Hall sensors) to visit (i.e., stop at) before moving on to the next.

  • Known limitations of train set protocol:
    1. The switch throw states described in section 2.3 and Table 4 of the trainset protocol document are incorrect, they should be 1 - straight and 0 - diverted. (Thanks to Bryan for finding this.)
    2. Message code C2 (Change of locomotive speed and direction acknowledgement message) is only sent to indicate failure; it is not sent as an acknowledgement. (Thanks to Mark for finding this.)
    3. Message code E2 (Throw-switch acknowledgement message) is never sent. (Thanks to Mark for finding this.)