(۹)
یک مجموعه از n وظیفه غیرتناوبی، بوسیله سیاست زمانبندی DMS ، قابل زمانبندی است هرگاه :
(۱۰)
که UB(n) به صورت زیر تعریف می‌شود:
(۱۱)
معماری زمانبندی الگوریتم مرجع ]۳۵[ :
می‌دانیم که وظایف تناوبی در سیستم‌های تعبیه‌شده، دائم در حال تکرار شدن اجرایشان هستند، تا زمانیکه پردازنده خاموش شود. بنابراین بهتر است که بین تکرار وظایف، هسته‌ها بجای اینکه خاموش و روشن شوند، به حالت مصرف‌پایین^[۱۳۷] بروند. در این الگوریتم وظایف تناوبی را به تعداد کمی هسته محدود کرده اند تا به حداقل هسته‌ها برای روشن ماندن نیاز داشته باشند، از سوی دیگر، وظایف غیرتناوبی را که خیلی کمتر رخ می‌دهند، به بقیه هسته‌ها اختصاص داده اند.وقتی اجرای یک وظیفه به پایان رسید، هسته‌ متناظر آن، همانند حافظه نهان آن، میتواند خاموش شود، بنابراین نیازی نیست محتوای مقادیر این وظایف که قرار نیست تا آینده‌ای نزدیک اتفاق بیوفتد، نگهداری شود. در الگوریتم این مقاله، وظایف تناوبی به وسیله الگوریتم RBound-FF به حداقل هسته‌ها اختصاص می‌یابند و وظایف غیرتناوبی بین بقیه هسته‌ها به صورت عادلانه توزیع می‌شوند. شبه کد این الگوریتم را در شکل ۳-۱۱ صفحه بعد مشاهده می‌کنید.

Task assignment(Inpot: τ_j , schedparam)
Begin
If(schedparam ->scedpolicy == RMS)
Assign τ_j to its bounded core
Endif
If(schedparam ->scedpolicy == DMS)
P_i = IDLestCore_RestCore()
If (τ_j can be admitted on P_i)
Assign τ_j to P_i
Endif
Else return(REJECT)
Endif
end
شکل ۳-۱۱ الگوریتم اختصاص دادن وظایف در مرجع ]۳۵[
شکل ۱۴شکل ۳-۱۱ الگوریتم اختصاص دادن وظایف در مرجع [۳۵]
مزایا و معایب این الگوریتم:
این الگوریتم بدلیل استفاده از RMS در زمانبندی وظایف تناوبی و الگوریتم DMS برای زمانبندی وظایف غیرتناوبی، می‌تواند تاثیر بسازیی در کاهش نرخ نقض سررسید وظایف گردد. همچنین در این الگوریتم نیز وظایف تناوبی از وظایف غیرتناوبی تفکیک شده و جداگانه توزیع می‌شوند که در مصرف انرژی موثر می‌باشد.
اما از جمله معایب این الگوریتم این است که، ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا توسط الگوریتم RBound جزءبندی شوند و این مسئله باعث افزایش سربار زمان اجرا می‌شود. همچنین در این الگوریتم نیز فشار زیادی روی تعداد محدودی از هسته‌ها برای اجرای وظایف غیرتناوبی می‌باشد که باعث می‌شود کارایی سیستم پایین بیاید.
۳-۶-۳ الگوریتم زمانبندی چند سطحی PDAMS ^[۱۳۸]
در مرجع ]۳۶[ ، مسئله زمانبندی چندهسته‌ای توان محور^[۱۳۹] به دو قسمت زیر تقسیم می‌شود:

• • توزیع بار ^[۱۴۰] بین هسته‌ها

• • زمانبندی توان محور برای هر هسته

با توجه به همین تقسیم‌بندی، برای هر کدام از این موارد، الگوریتم‌هایی جداگانه پیشنهاد شده است. برای کم‌کردن محدودیت‌ها وساختن یک الگوریتمی که اجرایش راحت‌تر باشد، از دست دادن برخی سررسیدها در این پژوهش اجازه داده شده است. مدلی که در این مقاله پیشنهاد شده، بشرح زیر می‌باشد.
مدل سیستم پیشنهادی مقاله ]۳۶[ :
در این سیستم، یک واحد پردازنده به عنوان مدیر^[۱۴۱] و n تا هسته پردازنده به عنوان برده^[۱۴۲] ، وجود دارند و هر هسته پردازنده برای خودش یک سیستم‌عامل خاص دارد و می‌تواند به صورت مستقل، فرکانس و ولتاژ عملیاتی خود را تغییر و تنظیم کند. وقتی وظایف در این سیستم توزیع می‌شوند، واحد پردازنده مدیر، اطلاعات هر هسته را بوسیله IPC ^[۱۴۳] مبادله می‌کند و سپس این وظایف را بین هسته‌ها توزیع می‌کند. سپس هسته‌ها، وظایفی که به آنها توزیع شده است را به صورت مستقل زمانبندی می‌کنند. تحت این معماری، الگوریتم پیشنهادی این مقاله می‌تواند هم برای سیستم‌های چندهسته‌ای همگن و هم ناهمگن پذیرفته شود و هر هسته پردازنده می‌تواند خودش را مدیریت کند.
ورودی‌های الگوریتم:
یک مجموعه کلی برای همه وظایف در نظر می‌گیریم:
T= { T_real , T_normal } (۱۲)
T_real مجموعه وظایف بی‌درنگ می‌باشد و T_normal مجموعه وظایف معمولی است. همچنین هر وظیفه بی‌درنگ دارای مشخصات زیر می‌باشد:

• • زمان آزادشدن

• • اولویت

• • سررسید متناظر

همچنین این وظایف می‌توانند تناوبی یا غیرتناوبی باشند. در محیط های پویا، بدست آوردن همه اطلاعات یک وظیفه مشکل می باشد و همچنین سربار الگوریتم‌های بهینه‌سازی استفاده شده، بسیار سنگین است( هنگامی که هر وظیفه آزاد می شود). بنابراین در این مقاله سعی شده است که بدون در نظر گرفتن زمان اجرای وظایف، وظایف بی‌درنگ را زمانبندی کند.
با اینکه سررسیدهای سخت ضمانت نشده است ولی روش‌هایی که پیشنهاد داده شده تا حد امکان باعث کاهش از دست دادن سررسیدها شده است..
T_normal فقط از مشخصه‌ های اولویت و زمان آزاد شدن تشکیل شده است. در کل، ترتیب اجرای وظایف بی‌درنگ براساس سررسید مطلق وظایف می‌باشد. اولویت وظایف بی‌درنگ فقط وقتی که دو یا چند وظیفه دارای سررسید مطلق یکسانی باشند، استفاده می شود.
خروجی الگوریتم :
خروجی الگوریتم PDAMS، یک مجموعه‌ای از زمانبندی‌های ممکن S که :
S= { S₁ , S₂ , … , S_n } (۱۳)

وجود تنوع در سراسر طیف وسیعی از معماری چندهسته‌ای، صرفا یک چالش نیست. در یک سیستم واحد، معماری هسته‌ها می‌تواند متفاوت باشد، همانطور که روند کنونی چنین است و بیشتر به سمت ترکیبی از هسته‌های متفاوت می‌رود. در طراحی برخی سیستم‌ها، هسته‌ها دارای مجموعه دستورالعمل‌های مشترکی هستند ولی مشخصه‌ های کارایی آن‌ها باهم متفاوت است.
از این رو، یک پردازنده با تعداد کمی هسته‌های قدرتمند ، برای برنامه‌های موازی، ناکارامد می‌باشد. اما از سوی دیگر، یک پردازنده با تعداد زیادی هسته‌های ضعیف‌، ممکن است در اجرای برنامه‌هایی که نیازمند عملیات محاسباتی ترتیبی هستند، ضعیف عمل کند. حالت دیگر در سیستم‌های چندهسته‌ای ، داشتن هسته‌هایی با مجموعه دستورالعمل‌های متفاوت برای توابع تخصصی (مانند ترکیب کردن سیستم‌های همه‌منظوره و هسته‌های DSP ) می‌باشد. از کاربردهای این حالت می‌توان به GPU ها، مدارهای واسط شبکه و دیگر کاربردهای خاص و قابل برنامه‌ریزی اشاره‌کرد.

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

۲-۹ نتیجه‌گیری
در این فصل به تعریف سیستم‌های تعبیه‌شده و کاربردهای مهم آن در زندگی روزمره پرداخته شد و مفهوم بی‌درنگ بودن و انواع سیستم‌های بی‌درنگ شرح داده شد. سپس به بیان تعاریف مفاهیم اولیه در سیستم‌های بی‌درنگ تعبیه‌شده پرداخته شد و در پایان نیز سیستم‌های چندهسته‌ای تعبیه‌شده تعریف و شرح داده‌ شدند.
فصل سوم
فصل سوم : مرور منابع و کارهای انجام‌شده
در فصل قبل مفاهیمی مانند سیستم‌های تعبیه‌شده و تعبیه شده بی‌درنگ، اهمیت مصرف انرژی در آن‌ها و اصطلاحات مهم آن، به طور کامل تشریح شد و سپس مفهوم زمانبندی مورد بررسی قرار گرفت و در نهایت سیستم‌های چندهسته‌ای معرفی و تعریف شدند. دراین فصل ابتدا به طبقه‌بندی انواع روش‌های زمانبندی تک‌هسته‌ای و چند‌هسته‌ای می‌پردازیم، سپس انواع معماری سیستم‌های چندهسته‌ای را تشریح می‌کنیم، پس از آن، روش‌های زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان می‌کنیم و در نهایت به شرح کامل روش‌های زمانبندی چندهسته‌ای ارائه شده در سال‌های گذشته می‌پردازیم و مزایا و معایب آن‌ها را تحلیل می‌کنیم.
۳-۱ طبقه بندی روش‌های زمانبندی
در این بخش مروری داریم بر طبقه‌بندی الگوریتم‌های زمانبندی که مگر در موارد مشخص‌شده، درهمه‌ موارد، قبضه‌ای بودن اجازه داده‌ شده‌است.

• • زمانبندی برخط^[۸۷] و برون‌خط^[۸۸] :

اولین نوع زمانبندی، براساس زمانی که زمانبندی در آن تولید می‌شود و همچنین تمایز بین زمانبندی برخط و زمانبندی برون‌خط، شکل گرفته است. در زمانبندی‌های برخط، در مورد اینکه چگونه وظایف در زمان اجرا در طول عملیات سیستم، زمانبندی شوند، تصمیم‌گیری می‌شود. بنابراین الگوریتم زمانبندی که بکار گرفته می‌شود، نشان‌دهنده نقش فعال و اساسی بخشی از نرم‌افزار است که بارها و بارها احضار می‌شود تا برای انجام زمانبندی مناسب تصمیماتی را به صورت لحظه‌ای اتخاذ کند. ( مانند آزادشدن یک وظیفه، انقضاء یک ساعت، تمام شدن یک وظیفه )
به همین دلیل الگوریتم‌های زمانبندی برخط، اگرچه بسیار انعطاف‌پذیر هستند؛ به عنوان مثال اجازه می‌دهند که یک وظیفه بی‌درنگ جدید به صورت پویا به سیستم وارد شده و زمانبندی شوند؛ ولی باعث بوجود آمدن سربار^[۸۹] زمان اجرا می‌شوند که باید با دقت بالایی محاسبه شود. در مورد الگوریتم‌های پیچیده، در حقیقت خود الگوریتم زمانبندی ممکن است هزینه‌ها و سربارهای محاسباتی غیرقابل اغماضی را مطالبه کند، که باعث می‌شود کل سیستم (وظایف بی‌درنگ+ زمانبند) غیرقابل زمانبندی شود.اگرچه زمانبندی برخط نشان داده است که یک طرح بسیار معمولی در بیشتر سیستم‌‌های تعبیه‌شده نوین می‌باشد.
برخلاف زمانبندی برخط، در زمانبندی برون‌خط، سیاست زمانبندی در طول زمان اجرای سیستم بی‌درنگ، اعمال نمی‌شود، بلکه از آن برای گرفتن تصمیمات و ایجاد دنباله‌ای از عملیات زمانبندی، قبل از فعال‌شدن و شروع به کار سیستم استفاده می‌شود. این رویکرد که طبیعتی ایستا و غیرقابل انعطاف دارد، به طراح اجازه می‌دهد که یک تصمیم بهینه و درعین حال بسیار پیچیده‌ای بگیرد. الگوریتم‌هایی که در برخی موارد نشان‌دهنده آخرین راه‌حل می‌باشند درحالی که تقاضای محاسباتی بالا و محدودیت زمانی سخت، اجازه مطرح‌شدن پیشنهادات برخط را نمی‌دهد.
ممکن است حالتی نیز وجود داشته باشد که الگوریتم زمانبندی آن با بهره گرفتن از تجزیه‌شدن به دو مرحله، چیزی بین این دو رده‌بندی باشد. برای مثال، می‌توان الگوریتم را به یک مرحله پیش‌پردازش^[۹۰] جدا تجزیه کرد که در آن تمام وظایف مجموعه τ، به زیرمجموعه‌های کوچکتر تقسیم شده و در مرحله زمانبندی واقعی، یک الگوریتم زمانبندی برخط بروی هرکدام از زیرمجموعه‌های شناسایی شده اعمال می‌شود. مرحله پیش‌پردازش، در این موارد ممکن است به منظور کاهش پیچیدگی مسئله و سربار زمان اجرای آن، به صورت برون‌خط باشد.

• • زمانبندی مبتنی بر اولویت:

الگوریتم‌های زمانبندی با توجه به نحوه تخصیص اولویت به سه دسته تقسیم می‌شوند:

• • الگوریتم‌های اولویت ایستا^[۹۱]

در این شیوه به هر وظیفه یک اولویت منحصر به فرد اختصاص داده‌ می‌شود و همه‌ی نخ‌های^[۹۲] یک وظیفه دارای اولویت یکسانی هستند. بنابراین هرگاه وظیفه T₁ دارای اولویت بالاتری نسبت به وظیفه T₂ داشته باشد، سپس هرزمان که هر دو وظیفه دارای نخ‌های فعالی باشند، نخ‌های وظیفه T₁ بر T₂ مقدم خواهد بود. نمونه‌ای از یک الگوریتم زمانبندی اولویت ایستا، الگوریتم زمانبندی نرخ یکنواخت (RMS) ^[۹۳] می‌باشد.

• • الگوریتم‌های اولویت پویای سطح نخ^[۹۴]

برای جفت نخ‌های T_ij و T_i^,_j^, ، اگر T_ij اولویت بالاتری نسبت به T_i^,_j^, در برخی لحظه‌های زمانی داشته باشد، آنگاه T_ij همیشه اولویت بالاتری نسبت به T_i^,_j^, دارد. نمونه‌ای از زمانبندی که دز این کلاس قرار می‌گیرد، زمانبندی ابتدا نزدیکترین سررسید (EDF)^[95] می‌باشد.

• • الگوریتم‌های اولویت پویای بدون محدودیت^[۹۶]

در این حالت هیچ محدودیتی در اولویتی که به یک وظیفه داده می‌شود وجود ندارد و اولویت مربوط به دو وظیفه ممکن است در طول زمان تغییر کند. به عنوان یک مثالی از این نوع که در هیچ‌یک از دو رده‌بندی قبل جای نمی‌گیرد، می‌توان به الگوریتم LLF ^[۹۷] اشاره کرد]۱۹[ .
با توجه به این تعاریف الگوریتم‌های اولویت پویای بدون محدودیت یک حالت کلی از الگوریتم‌های اولویت پویای سطح نخ هستند و الگوریتم‌های اولویت پویای سطح نخ نیز یک حالت کلی از الگوریتم‌های اولویت ثابت می‌باشند.

• • الگوریتم‌های WCET ^[۹۸] محور :

یکی از مهم‌ترین مشخصه‌هایی که برای وظایف بی‌درنگ مطرح شده، WCET یا بدترین حالت زمان اجرای وظیفه می‌باشد. این ویژگی برای تقریبا بیشتر آزمون‌های تجزیه و تحلیل قابلیت زمانبندی^[۹۹] شناخته‌شده ، اساسی است(تعیین پیشبینی این‌که یک الگوریتم زمانبندی، قادر به زمانبندی کردن وظیفه روی زمینه داده‌شده تحت بدترین مفروضات ممکن است یا نه). این پارامتر ممکن است در زمان اجرا توسط الگوریتم برای گرفتن تصمیمات زمانبندی موردنیاز باشد یا ممکن است نباشد.
در این رابطه ما می‌توانیم الگوریتم‌هایی که WCET محور هستند ( مانند الگوریتم LLF ) را از الگوریتم‌هایی که WCET محور نیستند ( مانند الگوریتم RMS و EDF ) را از هم تمییز دهیم. این تفاوت معمولا هنگامی که وظایف از تخمین بدترین حالت زمان اجرایشان منحرف می‌شوند، دلالت قوی بر رفتار الگوریتم‌های زمانبندی دارد.
انواع روش‌های زمانبندی
مبتنی بر اولویت
زمانبندی WCET محور
اولویت پویای بدون محدودیت
اولویت پویای سطح نخ
اولویت ایستا
پویا
پویا
ایستا
ایستا
پویا

ساختار زمان بندی ابری بلادرنگ شامل ۵ مرحله زیر می باشد:

1. 1. 1. درخواست خدمات به صورت زیر ساختی (IaaS) برای ارائه درخواست های کارهای بلادرنگ و مشخصه های آن به کارگزار (broker)

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

1. 1. ایجاد ماشین مجازی بلادرنگ بر اساس کارهای بلادرنگ (RT-VM)

1. 1. درخواست ماشین مجازی بلادرنگ: کارگزار درخواست ماشین را برای (RT- VM) می دهد.

این درخواست از تخصیص دهنده ماشین مجازی در ابرهای محاسباتی انجام می شود.

1. 1. نگاشت پردازده فیزیکی (تخصیص ماشین مجازی)

1. 1. اجرای برنامه های بلادرنگ

کار ما در مرحله ۳ انجام می شود، یعنی با بهره گرفتن از الگوریتم رقابت استعماری نگاشتی از بهترین تخصیص ماشین های مجازی به خادمی که کمترین زمان اجرا، با توجه به کمترین ظرفیت لازم برای اجرای آن ماشین مجازی دارد را انتخاب می کند و بر می گرداند.
شکل ۳-۳ نشان دهنده چگونگی انجام مراحل فوق می باشد.
شکل ۳-۳ نمایش چگونگی ساختار زمان بندی کارهای بلادرنگ در ابرهای محاسباتی
در ادامه نحوه انجام مرحله ۳ که همان الگوریتم رقابت استعماری می باشد را بیان می کنیم.
طبق الگوریتم تطابق اولیه، ماشین های مجازی به خادم ها اختصاص داده می شوند و سپس با بهره گرفتن از الگوریتم رقابت استعماری بهترین جایگذاری انتخاب می شود.
۳-۱-۵ مراحل اجرای الگوریتم رقابت استعماری
۳-۱-۵-۱ شکل دهی امپراطوری های اولیه
جمعیت اولیه متشکل از تعدادی راه حل می باشد که در الگوریتم رقابت استعماری استاندارد به صورت تصادفی ایجاد می شود. در این روش قصد داریم جمعیت اولیه را به صورت هدفمند ایجاد نماییم تا علاوه بر تسریع در یافتن جواب، پاسخ بدست آمده نیز نسبت به حالت معمول، به پاسخ بهینه نزدیک تر باشد. روش کار به این صورت است که برای پیشنهاد یک خادم به هر کار ابتدا مناسب بودن آن به صورت زیر بررسی می شود.

کمترین مقدار(هرچه کوچکتر از یک باشد بهتر است)
همانطور که بیان گردید هر کلونی نشان دهنده یک ماشین مجازی و خادم مناسب برای آن می باشد. بهترین خادم از لحاظ زمان اجرای کار با توجه به کمترین ظرفیت لازم برای آن در نظر گرفته می شود، در صورتی که خادمی واجد شرایط نباشد، خادم بعدی (دومین بهترین خادم) تست می شود و این روند به صورت best fit برای تمامی کلونی ها صورت می گیرد و سپس لیست خادم های کشور بر اساس ظرفیت باقی مانده هر خادم و با توجه به حجم کاری ماشین های مجازی، به روز می شود.
در تشکیل جمعیت اولیه، ایجاد هر راه حل نسبت به راه حل قبلی به این صورت است که برای کلونی ابتدایی، خادمی تست می شود که نسبت به همان کلونی در کشور قبلی، در اولویت بعدی از لیست خادم های مرکز داده قرار دارد، این شیوه انتخاب خادم های کاندید، نسبت به روش تصادفی باعث می شود تمامی خادم ها شانس قرار گرفتن در راه حل را داشته باشند. بدین ترتیب جمعیتی خواهیم داشت که تمامی راه حل های ممکن را دارد.
تابع هزینه را برای کشورها محاسبه می کنیم و ۱۰ تا از کشورهایی که دارای تابع هزینه کمتری هستند را به عنوان استعمارگر انتخاب می کنیم. سایر کشور ها را به صورت تصادفی بین این ۱۰ استعمارگر تقسیم می کنیم. شکل ۳-۵ چگونگی شکل گیری جمعیت و امپراطوری های اولیه را نشان می دهد.
قدرت کل هر امپراطوری را با درنظر گرفتن محاسبه می کنیم، به صورت مجموع مقدار تابع هزینه استعمارگر آن امپراطوری با ۰.۱ مجموع مقادیر تابع هزینه ی مستعمره های آن امپراطوری:
TC_n= Cost(I_n )+ ۰.۱* Mean( cost(C_n))
شکل۳-۴ چگونگی شکل‌گیری جمعیت و امپراطوری‌های اولیه]۱۲[
۳-۱-۵-۲ سیاست جذب
سیاست جذب با اعمال می شود، به صورتی که کشور مستعمره به اندازه x واحد به سمت استعمارگر خود حرکت می کند. (x عددی تصادفی با توزیع یکنواخت می باشد و d فاصله بین استعمارگر و مستعمره است.)

۳-۱-۵-۳ انقلاب
در این مرحله مستعمرات با احتمال نرخ انقلاب (Prevolution=0.2) دچار انقلاب می شوند، به طوری که یک مستعمره به طور کامل یا با حفظ برخی ویژگی ها (به منظور حفظ تنوع و فرار از مینیمم های محلی) دچار دگرگونی می شود. شکل۳-۵ اعمال سیاست انقلاب را نشان می دهد.
شکل ۳-۵ اعمال سیاست انقلاب]۱۱[
با توجه به اعمال سیاست جذب و رخ دادن انقلاب ممکن است یک مستعمره در موقعیت بهتری از استعمارگر خود در تابع هزینه برسد، پس تابع هزینه جدید محاسبه می گردد و اگر مستعمره ای وجود داشت که هزینه اش از هزینه استعمارگر آن کمتر باشد، جای مستعمره و استعمارگر عوض می شود و قدرت کل امپراطوری جدید محاسبه می گردد. شکل ۳-۶ نشان دهنده حرکت مستعمره به سمت استعمارگر می باشد، شکل ۳-۷ تغییر جای استعمارگر و مستعمره و شکل ۳-۸ کل امپراطوری بعد از تغییر موقعیت ها را نشان می دهند.
شکل۳-۶ حرکت یک کشور مستعمره به سمت استعمارگر]۱۱[

شکل ۳-۷ تغییر جای استعمارگر و مستعمره]۱۱[
شکل ۳-۸ کل امپراطوری، پس از تغییر موقعیت‌ها]۱۱[

شکل ۲-۴ چگونگی شکل‌گیری امپراطوری‌های اولیه را نشان می‌دهد. همانگونه که در این شکل نشان داده شده است. امپراطوری‌های بزرگتر، تعداد بیشتری مستعمره دارند. در این شکل، امپریالست شماره ۱ قوی‌ترین امپراطوری را ایجاد کرده است و بیش‌ترین تعداد مستعمرات را دارد.
شکل۲-۴ چگونگی شکل‌گیری امپراطوری‌های اولیه]۱۲[
۲-۵-۱-۲ مدل‌سازی سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست
سیاست همگون‌سازی (جذب) با هدف تحلیل فرهنگ و ساختار اجتماعی مستعمرات در فرهنگ حکومت مرکزی انجام می‌گرفت. کشورهای استعمارگر، برای افزایش نفوذ خود، شروع به ایجاد عمران (ایجاد زیرساخت‌های حمل و نقل، تاسیس دانشگاه و …) کردند. به عنوان مثال کشورهایی نظیر انگلیس و فرانسه با تعقیب سیاست همگون‌سازی در مستعمرات خود در فکر ایجاد انگلیس نو و فرانسه نو در مستعمرات خویش بودند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسلئه بهینه‌سازی، در حقیقت این حکومت مرکزی با اعمال سیاست جذب سعی داشت تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی سیاسی به خود نزدیک کند. این بخش از فرایند استعمار در الگوریتم بهینه‌سازی، به صورت حرکت مستعمرات به سمت کشور امپریالیست، مدل شده است]۱۲.[

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

شکل ۲-۵، شمای کلی این حرکت را نشان می‌دهد.

شکل۲-۵ شمای کلی حرکت مستعمرات به سمت امپریالیست]۱۲[
مطابق این شکل کشور امپریالیست کشور مستعمره را در راستای محورهای فرهنگ و زبان به سمت خود جذب می‌کند. همانگونه که در این شکل نشان داده شده است، کشور مستعمره (Colony)، به اندازه واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعیت جدید(New Position of Colony) ، کشانده می‌شود. در این شکل، فاصله میان استعمارگر و مستعمره با نشان داده شده است. نیز عددی تصادفی با توزیع یکنواخت (و یا هر توزیع مناسب دیگر) می‌باشد. یعنی برای داریم]۱۳.[
(۲-۴)
که در آن عددی بزرگتر از یک و نزدیک به ۲ می‌باشد. یک انتخاب مناسب می‌تواند باشد. وجود ضریب باعث می‌شود تا کشور مستعمره در حین حرکت به سمت کشور استعمارگر، از جهت‌های مختلف به آن نزدیک شود.

شکل۲-۶ حرکت واقعی مستعمرات به سمت امپریالیست]۱۲[
با بررسی تاریخی پدیده همگون‌سازی، یک حقیقت آشکار در این زمینه این است که علی رغم اینکه کشوهای استعمارگر بطور جدی پیگیر سیاست جذب بودند، اما وقایع بطور کامل مطابق سیاست اعمال شده آنها پیش نمی‌رفت و انحرافاتی در نتیجه کار وجود داشت. در الگوریتم معرفی شده، این انحراف احتمالی با افزودن یک زاویه تصادفی به مسیر جذب مستعمرات، انجام می‌گیرد. بدین منظور، در حرکت مستعمرات به سمت استعمارگر، کمی زاویه تصادفی نیز به جهت حرکت مستعمره، اضافه می‌کنیم. شکل ۲-۶ این حالت را نشان می‌دهد. بدین منظور این‌بار به جای حرکت به اندازه ، به سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان میزان، ولی با انحراف در مسیر، به حرکت خود ادامه می‌دهیم. را به صورت تصادفی و با توزیع یکنواخت در نظر می‌گیریم (اما هر توزیع دلخواه و مناسب دیگر نیز می‌تواند استفاده شود)]۱۱.[
(۲-۵)
در این رابطه، پارامتری دلخواه می‌باشد که افزایش آن باعث افزایش جستجوی اطراف امپریالیست شده و کاهش آن نیز باعث می‌شود تا مستعمرات تا حد ممکن، به بردار واصل مستعمره به استعمارگر، نزدیک حرکت کنند. با در نظر گرفتن واحد رادیان برای ، عددی نزدیک به /۴π، در اکثر پیاده‌سازی ها، انتخاب مناسبی بوده است.
۲-۵-۱-۳ جابجایی موقعیت مستعمره و امپریالیست
سیاست جذب در عین نابودی ساختارهای اجتماعی سیاسی کشور مستعمره در بعضی موارد نتایج مثبتی را نیز برای آنها در پی داشت. بعضی از کشورها در نتیجه اعمال این سیاست، به نوعی از خود باوری عمومی دست یافتند و پس از مدتی همان تحصیل کرد‌گان (به عبارت دیگر جذب شدگان فرهنگ استعماری) بودند، که به رهبری ملت خود برای رهایی از چنگال استعمار پرداختند. نمونه های فراوانی از این موارد را می‌توان در مستعمرات انگلیس و فرانسه یافت. از سوی دیگر نگاهی به فراز و نشیب چرخش قدرت در کشور‌ها به خوبی نشان می‌دهد که کشور هایی که زمانی در اوج قدرت سیاسی – نظامی بودند، پس از مدتی سقوط کردند و در مقابل کشورهایی سکان قدرت را در دست گرفتند که زمانی هیچ قدرتی در دست نداشتند. در مدلسازی این واقعه تاریخی در الگوریتم معرفی شده به این صورت عمل شده است که در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن است بعضی از این مستعمرات به موقعیتی بهتر از امپریالیست برسند (به نقاطی در تابع هزینه برسند که هزینه کمتری را نسبت به مقدار تابع هزینه در موقعیت امپریالیست، تولید می‌کنند.) در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با همدیگر عوض کرده و الگوریتم با کشور استعمارگر در موقعیت جدید ادامه یافته و این بار، این کشور امپریالیست جدید است که شروع به اعمال سیاست همگون‌سازی بر مستعمرات خود می‌کند. تغییر جای استعمارگر و مستعمره، در شکل ۲-۷ نشان داده شده است. در این شکل، بهترین مستعمره‌ی امپراطوری، که هزینه‌ای کمتر از خود امپریالیست دارد، به رنگ تیره‌تر، نشان داده شده است. شکل ۲-۸، کل امپراطوری را پس از تغییر موقعیت‌ها، نشان می‌دهد]۱۱.[

شکل ۲-۷ تغییر جای استعمارگر و مستعمره]۱۱[
شکل ۲-۸ کل امپراطوری، پس از تغییر موقعیت‌ها]۱۱[

۲-۵-۱-۴ قدرت کل یک امپراطوری
قدرت یک امپراطوری برابر است با قدرت کشور استعمارگر، به اضافه درصدی از قدرت کل مستعمرات آن. بدین ترتیب برای هزینه کل یک امپراطوری داریم.
(۲-۶)
که در آن هزینه کل امپراطوری nام و عددی مثبت است که معمولا بین صفر و یک و نزدیک به صفر در نظر گرفته می‌شود. کوچک در نظر گرفتن ، باعث می‌شود که هزینه کل یک امپراطوری، تقریبأ برابر با هزینه حکومت مرکزی آن (کشور امپریالیست)، شود و افزایش نیز باعث افزایش تاثیر میزان هزینه مستعمرات یک امپراطوری در تعیین هزینه کل آن می‌شود. در حالت نوعی در اکثر پیاده‌سازی به جوابهای مطلوبی منجر شده است]۱۱.[
۲-۵-۱-۵ سیاست رقابت استعماری

۱

ولتاژ (V)

۷۵۰

۶۰۰

۷۲

۱۹

توان مصرفی (mW)

سیستمی که ما برای آن الگوریتم زمانبندی وظایف را پیشنهاد داده‌ایم، یک سیستم بی‌درنگ نرم می‌باشد، بنابراین مجموعه وظایفی که از آن‌ها برای پیاده‌سازی سیستم استفاده کرده‌ایم نیز وظایفی هستند که همگی دارای مشخصه بی‌درنگی نرم می‌باشند. همچنین از آنجایی که در یک سیستم تعبیه‌شده، مشخصه‌ های وظایف سیستم و تعداد آنها و بدترین حالت زمان اجرای هر وظیفه در بالاترین فرکانس ممکن، در مرحله پیکربندی اولیه سیستم مشخص شده و براساس آن سیستم زمانبندی می‌شود، در سیستم ما نیز مشخصه‌ های مانند تعداد کل وظایف سیستم، تعداد وظایف تناوبی و تعداد وظایف غیرتناوبی، زمان ورود هر وظیفه، سررسید متناظر هر وظیفه و… مشخص هستند. مشخصه‌ های ورودی مجموعه وظایف تناوبی در سیستم ما عبارت‌اند از : زمان ورود، سررسید متناظر، دوره تناوب و بدترین حالت زمان اجرا. اما مشخصه‌ های وظایف غیرتناوبی عبارت‌انداز: زمان ورود، سررسید متناظر، اولویت اجرا و بدترین حالت زمان اجرا. خروجی سیستم ما پس از توزیع وظایف بین هسته‌ها و زمانبندی آنها روی هر هسته مشخص می‌شود که شامل زمان پایان اجرای هر وظیفه، میزان نرخ از دست دادن سررسید وظایف، زمان اجرای نهایی یک وظیفه، زمان پاسخ وظایف غیرتناوبی، متوسط زمان انتظار وظایف غیرتناوبی و در نهایت میزان انرژی مصرفی هر وظیفه در طول اجرای آن‌ها روی هسته پردازنده می‌باشد.

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

از آنجاییکه مقادیر مشخصه‌ های وظایف سیستم بصورت تصادفی انتخاب می­شوند نیازمند اجرای تعداد وظایف زیادی هستیم تا به مقادیر واقعی و صحیح نزدیک باشیم. ما در شبیه‌سازی از شش مجموعه وظیفه متفاوت که در مجموع دارای تعداد ۱۸۷۰ وظیفه است استفاده کرده‌ایم که مجموعه وظیفه اول دارای تعداد ۲۰ وظیفه، مجموعه وظیفه دوم دارای تعداد ۵۰ وظیفه، مجموعه وظیفه سوم دارای تعداد ۱۰۰ وظیفه، مجموعه وظیفه چهارم دارای تعداد ۲۰۰ وظیفه، مجموعه وظیفه پنجم دارای تعداد ۵۰۰ وظیفه و مجموعه وظیفه ششم دارای تعداد ۱۰۰۰ وظیفه می‌باشد. همچنین نسبت تعداد وظایف تناوبی و غیرتنابی نیز در هر مجموعه وظیفه در چندین حالت‌ مختلف در نظر گرفته شده است. در سه مجموعه اول سه حالت و در سه مجموعه بعدی، پنج حالت مختلف برای نسبت وظایف تناوبی و غیرتناوبی در هر مجموعه وظیفه در نظر گرفته شده‌است. بنابراین بر اساس این حالت‌های مختلف نسبت وظایف تناوبی به غیرتناوبی، تعداد کل وظایفی که ما در شبیه‌سازی مورد آزمایش قرار می‌دهیم ۹۰۱۰ وظیفه می‌باشد.
ما در این شبیه‌سازی، هر کدام از حالت‌های مجموعه وظایف را برای پردازنده دوهسته‌ای، چهارهسته‌ای و هشت‌هسته‌ای آزمایش می‌کنیم. برای رسیدن به جواب دقیق‌تر و واقعی‌تر، ما هر حالت ممکن از مجموعه وظایف را به تعداد ۵۰۰ بار اجرا کرده و میانگین خروجی‌های این ۵۰۰ بار را به عنوان جواب نهایی سیستم در نظر گرفته‌ایم. در کنار توضیحات ذکرشده، برخی فرضیات نیز برای شبیه­سازی سیستم درنظر گرفته‌شده است که عبارتند از :

• ظرفیت صف آماده تمام هسته‌های پردازنده، بی‌نهایت درنظر گرفته شده است.

• تمامی وظایف ، مستقل هستند و هیچ ارتباط و اشتراک­گذاری و محدودیت منابع وجود ندارد.

• مقدار دوره تناوب هر وظیفه تناوبی با مقدار سررسید متناظر آن برابر است.

• مشخصه اولویت برای وظایف غیرتناوبی، یک عدد ثابت تصادفی غیرتکراری از یک تا تعداد وظایف غیرتناوبی یک مجموعه وظیفه می‌باشد.

• تمامی وظایف به محض ورود می­توانند اجرا شوند.

• سربار هسته سیستم­عامل، صفر فرض می­ شود.

۵-۲ محیط شبیه‌سازی
برای شبیه‌سازی سیستم موردنظر، می‌بایست به طور کامل یک سیستم بی‌درنگ چندهسته‌ای شبیه سازی شود. ما برای این کار از زبان برنامه‌نویسی python استفاده کردیم که دلیل انتخاب این زبان سادگی در استفاده و سرعت زیاد برنامه نویسی به این زبان بوده است.
لازمه شبیه‌سازی یک سیستم بی‌درنگ چندهسته‌ای این است که به طور کامل واحد پردازش داده‌ها که در اینجا، پردازنده چندهسته‌ای PowerPC 405PL می‌باشد، همراه با هسته سیستم‌عامل بی‌درنگ چندپردازنده، شبیه‌سازی شود. برای اینکار ما هسته‌های پردازنده موردنظر، سیستم‌عامل تعبیه‌شده بی‌درنگ، کلاک پردازنده و مشخصه‌ های وظایف موجود در سیستم را با زبان برنامه‌نویسی python و در محیط برنامه‌نویسی Pycharm شبیه‌سازی کرده ایم. در ادامه به شرح هرکدام از این قسمت‌ها خواهیم پرداخت.
شبیه‌سازی هسته‌ها:
برای شبیه‌سازی هسته‌های پردازنده، از کلاس Core در کد برنامه استفاده شده است. پس از انتساب وظیفه‌ها به هسته‌ها، هر هسته در صورتی که در کلاک زمانی خود روشن باشد و وظیفه ای برای اجرا کردن داشته باشد آن وظیفه را اجرا می‌کند. الگوریتم انتخاب وظیفه از صف وظیفه ها و انتخاب فرکانس در فصل قبل توضیح داده شده است. سپس با توجه به فرکانس و زمان اجرای وظیفه، انرژی مصرف شده توسط آن هسته محاسبه می شود. در صورتی که وظیفه‌ای برای اجرا کردن وجود نداشت این هسته به حالت خاموش می‌رود.
شبیه‌سازی کلاک:
در این آزمایش از پردازنده چندهسته‌ای PowerPC 405PL استفاده کرده ایم که هسته‌های آن در چهار فرکانس اجرایی مختلف کار می‌کنند و در هر لحظه فرکانس هر هسته مستقل از هسته دیگر است. فرکانس‌های این پردازنده ۳۳ ،۱۰۰ ،۲۶۶ و ۳۳۳ مگاهرتز است که برای ایجاد این فرکانس‌ها (رعایت نسبت ها)‌، ابتدا کوچک‌ترین مضرب مشترک آنها را محاسبه می‌کنیم، سپس کلاکی به اندازه این مقدار ایجاد می‌کنیم، سپس با توجه به نسبت فرکانس به کوچک‌ترین مضرب مشترک، محاسبات را انجام می‌دهیم. در روند اصلی برنامه کلاک شبیه‌سازی‌شده، به میزان کوچک‌ترین مضرب مشترک زده می شوند و در هر کلاک پردازنده وظایف مورد نظر را اجرا می کند. برای پیاده سازی صف های هر هسته، از صف اولویت دار با ساختمان داده heap استفاده شده است که زمان اضافه کردن عنصر و حذف کردن از آن و در نتیجه سربار الگوریتم را کاهش می‌دهد.
شبیه‌سازی سیستم‌عامل:
برای شبیه‌سازی سیستم‌عامل بی‌درنگ، از کلاس OS در کد برنامه استفاده شده‌ است. این کلاس وظیفه انتساب دادن وظایف به هسته‌ها را دارد. این کلاس صفی از وظیفه‌های تازه ساخته شده دارد که در هر بار اجرای این کلاس ابتدا این صف چک می شود و در صورتی که وظیفه‌ای در این صف بود آن را با الگوریتم پیشنهادی، به یکی از هسته‌های پردازنده انتساب می دهد.
شبیه‌سازی وظیفه:
برای شبیه‌سازی یک وظیفه، از کلاسی با نام Task در کد برنامه استفاده کرده‌ایم که این کلاس اطلاعات مربوط به هر وظیفه را در خود ذخیره می کند. ما تمامی وظیفه ها را در کلاس OS ذخیره می کنیم و پس از پایان ، با بررسی آنها از صحت اجرا و کارایی سیستم اطلاعات مورد نظر را بدست می آوریم.
۵-۳ ارزیابی انرژی مصرفی
مصرف انرژی یکی از مهم‌ترین مشخصه‌ ها برای یک سیستم تعبیه‌شده قابل حمل است. بدلیل محدودیت در منابع نگهدارنده انرژی، مخصوصا در سیستم‌هایی مانند تلفن همراه، مسئله کاهش مصرف انرژی از اهمیت زیادی برخوردار می‌باشد. الگوریتم پیشنهادی ما همواره سعی در این موضوع دارد که در عین اینکه کاهش نرخ نقض سررسید وظایف و زمان پاسخ وظایف غیرتناوبی را مد نظر دارد، باعث کاهش مصرف انرژی نیز شود. سطح اول الگوریتم پیشنهادی با تفکیک وظایف تناوبی و غیر تناوبی و تخصیص بخشی از هسته‌ها به آن‌ها سعی در رسیدن به اهداف ذکر شده را دارد. این اختصاص نسبت هسته باید با توجه به بهترین نتیجه حاصل از شبیه‌سازی باشد که به تعداد، نوع و مشخصه‌ های وظایف یک سیستم بی‌درنگ نرم تعبیه شده وابسته است.
ما در الگوریتم خود، برای هر مجموعه وظیفه، مشخص می‌کنیم که بهترین حالت نسبت هسته‌ها برای اختصاص به وظایف تناوبی و غیرتناوبی کدام است. شکل ۵-۱ انرژی مصرفی حاصل شبیه‌سازی ۵۰۰ وظیفه را نشان می‌دهد که برای انتخاب بهترین حالت نسبت تفکیک هسته‌ها در پردازنده‌های چهارهسته‌ای و هشت‌هسته‌ای، با توجه به مصرف انرژی هر حالت، بکار می‌رود. ما آزمایش‌های خود را برای هر حالت از هر مجموعه وظایف، پانصد مرتبه تکرار کرده و میانگین جواب‌های بدست آمده را در نمودار می‌آوریم.
شکل ۵-۱ مقایسه انرژی مصرفی حالت‌های مختلف نسبت تفکیک هسته‌ها برای وظایف تناوبی و غیرتناوبی
شکل ۳۲شکل ۵-۱ مقایسه انرژی مصرفی حالت‌های مختلف نسبت تفکیک هسته‌ها برای وظایف تناوبی و غیرتناوبی
این نمودار نشان می‌دهد که برای این مجموعه وظایف، در حالت چهار هسته‌ای، نسبت ۳ به ۱ ، کمترین میزان مصرف انرژی سیستم را به دنبال دارد، این بدین معنی است که در تفکیک هسته‌ها از بین سه حالت ممکن، یعنی نسبت ۳ به ۱، نسبت ۲ به ۲ و نسبت ۱ به ۳، اگر وظایف تناوبی را به سه هسته و وظایف غیرتناوبی را به یک هسته توزیع کنیم( با الگوریتم توزیع پیشنهادی که در فصل قبل بیان شد)، آنگاه کمترین میزان انرژی مصرف خواهد شد. همچنین در حالت پردازنده هشت هسته‌ای نیز مشاهده می‌کنیم که برای این مجموعه وظایف آزمایش شده، تفکیک ۲ به ۶ توانسته کمترین میزان مصرف انرژی را داشته باشد.
ما در آزمایشات شبیه سازی الگوریتم خود، برای هر حالت، تمامی نسبت‌های هسته‌ها را آزمایش کرده و بهترین جواب را استخراج نمودیم، بنابراین در نمودارهای بعدی هر حالت نشان داده شده از پردازنده چهارهسته‌ای و هشت‌هسته‌ای، بهترین جواب ممکن بوده است.
نتایج مصرف انرژی الگوریتم پیشنهادی، حاصل از شبیه‌سازی ۱۸۷۰ وظیفه در ۶ مجموعه مختلف از وظیفه‌ها با میانگین‌گیری پانصد تکرار، در حالت‌های دو هسته‌ای، چهارهسته‌ای و هشت‌هسته‌ای در شکل ۵-۲ نشان داده شده است.
شکل ۵-۲ انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف
شکل ۳۳شکل ۵-۲ انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف