تخصیص حافظه به صورت پویا (Dynamic Memory Allocation)
در جدول زیر مهمترین دستورات لازم برای اجرای دستور العمل های مربوط به درخواست و آزادسازی حافظه آورده شده است.
اشارهگرهای معلق
• اشارهگرهای معلق در زبانهای برنامه نویسی، اشاره گرهایی هستند که به یک شیء مشخص اشاره نمی‌کنند.
• اشاره‌گر معلق زمانی به وجود می‌آید که یک شی حذف یا آزادسازی می‌شود، بدون اینکه مقدار یک اشاره‌گر تغییر داده شده باشد. "در نتیجه آن اشاره‌گر به مکانی اشاره می‌کند که دیگر وجود ندارد."
• حتی ممکن است سیستم مکان قبلی حافظه که آزاد شده بود را به فرایند دیگری داده باشد، در این صورت آن اشاره‌گر به دادهای متفاوت اشاره می‌کند.
دلایل بروز اشارهگرهای معلق
در بسیاری از زبان های برنامه نویسی، مانند C، وقتی یک شی از محدوده خارج می‌شود یا صریحاً دستور خالی شدن دریافت می‌کند، اشارهگرهایی که به ان شی اشاره میکنند تغییر نمی‌کنند.
به عنوان مثال به کد زیر توجه کنید:
{
char* dp = NULL;
/* ... */
{
char c;
dp = &c;
} /* c falls out of scope */
/* dp is now a dangling pointer*/
}
یک راه دیگر به وجود امدن اشاره‌گر معلق، استفاده همزمان تابع malloc و در ادامه free است. در واقع بعد از اینکه یک اشاره‌گر با malloc مقداردهی می‌شود توسط free خالی می‌شود و اشاره‌گر استفاده شده معلق می‌شود. به کد زیر توجه کنید:
راه حل
باید بعد از آزاد کردن حافظه توسط دستور free خود اشاره گر را نیز برابر با مقدار پوچ قرار دهیم.
در زبانهای برنامه نویسی سطح بالا، مانند سی شارپ و JAVA، امکان بروز اشاره‌گر معلق وجود ندارد، چرا که هیچ روش مستقیمی برای خالی کردن حافظه در این زبان تعبیه نشده و تمام ازادسازی حافظه توسط زباله روب (garbage collector) انجام می‌شود.
پیشرفت های اخیر در تحلیل ثابت برنامه‌ها میتواند کمی از این چالش ها را کاهش دهد.
برای مثال، Cherem, Princehouse and Rugina یک تکنیک ویژه تحلیل گراف کنترل جریان را معرفی کردند که بلوک های حافظه اختصاص داده شده را در برنامه زیرنظر می‌گیرد که عملیات های free() فراموش شده را تشخیص دهد تا باعث نشت حافظه (memory leak) نشوند. و یا عمیات های free() زود هنگام را تشخیص دهد تا باعث ایجاد اشاره‌گر های معلق نشود.
علاوه بر اختصاص داده توسط کاربر، سیستم های زمان-اجرا (run-time) اغلب داده هایی را تخصیص می‌دهند که عمر قابل پیش بینی ندارند و برنامه نویس اصلا از وجود آن ها خبر ندارد.
تولید دستور العمل هایی برای آزادسازی این داده ها ممکن است بسیار پیچیده باشد.
راه حل؟؟
تلاش ها برای حل این مشکلات منجر به تکنیک هایی برای آزادسازی خودکار داده های استفاده نشده با آزاد سازی حافظه به صورت ضمنی (implicit) شده است.
در مباحث پیش رو، ما درباره تکنیک هایی برای تخصیص داده به همراه آزادسازی صریح (explicit) حافظه توسط برنامه نویس و تخصیص داده به همراه آزادسازی ضمنی (implicit) حافظه که معمولا garbage collection نامیده می‌شود، می‌پردازیم.
در بیشتر سیستم ها، روال پایه ای تخصیص حافظه به این صورت است که یک بلوک استفاده نشده به میزان حجم درخواست شده از حافظه را پیدا می‌کند و آن را به عنوان حافظه استفاده شده علامت گذاری می‌کند و یک اشاره‌گر به آن بلوک را بر می‌گرداند. اگر همچین بلوکی وجود نداشته باشد نتیجه مختلف است: ممکن است یک اشاره‌گر بی‌مقدار (null) برگشت داده شود، یا یک خطا نمایان شود و یا برنامه خاتمه یابد.
روش های تخصیص حافظه
• به صورت bitmap
• به صورت بیت علامت
اگر بخواهیم از منظر کاربر به این تکه از حافظه نگاه کنیم آن را block می نامیم و اگر بخواهیم از منظر تخصیص دهنده حافظه به آن نگاه کنیم آن را chunk می نامیم.
همانگونه که در تصویر زیر مشاهده می کنید block زیرمجموعه ای از chunk است و مکان مورد نظر برای نگه داری داده است ولی chunk یکسری اطلاعات بیشتری نسبت به block دارد.
یکی از این اطلاعات اضافه وجود یک بیت مشخص برای نشان دادن مورد استفاده بودن یا نبودن آن بلاک است. یکی دیگر از این اطلاعات اضافه نشان دادن مقدار حافظه آن بلاک است. در واقع chunk یکسری اطلاعات مدیریتی بیشتری از بلاک در اختیار ما قرار می دهد.
ساختار حافظه
همانگونه که در تصویر زیر هم مشاهده می کنید حافظه (هرم) از یکسری chunk های پشت سر هم تشکیل شده است.
روش کار malloc به چه صورت است؟
همانگونه که در تصویر زیر هم مشاهده می کنید روال به این صورت است که هنگامی که دستور تخصیص حافظه به مقدار N بایت می آید malloc شروع به جستجو از ابتدای حافظه هرم کرده و با چک کردن بیت های استفاده شده و مقدار حافظه به دنبال حافظه با مقدار درخواست شده می گردد. هنگامی که به chunk مورد نظر رسید دو حالت وجود دارد. یکی اینکه حافظه chunk پیدا شده دقیقا برابر با مقدار درخواست شده است که در این صورت اشاره گر به آن chunk را بر می گرداند. دو این که حافظه پیدا شده مقدارش بیشتر از حافظه مورد نیاز است که در این صورت chunk یافت شده رو به 2 chunk تقسیم می کند و اولین chunk تقسیم شده مقدارش برابر با مقدار درخواست شده است و chunk دوم مقدارش برابر است با مقدار حافظه chunk اولیه منهای مقدار حافظه مورد نیاز.
بعد از انجام فرایند تقسیم chunk ها یک اشاره گر به chunk اولی را به سمت برنامه برمیگرداند.
فرایند آزادسازی حافظه free هم به همین صورت انجام می گیرد.
اما نکته ی مهمی که وجود دارد این است که اگر دستور malloc کل حافظه را جستجو کرد ولی نتوانست حافظه درخواست شده مورد نیاز را پیدا کند، تکلیف چیست؟
راهکار ها
بهینه سازی هایی برای تخصیص حافظه
پیشتر به این موضوع پرداختیم که هنگام تخصیص حافظه مورد نیاز برنامه نیاز است تا یک بار تمام حافظه جستجو شود (linear search) تا حافظه مورد نظر پیدا شود. حال اگر این مرحله شکست خورد بار دیگر نیاز است تا حافظه پیمایش شود تا حافظه (chunk) های کوچک را با یک دیگر ادغام کنیم. بدین ترتیب کارایی (performance) به شدت پایین می آید.
راهکار ها
یکی از راهکار ها این است تا chunk های آزاد حافظه را درون یک لیست پیوندی قرار بدهیم تا هنگام تخصیص حافظه لازم نباشد تا کل حافظه (اعم از حافظه های استفاده شده و آزاد) پیمایش شود. بدین ترتیب اگر لازم باشد میتوان chunk را تقسیم کرد و یا اگر حافظه ای آزاد شد به سادگی آن را به لیست پیوندی مان اضافه کنیم.
دستاورد
جستجوی خطی میان کل chunk های حافظه ====> جستجوی خطی صرفا میان chunk های آزاد حافظه
راهکار بهتر؟
یک روش پیچیده تر این است که chunk های با مقدار حافظه های بین بازه های مشخصی را درون یک لیست پیوندی قرار دهیم و تمامی این لیست های پیوندی را درون یک لیست پیوندی قرار دهیم. بازه ها هم میتواند به عنوان مثال توان های 2 باشند.
به تصویر زیر توجه کنید:
دستاورد
پیچیدگی زمانی====> (تقريبا) برابر با زمان ثابت (Constant Time)
منبع: Modern Compiler Design by Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs, Koen Langendoen
