پشته تماس

یک پشته تماس یا پشته فراخوانی (به انگلیسی: call stack) در علوم رایانه، یک ساختمان داده پشته است که اطلاعاتی درباره زیرروال‌های فعال یک برنامه رایانه‌ای را ذخیره می‌کند. اگرچه نگهداری از پشته تماس برای عملکرد درست نرم‌افزار مهم است، اما جزییات آن به صورت نرمال «پنهان» است و در زبان‌های برنامه‌نویسی سطح بالا، خودکار انجام می‌شود. خیلی از مجموعه دستورالعمل‌های رایانه‌ای دستورهای خاصی را برای دستکاری پشته‌ها تهیه می‌بینند.

اکثر کامپایلرها برای فراخوانی و برگشت زیربرنامه فراخوانی پشته (call stack) را پیاده‌سازی می‌کنند. Call stack یا run-time stack یک پشته است که اطلاعاتی دربارهٔ زیربرنامه فعال یک برنامه را نگهداری می‌کند. زیربرنامه فعال زیربرنامه‌ای است که فراخوانی شده‌است اما هنوز اجرایش تمام نشده‌است.

وقتی زیربرنامه‌ای فراخوانی می‌شود، قبل از اینکه کنترل اجرای برنامه به آدرس زیربرنامه پرش کند آدرس دستورالعمل بعدی (دستورالعملی که درحافظه بعد از دستور فراخوانی قرار دارد) درجائی باید ذخیره شود که هنگام برگشت از زیربرنامه از آن استفاده می‌شود. این آدرس را آدرس برگشتی (return addresses) می‌نامند.

معماری که بر اساس پشته است آدرس برگشتی را به عنوان نقطه برگشت در پشته اضافه می‌شود. هر بار که زیربرنامه‌ای فراخوانی می‌شود آدرس برگشتی در پشته push می‌شود. هنگام برگشت از زیربرنامه آدرس برگشتی از پشته pop شده و کنترل برنامه به آن آدرس پرش می‌کند و اجرای برنامه از بعد از دستور فراخوانی ادامه پیدا می‌کند.

به دلیل استفاده از پشته یک زیربرنامه می‌تواند خودش یا زیربرنامه‌های دیگر را صدا بزند.

در زبان‌های سطح بالا فراخوانی پشته معمولاً از برنامه‌نویس مخفی است. در مقابل در زبان اسمبلی نیاز است خود برنامه‌نویس با پشته درگیر شود.

کاربرد پشته‌ها در فراخوانی توابع

هر وقت تابعی فراخوانی می‌شود یک رکورد فعالیت برای آن تابع ایجاد می‌گردد و محیط فعلی را برای آن تابع ذخیره می‌کند. رکورد فعالیت شامل اطلاعات زیر است:۱. پارامتر ها۲. اطلاعات حالت فراخوان،مثل محتویات ثبات‌ها و آدرس‌های برگشت۳. متغیرهای محلی۴. حافظه‌های موقت برای انجام محاسبات میانیچون ممکن است هر تابع، توابع دیگری را فراخوانی کند و اجرای خود آن تابع به تعویق افتد، رکورد فعالیت آن باید طوری ذخیره شود که وقتی تابع از سر گرفته می‌شود، بتوان به رکورد فعالیت آن دست یافت. ساختمان داده‌ای که رکوردهای فعالیت در آن ذخیره می‌شوند، باید رفتار LIFO (خروج به ترتیب عکس ورود) داشته باشد، زیرا اولین تابعی که خاتمه یابد، آخرین تابعی است که فراخوانی شده‌است و رکورد فعالیت آن باید زودتر از همه بازیابی شود.

از این‌رو پشته ساختمان داده مناسبی برای این کار است. چون این پشته در زمان اجرا دستکاری می‌شود، پشته زمان اجرا نام دارد. وقتی تابعی فراخوانی می‌شود، کارهای زیر انجام می‌گیرد:۱. یک کپی از رکورد فعالیت آن در پشته قرار می‌گیرد.۲. پارامترها ذخیره می‌شوند.۳. کنترل به آدرس شروع بدنه تابع منتقل می‌شود. بنابراین، رکورد فعالیت بالای پشتهٔ زمان اجرا، مربوط به تابع در حال اجرا است. وقتی تابعی خاتمه می‌یابد، یک عمل ()pop رکورد فعالیت این تابع را از پشته حذف می‌کند و رکورد فعالیت تابع قبلی، که این تابع را فراخوانی کرده‌است، در بالای پشته قرار می‌گیرد.....

محتویات

ذخیره آدرس برگشت

وقتی که رویه‌ای فراخوانی می‌شود، باید مکان (آدرس) دستورالعملی که رویه را فراخوانی کرده در جایی ذخیره شود تا بعد از برگشت تابع، اجرای برنامه از همان نقطه از سر گرفته شود. استفاده از یک پشته برای ذخیره کردن آدرس برگشت تابع مزایایی نسبت به دیگر روش‌ها دارد. یکی از مزیت‌ها این است که هر فرایندی پشته مخصوص به خود را دارد، در نتیجه رویه می‌تواند به صورت reentrant باشد و می‌تواند به شکل همزمان برای چندین فرایند که هر کدام کارهای مختلفی را انجام می‌دهند فعال باشد. مزیت دیگر این است که بازگشت به شکل خودکار پشتیبانی می‌شود. وقتی که تابعی خودش را به صورت بازگشتی فراخوانی می‌کند، به ازای هر بار فراخوانی تابع باید یک آدرس برگشت ذخیره شود تا بعداً بتوان از آن‌ها برای برگشتن از تابع استفاده کرد. این قابلیت به شکل خودکار توسط پشته فراهم می‌شود.

ذخیره‌سازی داده‌های محلی

یک رویه مکرراً به فضایی از حافظه احتیاج دارد تا مقادیر متغیرهای محلی خودش را ذخیره کند. متغیرهای محلی تنها برای همان تابع در دسترس هستند و توابع دیگر و حتی فراخوانی‌های دیگر از همان تابع نمی‌توانند به آن متغیرها دسترسی داشته باشند. وقتی که تابع برمی‌گردد، این مقادیر هم نابود می‌شوند و حفظ نمی‌شوند. به کمک پشته می‌توان به راحتی چنین حافظه‌ای را در دسترس تابع قرار داد. کافیست آدرس بالای پشته را به اندازه کافی جابجا کنیم تا فضای مورد نیاز برای تابع فراهم شود. سپس وقتی تابع برگشت، آدرس بالای پشته را به اندازه کافی پایین می‌آوریم. این روش نسبت به اختصاص دادن حافظه به روش هرمی آسان‌تر است. توجه داشته باشید که هر نمونه فعال از تابع فضای مخصوص به خودش را در پشته دارد.

ارسال پارامترها

در هنگام فراخوانی توابع، معمولاً تعدادی آرگومان به آن‌ها ارسال می‌شود که آن‌ها را باید در جایی ذخیره کرد تا تابع بتواند از آن‌ها استفاده کند. اگر تنها چند پارامتر کوچک وجود داشته باشد، از ثبات‌های پردازنده می‌توان برای ذخیره کردن این پارامترها استفاده کرد. اما اگر پارامترها بیشتر از چیزی باشد که بتوان آن‌ها را در ثبات‌ها قرار داد، باید از فضای موجود در حافظه برای ذخیره کردن آن‌ها استفاده کنیم. از پشته برنامه می‌توان برای ذخیره کردن این پارامترها استفاده کرد. از آنجا که معمولاً تابع هر بار با پارامترهای مختلفی فراخوانی می‌شود، هر فراخوانی، فضای مخصوص به خودش را در پشته برنامه خواهد داشت.

منابع

• جعفر نژاد قمی، مهندس عین الله. " ساختمان داده‌ها در ++c ". چاپ پنجم. تهران:نشر علوم رایانه، ۱۳۸۷.