Escalonamento SO PDF

Preview

Summary

Exercicios praticos de treino para a prova...

Description

Exercícios Aula 6 Gerência de Processador – Escalonamento Gabriel Alcantara de Paiva

RA: 21708345

1. Explique por que o Windows, o Linux e o Solaris implementam vários mecanismos de trancamento. Descreva as circunstâncias em que eles usam spinlocks, locks mutex, semáforos, locks mutex adaptativos e variáveis de condição. Em cada caso, explique por que o mecanismo é necessário. R: Os spinlocks são usados no kernel somente quando um lock é mantido por um curto período de tempo. O Solaris usa o método mutex adaptativo para proteger apenas os dados que são acessados por curtos segmentos de código. Ou seja, ele é usado se um lock for mantido por menos de algumas centenas de instruções. Se o segmento de código é maior do que isso, o método de aguardar em um spinlock é excessivamente ineficiente. Para esses segmentos de código mais longos, variáveis de condição e semáforos são usados. 2. Qual é o significado do termo espera em ação? Que outros tipos de espera existem em um sistema operacional? A espera em ação pode ser totalmente evitada? Explique sua resposta. R: Enquanto um processo está em sua seção crítica, qualquer outro processo que tente entrar em sua seção crítica deve entrar em um loop contínuo na chamada acquire. A espera em ação pode ser desviada, porém isto irá causar um significativo aumento de overhead. 3. Explique por que os spinlocks não são apropriados para sistemas com um único processador, mas são usados com frequência em sistemas multiprocessadores. R: Eles não são apropriados para sistemas de único processador porque a condição que removeria um processo do spinlock só pode ser obtida pela execução de um processo diferente. Se o processo não abandonar o processador, os outros não terão a oportunidade de

posicionar a condição do programa requerida para o primeiro processo avançar. Em um sistema com múltiplos processadores, outros processos são executados em outros processadores e, assim, não modificam o estado do programa para liberar o primeiro splinlock. 4. Mostre que, se as operações de semáforo wait ( ) e signal ( ) não forem executadas atomicamente, a exclusão mútua pode ser violada. R: Uma operação wait() decrementa atomicamente o valor associado a um semáforo. Se duas operações dela forem executadas atomicamente, é muito provável que ambas decrementem o valor do semáforo, violando assim a exclusão mútua. 5.

Mostre como um semáforo binário pode ser usado para implementar a exclusão mútua entre n processos.

R: Os n processos compartilham um semáforo, mutex, inicializando com 1. Cada processo é organizado como mostrado a seguir: do{ wait (mutex); //seção crítica signal (mutex); // seção restante }while(true); 6. Explique como se dá o escalonamento com o algoritmo Round Robin. R: O algoritmo Round Robin é um dos mais antigos e um dos mais simples, além de ser totalmente imune a problemas de starvation. Uma unidade de tempo, que é nomeada “quantum”, é definido pelo sistema, que determina o período de tempo entre cada sinal de interrupção. Todos os processos são armazenados em uma fila circular. 7. Faça um resumo do capítulo 6. (mínimo de 5 laudas)

Conceitos Básicos

Em um sistema com um único processador, só um processo pode ser executado de cada vez, os outros devem esperar até que a CPU esteja livre e possa ser realocada. O objetivo da multiprogramação é haver sempre algum processo em execução para maximizar a utilização da CPU. A ideia é simples. Um processo é executado até ter que esperar pela conclusão de alguma solicitação de I/O. Em um sistema de computação simples, a CPU permanece ociosa. Com a multiprogramação, tentamos usar esse tempo produtivamente. Vários processos são mantidos na memória ao mesmo tempo. Quando um processo precisa esperar, o sistema operacional desvincula a CPU deste processo e a designa a outro processo. Um scheduling desse tipo é uma função básica do SO. Quase todos os recursos do computador são alocados antes de serem usados. É claro que a CPU é um dos principais recursos do computador. Portanto, seu scheduling é essencial no projeto do SO. O scheduling da CPU é a tarefa de selecionar um processo em espera na fila de prontos e alocar a CPU para seu uso. Essa CPU é alocada ao processo selecionado pelo processo despachante, que é o módulo que passa o controle da CPU ao processo selecionado pelo scheduler de curto prazo.

Critérios de Scheduling

Diferentes algoritmos de scheduling da CPU têm diferentes propriedades, e a escolha de um algoritmo específico pode favorecer uma classe de processos em vez de outra. Na escolha dele, devemos considerar as propriedades dos diversos algoritmos. Muitos critérios têm sido sugeridos para a comparação de algoritmos de scheduling da CPU. As características usadas nela podem fazer uma grande diferença na avaliação do algoritmo como o melhor. Os critérios são: Utilização da CPU - É preciso manter a CPU ocupada. Conceitualmente, a utilização dela pode variar de 0 a 100%. Em um sistema real, ele deve variar de 40 a 90%. Throughput - Se a CPU está ocupada, o trabalho está sendo realizado. Uma medida de trabalho é o número de processos que são concluídos por unidade de tempo, chamado throughput. Tempo de turnaround -

Do ponto de vista de um processo

específico, o critério importante é quanto tempo ele leva para ser executado. O tempo entre o momento em que o processo é submetido e o momento de sua conclusão é o tempo de turnaround. Ele é a soma dos períodos gastos em espera para entrar na memória, na fila de prontos, em execução na CPU, e executando I/O. Tempo de espera - É a soma dos períodos gastos em espera na fila de prontos. Tempo de resposta - É o tempo que vai da submissão de uma solicitação até a primeira resposta a ser produzida. Essa medida, chamada tempo de resposta, é o tempo necessário para que

comece o envio de respostas e não o tempo necessário à exibição da resposta.

Algoritmos de Scheduling

Existem

alguns

tipos

de

scheduling,

o

scheduling

“primeiro-a-chegar, primeiro-a-ser-atendido” (Em inglês, First Come, First Served - FCFS) é o mais simples algoritmo de scheduling, porém ele pode fazer com que processos curtos tenham de esperar por

processos

muito

longos,

além

de

não

poderem

ser

interrompidos pela CPU ou por interrupções de I/O. O scheduling “menor-job-primeiro” (Em inglês, Shortest Job First - SJF) é comprovadamente ótimo, fornecendo o mais curto tempo médio de espera. Entretanto, a implementação desse scheduling é difícil, porque é complicado prever a duração do próximo pico de CPU. O algoritmo SJF é um caso especial do algoritmo geral de scheduling por prioridades que basicamente aloca a CPU ao processo de prioridade mais alta. Tanto o scheduling por prioridades quanto o scheduling SJF podem sofrer de inanição. O envelhecimento é uma técnica que impede essa inanição. O scheduling round-robin (RR) é mais apropriado para um sistema de tempo compartilhado (interativo). Esse scheduling aloca a CPU ao primeiro processo na fila de prontos durante q unidades de tempo, em que q é o quantum de tempo. Após q unidades de tempo, se o processo ainda não tiver abandonado a CPU, ele é interceptado e inserido no final da fila de prontos. O principal problema desse algoritmo é a seleção do q, quantum de tempo. Se

ele é longo demais, o scheduling RR degenera para o scheduling FCFS. Se ele é muito curto, o overhead do scheduling, na forma de tempo de mudança de contexto, torna-se excessivo. O algoritmo FCFS não tem preempção (Não pode sofrer interrupção), enquanto que o algoritmo RR, tem preempção (Pode sofrer interrupção). Os algoritmos SJF e por prioridades podem ou não ter preempção. Os algoritmos de filas multiníveis permitem que diferentes algoritmos sejam usados para diferentes classes de processos. O modelo mais comum inclui uma fila interativa de foreground que usa o scheduling RR e uma fila batch de background que usa o scheduling

FCFS.

Existe também as filas multiníveis com

retroalimentação que permitem que os processos migrem de uma fila para outra.

Scheduling para Múltiplos Processadores

Muitos sistemas de computação contemporâneos dão suporte a múltiplos processadores e permitem que cada processador faça o seu próprio scheduling de forma independente. Normalmente, cada processador mantém sua própria fila privada de processos (ou threads), todos disponíveis para serem executados. As questões adicionais

relacionadas

processadores

incluem

com a

o

scheduling

com

múltiplos

afinidade com o processador, o

balanceamento de carga e o processamento multicore.

Scheduling de Tempo Real

Um sistema de computação de tempo real requer que os resultados cheguem dentro de um limite de tempo determinado, os resultados que chegam após esse limite de tempo determinado são inúteis. Sistemas de tempo real crítico, que precisam de computação rápida, devem garantir que tarefas de tempo real sejam atendidas dentro do limite de tempo, sem atrasos. Sistemas de tempo real não crítico possuem uma quantidade menor de restrições, atribuindo às tarefas de tempo real uma prioridade de scheduling mais alta do que a de outras tarefas. Os algoritmos de scheduling de tempo real incluem o scheduling de taxa monotônica e o do Limite-de-Tempo-Mais-Cedo-Primeiro (EDF - Earliest-Deadline-First). O scheduling de taxa monotônica é atribuída às tarefas que precisem da CPU com mais frequência uma prioridade mais alta do que a de tarefas que precisem da CPU com menos frequência. O

scheduling

do

Limite-de-Tempo-Mais-Cedo-Primeiro

atribui

prioridades de acordo com o vencimento dos limites de tempo, ou seja, quanto mais cedo o limite de tempo, maior a prioridade. O scheduling de cotas proporcionais divide o tempo do processador em cotas e atribui a cada processo um número de cotas, garantindo assim a cada processo uma cota proporcional de tempo da CPU. A API POSIX pthreads também fornece vários recursos para o scheduling de threads de tempo real.

Scheduling nos Sistemas Operacionais

Os sistemas operacionais que suportam threads no nível do kernel devem designar threads para execução, e não processos. É esse o caso do Solaris e do Windows. Esses dois sistemas designam threads para serem executadas usando algoritmos de scheduling baseados em prioridades com preempção e incluem o suporte a threads de tempo real. O scheduler de processos do Linux também usa um algoritmo baseado em prioridades com suporte a tempo real.

Os

algoritmos

de

scheduling

desses

três

sistemas

operacionais normalmente favorecem os processos interativos sobre os processos limitados por CPU.

Avaliação de Algoritmos

Os algoritmos de scheduling possuem uma grande variedade, a grande variedade desses algoritmos demanda o uso de métodos para selecionar o melhor deles, dependendo da tarefa. Os métodos analíticos usam uma análise matemática para determinar o desempenho

de

um

algoritmo. Os métodos de simulação

determinam o desempenho fazendo uma simulação do algoritmo de scheduling em uma amostra de processos “representativa” e calculando o desempenho resultante. Entretanto, a simulação pode fornecer no máximo uma aproximação do desempenho do sistema real. A única técnica confiável para a avaliação de um algoritmo de scheduling é implementar o algoritmo em um sistema real e monitorar o seu desempenho em um ambiente do “mundo real”....