Introdução aos sistemas operacionais

Olá Habr! Quero chamar sua atenção para uma série de artigos - traduções de uma literatura interessante em minha opinião - OSTEP. Este artigo discute profundamente o trabalho de sistemas operacionais semelhantes a unix, ou seja, trabalha com processos, vários agendadores, memória e outros componentes similares que compõem o sistema operacional moderno. O original de todos os materiais que você pode ver aqui . Observe que a tradução foi feita de maneira não profissional (muito livremente), mas espero ter mantido o significado geral.

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

Outras partes:

E você pode olhar para o meu canal no telegrama =)

Planejamento: fila de feedback multinível

Nesta palestra, falaremos sobre os problemas de desenvolver uma das abordagens mais famosas para
Planejamento chamado Fila de feedback de vários níveis (MLFQ). O agendador do MLFQ foi descrito pela primeira vez em 1962 por Fernando J. Corbató em um sistema chamado Sistema de Compartilhamento de Tempo Compatível (CTSS). Esses trabalhos (incluindo trabalhos posteriores sobre Multics) foram posteriormente submetidos ao Prêmio Turing. O agendador foi posteriormente aprimorado e adquiriu uma aparência que já pode ser encontrada em alguns sistemas modernos.

O algoritmo MLFQ tenta resolver 2 problemas transversais fundamentais.
Primeiro , ele tenta otimizar o tempo de resposta, que, como examinamos na palestra anterior, é otimizado iniciando no início da fila das tarefas mais curtas. No entanto, o sistema operacional não sabe quanto tempo esse ou aquele processo funcionará, e esse é o conhecimento necessário para a operação dos algoritmos SJF, STCF. Em segundo lugar , o MLFQ tenta tornar o sistema responsivo aos usuários (por exemplo, aqueles que estão sentados e olhando para a tela enquanto aguardam a conclusão da tarefa) e, assim, minimizar o tempo de resposta. Infelizmente, algoritmos como o RR reduzem o tempo de resposta, mas têm um efeito muito ruim nas métricas de tempo de resposta. Daí o nosso problema: como projetar um agendador que atenda aos nossos requisitos e, ao mesmo tempo, não saiba nada sobre a natureza do processo, em geral? Como o planejador pode aprender as características das tarefas que inicia e, assim, tomar melhores decisões de planejamento?

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

Nota: aprendendo com eventos anteriores

A programação do MLFQ é um ótimo exemplo de sistema que aprende com eventos passados para prever o futuro. Abordagens semelhantes são frequentemente encontradas no sistema operacional (e em muitos outros ramos da ciência da computação, incluindo ramos de previsão de hardware e algoritmos de cache). Viagens semelhantes funcionam quando as tarefas têm fases comportamentais e, portanto, são previsíveis.

No entanto, é preciso ter cuidado com essa técnica, porque as previsões podem facilmente ser erradas e levar o sistema a tomar decisões piores do que seria sem conhecimento.

MLFQ: Regras básicas

Considere as regras básicas do algoritmo MLFQ. Embora existam várias implementações desse algoritmo, as abordagens básicas são semelhantes.

Na implementação que consideraremos, no MLFQ haverá várias filas separadas, cada uma com uma prioridade diferente. A qualquer momento, uma tarefa pronta para execução está em uma fila. O MLFQ usa prioridades para decidir qual tarefa executar, ou seja, uma tarefa com uma prioridade mais alta (uma tarefa da fila com uma prioridade mais alta) será iniciada primeiro.

Sem dúvida, mais de uma tarefa pode estar em uma fila específica, portanto elas terão a mesma prioridade. Nesse caso, o mecanismo RR será usado para agendar o lançamento entre essas tarefas.

Assim, chegamos a duas regras básicas para o MLFQ:

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

Com base no exposto, os principais elementos do planejamento do MLFQ são prioridades. Em vez de definir uma prioridade fixa para cada tarefa, o MLFQ altera sua prioridade, dependendo do comportamento observado.

Por exemplo, se uma tarefa parar constantemente de trabalhar na CPU enquanto aguarda a entrada do teclado, o MLFQ manterá a prioridade do processo em um nível alto, porque é assim que o processo interativo deve funcionar. Se, pelo contrário, a tarefa usar constante e intensivamente a CPU por um longo período, o MLFQ diminuirá sua prioridade. Assim, o MLFQ estudará o comportamento dos processos no momento de sua operação e usará o comportamento.

Vamos desenhar um exemplo de como as filas podem parecer em algum momento e, em seguida, obtemos algo assim:

imagem

Nesse esquema, 2 processos A e B estão na fila com a prioridade mais alta. O processo C está em algum lugar no meio e o processo D está no final da fila. De acordo com as descrições acima do algoritmo MLFQ, o planejador executará tarefas apenas com a maior prioridade, de acordo com o RR, e as tarefas C, D ficarão sem trabalho.

Naturalmente, um instantâneo estático não fornecerá uma imagem completa de como o MLFQ funciona.
É importante entender exatamente como a imagem muda com o tempo.

Tentativa 1: Como alterar a prioridade

Nesse ponto, você precisa decidir como o MLFQ alterará o nível de prioridade da tarefa (e, portanto, a posição da tarefa na fila) durante seu ciclo de vida. Para fazer isso, lembre-se do fluxo de trabalho: várias tarefas interativas com um tempo de trabalho curto (e, portanto, liberação frequente da CPU) e várias tarefas longas que usam a CPU durante todo o tempo de trabalho, enquanto o tempo de resposta para essas tarefas não é importante. E assim, você pode fazer a primeira tentativa de implementar o algoritmo MLFQ com as seguintes regras:

Regra3: Quando uma tarefa entra no sistema, é colocada na fila com a maior
prioridade.
Regra4a: Se uma tarefa usa a janela de tempo inteira atribuída a ela, então sua
a prioridade diminui.
Rule4b: Se a tarefa liberar a CPU antes do vencimento de sua janela de tempo, então ela
permanece com a mesma prioridade.

Exemplo 1: Uma única tarefa de longa execução

Como você pode ver neste exemplo, a tarefa de admissão é colocada com a maior prioridade. Após uma janela de tempo de 10 ms, o processo é reduzido em prioridade pelo planejador. Após a próxima janela de tempo, a tarefa finalmente cai para a menor prioridade do sistema, onde permanece.

Exemplo 2: Eles trouxeram uma tarefa curta

Agora vamos ver um exemplo de como o MLFQ tentará se aproximar do SJF. Existem duas tarefas neste exemplo: A, que é uma tarefa de longa duração que ocupa constantemente a CPU, e B, que é uma tarefa interativa curta. Suponha que A já funcionou por algum tempo no momento em que a tarefa B chega.

Neste gráfico, os resultados do script são visíveis. A tarefa A, como qualquer tarefa que usa uma CPU, fica na parte inferior. A tarefa B chegará a T = 100 e será colocada na fila com a maior prioridade. Como o tempo de seu trabalho é curto, ele terminará antes de chegar ao último estágio.

A partir deste exemplo, deve-se entender o objetivo principal do algoritmo: como o algoritmo não conhece uma tarefa longa ou curta, ele assume primeiro que a tarefa é curta e lhe dá a maior prioridade. Se for uma tarefa realmente curta, ela será concluída rapidamente, caso contrário, se for uma tarefa longa, ela se moverá lentamente para baixo em prioridade e logo provará que é uma tarefa realmente longa que não requer resposta.

Exemplo 3: E quanto à E / S?

Agora dê uma olhada no exemplo de E / S. Conforme declarado na regra 4b, se um processo libera um processador sem utilizar totalmente o tempo do processador, ele permanece no mesmo nível de prioridade. A intenção desta regra é bastante simples - se uma tarefa interativa executar muitas operações de E / S, por exemplo, aguardando que o usuário pressione uma tecla ou mouse, essa tarefa liberará o processador antes da janela alocada. Não gostaríamos de omitir essa tarefa por prioridade e, portanto, ela permanecerá no mesmo nível.

Este exemplo mostra como o algoritmo funcionará com esses processos - uma tarefa interativa B, que precisa de uma CPU por apenas 1 ms antes de executar o processo de E / S, e uma tarefa longa A, que usa a CPU o tempo todo.

O MLFQ mantém o processo B com a maior prioridade, pois continua o tempo todo.
liberte a CPU. Se B é uma tarefa interativa, o algoritmo atingiu seu objetivo de iniciar tarefas interativas rapidamente.

Problemas com o algoritmo MLFQ atual

Nos exemplos anteriores, criamos a versão base do MLFQ. E parece que ele faz seu trabalho bem e honestamente, distribuindo honestamente o tempo do processador entre tarefas longas e permitindo que tarefas curtas ou tarefas que acessem intensivamente a E / S trabalhem rapidamente. Infelizmente, essa abordagem contém vários problemas sérios.

Primeiro , o problema da fome: se houver muitas tarefas interativas no sistema, elas consumirão todo o tempo do processador e, portanto, nem uma única tarefa longa poderá ser executada (elas estão morrendo de fome).

Em segundo lugar , usuários inteligentes poderiam escrever seus programas para que
enganar o planejador. O truque é fazer algo para fazer
planejador para dar ao processo mais tempo do processador. Algoritmo que
descrito acima é bastante vulnerável a esses ataques: antes que a janela de tempo seja praticamente
finalizado, é necessário executar uma operação de E / S (para alguns, não importa qual arquivo)
e, assim, liberar a CPU. Esse comportamento permitirá que você permaneça no mesmo
a própria fila e, novamente, obtém uma porcentagem maior do tempo da CPU. Se feito
isso está correto (por exemplo, 99% do tempo da janela antes de liberar a CPU)
essa tarefa pode simplesmente monopolizar o processador.

Finalmente, um programa pode mudar seu comportamento ao longo do tempo. Essas tarefas
quem usou a CPU pode se tornar interativo. No nosso exemplo, similar
tarefas não receberão tratamento adequado do agendador, pois outros receberiam
(interativas) tarefas interativas.

Pergunta à platéia: que ataques ao planejador poderiam ser feitos no mundo moderno?

Tentativa 2: Aumentar a prioridade

Vamos tentar mudar as regras e ver se podemos evitar problemas com
jejum. O que poderíamos 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 oferecer periodicamente
aumentar a prioridade de todas essas tarefas no sistema. Existem muitas maneiras.
para conseguir isso, vamos tentar implementar como exemplo algo simples: traduzir
todas as tarefas ao mesmo tempo na mais alta prioridade, daí a nova regra:

Regra5 : Após um certo período de S, transfira todas as tarefas do sistema para a prioridade mais alta.

Nossa nova regra resolve dois problemas ao mesmo tempo. Primeiro, os processos
garantido para não morrer de fome: as tarefas da mais alta prioridade compartilharão
processador de acordo com o algoritmo RR e, portanto, todos os processos receberão
tempo do processador. Em segundo lugar, se houver algum processo usado anteriormente
apenas o processador se tornar interativo, ele permanecerá alinhado com as
prioridade depois de uma vez receberá um aumento de prioridade para o mais alto.
Considere um exemplo. Nesse cenário, considere um processo usando

CPU e dois processos curtos e interativos. À esquerda na figura, a figura mostra o comportamento sem aumentar a prioridade e, portanto, a longa tarefa começa a passar fome depois que duas tarefas interativas chegam ao sistema. Na figura à direita, a cada 50ms, a prioridade é aumentada e, portanto, todos os processos são garantidos para receber o tempo do processador e serão iniciados periodicamente. 50ms neste caso é tomado como exemplo, na realidade esse número é um pouco maior.
Obviamente, a adição de tempo para um aumento periódico de S leva a
pergunta lógica: qual valor deve ser definido? Um dos homenageados
engenheiros de sistemas John Ousterhout denominaram quantidades semelhantes em sistemas como o voo-doo
constante, porque de alguma maneira exigiam magia negra para
exibindo. E, infelizmente, S tem esse aroma. Se você definir o valor também
grandes e longas tarefas começarão a passar fome. E se você definir o valor muito baixo,
As tarefas interativas não receberão o tempo adequado do processador.

Tentativa 3: Melhor contabilidade

Agora, temos mais um problema que precisa ser resolvido: como não
vamos enganar o nosso planejador? Culpado desta oportunidade são
regras 4a, 4b, que permitem que a tarefa mantenha prioridade, liberando o processador
antes da expiração do tempo alocado. Como lidar com isso?
A solução nesse caso pode ser considerada a melhor contabilização do tempo da CPU em cada
Nível MLFQ. Em vez de esquecer o tempo que o programa usou
processador durante o período designado, considere e salve-o. Depois
o processo gastou tempo alocado para ele deve ser reduzido para o próximo
nível de prioridade. Agora, não importa como o processo use seu tempo - como
constantemente computando no processador ou em tantas chamadas. Desta maneira
A regra 4 deve ser reescrita da seguinte maneira:

Regra4 : Depois que a tarefa esgotar o tempo alocado na fila atual (independentemente de quantas vezes liberou a CPU), a prioridade de uma tarefa diminui (ela desce a fila).

Vejamos um exemplo:

"

A figura mostra o que acontece se você tentar enganar o planejador, como
se fosse com as regras anteriores 4a, 4b, obteremos o resultado à esquerda. Feliz novo
a regra é o resultado à direita. Antes da proteção, qualquer processo poderia chamar E / S até a conclusão e
dominam a CPU, depois de ativar a proteção, independentemente do comportamento
E / S, ainda vai cair na linha e, portanto, não será desonesto
tomar posse dos recursos da CPU.

Melhorando o MLFQ e outros problemas

Com as melhorias acima, surgem novos problemas: um dos principais
perguntas - como parametrizar esse agendador? I.e. Quanto deve ser
rajadas? Qual deve ser o tamanho da janela do programa dentro da fila? Como
a prioridade do programa deve frequentemente ser aumentada para evitar a fome e
levar em conta mudanças no comportamento do programa? Para essas perguntas, não é fácil
resposta e apenas experimentos com cargas e configuração subsequente
o planejador pode levar a um 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 atribuídos. Essas filas consistem em tarefas interativas,
alternar entre o que é bastante sensível e deve levar 10 ou menos
ms Por outro lado, filas de baixa prioridade consistem em tarefas longas usando
CPU E, neste caso, longos intervalos de tempo se encaixam muito bem (100ms).

Neste exemplo, existem 2 tarefas que funcionaram na fila de alta prioridade 20
ms, quebrado por janelas por 10ms. 40ms na fila média (janela às 20ms) e na prioridade baixa
A janela de tempo da fila passou a 40ms, onde as tarefas concluíram seu trabalho.

A implementação do Solaris OS MLFQ é uma classe de agendadores de compartilhamento de tempo.
O planejador fornece um conjunto de tabelas que determinam exatamente como deve
mudar a prioridade do processo ao longo de sua vida, qual deve ser o tamanho
a janela selecionada e com que frequência você precisa elevar as prioridades da tarefa. Admin
sistemas podem interagir com esta tabela e fazer com que o planejador se comporte
de uma maneira diferente. Por padrão, existem 60 filas incrementais nesta tabela.
tamanho da janela de 20 ms (alta prioridade) a várias centenas de ms (menor 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
as regras descritas nesta palestra, pelo contrário, calculam as prioridades usando
fórmulas matemáticas. Então, por exemplo, o planejador no FreeBSD usa a fórmula para
calcular a prioridade atual de uma tarefa com base em quanto o processo
CPU usada. Além disso, o uso da CPU decai com o tempo e, portanto,
Assim, o aumento de prioridade ocorre de maneira um pouco diferente do descrito acima. É tão
chamados algoritmos de decaimento. Desde a versão 7.1, o FreeBSD usa o agendador ULE.

Finalmente, muitos planejadores têm outros recursos. Por exemplo, alguns
planejadores reservam os níveis mais altos para o sistema operacional e, portanto,
Dessa forma, nenhum processo do usuário pode obter a maior prioridade em
sistema Alguns sistemas permitem que você dê dicas para ajudar.
o planejador para definir prioridades corretamente. Por exemplo, usando o comando nice
você pode aumentar ou diminuir a prioridade da tarefa e, assim, aumentar ou diminuir
reduza as chances do programa para o tempo do processador.

MLFQ: Resumo

Descrevemos uma abordagem de planejamento chamada MLFQ. O nome dele
Ele é concluído no princípio do trabalho - possui várias filas e usa feedback
para determinar a prioridade da tarefa.
A forma final das regras será a seguinte:

Regra1 : Se a prioridade (A)> Prioridade (B), a tarefa A for iniciada (B não será)
Regra2 : Se a prioridade (A) = Prioridade (B), A&B são iniciados usando RR
Regra3 : Quando uma tarefa entra no sistema, ela é enfileirada com a prioridade mais alta.
Regra4 : Depois que a tarefa esgotar o tempo alocado na fila atual (independentemente de quantas vezes liberou a CPU), a prioridade de uma tarefa diminui (ela desce a fila).
Regra5 : Após um certo período de S, transfira todas as tarefas do sistema para a prioridade mais alta.

O MLFQ é interessante pelo seguinte motivo - em vez de exigir conhecimento prévio sobre a
natureza da tarefa, o algoritmo examina o comportamento passado da tarefa e
prioriza de acordo. Assim, ele tenta se sentar em duas cadeiras ao mesmo tempo - para obter produtividade para pequenas tarefas (SJF, STCF) e executar honestamente
tarefas longas e de carregamento da CPU. Portanto, muitos sistemas, incluindo BSD e seus derivados,
Solaris, Windows, Mac, usam alguma forma de algoritmo
MLFQ como um agendador como base.

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