CPU Scheduling

Kernel
تصمیم میگیره چی اجرا بشه
تا اینجا فهمیدیم چندین Process میتونن همزمان روی سیستم وجود داشته باشن
ولی یه سوال مهم داریم
اگه فقط یه CPU Core داشته باشیم و 10p تا Process آماده اجرا باشن
کدومشون باید CPU رو بگیره
اینجاست که CPU Scheduling وارد ماجرا میشه

Scheduler
توی Kernel بخشی وجود داره که وظیفه اش اینه تصمیم بگیره کدوم Process یا Thread برای اجرا انتخاب بشه

به این بخش میگیم
Scheduler
خیلی ساده

Ready Processes
│
├── Process A
├── Process B
├── Process C
└── Process D
│
▼
Scheduler
│
▼
CPU

Scheduler
در اصل داره جواب این سوال رو پیدا میکنه
الان چه چیزی باید روی CPU اجرا بشه

Ready Queue
Process
هایی که آماده اجرا هستن ولی فعلا CPU در اختیارشون نیست رو به صورت مفهومی داخل چیزی به اسم Ready Queue در نظر میگیریم

مثلا:

Ready Queue

┌─────────┐
│ Process A│
├─────────┤
│ Process B│
├─────────┤
│ Process C│
├─────────┤
│ Process D│
└─────────┘
│
▼
Scheduler
│
▼
CPU

البته توی سیستم عامل واقعی داستان خیلی پیچیده تر از یه صف ساده است

Scheduler
باید چیزهای مختلفی رو در نظر بگیره و ساختارهای داخلیش هم بسته به سیستم عامل و سیاست زمان بندی فرق میکنه
آیا یک Process میتونه برای همیشه CPU رو بگیره
فرض کنید یه برنامه داشته باشیم

while (1) {
// do something
}

این برنامه هیچ وقت تموم نمیشه
اگه سیستم عامل هیچ کنترلی روی CPU نداشت ممکن بود این Process تا مدت خیلی زیادی CPU رو اشغال کنه و برنامه های دیگه فرصت اجرا پیدا نکنن
برای همین سیستم عامل های مدرن از Preemptive Scheduling استفاده میکنن

Preemption
یعنی سیستم عامل بتونه اجرای واحد فعلی رو متوقف کنه و CPU رو به یه واحد دیگه بده

مثلا:

Process A
│
│ Running
▼
Scheduler تصمیم میگیرد
│
▼
Context Switch
│
▼
Process B
│
│ Running
▼

اینجا Process A لزوما تموم نشده
فقط فعلا CPU رو از دست داده
بعدا میتونه دوباره ادامه اجراش رو از همون جایی که متوقف شده دنبال کنه

Timer Interrupt
اینجا وارد میشه
یکی از چیزهایی که به سیستم عامل کمک میکنه کنترل CPU رو پس بگیره Timer هست
سیستم عامل یک Timer سخت افزاری رو تنظیم میکنه
بعد از گذشت یک بازه مشخص Timer میتونه یک Interrupt ایجاد کنه

به صورت ساده

CPU
│
│ اجرای Process A
│
▼
Timer
│
│ زمان تموم شد
▼
Interrupt
│
▼
Kernel
│
▼
Scheduler
│
▼
Process B

پس یه Process نمیتونه به سادگی بگه
CPU
مال منه و پسش نمیدم😁

Kernel
بالاخره میتونه وارد ماجرا بشه

Context Switch اینجا چه نقشی داره

یادتون هست قبلا گفتیم Context Switch یعنی وضعیت اجرای واحد فعلی ذخیره بشه و وضعیت واحد بعدی برای اجرا آماده بشه
حالا اینا رو کنار هم بذارید

Timer Interrupt
↓
Kernel
↓
Scheduler
↓
انتخاب واحد جدید
↓
Context Switch
↓
Thread یا Process Running جدید

این زنجیره یکی از پایه های مهم برای فهمیدن Scheduling هست

Scheduler
بر چه اساسی انتخاب میکنه
اینکه کدوم واحد اجرا بشه میتونه به سیاست ها و الگوریتم های مختلفی بستگی داشته باشه

چند نمونه کلاسیک رو ببینیم
FIFO یا FCFS

هر Process که زودتر وارد شده زودتر اجرا میشه

A → B → C → D

ساده است
ولی همیشه باعث بهترین عملکرد نمیشه

Shortest Job First
اگه مدت اجرای کارها رو بدونیم میتونیم کار کوتاه تر رو زودتر اجرا کنیم

مثلا:

A = 10ms
B = 2ms
C = 7ms

B → C → A

از نظر تئوری جالبه
ولی سیستم عامل معمولا از قبل دقیقا نمیدونه هر Process یا Thread قراره چقدر CPU مصرف کنه

Round Robin
اینجا هر واحد برای یه مقدار زمان مشخص CPU میگیره

مثلا

A → B → C → A → B → C

فرض کنید هرکدوم 10ms زمان داشته باشن

A 10ms
B 10ms
C 10ms
A 10ms
B 10ms

این مدل برای سیستم های تعاملی میتونه مناسب تر باشه

چرا Scheduling برای Reverse Engineering مهمه؟

وقتی دارید یه برنامه رو Debug میکنید ممکنه فکر کنید اجرای برنامه باید کاملا خطی باشه

مثلا

Instruction 1
Instruction 2
Instruction 3
Instruction 4

ولی سیستم عامل میتونه وسط اجرای اون Thread اجرای CPU رو ازش بگیره و واحد دیگه ای رو اجرا کنه

مثلا:

Thread A
│
├── Instruction 1
├── Instruction 2