CS Fundamentals Trainer · Guias
Sistemas operacionais: processos, threads, memória virtual e escalonamento
Processos versus threads, trocas de contexto, escalonamento round-robin, memória virtual, page faults, copy-on-write, substituição de páginas e thrashing, com medições no Linux e duas animações passo a passo.
28 min de leitura
Todo programa que você escreve roda sobre um sistema operacional, e muitos comportamentos intrigantes (um processo que está "usando 8 GB" quando a máquina tem 4, um servidor que fica mais lento quando você adiciona threads, uma pausa de alguns milissegundos que nenhum código explica) são o sistema operacional fazendo o seu trabalho. O kernel tem três trabalhos principais: decide quem roda na CPU (escalonamento), dá a cada programa a ilusão de ter a sua própria memória privada (memória virtual) e intermedeia o acesso ao hardware (arquivos, rede, dispositivos) por meio de chamadas de sistema. Este guia cobre os dois primeiros em profundidade, além do vocabulário que um entrevistador espera: processo, thread, troca de contexto, page fault.
Executei pequenos experimentos no Linux para os números abaixo; o código está no apêndice. A máquina era uma pequena máquina virtual com dois núcleos, então trate as proporções como a lição e os tempos absolutos como exemplos.
1. Processos e threads
Um processo é um programa em execução junto com seus recursos: seu próprio espaço de endereços virtual, arquivos abertos e pelo menos uma thread. Uma thread é um caminho de execução dentro de um processo: tem a sua própria pilha e registradores, mas compartilha o espaço de endereços (e portanto o heap e as variáveis globais) com as outras threads do mesmo processo.
| Processo | Thread | |
|---|---|---|
| Espaço de endereços | o seu próprio; isolado dos outros processos, a menos que a memória seja compartilhada de propósito (memória compartilhada, mmap de um arquivo compartilhado) | compartilhado com as outras threads do processo |
| Custo de criação | alto (novo espaço de endereços, tabelas de páginas) | menor (uma pilha e alguma contabilidade) |
| Comunicação | precisa de IPC: pipes, sockets, memória compartilhada | lêem e escrevem a mesma memória (e precisam de locks) |
| Uma falha | em geral encerra só aquele processo, mas veja os limites abaixo | pode derrubar o processo inteiro |
| Bom para | isolamento, segurança, uso de várias máquinas | paralelismo e concorrência dentro de um programa |
No experimento, criar e juntar (join) uma thread levou cerca de 48 microssegundos, enquanto fazer o fork de um processo levou cerca de 3,2 milissegundos (o processo que fez o fork tinha um heap de 128 MB, então havia tabelas de páginas para copiar: o custo depende do tamanho do processo). As threads são mais baratas, mas o preço é a memória compartilhada, de onde vêm as condições de corrida e os deadlocks do guia de concorrência. No experimento, uma thread que somou 1 a uma variável mudou o valor do pai; um processo filho que somou 100 não mudou, porque depois do fork tinha a sua própria cópia.
Até onde vai o isolamento de processos
Espaços de endereços separados impedem que um processo leia ou sobrescreva por acidente a memória de outro. Essa é uma promessa mais estreita que "processos não conseguem afetar uns aos outros". Várias coisas são compartilhadas, ou alcançáveis, entre processos:
- Recursos que o kernel compartilha. Arquivos, diretórios, sockets, a CPU, o disco, o page cache, a rede e a memória da máquina são compartilhados. Um processo que enche o disco, abre todos os descritores de arquivo que o usuário tem permissão de abrir ou consome toda a memória prejudica seus vizinhos, que é a razão de existirem limites de recursos, cotas e cgroups.
- Memória compartilhada de propósito. Processos que usam memória compartilhada ou um
mmapcompartilhado veem as escritas uns dos outros. Uma queda no meio de uma atualização pode deixar os dados compartilhados escritos pela metade, e um lock mantido por um processo que morreu continua mantido, a menos que o lock tenha sido projetado para ser robusto (recuperável pelo próximo dono). - Permissões. Processos do mesmo usuário em geral podem enviar sinais uns aos outros e, dependendo das configurações do sistema, inspecionar e controlar uns aos outros com
ptrace. O isolamento entre usuários ou entre serviços é trabalho das permissões, dos namespaces e dos sandboxes, não apenas do espaço de endereços. - O próprio kernel. Todos os processos de um host compartilham um kernel, então um bug do kernel, ou uma falha de hardware como os vazamentos de execução especulativa (classe Spectre), pode atravessar as fronteiras entre processos. É por isso que cargas de trabalho sensíveis usam máquinas virtuais ou isolamento adicional de hardware.
- Supervisão. Os processos vivem em uma árvore. Um pai que morre pode deixar seus filhos órfãos, que são adotados pelo
init, ou pode levá-los junto (quando compartilham um grupo de processos ou um gerenciador de serviços para a unidade inteira). Um supervisor como osystemd, um runtime de contêineres ou um orquestrador pode reiniciar um processo que caiu, ou pode decidir parar e reiniciar o grupo inteiro de processos relacionados. Em um contêiner, se o processo principal (PID 1) termina, o contêiner para. Uma falha é "em geral só daquele processo" para a memória, e não necessariamente para o serviço.
Então trate a fronteira de um processo como contenção de falhas para erros de memória e acrescente o que a situação exigir para o resto: limites, permissões, supervisão e, para código não confiável, sandboxes mais fortes.
No Linux, ambos são "tarefas" criadas pela mesma família de chamadas de sistema (clone) com flags diferentes sobre o que é compartilhado. Os runtimes das linguagens acrescentam as suas próprias camadas por cima: as goroutines do Go e o event loop do Node não são threads do kernel, embora rodem sobre algumas. O kernel escalona apenas as suas próprias threads.
A vida de um processo
Diagram: The states of a process or thread
Apenas tantas threads quanto núcleos de CPU podem estar em execução (running) ao mesmo tempo. As outras estão prontas (ready) (esperando por um núcleo) ou bloqueadas (blocked) (esperando outra coisa, sem usar CPU nenhuma). As threads da maioria dos servidores estão bloqueadas a maior parte do tempo, esperando pela rede ou pelo disco, e é por isso que um servidor pode ter milhares de threads em poucos núcleos. Quando se diz que um sistema é CPU-bound, quer-se dizer que muitas threads estão prontas e poucas bloqueadas; I/O-bound é o oposto.
2. A troca de contexto
Para rodar outra thread em um núcleo, o kernel salva os registradores da atual, escolhe outra e restaura os registradores dela. Se a nova thread pertence a outro processo, ele também precisa trocar o espaço de endereços. Isso é uma troca de contexto (context switch). O custo direto é pequeno; medi dois processos passando um byte para lá e para cá por pipes em um único núcleo e obtive cerca de 3,5 microssegundos por ida e volta, o que inclui duas trocas e quatro chamadas de sistema. O custo indireto é maior e mais difícil de ver: a nova thread encontra os caches da CPU e o cache de tradução de endereços (TLB) cheios de dados da thread anterior, então começa devagar.
É por isso que mais threads nem sempre é mais rápido. Para trabalho CPU-bound, mais threads executáveis do que núcleos acrescenta trocas e cache misses e nenhuma vazão. Para trabalho I/O-bound, mais threads ajudam até a máquina passar o tempo trocando ou ficar sem memória (cada thread tem uma pilha, tipicamente 1 MB ou mais de espaço de endereços e parte dele é memória real). É também isso que motiva os event loops, as goroutines e o async/await: um número muito grande de tarefas baratas multiplexadas em poucas threads do kernel.
3. Escalonamento
O escalonador (scheduler) decide qual thread pronta roda em seguida. Seus objetivos conflitam: alta vazão (throughput) (trabalho total feito), baixa latência (a rapidez com que o trabalho interativo responde) e justiça (fairness) (ninguém passa fome). Os algoritmos clássicos valem como vocabulário:
- First-come, first-served: simples, mas um job longo faz todos os curtos atrás dele esperarem (o efeito comboio).
- Shortest job first: o melhor tempo médio de espera, mas precisa saber a duração dos jobs e pode deixar os jobs longos passando fome.
- Round robin: cada thread recebe uma fatia de tempo (time slice) (quantum) e depois vai para o fim da fila. Justo e responsivo.
- Filas de prioridade e multi-level feedback: as threads que usam a fatia inteira são tratadas como devoradoras de CPU e perdem prioridade; as threads que bloqueiam com frequência (as interativas) a mantêm. Os escalonadores modernos, como o do Linux, são descendentes dessa ideia que rastreiam quanta CPU cada tarefa recebeu e preferem as que receberam menos. A próxima seção, "Escalonamento em uma máquina Linux moderna", diz até onde vai o modelo de livro-texto.
Percorra o round robin com três processos que precisam de 5, 3 e 8 unidades de CPU. Use o seletor para comparar uma fatia de 2 com uma fatia de 6.
Interactive animation: round robin
A troca fica visível nos números. Com uma fatia de tempo de 2 há 7 trocas de contexto e o tempo médio de espera é 7,0; com uma fatia de 6 há apenas 2 trocas e a espera média é 4,3. Uma fatia mais curta torna o sistema mais responsivo (um processo espera no máximo algumas unidades antes de poder rodar), mas gasta mais tempo trocando; uma fatia mais longa se aproxima do first-come-first-served. No primeiro caso, o processo curto P2 termina no tempo 9; no segundo, no tempo 8. Um kernel real não usa uma fatia fixa como esta (veja "Escalonamento em uma máquina Linux moderna" abaixo): ele calcula por quanto tempo uma tarefa roda a partir do número de tarefas executáveis, dos seus pesos e das configurações do próprio kernel, tipicamente na ordem de milissegundos, e o custo por troca é minúsculo comparado a um milissegundo, de modo que, em sistemas reais, a questão é mais de justiça e latência do que de sobrecarga.
Escalonamento em uma máquina Linux moderna
O round robin com uma fatia fixa é um modelo para aprender. Um escalonador real do Linux difere de formas que importam quando se raciocina sobre latência:
- Classes de escalonamento. Os programas comuns rodam na classe fair (
SCHED_OTHER, tambémSCHED_BATCHeSCHED_IDLE). Acima dela ficam as políticas de tempo real (SCHED_FIFO,SCHED_RR), em que uma tarefa de tempo real executável sempre vence uma fair, eSCHED_DEADLINE, em que uma tarefa declara seu tempo de execução, prazo e período e o kernel admite apenas o que consegue garantir. Uma tarefa de tempo real que gira em loop pode deixar o resto do sistema passando fome, então elas são usadas com parcimônia e com limites. - Pesos, não fatias fixas. Na classe fair cada tarefa tem um peso derivado do seu valor de
nice, e a CPU é dividida em proporção aos pesos. Não existe uma fatia de tempo fixa do tipo do livro-texto: por quanto tempo uma tarefa roda depende de quantas tarefas estão executáveis e dos pesos delas. O Linux usou o Completely Fair Scheduler (CFS), que sempre rodava a tarefa que tinha recebido menos tempo de CPU ponderado, até a versão 6.6 (2023), quando ele foi substituído pelo EEVDF (earliest eligible virtual deadline first). O EEVDF ainda rastreia a parcela devida a cada tarefa, mas também dá a cada tarefa um prazo derivado da fatia de tempo que ela pediu, de modo que uma tarefa que precisa de fatias curtas (uma sensível a latência) pode ser escalonada mais cedo sem receber uma parcela maior. Os botões de ajuste e o comportamento exato diferem entre versões do kernel, então confira a sua antes de confiar em um detalhe. - Uma fila de execução por CPU, com um balanceador de carga que move tarefas entre as CPUs. O escalonador também leva em conta a afinidade de cache (uma tarefa fica mais feliz no núcleo onde estão os seus dados) e, em máquinas grandes, a topologia NUMA e o custo de migrar entre sockets. É por isso que fixar uma thread a um núcleo (como faz o experimento do ping-pong) muda os tempos.
- Grupos também compartilham, não só tarefas. Com cgroups a CPU é dividida primeiro entre grupos:
cpu.weight(uma parcela proporcional, relevante apenas sob contenção) ecpu.max(uma cota rígida por período que limita (throttles) um grupo depois que ele a usou, mesmo quando as CPUs estão ociosas). É assim que funcionam os limites de CPU de contêineres, e por isso um contêiner com cota pode mostrar picos de latência com um uso médio de CPU baixo (contêineres e Kubernetes). - Preempção e ticks. Se o kernel pode preemptar uma tarefa que roda em modo kernel depende da sua configuração (preempção voluntária, completa ou de tempo real), e um tick do timer nem sempre está rodando (CPUs ociosas e "tickless"). Uma rajada de interrupções, uma mudança na frequência da CPU ou outra máquina virtual no mesmo host (steal time) também atrasam tarefas de formas que o escalonador não controla.
A lição do modelo de livro-texto continua valendo: as fatias de tempo trocam responsividade por custo de troca, e a justiça compete com a vazão. Mas "quanto tempo minha thread vai esperar?" em um sistema real depende da versão do kernel, da política, dos pesos, das configurações de cgroup e da carga naquela CPU, e é melhor respondido medindo (perf sched, latência da fila de execução a partir de ferramentas de tracing, /proc/pressure/cpu).
Mais dois termos. O escalonamento preemptivo significa que o kernel pode tirar a CPU de uma thread (por uma interrupção do timer) sem a sua cooperação; o escalonamento cooperativo depende de as tarefas cederem a vez, como em um event loop de thread única em que uma função síncrona longa bloqueia tudo. E a inversão de prioridade é quando uma thread de baixa prioridade segura um lock de que uma thread de alta prioridade precisa, enquanto uma thread de prioridade média impede a de baixa de rodar; a correção usual é a herança de prioridade, um aumento temporário para o detentor do lock.
4. Memória virtual
Todo processo vê um espaço de endereços grande, privado e contíguo. O hardware e o kernel traduzem cada endereço virtual em um endereço físico usando uma tabela de páginas, em unidades de páginas de tamanho fixo (4 KB na maioria dos sistemas). A tradução fica em cache na TLB. Uma página virtual pode estar:
- mapeada a um frame físico na RAM,
- ainda não mapeada (nunca tocada),
- ou em swap ou apoiada por um arquivo em disco.
Diagram: Translating a virtual address
A memória virtual dá isolamento (um processo não pode ler a memória de outro), simplicidade (cada programa é ligado como se fosse dono da máquina), overcommit (a soma de todos os espaços de endereços pode exceder a RAM) e compartilhamento (as mesmas páginas físicas de uma biblioteca, ou de um arquivo, podem aparecer em muitos processos).
A memória é preguiçosa: um page fault é normal
Mapeei 256 MB com mmap e medi:
| Passo | Tempo | Page faults |
|---|---|---|
mmap de 256 MB | 0,02 ms | 0 |
| Escrever um byte em cada página (65 536 páginas) | 203 ms | 65 536 |
| Escrever em cada página de novo | 14 ms | 4 |
Mapear memória não custa nada; o kernel apenas registra que a faixa é válida. Cada primeiro toque causa um page fault menor (minor): a CPU cai no kernel, que acha um frame livre, o zera e o mapeia. Isso custou cerca de 3 microssegundos por página aqui, e 14 vezes mais que a segunda passada, quando as páginas já estavam lá. (Esses números são de uma pequena máquina virtual; o custo de um fault menor varia com o kernel, a CPU, o tamanho da página e se há huge pages em uso.) É por isso que "o processo usa 8 GB" pode enganar: o tamanho virtual é o que foi mapeado, o tamanho residente (RSS) é o que realmente está na RAM. Um page fault maior (major) precisa trazer a página do armazenamento (uma página que foi para o swap, ou uma página de arquivo que não está no cache). Seu custo depende de de onde a página vem: de algumas dezenas a centenas de microssegundos de um drive NVMe rápido, milissegundos de um disco giratório ou de um volume de rede ocupado, muito menos de memória comprimida (zswap ou zram, que trocam CPU por acesso a disco), e cresce quando o dispositivo está ocupado, a fila é longa ou o volume sofre throttling (como em discos de nuvem com limites de I/O). Ele equivale, portanto, a algo entre dezenas e milhares de vezes o custo de um fault menor, e a cauda (os piores faults) é muito pior que a média. Meça no seu próprio hardware (perf, /proc/<pid>/stat, vmstat) antes de decidir quanto um fault importa.
fork e copy-on-write
O fork cria uma cópia de um processo. Copiar literalmente um heap de 128 MB levaria muito tempo, e o filho muitas vezes chama exec logo em seguida e joga a cópia fora. Então o kernel copia só as tabelas de páginas e marca todas as páginas como copy-on-write: os dois processos compartilham as páginas físicas, somente leitura, e uma página só é copiada quando alguém escreve nela. Fiz o fork de um processo com um heap de 128 MB e fiz o filho escrever em uma parte de suas páginas:
| O filho escreve em | Faults no filho | Tempo gasto pelo filho |
|---|---|---|
| nada | 13 | menos de 1 ms |
| 10% das páginas | 3 290 | 13 ms |
| todas as páginas | 32 781 | 133 ms |
A chamada fork em si levou de 1 a 2 ms em cada caso. Cada página escrita custa um fault e uma cópia de 4 KB. É por isso que o Redis, que usa fork para tirar um snapshot, pode precisar de memória extra proporcional a quantas páginas o pai modifica enquanto o snapshot roda, e por que uma carga com muita escrita durante um fork mostra picos de latência.
5. Quando a memória acaba: substituição de páginas
Se não há frame livre quando uma página é necessária, o kernel precisa expulsar uma. Qual? Uma boa escolha é uma página que não será necessária em breve; uma escolha ruim significa que a página é lida de volta imediatamente. O kernel não enxerga o futuro, então os algoritmos o aproximam:
- FIFO: expulsar a página que está há mais tempo na memória. Simples, mas uma página pode ser antiga e ainda muito usada.
- LRU (least recently used): expulsar a página que não é usada há mais tempo, na aposta de que o passado prevê o futuro (localidade). O LRU exato é caro em hardware, então os sistemas reais usam aproximações como o algoritmo do relógio (clock) com um bit de "referenciada", e o Linux mantém listas ativa e inativa.
- Ótimo: expulsar a página que será usada mais longe no futuro. Impossível na prática, mas uma régua para os outros.
Percorra uma sequência de referências com três frames, alternando entre FIFO e LRU. A sequência clássica produz 15 faults com FIFO e 12 com LRU, em 20 referências.
Interactive animation: page replacement
Mais memória pode significar mais faults: a anomalia de Belady
Com FIFO, dar mais frames a um processo pode aumentar seus faults. Para a sequência de referências 1 2 3 4 1 2 5 1 2 3 4 5, o FIFO dá 9 faults com 3 frames e 10 com 4 (meu script confirma os dois). A página mais antiga não é necessariamente a menos útil, então o frame extra muda a ordem de expulsão de uma forma azarada. O LRU não tem esse problema (10 faults com 3 frames e 8 com 4): ele pertence a uma família de "algoritmos de pilha" cujo conteúdo com n frames é sempre um subconjunto do conteúdo com n+1 frames.
Localidade e o working set
Programas com localidade precisam de muito menos memória do que o seu tamanho. Em um teste com 5 000 referências em que 90% vão para 10 páginas "quentes" entre 100, o LRU teve 3 023 faults com 5 frames, 1 247 com 10, 432 com 20 e 286 com 50. Os primeiros frames importam muito, e depois os ganhos diminuem. O conjunto de páginas de que um processo precisa em um curto período é o seu working set. Se a soma dos working sets dos processos em execução excede a RAM, o sistema está em thrashing: gasta o tempo trocando páginas para dentro e para fora e faz pouco trabalho útil. O laço sequencial sobre 10 páginas é o pior caso para o LRU: com 9 frames cada uma das 200 referências dá fault, enquanto com 10 frames só as 10 primeiras dão. Isso parece um precipício de desempenho, e é o que você vê quando o working set de um banco de dados deixa de caber na memória, ou quando um processo ou contêiner cujo limite permite swap fica sem memória e a máquina começa a usar swap. (Um contêiner sem permissão de swap não sofre thrashing dessa forma; ele é morto, veja a seção 6.)
6. Pondo em uso
- "Out of memory" nem sempre é um vazamento. Olhe para a memória residente, não para o tamanho virtual, e para se o page cache (dados de arquivos que o kernel guarda na RAM que de outro modo estaria livre, e devolve quando necessário) está sendo contado.
- Os contêineres limitam a memória com cgroups; o que acontece no limite depende da configuração. Três coisas são fáceis de confundir:
- O limite (
memory.maxno cgroup v2,memory.limit_in_bytesno v1; o limite de memória do Kubernetes) conta mais que o heap: a memória residente do processo mais o page cache que ele causou, memória do kernel como buffers de socket e seus filhos. - Recuperar antes de matar. Quando o grupo atinge o limite, o kernel primeiro tenta recuperar memória dentro do grupo: descarta page cache limpo e, se houver swap disponível para aquele grupo, manda páginas anônimas para o swap. Só quando não consegue recuperar o bastante é que o OOM killer escolhe um processo naquele grupo e o mata (status de saída 137,
OOMKilled). A configuraçãomemory.highdo cgroup é um limite mais brando que faz throttling do grupo antes do rígido. Isso é separado de a máquina inteira ficar sem memória, quando o OOM killer do host escolhe uma vítima pela sua pontuação de "maldade" (ajustável comoom_score_adj). - O swap é uma configuração própria. Se um contêiner pode usar swap depende de o host ter swap, do limite de swap do cgroup (
memory.swap.max;--memory-swapno Docker) e do orquestrador: o Kubernetes tradicionalmente exigiu que os nós rodassem sem swap, e o suporte a swap para contêineres é um recurso mais novo, opcional e com regras próprias. Sem swap para o grupo, ultrapassar o limite leva direto ao OOM kill, como no meu experimento de 50 MB em contêineres e Kubernetes. Com swap, pode em vez disso ficar lento, com o grupo usando muito swap antes de ser morto (ou em vez disso).
Conheça o limite, a configuração de swap e as configurações de memória do seu runtime (por exemplo, um heap de JVM ou de Node maior que o limite do contêiner, ou um heap que cabe mas não deixa nada para pilhas, buffers e o page cache).
- Picos de latência podem ser page faults. Um fault maior em um caminho crítico pode custar de centenas de microssegundos a milissegundos ou mais, dependendo do armazenamento. Os bancos de dados o evitam mantendo o working set na memória, com
mlockou desativando o swap. - Thread por requisição tem um teto. Cada thread custa memória de pilha e trabalho do escalonador; essa é a razão dos servidores orientados a eventos e dos pools de threads de tamanho limitado (veja também padrões de resiliência para limitar a concorrência).
- Uma chamada de sistema custa mais que uma chamada de função: ela atravessa para o kernel. Agrupar (
writev, I/O com buffer) é o remédio padrão; e veja hierarquia de memória e Big-O na prática para o próximo nível da história, os caches da CPU. - Arquivos mapeados em memória (
mmap) deixam a maquinaria de paginação do kernel agir como o seu cache de arquivos. Os bancos de dados os usam, e também os evitam por boas razões: você perde o controle de quando o I/O acontece, e um fault no lugar errado trava a thread.
7. Erros comuns
- Ler "memória virtual" como "swap". A memória virtual é a tradução de endereços; o swap é um possível armazenamento de apoio.
- Usar mais threads do que núcleos em trabalho CPU-bound e esperar mais vazão.
- Julgar um processo pelo tamanho virtual, ou pelo primeiro número do
topsem o cache. - Esquecer que um filho criado por fork não compartilha nada logicamente, mas tudo fisicamente até escrever.
- Escolher uma fatia de tempo ou o tamanho de um pool de threads por palpite em vez de medir.
- Supor que um processo e um contêiner são a mesma coisa: um contêiner é um processo (ou mais) com visões e recursos limitados, compartilhando o kernel do host.
- Supor que processos separados não conseguem afetar uns aos outros: eles compartilham o disco, a CPU, a rede, o page cache e o kernel, podem compartilhar memória de propósito e são gerenciados por supervisores.
- Tratar "limite de memória do contêiner", "OOM kill" e "swap" como uma coisa só, ou citar um único número para o que custa um page fault.
8. Coisas a mencionar em uma entrevista
- Processo versus thread em termos de espaço de endereços, custo, comunicação e falha, e os limites do isolamento de processos (recursos compartilhados, memória compartilhada, um kernel, supervisores).
- Os estados pronto, em execução e bloqueado, e o que uma troca de contexto custa direta e indiretamente.
- Escalonamento preemptivo versus cooperativo; round robin e o efeito da fatia de tempo; inversão de prioridade e sua correção; e como o Linux realmente escalona (classe fair com pesos, classes de tempo real, EEVDF desde a 6.6, parcelas e cotas de cgroup).
- Memória virtual como tabelas de páginas mais uma TLB, com page faults (menores e maiores), copy-on-write e por que o
forké barato. - Substituição de páginas (FIFO, LRU, clock), localidade, o working set, thrashing e a anomalia de Belady.
- Uma história concreta: "o contêiner foi morto porque sua memória (conjunto residente e page cache) atingiu o limite do cgroup e a recuperação não bastou, então o OOM killer rodou; não havia swap para aquele grupo". E as três perguntas separadas por trás dela: o que o limite conta, o que o kernel recupera primeiro e se o swap é permitido.
Resumo rápido
- Um processo tem o seu próprio espaço de endereços; threads compartilham um. As threads são mais baratas (cerca de 48 microssegundos contra 3,2 ms para criar aqui) e precisam de locks.
- O escalonador troca vazão, latência e justiça; uma fatia de round robin mais curta significa mais trocas (7 contra 2 no exemplo) e uma resposta mais rápida.
- A memória virtual é preguiçosa: mapear 256 MB custou 0,02 ms e tocá-los custou 65 536 page faults. Um fault menor foi de cerca de 3 microssegundos aqui; um fault maior depende do armazenamento, de dezenas de microssegundos a milissegundos.
- O copy-on-write torna o
forkrápido; as páginas só são copiadas quando escritas (33 000 faults quando o filho escreveu tudo). - A substituição de páginas escolhe vítimas adivinhando o futuro: o LRU venceu o FIFO (12 contra 15 faults), o FIFO pode mostrar a anomalia de Belady (9 e depois 10), e um working set que não cabe significa thrashing.
Apêndice: o código dos experimentos
Os tempos vêm do primeiro script (Python 3 no Linux, apenas a biblioteca padrão; rodado em uma pequena máquina virtual, então os tempos absolutos serão diferentes na sua (com a versão do kernel, a CPU, o tamanho da página e o hipervisor) e variam de execução para execução, enquanto as contagens de faults são exatas). Os scripts mostram os princípios; eles não modelam o escalonador real do Linux nem o código real de substituição de páginas. O segundo script é determinístico: os mesmos modelos de substituição de páginas e de escalonamento movem as animações acima.
Page faults, copy-on-write, trocas de contexto e criação de threads
import os, mmap, resource, time, threading, sys
PAGE = os.sysconf("SC_PAGE_SIZE")
def faults():
r = resource.getrusage(resource.RUSAGE_SELF); return r.ru_minflt, r.ru_majflt
# ---- 1. virtual memory is lazy: mapping 256 MB costs nothing until the pages are touched
size = 256 * 1024 * 1024
f0 = faults(); t0 = time.perf_counter()
m = mmap.mmap(-1, size)
t1 = time.perf_counter(); f1 = faults()
for off in range(0, size, PAGE): m[off] = 1
t2 = time.perf_counter(); f2 = faults()
print(f"page size {PAGE}; mmap of {size>>20} MB: {1000*(t1-t0):.2f} ms, {f1[0]-f0[0]} minor faults")
print(f"touching every page: {1000*(t2-t1):.0f} ms, {f2[0]-f1[0]} minor faults (pages: {size//PAGE})")
t3 = time.perf_counter()
for off in range(0, size, PAGE): m[off] = 2
t4 = time.perf_counter(); f4 = faults()
print(f"touching them again: {1000*(t4-t3):.0f} ms, {f4[0]-f2[0]} faults")
m.close()
# ---- 2. fork is copy-on-write: the child shares pages until it writes
buf = bytearray(b"x" * (128 * 1024 * 1024)); n = len(buf)//PAGE
def child_writes(fraction):
r, w = os.pipe(); t = time.perf_counter()
pid = os.fork()
if pid == 0:
a = faults()[0]; s = time.perf_counter()
for i in range(int(n * fraction)): buf[i * PAGE] = 7
os.write(w, f"{faults()[0]-a} {1000*(time.perf_counter()-s):.0f}".encode()); os._exit(0)
forkms = 1000 * (time.perf_counter() - t)
os.waitpid(pid, 0); fl, ms = os.read(r, 100).decode().split()
return forkms, fl, ms
for frac in (0.0, 0.1, 1.0):
fm, fl, ms = child_writes(frac)
print(f"fork of a {n*PAGE>>20} MB process took {fm:.1f} ms; child wrote {int(frac*100)}% of pages: {fl} faults, {ms} ms")
# ---- 3. what a context switch costs: two processes ping-pong one byte through pipes
def pingpong(rounds=20000):
a_r, a_w = os.pipe(); b_r, b_w = os.pipe()
pid = os.fork()
if pid == 0:
os.sched_setaffinity(0, {0})
for _ in range(rounds): os.read(a_r, 1); os.write(b_w, b"x")
os._exit(0)
os.sched_setaffinity(0, {0})
t = time.perf_counter()
for _ in range(rounds): os.write(a_w, b"x"); os.read(b_r, 1)
dt = time.perf_counter() - t; os.waitpid(pid, 0)
return dt / rounds * 1e6
print(f"process ping-pong on one core: {pingpong():.1f} microseconds per round trip (2 switches)")
# ---- 4. thread vs process creation
def spawn_thread(k=2000):
t = time.perf_counter()
for _ in range(k):
th = threading.Thread(target=lambda: None); th.start(); th.join()
return (time.perf_counter() - t) / k * 1e6
def spawn_proc(k=300):
t = time.perf_counter()
for _ in range(k):
pid = os.fork()
if pid == 0: os._exit(0)
os.waitpid(pid, 0)
return (time.perf_counter() - t) / k * 1e6
print(f"create+join a thread: {spawn_thread():.0f} us; fork+wait a process (here with a 128 MB heap): {spawn_proc():.0f} us")
# ---- 5. threads share memory, processes do not
shared = [0]
def bump(): shared[0] += 1
th = threading.Thread(target=bump); th.start(); th.join()
pid = os.fork()
if pid == 0: shared[0] += 100; os._exit(0)
os.waitpid(pid, 0)
print("after a thread added 1 and a child process added 100:", shared[0])
Substituição de páginas e escalonamento round-robin
from collections import deque, OrderedDict
def paging(refs, frames, policy):
mem = OrderedDict(); faults = 0
for p in refs:
if p in mem:
if policy == "lru": mem.move_to_end(p) # FIFO ignores hits
else:
faults += 1
if len(mem) == frames: mem.popitem(last=False) # oldest (FIFO) or least recently used (LRU)
mem[p] = True
return faults
REFS = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]
print("textbook string, 3 frames: FIFO", paging(REFS,3,"fifo"), "LRU", paging(REFS,3,"lru"))
B = [1,2,3,4,1,2,5,1,2,3,4,5]
print("Belady string, FIFO:", {f: paging(B,f,"fifo") for f in (3,4)}, " LRU:", {f: paging(B,f,"lru") for f in (3,4)})
# a loop over 10 pages: LRU with 9 frames is the worst case, with 10 it never faults again
loop = list(range(10)) * 20
print("loop over 10 pages, 200 refs, LRU:", {f: paging(loop,f,"lru") for f in (8,9,10)})
# locality: 90% of references go to 10 hot pages out of 100
import random
rnd = random.Random(3); hot = [rnd.randrange(10) if rnd.random() < .9 else rnd.randrange(10,100) for _ in range(5000)]
print("5000 refs, 90% to 10 hot pages of 100, LRU faults by frames:", {f: paging(hot,f,"lru") for f in (5,10,20,50,100)})
def round_robin(bursts, q):
t = 0; ready = deque(bursts); left = dict(bursts); first = {}; finish = {}; last = None; switches = 0
ready = deque(n for n,_ in bursts)
while ready:
n = ready.popleft(); run = min(q, left[n])
if last is not None and last != n: switches += 1
last = n; t += run; left[n] -= run
if left[n]: ready.append(n)
else: finish[n] = t
wait = {n: finish[n] - b for n,b in bursts}
return switches, finish, wait, sum(wait.values())/len(wait), sum(finish.values())/len(finish)
BURSTS = [("P1",5),("P2",3),("P3",8)]
for q in (1,2,6):
s,fin,w,aw,at = round_robin(BURSTS,q); print(f"quantum {q}: {s} switches, finish {fin}, avg wait {aw:.1f}, avg turnaround {at:.1f}")
Fontes
- Remzi e Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces, os capítulos sobre escalonamento, espaços de endereços, paginação e substituição de páginas.
- Silberschatz, Galvin e Gagne, Operating System Concepts (Wiley), para a anomalia de Belady e o modelo de working set.
- Peter Denning, The Working Set Model for Program Behavior (Communications of the ACM, 1968), e Thrashing: Its Causes and Prevention (1968).
- Páginas de manual do Linux: fork(2), mmap(2), clone(2).
- Documentação do kernel Linux, CFS scheduler, EEVDF scheduler, Real-time group scheduling and SCHED_DEADLINE e o cgroup v2 admin guide (
memory.max,memory.high,memory.swap.max,cpu.weight,cpu.max) e Concepts overview of memory management.
Pratique este tema: CS Fundamentals