MOS is a simple round-robin scheduling preemptive OS. I will show
how to use interrupt to write a concurrent program supported by a
task-switcher. A process consists of its data structure called
Process Control Block (PCB). PCB contains process's PC, process's SP
(and other attributes). Each process has its own Stack. The main part of
MOS is its scheduler. The scheduler has a queue of the pointer of
PCB.
In the following example, I will show how two processes are created and
then the operating system starts.
process1()
...
process2()
...
main()
p = newp() // create a new process
p.PC = &process1
p.SP = newStack()
enqueue(p) // put it in the process queue
p = newp()
p.PC = &process2
p.SP = newStack()
enqueue(p)
boot() // start the scheduler
We create two PCBs for process1() and process2() and put them in the
process queue. The scheduler is an Interrupt Service Routine.
It is invoked when an interrupt occurs. The task of the scheduler is
to save the current active process (its PC and SP including local states,
all registers) and set up for the next process to run by restoring its PC,
SP, registers. How the actual execution of the real processor
instruction occurs will be shown. It required the knowledge of low level
instruction of a real processor.
// this is invoked when interrupt occurs
tswitch()
p = current process
save current context of p
p =
nextp()
// get the next one in the process queue
restore the context of p // it uses p.SP
PC = p.PC
reti
// return from int, jump to the current p
That is all for a task-switcher. When an interrupt occurs, the
current process is interrupted. Its context is saved in its Stack.
The next process is selected and its context is restored. Then, finally,
jump to that process which make it active until the next interrupt
occurs.
The rest is just the handling of data structure and operations on them
that are required.
newp()
allocate a block of memory for storing PC, SP and other
attributes
return a pointer to this block (called PCB)
newStack()
allocate a block of memory as the stack for a process
return a pointer to this block
Next is the operations on the process queue. The process queue is a
fixed size array storing pointers to PCBs. A global variable "nump"
stores the number of process in the queue. The end of queue is
denoted by 0. The terminated process is denoted by 1.
nextp()
from the present queue index
scan for the next process
update the queue index
return the pointer to PCB
terminate()
terminate the current process
nump--
enqueue(p)
put p to the end of the queue
nump++
The last mysterious thing is boot(). Actually it is rather simple. It
works in a part just like the switcher. It sets up PC and SP then
jumps to start the first process in the queue.
boot()
PC = currentp.PC
SP = currentp.SP
jump to PC // this act needs
low level instruction sequence
The remaining question is "What happen when all processes
terminate?". Some how we must check that there is at least one
process in the queue (during nextp()). When "nump" is zero the operating
system should shut down (the simulation stops).
PCB contains the state of a process. It has the following fields:
0 Program counter
1 stack pointer
2 frame pointer
3 return address reg
4 return value reg
5 state: active/not-active
We use singly linked list with header for both. The header has two
fields: head, end. This will make appending a new cell at the end of
list easy. For semaphore wait list, the operations are
append-list(L,a)
append a cell at the end
of list
delete-head(L)
delete a cell
from the head
We keep the deleted cell in "freelist" and reuse it when a new cell is
required. For process queue, we need a pointer to identify the
current process. Also, we made the list a circular list in order to find
the next process. The members of this list are never deleted because
deleting an arbitrary element required searching for the previous
link. In order to make a process being "out" of the list, we use a
flag in the PCB instead denoting its state: active/not-active. When
we mark the state as not-active, it will be skip when considering the next
process. The operations on this list are:
nextp()
find next process on the process list (from the current
process)
enqueue(p)
put a new member p, at the end of process list
dequeue()
dequeue the current process by marking its PCB state not-active
To know when to terminate the program, we keep "nump" the number of
process in the process list. enqueue() increases this number.
dequeue() decreases this number. when nump is zero the simulation
will terminate.
Let us makes all the above code concrete by coding in S2 assembly language.
trap r1 #15
disable interrupt, r1
contains interrupt numbertrap r1 #16
enable interrupt, r1 contains interrupt numberxch r1
exchange RetAds
with r1 pushm sp
push
multiple register r0..r15 to stackpopm sp
pop
multiple register r0..r15 from stack
The main part of MOS in the task switcher. The implementation is S2 assembly language follows the pseudo code explained earlier.
:tswitch
ld r27 currentp
xch r20
; get RetAds
st r20 @0 r27 ; p.PC =
RetAds
pushm sp
; save current context
st sp @1 r27 ; p.SP
= sp
jal link nextp
jf r27 exit ;
no process in the queue
st r27 currentp ; update currentp
ld sp @1 r27 ; get
p.SP
popm sp
; restore context
ld r20 @0 r27 ; get p.PC
xch r20
; RetAds = p.PC
reti
:exit
trap r0 #stop
ld r27 currentp
xch r20
; get RetAds
st r20 @0 r27 ; p.PC =
RetAds
pushm sp
; save current context
st sp @1 r27 ; p.SP
= sp
jal link nextp
jf r27 exit
; no process in the queue
And restore the context of the next process. r27 holds the pointer to the process (PCB).
st r27 currentp ; update
currentp
ld sp @1 r27 ;
get p.SP
popm sp
; restore context
Then switch to the next process using "swap r20" follows by "reti"
ld r20 @0 r27 ;
get p.PC
xch r20
; RetAds = p.PC
reti
The task-switcher is not interruptible, so we must protect this section of the code. Using Disable Interrupt (di) and Enable Interrupt (ei) to enclose the code to prevent interrupt during running of this code. This is called "critical section".
:tswitch
trap r0 #di
... < critical section>
...
trap r0 #ei
reti
Here is the assembly code (mos2.txt) that
implement newp(), newStack(), enqueue(), terminate(), nextp()
in S2 assembly code. The way to boot MOS is slightly improved.
We made a dummy zeroth process which is not in the process queue and start
the task switcher to switch to the task in the process queue by software
interrupt, int #0
.
jal link newp
st sp @1 retval
st retval currentp ; zeroth p
trap r0 #ei
int
#0
; start by switch p
I create two processes, both count 1 to 10. The interrupt interval
is set to 100. The output shows the distinction between process1 n
and process2 [n]
. Please observe
the frequency of interrupt and the concurrency of two processes.
Once the process1 is terminated, process2 continues to its
end. This application program is tacked at the end of the
operating system code (mos2.txt). In pseudo
code it looks like this:
main()
set up int vec to tswitch()
initialize OS variables
create process1() and put it in the process queue
create process2() and put it in the process queue
start OS by forcing tswitch() with interrupt
global cnt, cnt2
process1()
cnt = 0
while( cnt < 10)
cnt = cnt + 1
print(cnt)
process2()
cnt2 = 0
while( cnt2 < 10)
cnt2 = cnt2 + 1
print(cnt2)
Here is the screen dump.
C:>\iot-rz\test>sim21 mos2.obj
load program, last address 200
>g
interrupt0
[1]interrupt0
1 2 3 4 5 6 7 interrupt0
[2][3][4][5][6][7][8]interrupt0
8 9 10 interrupt0
interrupt0
[9][10]interrupt0
stop, clock 577, execute 577 instructions
>
You can trace the execution of this program step-by-step and watch what happen when the interrupt occurs, how the task-switch works.
Please try it. I set the interrupt interval to 100 (in s21.h). If you change it (you have to recompile the simulator), you can observe the change in the number of interrupt.
Enjoy!
last update 18 Feb 2017