خوارزميات جدولة الأقراص

خوارزميات جدولة الأقراص

Disk Scheduling algorithms
من اهم مسئوليات نظم التشغيل استخدام الاجهزة بكفاءه وفي حالة القرص الصلب لابد من الاهتمام بمعايير منها تسريع وقت الوصول وعرض القرص ايضا
يندرج تحت هذا المعيار مفهومين :(acess time)وقت الوصول-
وهو الوقت الازم لتحريك راس القرص الى المكان المطلوب(seek time) المفهوم الاول: وقت الطلب
وهوالوقت المنتظرلتدوير القرص لوضع الراس عليه(rotational latency)المفهوم الثاني: تاخير التدويير
وهو العدد الاجمالي للبايت المنقولة مقسومة على الوقت من طلب الخدمة وحتى الانتهاء منها : (disk bandwidth )عرض القرص-
وفهمنا لهذه المعايير يساعدنا في تقييم اداء خوارزميات جدوله القرص ومعرفة الافضل
FCFS (First Come , First Served)
القادم أولاً يخدم أولاً

أبسط شكل من أشكال خوارزميات جدولة الأقراص ، فهو على اسمه ، القادم أولاً يخدم أولاً ويبدو لنا أنه عادل لأنه الخدمة تتم على حسب وقت الوصول ، لكن هذا قد يستهلك الكثير من الوقت مما يؤدي إلى عدم سرعة تقديم الخدمات .
فمثلاً لو كان لدي الطابور التالي المحتوي على هذه الطلبات :
98 , 183 , 37 , 122 , 14 , 124 , 65, 67
والرأس متوقف عند 53
فيكون ال
queue = 98 , 183 , 37 , 122 , 14 , 124 , 65, 67
head starts at 53
نلاحظ التنفيذ سيكون بالترتيب كما في الصورة

فسيتحرك الرأس من 53 إلى 98 إلى 183 ثم يعود إلى 37 ثم 122 ثم يعود إلى 14 ثم 124 ثم يعود إلى 65 وأخيراً إلى 67
لكي نحسب مجمل تحرك الرأس نقوم بجمع القيم المطلقة للفرق بين مكان وجود الرأس والمكان الذاهب إليه كما يلي :
tota head movment = | 53 - 98 | |98 - 183 | |183 - 37 | |37 - 122 | |122 - 14 | | 14 - 124 | | 124 - 65 | | 65 - 67 |
= 45 85 146 85 108 110 59 2
= 640 cylinders
wild jumpالفرق في الانتقال من 122 إلى 14 ثم العودة إلى 124 مرة أخرى يوضح المشكلة وهذا ما يعرف بـ
فلو كان تنفيذ الذهاب إلى 14 و 37 ينفذ تباعاً قبل الذهاب إلى 122 و 124 لقلّ تحرك الرأس ولزادت الفعالية
SSTF (Shortest Seek Time First)

من المنطقي خدمة جميع الطلبات القريبة من الرأس قبل توجه الرأس بعيداً لخدمة الطلبات الأخرى .
هذا الافتراض هو أساس هذه الخوارزمية والذي يحل المشكلة الظاهرة في الخوارزمية السابقة
فهذه الخوارزمية تقوم باختيار الطلب صاحب الفرق الأقل من مكان الرأس الحالي .
الصورة التالية توضح هذه الخوارزمية

ففي مثالنا ، الطلب الأقرب لمكان الرأس الحالي الذي هو 53 ، يكون 65
لأن
| 53 - 65 | = 12
بعد ذلك تكون النقطة الأقرب هي 67
يليها 37
فــ 37 أقرب من 98 لأن
|67 - 37 | = 30
|67 - 98 | = 31
ثم نكمل فيكون الترتيب
14 , 98 , 122 , 124 , 183
نقوم بالحساب فنجد
tota head movment = | 53 - 65 | |65 - 67 | |67 - 37 | |37 - 14 | |14 - 98 | | 98 - 122 | | 122 - 124 | | 124 - 183 |
= 12 2 30 23 84 24 2 59
= 236 cylinders
وهذا الرقم يمثل اثلث تقريباً بالنسبة للخوارزمية الأولى
ومع أن
SSTF
أفضل من FCFS
إلا أنه ليس الأفضل ،لأنه لا يقوم باختيار الأسطوانة التي ستكون أقرب إذا أخذت في عين الاعتبار جمع الأعداد المتواجدة لدي ، ففي الصورة التالية نجد طريقة أخرى :


المثال السابق أن نتجه من 53 الى 37 مع أن 37 ليست الأقرب للـ 53 و لكنه الأقرب إذا أخذت في عين الاعتبار الاختصار في الطريق الذي سوف ينتجه اختياري لهذا الرقم ، فعند اتجاه الرأس من 53 الى 37 الى 14 ، قبل خدمتي للـ65و67و98و122و124 فإن هذا الاتجاه سيعطيني مجموع تحرك الرأس=208 ، و سنلاحظ بأنها وفرت لي 28 حركة و هذا أفضل ..
[url=http://os2h.pbwiki.com/SCAN Sceduling]SCAN Sceduling[/url]
[url=http://os2h.pbwiki.com/C-SCAN Scheduling]C-SCAN Scheduling[/url]
LOOK & C-LOOK
كما شرح في
SCSN & C-SCAN
كلاهما يحركان ذراع القرص عبر العرض الكامل للقرص
لكن عملياً ، ولا خوارزمية تتنفذ بهذه الطريقة
ثم تعكس الاتجاه حالاً
بدون الذهاب طوال الطريق إلى نهاية القرص


نقوم بالحساب فنجد
tota head movment = | 53 - 65 | |65 - 67 | |67 - 98 | | 98 - 122 | |122 - 124 | | 124 - 183 | | 183 - 199 | | 199 - 0 | | 0 - 14 | | 0 - 37 |
= 12 2 31 24 2 59 16 199 14 37
= 396 cylinders

نقوم بالحساب فنجد
tota head movment = | 53 - 65 | |65 - 67 | |67 - 98 | | 98 - 122 | |122 - 124 | | 124 - 183 | | 183 - 14 | | 14 - 37 |
= 12 2 31 24 2 59 169 23
= 322 cylinders
إصدارات
SCSN & C-SCAN
اللتي تتبع هذا النط تسمى
LOOK & C-LOOK
lookلأنهم يقومون ب
رؤية الطلب قبل الاستمرار في التحرك إلى الاتجاه المعطى
************
هذا رابط لموقع ، يقوم برسم اتجاه الحركة مع الحسابات
http://gaia.ecs.csus.edu/~zhangd/oscal/DiskApplet.html