Baixe o app para aproveitar ainda mais
Prévia do material em texto
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 55 First-in-First-Out – FIFO (Primeiro que entra é o primeiro que sai) que também é conhecido como first come, first served - FCFS (Primeiro que chega é o primeiro a ser servido). Esse pode ser considerado o algoritmo de escalonamento mais simples e que não é preemptivo. À CPU é atribuída uma lista de processos que são executados na ordem de chegada e, basicamente, há uma fila única de processos prontos. Podemos dizer também que o processo que chega primeiro ao estado de pronto é o selecionado para execução. Esse algoritmo é bastante simples porque é necessária somente uma fila. Os processos que passam para o estado de pronto entram no final da fila, enquanto os processos que estão sendo executados entram em estado de bloqueado. O próximo da fila está na posição do início e são escalonados. Esse algoritmo é fácil de entender e de implementar. Podemos Aula 07 TIPOS DE ESCALONAMENTO Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 56 considerá-lo como um algoritmo justo, pois ele pode ser comparado a uma fila de pessoas para comprar ingressos de um show, por exemplo, Repare na figura 1 que se segue, como é simples entender esse tipo de algoritmo. Figura 1 Figura 2 Apesar de ser um algoritmo bastante simples, esse tipo de escalonamento apresenta algumas deficiências. Um dos principais problemas é a possibilidade de prever quando o processo será executado, já que isso depende do tempo de processamento dos outros processos que se encontram na frente. Como esse tipo de escalonamento respeita somente a ordem de chagada, ele não tem uma preocupação com o tempo de espera do processador. Vamos fazer uma pequena comparação com processos semelhantes, mas com um tempo médio diferenciado. Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 57 Vamos analisar a figura 2 na página anterior. Nas primeiras entradas, o processo maior está entrando por último. Portanto, um processo menor pode levar mais tempo que o esperado para ser processado. Ele só se utiliza do processador depois dos outros processos, inclusive o maior, que vai utilizar por mais tempo a CPU. Já na segunda entrada dos processos podemos perceber que os processos menores entraram primeiro para serem processados. Assim, eles não precisarão esperar muito tempo. A única diferença que se segue na figura é a da entrada dos processos na fila de pronto. O tempo médio de espera dos processos da primeira entrada é igual a (0+10+14)/3 = 8 u.t. e o tempo médio da segunda entrada de processos é (7+0+4)/3 = 3,7 u.t. A diferença que se dá entre as médias de tempo é bastante significativa, e é justificada pela diferença dos tempos de processador entre os processos. Outro problema nesse tipo de algoritmo é que os processos de CPU-bound levam vantagem sobre os de E/S-bound. Isso porque no caso de se ter um processo de E/S-bound mais importante do que um de CPU-bound, não é possível tratar esse tipo de diferença entre os processos. O tipo de escalonamento FIFO é um algoritmo implementado do tipo não preemptivo. Inicialmente foi desenvolvido para sistemas monoprogramáveis, com processamento Bach, e se torna ineficiente se for aplicado em ambiente interativo de tempo compartilhado. De certo modo, sistemas em lote permitem um escalonamento em três níveis diferentes, ou seja, quando os jobs chegam ao sistema eles são adicionados em uma fila de entrada, armazenados em disco, e tem-se um escalonador de admissão que faz a decisão de qual dos jobs será adicionado no sistema. Os outros jobs são mantidos na fila de entrada por um momento até que sejam selecionados para serem adicionados ao sistema. Um algoritmo feito para admissão pode ser uma mescla de jobs orientados à computação com jobs orientados à E/S. Mas pensando bem, os jobs curtos poderiam ser adicionados com mais agilidade. Enquanto isso, os jobs mais longos ficam esperando, pois o escalonador de admissão tem a liberdade de manter alguns jobs na fila de entrada e pode colocar depois os jobs que chegam, se estiverem de acordo com a política de escalonamento do algoritmo. Quando o job é adicionado no sistema, o processo é criado para ele. Assim, ele passa a competir pela CPU, mas o que pode acontecer é que se houver um número muito grande de processos, pode não haver espaço suficiente para todos na memória. Por isso, alguns processos devem ser levados para o disco. O segundo nível de escalonamento é que decide quais processos devem ser mantidos na memória e quais permanecerão em disco. Podemos chamar esse tipo de escalonador de escalonador de memória. Como o próprio nome sugere, é ele que decide qual processo deve ficar na memória e qual deve permanecer em disco. Observe na figura que se segue como pode ocorrer o escalonamento em três níveis. Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 58 Escalonamento Shortest-Job-First (SJF), ou seja, o job mais curto primeiro. Mas consideremos 4 jobs, sendo “A,B,C,D”, com tempos de processamento de 8,4,4,4, respectivamente e vamos deixar que o escalonador escolha o processo que tenha o tempo mais curto para processar primeiro. Ao executar nessa ordem, o tempo de retorno para o processo “A” é de 8 minutos, para “B” é de 12 minutos, para “C” é de 16 minutos e para “D” sequencialmente é de 20 minutos, o que resulta em uma média de 14 minutos. Considere agora a execução desses processos mas com a seleção do processo mais curto primeiro. Os tempos de retorno agora são 4, 8, 12 e 20 minutos, pois agora ele tem uma média de 11 minutos. Devemos nos atentar que o job mais curto primeiro é muito bom somente se todos os Jobs estiverem disponíveis simultaneamente. Com a versão de um algoritmo que podemos dar a distinção de o próximo job de menor tempo restante, ou seja, o próximo job mais curto é o primeiro (shortest remaining time next). Esse algoritmo necessita saber previamente o tempo de execução do job e quando chega um novo job. O seu tempo total é comparado ao tempo restante do job que está sendo executado no momento. Se esse tempo for menor, o job que está em execução é interrompido e o job menor é executado. Essa versão do algoritmo é implementada como preemptivo. Essa implementação permite que novos jobs tenham um melhor desempenho. ESCALONAMENTO COOPERATIVO A implementação por escalonamento cooperativo é desenvolvida para que seja alcançado um grau maior em aplicações de escalonamento que não possuem mecanismo de preempção, como o FIFO e o SJF, que são não preemptivos. Para isso, um processo em execução pode, voluntariamente, liberar a CPU e retornar à fila de pronto, dando, assim, a possibilidade de que outro processo seja escalonado para o uso da CPU. Isso Figura 3 Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 59 permite melhor uso da CPU. O que se destaca nesse tipo de algoritmo é que a liberação da CPU não é responsabilidade do sistema operacional, e sim exclusiva do processo que está em execução, que de maneira cooperativa libera a CPU para outro job. Com essa implementação de escalonamento, o processo que está em execução faz uma verificação periodicamente em uma fila de mensagens para determinar a existência de jobs na fila de pronto. Mas isso pode causar alguma dor de cabeça, pois como a interrupção não é de responsabilidade do sistema operacional e sim do processo que está em execução, o que pode ocorrer é um processo não verificar a fila de mensagens. Nesse caso, os outros processos não terão a chance de ser executados até a liberação da CPU pelo job em execução. Isso pode causar um problema para a multiprogramação cooperativa, na medida em que uma aplicação pode ficar por muito tempo em processamento, utilizando a CPU. ESCALONAMENTO CIRCULAR Escalonamento circular ou (round Robin sheduling), é do tipo preemptivo. É um tipo de escalonamento produzido para sistemas de tempo compartilhado. Esse algoritmoé muito semelhante ao sistema do tipo FIFO (Fisrt-in-First-out), mas com uma diferença, a de que quando o processo passa para o estado de execução ele tem um tempo predeterminado, ou seja, um tempo limite de uso do processador, que é denominado fatia de tempo (Time-slice) ou, também, conhecido como quantum. No escalonamento circula quando o processo é escalonado para a sua execução. Logo uma nova fatia de tempo é determinada. Caso essa fatia de tempo seja excedida, o sistema operacional interrompe o processo que está em execução, salva todo seu contexto e direciona o processo para o final da fila. Todo esse mecanismo é denominado de preempção por tempo. Esse sistema de escalonamento circular é considerado um dos mais simples e mais justos, porque a cada processo é atribuído o seu intervalo de tempo e, quando termina o seu tempo, ele passa para o final da fila e outro processo se utiliza da CPU, já com a sua fatia de tempo predeterminada. Observe na figura que se segue e veja que a fila de processos em estado de pronto é tratada como uma fila circular. O escalonamento é feito normalmente quando o processo da fila está em estado de pronto. O processo ficará em execução até que ele conclua o processamento ou que sua fatia de tempo termine. Aí ele sofre uma preempção pelo sistema operacional. Depois disso, outro processo é escalonado, tendo como critério a política de FIFO. Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 60 Cada sistema operacional tem sua política de tempo estabelecida para a fatia. Essa fatia de tempo pode variar de 10 a 100 milissegundos, valor que afeta diretamente o desempenho do sistema de escalonamento circular. Pode ser que com uma fatia de escalonamento muito alta, esse algoritmo caia no mesmo comportamento do algoritmo de escalonamento FIFO. Por outro lado, se tiver uma fatia de tempo muito pequena, pode ser que tenhamos um problema como um número muito alto de preempções, o que ocasionaria a baixa no desempenho do sistema, afetando, assim, o tempo de turnaround dos processos. A grande vantagem do escalonamento circular é permitir que um processo não fique o tempo todo usando a CPU, sendo que a quantidade de tempo de utilização é igual à fatia de tempo definida no sistema. O escalonamento circular é muito adequado para sistemas de tempo compartilhado em que há diversos processos interativos concorrendo para o uso da CPU. Uma das desvantagens da utilização desse sistema de escalonamento é que os processos de CPU, os CPU-bound têm vantagens sobre os processos de E/S, os E/S-bounds, devido à característica do sistema. Os processos CPU-bounds tendem a utilizar, por completo, a fatia de tempo, enquanto os processos E/S-bounds estão mais possibilitados a passar para o estado de espera antes de sofrer preempção por tempo, o que influencia em uso desigual do processador entre os processos. Para amenizar a situação, um aprimoramento nesse tipo de escalonamento é colocado, como mostra a figura abaixo. É criada uma fila auxiliar de pronto, ou seja, ele sai da fila e do estado de espera e vai para outra fila em estado de pronto. Tais processos, da fila auxiliar, têm preferência no escalonamento em relação à outra fila. O escalonador só escalona um processo da fila de pronto quando a fila auxiliar estiver vazia. E quando o processo é escalonado a partir da fila auxiliar, a sua fatia de tempo é calculada como sendo o valor da fatia de tempo do sistema, menos o tempo de processador que o processo utilizou na última vez em que foi escalonado a partir da primeira fila, a fila de pronto. Figura 4 Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 61 Esse algoritmo tem um grau maior de complexidade, mas com a vantagem de que ele balanceia melhor o uso do processador, o que o torna mais equilibrado. ESCALONAMENTO POR PRIORIDADE Podemos observar em uma fila de pessoas, que algumas podem ter prioridade de atendimento. O mesmo pode acontecer com o escalonamento por prioridade. Em filas onde não se tem prioridade, cada um se utiliza do serviço com o tempo necessário para resolver o seu problema, igual ao que ocorre com os processos em um sistema de escalonamento sem prioridade. Em computadores que possam ter apenas um proprietário, podem existir vários processos, mas, alguns dos processos podem ter uma importância maior que o outro. Pode-se dizer, então, que alguns processos têm mais prioridade de processamento que outros. Nesse tipo de escalonamento, o processo que está na fila em seu estado de pronto e que tem maior prioridade, é sempre o escolhido para o uso da CPU. E os processos que têm valores iguais são escalonados seguindo critérios do tipo de escalonamento FIFO. Este tipo de escalonamento é preemptivo. Sua preempção é associada ao valor de cada processo, que é chamado de prioridade de execução. Nesse tipo de escalonamento, o uso de fatia de tempo não existe e como consequência, o processo em execução não pode ter nenhuma preempção por tempo. Nesse tipo de escalonamento, o uso da CPU só terá perda caso o processo tenha uma mudança voluntária para o estado de pronto, ou se um processo com maior prioridade passar para o estado de pronto. No caso de o processo que passar para o estado de pronto tiver algum processo em execução, mas com uma prioridade menor, o sistema operacional se encarrega de interromper o processo corrente, salvar seu contexto e colocá-lo em estado de pronto. Esse tipo de escalonamento é chamado de preempção por prioridade. Após isso, o processo com maior prioridade é escalonado. Figura 5 Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 62 Observe a figura 6, para cada tipo de prioridade existe uma fila de processos em estado de pronto. O escalonamento ocorre na medida em que o processo dá mais prioridade e está no estado de pronto. Assim ele é escalonado e colocado em execução até o seu término ou até que fique em estado de espera voluntariamente ou que ocorra uma preempção, no caso de um processo com mais prioridade estar na fila em estado de pronto. Veja na figura, em uma escala de prioridade, em que o grau de maior prioridade tem o valor 5 e o de menor, valor 1. O escalonamento por prioridade pode ser implementado de modo que não se use a preempção. Pode ser de uma maneira simplificada, apenas colocando os processos com maior prioridade na frente da fila, em estado de pronto, e os processos deixam o estado de execução apenas quando terminarem o uso da CPU. Figura 6 Figura 7 Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 63 Cada sistema operacional tem a sua própria faixa de valores de prioridade. Alguns têm valores de 0 a 31, sendo que o de valor maior tem prioridade. Os outros têm o valor de 0 a 127, mas os de menor valor têm prioridade. A prioridade de execução é classificada por características do software de um processo, e pode ser classificada estática ou dinamicamente. Com a prioridade estática, o processo não tem o seu valor de priorização alterado. Por outro lado, a prioridade dinâmica pode ser ajustada de acordo com os critérios definidos pelo sistema operacional. Cada processo do sistema tem suas características e critérios de prioridade com possibilidade de alterar o valor da prioridade do processo. Isso permite que se possa ajustar os critérios de escalonamento. Claro que isso ocorre de acordo com o comportamento de cada processo no sistema. Um problema nesse tipo de escalonamento é causado por processos de baixa prioridade, pois eles podem não ser escalonados, ficando permanentemente na fila de pronto. Esse problema é denominado starvation, e pode ser resolvido principalmente em sistemas que são implementados com prioridade dinâmica, é a técnica de aging. Essa solução funciona da seguinte maneira: ele incrementa gradualmente a prioridade dos processos que permanecem na fila por um longo período de tempo. Esse tipo de escalonamento tem a capacidade de diferenciaros processos por meio de critérios de importância, e os processos com um grau maior de prioridade têm a preferência para serem escalonados. Esse tipo de técnica é muito útil para sistemas de tempo real, em aplicações de controle de processo e também em aplicações de sistemas de tempo compartilhado. ESCALONAMENTO CIRCULAR COM PRIORIDADE É um tipo de escalonamento que tem como implementação a fatia de tempo e a prioridade de execução ligadas a cada processo. Os processos, nesse modo de escalonamento, ficam no estado de execução até o término do seu processamento, até que voluntariamente ele passa para o estado de espera ou que aconteça uma preempção por tempo ou por prioridade. Com isso, espera-se melhor distribuição do processador entre os processos, e os processos de E/S-bound recebem do administrador do sistema valores maiores de prioridade do que os de processos de CPU-bound. Com isso, o sistema operacional se torna mais justo entre esses tipos de processos CPU-bound e E/S-bound. É uma forma de compensar os processos de E/S-bound, compartilhando o processador de forma mais igualitária. Esse tipo de escalonamento é muito utilizado em sistemas de tempo compartilhado. No escalonamento circular com prioridade tem-se duas modalidades, do tipo dinâmica ou estática. No escalonamento circular com prioridade estática, sua prioridade Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 64 é dada através do contexto de software de cada processo que permanece sem alteração durante a sua existência. Já no escalonamento circular com prioridade dinâmica, pode ser possível a alteração da prioridade de um processo dinamicamente, que pode ser ocasionado pelo administrador do sistema ou até mesmo por algumas políticas do próprio sistema operacional. Algum ajuste dinâmico de prioridade dos processos são definidos pelo sistema operacional. Para isso é tirada uma base do comportamento dos processos. Esse é um exemplo de comportamento adaptativo. Com isso, é possível um melhoramento no balanceamento e na utilização da CPU por processos de diferentes perfis. Algumas operações são mais lentas que outras. Isso faz com que o processo permaneça por mais tempo no estado de espera. Com isso, os processos que permanecem por mais tempo na espera têm um ganho no uso do processador, para que seja compensado em relação aos processos de CPU-bound. Devemos lembrar que os processos de CPU-bounds não são prejudicados por esse tipo de escalonamento, pois eles podem ser executados durante o tempo de espera dos processos de E/S-bound. FILAS MÚLTIPLAS O escalonamento por múltiplas filas (multilevel queue scheduling) é aquele que tem várias filas de processo pronto e cada uma das filas com a sua prioridade definida. A cada processo é designada a fila apropriada, através de características próprias, contando com a importância da aplicação, o tipo de processamento ou a área de memória necessária. Assim, o processo é designado à sua fila. Como vimos que os processos possuem características distintas, um único mecanismo torna-se inviável para atender a todos os tipos de processos. Por essa razão há uma grande vantagem no tipo de escalonamento de múltiplas filas. A sua grande vantagem é que se tem tipos de mecanismos de escalonamento diferentes em um sistema operacional. Cada fila possui o seu próprio tipo, pois alguns processos podem ser escalonados por um mecanismo de FIFO e outro pode ser escalonado no tipo de escalonamento circular. O mecanismo não dá prioridade aos processos, e isso fica associado à fila. Nesse tipo de sistema, o processo sofre preempção, mas isso se um outro processo entra em fila e esse processo tenha uma prioridade maior do que aquilo que está em execução. O sistema operacional somente escalona processos de uma determinada fila, caso todas as outra, com maior prioridade estejam vazias. Veja na figura 8, logo abaixo, uma exemplificação de como pode ficar um escalonamento por filas múltiplas. Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 65 Escalonamento por múltiplas filas com Realimentação é um tipo de escalonamento quase igual ao de múltiplas filas. A diferença é que um funciona com realimentação e os processos podem mudar de fila durante o seu processamento. Sua grande vantagem é permitir que o sistema operacional identifique dinamicamente o comportamento do processo e o coloque na fila de prioridade e, também, o tipo de escalonamento mais adequado. Permite que o processo seja colocado em diversas filas, fazendo com que o sistema operacional implemente um mecanismo adaptativo. ATIVIDADES As atividades referentes a esta aula estão disponibilizadas na ferramenta “Atividades”. Após respondê-las, envie-nas por meio do Portfólio- ferramenta do ambiente de aprendizagem UNIGRAN Virtual. Em caso de dúvidas, utilize as ferramentas apropriadas para se comunicar com o professor. Figura 8 Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN 66
Compartilhar