Shortest remaining time

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

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.

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

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

• 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

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

• Escalonamento de processos

Ligações externas

• Scheduling algorithm em inglês
• Process (computing) em inglês
• Process states em inglês
• Automated planning and scheduling em inglês
• Dynamic priority scheduling em inglês