سیستم های 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 و روش تخصيص حافظه‌اش صدا زده مي‌شود .