Infra-Estrutura de Software
Processos, Threads, Concorrência
e Escalonamento
Tópicos
•
•
•
•
•
Processos
Threads
Concorrência
Comunicação interprocesso
Escalonamento
Criação de Processos
Principais eventos que levam à criação de
processos
1. Início do sistema
2. Execução de chamada ao sistema de
criação de processos
3. Solicitação do usuário para criar um novo
processo
4. Início de um job em lote
Término de Processos
Condições que levam ao término de
processos
1. Saída normal (voluntária)
2. Saída por erro (voluntária)
3. Erro fatal (involuntário)
4. Cancelamento por um outro processo
(involuntário)
Estados de Processos
• Possíveis estados de processos
– em execução
– bloqueado
– pronto
• Mostradas as transições entre os estados
Camadas de Processos
• Camada mais inferior de um SO estruturado por
processos
– trata interrupções, escalonamento
• Acima daquela camada estão os processos
sequenciais
Implementação de Processos (1)
Campos da entrada de uma tabela de processos
Implementação de Processos (2)
Esqueleto do que o nível mais baixo do SO
faz quando ocorre uma interrupção
Threads
O Modelo de Thread (1)
(a) Três processos, cada um com um thread
(b) Um processo com três threads
Threads: Motivação
Concorrência
• Problemas:
– Programas que precisam de mais poder
computacional
– Dificuldade de implementação de CPUs mais
rápidas
• Solução:
– Construção de computadores capazes de
executar várias tarefas simultaneamente
Problemas com Concorrência
• Não-determinismo
– x = 1 || x = 2
• Qual o valor de “x” após a sua execução?
• Dependência de Velocidade
– [[ f(); x = 1 ]] || [[ g(); x = 2 ]]
– O valor final de x depende de qual das funções,
f() e g(), terminar primeiro
• Starvation
– Processo de baixa prioridade precisa de um
recurso que nunca é fornecido a ele...
Hermano P. Moura
Problemas com Concorrência
(cont.)
• Deadlock
• Um sistema de bibliotecas só fornece o “nada consta”
para alunos matriculados e o sistema de matricula só
matricula os alunos perante a apresentação do “nada
consta”
– Definição: dois processos bloqueiam a sua
execução pois um precisa de um recurso
bloqueado pelo outro processo
Conceitos: starvation e deadlock
Hermano P. Moura
O Modelo de Thread (2)
compartilhados
privados
O Modelo de Thread (3)
Cada thread tem sua própria pilha
Uso de Thread (1)
Um processador de texto com três threads
Uso de Thread (2)
Um servidor web com múltiplos threads
Implementação de
Threads de Usuário
Um pacote de threads de usuário
Implementação de
Threads de Núcleo
Um pacote de threads gerenciado pelo núcleo
Implementações Híbridas
Multiplexação de threads de usuário sobre
threads de núcleo
Criação de um novo thread quando
chega uma mensagem
Concorrência
Comunicação Interprocesso
Condições de Disputa/Corrida
Dois processos querem ter acesso simultaneamente à memória
compartilhada
Regiões Críticas (1)
• Quatro condições necessárias para prover
exclusão mútua:
– Nunca dois processos simultaneamente em uma
região crítica
– Não se pode considerar velocidades ou números
de CPUs
– Nenhum processo executando fora de sua região
crítica pode bloquear outros processos
– Nenhum processo deve esperar eternamente
para entrar em sua região crítica
Regiões Críticas (2)
Exclusão mútua usando regiões críticas
Exclusão Mútua com
Espera Ociosa (1)
Solução proposta para o problema da região crítica
(a) Processo 0.
(b) Processo 1.
Exclusão Mútua com
Espera Ociosa (2)
Solução de G. L. Peterson para exclusão mútua
Problema do ProdutorConsumidor
Produtor
Buffer
Consumidor
• se consumo > produção
– Buffer esvazia; Consumidor não tem o que
consumir
• se consumo < produção
– Buffer enche; Produtor não consegue produzir
mais
Dormir e Acordar (1)
Problema do produtor-consumidor com uma condição de disputa fatal
Dormir e Acordar (2)
Problema do produtor-consumidor com uma condição de disputa fatal
Semáforos (1)
O problema do produtor-consumidor usando semáforos
Semáforos (2)
O problema do produtor-consumidor usando semáforos
Exemplo da necessidade de Semáforo
(a) Um deadlock potencial.
(b) Um deadlock real.
Monitores (1)
Exemplo de um monitor
Monitores (2)
• O problema do produtor-consumidor com monitores
– somente um procedimento está ativo por vez no monitor
– o buffer tem N lugares
Troca de Mensagens
O problema do produtor-consumidor com N mensagens
Barreiras: Sincronização
•
Uso de barreira
a) processos se aproximando de uma barreira
b) todos os processos, exceto um, bloqueados
pela barreira
c) último processo chega, todos passam
Jantar dos Filósofos (1)
• Filósofos comem/pensam
• Cada um precisa de 2
garfos para comer
• Pega um garfo por vez
• Como prevenir deadlock ?
Jantar dos Filósofos (2)
Uma solução para o problema do jantar dos filósofos (parte 1)
Jantar dos Filósofos (3)
Uma solução para o problema do jantar dos filósofos (parte 2)
Escalonamento
Decidindo qual processo vai
executar
Processos Concorrentes
O Modelo de Multiprogramação
• Multiprogramação de quatro programas
• Modelo conceitual de 4 processos sequenciais,
independentes
• Somente um programa está ativo a cada momento
Conceitos Básicos
Tipos de S.O.
•
•
•
•
Monotarefa
Multitarefa
Monousuário
Multiusuário
Como evitar que um processo monopolize o sistema?
Sistemas de tempo compartilhado (Time Sharing Systems)
• Permite sistemas interativos (entrada/saída)
• Requer temporizadores (timers)
• Interrupções
Conceitos Básicos: Tipos de S.O.
Multiprocessamento
• O índice do processo
contém o apontador
para a lista de
processos
• PC (Program Counter) =
contador de programas
• Uma troca de
processos consiste em
trocar o valor dos
registradores de
contexto da CPU
Memória
Regs da CPU
Índ. Processo
...
Lista
de
proc.
...
...
Contexto
Proc. A.
PC
Dados
Código
Contexto
Dados
Proc. B.
Código
Base
Limite
Outros regs
Conceitos Básicos: Tipos de
S.O.
O que é necessário para haver multiprocessamento?
• Suporte do Hardware
– Temporizadores (timers)
– Interrupções
– Proteção de memória
• Suporte do S.O.
– Escalonamento dos processos
– Alocação de memória
– Gerenciamento dos periféricos
Comportamentos de Processos
•
Surtos de uso da CPU alternam-se com
períodos de espera por E/S
a) um processo orientado à CPU
b) um processo orientado à E/S
Escalonamento de Processos
Tipos de Processo
• CPU-bound:
– Se o processo gasta a maior parte do seu tempo usando a CPU
ele é dito orientado à computação (compute-bound ou CPUbound)
– processos com longos tempos de execução e baixo volume de
comunicação entre processos
• ex: aplicações científicas, engenharia e outras aplicações que
demandam alto desempenho de computação
• I/O-bound:
– Se um processo passa a maior parte do tempo esperando por
dispositivos de E/S, diz-se que o processo é orientado à E/S (I/Obound)
 processos I/O-bound devem ter prioridade sobre processos
CPU-bound
• Batch (lote) x Interativos
A importância da Interrupção
• Num sistema simples, CPU
deve esperar a execução
do comando de E/S
– A cada chamada do
comando write a CPU fica
esperando o dispositivo
executar o comando.
Ex: escrita em disco
A importância da Interrupção
• Um sistema com
interrupção não fica
esperando
– A CPU solicita o write e fica
executando outras tarefas
até ser interrompida pelo
disco.
Ex: escrita em disco
Operação Básica da CPU
Busca instrução
e dados
Incrementa PC
Executa a instrução
Com
interrupção
Não
Interrupção?
Sim
1) Pára o processo atual
2) Salta p/ rotina de interrupção
Interrupção do Programa
Processo de Interrupção
Dispositivo
pede interrupção
Hardware
Salva resto da Informação
do contexto do processo
Processador salva PSW
e PC na pilha de controle
Processa rotina
Processador carrega
novo valor do PC
baseado na interrupção
Restaura Informação do
estado do processo em
execução antes
da interrupção
*PSW = Program Status Word
*PC = Program Counter
de Interrupção
Restaura PSW e PC do
processo em execução
antes da interrupção
Software
Escalonamento de processos
• Quando um ou mais processos estão
prontos para serem executados, o sistema
operacional deve decidir qual deles vai ser
executado primeiro
• A parte do sistema operacional responsável
por essa decisão é chamada escalonador, e
o algoritmo usado para tal é chamado de
algoritmo de escalonamento
Escalonamento de Processos
Abstração
• Uma máquina para cada processo
• Paralelismo real
mP1
T11
T12
mP2
mP3
T0
mP3
T22
Escalonamento de Processos
Realidade
• Compartilhamento do tempo
• Pseudo-paralelismo
T12
mP1
T11
1
T0
41 51
T22
70
T0
90
121
t
Filas de Escalonamento
• High-level
– Decide quantos programas são admitidos no sistema
– Aloca memória e cria um processo
– Controla a long-term queue
• Short-term
– Decide qual processo deve ser executado
– Controla a short-term queue
• I/O
– Decide qual processo (com I/O) pendente deve ser tratado
pelo dispositivo de I/O
– Controla a I/O queue
Filas de Escalonamento
Short-term
scheduling
Process
request
Longterm
queue
High-level
scheduling
Interrupt
of process
Interrupt
from I/O
Interrupt
Handler
Shortterm
queue
CPU
I/O
I/O
queue
I/O
I/O
queue
I/O
I/O
queue
FIM
I/O scheduling
Categorias de Algoritmos de
Escalonamento
• Em lote (batch)
• Interativo
• Tempo-real
Introdução ao Escalonamento
Objetivos do algoritmo de escalonamento
Características de Escalonamento
• Justiça (fairness)
– Todos os processos têm chances iguais de uso dos
processador
• Eficiência
– Taxa de ocupação do processador ao longo do tempo
• Tempo de Resposta
– Tempo entre a ocorrência de um evento e o termino da
ação correspondente
• Turnaround
– “Tempo de resposta” para usuários em batch
– Minimizar o tempo que usuários batch devem esperar pelo
resultado
• Throughput
– No. de “jobs” (processos) executados por unidade de
tempo
Tipos de Escalonamento
• Mecanismos de Escalonamento Diz-se que um
– Preemptivo x Não-preemptivo
• Políticas de Escalonamento
– Round-Robin
– FIFO (First-In First-Out)
– Híbridos
algoritmo/sistema
operacional é preemptivo
quando um processo entra
na CPU e o mesmo pode
ser retirado da CPU antes
do término da sua execução
• Partições de Lote (Batch)
• MFQ - Multiple Feedback Queue
– SJF – Shortest Job First
– SRJN – Shortest Remaining Job Next
Escalonamento
Preemptivo
• Permite a suspensão temporária de processos
• Quantum ou time-slice: período de tempo durante
o qual um processo usa o processador a cada vez
Preempção
T12
mP1
T11
1
T0
41 51
T22
70
T0
90
121
t
Problema das trocas de processos
• Mudar de um processo para outro requer um certo
tempo para a administração — salvar e carregar
registradores e mapas de memória, atualizar
tabelas e listas do SO, etc
• Isto se chama troca de contexto
• Suponha que esta troca dure 5 ms
• Suponha também que o quantum está ajustado em
20 ms
• Com esses parâmetros, após fazer 20 ms de
trabalho útil, a CPU terá que gastar 5 ms com troca
de contexto. Assim, 20% do tempo de CPU (5 ms a
cada 25 ms) é gasto com o overhead
administrativo...
Solução?
• Para melhorar a eficiência da CPU, poderíamos ajustar o
quantum para 500 ms
– Agora o tempo gasto com troca de contexto é menos do que 1% “desprezível”...
• Considere o que aconteceria se dez usuários apertassem a
tecla <ENTER> exatamente ao mesmo tempo, disparando
cada um processo:
– Dez processos serão colocados na lista de processo aptos a
executar
– Se a CPU estiver ociosa, o primeiro começará imediatamente, o
segundo não começará cerca de ½ segundo depois, e assim por
diante
– O “azarado” do último processo somente começará a executar 5
segundos depois do usuário ter apertado <ENTER>, isto se todos
os outros processos tiverem utilizado todo o seu quantum
– Muitos usuários vão achar que o tempo de resposta de 5
segundos para um comando simples é “muita” coisa
“Moral da estória”
• Ajustar um quantum muito pequeno causa
muitas trocas de contexto e diminui a
eficiência da CPU, ...
• mas ajustá-lo para um valor muito alto
causa um tempo de resposta inaceitável
para pequenas tarefas interativas
Quantum grande:
Diminui número de mudanças de contexto e
overhead do S.O., mas...
Ruim para processos interativos
Categorias de Algoritmos de
Escalonamento
•
•
•
•
Em lote (batch)
Interativo
Tempo-real
Híbrido
Escalonamento em
Sistemas em Lote
• First-come first-served (ou FIFO)
• Shortest job first (job mais curto
primeiro)
• Shortest remaining Time/Job next
First-In First-Out (FIFO)
•
•
•
•
Uso de uma lista de processos sem prioridade
Escalonamento não-preemptivo
Simples e justo
Bom para sistemas em batch (lote)
CPU
A
FIM
B
C
D
E
F …
N
Escalonamentos
baseados no tempo de execução
• Shortest Job First (não-preemptivo)
• Shortest Remaining Job Next (preemptivo)
• Melhora o tempo de resposta
• Não é justo: pode causar estagnação (starvation)
– Pode ser resolvida alterando a prioridade dinamicamente
Exemplo de escalonamento job mais curto primeiro (Shortest Job First – SJF)
Escalonamento em Sistemas
Interativos
•
•
•
•
•
•
•
Round-robin
Prioridade
Multiple queues
Shortest process next
Guaranteed scheduling
Lottery scheduling
Fair-share scheduling
Escalonamento em
Sistemas Interativos (1)
•
Escalonamento por alternância circular (roundrobin)
a) lista de processos executáveis
b) lista de processos executáveis depois que B usou todo
o seu quantum
Escalonamento em
Sistemas Interativos (2)
Um algoritmo de escalonamento com quatro classes
de prioridade
Políticas de Escalonamento
Híbridos
• Como combinar processos batch com
interativos?
• Uso de Partições de Lote (batch)
– O sistema aceita tantos processos batch quantas
forem as partições de lote
– O sistema aceita todos os processos interativos
– Escalonamento em dois níveis
Segue...
Escalonamentos Híbridos
Partições de Lote
Memória
Processos interativos
são ativados
imediatamente
Processos
Interativos
Processos batch esperam a liberação do lote
Partição
de Lote
A
B
C
D
E
F …
N
Escalonamentos Híbridos
Multiple Feedback Queue
• Como saber a priori se o processo é CPUbound ou I/O-bound?
• MFQ usa abordagem de prioridades
dinâmicas
• Adaptação baseada no comportamento de
cada processo
• Usado no VAX / VMS...
Segue…
Escalonamentos Híbridos
Multiple Feedback Queue
• Novos processos entram na primeira fila (prioridade mais alta)
• Se acabar o quantum desce um nível
• Se requisitar E/S sobe um nível
– Lembrando: I/O-bound são prioritários
...
Fila 1
...
Fila 2
...
Fila n
Q
u
a
n
t
u
m
P
r
i
o
r
i
d
a
d
e
Escalonamento de Threads (1)
Possível escalonamento de threads de usuário
• processo com quantum de 50-mseg
• threads executam 5 mseg por surto de CPU
Escalonamento de Threads (2)
Possível escalonamento de threads de núcleo
• processo com quantum de 50-mseg
• threads executam 5 mseg por surto de CPU
Conclusões
Como funcionam dois ou mais programas ao mesmo tempo?
• Conceitos
– Processos x Threads
(processos leves)
• Interrupção
– Cooperação hardwaresoftware
• Escalonamento
– Tipos de processos
• CPU-bound x I/O-bound
• Lote (batch) x interativo
– Filas de escalonamento
• Long-term (admissão)
• Short-term
• I/O
• Escalonamento (cont.)
– Objetivos
• Justiça
• Eficiência
• Tempo de Resposta
– Conceitos
• Preempção
• Quantum (time-slice)
• Troca de contexto
– Algoritmos
• Propósito x Complexidade
x Eficiência