Contiguous allocation: fit policies और coalescing
लक्ष्य और model
Requests की sequence पर first/best/worst fit trace करें; splitting, coalescing और compaction अलग करें; alignment overhead निकालें। पूर्वज्ञान: paging पाठ का internal/external fragmentation। यहाँ variable-sized contiguous allocations हैं। Request एक hole में पूरी fit होगी; paging या कई holes में splitting नहीं। शुरुआती examples arbitrary units में हैं, headers/alignment zero, request hole का low-address हिस्सा लेती है और remainder free रहता है। Initial holes के बीच allocated regions हैं, इसलिए उनके sizes सीधे merge नहीं कर सकते।
1. खाली जगह चुनने के तीन नियम
अलग लंबाई की गाड़ियों के लिए parking gaps सोचें। First fit stated order में पहली पर्याप्त जगह लेता है। Best fit सबसे छोटी पर्याप्त जगह, worst fit सबसे बड़ी पर्याप्त जगह लेता है। ये placement rules हैं, भविष्य की पूरी sequence fit होने की guarantees नहीं। “Best” local gap choice है, universal optimality नहीं।
यहाँ free-list scan increasing address order में है। Equal-size tie में lowest-address hole। 350-unit hole से 160 देने पर 190 free बचते हैं। यह free external space है, नई allocation के अंदर internal waste नहीं; model client को ठीक 160 देता है।
2. हर policy समान initial state से चलाएँ
Address order में H1=120,H2=350,H3=180,H4=420। Labels original hole location बताते हैं; remainder उसी label/order में रहता है। Requests 160,300,100 हैं। हर policy शुरू से चलाएँ; first fit के बचे state पर best fit न चलाएँ।
First fit:
- 160: H1 छोटा, H2 split। Holes=(120,190,180,420)।
- 300: scan में H4 fit। Holes=(120,190,180,120)।
- 100: पहली sufficient H1। Final=(20,190,180,120)।
Total free=510; largest=190। आगे unsplittable 400 request fail, भले total पर्याप्त है।
Best fit:
- 160: H3=180 चुना, 20 बचा। Holes=(120,350,20,420)।
- 300: H2=350 चुना, 50 बचा। Holes=(120,50,20,420)।
- 100: H1=120 चुना, 20 बचा। Final=(20,50,20,420)।
Total फिर 510; largest=420। आगे 400 success, H4 में 20 बचेगा। यह इसी sequence की बात है, best fit हमेशा first fit से बेहतर होने का प्रमाण नहीं।
Worst fit:
- 160: H4=420 चुना, 260 बचा। Holes=(120,350,180,260)।
- 300: H2=350 चुना, 50 बचा। Holes=(120,50,180,260)।
- 100: H4=260 चुना, 160 बचा। Final=(120,50,180,160)।
Total=510; largest=180। आगे 400 fail। हर allocation के बाद largest फिर खोजें; शुरू की largest location हर बार नहीं चुनी जाएगी।
3. Conservation से स्वतंत्र जाँच
Initial free=120+350+180+420=1070। Requests=160+300+100=560। Zero overhead और no releases में हर policy का final free=1070−560=510 होना चाहिए। समान total के साथ largest holes अलग हो सकते हैं। Allocation, release या stated metadata cost के बिना total बदलना गलत है।
छोटे remainders चुपचाप न हटाएँ। Real allocators में minimum block size और metadata हो सकते हैं, पर model में बताने होंगे। Remainder client को अतिरिक्त allocated space के रूप में दे दिया जाए तो वह free hole की बजाय internal waste हो सकता है।
4. Coalescing को physical adjacency चाहिए
Free regions [0,100),[150,250), बीच का [100,150) allocated है। अभी free regions adjacent नहीं, merge नहीं होंगे। Middle allocation free हो तो [0,100),[100,150),[150,250) मिलकर length 250 का [0,250) बनते हैं। Half-open intervals boundary share करते हैं, allocated byte नहीं।
Coalescing adjacent free blocks merge करता है, live allocations नहीं हिलाता। Compaction live allocations move करके अलग free space को एक बड़े region में लाता है। इसके लिए references relocate/update करने का तरीका और copying cost चाहिए; arbitrary raw pointers पर अपने-आप सुरक्षित नहीं। दोनों total free capacity नहीं बढ़ाते। Layout बदलकर बड़ा contiguous hole बन सकता है जबकि total वही रहता है।
5. Metadata और alignment स्पष्ट गिनें
अब bytes और अलग model लें: हर allocation में payload से पहले 8-byte header है; total block size को 16 के multiple तक round करते हैं। 100-byte payload को पहले 108, फिर ceiling(108/16)×16=112 bytes चाहिए। Payload 100, header 8, alignment slack 4। Non-payload total 12, पर पूरा padding नहीं। इस rule में 108-byte hole पर्याप्त नहीं।
Next fit पिछली search के पास से scan जारी करता है; lowest address से फिर शुरू होने वाले first fit जैसा नहीं। Numeric trace में cursor behavior स्पष्ट चाहिए। केवल first fit पूछा हो तो next-fit cursor न गढ़ें।
परीक्षा checklist
Hole order, ties, overhead, splitting/coalescing assumptions लिखें। Successful request ठीक एक sufficient hole से घटाएँ और remainder की location रखें। Failure में largest hole और total दोनों देखें। Free-list के logical पड़ोसी और physically adjacent ranges अलग हैं।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
AL01. Address-order holes 120,350,180,420। First fit क्रम से 160,300,100 देता है; splitting, zero overhead, no coalescing। Largest final hole?
A. 120 B. 180 C. 190 D. 420
उत्तर: C
A: 120 final H4 है, largest नहीं।
B: H3=180 पर H2=190 है।
C: Final 20,190,180,120; largest=190।
D: H4 से 300 घट चुका है।
AL02. अलग से initial holes 120,350,180,420। Best fit 160,300,100 allocate करता है; zero overhead, splitting, no coalescing। आगे contiguous 400 fit होगा?
A. नहीं, क्योंकि total 510 ही है B. हाँ, बचे 420-unit hole में C. हाँ, छोटे holes जोड़कर D. नहीं, best fit split नहीं करता
उत्तर: B
A: 510 total, 400 से अधिक; individual hole देखना है।
B: पहले 180,350,120 use होते हैं; 420 बचा है।
C: अलग holes में request split नहीं हो सकती।
D: Splitting स्पष्ट allowed है।
AL03. Address-order holes 120,350,180,420 में worst fit 160,300,100 देता है; splitting और zero overhead। Original address order में final list?
A. 20,190,180,120 B. 20,50,20,420 C. 120,50,180,160 D. 120,350,20,120
उत्तर: C
A: यह first fit का result है।
B: यह best fit है।
C: 160 के लिए H4, 300 के लिए H2, 100 के लिए फिर H4।
D: Largest-hole rule और तीनों subtractions सही नहीं।
AL04. Free [0,100),[150,250) हैं। Allocated [100,150) free होता है और adjacent blocks coalesce होते हैं। Result?
A. [0,200) B. [0,250) C. [100,250) D. Merge संभव नहीं
उत्तर: B
A: Newly freed 50 units पूर्ण span से छूटे हैं।
B: तीनों adjacent intervals मिलकर [0,250)।
C: पहला original free interval छूट गया।
D: Middle free होने पर physical adjacency है।
AL05. 350-unit hole split करके client को ठीक 160 दिए, headers/alignment zero। 190-unit remainder क्या है?
A. 160-unit allocation के अंदर padding B. आगे allocation के लिए free hole C. अपने-आप client को allocated D. Untrackable lost memory
उत्तर: B
A: यह exact allocation के बाहर है।
B: 350−160=190 free-space structure में रहता है।
C: Client को ठीक 160 दिए हैं।
D: Allocator remainder free list में रखता है।
AL06. Payload 100 bytes, header 8 bytes। Total size को 16 के multiple तक ऊपर round करते हैं। Block size?
A. 100 B. 108 C. 112 D. 128
उत्तर: C
A: Header और rounding छूटे।
B: 108 में header है पर 16 का multiple नहीं।
C: ceil((100+8)/16)×16=112।
D: 112 पर्याप्त multiple है; 128 अतिरिक्त rounding है।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन