Atividade-desafio 2

Micro-Kernel de Tempo Real

Atenção: esta atividade é opcional, estritamente individual, e substitui a prova. Deve ser entregue até o dia da prova

O objetivo desta atividade é implementar um Micro-Kernel de Tempo Real para o 8086.

Sistemas embarcados usualmente possuem um micro-kernel que controla as tarefas concorrentes do sistema. O micro-kernel faz o papel de um sistema operacional muito simples: cria e escalona tarefas (processos), provê mecanismos de sinalização entre tarefas, etc. Quando o micro-kernel responde a eventos com rapidez ele se diz de tempo real.
Se o escalonamento das tarefas é feito através de um relógio de tempo real (hardware que interrompe o processador a intervalos de tempo regulares) o micro-kernel se diz preemptivo (pois pode interromper uma tarefa a qualquer instante e passar o controle da CPU para outra tarefa). Caso contrário ele é dito não-preemptivo e uma tarefa em execução libera o uso do processador através de uma função especial do sistema (t_yield).
O escalonamento de tarefas pode usar prioridades ou ser bastante simples como o escalonamento circular (em inglês round-robin), que ciclicamente dá o controle da CPU a cada tarefa em condições de executar. Será o caso desse projeto. Se as tarefas compartilham o mesmo espaço de endereçamento elas são também chamadas de threads ou processos leves. Nesse caso elas têm acesso aos mesmos dados e conflitos no seu acesso podem aparecer, requerendo técnicas de exclusão mútua entre tarefas para acesso a dados compartilhados (também ditas de implementação de Regiões Críticas). Este é o caso, por exemplo, das funções int 21h do DOS, que não podem ser usadas simultâneamente por duas tarefas.

Tarefas de sistemas embarcados usualmente nunca terminam; ficam num laço à espera de um evento sobre o qual devem atuar. No nosso caso vamos permitir o término de uma tarefa.
Uma thread no nosso caso é simplesmente uma rotina que possui sua própria pilha (e que pode chamar outras rotinas).

V. deve programar uma biblioteca de rotinas que permitam implementar threads num sistema com escalonamento não-preemptivo (infelizmente a máquina virtual que emula o DOS no Windows não permite o controle de interrupções, necessário à implementação de escalonamento preemptivo, que é muito mais poderoso do ponto de vista prático e mais interessante também).

No sistema que V.vai implementar haverá um número máximo prefixado de threads, NT, (é conveniente que seja uma potência de 2, pois facilita o cálculo de índices), e espaço em memória para controle das threads será pre-alocado para esse número.
Uma thread será identificada por um índice (tid) >=0 e < NT.
Apenas duas tabelas e algumas variáveis auxiliares serão necessárias para implementar a biblioteca:

• tcb - task control block: esta tabela contém NT registros, um para cada possível thread. Cada registro contém os seguintes campos:
  1. Status: estado da thread: um dentre FREE=0, READY=1, SLEEP=2, ENDED=3
     FREE significa que nenhuma thread está associada ao registro
     READY significa que a thread está pronta para executar
     SLEEP significa que a thread está bloqueada durante n ticks do relógio do sistema
     ENDED significa que a thread terminou mas ainda não foi liberada (pela função t_join, a ser vista)
  2. topo_pilha: apontador para o topo da pilha da thread
  3. timer_low: parte baixa do temporizador de 32 bits, caso a thread esteja bloqueada.
  4. timer_high: parte alta do temporizador de 32 bits, caso a thread esteja bloqueada
  
  Mais uma vez, é conveniente que o tamanho do registro seja uma potência de 2: se cada item acima ocupar uma palavra o registro terá 8 bytes. O 2º byte está livre e poderia ser usado, por exemplo, para colocar a prioridade da thread;

• st - tabela de pilhas, uma para cada thread. Cada pilha conterá STSIZE bytes, um parâmetro do sistema..

As seguintes funções básicas fazem parte da bibioteca:

• t-init: inicializa o sistema, por exemplo criando a thread ociosa, t-idle, para gastar o tempo da CPU quando não há nenhuma thread pronta para executar;

• t-create: cria uma nova thread;
  parâmetro de entrada: endereço da rotina inicial da thread.
  parâmetro de saida: identificador da thread

• t_yield: libera a CPU para outra thread, escalonando de forma circular a próxima thread no estado READY.

• t-exit: termina a thread corrente (em execução) passando-a para o estado ENDED.
  nenhum parâmetro de entrada ou saída.

• t-join: espera pelo término de uma dada thread; quando ocorrer passa o seu estado para FREE, liberando assim o registro do tcb.
  parâmetro de entrada: identificador da thread a esperar pelo término.

• t-sleep: passa a thread em execução para o estado SLEEP (bloqueada) por n ticks do relógio; se n=0 re-escalona a thread (chama t-yield).
  parâmetro de entrada: número de ticks do relógio durante os quais a thread ficará bloqueada.

• t-lock: bloqueia o semáforo passado como parâmetro. Caso já esteja bloqueado chama t_yield e tenta novamente.
  parâmetro de entrada: índice do semáforo.

• t_unlock: desbloqueia o semáforo passado como parâmetro.

Devido ao fato de o sistema ser não preemptivo, V. poderá depurá-lo com o turbo-debugger. É relativamente simples tranformá-lo num micro-kernel preemptivo: a função t_yield passaria a ser a rotina de interrupção do relógio de tempo real!. As outras funções da biblioteca não teriam alteração alguma, (exceto t_create) mas elas devem executar com interrupções desablitadas por razões óbvias (este é o problema básico da máquina virtual DOS que o Windows 2000/NT fornece: não é possivel desabilitar interrupções). As instruções cli e sti são inóquas e V. não deve usá-las, pois cli por alguma razão misteriosa atrasa a saída de mensagens enviadas via int 21h. V. poderia fazer o micro-kernel numa máquina com o velho sistema DOS, ou talvez num Windows mais antigo.
Descobri, no entanto, um truque (sujo) para implemetar um micro-kernel preemptivo no ambiente Windows NT/2000. De qualquer forma é importante implementar primeiro o micro-kernel não preemptivo, pois V. poderá depurá-lo com o turbo debugger ao contrário do preemptivo, especialmente as funções t_create e t_yield que são as mais críticas.
Se V. chegar ao final desta atividade darei a dica de como transformar o seu micro-kernel num micro-kernel preemptivo com pouquíssimas mudanças!
A título de ilustração, abaixo transcrevo algumas funções do nosso micro-kernel preemptivo.

   Org 100h
   ;aqui definição das constantes básicas acima mencionadas
   
   call init       ; create idle task and start RTClock
   call debug      ; send a numbered message to video
   mov ax,[ct]     ; ct is incremented at each interrupt (my debug help)
here:              ; check if RTC interrupt is enabled
    call t_yield   ; let idle task run
    cmp ax, [ct]
    jz here
   call debug      ; interrupt is working,for  we came out of the loop
   mov dx,task1
   call t_create   ; creates 1st task
   mov [tid],di    ; save tid of task created
   mov dx, task2   ; creates 2nd task
   call t_create
   mov [tid+2], di ; save tid of new task
   mov si, [tid]
   call t_join     ; waits for task1 to end
   call debug
   mov si, [tid+2]
   call t_join     ; and now waits for task2
end0:
   call debug
end:
    call restint        ; restore original 1ch interrupt vector
    mov ah, 4ch         ; back to DOS!
    int 21h
;________________________________________________________________
debug:
    inc byte[msg]       ; trick to number a standard message
    mov dx, msg
    call prtmsg			; prints message proteced by semaphore
    ret
;_____________________________________________________
task1:			         ; my first task									  		
    mov ax,4
my0:
    push ax
    mov dx,task1msg
    call prtmsg
    mov cx,18
    call t_sleep
    pop ax
    dec ax
    jnz my0
    call t_exit	 ; finish task
    jmp $        ; should never come here!
;__________________________________________________________________

task2:				    ; second task											   
    mov cx,18
    call t_sleep        ; sleep for 1 second
    mov dx, task2msg
    call prtmsg         ;show message protected by semaphore
    call t_exit         ; finish this task
    jmp $               ; should never come here
;********************************************************************
prtmsg:                 ; show message via DOS int 21h, protected by semaphore 0
                        ; input: dx= message address
    mov ax,1
    lock xchg ax, [sem] ; check semaphore: 1 = locked
    or ax,ax
    jz free
    call t_yield        ; semaphore locked, try again later
    jmp prtmsg
free:                   ; now we hold the semaphore
    mov ah,09           ; send message to video
    int 21h
    mov word[sem],0     ; unlock semaphore
    ret
;***********************************************************************

t_idle:                 ; idle task
    call t_yield        ; do nothing but allow others to run!
    jmp t_idle

;***********************************************************************
t_lock:              ; locks semaphore 
                     ; input bx = semaphore to lock
                     ; output: none
lock0:
    mov  ax, 1       ; 1: locks semaphore, 0: semaphore is unlocked
    lock xchg ax, [sem+bx] ; individible: locks bus in a multiprocessor system
    or ax, ax        ; if ax is 0
    jz lock1         ; then semaphore was uncloked
    call t_yield     ; else was locked by other task, release processor
    jmp lock0        ; and try again
lock1:
    ret
;*********************************************************************
t_unlock:               ; unlock semaphore bx
    mov word[sem+bx],0
    ret

;*********************************************************************