سیستم عاملهای بلادرنگ Real time system با 6 وظیفه

طراحی و نوشتن الگوریتم‌های برنامه‌نویسی هم یکی از مهم‌ترین اهداف فرادرس برای آموزش و انتشار محتوی در کشور هستند. از طرف دیگر، محصلان علوم کامپیوتر با کمک این فیلم‌ها می‌توانند خود را برای آزمون‌های آکادمیکی مانند کنکور ارشد و دکتری نیز آماده کنند. SSTF این کار با با محاسبه کوتاه‌ترین مسیر جست‌وجو زودتر از زمان شروع به حرکت سر دیسک برای تمام درخواست‌های موجود در صف انجام می‌دهد. سپس درخواست‌ها را بر اساس زمان جست‌وجوی آن‌ها در جدول خودش مرتب می‌کند. اگرچه این روال کاری، انصاف را بین فرایند‌ها رعایت نمی‌کند، در نتیجه، ممکن است به دلیل به تاخیر انداختن‌های نامنظم برای اجرای درخواست‌ها منجر به بروز مشکلاتی شود.

توسعه‌دهندگان می‌توانند کتابخانه‌هایی از کامپوننت‌های عمومی و پرکاربرد ایجاد کنند که در پروژه‌های مختلف استفاده شوند. عبارت «بدترین حالت دیرکرد» (Worst Case Latency) برای بیشترین زمانی به‌کار می‌رود که برای اجرای همه وظایف لازم است. در نتیجه استفاده از زمان کوانتوم کمتر می‌تواند باعث بهبود زمان پاسخ‌گویی برنامه شود و با سرعت بیشتری به هر برنامه نوبت اجرا برسد. در فهرست زیر مهم‌ترین مشخصات الگوریتم زمان‌بندی راند رابین را ارائه داده‌ایم. اگرچه در همه موارد ممکن، شاید نتوان FIFO را به عنوان کارآمدترین الگوریتم در نظر گرفت، زیرا این الگوریتم دو مسئله مهم زیر را در نظر نمی‌گیرد.

به بیان ساده ‌تر اگر چندین فرایند با اهمیت یکسان وجود داشته باشد، فرایندی انتخاب می‌ شود که دارای زمان کمتری باشد. از ویژگی ‌های آن می ‌توان به حداقل تایم انتظار و برگشت اشاره کنیم. توجه کنید که الگوریتم‌ها همیشه با ساختمان داده به صورت درهم تنیده کار می‌کنند. یعنی در واقع نوشتن الگوریتم وابسته به ساختمان داده‌هایی است که برنامه‌نویس می‌تواند پیاده‌سازی و استفاده کند. در این بخش، فرایند کار الگوریتم RR را با کمک مثال بسیار ساده‌ای توضیح و به شکل مصور نمایش داده‌ایم. سیستم عامل برای پیاده‌سازی الگوریتم FIFO از ساختار صف در ساختمان داده برای نگهداری فرایند‌ها استفاده می‌کند.

اما برای درک انواع تکنیک‌های تعریف و بهینه‌سازی الگوریتم‌ها به طور کلی، لازم است که با چند مورد دیگر از الگوریتم‌های مدرن و پیش‌رفته‌ نیز آشنا شویم. این الگوریتم‌ها بر روی انواع سیستم‌های حال حاضر جهان در حال استفاده‌اند. درک روش صحیح تعریف و پیاده‌سازی چنین الگوریتم‌هایی در پیاده‌سازی الگوریتم‌های شخصی خودمان کمک بسیار زیادی می‌کند. در نهایت، میبینم که FIFO یکی از روش‌های ساده و منصفانه‌ای است که کامپیوتر برای ردگیری کارها استفاده می‌کند. مخصوصا کارهایی که در بخش‌های مختلف سیستم عامل باید به ترتیب اجرا شوند. در مثال‌های زیر، روش کار این الگوریتم را در بخش‌های مختلف سیستم عامل بیان کرده‌ایم.

الگوریتم کوتاه‌ترین زمان باقی‌مانده یا Shortest Remaining Time First یک الگوریتم غیرانحصاری بوده که ملاک انتخاب فرآیند را زمان باقی‌مانده‌ی اجرا در نظر گرفته است. اگر کارها به طور همزمان وارد سیستم شوند، میانگین زمان برگشت و زمان انتظار، حداقل خواهد بود. در الگوریتم انتخاب کوتاه‌ترین فرایند، فرآیندی برای پردازش انتخاب می‌شود که به کوتاه‌ترین زمان پردازش نیاز داشته باشد. در جدول زیر پردازش‌ها، زمان رسیدن، زمان اجرا و اولویت آن‌ها داده شده است. اگر کامپوننت‌ها دارای رابط کاربری هستند، این رابط‌ها باید ساده، قابل فهم و کاربرپسند باشند. از ابزارهای پروفایلینگ استفاده کنید تا بخش‌های کد که ممکن است باعث کاهش عملکرد شوند را شناسایی و بهینه کنید.

زبان برنامه‌نویسی پایتون یکی از ساده‌ترین و در عین حال قوی‌ترین زبان‌های برنامه‌نویسی سطح بالا است. این زبان امروزه توسط کاربران زیادی در اقصی نقاط جهان استفاده می‌شود. البته معمولا برای پیاده‌سازی الگوریتم‌های مرتبط با سخت‌افزار به صورت مستقیم از پایتون استفاده نمی‌کنند اما کاربردهای بسیار گسترده‌ای دارد. برای آشنایی با کاربرده‌های پایتون می‌توانید مطلب جامع و مفید کاربرد پایتون چیست؟ معرفی ۲۵ کاربرد کلیدی که باید بدانید همراه با مسیر یادگیری از مجله فرادرس را مطالعه کنید. در مطلب حاضر درباره یکی از الگوریتم‌های زمان‌بندی CPU صحبت کرده‌ایم.

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

بنابراین می‌توانیم الگوریتم FIFO را شبیه به الگوریتم «اولین ورودی، اولین خدمت رسانی شده» (FIRST COME, FIRST SERVE | FCFS) نیز بدانیم. در واقع حتی در بعضی از منابع از نام FCFS نیز برای این الگوریتم استفاده می‌شود. در این قسمت از مطلب، الگوریتم SJF در سیستم عامل را با استفاده از زبان برنامه نویسی جاوا کدنویسی کرده‌ایم. در مطلب حاضر درباره الگوریتم SJF برای زمان‌بندی CPU صحبت کرده‌ایم. اما نکته مهم این است که علاوه بر شناخت این الگوریتم‌ها باید نسبت به روش کلی طراحی و نوشتن الگوریتم‌ نیز آشنا باشیم.

می‌توان از الگوریتم SJF با هر دو رویکرد انحصاری و غیرانحصاری استفاده کرد. به الگوریتم SJF در حالت غیر انحصاری الگوریتم «اول کوتاه‌ترین زمان باقیمانده» (Shortest Remaining Time First | SRTF) نیز گفته می‌‌شود. برای پیدا کردن کمترین زمان تکمیل فعالیت در میان همه فرایند‌های رسیده به صف از «درخت‌ بازه‌ها» (Segment Trees) استفاده می‌شود. در این مثال، جدولی به شکل زیر شامل چهار فرایند مختلف داده شده است. این الگوریتم دارای ویژگی‌های خاصی است که باعث شده با بقیه تکنیک‌های زمان‌بندی به صورت واضح فرق داشته باشد. • هر پردازه بمنظور اجراء می بایست دارای حافظه مورد نیاز و اختصاصی خود باشد .

سایت‌های معتبری مانند freeCodeCamp و W3Schools منابع رایگانی برای یادگیری برنامه‌نویسی فراهم کرده‌اند. برای استفاده از هر الگوریتمی باید مزایا و معایب آن را در نظر گرفت و با سایر الگوریتم‌های موجود مقایسه کرد. در این صورت همیشه می‌توانیم بهترین گزینه‌ را برای پیاده‌سازی ساختار مورد نظر انتخاب کنیم. در این قسمت از مطلب، روش‌های پویا برای تخمین زمان تکمیل فرایند را به دو دسته مختلف تقسیم کرده‌ایم. در برخی کاربردها (مثل کنترل صنعتی)در کامپیوترها از سیستم عامل استفاده نمی‌شود. از آنجا که در سیستمهای کنترل صنعتی برنامه می‌بایست در اسرع وقت در مقابل یک اتفاق، از خود عکس العمل نشان دهد، وجود واسطه سیستم عامل باعث کند شدن مراحل می‌گردد.

این امر باعث می‌شود تا خطاها و مشکلات به راحتی شناسایی و برطرف شوند، بدون اینکه نیاز به بررسی کل سیستم باشد. اگرچه استفاده از کامپوننت در برنامه نویسی مزایای بسیاری دارد، اما معایب و چالش‌هایی نیز وجود دارد که باید به آنها توجه کرد. با استفاده از کامپوننت‌ها، تیم‌های توسعه می‌توانند به صورت همزمان روی بخش‌های مختلف برنامه کار کنند، بدون اینکه به یکدیگر وابسته باشند. این موضوع باعث افزایش سرعت توسعه و بهبود همکاری بین اعضای تیم می‌شود. با کمک فرمول بالا می‌توان زمان مورد نیاز «بدترین حالت تاخیر» اجرای فرایند‌ها توسط این عملکرد را بدست آورد.

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

این امر به این دلیل است که کاربران انتظار دارند سیستم به همه فرآیندها به طور عادلانه رسیدگی کند. زمان انتظار یک فرآیند مدت زمانی است که یک فرآیند منتظر است تا اجرا شود. الگوریتم‌های زمان‌بندی پردازنده ای که زمان انتظار کمتری برای فرآیندها ایجاد می کنند، مطلوب تر هستند. این امر به این دلیل است که فرآیندهایی که مدت زمان طولانی تری منتظر اجرا هستند، ممکن است عملکرد ضعیف تری داشته باشند. قحطی زدگی (Starvation) در الگوریتم‌های زمانبندی پردازنده به معنای این است که یک فرآیند به طور مداوم مورد تأخیر در اجرای الگوریتم قرار می‌گیرد و نمی‌تواند به موقع اجرای خود برسد.

اگر در این کاروان یکی از وسایل نقلیه با سرعت بسیار کندی حرکت کند، سایر وسایل نقلیه پشت سر آن نیز سرعت خود را از دست می‌دهند. در نتیجه بقیه کاروان هم باید با سرعت این وسیله حرکت کرده و سرعت کلی کاروان کاهش پیدا می‌کند. در تصویر زیر هم فرایندهای موجود در صف آماده دیده می‌شوند و هم نمودار Gantt را می‌تواند در زمان ۵ دید. در تصویر زیر می‌بینید که این فرایند هم به صف آماده اضافه شده و منتظر تکمیل کار فرایند‌های قبل از خودش می‌ماند. در مسائل مربوط به زمان‌بندی CPU، بعضی عبارت‌های تخصصی استفاده می‌شوند که برای درک مفهموم رفتار الگوریتم، لازم است با معنی این عبارات آشنا شویم. دراین نمودار، درخواست‌های موجود در صف این مثال با توجه به الگوریتم SSTF و طبق مراحل بالا مورد رسیدگی قرار گرفته‌اند.

در این اصل هر کس، مقدار مساوی از منابع را به نوبت در اختیار می‌گیرد. اصل راند رابین، قدیمی‌ترین و ساده‌ترین الگوریتمی است که برای مدیریت سامانه‌های «چند وظیفه‌ای» (Multi Task) به‌کار برده می‌شود. سپس هر قسمت را در صفی حلقه‌وار و بدون در نظر گرفتن هیچ اولویتی پردازش می‌کند. عبارت‌های «زمان کوانتوم» (Time Quantum) و «برش زمانی» (Time Slice) برای توزیع همه منابع به صورت مساوی استفاده می‌شوند. اگر از الگوریتم FIFO در سیستم عامل استفاده شود، در زمان اجرای فرایندهای گوناگون، اولین فرایندی که به صف اجرا رسیده قبل از دیگران برای اجرا به منبع مورد نظر، دسترسی پیدا می‌کند. صف اجرا به خطی از فرایندهای منتظر دریافت منابع برای اجرا شدن می‌گویند.

برای پیاده‌سازی و استفاده از الگوریتم SJF در سیستم عامل دو استراتژی بسیار رایج وجود دارد. «زمان مورد نیاز برای انجام فعالیت» (Turn-Around Time | TAT) به تفاوت بین زمان تکمیل فرایند (CT) و زمان رسیدن به صف اجرا (AT) گفته می‌‌شود. با کمک فرمول زیر می‌توان زمان مورد نیاز برای انجام فعالیت هر فرایند را محاسبه کرد. «اثر کاروان» (The Convoy Effect) یکی از نقاط ضعف این الگوریتم است. برای درک این مفهوم، موقعیتی از دنیای واقعی را در نظر بگیرید که کاروانی از وسایل نقیله در حال مسافرت با هم به صورت یک واحد منسجم و حتی به هم متصل هستند.

به مجموع تمام این زمان‌ها زمان انتظار فرآیند یا پردازش گفته می‌شود. پروژه‌ها می‌توانند به بخش‌های کوچکتر و مستقلی تقسیم شوند که هر یک وظیفه خاصی دارند. این امر باعث می‌شود که تیم‌های مختلف بتوانند به صورت موازی و بدون وابستگی شدید به یکدیگر کار کنند. با استفاده از کامپوننت‌ها، اعمال تغییرات و به‌روزرسانی‌ها در سیستم آسان‌تر می‌شود. اگر نیاز به تغییر در یک بخش از نرم‌افزار باشد، تنها کامپوننت مربوطه نیاز به تغییر دارد و این تغییرات به سادگی قابل اعمال هستند. در پروژه‌های بزرگ که چندین تیم بر روی بخش‌های مختلف کار می‌کنند، استفاده از کامپوننت‌ها باعث می‌شود تا هر تیم بتواند بر روی یک بخش خاص تمرکز کند.

طراحی و نوشتن الگوریتم‌های برنامه‌نویسی، یکی از اهداف مهم فرادرس برای آموزش و انتشار محتوی در کشور است. دانشجویان علوم کامپیوتر با کمک این فیلم‌ها می‌توانند خود را برای آزمون‌های دانشگاهی، مانند کنکور ارشد و دکتری آماده کنند. در ادامه این بخش، چند مورد از فیلم‌های آموزشی فرادرس درباره طراحی الگوریتم را معرفی کرده‌ایم. مخاطبان فرادرس، می‌توانند هر کدام از موارد پایین را انتخاب کرده یا با کلیک بر روی تصویر بالا به صفحه اصلی این مجموعه آموزشی هدایت شده و سایر فیلم‌ها را مشاهده کنند. الگوریتم SJF یک الگوریتم زمان بندی برای برنامه های کاربردی یا پروسه‌های سیستم عامل است که بر اساس طول زمان اجرای باقی‌مانده آن‌ها ترتیب اجرا را تعیین می‌کند.

همچنین ممکن است برخی الگوریتم‌ها، ترکیبی از این الگوریتم‌ها را برای بهبود عملکرد پردازنده استفاده کنند. این روش می‌تواند باعث استفاده ناکارآمد از CPU و همچنین دستگاه‌های ورودی/خروجی (I/O) شود. فرآیندهای I/O فرضی به سرعت پردازش شده و در انتظار رویدادهای I/O باقی خواهند ماند. در این لحظه اگر فرآیندهای پردازشی هم مسدود باشند، CPU بیکار می‌ماند. در صورتی یک الگوریتم‌ خوب است که بتواند باعث افزایش میزان بهره وری cpu  شود تا بتوانید در کمترین زمان به نتیجه دستیابید.

در این مثال ورودی های ما شامل نام فرایند ، زمان ورود و زمان اجرا بوده و خروجی مورد انتظار نیز نمودار گانت مربوط به زمانبندی کل پروسه ها توسط CPU می باشد. برای پیاده سازی این الگوریتم در زبان برنامه نویسی پایتون، می‌توانیم از یک لیست از دیکشنری‌ها برای نگهداری اطلاعات هر فرایند استفاده کنیم. در هر دیکشنری، سه کلید “name” (نام فرایند)، “arrival_time” (زمان ورود) و “burst_time” (زمان اجرا) برای نگهداری اطلاعات فرایند وجود دارد. سپس، با استفاده از تابع sorted و key، لیست فرایندها به ترتیب زمان اجرا مرتب می‌شود. در ادامه، با استفاده از یک حلقه، فرایندها به ترتیب زمان اجرا اجرا می‌شوند و نمودار گانت ساخته می‌شود.

بهترین روش برای ماندگاری یادگیری، تبدیل آن به بخشی از روتین روزانه است. زمانی ثابت، مثل صبح‌ها قبل از شروع روز یا عصرها بعد از کار، به یادگیری اختصاص دهید. حتی اگر فقط ۳۰ دقیقه باشد، این تداوم به‌مرور تاثیر عمیقی خواهد گذاشت. مطلب موجود در این صفحه صرفا یک رپورتاژ آگهی است و تمام محتوای آن توسط سفارش‌دهنده آگهی تهیه شده است. تک دیک هیچ‌گونه مسئولیتی پیرامون این مطلب و محتوای صفحاتی که به آن‌ها در این مطلب لینک داده شده است یا خدمات مرتبط با آن‌ها بر عهده نمی‌گیرد و آن‌ها را تأیید یا رد نمی‌کند.

به این صورت که اولین فرایند به صف وارد شده، باید اولین فرایندی هم باشد که اجرا شده یا از آن خارج می‌شود. در واقع اجرای فرایند‌ها با همان‌ ترتیبی است که به صف وارد شده‌اند. همین‌طور که در بخش‌های بالایی این مطلب اشاره شد، الگوریتم SJF یکی از چندین الگوریتم موجود برای زمان‌بندی انجام کارها در سیستم عامل است. هر کدام از این الگوریتم‌ها رویکردهای خاصی را برای پیاده‌سازی دنبال می‌کنند. به منظور آشنایی با انواع الگوریتم‌های زمان‌بندی در سیستم عامل می‌توانید مطلب راهنمای جامع الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل را از مجله فرادرس مطالعه کنید. در الگوریتم SJF (Shortest Job First)، فرایندی که کمترین زمان اجرای آن را دارد، اولویت بیشتری در برنامه ریزی دارد.

به همان ترتیبی که فرایند‌ها وارد صف ‌شده‌اند از آن خارج خواهند شد. نظم صف کاملا ثابت بوده و هیچ فرایندی خارج از نوبت خود به منبع مورد نیازش دسترسی پیدا نمی‌کند. فرایند‌ها از انتهای صف به آن افزوده شده و در جلوی صف از آن حذف می‌شوند. به این مراحل به ترتیب «نوبت‌گرفتن» (Enqueueing) و «خروج از صف» (Dequeuing) گفته می‌شود. در دنیای امروز، بسیاری از مسائل پیش آمده در مقابل توسعه انسان جنبه تکراری دارند.

الگوی جست‌وجو در الگوریتم زمان بندی SSTF به شدت وابسته به مکان قرارگیری «Head» است. این الگوریتم شبیه به الگوریتم SJF یا «اول کوتاه‌ترین کار» (Shortest Job First) عمل می‌کند. زیرا در زمان‌هایی که بار کاری سنگین است، شاید از اجرا شدن درخواست‌های دور جلوگیری کند. الگوریتم MLFQ معمولاً در سیستم‌های تک‌پردازنده‌ای که پردازنده نسبتاً کندی دارند، استفاده می‌شود. این الگوریتم می‌تواند انصاف را برای فرآیندهایی با اولویت‌های مختلف حفظ کند و زمان انتظار را برای همه فرآیندها کاهش دهد. در این الگوریتم‌ها یک فرآیند که در حال اجراست ممکن است توسط سیستم عامل متوقف‌شده و به حالت آماده منتقل شود.

در این وضعیت ممکن است وقت CPU از یک پردازش در حال اجرا توسط پردازش جدیدی که نیاز به زمان کمتری برای اجرا و تکمیل شدن دارد گرفته شود. یکی از کاربردهای این الگوریتم، مدیریت درخواست‌ها برای دسترسی به حافظه اصلی و حافظه مجازی صفحه‌بندی شده است. برای تسلط بر این مبحث پیشنهاد می‌کنیم که فیلم آموزش رایگان مدیریت دیسک در سیستم عامل را همراه با مرور اجمالی و تست کنکور از فرادرس مشاهده کنید. الگوریتم FIFO در سیستم عامل، یکی از الگوریتم‌های ساده و منصفانه‌ای است که دسترسی همه فرایند‌ها را به منابع مورد نیازشان تضمین می‌کند. با کمک این الگوریتم همه فرایند‌ها دارای فرصت برابر برای استفاده از منابع سیستم هستند.

جهت تخمین زمان فرآیند در الگوریتم SJF از فرمول زیر استفاده می‌کنیم.