مقصر دانستن ویلیامز به علت متوجه نشدن اینکه اطلس یکی از گمان های فرضی الگوریتمش را باطل کرده است، کار بسیار غیرمنصفانه و غیر مستدلی است: تنها ادراک مشاهدات را ممکن می سازد. حقیقت این است که ۴۶ سال بعد اغلب متخصصان سی اس هنوز حافظه مجازی را به عنوان یک امر عادی درنظر نمی گیرند. این برای سی اس منظم و حرفه ای مایه خجالت است، بدون توجه به اتلاف مقدار زیادی از سخت افزار و ابزار الکتریکی.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

شبیه سازی کارایی: اجازه دهید که یک سری حقایق شبیه سازی شده را روی جدول به شما نشان دهم. نمودار شکل ۲-۶ زمان اجرای باینری هیپ و نسخه ی جدید بی هیپ^[۱۳۷]را برای یک میلیون آیتم روی یک ماشین ۶۴ بیتی نشان می دهد.
شکل ۲-۶ زمان اجرای باینری هیپ و بی هیپ
محور افقی فشار وی ام^[۱۳۸] است، در مقدار فضای آدرسی که در حافظه ی ابتدایی مستقر نیست اندازه گیری می شود، چون کرنل آن را درون حافظه ی ثانویه صفحه بندی می کند. محور عمودی سمت چپ مقدار اجرا در ثانیه را نشان می دهد(مقیاس لوگاریتم)، و محور عمودی سمت راست نرخ دو زمان اجرا را نشان می دهد(باینری هیپ و بی هیپ).
بیایید مرتبه ی بزرگی را به دست آوریم. وقتی روی قسمت چپ زوم می کنیم(شکل ۲-۷)، می بینیم که درواقع وجود دارد یک فاکتور ۱۰ تفاوتی در زمان دو الگوریتم وقتی که اجرا می شود تحت مجموع فشار وی ام : فقط ۸ تا ۱۰ صفحه از ۱۹۵۴ صفحه ی اختصاص یافته شده در حافظه ی مقدماتی در همان زمان وجود دارد.
شکل ۲-۷ مقایسه زمان اجرای بی هیپ و باینری هیپ به صورت زوم قسمت چپ
آیا شما چون ادعای من در مورد مرتبه ی بزرگی بر اساس تنها یک مورد نهایتا گوشه ای است گمان می کنید جعلی است؟ اگر شما اینگونه فکر می کنید اشتباه می کنید زیرا رفتار جهان حقیقی دیده شده پیرامون ما اینگونه است.
ایجاد و دور انداختن اشیا در وارنیش یک عمل مکرر است. وقتی ایجاد شد، اشیا اغلب برای هفته ها کش می شوند و نه ماه ها. بنابراین باینری هیپ ممکن است حتی یک بار در دقیقه هم به روزرسانی نشود و در بعضی سایت ها حتی یک بار در ساعت.
درضمن، گیگابایت هایی از اشیا را برای مرورگر کلاینت دریافت کردیم و تا زمانی که همه ی این اشیا برای فضا در حافظه ی مقدماتی رقابت نکردند، صفحات حافظه ی مجازی شامل باینری هیپ می باشد که از صفحات بیرون انداخته نشده است. درمورد بدتر تنها ۹ صفحه ی مستقر، باینری هیپ میانگین در هر عملیات ۱۱٫۵ صفحه انتقال می دهد، درحالیکه بی هیپ تنها به ۱٫۱۴صفحه برای انتقال نیاز دارد. اگر سرور شما دیسک های اس اس دی^[۱۳۹] (درایو حالت جامد) دارد، بین این که عملیات شما ۱۱ میلی ثانیه طول بکشد یا ۱٫۱ میلی ثانیه، تفاوت وجود دارد. اگر شما هنوز صفحات چرخشی^[۱۴۰]دارید، بین ۱۱۰ میلی ثانیه و ۱۱ میلی ثانیه تفاوت است.
در این مسیر، آیا فکر کردن به این قضیه اشتباه است که “اگر آن تنها یک بار در دقیقه اجرا می شود، چه کسی مراقب است که یک ثانیه ی تمام طول نکشد؟”
ما این کار را انجام می دهیم، در حقیقت مراقبت به این دلیل است که ۱۰ صفحه ی اضافی به یک بار در دقیقه تاخیر در رم نیاز دارند، برای نگه داشتن آن ها کاری انجام نمی دهیم تا زمانی که صفحات کرنل آن ها را دوباره برگردانند.
اکنون بیایید روی انتهای دیگر شکل زوم کنیم (شکل ۲-۸). اگر هیچ فشار حافظه مجازی وجود نداشته باشد، الگوریتم بی هیپ به مقایسه هایی بیشتر از باینری سورت^[۱۴۱] نیاز داشت، و محاسبه ی ایندکس ساده ی پدر به فرزند^[۱۴۲]یا فرزند به پدر^[۱۴۳] مانند نوزادی است که گرفتارتر شده است: بنابراین به جای زمان اجرای ۴٫۵۵ ثانیه، ۵٫۹۲ ثانیه طول می کشد، به مقدار ۳۰ درصد آهسته تر و تقریبا ۳۵۰ نانو ثانیه بر عملیات آهسته تر اجرا می شود.
شکل ۲-۸ تاثیر فشار وی ام روی سرعت اجرای باینری هیپ و بی هیپ به صورت زوم
بنابراین نوت و دیگر متخصصان سی اس این مسائل را به درستی کشف کرده اند.
اگر روی نمودار به سمت چپ حرکت کنیم، می بینیم که در یک فشار حافظه مجازی از ۴ صفحه ی از دست رفته (برابر ۰٫۲ درصد)، بی هیپ سبقت می گیرد، چون تعداد کمی از صفحات حافظه مجازی دارای نقص هستند، و به تدریج بهتر و بهتر می شود تا زمانی که به نقطه ی اوج ۱۰ بار سریع تر برسد.
بر فرض این که شما از یک دیسک اس اس دی استفاده می کنید که می تواند عملیات یک صفحه را در ۱ میلی ثانیه انجام دهد(به صورت خوش بینانه)، به ویژه برای نوشتن. اگر یک دیسک مکانیکی را توسط تنظیمات زمان ورودی/خروجی^[۱۴۴] شبیه سازی کنیم تا این زمان به صورت خوش بینانه به ۱۰ میلی ثانیه برسد(شکل۲-۹)، سپس بی هیپ ۱۰ درصد سریع تر است به محض این که کرنل تک صفحه ای را از ۱۹۵۴ صفحه ی در حال کار تنظیم می کند و ۳۷ درصد سریع تر است وقتی که ۴ صفحه از دست می رود.
شکل ۲-۹ مقایسه زمان اجرای باینری هیپ و بی هیپ روی دیسک مکانیکی
بی هیپ چیست؟ تنها تفاوت بین بی هیپ و باینری هیپ فرمول پیدا کردن پدر از فرزند است یا بالعکس.
فرمول مرسوم ۲-۱ ما را به یک هیپ ساخته شده از صفحات مجازی که روی هم طوری انباشته شده اند که با هر پیمایش عمودی روی درخت به سمت بالا یا پایین به یک صفحه ی متفاوت حافظه مجازی برخورد می کند، واگذار می کند، همانطور که در شکل ۲-۱۰ مشاهده می کنید با ۸ آیتم در هر صفحه این عمل انجام می شود.(اعداد نوشته شده کنار هر آیتم، اشیای اختصاص داده شده به هر آیتم است و مقدار کلید آن ها نیست)
n->{2n,2n+1} (2-1)
شکل ۲-۱۰ ساختار درخت باینری هیپ
بی هیپ درخت را با پر کردن صفحات به صورت عمودی می سازد، برای تطبیق مسیر مطابق شکل ۲-۱۱ درخت هیپ را پیمایش می کنیم. این ترتیب مجدد، میانگین تعداد عملیات مقایسه/معاوضه ی خواسته شده برای ثابت نگه داشتن درخت را افزایش می دهد. اما مطمئن باشید که اغلب این عملیات در کنار یک صفحه ی تنهای حافظه مجازی اتفاق می افتد و بنابراین جای پای حافظه مجازی کاهش پیدا می کند و در نتیجه صفحه ی حافظه مجازی دچار خطا می شود.
شکل ۲-۱۱ ساختار درخت بی هیپ
دو نکته ی جزیی قابل توجه:
یک بار ما یک صفحه ی حافظه مجازی را در پایین قرار دادیم، از نظر کارایی اهمیت دارد که هر دو گره ی فرزند در یک صفحه ی حافظه مجازی قرار بگیرند، زیرا ما قصد مقایسه ی هردوی آن ها با پدرشان را داریم.
به همین دلیل، درخت برای توسعه یافتن به منظور تولید، در زمان ورود یک صفحه ی حافظه مجازی جدید، برای استفاده ی اولین دو عنصر صفحه، شکست می خورد.
در مثال شبیه سازی شده ی ما، نقص زمانی اتفاق می افتد که ۵ صفحه بیشتر درخواست شود.
اگر این برای شما بی اهمیت به نظر بیاید، اشتباه می کنید: سعی کنید خط ۲۰ کیلوبایت در بی هیپ را در شکل های ۲-۷ و ۲-۸ به سمت راست جابجا کنید و درمورد مفاهیم فکر کنید.
پارامترهای شبیه سازی من انتخاب شده اند برای ارائه ی اینکه چه اتفاقی در زندگی واقعی وارنیش می افتد، و من نباید به توصیف و تحلیل جامع کارایی بی هیپ برای همه ی پارامترهای ممکن تلاش کنم. همچنین از وجود راه های هوشمندانه تر برای اضافه کردن راهنمای وی ام به یک باینری هیپ، جلوگیری نخواهم کرد. اما به خرید بلیط روی ریل قطارهای سیبری^[۱۴۵] به منظور یافتن زمان برای حل کردن آن، متمایل نشده ام.
مرتبه ی بزرگی تفاوت، با تعدادی از سطوح هیپ، کنار هر صفحه ی حافظه مجازی آغاز می شود. بنابراین تسریع نهایی روی ماشین هایی با سایز اشاره گرهای کوچک و سایز صفحه های بزرگ خواهد بود. این یک مشاهده ی وابسته است، همانطور که هسته های سیستم عامل شروع می کنند به استفاده از صفحات بزرگ برای بالا نگه داشتن عملکرد ورودی/خروجی.
چرا همچنان ما این کار را اشتباه انجام می دهیم؟ بحث معروفی وجود دارد با عنوان “سورت سریع^[۱۴۶] یا هیپ سورت” ، تمرکز روی این حقیقت که بدترین رفتار سابق وحشتناک است، درحالیکه آخری عملکرد میانگین بدتری دارد اما نه در حد “نقاط بد^[۱۴۷]“. وابسته به برنامه^[۱۴۸]ی شما، این می تواند تفاوت بسیار مهمی باشد.
ما فاقد یک درخواست مشابه به انتخاب الگوریتم در مواجه با تاخیر دسترسی حافظه ی ناهمسان به علت حافظه ی مجازی، کش های سی پی یو، بافرهای نوشتن^[۱۴۹]و دیگر حقایق سخت افزار مدرن هستیم.
در هر کتابی که آموزش برنامه نویسی را یاد گرفته اید، احتمالا در ۵ صفحه ی ابتدایی آن، شکلی از کامپیوتر مشابه شکل ۲-۱۲را داشته است.
شکل ۲-۱۲ مدل کامپیوتر منسوخ
این مدل، تنها مدل مفهومی استفاده شده در آموزش کامپیوتر است، علی رغم این واقعیت که هیچ چیزی برای کار با محیط اجرا روی یک کامپیوتر مدرن وجود ندارد. و فقط برای ضبط: توسط مدرن^[۱۵۰]، منظور من وکس^[۱۵۱] ۷۸۰/۱۱ یا بعدی است.
۳۰ یا ۴۰ سال گذشته از توسعه ی سیستم عامل و سخت افزار، درحاشیه روی دستورالعملی در بخش های تحلیلی الگوریتمی دپارتمان سی اس پیوند زده شده است، و طبق شاهد حدیثی من، درمجموع برای ثبت نامی که آن ها فراهم کردند شکست خورده است.
اختلاف سرعت بین انبار اولیه و ثانویه روی کامپیوتر اطلس روی مرتبه ی ۱:۱٫۰۰۰ بود. غلطک اطلس ۲ میلی ثانیه برای دریافت یک سکتور زمان برد. دستورالعمل ها تقریبا ۲ میکروثانیه برای اجرا زمان می برند. شما حدود ۱۰۰۰ دستورالعمل را برای هر نقص صفحه ی وی ام از دست داده اید.
روی یک سی پی یوی چند منظوره، اجرا می شود در فرکانس ساعت گیگاهرتز، بدترین اتلاف تقریبا ۱۰ میلیون دستورالعمل بر نقص صفحه ی وی ام است. اگر شما در حال اجرا باشید با یک دیسک چرخشی، عدد آن بیشتر از ۱۰۰ میلیون دستورالعمل است.
اگر عملیات^[۱۵۲] یک الگوریتم مرتبه اجرای لاگ ان، باعث نقص صفحه شود یا عملیات دیسک را آهسته کند، چقد خوب است؟ برای اغلب مجموعه داده های وابسته، روی الگوریتم مرتبه ی ان^[۱۵۳] یا حتی مرتبه ی ان دو^[۱۵۴]، که از نقص صفحه اجتناب می کند، دایره هایی دور آن اجرا خواهد شد.
تحلیل عملکرد الگوریتم ها، یک موفقیت بزرگ برای همیشه در علم کامپیوتر خواهد بود]۲۰[.

۲-۴ نرم افزارهای مبتنی بر وب

برای مشخص نمودن برنامه هائی با قابلیت اجراء بر روی وب، از واژه های متعددی استفاده می گردد:
نرم افزارهای تحت وب
نرم افزارهای وب ۲
نرم افزارهای مبتنی بر وب