Hay dos estructuras de datos que son conocidas por cualquier programador y que se consideran axiomas que nadie intenta analizar si son necesarios, si hay algún beneficio de ellos y si este daño no los supera.
Cola
En primer lugar, discutiremos la cola. ¿Cuál es el significado de la cola? Una cola es un búfer. ¿Y cuándo necesitamos un búfer? Cuando no tenemos tiempo para procesar eventos entrantes al ritmo de su llegada.
En relación con lo anterior, surge una sola pregunta: ¿por qué? La respuesta es que esperamos que suceda algo y de repente el sistema nos permitirá procesar eventos.
Primero, tratemos con el primer párrafo. ¿Qué debería pasarle al sistema, que de repente deja de frenar y comienza a digerir datos más rápido? Lo más probable es que algunos procesos intensivos en recursos simplemente terminen y liberen recursos. Pero, ¿y si esto no sucede? ¿Qué hacer con los datos? Se sabe que: o simplemente los reiniciamos, o todo el sistema simplemente se cuelga por falta de recursos.
Pato, hay dos preguntas:
- ¿Y por qué no puede descartar los datos de inmediato si sabemos que no tenemos recursos para procesarlos? ¿Por eso es imposible hacer una cola a partir de un elemento?
- O la pregunta inversa. ¿Por qué tenemos ilusiones y no suministramos al sistema la cantidad necesaria de recursos para procesar los datos a la velocidad de recepción?
Las respuestas a estas preguntas son, de hecho, obvias. Simplemente no sabemos cómo diseñar sistemas de software y hardware. Porque si supiéramos cómo diseñarlos, sabríamos cuántos datos de entrada tenemos, la tasa de recepción, cuánto necesitamos procesarlos y, en consecuencia, podríamos calcular la necesidad real de recursos. Pero el estado actual de las herramientas y metodologías de desarrollo de las TIC, con la excepción de una parte de los sistemas tecnológicos (y de ninguna manera todos), no nos permite hacer cálculos objetivos de los requisitos de recursos.
Y cerramos estas deficiencias con todo tipo de buffers, en particular, en forma de colas. Como resultado, tenemos una bomba colocada en los cimientos del edificio, incluso a nivel del pozo de la fundación, porque estas muletas sirven como fuente de varios problemas despreciables y difíciles de comprender con confiabilidad, seguridad y simplemente la calidad del trabajo.
Pero, continuemos, delante de nosotros está mi estructura más "favorita": ¡la pila!
Pila
Eso es seguro, como Hoar dijo una vez sobre Null, que se trata de un error de mil millones de dólares, por lo que se puede decir lo mismo de la pila.
Esta es una de las estructuras más problemáticas utilizadas en las TIC y su máxima evitación en la práctica de crear hardware y software, hasta la erradicación completa, es altamente deseable.
Entonces, ¿cuál es exactamente el problema de la pila? Sí, exactamente lo mismo que con la cola. Las pilas son fundamentalmente imposibles de organizar. Tan pronto como haya una persona que prediga con precisión la cantidad de memoria que necesita la pila de cualquier programa arbitrario, personalmente me disculparé y escribiré un gran artículo que me equivoqué y pediré perdón.
Pero algo me dice que es poco probable que esto suceda en el futuro previsible.
Analicemos por qué necesitamos pilas. Sí, exactamente por lo mismo, para lo cual la cola. Este es un búfer. Es decir, estas son muletas para una mente perezosa que no quiere diseñar correctamente sistemas de software y hardware.
Entonces, la lección es esta: las recursiones deben evitarse cuando hay una solución iterativa obvia. Sin embargo, esto no significa que las recursiones deban eliminarse a toda costa. Hay muchos buenos ejemplos del uso de la recursividad, que demostraremos en secciones y capítulos posteriores. El hecho de que existan implementaciones de procedimientos recursivos en máquinas prácticamente no recursivas demuestra que, a efectos prácticos, cualquier programa recursivo puede transformarse en uno puramente iterativo. Sin embargo, esto requiere un trabajo explícito con la pila de recursión, y estas acciones a menudo oscurecen la esencia del programa, por lo que puede ser difícil de entender. Conclusión: los algoritmos que son de naturaleza recursiva y no iterativa, deben formularse como procedimientos recursivos.
Nicklaus Wirth. Algoritmos y estructuras de datos.
De acuerdo con el maestro sobre las opciones de conversión, no estoy de acuerdo con sus enfoques suaves para usar la pila.
Presento un teorema: cualquier algoritmo de pila se puede convertir en un bucle, y los que no se pueden convertir son malos.
La práctica de llamar a subprogramas con parámetros de paso a través de la pila debe detenerse, y la recursión que no se expande en un ciclo y otras prácticas ampliamente utilizadas también deben ir allí.
Podemos reemplazar la pila para los siguientes casos:
- Recursión, implementada en la forma de expandir el algoritmo de pila en un bucle con un bloque de datos que se cambia durante la ejecución del bucle.
- Si necesita transferir parámetros, organizará un sistema de firmware con mensajería. Y sobre los mensajes, vamos a las líneas que se describieron en la primera parte del artículo. Si realmente quieres una pila, entonces obviamente no debes empujar decenas y cientos de kilobytes de objetos allí, pero debes asignar memoria para esto normalmente, en el montón.
Al mismo tiempo, en el nivel superior, los programadores pueden usar cualquier estructura de datos, y corresponde a los compiladores transformarlos para excluir el uso de la pila.
Por supuesto, algunas de las oportunidades probablemente se perderán, pero esto, si se considera en detalle, no es un hecho.
Bloqueo
En 1995, con mi compañero de clase, formulé los principios para construir un sistema operativo que excluyera ambos paradigmas.
Los principios fueron los siguientes:
- Software - redes de procesos interactivos.
- La interacción de los procesos se lleva a cabo mediante el intercambio de mensajes.
- La red de procesos de interacción está organizada de la siguiente manera: las fuentes de mensajes primarios en dicha red son solo eventos del mundo exterior suministrados por equipos, los consumidores finales de mensajes son solo dispositivos que realizan acciones en el mundo exterior. Es decir, la red comienza en el mundo real y termina en él.
- Los procesos no pueden tener prioridades. Las prioridades solo pueden tener una red de procesos.
- La red nunca almacena mensajes en el búfer. El complejo de hardware y software debe organizarse de tal manera que logre procesar los mensajes al ritmo de su recepción desde el mundo exterior.
- El complejo de hardware es una red de nodos informáticos conectados por canales de comunicación.
- Cada nodo tiene un "costo", dependiendo de su potencia de procesamiento, tamaño de memoria, coeficiente de carga y peso, teniendo en cuenta los costos de su creación y mantenimiento.
- Cada canal de comunicación tiene un "costo", dependiendo de su ancho de banda, congestión y coeficiente de peso, teniendo en cuenta los costos de su creación y mantenimiento.
- El sistema operativo proporciona el inicio de procesos en respuesta a mensajes entrantes y enrutamiento de mensajes.
- El sistema operativo garantiza la distribución de procesos y mensajes entre nodos informáticos, optimizando la función f (cpu, mem) en la topología de la red, teniendo en cuenta el costo de transmitir el código de proceso y los mensajes al nodo.
- Dada la construcción del sistema, siempre puede calcular con precisión la cantidad de memoria requerida para el proceso. La cantidad requerida de tiempo de recuento se puede calcular con precisión en función del análisis del algoritmo.
Procesador BIND
Como parte de su carrera docente, junto con los estudiantes, una vez participó en el concurso del emulador de CPU IEEE. Se desarrolló un procesador sin pila de uso general de arquitectura Harvard utilizando un sistema de comando similar a los ARM anteriores. Además, la idea olvidada de transportadores se incorporó a la CPU y el procesador estaba equipado con 16 canales de recepción-transmisión de 8 bits.
En consecuencia, no hubo operaciones de llamada / devolución en el procesador. Solo fue posible una transición condicional / incondicional. Dado que casi nadie escribe en ensamblador en este momento, se suponía que todas las preguntas sobre la generación de un programa en código de máquina deberían asignarse al compilador.
El objetivo principal de este procesador era admitir sin problemas los principios del sistema operativo Blockout a nivel de hardware mediante la creación de una red de procesadores en el nodo informático local conectado por canales de comunicación a través de los cuales los procesos ya se distribuirán.
Conclusiones
El texto muestra los defectos fatales de las estructuras de datos de la cola y la pila. Se dan los principios de diseño de sistemas de software y hardware que permiten excluir estas estructuras de la práctica de la aplicación.
Este texto es, más bien, una recopilación de pensamientos que se han producido en el transcurso de una carrera de TI para, por así decirlo, llevar todo a un solo lugar.