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 . 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 =)
Introdução ao Agendador
A essência do problema: como desenvolver uma política de agendador
Como deveriam ser projetadas as estruturas políticas subjacentes do escalonador? Quais devem ser as principais suposições? Quais métricas são importantes? Quais técnicas básicas foram usadas nos primeiros sistemas de computação?
Suposições de carga de trabalho
Antes de discutir possíveis políticas, vamos primeiro fazer algumas digressões simplificadas sobre os processos em execução no sistema, que são chamados coletivamente carga de trabalho. Definir a carga de trabalho é uma parte crítica da criação de políticas e, quanto mais você souber sobre a carga de trabalho, melhor será a política que poderá escrever.
Vamos fazer as seguintes suposições sobre os processos em execução no sistema, às vezes também chamados empregos (tarefas). Quase todas essas suposições não são realistas, mas são necessárias para o desenvolvimento do pensamento.
- Cada tarefa é executada pelo mesmo período de tempo,
- Todas as tarefas são definidas simultaneamente,
- A tarefa atribuída funciona até sua conclusão,
- Todas as tarefas usam apenas CPU,
- O tempo de execução de cada tarefa é conhecido.
Métricas do Agendador
Além de algumas suposições sobre a carga, é necessária outra ferramenta para comparar diferentes políticas de escalonamento: métricas do escalonador. Uma métrica é apenas uma medida de algo. Existem várias métricas que podem ser usadas para comparar agendadores.
Por exemplo, usaremos uma métrica chamada tempo de resposta (tempo de resposta). O tempo de resposta da tarefa é definido como a diferença entre o tempo de conclusão da tarefa e o tempo de chegada da tarefa no sistema.
Tturnaround=Tcompletion-Tarrival
Como assumimos que todas as tarefas chegaram ao mesmo tempo, então Ta=0 e, portanto, Tt=Tc. Este valor mudará naturalmente quando alterarmos as premissas acima.
Outra métrica - justiça (justiça, honestidade). A produtividade e a justiça são frequentemente características opostas no planeamento. Por exemplo, o escalonador pode otimizar o desempenho, mas ao custo de esperar pela execução de outras tarefas, reduzindo assim a justiça.
PRIMEIRO QUE ENTRA, PRIMEIRO QUE SAI (FIFO)
O algoritmo mais básico que podemos implementar é chamado FIFO ou primeiro a chegar (entrar), primeiro a ser servido (fora). Este algoritmo tem várias vantagens: é muito fácil de implementar e adapta-se a todos os nossos pressupostos e faz o trabalho muito bem.
Vejamos um exemplo simples. Digamos que 3 tarefas foram definidas simultaneamente. Mas vamos supor que a tarefa A chegou um pouco antes de todas as outras, então ela aparecerá na lista de execução antes das demais, assim como B em relação a C. Vamos supor que cada uma delas será executada por 10 segundos. Qual será o tempo médio para concluir essas tarefas neste caso?
Contando os valores - 10+20+30 e dividindo por 3, obtemos o tempo médio de execução do programa igual a 20 segundos.
Agora vamos tentar mudar nossas suposições. Em particular, a suposição 1 e, portanto, não assumiremos mais que cada tarefa leva o mesmo tempo para ser executada. Qual será o desempenho do FIFO desta vez?
Acontece que diferentes tempos de execução de tarefas têm um impacto extremamente negativo na produtividade do algoritmo FIFO. Vamos supor que a tarefa A levará 100 segundos para ser concluída, enquanto B e C ainda levarão 10 segundos cada.
Como pode ser visto na figura, o tempo médio do sistema será (100+110+120)/3=110. Este efeito é chamado efeito comboio, quando alguns consumidores de curto prazo de um recurso farão fila após um consumidor pesado. É como a fila do supermercado quando tem um cliente na sua frente com o carrinho cheio. A melhor solução para o problema é tentar trocar a caixa registradora ou relaxar e respirar profundamente.
Trabalho mais curto primeiro
É possível resolver de alguma forma uma situação semelhante com processos pesados? Certamente. Outro tipo de planejamento é chamadoTrabalho mais curto primeiro (SJF). Seu algoritmo também é bastante primitivo - como o nome indica, as tarefas mais curtas serão iniciadas primeiro, uma após a outra.
Neste exemplo, o resultado da execução dos mesmos processos será uma melhoria no tempo médio de execução do programa e será igual a 50 em vez de 110, o que é quase 2 vezes melhor.
Assim, para a suposição de que todas as tarefas chegam ao mesmo tempo, o algoritmo SJF parece ser o algoritmo mais ideal. No entanto, nossas suposições ainda não parecem realistas. Desta vez alteramos a suposição 2 e desta vez imaginamos que as tarefas podem estar presentes a qualquer momento, e não todas ao mesmo tempo. A que problemas isso pode levar?
Vamos imaginar que a tarefa A (100c) chegue primeiro e comece a ser executada. Em t = 10, chegam as tarefas B e C, cada uma levando 10 segundos. Portanto, o tempo médio de execução é (100+(110-10)+(120-10))3 = 103. O que o escalonador poderia fazer para melhorar isso?
Menor tempo para conclusão primeiro (STCF)
Para melhorar a situação, omitimos a suposição 3 de que o programa é lançado e funciona até ser concluído. Além disso, precisaremos de suporte de hardware e, como você pode imaginar, usaremos temporizador interromper uma tarefa em execução e mudança de contexto. Assim, o escalonador pode fazer algo no momento em que as tarefas B, C chegam - parar de executar a tarefa A e colocar as tarefas B e C em processamento e, após sua conclusão, continuar executando o processo A. Esse escalonador é chamado STCFou Trabalho preventivo primeiro.
O resultado deste planejador será o seguinte resultado: ((120-0)+(20-10)+(30-10))/3=50. Assim, tal agendador torna-se ainda mais ideal para nossas tarefas.
Tempo de resposta da métrica
Assim, se soubermos o tempo de execução das tarefas e que estas tarefas utilizem apenas CPU, o STCF será a melhor solução. E nos primeiros tempos, esses algoritmos funcionavam muito bem. Contudo, o usuário agora passa a maior parte do tempo no terminal e espera uma experiência interativa produtiva. Assim nasceu uma nova métrica - tempo de resposta (resposta).
O tempo de resposta é calculado da seguinte forma:
Tresponse=Tfirstrun-Tarrival
Assim, para o exemplo anterior, o tempo de resposta será: A=0, B=0, C=10 (abg=3,33).
E acontece que o algoritmo STCF não é tão bom em uma situação em que 3 tarefas chegam ao mesmo tempo - será necessário esperar até que as pequenas tarefas sejam completamente concluídas. Portanto, o algoritmo é bom para a métrica de tempo de resposta, mas ruim para a métrica de interatividade. Imagine se você estivesse sentado em um terminal tentando digitar caracteres em um editor e tendo que esperar mais de 10 segundos porque alguma outra tarefa estava ocupando a CPU. Não é muito agradável.
Então nos deparamos com outro problema – como podemos construir um escalonador que seja sensível ao tempo de resposta?
Round Robin
Um algoritmo foi desenvolvido para resolver este problema Round Robin (RR). A ideia básica é bastante simples: em vez de executar tarefas até que sejam concluídas, executaremos a tarefa por um determinado período de tempo (chamado de intervalo de tempo) e depois passaremos para outra tarefa da fila. O algoritmo repete seu trabalho até que todas as tarefas sejam concluídas. Neste caso, o tempo de execução do programa deve ser um múltiplo do tempo após o qual o temporizador interromperá o processo. Por exemplo, se um temporizador interrompe um processo a cada x=10ms, então o tamanho da janela de execução do processo deve ser um múltiplo de 10 e ser 10,20 ou x*10.
Vejamos um exemplo: As tarefas ABC chegam simultaneamente no sistema e cada uma delas quer ser executada por 5 segundos. O algoritmo SJF completará cada tarefa antes de iniciar outra. Em contraste, o algoritmo RR com janela de lançamento = 1s realizará as tarefas da seguinte forma (Fig. 4.3):
(SJF novamente (ruim para o tempo de resposta)
(Round Robin (bom para tempo de resposta)
O tempo médio de resposta para o algoritmo RR é (0+1+2)/3=1, enquanto para o SJF (0+5+10)/3=5.
É lógico supor que a janela de tempo é um parâmetro muito importante para RR; quanto menor for, maior será o tempo de resposta. No entanto, você não deve torná-lo muito pequeno, pois o tempo de troca de contexto também desempenhará um papel no desempenho geral. Assim, a escolha do tempo da janela de execução é definida pelo arquiteto do SO e depende das tarefas que estão planejadas para serem executadas nele. A troca de contexto não é a única operação de serviço que desperdiça tempo - o programa em execução opera em muitas outras coisas, por exemplo, vários caches, e a cada troca é necessário salvar e restaurar esse ambiente, o que também pode levar muito tempo. tempo.
RR é um ótimo agendador se estivéssemos falando apenas sobre a métrica de tempo de resposta. Mas como a métrica de tempo de resposta da tarefa se comportará com esse algoritmo? Considere o exemplo acima, quando o tempo de operação de A, B, C = 5s e chega ao mesmo tempo. A tarefa A terminará às 13, B às 14, C às 15s e o tempo médio de resposta será de 14s. Assim, RR é o pior algoritmo para a métrica de rotatividade.
Em termos mais gerais, qualquer algoritmo do tipo RR é justo; ele divide o tempo de CPU igualmente entre todos os processos. E assim, essas métricas entram em conflito constante entre si.
Assim, temos vários algoritmos contrastantes e ao mesmo tempo ainda restam várias suposições - que o tempo da tarefa é conhecido e que a tarefa utiliza apenas a CPU.
Mixagem com E/S
Em primeiro lugar, vamos remover a suposição 4 de que o processo utiliza apenas a CPU; naturalmente, este não é o caso e os processos podem acessar outros equipamentos.
No momento em que qualquer processo solicita uma operação de E/S, o processo entra no estado bloqueado, aguardando a conclusão da E/S. Se a E/S for enviada para o disco rígido, essa operação poderá levar vários ms ou mais e o processador ficará ocioso neste momento. Durante esse tempo, o escalonador pode ocupar o processador com qualquer outro processo. A próxima decisão que o escalonador terá que tomar é quando o processo completará sua E/S. Quando isso acontecer, ocorrerá uma interrupção e o sistema operacional colocará o processo que chamou a E/S no estado pronto.
Vejamos um exemplo de vários problemas. Cada um deles requer 50ms de tempo de CPU. Porém, o primeiro acessará I/O a cada 10ms (que também será executado a cada 10ms). E o processo B simplesmente usa um processador de 50 ms sem E/S.
Neste exemplo usaremos o agendador STCF. Como o escalonador se comportará se um processo como A for iniciado nele? Ele fará o seguinte: primeiro ele resolverá completamente o processo A e depois o processo B.
A abordagem tradicional para resolver este problema é tratar cada subtarefa de 10 ms do processo A como uma tarefa separada. Assim, ao iniciar com o algoritmo STJF, a escolha entre uma tarefa de 50 ms e uma tarefa de 10 ms é óbvia. Então, quando a subtarefa A for concluída, o processo B e a E/S serão iniciados. Após a conclusão da E/S, será habitual iniciar novamente o processo A de 10ms em vez do processo B. Desta forma, é possível implementar a sobreposição, onde a CPU é utilizada por outro processo enquanto o primeiro aguarda o E/S. E como resultado, o sistema é melhor utilizado - no momento em que processos interativos aguardam E/S, outros processos podem ser executados no processador.
O Oráculo não existe mais
Agora vamos tentar nos livrar da suposição de que o tempo de execução da tarefa é conhecido. Esta é geralmente a pior e mais irrealista suposição de toda a lista. Na verdade, no sistema operacional comum comum, o próprio sistema operacional geralmente sabe muito pouco sobre o tempo de execução das tarefas; então, como você pode construir um agendador sem saber quanto tempo a tarefa levará para ser executada? Talvez pudéssemos usar alguns princípios de RR para resolver este problema?
Total
Examinamos as ideias básicas de agendamento de tarefas e analisamos 2 famílias de agendadores. O primeiro inicia primeiro a tarefa mais curta e assim aumenta o tempo de resposta, enquanto o segundo fica dividido entre todas as tarefas igualmente, aumentando o tempo de resposta. Ambos os algoritmos são ruins onde os algoritmos da outra família são bons. Também analisamos como o uso paralelo de CPU e E/S pode melhorar o desempenho, mas não resolvemos o problema com a clarividência do sistema operacional. E na próxima lição veremos um planejador que olha para o passado imediato e tenta prever o futuro. E é chamada de fila de feedback multinível.
Fonte: habr.com