Sistemas operativos modernos

Una variación menor del primer ajuste es el siguiente ajuste. El funcionamiento es similar al del primer ajuste, sólo que el algoritmo recuerda en qué punto de la lista se quedó la última vez que encontró un hueco apropiado. La siguiente vez que se le pide hallar un hueco, inicia la búsqueda en ese punto de la lista, no en el principio, como lo hace el algoritmo de primer ajuste. Simulaciones efectuadas por Bays ( 1977) muestran que el desempeño del algoritmo de siguiente ajuste es un poco más lento que el de primer ajuste. Otro algoritmo muy conocido es el de mejor ajuste. En este caso se explora toda la lista y se escoge el hueco más pequeño que alcance. En lugar de dividir un hueco grande que po­ dría necesitarse después, el algoritmo trata de hallar un hueco de tamaño cercano al requerido. Como ejemplo del primer ajuste y el mejor ajuste, consideremos otra vez la figura 4-7. Si se necesita un bloque de tamaño 2 , el algoritmo de primer ajuste escogerá el bloque que co­ mienza en 5, pero el de mejor ajuste escogerá el que comienza en 18. El algoritmo de mejor ajuste es más lento que el de primer ajuste porque debe examinar to­ da la lista cada vez que se le invoca. Lo que resulta un tanto sorprendente es que desperdicia más memoria que el primer ajuste o el siguiente ajuste porque tiende a saturar la memoria de peque­ ños huecos que no sirven de nada. En promedio, el primer ajuste crea los huecos más grandes. Para resolver el problema de dividir un hueco de tamaño cercano al requerido en un proce­ so y un hueco diminuto, podríamos considerar el peor ajuste, es decir, siempre escoger el hue­ co más grande disponible, de modo que el hueco restante sea lo bastante grande como para ser úfil. Las simulaciones han demostrado que el peor ajuste tampoco es una idea muy buena. Los cuatro algoritmos pueden acelerarse manteniendo listas disfintas para los procesos y para los huecos. Así, se dedica toda la energía a inspeccionar huecos, no procesos. El precio inevitable que se paga esta aceleración de asignación es la mayor complejidad y la lenfitud de la liberación de memoria, pues un segmento liberado debe quitarse de la lista de procesos e in­ sertarse en la lista de huecos. Si se mantienen Ustas distintas para procesos y huecos, la lista de huecos podría mante­ nerse ordenada por tamaño, para que el algoritmo de mejor ajuste sea más rápido. Si este al­ goritmo examina la lista de huecos del más pequeño al más grande, tan pronto como encuentre un agujero apropiado sabrá que es el más pequeño que puede usarse y, por lo tanto, es el me­ jor ajuste. No es preciso buscar más, como en el esquema de una sola lista. Si la lista de hue­ cos está ordenada por tamaño, los algoritmos de primer ajuste y mejor ajuste tienen la misma rapidez, y el algoritmo de siguiente ajuste no fiene caso. Si los huecos se mantienen en listas separadas de los procesos, puede efectuarse una pe­ queña optimización. En lugar de tener una estructura de datos aparte para mantener la lista de huecos, como se hace en la figura 4-7c, pueden usarse los huecos mismos. La primera palabra de cada hueco podría indicar su tamaño, y la segunda, un apuntador al siguiente hueco. Los no­ dos de la lista de la figura 4-7c, que requieren tres palabras y un bit (P/H), son innecesarios. Otro algoritmo de asignación es el de ajuste rápido, que mantiene listas individuales para algunos de los tamaños que se solicitan en forma más común. Por ejemplo, podría mantenerse una tabla de n elementos, donde el primero es un apuntador a la cabeza de una lista de huecos de 4 KB, el segundo es un apuntador a una lista de huecos de 8 KB, el tercero es un apuntador a una lista de huecos de 12 KB, y así en forma sucesiva. Los huecos de, digamos, 21 KB po­ drían colocarse en la lista de 20 KB, o bien, en una lista especial de huecos de tamaño irregu-