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
skip the "1"
if the "0" is found go back to the beginning of
the queue.
update the queue index
return the pointer to PCB
terminate()
terminate the current process by placing "1" in the current
position in queue,
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).
Let us makes all the above code concrete by coding in S2 assembly
language.
To simplify the writing of MOS, those support functions for MOS are implemented as extended instructions using "trap n" in S2.1. The following functions are included in the simulator s21mos. You need to read mos.c in the tool package s21mos.zip to see how they are written.
trap 10
newp()
return pointer to block of memory (PCB) in r27trap 11
newStack() return pointer
to block of memory (Stack) in r27The process queue is managed internally inside the simulator (that is, it is outside of S2 space).
trap 12
enqueue() insert the
current process (in r1) into the process queue,trap 13
terminate() mark the
current process in the queue as terminated (by value 1)trap 14
nextp() scan the process
queue and return the next process pointer in r27The rest are for supporting auxiliary functions:
trap 15
di
disable interrupttrap 16
ei
enable interrupttrap 17
print1() print r1 of process1,
show with <.>
trap 18
print2()
print r1 of process2, show with [.]
The main part of MOS in the task switcher. The implementation is S2 assembly language follows the pseudo code explained earlier.
:tswitch
trap di
ld r27 currentp
savt
r20 ;; get RetAds
st r20 @0 r27 ;; p.PC = RetAds
savr sp
;; save current context
st sp @1 r27 ;; p.SP = sp
trap nextp
jf r27 exit ;; no
process in the queue
st r27 currentp ;; update currentp
ld sp @1 r27 ;; get p.SP
resr sp
;; restore context
ld r20 @0 r27 ;; get p.PC
rest
r20 ;; RetAds = p.PC
trap ei
reti
:exit
trap stop
ld r27 currentp
savt
r20 ;; get RetAds
st r20 @0 r27 ;; p.PC = RetAds
savr sp
;; save current context
st sp @1 r27 ;; p.SP = sp
Then we get the next process (trap nextp returns r27) and check whether there is any process in the queue.
trap 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
resr sp
;; restore context
Then switch to the next process using "rest r20" follows by "reti"
ld r20 @0 r27 ;; get
p.PC
rest
r20 ;; RetAds =
p.PC
trap ei
reti
The task-switcher is not interruptible, so we must protect this section of the code. Using Disable Interrupt (trap di) and Enable Interrupt (trap ei) to enclose the code to prevent interrupt during running of this code. This is called "critical section".
:tswitch
trap di
... < critical section>
...
trap ei
reti
I create two processes, one process counts to 5, another process counts
to 10. The interrupt interval is set to 30. The output shows the
distinction between process1 <.>
and process2 [.]
.
Please observe the frequency of interrupt and the concurrency of two
processes. Once the process1 is terminated, process2 continues to
its end.
The full assembly code is here (mos.txt). Here is the screen dump.
C:\s21i\test>sim21i mos.obj
load program, last address 62
>g
<1> interrupt
[1] [2] interrupt
<2> <3> interrupt
[3] [4] interrupt
<4> <5> interrupt
[5] [6] [7] interrupt
[8] [9] interrupt
[10] interrupt
stop, execute 248 instructions
>q
C:\s21i\test>
You can trace the execution of this program step-by-step and watch what happen when the interrupt occurs, how the task-switch works. I put additional information on the simulator when run it single step. It shows all relevant register values, process queue, and two PCBs. Here is some screen dump.
C:\s21i\test>sim21i mos.obj
load program, last address 62
>t
PC 0 trap
r15 r1:0 r2:0 r3:0
r4:0 r5:0 r6:0 r7:0 r8:0 r9:0
r20:0 r21:0 r22:0 r23:0 r24:0 r25:0 r26:0 r27:0 r28:0 r29:0
q ix 0 :0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
PCB [0 0] [0 0]
>b 46
>g
<1> interrupt
>t
PC 46 trap r15
r1:1 r2:0 r3:0 r4:0 r5:1 r6:0 r7:0 r8:0 r9:0
r20:0 r21:0 r22:0 r23:0 r24:0 r25:0 r26:0 r27:2380 r28:0 r29:0
q ix 0 :2100 2116 0 0 0 0 0 0 0 0 0 0 0 0 0 0
PCB [26 2300] [36 2380]
>
Here is the assembly code (mos2.txt) that
implement newp(), newStack(), enqueue(), terminate(), nextp()
in S2 assembly code (instead of special trap instructions). 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
.
Please use the s21mos2.zip package
to run the code.
jal link newp
st sp @1 retval
st retval currentp ;; zeroth p
trap ei
int
0
;; start by switch p
Please try it. I set the interrupt interval to 100 (in s21.h). If you change it, you can observe the change in the number of interrupt.
Enjoy!
last update 13 Apr 2016 Happy Songkran!