Nut Operating System



Nos composed of user-space functions (running in user-space).  Nos models concurrency using process.  The share-resource accesses are controlled with semaphores.  The processes in Nos communicate with each other through message passing. The crucial real-time functions are supported therefore Nos can support real-time tasks. Nos supports the following functions:

Process

A process is an independent computation which can run concurrently with other process.  A process is declared as a normal defined function.  Initial values can be passed as parameters at the starting time of a process.  A process will end its execution by self-termination when it executes the last instruction at the end of program.  This is different from the execution of a function which ends its execution by returning to the caller.  A program that calls a process will start that process execution, that program then will continue to work without waiting.  A process never returns to its caller.

A process is a program in execution.  Several processes can be active at the same time.  The concurrency is achieved via multi-threading ("light weight process").  A heavy weight process is a process with a separate address space.  It needs a mechanism to do the address mapping between virtual address and physical address.  A light weight process has single address space.  A thread is a trace of execution, a single thread process is resulted from co-operative process (via co-routinte).  A multi-thread process has several traces at the same time.  This can be accomplished by pre-emptive scheduler with time-slicing.  A light weight process is much cheaper to create than a heavy weight process.

Each process has its own stack segment.  In Nos, there is a single address space, the stack segment of all processes are in the same address space.  The advantage is that there is no translation between virtual address and physical address therefore it is fast and simple.  The disadvantage is that there is no protection between processes.  Each process has its process descriptor (PD) to store the necessary information.  A process descriptor in Nos consists of 12 fields:
  1. link previous
  2. link next
  3. process id
  4. process status
  5. PC
  6. SP
  7. FP
  8. TS
  9. in-box
  10. await-box
  11. message
  12. timer
The link previous/next are used to form the list of processes, for example the process queue.  The process identifier is a unique number used to label a process.  The process status holds the state of process (to be explained later).  The fields {PC, SP, FP, TS} hold the computation state of the process.  The mail-box (in-box and await-box) is used to communicate between processes.  The in-box is the list of processes that sent messages to this process.  The await-box is the list of processes that are waiting for messages from this process. The timer holds the timer value of this process.

<fig a process descriptor>

Scheduler

When a process is created it is ready to start the execution. Its PD will be linked to the "ready list" (the process queue) which is a doubly linked circular list used by the scheduler.  A scheduler has the duty of selecting a process to run from the ready list.  The scheduling policy of Nos is a Round-Robin policy where an equal time-slice is allocated for every process and the process is scheduled on first-come first-serve basis. A scheduler will enable a process in the ready list to run until its time-slice is over and then switches to the next process in the list.  If a process enters a "wait" state, it is said to be blocked.  A process is usually blocked because it performs some operation that requires waiting for another process, such as waiting for the receiver to retrieve a message.  When a process is blocked, its PD will be removed from the ready list.  The process in "wait" state can be awaken by other process.  Its PD will be inserted into the end of the ready list.  To perform the switch from one process to another process (task switching), the current state of computation {PC, SP, FP, TS} of the active process is saved in its PD and the state of computation of the process to be run is restored.  The first process to be active is the process to run the main program.  A process is run until it is time-out, or it is blocked or it is terminated.  "switchp" is the task switcher function in Nos. Here is how "switchp" work.

switchp
  if status is time-out or blocked
    runnable next task
  else status is terminated
    delete this task
    runnable next task

where status is the state of the process, runnable marks the process as running.  

Before we go into more details of the operating system functions, we must understand the basic of running a task first.

Nos supervisor (NOSS)

Nos is executed under Nos supervisor.  Nos supervisor runs on top of the processor simulator. Noss is a priviledge program. A priviledge program is a program that is "out-of-bound" of user programs.  A priviledge program provides mechanism for executing a user program, for example,  the sx processor simulator is a priviledge program that "execute" s-code.  In our implementation, priviledge programs are written in C.  User programs are written in Nut.  The relationship between Nos supervisor and the processor simulator can be understood by regarding Noss as issueing an "interrupt" to the processor. The processor continuously executes a program (running a process) until an interrupt occurs then the supervisor takes action.  The interrupt can occur only at the end of executing an instruction. There are three interrupt events: time-out, stop, block.
  1. time-out -- the current process has used up its own time-slice.
  2. stop -- the current process runs to completion.
  3. block -- the current process is blocked (to be resumed later).
The supervisor (Noss) takes action in response to the interrupt events as follows.

notation [state]

[start]         set up process queue
  |
  v
[user]   <---   run user process
  |         |
  | A       | stop
  v         |
[switch]  ---   run task switcher

A = time-out/stop/block

<fig Noss state diagram>

At [start], the main program creates processes and the process queue. Noss schedules only two kinds of processes: user process and switchp.  "switchp" is created and has its own PD but it is privileged and never enters the process queue.  Once the process queue is ready, at the state [user], a user process is run. The user process is run until it is time-out/stopped/blocked.  Then Noss calls the "switchp", at the state [switch].  "switchp" runs to completion. It must not be interrupted as it is manipulating the process queue.  Then the state is going back to run a user process.

At the end of task-switch, Noss always run the next task.  This is accomplished by restoring the computation state of that process.  This means the PC, SP, FP, TS of that process are restored to the processor simulator and then the processor simulator continues to execute until the interrupt occurs. The following pseudo code described noss.

noss
  if there is no process in the queue
     stop the whole simulation
  else
     update status to nos
     if state = switch
        save current user process
        restore "switchp"
        state = user
     else state = user
        restore active process
        state = switch

The process descriptor contains C-state. Saving and restoring C-state are the act of transferring C-state between the processor simulator and the process descriptor. Noss does the restoring of C-state by running the code in user-space. This restoring will affect the flow of execution, as the instruction pointer is changed, it does a jump in the program.  As Noss is responsible to run the task-switcher, it must save C-state.  Saving C-state can not be done in user-space as the precise state has been changed when trying to run the "saving state" function.  So, save-Cstate is done in the main loop of Noss (in C).  This gives the save-Cstate a special privilege (so called "kernel" in OS vocabulary).  It is implemented as a system call instruction.

Simulation of interrupt

To simulate the "interrupt", the processor calls Noss from time to time (this is called "yield").  The interrupt interval is controlled by
counting the cycle used since the last call to Noss.

The processor returns the control back to Noss after 3 conditions:
  1. its time-slice has been used up, this is called "time-out"
  2. the process has been blocked by executing some operation, this is called "blocked".
  3. the task is completed, the program reached "end", this is called "stopped".
When the processor hands the control back to Noss, Noss calls task-switch.  The task-switch code is in the user-space. The task-switch is the function "switchp".  "switchp" requires the knowledge of the status of the completion of the previous task: time-out, blocked, or ended. This information is provided by Noss via the variable "status", as Noss controls the processor simulator it knows how the task has returned the control.  

Noss is minimal in the sense that it does not do a lot of things by itself.  The only thing it does is to call "switchp". Noss monitors the state of computation of a process through two global variables: status and activep.

Processor simulator

In the processor simulator, the main simulation loop is "eval". It executes a fixed number of cycles.  This is the main fetch-execute cycle of the processor (in fact most processor simulator are like this):

eval
  count = 0
  loop
    if count > limit break
    fetch an instruction
    execute the instruction
    count = count + 1

To implement "interrupt", a flag (intflag) is used to disable the break.  This flag can be turned on/off by the system calls.

eval2
  count = 0
  loop
    if intflag == 1
      if count > limit break
    fetch an instruction
    execute the instruction
    count = count + 1

The system calls that support Nos are:

20 disable interrupt
21 enable interrupt
22 block a process

The following code describes the main loop of the processor simulator.

eval
  set PC
  while runflag = 1
    run one instruction
    yield

yield
  if intflag = 1
    if no of cycle used > TIMEOUT
       noss(time_out)

where runflag controls the termination of noss itself, intflag is the interrupt flag used to disable/enable interrupt.

How a process is created

A function "run" is used to create a process and put it to the process queue.  Although "run" looks like a normal function, it can not be compiled into a normal function call.  The argument to "run" is a function call which will be turned into a process so it should not be evaluated. A call to "run" is compiled into the code that passes an address of the function call.  The argument to call.run in n-code is just a user-function call with its arguments as usual.  However, this argument will not be evaluated.  Instead, the address of the code of  this call will be generated as an argument of "run". This code will be activated by the scheduler as a process.  See the following example:

in nut

(def add (a b) () (+ a b))
(def run (f) () 0)
(def main () ()
  (do
  (run (add 4 5))))

in n-code

add
(fun.2.2 (+ get.1 get.2 ))
run
(fun.1.1 (lit.0 ))
main
(fun.0.0 (do (call.17 (call.14 lit.4 lit.5 ))))

generate s-code. See line 12-18

      1 Call main
      2 End
      3 Fun add
      4 Get 2
      5 Get 1
      6 Add
      7 Ret 3
      8 Fun run
      9 Lit 0
     10 Ret 2
     11 Fun main
     12 Lit 15
     13 Call run
     14 Jmp 19
     15 Lit 4
     16 Lit 5
     17 Call add
     18 End
     19 Ret 1

The line "(run (add 4 5 ))" becomes

     12 Lit 15     ;; address of code (add 4 5)
     13 Call run
     14 Jmp 19     ;; do not execute now
     15 Lit 4      ;; the code (call.add lit.4 lit.5)
     16 Lit 5
     17 Call add
     18 End
     19 . . .

Example session

A user program is written as (count) and integrated with nos in "main":

; ---- application --------

(def count (n) (i)
  (do
  (set i 0)
  (while (< i n)
    (do
    (set i (+ i 1))
    (print i) (space)))))

(def main () (p)
  (do
  (sys 5)
  (set activep 0)
  (set sseg 1000)
  (set pid 1)
  (set psw (run (switchp)))
  (set activep 0)
  (set p (run (count 500)))
  (bootnos)))

The (run (count 500))  creates a process to run (count 500).  (bootnos) starts the process running.

To run NOSS, first compile user functions with NOS in nos.txt:

e:\test>nsim32 nut.obj < nos.txt > nos.obj
print
(fun.1.1 (sys.1 get.1 ))
printc
(fun.1.1 (sys.2 get.1 ))
nl
(fun.0.0 (sys.2 lit.10 ))
space
(fun.0.0 (sys.2 lit.32 ))
not
(fun.1.1 (if get.1 lit.0 lit.1 ))
. . .

Then generate s-code from n-code

e:\test>nsim32 gen2.obj < nos.obj > ns.obj

Then run Noss with the .obj executable (sx-code):

e:\test>noss ns.obj

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
*
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
. . .
146 147 148 149 150 151 152 153 154 155 156 157 158 159
*
 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
. . .
 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
 260 261 262 263 264 265 266 267 268
*
 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
. . .
*
487 488 489 490 491 492 493 494 495 496 497 498 499 500
*
9345 clocks

e:\test>

The "*" indicates the task-switching (every 1000 cycles).

22 Aug 2006