Visão Geral do Escalonamento

Em sistemas com mais processos do que núcleos de CPU, é necessário compartilhar o tempo de processamento entre eles. O objetivo é que esse compartilhamento seja transparente para os processos de usuário. Uma técnica comum é multiplexar os processos nos núcleos disponíveis, criando a ilusão de que cada processo tem acesso exclusivo à CPU.

Quando o Xv6 Realiza a Troca de Processos?

A troca ocorre em duas situações principais:

1. Troca Cooperativa: Quando um processo está aguardando a conclusão de uma operação de E/S em dispositivo ou pipe, aguardando o término de um processo filho, ou quando está em uma chamada de sistema sleep. O mecanismo de sleep e wakeup é utilizado.
2. Troca Preemptiva: Para lidar com processos que realizam cálculos longos sem dormir, o Xv6 utiliza interrupções de temporizador para forçar periodicamente a troca de contexto.

Desafios do Escalonamento

A implementação do escalonamento envolve superar vários desafios:

• Como efetuar a troca entre processos? O código de troca de contexto (context switch) é uma das partes menos transparentes do Xv6.
• Como forçar a troca de forma transparente para o processo de usuário? O Xv6 utiliza interrupções de temporizador para acionar a troca.
• Como evitar condições de corrida ao selecionar processos para execução, já que todos os núcleos compartilham o mesmo conjunto de processos? Bloqueios (locks) são essenciais.
• Quando um processo termina, ele deve liberar seus recursos (como memória), mas não pode fazê-lo completamente por si mesmo, pois precisa usar sua própria pilha de kernel.
• Cada núcleo de CPU precisa rastrear qual processo está executando, garantindo que chamadas de sistema afetem o estado correto.
• O mecanismo de sleep permite a um processo liberar a CPU, e wakeup permite reativar outro processo.

A implementação do Xv6 busca simplicidade, mas o código resultante ainda é complexo devido a esses desafios.

Troca de Contexto

O processo de troca de um processo de usuário para outro envolve os seguintes passos:

1. O processo de usuário (ex.: shell) inicia uma chamada de sistema ou sofre uma interrupção.
2. Controle é transferido para o thread de kernel do processo antigo.
3. Ocorre uma troca de contexto para o thread de escalonador (scheduler thread) do CPU atual.
4. O escalonador realiza outra troca de contexto para o thread de kernel do novo processo (ex.: cat).
5. Uma instrução de retorno de trap leva o controle de volta para o processo de usuário (cat).

Cada CPU tem um thread de escalonador dedicado. A troca de contexto salva os registradores da thread antiga e restaura os da nova. Isso inclui o ponteiro de pilha (sp) e o contador de programa, efetivamente mudando a thread em execução.

Função swtch()

A função swtch é responsável por trocar threads de kernel. Ela salva e restaura os 32 registradores da arquitetura RISC-V, que formam o contexto da thread.

Fluxo de operação:

• Quando um processo precisa liberar a CPU, sua thread de kernel chama swtch.
• swtch salva o contexto atual na estrutura context do processo (p->context).
• Em seguida, restaura o contexto previamente salvo do escalonador, que reside em cpu->scheduler_context.
• Apenas os registradores callee-saved são salvos explicitamente; os caller-saved já foram empilhados automaticamente pelos chamadores.
• O registrador pc não é salvo diretamente. Em vez disso, o ra (endereço de retorno) é salvo. Ao restaurar o ra de uma nova thread e retornar, a execução continua no ponto onde essa nova thread havia chamado swtch anteriormente.

O Escalonador do Xv6

A função scheduler (kernel/proc.c) é o coração do escalonamento. Ela é executada por um loop infinito em cada CPU.

Exemplo de Código Simplificado do Escalonador

void scheduler(void) {
  struct proc *p;
  struct cpu *c = mycpu();
  c->scheduler_thread = ...; // Inicialização da thread do escalonador

  for(;;) {
    // Habilita interrupções para permitir a troca de contexto
    intr_on();

    for(p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      if(p->state == RUNNABLE) {
        // Mude o estado para RUNNING, associe ao CPU
        p->state = RUNNING;
        c->current_proc = p;
        // Troca de contexto: de CPU->scheduler_ctx para p->context
        swtch(&c->scheduler_ctx, &p->context);
        // Retornamos aqui quando o processo nos devolve a CPU
        c->current_proc = 0;
      }
      release(&p->lock);
    }
  }
}

Passagem da CPU para o Escalonador

Quando um processo precisa dormir ou é finalizado, ele segue um caminho específico:

1. Adquire o lock do processo (p->lock).
2. Atualiza seu estado (para SLEEPING, ZOMBIE, etc.).
3. Chama a função sched().

A função sched realiza verificações de segurança e então invoca swtch(&p->context, &mycpu()->scheduler_ctx). Isso salva o contexto do processo atual e restaura o contexto do escalonador, retornando a execução para o ponto dentro do loop infinito do scheduler.

O Bloqueio p->lock: O Xv6 mantém p->lock no momento da chamada a swtch. O controle do bloqueio é, em essência, passado para o código que será executado após a troca. Isso é necessário para proteger os campos state e context do processo durante a transição crítica.

Caso Especial: Criação de Novo Processo

Ao alocar uma nova estrutura de processo (allocproc), o endereço de retorno (ra) de seu contexto é apontado para forkret. Na primeira vez que swtch é chamado para este processo, a execução salta para forkret, cuja principal função é liberar p->lock.

Acessando Informações da CPU e do Processo

As informações de cada CPU são armazenadas em um array global cpus[]. O identificador único de cada CPU (seu hart id no RISC-V) é armazenado no registrador tp para facilitar o acesso.

Funções de Acesso

struct cpu* mycpu(void) {
  // Obtém o ID do hart (núcleo) atual de 'tp'
  int id = get_hartid();
  // Usa o ID para indexar o array global
  return &cpus[id];
}

struct proc* myproc(void) {
  // Desabilita interrupções para obter um ponteiro consistente
  push_off();
  struct proc *p = mycpu()->current_proc;
  pop_off();
  return p;
}

Atenção: Os valores retornados por essas funções são frágeis. Se uma interrupção de temporizador ocorrer e causar uma troca de processo, o ponteiro retornado anteriormente pode se tornar inválido. Por isso, o Xv6 exige que as interrupções sejam desabilitadas ao usar o struct cpu retornado.

Sincronização com sleep e wakeup

Esses mecanismos permitem que um processo espere por um evento sem desperdiçar ciclos de CPU.

Implementação Ineficiente (Sem Sincronização)

// Exemplo de semáforo simples (não presente no Xv6)
struct semaphore {
    struct spinlock lock;
    int count;
};

void V_semaforo(struct semaphore *s) {
    acquire(&s->lock);
    s->count++;
    release(&s->lock);
}

void P_semaforo(struct semaphore *s) {
    while (s->count == 0) {
        // Espera ativa (busy-wait) - ineficiente!
    }
    acquire(&s->lock);
    s->count--;
    release(&s->lock);
}

O problema é a espera ativa no while. Precisamos de uma forma de ceder a CPU.

Primeira Tenta com sleep/wakeup

void V_semaforo(struct semaphore *s) {
    acquire(&s->lock);
    s->count++;
    wakeup(s); // Acorda processos esperando neste semáforo
    release(&s->lock);
}

void P_semaforo(struct semaphore *s) {
    while (s->count == 0) {
        sleep(s); // Dorme até ser acordado
    }
    acquire(&s->lock);
    s->count--;
    release(&s->lock);
}

Novo Problema (Condição de Corrida): Se P verificar count==0, mas antes de chamar sleep, V for executado em outro CPU, incrementando count e chamando wakeup, P não será acordado porque ainda não está dormindo. Quando finalmente chamar sleep, ninguém irá acordá-lo novamente.

Adicionando um Bloqueio de Condição

void V_semaforo(struct semaphore *s) {
    acquire(&s->lock);
    s->count++;
    wakeup(s);
    release(&s->lock);
}

void P_semaforo(struct semaphore *s) {
    acquire(&s->lock); // Adquire o lock antes de verificar a condição
    while (s->count == 0) {
        sleep(s); // Problema: dorme segurando o lock -> Deadlock!
    }
    s->count--;
    release(&s->lock);
}

Problema: P adormece segurando s->lock, impedindo que V o adquira para alterar count e acordá-lo. Resultado: deadlock.

Solução Final do Xv6

A função sleep no Xv6 aceita um segundo argumento: o bloqueio de condição (condition lock). sleep liberará este bloqueio de forma atômica (junto com a ação de dormir). Isso resolve o problema, pois V só poderá adquirir o bloqueio de condição após P ter efetivamente adormecido.

void V_semaforo(struct semaphore *s) {
    acquire(&s->lock);
    s->count++;
    wakeup(s);
    release(&s->lock);
}

void P_semaforo(struct semaphore *s) {
    acquire(&s->lock);
    while (s->count == 0) {
        // Passa o bloqueio de condição. sleep o libera antes de dormir.
        sleep(s, &s->lock);
    }
    s->count--;
    release(&s->lock);
}

Na prática, a chamada sleep(chan, lk) faz o seguinte:

1. Adquire o p->lock do processo atual.
2. Libera o bloqueio de condição lk.
3. Marca o estado do processo como SLEEPING e armazena o canal chan.
4. Chama sched() para liberar a CPU (o que, internamente, liberará p->lock durante a troca de contexto).

wakeup(chan) percorre a tabela de processos, adquire p->lock para cada um, e se encontrar um processo em estado SLEEPING com o mesmo canal chan, muda seu estado para RUNNABLE.

Exemplo: Pipes no Xv6

Pipes usam sleep e wakeup para sincronização entre leitores e escritores.

struct pipe {
    struct spinlock lock;
    char data[PIPESIZE];
    uint nread;     // Próximo byte a ser lido
    uint nwrite;    // Próximo byte a ser escrito
    int readopen;
    int writeopen;
};

Sincronização na Escrita (pipewrite)

1. Adquire pipe->lock.
2. Enquanto o buffer estiver cheio (nwrite - nread == PIPESIZE):
   • Chama wakeup(&pipe->nread) para acordar possíveis leitores.
   • Chama sleep(&pipe->nwrite, &pipe->lock) para liberar a CPU e o lock, esperando por espaço.
3. Escreve um byte, incrementa nwrite.
4. Libera pipe->lock.

Sincronização na Leitura (piperead)

1. Adquire pipe->lock.
2. Enquanto o buffer estiver vazio (nwrite == nread) e houver escritores:
   • Chama sleep(&pipe->nread, &pipe->lock) para esperar dados.
3. Lê bytes do buffer, incrementa nread.
4. Chama wakeup(&pipe->nwrite) para acordar escritores que possam estar esperando por espaço.
5. Libera pipe->lock.

Encerramento de Processos (exit, wait, kill)

exit e wait

Quando um processo filho chama exit:

1. Libera alguns de seus recursos (arquivos, memória de usuário).
2. Recoloca seus processos filhos sob o processo init.
3. Muda seu estado para ZOMBIE.
4. Chama wakeup no canal de seu processo pai (para acordar um wait bloqueado).
5. Cede a CPU finalmente via sched().

O processo pai, ao chamar wait:

1. Varre a tabela de processos em busca de um filho com estado ZOMBIE.
2. Se encontrar, coleta seu código de saída, libera a estrutura do processo e retorna o PID do filho.
3. Se não encontrar, mas existirem filhos vivos, adormece (usando um lock de condição chamado wait_lock) até ser acordado por um exit de filho.

A chave é que exit e wait coordenam-se através de wakeup e sleep, usando o wait_lock como bloqueio de condição para evitar perda de notificações.

kill

A chamada kill não termina um processo diretamente. Ela apenas marca o processo alvo (p->killed = 1). O processo terminará em breve porque:

• Se estiver rodando em espaço de usuário, a próxima interrupção ou chamada de sistema o levará ao kernel, onde usertrap verificará a flag p->killed e chamará exit.
• Se estiver dormindo, kill chamará wakeup para acordá-lo. O código que envolve o sleep do processo vítima deve, idealmente, verificar p->killed em seu loop e chamar exit se estiver definida. Nem todos os loops do Xv6 fazem essa verificação, o que pode atrasar o término.

Sobre os Bloqueios de Processo

O p->lock é um dos bloqueios mais críticos e multifuncionais do Xv6. Suas responsabilidades incluem:

• Proteger campos críticos como p->state, p->chan, p->killed, p->xstate e p->pid.
• Garantir que o processo não seja considerado RUNNABLE e escalonado antes de seu context estar completamente salvo.
• Prevenir que um processo ZOMBIE seja coletado pelo wait antes de ter liberado todos os seus recursos no kernel.
• Sincronizar ações entre sleep, wakeup e kill.

O campo p->parent é protegido pelo wait_lock global, e não pelo p->lock.

Considerações Finais

O escalonador do Xv6 implementa uma política simples de round-robin. Sistemas operacionais reais usam políticas muito mais complexas, considerando prioridades, justiça e throughput, o que pode levar a fenômenos como priority inversion e convoy effects.

Embora sleep/wakeup sejam simples e eficazes, outros sistemas operacionais usam abstrações como filas de espera (wait queues) e variáveis de condição (condition variables) para gerenciar a sincronização de forma mais explícita e, potencialmente, mais eficiente, evitando varreduras da tabela de processos.