Aula 2 - Sistmemas Operacionais - Processos e Threads - Parte II

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Sistemas Operacionais
Processos e Threads
Parte II
 Prof. Esp. Alan Rafael Ferreira dos Santos 
Universidade Federal do Piauí – UFPI
Campus Senador Helvídio Nunes de Barros – Picos –PI 
Bacharelado em Sistemas de Informação
1
1. Introdução ao Escalonamento 
 Uma vez que há diversos processo na fila de pronto, qual deles selecionar para o estado de execução?
 Política de Escalonamento!
 Base da gerência do processador
1. Introdução ao Escalonamento 
O escalonador é responsável por escolher o processo ou thread que deverá ser executado além de manter o maior desempenho da CPU.
Realizar muitos chaveamento pode comprometer uma grande quantidade de tempo e um algoritmo de escalonamento deve ser bem elaborado para utilizar este recurso de maneira eficiente.
1. Introdução ao Escalonamento 
 Funções básicas da política de escalonamento:
 Manter a CPU a mais ocupada possível;
 Balancear o uso da CPU entre os processos;
 Privilegiar aplicações críticas;
 Maximizar throughput (vazão) do sistema;
 Possibilitar tempos de resposta razoáveis para aplicações interativas (SO de tempo real).
4
1.1 Comportamento do Processo 
CPU-bound:
Se o processo gasta a maior parte do seu tempo usando a CPU ele é dito orientado à computação (compute-bound ou CPU-bound).
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/O-bound).
 Processos I/O-bound devem ter prioridade sobre processos CPU-bound.
1.1 Comportamento do Processo 
Surtos de uso da CPU se alternam com períodos de espera por E/S – tipos de processo:
orientado à CPU (CPU-bound);
orientado à E/S (I/O-bound).
1.2 Quando Escalonar 
Quando se cria um novo processo e necessário decidir em executar o processo pai ou processo filho, ambos em estado pronto.
Ao fim de todo processo, quando não há mais o que fazer, é necessário escolher um novo processo para ser executado.
 Quando um processo é bloqueado e o mesmo pode influenciar na escolha.
Quando ocorre uma interrupção de E/S, quando o processo bloqueado aguardando por uma E/S já pode ficar em estado pronto.
1.2 Quando Escalonar 
Algoritmos de escalonamento:
Não preempitivo:
- São algoritmos que escolhem o processo e o deixam executar até seu fim ou até que seja bloqueado (interrupção por E/S).
Preempitivo:
 São algoritmos que permitem que um processo seja interrompido durante sua execução, quer seja por força de uma interrupção de E/S, quer seja em decorrência da politica de escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por força do término da execução do processo.(requer uma interrupção controlada por relógio para melhor controle da CPU)
1.3 Categorias de Algoritmos de Escalonamento 
Para cada ambiente é necessário um algoritmo de escalonamento adequado para atender as necessidades, temos três ambientes que merecem distinção:
Lote 
Interativo 
Tempo Real
1.4 Objetivos dos Algoritmos de Escalonamento 
1.5 Algoritmos de Escalonamento 
FCFS (First-Come First-Served): o primeiro na fila de pronto é executado.
Uso de uma lista de processos sem prioridade;
Escalonamento não-preemptivo;
Simples e justo;
Bom para sistemas em batch (lote).
1.5 Algoritmos de Escalonamento 
 Simples, porém apresenta deficiências:
 Impossibilidade de se prever início da execução de determinado processo.
 Não se preocupa em otimizar critérios de escalonamento (p/ex., tempo de turnaround de processos que demandam menos CPU).
 Processos CPU-bound dominam o processador frente a processos I/O-bound.
12
1.5 Algoritmos de Escalonamento 
Shortest-Job-First: Processo com menor tempo de processador a executar é selecionado para execução
 Escalonamento não preempitivo;
 Tende a reduzir o tempo médio de espera;
 Bom para sistemas em batch (lote).
ASO – Machado/Maia – complem. por Sidney Lucena (UNIRIO)
1.5 Algoritmos de Escalonamento 
 Implementação se vale de estimativas para o tempo de execução restante para os processo na fila de pronto.
Em relação ao escalonamento FIFO, reduz o tempo médio de turnaround dos processos.
 Possibilidade de starvation para processos com tempo de CPU muito longos ou CPU-bound.
14
1.5 Algoritmos de Escalonamento 
 Round-Robin Scheduling: escalonamento “circular”: 
Um dos algoritmos mais antigos, simples, justos e amplamente usados.
Bom para sistemas interativos. 
 Escalonamento semelhante ao FCFS, porém preemptivo, onde é dada uma fatia de tempo de execução para cada processo e, ao final deste período, o processo vai para o final da fila de pronto.
1.5 Algoritmos de Escalonamento 
 Principal vantagem é impedir o monopólio da CPU por algum processo:
 Tempo máximo de CPU igual ao time-slice definido no sistema.
 Processos CPU-bound levam vantagem em relação a processos I/O-bound:
 Processos I/O-bound têm mais chance de entrar no estado de espera antes de usarem todo o time-slice.
16
1.5 Algoritmos de Escalonamento 
 Escalonamento por Prioridade: 
Escalonamento preemptivo com base na prioridade de execução de cada processo:
Processos são organizados em filas separadas de acordo com seu nível de prioridade;
 Processos são escalonados somente quando as filas dos processos de maior prioridade estiverem vazias;
 Processos com mesmo nível de prioridade são escalonados segundo uma política FCFS;
 Não existe conceito de time-slice, não há preempção por tempo e sim por prioridade.
1.5 Algoritmos de Escalonamento 
18
1.5 Algoritmos de Escalonamento 
 Também pode ser implementado de forma não-preemptiva:
 Processos com prioridade maior vão para o início da fila de pronto, sem causar preempção de processos com menor prioridade.
 Cada S.O. implementa sua faixa de valores para as prioridades de execução.
 Principal problema: possibilidade de Starvation!
 Processos com baixa prioridade podem nunca ser escalonados;
 Uma solução: aumentar gradativamente prioridade de processos há muito na fila de pronto.
19
1.5 Algoritmos de Escalonamento 
 Útil em sistemas de tempo real;
 Útil para aplicações de controle de processos;
 Útil para priorizar processos em sistemas de tempo compartilhado;
20
1.5 Algoritmos de Escalonamento 
Escalonamento Circular com Prioridade 
 Implementa conceito de fatia de tempo junto com prioridade:
 Processo em execução pode sofrer preempção por tempo ou por prioridade;
 Permite melhor balanceamento no uso da CPU;
 Amplamente usado em sistemas de tempo compartilhado;
 **Não** evita o starvation.
21
1.5 Algoritmos de Escalonamento 
22
1.5 Algoritmos de Escalonamento 
Filas Múltiplas:
Primeiros escalonadores por prioridade;
Só poderia manter um processo na memória por vez;
Classes de prioridades;
Se um processo utiliza-se todos os seus quanta, seria movido para uma classe inferior.
1.5 Algoritmos de Escalonamento 
Escalonamento Garantido:
Promessas reais sobre o desempenho aos usuários e então satisfazê-los.
Se houver n usuários estiverem conectados enquanto você estiver trabalhando, você receberá cerca de 1/n da CPU.
Para valer as promessas é preciso ter um controle da quantidade da CPU que cada processo recebe desde a sua criação.
Difícil implementação.
1.5 Algoritmos de Escalonamento 
Escalonamento por loteria:
Simples de Implementar.
“Bilhete de loteria” para processos, cujos os prêmios são recursos do sistema.
A processo mais importantes e possível dar mais de um bilhete (bilhete extra) aumentando a possibilidade de vitórias.
Divisão da CPU. 
1.5 Algoritmos de Escalonamento 
Escalonamento por fração justa (fair-share):
Propriedade do processo para escalonar.
Fração justa para cada usuário, por exemplo: se dois usuários tiverem disponíveis para cada 50% da CPU prometida a eles, cada um terá os 50%, não importando
o número de processos que eles tenham gerados.
2. Política versus Mecanismos 
Infelizmente nenhum dos algoritmos escalonadores vistos aceita qualquer entrada proveniente de processo de usuários sobre o escalonador. Como resultado, nem sempre o escalonador faz a melhor escolha (raramente).
A solução seria separar Mecanismo de Escalonamento de Política de Escalonamento.
Um processo, ao criar um processo filho, pode ter noção da importância do processo que está sendo criado.
O processo pai pode “controlar” como seus filhos devem ser escalonados.
O mecanismo está no núcleo do S.O. e a política e estabelecida pelo processo (prioridade passada por parâmetro)