سیستم عامل چیست ؟ سیستم عامل چیزی جزیک برنامه طولانی نیست ،لیکن اندازه و میزان پیچیدگی آن بستگی به یک سری عوامل دارد،که مهمترین آنهاعبارتنداز:خصوصیات کامپیوتر، ا مکاناتی که این کامپیوتر بایستی عرضه کندو مواردکاربرد این کامپیوتر. سیستم عامل معمولآاولین برنامه است که درحافظه کامپیوتر، پس ازبارگیری، برخی قسمتهای سیستم عامل بطوردا ئم، مادا میکه کامپیوتر مشغول کار است درحافظه باقی می مانند. قسمتهای دیگرسیستم عامل ، باتوجه به کاربرد کامپیوتر توسط استفاده کننده اش ، بین حافظه اصلی کامپیوترو حافظه ثانوی آن ، مثل دیسک ها، نقل وانتقال می یابند. به این عمل مبادلهSwapping می گویند. بطورکلی یک سیستم عامل وظایف مهم زیررا بعهده دارد: الف – تسهیل درعملیات ورودی وخروجی استفاده کنندگان معمولآمایل نیستندکه جزئیات نحوه کنترل یک دستگاه جنبی را بدا نند تا بتوانندیک کاراکتررا بخوانند یاچاپ کنند.واضح است که بایستی یک سطح ارتباطی بالاتربرای استفاده کننده فراهم شود ب –کنترل اشتباهات هراندازه که برنامه نویس ماهرباشد نمی تواند همیشه برنامه های بدون غلط بنویسد. بنابراین لازم است که سیستم بنحوی غلطهای برنامه ها راکنترل نماید. بدین ترتیب که بمجرد بروز اشتباهی دربرنامه ، سیستم عامل دخالت می کندو باچاپ پیغام خطای مناسب به استفاده کننده کمک می کند، تاعلت اشتباه را بیابد. ج – دسترسی چند تایی Multi- access استفاده کنندگان ازکامپیوتر، خیلی راحت ترهستند، اگر بتوا نند بصورت چندتایی به سیستم دسترسی داشته باشند. هرچند که زمان پاسخ مربوط به عده ای از استفاده کنندگان ممکن است بعلت دسترسی چندتایی افزایش یابد. د – سیستم های فایل File systems سیستم عامل مسئول نگهداری فهرست راهنماوحفاظت ازفایل های استفاده کنندگان است. چنین کنترل مرکزی توسط سیستم عامل برروی فایلها ضروری است تابتوان به چنداستفاده کننده اجازه داد تاهمزمان از یک سخت افزار بهره ببرند، ودرعین حال سیستم فایل ا من باشد. سیستم عامل ممکن است ا مکانات دیگری ازنوع کاربردی مثل استفاده ازویرایشگرها فراهم نماید تااستفاده کنندگان بتوا نند به فایل های خود دسترسی پیداکرده ، آنهاراتغییردهند. مدیریت حافظه درسیستم چند برنامه ای بخش کاربر، حافظه بایستی به زیربخشهای دیگرتقسیم شود تا بتواندچند فرایند رادرخودجای دهد. وظیفه تقسیم بندی حافظه به زیربخشها به صورت پویا توسط سیستم عامل انجام می گیردوبه این عمل مدیریت حافظه می گویند. وجود یک مدیریت حافظه کارآمد برای سیستم چندبرنامه ای حیاتی است . اگر فقط چند فرایند محدود درحافظه باشند، اغلب اوقات فرایند منتظر ورودی / خروجی هستند و پردازنده بی کار خواهد بود. پس بهتر است حافظه به گونه ای تخصیص یابد که فرایندهای بیشتری درآن مجتمع شوند. مدیریت حافظه اصلی به عهده واحدهای مدیریت حافظه سیستم عامل است. منظور ما از حافظه اصلی حافظه ای است که پردازنده ها برای یافتن دستورالعملهاوداده ها، مستقیما به آن دستیابی دارند.حافظه اصلی غالبا باتوجه به سابقه تکنولوژی حلقه های مزیت مغناطیسی که درطی سالها برای ساختن آنها بکارمی رفت ، به حافظه چنبره ای مرسوم است . مدیریت حافظه شامل چهاروظیفه زیراست : نظارت بروضعیت هر یک از مکانهای حافظه اصلی، یعنی نظارت براینکه کدام مکان تخصیص یافته وکدام یک تخصیص نیافته (آزاد) است . تعیین سیاست تخصیص حافظه، یعنی تصمیم گیری در مورداینکه حافظه به کدام فراروند بایداختصاص یابد، چه مقدار ازآن چه هنگام وکجا. چنانچه حافظه اصلی باید بطورهمروند بین چند فراروندتقسیم شود، دراین صورت مدیریت حافظه باید تعیین کندکه تقاضای کدام فراروندها اجابت گردد. شیوه تخصیص پس ارآنکه تصمیم به تخصیص حافظه گرفته شد، نشانیهای خاص بایدانتخاب شده واطلاعات مربوط به تخصیص به هنگام درآیند. شیوه وسیاست بازیابی حافظه، اقدام درمورد بازیابی حافظه. فراروند یا ممکن است حافظه تخصیص یافته ازپیش راخودآزادکندو یااینکه مدیریت حافظه به طوریک جانبه و برمبنای یک سیاست بازیابی آن را بازپس گیرد. پس ازبازیابی اطلاعات مربوط به وضعیت حافظه باید به هنگام درآیند. سیاستهای انتخاب شده برای مدیریت حافظه ممکن است تحت تاثیرتمایل به داشتن واحدهای کوچک وساده مدیریت حافظه ویا نیازبه افزایش انعطاف پذیری از دیدکاربریابازدهی سیستم قرارگیرد. برخی ازاین سیاستها وشیوه ها بهره وری بیشتر ازحافظه را ا مکان پذیر میسازد،درحالی که برخی دیگر،ا نعطاف پذیری بیشتری را برای کاربرفراهم می کنند، البته درعوض گاهی باعث پیچیدگی بیشترهزینه سخت افزاری بالاترویا سرباربیشترمی شوند. حفاظت حافظه مشکل مربوط به مدیریت حافظه دریک سیستم اشتراک زمانی عبارتست ازحفاظت حافظه . درحالیکه تعدادی پردازش درماشین وجوددارند، سیستم عامل بایدازهر یک درمقابل دخالت های دیگران حفاظت بعمل آورد. البته فراموش نشوندکه سیستم عامل بایدخودش را هم درمقابل دخالت های استفاده کنندگان حفظ کند. تکنیکهای متعددی جهت حفاظت منابع یک سیستم درمقابل دسترسی غیرمجاز برنامه های استفاده کنندگان وجوددارند. درعمل ، مسئله حفاظت ازسیستم عامل در برا بریک استفاده کننده با مشکل حفاظت ازیک برنامه استفاده کننده دربرا بربرنامه دیگریکسان است . نیازهای مدیریت حافظه جابجایی حفاظت اشتراک سازماندهی منطقی سازماندهی فیزیکی جابجایی درسیستم چند برنامه ای، عموما حافظه موجود بین چند فرایند تقسیم میگردد. معمولابرای برنامه سازغیر ممکن است ازقبل بدا ندچه برنامه های دیگری درزمان اجرای برنامه ، مقیم حافظه خواهند بود. همچنین می توا نیم فرایندهای فعال را به خارج حافظه مبادله نماییم وازطریق ایجاد مجموعه بزرگی از فرایندهای آماده به اجرا، استفاده ازپردازنده را به حداکثر میرسانیم. ازآنجا که سیستم عامل مدیریت حافظه را برعهده داردوهم چنین مسئول آوردن این فرایند به داخل حافظه اصلی است، به سادگی می توان این آدرسها را مشخص نماید. بعلاوه، پردازنده باید بتوا ند نسبت به عملیات مراجعه به حافظه دریک برنامه، اقدام نماید. حفاظت هرفرایند باید درمقابل تداخلهای ناخواسته فرایندهای دیگر محافظت شود، خواه این تداخل تصادفی خواه عمدی باشد. پس برنامه های فرایندهای دیگرنباید قادرباشند برای مقاصد خواندن یا نوشتن به محلهای حافظه یک فرایند، بدون اجازه مراجعه نماید. ازطرفی برآوردن نیازهای جابجایی می توا ند باعث افزا یش دشواری دربرآوردن نیازهای حفاظتی شود. ازآنجا که مکان یک برنامه درحافظه مشخص نیست، ا مکان بررسی آدرسها درزمان ترجمه برای ا طمینان ازحفاظت وجود ندارد. علاوه براین، اغلب زبانهای برنامه سازی محاسبه پویای آدرس درزمان اجرا(مثل محاسبه شاخص یک آرایه یا اشاره گر به یک ساختمان داده ) را اجازه می دهند. بنابراین کلیه مراجعات به حافظه که توسط یک فرایند تولید میشوند بایستی درزمان اجرا بررسی شوند تا مطمئن شویم فقط به فضاهای اختصاص یافته به همان فرایند رجوع می کنند. اشتراک هرراهکارحفاظتی که به کاررود بایدا نعطاف پذیری لازم برای اجازه دادن به فرایندهای متعدد در دسترسی به یک بخش یکسان از حافظه را داشته باشد. مثلا اگر چند فرایند درحال اجرای یک برنامه هستند، به جای اینکه هر فرایند کپی جداگانه ای از برنامه داشته باشد، بهتراست همه فرایندها به یک کپی ازبرنامه دسترسی داشته باشند. فرایندهایی که باهمکاری یک وظیفه راجلو می برند، ممکن است لازم باشد در دسترسی به ساختمان داده ای شریک باشند. پس سیستم مدیریت حافظه بایددسترسی کنترل شده به نواحی مشترک حافظه را با درنظرگرفتن اصول حفاظتی اجازه دهد. سازمان منطقی معمولادرسیستم کامپیوتری حافظه بصورت فضای آدرس خطی یا یک بعدی سازمان یافته وشامل د نباله ای ازبایتها یا کلمه ها ا ست. حافظه ثانوی نیزدرسطح فیزیکی به شکل مشابهی سازمان یافته است. اگرچه این ساختار منعکس کننده سخت افزار وا قعی ماشین می باشد، ولی ارتباطی به روشی که برنامه ها ساخت یافته اند ندارد. اکثر برنامه ها به صورت مجموعه ای از مؤلفه هاسازمان یافته ا ندکه بعضی ازآنهاغیرقابل تغییر(فقط خواندنی، فقط اجرایی) وبعضی دیگرشامل داده های قابل تقسیم هستند. سازمان فیزیکی حافظه کامپیوتر حدا قل دردو سطح سازمان یافته است : حافظه اصلی وحافظه ثانوی . حافظه اصلی دسترس سریع را در ازای بهای نسبتآ زیاد ارائه می دهد . حافظه اصلی ناپایدار است یعنی نمی توا ند برای ذخیره دا ئمی بکاررود. حافظه ثانوی کندترو ارزا نتر ازحافظه اصلی است و ناپایدار هم نیست. پس حافظه ثانوی با ظرفیت زیاد برای ذخیره طولانی مدت برنامه هاوداده ها در دسترس قرارمی گیرد، درحالی که حافظه اصلی کوچکتر، حاوی برنامه ها وداده های درحال استفاده میباشد. قطعه بندی روش جایگزین برای تقسیم برنامه کاربر ، قطعه بندی است . دراین روش، برنامه وداده های مربوط به تعدادی قطعه تقسیم می شوند. لزومی ندارد همه قطعه های تمام برنامه ها دارای اندازه یکسان باشند، گرچه حداکثر برای طول قطعه وجوددارد. به دلیل به کارگیری قطعه های غیر هم اندازه ، قطعه بندی مشابه بخش بندی پویا است.درنبود یک طرح روی هم گذاری ویا به کارگیری حافظه مجازی،لازم است کلیه قطعه های برنامه برای اجرا درحافظه بارشوند. تفاوت آن بابخش بندی دراین است که یک برنامه می تواند بیش ازیک بخش رااشغال کندولزومی ندارد این بخشهاپیوسته باشند. قطعه بندی تکه تکه شدن داخلی راحذف می کندولی همانند بخش بندی پویا ، دارای اشکال تکه تکه شدن خارجی است . ولی ازآنجا که یک فرایند به قطعه های کوچکتر شکسته شده است، تکه تکه شدن خارجی کمتر خواهد بود. قطعه بندی معمولا قابل رؤیت وعامل تسهیل سازماندهی برنامه ها وداده ها میباشد. معمولا برنامه ساز یا مترجم ، برنامه وداده ها را به قطعه های مختلف تفکیک می کنند. به منظور برنامه سازی مؤلفه ای نیز ممکن است برنامه و داده ها به قطعه هایی تقسیم گردد. سختی این روش بیشتردراین است که برنامه ساز باید از محدودیت حداکثراندازه یک قطعه آگاه باشد. پیامد وجود قطعه هایی باا ندازه های مختلف این است که رابطه ساده ای بین آدرسهای منطقی وآدرسهای فیزیکی وجودندارد. طرح قطعه بندی ساده، ازیک جدول قطعه برای هر فرایند وفهرستی ازبلوکهای آزاد درحافظه اصلی استفاده میکند. هر مدخل جدول قطعه ،آدرس شروع قطعه مورد نظردرحافظه اصلی را میدهد. همچنین طول قطعه نیز دراین مدخل وجوددارد، تا مطمئن شویم دسترسیهای غیر مجاز ا نجام نمی گیرند. هنگامی که فرایندی به حالت اجرا میرود، آدرس جدول قطعه آن درثبات خاصی که مورد استفاده سخت ا فزار مدیریت حافظه است، بارمیشود. یک آدرس n+m بیتی رادرنظر بگیرید که درآن nبیت سمت چپ شماره قطعه وm بیت سمت راست شماره ا نحراف هستند. مراحل زیر برای ترجمه آدرس لازم هستند: استخراج شماره قطعه از n بیت سمت چپ آدرس منطقی استفاده ازشماره قطعه به عنوان شاخص به جدول قطعه فرایند برای آدرس فیزیکی شروع آن قطعه مقایسه انحراف موجود درm بیت سمت راست با طول قطعه، اگرا نحراف بزرگتر ازطول قطعه باشد، آدرس معتبر نیست. آدرس فیزیکی مورد نظر عبارت است از مجموع آدرس فیزیکی شروع قطعه وا نحراف تکه تکه شدن مشکل تکه تکه شدن (و یا بطور د قیق تر تکه تکه شدن خارجی) ازآنجا ناشی میشودکه پردازش ها متفاوت است بنابراین وقتی که یک پردازش بخارج منتقل میشود، فضایی از حافظه باقی می ماند که ا ندازه آن متغییر است. همینطور، وقتی که یک پردازش را بداخل حافظه منتقل می کنیم باید فضایی ازحافظه را یافت که برای جادادن پردازش کافی باشد. اگرفضای آزادحافظه به نواحی کوچک تقسیم شده باشد، آنگاه گفته می شودکه حافظه تکه تکه شده است . پس درنتیجه حالتی وجود داردکه درآن ا ندازه برنامه کوچکترازکل فضای آزاد است، ولی یک قطعه حافظه پیوسته که برای جادادن برنامه کافی باشدوجود ندارد. تکه تکه شدن تا حدزیادی وابسته است به تکنیکی که جهت حفظ یک مجموعه فضای آزاد وتخصیص حافظه ازاین مجموعه بکارمی آید. محل برنامه مشکل محل برنامه تاحد زیادی مربوط به نحوه استفاده برنامه ازفضای آدرس مجازی خود می شود. اگرچه این فضای آدرس بصورت یکنواخت است، یعنی همه نقاط حافظه دارای خصایص مشابه هستند، لیکن دستیابی به نقاط گوناگون حافظه به هیچ وجه بصورت یکنواخت نیست .ازاین رو را ندمان به دوجهت پائین می آید: پراکندگی استاتیک پراکندگی دینامیک استفاده از کد و داده ها بصورت اشتراکی منظوراز استفاده اشتراکی این است که تعدادی برنامه به محل بخصوصی ازحافظه اجازه دسترسی مشترک داشته باشند. مثلاJoblist که را بطی است بین سیستم ورودی و زمانبندکار توسط این دو پردازش بصورت مشترک مورد استفاده قرار میگیرد. بعلاوه مواردی وجود دارندکه درآنها منافع زیادی دراستفاده اشتراکی ازکد وجود دارد. برای مثال ، در یک سیستم اشتراکی زمانی که تعدادی پردازش ازیک کامپایلر استفاده می کنند، توا نایی استفاده اشتراکی از یک کپی کد کامپایلر توسط تمام برنامه ها دارای منافع مهمی هم از جهت اشتغال کلی حاقظه وهم زمان های مبادله است، زیرا دیگرلازم نیست که هر بار یک کپی از کامپایلر بهمراه هر پردازش بداخل یا خارج حافظه مبادله گردد. برای اینکه بتوان از برنامه ها بصورت اشتراکی استفاده نمود، اینگونه برنامه ها بایستی بصورت کد خالص بیان شده باشد. یعنی (الف) برنامه به هیچ وجه خود اصلاح نباشد،(ب) داده های برنامه جدا ازخود برنامه نگهداشته شوند(احتمالا این داده ها توسط یک یا چند ثبات که بدانها می توان مقادیر مختلف در پردازش های مختلف داد، مورد دسترسی قرار می گیرند) . کاملا واضح است که نه از برنامه ای که خودرا تغییر می دهد می توان مشترکا استفاده نمود، ونه از برنامه ای که نتوا ند نواحی داده های متفاوتی برای هدر پردازشی که ازآن استفاده میکند داشته باشد. در ماشینی که تنها دارای یک ثبات پایه ـ حد است ، استفاده اشتراکی کنترل شده و حفاظت شده از کد و داده ها را به سختی می توان پیاده نمود. برای مثال، شرایط موجود در شکل زیر را در نظر بگیرید. حافظه اصلی داده های پردازش 2 داده های پردازش 1 کد استفاده اشتراکی در سیستم تک پایه ـ حد ثباتی در اینجا دو پردازش از یک کد بصورت اشتراکی استفاده می کنند، وهر پردازش دارای ناحیه داده های خود است. اگر چه می توان از ثبات پایه ـ حد برای پردازش شماره 1 استفاده نمود تا فضای آدرس آن را محدود به کد و ناحیه داده هایش کند، ولی نمی توان چنین عملی را برای پردازش شماره 2 نیز تکرار کرد. اگر هردو پردازش جزو سیستم عامل باشند، شاید چنین نقصانی را در سیستم حفاظت اجازه داد، زیرا اکثر پردازش های سیستم عامل کاملا ا متحان شده ومورد اعتماد هستند. ولی، در موارد عمومی تری که برنامه های کاربران نیاز به استفاده اشتراکی از کد دارند چنین سیستم حفاظتی کاملا غیر قابل قبول است . قطعات اشتراکی تقسیم کردن ا نباره مجازی به قطعات، راه راحت و منطقآ تمیزی را جهت استفاده اشتراکی ازاطلاعات توسط برنامه ها می گشاید. برنامه ها می توانند از یک یا چند قطعه بخصوص بصورت اشتراکی استفاده کنند بدون آنکه میزان حفاظتی که هر یک از آنها برای بقیه ا نباره مجازی اش انتظار دارد تقلیل یابد. البته سازمان دهی جدولهای سیستم عامل بگونه ای که بتوان از قطعاتی بصورت اشتراکی استفاده کرد، هنوز مشکلاتی را برای طراح سیستم فراهم می آورد، زیرا حداقل سه روش گوناگون برای ساختن این جدولها وجود دارند. این روشها عبارتند از (الف) همه مستقیم ،(ب )یکی مستقیم بقیه غیر مستقیم (پ) همه غیر مستفیم . ا نتخاب یکی ازتکنیکهای فوق برای هر سیستم بخصوص، احتمالا تا حدزیادی وابسته است به ا مکانات سخت ا فزار برای دو باره بار کردن ثباتها پایه ـ حد، همچنین سایر قیودی که درمورد کارایی سیستم وجود دارند. قطعات مشترک یک مورد ویژه استفاده اشتراکی از اطلاعات مربوط به فراهم آوردن برخی از نرم افزارها پر متقاضی از قبیل کامپایلرها، ویرایشگرها، کتابخانه ریاضی،وغیره می شود. درحالت ایده آل ،اگر ماشین قادربه فراهم آوردن یک فضای آدرس مجازی بزرگ باشد، می توان براحتی تمامی اینگونه امکانات را مستقیمآ در انبار مجازی استفاده کننده پیش ـ بار کرد. پس، این قبیل امکانات به سادگی در اختیار برنامه قرار داده می شوند، بدون اینکه لزومی به طی کردن مراحل مختلف جهت بازکردن کتابخانه ها وغیره باشد. ولی متاسفانه معمولاچنین فضای آدرس مجازی را نمی توان برای تعداد زیادی استفاده کننده فراهم آورد زیرا بهر حال فضای کل حافظه حقیقی محدود است. البته، می توان برای همه اینچنین فطعه هایی، که به مقدار زیاد مورد دستیابی قرار می گیرند، در جدول قطعه هر برنامه مدخلهایی قرار داد. ولی در اینجا مقدار زیادی از حافظه از دست رفته است زیرا یک سری اطلاعات یکسان در تعداد زیادی جدول قطعه برنامه قرار میگیرند. در اینجا لازم است بر روی تفاوت بین قطعه های اشتراکی و قطعه های مشترک تاکید شود. نوع اول ، یعنی قطعه های اشتراکی ،معمولا کم هستند، بهر حال توسط تمامی برنامه های موجود در سیستم مورد استفاده قرارنمی گیرند ، بلکه ممکن است دو یا سه برنامه (یا بیشتر)از یک قطعه بصورت اشتراکی استفاده کنند. حال آنکه قطعه های مشترک حاوی اطلاعات وکدهایی هستند که ما میل داریم در اختیار تمامی برنامه های استفاده کنندگان قرار دهیم . یک راه حل این است که یک جدول مجزا مخصوص قطعه های مشترک داشت . تمامی آدرسهای مجازیی که در بالای یک شماره قطعه معین قرار دارند با استفاده از اطلاعاتی که در یک جدول قطعات مشترک وجوددارند ترجمه می شوند، یعنی برای ترجمه آدرسهایی که از یک قطعه استفاده نمی شود. اگر بار کردن ثبات های پایه ـ حد بعهده نرم افزار باشد، این روش می تواند منافع اضافی دیگری هم داشته باشدزیرا در هنگام تعویض برنامه ها تنهاN ثبات اول را بایستی دوباره بارکرد. حتی اگر سخت افزار بصورت اتوماتیک ثباتهای پایه ـ حد را بار می کند، باز هم ممکن است اینگونه بهینه سازی صورت گیرد. چنین ماشینی معمولادارای دو ثبات پایه است که یکی برای جدول محلی قطعه برنامه جاری است و دیگری برای جدول قطعات مشترک است . صفحه بندی پدیده تکه تکه شدن به این دلیل بوجود می آید که فضای حافظه بصورت واحدهایی باا ندازه های متفاوت به برنامه ها اختصاص می یابد. راه حل این است که حافظه بصورت واحدهایی با اندازه های ثابت ویکسان به هر برنامه اختصاص یابد. به اینکار صفحه بندی، می گویند. در اینجا فضای انباره هر استفاده کننده (مثلا هربرنامه) که بدان فضای قابل آدرس دادن هم می گویند، به تعدادی صفحه با اندازه های یکسان تقسیم می شود. اگر چه استفاده کننده یک فضای حافظه بلااستفاده متوجه اینگونه تقسیم بندی نمی شود، ولیکن هرآدرس مجازی بایستی بگونه ای ساخته شود که نگاشت صفحات را برای ا نباره حقیقی میسر سازد. بنابراین ، مکانیزم ترجمه آدرس فرض می کندکه هر آدرس مجازی دارای قالبی بصورت زیر است . آدرس مجازی Displacement Page این تقسیم بندی حافظه، یعنی صفحه بندی، را نبایستی با مسئله قطعه بندی اشتباه گرفت. گفتیم که قطعه بندی یک تقسیم منطقی حافظه مجازی است، وهر قطعه میتوانست اندازه های متفاوت ودارای صفات حفاظتی متفاوت باشد. بدین ترتیب، یک قطعه ممکن است حاوی یک فایل کامل از نوع متن باشد و یا یک کامپایلر رادرخود جای دهد. ازطرفی، صفحه بندی عبارتست از تقسیم عملی حافظه مجازی، وهدف اصلی آن جلوگیری ازتکه تکه شدن حافظه است. صفحات دارای اندازه ثابت هستندو معمولا این مقدار خیلی کمترازا ندازه قطعه می باشند. نقطه ضعف مکانیزم صفحه بندی این است که اگر فقط احتیاج به ناحیه بسیارکوچکی ازانباره باشد، دراین صورت مقداری ازفضای حافظه تلف می شود، زیرا کوچکترین واحدی ازانباره که می توان آنرا به استفاده کننده اختصاص دادیک صفحه است . به این مشکل، تکه تکه شدن داخلی می گویند. درماشینهای گوناگون برای کم کردن اثراین مشکل اندازه های گوناگونی برای صفحه انباره ماشین انتخاب شده است . فرض کنید حافظه اصلی به بخشهای نسبتآکوچک هم ا ندازه وهر فرایند نیزبه تکه های هم اندازه با آنهاتقسیم شود. سپس تکه های یک فرایند که صفحه نام دارد بتواند به تکه های موجود حافظه که قاب یا قاب صفحه نامیده می شود، تخصیص یابند. دراین قسمت نشان می دهیم که اتلاف حافظه برای هرفرایند، به صورت تکه تکه شدن داخلی و فقط درآخرین صفحه آن فرایند است. در اینجا تکه تکه شدن خارجی وجود ندارد. شماره حافظه اصلی قاب 0 A.0 0 A.0 0 1 A.1 1 A.1 1 2 A.2 2 A.2 2 3 A.3 3 A.3 3 4 4 B.0 4 5 5 B.1 5 6 6 B.2 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 A.0 0 A.0 0 A.0 0 A.1 1 A.1 1 A.1 1 A.2 2 A.2 2 A.2 2 A.3 3 A.3 3 A.3 3 B.0 4 4 D.0 4 B.1 5 5 D.1 5 B.2 6 6 D.2 6 C.0 7 C.0 7 C.0 7 C.1 8 C.1 8 C.1 8 C.2 9 C.2 9 C.2 9 10 C.3 10 C.3 10 11 11 D.3 11 12 12 D.4 12 13 13 13 14 14 14 شکل فوق مثالی ازبکارگیری صفحه ها وقابها را نمایش می دهد. درزمان مشخصی برخی از قابهای حافظه به کار رفته و برخی آزاد هستند. سیستم عامل فهرستی از قابها ی آزاد رانگهداری می کند. فرایند A که دردیسک ذخیره شده است، شامل چهار صفحه می باشد. هنگامی که درزمان بارشدن این فرایند فرا رسد، سیستم عامل چهار قاب آزادرا یافته وچهار صفحه فرایند A رادر آنها بار می کند. فرایند B شامل سه صفحه و فرایند C شامل چهار صفحه هستندکه متعاقبآ بار میشوند. درپی آن فرایند B معلق شده وبه خارج از حافظه اصلی مبادله می گردد. پس از مدتی تمام فرایندهای داخل حافظه اصلی مسدود می شوندولازم می شود سیستم عامل فرایند جدیدD که ازپنج صفحه تشکیل شده است را به داخل بیاورد. حال همان طور که درمثال دیده می شود فرض کنید قابهای آزاد متوالی کافی برای نگهداری این فرایند موجود نباشد. آیا این مطلب جلوی سیستم عامل را جهت بار کردن D می گیرد؟ جواب منفی است ، زیرا می توان یک بار دیگر ازمفهوم آدرس منطقی استفاده کرد، البته دیگر یک ثبات پایه کافی نیست ، بلکه سیستم عامل یک جدول صفحه برای هر فرایند نگهداری می کند. جدول صفحه محل قاب هر صفحه از فرایند را نشان می دهد. درون برنامه، هرآدرس منطقی متشکل ازشماره صفحه وا نحراف درداخل صفحه است . می دانید آدرس منطقی مکان یک کلمه نسبت به شروع برنامه است وپردازنده آن را به آدرس فیزیکی ترجمه میکند. در مورد صفحه بندی ترجمه آدرس منطقی به آدرس فیزیکی همچنان توسط سخت افزار پردازنده انجام می گیرد. البته اکنون پردازنده باید نحوه دسترسی به جدول صفحه فرایند جاری را بداند. بادریافت آدرس منطقی (شماره صفحه ،انحراف)، پردازنده بابه کارگیری جدول صفحه، یک آدرس فیزیکی (شماره قاب ،انحراف) تولید می نماید. درادامه مثال، پنج صفحه فرایند D در قابهای 4،5،6،11و12 بارمی شوند. شکل زیر جداول مختلف صفحه رادر این زمان نشان می دهد. جدول صفحه یک فرایند، شامل یک مدخل برای هر صفحه آن فرایند است، به نحوی که شماره صفحه به راحتی میتواند به عنوان شاخص آن جدول (باشروع ازصفحه صفر) عمل کند. هر مدخل جدول صفحه شامل شماره قابی درحافظه است که صفحه مربوط را نگهداری میکند. ملاحظه می شود صفحه بندی ساده، آن گونه که دراینجا معرفی گردید، مشابه بخش بندی ایستا است. تفاوت دراین است که در صفحه بندی، بخشها کوچک هستندو یک برنامه میتواند بیش ازیک بخش رااشغال نموده و لزومی ندارد که این بخشها پیوسته باشند. برای ساده تر شدن طرح صفحه بندی، تاکید می کنیم که اندازه صفحه ودرنتیجه اندازه قاب باید توانی از2 باشد. دراین صورت آدرس نسبی که نسبت به ابتدای برنامه تعریف شده وآدرس منطقی که به صورت شماره صفحه وانحراف بیان گردیده است یکسان هستند. 13 4 0 7 0 - 0 0 0 14 5 1 8 1 - 1 1 1 6 2 9 2 - 2 2 2 11 3 10 3 3 3 12 4 ماشینهای صفحه بندی قطعه بندی شده یکی ازنقاط ضعف برخی ازسیتمهای صفحه بندی شده که تاکنون تشریح شده که تاکنون تشریح کرده ایم، این است که بایستی جدول صفحه بزرگی را برای هریک ازبرنامه ها نگهداشت. هر چنددر سیستم اطلس ازاینکار اجتناب شد ولیکن درآن تکنیک تمامی انباره اصلی بکمک ثباتهای آدرس صفحه (PAR) نگاشت می شد واین خود هزینه سنگینی رادر برداشت . درسیستمهایی که ازثباتهای صفحه جاری (CPR) برای ترجمه آدرس استفاده می کنند، سخت افزار می توا ند به جدول سیستم دسترسی پیدا کندو ثباتها رابکمک آن دوباره بارنماید. دراینجا مسئله جستجو کردن درجدول صفحه توسط مکانیزم سخت افزاری ترجمه آدرس حائز اهمیت زیادی است. هرگاه هیچیک از CPRها به صفحه مورد نظر اشاره نکنند، مکانیزم سخت افزاری بایستی به جدول صفحه برنامه جاری رجوع کند تا آدرس صفحه در حافظه اصلی را دریابد، البته بشرط اینکه این صفحه وا قعادرحافظه اصلی باشد. بنابراین ساختار جداول سیستم، بگونه ای که یک مکانیزم سخت افزاری بتوا ند براحتی درآن به جستجو ورودی بخصوص بپردازد، اهمیت زیاد وتاثیر فراوانی درکارایی سیستم دارد. پس لازم است، روشی درهنگام ساختن چنین جداول سیستم اتخاذ شود تا بتوان سازمانی فشرده تر برای اینگونه جداول فراهم آورد، ودرعین حال هنوز توا نایی شاخص بندی ساختمان داده ها جهت بدست آوردن یک ورودی معین ازجدول صفحه باقی باشد. راه حل بسیار مؤثری برای اینگونه مشکلات درماشینهایی که هردو تکنیک صفحه بندی و قطعه بندی رابا هم ترکیب می کنندارا ئه شده است. هدف این ماشینها این است که همانند کامپیوترهای چندپایه ـ حدثباتی ازمنافع انباره مجازی قطعه بندی شده استفاده کنند، ودرضمن ازتکنیک صفحه بندی هم بهره مند شوند تا بدین طریق مشکل تکه تکه شدن خارجی راهم حل کرده باشند.در اینگونه ماشینها فضای آدرس دهی مجازی به فیلدهایی که درشکل زیر نشان داده شده تقسیم می شود. Displacement Page Segment در اینجا درهرآدرس مجازی سه فیلد وجوددارند: (الف) قطعه (ب) صفحه مورد نظردردرون قطعه (ج) تفاوت مکان دردرون صفحه جدول قطعه برای هر برنامه یک جدول قطعه وجوددارد. این جداول قطعاتی که دردسترس برنامه قرار دارندرا مشخص می کند، درعین حال مکان جدول صفحه هریک ازاین قطعات را بیان می کند. جدول صفحه هر قطعه دارای یک جدول صفحه است که مکان تمامی صفحات موجوددر قطعه را می دهد. مدیریت حافظه درماشین صفحه بندی قطعه بندی شده ساختمان داده های اصلی این سیستم مدیریت حافظه عبارتنداز جداول قطعه و صفحه که بکمک آنها نگاشت ا نباره مجازی برروی انباره حقیقی صورت می گیرد. تا حدزیادی، قالب این جداول توسط سخت افزار ترجمه آدرس ماشین مورد نظر تعریف می شود. بنابراین، هنگامی که یک طراح سخت افزار مشخصات سیستم ترجمه آدرس را معین می کند بایستی اطمینان حاصل کندکه، باوجود چنین سخت افزاری، انباره مجازی دارای خصایص موردنظرخواهد بود. کارایی کارایی هربرنامه باتوجه به تعداد صفحات برنامه که درحافظه هستند تغییرمی کند. واضح است وقتی برنامه ای Cpu رادراختیار می گیرد تعداد بسیار کمی ازصفحات آن در حافظه قرار دارند ودر نتیجه پس ازاجرای تعداد کمی دستورالعمل، وقفه انباره مجازی اتفاق می افتد. ازطرفی اگر بتوان تمامی یک برنامه و داده هایش رادر حافظه نگاشت، در اینصورت هیچ وقفه انباره مجازی اتفاق نمی افتد. در سیستمهای چند برنامگی واشتراک زمانی ممکن است کمی برنامه با هم در حافظه قرارگیرند.درچنین شرایطی بسختی می توان تصمیم گرفت که چقدرحافظه به هربرنامه بایستی اختصاص یابد. شاید بتوان به اندازه کافی فضای حافظه به هر برنامه اختصاص دادتا بتوان تمامی برنامه رادر آن جای داد. ولی ازطرفی ممکن است فضای مورد نیاز خیال بزرگ باشد. درعمل تا وقتیکه مجموعه کار برنامه درحافظه قرارداد کارایی ماشین درحد خوبی است، و بطورکلی، مجموعه کارهر برنامه بسیار کوچکترازا ندازه تمامی برنامه است . محل این حقیقت که دررا بطه با برنامه هایی که بزرگترازا ندازه حافظه اصلی هستند میتوان کارایی خوبی را بدست آورد به علت پدیده ای به آن، محل یا موضع نام دارد. بصورت غیررسمی، پدیده محل عبارتست از تمایل برنامه ها در خوشه ای کردن ارجاعاتشان به صفحات، که درآن تعداد نقص صفحات در مقابل ا ندازه انباره(حافظه اصلی) برای یک برنامه نشان داده شده است واضح است که حتی برای یک ا نباره بسیاربزرگ، درابتدا تعداد کمی نقص صفحه رخ میدهد تاصفحات بداخل حافظه آورده شوند. پس ازآنکه تمام صفحات درحافظه اصلی قرارگرفتند، ازآن به بعد برنامه دیگر نقص صفحه ایجاد نمی کند. اگراندازه انباره کمترازا ندازه برنامه باشد، ممکن است تعداد بیشتری نقص های صفحه رخ دهد زیرا این ا مکان وجوددارد که صفحاتی که بعدا مورد نیازخواهند بود ازحافظه خارج گردند. ولی تعداد نقص های صفحه باکاهش اندازه ا نباره بصورت خطی افزایش نمی یابد، زیرا برخی صفحات که ازحافظه به خارج فرستاده شد ند ممکن است هرگز مورداستفاده مجدد قرارنگیرد. این نتیجه پدیده محل است. در مقایسه بابرنامه های نوعی، برنامه ای که به صفحاتش بصورت اتفاقی دست می یابد کارایی بسیاربدی را(تعدادبیشتری نقص های صفحه) برای انباره ای باا ندازه معین عرضه می کند. دریک سیستم اشتراک زمانی نیز نکات مشابهی را می توان درباره هرفعل وا نفعال بیان کرد. درآغاز یک برش زمان صفحات برنامه برروی ا نباره پشتوا نه ای قراردارندو بنابراین لازم است صفحه هایی که درطی برش زمانی مورد استفاده قرار می گیرند به داخل حافظه آورده شوند. تعداد نقص هایی صفحه اضافی بستگی بمقدار ا نباره ای دارد که دراختیار برنامه قرار دارد، واین مقدارمی تواند برا بر بااندازه ا نباره حقیقی اصلی باشدو یا به ا ندازه فضایی که توسط سیستم عامل به برنامه تخصیص یافته است . دراصل پدیده محل را می توان دوتاپدیده مجزا دا نست که باهم درفعل وانفعالات هستند. یکی محل زمانی ویکی محل فضایی. منظور ازمحل زمانی این است که اگر به صفحه ای دستیابی صورت گیرد باحتمال زیاد بزودی هم بدان دستیابی صورت میگیرد. منظورمحل فضایی این است که اگریک صفحه مورد دستیابی قرارگیرد، به احتمال زیاد صفحات مجاورآنهم بزودی مورد دستیابی قرارخواهند گرفت. هردوپدیده بصورت طبیعی ودراثر برنامه نویسی عادی بروزمی کنند. برنامه نویسان معمولا می توانند روالها و داده هایی که بطور همزمان مورد استفاده قرار میگیرند را نزدیک همدیگر در ا نباره قرار دهندو به این ترتیب کارایی برنامه های خود را بمیزان زیادی بهبود بخشد. ازنقطه نظر سیستم عامل، محل زمانی وفضایی چندان مفاهیم مفیدی نیستند، وبه محل بصورت یک پدیده نگریسته می شودکه درمفهوم کاربیان می گردد. مجموعه کاریک برنامه دریک زمان بخصوص عبارتست از مجموعه صفحاتی که برنامه درآن زمان در حافظه اصلی بدانها نیاز دارد. الگویتم های جایگزینی صفحه هنگامی که برنامه ای دریک ا نباره کوچک اجرا شود، کارایی برنامه تا حدی بستگی به الگوریتمی خواهد داشت که ازآن جهت بیرون کردن صفحات ازحافظه اصلی استفاده شده است، یعنی الگوریتم جایگزینی. باردیگربایستی تاکید کرد که اگر حافظه اصلی شدیدا کوچک باشد، حتی بهترین الگوریتم جایگزینی نمی تواندکارایی خوبی نشان دهد. برای اینکه یک کارایی معقول وجودداشته باشد باید حجم حافظه حداقل باندازه مجموعه کاربرنامه باشد. دراین حالت هدف الگوریتم جایگزینی این خواهد بود که صفحه ای را برای جایگزینی ا نتخاب کند که در مجموعه کار برنامه نباشد. دراین قسمت به الگوریتم های جایگزینی اشاره ای می شود: جایگزینی بلیدی اپتیمال BO اخیرا کمترین استفاده شده LRU الگوریتم اولین صادره اولین وارده FIFO الگوریتم اخیرا استفاده نشده NRU - جایگزینی بلیدی اپتیمال BO این الگوریتم بدلایل تاریخی دراینجا ذکر شده است زیری اولین بررسی همه جانبه ومؤثر الگوریتمهای جایگزینی توسطBelady در سال1966صورت گرفت چندین الگوریتم بکمک شبیه سازی مطالعه شدند،ویک الگوریتم جایگزینی عرضه شدوثابت گردید که اپتیمال است. الگوریتم ازاین قراراست : ‹صفحه ای راجایگزین کنید که دوباره برای طولانی ترین مدت مورد نیازنخواهدبود› این الگوریتم مترادف است با اینکه سعی شود مجموعه کار یک کار درحافظه نگهداشته شود. ولیکن این الگوریتم آنقدرها عملی نیست زیرا معمولا نحوه والگوی رجوعهای آینده به صفحات ازقبل معلوم نیست. فایده اصلی این الگوریتم این است که ازآن بعنوان یک معیار استفاده می گرددتا سایرالگوریتم هامورد ارزیابی ومقایسه قرارگیرند. البته این الگوریتم دراپتیمال کردن کامپایلرها نیز موارد استعمال دارد. درکامپایلر ممکن است ازآن جهت تخصیص ثباتها استفاده گردد زیرا درآنجا اغلب الگوهای رجوعهای آینده به ثباتها ازپیش معلوم است. ـاخیرا کمترین استفاده شده LRU گفتیم که پدیده محل برنامه بدین معناست که مجموعه کار یک برنامه خیلی به کندی درطول زمان تغییرمی کند. به این ترتیب تاریخچه رجوع به صفحات درگذشته بسیارنزدیک معمولا میتوانند بخوبی مبین ارجاعات درآینده نزدیک باشند، و تقریب بسیار نزدیکی به الگوریتم BO بصورت زیر بدست می آید: ‹صفحه ای راجایگزین کنیدکه اخیرا کمترین استفاده ازآن شده است.› یعنی، صفحه ای که طولانی مدت، خارج ازاستفاده بوده است.این الگوریتم اخیراکمترین استفاده بوده است. این الگوریتم اخیرا کمترین استفاده شده یا LRU نام داردودر عمل نشان داده شده که بخوبی عمل می کند. مشکل LRU این است که پیاده سازی آن سخت است، جهت پیاده سازی واقعی LRU لازم است سخت افزار برای هرصفحه حافظه اصلی علامتی نگهدار که بیانگر‹گذشت زمان نسبت به آخرین استفاده› باشد. بدون چنین امدادی علامتی ازطرف سخت افزار استفاده کندکه در زمان نقص صفحه بدست می آیند. یعنی قراردادن یک هزینه اضافی نرم افزاری در هر دستیابی به صفحه عملی نیست و بنابراین اطلاعات مورد نیازالگوریتم راتنها درطی نقص های صفحه که البته امیدواریم کم باشند می توان جمع آوری کرد. بدترین حالت برای الگوریتم رد LRU(ودر حقیقت برای تمام الگوریتم های معمولی که پیش بینی کننده نیستند) در مواقعی بروز می کندکه برنامه به صفحاتش در حافظه اصلی بصورت چرخه ای دست می یابد ولی حافظه اصلی باندازه کافی بزرگ نیست. برای مثال اگردستیابی به انباره بصورت زیر باشد: {…،2048،1024،0،4046،3072،2048،1024،.} وحافطه اصلی چهارکیلوبایت باشد واندازه هر صفحه یک کیلوبایت، دراین صورت برای هررجوعی یک نقص صفحه رخ می دهد. اینکه چرا عملکرد دستیابی چرخه ای دررابطه با بسیاری ازالگوریتم ها جایگزینی تااین حد بداست، پس ازبکاربردن الگوریتمBO دراین رابطه مشهودمی گردد. الگوریتم BO دراین حالت نشان می دهد که بهترین انتخاب جهت رد، همیشه آخرین صفحه ای است که اخیرا مورد دستیابی قرار گرفته، یعنی اخیرترین دستیابی. این عملا خلاف آن چیزی است که با توجه به اصل محل می توان انتطار داشت. واضح است که برنامه هایی که دارای دستیابی های چرخه ای به انباره می باشند،ازخود محل زمانی بسیار ضعیفی نشان می دهند. ـ الگوریتم اولین صادره اولین وارده FIFO ازاین الگوریتم مکررا استفاده می شودزیرا پیاده سازی آن بسیارساده است.دراینجا صفحه ای جایگزین میشود که برای طولانی مدت درحافظه بوده است. به سادگی می توان دلیل قابل درکی برای این انتخاب یافت، صفحه ای که مدتها پیش به داخل حافظه آورده شده است ممکن است حالادیگرمورداستفاده نباشد. ازطرفی دیگرممکن است از این صفحه اززمانیکه به داخل حافظه آورده شده است مرتبا استفاده گردیده باشد، دراین صورت این انتخاب بسیار بد برای جایگزینی می باشد. عملکرد جایگزینی FIFO هم دررابطه با دستیابی چرخه ای خیلی پایین است. ولیکن، این روش نقطه ضعف دیگری هم دراین رابطه ازخود نشان می دهدکه بدان تناقض FIFO می گویند. برای دستیابی های بخصوصی به صفحات ممکن است که، اگرازالگوریتم FIFO استفاده شده باشد، باافزایش اندازه انباره(حافظه اصلی) تعداد نقص های صفحه هم افزایش یابد. واضح است که این حالت اصلا قابل قبول نیست. هرچند که نسبتا به ندرت انباره حقیقی یک ماشین گسترش می یابد، لیکن وجود تناقص FIFO می تواند دریک سیستم چندبرنامگی صفحه بندی شده خیلی جدی باشد. درچنین سیستمی ممکن است سیستم عامل سهمیه ای ازانباره رابه هر کاراختصاص دهد، اگرتعداد نقص صفحه مربوط به یک برنامه خیلی زیاد باشد،سیستم عامل اندازه این سهمیه رابالامی برد. درچنین شرایطی F1 تناقص FIFO می تواند مخرب باشد. بعنوان مثال، دستیابی به صفحات زیر رادر نطر بگیرید: {5،1،2،3،4،5،3،4،1،2،3،4} جریان رادر رابطه بادو اندازه مختلف برای انباره دنبال می کنیم، یکی سه صفحه ودیگری چهارصفحه. اگر اندازه سه صفحه باشد،تعداد9 نقص صفحه رخ میدهد(صفحاتی که برای آنهانقص صفحه با‘ مشخص شده اند) : {5،‘1،‘2،3،4،‘5،‘3،‘4،‘1،‘2،‘3،‘4} اگراندازه انباره چهار صفحه افزایش دهیم، تعدادده نقص صفحه رخ می دهد: {‘5،‘1،‘2،‘3،‘4،‘5،3،4،‘1،‘2،‘3،‘4} توجه کنید که درFIFO، صفحه ای رد می شودکه طولانی ترین مدت رادر انباره بوده است، بدون اینکه توجهی به جدیدترین دستیابی شود. جهت مقایسه، مثال بالا رادررابطه باLRU بررسی می کنیم: اگر اندازه انباره سه صفحه باشد: ده نقص صفحه: {‘5،‘1،‘2،3،4،‘5،‘3،‘4،‘1،‘2،‘3،‘4} واگر اندازه انباره چهارصفحه باشد: فقط هشت نقص صفحه رخ می دهد: {‘5،‘1،‘2،3،4،‘5،3،4،‘1،‘2،‘3،‘4} وجوچنین موارد خطرناکی استفاده ازالگوریتم هایی چون FIFO را نگران کننده میسازد. بعدا نشان داده خواهد شدکه الگوریتم های LRU,BO ودرحقیقت گروهی ازالگوریتم ها که بدان الگوریتم پشته ای می گویندواین درنیز جزء آن هستند، چنین عملکردی از خود نشان نمی دهند.ولی قبل ازاین کاریک الگوریتم جایگزینی دیگررا بررسی می کنیم. ـ الگوریتم اخیرا استفاده نشده NRU این الگوریتم سعی می کند صفحاتی راکه درحافظه اصلی هستند به دودسته تقسیم کند، آنها که اخیرا مورداستفاده قرارگرفته ا ندوآنها که اخیرا مورداستفاده قرار نگرفته اند. هرصفحه ای که اخیرا مورد استفاده قرار نگرفته است رد می شود. در رایج ترین نحوه پیاده کردن این الگوریتم ازیک الگوریتم جایگزینی FIFO استفاده میشود، منتهی FIFO به گونه ای تغییر یافته است تابه صفحاتی که اخیرا مورد استفاده قرار گرفته ا ند شانس دیگری برای باقی ماندن در حافظه اصلی بدهد به این ترتیب که: هنگامی که به صفحه ای دستیابی می شود،آن صفحه به صورت رجوع شده علامت گذاری می گردد.(برای این کارنیاز به کمک سخت افزاراست، ولی سخت افزارموردنیازنسبتاارزان است ودراکثرسخت افزارهای صفحه بندی وجوددارد.) هنگامی که نیازبه ردکردن صفحه ای وجوددارد، صفحات موجوددرحافظه فقط بصورت چرخه ای پیمایش می شوند. مثل FIFO. اگرصفحه ای که مورد بررسی است بعنوان رجوع شده علامتگذاری نشده باشد،این علامت رجوع نشده تغییرمییابد،والگوریتم رد انباره جلومی رود تا صفحه بعدی را بررسی کند. دفعه دیگری که این صفحه مورد بررسی قرارمی گیرددارای علامت رجوع نشده است مگرآنکه در این مدت دوباره مورد دستیابی قرار گرفته باشد. پیاده کردن این الگوریتم آسان است ـ حتی به آسانی یک الگوریتم FIFO ـ ولی عملا تقریبی است ازالگوریتم LRU. در نتیجه کارایی آن بهتر ازFIFO است. ولیکن، هنوز برای برخی الگوهای دستیابی امکان بوجودآمدن تناقص FIFO وجوددارد(لزوما الگوی دستیابی که باعث تناقص در الگوریتم NRU می شودبا الگویی که باعث تناقص درالگوریتم FIFOمی گرددیکسان نیست). ایده NRU را می توان تعمیم دادتا تقریب نزدیکتری به LRU بدست آورد، برای اینکارلازم است صفحات حافظه به بیش از دو گروه تقسیم گردند وعمل رد در رابطه با گروهی که اخیرا کمترین استفاده ازآن شده صورت گیرد. ساده ترین طریق انجام اینکار عبارتست ازقرار دادن یک شمارنده در رابطه با هر صفحه. هرگاه به صفحه ای رجوع می شود،شمارنده برابر با مقدار معینی چون X قرار داده میشود. هربار که صفحه برای رد ازانباره مورد بررسی قرارمی گیرد ازشمارنده آن یکی کسر می گردد وتنها در صورتی صفحه به خارج از حافظه فرستاده می شودکه مقدار شمارنده برابر با صفر باشد. واضح است که مقدار X نیاز به تنطیم دقیق دارد، زیرا اگر خیلی زیاد باشد، چندین بار بیهوده بایستی در لیست صفحات گشت تا بالاخره یک کاندید مناسب جهت اخراج ازحافظه انتخاب گردد. به مرور می توان X را طوری تنطیم نمود تا بهترین حالت پخش صفحه ها در گروهها صورت گیردبطوریکه همیشه صفحاتی جهت رد در گروه صفر(یعنی جایگزین پذیران) در دسترس باشند. الگوریتم های پشته ای در سیستم چندبرنامگی، وجود تناقص FIFO نگران کننده است، زیرا هر چند که ممکن است زیاد رخ ندهد ولیکن می تواند باعث شکست هر گونه محاسبه ای جهت تخصیص اپتیمال حافظه بین کارها گردد. بنابراین، تدوین الگوریتم هایی که چندین خصیصه غیر عادی رااز خود نشان نمی دهند مورد توجه می باشد. می توان نشان داد که یک طبقه الگوریتم ها که به آنها الگوریتم های پشته ای می گویند(LRU,BO جزءآن می باشند) دچار چنین ضعفی نیستند. یک الگوریتم پشته ای بصورت زیر تعریف می گردد: فرض کنیدS(A,P,K,N) مجموعه صفحه هایی باشد که در هنگام پردازش رجوع به صفحه Kام از اثر صفحهP (PAGE TRACE ) با استفاده از الگوریتم جایگزینی A در صفحه باندازه N صفحه موجودباشد. [منظور از اثر صفحه صفحاتی از برنامه هستندکه به ترتیب مورد دستیابی برنامه قرار می گیرند، ومنظور از رجوع Kام همان رجوع به Kمین صفحه ازاین اثر صفحه می باشد]. حال، درصورتی A یک الگوریتم پشته ای است که برای تمامی N,K,P : S<(A,P,K,N)<=S(A,P,K,N+1) یعنی اگر اندازه انباره افزایش یابد، در هر زمانی همان مجموعه صفحات در انباره خواهندبود که برای انباره کوچکتر بودند، بعلاوه احتمالا تعدادی بیشتر. واضح است که اگر این شرایط ارضاء شوند هرگز نمی توان با انباره بزرگتر، نقص های صفحه بیشتری داشت. براحتی می توان نشان داد که BO,LRU در حقیقت الگوریتم های پشته ای هستند، زیرا آخرین Nصفحه مجزایی ازP که مورد استفاده قرار گرفته اند S(LRU,P,K,N) = آخرین N+1صفحه مجزایی ازP که مورد استفاده قرار گرفته اند S(LRU,P,K,N+1) = وواضح است که: S(LRU,P,K,N)<=S(LRU,P,K,N+1) صورت مشابهی در الگوریتم BO داریم Nصفحه مجزایی ازP که مورد استفاده قرار گرفته اند S(BO,P,K,N) = N+1صفحه مجزایی ازP که مورد استفاده قرار گرفته اند S(BO,P,K,N+1) = وبنابراین: S(BO,P,K,N)<=(BO,P,K,N+1) برای مقایسه بین LRU,BO ودرک بیشتر مطلب به مثال زیر توجه کنید. درجدول زیر وضعیت داخل حافظه پس از رجوع به هر یک از عناصر اثر صفحه نشان داده شده اند. در ضمن دو سری جدول، یکی برای حافظه ای به اندازه 3صفحه ودیگری 4 صفحه ارائه گشته اند. توجه داشته باشید که در هر مورد صفحات داخل حافظه با توجه به الگوریتم مورد استفاده مرتب شده اند. این مثال به وضوح نشان می دهدکه الگوریتم FIFO شرط فوق را ارضاء نمی کند. LRU FIFO 3 4 5 3 4 1 2 3 4 3 4 5 3 4 1 2 3 4 5 5 5 3 4 1 2 3 4 3 4 5 3 4 1 2 3 4 3 3 3 4 1 2 3 4 - 4 5 3 4 1 2 3 4 - 4 4 4 1 2 3 4 - - 5 3 4 1 2 3 4 - - 3 4 5 1 1 1 2 3 4 3 4 5 3 4 1 2 4 4 4 5 1 2 2 2 3 4 - 4 5 3 4 1 2 3 3 - 5 1 2 3 3 3 4 - - 5 3 4 1 2 3 4 - - 1 2 3 4 4 4 - - - 1 1 1 2 3 4 - - - چند برنامگی تاکنون تاثیر صفحه بندی را تنها برای یک استفاده کننده بررسی کرده ایم. ولیکن به سیستمی که توانایی پشتیبانی از چند برنامگی را داشته باشد نیازاست ووجودچنین نیازی معیارهای جدیدی رابرای سیستم صفحه بندی ایجاب می کند. قبلا توجه داده شده که زمانی که صرف مبادله کاری بداخل حافظه اصلی دریک سیستم صفحه بندی براثر تقاضا می گردد( یعنی زمانی که صرف آوردن مجموعه کاربه داخل حافظه می شود) می تواند به مراتب بیشتر اززمانی باشد که صرف آوردن کاری بااندازه یکسان ولی دریک سیستم صفحه بندی نشده می گردد،زیرا در اولی هزینه های رکورد برای انتقال هر


دسته‌بندی نشده

سایت ما حاوی حجم عظیمی از مقالات دانشگاهی است . فقط بخشی از آن در این صفحه درج شده شما می توانید از گزینه جستجو متن های دیگری از این موضوع را ببینید 

کلمه کلیدی را وارد کنید :

دسته بندی: دسته‌بندی نشده

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

مطالب مرتبط

دسته‌بندی نشده

2 (12256)

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

دسته‌بندی نشده

2 (12257)

دانشگاه آزاد اسلامی (واحد ابرکوه) سازمان خدمات بهزیستی استاد راهنما: جناب آقای مهندس مجتبی کوثری دانشجویان: امیرحسین غلام‌آزاد مرتضی تیموری سال تحصیلی 87 ـ 1386 با تشکر از زحمات اساتید بزرگوار جناب آقای کوثری و ادامه مطلب…

دسته‌بندی نشده

2 (12255)

قدیمی ترین شاعر زن ایرانی استاد راهنما : جناب آقای نیک روش گردآورنده : سید هاشم موسوی IT6 پاییز 87 رابعه بنت کعب قدیمی ترین شاعر زن حضور زنان در تاریخ ادبیات هم همچون دیگر ادامه مطلب…

background