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