Longest Remaining Time First (LRTF) ou Preemptive Longest Job First Algoritmo de agendamento de CPU

O algoritmo de agendamento Longest Remaining Time First (LRTF) é uma variante do algoritmo Longest Job First (LJF) e é usado pelo sistema operacional para agendar processos de entrada. No LRTF, o processo com o maior tempo de execução restante recebe a prioridade mais alta e é programado para ser executado primeiro. Em intervalos de tempo, como em cada unidade de tempo, o sistema verifica se chegou outro processo com um tempo de intermitência maior. Se tal processo existir, ele será agendado para execução antes de continuar com o processo atual. O algoritmo foi projetado para maximizar a utilização do processador e minimizar o tempo de espera dos processos.

Características do algoritmo de agendamento do Longest Remaining Time First (LRTF)

• Longest Remaining Time First (LRTF) é um algoritmo de escalonamento de CPU popular usado para determinar a ordem em que os processos recebidos são executados de maneira sistemática.

• O algoritmo LRTF segue uma abordagem preemptiva, onde a CPU é alocada apenas por um intervalo fixo de tempo e o processo com maior tamanho de burst é selecionado para execução.

• O processo com o maior tamanho de rajada pode ser executado por um período fixo de tempo, após o qual o processo de seleção ocorre novamente.

• Entretanto, o LRTF não é um algoritmo de escalonamento ideal devido ao seu alto tempo médio de espera.

• O algoritmo LRTF prioriza processos de longa execução, fazendo com que processos mais curtos esperem, resultando em um aumento no tempo médio de espera.

Vantagens

• O algoritmo LRTF é simples de implementar e entender, tornando-o amplamente utilizado em diversos sistemas operacionais.

• O tempo de conclusão de quase todos os processos ocorre antes que o trabalho mais longo seja concluído.

• O algoritmo LRTF é livre de fome, o que significa que todos os processos recebem uma parte justa da CPU.

Desvantagens

• A troca de contexto do algoritmo LRTF utiliza tempo de CPU que poderia ser usado de forma mais produtiva para executar processos.

• Processos mais baixos podem ter que permanecer para que a CPU termine de executar processos mais longos com tamanhos de intermitência maiores

• Apesar de ter um tempo de burst menor para cada processo, o algoritmo LRTF possui um tempo médio de espera e um tempo médio de resposta maiores.

Algoritmo de escalonamento de CPU com maior tempo restante (LRTF)

• Classifique os processos pela hora de chegada, em ordem crescente.

• Escolha o processo com menor tempo de chegada, mas com maior tempo de burst.

• Execute o processo escolhido por uma unidade de tempo.

• Verifique se algum novo processo chegou e, em caso afirmativo, compare o tempo de intermitência restante com o processo atual. Se o novo processo tiver um tempo de intermitência restante maior, preempte o processo atual e comece a executar o novo processo.

• Repita as etapas 2 a 4 até que todos os processos tenham sido executados.

Exemplo de tempo restante mais longo primeiro (LRTF)

Primeiro, vamos classificar os processos com base na hora de chegada -

Agora, vamos criar o gráfico de Gantt com base no Longest Remaining First Scheduling -

Explicação

• No tempo t=0, o único processo disponível é P1 com tempo de burst 3. Assim, P1 inicia a execução.

• No tempo t=1, P2 chega com um tempo de burst de 6, mas P1 ainda possui 2 unidades do tempo restante. Mas comparado ao P1, o P2 tem mais unidades. Assim, P2 é adicionado à fila de prontos.

• Então, aqui P2 é repetido até t=5, depois disso comparado com P1, P2, P3 e P4 têm mais unidades. Assim, P4 é adicionado à fila de prontos.

• Em t=6, ou seja, após a execução de P4, repetimos o mesmo processo até que todos os processos tenham sido executados.

• No tempo t=14, P2 completa sua execução e todos os processos são concluídos.

Agora, vamos calcular o tempo de espera e o tempo de resposta de cada processo -

Visto que o tempo de conclusão (C.T) pode ser determinado diretamente pelo gráfico de Gantt, e

Tempo de entrega (TAT)

= (Hora de conclusão) – (Hora de chegada)

Além disso, tempo de espera (WT)

= (Tempo de retorno) - (Tempo de explosão)

Saída

Tempo total de resposta=36 ms

Portanto, tempo médio de resposta=44/4=11 ms

E, tempo total de espera=18 ms

Portanto, tempo médio de espera=32/4=8 ms

Conclusão

O algoritmo de agendamento Longest Remaining Time First (LRTF) é comumente usado por sistemas operacionais para garantir que o processador seja usado de forma eficiente e que os processos não precisem esperar muito. Funciona dando prioridade ao processo que tem mais tempo para ser concluído. No entanto, esse algoritmo não é perfeito porque processos menores podem ter que esperar mais tempo para que processos maiores sejam concluídos. Apesar disso, o algoritmo LRTF é fácil de entender e implementar, e geralmente termina a maioria dos processos antes que o mais longo termine. O algoritmo LRTF garante que todos os processos tenham uma chance justa de usar a CPU. No entanto, outros algoritmos de escalonamento podem ser melhores para determinados sistemas, dependendo das suas necessidades.