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 deixe de ceder 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 threads no user-space, mas internamente no kernel utilizam o modelo cooperativo em certos contextos.

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.

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