Sistemas operativos modernos

bits en busca de una serie de k bits consecutivos en 0. Buscar el mapa una serie de cierta longi­ tud es una operación lenta (porque la serie podría cruzar fronteras de palabra en el mapa); éste es un argumento en contra del uso de mapas de bits. 4.2.2 Administración de memoria con listas enlazadas Otra forma de llevar el control de la memoria es mantener una lista enlazada de segmentos de memoria asignados y libres, donde un segmento es un proceso, o bien, un hueco entre dos pro­ cesos. La memoria de la figura 4-7a se representa en la figura 4-7c como lista enlazada de seg­ mentos. Cada entrada de la lista especifica un hueco (H) o un proceso (P), la dirección donde comienza, la longitud y un apuntador a la siguiente entrada. En este ejemplo, la lista de segmentos se mantiene ordenada por dirección. Este ordena­ miento tiene la ventaja de que cuando un proceso termina o se intercambia a disco, la actuali­ zación de la lista es sencilla. Por lo general, un proceso que termina tiene dos vecinos (excepto si está en el extremo superior o inferior de la memoria). Dichos vecinos podrían ser procesos o huecos, lo que da pie a las cuatro combinaciones de la figura 4-8. En la figura 4-8a, la actua­ lización de la lista requiere sustituir una P por una H. En las figuras 4-8b y 4-8c, dos entradas se funden en una sola, y la longitud de la lista se reduce en l . En la figura 4-8d se fusionan tres entradas y se eliminan dos elementos de la lista. Puesto que la ranura correspondiente al pro­ ceso que terminó en la tabla de procesos por lo general apunta a la entrada de la lista que co­ rresponde al proceso mismo, podría ser mejor mantener una lista doblemente enlazada, no una de enlace sencillo como la de la figura 4-7c. Esa estructura facilita la localización de la entra­ da anterior para determinar si puede haber una fusión. Antes de que X termine Después de que X termine (a) (b) A X B A X X B X cambia a cambia a cambia a A B A B Figura 4-8. Cuatro combinaciones de vecinos para el proceso que termina, X. Si los procesos y huecos se mantienen en una lista ordenada por dirección, pueden usarse varios algoritmos para asignar memoria a un proceso recién creado (o a un proceso existente que se intercambia a memoria). Damos por hecho que el administrador de memoria sabe cuán­ ta memoria debe asignar. El algoritmo más simple es el de primer ajuste. El administrador de memoria explora la lista de segmentos hasta hallar un hueco lo bastante grande. Luego el hueco se divide en dos partes, una para el proceso y una para la memoria desocupada, salvo en el caso poco probable de que el ajuste sea exacto. Este algoritmo es rápido porque la búsque­ da es lo más corta posible.