If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.
You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

طرق الحجز

Page history last edited by PBworks 16 years, 4 months ago

واحده من أصعب المشاكل التي تواجهنا في الملفات هي كيفية حجز مساحه للملفات ..

من ناحيتين:-

الأولى أن مساحه القرص الصلب يجب أن تكون مستغله تمام الاستغلال وبكفاءة عالية.

والناحية الأخرى هي سرعه البحث والدخول للملف المطلوب بسرعة.

وبعد هذا المقدمة المقتضبة سنتطرق الآن إلى الثلاث أنواع الرئيسية لطرق الحجز:-

الطريقة الأولى هي الحجز المتواصل الغير منقطع:-   (Contiguous Allocation)

أي أن يستولي كل ملف على مجموعه متتالية من العناوين (address) أي على مجموعه وحدات (block)

كما هو موضح بالرسم حيث إن كل لون هو عبارة عن أماكن محجوزة لملف

والتي باللون الأزرق هي أماكن فارغة غير محجوزة:-

ونلاحظ أن العناوين بالقرص(address disk) مرتبة ترتيب خطي بالقرص disk)) ,وتتميز هذه الطريقة للحجز في أن الإزاحات المتطلبة للعبور المتتابع accessing contiguous)   ) لحجز الملفات تقل وهذا متطلب من متطلبات الحجز التي ذكرناهما مسبقا وهما السرعة والمساحة.

أما الوصول إلى ملف معين فيتم ذلك بسهوله فنستخدم فقط عنوان البداية للوحدة الأولى(block address of first) لهذا الملف والطول له (أي أن هذا الملف على كم وحده يسيطر؟ )

كون الملف يحجز وحدات(blocks) متتابعة فهذا لا يمنع الدخول أو العبور العشوائي لهذه الوحدات (blocks) وهذه من حسنات طريقه الحجز المتتابع.

لكن الصعوبة في هذا الطريقة تظهر في إيجاد مساحه جديدة للملفات الجديدة فلو فرضنا إن الملف الذي سوف يُنشأ سيوضع في س من الوحدات (blocks) فان نظام التشغيل يجب إن يبحث عن س من الأماكن الفارغة المتتابعة.

التجزئة الأولى ( First-fit ), والتجزئة الأسوأ (worst-fit) ,والتجزئة الأفضل (best -fit) هي الاستراتيجيات الأكثر شيوعا المستخدمة لاختيار المكان الفارغ المناسب من بين مجموعه من الأماكن الفارغة لكن جميعها لا تناسب من ناحية الاستخدام والاستغلال الأمثل للقرص الصلب ولكن الأنسب من ناحية السرعة هنا هي التجزئة الأولى( First-fit ) وهي استراتيجيات سبق التطرق إليها.

وقبل الانتقال للنوع الثاني يجدر بنا الإشارة إلى مشكله أُخرى تواجهنا في هذه الطريقة وهي انه يجب تحديد كم من المساحة مطلوب للملف,أي انه عندما ننشئ الملف يجب أن نحدد كم من المساحة سيأخذ بالتالي كيف يمكن للمبرمج ان يعرف حجم الملف الذي سوف يُنشأ؟انه من الصعب تخمين ذلك!

هناك إصدار جديد معدّل على الطريقة الأولى ( الحجز المتواصل الغير منقطع ) وهو حل لمحدودية المكان وهو عبارة عن وحدات (blocks) تحتوي على مجموعات كبيره في وقت معين والتي ترغم أن يكون الحجز متتابع.

كما في الرسم فيما يلي:-

آليه عملها انه عندما يُكتب ملف ما تقوم بحجز عدد كبير من الوحدات (blocks) وتنقسم البيانات بالوا حدت إلى قسمين:-

(metadata) هي البيانات العلوية و ُتكتب أول ما يُنشأ الملف.

(Subsequent) وهي البيانات السفلية وتّكتب مع أول حجز متوسع للوحدات.

كما في الرسم فيما يلي:-

ملحوظة:-

لا نحتاج بيانات علوية إضافية(metadata) إلا بعد الحجز المتوسع التالي.

الطريقة الثانية من طرق الحجز هي الحجز المترابط:- Linked Allocation) )

في الحجز المرتبط كل ملف هو قائمه مرتبطة (linked list) من وحدات التخزين (Disk blocks) لكنها ليست متتابعة فعلياً في وحده التخزين وإنما بأماكن متفرقة.

وفيه يوجد دليل يحتوي على مؤشر لأول (واختياري آخر) وحدة من الملف وقيمة المؤشر الابتدائية تكون عديمة (null) وهي تكون لآخر طرف (node)في القائمة.

وتعتمد الكتابة على الملف في هذه الطريقة من الحجز على الكتابة في أول وحدة (block) فارغة بحيث تُربط هذه الوحدة الجديدة بالقائمة (linked list)فيما بعد.

ولقراءة الملف فإن المؤشر يتنقل بين الوحدات(blocks) من وحدة لأخرى .

ومما يميز هذه الطريقة هو انه لا يوجد مشكلة التجزئة الخارجية(external fragmentation ) ,فأي وحدة(block) فارغة يمكن أن تستخدم ,وكما انه يتميز عن الطريقة الأولى في انه لا يحتاج معرفه حجم معين للملف قبل إنشائه فالملف يمكن أن ينمو على قدر ما يوجد وحدات فارغة (blocks).

لكن سلبية الحجز المرتبط تكمن في انه غير فعّال للعبور(access) المباشر أو للعبور العشوائي فهو فعّال فقط بالعبور(access) التسلسلي ,فلو أردنا وحدة معينه على سبيل المثال فانه سيضطر إلى المرور على كل الملفات من البداية للنهاية وهذا مكلف للوقت فهو يتطلب قراءه وحدة التخزين ,ولا نغفل أن نذكر السلبية الأخرى إلا وهي انه لا يمكن الوثوق به و الاعتماد عليه(reliability) لان الملفات مرتبطة بعضها البعض عن طريق مؤشرات فلو حدث خطأ ما وفقدنا مؤشر(pointer) فهذا الخطأ يؤدي بنا إلى أن يكون مؤشر الملف المتضرر يؤشر على مكان فارغ أو على ملف آخر.

الجدير بالذكر أن هناك تغير طرأ على الحجز المرتبط باستخدام جدول حجز الملفات(File-Allocation Table) حيث انه في بداية كل حيّز (volume) يوضع بالجدول بدايات كل الوحدات(blocks) عن طريق رقمها(أي الوحدة) حيث ان هذه البدايات مرتبطة في الجدول بعضها البعض كالسلسلة.

كما هو موضح بهذا الرسم:-

وأخيرا الطريقة الثالثة وهي الحجز المفهرس:- (Indexed Allocation)

طريقة الحجز المفهرس حل للمشكلتين السابقتين بحيث توضع جميع المؤشرات مع بعضها البعض في وحدة واحدة (block) وتسمى الفهرس (index)

بحيث أن كل ملف له فهرس لوحدة التخزين الخاصة فيه والتي تؤشر على قطاع معين في قرص التخزين

ولقراءة القطاع رقم س من الملف, فالمؤشر عند رقم س في الفهرس ليجد القطاع المطلوب

ومما يميز هذا النوع هو انه يدعم الدخول المباشر(direct access) للوحدة المطلوبة ,بدون عناء التجزؤ الخارجي(external fragmentation) فأي مكان فارغ على القرص الصلب يمكن أن يوضع فيه ملفات يدلنا على مكانها الفهرس

ولكنها طريقة غير فعّالة إذا كان هناك ملفات قليلة.

كما هو موضح بهذا الرسم:-

وهذا عرض تقديمي قمت بتصميمه لتبسيط الطريقتين الاوائل ...



| View | Upload your own

وقد بحثت في google فوجدت سلسله من المحاضرات بالفيديو لكل المنهج قد تساعد على الفهم

على الرابط التالي:-

http://video.google.com/videoplay?docid=-8616006455995629880&q=allocation+methods&total=9&start=0&num=10&so=0&type=search&plindex=2

المراجع

http://filesystems.palconit.com/filesystems-file-allocation-methods.html

http://www.people.fas.harvard.edu/~lib215/lectures/lect_p/lect04/6_Extras/bar_fs/index3.htm

Silberschatz, Galvin, Gagne: Operating System Concepts

كتبته

سماح المطلق