qtOS Manual

qtOS, an OS for HCFSM-based systems

---

• qtOS, an OS for HCFSM-based systems
  • 1. Introduction
  • 2. Task programming
  • 3. Task execution
  • 4. Concurrency
  • 5. Hierarchy
  • 6. Examples
    • 6.1. Seat belt alarm controller
    • 6.2. Take-a-number system
    • 6.3. A simple shell
  • 7. Extensions
    • 7.1. Multi-processor
    • 7.2. Process communication services
    • 7.3. Interrupts
  • References

---

Lluís Ribas-Xirgo
Lluis.Ribas@uab.cat
Department of Microelectronics and Electronic Systems
School of Engineering
Universitat Autònoma de Barcelona, UAB
April 3rd, 2013

---

qtOS is not another tiny operating system but a task manager for a single processor onto which some real-time tasks must be run (1).

It has been done for educational purposes but can be used where several tasks have to share a single processor.

qtOS is thought to execute tasks described as finite-state machines, thus to run systems described as hierarchical concurrent FSMs, or HCFSMs (2).

This document refers to qtOS_basic, a simplified version of qtOS, intended for education and small MCUs.

1. Introduction

The idea of qtOS is to serve as a platform to run a net of tasks that are programmed as FSMs. For each task, there must be two functions, one to initialize it and that will be called when creating the task structures, and the other to run a transition each time it is called.

Each task is associated with the following data structure, when created.

typedef struct qtOS_PCB_s {
  char *name;     /* Name of the task                                  */
  qtOS_process_status_t status; /* qtOS_ IDLE, READY, RUNNING, BLOCKED */
  int priority;   /* Priority, in descending order from 0 (maximum)    */
  int xpri;       /* Execution priority, usually equal to priority     */ 
  int baton;      /* Flag to indicate next task to take the relay      */
  int parent;     /* ID of task that has created this one (-1, qtOS)   */
  int caller;     /* ID of task to activate after callee has finished  */
  int callee;     /* ID of callee (only one call at a time)            */
  int (* init)(); /* Function to call when task is created             */
  int (* step)(); /* Function to call to execute a task transition     */
} qtOS_PCB_t;

To create a task, call qtOS_new_task():

int qtOS_new_task(
  char name[],  
  int priority,
  int (* init)(),
  int (* step)()
) ;

Before any call to qtOS_new_task(), the control block for the operating system must be initialized:

#include "qtos_basic.h"
/* ... */
qtOS_init();

Finally, to run the system, it is necessary to activate some task before calling to qtOS_run():

int failure;
/* ... */
qtOS_new_task( "shell", 10, shell_init, shell_step );
qtOS_fork( "shell" );
failure = qtOS_run();

In the example above the system will contain some shell program to start an interactive session with the user. Note that the shell program is activated by qtOS_fork(). This function changes the state of the corresponding state to READY and puts its ID into de active processes’ queue so that it will be taken into account by the qtOS scheduler.

The system will stop when there are no active processes, if one of them returns an error condition or if they are all blocked. Priority inversion (3) is solved by priority inheritance and, in case of equal priority processes are brought to execution in a round-robin fashion.

2. Task programming

All tasks can be freely programmed, but it is assumed that they are programmed as if they were repeatedly called to run a single transition of a state-machine. Therefore, it is assumed that they will use some state variable to record at which state of the state machine has been left the last time they were called.

For every task there must be a task initializing function that, at least, sets the corresponding state variable to its initial value.

Task variables must be global, so it is recommended to pack them into a single structure.

For example, a task that continuously counts from 0 to MAX and from MAX to 0 can be represented by the following graph.

Note that arc conditions work on current values of C, and that the future values of C, denoted as C+, will be stored after current transitions have finished.

The recommended code for the previous state machine is listed below.

typedef struct updown_task_s {
  int state;
  int C;
  int MAX;
} updown_task_t;

updown_task_t updown_task;

int updown_task_init()
{
  updown_task.state = 0; /* UP */
  updown_task.C     = 0;
  updown_task.MAX   = 7;
  return 0;
} /* updown_task_init */

int updown_task_step()
{
  int C_plus;

  switch( updown_task.state ) {
    case 0: { C_plus = updown_task.C + 1;
              if( updown_task.C == updown_task.MAX - 1 ) {
                updown_task.state = 1;
              } /* if */
              break;
            } /* case 0 -- UP */
    case 1: { C_plus = updown_task.C - 1;
              if( updown_task.C == 1 ) {
                updown_task.state = 0;
              } /* if */
              break;
            } /* case 1 -- DOWN */
  } /* switch */
  updown_task.C = C_plus;
  return 0;
} /* updown_task_step */

To keep things simple, task functions do not have any parameters and they return a non-zero integer to mean that some error has happened during their execution or zero if everything has gone OK.

Communication among tasks is done via “shared memory” (4), i.e. through global variables. There are no coherence problems as all transitions are executed atomically, i.e. as a block similar to critical sections in conventional operating systems.

The idea is that shared memory is built out of all local memories (the task data structures) of tasks, that fields on each data structure can only be written by its owner, and that all data is accessible to any process.

In object-oriented implementations, tasks’ data must be encapsulated and data accessed accordingly.

3. Task execution

Function qtOS_new_task() has to be called for every task in the system:

  qtOS_new_task( "task1", 1, task1_init, task1_step );
  qtOS_new_task( "task2", 1, task2_init, task2_step );
  qtOS_fork( "task1" );
  qtOS_fork( "task2" );
  failure = qtOS_run();

The last call has to be to qtOS_run(), which runs a continuous loop in which the scheduler and the dispatcher are executed one after the other while there are active processes and no one has returned an error value.

There are two modes of process execution. The preemptive mode (by default) imply that higher priority tasks as well as the tasks with the same priority that have not been executed in the current round will take the turn before the current running process. The non-preemptive mode can be set when processes must be run step by step to the end. Note that, in this mode, the execution of running processes is completed regardless of the process priorities in the waiting queue.

To set qtOS to operate in a non-preemptive mode, use:

  qtOS_set_policy_to( qtOS_NON_PREEMPTIVE );

To set it back to the preemptive mode, use:

  qtOS_set_policy_to( qtOS_PREEMPTIVE );

Note that these functions can be called at any point, including within task codes, thus enabling a critical task to be fully completed once having a step executed for the first time.

In the following example, there are two tasks that print the sequences <1, 2, 3> and <0, 4, 8>, respectively. The tasks’ codes are listed below.

  int task1_init() { task1.n = 1; return 0; }
  int task2_init() { task2.n = 0; return 0; }
  int task1_step()
  {
    printf( "%d ", task1.n );
    task1.n = task1.n + 1;
    if( task1.n > 3 ) { return qtOS_join(); }
    else              { return 0; }
  } /* task1_step */
  int task2_step()
  {
    printf( "%d ", task2.n );
    task2.n = task2.n + 4;
    if( task2.n > 8 ) { return qtOS_join(); }
    else              { return 0; }
  } /* task2_step */

The calls to qtOS_join() cause the processes to end and become inactive (latent tasks).

To execute the former tasks on qtOS, the main() should include:

  qtOS_new_task( "task1", 1, task1_init, task1_step );
  qtOS_new_task( "task2", 1, task2_init, task2_step );
  qtOS_fork( "task1" );
  qtOS_fork( "task2" );
  /* qtOS_set_policy_to( qtOS_NON_PREEMPTIVE ); */
  failure = qtOS_run();

If run with preemptive policy, the output goes like <1, 0, 2, 4, 3, 8>, i.e. the execution of tasks steps is interleaved.

But, with non-preemptive policy, the output is <1, 2, 3, 0, 4, 8> because they are fully executed to completion before freeing the processor.

4. Concurrency

In the previous section, it has been shown that qtOS can run several tasks in parallel by executing ready processes’ steps in a round-robin fashion for every priority class.

Tasks can be run in parallel by activating them via qtOS_fork(). This function creates a new execution thread, which must end with a qtOS_join(), which returns the process to an idle task.

After activating a task with qtOS_fork(), child and parent tasks run independently. There is a field, in the process control block, that is used to store the ID of the parent process and can be used in future extensions to send a signal to it when qtOS_join() is called in the child process. Additionally, it is possible to add a forced ending of all child processes when its parent ends execution.

Communication between tasks is done through global variables that are accessible by senders and receivers but there is no rule enforcement mechanism to determine the time at which data is accessed by tasks. This is up to the task designer.

In this section, the communication between a producer and a consumer is described to illustrate a typical case in task communication.

The producer-consumer example is represented by two tasks running concurrently, one sending data to the other.

To ensure that the consumer has always data to consume, the producer should be run before the consumer. And to avoid losing any produced datum, the consumer should take it before the consumer produces a new one. There is no mechanism to guarantee that some datum is lost.

There are several solutions to this problem. Here there is a list of the most common:

1. Use an explicit hand-shake protocol.
   The consumer (producer) requests a data to be produced (consumed) by setting a request signal to 1, the producer (consumer) produces (consumes) a new piece of information, confirms this action by setting an acknowledgement signal to 1, the consumer (producer) sets the request signal back to 0 and, finally, the producer (consumer) returns the acknowledgement signal to 0. In the next section it will be explained how to create a similar communication protocol by using calls and returns.

2. Create a schedule in which producer is executed before consumers.
   In static-cycle scheduling, create producer tasks before consumers, with all tasks having the same priority. In this case, it should be checked that consumers do not consume the same data twice.
   In conventional operating systems, this can be achieved by giving producers a higher priority than consumers, as they would distribute processor time in accordance with active process priority thus given less priority processes opportunity to be executed. On the contrary, qtOS does not execute lower priority processes than the maximum priority ones except on non-preemptive mode, when top priority processes have been activated after the current, lower-priority process have gotten the processor.
   Again, there is a solution similar to creating a hand-shaking protocol through changing producer and consumer priorities dynamically.

3. Use FIFOs.
   By creating queues of data at each producer-consumer channel, no data is lost or can be retrieved twice. Note that qtOS executes complete steps of producer and consumer processes thus enabling producers insert data into channels and consumers take these data from them without any coherence problem.

The example to illustrate the producer-consumer case consists of two tasks, one producing a sequence of integer numbers from 1 to N, and another to consume these numbers and print them out into the console’s screen.

int producer_init() {
  producer.out = 1;
  producer.N = 3;
  producer.state = 0;
  return 0;
} /* producer_init */

int consumer_init() {
  consumer.inp = 0;
  return 0;
} /* consumer_init */

int producer_step()
{
  int failure;
  failure = 0;
  if( producer.state == 0 ) {
    producer.state = 1;
  } else if( producer.state == 1 ) {
    if( producer.out < producer.N ) {
      producer.out = producer.out + 1;
    } else {
      producer.state = 2;
      failure = qtOS_join();
    } /* if */
  } /* if */
  return failure;
} /* producer_step */

int consumer_step()
{
  int failure;
  if( consumer.inp == producer.out ) {
    failure = qtOS_join();
  } else {
    consumer.inp = producer.out;
    printf( "Got: %d\n", consumer.inp );
    failure = 0;
  } /* if */
  return failure;
} /* consumer_step */

The producer uses a state variable to determine if it has produced the first (state==0), the last (state==2) or an intermediate (state==1) value. The consumer detects that there is no more data to consume when the current reading equals the last read value.

To run this system correctly, the simplest option is to create two tasks with the same priority and with a static cycle in which producer is always run before consumer:

qtOS_new_task( "producer",  1, producer_init, producer_step );
qtOS_new_task( "consumer",  1, consumer_init, consumer_step );
qtOS_fork( "producer" );
qtOS_fork( "consumer" );
failure = qtOS_run();

The other options are left to the reader.

5. Hierarchy

To avoid complex behaviors to be described, tasks many be decomposed into subtasks. In these cases, tasks can call subtasks to be executed. In the meantime, the caller tasks are blocked.

The hierarchy of tasks is established in their code: a caller has a higher level than the callee. To call a task, use qtOS_call(), and to finish a task and return to its caller, qtOS_return().

To avoid the problem of the priority inversion, callee processes inherit higher priorities of callers. The inherited priorities are lost when callees return to callers.

Typically, the callee process runs a state machine within a given state of the caller one. As the caller gets blocked, it cannot exit that state until the subordinate state machine reaches an end state, i.e. it executes a step that includes a qtOS_return().

If the caller needs some data from the callee, there is no need for any additional control data, as the caller will wait until the callee has finished its execution thus having produced a new set of data.

The consumer-producer example that has been described in the previous section can be implemented by using call/return. The code is the following:

/* ... */

int producer_step()
{
  int failure;
  failure = 0;
  if( producer.state == 0 ) {
    producer.state = 1;
  } else if( producer.state == 1 ) {
    if( producer.out < producer.N ) {
      producer.out = producer.out + 1;
    } else {
      producer.state = 2;
    } /* if */
  } /* if */
  failure = qtOS_return();
  return failure;
} /* producer_step */

int consumer_step_cr()
{
  int failure;
  if( consumer.state == 0 ) {
    consumer.state = 1;
    failure = qtOS_call( "producer" );
  } else { /* active after being blocked by a call */
    consumer.state = 0;
    if( consumer.inp == producer.out ) {
      failure = qtOS_join();
    } else {
      consumer.inp = producer.out;
      printf( "Got: %d\n", consumer.inp );
    } /* if */
  } /* if */
  return failure;
} /* consumer_step */

/* ... */

int main()
{
    qtOS_init();
    qtOS_new_task( "producer",  1, producer_init, producer_step );
    qtOS_new_task( "consumer",  1, consumer_init, consumer_step );
    qtOS_fork( "consumer" );
    return qtOS_run();
} /* main */

Note that the consumer has to finish every step by calling qtOS_return(), and that the producer has been introduced a state variable to determine whether it should request a new datum or it has to acknowledge datum transmission by printing it.

In real-time systems, this is not the usual case, because tasks are devoted to continuously monitor or control external signals, and cannot be suspended at any time, as it happens with the consumer, nor can they be activated from time to time, as with the producer.

Be careful with calls and forks. A call blocks execution of caller until callee has finished its execution whereas a fork does not. Processes initiated with calls should end by using returns and the ones activated with forks, by joins. In qtOS, qtOS_return() and qtOS_join() are functionally equivalent to avoid call/return and fork/join pairing problems.

Note that, once active, processes cannot be called or forked again. In case there is need to use the same task functions twice, there should be created two different tasks, though possibly using the same functions or data structure.

Also note that it is only allowed to perform a unique call within a single task step. Any subsequent call will cause an error to be fired.

6. Examples

This section is devoted to show some illustrative examples on how to use qtOS.

6.1. Seat belt alarm controller

An example found in Esterel and POLIS references (5) is that of a controller of the alarm to warn about fastening the seat belt.

Its informal specification is something like:

“If the driver turns on the key and does not fasten the seat belt within 5 seconds then sound the alarm for 5 seconds, or until the driver fastens the seat belt, or until the driver turns off the key.”

The state machine that implements the previous behavior must begin by setting the alarm output to off, i.e. by setting Alarm signal to 0. Then, it waits for KeyOn event to take place, i.e. for input signal KeyOn to become true. At that instant, a timer must be set to generate future events End5 and End10 when 5 and 10 seconds have gone by, respectively. While waiting for these events to occur, if the key is turned off again or the belt has been fastened, the controlling state machine returns to the initial state and sets off the alarm.

The BeltOn is a Boolean sensor which stays true when the seat belt is fastened and false otherwise.

The timer task shall count 5 and 10 seconds after receiving a StartTimer event.

Events will be “transmitted” so that emitters will write a 1 into corresponding variables and receivers will write a 0 after reading them.

This way of transmitting events is an explicit handshaking protocol performed on a single shared variable. Emitters produce a value that is consumed by receivers.

Note that, in case there is more than one receiver per event, it does not work and, depending on the context, different approaches can be taken. Solutions include emitters writing the number of receivers and these subtracting one to it or having one variable per receiver and emitters writing ones on each one (sorry for the pun).

Receivers will consume (write zeroes) events at their inputs even if they do not affect their behavior, thus avoiding memory effect on information that is linked to time. Therefore, receivers should change state or internal variables to recall events occurrence.

Following this communication philosophy, the program that implements the seat belt alarm controller on qtOS is given below.

/* Seat belt alarm controller *************************************** */

/* Shared memory: */

int BeltExit; /* This is a counter that is non-zero to mean STOP:
                 When all tasks are active it remains to zero until
                 a stopping signal has been activated.
                 Then it is set to a value that is equal
                 to the number of involved processes (4, in this case).
                 When any of these processes runs its step,
                 if the counter is greater than zero,
                 it decrements it by 1 and becomes inactive by either
                 qtOS_join() or qtOS_return().
               */  
int BeltOn, KeyOn, KeyOff, StartTimer, End5, End10, Alarm;

/* Task functions: */

enum { ALARM_INIT, ALARM_START, ALARM_WAIT, ALARM_BEEP } alarm_state;

int alarm_init()
{
  StartTimer = 0;
  Alarm = 0;
  alarm_state = ALARM_INIT;
  return 0;
} /* alarm_init */

int alarm_step()
{
  int failure;

  failure = 0;
  switch( alarm_state ) {
    case ALARM_INIT: {
      if( KeyOn && !BeltOn ) {
        alarm_state = ALARM_START;
        StartTimer = 1;
        alarm_state = ALARM_WAIT;
      } /* if */
      Alarm = 0;
      break;
    } /* case */
    case ALARM_WAIT: {
      if( KeyOff || BeltOn || End10 ) {
        /* Former condition has been added "|| End10" to avoid
           that concurrent reception of End5 and En10 causes
           alarm to beep forever.
        */
        alarm_state = ALARM_INIT;
      } else {
        if( End5 ) {
          alarm_state = ALARM_BEEP; printf( "alarm: beeping\n" );
        } /* if */
      } /* if */
      Alarm = 0;
      break;
    } /* case */
    case ALARM_BEEP: {
      if( KeyOff || BeltOn || End10 ) {
        alarm_state = ALARM_INIT;  printf( "alarm: off\n" );
      } /* if */
      Alarm = 1;
      break;
    } /* case */
    default: {
      failure = -1;
    } /* default */
  } /* switch */
  /* Input events' consumption: */
  KeyOn  = 0;
  KeyOff = 0;
  End5   = 0;
  End10  = 0;
  if( BeltExit > 0 ) {
    BeltExit = BeltExit - 1;
    alarm_state = ALARM_INIT;
    failure = qtOS_join();
  } /* if */
  return failure;
} /* alarm_step */

#include <time.h>

enum { TIMER_OFF, TIMER_TO_5, TIMER_TO_10 } timer_state;
clock_t time0;

int timer_init()
{
  StartTimer = 0;
  End5 = 0;
  End10 = 0;
  time0 = clock();
  alarm_state = TIMER_OFF;
  return 0;
} /* timer_init */

int timer_step()
{
  double elapsed;

  if( StartTimer == 1 ) {
    timer_state = TIMER_TO_5;
    time0 = clock();
  } /* if */
  if( timer_state == TIMER_TO_5 ) {
    elapsed = (double)(clock()-time0)/CLOCKS_PER_SEC;
    if( elapsed >= 5.0 ) {
      End5 = 1; printf("timer: emit End5\n");
      timer_state = TIMER_TO_10;
    } /* if */
  } /* if */
  if( timer_state == TIMER_TO_10 ) {
    elapsed = (double)(clock()-time0)/CLOCKS_PER_SEC;
    if( elapsed >= 10.0 ) {
      End10 = 1; printf("timer: emit End10\n");
      timer_state = TIMER_OFF;
    } /* if */
  } /* if */
  /* Input events' consumption: */
  StartTimer = 0;
  if( BeltExit > 0 ) {
    BeltExit = BeltExit - 1;
    timer_state = TIMER_OFF;
    return qtOS_join();
  } else {
    return 0;
  } /* if */
} /* timer_step */

int carmon_init()
{
  BeltExit = 0;
  BeltOn = 0;
  KeyOn = 0;
  KeyOff = 0;
  return 0;
} /* carmon_init */

#include <conio.h>

int carmon_step()
{
  int  failure;
  char c;

  failure = 0;
  fflush( stdin );
  printf( "carmon: Type in ...\n" );
  printf( "        [B] to toggle seat belt,\n" );
  printf( "        [I] to start engine (KeyOn),\n" );
  printf( "        [S] to stop engine (KeyOff), and\n" );
  printf( "        [Q] to quit simulation.\n" );
  printf( "        or else to continue.\n" );
  c = getch();
  printf( "carmon: " );
  switch( c ) {
    case 'B':
    case 'b':
      if( BeltOn ) {
        BeltOn = 0;
        printf( "BeltOn'" );
      } else {
        BeltOn = 1;
        printf( "BeltOn" );
      } /* if */
      break;
    case 'I':
    case 'i': KeyOn = 1; KeyOff = 0; printf( "KeyOn" ); break;
    case 'S':
    case 's': KeyOff = 1; KeyOn = 0; printf( "KeyOff" );break;
    case 'Q':
    case 'q': BeltExit = 4; printf( "Exit!" ); break;
    default:  printf( "<nothing>" );
  } /* switch */
  putchar( '\n' );
  if( BeltExit > 0 ) {
    BeltExit = BeltExit - 1;
    failure = qtOS_join();
  } /* if */
  return failure;
} /* carmon_step */
/* ****************************************************************** */

Note that the former program mixes real-time behavior with simulated inputs, which is not coherent, but it is done only to show how time can be taken into account in qtOS tasks.

6.2. Take-a-number system

Take-a-number systems help organizing queues in busy places. To do so, only to types of processes are required: one to observe the movements in the queue and another to represent the clients in the queue.

The idea is to take profit of the qtOS process queue management performed by the scheduler: the observer process is run in higher priority than the client ones. The observer activates a client process when a new client comes and when a client goes out. In the first case, activation is done through a call so that the client process inherits the observer process priority and can be run in the next step. When it returns, the observer forks this process so that it is placed at the end of the client processes’ queue. In the second case, activation is done via qtOS_fork(). After forking, the observer returns to idle to enable that client processes can be executed. At their turn, client processes, must end their executions by activating the observer again.

As the client processes are representatives of the clients in the system, they are agents. These agents follow a series of steps, like their human counterparts would do. First, they take a ticket, then wait for their turn, and, finally, go out.

To code that into C using qtOS it is better to start with the corresponding state machines, which are shown in the following figures. At the left side, there is the one corresponding to the observer. It starts at a READING state where input events are waited for to occur. When either a ticket is demanded or a client has been served, it then goes to GIVE_TICKET or TAKE_TICKET state, respectively.

At the GIVE_TICKET state, a new client agent is activated by qtOS_call(), which will cause it to execute the GET_TICKET state step. Once the corresponding agent has taken the ticket, it moves to the GET_OUT state and gives way to the caller process by qtOS_return(). The next execution step will be performed by the observer, which will go to the PUSH state, where it will perform a qtOS_fork() to put the agent back in the ready process list.

When the observer detects a client has been served it moves to TAKE_TICKET state, where it stops execution by qtOS_join(). Hence, the first ready agent task can execute the step consisting of stopping its own execution and then, activating the observer again. At the POP state, the observer updates the global information about the system, i.e. the queue length and which is the next client to be served (Quantity and NowServing).

As the basic implementation of qtOS relies on a shared memory, the agent states must be stored in an array, and their code must access the corresponding state. To do so, there is a function, client_search(), to compute the vector index by using qtOS_self_name():

/* ... */
#define QUEUE_CAPACITY 8
char *ClientNames[QUEUE_CAPACITY] =
     { "01", "02", "03", "04", "05", "06", "07", "08" };
/* ... */
enum { CLIENT_GET_TICKET, CLIENT_GET_OUT } client_state[QUEUE_CAPACITY];
/* ... */
int client_search( char *name )
{
  int i, found;

  i = 0;
  found = 0;
  while( i < QUEUE_CAPACITY && found == 0 ) {
    if( strcmp( name, ClientNames[i] ) ) {
      i = i + 1;
    } else {
      found = 1;
    } /* if */
  } /* while */
  if( found == 0 ) i = -1;
  return i;
} /* client_search */
/* ... */

As mentioned before, the code for the client tasks must determine first which dataset (in this case, only the state) corresponds to the agent running at that moment:

int client_init()
{
  int i;

  i = client_search( qtOS_self_name() );
  if( i >= 0 ) {
    client_state[i] = CLIENT_GET_TICKET;
    i = 0;
  } /* if */
  return i;
} /* client_init */

int client_step()
{
  int  failure;
  int i;

  failure = 0;
  i = client_search( qtOS_self_name() );
  if( i < 0 ) return -1;
  switch( client_state[i] ) {
    case CLIENT_GET_TICKET: {
      printf( "client: ticket no. %s\n", qtOS_self_name() );
      client_state[i] = CLIENT_GET_OUT;
      failure = qtOS_return();
      break;
    }
    case CLIENT_GET_OUT: {
      printf( "client: ticket no. %s, dropped\n", qtOS_self_name() );
      client_state[i] = CLIENT_GET_TICKET;
      failure = qtOS_fork( "observer" );
      failure = qtOS_join();
      break;
    }
  } /* switch */
  return failure;
} /* client_step */

The code for the observer has been added an extra state to stop simulation, so that it be possible to quit the program.

/* ... */
int NowServing, NextInQueue, Quantity;
/* ... */
enum { O_READING,
       O_GIVE_TICKET, O_PUSH, O_TAKE_TICKET, O_POP, O_STOP
} observer_state;

int observer_init()
{
  NowServing = 0; NextInQueue = 0; Quantity = 0;
  observer_state = O_READING;
  return 0;
} /* observer_init */

int observer_step()
{
  int  failure;
  char c;

  failure = 0;
  switch( observer_state ) {
    case O_READING: {
      fflush( stdin );
      printf( "observer: Type in ...\n" );
      printf( "          [T] to [t]ake a number,\n" );
      printf( "          [G] to [g]o away, and\n" );
      printf( "          [Q] to quit simulation.\n" );
      printf( "          else to go on.\n" );
      c = getch();
      switch( c ) {
        case 'T':
        case 't': {
          observer_state = O_GIVE_TICKET;
          break;
        } /* client takes a number */
        case 'G':
        case 'g': {
          observer_state = O_TAKE_TICKET;
          break;
        } /* client gives a number back */
        case 'Q':
        case 'q': {
          observer_state = O_STOP;
        } /* quit simulation */
      } /* switch */
      break;
    }
    case O_GIVE_TICKET: {
      if( Quantity < QUEUE_CAPACITY ) {
        failure = qtOS_call( ClientNames[NextInQueue] );
        if( failure ) {
          observer_state = O_STOP;
        } else {
          observer_state = O_PUSH;
        } /* if */
      } else {
        printf(
          "observer: Queue capacity (%d) exceeded!\n",
          QUEUE_CAPACITY
        );
        observer_state = O_READING;
      } /* if */
      break;
    }
    case O_PUSH: {
      failure = qtOS_fork( ClientNames[NextInQueue] );
      if( failure ) {
        printf(
          "observer: Error processing %s entrance!\n",
          ClientNames[NextInQueue]
        );
        observer_state = O_STOP;
      } else {
        NextInQueue = (NextInQueue + 1) % QUEUE_CAPACITY;
        Quantity = Quantity + 1;
        observer_state = O_READING;
      } /* if */
      break;
    }
    case O_TAKE_TICKET: {
      if( Quantity > 0 ) {
        failure = qtOS_join();
        if( failure ) {
          printf(
            "observer: Error processing %s exit!\n",
            ClientNames[NowServing]
          );
          observer_state = O_STOP;
        } else {
          observer_state = O_POP;
        } /* if */
      } else {
        printf(
          "observer: Queue underflow, there are no clients waiting!\n"
        );
        observer_state = O_READING;
      } /* if */
      break;
    }
    case O_POP: {
      NowServing = (NowServing + 1) % QUEUE_CAPACITY;
      Quantity = Quantity - 1;
      observer_state = O_READING;
      break;
    }
    case O_STOP: {
      if( Quantity > 0 ) {
        printf( "observer: Cannot stop while there are clients!\n" );
      } else {
        NowServing = 0;
        NextInQueue = 0;
        failure = qtOS_return();
      } /* if */
      observer_state = O_READING;
    }
  } /* switch */
  return failure;
} /* observer_step */

This example can be further extended to transform the observer into a “server” for the clients and the clients’ step behavior can include a waiting state from which they can choose to stay at that queue or leave each time the server asks them to take such a decision.

6.3. A simple shell

Shell tasks help users interact with software run on qtOS, thus enabling its validation. Shells are, basically, tasks that read inputs from users, call tasks, and provide feedback of task execution to them.
The examples given in this text can be combined in a single program by using a shell that enables executing each one of them in an independent form.

For instance, it is possible to combine the previous two cases in a program that includes a shell that is able to interpret four different commands from the user, namely, one to simulate the seat belt controller, another to run the take-a-number system, another one to give a little help message, and, finally, the one to quit from shell execution.

The corresponding code is given below.

/* qtOS shell ****************************************************** */

typedef struct qtOS_shell_s {
  char input[BUFSIZ];
} qtOS_shell_t;

qtOS_shell_t qtOS_shell;

int qtOS_shell_init()
{
  qtOS_shell.input[0] = '\0';
  printf( "qtOS> Ready.\n" );
  return 0;
} /* qtOS_shell_init */

int qtOS_shell_step()
{
  int i, failure;

  failure = 0;
  printf( "qtOS> " ); scanf( "%s", qtOS_shell.input );
  i = 0; while( i<BUFSIZ && isspace( qtOS_shell.input[i] ) ) i = i + 1;
  switch( qtOS_shell.input[i] ) { /* only looks at 1st. char of input */
    case 'A':
    case 'a': qtOS_call( "belt" ); break;
    case 'T':
    case 't': qtOS_call( "turns" ); break;
    case 'H':
    case 'h': printf( "qtOS: Commands are " );
              printf( "[A]larm, [T]urns, [H]elp, and [Q]uit\n" );
              break;
    case 'Q':
    case 'q': printf( "qtOS: Bye.\n" ); failure = qtOS_join(); break;
    default : printf( "qtOS: Unknown command.\n" );
  } /* switch */
  return failure;
} /* qtOS_shell_step */

/* ***************************************************************** */

Note that there are two tasks, namely, “belt” (this new task is why BeltExit is 4 instead of 3) and “turns” that are called to activate the corresponding tasks for each system:

/* ... */
enum { BELT_IDLE, BELT_RUNNING } belt_state;

int belt_init() { belt_state = BELT_IDLE; BeltExit = 0; return 0; }

int belt_step()
{
  int failure;

  if( belt_state == BELT_IDLE ) {
    failure = qtOS_fork( "alarm" );
    if( failure == 0 ) failure = qtOS_fork( "timer" );
    if( failure == 0 ) failure = qtOS_fork( "carmon" );
    belt_state = BELT_RUNNING;
  } else {
    if( BeltExit > 0 ) {
      BeltExit = BeltExit - 1;
      belt_state = BELT_IDLE;
      qtOS_return();
    } /* if */
  } /* if */
  return failure;
} /* belt_step */

/* ... */

enum { TURNS_IDLE, TURNS_RUNNING } turns_state;

int turns_init() { turns_state = TURNS_IDLE; return 0; }

int turns_step()
{
  int failure;

  failure = 0;
  if( turns_state == TURNS_IDLE ) {
    failure = qtOS_call( "observer" );
    turns_state = TURNS_RUNNING;
  } else {
    turns_state = TURNS_IDLE;
    qtOS_return();
  } /* if */
  return failure;
} /* turns_step */
/* ... */

Before activating the shell, recall that this task should run at the lowest priority (i.e. highest value) than the rest of tasks. In the example, the main program should be:

int main()
{
  int i, failure;

  failure = 0;
  qtOS_init();
  qtOS_new_task( "shell",    4, qtOS_shell_init, qtOS_shell_step );
  /* Seat belt alarm controller */
  qtOS_new_task( "belt",     3, belt_init, belt_step );
  qtOS_new_task( "alarm",    2, alarm_init, alarm_step );
  qtOS_new_task( "timer",    2, timer_init, timer_step );
  qtOS_new_task( "carmon",   2, carmon_init, carmon_step );
  /* Take-a-number example */
  qtOS_new_task( "turns",    3, turns_init, turns_step );
  qtOS_new_task( "observer", 1, observer_init, observer_step );
  for( i = 0; i < QUEUE_CAPACITY; i = i + 1 ) {
    qtOS_new_task( ClientNames[i], 2, client_init, client_step );
  } /* for */
  qtOS_fork( "shell" );
  failure = qtOS_run();
  return failure;
} /* main */

The source code accompanying this documentation at http://qtos.sourceforge.net does include the full set of examples given in this section.

7. Extensions

7.1. Multi-processor

To distribute processes among processors, 1) the process control block must be added a processor ID; 2) the scheduler should be modified to mark as many processes as they have been executed in the last step with baton to 1, and 3) the dispatcher has to be modified so to execute each running process into a different processor, keeping the processes that were executed in the previous cycle in the same processor (that is what processor ID in process control blocks should be used for).

7.2. Process communication services

Though shared memory with direct process access is simple, it creates strong task interdependence. To make it more flexible and robust, services to publish/subscribe to data should be provided by the operating system. A further improvement would be that these data could optionally be stored and retrieved from input and output FIFOs.

7.3. Interrupts

qtOS relies on tasks be programmed in a way that they can be executed as a series of steps. Though this can be enforced if tasks’ programs are generated automatically, it is very difficult to be guaranteed when manually written.

Besides, having no timer information, real-time depends on worst-case execution times computed for every task, on scheduler and dispatcher latencies, and on scheduling policies.

To divide time into fixed-length quanta, the scheduler must be fired every time a new quantum begins. Note that this implies 1) including interrupt handling into qtOS; 2) having a time and memory penalty for process context switching, and 3) introducing mutexs (6) and critical sections for data sharing between processes.

References

1. http://en.wikipedia.org/wiki/Real-time_operating_system
2. D. D. Gajski, J. Zhu, and R. Dömer. (1997) Essential Issues in Codesign. Technical Report ICS-97-26. University of California, Irvine (USA).
3. http://en.wikipedia.org/wiki/Priority_inversion
4. http://en.wikipedia.org/wiki/Shared_memory
5. A Framework for Hardware-Software Co-Design of Embedded Systems. http://embedded.eecs.berkeley.edu/research/hsc/
6. http://en.wikipedia.org/wiki/Mutual_exclusion

---