Computer Science › Como os Computadores Realmente Funcionam
Este laboratório constrói um simulador em espaço de usuário que implementa o percurso de tabela de páginas multinível de Paginação e Tabelas de Páginas sobre um espaço de endereçamento virtual simulado, acrescenta uma pequena cache TLB de tamanho fixo na frente dele exatamente como O Translation Lookaside Buffer descreve, e mede diretamente, contando acessos reais à memória simulada, a diferença real de taxa de acerto que um TLB faz e o comportamento real de thrashing que Políticas de Substituição de Páginas prevê quando o working set simulado passa a exceder os quadros físicos disponíveis, sob substituição FIFO contra LRU.
Este laboratório, que corresponde ao trabalho oficial de escalonamento do xv6 nos OSTEP-projects, substitui o escalonador round-robin padrão do próprio xv6 por um escalonador por loteria, atribuindo a cada processo um número de bilhetes e escolhendo o próximo processo a rodar por um sorteio aleatório ponderado. É um mecanismo de justiça genuinamente diferente da abordagem de ajuste de prioridade do Escalonamento com Filas Multinível com Realimentação, e que contorna por construção o modo de falha de inanição de Escalonamento por Prioridade e Inanição, já que todo processo com pelo menos um bilhete tem uma chance real, diferente de zero, de ser sorteado em toda decisão de escalonamento.
O Heap e a Alocação Dinâmica já explica por que o malloc e o free precisam acompanhar eles mesmos o espaço livre e o alocado, já que o sistema operacional subjacente só distribui páginas de granularidade grossa; o próprio Malloc Lab da CMU é onde um estudante implementa malloc, free e realloc de verdade, apoiados numa lista livre que passa pelos próprios blocos não usados e em boundary tags que permitem a coalescência em tempo constante de blocos livres adjacentes, avaliados no mesmo trade-off real e concreto que todo projeto de alocador de fato enfrenta: vazão (operações por segundo) contra utilização de memória (quão pouco espaço é desperdiçado com fragmentação e sobrecarga de contabilidade).
Neste laboratório, um único arquivo comum na máquina hospedeira faz o papel de um disco bruto, formatado com o próprio layout de Arquivos, Diretórios e Inodes: um superbloco, uma tabela de inodes e uma região de blocos de dados acompanhada por um bitmap de blocos livres, que reaproveita a disciplina de gerenciamento de espaço livre do Laboratório 8 no nível de blocos em vez de bytes. Ele é exercitado por operações reais de criar, escrever, ler e apagar, e termina com uma falha deliberada injetada no meio de uma escrita para confirmar a afirmação de Implementação de Sistemas de Arquivos e Journaling de que só um sistema de arquivos com journaling, e não a primeira versão, de propósito mais simples, deste laboratório, de fato sobrevive a essa falha sem corrupção.
O conceito de fechamento de Sistemas Operacionais I acompanha um processo por fork, escalonamento, uma falta de página e uma escrita em disco como uma única narrativa conectada; este projeto final é onde essa narrativa roda de verdade, contra os componentes reais que esta disciplina inteira construiu: um processo criado e recebendo bilhetes do escalonador por loteria do Laboratório 9, um acesso à memória que falta no TLB simulado do Laboratório 10 e percorre sua tabela de páginas, e uma escrita resultante gravada pelo próprio sistema de arquivos simples do Laboratório 11, com cada um desses quatro eventos registrado com marca de tempo e produzido como um único traço contínuo que liga os laboratórios construídos separadamente desta disciplina no sistema integrado que Sistemas Operacionais I só teve espaço para descrever em prosa.
Este laboratório deixa para trás a CPU de brinquedo, personalizada, desta disciplina e passa para código de máquina x86-64 real e compilado: o próprio Bomb Lab da CMU, um binário Linux que lê uma string da entrada padrão e \"explode\" se ela não corresponder a um valor esperado escondido, ao longo de seis fases cada vez mais difíceis, desarmado inteiramente por meio de desmontagem (objdump), de um depurador (gdb) e das habilidades de leitura de registradores e códigos de condição já vistas na teoria em Registradores e Movimentação de Dados x86-64 e Códigos de Condição e Desvios Condicionais, sem acesso ao código-fonte em momento nenhum.
Stack Smashing e Buffer Overflows já provou, no papel, que uma escrita sem verificação além de um buffer de pilha consegue sobrescrever um endereço de retorno salvo; o próprio Attack Lab da CMU é onde essa prova vira uma exploração real e funcional contra um binário real e compilado: três ataques de injeção de código que sobrescrevem o endereço de retorno, seguidos de dois ataques mais difíceis de programação orientada a retorno (ROP), que encadeiam fragmentos de código já presentes no binário (gadgets) quando o binário-alvo passa a se defender de código injetado, exatamente a escalada que o próprio modelo de quadro de pilha de A Pilha de Execução x86-64: Call e Ret torna legível.
NAND como Porta Universal provou, no papel, que toda outra porta pode ser expressa só com NAND; este laboratório é onde essa prova deixa de ser um exercício de álgebra booleana e vira código funcional, compondo uma primitiva NAND em software em AND, OR, NOT, XOR e um multiplexador 2 para 1, cada um verificado contra sua própria tabela verdade, exatamente o primeiro passo, fundamental, da própria sequência de construção de um computador do Nand2Tetris.
Só a lógica combinacional não tem memória, e é por isso que este laboratório implementa um flip-flop D como a primitiva sequencial básica, o compõe num registrador de vários bits com sinal de habilitação de carga e depois compõe um arranjo desses registradores, endereçados por um decodificador construído com as próprias portas do Laboratório 1, numa RAM pequena e funcional, correspondendo aos projetos de De Flip-Flops a um Banco de Registradores e de Organização da RAM e Decodificação de Endereços com código real e executável, em vez de um diagrama de circuito.
Este laboratório compõe o conjunto de portas do Laboratório 1 numa ULA funcional que corresponde ao projeto já trabalhado na teoria em Projetando uma Unidade Lógica e Aritmética: um somador ripple-carry construído com somadores completos feitos com as próprias portas AND/XOR do Laboratório 1, um multiplexador de seleção de operação escolhendo entre soma, subtração, AND e OR, e flags de zero e de overflow calculadas diretamente a partir dos bits de saída do próprio somador, e não como um acréscimo pregado separadamente.
Cada laboratório anterior deste arco construiu um componente; este laboratório liga a ULA do Laboratório 2, o banco de registradores e a RAM do Laboratório 3 e uma unidade de controle que decodifica a própria ISA no estilo RISC-V deste currículo numa única CPU completa que de fato busca, decodifica e executa uma sequência real de instruções, conforme o próprio projeto de Montando uma CPU Monociclo Completa e o projeto da CPU Beta do MIT 6.004, verificada não por inspeção, mas carregando um pequeno programa montado à mão na RAM construída e confirmando que o banco de registradores termina no estado esperado depois da execução.
Este laboratório fecha o arco de construção da CPU escrevendo a ferramenta que torna a CPU do Laboratório 4 de fato utilizável: um montador de duas passagens que primeiro resolve cada rótulo num endereço (uma tabela de símbolos construída numa primeira passagem pelo código-fonte) e depois traduz cada instrução com mnemônico no padrão de bits exato que a unidade de controle do Laboratório 4 decodifica, conforme o próprio relato do processo em Tradução de Assembly para Código de Máquina, com a saída do montador pronto carregada diretamente de volta na RAM do Laboratório 4 como o teste real de correção de ponta a ponta deste laboratório.
Part of the Computer Science curriculum.
Este laboratório constrói um simulador em espaço de usuário que implementa o percurso de tabela de páginas multinível de Paginação e Tabelas de Páginas sobre um espaço de endereçamento virtual simulado, acrescenta uma pequena cache TLB de tamanho fixo na frente dele exatamente como O Translation Lookaside Buffer descreve, e mede diretamente, contando acessos reais à memória simulada, a diferença real de taxa de acerto que um TLB faz e o comportamento real de thrashing que Políticas de Substituição de Páginas prevê quando o working set simulado passa a exceder os quadros físicos disponíveis, sob substituição FIFO contra LRU.
Este laboratório, que corresponde ao trabalho oficial de escalonamento do xv6 nos OSTEP-projects, substitui o escalonador round-robin padrão do próprio xv6 por um escalonador por loteria, atribuindo a cada processo um número de bilhetes e escolhendo o próximo processo a rodar por um sorteio aleatório ponderado. É um mecanismo de justiça genuinamente diferente da abordagem de ajuste de prioridade do Escalonamento com Filas Multinível com Realimentação, e que contorna por construção o modo de falha de inanição de Escalonamento por Prioridade e Inanição, já que todo processo com pelo menos um bilhete tem uma chance real, diferente de zero, de ser sorteado em toda decisão de escalonamento.
O Heap e a Alocação Dinâmica já explica por que o malloc e o free precisam acompanhar eles mesmos o espaço livre e o alocado, já que o sistema operacional subjacente só distribui páginas de granularidade grossa; o próprio Malloc Lab da CMU é onde um estudante implementa malloc, free e realloc de verdade, apoiados numa lista livre que passa pelos próprios blocos não usados e em boundary tags que permitem a coalescência em tempo constante de blocos livres adjacentes, avaliados no mesmo trade-off real e concreto que todo projeto de alocador de fato enfrenta: vazão (operações por segundo) contra utilização de memória (quão pouco espaço é desperdiçado com fragmentação e sobrecarga de contabilidade).
Neste laboratório, um único arquivo comum na máquina hospedeira faz o papel de um disco bruto, formatado com o próprio layout de Arquivos, Diretórios e Inodes: um superbloco, uma tabela de inodes e uma região de blocos de dados acompanhada por um bitmap de blocos livres, que reaproveita a disciplina de gerenciamento de espaço livre do Laboratório 8 no nível de blocos em vez de bytes. Ele é exercitado por operações reais de criar, escrever, ler e apagar, e termina com uma falha deliberada injetada no meio de uma escrita para confirmar a afirmação de Implementação de Sistemas de Arquivos e Journaling de que só um sistema de arquivos com journaling, e não a primeira versão, de propósito mais simples, deste laboratório, de fato sobrevive a essa falha sem corrupção.
O conceito de fechamento de Sistemas Operacionais I acompanha um processo por fork, escalonamento, uma falta de página e uma escrita em disco como uma única narrativa conectada; este projeto final é onde essa narrativa roda de verdade, contra os componentes reais que esta disciplina inteira construiu: um processo criado e recebendo bilhetes do escalonador por loteria do Laboratório 9, um acesso à memória que falta no TLB simulado do Laboratório 10 e percorre sua tabela de páginas, e uma escrita resultante gravada pelo próprio sistema de arquivos simples do Laboratório 11, com cada um desses quatro eventos registrado com marca de tempo e produzido como um único traço contínuo que liga os laboratórios construídos separadamente desta disciplina no sistema integrado que Sistemas Operacionais I só teve espaço para descrever em prosa.
Este laboratório deixa para trás a CPU de brinquedo, personalizada, desta disciplina e passa para código de máquina x86-64 real e compilado: o próprio Bomb Lab da CMU, um binário Linux que lê uma string da entrada padrão e \"explode\" se ela não corresponder a um valor esperado escondido, ao longo de seis fases cada vez mais difíceis, desarmado inteiramente por meio de desmontagem (objdump), de um depurador (gdb) e das habilidades de leitura de registradores e códigos de condição já vistas na teoria em Registradores e Movimentação de Dados x86-64 e Códigos de Condição e Desvios Condicionais, sem acesso ao código-fonte em momento nenhum.
Stack Smashing e Buffer Overflows já provou, no papel, que uma escrita sem verificação além de um buffer de pilha consegue sobrescrever um endereço de retorno salvo; o próprio Attack Lab da CMU é onde essa prova vira uma exploração real e funcional contra um binário real e compilado: três ataques de injeção de código que sobrescrevem o endereço de retorno, seguidos de dois ataques mais difíceis de programação orientada a retorno (ROP), que encadeiam fragmentos de código já presentes no binário (gadgets) quando o binário-alvo passa a se defender de código injetado, exatamente a escalada que o próprio modelo de quadro de pilha de A Pilha de Execução x86-64: Call e Ret torna legível.
NAND como Porta Universal provou, no papel, que toda outra porta pode ser expressa só com NAND; este laboratório é onde essa prova deixa de ser um exercício de álgebra booleana e vira código funcional, compondo uma primitiva NAND em software em AND, OR, NOT, XOR e um multiplexador 2 para 1, cada um verificado contra sua própria tabela verdade, exatamente o primeiro passo, fundamental, da própria sequência de construção de um computador do Nand2Tetris.
Só a lógica combinacional não tem memória, e é por isso que este laboratório implementa um flip-flop D como a primitiva sequencial básica, o compõe num registrador de vários bits com sinal de habilitação de carga e depois compõe um arranjo desses registradores, endereçados por um decodificador construído com as próprias portas do Laboratório 1, numa RAM pequena e funcional, correspondendo aos projetos de De Flip-Flops a um Banco de Registradores e de Organização da RAM e Decodificação de Endereços com código real e executável, em vez de um diagrama de circuito.
Este laboratório compõe o conjunto de portas do Laboratório 1 numa ULA funcional que corresponde ao projeto já trabalhado na teoria em Projetando uma Unidade Lógica e Aritmética: um somador ripple-carry construído com somadores completos feitos com as próprias portas AND/XOR do Laboratório 1, um multiplexador de seleção de operação escolhendo entre soma, subtração, AND e OR, e flags de zero e de overflow calculadas diretamente a partir dos bits de saída do próprio somador, e não como um acréscimo pregado separadamente.
Cada laboratório anterior deste arco construiu um componente; este laboratório liga a ULA do Laboratório 2, o banco de registradores e a RAM do Laboratório 3 e uma unidade de controle que decodifica a própria ISA no estilo RISC-V deste currículo numa única CPU completa que de fato busca, decodifica e executa uma sequência real de instruções, conforme o próprio projeto de Montando uma CPU Monociclo Completa e o projeto da CPU Beta do MIT 6.004, verificada não por inspeção, mas carregando um pequeno programa montado à mão na RAM construída e confirmando que o banco de registradores termina no estado esperado depois da execução.
Este laboratório fecha o arco de construção da CPU escrevendo a ferramenta que torna a CPU do Laboratório 4 de fato utilizável: um montador de duas passagens que primeiro resolve cada rótulo num endereço (uma tabela de símbolos construída numa primeira passagem pelo código-fonte) e depois traduz cada instrução com mnemônico no padrão de bits exato que a unidade de controle do Laboratório 4 decodifica, conforme o próprio relato do processo em Tradução de Assembly para Código de Máquina, com a saída do montador pronto carregada diretamente de volta na RAM do Laboratório 4 como o teste real de correção de ponta a ponta deste laboratório.