Artigo: Processos e Threads

[Arkanun1000 4.581]

Processos e Threads

 

 

Processo é geralmente entendido como um programa em execução porém, na realidade, trata-se de uma estrutura mais complexa que contém, além do programa no seu formato executável, todas as informações necessárias (contexto) à execução e ao controle da execução do mesmo, como por exemplo: o contador de programa, pilhas, registradores e área de dados. O programa é uma entidade passiva, que pode ser visto como o conteúdo de um arquivo em disco, enquanto que o processo é uma entidade ativa, possuindo um contador de programa (PC), que especifica a próxima instrução a ser executada, e um conjunto de recursos a ele alocados. Nos sistemas operacionais mais antigos, cada processo possuía um único fluxo de controle, ou seja, as instruções são executadas sequencialmente, uma de cada vez. Já nos sistemas mais modernos, um processo pode, por sua vez, dar início a um ou mais subprocessos, que são executados em paralelo ou de forma concorrente com o processo pai e, para todos os efeitos, apresentam as mesmas características e particularidades de um processo qualquer, no tocante a contexto e fluxo de controle. Threads, por outro lado, representam uma nova concepção na forma de um processo paralelizar a execução de partes do seu código. Os threads, conceitualmente, se assemelham a subprocessos porém, diferentemente destes, não possuem identidade própria e, portanto, não são independentes. Cada thread possui seu próprio contador de programa, sua pilha e seus registradores porém compartilham todos o mesmo espaço de endereçamento, isto é, como se fossem uma única entidade . Nos sistemas tradicionais, cada processo tem seu próprio contexto e apenas um fluxo de controle – são do tipo single thread. Freqüentemente, no entanto, é desejado ter-se múltiplos fluxos de controle que compartilhem do mesmo espaço de endereçamento e sejam executados de forma paralela (no caso de multiprocessamento) ou de forma concorrente (no caso de monoprocessamento), como se fossem processos separados. Threads satisfazem estes requisitos, pois compartilham do mesmo espaço de endereçamento com o processo pai e com os demais threads, e podem ser executados de forma concorrente ou paralela (fig. VIII.1). O esquema de threads, no entanto, só pode ser utilizado quando for especificamente suportado pelo sistema operacional ou quando da existência de um gerenciador de threads. Os threads não são tão independentes como os processos e os subprocessos, uma vez que compartilham de um mesmo espaço de endereçamento e, por conseguinte, compartilham das mesmas variáveis globais, dos mesmos arquivos, das mesmas tabelas, etc. Uma vez que todo thread pode acessar todo o espaço virtual de endereçamento do processo pai e dos demais threads, ele pode “ler e escrever” em qualquer local, mesmo na pilha dos outros threads – o que significa que não há qualquer forma de proteção de acesso entre os threads. Os threads compartilham a UCP da mesma forma que os processos o fazem, isto é, podem criar outros threads e podem ficar suspensos aguardando (em block waiting) pelo término de uma operação qualquer (system call). Comparativamente, o contexto de um thread e de um processo é constituído por:

 

 

 

 

Figura 2: Processo Y com 3 subprocessos e Processo X com 3 Threads

 

 

 

Cabe ao sistema operacional a incumbência de prestar todo o suporte, os recursos e a proteção que forem necessários à execução eficiente e eficaz dos processos que forem submetidos. Para isto, o SO precisa:

 

a) Ser capaz de alternar a execução dos vários processos submetidos de forma a maximizar o uso da UCP e ao mesmo tempo garantir um tempo de resposta razoável a cada processo;

 

b) Distribuir os recursos

 

 

 

VIII.2 – Contexto de um Processo

O ambiente necessário a execução de um processo é formado pelos contextos de hardware e de software. O contexto de hardware é fundamental para que os processos possam se revezar no controle (utilização) da UCP, podendo ser interrompidos pelo SO e, posteriormente, reinicializados do ponto onde haviam parado sem qualquer solução de continuidade, isto é, como se nada tivesse ocorrido. A operação que possibilita tal revezamento é chamada de troca de contexto (context switch) e consiste basicamente em salvar o conteúdo dos registradores e carregá-los com os valores referentes ao processo que esteja ganhando o controle da UCP. O contexto de software especifica características do processo que influem na execução do mesmo, tais como: o número máximo de arquivos abertos, o tamanho do buffer para operações de E/S, etc. O Sistema Operacional cria para cada processo uma estrutura chamada PCB – Process Control Block, onde ele mantém todas as informações de contexto (hardware e software) do processo. O conteúdo e a estrutura do PCB variam de sistema para sistema, sendo que no exemplo mostrado na figura VIII.2 a seguir, ele consiste do estado do processo, da sua identificação, do registrador PC, dos demais registradores da UCP, de informações de escalonamento, de informações de memória, de informações de contabilização e de informações de entrada e saída.

 

 

Figura VIII.2 – Exemplo de PCB – Process Control Block

 

VIII.3 – Estados de um Processo O procedimento de execução de um processo tem início com a criação do mesmo, carga do mesmo em memória, para que de lá possa ser escalado para tomar o controle da UCP e realizar seu processamento e, finalmente, terminado, quando da sua conclusão. Quando em memória, o processo pode estar num dos três estados seguintes: em execução, em espera pela ocorrência de um evento previamente solicitado por ele mesmo ou, no estado de pronto para execução. Estados estes representados na figura VIII.3.

 

Um processo para poder ser escalado para execução precisa estar no estado de pronto (ready). Um processo em execução pode perder o controle da UCP de forma voluntária (quando ele próprio realiza uma operação de E/S) ou de forma involuntária (quando por algum critério gerencial o próprio sistema operacional retoma o controle da UCP). Um processo em estado de espera fica nesta situação até que sua pendência seja satisfeita e de lá passa para o estado de pronto.

 

 

 

 

Quando um processo em execução solicita um recurso que não está disponível no momento (como por exemplo a alocação de um arquivo ou de um periférico) ou cuja obtenção seja operacionalizada fora da UCP (como por exemplo leitura de registros em disco – DMA), ele automáticamente perde o controle da UCP e passa do estado de execução para o de espera.

 

O processo estando no estado de espera passa para o estado de pronto para execução assim que tiver sua solicitação de recurso atendida pelo sistema. No estado de pronto ele está em condições de reiniciar sua execução e fica aguardando apenas chegar sua vez de retomar o controle da UCP.

 

Nos sistemas preemptivos, isto é, que admitem interromper a execução de um processo toda vez que seu tempo (quantum) permitido para alocação da UCP expirar, pode ocorrer que um processo saia da UCP não para o estado de espera mas direto para o estado de pronto. Vê-se assim que um processo pode mudar de estado face um evento originado por ele próprio (eventos voluntários) ou pelo sistema (eventos involuntários).

 

 

 

Estados de Execução de um Processo

Dentro do estado de execução, para fins de proteção do sistema como um todo, são adotados níveis de prioridade que definem o que o processo está ou não autorizado a fazer. É a forma utilizada para evitar que processos dos usuários venham a danificar áreas do sistema operacional ou mesmo áreas reservadas a outros processos.

 

Diversas são as estratégias de definição destes níveis de prioridade. A estratégia básica consiste na definição de dois estados, um supervisor e outro usuário. Sistemas mais complexos como o OS/2 por exemplo, adotam 4 níveis: 0 – kernel (supervisor), 1 – sistema de arquivos, comunicação entre processos e acionadores de dispositivos de E/S, 2 – subsistema de E/S e 3 – usuário.

 

Um processo somente passa de um nível superior para um inferior com autorização do sistema operacional, que assim garante a integridade operacional.

 

 

 

VIII.4 – Sincronização de Processos

O compartilhamento de recursos entre processos pode gerar situações indesejáveis de inconsistência no acesso aos dados e de indisponibilidade no acesso aos recursos, a ponto de comprometer o sistema como um todo. A solução para estes casos é garantir a exclusão mútua, isto é, apenas um processo tem autorização para acessar o recurso de cada vez. O trecho do programa onde é feito o acesso ao recurso compartilhado é denominado região crítica e os mecanismos que implementam a exclusão mútua utilizam um protocolo de acesso à região crítica. Toda vez que um processo for executar sua região crítica, ele é obrigado a passar por um controle de entrada e outro de saída.

 

 

 

VIII.4.1 – Problemas de Sincronização Surgem a partir das tentativas de implementar a exclusão mútua. a) velocidade de execução dos processos A velocidade de execução dos processos pode interferir na operacionalização da exclusão mútua. No caso de um chaveamento simples entre dois processos, digamos A e B, sendo que o processo A consome um tempo de processamento bem mais longo que o processo B, pode levar a situação em que B se veja impossibilitado de entrar em sua região crítica por estar bloqueado pela execução do processo A fora da sua região crítica (fig. VIII.4).

 

 

 

Figura VIII.4 – Prog B impedido de acessar sua região crítica porque Prog A detém o controle da UCP em longo processamento fora da sua região crítica.

 

 

Observe na figura que o programa “B” passa pela sua região crítica e em seguida libera o acesso ao programa “A”. Caso o programa “B” retorne ao ponto de entrada de sua região crítica antes que o programa “A” passe por sua região crítica e libere o acesso ao programa “B”, este ficará bloqueado embora o programa “A” não esteja usando sua região crítica.

 

b) “Starvation”

É a situação onde um processo nunca consegue executar sua região crítica e, em conseqüência, nunca consegue acessar o recurso compartilhado. Este problema ocorre quando 2 ou mais processos estão na lista de espera por um recurso compartilhado. No momento em que o recurso é liberado, o sistema precisa determinar qual dos processos em espera deve ganhar acesso ao recurso. Esta escolha pode ser:

 

· aleatória – um processo pode nunca ser escolhido e sofrer starvation;

 

· por prioridade – um processo pode novamente permanecer indefinidamente na fila de espera face a constante chegada de processos de maior prioridade;

 

· fila tipo FIFO – evita starvation porém pode prejudicar o desempenho de programas com maior prioridade de execução.

 

c) Sincronização Condicional É quando um recurso compartilhado não se encontra pronto para ser utilizado e, nesse caso, o processo precisa ser mantido em estado de espera até o recurso ficar pronto. Este tipo de sincronização aparece em qualquer operação onde existam processos gerando serviços e processos consumindo estes mesmos serviços.

 

Um exemplo clássico deste tipo de sincronização é o da gravação de um buffer por um processo e leitura por outro. Ambos os processos envolvidos devem ser sincronizados de forma a não tentarem gravar um buffer cheio ou ler um buffer vazio.

 

 

 

VIII.4.2 – Soluções de Hardware

a) desabilitação de interrupções

Como a mudança de contexto só pode ser realizada através do uso de interrupção, se um processo desabilitar suas interrupções internas ao entrar na sua região crítica, ele garantirá a exclusão mútua porque não poderá ser interrompido pelo sistema.

 

Este mecanismo no entanto, não é dos mais convenientes por vários motivos, sendo que os principais são:

 

· O processo não tornar a habilitar suas interrupções ao sair da região crítica, permanecerá com o controle da UCP até que ele a deixe por um evento voluntário.

 

· O processo entrar em loop dentro da região crítica e, novamente, ninguém o interromperá. Desabilitar interrupções é uma solução interessante porém face ao potencial de efeitos colaterais que possam surgir, é normalmente adotado apenas pelas rotinas do sistema operacional.

 

 

 

b) Instrução test-and-set

É uma instrução atômica – indivisível e que não pode ser interrompida pela UCP – que testa e seta uma variável global que serve de senha de acesso a uma região crítica.

 

 

É necessário se cadastrar para acessar o conteúdo.

• Entre
• ou
• Cadastre-se

 

 

 

VIII.4.3 – Soluções de Software

Três fatores fundamentais para a solução dos problemas de sincronização devem ser considerados:

 

1. o número de processos concorrentes e o tempo de execução dos mesmos devem ser irrelevante;

 

2. um processo fora de sua região crítica não deve impedir que outros processos entrem em suas próprias regiões críticas;

 

3. um processo não pode permanecer indefinidamente esperando para entrar na sua região crítica (starvation);

 

As soluções inicialmente implementadas para resolver o problema de exclusão mútua sofriam da síndrome do “busy waiting”, ou seja, o processo permanecia em loop checando a liberação do acesso à região crítica e, portanto consumindo cilcos de UCP. As soluções mais atuais adotam primitivas que permitem que um processo seja colocado em estado de espera e reativado apenas quando o recurso estiver disponível. Nesta linha foram introduzidos os semáforos e os monitores.

 

a) Semáforo Consiste em uma variável inteira, não negativa, que só pode ser manipulada por duas instruções atômicas: down e up. Cada semáforo é associado a um único recurso compartilhado e seu significado é:

 

0(zero) – inexistência de recurso disponível;

 

>0(maior que zero) – disponibilidade de recurso. Um processo para entrar em sua região crítica precisa antes decrementar o conteúdo do semáforo (down), que só é permitido se ele for “>0” e ao sair incrementa-o (up), liberando o recurso para os demais processos.

 

Up e Down são atômicas e geralmente implementadas como system calls. Quando o processo executa um down em um semáforo vazio, ele automaticamente é colocado em estado de espera (sleeping) e é automaticamente reativado quando algum outro processo liberar (up) aquele recurso.

 

 

É necessário se cadastrar para acessar o conteúdo.

• Entre
• ou
• Cadastre-se

 

 

b) Monitor

O uso de semáforos exige muito cuidado do programador pois qualquer engano pode levar a problemas de sincronização imprevisíveis e difíceis de reproduzir, face à execução concorrente dos processos. Monitores são mecanismos de alto nível implementados pelo próprio compilador. Para isto basta especificar todas as regiões críticas em forma de procedimentos do monitor, e o compilador se encarregará de implementar a exclusão mútua.

 

 

VIII.4.4 – Deadlock É conseqüência do compartilhamento exclusivo e ocorre sempre que um ou mais processos estiverem esperando por um evento (recurso) que jamais ocorrerá. Caracteriza-se por uma espera circular onde dois ou mais processos aguardam pela liberação de recursos para que possam continuar suas tarefas. Exemplo, o processo “A”, da figura VIII.5, detém o recurso X e espera pelo recurso Y, por outro lado, o processo “B” detém o recurso Y e espera pelo X.

 

 

Figura VIII.6 – Esquema representativo de um Deadlock

 

a) condições para ocorrência de deadlock

 

· cada recurso só pode estar alocado a um único processo em um determinado instante (exclusão mútua);

 

· um processo, além dos recursos já alocados, pode ficar na espera por outros;

 

· um recurso não pode ser retirado de um processo porque outros processos o estão desejando (não-preempção);

 

· um processo pode aguardar por um recurso que esteja alocado a outro processo e viceversa (espera circular).

 

Dois procedimentos podem ser implementados para tratamento de deadlocks: previnir sua ocorrência ou, detetar sua ocorrência.

 

 

 

a.1) prevenção de deadlocks

 

Constitui-se de ações a serem tomadas com o objetivo de previnir a ocorrência de uma ou mais situações que possam levar ao surgimento de um de deadlock. Algumas possibilidades são:

 

· estabelecer o critério de que todos os recursos sejam previamente alocados, antes do processo ganhar acesso à UCP; · admitir a prática da preempção, isto é, o sistema ter a possibilidade de retirar um recurso alocado para um processo e dar para outro processo;

 

· forçar que um processo não aloque mais do que um recurso de cada vez. Qualquer que seja a estratégia de prevenção adotada, ela é sempre muito onerosa, uma vez que precisa ser executada a todo instante.

 

A estratégia mais comum e menos onerosa é detectar a ocorrência de um deadlock e, uma vez detectado, executar rotinas de resolução do problema.

 

a.2) Detecção de Deadlocks

 

Geralmente os algoritmos que implementam este mecanismo verificam a existência de uma “espera circular”, percorrendo toda a estrutura de alocação sempre que um processo não pode ser imediatamente atendido. Após o deadlock ser detectado, as ações de correção mais comuns são: · eliminar um ou mais processos envolvidos; · liberar acumulativamente alguns dos recursos já alocados pelos processos envolvidos até que a espera circular se desfaça.

 

 

 

VIII.5 Escalonamento de Processos

 

Os principais objetivos do escalonamento (scheduling) de processos são:

 

· manter a UCP ocupada a maior parte do tempo;

 

· balancear a utilização do processador pelos processos em execução;

 

· maximizar o throughput (capacidade de atendimento a processos) do sistema; e

 

· garantir tempos de resposta razoáveis aos usuários interativos. Para atender tais objetivos, muitas vezes conflitantes, os SOs precisam levar em considera- ção:

 

· as características dos processos em execução (batch, interativo, tempo-real, CPUbounded, IO_bounded);

 

· a disponibilidade de recursos; · as características da instalação. O escalonamento dos processos é realizado por um módulo do sistema operacional conhecido como dispatcher (scheduler). Existem diversos algoritmos utilizados para tal finalidade e cada um apresenta características próprias favorecendo um ou outro critério para a escolha do próximo processo a receber o controle da UCP. Os critérios geralmente considerados incluem os seguintes parâmetros ou medidas de eficiência:

 

· utilização da UCP – o desejado é manter a UCP p mais ocupada possível. O grau de utilização da UCP varia de 0 (idle) a 100%. Geralmente a ocupação da UCP gira no entorno dos 40% para sistemas com carga moderada e aproximadamente 90% para os com carga pesada.

 

· throughput – medida que representa o número de processos concluídos por unidade de tempo (ex. 10 processos/segundo).

 

· turnaround time – mede o tempo total gasto na execução de um processo, desde o momento em que ele é submetido até o instante em que é concluído.

 

· waiting time – mede apenas o tempo em que o processo fica aguardando por execução na fila de processos prontos (ready queue).

 

· response time – mede o tempo decorrido entre a submissão do processo e o instante em que o mesmo gera a primeira resposta ao usuário. Existem basicamente dois tipos de algoritmos para escalonamento de processos: os do tipo preemptivo e os do tipo não-preemptivo.

 

 

 

VIII.5.1 – Algoritmos Não-Preemptivos

Nesse tipo de escalonamento, quando um processo ganha o direito de utilizar a UCP, nenhum outro processo ou mesmo o próprio SO pode lhe tirar esse recurso. Ele manterá o uso da UCP até que, voluntariamente, a deixe.

 

Dentro do contexto dos algoritmos não-preemptivos, diferentes estratégias podem ser implementadas, tais como: o escalonamento FIFO e o shortest_job_first.

 

 

 

a) Escalonamento FIFO É de implementação e operação bastante simples, necessitando apenas da manutenção de um fila, onde os processos que passam para o estado de pronto entram no final da mesma e são escalados para execução quando atingem o seu topo.

 

As maiores restrições relativas a esta estratégia são:

 

· incapacidade de prever o instante inicial de execução de um processo;

 

· possibilidade de ocorrência de processos CPU_bound de menor importância prejudicarem o processamento de processos IO_bound mais prioritários;

 

Esta estratégia não é eficiente para sistemas de tempo compartilhado e muito menos para sistemas em tempo real.

 

 

 

b) Escalonamento Shortest_Job_First

Associa a cada processo uma estimativa do seu tempo de execução e favorece aqueles de menor tempo, escalando-os prioritariamente. A restrição maior deste algoritmo está na determinação da estimativa do tempo necessário para execução de um determinado processo. Tarefa fácil para processos (sistemas) já em regime de produção mas extremamente difícil para aqueles ainda em fase de desenvolvimento.

 

 

 

VIII.5.2 – Algoritmos Preemptivos

Um algoritmo de escalonamento é considerado preemptivo quando pode interromper um processo em execução, tirar-lhe o controle da UCP e repassá-la para outro processo que estiver na fila de espera. A estratégia preemptiva permite que o sistema dê atenção imediata a processos mais prioritários, bem como o compartilhamento do processador de forma mais uniforme. É importante lembrar que a troca de um processo na UCP implica, necessariamente, na troca de contexto (context switching), o que representa um overhead introduzido pelos algoritmos preemptivos não existente na estratégia não-preemptiva. Para que isto não se torne um problema crítico, os parâmetros de quantum ou time slice adotados para os processos em execução precisam ser cuidadosamente estabelecidos. Os principais algoritmos deste genero incluem: o round_robin, o por prioridade, o por múltiplas filas e o por múltiplas filas com realimentação. a) Escalonamento Round_Robin É um escalonamento circular, bastante similar ao FIFO, porém com a adoção de um limite de tempo (quantum ou time_slice) permitido aos processos para uso contínuo da UCP. A definição deste quantum é um parâmetro de gerência da operação, sendo que se deve levar em consideração a disponibilidade de recursos (MP e processador), o tipo e o número de processos em execução. Um tamanho razoável para este quantum pode oscilar, por exemplo, entre 100 e 300ms. b) Escalonamento Baseado em Prioridade O escalonamento leva em consideração o nível de prioridade estabelecido para os processos. É importante observar que contrariamente ao que possa ser inicialmente imaginado, os processos do tipo IO_bound devem, em princípio, receber uma prioridade mais alta, a fim de compensar o excessivo tempo gasto no estado de espera. O nível de prioridade é uma característica do processo e pode ser dos tipos estática ou dinâmica. Na prioridade dinâmica, ela pode ser constantemente ajustada em função do tipo de processo e da carga corrente do sistema. c) Escalonamento por Múltiplas Filas Como os diversos processos em execução geralmente possuem características de processamento distintas, é difícil imaginar que um único mecanismo de escalonamento seja igualmente adequado a todos. Uma boa política seria a de classificar os processos em função do tipo de processamento realizado, e aplicar a cada grupo um mecanismo distinto de escalonamento. O escalonamento por múltiplas filas implementa diversas filas de processos no estado de pronto (ready), e a cada fila pode ser estabelecido um mecanismo de escalonamento diferente. Cada fila possui uma prioridade associada, que estabelece uma relação de prioridade entre elas e o sistema, a partir disto, somente escala processos de uma fila quando todas as outras de maior prioridade estiverem vazias. d) Escalonamento por Múltiplas Filas com Realimentação Estratégia que visa reduzir a penalidade imposta pelo método anterior aos processos classificados em filas de mais baixa prioridade. Visa também atenuar “injustiças” que podem se materializar no método por múltiplas filas pelo fato de um processo alterar seu comportamento no decorrer do seu processamento.

 

Nesta estratégia de escalonamento, o sistema tenta identificar dinamicamente o comportamento de cada processo durante seu período de execução, e ajustar também dinamicamente, a prioridade e o mecanismo de escalonamento associado a cada um. A figura abaixo mostra um esquema com “m” filas e diferentes estratégias. Um processo ao ser inicializado (startado) é colocado no final da fila correspondente ao seu nível de prioridade. Sua progressão dentro da fila segue a estratégia de escalonamento ali adotada e, após ter sido escalado e concluído sua etapa de processamento, ele volta para o fianl da fila imediatamente inferior, caso sua perda da UCP tenha ocorrido por preempção ou no final da fila imediatamente superior, caso a perda da UCP tenha ocorrido voluntariamente para espera da ocorrência de algum evento externo.