Una cola , también llamada lista vinculada , es (típicamente, pero no necesariamente) una serie de estructuras de memoria (a menudo algún tipo de bloque de control ) vinculadas por punteros (direcciones) que forman parte de las estructuras vinculadas. Una cola (lista) sin elementos vinculados es una cola vacía (lista).
Nota sobre la notación: en los siguientes ejemplos / imágenes, un “gancho” significa una celda de memoria, un “cubo” que cuelga de un gancho significa que la celda de memoria contiene algún tipo de valor y una ” etiqueta de dirección ” que cuelga de un gancho significa que la celda de memoria contiene un puntero (una dirección de memoria).
Las colas suelen estar “ancladas” (por lo tanto, los símbolos de “anclaje” en estas imágenes) en un encabezado de cola , que generalmente se coloca en una ubicación de memoria globalmente conocida, mientras que las estructuras de datos vinculadas pueden ubicarse en cualquier lugar de la memoria :
La estructura de lista más simple es la lista vinculada individualmente , vinculada desde su encabezado, con el último elemento de la lista de alguna manera marcando “final de la lista” (aquí simbolizado por el símbolo “fundamental”). El enlace de listas enlazadas individualmente tiene un solo puntero, la dirección del “siguiente elemento enlazado”. Para encontrar un elemento de lista enlazado individualmente, la lista debe atravesarse desde el encabezado y hacia abajo:
Las listas enlazadas por separado pueden ser engorrosas para trabajar, y generalmente solo se usan para colas simples LIFO ( “Último en entrar , primero en salir” ) (análoga a una memoria “push down, pop up” o pila de registros).
Las listas doblemente enlazadas (también llamadas listas circulares ) son más flexibles, ya que pueden atravesarse desde cualquier extremo: hacia adelante (comenzando con el elemento de cabeza ) o hacia atrás (comenzando con el elemento de cola ). En las listas enlazadas individualmente y doblemente, cuando los punteros de la cabeza y la cola apuntan al encabezado , la lista está vacía (duuh).
La dirección del último elemento de la cola (en el encabezado de la cola, así como en cada estructura en cola) facilita la implementación de las colas FIFO ( “Primero en entrar , Primero en salir” (también conocido como FCFS (” Primero llegado, primero servido “)) .
La mayoría de los sistemas operativos mantienen una importante “cola de prioridad” llamada Lista de tiempos . La implementación puede variar, pero el resultado neto es el mismo: para administrar y realizar un seguimiento de las duraciones de tiempo (algo así como “temporizadores de huevo”: para generar alguna acción después de que haya transcurrido un intervalo de tiempo especificado).
Esto generalmente se realiza en cooperación con un controlador de interrupción de tiempo , que interrumpe el procesador a intervalos regulares, para manipular la lista de tiempo y tomar varias medidas. Los elementos en la lista de tiempo pueden ser cualquier estructura de datos, llamados elementos de lista de tiempo (TLE) mientras están vinculados en la lista.
En la implementación mostrada ( Guardian , el sistema operativo Tandem NonStop (ahora llamado NonStop OS para los servidores HP NonStop )): la unidad de tiempo Guardian se llama ” tick ” (= 0.01 segundo), y se establece el valor ” intervalo de temporizador ” mostrado a cierto número de ticks cuando el temporizador está “configurado” (100 ticks = un segundo). La lista de tiempo está organizada de modo que el intervalo total que cualquier TLE “esperará” es la suma de su propio valor de temporizador y todos los valores de temporizador de TLE antes de que aparezca en la lista (si esto suena complicado (realmente no lo es), la imagen a continuación puede aclarar).
En cada interrupción de tiempo, el controlador de interrupción de tiempo resta el número de tics transcurridos desde la última interrupción de tiempo , del intervalo del temporizador del TLE superior de la lista de tiempos , y si el resultado es cero o negativo, ese TLE se desvincula (se quita el tiempo lista), y el siguiente TLE a su vez se convierte en el TLE superior: luego se toman algunas medidas en nombre del TLE con el “temporizador caducado”, como “despertar” un proceso que espera que el temporizador caduque.
Si se cancela un temporizador antes de su vencimiento, la función del sistema operativo que elimina el TLE de la lista de Tiempo simplemente agrega el valor del depósito del temporizador del TLE vencido al valor del depósito del siguiente TLE, y todo es genial, muy eficiente.
Otra lista prioritaria doblemente vinculada importante , presente de una forma u otra en la mayoría de los sistemas operativos, es la Lista Lista . Las estructuras vinculadas a esta lista suelen ser algún tipo de Bloque de control de proceso (PCB), que representa un programa que ejecuta instrucciones.
La lista Lista está ordenada por un valor de prioridad de proceso (parte de la estructura vinculada), con el proceso de máxima prioridad primero en la lista (en Guardian, la prioridad varía de 0 a 255, con prioridades> 199 reservadas para procesos “privilegiados”) .
Cuando se inicia un proceso por primera vez, se le asigna un valor de prioridad, y cuando el proceso está listo para ejecutarse (por el sistema operativo), se inserta en la lista Listo de acuerdo con esta prioridad, y se invoca el controlador de interrupción Dispatcher (por el sistema operativo).
En cada interrupción del Despachador , lo último que hace el Despachador es cargar los registros de la IPU con los valores guardados, en el momento en que se desactivó el proceso, en la PCB enlazada superior de la lista Listo , luego sale. Esto activa ese proceso (es decir, obtener el control de la IPU, ejecutar las instrucciones del programa).
Cuando (en algún momento posterior) ese proceso necesita esperar algún otro evento ( por ejemplo, la finalización de alguna operación de E / S), la función (privilegiada) WAIT () elimina el PCB de la lista Listo y lo inserta en algunos lista de espera (que puede ser la lista de Tiempo), luego invoca el Despachador , lo que hará que el PCB de la lista Listo ahora superior sea el proceso activo. Y así continúa.
Hay más en las colas y listas que las muestras descritas aquí … Si desea detalles, no dude en descargar mi antiguo curso de GAME ( Guardian Architecture Made Easy ) de mis carpetas de box.com ( GAME (Public). Zip ): sin condiciones , ¡Puse toda la bola de JUEGO en el dominio público cuando me retiré del trabajo en la computadora, hace siete años!
Nota al margen: mi antiguo material GAME todavía está en uso. Es un testimonio de la fuerza y la resistencia de la arquitectura TNS (Tandem NonStop) que su arquitectura de sistema operativo distribuido basado en “Requester-Server” no ha cambiado fundamentalmente desde su inicio en 1974: el hardware ha evolucionado a pasos agigantados (tanto velocidad , capacidad y confiabilidad), pero aparte de muchas funciones agregadas desde entonces, su entorno de software de nivel de aplicación es exactamente el mismo : puede tomar un archivo de objeto antiguo, compilado en y para el antiguo NonStop / I de 1974, y se ejecuta sin problemas: pero mucho más rápido, ¡en la última versión de los sistemas NonStop Server de HP!
