O multikernel: uma nova arquitetura de SO para sistemas multicore escaláveis

Título original: The Multikernel: A New OS Architecture for Scalable Multicore Systems

PublicadoProceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles

Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.

Resumo

Sistemas de computação comuns têm cada vez mais núcleos de processador e exibem compromissos arquiteturais cada vez mais diversos, incluindo hierarquias de memória, interconexões, conjuntos de instruções e suas variantes, e configurações de E/S. Sistemas anteriores de computação de alto desempenho escalaram em casos específicos, mas a natureza dinâmica das cargas de trabalho modernas de clientes e servidores, somada à impossibilidade de otimizar estaticamente um SO para todas as cargas e variantes de hardware, impõe desafios sérios às estruturas de sistemas operacionais. Os autores defendem que o desafio do hardware multicore do futuro é melhor enfrentado ao assumir a natureza de rede da máquina, repensando a arquitetura do SO com ideias de sistemas distribuídos. Eles investigam uma nova estrutura de SO, o multikernel, que trata a máquina como uma rede de núcleos independentes, não assume compartilhamento entre núcleos no nível mais baixo e move a funcionalidade tradicional do SO para um sistema distribuído de processos que se comunicam por troca de mensagens. Implementaram um SO multikernel para mostrar que a abordagem é promissora e descrevem como problemas tradicionais de escalabilidade em sistemas operacionais (como a gerência de memória) podem ser reformulados com mensagens e aproveitar ideias de sistemas distribuídos e de redes. A avaliação do protótipo em sistemas multicore mostra que, mesmo em máquinas atuais, o desempenho de um multikernel é comparável ao de um SO convencional e pode escalar melhor para dar suporte ao hardware futuro.

Tradução nossa do resumo original dos autores, em inglês.

Análise de pesquisa

Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.

Última revisão
Versão
1.0

Visão geral

Este artigo do SOSP 2009, da ETH Zurique e da Microsoft Research Cambridge, está num ponto de virada: o número de núcleos crescia e o hardware se diversificava (caches, interconexões e até conjuntos de instruções diferentes), enquanto os kernels continuavam sendo programas de memória compartilhada com estruturas de dados protegidas por locks. A tese dos autores é que o problema é a própria estrutura, não um lock específico. A resposta é tratar a máquina como uma pequena rede e construir o SO como se constrói um sistema distribuído.

O artigo é a contrapartida arquitetural de um estudo de medição como An Analysis of Linux Scalability to Many Cores, que perguntou, um ano depois, até onde um Linux corrigido chega. Ele toma emprestado do exokernel (o driver de CPU abstrai muito pouco) e do seL4 (o sistema de capabilities do Barrelfish é modelado nele). Dois autores, Barham e Harris, também escreveram o Xen. A ponte com sistemas distribuídos é explícita: estado replicado mantido consistente por protocolos de acordo, no espírito da abordagem de máquina de estados (o próprio artigo não a cita), e mensagens em pipeline e em lote. A seção de trabalhos futuros observa que um SO estruturado como sistema distribuído se parece com modelos de programação populares em datacenters, como o MapReduce.

Vale conhecer antes: coerência de cache (um núcleo que escreve numa linha força a invalidação das outras cópias), TLB shootdown (quando um mapeamento muda, todo núcleo que pode tê-lo em cache precisa descartá-lo) e commit em duas fases.

Contribuição

  • O modelo multikernel. O SO é um sistema distribuído de núcleos que se comunicam por mensagens e não compartilham memória (exceto a usada pelos canais de mensagens). Três princípios: tornar explícita toda a comunicação entre núcleos, tornar a estrutura do SO neutra em relação ao hardware e ver o estado como replicado em vez de compartilhado. Só o transporte de mensagens e a interface com o hardware (CPUs e dispositivos) dependem da máquina.
  • Barrelfish. Cada núcleo roda um driver de CPU em modo privilegiado, orientado a eventos, de thread única e não preemptível, mais um processo monitor em modo usuário. Os monitores fazem toda a coordenação entre núcleos e mantêm as estruturas replicadas (tabelas de alocação de memória, mapeamentos de espaço de endereços) consistentes com protocolos de acordo. O driver de CPU x86-64 tem 7135 linhas de C e 337 de assembly. Um processo é um conjunto de objetos dispatcher, um por núcleo.
  • URPC. Entre núcleos, uma região de memória compartilhada serve de canal para mensagens do tamanho de uma linha de cache, de um único escritor para um único leitor. O remetente escreve em sequência e o receptor faz polling na última palavra, então nunca vê uma mensagem parcial. Os dispatchers fazem polling por pouco tempo e depois bloqueiam.
  • Base de conhecimento do sistema (SKB). Um subconjunto de lógica de primeira ordem, alimentado por descoberta de hardware (ACPI, PCI, CPUID), medições online (latência e largura de banda do URPC entre todos os pares de núcleos) e fatos pré-declarados. As consultas decidem, por exemplo, a alocação de drivers, os transportes de mensagens e as árvores de multicast. A primeira implementação é uma adaptação do sistema de restrições ECLiPSe.
  • Capabilities para memória. Seguindo o seL4, toda a gerência de memória passa por operações sobre capabilities (retype, revoke), com a memória virtual tratada em código de usuário.

Metodologia

A motivação é medida primeiro. A Figura 3 compara duas formas de atualizar estado compartilhado no sistema AMD 4×4 núcleos: threads que atualizam diretamente 1, 2, 4 ou 8 linhas de cache compartilhadas (SHM1 a SHM8, sem locks) contra um cliente que envia uma RPC leve, assumida como cabendo em uma linha de 64 bytes, a um servidor que faz a atualização (MSG1, MSG8).

A avaliação usa quatro máquinas: Intel 2×4 núcleos (Xeon X5355, 2,66 GHz), AMD 2×2 (Opteron 2220, 2,8 GHz), AMD 4×4 (Opteron 8380, 2,5 GHz) e AMD 8×4 (Opteron 8350, 2 GHz, com a interconexão da Figura 2). Os objetivos são declarados de antemão: desempenho comparável ao dos sistemas existentes, escalabilidade, readaptação a outro hardware, uso de pipelining e batching e posicionamento pela topologia. Os testes: um estudo de caso de TLB shootdown com quatro protocolos sobre URPC (Broadcast, Unicast, Multicast e Multicast consciente de NUMA) e um unmap completo contra Linux 2.6.26 (mprotect) e Windows Server 2008 R2 Beta (VirtualProtect); commit em duas fases para o retype de capabilities; NAS OpenMP e SPLASH-2 na máquina AMD 4×4 contra o Linux; e cargas de E/S (loopback IP, eco UDP, servidor web com banco de dados) contra o Linux com lighttpd 1.4.23.

Resultados

Todos os números abaixo são do próprio artigo.

  • Motivação (Figura 3). Um núcleo atualiza em menos de 30 ciclos, mas com 16 núcleos modificando os mesmos dados cada atualização custa quase 12.000 ciclos a mais, todos gastos parado em faltas de cache. Para atualizações de quatro ou mais linhas de cache, a latência da RPC é menor que a da memória compartilhada (SHM4 contra MSG8), e o servidor único faz o dobro de atualizações por segundo de todas as 16 threads de memória compartilhada juntas.
  • Custo das mensagens. A primitiva local, no mesmo núcleo, leva 845, 757, 1463 e 1549 ciclos nos quatro sistemas (Tabela 1). A latência do URPC vai de 180 ciclos (cache compartilhado, Intel 2×4, 11,97 mensagens por quilociclo) a 618 ciclos (dois saltos, AMD 8×4) (Tabela 2). No AMD 2×2, o URPC leva 450 ciclos contra 424 de um IPC do L4, com 3,42 contra 2,36 mensagens por quilociclo e menos linhas de cache usadas (9 de instruções e 8 de dados contra 25 e 13) (Tabela 3).
  • TLB shootdown. O Broadcast escala linearmente com o número de núcleos por causa do protocolo de coerência da AMD; o Unicast é melhor, mas ainda linear; o Multicast de dois níveis, e sobretudo o consciente de NUMA, escalam bem melhor. O SKB monta a árvore em tempo de execução. O unmap completo no Barrelfish supera rapidamente Linux e Windows conforme crescem os núcleos, mesmo com até 32 processos de usuário envolvidos, enquanto os outros dois pagam o custo de enviar IPIs em série. Os autores atribuem o grande custo extra sobre o protocolo-base principalmente ao laço de despacho, não otimizado, da biblioteca de threads.
  • Retype de capabilities. O commit em duas fases com a mesma técnica de multicast escala bem e, com pipelining, um retype consome menos ciclos que os shootdowns por IPI no Windows e no Linux.
  • Carga de CPU. No AMD 4×4, cinco aplicações (NAS CG, FT, IS; SPLASH-2 Barnes-Hut e radiosity) escalam mal nos dois sistemas, o que os autores tomam como prova de que a estrutura distribuída sustenta código paralelo de espaço de endereços compartilhado com pouca perda de desempenho.
  • E/S. Loopback IP no AMD 2×2: 2154 Mbit/s contra 1823 do Linux, 21 contra 77 faltas de cache de dados por pacote (Tabela 4). Eco UDP: 951,7 contra 951 Mbit/s. Página web estática: 18697 requisições por segundo (640 Mbit/s) contra 8924 (316 Mbit/s) do lighttpd. Com o SQLite atrás do URPC: 3417 requisições por segundo, limitadas pelo núcleo do banco.

Análise crítica

O artigo é cuidadoso com seus limites. Ele diz que "seria errado tirar conclusões quantitativas" dos benchmarks de grande escala, porque Linux e Windows são maduros e o Barrelfish é novo e mais leve, e os lê apenas como indício de desempenho razoável. Afirmações mais fortes ficam só para os microbenchmarks. Também declara que não trata cargas de aplicação complexas nem serviços de nível mais alto como armazenamento, não avalia a escalabilidade além do hardware comum da época e não avalia núcleos heterogêneos (as máquinas são Intel e AMD homogêneas; o port para ARM estava em andamento). Os autores admitem que o sistema de capabilities foi, em retrospecto, "desnecessariamente complexo" e não mais eficiente que gerenciadores de memória escaláveis por processador, e que separar driver de CPU e monitor não é ótimo para desempenho (vários milhares de ciclos por chamada ao SO). A máquina inteira é uma unidade de falha, então a tolerância a falhas fica de fora.

O que o artigo não afirma: que um kernel de memória compartilhada não consegue escalar (ele diz que os SOs atuais têm soluções pontuais), que mensagens vencem memória compartilhada em geral, nem que os resultados valem para hardware sem coerência. Ele também não mostra ganhos de ponta a ponta em misturas reais de aplicações.

Os pontos abaixo são uma leitura da evidência, não afirmações do artigo.

  • As bases de comparação são sistemas de 2008. Linux 2.6.26 e um Windows Server 2008 R2 Beta, com o custo do unmap não otimizado, dizem pouco sobre kernels posteriores.
  • O destaque é em parte o protocolo. O ganho no unmap vem de uma árvore de multicast consciente da topologia, que em princípio também poderia ser construída num kernel de memória compartilhada. O artigo argumenta que a abstração de mensagens torna isso mais fácil, não que seja a única via.

Literatura posterior, que não faz parte deste artigo: o estudo do MIT An Analysis of Linux Scalability to Many Cores (OSDI 2010) concluiu, para sete aplicações que exigem muito do kernel em 48 núcleos, que mudanças modestas no kernel bastaram, então ainda não havia razão de escalabilidade para abandonar organizações tradicionais. O Corey (Boyd-Wickizer et al., OSDI 2008), que o artigo do multikernel discute, deixa as aplicações controlarem o compartilhamento. Para hardware heterogêneo, veja Barbalace et al., "Popcorn: bridging the programmability gap in heterogeneous-ISA platforms" (EuroSys 2015, doi) e Asmussen et al., "M3: A Hardware/Operating-System Co-Design to Tame Heterogeneous Manycores" (ASPLOS 2016, doi). Só conferi os títulos e as conferências desses dois, não suas afirmações. Um contraponto de escalonamento num kernel Linux compartilhado é The Linux Scheduler: A Decade of Wasted Cores.

Pesquisas futuras

  • Compartilhamento limitado por trás das interfaces de réplicas: os autores apontam como questão aberta decidir quando compartilhar e automatizar essa decisão.
  • Transportes URPC de multicast, incast e anycast, e escalonamento baseado no tamanho das filas, já que efeitos de filas causaram anomalias de desempenho.
  • Um sistema de arquivos replicado e escalável dentro da máquina, e uma pilha de rede projetada para multikernels.
  • Estender o multikernel além de uma máquina para tratar falhas parciais.
  • Se os resultados valem em hardware sem coerência ou realmente heterogêneo, o que o artigo não mediu.

Texto completo

Carregando o paper…

Discussão · 0

Nenhum post ainda. Seja o primeiro a iniciar a discussão.