execute_edf(Job_head[P­_id] , , JQ­_{p_id} , P_id);
}
شکل ۳-۲۰ شبه‌کد سیاست زمانبندی TBS و EDF ]37[
شکل ۲۳شکل ۳-۲۰ شبه‌کد سیاست زمانبندی TBS و EDF [37]
Selected_processor(Job_AP) {
Find V_d for Job_AP an all the cores;
Selected the core with minimum V_d ;
Return processor id of Selected core;
}
شکل ۳-۲۱ شبه‌کد روش مهاجرت وظایف غیرتناوبی در ]۳۷[
شکل ۲۴شکل ۳-۲۱ شبه‌کد روش مهاجرت وظایف غیرتناوبی در [۳۷]
در ادامه با یک مثال عملکرد سیستم را بهتر نشان می­دهیم.
جدول ۳-۲، مجموعه وظایف تناوبی را نشان می­دهد که شامل شماره وظیفه، بدترین حالت زمان اجرا، دوره تناوب، سررسید و تعداد وظایف در یک فوق دوره^[۱۵۳] می­باشد. تمامی وظایف تناوبی در زمان صفر وارد سیستم شده و فوق دوره مجموعه وظیفه، ۱۶۸ است. در جدول ۳-۳ نیز یک مجموعه از وظایف غیرتناوبی که در زمان­های مختلف و داخواهی می­رسند، آورده شده است. شکل ۳-۲۲ نمودار زمانی وظایف این مثال را توسط الگوریتم بیان شده برروی ۲ هسته پردازشی و تا زمان ۱۷ نشان می­دهد. اعداد نشان داده شده در این نمودار، شماره­های متناظر با وظایف می­باشند. همانطورکه در این شکل قابل مشاهده است، الگوریتم مجموعه وظایف تناوبی را بین دو هسته پردازشی، جزءبندی می­ کند. وظیفه T₀ با بهره­وری ۵/۰ به هسته ۰ تخصیص داده می­ شود و وظیفه T­_۱ و T₂ به ترتیب با بهره­وری ۲۵/۰ و ۱۴/۰ به هسته ۱ تخصیص داده می­شوند از آنجاییکه کل بهره­وری هسته ۱ (۳۹/۰) کمتر از بهره­وری هسته ۰ (۵/۰) می­باشد، وظایف غیرتناوبی A₃ و A₄ که سررسیدهای مجازی نزدیکتری روی هسته ۱ بدست می­آورند، برروی هسته ۱ زمانبندی می­شوند A₅ نیز که در زمان ۶ وارد می­ شود ابتدا برروی هسته ۱ تخصیص داده می­ شود اما بعد به هسته ۰ برای قبضه شدن مهاجرت می­ کند.

جدول ۲جدول ۳-۲ مشخصات وظایف تناوبی در مثال مربوطه در [۳۷]
جدول ۳-۲ مشخصات وظایف تناوبی در مثال مربوطه در ]۳۷[

جدول ۳جدول ۳-۳ مشخصات وظایف غیرتناوبی در مثال مربوطه در [۳۷]
جدول ۳-۳ مشخصات وظایف غیرتناوبی در مثال مربوطه در ]۳۷[

شکل ۳-۲۲ نمودار زمانی مثال مربوطه در ]۳۷[
شکل ۲۵شکل ۳-۲۲ نمودار زمانی مثال مربوطه در [۳۷]
مزایا و معایب این الگوریتم :
یکی از مزایای این الگوریتم توجه به بهره‌وری هسته‌ها در هنگام توزیع وظایف می‌باشد که باعث شده تعادل بارگذاری بخوبی در آن انجام شود. همچنین تمایز بین وظایف تناوبی و غیرتناوبی از جمله مزیت‌های دیگر این الگوریتم است. اما بزرگترین عیب این الگوریتم این است که این الگوریتم فقط به بهره وری هسته‌ها پرداخته و سعی در کاهش بارکاری هر هسته دارد و اصلا به میزان انرژی مصرفی سیستم توجهی نکرده است. نوع توزیع وظایف بین هسته‌ها، عدم سعی در خالی نگه داشتن هسته‌ها و کاهش انرژی مصرفی آن‌ها و خاموش کردن هسته‌ها در حالت بیکار، باعث مصرف توان نامطلوب این الگوریتم خواهد شد.
۳-۷ نتیجه‌گیری
الگوریتم‌های زمانبندی چندهسته‌ای به سه دسته عمومی، جزبندی و دوگانه تقسیم می‌شوندو دارای مزایا و معایب خاص خود هستند. در این فصل علاوه بر اینکه طبقه‌بندی الگوریتم‌های چند هسته‌ای بیان شد، انواع روش‌های زمانبندی تک هسته‌ای نیز شرح داده شد. سپس چند مقاله به تفصیل مورد بررسی قرار گرفته و الگوریتم‌های پیشنهادی آن‌ها برای توزیع و زمانبندی وظایف بین هسته‌ها بیان شد. بیشتر این الگوریتم‌ها، چهار پارامتر مهم عدم نقض سررسید، مصرف انرژی پایین، زمان‌پاسخ وظایف غیرتناوبی و بهره‌وری سیستم، را به طور همزمان درنظر نگرفتند و تنها به یک یا چندتا از این پارامترها اهمیت می‌دادند. نکته بارز و قابل توجه روش‌های پیشنهاد شده تاکنون این است که هیچ کدام از این روش‌ها، برای اختصاص تعداد هسته‌ها با توجه به نوع وظایف سیستم، روشی را پیشنهاد نداده و تفکیک سازی متناسب با نوع وظایف، همراه با تفکیک سازی هسته‌ها از هم رخ نداده است. در حالی این مهم در روش پیشنهادی ما وجود داشته و نقش مهمی در کارایی الگوریتم پیشنهادی داشته است.
فصل چهارم
فصل چهارم : الگوریتم پیشنهادی
در این فصل الگوریتمی برای توزیع و زمانبندی وظایف در یک سیستم چندهسته‌ای پیشنهاد خواهد شد. این الگوریتم شامل سه سطح است، سطح اول تفکیک وظایف و هسته‌های متناسب با آن‌ها، سطح دوم الگوریتمی برای توزیع واختصاص وظایف بین هسته‌ها و سطح سوم، یک الگوریتم انرژی- سررسید محور، برای تنظیم فرکانس هسته‌ها متناسب با سررسید و زمان اجرای وظایف می‌باشد. همچنین برای زمانبندی هر صف از هسته‌ها از الگوریتم‌های تک‌پردازنده EDF و HPF^[154] استفاده شده است.
۴-۱ جایگاه الگوریتم پیشنهادی
در طبقه‌بندی روش‌های توزیع وظایف بین هسته‌ها در زمانبندی یک سیستم چندهسته‌ای، بیان شد که سه روش برای توزیع وظایف بین هسته‌ها وجود دارد: ۱) الگوریتم‌های جزبندی (بدون مهاجرت) ۲) الگوریتم‌های کاملا مهاجرتی (عمومی) ۳) الگوریتم‌های دوگانه (مهاجرتی محدودشده)
در الگوریتم‌های جزبندی، مجموعه کل وظایف سیستم به m زیرمجموعه مجزا (m تعداد هسته‌های پردازنده می‌باشد) تقسیم می‌شود و سپس هر زیرمجموعه به یک هسته اختصاص می‌یابد، هر هسته نیز با یک الگوریتم جدا برای خودش، این زیرمجموعه اختصاص یافته به خودش را زمانبندی می‌کند. در روش جزبندی، هیچ وظیفه‌ای از یک زیرمجموعه نمی‌تواند به زیرمجموعه دیگر مهاجرت کند و باید تا اتمام کار خود در صف همان هسته باقی بماند.
در الگوریتم‌های عمومی، کل وظایف سیستم، در یک صف عمومی قرار می‌گیرند و سپس توسط تنها یک زمانبند، زمانبندی شده و برای اجرا به هسته‌ها ارسال می‌شوند. در اینجا هر هسته دارای یک زمانبندی مجزا نیست و سیستم با همان تک زمانبند در صف عمومی، وظایف را به هسته‌های مورد نظر اختصاص می‌دهد. در این حالت وظایف می‌توانند بین هسته‌ها مهاجرت کنند و همچنین در صورت معلق شدن، می‌توانند پس از بازیابی، در پردازنده متفاوتی اجرا شوند.
اما در دسته سوم یعنی الگوریتم‌های دوگانه، برخی وظایف می‌توانند بین هسته‌ها جابجا شوند درحالی که برخی دیگر نمی‌توانند مهاجرت کنند. در واقع این نوع الگوریتم، ترکیبی از دو الگوریتم عمومی و جزبندی است.
الگوریتم پیشنهادی ما در این پژوهش، در دسته سوم این طبقه‌بندی، یعنی الگوریتم‌های دوگانه جای دارد. این بدین معنی است که در الگوریتم پیشنهادی ما، مجموعه کل وظایف سیستم، به دو زیرمجموعه مجزا تفکیک شده و هر زیرمجموعه، مربوط به دسته‌ای از هسته‌ها می‌باشد. همچنین هر کدام از این زیرمجموعه‌ها نیز خود به زیرمجموعه‌های دیگری به تعداد هسته‌های مربوط به خود تفکیک‌ شده و در نتیجه، هر هسته، روی مجموعه وظایف اختصاص یافته خود، زمانبندی را انجام می‌دهد. این مفهوم در شکل ۴-۱ به خوبی نشان داده شده است.
مجموعه کل وظایف سیستم
زیرمجموعه دوم وظایف
زیرمجموعه اول وظایف
هسته ۱
هسته ۴
هسته ۳
هسته ۲
الگوریتم زمانبندی مجزا
الگوریتم زمانبندی مجزا
الگوریتم زمانبندی مجزا
الگوریتم زمانبندی مجزا
الگوریتم توزیع مجزا
الگوریتم توزیع مجزا
شکل ۴-۱ ساختار کلی زمانبندی سیستم پیشنهادی