Sistemas Operacionais
Prof.: Filipe T. Marques
[email protected]
UNIPÊ
Transparências também adaptadas pelo
professor: Gustavo Wagner
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
1
Capítulo 2
Processos e Threads
2.1 Processos
2.2 Threads
2.3 Comunicação interprocesso
2.4 Problemas clássicos de IPC
2.5 Escalonamento
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
2
Escalonamento
• Em computadores multiprogramados há vários
processos concorrendo pela CPU ao mesmo
tempo;
• Se houver apenas uma CPU, deverá ser escolhido
um processo para executar primeiro;
• No SO, a parte que faz isso é o escalonador;
• O algoritmo usado é o algoritmo de
escalonamento;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
3
Introdução
• No início, com sistemas em lote, sendo a
entrada cartões gravados em fita magnética,
o algoritmo era: execute o próximo job na
fita;
• Um algoritmo de escalonamento inteligente
e eficiente é o que se busca;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
4
Introdução
• Com o advento de computadores pessoais, a
estória mudou em dois aspectos;
• Primeiro: normalmente em PCs existe
apenas um processo ativo: editor de texto;
• Segundo: as cpus ficaram tão rápidas que
atualmente a lentidão vem por parte do
usuário;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
5
Introdução
• Como conseqüência, em PCs simples, o
escalonamento não é tão importante;
• Já em servidores e estações de trabalho de
alto desempenho em rede, a situação muda;
• Por exemplo, qual deve executar primeiro:
– Processo que atualiza a tela depois do usuário
fechar uma janela;
– Processo que envia mensagens eletrônicas;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
6
Introdução
• Além de escolher qual processo executar, o
escalonador tem que fazer bom uso da CPU;
• Alternar processos é muito caro!
– Passa-se do modo usuário para modo núcleo;
– Salva-se o estado atual do processo: contexto;
– Em alguns sistemas, mapa de memória deve ser
salvo;
– Um novo processo precisa ser escolhido;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
7
Introdução
– A MMU precisa carregar o mapa de bits do
novo processo;
– O novo processo precisa ser iniciado;
– Além disso, a memória cache precisa ser
invalidada;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
8
Comportamento do processo
• Processos têm surtos de computação e
requisições de E/S;
• Interrupção de tempo
– Evita que o processo rede por um tempo muito
grande
– O escalonador é posto para rodar e decide qual
processo executará
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
9
Escalonamento
•
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
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
10
Comportamento do processo
• Quanto mais rápidas as CPUs, mais os
processos serão orientados à E/S;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
11
Quando escalonar
• Primeiro, quando se cria um novo processo,
é necessário tomar a decisão de execução do
pai ou filho;
• Segundo, no término de um processo é
necessário escolher outro processo;
• Terceiro, quando um processo bloqueia para
E/S, é necessário escolher outro processo
para executar;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
12
Quando escalonar
• Quarto, quando ocorre uma interrupção de
E/S; O processo que estava esperando a E/S
vai para pronto e pode ser escalonado;
• Decisões do escalonador pode ocorrer a
cada interrupção do relógio;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
13
Quando escalonar
• Preemptivo: tempo fixado de execução;
• Não-preemptivo: o processo só para de
executar se houver E/S ou finalizou;
• Se não houver relógio disponível, o
escalonamento não-preemptivo será a única
opção;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
14
Categorias de algoritmos
• Diferentes áreas de aplicações têm objetivos
diferentes;
• Por isso tempos diferentes categorias de
algoritmos;
– Lote: não há usuário impaciente esperando
resultado; Os algoritmos são não-preemptivos
ou preemptivos com tempo longo;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
15
Categorias de algoritmos
– Interativo: algoritmos preemptivos; Se um
programa falhar, é só escolher outro;
– Tempo real: estranhamente, preempção é
desnecessária; cada processo faz seu trabalho e
abandona a CPU;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
16
Requisitos
• Justiça
– Garantir que todos os processos terão chances
iguais de uso do processador
• Eficiência
– Manter o processador ocupado 100% do tempo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
17
Requisitos
• Tempo de resposta
– Minimizar o tempo de resposta para os usuários
interativos
• Turnaround
– Minimizar o tempo que os usuários batch devem
esperar pela saída
• Throughput
– Maximizar o número de jobs processados na
unidade de tempo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
18
Introdução ao Escalonamento (2)
Objetivos do algoritmo de escalonamento
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
19
Escalonamento em lote –
Primeiro a chegar, primeiro a ser
servido – FILA
• Um job executa até concluir sua computação ou
que seja bloqueado;
• Jobs que cheguem para executar esperarão numa
fila;
• Caso de desvantagem:
– um processo orientado à cpu precisa executar por 1s, a
cada vez;
– Outros processos orientados à E/S precisam realizar
1000 leituras de disco;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
20
Job mais curto primeiro
Um exemplo de escalonamento job mais curto primeiro
(4a + 3b + 2c + d)/4
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
21
Job mais curto primeiro
• Todos os jobs já devem estar prontos;
• Contra exemplo (quando nem todos os jobs
estão disponíveis):
– 5 processos: A(2), B(4), C(1), D(1), E(1)
– Tempos de chegada: 0, 0, 3, 3, 3
– Usando Job mais curto primeiro, teríamos: A,
B, C, D, E = 4,6
– Se executarmos na ordem B, C, D, E, A = 4,4
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
22
Próximo de menor tempo
restante
• Versão preemptiva do “Job mais curto
primeiro”;
• Se um processo chegar, e seu tempo de
execução for menor do que o tempo restante
do processo atual, ele será escolhido;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
23
Escalonamento em 3 níveis
Escalonamento em três níveis
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
24
Escalonamento em
Sistemas Interativos Round Robin
•
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
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
25
Round robin
• Mudança de contexto é caro;
• Se mudar de contexto durasse 1ms, e
quantum fosse 4ms, 20% do tempo de CPU
seria mudando contexto! 
• Se o quantum for muito grande, ex.: 100ms,
e tiver 10 usuários teclando <enter>, o
último talvez tenha que esperar 1s!
• Um quantum razoável está entre 20 a 50ms;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
26
Escalonamento por prioridade
Um algoritmo de escalonamento com quatro classes
de prioridade
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
27
Escalonamento por prioridades
• O escalonador pode levar em consideração quanto
do quantum o processo utilizou;
• Por exemplo, se o quando for de 50ms, e o
processo só usou 1ms, o escalonador deve
aumentar a prioridade deste em relação a outro
processo que usou todo o quantum;
• Fórmula: 1/f, onde f é a fração do quantum que o
processo usou;
• Como evitar que um processo de alta prioridade
rode indefinidamente?
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
28
Próximo processo mais curto
• Em sistemas em lote, funciona bem;
• Mas como fazer isso em sistemas
interativos? Ou seja, como saber quem é o
job mais curto nesse momento?
• Calcular com base em execuções passadas,
e fazer o cálculo do tempo estimado;
• aT0 + (1-a)T1;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
29
Escalonamento por loteria
• Cada processo é munido de um bilhete;
• George Orwell: “Todos os processos são iguais,
mas alguns são mais iguais que os outros”;
• Processos mais importantes podem receber mais
bilhetes;
• Um novo processo que recebe bilhete tem a
mesma chance que um antigo;
• Esse algoritmo é altamente responsivo;
• Os processos cooperativos podem trocar bilhetes:
ex.: Cliente-Servidor
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
30
Escalonamento por fração justa
• Se um usuário tiver 4 processos a executar,
e outro tiver 1 único processo para
executar?
• Provavelmente o primeiro usuário usará
80% da CPU e o outro apenas 20%;
• Escalonamento por fração justa divide
igualitariamente a CPU entre os usuários;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
31
Escalonamento em Sistemas
de Tempo Real
• Algoritmos de escalonamento de tempo real
podem ser estáticos ou dinâmicos;
• Estático: escalona-se antes do sistema ser
executado; tem-se informação precisa antes
da execução;
• Dinâmico: escalona-se durante a execução
do sistema;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
32
Política X Mecanismo
• Fizemos suposições até agora que os processos pertencem
a usuários diferentes;
• Mas existem vários processos que são do mesmo usuário,
como pai e filhos;
• Algoritmos são parametrizáveis, mas os parâmetros podem
ser passados pelos processos dos usuários;
• Mecanismo: algoritmo de escalonamento; está
normalmente no núcleo;
• Política: pode ser implementada por algum processo de
usuário;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
33
Escalonamento de Threads
• Em nível do usuário, quem escalona é o sistema
supervisor;
• Ele é quem entende qual o melhor momento e qual
thread deve escalonar;
• O escalonador do SO só escalona o processo das
threads, não as próprias threads;
• O algoritmo usado pelo sistema supervisor pode
ser qualquer um dos vistos anteriormente;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
34
Escalonamento de Threads
• Já em modo núcleo, o escalonador escalona cada
thread especificamente;
• Escalonar uma thread de núcleo é bem mais lento
que escalonar uma thread de usuário: precisa
invalidar memória, cache, etc;
• Mudar de uma thread A.1 para A.2 é mais rápido
que mudar de A.1 para B.1;
• Isso pode ser levado em consideração na hora de
escalonar;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
35