מחסנית קריאות
DrawLine, לאחר שהיא נקראה מתוך שגרה בשם DrawSquare, החלק העליון של מחסנית הקריאות יכול להראות כמודגם בתרשים זה.במדעי המחשב, מחסנית קריאות (באנגלית: call stack) היא מבנה נתונים מסוג מחסנית, המשמש לאחסון מידע אודות השגרות הפעילות של תוכנית מחשב. סוג זה של מחסנית נקרא גם execution stack (מחסנית ביצוע), control stack (מחסנית שליטה), run-time stack (מחסנית זמן ריצה) או machine stack (מחסנית מכונה), ובדרך כלל קוראים לה בקיצור פשוט "המחסנית" (the stack). למרות שתחזוקת מחסנית הקריאות חשובה לתפקודן התקין של מרבית התוכנות, בדרך כלל הפרטים שלה מוסתרים מהמתכנת והטיפול במחסנית מבוצע באופן אוטומטי בשפות תכנות עיליות.
מחסנית קריאות משרתת מספר מטרות קשורות, אבל הסיבה העיקרית לשימוש בה היא לצורך מעקב אחר הנקודה שאליה כל שגרה אמורה להחזיר את השליטה כאשר הביצוע שלה הסתיים. שגרה פעילה היא שגרה שנקראה אבל עדיין לא סיימה את הריצה שלה, שלאחריה השליטה אמורה להיות מועברת חזרה לנקודה שממנה נקראה השגרה. הפעלות כאלו של שגרות יכולות להיות מקוננות (קריאה לשגרה מתוך שגרה, כאשר קריאה רקורסיבית היא מקרה פרטי לכך), ולכן נעשה השימוש במבנה של מחסנית. לדוגמה, אם שגרה בשם DrawSquare (צייר ריבוע) קוראת לשגרה DrawLine (צייר קו) מארבעה מקומות שונים, השגרה DrawLine אמורה לדעת לאיזו נקודה לחזור בכל פעם שהביצוע שלה מסתיים. על מנת לעשות זאת, הכתובת בזיכרון יחד עם הוראת הקריאה – "כתובת החזרה" (return address), מתווספת על גבי המחסנית עם כל קריאה.
בנוסף, רוב שיטות הקריאה הרשמיות משתמשות במחסנית לצורכי העברת פרמטרים בין הקוד הקורא לפונקציה הנקראת.
תיאור
מאחר שמחסנית הקריאות בנויה כמחסנית, הקורא (מי שקרא לשגרה) דוחף (push) למחסנית את כתובת החזרה, והשגרה שנקראה, כאשר סיימה לרוץ, שולפת (pop) את כתובת החזרה מהמחסנית ומחזירה את השליטה לאותה כתובת. אם השגרה שנקראה קוראת לשגרה נוספת, היא תדחוף עוד כתובת חזרה על גבי מחסנית הקריאות, וכך הלאה - מידע מצטבר על המחסנית ומרוקן ממנה בהתאם למה שמכתיבה התוכנית. אם הכתיבות למחסנית מנצלות את כל שטח הזיכרון שהוקצה עבור מחסנית הקריאות, מתרחשת שגיאה שנקראת גלישת מחסנית (stack overflow), אשר בדרך כלל גורמת להתרסקות התוכנית. באנגלית, הוספת רשומה של שגרה למחסנית הקריאות לעיתים נקראת winding (ליפוף), ואילו הסרת רשומות נקראת unwinding.
בדרך כלל יש מחסנית קריאות אחת המשויכת לכל תוכנית רצה (או ליתר דיוק, לכל משימה (task) או תהליכון בתהליך), אך יכול להיות שמחסניות נוספות ייווצרו לצורך טיפול בסיגנלים או לריבוי משימות שיתופי. מכיוון שבהקשר זה בכל זאת תמיד יש רק מחסנית עיקרית אחת, ניתן לקרוא לה "המחסנית" (של ה-task).
בשפות תכנות עיליות, פרטי מחסנית הקריאות בדרך כלל מוסתרים מהמתכנת, אשר מקבל גישה רק לסט פונקציות מוגדרות מראש, ולא לזיכרון שעל המחסנית עצמה. זה נקרא אבסטרקציה. לעומת זאת, רוב שפות הסף דורשות מהמתכנת להיות מעורב בניהול המחסנית. פרטי המימוש של המחסנית בכל שפת תכנות תלויים בסוג המהדר, במערכת ההפעלה ובסט הפקודות הזמין.
שימושים
מחסנית קריאות טיפוסית משמשת לאחסון כתובת חזרה, משתנים מקומיים ופרמטרים, אשר יחד מכונים "מסגרת קריאה" (call frame). בסביבות שונות, מחסנית הקריאות יכולה לשמש יותר או פחות פונקציות. כפי שצוין למעלה, השימוש העיקרי במחסנית הקריאות הוא לצורך:
- אחסון כתובת החזרה
כאשר שגרה נקראת, המקום (הכתובת) של ההוראה שממנה תמשיך הריצה לאחר סיום השגרה צריך להישמר היכנשהו. לשימוש במחסנית לצורך שמירת כתובת החזרה ישנם יתרונות חשובים על פני האלטרנטיבות. אחד היתרונות הוא בכך שלכל משימה (task) יש מחסנית משלה, וכך השגרה יכולה להיות מרובת כניסות (reentrant), כלומר ניתן להפעיל אותה בו זמנית מתוך משימות שונות שעושות דברים שונים. יתרון נוסף הוא שרקורסיה נתמכת באופן אוטומטי. כאשר פונקציה קוראת לעצמה רקורסיבית, יש לשמור את כתובת החזרה עבור כל הפעלה של הפונקציה, כך שמאוחר יותר ניתן יהיה להשתמש בכתובת החזרה כדי לחזור מתוך הקריאה לפונקציה. היכולת הזאת מתאפשרת אוטומטית בשימוש במחסנית.
מחסנית קריאות עשויה לשרת פונקציות נוספות, כתלות בסוג שפת התכנות, מערכת ההפעלה וסביבת המכונה. ביניהן:
- אחסון נתונים מקומיים
לעיתים קרובות שגרות זקוקות לשטח בזיכרון לצורך אחסון הערכים של משתנים מקומיים – המשתנים אשר מוכרים רק במסגרת השגרה הפעילה ולא שומרים ערכים לאחר סיום הריצה של השגרה. בדרך כלל נוח להקצות שטח בזיכרון למטרה זו פשוט על ידי הזזת הקצה העליון של המחסנית על מנת לספק את השטח הנדרש. פעולה כזאת היא מהירה מאד בהשוואה להקצאת זיכרון על גבי ה-heap. כל הפעלה נפרדת של שגרה מקבלת שטח נפרד משלה במחסנית עבור המשתנים המקומיים.
- העברת פרמטרים
לעיתים קרובות שגרות דורשות שהקוד שקורא להן יספק ערכים לפרמטרים, ולעיתים קרובות השטח בזיכרון לצורך פרמטרים אלו מוקצה על גבי מחסנית הקריאות. בדרך כלל, אם ישנם רק כמה פרמטרים קטנים, יעשה שימוש באוגרי המעבד לצורך העברת הערכים, אבל אם מספר הפרמטרים גדול ואינו מאפשר לטפל בהם בצורה כזאת, יידרש מקום בזיכרון. מחסנית הקריאות פועלת היטב כמקום עבור פרמטרים אלו, בייחוד מאחר שכל קריאה לשגרה, שיכולה להכיל ערכים שונים עבור הפרמטרים, תקבל מקום נפרד עבור ערכים אלו על גבי מחסנית הקריאות.
- מחסנית הערכות (evaluation stack)
אופרנדים (ראו: אופרטור) עבור פעולות אריתמטיות או לוגיות בדרך כלל מאוחסנים באוגרים ושם מבוצעות עליהם הפעולות. עם זאת, ישנם מקרים בהם האופרנדים נערמים לעומק בלתי מוגבל, ובמקרה כזה האוגרים לא יספיקו (מצב הנקרא register spilling). המחסנית שמשמשת לאחסון אופרנדים כאלו, בדומה למחסנית המשמשת לחישוב בכתיב פולני הפוך, נקראת מחסנית הערכות (evaluation stack), והיא עשויה לתפוס מקום במחסנית הקריאות.
- מצביע למופע הנוכחי (this)
בחלק משפות התכנות מונחות-העצמים (לדוגמה, ++C), בזמן קריאה למתודות, המצביע ל-this מאוחסן במחסנית הקריאות ביחד עם הארגומנטים לפונקציות. המצביע ל-this מצביע למופע האובייקט לו שייכת המתודה הנקראת.
- אחסון מידע נוסף אודות מצבים
מלבד כתובת החזרה, בחלק מהסביבות יכול להיות צורך לשמור מידע אודות המצב של התוכנה או המכונה, אותו צריך יהיה לשחזר כאשר חוזרים משגרה. זה יכול להיות מידע אודות רמת הרשאות (privileges), טיפול בחריגות, מצב חישוב אריתמטי, וכדומה. במידת הצורך, אלה יכולים להיות מאוחסנים במחסנית הקריאות באופן דומה לאחסון כתובת החזרה.