NOS  and NOS Simulator



The NOS (Nut Operating System) consists of function calls (API) for a simple concurrent operating system.  The available functions are:

signal sem    -- signal semaphore
wait sem    -- wait on semaphore
send p mess    -- send message to a process
receive p    -- receive message from a process
run process    -- start a process
bootnos        -- start NOS
switchp        -- task switch, never call by users

Example of use

send/receive message

(def produce (n) (i)
  (do
  (set i 2)
  (while (< i n)
    (do
    (send p2 i)
    (set i (+ i 1))))
  (send p2 -1)))

;; receive 2..n from p1 ended with -1
(def consume () (m flag)
  (do
  (set flag 1)
  (while flag
    (do
    (set m (receive p1))
    (if (< m 0)
      (set flag 0))))
  (nl)))

Using semaphore

Construct a monitor to protest shared variables

def monitor (cmd) ()
  (do
  (wait sem1)
  (if (= cmd 1)
    ... access shared variables
    ;; else
    ... access shared variables
  (signal sem1)))

Starting processes

Create and run producer and consumer.

(def main () ()
  (do
  (di)            ;; disable interrupt
  (set activep 0)    ;; init task-list
  (set sseg 1000)    ;; init stack segment
  (set pid 1)        ;; init process id
  (set p1 (run (produce 1000)))
  (set p2 (run (consume)))
  (bootnos)))

NOS simulator (NOSS)


NOS is executed under NOS simulator which has a processor simulator.  N-code must be converted (code-generate) to native code of a processor.  S-code is chosen to be the native code and the processor to run NOS.  (Running NOS in its N-code will be quite difficult to control under N-processor simulator as it uses implicit control flow of C language).  As S-code is very close to N-code, in fact, S-code is almost a linear form of N-code, makes it easy to convert N-code to S-code.

NOSS itself is very minimal.  It takes control by calling the processor simulator to run a certain number of instructions, called quanta.  The processor returns the control back to NOSS after 3 conditions:
1.   it completes it job, this is called "time-out"
2.   it has been blocked by some action.
3.   the task is completed, the program reached "end".

When the processor handed the control back to NOSS, NOSS call task-switch.  The task-switch code is in the user-space, it is written in NUT. 

Here is the main loop of NOSS:

    while there is task
      call task-switch  

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 so it knows how the task has returned the control.  

Here is how "switchp" work

switchp
  if status = time-out or blocked
    runnable next task
  else                // task is ended
    delete this task
    runnable next task

runnable
  restore c-state

How the user program is executed then?

At the end of task-switch, it always run the next task.  This is accomplished by restoring the computation state of that task.  This means the ip, fp, sp of that task is restored in the processor simulator and then the processor simulator continues to execute until the quanta time is over.

At the end of execution of the processor simulator, it always save the computation state of the current process. Saving/restoring the computation state are done by the function calls (the special instructions to support OS functions).  There are several  system calls supported in S-processor:

enable interrupt
disable interrupt
save c-state
restore c-state
block a task

Processor simulator

Here is the main loop of the processor simulator:

eval
  clock = 0
  while runflag
    if interrupt_flag
      if clock > QUANTA
         status = time-out
         break
    execute one instruction
    clock++
  save c-state

The time-out can be disable by the system call: enable/disable interrupt so that uninterruptible function calls can be implemented.  

Implementation of process

The data structure of a process contains 10 fields:

next    -- doubly link
prev    -- doubly link
id    -- process id, not really use
value    -- state of the process, not really use
fp    -- fp,sp,ip are the computation states
sp
ip
mbox    -- pointer to mail box, list of process
await    -- pointer to await box, list of process
message    -- message buffer

The main data structure used by NOS is the process descriptor above.  The task-list is a doubly linked list of process descriptors (it is also a circular list, so switching to the next process is easy).  The computation state is restored upon entering the user code.  The saving is done at the end of executing a user code in the last line of the main loop of the processor simulator (eval).  The computation state is restored when switching from "switchp" to a user code (on making a process runnable by calling the syscall restore c-state, (sys 9 p)).  

The time line of NOSS

start NOS,    X switchp Y  user code  X switchp Y user code X ...
              |                       |                     |
<-- quanta --> <---- quanta ---------> <----- quanta ------>

where X is saving c-state, Y is restoring c-state

Mail box

The message passing in NOS is implemented as a blocking protocol where the sender and receiver wait until the exchange is completed before continuing.  This is done using two mailboxes (the process-list): mbox and await box.  

send p mess
  if there is a process p wait for it
    put mess to p's buffer
    wakeup p
  else
    block itself
    append itself to p's mbox

receive p
  if there is a process p mail in mbox
    take the message from p's buffer
    wakeup p
  else
    block itself
    append itself to p's await

There are two buffers, one in the sender and other in the receiver. The process descriptor is attached to the mbox/await so that waking up a process associated with the mail is simple.  The behaviour of mail from a producer/consumer cycle is as follows:

Suppose a producer streams the messages (integers) 2..n to a consumer.  The producer's output is marked "!n" and the receiver's output is marked " "n ". The task-switched is marked "*".  The trace is:

!2  * "2  * !3 !4  * "3 "4  * !5 !6  * "5 "6  * !7 !8  * "7 "8  * !9  *  "9 . . .

This behaviour can be explained as follows:

The following is the trace of sending/receiving messages between two processes: s, r.

notation

sM send mbox
sA send await
rM receive mbox
rA receive await
sB sender block
rB receiver block
p producer
c consumer

The trace is:
1 p: sM sB *
2 c: rM rA rB *
3 p: sA sM sB *
4 c: rM rA rB * ...

The first line says that the sender just sent a message to the receiver's mbox then itself is blocked.   The second line is quite interesting.  It says the receiver retrieves the message from the sender's buffer and then continue to execute it's program which do "receive p".  This call makes the receiver to send itself to the sender's await box, then itself is blocked.  This mean "r" is waiting for a message from "s".  Once "s" wakeups "r", "r" will have its message in its buffer.  Line 3, 4 can be similary explained.

Performance of NOS

The overhead of task-switching is quite small.  Measuring the time spends in the system kernel for doing "switchp" results in 5% of the total number of instruction executed of benchmarks.  In term of the number of instruction executed per task-switch, it takes 30 instructions of the optimised s-code (50 for non-optimised s-code).  (see profile1..9)

For message passing, around 170 instructions of optimised s-code are executed per message.  (see mail-beh)

last update 20 Feb 2005
P. Chongstitvatana