خوارزمية أقل استخدام تكراري
خوارزمية الأقل استخدام تكراري (LFU) هو نوع من خوارزميات التخزين المؤقت المستخدمة لإدارة الذاكرة داخل الحاسوب. تتضمن الخصائص القياسية لهذه الطريقة قيام النظام بتتبع عدد المرات التي يتم فيها الإشارة إلى كتلة ما في الذاكرة. عندما يكون التخزين المؤقت ممتلئًا ويتطلب مزيدًا من المساحة، سيقوم النظام بإزالة العنصر الذي يحتوي على أقل تكرار.
يتم أحيانًا دمج LFU مع خوارزمية الأقل استخدام مؤخرًا وتسمى LRFU.[1]
التنفيذ
عدلأبسط طريقة لاستخدام خوارزمية LFU هي تعيين عداد لكل كتلة يتم تحميلها في الذاكرة المؤقتة. في كل مرة يتم فيها الإشارة إلى تلك الكتلة، يزداد العداد بمقدار واحد. عندما يصل التخزين المؤقت إلى سعته القصوى ويكون هناك كتلة جديدة تنتظر الإدخال، يبحث النظام عن الكتلة التي تحتوي على أقل قيمة عداد ويزيلها من التخزين المؤقت. في حالة التعادل (أي وجود مفتاحين أو أكثر بنفس التردد)، يتم إبطال المفتاح الذي تم استخدامه مؤخرًا (LRU)
المشاكل
عدلفي حين أن طريقة خوارزمية LFU قد تبدو وكأنها طريقة بديهية لإدارة الذاكرة، إلا أنها ليست خالية من الأخطاء. فكر في عنصر في الذاكرة تتم الإشارة إليه بشكل متكرر لفترة زمنية قصيرة ولا يتم الوصول إليه مرة أخرى لفترة زمنية طويلة. بسبب سرعة الوصول إليه، يزداد عداده بشكل كبير على الرغم من أنه لن يُستخدم مرة أخرى لفترة زمنية. وهذا يجعل الكتل الأخرى التي قد يتم استخدامها بشكل متكرر أكثر عرضة للإزالة لمجرد الوصول إليها من خلال طريقة مختلفة. [2]
علاوة على ذلك، فإن العناصر الجديدة التي دخلت التخزين المؤقت تكون معرضة للإزالة مرة أخرى لأنها تبدأ بعداد منخفض، حتى لو تم استخدامها بشكل متكرر جدًا بعد ذلك. بسبب مشاكل كبيرة كهذه، فإن خوارزمية LFU غير شائعة إلى حد ما؛ بدلاً من ذلك، هناك أنظمة هجينة تستخدم مفاهيم LFU. [3]
مراجع
عدل- ^ Donghee Lee؛ Jongmoo Choi؛ Jong-Hun Kim؛ S.H. Noh؛ Sang Lyul Min؛ Yookun Cho؛ Chong Sang Kim (ديسمبر 2001). "LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policies". IEEE Transactions on Computers. ج. 50 ع. 12: 1352–1361. DOI:10.1109/TC.2001.970573. S2CID:2636466. مؤرشف من الأصل في 2024-08-15.
- ^ William Stallings (2012). Operating Systems: Internals and Design Principles (ط. 7th).
- ^ B.T. Zivkoz؛ A.J. Smith (1997). "Disk Caching in Large Database and Timeshared Systems". Proceedings Fifth International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. DOI:10.1109/MASCOT.1997.567612. مؤرشف من الأصل في 2024-07-12.