پاورپوینت آشنایی با الگوریتم های زمانبندی

بخشی از پاورپوینت

اسلاید 1 :

آشنایی با الگوریتم های زمانبندی

اسلاید 2 :

فهرست مطالب

زمانبندی در سیستم های تک پردازنده
زمانبندی در سیستم های چند پردازنده
زمانبندی Task بر روی سیستم های چند پردازنده
List Scheduling
Clustering
Genetic Algorithms
Simulated Annealing
رقابت بر روی منابع ارتباطی
زمانبندی لینک
زمانبندی در پردازنده های چند هسته ای

اسلاید 3 :

زمانبندی در سیستم های تک پردازنده
بیشینه کردن میزان بهره گیری از پردازنده
جلوگیری از اتلاف زمان پردازنده به هنگام انجام عملیات ورودی/خروجی توسط برنامه های مختلف
ارائه چند برنامه ای
از میان پردازه های آماده اجرا در حافظه، یکی را برای اجرا بر روی پردازنده انتخاب می کند.

اسلاید 4 :

اهداف زمانبندی پردازنده
Utilization پردازنده- تا جای ممکن، پردازنده اشغال نگه داشته شود.
برون دهی- تعداد پردازه هایی که اجرای آنها در واحد زمان تکمیل می شود.
زمان turnaround- زمان سپری شده برای اجرای یک پردازه خاص
زمان انتظار- میزان زمان انتظار پردازه در صف برای دستیابی به پردازنده
زمان پاسخ- میزان زمان سپری شده از ارسال پردازه تا دریافت اولین پاسخ از پردازه

اسلاید 5 :

First Come First Served (FCFS)
ProcessBurst Time
P124
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:

Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17

اسلاید 6 :

Shortest-Job-First (SJF) Scheduling
به هر پردازه طول بازه زمانی بعدی که نیاز به پردازنده دارد را تخصیص می دهیم. پردازنده ابتدا به پردازه ای تخصیص می یابد که دارای کوتاهترین زمان بعدی باشد.
SJF از نظر میانگین زمان انتظار برای یک مجموعه از پردازه ها بهینه است.
مهم ترین چالش در این میان پیش بینی رفتار آینده پردازه ها می باشد.

اسلاید 7 :

زمانبندی بر اساس اولویت
به هر کدام از پردازه ها یک عدد اولویت، نسبت داده می شود.
هر پردازه ای که دارای اولویت بیشتری باشد، زود تر به پردازنده دست خواهد یافت.
SJF نوعی زمانبندی بر اساس اولویت می باشد.
امکان وقوع Starvation در این نوع از زمان بندی ها وجود دارد.
Aging

اسلاید 8 :

Round Robin (RR)
هر پردازه، به اندازه بازه زمانی معینی، پردازنده را در اختیار می گیرد و بعد از سپری شدن این بازه، پردازنده در اختیار پردازه دیگری قرار می گیرد.

اسلاید 9 :

Multilevel Queue

اسلاید 10 :

Multilevel Feedback Queues

اسلاید 11 :

زمانبندی در سیستم های چند پردازنده
مدل کردن برنامه ها با استفاده از گراف
گراف وابستگی
گراف جریان
گراف وظیفه

اسلاید 12 :

مدل کردن برنامه ها با استفاده از گراف
به هنگام مدل کردن یک برنامه با استفاده از گراف، دو فعالیت مهم در برنامه مد نظر قرار می گیرد.
محاسبات
ارتباطات
محاسبات با استفاده از گره های گراف نشان داده می شود.
ارتباطات با استفاده از یال های گراف نمایش داده می شوند.
هر گره در هر لحظه یا در گیر عملیات محاسباتی است و یا مشغول دریافت/ ارسال داده است.
هر گره تا زمانی که تمامی داده های مربوط به ورودی های آن آماده نباشند شروع به اجرا نمی کند.
تا زمانی که تمامی عملیات محاسباتی گره ها تمام نشده باشد، هیچ کدام از خروجی های مربوط به گره، ارسال نخواهند شد.

اسلاید 13 :

گراف وابستگی
یک گراف جهت دار است.
هر گره، نشان دهنده یک وظیفه می باشد.
هر یال، نشان دهنده وجود وابستگی میان گره ها می باشد.

اسلاید 14 :

گراف جریان
یک گراف جهت دار است که برای نمایش یک محاسبه تکراری مورد استفاده قرار می گیرد.
گره ها نشان دهنده محاسبات هستند.
یال ها نشان دهنده ارتباط میان هر کدام از وظیفه ها هستند.
هر کدام از یال ها می تواند با یک وزن غیر منفی که نشان دهنده تاخیر است، وزن دهی شود.

اسلاید 15 :

گراف وظیفه
یک گراف جهت دار بدون دور است.
G = (V, E, w, c)
V نشان دهنده وظایف موجود در یک برنامه است.
E نشان دهنده ارتباطات میان وظایف است.
w، نشان دهنده وزن محاسبات در یک گره است.
c، نشان دهنده وزن ارتباطات در یک لینک می باشد.

اسلاید 16 :

زمانبندی در سیستم های چند پردازنده

اسلاید 17 :

تعریف زمانبندی در سیستم های چند پردازنده
فرض کنید که مجموعه ای از وظیفه ها با قید های مربوط به ترتیب آنها با استفاده از یک گراف وظیفه مشخص شده باشد.
زمانبندی عبارت است از نسبت دهی زمانی و فضایی وظایف به پردازنده ها می باشد. در واقع، نسبت دهی فضایی وظایف، عبارت است از تخصیص وظایف به پردازنده ها می باشد.
تخصیص زمانی عبارت است از نسبت دهی زمان آغاز به هر کدام از وظایف می باشد.

اسلاید 18 :

منظور از سیستم چند پردازنده چه سیستمی است؟
سیستم پردازنده ای مورد اشاره در این بخش، سیستمی است که دارای مجموعه ای از پردازنده های مشابه (P) می باشد. هر کدام از پردازنده ها با استفاده از یک شبکه به سایر پردازنده ها متصل است. این سیستم دارای ویژگی های عمده زیر می باشد.
Dedicated system
Dedicated Processor
Cost Free Local Communication
Communication Subsystem
Concurrent Communication
Fully Connected

اسلاید 19 :

Feasible Schedule

اسلاید 20 :

Gantt Chart
یک روش گرافیکی برای نمایش یک زمانبندی است. که در آن هر کدام از اشیاء زمانبندی شده، به صورت یک مستطیل نشان داده می شود.
محل هر کدام از اشیا، بر اساس محور زمان و محور مکان (پردازنده) مشخص می شود.