Algoritmo de agendamento FCFS: o que é, programa de exemplo

⚡ Resumo Inteligente

O escalonamento FIFO (First Come First Serve) executa os processos exatamente na ordem em que chegam à fila de prontos, usando uma abordagem FIFO não preemptiva simples, o que o torna o algoritmo de escalonamento de CPU mais fácil de implementar em um sistema operacional.

  • 🔄 Definição: O FCFS atribui a CPU ao processo que a solicita primeiro, gerenciando a fila de prontos como uma estrutura do tipo primeiro a entrar, primeiro a sair (FIFO).
  • ⚙️ Natureza: O FCFS não é preemptivo, portanto, um processo em execução mantém a CPU ocupada até que termine todo o seu tempo de execução.
  • 🎟️ Analogia: Assim como em uma fila de bilheteria, o processo que chega primeiro é atendido primeiro, e os que chegam depois esperam a sua vez.
  • 📊 Cálculo: O tempo médio de espera é calculado por subtraccalculando o tempo de chegada de cada processo a partir do seu tempo de início e, em seguida, calculando a média entre todos os processos.
  • ???? Efeito comboio: Um processo longo na linha de frente força tarefas mais curtas a esperar, aumentando o tempo médio de espera e prejudicando o desempenho.
  • 🤖 Ângulo da IA: O aprendizado de máquina prevê os tempos de execução de rajadas para melhorar o agendamento, e o Copilot ajuda a escrever e testar código FCFS rapidamente.

Algoritmo de escalonamento FCFS em OperaSistema de Ting

O que é o método First Come First Serve?

Primeiro a chegar, primeiro a servir (FCFS) FCFS é um algoritmo de escalonamento de sistema operacional que executa automaticamente solicitações e processos enfileirados na ordem de chegada. É o algoritmo de escalonamento de CPU mais simples e fácil de usar. Nesse tipo de algoritmo, o processo que solicita a CPU primeiro recebe a alocação de CPU primeiro. Isso é gerenciado por uma fila FIFO. A sigla FCFS significa "First Come First Serve" (Primeiro a Chegar, Primeiro a Ser Servido).

Quando um processo entra na fila de prontos, seu PCB (Bloco de Controle de Processo) é vinculado ao final da fila. Assim, quando a CPU fica livre, ela é alocada ao processo no início da fila.

Características do método FCFS

As principais características do método "First Come First Serve" estão listadas abaixo:

  • É um não preventivo algoritmo de agendamento, de forma que um processo mantenha a CPU ocupada até completar seu tempo de execução.
  • Os trabalhos são sempre executados por ordem de chegada.
  • É fácil de implementar e usar.
  • Este método tem desempenho ruim e o tempo de espera geral é bastante alto.

Exemplo de escalonamento FCFS

Um exemplo prático do método FCFS (primeiro a chegar, primeiro a ser servido) é a compra de um ingresso de cinema na bilheteria. Nesse algoritmo de agendamento, as pessoas são atendidas de acordo com a ordem da fila. A primeira pessoa a chegar compra o ingresso, e assim por diante, até que a última pessoa da fila compre o seu. Utilizando esse algoritmo, o processo da CPU funciona de maneira semelhante.

Como funciona o FCFS? Calculando o tempo médio de espera

Para entender como o algoritmo agenda os processos, aqui está um exemplo de cinco processos chegando em momentos diferentes. Cada processo tem um tempo de execução diferente.

Processo Tempo de explosão Tempo de chegada
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Usando o algoritmo de escalonamento FCFS, esses processos são tratados da seguinte maneira.

Passo 1) O processo começa com P4, que tem tempo de chegada 0.

Exemplo de agendamento FCFS - Etapa 1

Passo 2) No tempo=1, chega P3. P4 ainda está em execução. Portanto, P3 é mantido em fila.

Exemplo de agendamento FCFS - Etapa 2

Passo 3) No instante t=2, P1 chega e é mantido na fila.

Exemplo de agendamento FCFS - Etapa 3

Passo 4) No instante t=3, o processo P4 completa sua execução.

Exemplo de agendamento FCFS - Etapa 4

Passo 5) No tempo=4, P3, que é o primeiro da fila, inicia a execução.

Exemplo de agendamento FCFS - Etapa 5

Passo 6) No instante t=5, P2 chega e é colocado em uma fila.

Exemplo de agendamento FCFS - Etapa 6

Passo 7) No instante t=11, P3 completa sua execução.

Exemplo de agendamento FCFS - Etapa 7

Passo 8) No instante t=11, P1 inicia a execução. Ele tem um tempo de execução de 6, portanto, completa a execução no intervalo de tempo 17.

Exemplo de agendamento FCFS - Etapa 8

Passo 9) No instante 17, P5 inicia a execução. Ele tem um tempo de execução de 4, portanto, conclui a execução no instante 21.

Exemplo de agendamento FCFS - Etapa 9

Passo 10) No instante t=21, P2 inicia a execução. Ele tem um tempo de execução de 2, portanto, completa a execução no intervalo de tempo 23.

Exemplo de agendamento FCFS - Etapa 10

Passo 11) Agora, vamos calcular o tempo médio de espera para o exemplo acima.

tempo médio de espera no agendamento FCFS

Waiting time = Start time - Arrival time

P4 = 0 – 0 = 0

P3 = 3 – 1 = 2

P1 = 11 – 2 = 9

P5 = 17 – 4 = 13

P2 = 21 – 5 = 16

Tempo médio de espera = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8

Cálculo do tempo médio de espera no escalonamento FCFS

Vantagens do FCFS

Aqui estão as vantagens e os benefícios de usar o algoritmo de escalonamento FCFS:

Desvantagens do FCFS

Aqui estão as desvantagens e os inconvenientes de usar o algoritmo de escalonamento FCFS:

  • É um algoritmo de escalonamento de CPU não preemptivo, portanto, uma vez que um processo tenha sido alocado à CPU, ele nunca liberará a CPU até que termine sua execução.
  • O tempo médio de espera é alto.
  • Os processos curtos no final da fila têm que esperar que o processo longo no início termine.
  • Não é uma técnica ideal para sistemas de tempo compartilhado.
  • Devido à sua simplicidade, o FCFS não é muito eficiente.

Perguntas Frequentes

O algoritmo FIFO (First Come First Serve) não é preemptivo. Uma vez que um processo obtém a CPU, ele é executado até que seu período de execução termine, portanto o escalonador não pode interrompê-lo para executar um processo recém-chegado ou mais curto.

O efeito comboio ocorre quando vários processos curtos ficam à espera de um único processo longo que está no início da fila. Essa tarefa longa aumenta o tempo médio de espera e diminui a produtividade geral da CPU.

O tempo de retorno é igual ao tempo de conclusão menos o tempo de chegada de cada processo. Ele mede o tempo total que um processo passa no sistema, desde sua chegada até a conclusão de sua execução na CPU.

O atendimento é feito por ordem de chegada. Trabalho mais curto primeiro Serve primeiro a porção menor para reduzir o tempo de espera, e Round Robin Atribui a cada processo uma fração de tempo fixa para compartilhamento de tempo.

O FCFS puro não causa inanição, porque todos os processos eventualmente chegam ao início da fila FIFO. No entanto, tarefas longas ainda podem atrasar significativamente as curtas devido ao efeito comboio.

O algoritmo FCFS tem complexidade O(n) quando os processos já estão ordenados por chegada, visto que cada um é agendado apenas uma vez. Ordenar as chegadas não ordenadas por tempo de chegada primeiro adiciona uma etapa de O(n log n).

Modelos de aprendizado de máquina preveem os tempos de execução de processos e selecionam ou ajustam políticas de agendamento para reduzir o tempo médio de espera e o consumo de energia. Pesquisadores aplicam esses agendadores baseados em IA em servidores em nuvem e data centers.

Sim. O GitHub Copilot pode gerar código FCFS em C. Java, ou Python com cálculos de tempo de espera e tempo de resposta. Sempre verifique as fórmulas de classificação por horário de chegada, desempate e média antes de confiar no resultado.

Resuma esta postagem com: