بازیافت حافظه

در علوم رایانه بازیافت حافظه یا زباله‌روبی (به انگلیسی: Garbage collection) نوعی مدیریت حافظهٔ خودکار است. این حالت خاصی از مدیریت منابع است و منبع محدودی که مدیریت می‌شود، حافظه است. زباله‌روبی تلاشی برای بازیافت قطعات کوچک حافظه و ادغام آن‌ها است که این حافظه‌ها قبلاْ توسط اشیاء به کار گرفته شده‌اند، ولی دیگر مورد نیاز برنامه نیستند. تکنیک بازیافت حافظه توسط جان مک‌کارتی در حدود سال ۱۹۵۹ برای حل مشکلات لیسپ اختراع شده‌است.

شمایی کلی از چگونگی بازیافت حافظه

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

اصول بازیافت حافظه

اصول ابتدایی زباله‌روبی حاکی از این است که در یک برنامه، اشیایی را که در آینده قابل دسترسی نیستند، پیدا کرده و حافظهٔ تخصیص داده شده به آن‌ها را آزاد کنیم. بسیاری از زبان‌های برنامه‌نویسی به روش زباله‌روبی نیاز دارند، چه به عنوان بخشی از خصوصیات زبان برنامه‌نویسی (مانند جاوا، سی شارپ، گو، دی و بسیاری از زبان‌های اسکریپت‌نویسی) و چه به صورت مؤثر برای پیاده‌سازی‌های عملی مانند زبان صوری حساب لاندا. به چنین زبان‌هایی، زبان‌های زباله‌روبی می‌گویند. سایر زبان‌ها به گونه‌ای طراحی شده‌اند که مدیریت حافظهٔ آن‌ها به صورت دستی انجام می‌شود، اما پیاده‌سازی زباله‌روبی هم دارند مانند C و ++C.
برخی از زبان‌ها مانند Ada، Modula-3 و C++/CLI هر دو قابلیت آزادسازی دستی حافظه و زباله‌روبی را دارند و از دو هرم جداگانه برای نگهداری اشیائی که با زباله‌روب حذف می‌شوند و اشیائی که به صورت دستی آزاد می‌شوند؛ استفاده می‌کنند.

مزایا

بازیافت حافظه باعث می‌شود تا برنامه‌نویس دخالتی در مدیریت حافظه نداشته باشد، در نتیجه مشکلات برنامه‌نویسی زیر دیگر رخ نخواهند داد:

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

معایب

بازیافت حافظه معایبی مانند مصرف منابع اضافی، تأثیر بر عملکرد، ناسازگاری با مدیریت منابع دستی و توقف در اجرای برنامه دارد.
در فرایند زباله‌روبی منابع محاسباتی به منظور تصمیم‌گیری برای اینکه کدام حافظه‌ها باید حذف شوند، مصرف می‌شوند. هرچند ممکن است برنامه‌نویس از این اطلاعات مطلع باشد. درصورت مدیریت نکردن طول عمر اشیاء به صورت دستی در یک برنامه، ممکن است سربار محاسبات برای انجام فعالیت‌های زباله روبی منجر به کاهش عملکرد شود. مقاله‌ای کارشناسی شده این نتیجه را بیان می‌کند که بازیافت حافظه به حافظه‌ای معادل پنج برابر حالت عادی نیاز دارد تا به این سربار غلبه کند و عملکرد آن به نسبت سرعت مدیریت حافظه، آشکار می‌باشد. تعامل با اثرات سلسله مراتب حافظه می‌تواند این سربار محاسبات را در شرایطی که پیش‌بینی یا تشخیص آزادسازی حافظه در آزمایش‌های معمول سخت است، غیرقابل تحمل کند. به عنوان مثال شرکت اپل، زباله روب را با وجود تمام ویژگی‌های مطلوب آن به دلیل تأثیرات بر عملکرد سیستم، برای سیستم‌عامل آی‌اواس نپذیرفت.
زمان دقیقی که یک زباله از حافظه حذف می‌شود به دلیل توقف‌های کوتاهی که برای جابه‌جایی یا آزاد کردن حافظه انجام می‌شود، قابل پیش‌بینی نیست. زباله‌روب‌های افزایشی، هم‌زمانی و زمان واقعی با روش‌های متفاوتی به مشکلاتی از قبیل توقف‌ها در هنگام اجرای برنامه‌های :رایانش بی‌درنگ، پردازش تراکنش‌ها و برنامه‌های تعاملی رسیدگی می‌کنند.
در پیاده‌سازی زباله‌روب‌های امروزی سعی شده‌است که این توقف‌ها را با روش به حداکثر رساندن کارهایی که در پس زمینه اجرا می‌شوند، به حداقل برسانند. برای مثال با علامت‌گذاری نمونه‌های دست نیافتنی زباله هنگامی که برنامه در حال اجرا است، این کار صورت می‌گیرد.
زباله‌روب‌های غیر قطعی با مدیریت مبتنی بر RAII با منابع بدون زباله روب، ناسازگار هستند. به همین خاطر مدیریت روشن منابع دستی برای منابع بدون زباله‌روب و ترکیب‌های آن‌ها دارای خاصیت انتقالی می‌شوند. به این معنا که در یک سیستم زباله‌روبی غیر قطعی، اگر یک منبع یا یک شئ شبه منبع نیاز به مدیریت دستی منبع داشته باشد درحالی که این شئ به عنوان بخشی از یک شئ دیگر مورد استفاده قرار گرفته باشد، آنگاه شئ حاصل از ترکیب این اشیاء، خود یک شئ شبه منبع است که نیاز به مدیریت دستی حافظه دارد.

استراتژی‌ها

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

قابلیت استفاده

به‌طور کلی بیشتر زبان‌های برنامه‌نویسی سطح بالا، بازیافت حافظه را به عنوان ویژگی استاندارد دارا هستند. در برخی دیگر از زبان‌ها نیز می‌توان با استفاده از کتابخانه‌ها این ویژگی را اضافه کرد. مانند زباله‌روب Boehm در زبان‌های C و ++C. بیشتر زبان‌های برنامه‌نویسی تابعی مثل ML و Haskell و APL دارای ساختار زباله‌روب هستند. همچنین لیسپ نیز به عنوان اولین زبان برنامه‌نویسی تابعی و نیز اولین زبان با قابلیت بازیافت حافظه قابل توجه است. زبان‌های برنامه‌نویسی شئ‌گرا نیز معمولاً از زباله‌روب یکپارچه استفاده می‌کنند. هرچند ساختار آن برای Delphi و ++C متفاوت است.
محیط محدود
بازیافت حافظه معمولاً در سیستم‌های داخلی یا سیستم‌های زمان واقعی استفاده می‌شود؛ زیرا در این سیستم‌ها با توجه به محدود بودن منابع، نیاز شدید به کنترل استفاده از آن‌ها وجود دارد. با این حال زباله روب‌های سازگار با این محدودیت محیط نیز گسترش یافته‌اند. بدنۀ میکرو دات‌نت در ماکروسافت و سکوی جاوا (نسخهٔ میکرو)، سکوهای نرم‌افزاری زمان واقعی هستند که زباله‌روب دارند.
زباله‌روب دات نت، تخصیص حافظه را مدیریت کرده و وظیفهٔ آزادسازی حافظه برای برنامه‌ها را بر عهده دارد. هنگامی که شئ جدیدی ساخته می‌شود، زبان مشترک زمان اجرا، حافظه‌ای از هرم مدیریت به آن اختصاص می‌دهد و تا زمانی که فضای خالی و در دسترس وجود داشته باشد، این روند ادامه می‌یابد. اما به دلیل اینکه حافظه محدود است، این زباله‌روب باید مجموعه اعمالی به منظور آزادسازی حافظه انجام دهد. این زباله‌روب بر اساس تخصیص حافظه‌ها، بهترین زمان را برای آزادسازی حافظه محاسبه می‌کند. هنگامی که این زباله‌روب مجموعه‌ای از اعمال را اجرا می‌کند، اشیائی که دیگر توسط برنامه‌ها استفاده نمی‌شوند را پیدا و بررسی کرده و اعمال لازم برای بازیابی حافظه را انجام می‌دهد.
استفادهٔ زمان کامپایل
زباله‌روبی زمان کامپایل نوعی از تحلیل ایستا است که به حافظه اجازه می‌دهد با استفاده از ویژگی‌های شناخته شده در طول زمان کامپایل، اصلاح و دوباره مورد استفاده قرار گیرد. این روش زباله‌روبی در زبان برنامه‌نویسی مرکوری مورد مطالعه قرار گرفت. همچنین کاربردهای بیشتری از آن در سال ۲۰۱۱ و در معرفی شمارش مرجع خودکار ال‌ال‌وی‌ام در آی‌اواس و مک‌اواس دیده شد.
سیستم‌های زمان واقعی
امروزه زباله‌روب‌های افزایشی، هم‌روند و زمان واقعی مانند الگوریتم‌های بیکر و لیبرمن گسترش یافته‌اند. در الگوریتم بیکر این تخصیص در نصف هر یک از ناحیه‌های واحد حافظه صورت می‌گیرد. زمانی که نیمی از آن پر شود، بازیافت حافظه اجرا می‌شود. به این صورت که اشیاء زنده به قسمت دیگر منتقل می‌شوند و اشیاء باقی‌مانده به صورت ضمنی آزاد می‌شوند. برنامهٔ در حال اجرا هر بار بررسی می‌کند که هر شئ که به آن اشاره می‌شود در نیمهٔ درست باشد و در غیر این صورت آن را جابه‌جا می‌کند، در حالی که در پس زمینهٔ برنامه در حال یافتن تمام اشیاء است.
طرح ردیابی جمع‌آوری زباله بر اساس مشاهدات تجربی است که در آن بیشتر اشیاء جوان از بین می‌روند. در این طرح حداقل دو ناحیهٔ تخصیص دهی باقی می‌مانند که بر اساس سن اشیاء از هم جدا می‌شوند. اشیاء جدید در نسل جوان تولید می‌شوند که به‌طور منظم جمع‌آوری شده و زمانی که یک نسل پر باشد، اشیائی که همچنان از ناحیهٔ قدیمی به آن‌ها ارجاع داده می‌شود، به قدیمی‌ترین نسل بعدی منتقل می‌شوند. به ندرت یک بررسی کامل انجام می‌شود.
برخی از معماری‌های زبان‌های برنامه‌نویسی سطح بالا از پشتیبانی سخت‌افزاری برای بازیافت حافظهٔ زمان واقعی استفاده می‌کنند.
بیشتر پیاده‌سازی‌های زباله‌روب‌های زمان واقعی از ردیابی جمع‌آوری زباله استفاده می‌کنند. این زباله‌روب‌های زمان واقعی هنگامی که در یک سیستم عامل زمان واقعی استفاده می‌شوند با محدودیت‌های رایانش بی‌درنگ مواجه می‌شوند.

مطالعهٔ بیشتر

مدیریت حافظه

منابع

↑ "Recursive functions of symbolic expressions and their computation by machine, Part I". Portal.acm.org. Retrieved 29 March 2009.
↑ "Recursive functions of symbolic expressions and their computation by machine, Part I". Archived from the original on 4 October 2013. Retrieved 29 May 2009.
↑ http://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html
↑ Matthew Hertz; Emery D. Berger (2005). "Quantifying the Performance of Garbage Collection vs. Explicit Memory Management" (PDF). OOPSLA 2005. Archived from the original (PDF) on 6 July 2017. Retrieved 2015-03-15.
↑ "Developer Tools Kickoff — session 300" (PDF). WWDC 2011. Apple, inc. 2011-06-24. Retrieved 2015-03-27.
↑ https://msdn.microsoft.com/en-us/library/0xy59wtx(v=vs.110).aspx
↑ Lorenz Huelsbergen, Phil Winterbottom. "Very Concurrent Mark-&-Sweep Garbage Collection without Fine-Grain Synchronization". 1998.
↑ "GC FAQ".
↑ Henry Lieberman. A Real-Time Garbage Collector Based on the Lifetimes of Objects
↑ Baker, H.G. List processing in real time on a serial computer. Commun. ACM 21, 4 (April 1978) 280- 294. see also description
↑ McCloskey, Bacon, Cheng, Grove."Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors" بایگانی‌شده در ۸ اوت ۲۰۱۷ توسط Wayback Machine. 2008.

جستارهای وابسته

[1] "Recursive functions of symbolic expressions and their computation by machine, Part I". Portal.acm.org. Retrieved 29 March 2009.

[2] "Recursive functions of symbolic expressions and their computation by machine, Part I". Archived from the original on 4 October 2013. Retrieved 29 May 2009.

[3] ttp://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html

[4] Matthew Hertz; Emery D. Berger (2005). "Quantifying the Performance of Garbage Collection vs. Explicit Memory Management" (PDF). OOPSLA 2005. Archived from the original (PDF) on 6 July 2017. Retrieved 2015-03-15.

[wwdc2011-5] "Developer Tools Kickoff — session 300" (PDF). WWDC 2011. Apple, inc. 2011-06-24. Retrieved 2015-03-27.

[6] ttps://msdn.microsoft.com/en-us/library/0xy59wtx(v=vs.110).aspx

[7] Lorenz Huelsbergen, Phil Winterbottom. "Very Concurrent Mark-&-Sweep Garbage Collection without Fine-Grain Synchronization". 1998.

[8] "GC FAQ".

[lieberman-9] Henry Lieberman. A Real-Time Garbage Collector Based on the Lifetimes of Objects

[10] Baker, H.G. List processing in real time on a serial computer. Commun. ACM 21, 4 (April 1978) 280- 294. see also description

[11] McCloskey, Bacon, Cheng, Grove."Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors" بایگانی‌شده در ۸ اوت ۲۰۱۷ توسط Wayback Machine. 2008.