Trabalho 3: Escalonador de Tarefas Preemptivo

Avisos

Introdução

No terceiro trabalho da disciplina, você deve continuar com a distinção entre código de usuário e código de sistema introduzido no Lab07. Contudo, dessa vez, o código de usuário será fornecido. A tarefa que você deve realizar neste trabalho é desenvolver uma implementação de um escalonador de tarefas, ou seja, a parte do sistema operacional responsável por alternar entre os processos/programas que estão executando a cada momento na cpu do computador. Para isto, você deverá implementar as seguintes syscalls: write(), fork(), getpid() e exit().

Atendendo syscalls

No laboratório anterior você implementou um pequeno programa em linguagem de montagem ARM para atender às interrupções de hardware do tipo IRQ. Nesse laboratório, você deve expandir a implementação anterior para atender interrupções de software do tipo SVC (syscalls). No laboratório anterior você também configurou os dispositivos GPT e TZIC. Nesse, você deverá expandir seu código para configurar o dispositivo de saída serial, UART. Essas alterações vão permitir que você execute o código de usuário que será fornecido.

Tratamento de interrupções de software

Na convenção mais recente ARM EABI, para realizar uma chamada ao sistema, você deve colocar o número da chamada de sistema no registrador R7, e os parâmetros seguem a mesma convenção de uma chamada de função comum (devem estar nos registradores R0 a R3). O valor de retorno é passado no registrador R0. Para realizar a chamada de sistema, o código de usuário utiliza a instrução svc 0. Esta instrução irá gerar uma exceção e fazer com que o registrador PC (apontador para a instrução a ser executada) aponte para a posição 0x00000008 e troque o modo do processador para SUPERVISOR. A implementação de uma chamada de sistema, portanto, é similar à implementação de interrupções do laboratório anterior.

No entanto, você recebe em R7 um número correspondendo ao número da syscall. O seu tratador de chamadas de sistema deve, portanto, analisar o valor contido nesse registrador e selecionar a rotina de tratamento adequada (write, exit, fork e getpid). Lembre-se que, para retornar do tratador de chamadas de sistema para o código do usuário que chamou a syscall, você deve utilizar uma instrução especial como movs pc, lr para recuperar o registrador CPSR original, modificando o modo do processador. Mais detalhes sobre a troca de modos e o serviço de interrupções e syscalls no processador ARM estão disponíveis nos textos dos enunciados dos laboratórios anteriores.

syscall write

Não é necessário que seu sistema administre arquivos e descritores de arquivos. Portanto, ignore o primeiro parâmetro da chamada de sistema write, que diz respeito ao número do descritor de arquivo. Ou seja, independente do valor do descritor de arquivo, a chamada de sistema write deve escrever os bytes no dispositivo UART. Esta é uma pequena simplificação que deve ser adotada no seu sistema em relação ao um sistema operacional POSIX real.

Escreva R2 bytes do buffer cujo ponteiro está em R1. Retorne o número de bytes escritos com sucesso (0 indica que nenhum byte foi escrito) ou -1 caso tenha ocorrido algum erro. A seção Transmissão de dados pela UART a seguir, explica como enviar os bytes para o dispositivo UART.

UART

Configuração

A UART possui um datasheet intimidador de mais de 70 páginas. Não se preocupe, você só irá utilizar o datasheet para consultar os endereços na memória de cada registrador da UART. Quando for fazer isso, lembre-se que a plataforma iMX (da placa que está conectada na rede do IC e que o simulador também reproduz fielmente) possui 4 UARTs. Pegue o endereço da primeira UART, indicada no datasheet como UART1. Sabendo traduzir os endereços dos registradores, para ligar a UART, veja um exemplo de código de inicialização seguindo os passos da seção 75.5.1 do datasheet. Contudo, não realize o oitavo passo, pois não utilizaremos interrupções para comunicação com a UART.

Transmissão de dados pela UART

Nessa seção será explicado como transferir dados por polling, isto é, sem utilizar interrupções.

Verifique se o bit TRDY (transmitter ready), isto é, o bit 13 do registrador UART STATUS REGISTER 1 (UART1_USR1), está definido como 1. Caso positivo, isto indica que a ocupação da fila de transmissão (TX_FIFO) está abaixo de um nível de segurança pré-configurado (lembre-se que você configurou a UART seguindo os passos do datasheet), ou seja, você pode escrever um byte para transmissão sem correr o risco de perder o dado por fila cheia. Essa fila possui 32 posições e armazena os caracteres que estão pendentes para serem enviados. Quando um byte é transmitido, um caractere é removido da fila.

Para escrever um caractere na fila TX_FIFO e escaloná-lo para ser transmitido, basta realizar uma escrita no registrador UART1_UTXD. Ao escrever neste registrador, o dado vai para a fila TX_FIFO. Caso a ocupação da fila fique acima de um determinado nível, correndo o risco de ficar cheia, o bit TRDY é automaticamente desligado (vai para 0).

Portanto, uma forma de realizar escrita pela UART é implementar um laço que escreve byte por byte, realizando sucessivas escritas em UART1_UTXD sempre que a flag TRDY estiver avisando que o dispositivo pode receber mais um byte. A condição de parada do laço será se o número de bytes escritos já alcançou o número solicitado pelo usuário da chamada de sistema syswrite.

Processos

A chamada de sistema fork

FORK(2)                             Linux Programmer's Manual                            FORK(2)

NAME
	fork - create a child process

SYNOPSIS
	#include <unistd.h>

	pid_t fork(void);

DESCRIPTION
	fork()  creates  a  new  process  by  duplicating  the calling process.  The new process,
	referred to as the child, is an exact duplicate of the calling process,  referred  to  as
	the parent, except for the following points:

	*  The  child  has  its  own unique process ID, and this PID does not match the ID of any
	   existing process group (setpgid(2)).

(...)

RETURN VALUE
	On  success, the PID of the child process is returned in the parent, and 0 is returned in
	the child.  On failure, -1 is returned in the parent, no child process  is  created,  and
	errno is set appropriately.

(...)

O seu sistema operacional será similar a um sistema operacional verdadeiro, pois contará com a capacidade de rodar mais de um programa de usuário (ou processo) ao mesmo tempo. Este tipo de sistema operacional é chamado de sistema multi-tarefa. Em sistemas POSIX, a maneira de inserir novos processos no sistema operacional é através da chamada de sistema fork. Abaixo, um diagrama ilustra como um programa pode usá-la:

As barras pretas representam o fluxo de código executado no processador. Repare, entretanto, que a partir da chamada para fork, temos 2 processos rodando ao mesmo tempo no processador. Na prática, isso não acontece, a não ser que o sistema tenha múltiplos núcleos ou múltiplos processadores. Um dos métodos de implementar um sistema multi-tarefa é criando um escalonador preemptivo (se quiser saber mais, verifique este artigo ). O escalonador baseado em preempção pode ser implementado em sistemas que dispõem de interrupções por timer, a mesma utilizada no laboratório 7.

Neste trabalho, para todos os efeitos, o PID, ou process ID, é um inteiro de 32 bits que seu sistema deve utilizar para identificar um processo.

Após o sistema ser inicializado, ou seja, após tratar a interrupção reset, o sistema deverá fazer um salto para o endereço 0x8000 para que o programa do usuário comece a executar. O programa de usuário (fornecido) chamará diversas vezes a syscall fork para se replicar e nesses pontos o seu sistema deve interromper a execução do programa e fazer o tratamento de forma apropriada.

Preempção

O comportamento esperado de um escalonador baseado em preempção é o de tomar o controle do processador (daí vem o termo preempção) forçadamente por uma interrupção de um temporizador em hardware, como o GPT. Assim, o programa usuário pode ser feito como se fosse o único programa rodando no sistema operacional. Após passado um tempo executando no processador, é hora de rodar outro processo. A interrupção acontece e o tratador de interrupções chama o escalonador. Ao invés de voltar a execução para o processo interrompido, outro processo é colocado para ser executado no lugar. Desse modo, cada processo executa por um período de tempo predeterminado pelo temporizador. Este período de tempo é chamado de time slice do sistema operacional.

A política usada para escolher qual o próximo processo que será executado é chamada de round robin caso você alterne dando igual prioridade para cada processo. É esta a política que você deverá implementar no trabalho.

Suponha que o seu sistema possua 3 processos ativos no sistema, ou seja, 3 programas de usuário diferentes (ex: via fork()) para executar, a situação mostrada na figura abaixo ilustra o funcionamento do round robin:

Processos atualmente no sistema:
PID 1 (running) PID 2 (ready) PID 3 (ready)


Ordem de escalonamento dos processos:



O seu sistema deve comportar no máximo 8 processos. Se uma chamada de sistema fork for realizada e o sistema já está na capacidade máxima, com 8 processos, um erro deverá ser retornado.

Troca de contexto

Lembre-se que você precisa guardar o contexto de execução de cada processo. Para isso, crie um vetor com 8 posições. Cada contexto é composto pelos registradores, salvos no momento em que o processo foi interrompido pelo escalonador preemptivo, incluindo o CPSR.

Registradores do PID 1 Registradores do PID 2 Registradores do PID 3 ... Registradores do PID 8

Este vetor de contextos deve guardar um snapshot, ou "fotografia" de como estavam os registradores de um processo quando ele foi interrompido pela última vez. Dessa forma, quando o processo for escolhido para ser executado em um futuro próximo, todos os seus registradores (contexto) estarão intactos e serão restaurados, como se o programa nunca tivesse sido interrompido. A grande vantagem do escalonador preemptivo é justamente ser transparente ao programa - o programa de usuário não precisa saber que não está rodando no processador 100% do tempo.

Na inicialização, seu sistema também deve pré-alocar 8 pilhas em posições distintas. Cada novo processo recebe uma pilha diferente. Lembre-se de que pilha cresce para baixo. Uma sugestão para os endereços é dada abaixo:

EndereçoDescrição
0x11000Início da pilha do PID 1
0x10800Início da pilha do modo supervisor de PID 1
0x10000Início da pilha do PID 2
0x0F800Início da pilha do modo supervisor de PID 2
0x0F000Início da pilha do PID 3
0x0E800Início da pilha do modo supervisor de PID 3
0x0E000Início da pilha do PID 4
0x0D800Início da pilha do modo supervisor de PID 4
0x0D000Início da pilha do PID 5
0x0C800Início da pilha do modo supervisor de PID 5
0x0C000Início da pilha do PID 6
0x0B800Início da pilha do modo supervisor de PID 6
0x0B000Início da pilha do PID 7
0x0A800Início da pilha do modo supervisor de PID 7
0x0A000Início da pilha do PID 8
0x09800Início da pilha do modo supervisor de PID 8
0x07C00Início da pilha do modo UND.
0x07800Início da pilha do modo ABT.
0x07400Início da pilha do modo FIQ.
0x07000Início da pilha do modo IRQ.

Utilize o modelo abaixo como referência para inicializar a pilha de execução de cada programa.

@ Configurable STACK values for each ARM core operation mode
.set USR_STACK, 0x11000
.set SVC_STACK, 0x10800
.set UND_STACK, 0x07c00
.set ABT_STACK, 0x07800
.set FIQ_STACK, 0x07400
.set IRQ_STACK, 0x07000

@ First configure stacks for all modes
mov sp, #SVC_STACK 
msr CPSR_c, #0xDF	@ Enter system mode, FIQ/IRQ disabled
mov sp, #USR_STACK
msr CPSR_c, #0xD1	@ Enter FIQ mode, FIQ/IRQ disabled
mov sp, #FIQ_STACK
msr CPSR_c, #0xD2	@ Enter IRQ mode, FIQ/IRQ disabled
mov sp, #IRQ_STACK
msr CPSR_c, #0xD7	@ Enter abort mode, FIQ/IRQ disabled
mov sp, #ABT_STACK
msr CPSR_c, #0xDB	@ Enter undefined mode, FIQ/IRQ disabled
mov sp, #UND_STACK
msr CPSR_c, #0x1F	@ Enter system mode, IRQ/FIQ enabled

Algoritmo de recuperação de contexto

Repare que a troca de contexto pode interromper a realização de uma syscall de um processo (por exemplo, processo X). Então, a pilha de supervisor de X não pode interferir na realização de uma syscall por parte de outro processo (por exemplo, processo Y). Se todos os processos compartilhassem a mesma pilha de supervisor, uma intercalação de X para Y e em seguida para X novamente, sempre interrompendo um processo no meio de uma syscall, poderia arruinar o estado correto para a execução da syscall de X, pois Y provavelmente deixaria a pilha supervisor em um estado desconhecido para X. Assim, cada processo tem uma pilha de usuário e uma pilha de modo supervisor.

Para recuperar o contexto completamente, seu código deve entrar em modo SYSTEM (o modo SYSTEM é utilizado para acessar os registradores de usuário sem perder privilégios para uma troca de modo futura) e recuperar os registradores de usuário, inclusive a pilha de modo usuário. Em seguida, o seu algoritmo para recuperação de contexto deve entrar em modo SUPERVISOR e reescrever o registrador de pilha desse modo com a pilha supervisor particular desse processo. Por último, você deve recuperar o CPSR e o PC, que determinarão os dois últimos fatores cruciais para uma completa recuperação do contexto: Onde o código estava executando da última vez antes de ser interrompido, e o modo em que estava no CPSR (supervisor ou usuário).

Dicas

Não há muito código neste trabalho com as syscalls fork() e derivadas. Grande parte do trabalho consiste em pensar sobre todos os casos em que você pode ser interrompido e não irá conseguir recuperar corretamente o contexto, e cuidar para que o código fique correto mesmo nesses casos. Você pode, por exemplo, definir regiões críticas em que se desabilitam interrupções temporariamente. Um exemplo disso deve ocorrer na syscall write, em que enquanto você está escrevendo o texto de um processo, você não deseja que ele seja interrompido e outro processo comece a escrever no lugar. Por isso, você pode achar desejável desabilitar interrupções no laço de escrita da UART.

Outro ponto importante no trabalho é o conceito de reentrância. Você deve prestar atenção para o uso de variáveis globais no código de sistema, porque o seu código deve funcionar mesmo quando for interrompido e outro processo chamar a mesma função (entrar novamente na função). Repare que se você utiliza variáveis globais sem proteger o acesso com travas, você pode estar no meio da atualização de uma estrutura complexa e ser interrompido - e em seguida outro processo chama a mesma função, que irá encontrar essa estrutura global em um estado inconsistente e poderá falhar.

Algoritmo do escalonador

Perceba que no momento em que a chamada à fork é realizada, o novo processo possui exatamente o mesmo contexto do processo pai (que realizou a chamada). A única diferença é que quando o novo processo for executar, o valor de retorno da syscall fork será 0, enquanto quando o processo velho for escalonado para execução, o valor de retorno da syscall fork será o número do processo filho criado (o PID do novo processo).

O PID dos processos do seu sistema pode assumir os valores de 1 a 8. Assuma que o primeiro processo possui o PID 1, e o contexto inicial da execução dele é a chamada para main().

Demais chamadas de sistema que devem ser implementadas

getpid

GETPID(2)                           Linux Programmer's Manual                          GETPID(2)

NAME
	getpid - get process identification

SYNOPSIS
	#include <sys/types.h>
	#include <unistd.h>

	pid_t getpid(void);
DESCRIPTION
	getpid()  returns the process ID of the calling process.  (This is often used by routines
	that generate unique temporary filenames.)

ERRORS
	This function is always successful.

CONFORMING TO
	POSIX.1-2001, 4.3BSD, SVr4.

A syscall getpid() simplesmente retorna a identificação do processo (process ID) do processo que a chamar. Para responder a essa chamada, basta consultar seu escalonador para conhecer qual o número do processo em execução atualmente. Repare que, no trabalho, esse número só pode assumir os valores de 1 a 8.

exit

_EXIT(2)                            Linux Programmer's Manual                           _EXIT(2)

NAME
	_exit, _Exit - terminate the calling process

SYNOPSIS
	#include  <unistd.h>

	void _exit(int status);

DESCRIPTION
	The  function  _exit()  terminates  the  calling  process  "immediately".   Any open file
	descriptors belonging to the process are closed; any children of the process  are  inher‐
	ited by process 1, init, and the process's parent is sent a SIGCHLD signal.

	The  value status is returned to the parent process as the process's exit status, and can
	be collected using one of the wait(2) family of calls.

RETURN VALUE
	These functions do not return.

CONFORMING TO
	SVr4, POSIX.1-2001, 4.3BSD.  The function _Exit() was introduced by C99.

A última syscall a ser implementada, exit(), simplesmente encerra a execução do processo que a chamou e libera o seu número de PID para ser usado por um novo processo criado por fork().

Executando o Sistema

O único modo de testar o código supervisor (de sistema) é utilizando o simulador. Você deve especificar o código de sistema a carregar com o parâmetro --load-sys= e especificar o código de usuário com o parâmetro --load=.

O código de sistema deve ser ligado com a opção --Ttext=0 para que o código seja montado a partir do endereço 0x00000000. Se você não especificar esta opção, o ligador irá colocar seu código no endereço 0x00008000 e, dessa forma, seu sistema não irá executar, pois o processador, assim que ligado, começa sempre a executar a instrução que está no endereço 0x00000000.

Seu escalonador preemptivo deve ser capaz de executar o código de usuário fornecido aqui. Para utilizar a parte de sistema fornecida, descomprima e realoque o arquivo da seguinte maneira:

# descomprimir
unzip trab3-user.zip

# realocar no endereco 0x8000
arm-elf-ld -Ttext=0x8000 usuario.o -o usuario

Para executar no simulador execute o seguinte comando:

arm-sim --load-sys=myos --load=usuario