Itsy-OS Kernel: Preemptive Switcher & Memory Manager

Itsy-OS v0.1 is a small 8086 operating system kernel providing two basic services: a simple preemptive task switcher and memory management. If necessary, simple IPC and task management can be added to provide the features of a traditional microkernel.

Weighing in at about 380 bytes, Itsy should port well to tiny architectures.

Memory Control Blocks

Each block of memory is preceded by a memory control block which is 32 bytes long. The blocks of memory are arranged as a circular linked list. The first memory control block resides in segment 050h.

org 0h
; -----------------------------
; [Master Memory Control Block]
; -----------------------------

M_NEXT:dw 0             ; address of next MCB
M_LAST:dw 0             ; address of previous MCB
M_PARA:dw 0             ; size of this block in paragraphs including MCB
M_FLAG:db 0             ; flags
       db 0             ;
M_NPRO:dw 0             ; next MCB containing process, zero if not in queue
M_LPRO:dw 0             ; previous MCB containing process, or zero
M_STKP:dw 0             ; stack pointer
M_STKS:dw 0             ; stack segment

M_TIME:dw 0             ; time allocated / de-allocated
M_DATE:dw 0             ; date allocated / de-allocated
M_OWNR:dw 0             ; user number who owns this memory
M_NAME:db '          '  ; name of this memory block

; ---------------------------------------------------------------------------

; flag bits
F_FREE equ 01h          ; zero if this is free memory
F_ACTI equ 02h          ; zero if no task ready for CPU

; ---------------------------------------------------------------------------

  jmp E_INIT            ; setup kernel

; ---------------------------------------------------------------------------

; -------------------
; [Nucleus Data Area]
; -------------------

D_PCP:dw 0              ; segment of current process's MCB
D_SWEN:db 0             ; set to zero when switching disabled

Task Switcher

The task switcher is called by the timer interrupt. First it checks whether switching is disabled. If not:

• disable switching
• save the registers of the current task on the stack
• save the stack pointer of the current task in it's MCB
• find the next MCB with an available task
• restore the new task's stack pointer and registers
• enable switching and transfer control to the new task

; ---------------
; [Task Switcher]
; ---------------

E_SWITCHER:
; test if the switcher is enabled or disabled (indivisible test and set)
  pushf
  push cx
  xor cx,cx
  cs xchg cl,byte[D_SWEN]
  jcxz N_NOSWITCH

; save the registers of the current process
  push ax
  push dx
  push bx
  push bp
  push si
  push di
  push es
  push ds

; save the stack of the current process
  mov di,M_STKP
  cs mov ds,word[di+D_PCP-M_STKP]
  mov word[di],sp     ; M_STKP
  mov word[di+2],ss   ; M_STKS


E_SHORTCUT:

; select an active task to switch to
N_SELTASK:
  mov ds,word[di-4]        ; M_NPRO
  test byte[di-6],F_ACTI   ; M_FLAG
  jz N_SELTASK             ; is this task active?
  cs mov word[di+D_PCP-M_STKP],ds

; restore saved state of process being switched to
  mov sp,word[di]          ; M_STKP
  mov ss,word[di+2]        ; M_STKS
  pop ds
  pop es
  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop ax
  call E_ENABLE
N_NOSWITCH:
  pop cx
  popf
  iret

Deallocate Memory

Called with DS = MCB of memory to free. Deallocated memory is wiped with 0CCh.

Switching is disabled while the memory structure is being modified. If the memory being deallocated contains a process, it is removed from the process queue. If adjacent memory blocks are marked as free, the blocks are combined.

; -------------------
; [deallocate memory]
; -------------------

E_MEMDEALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di                   ; M_NEXT
  mov ax,word[di+M_NPRO]      ; see if there is entry in process queue
  test ax,ax
  jz N_NOPROC                 ; if there isn't, simply free the memory
  mov es,word[di+M_LPRO]      ; and if there is, remove it!
  es mov word[di+M_NPRO],ax
  mov bx,es
  mov es,ax
  es mov word[di+M_LPRO],bx

  mov ax,ds
  cs cmp ax,word[D_PCP]       ; check if process being killed is the current
  jnz N_NOPROC
  cs mov word[D_PCP],bx       ; if so, set last process as current

  call N_NOPROC               ; free the memory,
  mov di,M_STKP
  jmp short E_SHORTCUT        ; and then afterwards, switch to another task


N_NOPROC:
  mov bp,ds                   ; bp = first paragraph to clear
  mov bx,word[di+M_PARA]      ; bx = number of paragraphs to clear

  mov es,word[di]
  es test byte[di+M_FLAG],F_FREE        ; is next block free?
  jnz N_NNOTJOIN                        ; if not, can't join them

  es mov ax,word[di+M_PARA]             ; get size of next block
  add word[di+M_PARA],ax                ; add to size of this block
  es mov ax,word[di]                    ; move M_NEXT of next...
  mov word[di],ax                       ;  ...to M_NEXT of current
  inc bx                                ; an extra 2 paragraphs to clear
  inc bx
N_NNOTJOIN:
  and byte[di+M_FLAG],0FFh-F_FREE-F_ACTI       ; mark as free

  mov es,word[di+M_LAST]
  es test byte[di+M_FLAG],F_FREE        ; is previous block free?
  jnz N_PNOTJOIN                        ; if not, can't join them

  mov ax,word[di+M_PARA]                ; get size of this block
  es add word[di+M_PARA],ax             ; add to size of previous block
  mov ax,word[di]                       ; move M_NEXT of current...
  es mov word[di],ax                    ;  ... to M_NEXT of previous
  jmp short N_EXTRA2P
                                        ; block already marked as free
N_PNOTJOIN:
  inc bp              ; don't clear MCB
  inc bp
  dec bx
  dec bx

N_EXTRA2P:
  cld                 ; clear memory - bp=location, bx=paragraphs
  mov ax,0CCCCh       ; code for an INT3 instruction to fill memory with
  mov dx,01000h
N_CLRGO:
  mov es,bp
  sub bx,dx
  jc N_CLRFIN
  mov cx,08000h
  rep stosw
  add bp,dx
  jmp short N_CLRGO

N_CLRFIN:
  add bx,dx
  mov cl,3
  shl bx,cl
  mov cx,bx
  rep stosw

E_ENABLE:
  cs inc byte[D_SWEN] ; enable switching
  ret

Allocate Memory

Called with AX = number of paragraphs required. Returns DS = location of memory, or DS = 0 if no memory available. Switching is disabled while the memory structure is being modified. Allocation uses a simple best fit algorithm.

; -----------------
; [allocate memory]
; -----------------

E_MEMALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di
  xor dx,dx                    ; segment of current choice
  xor cx,cx                    ; left-over memory from current choice
  inc ax
  inc ax
  mov bx,050                   ; MMCB

N_MOREMEM:
  mov ds,bx
  test byte[di+M_FLAG],F_FREE  ; is the block we are looking at empty?
  jnz N_WONTFIT                ; if it isn't, move on

  mov bx,word[di+M_PARA]
  sub bx,ax                    ; check size
  jc N_WONTFIT
  jz N_EXACT                   ; perfect fit :-)

; ** KLUDGE ***
  cmp bx,3                     ; if leftover memory block smaller than 3
  jc N_WONTFIT                 ; paragraphs, it would be too small to contain
                               ; a MCB.  Maybe handle this better later

  cmp cx,bx                    ; bx= size of potential leftover memory block
  jc N_WONTFIT                 ; have we found a better fit?
  mov cx,bx
  mov dx,ds                    ; if so, then select it!
N_WONTFIT:
  mov bx,word[di]              ; M_NEXT
  cmp bx,050                   ; are we at MMCB?
  jnz N_MOREMEM

  test dx,dx
  jne N_ALLOCIT
  mov ds,dx                   ; out of memory :-(
  jmp short N_ALEXIT
N_ALLOCIT:
  mov ds,dx
  mov es,word[di]              ; M_NEXT, es= next block

  mov bx,word[di+M_PARA]       ; bx= number of paragraphs for this block
  add bx,dx                    ; bx= end of this block
  sub bx,ax                    ; bx= location of new block's MCB        

  es mov word[di+M_LAST],bx    ; point next block to new block
  mov word[di],bx              ; M_NEXT, point this block to new block
  sub word[di+M_PARA],ax       ; resize this block
  push ds
  mov ds,bx                    ; point es to new block
  pop bx

  mov word[di+M_LAST],bx       ; initialise new block's M_LAST
  mov word[di+M_PARA],ax       ; initialise new block's M_PARA
  mov word[di],es              ; initialise new block's M_NEXT

N_EXACT:
  mov byte[di+M_FLAG],F_FREE   ; mark new block as no longer free
  mov word[di+M_NPRO],di
  mov word[di+M_LPRO],di
N_ALEXIT:
  jmp short E_ENABLE

Setup

Simply sets up the timer interrupt.

E_INT1C:
  call E_SWITCHER
  db 0EAh
D_OLDINT1C:
  dw 0,0

; ---------------------------------------------------------------------------

E_INIT:
  push cs
  pop es
  xor ax,ax
  mov ds,ax
  mov si,01Ch*4
  mov di,D_OLDINT1C
  cld
  push si
  movsw
  movsw
  pop di
  cli
  push ds
  pop es
  mov ax,050h
  stosw
  mov ax,E_INT1C
  stosw
  sti
; ...