Faculdade Pernambucana FAPE
Sistemas Operacionais
Prof. Flávio Gonçalves da Rocha
Comunicação entre Processos
Monitores

Deve-se ter
semáforos.
muito
cuidado
ao
utilizar
 Ex: código do produtor com os dois down invertidos,
ou seja, o down do mutex antes do down do empty.

Se o buffer estiver cheio o produtor é bloqueado com
mutex em 0
 O consumidor fazendo down no mutex também será
bloqueado resultando em deadlock

df
Para tornar mais fácil escrever programas foi
proposta uma primitiva de sincronização de
nível mais alto chamada de monitor.
Comunicação entre Processos
Monitores

Um monitor é uma coleção de variáveis, de
procedimentos e de estruturas de dados que
são agrupados em um tipo especial de módulo
ou de pacote.
 Os monitores facilitam o uso de semáforos
df
Comunicação entre Processos
Monitores
Um Monitor
df
Comunicação entre Processos
Monitores

Principais aspectos do uso de monitores
 Todas as regiões críticas não são codificadas dentro
df
do próprio processo, mas são transformadas em
procedimentos do monitor
 As estruturas de dados internas do monitor só podem
ser acessadas por seus procedimentos
 Quando
um
processo
referencia
dados
compartilhados ele chama um procedimento do
monitor
 Só um processo pode estar ativo em um monitor em
qualquer instante.
Comunicação entre Processos
Monitores
 Monitores são uma construção de linguagem de
programação
 Cabe ao compilador implementar a exclusão mútua

Implementar exclusão mútua é facil mas não é
suficiente, é preciso encontrar uma maneira de
bloquear os processos
 Para o controle de bloqueio são usadas variáveis de
condição

df
São variáveis associadas a condições que provocam a
suspensão ou ativação do processo dentro do monitor.
Comunicação entre Processos
Monitores
 São declaradas dentro do monitor

As variáveis de condições são usadas por dois
procedimentos especiais:
 wait(condicao): O monitor bloqueia o processo. Há
uma estrutura de dados associada que guarda as
informações do processo
 signal(condicao):
O monitor desbloqueia um
processo da fila associada à variável de condição
df
Comunicação entre Processos
Monitores
Implementações propostas quando ocorrer um
SIGNAL
 Solução de Hoare
 O processo que fez a chamada é imediatamente
bloqueado
 O processo recentemente desbloqueado passa a
executar.

Solução de Brinch Hansen
 O processo que fez a chamada conclui a operação
em curso
df
Comunicação entre Processos
Monitores

Solução de Brinch Hansen (Continuação)
 O processo recentemente desbloqueado aguarda
que nenhum processo esteja executando dentro do
monitor.
df
Comunicação entre Processos
Monitores
df
df
Um esboço do problema produtores e consumidores com monitores.
Só um procedimento de monitor está ativo por vez. O buffer tem N entradas.
Comunicação entre Processos
Passagem de Mensagem

df
Semáforos e monitores foram projetados para
resolver problemas da exclusão mútua em
uma ou mais CPUs, com memória
compartilhada/comum
 Para sistemas distribuídos estas soluções não
atendem, é preciso de algo mais: passagem
de mensagem
 A passagem de mensagem é um método de
comunicação interprocesso que utiliza duas
primitivas, SEND e RECEIVE, que, como os
semáforos e, ao contrário dos monitores são
chamadas de sistema.
Comunicação entre Processos
Passagem de Mensagem

Questões de Projeto para
Passagem de Mensagem
Sistemas
de
 Controle de erro (perda de mensagens ou do próprio
reconhecimento de entrega)
 Identificação dos processos
 Autenticação
 Desempenho
df
Comunicação entre Processos
Passagem de Mensagem
df
O problema dos produtores e dos consumidores com N mensagens
Escalonamento de Processos

Quando mais de um processo é executável,
cabe ao SO decidir qual executar primeiro. A
parte do SO que toma essa decisão é
chamada Agendador.
 O algoritmo que utiliza é chamado algoritmo de
agendamento.

Vários critérios vem à mente sobre o que
constitui um bom algoritmo de agendamento:
1. A imparcialidade
2. A eficiência
3. Tempo de resposta
df
4. Turnaround
Escalonamento de Processos
5. Throughput

Algumas
das
contraditórias
metas
descritas
são
 Para minimizar o tempo de resposta para usuários
interativos, o agendador não deve executar nenhum
trabalho de lote (isso violaria o critério 4)
 Qualquer algoritmo de agendamento que favorece
alguma classe de trabalho acaba prejudicando outra
classe de trabalho

df
Uma outra complicação para o agendador é
que os processos são únicos e imprevisíveis
 O uso de interrupção de relógio garante que nenhum
processo executará por muito tempo
Escalonamento de Processos

A estratégia de permitir que processos que são
logicamente executáveis sejam temporiamente
suspensos é chamada de agendamento
preemptivo.
 No agendamento não-preemptivo o processo executa
até concluir (antigos sistemas de lote)
df
Escalonamento de Processos
Agendamento Round Robin

Mais simples, mais antigo e mais utilizado
 Fácil de implementar
 A cada processo é atribuído um intervalo de
tempo, chamado quantum, durante o qual lhe é
permitido executar.
 Se o processo ainda está executando no fim do
df
quantum, é feita a preempção da CPU e ela é dada a
outro processo.
 Se o processo bloqueiou ou terminou antes de o
quantum ter passado, é feita a comutação da CPU
quando o processo bloqueia, naturalmente.
Escalonamento de Processos
Agendamento Round Robin
Próximo
Processo
Processo
atual
B
F
D
G
A
(a)
Processo
atual
F
df
D
G
A
B
(b)
Agendamento round robin. (a) Lista de processos executáveis.
(b) Lista de processos executáveis depois que B utiliza todo seu quantum.
Escalonamento de Processos
Agendamento Round Robin

Uma questão importante é o tamanho do
quantum
 Quantum muito pequeno gera muitas comutações de
processos e a eficiência da CPU é reduzida
 Quantum muito longo a resposta pode ser demorada
para curtas requisições interativas

df
Um quantum em torno de 100ms
freqüentemente um compromisso razoável.
é
Escalonamento de Processos
Agendamento por Prioridade

Processos podem ter prioridades diferentes
 A necessidade de levar em conta fatores
externos conduz ao agendamento por
prioridade.
 A cada processo é atribuído uma prioridade, e o
processo executável com a maior prioridade recebe
permissão para executar.

df
A prioridade de um processo em execução
pode ser diminuída a cada interrupção de
relógio para evitar que um processo execute
indefinidamente
Escalonamento de Processos
Agendamento por Prioridade

Alternativamente, a cada processo pode ser
atribuído um quantum máximo em que lhe é
permitido usar a CPU continuamente.
 Quando esse quantum é utilizado é dada uma
chance de executar ao próximo processo com maior
prioridade

df
As prioridades podem ser atribuídas aos
processos estática ou dinamicamente
Escalonamento de Processos
Agendamento por Prioridade

df
Muitas vezes é conveniente agrupar processos
em classes de prioridade e utilizar
agendamento por prioridade entre as classes,
mas agendamento round robin dentro da
classe.
Escalonamento de Processos
Agendamento por Prioridade
Cabeçalhos de Fila
Prioridade 4
Processos executáveis
(Maior Prioridade)
Prioridade 3
Prioridade 2
Prioridade 1
df
(Menor Prioridade)
Um algoritmo de agendamento com quatro classes de prioridade
Escalonamento de Processos
Múltiplas Filas

Útil em situações nas quais processos são
facilmente classificáveis em diferentes grupos
(Ex.: interativos e batch);
 Prioridades são atribuídas à classes de
processos (de acordo com o tipo de
processamento), cada qual com sua própria
fila de prontos com seu mecanismo de seleção
 Cada
fila pode ter diferentes necessidades de
escalonamento (algoritmo diferente);
df
Escalonamento de Processos
Múltiplas Filas
 Os processos devem ser previamente classificados
para serem enviados à fila correspondente.

Processos das classes de maior prioridade
recebem o processador
 Os processos das classes de menor prioridade só
receberão o processador se as filas de prontos das
outras classes (de maior prioridade) estiverem vazias
df
Escalonamento de Processos
Múltiplas Filas
df
Escalonamento de Processos
O Menor Job Primeiro (Shortest-Job-First)

Apropriado para o processamento de Jobs em
lote, para os quais o tempo de execução é
conhecido com antemão
 É um algoritmo não preemptivo no qual o job
na fila de espera com o menor tempo total
estimado de processamento é executado em
seguida.
 Esse algoritmo reduz o tempo médio de espera
sobre o algoritmo FIFO.
df
Escalonamento de Processos
O Menor Job Primeiro (Shortest-Job-First)
Agendamento FIFO
8
4
A
Tempo de
execução
4
B
8
C
12
4
Agendamento Menor Job Primeiro
4
4
4
8
D
B
16
Média de retorno:
(8+12+16+20)/4 = 14 minutos
df
20
C
4
D
8
A
12
20
Média de retorno:
(4+8+12+20)/4 = 11 minutos
Escalonamento de Processos
O Menor Job Primeiro (Shortest-Job-First)

Pode ser usado para processos interativos
também desde que seja feito estimativas do
tempo de execução do comando tomando por
base as execuções passadas.
 O algoritmo do job mais curto primeiro só é
ótimo quando todos os jobs estão disponíveis
simultaneamente.
df
Escalonamento de Processos
Escalonamento Dirigido à Política

Ás vezes acontece de um processo ter muitos
filhos que executam sob seu controle.
 É plenamente possível que o processo principal
tenha uma excelente idéia de quais de seus filhos
são os mais importantes (ou de tempo crítico) e quais
são menos.

df
Como os agendadores anteriores não aceita
qualquer entrada de processos de usuário
sobre decisões de agendamento, raramente, o
agendador faz a melhor escolha.
Escalonamento de Processos
Escalonamento Dirigido à Política

A solução é separar o mecanismo de
agendamento da política de agendamento.
 O algoritmo de agendamento é parametrizado de
alguma maneira, mas os parâmetros podem ser
preenchidos por processos de usuários.
 Ex: o kernel utiliza um algoritmo de agendamento por
prioridade, mas fornece uma chamada de sistema
por meio da qual um processo pode definir (e alterar)
as prioridades de seus filhos.
df
Escalonamento de Processos
Escalonamento Dirigido à Política

Mesmo que os pais não façam o agendamento eles
podem controlar em detalhe como seus filhos são
agendados.
 O mecanismo está no kernel, mas a política é
configurada por um processo de usuário.
df
Escalonamento de Processos
Agendamento de Dois Níveis

Se a memória principal disponível for
insuficiente, alguns dos processos executáveis
terão de permanceer no disco, inteiros ou em
parte.
 Carregar processo de disco é muito mais demorado
do que a comutação de um processo já em memória.
 Solução: usar um agendador em dois níveis.

df
O agendador de nível mais baixo fica
preocupado com fazer uma escolha entre os
processos executáveis que estão na memória
principal.
Escalonamento de Processos
Agendamento de Dois Níveis

O agendador de nível mais alto fica
preocupado com o movimento dos processos
de um lado a outro entre memória e disco.
a, b,
c, d
Processos
Na memória
principal
e, f,
g, h
b,c,
f,g
e, f,
g, h
Processos
no disco
a, b,
c, d
a, d,
e, h
(a)
(b)
(c)
df
Um agendador de dois níveis deve mover processos entre disco e memória e também eleger processos
para executar na memória. Três instantes diferentes de tempo são representados por (a), (b) e (c)
Escalonamento de Processos
Agendamento de Dois Níveis

Entre os critérios que o agendador de nível
mais alto poderia utilizar para tomar suas
decisões estão os seguintes:
 Quanto tempo se passou desde que o processo foi
df
levado para o disco ou para a memória?
 Quanto
tempo de CPU o processo teve
recentemente?
 Qual é o tamanho do processo? (Os pequenos não
atrapalham)
 Qual o nível de prioridade do processo?