Reference String Performance of Demand Paging | Virtual Memory | Operating System

What is Reference string in Virtual Memory:

Memory reference के string को reference string कहा जाता है जो उस memory page के address को पहचानने के लिए होता है। Operating system हमें memory के एक विशेष भाग के address को reference के रूप में उपलब्ध कराता है। 

जब हम किसी memory page को लेना चाहते हैं तो उस page number का address देने की आवश्यकता नहीं होती केवल उसका reference देना होता है। 

इस reference string को system. automatic generate करता है इसे निम्न प्रकार समझ सकते हैं: माना कि निम्न प्रकार से memory address दिया गया है: 

Addresses: 45, 567, 410, 287, 1345, 45, 167, 230, 450

इस address को यदि यह page size 100 मानकर reference निकालते हैं तो वह कुछ निम्न प्रकार होगाः 

Reference: 0, 5, 4, 1, 2, 13, 0, 1, 2, 4 

FIFO (First Come First Out) Algorithm:

इसमें सभी page के लिए linked list बनाया जाता है और उनके memory के प्रवेश करने को निर्धारित किया जता है। जो page list में सबसे पहले होता है उसे पहले replace करते हैं। यह तकनीक सरल होता है परंतु इसका नुकसान यह है कि page memory में लम्बे समय तक रहता है।

इसके कार्य को समझने के लिए निम्न चित्र को देखः

FIFO in OS

उपरोक्त में missed page 10 में से 8 है इसलिए fault rate की गणना निम्न प्रकार होगीः

Fault rate: 8:10 = 80% 

Read Also - Paging And Segmentation

Optimal Page Replacement Algorithm:

इस algorithm में जिस page का उपयोग लम्बे समय से नहीं हुआ है उसे ही सबसे पहले replace करते हैं। क्योंकि लम्बे समय से उपयोग नहीं होने वाले page को पहले replace किया जाता है इसलिए आवश्यक है कि आपको पूर्ण sequence के विषय में पूर्ण जानकारी हो।

इस विधि को सबसे अच्छा मान सकते हैं क्योंकि इसका page fault rate बहुत ही कम होता है, परंतु इसे वास्तविक system पर apply करना कठिन होता है। इसके कार्य को समझने के लिए निम्न चित्र को देखें -

OPR in OS

उपरोक्त में missed page 10 में से 6 है इसलिए fault rate की गणना निम्न प्रकार होगीः

Fault rate: 6:10 = 60%

Not Recently Used (NRU) Algorithm:

इसमें प्रत्येक page के लिए एक reference bit और dirty bit निर्धारित होता है इसलिए इसमें किसी page के लिए निम्न चार स्थितियों में से एक स्थिति निर्मित हो सकती है:

0: not referenced, not dirty
1: not referenced, dirty
2: referenced, not dirty
3: referenced, dirty

इस प्रकार के तकनीक के लिए algorithm तैयार करना आसान होता है इसमें list को सुरक्षित रखा जाता है। इसमें list से समय-समय पर reference bit को हटाया जाता है।

Read Also - Demand Paging and Page Replacement in OS in Hindi

Least Recently Used (LRU) algorithm:

इसमें यह माना जाता है कि जो page तुरंत उपयोग हुआ है वह जल्दी ही फिर से उपयोग में लाया जायेगा इसलिए page को हमेशा linked list में रखा जाता है। 

इसमें अधिक उपयोग हुए page को शुरूआत में और कम उपयोग होने वाले page को अंत में रखा जाता है अर्थात् जिस page का उपयोग लम्बे समय से नहीं किया गया है उसे replace कर दिया जाता है। Page को हर memory reference के बाद update किया जाता है।

Performance of demand paging:

• Demand paging memory के लिए Effective Access Time (EAT) का उपयोग किया जाता है।
• वर्तमान में अधिकांश computer में Memory Access Time (ma) 10 से 200 nano seconds के बीच होती है।
• यदि page fault नहीं है तो उस स्थिति में Effective Access Time, Memory Access Time के बराबर होगा। EAT=ma
• यदि page fault है तो इसके लिए निम्न प्रकार समीकरण तैयार होगाः

Page fault rate 0 < p < 1.0
यहाॅ p = 0 का अर्थ है page में कोई fault नहीं है
उसी प्रकार p= 1 का अर्थ है प्रत्येक reference में fault है।
इसका पूर्ण समीकरण निम्न प्रकार तैयार होगाः
EAT=(1-p) x (ma) + p x (page fault time)

• Page fault time= (Page fault overhead + [swap page out] + swap page in + restart overhead)

Example:

• Memory access time = 1 microseconds 
• इसमें page को सशोधन के लिए प्रतिस्थापित किये जाने में लगभग आधा समय व्यतीत हो जाता है।
• page swap time = 10 msec = 10000 msec
• इस प्रकार निम्न प्रकार इसका समीकरण बनेगाः

EAT = ( 1-p) x 1 + p ( 15000) = = 1 + 15000P (in msec )

PDF Notes Operating System PDF Notes Download Download PDF