دانلود مقاله سیستم های 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 های از دست داده شده که به حداقل برساند . در شکل 22 ،‌یک الگوریتم زمان‌بندی Query بر مبنای هدف بازدهی آن معرفی شده است . این الگوریتم ( PMM ) مدیریت اولویت‌بندی حافظه نامیده می‌شود که استفاده از حافظه‌ که برای محیط‌های Firm Real _ Time Query تنظیم می‌کند . چون PAQRS از روی این الگوریتم ساخته شده است ، PMM را در این بخش به صورت کامل معرفی می‌کنیم .
الگوریتم PMM از یک جزء کنترل ورودی و یک جزء تخصیص حافظه تشکیل شده است . هر دوی این اجزاء از روش زمان‌بندی ED Earliest deadline استفاده می‌کنند ،‌بنابر این به Query هایی که عجله‌ای‌تر باشند در ورود به سیستم و تصمیمات تخصیص حافظه اولویت بیشتری نسبت به Query هایی که Dead line دورتری دارند خواهند داشت . جزء کنترل ورودی PMM هدف سطح Multi Proyramming mpl که با استفاده از انعکاس آماریی از نسبت‌های از دست‌دهی قبلی و مقادیر MPL های در رابطه با آنها تنظیم می‌کند . در شرایطی که این روش ناموفق باشد ، PMM به روش Heuristic ای برمی‌گردد که MPL که بر مبنای سطح‌های مصرف منابع مطلوبشان انتخاب می‌کند .
جزء تخصیص حافظه از یکی از دو استراتژی زیر استفاده کند :
1 ـ استراتژی Max که به هر Query حداکثر حافظة موردنیازش را می‌دهد و یا اصلاً حافظه‌ای به آن نمی‌دهد .
2 ـ استراتژی 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 –1
روش 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 –2
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 به صورت دینامیک اتکا کند .

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله   34 صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید