08__AOK__Ligjërata 8__Memoria virtuale. Përkthimi i adresave virtuale në adresa fizike -- MSc. Valdrin Haxhiu.pdf

Kolegji UBT Arkitektura dhe organizimi i kompjuterëve Ligjërata 8 Memoria virtuale. Përkthimi i adresave virtuale në adresa fizike MSc. Valdrin Haxhiu Faqja virtuale me madhësi 4 KB DRAM ⋮ Hapësira virtuale e adresave... Hapësira fizike e adresave HDD Swap file Faqja fizike me madhësi 4 KB MSc. Vald...

Kolegji UBT Arkitektura dhe organizimi i kompjuterëve Ligjërata 8 Memoria virtuale. Përkthimi i adresave virtuale në adresa fizike MSc. Valdrin Haxhiu Faqja virtuale me madhësi 4 KB DRAM ⋮ Hapësira virtuale e adresave... Hapësira fizike e adresave HDD Swap file Faqja fizike me madhësi 4 KB MSc. Valdrin Haxhiu Shembull 1: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 30 bit dhe faqja ka madhësinë 4 KB, gjeni: 1) 2) 3) 4) numrin e bitëve për pjesën offset të faqes virtuale – OFV (virtual page offset – VPO) numrin e bitëve për pjesën offset të faqes fizike – OFF (physical page offset – PPO) numrin e bitëve për pjesën e numrit të faqes virtuale – NFV (virtual page number – VPN) numrin e bitëve për pjesën e numrit të faqes fizike – NFF (physical page number – PPN) Zgjidhje: 1) Meqë madhësia e faqes virtuale është 4 KB, për adresimin e secilit bajt brenda 4 KB nevojiten: 4 KB = 22 · 210 B = 212 B → log2 212 = 12 bit për OFV 2) Madhësia e faqes fizike është e barabartë me madhësinë e faqes virtuale. Pra, nevojiten: 4 KB = 22 · 210 B = 212 B → log2 212 = 12 bit për OFF 3) Gjatësia e adresës virtuale është 32 bit. Prej 32 bitëve, 12 bit përdoren për OFV dhe mbesin: 32 – 12 = 20 bit për NFV 4) Gjatësia e adresës fizike është 30 bit. Prej 30 bitëve, 12 bit përdoren për OFF dhe mbesin: 30 – 12 = 18 bit për NFF Në Figura 1 kemi paraqitur formatin e adresës virtuale dhe në Figura 2 kemi paraqitur formatin e adresës fizike. 32 bit NFV 20 bit OFV 12 bit Figura 1 – Formati i adresës virtuale 1 MSc. Valdrin Haxhiu 30 bit NFF OFF 12 bit 18 bit Figura 2 – Formati i adresës fizike Shembull 2: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 30 bit dhe faqja ka madhësinë 8 KB: 1) Sa është numri i faqeve virtuale? 2) Sa është numri i faqeve fizike? Zgjidhje: 1) Meqë madhësia e faqes virtuale është 8 KB, për adresimin e secilit bajt brenda 8 KB nevojiten: 8 KB = 23 · 210 B = 213 B → log2 213 = 13 bit për OFV. Gjatësia e adresës virtuale është 32 bit. Prej 32 bitëve, 13 bit përdorën për OFV dhe mbesin: 32 – 13 = 19 bit për NFV. Me 19 bit mund të adresohen 219 = 524, 288 faqe virtuale. Pra, numri i faqeve virtuale është 524, 288. 2) Madhësia e faqes fizike është e barabartë me madhësinë e faqes virtuale. Pra, nevojiten: 8 KB = 23 · 210 B = 213 B → log2 213 = 13 bit për pjesën OFF. Gjatësia e adresës fizike është 30 bit. Prej 30 bitëve, 13 bit përdorën për OFF dhe mbesin: 30 – 13 = 17 bit për NFF. Me 17 bit mund të adresohen 217 = 131, 072 faqe fizike. Pra, numri i faqeve fizike është 131, 072. Në këtë shembull, numri faqeve virtuale është më i madh se numri i faqeve fizike. Hapësira e adresave virtuale (virtual address space) është 232 = 4 GB. Hapësira e adresave fizike (physical address space) në DRAM është 230 = 1 GB. Ideja e memories virtuale është që 2 MSc. Valdrin Haxhiu programet (proceset) gjatë punës së tyre të adresojnë më shumë memorie DRAM se sa është e instaluar fizikisht në kompjuter. Kjo arrihet duke e përdorë një pjesë të diskut (HDD ose SSD) si pjesë të memories DRAM. Pra, programeve u ofrohet më shumë memorie DRAM përmes memories virtuale. Ndryshimi i hapësirës virtuale prej asaj fizike në këtë shembull është për 3 GB. Pra, edhe pse në kompjuter është instaluar vetëm 1 GB memorie DRAM, programet mund të përdorin deri në 4 GB memorie DRAM duke i marrë 3 GB shtesë si memorie virtuale nga disku. Për funksionimin e memories virtuale është i nevojshëm përkthimi i adresave virtuale në adresa fizike sepse në memorien DRAM mund të shkruhet/lexohet vetëm përmes adresave fizike. Shembull 3: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 28 bit, faqja ka madhësinë 4 KB dhe një pjesë e tabelës së faqes (page table) është dhënë në Tabela 1, cila është adresa e faqes fizike për faqen virtuale me adresë 0x12212112 (në formë heksadecimale)? Tabela 1 – Një pjesë e tabelës së faqes NFV 0x11221 0x12212 0x12213 0x12214 0x12215 0x12216 0x12217 R 1 1 1 1 1 1 1 D 1 1 0 1 1 0 1 NFF 0x1112 0x1322 0x1722 0x2522 0x3605 0x5650 0x7841 Zgjidhje: Meqë madhësia e faqes është 4 KB, nevojiten 12 bit për OFV dhe OFF. NFV ka gjatësinë 20 bit dhe NFF ka gjatësinë 16 bit. Në Figura 3 kemi paraqitur përkthimin e adresës virtuale 0x12212112 në adresën fizike 0x1322112 bazuar në pjesën e tabelës që është dhënë në këtë shembull. Numri i faqes virtuale shërben për gjetjen e numrit të faqes fizike në tabelën e faqes. Nëse faqja fizike që i takon faqes së caktuar virtuale gjendet në memorie (në DRAM ose në kesh), atëherë vlera në kolonën R (resident) në tabelën e faqes është 1. Nëse faqja fizike nuk është në DRAM ose në kesh atëherë biti R ka vlerën 0 dhe në ato raste paraqitet një page fault që angazhon sistemin operativ (p.sh. Microsoft Windows) që atë faqe fizike të sjellë nga disku në DRAM dhe vlerën e bitit R të ndryshojë në 1. Tabela e faqes menaxhohet nga sistemi operativ. Kërkimin për përkthimin e adresave virtuale në adresa fizike e bën pjesa harduerike e njohur si njësia për menaxhim të memories (memory management unit – MMU) që gjendet në CPU. 3 MSc. Valdrin Haxhiu Adresa virtuale 32 bitëshe 0x12212 0x112 OFV NFV NFV 0x11221 0x12212 0x12213 0x12214 0x12215 0x12216 0x12217 R 1 1 1 1 1 1 1 D 1 1 0 1 1 0 1 NFF 0x1112 0x1322 0x1722 0x2522 0x3605 0x5650 0x7841 Adresa fizike 28 bitëshe 0x1322 0x112 NFF OFF Figura 3 – Përkthimi i adresës virtuale në adresë fizike Në Figura 3, shihet që vetëm NFV përkthehet në NFF. OFV është i njëjtë me OFF, prandaj nuk ka nevojë të përkthehet. Në Figura 4 kemi paraqitur thjeshtë skemën e punës që bëhet gjatë përkthimit të adresës virtuale në adresë fizike. Më poshtë është dhënë kuptimi i hapave në Figura 4 të paraqitur me anë të rrathëve me numrat e hapave: 1. Në hapin e parë, programi përmes procesorit dërgon adresën virtuale te pjesa MMU 2. Në hapin e dytë, pjesa MMU i qaset tabelës së faqes në DRAM 3. Në hapin e tretë, NFV e ka NFF në tabelën e faqes dhe adresa fizike e adresës virtuale kthehet në MMU 4. Në hapin e katërt, MMU përmes adresës fizike 0x1322112 i qaset faqes fizike në DRAM 5. Në hapin e pestë, faqja fizike me fillim në adresën fizike 0x1322112 merret nga memoria DRAM dhe dërgohet në procesor. Në këtë shembull, tabela e faqes gjendet në memorien DRAM. Për të shpejtuar përkthimin e adresave virtuale në adresa fizike, një pjesë e tabelës së faqes vendoset në memorien kesh dhe njihet si translation lookaside buffer – TLB. Çdo program gjatë punës e ka hapësirën e vet virtuale të adresave. 4 MSc. Valdrin Haxhiu RAM 0x0000000 4 KB Çipi i CPU-së 0x0001000 4 KB 0x0002000 1... 2 MMU Procesori Tabela e faqes 3 0x1322112 4 5 0x1323112 4 KB 0x1324112... 0xFFFEFFF 4 KB 0xFFFFFFF Figura 4 – Skema e punës për përkthimin e adresës virtuale në adresë fizike Në Tabela 1, gjendet edhe kolona D që paraqet një dirty bit, përmes të cilit ruhet informata se a është ndryshuar (përmes shkrimit në të) faqja e caktuar. Nëse biti D e ka vlerën 1, përmbajtja e faqes është ndryshuar dhe nëse biti D e ka vlerën 0, përmbajtja e faqes nuk është ndryshuar. Biti D ndihmon në rastin kur një faqe duhet të merret në disk e të vendoset në DRAM. Nëse në DRAM nuk ka vend të lirë për faqen që merret në disk, atëherë përmes një algoritmi për zëvendësim (p.sh. least recently used) faqja e caktuar që është vendosur më herët largohet nga memoria DRAM dhe nëse biti D i asaj faqeje në tabelën e faqes është 1, ajo faqe e mbishkruan versionin e saj të mëhershëm në disk. Nëse biti D ka vlerën zero, atëherë nuk është e nevojshme që faqja që largohet nga memoria DRAM të shkruhet në disk. 5 MSc. Valdrin Haxhiu Shembull 4: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 30 bit, faqja ka madhësinë 8 KB dhe një pjesë e tabelës së faqes (page table) është dhënë në Tabela 2, cila është adresa e faqes fizike për faqen virtuale me adresë 0x30120011 (në formë heksadecimale)? Tabela 2 – Një pjesë e tabelës së faqes NFV 0x14542 0x22123 0x19521 0x12214 0x18090 0x12216 0x13556 R 1 1 1 1 1 1 1 D 0 1 0 0 0 0 1 NFF 0x1132 0x1322 0x1722 0x2522 0x1120 0x5650 0x7841 Zgjidhje: Në këtë shembull, faqja ka madhësinë 8 KB. Për OFV dhe OFF nevojiten 8 KB = 23 · 210 B → log2 213 =13 bit. Numri i bitëve për NFV është: 32 – 13 = 19 Numri i bitëve për NFF është: 30 – 13 = 17 Bitët e adresës virtuale 0x30120011 janë paraqitur në Figura 5. NFV 32 bit OFV 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 19 bit 13 bit Figura 5 – Bitët e adresës virtuale 0x30120011 Duke shndërruar 19 bitët e NFV në formë heksadecimale (duke i grupuar bitët në grupe me nga 4 bit) fitohet NFV = 0x18090 dhe duke shikuar tabelën e dhënë të faqes shihet se NFF është 0x1120. Adresa fizike formohet duke i bashkuar bitët e NFF dhe OFF. Bitët e adresës fizike i kemi paraqitur në Figura 6. 6 MSc. Valdrin Haxhiu 30 bit NFF OFF 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 17 bit 13 bit Figura 6 – Bitët e adresës fizike Duke shndërruar në formë heksadecimale, nga bitët e adresës fizike fitohet adresa fizike 0x2240011 e faqes fizike të faqes virtuale me adresë 0x30120011. Shembull 5: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 30 bit dhe faqja ka madhësinë 4 KB: 1) 2) 3) 4) 5) Sa është numri i faqeve virtuale? Sa është numri i faqeve fizike? Sa rreshta ka tabela e faqes? Sa bit ka rreshti brenda tabelës së faqes? Sa bitëshe është madhësia e tabelës së faqes? Zgjidhje: 1) Në bazë të madhësisë së faqes, 12 bit prej 32 bitëve të adresës virtuale janë për OFV. Për NFV janë 32 – 12 = 20 bit. Me 220 fitohen 1, 048, 576 faqe virtuale. 2) Për NFF janë 30 – 12 = 18 bit. Numri i faqeve fizike është 218 = 262, 144. 3) Meqë në tabelën e faqes vendoset nga një rresht për secilën faqe virtuale, atëherë numri i rreshtave në tabelën e faqes është i barabartë me numrin e faqeve virtuale. 4) Në secilin rresht të tabelës së faqes ruhet biti R, biti D dhe bitët e numrit të faqes fizike. Pra, në secilin rresht të tabelës së faqes ruhen 1 + 1 + 18 = 20 bit. 7 MSc. Valdrin Haxhiu 5) Meqë në secilin rresht ruhen 20 bit dhe numri i rreshtave është 1, 048, 576, atëherë tabela e faqes ka 20 ∙ 1, 048, 576 = 20, 971, 520 bit. Shembull 6: Nëse adresa virtuale ka gjatësinë 32 bit, adresa fizike ka gjatësinë 28 bit, faqja ka madhësinë 4 KB dhe një pjesë e tabelës së faqes (page table) është dhënë në Tabela 3, cila është adresa e faqes fizike për faqen virtuale me adresë 0x12212112 (në formë heksadecimale)? Tabela 3 – Një pjesë e tabelës së faqes NFV 0x11221 0x12212 0x12213 0x12214 0x12215 0x12216 0x12217 R 1 0 1 1 1 1 1 D 1 0 0 1 1 0 1 NFF 0x1112 page fault 0x1722 0x2522 0x3605 0x5650 0x7841 Zgjidhje: Ky shembull është i ngjashëm me shembullin 3, por në këtë rast për faqen virtuale me adresë 0x12212112 nuk mund të formohet menjëherë adresa fizike e faqes fizike sepse në tabelën e faqes nuk ekziston NFF. Nëse nuk ekziston NFF në tabelën e faqes, atëherë faqja fizike me atë NFF nuk ekziston në DRAM dhe me ndihmën e sistemit operativ, faqja nga disku vendoset në DRAM dhe për atë faqe vendoset vlera 1 për bitin R dhe vlera 0 për bitin D. Pas vendosjes në DRAM të faqes fizike, nga NFF e asaj faqeje fizike dhe OFF mund të formohet adresa fizike me anë të cilës bëhet qasja në faqen fizike në DRAM. Në Figura 7 kemi paraqitur thjeshtë skemën e punës që bëhet gjatë përkthimit të adresës virtuale në adresë fizike. 8 MSc. Valdrin Haxhiu RAM 0x0000000 4 KB Çipi i CPU-së 0x0001000 4 KB MMU Procesori 0x0002000 2 3 1 8 7 9 6... Tabela e faqes 0x1322112 0x1323112 4 5 4 KB 0x1324112... 0xFFFEFFF 4 KB Disku 0xFFFFFFF Figura 7 – Skema e punës për përkthimin e adresës virtuale në adresë fizike Më poshtë është dhënë kuptimi i hapave në Figura 7 të paraqitur me anë të rrathëve me numrat e hapave: 1. 2. 3. 4. 5. 6. 7. 8. 9. Në hapin e parë, programi përmes procesorit dërgon adresën virtuale te pjesa MMU Në hapin e dytë, pjesa MMU i qaset tabelës së faqes në DRAM Në hapin e tretë, informata se në tabelën e faqes nuk ka NFF kthehet në MMU Në hapin e katërt, MMU përmes procesorit ka kërkuar ndihmën e sistemit operativ dhe sistemi operativ ka marrë faqen fizike përkatëse nga disku Në hapin e pestë, faqja fizike nga disku vendoset në DRAM me fillim në adresën fizike 0x1322112 dhe në tabelën e faqes në rreshtin përkatës vendoset vlera 1 për bitin R, vlera 0 për bitin D dhe NFF Në hapin e gjashtë, MMU i qaset prapë tabelës së faqes në DRAM Në hapin e shtatë, NFV e ka NFF në tabelën e faqes dhe adresa fizike e adresës virtuale kthehet në MMU Në hapin e tetë, MMU përmes adresës fizike 0x1322112 i qaset faqes fizike në DRAM Në hapin e nëntë, faqja fizike me fillim në adresën fizike 0x1322112 merret nga memoria DRAM dhe dërgohet në procesor. 9