Nut Operating System
Nos composed of user-space functions (running in user-space). Nos
models concurrency using process. The share-resource accesses are
controlled with semaphores. The processes in Nos communicate with
each other through message passing. The crucial real-time functions are
supported therefore Nos can support real-time tasks. Nos supports the
following functions:
- create a process
- terminate a process
- manage the process queue
- task switching
- wait/signal a semaphore
- send/receive a message
- get a real-time clock
- set a timer
Process
A process is an independent computation which can run concurrently with
other process. A process is declared as a normal defined
function. Initial values can be passed as parameters at the
starting time of a process. A process will end its execution by
self-termination when it executes the last instruction at the end of
program. This is different from the execution of a function which
ends its execution by returning to the caller. A program that
calls a process will start that process execution, that program then
will continue to work without waiting. A process never returns to
its caller.
A process is a program in execution. Several processes can be
active at the same time. The concurrency is achieved via
multi-threading ("light weight process"). A heavy weight process
is a process with a separate address space. It needs a mechanism
to do the address mapping between virtual address and physical
address. A light weight process has single address space. A
thread is a trace of execution, a single thread process is resulted
from co-operative process (via co-routinte). A multi-thread
process has several traces at the same time. This can be
accomplished by pre-emptive scheduler with time-slicing. A light
weight process is much cheaper to create than a heavy weight process.
Each process has its own stack segment. In Nos, there is a single
address space, the stack segment of all processes are in the same
address space. The advantage is that there is no translation
between virtual address and physical address therefore it is fast and
simple. The disadvantage is that there is no protection between
processes. Each process has its process descriptor (PD) to store
the necessary information. A process descriptor in Nos consists
of 12 fields:
- link previous
- link next
- process id
- process status
- PC
- SP
- FP
- TS
- in-box
- await-box
- message
- timer
The link previous/next are used to form the list of processes, for
example the process queue. The process identifier is a unique
number used to label a process. The process status holds the
state of process (to be explained later). The fields {PC, SP, FP,
TS} hold the computation state of the process. The mail-box
(in-box and await-box) is used to communicate between processes.
The in-box is the list of processes that sent messages to this
process. The await-box is the list of processes that are waiting
for messages from this process. The timer holds the timer value of this
process.
<fig a process descriptor>
Scheduler
When a process is created it is ready to start the execution. Its PD
will be linked to the "ready list" (the process queue) which is a
doubly linked circular list used by the scheduler. A scheduler
has the duty of selecting a process to run from the ready list.
The scheduling policy of Nos is a Round-Robin policy where an equal
time-slice is allocated for every process and the process is scheduled
on first-come first-serve basis. A scheduler will enable a process in
the ready list to run until its time-slice is over and then switches to
the next process in the list. If a process enters a "wait" state,
it is said to be blocked. A process is usually blocked because it
performs some operation that requires waiting for another process, such
as waiting for the receiver to retrieve a message. When a process
is blocked, its PD will be removed from the ready list. The
process in "wait" state can be awaken by other process. Its PD
will be inserted into the end of the ready list. To perform the
switch from one process to another process (task switching), the
current state of computation {PC, SP, FP, TS} of the active process is
saved in its PD and the state of computation of the process to be run
is restored. The first process to be active is the process to run
the main program. A process is run until it is time-out, or it is
blocked or it is terminated. "switchp" is the task switcher
function in Nos. Here is how "switchp" work.
switchp
if status is time-out or
blocked
runnable next
task
else status is terminated
delete this
task
runnable next
task
where status is the state of the process, runnable marks the process as
running.
Before we go into more details of the operating system functions, we
must understand the basic of running a task first.
Nos supervisor (NOSS)
Nos is executed under Nos supervisor. Nos supervisor runs on top
of the processor simulator. Noss is a priviledge program. A priviledge
program is a program that is "out-of-bound" of user programs. A
priviledge program provides mechanism for executing a user program, for
example, the sx processor simulator is a priviledge program that
"execute" s-code. In our implementation, priviledge programs are
written in C. User programs are written in Nut. The
relationship between Nos supervisor and the processor simulator can be
understood by regarding Noss as issueing an "interrupt" to the
processor. The processor continuously executes a program (running a
process) until an interrupt occurs then the supervisor takes
action. The interrupt can occur only at the end of executing an
instruction. There are three interrupt events: time-out, stop, block.
- time-out -- the current process has used up its own time-slice.
- stop -- the current process runs to completion.
- block -- the current process is blocked (to be resumed later).
The supervisor (Noss) takes action in response to the interrupt events
as follows.
notation [state]
[start]
set up process queue
|
v
[user]
<--- run user process
| |
|
A | stop
v |
[switch] ---
run task switcher
A = time-out/stop/block
<fig Noss state diagram>
At [start], the main program creates processes and the process queue.
Noss schedules only two kinds of processes: user process and
switchp. "switchp" is created and has its own PD but it is
privileged and never enters the process queue. Once the process
queue is ready, at the state [user], a user process is run. The user
process is run until it is time-out/stopped/blocked. Then Noss
calls the "switchp", at the state [switch]. "switchp" runs to
completion. It must not be interrupted as it is manipulating the
process queue. Then the state is going back to run a user process.
At the end of task-switch, Noss always run the next task. This is
accomplished by restoring the computation state of that process.
This means the PC, SP, FP, TS of that process are restored to the
processor simulator and then the processor simulator continues to
execute until the interrupt occurs. The following pseudo code described
noss.
noss
if there is no process in
the queue
stop the
whole simulation
else
update
status to nos
if state
= switch
save current user process
restore "switchp"
state = user
else
state = user
restore active process
state = switch
The process descriptor contains C-state. Saving and restoring C-state
are the act of transferring C-state between the processor simulator and
the process descriptor. Noss does the restoring of C-state by running
the code in user-space. This restoring will affect the flow of
execution, as the instruction pointer is changed, it does a jump in the
program. As Noss is responsible to run the task-switcher, it must
save C-state. Saving C-state can not be done in user-space as the
precise state has been changed when trying to run the "saving state"
function. So, save-Cstate is done in the main loop of Noss (in
C). This gives the save-Cstate a special privilege (so called
"kernel" in OS vocabulary). It is implemented as a system call
instruction.
Simulation of
interrupt
To simulate the "interrupt", the processor calls Noss from time to time
(this is called "yield"). The interrupt interval is controlled by
counting the cycle used since the last call to Noss.
The processor returns the control back to Noss after 3 conditions:
- its time-slice has been used up, this is called "time-out"
- the process has been blocked by executing some operation, this is
called "blocked".
- the task is completed, the program reached "end", this is called
"stopped".
When the processor hands the control back to Noss, Noss calls
task-switch. The task-switch code is in the user-space. 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 it
knows how the task has returned the control.
Noss is minimal in the sense that it does not do a lot of things by
itself. The only thing it does is to call "switchp". Noss
monitors the state of computation of a process through two global
variables: status and activep.
Processor simulator
In the processor simulator, the main simulation loop is "eval". It
executes a fixed number of cycles. This is the main fetch-execute
cycle of the processor (in fact most processor simulator are like this):
eval
count = 0
loop
if count >
limit break
fetch an
instruction
execute the
instruction
count = count
+ 1
To implement "interrupt", a flag (intflag) is used to disable the
break. This flag can be turned on/off by the system calls.
eval2
count = 0
loop
if intflag == 1
if
count > limit break
fetch an
instruction
execute the
instruction
count = count
+ 1
The system calls that support Nos are:
20 disable interrupt
21 enable interrupt
22 block a process
The following code describes the main loop of the processor simulator.
eval
set PC
while runflag = 1
run one
instruction
yield
yield
if intflag = 1
if no of cycle
used > TIMEOUT
noss(time_out)
where runflag controls the termination of noss itself, intflag is the
interrupt flag used to disable/enable interrupt.
How a process is
created
A function "run" is used to create a process and put it to the process
queue. Although "run" looks like a normal function, it can not be
compiled into a normal function call. The argument to "run" is a
function call which will be turned into a process so it should not be
evaluated. A call to "run" is compiled into the code that passes an
address of the function call. The argument to call.run in n-code
is just a user-function call with its arguments as usual.
However, this argument will not be evaluated. Instead, the
address of the code of this call will be generated as an argument
of "run". This code will be activated by the scheduler as a
process. See the following example:
in nut
(def
add (a b) () (+ a b))
(def run (f) () 0)
(def main () ()
(do
(run (add 4 5))))
in n-code
add
(fun.2.2 (+ get.1 get.2 ))
run
(fun.1.1 (lit.0 ))
main
(fun.0.0 (do (call.17 (call.14
lit.4 lit.5 ))))
generate s-code. See line 12-18
1
Call main
2
End
3
Fun add
4
Get 2
5
Get 1
6
Add
7
Ret 3
8
Fun run
9
Lit 0
10 Ret 2
11 Fun
main
12 Lit 15
13 Call
run
14 Jmp 19
15 Lit 4
16 Lit 5
17 Call
add
18 End
19 Ret 1
The line "(run (add 4 5 ))" becomes
12 Lit
15 ;; address of code (add 4 5)
13 Call
run
14 Jmp
19 ;; do not execute now
15 Lit
4 ;; the code (call.add lit.4 lit.5)
16 Lit 5
17 Call
add
18 End
19 . . .
Example session
A user program is written as (count) and integrated with nos in "main":
;
---- application --------
(def count (n) (i)
(do
(set i 0)
(while (< i n)
(do
(set i (+ i 1))
(print i)
(space)))))
(def main () (p)
(do
(sys 5)
(set activep 0)
(set sseg 1000)
(set pid 1)
(set psw (run (switchp)))
(set activep 0)
(set p (run (count
500)))
(bootnos)))
The (run (count 500)) creates a process to run (count 500).
(bootnos) starts the process running.
To run NOSS, first compile user functions with NOS in nos.txt:
e:\test>nsim32
nut.obj < nos.txt > nos.obj
print
(fun.1.1 (sys.1 get.1 ))
printc
(fun.1.1 (sys.2 get.1 ))
nl
(fun.0.0 (sys.2 lit.10 ))
space
(fun.0.0 (sys.2 lit.32 ))
not
(fun.1.1 (if get.1 lit.0 lit.1 ))
. . .
Then generate s-code from n-code
e:\test>nsim32
gen2.obj < nos.obj > ns.obj
Then run Noss with the .obj executable (sx-code):
e:\test>noss
ns.obj
1 2 3 4 5 6 7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
*
50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
. . .
146 147 148 149 150 151 152 153
154 155 156 157 158 159
*
160 161 162 163 164 165 166
167 168 169 170 171 172 173 174 175 176 177 178 179
. . .
240 241 242 243 244 245 246
247 248 249 250 251 252 253 254 255 256 257 258 259
260 261 262 263 264 265 266
267 268
*
269 270 271 272 273 274 275
276 277 278 279 280 281 282 283 284 285 286 287 288
. . .
*
487 488 489 490 491 492 493 494
495 496 497 498 499 500
*
9345 clocks
e:\test>
The "*" indicates the task-switching (every 1000 cycles).
22 Aug 2006