ويكيبيديا

تجاوز سعة المكدس

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

في البرمجيات، يحدث تجاوز سعة المكدس إذا تجاوز مؤشر مكدس الاستدعاء حدود المكدس . قد يتكون مكدس الاستدعاءات من كمية محدودة من مساحة العناوين ، والتي يتم تحديدها غالبًا عند بدء تشغيل البرنامج. يعتمد حجم مكدس الاستدعاءات على العديد من العوامل، بما في ذلك لغة البرمجة، بنية الجهاز، تعدد الخيوط (multi-threading)، وكمية الذاكرة المتاحة. عندما يحاول برنامج استخدام مساحة أكبر مما هو متاح في مكدس الاستدعاءات (أي عندما يحاول الوصول إلى ذاكرة تتجاوز حدود مكدس الاستدعاءات، وهو ما يعتبر في أساسًا تجاوز سعة المخزن المؤقت "buffer overflow")، يقال إن المكدس قد تجاوز حدوده، و عادة ما يؤدي عادةً إلى تعطل البرنامج. [1]

الأسباب

عدل

تكرار لانهائي

عدل

السبب الأكثر شيوعًا لتجاوز سعة المكدس هو التكرار العميق للغاية أو اللانهائي، حيث تستدعي الدالة نفسها مرات عديدة لدرجة أن المساحة المطلوبة لتخزين المتغيرات والمعلومات المرتبطة بكل استدعاء تصبح أكبر مما يمكن أن يستوعبه المكدس. [2]

مثال على التكرار اللانهائي في لغة C.

int foo() 
{
     return foo();
}

عند استدعاء الدالة foo، تستمر في استدعاء نفسها، مما يؤدي إلى تخصيص مساحة إضافية على المكدس في كل مرة، حتى يتجاوز المكدس حدوده مما يؤدي إلى خطأ التجزئة (segmentation fault). [2] ومع ذلك، فإن بعض المترجمات (compilers) تقوم بتنفيذ تحسين استدعاء الذيل (tail-call optimization) ، مما يسمح بالتكرار اللانهائي من نوع معين - التكرار الذيلي tail recursion) - ليحدث دون تجاوز سعة المكدس. يعمل هذا لأن استدعاءات التكرار الذيلي لا تشغل مساحة إضافية على لمكدس. [3]

بعض خيارات مترجم C تمكن تحسين استدعاء الذيل بشكل فعال؛ على سبيل المثال، عند ترجمة البرنامج البسيط المذكور أعلاه باستخدام gcc مع الخيار -O1 إلى حدوث خطأ تجزئة (segmentation fault)، ولكن ليس عند استخدام -O2 أو -O3 ، حيث أن هذه المستويات من التحسين تتضمن خيار المترجم -foptimize-sibling-calls . [4] لغات الأخرى، مثل سكيم ، تشترط أن تتضمن جميع تنفيذاتها التكرار الذيلي كجزء من معيار اللغة. [5]

التكرار العميق جدًا

عدل

يمكن إصلاح دالة تكرارية تنتهي نظريًا ولكنها تتسبب في تجاوز مخزن مكدس الاستدعاءات في التطبيق العملي عن طريق تحويل التكرار إلى حلقة (loop) وتخزين معاملات الدالة في مكدس صريح (بدلاً من الاستخدام الضمني لمكدس الاستدعاءات). هذا دائما ممكن لأن فئة الدوال التكرارية البدائية (primitive recursive functions) تعادل فئة الدوال القابلة للحساب باستخدام LOOP. إليك مثالًا في هذا الكود الزائف المشابه لـ C++ : 

void function (argument) 
{
  if (condition)
    function (argument.next);

}

stack.push(argument);
while (!stack.empty())
{
  argument = stack.pop();
  if (condition)
    stack.push(argument.next);
}

يمكن دائمًا تحويل الدالة التكرارية البدائية مثل تلك الموجودة على الجانب الأيمن إلى حلقة مثل تلك الموجودة على الجانب الأيسر.

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

int pow(int base, int exp) {
    if (exp > 0)
        return base * pow(base, exp - 1);
    else
        return 1;
}

int pow(int base, int exp) {
    return pow_accum(base, exp, 1);
}

int pow_accum(int base, int exp, int accum) {
    if (exp > 0)
        return pow_accum(base, exp - 1, accum * base);
    else
        return accum;
}

كلتا الدالتين pow(base, exp) تحسبان نفس النتيجة، لكن الدالة على اليسار معرضة لتجاوز المكدس لأن تحسين استدعاء الذيل (tail-call optimization) غير ممكن لهذه الدالة. أثناء التنفيذ، سيبدو مكدس الاستدعاءات الخاص بهاتين الدالتين كما يلي: 

pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625

pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625

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

متغيرات المكدس الكبيرة جدًا

عدل

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

مثال على متغير مكدس كبير جدًا في C :

int foo() 
{
     double x[1048576];
}

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

البيئة المقيدة

عدل

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

انظر أيضا

عدل

مراجع

عدل
  1. ^ Burley، James Craig (1 يونيو 1991). "Using and Porting GNU Fortran". مؤرشف من الأصل في 2012-02-06.
  2. ^ ا ب What is the difference between a segmentation fault and a stack overflow? نسخة محفوظة 2021-09-13 على موقع واي باك مشين. at Stack Overflow
  3. ^ "An Introduction to Scheme and its Implementation". 19 فبراير 1997. مؤرشف من الأصل في 2007-08-10.
  4. ^ "Using the GNU Compiler Collection (GCC): Optimize Options". مؤرشف من الأصل في 2017-08-20. اطلع عليه بتاريخ 2017-08-20.
  5. ^ Richard Kelsey؛ William Clinger؛ Jonathan Rees؛ وآخرون (أغسطس 1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation. ج. 11 ع. 1: 7–105. DOI:10.1023/A:1010051815785. S2CID:14069423. مؤرشف من الأصل في 2007-01-05. اطلع عليه بتاريخ 2012-08-09.
  6. ^ Feldman، Howard (23 نوفمبر 2005). "Modern Memory Management, Part 2". مؤرشف من الأصل في 2012-09-20. اطلع عليه بتاريخ 2007-08-14.
  7. ^ "Kernel Programming Guide: Performance and Stability Tips". Apple Inc. 2 مايو 2014. مؤرشف من الأصل في 2014-05-03. اطلع عليه بتاريخ 2014-05-02.

روابط خارجية

عدل
مجلوبة من «https://ar.wikipedia.org/wiki/تجاوز_سعة_المكدس»