mylab

SO1 – Escalonamento – Conceitos e Algoritmos

[so1t]

#conceitos de multi-programação

o pseudo-paralelismo:
consistem em ter varias actividades a decorrer ao mesmo tempo
disponivel em sistemas multi-programados (com tempo partilhado ou não)

algoritmos preemptivos:
forçam o processo a deixar o processador não bloqueado
usados em sistemas de tempo partilhado

exemplos de algoritmos preemptivos:
fim de quantum
processo prioritários
processos mais curtos

sistemas preemptivos:
o processo em execução pode ser interrompido e colocar em estado de “executável” pelo sistema operativo
e pode acontecer porque:
um novo processo esta no estado executável
surge uma interrupção que termina um determinado bloqueio
face à imposição do tempo partilhado
exemplo: windowsNT, Unix

desvantagens dos sistemas preemptivos:
maior comutação de processos, menor desempenho global
maior complexidade dos sistemas operativos

algoritmos não preemptivos:
não forçam o processo a sair do processador
exemplo: ms-dos

exemplos de algoritmos não preemptivos:
o programa terminou
o programa pediu acesso a um semáforo que está fechado
o programa requisitou uma operação de E/S demorada

sistemas não preemptivos:
um processo está em estado de execução e ele tem que terminar ou bloquear (por pedido do sistema operativo ou conclusão de operação de E/S)

escalonamento preemptivo:
usado em sistemas de tempo real
em sistemas multi-utilizador
permitem que um processo prioritário reaja a acontecimentos

como funciona o escalonamento preemptivo:
a) um processo prioritário está bloqueado num semáforo
b) é provocado um acontecimento no semáforo
c) o processo prioritário passa a executável
d) o processo em execução é retirado do processador
e) o processo prioritário entra em execução

a acção da preempção implica que o despacho seja chamado na sequência de alterações ao estado do processo e que podem ser:
fim do quantum
sinalização de periféricos
operações de sincronização

as prioridades:
é um atributo dos processos e das threads
um processo pode ser atendido por uma determinada ordem
usada em algoritmos de escalonamento

e as prioridades podem ser:
fixas, associadas à importância de acontecimentos, definidas pelo programador ou utilizador
dinâmicas, associadas ao comportamento do processo no sistema (evitar a monopolização de recursos levando a starvation), e é atribuída pelo escalonamento de acordo com o seu comportamento no sistema

os escalonadores:
longo prazo, admite ou não um processo a execução
médio prazo, determina quando e qual o processo que está no estado executável e que vai obter o processador (swaping)
curto prazo (ou despachos), efectua a comutação entre o processo que está a executar e o próximo (fim do quantum)

no despacho:
tempo de latência = tempo de parar um processo + tempo de recomeçar outro processo

a comutação faz com que:
invoca o despacho
salvaguarda o contexto de software e hardware do processo anterior em execução
recuperar o contexto do software e hardware
salta para a localização onde estava antes dentro do processo que vai para execução

sistema multi-programado simples:
são não preemptivos
executa os processos de forma colaborativa
não forçam os processos a sair do processador
faz uso das interrupções voluntárias (inputs) para executar outro processo pronto no processador

desvantagens:
processo que nunca bloqueiem
não optimiza os tempos de execução

questões:
qual a diferença entre multi-programação simples e multi-programação preemptiva
que tipos de preempção pode haver no escalonamento preemptivo?
como é que um computador só com um processador/núcleo consegue executar vários programas em simultâneo”?
se um programa entrar num ciclo infinito “encalha” a maquina toda? dê a sua resposta no contexto de multi-programação simples e depois multiplicação preemptiva
o que é o pseudo-paralelismo?
quais são as vantagens que a multi-programação preemptiva traz em relação à multi-programação simples?
num cenário real, poderá um sistema preemptivo ter menos performance global em relação a um sistema multi-programado mas não preemptivo? explique
qual destes é mais estável e porquê?: mono-processamento, multi-programação simples, multi-programação preemptiva?
que tipo de prioridades conhece. Para que serve cada tipo. Dê exemplos de aplicação.
Existem vários escalonadores? quais/para quê?

#conceito de estado de processos
em sistemas multi-programados os processo não estão apenas no estado em execução, mas podem estar em: execução, bloqueado não executável, ou executável (à espera de vez no processador)

os processos, num sistema monoprogramado (figSO1_01):

existem dois estados: parado e em execução
o processo quando é criado vai para o estado parado
o processo sai do estado parado (da fila de espera) pelo despacho
o processo quando está no estado de execução e termina, vai para processo termina
o processo quando está no estado de execução e não termina, fica suspenso, e vai para a fila de espera

os processos, num sistema multi-programado:
existem três estados: em execução, bloqueado, e executável (pronto a correr mas à espera do processador)
o processo está em execução: está a ser executado pelo processador
o processo está bloqueado: o processo não precisa do processador, e liberta-o
o processo está executável: o processo está pronto mas entrar em execução, mas o processador está ocupado

se dois processos estiverem prontos para irem para o processador, é o algoritmo de escalonamento que determina quem vai.

os processos, num sistema multi-programado (figSO1_02):

o processo quando é criado vai para o estado executável
o processo sai do estado executável (da fila de espera) pelo despacho
o processo quando está no estado de execução e termina, vai para processo termina
o processo quando está no estado de execução e aguarda um evento, vai para o estado de bloqueado
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável
o processo quando está no estado de execução e é retirado da execução, vai para o estado de executável (timeslice, quantum)

os processos, num sistema multi-programado, modelo completo (figSO1_03):

o processo quando é criado vai para o estado executável
o processo sai do estado executável (da fila de espera) pelo despacho
o processo sai do estado executável pode ser suspenso, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de execução e termina, vai para processo terminado
o processo quando está no estado de execução e aguarda um evento, vai para o estado de bloqueado (fila processos bloqueados)
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de bloqueado e é suspenso, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de suspenso e é des-suspenso, vai para o estado de bloqueado (fila processos bloqueados)
o processo quando está no estado de suspenso e é des-suspenso, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de execução e auto-suspende-se, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de execução e é retirado da execução, vai para o estado de executável (timeslice, quantum)(fila processos executáveis)

questões:
descreva o conceito de “estado de um processo” e indique a sua utilidade
quais os estados que conhece e respectivo significado?
que transições de estado podem ocorrer e em que circunstâncias
um processo pode passar directamente de bloqueado para em execução? em que circunstâncias/porquê?
qual diferença entre suspenso e bloqueado?
o que é o escalonamento por níveis e para que serve?

#conceitos gerais usados em escalonamento
a gestão do processador tem que ter em conta:
desempenho
suporte para multi-utilizador
robustez e fiabilidade

na gestão do processador tem que ser ter em conta:
previsibilidade
equilíbrio de recursos (evitar picos de uso dos recursos)
justiça (todos os processos devem ter a mesma utilização dos recursos) e starvation
processos I/O bound (processos que fazem muitas operações de E/S, bloqueando-se) e CPU bound (processos que usam de forma intensiva o processador, nunca se bloqueando)

questões:
o que se entende por conceito de justiça no escalonamento?
no contexto de escalonamento, indique cenários em que a justiça é desejável e cenários em que a justiça não é desejável
o que entende pelo conceito de starvation?
descreva o que entende por processo CPU bound e por processo I/O bound? Explique.
o que entende por equilíbrio de recursos?
qual a relação entre a gestão do processador e a gestão do resto da máquina?

#indicadores de desempenho
aferir como o sistema gere o uso do processador

as métricas que existem acerca do desempenho:
utilização do processador (é a percentagem de tempo que o processador está a ser usado, pouco interessante em sistemas interactivos, mono-utilziador ou sistemas de tempo real)
throughput (quantidade de processos concluídos por unidade de tempo, é interessante se os processos tiverem a mesma carga)
tempo de conclusão (touraround) (intervalo de tempo desde que se cria o processo até ele terminar)
prazos / deadlines (interessa maximizar a percentagem de prazos cumpridos, usado em sistemas de tempo real)
tempo de resposta / latência (tempo que demora a obtenção de uma resposta a uma acção do utilizador, usado em sistemas multi-programados interactivos)
razão da penalização / penalty ratio (é a razão entre o tempo de existência total sobre o tempo que levaria a executar-se se estivesse sozinho no sistema)
tempo de espera (tempo total que um processo esteve no estado executável)
previsibilidade (implementação complexa, o tempo de execução deve ser sempre o mesmo independentemente da carga no processador, necessidade de recorrer a registos de tempos de execução)

assim e acerca da gestão do processador e sendo um objectivo do escalonamento do sistema operativo:
minimizar a latência
maximizar o throughput
maximizar o equilíbrio da utilização dos periféricos
justiça

problemas e dificuldades que podem surgir nesta gestão:
dificuldade de prever o tipo de processos (CPU bound ou I/O bound), ficando os dispositivos de E/S inactivos
uma optimização pode provocar starvation
ocorrência de deadlocks

questões:
explique o que significa e qual o cenário de uso do indicador de desempenho de utilização do processador
explique o que significa e qual o cenário de uso do indicador de desempenho de throughput
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de conclusão (touraround)
explique o que significa e qual o cenário de uso do indicador de desempenho de prazos / deadlines
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de resposta / latência
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de razão da penalização / penalty ratio
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de espera
explique o que significa e qual o cenário de uso do indicador de desempenho de previsibilidade
dado um cenário com alguns processos e dois algoritmos de escalonamento, calcule cada uma das várias métricas de indicadores explicados e identifique qual o melhor algoritmo
verifique, para um dado cenário, identifique quais os indicadores de desempenho mais adequados e menos adequados. justifique.

#algoritmos de escalonamento
os algoritmos de escalonamento podem ser: não preemptivos e preemptivos

os não preemptivos são:
FCFS (first come first serve)
SPN (shortest process next)
HRRN (highest response ratio)

os preemptivos são:
Round Robin
SRT (shortest remaining time)
FEEDBACK

algortimo FCFS (first come first serve):
algoritmo não preemptivo
os processos são atendidos por ordem de chegada
favorece processos CPU bound
bloqueia os processos I/O bound
adequado para processos que não são interactivos
adequado para processos com a mesma duração de tempo
em arquitecturas de um só processador, deve usar-se com a variante de prioridades

algortimo Round Robin:
algoritmo preemptivo
os processos são atendidos por ordem de chegada
tem por base um quantum, sendo que depois volta para a lista dos executáveis
garantia que todos os processos são atendidos (não vai existir a starvation)
se existir uma variação de tempo nos processos, então este algoritmo é melhor que o FCFS
problema, definir o quantum (muito grande fica como o FCFS, já muito pequeno pode haver a necessidade de mais quantum)
adequado em arquitecturas com sistemas multi-programados

exemplo 1, de um cenário FCFS vs Round Robin (figSO1_04):

três processos, A, B e C, do tipo CPU bound
tempo total, de 18q
duração dos processos: A(12q), B(3q) e C(3q)
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

exemplo 2, de um cenário FCFS vs Round Robin (figSO1_05):

três processos, A, B e C, do tipo CPU bound
tempo total, de 18q
duração dos processos: 6q para todos
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

algortimo SPN (shortest process next):
não é preemptivo
similar ao FCFS, mas o próximo processo a ser executado é aquele que supostamente vai demorar menos tempo a executar
favorece os processos CPU bound
pode levar à starvation dos processos longos
tem um melhor touraround médio
não serve para sistemas multi-programados de tempo partilhado
problema: necessidade de ter um registo estatisito dos tempos dos processos

algoritmo SRT (shortest remaining time):
é preemptivo
similar ao SPN
o próximo processo a ser executado é aquele em que o tempo restante de processamento é menor
não é baseado no quantum
pode existir starvation dos processos longos
menor interactividade do que o RR
menor overhead que o RR
melhor touraround
problema: necessidade de ter um registo dos tempos de execução

algoritmo HRRN (highest response ratio):
eliminar o problema da starvation (que acontece no SPN e SRT)
surge o response ratio (RR)
RR = tempo de espera do processador + tempo de execução esperado / tempo de execução esperado
é escolhido o processo que tiver o maior RR
problema: como saber o tempo de execução de um processo?

algoritmo de FEEDBACK:
é preemptivo
é feita uma análise no passado recente
uso de prioridades dinâmicas (processo curto nunca perde a prioridade, processo longo vai perdendo a prioridade)
quantum variável (uso de diferentes quantums para recuperar processos, se este estiver a ser penalizado)

algoritmo de escalonamento escalável (a escabilidade):
algoritmo não escalável: pequenos aumentos no numero de processos levam a grandes aumentos no custo de execução do escalonador
algoritmo escalável pesado: pequenos aumentos no numero de processos levam a aumentos grandes mas proporcionais no custo de execução do escalonador (comum)
algoritmo escalável leve: pequenos aumentos no numero de processos levam a aumentos pequenos e proporcionais no custo de execução do escalonador (melhor cenário que se consegue)
algoritmo escalável muito bom (mas é fantasia): cada aumento no numero de processos causa pesos de execução cada vez menores

a técnica do escalonamento multi-lista (figSO1_06):

o nível superior é naquele cujos processos vão para execução
periodicamente, ir passando os processos para níveis mais superiores
ou despromovendo os processos do nível superior

problemas com qualquer escalonamento:
tempo de comutação de processos

questões:
explique como funciona um algoritmo
explique quais as vantagens face aos restantes, de um algoritmo
explique quais as desvantagens face aos restantes, de um algoritmo
exemplifique um cenário onde o algoritmo é o mais indicado, de um determinado algoritmo
exemplifique um cenário onde o algoritmo é não é o indicado, de um determinado algoritmo
o que é o escalonamento por níveis (multi-lista) e para que serve?
o que entende pela questão de escabilidade no escalonamento. indique uma forma de lidar com essa questão.

#escalonamento nos sistemas unix, linux, e windows NT

o escalonamento em unix:
round robin, com prioridades dinâmicas
privilegia os processos I/O bound
não pretendente atrasar os processos CPU bound
tem um quantum
a prioridade varia consoante o comportamento recente do processo
escalonamento multi-lista

o escalonamento em linux:
quantum são cerca de um conjunto de 20 notificações do relógio
e o quantum é modificado em cada época para um determinado processo

o escalonamento em windows nt:
o escalonamento é nas thread
round robim, com prioridades fixas e dinâmicas
escalonamento multi-lista
quantum é um conjunto de notificações do relógio

questões:
explique o funcionamento do escalonamento em unix, no linux e no windowsNT. Relacione com os conceitos dados nesta matéria
explique de que forma o windowsNT evita situações de starvation
explique de que forma o linux evita situações de starvation
poder-se-á dizer que os algoritmos de escalonamento do linux e do windowsNT são 100% justos= é isso é bom ou mau= Explique.
explique como são usadas as prioridades do windowsNT
os quantuns no linux têm sempre a mesma duração? porquê?
no contexto de escalonamento, indique uma diferença entre a edição desktop e a edição server do windowsNT. Explique essa diferença.

Outras questões:
descreva o que é um quantum
descreva o que é a preempção
explique o conceito de justiça
descrever o que é o cpu bound e o i/o bound
explicar o que é o tempo de espera, throughput, penalty ratio, conceito de justiça
descrever o modo de funcionamento de cada um dos algoritmos estudados
descrever os objectivos dos escalonamento e duas principais dificuldades na obtenção de uma gestão óptima absoluta
explicar e justificar a influencia de preempção ou ausência dela num sistema
comparação entre dois ou mais algoritmos, vantagens/desvantagens. Para uma determinado cenário, qual é o melhor e porquê?
descrever a influência da optimização de alguns indicadores de desempenho sobre os outros. explicar se é/não é possivel melhorar dois ou mais determinados indicadores e porquê.