Existem duas estruturas de dados conhecidas por qualquer programador e consideradas tão axiomas que ninguém sequer tenta analisar se elas são necessárias, se há algum benefício delas e se esse dano não as excede.
Fila
Primeiro de tudo, discutiremos a fila. Qual é o significado da fila? Uma fila é um buffer. E quando precisamos de um buffer? Quando não temos tempo para processar os eventos recebidos no ritmo de sua chegada.
Em conexão com o exposto, surge uma única pergunta: por que? A resposta é que esperamos que algo aconteça e, de repente, o sistema nos permita processar eventos.
Primeiro, vamos lidar com o primeiro parágrafo. O que deveria acontecer com o sistema, que de repente para de frear e começa a digerir os dados mais rapidamente? Provavelmente, algum processo intensivo em recursos simplesmente encerrará e liberará recursos. Mas e se isso não acontecer? O que fazer com os dados? Sabe-se que: ou apenas as redefinimos ou o sistema inteiro fica paralisado por falta de recursos.
Duck, existem duas perguntas:
- E por que você não pode soltar os dados imediatamente se sabemos que não temos recursos para processá-los? É por isso que é impossível fazer uma fila a partir de um elemento?
- Ou a pergunta inversa. Por que temos ilusões e não fornecemos ao sistema a quantidade necessária de recursos para processar os dados na taxa de recebimento?
As respostas para essas perguntas são, de fato, óbvias. Simplesmente não sabemos como projetar sistemas de software e hardware. Como se soubéssemos projetá-los, saberíamos quantos dados de entrada temos, a taxa de recebimento, quanto precisamos processá-los e, portanto, poderíamos calcular a real necessidade de recursos. Mas o estado atual das ferramentas e metodologias de desenvolvimento de TIC, com exceção de uma parte dos sistemas tecnológicos (e de modo algum todos eles), não nos permite fazer cálculos objetivos dos requisitos de recursos.
E encerramos essas deficiências com todos os tipos de buffers, em particular, na forma de filas. Como resultado, temos uma bomba colocada na fundação do edifício, mesmo no nível do poço da fundação, porque essas muletas servem como fonte de vários problemas desprezíveis e difíceis de entender, com confiabilidade, segurança e simplesmente a qualidade do trabalho.
Mas, vamos continuar, à nossa frente está minha estrutura mais “favorita” - a pilha!
Stack
Isso é certo, como Hoar disse uma vez sobre Null, que este é um erro de bilhão de dólares, portanto o mesmo pode ser dito sobre a pilha.
Essa é uma das estruturas mais problemáticas usadas nas TIC e é altamente desejável evitar a prática máxima da criação de hardware e software, até a completa erradicação.
Então, qual é exatamente o problema da pilha? Sim, exatamente o mesmo que com a fila. Pilhas são fundamentalmente impossíveis de organizar. Assim que há uma pessoa que prevê com precisão quanta memória a pilha de qualquer programa arbitrário precisa, peço desculpas pessoalmente e escrevo um artigo enorme que estava errado e peço perdão.
Mas algo me diz que é improvável que isso aconteça no futuro próximo.
Vamos analisar por que precisamos de pilhas? Sim, exatamente para o mesmo, para o qual a fila. Este é um buffer. Ou seja, essas são muletas para uma mente preguiçosa que não deseja projetar corretamente sistemas de software e hardware.
Portanto, a lição é a seguinte: recursões devem ser evitadas onde houver uma solução iterativa óbvia. No entanto, isso não significa que as recursões devem ser descartadas a todo custo. Existem muitos bons exemplos de uso da recursão, que demonstraremos nas seções e capítulos subsequentes. O fato de haver implementações de procedimentos recursivos em máquinas praticamente não recursivas prova que, para fins práticos, qualquer programa recursivo pode ser transformado em um puramente iterativo. No entanto, isso requer trabalho explícito com a pilha de recursão, e essas ações geralmente obscurecem a essência do programa, para que possa ser difícil de entender. Conclusão: algoritmos de natureza recursiva e não iterativa precisam ser formulados como procedimentos recursivos.
Nicklaus Wirth. Algoritmos e estruturas de dados
Concordando com o mestre sobre as opções de conversão, não concordo com suas abordagens suaves para usar a pilha.
Apresentei um teorema: qualquer algoritmo de pilha pode ser convertido em um loop, e aqueles que não podem ser convertidos são ruins.
A prática de chamar subprogramas com a passagem de parâmetros pela pilha deve ser interrompida, e a recursão que não se expande no loop e outras práticas amplamente usadas também devem ir para lá.
Podemos substituir a pilha para os seguintes casos:
- Recursão, implementada na forma de expandir o algoritmo da pilha em um loop com um bloco de dados que é alterado durante a execução do loop.
- Se precisar transferir parâmetros, você organizará um sistema de firmware com mensagens. E sobre mensagens, vamos para as linhas que foram descritas na primeira parte do artigo. Se você realmente deseja uma pilha, obviamente não deve enviar dezenas e centenas de kilobytes de objetos para lá, mas precisará alocar memória para isso normalmente, no heap.
Ao mesmo tempo, no nível superior, os programadores podem usar qualquer estrutura de dados, e cabe aos compiladores transformá-los para excluir o uso da pilha.
Obviamente, algumas das oportunidades provavelmente serão perdidas, mas isso, se considerado em detalhes, não é um fato.
Bloqueio
Em 1995, com meu colega de classe, formulei os princípios de construção de um sistema operacional que excluiu esses dois paradigmas.
Os princípios foram os seguintes:
- Software - redes de processos em interação.
- A interação dos processos é realizada através da troca de mensagens.
- A rede de processos de interação está organizada da seguinte forma: as fontes de mensagens primárias em uma rede são apenas eventos do mundo externo fornecidos pelo equipamento, os consumidores finais das mensagens são apenas dispositivos que executam ações no mundo externo. Ou seja, a rede começa no mundo real e termina nele.
- Os processos não podem ter prioridades. As prioridades podem ter apenas uma rede de processos.
- A rede nunca armazena em buffer as mensagens. O complexo de hardware e software deve ser organizado de maneira a conseguir processar mensagens no ritmo de seu recebimento do mundo exterior.
- O complexo de hardware é uma rede de nós de computação conectados por canais de comunicação.
- Cada nó possui um "custo", dependendo de sua capacidade de processamento, tamanho da memória, carga e fator de peso, levando em consideração os custos de sua criação e manutenção.
- Cada canal de comunicação possui um “custo”, dependendo de sua largura de banda, congestionamento e coeficiente de peso, levando em consideração os custos de criação e manutenção.
- O sistema operacional fornece o lançamento de processos em resposta a mensagens recebidas e roteamento de mensagens.
- O sistema operacional garante a distribuição de processos e mensagens entre os nós da computação, otimizando a função f (cpu, mem) na topologia da rede, levando em consideração o custo de transmissão do código do processo e das mensagens para o nó.
- Dada a construção do sistema, você sempre pode calcular com precisão a quantidade de memória necessária para o processo. A quantidade necessária de tempo de contagem pode ser calculada com precisão com base na análise do algoritmo.
Processador BIND
Como parte de sua carreira de professor, juntamente com os alunos, ele participou do concurso de emuladores de CPU IEEE. Um processador sem pilha de uso geral da arquitetura de Harvard foi desenvolvido usando um sistema de comando semelhante aos ARMs anteriores. Além disso, a idéia esquecida dos transportadores foi incorporada à CPU e o processador foi equipado com 16 canais de transmissão e recepção de 8 bits.
Consequentemente, não houve operações de chamada / retorno no processador. Somente uma transição condicional / incondicional foi possível. Dado que quase ninguém escreve no assembler no momento, todas as perguntas sobre a geração de um programa em código de máquina deveriam ser atribuídas ao compilador.
O principal objetivo desse processador era suportar perfeitamente os princípios do sistema operacional Blockout no nível do hardware, criando uma rede de processadores no nó de computação local conectado por canais de comunicação pelos quais os processos já serão distribuídos.
Conclusões
O texto mostra as falhas fatais da fila e empilha as estruturas de dados. São apresentados os princípios de projeto de sistemas de software e hardware que permitem excluir essas estruturas da prática da aplicação.
Este texto é, antes, uma compilação de pensamentos que ocorreram ao longo da carreira em TI, por assim dizer, para reduzir tudo em um só lugar.