مبانی (آشنایی با ویندوز قسمت دوم): Thread Scheduling

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

با این حال، چند سوال ممکن است پیش بیاید:

• هر نخ چه مدت زمان از پردازنده دریافت می‌کند؟

• اگر یک نخ جدید بیدار شود چه اتفاقی می‌افتد؟

• اگر تعداد نخ‌های آماده برای اجرا بیشتر از پردازنده‌های موجود باشد، چه می‌شود؟

در این بخش:

• اولویت‌ها (Priorities)

• مبانی زمان‌بندی (Scheduling Basics)

• زمان‌بندی چندپردازنده‌ای (Multiprocessor Scheduling)

• حالت پس‌زمینه (Background Mode)

• گروه‌های پردازنده (Processor Groups)

• توقف و از سرگیری اجرا (Suspending and Resuming)

اولویت‌ها (Priorities)
هر نخ دارای یک اولویت است، که اهمیت آن زمانی مشخص می‌شود که تعداد نخ‌هایی که قصد اجرا دارند بیشتر از تعداد پردازنده‌های موجود باشد. در این بخش، به اولویت‌های موجود و نحوهٔ تغییر آن‌ها می‌پردازیم و در بخش بعدی خواهیم دید که چگونه این اولویت‌ها در زمان‌بندی اعمال می‌شوند.

اولویت نخ‌ها از ۰ تا ۳۱ است، که ۳۱ بالاترین اولویت است. از نظر فنی، نخ ۰ به نخ ویژه‌ای به نام zero page thread اختصاص دارد که بخشی از Memory Manager در هسته (kernel) است. این تنها نخ است که می‌تواند اولویت صفر داشته باشد. بنابراین، اولویت‌های قابل استفاده عملاً از ۱ تا ۳۱ هستند.

در حالت user mode ، اولویت‌ها نمی‌توانند به‌طور دلخواه تنظیم شوند. در عوض، اولویت یک نخ ترکیبی است از Priority Class پردازه (که در Task Manager با نام Base Priority نمایش داده می‌شود) و یک offset اطراف این اولویت پایه. شکل 6-1 Task Manager را با ستون Base Priority برجسته نشان می‌دهد.

هر کلاس اولویت با یک مقدار اولویت مرتبط است که در جدول 6-1 نشان داده شده است.

نام «Real-time» در جدول 6-1 به این معنی نیست که ویندوز یک سیستم عامل زمان واقعی (real-time operating system) است؛ ویندوز چنین نیست. ویندوز نمی‌تواند تضمین‌های تأخیر و زمان‌بندی که سیستم‌عامل‌های زمان واقعی ارائه می‌دهند را فراهم کند. دلیل این امر این است که ویندوز با انواع مختلف سخت‌افزار کار می‌کند و بنابراین فراهم کردن چنین تضمین‌هایی زمانی که محدودهٔ سخت‌افزار محدود نیست، امکان‌پذیر نیست. اصطلاح «Real-time» در جدول 6-1 صرفاً به معنای «بالاتر از همهٔ سایر اولویت‌ها» است.

کلاس اولویت یک پردازه می‌تواند هنگام ایجاد آن پردازه با تابع CreateProcess تنظیم شود. پارامتر ششم (flags) می‌تواند با یکی از ثابت‌های جدول 6-1 ترکیب شود. اگر کلاس اولویت به‌طور صریح مشخص نشود، کلاس اولویت به صورت پیش‌فرض Normal خواهد بود، مگر اینکه کلاس اولویت ایجادکننده Idle یا Below Normal باشد، که در این صورت کلاس اولویت ایجادکننده استفاده می‌شود.

اگر پردازه‌ای از قبل وجود داشته باشد، تغییر کلاس اولویت با تابع SetPriorityClass امکان‌پذیر است:

BOOL SetPriorityClass(
  _In_ HANDLE hProcess,
  _In_ DWORD dwPriorityClass
);

Task Manager و همچنین Process Explorer یک منوی زمینه‌ای (context menu) ارائه می‌دهند تا کلاس اولویت یک پردازه را تغییر دهند.

برای موفقیت فراخوانی، هندل پردازه باید دارای PROCESS_SET_INFORMATION در ماسک دسترسی باشد. همچنین، اگر کلاس اولویت هدف Real-time باشد، فراخواننده باید امتیاز SeIncreaseBasePriority را داشته باشد. در غیر این صورت، تابع شکست نمی‌خورد، اما کلاس اولویت حاصل به جای Real-time روی High تنظیم می‌شود.

طبیعی است که تابع مخالف نیز وجود دارد تا کلاس اولویت یک پردازه را دریافت کند:

DWORD GetPriorityClass(_In_ HANDLE hProcess);

برای این تابع، ماسک دسترسی هندل تنها نیاز به PROCESS_QUERY_LIMITED_INFORMATION دارد، که تقریباً برای همهٔ پردازه‌ها قابل دریافت است.

کلاس اولویت پردازه تأثیر مستقیم بر خود پردازه ندارد، زیرا پردازه‌ها اجرا نمی‌شوند، بلکه نخ ها اجرا می‌شوند. همهٔ نخ ها ایجادشده در یک پردازه، اولویت پیش‌فرض خود را از سطح کلاس اولویت پردازه می‌گیرند. برای مثال، در یک پردازه با کلاس اولویت Normal، همهٔ رشته‌ها اولویت پیش‌فرض ۸ دارند.

برای تغییر اولویت یک نخ ، می‌توان از تابع SetThreadPriority استفاده کرد:

BOOL SetThreadPriority(
  _In_ HANDLE hThread,
  _In_ int nPriority
);

پارامتر nPriority یک مقدار اولویت مطلق نیست. بلکه یکی از هفت مقدار ممکن است (به جز کلاس اولویت Real-time) و در جدول 6-2 نشان داده شده است.

مقادیر Idle و Time Critical به عنوان مقادیر اشباع (Saturation values) شناخته می‌شوند.

ترکیب حاصل از کلاس اولویت پردازه و اولویت نسبی نخ، اولویت نهایی نخ را مشخص می‌کند. از دیدگاه زمان‌بند هسته (kernel scheduler)، تنها عدد نهایی اهمیت دارد و اینکه این عدد چگونه به دست آمده است برای آن اهمیتی ندارد. به‌عنوان مثال، اولویت ۸ می‌تواند به یکی از سه روش به دست آید:

• کلاس اولویت Normal با اولویت نسبی نخ Normal (0)

• کلاس اولویت Below Normal با بالاترین اولویت نسبی نخ (+2)

• کلاس اولویت Above Normal با پایین‌ترین اولویت نسبی نخ (-2)

از دیدگاه زمان‌بند، همهٔ این‌ها یکسان هستند؛ زمان‌بند به پردازه‌ها به طور کلی کاری ندارد، فقط نخ‌ها برایش مهم هستند.

دامنه اولویت Real-time (16-31) توسط بسیاری از نخ‌های هسته‌ای که کارهای حیاتی برای کل سیستم انجام می‌دهند استفاده می‌شود، بنابراین برای پردازه‌هایی که نخ‌هایشان در این دامنه اجرا می‌شوند مهم است که زمان CPU زیادی مصرف نکنند. البته، یک پردازه باید دلیل بسیار خوبی داشته باشد که نخ‌هایش در این دامنه قرار گیرند.

اگر به اولویت‌های نخ در ابزارهایی مانند Process Explorer نگاه کنیم، دو مقدار برای اولویت مشاهده می‌کنیم: Base Priority و Dynamic Priority (شکل 6-3).

Base Priority اولویتی است که توسط توسعه‌دهنده تعیین شده است (یا مقدار پیش‌فرض)، در حالی که Dynamic Priority اولویت واقعی و جاری آن نخ است. در برخی موارد، اولویت به‌طور موقت افزایش (boost) می‌یابد.از دیدگاه زمان‌بند (scheduler)، Dynamic Priority همان مقداری است که تعیین‌کننده اولویت نخ است.

رشته‌ها (Threads) در بازه Real-time هرگز اولویتشان افزایش (boost) نمی‌یابد.

مبانی زمان‌بندی (Scheduling Basics)
زمان‌بندی به‌طور کلی پیچیده است و عوامل متعددی را در نظر می‌گیرد که گاهی با یکدیگر در تضاد هستند: پردازنده‌های متعدد، مدیریت توان (تمایل به صرفه‌جویی در انرژی در یک سو و استفاده از تمام پردازنده‌ها در سوی دیگر)، معماری NUMA (Non-Uniform Memory Architecture)، Hyper-Threading، کش‌ها و موارد دیگر. الگوریتم‌های دقیق زمان‌بندی مستند نشده‌اند، زیرا مایکروسافت می‌تواند در نسخه‌ها و به‌روزرسانی‌های بعدی ویندوز تغییرات و اصلاحاتی ایجاد کند بدون اینکه توسعه‌دهندگان وابسته به جزئیات الگوریتم‌ها باشند. با این حال، می‌توان بسیاری از این الگوریتم‌ها را از طریق آزمایش و مشاهده تجربه کرد.

ما با ساده‌ترین حالت زمان‌بندی شروع می‌کنیم: سیستمی با یک پردازنده، زیرا این حالت پایهٔ عملکرد زمان‌بندی است. سپس به بررسی تغییرات الگوریتم‌ها در سیستم‌های چندپردازنده‌ای خواهیم پرداخت.

زمان‌بندی تک‌پردازنده (Single CPU Scheduling)
زمان‌بند یک صف آماده (Ready Queue) نگهداری می‌کند که در آن رشته‌هایی که آمادهٔ اجرا هستند (در وضعیت Ready) مدیریت می‌شوند. رشته‌های دیگر که در حال حاضر قصد اجرا ندارند (در وضعیت Wait) مورد توجه قرار نمی‌گیرند، زیرا تمایلی به اجرا ندارند.

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

ممکن است هزاران رشته در یک سیستم وجود داشته باشد، اما اکثر آن‌ها در وضعیت Wait قرار دارند و بنابراین توسط زمان‌بند در نظر گرفته نمی‌شوند.

الگوریتم زمان‌بندی برای یک پردازنده به این صورت است:

1. رشته با بالاترین اولویت ابتدا اجرا می‌شود. در شکل بالا ، رشته‌های ۱ و ۲ بالاترین اولویت (۳۱) را دارند، بنابراین اولین رشته در صف مربوط به اولویت ۳۱ اجرا می‌شود؛ فرض کنیم این رشته رشته ۱ باشد (شکل پایین).

نخ ۱ برای مدت زمانی مشخص اجرا می‌شود که به آن Quantum گفته می‌شود. فرض کنید نخ ۱ کارهای زیادی برای انجام دادن دارد؛ وقتی Quantum آن به پایان می‌رسد، زمان‌بند نخ ۱ را متوقف (preempt) می‌کند، وضعیت آن را در کُنش‌گر هسته (kernel stack) ذخیره می‌کند و رشته به وضعیت Ready بازمی‌گردد (زیرا هنوز کارهایی برای انجام دادن دارد).

اکنون رشته ۲ به دلیل داشتن همان اولویت، به عنوان رشته در حال اجرا انتخاب می‌شود (شکل زیر).

بنابراین، اولویت عامل تعیین‌کننده است. تا زمانی که رشته‌های ۱ و ۲ نیاز به اجرا داشته باشند، به صورت Round-Robin روی پردازنده اجرا می‌شوند و هر کدام برای یک Quantum زمان اجرا خواهند داشت. خوشبختانه، معمولاً نخ ها برای همیشه اجرا نمی‌شوند و در نقطه‌ای وارد وضعیت انتظار (Wait) می‌شوند.

چند نمونه که باعث می‌شوند یک نخ وارد وضعیت انتظار شود:

• انجام یک عملیات I/O همگام (synchronous)

• انتظار برای یک شیء هسته‌ای که در حال حاضر فعال نشده است

• انتظار برای یک پیام رابط کاربری (UI) زمانی که پیامی وجود ندارد

• ورود به حالت خواب داوطلبانه (voluntary sleep)

وقتی یک نخ وارد وضعیت انتظار می‌شود، از صف آماده زمان‌بند حذف می‌شود. فرض کنیم نخ های ۱ و ۲ وارد وضعیت انتظار شده‌اند. در این حالت، نخ ۳ با بالاترین اولویت، به عنوان رشته در حال اجرا انتخاب می‌شود (شکل زیر).

نخ ۳ برای یک Quantum اجرا می‌شود. اگر هنوز کار برای انجام دادن داشته باشد، یک Quantum دیگر دریافت می‌کند، زیرا تنها نخ در سطح اولویت خود است.

با این حال، اگر نخ ۱ نتیجه‌ای که منتظرش بود را دریافت کند، وارد وضعیت Ready می‌شود و نخ ۳ را پیش‌دستی (preempt) می‌کند، زیرا نخ ۱ اولویت بالاتری دارد و به عنوان نخ در حال اجرا انتخاب می‌شود. در این حالت، نخ ۳ به وضعیت Ready بازمی‌گردد (شکل زیر).

این تعویض در پایان Quantum نخ ۳ رخ نمی‌دهد، بلکه درست در لحظه تغییر (زمانی که نخ ۱ انتظار خود را به پایان می‌رساند) اتفاق می‌افتد. Quantum نخ ۳ دوباره پر می‌شود اگر اولویت آن بالاتر از ۱۵ باشد، که در این مثال همین‌طور است.

اگر اولویت رشته‌ای که پیش‌دستی (preempt) شده 16 یا بالاتر باشد، Quantum آن وقتی به وضعیت Ready بازمی‌گردد، دوباره پر می‌شود.

با توجه به این الگوریتم، نخ های۴، ۵ و ۶ هر کدام Quantum خود را اجرا خواهند کرد، به شرطی که هیچ رشته‌ای با اولویت بالاتر در وضعیت Ready نباشد.

این اساس زمان‌بندی است. در واقع، در یک سناریوی واقعی با یک پردازنده، این دقیقاً همان الگوریتمی است که استفاده می‌شود. با این حال، حتی در این حالت، ویندوز سعی می‌کند تا حدی «منصفانه» عمل کند. برای مثال، نخ ۷ در شکل‌های 6-4 تا 6-8 (با اولویت ۴) ممکن است اجرا نشود اگر نخ های با اولویت بالاتر در صف آماده باشند و بنابراین دچار گرسنگی پردازنده (CPU starvation) می‌شود. آیا این نخ در چنین سیستمی محکوم است؟ نه لزوماً؛ سیستم هر حدود ۴ ثانیه، اولویت نخ را تا ۱۵ افزایش می‌دهد و به آن شانس بهتری برای پیشرفت می‌دهد. این افزایش موقت اولویت تنها برای یک Quantum واقعی از اجرای نخ باقی می‌ماند و سپس اولویت به مقدار اولیه بازمی‌گردد. این فقط یک نمونه از افزایش موقت اولویت است.

Quantum

Quantum چندین بار در بخش قبل ذکر شد، اما طول آن چقدر است؟
زمان‌بند به دو روش مستقل عمل می‌کند:

1. با استفاده از یک تایمر که به‌طور پیش‌فرض هر ۱۵.۶۲۵ میلی‌ثانیه فعال می‌شود. این مقدار را می‌توان با فراخوانی GetSystemTimeAdjustment و بررسی آرگومان دوم آن به دست آورد.

2. استفاده از ابزار clockres از مجموعه SysInternals:

C:\Users\pavel>clockres
Clockres v2.1 - Clock resolution display utility
Copyright (C) 2016 Mark Russinovich
Sysinternals
Maximum timer interval: 15.625 ms
Minimum timer interval: 0.500 ms
Current timer interval: 1.000 ms

مقداری که در رابطه با Quantum باید به آن توجه کرد، Maximum timer interval است.

مقدار Current timer interval که توسط ابزار clockres نمایش داده می‌شود، نشان‌دهندهٔ فاصلهٔ زمانی فعلی فعال‌سازی تایمر است. این مقدار معمولاً کمتر از Maximum interval است، زیرا ممکن است تایمرهای چندرسانه‌ای (multimedia timers) درخواست شده باشند. این امکان را فراهم می‌کند که اطلاع‌رسانی‌های تایمر با دقت تا ۱ میلی‌ثانیه دریافت شود. با این حال، Quantum خود نخ تحت تأثیر Current timer interval قرار نمی‌گیرد.

Telegram: @CaKeegan
Gmail : amidgm2020@gmail.com