Computer Science › Como os Computadores Realmente Funcionam
A abstração de processo transforma uma CPU física na ilusão de muitas: a memória, os registradores e os arquivos abertos de um programa em execução empacotados numa única unidade que o SO consegue pausar, retomar e equilibrar entre muitas outras.
A separação do Unix entre \"crie uma cópia de mim\" (fork) e \"substitua minha memória por outro programa\" (exec): um projeto de dois passos genuinamente estranho, cuja estranheza é exatamente o que torna possíveis os shells e os pipes.
Um processo está sempre em exatamente um de um punhado de estados (executando, pronto ou bloqueado), e o mecanismo que permite ao SO salvar o estado de CPU de um processo e carregar o de outro é a troca de contexto, a maquinaria sobre a qual a execução direta limitada é construída.
Antes de comparar políticas de escalonamento, é preciso fixar o que 'bom' significa: tempo de retorno, tempo de resposta e vazão muitas vezes competem entre si, então nenhuma política vence em todas as métricas ao mesmo tempo.
O primeiro-a-chegar-primeiro-a-ser-atendido é trivialmente justo, mas deixa uma única tarefa longa bloquear todas as tarefas curtas atrás dela (o efeito comboio), enquanto o menor-tarefa-primeiro corrige de forma comprovada o tempo de retorno médio, ao custo de precisar conhecer o futuro.
Dar a toda tarefa uma fatia de tempo pequena e fixa e revezar entre elas: excelente para o tempo de resposta, pior para o tempo de retorno que o SJF, e a primeira política desta disciplina que não precisa prever o futuro.
Deixar algumas tarefas furarem a fila resolve o problema de trabalho urgente esperando atrás de trabalho trivial, mas abre um novo: uma tarefa de baixa prioridade pode esperar para sempre se o trabalho de prioridade mais alta nunca parar de chegar.
O escalonador que os sistemas operacionais reais de fato aproximam: várias filas de prioridade, tarefas rebaixadas por usarem CPU demais e promovidas periodicamente para evitar inanição, aprendendo o comportamento de uma tarefa pelo seu histórico recente em vez de perguntar de antemão.
Uma thread é um fluxo de execução escalonável de forma independente que compartilha o espaço de endereçamento do seu processo com as threads irmãs: exatamente a mecânica em nível de sistema com que o modelo de concorrência com estado compartilhado, apresentado conceitualmente em outro lugar, é de fato construído.
O enunciado formal do perigo de condição de corrida já visto como modelo mental: uma seção crítica é qualquer código que toca estado compartilhado, e a exclusão mútua é a garantia de que no máximo uma thread está dentro dela por vez.
Um lock só funciona se adquiri-lo for ele mesmo imune à mesma condição de corrida que ele impede, e é por isso que locks reais são construídos sobre instruções atômicas fornecidas pelo hardware, como test-and-set e compare-and-swap, e não sobre load/store comuns.
Um lock sozinho não consegue deixar uma thread esperar que alguma condição se torne verdadeira sem ficar girando ocupada; uma variável de condição acrescenta exatamente isso: uma fila em que uma thread pode dormir, e um sinal que outra thread envia quando a espera acaba.
Um único contador inteiro com duas operações atômicas, wait e signal, geral o bastante para implementar um lock, a sinalização de uma variável de condição ou um limite de quantas threads podem prosseguir ao mesmo tempo: a única primitiva de Dijkstra que faz o trabalho de várias.
Locks e semáforos resolvem condições de corrida, mas abrem um novo modo de falha: threads esperando umas pelas outras num ciclo, para sempre. É o deadlock, detectável construindo um grafo de alocação de recursos e rodando exatamente o mesmo algoritmo de detecção de ciclos já visto para grafos em geral.
Cada processo vê seu próprio espaço de endereçamento privado e contíguo, começando no endereço zero: uma ilusão que o SO mantém sobre uma única RAM física compartilhada, e o motivo de um bug nos ponteiros de um programa não conseguir corromper a memória de outro.
O suporte de hardware mais simples possível para memória virtualizada: um registrador guardando onde a memória de um processo começa e outro guardando seu tamanho; todo endereço que um programa usa é realocado e conferido contra o limite automaticamente.
Dividir um espaço de endereçamento em segmentos realocados de forma independente (código, pilha, heap) evita desperdiçar memória com o vão sem uso entre um heap pequeno e uma pilha pequena, ao custo da fragmentação externa, o mesmo problema de gerenciamento de espaço livre que um alocador de propósito geral enfrenta.
Em vez de alguns segmentos grandes e de tamanho variável, picar a memória em muitas páginas pequenas e de tamanho fixo, eliminando por completo a fragmentação externa, ao custo de precisar de uma tabela de páginas para registrar onde cada página de fato fica na memória física.
Consultar uma entrada da tabela de páginas na memória a cada acesso deixaria a paginação catastroficamente lenta; o TLB é uma pequena cache de hardware totalmente associativa de traduções recentes, aplicando a mesma ideia de cache já vista para dados, agora à própria tradução de endereços.
Quando a memória física está cheia e uma página nova precisa entrar, algo tem de ser despejado: FIFO, ótimo e LRU são três respostas diferentes para 'qual página', comparadas na mesmíssima sequência de referências para ver quantas faltas de página cada uma de fato causa.
Carregar páginas só quando elas são de fato tocadas permite que um processo rode com menos memória física do que seu espaço de endereçamento completo exigiria, até que processos demais disputem memória de menos e o sistema passe mais tempo paginando do que calculando, um colapso chamado thrashing.
O trabalho real de um sistema de arquivos é transformar um array plano de blocos de disco em arquivos hierárquicos com nome: um inode guarda os metadados de um arquivo e os ponteiros de bloco que localizam seus dados, enquanto um diretório é só um arquivo especial que mapeia nomes em números de inode.
Uma falha no meio de uma atualização de vários blocos (um novo inode, um novo bloco de dados, um bitmap atualizado) pode deixar inconsistentes as estruturas em disco de um sistema de arquivos; o journaling corrige isso escrevendo primeiro as mudanças pretendidas num log, tornando a atualização inteira recuperável como um único passo atômico.
Todos os mecanismos desta disciplina trabalhando juntos numa única linha do tempo concreta: um shell faz fork e exec de um programa, o escalonador o escolhe, ele toca uma página que ainda não está residente, e a falta de página resultante termina numa leitura real de disco pelo sistema de arquivos.
Part of the Computer Science curriculum.
A abstração de processo transforma uma CPU física na ilusão de muitas: a memória, os registradores e os arquivos abertos de um programa em execução empacotados numa única unidade que o SO consegue pausar, retomar e equilibrar entre muitas outras.
A separação do Unix entre \"crie uma cópia de mim\" (fork) e \"substitua minha memória por outro programa\" (exec): um projeto de dois passos genuinamente estranho, cuja estranheza é exatamente o que torna possíveis os shells e os pipes.
Um processo está sempre em exatamente um de um punhado de estados (executando, pronto ou bloqueado), e o mecanismo que permite ao SO salvar o estado de CPU de um processo e carregar o de outro é a troca de contexto, a maquinaria sobre a qual a execução direta limitada é construída.
Antes de comparar políticas de escalonamento, é preciso fixar o que 'bom' significa: tempo de retorno, tempo de resposta e vazão muitas vezes competem entre si, então nenhuma política vence em todas as métricas ao mesmo tempo.
O primeiro-a-chegar-primeiro-a-ser-atendido é trivialmente justo, mas deixa uma única tarefa longa bloquear todas as tarefas curtas atrás dela (o efeito comboio), enquanto o menor-tarefa-primeiro corrige de forma comprovada o tempo de retorno médio, ao custo de precisar conhecer o futuro.
Dar a toda tarefa uma fatia de tempo pequena e fixa e revezar entre elas: excelente para o tempo de resposta, pior para o tempo de retorno que o SJF, e a primeira política desta disciplina que não precisa prever o futuro.
Deixar algumas tarefas furarem a fila resolve o problema de trabalho urgente esperando atrás de trabalho trivial, mas abre um novo: uma tarefa de baixa prioridade pode esperar para sempre se o trabalho de prioridade mais alta nunca parar de chegar.
O escalonador que os sistemas operacionais reais de fato aproximam: várias filas de prioridade, tarefas rebaixadas por usarem CPU demais e promovidas periodicamente para evitar inanição, aprendendo o comportamento de uma tarefa pelo seu histórico recente em vez de perguntar de antemão.
Uma thread é um fluxo de execução escalonável de forma independente que compartilha o espaço de endereçamento do seu processo com as threads irmãs: exatamente a mecânica em nível de sistema com que o modelo de concorrência com estado compartilhado, apresentado conceitualmente em outro lugar, é de fato construído.
O enunciado formal do perigo de condição de corrida já visto como modelo mental: uma seção crítica é qualquer código que toca estado compartilhado, e a exclusão mútua é a garantia de que no máximo uma thread está dentro dela por vez.
Um lock só funciona se adquiri-lo for ele mesmo imune à mesma condição de corrida que ele impede, e é por isso que locks reais são construídos sobre instruções atômicas fornecidas pelo hardware, como test-and-set e compare-and-swap, e não sobre load/store comuns.
Um lock sozinho não consegue deixar uma thread esperar que alguma condição se torne verdadeira sem ficar girando ocupada; uma variável de condição acrescenta exatamente isso: uma fila em que uma thread pode dormir, e um sinal que outra thread envia quando a espera acaba.
Um único contador inteiro com duas operações atômicas, wait e signal, geral o bastante para implementar um lock, a sinalização de uma variável de condição ou um limite de quantas threads podem prosseguir ao mesmo tempo: a única primitiva de Dijkstra que faz o trabalho de várias.
Locks e semáforos resolvem condições de corrida, mas abrem um novo modo de falha: threads esperando umas pelas outras num ciclo, para sempre. É o deadlock, detectável construindo um grafo de alocação de recursos e rodando exatamente o mesmo algoritmo de detecção de ciclos já visto para grafos em geral.
Cada processo vê seu próprio espaço de endereçamento privado e contíguo, começando no endereço zero: uma ilusão que o SO mantém sobre uma única RAM física compartilhada, e o motivo de um bug nos ponteiros de um programa não conseguir corromper a memória de outro.
O suporte de hardware mais simples possível para memória virtualizada: um registrador guardando onde a memória de um processo começa e outro guardando seu tamanho; todo endereço que um programa usa é realocado e conferido contra o limite automaticamente.
Dividir um espaço de endereçamento em segmentos realocados de forma independente (código, pilha, heap) evita desperdiçar memória com o vão sem uso entre um heap pequeno e uma pilha pequena, ao custo da fragmentação externa, o mesmo problema de gerenciamento de espaço livre que um alocador de propósito geral enfrenta.
Em vez de alguns segmentos grandes e de tamanho variável, picar a memória em muitas páginas pequenas e de tamanho fixo, eliminando por completo a fragmentação externa, ao custo de precisar de uma tabela de páginas para registrar onde cada página de fato fica na memória física.
Consultar uma entrada da tabela de páginas na memória a cada acesso deixaria a paginação catastroficamente lenta; o TLB é uma pequena cache de hardware totalmente associativa de traduções recentes, aplicando a mesma ideia de cache já vista para dados, agora à própria tradução de endereços.
Quando a memória física está cheia e uma página nova precisa entrar, algo tem de ser despejado: FIFO, ótimo e LRU são três respostas diferentes para 'qual página', comparadas na mesmíssima sequência de referências para ver quantas faltas de página cada uma de fato causa.
Carregar páginas só quando elas são de fato tocadas permite que um processo rode com menos memória física do que seu espaço de endereçamento completo exigiria, até que processos demais disputem memória de menos e o sistema passe mais tempo paginando do que calculando, um colapso chamado thrashing.
O trabalho real de um sistema de arquivos é transformar um array plano de blocos de disco em arquivos hierárquicos com nome: um inode guarda os metadados de um arquivo e os ponteiros de bloco que localizam seus dados, enquanto um diretório é só um arquivo especial que mapeia nomes em números de inode.
Uma falha no meio de uma atualização de vários blocos (um novo inode, um novo bloco de dados, um bitmap atualizado) pode deixar inconsistentes as estruturas em disco de um sistema de arquivos; o journaling corrige isso escrevendo primeiro as mudanças pretendidas num log, tornando a atualização inteira recuperável como um único passo atômico.
Todos os mecanismos desta disciplina trabalhando juntos numa única linha do tempo concreta: um shell faz fork e exec de um programa, o escalonador o escolhe, ele toca uma página que ainda não está residente, e a falta de página resultante termina numa leitura real de disco pelo sistema de arquivos.