الرئيسيةعريقبحث

خوارزم تبديل الصفحات


خوارزم تبديل الصفحات في ذاكرة الكمبيوتر الثانوية هو خوارزم يستخدم لتبديل الصفحة التي لم يتم استخدامها مؤخرا (Least recently used LRU)

وهذه الطريقة تعتمد على تبديل الصفحة التي لم يتم استخدامها لأطول وقت (أقدم صفحة في الذاكرة) هي التي سوف يتم استبدالها بالصفحات الجديدة وذلك لان الصفحات التي تم استخدامها حديثا هي صاحبة الاحتمال الأكبر في الاستعمال التالي القريب بناء على نظرية اسمها (locality) وهي تعني أن البيانات الأقرب من ناحية الزمان والمكان هي ذات الحظ الأوفر بالاستخدام القادم لذلك يتم إبقاءها وهذه الطريقة هي اقرب الطرق إلى النظام المتكامل الذي يمكن أن يعلم بالمستقبل والذي لا يمكن أن يتم تحقيقه إلا إذا علمنا بالمستقبل ولكن من سيئات هذا النظام انه يحتاج إلى معلومات عن الوقت أي يتم الفحص والبحث في كل البيانات عن كل عملية إدخال لبيانات جديدة .

مثال: تم إدخال البيانات بالترتيب ألزماني التالي من اليسار إلى اليمين في ذاكرة تحوي فقط 3 صفحات 70120304230321201701 فيتم تمثيلها بطريقة الصفحة التي لم يتم استخدامها مؤخرا كالتالي

فيتم تمثيلها بطريقة الصفحة التي لم يتم استخدامها مؤخرا كالتالي 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 11111110004442222777 0000033333300000000- 777222222222333111--

  • * * * * * * * * * * *
    تعني أننا احتجنا إلى صفحة جديدة أي تم عمل الاستبدال

شرح المثال : عند إدخالنا لأول 3 صفحات (7 0 1) كان لكل منها مكان فارغ ولم تتكرر الصفحات لذلك لم نحتاج للتبديل ولكن عند إدخال 2 وجب علينا استبدالها بـ2 لان 7 هي التي لها أطول وقت في الذاكرة دون استخدام وعندما احتجنا ال0 كان أصلا موجود بالذاكرة لذلك لا يتم الاستبدال ولكن يتم تحديث زمن ال0 ليكون أحدث واحد تم استخدامه عند ال3 كانت أقدم صفحة دون استخدام هي ال1 وبذلك يتم استبدال ال1 ب ال3 ويتم الاستمرار على هذا النمط .

وهذا كود يبين كيفيت عمل الطريقة وهو مكتوب بلغة تيربوسي TC

# define n_fram 3 # include<stdio.h> # include<conio.h> main() { int fram[n_fram],i,j,c[n_fram],page,done,max; for(i=0;i<n_fram;i++) { do { printf("\npls enter new page between 0-9 :\n"); scanf("%d",&page); }while(page>9 || page<0); fram[i]=page; clrscr(); for(j=0;j<=i;j++) printf("\n --------------\n||\t%d\t||\n --------------",fram[j]); c[i]=n_fram-i; } while(1) { done=max=0; do { printf("\npls enter new page between 0-9 :\n"); scanf("%d",&page); }while(page>9 || page<0); for(i=0;i<n_fram;i++) { if(fram[i]==page) { done=1; c[i]=0; } if(c[i]>max) max=c[i]; } if(done==0) for(i=0;i<n_fram;i++) if(max==c[i]) { fram[i]=page; c[i]=0; } clrscr(); for(i=0;i<n_fram;i++) printf("\n --------------\n||\t%d\t||\n --------------",fram[i]); for(i=0;i<n_fram;i++) c[i]++; } getch(); getch(); }

مرجع التقرير Understanding Operating System,4th edition, Flynn and McHoes

شرح المثال : عند إدخالنا لأول 3 صفحات (7 0 1) كان لكل منها مكان فارغ ولم تتكرر الصفحات لذلك لم نحتاج للتبديل ولكن عند إدخال 2 وجب علينا استبدالها بـ2 لان 7 هي التي لها أطول وقت في الذاكرة دون استخدام وعندما احتجنا ال0 كان أصلا موجود بالذاكرة لذلك لا يتم الاستبدال ولكن يتم تحديث زمن ال0 ليكون أحدث واحد تم استخدامه عند ال3 كانت أقدم صفحة دون استخدام هي ال1 وبذلك يتم استبدال ال1 ب ال3 ويتم الاستمرار على هذا النمط .

وهذا كود يبين كيفيت عمل الطريقة وهو مكتوب بلغة تيربوسي TC

# define n_fram 3 # include<stdio.h> # include<conio.h> main() { int fram[n_fram],i,j,c[n_fram],page,done,max; for(i=0;i<n_fram;i++) { do { printf("\npls enter new page between 0-9 :\n"); scanf("%d",&page); }while(page>9 || page<0); fram[i]=page; clrscr(); for(j=0;j<=i;j++) printf("\n --------------\n||\t%d\t||\n --------------",fram[j]); c[i]=n_fram-i; } while(1) { done=max=0; do { printf("\npls enter new page between 0-9 :\n"); scanf("%d",&page); }while(page>9 || page<0); for(i=0;i<n_fram;i++) { if(fram[i]==page) { done=1; c[i]=0; } if(c[i]>max) max=c[i]; } if(done==0) for(i=0;i<n_fram;i++) if(max==c[i]) { fram[i]=page; c[i]=0; } clrscr(); for(i=0;i<n_fram;i++) printf("\n --------------\n||\t%d\t||\n --------------",fram[i]); for(i=0;i<n_fram;i++) c[i]++; } getch(); getch(); }

مرجع التقرير

Understanding Operating System,4th edition, Flynn and McHoes

موسوعات ذات صلة :