Sistemas de Computação 8 - Compartilhamento do tempo do processador

Muy bueno... pelo que vimos até agora existem alguns mistérios entre as coisas feitas pelo kernel do sistema operacional, e neste post vamos resolver um deles. Se, pelo que vimos da arquitetura Von Neumann e do ciclo fetch-execute, o processador só é capaz de executar um programa de cada vez (com a exceção óbvia das máquinas multiprocessadas e dos processadores com múltiplos núcleos) então como o sistema operacional consegue criar a ilusão de execução simultânea de vários programas?

A resposta é simples. Intercalando no tempo a execução dos vários programas do(s) usuário(s), e fazendo isto tão rápido que, para o observador humano, a aparência é de execução simultânea. Esta técnica é chamada de multitasking (multiprogramação), e o algoritmo mais popular para realizá-la é o time-sharing. Mas este algritmo necessita que o hardware (e/ou o microcódigo) implemente o mecanismo de interrupções (interrupts). Portanto vamos primeiro falar disso.

Interrupções:

Uma interrupção, como o nome indica, é um evento que provoca uma quebra na sequência normal do ciclo fetch-execute, através de um desvio incondicional para uma rotina de tratamento da interrupção (que tem de estar previamente carregada na memória, mas isto é papel do kernel durante a inicialização do sistema operacional) chamada interrupt handler.

A sinalização da interrupção pode ser gerada por algum elemento de hardware (ex.: o controlador de um dispositivo ao término de uma operação de I/O físico), ou pelo próprio programa em execução (este é o modo geral para invocar os serviços da API de system calls do sistema operacional). Cada tipo de interrupção suportado pelo processador possui um interrupt handler associado. Os endereços de memória correspondentes à primeira instrução de cada interrupt handler ficam armazenados em posições contíguas da memória, denominadas interrupt vector (IV).

Mas, para que este esquema possa funcionar, é necessário preservar o estado dos registradores do processador no momento da interrupção (em especial o program counter - PC), para que o programa que foi interrompido possa retornar a executar normalmente daquele ponto em diante. Isto é chamado de salvar o contexto do processo - que é o "apelido" para um programa executando sob o controle do kernel. Existem várias técnicas para salvar o contexto do processo. Por exemplo: usar uma estrutura de dados do kernel chamada stack (pelo que sei os processadores Intel desde o 8086 até o Pentium são assim), ou convencionar que cada rotina alvo de um desvio deve reservar memória e executar o salvamento do contexto da rotina de origem do desvio (como na programação assembly para mainframes IBM /370 e /370-XA. Creio que nas arquiteturas ESA/390 e z-Architecture ainda seja assim).

Ótimo. com todas estas peças no lugar, só precisamos agora mudar um pouquinho o nosso ciclo fetch-execute para incorporar a verificação da ocorrência de interrupções ao final da execução de cada instrução de máquina, tal como mostrado abaixo.

Como vocês podem ver existe também um mecanismo para temporariamente inibir o reconhecimento de interrupções pelo processsador. Isto é feito ligando/desligando bits de habilitação/desabilitação (enable/disable ou mask/unmask) em algum registrador de controle, um bit para cada tipo de interrupção suportada pelo processador. Quem faz uso disto? Tipicamente as rotinas do kernel, ou programas do usuário que invoquem funções ou serviços do sistema operacional que não possam ter sua execução interrompida.

Repare que a desabilitação (ou mascaramento) do reconhecimento de interrupções não elimina a sinalização da ocorrência da interrupção. Limpar a sinalização de interrupções pendentes são outros quinhentos, portanto quando a(s) interrupção(ões) voltarem a ser habilitadas o processador irá reconhecê-la(s).

Ao carregar no PC o endereço da primeira instrução do interrupt handler (contido no IV) temos o equivalente a um desvio incondicional do fluxo de execução para aquele endereço. As instruções de máquina do interrupt handler são executadas, então, da forma usual (podendo ou não, conforme o caso, ser interrompidas também). Cada rotina interrupt handler tem que, obrigatoriamente, como sua última atividade, restaurar o contexto que foi salvo. Isto restaura o valor do PC existente antes da interrupção, e força o retorno do fluxo de execução ao mesmo ponto do programa do usuário. A figura abaixo ilustra isso.

Claro que, além dos registradores, para que o programa do usuário possa retomar a execução normalmente as áreas de memória que contém as suas instruções de máquina e as suas estruturas de dados também tem que ser preservadas, mas isto é problema das funções de gerência da memória virtual do kernel, das quais falaremos em outro post.

Entendido o mecanismo de interrupção? Ótimo... passemos ao algoritmo time-sharing propriamente dito.

Time-sharing

Um processo começa a sua vida quando algum usuário (via interface do usuário) ou programa do usuário (via system call) solicita a execução de um programa. A rotina do kernel invocada para esta função é chamada Loader, e faz o seguinte:

• Invoca as rotinas de gerência da memória virtual para alocar os blocos de memória necessários para acomodar as instruções de máquina e as estruturas de dados do programa solicitado;
• Cria as estruturas de dados para o controle do processo pelo kernel;
• Cria uma entrada para o novo processo na ready queue (fila de processos prontos para execução).

O lugar onde o novo processo entra na ready queue geralmente é definido por critérios de prioridade. Senão o novo processo simplesmente ocupa o último lugar na fila.

O Loader então passa o controle para outra rotina do kernel, chamada dispatcher, que:

• Seleciona o primeiro processo na ready queue;
• Remove o processo selecionado e reorganiza a ready queue (faz a fila andar um passo à frente);
• Calcula, com base na estatística dos períodos anteriores de execução do processo selecionado (se houver, senão é feita uma estimativa inicial) o tempo máximo que este processo receberá do processador. Este intervalo de tempo é chamado time slice do processo, e é sempre um múltiplo inteiro de um intervalo básico denominado quantum (que normalmente depende do modelo do processador utilizado);
• Programa o relógio (clock) do processador para provocar uma interrupção após transcorrido o tempo de duração do time slice calculado;
• Restaura o contexto do processo selecionado.

Após isto o processo selecionado tem o controle do processador até que:

1. O time slice acabe (o que é sinalizado pela clock interrupt programada pelo Dispatcher);
2. O programa ceda voluntariamente o controle do processador. Normalmente isto ocorre como parte do processamento de alguma system call invocada pelo programa, cujo completamento será demorado (ex.: solicitação de operações de I/O);
3. Término (normal ou anormal) da execução do programa.

Em todos os casos o controle do processador é passado para outra rotina do kernel, denominada Scheduler, que faz o seguinte:

• Se  processo perdeu o controle do processador por término (caso 3), então invoca as rotinas de gerência da memória virtual para liberar as áreas de memória associadas ao processo e apaga as esturutras de dados para controle do processo;
• Se o proocesso perdeu o controle do processador por cessão voluntária (caso 2), então verifica se existem pendências para o processo (ex.: o completamento de operação de I/O). Se existirem pendências o processo é colocado na wait queue (fila de espera), senão o processo é colocado de volta na ready queue;
• Se o processo perdeu o controle do processador por término do time slice (caso 1) então o processo é colocado de volta na ready queue.
• Verifica se existem processos na wait queue cujas pendências já tenham sido liberadas (isto ocorre como parte do processamento de outros tipos de interrupção, como I/O interrupts, por exemplo). Os processos que não possuam mais pendências são, então, promovidos para a ready queue.

Então, excluindo as situações de início e término, um processo sempre estará em um entre tês estados: ready, quando o processo está na ready queue, aguardando chegar a sua vez de ganhar um time slice do tempo do processador; running, quando ele tem o controle do processador; ou waiting, quando ele está na wait queue aguardando o comletamento das suas pendências.

A figura abaixo sintetiza todo este algoritmo.

Por enquanto chega. No próximo post desta série (e o último, até onde imaginei tratar deste assunto) vou tratar da gerência da memória virtual pelo kernel. Até lá...