Baixe o app para aproveitar ainda mais
Prévia do material em texto
Sistemas Operacionais Prof. Fernando Eryck 2012.2 Redes de Computadores SUMÁRIO � Gerenciador de Processos Introdução �Sistemas multiprogramáveis � Múltiplos processos compartilhamento a memória principal � Múltiplos processos fazendo a disputa pelo uso da CPU (fila) �Sistema operacional �deve decidir qual dos processos será escolhido para fazer uso do processador �Seleção baseada em critérios �Política de escalonamento Estado de Espera Estado de Execução Estado de Pronto Escalo na m ento Funções Básicas da Política de Escalonamento �Manter a CPU ocupada a maior parte do tempo �Balancear o uso da CPU entre os processos �Privilegiar a execução de aplicações críticas �Maximar o throughput �Oferecer tempos de respostas razoázeis para usuários interativos �Implementar o scheduler e dispatcher � Scheduler (Escalonador) – rotina do SO que tem como principal função implementar os critérios da política de escalonamento �Dispatcher – rotina do SO responsável pela troca de contexto dos processos após o escalonamento Funções Básicas da Política de Escalonamento � Processos – unidades de alocação de recursos �Threads - unidades de escalonamento Critérios de Escalonamento �Maximizar a utilização do processador � É desejável que o processador permaneça a maior parte do seu tempo ocupado. �U/lização <= 30% → carga de processamento baixa�U/lização <= 30% → carga de processamento baixa �Utilização até 90% → carga de processamento próximo a capacidade máxima �Maximizar a produção do sistema (Throughput) � Número de processos executados em um determinado intervalo de tempo � Quanto maior o throughput, maior o número de tarefas executadas em função do tempo Critérios de Escalonamento � Tempo de processador / Tempo de CPU � Tempo que um processo leva no estado de execução durante seu processamento �Minimizar o tempo de espera�Minimizar o tempo de espera � Tempo total de um processo na fila de pronto durante seu processamento, aguardando para ser executado. �Minimizar o tempo de execução (Turnaround) � tempo de criação de um processo até seu término � tempo de espera alocação recursos + fila de pronto + tempo de processamento + tempo de espera (e/s) Critérios de Escalonamento �Minimizar o tempo de resposta � Tempo decorrido entre uma requisição ao sistema e o instante em que a resposta é exibida � Tempo de resposta, em geral, é limitado pela velocidade dos dispositivos de E/S, e não pela capacidade de processamento do sistema de E/S, e não pela capacidade de processamento do sistema computacional Política de Escalonamento Visa: - Otimizar a utilização do processador e o throughput - Diminuir os tempos de turnaround, espera e resposta Classificação das Políticas de Escalonamento - Escalonadores Preemptivos e Não-Preemptivos �Preemptivos � Possibilidade do SO interromper um processo em execução e substituí- lo por outro � Implementação mais complexa � Possibilita políticas de escalonamento mais flexíveis � É possível ao sistema priorizar a execução de processos� É possível ao sistema priorizar a execução de processos � Possibilidade de implementar políticas de escalonamento que compartilhem a CPU de maneira uniforme. �Não-preemptivos � Quando um processo está em execução nenhum evento externo pode ocasionar a perda do uso do processador � O processo sai do estado de execução quando terminar seu processamento, ou; � Executar instruções do próprio código que o mude para o estado de espera Escalonamento FIFO – (First In - First Out) �O processo que chegar primeiro ao estado de pronto, é o primeiro a ser selecionado para execução � Simples de ser implementado � Necessário uma fila Necessário uma fila � Todos os processos quando saem do estado de espera entram no final da fila de pronto � Tipo não-preemptivo UCP Estado de Criação Estado de Espera Fila dos processos no estado de Pronto Estado de Término Problemas do escalonamento FIFO � Problema � Processos CPU-Bound levam vantagem no uso do processador em relação aos I/O-Bound Processo A Processo B Processo C 10 14 17 u.t. � Não se sabe quando um processo terá sua execução iniciada �Não há uma preocupação em melhorar o tempo médio de espera. �Problema nos tempos de turnaround para processos que demandam pouco tempo de CPU 10 14 17 Processo A Processo B Processo C 4 7 17 u.t. u.t. Processo Tempo de processador (u.t.) A B C 10 4 3 Implementações do escalonamento FIFO � Implementado inicialmente em sistemas monoprogramáveis do tipo batch. � Implementado atualmente em sistema de tempo compartilhado com algumas variações.compartilhado com algumas variações. Escalonamento Shortest-Job-First (SJF) �Algoritmo de escalonamento seleciona o processo que tiver o menor tempo de processador ainda por executar � O processo na fila de pronto que necessita de menos tempo de CPU é selecionado �Realizado uma estimativa com base nas execuções passadas � Para cada novo processo um tempo de CPU era associado ao seu contexto de software Processo A Processo B Processo C 3 7 17 u.t. Problema do Escalonamento SJF � Impossibilidade de estimar tempo de processador para processos interativos �Não é possível ao SO saber quanto tempo um processo irá permanecer utilizando a CPU na próxima vez que for escalonado, permanecer utilizando a CPU na próxima vez que for escalonado, mas é possível prever o tempo com base no comportamento passado � É possível haver Starvation para processos com tempo de processador muito longo � CPU-Bound Starvation = Ocorre quando um processo fica indefinidamente esperando pela utilização da CPU. Escalonamento Shortest-Job-First (SJF) �Tipo não-preemptivo (concepção inicial) � Vantagem sobre o FIFO � redução do tempo médio de turnaround dos processos Implementações do Shortest-Job-First (SJF) � Implementado nos primeiros SOs exclusivamente em batch Escalonamento SJF preemptivo �Escalonamento shortest remaining time (SRT Scheduling) � Toda vez que um processo no estado de pronto tem um tempo de processador estimado menor do que o processo em execução o SO realiza a preempção � O SO continua estimando o tempo de processador� O SO continua estimando o tempo de processador �O risco de sofrer Stavartion continua Escalonamento Cooperativo �Um processo em execução libera voluntariamente o uso da CPU � Tarefa realizada exclusivamente pelo processo em execução � Implementado em escalonadores que não executam a preempção, FIFO e SJF �Processo verifica a fila de mensagens para determinar se existem outros �Processo verifica a fila de mensagens para determinar se existem outros processos na fila de pronto �Melhor distribuição do processador �Problema � Caso o processo não verifique a fila de mensagens os demais processos não terão chance de serem executadas até o término do uso da CPU �EX. � Primeiros SOs Windows (Win 3.11) Escalonamento Circular (Round Robin Scheduling)) �Escalonamento preemptivo �Projetado para sistemas de tempo compartilhado �Semelhante ao FIFO � Quando um processo passa para o estado de execução é � Quando um processo passa para o estado de execução é alocado um tempo limite chamado fatia de tempo ou quantum. � A fatia de tempo depende da arquitetura do SO e varia de 10 a 100 ms � Ao final da fatia de tempo o SO: � interrompe o processo em execução � Salva seu contexto � Direciona para o final da fila de pronto Escalonamento Circular (Round Robin Scheduling)) �O processo permanece em execução até que: �Termine seu processamento �Voluntariamentepasse para o estado de espera � Fatia de tempo expire� Fatia de tempo expire � Vantagem � Não permite que um processo monopolize a CPU Escalonamento Circular (Round Robin Scheduling)) Preempção por tempo UCP Estado de Criação Fila dos processos no estado de Pronto Estado de Término Estado de Espera Processo A Processo B Processo C 2 4 17 u.t.6 8 10 11 Escalonamento Circular (Round Robin Scheduling)) �Problema (Balanceamento desigual) � CPU-Bound são beneficiados em relação ao I/O-Bound � CPU-Bound tendem a utilizar por completo a fatia de tempo � I/O-Bound passam mais tempo no estado de espera� I/O-Bound passam mais tempo no estado de espera UCP Estado de Criação Estado de Espera Fila dos processos no estado de Pronto Estado de Término Escalonamento Circular (Round Robin Scheduling)) � Escalonamento Circular Virtual (Mecanismo adaptativo) � Processos saem do estado de espera vão para uma fila de pronto auxiliar � Os processos da fila auxiliar possuem preferência no escalonamento em relação à fila de pronto � Fila de pronto é escalonada quando a fila auxiliar estiver vazia� Fila de pronto é escalonada quando a fila auxiliar estiver vazia Preempção por tempo UCP Estado de Criação Fila dos processos no estado de Pronto Estado de Término Estado de Espera Fila auxiliar Processos na fila auxiliar continuarão executando o tempo restante da fatia de tempo. Escalonamento por Prioridades �Tipo preemptivo � Realizado com base em um valor associado a cada processo denominado prioridade execução � O processo com maior prioridade no estado de pronto e sempre � O processo com maior prioridade no estado de pronto e sempre o escolhido para execução �Não existe o conceito de fatia de tempo � Processos com prioridades iguais seguem o critério FIFO � Perda do uso do processador � Mudança voluntária para o estado de espera � Um processo de prioridade maior passe para o estado de pronto � termine seu processamento Escalonamento por Prioridades Estado de Filas dos processos no estado de Pronto Prioridade P1 Prioridade P2 Estado de UCP Estado de Término Prioridade Pn Estado de Criação Estado de Espera Preempção por prioridade Escalonamento por Prioridades Processo A Processo B Processo Tempo de processador (u.t.) Prioridade Processo B Processo C 3 13 17 u.t. A B C 10 4 3 2 1 3 Escalonamento por Prioridades �Tipo Não-preemptivo � Processsos que passem para o estado de pronto com prioridade maior do que a do processo em execução não ocasionam preempção � São colocados no ínicio da fila de pronto � Prioridade estática � não tem seu valor alterado durante a existência do processo �Prioridade dinâmica � Pode alterar o valor de acordo com critérios definidos pelo SO Escalonamento por Prioridades � Principais problemas do Escalonamento de prioridades � Processos de baixa prioridade podem sofrer starvation, permanecendo na fila de pronto indefinidamente � Solução � Mecanismo de aging. � Mecanismo de aging. �Mecanismo que incrementa gradualmente a prioridade de processos que permanecem por muito tempo na fila de pronto Escalonamento Circular com Prioridades �a cada processo implementa o conceito de : � fatia de tempo; � Prioridade de execução � O processo permanece no estado de execução até que: � Termine seu processamento � Voluntariamente passe para o estado de espera � Sofra uma preempção por tempo ou prioridade � Permite um melhor balanceamento no uso do processador � Processos I/O-Bound devem receber do adm. de sistemas prioridades maiores que os processos CPU-Bound. � Usado em sistemas Windows e Unix Escalonamento Circular com Prioridades �Possui duas variações � Prioridade estática � Prioridade dinâmica Escalonamento Circular com Prioridades Estado de Término Fila dos processos no estado de Pronto Prioridade P1 Prioridade P2 Estado de Criação UCP Término Prioridade Pn Criação Estado de Espera Preempção por tempo ou prioridade Escalonamento por Múltiplas Filas � Diversas filas de processo no estado de pronto, cada qual com uma prioridade especifica �Processos são associados às filas em função de características próprias � Importância para aplicação � Tipo de processamento� Tipo de processamento � Àrea de memória necessária �Vantagem � Convivência de mecanismos de escalonamento distintos � FIFO e CIRCULAR por exemplo Escalonamento por Múltiplas Filas � Preempção � Ocorre com base nas filas (fila com maior prioridade) � O SO só pode escalonar processos de uma fila caso a fila de prioridade maior estiver vazia � Desvantagem � Caso o processo altere seu comportamente no decorrer do tempo o processo não poderá ser redirecionado para uma fila mais adequada Escalonamento por Múltiplas Filas Fila de processos do sistema Fila de processos interativos Maior prioridade UCP Fila de processos batch Menor prioridade Escalonamento por Múltiplas Filas com realimentação � semelhante ao de múltiplas filas, porém os processos podem trocar de filas durante seu processamento Fila 1 (FIFO Adaptado) Preempção por tempo M a i o r P r i o r i d a d e M e n o r f a t i a d e t e m p o UCP Fila 2 (FIFO Adaptado) Preempção por tempo Fila 3 (FIFO Adaptado) Preempção por tempo Fila n (Circular) Preempção por tempo M e n o r P r i o r i d a d e M a i o r f a t i a d e t e m p o Escalonamento por Múltiplas Filas com realimentação �Vantagem � SO pode identificar dinamicamente o comportamento de cada processo , direcionando-os para filas com prioridade de execução �Escalonamento � Ocorre apenas quando todas as outras filas de prioridade mais alta � Ocorre apenas quando todas as outras filas de prioridade mais alta estiverem vazias. � A fatia de tempo em cada fila varia em função da prioridade � quanto maior a prioridade da fila menor a sua fatia de tempo
Compartilhar