Agendamento FCFS

No caso de multiprogramação, a CPU precisa ser escalonada, para que múltiplos trabalhos possam ser realizados simultaneamente em menos tempo ou ao mesmo tempo. Pelo escalonamento da CPU é decidido qual dos processos da fila de prontidão será alocado na CPU. Portanto, existem muitos algoritmos de escalonamento de CPU para escalonar a CPU. O escalonamento FCFS é um dos algoritmos de escalonamento da CPU.

Agendamento FCFS (FIRST-COME, FIRST-SERVED)

FCFS é considerado o algoritmo de escalonamento de CPU mais simples. No algoritmo FCFS, o processo que solicita primeiro a CPU é alocado primeiro na CPU. A implementação do algoritmo FCFS é gerenciada com fila FIFO (Primeiro a entrar, primeiro a sair). O agendamento FCFS não é preemptivo. Não preemptivo significa que, uma vez alocada a CPU para um processo, esse processo mantém a CPU até executar um trabalho ou tarefa e liberar a CPU, seja solicitando E/S.

Exemplo da vida real de agendamento FCFS

Como exemplo da vida real de agendamento do FCFS, pode-se observar um sistema de balcão de cobrança de shopping center. A primeira pessoa na fila recebe a conta primeiro e depois a próxima pessoa tem a chance de receber a conta e efetuar o pagamento e assim por diante. Se nenhuma prioridade for dada aos clientes VIP, o sistema de cobrança continuará assim (significa que a primeira pessoa (primeira tarefa) na fila receberá a conta primeiro e após terminar (executar) o pagamento do primeiro cliente, o balconista (CPU ) prestará atenção a outros clientes (tarefas separadas) à medida que estiverem na fila). Como o FCFS é do tipo não preemptivo, nenhuma prioridade será dada às tarefas aleatórias importantes.

Exemplos matemáticos de agendamento FCFS

Em problemas de escalonamento de CPU, alguns termos são usados durante a resolução dos problemas, portanto, para fins conceituais, os termos são discutidos a seguir -

• Hora de chegada (AT) - Hora de chegada é a hora em que o processo chega na fila de prontos.

• Burst time (BT) ou tempo de CPU do processo - Burst time é a unidade de tempo em que um determinado processo conclui sua execução.

• Tempo de conclusão (CT) - O tempo de conclusão é o momento em que o processo foi encerrado.

• Tempo de retorno (TAT) - O tempo total desde o tempo de chegada até o tempo de conclusão é conhecido como tempo de retorno. TAT pode ser escrito como,

Tempo de entrega (TAT)=Tempo de conclusão (CT) – Tempo de chegada (AT) ou, TAT=Tempo de ruptura (BT) + Tempo de espera (WT)

• Tempo de espera (WT) - Tempo de espera é o tempo em que o processo aguarda sua alocação enquanto o processo anterior está na CPU para execução. WT é escrito como,

Tempo de espera (WT)=Tempo de retorno (TAT) – Tempo de pico (BT)

• Tempo de resposta (RT) - O tempo de resposta é o momento em que a CPU foi alocada para um processo específico pela primeira vez.

  No caso de agendamento não preemptivo, geralmente o tempo de espera e o tempo de resposta são iguais.

• Gráfico de Gantt - O gráfico de Gantt é uma visualização que ajuda a agendar e gerenciar tarefas específicas em um projeto. É utilizado na resolução de problemas de escalonamento, para ter uma ideia de como os processos estão sendo alocados em diferentes algoritmos.

Problema 1

Considere a tabela abaixo e encontre o tempo de conclusão (CT), o tempo de resposta (TAT), o tempo de espera (WT), o tempo de resposta (RT), o tempo médio de resposta e o tempo médio de espera.

Solução

gráfico de Gantt

Para este problema CT, TAT, WT, RT é mostrado na tabela fornecida -

Tempo médio de espera=(9+8+0+4+12)/5=33/5=6,6 unidades de tempo (a unidade de tempo pode ser considerada como milissegundos)

Tempo médio de resposta=(11+14+4+11+16)/5=56/5=11,2 unidade de tempo (a unidade de tempo pode ser considerada como milissegundos)

Problema 2

Considere a tabela abaixo e encontre o tempo de conclusão (CT), tempo de resposta (TAT), tempo de espera (WT), tempo de resposta (RT), tempo médio de resposta e tempo médio de espera.

Solução

Gráfico de Gantt -

Para este problema CT, TAT, WT, RT é mostrado na tabela fornecida -

Tempo médio de espera=(0+0+2+4+8)/5=14/5=2,8 unidades de tempo (a unidade de tempo pode ser considerada como milissegundos)

Tempo médio de resposta=(2+1+5+9+13)/5=30/5=6 unidades de tempo (a unidade de tempo pode ser considerada como milissegundos)

*No período de CPU ociosa (não ativa), nenhum processo é programado para ser encerrado, portanto neste período ele permanece nulo por um breve período.

Vantagens do agendamento FCFS

• É um algoritmo fácil de implementar, pois não inclui nenhuma forma complexa.

• Cada tarefa deve ser executada simultaneamente, pois segue a fila FIFO.

• O FCFS não dá prioridade a nenhuma tarefa aleatória importante primeiro, portanto é um agendamento justo.

Desvantagens do agendamento FCFS

• O FCFS resulta em efeito de comboio, o que significa que se um processo com tempo de burst mais alto chegar primeiro na fila de prontidão, os processos com tempo de burst mais baixo poderão ser bloqueados e os processos com tempo de burst mais baixo poderão não conseguir obter a CPU se o tempo de burst mais alto tarefa leva tempo para sempre.

• Se um processo com tempo de rajada longo entrar na linha primeiro, então o outro processo com tempo de rajada curto terá que esperar por um longo tempo, portanto não é muito bom como sistemas de compartilhamento de tempo.

• Por não ser preemptivo, ele não libera a CPU antes de concluir completamente a execução da tarefa.

*Efeito comboio e fome parecem semelhantes, mas há uma pequena diferença, por isso é aconselhável não tratar esses dois termos como as mesmas palavras.

Conclusão

Embora o FCFS seja simples de implementar e entender, o FCFS não é bom para sistemas interativos e não é usado em sistemas operacionais modernos. O efeito Convoy no FCFS pode ser evitado usando outros algoritmos preemptivos de escalonamento de CPU, como 'agendamento Round-robin'.