sistemas_operacionais_unidade_02_processos_20110417

Prévia do material em texto

Sistemas Operacionais
Prof. Douglas Machado
professor@douglasmachado.com
www.douglasmachado.com
v. 20110417
NOTA DO AUTOR: esta apresentação está em sua versão BETA e está sendo
disponibilizada para você “as is”. Ainda não foi revisada, servindo apenas como
um resumo das aulas. .
Sistemas Operacionais
 Sobre o professor
 Pesquisador no NP2TEC/UNIRIO (desde 2009)‏
 Professor na FES/JF (desde 2007)‏
 Coordenador do curso de Tecnologia em Redes de 
Computadores da FES/JF (2010)
 Analista de sistemas em empresa privada (1999-2010)‏
 Certificado em Qualidade de Software (PROQUALITI)‏
 Mestrando em Informática (UNIRIO)
 Especialista em Melhoria de Proc. de Software (UFLA)‏
 Tecnólogo em Processamento de Dados (CES/JF)‏
 Técnico em Informática Industrial (UFJF/CTU)‏
Sistemas Operacionais
 Unidade II – Processos
• Conceito de Processo
• Estados de um processo
• Threads
• Comunicação entre Processos
• Sincronização entre Processos
Unidade II - Processos
 Objetivos
 Entender o conceito de processo
 Conhecer os componentes de um processo
 Conhecer os estados de um processo e suas transições
 Diferenciar os tipos de processos
Unidade II - Processos
 Introdução
 O conceito de processo é a base para a implementação de 
sistemas multiprogramáveis
 Um programa, ao ser executado, deve sempre estar associado
a um processo
 Trata-se da instância de um programa em execução (visão
simplificada)
Unidade II - Processos
 Por que o processador consegue executar
múltiplos processos?
 O processador não diferencia processos
 O processador apenas executa instruções
 Modo simplificado de funcionamento do processador:
1. O processador busca a instrução a ser executada na
memória principal
2. O processador armazena a instrução no registrador de 
instruções
3. O processador decodifica os bits da instrução
4. O processador executa a instrução
Unidade II - Processos
 Como o processador sabe o endereço da 
próxima instrução a ser executada?
Unidade II - Processos
 Como o processador sabe o endereço da próxima instrução a 
ser executada?
 Através do registrador PC
 O processador executa instruções sem tomar conhecimento de 
a qual programa se refere
 A responsabilidade por essa gerência é do sistema operacional
 É o SO que vai gerenciar a alternância de instruções na CPU 
(controle e segurança)
Unidade II - Processos
 Como um programa pode ter seu
funcionamento interrompido e retornar
exatamente do ponto onde parou?
Unidade II - Processos
 Como um programa pode ter seu funcionamento interrompido e 
retornar exatamente do ponto onde parou?
 Todas as informações referentes à execução do programa
precisam ser guardadas
 Essa é a base para a implementação da multiprogramação e 
da concorrência
 Quando um programa é interrompido e volta a funcionar, não
pode faltar nenhuma informação necessária à sua execução
Unidade II - Processos
 Podemos continuar conceituando processo
apenas como “um‏programa em execução”?
Unidade II - Processos
 Podemos continuar conceituando processo
apenas como “um‏programa em execução”?
 Uma definição mais ampla:
 Conjunto necessário de informações para que o sistema
operacional implemente a concorrência de programas
 Ambiente no qual um programa é executado, incluindo
 As informações sobre a execução
 A quantidade de recursos do sistema que cada programa
pode utilizar
 Espaço de endereçamento da memória principal
 Tempo de processador
 Área em disco
Unidade II - Processos
 A troca de um processo para outro no processador é chamada de 
mudança de contexto
 Em um sistema multiusuário, cada usuário tem seu programa 
associado a um processo
 O funcionamento de um programa pode variar de acordo com o 
processo em que é executado
Unidade II - Processos
 Que informações são necessárias para que
um programa tenha sua execução
interrompida e retomada?
Unidade II - Processos
 Entendendo a estrutura de um processo
 Um processo é formado, basicamente, por três partes
 Contexto de hardware
 Contexto de software
 Espaço de endereçametno
 Essas três partes contêm todas as informações necessárias à 
execução do programa
Unidade II - Processos
 Contexto de hardware
 Contém
 Registradores gerais da CPU
 Registradores de uso específico
 PC (program counter)
 SP (stack pointer)
 Registrador de status
 Processo em execução = contexto de hardware nos 
registradores do processador
 Quando um processo sai do processador as informações dos 
registradores são salvas no contexto de hardware do processo
Unidade II - Processos
 Exemplo de mudança de contexto
1. “Processo‏A”‏está‏executando
2. “Processo‏A”‏será‏interrompido‏para‏execução‏do‏“Processo‏
B”
3. SO‏salva‏registradores‏do‏“Processo‏A”
4. SO‏carrega‏registradores‏do‏“Processo‏B”
5. “Processo‏B”‏entra‏em‏execução
6. SO‏salva‏registradores‏do‏“Processo‏B”
7. SO‏carrega‏registradores‏do‏“Processo‏A”
8. “Processo‏A”‏entra‏em‏execução
Unidade II - Processos
 Contexto de software
 Armazena os limites e características dos recursos que podem 
ser alocados pelo processo
 Exemplo:
 Número máximo de arquivos abertos simultaneamente
 Prioridade de execução
 Tamanho do buffer para operações de E/S
 Algumas dessas características são determinadas no momento 
da criação do processo
 Outras podem ser alteradas mesmo depois que o processo já 
tenha sido criado
Unidade II - Processos
 Divide-se em três grupos
 Identificação
 Quotas
 Privilégios
Unidade II - Processos
 Identificação
 PID (process identification)
 Número que identifica um processo
 É através deste número que um processo é 
referenciado pelo SO
 UID (user identification)
 Número que identifica um usuário
 Todo processo tem a identificação de seu owner (o 
usuário ou processo que o criou)
 Util para mecanismos de segurança
Unidade II - Processos
 Quotas
 Limites de cada recurso do sistema que um processo pode 
alocar
 Exemplos
 Número máximo de arquivos abertos simultaneamente
 Tamanho máximo de memória principal que um 
processo pode alocar
 Tamanho máximo de memória secundária que um 
processo pode alocar
 Número máximo de operações de E/S pendentes
 Tamanho máximo do buffer para operações de E/S
 Número máximo de processos, subprocessos e threads 
que podem ser criados
Unidade II - Processos
 Privilégios
 Define as ações que um processo pode fazer
 Em relação a ele mesmo
 Em relação aos demais processos
 Em relação ao sistema operacional
Unidade II - Processos
 Ações em relação ao próprio processo
 Alteração das suas próprias características, como:
 Prioridade de execução
 Limites alocados na memória principal
 Limites alocados na memória secundária
 Ações em relação aos demais processos
 Alterações nas características de outros processos
Unidade II - Processos
 Ações em relação ao sistema operacional
 São os processos mais amplos e poderosos
 Estão relacionados à operação e à gerência do 
ambiente, como:
 Desativação do sistema
 Alteração de regras de segurança
 Criação de outros processos privilegiados
 Modificação de parâmetros de configuração do 
sistema
Unidade II - Processos
 Espaço de endereçamento
 É a área de memória pertencente ao processo
 Nela são armazenadas as instruções do programa e os seus 
dados
 Cada processo possui seu próprio espaço de endereçamento
 O sistema operacional deve proteger este espaço, de forma 
que outros processos não o usem
Unidade II - Processos
Contexto de software Contexto de Hardware Espaço de 
endereçamento
Nome Registradores gerais Endereços de memória 
principal alocados
PID Registrador PC
Owner (UID) Registrador SP
Prioridade de execução Registrador de status
Data/hora de criação
Tempo de processador
Quotas
Privilégios
Unidade II - Processos
 Estados de um processo
 Em sistemas multiprogramáveis os processos podem assumirdiferentes estados
 Os três estados mais importantes são
 Running (execução)
 Ready (pronto)
 Wait (espera)
Unidade II - Processos
 Running (execução)
 O processo está sendo executado pela CPU
 Apenas um processo pode estar na CPU
 Em sistemas multiprocessados:
 Um processo pode estar em execução em mais de uma 
CPU
 Mais de um processo pode estar em execução, em 
CPUs diferentes
Unidade II - Processos
 Ready (pronto)
 O processo está pronto para ser executado
 Vários processos podem estar no estado de pronto
 É o sistema operacional que estabelece a ordem e os 
critérios de uso do processador (política de escalonamento)
Unidade II - Processos
 Wait (espera)
 O processo está aguardando 
algum evento externo ou 
algum recurso para 
prosseguir o processamento
 Exemplo:
 O término de uma 
operação de E/S
 Uma determinada 
data/hora
 Em alguns sistemas é 
conhecido como blocked
(bloqueado)
Unidade II - Processos
 Mudanças de estado de um processo
 Pode ocorrer
 Voluntariamente (eventos gerados pelo próprio processo)
 Involuntariamente (eventos gerados pelo sistema 
operacional)
Unidade II - Processos
Pronto Execução
Execução Espera
Espera Pronto
Execução Pronto
Unidade II - Processos
 Após ser criado, o processo fica no estado de pronto
 O processo mudará para o estado de execução quando for 
determinado pelo sistema operacional (política de escalonamento)
Pronto Execução
Unidade II - Processos
 Essa mudança pode ser voluntária (ex.: operação de E/S)
 Também pode ser involuntária (quando o sistema operacional 
suspende a execução do processo)
Execução Espera
Unidade II - Processos
 Um processo nunca passa do estado de espera para o estado de 
executando automaticamente
 Enquanto um processo aguarda uma solicitação ou um recurso, 
ele fica em estado de espera
 Quando essa solicitação é atendida ou o recurso liberado, ele 
muda para o estado de pronto até que o sistema operacional o 
selecione para execução
Espera Pronto
Unidade II - Processos
 Ocorre quando a execução de um processo é interrompida (ex.: 
sua fatia de tempo terminou)
 O processo ficará em estado de pronto até que o sistema 
operacional o selecione para execução novamente
Execução Pronto
Unidade II - Processos
 Considerações sobre a mudança de estado do processo
 Pode acontecer de não haver memória suficiente para todos 
os processos
 Na mudança para os estados Pronto ou Espera, pode ser 
que o processo seja transferido para a memória secundária 
(swap out)
 Quando voltam para o estado Executando, são trazidos de 
volta para a memória principal (swap in)
 Em alguns sitemas operacionais também existem os 
estados new (criação) e exit (terminado)
Unidade II - Processos
Tipos de 
processo
CPU-bound I/O-bound Foreground Background
Unidade II - Processos
 Processos CPU-bound
 Ficam a maior parte do tempo nos estados de Execução e/ou 
Pronto
 Executam poucas operações de E/S
 Ex.: aplicações científicas
Unidade II - Processos
 Processos I/O-bound
 Fica a maior parte do tempo no estado de Espera
 Realiza muitas operações de E/S
 Ex.: processos que fazem muita leitura de disco (banco de 
dados) ou requerem muita interação com o usuário
Unidade II - Processos
 Processos foreground
 Permite a interação direta com o usuário (teclado, mouse, 
monitor...)
 Processos background
 Nâo existe a comunicação com o usuário durante sua 
execução
 Entradas e saídas comumente estão em arquivos
Unidade II - Processos
- Revisão
1 – Com base no que foi estudado, apresente uma definição para processo
2 – Você acha que a compreensão do conceito de processo tem alguma importância no
projeto de sistemas multiprogramáveis? Justifique sua opinião.
3 – Quais são as três partes que compõem um processo?
4 – Explique o que é o contexto de hardware de um processo e como ocorre a troca de
contexto.
5 – Descreva detalhadamente o que é o contexto de software de um processo
6 - Com base nos conceitos de contexto de hardware e contexto de software, responda:
podem existir dois processos iguais? Explique.
7 - Um processo no estado de pronto pode passar para o estado de aguardando?
8 – Descreva a mudança de estados de um processo a partir do momento que ele é criado
9 – Defina os possíveis estados de um processo
10 – Explique a diferença entre processos foreground e background
11 – Dê exemplos de aplicações CPU-bound e I/O-bound
Unidade II - Processos
 Threads
 Suponha‏um‏processo‏de‏“descarga”‏de‏um‏caminhão‏de‏
entregas
 Este caminhão contém 50 tvs que devem ser entregues em 
uma loja
 Uma única pessoa retira as 50 tvs e as coloca na calçada
 Após isto, essa pessoa transfere as tvs da calçada para o 
interior da loja
 Há como otimizar esse processo inserindo uma pessoa a 
mais? Como?
Unidade II - Processos
 Threads (cont.)
 Sim! 
 Enquanto uma pessoa coloca as tvs na calçada, a outra as 
leva para o interior da loja
 Podemos aplicar essa mesma solução no contexto de um 
processo de software?
Unidade II - Processos
 Threads (cont.)
 Sim! 
 Um mesmo processo pode executar mais de uma tarefa, de 
forma concorrente
 Esse é o princípio básico do ambiente multithread
Unidade II - Processos
 Threads (cont>)
 Relembrando: processos têm contexto de software, hardware e 
espaço de endereçamento próprios
 E os threads, como seriam?
Unidade II - Processos
 Threads (cont.)
 Threads também têm contexto de hardware próprios, mas 
compartilham o contexto de software e espaço de 
endereçamento
 São fluxos de execução distintos de um mesmo processo
 Pode ser imaginado como a função de um programa que tem 
“vida‏própria”
 Um mesmo programa pode ter partes diferentes de seu código 
sendo executadas de forma concorrente
Unidade II - Processos
 Quais seriam as vantagens e desvantagens do uso de 
threads?
Unidade II - Processos
 Principal vantagem: aumento de desempenho
 Principal desvantagem: complexidade na implementação, 
devido à comunicação e à sincronização entre os threads
Unidade II - Processos
 Ainda em relação às vantagens...
 O que seria mais rápido: a comunicação entre threads ou a 
comunicação entre processos?
Unidade II - Processos
 Ainda em relação às vantagens...
 O que seria mais rápido: a comunicação entre threads ou a 
comunicação entre processos?
 A comunicação entre threads, já que o espaço de 
endereçamento é compartilhado.
Unidade II - Processos
 Suponha um programa editor de textos
 Como esse programa pode ser beneficiado com o uso de 
multithread?
Unidade II - Processos
 Suponha um programa editor de textos
 Como esse programa pode ser beneficiado com o uso de 
multithread?
 Ex.: enquanto o usuário formata um texto, o programa está 
salvando o conteúdo em disco.
Unidade II - Processos
 Exemplo:
 Suponha a seguinte equação: X = (100x3) + (9/3) + (20-2)
 Como implementá-la através de um algoritmo?
Unidade II - Processos
 Exemplo:
 Suponha a seguinte equação: X = (100x3) + (9/3) + (20-2)
 Como implementá-la através de um algoritmo?
 Ex.:
PROGRAM EQUACAO;
VAR X: integer;
BEGIN
X := (100*3) + (9/3) + (20-2);
WRITELN (X);
END.
Unidade II - Processos
 Implementando a mesma solução, de forma paralela:
PROGRAM EQUACAO;
VAR X, A, B, C: integer;
BEGIN
PARBEGIN
A := (100*3);
B := (9/3);
C := (20-2);
PAREND;
X := A + B + C;
WRITELN (X);
END.
Unidade II - Processos
 Implementando a mesma solução, de forma paralela:
PROGRAM EQUACAO;
VAR X, A, B, C: integer;
BEGIN
PARBEGIN
A := (100*3);
B := (9/3);
C := (20-2);
PAREND;
X := A + B + C;
WRITELN (X);
END.
 Houve algum ganho nessa solução?
Unidade II - Processos
 Suponha outro problema:
PROGRAM EQUACAO;
VAR X, A, B, C, D: integer;
BEGIN
A := (100*3);
B := 2 * (A + 30);
C := (20-2);
D := (3 * B);
X := A + B + C + D;
END.
 Como implementá-lo através de paralelismo?Unidade II - Processos
 Suponha outro problema:
PROGRAM EQUACAO;
VAR X, A, B, C, D: integer;
BEGIN
A := (100*3);
B := 2 * (A + 30);
C := (20-2);
D := (3 * B);
X := A + B + C + D;
END.
 Como implementá-lo através de paralelismo?
 Se não tomarmos cuidado, teremos sérios problemas de 
sincronia! 
 Essa á a maior dificuldade de se implementar programação 
multithread
Unidade II - Processos
 Tipos de thread
 Threads em modo usuário
 São implementados pela aplicação (e não pelo sistema 
operacional)
 Depende da existência de uma biblioteca de rotinas
 O sistema operacional NÃO sabe da existência das 
threads (apenas dos processos)
Unidade II - Processos
 Quais seriam as principais vantagens desse tipo de thread?
Unidade II - Processos
 Quais seriam as principais vantagens desse tipo de thread?
 Esse tipo de thread funcionaria em um sistema 
monothread?
 E em relação às mudanças de estado de um processo?
Unidade II - Processos
 Quais seriam as principais vantagens desse tipo de thread?
 Independe do sistema operacional suportar threads
 Threads não precisam trocar de modo de acesso (usuário-
kernel-usuário)
 Threads em modo usuário são rápidos e eficientes
Unidade II - Processos
 E quais seriam as principais desvantagens?
Unidade II - Processos
 E quais seriam as principais desvantagens?
 O que aconteceria quando um thread fizesse com o que o 
estado‏de‏um‏processo‏entrasse‏em‏modo‏“espera”?
Unidade II - Processos
 E quais seriam as principais desvantagens?
 O que aconteceria quando um thread fizesse com o que o 
estado‏de‏um‏processo‏entrasse‏em‏modo‏“espera”?
 Nenhum outro thread seria executado...
 Para contornar esse problema, a biblioteca tem que possuir 
rotinas que não causem o bloqueio de um thread 
(transparente para o usuário e para o sistema operacional)
Unidade II - Processos
 Outro problema: interrupções
 É necessário interceptar e tratar os sinais das interrupções 
para que seja feita a troca de contexto do thread
Unidade II - Processos
 E os sistemas multiprocessados? Threads em modo usuário 
podem ser executados em mais de um processador?
Unidade II - Processos
 E os sistemas multiprocessados? Threads em modo usuário 
podem ser executados em mais de um processador?
 Não...‏pois‏o‏sistema‏operacional‏irá‏“enxergar”‏apenas‏o‏
processo
Unidade II - Processos
 Threads em modo kernel
 São implementados diretamente pelo SO
 São acionados através de chamadas a rotinas do sistema 
(system call)
 Essas system calls oferecem todas as funções de 
gerenciamento e sincronização
 O SO tem ciência da existência de threads
 As threads podem ser escalonadas individualmente
 E se o sistema for multiprocessado?
Unidade II - Processos
 E se o sistema for multiprocessado?
 Threads em modo kernel de um mesmo processo podem ser 
executados simultaneamente em diferentes processadores
Unidade II - Processos
 Quais seriam as desvantagens de threads em modo kernel?
Unidade II - Processos
 Quais seriam as desvantagens de threads em modo kernel?
 Por utilizarem system calls, mudanças no modo de acesso 
devem ser feitas (várias)
Unidade II - Processos
Implementação Operação 1 µs Operação 2 µs
Subprocessos 11.300 1.840
Threads em modo kernel 948 441
Threads em modo usuário 34 37
Unidade II - Processos
 Threads em modo híbrido
 Combina as vantagens da arquitetura de threads em modo 
usuário e kernel
 Um processo pode ter vários threads em modo kernel
 Cada thread em modo kernel pode ter vários threads em modo 
usuário
Unidade II - Processos
Thread modo kernel 1 Thread modo kernel 2
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
T
h
re
a
d
m
o
d
o
 u
s
u
á
ri
o
1
Modo 
usuário
Modo 
kernel
Pode 
haver a 
biblioteca
Unidade II - Processos
 Threads em modo híbrido: desvantagens?
Unidade II - Processos
 Threads em modo híbrido: desvantagens?
 Se um thread em modo usuário entrar em estado de espera, 
todo o thread em modo kernel ficará em espera
 Threads em modo usuário que quiserem ser executados em 
mais de um processador deverão estar em threads em modo 
kernel diferentes
Unidade II - Processos
 Como seria um modelo ideal?
Unidade II - Processos
 Como seria um modelo ideal?
 Facilidades dos threads em modo kernel
 Desempenho do modo usuário
 Esse é o modelo scheduler activations
 Os threads NÃO são divididos entre modo usuário e modo 
kernel
 São evitadas as mudanças no modo de acesso 
desnecessárias
 Há uma biblioteca responsável por gerenciar os modos de 
acesso
 Caso um thread fique em estado de espera, a própria 
biblioteca aciona outro thread (trabalhando de forma 
cooperativa com o kernel)
Unidade II - Processos
 Exercícios de revisão
1. Apresente uma definição para thread.
2. Diferencie thread de processo
3. Suponha que um programador está desenvolvendo uma aplicação para um ambiente 
monothread. Este programador deseja implementar concorrência nesta aplicação. 
Explique como isso é possível.
4. Explique quais são os principais problemas de se desenvolver aplicações concorrentes 
para ambientes monothread.
5. Explique o que você entendeu por thread. Cite as vantagens de um ambiente multithread.
6. Sabe-se que em um ambiente multithread o espaço de endereçamento é compartilhado 
entre os threads de um mesmo processo. Quais sãos as vantagens e desvantagens 
desse compartilhamento?
7. Faça uma comparação entre threads em modo usuário e trheads em modo kernel
8. Além dos threads em modo usuário e em modo kernel, há também o modo híbrido e o 
scheduler activations. Compare o modo híbrido com o scheduler activations.
Unidade II - Processos
 Exercícios de revisão (cont)
9. Apresente um exemplo de alguma aplicação que possa se beneficiar do uso de threads, 
descrevendo os possíveis threads dessa aplicação (fora do que foi dado como exemplo 
em sala de aula)
10. Agora que você compreendeu o conceito de threads, responda: como uma aplicação 
pode se beneficiar do uso de múltiplos processadores?
11. Suponha um ambiente cliente-servidor. Descreva que benefícios uma aplicação pode ter 
nesse tipo de ambiente.
Unidade II - Processos
 Sincronização e comunicação entre 
processos
Unidade II - Processos
 Objetivos
 Entender os problemas gerados pelo compartilhamento
de recursos
 Entender o conceito de condição de corrida
 Identificar condições críticas em um programa
 Entender o que é exclusão mútua
 Entender os conceitos de deadlock e starvation
 Entender os mecanismos de exclusão mútua
 Entender a diferença entre espera ocupada e bloqueio
 Avaliar as vantagens e desvantagens de cada mecanismo
Unidade II - Processos
 Entendendo a sincronização e a 
comunicação entre processos…
Unidade II - Processos
 Sobre a figura anterior, é importante
considerar:
 Ambos os processos compartilham o buffer
 Um processo só pode gravar dados no buffer se o buffer 
não estiver cheio
 Um processo só pode ler dados do buffer se tiver alguma
informação a ser lida
 Em resumo: ambos os processos precisam aguardar que
o buffer esteja pronto
Unidade II - Processos
 Mecanismo de sincronização
 Garantem a comunicação entre processos concorrentes
 Garantem o acesso a recursos compartilhados
Unidade II - Processos
 Problemas de compartilhamento de recursos
 Problema da conta corrente
PROGRAM Conta_Corrente;
.
.
READ (Arq_Contas, Reg_Cliente);
READLN (Valor_Dep_Ret);
Reg_Cliente.Saldo := 
Reg_Cliente.Saldo + Valor_Dep_Ret;
WRITE (Arq_Contas, Reg_Cliente);
.
.
END.
Unidade II - Processos
 Suponha que dois caixas precisem atualizar o saldo do 
cliente
Caixa Instrução Saldo arq. Valor 
dep/ret
Sado 
memória
1 READ 1.000 * 1.000
1 READLN 1.000 -200 1.0001 := 1.000 -200 800
2 READ 1.000 * 1.000
2 READLN 1.000 +300 1.000
2 := 1.000 +300 1.300
1 WRITE 800 -200 800
2 WRITE 1.300 +300 1.300
Unidade II - Processos
 Exclusão mútua
 Propõe o mapeamento de regiões críticas
 Regiões críticas: parte do código onde é feito o acesso
ao recurso compartilhado
 São utilizados protocolos de acesso à região crítica
Processo
Unidade II - Processos
Região crítica
Protocolo de entrada
Protocolo de saída
Unidade II - Processos
BEGIN
.
.
Entra_Regiao_Critica; (* Protocolo de entrada *)
Regiao_Critica;
Sai_Regiao_Critica; (* Protocolo de saída *)
.
.
END.
Unidade II - Processos
 Como resolver o problema apresentado para
o acesso ao arquivo de conta corrente?
Unidade II - Processos
 “Processo A”‏deseja atualizar o saldo de um cliente
 “Processo A”‏solicita acesso através de seu protocolo de 
acesso à região crítica (antes mesmo de ler o registro)
 O protocolo indica se há algum processo acessando o 
recurso
 Se o recurso estiver livre,‏o‏“Processo A”‏faz o acesso
 Se‏o‏“Processo B”‏tentar acessar o arquivo, o protocolo fará
com que ele aguarde pelo “Processo A”
 Ao terminar,‏o‏“Processo A”‏executa o protocolo de saída, 
sinalizando para os outros processos que o recurso está
livre
Unidade II - Processos
 Em resumo: o acesso ao recurso compartilhado deve se dar
de forma sincronizada
Unidade II - Processos
 Pergunta: acesso simultâneo a uma região crítica é o 
mesmo que execução simultânea?
Unidade II - Processos
 Segunda pergunta: quais problemas podem se originar da 
exclusão mútua?
Unidade II - Processos
 Starvation (espera indefinida)
 Nessa condição, um processo NUNCA consegue
executar sua região crítica
 Dessa forma, o processo nunca acessa o recurso
compartilhado
 Isso acontece porque…
 Muitos processos podem estar aguardando o recurso
 O sistema operacional irá escolher o processo que irá
acessá-lo
 Dependendo dos critérios de escolha, o starvation
pode ocorrer…
Unidade II - Processos
 Típicos critérios de escolha que podem gerar starvation
 Aleatório
 Por prioridade
 Por que?
Unidade II - Processos
 Aleatório: por ser randômico, um determinado processo
pode nunca ser escolhido
 Por prioridade: se a prioridade do processo for baixa, 
outros podem sempre ser mais prioritários
Unidade II - Processos
 Soluções para o problema do starvation
 Soluções de hardware
 Soluções de software
 Soluções baseadas em primitivas do sistema operacional
Unidade II - Processos
 Soluções de hardware
 Desabilitação de interrupções
 Instrução test-and-set
Unidade II - Processos
 Desabilitação de interrupções
 Apenas interrupções mudam o contexto de um processo
 Logo, se as interrupções forem desabilitadas, um 
processo terá acesso exclusivo ao recurso garantido
BEGIN
.
Desabilita_Interrupcoes;
Regiao_Critica;
Habilita_Interrupcoes;
.
END.
Unidade II - Processos
 Quais seriam os problemas desse mecanismo?
Unidade II - Processos
 Quais seriam os problemas desse mecanismo?
 Sem interrupções, não há multiprogramação
 Pior ainda: se um processo não reabilitar as 
interrupções…
 Vantagens:
 O próprio kernel pode necessitar executar uma operação
sem interrupções
Unidade II - Processos
 Instrução test-and-set
 Exemplo:
 Test-and-set (X, Y);
 O conteúdo de Y é movido par X
 Y recebe TRUE
Unidade II - Processos
 Muitos processadores possuem essa instrução especial
 Trata-se de uma instrução indivisível
 É especial por ser executada sem interrupção
 Dessa forma, é impossível que a variável X seja
manipulada por mais de um processo ao mesmo tempo
Unidade II - Processos
 Exemplo de aplicação
PROGRAM Test_and_set;
VAR Bloqueio : BOOLEAN;
PROCEDURE Processo_A;
VAR Pode_A : BOOLEAN;
BEGIN
REPEAT
Pode_A := true;
WHILE (Pode_A) DO
Test_and_set (Pode_A, Bloqueio);
Regiao_Critica_A;
Bloqueio := false
UNTIL false;
END;
PROCEDURE Processo_B;
VAR Pode_B : BOOLEAN;
BEGIN
REPEAT
Pode_B := true;
WHILE (Pode_B) DO
Test_and_set (Pode_B, Bloqueio);
Regiao_Critica_B;
Bloqueio := false
UNTIL false;
END;
BEGIN
Bloqueio := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Unidade II - Processos
 Soluções de software
 Foram propostos vários algoritmos para resolver os
problemas da exclusão mútua
 Primeiro algoritmo
 Segundo algoritmo
 Terceiro algoritmo
 Quarto algoritmo
 Algoritmo de Dekker
 Algoritmo de Peterson
 Algoritmo para exclusão mútua entre N processos
Unidade II - Processos
 Primeiro algoritmo
PROGRAM Algoritmo_1;
VAR Vez : CHAR;
PROCEDURE Processo_A;
BEGIN
REPEAT
WHILE (Vez = ´B´) DO (*nada*);
Regiao_critica_A;
Vez := ‘B’;
Processamento_A;
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
WHILE (Vez = ‘A’) DO (*nada*);
Regiao_critica_B;
Vez := ‘A’;
Processamento_B;
UNTIL false;
BEGIN
Vez := ‘A’;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Unidade II - Processos
 Primeiro algoritmo
 Este algoritmo resolve definitivamente o problema?
 Limitações:
 Apenas DOIS processos
 O recurso sempre é utilizado de maneira alternada, ou
seja, se um processo precisar mais do recurso do que
outro, ficará grande parte do tempo bloqueado
 Se ocorrer alguma falha em um dos processos e a 
variável “Vez”‏não for alterada, o outro processo
aguardará indefinidamente
Unidade II - Processos
 Segundo algoritmo
 Endereça as limitações do primeiro
 Principal problema do primeiro algoritmo: usar uma única 
variável‏global‏(“Vez”)
 Solução apresentada no segundo algoritmo: usar 
variáveis distintas (CA e CB) para cada processo.
PROGRAM Algoritmo_2;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
WHILE (CB) DO (*nada*);
CA := true;
Regiao_critica_A;
CA := false;
Processamento_A;
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
WHILE (CA) DO (*nada*);
CB := true;
Regiao_critica_B;
CB := false;
Processamento_B;
UNTIL false;
BEGIN
CA := false;
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Unidade II - Processos
 Segundo algoritmo
 Este algoritmo resolve os problemas apresentados?
 Apenas um: se ocorrer um problema FORA da região
crítica, o outro não ficará bloqueado.
 Limitações:
 Se ocorrer um problema dentro da região crítica, o 
outro processo ficará bloqueado
 Novo problema: a exclusão mútua é mesmo garantida?
Unidade II - Processos
Processo Instrução CA CB
A WHILE (CB) false false
B WHILE (CA) false false
A CA := true true false
B CB := true true true
A Regiao_critica_A true true
B Regiao_critica_B true True
 A exclusão mútua é garantida?
 NÃO!
Unidade II - Processos
 Terceiro algoritmo
 Tenta resolver o problema da exclusão mútua
apresentado no segundo algoritmo
 A atribuição das variáveis CA e CB são feitas antes do 
teste
PROGRAM Algoritmo_3;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
WHILE (CB) DO (*nada*);
Regiao_critica_A;
CA := false;
Processamento_A;
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true;
WHILE (CA) DO (*nada*);
Regiao_critica_B;
CB := false;
Processamento_B;
UNTIL false;
BEGIN
CA := false;
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Unidade II - Processos
 Terceiro algoritmo
 Este algoritmo resolve os problemas apresentados?
 Garante a exclusão mútua,‏mas…
Processo Instrução CA CB
A CA := true true false
B CB := true true true
A WHILE (CB) true true
Unidade II - Processos
 Quarto algoritmo
 Tenta resolver o problema do bloqueio indefinido do 
terceiro algoritmo
PROGRAM Algoritmo_4;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
WHILE (CB) DO
BEGIN
CA := false;
{pequeno intervalo
de tempo aleatório}
CA := true;
END;
Regiao_critica_A;
CA := false;
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true;
WHILE (CA) DO 
BEGIN
CB := false;
{pequenointervalo
de tempo aleatório}
CB := true;
END;
Regiao_critica_B;
CB := false;
UNTIL false;
END;
Unidade II - Processos
 Quarto algoritmo
 Este algoritmo resolve os problemas apresentados?
 Sim!
 Garante a exclusão mútua
 Não gera o bloqueio simultâneo dos processos
 Entretanto, ainda há uma pequena limitação, que
acontece na seguinte situação
 Tempo aleatório igual ou muito próximo
 CA e CB recebem “false”‏antes‏do‏loop‏terminar
 Nenhuma das regiões críticas será executada
Unidade II - Processos
 Algoritmo de Dekker
 A primeira solução!
 Garantiu a exclusão mútua
 Não inseriu nenhum problema adicional
 DESVANTAGEM: 
 Lógica complexa
Unidade II - Processos
 Algoritmo de Peterson
 Propôs uma solução mais simples do que Dekker
PROGRAM Algoritmo Peterson;
VARCA,CB: boolean;
Vez: CHAR;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
Vez := ‘B’;
WHILE (CB and Vez = ‘B’) DO 
(*nada*);
Regiao_Critica_A;
CA := false;
Processamento_A;
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true;
Vez := ‘A’;
WHILE (CA and Vez = ‘A’) DO 
(*nada*);
Regiao_Critica_B;
CB := false;
Processamento_B;
UNTIL false;
END;
BEGIN
CA := false;
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Unidade II - Processos
 Limitações do algoritmo de Dekker e Peterson:
 Ambos só suportam dois processos.
 Solução: novos algoritmos foram propostos para suportar
“N”‏processos
Unidade II - Processos
 Todos os algoritmos mostrados até então têm ainda uma
limitação:
 Quando um processo está executando sua região crítica, 
o que acontece com os DEMAIS processos?
 Ficam “testando”,‏em looping…
 Problema: processamento desnecessário
 Nome desta condição: espera ocupada (busy wait).
Unidade II - Processos
 Sincronização condicional
 Problema do produtor / consumidor ou do buffer limitado
 O processo “consumidor”‏não deve tentar ler um buffer 
vazio
 O processo “produtor”‏não deve tentar gravar um 
buffer cheio
 Resumindo: a sincronização entre os processo exige
também uma condição de acesso ao recurso
PROGRAM Produtor_consumidor_1;
CONST TamBuf = (*tam.qualquer*);
TYPE Tipo_Dado = (*t.qualquer*);
VAR Buffer : ARRAY [1.. TamBuf] 
OF Tipo_Dado;
Dado_1 : Tipo_Dado;
Dado_2 : Tipo_Dado;
Cont : 0..TamBuf;
PROCEDURE Produtor;
BEGIN
REPEAT
Produz_Dado (Dado_1);
WHILE (Cont = TamBuf) DO 
(*nada*);
Grava_Buffer (Dado_1, Buffer)
Cont := Cont + 1;
UNTIL false;
END;
PROCEDURE Consumidor;
BEGIN
REPEAT
WHILE (Cont = 0) DO (*nada*);
Le_Buffer (Dado_2, Buffer);
Consome_Dado (Dado_2);
Cont := Cont – 1;
UNTIL false;
END;
BEGIN
Cont := 0;
PARBEGIN
Produtor;
Consumidor;
PAREND;
END.
Obs.: a exclusão mútua da variável “Cont”‏não foi
considerada
Unidade II - Processos
 Sincronização condicional (cont.)
 Na solução para a sincronização condicional, o problema
da espera ocupada foi resolvido?
 Não!
 Solução: uso de semáforos e monitores
Unidade II - Processos
 Semáforos
 Trata-se de um tipo de variável
 Assume valores numéricos inteiros não-negativos
 Só pode ser manipulada através de duas instruções:
 DOWN: decrementa a variável
 UP: incrementa a variável
 Se o semáforo atinge o valor “0”‏(zero),‏o‏processo entra
em estado de espera
 Podem ser binários (0 e 1) ou contadores (qualquer valor
inteiro maior que zero)
 As instruções UP e DOWN são indivisíveis
 Seu uso depende do suporte da linguagem de 
programação
Unidade II - Processos
 Exclusão mútua: solução através do uso de semáforos
 Instrução DOWN: protocolo de entrada.
 Instrução UP: protocolo de saída.
 Semáforo = 0: recurso em uso.
 Semáforo = 1: recurso disponível.
 <colocar figura>
Unidade II - Processos
Processo deseja 
entrar na região crítica
Processo acessa a 
região crítica Fila de espera de 
processos
DOWN (S=1) DOWN (S=O)
UP (S) – processo sai 
da região crítica
Libera processo da fila 
de espera
Unidade II - Processos
 Exemplo de aplicação
PROGRAM Semaforo_1;
VAR s: Semaforo := 1;
PROCEDURE Processo_A;
BEGIN
REPEAT
DOWN (s);
Regiao_Critica_A;
UP (s);
UNTIL false;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
DOWN (s);
Regiao_Critica_B;
UP (s);
UNTIL false;
END;
BEGIN
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END. 
Obs.: o semáforo é inicializado com o valor 1, indicando que
nenhum processo está executando sua região crítica
Unidade II - Processos
 Sincronização condicional utilizando semáforos
 Lembrando: na sincronização condicional, um processo
“depende”‏do‏outro
 Ex.: um processo depende de uma operação de E/S de 
outro para continuar
Solicita
leitura
Lê 
dados
DOWN (Evento)
UP (Evento)
P
a
ra
le
lo
PROGRAM Semaforo_2;
VAR Evento : Semaforo := 0;
PROCEDURE Solicita_Leitura;
BEGIN
DOWN (Evento);
END;
PROCEDURE Le_Dados;
BEGIN
UP (Evento);
END;
BEGIN
PARBEGIN
Solicita_Leitura;
Le_Dados;
PAREND;
END.
Unidade II - Processos
 E o problema do produtor consumidor?
 Solução:
 Exclusão mútua
 Sincronização condicional
PROGRAM Produtor_Consumidor_2;
CONST TamBuf = 2;
TYPE Tipo_Dado = (*qualquer*);
VAR Vazio : Semaforo := TamBuf;
Cheio : Semaforo := 0;
Mutex : Semaforo := 1;
Dado_1 : Tipo_Dado;
Dado_2 : Tipo_Dado;
PROCEDURE Produtor;
BEGIN
REPEAT
Produz_Dado (Dado_1);
DOWN (Vazio);
DOWN (Mutex);
Grava_Buffer (Dado_1, Buffer);
UP (Mutex);
UP (Cheio);
UNTIL false;
END;
PROCEDURE Consumidor;
BEGIN
REPEAT
DOWN (Cheio);
DOWN (Mutex);
Le_Buffer (Dado_2, Buffer);
UP (Mutex);
UP (Vazio);
UNTIL false;
END;
BEGIN
PARBEGIN
Produtor;
Consumidor;
PAREND.
END.
Unidade II - Processos
 Problema dos filósofos
 Exemplo clássico de sincronização de processos
Unidade II - Processos
 CENÁRIO
 Cinco filósofos
 Cinco pratos
 Cinco garfos
 PROBLEMA
 O filósofo para de 
pensar para comer
 Cada filósofo precisa
de dois garfos para
comer (um à direita e 
outro à esquerda)
Unidade II - Processos
 Primeira tentativa de solução
PROGRAM Filosofo_1;
VAR Garfos : ARRAY [0..4] of Semaforo := 1;
I : INTEGER;
PROCEDURE Filosofo (I : INTEGER);
BEGIN
REPEAT
Pensando;
DOWN (Garfos[I]); // garfo da direita
DOWN (Garfos[(I+1) MOD 5]]; // garfo da esquerda
Comendo;
UP (Garfos[I]); // garfo da direita
UP (Garfos[(I+1) MOD 5]); // garfo da esquerda
UNTIL false;
END;
BEGIN
PARBEGIN
FOR I := 0 TO 4 DO
Filosofo(I);
PAREND;
END.
Unidade II - Processos
 Problema: 
 E se cada filósofo já estiver segurando 1 (um) garfo?
 Deaklock!
 Soluções:
a) Permitir que apenas quatro filósofos se sentem
simultaneamente
b) Permitir que um filósofo pegue um garfo apenas se o 
outro estiver disponível