Nos services

Nos provides serveral services: semaphore, monitor, message passing, timer

Process communication

There are two ways to communicate (passing some values) between processes:

1 by share variables
2 by message passing

Share variables

A semaphore is used to provide mutual exclusion of access to share variables. The share variable will be accessed by only one process at a time. (remember that processes can be concurrent therefore at any time there can be more than one process trying to access the same variable). (read OS concept) send and signal are used in order to access a semaphore.

;; ---- semaphore ------------
;; field: sval(value) slist(wait-list)
;; semaphore access functions

(def getsval (s) () (vec s 0))
(def getslist (s) () (vec s 1))
(def setsval (s v) () (setv s 0 v))
(def setslist (s v) () (setv s 1 v))

(def initsem (v) (s1)
(do
(set s1 (new 2))
(setsval s1 v)
(setslist s1 0)   ;; wait-list nil
s1))

(def wakeup (p) ()
(do
(setValue p READY)
(set activep (appendDL activep p))))

(def signal (s) (p)
(do
(di)
(set p (getslist s))
(if (!= p 0)
    (do
    (setslist s (deleteDL p))
    (wakeup p))
    ;; else
    (setsval s (+ (getsval s) 1)))
(ei)))

(def wait (s) (v p)
(do
(di)
(set v (getsval s))
(if (<= v 0)
    (do                 ;; block activep to WAIT
    (set p activep)
    (set activep (deleteDL activep))
    (setValue p WAIT)   ;; to wait-list
    (setslist s (appendDL (getslist s) p))
    (blockp))           ;; block
    ;; else
    (setsval s (- v 1)))
(ei)))

Construct a monitor to protect shared variables

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

Message passing

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 mail-boxes: in-box 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 in-box

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

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

Example of use of send/receive message

(let p1 p2)

(def produce (n) (i)
(do
(set i 2)
(while (< i n)
    (do
    (send p2 i)
    (set i (+ i 1))))
(send p2 (- 0 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)))

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 pid 1)
(set psw (run (switchp)))
(set activep 0)
(set p1 (run (produce 1000)))
(set p2 (run (consume)))
(bootnos)))

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 in-box
sA send await
rM receive in-box
rA receive await
sB sender block
rB receiver block

The trace is:

1 producer: sM sB *
2 consumer: rM rA rB *
3 producer: sA sM sB *
4 consumer: rM rA rB * ...

The first line says that the sender just sent a message to the receiver's in-box 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 does "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.

With the benchmark, sending and receiving 1000 messages in total 171037 instructions, with nut25 all optimisations turned on (macro, prim, lxvd, sxvd). Therefore the number of instruction for passing (send and receive) one message is 171037/1000 = 170 inst./mess.

Timer

To facilitate a real-time system, some operating system functions needed to be supported. In our system, the real-time clock is the clock of running the processor.

gettime() returns the real-time clock.

timer(t)

set a timer to be time-out at t cycles in the future, not earlier than gettime+t. timer is used to schedule a task according to some real-time.

How a timer is implemented?

A timer stores its time value as a field in PD. A timer list keeps track of the processes that have been scheduled to time-out in the future by "timer". The time value in PD is an absolute time. When a timer is set to t, the time value in PD is set to gettime+t. The process that executes "timer" is blocked. It is removed from the process queue and it is added to the timer list. The timer list is sorted according to the time values from earliest time to the latest. This list will be processed by a timer process which is scheduled by the supervisor, noss.

Timer process

The time value in the list is compared to the master time (the global variable clock in the processor simulator). If it is less than the
master time the owner process of this timer is awaken. As the timer list is sorted in accending order of time value, only the first one is consulted if it is time-out then the next one is consulted and so on.

Granuality of timer

How precise the timer be depends on how often the timer process is scheduled to run. The overhead depends on this rate. It is reasonable to have the granuality at most the same as "quanta". Then, the timer process can be scheduled to run after the task switcher.

What Noss needs to do?

Noss needs to run "timer" after "switchp". The time-out timer process will be queued either at the front of the process queue or the back depends on the scheduling policy. What to do when there is no more process in the process queue? To simulate the real-time, if the timer list is not empty, and the process queue is empty, then the first process in the timer list should be scheduled to be run. The master time should be updated to advance to the time value of that process. This is similar to an ordinary event-
driven simulation based on time.

20 Aug 2006