Pesquisa de site

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.

Process ID

Arrival time

Burst time

P1

2

2

P2

5

6

P3

0

4

P4

0

7

P5

7

4

Solução

gráfico de Gantt

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

Process ID

Arrival time

Burst time

CT

TAT=CT-AT

WT=TAT-BT

RT

P1

2

2

13

13-2= 11

11-2= 9

9

P2

5

6

19

19-5= 14

14-6= 8

8

P3

0

4

4

4-0= 4

4-4= 0

0

P4

0

7

11

11-0= 11

11-7= 4

4

P5

7

4

23

23-7= 16

16-4= 12

12

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.

Process ID

Arrival time

Burst time

P1

2

2

P2

0

1

P3

2

3

P4

3

5

P5

4

5

Solução

Gráfico de Gantt -

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

Process ID

Arrival time

Burst time

CT

TAT=CT-AT

WT=TAT-BT

RT

P1

2

2

4

4-2= 2

2-2= 0

0

P2

0

1

1

1-0= 1

1-1= 0

0

P3

2

3

7

7-2= 5

5-3= 2

2

P4

3

5

12

12-3= 9

9-5= 4

4

P5

4

5

17

17-4= 13

13-5= 8

8

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'.

Artigos relacionados: