Introdução aos Sistemas Operacionais

Oi, Habr! Gostaria de chamar sua atenção para uma série de artigos-traduções de uma literatura interessante na minha opinião - OSTEP. Este material discute profundamente o trabalho de sistemas operacionais do tipo unix, ou seja, trabalhar com processos, vários agendadores, memória e outros componentes semelhantes que compõem um sistema operacional moderno. Você pode ver o original de todos os materiais aqui aqui. Por favor, note que a tradução foi feita de forma pouco profissional (com bastante liberdade), mas espero ter mantido o significado geral.

O trabalho de laboratório sobre este assunto pode ser encontrado aqui:

Outras partes:

Você também pode conferir meu canal em telegrama =)

Planejamento: fila de feedback multinível

Nesta palestra falaremos sobre os problemas de desenvolvimento de uma das abordagens mais famosas para
planejamento, que é chamado Fila de feedback multinível (MLFQ). O escalonador MLFQ foi descrito pela primeira vez em 1962 por Fernando J. Corbató em um sistema denominado
Sistema de compartilhamento de tempo compatível (CTSS). Esses trabalhos (incluindo trabalhos posteriores sobre
Multics) foram posteriormente nomeados para o Prêmio Turing. O planejador foi
posteriormente melhorou e adquiriu a aparência que já pode ser encontrada em
alguns sistemas modernos.

O algoritmo MLFQ tenta resolver 2 problemas fundamentais sobrepostos.
Em primeiro lugar, tenta otimizar o tempo de resposta, que, como discutimos na aula anterior, é otimizado pelo método de começar mais no início da fila
tarefas curtas. No entanto, o sistema operacional não sabe quanto tempo um determinado processo será executado, e isso
conhecimentos necessários para o funcionamento dos algoritmos SJF, STCF. em segundo lugar, MLFQ está tentando
tornar o sistema responsivo para os usuários (por exemplo, para aqueles que sentam e
olhar para a tela aguardando a conclusão da tarefa) e assim minimizar o tempo
resposta. Infelizmente, algoritmos como RR melhoram o tempo de resposta, mas extremamente
têm um impacto negativo na métrica do tempo de resposta. Daí o nosso problema: como projetar
um agendador que atenderá aos nossos requisitos sem saber nada sobre
a natureza do processo em geral? Como o agendador pode aprender as características das tarefas,
que lança e assim tomar melhores decisões de planeamento?

A essência do problema: como planejar a definição de tarefas sem um conhecimento perfeito?
Como projetar um agendador que minimize simultaneamente o tempo de resposta
para tarefas interativas e ao mesmo tempo minimiza o tempo de resposta sem saber
conhecimento do tempo de execução da tarefa?

Nota: aprendemos com eventos anteriores

A fila MLFQ é um excelente exemplo de sistema que aprende com
eventos passados para prever o futuro. Abordagens semelhantes são frequentemente
encontrado no sistema operacional (e em muitos outros ramos da ciência da computação, incluindo ramos
previsões de hardware e algoritmos de cache). Viagens semelhantes
são acionados quando as tarefas têm fases comportamentais e são, portanto, previsíveis.
No entanto, você deve ter cuidado com esta técnica porque as previsões são muito fáceis
pode revelar-se incorreto e levar o sistema a tomar decisões piores do que
ficaria sem conhecimento algum.

MLFQ: Regras Básicas

Vejamos as regras básicas do algoritmo MLFQ. E embora as implementações deste algoritmo
Existem vários, as abordagens básicas são semelhantes.
Na implementação que veremos, o MLFQ terá vários
filas separadas, cada uma das quais terá uma prioridade diferente. A qualquer momento,
uma tarefa pronta para execução está em uma fila. MLFQ usa prioridades,
para decidir qual tarefa executar para execução, ou seja, tarefa com maior
prioridade (tarefa da fila com maior prioridade) será lançada primeiro
fila.
É claro que pode haver mais de uma tarefa em uma determinada fila, então
então eles terão a mesma prioridade. Neste caso, o mecanismo será utilizado
RR para agendar uma execução entre essas tarefas.
Assim chegamos a duas regras básicas para o MLFQ:

Regra1: Se prioridade(A) > Prioridade(B), a tarefa A será lançada (B não)
Regra2: Se prioridade(A) = Prioridade(B), A&B são iniciados usando RR

Com base no exposto, os elementos-chave para o planejamento do MLFQ
são prioridades. Em vez de dar uma prioridade fixa a cada
tarefa, o MLFQ muda sua prioridade dependendo do comportamento observado.
Por exemplo, se uma tarefa está constantemente jogando trabalho na CPU enquanto espera pela entrada do teclado,
O MLFQ manterá alta a prioridade do processo porque é assim
um processo interativo deve funcionar. Se, pelo contrário, a tarefa é constante e
usa muito a CPU por um longo período, o MLFQ irá reduzi-la
uma prioridade. Assim, o MLFQ estudará o comportamento dos processos enquanto eles estão em execução
e usar comportamentos.
Vamos desenhar um exemplo de como serão as filas em algum momento
vez e então você obtém algo assim:

Neste esquema, 2 processos A e B estão na fila de prioridade mais alta. Processo
C está em algum lugar no meio e o processo D está bem no final da fila. De acordo com o acima
De acordo com as descrições do algoritmo MLFQ, o escalonador executará tarefas apenas com a maior
prioridade de acordo com RR, e as tarefas C, D ficarão desempregadas.
Naturalmente, um instantâneo estático não dará uma imagem completa de como o MLFQ funciona.
É importante entender exatamente como o quadro muda com o tempo.

Tentativa 1: Como alterar a prioridade

Neste ponto você precisa decidir como o MLFQ mudará o nível de prioridade
tarefas (e, portanto, a posição da tarefa na fila) à medida que avança em seu ciclo de vida. Para
isso é necessário para ter em mente o fluxo de trabalho: uma certa quantidade
tarefas interativas com tempos de execução curtos (e, portanto, liberação frequente
CPU) e diversas tarefas de longa duração que utilizam a CPU durante todo o seu tempo de trabalho, enquanto
O tempo de resposta não é importante para tais tarefas. E desta forma você pode fazer sua primeira tentativa
implemente o algoritmo MLFQ com as seguintes regras:

Regra 3: Quando uma tarefa entra no sistema, ela é colocada na fila com maior
prioridade.
Regra 4a: Se uma tarefa usa todo o intervalo de tempo alocado para ela, então ela
a prioridade é reduzida.
Regra 4b: Se uma tarefa liberar a CPU antes que sua janela de tempo expire, então ela
permanece com a mesma prioridade.

Exemplo 1: tarefa única de longa duração

Como pode ser visto neste exemplo, a tarefa de admissão é definida com o maior
prioridade. Após uma janela de tempo de 10ms, o processo é rebaixado em prioridade
planejador. Após a próxima janela de tempo, a tarefa é finalmente rebaixada para
prioridade mais baixa no sistema, onde permanece.

Exemplo 2: entregou uma tarefa curta

Agora vamos ver um exemplo de como o MLFQ tentará abordar o SJF. Naquilo
por exemplo, duas tarefas: A, que é uma tarefa de longa duração constantemente
ocupando CPU e B, que é uma tarefa interativa curta. Suponha
que A já estava trabalhando há algum tempo quando a tarefa B chegou.

Este gráfico mostra os resultados do cenário. A tarefa A, como qualquer tarefa,
O uso da CPU estava no nível mais baixo. A tarefa B chegará no tempo T=100 e será
colocado na fila de prioridade mais alta. Como seu tempo de operação é curto, então
ele será concluído antes de chegar à última fila.

A partir deste exemplo, o objetivo principal do algoritmo deve ser entendido: uma vez que o algoritmo não
sabe se uma tarefa é longa ou curta, então primeiro ele assume que a tarefa
curto e dá-lhe a mais alta prioridade. Se esta for uma tarefa realmente curta, então
será concluído rapidamente, caso contrário, se for uma tarefa longa, ela se moverá lentamente
prioridade e em breve provará que ela é de fato uma tarefa longa que não
requer uma resposta.

Exemplo 3: E quanto à E/S?

Agora vamos ver um exemplo de E/S. Como afirmado na regra 4b,
se um processo libera o processador sem usar todo o seu tempo de processador,
então permanece no mesmo nível de prioridade. A intenção desta regra é bastante simples
- se o trabalho interativo executar muitas operações de E/S, por exemplo, aguardar
a partir do pressionamento da tecla do usuário ou do mouse, tal tarefa liberará o processador
antes da janela atribuída. Não gostaríamos de diminuir a prioridade de tal tarefa,
e assim permanecerá no mesmo nível.

Este exemplo mostra como o algoritmo funcionará com tais processos - tarefa interativa B, que só precisa de CPU por 1 ms antes da execução
Processo de E/S e Job A de longa execução, que passa todo o tempo usando a CPU.
O MLFQ mantém o processo B na prioridade mais alta porque continua
liberar a CPU. Se B for uma tarefa interativa, então o algoritmo alcançou
Seu objetivo é executar tarefas interativas rapidamente.

Problemas com o algoritmo MLFQ atual

Nos exemplos anteriores construímos uma versão básica do MLFQ. E parece que ele
faz seu trabalho bem e honestamente, distribuindo o tempo de CPU de maneira justa entre
tarefas longas e permitindo tarefas curtas ou de alto volume
trabalhe em E/S rapidamente. Infelizmente, esta abordagem contém vários
problemas sérios.
Em primeiro lugar, o problema da fome: se o sistema tiver muitos recursos interativos
tarefas, então elas consumirão todo o tempo do processador e, portanto, nenhuma delas por muito tempo
a tarefa não poderá ser executada (eles estão morrendo de fome).

em segundo lugar, usuários inteligentes poderiam escrever seus programas de modo que
enganar o agendador. A decepção consiste em fazer algo para forçar
O escalonador dá ao processo mais tempo de CPU. Algoritmo que
descrito acima é bastante vulnerável a ataques semelhantes: antes que a janela de tempo seja praticamente
finalizado, você precisa realizar uma operação de E/S (para alguns, não importa qual arquivo)
e assim liberar a CPU. Tal comportamento permitirá que você permaneça no mesmo
a própria fila e novamente obtém uma porcentagem maior de tempo de CPU. Se você fizer
isso está correto (por exemplo, execute 99% do tempo da janela antes de liberar a CPU),
tal tarefa pode simplesmente monopolizar o processador.

Finalmente, um programa pode mudar seu comportamento ao longo do tempo. Essas tarefas
que usou a CPU pode se tornar interativo. Em nosso exemplo, semelhante
tarefas não receberão o tratamento que merecem do agendador como outras receberiam
tarefas interativas (iniciais).

Pergunta para o público: quais ataques ao agendador poderiam ser realizados no mundo moderno?

Tentativa 2: Aumentar a prioridade

Vamos tentar mudar as regras e ver se conseguimos evitar problemas com
jejum. O que podemos fazer para garantir que
As tarefas da CPU terão seu tempo (mesmo que não por muito tempo).
Como uma solução simples para o problema, você pode sugerir periodicamente
aumentar a prioridade de todas essas tarefas no sistema. Existem muitos caminhos
Para conseguir isso, vamos tentar implementar algo simples como exemplo: traduzir
todas as tarefas recebem imediatamente a prioridade mais alta, daí a nova regra:

Rule5: Após um determinado período S, mova todas as tarefas do sistema para a fila mais alta.

Nossa nova regra resolve dois problemas ao mesmo tempo. Primeiro, os processos
têm a garantia de não morrer de fome: as tarefas de maior prioridade serão divididas
Tempo de CPU de acordo com o algoritmo RR e assim todos os processos receberão
Tempo de CPU. Em segundo lugar, se algum processo usado anteriormente
apenas o processador se torna interativo, ele permanecerá na fila com maior
prioridade depois de receber um aumento único na prioridade para o mais alto.
Vejamos um exemplo. Neste cenário, considere um processo usando

CPU e dois processos curtos e interativos. À esquerda da figura, a figura mostra o comportamento sem promoção prioritária e, portanto, a tarefa de longa duração começa a morrer de fome depois que duas tarefas interativas chegam ao sistema. Na figura à direita, um aumento de prioridade é realizado a cada 50ms e assim todos os processos têm garantia de receber tempo de CPU e serão lançados periodicamente. 50ms neste caso é tomado como exemplo; na realidade este número é um pouco maior.
Obviamente, adicionar o tempo de aumento periódico S leva a
uma pergunta lógica: qual valor deve ser definido? Um dos homenageados
os engenheiros de sistemas John Ousterhout chamaram essas quantidades em sistemas de voo-doo
constante, já que de alguma forma exigiam magia negra para corrigir
exibindo. E, infelizmente, S tem esse cheiro. Se você definir o valor também
tarefas grandes e longas começarão a morrer de fome. E se você definir o valor muito baixo,
As tarefas interativas não receberão o tempo de CPU adequado.

Tentativa 3: Melhor Contabilidade

Agora temos outro problema para resolver: como não
permitir que nosso agendador seja enganado? As pessoas culpadas por esta possibilidade são
regras 4a, 4b, que permitem que um trabalho mantenha a prioridade, liberando o processador
antes que o tempo estipulado expire. Como lidar com isso?
A solução neste caso pode ser considerada uma melhor contabilização do tempo de CPU em cada
Nível MLFQ. Em vez de esquecer o tempo que o programa usou
processador durante o período concedido, ele deve ser levado em consideração e salvo. Depois
o processo esgotou o tempo alocado, ele deve ser rebaixado para o próximo
nível de prioridade. Agora não importa como o processo usará seu tempo - como
computando constantemente no processador ou como uma série de chamadas. Por isso,
a regra 4 deve ser reescrita na seguinte forma:

Rule4: depois que uma tarefa esgota seu tempo alocado na fila atual (não importa quantas vezes ela liberou a CPU), a prioridade dessa tarefa é reduzida (ela desce na fila).

Vejamos um exemplo:
»

A figura mostra o que acontece se você tentar enganar o escalonador, como
se fosse com as regras anteriores 4a, 4b seria obtido o resultado da esquerda. Feliz novo
a regra é o resultado à direita. Antes da proteção, qualquer processo poderia chamar E/S antes da conclusão e
assim dominar a CPU, após habilitar a proteção, independente do comportamento
I/O, ele ainda descerá na fila e, portanto, não poderá
assumir o controle dos recursos da CPU.

Melhorando o MLFQ e outros problemas

Com as melhorias acima mencionadas surgem novos problemas: um dos principais
Dúvidas - como parametrizar tal agendador? Aqueles. Quanto deveria ser
filas? Qual deve ser o tamanho da janela do programa na fila? Como
A prioridade do programa deve muitas vezes ser aumentada para evitar a fome e a
levar em conta a mudança no comportamento do programa? Não há uma resposta simples para essas perguntas
responda e apenas experimente cargas e configuração subsequente
planejador pode levar a algum equilíbrio satisfatório.

Por exemplo, a maioria das implementações do MLFQ permite atribuir diferentes
intervalos de tempo para diferentes filas. Filas de alta prioridade geralmente
intervalos curtos são prescritos. Essas filas consistem em tarefas interativas,
alternar entre os quais é bastante sensível e deve levar 10 ou menos
EM. Por outro lado, as filas de baixa prioridade consistem em tarefas de longa duração que usam
CPU. E neste caso cabem muito bem intervalos de tempo longos (100ms).

Neste exemplo existem 2 tarefas que funcionaram na fila de alta prioridade 20
ms, dividido em janelas de 10ms. 40ms na fila intermediária (janela de 20ms) e na prioridade baixa
A janela de tempo da fila passou a ser de 40 ms onde as tarefas concluíram seu trabalho.

A implementação do MLFQ no Solaris OS é uma classe de agendadores de compartilhamento de tempo.
O planejador fornecerá um conjunto de tabelas que definem exatamente como deveria
a prioridade do processo muda ao longo de sua vida, qual deve ser o tamanho
janela alocada e com que frequência você precisa aumentar as prioridades das tarefas. Administrador
sistemas podem interagir com esta tabela e fazer com que o escalonador se comporte
diferentemente. Por padrão, esta tabela possui 60 filas com aumento gradual
tamanho da janela de 20 ms (alta prioridade) a várias centenas de ms (baixa prioridade), e
também com um aumento de todas as tarefas uma vez por segundo.

Outros planejadores do MLFQ não usam uma tabela ou qualquer
regras descritas nesta palestra, pelo contrário, calculam prioridades usando
fórmulas matemáticas. Por exemplo, o agendador do FreeBSD usa uma fórmula para
calcular a prioridade atual de uma tarefa com base em quanto tempo o processo leva
CPU usada. Além disso, o uso da CPU diminui com o tempo e, portanto,
Assim, o aumento da prioridade ocorre de forma um pouco diferente da descrita acima. Isto é verdade
chamados algoritmos de decaimento. Desde a versão 7.1, o FreeBSD usa o escalonador ULE.

Finalmente, muitos agendadores possuem outros recursos. Por exemplo, alguns
os escalonadores reservam os níveis mais altos para a operação do sistema operacional e, portanto,
Assim, nenhum processo de usuário pode receber a prioridade mais alta em
sistema. Alguns sistemas permitem que você dê conselhos para ajudar
o planejador pode definir prioridades corretamente. Por exemplo, usando o comando agradável
você pode aumentar ou diminuir a prioridade de uma tarefa e, assim, aumentar ou
reduzir as chances do programa usar o tempo da CPU.

MLFQ: Resumo

Descrevemos uma abordagem de planejamento chamada MLFQ. O nome dele
incluído no princípio de funcionamento - possui diversas filas e utiliza feedback
para determinar a prioridade da tarefa.
A forma final das regras será a seguinte:

Rule1: Se prioridade(A) > Prioridade(B), a tarefa A será lançada (B não)
Rule2: Se prioridade(A) = Prioridade(B), A&B são iniciados usando RR
Rule3: quando uma tarefa entra no sistema, ela é colocada na fila de prioridade mais alta.
Rule4: depois que uma tarefa esgota seu tempo alocado na fila atual (não importa quantas vezes ela liberou a CPU), a prioridade dessa tarefa é reduzida (ela desce na fila).
Rule5: Após um determinado período S, mova todas as tarefas do sistema para a fila mais alta.

O MLFQ é interessante pela seguinte razão - em vez de exigir conhecimento sobre
natureza da tarefa com antecedência, o algoritmo estuda o comportamento passado da tarefa e define
prioridades em conformidade. Assim, ele tenta sentar-se em duas cadeiras ao mesmo tempo - para obter produtividade em pequenas tarefas (SJF, STCF) e para correr honestamente por muito tempo,
Trabalhos de carregamento de CPU. Portanto muitos sistemas incluindo BSD e seus derivados
Solaris, Windows, Mac usam alguma forma de algoritmo como agendador
MLFQ como linha de base.

Materiais adicionais:

Fonte: habr.com

Sistemas operacionais: três peças fáceis. Parte 5: Planejamento: Fila de Feedback Multinível (tradução)