Operating System NOS

A computation task is performed in an operating system as a process. A process is a program in execution. A process consists of a program and its attributes for run-time environment such as computation state and other data structure to manage process at run-time.

Multi-task is implemented by time-slicing. Each process takes turn to use the processor to execute its code until its time-slice is over then the next process is started. To divide time into slices, one can visualise that an interrupt event occurs periodically and the processor jumps to execute a special code called Interrupt Service Routine (ISR). Upon completion of ISR, the processor returns back to its process.

The main operating system code to manage multi-task is the task switcher (switchp). Its job is to select the next process. Here is the time line of a processor running a multi-task operating system:

p1 || p2 || p3 || ...

-----> t

where p1, p2 ... are processes and || denotes the task-switching at the interrupt event. In Nos, there are three types of interrupt events: timeout, block, stop. Timeout occurs when a process used up its time-slice. Block is an event that a process is suspended when it requests a operating system service. Stop denotes a process termination.

Task-switcher

Here is the code of the task-switcher

switchp()
di()
event = getevent()
if(event == STOP)
    setValue(activep,DEAD)
    activep = deleteDL(activep)
else
    setValue(activep,READY)
    activep = getNext(activep)
ei()

activep holds the (circular) list of processes scheduled to be run. di() is a disable interrupt function. ei() is an enable interrupt function. They prevent switchp from being interrupted during the task-switching.

To create time-slicing we run Instruction Level Simulator (ILS) for the target machine (such as s-code, sx-chip, som-v2x) and at the end of executing an instruction we check for "interrupt". To actually start/stop a process by interruption, the supervisor code is used to emulate Interrupt Service Routine (ISR) in Nos. The supervisor code save/restore the processor state to/from the data structure of a process. It is performed "at a higher level" above ILS. (In an actual processor it is implemented as a privilege code).

The code for the operating system is executed in the "user space". Only a tiny part of OS must have a special privilege, this part is the supervisor. The supervisor (called Noss, Nut Operating System Supervisor) manages the data structure of the task (called Process Control Block) which involves save/restore the computation state (such as PC, FP, SP) and initiate the operating system code to be executed.

Supervisor Noss

The supervisor is implemented as a function to be called when an interrupt event occurs. It has two internal states: task-switch (psw) and user. When an interrupt occurs, Noss is called (it is in psw state), the current user process (in the queue at activep) is suspended, the task-switcher (it is a special process, switchp) is started. Switchp runs to its completion and calls Noss, activep by now is updated to the next process in the queue. Noss (it is in user state) resumes the process in the queue. Here is the time line of task-switching:

p1 ^psw switchp ^user p2 ...

-----> t

where ^psw denotes an interrupt to call noss (in psw state), ^user denotes call to noss (in user state) when switchp runs to its completion. Here is a pseudo code of noss function.

noss
switch(noss_state)
    psw:
       save computation state of userp
       start switchp
       noss_state = user
    user:
       userp = activep
       restore computation state of userp
       noss_state = psw

The computation state consists of FP,SP and PC. Here is how the ILS looks like:

eval
while runflag do
    clock = clock + 1
    fetch
    decode
    do each instruction
       add: ...
       jmp: ...
       stop: noss(STOP)
       block: noss(BLOCK)
       ...
    if time-out then noss(TIMEOUT)

To simulate a time-out, the number of instruction executed is counted (clock). A time-out occurs when it exceeds a threshold (QUANTA).

Process creation

A special syntax is used to create a process:

p = run( function_name() )

"run" is compiled into a sequence that will call function_name. The function "run" itself is a Nos operating system code to create a process with appropriate attributes (in its data structure) including the correct pointer to body of code of function_name (ads). Here is the "run" function:

run(ads)
p = newp()
setId(p,pid)
pid = pid + 1
p[6] = ads
activep = appendDL(activep, p)
return p

where newp() creates a new Process Control Block that holds attributes.

Nos services

mutual exclusion (mutex)

wait(semaphore)
signal(semaphore)
initsem(semaphore)

message passing

send(p,message)
receive(p)

call to suspend the current process

blockp()

boot the operating system by

bootnos()

Practice session

Nos and a user program are combined into a single source file. It is compiled with an extended Rz compiler (rz34). The object code is run by a special instruction level simulator that incorporates Noss function. Here is an example session:

Assume the source is (myapp.txt):

....

main()
init()
psw = run(switchp())
activep = 0
// start user process
showProduce()
bootnos()

The first three lines are required preliminaries to create the task-switcher process (not in the normal process list). The user program is "showProduce()". At the end the operating system is started by "bootnos()".

Compile the source:

C:> rz34 myapp.txt

The compiler outputs an object file. Run the object file with noss:

C:> noss myapp.obj

The screen output may look like:

load program, last address 718
DP 2024
* 2 * * 3 4 * * 5 6 * * 7 8 * * 9
3375 inst. (system 288 user 3087) switchp 9

DP shows the amount of data segment in used. * denotes task-switching. The last line reports the total number of instructions executed, divided into system and user where system means the number of instructions performing switchp. Lastly the total number of task-switching is reported.

A call stack trace can be turned on (usually for debugging purpose) by changing the definition of TRACE symbol in the header file (compile.h)

#define TRACE

The whole instruction set simulator must be recompiled. Here is a sample of the screen output after turning on the trace mode (so called Godmode):

C:> noss myapp.obj

load program, last address 718
DP 2024
call main
    call init
...
    call showProduce
      call run
...
    call bootnos
      call produce
        call send
...
          call blockp

noss clock 530 active 3
save pid 2 fp 1000 sp 1001 ip 8
event 11 run task switcher

            call switchp
              call di
              call getevent
              call setValue
              call getNext
              call ei

noss clock 562 active 3
restore pid 3 fp 3000 sp 3001 ip 715

          call consume
            call receive
              call di
              call getMbox
              call findmail
              call deleteDL
...
noss clock 3375 active 0

3375 inst. (system 288 user 3087) switchp 9

QUANTA can be changed to observe the behavior when the time-slice is changed by changing its definition in the header file (compile.h)

#define QUANTA 400

Again, the whole ILS must be recompiled for the change to take effect.

end

last update 4 Sept 2011