به نام خدا

تمرینات Buffer Overflow

استاد: دکتر مقصود عباسپور

کمک تدریس: جواد زندی

 

لطفا در ارسال تمرینات خود به نکات‌ مهم زیر توجه داشته باشید:

1-     مهلت این سری تمرینات تا ۴اردیبهشت می‌باشد.

2-     برای دانلود نسخه الکترونیکی PDF از لینک استفاده نمایید.

3-     نحوه تحویل تمرینات شما به دو صورت می‌تواند باشد:

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

ب) سوالاتی از تمرین که شامل برنامه‌نویسی است: در این مورد باید متن برنامه ‌(source code) که حتما باید قابل اجرا باشد به همراه متعلقات لازم در درس‌افزار با درنظرگرفتن عنوان مناسب با فرمول [SecNet95B][hw2][student#][full name] ارسال کنید. همچنین به خاطر داشته باشید که درصورتی که قصد دارید چندین فایل برای حل تمرین بفرستید، ابتدا باید آنها را zip کنید و نام فایل زیپ شده را به فرمول فوق درآورید.

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

برای مشاهده سوالات به ادامه مطلب بروید.

به نام خدا

تمرینات ‌سری سوم

استاد: دکتر مقصود عباسپور

کمک تدریس: جواد زندی

 

لطفا در ارسال تمرینات خود به نکات‌ مهم زیر توجه داشته باشید:

1-     مهلت این سری تمرینات ۷خرداد می‌باشد.

2-     برای دریافت این تمرین به صورت فایل pdf روی لینک کلیک کنید.

3-     نحوه تحویل تمرینات شما به دو صورت می‌تواند باشد:

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

ب) سوالاتی از تمرین که شامل برنامه‌نویسی است: در این مورد باید متن برنامه ‌(source code) که حتما باید قابل اجرا باشد به همراه متعلقات لازم در درس‌افزار با درنظرگرفتن عنوان مناسب با فرمول [SecNet95B][hw3][student#][full name] ارسال کنید. همچنین به خاطر داشته باشید که درصورتی که قصد دارید چندین فایل برای حل تمرین بفرستید، ابتدا باید آنها را zip کنید و نام فایل زیپ شده را به فرمول فوق درآورید.

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

5-     در مورد تمرینات این سری تحویل‌ها با کمی جزیات همراه می‌باشد. لطفا در ارایه تمرینات خود به آنها توجه نمایید. این جزیات در خود سوال حتما قید خواهد شد.

برای مشاهده سوالات به ادامه مطلب بروید.

به نام خدا

پروژه پاياني درس سیستم عامل

استاد: دکتر محسن ابراهیمی مقدم

کمک تدریس: جواد زندی  – زهرا خوبی

 

لطفا در ارسال پروژه خود به نکات‌ مهم زیر توجه داشته باشید:

1-     برای دریافت نسخهPDF تعریف پروژه از لینک استفاده نمایید.

2-     برای دریافت فایل‌های هسته اولیه برنامه نویسی پروژه و سایر فایل های مورد نیازتان، روی لینک کلیک کنید.

3-     پروژه اين درس در گروه‌‌های دونفره خواهد بود.

4-     براي تحويل پروژه بايد دو قدم زير را طي کنيد.

الف) ابتدا کد متن پروژه تان را به همراه راهنماي کامل که به صورت يک فايل pdf است در يک فايل zip‌ شده به بنده در فرمت زير ايميل خواهيد کرد. توجه داشته باشيد که عنوان ايميل و فايل ضميمه شده بايد از فرمول زير تبعيت کند. حتما به خاطر داشته باشید که در صورت ارسال با فرمت صحیح حتما یک ایمیل تاییدیه صورت خودکار توسط سیستم برای شما ارسال خواهد شد. در غیر این صورت پروژه شما به دست من نرسیده است.

[sbuos93a][project][studentNumber1][full name1][studentNumber2][full name2]

i.e.: [sbuos93a][project][89213092][Javad Zandi][89213092][Zahra Khobi]

ب) در فرصتي که بعدا اعلام خواهد شد به شما نوبت داده مي‌شود تا حضور پيدا کنيد و کد خودتان را توضيح دهيد. عدم حضور شما در تحويل حضوري به منزله عدم تحويل پروژه خواهد بود. لذا حتما در نوبتي که به شما داده مي‌شود به موقع حضور داشته باشيد.

5-     فراموش نکنيد براي ارزش يابي پروژه بايد يکبار کد شما خوانده شود. پس براي رفع ابهام از کدتان حتما از comment‌ استفاده کنيد.

6-     به خاطر داشته باشید که فايل پروژه خود را باید به ایمیل sbuos93a@gmail.com بفرستید. همچنین هرگونه مشکل در روند کلاس و پیشنهادات خود را می‌توانید از این طریق پیگیری نمایید. از ارسال پروژه تان به گروه اجتناب کنید. بهتر است سوالات خود را در گروه مطرح کنید تا دیگر دوستان از مطالب فیض ببرند!

7-     پروژه شما به گونه‌اي طرح شده است که فقط با زبان‌هاي C/C++  قابل پياده‌سازي است. پس زبان مجاز شما فقط C/C++‌  و کتابخانه‌های قید شده مي‌باشد.

مقدمه

در این پروژه با مفاهیم Virtual Memory و Synchronizationآشنایی بیشتری پیدا می‌کنیم. پروژه شامل دو فاز است که باید جداگانه پیاده‌سازی شده و تحویل شوند (می‌توانید پس از تکمیل فاز اول یک کپی از کد خود بگیرید و آنرا در انتها همراه با کد کامل تحویل دهید).

شبیه‌سازی عملکرد Virtual Memory هدف این پروژه است. کلیت شبیه‌سازی در یک زبان برنامه‌سازی انجام می‌شود و زبان برنامه‌سازی مذکور باید امکانات همسان‌سازی (Synchronization) ‌را در اختیار برنامه‌نویس قرار دهد، نه اینکه به صورت خودکار پیاده کند. به عنوان مثال زبان‌های C و ++C ایده‌آل هستند.

 

فاز اول (۵۰ نمره) :

در فاز اول دو برنامه جداگانه باید نوشته شود،‌ یکی مدیر Paging Supervisor که از این پس آنرا Supervisor می‌نامیم، و دیگری مصرف‌کننده (Consumer). برنامه مدیر، باید برنامه مصرف‌کننده را به عنوان فرزند خود اجرا کند. در برنامه مدیر، یک آرایه بزرگ با مقدار قابل تغییر(ثابت در طول اجرای برنامه) برای شبیه‌سازی Page Table در نظر گرفته‌ می‌شود. این آرایه باید در فضای اشتراکی (Shared Memory) تخصیص‌یابد (مثلا با استفاده از دستور shmget در لینوکس). برنامه مصرف‌کننده نیز به این فضای اشتراکی دسترسی‌دارد. فضای دیگری تحت عنوان TLB به صورت اشتراکی در هر دوی این برنامه‌ها تخصیص می‌یابد، که کارکرد Translation Lookaside Buffer را شبیه‌سازی می‌کند.

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

در ابتدای فایل ورودی‌(که مصرف‌کننده آن را می‌خواند)، اندازه کلی حافظه و همچنین اندازه هر صفحه حافظه در دو خط مجزا به بایت مشخص شده‌اند. هنگامی که برنامه مصرف‌کننده به آدرسی مجازی می‌رسد که در جدول صفحات موجود نیست، یک Page Fault رخ می‌دهد. شبیه‌سازی این عمل را با ایجاد یک سیگنال دلخواه در برنامه مصرف‌کننده انجام می‌دهیم(تابع raise در لینوکس). برنامه مدیر، قبل از اجرای برنامه مصرف کننده تنظیم می‌کند که سیگنال مربوطه در برنامه مدیر پردازش شود، لذا وقتی برنامه مصرف‌کننده سیگنالی را raise کرد، کنترل به برنامه مدیر منتقل‌می‌شود و مدیر وظیفه دارد تا این حافظه را از دیسک به جدول صفحات منتقل کند(البته مفاهیم دیسک و حافظه مجازی هستند و کاری به دیسک و حافظه‌اصلی واقعی سیستم شما ندارند). برای سادگی کار، به انتقال داده از/به دیسک نیازی نیست، و فقط کافیست برنامه‌مدیر ردیف مربوطه از جدول صفحات(با درنظر گرفتن الگوریتم‌های جایگزینی صفحات) بروزرسانی کند.

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

 

 

فاز دوم(۵۰ نمره):

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

                برنامه مدیر باید به‌ترتیب نام این فایلها را از ورودی خود بخواند و به مصرف‌کننده‌ها برای پردازش ارسال کند. توجه داشته‌باشید که تعداد مصرف‌کننده‌ها ثابت است، و همگی آنها باید در ابتدای اجرای مدیر اجرا شوند، نه پس از شروع فرآیند مدیر (يعني همگي از يک pool باشند و نه اينکه در طول اجراي برنامه spawn شود). هنگامی که تمام مصرف‌کننده‌ها مشغول هستند، برنامه مدیر صبر می‌کند تا یکی از آنها خالی شوند و سپس فایل بعدی را به او برای پردازش ارسال می‌کند.

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

در فاز دوم، باید دقت داشته باشید که تغییرات در TLB و Page Table باید به صورت همسان(synchronized) شده باشد، زیرا چندین برنامه در حال کار کردن با آن به صورت همزمان هستند. در غیر اینصورت عملیات دچار خطا خواهد شد.

 

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

 

نکات مورد نياز در تحويل پروژه:

1- برنامه شما حداقل بايد يک نوع واسط باشد چه CLI‌ و چه GUI.

2- عدم رخداد خطاي زمان اجرا و کار کردن با فايل به عنوان وردی مصرف‌کننده و مدیر الزامي است.

3- برنامه شما بايد تماما deadlock free و without starvation و Mutal Exclusion باشد.

4- براي ايجاد همروندي فقط بايد از multi processing استفاده کنيد. يعني برنامه مدير و مصرف‌کننده‌ها هريک بايد يک فرايند مستقل باشند.

5- برنامه مدیر باید هرگاه یک TLB miss یا Page fault که رخ داد، یک گزارش کامل شامل آدرس مجازی، شناسه مصرف‌کننده  و نوع خطا(TLB miss or Page fault) در یک خط در فایل خروجی طبق فرمت پیشنهادی بنویسد.

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

 

مقررات پروژه:

1) پروژه شما در گروه‌های ۲نفره خواهد بود. لذا درخواست گروه تک نفره یا ۳نفره را نفرمایید. کسانی که تک نفره مانده‌اند یک ایمیل به حل تمرین بفرستند تا حل تمرین برای آنان یک هم‌گروهی مناسب پیدا کند.

2) تا پایان ۲۶آذر فرصت دارید اسامی گروه خود را به حل‌تمرین ایمیل کنید.

3) تحویل حضوری شما حداکثر ۲۰ دقیقه مهلت دارد. لذا رایانه خود را به طور کامل آماده نمایید تا فرصت شما ضایع نشود. بهتر است از یک ساعت قبل همه چیز را آماده کنید تا برای شما مشکلی پیش نیاید.

4) به هیچ وجه کد خود را با دیگران به اشتراک نگذارید. در صورت مشاهده کد‌های مشابه، منفی حداکثر نمره پروژه به شما تعلق خواهد گرفت.

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

6) برنامه‌زمانی برای تحویل پروژه: فاز اول را تا ۱دی تکمیل کنید و حضوری تحویل دهید. فاز دوم را تا ۱۵دی تکمیل کنید و تحویل دهید. این کار ۲دلیل دارد: الف) در صورتی که به اشکال برخورده‌اید می‌توانید در فرصت کافی آن را حل کنید و مشکلات زیاد را به روزهای آخر تحویل کلی پروژه موکول نکنید. ب) ایراد احتمالی در طراحی شما در ابتدا آشکار و رفع نقص خواهد شد.

7) در صورتی که تا ۱دی فاز اول را تحویل ندهید و هردو فاز را ۱۵دی تحویل دهید، ۳۵٪ نمره فاز اول را دریافت نخواهید کرد.

8) هیچ فرضی برای نحوه انجام دادن پروژه ننماید. هرجا در تعریف پروژه مفهوم گنگی وجود داشت بدون از دست رفتن وقت حتما سوال بفرمایید. بنده حتما در اسرع وقت پاسخ‌گوی شما خواهم بود.

9) از ۲۶آذر ساعت ۱ظهر به بعد در سیستم آموزش الکترونیکی وارد حساب کاربری خود بشوید و یک ساعت مناسب برای تحویل پروژه از لیست پیشنهادی انتخاب کنید (اینکار را فقط یک نفر از گروه انجام دهد و نه هر دو نفر).

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

11) ایده‌های خلاقانه همیشه بسیار دوست داشتنی هستند. در هسته‌ی اصلی هر پروژه اگر ایده‌ی خلاقانه وجود داشته باشد، نمره‌ای فراتر از حد پروژه خواهد گرفت.

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

13) قبل از تحویل حضوری، حتما کد پروژه خود را به ایمیل حل‌تمرین ایمیل کنید.

14) حتما یک مستند متنی برای کدتان آماده کنید. اینکار به من کمک می‌کند کد شما را بهتر بفهمم و نمره‌ای بیشتر به تلاش شما بدهم.

15) هرگونه سوالی را در ساعت‌های مجاز پرسش و پاسخ بپرسید یا از طریق ایمیل حل تمرین جویا شوید.

موفق باشيد

مدت زمان کوییز: ۲۰ دقیقه                                                             بالای برگه خود حتما نام و نام‌خانوادگی را بنویسید.

１- الگوریتم‌های زمان‌بندی که تاکنون خوانده‌اید (FCFS, SJF, SPN, SRT, Priority, RR, MultiLevel Queue, …) را درنظر بگیرید و به سوالات زیر با استدلال پاسخ دهید:

الف) کدام الگوریتم(ها) بیشترین بهره‌ی پردازنده را دارد؟    ب) کدام الگوریتم(ها) کمترین زمان گردش کار را دارد؟

ج) کدام الگوریتم(ها) کمترین زمان انتظار را دارد؟               د) کدام الگوریتم(ها) کمترین زمان پاسخ‌دهی را دارد؟

پاسخ:

２- با زبان مهندسی خودتان توضیح دهید برتری روشی مانند مانیتور به سمافور به چه دلیل است؟ برای توضیح یک مسئله را به دلخواه خودتان با تکنیک سمافور حل کنید و سپس همان مسله را با مانیتور حل کنید. آنگاه به مقایسه این ۲روش بپردازید.

پاسخ:  در کلاس حل تمرین به تفصیل بحث و بررسی شده است.

３- در جدول زیر کد اجرایی سه فرآیند را می‌بینید که برای شش منبع با یکدیگر رقابت می‌کنند. در این مورد:

void P0() {      while (true) {              get(A);              get(B);              get(C);              // critical region:              // use A, B, C              release(A);              release(B);              release(C);     } }

void P1() {      while (true) {          get(D);          get(E);          get(B);          // critical region:          // use D, E, B          release(D);          release(E);          release(B);      }  }

void P2() {     while (true) {          get(C);          get(F);          get(D);          // critical region:          // use C, F, D          release(C);          release(F);          release(D);     } }

 

الف) گراف تخصیص منابع را برای این سه فرآیند رسم کنید و در مورد احتمال رخداد بن بست استدلال کنید.

پاسخ: برای تشخیص بن‌بست باید ۴شرط به طور همزمان ایفا شود:

１- وجود انحصار متقابل (Mutal Exclusion)

２- نگهداری و انتظار (Hold & Wait)

３- غیرقابل بازپس گیری‌(No Preemption)

４- انتظار حلقوی (Circular Waiting)

 

بنابراین توجه داشته‌باشید که باید هر چهار شرط بررسی شود.

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

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

   حال که شکل پیوست را دیده‌اید باید بررسی کنیم در این مسئله بن‌بست داریم یا نه؟

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

 

باتوجه به ینکه اجرای فرآیندها موازی است:

P2.get(C) à P1.get(D) à P0.get(A) à P0.get(B)

یعنی ابتدا C را به P2 می‌دهیم و …

بنابراین گراف حاصل مطابق با شکل‌زیر خواهد بود:

اختصاص بی‌خطر: هرگاه برای یک منبع فقط یک درخواست داشته باشیم اختصاص بی‌خطر است. (به عنوان مثال فقط یک متقاضی داشته‌باشد)

اختصاص خطرناک: هرگاه برای یک منبع بیش‌از یک درخواست داشته باشیم اختصاص خطرناک است. (به عنوان مثال چند متقاضی داشته‌باشد)

یال‌های درخواستی: این یال‌ها درواقع همان get(…) ها می‌باشند.

 

با کمی دقت در شکل بالا متوجه وجود یک دور خواهید شد.

 

ب) ترتیب نحوه درخواست فرآیندها به منابع را طوری تغییر دهید که تخصیص منابع کاملا امن باشد. توجه کنید منابع نباید میان فرآیندها جابجه شود. یعنی فقط در داخل فرآیندها ترتیب اختصاص را تغییر دهید.

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

و در نتیجه کد فوق به صورت زیر خواهد بود:

 

 

void P0() {      while (true) {              get(A);              get(B);              get(C);              // critical region:              // use A, B, C              release(A);              release(B);              release(C);     } }

void P1() {      while (true) {          get(E);          get(B);          get(D);          // critical region:          // use D, E, B          release(E);          release(B);          release(D);      }  }

void P2() {     while (true) {          get(F);          get(D);          get(C);          // critical region:          // use C, F, D          release(F);          release(D);          release(C);     } }

 

با آرزوی موفقیت برای شما دوستان عزیز

زندی

برای دریافت نسخهPDF پاسخ کوییز از لینک استفاده نمایید.