Gestió de memòria
Introducció
La seua labor és la de portar el control de quines parts de la memòria estan en ús i quines no ho estan, assignar memòria a processos quan la necessiten i retirar quan acaben, administrar l'intercanvi entre la memòria central i el disc quan la memòria central no siga suficient per contenir tots els processos.
En aquest tema començarem estudiant el sistema de gestió de la memòria més simple sencill, després progressarem gradualment analitzant sistemes cada vegada més elaborats.
ADMINISTRACIÓ DE LA MEMÒRIA SENSE INTERCANVI
Els sistemes d'administració de la memòria es poden dividir en dues classes: els que mouen els processos entre la memòria central i el disc durant l'execució (intercanvi i paginació) i aquells que no ho fan. Els segons són més simples, l'intercanvi i la paginació són estratagemes produïdes principalment per la insuficiència de la memòria central per contenir tots els programes al mateix temps.
MONOPROGRAMACIÓN
L'esquema d'administració de la memòria més simple consisteix en tenir només un procés en la memòria alhora i en permetre que aquest procés utilitze tota la memòria. Quan el sistema s'organitza d'aquesta manera, només pot estar en execució un sol procés alhora.
INCIDÈNCIA DE LA multiprogramació A LA GESTIÓ DE LA MEMÒRIA
Una de les principals raons que s'usi la multiprogramació en un ordinador, és que la majoria dels processos passen una fracció substancial del seu temps espejando que acabi l'E / S del disc. És comú que un procés entri en un cicle llegint blocs de dades d'un arxiu en disc i després faci algun càlcul pel que fa al contingut dels blocs llegits. Amb monoprogramación la unitat central de processament estarà ociosa esperant el disc aproximadament un 75% del temps.
Quan s'utilitza la multiprogramació, pot millorar la utilització de la unitat central de processament (CPU). Si cada procés, de mitjana realitza càlculs només durant el 20% del temps en què es troba en la memòria, amb cinc processos en la memòria a la vegada, la CPU ha d'estar permanentment ocupada. No obstant això, aquest model és molt optimista, ja que suposa que els cinc mai esperaran la E / S al mateix temps.
Un model més adequat consisteix a observar l'ús de la CPU des d'un punt de vesteix probabilístic. Suposem que un procés inverteix una fracció p del seu temps en un estat d'espera d'E / S. Amb n processos en la memòria a la vegada, la probabilitat que els n processos esperin la I / S (en aquest cas la CPU estarà ociosa) és p ". La utilització de la CPU és, per tant, i - pn.
2.2.1. Multiprogramació AMB PARTICIONS FIXES
Per als requeriments actuals de còmput és útil tenir més d'un procés en la memòria a la vegada. Per aconseguir aquest objectiu sorgeix la qüestió de la manera com s'ha d'organitzar la memòria per aconseguir aquest objectiu. La manera més simple consisteix en repartir l'espai en n particions (possiblement desiguals). Per continuar amb la simplicitat, aquesta partició podria tenir lloc a manualment per un operador quan el sistema s'iniciï.
Així, quan arriba un treball, aquest es pot col · locar a la cua d'espera d'entrada de la partició prou gran per contenir-lo. Com en aquest esquema les particions són fixes, qualsevol espai que no utilitzi un treball en una partició es perd.
Ordenar els treballs en cues d'espera separades és ineficient quan la llista d'espera d'una partició gran és buida però les d'una partició petita aquesta plena.
Sempre que una partició quedi lliure, el primer treball de la cua d'espera es carrega a la partició buida i s'executa. Com no és desitjable desaprofitar una partició gran amb un treball petit, una estratègia diferent quan una partició quedi lliure consisteix en buscaren tota la cua d'espera d'entrada i prendre el treball més gran que càpiga en ella. Aquest algorisme discrimina els treballs petits cosa que no sol ser adequat per millorar les prestacions.
Aquest mètode, amb particions fixes establertes per l'operador al principi del treball, va ser utilitzat per OS/360 a les macrocomputadoras d'IBM per molts anys. Se li deia MFT. És simple d'entendre i igualment simple d'implementar: els treballs que arriben esperen a la cua d'esperança fins que es disposa d'una partició adequada, en el qual el treball es carrega en la partició i s'executa fins que acaba.
Reubicació i protecció
La multiprogramació introdueix dos problemes essencials que s'han de solucionar: la reubicació i la protecció. Quan un programa s'enllaça (és a dir, el programa central, procediments escrits per l'usuari i procediments de biblioteca es combinen en un sol espai de direcció), l'enllaçador ha de saber en quina direcció començarà el programa en la memòria.
Per exemple, suposem que la primera instrucció és una crida a un procediment ubicat a la direcció relativa 1E3 l'arxiu binari produït pel enllaçador. Si aquest programa es carrega la partició 1, aquesta instrucció saltarà a la direcció absoluta 1E3, la qual està dins del sistema operatiu. El que es necessita és una crida a 1M + 1E3. Si el programa es carrega a la partició 2, aquest s'ha d'executar com una crida a 2M + 1E3, etc. Aquesta dificultat es coneix com a problema de reubicació.
Una solució possible consisteix a modificar les instruccions a mesura que el programa es carrega a la memòria. Els programes carregats a la partició 1 tindran 1MB agregats a cada direcció, els programes carregats a la partició 2 tenen 2MB sumats a les adreces i aixÍ successivament.
Un altre problema addicional a la reubicació és el de la protecció de les diferents particions. Un programa malintencionat sempre pot construir una nova instrucció i passar-hi. Com que els programes d'aquest sistema utilitzen adreces de memòria absolutes en comptes d'adreces relatives a un registre, en principi, és fàcil que un programa llegeixi o escrigui alguna paraula en la memòria en una partició que no és la seva. No obstant això, en sistemes de múltiples usuaris, no s'ha de permetre que els processos llegeixin i escriguin a la memòria que pertany a altres usuaris.
La solució que IBM va triar per protegir el sistema 360 consistir en repartir l'espai en blocs de 2KB i assignar un codi de protecció de 4 bits a cada bloc. El maquinari del 360 atrapava qualsevol intent d'accés a la memòria per part d'un procés el codi de protecció difereix de la contrasenya. Com només el sistema operatiu podia conèixer la clau, es prevenia el que els processos de interferissin entre si.
3. INTERCANVI (swapping)
Amb un sistema per lots l'organització de la memòria en particions fixes és simple i efectiva. Mentre puguin guardar suficients treballs a la memòria per mantenir ocupada a la CPU tot el temps, no hi ha raó per utilitzar res més complicat. Amb el processament amb temps compartit la situació és diferent: normalment hi ha més usuaris que memòria per contenir tots els seus processos, tal que cal guardar els processos sobrants en disc. Per descomptat, per a executar aquests processos han portar a la memòria central. El pas de processos complets de la memòria central a un disc i el seu retorn es denomina intercanvi i s'estudia en els següents apartats. El mecanisme d'intercanvi, treballant amb processos complets o amb unitats d'assignació de memòria, és un dels pilars en què es recolza la memòria virtual que també s'estudia més endavant.
3.1. Multiprogramació AMB PARTICIONS VARIABLES
Aparentment, es podria implementar un sistema d'intercanvi sobre particions fixes. Sempre que un procés es bloquegés es podria passar al disc col · locant altre procés en el seu partició. A la pràctica, les particions fixes no són atractives quan la memòria és escassa perquè una part molt gran d'ella és desaprofitada per programes que són menors que les particions. En el seu lloc s'utilitza un mètode diferent per al maneig de la memòria. Aquest es coneix com particions variables.
Quan s'empren particions variables, el nombre i grandària dels processos de la memòria varien en forma dinàmica en temps d'execució. En el dibuix de sota es mostra la manera com funcionen les particions variables en què en una seqüència temporal s'han anat produït els següents canvis (+ significa procés portat a memòria i - procés extret de memòria): 1) + A 2) + B 3) + C 4)-A 5) + D 6)-B 7) + E.
La diferència principal entre les particions fixes i les particions variables és que el nombre, ubicació i mida de les particions varien en forma dinàmica en el segon cas, a mesura que els processos vénen i se'n van, mentre que són fixos en el primer. El no estar condicionat per un nombre fix de particions, que pot ser massa gran o massa petit millora la utilització de la memòria però també complica la seva assignació així com el seu control.
És possible combinar tots els buits (espacias de memòria disponible) en un gran passant tots els processos el més baix que sigui possible dins de l'espai d'adreçament. Aquesta tècnica es coneix com compactació de la memòria i només s'usa en casos extrems ja que requereix molt de temps de CPU.
Un aspecte que cal destacar fa a la quantitat de la memòria que ha d'assignar a un procés quan aquest es crea o intercanvia. Es creen processos amb una mida fixa que mai canvia, llavors l'assignació és simple: s'assigna exactament el que es necessita. No obstant això, si els segments de dades dels processos poden créixer assignant dinàmicament memòria des d'una pila, com en molts llenguatges de programació, quan un procés intenti créixer es produiran problemes. Si hi ha memòria lliure adjacent al procés, se li pot assignar a aquest que creixerà ocupant el buit. D'altra banda, si el que hi ha ¡unto al procés és un altre procés, el procés en creixement ha de passar-se a un buit de la memòria prou gran per contenir-o bé caldrà intercanviar un o més processos per crear un buit prou gran . Si un procés no pot créixer en la memòria i l'àrea d'intercanvi del disc és plena, el procés haurà de ser eliminat.
Si s'espera que molts processos creixin a mesura que s'executin, probablement sigui adequat assignar una mica de memòria extra sempre que es carregui un procés. Això permetrà reduir el cost general associat amb el canvi o intercanvi de processos que ja no caben en la seva memòria assignada. No obstant això, quan s'intercanvien processos a un disc, només ha d'intercanviar la memòria que en realitat està en ús ja que ocupar temps i disc guardant dades en blanc no és de cap manera recomanable.
3.2. GESTIÓ DE LA MEMÒRIA LLIURE
En els sistemes amb particions de memòria de mida i nombre variables, cal introduir algun mecanisme que permeti fer el seguiment de particions que hi ha usades i quins estan lliures. Existeixen tres mètodes comunes per portar el control de l'ús de la memòria: mapa de bits, llistes i particions equivalents.
3.2.1. GESTIÓ DE LA MEMÒRIA AMB MAPA DE BITS
Amb un mapa de bits, la memòria es divideix en unitats d'assignació, la grandària pot variar des d'unes poques paraules fins a diversos KB. Per cada unitat d'assignació hi ha un bit al mapa de bits, que és 0 si la unitat està lliure, i 1 si la unitat està ocupada (o viceversa).
La grandària de la unitat d'assignació és un aspecte important en el disseny. A igual quantitat de memòria, com menor sigui la unitat d'assignació, major serà el mapa de bits necessari. Per exemple, amb unitats d'assignació de 4 bytes, una memòria de M bytes necessitarà M/32 bits per al mapa. D'aquesta manera el mapa de bits utilitzar el 3,125% de la memòria. Sembla poc però per a una memòria de 64 MB es necessita un mapa de bits de 2 MB. No obstant això, si la unitat d'assignació s'escull gran, el mapa de bits serà petit, però pot desaprofitar bastant memòria en l'última unitat ocupada per cada procés si la mida del procés no és un múltiple exacte de la unitat d'assignació.
Un mapa de bits ofereix una manera senzilla de portar el control de les paraules de la memòria. Ara bé, el problema principal que té amb ell és que quan s'hagi decidit portar a la memòria un procés de k unitats d'assignació, l'administrador de la memòria haurà de buscar al mapa una seqüència de k bits 0. Aquest tipus de cerca és una operació no és massa ràpida, de manera que a la pràctica els mapes de bits no s'utilitzen massa.
3.2.2. GESTIÓ DE LA MEMÒRIA AMB LLISTES ENLLAÇADES
Una altra manera de portar el control de la memòria és mitjançant la conservació d'una llista enllaçada de segments de Ia memòria assignats i lliures, on un segment és un procés o un lloc entre dos processos. Cada entrada de la llista especifica un buit (H) o un procés (P), la direcció en la qual comença, la longitud i dos punters a les entrades anterior i següent
En aquest exemple, la llista de segments es manté ordenada per direcció. Aquesta classe d'ordenació té l'avantatge que quan un procés acaba o s'intercanvia, l'actualització de les llistes és directa. Llevat del cas dels extrems, un procés que acaba té dos veïns. Aquests al seu torn, poden ser processos o buits. Quan acaba un procés envoltat per processos es canviarà l'indicador de procés P pel de buit H. Quan un buit es troba amb un altre buit, aquests es podran unir actualitzant convenientment la llista.
Estratègies de col · locació
Quan els processos i els buits es conserven en una llista classificada per direcció, es poden emprar diversos algorismes per assignar memòria per un procés acabat de crear o intercanviat. Se suposa que l'administrador de la memòria sap quanta memòria ha d'assignar.
Primer ajust
L'algorisme més simple és el primer ajust. L'administrador de la memòria rastreja la llista de segments n'hi ha prou que hi hagi un buit que sigui prou gran. Després el buit es divideix en dues parts, una per al procés i una per a la memòria no utilitzada, excepte en el cas improbable d'un ajust exacte. El primer ajust és un algorisme veloç perquè ocupa el menor temps possible en la recerca d'espai lliure.
Següent ajust
Aquest funciona igual que el primer ajust, llevat que porta el control d'on es localitza quan troba un forat adequat. La següent vegada que és cridat, comença a buscar a partir d'on es va quedar, en comptes de començar sempre des de l'inici, com ho fa el primer ajust.
Les simulacions fetes per C. Bays el 1977 mostren que el següent ajust presenta un rendiment lleugerament inferior al del primer ajust.
Millor ajust
Aquest algorisme busca en tota la llista i pren el buit més petit possible. En comptes de dividir un buit gran que es podria necessitar després, aquest algorisme intenta trobar un buit que està pròxim a la mida real que es necessita.
El que millor s'ajusta és més lent que el primer ajust perquè ha de buscar en tota la llista cada vegada que és anomenat. Una cosa que sorprèn és que també dóna lloc encara major despesa de la memòria que el primer ajust o que el següent ajust perquè tendeix a omplir la memòria amb buits molt petits sense utilitat. Així, de mitjana, el primer ajust genera buits majors que els dos anteriors mètodes.
Pitjor ajust
Per sortejar el problema de dividir espais molt ajustats en un procés i un buit molt petit, es podria pensar en el que pitjor s'ajusta, és a dir, prendre sempre el buit més gran disponible, de manera que el buit lliure després de la divisió sigui el prou gran per ser útil. No obstant això, s'ha comprovat empíricament la seva poca funcionalitat.
3.2.3. GESTIÓ DE LA MEMÒRIA MITJANÇANT PARTICIONS AMB MIDA 2N
En l'apartat anterior es va veure que portar nota dels buits en una o més llistes ordenades per mida de buit fa l'assignació veloç però la alliberament lent, perquè per trobar els veïns del segment alliberat s'han de comprovar totes les llistes de buits.
El mètode de les particions amb mida 2n (que rep també altres noms com a sistema company o sistema dels associats) és un algorisme per al maneig de la memòria que aprofita el fet que les computadores utilitzen nombres binaris per l'adreçament per tal de accelerar la unió de buits adjacents quan un procés acaba o s'intercanvia.
El funcionament és el següent. L'administrador de la memòria conserva una llista de blocs lliures per cada mida 1, 2, 4, 8,16, 32, 64, 128, 256, etc, bytes fins arribar a la mida de la memòria. Amb una memòria d'1 MB, per exemple, es necessiten 21 d'aquestes llistes, des de 1 byte fins a 1 MB. Inicialment, tota la memòria està lliure i la llista d'1 MB té una única entrada que assenyalant un buit d'1 MB. Les altres llistes estan buides. Conforme es va necessitant assignar memòria es divideix un tram d'ordre superior en 2 d'ordre immediatament inferior (per exemple 1 MB en 2 de 512 KB) i així successivament fins a tenir un tram de la mida menor necessari per allotjar el procés.
Per a cada divisió, el tram que es divideix s'elimina de la llista corresponent i els dos trams nous apareixen com disponibles a la llista apropiada. Quan un procés s'assigna a un buit, aquest es registra com ocupat en la llista corresponent.
A cada nivell quan un bloc ocupat queda lliure es comprova si té un company lliure. Les parelles comencen sempre per blocs que ocupen una posició senar i si és així s'uneixen dos formant un bloc de nivell superior. El procés continua recursivament fins al nivell superior. Aquest mètode té un avantatge sobre els algoritmes que classifiquen blocs de memòria per grandària però no necessàriament en direccions que siguin múltiples de la mida del bloc. L'avantatge és que quan s'allibera un bloc d'una mida determinada, l'administrador de la memòria ha de buscar només en la llista de buits corresponent per veure si és possible una unió. En els algorismes que permeten que els blocs de la memòria es divideixin en formes arbitràries s'ha de buscar en totes les llistes de buits. El resultat és que el sistema de particions amb mida 2n és veloç.
Malauradament, també és extremadament ineficient en l'ús de la memòria (que és la seva tasca principal). El problema prové del fet que totes les sol · licituds han arrodonir a una potència de 2. A un procés de 257 KB li seran assignades 512 KB. Els 255 KB no usats es malgasten. Hi ha hagut diversos intents de millorar aquest mètode per tal de fer-lo més eficient.
4. MEMÒRIA VIRTUAL
Ja en els albors de la computació, els tècnics es van enfrontar per primera vegada amb programes que eren massa grans per cabre en la memòria disponible. La primera solució vàlida per al problema va consistir a dividir el programa en parts, anomenades superposicions (overlays).
Alguns sistemes de superposició eren molt complexos i admetien múltiples superposicions en la memòria a la vegada. Les superposicions es guardaven en el disc i el sistema operatiu les intercanvia en la memòria, encara que el treball de la divisió del programa en parts havia de ser realitzat prèviament pel programador. Així, molts professionals consumien grans quantitats del seu escàs temps component exquisits puntes de grans programes en petites memòries, tasca gens grata de les que els programadors fugien. No va passar molt temps abans que algú va idear una manera de deixar l'ordinador tota la feina de gestió de la memòria.
La idea bàsica que implica la memòria virtual és que la mida del programa, les dades i la pila combinats puguin excedir de la quantitat de memòria física disponible. És sistema operatiu guarda aquelles part del programa que es troben en ús corrent en la memòria central, i la resta en el disc mitjançant la utilització d'uns mecanismes similars als de la tècnica d'intercanvi (però aquí no s'apliquen a processos complets).
Així, no només és possible executa programes més grans sinó, que també es beneficia el funcionament dels sistemes de multiprogramació.
El mecanisme bàsic subjacent sota el concepte d'emmagatzematge virtual és la separació de les adreces a les quals fan referència els processos que s'executen en un ordinador de les adreces efectivament disponibles a la memòria principal. A les primeres se les coneix com adreces virtuals ia les direccions de memòria real com adreces físiques o adreces reals. El rang d'adreces virtuals a les que pot fer referència un procés en execució es coneix com espai d'adreces virtuals, (denotat usualment V), del procés. L'interval d'adreces físiques disponibles en un sistema de còmput determinant es coneix com espai d'adreces físiques, (denotat F), de l'ordinador.
Evidentment, encara que els processos usin adreces virtuals l'execució efectiva es porta a terme en l'emmagatzematge físic. Així, per executar qualsevol procés és necessari establir una correspondència entre les adreces virtuals i les físiques. Aquest mecanisme de correspondència ha de ser ràpid i eficient ja que si no les prestacions del sistema es degradaran de manera insuportable.
S'han desenvolupat diversos mètodes per associar les adreces virtuals amb les físiques mentre s'executa un procés. D'aquesta manera s'allibera el desenvolupador de la preocupació per la posició de procediments i dades en l'emmagatzematge físic permetent concentrar tota la seva atenció en qüestions arquitectòniques d'eficiència d'algorismes i estructura dels programes, i evitant-li la dura tasca de conèixer la composició i funcionament del maquinari subjacent.
4.1. JERARQUIA DE MEMÒRIA
Quan l'espai d'adreces virtuals de l'usuari és més gran que la memòria física i, més encara, quan molts usuaris, cada un amb el seu espai d'adreces virtuals, comparteixen aquesta memòria, es produiran situacions en què la memòria física principal serà incapaç de contenir tot el codi, dades, etc. dels processos dels usuaris. En aquest cas serà necessari recórrer a l'intercanvi entre la memòria i l'emmagatzematge auxiliar que lògicament, serà més gran. Així, s'estableix una jerarquia de memòria de dos nivells (encara que, en realitat en el tema corresponent s'estudia que aquesta jerarquia és més àmplia). El primer nivell, compost per la memòria central i els registres, és aquell en què s'executen els processos i en el qual han de trobar les dades perquè un procés en execució pugui fer referència a ells. El segon nivell consisteix en mitjans d'emmagatzematge de gran capacitat, com discos. Així, quan es va a executar un procés, el seu codi i dades es col · loquen en l'emmagatzematge principal.
4.2. TRADUCCIÓ D'ADRECES VIRTUALS A REALS
Com vam veure, per a una correcta gestió de la memòria és necessari portar el control de les parts ocupades i les parts lliures tant en la memora principal com en l'espai d'intercanvi a la memòria secundària. A més, els mecanismes de traducció dinàmica d'adreces han de mantenir mapes de correspondències entre les adreces virtuals situades en la memòria principal i les adreces reals que efectivament ocupen. Per motius d'eficàcia, en cada sistema, la memòria física se sol organitzar en unitats d'assignació anomenades blocs, de mida fixa o variable, però sempre molt superior a la paraula de memòria.
Per tant, la informació és agrupada en blocs, que tindran exactament la mateixa mida a la memòria virtual, en la memòria física i en l'àrea d'intercanvi de l'emmagatzematge secundari, i el sistema porta un registre del lloc de l'emmagatzematge real on s'han col · locat els diversos blocs d'emmagatzematge virtual. Com més gran sigui la mida de bloc, menor serà la fracció de l'emmagatzematge real dedicada a guardar la informació de correspondències. No obstant això, els blocs grans triguen més a ser transferits de l'emmagatzematge secundari al primari i consumeixen més memòria física, de manera que el seu ús limita el nombre de processos que poden compartir l'emmagatzematge real. D'altra banda, la regla de la memòria no utilitzada ens diu que, en nom de l'eficiència en l'ús d'aquest escàs i valuós recurs, tampoc podem elevar molt la mida dels blocs.
Hi ha diverses alternatives sobre si tots els blocs dins d'un sistema han de ser de la mateixa mida o no. Quan tots els blocs són iguals reben el nom de pàgines i l'organització de l'emmagatzematge virtual corresponent es coneix com paginació. Quan els blocs són de diferents mides, cas en el qual es denominen segments, l'organització de l'emmagatzematge virtual corresponent es coneix com segmentació. Els sistemes actuals solen combinar ambdues tècniques, amb segments de mida variable compostos de pàgines de mida fixa.
Les adreces de memòria virtual són, si més no, bidimensionals. Per accedir a una dada, un procés ha d'indicar el bloc on es troba l'element i el seu desplaçament a partir de l'inici del bloc. Així, podem denotar una direcció e, v, amb un parell (b, d), on b és el nombre de bloc en què es troba l'element al qual es fa referència id és el desplaçament des de l'inici del bloc.
Per traduir una adreça d'emmagatzematge virtual en una direcció d'emmagatzematge físic, cada procés té la seva pròpia taula d'assignació de blocs (com veurem aquesta taula pot, al seu torn, dividir-se en diversos nivells), que el sistema allotja en una zona de l'emmagatzematge real que mai es virtualitza. Cada vegada que es produeix un canvi de context (és a dir, canvia el procés en execució en la CPU) es carrega amb l'adreça física, a, un registre especial dins de la CPU anomenat registre d'inici de la taula d'assignació de blocs. Cada procés tindrà la seva pròpia taula d'assignació de blocs encara que és normal que totes aquestes taules s'allotgin en un espai contigu d'adreces que es coneix com a directori de blocs (així treballa, per exemple, Windows 2003). Un cop conegut el nombre de bloc, b, i la mida, t que les dades de cada bloc ocupen a la taula (sol ser un valor predeterminat pels dissenyadors del sistema operatiu), es suma el producte b • ta l'adreça base, a, de la taula de blocs per formar l'adreça real de l'entrada del bloc a la taula d'assignació de blocs. Aquesta entrada conté l'adreça física, b ', de l'inici del bloc b. A més, també conté una sèrie de valors addicionals v1, v2, ... necessaris per a la gestió de la memòria (bits d'accés i modificació, direcció en memòria secundària, possibles clau de bloqueig, etc.). Finalment, el desplaçament, d es suma a la direcció d'inici del bloc b 'per formar l'adreça física desitjada, f = b' + d.
4.3. Paginació I SEGMENTACIÓ
La majoria dels sistemes de memòria virtual empren una tècnica anomenada paginació. Amb ella, la memòria virtual es divideix en blocs de la mateixa mida anomenats pàgines. D'aquesta manera, els programes utilitzen adreces virtuals pertanyents a l'espai de direcció virtual. Aquestes adreces virtuals són enviades a una unitat d'administració de la memòria (MMU, que és un xip o conjunt de xips que associen les adreces virtuals a les adreces de la memòria física).
A la paginació, la memòria, tant virtual com física es divideix en blocs de la mateixa mida. Els blocs de la memòria virtual es denominen pàgines i els de la memòria física marcs de pàgina. La mida d'aquests blocs varies en funció de l'arquitectura del processat i les seves busos, però aquesta mida es manté constant al llarg de tot el procés de traducció i paginació per facilitar el procés de traducció.
Quan la CPU utilitza una direcció e corresponent a una pàgina que no està carregada en cap marc, la MMU fa que la CPU envia un senyal anomenada fallada de pàgina al sistema operatiu i bloqueja el procés que resta pendent de l'E / S corresponent. El sistema operatiu prendrà un marc de pàgina amb poc ús, el bolcarà en disc (encara que no sempre, com després veurem), es carregarà la pàgina corresponent a la direcció e en el marc de pàgina que acaba d'alliberar (normalment, l'entrada corresponent d' la taula de pàgines recull la direcció de disc on cal buscar la pàgina corresponent) i efectuar els ajustos pertinents al mapa de memòria després del que es desbloquejarà el procés permetent reprendre l'execució.
Hi ha la necessitat imperiosa que la traducció entre adreces virtuals i físiques sigui el més ràpida possible. Per això, se solen utilitzar tècniques que combinen memòries associatives i cau d'alta velocitat que contenen les parts més usades de les taules d'adreces per tal d'accelerar el citat procés de traducció.
4.4. ALGORISMES DE SUBSTITUCIÓ DE PÀGINES
Quan hi ha un error d'una pàgina, el sistema operatiu ha d'escollir una pàgina per retirar-la de la memòria per tal de deixar espai per a la pàgina que ha de carregar en el marc de pàgina que aquella ocupa. Si la pàgina per ser retirada s'ha modificat en la seva estada a la memòria, aquesta s'ha d'escriure al disc per actualitzar la còpia allí existent. No obstant això, si la pàgina no s'ha alterat no cal tornar a escriure la còpia en disc. La pàgina per llegir simplement s'escriu sobre de la pàgina que s'expulsa.
El rendiment del sistema es veurà beneficiat si a cada fallada de pàgina es tria, per substituir, una pàgina poc usada. Si es retira una pàgina molt utilitzada, probablement haurà de tornar a carregar gairebé immediatament. S'han realitzat molts treballs sobre el tema dels algorismes de substitució de pàgines, tant teòrics com experimentals. Seguidament resumim algunes de les tècniques principals.
PRINCIPI DE optimalitat
El millor algorisme possible de substitució de pàgines és fàcil de descriure però impossible d'implementar. L'algorisme és el següent. Al moment en què ocorre la fallada d'una pàgina i no queden marcs de pàgina buits, s'eliminarà la pàgina que trigarà més a ser referenciada.