Bài giảng hệ điều hành : BỘ NHỚ ẢO part 4

- Khi tìm một phần tử có khoá key trong bảng băm, hàm băm h(key) sẽ xácđịnh địa chỉ i trong khoảng từ 0 đến M-1, tìm phần tử khoá key trong bảng bămxuất phát từ địa chỉ i.Hàm băm lại lần i được biểu diễn bằng công thức sau:f(key)=(f(key)+i) %M với f(key) là hàm băm chính của bảng băm.
Nội dung trích xuất từ tài liệu:
Bài giảng hệ điều hành : BỘ NHỚ ẢO part 4 Caùc caâu hoûi1. Choïn trang naïn nhaân ? => Chieán löôïc thay theá trang2. Choïn trang naøo ñeå naïp ? => Chieán löôïc naïp 7 Chieán löôïc thay theá trang victim add FIFO: trang “giaø” nhaát Coâng baèng ?  Khoâng xeùt ñeán tính suû duïng !  victim TOÁI ÖU : trang laâu söû duïng ñeán nhaát trong töông lai AGBDCABCABCGABC Taàn suaát loãi trang thaáp nhaát  Cur page Khoâng khaû thi !  victim LRU :trang laâu nhaát chöa söû AGBDCABCABCGABC duïng ñeán trong quaù khöù Döï ñoaùn töông lai LRU = MIN ? Cur page  8 Chieán löôïc naïp Demand paging : naïp trang ñöôïc yeâu caàu Khi naøo ?  Naïp sau : taàn suaát loãi trang cao ? => pure demand paging  Naïp tröôùc : laøm sao bieát ? =>prepaging  ld page ...ld init pages ld page ld page init pages = ? 9 Thrashing = aûo töôûng suïp ñoå ! Caùc tieán trình trong heä thoáng yeâu caàu boä nhôù nhieàu hôn khaû naêng cung caáp cuûa heä thoáng ! P3 P2 P1 Real mem Taát caû tieán trình ñaàu baän roän xöû lyù loãi trang ! IO hoaït ñoäng 100 %, CPU raûnh ! Heä thoáng ngöøng treä 10 Nguyeân nhaân Thrashing1. Tieán trình khoâng taùi söû duïng boä nhôù (quaù khöù != töông lai)2. Tieán trình taùi söû duïng boä nhôù, nhöng vôùi kích thöôc lôùn hôn3. Quaù nhieàu tieán trình trong heä thoáng Chæ coù theå kieåm soaùt thrashing do nguyeân nhaân 3. 11 Giaûi quyeát thrasing vôùi moâ hình Working set Working set = taäp hôïp caùc trang tieán trình ñang truy xuaát taïi 1 thôøi ñieåm. Heä ñieàu haønh :  Chæ naïp moät tieán trình khi coù ñuû khung trang töï do cho working set cuûa noù.  Kieåm soaùt möùc ñoä ña chöông cuûa heä thoáng : Neáu toång soá khung trang yeâu caàu cuûa caùc tieán trình trong heä thoáng vöôït quaù caùc khung trang coù theå söû duïng, choïn moät tieán trình ñeå taïm döøng, ngöôïc laïi, khi toång working set beù hôn soá khung trang töï do, naïp theâm tieán trình. 12