Gestió de memòria

De Jose Castillo Aliaga
Revisión del 09:05 27 feb 2017 de Admin (discusión | contribs.) (→‎Enllaços)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)
Ir a la navegación Ir a la búsqueda
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