یکی از مهم ترین سرویس هایی که یک سیستم عامل ارائه میکند، مدیریت فایل است.

یک فایل، مجموعه ای از اطلاعات وابسته تعریف شده به وسیله سازنده فایل است.

فایل ها توسط سیستم عامل بر روی دستگاه های فیزیکی نگاشته میشوند. به منظور سهولت کار با فایل ها، معمولاً آنها را در فهرست هایی سازمان میدهند.

الگوریتم های تخصیص فضای آزاد و مدیریت فضا

 

سیستم عامل در ارتباط با مدیریت فایل، مسئول فعالیت های زیر است:

– ایجاد و حذف فایل ها و فهرست ها

– مهیا کردن ابزاری برای کار با فایل ها و فهرست ها

– نگاشت فایل ها روی حافظه جانبی

– ایجاد پشتیبانی از فایل ها بر روی حافظه ماندنی

– مکانیسم حفاظتی برای کنترل دستیابی کاربران مختلف به فایل ها

 

از آنجایی که سیستم کامپیوتری باید برای استفاده، مناسب و راحت باشد، سیستم عامل یک دیدگاه منطقی یکنواخت، از ذخیره سازی اطلاعات را تدارک میبیند.

سیستم عامل ویژگی های فیزیکی دستگاه های ذخیره سازی اش را به صورت یک واحد ذخیره سازی منطقی به نام فایل تبدیل میکند؛ به عبارت دیگر، فایل ها به وسیله سیستم عامل بر روی دستگاه های فیزیکی نگاشته میشوند.

بنابراین سیستم فایل متشکل از دو قسمت مختلف است:

1- مجموعه ای از فایل های حقیقی که هر یک متشکل از اطلاعات مرتبط هستند.

2- ساختار فهرست هایی که اطلاعاتی درباره تمام فایل ها در سیستم را در بر میگیرند.

 

در این زمینه بحث های متفاوتی نظیر، ساختار فهرست، عملیات فایلی، شیوه های دستیابی به فایل، سازمان دهی ساختار فهرست و حفاظت فایل وجود دارد که از هدف این موضوع خارج می باشد.

در ادامه درمورد چگونگی مدیریت فضای آزاد دیسک بحث خواهیم کرد و الگوریتم های تخصیص فضای آزاد دیسک را بررسی میکنیم.

 

مدیریت فضای آزاد دیسک

از آنجا که میزان فضای آزاد دیسک محدود است، لازم است فضای آزاد حاصل از فایل های حذف شده، برای فایل های جدید، مجدداً استفاده گردد.

برای ثبت وضعیت فضای آزاد دیسک، سیستم نیاز به فضای آزاد دارد.

1- بردار بیتی (Bitmap)

هر بلوک آزاد به وسیله یک بیت صفر نشان داده میشود و در غیر اینصورت بیت متناظرش 1 خواهد بود.

مزیت اصلی این روش، سادگی آن است و برای پیدا کردن n بلوک آزاد متوالی بر روی دیسک، کارآمد خواهد بود.

نگهداری این بردار در حافظه اصلی برای دیسک های کوچک ممکن و مقدور است.

 

2- فهرست های پیوندی (Linked List)

در این روش تمام بلوک های آزاد دیسک به یکدیگر پیوند داده میشوند و اشاره گری به اولین بلوک آزاد، مقداردهی میگردد.

این شیوه چندان کارا نیست؛ زیرا برای پیمایش فهرست، باید هر بلوک آزاد خوانده شود، که زمان ورودی / خروجی قابل ملاحظه ای نیاز دارد.

 

3- گروه بندی (Grouping)

آدرس های n بلوک آزاد در اولین بلوک آزاد ذخیره میشود. آخرین آدرس، آدرسی است که بلوک دیگر را که حاوی آدرس بلوک های آزاد دیگر است، نشان میدهد.

اهمیت این روش این است که آدرس های تعداد زیادی از بلوک های آزاد را میتوان به سرعت پیدا کرد.

 

4- شمارشی (Counting)

آدرس اولین بلوک آزاد و تعداد n بلوک آزاد متوالی، که به دنبال اولین بلوک آزاد قرار گرفته اند را ذخیره مینماییم.

به این ترتیب هر درایو در لیست فضای آزاد، شامل آدرس یک بلوک و تعداد بلوک آزاد متوالی بعدی خواهد بود. در نتیجه لیست فضای آزاد، کوتاه تر خواهد شد.

 

 

روش های اختصاص فضای آزاد دیسک

همانطور که مشخص است، تعداد زیادی فایل بر روی دیسک ذخیره میشود؛ مسئله اصلی چگونگی اختصاص فضای آزاد به این فایل هاست، به طوری که فضای آزاد دیسک به طور مؤثری استفاده شود و فایل ها با سرعت زیاد مورد دستیابی قرار گیرند.

فرض بر این است که فایل به صورت بلوک های متوالی دیده میشود و تمام کارهای ورودی / خروجی اصلی بر حسب بلوک ها صورت می پذیرد.

 

1- تخصیص فضا به شیوه پیوسته

تخصیص پیوسته فایل، با آدرس اولین بلوک و طول فایل (بر حسب واحد بلوک) تعریف میگردد؛ در نتیجه درایه فهرست برای هر فایل، ادرس بلوک آغازین و طول فضای اختصاص یافته شده برای فایل را شامل خواهد شد.

معایت این روش، تکه تکه شدن خارجی (External Fragmentation) و چگونگی تعیین فضای مورد نیاز برای یک فایل می باشد.

 

2- تخصیص فضا به شیوه پیوندی

در این روش، هر فایل، متشکل از یک لیست پیوندی از بلوک هاست. این بلوک ها میتوانند در هر جای دیسک، پخش شده باشند.

فهرست شامل اشاره گری به بلوک های اول و آخر است.

اهمیت این روش این است که مشکل تکه تکه شدن خارجی را حذف کرده و نیازی به مشخص کردن اندازه فایل در زمان ایجاد آن نخواهد بود.

مشکل اصلی آن این است که فقط در دستیابی ترتیبی فایل ها، مؤثر عمل میکند.

عیب دیگر شیوه تخصیص پیوندی، مقدار حافظه مصرف شده برای اشاره گرها در بلوک هاست. همچنین قابلیت اطمینان کمتری دارد، زیرا اشاره گرها در داخل بلوک های سرتاسر دیسک پخش هستند.

 

3- تخصیص فضا به صورت شاخص دار

هر فایل، دارای بلوکی به نام بلوک شاخص می باشد که متشکل از تمام اشاره گرهایی است که به بلوک های آن فایل اشاره میکند. یعنی، بلوک شاخص آرایه ای از آدرس بلوک های آن فایل ایجاد میکند.

فهرست، شامل آدرس بلوک شاخص خواهد بود.

این روش امکان دسترسی مستقیم را در اختیار میدهد و ضمناً تکه تکه شدن خارجی نیز پیش نخواهد آمد.

مشکل شیوه تخصیص شاخص دار، فضای هرزی است که به ازای بلوک شاخص مصرف میشود.

 

4- تخصیص فضا به شیوه ترکیبی

این روش در سیستم BSD-UNIX استفاده میشود و به این ترتیب است که تعدادی اشاره گر در بلوک شاخص، در فهرست دستگاه ذخیره میشود. این اشاره گرها به 4 شکل مختلف ظاهر میشوند:

1- اشاره گرهایی که به بلوک های مستقیم اشاره میکنند.

2- اشاره گرهایی که به بلوک غیرمستقیم واحد (Single Indirect Block) اشاره میکنند.

3- اشاره گرهایی که به بلوک غیرمستقیم مضاعف (Double Indirect Block) اشاره میکنند.

4- فقط یک اشاره گر نوع آخر به یک بلوک غیرمستقیم سه گانه (Triple Indirect Block) اشاره میکند.

 

بلوک غیرمستقیم واحد، یک بلوک شاخص است که شامل داده ای نیست و در عوض، آدرس بلوک هایی را در خود حفظ میکند که حاوی داده ها هستند.

بلوک غیرمستقیم مضاعف یک بلوک شاخص است که آدرس غیرمستقیم واحد را در خود حفظ مینماید.

بلوک غیرمستقیم سه گانه یک بلوک شاخص است که آدرس بلوک های غیر مستقیم را در خود ذخیره میکند.