איסוף זבל

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

איסוף זבל (באנגלית: Garbage collection) הוא תהליך שבו סביבת הריצה של תוכנית מחשב מנקה מהזיכרון את האובייקטים שאין בהם עוד צורך.

המנגנון הומצא ויושם לראשונה בשנת 1959 על ידי ג'ון מקארתי עבור שפת Lisp.‏[1] איסוף זבל נפוץ בשפות תכנות מונחות-עצמים מודרניות כגון Java ו-#C‏, וכן בשפות המורצות על ידי מפרש כמו Perl, ‏פייתון, ‏PHP ו-JavaScript. יש שפות כגון עדה ושפת D (ובמידה מסוימת גם Delphi) המאפשרות למתכנת לבחור אם להשתמש במנגנון זה או לנהל הקצאות ושחרור זיכרון באופן עצמאי. התקן החדש של שפת ++C,‏ C++11, כולל תמיכה מוגבלת באיסוף זבל.

בהקשר הנוכחי, "זבל" הוא אובייקט שהזיכרון אותו הוא תופס הוקצה באופן דינמי, אך לא ניתן להתייחס אליו דרך אף מזהה הנגיש בתוכנית, ולכן לא ניתן להגיע אליו. מצב בו חלק מאותם אובייקטים שאין בהם צורך לא נמחקים מכונה "דליפת זיכרון" (Memory leak) ועלול להביא למצב בו משאבי הזיכרון שהתוכנית משתמשת בהם הולכים וגדלים ובסופו של דבר אף לקריסה (הפסקת ריצה) של התוכנית.

איסוף זבל חוסך מן המתכנת את המעקב אחר אובייקטים להם הקצה זיכרון במהלך התוכנית ואת הצורך לשחרר את הזיכרון בצורה תקינה עם סיום השימוש בהם. כמו כן מונע שגיאות זמן ריצה הנובעות מניסיון לשחרר זיכרון שלא הוקצה. באופן עקרוני, יש קושי עצום להגדיר שפת תכנות המכילה רפרנסים (או מצביעים) כך שתהיה בעלת טיפוסיות חזקה ובטוחה, אם היא הכוללת שחרור זיכרון מפורש (במקום איסוף זבל)‏[2].

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

יישום איסוף אוטומטי בשפות תכנות[עריכת קוד מקור | עריכה]

במספר שפות תכנות כגון Java‏, Basica‏, Lisp ו-C#‏ (כחלק מכלל פלטפורמת ה-‎.NET) מתנהל איסוף הזבל באופן אוטומטי.

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

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

טכניקות איסוף זבל אוטומטי[עריכת קוד מקור | עריכה]

קיימות שתי טכניקות עיקריות של איסוף זבל אוטומטי.

סימון ומחיקה[עריכת קוד מקור | עריכה]

טכניקה אחת, הקרויה "סימון ומחיקה" (Mark and sweep). בשיטה זו, אחת לכמה זמן מתעורר תהליך שעובר על האובייקטים שנמצאים בשימוש כרגע (בשפות תכנות בדרך כלל מדובר באובייקטים סטטיים וגלובליים ואובייקטים במחסנית). התהליך רץ על כל ההצבעות מהם אל אובייקטים הנמצאים בזיכרון באזור הערימה (heap) המכיל אובייקטים שהוקצו דינמית, ומסמן את כל האובייקטים שעבר דרכם כאובייקטים בשימוש. לבסוף, כל האובייקטים שאינם מסומנים נמחקים.

היתרונות העיקריים של שיטה זו:

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

החסרונות העיקריים של סימון ומחיקה:

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

מניית התייחסויות[עריכת קוד מקור | עריכה]

טכניקה נוספת הקרויה "מניית התייחסויות" (Reference counting) מבוססת על כך שלכל אובייקט יש מונה הסופר את מספר המצביעים שמתייחסים אליו. ברגע שמספר ההתייחסויות יורד ל-0, האובייקט מוחק את עצמו באופן אוטומטי.

היתרונות של שיטה זו:

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

החסרונות של שיטה זו:

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

בשל פשטותה היא נמצאת בשימוש במספר רב של שפות, כגון המימושים המקובלים ל-LISP, פרל, פייתון, PHP ועוד.[דרוש מקור]

איסוף זבל ב-‎.NET וב-Java[עריכת קוד מקור | עריכה]

כאמור לעיל, מספר שפות משתמשות במנגנון איסוף זבל אוטומטי. המכונה הווירטואלית מחייבת שכל האובייקטים יוקצו בערימה המנוהלת (managed heap). המתכנת לא משחרר אובייקטים מהערימה, אלא הם משוחררים אוטומטית כאשר לאפליקציה אין עוד שימוש בהם. האלגוריתם שבו מתבצע איסוף הזבל ב-‎.NET הוא סימון ומחיקה.[דרוש מקור]

Finalization[עריכת קוד מקור | עריכה]

אוסף הזבל מתמודד בהצלחה עם מעקב אחר אובייקטים שהאפליקציה יוצרת לצורך שחרורם, אך נכשל בהתמודדות עם משאבים בלתי מנוהלים, כגון חלון, חיבור לקובץ או לרשת. את המשאבים הללו יש לשחרר ידנית בסיום השימוש בהם. בפלטפורמת .NET ובשפת Java קיימת השיטה Object.Finalize, שיטה שאוסף הזבל מריץ על האובייקט כדי לנקות את המשאבים הבלתי מנוהלים של אותו אובייקט, לפני שהוא משחרר את הזיכרון של האובייקט. מאחר שהשיטה הבסיסית אינה עושה דבר, על המתכנת לדרוס אותה (override) אם יש צורך בשחרור משאבים פרטני. להבדיל מ-destructor, שיטת ה-Finalize נקראת כאשר אוסף הזבל מגיע לניקוי האובייקט, בעוד ה-destructor מתבצע מיידית כאשר האובייקט יוצא משימוש.

השיטה זו מעכבת את עבודתו של אוסף הזבל האוטומטי, שכן הוא יצטרך לעבור על האובייקט בשני "סיבובים" לפני שהאובייקט ישוחרר לחלוטין. כאשר אובייקט חדש, לו יש שיטת Finalize, מוקצה בערימה, מתווסף מצביע לאובייקט ב-Finalization queue (תור ה-Finalization). כאשר יש לשחרר את האובייקט, אוסף הזבל יחפש בתור מצביע לאותו אובייקט, ולאחר שיימצא, יעביר את המצביע לאובייקט אל תור אחר - Freachable queue - וטכנית האובייקט לא ייחשב זבל. בסיום שלב המחיקה (sweep), אוסף הזבל מריץ את שיטת ה-Finalize של כל אובייקט בתור ה-Freachable. בסיבוב הבא של אוסף הזבל, האובייקטים שהופעלה שיטת ה-Finalize שלהם יזוהו כזבל אמיתי, ולבסוף ישוחרר הזיכרון שהוקצה להם. לכן, מומלץ להשתמש בשיטת ה-Finalize רק בעת צורך, משום שהם גורמים לאובייקטים להשתחרר מהזיכרון מאוחר יותר, ובכך לבזבוז זיכרון: נדרשים שני סיבובים של אוסף הזבל על מנת לפנותם.

שיפור ביצועים[עריכת קוד מקור | עריכה]

Weak Reference[עריכת קוד מקור | עריכה]

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

דורות[עריכת קוד מקור | עריכה]

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

  1. לאובייקטים חדשים יש נטייה "לחיות" זמן קצר.
  2. ככל שאובייקט "מבוגר" יותר, כך הוא ישרוד יותר זמן.

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

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ג'ון מקארתי, History Of Lisp, אוניברסיטת סטנפורד, 1979
  2. ^ Benjamin C. Pierce, Types and Programming Languages, pg. 158