Algorismes Substitució Pàgines: FIFO, Rellotge, LRU i Més

Algorisme FIFO

L'algorisme FIFO (First-In, First-Out) tracta els marcs de pàgina assignats a un procés considerant-los dins d'un buffer circular. Quan el buffer és ple, la pàgina més antiga és la seleccionada. No sempre coincideix amb la seleccionada per l'algorisme LRU (Least Recently Used). Una pàgina molt consultada sovint és la més antiga, per tant, serà expulsada amb relativa freqüència.

Implementació senzilla: Només es requereix un apuntador que es desplaci circularment a través de les pàgines assignades al procés.

Algorisme del Rellotge

El conjunt de marcs de pàgina candidats a ser substituïts es considera en un buffer circular. Quan una pàgina és substituïda, l'apuntador passa a assenyalar el següent element del buffer. Per a cada marc de pàgina es manté un bit d'ús. Aquest bit passa a valer 1 sempre que:

• La pàgina es carrega per primera vegada en el marc.
• Es fa referència a una posició de la pàgina.

En el moment de substituir una pàgina, es seleccionarà la primera que presenti el bit d'ús amb un valor 0. Durant aquesta recerca, els bits d'ús amb valor 1 es modifiquen i passen a valer 0.

Comparació: LRU, FIFO i Rellotge

Les proves numèriques tendeixen a demostrar que el rendiment de l'algorisme del Rellotge és proper al de l'LRU. S'han realitzat experiments suposant un nombre fix de marcs de pàgina per a cada procés i que el conjunt de pàgines substituïbles és el del propi procés que genera la fallada.

• Per a sistemes amb poques pàgines residents per procés (6 a 8), el nombre de fallades de pàgina per als sistemes FIFO és gairebé el doble que per a sistemes LRU.
• Aquest factor es redueix a 1 si es permeten més pàgines residents (més de 12). Però en aquesta situació caldrà molta més memòria principal per mantenir el nivell de multiprogramació.

Emmagatzematge Intermedi de Pàgines (Page Buffering)

Concepte

La política de substitució utilitzada és FIFO, però per millorar el rendiment, la pàgina substituïda es manté temporalment en memòria. Quan una pàgina s'ha de substituir, no s'elimina de la memòria; només es modifica el bit de presència i s'afegeix la referència a la pàgina a una de les dues llistes següents:

• La llista de pàgines buides: on hi ha totes les pàgines que no han sofert cap modificació des que s'han carregat en memòria i, per tant, no cal actualitzar-les al disc.
• La llista de pàgines modificades: que s'han d'actualitzar al disc en ser eliminades de la memòria.

La pàgina realment substituïda és la primera d'una de les llistes.

Funcionament

Quan es produeix una fallada de pàgina, abans d'accedir a memòria secundària, es consulten les dues llistes per veure si la pàgina és encara en memòria principal.

• Si hi és: només cal modificar el bit de presència i eliminar la corresponent entrada de la llista de pàgines lliures o modificades.
• Si no hi és: es carrega la pàgina en el marc ocupat per la primera pàgina de la llista de pàgines lliures. La pàgina s'elimina de la memòria principal i el cap de la llista es desplaça a la següent entrada.

La llista de pàgines modificades ofereix l'avantatge de permetre actualitzar la memòria secundària en bloc, en lloc de fer-ho individualment pàgina a pàgina.

Polítiques de Buidatge (Cleaning)

És aquella que es preocupa de quan s'ha d'actualitzar en la memòria secundària una pàgina modificada.

• Buidatge per demanda: Només s'actualitza just abans de ser substituïda. El procés haurà d'esperar el temps de dues transferències de pàgina.
• Buidatge previ: S'actualitzen abans de ser substituïdes, per tant, poden actualitzar-se per lots. No té gaire sentit si la majoria d'elles tornen a ser modificades abans de substituir-les de la memòria.
• Solució de compromís (amb emmagatzematge intermedi): Les pàgines de la llista de modificades s'actualitzen per lots i passen a la llista de pàgines lliures.

Polítiques de Gestió: Capacitat i Abast

Capacitat del Conjunt Resident

El Sistema Operatiu (SO) ha de fixar el nombre màxim de pàgines residents per a cada procés:

• Poques pàgines: taxa de fallades de pàgina gran.
• Moltes pàgines: nivell de multiprogramació baix.

Tipus de sistemes segons l'assignació:

• Sistemes amb assignació fixa: El nombre es decideix en el moment de creació del procés i depèn del tipus de procés (interactiu, per lots, etc.). En produir-se una fallada de pàgina, s'ha de substituir una de les pàgines del procés.
• Sistemes d'assignació variable: El nombre de marcs de pàgina varia en el temps d'execució: pot augmentar si les fallades de pàgina són moltes; pot reduir-se si la taxa de fallades de pàgina és petita. Requereix una major intervenció del SO i, per tant, més software i major sobrecàrrega del sistema.

Abast de la Substitució

És el conjunt de marcs de pàgina a considerar quan es produeix una fallada de pàgina.

• Política de substitució local: Només pot substituir les pàgines pròpies del procés que ha provocat la fallada de pàgina.
• Política de substitució global: Qualsevol pàgina pot ser substituïda, independentment del procés al qual pertanyi.

Combinacions Implementades

Les combinacions possibles d'abast de substitució i capacitat de conjunt resident inclouen:

• Capacitat fixa i abast local
• Capacitat variable i abast global
• Capacitat variable i abast local

Capacitat Fixa i Abast Local

Cada procés té un nombre de pàgines assignat. El nombre es determina en el moment de la càrrega del procés i depèn del tipus d'aplicació. En produir-se una fallada de pàgina, només considera substituïbles els marcs de pàgina propis del procés. El nombre de marcs es manté constant. Els algorismes de substitució són els estudiats (FIFO, LRU, Rellotge, etc.).

Problema: Com decidir prèviament el nombre de marcs de pàgina assignables?

• Si el nombre és baix, provocarà moltes fallades de pàgina.
• Si el nombre és alt, el nivell de multiprogramació és baix.

Capacitat Variable i Abast Global

És la combinació d'implementació més senzilla i l'han adoptada molts SO. El SO manté una llista de marcs de pàgina buits. Quan es produeix una fallada de pàgina, un marc de la llista s'assigna al procés que el sol·licita. El nombre de marcs assignats a un procés augmenta i, per tant, és de suposar que minvi la taxa de fallades de pàgina.

Qualsevol pàgina (excepte les bloquejades) pot ser substituïda; no hi ha cap criteri per decidir quin procés la perd. Amb un sistema d'emmagatzematge intermedi de pàgines es pot millorar el rendiment, ja que permet recuperar una pàgina que no s'hauria d'haver esborrat.

Estratègia del Conjunt de Treball

Una possible estratègia per a sistemes de capacitat variable és la coneguda com estratègia del conjunt de treball.

El conjunt de treball d'un procés en l'instant t, W(t, Δ), és el conjunt de pàgines a les quals el procés ha accedit en les darreres Δ unitats de temps virtual.

• Temps virtual: temps passat des que el procés està en execució.

En el moment de la càrrega del procés es fixa un nombre de marcs utilitzables (tant es pot usar paginació prèvia o paginació per demanda). En produir-se una fallada de pàgina, la pàgina a substituir es selecciona del conjunt resident del procés que provoca la fallada. Periòdicament, s'avalua el rendiment i es pot modificar el nombre de marcs de pàgines assignat al procés. És important definir els criteris per assignar el nombre inicial de marcs de pàgina i fixar els moments de possibles canvis.