Sistemas operacionais

Introdução, conceitos e chamadas de sistema

Pense em um restaurante. Você (o programa do usuário) senta em uma mesa. A cozinha (o hardware) é perigosa: facas, fogo, óleo quente. Você nunca entra. Você diz ao garçom o que quer, e o garçom fala com a cozinha. O sistema operacional é o garçom e o gerente ao mesmo tempo.

Há duas maneiras de olhar para o sistema operacional, e as duas são verdadeiras:

• Máquina estendida (olhando de cima para baixo): o hardware real é desajeitado. Um disco só sabe 'ler o setor 4.821'. O SO esconde isso e oferece ideias agradáveis como arquivos e processos. Ele torna o computador mais fácil de usar.
• Gerenciador de recursos (olhando de baixo para cima): a CPU, a memória e os dispositivos são compartilhados por vários programas. O SO divide tudo de forma justa e segura, no tempo (cada um na sua vez) e no espaço (cada programa recebe a sua parte).

Modo kernel e modo usuário

O kernel precisa ser protegido contra erros de programas comuns. Por isso a CPU tem pelo menos dois modos, como uma porta com um guarda.

As instruções perigosas são as privilegiadas: desligar interrupções, fazer entrada e saída direto em um dispositivo e mudar as tabelas de páginas (os mapas que decidem qual memória um programa enxerga). Só o kernel pode fazer isso. Contas comuns, como somar dois números, são permitidas em qualquer modo.

Chamadas de sistema: pedir um serviço ao kernel

Um programa que quer ler um arquivo não pode tocar no disco. Ele faz uma chamada de sistema (system call), que é um pedido educado ao kernel. Uma instrução especial (a trap) muda a CPU para o modo kernel e salta para um lugar fixo do SO. O SO faz o trabalho e depois volta ao modo usuário.

programa:   read(fd, buf, n)           <- chamada normal
      |
biblioteca: põe o número da chamada num registrador
           TRAP  ------------------------+   <- o modo muda AQUI
                                         v
kernel:    usa o número como índice numa tabela de rotinas
           faz o trabalho (lê o arquivo)
           volta ao modo usuário  -------+
      ^                                  |
programa continua  <---------------------+

Repare que chamar read é só uma chamada de função normal para uma biblioteca. O modo só muda na instrução trap dentro dessa função da biblioteca.

fork, exec e o shell

No UNIX, criar um processo novo e carregar um programa novo são dois passos separados. fork faz uma cópia do processo que chamou. A cópia continua no mesmo ponto, logo depois do fork. fork devolve 0 no filho e o número do filho (o PID) no pai, então cada um sabe quem é. exec troca o programa que o processo está rodando por outro programa.

fork();
fork();
printf("hi\n");
/* 1 processo -> 2 -> 4 processos: 2^n depois de n forks,
   então isto imprime "hi" 4 vezes */

Como os dois passos são separados, o filho pode mudar coisas entre eles, por exemplo redirecionar a entrada e a saída. É exatamente assim que um shell faz ls > arquivo.txt e pipes. Cada processo também tem o seu próprio diretório atual, herdado do pai. Por isso comandos que precisam mudar o próprio shell, como cd e exit, são embutidos (builtins) no shell: se o cd rodasse em um filho, só o filho mudaria de pasta.

Como o kernel é organizado

Um pouco de história

Nos primeiros sistemas em lote (batch), a CPU cara ficava parada sempre que um job esperava uma entrada ou saída lenta. A multiprogramação resolveu isso: a memória é dividida em partes, vários jobs ficam carregados e, quando um bloqueia, a CPU passa para outro. O tempo compartilhado (timesharing) acrescentou trocas muito rápidas para que muitos usuários trabalhassem de forma interativa ao mesmo tempo.

Processos e threads

Uma receita de bolo está escrita no papel. Sozinha, ela não faz nada. Quando alguém realmente faz o bolo, seguindo a receita, medindo e misturando, essa atividade é o que importa. Um programa é a receita, uma lista de instruções guardada. Um processo é o ato de fazer o bolo: um programa em execução, com o seu passo atual (o contador de programa), as suas variáveis e os seus arquivos abertos. Rode o mesmo programa duas vezes e você terá dois processos diferentes, como dois cozinheiros fazendo bolos da mesma receita.

Os três estados

A cada momento um processo está em um de três estados:

• Executando (running): está usando a CPU agora.
• Pronto (ready): poderia rodar, mas a CPU está ocupada com outro processo. Ele espera a sua vez.
• Bloqueado (blocked): não pode rodar até que algo de fora aconteça, como uma tecla pressionada ou um disco terminar.

              1: espera um evento
   +-----------+ -----------------> +-----------+
   | EXECUTANDO|                    | BLOQUEADO |
   +-----------+ <-+                +-----------+
     | ^           |                      |
 2:  | | 3:        |                      | 4: o evento
tempo| | escalonador                      | aconteceu
acaba| | escolhe                          |
     v |                                  |
   +---------+ <------------------------+
   | PRONTO  |
   +---------+

Pronto e bloqueado diferem no motivo pelo qual o processo não está rodando. Um processo pronto só espera o escalonador. Um processo bloqueado espera um evento, então dar a CPU a ele seria inútil. A causa usual de executando para pronto é a interrupção do relógio encerrando a vez do processo.

Como um processo começa e termina

Um processo termina de quatro maneiras. Duas são voluntárias: a saída normal e a saída por erro que o próprio programa detecta (por exemplo 'arquivo não encontrado'). Duas são involuntárias: um erro fatal causado por um bug (como dividir por zero) e ser morto por outro processo.

Quando um processo termina, o kernel libera os recursos dele, mas guarda o código de saída para o pai poder lê-lo com wait. Até o pai fazer isso, o filho é um zumbi: acabou, mas ainda ocupa uma linha na tabela de processos. Um pai que nunca chama wait acumula zumbis.

Depois do fork, o filho tem uma cópia da memória do pai. Dali em diante eles são independentes: se o filho muda uma variável, o pai não vê. Para compartilhar dados é preciso algo explícito, como um pipe, um arquivo ou memória compartilhada. Copiar tudo seria lento, então os sistemas modernos usam copy-on-write (cópia na escrita): pai e filho compartilham as mesmas páginas (marcadas como somente leitura), e uma página só é copiada quando um dos dois escreve nela.

int x = 5;
pid_t pid = fork();
if (pid == 0) { x = 10; exit(0); }   /* o filho muda a SUA cópia */
waitpid(pid, NULL, 0);
printf("%d\n", x);                    /* o pai ainda vê 5 */

Threads

Um processo é como uma casa: ele é dono dos cômodos (espaço de endereçamento), dos móveis (variáveis globais) e das chaves (arquivos abertos). Uma thread é uma pessoa que mora na casa fazendo a sua própria tarefa. Várias threads compartilham a casa, mas cada uma tem o seu próprio caderno do que está fazendo.

Trocar entre duas threads do mesmo processo é mais barato do que trocar entre dois processos, porque o mapa de memória continua o mesmo e a TLB e os caches continuam úteis. Threads também são um bom jeito de escrever programas que fazem várias coisas ao mesmo tempo, por exemplo um servidor web em que cada requisição tem a sua thread e pode esperar o disco enquanto as outras continuam trabalhando.

Threads de usuário, threads de kernel

As scheduler activations tentam pegar o melhor dos dois: o kernel dá ao processo processadores virtuais e faz um upcall para a biblioteca de usuário quando algo importante acontece (uma thread bloqueia, uma entrada ou saída termina). A escolha de qual thread roda continua no espaço do usuário.

Três jeitos de construir um servidor e uma armadilha do código antigo

• Threads: paralelismo com chamadas bloqueantes simples.
• Um único fluxo, bloqueante: simples, mas sem paralelismo.
• Máquina de estados finitos com chamadas não bloqueantes e um laço de eventos: paralelo, mas o programador precisa simular à mão as threads e suas pilhas, o que é difícil.

Comunicação entre processos e sincronização

Imagine duas crianças escrevendo ao mesmo tempo na mesma página de um caderno compartilhado. Se as duas escrevem 'o placar é' e depois cada uma acrescenta um número, a página vira uma bagunça. Quando programas compartilham dados e pelo menos um deles escreve, o resultado pode depender do tempo exato. Isso é uma condição de corrida (race condition). É desagradável porque acontece raramente e quase não dá para repetir quando se quer.

A atualização perdida

A linha count = count + 1 parece um passo, mas são três: carregar o valor em um registrador, somar um, guardar de volta. Se uma troca acontece entre o carregar e o guardar, uma atualização pode sumir.

count = 0
Thread A            Thread B
load  (0)
                    load  (0)
add   (1)
                    add   (1)
store (1)
                    store (1)   <- count final = 1, não 2!

Regiões críticas e as quatro condições

A parte do código que mexe em dados compartilhados é a região crítica. A cura é a exclusão mútua: só um processo lá dentro por vez, como uma chave para um banheiro. Uma boa solução precisa de quatro coisas:

1. Nunca dois processos dentro da região crítica ao mesmo tempo.
2. Nenhuma suposição sobre a velocidade ou o número de CPUs.
3. Um processo fora da sua região crítica não pode bloquear outro.
4. Ninguém espera para sempre.

Repare que uma promessa sobre a ordem de entrada não está na lista.

Soluções com espera ocupada

• Alternância estrita: uma variável turn diz de quem é a vez. Ela garante exclusão mútua, mas quebra a condição 3: um processo rápido precisa esperar um lento mesmo que o lento esteja longe da região crítica. Também gasta CPU girando em um laço (espera ocupada).
• A solução de Peterson corrige isso acrescentando uma bandeira 'tenho interesse' por processo.
• Uma simples variável de trava falha por causa do intervalo entre testar a trava e marcá-la: dois processos podem vê-la livre. As instruções de hardware TSL (test and set lock) e XCHG fazem as duas ações como um único passo atômico, então o intervalo desaparece. Uma trava feita assim e esperada em um laço é um spin lock.

Semáforos

Um semáforo é um contador com duas ações atômicas. down (também chamada P ou wait): se o contador é maior que zero, subtrai um e continua; se é zero, vai dormir. up (V ou signal): se alguém está dormindo, acorda um; senão soma um. Como verificar, mudar e dormir são uma ação indivisível, um acordar nunca se perde.

Um semáforo iniciado em 1 funciona como mutex (uma trava). Um semáforo iniciado em N deixa N processos entrarem, o que controla um conjunto de N recursos iguais. Se começa em 3 e cinco processos fazem down, três passam e dois dormem. Um up acorda um dos dois.

Produtor e consumidor

Um produtor coloca itens em um buffer de N posições; um consumidor os tira. Três semáforos resolvem: mutex (começa em 1, protege o buffer), empty (começa em N, conta as posições livres) e full (começa em 0, conta as posições ocupadas).

produtor:               consumidor:
  down(&empty);           down(&full);
  down(&mutex);           down(&mutex);
  put(item);              item = take();
  up(&mutex);             up(&mutex);
  up(&full);              up(&empty);

Monitores e variáveis de condição

Um monitor é um grupo de dados e procedimentos em que a linguagem garante que só um processo está lá dentro por vez. Para esperar uma condição, um processo faz wait em uma variável de condição, o que o bloqueia e deixa outros entrarem. Um signal acorda quem espera. Diferença para o semáforo: um signal não é lembrado. Se ninguém está esperando, ele se perde. Então quem espera precisa testar a condição (guardada em variáveis comuns) dentro do monitor, e o wait precisa vir antes do signal.

Leitores e escritores

Muitos leitores podem ler os mesmos dados juntos, mas um escritor precisa dos dados sozinho. Se leitores são sempre admitidos enquanto outros estão lendo, um escritor pode esperar para sempre (starvation, inanição). A alternativa justa faz os novos leitores esperarem atrás de um escritor que está esperando, com um pouco menos de concorrência.

Troca de mensagens

Processos também podem conversar com send e receive, sem memória compartilhada. Com caixas de correio (mailboxes), as mensagens esperam em um buffer até serem lidas. Sem nenhum buffer (rendezvous, usado pelo MINIX 3), quem chega primeiro bloqueia até o outro estar pronto, e a mensagem é copiada direto. É simples, mas amarra o ritmo dos dois lados.

Escalonamento

Muitos processos estão prontos, mas há só uma CPU (ou poucas). Quem vai agora? A parte do SO que decide é o escalonador (scheduler), como um professor escolhendo quem pode usar o único computador da sala. Lugares diferentes querem coisas diferentes.

Escalonadores preemptivos podem tirar a CPU de um processo usando a interrupção do relógio, para que ninguém a monopolize. Isso é vital para sistemas interativos. Escalonadores não preemptivos deixam o processo rodar até bloquear ou terminar. São mais simples e têm menos trocas de contexto, o que serve bem para trabalho em lote.

Palavras para conhecer

• Tempo de retorno (turnaround): da chegada de um job até ele terminar.
• Tempo de espera: tempo na fila de prontos, sem rodar.
• Tempo de resposta: de um pedido até a primeira resposta.
• Quantum: a fatia de tempo dada a um processo no round-robin.

Primeiro a chegar, primeiro a ser servido (FCFS)

Os jobs rodam até o fim na ordem de chegada, como uma fila na cantina. O tempo de espera de um job é a soma dos tempos de execução dos jobs à frente dele. Se um job longo vem primeiro, todos os curtos esperam atrás dele: o efeito comboio.

Job mais curto primeiro (SJF)

Se todos os jobs estão presentes no começo, rodar o mais curto primeiro dá o melhor tempo médio possível de retorno e de espera, porque o tempo do primeiro job é contado em todos os outros. O problema: é preciso conhecer ou estimar os tempos de execução.

Jobs chegam juntos com tempos de CPU  A=6   B=3   C=3

FCFS  |AAAAAA|BBB|CCC|   esperas: A0 B6 C9 -> média 5
SJF   |BBB|CCC|AAAAAA|   esperas: B0 C3 A6 -> média 3

O menor tempo restante primeiro (SRTN) é o SJF com preempção: quando um job novo chega, compare o tempo total dele com o tempo restante do job em execução. Se o recém-chegado é mais curto, ele toma a CPU. Isso favorece ainda mais os jobs curtos, mas pode atrasar muito os longos.

Round-robin

Cada processo recebe um quantum e vai para o fim da fila. Um processo que precisa de menos que um quantum devolve a CPU quando termina. Para achar quando algo termina, simule a fila passo a passo.

X precisa de 4, Y precisa de 3, quantum = 2

tempo: 0   2   4   6   7
       |XX |YY |XX |Y  |
                 X acaba em 6, Y acaba em 7

• Quantum pequeno demais: resposta muito boa, mas a CPU perde tempo com trocas de contexto.
• Quantum grande demais (maior que o tempo que os processos usam antes de bloquear): o round-robin vira quase FCFS e pedidos curtos esperam.
• Um quantum de cerca de 20 a 50 ms é um compromisso comum.

Prioridades e inanição

Cada processo recebe uma prioridade, e o pronto de maior prioridade roda. Mas se o trabalho de alta prioridade nunca para, os de baixa prioridade podem sofrer inanição (starvation). A cura é mudar as prioridades com o tempo: baixar a prioridade de quem usou muita CPU ou subir a de quem esperou muito (aging, envelhecimento).

Filas multinível com realimentação

O sistema não sabe quais processos são interativos e quais devoram CPU. Então ele deixa que eles se revelem. Há classes; a classe de cima tem quantum 1, a seguinte 2, depois 4, e assim por diante. Um processo que usa o quantum inteiro desce uma classe. Um que bloqueia cedo fica no alto e é servido rápido. Os processos pesados em CPU afundam e rodam menos vezes, porém por mais tempo. Um processo que precisa de muita CPU é trocado só cerca de log2 dessa quantidade de vezes.

Tempo real

Um sistema de tempo real trata eventos periódicos. Se um evento custa C milissegundos de CPU a cada P milissegundos, ele usa a fração C/P da CPU. O conjunto só pode ser escalonado se a soma de C/P for no máximo 1 (supondo que a troca de contexto seja de graça). Algoritmos como o EDF (earliest deadline first, prazo mais próximo primeiro) conseguem escalonar qualquer conjunto que satisfaça isso. Exemplo: 20 ms a cada 100 ms (0,2) e 100 ms a cada 400 ms (0,25) dão 0,45, que cabe.

Gerenciamento de memória: paginação, TLB, substituição de páginas, segmentação

A memória é onde os programas em execução vivem. Dois grandes problemas: os programas não devem ler a memória uns dos outros, e um programa não deveria precisar caber inteiro na memória real. A solução é a memória virtual: cada processo enxerga os seus próprios endereços privados (endereços virtuais), e o hardware os traduz para endereços reais (endereços físicos).

Paginação

A memória virtual é cortada em pedaços iguais chamados páginas; a memória real é cortada em pedaços do mesmo tamanho chamados quadros de página (page frames), como uma estante com caixas todas do mesmo tamanho. Uma tabela de páginas diz qual quadro guarda cada página. Um endereço virtual tem duas partes: o número da página (bits altos) e o deslocamento (offset, bits baixos, o lugar dentro da página). A tradução troca o número da página pelo número do quadro e copia o deslocamento sem mudar.

Com páginas de 4096 bytes, o deslocamento tem 12 bits (2 elevado a 12 é 4096). Exemplo: endereço virtual 8200. Dividindo, página = 2 (2 x 4096 = 8192) e deslocamento = 8. Se a página 2 está no quadro 7, o endereço físico é 7 x 4096 + 8 = 28680.

endereço virtual 8200
+--------------------+--------------+
| número da página=2 | deslocamento 8 |
+--------------------+--------------+
         |                |
  tabela de páginas: 2 -> 7|
         v                v
+--------------------+--------------+
| número do quadro=7 | deslocamento 8 |  = 7*4096 + 8 = 28680
+--------------------+--------------+

Qual o tamanho da tabela de páginas?

Número de páginas virtuais = tamanho do espaço de endereçamento dividido pelo tamanho da página. Em bits: bits do endereço menos bits do deslocamento. Com endereços de 32 bits e páginas de 4 KB, 32 - 12 = 20, então 2^20 = 1.048.576 páginas. Uma tabela de um nível precisa de uma entrada por página virtual, usada ou não, o que dá cerca de um milhão de entradas para cada processo (4 MB com 4 bytes cada). Para endereços de 64 bits isso se torna impossível.

Uma tabela multinível resolve isso. A tabela de primeiro nível aponta para tabelas de segundo nível, e as entradas de regiões não usadas são só marcadas como ausentes. Com 10 + 10 + 12 bits: descarte os 12 bits do deslocamento; então os 10 bits de cima indexam a primeira tabela e os 10 bits seguintes indexam a segunda. Para o endereço 0x00C02010: os 10 bits de cima dão 3 (PT1 = 3), os 10 seguintes dão 2 (PT2 = 2) e o deslocamento é 0x010 = 16. Trocamos um pouco de tempo de tradução por uma grande economia de memória. Uma tabela de páginas invertida vai no sentido oposto: uma entrada por quadro físico, então ela cresce com a memória real. O preço é que a busca deixa de ser um índice direto, então se usa um hash do endereço virtual e a TLB faz a maior parte do trabalho.

Falhas de página e a entrada da tabela de páginas

Só algumas páginas estão na memória real. O bit presente/ausente de cada entrada diz se a página está carregada. Tocar uma página ausente causa uma trap chamada falha de página (page fault). O SO escolhe um quadro, carrega a página do disco, atualiza a tabela e reinicia a instrução. Outros bits ajudam: o bit R (referenciada: ligado quando a página é lida ou escrita) e o bit M (modificada ou suja, dirty: ligado na primeira escrita). Uma página suja precisa ser escrita no disco antes de o quadro ser reutilizado, enquanto uma página limpa pode simplesmente ser descartada, então os algoritmos preferem vítimas limpas.

A TLB

Ler a tabela de páginas na memória deixaria todo acesso duas vezes mais lento. Mas os programas usam poucas páginas por vez, então um pequeno cache rápido de traduções, a TLB (translation lookaside buffer), responde à maioria das perguntas. Em um acerto na TLB (hit) a resposta está ali. Em uma falha (miss) a tabela de páginas é lida e a entrada é carregada na TLB. O tempo efetivo é uma média ponderada: a consulta à TLB sempre acontece, e uma falha acrescenta um acesso à memória por nível da tabela.

Exemplo: acesso à memória 100 ns, consulta à TLB 10 ns, taxa de acerto 90%, tabela de um nível. Tempo efetivo = 10 + 100 + 0,10 x 100 = 120 ns. Quanto maior a taxa de acerto, mais perto de 110 ns (consulta mais um acesso).

Substituição de páginas

Quando a memória está cheia e uma página nova é necessária, alguma página precisa sair. Qual?

Exemplo com 3 quadros e referências 1, 2, 3, 1, 4, 1. FIFO: as páginas 1, 2, 3 são carregadas (3 faltas); o acerto em 1 não muda nada; o 4 remove a página 1 (a mais antiga) embora tenha acabado de ser usada; depois o 1 falta de novo. Total de 5 faltas. LRU: o 4 remove a página 2 (sem uso há mais tempo) e o último 1 é um acerto. Total de 4 faltas.

No algoritmo do relógio (clock) os quadros ficam em um círculo com um ponteiro. Em uma falta, se a página sob o ponteiro tem R = 0, ela é substituída. Se R = 1, o bit é zerado e o ponteiro avança. Uma página só sobrevive a uma volta inteira se for usada de novo nesse meio tempo.

Anomalia de Belady e thrashing

Você esperaria que mais quadros significassem menos faltas. Isso vale para os algoritmos de pilha (LRU, ótimo): as páginas mantidas com n quadros estão sempre dentro das mantidas com n+1. O FIFO não é um deles. Na sequência clássica 1,2,3,4,1,2,5,1,2,3,4,5 o FIFO dá 9 faltas com 3 quadros e 10 com 4. Essa surpresa é a anomalia de Belady.

O conjunto de trabalho (working set) de um processo é o conjunto de páginas que ele usa em uma janela de tempo recente. Se a memória não comporta os conjuntos de trabalho de todos os processos ativos, eles roubam páginas uns dos outros e a máquina passa o tempo trocando páginas em vez de trabalhar. Isso é thrashing. Sinais típicos: pouco uso da CPU, um disco de paginação quase sempre ocupado, muitos processos na memória. Colocar mais processos piora; a cura é o controle de carga, ou seja, reduzir o número de processos que competem pela memória (ou acrescentar memória).

Segmentação e listas de memória livre

Um segmento é uma unidade de tamanho variável que combina com o que o programa usa (código, pilha, uma tabela). Ele se encaixa bem, mas com o tempo a memória se enche de buracos pequenos entre os segmentos (efeito tabuleiro, ou fragmentação externa). A compactação junta os buracos, mas é cara. A paginação usa pedaços de tamanho fixo: qualquer quadro livre serve para qualquer página, e o desperdício fica só dentro da última página de uma região (fragmentação interna).

Para colocar um pedido de tamanho variável em uma lista de buracos: o first fit (primeiro que couber) pega o primeiro buraco grande o bastante (rápido). O best fit (melhor encaixe) pega o menor buraco grande o bastante (percorre tudo e deixa pedaços minúsculos inúteis). O worst fit (pior encaixe) pega o maior buraco, esperando que o resto continue útil. Exemplo: buracos de 10, 4, 25, 6, 15 KB em ordem de endereço, pedido de 5 KB. O first fit usa o de 10, o best fit usa o de 6, o worst fit usa o de 25. As simulações mostram que o first fit costuma ser tão bom quanto os outros.

Sistemas de arquivos

A memória é esquecida quando a energia acaba. Um sistema de arquivos é a maneira de o disco guardar informação por muito tempo, como arquivos (caixas com nome cheias de bytes) dentro de diretórios (pastas). O sistema operacional esconde o disco real, que só sabe 'me dê o bloco número 4.000', e oferece nomes e caminhos no lugar.

Abrindo um arquivo

Encontrar um arquivo é a parte cara: percorrer cada diretório do caminho, achar a descrição do arquivo e checar as permissões. Por isso o programa primeiro chama open. O SO faz esse trabalho uma vez e guarda o resultado em tabelas do kernel. Ele devolve um número pequeno, o descritor de arquivo (file descriptor). Depois disso, read e write usam o número, e a posição atual de leitura fica ligada àquele open.

O i-node: a descrição de um arquivo

Em sistemas do tipo UNIX cada arquivo tem um i-node (index node) com os seus atributos (dono, permissões, tamanho, datas) e os endereços dos seus blocos. Um diretório é só uma tabela de pares: um nome e um número de i-node. O nome não está no i-node. Separar nome e descrição permite vários nomes para um arquivo e faz com que renomear um arquivo mude só o diretório.

O rm chama unlink: remove uma entrada de diretório e subtrai 1 do contador. Só quando ele chega a zero, e nenhum processo tem o arquivo aberto, o i-node e os blocos são liberados. Se um arquivo tem dois nomes e você remove um, o arquivo continua existindo sob o outro.

Como os blocos de um arquivo são encontrados

• Alocação contígua: um arquivo é uma sequência de blocos vizinhos; descreve-se por primeiro bloco e comprimento. Muito rápida para ler, mas apagar arquivos deixa buracos e é preciso saber o tamanho final na criação. Por isso funciona em CDs e DVDs de gravação única (nada é apagado) mas não em discos comuns.
• Lista encadeada com tabela na memória (FAT): cada entrada da tabela guarda o número do próximo bloco do arquivo. Há uma entrada para cada bloco do disco, então a tabela cresce com o disco. Exemplo: um disco de 8 GB com blocos de 4 KB tem 2^33 / 2^12 = 2.097.152 entradas; com 4 bytes cada, são 8 MB de tabela, toda mantida na memória.
• I-node com ponteiros: alguns ponteiros diretos para os primeiros blocos e um ponteiro indireto para um bloco cheio de endereços. O número de endereços em um bloco é o tamanho do bloco dividido pelo tamanho do endereço. Ponteiros indiretos duplos e triplos repetem a ideia.

Exemplo: um i-node com 12 ponteiros diretos e 1 ponteiro indireto simples, blocos de 1 KB, endereços de 4 bytes. Um bloco indireto guarda 1024 / 4 = 256 endereços. O arquivo máximo tem 12 + 256 = 268 blocos = 268 KB.

i-node
+---------+
| dono .. |
| direto 1|--> [dados]
| ...     |--> [dados]
| direto 12-->[dados]
| indireto|--> [bloco de 256 endereços]
+---------+        |--> [dados]
                   |--> [dados] ...

Tamanho do bloco

Um compromisso. Blocos grandes significam menos buscas e menos entradas, logo uma taxa de dados maior, mas a sobra não usada no fim do último bloco de cada arquivo (slack) cresce. Como a maioria dos arquivos é pequena, blocos enormes desperdiçam muito disco. Blocos pequenos desperdiçam pouco, mas deixam o disco mais lento.

Quedas: journaling e fsck

Remover um arquivo exige vários passos em lugares diferentes: remover a entrada do diretório, liberar o i-node, devolver os blocos. Uma queda de energia no meio deixa o disco inconsistente. Com journaling, o sistema primeiro escreve em um log o que vai fazer, e depois faz. Depois de uma queda ele reexecuta o log. Alguns passos podem já ter sido feitos, então cada passo registrado precisa ser idempotente: fazê-lo duas vezes dá o mesmo resultado que uma.

Um verificador como o fsck mantém dois contadores por bloco: em quantos arquivos ele aparece e quantas vezes está na lista de livres. Um bloco saudável tem exatamente 1 em um contador e 0 no outro. Um bloco em nenhum deles volta para a lista de livres. Um bloco em dois arquivos é grave: remover um arquivo liberaria um bloco ainda usado pelo outro, então o verificador faz uma cópia do bloco para cada arquivo.

VFS e sistemas de arquivos estruturados em log

Um sistema UNIX pode montar muitos tipos de sistemas de arquivos em uma só árvore. A camada VFS (virtual file system, sistema de arquivos virtual) define objetos comuns (superblock, v-node, diretório) e uma lista de operações que cada sistema de arquivos real implementa. Os programas sempre usam as mesmas chamadas POSIX e não se importam com o que há por baixo.

Discos são lentos em escritas pequenas e espalhadas. Um sistema de arquivos estruturado em log (LFS) junta todas as escritas pendentes (dados, i-nodes, diretórios) na memória e as escreve juntas como um segmento longo no fim de um log. Um mapa de i-nodes diz onde está a cópia mais nova de cada i-node. As cópias antigas se acumulam, então um limpador (cleaner) copia o que ainda vale e libera segmentos.

Entrada e saída: interrupções, drivers, discos, RAID

Teclados, telas, discos, impressoras, placas de rede: todos são muito diferentes e muito mais lentos que a CPU. O sistema operacional precisa conversar com todos de forma organizada. Cada dispositivo tem um controlador (um chip pequeno) com registradores para comandos, estado e dados.

Chegando ao controlador

• E/S mapeada em portas (port-mapped I/O): os registradores ficam em um espaço de endereços separado, alcançado por instruções especiais.
• E/S mapeada em memória (memory-mapped I/O): os registradores aparecem em endereços da memória normal. A proteção é simples: o SO só não mapeia essas páginas para os processos de usuário, usando a gerência de memória normal.

Três jeitos de fazer E/S

Cada interrupção custa tempo de CPU, então para dispositivos rápidos é importante reduzi-las. Esse é o ganho do DMA.

Interrupções

Uma interrupção é um sinal de um dispositivo dizendo 'preciso de atenção'. A CPU para o que está fazendo, guarda onde estava, roda uma rotina curta (o tratador) e depois volta. Uma interrupção precisa (precise) deixa a máquina como se tivesse parado exatamente entre duas instruções: o contador de programa é guardado em um lugar conhecido, tudo antes terminou, nada depois mudou coisa alguma. Isso torna fácil retomar. As CPUs modernas executam muitas instruções ao mesmo tempo (pipelines, fora de ordem), então precisam de lógica extra no hardware para apresentar esse quadro limpo; senão o SO teria que descobrir o que ficou pela metade.

Camadas do software de E/S

Graças aos drivers, um dispositivo novo pode ser acrescentado sem mudar o resto do sistema operacional.

Escalonamento de disco

Um disco rígido tem um braço que se move sobre cilindros. Mover o braço (a busca, seek) é lento, então a ordem dos pedidos importa.

• FCFS: atender na ordem de chegada. Justo, mas o braço fica pulando.
• SSTF (shortest seek time first, menor tempo de busca primeiro): sempre atender o pedido mais próximo. Anda bem menos que o FCFS, mas nem sempre é o mínimo, e com uma sequência de chegadas os pedidos das bordas podem esperar muito tempo.
• Elevador (SCAN): o braço vai em uma direção atendendo tudo pelo caminho e depois volta, como um elevador em um prédio.

Exemplo: o braço está no cilindro 40 e chegam pedidos para 10, 45 e 12. FCFS: 30 + 35 + 33 = 98 cilindros. SSTF: vai para 45 (5), depois 12 (33), depois 10 (2) = 40 cilindros.

RAID: muitos discos trabalhando como um

O RAID junta discos para ganhar velocidade, segurança ou os dois. O striping (distribuição em faixas) espalha os dados por discos para que trabalhem em paralelo. O espelhamento (mirroring) guarda uma cópia. A paridade guarda informação extra para reconstruir dados perdidos.

Exemplo: 4 discos de 1 TB em RAID 5 dão 3 TB para dados. A paridade é o XOR dos blocos de dados da faixa. O XOR é o inverso de si mesmo, então qualquer bloco perdido é o XOR de todos os outros, paridade incluída. Exemplo: D1 = 0101, D3 = 0011, paridade P = 1110. Se o disco com D2 morre, D2 = 0101 XOR 0011 XOR 1110 = 1000. A reconstrução precisa ler todos os discos restantes.

Impasses (deadlocks)

Dois carros chegam a uma ponte estreita por lados opostos. Cada um espera o outro dar ré. Ninguém se move nunca. Um deadlock (impasse) é um grupo de processos em que cada um espera algo que só outro membro do grupo pode dar. Todos ficam bloqueados para sempre.

As quatro condições

Um deadlock de recursos precisa destas quatro ao mesmo tempo:

1. Exclusão mútua: um recurso é mantido por um processo de cada vez.
2. Posse e espera (hold and wait): um processo que segura recursos pode pedir mais.
3. Sem preempção: recursos não podem ser tomados à força.
4. Espera circular: um anel de processos, cada um esperando um recurso mantido pelo próximo.

Quebre qualquer uma e o deadlock se torna impossível. Essa é a ideia por trás da prevenção.

Grafo de alocação de recursos

Desenhe processos como círculos e recursos como quadrados. Uma seta de um recurso para um processo significa 'possui'. Uma seta de um processo para um recurso significa 'pede'. Quando cada recurso tem uma única instância, há deadlock exatamente quando o grafo tem um ciclo, e os processos do ciclo são os que estão em deadlock.

  A tem R, quer S
  B tem S, quer T
  C tem T, quer R

   A --quer--> S --mantido por--> B
   ^                              |
   |                            quer
 mantido por                      v
   |                              T
   R <---------quer-------------- C   (C tem T)

 O anel A -> B -> C -> A nunca se abre: DEADLOCK

Quatro maneiras de lidar com deadlocks

Prevenção na prática

O jeito mais prático é ordenar os recursos: numere todas as travas e exija que uma thread peça só uma trava com número maior que todas as travas que já segura. Assim um ciclo é impossível, porque, seguindo as setas, os números só crescem. Isso nega a condição de espera circular. O preço é a disciplina: às vezes é preciso soltar e pegar travas de novo para respeitar a ordem.

Outra ideia é tentar a trava sem bloquear (trylock) e, se falhar, soltar o que se segura e recomeçar. Isso nega posse e espera, mas pode causar livelock: dois processos repetindo a mesma dança para sempre, como duas pessoas que dão um passo para o mesmo lado em um corredor. Esperar um tempo aleatório antes de tentar de novo costuma ajudar.

Estados seguros e inseguros

Um estado é seguro se existe alguma ordem em que todos os processos conseguem terminar, mesmo que cada um peça o seu máximo. Um estado inseguro não significa que o deadlock aconteceu; significa que a garantia se perdeu e o resultado depende da sorte. O algoritmo do banqueiro funciona como um banqueiro cuidadoso com dinheiro limitado: ele só atende um pedido se o novo estado ainda for seguro, mesmo que haja recursos livres.

Para testar a segurança: necessidade restante = máximo - alocado. Ache um processo cuja necessidade restante cabe no que está livre. Finja que ele termina e devolve tudo. Repita. Se todos conseguem terminar, o estado é seguro.

Virtualização e a nuvem

Imagine um prédio grande dividido em muitos apartamentos separados. Cada família acha que é dona da sua casa, mas todas compartilham as mesmas paredes e canos. A virtualização faz isso com computadores: uma máquina real finge ser várias. Cada máquina de mentira é uma máquina virtual (VM) e tem o seu próprio sistema operacional, chamado de convidado (guest). A nuvem usa isso o tempo todo: uma empresa aluga para você uma VM em vez de um computador inteiro.

O hypervisor

O programa que cria a ilusão é o hypervisor (ou monitor de máquinas virtuais, VMM).

Trap e emulação

O SO convidado acha que está em modo kernel, mas na verdade roda em modo usuário, então o hypervisor continua no comando. Quando o convidado tenta uma instrução privilegiada, a CPU faz uma trap para o hypervisor, que finge executá-la e volta. Isso é trap and emulate.

Só funciona se toda instrução sensível (a que se comporta de forma diferente conforme o modo ou mexe no estado privilegiado da máquina) também for privilegiada (faz trap em modo usuário). Esse é o critério de Popek e Goldberg: as instruções sensíveis devem ser um subconjunto das privilegiadas. O x86 original quebrava isso: algumas instruções sensíveis faziam silenciosamente outra coisa em modo usuário, sem trap. As soluções foram a tradução binária (reescrever o código do convidado na hora) e depois o suporte em hardware (Intel VT-x, AMD-V).

Virtualização completa e paravirtualização

Memória com máquinas virtuais

Há três tipos de endereço: virtual do convidado, físico do convidado e físico da máquina (o real). O convidado controla só a primeira tradução. Sem ajuda do hardware, o hypervisor mantém tabelas de páginas sombra (shadow page tables) que vão direto de virtual do convidado para físico da máquina, e precisa interceptar toda escrita do convidado nas suas próprias tabelas para mantê-las sincronizadas, o que é caro. As CPUs modernas têm tabelas de páginas aninhadas (EPT na Intel, NPT na AMD) que fazem as duas traduções em hardware.

Sistemas com múltiplos processadores

Hoje até celulares têm vários núcleos de CPU. Com uma CPU, os programas só parecem rodar juntos porque se revezam rapidamente. Com várias CPUs, dois pedaços de código realmente rodam no mesmo instante, o que cria problemas novos para o kernel.

Por que desligar interrupções não basta

Com uma CPU, tudo o que pode interromper um trecho de código do kernel vem de interrupções e das trocas de contexto que elas causam. Então desabilitar interrupções torna segura uma região crítica curta. Em um multiprocessador, desabilitar interrupções afeta só aquela CPU. Outra CPU pode entrar no mesmo código no mesmo momento. Por isso precisamos de travas construídas sobre instruções atômicas (como a TSL), em geral combinadas com desabilitar interrupções localmente.

Girar ou bloquear?

Quando uma thread encontra a trava tomada, ela pode girar (espera ocupada, ficar perguntando) ou bloquear (dormir e entregar a CPU).

É por isso que as travas ao redor de regiões críticas muito curtas do kernel são spin locks. Muitas implementações giram por um tempo limitado e depois bloqueiam se a trava continua tomada, chegando perto do melhor dos dois.

Segurança

Uma escola deixa algumas salas abertas e outras trancadas, e dá a cada pessoa só as chaves de que precisa. O sistema operacional faz o mesmo com arquivos, memória e dispositivos. O objetivo é que um programa ou usuário possa fazer só o que lhe é permitido.

A matriz de proteção

Imagine uma tabela. Cada linha é um domínio (um usuário ou processo). Cada coluna é um objeto (um arquivo, uma impressora). Cada célula lista os direitos, como ler ou escrever. A tabela é enorme e quase toda vazia, então é guardada em pedaços:

Uma boa regra é o menor privilégio: dar a cada programa só os direitos de que ele realmente precisa.

Estouro de buffer e suas defesas

Um estouro de buffer (buffer overflow) acontece quando um programa copia mais dados para uma caixa de tamanho fixo do que ela comporta, derramando na memória vizinha. No ataque clássico os dados contêm código de máquina e sobrescrevem o endereço de retorno na pilha, para o programa saltar para esse código. Estudamos isso apenas para nos defender.

Com o DEP, os atacantes passaram a reutilizar código já carregado e executável, e por isso combinamos canários, DEP e ASLR.

Juntando tudo

Todos os tópicos são partes de uma só história. Um programa começa como um processo (com threads). Ele pede serviços ao kernel com chamadas de sistema. Ele compartilha dados com segurança usando sincronização. O escalonador dá a CPU a ele. A memória virtual dá os endereços. Os arquivos guardam os dados. A E/S alcança os dispositivos. O SO precisa evitar deadlocks, pode rodar dentro de uma máquina virtual, lida com várias CPUs e faz valer a segurança.

Erros comuns

• Achar que um processo pronto e um bloqueado são a mesma coisa. Pronto espera a CPU; bloqueado espera um evento.
• Achar que o modo muda quando você chama read. Ele muda na trap dentro dele.
• Achar que mais memória sempre reduz as faltas do FIFO (anomalia de Belady).
• Achar que um estado inseguro já é um deadlock.
• Achar que desabilitar interrupções basta em um multiprocessador.
• Esquecer que o nome de um arquivo fica no diretório e não no i-node.
• Misturar deadlock (todos bloqueados), inanição (um é ignorado) e livelock (todos ocupados, sem progresso).