Nos services
Nos provides several 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. The following example shows how to share a variable between
two processes in synchronisation. The semaphore "mutex" is used to protect
the shared variable. Two semaphores: empty, full, are used to
synchronise two processes.
// --- use semaphore to protect share
resource ------
empty, full, mutex // semaphores
shareVar
writer()
i = 0
while( i < 3 )
wait(empty)
wait(mutex)
shareVar = shareVar + 1
signal(mutex)
signal(full)
i = i + 1
reader()
i = 0
while( i < 3 )
wait(full)
wait(mutex)
print(shareVar)
signal(mutex)
signal(empty)
i = i + 1
p1, p2 // user
process
main()
...
shareVar = 0
empty = initsem()
full = initsem()
mutex = initsem()
p1 = run(writer())
p2 = run(reader())
bootnos()
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
//
send 2..n to p2 ended with -1
produce()
n = 10
i = 2
while( i < n )
send(p2,i)
i = i + 1
send(p2,-1)
// receive 2..n from p1 ended with -1
consume()
m = 1
while( m > 0 )
m = receive(p1)
print(m)
Create and run producer and consumer.
main()
...
p1 = run(produce())
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 similarly explained.
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.
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 ascending order of time value, only the first one is consulted if
it is time-out then the next one is consulted and so on.
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.
The timer process is run after "switchp".
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.
last update 26 Jan 2013