Determinación de tamaños de tramas de memoria para la asignación dinámica de memoria limitando la fragmentación interna.

Un procedimiento para determinar el tamaño de cada una de un número predeterminado de tramas de memoria de una memoria (12),

donde dicha memoria (12) está adaptada para almacenar bloques de datos en tramas de datos, de un número predeterminado de diferentes tamaños a asignar, comprendiendo dicho procedimiento:

determinar la distribución de tamaños de bloques de datos para al menos un conjunto de bloques de datos (101 a 106, 111 a 117, 121 a 125) de al menos un proceso o señal, teniendo cada bloque de datos de dicho conjunto de bloques de datos un tamaño particular, caracterizado por:

eliminar iterativamente al menos un tamaño de bloque de datos de la distribución de tamaños de bloques de datos, hasta que el número de tamaños de bloques de datos de dicha distribución corresponda al número de tamaños del número predeterminado de tramas de memoria, mediante la realización iterativa de: 1) calcular, para cada bloque de datos que tenga un tamaño P de bloque de datos, un valor de holgura predicha (PS) usando la fórmula:

PS ≥ (Numero de bloques de datos de tamaño P) x ((tamaño de bloque de datos a fusionar con el tamaño P de bloque de datos) - (tamaño P de bloque de datos)),

donde el tamaño de bloque de datos a fusionar con el tamaño P de bloque de datos es mayor que el tamaño P de bloque de datos,

2) seleccionar dos tamaños de bloques de datos a fusionar, usando uno cualquiera de los siguientes criterios, 20 y que corresponden a:

- el menor valor calculado de holgura predictiva (PS),

- el menor valor predictivo de holgura (SPV), donde el valor predictivo de holgura es la suma de los valores calculados de holgura predicha (PS), excepto el valor calculado de holgura predicha para el tamaño de bloque de datos más grande de la distribución de tamaños de bloques de datos que quedaría si un cierto tamaño P de bloque de datos se eliminase, o

- el menor valor ponderado de holgura predictiva (WSPV), calculado usando la siguiente fórmula:

WSPV ≥ c1 (PS) + c2 (SPV), donde c1 y c2 son factores de ponderación,

3) fusionar los dos tamaños de bloques de datos correspondientes para generar un tamaño de bloque de datos fusionado, y

4) determinar cada tamaño de las tramas de memoria como un tamaño de los tamaños de bloques de datos de dicha distribución, que quedan después de dicha eliminación, y de modo que los tamaños de las tramas de memoria sean diferentes.

Determinación de tamaños de tramas de memoria para la asignación dinámica de memoria limitando la fragmentación interna

Campo técnico de la invención

La presente invención se refiere a un procedimiento para determinar los tamaños de las tramas de memoria, que tienen tamaños predefinidos y se utilizan para el almacenamiento de bloques de datos en una memoria. La invención también se refiere a un dispositivo de procesamiento adaptado para implementar el procedimiento según la invención.

Descripción de la técnica relacionada

La asignación dinámica de memoria se utiliza para la asignación de memoria en un sistema en tiempo real a medida que se produce una necesidad de recursos de memoria. La asignación dinámica de recursos de memoria en un dispositivo de asignación de memoria puede estar limitada a un cierto número de tamaños predefinidos de tramas de memoria, o a un cierto número de tramas de memoria que tienen diferentes tamaños, es decir, cada trama de memoria puede almacenar un cierto número de bits de datos. La capacidad de almacenamiento de cada trama de la memoria puede no corresponder necesariamente a su tamaño real, pues ciertos bits de la trama de memoria se pueden usar para la gestión de la memoria. Tener tramas de memoria con tamaños predefinidos hace que sea posible proporcionar un asignador de memoria que se comporta de manera muy predecible, en términos de tiempo de ejecución, para la asignación y des-asignación de memoria. Sin embargo, también tiene un impacto en el rendimiento.

Un inconveniente con un esquema de asignación de memoria que utiliza tramas de memoria con tamaños predefinidos es un fenómeno llamado fragmentación interna u holgura (en inglés slack). Esto significa que si un tamaño de memoria solicitado, es decir, el tamaño de un bloque de datos que va a almacenarse, es menor que el tamaño de la trama más pequeña de memoria que tiene la capacidad de almacenar el bloque de datos de ese tamaño, el número de los octetos que difieren no será utilizado, es decir, se convierte en holgura, que también es conocida como fragmentación interna.

El problema con la holgura tiene impacto en todas las áreas en donde es utilizada la asignación dinámica de memoria. Dos de estas áreas están en el procesamiento de procesos donde la memoria se pierde debido a la holgura para cada proceso, y en almacenes temporales de señales donde la memoria se pierde como holgura para cada señal asignada. Sin embargo, son conocidos los requisitos de memoria de un determinado proceso. Por lo tanto, es posible establecer los tamaños de las tramas de memoria de tal manera que se produzca tan poca holgura como sea posible. Además, si se conocen los posibles tamaños de los bloques de datos de una señal, los tamaños de las tramas de memoria se pueden fijar en una configuración óptima predicha, mediante la predicción de los tamaños de señal, por ejemplo, mediante la ejecución del sistema en el que se debería implementar el dispositivo de asignación dinámica de memoria, para diferentes casos de uso.

En los sistemas conocidos en la técnica, los tamaños de las tramas de memoria pueden ser adivinados por un ser humano que observa todos los diferentes tamaños de bloques de datos de un proceso/señal y el número de bloques de datos de cada tamaño de bloque de datos y, a continuación, recorta los tamaños de las tramas de memoria hasta los tamaños adecuados. Debe hacer esto una y otra vez para cada nuevo conjunto de tamaños de bloques de datos de un proceso/señal. Esto es un problema, ya que requiere mucho tiempo, y a veces los tamaños de las tramas de memoria, determinados manualmente, no son óptimos en absoluto.

En los sistemas integrados, tales como un terminal móvil, en los que los recursos de memoria son limitados, la configuración de un dispositivo de asignación dinámica de memoria en tamaños óptimos de tramas de memoria predefinidas tiene un gran impacto sobre la holgura. En tal sistema, el número de procesos puede, por ejemplo, estar en el intervalo entre 10 y 30 para un sistema pequeño, y en hasta cientos de procesos para un sistema más grande. Además, cada proceso puede comprender varios cientos de tamaños distintos de bloques de datos, pero los diferentes tamaños de las tramas de memoria sólo pueden estar en la gama entre unos pocos hasta algunas decenas. De manera similar, el número de tamaños diferentes de los bloques de datos de señales puede estar en la misma gama que el número de tamaños diferentes de bloques de datos de un proceso. Los ahorros en términos de recursos de memoria en este tipo de dispositivos electrónicos tienen un impacto sobre los costes de producción; el impacto es más grande cuanto mayor es el sistema. Si se pueden limitar los recursos de memoria debido a la reducción de la holgura, puede reducirse el coste de producción.

Un algoritmo según la técnica anterior para determinar automáticamente la cantidad y el tipo de diferentes recursos de sistema de un sistema se describe en el documento xp010588126, "Hardware-Software Co-Synthesis of low power real-time distributed embedded system with dynamically reconfigurable FPGAs" ["Co-síntesis de hardware y software de sistemas integrados distribuidos en tiempo real de baja energía, con FPGA reconfigurables dinámicamente"], CONFERENCIA DE AUTOMATIZACIÓN DEL DISEÑO, 2002. Los recursos de sistema pueden

comprender FPGA [Formaciones de Compuertas Programables en el Terreno], procesadores y otros recursos de sistema dinámicamente programables. El algoritmo también comprende asignar tareas que deberían llevarse a cabo a los diferentes recursos de sistema.

El documento XP-000903927 revela un algoritmo para correlacionar una especificación de sistema de velocidad única restringida en el tiempo con una especificación de sistema heterogéneo. El sistema heterogéneo comprende múltiples limitaciones de recursos, tales como el tamaño de memoria de los procesadores, el tamaño del almacén temporal de enlaces de comunicación, y el área de los ASIC [Circuitos Integrados Específicos de la Aplicación].

El documento XP-002262845 se refiere a la fragmentación de memoria. Se revela que el tamaño de los bloques de memoria tiene Implicaciones para la fragmentación.

El documento US-A-6 088 777 revela un sistema de memoria y un procedimiento de gestión para la asignación dinámica de memoria. Un área fija de memoria se divide en un número entero de clases. Cada clase de memoria incluye bloques de memoria del mismo tamaño, enlazados entre sí por punteros. Los tamaños de bloques de memoria son diferentes para cada clase. Los tamaños de los diferentes bloques de memoria se seleccionan para que sean conformes a la CPU y el acceso a la memoria, excepto al hardware, asi como para asimilar los diversos tamaños de datos que se espera procesar para una aplicación particular.

Resumen de la invención

Es un objeto de la Invención proporcionar un procedimiento y un dispositivo para determinar el tamaño de al menos una trama de memoria para un medio de memoria, que cause tan poca holgura como sea posible cuando los bloques de datos de diferentes tamaños se almacenen en tramas de memoria que tienen dlcho(s) tamaño(s) determinado (s) en dicho medio de memoria.

De acuerdo con un primer aspecto de la invención, el objeto se logra mediante un procedimiento para determinar el tamaño de cada una entre un número predeterminado de tramas de memoria a asignar para el almacenamiento de bloques de datos en una memoria. El procedimiento comprende la determinación de una distribución de tamaños de bloque de datos para al menos un conjunto de bloques de datos. Por lo menos un tamaño de bloque de datos de la distribución de tamaños de bloques de datos se elimina de forma iterativa hasta que el número de tamaños de bloques de datos corresponda al número de tamaños de las tramas de memoria. Dicho al menos un tamaño de bloque de datos se fusiona con un primer tamaño de bloque de datos de la distribución, para generar un tamaño fusionado de bloque de datos. El primer tamaño de bloque de datos es más grande que dicho al menos un tamaño de bloque de datos y el tamaño del tamaño fusionado de bloque de datos corresponden al primer tamaño de bloque de datos. Los tamaños de bloques de datos a fusionar se seleccionan por medio de un algoritmo de predicción de holgura. Los tamaños de las tramas de memoria son determinados como los tamaños de bloques de datos de la distribución que quedan después de la eliminación.

El procedimiento también puede comprender añadir el número de bloques de datos que tienen dicho al menos un tamaño de bloque de datos al número de bloques de datos que tienen el primer tamaño de bloque de datos cuando... [Seguir leyendo]

1. Un procedimiento para determinar el tamaño de cada una de un número predeterminado de tramas de memoria de una memoria (12), donde dicha memoria (12) está adaptada para almacenar bloques de datos en tramas de datos, de un número predeterminado de diferentes tamaños a asignar, comprendiendo dicho procedimiento:

determinar la distribución de tamaños de bloques de datos para al menos un conjunto de bloques de datos (101 a 106, 111 a 117, 121 a 125) de al menos un proceso o señal, teniendo cada bloque de datos de dicho conjunto de bloques de datos un tamaño particular, caracterizado por:

eliminar iterativamente al menos un tamaño de bloque de datos de la distribución de tamaños de bloques de datos, hasta que el número de tamaños de bloques de datos de dicha distribución corresponda al número de tamaños del número predeterminado de tramas de memoria, mediante la realización iterativa de:

1) calcular, para cada bloque de datos que tenga un tamaño P de bloque de datos, un valor de holgura predlcha (PS) usando la fórmula:

PS = (Numero de bloques de datos de tamaño P) x ((tamaño de bloque de datos a fusionar con el tamaño P de bloque de datos) - (tamaño P de bloque de datos)), donde el tamaño de bloque de datos a fusionar con el tamaño P de bloque de datos es mayor que el tamaño P de bloque de datos,

2) seleccionar dos tamaños de bloques de datos a fusionar, usando uno cualquiera de los siguientes criterios, y que corresponden a:

el menor valor calculado de holgura predictiva (PS),

el menor valor predictivo de holgura (SPV), donde el valor predictivo de holgura es la suma de los valores calculados de holgura predicha (PS), excepto el valor calculado de holgura predicha para el tamaño de bloque de datos más grande de la distribución de tamaños de bloques de datos que quedaría si un cierto tamaño P de bloque de datos se eliminase, o

el menor valor ponderado de holgura predictiva (WSPV), calculado usando la siguiente fórmula: WSPV = c1 (PS) + c2 (SPV), donde c1 y c2 son factores de ponderación,

3) fusionar los dos tamaños de bloques de datos correspondientes para generar un tamaño de bloque de datos fusionado,

y

4) determinar cada tamaño de las tramas de memoria como un tamaño de los tamaños de bloques de datos de dicha distribución, que quedan después de dicha eliminación, y de modo que los tamaños de las tramas de memoria sean diferentes.

2. El procedimiento según la reivindicación 1, que comprende, para cada iteración, añadir el número de bloques de datos que tienen dicho al menos un tamaño de bloque de datos, al número de bloques de datos que tienen el otro tamaño de bloque de datos, cuando dicho al menos un tamaño de bloque de datos se fusiona con dicho otro tamaño

de bloque de datos.

3. El procedimiento según cualquiera de las reivindicaciones anteriores, que comprende, para cada tamaño de bloque de datos, excepto el tamaño de bloque de datos más grande de dicha distribución, y para cada iteración, determinar la holgura predicha que se produciría si dicho al menos un tamaño de bloque de datos se incorporase a un tamaño de bloque de datos más grande de dicha distribución determinada.

4. El procedimiento según la reivindicación 3, en el que el tamaño de bloque de datos más grande es el siguiente tamaño de bloque de datos más grande de dicha distribución determinada, que no haya sido eliminado.

5. El procedimiento según cualquiera de las reivindicaciones anteriores, en el que el algoritmo de predicción de holgura comprende, para cada iteración, determinar cuál de los tamaños de bloques de datos de dicha distribución, que no haya sido eliminado, generaría la holgura más baja si se incorporase a un tamaño de bloque de datos más grande, y seleccionar dicho tamaño de bloque de datos determinado para que sea uno de dicho al menos un tamaño de bloque de datos.

6. El procedimiento según cualquiera de las reivindicaciones anteriores, en el que el algoritmo de predicción de holgura comprende, para cada iteración, generar un valor de predicción de holgura indicativo de la holgura total predlcha para los tamaños de bloques de datos de la distribución que no se hayan eliminado.

7. El procedimiento según cualquiera de las reivindicaciones anteriores, en el que el conjunto de bloques de datos se refiere a bloques de datos para al menos un proceso predeterminado de un sistema que comprende una memoria (12).

8. El procedimiento según cualquiera de las reivindicaciones 1 a 6, en el que el conjunto de bloques de datos se refiere a bloques de datos de al menos una señal.

9. El procedimiento según cualquiera de las reivindicaciones anteriores, que comprende determinar la distribución de tamaños de bloques de datos en tiempo de ejecución cuando los bloques de datos se escriben en la memoria

10. El procedimiento según cualquiera de las reivindicaciones anteriores, en el que el efecto, en al menos una posible distribución siguiente de tamaños de bloques de datos, de la eliminación de un cierto tamaño de bloque de datos de una distribución actual se comprueba antes de eliminar cualquier tamaño de bloque de datos en una distribución actual.

11. El procedimiento según la reivindicación 10, que comprende cambiar dinámicamente el número de posibles distribuciones siguientes de tamaños de bloques de datos para comprobar la independencia del número de tamaños de bloques de datos de la distribución actual de tamaños de bloques de datos.

12. El procedimiento según la reivindicación 10 u 11, que comprende determinar cada posible distribución de tamaños de bloques de datos que pueda generarse sobre la base de la distribución actual de tamaños de bloques de datos, y generar un valor de predicción de holgura para cada una de las actuales y las posibles distribuciones de tamaños de bloques de datos.

13. El procedimiento según la reivindicación 12, que comprende seleccionar un primero de dichos al menos un tamaño de bloque de datos de la distribución actual de tamaños de bloques de datos, como el tamaño de bloque de datos que generaría la más baja holgura predicha en total, en la iteración actual y la siguiente.

14. El procedimiento según cualquiera de las reivindicaciones 10 a 13, que comprende seleccionar un segundo de dichos al menos un tamaño de bloque de datos a partir de la siguiente iteración, y fusionar dicho segundo tamaño de bloque de datos con otro tamaño de bloque de datos de la siguiente distribución de bloques de datos.

15. El procedimiento según cualquiera de las reivindicaciones anteriores, en el que el otro tamaño de bloque de datos es el tamaño de bloque de datos, que queda en la distribución, después del tamaño de bloque de datos más grande de dichos al menos un tamaño de bloques de datos dentro de dicha distribución.

16. Un dispositivo (13) de procesamiento configurado para determinar el tamaño de cada una de un número predeterminado de tramas de memoria de una memoria (12), según las etapas del procedimiento de cualquiera de las reivindicaciones 1 a 15.

17. Un producto de programa de ordenador que comprende medios de código de programa de ordenador, para ejecutar el procedimiento según cualquiera de las reivindicaciones 1 a 15 cuando dichos medios de código de programa de ordenador son ejecutados por un dispositivo electrónico que tiene capacidades de programa de ordenador.

18. El producto de programa de ordenador según la reivindicación 17, en el que los medios de código de programa de ordenador están realizados en un medio legible por ordenador.