Bai07 bo nho

  • Published on
    05-Jul-2015

  • View
    421

  • Download
    3

Embed Size (px)

Transcript

  • 1. TH 106: H iu hnh Khoa CNTT H KHTN

2. Khi nim cache Cc c im chung Truy sut nhanh Gim tn xut truy cp b nh Tng dung lng phc v ca b x l chnh Tng kch thc n v d liu H KHTN TpHCM TH 106: H iu hnh Registers Cache Memory 3. gn processor hn l b nh chnh Nh v nhanh hn b nh chnh Nh l b nh tm: cha gi tr vng nh trn b nh chnh ni mi va truy cp. Chuyn i d liu gia cache v b nh chnh c tnh theo n v: blocks/lines Caches cng cha gi tr nh gn vi nh va c truy xut nh x gia b nh v cache l nh x tnh (hu ht) X l nhanh khi xy ra li trang Thng thng l c mt cache chnh v nhiu caches ph (L1, L2, L3, ...) H KHTN TpHCM TH 106: H iu hnh 4. Kch thc cache v kch thc cache block nh x: physical/virtual caches Thut ton thay th H KHTN TpHCM TH 106: H iu hnh word transfer block transfer Registers Cache Memory 5. Cu hi: Phi lm g nu ta mun thc thi chng trnh m yu cu b nh ln hn b nh ta ang c sn? H KHTN TpHCM TH 106: H iu hnh Registers Cache Memory 6. Tr li: Gi lp nh chng ta c b nh ln hn: B nh o H KHTN TpHCM TH 106: H iu hnh Registers Cache Memory Virtual Memory 7. Mt trang l mt n v ca b nh o (cache c) HH qun l vic nh x gia cc trang ca VM v b nh vt l H KHTN TpHCM TH 106: H iu hnh Cache Memory Memory VM frame page 8. Nhn t phn cng chia s b nh vt l Nhn t phn mm mt tin trnh s ch thy: khng gian a ch o ca n Qun l b nh ca HH l kt hp hai cch nhn trn Bn vng (Consistency): cc b nh vt l trng ging nhau Cp pht a ch (Relocation): tin trnh c th c np ln ti bt k a ch vt l no Bo v (Protection): mt tin trnh khng th truy cp vng nh ca tin trnh khc Chia s (Sharing): cho php chia s b nh vt l (phi ci t iu khin) H KHTN TpHCM TH 106: H iu hnh 9. Vn phn mnh trong mi trng a chng H KHTN TpHCM TH 106: H iu hnh B nh B nh Tin trnh mi 10. Phn mnh ngoi vi (External Fragmentation) tng b nh trng tha yu cu, nhng khng lin tc Phn mnh ni vi (Internal Fragmentation) mi block c cp pht ln hn yu cu b nh mt t Gii php phn mnh ngoi vi: kt hp Chuyn cc vng trng thnh mt khi b nh lin tc Ch thc hin c nu HH h tr bin dch a ch trong thi gian thc thi H KHTN TpHCM TH 106: H iu hnh 11. Cp pht b nh kch thc X c thc hin nh th no? First-fit: cp pht vng trng u tin cho yu cu. Best-fit: cp pht vng trng nh nht va yu cu; phi duyt ton danh sch, nu khng sp theo th t. S to ra vng nh trng d ra nh nht. Worst-fit: cp pht vng trng ln nht; phi duyt ton danh sch. S to nhng trng d ra ln nht. First-fit v best-fit tt hn worst-fit v mt tc v vic tn dng b nh. H KHTN TpHCM TH 106: H iu hnh 12. B nh o l s tru tng ha ca HH, n cung cp ngi lp trnh mt khng gian a ch ln hn khng gian a ch vt l tht s B nh o c th c trin khai bng cch phn trang hoc phn on, hin ti phn trang thng dng hn M hnh kt hp cng thng c dng, phn on thng kh n gin (v.d., mt s lng xc nh cc on cng kch thc) Hu ch ca b nh o: Lp trnh vin khng lo lng vi vic cc my tnh khc nhau c kch thc b nh vt l khc nhau Phn mnh trong mi trng a chng H KHTN TpHCM TH 106: H iu hnh 13. MMU: memory management unit H KHTN TpHCM TH 106: H iu hnh Processor Physical memory translation box (MMU) 14. H KHTN TpHCM TH 106: H iu hnh a ch logic offset segment segment table + a ch vt l 15. Cc on c kch thc khc nhau Bin dch a ch da vo cc thanh ghi (base, size, state) bng phn on Trng thi (state): valid/invalid, access permission, reference bit, modified bit Cc on c th trc quan vi lp trnh vin v tin li, chia ra hai loi on, dng cho m chng trnh hay d liu (ngha l code segment hoc l data segments) H KHTN TpHCM TH 106: H iu hnh 16. H KHTN TpHCM TH 106: H iu hnh a ch logic page table + a ch vt l page # offset 17. Cc trang c kch thc c nh B nh vt l tng ng vi trang gi l page frame Chuyn i a ch thng qua bng trang, c nh ch mc bng page number Mi mc tin trong bng trang lu mt con s i din page frame m trang nh x ti v trng thi ca trang trong b nh Trng thi: valid/invalid, access permission, reference bit, modified bit, caching Vic phn trang l trong sut vi ngi lp trnh H KHTN TpHCM TH 106: H iu hnh 18. Mt vi MMU kt hp phn trang v phn on Chuyn i a ch phn on trc a ch on lu a ch bng trang cho on Bng trang c nh ch mc bng phn page number trong a ch o v nh x ti page frame tng ng Ngy nay ngi ta khng cn dng phn on nhiu na UNIX s dng m hnh phn on n gin nhng khng yu cu h tr ca phn cng H KHTN TpHCM TH 106: H iu hnh 19. H KHTN TpHCM TH 106: H iu hnh CPU p d p f f d f d page table Memory virtual address physical address 20. 000 000 000 000 111 000 101 000 000 000 011 100 000 110 001 010 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Bang trang Bit trang thai 110 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 Giatrtrang ao =2, cung la chmuc cua bang trang 12 bit a ch offset chep nguyen qua a chvat ly a chao (8196) a chvat ly (24580) Bng trang 16-bit, Mi trang kch thc 4KB H KHTN TpHCM TH 106: H iu hnh 21. H KHTN TpHCM TH 106: H iu hnh 22. H KHTN TpHCM TH 106: H iu hnh B nh 32-byte v m i trang 4 byte 23. Mi truy cp b nh tm trang vt l tng ng ca trang o phi rt nhanh H KHTN TpHCM TH 106: H iu hnh Caching, la chn u tin Chng ta vn phi tm kim a ch vt l ca trang t cc mu tin trn bng trang? Tng t nh cc cache b nh thng thng 24. Cache cho cc mu tin trong bng trang gi l Translation Lookaside Buffer (TLB) Thng l 64 mu tin Mi mu tin ca TLB cha 1 page number v mt mu tin ca bng trang tng ng Mi ln truy cp b nh, chng ta tm page number frame c nh x trong TLB bi trang ny H KHTN TpHCM TH 106: H iu hnh 25. H KHTN TpHCM TH 106: H iu hnh 26. H KHTN TpHCM TH 106: H iu hnh CPU p d f d f d TLB Memory virtual address physical address p/f f 27. iu g xy ra nu TLB khng cha thng tin bng trang truy cp? TLB miss Thu hi mt mu tin trn TLB nu khng c mu tin ang rnh Chnh sch thay th? Chp vo TLB mu tin thiu t bng trang TLB misses c th c x l bng phn cng hoc phn mm Phn mm cho php ng dng h tr quyt nh thay th H KHTN TpHCM TH 106: H iu hnh 28. H KHTN TpHCM TH 106: H iu hnh 29. Khng gian a ch c th ln hn b nh vt l Chng ta lu n u? Chng ta lu bng trang u? H KHTN TpHCM TH 106: H iu hnh 30. iu th v l s dng b nh m rng a ch b nh, kch thc b nh vt l gim Trade-off nh th no! Cn hiu c tnh ca cc ng dng Bng trang c th rt ln! Gii php? H KHTN TpHCM TH 106: H iu hnh OS Code Globals Stack Heap P1 Page Table P0 Page Table Trong b nh 31. H KHTN TpHCM TH 106: H iu hnh 32. Mt a ch logic (my 32-bit kch thc trang 4K) c chia thnh: Page number: 20 bits. Page offset: 12 bits. V bng trang li c phn trang, page number li c chia thnh: 10-bit: page number. 10-bit: page offset. H KHTN TpHCM TH 106: H iu hnh 33. Vy, a ch logic nh sau: Vi pi l ch mc trong outer page table, v p2 l ch mc ca mt trang thuc outer page table. H KHTN TpHCM TH 106: H iu hnh page number page offset pi p2 d 10 10 12 34. Lc chuyn i a ch ca kin trc phn trang 2 cp 32-bit H KHTN TpHCM TH 106: H iu hnh 35. V mi cp c lu nh mt bng phn bit trong b nh, chuyn i a ch logic thnh a ch vt l tn ti 4 ln truy cp b nh. Caching cho php cc tnh ton ny kh thi. Cache t 98% hit th: effective access time = 0.98 x 120 + 0.02 x 520 = 128 nanoseconds. B chm li ch c 28% trong vic truy cp b nh. 128-100 = 28 nanoseconds. Gi s 1 truy cp b nh l 100 ns, thi gian tm trn TLB l 20 ns, nn nu 1 hit trn LTB => tn 120 ns. Cn nu miss th 4*100 + 20(search tren TLB) + 100 truy cp frame = 520ns H KHTN TpHCM TH 106: H iu hnh 36. Mc tiu ca bng trang l tm ra trang vt l tng ng ca tng trang o Tuy nhin, s lng trang o rt ln kch thc bng trang c th chim mt khng gian ln trn b nh V d h thng 64-bit a ch, kch thc mi trang l 4KB, vy bng trang cn 252 mu tin. Nu mi mu tin 8 bytes th bng trang chim 30 triu GB. H KHTN TpHCM TH 106: H iu hnh 37. Mi mu tin dnh cho 1 trang tht (frame) trn b nh. Mi mu tin gm a ch o ca trang, cng vi thng tin v tin trnh ang dng trang ny. Gim b nh cn thit lu mi trang, nhng tng thi gian tm bng trang. S dng CTDL bng bm (hash table) tng tc tm kim. H KHTN TpHCM TH 106: H iu hnh 38. H KHTN TpHCM TH 106: H iu hnh 39. Nu khng gian a ch o ca mt tin trnh nh hn b nh vt l th khng c vn g Ch lo gii quyt vn phn mnh Khi b nh o ca mt tin trnh ln hn b nh vt l Mt phn lu trn b nh Mt phn lu trn a Gii quyt ntn? H KHTN TpHCM TH 106: H iu hnh 40. bt u mt tin trnh (chng trnh), ch np trang cha on m cho tin trnh bt u thc thi Khi tin trnh c yu cu ti vng nh (cha lnh hay d liu) nm ngoi trang np, th np trang ln Lm sao biu din mt trang ca my o m n cha np ln b nh? H KHTN TpHCM TH 106: H iu hnh 0 1 2 1 v i i A B C 0 1 2 3 A 0 1 2 B C VM Paging Table Memory Disk 41. H KHTN TpHCM TH 106: H iu hnh 42. iu g xy ra khi tin trnh yu cu mt trang b nh du li? Trap li trang Kim tra c phi truy xut hp l (c trang vt l ng) Tm 1 frame b nh trng c trang cn thit t b nh ph ( a) i valid bit ca trang thnh v (hp l) Bt u li lnh b ngt bi trap Nu khng c frame trng th sao? H KHTN TpHCM TH 106: H iu hnh 43. Cc tnh hung khi truy cp b nh? Nu TLB miss c mu tin trong bng trang V nu, li trang (=>thay trang) V nu, tt c cc frames ang dng cn thu hi mt trang thay i gi tr trong bng trang ca tin trnh c trang cn thit, cp nht mu tin ca bng trang, cp nht TLB H KHTN TpHCM TH 106: H iu hnh 44. Trap, kim tra bng trang, tm frame trng (hoc tm trang thay th) khong 200 - 600 s Tm v c trn a khong 10 ms Truy cp b nh khong 100 ns Li trang lm chm thc thi khong ~100,000 ln!!!!! l cha k pht sinh c th xy ra trong cc bc trn Tt nht l khng xy ra nhiu li trang! Nu mun s nh hng t hn 10%, ch cho php 1 li trang trong 1,000,000 ln truy cp b nh H KHTN TpHCM TH 106: H iu hnh 45. Nu khng cn frame trng khi b li trang? Ly li mt frame ang c s dng Chn frame thay th (nn nhn) Lu trang nn nhn vo a Cp nht li bng trang (trang nn nhn thnh invalid) c trang cn thit vo frame va chn Cp nht li bng trang (trang va thay th l valid) Bt u li lnh gy ra li trang Ti u ha: khng phi ghi trang nn nhn tr li nu nh n vn cha b thay i (cn thm dirty bit cho mi trang). H KHTN TpHCM TH 106: H iu hnh 46. Khng d dng tm c chnh sch thay th trang tt Khi thu hi mt trang, lm sao chng ta bit l trang tt nht c th gim thiu li trang sau ny? C tn ti thut ton thay th tran