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 જે fit થાય | સૌથી ઝડપી performance |
| Best Fit | પૂરી memory scan કરે છે | સૌથી નાનો hole જે fit થાય | મોટા 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 fit થાય છે એ 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 મોટી જગ્યાઓ છોડે છે!