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

بخشی از مقاله

خلاصه
زمان بندی CPU یک مفهوم کلیدی بسیار مهم در سیستم عامل است که در آن هدف زمانبندی و معیارهای مورد نظر مختلفی تاثیرگذار است.انتخاب و یا تغییر سیاست برنامه ریزی برای اجرای نخ ها بستگی به معیارها و اهداف خاص از پیش تعریف شده دارد.در این تحقیق ، به بررسی و مقایسه روش های زمانبندی که از تعدیل وزن نخ ها برای فرآیندهای چند نخی در سیستم عامل های چندپردازنده ای استفاده می کنند، پرداخته شده است. زمانبندی های بررسی شده از اشتراک CPU های سیستم استفاده می کنند که برای زمانبندی فرآیندهای چندنخی طراحی شده اند. در این مقاله یک الگوریتم جدید کاربردی به نام(TPFS) Two Phases Fair Scheduling زمانبند عادلانه ی دو فازی ارائه شده است که از مزایای الگوریتم های SPS و TWRS استفاده کرده و ایده ای جدید را به کار می برد.در الگوریتم جدید TPFS، علاوه بر تعداد پراسسورهای سیستم، تعداد نخ های هر فرآیند در سیاست زمانبندی، برای محاسبه وزن جدید و برش زمانی در نظر گرفته شده اند. الگوریتم جدید TPFS مانع استفاده بیش از حد از پراسسورها توسط برنامه های حریص می شود و زمان CPU ها را به صورت عادلانه بین نخ ها تقسیم می کند.
کلمات کلیدی: سیستم عامل های چند پردازنده ای ، زمان بندی ، چند نخی ، تعمیم وزن نخ ها ، لینوکس

.1 مقدمه
برای طراحی الگوریتم زمانبندی لازم است که ایده هایی از الگوریتم هایی با عملکرد خوب داشته باشیم.انتخاب یا تغییر سیاست های زمان بندی برای اجرای نخ ها به تعریف های قبلی و اهداف خاص و معیارها بستگی دارد. برخی از اهداف به محیط بستگی دارد که دسته ای ، تعاملی یا بلادرنگ باشد. البته در مورد برخی از اهداف همه معیارهای ذکر شده مهم هستند. برای سیستم های چندکاره هدف های مختلفی اعمال می شود.[7] یکی از مهمترین این اهداف بیشترین توان مفید می باشد.( برای مثال تعداد فرایندهایی که اجرای آنها در هر واحد زمان تکمیل شده است) در ماشین های دارایچند پردازنده ، فعالیت ها به طور همزمان به طور موازی در پردازنده های مختلف اجرا می شوند. در سیستم عامل های چندکاره دو حالت وجود دارد :
• چندکاره همیاری در این روش فرآیندها خود در رها کردن پردازنده با یکدیگر همکاری می کنند.
• چندکاره غیر انحصاری در این روش زمانبند تصمیم می گیرد که چه زمانی اجرای یک پروسه متوقف و به پروسه جدید اجازه اجرا دادهشود.به عملیات غیرعمدی تعلیق یک فرآیند در حال اجرا انحصار گفته می شود.به مدت زمانی که برای یک فرآیند قبل از تعلیق شدن تعیین می شود تا اجرا شود را برش زمان می گویند.هر برش زمانی اجازه ی استفاده از یک تکه از زمان CPU را برای اجرا شدن به فرآیند می دهد.
لینوکس مانند یونیکس یا مثل بیشتر سیستم عامل های مدرن دیگر از حالت چندکاره انحصاری تبعیت میکند. برای اجازه دادن به نخ های متعدد برای اجرای همزمان در یک پردازنده و اشتراک منابع ، تعیین زمان CPU در این مفهوم اخیر یک تکنیک معماری است که باعث بهبود بهره وری از منابع می شود.چندنخی همزمان یا SMT یکی از تکنیک های معماری است که مفهوم گسترده ای در سال های اخیر برای بهبود بهره وری از منابع داشته است.[1] معماری های SMT دستورالعمل ها را از چندین جریان از نخ های هر دوره اجرا می کنند تا موازی سازی سطح دستورات را بالا ببرند.[8,9,10] موازی سازی یکی از مهمترین مسائل در سیستم های چند هسته ای می باشد چون بیشترین کارایی را ارائه داده ، و محاسبات آینده در ماشین های چند هسته ای در حال پیشرفت می باشد. یکی از راه های کارآمد و مقیاس پذیر برای بهره مندی از معماری چند هسته ای استفاده از چند نخی است.چندنخی فرایندی از اجرای چندین نخ به طور همزمان روی هسته ها می باشد و یک برنامه نویسی گسترده و یک مدل اجرایی است که به چندین نخ اجازه می دهد که از مفهوم تک پراسسوری خارج شوند و منابع پراسسور را به اشتراک بگذارند به طوری که قادر به اجرا به صورت مستقل باشند. بیشتر نرم افزارهای کاربردی که روی کامپیوتر های مدرن اجرا می شوند چند نخی هستند.یک برنامه به صورت معمول به عنوان یک فرآیند جداگانه با چندین کنترل از نخ ها اجرا می شود.مزایای چندکاره multitasking بودن را می توان به صورت زیر بیان کرد :
• میزان پاسخ دهی
• اشتراک منابع
• اقتصادی
• مقیاس پذیری
در اینجا نیاز به الگوریتم زمانبندی مطرح می شود که شرایط لازم برای تمام سیستم های جدید که نیاز به خصوصیت چند وظیفه ای بودن( اجرای همزمان چند نخ یا فرآیند) و تسهیم multiplexing (انتقال جریان چندگانه به طور همزمان ) را دارا باشد. یک اصل مهم در طراحی الگوریتم های زمان بندی جداسازی سیاست از مکانیزم است.مکانیزم چگونگی نحوه انجام زمانبندی را نشان می دهد ولی سیاست آنچه را که باید انجام شود نشان می دهد.مثلا اینکه چگونه و به چه ترتیبی CPU به فرآیندی داده شود یک مکانیزم است ولی اینکه چه مدت زمانی از CPU داده شود یک سیاست محسوب می شود. بعضی مواقع است که یک پروسس چندین فرزند دارد و می تواند ایده جالبی باشد که ایده کاربران به آن داده شود و پروسسهای جدید به عنوان فرزندان برای انجام درخواستها و امور مختلف ایجاد شود. در این حالت پروسس اصلی می داند که کدام پروسس چه اولویتی دارد.در این موارد راه حل این است که مکانیزم زمانبندی از سیاست زمانبندی جدا باشد. مثلاالگوریتم زمانبندی پارامتر پذیر باشد ؛ اما پارامترها توسط پروسسهای کاربر مقداردهی شود. در مورد مثال پایگاه داده ها هسته ممکن است از الگوریتم اولویت دار استفاده کند ولی یک فراخوان سیستمی وجود داشته باشد که از طریق آن یک پروسس بتواند اولویت فرزندان خود را تعیین کند یا تغییر دهد . در اینجا مکانیزم در درون هسته است ، اما سیاست توسط کاربر تعیین می شود . پروسس پدر می تواند جزئیات چگونگی زمانبندی فرزندان خود را کنترل نماید ، اگر چه که خود او زمانبندی را انجام نمی دهد.
در ادامه ترتیب بخش های بعدی در این مقاله به صورت زیر خواهد بود : در بخش 1.2 در مورد انگیزه ی این تحقیق صحبت خواهیم کرد .در بخش 1.3 در مورد زمانبند کرنل لینوکس صحبت شده است، سپس در بخش 2 الگوریتم های زمانبندی بر پایه نسبت سهم معرفی و با یکدیگر مقایسه شده اند. در بخش 2.1 تعدیل وزن تعریف شده و در بخش 3 ایده ی اصلی الگوریتم جدید ارائه شده است. در بخش 3.1 نحوه ی محاسبه ی وزن جدید نخ ها در الگوریتم TPFS و در بخش 3.2 نحوه ی محاسبه ی برش زمانی در الگوریتم جدید و در آخر بخش 4 نتیجه گیری آمده است.

.1.1 انگیزه
در علم کامپیوتر الگوریتم زمانبندی روشی است که به وسیله ی آن به نخ ها ، فرایندها و جریان داده ، اجازه دسترسی به منابع داده می شود. زمانبندی اساس چند وظیفه ای در سیستم عاملی مثل لینوکس است.با تصمیم در مورد اینکه در نوبت بعد کدام فرآیند اجرا خواهد شد، زمانبند مسئول بهترین استفاده از سیستم و دادن این تصور به کاربران است که فرآیند ها به طور همزمان در حال اجرا است. مدیریت کردن برش زمانی، زمانبند را قادر می سازد که تصمیم گیری عمومی برای سیستم را انجام دهد.همچنین این مسئله مانع انحصار پردازنده توسط هر یک از فرآیند ها می شود.در بسیاری از سیستم عامل های مدرن برش زمانی به صورت پویا به عنوان تابعی از رفتار فرآیند و سیاست تنظیم سیستم محاسبه می شود. در حالت کلی الگوریتم های زمان بندی، در شکل کلی از نوع NP complete می باشد.( به عنوان مثال، اعتقاد بر این است که هیچ الگوریتم چند جمله ای بهینه برای آن وجود ندارد([12,13] بسیاری از تعریف هایی که برای زمانبندی کارا و خوب ارائه شده، منجر به وضعیت دادن وگرفتن منابع می شود که این مسئله کارایی را در جایی بهبود و در جای دیگر کاهش می دهد.در برخی از بهبودهایی که در زمانبند لینوکس انجام شده است، به کارایی کلی کمک می کند، اما چنین پیشرفت هایی سخت تر به دست آمده است . الگوریتم های زمانبندی پردازنده مختلف خصوصیات متفاوتی دارند و انتخاب یک الگوریتم خاص ممکن است به نفع یک کلاس از فرآیندها نسبت به فرآیندهای دیگر باشد.در انتخاب یک الگوریتم در یک وضعیت خاص، بایستی خصوصیات الگوریتم های مختلف را در نظر بگیریم. معیارهای زیادی برای مقایسه ی الگوریتم های زمانبندی پردازنده پیشنهاد شده است. ویژگی های موجود برای مقایسه، می تواند تفاوت های قابل توجهی را برای داوری بهتر انتخاب الگوریتم ها به ما ارائه دهد.این معیار عبارتند از: [14]
• بهره وری (utilization)
• توان عملیاتی (throughput)
• عدالت (fairness)
• زمان اجرا((execution time
• زمان چرخش((turnaround
• زمان انتظار((waiting time
هکرهای کرنل سعی کرده اند که الگوریتم های زمانبندی لینوکس را بهبود دهند، که این مسئله به این دلیل است که الگوریتم های زمان بندی لینوکس، جامع و به راحتی قابل درک است.[4] در این مقاله کارایی کرنل به شکل قابل توجهی توسط اصلاح چند پارامتر کلیدی، تغییر داده شده است.در این کار اثر تغییر وزن نخ های thread)sibling هایی که توسط یک فرآیند ایجاد شده اند) بررسی شده و این تغییر با توجه به معیارهای زمان انتظار، زمان چرخش و توان عملیاتی ارزیابی شده است.

.1.2 زمانبند کرنل لینوکس
یک نسخه از زمانبند لینوکس، با کرنل 2.4 توسعه یافته بود که O(N) نام داشت. این زمانبند هر یک از فرآیند ها را بررسی می کرد و به آن امتیازی میداد. فرآیندی که بیشترین امتیاز را به دست میآورد را برای اجرا انتخاب میکرد که مشکل این الگوریتم بالا بودن پیچیدگی آن بود . نسخه دیگری که برای کرنل 2.6 توسعه یافته است O(1) نام دارد که در آن دو آرایه به نام آرایه فعال و غیر فعال وجود دارد و به هر فرآیند یک برش زمانی ثابت داده می شود، پس از اتمام برش زمانی فرآیند به آرایه غیر فعال منتقل می شود. زمانی که همه فرآیندهایی که در آرایه ی فعال قرار دارند، برش زمانی خود را تمام کردند، به آرایه غیر فعال منتقل شده و یک جا به جایی (سوییچ) آرایه اتفاق می افتد.این سوییچ باعث می شودکه آرایه ی غیر فعال به آرایه ی فعال تبدیل شود.مشکل این الگوریتم در این است که فرآیندها را به دودسته تعاملی و غیرتعاملی تقسیم می کند و براساس این موضوع به آنها برش زمانی اختصاص می دهد که مشکل این زمانبند در این است که ممکن است زمانبند یک الگوریتم تعاملی را غیر تعاملی فرض کند و اولویت پایین تری به آن اختصاص دهد. هر آرایه در صف اجرا نشان دهنده ی 140 سطح اولویت مختلف است : از 0 (بیشترین) تا 99 (کمترین) از سیاست بلادرنگ استفاده می کنند. سطوح اولویت از 100 (بیشترین) تا 139 (کمترین) اشتراک زمانی فرآیندها تحت زمانبندی SCHED-NORMAL را ارائه می دهد.( شکل (1
زمانبند CFS لینوکس، از زمانبندی عادلانه thread، استفاده می کند.این الگوریتم منابع CPU را بر اساس تعداد نخ ها در سیستم و نه تعداد فرآیندهای که در حال اجرا هستند، اختصاص می دهد.در زمانبند کنونی CFS، وقتی که فرآیند جدیدی ایجاد می شود،به عنوان یک thread در نظر گرفته می شود به طوری که PID و TGID هر دو یک شماره است، همچنین وقتی یک نخ، نخ دیگری را شروع می کند، نخ جدید یک PID جدید می گیرد.(بنابراین زمانبند می تواند آن را به صورت مستقل زمانبندی کند) اما آن نخ شماره ی TGID خود را از والدین خود به ارث می برد.( شکل (1
در زمانبند CFS سعی شده نسبت به هر نوع فرآیند زمانبندی به صورت عادلانه انجام شود.این عمل با دادن یک مقدار عادلانه از زمان CPU به هر فرآیند به نسبت اولویت فرآیند ها، انجام می شود.یکی از تفاوت هایی که این زمانبند را از زمانبند های قبلی متمایز می کند، تنظیمات اولویت برای هر نخ است.در زمانبند CFS ، زمان اجرای هرنخ شمارش می شود و اولویت را به عنوان زمان اجرا مجازی (vruntime) محاسبه می کند. CFS بیشترین اولویت را به نخ هایی با کمترین vruntime می دهد . صف اجرا در CFS از درخت قرمز- سیاه استفاده می کند که در آن هر گره نشان دهنده ی یک نخ و مقدار هر گره نشان دهنده ی vruntime هر نخ است.( شکل (2
بنابراین زمانبند CFS بین نخ ها و فرآیندها تمایزی قائل نمی شود و به این صورت زمانبند کرنل می تواند به راحتی نخ را فارغ از اینکه به کدام فرآیند متعلق است، زمانبندی کند. به هر نخ ، وزنی اختصاص می یابد که سهم CPU آن نخ را مشخص می کند. ( شکل [6](3

.2 الگوریتم زمانبندی به نسبت سهم
یکی از روش های عادلانه برای زمانبندی دسترسی فرآیندها به پراسسور، دادن پراسسور به فرآیندها بر اساس وزن آنهاست الگوریتم های مختلفی مثل WFQ(weighted fair queuing) , SFQ( start-time fair [8] BVT queueing) ,از این روش استفاده کرده اند.در الگوریتم SFQ هر فرآیند دارای یک شمارنده به نام Si است که در زمانی که یک نخ از آن برنامه اجرا شد به مقدار q/wi به آن اضافه می شود.( q مدت زمان یک کوانتوم است) این روش ها در سیستم های چند پراسسوره دچار مشکل گرسنگی (starvation) می شوند. شکل 4 وجود این مشکل را نشان می دهد.[3]
زمانبندی از کمترین برچسب (start tag) شروع می شود.در ابتدا CPU1 به فرآیند A داده می شود و CPU2 به فرآیند B داده می شود وقتی در زمان 1000 ، C وارد می شود چون برچسب (10 ) کمتر نسبت به فرآیند B دارد، بنابراین CPU2 از فرآیند B گرفته شده و به فرآیند C داده می شود که همانطور که می بینید به گرسنگی فرآیند B ختم می شود.مشکل این نوع الگوریتم ها به دلیل اختصاص وزن های نامناسب به فرآیندهاست ، مثلا در نظر گرفتن وزن 1 و 100 برای دو CPU مناسب نیست.یکی از راه حل های ارائه شده برای حل این مشکل الگوریتم تعدیل وزن ها است.
.2.1 تعدیل وزن نخ ها
برای اختصاص وزن به فرآیندها بایستی محدودیتی در نظر گرفته شود و با توجه به آن محدودیت وزن به فرآیندها اختصاص یابد.می توان قبل از اختصاص وزن از معادله شماره 1 استفاده کرد :
هر فرآیند دارای یک شمارنده به نام Si است و در زمانی که یک نخ از آن برنامه اجرا شد به مقدار q/wi به Si اضافه می شود.( q مدت زمان یک کوانتوم است) به یک نخ با وزن wi به اندازه ی wi / wj (یعنی کسری از کل پهنای باند پردازنده) اختصاص می یابد.اگر درخواست وزن اختیاری باشد، ممکن است یک نخ درخواست پهنای باندی بیشتر از آنچه می تواند مصرف می کند را بدهد.[3]

الگوریتم SFS(Surplus Fair Scheduling) برای اختصاص وزن به فرآیندها از معادله شماره 1 استفاده می کند به طوری که در ابتدا وزن نخ ها به صورت نزولی در آرایه ای به نام w[ i ] مرتب می شود، سپس برای هر یک از نخ ها شرط 1 چک می شود، در صورتی که شرایط مورد نظر رعایت نشده باشد، تابع تعدیل وزن نخ ها (Readjust) صدا زده می شود.در این الگوریتم P تعداد پراسسورها و t تعداد نخ های آماده اجرا می باشد.(شکل (5

برای محاسبه ی حداقل زمان سرویس برای هر نخ (Surplus) از معادلات 2 و 3 و 4 استفاده می شود، که service i مدت زمان سرویس نخ i ام ، Service lagging کمترین مدت زمان سرویس برای هر نخ در زمان محدود و V کمترین برچسب شروع نخ های آماده اجرا می باشد.پس از محاسبه ی این مقادیر نخ ها بر اساس Surplus به صورت صعودی مرتب شده و سرویس می گیرند.

الگوریتم SFS الگوریتمی است که از روش تعدیل وزن ها استفاده کرده است و بر روی نسخه ی قدیمی لینوکس 2.2.14 اجرا شده است.

الگوریتم SFQ و SFS در [3] با یکدیگر مقایسه شده اند.این مقایسه نشان می دهد که استفاده از تعدیل وزن در الگوریتم SFQ منجر به کاهش مشکل گرسنگی فرآیندها می شود. ( شکل (6 و همچنین افزایش ورودی ها و خروجی ها مانع SFQ در تخصیص پهنای باند می شود در نسبت درخواست ها می شود ولی الگوریتم SFS در این شرایط دچار مشکل نمی شود و بهتر عمل می کند. ( شکل (7

الگوریتم دیگری به نام PFS (Proportional Fairness Algorithm) از روش تعدیل نخ ها در سیستم های چند پردازنده ای استفاده کرده است که در آن فرض شده که تعداد بهینه ی نخ ها ایجاد شده در برنامه، به منظور داشتن بهترین کارایی در یک محیط چند پردازشی،برابر تعداد هسته های موجود است. در الگوریتم PFS ، برش زمانی اختصاص داده شده به برنامه ها ی حریص برابر همان مقدار برش زمانی است که به فرآیندهای با تعداد نخ بهینه داده می شود. محدودیت این الگوریتم در این است که همه ی فرآیند با یک برش زمانی nice value یکسان اجرا می شوند. همه ی فرآیندهایی که دارای nice value مشابه هستند، بدون توجه به تعداد نخ ها ، برش زمانی مشابه دریافت می کنند. این مسئله باعث سربار در سیستم به خاطر context switching زیاد، در اجرای برنامه های حریص می شود. این محدودیت در یک الگوریتم جدید تر به نام TFPS رفع شده است. با توجه به اینکه در الگوریتم های PFS و TFPS به برنامه های چندنخی زمان زیادتری اختصاص نمی یابد، و این مسئله به این دلیل است که در PFS برش زمانی برنامه ی حریص برابر با برش زمانی است که به برنامه هایی که دارای نخ های کمتری هستند داده می شود. و در الگوریتم TFPS ، برش زمانی برنامه ی حریص برابر همان مقدار برش زمانی است که به فرآیندهای نخ بهینه داده می شود.[17]
در الگوریتم TWRS(Thread Weight Readjustment Scheduler) ایده اصلی الگوریتم شبیه الگوریتمPFS است. زمانبند TWRS یک زمانبند چند نخی در سطح کرنل می باشد، برای بالا بردن کارایی برنامه های چندنخی با تمرکز بر تطبیق دوباره ی وزن های برنامه های چندنخی مشتق شده (forked) از همان فرآیند است که به طور قابل توجهی به معیار زمانبندی بهتری منجر می شود.[5] همانطور که از اسم این زمانبند پیداست، این زمانبند به نسبت زمان توزیع CPU بین نخها ، بستگی دارد.در این الگوریتم به هر نخ یک وزن اختصاص می یابد که تعیین کننده ی سهم آن نخ، از پهنای باند CPU می باشد.سهمی که به نخ ها اختصاص می یابد، نسبتی از وزن آن نخ به جمع کل نخ های فعال در صف اجراست.این نسبت را می توان با معادله (5) نمایش داد.

Se ➔load.weight وزن نخ است، که از nice value به متغیر prio_to_weight نگاشت شده است.( که به عنوان یک متغیر در کتابخانه ی sched.c در کرنل تعیین شده است)[16] و هر nice value وزن مربوط به خود را دارد.

Cfs➔load.weight کل وزن های مربوط به نخ ها تحت الگوریتم cfs ، که در صف اجرا هستند می باشد.برش زمانی که یک نخ باید در یک دوره از زمان دریافت کند برابر است با :( معادله (6
Period مدت زمانی است که، زمانبند سعی می کند همه ی نخ ها را اجرا کند.که این مقدار به صورت پیش فرض برابر با 20ms می باشد.[2]
به صورت پیش فرض دو مقدار ثابت به صورت زیر تعیین شده اند [15]:
با توجه به مقادیر بالا تعداد فرآیندهایی که در 20ms می توانند اجرا شوند 20/4 یعنی، 5 فرآیند بود. اگر تعداد فرآیندهای قابل اجرا (n) از مقدار 5 تجاوز نکند، period همان مقدار 20 باقی می ماند، در غیر این صورت مقدار Period از الگوریتم 8 محاسبه خواهد شد.
تعداد کل نخ ها را درCPU و همچنین تعداد فرآیندهای fork شده از همان فرآیندها شمارش شده است، بنابراین وزن جدید برای نخ ها با توجه به معادله ی پایین محاسبه شده است:

در معادله ی 7، p->se.load.weight وزن کنونی نخ است و prcsr->totl_thrds تعداد کل نخ ها در CPU می باشد. و curr_proc ->nr_thrds تعداد کل نخ ها در آن فرآیند است. وزن دهی جدید به نخ ها باعث کاهش وزن نخ های متعلق به فرآیندهای حریص می شود.
یک مثال روشن از این الگوریتم در این قسمت ارائه شده است. در شکل 9 یک مثال روشن از توضیحات بالا ارائه شده است.یک صف اجرا از الگوریتم CFS نشان داده شده است.دایره ها در شکل نشان دهنده ی نخ هاست.رنگ قرمز و سیاه در درخت قرمز- سیاه نادیده گرفته شده است. نخ هایی که توسط یک فرآیند تولید شده اند را نخ های sibling گویند .ما در این مثال دو فرآیند A و B را فرض کرده ایم، فرآیند A دارای 5 نخ و فرآیند B دارای 2 نخ می باشد و همه ی نخ ها دارای
nice value صفر هستند و بنابراین وزن یکسان دارند.شماره مجازی) است و نخ ها در صف اجرا با توجه به مقدار vruntimeها در نخ ها نشان دهنده ی vruntime (زمان اجرای آن نخ، به صورت صعودی قرار گرفته شده است.[5]