+ All Categories
Home > Documents > Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Date post: 19-Jan-2016
Category:
Upload: hertz
View: 27 times
Download: 1 times
Share this document with a friend
Description:
Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-. Profesor îndrumător: Ștefan Stăncescu Student: Toma Oana-Mădălina. Memoria flash. Memoria flash este o memorie electronică cu acces aleator. Ea este nevolatilă , se poate șterge și reprograma. - PowerPoint PPT Presentation
32
Managementul memoriei flash Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și -Algoritmul Rejuvenator, TrueFFS și Dual pool- Dual pool- Profesor îndrumător: Ștefan Profesor îndrumător: Ștefan Stăncescu Stăncescu Student: Toma Oana-Mădălina Student: Toma Oana-Mădălina
Transcript
Page 1: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Managementul memoriei flashManagementul memoriei flash-Algoritmul Rejuvenator, TrueFFS și Dual pool--Algoritmul Rejuvenator, TrueFFS și Dual pool-

Profesor îndrumător: Ștefan StăncescuProfesor îndrumător: Ștefan StăncescuStudent: Toma Oana-MădălinaStudent: Toma Oana-Mădălina

Page 2: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Memoria flashMemoria flash

Memoria flash este o memorie electronică cu Memoria flash este o memorie electronică cu acces aleator. Ea este nevolatilăacces aleator. Ea este nevolatilă, , se poate se poate șterge și reprograma.șterge și reprograma.Se foloseSe folosește pentru dispozitivele mobile, cum ște pentru dispozitivele mobile, cum sunt telefoanele, camerele digitale și sunt telefoanele, camerele digitale și dispozitivele cu senzori. dispozitivele cu senzori. Memoria flash este populară printe aceste Memoria flash este populară printe aceste dispositive datorită dimensiunilor mici, greutății dispositive datorită dimensiunilor mici, greutății scăzute, consumului scăzute, consumului redusredus de energie, de energie, rezistenței sporite la șocuri și citirea rapidă.rezistenței sporite la șocuri și citirea rapidă.

Page 3: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Dezavantajele memoriei flashDezavantajele memoriei flash

Memoriile flash moștenesc probleme de Memoriile flash moștenesc probleme de rezistentă. Este esential ca aceste probleme de rezistentă. Este esential ca aceste probleme de bază să fie rezolvate pentru ca memoria flash bază să fie rezolvate pentru ca memoria flash NAND să-și poată materializa potențialul la NAND să-și poată materializa potențialul la memorarea pe scală largă. Aceste probleme memorarea pe scală largă. Aceste probleme sunt rezolvate de algoritmii de wear leveling.sunt rezolvate de algoritmii de wear leveling.În prezent se lucrează cu algoritmi de wear În prezent se lucrează cu algoritmi de wear leveling deoarece, fără această implementare leveling deoarece, fără această implementare durata medie de viață a unei memorii flash este durata medie de viață a unei memorii flash este de 0,55 ore, iar folosind algoritmii se ajunge la o de 0,55 ore, iar folosind algoritmii se ajunge la o durată de viață de aproximativ 50 de ani.durată de viață de aproximativ 50 de ani.

Page 4: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Organizarea memoriei flashOrganizarea memoriei flash

Memoria flash NAND este organizată ca o Memoria flash NAND este organizată ca o matrice de blocuri. Un bloc cuprinde de la 32 la matrice de blocuri. Un bloc cuprinde de la 32 la 64 pagini, unde pagina este cea mai mica 64 pagini, unde pagina este cea mai mica unitate pentru operațiile de scriere și citire. unitate pentru operațiile de scriere și citire.

Memoria flash NAND are două variante numite Memoria flash NAND are două variante numite SLC (Single Level Cell) și MLC (Multi Level SLC (Single Level Cell) și MLC (Multi Level Cell). Dispozitivele SLC stochează un bit pe Cell). Dispozitivele SLC stochează un bit pe celula în timp ce MLC stochează mai mult de un celula în timp ce MLC stochează mai mult de un bit pe celulă. bit pe celulă.

Page 5: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Caracteristicile stocării pe memorii Caracteristicile stocării pe memorii flashflash

Acces uniform la latența de citire: În discurile magnetice Acces uniform la latența de citire: În discurile magnetice convenționale, timpul de acces este dominat de timpul convenționale, timpul de acces este dominat de timpul necesar capătului de citire să găseasca calea necesară necesar capătului de citire să găseasca calea necesară (timp de explorare) urmat de rotația întarziată pentru (timp de explorare) urmat de rotația întarziată pentru găsirea sectorului (latența de rotație). Timpul de citire a găsirea sectorului (latența de rotație). Timpul de citire a unui bloc aleator de pe un disc magnetic depinde în unui bloc aleator de pe un disc magnetic depinde în primul rând de locația fizică a datelor.primul rând de locația fizică a datelor. Acces la citirea și scrierea asimetrică: În discurile Acces la citirea și scrierea asimetrică: În discurile magnetice convenționale, timpii de citire și scriere pentru magnetice convenționale, timpii de citire și scriere pentru o anumită locație sunt aproximativ aceeași. Operațiile de o anumită locație sunt aproximativ aceeași. Operațiile de citire și scriere sunt făcute la nivel de pagina în timp ce citire și scriere sunt făcute la nivel de pagina în timp ce operațiile de ștergere sunt făcute la nivel de block. Acest operațiile de ștergere sunt făcute la nivel de block. Acest lucru duce la asimetrie pentru latența operațiilor de citire lucru duce la asimetrie pentru latența operațiilor de citire și scriere.și scriere.

Page 6: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Uzura block-urilor: Frecvent operația de ștergere a Uzura block-urilor: Frecvent operația de ștergere a blocului reduce durata de viață a memoriei flash. Pentru blocului reduce durata de viață a memoriei flash. Pentru o memorie flash SLC numărul limitat de ștergeri este în o memorie flash SLC numărul limitat de ștergeri este în jur de 100K și pentru o memorie flash MLC este în jur de jur de 100K și pentru o memorie flash MLC este în jur de 10K.10K.Colectorul de gunoi: Fiecare pagină în memoria flash se Colectorul de gunoi: Fiecare pagină în memoria flash se află într-una din cele trei stări: validă, invalidă și curătă. află într-una din cele trei stări: validă, invalidă și curătă. Paginile validePaginile valide conțin date care mai sunt înca valide. conțin date care mai sunt înca valide. Paginile invalidePaginile invalide vor fi șterse la următoarea colectare vor fi șterse la următoarea colectare de gunoi. de gunoi. Pagini curatePagini curate sunt acelea care sunt în curs de sunt acelea care sunt în curs de ștergere și pot primi noi date în ele. Când numărul ștergere și pot primi noi date în ele. Când numărul paginilor goale din dispozitivul cu memorie flash este paginilor goale din dispozitivul cu memorie flash este redus, procesul de colectare de gunoi este declanșat. redus, procesul de colectare de gunoi este declanșat. Colectarea de gunoi corectează paginile invalide prin Colectarea de gunoi corectează paginile invalide prin ștergerea lorștergerea lor Mutarea datelor în cazul ștergerilor la nivel de blockMutarea datelor în cazul ștergerilor la nivel de block

Page 7: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Amplificarea de scriere: În cazul hard disk-urilor, cererile Amplificarea de scriere: În cazul hard disk-urilor, cererile de scriere făcute de utilizator se potrivesc cu scrierile de scriere făcute de utilizator se potrivesc cu scrierile fizice ale dispozitivului actual. În cazul SSD-urilor, fizice ale dispozitivului actual. În cazul SSD-urilor, activitățile de wear leveling și colectarea de gunoi duc la activitățile de wear leveling și colectarea de gunoi duc la rescrierea datelor utilizatorului într-o altă parte fără vreo rescrierea datelor utilizatorului într-o altă parte fără vreo cerere de scriere propriu-zisă. Fenomenul este numit cerere de scriere propriu-zisă. Fenomenul este numit amplificarea scrierilor și este definit prin următoarea amplificarea scrierilor și este definit prin următoarea relație:relație:Amplificarea scrierii=Amplificarea scrierii= (Numărul actual de (Numărul actual de pagini)/(Numărul paginilor scrise de utilizator)pagini)/(Numărul paginilor scrise de utilizator)Matricea de translație flash (FTL): Multe SSD-uri cu Matricea de translație flash (FTL): Multe SSD-uri cu performante ridicate au o matrice de translație flash, performante ridicate au o matrice de translație flash, pentru administrarea memoriei flash. FTL, ascunde pentru administrarea memoriei flash. FTL, ascunde organizarea interna a memoriei flash NAND și prezintă organizarea interna a memoriei flash NAND și prezintă un dispozitiv block matricii sistemului de fișiere. FTL un dispozitiv block matricii sistemului de fișiere. FTL mapează spațiul de adrese logice pentru locațiile fizice mapează spațiul de adrese logice pentru locațiile fizice din memoria flash. din memoria flash.

Page 8: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Algoritmul de wear levelingAlgoritmul de wear leveling

Un algoritm de wear leveling urmărește ieșirea Un algoritm de wear leveling urmărește ieșirea din uz a block-urilor diferite ale memoriei flash. din uz a block-urilor diferite ale memoriei flash. Un block se spune că este ieșit din uz când a Un block se spune că este ieșit din uz când a fost șters de numărul maxim de ori. fost șters de numărul maxim de ori. Definesc durata de viață a memoriei flash ca Definesc durata de viață a memoriei flash ca numărul de update-uri care poate fi executat numărul de update-uri care poate fi executat până când primul block este scos din uz.până când primul block este scos din uz.Principalul scop al oricărui algoritm de wear Principalul scop al oricărui algoritm de wear leveling este să crească durata de viață a leveling este să crească durata de viață a memoriei flash prin prevenirea ajungerii fiecărui memoriei flash prin prevenirea ajungerii fiecărui block la limita.block la limita.

Page 9: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Hot data vs. Cold dataHot data vs. Cold data

Datele care sunt updatate mai des sunt definite Datele care sunt updatate mai des sunt definite ca hot data, în timp ce datele care rămân relativ ca hot data, în timp ce datele care rămân relativ nemodificate sunt definite sub numele de cold nemodificate sunt definite sub numele de cold data. Optimizarea plasării datelor hot și cold în data. Optimizarea plasării datelor hot și cold în memoria flash presupune darea unei importanțe memoria flash presupune darea unei importanțe extreme numărului limitat de cicluri de ștergere extreme numărului limitat de cicluri de ștergere pentru block-urile flash. pentru block-urile flash.

Importanța scrierii datelor hot pe block-uri Importanța scrierii datelor hot pe block-uri diferitediferite

Page 10: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Organizarea algoritmilor de wear Organizarea algoritmilor de wear levelingleveling

Wear leveling dinamicWear leveling dinamic: Algoritmi realizeaza wear : Algoritmi realizeaza wear leveling-ul prin reutilizarea block-urilor cu cel mai mic leveling-ul prin reutilizarea block-urilor cu cel mai mic număr de ștergeri. Totuși acești algoritmi nu încearcă număr de ștergeri. Totuși acești algoritmi nu încearcă să mute datele cold care pot rămâne pentru totdeauna să mute datele cold care pot rămâne pentru totdeauna în câteva block-uri. în câteva block-uri. Wear leveling staticWear leveling static: Spre deosebire de algoritmii de : Spre deosebire de algoritmii de wear leveling dinamic, algoritmii de wear leveling static wear leveling dinamic, algoritmii de wear leveling static încearca să mute datele cold pe block-uri utilizate mai încearca să mute datele cold pe block-uri utilizate mai mult pentru a facilita răspândirea rapidă a uzurii. mult pentru a facilita răspândirea rapidă a uzurii. Totuși, mutarea datelor cold în jur fără cereri de update Totuși, mutarea datelor cold în jur fără cereri de update duce la depășiri.duce la depășiri.

Page 11: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Principalii algoritmi descrișiPrincipalii algoritmi descriși

RejuvenatorRejuvenator este un algoritm static de wear este un algoritm static de wear leveling. Este important operațiile care folosesc leveling. Este important operațiile care folosesc multe resurse pentru mutarea datelor cold să fie multe resurse pentru mutarea datelor cold să fie făcute optim și să nu creeze depașiri excesive. făcute optim și să nu creeze depașiri excesive. Rejuvenator-ul este un algoritm de wear leveling Rejuvenator-ul este un algoritm de wear leveling care scalează memoria flash de capacități mari care scalează memoria flash de capacități mari și garantează cererile de performanță pentru și garantează cererile de performanță pentru centrele de stocare.centrele de stocare.Numesc algoritmul de wear leveling Rejuvenator Numesc algoritmul de wear leveling Rejuvenator deoarece previne blocurile să atingă durata de deoarece previne blocurile să atingă durata de viață rapid și le ține tinere.viață rapid și le ține tinere.

Page 12: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Algoritmul TrueFFSAlgoritmul TrueFFSMecanismul TrueFFS de wear leveling mapează Mecanismul TrueFFS de wear leveling mapează

unitățile șterse virtual într-un lanț de unități șterse fizic. unitățile șterse virtual într-un lanț de unități șterse fizic. Dacă nu există unități fizice libere în fondul comun, se Dacă nu există unități fizice libere în fondul comun, se produce întoarcerea, operație în care harta fiecărei produce întoarcerea, operație în care harta fiecărei unitați șterse virtual este schimbată cu una din lanțul de unitați șterse virtual este schimbată cu una din lanțul de unități fizice. Datele valide din lanț sunt copiate pe o unități fizice. Datele valide din lanț sunt copiate pe o singură unitate fizică și unitățile fizice din lanț sunt singură unitate fizică și unitățile fizice din lanț sunt eliberate. Acest lucru garantează o distribuire uniformă a eliberate. Acest lucru garantează o distribuire uniformă a numărului de ștergeri pe block-urile de stocare dinamică numărului de ștergeri pe block-urile de stocare dinamică a datelor. a datelor. Se bazează pe periodicitate și procedeul round robinSe bazează pe periodicitate și procedeul round robin

Principalii algoritmiPrincipalii algoritmi

Page 13: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Principalii algoritmiPrincipalii algoritmi

Algoritmul dual poolAlgoritmul dual poolUn algoritm cu stare dublă menține două Un algoritm cu stare dublă menține două

stări pentru block-uri-hot și cold. Block-urile sunt stări pentru block-uri-hot și cold. Block-urile sunt inițial alocate aleator stărilor hot și cold. Apoi pe inițial alocate aleator stărilor hot și cold. Apoi pe măsură ce se termină update-urile starea măsură ce se termină update-urile starea asociată devine stabilă .asociată devine stabilă .Dacă block-urile asociate stării hot sunt șterse Dacă block-urile asociate stării hot sunt șterse peste un prag sigur conținutul este mutat în cele peste un prag sigur conținutul este mutat în cele mai puțin utilizate block-uri din starea cold.mai puțin utilizate block-uri din starea cold. Dezavantaj: timpul pentru asocierea stărilorDezavantaj: timpul pentru asocierea stărilor

Page 14: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

DezavantajeDezavantaje

Pe lângă wear leveling, alte mecanisme cum sunt colectorul de Pe lângă wear leveling, alte mecanisme cum sunt colectorul de gunoi și harta block-urilor fizice logice pot afecta performanțele și gunoi și harta block-urilor fizice logice pot afecta performanțele și durata de viață a memoriei flash.durata de viață a memoriei flash. Tabelele de mapare sunt păstrate în RAM. Nivelul tehnicilor de Tabelele de mapare sunt păstrate în RAM. Nivelul tehnicilor de mapare consumă o cantitate enormă de memorie deoarece conține mapare consumă o cantitate enormă de memorie deoarece conține informație de mapare despre fiecare pagină. S-a propus utilizarea informație de mapare despre fiecare pagină. S-a propus utilizarea unei scheme hibride de mapare pentru a beneficia de performanța unei scheme hibride de mapare pentru a beneficia de performanța la nivel de mapare a paginilor și pentru a eficientiza utilizarea la nivel de mapare a paginilor și pentru a eficientiza utilizarea spațiului la nivel de mapare a block-urilor.spațiului la nivel de mapare a block-urilor.Toate schemele de mapare hibridă folosesc un set de block-uri Toate schemele de mapare hibridă folosesc un set de block-uri înregistrate pentru a reține update-urile și pentru a le scrie block-înregistrate pentru a reține update-urile și pentru a le scrie block-urile de date corespunzătoare. Block-urile înregistrate sunt mapate urile de date corespunzătoare. Block-urile înregistrate sunt mapate la nivel de pagină în timp ce block-urile de date sunt mapate la nivel la nivel de pagină în timp ce block-urile de date sunt mapate la nivel de block.de block. DFTL stochează o porțiune a tabelului pentru maparea paginilor și DFTL stochează o porțiune a tabelului pentru maparea paginilor și restul tabelelor în memoria flash însăși. Acest procedeu reduce restul tabelelor în memoria flash însăși. Acest procedeu reduce cerințele de memorie pentru tabelul de mapare la nivel de pagină.cerințele de memorie pentru tabelul de mapare la nivel de pagină.

Page 15: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Algoritmul RejuvenatorAlgoritmul Rejuvenator

Se păstrează o mapare la nivel de pagină pentru Se păstrează o mapare la nivel de pagină pentru stocarea block-urilor cu date hot și o mapare la nivel de stocarea block-urilor cu date hot și o mapare la nivel de block-uri pentru block-urile care stochează date cold.block-uri pentru block-urile care stochează date cold. Identificarea datelor hot și cold este o parte integrantă a Identificarea datelor hot și cold este o parte integrantă a Rejuvenator-ului. Pentru idetificare se utilizează o Rejuvenator-ului. Pentru idetificare se utilizează o fereastră simplă bazată pe scheme ce conțin contor fereastră simplă bazată pe scheme ce conțin contor pentru a determina care adrese logice sunt hot. pentru a determina care adrese logice sunt hot. Dimensiunea ferestrei este fixa și acoperă adresele Dimensiunea ferestrei este fixa și acoperă adresele logice care sunt accesate în trecutul apropiat. În orice logice care sunt accesate în trecutul apropiat. În orice moment adresele logice care au valori mari ale moment adresele logice care au valori mari ale contorului în fereastră sunt considerate hot.contorului în fereastră sunt considerate hot.

Page 16: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Descrierea algoritmuluiDescrierea algoritmului

Rejuvenator-ul menține τ liste de block-uri. Diferența dintre numărul Rejuvenator-ul menține τ liste de block-uri. Diferența dintre numărul maxim de ștergeri al fiecărui block și numărul minim de ștergeri al maxim de ștergeri al fiecărui block și numărul minim de ștergeri al fiecărui block este mai mică sau egală cu pragul τ. Fiecărui block îi fiecărui block este mai mică sau egală cu pragul τ. Fiecărui block îi este asociat numărul listei egal cu numărul ștergerilor sale. Câteva este asociat numărul listei egal cu numărul ștergerilor sale. Câteva liste pot fi goale. Inițial tuturor block-urilor le este asociată lista cu liste pot fi goale. Inițial tuturor block-urilor le este asociată lista cu numarul 0. Pe măsură ce block-urile sunt updatate vor fi promovate numarul 0. Pe măsură ce block-urile sunt updatate vor fi promovate la liste cu număr mai mare. Notez numărul minim de ștergeri cu la liste cu număr mai mare. Notez numărul minim de ștergeri cu win_wear și numărul maxim de ștergeri cu max_wear. Fie diferența win_wear și numărul maxim de ștergeri cu max_wear. Fie diferența dintre max_wear și min_wear notată cu diff. Fiecare bloc poate avea dintre max_wear și min_wear notată cu diff. Fiecare bloc poate avea trei tipuri de pagini: valide, invalide sau curate. trei tipuri de pagini: valide, invalide sau curate. Fie m o valoare intermediară între min_wear și min_wear + (τ-1). Fie m o valoare intermediară între min_wear și min_wear + (τ-1). Block-urile care au contorul între min_wear și min_wear+ (m-1) sunt Block-urile care au contorul între min_wear și min_wear+ (m-1) sunt folosite pentru stocarea datelor hot și block-urile care aparțin listelor folosite pentru stocarea datelor hot și block-urile care aparțin listelor cu număr ridicat sunt folosite pentru a stoca date cold. cu număr ridicat sunt folosite pentru a stoca date cold.

Page 17: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Algoritmii RejuvenatorAlgoritmii RejuvenatorALGORITMUL 1ALGORITMUL 1Eveniment= Cererea de scriere in LBA (Eveniment= Cererea de scriere in LBA (Logical Block Logical Block AddressAddress))Dacă LBA are o hartă pagină atunciDacă LBA are o hartă pagină atunci

Dacă LBA este cald atunciDacă LBA este cald atunci Scrie într-o pagină dintr-o listă cu Scrie într-o pagină dintr-o listă cu număr mic număr mic Updatează harta paginăUpdatează harta paginăAltfelAltfel

Scrie pagina într-o listă cu număr Scrie pagina într-o listă cu număr mare (sau într-un block înregistrat)mare (sau într-un block înregistrat)

Updatează harta block-urilorUpdatează harta block-urilorAltfel dacă LBA este cald atunciAltfel dacă LBA este cald atunci

Scrie într-o Scrie într-o pagină dintr-o pagină dintr-o listă culistă cu

număr micnumăr micInvalidează Invalidează (datele) fiecărei (datele) fiecărei harți block harți block asociateasociateUpdatează Updatează harta paginilorharta paginilor

Altfel dacă LBA este cold atunciAltfel dacă LBA este cold atunci

Scrie pe oScrie pe o

pagină dintr-o pagină dintr-o

listă cu număr listă cu număr

mare (sau block mare (sau block

înregistrat)înregistrat)Updatează harta block-urilorUpdatează harta block-urilorSfarșit Sfarșit

ALGORITMUL 2: . Mutarea datelorALGORITMUL 2: . Mutarea datelor Dacă Numărul de block-uri șterse în listele cu Dacă Numărul de block-uri șterse în listele cu număr mic < TL atuncinumăr mic < TL atunci

Mută datele block-urilor Mută datele block-urilor din din lista cu numărul între lista cu numărul între

min_wear min_wear și min_wear la și min_wear la

block-urile din listele cu block-urile din listele cu număr marenumăr mareColectează gunoiul Colectează gunoiul

block-block- urilor din urilor din lista cu numărul lista cu numărul

între min_wear și între min_wear și min_wear+(τ-1)min_wear+(τ-1)

Dacă Numărul de block-uri șterse din lista cu număr Dacă Numărul de block-uri șterse din lista cu număr mare <TH atuncimare <TH atunci

Mută datele block-urilor din lista cu Mută datele block-urilor din lista cu numarul min_wear la numarul min_wear la

block-urile din lista block-urile din lista cu număr mic cu număr micColectează gunoiul block-urilor din lista cu Colectează gunoiul block-urilor din lista cu numerele între min_wear și min_wear+(τ-1)numerele între min_wear și min_wear+(τ-1)SfârșitSfârșit

Page 18: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Descriere Algoritm 1Descriere Algoritm 1

Algoritmul 1 încearcă să stocheze Algoritmul 1 încearcă să stocheze blocurile hot de date în liste numerotate blocurile hot de date în liste numerotate între min_wear și min_wear + (m-1). între min_wear și min_wear + (m-1). Acestea sunt block-urile care au fost Acestea sunt block-urile care au fost șterse de un număr mic de ori și au o șterse de un număr mic de ori și au o rezistentă mai bună. De acum, numerele rezistentă mai bună. De acum, numerele listelor vor fi date de la min_wear la listelor vor fi date de la min_wear la min_wear+ (m-1), pentru listele cu numere min_wear+ (m-1), pentru listele cu numere mici, și de la min_wear la min_wear + (τ-mici, și de la min_wear la min_wear + (τ-1), pentru listele cu numere mari.1), pentru listele cu numere mari.

Page 19: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Dacă o singură pagină într-un block care a Dacă o singură pagină într-un block care a

fost mapată la nivel de block devine hotfost mapată la nivel de block devine hot Prima opțiune este de a schimba maparea fiecărei pagini Prima opțiune este de a schimba maparea fiecărei pagini din block în mapare la nivel de pagină. Cea de-a doua din block în mapare la nivel de pagină. Cea de-a doua opțiune este să se schimbe maparea doar pentru pagina opțiune este să se schimbe maparea doar pentru pagina hot din mapare la nivel block în mapare la nivel pagină și hot din mapare la nivel block în mapare la nivel pagină și să se lase restul block-ului mapat la nivel block. să se lase restul block-ului mapat la nivel block. Pentru ultima opțiune:Pentru ultima opțiune:Aceasta lasă block-ul fragmentat datorită corespondenței Aceasta lasă block-ul fragmentat datorită corespondenței paginilor fizice cu paginile hot care mai conțin date paginilor fizice cu paginile hot care mai conțin date invalide. Această fragmentare este înca acceptată invalide. Această fragmentare este înca acceptată fiindcă evită maparea la nivel pagină nenecesară. În fiindcă evită maparea la nivel pagină nenecesară. În acest experiment s-a gasit o fragmentare mai mică de acest experiment s-a gasit o fragmentare mai mică de 0.001% a întregii capacitați memoriei flash.0.001% a întregii capacitați memoriei flash.

Page 20: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Dacă o singură pagină într-un block care a Dacă o singură pagină într-un block care a fost mapată la nivel de block devine hotfost mapată la nivel de block devine hot

Când o pagină hot dintr-o listă cu număr mic este Când o pagină hot dintr-o listă cu număr mic este updatată, o nouă pagină aparținând block-ului listelor de updatată, o nouă pagină aparținând block-ului listelor de număr mic va fi utilizată. Acest lucru este făcut pentru a număr mic va fi utilizată. Acest lucru este făcut pentru a reține datele hot în block-uri din asociate listelor cu reține datele hot în block-uri din asociate listelor cu număr mic. Când update-ul este făcut paginilor asociate număr mic. Când update-ul este făcut paginilor asociate listelor cu numere mici și este identificat un block cold.Se listelor cu numere mici și este identificat un block cold.Se verifică maparea block-urilor din LBA. Întrucât LBA are verifică maparea block-urilor din LBA. Întrucât LBA are deja o mapare la nivel de pagini, pagina corespunzătoare deja o mapare la nivel de pagini, pagina corespunzătoare mapării block-urilor fizice va fi goală sau invalidă. Datele mapării block-urilor fizice va fi goală sau invalidă. Datele sunt scrise pe pagina corespunzătoare în block-ul fizic sunt scrise pe pagina corespunzătoare în block-ul fizic mapat (dacă pagina fizică este liberă) sau într-un block mapat (dacă pagina fizică este liberă) sau într-un block înregistrat (dacă pagina fizică este marcată ca invalidă înregistrat (dacă pagina fizică este marcată ca invalidă sau nu este liberă). Dacă nu este niciun block mapat sau nu este liberă). Dacă nu este niciun block mapat asociat cu LBA, acesta va fi scris într-unul din block-urile asociat cu LBA, acesta va fi scris într-unul din block-urile goale aparținând listelor cu număr mare deci datele cold goale aparținând listelor cu număr mare deci datele cold sunt plasate în mai multe block-uri utilizate.sunt plasate în mai multe block-uri utilizate.

Page 21: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Dacă o singură pagină într-un block care a Dacă o singură pagină într-un block care a fost mapată la nivel de block devine hotfost mapată la nivel de block devine hot

Similar când o pagina din block-ul aparținând unei liste cu număr Similar când o pagina din block-ul aparținând unei liste cu număr mare este updatată, dacă ea conține date cold, este stocată într-un mare este updatată, dacă ea conține date cold, este stocată într-un block nou cu liste numerotate cu număr mare. Întrucât aceste block-block nou cu liste numerotate cu număr mare. Întrucât aceste block-uri sunt mapate, update-urile trebuie să se facă în block-uri uri sunt mapate, update-urile trebuie să se facă în block-uri înregistrate. Unui block înregistrat îi poate fi asociat orice block de înregistrate. Unui block înregistrat îi poate fi asociat orice block de date. Block-urile de date și block-urile înregistrate sunt îmbinate la date. Block-urile de date și block-urile înregistrate sunt îmbinate la colectarea de gunoi. Această schemă este folosită numai pentru colectarea de gunoi. Această schemă este folosită numai pentru block-urile de date cold care au un număr foarte mic de update-uri. block-urile de date cold care au un număr foarte mic de update-uri. Astfel numărul cerut al block-urilor înregistrate este mic. Un Astfel numărul cerut al block-urilor înregistrate este mic. Un potențial dezavantaj al schemei este faptul că block-urile potențial dezavantaj al schemei este faptul că block-urile înregistrate conțin date hot rămân valide, mare parte dintre ele. În înregistrate conțin date hot rămân valide, mare parte dintre ele. În timpul colectării de gunoi, pot exista multe operații scumpe de timpul colectării de gunoi, pot exista multe operații scumpe de îmbinare completă între paginile valide ale unui block înregistrat și îmbinare completă între paginile valide ale unui block înregistrat și block-urile de date asociate lor. În cadrul acestor operații este block-urile de date asociate lor. În cadrul acestor operații este nevoie ca datele să fie copiate pe un block curățat și apoi block-urile nevoie ca datele să fie copiate pe un block curățat și apoi block-urile de date și cele înregistrate sunt șterse.de date și cele înregistrate sunt șterse.

Page 22: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Colectarea de gunoiColectarea de gunoi

Colectarea de gunoi este facută începând de la Colectarea de gunoi este facută începând de la block-urile listelor cu număr redus și apoi block-urile listelor cu număr redus și apoi ajungând până la listele cu număr mare. ajungând până la listele cu număr mare. Motivele din spatele acestui process sunt două: Motivele din spatele acestui process sunt două: Primul motiv este datorat block-urilor listelor cu Primul motiv este datorat block-urilor listelor cu număr mic care stochează datele hot, ele tind să număr mic care stochează datele hot, ele tind să aibă mai multe pagini invalide. Definesc aibă mai multe pagini invalide. Definesc curățarea eficientă a block-urilor cu formula:curățarea eficientă a block-urilor cu formula:

Page 23: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Colectarea de gunoiColectarea de gunoi

Dacă eficiența curațării unui block este mare, Dacă eficiența curațării unui block este mare, atunci mai puține pagini trebuie copiate înainte atunci mai puține pagini trebuie copiate înainte de ștergerea block-ului. Block-urile din listele cu de ștergerea block-ului. Block-urile din listele cu număr mic au o eficienta mai mare a curățării număr mic au o eficienta mai mare a curățării deoarece stochează date hot. Al doilea motiv deoarece stochează date hot. Al doilea motiv pentru colectarea de gunoi de la lista cu număr pentru colectarea de gunoi de la lista cu număr mic este acela că block-urile acestui tip de liste mic este acela că block-urile acestui tip de liste au număr mai mic de ștergeri. Colectarea de au număr mai mic de ștergeri. Colectarea de gunoi implică operații de ștergere așa că este gunoi implică operații de ștergere așa că este totdeauna mai bine să realizeze colectarea de totdeauna mai bine să realizeze colectarea de gunoi mai întâi pentru block-urile cu număr mic gunoi mai întâi pentru block-urile cu număr mic de ștergeri.de ștergeri.

Page 24: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Avantajele Avantajele Wear leveling-ului Wear leveling-ului staticstatic

Wear leveling-ul static mută datele cold din block-uri cu Wear leveling-ul static mută datele cold din block-uri cu număr mic de ștergeri în block-uri cu număr mai mare de număr mic de ștergeri în block-uri cu număr mai mare de ștergeri. Se eliberează astfel mai puține block-uri uzate ștergeri. Se eliberează astfel mai puține block-uri uzate care pot fi folosite pentru stocarea datelor cold. De care pot fi folosite pentru stocarea datelor cold. De asemenea împrăștie ulterior uzura block-urilor. asemenea împrăștie ulterior uzura block-urilor. Rejuvenator-ul realizează acest lucru într-un mod bine Rejuvenator-ul realizează acest lucru într-un mod bine determinat și numai când este necesar. Mutarea datelor determinat și numai când este necesar. Mutarea datelor cold este de obicei făcută schimbând datele cold ale unui cold este de obicei făcută schimbând datele cold ale unui block (cu număr mic de ștergeri) cu datele altui block cu block (cu număr mic de ștergeri) cu datele altui block cu număr mare de ștergeri. În cadrul Rejuvenator-ului acest număr mare de ștergeri. În cadrul Rejuvenator-ului acest proceseu este făcut sistematic.proceseu este făcut sistematic.Operațiile algoritmului Rejuvenator pot fi vizualizate într-Operațiile algoritmului Rejuvenator pot fi vizualizate într-o fereastră de mutare unde dimensiunea ferestrei este τ o fereastră de mutare unde dimensiunea ferestrei este τ ca în figura 1.ca în figura 1.

Figure 1 Funcționarea algoritmului Rejuvenator [30]

Page 25: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Adaptarea parametrului τAdaptarea parametrului τ

Aspectul cheie al Rejuvenator-ului este că Aspectul cheie al Rejuvenator-ului este că parametrul τ este ajustat potrivit duratei de viața parametrul τ este ajustat potrivit duratei de viața a block-urilor. Valoarea acestui parametru poate a block-urilor. Valoarea acestui parametru poate fi mare la început, când block-urile sunt departe fi mare la început, când block-urile sunt departe de atingerea duratei lor de viață. Pe măsură ce de atingerea duratei lor de viață. Pe măsură ce block-urile se apropie de durata de viață τ se block-urile se apropie de durata de viață τ se decrementează. Către sfârșitul duratei de viață a decrementează. Către sfârșitul duratei de viață a memoriei flash valoarea lui τ este foarte mică. memoriei flash valoarea lui τ este foarte mică. Pentru a-și atinge scopul se adoptă două Pentru a-și atinge scopul se adoptă două metode de decrementare a valorii lui τ.metode de decrementare a valorii lui τ.

Page 26: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Adaptarea parametrului τAdaptarea parametrului τFigure 2 Decrementarea liniara a lui τFigure 2 Decrementarea liniara a lui τ Figure 3 Decrementarea neliniara a lui τFigure 3 Decrementarea neliniara a lui τ

Page 27: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Decrementarea liniarăDecrementarea liniară

Notez diferența dintre 100K (numărul maxim Notez diferența dintre 100K (numărul maxim de ștergeri pe care un block o poate suporta) de ștergeri pe care un block o poate suporta) și max_wear (numărul maxim de ștergeri și max_wear (numărul maxim de ștergeri existent pentru block-urile din memorie) cu existent pentru block-urile din memorie) cu life_diff. Pe măsură ce block-urile sunt folosite, life_diff. Pe măsură ce block-urile sunt folosite, valoarea lui τ este r% din life_diff. Pentru valoarea lui τ este r% din life_diff. Pentru realizarea experimentului se va seta valoarea realizarea experimentului se va seta valoarea lui r la 10%. Pe măsură ce valoarea lui lui r la 10%. Pe măsură ce valoarea lui max_wear crește, valoarea lui life_diff scade max_wear crește, valoarea lui life_diff scade liniar și la fel și valoarea lui τ. Figura 2 liniar și la fel și valoarea lui τ. Figura 2 ilustreaza modelul de descreștere a valorii lui τ ilustreaza modelul de descreștere a valorii lui τ în schema liniară.în schema liniară.

Page 28: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Decrementarea neliniară: Decrementarea neliniară:

1.1. Decrementarea liniară uniformă reduce Decrementarea liniară uniformă reduce valoarea lui τ cu r% de fiecare atunci când valoarea lui τ cu r% de fiecare atunci când decrementarea este declanșată. Dacă este decrementarea este declanșată. Dacă este nevoie de un control mai eficient, valoarea lui τ nevoie de un control mai eficient, valoarea lui τ trebuie modificată neliniar adică, trebuie modificată neliniar adică, decrementarea lui τ trebuie făcută inițial mai decrementarea lui τ trebuie făcută inițial mai lent și mai rapid către sfârșit. Figura 3 lent și mai rapid către sfârșit. Figura 3 ilustrează această schemă. Se alege curba din ilustrează această schemă. Se alege curba din figura 3 și i se setează valoarea pantei, curbei figura 3 și i se setează valoarea pantei, curbei corespunzătoare valorii life_diff, ca τ. Se poate corespunzătoare valorii life_diff, ca τ. Se poate vedea că rata de descreștere a lui τ este mult vedea că rata de descreștere a lui τ este mult mai abruptă la sfârșitul duratei de viață. mai abruptă la sfârșitul duratei de viață.

Page 29: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Adaptarea parametrului mAdaptarea parametrului m

Ajustarea a lui m ajută la reducerea migrării Ajustarea a lui m ajută la reducerea migrării datelor. Când valoarea lui m este incrementată datelor. Când valoarea lui m este incrementată sau decrementată, tipul de mapare a block-urilor sau decrementată, tipul de mapare a block-urilor (la nivel de block sau la nivel de pagină) nu este (la nivel de block sau la nivel de pagină) nu este schimbat imediat. Maparea este schimbată la schimbat imediat. Maparea este schimbată la tipul relevant doar la primirea cererilor de scriere tipul relevant doar la primirea cererilor de scriere după incrementarea sau decrementarea după incrementarea sau decrementarea parametrului m. Din această cauză o parte din parametrului m. Din această cauză o parte din block-uri asociate listelor numerotate cu numere block-uri asociate listelor numerotate cu numere mici vor rămâne mapate la nivel de block-uri. mici vor rămâne mapate la nivel de block-uri. Problemă este rezolvată în timpul wear leveling-Problemă este rezolvată în timpul wear leveling-ului static și operațiunilor de colectare de gunoi.ului static și operațiunilor de colectare de gunoi.

Page 30: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Comparatia algoritmilorComparatia algoritmilor

Figure 4 Numărul de cereri de scriere realizate înainte ca primul block sa atingă durata de

Page 31: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Comparatia algoritmilorComparatia algoritmilor

Figure 7 Distribuția numărului de ștergeri pe block-uri

Page 32: Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Vă mulțumesc!Vă mulțumesc!

Intrebări?Intrebări?


Recommended