Shortest remaining time

(Redirecionado de SRT)

Shortest remaining time ("tempo remanescente mais curto" em inglês; sigla: SRT) é a variante preemptiva do escalonamento SJF. A fila de processos a serem executados pelo SRT é organizada conforme o tempo estimado de execução, ou seja, de forma semelhante ao SJF, sendo processados primeiros os menores jobs. Na entrada de um novo processo, o algoritmo de escalonamento avalia seu tempo de execução incluindo o job em execução, caso a estimativa de seu tempo de execução seja menor que o do processo concorrentemente em execução, ocorre a substituição do processo em execução pelo recém chegado, de duração mais curta, ou seja, ocorre a preempção do processo em execução.

Exemplo de execução do algoritmo shortest remaining time.

Cada processo suspenso pelo SRT deverá ser recolocado na fila em uma posição correspondente apenas ao seu tempo restante de execução e não mais o tempo de execução total, tornando-se necessário registrar os tempos decorridos de execução de cada processo suspenso.

Vantagens

editar

A principal diferença para o algoritmo SJF é a preempção, digamos que um processo X esteja em execução na CPU e nesse meio tempo chegue um processo Y menor do que o restante do processo X, nesse momento ocorrerá uma preempção, ou seja, o processo X irá parar sua execução e ceder lugar para o processo Y executar. Caso chegue um processo ainda menor que o restante do processo Y, esse processo ganhará a CPU e o processo Y retornará para a fila de prontos antes de terminar e irá aguardar um momento para ser executado.

Para que a preempção ocorra é necessário um timer que determine corretamente o tempo em que uma interrupção de hardware possa alternar os processos.

Como o trabalho mais curto em primeiro lugar, ele tem potencial para inanição do processo; longos processos podem ser mantidos indefinidamente se processos curtos forem continuamente adicionados. Essa ameaça pode ser mínima quando os tempos de processo seguem uma distribuição de cauda pesada.<ref>{{cite journal |last=Harchol-Balter |first=Mor |last2=Schroeder |first2=Bianca |last3=Bansal |first3=Nikhil |last4=Agrawal |first4=Mukesh |year=2003 |title=Size-Based Scheduling to Improve Web Performance |journal

Características

editar
  • Preempção: interrompe um processo e inicia outro menor.
  • Tempo de resposta: possuirá um tempo de resposta muito bom se o processo não for muito grande, caso seja demorará muito para começar a ser executado.
  • Tempo de espera: caso comece a ser executado e de repente volte à fila de prontos, terá um tempo de espera maior que o tempo de resposta.
  • Starvation: possível de ocorrer em processos longos.
  • Throughput: possuirá um alto número de processos por unidade de tempo.

Quando um processo qualquer começa a executar e nenhum outro processo é menor que ele em nenhum momento, ele irá possuir o tempo de espera igual ao tempo de resposta.

Exemplo

editar

Digamos que um processo 0 inicie a execução no tempo 0 e tenha uma duração de 5 segundos. Um outro processo 1 chegue à fila de prontos no tempo 2 e sua duração seja de 2 segundos. O processo 0 que está atualmente em execução faltando 3 segundos para terminar, não concluirá e vai direto para a fila de prontos esperar que o processo 1 que é menor seja executado. Após isso o processo 0 termina sua execução, confira na animação abaixo:

 
 

Ver também

editar

Referências

Ligações externas

editar
  Este artigo sobre informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.