تخصیص حافظه (Memory Allocation)
درسیستمهای مدیریت حافظه، سه کار اصلی انجام میشود:
- تخصیص حافظه (Allocation)
- شناسایی اشیای زنده و مرده (Identifying Live/Dead Objects)
- آزادسازی حافظه برای استفادهی مجدد (Reclamation)
و این کارها بستگی دارد به این که Garbage Collector (GC) چگونه حافظه را مدیریت میکند.
تفاوت تخصیص در سیستمهای GC و سیستمهای مدیریت حافظهی صریح
در GC، حافظه به صورت خودکار آزاد میشود؛ پس: تخصیص حافظه معمولاً متوالی و ساده انجام میشود. برخی GCها کل حافظهی اشیای مرده را یکجا آزاد میکنند. برنامهنویسها معمولاً از هیپ، بیشتر از استک استفاده میکنند.
در مدیریت حافظهی صریح (مانند malloc/free در C): برنامهنویس مسئول آزادسازی حافظه است. تخصیص و آزادسازی اشیاء میتواند منجر به تکهتکه شدن حافظه (Fragmentation) شود.
استراتژیهای تخصیص حافظه
به طور کلی دو روش اصلی داریم:
- تخصیص متوالی (Sequential Allocation)
- تخصیص از لیست آزاد (Free-List Allocation)
تخصیص متوالی (Sequential Allocation)
ایدهی اصلی: یک بلوک بزرگ از حافظه داریم که اشیاء را به ترتیب در آن ذخیره میکنیم. برای هر تخصیص، مقدار مورد نیاز را از انتهای فضای آزاد برمیداریم و Pointer را جلو میبریم. بعد از آزاد شدن حافظه، Garbage Collector، فضاء را فشرده میکند و مجدد استفاده میشود.
ساختار دادهها در این روش:
- یک Pointer به فضای آزاد (Free Pointer)
- یک Pointer به انتهای بلوک حافظه (Limit Pointer)
ویژگیهای این روش:
خیلی ساده و سریع است، چون فقط Pointer را جلو میبرد! کارایی خوبی برای حافظهی کش (Cache Locality) دارد. در GCهای جابجایی (Moving Collectors) خیلی خوب کار میکند.
تخصیص از لیست آزاد (Free-List Allocation)
این روش زمانی استفاده میشود که تخصیص متوالی بهینه نباشد، مخصوصاً برای GCهای غیرجابجایی (Non-Moving Collectors) که باعث تکهتکه شدن حافظه (Fragmentation) میشوند.
ایدهی اصلی تخصیص از لیست آزاد:
یک لیست از بلوکهای آزاد حافظه را نگه میداریم و هر بار که نیاز به تخصیص داریم، یکی از این بلوکها را انتخاب میکنیم. هر بلوک آزاد شامل اندازهی خودش و آدرس بلوک بعدی در لیست آزاد است. اگر اندازهی بلوک، بزرگتر از مقدار درخواستی باشد، میتوانیم به دو بخش تقسیم کنیم و بقیهی فضای باقیمانده را دوباره به لیست آزاد اضافه کنیم. اگر یک بلوک بهطور کامل استفاده شد، از لیست حذف میشود. این روش در مقابل تخصیص متوالی قرار میگیرد که فقط Pointer را جلو میبرد و نیازی به جستجوی بلوک مناسب ندارد.
استراتژیهای تخصیص از لیست آزاد
سه روش اصلی برای انتخاب بلوک مناسب از لیست آزاد داریم:
- First-Fit (اولین اندازه مناسب): اولین بلوکی که فضای کافی دارد انتخاب میشود.
- Next-Fit (بعدی مناسب): جستجو از آخرین محل تخصیص شروع میشود.
- Best-Fit (بهترین اندازه مناسب): کوچکترین بلوک مناسب انتخاب میشود.
نتیجه:
- اگر سرعت مهم باشد، First-Fit بهتر است.
- اگر میخواهیم تخصیصها پخش شوند، Next-Fit گزینهی مناسبی است.
- اگر مصرف حافظه خیلی برایمان مهم است، Best-Fit بهتر جواب میدهد.
چند روش پیشرفتهتر برای مدیریت لیست آزاد:
- Balanced Binary Trees (درخت دودویی متوازن) : گرهها را بر اساس اندازه یا آدرس مرتب میکند و زمان جستجو را log(n) میکند.
- Cartesian Trees (درخت کارتزین) : هم آدرس و هم اندازهی بلوکها را نگه میدارد و برای First-Fit و Next-Fit خوب کار میکند.
- Bitmapped-Fits (تخصیص بر پایه بیتمپ) : هر بلوک یک بیت در یک بیتمپ دارد که وضعیت آن را مشخص میکند و جستجو سریعتر انجام میشود.
- Hierarchical Bitmaps (بیتمپ سلسلهمراتبی) : اطلاعات هر گروه از بلوکها را خلاصه میکند تا پردازش سریعتر شود.
اگر GC جابجایی دارد (Moving Collector)، تخصیص متوالی بهتر است.
اگر GC جابجایی ندارد (Non-Moving Collector)، تخصیص از لیست آزاد مشکل Fragmentation را کاهش میدهد.
تکهتکه شدن حافظه (Fragmentation) و راههای مدیریت آن
وقتی یک برنامه حافظه را درخواست میکند و بعد آزاد میکند، معمولاً فضاهای خالی نامنظم و پراکندهای در حافظه باقی میماند. به این حالت Fragmentation گفته می شود.
دو مشکل اصلی Fragmentation:
فضا هست، اما قابل استفاده نیست!
فرض کنید یک برنامه به 10 مگابایت حافظه نیاز دارد، اما حافظهی خالی بهصورت پراکنده در چند بلوک کوچکتر موجود است. یعنی جمعاً فضای آزاد به اندازهی کافی هست، اما هیچ بلوک پیوستهای که 10 مگابایت را تأمین کند وجود ندارد.
- در سیستمهایی که GC ندارند (مثل C و ++C)، این یعنی برنامه ممکن است کرش کند!
- در سیستمهایی که GC دارند (مثل Java و #C)، این یعنی GC زودتر اجرا میشود تا ببیند که میتواند فضا را مرتب کند یا خیر.
استفادهی غیربهینه از حافظهی کش و آدرسدهی!
وقتی حافظه پراکنده و تکهتکه شود، برنامه بهجای استفاده از چند صفحهی متوالی از RAM، باید بین صفحات مختلف جابجا شود. این باعث میشود برنامه صفحات بیشتری را در RAM رزرو کند و بیشتر از حد نیاز از کش CPU استفاده کند.
هیچ الگوریتمی کاملاً عاری از Fragmentation نیست!
- First-Fit (اولین فضای مناسب) بلوکهای کوچک در ابتدای لیست جمع میشوند!
- Next-Fit (بعدی مناسب) بلوکهای کوچکتر پخش میشوند، ولی بهتر نیست!
- Best-Fit (بهترین اندازه مناسب) باعث ایجاد تکههای خیلی کوچک غیرقابل استفاده میشود!
راهحلهای مدیریت Fragmentation
- Compaction (فشردهسازی): جابجایی دادهها برای ایجاد فضای متوالی
- Copying Collection: انتقال تمام دادههای زنده به یک بخش جدید و حذف فضای خالی
- Segregated Free Lists: مدیریت جداگانهی بلوکهای کوچک و بزرگ برای جلوگیری از هدررفت
- Pooling (حوضچهای): اختصاص حافظه در سایزهای مشخص برای کاهش Fragmentation داخلی
اگه GC داریم و حافظه را میتوانیم جابهجا کنیم، Compaction و Copying Collection عالی هستند.
اگه GC نداریم، باید از Segregated Free Lists یا Pooling استفاده کنیم.
تخصیص حافظه با روش Segregated-Fits
Segregated-Fits تکنیکی سریعتر از Free-List معمولی است که برای جلوگیری از جستجوی زیاد لیستهای جداگانهای بر اساس سایز آبجکتها ایجاد میکند.
بهجای اینکه یک لیست کلی از همه بلوکهای آزاد داشته باشیم و دنبال یک فضای مناسب بگردیم، برای هر کلاس اندازه (Size Class) یک لیست جداگانه داریم. یعنی:
بلوکهای کوچک (مثلاً 8 بایت)
بلوکهای متوسط (مثلاً 32 بایت)
بلوکهای بزرگ (مثلاً 256 بایت و بیشتر)
در نتیجه مستقیماً میریم سراغ لیست مناسب و سریعترین بلوک را برمیداریم!
ساختار Segregated-Fits
در Segregated-Fits، اندازههای مختلف در دستههای جدا قرار میگیرند:
- Small Objects محدوده اندازه 8 - 32 بایت - کاربرد اشارهگرها، اعداد کوچک
- Medium Objects محدوده اندازه 64 - 256 بایت - کاربرد آبجکتهای معمولی مثل رشتهها
- Large Objects محدوده اندازه 512 بایت - چند کیلوبایت - کاربرد آرایههای بزرگ، تصاویر، بافرها
انواع پیادهسازی Segregated-Fits
روش BiBoP (Big Bag of Pages)
در این روش، هر صفحهی حافظه فقط برای یک سایز خاص استفاده میشود.
روش Buddy System
در این روش، بلوکهای حافظه به توانهای 2 تقسیم میشوند. مثلاً:
یک بلوک 512 بایتی به دو تا بلوک 256 بایتی تقسیم میشود
یک بلوک 256 بایتی، به دو تا 128 بایتی و همینطور ادامه پیدا میکند...
در سیستمهای چندنخی (Concurrent Systems) تخصیص حافظه یک چالش جدید است، چون اگر همه نخها بخواهند همزمان حافظه بگیرند، ممکن است باعث بنبست (Deadlock) یا تأخیر (Latency) شود.
تخصیص در سیستمهای همزمان (Concurrent Allocation)
چالش؟ اگر چند نخ همزمان حافظه درخواست کنند، سیستم باید با عملیات اتمیک یا قفلها (Locks) جلوی خراب شدن ساختار حافظه را بگیرد. اما این کار میتواند باعث کندی عملکرد شود.
راهحل؟ به هر نخ (Thread) یک منطقه تخصیص محلی (LAB) بدهیم که بتواند بدون نیاز به تعامل با بقیه نخها بهصورت مستقل حافظه بگیرد،.
فقط وقتی که LAB پر شد، نخ یک بلوک جدید از حافظه جهانی میگیرد.
مزایا
- کم شدن رقابت بین نخها
- افزایش سرعت تخصیص حافظه
- کاهش نیاز به عملیات اتمیک
تطبیق اندازهی LAB بر اساس میزان تخصیص
چالش؟ همهی نخها با یک سرعت یکسان حافظه مصرف نمیکنند! بعضیها سریعتر حافظه میگیرند و بعضیها کندتر.
راهحل؟ نخهایی که حافظه را سریع مصرف میکنند، بلوکهای بزرگتر بگیرند.
نخهای کممصرف، بلوکهای کوچکتر بگیرند.
تخصیص بر اساس پردازنده (Processor-based Allocation)
چالش؟ اگر نخها روی پردازندههای مختلف اجرا شوند، ممکن است LAB بعد از تعویض پردازنده دچار مشکل شود.
راهحل؟ به جای اختصاص دادن LAB به نخ، برای هر پردازنده یک LAB اختصاص بدهیم!
اینطوری وقتی یک نخ از یک پردازنده به پردازنده دیگر منتقل میشود، همچنان از LAB مخصوص آن پردازنده استفاده میکند.
مزایا
- کاهش تأخیر (Latency)
- عدم نیاز به مکانیزمهای پیچیده تنظیم اندازهی LAB
- بهبود عملکرد در سیستمهایی با تعداد زیاد نخهای در حال اجرا
کدام روش بهتر است؟
- اگر تعداد نخها کمتر از تعداد پردازندهها باشد، تخصیص بر اساس نخ بهتر است.
- اگر تعداد نخها خیلی زیاد باشد، تخصیص بر اساس پردازنده عملکرد بهتری دارد.
بهترین راه، سوییچ داینامیک بین این دو روش است.
تخصیص با لیستهای آزاد جداگانه (Segregated Free-Lists)
چالش؟ اگه نخها بخواهند از یک لیست آزاد مشترک (Free-List) استفاده کنند، ممکن است باعث رقابت زیاد و کاهش عملکرد شود.
راهحل؟ هر نخ، لیست آزاد مخصوص خودش را داشته باشد!
وقتی یک نخ بلوک جدیدی از حافظه میگیرد، سلولهای آزاد شده را در لیست خودش نگه میدارد تا بعداً راحتتر ازآنها استفاده کند.
مزایا
- کاهش رقابت بین نخها
- افزایش سرعت تخصیص حافظه
- هماهنگی بهتر با جمعکننده زباله (Garbage Collector)
چالش؟
اگر برنامهای مثل تولیدکننده-مصرفکننده (Producer-Consumer) باشد، ممکن است این روش باعث نامتعادل شدن تخصیص حافظه شود.
در این شرایط، باید یک حافظه مشترک برای تبادل دادهها ایجاد کنیم.
مسائل مهم در طراحی تخصیصدهنده حافظه
چالش؟ تخصیصدهنده حافظه نباید جدا از جمعکننده زباله طراحی شود!
نکات مهم:
جمعکنندههای غیربرنامهریزی (Non-Moving Collectors) معمولاً نیاز به تخصیص مبتنی بر لیست آزاد دارند.
جمعکنندههای کپیکننده (Copying Collectors) و فشردهسازی (Compacting Collectors) معمولاً از تخصیص ترتیبی (Sequential Allocation) استفاده میکنند.
در برخی سیستمها، ترکیبی از این روشها با فشردهسازی اضطراری (Emergency Compaction) استفاده میشود.
راهحلهای بهینهسازی:
استفاده از بیتمپ (Bitmaps) برای ثبت وضعیت بلوکها
کاهش سربار متادیتا (Metadata Overhead) با تخصیص بلوکی (Block-based Allocation)
استفاده از تخصیص Segregated-Fits برای افزایش سرعت تخصیص
چالش؟
تخصیصدهنده باید بهینه برای نوع جمعکننده زباله انتخاب شود.
سیستم باید حجم زیاد تخصیص در برنامههایی که از GC استفاده میکنند را در نظر بگیرد.