بخشی از مقاله
چکیده:
با پیشرفتهای سریع در زمینه تکنولوژی محاسبات سیار، نیاز به پردازش تراکنشهای بلادرنگ در محیط سیار رو به افزایش است. در این مقاله مسالهی کنترل همروندی در سیستمهای پایگاه دادهای بلادرنگ توزیعشدهی سیار (MDRTDBS) را مورد مطالعه قرار داده-
ایم و بر اساس مکانیزمهای HP-2PLپروتکلDHP-2PL یک
جدید قفلگذاری بلادرنگ توزیعشده برای سیستمهای MDRTDBS
ارائه کردهایم. در پروتکل ارائه شده، جهت برطرف نمودن برخورد میان تراکنشها از خصوصیات اولویت و زمان سکون تراکنشها استفاده شده است. بعلاوه، یک طرح توارث اولویت نیز در این پروتکل در نظر گرفته شده است. در ضمن به منظور ارزیابی بهتر کارایی مکانیزم ارائه شده، یک مدل شبیهسازی جامع توسعه داده شده است. نتایج آزمایشهای انجام شده نشان میدهد که پروتکل ارائه شده کارایی بهتری نسبت به پروتکلهای DHP-2PLو HP-2PL دارد.
واژه هـای کلیـدی: کنتـرل همرونـدی، سیسـتمهـای پایگـاه دادهای بلادرنگ توزیعشده، پایگاه دادههای بلادرنگ سـیار، سیاسـت تخصـیص اولویت، تراکنش یکنواخت، زمانبندی تراکنشها.
-1 مقدمه
پیشرفتهای اخیر در زمینه تکنولوژی ارتباط بیسیم، سرویسهای اطلاعاتی سیار را محقق ساخته است14]و2و3و.[4 از نمونههای جدید سیستمهای محاسباتی سیار1 میتوان به مواردی همچون سیستمهای پزشکی از راه دور2، سیستمهای اطلاعات و راهبری بلادرنگ ترافیک، و سیستمهای خرید و فروش سهام سیار3 اشاره کرد. تکنولوژی محاسباتی سیار، نه تنها توزیعشدگی و جریان اطلاعات را بهبود میدهد، بلکه بطور همزمان، عملکرد برنامههای کاربردی پایگاه داده بلادرنگمیزانرا به قابل توجهی افزایش میدهد. تحقق دسترسی فوری به اطلاعات در
شبکههای سیار، به پردازش بلادرنگ تراکنشها بستگی دارد و این موضوع موجب میشود تا مسئلهی دقت در دسترسی به دادهها به یک موضوع مهم و حیاتی تبدیل شود. در نتیجه، در سالهای اخیر پژوهش در زمینهی پردازش تراکنشهایبلادرنگِ نرم در سیستمهای پایگاه دادهایبلادرنگِ توزیعشدهی سیارتوجه((4MDRTDBS، مورد بیشتری واقع شده است14]و7و6و.[5
یکی از بحثهای مهم در تضمین دقت اجرای تراکنش، کنترل همروندی است. با این وجود، مکـانیزمهـای کنتـرل همرونـدی مـورد اسـتفاده در سیستمهای پایگاه دادهی عادی، برای سیستمهای پایگاه داده بلادرنـگ مناسب نیسـتند. تـراکنشهـای بلادرنـگ حیـاتی بـوده و بایـد طـوری زمانبندی شوند تا مهلت زمانی آنها ارضاء شود(یعنی اجرای هر تراکنش بایستی قبل از اتمام مهلت زمانی تعیین شده پایان پذیرد). پروتکلهـای کنترل همروندی معمولی همانند قفلگذاری دو مرحلهای و خوشبینانه، تراکنشها را بر اساس اصول یکسانی زمانبندی میکننـد. ممکـن اسـت تراکنشهای با اولویت بالاتر با مسـاله وارونگـی اولویـت درگیـر باشـند.
وارونگی اولویت به وضعیتی گفته میشـود کـه در آن یـک تـراکنش بـا اولویت بالا بوسیله تراکنشی با اولویت کمتر بلوکه شود9]و.[10
در این مقاله، بحث کنترل همروندی در سیستمهـای MDRTDBS را مورد مطالعه قرار میدهیم. بر اساس مکانیزمهـای 5HP-2PL و DHP-62PL، مکانیزم 7HPFS-2PL را برای این سیستمها پیشنهاد میکنـیم.
مزیت استفاده از الگوریتم پیشنهادی این است که در آن علاوه بر اینکـه اولویت تراکنشها مد نظر قرار دارند، زمان سکون آنها نیز در نظر گرفته میشود تا بدین وسیله از Miss شدن غیر ضروری تراکنشها در زمـانی که امکان اجرای کامل آنها وجود دارد، جلوگیری شود.
ما تراکنشهایی را در نظر مـیگیـریم کـه بصـورت یکنواخـت (Flat) و
ساده بوده و نیز دارای عملیات خواندن و نوشتن هسـتند. بـرای ارزیـابی کارایی مکانیزم پیشنهادی، یک مدل شبیه سازی دقیـق از محـیطهـای سیار توسعه داده و سپس با استفاده از این مدل، آزمایشهـای مختلفـی را انجام دادهایم تا بدین وسیله، توانـایی مکـانیزم ارائـه شـده را نمـایش دهیم.
باقیمانده مطالب این مقاله به شکل زیر سازماندهی شده است: در بخش
2 ویژگیهای مدل محیطهای پایگاه دادهای بلادرنگ توزیعشده سـیار و مدل تراکنش مورد استفاده در این محیطها ارائه شده است. در بخش 3
دو مورد از سیاستهای موجود برای تخصـیص اولویـت بـه تـراکنشهـا بررسی شده و در بخش 4 یک مکانیزم کنترل همرونـدی بـرای پایگـاه دادههای بلادرنگ توزیعشده و سیار پیشنهاد شده اسـت. آزمـایشهـا و شبیهسازیهای انجام شده و پارامترهای مـورد بررسـی در آنهـا نیـز در بخش 5 آورده شده است. درنهایت، نتیجهگیری در بخش 6 بیان شـده-
اند.
-2 مدل سیستمهای پایگاهدادهای بلادرنگ توزیعشدهی سیار
٢-١ مدل سیستم
یک محیط MDRTDBS شامل چهار مولفهی اصلی است که عبارتند از: سرویسگیرندههای سیار((8MC، ایستگاههای اصلی9، شبکه سـیار، و محل سوئیچینگ اصلی .[14](10MTSO) فرض مـیشـود کـه شـبکه سیار، یک شبکهی رادیویی بـوده و کـل دامنـهی سـرویس بـه تعـدادی سایت تقسیم شده باشد. در هر سایت یک ایستگاه اصلی وجود دارد کـه ارتباط سرویسگیرنـدههـای مربـوط بـه آن سـایت را فـراهم مـیکنـد.
ایستگاههای اصلی سایتهای مختلف از طریق شبکهی سیمی نقطه-بـه-
نقطه به MTSO متصل میشوند. بنابراین، ارتباطهای بین ایستگاههای اصلی و MTSO نسـبت بـه ارتبـاطهـای بـین ایسـتگاههـای اصـلی و سرویسگیرندههای سیار، کاراتر و قابل اطمینـانتـر هسـتند. همچنـین فرض میشود که یک پایگاه داده بلادرنگ وجـود دارد کـه در سـایتهای مختلف توزیع شده است. بدین ترتیب کـه در کنـار ایسـتگاه اصـلی هـر سایت، بخشی از این پایگاه داده موجود میباشد. نحوه دسترسی MCها به دادههای این پایگاه داده بدین شکل است کـه اگـر یـک MC قصـد دسترسی به دادهای را در همان سایت داشته باشد، این کار را از طریـق ایستگاه اصلی آن سایت انجام میدهد و در غیر اینصورت، اگـر نیـاز بـه دسترسی نمودن به دادههای سایتهای دیگر داشته باشد، ایـن کـار را از طریق MTSO انجام میدهد
٢-٢ مدل تراکنش
فرض میشود که تراکنشهای موجود در سیستم MDRTDBS از نوع تراکنشهای یکنواخت بوده و دارای مجموعهای از عملیات خواندن و نوشتن است. به محض ورود تراکنشها به سیستم، بر حسب اهمیت تراکنشها، به هر یک از آنها یک مهلت زمانی داده میشود که مقدار آن با استفاده از رابطهی (1) بدست میآید:
D(T)=ArrTime(T)+ExTime(T)*SlackFactor (1)
در رابطه (1)، D(T) نشاندهنده مهلت زمانی تراکنش T، ArrTime زمان ورود تراکنش به سیستم، ExTime زمان اجرای تخمینـی بـرای تراکنش T، و SlackFactor بیانگر فاکتور سکون است که عددی بین
1,5 و 3 بوده و با استفاده از آن میتوان میزان سفتی/نرمـی11 بلادرنـگ بودن تراکنش را تعیین نمود. و نیز مقدار پارامتر ExTime(T)این در رابطه با استفاده از فرمول زیر محاسبه میگردد:
ExTime(T)=(TLock+TProcess+TUpdate)*OpNum (2)
که در رابطهی (2)، TLock مدت زمان لازم برای قفل کردن یـک آیـتم دادهای، TProcess مدت زمان لازم بـرای پـردازش یـک عمـل تـراکنش،
Archvie of SID
TUpdate مــدت زمــان لازم بــرای بهنگــامســازی یــک آیــتم دادهای و OpNum بیانگر تعداد عملیات موجود در تراکنش میباشد.
اگر اجرای تراکنشی نتواند قبل از مهلت زمـانیاش کامـل شـود، Miss
خواهد شد. یـک تـراکنش مـیتوانـد بـه آیـتمهـای دادهای موجـود در سایتهای مختلف دسترسی داشته باشد. زمانیکـه اجـرای تمـام عملیـات یک تراکنش خاتمه مییابد، یک پروتکل نهـاییسـازی12 بـرای تضـمین خاصیت تجزیهناپذیری تراکنش اجرا خواهد شد. فرض بر این اسـت کـه برای نهاییشـدن تـراکنشهـا از پروتکـل نهـاییسـازی دو مرحلـهای13
استفاده میشود. برخی از مشخصات کلی تراکنشها در جـدول 1 آمـده است.
جدول :(1 ) مشخصات تراکنشهای یکنواخت
پارامتر مفهوم
Ti تراکنش iام
D(Ti) مهلت زمانی(فرجه) Ti
P(Ti) اولویت Ti
V(Ti) ارزش Ti
ArrTime(Ti) زمان ورود Ti به سیستم
SlackTime(Ti) زمان سکون Ti
StartTime(Ti) زمان شروع Ti
ExTime(Ti) مدت زمان تخمینی مورد نیاز
برای اجرای Ti
RemExTime(Ti) زمان اجرای باقیمانده Ti
ElaExTime(Ti) زمان اجرای سپری شده Ti
-3 سیاستهای تخصیص اولویت
یک زمانبند بلادرنگ شامل یک سیاست تخصیص اولویت و یک مکانیزم کنترل همروندی بلادرنگ است. چندین طرح تخصیص اولویت برای زمانبندی تراکنشهای یکنواخت در سیستمهای مدیریت پایگاه داده بلادرنگ استفاده میشود. بدون اولویتدهی، دو تراکنش Tiو Tj
واحدهای دیسک و CPU را بصورت اشتراکی استفاده میکنند و این ممکن است باعث شود قبل از اینکه تراکنشی اجرای خود را تمام کند، مهلت زمانی خود را از دست بدهد.[9] در ادامهی این بخش، دو سیاست تخصیص اولویت را مورد بررسی قرار میدهیم که در آزمایش-
های انجام شده از آنها استفاده شده است و در بخش بعدی، مکانیزم کنترل همروندی پیشنهادی را ارائه خواهیم نمود.
• سیاست :(Earliest Deadline) ED در سیاست ED، اولویت بالا به تراکنشهایی بـا زودتـرین مهلـت زمـانی تخصـیص داده مـی-شود.[10] فرمول تخصیص اولویت در این سیاسـت بصـورت زیـر است:
(٣) P(Ti)←1/D(Ti)
• سیاست :(Highest Value) HV مشکل سیاست ED این اسـت که این سیاست ارزش تراکنشها را در نظر نمـیگیـرد. تخصـیص اولویت بالا به تراکنشهایی با ارزش بالا، سیاست HV نامیده می-
