مدیریت حافظه دوستانه

تکنیک مدیریت حافظهٔ دوستانه یک الگوریتم برای مدیریت حافظه است که حافظه را به بخش‌هایی تقسیم می‌کند تا د خواست حافظه را تا آنجایی که ممکن است به‌طور مناسبی پاسخگو باشد. این سیستم حافظه را به دو نیم تقسیم می‌کند تا بهترین برازش را مطابق با دانلد کنوت انجام بدهد. سیستم رفاقتی در سال ۱۹۶۳ توسط هری مارکوویتز ابداع شده‌است، که در سال ۱۹۹۰ جایزه نوبل اقتصاد را دریافت کرده‌است و اولین بار توسط Kenneth C. Knowlton توصیف شده‌است (در سال ۱۹۶۵ منتشر شده‌است) سیستم مدیریت حافظهٔ دوستانه نسبتاً برای پیاده‌سازی آسان است. این سیستم از محدودیت‌های بخش بندی کار آمد و بهم آمیختن (یکی شدن) بلاک‌های حافظه حمایت می‌کند.

سیستم حافظهٔ رفاقتی چگونه کار می‌کند

فرم‌های گوناگونی از سیستم حافظه وجود دارد، اما رفاقتی دودویی که در آن هر بلاک به دو بلاک کوچکتر تقسیم می‌شود، ساده‌ترین و رایج‌ترین نوع آن هستند.

هر بلاک حافظه در این سیستم یک مرتبه دارد. در جایی که مرتبهٔ آن در بازهٔ یک عدد صحیح از ۰تا محدودهٔ بالایی مشخص شده‌است. بلاک‌ها در هر مرتبه دارای اندازه‌های متناسب با ۲ به توان مرتبه هستند، که هر بلاک دقیقآ دو برابر اندازهٔ بلاک‌هایی است که در یک مرتبه در محدودهٔ پایین‌تر هستند. توان دو اندازهٔ بلاک‌ها محاسبات آدرس را ساده می‌سازد، به این دلیل که همهٔ رفیق‌ها در یک ردیف از محدودهٔ آدرس روی حافظه هستند که توان‌هایی از دو می‌باشند. زمانی که یک بلاک بزرگتر تقسیم‌بندی می‌شود، این بلاک به دو بلاک کوچکتر تقسیم می‌شود و هر کدام از بلاک‌های کوچکتر یک رفیق یکتا برای دیگری می‌شود. یک بلاک بخش بندی شده فقط با یک بلاک رفیق یکتای خودش می‌تواند ترکیب شود که به یک بلاک بزرگتر از آن (که از آن به دو نیم شده بودند) باز سازی شوند.

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

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

برنامه‌نویس سپس روی نوشتن کد برای دستیابی به بالاترین مرتبهٔ ممکن که متناسب با فضای در دسترس از حافظهٔ باقی‌مانده می‌باشد، تصمیم‌گیری می‌کند.

از انجایی که کل حافظهٔ در دسترس به سیستم کامپیوتری داده شده، ممکن است توانی از دو به ازای کوچکترین اندازه‌های بلاک نباشد، بزرگترین اندازهٔ بلاک ممکن است کل حافظهٔ سیستم را پوشش ندهد. به عنوان نمونه، اگر سیستم 2000k حافظهٔ فیزیکی داشته باشد و اندازهٔ بلاک مرتبهٔ 0,4k باشد، محدودهٔ بالایی مرتبهٔ ۸می‌شود. از آنجایی که یک بلاک مرتبهٔ ۸ (۲۵۶ تا بلاک مرتبهٔ ۰ متناظر با 1024k) بزرگترین بلاک متناسب با حافظه خواهد بود؛ بنابراین این امکان‌پذیر است که یک حافظهٔ فیزیکی کامل را به یک بخش بزرگ واحد تخصیص دهیم. باقی ماندهٔ 967k از حافظه ممکن است به بلاک‌های کوچکتر تخصیص داده شود.

به عنوان تمرین

شرح ذیل یک مثالی است در رابطه با اینکه وقتی یک برنامه‌ای در خواست حافظه می‌کند چه اتفاقی می‌افتد. بیایید در رابطه با این سیستم صحبت کنیم. اندازهٔ کوچکترین بلاک ممکن ۶۴ کیلو بایت هست، محدودهٔ بالایی برای مرتبهٔ ۴ هست، که بزرگترین تخصیص بلاک ممکن را نتیجه می‌دهد. در اندازهٔ ۲ به توان ۴ تا 64k برابر با 1024k می‌شود. در ذیل یک حالت ممکن از سیستم پس از در خواست‌های حافظهٔ گوناگون نمایش داده می‌شود:

Step	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K	64K
۱	24
۲٫۱	23								23
۲٫۲	22				22				23
۲٫۳	21		21		22				23
۲٫۴	20	20	21		22				23
۲٫۵	A: 20	20	21		22				23
۳	A: 20	20	B: 21		22				23
۴	A: 20	C: 20	B: 21		22				23
۵٫۱	A: 20	C: 20	B: 21		21		21		23
۵٫۲	A: 20	C: 20	B: 21		D: 21		21		23
۶	A: 20	C: 20	21		D: 21		21		23
۷٫۱	A: 20	C: 20	21		21		21		23
۷٫۲	A: 20	C: 20	21		22				23
۸	20	C: 20	21		22				23
۹٫۱	20	20	21		22				23
۹٫۲	21		21		22				23
۹٫۳	22				22				23
۹٫۴	23								23
۹٫۵	24

این تخصیص می‌تواند به طریقهٔ زیر اتفاق بیفتد:

1. موقعیت آغازین
2. برنامهٔ A حافظهٔ 34 k را در خواست می‌کند (در مرتبهٔ ۰)
   1. هیج بلاک مرتبهٔ ۰ ای در دسترس نیست، بنابراین بلاک مرتبهٔ ۴ دو نیم می‌شود و دو بلاک مرتبهٔ ۳ می‌سازد.
   2. هنوز بلاک مرتبه ی۰ در دسترس نیست، بنابراین اولین بلاک مرتبهٔ ۳ به دو نیم می‌شود و دو بلاک با مرتبهٔ ۲می‌سازد.
   3. هنوز بلاک مرتبهٔ ۰ در دسترس نیست، بنابراین اولین بلاک مرتبهٔ ۲ به دو نیم می‌شود و دو بلاک با مرتبهٔ ۱ می‌سازد.
   4. هنوز بلاک مرتبهٔ ۰ در دسترس نیست، بنابراین اولین بلاک مرتبه ی۱ به دو نیم می‌شود و دو بلاک با مرتبهٔ ۰ می‌سازد.
   5. در حال حاضر بلاک مرتبهٔ ۰ در دسترس است پس به A تخصیص می‌یابد.
3. برنامه یBدر خواست حافظهٔ 66k را می‌کند (مرتبه ی۱), یک بلاک مرتبهٔ ۱ در دسترس است بنابراین به Bتخصیص می‌یابد.
4. برنامهٔ Cدر خواست حافظهٔ 35kرامی‌کند (مرتبهٔ ۰), یک بلاک مرتبهٔ ۰ در دسترس است، بنابراین به C تخصیص می‌یابد.
5. برنامهٔ D , 67k حافظه را در خواست می‌کند. (مرتبهٔ ۱)
   1. هیچ بلاک مرتبهٔ ۱ ای در دسترس نیست بنابراین بلاک مرتبهٔ ۲ به دو نیم می‌شود و ۲ بلاک مرتبهٔ ۱ می‌سازد.
   2. در حال حاضر بلاک مرتبهٔ ۱ در دسترس است پس به D تخصیص می‌یابد.
6. برنامهٔ Bحافظه اش را آزاد می‌کند، یک بلاک مرتبهٔ ۱ آزاد می‌شود.
7. برنامه یDحافظه اش را آزاد می‌کند.
   1. یک بلاک مرتبهٔ ۱ آزاد شده‌است.
   2. از آنجایی که بلاک رفیق بلاک تازه آزاد شده، آزاد است ۲ بلاک از مرتبهٔ ۱ به یک بلاک از مرتبهٔ ۲ ترکیب می‌شوند.
8. برنامهٔ A حافظه اش را آزا د می‌کند، یک بلاک مرتبهٔ ۰ آزاد می‌شود.
9. برنامهٔ C حافظه اش را آزاد می‌کند.
   1. یک بلاک مرتبهٔ ۰ آزاد می‌شود.
   2. از آنجایی که بلاک رفیق بلاک تازه آزاد شده، آزاد است ۲ بلاک از مرتبه ی۰ به یک بلاک از مرتبهٔ ۱ ترکیب می‌شوند.
   3. از آنجایی که بلاک رفیق بلاک تازه آزاد شده، آزاد است ۲ بلاک از مرتبهٔ ۱ به یک بلاک از مرتبهٔ ۲ ترکیب می‌شوند.
   4. از آنجایی که بلاک رفیق بلاک تازه آزاد شده، آزاد است ۲ بلاک از مرتبهٔ ۲ به یک بلاک از مرتبهٔ ۳ ترکیب می‌شوند.
   5. از آنجایی که بلاک رفیق بلاک تازه آزاد شده، آزاد است ۲ بلاک از مرتبهٔ ۳ به یک بلاک از مرتبهٔ ۴ ترکیب می‌شوند.

همانطوری که می‌بینید، در پی در خواست حافظه به مانند زیر چه اتفاقی می‌افتد.

• اگر حافظه اختصاص داده شده باشد:

1. دنبال بخش با اندازهٔ مناسب از حافظه (حداقل ۲ به توان kبلاک که بزرگتر یا مساوی با حافظهٔ در خواستی است) می‌گردد.
   1. اگرپیدا شد، به برنامه تخصیص می‌یابد.
   2. اگر پیدا نشد، تلاش می‌کند تا بخش مناسبی از حافظه را بسازد. سیستم به صورت زیر تلاش می‌کند:
      1. بخش حافظهٔ آزاد بزرگتر از حافظهٔ در خواستی را به دو نیم می‌کند.
      2. اگر محدودهٔ پایین‌تر دستیابی شد، آنگاه مقدار حافظه را تخصیص می‌دهد.
      3. به گام اول بر می‌گردد. (به دنبال بخش حافظه‌ای با اندازهٔ مناسب می‌گردد)
      4. این فرایند را تکرار می‌کند تا بخش حافظه‌ای مناسب را پیدا کند.

• اگر حافظه آزاد شده باشد:

1. بلاک حافظه را آزاد می‌کند.
2. دنبال بلاک همسایه می‌گردد (که آیا آزاد هست یا نه)
3. اگرآزاد است ۲ بلاک را به یک بلاک ترکیب می‌کند و به گام دوم برمیگردد و این فرایند را تکرا رمی‌کند تا محدودهٔ بالایی دستیابی شود. (همهٔ حافظه آزاد شود) یا با هیچ همسایه‌ای با بلاک آزاد برخورد نکند.

پیاده‌سازی و کارایی

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

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

به هر حال هنوز مشکل تکه‌تکه شدن داخلی وجود دارد. حافظه به هدر می‌رود به خاطر اینکه حافظهٔ در خواست شده یک مقدار کمی از اندازهٔ کوچکترین بلاک کمتر است، اما خیلی کوچکتر از بلاک بزرگ است.

برای اینکه سیستم تخصیص رفاقتی کار کند، به یک برنامه‌ای که 66k حافظه را در خواست کرده‌است، 128k اختصاص یافته‌است، که در نتیجه 62k حافظه به هدر رفته است. این مشکل می‌تواند با تخصیص قطعه (slab allocation) حل می‌شود؛ که به بالای درشت‌ترین اختصاص رفاقتی لایه بندی می‌شود تا تخصیص (fine–grain) بیشتری را فراهم کند.

یک نسخه از الگوریتم تخصیص حافظه با جزییات توسط دانلد کنوت در جلد ۱ از کتاب هنر برنامه‌نویسی کامپیوتر شرح داده شده‌است. در امتداد اختصاص‌های گوناگون دیگر برای مدیریت کردن حافظه‌های درون بلاکی، هستهٔ لینوکس همچنین برای سیستم رفاقتی به همراه اصلاحات بیشتری برای به حد اقل رساندن تکه‌تکه شدن خارجی، استفاده می‌شود. در میان دیگران و تکنیک‌های رفاقتی jemalloc یک اختصاص دهندهٔ حافظهٔ مدرن است که به کار گرفته می‌شود.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Buddy memory allocation». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۵ ژوئن ۲۰۱۳.