در مزایده های تلفنی، حداکثر مزایده با حداقل درخواست تطبیق داده می شود. در متا زمانبند، برنامه ای که زودترین پایان مهلت را دارد (و بنابراین فوری تر است) باید با سریع ترین صف تطبیق یابد که پردازشگرهای قابل دسترس کافی دارد. بنابراین، ما مکانیسم ارزیابی خودمان را ساخته ایم از این رو، ارزیابی های منابع، درخواست است و برنامه یا ارزیابی کار، مزایده هستند. ارزیابی منابع و برنامه ها به عوامل زیادی از جمله عرضه و تقاضا، بارهای منبع و پایان مهلت های کاربر بستگی دارند. ما مجبوریم این اقدامات چندگانه را با یک ارزش واحد تطبیق دهیم که بتوان برای مقایسه این ارزش ها استفاده کرد. به این منظور، ما نظریه سود چند ویژگی(MAUT) را بکار می گیریم [۲۴,۲۵,۲۶]، که یک روش منطقی، منسجم و اسان برای تعیین تنظیمات شخصی از طریق ادغام انها در یک هدف واحد را ارائه می کند. این تئوری ابتدا به شناسائی ویژگیها و تابع مطلوبیت برای هر ویژگی و سپس تجمع این تابع مطلوبیت در یک ارزش ابزار عددی واحد می پردازد.

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

ارزیابی منابع( درخواست) زمانبندهای کار دسته ای که منابع را مدیریت می کنند عموما به عنوان مجموعه صف هایی با ویژگیهای مختلف ساخته می شوند. بار یک صف به عنوان نسبت تعداد پردازشگرهایی که با کارها مشغول می شود به تعداد کل پردازشگرهای موجود برای صف تعریف می شود. متا زمانبند سعی می کند برای متعادل کردن بار در سایت های شبکه، در حال ارائه برنامه، تقدم را به صف هایی بدهد که کمترین بار را دارند. همچنین، فوریترین برنامه باید با سریعترین صف ها مطابق شوند. بنابراین، متریک ارزیابی صف های منابع باید طوری باشند که صفی با حداقل زمان انتظار ،کمترین ارزش درخواست را داشته باشد. متریک ارزیابی باید ارزیابی اولیه که فروشنده منبع ارائه می کند را در نظر بگیرد و همچنین سطوح عرضه و تقاضا منابع در سیستم ( که عرضه و تقاضا معنی می شود). تقاضا مجموع پردازشگرهائی است که برنامه ها برای تخصیص به ان نیاز دارند و عرضه، کل تعداد پردازشگرهای موجود در همه منابع است..فرض کنید l_k, _t بار روی صف منابع k در زمان t باشد. فرض کنید c_k,t ارزش منبع اولیه باشد که فروشنده ارائه کرده است. فرض کنید w_k,t زمان انتظار برنامه برای صف k در زمان t باشد. بنا براین، تابع مطلوبیت متناسب با w_k,_t, c_k,_{t ،} عرضه و تقاضا وL_kt هستند. از انجا که هر یک از این ویژگیها ترجیحا مستقل هستند[۲۶] بنابراین ارزش متریک را می توان با تجمع این ویژگیها در شکل افزاینده یا جمع پذیر تشکیل داد و وقتی اثرات هر متریک را روی توزیع بار روی سایت های منبع مقایسه می کنیم مشاهده می شودکه در مورد شکل جمع پذیر انحراف در بار در سایت های منبع بسیار بیشتر از انحراف در بار در شکل افزاینده است که در شکل ۳-۸ نشان داده می شود.

شکل۳-۸٫ مقایسه حالت های ضربی و جمعی در فاکتور ارزیابی

بعلاوه، وقتی بیشتر از دو ویژگی مشارکت دارند یک تجمع جمع پذیر صحیح نیاز به مبادله دقیق بین ویژگیها دارد که ممکن است ظاهر نباشد. بنابراین، ما از یک تجمع افزاینده استفاده کرده ایم تا یک متریک ارزیابی را از ویژگیهای نرمال شده، شکل دهیم که c_{max, t} حداکثر ارزیابی ابتدائی است که فروشنده منابع ارائه کرده است و L_{max t} حداکثر بار روی منابع است. این متریک ارزیابی(t) a_k صف k در زمان t توسط معادله زیر ارائه می شود:
(۳-۹) 
که O_k ثابت تناسب است که برای اهداف شبیه سازی ۱ گرفته می شود.
ارزیابی کار(مزایده) مثل منابع، یک برنامه کاربر ویژگیهای زیادی از قبیل تعداد CPUs ، پایان مهلت و زمان اجرا نیاز دارد. متریک ارزیابی برنامه i در زمان t به روشی طراحی می شود که حداکثر ارزش به برنامه هایی با پایان مهلت فوری اختصاص می یابد. همچنین، اگر یک برنامه در چرخه زمانبندی قبلی ترسیم نشده است مزایده مربوط به ان (ارزیابی) باید افزایش یابد. برای اینکه احتمال خالی شدن این برنامه توسط دیگران با ارزیابی بالاتر (مزایده) که همزمان به متازمانبند رسیده اند را کاهش دهیم. (d_i-t) نشان می دهد که کاربر چقدر زود می خواهد برنامه i اجرا شود که _di پایان مهلتی است که کاربر برای برنامه i فراهم کرده است. فرض کنید st_i زمان ارائه برنامه باشد همینطور برای منابع، متریک برنامه باید ارزیابی اولیه برنامه کاربر و همچنین سطوح عرضه و تقاضای منابع در این سیستم (که عرضه و تقاضا معنی می شود) را در نظر بگیرد. فرض کنید  ارزیابی اولیه برنامه باشد که کاربر ارائه می کند. بنابراین، تابع مطلوبیت متناسب با v_i و st_i ، عرضه و تقاضا (d_i-t) هستند فرض کنید d_maxوv_max و st_max به ترتیب بالاترین ارزیابی اولیه ، بزرگترین پایان مهلت و زودترین زمان اغاز باشند. متریک ارزیابی حاصله برای برنامه i در زمان t با ضرب کردن همه ویژگیهای نرمال شده به صورت رابطه ۳-۱۰ است :
(۳-۱۰) 
که H_i ثابت تناسب است که برای اهداف شبیه سازی ۱ گرفته می شود. و 
همانطور بیان شد، واحد کالا که از سوی سایت های منبع مطابق می شود شیاری است که یک مجموعه از پردازشگرها توسط زمان اغاز و پایان محدود می شوند. شکل ۳-۹روشی را نشان می دهد که با بهره گرفتن از ان می توان شیار ها را در یک سایت شبکه تولید کرد. در زمان t زمانبند کار محلی می تواند شیارهای زمانی را فراهم کند که درحال حاضر ازاد هستند، بنابراین، برنامه ها را می توان برای پر کردن صف در یک افق زمانی خاص T_iبا متا زمانبند زمانبندی کرد. شیار ها از اولین زمان موجود اغاز می شوند و دارای پردازشگرهای زیادی هستند که برای یک مدت خاص مشغول نیستند. شیار های S₁ به S₅ در شکل ۳-۹، نمونه های چنین شیار های ازاد هستند. فهرست شیار های موجود را می توان با زمانبند کار محلی با بهره گرفتن از زمان اجرای تخمین زده شده برنامه تولید کرد. همانطور که در شکل ۳-۹ نشان داده شده پس از زمان کنونی t دو پردازشگر در صف تا زمان T_H آزاد هستند زیرا تخمین زده می شود که کارهای J₆و J₇ قبل زمان t پایان یابند. بنابرابن، شیار زمان موجود با زمان موجود T_H-t است. در مورد صف کارهای J₄ و J₃ پس از زمان t پایان می یابند و ارزیابی می شود که در زمان های مختلف تکمیل شوند. بنابراین، پردازشگرهای ازاد همزمان پس از زمان t منجر به دو شیار زمان می شوند که هر یک تعداد پردازشگرها و واحد زمان قابل دسترس متفاوتی دارند. به همین صورت یک شیار زمان دیگر شامل یک پردازشگر در صف نیز قابل دسترس است. این روش که شیار دارای اندازه های مختلف است توسط سینق (Singh)و همکاران[۲۷] بکار رفت. در این مورد، زمانبند محلی در سایت منبع می تواند دوباره پر شود تا بخشی را در زمانبندی کوچک کند بطوریکه اجرای برنامه در صف به تاخیر نیافتد. متا زمانبند، برنامه را در فواصل زمانی منظم زمانبندی می کند بنابراین در اغاز چرخه زمانبندی شیار صف به روز شده موجود

شکل ۳-۹٫ساختار خانه های صف

را با بهره گرفتن از روش بالا از زمانبندهای کار محلی می گیرد. الگوریتم زمانبندی پیشنهادی این روش در شکل ۳-۱۰ نشان داده می شود. متا زمانبند در هر چرخه زمانبندی، برنامه های موازی را پس از جمع اوری درخواستهای همه کاربران و اطلاعات عملکرد منابع از قبیل زمان انتظار صف و شیار های زمان ازاد، زمانبندی می کند (خط ۳-۱). متا زمانبند، در پایان هر چرخه زمانبندی، تقاضا برای منابع و عرضه انها را محاسبه می کند. (خط ۴). سپس متا زمانبند ، براساس اطلاعات جمع اوری شده از کابران و منابع، ارزیابی را با بهره گرفتن از مکانیسم های ارزیابی که در بخش قبلی ارائه شدند (خط ۶) به برنامه کاربر (مزایده) و صف منابع(درخواست) اختصاص می دهد. از فهرست مزایده دسته بندی شده ، مزایده (b_i) با بالاترین ارزش با صف منبع با حداقل درخواست (a_j) منطبق خواهد شد که می تواند نیازهای کاربر را براورده کند. ایا برنامه i کاربر به صف منبع j زمانبندی خواهد شد(در ارتباط با درخواست a_j ) به پردازشگر برنامه و نیاهای پایان مهلت بستگی دارد. بنابراین اولین پایان مهلت برنامه i با بهره گرفتن از زمان انتظار صف منبع j بررسی می شود(خط ۱۳). اگر درخواستی باشد که نیازهای برنامه QOS را براورده کند سپس مزایده برای درخواست منطبق می شود؛ و کاربر منطبق شده و فروشنده منبع از تصمیم اگاه می شوند. برنامه i روی صف منبع j زمانبندی می شود(خط ۱۴) و سپس به فهرست زمانبندی اضافه می شود (خط ۱۵). شیار های زمان موجود (واحدهای کالا) روی صف متقابلا به روز می شوند(خط ۱۶). اگر نیازهای پایان مهلت برنامه i با صف منبع j براورده شوند سپس هیچ درخواست دیگری را نمی توان با مزایده برنامه منطبق کرد (خط ۲۰). بنابراین، برنامه از فهرست مزایده در ان چرخه زمانبندی حذف می شود. اگر تعداد پردازشگرهای مورد نیاز در صف منبع j موجود نباشد مزایده b_i با درخواست بعدی در سکانس منطبق می شود(خط ۲۱). انطباق برای دیگر مزایده ها و درخواست ها که در لیست الحاقی هستند باید در چرخه زمانبندی بعدی با درخواست های جدید انجام گیرد. همه کاربرانی که برنامه های انها زمانبندی شده است در مورد منطبق شدن، توسط متا زمانبند اگاه شده اند. (خط ۲۳). این فرایند در هر چرخه زمانبندی با محاسبه مجدد ارزش درخواست و مزایده تکرار می شود تا همه مزایده ها یا درخواست ها منطبق شوند. همچنین باید بگوئیم که فرایند ارزیابی به گونه ای است که مزایده های منطبق نشده ارزش بالاتری در چرخه زمانبندی بعدی دریافت خواهد کرد تا از کمبود کار جلوگیری کند.

• • 1. 1. while current-time < next-8chedule-time do

     

    1. 1. Recv Resource Publish (P):

     

     

/ / P contains information about providers
۳ RecvJobQos (Q) ;
/ / Q contains Qos information about users
۴ Add information of pending applications from previous
Scheduling cycle to RecvJobQos;
۵ Calculate the Demand and Supply for resources;
۶ Update the value of bids and asks using eqn. 2 and 1;
۷ Sort asks in ascending order :
۸ Sort bids in descending order;
۹ while no all applications are assigned to resource queues do
۱۰ i = 1, j = 1;
۱۱ if bid b_i is greater than ask a_j then
۱۲ if QueueWaitingTime(j) + ExecTime(i) <
Deadline(i) then
۱۳ if check processor availability on resource j
then

1. 1. Schedule the application i to the resource j;

1. 1. add application with matched resource site

in Schedule List (Schd-List) ;

1. 1. update the value of available time slots

from resource j;

1. 1. i + +;

۱۸