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