Algoritmo de agendamento FCFS: o que é, programa de exemplo
Nathaniel Brooks
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
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 |
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 |
Passo 4) No tempo=3, o processo P4 completa sua execução.
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 |
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 |
Passo 7) No tempo 11, P3 completa sua execução.
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
Passo 9) No tempo=17, P5 inicia a execução. Tem um tempo de burst de 4. Conclui a execução no tempo = 21
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
Passo 11) Vamos calcular o tempo médio de espera para o exemplo acima.
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
= 40 / 5 = 8
Vantagens do FCFS
Aqui estão os prós/benefícios de usar o algoritmo de agendamento FCFS:
- A forma mais simples de um Algoritmo de escalonamento de CPU
- Fácil de programar
- Primeiro a chegar, primeiro a ser servido
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.
