Theory
Midnight Lab Rush
कल्पना कीजिए आपके semester project submission से पहले रात 11 बजे हैं। आप एक 18 MB data processing task चलाने के लिए LabOne server में log in करते हैं। उस बिल्कुल पल पर, server की RAM में memory map भर में फैले अलग आकारों के चार खुले slots हैं। operating system कैसे तय करता है कि आपके program को कौन सा ख़ास slot दे? ग़लत slot चुनना पूरे server को धीमा कर सकता है या भविष्य के student projects को memory से पूरी तरह बाहर बंद छोड़ सकता है।
Theory
College Parking की दुविधा
memory placement को एक college lot में बेतरतीब खुले spots के साथ एक car park करने की तरह सोचिए: एक तंग spot, एक मध्यम spot, और एक विशाल bus spot। आप पहला spot जो आप देखते हैं जो काफ़ी बड़ा है उसमें park कर सकते हैं। या, आप trucks के लिए बड़ी जगहें बचाने के लिए सबसे तंग fit खोजने के लिए पूरा lot खोज सकते हैं। वैकल्पिक रूप से, आप सबसे बड़े spot में park कर सकते हैं ताकि आपके आस-पास भरपूर जगह हो। हर विकल्प एक अलग operating system रणनीति दर्शाता है।
Theory
Memory Placement Policies
जब एक process एक contiguous allocation system में memory माँगती है, operating system एक उपलब्ध मुफ़्त block, जिसे एक hole कहते हैं, चुनने के लिए एक placement policy इस्तेमाल करता है। तीन प्राथमिक algorithms हैं First Fit, जो पहला hole allocate करता है जो काफ़ी बड़ा हो: Best Fit, जो सबसे छोटा hole allocate करता है जो काफ़ी बड़ा हो: और Worst Fit, जो सबसे बड़ा उपलब्ध hole allocate करता है। हर रणनीति बदलती है कि बची memory पूरे system में कैसे बँटती है।
At a glance
तीन मानक memory placement algorithms की तुलना।
| Policy | Search Method | Target Hole Choice | मुख्य फ़ायदा |
|---|---|---|---|
| First Fit | शुरुआत से शुरू करता है | पहला hole जो फिट हो | सबसे तेज़ performance |
| Best Fit | पूरी memory scan करता है | सबसे छोटा hole जो फिट हो | बड़े blocks बचाता है |
| Worst Fit | पूरी memory scan करता है | सबसे बड़ा उपलब्ध hole | उपयोगी बचे टुकड़े छोड़ता है |
Theory
100 MB LabOne Scenario
एक असली university exam समस्या देखते हैं। LabOne server में एक 100 MB memory map है जिसमें इस बिल्कुल क्रम में चार मुफ़्त holes हैं:
- Block 1: 15 MB
- Block 2: 30 MB
- Block 3: 20 MB
- Block 4: 35 MB
18 MB contiguous space माँगती एक student program आती है। ट्रेस करते हैं कि यह program हर policy के तहत कहाँ उतरती है।
Think first
तीनों Policies को कदम-दर-कदम ट्रेस करें
जवाब प्रकट करने से पहले दिए गए holes के क्रम का उपयोग करते हुए हल कीजिए कि 18 MB program First Fit, Best Fit, और Worst Fit के लिए कहाँ जाती है।
Show the answer
First Fit शुरू से scan करता है। Block 1 (15 MB) बहुत छोटा है, तो यह Block 2 (30 MB) चुनता है। बचा hole: 12 MB.
Best Fit सारे blocks जाँचता है। जो blocks फिट होते हैं वे 30 MB, 20 MB, और 35 MB हैं। सबसे क़रीबी मेल Block 3 (20 MB) है। बचा hole: 2 MB.
Worst Fit memory में परम सबसे बड़ा block खोजता है, जो Block 4 (35 MB) है। बचा hole: 17 MB.
Quiz
Best Fit भविष्य की allocations के लिए कभी-कभी समस्याग्रस्त क्यों है?
- यह हमेशा छोटे, अनुपयोगी holes छोड़ता है जिन्हें shards कहते हैं
- यह process parameters store करने में बहुत ज़्यादा memory लेता है
- यह दो allocations के बाद पूरी तरह partitions ख़त्म कर देता है
- यह operating system के ठीक से track करने के लिए बहुत तेज़ है
Show the answer
यह हमेशा छोटे, अनुपयोगी holes छोड़ता है जिन्हें shards कहते हैं
Best Fit वह hole चुनता है जो process request के आकार में सबसे क़रीब है। इसका मतलब बचा हुआ space जितना संभव हो उतना छोटा है। हालाँकि यह अच्छा लगता है, यह अक्सर छोटे, आंशिक memory fragments (जैसे एक 1 MB hole) छोड़ता है जो किसी असली program के लिए बहुत छोटे हैं, गंभीर external fragmentation तक ले जाते हुए।
Think first
Worst Fit का विरोधाभास
मन में भविष्यवाणी कीजिए कि एक Worst Fit allocation के बाद बची जगह का क्या होता है। कुछ systems इसे Best Fit से क्यों पसंद करते हैं?
Show the answer
Worst Fit जानबूझकर सबसे बड़ा उपलब्ध hole चुनता है। क्योंकि यह एक विशाल block से लेता है, बचा हुआ space आम तौर पर काफ़ी बड़ा होता है और आगामी processes के लिए अत्यधिक उपयोगी रहता है। उदाहरण के लिए, एक 35 MB hole में 18 MB allocate करना एक स्वस्थ 17 MB hole छोड़ता है, Best Fit के उलट जिसने एक छोटा 2 MB hole छोड़ा।
Watch out
Best Fit Efficiency का जाल
इस जाल में मत फँसिए कि Best Fit हमेशा सबसे अच्छा विकल्प है बस इसके नाम की वजह से। university exams में, students अक्सर नाम को performance समझ लेते हैं। Best Fit को हर एक बार मुफ़्त holes की पूरी सूची scan करनी होती है जब तक सूची sorted न हो, जो काफ़ी processing overhead लाता है। इसके अलावा, यह छोटे, बेकार memory fragments पैदा करता है जो समय के साथ system performance घटाते हैं।
Theory
असली दुनिया की Memory Allocation
हालाँकि आधुनिक operating systems उन्नत paging frameworks इस्तेमाल करते हैं, ये placement concepts बुनियादी हैं। आप इन बिल्कुल placement concepts को फिर इस्तेमाल करेंगे जब इस subject का Unit 3 disk पर file blocks रखता है, और फिर BCA205 में जब databases storage pages manage करते हैं। इन व्यापारों को जानना आपको memory efficient application code लिखने में मदद करता है।
Summary
Key takeaways
- First Fit पहला उपलब्ध hole चुनता है जो काफ़ी बड़ा हो, इसे बेहद तेज़ बनाते हुए।
- Best Fit सबसे छोटा hole चुनता है जो request संतुष्ट करे, तत्काल बर्बाद जगह न्यूनतम करते हुए।
- Worst Fit सबसे बड़ा उपलब्ध hole allocate करता है, बची जगह को बड़ी और उपयोगी रखते हुए।
- Best Fit और Worst Fit दोनों को पूरी memory map scan करनी होती है, overhead बढ़ाते हुए।
- Memory hook: First Fit तेज़ है, Best Fit छोटे fragments छोड़ता है, Worst Fit बड़ी जगहें छोड़ता है!