A longa jornada para implementar a “preempção preguiçosa” no escalonador de CPU do Linux

• O kernel Linux vem mantendo vários modos de preempção como compromisso entre vazão e tempo de resposta, e um novo conjunto de patches de Peter Zijlstra recolocou em pauta a discussão sobre a preempção preguiçosa (PREEMPT_LAZY)
• Os modos existentes PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL e PREEMPT_RT diferem no quanto permitem preempção; quanto mais frequente ela for, melhor pode ser a responsividade, mas maior também é o custo para a vazão e a contenção de locks
• PREEMPT_LAZY usa a flag TIF_NEED_RESCHED_LAZY para marcar que “é preciso reescalonar, mas não imediatamente”, adiando a maior parte das preempções até o tick do temporizador
• No longo prazo, a ideia é reduzir os modos de preempção não em tempo real para PREEMPT_LAZY e PREEMPT_FULL, além de remover a maior parte das chamadas a cond_resched() espalhadas pelo kernel
• O conjunto de patches atual ainda precisa de estabilização, revisão dos pontos de chamada e testes de desempenho; nos testes iniciais, a vazão de PREEMPT_LAZY ficou ligeiramente abaixo de PREEMPT_VOLUNTARY

---

Modos de preempção existentes no kernel Linux

• O kernel atual oferece vários modos de preempção que controlam quando uma tarefa em execução pode ser preemptada por outra
  • PREEMPT_NONE: o modo mais simples, que só permite preempção quando a tarefa em execução consome todo o seu time slice
  • PREEMPT_VOLUNTARY: modo que adiciona muitos pontos no kernel onde a preempção pode ocorrer quando necessário
  • PREEMPT_FULL: permite preempção em quase todos os pontos, exceto em trechos bloqueados pelo kernel, como quando um spinlock está sendo mantido
  • PREEMPT_RT: prioriza preempção acima de quase tudo e torna preemptável até a maior parte do código que mantém spinlocks
• Um nível maior de preempção pode permitir reações mais rápidas a eventos como o movimento do mouse ou um sinal iminente de anomalia em um reator nuclear
• Em compensação, quanto mais frequente for a preempção, menor pode ser a vazão total de tarefas longas e intensivas em CPU, além de aumentar a contenção de locks
• Muitas distribuições compilam o kernel com o pseudomodo PREEMPT_DYNAMIC
  • Na inicialização, é possível escolher um dos três modos não RT anteriores
  • O padrão é PREEMPT_VOLUNTARY
  • Em sistemas com debugfs montado, o modo atual pode ser verificado em /sys/kernel/debug/sched/preempt

Por que cond_resched() era necessário

• PREEMPT_NONE e PREEMPT_VOLUNTARY não permitem preempção arbitrária durante a execução de código do kernel
• Se um trabalho longo continuar dentro do kernel, isso pode causar latência excessiva mesmo em sistemas onde latência mínima não é a prioridade máxima
• Para evitar isso, chamadas a cond_resched() foram adicionadas em vários loops de longa duração
  • Cada chamada é um ponto extra de preempção voluntária
  • Também funciona no modo PREEMPT_NONE
  • Há centenas dessas chamadas no kernel
• Essa abordagem é uma heurística que só funciona nos pontos escolhidos pelos desenvolvedores
  • Pode haver chamadas desnecessárias
  • Pode faltar chamadas onde elas seriam necessárias
  • A lógica de decisão de escalonamento acaba espalhada por todo o código do kernel

Funcionamento central da preempção preguiçosa

• O kernel observa várias variáveis ao decidir se a tarefa atual pode ser preemptada
• Entre elas, TIF_NEED_RESCHED é uma flag que indica que uma tarefa de prioridade mais alta está esperando acesso à CPU
  • Quando uma tarefa de maior prioridade desperta, essa flag pode ser definida na tarefa atualmente em execução
  • Sem essa flag, o kernel não precisa preemptar a tarefa atual
• O kernel pode verificar TIF_NEED_RESCHED em vários pontos e preemptar a tarefa atual
  • no tick do temporizador do escalonador
  • ao retornar para o espaço do usuário após uma chamada de sistema
  • ao concluir um manipulador de interrupção
  • em chamadas a cond_resched()
• O patch de preempção preguiçosa adiciona a nova flag TIF_NEED_RESCHED_LAZY
  • Ela significa que é necessário reescalonar, mas não necessariamente executar isso de imediato
  • No modo PREEMPT_LAZY, a maior parte dos eventos define essa nova flag em vez de TIF_NEED_RESCHED
• Nos pontos em que o kernel retorna ao espaço do usuário, basta que uma das duas flags esteja definida para acionar o escalonador
• Já nos pontos de preempção voluntária e nos caminhos de retorno de interrupção, apenas TIF_NEED_RESCHED é verificada

O compromisso criado por PREEMPT_LAZY

• Em PREEMPT_LAZY, a maior parte dos eventos dentro do kernel não preempta imediatamente a tarefa atual
• Em vez disso, o manipulador do tick do temporizador verifica se TIF_NEED_RESCHED_LAZY está definida
  • Se estiver, ele também define TIF_NEED_RESCHED
  • Como resultado, a tarefa em execução pode então ser preemptada
• Em geral, a tarefa continua executando por um período próximo ao seu time slice, a menos que ceda a CPU voluntariamente
  • Espera-se que esse comportamento resulte em boa vazão
• Com essa mudança, PREEMPT_LAZY também pode rodar, como PREEMPT_FULL, com a preempção do kernel ativada quase o tempo todo
  • Sempre que o contador de preempção permitir, a preempção pode ocorrer
  • Se outras condições não bloquearem, até código de kernel de longa execução pode ser preemptado
• Quando a preempção imediata é realmente necessária, ela não é adiada
  • Por exemplo, se o resultado do tratamento de uma interrupção tornar uma tarefa em tempo real executável, TIF_NEED_RESCHED será definida
  • Nesse caso, a preempção ocorre quase imediatamente, sem esperar o tick do temporizador
• Quando apenas TIF_NEED_RESCHED_LAZY está definida, não ocorre preempção
  • Por isso, um kernel PREEMPT_LAZY tem muito menos probabilidade de preemptar a tarefa em execução do que um kernel PREEMPT_FULL

O trabalho que ainda falta até remover cond_resched()

• O objetivo de longo prazo é reduzir os modos de preempção não em tempo real a dois
  • PREEMPT_LAZY
  • PREEMPT_FULL
• PREEMPT_LAZY deve ocupar a posição entre PREEMPT_NONE e PREEMPT_VOLUNTARY, substituindo ambos
• Se a preempção passar a ser possível em quase toda parte, diminui a necessidade de adicionar pontos voluntários específicos em locais determinados
• No momento, as chamadas a cond_resched() continuam presentes
  • Elas ainda são necessárias enquanto PREEMPT_NONE e PREEMPT_VOLUNTARY existirem
  • Também ajudam a evitar problemas durante a estabilização da preempção preguiçosa
• No conjunto atual de patches, cond_resched() verifica apenas TIF_NEED_RESCHED
  • Por isso, em PREEMPT_VOLUNTARY ou PREEMPT_NONE, muitos casos que antes seriam preemptados imediatamente podem acabar adiados
• Steve Rostedt perguntou se manter o significado antigo de cond_resched(), especialmente em PREEMPT_VOLUNTARY, poderia facilitar a transição
• Thomas Gleixner considera correta a escolha de verificar apenas TIF_NEED_RESCHED
  • Porque isso força a revisão de todas as chamadas a cond_resched()
  • Chamadas que não precisam verificar o bit lazy poderão ser removidas com a adoção de PREEMPT_LAZY
  • Chamadas que precisam verificar o bit lazy deverão permanecer
• Gleixner espera que menos de 5% das chamadas a cond_resched() precisem verificar TIF_NEED_RESCHED_LAZY
• Até a transição ser concluída, será preciso revisar centenas de chamadas a cond_resched() e remover a maioria delas
• Um conjunto separado de patches de Ankur Arora trata de parte desses detalhes relacionados
• Também serão necessários testes de desempenho em larga escala
  • Nos testes iniciais de Mike Galbraith, a vazão da preempção preguiçosa ficou ligeiramente abaixo de PREEMPT_VOLUNTARY

Objetivo final

• Como resultado do trabalho com a preempção preguiçosa, o kernel pode ficar um pouco mais enxuto e simples
• A meta é ter um kernel que ofereça latências previsíveis sem espalhar chamadas relacionadas ao escalonador por todo o código
• A abordagem atual parece uma solução melhor, mas ainda levará tempo até chegar a esse ponto

[GN⁺]

Comentários do Hacker News

• Parece promissor. Como o EEVDF, segue uma direção que melhora ao mesmo tempo em que simplifica o estado atual; difícil ser melhor que isso

• Fico me perguntando por que o nível de preempção não é um atributo de eventos específicos, em vez de um modo global. Alguns eventos precisam ser tratados com latência menor do que outros

  • Para avaliar a prioridade de um evento, primeiro é preciso tempo de CPU. Essa avaliação só é possível depois de interromper o processo que está em execução na CPU atual
    Portanto, até a prioridade máxima que um evento pode ter é limitada por quão curta pode ser a fatia de tempo que um programa recebe antes de passar por uma troca de contexto. Para responder de forma confiável e com baixa latência a qualquer tipo de evento, todos os programas intensivos em CPU precisam sempre pagar esse custo de desempenho, por mais raro que esse evento seja
  • Há dois conceitos que são fáceis de confundir aqui. Um é o momento em que um processo pode ser preemptado; o outro é se ele será de fato preemptado
    Os pontos potenciais de preempção são uma propriedade do escalonador, e é disso que se fala aqui como modo global. Quanto mais pontos de preempção houver, naturalmente maior a chance de um processo ser preemptado em um momento inconveniente, mas também aumentam as oportunidades de refletir corretamente as prioridades. O nível de preempção mencionado na pergunta, isto é, a prioridade dada pelo escalonador, é de fato uma propriedade do processo e pode ser configurado. O escalonador padrão do Linux também dá fatias de tempo maiores a processos com prioridade e tenta preemptar menos outros processos
  • O PREEMPT_VOLUNTARY descrito no artigo foi, em certa medida, uma tentativa nessa direção, e agora pode ser visto como algo em processo de descontinuação
  • Este patch cumpre um pouco esse papel. Segundo https://lwn.net/ml/all/[e-mail]...:
    SCHED_IDLE, SCHED_BATCH e SCHED_NORMAL/OTHER usam preempção adiada, enquanto FIFO, RR e DEADLINE usam o comportamento Full existente
  • Um sistema assim provavelmente criaria uma disputa entre programas, cada um reivindicando prioridade por se considerar importante. Na prática, é mais provável que grandes empresas o utilizem para uma experiência de usuário “melhor”
    Por isso é importante minimizar o número de aplicativos em execução, ou controlar manualmente aqueles breves momentos que a maioria dos usuários vivencia. Às vezes, trabalhos intensivos em CPU têm mais chance de ser código ruim do que uso realmente eficiente de recursos. Em jogos, o desempenho deve ter prioridade, mas é preciso um equilíbrio delicado para não paralisar o sistema em nome da multitarefa. De qualquer forma, isso é principalmente voltado a tarefas ociosas, então não parece haver grande necessidade de automatizar além de oferecer ao usuário um comando simples para alternar várias ações em scripts

• O texto diz que “o kernel atual tem quatro modos que controlam quando uma tarefa pode ser preemptada em favor de outra”. Fico curioso se isso se refere a tarefas do kernel ou se inclui também tarefas de usuário

  • É sobre código do kernel. Código em espaço de usuário é sempre preemptível

• Não encontrei números na thread vinculada em que o patch foi enviado. Imagino que já devesse haver ao menos alguns benchmarks iniciais mostrando o potencial prático dessa mudança

  • Está no penúltimo parágrafo do artigo
    Ele diz que serão necessários testes de desempenho abrangentes, que Mike Galbraith iniciou o trabalho preliminar e que os resultados mostraram que a vazão da preempção adiada é ligeiramente menor que a do PREEMPT_VOLUNTARY
  • Fico me perguntando como algo assim deveria ser benchmarkado. Seria rodar vários processos ao mesmo tempo e ordenar pelo tempo total de execução, ou medir a latência de cada processo individualmente?

• Fico curioso sobre o quanto o escalonador é fortemente acoplado ao restante do código do kernel
  Por exemplo, se eu quisesse simplificar bastante o escalonador para uma aplicação de computação científica que não se importa nada com preempção, isso seria possível de forma limpa e modular? Haveria algum benefício real?

  • Se você quiser executar um conjunto de processos reduzindo a preempção tanto quanto possível, por exemplo em um ambiente de HPC, a abordagem mais forte é configurar alguns núcleos como CPUs isoladas, reiniciar e então colocar as tarefas diretamente neles com taskset
    Mas aí é preciso realmente atribuir as tarefas às CPUs manualmente, e também fica fácil acabar com todas as tarefas indo parar nas CPUs erradas. A abordagem padrão é configurar máscaras de interrupção para que interrupções não sejam enviadas às CPUs de “trabalho”, e usar cpuset para que apenas determinados cgroups sejam executados no cpuset especificado
  • Em um sistema limpo, quase sem daemons, se você ajustar a aplicação para ter uma thread do sistema operacional por thread de CPU e aplicar fixação de CPU para impedir migração, dá para chegar a uns 95%
    Como a fila de execução fica muito curta, o impacto do que quer que o escalonador faça deve ser bem pequeno. Se a aplicação não fizer muito I/O, também não haverá muitas interrupções. Se for possível usar um kernel tickless — não sei se hoje isso ainda é uma opção separada ou o padrão —, talvez quase não haja interrupções por longos períodos
  • Da última vez que olhei, ele era surpreendentemente bem separado
    Porém, o motivo para simplificar drasticamente seria evitar bugs, não obter muito desempenho em comparação com um escalonador padrão bem configurado. Há muitas configurações, mas também não havia muitos bugs nessa área. Se você simplificar de forma ingênua, na maioria das vezes vai perder desempenho em vez de ganhar. Se estiver rodando um sistema não interativo, a mudança mais simples é aumentar a quota de tempo dos processos
  • Eu simplesmente usaria RT Linux. Ele tem seu próprio escalonador padrão, enquanto o escalonador do kernel roda como tarefa ociosa, e as tarefas de tempo real têm prioridade sobre todo o resto