این متن شامل 33 صفحه می باشد 

در سالهاي اخير ، يك درخواست براي سيستم‌هاي 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 متمركز است . در اينجا الگوريتمي به نام