SO1 – Escalonamento – Conceitos e Algoritmos

Escalonamento – Conceitos e Algoritmos

a multiprogramação simples consegue-se com:
dispositivos de memoria secundária e rápida;
boa gestão de E/S por parte do SO
mecanismo de gestão e partilha de memória
mecanismos no SO para partilhar e gerir recursos partilhados na maquina, entre todos os programas que estão em execução

a multiprogramação simples (não preemptiva: que prevê ou antecipa situações),
baseia-se na cedência voluntária (que pode ou não acontecer) do CPU, por parte do programa que está a ser executado

a multiprogramação preemptiva (ou “interactiva” ou “de tempo partilhado”),
o sistema força a cedência do CPU por parte do programa actualmente em execução, passado a CPU a outro programa e posteriormente voltando ao programa inicial

exemplo de algortimos preemptivos:
fim de quantum (interrupção do relógio, tempo partilhado)
processo mais prioritário
processo mais curto

objetivos do escalonamento preemptivo:
permitir que processos prioritários possam reagir rapidamente a um acontecimento
exemplo: windows NT, já o MSDOS é não preemptivo

exemplo de algortimos nao preemptivos:
o programa que terminou
o programa pediu acesso a um semáforo que estava fechado
o programa requisitou uma operação de E/S demorada

assim a preempção pode ser baseada em:
_intervalos de tempo fixo (um bocado de tempo à vez de todos)
_prioridade (o mais importante primeiro)
_critérios de performance (o mais pequeno/rápido primeiro)

o escalonamento multiprogramado simples:
consegue aproveitar esses tempo de E/S sem garantia que um programa impede outros de serem executados
aproveita melhor o CPU do que o monoprocessamento

o escalonamento multiprogramado:
o sistema consegue aproveitar os tempos de I/O de um programa para executar instruções de outros programas
existe a cedência do CPU

mas se existir um escalonamento preemptivo, baseado em intervalo de tempo, o utilizador obtém a garantia que todos os programas têm oportunidade de execução concorrente

Evolução dos sistemas operativos e do escalonamento
processamento em série (eniac)
processamento em lote on-line (uso de cartões perfurados junto do CPU, só existe um processo em cada instante)
processamento em lote off-line (uso de computadores auxiliares para ler os cartões perfurados, falhas na sincronização entre estes e o CPU, só existe um processo em cada instante)
processamento em lote o spooling (uso de mecanismos de interrupção, uso de discos)
multiprogramação (são sistemas de lote multi-programados ou concorrentes) e interactividade (são sistemas de tempo partilhado/time-sharing, com rotatividade de processos. Existe a pseudo execução em paralelo dos processos)

Parte 3 – conceitos de multiprogramação
o pseudo-paralelismo, consiste em ter várias actividades a decorrer ao mesmo tempo (em sistemas multiprogramados)
(existe um tempo de vista pelos processos e o que é a real desdestruição do processador)

Monoprocessamento vs multiprogramação simples

com esta acção de mutilprogramação simples o tempo total de execução diminui

Tempo não partilhado vs tempo partilhado (ou muliprogramação simples VS multiprogramação preemptiva)

resultados visíveis são errados, já que apesar do tempo de execução no tempo não partilhado (multiprogramação simples) ser menor que no tempo partilhado (multiprogramação preemptiva) o tempo apenas é explicado pelo aumento do numero de trocas entre os processos

Resumo das figuras:
sistemas multi-programados: optimização do processador
sistemas de tempo partilhado: optimizar a interactividade

As prioridades
surgem nos algoritmos de escalonamento e permite ao processo ser atendido que não fazendo uso do FIFO

As prioridades podem ser:
prioridades fixas (tem em conta o tipo de processo, associadas à importância dos acontecimentos. por exemplo: processo paginador)
prioridades dinâmicas (têm em conta o comportamento do processo, com o objectivo de ser justo, evitar a monopolização ou starvation. Neste caso são dadas prioridades aos processo que melhor se encaixam nos critérios de optimização global da máquina)

Os escalonadores
Os escalonadores podem ser:
escalonador de longo prazo (responsável por admitir um processo a execução. quantos mais processo maior a latência da máquina)
escalonador de médio prazo (através de um algoritmo determina quando e qual o processo, no estado de executável, que deve obter o processador)
escalonador de curto prazo (ou despacho, comuta os processos, após decisão do escalonado de médio prazo). O tempo de latência do despacho = tempo de parar um processo + tempo de recomeçar um processo

Quando se comuta de processo temos que ter em conta várias actividades:
invocação do despacho
salvaguarda do contexto do processo que estava a ser executado
recuperação do contexto para colocar o novo processo em execução
saltar para a localização do processo

Parte 4 – conceito de estado de processos

Modelo de dois estados:
faz uso do algoritmo de escalonamento, para determinar qual de dois processos que fica com o processo primeiro

Modelo de três estados:
surge o estado “novo” – serve para manter a informação acerca do processo, cuja criação foi pedida mas não foi admitido a execução
surge o estado “terminado” – serve para manter a informação acerca do processo, já terminado mas ainda não foi aproveitado
surge o estado de “suspenso” – pedido pelo próprio processo ou de outro processo

Modelo completo:

Parte 5 – conceitos usados em escalonamento

os diferentes algoritmos de escalonamento estão relacionados com respostas diferentes à forma como a gestão do processador tem que ser feita (desempenho, suporte, fiabilidade, robustez..).
qualquer algoritmo de escalonamento tem que manter todos os recursos do sistema. igualmente ocupados (para evitar picos de utilização)

aquando da gestão do processador tem que ter em conta os seguintes conceitos:
previsibilidade,
equilíbrio dos recursos,
justiça e starvation,
processos I/O bound e CPU bound

Existem dois tipos de processos/threads:
processos/threads I/O bound (que fazem muitas operações de E/S, bloqueando-se frequentemente)
processos/threads CPU bound (utilizam intensivamente o processador, quase nunca se bloqueando)

a Justiça
todos os processos/threads devem ter a mesma utilização dos recursos do sistema

a starvation
Surge quando o processo/thread nunca obtém o recurso pretendido, ou porque o recurso esta bloqueado ou porque o próprio processo/thread esta bloequeado
solução do starvation:
uso de prioridades dinâmicas (aumentar a prioridade para processos que estão à mais tempo à espera)

Parte 6 – indicadores de desempenho

este tipo de indicadores permitem que se verifique como está a eficiência com que o sistema gere a informação

exemplos de métricas/indicadores:
utilização do processador (importante para sistemas multiprogramados),
throughput (quantidade de processos concluídos por unidade de tempo)
tournaround (tempo de execução/conclusão. Desde a criação do processo/thread até à sua conclusão)
prazos (aplica-se em sistemas de tempo real). Exemplo:
três processos com um prazo de 15 minutos e outros com 3 com um prazo e 120 minutos
algoritmoA: todos os prazos são cumpridos à tangente
algoritmoB: os prazos dos processos de 15 minutos são ligeiramente excedidos enquanto os de 120 minutos são cumpridos com grande margem. Aparentemente o algortimo B seria melhor pois, em média, o throughput e o turnaround são melhores, mas a percentagem de prazos cumpridos é pior, pelo que o algortimo A é melhor

latência (tempo de resposta. Só se aplica a sistemas multiprogramados interactivos. É mais significado em sistemas interactivos que o throughut)
razão de penalização (é a razão entre o tempo total do processo e o tempo que demoraria se não tivesse outros processos)
exemplo:

tempo de espera (tempo total que um processo passou para o estado de executável)
previsibilidade (medida qualitativa do que quantitativa, e de implementação complexa, já que deve sempre necessitar do mesmo tempo para se executar independentemente da carga)

O escalonador tem que ser capaz de:
minimizar a latência,
maximizar o throughput,
maximizar o equilibro de uso dos periféricos,
justiça

Mas podem surgir problemas por via de:
dispositivos de E/S
optimização levar à starvation.
ocorrência de deadlocks

Parte 7 – algoritmos de escalonamento
Os algortimos de escalonamento podem ser:
preemptivos (round robin e SRT e Feedback)
não preemptivos (FCFS, SPN e HRRN) -> não servem para sistemas multiprogramados de tempo partilhado

algoritmo FCFS – Firts Come First Served
em que:
favorece o CPU Bound bloqueando os processos I/O Bound
não optimiza a utilização de dispositivos
para processos/threads nao interactivas, que têm o mesmo tempo de execução
tempo de conclusão não é importante

algoritmo RoundRobin
em que:
tem por base um quantum (intervalo de tempo)
força a interrupção de uma thread ao fim de um tempo
tempo partilhado em sistemas multiprogramados
é justo, independentemente do tamanho dos processos todos são atendidos da mesma forma
não surge o starvation
tournaround e tempo de espera melhors que o FCFS, quando a duração dos processos varia

Exemplo1 de FCFS e RoundRobin em que:
três processos do tipo CPU bound
existem um quantum
a duração do processo A=12q, do B=3q e do C=3q
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

Exemplo2 de FCFS e RoundRobin em que:
duração dos processo igual para todos = 6q

algoritmo SPN, Shortest Process Next
em que:
o próximo processo a ser executado é o que se espera que demore menos tempo;
não é preemptivo, não serve para sistemas multiprogramados,
situação de starvation dos processos longos face aos curtos
tem um melhor tournaround

algoritmo SRT, Shortest Remaining Time
em que:
o próximo processo/thread a ser executada é aquele cujo tempo restante de processamento é menor,
preemptivo (se um processo que estava bloqueado passar a executável e tiver tempo restante de processamento menor do que actualmente em execução, ocorre a preempção),
não é baseado em quantum
dificuldade: e qt tempo demoram os processos

algoritmo HRRN, Highest response Ratio Next
em que:
eliminar a starvation dos processos longos
valoriza o tempo esperado e a idade do processo no sistema
escolhe sempre o processo que tiver maior response ratio

RR (response ratio) = tempo de espera (w) + tempo de execução esperado (s) / tempo de execução esperado (s)

algoritmo de Feedback
em que:
quando quando não é possivel estimar o tempo de processamento
faz-se uso de uma análise na máquina no passado, para prever o que vai acontecer
faz uso de prioridades dinâmicas: a prioridade vai diminuindo ao longo da idade do processo
faz uso de quantum variável: atribui um quantum maior ao processo que esteja a ser penalizado e vice-versa

A escalabilidade:
uma solução em engenharia é escalável, se o custo for proporcional à dimensão do problema
um algoritmo de escalonamento é escalável se o seu overhead de execução for proporcional ao numero de processo em execução

Para evitar que o escalonamento se torne não escalável usamos a técnica de escalonamento multi-lista: agrupando os processos executáveis em conjuntos, promovendo os que estão mais perto do que está a ser analisado (primeiro nível e despromovendo para o nível mais baixo os que estão no primeiro nível.

coisas maybe importantes:
descrever o que é um quantum
o que é a preempção
conceito de justiça
o que é o CPU bound e i/o bound
o que é o tempo de espera, throughput, penalty ratio, conceito de justiça,
descrever o modo de funcionamento de cada um dos algoritmos estudados,
objectivos do escalonamento e duas principais dificuldades na obtenção de uma gestão óptima absoluta
explicar a influencia da preempção ou ausência dela num sistema
comparar dois algoritmos, para um cenário, e explicar qual o melhor e porquê
descrever a influencia da optimização de alguns indicadores de desempenho sobre os outros..
calcular tempos e indicadores..

Tags :