مرتب سازی حافظه
"این مقاله در حال ترجمه از ویکی انگلیسی است لطفا حذف نشود"
مرتب سازی حافظه دسترسی به حافظه کامپیوتر توسط یک CPU را توصیف می‌کند. این اصطلاح می‌تواند به مرتب سازی حافظه تولید شده توسط کامپایلر در طول زمان کامپایل یا به مرتب سازی حافظه تولید شده توسط یک CPU در طول زمان اجرا اشاره داشته باشد.
در ریزپردازنده‌های مدرن، مرتب‌سازی حافظه توانایی CPU برای ترتیب‌دهی مجدد عملیات حافظه را مشخص می‌کند – این یک نوع اجرای خارج از نظم است. از مرتب سازی مجدد حافظه می‌توان برای استفاده کامل از پهنای باند گذرگاه انواع مختلف حافظه مانند کش‌ها و بانک‌های حافظه استفاده کرد.
در اکثر سیستم‌های تک پردازنده مدرن عملیات حافظه در جهت مشخص شده توسط کد برنامه اجرا نمی‌شود. در برنامه‌های تک رشته‌ای، به نظر می‌رسد که همه عملیات‌ها به ترتیب مشخص شده اجرا شده‌اند، شامل تمام اجراهای خارج از نظم پنهان برای برنامه‌نویس - اما در محیط‌های چند رشته‌ای (یا هنگام اتصال با سایر سخت‌افزارها از طریق گذرگاه‌های حافظه) این موضوع می‌تواند منجر به چالش‌ها و مسائلی شود. برای جلوگیری از این مشکلات می‌توان از موانع حافظه در این موارد استفاده کرد.
اکثر زبانهای برنامه‌نویسی مفهومی از رشته اجرا دارند که دستورها را به ترتیب تعریف شده اجرا می‌کند. کامپایلرهای سنتی عبارت‌های سطح بالا را به دنباله ای از دستورالعمل‌های سطح پایین نسبت به شمارنده برنامه در سطح ماشین‌های اساسی ترجمه می‌کند.
اثرات اجرا در دو سطح قابل مشاهده است: در کد برنامه در سطح بالا، و در سطح ماشین همان‌طور که توسط رشته‌ها یا عناصر پردازشی دیگر در برنامه‌نویسی همزمان مشاهده می‌شود، یا در هنگام اشکال‌زدایی هنگام استفاده از کمک اشکال‌زدایی سخت‌افزاری با دسترسی به وضعیت ماشین (برخی از پشتیبانی برای این اغلب به‌طور مستقیم در CPU یا میکروکنترلر به عنوان مدار مستقل که عملکردی جدا از هسته اجرایی دارد و حتی زمانی که خود هسته برای بازرسی ایستا از وضعیت اجرای خود متوقف می‌شود، به کار خود ادامه می‌دهد، قرار گرفته‌است) مرتب سازی حافظه زمان کامپایل به دیدگاه اول مربوط می‌شود و به دیدگاه‌های دیگر ارتباطی ندارد.
در طول کامپایل، دستورالعمل‌های سخت‌افزاری اغلب با دانه‌بندی دقیق‌تر از آنچه در کد سطح بالا مشخص شده‌است، تولید می‌شوند. اثر قابل مشاهده اولیه در برنامه‌نویسی رویه ای، تخصیص یک مقدار جدید به یک متغیر است. دستور print از عبارتی پیروی می‌کند که به متغیر sum مقدار اختصاص می‌دهد بنابراین وقتی دستور print به متغیر محاسبه شده codice_1 ارجاع می‌دهد، نتیجه را به عنوان یک اثر قابل مشاهده از دنباله اجرای قبلی ارجاع می‌دهد. همان‌طور که در قواعد دنباله برنامه تعریف شده‌است، وقتی دستور codice_2 به sum ارجاع می‌دهد، مقدار codice_1 باید همان تخصیص اخیراً اجرا شده به متغیر codice_1 باشد (در این مورد عبارت بلافاصله قبلی).
در سطح ماشین، تعداد کمی از ماشین‌ها می‌توانند مجموع سه عدد را در یک دستورالعمل واحد محاسبه کنند، بنابراین کامپایلر باید این عبارت را به دو عملیات جمع ترجمه کند. اگر مفاهیم زبان برنامه، کامپایلر را برای ترجمه عبارت به ترتیب چپ به راست محدود کند (برای مثال)، کد تولید شده به نظر می‌رسد که گویی برنامه‌نویس عبارات زیر را در برنامه اصلی نوشته‌است: اگر کامپایلر مجاز باشد از خاصیت تداعی جمع استفاده کند، ممکن است عبارات زیر را ایجاد کند: اگر کامپایلر همچنین اجازه استفاده از ویژگی جابجایی جمع را داشته باشد، ممکن است عبارات زیر را ایجاد کند: توجه داشته باشید که نوع داده عدد صحیح در اکثر زبان‌های برنامه‌نویسی فقط از جبر برای اعداد صحیح ریاضی در صورت عدم سرریز اعداد صحیح پیروی می‌کند و اینکه محاسبات ممیز شناور در نوع داده‌های ممیز شناور موجود در اکثر زبان‌های برنامه‌نویسی در خطاهای گرد کردن جابجا نمی‌شود بلکه باعث ایجاد خطا در ترتیب عبارات قابل مشاهده در تفاوت‌های کوچک نتیجه محاسبه شده می‌شود (تفاوت‌های اولیه کوچک ممکن است در یک محاسبه طولانی‌تر به تفاوت‌های قراردادی بزرگ تبدیل شوند).
اگر برنامه‌نویس نگران سرریز اعداد صحیح یا اثرات گرد کردن در ممیز شناور باشد، همان برنامه را می‌توان در سطح بالای اصلی به صورت زیر کدگذاری کرد:
بسیاری از زبان‌ها مرز دستور را به‌عنوان یک نقطه توالی در نظر می‌گیرند، که تمام اثرات یک عبارت را مجبور می‌کنند قبل از اجرای دستور بعدی کامل شوند. این کار کامپایلر را مجبور می‌کند تا کدی مطابق با ترتیب بیان شده تولید کند. با این حال، دستورات اغلب پیچیده‌تر هستند و ممکن است شامل فراخوانی‌های تابع داخلی باشند. در سطح ماشین، فراخوانی یک تابع معمولاً شامل تنظیم یک پشته تماس برای فراخوانی تابع است که شامل خواندن و نوشتن بسیاری در حافظه ماشین است. در بیشتر زبان‌های کامپایل شده، کامپایلر آزاد است تا فراخوانی توابع codice_5, codice_6 و codice_7 هر طور که مناسب می‌داند ترتیب دهد و در نتیجه ترتیب حافظه برنامه را در مقیاس بزرگ تغییر دهد. در یک زبان برنامه‌نویسی تابعی خالص، فراخوانی تابع از داشتن اثرات جانبی بر روی وضعیت برنامه قابل مشاهده (غیر از مقدار بازگشتی آن) منع شده‌است و تفاوت در ترتیب حافظه ماشین به دلیل ترتیب فراخوانی تابع، برای مفاهیم برنامه بی‌اهمیت خواهد بود. در زبان‌های رویه‌ای، توابعی که نامیده می‌شوند ممکن است دارای اثرات جانبی باشند، مانند انجام یک عملیات ورودی/خروجی، یا به‌روزرسانی سراسری مقدار یک متغیر، که هر دوی این‌ها اثرات قابل مشاهده با مدل برنامه ایجاد می‌کنند.
مجدداً، برنامه‌نویسی که به این آثار توجه دارد، می‌تواند در بیان برنامه منبع اصلی سختگیرتر شود: در زبان‌های برنامه‌نویسی که مرز دستور به عنوان یک نقطه توالی تعریف می‌شود، فراخوانی توابع codice_5, codice_6 و codice_7 ف باید به ترتیب دقیق اجرا شود.
اکنون همان جمع بیان شده با اشاره گر غیرمستقیم را در زبانی مانند C یا C++ در نظر بگیرید که از اشاره گرها پشتیبانی می‌کند: ارزیابی عبارت codice_11 به نام " عدم ارجاع " یک اشاره گر است و شامل خواندن از حافظه در مکانی است که با مقدار فعلی codice_12 مشخص شده‌است. آثار خواندن از یک اشاره گر توسط مدل حافظه معماری تعیین می‌شود. هنگام خواندن از حافظه استاندارد برنامه، به دلیل ترتیب عملیات خواندن در حافظه، هیچ اثر جانبی وجود ندارد. در برنامه‌نویسی سیستم‌های جاسازی شده، بسیار رایج است که I/O با نقشه حافظه داشته باشیم که در آن خواندن و نوشتن در حافظه موجب عملیات I/O می‌شود، یا حالت عملیاتی پردازنده را تغییر می‌دهد، که آثار جانبی بسیار قابل مشاهده ای هستند. برای مثال بالا، فعلاً فرض کنید که اشاره گرها به حافظه برنامه معمولی اشاره می‌کنند، بدون این آثار جانبی. کامپایلر آزاد است که این خواندن‌ها را به ترتیبی که صلاح می‌داند دوباره ترتیب دهد و هیچ عارضه جانبی قابل مشاهده ای در برنامه وجود نخواهد داشت.
اگر "مقدار تخصیص داده شده" نیز اشاره گر غیرمستقیم باشد چه؟ در اینجا مفهوم زبان بعید است که به کامپایلر اجازه دهد این را به صورت زیر جدا کند: این در اکثر موارد کارآمد تلقی نمی‌شود، و نوشتن اشاره‌گر عوارض جانبی بالقوه‌ای روی وضعیت قابل مشاهده ماشین دارد. از آنجا که کامپایلر مجاز نیست که این تغییر و تحول تقسیم خاص را ایجاد کند، تنها نوشتن در محل حافظه از codice_1 منطقا باید سه اشاره‌گر خواندن را در عبارت مقدار دنبال کند.
با این حال، فرض کنید که برنامه‌نویس نگران مفهوم قابل مشاهده سرریز اعداد صحیح باشد و عبارت را به صورت سطح برنامه به صورت زیر جدا کند: دستور اول دو خواندن حافظه را رمزگذاری می‌کند، که باید قبل از اولین نوشتن codice_14 باشد (به هر ترتیب). دستور دوم دو خواندن حافظه (به هر ترتیب) را رمزگذاری می‌کند که باید قبل از به روز رسانی دوم codice_14 باشد. این ترتیب دو عملیات جمع را تضمین می‌کند، اما به‌طور بالقوه یک مشکل جدید در نام مستعار آدرس را معرفی می‌کند: هر یک از این اشاره گرها می‌توانند به‌طور بالقوه به یک مکان حافظه اشاره کنند.
برای مثال، بیایید در این مثال فرض کنیم که codice_16 و codice_14 مستعار در یک مکان حافظه دارند و هر دو نسخه برنامه را با codice_14 برای هر دو بازنویسی کنیم. اینجا هیچ مشکلی وجود ندارد. مقدار اصلی چیزی که ما در ابتدا به عنوان codice_16 نوشتیم با انتساب به codice_14 ، و همچنین مقدار اصلی codice_14 اما این در وهله اول بازنویسی شده بود و نگرانی خاصی ندارد. در اینجا مقدار اصلی codice_14 قبل از اولین دسترسی بازنویسی می‌شود و در عوض معادل جبری را بدست می‌آوریم: که یک مقدار کاملاً متفاوت به codice_14 به دلیل بازآرایی دستورات اختصاص می‌دهد.
به دلیل اثرات احتمالی نام‌های مستعار، تنظیم مجدد عبارات اشاره گر بدون خطر اثرات قابل مشاهده برنامه دشوار است. در حالت معمول، ممکن است هیچ نام مستعاری وجود نداشته باشد، بنابراین به نظر می‌رسد که کد به‌طور معمول مانند قبل اجرا می‌شود. اما در مورد لبه ای که نام مستعار وجود دارد، خطاهای برنامه شدیدی می‌تواند ایجاد شود. حتی اگر این موارد لبه در اجرای معمولی به‌طور کامل وجود نداشته باشند، در را برای یک دشمن مخرب باز می‌کند تا در جایی که نام مستعار وجود دارد، ورودی ایجاد کند، که به‌طور بالقوه منجر به یک سوء استفاده امنیتی رایانه می‌شود.
یک مرتب سازی مجدد امن برنامه قبلی به شرح زیر است: در نهایت مورد غیر مستقیم را با فراخوانی توابع اضافه شده در نظر بگیرید: کامپایلر ممکن است انتخاب کند که ارزیابی codice_24 و codice_25 قبل از فراخوانی تابع صورت بگیرد، ممکن است ارزیابی codice_25 را تا بعد از فراخوانی تابع codice_5 یا ارزیابی codice_24 را تا بعد از فراخوانی تابع codice_6 تعویق بیندازد. اگر تابع codice_5 و codice_6 عاری از اثرات جانبی قابل مشاهده برنامه باشند، هر سه گزینه برنامه ای با همان جلوه‌های برنامه قابل مشاهده تولید می‌کنند. اگر اجرای codice_5 یا codice_6 دارای اثر جانبی هر نوشتن اشاره‌گری باشد که مستعار با نشانگرهای codice_34 یا codice_35 ، این سه گزینه می‌توانند جلوه‌های برنامه قابل مشاهده متفاوتی را ایجاد کنند.
به‌طور کلی، زبان‌های کامپایل شده به اندازه کافی در مشخصات خود دقیق نیستند تا کامپایلر به‌طور رسمی در زمان کامپایل تعیین کند که کدام نشانگرها به‌طور بالقوه نام مستعار دارند و کدام‌ها نیستند. ایمن‌ترین اقدام این است که کامپایلر فرض کند که همه اشاره گرها به‌طور بالقوه همیشه نام مستعار هستند. این سطح از بدبینی محافظه کارانه در مقایسه با این فرض خوش‌بینانه که هیچ نام مستعار وجود ندارد، تمایل به ایجاد عملکرد بسیار بد دارد.
در نتیجه، بسیاری از زبان‌های کامپایل‌شده سطح بالا، مانند C/C++، به‌گونه‌ای تکامل یافته‌اند که دارای مشخصات معنایی پیچیده و پیچیده‌ای در مورد اینکه کامپایلر در کجا مجاز است در مرتب‌سازی مجدد کدها به منظور دستیابی به بالاترین عملکرد ممکن، مفروضات خوش‌بینانه‌ای داشته باشد، و جایی که کامپایلر باید برای جلوگیری از خطرات معنایی، مفروضات بدبینانه ای را در مرتب سازی مجدد کد ایجاد کند.
تا حد زیادی بزرگترین دسته از عوارض جانبی در یک زبان رویه ای مدرن شامل عملیات نوشتن حافظه است، بنابراین قوانین مربوط به ترتیب حافظه جزء غالب در تعریف معنایی ترتیب برنامه هستند. ترتیب مجدد فراخوانی‌های توابع بالا ممکن است به نظر متفاوت باشد، اما این معمولاً به نگرانی‌هایی در مورد تأثیرات حافظه داخلی توابع فراخوانی شده در تعامل با عملیات حافظه در عبارتی که فراخوانی تابع را تولید می‌کند، تبدیل می‌شود.
کامپایلرهای مدرن گاهی اوقات با استفاده از یک مفهومی به نام قاعده as-if یک گام جلوتر می‌روند، که در آن هرگونه ترتیب مجدد (حتی در بین عبارات) در صورت عدم تأثیر قابل مشاهده نتایج مفهومی برنامه مجاز است. بر اساس این قانون، ترتیب عملیات در کد ترجمه شده می‌تواند به شدت از ترتیب برنامه مشخص شده متفاوت باشد. اگر کامپایلر مجاز باشد در مورد عبارات اشاره گر متمایز بدون همپوشانی مستعار در موردی که نام مستعاری وجود دارد، مفروضات خوش‌بینانه داشته باشد (این امر معمولاً به عنوان یک برنامه نامناسب طبقه‌بندی می‌شود که رفتار نامشخصی از خود نشان می‌دهد)، نتایج نامطلوب تبدیل یک کد بهینه سازی تهاجمی غیرقابل حدس زدن قبل از اجرای کد یا بازرسی مستقیم کد می‌باشد. قلمرو رفتار تعریف نشده تظاهرات تقریباً نامحدودی دارد.
این وظیفه برنامه‌نویس است که با مشخصات زبان مشورت کند تا از نوشتن برنامه‌های بد شکلی که در آن معنای به‌طور بالقوه در نتیجه هر گونه بهینه سازی کامپایلر قانونی تغییر می‌کند، جلوگیری کند. Fortran به طور سنتی بار زیادی را بر دوش برنامه‌نویس قرار می‌دهد تا از این مسائل آگاه باشد، زبان‌های برنامه‌نویسی C و C++ سیستم‌ها چندان از این موارد عقب نیستند.
برخی از زبان‌های سطح بالا ساختارهای نشانگر را به کلی حذف می‌کنند، زیرا این سطح هوشیاری و توجه به جزئیات بسیار بالاست و حتی در بین برنامه‌نویسان حرفه‌ای نمی‌توان آن را به‌طور قابل اعتماد حفظ کرد.
درک کامل معنایی مرتب سازی حافظه به عنوان یک تخصص محرمانه حتی در میان گروهی از برنامه نویسان سیستم‌های حرفه ای که معمولاً در این زمینه موضوعی بهترین هستند، در نظر گرفته می‌شود. اکثر برنامه نویسان به درک کافی از این مسائل در حوزه معمولی تخصص برنامه‌نویسی خود رضایت می‌دهند. در نهایت تخصص در معنای‌شناسی مرتب سازی حافظه، برنامه نویسانی هستند که چارچوب‌های نرم‌افزاری را برای پشتیبانی از مدل‌های محاسباتی همزمان ایجاد می‌کنند.