Capítulo 2. Processos e Threads 1.

Início do sistema;
2. Execução de uma chamada de sistema de
criação de processos por um processo
Processo é uma abstração de um programa em em execução;
execução. Mantêm a capacidade de operações 3. Uma requisição do usuário para criar um
(pseudo)concorrentes, mesmo quando há novo processo;
apenas uma CPU disponível. Eles transformam 4. Início de uma tarefa em lote (batch
uma única CPU em múltiplas CPUs virtuais. job);

Processos Foreground (primeiro plano): que

1. Processos interagem com usuários e realizam tarefas
para eles.
Em qualquer sistema multiprogramado, a CPU
chaveia de programa para programa, Processos Background (segundo plano): Que não
executando cada um deles por dezenas ou estão associados a usuários em particular, mas
centenas de milissegundos. Se tem a impressão que apresentam alguma função específica.
de paralelismo. Por isso se usa o termo
pseudoparalelismo para distinguir do Processos que ficam em background com a
verdadeiro paralelismo de hardware dos finalidade de lidar com alguma atividade como
sistemas multiprocessadores (que tem mais de mensagem eletrônica, páginas da web, notícias,
uma CPU que compartilham simultaneamente a impressão, entre outros, são chamados de
mesma memória física). Daemons.

Muitas vezes, um processo em execução fará

1.1 O modelo de processo chamadas de sistema (system calls) para criar
um ou mais novos processos para ajudá-lo em
Processo é apenas um programa em execução, seu trabalho.
acompanhado dos valores atuais do contador de
programa, dos registradores e das variáveis. O Tecnicamente, em todos esses casos, um novo
mecanismo de trocas rápidas entre os processo (processo filho) é criado por um
processos é chamado de multiprogramação processo existente (processo pai) executando
(como visto no capítulo 1). uma chamada de sistema para a criação de
processo. Esse processo (processo pai) pode
A ideia principal é que um processo constitui ser um processo de usuário que está
uma atividade. Ele possui programa, entrada, executando, um processo de sistema invocando
saída e um estado. Um único processador pode a partir do teclado ou do mouse ou um processo
ser compartilhado entre os vários processos, gerenciador de lotes. O que o processo pai faz
com algum algoritmo de escalonamento usado é executar uma chamada de sistema para criar
para determinar quando parar o trabalho sobre um novo processo filho e assim indica, idreta ou
um processo e servir outro. indiretamente, qual programa executar nele.

No UNIX a chamada de sistema para criar um

1.2 Criação de Processos processo é o FORK. Essa chamada cria um clone
iidentico ao processo que a chamou. Após o
Há 4 eventos principais que fazem com que fork os dois processos tem a mesma imagem de
processos sejam criados: memória, as memsmas variáveis de ambiente e
os mesmos arquivos abertos. Normalmente o
processo filho executa, em seguida, EXECVE ou No Unix, um processo, todos os seus filhos e
uma chamada de sistema similar para mudar descendentes formam um grupo de processos.
sua imagem de memória e executar um novo
programa. No Unix um processo especial, chamado INIT,
está presente na imagem de carga do sistema.
No Unix e no Windows, depois que um processo Este pode se bifurcar em vários outros
é criado, o pai e o filho tem seus próprios processos de terminal. O usuário ao utilziar o
espaços de endereçamento distintos. terminal pode executar um comando que gere
um processo e assim por diante.
No Unix o espaço de endereçamento inicial do
filho é uma cópia do espaço de endereçamento No Win não apresenta nenhum conceito de
do pai, mas ha dois espaços de endereçamento hierarquia de processos. Todos os processos
distintos. são iguais. Algo parecido com uma hierarquia de
processos ocorre somente quando um processo
No Windows, os espaços de endereçamento do é criado. Ao paii é dado um identificador
pai e do filho são diferentes desde o início. especial (chamado Handle), que ele pode usar
para controlar o filho. Contudo, ele é livre para
passar esse identificador para alguns outros
1.3 Término de Processos processos, invalidando, assim, a hierarquia. Os
processos no Unix não pode deserdar seus
Algumas razões para o término do processo: filhos.
• Saída normal (voluntária);
• Saída por erro (voluntária);
• Erro fatal (involuntário); 1.5 Estado de Processos
• Cancelamento por outro processo
(involuntário); Embora cada processo seja uma entidade
independente, com seu próprio contador de
Unix → exit programa e estado interno, muitas vezes os
Win → exitProcess processos precisam interagir com outros. Um
processo pode gerar uma saída que outro
A quarta razão pela qual um processo pode processo usa como entrada.
terminar se dá quando um processo executa
uma chamada de sistema dizendo ao sistema cat ch1 ch2 ch3 | grep tree
operacional para cancelar algum outro
processo; O primeiro processo CAT gera como saída a
concatenação dos 3 arquivos.
Unix → kill
Win → terminateProcess O segundo processo, que executa GREP,
seleciona todas as linhas contendo a palavra
Em alguns sistemas quando um processo tree.
termina voluntariamente ou não, todos os
processos criados por ele também são Se o grep ficar pronto antes de cat, ele deve
imediatamente cancelados. Contudo, nem no ser bloqueado até ter uma entrada para ser
Unix, nem no Windows funciona dessa maneira. executado. Outro motivo de bloqueio de
1.4 Hierarquia de Processos processo é quando a CPU resolve executar outr
o processo. Há várias razões para existirem esses
miniprocessos dentro de processos, chamados
Threads.

Muitas aplicações ocorrem múltiplas atividades

ao mesmo tempo. Algumas dessas atividades
podem ser bloqueadas de tempos em tempos. O
modelo de programação se torna mais simples
se decompomos uma aplicação em múltiplos
1.6 Implementação de Processos threads sequenciais que executam quase em
paralelo.
Para implementar o modelo de processos, o
sistema operacional mantém uma tabela (um Com os threads é possível ter a capacidade de
arranjo de estruturas) chamada de Tabela de entidades paralelas compartilharem de um
Processos (PCB – process control blocks), espaço de endereçamento e todos os seus
com uma entrada para cada processo. dados entre elas mesmas.

Essa entrada contém: Elas são mais fáceis (rápidas) de criar e

• informações sobre o estado do destruir que os processos, pois não tem
processo; qualquer recurso associados a elas.
• seu contador de programa;
• ponteiro da pilha; O uso de threads não resulta em ganho de
• alocação de memória; desempenho quando todos eles são CPU-bound.
• estados de seus arquivos abertos; No entando, quando há grande quantidade de
• informação sobre contabilidade; computação e de IO, os threads permitem que
• escalonamento; essas atividades se sobreponham e, desse
e tudo que tiver de ser salvo quando o processo modo, aceleram a aplicação.
for para o estado de pronto ou bloqueado, para
que ele possa ser iniciado depois. Os threads são úteis em sistemas com
múltiplas CPUs, para os quais o paralelismo real
é possível.
2. Threads

Em sistemas operacionais tradicionais, cada

processo tem um espaço de endereçamento e
um único thread de controle. Na verdade, isso
é quase uma definição de processo. Contudo,
frequentemente há situações em que é
desejável ter múltiplos threads de controle no Eles tornam possível manter a ideia de
mesmo espaço de endereçamento executando processos sequenciais que fazem chamadas de
em quase-paralelo, como se eles fossem sistema bloqueante (por exemplo, IO de disco)
processos separados (execeto pelo espaço de e mesmo assim conseguem obter paralelismo.
endereçamento compartilhado. Chamadas de sistema bloqueante tornam a
programação mais fácil, e o paralelismo
2.1 O uso de threads melhora o desempenho.
 computador. No primeiro caso (múltiplos
threads executando em paralelo), os threads
compartilham um mesmo espaço de
endereçamento e outros recursos. No último
(múltiplos processos executando em paralelo),
os processos compartilham um espaço físico de
memória, discos, impressoras e outros
2.2 O modelo de thread clássico recursos.

O modelo de processos é baseado em 2 Como os threads tem algumas das propriedades

conceitos independentes: do processo tem alguma das propriedades dos
• agrupamento de recursos; processos, eles são por vezes chamados de
• execução; processos leves (ligthweiht process).

Às vezes é útil separá-los; esse é o caso dos Multithread é também usado para descrever a
threads. situação em que se permite a existência de
múltiplos threads no mesmo processo. Algumas
Um processo apresenta um espaço de CPUs tem suporte de hardware diretoo para
endereçamento que contém o código e os dados multithread e peprmite a ocorrência de
do programa, bem como outros recursos chaveamento de threads em uma escala de
(arquivos abertos e etc). tempo de nanossegundos.

Outro conceito que um processo apresenta é o

thread de execução (thread). Este tem um
contador de programa que mantém o controle
de qual instrução ele deve executar em
seguida. Ele tem registradores, que contêm Na figura tem 3 processos tradicionais. Cada
suas variáveis de trabalho atuais. Apresenta um possui seu próprio espaço de
uma pilha que traz a história da execução, com endereçamento e um único thread de controle.
uma estrutura para cada rotina chamada mas
ainda não retornada. Apesar de um thread ter
de executar em um processo, ambos – o thread
e seu processo – são conceitos diferentes e
podem ser tratados separadamente.

Processos são usados para agrupar recursos; Na figura tem um único processo com 3
threads são entidades escalonadas para a threads de controle.
execução sobre a CPU.
Contudo, em ambos os casos há 3 threads. Na
O que os threads acrescentam ao modelo de primeira cada um deles opera em um espaço de
processo é permitir que múltiplas execuções endereçamento diferente; No segundo, todos
ocorram no mesmo ambiente do processo, com os 3 threads compartilham o mesmo espaço de
um grande grau de independência uma da outra. endereçamento.
Ter múltiplos threads executando em paralelo
em um processo é análogo a múltiplos processos Threads distintos em um processo não são tão
executando em paralelo em um único
independentes quanto processos distintos. Cada thread geralmente chama rotinas
Todos os threads tem exatamente o mesmo diferentes resultando uma história de
espaço de endereçamento, o que significia que execução diferente. Por isso é que o thread
eles compartilham as mesmas variáveis globais. precisa ter sua própria filha.
Como cada thread pode ter acesso a qualquer
endereço de memória dentro do espaço de Na execução de múltiplos threads, os
endereçamento do processo, um thread pode processos normalmente iniciam com um único
ler, escrever ou até mesmo apagar thread. Esse thread tem a capacidade de criar
completamente a pilha de outro thread. Além novos threads chamadno uma rotina de
também de compartilhar o mesmo conjunto de biblioteca – exemplo THREAD_CREATE.
arquivos abertos, processos filhos e etc.
Quando um thread termina seu trabalho, um
Então na primeira figura seria usada quando os thread pode terminar sua execução chamando a
3 processos fossem essencialmente rotina de biblioteca THREAD_EXIT.
descorrelacionados.
Uma chamada de rotina THREAD_JOIN
Na segunda, seria apropriada quando os 3 bloqueia o thread que executou a chamada até
threads fizessem realmente parte da mesma que um thread (específico) tenha terminado.
tarefa e cooperassem ativa e intimamente uns
com os outros. Outra chamada de rotina é a THREAD_YIELD
que permite que um outro thread desista
Os itens da primeira coluna são propriedades voluntariamente da CPU para deixar outra
dos processos. O processo é a unidade de thread executar.
gerenciamento de recursos, e não o thread. O
conceito de thread é a capacidade, para 2.3 Threads POSIX
múltiplos threads de execução, de
compartilahr um conjunto de recursos, de Possibilita criar programas com threads
forma que eles podem cooperar na realização portáteis. Padronizado pelo IEEE sobre o
de uma tarefa. 1003.1C. O pacote de threads que ele define é
chamado de Pthreads. A maioria dos sistemas
Assim como em processos tradicionais UNIX o suporta.
(processo com apenas um thread), um thread
pode estar em um dos vários estados: pronto,
executando, bloqueado ou finalizado.

Cada thread tem sua própria pilha. Cada pilha

de thread contém uma estrutura para cada
rotina chamada, ma que ainda não retornou.
Essa estrutura possui as variáveis locais da
rotina e o endereço de retorno para usá-lo
quando a rotina chamada terminar.
Todos os pthreads tem certas propriedades.
Cada um tem um identificador, um conjunto de
registros (inclusive o contador de programa), e
um conjunto de atibutos, que são armazenados
em uma estrutura.
2.4 Implementação de threads no espaço do criação ou a destruição atualizando a tabela de
usuário threads do núcleo.

Há 2 modos principais de implementar um A tabela de threads do núcleo contém os

pacote de threads: registradores, o estado e outras informações
• no espaço do usuário; de cada thread. As informações são a smesmas
• no núcle; dos threads de usuário, mas estão agora no
Pode ser feita de uma forma híbrida também. núcleo, e não no espaço do usuário.

Quando os threads são gerenciados no espaço Quando um thread é bloqueado, é opção do

do usuário, cada processo precisa de sua núcleo executar outro thread od mesmo
própria tabela de threads para manter o processo (se algum estiver pronto) ou um
controle dos threads naquele processo. Essa thread de outro processo. Com os threads de
tabela é análoga à tabela de processos do usuário, o sistema de tempo de execução
núcleo, exceto por manter o controle apenas mantém os threads de seu próprio processo
das propriedades do thread, como o contador executando até que o núcleo retire a CPU dele
de programa, o ponteiro de pilham os (ou até que não haja mais threads prontos para
registradores, o estado e assim por diante. executar).

Threads de usuário tem outras vantagens como Por causa do custo relativamente maior de
permitir que cada processo tenha seu próprio criar e destruir threads de núcleo, alguns
algoritmo de escalonamento personalizado. sitemas adotam uma abordagem
ambientalmente correta e reciclam seus
Threads de usuário apresentam melhor threads. Ao ser destruído, um thread é
desempenho. marcado como não executável, mas suas
estruturas de dados no núcleo não são
A chamada de sistema SELECT permite a quem afetadas. Depois, quando for preciso criar um
chama, saber se um futuro READ bloqueará. Se novo thread, um thread antigo será reativado,
causar bloqueio, a chamada não será feita, e economizando, assim, alguma sobrecarga. A
outro thread será executado. O código que reciclagem de threads também é possível para
envolve a chamada de sistema para fazer a threads de usuário, mas como necesse caso a
verificação é chamado de jaqueta (jacket) ou sobrecarga do gerenciamento do thread é
wrapper. muito menor, há menos incentivo para isso.

O custo de criação e exclusão de threads no

2.5 Implementação de threads no núcleo núcleo é muito alto.

Consideremos agora que o núcleo saiba sobre Só para lembrar. Os sinais são enviados para os
os threads e os gerencia. Não é necessário um processos, não para threads, pelo menos no
istema de tempo de execução. Não há também, modo clássico.
nenhuma tabela de threads em cada processo.
Em vez disso, o núcleo tem uma tabela de
threads que acompanha todos os threads no 2.6 Implementações Híbridas
sistema. Quando um thread quer criar um novo
thread ou destruir um já existente, ele faz Vários modos de tentar combinar as vantagens
uma chamada ao núcleo, que realiza então a dos threads de usuário com os threads de
núcleo tem sido investigados. Um deles é usar 2.8 Threads Pop-Up
threads de núcleo, e então, multiplexar
threads de usuário sobre algum ou todos os A chegada de uma mensagem faz com que o
threads de núcleo. Assim o programador sistema crie um novo thread para lidar com a
decide quantos threads de núcleo usar e mensagem. Esse thread é chamado thread
quantos threads de usuário multiplexar sobre pop-up.
cada um.

Com essa abordagem, o núcleo, sabe apenas

sobre os threads de núcleo e escalona-os.
3. Comunicação entre processos
Alguns desses threads podem ter multiplexado
diversos threads de usuário. Estes são criados,
Frequentemente processos precisam se
destruídos e escalonados do mesmo modo que
comunicar com outros.
threads de usuário em um processo que
executa em um sistema operacional sem
3.1 Condições de Corrida
capacidade multithread. Nesse modelo, cada
thread de núcleo possui algum conjunto de
São situações nas quais dois ou mais processos
threads de usuário que aguarda sua vez para
estão lendo ou escrevendo algum dado
usá-lo.
compartilhado e cujo resultado final depende
de quem executa precisamente e quando. A
depuração de programas que contenham
2.7 Ativações do Escalonador
condições de corrida não é nada divertida. Os
resultados da maioria dos testes não
Threads de núcleo são melhores que threads
apresentam problemas, mas uma hora, em um
de usuário, mas são mais lentos.
momento raro, algo estranho e inexplicável
acontece.
Ativações do Escalonador servem para imitar
a funcionalidade dos threads de núcleo – porém
com melhor desempenho e maior flexibilidade –
3.2 Regiões Críticas
em geral associados aos pacotes de threads de
usuário.
Para evitar as condições de disputa deve-se
impedir que mais de um processo leia e escreva
Quando são usadas ativações do escalonador, o
ao mesmo tempo na memória compartilhada. Em
núcleo atribui um certo número de
outras palavras, precisamos de exclusão mútua
processadores virtuais a cada processo e deixa
(mutual exclusion), isto é, algum modo de
o sistema de tempo de execução (no espaço do
assegurar que outros processos sejam
usuário) alocar os threads aos processadores.
impedidos de usar uma variável ou arquivo
compartilhado que já estiver em uso por um
processo. chaveada de processo em processo somento
como um resultado da interrupção do relógio ou
A parte do programa em que há acesso à de outra interrupção. Com as interrupções
memória compartilhada é chamada de Região desligadas, a CPU não será maiis chaveada para
Crítica ou Seção Crítica. O ideial é que nunca outro processo. Asssim, uma vez que tenha
dois processos estivessem em suas regiões desabilitado as interrupções, um processo pode
críticas ao mesmo tempo, pois assim as verificar e atualizar a memória compartilhada
disputas seriam evitadas. sem temer a intervenção de outro processo.

Embora essa solução impeça as condições de Em processadores multicore, desabilitar

disputa, isso não é suficiente para que interrupções de uma CPU não impede que
processos paralelos cooperaem correta e outras CPUs interfiram nas operações que a
eficientemente usando dados compartilhados. primeira CPU está executando. Assim esquemas
Precisamos satisfazer 4 condições para chegar mais sofisticados são necessários.
a uma boa solução:

1. Dois processos nunca podem estar Variáveis do tipo trava (lock)

simultaneamente em suas regiões críticas.
É uma solução de software que considera que
2. Nada pode ser afirmado sobre a velocidade hava uma única variável compartilhada (trava),
ou subre o número de CPUs. contendo o valor 0. Para entrar em sua região
crítica, um processo testa antes se há trava,
3. Nenhum processo executando fora de sua verificando o valor da variável trava. Se trava
região crítica pode bloquear outros processos. for 0, o processo alterar essa variável para 1 e
entra na região crítica. E trava já estivar com o
4. Nenhum processo deve esperar eternamente valor 1, o processo simplesmente aguardará até
para entrar em sua região crítica. que ela se torne 0.

Se dois processos fizerem isso ao mesmo

3.3 Exclusão mútua com espera ociosa tempo, continuará ocorrendo a disputa.

Nesta seção estudaremos várias alteranativas

para realizar exclusão mútua, de modo que, Chaveamento Obrigatório
enquanto um processo estiver ocupado
atualizando a memória compartilhada em sua Testa continuamente uma variável até que
região crítica, nenhum outro processo cause algum valor apareça. É chamada de Espera
problemas invadindo-a. Ociosa (Busy Waiting). A espera ociosa
deveria em geral ser evitada, já que gasta
Desabilitando Interrupções tempo de CPU. Somente quando há uma
Em um sistema de processador único, a solução expectativa razoável de que a espera seja
mais simples é aquela em que cada processo breve é que ela é usada. Uma variável de trava
desabilita todas as interrupções logo depois de que usa a espera ociosa é chamada de Trava
entrar em sua região crítica e as reabilita Giratório (spin lock).
imediatamente antes de sair dela. Com as
interrupções desabilitadas, não pode ocorrer
qualquer interrupção de relógio. A CPU é
Solução de Peterson relacionadas é totalmente executado sem
interrupções ou não é executado em absoluto,
Combina a ideia de alternar a vez (com a são extremamente importantes em muitas
variável turn) com a ideia das variáveis de outras áreas da computação.
trava e de advertência.
Existem 2 operações, down e up
(generalizações de sleep e wakeup,
Instrução TSL respectivamente).

Requer um pequeno auxílio do hardware.

3.6 Mutexes
Ela impede o acesso ao barramento de memória
para proibir que outras CPUs tenham acesso à Quando não é preciso usar a capacidade do
memória enquanto ela não terminar. semáforo de contar, lança-se mão de uma
versão simplificada de semáforo, chamada
mutex (mutual exclusion).
3.4 Dormir e Acordar
Mutexes são adequados apenas para gerenciar
A solução de Peterson e a solução TSL ou a exclusão mútua de algum recurso ou parte de
XCHG são corretas mas ambas apresentam o código compartilhada. São fáceis de
defeito de precisar da espera ociosa. Em implementar e eficientes, o que os torna
essência, o que essas soluções fazem é: quando especialmente úteis em pacotes de threads
quer entrar em sua região crítica, um processo implementados totalmente no espaço do
verifica se sua entrada é permitida. Se não usuário.
for, ele ficará em um laço esperando até que
seja permitida a entrada. Esses métodos Um mutex é uma variável que pode estar em um
gastam tempo de CPU, mas também pode ter dos 2 estados seguintes:
efeitos inesperados. • desimpedido (valor 0);
• impedido (qualquer outro valor);
Sleep é uma chamada de sistema que faz com
que o processo que a chama durma. Quando um trhead (ou processo) precisa ter
acesso a uma região crítica, ele chama
Wakeup faz com que um processo seja mutex_lock. Se o mutex estiver desimpedido
acordado. (indicando que a região crítica está disponível),
a chamada proseguirá e o thread que chamou
mutex_lock ficará livre para entrar na região
3.5 Semáforos crítica.

Garante que uma vez iniciada uma operação de Se o mutex já estiver impedido, o thread que
semáforo, nenhum outro processo pode ter chamou mutex_lock permanecerá bloqueado
acesso ao semáforo até que a operação tenha até que o thread na região crítica termine e
terminado ou sido bloqueada. As ações chame mutex_unlock. Se múltiplos threads
atômicas dos semáforos, resolve os problemas estiverem bloqueados sobre o mutex, um deles
de sincronização e evita condições de corrida. será escolhido aleatoriamente e liberado para
adquirir a trava.
Ações atômicas, em que um grupo de operações
Os mutexes podem ser implementados pacote. Os processos podem chamar as rotinas
facilmente no espaço de usuário, se houver uma em um monitor quando quiserem, mas não
instrução TSL ou XCHG disponível. podem ter acesso direto às estruturas internas
de dados ao monitor a partir de rotinas
Mutex no pthread declaradas fora dele.
Os pthreads fornecem várias funções que
podem ser usadas para sincronizar threads. O
mecanismo básico usa uma variável mutex, que 3.8 Troca de Mensagens
pode ser travada ou destravada, para proteger
uma região crítica. A troca de mensagens é um método de
comunicação entre processos que usa 2
primitivas
• send
• receive
que assim como os semáforos mas
diferentemente dos monitores, são chamadas
de sistema e não construções de linguagem.
Além dos mutexes, os pthreads oferecem um
segundo mecanismo de sincronização: Variáveis Então, a conclusão é que Troca de Mensagens
de Condição. Os mutexes são úteis para e Semáforos são chamadas de sistema.
permitir ou bloquear o acesso a uma região
crítica. As variáveis de condição permitem que Monitores são construções de linguagem.
os threads bloqueiem em virtude de alguma
condição não satisfeita. Quase sempre os dois Para que haja prevenção de perda de pacotes,
métodos são usados juntos. pacotes duplicados, principalmente se os
comunicantes estiverem em locais distintos de
uma rede são as confirmações de recebimento
(acknowledgement). Se uma confirmação
chegar duplicada, pelo número de sequência do
pacote é possível saber se aquele pacote já
chegou ou não.

O processo de troca de mensagens é mais lento

As variáveis de condição (à diferença dos
que uma operação de semáforo ou entrar em
semáforos) não tem memória. Se um sinal é
um monitor.
enviado para uma variável de condição pela qual
nenhum thread está esperando, o sinal é
Caixa Postal: Existem variações possíveis do
perdido.
mecanismo de troca de mensagens. Um tópico é
a forma que as mensagens são endereçadas. Um
meio para isso é atribuir a cada processo um
3.7 Monitores
endereço único e fazer as mensagens serem
endereçadas aos processos. Um outro modo é
É uma unidade básica de sincronização de alto
inventar uma nova estrutura de dados, chamada
nível. Um monitor é uma coleção de rotinas,
caixa posta. Uma caixa posta é um local para
variáveis e estruturas de dados, tudo isso
armazenar temporariamente um certo número
agrupado em um tipo especial de módulo ou
de mensagens, normalmente especificado
quando ela é criada. Quando as caixas postais por meio da colocação de uma barreira no final
são usadas, os parâmetros de endreço nas de cada fase. Quando alcança a barreira, um
chamadas send e receive são as caixas postais, processo permanece bloqueado até que todos
não os processos. Ao tentar enviar para uma os processos alcancem a barreira.
caixa posta que esteja cheia, um processo é
suspenso até que uma mensagem seja removida
daquela caixa postal e dê lugar a uma nova.
Rendezvous: Outro extremo das caixas postas
é eliminar todo o armazenamento temporário.
Quando se opta por esse caminho, se o send é
emitido antes do receive, o processo emissor
permanece bloqueado até que ocorra o receive,
momento no qual a mensagem pode ser copiada
diretamente do emissor para o receptor, sem
armazenamento intermiediário. Da mesma 4. Escalonamento
maneira, se o receive é emitido antes, o
receptor é bloqueado até que ocorra um send. Escalonador é a parte do sistema operacional
Essa estratégia é chamada de redezvous. que faz a escolha de qual processo ou thread
vai ser executado no processoador. O
O rendezvous é mais fácil de implementar que algoritimo que ele usa é o algoritmo de
um esquema de armazenamento de mensagens, escalonamento.
mas é menso flexível, pois o emissor e o
receptor são forçados a executar de maneira
interdependete. 4.1 Introdução ao escalonamento

A troca de mensagens é bastante usada em CPU-Bound: São processos que passam a maior
sistema de programação paralela. Um sistema parte do tempo computando. Também são
de troca de mensagens bem conhecido é o MPI chamados de compute-bound ou processos
(message-passing interface) – interface de limitados pela cpu.
troca de mensagens.
IO Bound: São processos que passam a maior
parte do tempo esperando o IO. Também são
3.9 Barreiras chamdas de processos limitados pela IO.

A medida que as CPUs se tornam mais rápidas,

É o último mecanismo de sincronização.
os processos tendem a ficar mais limitados por
ATENTAR QUE OS ANTERIORES SÃO IO. Isso ocorrer porque as CPUs estão ficando
MECANISMOS DE SINCRONIZAÇÃO!!!!! muito mais rápidas que os discos.

É dirigido aos grupos de processos em vez de Os algoritmos de escalonamento podem ser

situações que envolvem dois processos do tipo divididos em 2 categorias quanto ao modo como
produtor-consumidor. Algumas aplicações são tratam as interrupções:
divididas em fases e tem como regra que • não preemptivo;
nenhum processo pode abançar para a próxima • preemptivo;
fase até que todos os processos estejam
prontos a fazê-lo. Isso pode ser conseguido
Não preemptivo: escolhe um processo para
Utilização de CPU: Manter a CPU ocupada o tempo todo;
executar e, então, o deixa executar até que
Tempo de Resposta: Responder rapidamente às
seja bloqueado (à espera de IO ou de um outro requisições.
Sistemas
processo) ou até que ele voluntariamente libere Interativos
Proporcionalidade: Satisfazer às expectativas dos
a CPU. Mesmo que ele execute por horas, não usuários;
será compulsoriamente suspenso. Na verdade, Cumprimento dos Prazos: Evitar a perda de dados;
Sistemas
nenhuma decisão de escalonamento é tomada de Tempo
Previsibilidade: Evitar a degradação da qualidade em
durante as interrupções de relógio. Depois que Real
sistemas multimídia;
o processamento da interrupção de relógio
termina, o processo que estava executando 4.2 Escalonamento em sistemas em lote
antes da interrupção prossegue até acabar, a
menos que um processo de prioridade mais alta
esteja esperando por um tempo de espera Primeiro a Chegar, Primeiro a Ser Servido
agora satisfeito.
É o mais simples algoritmo de escalonamento
Preemptivo: Escolhe um processo e o deixa em
não preemptivo, Primeiro a Chegar, Primeiro a
execução por um tempo máximo fixado. Se ser Servido (FCFS – first come, first served).
ainda estiver executando ao final desse Com esse algoritmo, a CPU é atribuída aos
intervalo de tempo, o processo será suspenso e
processos na ordem em que eles a requisitam.
o escalonador escolherá outro processo paraO processo não é interrompido porque está
executar. O escalonador preemptivo requer asendo executado há muito tempo. À medida que
existência de uma interrupção de relógia aochegam as outras tarefas, eles são
fim do intervalo de tempo para que o controle
encaminhados para o fim da fila. Quando o
sobre a cpu seja devolvido ao escalonador. Se
processo em execução é bloqueado, o primeiro
não houver relógio disponível, o escalonador
processo na fila é o próximo a executar.
não preemptivo será a única opção. Quando um processo bloqueado fica pronto –
assim como uma tarefa que acabou de chegar –
Para diferentes ambientes, são necessários ele é posto no fim da fila.
diferentes algoritmos de escalonamento. 3
ambientes merecem distinção:
• Lote;
• Interativo; Tarefa mais curta primeiro (SJF)
• Tempo real;
Também é um outro algoritmo não preemptivo,
Alguns objetivos dependem do ambiente (lote, que supões como previamente conhecido todos
interativo ou tempo real), mas há também os tempos de execução. O algoritmo aloca a
aqueles que são desejáveis para todos os casos. tarefa mais curta primeiro (Shortest Job
First – SJF).
Justiça: Dar a cada processo uma porção justa da CPU.;

Todos os Aplicação da Política: Verificar se a política

sistemas estabeleceida é cumprida;

Equilíbrio: Manter ocupadas todas as partes do sistema;

Sistemas Vazão (throughput): Maximizar o número de tarefas

em Lote por hora;
Tempo Média de Resposta para A:
Tempo de Retorno: Minimizar o tempo entre a (8 + 12 + 16 + 20) / 4 = 14
submissão e o término;
 tabelas, carregar e descarregar a memória
Tempo Médio de Resposta em SJF: cache etc.
(4+8+12+20) / 4 = 11
Adotar um quantum muito curto causa muitos
O SJF é adequado somente para situações em chaveamentos de processo e reduz a eficiência
que todas as tarefas estejam disponíveis da cpu, mas um quantum muito longo pode gerar
simultaneamente. uma resposta pobre às requisições interativas
curtas.

Próximo de menor tempo restante Escalonamento por Prioridades

Uma versão preemptiva da tarefa mais curta A cada processo é atribuída uma prioridade, e
primeiro é o próximo de menor tempo ao processo executável com a prioridade mais
restante (shortest maining time next). Com alta é permitido executar.
esse algorimo, o escalonador sempre escolhe o
processo cujo tempo de execução retante seja Para evitar que processos de alta prioridade
o menor. Novamente, o tempo de execução executem indefinidamente, o escalonador pode
deve ser previamente conhecido. Quando chega reduzir a prioridade do processo em execução
uma nova tarefa, seu tempo total é comparado a cada tique de relógio. Outra possibilidade é
ao tempo restante do processo em curso. Se, atribuit um quantum máximo que ele pode ser
para terminar, a nova tarefa precisar de menos executado. Quando o quantum esgotar, será
tempo que o processo corrente, então esse dada a oportunidade para que o próximo
será suspenso e a nova tarefa será iniciada. processo com prioridade mais alta execute.
Esse esquema permite que novas tarefas
curtas obtenham um bom desempenho. Comando NICE (UNIX) faz com que o usuário
possa diminuir voluntariamente a prioridade de
seu processo.
4.3 Escalonamento em Sistemas Interativos
O algoritmo executa todos da classe com maior
Esses sistemas são comuns em computadores prioridade, quando não existir mais nenhum
pessoais, serivodres e outros tipos de sistemas processo nessa classe, ele pega da classe de
também. prioridade abaixo e assim por diante. Se as
prioridades não forem ajustadas, as classes de
Escalonamento por Chaveamento Circular prioridade mais baixas poderão todas morrer
(Round – Robin) de fome.

Esse algoritmo circular, a cada processo é

atribuído um intervalo de tempo, o seu Filas Múltiplas
quantum, no qual ele é permitido executar. Se
ao final do quantum, o processo ainda estiver Os processos na classe de prioridade mais alta
executando, a cpu sofrerá preempção e será eram executados por um quantum. Os
dada a outro processo. processos na classe seguinte de prioridade
mais alta executava por 2 quantus. Os
Chaveamento de Processo (ou Contexto): é o processos na próxima classe executavam por
processo de salvar e carregar registradores e quatro quantuns e assim por diante. Se um
mapas de memória, atualizar várias listas e processo utilizasse todos os seus quantuns,
seria movido para uma classe inferior. Escalonamento por fração justa (fair-share)

À medida que o processo se aprofundasse mais A cada usuário é alocada uma fração da CPU, e
nas filas de prioridade, ele seria cada vez o escalonador escolhe os processos de modo
menos frequentemente executado, liberando a que garanta essa fração. Assim, se dois
CPU para processos interativos e rápidos. usuários tiverem 50% da CPU prometida a cada
um deles, cada um obterá os 50%, não
Próximo processo mais curto (shortest importando quantos processos eles tenham
process next) gerado.

Processos interativos geralmente seguem o

padrão de esperar por comando, executar 4.4 Escalonamento em sistemas de tempo real
comando, esperar por comado, executar
comando e assim por diante. Com isso é possível Um sistema de tempo real é aquele no qual o
realizar uma estimativa com base no tempo tem uma função essencial. Nesses
comportamento passado e saber qual é o sistemas, ter a resposta certa, mas tardia, é
processo mais curto. tão ruim quanto não ter nada.

A técnica de estimar o valor seguinte da série, Sistema de tempo real são em geral
tomando a média ponderada do valor sendo categorizados como:
medido e a estimativa anterior, é algumas
vezes chamada de AGING (envelhecimento). Tempo Real Crítico: Há prazos absolutos que
devem ser cumpridos;

Escalonamento Garantido Tempo Real não Crítico: No qual o

descumprimento ocasional de um prazo é
Faz promessas reais sobre o desempenho aos indesejável, contudo tolerável.
usuários. Uma promessa pode ser vista como a
seguinte: se hpuver n usuários conectados Em ambos os casos, o comportamento de tempo
enquanto você estiver trabalhando, você real é implementado dividindo-se o programa
receberá cerca de 1/n de CPU. em vários proessos cujo comportamento é
previamente conhecido. Esses processos tem
vida curta e podem executar em bem menos de
Escalonamento por loteria um segundo. Quando é detectado um evento
externo, o trabalho do escalonador é escalonar
A ideia é dar bilhetes de loteria aos processos, os processos de tal maneira que todos os
cujos prêmicos são vários recursos do sistema, prazos sejam cumpridos.
como tempo de CPU. Se houver uma decisão de
escalonamento, um bilhete de loteria será Os eventos aos quais um sistema de tempo real
escolhido aleatoriamente e o processo que tem pode precisar responder podem ser
o bilhete conseguirá o recurso. Pode ser categorizados ainda como:
aplicado alguns bilhetes extras a um processo • periódicos (ocorrem em intervalos
para aumentar sua probabilidade de vitória. regulares);

Os processos cooperativos podem trocar • aperiódicos (acontecem em modo

bilhetes entre si, se quiserem. imprevisível);
Um sistema de tempo real escalonável é um
sistema que tem de responder a múltiplos
fluxos de eventos periódicos.

Os algoritmos de escalonamento de tempo real

podem ser: estáticos ou dinâmicos.

Estáticos: tomam suas decisões de

escalonamento antes de o sistema começar a
executar. Só funciona quando há prévia
informação sobre o trabalho necessário a ser
feito e os prazos a serem cumpridos.

Dinâmicos: Fazem essas decisões em tempo de

execução. Não precisam de informação prévia.

4.5 Escalonamento de threads

Quando cada um dentre vários processos tem

múltiplos threads, ocorrem dois níveis de
paralelismo: processos e threads. Não existem
interrupções de relógio para multiprogramar
threads!! Os threads podem continuar
executando enquanto quiser.

Uma diferença importante entre os threads de

usuário e os threads de núcleo é o desempenho.
O chaveamento de thread com threads de
usuário usa poucas instruções de máquina. Para
os threads de núcleo, o chaveamento requer um
chaveamento completo do contexto, com
alteração do mapa de memória e etc. Por outro
lado, para os threads de núcleo, um thread
bloqueado pelo IO não suspende o processo
interior, como ocorre nos threads de usuário.

Os threads de usuário podem utilizar um

escalonador de threads específico para uma
aplicação.