ALGORITMOS DE SUSTITUCIÓN DE PÁGINAS :

LFU à Least Frequently Used.
MFU à Most Frequently Used.

CRITERIO LFU (Least Frequently Used).

· El sistema precisa de un contador que refleje el número de veces que se accede a una página (para ver cual es la menos usada). Este contador debe estar en la Tabla de Páginas.
· Problemas de este criterio : Si una página se usa mucho al principio y luego deja de usarse, toma un valor muy alto (al principio) el contador, y es difícil de echar esa página. Para solucionarlo se emplea un Algoritmo de Envejecimiento.
· Algoritmo de Envejecimiento : Emplea los bits de referencia para detectar e implementar el envejecimiento de la página para poder expulsarla.

{En la Tabla de Páginas en cada una de las entradas, hay un contador que indica el número de veces que se ha requerido. Un algoritmo adicional utiliza 1 byte por cada entrada, cada pulso de reloj se introduce un bit de referencia (lo copia, lo introduce por la izquierda, y pierde un bit por la derecha, de ese modo si entran ceros, se va degradando el valor).}







Ejemplo :Acceso a páginas 0-5 (6 páginas) :

Pulso de reloj 123456 (nº página)
0 101011
1 110010
2 110101 Bits de Referencia (cada uno de estos bits
3 100010 referencia a una de las páginas en un pulso
4 011000 determinado de reloj).

Pulso 0 1 2 3 4 etc...
Página

0 10000000 11000000 11100000 . . .
1 00000000 10000000 11000000 . . .
2 10000000 01000000 00100000 . . .
3 00000000 00000000 10000000 . . .
4 10000000 11000000 10000000 . . .
5 10000000 01000000 10100000 . . .


· Hay otros algoritmos que utilizan los bits de referencia y de modificaciones a la vez. Con ellos se establecen 4 clases :

Bit Referencia
Bit Modificación

( 0 0 ) à No usada. No modificar.
( 0 1 ) à No usada (recientemente). Si modificar.
( 1 0 ) à Si usada. No modificar.
( 1 1 ) à Si usada. Si modificar.


ASIGNACION DE PAGINAS POR EL SISTEMA OPERATIVO.

Dependerá del Hardware en cierta medida. Por ejemplo, en una arquitectura PC, tenemos CO, OP 1 y OP2, con lo que podríamos necesitar 3 páginas de memoria para ejecutar una cierta instrucción. Todos los procesos deben tener asignadas un número mayor de páginas que el mínimo estructural. Si un proceso desciende bajo el mínimo estructural, será llevado al almacenamiento secundario por el planificador a medio plazo.

Van a existir unos algoritmos de asignación de marcos de página para los procesos y unas políticas de asignación (sustitución) :
· Asignación Global : Para hacer una sustitución de marco de página podemos acceder tanto a los procesos que han provocado un error de marco de página como a los procesos que están funcionando correctamente en multiprogramación(cogemos marcos de otros procesos que están en funcionamiento)).
· Asignación Local : Sólo se puede acceder a los marcos de página asignados a un proceso que haya producido un error de marcos de página, y no a los marcos de página de los demás procesos en multiprogramación).

Políticas (algoritmos) de asignación de número de marcos :

· Algoritmo de Asignación Igualitaria o Equitativa : Depende del mínimo estructural y del grado de multiprogramación (número de procesos). Para asignar a los procesos, dividiremos entre el total de los procesos el total de los procesos el total de marcos disponibles en el sistema.
Ejemplo :
Procesos Necesita Le asignamos
1 50 marcos 20 marcos Nº Procesos = 4
2 50 marcos 20 marcos Total marcos disponibles = 80
3 15 marcos 20 marcos Marcos/Proceso = 20
4 5 marcos 20 marcos

· Algoritmo de Asignación Proporcional : Tiene en cuenta el mínimo estructural, el grado de multiprogramación (número de procesos), el tamaño de los procesos y la prioridad de estos.
Ejemplo :

Ai =Vi x (m /v) Ai : Marcos que asignamos al proceso i.
Vi : Páginas que necesita un proceso determinado (i).
v : Sumatorio de las páginas que necesitan cada uno
de los procesos.
m : Nº de marcos disponibles.

Procesos Necesita Le asignamos
1 50 marcos 33.3 marcos A1 =50 x 80 / 120 =33.3
2 50 marcos 33.3 marcos A2 =50 x 80 / 120 =33.3
3 15 marcos 9.9 marcos A3 =15 x 80 / 120 =9.9
4 5 marcos 3.3 marcos A4 =5 x 80 / 120 =3.3

El repartimiento puede ser dependiendo de :
· Solamente el Tamaño de los procesos. (Tamaño)
· Solamente a la Prioridad de los Procesos. (Prioridad)
· Ambos.(Tamaño x Prioridad). Es el ideal (es el más empleado).