مقدمه ای بر سیستم عامل ها

هی هابر! من می خواهم توجه شما را به مجموعه ای از مقالات - ترجمه های یک ادبیات جالب به نظر من - OSTEP جلب کنم. این مطالب عمیقاً کار سیستم‌های عامل یونیکس مانند را مورد بحث قرار می‌دهد، یعنی کار با فرآیندها، زمان‌بندی‌های مختلف، حافظه و سایر اجزای مشابه که یک سیستم‌عامل مدرن را تشکیل می‌دهند. شما می توانید اصل تمام مواد را اینجا ببینید اینجا. لطفا توجه داشته باشید که ترجمه غیرحرفه ای (کاملا آزادانه) انجام شده است، اما امیدوارم معنی کلی را حفظ کرده باشم.

کارهای آزمایشگاهی در مورد این موضوع را می توان در اینجا یافت:

• اصل
• اصل
• سازگاری شخصی من

قسمت های دیگر:

• قسمت 1: مقدمه
• بخش 2: انتزاع: فرآیند
• قسمت 3: مقدمه ای بر Process API
• قسمت 4: مقدمه ای بر زمانبند

شما همچنین می توانید از کانال من دیدن کنید تلگرام =)

مقدمه ای بر زمانبند

ماهیت مشکل: چگونه یک خط مشی زمانبندی ایجاد کنیم
چارچوب های خط مشی زمانبندی اساسی چگونه باید طراحی شوند؟ مفروضات کلیدی چه باید باشد؟ چه معیارهایی مهم هستند؟ چه تکنیک های اساسی در سیستم های محاسباتی اولیه استفاده می شد؟

مفروضات حجم کار

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

بیایید مفروضات زیر را در مورد فرآیندهای در حال اجرا در سیستم، که گاهی اوقات نیز نامیده می شوند، انجام دهیم شغل ها (وظایف). تقریباً همه این مفروضات واقع بینانه نیستند، اما برای توسعه فکر ضروری هستند.

1. هر کار برای مدت زمان مشابهی اجرا می شود،
2. همه وظایف به طور همزمان تنظیم می شوند،
3. وظیفه محول شده تا تکمیل آن کار می کند،
4. همه وظایف فقط از CPU استفاده می کنند،
5. زمان اجرای هر کار مشخص است.

معیارهای زمانبندی

علاوه بر برخی مفروضات در مورد بار، ابزار دیگری برای مقایسه سیاست‌های زمان‌بندی مختلف مورد نیاز است: معیارهای زمان‌بندی. یک متریک فقط مقداری از چیزی است. تعدادی معیار وجود دارد که می توان از آنها برای مقایسه زمانبندی ها استفاده کرد.

به عنوان مثال، ما از یک متریک به نام استفاده خواهیم کرد زمان چرخش (زمان چرخش). زمان چرخش کار به عنوان تفاوت بین زمان اتمام کار و زمان رسیدن کار در سیستم تعریف می شود.

Tturnaround=Tcompletion−Tarrival

از آنجایی که فرض کردیم همه کارها همزمان می‌رسند، پس Ta=0 و بنابراین Tt=Tc. زمانی که مفروضات فوق را تغییر دهیم این مقدار به طور طبیعی تغییر می کند.

یک معیار دیگر - عدالت (انصاف، صداقت). بهره وری و انصاف اغلب ویژگی های متضاد در برنامه ریزی هستند. برای مثال، زمان‌بند ممکن است عملکرد را بهینه کند، اما به قیمت انتظار برای اجرای سایر وظایف، در نتیجه انصاف را کاهش می‌دهد.

FIRST IN FIRST OUT (FIFO)

ابتدایی ترین الگوریتمی که می توانیم پیاده سازی کنیم FIFO یا نام دارد اولین بار (ورود)، اولین خدمت (خروج). این الگوریتم چندین مزیت دارد: پیاده سازی آن بسیار آسان است و با تمام فرضیات ما مطابقت دارد و کار را به خوبی انجام می دهد.

بیایید به یک مثال ساده نگاه کنیم. فرض کنید 3 وظیفه به طور همزمان تنظیم شده است. اما بیایید فرض کنیم که کار A کمی زودتر از بقیه رسیده است، بنابراین در لیست اجرا زودتر از بقیه ظاهر می شود، درست مانند B نسبت به C. فرض کنید هر یک از آنها به مدت 10 ثانیه اجرا می شود. در این صورت میانگین زمان انجام این وظایف چقدر خواهد بود؟

با شمارش مقادیر - 10+20+30 و تقسیم بر 3، میانگین زمان اجرای برنامه برابر با 20 ثانیه به دست می آید.
حالا بیایید سعی کنیم فرضیات خود را تغییر دهیم. به طور خاص، فرض 1 و بنابراین دیگر فرض نخواهیم کرد که اجرای هر کار به زمان یکسانی نیاز دارد. FIFO این بار چگونه عمل خواهد کرد؟

همانطور که مشخص است، زمان های مختلف اجرای کار تأثیر بسیار منفی بر بهره وری الگوریتم FIFO دارند. بیایید فرض کنیم که کار A 100 ثانیه طول می کشد، در حالی که B و C هر کدام 10 ثانیه طول می کشد.

همانطور که از شکل مشخص است، میانگین زمان برای سیستم (100+110+120)/3=110 خواهد بود. این اثر نامیده می شود اثر کاروان، زمانی که برخی از مصرف کنندگان کوتاه مدت یک منبع پس از مصرف کننده سنگین صف می کشند. مثل صف خواربارفروشی است که مشتری با سبد خرید پر جلوی شماست. بهترین راه حل مشکل این است که سعی کنید صندوق را عوض کنید یا استراحت کنید و عمیق نفس بکشید.

کوتاه ترین کار اول

آیا می توان به نحوی یک وضعیت مشابه را با فرآیندهای سنگین حل کرد؟ قطعا. نوع دیگری از برنامه ریزی نامیده می شودکوتاه ترین کار اول (SJF). الگوریتم آن نیز کاملاً ابتدایی است - همانطور که از نام آن پیداست، کوتاه ترین کارها ابتدا یکی پس از دیگری راه اندازی می شوند.

در این مثال، نتیجه اجرای همان فرآیندها، بهبود میانگین زمان گردش برنامه خواهد بود و برابر با 50 به جای 110، که تقریبا 2 برابر بهتر است.

بنابراین، برای فرض داده شده که همه وظایف در یک زمان می رسند، به نظر می رسد الگوریتم SJF بهینه ترین الگوریتم باشد. با این حال، فرضیات ما هنوز واقعی به نظر نمی رسد. این بار فرض 2 را تغییر می دهیم و این بار تصور می کنیم که وظایف می توانند در هر زمانی وجود داشته باشند و نه همه به طور همزمان. این می تواند منجر به چه مشکلاتی شود؟

بیایید تصور کنیم که وظیفه A (100c) ابتدا می رسد و شروع به اجرا می کند. در t=10، وظایف B و C می رسند که هر کدام 10 ثانیه طول می کشد. بنابراین میانگین زمان اجرا (100+(110-10)+(120-10))3 = 103 است. زمانبندی برای بهبود این موضوع چه کاری می تواند انجام دهد؟

اول کوتاهترین زمان برای تکمیل (STCF)

به منظور بهبود وضعیت، فرض 3 را حذف می کنیم که برنامه راه اندازی شده و تا تکمیل اجرا می شود. علاوه بر این، ما به پشتیبانی سخت افزاری نیاز خواهیم داشت و همانطور که ممکن است حدس بزنید، از آن استفاده خواهیم کرد تایمر برای قطع کردن یک کار در حال اجرا و تغییر زمینه. بنابراین، زمان‌بندی‌کننده می‌تواند در لحظه رسیدن وظایف B، C کاری انجام دهد - اجرای وظیفه A را متوقف کند و وظایف B و C را در پردازش قرار دهد و پس از تکمیل آنها، اجرای فرآیند A را ادامه دهد. چنین زمان‌بندی نامیده می‌شود. STCFیا اول کار پیشگیرانه.

نتیجه این برنامه ریز نتیجه زیر خواهد بود: ((120-0)+(20-10)+(30-10))/3=50. بنابراین، چنین زمانبندی برای وظایف ما حتی بهینه تر می شود.

زمان پاسخ متریک

بنابراین، اگر زمان اجرای وظایف را بدانیم و این کارها فقط از CPU استفاده می کنند، STCF بهترین راه حل خواهد بود. و یک بار در زمان های اولیه، این الگوریتم ها به خوبی کار می کردند. با این حال، کاربر اکنون بیشتر وقت خود را در ترمینال می گذراند و انتظار یک تجربه تعاملی سازنده را دارد. بنابراین یک معیار جدید متولد شد - زمان پاسخ (واکنش).

زمان پاسخگویی به صورت زیر محاسبه می شود:

Tresponse=Tfirstrun−Tarrival

بنابراین، برای مثال قبلی، زمان پاسخ: A=0، B=0، C=10 (abg=3,33) خواهد بود.

و معلوم می شود که الگوریتم STCF در شرایطی که 3 کار به طور همزمان می رسند چندان خوب نیست - باید صبر کرد تا کارهای کوچک به طور کامل تکمیل شوند. بنابراین الگوریتم برای متریک زمان چرخش خوب است، اما برای متریک تعامل بد است. تصور کنید که در یک ترمینال نشسته اید و سعی می کنید کاراکترها را در یک ویرایشگر تایپ کنید و مجبور باشید بیش از 10 ثانیه منتظر بمانید زیرا کار دیگری در حال اشغال CPU است. زیاد خوشایند نیست

بنابراین ما با مشکل دیگری روبرو هستیم - چگونه می توانیم یک زمانبندی بسازیم که به زمان پاسخ حساس باشد؟

انجام مسابقه بنوبت

الگوریتمی برای حل این مشکل ایجاد شد انجام مسابقه بنوبت (RR). ایده اصلی بسیار ساده است: به جای اجرای وظایف تا زمانی که آنها کامل شوند، وظیفه را برای مدت زمان مشخصی اجرا می کنیم (به نام یک برش زمانی) و سپس به کار دیگری از صف تغییر می دهیم. الگوریتم کار خود را تکرار می کند تا زمانی که همه کارها تکمیل شوند. در این حالت زمان اجرای برنامه باید مضربی از زمانی باشد که پس از آن تایمر فرآیند را قطع می کند. به عنوان مثال، اگر یک تایمر یک فرآیند را هر x=10ms قطع کند، اندازه پنجره اجرای فرآیند باید مضربی از 10 باشد و 10,20،10 یا x*XNUMX باشد.

بیایید به یک مثال نگاه کنیم: وظایف ABC به طور همزمان وارد سیستم می شوند و هر یک از آنها می خواهند به مدت 5 ثانیه اجرا شوند. الگوریتم SJF هر کار را قبل از شروع کار دیگر کامل می کند. در مقابل، الگوریتم RR با یک پنجره راه اندازی = 1s وظایف را به صورت زیر انجام می دهد (شکل 4.3):

(دوباره SJF (برای زمان پاسخ بد)

(Round Robin (مناسب برای زمان پاسخگویی)

میانگین زمان پاسخ برای الگوریتم RR (0+1+2)/3=1 است، در حالی که برای SJF (0+5+10)/3=5 است.

منطقی است که فرض کنیم پنجره زمانی یک پارامتر بسیار مهم برای RR است؛ هر چه کوچکتر باشد، زمان پاسخ بیشتر است. با این حال، نباید آن را خیلی کوچک کنید، زیرا زمان تعویض متن نیز در عملکرد کلی نقش دارد. بنابراین، انتخاب زمان پنجره اجرا توسط معمار سیستم عامل تنظیم می شود و بستگی به وظایفی دارد که برای اجرا در آن برنامه ریزی شده است. تعویض متن تنها عملیات سرویسی نیست که زمان را هدر می دهد - برنامه در حال اجرا روی بسیاری از چیزهای دیگر مانند حافظه پنهان مختلف کار می کند و با هر سوئیچ لازم است این محیط ذخیره و بازیابی شود، که همچنین می تواند زمان زیادی را ببرد. زمان.

اگر فقط در مورد سنجه زمان پاسخ صحبت کنیم، RR یک زمانبندی عالی است. اما متریک زمان چرخش کار با این الگوریتم چگونه رفتار خواهد کرد؟ مثال بالا را در نظر بگیرید، زمانی که زمان عملیات A، B، C = 5s و در همان زمان می رسد. وظیفه A در 13، B در 14، C در 15 ثانیه به پایان می رسد و میانگین زمان چرخش 14 ثانیه خواهد بود. بنابراین، RR بدترین الگوریتم برای متریک گردش مالی است.

به عبارت کلی تر، هر الگوریتم نوع RR منصفانه است؛ زمان CPU را به طور مساوی بین تمام فرآیندها تقسیم می کند. و بنابراین، این معیارها دائماً با یکدیگر در تضاد هستند.

بنابراین، ما چندین الگوریتم متضاد داریم و در عین حال هنوز چندین فرض باقی مانده است - اینکه زمان کار مشخص است و این کار فقط از CPU استفاده می کند.

مخلوط کردن با I/O

اول از همه، اجازه دهید فرض 4 را حذف کنیم که فرآیند فقط از CPU استفاده می کند؛ طبیعتاً اینطور نیست و فرآیندها می توانند به تجهیزات دیگر دسترسی داشته باشند.

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

بیایید به مثالی از چندین مشکل نگاه کنیم. هر کدام از آنها به 50 میلی ثانیه زمان CPU نیاز دارند. با این حال، اولین مورد هر 10 میلی ثانیه به I/O دسترسی خواهد داشت (که هر 10 میلی ثانیه نیز اجرا می شود). و فرآیند B به سادگی از یک پردازنده 50 میلی‌ثانیه بدون I/O استفاده می‌کند.

در این مثال از زمانبندی STCF استفاده خواهیم کرد. اگر فرآیندی مانند A بر روی آن راه اندازی شود، زمانبند چگونه رفتار خواهد کرد؟ او کارهای زیر را انجام می دهد: ابتدا فرآیند A را کاملاً کار می کند و سپس B را پردازش می کند.

رویکرد سنتی برای حل این مشکل این است که هر 10 میلی‌ثانیه زیرکار فرآیند A را به عنوان یک کار جداگانه در نظر بگیریم. بنابراین، هنگام شروع با الگوریتم STJF، انتخاب بین یک کار 50 میلی ثانیه و یک وظیفه 10 میلی ثانیه واضح است. سپس، هنگامی که زیرکار A کامل شد، پردازش B و I/O راه اندازی می شوند. پس از اتمام ورودی/خروجی، مرسوم خواهد بود که به جای فرآیند B، فرآیند 10 میلی‌ثانیه A را دوباره شروع کنیم. به این ترتیب، می‌توان همپوشانی را پیاده‌سازی کرد، جایی که CPU توسط فرآیند دیگری استفاده می‌شود در حالی که اولین مورد منتظر است. I/O. و در نتیجه، سیستم بهتر مورد استفاده قرار می گیرد - در لحظه ای که فرآیندهای تعاملی منتظر I/O هستند، فرآیندهای دیگر را می توان روی پردازنده اجرا کرد.

اوراکل دیگر نیست

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

مجموع

ما به ایده‌های اساسی زمان‌بندی کار و 2 خانواده زمان‌بندی‌کننده نگاه کردیم. اولی کوتاه ترین کار را ابتدا شروع می کند و بنابراین زمان چرخش را افزایش می دهد، در حالی که دومی بین همه کارها به طور مساوی پاره می شود و زمان پاسخ را افزایش می دهد. هر دو الگوریتم در جایی که الگوریتم های خانواده دیگر خوب هستند بد هستند. ما همچنین بررسی کردیم که چگونه استفاده موازی از CPU و I/O می تواند عملکرد را بهبود بخشد، اما مشکل روشن بینی سیستم عامل را حل نکرد. و در درس بعدی به برنامه‌ریزی نگاه می‌کنیم که به گذشته نزدیک می‌نگرد و سعی می‌کند آینده را پیش‌بینی کند. و به آن صف بازخورد چند سطحی می گویند.

منبع: www.habr.com