Diferencia entre revisiones de «Gestió de memòria»

De Jose Castillo Aliaga
Ir a la navegación Ir a la búsqueda
Sin resumen de edición
 
(No se muestran 21 ediciones intermedias del mismo usuario)
Línea 1: Línea 1:
Relacionat: [[Gestió de processos]], [[Linux]], [[Gestió de memòria]], [[Gestió de E/S]], [[Processos en Linux]]
==Introducció==
==Introducció==


Línea 30: Línea 32:




== Gestió de la memòria amb intercanvi ==


Reubicació i protecció
Amb la reassignació dinámica apareixen possiblitats noves com la '''càrrega dinàmica''', que permet carregat parts del programa sols quant fan falta i '''l'enllaç dinàmic''', per a les biblioteques dinàmiques.  
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.
Per a possibilitar la càrrega dinàmica, és necessari comptar amb un mecanisme per a passar els fragments de programa de la RAM al disc o dels disc a la RAM quant fan falta. Aques mecanisme es diu '''swapping'''. I es parla de swap in quant es carrega en al RAM i swap out quant es passa al disc. L'encarregat de implementar aquest mecanisme és el '''Planificador a mig plaç'''.


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.
El planificador a mig plaç necessita un criteri per a elegir el procés que entrarà a la RAM i un criteri per a elegir a la víctima que es quedarà fora. Amés, necessita un espai reservat en disc per a poder fer-ho.


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.
<div style="margin:10px; padding:5px; border:1px solid #eee; background-color:#ddf">
Aquest espai és la partició swap de Linux o el fitxer pagefile.sys de Windows. En el cas de Windows, el fitxer està per defecte en c:, encara que es pot canviar.
</div>


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.
=== Gestió de la memòria contigua ===
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.
El cas trivial és en el que no hi ha multiprogramació i sols cal establir un registre base per a separar l'espai del SO de l'espai del procés.


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.
[[Archivo:Contigua.png]]


És insuficient si volem poder tindre més d'un procés a la vegada.


L'evolució són les particions múltiples. Aquestes poden ser de mida fixa MFT o variable MVT. Les de mida fixa poden ser totes iguals o no. 
[[Archivo:Particionsmultiples.png]]


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.
Les particions de mida fixa simplifiquen la protecció, ja que no és necessari guardar un registre límit per a cada partició. Amés, simplifiquen la gestió de l'espai lliure.


É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.
Si les particions no són totes iguals o són de mida variable, cal reservar espai per a un procés segons un d'aquests algoritmes:
* Millor Buit (el més menut on cap)
* Pijor buit (el més gran)
* Primer buit (el primer buit trobat on cap)


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.
En general, el primer o millor buit donen millor rendiment.


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.
Per a evitar que un procés puga accedir a una direcció de memòria que no li correspon, cal implementar un mecanisme de protecció amb un registre base i un registre límit.  


[[Archivo:Protecciomemoria.png]]


3.2. GESTIÓ DE LA MEMÒRIA LLIURE
=== El problema de la fragmentació ===


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.
És el gran problema de la memòria


* Fragmentació interna (MFT) Si les particions de mida fixa, els processos no tenen perquè ocupar tot l'espai reservat. El que sobre no es pot aprofitar. Per un altra banda, si les particions les fem menudes per a que no sobre espai, és possible que no puguen entrar processos grans. La solució és poder partir el procés en parts més menudes que sí entren en les particions.
3.2.1. GESTIÓ DE LA MEMÒRIA AMB MAPA DE BITS
* Fragmentació externa (MVT) Si les particions són de mida variable, és possible que es creen buits tan menuts que ningún procés puga aprofitar-los. La solució és compactar la memòria, però és molt ineficient.


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 solució de dividir el programa en parts més menudes es fà amb dos estratègies: segmentació i paginació.


=== Segmentació ===


La segmentació es pot fer si gestionem la memòria amb particions variables.


Un programa es pot dividir en varis segments de  memòria. Aquestes divisións es basen en la lògica del programa. D'aquesta manera, es pot diferenciar entre dades i instruccions o pila. Amés, per exemple, es poden subdividir les dades en funció de la seua utilitat.


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ó.
Puguem col·locar els segments en zones de memòria no contigües. De manera que aprofitem millor els buits menuts.


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.
El compilador farà direccions de memòria amb dos components (segment i desplaçament).


3.2.2. GESTIÓ DE LA MEMÒRIA AMB LLISTES ENLLAÇADES
El maquinari reassigna dinàmicament amb una taula de segments en la que fa falta el registre base i límit per a cada segment.


La segmentació atenua la fragmentació, encara que no pot eliminar la fragmentació externa. Es poden definir segments amb protecció selectiva de la memòria per a permetre, per exemple, llegir a un altre procés. No afegís complexitat als algoritmes de gestió de memòria, ja que considera cada segment com un procés independent. Però necessita suport de maquinari per a trauir les direccions de memòria i accedir a la taula de segments. Es necessita un accés adicional a la memòria a consultar la taula de segments


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
=== Paginació ===


La paginació soluciona la fragmentació externa de la segmentació. Necessita unes particions de mida fixa i totes iguals.


La idea es trossejar la memòria en pàgines de mida fixa. (ex 4KB). Un programa pot residir en varies pàgines no contigües. Aquesta divsió no es fà en funció de ninguna lògica, per tant, és més difícil fer la protecció selectiva.
Les pàgines es claven en marcs de pàgina


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.
Tota direcció lògica té el número de pàgina i desplaçament. Amés, no és necessari un registre límit per a la pàgina, ja que són totes de la mateixa mida. També és més fàcil definir uns bits per a la pàgina i uns altres per al desplaçament. Per exemple, per a pàgines de 4KB fan falta 12 bits.  


Estratègies de col · locació
La MMU associa el número de pàgina lògic al marc de pàgina físic. Empra una taula de pàgines.


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.
[[Archivo:Traduirdireccions.png]]
Com es veu en el gràfic, el desplaçament es manté, però canvien els bits de la pàgina.


Primer ajust
La paginació provoca fragmentació interna. Si fem les pàgines més menudes la fragmentació serà menor, però la taula de pàgines serà més gran (la taula de pàgines ocupa memòria principal).


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
Els segments es poden paginar i situar en marcs de pàgina. ('''segmentació paginada''') Està millor organitzat lògicament gràcies a la segmentació. Millora el problema de la fragmentació externa (la interna no millora)


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.
=== Memòria Virtual ===


Les simulacions fetes per C. Bays el 1977 mostren que el següent ajust presenta un rendiment lleugerament inferior al del primer ajust.
La memòria virtual permet la execució de processos parcialment carregats en la memòria principal. És necessaria perquè els programes o la suma d'ells pot ser més gran que la memòria principal. Per a poder fer-ho, s'utilitza el disc com a magatzem de processos.


Millor ajust
Un dels avantatges de la memòria virtual més significatius és allibera al programador de la preocupació de que els programes càpiguen en memòria.


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.
Es tracta de mantindre en memòria principal sols els fragments que estan utilitzant-se, ja que en molts casos no es necessita tot el programa.


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.
El SO selecciona automàticament què fragments residiran en memòria principal. És molt difícil de predir quins fragments seran els més utilitzats.Si es seleccionen mal els fragments tindrem que recorre al disc amb freqüència. Açò no bloqueja el ordinador, però baixa molt el rendiment.


Pitjor ajust
La MV funciona perque els programes tenen una gran '''localitat''', és a dir, els accessos a memòria estan pròxims als anteriors.


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.
És la tècnica més habitual és la '''paginació per demanda''', combina paginació amb intercanvi (swap). En lloc de intercanviar un procés s'intercanvien algunes pàgines. Idealment, el paginador endevinarà quines pàgines es van a usar.


3.2.3. GESTIÓ DE LA MEMÒRIA MITJANÇANT PARTICIONS AMB MIDA 2N
Les pàgines no vàlides o vàlides (estan o no el la memòria principal) es marquen en la taula de pàgines amb un bit de validesa. Si intentem accedir a una pàgina no vàlida el hardware donarà una excepció anomenada '''page fault''' o fallada de pàgina. La fallada de pàgina provoca que el SO recupere del disc la pàgina requerida, s'actualitza la taula de pàgines i es reintenta la instrucció que va fallar.


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.
Els programadors tenen més espai que la disponibilitat del sistema i millora el rendiment al millorar la multiprogramació i la planificació del SO. Però és important mantindre una baixa '''freqüència de fallades de pàgina'''.


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 SO deu implementar:


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.
*Un algoritme de assignació de marcs (decidir els marcs que assignem a cada procés)
*Un algoritme de reemplaç de pàgines
#Atendre la interrupció de fallada de pàgina
#Portar la pàgina a memòria i colocar-la en un marc lliure
#Reiniciar 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.
Si no hi ha marc lliure cal escollir un marc víctima.


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.
*Escriure la víctima en disc i actualitzar taules.
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ç.
*Llegir la pàgina demandada i col·locar-la en el marc lliberat, actualitzar taules.
*Reiniciar el procés.


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.
Per a reduir la freqüència de fallades de pàgina s'estudien el '''algoritmes de reemplaç'''.


S'avaluen els algoritmes executant una sèrie de referències i calculant les fallades. La sèrie pot ser aleatòria o a partir de l'estudi d'un procés reial. Cal conèixer el nombre de marcs disponibles.
4. MEMÒRIA VIRTUAL


Aquests són els algoritmes de reemplaç:


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).
* FIFO: Fàcil de implementar, es substitueix la pàgina amb més temps en memòria. No té en compte l'historial i no sap les que s'executen amb freqüència. Anomalía de Belady (fenómen paradògic que Consisteix en que augmenten les fallades Quant s'asignen mès pàgines)


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.
* Óptim: Escollir la víctima que més tard tornarà a ser accedida. Presenta la freqüència de fallades més baixa. No es pot fer, requereix presciència. Peró s'estudia perqué és útil com a referència.


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).
* LRU: Aproximació del òptim. Less Recently Used. Es fa amb comptadors o piles. Requereix maquinari addicional i costos Els sistemes reials implementen aproximacions.


Així, no només és possible executa programes més grans sinó, que també es beneficia el funcionament dels sistemes de multiprogramació.
* Segona oportunitat:  FIFO amb bit de referència. Si el bit es 0 es canvia, si és 1 no, i el posem a 0 Si el millorem puguem tindre un bit de modificat i canviem el de clase mès baixa (Machintosh)


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.
* LFU:  Menys freqüentment usades. Implementa un comptador. Presenta problemes amb Pàgines que es van usar molt i després no es tornen a gastar. També passa que pàgines recentment portades tenen el compte baix.


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.
* MFU: Més freqüentment usada. Evita el primer problema anterior. El problema és que manté pàgines velles que no es gasten i es reemplacen pàgines bones.




Amés de l'algortime de reemplaç, cal tindre en compte que és convenient mantindre un % de marcs desocupats per evitar el doble reemplaç. Es pot fer en segon pla aquesta neteja.
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
Per a que tots els processos tinguen uns marcs reservats i lliures, cal definir un sistema de repartiment de marcs. Aquest repartiment pot ser proporcional a la mida o per prioritat.


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.
====Hiperpaginació====


4.2. TRADUCCIÓ D'ADRECES VIRTUALS A REALS
Cal recordar que el SO supervisa la CPU. Si el aprofitament baixa, augmenta la multiprogramació.  


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.
Al entrar un nou procés es lleven marcs a altres processos que necessitaran més marcs i aquests, els llevaran a altres. Com a conseqüència, Augmenta la cola de processos en espera de paginació. Per tant, disminueix l'aprofitament de la CPU i el sistema augmenta la multiprogramació agreujant encara més el problema. Si el sistema està més temps paginant que treballant està en estar de '''hiperpaginació'''.


Per a solucionar el problema, s'observa que tot procés compleix el principi de localitat. Si un procés té tota la seua localitat en memòria principal ocasiona poques fallades de pàgina.


S'anomena Àrea activa al conjunt de pàgines que el procés a utilitzat en un temps, eixe conjunt és Δ. Si Δ te una mida adequada és una fidel aproximació a la localitat actual.


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.
Si el SO manté el àrea activa en memòria de tots els processos i, si queden marcs addicionals es pot iniciar un altre. Si la suma de les mides de les àrees actives augmenta, el SO suspèn un procés. Aquesta solució evita la hiperpaginació i manté la multiprogramació molt alta. Aquesta solució, necessita d'un nou concepte: '''Prepaginació''': Si un procés estava suspès en swap es porten totes les pàgines de l'àrea activa.


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.
== La memòria dels processos ==


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.
Un procés en un sistema operatiu està executant-se en un ''Sand-Box'' de memòria virtual. El '''Virtual address space'''. En SO de 32 bits és de 2³² = 4GiB. En sistemes de 64 Bits teòricament pot ser de 2⁶⁴, encara que en sistemes com Windows de 64 bits és de 8 TiB. Aquesta memòria virtual, com hem vist, està dividida en pàgines que tenen una correspondència amb Marcs de pàgina físics o Page Frame Number '''PFN'''. Per facilitar l'administració, es tracta de segmentació paginada.
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Ó
Cal tindre en compte que quant un procés està en execució, per al processador, el procés té tota la memòria disponible. Serà l'MMU i el Sistema Operatiu el que traduirà les direccions lògiques en físiques.


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).
[[Archivo:LinuxFlexibleAddressSpaceLayout.png|right]]
Un procés en execució té assignats uns segments amb distints permisos. Dels segments més rellevants destaquem:
* Text o executable: Són les instruccions del programa.
* Dades estàtiques: Es tracta del codi i dades que són reservats en temps de càrrega del programa.
* Pila (Stack): Es tracta de un espai reservat per a les variables de les funcions que estan en execució. Té un accés LIFO molt eficient. Quant una funció entra en execució, carrega les dades en la pila i quant ix, les descarrega. Cada fil en un procés té la seua propia pila i les CPU actuals solen tindrer-la en la memòria cau.
* Monticle (Heap): És un espai de memòria dinàmica que és reservat en temps d'execució. En llenguatges com C, és on es creen el punters i s'utilitza la funció malloc(). Cal esborrar els punters que no s'utilitzen. Java i altres llenguatges tenen el ''recolector de fem'' o '''garbage-collector''' per eliminar el que, per descuit del programador, no han sigut eliminats correctament. L'accés al heap és més complicat i lent. A més, pot quedar fragmentat.


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ó.
Entre els segments, el sistema operatiu introdueix un espai aleatori per evitar atacs que coneguen les direccions de memòria que manipular.
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ó.


=== Stack vs Heap ===
[[Archivo:9UshP.png|right]]
El funcionament del monticle o Heap és senzill d'entendre. La memòria de Heap és una matriu de cel·les buides i accessibles de manera aleatòria. Per tant els programes sols han de reservar espai en ella alliberar-lo quant acaben. Però el Heap és ineficient en alguns aspectes. El heap ha d'implementar les solucions als problemes de la gestió de la memòria: Gestió d'espais lliures i fragmentació. El programador ha de ser responsable de reservar la memòria i de alliberar-la quant acabe. En cas contrari es produeix un '''Memory-Leak''' i pot no haver suficient memòria per a noves variables. Alguns llenguatges, com Java implementes el garbage-collector per alliberar les variables que ja no s'utilitzen. Quant es produeix un malloc(), el programa ha de buscar un espai lliure en el monticle i assignar-lo. Això és poc eficient.


No obstant, la memòria dinàmica en els monticles és necessària en molts casos. No sempre es sap la mida d'una variable quant es programa. La memòria dinàmica la pot reservar en temps d'execució. Amés, les variables es poden declarar en una funció, però es poden quedar en el procés inclús quant ja ha acabat la funció. Les variables declarades en el heap són accessibles per totes les funcions i es pot enviar a una funció per referència. Passar un vector gran per referència és més eficient que passar totes les dades.


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ó.
La pila o Stack, és molt més eficient. Les dades són carregades quant s'executa la funció que les utilitza. Per un processador és molt senzill accedir a una direcció de la pila i les noves dades se inserissen en la part de dalt. El programador no es preocupa de eliminar les dades de la pila. Quant s'acaba la funció, el punter deixa d'apuntar a les últimes clavades i queden alliberades. La pila creix cap abaix, per tant, quant es carrega una nova funció, el punter és decrementat i és incrementat quant s'allibera. la pila pot omplir-se i provocar un '''Stackoverflow'''. Sol ser en funcions recursives.


4.4. ALGORISMES DE SUBSTITUCIÓ DE PÀGINES
== Enllaços ==


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.
* Sobre pmap i pagemap per saber la memòria utilitzada per un procés: http://stackoverflow.com/questions/6252063/simplest-way-to-get-physical-address-from-the-logical-one-in-linux-kernel-module http://www.mjmwired.net/kernel/Documentation/vm/pagemap.txt


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.
* http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory


* http://www.redhat.com/magazine/001nov04/features/vm/


PRINCIPI DE optimalitat
* https://people.freebsd.org/~lstewart/articles/cpumemory.pdf


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.
* https://www.redhat.com/en/about/blog/do-we-really-need-swap-modern-systems (https://news.ycombinator.com/item?id=13715249)

Revisión actual - 10:05 27 feb 2017

Relacionat: Gestió de processos, Linux, Gestió de memòria, Gestió de E/S, Processos en Linux

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.


Gestió de la memòria sense reasignació

En aquest cas, el compilador assigna a les dades e instruccions direccions físiques que no poden cambiar durant l'execució del programa. És un sistema molt sencill, però al no ser reasignables les direccions de memòria, dificulta la multiprogramació i la protecció de la memòria. El problema és que, abans de la compilació, deuriem conèixer les direccions de memòria que tindrà disponible el programa.

Els sistemes operatius amb aquesta gestió han de ser monotarea. Per exemple MS-DOS

Gestió de la memòria amb reasignació

Ens interessa que el compilador no genere direccions definitives, sinó reassignables. Si la reassignació es fa en temps de càrrega es diu estàtica i si es fa en temps d'execució es diu dinàmica. Els processos no saben la direcció real que estan utilitzant. Per a ells, sempre comença per la 0.

Si la reassignació és estàtica, la Unitat de Gestió de la Memòria (MMU), conté un registre base al qual se li sumarà la direcció de la memòria que necessite el procés. Però el valor d'aquest registre no pot canviar durant l'execució del programa. El canviar aquesta direcció implicaria poder moure el procés a un altre lloc de la memòria. El problema de la estàtica és que no podem compactar la memòria i podem provocar fragmentació.

Amb la reassignació dinàmica, podem recol·locar els processos per deixar buits majors.

Reassignaciodinamina.png


Gestió de la memòria amb intercanvi

Amb la reassignació dinámica apareixen possiblitats noves com la càrrega dinàmica, que permet carregat parts del programa sols quant fan falta i l'enllaç dinàmic, per a les biblioteques dinàmiques.

Per a possibilitar la càrrega dinàmica, és necessari comptar amb un mecanisme per a passar els fragments de programa de la RAM al disc o dels disc a la RAM quant fan falta. Aques mecanisme es diu swapping. I es parla de swap in quant es carrega en al RAM i swap out quant es passa al disc. L'encarregat de implementar aquest mecanisme és el Planificador a mig plaç.

El planificador a mig plaç necessita un criteri per a elegir el procés que entrarà a la RAM i un criteri per a elegir a la víctima que es quedarà fora. Amés, necessita un espai reservat en disc per a poder fer-ho.

Aquest espai és la partició swap de Linux o el fitxer pagefile.sys de Windows. En el cas de Windows, el fitxer està per defecte en c:, encara que es pot canviar.


Gestió de la memòria contigua

El cas trivial és en el que no hi ha multiprogramació i sols cal establir un registre base per a separar l'espai del SO de l'espai del procés.

Contigua.png

És insuficient si volem poder tindre més d'un procés a la vegada.

L'evolució són les particions múltiples. Aquestes poden ser de mida fixa MFT o variable MVT. Les de mida fixa poden ser totes iguals o no. Particionsmultiples.png

Les particions de mida fixa simplifiquen la protecció, ja que no és necessari guardar un registre límit per a cada partició. Amés, simplifiquen la gestió de l'espai lliure.

Si les particions no són totes iguals o són de mida variable, cal reservar espai per a un procés segons un d'aquests algoritmes:

  • Millor Buit (el més menut on cap)
  • Pijor buit (el més gran)
  • Primer buit (el primer buit trobat on cap)

En general, el primer o millor buit donen millor rendiment.

Per a evitar que un procés puga accedir a una direcció de memòria que no li correspon, cal implementar un mecanisme de protecció amb un registre base i un registre límit.

Protecciomemoria.png

El problema de la fragmentació

És el gran problema de la memòria

  • Fragmentació interna (MFT) Si les particions de mida fixa, els processos no tenen perquè ocupar tot l'espai reservat. El que sobre no es pot aprofitar. Per un altra banda, si les particions les fem menudes per a que no sobre espai, és possible que no puguen entrar processos grans. La solució és poder partir el procés en parts més menudes que sí entren en les particions.
  • Fragmentació externa (MVT) Si les particions són de mida variable, és possible que es creen buits tan menuts que ningún procés puga aprofitar-los. La solució és compactar la memòria, però és molt ineficient.

La solució de dividir el programa en parts més menudes es fà amb dos estratègies: segmentació i paginació.

Segmentació

La segmentació es pot fer si gestionem la memòria amb particions variables.

Un programa es pot dividir en varis segments de memòria. Aquestes divisións es basen en la lògica del programa. D'aquesta manera, es pot diferenciar entre dades i instruccions o pila. Amés, per exemple, es poden subdividir les dades en funció de la seua utilitat.

Puguem col·locar els segments en zones de memòria no contigües. De manera que aprofitem millor els buits menuts.

El compilador farà direccions de memòria amb dos components (segment i desplaçament).

El maquinari reassigna dinàmicament amb una taula de segments en la que fa falta el registre base i límit per a cada segment.

La segmentació atenua la fragmentació, encara que no pot eliminar la fragmentació externa. Es poden definir segments amb protecció selectiva de la memòria per a permetre, per exemple, llegir a un altre procés. No afegís complexitat als algoritmes de gestió de memòria, ja que considera cada segment com un procés independent. Però necessita suport de maquinari per a trauir les direccions de memòria i accedir a la taula de segments. Es necessita un accés adicional a la memòria a consultar la taula de segments

Paginació

La paginació soluciona la fragmentació externa de la segmentació. Necessita unes particions de mida fixa i totes iguals.

La idea es trossejar la memòria en pàgines de mida fixa. (ex 4KB). Un programa pot residir en varies pàgines no contigües. Aquesta divsió no es fà en funció de ninguna lògica, per tant, és més difícil fer la protecció selectiva. Les pàgines es claven en marcs de pàgina

Tota direcció lògica té el número de pàgina i desplaçament. Amés, no és necessari un registre límit per a la pàgina, ja que són totes de la mateixa mida. També és més fàcil definir uns bits per a la pàgina i uns altres per al desplaçament. Per exemple, per a pàgines de 4KB fan falta 12 bits.

La MMU associa el número de pàgina lògic al marc de pàgina físic. Empra una taula de pàgines.

Traduirdireccions.png Com es veu en el gràfic, el desplaçament es manté, però canvien els bits de la pàgina.

La paginació provoca fragmentació interna. Si fem les pàgines més menudes la fragmentació serà menor, però la taula de pàgines serà més gran (la taula de pàgines ocupa memòria principal).


Els segments es poden paginar i situar en marcs de pàgina. (segmentació paginada) Està millor organitzat lògicament gràcies a la segmentació. Millora el problema de la fragmentació externa (la interna no millora)

Memòria Virtual

La memòria virtual permet la execució de processos parcialment carregats en la memòria principal. És necessaria perquè els programes o la suma d'ells pot ser més gran que la memòria principal. Per a poder fer-ho, s'utilitza el disc com a magatzem de processos.

Un dels avantatges de la memòria virtual més significatius és allibera al programador de la preocupació de que els programes càpiguen en memòria.

Es tracta de mantindre en memòria principal sols els fragments que estan utilitzant-se, ja que en molts casos no es necessita tot el programa.

El SO selecciona automàticament què fragments residiran en memòria principal. És molt difícil de predir quins fragments seran els més utilitzats.Si es seleccionen mal els fragments tindrem que recorre al disc amb freqüència. Açò no bloqueja el ordinador, però baixa molt el rendiment.

La MV funciona perque els programes tenen una gran localitat, és a dir, els accessos a memòria estan pròxims als anteriors.

És la tècnica més habitual és la paginació per demanda, combina paginació amb intercanvi (swap). En lloc de intercanviar un procés s'intercanvien algunes pàgines. Idealment, el paginador endevinarà quines pàgines es van a usar.

Les pàgines no vàlides o vàlides (estan o no el la memòria principal) es marquen en la taula de pàgines amb un bit de validesa. Si intentem accedir a una pàgina no vàlida el hardware donarà una excepció anomenada page fault o fallada de pàgina. La fallada de pàgina provoca que el SO recupere del disc la pàgina requerida, s'actualitza la taula de pàgines i es reintenta la instrucció que va fallar.

Els programadors tenen més espai que la disponibilitat del sistema i millora el rendiment al millorar la multiprogramació i la planificació del SO. Però és important mantindre una baixa freqüència de fallades de pàgina.

El SO deu implementar:

  • Un algoritme de assignació de marcs (decidir els marcs que assignem a cada procés)
  • Un algoritme de reemplaç de pàgines
  1. Atendre la interrupció de fallada de pàgina
  2. Portar la pàgina a memòria i colocar-la en un marc lliure
  3. Reiniciar el procés.

Si no hi ha marc lliure cal escollir un marc víctima.

  • Escriure la víctima en disc i actualitzar taules.
  • Llegir la pàgina demandada i col·locar-la en el marc lliberat, actualitzar taules.
  • Reiniciar el procés.

Per a reduir la freqüència de fallades de pàgina s'estudien el algoritmes de reemplaç.

S'avaluen els algoritmes executant una sèrie de referències i calculant les fallades. La sèrie pot ser aleatòria o a partir de l'estudi d'un procés reial. Cal conèixer el nombre de marcs disponibles.

Aquests són els algoritmes de reemplaç:

  • FIFO: Fàcil de implementar, es substitueix la pàgina amb més temps en memòria. No té en compte l'historial i no sap les que s'executen amb freqüència. Anomalía de Belady (fenómen paradògic que Consisteix en que augmenten les fallades Quant s'asignen mès pàgines)
  • Óptim: Escollir la víctima que més tard tornarà a ser accedida. Presenta la freqüència de fallades més baixa. No es pot fer, requereix presciència. Peró s'estudia perqué és útil com a referència.
  • LRU: Aproximació del òptim. Less Recently Used. Es fa amb comptadors o piles. Requereix maquinari addicional i costos Els sistemes reials implementen aproximacions.
  • Segona oportunitat: FIFO amb bit de referència. Si el bit es 0 es canvia, si és 1 no, i el posem a 0 Si el millorem puguem tindre un bit de modificat i canviem el de clase mès baixa (Machintosh)
  • LFU: Menys freqüentment usades. Implementa un comptador. Presenta problemes amb Pàgines que es van usar molt i després no es tornen a gastar. També passa que pàgines recentment portades tenen el compte baix.
  • MFU: Més freqüentment usada. Evita el primer problema anterior. El problema és que manté pàgines velles que no es gasten i es reemplacen pàgines bones.


Amés de l'algortime de reemplaç, cal tindre en compte que és convenient mantindre un % de marcs desocupats per evitar el doble reemplaç. Es pot fer en segon pla aquesta neteja.

Per a que tots els processos tinguen uns marcs reservats i lliures, cal definir un sistema de repartiment de marcs. Aquest repartiment pot ser proporcional a la mida o per prioritat.

Hiperpaginació

Cal recordar que el SO supervisa la CPU. Si el aprofitament baixa, augmenta la multiprogramació.

Al entrar un nou procés es lleven marcs a altres processos que necessitaran més marcs i aquests, els llevaran a altres. Com a conseqüència, Augmenta la cola de processos en espera de paginació. Per tant, disminueix l'aprofitament de la CPU i el sistema augmenta la multiprogramació agreujant encara més el problema. Si el sistema està més temps paginant que treballant està en estar de hiperpaginació.

Per a solucionar el problema, s'observa que tot procés compleix el principi de localitat. Si un procés té tota la seua localitat en memòria principal ocasiona poques fallades de pàgina.

S'anomena Àrea activa al conjunt de pàgines que el procés a utilitzat en un temps, eixe conjunt és Δ. Si Δ te una mida adequada és una fidel aproximació a la localitat actual.

Si el SO manté el àrea activa en memòria de tots els processos i, si queden marcs addicionals es pot iniciar un altre. Si la suma de les mides de les àrees actives augmenta, el SO suspèn un procés. Aquesta solució evita la hiperpaginació i manté la multiprogramació molt alta. Aquesta solució, necessita d'un nou concepte: Prepaginació: Si un procés estava suspès en swap es porten totes les pàgines de l'àrea activa.

La memòria dels processos

Un procés en un sistema operatiu està executant-se en un Sand-Box de memòria virtual. El Virtual address space. En SO de 32 bits és de 2³² = 4GiB. En sistemes de 64 Bits teòricament pot ser de 2⁶⁴, encara que en sistemes com Windows de 64 bits és de 8 TiB. Aquesta memòria virtual, com hem vist, està dividida en pàgines que tenen una correspondència amb Marcs de pàgina físics o Page Frame Number PFN. Per facilitar l'administració, es tracta de segmentació paginada.

Cal tindre en compte que quant un procés està en execució, per al processador, el procés té tota la memòria disponible. Serà l'MMU i el Sistema Operatiu el que traduirà les direccions lògiques en físiques.

LinuxFlexibleAddressSpaceLayout.png

Un procés en execució té assignats uns segments amb distints permisos. Dels segments més rellevants destaquem:

  • Text o executable: Són les instruccions del programa.
  • Dades estàtiques: Es tracta del codi i dades que són reservats en temps de càrrega del programa.
  • Pila (Stack): Es tracta de un espai reservat per a les variables de les funcions que estan en execució. Té un accés LIFO molt eficient. Quant una funció entra en execució, carrega les dades en la pila i quant ix, les descarrega. Cada fil en un procés té la seua propia pila i les CPU actuals solen tindrer-la en la memòria cau.
  • Monticle (Heap): És un espai de memòria dinàmica que és reservat en temps d'execució. En llenguatges com C, és on es creen el punters i s'utilitza la funció malloc(). Cal esborrar els punters que no s'utilitzen. Java i altres llenguatges tenen el recolector de fem o garbage-collector per eliminar el que, per descuit del programador, no han sigut eliminats correctament. L'accés al heap és més complicat i lent. A més, pot quedar fragmentat.

Entre els segments, el sistema operatiu introdueix un espai aleatori per evitar atacs que coneguen les direccions de memòria que manipular.

Stack vs Heap

9UshP.png

El funcionament del monticle o Heap és senzill d'entendre. La memòria de Heap és una matriu de cel·les buides i accessibles de manera aleatòria. Per tant els programes sols han de reservar espai en ella alliberar-lo quant acaben. Però el Heap és ineficient en alguns aspectes. El heap ha d'implementar les solucions als problemes de la gestió de la memòria: Gestió d'espais lliures i fragmentació. El programador ha de ser responsable de reservar la memòria i de alliberar-la quant acabe. En cas contrari es produeix un Memory-Leak i pot no haver suficient memòria per a noves variables. Alguns llenguatges, com Java implementes el garbage-collector per alliberar les variables que ja no s'utilitzen. Quant es produeix un malloc(), el programa ha de buscar un espai lliure en el monticle i assignar-lo. Això és poc eficient.

No obstant, la memòria dinàmica en els monticles és necessària en molts casos. No sempre es sap la mida d'una variable quant es programa. La memòria dinàmica la pot reservar en temps d'execució. Amés, les variables es poden declarar en una funció, però es poden quedar en el procés inclús quant ja ha acabat la funció. Les variables declarades en el heap són accessibles per totes les funcions i es pot enviar a una funció per referència. Passar un vector gran per referència és més eficient que passar totes les dades.

La pila o Stack, és molt més eficient. Les dades són carregades quant s'executa la funció que les utilitza. Per un processador és molt senzill accedir a una direcció de la pila i les noves dades se inserissen en la part de dalt. El programador no es preocupa de eliminar les dades de la pila. Quant s'acaba la funció, el punter deixa d'apuntar a les últimes clavades i queden alliberades. La pila creix cap abaix, per tant, quant es carrega una nova funció, el punter és decrementat i és incrementat quant s'allibera. la pila pot omplir-se i provocar un Stackoverflow. Sol ser en funcions recursives.

Enllaços

Obtenido de «https://castilloinformatica.es/wiki/index.php?title=Gestió_de_memòria&oldid=2929»