Algorisme de substitució de pàgines

En un sistema operatiu d'ordinador que utilitza paginació per a la gestió de la memòria virtual, els algorismes de substitució de pàgines decideixen quines pàgines de memòria s'han de paginar, de vegades anomenades intercanvi o escriptura al disc, quan s'ha d'assignar una pàgina de memòria. La substitució de la pàgina es produeix quan una pàgina sol·licitada no es troba a la memòria (error de pàgina) i no es pot utilitzar una pàgina lliure per satisfer l'assignació, ja sigui perquè no n'hi ha, o perquè el nombre de pàgines lliures és inferior a algun llindar.

Quan es torna a fer referència a la pàgina que s'ha seleccionat per a la substitució i es va extreure de pàgina, s'ha d'introduir (llegir des del disc) i això implica esperar que finalitzi l'E/S. Això determina la qualitat de l'algoritme de substitució de pàgines: com menys temps s'espera per a les entrades de pàgina, millor serà l'algorisme. Un algorisme de substitució de pàgines analitza la informació limitada sobre els accessos a les pàgines que proporciona el maquinari i intenta endevinar quines pàgines s'han de substituir per minimitzar el nombre total de pàgines perdudes, alhora que equilibra això amb els costos (emmagatzematge principal i temps del processador) de el propi algorisme.

El problema de substitució de pàgines és un problema típic en línia des de la perspectiva de l'anàlisi competitiva en el sentit que es coneix l'algorisme determinista òptim.

Història

Els algorismes de substitució de pàgines van ser un tema candent de recerca i debat als anys 60 i 70. Això va acabar principalment amb el desenvolupament d'aproximacions LRU (utilitzades menys recentment) sofisticades i algorismes de conjunt de treball. Des d'aleshores, es van invalidar algunes suposicions bàsiques fetes pels algorismes de substitució de pàgines tradicionals, donant lloc a un renaixement de la investigació. En particular, les tendències següents en el comportament del maquinari subjacent i del programari a nivell d'usuari han afectat el rendiment dels algorismes de substitució de pàgines:

La mida de l'emmagatzematge primari ha augmentat en diversos ordres de magnitud. Amb diversos gigabytes de memòria primària, els algorismes que requereixen una comprovació periòdica de tots i cadascun dels marcs de memòria són cada cop menys pràctics.
Les jerarquies de memòria han crescut. El cost d'una pèrdua de memòria cau de la CPU és molt més car. Això agreuja el problema anterior.
La localitat de referència del programari d'usuari s'ha debilitat. Això s'atribueix principalment a la difusió de tècniques de programació orientada a objectes que afavoreixen un gran nombre de funcions petites, l'ús d'estructures de dades sofisticades com arbres i taules hash que tendeixen a donar lloc a patrons de referència de memòria caòtics i l'arribada de la recollida d'escombraries que va canviar dràsticament. comportament d'accés a la memòria de les aplicacions.

Els requisits per als algorismes de substitució de pàgines han canviat a causa de les diferències en les arquitectures del nucli del sistema operatiu. En particular, la majoria dels nuclis de SO moderns tenen memòria virtual unificada i memòria cau del sistema de fitxers, la qual cosa requereix que l'algoritme de substitució de pàgines seleccioni una pàgina entre les pàgines tant dels espais d'adreces virtuals del programa d'usuari com dels fitxers en memòria cau. Aquestes últimes pàgines tenen propietats específiques. Per exemple, es poden bloquejar o poden tenir requisits d'ordre d'escriptura imposats per l'escriptura en el diari. A més, com que l'objectiu de la substitució de pàgines és minimitzar el temps total d'espera per a la memòria, s'ha de tenir en compte els requisits de memòria imposats per altres subsistemes del nucli que assignen memòria. Com a resultat, la substitució de pàgines als nuclis moderns (Linux, FreeBSD i Solaris) acostuma a funcionar al nivell d'un assignador de memòria del nucli de propòsit general, més que al nivell superior d'un subsistema de memòria virtual.

Algoritmes de substitució de pàgines

Hi ha diversos algorismes de substitució de pàgines: ^[1]

L'algoritme de substitució de pàgines teòricament òptim

L'algoritme de substitució de pàgines teòricament òptim (també conegut com OPT, algorisme de substitució clarivident o política de substitució òptima de pàgines de Bélády) ^[2]^[3] és un algorisme que funciona de la següent manera: quan s'ha de canviar una pàgina, el sistema operatiu intercanvia la pàgina el proper ús de la qual es produirà més lluny en el futur. Per exemple, una pàgina que no s'utilitzarà durant els propers 6 segons es canviarà per una pàgina que s'utilitzarà durant els propers 0,4 segons.

No s'ha utilitzat recentment

L'algorisme de substitució de pàgines no utilitzades recentment (NRU) és un algorisme que afavoreix mantenir a la memòria les pàgines que s'han utilitzat recentment. Aquest algorisme funciona segons el principi següent: quan es fa referència a una pàgina, s'estableix un bit de referència per a aquesta pàgina, marcant-la com a referenciada. De la mateixa manera, quan es modifica una pàgina (s'escriu a), s'estableix un bit modificat. La configuració dels bits la fa normalment el maquinari, tot i que també és possible fer-ho a nivell de programari.

Primer a entrar, primer a sortir

L'algorisme de substitució de pàgines més senzill és un algorisme FIFO. L'algoritme de substitució de pàgines de primer en entrar, primer en sortir (FIFO) és un algorisme de baix cost que requereix poca comptabilitat per part del sistema operatiu. La idea és òbvia pel nom: el sistema operatiu fa un seguiment de totes les pàgines de la memòria en una cua, amb l'arribada més recent al darrere i l'arribada més antiga al davant. Quan s'ha de substituir una pàgina, se selecciona la pàgina al capdavant de la cua (la pàgina més antiga). Tot i que FIFO és barat i intuïtiu, té un mal rendiment en l'aplicació pràctica. Per tant, rarament s'utilitza en la seva forma no modificada. Aquest algorisme experimenta l'anomalia de Bélády. En paraules senzilles, en un error de pàgina, es substitueix el fotograma que ha estat més temps a la memòria.

Segona oportunitat

Una forma modificada de l'algoritme de substitució de la pàgina FIFO, coneguda com l'algoritme de substitució de la pàgina de segona oportunitat, surt relativament millor que FIFO a un cost baix per a la millora. Funciona mirant la part davantera de la cua com ho fa FIFO, però en lloc d'anar immediatament a aquesta pàgina, comprova si el bit de referència està establert. Si no està configurat, la pàgina s'intercanvia. En cas contrari, el bit referenciat s'esborra, la pàgina s'insereix a la part posterior de la cua (com si fos una pàgina nova) i aquest procés es repeteix. Això també es pot considerar com una cua circular. Si totes les pàgines tenen el bit de referència establert, a la segona trobada de la primera pàgina de la llista, aquesta pàgina s'intercanviarà, ja que ara té el bit de referència esborrat. Si totes les pàgines tenen el bit de referència esborrat, aleshores l'algorisme de la segona oportunitat degenera en FIFO pur.

Rellotge

El rellotge és una versió més eficient de FIFO que la segona oportunitat perquè les pàgines no s'han d'empènyer constantment al final de la llista, però fa la mateixa funció general que la segona oportunitat. L'algoritme de rellotge manté una llista circular de pàgines a la memòria, amb la "mà" (iterador) apuntant al darrer marc de pàgina examinat de la llista. Quan es produeix un error de pàgina i no hi ha marcs buits, el bit R (referenciat) s'inspecciona a la ubicació de la mà. Si R és 0, la pàgina nova es posa en lloc de la pàgina a la qual apunta la "mà" i la mà s'avança una posició. En cas contrari, el bit R s'esborra, després s'incrementa la maneta del rellotge i el procés es repeteix fins que es substitueix una pàgina.^[4] Aquest algorisme va ser descrit per primera vegada l'any 1969 per Fernando J. Corbató.^[5]

Aleatori

No s'utilitza amb freqüència (NFU)

Envelliment

Algorisme de substitució de la pàgina de la distància més llarga (LDF)

Memòria cau de pàgines a Linux

Linux utilitza una memòria cau de pàgines unificada per

brk i mmap ed -regions anònimes. Això inclou el munt i la pila de programes d'espai d'usuari. S'escriu per intercanviar quan es surt de pàgina.
Regions mmap ed no anònimes (con suport de fitxers). Si està present a la memòria i no es modifica de manera privada, la pàgina física es comparteix amb la memòria cau de fitxers o la memòria intermèdia.
Memòria compartida adquirida mitjançant shm_open.
El sistema de fitxers tmpfs a la memòria; escrit per intercanviar quan es surt de pàgina.
La memòria cau de fitxers inclou; escrit a l'emmagatzematge de blocs subjacent (possiblement passant per la memòria intermèdia, vegeu més avall) quan s'extreu de pàgina.
La memòria cau dels dispositius de blocs, anomenat "buffer" per Linux (no s'ha de confondre amb altres estructures també anomenades buffers com les que s'utilitzen per a canonades i buffers utilitzats internament a Linux); s'escriu a l'emmagatzematge subjacent quan s'apaga.

Referències

↑ Jones, Douglas W. «22C:116 Lecture Notes» (en anglès). University of Iowa Department of Computer Science. Arxivat de l'original el 30 June 2012. [Consulta: 18 març 2008].
↑ Torrez, Paul. «CS111 Lecture 11 notes» (en anglès). UCLA Computer Science Department. Arxivat de l'original el 9 January 2009.
↑ Jones, Douglas W. «22C:116 Lecture Notes» (en anglès). University of Iowa Department of Computer Science. Arxivat de l'original el 30 June 2012. [Consulta: 18 març 2008].
↑ Tanenbaum, Andrew S. Modern Operating Systems (en anglès). 2a edició. Upper Saddle River, NJ, USA: Prentice-Hall, 2001, p. 218 (4.4.5). ISBN 978-0-13-031358-4. OCLC 45284637. LCCN 00051666.
↑ Corbató, Fernando J. «A Paging Experiment with the Multics System». A: Festschrift: In Honor of P. M. Morse (en anglès). MIT Press, 1969, p. 217–228.

[lecture_notes_jones-1] Jones, Douglas W. «22C:116 Lecture Notes» (en anglès). University of Iowa Department of Computer Science. Arxivat de l'original el 30 June 2012. [Consulta: 18 març 2008].

[2] Torrez, Paul. «CS111 Lecture 11 notes» (en anglès). UCLA Computer Science Department. Arxivat de l'original el 9 January 2009.

[lecture_notes_jones2-3] Jones, Douglas W. «22C:116 Lecture Notes» (en anglès). University of Iowa Department of Computer Science. Arxivat de l'original el 30 June 2012. [Consulta: 18 març 2008].

[Tanenbaum-4] Tanenbaum, Andrew S. Modern Operating Systems (en anglès). 2a edició. Upper Saddle River, NJ, USA: Prentice-Hall, 2001, p. 218 (4.4.5). ISBN 978-0-13-031358-4. OCLC 45284637. LCCN 00051666.

[5] Corbató, Fernando J. «A Paging Experiment with the Multics System». A: Festschrift: In Honor of P. M. Morse (en anglès). MIT Press, 1969, p. 217–228.

[1]

[2]

[3]

[4]

[5]