Theory
Librarian का दुःस्वप्न
कल्पना कीजिए लाखों किताबों वाली एक library, पर कोई shelf labels या एक master catalog नहीं। अगर एक नई किताब आती है, आप बस इसे किसी भी बेतरतीब ख़ाली gap में फेंक देते हैं। बाद में एक किताब खोजने के लिए, आपको building में हर एक shelf scan करनी होगी। एक computer को Disk Space Management के बिना बिल्कुल यही सामना करना पड़ता। OS को librarian के रूप में काम करना होगा, एक सख़्त record बनाए रखते हुए कि हर file कहाँ शुरू होती, ख़त्म होती है, और कौन से ख़ाली sectors नए data रखने के लिए उपलब्ध हैं।
Theory
अपना Data File करने के तीन तरीक़े
एक disk पर files store करने के लिए, OS यह manage करने के लिए तीन प्राथमिक रणनीतियों में से एक इस्तेमाल करता है कि clusters (disk space के blocks) files को कैसे allocate होते हैं:
1. Contiguous Allocation: OS मुफ़्त blocks की एक बड़ी, अटूट लंबाई खोजता है। एक car को adjacent spots की एक पंक्ति में park करने जैसा। यह पढ़ने में बेहद तेज़ है क्योंकि disk head को 'jump' करने की ज़रूरत नहीं।
2. Linked Allocation: OS files को बिखरे, non-adjacent blocks में store करता है। हर block में अगले block के address की ओर एक छोटा pointer होता है। यह एक scavenger hunt जैसा है: आप पहला टुकड़ा पाते हैं, जो आपको बताता है कि दूसरा टुकड़ा कहाँ छुपा है।
3. Indexed Allocation: OS एक समर्पित 'Index Block' (table of contents जैसा) बनाता है जो उन सारे addresses की एक सूची रखता है जहाँ file के हिस्से store हैं। आप index एक बार जाँचते हैं और फिर सीधे data blocks पर jump करते हैं।
Theory
Grocery Shopping का उपमान
Contiguous को एक box में items का एक bulk pack ख़रीदने की तरह सोचिए। ले जाने में कुशल है, पर फिट करना मुश्किल है अगर आपके पास सिर्फ़ छोटे shelf gaps हैं। Linked Allocation को एक shopping list की तरह सोचिए जहाँ हर item आपको अगले item के लिए aisle number बताता है, तो आपको पूरे store में चलना पड़ता है। Indexed Allocation पूरे store का एक perfectly organized digital map होने जैसा है; आप बस map एक बार देखते हैं और सीधे बिल्कुल उसी पर चलते हैं जो आपको चाहिए।
Think first
Fragmentation का जाल
अगर मैं Contiguous Allocation इस्तेमाल करते हुए files save और delete करता रहूँ, समय के साथ मेरी hard drive पर मुफ़्त जगह का क्या होता है? (Hint: इस्तेमाल किए blocks के बीच छोटे gaps के बारे में सोचिए)।
Show the answer
आप 'External Fragmentation' के साथ रह जाते हैं। आपके पास कुल 500MB मुफ़्त जगह हो सकती है, पर यह हज़ारों छोटे, non-adjacent 1KB gaps में टूटी है। आप एक 10MB file save नहीं कर सकते, भले आपके पास 500MB 'मुफ़्त जगह' है, क्योंकि आप इसे रखने के लिए काफ़ी बड़ा एक अकेला contiguous chunk नहीं खोज सकते।
Theory
Allocation को Visualize करना
एक छोटी 12-block disk (blocks 0 से 11) की कल्पना कीजिए जो एक 4-block file को तीन तरीक़ों से store करती है:
- Contiguous: blocks 4, 5, 6, 7, एक अटूट run।
- Linked: blocks 2 से 9 से 5 से 11, हर block अगले का address store करता है।
- Indexed: block 3 index है जो सूची (2, 9, 5, 11) रखता है; इसे एक बार पढ़िए, फिर सीधे किसी भी टुकड़े पर jump कीजिए।
एक ही file, तीन बिल्कुल अलग maps, और इस lesson का हर trade-off इन तस्वीरों से निकलता है।
Quiz
कौन सी disk space allocation method external fragmentation के लिए सबसे प्रवृत्त है?
- Linked Allocation
- Indexed Allocation
- Contiguous Allocation
- Random Allocation
Show the answer
Contiguous Allocation
Contiguous allocation को जगह की एक बड़ी, अटूट लंबाई चाहिए। जैसे अलग आकारों की files बनती और delete होती हैं, disk छोटे, अनुपयोगी holes से भर जाती है, महत्वपूर्ण external fragmentation पैदा करते हुए।
Formula
Exams के लिए Comparison सारांश
अपने exams के लिए इस 'cheat sheet' को ध्यान में रखिए:
• Contiguous: तेज़ access, पर गंभीर external fragmentation झेलता है।
• Linked: कोई external fragmentation नहीं, पर धीमा (pointers का पालन करना होगा) और pointer loss के प्रति असुरक्षित (अगर एक pointer टूटता है, file का बाक़ी खो जाता है)।
• Indexed: direct access support करता है और fragmentation से बचता है, पर Index Block ख़ुद अतिरिक्त storage जगह खपत करता है।
Theory
Disk Space Accounting
allocation से आगे, OS को एक Bit Map (या Bit Vector) इस्तेमाल करते हुए मुफ़्त जगह track करनी होगी। map पर हर bit एक disk block को दर्शाता है: एक '1' का मतलब block मुफ़्त है, और एक '0' का मतलब यह घेरा हुआ है। जब OS को जगह चाहिए, यह बस bit map में एक '1' के लिए scan करता है, इसे '0' के रूप में mark करता है, और data save करता है। यह memory में बस एक छोटी table के साथ gigabytes data manage करने का एक अत्यधिक कुशल तरीक़ा है!
Summary
Key takeaways
- Disk space management इस्तेमाल की गई बनाम मुफ़्त storage sectors track करने के लिए OS का ledger है।
- Contiguous allocation तेज़ है पर भारी fragmentation की ओर ले जाती है।
- Linked allocation blocks को chain करके fragmentation सुलझाती है पर access speed क़ुर्बान करती है।
- Indexed allocation direct address lookup के लिए एक index block इस्तेमाल करके सबसे अच्छा संतुलन देती है।
- Bit maps एक disk पर free/busy blocks track करने के लिए OS द्वारा इस्तेमाल की जाने वाली मानक, कुशल data structure हैं।