Introdución aos Sistemas Operativos
Ola Habr! Gustaríame chamarlle á súa atención unha serie de artigos-traducións dunha literatura interesante na miña opinión: OSTEP. Este material discute con bastante profundidade o traballo dos sistemas operativos tipo Unix, é dicir, o traballo con procesos, varios programadores, memoria e outros compoñentes similares que constitúen un sistema operativo moderno. Podes ver o orixinal de todos os materiais aquí . Teña en conta que a tradución foi feita de forma non profesional (con bastante liberdade), pero espero manter o significado xeral.
Os traballos de laboratorio sobre este tema pódense consultar aquí:
Outras partes:
Tamén podes consultar a miña canle en =)
Planificación: Fila de comentarios multinivel
Nesta charla, falaremos sobre os problemas de desenvolvemento dun dos enfoques máis famosos
planificación, que se chama Fila de comentarios de varios niveis (MLFQ). O planificador MLFQ foi descrito por primeira vez en 1962 por Fernando J. Corbató nun sistema chamado
Sistema de tempo compartido compatible (CTSS). Estes traballos (incluídos traballos posteriores sobre
Multics) foron nomeados posteriormente para un premio Turing. O programador foi
posteriormente mellorou e adquiriu o aspecto que xa se pode atopar en
algúns sistemas modernos.
O algoritmo MLFQ tenta resolver 2 problemas fundamentais de superposición.
En primeiro lugar, tenta optimizar o tempo de resposta, que, como comentamos na conferencia anterior, optimízase polo método de comezar na cabeza da cola máis
tarefas curtas. Non obstante, o sistema operativo non sabe canto tempo durará este ou aquel proceso, e isto
coñecementos necesarios para o funcionamento dos algoritmos SJF, STCF. En segundo lugar, MLFQ intenta
fai que o sistema responda aos usuarios (por exemplo, para aqueles que se senten e
mirando para a pantalla mentres espera a que se complete a tarefa) e así minimizar o tempo
resposta. Desafortunadamente, algoritmos como RR reducen o tempo de resposta, pero
ter un mal efecto na métrica do tempo de resposta. De aí o noso problema: Como deseñar
planificador que satisfará os nosos requisitos e que ao mesmo tempo non sabe nada
a natureza do proceso, en xeral? Como pode o planificador aprender as características das tarefas,
que lanza e así tomar mellores decisións de programación?
A esencia do problema: como planificar a configuración de tarefas sen coñecementos perfectos?
Como deseñar un planificador que minimiza simultaneamente o tempo de resposta
para tarefas interactivas e, ao mesmo tempo, minimiza o tempo de resposta sen saber
coñecemento do tempo de execución das tarefas?
Nota: aprendizaxe de eventos anteriores
A cola MLFQ é un excelente exemplo dun sistema no que se adestra
acontecementos pasados para predicir o futuro. Estes enfoques son moitas veces
atopado no sistema operativo (e moitas outras ramas da informática, incluíndo ramas
prediccións de hardware e algoritmos de caché). Camiñas semellantes
desencadean cando as tarefas teñen fases de comportamento e, polo tanto, son previsibles.
Non obstante, hai que ter coidado con esta técnica, porque as predicións son moi fáciles.
pode resultar incorrecto e levar ao sistema a tomar peores decisións que
estaría sen coñecemento en absoluto.
MLFQ: Regras básicas
Considere as regras básicas do algoritmo MLFQ. E aínda que as implementacións deste algoritmo
hai varios, os enfoques básicos son similares.
Na implementación que teremos en conta, MLFQ terá varias
filas separadas, cada unha das cales terá unha prioridade diferente. En calquera momento,
a tarefa lista para a execución está na mesma cola. MLFQ utiliza prioridades,
para decidir que tarefa executar, é dicir. tarefa con maior
prioridade (unha tarefa da cola coa prioridade máis alta) lanzarase ao primeiro
cola.
Por suposto, pode haber máis dunha tarefa nunha determinada cola, polo tanto
polo que terán a mesma prioridade. Neste caso, utilizarase o mecanismo
RR para a planificación do lanzamento entre estas tarefas.
Así chegamos a dúas regras básicas para MLFQ:
- Regra 1: se prioridade (A) > Prioridade (B), executarase a tarefa A (B non).
- Regra 2: se prioridade (A) = Prioridade (B), A e B comezan a usar RR
Con base no anterior, os elementos clave para planificar un MLFQ son
son prioridades. En lugar de darlle unha prioridade fixa a cada un
tarefa, MLFQ cambia a súa prioridade dependendo do comportamento observado.
Por exemplo, se unha tarefa sae constantemente na CPU mentres se espera a entrada do teclado,
MLFQ manterá alta a prioridade do proceso porque é así
proceso interactivo debería funcionar. Se, pola contra, a tarefa é constantemente e
é intensivo en CPU durante un longo período, MLFQ degradarao
unha prioridade. Así, a MLFQ estudará o comportamento dos procesos no momento en que se están a executar.
e utilizar comportamentos.
Debuxemos un exemplo de como poden ser as filas nalgún momento
tempo e despois obtén algo así:
Neste esquema, 2 procesos A e B están na cola con maior prioridade. Proceso
C está nalgún lugar no medio e o proceso D está ao final da cola. Segundo o anterior
descricións do algoritmo MLFQ, o planificador só executará tarefas co máis alto
prioridade segundo RR, e as tarefas C, D estarán sen traballo.
Por suposto, unha instantánea estática non dará unha imaxe completa de como funciona MLFQ.
É importante comprender exactamente como cambia a imaxe co paso do tempo.
Intento 1: Como cambiar a prioridade
Neste punto, cómpre decidir como MLFQ cambiará o nivel de prioridade
tarefa (e, polo tanto, a posición da tarefa na cola) durante o seu ciclo de vida. Para
disto, cómpre ter en conta o fluxo de traballo: unha certa cantidade
tarefas interactivas con tempo de execución curto (e, polo tanto, liberación frecuente
CPU) e varias tarefas longas que usan a CPU todo o seu tempo de traballo, mentres
o tempo de resposta para tales tarefas non é importante. E así podes facer o primeiro intento
implementar o algoritmo MLFQ coas seguintes regras:
- Regra 3: cando unha tarefa entra no sistema, colócase na cola con máis alta
- prioridade.
- Regra 4a: se unha tarefa usa toda a súa xanela de tempo, entón
- redúcese a prioridade.
- Regra 4b: se unha tarefa libera a CPU antes de que caduque a súa xanela de tempo, entón
- segue coa mesma prioridade.
Exemplo 1: tarefa única de longa duración
Como podes ver neste exemplo, a tarefa na admisión establécese co máis alto
prioridade. Despois dunha xanela de tempo de 10 ms, o proceso redúcese con prioridade.
planificador. Despois da seguinte xanela temporal, a tarefa redúcese finalmente a
prioridade máis baixa do sistema, onde permanece.
Exemplo 2: colleu unha pequena tarefa
Agora vexamos un exemplo de como MLFQ tentará achegarse a SJF. Niso
exemplo, dúas tarefas: A, que é unha tarefa de longa duración constantemente
ocupando CPU e B, que é unha pequena tarefa interactiva. Supoñamos
que A xa levaba tempo funcionando cando chegou a tarefa B.
Este gráfico mostra os resultados do escenario. Tarefa A, como calquera tarefa,
usar a CPU estaba na parte inferior. A tarefa B chegará á hora T=100 e chegará
colocado na cola de maior prioridade. Dado que o tempo de execución é curto,
completarase antes de chegar á última cola.
A partir deste exemplo, debes entender o obxectivo principal do algoritmo: xa que o algoritmo non
sabe unha tarefa longa ou curta, entón en primeiro lugar asume que a tarefa
curto e dálle a máxima prioridade. Se realmente é unha tarefa curta, entón
executarase rapidamente, se non, se é unha tarefa longa, moverase lentamente
en prioridade para abaixo e pronto demostrará que realmente é unha tarefa longa que non
require unha resposta.
Exemplo 3: e E/S?
Agora vexamos un exemplo de E/S. Como se indica na regra 4b,
se un proceso libera o procesador sen ter utilizado completamente o seu tempo de procesador,
entón permanece no mesmo nivel de prioridade. A intención desta regra é bastante sinxela.
- se o traballo interactivo realiza moitas E/S, por exemplo, esperando
das pulsacións de tecla ou do rato do usuario, tal tarefa liberará o procesador
antes da xanela asignada. Non nos gustaría omitir unha tarefa tan prioritaria,
e así permanecerá no mesmo nivel.
Este exemplo mostra como funcionaría o algoritmo con tales procesos: tarefa interactiva B, que só necesita a CPU durante 1 ms antes de executar
Proceso de E/S e un traballo longo A, que usa a CPU todo o tempo.
MLFQ mantén o proceso B coa máxima prioridade mentres continúa
liberar a CPU. Se B é unha tarefa interactiva, entón o algoritmo neste caso chegou
a súa finalidade é lanzar tarefas interactivas rapidamente.
Problemas co algoritmo MLFQ actual
Nos exemplos anteriores, creamos unha versión básica de MLFQ. E parece que el
fai o seu traballo ben e de forma xusta, distribuíndo o tempo da CPU de forma xusta
tarefas longas e permitindo tarefas curtas ou tarefas moi accesibles
a E/S para procesar rapidamente. Desafortunadamente, este enfoque contén varios
problemas graves.
En primeiro lugar, o problema da fame: se o sistema terá moitos interactivos
tarefas, consumirán todo o tempo da CPU e, polo tanto, nin un tempo
a tarefa non terá oportunidade de ser executada (están morrendo de fame).
En segundo lugar, os usuarios intelixentes poderían escribir os seus programas para que
enganar ao programador. O engano reside en facer algo para forzar
planificador para darlle ao proceso máis tempo de CPU. O algoritmo que
descrito anteriormente é bastante vulnerable a tales ataques: antes da xanela de tempo é practicamente
superado, cómpre realizar unha operación de E/S (para algúns, non importa o ficheiro)
e así liberar a CPU. Tal comportamento permitirache permanecer no mesmo
a propia cola e de novo obter unha maior porcentaxe de tempo de CPU. Se está feito
isto é correcto (por exemplo, executa o 99 % do tempo da xanela antes de liberar a CPU),
tal tarefa pode simplemente monopolizar o procesador.
Finalmente, un programa pode cambiar o seu comportamento ao longo do tempo. Esas tarefas
que utilizou a CPU pode volverse interactivo. No noso exemplo, semellante
as tarefas non recibirán o tratamento adecuado do planificador, como o farían outras
tarefas interactivas (orixinais).
Pregunta ao público: que ataques ao programador poderían facerse no mundo moderno?
Intento 2: Aumentar a prioridade
Intentemos cambiar as regras a ver se podemos evitar problemas
fame. Que podemos facer para garantir que está relacionado
As tarefas da CPU terán o seu tempo (aínda que non sexan longas).
Como solución sinxela ao problema, pode suxerir periodicamente
aumentar a prioridade de todas estas tarefas no sistema. Hai moitas maneiras
para conseguilo, intentemos implementar algo sinxelo como exemplo: traducir
todas as tarefas á vez á máxima prioridade, de aí a nova regra:
- Regra5: Despois dun período S, transfire todas as tarefas do sistema á cola máis alta.
A nosa nova regra resolve dous problemas á vez. En primeiro lugar, os procesos
garantido non morrer de fame: compartiranse tarefas na cola máis alta
tempo do procesador segundo o algoritmo RR e, polo tanto, recibirán todos os procesos
tempo do procesador. En segundo lugar, se algún proceso que se utilizou anteriormente
só o procesador pasa a ser interactivo, permanecerá na cola co máis alto
prioridade despois de recibir un impulso á prioridade máis alta unha vez.
Considere un exemplo. Neste escenario, considere un único proceso usando
CPU e dous procesos curtos e interactivos. Á esquerda da figura, a figura mostra o comportamento sen impulso de prioridade e, polo tanto, a tarefa de longa duración comeza a morrer de fame despois de que chegan dúas tarefas interactivas ao sistema. Na figura da dereita, cada 50 ms realízase un aumento de prioridade e, así, todos os procesos teñen garantido que reciben o tempo do procesador e que se iniciarán periodicamente. 50 ms neste caso tómase como exemplo, en realidade este número é algo maior.
É obvio que a suma do tempo de subida periódico S leva a
pregunta lóxica: que valor se debe establecer? Un dos ben merecidos
os enxeñeiros de sistemas John Ousterhout referiuse a cantidades similares nos sistemas como voo-doo
constante, xa que dalgunha maneira requirían maxia negra para o correcto
exposición. E, por desgraza, S ten tal sabor. Se estableces o valor tamén
grandes - tarefas longas morrerán de fame. E se o axustes demasiado baixo,
as tarefas interactivas non recibirán o tempo de CPU adecuado.
Intento 3: Mellor Contabilidade
Agora temos un problema máis que resolver: como non
permitir enganar o noso planificador? Os culpables desta posibilidade son
regras 4a, 4b que permiten que un traballo manteña a súa prioridade liberando o procesador
antes do vencemento do tempo previsto. Como tratar con iso?
A solución neste caso pódese considerar unha mellor conta do tempo de CPU en cada un
Nivel MLFQ. En lugar de esquecer o tempo que utilizou o programa
procesador para o intervalo asignado, debes telo en conta e gardalo. Despois
o proceso esgotou o seu tempo asignado, debería ser degradado ao seguinte
nivel de prioridade. Agora non importa como o proceso usará o seu tempo - como
computando constantemente no procesador ou como un conxunto de chamadas. Así,
A regra 4 debe reescribirse do seguinte xeito:
- Regra4: Despois de que unha tarefa esgotou o seu tempo asignado na cola actual (independentemente de cantas veces liberou a CPU), a prioridade desta tarefa redúcese (move a cola cara abaixo).
Vexamos un exemplo:
»
A figura mostra o que ocorre se tentas enganar ao planificador
se fose coas anteriores regras 4a, 4b sería o resultado da esquerda. Con novo
a regra é que o resultado está á dereita. Antes da protección, calquera proceso podía chamar a E/S antes da súa finalización e
domina así a CPU, despois de habilitar a protección, independentemente do comportamento
I/O, seguirá caendo na cola e, polo tanto, non poderá facer deshonesto
asumir os recursos da CPU.
Mellora do MLFQ e outros problemas
Coas melloras anteriores xorden novos problemas: un dos principais
preguntas: como parametrizar un programador deste tipo? Eses. Canto debería ser
filas? Cal debería ser o tamaño da xanela do programa dentro da cola? Como
programa moitas veces debe ser priorizado para evitar a fame e
para ter en conta o cambio no comportamento do programa? Para estas preguntas, non hai nada sinxelo
resposta e só experimentos con cargas e configuración posterior
o planificador pode levar a un equilibrio satisfactorio.
Por exemplo, a maioría das implementacións de MLFQ permítenche asignar diferentes
franxas horarias para diferentes filas. As colas de alta prioridade adoitan ser
intervalos curtos. Estas filas consisten en tarefas interactivas,
cambiar entre o que é bastante sensible e debería levar 10 ou menos
Señorita. Pola contra, as colas de baixa prioridade consisten en tarefas de longa duración que se usan
CPU. E neste caso, os intervalos de tempo longos encaixan moi ben (100 ms).
Neste exemplo, hai 2 tarefas que funcionaron na cola 20 de alta prioridade
ms dividido en fiestras de 10 ms. 40 ms na cola do medio (xanela de 20 ms) e na cola de baixa prioridade
A xanela de tempo de cola converteuse en 40 ms onde as tarefas completaban o seu traballo.
A implementación de MLFQ no SO Solaris é unha clase de programadores de tempo compartido.
O planificador proporcionará un conxunto de táboas que definen exactamente como debería
cambiar a prioridade do proceso ao longo da súa vida, cal debería ser o tamaño
ventá a asignar e con que frecuencia se deben elevar as prioridades das tarefas. Administrador
o sistema pode interactuar con esta táboa e facer que o planificador se comporte
de forma diferente. Por defecto, esta táboa ten 60 colas cun aumento gradual
tamaño da xanela de 20 ms (prioridade alta) a varios centos de ms (prioridade máis baixa) e
tamén co impulso de todas as tarefas unha vez por segundo.
Outros programadores MLFQ non usan unha táboa nin ningún tipo específico
as regras que se describen neste capítulo, pola contra, calculan as prioridades utilizando
fórmulas matemáticas. Por exemplo, o programador en FreeBSD usa unha fórmula para
calculando a prioridade da tarefa actual en función do proceso
utilizou a CPU. Ademais, o uso da CPU podrece co paso do tempo e, polo tanto
Así, o aumento de prioridade é algo diferente do descrito anteriormente. É verdade
chamados algoritmos de decadencia. A partir da versión 7.1, FreeBSD usa o planificador ULE.
Finalmente, moitos planificadores teñen outras características. Por exemplo, algúns
os programadores reservan niveis máis altos para o funcionamento do sistema operativo e así
Así, ningún proceso de usuario pode obter a máxima prioridade
sistema. Algúns sistemas permítenche dar consellos para axudar
o planificador para priorizar correctamente. Por exemplo, usando o comando bo
pode aumentar ou diminuír a prioridade dunha tarefa e así aumentar ou diminuír
reducir as posibilidades do programa para o tempo de CPU.
MLFQ: Resumo
Describimos un enfoque de planificación chamado MLFQ. O seu nome
concluíu no principio de funcionamento: ten varias filas e usa comentarios
para priorizar unha tarefa.
A forma final das normas será a seguinte:
- Regra1: Se prioridade(A) > Prioridade(B), executarase a tarefa A (B non)
- Regra2: Se prioridade(A) = Prioridade(B), A&B comezan usando RR
- Regra3: Cando unha tarefa entra no sistema, colócase na cola de maior prioridade.
- Regra4: Despois de que unha tarefa esgotou o seu tempo asignado na cola actual (independentemente de cantas veces liberou a CPU), a prioridade desta tarefa redúcese (move a cola cara abaixo).
- Regra5: Despois dun período S, transfire todas as tarefas do sistema á cola máis alta.
MLFQ é interesante polo seguinte motivo - en lugar de esixir coñecementos sobre
natureza da tarefa con antelación, o algoritmo aprende o comportamento pasado da tarefa e establece
prioridades en consecuencia. Así, intenta sentarse en dúas cadeiras á vez - para lograr o rendemento para tarefas pequenas (SJF, STCF) e executar honestamente as longas,
Traballos de carga de CPU. Polo tanto, moitos sistemas, incluíndo BSD e os seus derivados,
Solaris, Windows e Mac usan algún tipo de algoritmo como programador
MLFQ como referencia.
Materiais adicionais:
- (computación)
Fonte: www.habr.com