❧ Escalonamento ❧

Introdução6.1

O escalonamento de processos é um dos pilares do gerenciamento de recursos em sistemas operacionais multiprogramados. Quando múltiplos processos ou threads competem pelo uso da Unidade Central de Processamento (CPU), o sistema operacional deve determinar a ordem e o tempo de alocação desse recurso crítico. Esta decisão, tomada pelo escalonador (scheduler) com base em um algoritmo de escalonamento, afeta diretamente o desempenho do sistema e a satisfação do usuário.

Como modelo conceitual, imagine que você é o gerente de um banco com um único caixa atendendo dezenas de clientes na fila. Sua decisão mais crítica não é como o caixa realiza as transações, mas quem atende primeiro. Um cliente com uma consulta rápida de saldo, se impedido por um cliente que precisa de uma hora para fechar um financiamento, ficará frustrado ao ponto de trocar de banco. O gerente toma uma decisão estratégica sobre a ordem de atendimento visando maximizar a satisfação geral.

O sistema operacional vive essa mesma situação continuamente. Como apenas uma instrução pode ser executada por vez (em um único núcleo), o S.O. deve tomar decisões ininterruptas sobre quem executa, quando, e por quanto tempo.

Nas aulas anteriores, estudamos processos e threads como entidades de execução, e depois como elas se comunicam e sincronizam com segurança. Agora, voltamos o olhar para a inteligência estratégica do S.O. ao gerenciar o tempo da CPU.

Por que o escalonamento importa?6.1.1

Você pode pensar: "Os computadores são tão rápidos hoje em dia, será que ainda importa quem executa primeiro?" A resposta depende do contexto:

Além de escolher o processo certo, o escalonador precisa ser eficiente por conta própria. Chavear de processo é caro: o estado atual deve ser salvo na tabela de processos, a MMU (unidade de gerenciamento de memória) deve ser reconfigurada, e o cache de memória pode ser invalidado. Chavear processos em excesso desperdiça CPU.

Comportamento de processos: CPU x E/S6.1.2

Antes de falar de algoritmos, precisamos entender o que os processos fazem. Quase todos eles alternam entre surtos de CPU (CPU bursts), que são períodos de cálculo intenso, e esperas de E/S (I/O waits), momentos em que ficam bloqueados aguardando disco, rede ou entrada do usuário.

Essa alternância cria dois perfis bem distintos:

À medida que as CPUs ficam cada vez mais rápidas, os processos tendem a ficar mais limitados pela E/S. O disco e a rede simplesmente não acompanham o ritmo da CPU. Isso torna o bom escalonamento de processos E/S-intensivos cada vez mais importante: devemos dar a eles a CPU rapidamente para que emitam sua próxima requisição de disco, mantendo o hardware ocupado.

Quando o escalonador age?6.1.3

O escalonador não é chamado aleatoriamente. Existem quatro momentos principais em que uma decisão de escalonamento é necessária. Primeiro, na criação de um novo processo, o escalonador decide se o pai ou o filho deve executar primeiro. Segundo, no término de um processo, o processo atual desaparece e outro deve ser escolhido da fila de prontos. Terceiro, quando um processo se bloqueia aguardando E/S ou sincronização, a CPU deve ser dada a outro. Por fim, quando ocorre uma interrupção de E/S e um dispositivo conclui seu trabalho, o processo que aguardava pode ter ficado pronto; o escalonador deve então decidir se deve privilegiá-lo imediatamente.

Preempção vs. Não-Preempção6.1.4

Com base nesses momentos, os algoritmos se dividem em duas grandes famílias:

Com base nesses momentos, os algoritmos se dividem em duas grandes famílias. Em algoritmos não-preemptivos, uma vez que o processo ganhou a CPU, ele a mantém até bloquear voluntariamente ou terminar. Já em algoritmos preemptivos, o escalonador pode retirar a CPU de um processo a qualquer momento, geralmente por interrupção de relógio, forçando-o a voltar à fila de prontos.

A preempção é essencial em sistemas interativos para evitar que um processo monopolize a CPU, tornando os outros irresponsivos. Em sistemas de tempo real, paradoxalmente, às vezes não é necessária, pois os próprios processos se liberam rapidamente.

Métricas de Desempenho6.2

Para avaliar a eficácia de um algoritmo de escalonamento, a literatura acadêmica define um conjunto rigoroso de métricas. As principais são:

• Tempo de Retorno ($T_{ret}$ ou Turnaround Time): É o tempo total decorrido desde o momento em que um processo chega ao sistema até o instante em que sua execução é concluída. Inclui o tempo de espera na memória, na fila de prontos, a execução na CPU e as operações de E/S.
  $$T_{ret} = T_{termino} - T_{chegada}$$

• Tempo de Espera ($T_{esp}$ ou Waiting Time): É o tempo total que um processo passa aguardando na fila de prontos. O tempo gasto executando na CPU ou bloqueado por E/S não é contabilizado. Uma forma simples de calcular (assumindo que não haja requisições extras de E/S) é:
  $$T_{esp} = T_{ret} - T_{burst}$$
  (Onde $T_{burst}$ é o tempo total de CPU que o processo necessita para concluir).

• Tempo de Resposta ($T_{resp}$ ou Response Time): Essencial em sistemas interativos, é o tempo decorrido desde a submissão de uma requisição até a primeira resposta do sistema (o momento em que o processo ganha a CPU pela primeira vez).
  $$T_{resp} = T_{primeira\_execucao} - T_{chegada}$$

• Vazão (Throughput): Mede o número de processos que concluem sua execução por unidade de tempo (ex: processos por segundo).

• Utilização da CPU: A fração de tempo em que a CPU está ocupada executando processos úteis, não incluindo a ociosidade do sistema. Em sistemas reais, busca-se manter a utilização entre 40% a 90%.

Ambientes e objetivos6.2.1

Os objetivos do escalonador dependem do ambiente onde o sistema opera. A taxonomia a seguir ilustra essas categorias e suas necessidades:

graph TD
    A[Sistemas Operacionais] --> B[Sistemas em Lote Batch]
    A --> C[Sistemas Interativos]
    A --> D[Sistemas de Tempo Real]
    B --> B1[Ex: Simulações, Processamento de Dados]
    C --> C1[Ex: Desktops, Servidores Web, Smartphones]
    D --> D1[Ex: Controle de Voo, Automotivo, Áudio/Vídeo]

graph TD
    A[Sistemas Operacionais] --> B[Sistemas em Lote Batch]
    A --> C[Sistemas Interativos]
    A --> D[Sistemas de Tempo Real]
    B --> B1[Ex: Simulações, Processamento de Dados]
    C --> C1[Ex: Desktops, Servidores Web, Smartphones]
    D --> D1[Ex: Controle de Voo, Automotivo, Áudio/Vídeo]

Cada um destes ambientes exige a otimização de métricas distintas:

graph LR
    A[Metas de Escalonamento] --> B[Todos]
    A --> C[Lote]
    A --> D[Interativo]
    A --> E[Tempo Real]
    B --> B1[Justiça fairness]
    B --> B2[Cumprimento de políticas]
    B --> B3[Equilíbrio de uso de recursos]
    C --> C1[Maximizar Vazão throughput]
    C --> C2[Minimizar Tempo de Retorno]
    C --> C3[Maximizar Utilização da CPU]
    D --> D1[Minimizar Tempo de Resposta]
    D --> D2[Proporcionalidade das expectativas]
    E --> E1[Cumprir Prazos rigorosamente]
    E --> E2[Previsibilidade]

graph LR
    A[Metas de Escalonamento] --> B[Todos]
    A --> C[Lote]
    A --> D[Interativo]
    A --> E[Tempo Real]
    B --> B1[Justiça fairness]
    B --> B2[Cumprimento de políticas]
    B --> B3[Equilíbrio de uso de recursos]
    C --> C1[Maximizar Vazão throughput]
    C --> C2[Minimizar Tempo de Retorno]
    C --> C3[Maximizar Utilização da CPU]
    D --> D1[Minimizar Tempo de Resposta]
    D --> D2[Proporcionalidade das expectativas]
    E --> E1[Cumprir Prazos rigorosamente]
    E --> E2[Previsibilidade]

Objetivos podem ser conflitantes. Maximizar a vazão (terminar mais tarefas por hora) pode significar ignorar tarefas longas em favor de muitas curtas, arruinando o tempo de retorno dessas tarefas longas. Um bom escalonador encontra o equilíbrio adequado para o contexto.

Algoritmos para Sistemas em Lote6.3

Sistemas em lote (batch) processam trabalhos sem interação direta do usuário. São comuns em bancos, sistemas de folha de pagamento, simulações científicas. Neles, um certo atraso no início de um trabalho é aceitável, mas a eficiência total importa muito.

Primeiro a Chegar, Primeiro a Ser Servido (FCFS)6.3.1

O algoritmo mais simples imaginável: a CPU é atribuída na ordem de chegada. Há uma única fila; quem chega primeiro, executa primeiro. O FCFS é de implementação trivial; basta uma fila encadeada. Processos desbloqueados retornam ao final da fila e a ordem é "quem chegou primeiro, serve primeiro", assemelhando-se a uma fila de banco tradicional.

O Problema do Comboio (Convoy Effect)6.3.1.1

Imagine um processo CPU-intensivo que roda por 20 ms. Atrás dele estão 3 processos E/S-intensivos que precisam de apenas 2 ms de CPU cada, mas bloqueiam no disco frequentemente. Enquanto o processo longo roda, o disco fica ocioso. Quando ele finalmente termina e os processos E/S tentam executar, a CPU fica ociosa enquanto eles esperam o disco (que agora está sobrecarregado). O sistema inteiro "soluça".

Exemplo de Cálculo Analítico6.3.1.2

Considere três processos chegando no instante 0 (zero), na ordem $P_1, P_2, P_3$:

Cálculo do Tempo de Espera ($T_{esp}$):

• $P_1$ é o primeiro, logo $T_{esp}(P_1) = 0$ ms.
• $P_2$ espera $P_1$ terminar, logo $T_{esp}(P_2) = 24$ ms.
• $P_3$ espera $P_1$ e $P_2$, logo $T_{esp}(P_3) = 24 + 3 = 27$ ms.
• Média: $(0 + 24 + 27) / 3 = 17$ ms.

Cálculo do Tempo de Retorno ($T_{ret}$):

• $P_1$ termina no instante 24. $T_{ret}(P_1) = 24 - 0 = 24$ ms.
• $P_2$ termina no instante 27. $T_{ret}(P_2) = 27 - 0 = 27$ ms.
• $P_3$ termina no instante 30. $T_{ret}(P_3) = 30 - 0 = 30$ ms.
• Média: $(24 + 27 + 30) / 3 = 27$ ms.

Se a ordem de chegada fosse $P_2, P_3, P_1$, a média do tempo de espera cairia drasticamente para $(0 + 3 + 6) / 3 = 3$ ms, ilustrando a principal fraqueza do FCFS.

Tarefa Mais Curta Primeiro (SJF - Shortest Job First)6.3.2

Sabendo antecipadamente o tempo de execução de cada tarefa, podemos fazer melhor. A ideia: execute a tarefa mais curta disponível primeiro.

Por que funciona? Matematicamente, o SJF minimiza o tempo de retorno médio quando todas as tarefas estão disponíveis simultaneamente.

Considerando quatro tarefas com tempos de 8, 4, 4 e 4 minutos, a ordem original (A, B, C, D) resultaria em tempos de retorno de 8, 12, 16 e 20 minutos, com média de 14 min. Já reordenando para SJF (B, C, D, A), os retornos caem para 4, 8, 12 e 20, reduzindo a média para 11 min, o que representa uma melhora de aproximadamente 21%.

Exemplo de Cálculo Analítico (SJF)6.3.2.1

Considere o seguinte conjunto de processos, assumindo que todos chegam no instante 0:

No escalonamento SJF, a ordem de execução será $P_4, P_1, P_3, P_2$.

• Tempos de Espera:
  • $P_4$: 0 ms (executa primeiro)
  • $P_1$: 3 ms (espera $P_4$)
  • $P_3$: $3 + 6 = 9$ ms (espera $P_4$ e $P_1$)
  • $P_2$: $3 + 6 + 7 = 16$ ms (espera os demais)
• Tempo de Espera Médio: $(0 + 3 + 9 + 16) / 4 = 7$ ms.

Se usássemos FCFS ($P_1, P_2, P_3, P_4$), o tempo médio de espera seria $(0 + 6 + 14 + 21) / 4 = 10,25$ ms. A ordenação do SJF comprova matematicamente a minimização do tempo de espera.

Uma redução de ~21% no tempo médio! A intuição é simples: cada tarefa que entra na fila aumenta o tempo de espera de todas as que vêm depois. Colocar as mais curtas na frente minimiza esse "dano coletivo".

O SJF é ótimo somente quando todas as tarefas estão disponíveis ao mesmo tempo. Se novas tarefas chegam durante a execução, a história muda. Além disso, saber o tempo de execução antecipadamente é possível em sistemas em lote, mas não em sistemas interativos (onde usamos estimativas).

Tempo Restante Mais Curto em Seguida (SRTN)6.3.3

É a versão preemptiva do SJF. Quando uma nova tarefa chega, seu tempo total é comparado com o tempo restante do processo atual. Se a nova tarefa for mais curta, o processo atual é suspenso e ela começa.

Exemplo Comparativo Analítico (SRTN vs SJF)6.3.3.1

Para demonstrar o impacto da preempção, considere processos chegando em tempos diferentes:

Cálculo com SJF Não-Preemptivo:

1. Em $t=0$, apenas $P_1$ está pronto. Ele roda até o fim (instante 8).
2. Em $t=8$, $P_2, P_3, P_4$ já chegaram. O menor é $P_2$ (4ms). Roda até $t=12$.
3. Em $t=12$, o menor é $P_4$ (5ms). Roda até $t=17$.
4. Em $t=17$, roda $P_3$ (9ms). Termina em $t=26$.

• Tempos de Retorno ($T_{termino} - T_{chegada}$): $P_1(8-0=8)$, $P_2(12-1=11)$, $P_3(26-2=24)$, $P_4(17-3=14)$. Média = 14,25 ms.

Cálculo com SRTN (Preemptivo):

1. Em $t=0$, $P_1$ inicia.
2. Em $t=1$, $P_2$ chega (precisa de 4). $P_1$ tem 7 restantes. $4 < 7$, então $P_2$ interrompe $P_1$.
3. Em $t=2$, $P_3$ chega (9). $P_2$ tem 3 restantes. $3 < 9$, então $P_2$ continua.
4. Em $t=3$, $P_4$ chega (5). $P_2$ tem 2 restantes. $2 < 5$, então $P_2$ continua e termina em $t=5$.
5. Em $t=5$, temos prontos: $P_1$ (restam 7), $P_3$ (restam 9), $P_4$ (restam 5). O menor é $P_4$. Roda até $t=10$.
6. Em $t=10$, o menor é $P_1$ (restam 7). Roda até $t=17$.
7. Em $t=17$, roda $P_3$ (9). Termina em $t=26$.

• Tempos de Retorno ($T_{termino} - T_{chegada}$): $P_1(17-0=17)$, $P_2(5-1=4)$, $P_3(26-2=24)$, $P_4(10-3=7)$. Média = 13 ms.

O SRTN reduziu o tempo de retorno médio através de interrupções estratégicas. No instante t=0, o Processo A (8 ms) começa a rodar. Dois milissegundos depois, em t=2, chega o Processo B (3 ms). Como A já rodou 2 ms e restam 6 ms, enquanto B precisa de apenas 3 ms, o escalonador interrompe A (3 < 6) e coloca B para rodar. B termina em t=5, momento em que A retoma e termina em t=11.

Algoritmos para Sistemas Interativos6.4

Em sistemas interativos (desktops, servidores, smartphones), o usuário está presente e espera respostas rápidas. Aqui, a preempção é fundamental e o tempo de resposta é a métrica mais importante.

Escalonamento Circular (Round-Robin)6.4.1

Um dos algoritmos mais antigos, simples, justos e amplamente usados. A ideia central: Cada processo recebe um quantum de tempo (fatia de CPU). Se não terminar dentro do quantum, é suspenso e vai para o final da fila de prontos.

Exemplo de Cálculo Analítico (Round-Robin)6.4.1.1

Considere três processos que chegam em $t=0$:

Vamos adotar um Quantum = 4 ms e ignorar o overhead de chaveamento para facilitar as contas.

• Execução:

  • $P_1$ ganha a CPU. Roda 4 ms e é interrompido. Restam 20 ms. ($t=4$)
  • $P_2$ ganha a CPU. Precisa de 3 ms e termina antes do quantum acabar. ($t=7$)
  • $P_3$ ganha a CPU. Precisa de 3 ms e termina. ($t=10$)
  • $P_1$ é o único restante e roda em fatias sucessivas até terminar em $t=30$.

• Cálculo do Tempo de Resposta ($T_{primeira\_exec} - T_{chegada}$):

  • $P_1$: $0 - 0 = 0$ ms.
  • $P_2$: $4 - 0 = 4$ ms.
  • $P_3$: $7 - 0 = 7$ ms.
  • Tempo de Resposta Médio: $(0 + 4 + 7) / 3 = 3,66$ ms.

Apesar de o tempo médio de retorno ser maior no Round-Robin comparado ao SJF, o tempo de resposta é substancialmente menor e mais justo, que é a métrica crítica em sistemas interativos.

A questão crítica: qual o tamanho ideal do quantum?

Este é o trade-off central do Round-Robin:

Um quantum entre 20 e 50 ms é geralmente razoável na prática. O overhead de chaveamento (tipicamente < 1 ms) torna-se uma fração pequena, enquanto processos interativos curtos respondem em um ciclo de fila.

Se o quantum for maior que o surto médio de CPU dos processos, a maioria dos processos se bloqueará voluntariamente (por E/S) antes do quantum expirar. O chaveamento ocorrerá por razão lógica, e a preempção se tornará rara. Isso é desejável!

Escalonamento por Prioridades6.4.2

O Round-Robin assume que todos os processos são igualmente importantes. Mas isso nem sempre é verdade: um servidor de vídeo em tempo real é claramente mais urgente que uma tarefa de backup noturno.

Ideia básica: cada processo recebe uma prioridade. O processo executável com a prioridade mais alta é escalonado primeiro.

O problema da inanição (starvation) surge quando processos de alta prioridade continuam chegando e os de baixa prioridade nunca executam, pois ficam morrendo de fome na fila. A solução clássica é o envelhecimento (aging): a cada quantum que um processo permanece esperando sem executar, sua prioridade é incrementada gradualmente pelo sistema operacional, garantindo que ele eventualmente chegue ao topo da fila.

As prioridades podem ser estáticas, que são definidas na criação do processo e imutáveis (como em sistemas militares, onde generais têm prioridade fixa sobre soldados), ou dinâmicas, ajustadas pelo S.O. em tempo de execução. Projetistas costumam privilegiar processos E/S-intensivos com prioridades dinâmicas mais altas para manter o hardware de E/S ocupado.

Um truque elegante para prioridades dinâmicas é definir a prioridade como $1/f$, onde $f$ é a fração do quantum que o processo utilizou da última vez. Assim, um processo que usou apenas 1 ms de um quantum de 50 ms recebe prioridade máxima, enquanto um que esgotou o quantum inteiro recebe a prioridade mínima.

Muitos sistemas combinam Round-Robin com prioridades: processos são agrupados em classes de prioridade, e dentro de cada classe o escalonamento é circular. Se a classe mais alta tem processos, as classes baixas esperam.

O sistema CTSS do MIT foi pioneiro aqui, mas com uma variação inteligente para reduzir o custo de chaveamento (que envolvia disco): processos de alta prioridade recebiam 1 quantum, os de segunda classe recebiam 2, os de terceira recebiam 4, e assim por diante. Um processo CPU-intensivo gradualmente afundava nas classes e recebia fatias maiores, mas menos frequentes. Se ele de repente ficasse interativo, ele subia de volta ao topo.

Acertar a política de escalonamento na prática é muito mais difícil do que definir a teoria. Um engenheiro do MIT descobriu que apertar Enter aleatoriamente no terminal melhorava drasticamente o tempo de resposta de seu processo CPU-intensivo; a política havia sido "hackeada" de forma não intencional, pois o sistema via a entrada de teclado como prova de interatividade.

Processo Mais Curto em Seguida (Shortest Process Next)6.4.3

No sistema em lote, o SJF minimiza o tempo de resposta médio. Seria ótimo aplicar o mesmo princípio aos sistemas interativos. O desafio é que não sabemos o tempo de execução futuro.

Solução: estimar com base no histórico, usando a técnica de envelhecimento (aging):

$$T_{estimado} = \alpha \cdot T_{anterior} + (1 - \alpha) \cdot T_{medido}$$

Onde $\alpha$ controla o "peso da memória". Com $\alpha = 1/2$:

$$T_{novo} = \frac{T_{velho} + T_{medido}}{2}$$

Isso pode ser implementado com um simples deslocamento de bits! As últimas medições têm maior peso, e o passado distante pesa exponencialmente menos. A estimativa se adapta ao comportamento atual do processo.

Escalonamento Garantido6.4.4

Uma abordagem radicalmente diferente: faça promessas e cumpra-as.

Com $n$ processos rodando, cada um recebe exatamente $1/n$ da CPU. O S.O. rastreia quanto de CPU cada processo já recebeu e quanto merecia receber. O processo com o menor índice (CPU_recebida / CPU_merecida) é sempre o próximo a executar.

Escalonamento por Loteria6.4.5

Uma abordagem probabilística elegante: distribua bilhetes de loteria (tickets) para os processos. A cada decisão de escalonamento, sorteie um bilhete. O dono ganha a CPU.

Uma abordagem probabilística elegante: distribua bilhetes de loteria (tickets) para os processos. A cada decisão de escalonamento, sorteie um bilhete; o dono ganha a CPU.

O escalonamento por loteria tem propriedades excelentes: é proporcional por construção (um processo com 20% dos bilhetes recebe ~20% da CPU a longo prazo), responsivo (novos processos competem imediatamente), cooperativo (processos podem ceder bilhetes a outros, como um cliente cedendo ao servidor) e flexível (processos importantes simplesmente recebem mais bilhetes). Diferente do escalonamento por prioridades, onde é difícil quantificar a diferença entre os níveis, na loteria a semântica é clara, um processo com uma fração $f$ dos bilhetes recebe exatamente a fração $f$ da CPU.

E quando usuários diferentes têm números diferentes de processos? Com Round-Robin puro, um usuário com 9 processos recebe 90% da CPU enquanto outro com apenas 1 processo recebe 10%, mesmo que ambos devessem ter participação igual.

Fair-Share aloca a CPU por usuário, não por processo. Cada usuário recebe sua fração, independentemente de quantos processos tenha criado.

Exemplo: Usuário 1 tem 4 processos (A, B, C, D), Usuário 2 tem 1 processo (E), ambos com 50% de participação. Uma sequência justa seria:

A E B E C E D E A E B E C E D E ...

Algoritmos para Sistemas de Tempo Real6.5

Sistemas de tempo real são aqueles onde o tempo de resposta tem validade. Um dado correto que chega tarde pode ser tão inútil quanto um dado errado.

Sistemas de tempo real são aqueles onde o tempo de resposta tem validade. Um dado correto que chega tarde pode ser tão inútil quanto um dado errado.

Existem dois tipos fundamentais de tempo real. No Tempo Real Crítico (Hard Real-Time), os prazos são absolutos e nunca podem ser violados; uma falha de milissegundos num sistema de controle de voo ou num pace-maker pode custar vidas. Já no Tempo Real Não-Crítico (Soft Real-Time), perder um prazo esporadicamente é indesejável, mas tolerável; um frame atrasado num streaming de vídeo gera apenas um pequeno "engasgo", sem desastre.

Eventos em tempo real podem ser periódicos, ocorrendo em intervalos regulares (como a leitura de um sensor a cada 10 ms), ou aperiódicos, surgindo de forma imprevisível (como o clique de um botão de parada de emergência).

Condição de Escalonabilidade: Com $m$ eventos periódicos, onde o evento $i$ ocorre com período $P_i$ e precisa de $C_i$ segundos de CPU, o sistema é escalonável se:

$$\sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1$$

O sistema é escalonável! Sobraram 15% de folga. Se adicionarmos um quarto evento com período de 1 segundo, ele pode usar no máximo 150 ms (0,15 de folga).

Política vs. Mecanismo6.6

Uma distinção fundamental na arquitetura de escalonamento é separar o que o escalonador faz de como ele é configurado:

Uma distinção fundamental na arquitetura de escalonamento é separar o mecanismo, que é o algoritmo propriamente dito (como prioridades ou Round-Robin), e a política, composta pelos parâmetros que controlam esse algoritmo (como quais valores de prioridade atribuir a cada processo).

Separar os dois permite que o núcleo forneça a ferramenta, mas deixe a estratégia para os processos de usuário. Por exemplo, um processo pai pode conhecer melhor qual de seus filhos é mais urgente do que o S.O. O núcleo fornece uma chamada de sistema para que o pai defina as prioridades, sem que o escalonador precise entender nada sobre a lógica da aplicação (ex: qual thread é um banco de dados e qual é um log).

Escalonamento de Threads6.7

Quando processos possuem múltiplos threads, surge um novo nível de complexidade. O comportamento difere drasticamente dependendo de onde os threads são gerenciados:

Threads de Usuário6.7.1

O núcleo não sabe que existem threads dentro do processo. Ele escolhe um processo (ex: Processo A) e lhe dá um quantum completo. O sistema de tempo de execução dentro desse processo decide qual thread rodar.

sequenceDiagram
    participant Núcleo
    participant Proc_A
    participant A1
    participant A2
    participant A3
    participant Proc_B
    Núcleo->>Proc_A: Quantum de 50ms
    Proc_A->>A1: 5ms
    A1-->>Proc_A: cede voluntariamente
    Proc_A->>A2: 5ms
    A2-->>Proc_A: cede voluntariamente
    Proc_A->>A3: 5ms
    A3-->>Proc_A: cede voluntariamente
    Note over Proc_A: ... repete A1, A2, A3 ...
    Proc_A-->>Núcleo: quantum expirou
    Núcleo->>Proc_B: próximo quantum

sequenceDiagram
    participant Núcleo
    participant Proc_A
    participant A1
    participant A2
    participant A3
    participant Proc_B
    Núcleo->>Proc_A: Quantum de 50ms
    Proc_A->>A1: 5ms
    A1-->>Proc_A: cede voluntariamente
    Proc_A->>A2: 5ms
    A2-->>Proc_A: cede voluntariamente
    Proc_A->>A3: 5ms
    A3-->>Proc_A: cede voluntariamente
    Note over Proc_A: ... repete A1, A2, A3 ...
    Proc_A-->>Núcleo: quantum expirou
    Núcleo->>Proc_B: próximo quantum

Limitação: A sequência A1, B1, A2, B2 (intercalando threads de processos diferentes) é impossível com threads de usuário. O núcleo não intercala threads de processos distintos, apenas processos.

Threads de Núcleo6.7.2

O núcleo sabe de cada thread e os escalona individualmente. Ele pode intercalar threads de processos diferentes: A1, B1, A2, B2 se torna possível.

sequenceDiagram
    participant Núcleo
    participant A1
    participant B1
    participant A2
    participant B2
    Núcleo->>A1: 5ms
    Núcleo->>B1: 5ms
    Núcleo->>A2: 5ms
    Núcleo->>B2: 5ms

sequenceDiagram
    participant Núcleo
    participant A1
    participant B1
    participant A2
    participant B2
    Núcleo->>A1: 5ms
    Núcleo->>B1: 5ms
    Núcleo->>A2: 5ms
    Núcleo->>B2: 5ms

Na prática, a maioria dos sistemas modernos (como o Linux) utiliza threads de núcleo mapeadas 1:1, onde a biblioteca pthreads cria uma tarefa real no kernel para cada thread da aplicação. Contudo, linguagens modernas como Go implementam o modelo híbrido (M:N): milhares de "goroutines" (threads de usuário) são multiplexadas sobre um número menor de threads de núcleo, unindo a leveza do chaveamento local com a robustez do kernel.

Um servidor web com threads de usuário pode usar um escalonador customizado que sempre prioriza o thread despachante após um worker bloquear. O núcleo jamais teria esse conhecimento semântico sobre o papel de cada thread dentro da aplicação.

Comparativo Final dos Algoritmos6.8

Antes de avançarmos para as questões, consolide seus conhecimentos simulando os algoritmos de forma interativa. O applet abaixo permite configurar processos, tempos de chegada e duração para visualizar os resultados em gráficos de Gantt e comparar as métricas discutidas.

Questões6.9

1. Um sistema tem três processos prontos: A (precisa de 12 ms), B (precisa de 4 ms) e C (precisa de 8 ms), todos chegando ao mesmo tempo. Calcule o tempo de retorno médio para cada algoritmo:

• a) FCFS na ordem A → B → C.
• b) FCFS na ordem B → C → A.
• c) SJF com todos simultaneamente disponíveis.
• d) Round-Robin com quantum de 4 ms (ordem de chegada A, B, C). Mostre a linha do tempo de execução passo a passo.
• e) Qual dos algoritmos produz o menor tempo de retorno médio? Por quê?

2. Sobre preempção e seus impactos, assinale a alternativa correta:

• A) No algoritmo FCFS, um processo de alta prioridade que chega tarde pode imediatamente interromper o processo em execução.
• B) O SJF não-preemptivo é ótimo para minimizar o tempo de retorno médio quando todas as tarefas chegam simultaneamente, pois cada tarefa curta na frente reduz o tempo de espera de todas as subsequentes.
• C) O escalonamento Round-Robin é preemptivo, mas um processo que bloqueia voluntariamente (por E/S) antes do quantum expirar desperdicia o tempo restante do seu quantum para sempre.
• D) O algoritmo SRTN não sofre de starvation pois trata igualmente processos curtos e longos.

3. Relacione cada cenário da Coluna A com o algoritmo de escalonamento mais adequado da Coluna B:

4. O sistema CTSS do MIT implementava múltiplas filas de prioridade onde processos CPU-intensivos "desciam" de classe ao longo do tempo e recebiam quanta maiores, mas menos frequentes. Um engenheiro descobriu que apertar Enter aleatoriamente no terminal "hackeava" o sistema, elevando seu processo de volta à classe mais alta.

• a) Por que apertar Enter no terminal causava esse efeito no CTSS?
• b) Qual princípio de projeto esse tipo de vulnerabilidade demonstra ser difícil de acertar?
• c) Como o conceito de Política vs. Mecanismo poderia ter ajudado os projetistas a evitar esse tipo de bug?

5. Sobre o escalonamento por Loteria, analise as afirmativas e julgue-as como Verdadeiras (V) ou Falsas (F):

• ( ) Um processo com 30 bilhetes em um sistema com 100 bilhetes no total receberá exatamente 30% da CPU a cada segundo.
• ( ) Processos cooperativos podem transferir bilhetes entre si, o que é útil quando um cliente espera a resposta de um servidor.
• ( ) O escalonamento por loteria é altamente responsivo: um novo processo que recebe bilhetes passa a competir no próximo sorteio.
• ( ) O principal problema do escalonamento por loteria é que é matematicamente impossível garantir que todos os processos receberão pelo menos algum tempo de CPU.

6. Um sistema de tempo real tem os seguintes processos periódicos:

• a) Calcule a carga total da CPU e verifique se o sistema é escalonável.
• b) Se adicionarmos um processo P4 com período de 500 ms, qual é o tempo máximo de CPU que P4 pode exigir para que o sistema permaneça escalonável?
• c) Um sistema de tempo real crítico (hard real-time) que falha repetidamente em cumprir prazos sofre de que problema fundamental? Qual seria a consequência num sistema de controle de voo?

7. Compare o escalonamento de threads de usuário com threads de núcleo. Para cada cenário abaixo, indique qual modelo seria preferível e justifique em uma frase:

• a) Um servidor web onde centenas de requisições chegam simultaneamente e muitas bloqueiam por E/S de disco.
• b) Um simulador financeiro com 1.000 threads que realizam cálculos intensivos sem E/S, e onde o custo de criação/chaveamento de threads impacta a performance.
• c) Um sistema onde a aplicação precisa de um escalonador customizado que usa conhecimento semântico sobre a função de cada thread (ex: priorizar despachantes sobre trabalhadores).

8. (Questão Visual: Gantt) Observe o diagrama de Gantt abaixo referente a três processos (P1, P2, P3) que chegam no instante $t=0$:

• a) Qual algoritmo de escalonamento foi utilizado (considerando que todos chegaram juntos)?
• b) Calcule o tempo de retorno (turnaround) médio para esse cenário.

9. (Desafio em Sala) No gráfico de Round-Robin: Eficiência vs. Responsividade apresentado na aula, se o custo de chaveamento de contexto aumentasse de 1 ms para 5 ms (devido a um hardware mais lento), como as curvas de Eficiência e Latência se deslocariam? O "ponto ideal" de quantum se moveria para a esquerda ou para a direita? Justifique.

10. (Cenário Fair-Share) Dois usuários em uma universidade dividem um servidor. O Usuário A tem 8 processos ativos (compilações pesadas) e o Usuário B tem apenas 2 processos (editores de texto). O S.O. utiliza Escalonamento por Fração Justa (Fair-Share) com divisão de 50% para cada usuário.

• a) Qual a porcentagem de CPU que cada processo do Usuário A receberá, em média? E do Usuário B?
• b) Se o algoritmo fosse Round-Robin puro (ignorando os usuários), qual seria a divisão de CPU por processo?
• c) Explique por que o Usuário B prefere o Fair-Share e por que o Usuário A pode achar que o sistema está "ocioso" mesmo quando ele tem muito trabalho a fazer.

11. (SJF vs SRTN) Um servidor recebe quatro tarefas no instante t=0 com durações (10, 2, 3, 1). No instante t=2, chega uma nova tarefa curta de duração 1.

• a) Qual seria o tempo de retorno médio se usássemos SJF (não-preemptivo)?
• b) E se usássemos SRTN (preemptivo)?
• c) Em que caso a preempção do SRTN é prejudicial ao sistema?

12. (Escalonamento Garantido) Um sistema com 3 processos promete 33% da CPU a cada um.

• Processo X recebeu 20% da CPU até agora.

• Processo Y recebeu 40%.

• Processo Z recebeu 40%.

  • a) Qual processo o escalonador garantido escolherá para rodar agora? Justifique com o cálculo do índice de merecimento.

Próximos passos6.10

Na próxima aula, exploraremos o fenômeno dos 7 - deadlocks, o derradeiro "nó cego" da sincronização. Estudaremos como processos ficam permanentemente bloqueados ao disputar recursos, as quatro condições fundamentais de Coffman e as estratégias que os sistemas operacionais modernos utilizam para detectar, evitar ou prevenir esse colapso.