No segundo trabalho da disciplina, você deve continuar com a distinção entre código de usuário e código de sistema. Contudo, dessa vez, o código de usuário será fornecido. Para que o programa fornecido funcione no seu sistema, você deve ter implementado as syscalls: write(), fork(), getpid() e exit(). A syscall write() é a mesma do trabalho anterior.

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.

(...)

PID, ou process ID, é um inteiro de 32 bits que seu sistema deve utilizar para identificar um processo. A partir de agora, o seu sistema operacional ficará mais próximo de 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 8.

Suponha que o seu sistema possua 3 processos ativos no sistema, ou seja, 3 programas de usuário diferentes para executar:

PID 1 (running)

PID 2 (ready)

PID 3 (ready)

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.

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 processor 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. A atribuição de endereços a ser adotada é:

Endereço de memória	Descrição
0001 1000	Início da pilha do PID 1
0001 0800	Início da pilha do modo supervisor de PID 1
0001 0000	Início da pilha do PID 2
0000 F800	Início da pilha do modo supervisor de PID 2
0000 F000	Início da pilha do PID 3
0000 E800	Início da pilha do modo supervisor de PID 3
...
0000 A000	Início da pilha do PID 8
0000 9800	Início da pilha do modo supervisor de PID 8

Observação: note que as posições iniciais das pilhas foram alteradas. Isto ocorreu porque a pilha do modo supervisor do processo de PID 8 estava muito próxima do endereço de inicio do código de usuário(0x8000).

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

• Não é necessário implementar o escalonador com uma fila (estrutura de dados).
• Você poderá usar exclusivamente vetores: o vetor de contextos e um vetor para indicar quais PIDs estão vivos (devem ser escalonados em algum momento).

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

Código de usuário fornecido

Seu escalonador preemptivo deve ser capaz de executar o código de usuário fornecido aqui. Descomprima o código utilizando o comando:

	tar -xjvf trab2-codigousuario.tar.bz2

Você deve ligar o código de usuário separado do código de sistema como no último laboratório. Exemplo:

	arm-elf-ld -g user.o -o user

Desafio

Implementar as syscalls write() e read() por interrupção. Essas syscall marcam o processo como bloqueado e permitem o escalonamento de outro processo para ser executado no lugar até a interrupção informando que o periférico está pronto (S.O. que esconde latências de I/O).

Submissão

O trabalho poderá ser feito individualmente ou em duplas. Para realizar a entrega, você deverá utilizar a SuSy ( http://susy2.ic.unicamp.br:9999/mc404ab/24). Uma tarefa especial para a entrega do trabalho será aberta e você deverá entregar todos os arquivos do código de montagem em um arquivo compactado (.zip, .tar.gz ou .tar.bz2). Note que a SuSy não verifica o seu trabalho durante a submissão. Você deve testá-lo nos laboratórios do IC-3 utilizando a infraestrutura disponibilizada para a disciplina.