X
تبلیغات
الگوریتم - الگوریتم زمانبندی

الگوریتم زمانبندی HRRN

          زمانبندی Highest Response Ratio Next) HRRN) نوعی زمانبندی انحصاری است که بعضی از مشکلات SJF را برطرف می‌سازد. در SJF نظر افراطی خوبی نسبت به کارهای کوتاه و برعکس نظر افراطی بدی نسبت به کارهای طولانی وجود دارد به طوری که ممکن است مشکل قحطی زدگی رخ دهد. در این زمانبندی اولویت ها دینامیک است.
کارهای کوتاهتر اولویت بیشتری داشته و زودتر اجراء می‌شوند. کارهای طولانی نیز که مدت زیادی در صف انتظار بوده اند اولیت بیشتری کسب کرده وبالاخره در یک زمان معین اجراء می‌شوند. بدین ترتیب مشکل قحطی زدگی برطرف می‌شود.

 

فرمول تشخیص بالاترین پاسخ :  R=((w+s)/s)

  W=  زمان انتظار برای پردازنده

S   =  زمان خدمت مورد انتظار

R   = نسبت پاسخ

 

مثال)

 

 

حل:

علامت # تعداد اجراها

علامت -  تعداد انتظارها

فرایند های درخواست کننده در زمان 0:

P0

به دلیل اینکه فرآیندی با فرایند P0 در حال رقابت نیست پس بدون استفاده از فرمول (R=((w+s))/s) فرایند P0 تا آخر اجرا شده و تمام می شود.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

P1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

همانطور که مشاهده می کنید فرایند P1 در زمان 2 وارد شده و منتظر تمام شدن زمان اجرای P1 می باشد

به دلیل اینکه به جز فرایند P1  فرایند دیگری وارد صف نشده است پس فرایند P1 هم به صورتی که در شکل زیر نشان داده شده اجرا شده و تمام می شود

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

#

#

#

#

#

#

-

P1

 

 

 

 

 

 

 

 

 

 

 

 

 

-

-

-

-

-

P2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

-

-

P3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

P4

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

در این قسمت مشاهده می شود که سه تا فرایند P2,P3,P4 می خواهند اجرا شوند در این مرحله باید با استفاده از فرمول

 (R=((w+s))/s) فرایندی که بیشترین نسبت پاسخ(بیشترین مقدار R) را دارد را پیدا کنیم و آن فرایند از بین سه تا فرایند زودتر اجرا می  شود

حل:

P2:

 

W=5

S=4

          R=(w+s)/s è (5+4)/4 è R(P2)=2.25

P3:

 

W=3

S=5

          R=(w+s)/s è (3+5)/5 è R(P3)=1.6

P4:

 

W=1

S=2

          R=(w+s)/s è (1+2)/2 è R(P4)=1.5

 

همانطور که مشاهده می کنید فرایند P2 بیشترین نسبت پاسخ را دارد پس زود تر از همه اجرا می شود

 

 

 

دوباره نسبت پاسخ را بین دو فرایند باقیمانده(P3,P4) پیدا می کنیم

 

حل:

P3:

 

W=7

S=5

          R=(w+s)/s è (7+5)/5 è R(P3)=2.2

P4:

 

W=5

S=2

          R=(w+s)/s è (5+2)/2 è R(P4)=3.5

 

همانطور که ملاحظه می کنید فرایند P4 نسبت پاسخ بیشتری نسبت به فرایند P3 دارد وبه دلیل اینکه فرایند دیگری به جز این دو فرایند وجود ندارد اول فرایند P4 و سپس فرایند P3 به صورت زیر اجرا می شود.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

#

#

#

#

#

#

-

P1

 

 

 

 

 

 

 

 

 

#

#

#

#

-

-

-

-

-

P2

 

 

 

 

#

#

#

#

#

-

-

-

-

-

-

-

-

-

P3

 

 

 

 

 

 

 

 

 

 

 

#

#

-

-

-

-

-

P4

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

خصوصیات الگوریتم HRRN:

 

·        تابع انتخاب:max(w+s/s)

·        حالت تصمیم گیری: بدون قبضه کردن

·        توان عملیاتی: زیاد

·        زمان پاسخ: خوب

·        سربار: می تواند زیاد باشد

·        تاثیر بر روی فرآیند ها: توازن مناسب

·        گرسنگی: خیر

الگوریتم FeedBack (FB):

ااگر هیچ نشانه ای از طول نسبی فرایندها متفاوت نداشته باشیم هیچ یک از روشهای  HRRN ; SRT ; SPN را نمی توان بکار برد.

کار این الگوریتم به این صورت است که بر اساس قبضه کردن صورت می کیرد و از راهکار اولویت دهی پویا عمل می کند

هنگامی که فرایندی برای اولین بار می خواهد اجرا بشود وارد صف RQ0 می شود هنگامی که برای یک تایم زمانی مشخص شده اجرا می شود وبه حالت آماده باز می گردد وارد صف بعدی(RQ1) می شود و بدین ترتیب پس از هر بار اجرا شدن به صف بعدی (کم اولویت تر) انتقال میابد(مانند شکل زیر).

 

پردازنده

CPU

RQ0

RQ1

RQn

آزاد سازی

قبضه کردن

صف مسدود

 

 در این روش فرایند هایی که کوتاه هستند زود تر اجرا می شوند و بدون این که به صف های بعدی(کم اولویت تر) وارد شوند تمام می شوند فرایند هایی که زمان اجرای زیادی را دارند کم کم به صف های پایین تر منتقل می شوند در این صورت است که فرایند های کوچکتر زود تر از همه اتمام می شوند

در داخل هر صف به استثنای صف کمترین اولویت یک راهکار ساده Fifo به کار گرفته می شود وقتی فرایندی در صف کمترین اولویت قرار گرفت نمی تواند به صف بعدی برود پس فرایند تا آخر در همان صف اجرا شده و تمام می شود

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

 

RQ0

RQ1

RQn

 

پردازنده

CPU

آزاد سازی

 

پردازنده

CPU

آزاد سازی

 

پردازنده

CPU

آزاد سازی

فرایند زمانبندی شده برای RQ0 می تواند به اندازه یک واحد زمانی اجرا و سپس قبضه شود فرایند زمانبندی برای RQ1 میتواند به اندازه دو واحد زمانی اجرا شود وهمین طور برای صفهای دیگر. در حالت کلی یک فرایند زمانبندی شده برای Rqi مجاز است قبل از قبضه شدن به اندازه 2 به توان i واحد زمانی اجرا شود.

 

خصوصیات الگوریتم FB:

•       تابع انتخاب:  ------------

•       حالت تصمیم گیری: با قبضه کردن

•       توان عملیاتی: تاکید نشده است

•       زمان پاسخ: تاکید نشده است

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

•       تاثیر بر روی فرآیند ها: به نفع فرایند های در تنگنای I/O

•       گرسنگی: امکان دارد از طریق جریمه کردن کارهایی که زمان طولانی تری برای اجرا دارند.

 

+ نوشته شده توسط مهدی شعبانی در دوشنبه ششم اردیبهشت 1389 و ساعت 10:44 |


Powered By
BLOGFA.COM