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

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

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

تُعد مشكلة استبدال الصفحة مشكلة نموذجية على الإنترنت من منظور التحليل التنافسي بمعنى أن الخوارزمية الحتمية المثلى معروفة.

تاريخ

كانت خوارزميات استبدال الصفحات موضوعًا ساخنًا للبحث والنقاش في الستينيات والسبعينيات. وانتهى ذلك في الغالب بتطوير تقريبات LRU (الأقل استخدامًا مؤخرًا) المتطورة وخوارزميات مجموعة العمل . ومنذ ذلك الحين، تم دحض بعض الافتراضات الأساسية التي بُنيت عليها خوارزميات استبدال الصفحات التقليدية، مما أدى إلى انتعاش البحث. وعلى وجه الخصوص، أثرت الاتجاهات التالية في سلوك الأجهزة والبرامج على مستوى المستخدم على أداء خوارزميات استبدال الصفحات:

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

Requirements for page replacement algorithms have changed due to differences in operating system kernel architectures. In particular, most modern OS kernels have unified virtual memory and file system caches, requiring the page replacement algorithm to select a page from among the pages of both user program virtual address spaces and cached files. The latter pages have specific properties. For example, they can be locked, or can have write ordering requirements imposed by journaling. Moreover, as the goal of page replacement is to minimize total time waiting for memory, it has to take into account memory requirements imposed by other kernel sub-systems that allocate memory. As a result, page replacement in modern kernels (Linux, FreeBSD, and Solaris) tends to work at the level of a general purpose kernel memory allocator, rather than at the higher level of a virtual memory subsystem.

Local vs. global replacement

Replacement algorithms can be local or global.

When a process incurs a page fault, a local page replacement algorithm selects for replacement some page that belongs to that same process (or a group of processes sharing a memory partition). A global replacement algorithm is free to select any page in memory.

Local page replacement assumes some form of memory partitioning that determines how many pages are to be assigned to a given process or a group of processes. Most popular forms of partitioning are fixed partitioning and balanced set algorithms based on the working set model. The advantage of local page replacement is its scalability: each process can handle its page faults independently, leading to more consistent performance for that process. However global page replacement is more efficient on an overall system basis.^[1]

Detecting which pages are referenced and modified

Modern general purpose computers and some embedded processors have support for virtual memory. In most of them, each process has its own virtual address space. A page table maps a subset of the process virtual addresses to physical addresses. In addition, in most architectures the page table holds an "access" bit and a "dirty" bit for each page in the page table. The CPU sets the access bit when the process reads or writes memory in that page. The CPU sets the dirty bit when the process writes memory in that page. The operating system can modify the access and dirty bits. The operating system can detect accesses to memory and files through the following means:

يتم ذلك عن طريق مسح بت الوصول في الصفحات الموجودة في جدول صفحات العملية. بعد فترة، يقوم نظام التشغيل بفحص جدول الصفحات بحثًا عن الصفحات التي تم تعيين بت الوصول إليها بواسطة وحدة المعالجة المركزية. هذه العملية سريعة لأن بت الوصول يتم تعيينه تلقائيًا بواسطة وحدة المعالجة المركزية، ولكنها غير دقيقة لأن نظام التشغيل لا يتلقى إشعارًا فوريًا بالوصول، كما أنه لا يملك معلومات حول ترتيب وصول العملية إلى هذه الصفحات.
عن طريق إزالة الصفحات من جدول صفحات العملية دون إزالتها بالضرورة من الذاكرة الفعلية. يتم اكتشاف الوصول التالي إلى تلك الصفحة فورًا لأنه يتسبب في خطأ صفحة . هذه العملية بطيئة لأن خطأ الصفحة يتضمن تبديل سياق إلى نظام التشغيل، وبحثًا برمجيًا عن العنوان الفعلي المقابل ، وتعديل جدول الصفحات، ثم تبديل سياق عائد إلى العملية، وهي دقيقة لأن الوصول يُكتشف فور حدوثه.
مباشرة عندما يقوم النظام بإجراء استدعاءات النظام التي قد تصل إلى ذاكرة التخزين المؤقت للصفحة مثل readذلك writeفي POSIX .

التنظيف المسبق

معظم خوارزميات الاستبدال تُعيد ببساطة الصفحة المستهدفة كنتيجة. هذا يعني أنه إذا كانت الصفحة المستهدفة غير مُنظَّمة (أي تحتوي على بيانات يجب كتابتها إلى وحدة التخزين الثابتة قبل استعادة الصفحة)، فيجب بدء عملية إدخال/إخراج لإرسال تلك الصفحة إلى وحدة التخزين الثابتة (لتنظيفها ) . في بدايات الذاكرة الافتراضية، لم يكن الوقت المُستغرق في التنظيف مُشكلة كبيرة، لأن الذاكرة الافتراضية طُبِّقت في البداية على أنظمة ذات قنوات اتصال ثنائية الاتجاه مع وحدة التخزين الثابتة، وكان التنظيف يتداخل عادةً مع عملية الترحيل. أما الأجهزة الحديثة، فلا تدعم عمليات النقل ثنائية الاتجاه، مما يجعل تنظيف الصفحات المستهدفة مُشكلة.

لمعالجة هذه المشكلة، تُطبَّق سياسات تنظيف مسبق متنوعة . التنظيف المسبق هو الآلية التي تبدأ عمليات الإدخال/الإخراج على الصفحات المتسخة التي يُحتمل استبدالها قريبًا. الفكرة هي أنه بحلول الوقت الذي تُختار فيه الصفحة المنظفة مسبقًا للاستبدال، تكون عمليات الإدخال/الإخراج قد اكتملت، وتصبح الصفحة نظيفة. يفترض التنظيف المسبق إمكانية تحديد الصفحات التي سيتم استبدالها لاحقًا . قد يؤدي التنظيف المسبق المتسرع إلى إهدار عرض نطاق الإدخال/الإخراج من خلال كتابة صفحات تُصبح متسخة مرة أخرى قبل اختيارها للاستبدال.

مشكلة الترحيل (h,k)

تُعدّ مسألة الترحيل (h,k) تعميمًا لنموذج مسألة الترحيل: ليكن h و k عددين صحيحين موجبين بحيث $h\leq k$ نقيس أداء خوارزمية ذات ذاكرة تخزين مؤقتة بحجم $h\leq k$ مقارنةً بخوارزمية استبدال الصفحات المثلى نظرياً . إذا $h<k$ نقدم خوارزمية استبدال الصفحات المثلى باستخدام موارد أقل بكثير.

تُعد مشكلة الترحيل (h,k) طريقة لقياس أداء الخوارزمية عبر الإنترنت من خلال مقارنتها بأداء الخوارزمية المثلى، وتحديدًا، تحديد حجم ذاكرة التخزين المؤقت للخوارزمية عبر الإنترنت والخوارزمية المثلى بشكل منفصل.

خوارزميات وضع العلامات

تُعدّ خوارزميات الوسم فئة عامة من خوارزميات الترحيل. لكل صفحة، نُخصّص لها بتًا يُسمى علامتها. في البداية، نُعيّن جميع الصفحات على أنها غير مُعلّمة. خلال مرحلة (فترة تشغيل أو سلسلة طلبات) من طلبات الصفحات، نُعلّم الصفحة عند طلبها لأول مرة في هذه المرحلة. خوارزمية الوسم هي خوارزمية لا تُرحّل صفحة مُعلّمة أبدًا.

إذا كانت ALG خوارزمية تعليم ذات ذاكرة تخزين مؤقت بحجم k، وOPT هي الخوارزمية المثلى ذات ذاكرة تخزين مؤقت بحجم h، حيث $h\leq k$ إذن، ALG هو ${\tfrac {k}{k-h+1}}$ -تنافسية. لذا فإن كل خوارزمية تقييم تحقق ${\tfrac {k}{k-h+1}}$ نسبة تنافسية.

LRU هي خوارزمية وضع علامات بينما FIFO ليست خوارزمية وضع علامات.

الخوارزميات المحافظة

تعتبر الخوارزمية متحفظة إذا كانت في أي تسلسل طلبات متتالي يحتوي على k أو أقل من مراجع الصفحات المتميزة، ستتكبد الخوارزمية k أو أقل من أخطاء الصفحات.

إذا كانت ALG خوارزمية محافظة ذات ذاكرة تخزين مؤقت بحجم k، وOPT هي الخوارزمية المثلى ذات ذاكرة تخزين مؤقت بحجم $h\leq k$ إذن، ALG هو ${\tfrac {k}{k-h+1}}$ -تنافسية. لذا فإن كل خوارزمية محافظة تحقق ذلك ${\tfrac {k}{k-h+1}}$ نسبة تنافسية.

تُعتبر خوارزميات LRU و FIFO و CLOCK خوارزميات محافظة.

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

توجد مجموعة متنوعة من خوارزميات استبدال الصفحات: ^{[ 2 ]}

خوارزمية استبدال الصفحات المثلى نظرياً

خوارزمية استبدال الصفحات المثلى نظريًا (المعروفة أيضًا باسم OPT، أو خوارزمية الاستبدال الاستشرافية ، أو سياسة استبدال الصفحات المثلى لبيلادي ) ^{[ 3 ]}^{[ 4 ]}^{[ 2 ]} هي خوارزمية تعمل على النحو التالي: عندما يحتاج نظام التشغيل إلى استبدال صفحة، فإنه يستبدل الصفحة التي سيتم استخدامها لاحقًا بأبعد مدة. على سبيل المثال، سيتم استبدال صفحة لن تُستخدم خلال الثواني الست القادمة بصفحة سيتم استخدامها خلال 0.4 ثانية القادمة.

لا يمكن تطبيق هذه الخوارزمية في نظام تشغيل عام لأنه من المستحيل حساب المدة الزمنية اللازمة لاستخدام صفحة ما بدقة، إلا في حالتين: إما أن تكون جميع البرامج التي ستعمل على النظام معروفة مسبقًا وقابلة للتحليل الثابت لأنماط الوصول إلى الذاكرة، أو أن تقتصر على فئة محددة من التطبيقات التي تسمح بالتحليل أثناء التشغيل. على الرغم من هذا القيد، توجد خوارزميات ^{[ 5 ]} قادرة على تحقيق أداء شبه مثالي، حيث يحتفظ نظام التشغيل بسجل لجميع الصفحات التي يشير إليها البرنامج، ويستخدم هذه البيانات لتحديد الصفحات التي سيتم استبدالها في عمليات التشغيل اللاحقة. يمكن لهذه الخوارزمية تحقيق أداء شبه مثالي، ولكن ليس في أول تشغيل للبرنامج، وفقط إذا كان نمط الوصول إلى الذاكرة للبرنامج متسقًا نسبيًا في كل مرة يتم تشغيله.

تم أيضاً تحليل مشكلة الترحيل في مجال الخوارزميات عبر الإنترنت . ويتم قياس كفاءة الخوارزميات العشوائية عبر الإنترنت لحل مشكلة الترحيل باستخدام تحليل الاستهلاك .

غير مستخدمة مؤخراً

خوارزمية استبدال الصفحات غير المستخدمة مؤخرًا (NRU) هي خوارزمية تُفضّل الاحتفاظ بالصفحات التي استُخدمت مؤخرًا في الذاكرة. تعمل هذه الخوارزمية وفق المبدأ التالي: عند الإشارة إلى صفحة، يتم ضبط بت الإشارة إليها، مما يدل على أنها مُشار إليها. وبالمثل، عند تعديل صفحة (الكتابة إليها)، يتم ضبط بت التعديل. عادةً ما يتم ضبط هذه البتات بواسطة العتاد، مع إمكانية القيام بذلك برمجيًا أيضًا.

عند فترة زمنية محددة، يتم تفعيل مقاطعة مؤقتة، مما يؤدي إلى مسح بت الإشارة من جميع الصفحات، وبالتالي لا يتم تمييز بت الإشارة إلا للصفحات التي تمت الإشارة إليها خلال فترة المؤقت الحالية. وعندما تحتاج صفحة ما إلى الاستبدال، يقوم نظام التشغيل بتقسيم الصفحات إلى أربع فئات:

3. المشار إليه، المعدل

2. تمت الإشارة إليه، وليس تعديله

1. غير مذكور، معدل

0. غير مُشار إليه، غير مُعدَّل

على الرغم من أنه يبدو من غير الممكن تعديل صفحة دون الإشارة إليها، إلا أن هذا يحدث عندما تُمسح بتة الإشارة إلى صفحة من الفئة 3 بواسطة مقاطعة المؤقت. تختار خوارزمية NRU صفحة عشوائية من أدنى فئة لإزالتها. لذا، من بين فئات الصفحات الأربع المذكورة أعلاه، ستستبدل خوارزمية NRU صفحة غير مُشار إليها وغير مُعدّلة، إن وُجدت. تجدر الإشارة إلى أن هذه الخوارزمية تعني أن الصفحة المُعدّلة ولكن غير المُشار إليها (خلال فترة المؤقت الأخيرة) أقل أهمية من الصفحة غير المُعدّلة التي تتم الإشارة إليها بكثافة.

NRU هي خوارزمية للتقييم، لذا فهي ${\tfrac {k}{k-h+1}}$ -تنافسي.

أسبقية الحضور، أسبقية الخروج

أبسط خوارزمية لاستبدال الصفحات هي خوارزمية FIFO (الأول في الأول خارج). تُعدّ خوارزمية استبدال الصفحات هذه خوارزمية منخفضة التكلفة، لا تتطلب الكثير من العمليات الحسابية من جانب نظام التشغيل . الفكرة واضحة من اسمها، حيث يحتفظ نظام التشغيل بسجل لجميع الصفحات الموجودة في الذاكرة في قائمة انتظار، مع وضع أحدث صفحة في نهاية القائمة وأقدمها في بدايتها. عند الحاجة إلى استبدال صفحة، يتم اختيار الصفحة الموجودة في بداية قائمة الانتظار (أقدم صفحة). على الرغم من أن خوارزمية FIFO بسيطة وسهلة الاستخدام، إلا أنها ضعيفة الأداء في التطبيقات العملية، ولذلك نادرًا ما تُستخدم بشكلها الأصلي. تُعاني هذه الخوارزمية من شذوذ بيلادي ، أي أنه عند حدوث خطأ في الصفحة، يتم استبدال الإطار الذي بقي في الذاكرة لأطول فترة.

يستخدم نظام التشغيل OpenVMS خوارزمية استبدال الصفحات FIFO مع بعض التعديلات. ^{[ 6 ]} يتم توفير فرصة ثانية جزئية عن طريق تخطي عدد محدود من الإدخالات ذات مراجع جدول الترجمة الصالحة، ^{[ 7 ]} بالإضافة إلى ذلك، يتم نقل الصفحات من مجموعة عمل العملية إلى مجمع على مستوى النظام حيث يمكن استعادتها إذا لم يتم إعادة استخدامها بالفعل.

خوارزمية FIFO خوارزمية محافظة، لذا فهي ${\tfrac {k}{k-h+1}}$ -تنافسي.

فرصة ثانية

يُعدّ شكلٌ مُعدّل من خوارزمية استبدال الصفحات FIFO، يُعرف باسم خوارزمية استبدال الصفحات ذات الفرصة الثانية، أفضل نسبيًا من FIFO مع تكلفة تحسين طفيفة. تعمل هذه الخوارزمية من خلال فحص مقدمة قائمة الانتظار كما تفعل FIFO، ولكن بدلًا من سحب الصفحة فورًا، تتحقق مما إذا كانت بتة الإشارة الخاصة بها مُفعّلة. إذا لم تكن مُفعّلة، يتم استبدال الصفحة. أما إذا كانت مُفعّلة، فتُمسح بتة الإشارة، وتُضاف الصفحة إلى مؤخرة قائمة الانتظار (كما لو كانت صفحة جديدة)، وتُكرر هذه العملية. يُمكن أيضًا اعتبار هذه الخوارزمية قائمة انتظار دائرية. إذا كانت بتة الإشارة لجميع الصفحات مُفعّلة، فسيتم استبدال الصفحة الأولى في القائمة عند ظهورها للمرة الثانية، لأن بتة الإشارة الخاصة بها أصبحت الآن مُمسحة. أما إذا كانت بتة الإشارة لجميع الصفحات مُمسحة، فإن خوارزمية الفرصة الثانية تتحول إلى خوارزمية FIFO خالصة.

كما يوحي اسمها، فإن ميزة "الفرصة الثانية" تمنح كل صفحة "فرصة ثانية" - فالصفحة القديمة التي تمت الإشارة إليها ربما تكون قيد الاستخدام، ولا ينبغي استبدالها بصفحة جديدة لم تتم الإشارة إليها.

ساعة

تُعدّ خوارزمية الساعة نسخةً أكثر كفاءةً من خوارزمية FIFO مقارنةً بخوارزمية الفرصة الثانية، إذ لا تتطلب دفع الصفحات باستمرار إلى نهاية القائمة، مع أنها تؤدي الوظيفة العامة نفسها. تحتفظ خوارزمية الساعة بقائمة دائرية من الصفحات في الذاكرة، حيث يشير "العقرب" (المُكرِّر) إلى آخر إطار صفحة تم فحصه في القائمة. عند حدوث خطأ في الصفحة وعدم وجود إطارات فارغة، يتم فحص بت R (المُشار إليه) عند موضع العقرب. إذا كانت قيمة R تساوي صفرًا، تُوضع الصفحة الجديدة مكان الصفحة التي يشير إليها "العقرب"، ويُحرَّك العقرب موضعًا واحدًا للأمام. وإلا، تُمسح قيمة بت R، ثم يُزاد عقرب الساعة، وتُكرَّر العملية حتى يتم استبدال صفحة. ^{[ 8 ]} وُصِفت هذه الخوارزمية لأول مرة عام 1969 على يد فرناندو ج. كورباتو . ^{[ 9 ]}

أنواع الساعات

GCLOCK: خوارزمية استبدال صفحات الساعة المعممة. ^{[ 10 ]}
يحتفظ برنامج Clock-Pro بقائمة دائرية من المعلومات حول الصفحات التي تمت الإشارة إليها مؤخرًا، بما في ذلك جميع صفحات M الموجودة في الذاكرة بالإضافة إلى أحدث صفحات M التي تم إخراجها من الذاكرة. هذه المعلومات الإضافية حول الصفحات التي تم إخراجها من الذاكرة، مثل المعلومات المماثلة التي يحتفظ بها برنامج ARC ، تساعده على العمل بشكل أفضل من برنامج LRU في الحلقات الكبيرة وعمليات المسح لمرة واحدة. ^{[ 11 ]}
WSclock. ^{[ 12 ]} من خلال دمج خوارزمية الساعة مع مفهوم مجموعة العمل (أي مجموعة الصفحات المتوقع استخدامها من قِبل تلك العملية خلال فترة زمنية محددة)، يمكن تحسين أداء الخوارزمية. عمليًا، تُعد خوارزمية "التقادم" وخوارزمية "WSClock" من أهم خوارزميات استبدال الصفحات. ^{[ 13 ]}^{[ 14 ]}
خوارزمية استبدال الصفحات باستخدام الساعة مع الاستبدال التكيفي (CAR) هي خوارزمية استبدال صفحات ذات أداء يُضاهي خوارزمية ARC ، وتتفوق بشكل ملحوظ على كل من خوارزميتي LRU وCLOCK. ^{[ 15 ]} تتميز خوارزمية CAR بضبطها الذاتي ولا تتطلب أي معلمات خاصة يحددها المستخدم.

خوارزمية CLOCK خوارزمية محافظة، لذا فهي ${\tfrac {k}{k-h+1}}$ -تنافسي.

الأقل استخدامًا مؤخرًا

على الرغم من تشابه اسم خوارزمية استبدال الصفحات الأقل استخدامًا مؤخرًا (LRU) مع خوارزمية NRU، إلا أنها تختلف عنها في كونها تتتبع استخدام الصفحات خلال فترة زمنية قصيرة، بينما تكتفي NRU بمراقبة الاستخدام في آخر دورة ساعة. تعتمد LRU على فكرة أن الصفحات الأكثر استخدامًا في التعليمات القليلة الماضية هي الأكثر عرضة للاستخدام بكثافة في التعليمات القليلة التالية أيضًا. ورغم أن LRU تُحقق أداءً شبه مثالي نظريًا (يكاد يُضاهي أداء ذاكرة التخزين المؤقت للاستبدال التكيفي )، إلا أن تطبيقها عمليًا مُكلف للغاية. توجد عدة طرق لتطبيق هذه الخوارزمية تُحاول تقليل التكلفة مع الحفاظ على أعلى مستوى ممكن من الأداء.

الطريقة الأكثر تكلفة هي طريقة القائمة المتصلة ، التي تستخدم قائمة متصلة تحتوي على جميع الصفحات في الذاكرة. في نهاية هذه القائمة توجد الصفحة الأقل استخدامًا، وفي بدايتها توجد الصفحة الأكثر استخدامًا. تكمن تكلفة هذه الطريقة في ضرورة نقل عناصر القائمة مع كل عملية وصول إلى الذاكرة، وهي عملية تستغرق وقتًا طويلًا.

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

بسبب تكاليف التنفيذ، يمكن للمرء أن يفكر في خوارزميات (مثل تلك التي تليها) مشابهة لخوارزمية LRU، ولكنها توفر تطبيقات أرخص.

تتمثل إحدى المزايا المهمة لخوارزمية LRU في قابليتها للتحليل الإحصائي الكامل. فقد ثبت، على سبيل المثال، أن خوارزمية LRU لا يمكن أن تتسبب في أخطاء صفحات أكثر من N ضعفًا مقارنةً بخوارزمية OPT، حيث N تتناسب طرديًا مع عدد الصفحات في مجموعة الصفحات المُدارة.

من ناحية أخرى، تكمن نقطة ضعف خوارزمية LRU في ميل أدائها للتدهور في ظل العديد من أنماط الوصول الشائعة. على سبيل المثال، إذا كان هناك N صفحة في مجمع LRU، فإن تطبيقًا يُنفذ حلقة تكرارية على مصفوفة من N + 1 صفحة سيؤدي إلى خطأ في الصفحة عند كل وصول. ونظرًا لشيوع الحلقات التكرارية على المصفوفات الكبيرة، بُذلت جهود كبيرة لتعديل خوارزمية LRU لتحسين أدائها في مثل هذه الحالات. تحاول العديد من التعديلات المقترحة على خوارزمية LRU اكتشاف أنماط الوصول المتكررة والتحويل إلى خوارزمية استبدال مناسبة، مثل خوارزمية MRU (الأكثر استخدامًا مؤخرًا).

متغيرات على LRU

تقوم خوارزمية LRU-K ^{[ 16 ]} بحذف الصفحة التي كان آخر وصول لها (رقم K) هو الأقدم. على سبيل المثال، LRU-1 هي ببساطة LRU، بينما تقوم LRU-2 بحذف الصفحات وفقًا لوقت آخر وصول لها. تُحسّن LRU-K بشكل كبير من LRU فيما يتعلق بموقع الصفحة في الوقت المناسب.
تُوسّع خوارزمية ARC [ ^{17 ] خوارزمية} LRU من خلال الاحتفاظ بسجل للصفحات التي تم إخراجها مؤخرًا، وتستخدم هذا السجل لتغيير تفضيل الوصول إلى الصفحات الحديثة أو المتكررة. وهي مقاومة بشكل خاص لعمليات المسح التسلسلي.
تُحسّن خوارزمية 2Q ^{[ 18 ]} من خوارزميتي LRU وLRU/2. باستخدامها طابورين، أحدهما للعناصر ذات المسار السريع والآخر للعناصر ذات المسار البطيء، تُوضع العناصر أولًا في طابور المسار البطيء، ثم تُوضع في طابور المسار السريع بعد الوصول إليها مرة أخرى. ونظرًا لأن مدة الاحتفاظ بالمراجع للعناصر المضافة أطول من خوارزميتي LRU وLRU/2، فإنها تتميز بطابور مسار سريع أفضل، مما يُحسّن معدل الوصول إلى الذاكرة المؤقتة.

يمكن الاطلاع على مقارنة ARC مع الخوارزميات الأخرى (LRU، MQ، 2Q، LRU-2، LRFU، LIRS ) في Megiddo & Modha 2004. ^{[ 19 ]}

LRU هي خوارزمية للتمييز، لذا فهي ${\tfrac {k}{k-h+1}}$ -تنافسي.

عشوائي

تستبدل خوارزمية الاستبدال العشوائي صفحة عشوائية في الذاكرة، مما يلغي تكلفة تتبع مراجع الصفحات. وعادةً ما يكون أداؤها أفضل من خوارزمية FIFO، وفي حالة مراجع الذاكرة المتكررة، تكون أفضل من خوارزمية LRU، مع أن LRU تتفوق عليها عمليًا. يستخدم نظام التشغيل OS/390 تقريبًا شاملًا لخوارزمية LRU، ويلجأ إلى الاستبدال العشوائي عند تراجع أداء LRU، كما استخدم معالج Intel i860 سياسة الاستبدال العشوائي (Rhodehamel 1989 ^{[ 20 ]} ).

غير مستخدم بشكل متكرر (NFU)

تتطلب خوارزمية استبدال الصفحات غير المستخدمة بكثرة (NFU) عدادًا، ولكل صفحة عداد خاص بها يُضبط مبدئيًا على الصفر. عند كل فاصل زمني، يتم زيادة عداد جميع الصفحات التي تمت الإشارة إليها خلال ذلك الفاصل بمقدار 1. وبذلك، تتتبع العدادات مدى تكرار استخدام كل صفحة. وبالتالي، يمكن استبدال الصفحة ذات العداد الأقل عند الضرورة.

تكمن المشكلة الرئيسية في خوارزمية NFU في أنها تتعقب معدل استخدام الصفحات دون مراعاة مدة الاستخدام. وبالتالي، في مُصرّف متعدد المراحل ، تُفضّل الصفحات التي استُخدمت بكثافة خلال المرحلة الأولى، ولكنها غير مطلوبة في المرحلة الثانية، على الصفحات الأقل استخدامًا في المرحلة الثانية، نظرًا لارتفاع عدادات معدل استخدامها. ينتج عن ذلك أداء ضعيف. توجد سيناريوهات شائعة أخرى تتصرف فيها خوارزمية NFU بشكل مشابه، مثل بدء تشغيل نظام التشغيل. لحسن الحظ، توجد خوارزمية مماثلة وأفضل، وسيتم شرحها لاحقًا.

إن خوارزمية استبدال الصفحات غير المستخدمة بشكل متكرر تولد أخطاء صفحات أقل من خوارزمية استبدال الصفحات الأقل استخدامًا عندما يحتوي جدول الصفحات على قيم مؤشر فارغة .

شيخوخة

تُعدّ خوارزمية التقادم امتدادًا لخوارزمية NFU، مع تعديلات تجعلها تراعي الفترة الزمنية للاستخدام. فبدلًا من مجرد زيادة عدادات الصفحات المُشار إليها، مع إيلاء أهمية متساوية لجميع مراجع الصفحات بغض النظر عن الوقت، يتم أولًا إزاحة عداد المراجع في الصفحة إلى اليمين (بقسمته على 2)، قبل إضافة البت المُشار إليه إلى يسار ذلك الرقم الثنائي. على سبيل المثال، إذا أشارت صفحة ما إلى البتات 1,0,0,1,1,0 خلال الست نبضات ساعة الماضية، فسيبدو عداد المراجع الخاص بها على النحو التالي بالترتيب الزمني: 10000000، 01000000، 00100000، 10010000، 11001000، 01100100. للمراجع الأقرب إلى الوقت الحاضر تأثير أكبر من المراجع القديمة. وهذا يضمن أن الصفحات التي تمت الإشارة إليها مؤخرًا، وإن كانت أقل تكرارًا، ستكون لها أولوية أعلى من الصفحات التي تمت الإشارة إليها بشكل متكرر في الماضي. وبالتالي، عندما تحتاج صفحة ما إلى استبدال، سيتم اختيار الصفحة ذات العداد الأدنى.

يحاكي كود بايثون التالي خوارزمية التقادم. العدادات $V_{i}$ هي الأحرف الأولى من كلمة "ك" مع0 وتم تحديثه كما هو موضح أعلاه عبر $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ ، باستخدام عوامل الإزاحة الحسابية .

from collections.abc import Sequenceدالة محاكاة الشيخوخة ( Rs : تسلسل ، k : عدد صحيح ) -> لا شيء : """محاكاة الشيخوخة""" print("t | R-bits (0- {length}) | عدادات للصفحات 0- {length} ".format(length = len ( Rs ) ) ) Vs = [ 0 ] * len ( Rs [ 0 ] ) for t , R in enumerate ( Rs ) : Vs [ : ] = [ R [ i ] << ( k - 1 ) | V >> 1 for i , V in enumerate ( Vs ) ] print ( " { : 02d }  | {}  | [ {} ]" . format ( t , R , "", " .join ( [ "{:0 {} b}" . format ( V , k ) for V in Vs ])))

في المثال المذكور لـ R-bits لست صفحات على مدى خمس نبضات ساعة، تطبع الدالة المخرجات التالية، والتي تسرد R-bits لكل نبضة ساعة $t$ وقيم العداد الفردية $V_{i}$ لكل صفحة في التمثيل الثنائي . ^{[ 21 ]}

>>> Rs=[[1,0,1,0,1,1],[1,1,0,0,1,0],[1,1,0,1,0,1],[1,0,0,0,1,0],[0,1,1,0,0,0]]>>> k=8>>> simulate_aging(Rs,k) t | R-bits (0-5) | Counters for pages 0-500 | [1, 0, 1, 0, 1, 1] | [10000000, 00000000, 10000000, 00000000, 10000000, 10000000]01 | [1, 1, 0, 0, 1, 0] | [11000000, 10000000, 01000000, 00000000, 11000000, 01000000]02 | [1, 1, 0, 1, 0, 1] | [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]03 | [1, 0, 0, 0, 1, 0] | [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]04 | [0, 1, 1, 0, 0, 0] | [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]

Note that aging differs from LRU in the sense that aging can only keep track of the references in the latest 16/32 (depending on the bit size of the processor's integers) time intervals. Consequently, two pages may have referenced counters of 00000000, even though one page was referenced 9 intervals ago and the other 1000 intervals ago. Generally speaking, knowing the usage within the past 16 intervals is sufficient for making a good decision as to which page to swap out. Thus, aging can offer near-optimal performance for a moderate price.

Longest distance first (LDF) page replacement algorithm

The basic idea behind this algorithm is Locality of Reference as used in LRU but the difference is that in LDF, locality is based on distance not on the used references. In the LDF, replace the page which is on longest distance from the current page. If two pages are on same distance then the page which is next to current page in anti-clock rotation will get replaced.

Implementation details

Techniques for hardware with no reference bit

Many of the techniques discussed above assume the presence of a reference bit associated with each page. Some hardware has no such bit, so its efficient use requires techniques that operate well without one.

من الأمثلة البارزة على ذلك أجهزة VAX التي تعمل بنظام OpenVMS . يعرف هذا النظام ما إذا تم تعديل صفحة ما، ولكن ليس بالضرورة ما إذا تمت قراءتها. يُعرف هذا الأسلوب باسم التخزين المؤقت الثانوي للصفحات. تُوضع الصفحات التي تُزال من مجموعات العمل (الذاكرة الخاصة بالعملية، عمومًا) في قوائم مخصصة، بينما تبقى في الذاكرة الفعلية لفترة من الزمن. لا تُعد إزالة صفحة من مجموعة العمل عملية استبدال للصفحة من الناحية التقنية، ولكنها تُحدد تلك الصفحة كمرشحة. تُوضع الصفحة التي لا يزال مخزنها الأساسي صالحًا (أي التي لم تتغير محتوياتها، أو لا تحتاج إلى الحفظ لأي سبب آخر) في نهاية قائمة الصفحات الحرة. أما الصفحة التي تتطلب الكتابة إلى المخزن الأساسي فتُوضع في قائمة الصفحات المُعدلة. عادةً ما يتم تفعيل هذه الإجراءات عندما يقل حجم قائمة الصفحات الحرة عن حد أدنى قابل للتعديل.

يمكن اختيار الصفحات لإزالتها من مجموعة العمل بطريقة عشوائية، مع توقع أنه في حال اختيار صفحة غير مناسبة، يمكن استرجاعها لاحقًا من قائمة الصفحات الحرة أو المعدلة قبل إزالتها من الذاكرة الفعلية. تُزال الصفحة المشار إليها بهذه الطريقة من قائمة الصفحات الحرة أو المعدلة وتُعاد إلى مجموعة عمل العملية. توفر قائمة الصفحات المعدلة أيضًا إمكانية كتابة الصفحات إلى وحدة التخزين الخلفية في مجموعات تضم أكثر من صفحة، مما يزيد من الكفاءة. يمكن بعد ذلك وضع هذه الصفحات في قائمة الصفحات الحرة. يشبه تسلسل الصفحات التي تصل إلى رأس قائمة الصفحات الحرة نتائج آلية LRU أو NRU، ويشابه التأثير العام خوارزمية الفرصة الثانية الموصوفة سابقًا.

يُستخدم مثال آخر في نواة لينكس على معالجات ARM . يُعوَّض نقص وظائف العتاد بتوفير جدولين للصفحات: جدول الصفحات الأصلي للمعالج، الذي لا يحتوي على بتات مرجعية أو بتات مُعدَّلة ، وجدول الصفحات المُدار برمجياً والذي يحتوي على البتات المطلوبة. تُحدَّد البتات المُحاكاة في الجدول المُدار برمجياً بواسطة أخطاء الصفحات. وللحصول على أخطاء الصفحات، يؤدي مسح البتات المُحاكاة في الجدول الثاني إلى إلغاء بعض حقوق الوصول إلى الصفحة المُقابلة، ويتم ذلك بتعديل الجدول الأصلي.

ذاكرة التخزين المؤقت للصفحات في لينكس

يستخدم نظام لينكس ذاكرة تخزين مؤقتة موحدة للصفحات لـ

brkوالمناطق المجهولة mmaped . يشمل ذلك كومة ومكدس برامج مساحة المستخدم . تتم كتابتها إلى مساحة التبديل عند نقلها إلى الذاكرة الافتراضية .
المناطق غير المجهولة (المدعومة بالملفات) mmap. إذا كانت موجودة في الذاكرة ولم يتم تعديلها بشكل خاص، تتم مشاركة الصفحة الفعلية مع ذاكرة التخزين المؤقت للملفات أو المخزن المؤقت.
الذاكرة المشتركة المكتسبة من خلال shm_open.
نظام الملفات tmpfs الموجود في الذاكرة؛ تتم كتابته إلى ملف التبديل عند نقله إلى الذاكرة الافتراضية.
تتضمن ذاكرة التخزين المؤقت للملفات ما يلي؛ الكتابة إلى وحدة التخزين الأساسية (ربما تمر عبر المخزن المؤقت، انظر أدناه) عند إخراجها من الصفحة.
ذاكرة التخزين المؤقت لأجهزة الكتل ، والتي يطلق عليها نظام Linux اسم "buffer" (لا ينبغي الخلط بينها وبين الهياكل الأخرى التي تسمى أيضًا مخازن مؤقتة مثل تلك المستخدمة للأنابيب والمخازن المؤقتة المستخدمة داخليًا في Linux)؛ يتم كتابتها إلى وحدة التخزين الأساسية عند ترحيلها.

تعمل ذاكرة التخزين المؤقت الموحدة للصفحات على وحدات أصغر حجم صفحة يدعمه المعالج (4 كيلوبايت في معالجات ARMv8 و x86 و x86-64 )، مع بعض الصفحات ذات الحجم الأكبر التالي (2 ميجابايت في x86-64 ) والتي تُسمى "الصفحات الضخمة" في نظام لينكس. تُقسم الصفحات في ذاكرة التخزين المؤقت إلى مجموعتين: "نشطة" و"غير نشطة". تحتفظ كلتا المجموعتين بقائمة الصفحات الأقل استخدامًا (LRU). في الحالة الأساسية، عند وصول برنامج في مساحة المستخدم إلى صفحة، تُوضع في بداية المجموعة غير النشطة. وعند الوصول إليها بشكل متكرر، تُنقل إلى القائمة النشطة. ينقل لينكس الصفحات من المجموعة النشطة إلى المجموعة غير النشطة حسب الحاجة، بحيث تكون المجموعة النشطة أصغر من المجموعة غير النشطة. عند نقل صفحة إلى المجموعة غير النشطة، تُزال من جدول الصفحات لأي مساحة عناوين عملية، دون إخراجها من الذاكرة الفعلية. ^{[ 22 ]}^{[ 23 ]} عند إزالة صفحة من المجموعة غير النشطة، تُخرج من الذاكرة الفعلية. يمكن الاستعلام عن حجم قائمة "النشط" و"غير النشط" من /proc/meminfoخلال الحقول "نشط"، "غير نشط"، "نشط (مجهول)"، "غير نشط (مجهول)"، "نشط (ملف)" و"غير نشط (ملف)".

مجموعة العمل

مجموعة العمل الخاصة بعملية ما هي مجموعة الصفحات المتوقع استخدامها بواسطة تلك العملية خلال فترة زمنية معينة.

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

مراجع

↑ بيل، جون. "ملاحظات دورة أنظمة التشغيل: الذاكرة الافتراضية" . كلية الهندسة بجامعة إلينوي في شيكاغو . مؤرشف من الأصل في 23 سبتمبر 2018. تم الاطلاع عليه في 21 يوليو 2017 .
1 2 جونز، دوغلاس دبليو. "ملاحظات المحاضرة 22C:116" . قسم علوم الحاسوب، جامعة أيوا . تم الاطلاع عليه بتاريخ 18 مارس 2008 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
↑ توريز، بول؛ وآخرون . "ملاحظات المحاضرة 11 من مقرر CS111" . قسم علوم الحاسوب، جامعة كاليفورنيا في لوس أنجلوس . مؤرشف من الأصل في 9 يناير 2009.
↑ بان، هيوكيونغ؛ نوه، سام هـ. (12-14 فبراير 2003). إعادة النظر في توصيف سلوك الإحالة إلى الويب: دليل على إدارة ذاكرة التخزين المؤقت الثنائية . المؤتمر الدولي لشبكات المعلومات 2003. جيجو، كوريا الجنوبية: سبرينغر-فيرلاغ. ص 1018-1027 . doi : 10.1007/978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.
↑ جاين، أكانكشا؛ لين، كالفن (2016). العودة إلى المستقبل: الاستفادة من خوارزمية بلادي لتحسين استبدال ذاكرة التخزين المؤقت (ملف PDF) . الندوة الدولية حول هندسة الحاسوب (ISCA). سيول، كوريا الجنوبية: IEEE. doi : 10.1109/ISCA.2016.17 .
↑ سيلبرشاتز، أبراهام؛ جالفين، بيتر باير؛ غاني، جريج (14 ديسمبر 2004). مفاهيم أنظمة التشغيل ( الطبعة السابعة). هوبوكين، نيوجيرسي، الولايات المتحدة الأمريكية: جون وايلي وأولاده. ص 339. ISBN 0-47169-466-5. OCLC 56913661 .
↑ مساعدة VMS — معلمات النظام، TBSKIPWSL
↑ تانينباوم، أندرو س. (2001). أنظمة التشغيل الحديثة ( الطبعة الثانية). أبر سادل ريفر، نيوجيرسي، الولايات المتحدة الأمريكية: برنتيس هول. ص 218 (4.4.5) . ISBN 978-0-13-031358-4. إل سي سي إن 00051666 . او سي ال سي 45284637 . رأ 24214243 م .
↑ كورباتو، فرناندو ج. (1969). "تجربة الترحيل باستخدام نظام Multics" (ملف PDF) . كتاب تذكاري: تكريمًا لـ PM Morse . مطبعة معهد ماساتشوستس للتكنولوجيا . الصفحات 217-228 .
↑ سميث، آلان جاي (سبتمبر 1978). "التسلسل والجلب المسبق في أنظمة قواعد البيانات" . معاملات ACM لأنظمة قواعد البيانات . 3 (3). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 223-247 . doi : 10.1145/320263.320276 . S2CID 11611563 .
↑ جيانغ، سونغ؛ تشين، فنغ؛ تشانغ، شياودونغ (10-15 أبريل 2005). CLOCK-Pro: تحسين فعال لاستبدال CLOCK (ملف PDF) . المؤتمر التقني السنوي لـ USENIX لعام 2005. أنهايم، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. ص 35. مؤرشف (ملف PDF) من الأصل في 12 يونيو 2019. تم الاطلاع عليه في 24 مارس 2009 .
↑ كار، ريتشارد دبليو؛ هينيسي، جون إل. (14-16 ديسمبر 1981). WSCLOCK - خوارزمية بسيطة وفعالة لإدارة الذاكرة الافتراضية (ملف PDF مضغوط) . الندوة الثامنة لجمعية ACM حول مبادئ أنظمة التشغيل . باسيفيك غروف، كاليفورنيا، الولايات المتحدة الأمريكية: ACM. الصفحات 87-95 . doi : 10.1145/800216.806596 . ISBN 0-89791-062-1تمت أرشفة هذا النص من النسخة الأصلية في 10 يونيو 2007.
↑ غوتليب، آلان. "WSClock" . قسم علوم الحاسوب بجامعة نيويورك . تم الاطلاع عليه بتاريخ 12 يونيو 2019 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
↑ تانينباوم، أندرو س. "خوارزميات استبدال الصفحات" . إنفورم آي تي . تم الاطلاع عليه بتاريخ 12 يونيو 2019 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
↑ بانسال، سوراف ومودها، دارمندرا س. (31 مارس - 2 أبريل 2004). CAR: ساعة مع استبدال تكيفي (ملف PDF) . المؤتمر الثالث لـ USENIX حول تقنيات الملفات والتخزين (FAST '04) . سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. الصفحات 187-200 . CiteSeerX 10.1.1.105.6057 . مؤرشف (ملف PDF) من الأصل في 31 يوليو 2004.
↑ أونيل، إليزابيث جيه؛ وآخرون . (25-28 مايو 1993). خوارزمية استبدال الصفحات LRU-K لتخزين البيانات على القرص (ملف PDF) . المؤتمر الدولي ACM SIGMOD لإدارة البيانات لعام 1993. واشنطن العاصمة، الولايات المتحدة الأمريكية: ACM. الصفحات 297-306 . CiteSeerX 10.1.1.18.1434 . doi : 10.1145/170035.170081 . ISBN 0-89791-592-5تمت أرشفة الملف (PDF) من النسخة الأصلية في 6 سبتمبر 2019.
↑ ميغيدو، نمرود ومودها، دارمندرا س. (31 مارس - 2 أبريل 2003). ARC: ذاكرة تخزين مؤقتة بديلة ذاتية الضبط ومنخفضة الحمل الزائد (ملف PDF) . المؤتمر الثاني لـ USENIX حول تقنيات الملفات والتخزين (FAST '03) . سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. الصفحات 115-130 . مؤرشف (ملف PDF) من الأصل في 8 فبراير 2010.
↑ جونسون، ثيودور؛ شاشا، دينيس (12-15 سبتمبر 1994). 2Q: خوارزمية استبدال إدارة المخزن المؤقت منخفضة الحمل وعالية الأداء (ملف PDF) . المؤتمر الدولي العشرون لقواعد البيانات الضخمة جدًا . سانتياغو، تشيلي: مورغان كوفمان. الصفحات 439-450 . ISBN 1-55860-153-8تمت أرشفة الملف (PDF) من النسخة الأصلية في 17 مارس 2020. تم الاطلاع عليه في 31 يوليو 2005 .
↑ ميغيدو، نمرود ومودها، دارمندرا س. (2004). "التفوق على خوارزمية LRU باستخدام خوارزمية ذاكرة التخزين المؤقت للاستبدال التكيفي" ( ملف PDF) . مجلة Computer ، 37 (4). جمعية IEEE للحاسبات: 58. CiteSeerX 10.1.1.231.498 . doi : 10.1109/MC.2004.1297303 . S2CID 5507282. مؤرشف (ملف PDF) من الأصل في 21 أكتوبر 2012. تم الاطلاع عليه في 20 سبتمبر 2013 .
↑ روديهاميل، مايكل و. (2-4 أكتوبر 1989). واجهة ناقل البيانات ووحدات الترحيل في المعالج الدقيق i860 . المؤتمر الدولي لعام 1989 لمعهد مهندسي الكهرباء والإلكترونيات حول تصميم الحاسوب: الدوائر المتكاملة واسعة النطاق في الحواسيب والمعالجات . كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية: معهد مهندسي الكهرباء والإلكترونيات. الصفحات 380-384 . doi : 10.1109/ICCD.1989.63392 . ISBN 0-8186-1971-6رقم الوصول في نظام INSPEC هو 3719504.
^ تاننباوم، أندرو س. بوس، هربرت (2015). أنظمة التشغيل الحديثة (الطبعة الرابعة ). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: بيرسون. ص. 215. ردمك 978-0-13-359162-0. OL 25620855M .
↑ انظر الشرح في بداية/mm/workingset.cمصدر لينكس
↑ كوربيت، جوناثان كوربيت (2 مايو 2012). "تحسين موازنة القوائم النشطة/غير النشطة" . LWN.net .

للمزيد من القراءة

وونغ، كين-يونغ (23 يناير 2006). "سياسات استبدال ذاكرة التخزين المؤقت للويب: منهج عملي". شبكة IEEE . 20 (1). IEEE: 28-34 . doi : 10.1109/MNET.2006.1580916 . ISSN 0890-8044 . S2CID 17969287. رقم الوصول في INSPEC 8964134.
أهو، ألفريد ف.؛ دينينغ، بيتر ج.؛ أولمان، جيفري د. (يناير 1971). "مبادئ الاستبدال الأمثل للصفحات" . مجلة ACM . 18 (1). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 80-93 . doi : 10.1145/321623.321632 . S2CID 3154537 .
تانينباوم، أندرو س. (1997). أنظمة التشغيل: التصميم والتنفيذ (الطبعة الثانية ). أبر سادل ريفر، نيوجيرسي، الولايات المتحدة الأمريكية: برنتيس هول. ISBN 0-13-638677-6. إل سي سي إن 96037153 . رأ 998396 م .
تانينباوم، أندرو س. (2001). أنظمة التشغيل الحديثة ( الطبعة الثانية). أبر سادل ريفر، نيوجيرسي، الولايات المتحدة الأمريكية: برنتيس هول. ISBN 978-0-13-031358-4. إل سي سي إن 00051666 . او سي ال سي 45284637 . رأ 24214243 م . مقتطف من الإنترنت حول خوارزميات استبدال الصفحات: خوارزميات استبدال الصفحات .
جلاس، جيديون؛ كاو، باي (15-18 يونيو 1997). استبدال الصفحات التكيفي بناءً على سلوك مرجع الذاكرة . المؤتمر الدولي لعام 1997 لجمعية ACM SIGMETRICS حول قياس ونمذجة أنظمة الحاسوب . سياتل، واشنطن، الولايات المتحدة الأمريكية: ACM. الصفحات 115-126 . doi : 10.1145/258612.258681 . ISBN 0-89791-909-2.متوفر أيضاً بصيغة موسعة بعنوان: جلاس، جيديون؛ كاو، باي (1997). "التقرير الفني 1338" . قسم علوم الحاسوب، جامعة ويسكونسن-ماديسون .
كيم، جونغ مين؛ وآخرون . (17-21 أكتوبر 2000). مخطط إدارة مخزن مؤقت موحد عالي الأداء ومنخفض التكاليف يستغل المراجع التسلسلية والحلقية (ملف PDF) . المؤتمر الرابع لجمعية USENIX حول تصميم وتنفيذ أنظمة التشغيل (OSDI'2000) . المجلد 4. سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. مؤرشف (ملف PDF) من النسخة الأصلية في 18 سبتمبر 2004.
سماراغداكيس، يانيس؛ كابلان، سكوت؛ ويلسون، بول (1-4 مايو 1999). EELRU: استبدال الصفحات التكيفي البسيط والفعال (ملف PDF) . المؤتمر الدولي لجمعية ACM SIGMETRICS لعام 1999 حول قياس ونمذجة أنظمة الحاسوب . أتلانتا، جورجيا، الولايات المتحدة الأمريكية: ACM. الصفحات 122-133 . doi : 10.1145/301453.301486 . ISBN 1-58113-083-Xتمت أرشفة الملف (PDF) من النسخة الأصلية في 4 مارس 2016.
جيانغ، سونغ؛ تشانغ، شياودونغ (15-19 يونيو 2002). LIRS: بديل لمجموعة المراجع الحديثة المنخفضة (ملف PDF) . المؤتمر الدولي لعام 2002 لجمعية ACM SIGMETRICS حول قياس ونمذجة أنظمة الحاسوب . مارينا ديل ري، كاليفورنيا، الولايات المتحدة الأمريكية: ACM. الصفحات 31-42 . doi : 10.1145/511334.511340 . ISBN 1-58113-531-9تمت أرشفة الملف (PDF) من النسخة الأصلية في 12 يونيو 2019.
لي، دونغهي؛ وآخرون . (1-4 سبتمبر 1997). تطبيق وتقييم أداء سياسة استبدال وحدات LRFU . المؤتمر الثالث والعشرون لـ Euromicro: آفاق جديدة لتكنولوجيا المعلومات . بودابست، المجر: جمعية IEEE للحاسبات. الصفحات 106-111 . doi : 10.1109/EMSCNT.1997.658446 . ISBN 0-8186-8215-9رقم الوصول إلى INSPEC هو 5856800.
تشو، يوانيوان؛ فيلبين، جيمس؛ لي، كاي (25-30 يونيو 2001). خوارزمية استبدال الطوابير المتعددة لذاكرة التخزين المؤقت من المستوى الثاني (ملف PDF) . المؤتمر التقني السنوي لجمعية USENIX لعام 2001. بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: جمعية USENIX. الصفحات 91-104 . ISBN 1-880446-09-Xتمت أرشفة (PDF) من الأصل في 24 نوفمبر 2005.

[1] بيل، جون. "ملاحظات دورة أنظمة التشغيل: الذاكرة الافتراضية" . كلية الهندسة بجامعة إلينوي في شيكاغو . مؤرشف من الأصل في 23 سبتمبر 2018. تم الاطلاع عليه في 21 يوليو 2017 .

[lecture_notes_jones-2] 1 2 جونز، دوغلاس دبليو. "ملاحظات المحاضرة 22C:116" . قسم علوم الحاسوب، جامعة أيوا . تم الاطلاع عليه بتاريخ 18 مارس 2008 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )

[3] توريز، بول؛ وآخرون . "ملاحظات المحاضرة 11 من مقرر CS111" . قسم علوم الحاسوب، جامعة كاليفورنيا في لوس أنجلوس . مؤرشف من الأصل في 9 يناير 2009.

[4] بان، هيوكيونغ؛ نوه، سام هـ. (12-14 فبراير 2003). إعادة النظر في توصيف سلوك الإحالة إلى الويب: دليل على إدارة ذاكرة التخزين المؤقت الثنائية . المؤتمر الدولي لشبكات المعلومات 2003. جيجو، كوريا الجنوبية: سبرينغر-فيرلاغ. ص 1018-1027 . doi : 10.1007/978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.

[5] جاين، أكانكشا؛ لين، كالفن (2016). العودة إلى المستقبل: الاستفادة من خوارزمية بلادي لتحسين استبدال ذاكرة التخزين المؤقت (ملف PDF) . الندوة الدولية حول هندسة الحاسوب (ISCA). سيول، كوريا الجنوبية: IEEE. doi : 10.1109/ISCA.2016.17 .

[Silber-6] سيلبرشاتز، أبراهام؛ جالفين، بيتر باير؛ غاني، جريج (14 ديسمبر 2004). مفاهيم أنظمة التشغيل ( الطبعة السابعة). هوبوكين، نيوجيرسي، الولايات المتحدة الأمريكية: جون وايلي وأولاده. ص 339. ISBN 0-47169-466-5. OCLC 56913661 .

[7] مساعدة VMS — معلمات النظام، TBSKIPWSL

[Tanenbaum-8] تانينباوم، أندرو س. (2001). أنظمة التشغيل الحديثة ( الطبعة الثانية). أبر سادل ريفر، نيوجيرسي، الولايات المتحدة الأمريكية: برنتيس هول. ص 218 (4.4.5) . ISBN 978-0-13-031358-4. إل سي سي إن 00051666 . او سي ال سي 45284637 . رأ 24214243 م .

[9] كورباتو، فرناندو ج. (1969). "تجربة الترحيل باستخدام نظام Multics" (ملف PDF) . كتاب تذكاري: تكريمًا لـ PM Morse . مطبعة معهد ماساتشوستس للتكنولوجيا . الصفحات 217-228 .

[10] سميث، آلان جاي (سبتمبر 1978). "التسلسل والجلب المسبق في أنظمة قواعد البيانات" . معاملات ACM لأنظمة قواعد البيانات . 3 (3). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 223-247 . doi : 10.1145/320263.320276 . S2CID 11611563 .

[11] جيانغ، سونغ؛ تشين، فنغ؛ تشانغ، شياودونغ (10-15 أبريل 2005). CLOCK-Pro: تحسين فعال لاستبدال CLOCK (ملف PDF) . المؤتمر التقني السنوي لـ USENIX لعام 2005. أنهايم، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. ص 35. مؤرشف (ملف PDF) من الأصل في 12 يونيو 2019. تم الاطلاع عليه في 24 مارس 2009 .

[12] كار، ريتشارد دبليو؛ هينيسي، جون إل. (14-16 ديسمبر 1981). WSCLOCK - خوارزمية بسيطة وفعالة لإدارة الذاكرة الافتراضية (ملف PDF مضغوط) . الندوة الثامنة لجمعية ACM حول مبادئ أنظمة التشغيل . باسيفيك غروف، كاليفورنيا، الولايات المتحدة الأمريكية: ACM. الصفحات 87-95 . doi : 10.1145/800216.806596 . ISBN 0-89791-062-1تمت أرشفة هذا النص من النسخة الأصلية في 10 يونيو 2007.

[13] غوتليب، آلان. "WSClock" . قسم علوم الحاسوب بجامعة نيويورك . تم الاطلاع عليه بتاريخ 12 يونيو 2019 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )

[14] تانينباوم، أندرو س. "خوارزميات استبدال الصفحات" . إنفورم آي تي . تم الاطلاع عليه بتاريخ 12 يونيو 2019 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )

[15] بانسال، سوراف ومودها، دارمندرا س. (31 مارس - 2 أبريل 2004). CAR: ساعة مع استبدال تكيفي (ملف PDF) . المؤتمر الثالث لـ USENIX حول تقنيات الملفات والتخزين (FAST '04) . سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. الصفحات 187-200 . CiteSeerX 10.1.1.105.6057 . مؤرشف (ملف PDF) من الأصل في 31 يوليو 2004.

[16] أونيل، إليزابيث جيه؛ وآخرون . (25-28 مايو 1993). خوارزمية استبدال الصفحات LRU-K لتخزين البيانات على القرص (ملف PDF) . المؤتمر الدولي ACM SIGMOD لإدارة البيانات لعام 1993. واشنطن العاصمة، الولايات المتحدة الأمريكية: ACM. الصفحات 297-306 . CiteSeerX 10.1.1.18.1434 . doi : 10.1145/170035.170081 . ISBN 0-89791-592-5تمت أرشفة الملف (PDF) من النسخة الأصلية في 6 سبتمبر 2019.

[17] ميغيدو، نمرود ومودها، دارمندرا س. (31 مارس - 2 أبريل 2003). ARC: ذاكرة تخزين مؤقتة بديلة ذاتية الضبط ومنخفضة الحمل الزائد (ملف PDF) . المؤتمر الثاني لـ USENIX حول تقنيات الملفات والتخزين (FAST '03) . سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية USENIX. الصفحات 115-130 . مؤرشف (ملف PDF) من الأصل في 8 فبراير 2010.

[18] جونسون، ثيودور؛ شاشا، دينيس (12-15 سبتمبر 1994). 2Q: خوارزمية استبدال إدارة المخزن المؤقت منخفضة الحمل وعالية الأداء (ملف PDF) . المؤتمر الدولي العشرون لقواعد البيانات الضخمة جدًا . سانتياغو، تشيلي: مورغان كوفمان. الصفحات 439-450 . ISBN 1-55860-153-8تمت أرشفة الملف (PDF) من النسخة الأصلية في 17 مارس 2020. تم الاطلاع عليه في 31 يوليو 2005 .

[19] ميغيدو، نمرود ومودها، دارمندرا س. (2004). "التفوق على خوارزمية LRU باستخدام خوارزمية ذاكرة التخزين المؤقت للاستبدال التكيفي" ( ملف PDF) . مجلة Computer ، 37 (4). جمعية IEEE للحاسبات: 58. CiteSeerX 10.1.1.231.498 . doi : 10.1109/MC.2004.1297303 . S2CID 5507282. مؤرشف (ملف PDF) من الأصل في 21 أكتوبر 2012. تم الاطلاع عليه في 20 سبتمبر 2013 .

[20] روديهاميل، مايكل و. (2-4 أكتوبر 1989). واجهة ناقل البيانات ووحدات الترحيل في المعالج الدقيق i860 . المؤتمر الدولي لعام 1989 لمعهد مهندسي الكهرباء والإلكترونيات حول تصميم الحاسوب: الدوائر المتكاملة واسعة النطاق في الحواسيب والمعالجات . كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية: معهد مهندسي الكهرباء والإلكترونيات. الصفحات 380-384 . doi : 10.1109/ICCD.1989.63392 . ISBN 0-8186-1971-6رقم الوصول في نظام INSPEC هو 3719504.

[21] تاننباوم، أندرو س. بوس، هربرت (2015). أنظمة التشغيل الحديثة (الطبعة الرابعة ). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: بيرسون. ص. 215. ردمك 978-0-13-359162-0. OL 25620855M .

[22] انظر الشرح في بداية/mm/workingset.cمصدر لينكس

[23] كوربيت، جوناثان كوربيت (2 مايو 2012). "تحسين موازنة القوائم النشطة/غير النشطة" . LWN.net .

[1]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

17 ] خوارزمية

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]