Scheduling Metrics

از کجا بفهمیم Scheduler خوبه؟

توی قسمت قبل فهمیدیم Scheduler مسئول اینه که مشخص کنه کدوم Thread یا Process نوبتش بشه و روی CPU اجرا بشه

اما یه سؤال مهم داریم:

از کجا بفهمیم یک الگوریتم Scheduling واقعا خوبه؟

فرض کنید سه تا Process داریم:

A
B
C

Scheduler
میتونه این‌ها رو با ترتیب‌های مختلف اجرا کنه

پس باید یه سری معیار داشته باشیم تا بتونیم عملکرد الگوریتم‌های مختلف رو با هم مقایسه کنیم

اینجاست که میرسیم به Scheduling Metrics



Turnaround Time

اولین مفهوم:

Turnaround Time

به زبان ساده یعنی:

از لحظه‌ای که یک Job وارد سیستم میشه تا لحظه‌ای که کارش کاملا تموم میشه چقدر زمان گذشته؟

فرمولش:

Turnaround Time =

Completion Time - Arrival Time

مثلا:

Arrival Time = 0
Completion Time = 10

پس:

Turnaround Time = 10 - 0
= 10

یعنی این Process از لحظه ورود تا پایان 10 واحد زمانی داخل سیستم بوده



Waiting Time

حالا یه سؤال دیگه:

Process
چه مقدار از زمان رو فقط منتظر CPU بوده؟

اینجا میرسیم به:

Waiting Time

فرض کنید وضعیت یک Process این شکلی باشه:

Arrival
↓
Waiting
↓
Running
↓
Waiting
↓
Running
↓
Finished

هر مدتی که Process توی Ready Queue منتظر CPU باشه، جزو Waiting Time حساب میشه

پس خیلی ساده:

Waiting Time =
مدت زمانی که Process منتظر CPU بوده



Response Time

این یکی مخصوصا برای برنامه‌های تعاملی خیلی مهمه

Response Time
از وقتی Job وارد سیستم میشه تا اولین باری که CPU بهش میرسه چقدر طول کشیده؟

مثلا:

Arrival
│
│ 5ms
▼
First Run

پس:

Response Time = 5ms

حالا تفاوتش با Turnaround Time رو خوب دقت کنید

Response Time

فقط تا اولین اجرا:

Arrival → First Run

Turnaround Time

تا اخر کامل کار:

Arrival → Completion

پس ممکنه یک Process خیلی سریع اولین بار اجرا بشه ولی برای تمام شدن کارش مدت زیادی زمان لازم داشته باشه


یک مثال کامل

فرض کنیم سه تا Job داریم:

Job A
Arrival = 0
Runtime = 5

Job B
Arrival = 0
Runtime = 3

Job C
Arrival = 0
Runtime = 2

فرض کنیم Scheduler تصمیم گرفته این ترتیب رو اجرا کنه:

A → B → C

پس Timeline میشه:

0 5 8 10
|--------|--------|--------|
A B C

حالا یکی‌یکی حساب کنیم


Job A

A
از زمان:

0

شروع شده و در:

5

تموم شده

پس:

Turnaround = 5 - 0
= 5

چون A بلافاصله اجرا شده:

Response = 0



Job B

B
در زمان:

5

شروع شده و در:

8

تموم شده.

پس:

Turnaround = 8 - 0
= 8

و چون B از زمان 0 تا 5 منتظر CPU بوده:

Response = 5



Job C

C
در زمان:

8

شروع شده و در:

10

تموم شده

پس:

Turnaround = 10 - 0
= 10

و:

Response = 8

چون C تا زمان 8 منتظر مونده تا بالاخره CPU بهش برسه


میانگین هم مهمه

معمولا قرار نیست فقط یک Process رو بررسی کنیم

میخوایم ببینیم الگوریتم ما در مجموع چه عملکردی داشته

پس میانگین میگیریم

مثلا:

Turnaround:

A = 5
B = 8
C = 10

میانگین:

(5 + 8 + 10) / 3
= 7.67

پس:

Average Turnaround Time = 7.67

همین کار رو میتونیم برای معیارهای دیگه مثل Response Time هم انجام بدیم



مشکل یک Scheduler ساده

حالا یه حالت جالب‌تر رو ببین.

فرض کنید داریم:

A = 100ms
B = 2ms
C = 2ms

و Scheduler هم بگه:

A → B → C

Timeline
میشه:

0 100 102 104
|------------------------------|------|------|
A B C

یعنی B و C باید منتظر بمونن تا A کارش تموم بشه

در نتیجه:

Response Time B = 100ms
Response Time C = 102ms

در حالی که خود B و C فقط 2ms کار دارن

یعنی یه Job سنگین میتونه باعث بشه Jobهای کوچیک مدت زیادی منتظر بمونن



اینجا Shortest Job First جالب میشه

اگر از قبل بدونیم مدت اجرای Job ها تقریبا چقدره می‌تونیم اول Job های کوتاه‌تر رو اجرا کنیم

مثلا:

A = 100ms
B = 2ms
C = 2ms

پس به‌ جای:

A → B → C

میتونیم داشته باشیم:

B → C → A

Timeline:

0 2 4 104
|----|----|--------------------------------|
B C A

حالا B و C خیلی سریع اولین پاسخ خودشون رو میگیرن

این ایده پایه الگوریتم:

Shortest Job First (SJF)

هست


ولی اینجا یک مشکل داریم

سیستم‌عامل معمولا از قبل دقیقا نمیدونه:

این Process قراره چند میلی‌ثانیه CPU مصرف کنه؟

مثلا یک برنامه ممکنه مدام بین CPU و I/O جا به‌ جا بشه: