Esquemas de asignación de Malloc

Question

Sí, estoy tomando un curso de sistemas informáticos. Tuve algunas preguntas sobre los diversos esquemas de asignación para implementar malloc. Para listas explícitas, si implemento malloc usando una pila tipo LIFO, ¿cuál es exactamente el propósito de tener punteros a la memoria liberada anterior? ¿Por qué necesitas listas doblemente vinculadas? ¿Las listas vinculadas por separado no funcionarían igual de bien?

Malloc lecture. Encontré este enlace en línea, puede ver la diapositiva 7 para ver de qué estoy hablando.

Al observar un esquema de asignación de listas segregadas, estas listas son unidireccionales, ¿verdad? Y también, ¿qué es exactamente el mecanismo de coalescencia? Como por ejemplo, si se liberan 4 palabras, ¿intentarías unirte primero al espacio libre a tu alrededor antes de volver a insertarlo en la respectiva lista de enlaces segregados? ¿O simplemente insertarías el bloque de 4 palabras en la sección '4 palabras' de la respectiva lista enlazada segregada?

Gracias.

Answer 1

Dado que un bloque liberado siempre tiene espacio para dos punteros, ¿por qué no vincular doblemente la lista? Simplifica el código de fusión para que no tenga que mantener un puntero al atravesar la lista. También permite atravesar la lista en cualquier dirección en caso de que haya una pista para qué final de la lista podría estar más cerca de comenzar la búsqueda. Un sistema oscuro que una vez miré mantuvo un puntero en el "medio", donde ocurrió la última actividad.

Al liberar un bloque. Hay sólo cuatro casos posibles:

• El bloque libre es adyacente después de un bloque libre.
• El bloque libre es adyacente antes un bloque libre.
• El bloque libre se encuentra entre y adyacente a ambos bloques libres antes y después de él.
• El bloque libre no es adyacente a ningún bloque libre.

Los efectos de coalescencia bloques libres adyacentes son:

• para reducir la longitud de la lista enlazada
• para reflejar con precisión el tamaño de un bloque libre sin tener que sobrecargar el asignador de mirar hacia adelante para ver si hay dos bloques adyacentes

La clasificación de un bloque libre en un servidor de longitud específica a menudo tiene beneficios, pero en la mayoría de las implementaciones prácticas, la unión es una prioridad para que alloc() la solicitud de un bloque de tamaño diferente no se niega de manera inapropiada cuando hay muchos bloques libres de diferentes tamaños.