Loading AI tools
من ويكيبيديا، الموسوعة الحرة
في علوم الكمبيوتر، مكدس الاستدعاءات (بالإنجليزية: call stack) هو مجموعة بنية البيانات التي تخزين معلومات حول النشطة الوظائف الفرعية ل برنامج كمبيوتر. يُعرف هذا النوع من المكدس أيضًا باسم مكدس التنفيذ ، أو مكدس البرامج ، أو مكدس التحكم ، أو مكدس وقت التشغيل ، أو مكدس الماكينة ، وغالبًا ما يتم اختصاره إلى «المكدس» فقط. على الرغم من أهمية صيانة مكدس الاستدعاءات للتشغيل السليم لمعظم البرامج، إلا أن التفاصيل عادةً ما تكون مخفية وتلقائية في لغات البرمجة عالية المستوى. توفر العديد من مجموعات تعليمات الكمبيوتر إرشادات خاصة للتعامل مع الحزم.
صنف فرعي من | |
---|---|
جزء من | |
جانب من جوانب | |
يستخدمه |
يتم استخدام مكدس الاستدعاءات لعدة أغراض ذات صلة، ولكن السبب الرئيسي لامتلاك واحد هو تتبع النقطة التي يجب أن يعيد كل روتين فرعي نشط التحكم إليها عند الانتهاء من التنفيذ. الروتين الفرعي نشط هو روتين تم استدعاؤه، ولكنه لم يكتمل بعد، وبعد ذلك يجب إعادة التحكم إلى نقطة الاستدعاء. يمكن أن تتداخل عمليات التنشيط هذه للروتينات الفرعية مع أي مستوى (تكراري كحالة خاصة)، ومن هنا تأتي بنية المكدس. على سبيل المثال، إذا قام روتين فرعي DrawSquare
باستدعاء روتين فرعي DrawLine
من أربعة أماكن مختلفة، DrawLine
أن يعرف DrawLine مكان العودة عند اكتمال تنفيذه. لإنجاز ذلك، يتم دفع العنوان الذي يتبع التعليمات التي DrawLine
إلى DrawLine ، عنوان المرسل ، إلى الجزء العلوي من مكدس المكالمات مع كل مكالمة.
نظرًا لأن مكدس المكالمات منظم ك مكدس، يقوم المتصل بدفع عنوان الإرجاع إلى المكدس، والروتين الفرعي المسمى، عندما ينتهي، يسحب أو ينبثق عنوان الإرجاع من مكدس المكالمات وينقل التحكم إلى هذا العنوان. إذا استدعى روتين فرعي يسمى روتينًا فرعيًا آخر، فسوف يدفع عنوان إرجاع آخر إلى مكدس المكالمات، وهكذا، مع تراكم المعلومات وتفكيكها كما يملي البرنامج. إذا استهلك الدفع كل المساحة المخصصة لمكدس الاستدعاءات، يحدث خطأ يسمى تجاوز سعة المكدس، مما يؤدي عمومًا إلى تعطل البرنامج. تسمى إضافة إدخال روتين فرعي إلى مكدس المكالمات أحيانًا «لف»؛ على العكس من ذلك، فإن إزالة الإدخالات هي «فك».
عادة ما يكون هناك مكدس استدعاء واحد مرتبط ببرنامج قيد التشغيل (أو بشكل أكثر دقة، مع كل مهمة أو سلسلة من العمليات)، على الرغم من أنه يمكن إنشاء مكدسات إضافية لمعالجة الإشارات أو تعدد المهام التعاوني (كما هو الحال مع setcontext). لأنه ليس هناك واحد فقط في هذا السياق أهمية، فإنه يمكن أن يشار إليها على أنها كومة (ضمنا، «المهمة»)؛ ومع ذلك، في لغة البرمجة فورت الوصول إلى كومة البيانات أو المعلمة كومة أكثر صراحة من مكدس الاستدعاءات ويشار إلى كومة
في لغات البرمجة عالية المستوى، عادةً ما تكون تفاصيل مكدس المكالمات مخفية عن المبرمج. يتم منحهم حق الوصول إلى مجموعة من الوظائف فقط، وليس الذاكرة الموجودة على المكدس نفسه. هذا مثال على التجريد. من ناحية أخرى، تتطلب معظم لغات التجميع من المبرمجين المشاركة في معالجة المكدس. تعتمد التفاصيل الفعلية للمكدس في لغة برمجة على المترجم ونظام التشغيل ومجموعة التعليمات البرمجية المتاحة.
كما هو مذكور أعلاه، فإن الغرض الأساسي من مكدس المكالمات هو تخزين عناوين الإرجاع . عندما يتم استدعاء روتين فرعي، يجب حفظ موقع (عنوان) التعليمات التي يمكن من خلالها استئناف روتين الاتصال لاحقًا في مكان ما. استخدام مكدس لحفظ عنوان المرسل له مزايا مهمة مقارنة باتفاقيات الاستدعاء(اصطلاح الاستدعاء) البديلة. الأول هو أن كل مهمة يمكن أن يكون لها مكدس خاص بها، وبالتالي يمكن أن يكون الروتين الفرعي آمنًا، أي أنه يمكن أن يكون نشطًا في وقت واحد لمهام مختلفة تقوم بأشياء مختلفة. فائدة أخرى هي أنه من خلال توفير reentrancy ، يتم دعم العودية تلقائيًا. عندما تستدعي إحدى الوظائف نفسها بشكل متكرر، يجب تخزين عنوان إرجاع لكل تنشيط للوظيفة بحيث يمكن استخدامه لاحقًا للعودة من تنشيط الوظيفة. توفر هياكل المكدس هذه الإمكانية تلقائيًا.
اعتمادًا على اللغة ونظام التشغيل وبيئة الجهاز، قد يخدم مكدس الاستدعاءات أغراضًا إضافية، بما في ذلك على سبيل المثال:
يتم استخدام مكدس الاستدعاءات النموذجي لعنوان الإرجاع والسكان المحليين والمعلمات (المعروفة باسم إطار الاتصال). في بعض البيئات، قد يكون هناك وظائف أكثر أو أقل مخصصة لمكدس الاستدعاءات. في لغة البرمجة الرابعة، على سبيل المثال، عادةً ما يتم تخزين عنوان المرسل، ومعلمات الحلقة المعدودة والفهارس، وربما المتغيرات المحلية في مكدس الاستدعاءات (والذي يُسمى في تلك البيئة مكدس الإرجاع)، على الرغم من أنه يمكن وضع أي بيانات مؤقتًا هناك باستخدام رمز معالجة مكدس الإرجاع الخاص طالما يتم احترام احتياجات المكالمات والإرجاع؛ يتم تخزين المعلمات عادة على كومة البيانات أو المعلمة كومة منفصلة، وعادة ما تسمى كومة في المصطلحات الرابع على الرغم من وجود مكدس الاستدعاءات منذ عادة ما يتم الوصول إليه بشكل أكثر وضوحا. تحتوي بعض (Forths) أيضًا على مكدس ثالث لمعلمات الفاصلة العائمة.
يتكون مكدس الاستدعاء من إطارات مكدسة (تسمى أيضًا سجلات التنشيط أو إطارات التنشيط). هذه هياكل بيانات تعتمد على الآلة وABI تحتوي على معلومات حالة الروتين الفرعي. يتوافق كل إطار مكدس مع استدعاء إجراء فرعي لم ينته بعد بالعودة. على سبيل المثال، إذا كان هناك روتين فرعي يسمى DrawLine
قيد التشغيل حاليًا، بعد أن تم استدعاؤه بواسطة روتين فرعي DrawSquare
، فقد يتم وضع الجزء العلوي من مكدس الاستدعاءات كما في الصورة المجاورة.
يمكن رسم مخطط مثل هذا في أي اتجاه طالما أن موضع القمة، وبالتالي اتجاه نمو المكدس، مفهوم. علاوة على ذلك، وبغض النظر عن ذلك، تختلف البنى فيما يتعلق بما إذا كانت مكدسات المكالمات تنمو باتجاه عناوين أعلى أو نحو عناوين أقل. منطق الرسم البياني مستقل عن اختيار العنونة.
إطار المكدس الموجود أعلى المكدس مخصص للإجراء المنفذ حاليًا. يشتمل إطار المكدس عادةً على العناصر التالية على الأقل (بترتيب الدفع):
DrawLine
، عنوان في DrawSquare
)؛ وعندما يمكن أن تختلف أحجام إطار المكدس، مثل بين وظائف مختلفة أو بين استدعاءات وظيفة معينة، فإن ظهور إطار خارج المكدس لا يشكل تناقصًا ثابتًا لمؤشر المكدس . عند إرجاع الدالة، تتم استعادة مؤشر المكدس بدلاً من ذلك إلى مؤشر الإطار ، وهي قيمة مؤشر المكدس قبل استدعاء الوظيفة مباشرةً. يحتوي كل إطار مكدس على مؤشر مكدس إلى أعلى الإطار أدناه مباشرة. مؤشر المكدس هو سجل متغير مشترك بين جميع الاستدعاءات. مؤشر الإطار لاستدعاء معين لوظيفة هو نسخة من مؤشر المكدس كما كان قبل استدعاء الوظيفة.[1]
يمكن تحديد مواقع جميع الحقول الأخرى في الإطار بالنسبة إلى الجزء العلوي من الإطار، كإزاحات سالبة لمؤشر المكدس، أو بالنسبة إلى الجزء العلوي من الإطار أدناه، كإزاحات موجبة لمؤشر الإطار. يجب تحديد موقع مؤشر الإطار نفسه كإزاحة سلبية لمؤشر المكدس.
في معظم الأنظمة، يحتوي إطار المكدس على حقل يحتوي على القيمة السابقة لسجل مؤشر الإطار، وهي القيمة التي كان يمتلكها أثناء تنفيذ المتصل. على سبيل المثال، سيكون لإطار المكدس الخاص بـ (DrawLine
) موقع ذاكرة يحتوي على قيمة مؤشر الإطار (DrawSquare)
. يتم حفظ القيمة عند الدخول إلى الروتين الفرعي واستعادتها عند العودة. إن وجود مثل هذا الحقل في موقع معروف في إطار المكدس يمكّن الكود من الوصول إلى كل إطار على التوالي أسفل إطار الروتين المنفذ حاليًا، ويسمح أيضًا للروتين باستعادة مؤشر الإطار بسهولة إلى إطار المتصل ، قبل أن يعود مباشرة.
تحتوي لغات البرمجة التي تدعم الإجراءات الفرعية المتداخلة أيضًا على حقل في إطار الاستدعاء يشير إلى إطار المكدس لأحدث تنشيط للإجراء الذي يغلف بشكل وثيق المستدعى، أي النطاق المباشر للمستدعى. يسمى هذا ارتباط الوصول أو الارتباط الثابت (لأنه يتتبع التداخل الثابت أثناء المكالمات الديناميكية والمتكررة) ويوفر للروتين (بالإضافة إلى أي إجراءات أخرى قد يستدعيها) الوصول إلى البيانات المحلية لإجراءاته المغلفة في كل تداخل مستوى. تخزن بعض البنيات أو المجمعات أو حالات التحسين ارتباطًا واحدًا لكل مستوى من مستويات التضمين (وليس فقط الإحاطة الفورية)، بحيث لا تضطر الإجراءات المتداخلة بشدة للوصول إلى البيانات الضحلة إلى اجتياز عدة روابط؛ غالبًا ما تسمى هذه الإستراتيجية «عرض».[2]
يمكن تحسين روابط الوصول بعيدًا عندما لا تصل وظيفة داخلية إلى أي بيانات محلية (غير ثابتة) في التغليف، كما هو الحال مع الوظائف البحتة التي تتواصل فقط عبر الوسائط وقيم الإرجاع، على سبيل المثال. تحتوي بعض أجهزة الكمبيوتر التاريخية، مثل أنظمة Burroughs الكبيرة، على «سجلات عرض» خاصة لدعم الوظائف المتداخلة، بينما يحتفظ المترجمون لمعظم الأجهزة الحديثة (مثل x86 في كل مكان) ببضع كلمات على المكدس للمؤشرات، حسب الحاجة.
لبعض الأغراض، يمكن اعتبار إطار المكدس لروتين فرعي وإطار المتصل به متداخلين، حيث يتكون التداخل من المنطقة التي يتم فيها تمرير المعلمات من المتصل إلى المستدعي. في بعض البيئات، يدفع المتصل كل وسيطة إلى المكدس، وبالتالي يوسع إطار المكدس، ثم يستدعي المستدعي. في البيئات الأخرى، يمتلك المتصل منطقة مخصصة مسبقًا في الجزء العلوي من إطار المكدس الخاص به للاحتفاظ بالمتغيرات التي يوفرها للعمليات الفرعية الأخرى التي يستدعيها. تسمى هذه المنطقة أحيانًا منطقة الوسائط الصادرة أو منطقة وسيلة الشرح . في ظل هذا النهج، يتم حساب حجم المنطقة بواسطة المترجم ليكون الأكبر الذي يحتاجه أي روتين فرعي يسمى.
عادةً ما يكون التلاعب بمكدس الاستدعاءات المطلوب في موقع استدعاء إجراء فرعي ضئيلاً (وهو أمر جيد حيث يمكن أن يكون هناك العديد من مواقع الاتصال لكل روتين فرعي ليتم استدعاؤه). يتم تقييم قيم الوسائط الفعلية في موقع الاستدعاء، نظرًا لأنها خاصة بمكالمة معينة، وإما يتم دفعها إلى المكدس أو وضعها في السجلات، كما هو محدد بواسطة اصطلاح الاستدعاء المستخدم. يتم بعد ذلك تنفيذ تعليمات الاستدعاء الفعلية، مثل «الفرع والرابط»، لنقل التحكم إلى رمز الروتين الفرعي الهدف.
في الإجراء الفرعي المسمى، عادةً ما يُطلق على الكود الأول الذي تم تنفيذه اسم مقدمة الروتين الفرعي، لأنه يقوم بالتدبير المنزلي الضروري قبل بدء الكود الخاص بعبارات الروتين.
بالنسبة إلى بنى مجموعة التعليمات حيث تضع التعليمات المستخدمة لاستدعاء روتين فرعي عنوان الإرجاع في السجل، بدلاً من دفعه إلى المكدس، ستحفظ المقدمة عادةً عنوان الإرجاع عن طريق دفع القيمة إلى مكدس الاستدعاءات، على الرغم من أنه إذا تم استدعاء لا يستدعي الروتين الفرعي أي إجراءات أخرى قد يترك القيمة في السجل. وبالمثل، قد يتم دفع مؤشر المكدس الحالي و / أو قيم مؤشر الإطار.
إذا تم استخدام مؤشرات الإطار ، فستقوم المقدمة عادةً بتعيين القيمة الجديدة لسجل مؤشر الإطار من مؤشر المكدس. يمكن بعد ذلك تخصيص مساحة على المكدس للمتغيرات المحلية عن طريق تغيير مؤشر المكدس بشكل تدريجي.
تسمح لغة البرمجة الرابعة باللف الواضح لمكدس الاستدعاءات (يسمى هناك «مكدس الإرجاع»).
عندما يكون روتين فرعي جاهزًا للعودة ، فإنه ينفذ خاتمة تبطل خطوات المقدمة. سيؤدي هذا عادةً إلى استعادة قيم السجل المحفوظة (مثل قيمة مؤشر الإطار) من إطار المكدس ، وإخراج إطار المكدس بالكامل من المكدس عن طريق تغيير قيمة مؤشر المكدس ، وأخيراً التفرع إلى التعليمات الموجودة في عنوان المرسل. في ظل العديد من اصطلاحات الاستدعاء ، تشتمل العناصر المنبثقة من المكدس بواسطة الخاتمة على قيم الوسيطة الأصلية ، وفي هذه الحالة لا توجد عادةً معالجات مكدس أخرى يجب أن يقوم بها المتصل. ومع ذلك ، مع بعض اصطلاحات الاستدعاء ، يكون المتصل مسؤولاً عن إزالة الوسيطات من المكدس بعد الإرجاع.
ستؤدي العودة من الوظيفة التي تم استدعاؤها إلى إخراج الإطار العلوي من المكدس ، وربما ترك قيمة مرتجعة. يُطلق على الإجراء الأكثر عمومية المتمثل في إخراج إطار واحد أو أكثر من المكدس لاستئناف التنفيذ في مكان آخر في البرنامج فك لف المكدس ويجب إجراؤه عند استخدام هياكل تحكم غير محلية ، مثل تلك المستخدمة في معالجة الاستثناءات. في هذه الحالة ، يحتوي إطار المكدس للدالة على إدخال واحد أو أكثر يحدد معالجات الاستثناءات. عند طرح استثناء ، يتم إلغاء المكدس حتى يتم العثور على معالج جاهز للتعامل مع (التقاط) نوع الاستثناء الذي تم طرحه.
تحتوي بعض اللغات على هياكل تحكم أخرى تتطلب فكًا عامًا. يسمح باسكال لبيان goto الشامل بنقل التحكم من دالة متداخلة إلى دالة خارجية تم استدعاؤها سابقًا. تتطلب هذه العملية إلغاء ارتباط المكدس ، وإزالة أكبر عدد ممكن من إطارات المكدس حسب الضرورة لاستعادة السياق المناسب لنقل التحكم إلى العبارة الهدف داخل وظيفة التضمين الخارجية. وبالمثل ، فإن لغة C لها setjmp
و longjmp
غير محلية. يسمح Common Lisp بالتحكم في ما يحدث عندما يتم unwind-protect
المكدس باستخدام عامل حماية خاص.
عند تطبيق استمرار، يتم فك المكدس (منطقيًا) ثم يتم إرجاعه باستخدام مكدس الاستمرارية. ليست هذه هي الطريقة الوحيدة لتنفيذ الاستمرارية ؛ على سبيل المثال ، باستخدام مكدسات متعددة وواضحة ، يمكن لتطبيق استمرار ببساطة تنشيط مكدسها ولف قيمة ليتم تمريرها. تسمح لغة برمجة النظام بتنفيذ thunks التعسفي في نقاط محددة عند «فك» أو «إعادة لف» مكدس التحكم عند استدعاء الاستمرارية.
يمكن أحيانًا فحص مكدس الاستدعاءات أثناء تشغيل البرنامج. اعتمادًا على كيفية كتابة البرنامج وتصنيفه ، يمكن استخدام المعلومات الموجودة في المكدس لتحديد القيم الوسيطة وتتبعات استدعاء الوظيفة. تم استخدام هذا لإنشاء اختبارات آلية دقيقة [3]، وفي حالات مثل Ruby و Smalltalk ، لتنفيذ عمليات مستمرة من الدرجة الأولى. على سبيل المثال ، يقوم مصحح الأخطاء GNU (GDB) بتنفيذ فحص تفاعلي لمكدس الاستدعاءات لبرنامج C قيد التشغيل ولكن متوقف مؤقتًا.[4]
يمكن أن يكون أخذ عينات من مكدس الاستدعاءات في الوقت العادي مفيدًا في تحديد أداء البرامج ، لأنه إذا ظهر مؤشر روتين فرعي على بيانات أخذ عينات مكدس الاستدعاءات عدة مرات ، فمن المحتمل أن يكون عنق الزجاجة ويجب فحصه بحثًا عن مشاكل الأداء.
في لغة ذات مؤشرات حرة أو يكتب مصفوفة غير محددة (مثل C)، فإن خلط بيانات تدفق التحكم الذي يؤثر على تنفيذ الكود (عناوين الإرجاع أو مؤشرات الإطار المحفوظة) وبيانات البرنامج البسيطة (المعلمات أو القيم المرتجعة)) في مكدس المكالمات يمثل مخاطرة أمنية ، وربما يمكن استغلالها من خلال فائض المخزن المؤقت للتكدس باعتباره النوع الأكثر شيوعًا من تجاوزات سعة المخزن المؤقت.
تتضمن إحدى هذه الهجمات ملء مخزن مؤقت واحد برمز تعسفي قابل للتنفيذ ، ثم تجاوز نفس المخزن المؤقت أو بعضه لاستبدال بعض عناوين الإرجاع بقيمة تشير مباشرةً إلى الكود القابل للتنفيذ. نتيجة لذلك ، عندما تعود الوظيفة ، يقوم الكمبيوتر بتنفيذ هذا الرمز. يمكن صد هذا النوع من الهجوم بسهولة باستخدام W ^ Xيمكن أن تنجح الهجمات المماثلة حتى مع تمكين حماية W ^ X ، بما في ذلك هجوم العودة إلى libc أو الهجمات القادمة من البرمجة الموجهة نحو الإرجاع . تم اقتراح عوامل تخفيف مختلفة ، مثل تخزين المصفوفات في موقع منفصل تمامًا عن مكدس الإرجاع ، كما هو الحال في لغة البرمجة الرابعة.[5]