Suporte do SO à Concorrência

Como dito na Introdução, os estudos de concorrência e sistemas operacionais se retro-alimentam:

• As primeiras descobertas sobre concorrência surgiram durante o desenvolvimento dos primeiros sistemas operacionais.
• Um sistema operacional é o tipo de sistema mais complexo e concorrente que alguém pode chegar a trabalhar.
• Os conceitos e técnicas desenvolvidos nos estudos de concorrência têm como principal domínio de aplicação justamente os sistemas operacionais.

Além disso, todo e qualquer programa concorrente eventualmente acaba desembocando no sistema operacional. É o SO que decide qual código roda em qual núcleo e em que momento; que media o acesso aos dispositivos de I/O e que fornece os primitivos fundamentais (processos, threads, escalonamento, sincronização, interfaces de I/O) a partir dos quais qualquer código concorrente é montado.

Portanto, para começarmos falar de concorrência precisamos estabelecer conceitos que surgem justamente na área de sistemas operacionais. Nesse capítulo, vamos entender, num nível suficiente para esse livro, os seguintes conceitos:

• Processos
• Threads
• Escalonamento

Unidades Escalonáveis: Processos e Threads

Tanto processos quanto threads atuam como tarefas: construtos do sistema operacional que podem ser escalonados. Isto é, na presença de vários processos e threads, apenas uma parte deles é selecionada para executar no hardware. Ao longo do tempo, uma tarefa dá lugar (voluntariamente ou não) para outra ser executada.

A diferença entre esses construtos é no nível de isolamento entre eles, o que determina o poder e os riscos que cada um possui.

Processos

Processos são tarefas independentes cujo contexto de execução é altamente isolado.

Dois processos não podem acessar uma mesma região de memória. Cada processo tem seu próprio:

• Espaço de endereçamento virtual
• Tabela de file descriptors (arquivos, pipes, sockets, etc)
• Conjunto de signal dispositions
• Conjunto de mapeamentos de memória
• Heap e segmentos estáticos de memória (.text, .data, .bss)
• ID (Process ID ou PID)

Todos esses componentes são isolados entre dois processos distintos. Isto significa que quando um processo A escreve algo no endereço 0x7fff, ele está escrevendo numa página de memória física que um outro processo B não pode ver (imposto pela Memory Management Unit, MMU, da CPU).

Esse isolamento tem prós e contras.

• O principal pró é que se um processo crashar — ao dereferenciar um ponteiro inválido ou corromper seu heap — ele não irá afetar outros processos, devido ao isolamento.
• O principal contra é que a comunicação entre dois processos (conhecida como IPC, Inter-Process Communication) é mais trabalhosa de ser feita, tanto em termos de codificação quanto de performance.

Threads

Threads (também chamadas de threads nativas, de kernel ou do SO, para distinguir de threads de usuário) são tarefas que vivem dentro de um processo e cujo contexto de execução é pouco isolado.

Diferentemente de processos, duas threads de um mesmo processo podem acessar uma mesma região de memória. De maneira geral, todas threads em um mesmo processo compartilham:

• O mesmo espaço de endereçamento virtual
• O mesmo heap e segmentos estáticos de memória
• A mesma tabela de file descriptors
• O mesmo conjunto de signal dispositions

Isso não quer dizer que as threads compartilham tudo. Cada thread tem um estado próprio, separado das outras threads no mesmo processo. Esse estado inclui:

• Uma pilha. Permite que cada thread execute funções de maneira independente.
• Um conjunto de registradores, incluindo os registradores PC (Program Counter) e SP (Stack Pointer). Permite que cada thread execute uma sequência de instruções individual.
• Contexto de escalonamento do kernel. Permite que cada thread seja escalonada independentemente pelo SO.
• Um ID (Thread ID ou TID).

Todo processo tem pelo menos uma thread, que é a thread principal.

Prós e Contras

Esse isolamento menor entre threads apresenta prós e contras.

• O principal pró é que a comunicação entre threads é muito mais fácil de ser feita do que entre processos. Como as threads compartilham o mesmo heap e variáveis globais, a escrita de uma thread numa dessas localizações é visível para todas as outras threads do mesmo processo.
• Além disso, outro pró é que, como a criação de uma thread re-aproveita a maior parte das estruturas de dados usadas pelo processo, esse processo é consideravelmente mais barato (em termos de ciclos de CPU e memória).

No entanto, esse “poder” é justamente o que permite alguns dos maiores riscos quando falamos de threads:

• A memória compartilhada entre threads significa que duas escritas na mesma localização podem gerar bugs de concorrência, que levam o programa a ter um comportamento fora do esperado, como veremos mais pra frente.
• Para evitar esses bugs de concorrência, são introduzidos mecanismos de sincronização, que restringem o acesso a regiões de memória específicas, o que pode gerar os custos de overhead mencionados no Capítulo 1.
• A memória compartilhada também significa que se um thread corromper o heap do processo, todas as threads serão afetadas.

Simultaneous Multithreading (SMT)

Geralmente, cada thread ocupa um único núcleo do processador num dado instante. No entanto, uma tecnologia conhecida simultaneous multithreading (SMT) ou hardware multithreading permite que um único núcleo da CPU exiba para o sistema operacional duas ou mais “threads”. É por isso que em, algumas máquinas, quando o sistema operacional lista o número de threads que ele pode rodar ao mesmo, esse número acaba sendo maior do que a quantidade de núcleos no processador.

Por exemplo, abaixo está o resultado do lscpu (um programa de linha de comando do Linux que retorna informações sobre as CPUs do computador) na minha máquina pessoal:

$ lscpu
Architecture:                x86_64
  CPU op-mode(s):            32-bit, 64-bit
  Address sizes:             39 bits physical, 48 bits virtual
  Byte Order:                Little Endian
CPU(s):                      16   # <-- o SO vê 16 threads/"CPUs"
  On-line CPU(s) list:       0-15
Vendor ID:                   GenuineIntel
  Model name:                13th Gen Intel(R) Core(TM) i7-13620H
    CPU family:              6
    Model:                   186
    Thread(s) per core:      2   # <-- temos duas threads por núcleo
    Core(s) per socket:      8   # <-- temos 8 núcleos físicos
    Socket(s):               1

Escalonamento

Vimos que processos e threads são as unidades básicas que um sistema operacional utiliza para organizar as tarefas que ele manda para o hardware executar. No entanto, a maioria dos computadores para usuários comuns atualmente têm de 4 a 8 núcleos. Mesmo com SMT, isso limita a quantidade de threads em paralelo nesses computadores a até 16 threads.

Se você abrir o Gerenciador de Tarefas do seu computador, você vai ver que existem muito mais processos e threads em execução do que 16. Portanto, além de criar as abstrações para representar tarefas, o sistema operacional também precisa responder a seguinte pergunta: quais tarefas serão executadas pelo hardware, num dado momento?

A resposta para essa pergunta é o escalonamento: um dos processos mais importantes que o sistema operacional realiza, e que determina a execução de todos os programas do computador.

O escalonamento é realizado por um escalonador: um processo que roda no kernel do sistema operacional e segue algum algoritmo para decidir qual será a próxima tarefa a ser executada.

O escalonamento pode ser feito de maneira preemptiva, não-preemptiva/cooperativa ou mista. Esse tipo de escalonamento tem impacto direto em como o programador escreve código.

Escalonamento Preemptivo

No escalonamento preemptivo, o escalonador pode interromper a tarefa em execução a qualquer momento para trocá-la por outra tarefa.

Vamos ver o funcionamento desse tipo de escalonamento. Para simplificar, vamos supor que estamos numa máquina com um único núcleo de CPU, sem SMT.

Um escalonador preemptivo inicialmente cria um temporizador que “apita” a cada período de tempo (por exemplo, 1 ms)¹. Esse temporizador define uma fatia/quantum de tempo, durante a qual cada tarefa irá executar na CPU.

Sempre que o temporizador apita, o escalonador força a interrupção da tarefa em execução — independente se ela quer parar ou não — salvando seu estado e trocando para a próxima tarefa.

Esse processo em que o escalonador salva o estado da tarefa interrompida e troca para a próxima tarefa é conhecido como troca de contexto (context switch), que tem um custo considerável de ciclos de CPU e de memória. Um context switch pode acontecer entre quaisquer duas instruções de uma tarefa.

Em suma, no escalonamento preemptivo o escalonador está no controle. Isso permite que ele garanta uma distribuição justa de tempo de CPU e robustez contra processos bugados ou maliciosos que tentem consumir a CPU sem parar.

Ilustração do escalonamento preemptivo com 3 tarefas. “int.” = interrupção

A maior parte dos sistemas operacionais adota o escalonamento preemptivo para processos que não são do kernel, isto é, processos a nível de usuário, para evitar que um processo mal-comportado não ceda tempo de CPU para outras tarefas.

Escalonamento Cooperativo/Não-preemptivo

No escalonamento cooperativo, é a própria tarefa que escolhe quando vai interromper sua execução e liberar o controle para o escalonador.

Para indicar ao escalonador que interrompa a execução, as tarefas usam uma função (ou keyword) geralmente chamada de yield ou await. Essa função é inserida no código que o programador escreve. Veja exemplos em Python e Lua:

async def tarefa(url: str) -> str:
    print(f"Consultando {url}...")
    res = await client.get(url)  # <-- yield aqui
    return res.text

function tarefa(url)
    print("Consultando " .. url .. "...")
    local res = coroutine.yield(http_get(url)) -- yield aqui
    return res.body
end

Um padrão muito comum é que as tarefas façam o yield enquanto esperam algum resultado de I/O ficar pronto, como ao ler algo do disco, enviar uma mensagem num socket, etc.

Nesse modelo, o escalonador confia que as tarefas não irão se comportar mal. Ou seja, que elas não irão “monopolizar” a CPU ao não chamar o yield em momentos oportunos. Uma tarefa que não libera o controle irá deixar todas as outras tarefas em inanição (starvation).

Após um yield, o escalonador ainda faz um context switch, porém este é muito menos custoso de se realizar, pois como o yield funciona como uma chamada de função, ele só precisa salvar um subconjunto dos registradores do programa.²

Comparação

Escalonamento híbrido

A maioria dos sistemas operacionais e runtimes não utilizam um escalonamento que é 100% preemptivo ou 100% cooperativo, mas sim alguma forma híbrida.

Sistemas operacionais geralmente adotam o modelo preemptivo para processos e thread no user-space, mas internamente no kernel utilizam o modelo cooperativo em certos cotextos.

Alguns runtimes, como os de Go e Erlang, usam um modelo cooperativo, mas com um limite de tempo ou de chamadas de função que, quando atingido, força a preempção.

Escalonamento no user-space

Apesar da maior parte desse capítulo ter focado em conceitos do sistema operacional, que são implementados no kernel-space, o escalonamento é um processo que pode ser implementado no user-space.

Quando feito dessa forma, o escalonador é geralmente implementado nativamente em algum runtime (é o caso de Go e Erlang) ou numa biblioteca (Python, C++). A unidade escalonada não são processos ou threads do sistema operacional, mas sim objetos no user-space que possuem um contexto de execução, lembrando threads e processos.

Algumas linguagens e bibliotecas implementam um event loop, um programa no user-space responsável por gerenciar eventos e tarefas que reagem a esses eventos. Todo event loop contém um escalonador, que obviamente é implementado no user-space.

A principal motivação para implementar escalonamento no user-space é que o custo computacional e de memória é consideravelmente menor se comparado ao escalonamento no kernel-space. Com escalonamento no user-space, um programa pode chegar a milhões de tarefas concorrentes. A razão por trás disso está na seção Comparando context switches.

Veremos ao longo do livro que escalonamento no user-space é a base do modelo de concorrência de muitos runtimes.

1. No caso do escalonador do sistema operacional, esse temporizador é implementado no hardware do computador. ↩

2. O motivo pelo qual um context switch após um yield é mais eficiente do que um preemptivo é explicado na seção Comparando context switches e também aqui. ↩