فایل کامل و عالی مقاله در مورد سیستم های REAL TIME

بخشی از متن فایل کامل و عالی مقاله در مورد سیستم های REAL TIME :

سیستم های REAL TIME

خلاصه : در سالهای اخیر ، یک درخواست برای سیستم‌های REAL_TIME که می‌‌تواند حجم گسترده‌‌‌ای از داده‌‌های به اشتراک گذاشته شده را دستکاری کند ، به یک امر حتمی و لازم در سیستم‌‌های REAL_TIME Data BASE RTDBS به عنوان یک زمینه تحقیقی تبدیل شده است . این مقاله بر روی مسئله زمان‌بندی QUERY ها در RTDBS ها متمرکز شده است .

ما الگوریتم جدیدی به نام Priority Adaptation Query Reource Scheduling PAQRS برای اداره کردن کارهای Multi Class Query و Single Class Query را معرفی و ارزیابی می‌کنیم . هدف عمده الگوریتم به حداقل رساندن تعداد Deadline های از دست داده شده است و در عین حال اطمینان پیدا کردن از اینکه dead line های از دست داده شده در بین کلاسهای متفاوت مربوط به یک توزیع اجرایی از دست دادن پخش شده باشد . این منظور با تعدیل پویای پذیرش ورودی ، تخصیص حافظه و سیاست‌های اعمال اولویت بر طبق پیکربندی منبع معنی آن و خصوصیات کلی کار بدس

ت می‌آید . یک سری از آزمایشات نشان داده‌اند که PAQRS برای زمان‌بندی Query های Real _Time بسیار مؤثر هستند .
معرفی : در تعدادی از Data Base application های پدیداری شامل ـ کنترل پرواز ، مدیریت شبکه و اتوماسیون کارخانه ـ باید تعداد زیادی از داده‌های به اشتراک گذاشته شده به یک روش به هنگام دستکاری شوند . به صورت مخصوص‌‌ تری ،‌این application ها ممکن است که transaction ها و Query هایی تولید کنند که باید تا Dead line های مشخصی انجام شوند تا نتایج کاملی ( یا اصلاً نتیجه‌ای ) را در برداشته باشند . نیاز به سیستم‌هایی که می‌توانند از چنین مدیریت‌های زمانی میزان اصلی داده‌ها ،‌ پشتیبانی کنند ،‌توجه محققین را به سمت زمینه سیستم‌های Real _ Time Data buse RTDBS در هر دو زمینه اجتماعات محاسبه‌ای Real _ Time و Data base ای کشانده است . امروزه بیشتر کار در زمینه RTDBS بر روی موارد مدیریت Tran ssaction و زمان‌بندی منابع سطح پایین CPU , I/O متمرکز شده است .
بسته به اینکه چگونه application های یک سیستم Real _Time Data base می‌توانند فشار زمانی اشان را تحمل کنند به عنوان یک سیستم Hard ، Soft یا Firm شناخته می‌شوند . در این مطالعه ، ما بر روی Firm RTDBS ها تمرکز می‌کنیم که در آن Job ای که از زمان dead line اش بگذرد به

عنوان یک Job بدون استفاده ( غیرمفید ) در نظر گرفته می‌شود . برای رویارویی با فشارهای زمانی Job هایش ، یک Firm RTDBS باید Mulit Program باشند ، بنابر این تمامی منابع آن می‌تواند به صورت پرباری مورد استفاده قرار بگیرد . به علاوه ، باید زمان تکمیل Job های منفرد که تنظیم کند ؛‌ برای این کار باید از زمان‌بندی الویت‌بندی برای رفع هرگونه درگیری منبعی Multi Programming باعث آن می‌شود استفاده کند . در Firm RTDBS هنگامی که فضای کاری آن شامل Job هایی است که از کلاسهای متفاوتی نشأت گرفته‌اند رسیدن به هدف اصلی آن سخت‌تر می‌شود . برا

ی چنین فضاهای کاری ، RTDBS باید مواردی مانند چگونگی توزیع از دست دادن Dead line ها در بین کلاسهای مختلف را هم اداره کند . چون توزیع مطلوب از دست دادنهای Dead line از یک محیط به محیط دیگر ممکن است فرق داشته باشد ، RTDBS باید بتواند سیاست‌های زمان‌بندی منبع‌هایش را بر مبنای توزیع اعمال شده توسط System Administer سازگار کند . بنابر این هدف یک RTDBS با یک فضای کاری چند کلاسه multi class باید به حداقل رساندن کل تعداد موارد از دست رفتن Dead line ها باشد و هر از دست رفتنی باید با توجه به تنظیمات Administer بین کلاسها توزیع شود .
( A) Real_Time Query Processing
بازده Query ها می‌تواند بسته به میزان حافظه‌ای که برای کار به آنها داده شده است بسیار متفاوت باشد . هنگامی که حافظه کافی در اختیار Query ها قرار می‌گیرد ،‌اکثر آنها می‌توانند به آسانی یکباره Operand Relation هایشان را بخوانند و نتایج لازم را به صورت مستقیم تولید کنند . این مقدار به عنوان حداکثر حافظه مورد نیاز Query در نظر گرفته می‌شود . اگر حافظه کمتری به آنها اختصاص داده شود ، تا زمانیکه این مقدار بیشتر از حداقل حافظه مورد نیاز Query باشد ، باز هم اکثر Query ها می‌توانند با بیرون نوشتن فایلهای Temporary و خواندن دوباره آنها در Process های بعدی اجر شوند . برای مثال ، یک Hash Join هم می‌تواند با داشتن حداکثر حافظه مورد نیاز برای Query اش اجرا شود که یکی بزرگتر از اندازه Inner Relation اش است و هم می‌تواند فقط در یک عبور اضافی با تعداد Buffer Page هایی به کمی ریشه دوم اندازه inner Relation اش کار کند . برای کمک به اینکه تمامی کلاسهای Query بتوانند به سطح بازدهی موردنظرشان برسند ، یک RTDBS حتماً باید به تعدادی از Query ها کمتر از حداکثر حافظه موردنیازشان تخصیص دهد به ویژه هنگامی که مقدار حافظه موردنیازشان بزرگ است . در هر حال ، اگر تعداد زیادی Query پذیرفته شود ، I/o اضافی که در نتیجه آن ایجاد می‌شود باعث Thrashing می‌شود و به جای کمک بودن برای هم روندی ایجاد اشکال می‌کند . بنابر این RTDBS ها باید به دقت پذیرفتن Query به سیستم را کنترل کنند .
بعد از مشخص شدن اینکه کدام Query ها باید پذیرفته شوند مسئله‌بعدی که RTDBS با آن رو برو سست تخصیص حافظه است . هنگامیکه با اولویت‌ترین Query ایی که Cpu یا Disk را در اختیار دارد ، از آن منبع به صورت کاملاً انحصاری استفاده می‌کند ،‌ ولی حافظه باید بین تمام Query های

پذیرفته شده به اشتراک گذاشته شود . هنگامیکه حداکثر حافظه موردنیاز کل Query های پذیرفته شده از حافظه قابل دسترسی بیشتر باشد ، RTDBS باید در مورد میزان حافظه‌ای که باید بر هر Query بدهد تصمیم‌گیری کند . در این تصمیم‌گیری هم بازده موردنیاز کلاسها و هم فشار محدودیت

زمانی هر Query در نظر گرفته شود . به علاوه ، تأثیر تخصیص حافظه در کاهش زمان پاسخگویی Query های منفرد هم باید در نظر گرفته شود اینکه بهترین استفاده از حافظه در دسترس بشود . در آخر ، چون اولویت نسبی تا یک Query در حال اجرا ممکن است با گذشت زمان به علت آمدن و رفتن Query های دیگر به سیستم تغییر کند ، تخصیص حافظه به یک Query احتمالاً نوسان و بالا

و پایین خواهد داشت . برای ساده کردن پردازش َquery مؤثر در رویارویی با چنین نوسان حافظه‌ای ، RTDBS ها نیازمندquery operator هایی هستند که بصورت دینامیکدر حال اجرا هم بتوانند حافظه آزاد کنند و هم حافظه بیشتری را بپذیرند . تا این تاریخ ، کنترل ورودی و تخصیص حافظه

مسائلی هستند که در زمان‌بندی Real _Time Query آدرس دهی نشده‌اند .
Our Foues ( B )
این مقاله بر روی مشکل Query های زمان‌بندی در سیستم‌های Real _ Time Data base متمرکز است . در اینجا الگوریتمی به نام

Priority Adaptation Query Reacurce Sche duling ( PAQRS ) معرفی و ارزیابی می‌کنیم که هم برای محیط‌های کاری Query تک کلاسه و هم برای محیط کاری Query های چند کلاسه طراحی شده است . این الگوریتم مکانیزمی برای پذیرفتن دینامیک کنترل ورودی و تصمیمات تخصیص حافظه یک RTDBS با توجه به خصوصیات محیط کاری و پیکربندی منبع سیستم ارائه می‌کند .

به علاوه PAQRS یک مکانیزم کنترل اریب ( bias ) حساس به کلاس مجهز است . هنگامیکه یک فضای کاری چند کلاسه سنگین وجود دارد ، این مکانیزم کنترل صریحی که بر روی اولویت نسبی کلاسهای منفرد اعمال می‌کند .
Related Work (2)
بدنه اصلی کار در فضای سیستم Real _ Time Data base وجود دارد ولی کل این کار بر روی مسائل و الگوریتم‌هایی در رابطه با زمان‌بندی Real _ Time Tran saction یا زمان‌بندی Real _ Time Disk متمرکز شده است . با توجه به حداکثر دانش ما ، مشکل Query های زمان‌بندی در یک RTDBS تا این تاریخ بر طرف نشده است . در نتیجه ، تنها مطالعاتی که به این کار نزدیک هستند دو مطالعه‌ایست که زمان‌بندی منبع برای محیط‌های کاری Query های چند کلاسه را در متن سیستم‌های Data base قدیمی غیر real – time بررسی کرده ‌اند .
مفاهیم مصرف حافظه و بازگشت به مصرف roc به عنوان مبنایی برای مدیریت حافظه در یک محیط Multi Query معرفی شده‌اند با استفاده از این مفاهیم برای مشخص کردن اثر تخصیص حافظه د

ر زمان پاسخگویی Query ، یک الگوریتم Hearistrc برای تخصیص حافظه بین Query هایی که به صورت هم روند در حال اجرا هستند پیشنهاد شد به روشی که یک سطح خارجی از Roc را تضمین کند . نتیجه مهم این تحقیق این است که دادن حداکثر حافظه موردنیاز به بعضی از Query ها در حالیکه به بقیه Query ها حداقل حافظه موردنیاز شان داده شده است ، استفاده از حافظه که تقریباً بهینه می‌کند . این نتیجه به صورت مستقیم با استراتژی‌های تخصیص حافظه در PAQRS در ارتباط است .
در یک مطالعه‌ای ، Brown et al مشکل تنظیم اتومکانیک سطح‌های Multi Proyramming mpl و

تخصیص حافظه‌های یک سیستم مدیریت Data base برای دستیابی به اهداف پاسخ زمانی هر کلاس در محیط‌های چند کلاسه بررسی کرد . الگوریتمی به نام M & M برای پیدا کردن MPL و تنظیمات حافظه هر کلاس معرفی شد ؛ که این تنظیمات به صورت دینامیک توسط یک مکانیزم Fead back که از یکسری تکنیک‌های Heu Ristic و تخمینی نشأت گرفته مشخص شده‌اند . نتایج شبیه‌سازی نشان داد که M & M می‌تواند به صورت موفقی به زمانهای پاسخی که در درصد کمی از اهداف وجود دارند برسد . بجز تعهد آن ، M & M نمی‌تواند به صورت مستقیم در RTDBS Content استفاده شود . این بدان علت است که M & M اولویتی در نظر نمی‌گیرد .و ممکن است MPL و تنظیمات حافظه‌ای vh انتخاب کند که با اولویت‌های Job ها که برای کنترل هم روندی و زمان‌بندی Cpu و Disk تداخل داشته باشد . بنابر این یک راه‌حل کامل که هم نسبت‌دهی اولویت که هم و هم کنترل Mpl و تخصیص حافظه را داشته باشد باید پیدا کرد .
Basic Real time Scheduling (3)
در یک سیستم Firm Real _ Time Data base ،‌ Query که از زمان Dead line آن بگذرد بی‌مصرف قلم داد می‌شود . هدف اصلی اولیه یک RTDBS ،‌ در صورت امکان ،‌ ملاقات با تمامی Query Dead line هاست . اگر این مسئله امکان نداشته باشد و اگر تمام Query ها از اهمیت یکسانی برخوردار باشند ،‌آنگاه RTDBS سعی خواهد کرد که تعداد Dead line های از دست داده شده که به حداقل برساند . در شکل ۲۲ ،‌یک الگوریتم زمان‌بندی Query بر مبنای هدف بازدهی آن معرفی شده است . این الگوریتم ( PMM ) مدیریت اولویت‌بندی حافظه نامیده می‌شود که استفاده از حافظه‌ که برای محیط‌های Firm Real _ Time Query تنظیم می‌کند . چون PAQRS از روی این الگوریتم ساخته شده است ، PMM را در این بخش به صورت کامل معرفی می‌کنیم .

الگوریتم PMM از یک جزء کنترل ورودی و یک جزء تخصیص حافظه تشکیل شده است . هر دوی این اجزاء از روش زمان‌بندی ED Earliest deadline استفاده می‌کنند ،‌بنابر این به Query هایی که عجله‌ای‌تر باشند در ورود به سیستم و تصمیمات تخصیص حافظه اولویت بیشتری نسبت به Query هایی که Dead line دورتری دارند خواهند داشت . جزء کنترل ورودی PMM هدف سطح Multi

Proyramming mpl که با استفاده از انعکاس آماریی از نسبت‌های از دست‌دهی قبلی و مقادیر MPL های در رابطه با آنها تنظیم می‌کند . در شرایطی که این روش ناموفق باشد ، PMM به روش Heuristic ای برمی‌گردد که MPL که بر مبنای سطح‌های مصرف منابع مطلوبشان انتخاب می‌کند .
جزء تخصیص حافظه از یکی از دو استراتژی زیر استفاده کند :
۱ ـ استراتژی Max که به هر Query حداکثر حافظه موردنیازش را می‌دهد و یا اصلاً حافظه‌ای به آن نمی‌دهد .
۲ ـ استراتژی Min Max که به بعضی از Query هایی که اولویت پایینی دارند اجازه می‌دهد تا با حداقل میزان حافظه موردنیازشان اجرا شوند در حالیکه Query هایی که اولویت بالای دارند حداکثر حافظه‌ای که نیاز دارند که در اختیار می‌گیرند .
انتخاب فعلی استراتژی تخصیص حافظه به آماری درباره خصوصیات فضای کاری که PMM جمع‌آوری می‌کند بستگی دارد . به علت اینکه هم تنظیمات MPL و هم انتخاب استراتژی تخصیص حافظه باید با خصوصیات فضای کاری سازگاری داشته باشند ، PMM پیوسته تغییرات فضای کاری را که ممکن است مستلزم تعدیل تصمیمات آن باشد را کنترل می‌کند . جزئیات الگوریتم در زیر ارائه شده است .
پارامترهای کلیدی PMM که در جدول I به اختصار آمده‌اند .
Admission Control (A)
کار مکانیزم کنترل ورودی مشخص کردن MPL بر مبنای شرایط اجرایی فعلی است . برای به حداقل رساندن Miss ratoi ( نسبت از دست دهی ) که به عنوان بخشی از Query هایی که به خاطر گذشتن از مرز Dead line شان ناموفق بوده‌اند تعریف می‌شود ، MPL باید به اندازه کافی بالا ب

اشد تا منابع Dick و Cpu بتوانند به صورت کامل مورد بهره‌برداری قرار بگیرند . در هر صورت ، MPL نباید آنقدر هم بالا باشد که باعث Thrashing شود . بنابر این ارتباط بین MPL و Miss ratio به شکل یک منحنی مقعر خواهد بود . PMM سعی می‌کند تا MPL بهینه را قرار دهد ، یعنی MPL ای که باعث حداقل Miss ratios در این منحنی در یک ترکیب Miss ratio Projection و یک Resource

Utilization heuristic بشود که تنظیمات MPL اش را بعد از هر Sample Size Query ای که توسط سیستم سرویس‌دهی می‌شود ،‌اصلاح می‌کند. دو جزء روش تعیین MPL در زیر ارائه شده‌اند :
Miss Ratio Projection A –۱
روش Miss Ratios Projectionارتباط بین MPL و Miss Ratio را توسط یک معادله درجه دوم منحنی تخمین می‌زند ، این معادله برای تنظیم هدف MPL سیستم استفاده می‌شود . یک معادله درجه دوم در اینجا استفاده می‌شود زیرا نسبت معادلات درجه بالاتر هنگام تسخیر شکل کلی منحنی معقر سریعتر به حالت تثبیت می‌رسد . بعد از تکمیل هر Sample Size Query ، PMM
Miss Ratio miss i را که MPL فعلی MPL iتولید می‌کند را اندازه‌گیری می‌کند. بسته به این مقادیر ، به همراه Miss Ratio های قبلی و تنظیمات MPL مربوط به آنها ، یک معادله درجه دوم جدید در رابطه با روش حداقل مربعات محاسبه می‌شود . قابل توجه است که احتیاجی نیست که PMM خواندن Miss Ratio های تک را دنبال کند و فقط باید مقادیر را دنبال کند که K تعداد دفعاتی است که PMM احضار شده است . بنابر این فضای سربار دیده شده توسط روش انعکاسی خیلی پایین است سربار محاسبه‌ای هم حداقل است زیرا این روش فقط نیازمند این است که جمع‌های بالا بعد از هر تکمیل Query به روز شوند و مشتق‌گیری از معادله درجه دوم هم فقط مستلزم محاسبات ساده‌ای شامل این جمع‌ها ـ است .
بعد از تخمین معادله ، یک مقدار MPL جدید در رابطه با نوع منحنی بدست آمده انتخاب می‌شود .
Type 1 . منحنی به شکل یک کاسه است : در این وضعیت ، منحنی یک مقدار Minimum دارد . بنابر این MPL برابر با حداقل منحنی می‌شود . (‌این وضعیتی است که بعد از اجرای الگوریتم برای یک مدت زمانی انتظار می‌رود) .
Type 2 . منحنی نزولی یکنواخت است : یعنی MPL های بالاتر باعث Miss Ratio های پایین‌تر می‌شوند . این نشان می‌دهد که MPL بهینه بالاتر از بیشترین MPL ای است که تا به حال در نظر گرفته شده است . چون منحنی ممکن است که در صورت دور بودن تخمین معتبر نباشد ، روش انعکاسی یک MPL ای را انتخاب می‌کند که یکی بالاتر از این MPL های بکار رفته وسیع باشد . سپس ،‌Resource Utilizing Heuristic , PMM را اعمال می‌‌کند تا ببیند آیا MPL بالاتری ممکن است وجود داشته باشد یا نه ، اگر وجود دارد ، MPL توسط Heuristic پیشنهاد می‌شود ، در غیر این صورت PMM ،MPL ای که توسط روش Miss Ratio انتخاب شده است را حفظ می‌کند .
Type 3 . منحنی صعودی یکنواخت است : پروسه محاسبه‌MPL برای این وضعیت درست برخلاف روحیه منحنی Type 2 است . در اینجا روش انعکاسی به صورت آزمایشی یک MPL ای انتخاب می‌کند که یک واحد در زیر کوچکترین MPL ای است که تا به حال بکار رفته است . سپس ، MPL دومی با استفاده از Resource Utilizing Heuridtic بدست می‌آید . دو MPL با هم مقایسه می‌شوند و کوچکترین مقدار انتخاب می‌شود .
Type 4 . منحنی به شکل تپه است : گه گاهی منحنی ثابت شده در این شکل در نتیجه Miss Ratios های تصادفی بدست آمده توسط بالا و پایین‌های ذاتی فضای کاری بوجود می‌آید . وقتی این اتفاق می‌افتد ،‌روش انعکاسی ناموفق است و PMM به Resource Utilizing Heuristic متوسل

می‌شود .
یک ویژگی جالب روش انعکاسی Miss Ratio این است که مقادیر MPL ای که این روش انتخاب می‌کند با گذشت زمان بهبود می‌یابد : در ابتدا ،‌شکل منحنی به صورت گسترده‌ای تحت تأثیر نوسانات تصادفی فضای کاری است . با گذشت زمان و بدست آمدن Miss Ratios های بیشتر ؛ منحنی به تدریج تثبیت می‌شود و مقدار مطلوب آن به MPL بهینیه نزدیک خواهد شد . در این ن

قطه ، می‌توان از سیستم انتظار داشت که بازده خوبی را تا زمانی که تغییرات عمده‌ای در خصوصیات فضای کاری به وجود نیامده ارائه کند .
Resource Utilizing Heuristic A –۲
Resource Utilizing ( RU ) Heuristic تلاش می‌کند تا به سیستم در رسیدن Miss Ratio ها پایین‌تری کمک کند و این کار را با بهره‌گیری مدام از بیشترین منبع Load شده در بین Cpu ها و Dick ها در یک دامنه مطلوب انجام می‌دهد بنابر این از موقعیت‌هایی که منبع گلوگاهی تحت مصرف یا نزدیک به اشباع باشد جلوگیری می‌کند . Heuristic از MPL جاری و میزان مصرف برای پیش‌بینی یک MPL جدید استفاده می‌کند که احتمالاً با بکار بردن فرمول زیر میزان مصرف را به وسط محدوده می‌برد :
فرمول
وابستگی خطی بین MPL و میزان مصرف که این فرمول فرض کرده است ،‌بر مبنای مشاهده‌ای است که میزان مصرف یک منبع تقریباً به صورت خطی تا زمانیکه منبع نزدیک به اشباع باشد همراه با MPL افزایش می‌یابد که هنگامیکه منبع نزدیک اشباع است نقطه‌ای است که سطح مصرف به صفر می‌رسد چون هیچکدام از روشهای Miss Ratios Projection Ru Heustric میزان روش را به سمت بالای حد که نقطه اشباع است نمی‌برند ، فرمول بالا باید تخمین‌های MPL صحیحی را در اکثر مواقع انجام دهد . حتی در جاهایی که فرض وابستگی خطی در نظر گرفته نمی‌شود ، روش Ru Heustric باز هم در جهت تنظیم MPL در مسیری به سمت MPL بهینیه مفید است زیرا میزان مصرف به صورت یکنواخت همراه با MPL تغییر می‌کند .
همانطور که توضیح داده شد ،‌مقداری که Ru Heustric برای محاسبه MPL جدید استفاده می‌کند ، میزان مصرف سنگین‌ترین منبع Load شده در MPL جاری است . با توجه به نوسانات تصادفی فضای کار ، میزان مصرف بعد از مدت دسته Sample Size Query های فعلی نشان‌دهنده میانگین میزان مصرف سراسری در آن MPL نیست . به این علت ،‌در واقع Heustric مقادیر میزان مصرفی که تا به حال بدست آمده‌اند را میانگین‌گیری می‌کند . به جای اینکه تنها به خواندن آخرین مقدار میزان مصرف بسنده کند . PMM میـانگین میزان مصرف در MPL جـــــــــــــــــــاری که بر در فرمول بالا دلالت می‌کند ، را توسط اولین خط راست بدست آمده از هر جفت از مقادیر میزان مصرف بررسی شده و MPL های مربوط به آن را با استفاده از روش حداقل مربعات محاسبه می‌کند که در اینجا هم باز از فرض خطی بودن استفاده می‌شود . میــــــــــــانگین میـــــــــــزان مصرف سپس از خط منــــاسب به عنوان پایه‌ای که مطابق با MPL جاری است گرفته می‌شود . بــــــــــــه منظور

محــــــــــــاسبه خط راست ، PMM مقادیر را که K تعداد دفعاتی که PMM صدا زده شده است را نشان می‌دهد ،‌ثبت می‌کند . همانطور که قبلاً بحث شد ، Overheadهای محاسبه‌ای و فضایی که در این روش وجود دارد حداقل هستند .
Memory Allocatoin – B
همانطور که در بالا توضیح داده شد ،‌ Query هایی مانند Hash Join ها و Externul Sort ها یک مقدار نیاز حداکثر و حداقل به حافظه دارند . با دادن حداکثر حافظه موردنیازشان ، چنین عملیلاتی

می‌تواند Operand Relation هایش را بخواند و مستقیماً نتیجه را تولید کند . اگر فقط حداقل حافظه موردنیازش به آن داده شود که عملاً خیلی کمتر از میزان حداکثر آن است ، این عملیات باید Operand Relation هایش را پردازش کند ، نتایج میانی را در جایی خارجی در فایلهای کمکی بنویسد ،‌و سپس این فایلها را دوباره پردازش‌های قبلی ،‌قبل از اینکه نتیجه آخر تولید شود ، بخواند . حداکثر حافظه موردنیاز یک Externul Sort به اندازه Operand Relation اش است ،‌ در حالیکه می‌تواند با مقداری به کمی سه صفحه حافظه با استفاده از Merge Pass های چندگانه اجرا شود .
برای یک Haoh Join ،‌حداکثر حافظه موردنیاز و حداقل حافظه درخواستی آن ( برای عملیاتtwo-pass ای ) F(®) , F(®)هستند که (®) اندازه Relation داخلی ( ساختمان ) و F یک فاکتور سرهم‌بندی است که سر باریک Hash Table را منعکس می‌کند .
وقتی که حداکثر حافظه موردنیاز کلی Query های داخل شده از حافظه در دسترس بیشتر باشد ، جزء تخصیص حافظه موظف است که مقدار حافظه‌ای که باید به هر Query داده شود را مشخص کند . همانطور که قبلاً اشاره شد ،‌تصمیمات تخصیص حافظه بر مبنای سیاست ED انجام می‌گیرد ، بنابر این به Query هایی که اورژانسی‌تر هستند همیشه Buffer هایی بالاتر از Query هایی با Dead line های دورتری دارند داده می‌شود . در هر زمان ، PMM یکی از دو استراتژی تخصیص حافظه را قبول می‌کند : استراتژی Max یا سیاست Min Max . در روش Max ، Query یا Max نیازشان به حافظه را در اختیار می‌گیرند یا اصلاً بافری نخواهند داشت . برای اجرا در روش Min Max ، PMM می‌تواند Query های بیشتری را بپذیرد و فقط به Query هایی که عجله بیشتری دارند ماکزیمم مقدار حافظه‌ موردنیازشان را بدهد و به بقیه اجازه دهد که با در دست داشتن حداقل حافظه موردنیازشان اجرا شوند . علت انجام تخصیص حافظه از نوع Min Max که حافظه در دسترس را بین Query های پذیرفته شده به تناسب تقسیم می‌کند این است باعث استفاده بهینه‌تری از حافظه نسبت به تخصیص نسبی می‌شود . یک مسئله ممکن درباره Min Max این است که ممکن است Query های زیادی را برای اجرا با حداقل حافظه موردنظرشان بپذیرد و در نتیجه Disk ها Over Load شوند . به هر حال ،‌این وضعیت همراه با الگوریتم PAQRS به وجود نخواهد آمد زیرا تعداد Query هایی که واجد شرایط تخصیص حافظه هستند توسط جزء کنترل ورودی PAQRS تنظیم

می‌شوند .
پروسه تخصیص Min Max در دو Pass انجام می‌شود . از Query هایی که اولویت بیشتری دارند شروع می‌شود ، PMM در ابتدا به هر Query فقط یک مقدار حافظه می‌دهد تا بتوانند اجرا شوند . اگر در انتهای این گذر ، Buffer هایی باقی بمانند ، PMM گذر دیگری را در بین لیست Query های پذیرفته شده شروع می‌کند و دوباره از با اولویت‌ترین Query شروع می‌کند . در گذر دوم ،‌به نوبت مقداری به هر Query داده می‌شود که به حداکثر نیازش به حافظه دسترسی پیدا کند . پروسه تخصیص هنگامیکه تمام حافظه در دسترس به Query ها اختصاص داده شود یا تمام Query ها به حداکثر مقدار حافظه موردنیازشان دست پیدا کنند تمام می‌شود . در آخر این پروسه تخصیص حافظه اتفاقی که ممکن است بیفتد این است که بعضی از Query های با اولویت بالا حداکثر حافظه موردنیازشان را در اختیار بگیرند در صورتی که Query های با اولویت کمتر به علت کمبود حافظه suspend شوند . اتفاق دیگر این است که Query های با اولویت بالا حداکثر حافظه موردنیازشان را داشته باشند در حالیکه Query های با اولویت‌ پایین فقط حداقل موردنیازشان را داشته باشند . تنها استثناء ممکن این است که Query ایکه آخرین صفحات حافظه در گذر دوم را در اختیار می‌گیرد ، ممکن است مقدار حافظه‌ای بین حداقل و حداکثر درخواستش را داشته باشد . در یک سیستم در حال اجرا ، Query ها همه‌شان یک دفعه وارد نمی‌شود ، بلکه با گذشت زمان می‌آیند و می‌روند . چون سیاست ED به Query ها در رابطه با عجله‌ای بودن یا نبودنشان اولویت می‌دهد ،‌بنابر این تخصیص حافظه یک Query می‌تواند بین Min تا Max آن خیلی متفاوت باشد یا اصلاً به آن حافظه‌ای داده نشود چون Query های با اولویت‌ بالا به سیستم وارد و خارج می‌شوند ، ولی با گذشت زمان به آن حداکثر حافظه موردنیازش داده می‌شود زیرا به زمان Dead Line اش نزدیک می‌شود . برای مقابله با چنین نوساناتی در تخصیص حافظه Query ها ، PMM باید به عملکردهای پردازش پذیرفتن Query مثل Adaptive Join ، Sort ها برای تنظیم میزان مصرف حافظه Query به صورت دینامیک اتکا کند .
استراتژی Max ، با اصرار به تخصیص حداکثر نیاز حافظه ،‌مشکل بالقوه Thrashing که می‌تواند هنگامیکه Query های با اولویت پایین اضافی که برای اجرا به حافظه‌ای کمتر از حداکثر نیازشان احتیاج دارند وارد سیستم شوند ، بوجود آید را حذف می‌کند . در نتیجه ،‌PMM نیازی به محدود کردن صریح MPL در روش Max ندارد . در عوض ، PMM تا جائیکه حافظه در دسترس اجازه بدهد ، Query با اولویت بالا همراه با تخصیص حداکثر حافظهْ موردنیازشان را می‌پذیرد . یک تله ممکن Max این است که ممکن است هنگامیکه تله ‌ Query ها برای اجرا با حداکثر حافظه موردنیازش احتیاج به یک بخش اصلی حافظه سیستم داشته باشند ، MPL ها را شدید و محدود کند . در مقابل Max ، Min Max به تمام یا بعضی از Query های پذیرفته شده ،‌حداقل حافظه درخواستی‌شان را نسبت

می‌دهد که در نتیجه به سیستم امکان می‌دهد که به هدف MPL که جز و کنترل ورودی تنظیم می‌کند برسد . بسته به خصوصیات فضای کاری و پیکربندی سیستم یکی از دو روش Max و Min Max ممکن است بازده بهتری داشته باشد اگر حافظه بسیار زیاد باشد و نوع منبع گلوگاهی Cpu یا Disk باشد ، Max ترجیح داده می‌شود ، در حالیکه برای شرایطی که حافظه محدود است Min Max مفیدتر است .
الگوریتم PMM از یک مکانیزم Fead back برای ثبت وضعیت سیستم استفاده می‌کند ، که انتخاب استراتژی تخصیص را در صورت نیاز اصلاح می‌کند . در ابتدا ، روش Max انتخاب می‌شود . بعد از

سرویس‌دهی به تمامی Sample Size Query ها ، PMM وضعیت سیستم را چک می‌کند و اگر تمام شرایط زیر برقرار باشد برروی روش Min Max سوئیچ می‌کند :
۱ ـ یک یا چند Query در این دسته Dead line هایشان را از دست داده باشند.
۲ ـ میزان مصرف تمام Cpu ها و Disk ها پایین‌تر از است که نشان می‌دهد هیچیک از این منابع در کل گلوگاهی نیستند .
۳ ـ یک زمان انتظار پذیرفته شدن غیرصفر وجود دارد که پیشنهاد می‌کند که رقابت بر سر حافظه وجود دارد .
۴ ـ به صورت متوسط ،‌زمان اجرای یک Query کوتاه‌تراز امحدودیت زمانی آن است (‌زمان اجرا = تفاضل بین Dead line و زمان و روش ) بنابر این زمانهای اجرای طولانی‌تری که در نتیجه سوئیچ کردن روی استراتژی Min Max نتیجه خواهــند شــــد عملی است . در چک کردن برای شرط۳ ، PMM یک تست بــــزرگ نمونه را به منظور بدست آوردن زمـان انتظار در یک سطح اطمینان اجرا می‌کند . شرط ۴ به یک روش مشابه تست می‌شود ، به استثنای اینکه در اینجا آزمایش بر روی تفاوت بین زمان اجرا و محدودیت زمانی اعمال می‌شود . بعد از سوئیچ کردن روی Min Max ، PMM سپس MPL هدف را ثبت می‌کند . اگر MPL پایین‌‌تر از MPL میانگینی باشد که از روش Max بدست آمده ، PMM به روش Max باز می‌گردد . عمل این پروسه مدام تکرار می‌شود .
Dealing with Workload Charges – C
PMM تلاش می‌کند تا Query Miss Ratio را با تطبیق MPL و تنظیمات حافظه‌اش با فضای کاری سیستم و پیکربندی منبع به حداقل برساند . در نتیجه ، PMM باید هنگامیکه فضای کار ـ تحت یک تغییر اساسی است آمارهایی را که جمع‌آوری کرده است را دور بریزد و دوباره خودش را سازگار کند . برای تشخیص تغییرات فضای کاری ، PMM به صورت ثابت خصوصیات فضای کاری زیر را بررسی و ثبت می‌کند :
۱ ـ میانگین حداکثر حافظه موردنیاز Query ها .
۲ ـ میانگین تعداد I/O هایی که هر Query برای خواندن Operand Relation هایش اجرا می‌کند .
۳ ـ میانگین محدودیت زمانی نرمال شده که به عنوان نسبت محدودیت زمانی به تعداد I/O های لازم برای خواندن Operand Relation ها مورد نیاز است ، تعریف شده است . بعد از تکمیل هر Sample Size query ، PMM یک تست نمونــــــــــه‌ای بزرگ را در یک سطح اطمینـــــــــان از برروی هر یک از خصوصیات فضای کاری ثبت شده انجام می‌دهد تا ببیند که آیا مقدار فعلی از مقدار

ارزیابی شده آخر تفاوت عمده‌ای دارد یا نه . اگر چنین باشد ، PMM نتیجه می‌گیرد که یک تغییر در فضای کاری در حال اجراست . چون هر تغییر فضای کاری باعث می‌شود تا PMM خودش را Restart کند . روی بالاترین مقدار تنظیم می‌شود تا تغییرات اشتباه PMM بر اثر نوسانات ذاتی فضای کاری را کاهش دهد .
-D یک مثال : فرض کنید که اولین دسته Sample Size query ها نقطه‌ a در شکل a ـ ۱ را تحت استراتژی Max تولید کرده‌اند ، و فرض کنید که PMM نتیجه‌گیری کرده است که روش Max مناسب نیست و تصمیم به سوئیچ کردن روی Min Max را گرفته است . در اینجا ،‌ Heuristrie RU ، MPL بالاتری نسبت به آنچه که ما از نقطه b بعد از تکمیل دسته بعدی Query ها بدست آورده‌ایم پیشنهاد می‌کند . به علاوه RU Heuristrie باعث می‌شود تا PMM تنظیمات MPL اش را بالا ببرد که نتیجه آن نقطه c بعد از سومین دسته Query هاست . با جمع‌آوری سه ارزیابی ،‌PMM می‌تواند روش انعکاسی Miss Ratio را اعمال کند . معادله درجه دومی را از آن سر نقطه محاسبه شده است . در منحنی Type 2 در شکل a – 1 نشان داده شده است . این منحنی باعث می‌شود تا PMM ،‌ حتی MPL بالاتری را به کار ببرد ، نتیجه‌ای که با نقطه d در شکل b ـ ۱ نشان داده شده است . با به کار بردن دوباره روش انعکاسی ، PMM حالا یک منحنی Type _1 بدست میآورد . چون بهینه منحنی تقریباً به نقطه مطلوب نزدیک است ، PMM مقدار MPL مربوط به این نقطه‌بهینه را برای MPL بعدی‌اش می‌پذیرد . با پیش رفتن این پروسه و جمع‌آوری بازبینی‌های بیشتر ، منحنی به تدریج به ثبات می‌رسد و PMM را به سمت بهترین MPL برای فضای کاری داده شده می‌برد .
( شکل a ـ ۱ و b ـ ۱ )
۴- Multi Class Real _Time Query Scheduling
همانطور که قبلاً گفته شد ، ممکن است در بعضی محیط‌ها لازم باشد تا Dead line های از دست رفته به صورت متناسب بین کلاسهای Query در رابطه با اهداف فضای کاری تعریف شده توسط Administer ، توزیع شود .
برای آدرس‌دهی نیازهای چنین بازده کنترل شده‌ای ،‌این بخش PAQRS را که الگوریتمی برای زمان‌بندی فضاهای کاری Multi Class Firm Real _ Time Query است معرفی می‌کنیم . در چنین فضای کاری ، PAQRS به یک Administer سیستم اجازه می‌دهد تا لیستی از مقادیر زیر را که توزیع Real _Time دلخواه در بین کلاسهای فضای کاری را نشان می‌دهد ، مشخص کند :
Rel Miss Ratio = { Rel Miss Ratio 1 : .… : Rel Miss Ratio Numclasses }
بـــــــــــرای مثـــال ،‌فرض کنید کــــــه فضای کاری از دو کلاس تشکیل شده است . اگر Rel Miss Ratio = { 3 : 1 } باشدآنگاه توزیع Miss Ratioی هدف به شکل Miss Ratio1 =3x% و Miss Ra

tio2 = 1x % برای هر x خواهد بود . هدف کارآیی PAQRS به حداقل رساندن تعداد Dead line های از دست رفته است و به تبع آن محدودیتی است که Miss Ratio ها باید بین کلاسهایی که توسط Administer سیستم مشخص شده‌اند توزیع شوند . کنترل سطح چند برنامگی ( MPL ) مربوط به الگوریتم PAQRS و مکانیزم‌های تخصیص حافظه‌ آن ارائه شده‌اند تا به PAQRS اجازه دهند تا بر روی نصف کلاسهایی که به کمک نیاز دارند مداخله کند تا هدف کارآیی برآورده شود .
جزئیات الگوریتم در زیر آمده است . متغیرها و پارامترهای داخلی در جدول ۲ خلاصه شده‌اند 
Ov erview of PAQRS Algorithm -A
مانند PMM ، PAQRS یک MPL سراسری سیستم و یک شمای تخصیص حافظه سراسری ( Max یا Min Max )‌را تنظیم می‌کند . برخلاف PMM ، که تنها برای به حداقل رساندن تعداد کلی Dead line های از دست رفته تلاش می‌کند ، PAQRS ، MPL و استراتژی تخصیص حافظه‌اش را بر مبنای یک اندازه‌گیری بازده حساس به کلاس انتخاب می‌کند . به علاوه ، محرکهای حساس به کلاسی استفاده می‌شوند تا مشخص کنند چه زمانی تغییرات فضای کاری ایجاب می‌کند که آن انتخابها دوباره محاسبه شوند . بنابر این PAQRS می‌تواند تصمیمات مربوط به تخصیص حافظه و کنترل ورودی را بگیرد ،‌یعنی مکانیزم کنترل bias برای کمک به تمام کلاسها برای رسیدن به سطح بازدهی موردنظرشان .
مکانیزم کنترل bias بازده کلاسهای منفرد را توسط تنظیم اولویت Query هاشان کنترل می‌کند . بدون در نظر گرفتن جزئیات ، PAQRS این تنظیمات را با استفاده از یک نسخه چند کلاسه از سیاست زمان‌بندی Adaptive Earliest Dead line نشان داده شده در شکل ۱۳ به انجام می‌رساند .
PAQRS تمام Query ها را به دو گروه اولویتی تقسیم می‌کند ـ یکی گروه Regular و دیگری گروه Reserve ـ و یک سهمیه از Regular Query ها برای هر کلاس از Query ها انتخاب می‌شود . مقادیر اولویت بر مبنای سیاست ED به Regular Query ها نسبت داده می‌شود ، در حالیکه به Reserve Query ها اولویت‌های تصادفی که پایین‌تر از اولویت‌های Regular Query هاست داده می‌شود . اگر میزان سهمیه Regular Query های هر کلاس بالا برده شود طبیعتاً Dead line هایی بیشتر از حد مطلوب از دست می‌روند و با محدود کردن تعداد Regular Query های هر کلاس که باعث از دست رفتن Dead line های کمتری می‌شود ،‌به PAQRS امکان می‌دهد که Dead line های از دست رفته را بین کلاسهای Query در راستای اهداف مشخص شده فضای کاری توزیع کند .
Admission Control & Memory Allocaton in PAQRS – B
همانطور که در بالا اشاره شد ، الگوریتم PAQRS ،‌ PMM را برای انتخاب یک MPL کلی برای سیستم و یک روش تخصیص حافظه سراسری که موجب رسیدن به هدف بازدهی چند کلاسه فضای کاری می‌شود وفق داده است . PAQRS این کار را مبنا قرار دادن میزان بازدهی کلی سیستم برای تصمیمات انتخاب MPL که بهتر توزیع Miss Ratio مطلوب را منعکس می‌کند و همچنین توسط انتخاب استراتژی تخصیص حافظه در رابطه با سطح رقابت حافظه انجام شده توسط کلاسها ، انجام می‌دهد .
مکانیزم اولیه‌ای که PAQRS برای تنظیمات MPL اش اتکا می‌کند ، یک روش انعکاسی آماری است که مقداری MPL ای را که باعث پایین‌ترین «میانگین» Miss Ratios می‌شود را پیش‌بینی می‌کند . بنابر این ما نیاز به رویه محاسبه « میانگین Miss Ratio » ای داریم که به درستی نفوذ موردنظر تک تک کلاسهـــــــــــا را منعکس کند . بــــــــرای درک مستقیم ، اگر ما بخواهیم Rel Miss Ratio j × Rel Miss Ratio i = C برای دو کلاس i و j داشته باشیم ،‌ Class i باید C بار بیشتر از نفوذ Class j در میانگین Miss Ratio به کار رود . این کار با اولین تغییر شکل مقادیر Rel Miss Ratio به وزن کلاسها بدست می‌آید :
فرمول

و سپس محاسبه یک Miss Ratios ی وزن دار برای روش انعکاسی از Miss Ratio ی کلاسهای منفرد و وزنهای مربوط به آنها :
Weighted Miss Ratios = Weight i X Miss Ratio i
برای این که نشان بدهیم که این الگوریتم چه جوری کار می‌کند ،‌بیایید دوباره یک فضای کاری دو کلاسه را با Rel Miss Ratio { 3 : 1 } را بررسی کنیم . با اعمال رویه بالا ،‌به دو کلاس وزنهای O.25 و O.75 نسبت داده می‌شود و کلاس ۲ سه برابر کلاس ۱ با نفوذتر خواهد بود . یک ویژگی مهم وزن کلاسها این است که جمع آنها ۱ می‌شود . این ویژگی اطمینان می‌دهد که جمع وزنهای Miss Ratio های کلاس ،‌که هر کدام در محدوه‌ای بین ۰ % تا ۱۰۰ % هستند ، در فاصله { ۰ % _ ۱۰۰ %} باقی می‌ماند .
بعد از تنظیم مکانیزم انتخاب MPL ، توجه‌مان را روی روشی که PAQRS استراتژی تخصیص حافظه‌اش را انتخاب می‌کند می‌بریم . برای تطبیق بهتر در یک متن چند کلاسه ، PAQRS باید اندازه‌گیری بازدهی کلی سیستم را که PMM با اندازه‌گیری‌های حساس به کلاس استفاده می‌کند جایگزین کند . PAQRS با استراتژی تخصیص Max شروع می‌کند و سپس اگر میزان مصرف تمام Cpu ها و Disk ها کمتر از Utillow باشد و بعضی از Class های I تمامی شرایط زیر را داشته باشند ، روی روش Min Max سوئیچ می‌کند :
۱ ـ یک یا چند Query از آن کلاس تا زمان آخرین فعالیت PAQRS ، Dead line هایشان را از دست داده‌اند .
۲ ـ کلاس I یک زمان انتظار پذیرفته شدن غیرصفر دارد .
۳ ـ بطور متوسط ،‌زمان اجرای یک Query متعلق به کلاس I خیلی کمتر از محدودیت زمانی آن ( که تفاضل بین Dead line و زمان ورود آن است ) است. به عبارت دیگر PAQRS در صورتی به روش Min Max سوئیچ می‌کند که بعضی از کلاسها بی‌جهت Dead line هایشان را از دست می‌دهند زیرا Query هایشان باید منتظر حافظه بمانند . چون تست بالا نیازمند آمارهایی بازدهی کل

کلاسهاست ، PAQRS فقط بعد از اینکه سیستم حداقل به Sample Size Query ها را از هر کلاس سرویس داد برای اصلاح انتخاب MPL و روش تخصیص حافظه‌اش صدا زده می‌شود .