وبلاگ میثم پاسداری هریس

۲ مطلب در دی ۱۳۹۲ ثبت شده است

  • ۱
  • ۰
ای قوم به حج رفته کجایید کجایید * معشوق همین جاست بیایید بیایید

معشوق تو همسایه و دیوار به دیوار * در بادیه سرگشته شما در چه هوایید

گر صورت بیصورت معشوق ببینید * هم خواجه و هم خانه و هم کعبه شمایید

ده بار از آن راه بدان خانه برفتید * هم خواجه و هم خانه و هم کعبه شمایید

آن خانه لطیفست نشانهاش بگفتید * از خواجه آن خانه نشانی بنمایید

یک دسته گل کو اگر آن باغ بدیدیت * یک گوهر جان کو اگر از بحر خدایید

با این همه آن رنج شما گنج شما باد * افسوس که بر گنج شما پرده شمایید

" مولانا "
  • میثم پاسداری
  • ۰
  • ۰


سوال 1) دو روش شناخته شده برای ارتباط بین فرآیند ها (IPC) ارتباط از طریق ارسال پیام (Message Passing) و ارتباط از طریق حافظه مشترک (Shared Memory) می باشد. نحوه تبادل اطلاعات را در دو روش با رسم شکل نشان دهید.توضیح دهید که هرکدام از روش ها در رابطه با کدام نوع پیام ها (پیام های طولانی و کوتاه) مفید هستند؟

پاسخ پیشنهادی سوال 1: 

در شکل بالا میتونید مشاهده کنید که طرز کار این دو روش چیست و تفاوت های ظاهری شان را نیز ببینید.

روش message passing  از یک صف برای مدیریت پیام ها استفاده می کند و هسته سیستم عامل مسئول دریافت و ارسال پیام ها می باشد. در این روش هر پراسس فقط می تواند به پیام مورد نظر خود دسترسی داشته باشد.

در روش Shared memory بخشی از حافظه به صورت مشترک بین دو پراسس مورد استفاده قرار می گیرد که در این روش ممکن است ناحیه اشتراکی توسط چندین پراسس مورد استفاده قرار گیرد و یا ممکن است داده مورد نظر تغییر یابد. در واقع به طور پیشفرض protection وجود ندارد.

نقاط قوت Message Passing:

            -پیاده سازی راحت تر در سیستم های توزیع شده

            -کارایی بالا در تبادل اطلاعات با حجم کم به دلیل نبود برخورد(Conflict)

 

نقاط قوت Shared Memory:

          -  سرعت بالایی نسبت به Message Passing دارد.

          - عدم نیاز به دستیاری به Kernel

            - در سیستم های چندپردازه ای چندهسته ای Message Passing  کارایی بهتری نسبت به Shared Memory دارد (چون یک پیام میتواند در قالب یک Packet از طریق شبکه بین سیستم های مختلف تبادل شود)

          - متناسب برای ارسال داده با حجم زیاد

- - - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - -

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

پاسخ پیشنهادی سوال 2: 

بهتره قبلا از اینکه سراغ حل مسئله بریم چندتا اصطلاح رو تعریف کنیم:

زمان پاسخ(Response Time): مدت زمانی است بین صدور تقاضای پراسس تا اولین تخصیص CPU به آن (یعنی مدت زمان تولید اولین پاسخ)

زمان برگشت(Turn Around Time): به فاصله زمانی از لحظه ورود پراسس به صف آماده تا خروج از سیستم گفته می شود.

قحطی زدگی (Starvation): یعنی الان منبعی در دسترس نیست و هیچ تخمینی هم از بدست آوردن منبع در اینده ندارد(یعنی حدی برای تعویق وجود ندارد).

قابل پس گرفتن(Preemptive): در اینجا یعنی می توان CPU را از دست یک پراسس گرفت و به پراسس دیگری تخصیص داد.

بخش اول سوال گفته که یک سیستم داریم با Job هایی که زمان بیشتری از Cpu را نیاز دارند تا اجرا شده و تمام شوند، از طرف دیگر الگوریتمی را می طلبد که در آن هزینه (Overhead) کمینه ای داشته باشد، پراسس ها دچار قحطی زدگی (Starvation) نشوند و مهمتر از همه زمان پاسخ (Response Time) بهتری (کمتری) داشته باشد.

الگوریتم های زمانبندی زیر وجود دارند :

FCFS یا First Come First Served: این روش عادلانه است یعنی پردازه ای که زود بیاید زود cpu را دست می گیرد، تمام پردازه ها اجرا می شوند، مشکل قحطی زدگی ندارد، اما مشکل بزرگی که دارد این است که زمان پاسخ بهینه ای نمی دهد.

SJF یا Shortest Job First: این روش به پردازه هایی با زمان اجرایی کمتر اولویت بالایی می دهد اما زمان پاسخ خوبی هم دارد. از طرف دیگر مشکل قحطی زدگی را (در صورت ورود دائم پردازه های بازمان اجرا کوتاه تر) در بطن خود دارد.این زمانبندی برای کارهای کوتاه بسیار مناسب است.

SRTF یا Shortest Remaining Time First: حالتی از  Preemptive SJF است که در آن پردازنده قابل پس گرفتن بوده و بجای در نظر گرفتن زمان کل کار، طول زمان باقی مانده را در نظر می گیریم. این روش در مقایسه با SJF زمان برگشت بهتری را ارائه می دهد زیرا به کار کوتاه نسبت به کار طولانی در حال اجرا اولویت می دهد.

RR یا Round Robin: این زمانبندی یکی از ساده ترین، عادلانه ترین و رایج ترین الگوریتم های زمانبندی است. در واقع این زمانبندی از تعمیم FCFS به وجود آمده است با این تفاوت که Non Preemptive است و در آن هر پراسس حداکثر در یک زمان مشخص (Quantum Time) می تواند CPU را اختیار کند. این زمانبندی با قرار دادن پراسس ها در یک صف چرخشی آنها را به ترتیب اجرا کرده و CPU را به یک اندازه زمانی مشخص در اختیار آنها قرار می دهد.

روش های دیگری از جمله HRRN، LPT،MLQ،MFQ،Priority و ... وجود دارند که در حوصله این سوال نمی گنجد.

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

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

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

اما شاید برایتان سوال پیش بیاید که SRTF نسبت به SJF برای اینکار مناسب است، دلیل اینکه از این روش استفاده نکردیم Overhead نسبتا بالای آن(متضاد با مفروضات مسئله) در مقابل  SJF است.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

سوال 3) سوالاتی از مبحث Threading در سیستم عامل 

الف) زمان سربار Context Switch مابین دو User-level thread بیشتر است یا دوkernel-level thread ؟ چرا؟

پاسخ پیشنهادی بخش الف:

زمان تعویض متن بین دو kernel-level-thread بیشتر از دو User-Level-Thread است به دلیل اینکه سیستم عامل با حالت اول همانند پراسس رفتار نموده و( TCB(Thread Control Block را بررسی می نماید اما در حالت User نه تنها TCB سراسری Thread را بررسی نمی کند به Kernel نیز رجوع نمی کند.

ب) به نظر شما برنامه نویسیMulti-thread (استفاده از امکان موازی سازی توسط thread) ها چه مزایا و چه معایبی به دنبال دارد؟ (حداقل یه حسن و یک عیب – نهایتا در دو خط پاسخ دهید)

پاسخ پیشنهادی بخش ب:

مزایا:
 قسمت‌هایی از برنامه اصلی که قابلیت اجرای همزمان (Concurrent) را دارند به چند زیربرنامه تقسیم شده و به صورت همزمان روی چند پردازنده یا چند نخ اجرا می‌شوند، که در نتیجه سرعت اجرای برنامه بالا خواهد بود.

معایب:

به دلیل اینکه این روش برنامه نویسی باید چندین Thread را مدیریت کند و همچنین استفاده از فضای اشتراکی خود معضلاتی دارد بنابراین پیچیدگی بالایی را به همراه دارد.

این صفحه رو هم ببینید تو مبحث Threading خالی از لطف نیست.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

سوال4) معیار های ارزیابی روش های زمانبندی را نام برده و هرکدام را دقیقا در یک خط تعریف کنید.(با نمره مفت از سوال آسان کیف کنید :D)

پاسخ سوال 4 : 

عدالت (Fairness): اطمینان از اینکه هر پراسس سهم عادلانه ای از CPU را دریافت کند.

بهره وری (Utilization):  پردازنده (Cpu) همواره مشغول باشد.

زمان پاسخ(Response Time): به حداقل رساندن زمان پاسخ برای کارهای Interactive

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

توان عملیاتی(Throughput): به تعداد پراسس هایی که در واحد زمان تکمیل می شوند گفته می شود، الگوریتم زمانبندی باید این معیار را افزایش دهد.

زمان انتظار (Waiting Time): مجموع دوره های زمانی صرف شده در صف Ready

- - - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - -

سوال5) تفاوت Mode Switch و Context Switch چیست؟

پاسخ سوال 5 :

در حالت Mode Switch ممکن است که State پراسس تغییر نیابد (یعنی اگر در حالت Running است در همان حالت بماند) اما در حالت Context Switch حتما State  تغییر می یابد (مثلا از حالت Running به حالتReady یا Block می رود). در حالت Context Switch اطلاعات بیشتری از State پراسس باید ذخیره گردد.

- - - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - -

سوال6) در ماشینی طول virtual address ها و Physical Address ها 48 بیت و اندازه frame ها 8 کلیوبایت می باشد.

  الف) در صورتیکه از روش segmentation with paging در این ماشین استفاده نماییم. شمای دقیق روال Address Binding را با مشخص کردن تعداد بیت هر بخش (مثل offset و...) رسم نمایید.

پاسخ پیشنهادی بخش الف) منبع مورد استفاده 

  • میثم پاسداری