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

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

Primeiro a chegar, primeiro a servir (FCFS) é um algoritmo de escalonamento do sistema operacional que executa automaticamente solicitações e processos enfileirados na ordem de chegada. É o algoritmo de escalonamento de CPU mais fácil e simples. Neste tipo de algoritmo, os processos que solicitam primeiro a CPU obtêm primeiro a alocação da CPU. Isso é gerenciado com uma fila FIFO. A forma completa do FCFS é First Come First Serve.

À medida que o processo entra na fila de prontos, seu PCB (Process Control Block) é vinculado ao final da fila e, quando a CPU fica livre, deve ser atribuída ao processo no início da fila.

Características do método FCFS

  • Ele suporta algoritmo de agendamento não preemptivo e preemptivo.
  • 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 agendamento FCFS

Um exemplo real do método FCFS é comprar um ingresso de cinema na bilheteria. Neste algoritmo de agendamento, uma pessoa é atendida de acordo com o formato da fila. Quem chega primeiro na fila compra primeiro o ingresso e depois o seguinte. Isso continuará até que a última pessoa da fila compre o ingresso. Usando este algoritmo, o processo da CPU funciona de maneira semelhante.

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

Aqui está um exemplo de cinco processos chegando em momentos diferentes. Cada processo tem um tempo de burst diferente.

Extração 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 hora de chegada 0

Obras do FCFS

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

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

Obras do FCFS

Passo 3) No tempo = 2 chega P1 que fica na fila.

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

Obras do FCFS

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

Obras do FCFS

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

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

Obras do FCFS

Passo 6) No tempo =5, P2 chega e é mantido em fila.

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

Obras do FCFS

Passo 7) No tempo 11, P3 completa sua execução.

Obras do FCFS

Passo 8) No tempo=11, P1 inicia a execução. Tem um tempo de burst de 6. Conclui a execução no intervalo de tempo 17

Obras do FCFS

Passo 9) No tempo=17, P5 inicia a execução. Tem um tempo de burst de 4. Conclui a execução no tempo = 21

Obras do FCFS

Passo 10) No tempo=21, P2 inicia a execução. Tem um tempo de burst de 2. Conclui a execução no intervalo de tempo 23

Obras do FCFS

Passo 11) Vamos calcular o tempo médio de espera para o exemplo acima.

Obras do FCFS

Waiting time = Start time - Arrival time

P4 = 0-0 = 0

P3 = 3-1 = 2

IP = 11-2 = 9

P5= 17-4 = 13

P2= 21-5= 16

Tempo Médio de Espera

Obras do FCFS
= 40 / 5 = 8

Vantagens do FCFS

Aqui estão os prós/benefícios de usar o algoritmo de agendamento FCFS:

Desvantagens do FCFS

Aqui estão as desvantagens/desvantagens do uso do algoritmo de escalonamento FCFS:

  • É um algoritmo de escalonamento de CPU não preemptivo, portanto, após o processo ter sido alocado para a CPU, ele nunca irá liberar a CPU até que termine de ser executado.
  • O tempo médio de espera é alto.
  • Processos curtos que estão no final da fila precisam esperar que o processo longo na frente termine.
  • Não é uma técnica ideal para sistemas de compartilhamento de tempo.
  • Devido à sua simplicidade, o FCFS não é muito eficiente.

Resumo

  • Definição: FCFS é um algoritmo de escalonamento do sistema operacional que executa automaticamente solicitações e processos enfileirados por ordem de chegada
  • Suporta agendamento não preemptivo e preventivo
  • algoritmo.
  • FCFS significa Primeiro a chegar, primeiro a servir
  • Um exemplo real do método FCFS é comprar um ingresso de cinema na bilheteria.
  • É a forma mais simples de algoritmo de escalonamento de CPU
  • É um algoritmo de escalonamento de CPU não preemptivo, portanto, após o processo ter sido alocado para a CPU, ele nunca irá liberar a CPU até que termine de ser executado.