دانلود تحقیق پردازشها

زمانبندی
در علم کامپیوتر، هسته (kernel) اساسی‌ترین بخش یک سیستم عامل است.

هسته سیستم عامل برنامه‌ای است که دسترسی ایمن به سخت‌افزار را برای برنامه‌های گوناگون فراهم می‌کند.

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

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

این مجرد‌سازی پیچیدگی‌های سخت‌افزاری را پنهان می‌کند و رابطی (Interface) ساده و یکنواخت برای سخت‌افزار فراهم می‌کند که استفاده از آن را برای برنامه‌نویسان آسان‌تر می‌کند.
برای اجرای یک برنامه بر روی کامپیوتر وجود هسته در سیستم عامل ضروری نیست.

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

اجرای برنامه‌ها بدون استفاده از سیستم عامل، در بسیاری از کامپیوترهای اولیه روش معمولی بوده است.

البته، در این روش برای اجرای برنامه‌های مختلف لازم بود که مجددا کامپیوتر راه‌اندازی (Reset) و برنامه بارگذاری شود.

سرانجام برای رفع این مشکل برنامه‌های کمکی کوچکی مثل loaderها و debuggerها ایجاد شدند، که حین اجرای برنامه‌های مختلف در حافظه باقی‌می‌ماندند یا از حافظه ROM بارگذاری می‌شدند.

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

1.

هسته یکپارچه (Monolithic)، که انتزاع (abstraction) [1] سخت‌افزاری نیرومندی را فراهم می‌آورد.
2.

ریزهسته (Microkernel)، که مجموعه‌ای کوچک از انتزاع ساده سخت‌افزاری را به وجود می‌آورد و از نرم‌افزارهایی با نام سرویس‌دهنده (Server) استفاده می‌کنند تا قابلیت بیشتری را ارایه دهند.
3.

هسته دورگه (Hybrid) یا ریزهسته اصلاح شده، که شباهت زیادی به ریزهسته‌ دارد، با این تفاوت که به منظور اجرای سریع‌تر، شامل کدهایی اضافی در فضای هسته می‌باشد.
4.

برون‌هسته (Exokernel)، که هیچ گونه انتزاعی را فراهم نمی‌کنند، ولی با استفاده از کتابخانه‌ای از توابع (libraries) برای افزایش کارایی، دسترسی مستقیم یا نیمه‌مستقیم به سخت‌افزار را فراهم می‌کنند.

هسته یکپارچه (Monolithic)

هسته یکپارچه (Monolithic)، یک رابط مجازی سطح بالا بر روی سخت‌افزار تعریف می‌کند.

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

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

چرا که در غیر این صورت، برتری اندکی نسب به ریزهسته‌ها خواهند داشت.

سیستم‌های عامل Linux و Unix را می‌توان جزو پیشرفته‌ترین هسته‌های یکپارچه دانست
زمانبندی نوبت گردشی
این زمانبندی یکی از قدیمیم ترین , ساده ترین , عادلانه ترین و رایجترین الگوریتم های زمانبندی است و از نوع غیر انحصاری (preemptive) می‌باشد.

این الگوریتم شبیه FCFS است ولی به هر پردازش حداکثر به میزان زمانی مشخصی CPU داده می‌شود.

به عبارتی دیگر یک واحد کوچک زمانی به نام کوانتوم زمانی (time quantum) با برش زمانی (time slice) تعریف می‌شود که معمولاً بین 10 تا 100میلی ثانیه است و هر پروسس حداکثر به این میزان می‌تواند CPU را در اختیار بگیرد.

هنگامی که پردازشی CPU را در اختیار دارد دوحالت ممکن است رخ دهد .

یا انفجار محاسباتی جاری کمتر از یک کوانتوم زمانی است که در این حالت پردازش داوطلبانه CPU را رها می‌کند و منتظر اتمام عملیات I/O می‌شود (مانند FCFS) و یا اینکه انفجار محاسباتی بیشتر از یک کوانتوم زمانی است که در این حالت تایمر یک وقفه به سیستم عامل می‌دهد و سیستم عامل با تعویض متن (Context switch) CPU را از پردازش جاری گرفته و آن را به ته صفآماده می‌فرستد, سپس از ابتدای صف آماده, پردازش دیگری را جهت اجرا انتخاب می‌کند :


از این روش در سیستمهای اشتراک زمانی استفاده شده تا زمانهای پاسخ برای کاربران محاوره‌ای بصورت مناسب گارانتی شود.
این زمانبندی یکی از قدیمیم ترین , ساده ترین , عادلانه ترین و رایجترین الگوریتم های زمانبندی است و از نوع غیر انحصاری (preemptive) می‌باشد.

این الگوریتم شبیه FCFS است ولی به هر پردازش حداکثر به میزان زمانی مشخصی CPU داده می‌شود.

به عبارتی دیگر یک واحد کوچک زمانی به نام کوانتوم زمانی (time quantum) با برش زمانی (time slice) تعریف می‌شود که معمولاً بین 10 تا 100میلی ثانیه است و هر پروسس حداکثر به این میزان می‌تواند CPU را در اختیار بگیرد.

هنگامی که پردازشی CPU را در اختیار دارد دوحالت ممکن است رخ دهد .

یا انفجار محاسباتی جاری کمتر از یک کوانتوم زمانی است که در این حالت پردازش داوطلبانه CPU را رها می‌کند و منتظر اتمام عملیات I/O می‌شود (مانند FCFS) و یا اینکه انفجار محاسباتی بیشتر از یک کوانتوم زمانی است که در این حالت تایمر یک وقفه به سیستم عامل می‌دهد و سیستم عامل با تعویض متن (Context switch) CPU را از پردازش جاری گرفته و آن را به ته صفآماده می‌فرستد, سپس از ابتدای صف آماده, پردازش دیگری را جهت اجرا انتخاب می‌کند : از این روش در سیستمهای اشتراک زمانی استفاده شده تا زمانهای پاسخ برای کاربران محاوره‌ای بصورت مناسب گارانتی شود.

حد بالای کوانتوم زمانی بایدبه قدری باشد که زمان پاسخ دهی مناسبی داشته باشیم.

حد پایین برش زمانی توسط دو عامل تعیین می‌شود یکی اینکه باید این برش خیلی بزرگتر از زمان تعویض متن باشد مثلاً هزاران برابر.

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

یک قاعده سرانگشتی این است که go درصد انفجارهای محاسباتی باید کوتاه‌تر از کوانتوم زمانی باشند و در عمل برا یاین امر برش زمانی را حدود 100 میلی ثانیه در نظر می‌گیرند انواع زمانبند ها در سیستم عامل از یک جنبه زمانبندهای پردازش در سیستم عامل به سه دسته الف- دراز مدت (Long term scheduler) ب– کوتاه مدت(Short term scheduler) ج – میان مدت, تقسیم بندی می‌شوند.

در یک سیستم دسته‌ای پردازشهای بیشتری نسبت به آنچه فوراً می‌توانند اجرا شوند تحویل داده می‌شوند .

این پردازشها در دیسک نگهداری می‌شوند .زمانبندی دراز مدت (یازمانبندی کار sheduler Job )پروسسهایی را انتخاب کرده و آنها را برای اجرا از دیسک به حافظه اصلی می‌آورد.

زمانبند کوتاه مدت (یا زمانبند CPU) از بین پروسسهای موجود در حافظه اصلی که آماده اجرا هستند یک را انتخاب کرده و CPU را به آن اختصاص می‌دهد.

غالبا زمانبند کوتاه مدت هر صد میلی ثانیه یک بار اجراء می‌شود ولی زمانبند دراز مدت ممکن است هر چند دقیقه یک بار اجرا شود.

در واقع زمانبند دراز مدت در جه چند برنامگی (degree of multiprogramming) یعنی تعداد پردازشهای موجود در حافظه را کنترل می‌کند .

زمانبند دراز مدت وقت زایدی برای تصمیم گیری دارد ولی زمانبند کوتاه مدت می‌بایست خیلی سریع تصمیمی گیری کند.

زمانبند دراز مدت می‌بایست مخلوط مناسبی از پردازشهای CPU-limiter و I/O limited را جهت قرار گیری در حافظه انتخاب کند تا کارایی CPU و وسایل I/O بهینه شود.

در بعضی سیستمها مثل اغلب سیستم های اشتراک زمانی زمانبند دراز مدت وجود ندارد, چرا که هر پردازش در سیستم عامل جدید جهت زمانبند CPU در حافظه گذاشته می‌شود تا زمان پاسخ دهی به برنامه مناسب باشد.

البته بعضی سیستم عاملها از زمانبند میان مدت نیز استفاده می‌کنند.

بدین ترتیب که گاهی پروسس هایی از حافظه و در واقع از رقابت جهت دریافت CPU حذف شده و به دیسک برده می‌شوند (swap Out) .بدین ترتیب درجه چند برنامگی کاهش می‌یابد .

سپس در زمانی دیگر پردازش در سیستم عامل مذکور مجددا به حافظه آورده شده (swap in) و اجرایش از همان نقطه قبلی ادامه می‌یابد, این عملیات به نام مبادله (swapping)معروف است .

زمانبندی CPU به طوری کلی می تواند انحصاری (غیر قابل پس گرفتن non preemptive) یا غیر انحصاری (قابل پس گرفتن preemptive) باشد.

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

بنابراین مفهوم و پیاده سازی الگوریتم زمانبندی انحصاری ساده است .ولی ممکن است پردازشی برای مدت طولانی CPU را جهت محاسبات در اختیار بگیرد.

رد این حال پردازشهای دیگر برای مدتی طولانی انتظار خواهند کشید و این موضوع مخصوصاً برای سیستم‌های اشتراک زمانی نامناسب است .لذا در اغلب سیستمها از یک زمان سنج(Timer) داخلی برای ایجاد وقفه‌های متناوب سخت افزاری جهت گرفتن CPUاستفاده می‌شود.

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

فرکانس این وقفه در سیستم عامل‌های ساعت معمولا بین 50تا60 بار در ثانیه است .

این نوع زمانبندی که در آن پس از تمام شدن برش زمانی معین , CPU از گرفته می‌شود زمانبندی غیر انحصاری نام دارد.

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

یک اولویت ممکن است استاتیک باشد یا دینامیک .

اولویت استاتیک تغییر نمی‌کندو بنابراین پیاده سازی آن ساده است .

ولی این نوع اولویت در مقابل تغییرات محیطی عکس العملی نشان نمی‌دهد .

برعکس اولویت دینامیک بر اثر تغییرات محیطی تغییر می‌کند مثلا ً ممکن است در آغاز یک برنامه اولویت پائینی داشته باشد ولی به تدریج اولویت آن بهبود یابد.

معیار های زمانبندی در سیستم عامل 1.

عدالت (fairness) یعنی اطمینان از اینکه هر پروسس سهم عادلانه و منصفانه‌ای از CPU را دریافت کند.

2.

کارایی یا بهره وری (utilization- Efficiency) CPU یعنی اینکه CPU در تمام زمانها (حتی الامکان) مشغول باشد 3.

زمان پاسخ (Response Time) یعنی به حداقل رساندن زمان پاسخ برای فرمانهای محاوره‌ای کاربر.

این زمان معمولاً با سرعت ابزار خروجی محدود می‌شود.

4.

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

فاصله زمانی از لحظه تحویل کار تا لحظه تکمیل کار را زمان برگشت می‌نامند ولی زمان پاسخ مدت زمانی است که از صدور یک تقاضا تا تولید اولین پاسخ آن طول می‌کشد (نه زمان خروجی کل برنامه) زمان بارگذاری در حافظه +زمان عملیات I/O +زمان اجراء+ زمان انتظاردر صف آماده = زمان گردش کار 5.

توان عملیاتی یا گذردهی (throughput) به تعداد پردازشهایی که در واحد زمان تکمیل می‌شوند توان عملیاتی می‌گویند.

الگوریتم زمانبندی باید به گونه‌ای باشد که این معیار را افزایش دهد .

6.

زمان انتظار (waiting time) الگوریتم زمانبندی CPU, بر میزان زمان اجرای پردازش یا اعمال I/O اثر نمی‌کند, بلکه فقط در زمان صرف شده جهت انتظار در صف آماده اثر می‌گذارد.

زمان انتظار , مجموع پریودهای زمانی صرف شده در صف آماده می‌باشد.

زمانبندی صفهای چند گانه Multiple queues هنگامی که بتوان فرآیندها را به سادگی به دسته‌های متفاوت طبقه بندی کرد از این روش استفاده می‌گردد.

در الگوریتم صفهای چندگانه, صف آماده, به صف های جداگانه مختلفی تجزیه می‌شود و هر پردازش وارد یک صف می‌گردد.

اولویت صفها با هم فرق داشته و هر صفی الگوریتم زمانبندی خود را دارد اول آمده-اول سرویس شده (FIFO): ساده ترین الگوریتم زمانبندی CPU ,الگوریتم اول آمده, اول سرویس شده (first come- first served =FCFS) می‌باشد .

گاهی اوقات به این روش (first In First Out)FIFO نیز می‌گویند.

در این روش هر پردازش در سیستم عاملی که اولین در خواست CPU را صادر کند , اولین پروسسی خواهد بود که آن را به دست می‌آورد .

این روش از نوع انحصاری (non- preemptive) است که به سادگی توسط یک صف FIFO پیاده سازی می‌شود.

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

زمانبندی نوبت گردشی (Round Rabin) : این زمانبندی یکی از قدیمیم ترین , ساده ترین , عادلانه ترین و رایجترین الگوریتم های زمانبندی است و از نوع غیر انحصاری (preemptive) می‌باشد.

یک قاعده سرانگشتی این است که go درصد انفجارهای محاسباتی باید کوتاه‌تر از کوانتوم زمانی باشند و در عمل برا یاین امر برش زمانی را حدود 100 میلی ثانیه در نظر می‌گیرند.

اول کوتاه ترین زمان (SJF) در الگوریتم (Shortest Job First) که روشی انحصاری است CPU به پردازش داده می‌شود که کوچکترین انفجار محاسباتی بعدی را دارد.

البته اصطلاح مناسبتر , «کوتاهترین انفجار محاسباتی بعدی»می‌باشد.

زیرا این زمانبندی بر اساس طول مدت انفجار CPU بعدی عمل می‌کند و نه بر اساس طول کل پردازش در سیستم عامل .

اگر دو پردازش در سیستم عامل مدت انفجار محاسباتی یکسانی داشته باشد براساس FCFS زمانبندی می‌شوند.

این الگوریتم می‌تواند انحصاری و غیر انحصاری باشد.

این الگوریتم مخصوصاً برای کارهای دسته‌ای که از قبل زمان اجرای آن کارها , مشخص و معین باشد به کار می‌رود .

مهمترین مشکل در SJF آگاهی از طول درخواست بعدی CPU می‌باشد.

هیچ راهی که طول انفجار محاسباتی بعدی را برای ما مشخص سازد وجود ندارد.

لذا در صورت لزوم مجبوریم آن را پیش بینی کنیم .

یعنی انتظار داشته باشیم که طول انفجار بعدی خیلی شبیه طول انفجار‌های قبلی باشد.

بالا ترین نسبت پاسخ(HRRN) زمانبندی Highest Response Ratio Next) HRRN) نوعی زمانبندی انحصاری است که بعضی از مشکلات SJF را برطرف می‌سازد.

در SJF نظر افراطی خوبی نسبت به کارهای کوتاه و برعکس نظر افراطی بدی نسبت به کارهای طولانی وجود دارد به طوری که ممکن است مشکل قحطی زدگی رخ دهد.

در این زمانبندی اولویت ها دینامیک است.

کارهای کوتاهتر اولویت بیشتری داشته و زودتر اجراء می‌شوند.

کارهای طولانی نیز که مدت زیادی در صف انتظار بوده اند اولیت بیشتری کسب کرده وبالاخره در یک زمان معین اجراء می‌شوند.

بدین ترتیب مشکل قحطی زدگی برطرف می‌شود بلا درنگReal time) ) در سیستم بلادرنگ سخت , پردازش در سیستم عامل ها می‌بایست در یک زمان تخمین شده اجراء و اتمام شوند., مانند سیستم کنترل موشک .

چنین تضمینی در یک سیستم با حافظه ثانویه یا حافظه مجازی غیر ممکن است .

در سیستم بلادرنگ نرم (مانند پخش موسیقی) زمان پاسخگویی به پردازش در سیستم عامل مهم است ولی مانند بلادرنگ سخت , حیاتی نیست .

اتفاقاتی که سیستم بلادرنگ باید به آنها پاسخ دهد به دو دسته متناوب و غیر متناوب تقسیم می‌شوند.

وقایع متناوب در فواصل زمانی مساوی اتفاق می‌افتند ولی وقایع متناوب به صورت تصادفی و تصادفی بوده و غیر قابل پیش بینی می‌باشند.

روشهای زمانبندی بلادرنگ به دو دسته کلی پویا و ایستا تقسیم می‌شوند.

در حالت ایستا قبل از شروع سیستم , تصمیمات زمانبندی گرفته می‌شود ولی در حالت پویا تصمیمات زمانبندی در زمان اجرای سیستم انجام می‌پذیرد .

سه روش زمانبندی بلا درنگ پویا عبارتند از: • الگوریتم نرخ یکنواخت (Rate monotonic) : در این الگوریتم به هر پردازش در سیستم عامل اولویتی متناسب با فرکانس رخداد آن واقعه نسبت داده می‌شود.

مثلاً به پردازشی که هر20 میلی ثانیه تکرار می‌شود, اولویت 50 و به پردازشی که هر 100 میلی ثانیه تکرار می‌شود, اولیت 10 داده می‌شود.

این الگوریتم از نوع غیرانحصاری است .

می‌توان اثبات کرد که این الگوریتم بهینه است.

• الگوریتم ابتدا زودترین مهلت (Earliest deadline first) در این الگوریتم پردازش در سیستم عاملی ابتدا اجراء می‌شود که فرصتش از همه کمتر است یعنی نزدیکترین مهلت را دارد .

این مهلت برای وقایع متناوب برابر زمان رخداد واقعه بعدی می‌باشد.

• الگوریتم کمترین سستی (least laxity) زمان سستی یک پردازش در سیستم عامل زمانی است که می‌تواند آماده باقی مانده و اجراء نشود.

مثلاً اگر یک پردازش در سیستم عامل به 200 میلی ثانیه وقت CPU احتیاج داشته باشد.

و250 میلی ثانیه نیز مهلت داشته باشد که کارش را تمام کند, زمان سستی او برابر 250-200=50 میلی ثانیه می‌باشد.

در این الگوریتم پردازشی ابتدا اجراء می‌گردد که کوچکترین زمان سستی را دارد.

زمانبندی LPT در زمانبندی (Longest Processing Time) هر گاه که پردازنده‌ای آزاد می‌گردد, از بین کارهای باقی مانده طولانی‌ترین کار را برای اجرا انتخاب می‌کند.

هرچند که این الگوریتم بهینه نیست ولی غالباً منحصر به زمانبندی‌هایی با طول معقول می‌شود منبع: http://ghanbari_os_ict.persianblog.ir/