Algoritmos de programação do sistema operacional

Um Process Scheduler agenda diferentes processos a serem atribuídos à CPU com base em algoritmos de agendamento específicos. Existem seis algoritmos de escalonamento de processos populares que iremos discutir neste capítulo -

  • Programação por ordem de chegada (FCFS)
  • Programação Shortest-Job-Next (SJN)
  • Agendamento prioritário
  • Menor Tempo Restante
  • Agendamento de Round Robin (RR)
  • Agendamento de filas de vários níveis

Esses algoritmos são non-preemptive or preemptive. Algoritmos não preemptivos são projetados para que, uma vez que um processo entre no estado de execução, ele não possa ser interrompido até que complete seu tempo alocado, enquanto o agendamento preemptivo é baseado na prioridade, onde um planejador pode antecipar um processo em execução de baixa prioridade a qualquer momento quando for de alta prioridade processo entra em um estado pronto.

Primeiro a chegar, primeiro a servir (FCFS)

  • Os trabalhos são executados por ordem de chegada.
  • É um algoritmo de escalonamento preventivo e não preemptivo.
  • Fácil de entender e implementar.
  • Sua implementação é baseada na fila FIFO.
  • Baixo desempenho porque o tempo médio de espera é alto.

Wait time de cada processo é o seguinte -

Processo Tempo de espera: Tempo de serviço - Tempo de chegada
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 8 - 2 = 6
P3 16 - 3 = 13

Tempo médio de espera: (0 + 4 + 6 + 13) / 4 = 5,75

Shortest Job Next (SJN)

  • Isso também é conhecido como shortest job first, ou SJF

  • Este é um algoritmo de escalonamento não preemptivo e preventivo.

  • Melhor abordagem para minimizar o tempo de espera.

  • Fácil de implementar em sistemas Batch onde o tempo de CPU necessário é conhecido com antecedência.

  • Impossível de implementar em sistemas interativos onde o tempo de CPU necessário não é conhecido.

  • O processador deve saber com antecedência quanto tempo o processo levará.

Dado: Tabela de processos, e seu tempo de chegada, tempo de execução

Processo Tempo de chegada Tempo de execução Tempo de serviço
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8

Waiting time de cada processo é o seguinte -

Processo Tempo de espera
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 14 - 2 = 12
P3 8 - 3 = 5

Tempo médio de espera: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Agendamento com base em prioridade

  • O escalonamento prioritário é um algoritmo não preemptivo e um dos algoritmos de escalonamento mais comuns em sistemas em lote.

  • Cada processo recebe uma prioridade. O processo com prioridade mais alta deve ser executado primeiro e assim por diante.

  • Os processos com a mesma prioridade são executados por ordem de chegada.

  • A prioridade pode ser decidida com base nos requisitos de memória, requisitos de tempo ou qualquer outro requisito de recurso.

Dado: Tabela de processos e sua hora de chegada, tempo de execução e prioridade. Aqui, estamos considerando que 1 é a prioridade mais baixa.

Processo Tempo de chegada Tempo de execução Prioridade Tempo de serviço
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5

Waiting time de cada processo é o seguinte -

Processo Tempo de espera
P0 0 - 0 = 0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5 - 3 = 2

Tempo médio de espera: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

Menor Tempo Restante

  • O menor tempo restante (SRT) é a versão preemptiva do algoritmo SJN.

  • O processador é alocado para o trabalho mais próximo da conclusão, mas pode ser eliminado por um trabalho pronto mais recente com tempo de conclusão mais curto.

  • Impossível de implementar em sistemas interativos onde o tempo de CPU necessário não é conhecido.

  • Geralmente é usado em ambientes em lote onde trabalhos curtos precisam dar preferência.

Agendamento de Round Robin

  • Round Robin é o algoritmo de escalonamento de processo preventivo.

  • Cada processo recebe um tempo fixo para execução, chamado de quantum.

  • Depois que um processo é executado por um determinado período de tempo, ele é interrompido e outro processo é executado por um determinado período de tempo.

  • A comutação de contexto é usada para salvar estados de processos antecipados.

Wait time de cada processo é o seguinte -

Processo Tempo de espera: Tempo de serviço - Tempo de chegada
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11

Tempo médio de espera: (9 + 2 + 12 + 11) / 4 = 8,5

Agendamento de filas de vários níveis

As filas de vários níveis não são um algoritmo de programação independente. Eles fazem uso de outros algoritmos existentes para agrupar e agendar trabalhos com características comuns.

  • Várias filas são mantidas para processos com características comuns.
  • Cada fila pode ter seus próprios algoritmos de agendamento.
  • As prioridades são atribuídas a cada fila.

Por exemplo, os trabalhos vinculados à CPU podem ser agendados em uma fila e todos os trabalhos vinculados a E / S em outra fila. O Process Scheduler então seleciona alternadamente os trabalhos de cada fila e os atribui à CPU com base no algoritmo atribuído à fila.