. Introducao-ao-Escalonamento
Esse documento representa parte dos meus estudos acerca do Livro - Operational Systems Three Easy Pieces, de dominio publico.
3.0 Escalonamento
3.1 Metricas de escalonamento
Existem diversas metricas para qualificarmos politicas de escalonamento ou apenas medir por prazer o que um metodo de escalonamento faz. Neste momento, usaremos apenas o turnaround time, o qual eh definido pela diferenca entre o tempo de completude do processo e o tempo de chegada. $$T_{turnaround} = T_{completion} - T_{arrival} $$
3.1.1 First In, First Out (FIFO)
O algoritmo mais basico de escalonamento eh o FIFO, primeiro a entrar eh o primeiro a sair.
exemplo: se 3 processos, A, B e C chegam no processo nesta ordem, sem tempo de chegada, podemos calcular a media de turnaround time apenas somando o tempo de completude de cada um e dividindo pela quantidade de processos, neste caso, os 3, e.g: $T_{c}(A) = 10, T_{c}(B) = 20, T_{c}(C) = 30, T_{tt} = \frac{10 + 20 + 30}{3} = 20$
se um processo rodasse por mais do que o tempo definido, teriamos um problema chamado de efeito de comboio, ou seja, varios processos menores poderiam ter sido executados antes de um processo que precisaria usar mais a CPU. Este problema nos leva a proxima solucao:
Shortest Job First (SJF)
O trabalho mais curto primeiro mata o problema de efeito de comboio, ja que voce executara o processo pequeno antes de precisar segurar a CPU para um processo mais pesado. O problema deste metodo esta no fato de que processos nao chegam a lista de processos ao mesmo tempo, eles chegam em tempo assincronamente. Isto nos leva a outro metodo.
Shortest Time-to-Completion First (STCF)
Este metodo calcula o quanto um processo precisa para terminar assim que ele entra na lista de processos e alterar qual processo usa a CPU de acordo com essa metrica. ASsim, atraves de context switch e preempting, o processo B pode tomar o lugar do processo A.
Tempo de resposta
A metrica tempo de resposta pode ser definida como:
$$T_{response} = T_{firstrun} - T_{arrival} $$
Desta forma, se A chegar no tempo 0, B e C no tempo 10, teremos a seguinte conta de media de tempo de resposta:
$$T_{r}(A) = 0, T_{c}(B) = 0, T_{r}(C) = 10, T_{r} = \frac{0 + 0 + 10}{3} = 3.33$$
Round Robin
Para fazer melhor gerenciamento e otimizar o escalonamento baseado nesta nova metrica. O Round Robin nao roda um programa ate sua completude, ele o executa em fatias de tempo.
cada fatia de tempo tem de ser um multiplo do timer de interrupcao, e.g: se o timer = 10ms, entao cada slice pode ter 10ms, 20ms e assim por diante.
para amortizar o tempo perdido com context switch, podemos aumentar o tamanho do slice. E.g: se o time slice tem 10ms e o context switch leva 1ms, perdemos 10% do slice so com troca de contexto. Assim, se fizermos o slice com 5 vezes o tamanho (50ms), apenas 2% sera “perdido”.
I/O
Quando um processo inicia um I/O, ele entra em estado de espera (blocked). Neste instante, o scheduler deve, evidentemente, disparar outro processo para rodar, enquanto aguarda a interrupcao para alterar o processo bloqueado para pronto.
[!attention] Exemplo
Vamos supor que temos 2 processos, A e B, ambos com 50ms para completude. A diferenca, A usa 10ms e depois requisita I/O, que tambem demora 5 vezes, enquanto B faz apenas 50ms. Como podemos otimizar o uso da cpu nesse caso?
Uma maneira de fazer isso eh dividir um processo A entre mini-processos de tamanho definidos (misturando a ideia de RR com STCF), assim, o processo B entra em acao enquanto A espera pelo I/O.