: در سالهای اخیر ، یک درخواست برای سیستمهای 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 در حال اجرا ممکن است با گذشت زمان به علت آمدن و رفتن 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