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 =)
Introdución ao Scheduler
A esencia do problema: como desenvolver unha política de planificador
Como deberían deseñarse os marcos de políticas do programador subxacente? Cales deben ser os supostos fundamentais? Que métricas son importantes? Que técnicas básicas se utilizaron nos primeiros sistemas informáticos?
Presuntos de carga de traballo
Antes de discutir posibles políticas, primeiro fagamos algunhas digresións simplificadoras sobre os procesos que se executan no sistema, que se denominan colectivamente carga de traballo. Definir a carga de traballo é unha parte fundamental das políticas de creación, e canto máis saibas sobre a carga de traballo, mellor será a política que podes escribir.
Imos facer as seguintes suposicións sobre os procesos que se executan no sistema, ás veces tamén chamados emprego (tarefas). Case todos estes supostos non son realistas, pero son necesarios para o desenvolvemento do pensamento.
- Cada tarefa execútase durante o mesmo tempo,
- Todas as tarefas están configuradas simultaneamente,
- A tarefa asignada funciona ata a súa finalización,
- Todas as tarefas usan só CPU,
- Coñécese o tempo de execución de cada tarefa.
Métricas do programador
Ademais dalgunhas suposicións sobre a carga, é necesaria outra ferramenta para comparar diferentes políticas de programación: as métricas do planificador. Unha métrica é só unha medida de algo. Hai unha serie de métricas que se poden usar para comparar programadores.
Por exemplo, utilizaremos unha métrica chamada tempo de resposta (tempo de resposta). O tempo de entrega da tarefa defínese como a diferenza entre o tempo de finalización da tarefa e o tempo de chegada da tarefa no sistema.
Tturnaround=Tfinalización−Chegada
Dado que asumimos que todas as tarefas chegaban ao mesmo tempo, entón Ta=0 e, polo tanto, Tt=Tc. Este valor cambiará naturalmente cando cambiemos as suposicións anteriores.
Outra métrica - xustiza (xusto, honestidade). A produtividade e a equidade adoitan ser características opostas na planificación. Por exemplo, o programador pode optimizar o rendemento, pero a costa de esperar a que se executen outras tarefas, reducindo así a equidade.
PRIMEIRO EN ENTRAR PRIMEIRO EN SALIR (FIFO)
O algoritmo máis básico que podemos implementar chámase FIFO ou primeiro en entrar, primeiro servido (saír). Este algoritmo ten varias vantaxes: é moi sinxelo de implementar e encaixa con todas as nosas hipóteses e fai o traballo bastante ben.
Vexamos un exemplo sinxelo. Digamos que se estableceron 3 tarefas á vez. Pero supoñamos que a tarefa A chegou un pouco antes que todas as demais, polo que aparecerá na lista de execución antes que as demais, igual que B en relación con C. Supoñamos que cada unha delas se executará durante 10 segundos. Cal será o tempo medio para completar estas tarefas neste caso?
Contando os valores - 10+20+30 e dividindo por 3, obtemos o tempo medio de execución do programa igual a 20 segundos.
Agora imos tentar cambiar as nosas suposicións. En particular, o suposto 1 e, polo tanto, xa non asumiremos que cada tarefa leva a mesma cantidade de tempo en executarse. Como actuará a FIFO nesta ocasión?
Polo que se ve, os diferentes tempos de execución de tarefas teñen un impacto extremadamente negativo na produtividade do algoritmo FIFO. Supoñamos que a tarefa A tardará 100 segundos en completarse, mentres que B e C aínda tardarán 10 segundos cada unha.
Como se pode ver na figura, o tempo medio para o sistema será (100+110+120)/3=110. Este efecto chámase efecto convoi, cando algúns consumidores a curto prazo dun recurso farán cola despois dun gran consumidor. É como a fila do supermercado cando hai un cliente diante de ti cun carro cheo. A mellor solución ao problema é intentar cambiar a caixa rexistradora ou relaxarse e respirar profundamente.
O traballo máis curto primeiro
É posible resolver dalgún xeito unha situación semellante con procesos pesados? Certamente. Outro tipo de planificación chámaseO traballo máis curto primeiro (SJF). O seu algoritmo tamén é bastante primitivo: como o nome indica, as tarefas máis curtas lanzaranse primeiro, unha tras outra.
Neste exemplo, o resultado de executar os mesmos procesos será unha mellora no tempo medio de entrega do programa e será igual a 50 no canto de 110, que é case 2 veces mellor.
Así, para o suposto dado de que todas as tarefas chegan ao mesmo tempo, o algoritmo SJF parece ser o algoritmo máis óptimo. Non obstante, as nosas suposicións aínda non parecen realistas. Desta vez cambiamos o suposto 2 e esta vez imaxinamos que as tarefas poden estar presentes en calquera momento, e non todas ao mesmo tempo. A que problemas pode levar isto?
Imaxinemos que a tarefa A (100c) chega primeiro e comeza a executarse. En t=10 chegan as tarefas B e C, cada unha delas levará 10 segundos. Polo tanto, o tempo medio de execución é (100+(110-10)+(120-10))3 = 103. Que podería facer o planificador para mellorar isto?
O tempo máis curto para completar primeiro (STCF)
Para mellorar a situación, omitimos a hipótese 3 de que o programa está en marcha e funciona ata a súa finalización. Ademais, necesitaremos soporte de hardware e, como podes adiviñar, utilizaremos temporizador para interromper unha tarefa en execución e cambio de contexto. Así, o planificador pode facer algo no momento en que chegan as tarefas B, C: deixar de executar a tarefa A e poñer as tarefas B e C en procesamento e, despois da súa finalización, continuar executando o proceso A. Este programador chámase STCFou Traballo preventivo primeiro.
O resultado deste planificador será o seguinte: ((120-0)+(20-10)+(30-10))/3=50. Así, un programador deste tipo faise aínda máis óptimo para as nosas tarefas.
Tempo de resposta métrica
Así, se coñecemos o tempo de execución das tarefas e que estas tarefas só usan CPU, STCF será a mellor solución. E unha vez nos primeiros tempos, estes algoritmos funcionaron bastante ben. Non obstante, a usuaria agora pasa a maior parte do seu tempo no terminal e espera unha experiencia interactiva produtiva. Así naceu unha nova métrica - tempo de resposta (resposta).
O tempo de resposta calcúlase do seguinte xeito:
Tresponse=Tfirstrun−Tarrival
Así, para o exemplo anterior, o tempo de resposta será: A=0, B=0, C=10 (abg=3,33).
E resulta que o algoritmo STCF non é tan bo nunha situación na que chegan 3 tarefas ao mesmo tempo: terá que esperar ata que as pequenas tarefas estean completamente completadas. Polo tanto, o algoritmo é bo para a métrica de tempo de resposta, pero malo para a métrica de interactividade. Imaxina se estiveses sentado nun terminal intentando escribir caracteres nun editor e tes que esperar máis de 10 segundos porque algunha outra tarefa ocupaba a CPU. Non é moi agradable.
Entón, enfrontámonos a outro problema: como podemos construír un programador que sexa sensible ao tempo de resposta?
Round Robin
Desenvolveuse un algoritmo para resolver este problema Round Robin (RR). A idea básica é bastante sinxela: en lugar de executar tarefas ata que estean completadas, executaremos a tarefa durante un período de tempo determinado (chamado intervalo de tempo) e despois cambiaremos a outra tarefa da cola. O algoritmo repite o seu traballo ata completar todas as tarefas. Neste caso, o tempo de execución do programa debe ser un múltiplo do tempo despois do cal o temporizador interromperá o proceso. Por exemplo, se un temporizador interrompe un proceso cada x=10ms, entón o tamaño da xanela de execución do proceso debería ser un múltiplo de 10 e ser 10,20 ou x*10.
Vexamos un exemplo: as tarefas ABC chegan simultaneamente ao sistema e cada unha delas quere executarse durante 5 segundos. O algoritmo SJF completará cada tarefa antes de comezar outra. Pola contra, o algoritmo RR cunha xanela de inicio = 1s realizará as tarefas do seguinte xeito (Fig. 4.3):
(SJF de novo (malo para o tempo de resposta)
(Round Robin (bo para o tempo de resposta)
O tempo medio de resposta para o algoritmo RR é (0+1+2)/3=1, mentres que para o SJF (0+5+10)/3=5.
É lóxico asumir que a xanela de tempo é un parámetro moi importante para RR; canto menor sexa, maior será o tempo de resposta. Non obstante, non debes facelo demasiado pequeno, xa que o tempo de cambio de contexto tamén terá un papel no rendemento xeral. Así, a elección do tempo da xanela de execución é definida polo arquitecto do SO e depende das tarefas que se planifiquen para executar nela. Cambiar de contexto non é a única operación de servizo que fai perder tempo: o programa en execución funciona en moitas outras cousas, por exemplo, varias cachés, e con cada cambio é necesario gardar e restaurar este ambiente, o que tamén pode levar moito tempo. tempo.
RR é un gran programador se falamos só da métrica do tempo de resposta. Pero como se comportará a métrica do tempo de entrega da tarefa con este algoritmo? Considere o exemplo anterior, cando o tempo de funcionamento de A, B, C = 5 s e chega ao mesmo tempo. A tarefa A rematará ás 13, B ás 14, C ás 15 segundos e o tempo medio de resposta será de 14 segundos. Así, RR é o peor algoritmo para a métrica de rotación.
En termos máis xerais, calquera algoritmo de tipo RR é xusto; divide o tempo da CPU por igual entre todos os procesos. E así, estas métricas entran en conflito constantemente entre si.
Así, temos varios algoritmos contrastantes e, ao mesmo tempo, aínda quedan varias suposicións: que se coñece o tempo da tarefa e que a tarefa só usa a CPU.
Mestura con E/S
En primeiro lugar, eliminemos a suposición 4 de que o proceso só usa a CPU; naturalmente, este non é o caso e os procesos poden acceder a outros equipos.
No momento en que calquera proceso solicita unha operación de E/S, o proceso entra no estado bloqueado, á espera de que se complete a E/S. Se se envía E/S ao disco duro, tal operación pode levar ata varios ms ou máis, e o procesador estará inactivo neste momento. Durante este tempo, o planificador pode ocupar o procesador con calquera outro proceso. A seguinte decisión que terá que tomar o planificador é cando o proceso completará a súa E/S. Cando isto ocorre, producirase unha interrupción e o sistema operativo poñerá o proceso que chamou a E/S no estado listo.
Vexamos un exemplo de varias tarefas. Cada un deles require 50 ms de tempo de CPU. Non obstante, o primeiro accederá á E/S cada 10 ms (que tamén se executará cada 10 ms). E o proceso B simplemente usa un procesador de 50 ms sen E/S.
Neste exemplo usaremos o programador STCF. Como se comportará o planificador se se inicia un proceso como A nel? Fará o seguinte: primeiro traballará completamente o proceso A e despois o proceso B.
O enfoque tradicional para resolver este problema é tratar cada subtarefa de 10 ms do proceso A como unha tarefa separada. Así, ao comezar co algoritmo STJF, a elección entre unha tarefa de 50 ms e unha tarefa de 10 ms é obvia. Despois, cando se complete a subtarefa A, lanzaranse o proceso B e E/S. Despois de que se complete a E/S, será habitual iniciar o proceso A de 10 ms de novo en lugar do proceso B. Deste xeito, é posible implementar a superposición, onde a CPU é utilizada por outro proceso mentres o primeiro está esperando o E/S. E, como resultado, o sistema utilízase mellor: no momento en que os procesos interactivos están esperando E/S, outros procesos poden ser executados no procesador.
O Oracle xa non existe
Agora imos tentar desfacernos da suposición de que se coñece o tempo de execución da tarefa. Esta é xeralmente a peor e máis irreal suposición de toda a lista. De feito, no sistema operativo ordinario medio, o propio sistema operativo adoita saber moi pouco sobre o tempo de execución das tarefas, entón como se pode construír un programador sen saber canto tempo tardará en executarse a tarefa? Quizais poderiamos usar algúns principios de RR para resolver este problema?
Total
Observamos as ideas básicas da programación de tarefas e observamos 2 familias de programadores. O primeiro comeza primeiro a tarefa máis curta e, polo tanto, aumenta o tempo de resposta, mentres que o segundo é dividido entre todas as tarefas por igual, aumentando o tempo de resposta. Ambos os algoritmos son malos onde os algoritmos da outra familia son bos. Tamén analizamos como o uso paralelo da CPU e E/S pode mellorar o rendemento, pero non resolvemos o problema coa clarividencia do SO. E na próxima lección veremos un planificador que mira ao pasado inmediato e trata de predecir o futuro. E chámase cola de comentarios de varios niveis.
Fonte: www.habr.com