Agendamento de CPU Algorithms in OperaSistemas de gerenciamento

Tipos de agendamento de CPU

Aqui estão dois tipos de métodos de agendamento:

Agendamento Preemptivo

No Agendamento Preemptivo, as tarefas são atribuídas principalmente com suas prioridades. Às vezes é importante executar uma tarefa com prioridade mais alta antes de outra tarefa com prioridade mais baixa, mesmo que a tarefa com prioridade mais baixa ainda esteja em execução. A tarefa de menor prioridade é mantida por algum tempo e continua quando a tarefa de maior prioridade termina sua execução.

Agendamento Não Preemptivo

Neste tipo de método de escalonamento, a CPU foi alocada para um processo específico. O processo que mantém a CPU ocupada irá liberá-la alternando o contexto ou encerrando. É o único método que pode ser usado para diversas plataformas de hardware. Isso porque não precisa de hardware especial (por exemplo, um temporizador), como agendamento preemptivo.

Quando o agendamento é Preemptivo ou Não Preemptivo?

Para determinar se o agendamento é preemptivo ou não preemptivo, considere estes quatro parâmetros:

1. Um processo muda do estado de execução para o estado de espera.
2. Processo específico muda do estado de execução para o estado pronto.
3. Processo específico muda do estado de espera para o estado pronto.
4. O processo finalizou sua execução e foi encerrado.

Apenas as condições 1 e 4 se aplicam, o escalonamento é denominado não preemptivo.

Todos os outros agendamentos são preventivos.

Terminologias importantes de agendamento de CPU

• Tempo de rajada/tempo de execução: É um tempo requerido pelo processo para completar a execução. Também é chamado de tempo de execução.
• Tempo de chegada: quando um processo entra em um estado pronto
• Tempo de término: quando o processo é concluído e sai de um sistema
• Multiprogramação: Vários programas que podem estar presentes na memória ao mesmo tempo.
• Empregos: É um tipo de programa sem qualquer tipo de interação do usuário.
• Usuário: É um tipo de programa com interação do usuário.
• Processo: É a referência que é usada para trabalho e usuário.
• Ciclo de rajada de CPU/IO: Caracteriza a execução do processo, que alterna entre atividade de CPU e E/S. Os tempos de CPU são geralmente menores que o tempo de E/S.

Critérios de agendamento de CPU

Um algoritmo de escalonamento de CPU tenta maximizar e minimizar o seguinte:

Maximizar

Utilização da CPU:A utilização da CPU é a principal tarefa na qual o sistema operacional precisa garantir que a CPU permaneça o mais ocupada possível. Pode variar de 0 a 100 por cento. No entanto, para o RTOS, pode variar de 40% para sistema de baixo nível e 90% para sistema de alto nível.

Taxa de transferência: O número de processos que terminam sua execução por unidade de tempo é conhecido. Assim, quando a CPU está ocupada executando o processo, naquele momento o trabalho está sendo realizado, e o trabalho concluído por unidade de tempo é chamado de Throughput.

Minimizar

Tempo de espera: O tempo de espera é a quantidade que um processo específico precisa esperar na fila de prontidão.

Tempo de resposta: É o tempo que a solicitação foi enviada até que a primeira resposta seja produzida.

Tempo de resposta: O tempo de resposta é uma quantidade de tempo para executar um processo específico. É o cálculo do tempo total gasto esperando para entrar na memória, esperando na fila e executando na CPU. O período entre o momento da submissão do processo e o tempo de conclusão é o tempo de resposta.

Temporizador de intervalo

A interrupção do temporizador é um método intimamente relacionado à preempção. Quando um determinado processo obtém a alocação de CPU, um temporizador pode ser definido para um intervalo especificado. Tanto a interrupção do temporizador quanto a preempção forçam um processo a retornar a CPU antes que seu burst de CPU seja concluído.

A maior parte do sistema operacional multiprogramado usa algum tipo de temporizador para evitar que um processo prenda o sistema para sempre.

O que é despachante?

É um módulo que fornece controle da CPU ao processo. O Dispatcher deve ser rápido para que possa ser executado em todas as trocas de contexto. A latência de despacho é a quantidade de tempo necessária para o escalonador da CPU interromper um processo e iniciar outro.

Funções desempenhadas pelo Dispatcher:

• Mudança de contexto
• Mudando para o modo de usuário
• Movendo-se para o local correto no programa recém-carregado.

Tipos de algoritmo de agendamento de CPU

Existem basicamente seis tipos de algoritmos de escalonamento de processos

1. Primeiro a chegar, primeiro a servir (FCFS)
2. Programação Shortest-Job-First (SJF)
3. Tempo restante mais curto
4. Agendamento prioritário
5. Agendamento de Round Robin
6. Agendamento de fila multinível

Primeiro a chegar, primeiro a servir

O First Come First Serve é a forma completa do FCFS. É o algoritmo de escalonamento de CPU mais fácil e simples. Neste tipo de algoritmo, o processo que solicita a CPU obtém primeiro a alocação da CPU. Este método de agendamento pode ser gerenciado com uma fila FIFO.

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

Características do método FCFS

• Ele oferece algoritmo de agendamento não preemptivo e preventivo.
• Os trabalhos são sempre executados por ordem de chegada
• É fácil de implementar e usar.
• No entanto, esse método tem desempenho ruim e o tempo de espera geral é bastante alto.

Tempo restante mais curto

A forma completa do SRT é o menor tempo restante. Também é conhecido como agendamento preemptivo SJF. Neste método, o processo será alocado para a tarefa que estiver mais próxima de sua conclusão. Este método evita que um processo de estado pronto mais recente retenha a conclusão de um processo mais antigo.

Características do método de agendamento SRT

• Este método é aplicado principalmente em ambientes em lote onde é necessário dar preferência a trabalhos curtos.
• Este não é um método ideal para implementá-lo em um sistema compartilhado onde o tempo de CPU necessário é desconhecido.
• Associe a cada processo a duração de seu próximo burst de CPU. Então esse sistema operacional utiliza esses comprimentos, o que ajuda a agendar o processo com o menor tempo possível.

Agendamento baseado em prioridade

Agendamento prioritário é um método de agendamento de processos com base na prioridade. Neste método, o agendador seleciona as tarefas para trabalhar de acordo com a prioridade.

O agendamento prioritário também ajuda o sistema operacional a envolver atribuições prioritárias. Os processos com maior prioridade devem ser executados primeiro, enquanto os trabalhos com prioridades iguais são realizados numa base round-robin ou FCFS. A prioridade pode ser decidida com base nos requisitos de memória, requisitos de tempo, etc.

Agendamento Round-Robin

Round robin é o algoritmo de agendamento mais antigo e simples. O nome desse algoritmo vem do princípio round-robin, onde cada pessoa recebe uma parte igual de algo por sua vez. É usado principalmente para algoritmos de agendamento em multitarefa. Este método de algoritmo ajuda na execução de processos sem fome.

Características do agendamento Round-Robin

• Round robin é um modelo híbrido movido por relógio
• O intervalo de tempo deve ser mínimo, atribuído para que uma tarefa específica seja processada. No entanto, pode variar para diferentes processos.
• É um sistema em tempo real que responde ao evento dentro de um limite de tempo específico.

Trabalho mais curto primeiro

SJF é uma forma completa de (Shortest job first) é um algoritmo de escalonamento no qual o processo com o menor tempo de execução deve ser selecionado para execução a seguir. Este método de agendamento pode ser preemptivo ou não preemptivo. Reduz significativamente o tempo médio de espera de outros processos que aguardam execução.

Características do agendamento SJF

• Está associado a cada trabalho como uma unidade de tempo para ser concluído.
• Neste método, quando a CPU estiver disponível, o próximo processo ou job com o menor tempo de conclusão será executado primeiro.
• É implementado com política não preemptiva.
• Este método de algoritmo é útil para processamento em lote, onde a espera pela conclusão dos trabalhos não é crítica.
• Melhora a produção do trabalho, oferecendo trabalhos mais curtos, que devem ser executados primeiro, e que, em sua maioria, têm um tempo de resposta mais curto.

Agendamento de filas de vários níveis

Este algoritmo separa a fila pronta em várias filas separadas. Neste método, os processos são atribuídos a uma fila com base em uma propriedade específica do processo, como prioridade do processo, tamanho da memória, etc.

No entanto, este não é um algoritmo de agendamento independente do sistema operacional, pois precisa usar outros tipos de algoritmos para agendar os trabalhos.

Característica do agendamento de filas de múltiplos níveis

• Múltiplas filas devem ser mantidas para processos com algumas características.
• Cada fila pode ter seus algoritmos de escalonamento separados.
• As prioridades são dadas para cada fila.

O objetivo de um algoritmo de agendamento

Aqui estão as razões para usar um algoritmo de agendamento:

• A CPU usa agendamento para melhorar sua eficiência.
• Ajuda você a alocar recursos entre processos concorrentes.
• A utilização máxima da CPU pode ser obtida com multiprogramação.
• Os processos a serem executados estão na fila de prontos.

Resumo

• O agendamento da CPU é um processo para determinar qual processo possuirá a CPU para execução enquanto outro processo está em espera.
• No Agendamento Preemptivo, as tarefas são atribuídas principalmente com suas prioridades.
• No método de escalonamento não preemptivo, a CPU foi alocada para um processo específico.
• O tempo de burst é o tempo necessário para que o processo conclua a execução. Também é chamado de tempo de execução.
• A utilização da CPU é a principal tarefa na qual o sistema operacional precisa garantir que a CPU permaneça o mais ocupada possível.
• O número de processos que terminam sua execução por unidade de tempo é conhecido.
• O tempo de espera é a quantidade que um processo específico precisa esperar na fila de prontidão.
• É o tempo que a solicitação foi enviada até que a primeira resposta seja produzida.
• O tempo de resposta é a quantidade de tempo para executar um processo específico.
• A interrupção do temporizador é um método intimamente relacionado à preempção.
• Um despachante é um módulo que fornece controle da CPU ao processo.
• Seis tipos de algoritmos de agendamento de processos são: Primeiro a chegar, primeiro a servir (FCFS), 2) Agendamento Shortest-Job-First (SJF), 3) Menor tempo restante, 4) Agendamento prioritário, 5) Agendamento Round Robin, 6) Agendamento de fila multinível .
• De acordo com o relatório Método Primeiro a Chegar, Primeiro a Servir, o processo que solicita a CPU obtém primeiro a alocação da CPU.
• No Menor Tempo Restante, o processo será alocado para a tarefa mais próxima de sua conclusão.
• No Agendamento Prioritário, o agendador seleciona as tarefas para trabalhar de acordo com a prioridade.
• Agendamento round-robin funciona com base no princípio de que cada pessoa recebe uma parte igual de algo por sua vez.
• No trabalho mais curto primeiro, o tempo de execução mais curto deve ser selecionado para execução a seguir.
• O método de agendamento multinível separa a fila pronta em várias filas separadas. Neste método, os processos são atribuídos a uma fila com base em uma propriedade específica.
• A CPU usa agendamento para melhorar sua eficiência.