داشتم یک مطلبی می‌خوندم که دیدم درمورد garbage collector اطلاعات زیاد دقیقی ندارم، به خاطر همین گفتم برم ببینم پشت صحنه چه خبراست و زبان‌های برنامه‌نویسی چطوری دارند، این موضوع را مدیریت می‌کنند. چیزهای خوبی را یادگرفتم و امیدوارم بتونم بعضی از این موارد را منتقل کنم.
نکته: تلاش می‌کنم که متن را به صورت محاوره ننویسم ولی احتمالا حواسم نباشه و جملاتی از متن به صورت محاوره باشه. پیشاپیش پوزش بابت این ناهمگونی. :)
این مطلب برای آشنایی با garbage collectorهاست. اینکه چطوری کار می‌کنند؟ چه الگوریتم‌ها وجود دارد؟ چه رویکردهایی مورد استفاده‌ست و کلا چیزهایی از این قبیل. اما از اونجایی که برای درک بهتر موضوع باید با برخی موارد آشنا باشیم، به خاطر همین یک مقدمه خیلی مختصری را داریم. بعد به سراغ اصل موضوع یعنی garbage collectorها می‌رویم و عمیق‌تر بررسی‌شون می‌کنیم.
سعی می‌کنم طی چند روز آینده یک پست جداگانه درمورد garbage collector تو پایتون هم داشته باشیم.
برنامه‌ها به هنگام اجرا در حافظه باگذاری(load) می‌شوند. قبل‌ترها اینطوری بود یک تکه از حافظه جدا و به برنامه اختصاص داده می‌شد تا در اون برنامه بارگذاری بشود و تمام! برنامه‌ها هم هر جوری دوست داشتند رفتار می‌کردند(ملق می‌زدند، از این‌ور به اون‌ور، اون‌ور به این‌ور و خلاصه شلم شوربایی بود)! اما این کار باعث یک سری مشکلات می‌شد. مشکلاتی مثل مشکلات امنیتی! چطوری؟ چون همه به همه‌ی خانه‌های حافظه دسترسی داشتند و هیچ کنترل و نظارتی نبود، در نتیجه امکان تغییر محتوای خانه‌ها وجود داشت! یک برنامه مخرب خیلی راحت می‌تونست به خراب‌کاری در سیستم بپردازد. این مشکلات باعث تغییر این رویکرد و پدیدار شدن، بخش‌بندی و جداسازی شد. بخش‌هایی مثل بخش کد، بخش دیتا و ... که کنترل هم می‌شدند. به دلیل اینکه مطلب طولانی نشه این بخش‌ها را توضیح نمی‌دهیم(اگر علاقه‌مند هستید این لینک می‌تواند کمک کننده باشد). به طور خلاصه عکس پایین این بخش‌ها را نشان می‌دهد.
با توجه به موضوع این مطلب(garbage collector)، در بین این بخش‌ها ما به heap علاقه‌مندیم. دلیل آن هم این است که به طور کلی garbage collectorها در بخش Heap اجرا می‌شوند. توصیه می‌کنم اگر با heap و stack آشنا نیستید، قبل یا بعد از این مطلب حتما یک مطالعه‌ای درباره آن‌ها داشته باشید(حتی به صورت خیلی خلاصه وار. منم آخر سر یک لینک میزارم)، چون هم درک بهتر و عمیق‌تری از برنامه‌نویسی بدست می‌آورید و هم برخی از رفتار‌های زبان‌های برنامه‌نویسی براتون مملوس‌تر می‌شود.
مدیریت این بخش heap همیشه از چالش‌هایی بوده که طراحان زبان‌های برنامه‌نویسی باهاش مواجه بودند و هستند. پایه‌ای‌ترین سوالی که همیشه مطرحه اینه که آيا این کار باید توسط خود برنامه‌نویس صورت بگیرد؟ یا خودِ زبانِ برنامه‌نویسی باید قابلیتی را برای آن ارائه کند؟ به عبارت دیگر اصلا یک زبان برنامه‌نویسی باید garbage collector داشته باشد یا نه؟ این مطلب برای این جواب دادن به این سوال نیست! چون این سوال یک جواب مشخص و به اصطلاح صفر و یکی ندارد که بتوان با قاطعیت برای همه یک نسخه واحد پیچید و تامام! اما شناخت جنبه‌هایی از این موضوع، به ما کمک می‌کند تا دید بهتری داشته باشیم.
در رابطه با سوال پاراگراف قبل(اینکه مدیریت heap چگونه باشد)، دو تا رویکرد وجود دارد که مثل همیشه هر کدوم از این رویکردها مزایا و معایبی را دارند. در ادامه مطلب یک اشاره مختصر به این مزایا و معایب خواهیم داشت و سپس به اصل موضوع می‌پردازیم. توجه کنید که ما درمورد allocation بحثی نداریم و چالش اصلی، آزاد کردن و ازبین‌بردن اشیا بی‌مصرف حافظه می‌باشد.
مدیریت حافظه توسط برنامه‌نویس:
از معروف‌ترین زبان‌های برنامه‌نویسی که کنترل حافظه را به خود برنامه‌نویس‌ها سپرده‌اند، می‌توان به c و ++c اشاره کرد. برنامه‌نویس‌های این زبان‌ها باید دائما حواسشون به حافظه و اینکه کِی حافظه را اختصاص و کِی حافظه‌ای را آزاد کنند، باشد.
مزایا:
معایب:
شاید با خودتون بگین که چطوری ممکن است که این اتفاق‌ها بیافتد؟ یعنی چی از یک حافظه که خالی شده دوباره استفاده کنیم و یا دوبار خالی شود و... . باید خدمتون عرض کنم که وقتی چند نفر روی یک موضوع کار می‌کنند، از این اتفاق‌ها پیش میاد.
مدیریت حافظه توسط زبان برنامه‌نویسی:
تقریبا اکثر زبان‌های برنامه‌نویسی سطح بالا این قابلیت را دارند، زبان‌هایی مثل جاوا، پایتون، سی‌شارپ و... . از آنجایی که این فرآیند توسط خود زبان برنامه‌نویسی مدیریت می‌شود، پس باید یک الگوریتم آن را انجام دهد. اینکه این الگوریتم چطوری باشد و کی شروع به کار کند و ... بحث‌هایی هستند که ما بهشون علاقه‌مند هستیم. اما این خودکارسازی(Automation) مزایا و معایبی را به همراه دارد:
مزایا:
معایب:
برسیم به اصل موضوع و اینکه اصلا چند نوع garbage collector داریم؟ چه الگوریتم‌هایی برای پیدا کردن اشیا بی‌مصرف از حافظه پیشنهاد شده‌اند؟ و مواردی از این دست.
اما قبل از همه بیایید درباره‌ی موارد پایه‌ای که در رابطه با garbage collectorها مطرح هستش حرف بزنیم. سه نکته اساسی را باید به هنگام بحث از garbage collectorها در نظر داشته باشیم. این سه عبارت‌اند از:
انواع garbage collector
برای دسته‌بندی garbage collectorها دیدگاه ما در بررسی تعیین‌کننده خواهد بود. دوتا دیدگاه را بیان می‌کنیم، اما ممکن است دیدگاه‌های دیگری هم باشند(سواد من در حد این دوتاست).
− بر اساس نوع اجرا
در این روش garbage collector همراه با برنامه اصلی اجرا می‌شود.
برخلاف روش قبل در این روش، اجرای برنامه اصلی متوقف و garbage collector به پیدا کردن اشیا بی‌مصرف می‌پردازد.
− براساس مدیریت fragmentation
اول با fragmentation و مشکلی که این موضوع به همراه دارد آشنا بشیم:
به تکه تکه شدن حافظه fragmentation گفته می‌شود که به دو صورت internal و external پدیدار می‌شود. در حالت internal میزان حافظه‌ای که یک شی اختیار می‌کند، بزرگتر از میزان نیازش می‌باشد. یعنی ما شی‌ای داریم که به اندازه x از حافظه نیاز دارد، اما به اندازه y(که بزرگتر از x هستش) حافظه اختیار می‌کند که در این حالت بخش‌هایی از حافظه بی‌استفاده خواهد بود. در حالت external مشکل وجود تکه‌های خالی کوچک حافظه بین خانه‌های حافظه که در حال استفاده هستند را داریم. این خانه‌ها با اینکه خالی هستند اما به دلیل کوچک بودنشون نمی‌توان شی جدیدی را در آن‌ها جای داد و در نتیجه بی‌استفاده می‌مانند. اگر تعداد این خونه‌ها زیاد گردد، میزان پِرتی حافظه زیاد خواهد بود.
بعضی از garbage collectorها همزمان با پاک کردن اشیا بی‌مصرف، خونه‌های مصرف شده را جابه‌جا و در یک‌جا تجمیع می‌کنند. تا خونه‌های کوچک حافظه از بین بروند.
در این مورد garbage collectorها پس از پاک کردن کردن اشیا، کاری با بقیه اشیا موجود ندارد.
استراتژی‌های تخصیص حافظه
اول مطلب گفتیم که بحثی در رابطه با Allocation نداریم ولی از اونجایی که تخصیص حافظه بحث جالبی هستش حیفم اومد که اصلا درموردش حرف نزنیم به خاطر همین خیلی گذرا به این موضوع اشاره می‌کنیم.
طبق معمول برای این کار روش‌ها و الگوریتم‌های مختلفی وجود دارد. چند مورد را به صورت خیلی تیتروار مطرح می‌کنیم:
در این روش حافظه بررسی و کوچک‌ترین بلاک حافظه تخصیص داده می‌شود.
اولین بلاک حافظه که می‌تواند شی را در خودش جای دهد را تخصیص داده می‌شود.
بزرگترین بلاک حافظه را انتخاب می‌کند!(می‌پرسید چرا؟ به دردی هم می‌خورد؟ بله ممکن است تحت شرایطی مفید باشد).
این الگوریتم شبیه به first fit هستش ولی با این تفاوت که شروع به جستجو را از آخرین بلاک حافظه‌ای که تخصیص پیدا کرده بود، ادامه می‌یابد.
یک الگوریتم دیگه هم به اسم Buddy memory allocation که اونم جالبه، یک نگاه بهش بندازید. لینک ۱ و لینک ۲.
احتمالا بر اساس توضیحاتی که برای این الگوریتم‌ها داده شد، با خودتون میگین که طبیعتا best fit همیشه بهترین عملکرد را دارد ولی واقعیت اینه که نه این طوری نیست!! چگونه است که این گونه است؟ این گونه:
مثال ۱: فرض کنیم که ما دو بلاک حافظه به اندازه‌های ۱۵۰تایی و ۳۵۰تایی(به ترتیب بیان شده) داریم(یعنی اول ۱۵۰ و بعد ۳۵۰). توجه کنید که این دوتا بلاک حافظه از هم جدا هستند، یعنی انگار بلاک ۱۵۰ از آدرس x1 شروع و تا x2 ادامه دارد و بلاک ۳۵۰ از آدرس y1 شروع و تا y2 می‌باشد(چون هم گفتیم که بلاک ۱۵۰ قبل از ۳۵۰ قرار دارد پس y1 > x2).
برای این دوتاحافظه با درخواست‌هایی به اندازه‌های ۳۰۰، ۲۵، ۱۲۵ و ۵۰(با همین ترتیبی که گفته شد) مواجه می‌شویم. ببنیم که دو الگوریتم best fit و first fit چگونه این درخواست‌ها را مدیریت می‌کنند(توجه گردد که فرض بر این است که برای تخصیص حافظه به یک درخواست حتما باید تمام تمام خانه‌ها در کنار هم باشند).
الگوریتم best fit: برای درخواست ۳۰۰، بلاک حافظه به اندازه ۳۵۰ را انتخاب می‌کند(از ۳۵۰ خانه حافظه ۳۰۰ خانه استفاده و ۵۰ تا اون هنوز خالی و میشه ازش استفاده کرد). درخواست ۲۵ وارد صف می‌شود. در حافظه یک خانه ۱۵۰ تایی و یک خانه ۵۰ تایی داریم. خانه ۵۰تایی انتخاب می‌گردد(باز هم ۲۵ تا از حافظه خالی می‌ماند و میشه ازش استفاده کرد). درخواست ۱۲۵ دریافت می‌گردد. خانه ۱۵۰تایی از حافظه انتخاب می‌شود. ۲۵ خانه باقیمانده به حافظه برمی‌گردد. یعنی الان ما دو بلاک حافظه به اندازه ۲۵تایی داریم. درخواست ۵۰ تایی وارد می‌شود اما به دلیل اینکه بلاک حافظه به اندازه ۵۰ نداریم(دو تا ۲۵ داریم که کنار هم نیستند). حافظه‌ای تخصیص داده نمی‌شود و خطای حافظه کافی در اختیار نیست raise می‌گردد.
الگوریتم first fit: برای درخواست ۳۰۰تایی بلاک ۳۵۰ انتخاب و ۵۰تای آن به حافظه بازگشت داده می‌شود. برای درخواست ۲۵ بلاک حافظه ۱۵۰تایی انتخاب(چون در حافظه قبل از بلاک ۵۰ تایی قرار دارد) و ۱۲۵ تا آن بازگشت داده می‌شود. درخواست ۱۲۵ دریافت و بلاک ۱۲۵ تایی اختصاص داده می‌شود، در نهایت نیز درخواست ۵۰تایی دریافت و بلاک ۵۰تایی که از بلاک ۳۵۰ تایی باقی مانده بود تخصیص داده می‌شود.
مثال ۲: دو بلاک خالی حافظه به ترتیب و به اندازه‌های ۲۰ و ۱۵ داریم(یعنی ۲۰ قبل از ۱۵ می‌باشد). در شکل پایین مستطیل سمت چپ بلاک ۲۰ تایی و مستطیل سمت راست مربوط به بلاک ۱۵تایی می‌باشد.
حالت اول: اگر دو تا شی با اندازه‌های ۱۰ و ۲۰ برای حافظه درخواست بدهند(برای طولانی نشدن مطلب توضیح داده نمیشه ولی اگر مبهم بود تو کامنت‌ها بگین تا همونجا توضیح بدهم):
حالت دوم: اگر سه شی به اندازه‌های ۸، ۱۲ و ۱۳ برای تخصیص داشته باشیم:
قبل از اینکه وارد بحث الگوریتم‌ها بشویم. باید با نظریه‌ی 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 به صورت خلاصه این الگوریتم را بیان می‌کند.
از معایب این روش:
۲− شمارش تعداد رفرنس‌ها(Reference counting)
این الگوریتم از شمارش تعداد رفرنس‌ها(اشاره‌گر) به یک شی مشخص می‌کند که آیا یک شی بی‌مصرف می‌باشد یا نه؟ این عدد(که با اسم refcount شناخته می‌شود) با تعداد رفرنس‌های یک شی کاهش و افزایش داشته و وقتی که refcount یک شی به صفر می‌رسد، یعنی بی‌مصرف بوده و باید خانه‌های اشغال شده توسط آن شی به حافظه بازگردانده شود. برای نگهداری اطلاعات رفرنس‌ها هم یک overhead خواهیم داشت. اگر بخواهیم که به صورت شماتیک این الگوریتم را نشان دهیم، خواهیم داشت:
چندتا ویژگی داره که می‌توان به:
البته معایبی هم داره که یک موردش خیلی بده:
این الگوریتم را می‌توان بر اساس وزن هم پیاده‌سازی کرد که بهش Weighted reference counting گفته می‌شود. برای مطالعه می‌تونید از این لینک و این لینک استفاده کنید.
۳−الگوریتم Copy
برای این الگوریتم گاها از نام Stop and Copy هم استفاده می‌شود. الگوریتم به این صورت کار می‌کند که حافظه را به دو بخش تقسیم می‌کند که به یک بخش active(یا from-space) و به بخش دیگر idle(یا to-space) گفته می‌شود. سپس به هنگام تخصیص حافظه فقط از بخش active استفاده خواهد شد. روش تخصیص حافظه نیز خطی بوده و از ابتدا بخش شروع و رفته رفته به سمت انتهای حافظه حرکت خواهد کرد. موقعی که خانه‌های حافظه active دیگر جوابگوی تخصیص حافظه نبودند، برنامه stop و شروع به حذف اشیا بی‌مصرف خواهد نمود. شی‌هایی که هنوز قابلیت استفاده را دارند نیز در بخش Idle(از ابتدای این بخش) کپی می‌گردند. در آخر نیز حافظه بخش idle مرحله قبل به حافظه active و حافظه active مرحله قبل به idle تغییر پیدا خواهند کرد. البته نحوه پیدا کردن اشیا بی‌مصرف و کپی کردن دگیر اشیا نیز خود می‌تواند شامل روش‌های مختلفی داشته باشد. به عنوان مثال می‌توان از Cheney که یک الگوریتم به صورت BFS می‌باشد نام نمود(لینک دادم چون به نظرم مطلب طولانی شده). یکی از معایب این روش کاهش حجم حافظه و استفاده تنها از نصف آن می‌باشد. موردی دیگری که می‌توان به آن اشاره کرد، کپی کردن اشیا در هر چرخه اجرای الگوریتم می‌باشد.
سعی کردم برای منابع از دانشگاه‌های معتبر استفاده کنم تا احیانا موردی اشتباه گفته نشود، اما طبیعتا ممکن است خطا(یا خطاهایی) وجود داشته باشد، خوشحال می‌شوم اون‌ها را بدانم تا هم مطلب و هم سواد ناقصم را یکم اصلاح کنم. همین! امیدوارم که مفید بوده باشه.
در خصوص اجرای برنامه‌ها و کلا ماجرای حافظه در سیستم‌عامل آقای عباس یزدان‌پناه یک سری ویدئو آموزشی خوب و مختصر و مفید را توی کانال یوتیوب خودشون تحت عنوان "گردشی در سیستم‌عامل" قرار دادند که توصیه می‌کنم، این سری ویدئوهارو حتما نگاه کنید، چون دانش خوبی را بدست می‌آورید.
یک نمونه از ویدئوهاشون(IP خودتون رو تغییر بدین).
لبخند بزنین لطفا :)
