[/align]یه تیپ سوال هست که چند وقتیه از بخش حافظه مجازی تو کنکورهای سال پیش مطرح می شه. اینکه یه قطعه کد می دن حاوی دو تا حلقه تو در تو و از شما می خوان بر اساس الگوریتم LRU یا FCFS تعداد نقص صفحات رو معلوم کنید. خب از این تیپ سوال من دو مو رد رو دیدم. این دو مورد اینان:
فرض کنید آرایه تعریف زیر رو داشته باشه و سایز صفحات هم ۲۰۰ باشه. هر integer هم یک کلمه بگیره:
[tex]var A:array[1..100] of array[1..100] of integer[/tex]
کد اول:
[tex]for j=1 to 100 do[/tex]
[tex]for i=1 to 100 do[/tex]
[tex]A[i][j]=0;[/tex]
خب ما ۲ تا قاب صفحه خالی داریم. جایگزینی صفحات از از روش LRU استفاده می کنیم. آرایه هم به روش سطری ذخیرهی شه. اینجا ۵۰۰۰ نقص صفحه داریم. حالا اگر جای حلقه اول و دوم عوض شه میشه اینطوری و ۵۰ نقص صفحه داریم:
کد دوم:
[tex]for i=1 to 100 do[/tex]
[tex]for j=1 to 100 do[/tex]
[tex]A[i][j]=0;[/tex]
سوال من اینه اگر آرایه ما به روش ستونی (و نه سطری) ذخیره بشه چه اتفاقی میفته و تعداد نقص صفحات در هر کدوم از حالات چه تغییری می کنه؟
بستگی داره که در چه بازه ای اعداد را بدن و اون موقع شما بگید که مثلاً با اینجور آدرس دهی فقط هر سری ۵ تا از صفحهها پشت سر هم میاد و مابقی نقص صفحه است . اگه سوالی داره بده تا روی سوال بحث کنیم ضمناً من پستهای جالبی در این مورد در همین قسمت دیدم تو پستهای قبلی دنبالش بگرد
شاید منظور از اینکه سطری پر شده این باشه که درایه های یک سطر مجاورن و حالت اینکه توی یک بلاک باشن همه رو با هم میاریم توی قاب.
اگه اینجوری باشه وقتی اولین درایه یه سطر رو میاریم بقیه درایه های اون سطر هم همراهش میان اونوقت اگه اول حلقه for i داشته باشیم اونوقت i ثابته یعنی سطر ثابته و ستون داره تغییر میکنه. یعنی اولین درایه رو که بیاریم بقیه هم اومدن و دیگه اونها حاضر هستند.
یعنی در کد دوم فقط درایه اول سطرهاست که غیبت میخوره.
البته چون سایز صفحه ۲۰۰ هست احتمالا دو سطر وارد قاب میشن.
به خاطر همین هم یکی در میون درایه های اول سطرها غیبت میخوره.
یعنی ۱۰۰/۲=۵۰
اما در حالتی که حلقه forj اول اومده باشه اومدن دو سطر از آرایه به قاب به ما کمکی نمیکنه .
فقط درایه بعدی که زیر همون درایه هست مثلا اگه j=1 و i=1 باشه چون دو سطر ۱و۲ میاد توی قاب وقتی j=1,i=2 میشه اون درایه توی قاب هست.
به خاطر همین درایهها یکی در میون غیبت میخورن و میشه ۱۰۰۰۰/۲=۵۰۰۰
به نظر من
وقتی میگه آرایه به صورت سطری پر میشه و کد به صورت
For j= 1 to 100 do
For i= 1 to 100 do
A[i][j]=0 ;
و هر قاب هم که۲۰۰ کلمه است و چون گفتیم ارایه سطری ذخیره میشه هر ۲ سطر میتونن در ۱ قاب قرار بگیرن از طرفی هم
وقتی حلقه بیرونی مقدار j رو ۱ در نظر میگیره مقدار I از ۱ تا ۱۰۰ رو میتونه داشته باشه یعنی درایه های
A[1][1],A[2][1],….. یعنی از هر سطر فقط یه درایه در هر قاب قرار می گیرن و چون ۲ تا قاب خالی داریم بعد ازقرارگرفتن ۲ درایه درهر قاب دیگه قاب خالی نخواهیم داشت پس بزای هر ۲ درایه ۱ page fault خواهیم داشت که میشه ۱۰۰*۱۰۰/۲=۵۰۰۰
و اگه جای حلقهها در کد عوض شن هر۲ سطر میتونه به طور کامل(با تمام درایهاش) در ۱ قاب قرار بگیره پس درواقع برای ۲ سطرپر ۱ page fault خواهیم داشت که میشه ۱۰۰/۲= ۵۰
خیلی ممنونم از دوستان
مشکل من با صورت یا پاسخ سوالات بالا نیست. سوال اینجاست که اگر به جای اینکه آرایه به صورت سطری پر شه، به صورت ستونی پر شه چه تغییری تو جواب حالت ۱ و ۲ اتفاق میفته؟
خوب اونوقت جواب اولی میشه ۵۰ دومی ۵۰۰۰ یعنی برعکس میشه.