پشت صحنه garbage collector در زبان‌های برنامه‌نویسی

داشتم یک مطلبی می‌خوندم که دیدم درمورد garbage collector اطلاعات زیاد دقیقی ندارم، به خاطر همین گفتم برم ببینم پشت صحنه چه خبراست و زبان‌های برنامه‌نویسی چطوری دارند، این موضوع را مدیریت می‌کنند. چیزهای خوبی را یادگرفتم و امیدوارم بتونم بعضی از این موارد را منتقل کنم.نکته: تلاش می‌کنم که متن را به صورت محاوره ننویسم ولی احتمالا حواسم نباشه و جملاتی از متن به صورت محاوره باشه. پیشاپیش پوزش بابت این ناهمگونی. :)مقدمهاین مطلب برای آشنایی با garbage collectorهاست. اینکه چطوری کار می‌کنند؟ چه الگوریتم‌ها وجود دارد؟ چه رویکردهایی مورد استفاده‌ست و کلا چیزهایی از این قبیل. اما از اونجایی که برای درک بهتر موضوع باید با برخی موارد آشنا باشیم، به خاطر همین یک مقدمه خیلی مختصری را داریم. بعد به سراغ اصل موضوع یعنی garbage collectorها می‌رویم و عمیق‌تر بررسی‌شون می‌کنیم.سعی می‌کنم طی چند روز آینده یک پست جداگانه درمورد garbage collector تو پایتون هم داشته باشیم.اجرای برنامه‌هابرنامه‌ها به هنگام اجرا در حافظه باگذاری(load) می‌شوند. قبل‌ترها اینطوری بود یک تکه از حافظه جدا و به برنامه اختصاص داده می‌شد تا در اون برنامه بارگذاری بشود و تمام! برنامه‌ها هم هر جوری دوست داشتند رفتار می‌کردند(ملق می‌زدند، از این‌ور به اون‌ور، اون‌ور به این‌ور و خلاصه شلم شوربایی بود)! اما این کار باعث یک سری مشکلات می‌شد. مشکلاتی مثل مشکلات امنیتی! چطوری؟ چون همه به همه‌ی خانه‌های حافظه دسترسی داشتند و هیچ کنترل و نظارتی نبود، در نتیجه امکان تغییر محتوای خانه‌ها وجود داشت! یک برنامه مخرب خیلی راحت می‌تونست به خراب‌کاری در سیستم بپردازد. این مشکلات باعث تغییر این رویکرد و پدیدار شدن، بخش‌بندی و جداسازی شد. بخش‌هایی مثل بخش کد، بخش دیتا و ... که کنترل هم می‌شدند. به دلیل اینکه مطلب طولانی نشه این بخش‌ها را توضیح نمی‌دهیم(اگر علاقه‌مند هستید این لینک می‌تواند کمک کننده باشد). به طور خلاصه عکس پایین این بخش‌ها را نشان می‌دهد.https://en.wikipedia.org/wiki/Data_segment با توجه به موضوع این مطلب(garbage collector)، در بین این بخش‌ها ما به heap علاقه‌مندیم. دلیل آن هم این است که به طور کلی garbage collectorها در بخش Heap اجرا می‌شوند. توصیه می‌کنم اگر با heap و stack آشنا نیستید، قبل یا بعد از این مطلب حتما یک مطالعه‌ای درباره آن‌ها داشته ‌‌‌‌‌‌‌باشید(حتی به صورت خیلی خلاصه وار. منم آخر سر یک لینک میزارم)، چون هم درک بهتر و عمیق‌تری از برنامه‌نویسی بدست می‌آورید و هم برخی از رفتار‌های زبان‌های برنامه‌نویسی براتون مملوس‌تر می‌شود.مدیریت این بخش heap همیشه از چالش‌هایی بوده که طراحان زبان‌های برنامه‌نویسی باهاش مواجه بودند و هستند. پایه‌ای‌ترین سوالی که همیشه مطرحه اینه که آيا این کار باید توسط خود برنامه‌نویس صورت بگیرد؟ یا خودِ زبانِ برنامه‌نویسی باید قابلیتی را برای آن ارائه کند؟ به عبارت دیگر اصلا یک زبان برنامه‌نویسی باید garbage collector داشته باشد یا نه؟ این مطلب برای این جواب دادن به این سوال نیست! چون این سوال یک جواب مشخص و به اصطلاح صفر و یکی ندارد که بتوان با قاطعیت برای همه یک نسخه واحد پیچید و تامام! اما شناخت جنبه‌هایی از این موضوع، به ما کمک می‌کند تا دید بهتری داشته باشیم.در رابطه با سوال پاراگراف قبل(اینکه مدیریت heap چگونه باشد)،‌ دو تا رویکرد وجود دارد که مثل همیشه هر کدوم از این رویکردها مزایا و معایبی را دارند. در ادامه مطلب یک اشاره مختصر به این مزایا و معایب خواهیم داشت و سپس به اصل موضوع می‌پردازیم. توجه کنید که ما درمورد allocation بحثی نداریم و چالش اصلی، آزاد کردن و ازبین‌بردن اشیا بی‌مصرف حافظه می‌باشد.مدیریت حافظه توسط برنامه‌نویس:از معروف‌ترین زبان‌های برنامه‌نویسی که کنترل حافظه را به خود برنامه‌نویس‌ها سپرده‌اند، می‌توان به c و ++c اشاره کرد. برنامه‌نویس‌های این زبان‌ها باید دائما حواسشون به حافظه و اینکه کِی حافظه را اختصاص و کِی حافظه‌ای را آزاد کنند، باشد.مزایا:سرعت بیشتر: شی بی‌مصرف در لحظه و بدون ایجاد وفقه‌ی خاصی ازبین رفته و فضای اختصاص داده شده به حافظه برمی‌گردد.سادگی: هیچ‌گونه پیچیدگی‌ای ندارد و پیاده‌سازی آن راحت می‌باشد(در واقع پیاده‌سازی‌ای ندارد).رفتار قابل پیش‌بینی: با توجه به اینکه همه چیز به عهده خود برنامه‌نویس می‌باشد در نتیجه رفتار غیرقابل پیش‌بینی رخ نمی‌دهد. به عنوان مثال یک مرتبه روند اجرای برنامه متوقف و garbage collector شروع به اجرا بکند.معایب:معروف‌ترین مورد: memory leaks. البته این مورد ممکن است با garbage collector هم اتفاق بیوفتد، اما در حالتی که حافظه توسط برنامه‌نویس کنترل می‌شود، معمولا بیشتر اتفاق می‌افتد.افزایش زمان توسعه(سردرد شدید): برنامه‌نویس باید حواسش به اشیا مختلف باشد. کِی حافظه را آزاد کنه و کِی نه و این سردرد به حساب میاد. نتیجه‌ی این بررسی دائم نتیجه‌ی کندتر شدن سرعت توسعه می‌باشد(توجه گردد که به هنگام بحث ما باید همه برنامه‌نویس‌ها را مدنظر داشته باشیم نه فقط برنامه‌نویس‌های senior‌).استفاده از حافظه خالی شده: بنا به دلایل مختلف ممکن است یک حافظه خالی شده، توسط خود برنامه‌نویس یا یک برنامه‌نویس دیگر دوباره مورد استفاده قرار می‌گیرد.خالی کردن حافظه خالی: برنامه‌نویس یک خانه از حافظه را که قبلا خالی شده، دوباره خالی می‌کند!شاید با خودتون بگین که چطوری ممکن است که این اتفاق‌ها بیافتد؟ یعنی چی از یک حافظه که خالی شده دوباره استفاده کنیم و یا دوبار خالی شود و... . باید خدمتون عرض کنم که وقتی چند نفر روی یک موضوع کار می‌کنند، از این اتفاق‌ها پیش میاد.https://preview.redd.it/wi0v46k4jhq21.jpg?auto=webp&s=2fb6bd400a7845f61af85c6db635628eb74aa432 مدیریت حافظه توسط زبان برنامه‌نویسی:تقریبا اکثر زبان‌های برنامه‌نویسی سطح بالا این قابلیت را دارند، زبان‌هایی مثل جاوا، پایتون، سی‌شارپ و... . از آنجایی که این فرآیند توسط خود زبان برنامه‌نویسی مدیریت می‌شود، پس باید یک الگوریتم آن را انجام دهد. اینکه این الگوریتم چطوری باشد و کی شروع به کار کند و ... بحث‌هایی هستند که ما بهشون علاقه‌مند هستیم. اما این خودکارسازی(Automation) مزایا و معایبی را به همراه دارد:مزایا:افزایش سرعت توسعه و برنامه‌نویسی راحت: برنامه‌نویس به حافظه و اینکه حافظه کی خالی یا پر می‌شود، توجهی نمی‌کند. طبیعتا تو پروژه‌های حساس و یا چالشی که حجم حافظه کمه، ممکن است برنامه‌نویس مجبور باشد به این مورد اهمیت بدهد ولی به طور کلی در اکثر موارد مهم نمی‌باشد.کمتر شدن مشکلات امنیتی ناشی از مدیریت حافظه: در طی سالیان با کشف باگ‌ها و افزایش تجربه طراحان زبان‌های برنامه‌نویسی این روند رفته رفته بهتر شده است.رفع بعضی از معایب روش مدیریت دستی.معایب:مصرف منابع: برای اجرای دستورات خود garbage collector به cpu نیاز داریم. از سوی دیگر برای نگهداری اطلاعات موردنیاز GC(گاها به جای Garbage Colletor از GC استفاده خواهد شد) به حافظه نیاز داریم که به طبع این‌ها منابع را مصرف و هزینه دارند.کاهش performance: اول از همه بگم که این‌طوری نیست که یهو performance را خیلی کم کند، نه، اما طبیعتا باعث کاهش هرچند خیلی خیلی جزئی‌ای خواهد شد. طبیعتا در اکثر برنامه‌های موجود در جهان این میزان کاهش اصلا، اصلا، اصلا مطرح و مهم نیستند، چون کار performanceی خاصی انجام نمی‌دهند. اما این کاهش چرا رخ می‌دهد؟ GC نیاز به بررسی حافظه دارد، که این بررسی به زمان نیاز دارد و این زمان یک زمان مفید نمی‌باشد. توجه گردد که در مورد قبل ما درباره استفاده از cpu و حافظه حرف زدیم، اما اینجا درباره خود زمان لازم برای بررسی حرف می‌زنیم(البته طبق ادعای یک مقاله، درمواردی ممکن است، در مجموع نه تنها باعث کاهش performance نگردد بلکه باعث افزایش آن نیز ‌شود).غیرقابل پیش‌بینی بودن: اینکه garbage collector کی و کجای برنامه شروع به کار می‌کند، برای ما مشخص نیست و این ممکن است در شرایط خیلی خیلی خاصی مشکلاتی را به وجود بیارد. به عنوان مثال این اتفاق شاید شاید در یک سفینه فضایی یا راکتور هسته‌ای باعث مشکلاتی گردد!https://memegenerator.net/img/instances/55176653/the-garbage-collector-will-handle-it.jpgGarbage Collectionبرسیم به اصل موضوع و اینکه اصلا چند نوع garbage collector داریم؟ چه الگوریتم‌هایی برای پیدا کردن اشیا بی‌مصرف از حافظه پیشنهاد شده‌اند؟ و مواردی از این دست.اما قبل از همه بیایید درباره‌ی موارد پایه‌ای که در رابطه با garbage collectorها مطرح هستش حرف بزنیم. سه نکته اساسی را باید به هنگام بحث از garbage collectorها در نظر داشته باشیم. این سه عبارت‌اند از:حافظه: میزان حافظه heap که برای برنامه اختصاص داده می‌شود.توان عملیاتی(Throughput): مقدار زمان اجرای کد برنامه نسبت به مدت زمانی که garbage collector اجرا می‌گردد. به عنوان مثال اگر بگیم Throughput برابر %99 می‌باشد یعنی در ۹۹ درصد مواقع کد اصلی(برنامه) اجرا شده و ۱ درصد هم برای garbage collector صرف شده است. طبیعتا هرچقدر این عدد به ۱۰۰ نزدیک‌تر باشد، به معنی بهتر بودن garbage collector خواهد بود.تاخیر: مدت زمانی که اجرای برنامه اصلی به خاطر garbage collector با تاخیر مواجه شده است.انواع garbage collectorبرای دسته‌بندی garbage collectorها دیدگاه ما در بررسی تعیین‌کننده خواهد بود. دوتا دیدگاه را بیان می‌کنیم، اما ممکن است دیدگاه‌های دیگری هم باشند(سواد من در حد این دوتاست).− بر اساس نوع اجراIncremental:در این روش garbage collector همراه با برنامه اصلی اجرا می‌شود.stop-the-worldبرخلاف روش قبل در این روش، اجرای برنامه اصلی متوقف و garbage collector به پیدا کردن اشیا بی‌مصرف می‌پردازد.− براساس مدیریت fragmentationاول با fragmentation و مشکلی که این موضوع به همراه دارد آشنا بشیم:به تکه تکه شدن حافظه fragmentation گفته می‌شود که به دو صورت internal و external پدیدار می‌شود. در حالت internal میزان حافظه‌ای که یک شی اختیار می‌کند، بزرگتر از میزان نیازش می‌باشد. یعنی ما شی‌ای داریم که به اندازه x از حافظه نیاز دارد، اما به اندازه y(که بزرگتر از x هستش) حافظه اختیار می‌کند که در این حالت بخش‌هایی از حافظه بی‌استفاده خواهد بود. در حالت external مشکل وجود تکه‌های خالی کوچک حافظه بین خانه‌های حافظه که در حال استفاده هستند را داریم. این خانه‌ها با اینکه خالی هستند اما به دلیل کوچک بودنشون نمی‌توان شی جدیدی را در آن‌ها جای داد و در نتیجه بی‌استفاده می‌مانند. اگر تعداد این خونه‌ها زیاد گردد، میزان پِرتی حافظه زیاد خواهد بود.Compactingبعضی از garbage collectorها همزمان با پاک کردن اشیا بی‌مصرف، خونه‌های مصرف شده را جابه‌جا و در یک‌جا تجمیع می‌کنند. تا خونه‌های کوچک حافظه از بین بروند.non-compactingدر این مورد garbage collectorها پس از پاک کردن کردن اشیا، کاری با بقیه اشیا موجود ندارد.https://ijavayou.files.wordpress.com/2019/02/2ugnhk.jpgاستراتژی‌های تخصیص حافظهاول مطلب گفتیم که بحثی در رابطه با Allocation نداریم ولی از اونجایی که تخصیص حافظه بحث جالبی هستش حیفم اومد که اصلا درموردش حرف نزنیم به خاطر همین خیلی گذرا به این موضوع اشاره می‌کنیم.طبق معمول برای این کار روش‌ها و الگوریتم‌های مختلفی وجود دارد. چند مورد را به صورت خیلی تیتروار مطرح می‌کنیم:Best fit در این روش حافظه بررسی و کوچک‌ترین بلاک حافظه تخصیص داده می‌شود.First fitاولین بلاک حافظه که می‌تواند شی را در خودش جای دهد را تخصیص داده می‌شود.Worst fitبزرگترین بلاک حافظه را انتخاب می‌کند!(می‌پرسید چرا؟ به دردی هم می‌خورد؟ بله ممکن است تحت شرایطی مفید باشد).Next Fitاین الگوریتم شبیه به first fit هستش ولی با این تفاوت که شروع به جستجو را از آخرین بلاک حافظه‌ای که تخصیص پیدا کرده بود، ادامه می‌یابد.یک الگوریتم دیگه هم به اسم ‌Buddy memory allocation که اونم جالبه، یک نگاه بهش بندازید. لینک ۱ و لینک ۲.احتمالا بر اساس توضیحاتی که برای این الگوریتم‌ها داده شد، با خودتون میگین که طبیعتا best fit همیشه بهترین عملکرد را دارد ولی واقعیت اینه که نه این طوری نیست!! چگونه است که این گونه است؟ این گونه:مثال ۱: فرض کنیم که ما دو بلاک حافظه به اندازه‌های ۱۵۰تایی و ۳۵۰تایی(به ترتیب بیان شده) داریم(یعنی اول ۱۵۰ و بعد ۳۵۰). توجه کنید که این دوتا بلاک حافظه از هم جدا هستند، یعنی انگار بلاک ۱۵۰ از آدرس x1 شروع و تا x2 ادامه دارد و بلاک ۳۵۰ از آدرس y1 شروع و تا y2 می‌باشد(چون هم گفتیم که بلاک ۱۵۰ قبل از ۳۵۰ قرار دارد پس y1 > x2).برای این دوتاحافظه با درخواست‌هایی به اندازه‌های ۳۰۰، ۲۵، ۱۲۵ و ۵۰(با همین ترتیبی که گفته شد) مواجه می‌شویم. ببنیم که دو الگوریتم best fit و first fit چگونه این درخواست‌ها را مدیریت می‌کنند(توجه گردد که فرض بر این است که برای تخصیص حافظه به یک درخواست حتما باید تمام تمام خانه‌ها در کنار هم باشند).الگوریتم best fit: برای درخواست ۳۰۰، بلاک حافظه به اندازه ۳۵۰ را انتخاب می‌کند(از ۳۵۰ خانه حافظه ۳۰۰ خانه استفاده و ۵۰ تا اون هنوز خالی و میشه ازش استفاده کرد). درخواست ۲۵ وارد صف می‌شود. در حافظه یک خانه ۱۵۰ تایی و یک خانه ۵۰ تایی داریم. خانه ۵۰تایی انتخاب می‌گردد(باز هم ۲۵ تا از حافظه خالی می‌ماند و میشه ازش استفاده کرد). درخواست ۱۲۵ دریافت می‌گردد. خانه ۱۵۰تایی از حافظه انتخاب می‌شود. ۲۵ خانه باقیمانده به حافظه برمی‌گردد. یعنی الان ما دو بلاک حافظه به اندازه ۲۵تایی داریم. درخواست ۵۰ تایی وارد می‌شود اما به دلیل اینکه بلاک حافظه به اندازه ۵۰ نداریم(دو تا ۲۵ داریم که کنار هم نیستند). حافظه‌ای تخصیص داده نمی‌شود و خطای حافظه کافی در اختیار نیست raise می‌گردد.الگوریتم first fit: برای درخواست ۳۰۰تایی بلاک ۳۵۰ انتخاب و ۵۰تای آن به حافظه بازگشت داده می‌شود. برای درخواست ۲۵ بلاک حافظه ۱۵۰تایی انتخاب(چون در حافظه قبل از بلاک ۵۰ تایی قرار دارد) و ۱۲۵ تا آن بازگشت داده می‌شود. درخواست ۱۲۵ دریافت و بلاک ۱۲۵ تایی اختصاص داده می‌شود، در نهایت نیز درخواست ۵۰تایی دریافت و بلاک ۵۰تایی که از بلاک ۳۵۰ تایی باقی مانده بود تخصیص داده می‌شود.مثال ۲: دو بلاک خالی حافظه به ترتیب و به اندازه‌های ۲۰ و ۱۵ داریم(یعنی ۲۰ قبل از ۱۵ می‌باشد). در شکل پایین مستطیل سمت چپ بلاک ۲۰ تایی و مستطیل سمت راست مربوط به بلاک ۱۵تایی می‌باشد.حالت اول: اگر دو تا شی با اندازه‌های ۱۰ و ۲۰ برای حافظه درخواست بدهند(برای طولانی نشدن مطلب توضیح داده نمیشه ولی اگر مبهم بود تو کامنت‌ها بگین تا همونجا توضیح بدهم):https://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l19-mem.pdfحالت دوم: اگر سه شی به اندازه‌های ۸، ۱۲ و ۱۳ برای تخصیص داشته باشیم:https://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l19-mem.pdfالگوریتم‌های garbage collectorقبل از اینکه وارد بحث الگوریتم‌ها بشویم. باید با نظریه‌ی Generational آشنا و آن را بفهمیم. بر اساس نظریه نسل‌ها اکثر اشیا عمر طولانی نداشته و در همان لحظات ابتدایی پس از ایجاد شدنشون ازبین می‌روند. به همین دلیل بعضی از الگوریتم‌های garbage collector اشیا داخل حافظه heap را به دو دسته کلی تقسیم کنند: نسل جوان و نسل پیر.یکی از مزایای تقسیم کردن حافظه به دو بخش، اجرا کردن بیشتر الگوریتم GC در بخشِ نسل جوان می‌باشد. این کار باعث می‌شود از جهتی میزان حافظه کمتری بررسی گردد(کل حافظه پیمایش نمی‌شود) و از طرف دیگر امکان پیدا کردن اشیا بی‌مصرف بیشتر شود(چون اکثر اشیا در همان لحظات ابتدایی ازبین میٰ‌روند)، که در نتیجه آزادسازی تعداد بیشتری از خانه‌های حافظه را خواهیم داشت. حس می‌کنم مطلب خیلی طولانی شده به خاطر همین دیگه بریم سراغ الگوریتم‌ها.الگوریتم‌ها۱− ردیابی(Tracing)در این سبک از الگوریتم‌، روش پیدا کردن اشیا بی‌مصرف براساس قابلیت دسترسی به آن شی می‌باشد. یعنی برای تشخیص اینکه یک شی هنوز قابل استفاده می‌باشد یا نه؟ اگر بتوانیم از طریق پیمایش گراف به آن شی برسیم یعنی هنوز بی‌مصرف نشده و قابلیت استفاده را دارد، در غیر این صورت اون شی باید ازبین برود. احتمالا الان دارین میگین که گراف از کجا اومد(اولا اینکه گراف یک نوع ساختمان داده‌ست که شبیه درخته ولی دور هم دارد) و پیمایش اون چطوریه(BFS یا DFS) و ...؟ اساس این سبک الگوریتم ایجاد یک گراف و پیمایش آن می‌باشد. به نقاط شروع این گراف‌ها root set گفته می‌شود که root set در واقع خانه‌هایی از حافظه هستند که می‌دونیم قابل دسترسی می‌باشند. حالا برای بررسی حافظه از این root set شروع به پیمایش می‌کنیم و به هر خانه‌ای که رسیدیم به عنوان یک خانه مفید حافظه که قابلیت استفاده را دارد علامت‌گذاری می‌کنیم، وقتی که پیمایش تمام شد، خانه‌هایی که علامت‌گذاری نشدند حذف می‌گردند. اینکه پیمایش به چه شکل انجام می‌شود به نحوه پیاده‌سازی الگوریتم بستگی دارد، اما یکی از معروف‌ترین پیاده‌سازی‌های این سبک(mark&sweep) از DFS استفاده می‌کند. این الگوریتم چند نوع پیاده سازی دارد که یکی از معروف‌ترین‌ها و قدیمی‌ترین‌ها اسمش mark & sweep هستش. برای همین این الگوریتم توضیح داده می‌شود، تقریبا بقیه هم تقریبا به این صورت عمل می‌کنند. الگوریتم mark & sweep:این الگوریتم دو فاز دارد: فاز mark و فاز sweep(جمله فاخری بود D:)! در این الگوریتم برای هر شی یک بیت درنظر گرفته می‌شود که مشخص می‌کند این شی از حافظه پاک شود یا نه؟ فاز mark: در ابتدای این فاز بیت نشانه‌گذاری در همه اشیا، به صفر تنظیم شده است به چه صورت؟ اگر یک شی جدید ایجاد شده باشد به صورت پیشفرض این بیت برای آن شی صفر می‌باشد و اگر شی از قبل وجود داشته باشد، در سریِ قبلِ اجرای الگوریتم، به صفر تغییر داده شده است. الگوریتم از root set شروع به پیمایش می‌کند به هر شی‌ای که می‌رسد بیت نشانه‌گذاری را به یک تغییر می‌دهد و این کار تا جایی ادامه پیدا می‌کند که دیگه همه خانه‌های قابل دسترسی پیمایش گردد. اگر بخواهیم کد را این فاز را شبیه‌سازی کنیم، خواهیم داشت:Mark(node) If markedBit(node) = false then markedBit(node) = true For each v referenced by node Mark(v)یک گره را دریافت می‌کنیم اگر بیت نشانه‌گذاریش صفر باشد، اون را به یک تبدیل می‌کنیم. سپس این کار را برای تک‌تک گره‌هایی که از گره فعلی قابل دسترسی هستند، انجام میدیم.فاز sweep: در این فاز اشیا بررسی شده و شی‌هایی که بیت نشانه‌گذاری‌شان صفر می‌باشد حذف می‌گردند. همچین بیت‌نشانه‌گذاری دیگر اشیا نیز از یک به صفر تنظیم می‌گردد تا اشیا برای سری بعد اجرای الگوریتم آماده باشد. شبه کد این فاز:Sweep(): For each node in heap If markedBit(node) = true then markedBit(node) = false else heap.release(node)این عکس gif به صورت خلاصه این الگوریتم را بیان می‌کند.از معایب این روش:متوقف کردن اجرای برنامه اصلی برای بررسی حافظهایجاد شدن fragmentation خارجی۲− شمارش تعداد رفرنس‌ها(Reference counting)این الگوریتم از شمارش تعداد رفرنس‌ها(اشاره‌گر) به یک شی مشخص می‌کند که آیا یک شی بی‌مصرف می‌باشد یا نه؟ این عدد(که با اسم refcount شناخته می‌شود) با تعداد رفرنس‌های یک شی کاهش و افزایش داشته و وقتی که refcount یک شی به صفر می‌رسد، یعنی بی‌مصرف بوده و باید خانه‌های اشغال شده توسط آن شی به حافظه بازگردانده ‌شود. برای نگهداری اطلاعات رفرنس‌ها هم یک overhead خواهیم داشت. اگر بخواهیم که به صورت شماتیک این الگوریتم را نشان دهیم، خواهیم داشت:https://rebelsky.cs.grinnell.edu/Courses/CS302/99S/Presentations/GC/چندتا ویژگی داره که می‌توان به:سادگی: پیچیدگی خاصی ندارد و راحت پیاده‌سازی می‌گردد.سرعت مناسب: برنامه اصلی تنها برای چند لحظه کوتاه متوقف می‌شود و از این جهت مناسب می‌باشد.ازبین رفتن سریع اشیا بی‌مصرف: بازپس‌گیری حافظه به سرعت اتفاق می‌افتد.البته معایبی هم داره که یک موردش خیلی بده:حلقه بی‌نهایت: اگر رفرنس‌ها تشکیل یک دور را بدهند در این صورت این الگوریتم با شکست مواجه خواهد شد و refcount درست نخواهد بود(البته این مورد با کمک اجرای یک الگوریتم به اسم cycle رفع می‌گردد).مشکل اضافه و کم‌کردن تعداد رفرنس‌های یک شی: این مورد می‌تواند باعث pipeline bubbles گردد که البته تکنیک‌هایی برای رفع آن وجود دارد. به عنوان مثال کامپایلر می‌تواند افزایش و کاهش رفرنس‌های نزدیک به هم را در یک مرحله انجام دهد که این کمک کننده خواهد بود.این الگوریتم را می‌توان بر اساس وزن هم پیاده‌سازی کرد که بهش Weighted reference counting گفته می‌شود. برای مطالعه می‌تونید از این لینک و این لینک استفاده کنید.۳−الگوریتم Copyبرای این الگوریتم گاها از نام Stop and Copy هم استفاده می‌شود. الگوریتم به این صورت کار می‌کند که حافظه را به دو بخش تقسیم می‌کند که به یک بخش active(یا from-space) و به بخش دیگر idle(یا to-space) گفته می‌شود. سپس به هنگام تخصیص حافظه فقط از بخش active استفاده خواهد شد. روش تخصیص حافظه نیز خطی بوده و از ابتدا بخش شروع و رفته رفته به سمت انتهای حافظه حرکت خواهد کرد. موقعی که خانه‌های حافظه active دیگر جوابگوی تخصیص حافظه نبودند، برنامه stop و شروع به حذف اشیا بی‌مصرف خواهد نمود. شی‌هایی که هنوز قابلیت استفاده را دارند نیز در بخش Idle(از ابتدای این بخش) کپی می‌گردند. در آخر نیز حافظه بخش idle مرحله قبل به حافظه active و حافظه active مرحله قبل به idle تغییر پیدا خواهند کرد. البته نحوه پیدا کردن اشیا بی‌مصرف و کپی کردن دگیر اشیا نیز خود می‌تواند شامل روش‌های مختلفی داشته باشد. به عنوان مثال می‌توان از Cheney که یک الگوریتم به صورت BFS می‌باشد نام نمود(لینک دادم چون به نظرم مطلب طولانی شده). یکی از معایب این روش کاهش حجم حافظه و استفاده تنها از نصف آن می‌باشد. موردی دیگری که می‌توان به آن اشاره کرد، کپی کردن اشیا در هر چرخه اجرای الگوریتم می‌باشد.https://images.slideplayer.com/25/8257976/slides/slide_23.jpgسعی کردم برای منابع از دانشگاه‌های معتبر استفاده کنم تا احیانا موردی اشتباه گفته نشود، اما طبیعتا ممکن است خطا(یا خطاهایی) وجود داشته باشد، خوشحال می‌شوم اون‌ها را بدانم تا هم مطلب و هم سواد ناقصم را یکم اصلاح کنم. همین! امیدوارم که مفید بوده باشه.در خصوص اجرای برنامه‌ها و کلا ماجرای حافظه در سیستم‌عامل آقای عباس یزدان‌پناه یک سری ویدئو آموزشی خوب و مختصر و مفید را توی کانال یوتیوب خودشون تحت عنوان "گردشی در سیستم‌عامل" قرار دادند که توصیه می‌کنم، این سری ویدئوهارو حتما نگاه کنید، چون دانش خوبی را بدست می‌آورید.یک نمونه از ویدئوهاشون(IP خودتون رو تغییر بدین). https://youtu.be/vrMuzaowMjc لبخند بزنین لطفا :)منابع:https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/18/Slides18.pdfhttps://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l19-mem.pdfhttps://dzone.com/articles/choosing-the-best-garbage-collection-algorithm-forhttps://www.geeksforgeeks.org/partition-allocation-methods-in-memory-management/https://en.wikipedia.org/wiki/Reference_countinghttps://rebelsky.cs.grinnell.edu/Courses/CS302/99S/Presentations/GC/http://wiki.dreamrunner.org/public_html/C-C++/Library-Notes/SimpleGarbageCollector.htmlhttps://en.wikipedia.org/wiki/Garbage_collection_(computer_science)