CS330 - أنظمة التشغيل
التصفح عند الطلب، استبدال الصفحات، التخبط ونموذج مجموعة العمل
الذاكرة الافتراضية هي تقنية تسمح بتنفيذ عمليات ليست بالكامل في الذاكرة.
يمكن تنفيذ الذاكرة الافتراضية عبر:
إحضار صفحة إلى الذاكرة فقط عند الحاجة إليها
مع كل إدخال في جدول الصفحات، يُربط بت صالح/غير صالح:
| صفحة | إطار | بت صالح | المعنى |
|---|---|---|---|
| ٠ | ٤ | ص | في الذاكرة |
| ١ | ٦ | ص | في الذاكرة |
| ٢ | - | غ | ليست في الذاكرة |
| ٣ | ٩ | ص | في الذاكرة |
| ٤ | - | غ | ليست في الذاكرة |
المعالج يشير لصفحة
بت غير صالح
ابحث عن الصفحة على القرص
إحضار الصفحة إلى إطار
تعيين بت صالح
متابعة التنفيذ
إدخال جدول الصفحات به بت غير صالح، مسببًا خطأ صفحة
نظام التشغيل يتحقق من جدول داخلي لمعرفة إذا كان المرجع صالحًا
ابحث عن إطار فارغ من قائمة الإطارات الحرة
اقرأ الصفحة من التخزين الاحتياطي إلى الإطار
تعيين إدخال جدول الصفحات، بت صالح = ص
إعادة تشغيل التعليمة التي سببت خطأ الصفحة
EAT = (١ - p) × ma + p × وقت_خطأ_الصفحة
حيث:
وقت الوصول للذاكرة = ٢٠٠ نانوثانية
وقت خدمة خطأ الصفحة = ٨ ملي ثانية
معدل خطأ الصفحة (p) = ٠.٠٠١
EAT = (١ - ٠.٠٠١) × ٢٠٠ + ٠.٠٠١ × ٨,٠٠٠,٠٠٠
EAT = ٠.٩٩٩ × ٢٠٠ + ٠.٠٠١ × ٨,٠٠٠,٠٠٠
EAT = ١٩٩.٨ + ٨,٠٠٠
EAT = ٨,١٩٩.٨ نانوثانية
هذا أبطأ بحوالي ٤٠ مرة من عدم وجود أخطاء صفحة!
لأداء مقبول، يجب أن يكون معدل خطأ الصفحة منخفضًا جدًا (< ٠.٠٠٠١)
حتى خطأ صفحة واحد لكل ١٠٠٠ وصول يسبب تباطؤًا كبيرًا
عندما لا يوجد إطار فارغ، يجب استبدال صفحة
نريد أقل معدل لأخطاء الصفحة
تقييم الخوارزمية بتشغيلها على سلسلة مراجع وحساب عدد أخطاء الصفحة
باستخدام ٣ إطارات
استبدال أقدم صفحة في الذاكرة
| المرجع | ٧ | ٠ | ١ | ٢ | ٠ | ٣ | ٠ | ٤ | ٢ | ٣ | ٠ | ٣ | ٢ | ١ | ٢ | ٠ | ١ | ٧ | ٠ | ١ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| إطار ٠ | ٧ | ٧ | ٧ | ٢ | ٢ | ٢ | ٢ | ٤ | ٤ | ٤ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٧ | ٧ | ٧ |
| إطار ١ | ٠ | ٠ | ٠ | ٠ | ٣ | ٣ | ٣ | ٢ | ٢ | ٢ | ٢ | ٢ | ١ | ١ | ١ | ١ | ١ | ٠ | ٠ | |
| إطار ٢ | ١ | ١ | ١ | ١ | ٠ | ٠ | ٠ | ٣ | ٣ | ٣ | ٣ | ٣ | ٢ | ٢ | ٢ | ٢ | ٢ | ١ | ||
| خطأ؟ | خ | خ | خ | خ | - | خ | خ | خ | خ | خ | خ | - | - | خ | خ | - | - | خ | خ | خ |
إجمالي أخطاء الصفحة: ١٥
استبدال الصفحة التي لن تُستخدم لأطول فترة زمنية
| المرجع | ٧ | ٠ | ١ | ٢ | ٠ | ٣ | ٠ | ٤ | ٢ | ٣ | ٠ | ٣ | ٢ | ١ | ٢ | ٠ | ١ | ٧ | ٠ | ١ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| إطار ٠ | ٧ | ٧ | ٧ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٢ | ٧ | ٧ | ٧ |
| إطار ١ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٤ | ٤ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | |
| إطار ٢ | ١ | ١ | ١ | ٣ | ٣ | ٣ | ٣ | ٣ | ٣ | ٣ | ٣ | ١ | ١ | ١ | ١ | ١ | ١ | ١ | ||
| خطأ؟ | خ | خ | خ | خ | - | خ | - | خ | - | خ | - | - | - | خ | - | - | - | خ | - | - |
إجمالي أخطاء الصفحة: ٩ (أمثل لكن يتطلب معرفة مستقبلية)
استبدال الصفحة التي لم تُستخدم لأطول وقت
| المرجع | ٧ | ٠ | ١ | ٢ | ٠ | ٣ | ٠ | ٤ | ٢ | ٣ | ٠ | ٣ | ٢ | ١ | ٢ | ٠ | ١ | ٧ | ٠ | ١ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| إطار ٠ | ٧ | ٧ | ٧ | ٢ | ٢ | ٢ | ٢ | ٤ | ٤ | ٤ | ٠ | ٠ | ٠ | ١ | ١ | ١ | ١ | ١ | ١ | ١ |
| إطار ١ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٠ | ٣ | ٣ | ٣ | ٣ | ٠ | ٠ | ٠ | ٠ | ٠ | |
| إطار ٢ | ١ | ١ | ١ | ٣ | ٣ | ٣ | ٢ | ٣ | ٣ | ٣ | ٢ | ٢ | ٢ | ٢ | ٢ | ٧ | ٧ | ٧ | ||
| خطأ؟ | خ | خ | خ | خ | - | خ | - | خ | خ | - | خ | - | خ | خ | - | خ | - | خ | - | - |
إجمالي أخطاء الصفحة: ١٢
| الخوارزمية | الوصف | أخطاء الصفحة | المزايا | العيوب |
|---|---|---|---|---|
| FIFO | استبدال أقدم صفحة | ١٥ | سهلة التنفيذ | أداء ضعيف، شذوذ بيلادي |
| الأمثل | استبدال صفحة لن تُستخدم لأطول وقت مستقبلي | ٩ | أقل أخطاء صفحة | يحتاج معرفة مستقبلية (مستحيل) |
| LRU | استبدال الأقل استخدامًا مؤخرًا | ١٢ | أداء جيد، يقارب الأمثل | مكلف للتنفيذ بدقة |
| الساعة | تقريب LRU باستخدام بت المرجع | ~١٣ | تنفيذ فعال | ليس بجودة LRU الحقيقي |
| LFU | استبدال الأقل استخدامًا من حيث التكرار | يتفاوت | يأخذ في الاعتبار تردد الاستخدام | الصفحات المستخدمة بكثرة في البداية تبقى |
لبعض خوارزميات استبدال الصفحات (مثل FIFO)، المزيد من الإطارات يمكن أن يسبب المزيد من أخطاء الصفحة!
مثال: سلسلة المراجع: ١, ٢, ٣, ٤, ١, ٢, ٥, ١, ٢, ٣, ٤, ٥
العملية تتخبط إذا كانت تقضي وقتًا في التصفح أكثر من وقت التنفيذ
درجة تعدد البرمجة →
إذا تمت الإشارة إلى موقع ذاكرة، فسيتم الإشارة إليه مرة أخرى قريبًا
مثال: عدادات الحلقات، المتغيرات المستخدمة بكثرة
إذا تمت الإشارة إلى موقع ذاكرة، فسيتم الإشارة إلى المواقع القريبة منه قريبًا
مثال: عناصر المصفوفة، الكود المتسلسل
مجموعة العمل W(t, Δ) = مجموعة الصفحات المشار إليها في آخر Δ وحدة زمنية
نافذة مجموعة العمل (Δ = ١٠)
مجموعة العمل = {١, ٢, ٣, ٥, ٦, ٧}
حجم مجموعة العمل = ٦
إذا كان إجمالي مجموعة العمل > الذاكرة المتاحة → تخبط
إذا كانت D = Σ حجم مجموعة العمل > m (إطارات متاحة)
ثم علق عملية أو أكثر
تحديد نطاق مقبول لتردد خطأ الصفحة
كل عملية تحصل على حصة متساوية
m إطار، n عملية
كل عملية تحصل m/n إطارًا
تخصيص حسب الحجم
sᵢ = حجم العملية i
S = Σsᵢ
aᵢ = (sᵢ/S) × m
بناءً على أولوية العملية
أولوية أعلى = إطارات أكثر
سلسلة المراجع: ١, ٢, ٣, ٤, ٢, ١, ٥, ٦, ٢, ١, ٢, ٣, ٧, ٦, ٣, ٢, ١, ٢, ٣, ٦
إطارات: ٣
احسب أخطاء الصفحة لخوارزميات FIFO، LRU، والأمثل
FIFO: ١٦ خطأ صفحة
LRU: ١٥ خطأ صفحة
الأمثل: ١١ خطأ صفحة
وقت الوصول للذاكرة = ١٠٠ نانوثانية
وقت خدمة خطأ الصفحة = ٢٥ ملي ثانية
معدل خطأ الصفحة = ٠.٠٠٠١
احسب EAT
EAT = (١ - ٠.٠٠٠١) × ١٠٠ + ٠.٠٠٠١ × ٢٥,٠٠٠,٠٠٠
EAT = ٩٩.٩٩ + ٢,٥٠٠
EAT = ٢,٥٩٩.٩٩ نانوثانية
سلسلة المراجع: ٢, ٣, ٢, ٤, ٥, ٣, ٦, ٣, ٤, ٥, ٣
حجم النافذة Δ = ٤
أوجد مجموعة العمل عند t = ٧
انظر إلى آخر ٤ مراجع: ٥, ٣, ٦, ٣
مجموعة العمل = {٣, ٥, ٦}
حجم مجموعة العمل = ٣
س١. أي خوارزمية استبدال صفحات تعاني من شذوذ بيلادي؟
الإجابة: FIFO
س٢. النظام يتخبط عندما:
الإجابة: العمليات تقضي وقتًا في التصفح أكثر من التنفيذ
س٣. نموذج مجموعة العمل يعتمد على:
الإجابة: المكانية المرجعية
س٤. البت صالح/غير صالح في جدول الصفحات يشير إلى:
الإجابة: ما إذا كانت الصفحة في الذاكرة (ص) أو على القرص (غ)
س٥. اذكر طريقتين لتحسين أداء النظام عند حدوث التخبط.
الإجابة:
س٦. لماذا خوارزمية استبدال الصفحة المثلى غير قابلة للتنفيذ؟
الإجابة: تتطلب معرفة مستقبلية بسلسلة المراجع، وهو أمر مستحيل معرفته مسبقًا. تُستخدم فقط كمعيار لمقارنة الخوارزميات الأخرى.
[إدراج مخطط مفصل لمعالجة خطأ الصفحة مع نظام التشغيل والذاكرة والقرص]
[إدراج مقارنة مرئية لـ FIFO و LRU والأمثل]
[إدراج منحنى استخدام المعالج مقابل درجة تعدد البرمجة]
[إدراج نافذة مجموعة العمل ومثال حساب حجم مجموعة العمل]
ملاحظة: يرجى توفير المخططات الفعلية من مواد المقرر لاستبدال هذه العناصر النائبة.