تحلیل الگوریتم شاخه و قید موازی آسنکرون

1- خلاصه:

در این مقاله توضیحی درباره کامپیوترهای موازی می‌دهیم و بعد الگوریتمهای موازی را بررسی می‌کنیم. ویژگیهای الگوریتم branch & bound را بیان می‌کنیم و الگوریتمهای b&b موازی را ارائه می‌دهیم و دسته‌ای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه می‌دهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی می‌کنیم.

نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازی‌سازی است معرفی می‌کنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازی‌سازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.

2- معرفی:

همیشه نیاز به کامپیوترهای قدرتمند وجود داشته است. در مدل سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک دستورالعمل داده بایستی از محل یک کامپیوتر به محل دیگری منتقل می‌شد، لذا نیاز هب کامپیوترهای قدرتمند اهمیت روز افزون پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این مدل جدید چندین عنصر پردازشی در اجرای یک task واحد با هم همکاری می‌کنند. ایده اصل این مدل بر اساس تقسیم یک task به subtask‌های مستقل از یکدیگر است که می‌توانند هر کدام بصورت parallel (موازی) اجرا شوند. این نوع از کامپیوتر را کامپیوتر موازی گویند.

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

اولاً: این امکان وجود ندارد که هر taskی را بطور دلخواه به تعدادی زیر task‌های مستقل تقسیم کنیم. چون همواره تعدادی زیر task های وابسته وجود دارد که بایستی بطور خطی اجرا شوند. از اینرو زمان مورد نیاز برای اجرای یک task بطور موازی یک حد پایین دارد.

دوماً: هر کامپیوتر موازی که عملاً ساخته می‌شود شامل تعداد معینی عناصر پردازشی (Processing element) است. به محض آنکه تعداد taskها فراتر از تعداد عناصر پردازشی برود، بعضی از sub task ها بایستی بصورت خطی اجرا شوند و بعنوان یک فاکتور ثابت در تسریع کامپیوتر موازی تصور می‌شود.

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

الگوریتم B&B یک مسئله را به زیر مسئله‌های کوچکتر بوسیله تقسیم فضای حالت به زیر فضاهای (Subspace) کوچکتر، تجزیه می‌کند. هر زیر مسئله تولید شده یا حل است و یا ثابت می‌شود که به حل بهینه برای مسئله اصلی (Original) نمی‌انجامد و حذف می‌شود. اگر برای یک زیر مسئله هیچ کدام از این دو امکان بلافاصله استنباط نشود، آن زیر مسئله به زیرمسئله‌های کوچکتر دوباره تجزیه می‌شود. این پروسه آنقدر ادامه پیدا می‌کند تا تمام زیر مسئله‌های تولید شده یا حل شوند یا حذف شوند.

در الگوریتمهای B&B کار انجام شده در حین اجرا به شدت تحت تاثیر نمونه مسئله خاص قرار می‌گیرد. بدون انجام دادن اجرای واقعی الگوریتم این امکان وجود ندارد که تخمین درستی از کار انجام شده بدست آورد. علاوه برآن، روشی که کار باید سازمان‌دهی شود بر روی کار انجام شده تاثیر می‌گذارد. هر گامی که در اجرای الگوریتم b&b ی موازی بطور موفقیت‌آمیزی انجام می‌شود و البته به دانشی است که تاکنون بدست آورده. لذا استفاده از استراتژی جستجوی متفاوت یا انشعاب دادن چندین زیر مسئله بطور موازی باعث بدست آمدن دانشی متفاوت می‌شود پس می‌توان با ترتیب متفاوتی زیر مسئله‌ها را انشعاب داد.

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

با این حال اگر قدرت محاسبه یک کامپیوتر موازی با اضافه کردن عناصر پردازشی اضافه افزایش پیدا کند. اجرای الگوریتم b&b بطور آشکاری تغییر می‌کند (به عبارت دیگر ترتیبی که در آن زیر برنامه‌ها انشعاب پیدا می‌کنند تغییر می‌کند). بنابراین حل مسائل بهینه‌سازی گسسته سرسع بوسیله یک کامپیوتر موازی نه تنها باعث افزایش قدرت محاسبه کامپیوتر موازی شده است بلکه باعث گسترش الگوریتمهای موازی نیز گشته است.

3- کامپیوترهای موازی (Parallel computers):

یکی از مدلهای اصلی محاسبات Control drivenmodel است، در این مدل کاربر باید صریحاً ترتیب انجام عملیات را مشخص کند و آن دسته از عملیاتی که باید به طور موازی اجرا شوند را تعیین کند. این مدل مستقل از عناصر پردازش به صورت زیر تقسیم‌بندی می‌شود:

- کامپیوترهای SISD، که یک عنصر پردازشی وجود دارد و توان انجام فقط یک عمل را در یک زمان دارد.

- کامپیوترهای MIMD، دارای چندین عنصر پردازشی هستند که بطور موازی دستورالعمل‌های متفاوت را روی دیتاهای متفاوت انجام می‌دهند.

- کامپیوترهای SIMD، همه عناصر پردازشی‌شان یک دستور یکسان را در یک زمان بر روی داده‌های متفاوتی انجام می‌دهند. اگر چه امکان پنهان کردن عناصر پردازشی وجود دارد. عنصر پردازشی پنهان شده نتیجه عملی را که انجام داده ذخیره نمی‌کند.

سیستمهای SIMD بر اساس نحوه ارتباط و اتصال عناصر پردازشی به یکدیگر خود به بخشهایی تقسیم می‌شوند: اگر تمام عناصر پردازشی به یکدیگر متصل باشند و از طریق یک حافظه مشترک ارتباط داشته باشند، به آن tightly coupled system گویند.

و اگر عناصر پردازش حافظه مشترک نداشته باشند اما از طریق شبکه‌ای بهم متصل باشند و بروش message passing با هم ارتباط داشته باشند، به آن loosely coupled system گویند.

حافظه مشترک در tightly coupled system ها هم نقطه قوت و هم نقطه ضعف این سیستمها است. امکان به اشتراک گذاشتن راحت و سریع اطلاعات بین عناصر پردازشی مختلف را فراهم می‌کند. ارتباط به عملیات ساده read و wite روی حافظه مشترک خلاصه می‌شود و هر عنصر پردازشی مستقیماً با دیگر عناصر پردازشی ارتباط برقرار می‌کند. با این حال، اگر تعداد عناصر پردازشی متصل به حافظه مشترک افزایش یابد، حافظه مشترک تبدیل به گلوگاه (Bottleneck) می‌شود.

بنابراین تعداد عناصر پردازشی در یک سیستم tightly coupled محدود است. به جهت اینکه تمام عناصر پردازشی بایستی به ان حافظه مشترک متصل باشند، این سیستمها بصورت کامل از پیش ساخته هستند و امکان اضافه کردن عناصر پردازش به سیستم وجود ندارد.

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

در مقابل compactness بودن سیستمهای tightly coupled ، عناصر پردازشی در یک سیستم loosely coupled می‌توانند در تمام نقاط توزیع شوند. لذا فاصله فیزیکی که یک پیام باید طی کند، بیشتر می‌شود. به جهت این حقیقت که عناصر پردازشی برای ارتباط در یک شبکه از یک پروتکل استفاده می‌کنند، lossely coupled system می‌توانند شامل انواع مختلفی از عناصر پردازشی باشند. امکان اضافه کردن عناصر پردازشی اضافه‌تری به سیستم وجود دارد. در حالت کلی عناصر پردازشی خودشان یک کامپیوتر کاملی هستند.

مثالی از سیستمهای loosely coupled، Distributed Processing utilities Package است که بعداُ به تفضیل درباره آنها توضیح می‌دهیم.

4- الگوریتمهای موازی (Parallel Algorithm):

یک الگوریتم موازی شامل sub taskهایی است که باید انجام شود. بعضی از این sub taskها بصورت موازی اجرا می‌شوند، اما گاهی sub taskهایی هم وجود دارد که باید بصورت خطی اجرا شوند. اجرای هر sub task توسط یک پروسس مجزا انجام می‌شود. از ویژگیهای مهم یک الگوریتم موازی نحوه محاوره این پروسسها، سنکرون بودن و قطعی بودن الگوریتم است. دو پروسس با یکدیگر محاوره (interact) دارند، اگر خروجی یکی از آندو پروسس ورودی دیگری باشد. نحوه محاوره دو پروسس می‌تواند بطور کامل مشخص شده باشد یا نباشد. اگر مشخص شده باشد، این دو پروسس فقط زمانی می‌توانند ارتباط داشته باشند که هر دو مایل به انجام ارتباط باشند. اگر گیرنده هنوز آماده ارتباط نباشد، فرستنده نمی‌تواند اقدامی انجام دهد.

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

یک الگوریتم قطعی است اگر هر بار که الگوریتم بر روی ورودی مشابه اجرا شود، نتیجه اجرا یکسان باشد. یعنی دستورالعملهای مشابه به ترتیب مشابه انجام شود. بنابراین اجراهای متوالی از یک الگوریتم همیشه خروجی یکسان دارد در حالیکه در الگوریتمهای غیر قطعی یک تصمیم یکسان خروجیهای متفاوتی دارد. مثلاً خروجی یک تصمیم ممکن است و البته به فاکتورهای محیطی معینی باشد که توسط الگوریتم کنترل نمی‌شود. از اینرو اجراهای پی‌در پی یک الگوریتم غیر قطعی، خروجی‌های متفاوت تولید می‌کند.

آشنایی با چند سخت افزار کامپیوتر

چکیده

امروزه کامپیوتر در موارد متعددی به خدمت گرفته می شود . برخی از تجهیزات موجود در منازل ، دارای نوعی خاصی از ریز پردازنده می باشند . حتی اتومبیل های جدید نیز دارای نوعی کامپیوتر خاص می باشند . کامپیوترهای شخصی ، اولین تصویر از انواع کامپیوترهائی است که در ذهن هر شخص نقش پیدا می کند. که به شرح چند نمونه از سخت افزار کامپیوتر می پردازیم.

1- حافظة RAM (Random Access Memory)

RAM نوعی حافظه است که کامپیوتر از آن برای ذخیره برنامه ها و داده ها هنگام پردازش استفاده می کند. اطلاعات اکثر انواع RAMها هنگام خاموش کردن کامپیوتر پاک می شود. در حال حاضر شرکت ها در تلاش هستند RAMهایی تولید کنند که با خاموش شدن کامپیوترهم، داده ها را در خود نگه دارند (با استفاده از نانوتیوب­های کربنی و اثر تونل های مغناطیسی).

امروزه بعضی از انواع RAMها قادرند اشتباهات تصادفی را تصحیح کنند. در سال های اخیر chipهایی ساخته شده است که تا GB10 حافظه دارند، همینطور chipهایی که اندازه آن ها در حدود 18/0 میکرون می باشد .

انواع RAM (نرخهای عملکرد با رنگ سبز نشان داده شده­اند):

• SDRAM (Synchronous Dynamic RAM) ® 100 MHz
• DDR SDRAM (Double-Data-Rate SDRAM)
• DDR1 (or DDR) ® 100-200 MHz
• DDR2 ® 200-400 MHz
• DDR3 ® 400-800 MHz
• RDRAM (Rambus Dynamic RAM) ® 300-800 MHz

2- Modem

3- دیسک سخت

4- Cpu

فصل اول : حافظه RAM

حافظهRAM (Random Access Memory) شناخته ترین نوع حافظه در دنیای کامپیوتر است . روش دستیابی به این نوع از حافظه ها تصادفی است . چون می توان به هر سلول حافظه مستقیما" دستیابی پیدا کرد . در مقابل حافظه های RAM ، حافظه هایSAM (Serial Access Memory) وجود دارند. حافظه های SAM اطلاعات را در مجموعه ای از سلول های حافظه ذخیره و صرفا" امکان دستیابی به آنها بصورت ترتیبی وجود خواهد داشت. ( نظیر نوار کاست ) در صورتیکه داده مورد نظر در محل جاری نباشد هر یک از سلول های حافظه به ترتیب بررسی شده تا داده مورد نظر پیدا گردد. حافظه های SAM در مواردیکه پردازش داده ها الزاما" بصورت ترتیبی خواهد بود مفید می باشند ( نظیر حافظه موجود بر روی کارت های گرافیک ). داده های ذخیره شده در حافظه RAM با هر اولویت دلخواه قابل دستیابی خواهند بود.

مبانی حافظه های RAM

حافظه RAM ، یک تراشه مدار مجتمع (IC) بوده که از میلیون ها ترانزیستور و خازن تشکیل شده است .در اغلب حافظه ها با استفاده و بکارگیری یک خازن و یک ترانزیستور می توان یک سلول را ایجاد کرد. سلول فوق قادر به نگهداری یک بیت داده خواهد بود. خازن اطلاعات مربوط به بیت را که یک و یا صفر است ، در خود نگهداری خواهد کرد.عملکرد ترانزیستور مشابه یک سوییچ بوده که امکان کنترل مدارات موجود بر روی تراشه حافظه را بمنظور خواندن مقدار ذخیره شده در خازن و یا تغییر وضعیت مربوط به آن ، فراهم می نماید.خازن مشابه یک ظرف ( سطل) بوده که قادر به نگهداری الکترون ها است . بمنظور ذخیره سازی مقدار" یک" در حافظه، ظرف فوق می بایست از الکترونها پر گردد. برای ذخیره سازی مقدار صفر، می بایست ظرف فوق خالی گردد.مسئله مهم در رابطه با خازن، نشت اطلاعات است ( وجود سوراخ در ظرف ) بدین ترتیب پس از گذشت چندین میلی ثانیه یک ظرف مملو از الکترون تخلیه می گردد. بنابراین بمنظور اینکه حافظه بصورت پویا اطلاعات خود را نگهداری نماید ، می بایست پردازنده و یا " کنترل کننده حافظه " قبل از تخلیه شدن خازن، مکلف به شارژ مجدد آن بمنظور نگهداری مقدار "یک" باشند.بدین منظور کنترل کننده حافظه اطلاعات حافظه را خوانده و مجددا" اطلاعات را بازنویسی می نماید.عملیات فوق (Refresh)، هزاران مرتبه در یک ثانیه تکرار خواهد شد.علت نامگذاری DRAM بدین دلیل است که این نوع حافظه ها مجبور به بازخوانی اطلاعات بصورت پویا خواهند بود. فرآیند تکراری " بازخوانی / بازنویسی اطلاعات" در این نوع حافظه ها باعث می شود که زمان تلف و سرعت حافظه کند گردد.

سلول های حافظه بر روی یک تراشه سیلیکون و بصورت آرائه ای مشتمل از ستون ها ( خطوط بیت ) و سطرها ( خطوط کلمات) تشکیل می گردند. نقطه تلاقی یک سطر و ستون بیانگر آدرس سلول حافظه است .

حافظه های DRAM با ارسال یک شارژ به ستون مورد نظر باعث فعال شدن ترانزیستور در هر بیت ستون، خواهند شد.در زمان نوشتن خطوط سطر شامل وضعیتی خواهند شد که خازن می بایست به آن وضغیت تبدیل گردد. در زمان خواندن Sense-amplifier ، سطح شارژ موجود در خازن را اندازه گیری می نماید. در صورتیکه سطح فوق بیش از پنجاه درصد باشد مقدار "یک" خوانده شده و در غیراینصورت مقدار "صفر" خوانده خواهد شد. مدت زمان انجام عملیات فوق بسیار کوتاه بوده و بر حسب نانوثانیه ( یک میلیاردم ثانیه ) اندازه گیری می گردد. تراشه حافظه ای که دارای سرعت 70 نانوثانیه است ، 70 نانو ثانیه طول خواهد کشید تا عملیات خواندن و بازنویسی هر سلول را انجام دهد.

سلول های حافظه در صورتیکه از روش هائی بمنظور اخذ اطلاعات موجود در سلول ها استفاده ننمایند، بتنهائی فاقد ارزش خواهند بود. بنابراین لازم است سلول های حافظه دارای یک زیرساخت کامل حمایتی از مدارات خاص دیگر باشند.مدارات فوق عملیات زیر را انجام خواهند داد :

-- مشخص نمودن هر سطر و ستون (انتخاب آدرس سطر و انتخاب آدرس ستون)

-- نگهداری وضعیت بازخوانی و باز نویسی داده ها ( شمارنده )

-- خواندن و برگرداندن سیگنال از یک سلول ( Sense amplifier)

-- اعلام خبر به یک سلول که می بایست شارژ گردد و یا ضرورتی به شارژ وجود ندارد ( Write enable)

سایر عملیات مربوط به "کنترل کننده حافظه" شامل مواردی نظیر : مشخص نمودن نوع سرعت ، میزان حافظه و بررسی خطاء است .

حافظه های SRAM دارای یک تکنولوژی کاملا" متفاوت می باشند. در این نوع از حافظه ها از فلیپ فلاپ برای ذخیره سازی هر بیت حافظه استفاده می گردد. یک فلیپ فلاپ برای یک سلول حافظه، از چهار تا شش ترانزیستور استفاده می کند . حافظه های SRAM نیازمند بازخوانی / بازنویسی اطلاعات نخواهند بود، بنابراین سرعت این نوع از حافظه ها بمراتب از حافظه های DRAM بیشتر است .با توجه به اینکه حافظه های SRAM از بخش های متعددی تشکیل می گردد، فضای استفاده شده آنها بر روی یک تراشه بمراتب بیشتر از یک سلول حافظه از نوع DRAM خواهد بود. در چنین مواردی میزان حافظه بر روی یک تراشه کاهش پیدا کرده و همین امر می تواند باعث افزایش قیمت این نوع از حافظه ها گردد. بنابراین حافظه های SRAM سریع و گران و حافظه های DRAM ارزان و کند می باشند . با توجه به موضوع فوق ، از حافظه های SRAM بمنظور افزایش سرعت پردازنده ( استفاده از (Cacheو از حافظه های DRAM برای فضای حافظه RAM در کامپیوتر استفاده می گردد.

حافظة مجازی

حافظه مجازی‌
در این تمرین شما با صورتها و شکلهای مختلفی از مکانیزم حافظه مجازی در ویندوز NT آشنایی پیدا خواهید کرد علی‌رغم اغلب دیگر سیستمهای عامل، ویندوز NT یک API ساده و روشنی را برای اداره کردن بعضی شکلها و صورتهای حافظه مجازی تهیه می‌کند(معمولاً حافظه مجازی بطور کامل توسط برنامه نویس کاربردی‌اش روشن و واضح می‌گردد) در این تمرین شما در موارد زیر اطلاعاتی یاد خواهید گرفت:  سازماندهی سیستم حافظه مجازی ویندوز NT چگونه فضای حافظه مجازی خود را کنترل کنید؟ چگونه یک وسیله آگاه کننده و گزارش دهنده بنویسید؟ جزئیات GlobalMemory Status , GetsystemInfo – VirtualQuery – VirtualUnlock – VirtualLock – VirtueaFree – VirtualAlloc معرفی
حافظه مجازی صفحه‌بندی یا Paging Virtual Memory در بسیاری از سیستمهای عامل امروزی بکار گرفته می‌شود. در یک سیستم صفحه‌بندی شده، هر فرآیندی یک فضای آدرس دهی مجازی خاص خود دارد که برای ارجاع دیگر اشیاء بکار گرفته می‌شود که معمولاً محتوای یک محل یا موقعیتی از حافظه است بخشی از فضای آدرس دهی مجازی توسط ویراستار خطی ( Link editor ) تعریف می‌شوند وقتی که آن یک تصویر قابل اجرایی بوجود می‌آورد که در واقع فایل اجرایی یا EXE است. تعداد باقیمانده از فضای آدرس‌دهی می‌تواند بطور پویا در زمان اجرا توسط روشهایی که در این تمرین توضیح داده خواهد شد تعر یف شود. بعد از اینکه قسمت پایدار و ثابت از فضای آدرس‌دهی مجازی ایجاد شد در حافظه ثانویه ذخیره خواهد شد ( معمولاً در بخش یا Partition از وسیله ذخیره‌سازی کهPaging disk نام دارد ). به منظور عملی‌تر شدن شما می‌توانید Paging disk را مشابه فایل در نظر بگیرید. در یک کامپیوتر معمول و مرسوم پردازنده تنها می‌تواند دستورات را واکشی کند یا داده‌هایی را که در حافظه اولیه یا قابل اجرا ( که معمولاً RAM خوانده می‌شوند. ) واقع شده‌اند را بارگذاری کند. حافظه اولیه در مقایسه با حافظه ثانویه کوچکتر و سریعتر است. حافظه اولیه خیلی گرانتر از حافظه ثانویه است بنابراین بطور معمول در زمره اجزای با ارزش‌تر از نظر حجم اما کوچکتر از حافظه‌های ثانویه قرار دارند. اغلب کامپیوترها حافظه اولیه کافی حتی برای ذخیره فضای آدرس‌دهی مجازی کامل یک فرآیند را هم ندارند بنابراین در یک زمان تعداد زیادی فضا روی حافظه ثانویه برای ذخیره فضای آدرس‌دهی مجازی تعداد زیادی فرآیند وجود خواهد داشت. حافظه اولیه همچنین خیلی سریعتر از حافظه ثانویه می‌باشد. پردازنده می‌تواند یک بایت را در 2 سیکل پردازنده در حافظه اولیه بخواند یا بنویسید. اما همین عمل هزاران سیکل از پروسسور را برای نوشتن یا خواندن اطلاعات در حافظه ثانویه نیازمند است.برای نگهداری فضای حافظه اولیه یک سیستم حافظه مجازی صفحه‌بندی شده در هر زمان داده شده تنها بخشی از فضای آدرس‌دهی مجازی تعداد مختلفی از فرآیند‌ها را بارگذاری یا ( Load ) می‌کند. همانطور که Thread ها در فضای آدرس‌دهی فرآیندهایشان اجرا می‌شوندبخشی از فضای آدرس‌دهی مجازی که در حال حاضر در حال استفاده است در حافظه اولیه بارگذاری می‌شود و در همان حال دیگر بخشهای فضای آدرس‌دهی در حافظه ثانویه قرار گرفته‌اند. زمانی که فرآیندی به بخشی از فضای آدرس‌دهی مجازی دیگر نیاز ندارد ( حداقل برای مدتی ) از آن بخش در حافظه ثانویه کپی گرفته می‌شود. این به موقعیتی از حافظه اولیه که مورد استفاده برای ذخیره بخشی از فضای آدرس‌دهی مجازی قرار گرفته بود این اجازه را می‌دهد که برای ذخیره بخش دیگری از فضای آدرس‌دهی مجازی در زمان دیگری بکار گرفته شود. در یک سیستم حافظه مجازی سنجش در کارایی بوسیله کپی کردن یک بلوک از حافظه در حافظه اولیه یا بازگرداندن به حافظه ثانویه در زمانی که یک جابه‌جایی بین دوسطح از سلسله مرتبه حافظ مورد نیاز و ضروری باشد بدست می‌آید کارایی از این واقعیت بدست می‌آید که عملیات ورودی و خروجی حافظه ثانویه وابسته به بلوکها می‌باشد. این یعنی اگر تنها یک کلمه ( Word ) اطلاعات از حافظه ثانویه مورد نیاز باشد همه بلوک باید خوانده شود تابه آن کلمه برسیم. همچنین نسبت به مکانی که همه آن بلوک در حافظه اولیه قرار داد هم احساس است تا زمانی که باید خوانده شود تابه لغت گم شده برسیم. فواید دیگری در بارگذاری همه بلوک‌ها نسبت به فقط یک کلمه وجود دارد. هنگامی که یک نخ یا Thread به مکانی چون I رجوع می‌کند احتمال زیادی وجود دارد که بخواهد به مکان I+1 در آینده نزدیک رجوع کند به این مفهوم محلیت یا Locality گفته می‌شود. یک حافظه مجازی صفحه‌بندی شده بلوکهای با اندازة ثابت را بارگذاری می‌کند و یا برمی‌دارد که به آنها صفحه یا Page گفته می‌شود که در زمانی که داده‌ها و اطلاعات را بین حافظه اولیه و ثانویه در جهت رفت و برگشت حرکت می‌دهد انجام می‌گیرد. حد و مرز صفحه‌ها یا Page ها کاملاً توسط برنامه‌نویس مشخص و واضح می‌شود. شکل 1 عملیات یک سیستم حافظه مجازی صفحه‌بندی شده بطور عام را خلاصه می‌کند.زمانی که یک نخ یا Thread به آدرس مجازی K رجوع می‌کند ( مرحله 1 در شکل ) حافظه مجازی ابتدا تعدا صفحات یا Page هایی که آدرس مجازی K را در بردارد تعیین می‌کند (مرحله2 در شکل ) اگر صفحه در حال حاضر در حافظه اولیه بارگذاری شده بود و موجود بود ( مرحله 3 در شکل ) سیستم حافظه مجازی آدرس مجازی را به آدرس فیزیکی متناظر با آن موقعیت در حافظه اولیه که همان Page Frame است تبدیل می‌کند ( جایی که صفحه هدف در آن واقع شده است. ) اگر صفحه در همان زمان که به آن رجوع شده بارگذاری نشده بود اجرای ‏Thread عادی دچار وقفه می‌شود تا زمانی که مدیریت حافظه صفحه مقصد را در Page Frame بارگذاری کند به محضی که آن صفحه بارگذاری شد اجرا ادامه پیدا خواهد کرد در مرحله 4 رجوع به آدرس مجازی K دوباره با آدرس فیزیکی در حافظه اولیه تعیین می‌گردد ( مکانی که موقعیت مجازی K در حال حاضر آنجا بارگذاری شده است. )

حافظه مجازی‌در این تمرین شما با صورتها و شکلهای مختلفی از مکانیزم حافظه مجازی در ویندوز NT آشنایی پیدا خواهید کرد علی‌رغم اغلب دیگر سیستمهای عامل، ویندوز NT یک API ساده و روشنی را برای اداره کردن بعضی شکلها و صورتهای حافظه مجازی تهیه می‌کند(معمولاً حافظه مجازی بطور کامل توسط برنامه نویس کاربردی‌اش روشن و واضح می‌گردد) در این تمرین شما در موارد زیر اطلاعاتی یاد خواهید گرفت:  سازماندهی سیستم حافظه مجازی ویندوز NT چگونه فضای حافظه مجازی خود را کنترل کنید؟ چگونه یک وسیله آگاه کننده و گزارش دهنده بنویسید؟ جزئیات GlobalMemory Status , GetsystemInfo – VirtualQuery – VirtualUnlock – VirtualLock – VirtueaFree – VirtualAlloc معرفی حافظه مجازی صفحه‌بندی یا Paging Virtual Memory در بسیاری از سیستمهای عامل امروزی بکار گرفته می‌شود. در یک سیستم صفحه‌بندی شده، هر فرآیندی یک فضای آدرس دهی مجازی خاص خود دارد که برای ارجاع دیگر اشیاء بکار گرفته می‌شود که معمولاً محتوای یک محل یا موقعیتی از حافظه است بخشی از فضای آدرس دهی مجازی توسط ویراستار خطی ( Link editor ) تعریف می‌شوند وقتی که آن یک تصویر قابل اجرایی بوجود می‌آورد که در واقع فایل اجرایی یا EXE است. تعداد باقیمانده از فضای آدرس‌دهی می‌تواند بطور پویا در زمان اجرا توسط روشهایی که در این تمرین توضیح داده خواهد شد تعر یف شود. بعد از اینکه قسمت پایدار و ثابت از فضای آدرس‌دهی مجازی ایجاد شد در حافظه ثانویه ذخیره خواهد شد ( معمولاً در بخش یا Partition از وسیله ذخیره‌سازی کهPaging disk نام دارد ). به منظور عملی‌تر شدن شما می‌توانید Paging disk را مشابه فایل در نظر بگیرید. در یک کامپیوتر معمول و مرسوم پردازنده تنها می‌تواند دستورات را واکشی کند یا داده‌هایی را که در حافظه اولیه یا قابل اجرا ( که معمولاً RAM خوانده می‌شوند. ) واقع شده‌اند را بارگذاری کند. حافظه اولیه در مقایسه با حافظه ثانویه کوچکتر و سریعتر است. حافظه اولیه خیلی گرانتر از حافظه ثانویه است بنابراین بطور معمول در زمره اجزای با ارزش‌تر از نظر حجم اما کوچکتر از حافظه‌های ثانویه قرار دارند. اغلب کامپیوترها حافظه اولیه کافی حتی برای ذخیره فضای آدرس‌دهی مجازی کامل یک فرآیند را هم ندارند بنابراین در یک زمان تعداد زیادی فضا روی حافظه ثانویه برای ذخیره فضای آدرس‌دهی مجازی تعداد زیادی فرآیند وجود خواهد داشت. حافظه اولیه همچنین خیلی سریعتر از حافظه ثانویه می‌باشد. پردازنده می‌تواند یک بایت را در 2 سیکل پردازنده در حافظه اولیه بخواند یا بنویسید. اما همین عمل هزاران سیکل از پروسسور را برای نوشتن یا خواندن اطلاعات در حافظه ثانویه نیازمند است.برای نگهداری فضای حافظه اولیه یک سیستم حافظه مجازی صفحه‌بندی شده در هر زمان داده شده تنها بخشی از فضای آدرس‌دهی مجازی تعداد مختلفی از فرآیند‌ها را بارگذاری یا ( Load ) می‌کند. همانطور که Thread ها در فضای آدرس‌دهی فرآیندهایشان اجرا می‌شوندبخشی از فضای آدرس‌دهی مجازی که در حال حاضر در حال استفاده است در حافظه اولیه بارگذاری می‌شود و در همان حال دیگر بخشهای فضای آدرس‌دهی در حافظه ثانویه قرار گرفته‌اند. زمانی که فرآیندی به بخشی از فضای آدرس‌دهی مجازی دیگر نیاز ندارد ( حداقل برای مدتی ) از آن بخش در حافظه ثانویه کپی گرفته می‌شود. این به موقعیتی از حافظه اولیه که مورد استفاده برای ذخیره بخشی از فضای آدرس‌دهی مجازی قرار گرفته بود این اجازه را می‌دهد که برای ذخیره بخش دیگری از فضای آدرس‌دهی مجازی در زمان دیگری بکار گرفته شود. در یک سیستم حافظه مجازی سنجش در کارایی بوسیله کپی کردن یک بلوک از حافظه در حافظه اولیه یا بازگرداندن به حافظه ثانویه در زمانی که یک جابه‌جایی بین دوسطح از سلسله مرتبه حافظ مورد نیاز و ضروری باشد بدست می‌آید کارایی از این واقعیت بدست می‌آید که عملیات ورودی و خروجی حافظه ثانویه وابسته به بلوکها می‌باشد. این یعنی اگر تنها یک کلمه ( Word ) اطلاعات از حافظه ثانویه مورد نیاز باشد همه بلوک باید خوانده شود تابه آن کلمه برسیم. همچنین نسبت به مکانی که همه آن بلوک در حافظه اولیه قرار داد هم احساس است تا زمانی که باید خوانده شود تابه لغت گم شده برسیم. فواید دیگری در بارگذاری همه بلوک‌ها نسبت به فقط یک کلمه وجود دارد. هنگامی که یک نخ یا Thread به مکانی چون I رجوع می‌کند احتمال زیادی وجود دارد که بخواهد به مکان I+1 در آینده نزدیک رجوع کند به این مفهوم محلیت یا Locality گفته می‌شود. یک حافظه مجازی صفحه‌بندی شده بلوکهای با اندازة ثابت را بارگذاری می‌کند و یا برمی‌دارد که به آنها صفحه یا Page گفته می‌شود که در زمانی که داده‌ها و اطلاعات را بین حافظه اولیه و ثانویه در جهت رفت و برگشت حرکت می‌دهد انجام می‌گیرد. حد و مرز صفحه‌ها یا Page ها کاملاً توسط برنامه‌نویس مشخص و واضح می‌شود. شکل 1 عملیات یک سیستم حافظه مجازی صفحه‌بندی شده بطور عام را خلاصه می‌کند.زمانی که یک نخ یا Thread به آدرس مجازی K رجوع می‌کند ( مرحله 1 در شکل ) حافظه مجازی ابتدا تعدا صفحات یا Page هایی که آدرس مجازی K را در بردارد تعیین می‌کند (مرحله2 در شکل ) اگر صفحه در حال حاضر در حافظه اولیه بارگذاری شده بود و موجود بود ( مرحله 3 در شکل ) سیستم حافظه مجازی آدرس مجازی را به آدرس فیزیکی متناظر با آن موقعیت در حافظه اولیه که همان Page Frame است تبدیل می‌کند ( جایی که صفحه هدف در آن واقع شده است. ) اگر صفحه در همان زمان که به آن رجوع شده بارگذاری نشده بود اجرای ‏Thread عادی دچار وقفه می‌شود تا زمانی که مدیریت حافظه صفحه مقصد را در Page Frame بارگذاری کند به محضی که آن صفحه بارگذاری شد اجرا ادامه پیدا خواهد کرد در مرحله 4 رجوع به آدرس مجازی K دوباره با آدرس فیزیکی در حافظه اولیه تعیین می‌گردد ( مکانی که موقعیت مجازی K در حال حاضر آنجا بارگذاری شده است. )