גלישת מחסנית

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

גלישת מחסניתאנגלית: stack overflow) היא שגיאת תוכנה המתרחשת כאשר מנצלים יותר מדי זיכרון על מחסנית הקריאות. מחסנית הקריאות מכילה כמות מוגבלת של זיכרון, הנקבעת בדרך כלל בתחילת הריצה של התוכנית. גודל מחסנית הקריאות תלוי בגורמים רבים, ביניהם שפת התכנות, ארכיטקטורת המכונה, ריבוי תהליכונים (multithreading), וכמות הזיכרון הפנוי. כאשר תוכנה מנסה להשתמש ביותר מקום מאשר זמין על גבי מחסנית הקריאות (כלומר כאשר היא מנסה לגשת לזיכרון אשר מעבר לגבולות מחסנית הקריאות, מה שבעצם גורם לגלישת חוצץ (buffer overflow)), נאמר על המחסנית שהיא "עולה על גדותיה" (overflow), מה שבדרך כלל גורם להתרסקות התוכנה.

StackOverflow הוא גם שמו של אתר אינטרנט פופולרי לשאלות ותשובות בנושא תכנות. שם האתר נבחר בהצבעת גולשים.

רקורסיה אינסופית או עמוקה מדי

רקורסיה אינסופית

הגורם הנפוץ ביותר לגלישת מחסנית היא רקורסיה אינסופית או עמוקה מדי. דוגמה לרקורסיה אינסופית בשפת C:

int foo()
{
 return foo();
}

כאשר קוראים לפונקציה foo, היא ממשיכה לקרוא לעצמה תוך ניצול מקום על מחסנית הקריאות עם כל קריאה, עד שהמחסנית "גולשת", מה שמביא לשגיאת segmentation fault.

שפות תכנות כמו שפת Scheme, אשר מממשות אופטימיזציות לקריאות זנב (tail-call) מאפשרות סוג ספציפי של רקורסיה אינסופית הנקראת רקורסיית זנב, מבלי שתתרחש גלישת מחסנית. זה מתאפשר כיוון שקריאות של רקורסיית זנב אינן תופסות מקום נוסף על המחסנית.

רקורסיה עמוקה מאד

פונקציה רקורסיבית שתאורטית אמורה לעצור בשלב מסוים, אבל למעשה גורמת לגלישת חוצץ במחסנית הקריאות, ניתנת לתיקון על ידי החלפת הרקורסיה בלולאה ואחסון הארגומנטים לפונקציה במחסנית. זה תמיד אפשרי בגלל שקבוצת הפונקציות הפרימיטיביות רקורסיביות שקולה לקבוצת פונקציות הלולאה החישוביות.

בתור דוגמה נביט על הפסאודו קוד הבא בתחביר דמוי-++C:

תמיד ניתן להפוך פונקציה פרימיטיבית רקורסיבית כמו הפונקציה שמצד שמאל ללולאה כמו בצד ימין.

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

 if (condition)
 function (argument.next);

}

משתני מחסנית גדולים מאד

גורם משמעותי נוסף לגלישת מחסנית הוא ניסיון להקצות יותר זיכרון על מחסנית הקריאות מאשר היא יכולה להכיל. לדוגמה, זה יכול לקרות כאשר יוצרים מערכים מקומיים גדולים מדי. מסיבה זו, יש הממליצים שמערכים שגודלם הוא יותר מכמה קילו-בייט יוקצו דינמית ולא כמשתנים מקומיים.

דוגמה בשפת C למשתנה מחסנית גדול מאד (מערך מטיפוס double בגודל מיליון):

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

הצהרה על מערך כזה צורכת 8 מגה-בייט של נתונים (בהנחה שהגודל של כל double הוא 8 בייט); אם מחסנית הקריאות לא מכילה כמות כזאת של זיכרון פנוי (בהתאם לקבוע בפרמטרים ליצירת תהליכונים או המגבלות של מערכת ההפעלה), תתרחש גלישה מחסנית.

הסיכוי לגלישת מחסנית גובר עם כל דבר שמקטין את הגודל האפקטיבי של מחסנית הקריאות של תוכנית מסוימת. לדוגמה, יכולה להיות תוכנית שכאשר היא מורצת על תהליכון אחד היא תעבוד באופן תקין, אבל ברגע שיאופשר ריבוי תהליכונים התוכנית תתרסק. הסיבה לכך היא שבמרבית התוכנות מרובות התהליכונים יש פחות שטח על המחסנית עבור כל תהליכון מאשר בתוכנית שאינה תומכת בריבוי תהליכונים. באופן דומה, ההמלצה לאנשים שאינם מנוסים בפיתוח תוכנה לליבה היא להימנע משימוש באלגוריתמים רקורסיביים או חוצצים גדולים על המחסנית.

ראו גם