Multitask OS (MOS)

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 and Frame. 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, SP, FP including local states, all registers) and set up for the next process to run by restoring its PC, SP, FP, 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 circular list storing pointers to PCBs. A global variable "nump" stores the number of process in the queue.

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).

Data structure

Process control block (PCB)

PCB contains the state of a process. It has the following fields:

0 Program counter
1 stack pointer
2 frame pointer
3 process state (1 active, 0 dead)

PC stores the program counter of the process at the time of task switching so that it can return to continue. SP points to local stack. FP points to local frame (activation record). Both local stack and local frame are created at the time of creating a process. In the local stack, low register 0..15 are pushed there including return address register and return value register.

Process queue and semaphore

Process queue is a singly linked circular list where the end of list points to the first item in the list. A node stores pointer to PCB. Q is the header of this list. It contains head:tail which points to the first node in the queue and the last node in the queue. This made it simple to delete a node at the front and append
a node at the end. We will use notation head/tail to denote a node (a node contains two adjacent cells).

List functions

append(L,a)          // append
      a to list L, need special case when queue is empty

e = tail(L)
tail(e) = a // link end to a
tail(L) = a // update L

delete(L)           
      // delete the first node from L

  a = head(L)        // node to be
      deleted

b = tail(L)
if ( a == b) // singleton
head(L) = 0 // make L empty
else

    head(L) = tail(a)    // update L to
      point to next node

p = head(a)
free(a)

Waiting list of a semaphore can use this similar queue.

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. The round-robin schedule is easy. The next process can be found in one step in the circular list. The operations on this list are:

Queue functions

Q is the process queue. It is a node.

nextp()               find next process on the process list (from the current process)
enqueue(p)          append a new node p at the end of process list
dequeue()           delete its node from the process queue

nextp()           //
      qq is the index to currentp

        p = tail(qq)

        return head(p)

enqueue(p)
nump = nump + 1
e = new(p) // get a node
append(Q,e)
tail(e) = head(Q)

dequeue()       // delete the current
      process from the queue

\
nump = nump - 1
p = currentp
p[3] = 0 // mark it non-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.

Extended Instructions

S2 has extended instructions to deal with interrupt:

int #n      software interrupt

      ei #n       enable interrupt

      di #n       diable interrupt

      reti        return from interrupt

      wfi         wait for interrupt

when interrupt occurs, return address is saved in R[31]. reti uses this register to return to the point where interrupt occurs and enable the system interrupt (hardware related).

There are supporting function for implementing OS. They are "trap r1 #n" forms.

trap r1 #15 push multiple registers r0..r15 to stack (r1 is stack pointer)
trap r1 #16 pop multiple registers r0..r15 from stack (r1 is stack pointer)

MOS in Assembly

Before we write assembly code we must layout the memory. To assign location of all variables and data, because we need to know absolute addresses.

Memory Map

0..900     code
1000         interrupt vector
1500..1999    global variables
2000        process queue
2100              process control block
2300              stack

Task Switcher

The main part of MOS in the task switcher. The implementation is S2 assembly language follows the pseudo code explained earlier.

:tswitch        

          trap sp #15   ; save current context

          ld r1 currentp

          st r31 @0 r1     ;  p.PC = RetAds

          st sp @1 r1      ;  p.SP = sp

          st fp @2 r1      ;  p.FP
      = fp

      

         jal link nextp

         jf r27 exit       ;  no
      process in the queue

      

         ld r1 currentp

         ld r31 @0 r1    ; restore p.PC

         ld sp @1 r1     ; restore p.SP

         ld sp @2 r1     ; restore p.FP

         trap sp #16    ; restore context  

         reti

      :exit        

          trap r0 #stop

This section of code saves the current process context: PC, SP, Stack (register r0..r15). sp (r29) is a register that is persistent. It lives across all process switches.

    trap sp #15   ; save current context

          ld r1 currentp

          st r31 @0 r1     ;  p.PC = RetAds

          st sp @1 r1      ;  p.SP = sp

          st fp @2 r1      ;  p.FP
      = fp

Then we get the next process (nextp returns r27) and check whether there is any process in the queue.

jal link nextp jf r27 exit ; no process in the queue

And restore the context of the next process.

ld r1 currentp ld r31 @0 r1 ; restore p.PC ld sp @1 r1 ; restore p.SP ld sp @2 r1 ; restore p.FP trap sp #16 ; restore context

Then restore PC to switch to the next process, follows by "reti"

Critical Section

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
     di #0
    ... < critical section>
    ...
    ei #0
    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 ei #0 int #0 ; start by switch p

Example

I create two processes, both count upward. 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   cnt1, cnt2

clock1()
    cnt1 = 0
    while( 1 )
        cnt = cnt + 1
        print(cnt1)
        doze()

clock2()
    cnt2 = 100
    while( 1)
        cnt2 = cnt2 + 1
        print(cnt2)
        doze()

Here is the screen dump.

C:>\iot-rz\test>sim21 mos2.obj

       load program, last address 200

       >g

       interrupt0

       [101]  interrupt0

      2 interrupt0

      [102]  interrupt0

      3  interrupt0

      [103] interrupt0

      . . .

      infinite loop

       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.

Update: MOS written in Rz is here (mos-rz.txt). Only the task-switching needs to be done in assembly.

Enjoy!

last update 8 Feb 2025