Escalonamento de Processos em Sistemas Operacionais

SISTEMAS SISTEMAS OPERACIONAIS OPERACIONAIS SISTEMAS SISTEMAS OPERACIONAIS OPERACIONAIS Parte 05 Escalonamento de Processos Professor Eduardo Xavier Parte 05 Escalonamento de Processos Professor Eduardo Xavier GERENCIAMENTO DO PROCESSADOR GERENCIAMENTO DO PROCESSADOR A gerência do processador é uma das atividades mais importantes do sistema operacional pois estabelece critérios para definir qual processo fará uso do processador Estes critérios compõem a política de escalonamento A rotina do SO encarregada de implementar a política de escalonamento se chama Escalonador Scheduler A rotina do SO encarregada de implementar a troca de contexto de processos obedecendo as regras do Escalonador se chama Dispatcher GERENCIAMENTO DO PROCESSADOR GERENCIAMENTO DO PROCESSADOR Critérios de Escalonamento Cada sistema operacional define quais aspetos são mais importantes para seu funcionamento de acordo com os objetivos de seu projeto As principais métricas utilizadas são Utilização do processador O percentual de ocupação da CPU ao longo do tempo Throughput Representa o número de processos executados em determinado intervalo de tempo Quanto maior o throughput maior o número de tarefas executadas Tempo de processador Tempo que um processo leva no estado de executando durante seu processamento GERENCIAMENTO DO PROCESSADOR GERENCIAMENTO DO PROCESSADOR As principais métricas utilizadas são continuação Tempo de espera Tempo total que um processo permanece esperando na fila de prontos aguardando ser executado A redução do tempo de espera é algo desejado na maioria das polpiticas de escalonamento Tempo de turnaround Tempo que um processo leva desde sua criação até seu término As políticas de escalonamento tentam minimizar este tempo Tempo de resposta Tempo decorrido entra a requisição da tarefa ao sistema e a exibição de sua resposta DEFINIÇÃO DE ESCALONAMENTO DEFINIÇÃO DE ESCALONAMENTO O que é Escalonamento de Processos É a forma como os processos são distribuídos para execução nos processadores ou seja de que forma os processos são ordenados nas filas de execução Preempção É a mudança de processo que está controlando o processador DEFINIÇÃO DE ESCALONAMENTO DEFINIÇÃO DE ESCALONAMENTO Existem duas categorias de escalonamento Escalonamento Não Preemptivo Seu funcionamento é mais simples O controle do processador permanece com um mesmo processo até que este termine Isso acontece independente do uso que o processo faz da CPU Ocorre em sistemas que adotam o processamento em Batch lote Escalonamento Preemptivo Seu funcionamento é mais complexo O controle da CPU pode ser passado a outro processo em função de alguma regra de funcionamento estabelecida exemplo fatia de tempo Ocorre em sistemas que adotam Time Sharing ou Tempo Real MUDANÇA DE CONTEXTO MUDANÇA DE CONTEXTO Quando um escalonamento preemptivo decide mudar o processo que está controlando a CPU ocorre o que se chama de Mudança de Contexto A mudança de contexto é o procedimento de salvar as informações do processo atual para que ele volte a ser executado a partir deste ponto no futuro e carregar as informações do novo processo que será executado O que se chama aqui de contexto são todas as informações existentes em cada PCB Process Control Block MUDANÇA DE CONTEXTO MUDANÇA DE CONTEXTO Tanto o PCB do antigo processo quanto o PCB do novo processo são armazenados na tabela de processos que está carregada na memória principal A eficiência do escalonamento de um sistema operacional depende muito do tamanho da fatia de tempo dedicada a cada processo Fatias de tempo muito pequenas obrigam o sistema operacional a executar muitas mudanças de contexto Fatias de tempo muito grandes podem gerar um tempo de espera elevado para os processos que estão aguardando QUANTUM QUANTUM Quantum é o nome que se dá a cada fatia de tempo dedicada à execução de um determinado processo IMPORTANTE Não inclui o tempo necessário para a mudança de contexto A mudança de contexto propriamente dita ocorre em duas etapas TPC Tempo de Preservação de Contexto Tempo que leva para o salvamento do PCB do processo anterior na tabela de processos TRC Tempo de Recuperação de Contexto Tempo que leva para a recuperação do PCB do processo novo da tabela de processos QUANTUM QUANTUM Podemos representar o uso de cada processador ao longo do tempo da seguinte maneira ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO FIFO FIRSTINFIRSTOUT FIFO FIRSTINFIRSTOUT No algoritmo FIFO também chamado de FCFS FirstComeFirst Served o processo que chegar primeiro ao estado de pronto será selecionado para ser atendido Ou seja ele funciona por ordem de chegada na fila de prontos Existe uma única fila e todo processo novo que chega seja ele recém criado ou um já existente que tenha acabado de mudar para o estado de pronto entra no final desta fila ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO FIFO FIRSTINFIRSTOUT FIFO FIRSTINFIRSTOUT Apesar de ser uma solução simples o FIFO possui algumas desvantagens É impossível prever quando um processo será executado depende de quem está antes dele na fila Nesta solução os processos CPU Bound levam vantagem sobre os processos IOBound Originalmente esse algoritmo foi criado como não preemptivo mas com a popularização de sistemas timesharing surgiu a versão preemptiva a preempção ocorre em momentos de IO do processo ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO SJF SHORTESTJOBFIRST SJF SHORTESTJOBFIRST O SJF também é conhecido como SPN SortestProcess Next e funciona com uma única fila ordenada pelo consumo estimado de processador Quanto menor o consumo estimado do processo mais à frente da fila esse processo será colocado A estimativa é fornecida por quem submete o processo para a execução Isso atende bem o processamento em batch pode ser problemático para sistemas interativos ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO SJF SHORTESTJOBFIRST SJF SHORTESTJOBFIRST O SJF também foi iniciamente criado como não preemptivo e foi posteriormente adaptado para timesharing A estimativa então pode ser baseada no cálculo a partir do consumo de CPU nas vezes anteriores do processo A vantagem do SJF sobre o FIFO é a redução do tempo médio de turnaround dos processos porém há risco de acontecer starvation espera demasiada por CPU para processos que possuem tempo de processador muito longos ou são CPUBound Uma implementação preemptiva do SJF se chama SRT Shortest RemainingTime onde toda vez que um processo na fila de prontos tiver uma estimativa menor que o processo em execução o SO realiza uma preempção e concede o processador ao novo processo Aqui é o SO que calcula as estimativas e o risco de starvation continua ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO COOPERATIVO ESCALONAMENTO COOPERATIVO O escalonamento Cooperativo é uma tentativa de aumentar o grau de multiprogramação em políticas de escalonamento não preemptivas Nesta solução um processo em execução pode liberar o processador voluntariamente e retornar à fila de prontos permitindo que um novo processo seja escalonado e proporcionando uma melhor distribuição de CPU Cabe ao processo verificar a fila de prontos e decidir isso Como o SO não participa disso o sucesso dessa estratégia depende da programação dos processos ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ROUND ROBIN ESCALONAMENTO CIRCULAR ROUND ROBIN ESCALONAMENTO CIRCULAR O escalonamento Round Robin se parece com o FIFO porém com um detalhe a mais processos ficam em execução apenas durante uma fatia de tempo quantum de cada vez e são retiradas do processador voltando para a fila de prontos ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ROUND ROBIN ESCALONAMENTO CIRCULAR ROUND ROBIN ESCALONAMENTO CIRCULAR O tamanho da time slice influencia na quantidade de preempções A grande vantagem dessa abordagem é evitar que um único processo monopolize a CPU A desvantagem é que processos CPUbound são beneficiados processos IO bound nem sempre utilizam o quantum completo ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ROUND ROBIN ESCALONAMENTO CIRCULAR ROUND ROBIN ESCALONAMENTO CIRCULAR Uma variação do Round Robin que tenta reduzir a desvantagens de processos IObound é chamada de Escalonamento Circular Virtual onde processos que saem do estado de espera vão para uma fila auxiliar de prontos O SO só seleciona processos da fila normal se não houver processos aguardando na fila auxiliar O quantum desses processos é diferente É o tempo normal do sistema menos o que o processo usou da última vez que foi escalonado da fila de prontos original ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ROUND ROBIN ESCALONAMENTO CIRCULAR ROUND ROBIN ESCALONAMENTO CIRCULAR Escalonamento Circular Virtual ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR PRIORIDADE ESCALONAMENTO POR PRIORIDADE O escalonamento por Prioridades é um escalonamento preemptivo onde cada processo recebe um valor denominado prioridade de execução Quem possui a maior prioridade é executado primeiro e processos com prioridades iguais obedecem o critério FIFO Não existe conceito de fatia de tempo nesta solução O processo que está na CPU só sai quando Sua lógica pede uma mudança volutária de estado Um processo com maior prioridade chega nas filas de prontos o SO verifica isso e tempos em tempos Há uma versão não preemptiva desse escalonamento onde o SO apenas arruma as filas de acordo com as prioridades As prioridades podem ser estáticas ou dinâmicas durante a execução do processo ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR PRIORIDADE ESCALONAMENTO POR PRIORIDADE O principal problema desta solução é o risco de starvation mas isso pode ser contornado com a aplicação da técnica de aging envelhecimento onde processos que estão a mais tempo rodando vão gradualmente perdendo prioridade ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO CIRCULAR COM PRIORIDADES ESCALONAMENTO CIRCULAR COM PRIORIDADES Este escalonamento é muito semelhante ao escalonamento por prioridades explicado anteriormente A única diferença é que nesta abordagem é acrescentado o conceito de fatia de tempo quantum que também causa preempção nos processos executantes ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR MÚLTIPLAS FILAS ESCALONAMENTO POR MÚLTIPLAS FILAS No escalonamento por multiplas filas multilevel queue scheduling existem diversas filas de prontos cada uma reservada para atender processos com determinadas características Cada processo novo é encaminhado para uma das filas de acordo com suas características próprias exemplo consumo de memória tipo de processamento importância para a aplicação As filas possuem prioridades diferentes e cada uma prossui seu próprio mecanismo de funcionamento FIFO Circular que pode ser diferente das demais Os processos não possuem prioridade só as filas Cada processo que está em uma fila só pode ser escalonado se as filas com maior prioridade estiverem vazias Se um novo processo chegar em uma delas ocorrerá uma preempção afinal a fila dele tem mais prioridade que o processo que está sendo atualmente sendo executado ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR MÚLTIPLAS FILAS ESCALONAMENTO POR MÚLTIPLAS FILAS O problema desta solução é que o processo é associado a uma fila na sua criação e não pode mudar isso até seu término Se o processo mudar seu comportamento durante a execução ficará rodando na fila errada pois não poderá ser reenquadrado ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR MÚLTIPLAS FILAS COM ESCALONAMENTO POR MÚLTIPLAS FILAS COM REALIMENTAÇÃO REALIMENTAÇÃO O MFQ Multilevel Feedback Queue ou escalonamento por múltiplas filas com realimentação também utiliza várias filas mas os processos podem mudar de fila durante sua execução O SO identifica o comportamento do processo dinamicamente e reposiciona o processo em uma fila mais adequada Todas as filas funcionam com mecanismo FIFO preemptivo exceto a de menor prioridade que utiliza Round Robin Quanto maior a prioridade da fila menor é a duração de seu quantum Ou seja quem tem menos prioridade recebe fatias de tempo maiores para usar o processador ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR MÚLTIPLAS FILAS COM ESCALONAMENTO POR MÚLTIPLAS FILAS COM REALIMENTAÇÃO REALIMENTAÇÃO No MFQ todos os processos iniciam no final da fila de maior prioridade e só são rebaixados para a fila imediatamente inferior envelhecimento ao sofrerem uma preempção por tempo Caso o processo saia do processador em virtude de uma operação de IO muda para estado em espera o mesmo volta para a mesma fila de prontos em que estava antes quando terminar a operação solicitada Os problemas dessa solução são Existe uma maior complexidade de implementação do escalonamento Caso um processo mude de CPUbound para IObound pode ser prejudicado pelo rebaixamento nas filas ALGORITMOS DE ESCALONAMENTO ALGORITMOS DE ESCALONAMENTO ESCALONAMENTO POR MÚLTIPLAS FILAS COM ESCALONAMENTO POR MÚLTIPLAS FILAS COM REALIMENTAÇÃO REALIMENTAÇÃO MFQ POLÍTICAS DE ESCALONAMENTO POLÍTICAS DE ESCALONAMENTO Em sistemas de tempo compartilhado Normalmente são sistemas interativos onde o tempo de resposta ai usuário é fundamental por isso é importante um equilíbio no consumo de recursos para oferecer um balancemamento equitativo de CPU entre os processos Atualmente a maioria dos SOs desta categoria adota algum tipo de escalonamento circular com prioridades dinâmicas Em sistemas de tempo real Esta categoria de SOs exige que sejam obedecidos limites rígidos de tempo Em função disso geralmente não se usa o conceito de fatias de tempo e são adotados escalonamentos por prioridade estática Referências Bibliográficas Referências Bibliográficas Arquitetura de Sistemas Operacionais Francis Machado Luiz Maia 4a Edição Capítulo 8 Gerência do Processador