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 ખરીદવા જેવું વિચારો. લઈ જવામાં કાર્યક્ષમ છે, પણ fit કરવું મુશ્કેલ છે જો તમારી પાસે માત્ર નાના 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 છે.