====== Preempção e compartilhamento de tempo ======
Este projeto faz parte do [[PPOS-v2:start|PPOS v2]].
Até agora, nosso sistema suporta apenas tarefas **cooperativas**, que precisam informar ao despachante quando não precisam mais da CPU, usando a chamada ''task_yield''. O objetivo deste projeto é adicionar preempção por tempo ao sistema. Com essa modificação, nosso sistema passará a suportar tarefas **preemptivas**, que podem se alternar no uso do processador sem a necessidade de solicitar trocas ao despachante.
===== Preempção =====
Em sistemas de tempo compartilhado (//time-sharing//), cada tarefa de usuário recebe uma pequena fatia de tempo de processador, denominada //quantum//. Valores típicos de quantum estão entre 1 ms e 100 ms. Ao acabar seu quantum, o despachante é ativado, a tarefa em execução retorna à fila de prontas e cede lugar à próxima tarefa da fila de prontas.
Em um sistema real, a implementação da preempção por tempo tem como base as interrupções geradas pelo temporizador programável do hardware. Esse temporizador é programado para gerar uma interrupção a cada 1 milissegundo, que é tratada por um //interrupt handler// (tratador de interrupção) ou ISR (//Interrupt Service Routine//); essas ativações periódicas do tratador de interrupção são normalmente chamadas de //ticks// do relógio.
Quando uma tarefa recebe o processador, o //dispatcher// ajusta um contador de //ticks// que essa tarefa pode usar, ou seja, seu quantum definido em número de //ticks//. A cada //tick//, esse contador deve ser decrementado; quando ele chegar a zero, o processador deve ser devolvido ao //dispatcher// e a tarefa volta à fila de prontas. A figura a seguir ilustra esse conceito:
{{ so:time-sharing.png |Compartilhamento de tempo}}
===== Emulação do temporizador =====
Como um processo UNIX não tem permissão de acesso aos temporizadores e interrupções do hardware, em nosso projeto eles são emulados através de temporizadores e sinais UNIX. Isso é feito através das seguintes funções, definidas no arquivo ''hardware/cpu.h'' do projeto:
* ''hw_timer(first, next)'' : arma um temporizador para disparar após ''first'' milissegundos e depois a cada ''next'' milissegundos. Quando o temporizador dispara, ele gera uma interrupção virtual (//irq//) definida pela constante/macro ''IRQ_TIMER''.
* ''hw_irq_handle(irq, handle)'' : registra a função ''handle'' para ser ativada sempre que ocorrer a interrupção ''irq''.
===== Implementação =====
O mecanismo a ser implementado pode ser resumido nos seguintes passos:
- Durante a inicialização do sistema (na função ''kernel/time.c:time_init''), um temporizador deve ser programado para disparar a cada 1 milissegundo (1 //tick//);
- Os disparos desse temporizador devem ser tratados por uma rotina de tratamento de //ticks//, a ser definida em ''kernel/time.c'';
- Ao ganhar o processador, cada tarefa recebe um quantum de 10 //ticks// de relógio (experimente com diferentes tamanhos de //quantum// para ver seu efeito);
- Ao ser acionada, a rotina de tratamento de //ticks// de relógio deve decrementar o contador de //quantum// da tarefa corrente, se for uma tarefa de usuário;
- Se o contador de quantum chegar a zero, a tarefa em execução deve voltar à fila de prontas e o controle do processador deve voltar ao //dispatcher//.
Sua implementação deve funcionar com o código de teste ''test/pingpong-preempcao.c'' e deve gerar um resultado similar ao presente no arquivo ''pingpong-preempcao.txt''.
A rotina de tratamento de //ticks// de relógio é **crítica**, pois vai ser executada com muita frequência (1000× por segundo). Essa rotina deve ser pequena e rápida, para não prejudicar o desempenho do sistema e garantir sua estabilidade.
===== Arquivos =====
Os seguintes arquivos são relevantes para este projeto:
* ''hardware/cpu.h'' : interface da emulação de hardware (interrupções e timer) **não alterar**
* ''kernel/time.c'': implementação da gestão de tempo
* ''kernel/tcb.c'': define a estrutura do task control block
* ''kernel/dispatcher.c'': implementação do escalonador
* ''test/pingpong-preempcao.c'': código de teste
* ''test/pingpong-preempcao.txt'': saída esperada do teste (pequenos desvios são aceitáveis)
===== Condições de disputa =====
É importante evitar preempções dentro do //dispatcher// ou de funções do nosso sistema, pois estas podem ter resultados imprevisíveis, como **condições de disputa** e instabilidade. Pode-se controlar a ocorrência de preempções de várias formas. Uma forma básica de implementar esse controle usa o conceito de **tarefa de sistema**:
* Tarefas críticas como o //dispatcher// são consideradas **tarefas de sistema**, pois sua execução correta é fundamental para o bom funcionamento do sistema; sua preempção deve ser evitada.
* As demais tarefas (//Main//, //Pang//, ...//Pung//) são consideradas **tarefas de usuário**, pois executam código definido pelo usuário do sistema, e podem ser "preemptadas" quando necessário.
* O tratador do temporizador deve sempre verificar se a tarefa corrente é de usuário ou de sistema, antes de preemptá-la devido ao fim de um //quantum//. Pode ser adicionado um //flag// na estrutura de controle de cada tarefa para indicar se ela é uma tarefa de sistema ou de usuário.
Uma solução mais "radical" para esse problema consiste em impedir completamente as preempções enquanto a execução estiver dentro das funções do núcleo. Uma forma simples de obter isso consiste em definir um //flag// global que seja ''TRUE'' quando uma tarefa de usuário estiver executando seu próprio código e ''FALSE'' quando a execução estiver dentro de uma função do sistema (''task_create'', ''task_switch'', etc). Esse //flag// deve ser testado pela rotina de tratamento de //ticks// de relógio e precisa ser ligado/desligado explicitamente em cada função.
Versões mais antigas do núcleo Linux possuíam uma trava global chamada //[[https://www.halolinux.us/kernel-architecture/the-big-kernel-lock.html|The Big Kernel Lock]]// para fazer esse controle.
===== Sinais e Temporizadores UNIX =====
Para a emulação de interrupções e temporizadores de hardware, o PPOS usa sinais e temporizadores UNIX/POSIX. O mecanismo de sinais do UNIX é similar às interrupções (IRQs) geradas pelo hardware: ao receber um sinal, um processo desvia sua execução para uma função que ele previamente registrou no sistema operacional.
A página de manual ''{{so:signal.txt|signal}}'' (seção 7) relaciona os principais sinais disponíveis em um sistema UNIX e as ações que cada sinal pode desencadear no processo que o recebe. Através da chamada de sistema ''sigaction'' é possível registrar uma função de tratamento para um determinado sinal (//signal handler function//).
Um exemplo do uso de sinais está no arquivo ''{{so:signal.c}}''. Nele, uma função é registrada para tratar o sinal ''SIGINT'', que corresponde ao //Control-C// do teclado. Analise atentamente seu código, execute-o e observe seu comportamento.
Para simular as interrupções de relógio do hardware, é usado o do mecanismo de sinais (para implementar a preempção) e de temporizadores UNIX (para gerar os //ticks// de relógio). O UNIX permite definir temporizadores através das chamadas de sistema ''getitimer'' e ''setitimer''. Ao disparar, um temporizador gera um sinal para o processo, que pode ser capturado por uma função tratadora previamente registrada por ele. O arquivo ''{{so:timer.c|timer.c}}'' apresenta um exemplo de uso do temporizador.
===== GDB e sinais =====
Por default, o depurador GDB interrompe a depuração a cada sinal recebido pelo processo, o que torna inviável usá-lo para depurar nosso projeto, pois ele recebe 1.000 sinais por segundo do temporizador virtual. Para resolver esse problema, basta configurar o GDB para ignorar os sinais UNIX gerados pelo hardware virtual, incluindo o conteúdo abaixo no arquivo ''$HOME/.gdbinit'':
handle SIG34 nostop noprint
handle SIG35 nostop noprint
handle SIG36 nostop noprint
handle SIG37 nostop noprint
===== Outras informações =====
* Duração estimada: 4 horas.
* Dependências:
* [[Tarefas cooperativas]]
* [[Despachante de tarefas]]