איסוף זבל (מדעי המחשב)
איסוף זבל (באנגלית: Garbage collection) הוא תהליך שבו סביבת הריצה של תוכנית מחשב משחררת באופן אוטומטי זיכרון שהוקצה דינאמית ואין בו עוד צורך.
המנגנון הומצא ויושם לראשונה בשנת 1959 על ידי ג'ון מקארתי עבור שפת Lisp.[1] איסוף זבל נפוץ בשפות תכנות מונחות-עצמים מודרניות כגון Java ו-#C, וכן בשפות המורצות על ידי מפרש כמו Perl, פייתון, PHP ו-JavaScript. יש שפות כגון עדה ושפת D (ובמידה מסוימת גם Delphi) המאפשרות למתכנת לבחור אם להשתמש במנגנון זה או לנהל הקצאות ושחרור זיכרון באופן עצמאי.
בהקשר הנוכחי, "זבל" הוא כל מקטע זיכרון שהוקצה באופן דינמי ואין בו ולא יהיה בו שימוש נוסף בתוכנית. מצב בו זיכרון "זבל" לא משוחרר מכונה "דליפת זיכרון" (Memory leak) ועלול להביא למצב בו משאבי הזיכרון שהתוכנית משתמשת בהם הולכים וגדלים ובסופו של דבר אף לקריסה (הפסקת ריצה לא מתוכננת) של התוכנית.
איסוף זבל חוסך מהמתכנת את המעקב אחר זיכרון שהוקצה במהלך ריצת התוכנית ואת שחרורו באופן מפורש. באופן עקרוני, יש קושי עצום להגדיר שפת תכנות המכילה רפרנסים (או מצביעים) כך שתהיה בעלת טיפוסיות חזקה ובטוחה, אם היא הכוללת שחרור זיכרון מפורש (במקום איסוף זבל)[2].
חסרונו הבולט של המנגנון הוא תוספת מסוימת של תקורות בביצועי התוכנית בפועל, ובמיוחד התנהגות לא דטרמיניסטית של זמן הריצה באופן שאיננו ברור מקוד התוכנית, היבט משמעותי במיוחד עבור תוכניות זמן אמת. בנוסף, מנגנוני איסוף זבל לא מזהים דליפת זיכרון שנובעת מהחזקה של אובייקטים שאינם בשימוש בתוך מבני נתונים (כגון רשימה) שנמצאים בשימוש, ואינם יכולים למנוע דליפת זיכרון מסוג זה.
יישום איסוף אוטומטי בשפות תכנות
רוב שפות התכנות המודרניות כגון Java, Basica, Lisp, פייתון, C# (כחלק מכלל פלטפורמת ה-NET.), Ruby וג'וליה משחררות את המתכנת מניהול מפורש של שחרור הזיכרון שהוקצה, ומותירה את הניהול למנגנון איסוף זבל שמתבצע בזמן ריצה.
שפת C לא מגדירה איסוף זבל, ועל המתכנת מוטלת האחריות לשחרר באופן מפורש כל זיכרון שהוקצה. עם זאת, השפה לא אוכפת בזמן קומפילציה את ניהול הזיכרון. מסיבה זו, דליפות זיכרון הן בעיה חמורה ושכיחה ביותר בתכנות בשפת C, וישנן תוכנות מיוחדות שמטרתן לעזור לאתר דליפות זיכרון.
בשפת ++C, בדומה לשפת C, לא קיים איסוף זבל אוטומטי, אבל ניתן לדמות איסוף זבל אוטומטי באמצעות "מצביעים חכמים", אובייקטים שעוטפים מצביעים רגילים ומנהלים את איסוף הזבל של הזיכרון אליו הם מצביעים באופן אוטומטי (למשל באמצעות מניית התייחסויות). מנגנון זה פותר חלק מהבעיות הקשורות בדליפת זיכרון, אך לא מאפשר לטפל באופן אוטומטי בכל תבנית של ניהול זיכרון.
שפת Rust אוכפת בזמן קומפילציה, דרך מערכת הטיפוסים, ניהול חוקי של הזיכרון. בכך הופכת השפה את איסוף הזבל בזמן ריצה לטריוויאלי, ומשיגה יעילות יחד עם היעדר דליפות זיכרון. המחיר הוא מערכת טיפוסים מורכבת ולעיתים לא אינטואיטיבית, שדורשת השקעה משמעותית על מנת לקמפל תוכניות.
טכניקות איסוף זבל אוטומטי
קיימות שתי טכניקות עיקריות של איסוף זבל אוטומטי.
סימון ומחיקה
טכניקה אחת, הקרויה "סימון ומחיקה" (Mark and sweep). בשיטה זו, אחת לכמה זמן מתעורר תהליך שעובר על האובייקטים שנמצאים בשימוש כרגע (בשפות תכנות בדרך כלל מדובר באובייקטים סטטיים וגלובליים ואובייקטים במחסנית). התהליך רץ על כל ההצבעות שנמצאות בשימוש אל אובייקטים הנמצאים בזיכרון באזור הערימה (heap) שהוקצו דינמית, ומסמן את כל האובייקטים שעבר דרכם כאובייקטים בשימוש. לבסוף, כל האובייקטים שאינם מסומנים נמחקים.
היתרונות העיקריים של שיטה זו:
- עובד על כל סוג של מבנה נתונים
- אינו דורש הרבה זיכרון נוסף לצורך הפעלה
- אין תקורה של זמן על יצירה ומחיקת אובייקטים
החסרונות העיקריים של סימון ומחיקה:
- כאשר התהליך מתעורר, ביצועה של התוכנית מושהה עד שאיסוף הזבל מסתיים. השהיה זו יכולה להיות מורגשת כאשר ישנם הרבה אובייקטים בזיכרון. לא מתאים ליישומי זמן אמת.
- כאשר ישנה כמות גדולה מאוד של אובייקטים בזיכרון, התהליך יכול להיות מאוד בזבזני מבחינת זמן.
מניית התייחסויות
טכניקה נוספת הקרויה "מניית התייחסויות" (Reference counting) מבוססת על כך שלכל אובייקט יש מונה הסופר את מספר המצביעים שמתייחסים אליו. ברגע שמספר ההתייחסויות יורד ל-0, האובייקט מוחק את עצמו באופן אוטומטי.
היתרונות של שיטה זו:
- תהליך ניהול הזיכרון מתרחש באופן מיידי ואובייקטים שאין בהם צורך נמחקים ברגע שההתייחסות אליהם מוסרת
- אין צורך בהרצת תהליך המעכב את ריצת התוכנית
- יעיל יותר כאשר ישנו מספר רב של אובייקטים בזיכרון
- פשוטה למימוש.
החסרונות של שיטה זו:
- לא עובד נכון כאשר ישנה הצבעה מעגלית, כלומר אובייקט A מצביע על B ואובייקט B מצביע על A. ישנה דרך לתקן בעיה זו, אולם יש לכך עלות נוספת בביצועים.
- פחות יעיל מבחינת זיכרון בשל הצורך להחזיק מונה התייחסויות עבור כל אובייקט.
- יש צורך לשנות את ערכו של המונה בכל פעם שמוסיפים או מוחקים מצביע המתייחס לאותו האובייקט.
בשל פשטותה היא נמצאת בשימוש במספר רב של סביבות ריצה, כגון פרל[3], פייתון[4], PHP[5] ועוד.
איסוף זבל ב-.NET וב-Java
כאמור לעיל, מספר שפות משתמשות במנגנון איסוף זבל אוטומטי. המכונה הווירטואלית מחייבת שכל האובייקטים יוקצו בערימה המנוהלת (managed heap). המתכנת לא משחרר אובייקטים מהערימה, אלא הם משוחררים אוטומטית כאשר לאפליקציה אין עוד שימוש בהם. האלגוריתם שבו מתבצע איסוף הזבל ב-.NET הוא סימון ומחיקה.[6]
Finalization
אוסף הזבל מתמודד בהצלחה עם מעקב אחר אובייקטים שהאפליקציה יוצרת לצורך שחרורם, אך נכשל בהתמודדות עם משאבים בלתי מנוהלים, כגון חלון, חיבור לקובץ או לרשת. את המשאבים הללו יש לשחרר ידנית בסיום השימוש בהם. בפלטפורמת .NET ובשפת Java קיימת השיטה Object.Finalize, שיטה שאוסף הזבל מריץ על האובייקט כדי לנקות את המשאבים הבלתי מנוהלים של אותו אובייקט, לפני שהוא משחרר את הזיכרון של האובייקט. מאחר שהשיטה הבסיסית אינה עושה דבר, על המתכנת לדרוס אותה (override) אם יש צורך בשחרור משאבים פרטני. להבדיל מ-destructor, שיטת ה-Finalize נקראת כאשר אוסף הזבל מגיע לניקוי האובייקט, בעוד ה-destructor מתבצע מיידית כאשר האובייקט יוצא משימוש.
שיטה זו מעכבת את עבודתו של אוסף הזבל האוטומטי, שכן הוא יצטרך לעבור על האובייקט בשני "סיבובים" לפני שהאובייקט ישוחרר לחלוטין. כאשר אובייקט חדש, לו יש שיטת Finalize, מוקצה בערימה, מתווסף מצביע לאובייקט ב-Finalization queue (תור ה-Finalization). כאשר יש לשחרר את האובייקט, אוסף הזבל יחפש בתור מצביע לאותו אובייקט, ולאחר שיימצא, יעביר את המצביע לאובייקט אל תור אחר - Freachable queue - וטכנית האובייקט לא ייחשב זבל. בסיום שלב המחיקה (sweep), אוסף הזבל מריץ את שיטת ה-Finalize של כל אובייקט בתור ה-Freachable. בסיבוב הבא של אוסף הזבל, האובייקטים שהופעלה שיטת ה-Finalize שלהם יזוהו כזבל אמיתי, ולבסוף ישוחרר הזיכרון שהוקצה להם. לכן, מומלץ להשתמש בשיטת ה-Finalize רק בעת צורך, משום שהם גורמים לאובייקטים להשתחרר מהזיכרון מאוחר יותר, ובכך לבזבוז זיכרון: נדרשים שני סיבובים של אוסף הזבל על מנת לפנותם.
שיפור ביצועים
Weak Reference
מצביע חלש (Weak Reference) עוזר להוריד לחץ של אובייקטים גדולים על הערימה המנוהלת. כפי שצוין, אובייקט שיש לו מצביע רגיל (הנקרא מצביע חזק) לא ישוחרר על ידי אוסף הזבל, מכיוון שלאפליקציה יש גישה אליו. אך כאשר לאובייקט יש רק מצביעים חלשים, אוסף הזבל כן ישחרר את הזיכרון, אף על פי שעדיין קיים מצביע לאזור ההוא בזיכרון. לכן, כאשר התוכנה תנסה לגשת לאזור ההוא בעזרת אותם מצביעים חלשים, הניסיון ייכשל. אם קיימים מצביעים חזקים וחלשים לאובייקט מסוים הוא לא ישוחרר. אחד השימושים למצביעים חלשים הוא כאשר יש רצון לחסוך בזיכרון, בדרך כלל כשהתוכנה מתעסקת באובייקטים שתופסים מקום גדול בזיכרון, לדוגמה, מיפוי של דיסק קשיח בעזרת עץ - לכל אחד מהצמתים בעץ יהיה מצביע חלש. לפני גישה לכל אחד מהם תהיה בדיקה האם הוא שוחרר על ידי אוסף הזבל או לא, ובמידה שכן, הצומת ההוא בלבד ימופה. ההשלכה לדרך עבודה זו היא אמנם הורדת יעילות זמן הריצה של התוכנה, אך הקטנת הנפח שיתפוס בזיכרון.
דורות
אחד המאפיינים של אוסף הזבל האוטומטי שנועד באופן בלעדי לשיפור הביצועים הוא חלוקת האובייקטים בזיכרון לדורות. החלוקה לדורות מתבססת על שתי עובדות שנמצאו, באופן אמפירי, במגוון תוכנות ושפות:
- לאובייקטים חדשים יש נטייה "לחיות" זמן קצר.
- ככל שאובייקט "מבוגר" יותר, כך הוא ישרוד יותר זמן.
המשמעות של חלוקה לדורות היא שערימת הזיכרון מחולקת לדורות. לכל האובייקטים החדשים שמוקצים, מתווסף מצביע לערמה של הדור הראשון (דור 0). כאשר הערימה מתמלאת, יבוצע איסוף אוטומטי, וכל המצביעים לאובייקטים ששורדים בערימה זו, מועברים לערימה של הדור הבא (דור 1). משום שרוב האובייקטים שורדים זמן קצר, רק אחוז קטן מהם יעברו לדור הבא. לכן, נדרש מספר רב של איסופים על הערימה של דור 0 כדי שהערימה של דור 1 תעורר את ריצת האוסף עליה. באותו האופן גם מתנהל המעבר של מצביעים בין דור 1 ו-2, וכך הלאה.
לפיכך, חלוקת הערימה לדורות, וריצת האוסף בעיקר על הערימה הראשונה, מקטין בהרבה את זמן הריצה של אוסף הזבל האוטומטי, מכיוון שהוא לא נדרש לעבור על כל האובייקטים בכל הדורות, אלא רק על אחד מהם, והרי שההנחה היא שאובייקטים מבוגרים גם ישרדו את האיסוף הבא, אין, לכאורה, צורך לבדוק אותם.
ראו גם
הערות שוליים
- ^ ג'ון מקארתי, History Of Lisp, אוניברסיטת סטנפורד, 1979
- ^ Benjamin C. Pierce, Types and Programming Languages, pg. 158
- ^ באתר הרשמי של "פרל"
- ^ בתיעוד של שפת פייתון
- ^ באתר של שפת PHP
- ^ Garbage Collection and Performance באתר מיקרוסופט
