A estrutura do sistema de multiprogramação “THE”
Título original: The Structure of the “THE”-Multiprogramming System
PublicadoCommunications of the ACM
Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.
Resumo
Descreve-se um sistema de multiprogramação em que todas as atividades são divididas entre vários processos sequenciais. Esses processos sequenciais são colocados em diversos níveis hierárquicos, e em cada um deles foram implementadas uma ou mais abstrações independentes. A estrutura hierárquica mostrou-se vital para a verificação da correção lógica do projeto e da correção de sua implementação.
Tradução nossa do resumo original dos autores, em inglês.
Análise de pesquisa
Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.
- Última revisão
- Versão
- 1.0
Visão geral
O artigo de Edsger Dijkstra na Communications of the ACM (volume 11, número 5, maio de 1968, páginas 341 a 346) foi apresentado em um ACM Symposium on Operating System Principles, em Gatlinburg, Tennessee, de 1 a 4 de outubro de 1967. É um relatório de andamento de um grupo de seis pessoas, em média com meio período, no Departamento de Matemática da Universidade Técnica de Eindhoven, que queriam aprender projeto de sistemas "incluindo todas as etapas de concepção, construção e verificação". O sistema rodava num Electrologica X8: memória de núcleos de 27 bits (32K palavras na época, ciclo de 2,5 microssegundos), um tambor de 512K palavras com tempo de rotação de 40 ms e dez canais de periféricos de baixa capacidade.
O objetivo era processar um fluxo contínuo de programas de usuários como serviço à universidade: menor tempo de resposta para programas curtos, uso econômico dos periféricos, controle automático da memória auxiliar e uso da máquina em trabalhos que pedem flexibilidade, não potência. O autor diz explicitamente que não é um sistema multiacesso e que não atende programas de usuário em linguagem de máquina. Vale conhecer antes: o que é uma interrupção, o que é um processo e por que erros dependentes de temporização não se reproduzem sob demanda. O medo desse tipo de erro (Dijkstra escrevia software com interrupções desde 1958) é o motivo declarado do artigo.
O mesmo fascículo da CACM (11(5)) traz O modelo de working set para o comportamento de programas, do mesmo simpósio de 1967. O THE trata de como os segmentos se movem entre núcleo e tambor (o segment controller, nível 1); Denning pergunta quais páginas de um programa devem estar na memória principal, definidas pelas páginas referenciadas nos últimos tau segundos. O pareamento é meu, não achei que um dos textos discuta o outro.
Os pareamentos abaixo são meus, o artigo de 1968 não pode citar trabalhos posteriores. O sistema de tempo compartilhado UNIX tem outro temperamento de projeto: um sistema pequeno e interativo, sobre uma única abstração uniforme de arquivo, e não sobre níveis estritos. A proteção da informação em sistemas computacionais é um tutorial de 1975 sobre proteção, que pergunta o que um supervisor precisa impor, algo que o artigo de 1968 não aborda. O Exokernel, o seL4 e o Multikernel assumem, cada um, uma posição diferente sobre o que deve ser a camada mais baixa de um SO.
Contribuição
- Uma sociedade de processos sequenciais. O sistema inteiro é organizado como processos sequenciais "progredindo com razões de velocidade indefinidas": um por programa de usuário aceito, um por periférico de entrada e de saída, um "segment controller" para o tambor e um "message interpreter" para o teclado do console. Só a ordem dos estados importa logicamente, não a velocidade, então os processos cooperam por sincronização mútua explícita, e o sistema independe de quantos processadores o executam.
- Seis níveis. O nível 0 aloca o processador entre os processos cujo progresso é logicamente permitido, trata a interrupção do relógio de tempo real (para que nenhum processo monopolize o processador) e aplica uma regra de prioridade. O nível 1 é o segment controller, com a contabilidade da memória auxiliar automática. O nível 2 é o message interpreter, que compartilha o console do operador. O nível 3 reúne os processos que fazem buffering das entradas e das saídas e abstrai os periféricos físicos. O nível 4 são os programas de usuário independentes, e o nível 5 é o operador ("não implementado por nós"). Cada nível esconde um recurso: acima do nível 0, os processadores; acima do 1, as páginas de núcleo e de tambor; acima do 2, o console.
- Segmentos separados de páginas. As unidades de informação ("segmentos", cada uma cabendo exatamente numa página) têm identificadores próprios, muito mais numerosos que as páginas de núcleo e de tambor. Um segmento removido do núcleo pode ir para qualquer página livre do tambor, e escolhe-se a de menor latência, de modo que não existe problema de alocação do tambor.
- Semáforos (apêndice). Variáveis inteiras inicializadas com 0 ou 1, acessadas só pela operação P (diminui 1, bloqueia se o resultado for negativo) e pela operação V (aumenta 1, libera um processo em espera se o resultado for não positivo). Dijkstra distingue semáforos de exclusão mútua de "semáforos privados", cada um esperado por um único processo.
- Estrutura para limitar o teste. O projeto busca um mecanismo "tão bem estruturado" que, em cada etapa do teste, "o número de casos de teste relevantes será tão pequeno que ele poderá tentá-los todos".
Metodologia
O artigo é um relato de projeto e de experiência, sem benchmark. O autor descreve a construção em três etapas. A concepção levou muito tempo e produziu os conceitos acima, além da "arte de raciocinar" para deduzir, de requisitos como "nenhuma informação pode ser usada antes de ser produzida" e "nenhum periférico pode receber duas tarefas ao mesmo tempo", como os processos devem se sincronizar. A construção foi "bastante tradicional, talvez até antiquada": código de máquina puro. A verificação usou curtas sessões com a máquina nua e sem ferramentas de depuração.
O teste começou no nível 0, e cada nível acima só era acrescentado depois que o anterior estava bem testado. Cada sessão incluía processos de teste que forçavam o sistema a todos os estados relevantes e verificavam se ele continuava reagindo conforme a especificação. O apêndice foi acrescentado a pedido do comitê de programa, que queria mais informação sobre as primitivas de sincronização e uma justificativa para a afirmação de provar a correção lógica a priori. Ele traz uma demonstração em prosa, em três estágios: uma única tarefa não pode causar uma cadeia infinita de geração de tarefas (tarefas só vão para níveis mais baixos, com uma precaução contra o "page flutter" no segment controller); nenhuma tarefa gerada pode ficar pendente enquanto todos os processos estão em repouso; e não pode haver espera circular, o "Deadly Embrace". Para sistemas mais gerais a prova é por indução sobre o nível, como A. N. Habermann mostrou em sua tese de doutorado.
Resultados
Todos os números abaixo são do artigo, e o artigo não traz números de desempenho.
- Erros encontrados. Os únicos erros durante o teste foram erros triviais de codificação, "com densidade de um erro por 500 instruções", cada um localizado em até 10 minutos de inspeção na máquina.
- Situação na data da escrita. O teste "ainda não estava concluído", mas o autor escreve que o sistema resultante "tem garantia de ser impecável" e que sua correção terá sido provada "com um rigor e uma explicitação incomuns para a grande maioria das demonstrações matemáticas".
- Por que níveis ajudam o teste. Testar o nível 0 exigiu apenas processos de teste sequenciais por cima dele. No nível 1, o relógio de tempo real, embora "interrompendo o tempo todo", era tão irrelevante que um dos testadores esqueceu que ele existia. Sem os níveis separados, o número de "estados relevantes" das ordens arbitrárias de interrupções do relógio e do tambor "teria explodido" a ponto de o teste exaustivo "ser uma ilusão".
- Falha de hardware absorvida. Ao testar nos níveis 2 ou 3, o canal do tambor quebrou por algum tempo, e o teste continuou limitando o número de segmentos ao que cabia no núcleo, o que foi possível porque as páginas perdem a identidade acima do nível 1.
- Por que o message interpreter fica acima do segment controller. Seu vocabulário é guardado em segmentos, podendo residir no tambor, em vez de ocupar uma reserva permanente de núcleo.
- Erros admitidos. O grupo se concentrou por tempo demais numa "instalação perfeita" e só tarde cuidou das quebras de periféricos (a "patologia"), o que deixou suas regras de gerência mais refinadas que o necessário. Também concebeu quase todo o sistema dando "pouco pensamento" à depuração, o que Dijkstra diz não ter tido consequências sérias e pelo que recusa crédito.
- Condições de trabalho. O pessoal de meio período reduziu a produção em "pelo menos um fator de quatro", e ele diz que esse trabalho exige as melhores pessoas.
Análise crítica
- "Provado" significa um argumento em prosa. O artigo dá uma demonstração informal em três estágios num apêndice, não uma prova formal nem verificada por máquina, e o sistema ainda estava em teste. O teste achou erros de codificação, então a afirmação é sobre o projeto (correção lógica a priori) mais uma implementação testada, não sobre um programa verificado. O mesmo texto diz também que os programas de teste foram "um grande esforço intelectual" e que os estados relevantes foram todos gerados apenas "até onde sabemos".
- O escopo é estreito. Serviço em lote para uma universidade, numa máquina, sem multiacesso, sem programas de usuário em linguagem de máquina, sem base de dados comum e sem medida de vazão ou de tempo de resposta. A conclusão menciona o ceticismo da indústria sobre a transferência das técnicas para fora da "atmosfera protegida de uma universidade". O autor responde com uma opinião ("quanto maior o projeto, mais essencial a estruturação!"), não com um sistema maior.
- Custos da estrutura. O texto não discute custo de execução das camadas. Lista custos em outros pontos: uma ordem rígida de dependências (o message interpreter precisa ficar acima do segment controller), processos que só geram tarefas para níveis mais baixos e um esforço de concepção e de construção dos programas de teste que o autor chama de grande.
- Literatura posterior (marcada como tal, só fonte secundária lida). Um resumo da Wikipedia sobre o THE, que li sem rastrear suas fontes, atribui ao sistema as primeiras formas de memória paginada em software e cita o livro de Silberschatz e Peterson (1988, não lido) para dizer que era sobretudo em lote e com conjunto estático de processos. As afirmações de que Windows NT e macOS usariam camadas depois, e de que o projeto lembra os anéis do Multics, não têm citação lá, então não me apoio nelas.
Pesquisas futuras
- Comparar a estrutura em níveis com sistemas que mantêm uma pequena camada inferior confiável, como seL4, O Exokernel e O Multikernel, perguntando o que cada um escolhe esconder.
- Projetos em camadas verificados por máquina: o CertiKOS constrói um kernel a partir de camadas de abstração certificadas (não conferi se cita este artigo), a contrapartida verificada de um argumento informal nível por nível.
- O lado do custo: Por que os sistemas operacionais não ficam rápidos como o hardware? e Sobre a construção de micro-kernels medem o que custam as travessias do kernel e o IPC, uma pergunta que este artigo nunca faz.
- Sincronização além de P e V: Algoritmos para sincronização escalável em multiprocessadores de memória compartilhada estuda travas de espera ocupada em máquinas de memória compartilhada, um cenário em que os semáforos de um único processador com interrupções não se aplicam diretamente.
Texto completo
Discussão · 0
Entre para participar da discussãoNenhum post ainda. Seja o primeiro a iniciar a discussão.