Baixe o app para aproveitar ainda mais
Prévia do material em texto
Tópicos ● Conceitos ● Níveis de escalonamento ● Tipos de sistemas ● Escalonamento em sistemas em lote ● Escalonamento em sistemas interativos ● Outros tópicos ● Escalonamento em sistemas de tempo real ● Escalonamento de threads Conceitos ● O escalonador é a entidade do sistema operacional responsável por selecionar um processo apto/pronto para executar no processador ● O objetivo é dividir o tempo do processador de forma “justa” entre os processos aptos a executar ● Além de escolher o processo “certo”, o escalonador deve se preocupar em fazer uso eficiente da CPU – Lembrando, chaveamento de contexto (ou seja, escalonamento de processos) é uma tarefa administrativa “cara” e deve ser minimizada ● O escalonador é necessário em diferentes tipos de sistemas multiprogramados: em lote, tempo compartilhado e tempo real ● Requisitos e restrições diferentes em relação a utilização da CPU Conceitos (cont.) ● Tipicamente, os processos alternam surtos de uso da CPU com períodos de espera por E/S (a) um processo orientado à CPU (b) um processo orientado à E/S Conceitos (cont.) ● Situações típicas para execução do escalonador ● Sempre que a CPU estiver livre e houver processos aptos a executar ● Criação e término de processos ● Um processo de mais alta prioridade ficar apto a executar ● Interrupção de tempo – Processo executou por um período de tempo máximo permitido ● Interrupção de dispositivos de entrada e saída ● Interrupção por falta de página (segmento) em memória – Endereço acessado não está carregado na memória (memória virtual) ● Interrupção por erros Fatores como o escalonador ser preemptivo ou não e considerar prioridades ou não vão definir quando o mesmo deve atuar Conceitos (cont.) ● O escalonamento está divido em duas partes: ● Escalonador – define qual processo deve executar ● Expedidor (dispatcher) – efetua a troca de contexto ● Níveis de escalonamento: ● Longo prazo ● Médio prazo ● Curto prazo Conceitos (cont.) ● Escalonamento de longo prazo: ● É executado quando um novo processo é criado ● Determina quando um processo novo passa a ser considerado no sistema, isto é, quando após sua criação ele passa a ser apto – Controle de admissão ● Controla o grau de multiprogramação do sistema – Quanto maior o número de processos ativos, menor a porcentagem de tempo de uso do processador por processo Conceitos (cont.) ● Escalonamento de médio prazo: ● Associado a gerência de memória – Participa do mecanismo de troca (swapping), escolhendo os processos que devem ir para o disco ou serem trazidos para a memória ● Suporte adicional a multiprogramação – Grau de multiprogramação efetiva (diferencia aptos de aptos-suspensos e bloqueados de bloqueados- suspensos) Conceitos (cont.) ● Escalonamento de curto prazo: ● É o mais importante e, geralmente, o mais atuante ● Determina qual processo apto deverá utilizar o processador ● É executado quando ocorre eventos importantes: – Interrupção de relógio – Interrupção de entrada/saída – Chamadas de sistemas – Sinais (interrupção software) Conceitos (cont.) ● Níveis de escalonamento CPU Escalonador de médio prazo Processos Escalonador de longo prazo Interrupção de tempo Fila de aptos Fila de suspensos (apto) Filas de suspensos (bloqueado) Fila de bloqueados Evento Espera por evento Término Escalonador de curto prazo Conceitos (cont.) ● Um vez escalonado, o processo utiliza o processador até que: ● Não preemptivo: – Término de execução do processo – Execução de uma requisição de entrada/saída ou sincronização – Liberação voluntária do processador a outro processo ● Preemptivo: – Término de execução do processo – Execução de uma requisição de entrada/saída ou sincronização – Liberação voluntária do processador a outro processo – Interrupção de relógio – Processo de mais alta prioridade esteja pronto para executar Conceitos (cont.) ● Ambientes diferentes, demandam diferentes algoritmos de escalonamento ● Diferentes áreas de aplicação e diferentes tipos de SOs têm objetivos diferentes ● Em termos de escalonamentos, três ambientes se destacam: – Em lote – Interativo – Tempo real Conceitos (cont.) ● Sistemas em lote ● Ainda são amplamente usados em ambientes corporativos – Exemplos: folhas de pagamento, estoque, contas a pagar, cálculo de juros (em bancos), processamento de pedidos indenização (em companhias de seguros), mineração de dados, etc. ● Não há demanda por interatividade ● Algoritmos não preemptivos ou preemptivo com longo intervalo de tempo para cada processo são aceitáveis Conceitos (cont.) ● Sistemas interativos ● A preempção é essencial para evitar que um processo se aposse da CPU – Minimiza os problemas causados por programas mal- comportados ou defeituosos ● Além dos computadores pessoais, servidores que atendem a múltiplos usuários remotos também se enquadram nessa categoria Conceitos (cont.) ● Sistemas de tempo real ● Em geral, são sistemas de propósito específico, permitindo assumir algumas premissas: – Os processos sabem que não podem executar por longos períodos, portanto fazem seu trabalho e bloqueiam rapidamente ● Em determinados cenários, a preempção pode ser até desnecessária – Os processos visam o progresso da aplicação, ou seja, são cooperativos Conceitos (cont.) ● Objetivos de um algoritmo de escalonamento Escalonamento em sistemas em lote ● Algoritmos ● Primeiro a chegar, primeiro a ser servido (First- Come, First-Served – FCFS ou First-In, First-Out – FIFO) ● Tarefa mais curta primeiro (Shortest Job First – SJF ou Shortest Process Next – SPN) ● Próximo de menor tempo restante (Shortest Remaining Time – SRT) Escalonamento em sistemas em lote – FCFS ● Simples de implementar ● É apenas uma fila ● Funcionamento: ● Processos que se tornam aptos são inseridos no final da fila ● Processo que está no início da fila é o próximo a executar ● Processo executa até que: – Libere explicitamente o processador – Realize uma chamada de sistema (bloqueado) – Termine sua execução Escalonamento em sistemas em lote – FCFS (cont.) ● Desvantagem: ● Prejudica processos que fazem muitas operações de E/S ● Tempo médio de espera na fila do exemplo abaixo: – Ordem A-B-C-D = (0 + 12 + 20 + 35 ) / 4 = 16.75 u.t. A 0 12 20 35 40 B C D Processo A B C D Tempo 12 8 15 5 Escalonamento em sistemas em lote – SJF ● Motivado pelo fato que o menor tempo de médio é obtido quando se executa primeiro os processos de menor ciclo de processador (E/S intensiva) ● Tempo médio de espera na fila do exemplo abaixo: – Ordem D-B-A-C = (0 + 5 + 13 + 25) / 4 = 10.75 u.t A 0 40 B C D 5 13 25 Processo A B C D Tempo 12 8 15 5 Escalonamento em sistemas em lote – SJF (cont.) ● Fornece o menor tempo médio de espera para um conjunto de processos ● Processos do tipo E/S intensiva são favorecidos ● Apresenta algumas dificuldades: ● É necessário que as tarefas estejam disponíveis – Se os tempos de chegada são diferentes, o algoritmo não garante a melhor escolha ● Determinar o tempo do próximo ciclo de CPU de cada processo, ou seja, durante quanto tempo o processo vai utilizar a CPU – Porém, é possível utilizar um preditor simples para estimar esse tempo Escalonamento em sistemas em lote – SJF (cont.) ● Usando um preditor simples ● Média Móvel Exponencialmente Ponderada (EWMA – Exponentially Weighted Moving Average) – Se baseia nos valores anteriores para estimaro próximo valor, da seguinte forma: Tn+1 = a . tn + (1 – a) . Tn Tn+1 = valor estimado para a próxima amostra Tn = média exponencialmente ponderada das amostras anteriores tn = amostra atual a = parâmetro de ajuste do peso a ser dado a amostra atual e ao histórico das amostras, sendo que 0 ≤ a ≤ 1 Escalonamento em sistemas em lote – SJF (cont.) ● Ciclo de CPU (parâmetros: a = 0.5 e T0=10) ● Real: 6 4 6 4 13 13 13 13 ● Previsto: 10 8 6 6 5 9 11 12 0 2 4 6 8 10 12 14 0 1 2 3 4 5 6 7 Real Previsto Escalonamento em sistemas em lote – SRT ● Versão preemptiva do SJF ● O escalonador escolhe o processo cujo tempo de execução restante seja o menor – Novamente, o tempo de execução deve ser previamente conhecido (ou estimado) ● Quando chega um novo processo, seu tempo total é comparado ao tempo restante do processo em curso – Se o novo processo precisar de menos tempo que o processo corrente, então esse será suspenso e o novo processo começa a ser executado ● Não é afetado por tempos de chegada diferentes entre os processos Escalonamento em sistemas interativos ● Algoritmos ● Chaveamento circular (Round-Robin) ● Por prioridades ● Há vários outros na literatura: próximo processo mais curto, escalonamento garantido, escalonamento por loteria, escalonamento por fração justa, etc. Escalonamento em sistemas interativos – Round-Robin ● Similar ao FCFS, porém cada processo recebe um tempo limite máximo (fatia de tempo, quantum) para executar um ciclo de processador ● Fila de processos aptos/prontos é uma fila circular ● Necessidade de um relógio para delimitar as fatias de tempo ● Interrupção de tempo fornecido pelo hardware A 0 40 B C D 3 6 9 12 15 18 2823 34 Processo A B C D Tempo 12 8 15 5 Quantum = 3 u.t. ● Problemas: ● Dimensionamento do quantum – Compromisso entre sobrecarga (devido ao chaveamento de contexto) e tempo de resposta em função do número de usuários (1/n na presença de n usuários) ● Quantum muito curto causa muitos chaveamentos de contexto e reduz eficiência da CPU e quantum muito longo pode gerar tempo resposta muito alto para requisições interativas curtas ● Processos que fazem muito E/S são prejudicados – Esperam da mesma forma que processos que utilizam muito a CPU, porém (provavelmente) não utilizam todo o seu quantum – Solução: ● Prioridades: associar prioridades mais altas aos processos do tipo E/S intensiva para compensar o tempo de espera Escalonamento em sistemas interativos – Round-Robin (cont.) Escalonamento em sistemas interativos – Por prioridades ● Consiste em atribuir tratamento diferenciado aos processos no escalonamento ● Prioridades podem ser: ● Estáticas – associadas com alguma característica do processo: função desempenhada, usuário, etc. ● Dinâmicas – alteradas de acordo com o comportamento do processo: quanto menos usa a CPU, maior a prioridade – Exemplo de algoritmo simples: prioridade = 1 / f, onde f é a fração efetivamente usada do quantum ● “Mistas” – combina prioridades estáticas e dinâmicas Escalonamento em sistemas interativos – Por prioridades (cont.) ● Exemplo: algoritmo de escalonamento com 4 classes de prioridade ● Abordagens comuns: – Escalonar todos os processos de uma prioridade antes de começar a escalonar de outra ● Se não houver ajuste das prioridades, pode levar a inanição (starvation) – Associar a frequência de escalonamento à prioridade – Atribuir quantum de tempo diferente para cada prioridade Escalonamento em sistemas de tempo real ● Principal objetivo é escalonar os processos de maneira que os prazos sejam cumpridos ● Tipicamente, os processos de um sistema de tempo real precisam tratar 2 tipos de eventos ● Periódicos – ocorrem em intervalos regulares de tempo (exemplo: captura de vídeo) – É necessário dimensionar se o sistema de tempo real é escalonável ● Aperiódicos – acontecem de modo imprevisível (exemplo: falha de uma turbina de avião) ● Dimensionamento de um sistema de tempo real escalonável ● Dados: – m eventos periódicos – evento i ocorre dentro do período Pi e requer Ci segundos ● A carga poderá ser tratada somente se 1 1 m i i i C P = ≤ ∑ Escalonamento em sistemas de tempo real (cont.) Escalonamento de threads ● Threads modo usuário ● Núcleo escalona o processo e biblioteca de threads é responsável pelo escalonamento das mesmas – Depende da cooperação das threads, pois não há interrupção de relógio – Pode ser usado qualquer algoritmo de escalonamento – É flexível, podendo ser customizado para dar tratamento diferenciado as threads através de conhecimento da aplicação Escalonamento de threads (cont.) ● Threads modo núcleo ● Não precisa levar em consideração a qual processo pertence uma thread, embora possa fazê-lo ● Impede que o bloqueio de uma thread leve necessariamente ao bloqueio de um processo ● Suporta diferenciação das threads por prioridade, mas não sabe nada sobre a aplicação
Compartilhar