Bài giảng Hệ điều hành (Operating Systems) - Chương V-I: Liên lạc giữa các Tiến Trình - Vũ Đức Lung

duï caùc thuû tuïc xöû lyù loãi)
Hoã trôï töø heä ñieàu haønh – Thoâng thöôøng, user chòu traùch nhieäm thieát keá vaø hieän thöïc caùc chöông trình coù dynamic loading. – Heä ñieàu haønh chuû yeáu cung caáp moät soá thuû tuïc thö vieän hoã trôï, taïo ñieàu kieän deã daøng hôn cho laäp trình vieân. Khoa KTMT 17 Cô cheáá phuûû laéép (overlay)
Taïi moãi thôøi ñieåm, chæ giöõ laïi trong boä nhôù nhöõng leänh hoaëc döõ lieäu caàn thieát, giaûi phoùng caùc leänh/döõ lieäu chöa hoaëc khoâng caàn duøng ñeán.
Cô cheá naøy raát höõu duïng khi kích thöôùc moät process lôùn hôn khoâng gian boä nhôù caáp cho process ñoù.
Cô cheá naøy ñöôïc ñieàu khieån bôûi ngöôøi söû duïng (thoâng qua söï hoã trôï cuûa caùc thö vieän laäp trình) chöù khoâng caàn söï hoã trôï cuûa heä ñieàu haønh Khoa KTMT 18 Pass 1 70K Pass 2 80K Symbol table 20K Common routines 30K Pass 1 70K Pass 2 80K Symbol table 20K Common routines 30K Assembler Total memory available = 150KB Cô cheáá overlay (tt) symbol table 20K common routines 30K overlay driver 10K pass 1 pass 2 80K70K Ñôn vò: byte naïp vaø thöïc thi 4Khoa KTMT 19 Cô cheáá hoaùùn vò (swapping)
Moät process coù theå taïm thôøi bò swap ra khoûi boä nhôù chính vaø löu treân moät heä thoáng löu tröõ phuï. Sau ñoù, process coù theå ñöôïc naïp laïi vaøo boä nhôù ñeå tieáp tuïc quaù trình thöïc thi. Swapping policy: hai ví duï – Round-robin: swap out P1 (vöøa tieâu thuï heát quantum cuûa noù), swap in P2 , thöïc thi P3 , – Roll out, roll in: duøng trong cô cheá ñònh thôøi theo ñoä öu tieân (priority-based scheduling)  Process coù ñoä öu tieân thaáp hôn seõ bò swap out nhöôøng choã cho process coù ñoä öu tieân cao hôn môùi ñeán ñöôïc naïp vaøo boä nhôù ñeå thöïc thi
Hieän nay, ít heä thoáng söû duïng cô cheá swapping treân Khoa KTMT 20 Minh hoïïa cô cheáá swapping Khoa KTMT 21 Moââ hình quaûûn lyùù boää nhôùù
Trong chöông naøy, moâ hình quaûn lyù boä nhôù laø moät moâ hình ñôn giaûn, khoâng coù boä nhôù aûo.
Moät process phaûi ñöôïc naïp hoaøn toaøn vaøo boä nhôù thì môùi ñöôïc thöïc thi (ngoaïi tröø khi söû duïng cô cheá overlay).
Caùc cô cheá quaûn lyù boä nhôù sau ñaây raát ít (haàu nhö khoâng coøn) ñöôïc duøng trong caùc heä thoáng hieän ñaïi – Phaân chia coá ñònh (fixed partitioning) – Phaân chia ñoäng (dynamic partitioning) – Phaân trang ñôn giaûn (simple paging) – Phaân ñoaïn ñôn giaûn (simple segmentation) Khoa KTMT 22 Phaânâ maûûnh (fragmentation)
Phaân maûnh ngoaïi (external fragmentation) – Kích thöôùc khoâng gian nhôù coøn troáng ñuû ñeå thoûa maõn moät yeâu caàu caáp phaùt, tuy nhieân khoâng gian nhôù naøy khoâng lieân tuïc ⇒ coù theå duøng cô cheá keát khoái (compaction) ñeå gom laïi thaønh vuøng nhôù lieân tuïc.
Phaân maûnh noäi (internal fragmentation) – Kích thöôùc vuøng nhôù ñöôïc caáp phaùt coù theå hôi lôùn hôn vuøng nhôù yeâu caàu.  Ví duï: caáp moät khoaûng troáng 18,464 bytes cho moät process yeâu caàu 18,462 bytes. – Hieän töôïng phaân maûnh noäi thöôøng xaûy ra khi boä nhôù thöïc ñöôïc chia thaønh caùc khoái kích thöôùc coá ñònh (fixed-sized block) vaø caùc process ñöôïc caáp phaùt theo ñôn vò khoái. Ví duï: cô cheá phaân trang (paging). Khoa KTMT 23 Phaânâ maûûnh noääi operating system (used) yeâu caàu keá tieáp laø 18,462 bytes !!! hole kích thöôùc 18,464 bytes caàn quaûn lyù khoaûng troáng 2 bytes !?! OS seõ caáp phaùt haún khoái 18,464 bytes cho process ⇒ dö ra 2 bytes khoâng duøng! Khoa KTMT 24 Fixed partitioning
Khi khôûi ñoäng heä thoáng, boä nhôù chính ñöôïc chia thaønh nhieàu phaàn rôøi nhau goïi laø caùc partition coù kích thöôùc baèng nhau hoaëc khaùc nhau
Process naøo coù kích thöôùc nhoû hôn hoaëc baèng kích thöôùc partition thì coù theå ñöôïc naïp vaøo partition ñoù.
Neáu chöông trình coù kích thöôùc lôùn hôn partition thì phaûi duøng cô cheá overlay.
Nhaän xeùt – Khoâng hieäu quaû do bò phaân maûnh noäi: moät chöông trình duø lôùn hay nhoû ñeàu ñöôïc caáp phaùt troïn moät partition. 5Khoa KTMT 25 Chieán löôïc placement (tt)
Partition coù kích thöôùc baèng nhau – Neáu coøn partition troáng⇒ process môùi seõ ñöôïc naïp vaøo partition ñoù – Neáu khoâng coøn partition troáng, nhöng trong ñoù coù process ñang bò blocked ⇒ swap process ñoù ra boä nhôù phuï nhöôøng choã cho process môùi.
Partition coù kích thöôùc khoâng baèng nhau: giaûi phaùp 1 – Gaùn moãi process vaøo partition nhoû nhaát phuø hôïp vôùi noù – Coù haøng ñôïi cho moãi partition – Giaûm thieåu phaân maûnh noäi – Vaán ñeà: coù theå coù moät soá haøng ñôïi troáng khoâng (vì khoâng coù process vôùi kích thöôùc töông öùng) vaø haøng ñôïi daøy ñaëc Khoa KTMT 26 Chieáán löôïïc placement (tt)
Partition coù kích thöôùc khoâng baèng nhau: giaûi phaùp 2 – Chæ coù moät haøng ñôïi chung cho moïi partition – Khi caàn naïp moät process vaøo boä nhôù chính ⇒ choïn partition nhoû nhaát coøn troáng Khoa KTMT 27 Dynamic partitioning
Soá löôïng partition khoâng coá ñònh vaø partition coù theå coù kích thöôùc khaùc nhau
Moãi process ñöôïc caáp phaùt chính xaùc dung löôïng boä nhôù caàn thieát
Gaây ra hieän töôïng phaân maûnh ngoaïi Khoa KTMT 28 Chieáán löôïïc placement
Duøng ñeå quyeát ñònh caáp phaùt khoái boä nhôù troáng naøo cho moät process
Muïc tieâu: giaûm chi phí compaction
Caùc chieán löôïc placement – Best-fit: choïn khoái nhôù troáng nhoû nhaát – First-fit: choïn khoái nhôù troáng phuø hôïp ñaàu tieân keå töø ñaàu boä nhôù – Next-fit: choïn khoái nhôù troáng phuø hôïp ñaàu tieân keå töø vò trí caáp phaùt cuoái cuøng – Worst-fit: choïn khoái nhôù troáng lôùn nhaát Khoa KTMT 29 Caáp phaùt khoâng lieân tuïc 1.Cô cheá phaân trang (paging) Boä nhôù vaät lyù
khung trang (frame). – Kích thöôùc cuûa frame laø luõy thöøa cuûa 2, töø khoaûng 512 byte ñeán 16MB.
Boä nhôù luaän lyù (logical memory) hay khoâng gian ñòa chæ luaän lyù laø taäp moïi ñòa chæ luaän lyù maø moät chöông trình baát kyø coù theå sinh ra
page. – Ví duï • MOV REG,1000 //1000 laø moät ñòa chæ luaän lyù
Baûng phaân trang (page table) ñeå aùnh xaï ñòa chæ luaän lyù thaønh ñòa chæ thöïc Khoa KTMT 30 1.Cô cheá phaân trang (tt) logical memory 1 4 3 5 0 1 2 3 page table page 0 page 2 physical memory frame number 0 1 2 3 page 14 5 page 3 page number 0 1 2 3 6Khoa KTMT 31 1.Cô cheá phaân trang (tt) A) Chuyeån ñoåi ñòa chæ trong paging – Ñòa chæ luaän lyù goàm coù:  Soá hieäu trang (Page number) p  Ñòa chæ töông ñoái trong trang (Page offset) d – Neáu kích thöôùc cuûa khoâng gian ñòa chæ luaän lyù laø 2m, vaø kích thöôùc cuûa trang laø 2n (ñôn vò laø byte hay word tuøy theo kieán truùc maùy) thì Baûng phaân trang seõ coù toång coäng 2m/2n = 2m − n muïc (entry) p d page number page offset m − n bits (ñònh vò töø 0 ÷ 2m − n − 1) n bits (ñònh vò töø 0 ÷ 2n − 1) Khoa KTMT 32 1.Cô cheá phaân trang (tt) CPU p d f d f p page table logical address physical address physical memory f 00000 f 11011 f frames A) Chuyeån ñoåi ñòa chæ trong paging Khoa KTMT 33 1.Cô cheá phaân trang (tt) Ví duï: Chuyeån ñoåi ñòa chæ nhôù trong paging Khoa KTMT 34 1.Cô cheá phaân trang (tt) Tröôùc khi vaø sau khi caáp phaùt cho Process môùi Khoa KTMT 35 B) Caøi ñaët baûng trang (Paging hardware)
Baûng phaân trang thöôøng ñöôïc löu giöõ trong boä nhôù chính – Moãi process ñöôïc heä ñieàu haønh caáp moät baûng phaân trang – Thanh ghi page-table base (PTBR) troû ñeán baûng phaân trang – Thanh ghi page-table length (PTLR) bieåu thò kích thöôùc cuûa baûng phaân trang (coù theå ñöôïc duøng trong cô cheá baûo veä boä nhôù)
Thöôøng duøng moät boä phaän cache phaàn cöùng coù toác ñoä truy xuaát vaø tìm kieám cao, goïi laø thanh ghi keát hôïp (associative register) hoaëc translation look-aside buffers (TLBs) Khoa KTMT 36 B) Caøi ñaët baûng trang (Paging hardware)
Duøng thanh ghi Page-Table Base Register (PTBR) p 7Khoa KTMT 37 Paging hardware vôùi TLB Khoa KTMT 38 C) Effective access time (EAT) • Tính thôøi gian truy xuaát hieäu duïng (effective access time, EAT)
Thôøi gian tìm kieám trong TLB (associative lookup): ε
Thôøi gian moät chu kyø truy xuaát boä nhôù: x
Hit ratio: tæ soá giöõa soá laàn chæ soá trang ñöôïc tìm thaáy (hit) trong TLB vaø soá laàn truy xuaát khôûi nguoàn töø CPU – Kí hieäu hit ratio: α
Thôøi gian caàn thieát ñeå coù ñöôïc chæ soá frame – Khi chæ soá trang coù trong TLB (hit) ε + x – Khi chæ soá trang khoâng coù trong TLB (miss) ε + x + x
Thôøi gian truy xuaát hieäu duïng EAT = (ε + x)α + (ε + 2x)(1 – α) = (2 – α)x + ε Khoa KTMT 39 C) Effective access time (EAT)
Ví duï 1: ñôn vò thôøi gian nano giaây  Associative lookup = 20  Memory access = 100  Hit ratio = 0.8  EAT = (100 + 20) × 0.8 + (200 + 20) × 0.2 = 1.2 × 100 + 20 = 140
Ví duï 2  Associative lookup = 20  Memory access = 100  Hit ratio = 0.98  EAT = (100 + 20) × 0.98 + (200 + 20) × 0.02 = 1.02 × 100 + 20 = 122 Khoa KTMT 40 D) Toå chöùc baûng trang - Phaân trang ña caáp
Caùc heä thoáng hieän ñaïi ñeàu hoã trôï khoâng gian ñòa chæ aûo raát lôùn (232 ñeán 264), ôû ñaây giaû söû laø 232 – Giaû söû kích thöôùc trang nhôù laø 4KB (= 212) ⇒ baûng phaân trang seõ coù 232/212 = 220 = 1M muïc. – Giaû söû moãi muïc goàm 4 byte thì moãi process caàn 4MB cho baûng phaân trang  VD: Phaân trang hai caáp P2 d Soá trang Ñoä dôøi trang P1 10 bit 10 bit 12 Khoa KTMT 41 D) Toå chöùc baûng trang Phaân trang ña caáp Khoa KTMT 42 D) Toå chöùc baûng trang
Baûng trang nghòch ñaûo: söû duïng cho taát caû caùc Process i 8Khoa KTMT 43 E) Baûo veä boä nhôù
Vieäc baûo veä boä nhôù ñöôïc hieän thöïc baèng caùch gaén vôùi frame caùc bit baûo veä (protection bits) ñöôïc giöõ trong baûng phaân trang. Caùc bit naøy bieåu thò caùc thuoäc tính sau – read-only, read-write, execute-only
Ngoaøi ra, coøn coù moät valid/invalid bit gaén vôùi moãi muïc trong baûng phaân trang – “valid”: cho bieát laø trang cuûa process, do ñoù laø moät trang hôïp leä. – “invalid”: cho bieát laø trang khoâng cuûa process, do ñoù laø moät trang baát hôïp leä. Khoa KTMT 44 Baûo veä baèng valid/invalid bit  Moãi trang nhôù coù kích thöôùc 2K = 2048  Process coù kích thöôùc 10,468 ⇒ phaân maûnh noäi ôû frame 9 (chöùa page 5), caùc ñòa chæ aûo > 12287 laø caùc ñòa chæ invalid.  Duøng PTLR ñeå kieåm tra truy xuaát ñeán baûng phaân trang coù naèm trong baûng hay khoâng. 00000 10468 12287 i0 i0 v9 v8 v7 v4 v3 v2 frame number valid/ invalid bit 0 1 2 3 4 5 6 7 page n 9 8 7 6 5 4 3 2 1 0 ... page 5 page 4 page 3 page 2 page 1 page 0 16383 14 bit Khoa KTMT 45 F) Chia seû caùc trang nhôù Process 1 ed 1 ed 2 ed 3 data 1 ed 1 ed 2 ed 2 data 3 Process 3 3 4 6 2 0 1 2 3 3 4 6 1 0 1 2 3 Process 2 ed 1 ed 2 ed 3 data 2 3 4 6 7 0 1 2 3 10 9 8 data 27 ed 36 5 ed 24 ed 13 data 32 data 11 0 Boä nhôù thöïc Khoa KTMT 46 2.Phaân ñoaïn (segmentation)
Nhìn laïi cô cheá phaân trang – user view (khoâng gian ñòa chæ aûo) taùch bieät vôùi khoâng gian boä nhôù thöïc. Cô cheá phaân trang thöïc hieän pheùp aùnh xaï user-view vaøo boä nhôù thöïc.
Trong thöïc teá, döôùi goùc nhìn cuûa user, moät chöông trình caáu thaønh töø nhieàu ñoaïn (segment). Moãi ñoaïn laø moät ñôn vò luaän lyù cuûa chöông trình, nhö – main program, procedure, function – local variables, global variables, common block, stack, symbol table, arrays, Khoa KTMT 47 User view cuûa moät chöông trình
Thoâng thöôøng, moät chöông trình ñöôïc bieân dòch. Trình bieân dòch seõ töï ñoäng xaây döïng caùc segment.
Ví duï, trình bieân dòch Pascal seõ taïo ra caùc segment sau: – Global variables – Procedure call stack – Procedure/function code – Local variable
Trình loader seõ gaùn moãi segment moät soá ñònh danh rieâng. procedureprocedure stackstack symbol table symbol table function sqrt function sqrt main programmain program Logical address space Khoa KTMT 48 Phaân ñoaïn
Duøng cô cheá phaân ñoaïn ñeå quaûn lyù boä nhôù coù hoã trôï user view – Khoâng gian ñòa chæ aûo laø moät taäp caùc ñoaïn, moãi ñoaïn coù teân vaø kích thöôùc rieâng. – Moät ñòa chæ luaän lyù ñöôïc ñònh vò baèng teân ñoaïn vaø ñoä dôøi (offset) beân trong ñoaïn ñoù (so saùnh vôùi phaân trang!) 9Khoa KTMT 49 Phaân ñoaïn (tt) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 Khoa KTMT 50 Caøi ñaët phaân ñoaïn
Ñòa chæ luaän lyù laø moät caëp giaù trò (segment number, offset)
Baûng phaân ñoaïn (segment table): goàm nhieàu muïc, moãi muïc chöùa – base, chöùa ñòa chæ khôûi ñaàu cuûa segment trong boä nhôù – limit, xaùc ñònh kích thöôùc cuûa segment
Segment-table base register (STBR): troû ñeán vò trí baûng phaân ñoaïn trong boä nhôù
Segment-table length register (STLR): soá löôïng segment cuûa chöông trình ⇒ Moät chæ soá segment s laø hôïp leä neáu s < STLR Khoa KTMT 51 Moät ví duï veà phaân ñoaïn procedureprocedure stackstack symbol table symbol table function sqrt function sqrt main programmain program segment 0 segment 3 segment 1 segment 2 segment 4 function sqrt symbol table main stack procedure 4 3 2 1 0 47001000 32001100 4300400 6300400 14001000 limit base segment table logical address space physical memory space 1400 2400 3200 4300 4700 5700 6300 Khoa KTMT 52 Phaàn cöùng hoã trôï phaân ñoaïn CPU < + physical memory physical e ory no trap; addressing error limit base s ds yes segment table Khoa KTMT 53 Chuyeån ñoåi ñòa chæ trong cô cheá phaân ñoaïn Ví duï Khoa KTMT 54 Chia seû caùc ñoaïn editoreditor data 1data 1 segment 0 segment 1 logical address space process P1 editoreditor data 2data 2 segment 0 segment 1 logical address space process P2 1 0 683484425 4306225286 limit base segment table process P1 1 0 900038850 4306225286 limit base segment table process P2 data 2 data 1 editor physical memory 43062 72773 68348 90003 98853 10 Khoa KTMT 55 3.Keát hôïp phaân trang vaø phaân ñoaïn
Keát hôïp phaân trang vaø phaân ñoaïn nhaèm keát hôïp caùc öu ñieåm ñoàng thôøi haïn cheá caùc khuyeát ñieåm cuûa phaân trang vaø phaân ñoaïn: – Vaán ñeà cuûa phaân ñoaïn: Neáu moät ñoaïn quaù lôùn thì coù theå khoâng naïp noù ñöôïc vaøo boä nhôù. – YÙ töôûng giaûi quyeát: paging ñoaïn, khi ñoù chæ caàn giöõ trong boä nhôù caùc page cuûa ñoaïn hieän ñang caàn. Logic Addr = Khoa KTMT 56 3.Keát hôïp phaân trang vaø phaân ñoaïn Khoa KTMT 57 3.Keát hôïp phaân trang vaø phaân ñoaïn 1Chöông 8 Boä Nhôù AÛo Khoa KTMT 2 Noäi dung trình baøy
Toång quan veà boä nhôù aûo
Caøi ñaët boä nhôù aûo : demand paging
Caøi ñaët boä nhôù aûo : Page Replacement – Caùc giaûi thuaät thay trang (Page Replacement Algorithms)
Vaán ñeà caáp phaùt Frames
Vaán ñeà Thrashing
Caøi ñaët boä boä nhôù aûo : Demand Segmentation Khoa KTMT 3 1. Toång quan boä nhôù aûo
Nhaän xeùt: khoâng phaûi taát caû caùc phaàn cuûa moät process caàn thieát phaûi ñöôïc naïp vaøo boä nhôù chính taïi cuøng moät thôøi ñieåm • Ví duï – Ñoaïn maõ ñieàu khieån caùc loãi hieám khi xaûy ra – Caùc arrays, list, tables ñöôïc caáp phaùt boä nhôù (caáp phaùt tónh) nhieàu hôn yeâu caàu thöïc söï – Moät soá tính naêng ít khi ñöôïc duøng cuûa moät chöông trình – Caû chöông trình thì cuõng coù ñoaïn code chöa caàn duøng
Boä nhôù aûo (virtual memory): Boä nhôù aûo laø moät kyõ thuaät cho pheùp xöû lyù moät tieán trình khoâng ñöôïc naïp toaøn boä vaøo boä nhôù vaät lyù Khoa KTMT 4 1. Boä nhôù aûo (tt) Öu ñieåm cuûa boä nhôù aûo – Soá löôïng process trong boä nhôù nhieàu hôn – Moät process coù theå thöïc thi ngay caû khi kích thöôùc cuûa noù lôùn hôn boä nhôù thöïc – Giaûm nheï coâng vieäc cuûa laäp trình vieân
Khoâng gian traùo ñoåi giöõa boä nhôù chính vaø boä nhôù phuï(swap space). • Ví duï: – swap partition trong Linux – file pagefile.sys trong Windows Khoa KTMT 5 2. Caøi ñaët boä nhôù aûo
Coù hai kyõ thuaät: – Phaân trang theo yeâu caàu (Demand Paging) – Phaân ñoaïn theo yeâu caàu (Segmentation Paging)
Phaàn cöùng memory management phaûi hoã trôï paging vaø/hoaëc segmentation
OS phaûi quaûn lyù söï di chuyeån cuûa trang/ñoaïn giöõa boä nhôù chính vaø boä nhôù thöù caáp
Trong chöông naøy, – Chæ quan taâm ñeán paging – Phaàn cöùng hoã trôï hieän thöïc boä nhôù aûo – Caùc giaûi thuaät cuûa heä ñieàu haønh Khoa KTMT 6 2.1.Phaân trang theo yeâu caàu demand paging • Demand paging: caùc trang cuûa quaù trình chæ ñöôïc naïp vaøo boä nhôù chính khi ñöôïc yeâu caàu.
Khi coù moät tham chieáu ñeán moät trang maø khoâng coù trong boä nhôù chính (valid bit) thì phaàn cöùng seõ gaây ra moät ngaét (goïi laø page-fault trap) kích khôûi page-fault service routine (PFSR) cuûa heä ñieàu haønh.
PFSR: 1. Chuyeån process veà traïng thaùi blocked 2. Phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp trang ñöôïc tham chieáu vaøo moät frame troáng; trong khi ñôïi I/O, moät process khaùc ñöôïc caáp CPU ñeå thöïc thi 3. Sau khi I/O hoaøn taát, ñóa gaây ra moät ngaét ñeán heä ñieàu haønh; PFSR caäp nhaät page table vaø chuyeån process veà traïng thaùi ready. 2Khoa KTMT 7 2.2. Loãi trang vaø caùc böôùc xöû lyù Khoa KTMT 8 2.3. Thay theá trang nhôù
Böôùc 2 cuûa PFSR giaû söû phaûi thay trang vì khoâng tìm ñöôïc frame troáng, PFSR ñöôïc boå sung nhö sau 1. Xaùc ñònh vò trí treân ñóa cuûa trang ñang caàn 2. Tìm moät frame troáng: a. Neáu coù frame troáng thì duøng noù b. Neáu khoâng coù frame troáng thì duøng moät giaûi thuaät thay trang ñeå choïn moät trang hy sinh (victim page) c. Ghi victim page leân ñóa; caäp nhaät page table vaø frame table töông öùng 3. Ñoïc trang ñang caàn vaøo frame troáng (ñaõ coù ñöôïc töø böôùc 2); caäp nhaät page table vaø frame table töông öùng. Khoa KTMT 9 2.3. Thay theá trang nhôù (tt) Khoa KTMT 10 2.4. Caùc thuaät toaùn thay theá trang • Hai vaán ñeà chuû yeáu:
Frame-allocation algorithm – Caáp phaùt cho process bao nhieâu frame cuûa boä nhôù thöïc?
Page-replacement algorithm – Choïn frame cuûa process seõ ñöôïc thay theá trang nhôù – Muïc tieâu: soá löôïng page-fault nhoû nhaát – Ñöôïc ñaùnh giaù baèng caùch thöïc thi giaûi thuaät ñoái vôùi moät chuoãi tham chieáu boä nhôù (memory reference string) vaø xaùc ñònh soá laàn xaûy ra page fault
Ví duï • Thöù töï tham chieáu caùc ñòa chæ nhôù, vôùi page size = 100: • 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 ⇒ caùc trang nhôù sau ñöôïc tham chieáu laàn löôït = chuoãi tham chieáu boä nhôù (trang nhôù) • 1, 4, 1, 6, 1, • 1, 1, 1, 6, 1, • 1, 1, 1, 6, 1, • 1, 1, 1, 6, 1, • 1 Khoa KTMT 11 a) Giaûi thuaät thay trang FIFO
Caùc döõ lieäu caàn bieát ban ñaàu: – Soá khung trang – Tình traïng ban ñaàu – Chuoãi tham chieáu Khoa KTMT 12 Nghòch lyù Belady 3Khoa KTMT 13 Nghòch lyù Belady Baát thöôøng (anomaly) Belady: soá page fault taêng maëc daàu quaù trình ñaõ ñöôïc caáp nhieàu frame hôn. Khoa KTMT 14 2.4 b)Giaûi thuaät thay trang OPT(optimal)
Giaûi thuaät thay trang OPT – Thay theá trang nhôù seõ ñöôïc tham chieáu treã nhaát trong töông lai
Ví duï: moät process coù 7 trang, vaø ñöôïc caáp 3 frame Khoa KTMT 15 c) Giaûi thuaät laâu nhaát chöa söû duïng Least Recently Used (LRU)
Ví duï:
Moãi trang ñöôïc ghi nhaän (trong baûng phaân trang) thôøi ñieåm ñöôïc tham chieáu ⇒ trang LRU laø trang nhôù coù thôøi ñieåm tham chieáu nhoû nhaát (OS toán chi phí tìm kieám trang nhôù LRU naøy moãi khi coù page fault)
Do vaäy, LRU caàn söï hoã trôï cuûa phaàn cöùng vaø chi phí cho vieäc tìm kieám. Ít CPU cung caáp ñuû söï hoã trôï phaàn cöùng cho giaûi thuaät LRU. Khoa KTMT 16 LRU vaøø FIFO
So saùnh caùc giaûi thuaät thay trang LRU vaø FIFO chuoãi tham chieáu trang nhôù → → →→ → → →→ → → → → Khoa KTMT 17 Giải thuật cơ hội thứ hai
Sử dụng các bit tham khảo tại những khoản thời gian đều đặn
Dùng một byte cho mỗi trang trong một bảng nằm trong bộ nhớ
Dùng một thanh ghi dịch chứa lịch sử tham khảo trong 8 lần gần nhất VD: 00110101, 00000000, 11111111
Là giải thuật thay thế FIFO, trước khi thay thế một trang xem xét bit tham khảo của nó
Đôi khi sử dụng hai bit: tham khảo và sửa đổi như một cặp (x,x): – (0,0) không được dùng mới đây và không được sửa đổi-là trang tốt nhất để thay thế. – (0,1) không được dùng mới đây nhưng được sửa đổi-không thật tốt vì trang cần được viết ra trước khi thay thế. – (1,0) được dùng mới đây nhưng không được sửa đổi-nó có thể sẽ nhanh chóng được dùng lại. – (1,1) được dùng mới đây và được sửa đổi-trang có thể sẽ nhanh chóng được dùng lại và trang sẽ cần được viết ra đĩa trước khi nó có thể được thay thế. Khoa KTMT 18 Giải thuật cơ hội thứ hai (tt) 4Khoa KTMT 19 2.5.Soá löôïng frame caáp cho process
OS phaûi quyeát ñònh caáp cho moãi process bao nhieâu frame. – Caáp ít frame ⇒ nhieàu page fault – Caáp nhieàu frame ⇒ giaûm möùc ñoä multiprogramming
Chieán löôïc caáp phaùt tónh (fixed-allocation) – Soá frame caáp cho moãi process khoâng ñoåi, ñöôïc xaùc ñònh vaøo thôøi ñieåm loading vaø coù theå tuøy thuoäc vaøo töøng öùng duïng (kích thöôùc cuûa noù,)
Chieán löôïc caáp phaùt ñoäng (variable-allocation) – Soá frame caáp cho moãi process coù theå thay ñoåi trong khi noù chaïy  Neáu tyû leä page-fault cao ⇒ caáp theâm frame  Neáu tyû leä page-fault thaáp ⇒ giaûm bôùt frame – OS phaûi maát chi phí ñeå öôùc ñònh caùc process Khoa KTMT 20 a) Chieán löôïc caáp phaùt tónh
Caáp phaùt baèng nhau: Ví duï, coù 100 frame vaø 5 process → moãi process ñöôïc 20 frame
Caáp phaùt theo tæ leä: döïa vaøo kích thöôùc process
Caáp phaùt theo ñoä öu tieân m S s pa m sS ps i ii i ii ×== = = = ∑ for allocation frames ofnumber total process of size 5964 137 127 564 137 10 127 10 64 2 1 2 ≈×= ≈×= = = = a a s s m i Ví duï: Khoa KTMT 21 3. Trì treân toaøn boä heä thoáng Thrashing
Neáu moät process khoâng coù ñuû soá frame caàn thieát thì tæ soá page faults/sec raát cao.
Thrashing: hieän töôïng caùc trang nhôù cuûa moät process bò hoaùn chuyeån vaøo/ra lieân tuïc. Khoa KTMT 22 a)Moâ hình cuïc boä (Locality)
Ñeå haïn cheá thrashing, heä ñieàu haønh phaûi cung caáp cho process caøng “ñuû” frame caøng toát. Bao nhieâu frame thì ñuû cho moät process thöïc thi hieäu quaû? Nguyeân lyù locality (locality principle) – Locality laø taäp caùc trang ñöôïc tham chieáu gaàn nhau – Moät process goàm nhieàu locality, vaø trong quaù trình thöïc thi, process seõ chuyeån töø locality naøy sang locality khaùc
Vì sao hieän töôïng thrashing xuaát hieän? Khi Σ size of locality > memory size Khoa KTMT 23 b) Giaûi phaùp taäp laøm vieäc (working set) • Ñöôïc thieát keá döïa treân nguyeân lyù locality.
Xaùc ñònh xem process thöïc söï söû duïng bao nhieâu frame.
Ñònh nghóa: – WS(t) - soá löôïng caùc tham chieáu trang nhôù cuûa process gaàn ñaây nhaát caàn ñöôïc quan saùt. –
- khoaûng thôøi gian tham chieáu • Ví duï: 2 4 5 6 9 1 3 2 6 3 9 2 1 4 thôøi ñieåm t1 ∆ = 4 chuoãi tham khaûo trang nhôù Khoa KTMT 24 b) Giaûi phaùp taäp laøm vieäc (working set)
Ñònh nghóa: working set cuûa process Pi , kyù hieäu WSi , laø taäp goàm ∆ caùc trang ñöôïc söû duïng gaàn ñaây nhaát.
Nhaän xeùt: • ∆ quaù nhoû⇒ khoâng ñuû bao phuû toaøn boä locality. • ∆ quaù lôùn ⇒ bao phuû nhieàu locality khaùc nhau. • ∆ = ∞ ⇒ bao goàm taát caû caùc trang ñöôïc söû duïng. Duøng working set cuûa moät process ñeå xaáp xæ locality cuûa noù. chuoãi tham khaûo trang Ví duï: ∆ = 10 và 5Khoa KTMT 25 b) Giaûi phaùp taäp laøm vieäc (working set) Ñònh nghóa WSSi laø kích thöôùc cuûa working set cuûa Pi : WSSi = soá löôïng caùc trang trong WSi chuoãi tham khaûo trang WSS(t1) = 5 WSS(t2) = 2 Ví duï (tieáp): ∆ = 10 và Khoa KTMT 26 b) Giaûi phaùp taäp laøm vieäc (working set) • Ñaët D = ΣWSSi = toång caùc working-set size cuûa moïi process trong heä thoáng.  Nhaän xeùt: Neáu D > m (soá frame cuûa heä thoáng) ⇒ seõ xaûy ra thrashing.
Giaûi phaùp working set: – Khi khôûi taïo moät quaù trình: cung caáp cho quaù trình soá löôïng frame thoûa maûn working-set size cuûa noù. – Neáu D > m ⇒ taïm döøng moät trong caùc process.  Caùc trang cuûa quaù trình ñöôïc chuyeån ra ñóa cöùng vaø caùc frame cuûa noù ñöôïc thu hoài. Khoa KTMT 27 b) Giaûi phaùp taäp laøm vieäc (working set)
WS loaïi tröø ñöôïc tình traïng trì treä maø vaãn ñaûm baûo möùc ñoä ña chöông
Theo veát caùc WS? => WS xaáp xæ (ñoïc theâm trong saùch) Ñoïc theâm:  Heä thoáng taäp tin  Heä thoáng nhaäp xuaát  Heä thoáng phaân taùn Khoa KTMT 28 Baøøi taääp
Bài 01: Một má