CÁLCULO DE TEMPO DE ESPERA MÉDIO - ESCALONAMENTO SJF PREEMPTIVO

Vou postar um exemplo simples do algoritmo de escalonamento SJF preemptivo, pois tive muita dificuldade de achar uma referência que explicasse os exemplos que já estão prontos na internet.

O algoritmo SJF pode ser preemptivo ou não-preemptivo. No preemptivo, pode ser que no momento da execução de um processo, no estado do processo (veja quais são os estados do processo), apareça na fila de processos prontos, um processo com seu tempo de surto de CPU (também  conhecido como surto de CPU ou burst time), mais curto do que o tempo de surto do processo atual em execução. Neste momento o algoritmo SJF preemptivo interromperá o processo em execução no momento, enviando-o para fila de pronto/bloqueado, dando a vez para o processo com o menor surto, de ser executado.

Considere o exemplo abaixo, o tempo de execução (também  conhecido como surto de CPU ou burst time) como tempo em milissegundos:







É aqui que está a grande dificuldade de achar algum post que explique, até a referência do livro não mostra como foi calculado o tempo médio de espera.

VAMOS PARA O PASSO A PASSO:

Como não existia nenhum processo, chega P1 como próximo processo na fila de pronto, no tempo de chegada igual a 0.0, e vai para execução. Ele possui um tempo de execução  (também  conhecido como surto de CPU ou burst time) que irá utilizar a CPU, igual a 7 milissegundos. A CPU, executa P1 normalmente até o tempo de chegada igual a 2.0, que é o momento que aparece o P2 na fila de pronto que possui o tempo de execução menor que o atual processo (P1 agora com 5 milissegundos a executar, enquanto P2 chegou com 4milissegundos). A CPU interrompe P1, que executou dos seus 7 milissegundos, somente 2 milissegundos, coloca-o como bloqueado (processo pronto para executar mas que não tem a CPU) e passa a executar P2, que irá executar seus 4milisegundos. No tempo de chegada igual a 4, aparece o P3 que possui o tempo de execução igual a 1 (neste momento P2 executou 2milissegundos dos seus 4). Lembrando que, a CPU só da a vez para os processos que estão  chegando com seus respectivos tempo de execução, por serem menores que os atuais que estão sendo executados e por serem PREEMPTIVO, caso fossem não-preemptivo, a CPU executaria normalmente até acabar seus tempos de execução e passaria a vez para o próximo da fila de prontos, conforme algoritmo de escalonamento (FIFO ou SJF).

P3 executa até o tempo igual a 5, que coincide com o tempo de chegada do P4 com seu tempo de execução igual a 4, e encerra sua participação, porém, já existe um processo com tempo menor aguardando a CPU, é o caso do P2 que restou 2milissegundo a ser executado. O mesmo, executa até tempo 7 e encerra sua participação. Neste momento existe o P1 aguardando com 5milissegundo de tempo de execução restantes e P4 com 4milissegundo de tempo de execução que ainda não foram executados. A CPU escolhe o de menor tempo (por isso do SFJ, Small Job First), então o P4 executa seus 4 milissegundos e após P1 avança, terminando seus 5 milissegundos restantes.

CÁLCULO DO TEMPO DE ESPERA MÉDIO:

vamos começar por ordem dos processos de P1 ao P4.

P1 executa até tempo 2, após, somente no tempo 11. Como já tinha executado as 2 unidade de tempo, então fica o tempo 11 - (subtração) o tempo 2 - (subtração) o tempo de chegada 0.0. Ficando 11 - 2 - 0.0 = 9, que é o tempo médio de espera do processo P1 para ser executado.

TM P1 = 9

(9)


P2 executa do tempo 2 até tempo 4, executando 2 unidades de tempo, após, somente no tempo 5, ficando 2 unidades de tempo executadas - (subtração) o tempo 5 - (subtração) o tempo de chegada 2.0. Ficando 2  - 5 - 2.0 =1, que é o tempo médio de espera do processo P2 para ser executado.

TM P2 = 1

(9 + 1)

P3 executa no tempo 4, apenas uma unidade, acabando em seguida. Ficando o tempo 4 - (subtração) o tempo de chegada 4.0. Ficando 4 - 4.0 = 0, que é o tempo médio de espera do processo P3 para ser executado.

TM P3 = 0

(9 + 1 + 0)

P4 executa no tempo 7 as suas 4 unidades de tempo e, após, acaba. Ficando o tempo 7 - (subtração) o tempo de chegada 5.0. Ficando 7 - 5.0 = 2, que é o tempo médio de espera do processo P4 para ser executado.

TM P4 = 2

(9 + 1 + 0 + 2)

agora dividimos pelo total de processos. Ficando (9 + 1 + 0 + 2) / 4 = 3.


Referência:

SILBERSCHATZ, A., PETER G., GREG G. SISTEMA OPERACIONAIS - Conceitos e Aplicações