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.

ProcessoThread
Espaço de endereçoso 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çãoalto (novo espaço de endereços, tabelas de páginas)menor (uma pilha e alguma contabilidade)
Comunicaçãoprecisa de IPC: pipes, sockets, memória compartilhadalêem e escrevem a mesma memória (e precisam de locks)
Uma falhaem geral encerra só aquele processo, mas veja os limites abaixopode derrubar o processo inteiro
Bom paraisolamento, segurança, uso de várias máquinasparalelismo 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:

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:

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:

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:

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:

PassoTempoPage faults
mmap de 256 MB0,02 ms0
Escrever um byte em cada página (65 536 páginas)203 ms65 536
Escrever em cada página de novo14 ms4

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 emFaults no filhoTempo gasto pelo filho
nada13menos de 1 ms
10% das páginas3 29013 ms
todas as páginas32 781133 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:

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

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).

7. Erros comuns

8. Coisas a mencionar em uma entrevista

Resumo rápido

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

Pratique este tema: CS Fundamentals

Mais guias