Escalonamento linux

Prévia do material em texto

Sistemas Operacionais
Lavras, 2020
Erasmo Evangelista de Oliveira
erasmo.oliveira@fagammon.edu.br
Escalonamento de Processos no Linux - Parte II
Agenda
Kernel do Linux e Preempção
Revisão sobre Escalonamento de Processos
Escalonamento de Processos no Linux
Escalonador de Processos do Linux
Algoritmo CFS - Completely Fair Scheduler
Kernel do Linux e Preempção
Kernel do Linux - Preempção
Preempção: capacidade do escalonador interromper temporariamente um processo em favor de outro processo, por meio de uma política de escalonamento que utilizará critérios, como por exemplo, o quantum ou prioridade . 
Esta alternância entre os processos também é conhecida como troca de contexto (switch context) .
Um kernel preemptivo tem a capacidade de alternar o contexto. Isso significa que ele pode interromper um processo, mesmo que não esteja concluído, e dar tempo de processamento ao próximo processo conforme o esperado. O processo interrompido continuará a ser executado quando for novamente escalonado.
Kernel do Linux - Preempção
Por exemplo, suponha que dois processos P1 (prioridade alta) e P2 (prioridade baixa) que necessitem fazer chamadas de sistema e executar em modo kernel:
 P2 está em execução e P1 entra na fila de prontos, logo precisa ser escalonado para entrar em execução.
Se a preempção do kernel estiver disponível, o P2 pode ser “preemptado” (interrompido temporariamente) ou “dormir” e o P1 pode executar.
Senão (preempção do kernel não disponível), como P2 está em modo kernel, o sistema espera até que o P2 seja finalizado, para que em seguida, P1 possa ser executado.
Kernel do Linux - Não Preemptivos
Kernels do Linux anteriores a versão 2.6 :
 Um processo rodando no modo kernel não poderia ser interrompido, mesmo que um processo de maior prioridade necessitasse ser executado.
 Um processo em execução no modo kernel não deixa o processador até que ele termine ou necessite de alguma operação de entrada/saída.
 Um loop infinito pode bloquear o sistema.
 Apenas os processos em modo usuário são preemptivos: preempção por quantum ou caso processos de prioridade mais alta necessitassem entrar em execução.
 Essa ausência de preempção no kernel causou vários problemas com relação à latência e escalabilidade.
Kernel do Linux - Preemptivos
A partir da versão 2.6 do kernel Linux:
 A preempção do kernel foi introduzida nos kernels 2.6.x e é possível habilitá-la ou desabilitá-la usando a opção CONFIG_PREEMPT.
 Se CONFIG_PREEMPT estiver ativado, o código do kernel poderá ser preemptado (interrompido temporariamente) em qualquer lugar, exceto quando o código tiver desativado as interrupções locais. Assim:
 Um loop infinito no código não pode mais bloquear todo o sistema.
 Uma tarefa que execute em modo kernel pode ser interrompida, porém nem todas as seções do código do kernel podem ser preemptadas (seção crítica).
 Se CONFIG_PREEMPT estiver desativado, o comportamento do kernel passa ser o mesmo das versõens anteriores ao 2.6, ou seja não preemptivo.
Escalonamento de Processos
(Revisão)
Revisão: Escalonamento de Processos
S.O modernos tentam extrair o desempenho ideal do hardware: 
 Virtualizando a CPU e a memória.
 A virtualização da CPU é alcançada “compartilhando” a CPU entre vários processos (cada processo recebe uma pequena fração da CPU em intervalos regulares). 
O algoritmo usado para selecionar uma tarefa dentre das várias tarefas executáveis disponíveis é chamado escalonador.
O processo de seleção da próxima tarefa é chamado escalonamento.
A implementação de um algoritmo de escalonamento é difícil.
Revisão: Escalonamento de Processos
S.O modernos tentam extrair o desempenho ideal do hardware:
Virtualizando a CPU e a memória.
A virtualização da CPU é alcançada “compartilhando” a CPU entre vários processos (cada processo recebe uma pequena fração da CPU em intervalos regulares). 
O algoritmo usado para selecionar uma tarefa dentre das várias tarefas executáveis disponíveis é chamado escalonador.
O processo de seleção da próxima tarefa é chamado escalonamento.
A implementação de um algoritmo de escalonamento é difícil.
Revisão: Escalonamento de Processos
Escalonador Atuando na Fila de Processos
Requisitos de um Bom Algoritmo de Escalonamento 
Um algoritmo aceitável precisa alocar o tempo da CPU para que tarefas de alta prioridade (aplicativos interativos ) tenham preferência sobre tarefas de baixa prioridade (processos não interativos)
Deve proteger contra a inanição (Starvation) os processos de baixa prioridade
Processos de baixa prioridade devem ter a oportunidade de serem executados, independentemente de quantos processos de alta prioridade estão disputando a CPU. 
Os processos devem parecer estar executando simultaneamente sem causar um impacto muito grande na taxa de transferência do sistema.
Escalonador de Processos Ideal
Para processos interativos como GUIs, o escalonador ideal daria a cada processo uma quantidade muito pequena de tempo na CPU e alternaria rapidamente entre processos. 
Como os usuários esperam que os processos interativos respondam à entrada imediatamente, o atraso entre a entrada do usuário e a execução do processo deve ser idealmente imperceptível para os seres humanos - algo entre 50 e 150ms, no máximo.
Para processos não interativos, a situação é revertida. A alternância entre processos ou troca de contexto é uma operação relativamente cara. 
Fatias de tempo maiores no processador e menos alternâncias de contexto podem melhorar o desempenho e a taxa de transferência do sistema. 
Um escalonador deve controlar qual processo será executado e por quanto tempo será executado.
Deve encontrar um equilíbrio entre todas essas necessidades concorrentes.
 Precisa resolver 2 requisitos contraditórios: a capacidade de resposta à E/S (responsividade) e a taxa de transferência (throughput).
Escalonador de Processos do Linux
(Scheduler)
Escalonamento no Linux
O escalonamento é baseado em classes de escalonamento. Cada classe recebe uma prioridade específica. 
Ao usar diferentes classes de escalonamento, o kernel pode acomodar diferentes algoritmos de escalonamento com base nas necessidades do sistema e de seus processos.
Os critérios de escalonamento para um servidor podem ser diferentes daqueles de um dispositivo móvel .
Para decidir qual tarefa executar, o escalonador seleciona a tarefa de maior prioridade pertencente à classe de escalonamento de maior prioridade.
Classes de Escalonamento no Linux 
Atualmente kernel Linux padrão ( a partir da versão 2.6) implementa duas classes de escalonamento:
uma classe de escalonamento padrão usando o algoritmo de escalonamento CFS - Completely Fair Scheduler
uma classe de escalonamento em tempo real.
novas classes de escalonamento podem ser adicionadas.
Escalonamento no Linux - Prioridade
Em versões do kernel anteriores a 2.6 tínhamos a atribuição de quantum em função da prioridade como na figura.
Em versões do kernel a partir do 2.6.23 , em vez de usar regras estritas que associam um valor de prioridade relativo à duração de um quantum de tempo, o escalonador CFS atribui uma proporção do tempo de processamento da CPU a cada tarefa.
Essa proporção é calculada com base no valor de nice atribuído a cada tarefa.
Escalonamento no Linux - Nice
Os valores do nice variam de -20 a +19, onde um valor nice numericamente mais baixo indica uma prioridade relativa mais alta.
Tarefas com valores nice mais baixos recebem uma proporção maior de tempo de processamento da CPU do que tarefas com valores nice mais altos.
O valor padrão do nice é 0.
O termo nice vem da idéia de que, se uma tarefa aumenta seu valor de nice, por exemplo, 0 para +10, ela está sendo “gentil” com as outras tarefas no sistema, diminuindo sua prioridade relativa. Em outras palavras, “bons processos” terminam por último!
Algoritmo CFS - Completely Fair Scheduler
Completely Fair Scheduler (CFS)
O CFS não usa valores discretos de fatias de tempo e em vez disso identifica uma latênciaalvo (targeted latency) , que é um intervalo de tempo durante o qual cada tarefa executável deve ser executado pelo menos uma vez.
Proporções de tempo de CPU são alocadas a partir do valor da latência alvo. Além de ter valores padrão e mínimos, a latência direcionada pode aumentar se o número de tarefas ativas no sistema crescer além de um determinado limite.
Completely Fair Scheduler (CFS)
Segundo Ingo Molnar, autor do CFS: “ O CFS modela uma CPU ideal, multitarefa e precisa, em hardware real".
 CPU que pode executar vários processos ao mesmo tempo (em paralelo), dando a cada processo uma parcela igual da poder de processamento do processador. 
Se um único processo estiver em execução, ele receberá 100% do poder da CPU. Com dois processos, cada um teria exatamente 50% da poder da CPU (em paralelo). Com quatro processos em execução, cada um deles teria 25% do poder da CPU e assim por diante. Portanto, essa CPU seria "justa" para todas as tarefas em execução no sistema.
Completely Fair Scheduler (CFS)
Essa CPU ideal é inexistente, mas o CFS tenta emular esse processador em software. 
Em um processador real, apenas uma tarefa pode ser alocada para uma CPU em um determinado momento.
Portanto, todas as outras tarefas aguardam durante esse período. Logo, enquanto a tarefa atualmente em execução obtém 100% do poder da CPU, todas as outras tarefas obtêm 0% do poder da CPU. 
Obviamente, isso não é justo
Completely Fair Scheduler (CFS)
 Essa CPU ideal é inexistente, mas o CFS tenta emular esse processador em software. 
 Em um processador real, apenas uma tarefa pode ser alocada para uma CPU em um determinado momento.
 Portanto, todas as outras tarefas aguardam durante esse período. Logo, enquanto a tarefa atualmente em execução obtém 100% do poder da CPU, todas as outras tarefas obtêm 0% da energia da CPU. 
 Obviamente, isso não é justo.
Completely Fair Scheduler (CFS)
 A partir da versão 2.6.23 do kernel , por padrão, é utilizado o algoritmo de de escalonamento Completely Fair Scheduler (CFS).
Tenta eliminar essa injustiça do sistema.
 Tenta encontrar a parcela justa da CPU que estaria disponível para cada processo no sistema.
 Executa um clock justo de acordo com uma fração da velocidade real do clock da CPU.
 A taxa de aumento do clock justo é calculada dividindo o tempo total de processamento (em ns) pelo número total de processos em espera.
 O valor resultante é a quantidade de tempo da CPU à qual cada processo tem direito.
 Enquanto um processo aguarda a CPU, o escalonador tenta encontrar a quantidade de tempo que teria sido usado no processador ideal.
Completely Fair Scheduler (CFS)
 Esse tempo de espera (variável wait_runtime) é usado para “rankear” processos para escalonamento e determinar a quantidade de tempo que o processo pode executar antes de ser premptado.
 O processo com o maior tempo de espera (ou seja, com a maior necessidade de CPU) é escolhido pelo escalonador e atribuído à CPU.
 Quando esse processo está em execução, o tempo de espera diminui, enquanto o tempo de outras tarefas em espera aumenta (como estavam aguardando).
 Isso significa que após algum tempo, haverá outra tarefa com o maior tempo de espera (necessidade mais urgente da CPU) e a tarefa em execução no momento será preemptada.
 Usando esse princípio, o CFS tenta ser justo com todas as tarefas e sempre tenta ter um sistema com tempo de espera zero para cada processo - cada processo tem uma parcela igual da CPU (algo que uma “CPU ideal, precisa e multitarefa” teria feito )
Escalonador do Linux 
O escalonador precisa lidar com tarefas que não possuem requisitos de tempo real (tarefas cujos tempos de respostas sejam garantidos ou sejam concluída dentro de um determinado período de tempo rígido) e tarefas que possuem requisitos de tempo real .
Para as tarefas que não são de tempo real é usada a política de escalonamento SCHED_NORMAL (também chamada SCHED_OTHER em kernels mais antigos), utilizada para as tarefas normais do usuário.
Para as tarefas que possuem requisitos de tempo real. O kernel padrão do Linux fornece duas políticas de escalonamento, SCHED_FIFO e SCHED_RR. 
Escalonador do Linux - SCHED_FIFO
SCHED_FIFO: principal política em tempo real.
Ele implementa um algoritmo de fila ( primeiro a entrar, primeiro a sair).
 Quando uma tarefa SCHED_FIFO começa a ser executada, ela continua sendo executada até que voluntariamente ceda o controle do processador, bloqueie ou seja impedida por uma tarefa em tempo real de prioridade mais alta.
 Não possui time slices ou fatias de tempo (quantum).
 Todas as outras tarefas de menor prioridade não serão escalonadas até que a CPU seja deixada.
Duas tarefas SCHED_FIFO de prioridade igual não são preemptadas entre si. 
Escalonador do Linux - SCHED_RR
SCHED_RR : algoritmo preemptivo Round Robin
Para as tarefas com requisitos de tempo real são atribuídas time slices (fatias de tempo) com base em sua prioridade e as mesmas são executadas até que esgotam sua fatia de tempo.
Uma tarefa deixa a CPU se houver outra tarefa RT na fila de execução.
Se pelo menos uma tarefa RT estiver em execução, nenhuma outra tarefa SCHED_OTHER poderá executar em qualquer CPU.
Cada tarefa RT tem um campo de prioridade.
 A CPU pode ser distribuída entre as tarefas SCHED_RR.
A prioridade classe SCHED_RR funciona exatamente como o campo de prioridade normal da classe SCHED_NORMAL (padrão).
Tipos de Processos
Gerência de processos
A gerência de processos do UNIX separa a criação e a execução de um novo programa em duas operações distintas.
A chamada do sistema fork cria um novo processo
Um novo programa é executado após uma chamada a execve
No UNIX, um processo abrange toda a informação que o sistema operacional deve manter para acompanhar o contexto de uma única execução de um único programa
No Linux, as propriedades do processo estão em três grupos: identidade, ambiente e contexto do processo
Identidade do processo
ID de processo (PID). O identificador exclusivo do processo; usado para especificar processos ao sistema operacional quando uma aplicação faz uma chamada do sistema para sinalizar, modificar ou esperar por outro processo.
Credenciais. Cada processo precisa ter um ID de usuário associado e um ou mais IDs de grupo que determinam os direitos de um processo para acessar recursos e arquivos do sistema
Personalidade. Não encontrada tradicionalmente nos sistemas UNIX, mas, sob o Linux, cada processo possui um identificador de personalidade associado, que pode modificar a semântica de certas chamadas de sistema
Usada principalmente por bibliotecas de simulação para requisitar que as chamadas de sistema sejam compatíveis com certas variantes do UNIX
Ambiente do processo
O ambiente de um processo é herdado do seu pai e é composto de dois vetores terminados em nulo:
O vetor de argumento lista os argumentos da linha de comandos usados para invocar o programa em execução, e por convenção começa com o nome do próprio programa
O vetor de ambiente é uma lista de pares “NOME=VALOR”, que associa variáveis de ambiente nomeadas a valores de texto quaisquer
A passagem de variáveis de ambiente de um processo para o seguinte, e a herança dessas variáveis pelos filhos de um processo, são meios flexíveis de passar informações aos componentes do software de sistema no modo usuário 
O mecanismo de variável de ambiente oferece uma personalização do sistema operacional que pode ser definida para cada processo, ao invés de configurada para o sistema como um todo
Contexto de processo
O estado (alterando constantemente) de um programa em execução a qualquer momento
O contexto de escalonamento é a parte mais importante do contexto de processo; as informações que o escalonador precisa para suspender e reiniciar o processo
O kernel mantém informações sobre os recursos consumidos em cada processo, e os recursos totais consumidos pelo processo em seu tempo de vida inteiro até o momento 
A tabela de arquivos é um array de ponteiros para estruturas de arquivodo kernel
Ao fazer chamadas de sistema de E/S de arquivo, os processos se referem aos arquivos por seu índice para essa tabela
Contexto de processo (cont.)
Enquanto a tabela de arquivos lista os arquivos abertos existentes, o contexto do sistema de arquivos se aplica a requisições para abrir novos arquivos
A raiz atual e os diretórios default a serem usados para novas buscas de arquivos são armazenados aqui 
A tabela do tratador de sinais define a rotina no espaço de endereços do processo a ser chamada quando chegam sinais específicos 
O contexto da memória virtual de um processo descreve o conteúdo completo do seu espaço de endereços privado
Processos e threads
O Linux usa a mesma representação interna para processos e threads; uma thread é simplesmente um novo processo que compartilha o mesmo espaço de endereços de seu pai
Só é feita uma distinção quando uma nova thread é criada pela chamada do sistema clone
fork cria um novo processo com seu próprio contexto de processo inteiramente novo
clone cria um novo processo com sua própria identidade, mas com permissão para compartilhar as estruturas de dados de seu pai
O uso de clone dá a uma aplicação controle detalhado sobre exatamente o que é compartilhado entre duas threads
SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais.  8ª Ed. Rio de Janeiro: LTC, 2010. 
TANENBAUM, Andrew S. Sistemas Operacionais Modernos. 3ª ed. Curitiba: Pearson. 2009. 
‹#›
Referências
Link da aula de 30/03/2020: https://bit.ly/2wR8qEh
‹#›
Gravação da Aula
Agenda
Kernel do Linux e Preempção
Escalonador de Processos do Linux
Tipos de processo no Linux
Prioridades de execução dos processos
Principais comandos de gerenciamento de processo no Linux
Envio de sinais no Linux