Espaço de endereçamento

Conjunto de endereços de memória que um processo pode acessar.

Contador de instruções

Registrador de uma unidade central de processamento que indica qual é a posição atual na sequência de execução de um processo. Dependendo dos detalhes da arquitetura, ele armazena o endereço da instrução que está sendo executada ou o endereço da próxima instrução.

Estados de um processo

Um processo pode ter vários estados, geralmente são eles: Novo, Pronto, Bloqueado, Terminado.

Mudança de contexto

Para transferir o controle da UCP de um processo a outro, é necessário guardar o estado do processo em execução e carregar o estado do processo a entrar em execução. Esta tarefa é conhecida como mudança de contexto (ou troca de contexto).

O contexto de um processo pode ser dividido em três elementos básicos:

• Contexto de hardware

  O contexto de hardware constitui-se basicamente do conteúdo dos registradores. No momento em que o processo perde a UCP, o sistema salva suas informações. Ele é fundamental para a implementação dos sistemas multiprogramáveis.

• Contexto de software

  O contexto de software especifica características do processo que influenciarão na execução de um programa. Ele define basicamente três grupos de informações sobre um processo: identificação, quotas e privilégios. A identificação define o processo para o sistema de forma única, através de seu PID, UID e GID. Quotas são os limites de cada recurso que o sistema operacional pode alocar, como número de arquivos abertos, quantidade de memória, quantidade de subprocessos que podem ser criados etc. Privilégio é o que o processo pode ou não fazer em relação ao sistema e outros processos.

• Espaço de endereçamento

  O espaço de endereçamento é a área de memória do processo em que o programa será executado e a área de memória onde os dados do processo serão armazenados. Cada processo possui seu próprio espaço de endereçamento, que deve ser protegido dos demais.

Subprocesso

Quando um processo (processo pai) cria um outro processo, ele é conhecido como subprocesso ou processo filho. O subprocesso, por sua vez, pode criar outros subprocessos.

A utilização de subprocessos permite dividir uma aplicação em partes que podem trabalhar de forma concorrente.

O problema com essa solução é que ela não aproveita a capacidade de multiprocessamento dos sistemas atuais. Como existe apenas um processo em execução, somente um dos processadores do sistema é utilizado para atendimento das requisições. Além disso, se houver várias requisições complexas e demoradas e uma requisição simples, como uma pequena página HTML, entrar no final da fila, esta requisição mais simples, que poderia ser respondida rapidamente, será atendida somente depois que todas as demais forem processadas.

A utilização de subprocessos resolve bem estes problemas. Se o servidor, no lugar de responder sequencialmente a cada requisição, criar um subprocesso para cada uma delas, tirará proveito da capacidade de multiprocessamento do sistema. Como cada requisição será tratada por um processo diferente, as requisições serão espalhadas pelos processadores do sistema, aproveitando sua capacidade de multiprocessamento. Além disso, como as requisições serão tratadas por diferentes processos, elas serão executadas concorrentemente.

Threads

Na tentativa de diminuir o tempo gasto na criação/eliminação de processos, bem como economizar recursos do sistema, foi introduzido o conceito de thread. Em um ambiente com múltiplos threads, não é necessário haver vários processos para implementar aplicações concorrentes.

Threads compartilham o processador da mesma maneira que um processo. Cada thread possui seu próprio conjunto de registradores (contexto de hardware), porém compartilha o mesmo espaço de endereçamento com os demais threads do processo. No momento em que um thread perde a utilização do processador, o sistema salva suas informações. Threads passam pelos mesmos estados que um processo.

A grande diferença entre subprocessos e threads é em relação ao espaço de endereçamento.

Tipos de processos

Existem basicamente dois tipos de processos relacionados ao tipo de processamento que executam

CPU-bound

Os processos do tipo CPU-bound passam a maior parte do tempo no estado executando, realizando poucas operações de E/S. Costumam ser encontrados em aplicações científicas.

I/O-bound

Os processos do tipo I/O-bound passam a maior parte do tempo no estado bloqueado, por realizar elevado número de operações de E/S. Costumam ser encontrados em aplicações comerciais. Processos interativos também são exemplos deste tipo de processo.

Processos e threads no Linux

O Linux pode duplicar um processo por meio da chamada de sistema fork(), mas também pode criar threads pela chamada de sistema clone(). No entanto, ele não faz distinção entre processos e threads. Toda entidade em execução, processo ou thread, será considerada como uma tarefa (task). Um processo com um único thread será considerado como uma tarefa, e um processo com n threads terá n estruturas de tarefas.

Cópia do segmento compartilhado - copy on write

Se os processos se limitarem à operação de consulta nos segmentos, não haverá problema, mas, se algum dos processos tentar escrever em um dos segmentos, neste momento, haverá a cópia do segmento compartilhado (mecanismo conhecido como cópia na escrita – copy on write). Além de aumentar o desempenho do sistema, esse mecanismo ajuda a diminuir o consumo de memória física.

Semáfotos

• down

  A operação down decrementa o valor do semáforo se ele for maior que 0, senão o processo é bloqueado.

• up

  A operação up incrementa o valor do semáforo caso não haja processos que tenham sido bloqueados pela operação down, senão um processo é desbloqueado.

No caso da exclusão mútua, as instruções down e up funcionam como protocolos para que um processo possa entrar e sair de sua região crítica. O semáforo fica associado a um recurso compartilhado, indicando quando o recurso está sendo acessado por um dos processos concorrentes. Se seu valor for maior que 0, nenhum processo está utilizando o recurso. Caso contrário, o processo fica impedido de acessar o recurso.

As operações up e down são realizadas pelo sistema operacional, que deve garantir que elas sejam executadas atomicamente.

Monitores

Um monitor é uma coleção de variáveis, procedimentos e estruturas de dados que são agrupados em um pacote. Em determinado instante, somente um processo pode estar ativo em um monitor. Toda vez que algum processo chama um procedimento do monitor, ele verifica se já existe outro processo executando qualquer procedimento do monitor. Caso exista, o processo ficará aguardando a sua vez, até que tenha permissão para executar.

SINCRONIZAÇÃO NO LINUX

O Linux oferece suporte à utilização de semáforos para sincronização de tarefas por meio da chamada de sistema sem_wait(), que realiza a operação up(), e da chamada de sistema sem_post(), que realiza a operação down(). Porém, em algumas situações, a tarefa pode querer apenas verificar se é possível prosseguir, mas não é interessante bloquear, caso não possa prosseguir. Para esses casos, pode ser utilizada a chamada de sistema sem_trywait(), que tem funcionamento parecido com a sem_wait(), exceto pelo fato de que, se o decremento não puder ser executado imediatamente, a chamada de sistema retorna um erro sem bloqueio.

A troca de mensagens pode ser implementada pelo mecanismo de pipe. O pipe ( | ) é um mecanismo especial de redirecionamento utilizado para conectar a saída padrão de um processo à entrada padrão de outro processo. Por exemplo, os comandos a seguir juntam todos os arquivos com extensão “.txt”, ordenando suas linhas e retirando as duplicadas.

cat *.txt | sort | uniq

Entenda o significado de cada um deles:

• O comando “cat *.txt” joga na saída padrão (tela) o conteúdo de todos os arquivos presentes no diretório e que possuem extensão “.txt”.

• O comando “sort” recebe linhas por sua entrada padrão (inicialmente, o teclado), ordena as linhas e envia as linhas devidamente ordenadas para a saída padrão.

• O comando “uniq” recebe linhas por sua entrada padrão e elimina as linhas duplicadas, enviando para a saída padrão somente as linhas que não estão em duplicidade.

Quando é utilizada a barra vertical ( | ) entre os comandos, é introduzido um pipe entre as tarefas, ou seja, as tarefas são colocadas em execução concorrente, e a saída padrão da tarefa à esquerda do pipe é conectada à entrada padrão da tarefa à direita do pipe. Assim, no exemplo, a saída do comando “cat *.txt” é enviada para a entrada do comando “sort”, que faz a ordenação, e sua saída é enviada à entrada do comando “uniq”, que elimina as linhas repetidas e, finalmente, joga o resultado de seu processamento para a saída padrão (o monitor, por padrão).

Outra forma de comunicação entre processos no Linux ocorre por meio de envio de sinais, que são enviados na ocorrência de eventos, como a chegada de uma informação pela rede, o fim de um temporizador, o término da execução de um processo filho etc. São eventos que chegam ao processo e precisam ser tratados de alguma forma. Para isso, é necessário definir uma rotina para o tratamento do evento.

Preemtivo

O escalonamento preemptivo permite que o sistema dê atenção imediata a processos mais prioritários, além de proporcionar melhor tempo de resposta em sistemas de tempo compartilhado. Outro benefício decorrente é o compartilhamento do processador de maneira mais uniforme.

Quando o sistema pode interromper um processo durante sua execução para colocá-lo no estado pronto e colocar outro processo no estado executando, coso o contrário será um sistema não preemptivo

• Escalonamento First In First Out (FIFO)

  Algoritmo de escalonamento também conhecido como primeiro a chegar, primeiro a ser servido (first come, first served).

  A grande força deste algoritmo é que ele é fácil de aprender e de programar.

  Nesse escalonamento, o processo que chegar primeiro é o primeiro a ser selecionado para execução. É preciso apenas uma fila, em que os processos que passam para o estado pronto entram no seu final. Quando um processo ganha a UCP, ele a utiliza sem ser interrompido, caracterizando-o como um algoritmo não preemptivo.

  O problema do escalonamento FIFO é a impossibilidade de se prever quando um processo terá sua execução iniciada. Outro problema é a possibilidade de processos CPU-bound de menor importância prejudicarem processos I/O-bound mais prioritários.

  Este algoritmo foi inicialmente implementado em sistemas batch.

Escalonamento Shortest Job First (SJF)

O algoritmo SJF (tarefa mais curta primeiro) associa a cada processo seu tempo de execução. Quando a UCP está livre, o processo no estado pronto que precisar de menos tempo para terminar é selecionado para execução.

O escalonamento SJF beneficia processos que necessitam de pouco processamento e reduzem o tempo médio de espera em relação ao FIFO. O problema é determinar quanto tempo de UCP cada processo necessita para terminar seu processamento. Em ambientes de produção, é possível estimar o tempo de execução, mas, em ambientes de desenvolvimento, é muito difícil. Imagine quatro tarefas A, B, C e D com tempos de execução de 14, 8, 6 e 4 minutos, respectivamente. Ao executá-las nessa ordem, o tempo de retorno para A é 14 minutos, para B, 22 minutos, para C, 28 minutos e, para D, 32 minutos, resultando em uma média de 24 minutos. Agora, considere executar essas quatro tarefas usando o algoritmo da tarefa mais curta primeiro. Os tempos de retorno são agora 4, 10, 18 e 32 minutos, o que resulta em uma média de 16 minutos. É um algoritmo de escalonamento não preemptivo e, assim como o FIFO, também foi utilizado nos primeiros sistemas operacionais com processamento batch.

• Escalonamento Shortest Remaining Time Next (SRTN)

  O SRTN (tempo restante mais curto em seguida) é uma versão preemptiva do SJF. Nele, o escalonador escolhe o processo cujo tempo de execução restante é o mais curto. Para o seu funcionamento, o tempo de execução precisa ser conhecido antecipadamente.

  Quando uma nova tarefa chega, seu tempo total é comparado ao tempo restante do processo atual. Se a nova tarefa precisar de menos tempo para terminar do que o processo atual, ela é suspensa, e a nova tarefa é iniciada. Esse esquema permite que novas tarefas curtas tenham um bom desempenho.

• Escalonamento cooperativo

  O SJF e o FIFO não são algoritmos de escalonamento aplicáveis a sistemas de tempo compartilhado, onde um tempo de resposta razoável deve ser garantido a usuários interativos.

  No escalonamento cooperativo, quando um processo já está em execução por determinado tempo, ele voluntariamente libera a UCP, retornando para a fila de processos prontos.

  Sua principal característica está no fato de a liberação da UCP ser uma tarefa realizada exclusivamente pelo processo em execução, que a libera para um outro processo. Não existe nenhuma intervenção do sistema operacional na execução do processo. Isto pode ocasionar sérios problemas na medida em que um programa pode não liberar a UCP ou um programa mal escrito pode entrar em loop, monopolizando a UCP.

  É um algoritmo de escalonamento não preemptivo.

• Escalonamento circular (Round Robin)

  Esse algoritmo é bem semelhante ao FIFO. Entretanto, quando um processo passa para o estado executando, existe um tempo limite (conhecido como time-slice ou quantum) para utilização da UCP de forma contínua. Quando esse tempo expira, o processo volta ao estado pronto, dando a vez a outro processo.

  A fila de processos no estado pronto é tratada como uma fila circular. O escalonamento é realizado alocando a UCP para cada processo da fila no intervalo de tempo determinado pelo quantum.

  Se o quantum for muito pequeno, gasta-se muito tempo de UCP com trabalho administrativo. Se o quantum for muito grande, a interatividade fica prejudicada, já que um processo que sai de execução pode demorar muito a voltar. Em geral, o quantum varia de 10 a 100ms.

  Através do escalonamento circular, nenhum processo poderá monopolizar a UCP, caracterizando-o como um algoritmo de escalonamento preemptivo.

  Um problema do escalonamento circular é que ele não oferece qualquer tratamento diferenciado a processos I/O-bound. Assim, processos CPU-bound terão a tendência de monopolizar a utilização da UCP, enquanto processos I/O-bound permanecem à espera.

• Escalonamento por prioridade

  O escalonamento circular consegue melhorar a distribuição do tempo de UCP em relação aos escalonamentos não preemptivos, porém ainda não consegue implementar um compartilhamento equitativo entre os diferentes tipos de processos.

  Para solucionar esse problema, os processos I/O-bound devem levar alguma vantagem no escalonamento, a fim de compensar o tempo excessivo gasto no estado bloqueado. Como alguns processos devem ser tratados de maneira diferente dos outros, é preciso associar a cada um deles uma prioridade de execução. Assim, processos de maior prioridade são escalonados preferencialmente.

  A preempção por prioridade é implementada mediante um relógio que interrompe o processador periodicamente, para que a rotina de escalonamento reavalie prioridades e, possivelmente, escalone outro processo, caracterizando-o como um algoritmo de escalonamento preemptivo.

  Todos os sistemas de tempo compartilhado implementam algum esquema de prioridade, que é uma característica do contexto de software de um processo, podendo ser estática ou dinâmica.

  Tem-se a prioridade estática quando a prioridade não é modificada durante a existência do processo. Apesar da simplicidade de implementação, a prioridade estática pode ocasionar tempos de resposta elevados.

  Na prioridade dinâmica, a prioridade do processo pode ser ajustada de acordo com o tipo de processamento realizado pelo processo ou pela carga do sistema. Quando o processo sai do estado bloqueado, recebe um acréscimo à sua prioridade. Dessa forma, os processos I/O-bound terão mais chance de ser escalonados e de compensar o tempo que passam no estado bloqueado.

  Para evitar que processos com maior prioridade sejam executados indefinidamente, a prioridade é diminuída com o passar do tempo.

  Outra forma de obter prioridade dinâmica é fazer com que o quantum do processo seja inversamente proporcional à fração do último quantum utilizado.

  Embora os sistemas de prioridade dinâmica sejam mais complexos e gerem um overhead maior, o tempo de resposta oferecido compensa.

• Escalonamento por múltiplas filas

  Como os processos de um sistema possuem diferentes características de processamento, é difícil que um único mecanismo de escalonamento seja adequado a todos. Uma boa política seria classificar os processos em função do tipo de processamento realizado e aplicar a cada grupo mecanismos de escalonamentos distintos.

  O escalonamento por múltiplas filas implementa diversas filas de processo no estado pronto, onde cada processo é associado exclusivamente a uma delas. Cada fila possui um mecanismo próprio de escalonamento em função das características do processo. Nesse esquema, os processos devem ser classificados, previamente, em função do tipo de processamento para poderem ser encaminhados à determinada fila.

  Cada fila possui uma prioridade associada, que estabelece quais são prioritárias em relação às outras. O sistema só pode escalonar processos de uma fila se todas as outras filas de prioridade maior estiverem vazias.

  Para exemplificar esse escalonamento, considere que os processos, em função de suas características, sejam divididos em três grupos: sistema, interativo e batch. Os processos do sistema devem ser colocados em uma fila de prioridade superior aos outros processos, implementando um algoritmo de escalonamento baseado em prioridades. Os processos de usuários interativos devem estar em uma fila de prioridade intermediária, implementando, por exemplo, o escalonamento circular. O mesmo mecanismo de escalonamento pode ser utilizado na fila de processos batch, com a diferença de que esta fila deverá possuir uma prioridade mais baixa.

• Escalonamento em sistemas de tempo real

  Um sistema de tempo real é aquele em que o tempo tem um papel essencial. Tipicamente, um ou mais dispositivos físicos externos ao computador geram estímulos. O computador tem de reagir em conformidade dentro de um montante de tempo fixo. Exemplos de sistemas de tempo real são equipamentos que estão monitorando pacientes em uma UTI, o piloto automático de um avião e o controle de robôs em uma fábrica automatizada. Em todos esses casos, ter a resposta certa tarde demais é, muitas vezes, tão ruim quanto não tê-la.

  Sistemas em tempo real geralmente são categorizados como tempo real crítico, significando que há prazos absolutos que devem ser cumpridos, e tempo real não crítico, significando que descumprir um prazo ocasional é indesejável, mas, mesmo assim, tolerável. Em ambos os casos, o comportamento em tempo real é conseguido com a divisão do programa em uma série de processos, cada um dos quais é previsível e conhecido antecipadamente. Esses processos geralmente têm vida curta e podem ser concluídos em curto espaço de tempo. Quando um evento externo é detectado, cabe ao escalonador programar os processos de maneira que todos os prazos sejam atendidos.

  Os eventos a que um sistema de tempo real talvez tenha de responder podem ser categorizados ainda como periódicos (significando que eles ocorrem em intervalos regulares) ou aperiódicos (significando que eles ocorrem de maneira imprevisível). Dependendo de quanto tempo cada evento exige para o processamento, tratar de todos talvez não seja possível.

  Diz-se de um sistema de tempo real que atende a esse critério que ele é escalonável, o que significa que ele realmente pode ser implementado. Um processo que não atende a esse critério não pode ser escalonado, pois o montante total de tempo de UCP que os processos querem coletivamente é maior do que a UCP pode proporcionar.

  Algoritmos de escalonamento de tempo real podem ser estáticos ou dinâmicos. Algoritmos estáticos tomam suas decisões de escalonamento antes de o sistema começar a ser executado. Algoritmos dinâmicos tomam suas decisões no tempo de execução, após ela ter começado. O escalonamento estático funciona apenas quando há uma informação perfeita disponível antecipadamente sobre o trabalho a ser feito e sobre os prazos que precisam ser cumpridos. Algoritmos de escalonamento dinâmico não têm essas restrições.

• Escalonamento de threads

  Quando vários processos têm, cada um, múltiplos threads, há dois níveis de paralelismo presentes: processos e threads. O escalonamento nesses sistemas vai diferir, ainda, se são threads de usuário ou threads de núcleo.

  Sendo threads de usuário, o núcleo não tem ciência da existência dos threads. Assim, ele opera como sempre fez, escolhendo um processo A e dando a A o controle de seu quantum. O escalonador de thread dentro de A decide qual thread executar (A1, por exemplo). Dado que não há interrupções para multiprogramar threads, esse thread pode continuar a ser executado por quanto tempo quiser. Se ele utilizar todo o quantum do processo, o núcleo selecionará outro processo para executar. Quando o processo A executar novamente, o thread A1 retomará a execução. Ele continuará a consumir todo o tempo de A até que termine. No entanto, seu comportamento não afetará outros processos. Eles receberão o que quer que o escalonador considere sua fração apropriada, não importa o que estiver acontecendo dentro do processo A.

  Agora, considere o caso em que os threads de A tenham relativamente pouco trabalho para fazer, por exemplo, 5ms de trabalho dentro de um quantum de 50ms. Em consequência, cada um é executado por um tempo. Então, cede a UCP de volta ao escalonador de threads. Isso pode levar à sequência A1, A2, A3, A1, A2, A3, A1, A2, A3, A1, antes que o núcleo chaveie para o processo B.

  O algoritmo de escalonamento usado pelo sistema de tempo de execução pode ser qualquer um dos descritos anteriormente. A única restrição é a ausência de um relógio para interromper um thread que esteja sendo executado há tempo demais. Como os threads cooperam, isso normalmente não é um problema.

  Vejamos agora a situação com threads de núcleo. Aqui, o núcleo escolhe um thread em particular para executar. Ele não precisa levar em conta a qual processo o thread pertence, mas pode fazer isso. O thread recebe um quantum e é suspenso compulsoriamente se o exceder. Com um quantum de 50ms e threads que são bloqueados após 5ms, a ordem do thread por algum período de 30ms pode ser A1, B1, A2, B2, A3, B3, algo que não é possível com esses parâmetros e threads de usuário. Uma diferença importante entre threads de usuário e de núcleo é o desempenho. Realizar um chaveamento de thread com threads de usuário exige um punhado de instruções de máquina. Com threads de núcleo, é necessário um chaveamento de contexto completo, mudar o mapa de memória e invalidar o cache, o que representa uma demora bem maior. Por outro lado, com threads de núcleo, ter um bloqueio de thread na E/S não suspende todo o processo, como ocorre com threads de usuário. Como o núcleo sabe que chavear de um thread no processo A para um thread no processo B é mais caro do que executar um segundo thread no processo A, ele pode levar essa informação em conta quando toma uma decisão.

  Outro fator importante é que os threads de usuário podem empregar um escalonador de thread específico de uma aplicação.