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

خوارزمية تبديل الصفحات في ذاكرة الكمبيوتر الثانوية هي خوارزمية تستخدم لتبديل الصفحة التي لم يتم استخدامها مؤخرا (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 1 1 1 1 1 1 1 0 0 0 4 4 4 2 2 2 2 7 7 7 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 0 0 0 - 7 7 7 2 2 2 2 2 2 2 2 2 3 3 3 1 1 1 - -

• * * * * * * * * * * *

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

شرح المثال : عند إدخالنا لأول 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