project2-design.md

سیستم‌های عامل - تمرین گروهی دوم

مشخصات گروه

نام، نام خانوادگی و ایمیل خود را در ادامه وارد کنید.

سروش شرافت sorousherafat@gmail.com

علی‌پاشا منتصری alipasha.montaseri@gmail.com

کیان بهادری kkibian@gmail.com

مهدی علیزاده alizademhdi@gmail.com

مقدمه

اگر نکته‌ای درباره فایل‌های سابمیت شده یا برای TAها دارید، لطفا اینجا بیان کنید.

اگر از هر منبع برخط یا غیر برخطی به غیر از مستندات Pintos، متن درس، اسلایدهای درس یا نکات گفته شده در کلاس در تمرین گروهی استفاده کرده‌اید، لطفا اینجا آن(ها) را ذکر کنید.

ساعت زنگ‌دار

داده ساختارها

پرسش اول: تعریف structهای جدید، structهای تغییر داده شده، متغیرهای گلوبال یا استاتیک، typedefها یا enumerationها را در اینجا آورده و برای هریک در 25 کلمه یا کمتر توضیح بنویسید.

/* An ordered static list,
 * containing all the threads that are currently sleeping.
 */
static struct list sleeping_threads;

typedef uint64_t ticks_t;

/* Additions to `struct thread`. */
struct thread {
    ...
    /* When the thread will wake up, if sleeping,
     * expressed in `TICK`s counting from the kernel startup.
     */
    ticks_t wake_up_tick;

    /* `struct list_elem` for the `struct list sleeping_threads`.
     * It is shared between different linked lists,
     * because a `struct thread` is not a member of
     * more than one of these lists at any given time. */
    struct list_elem elem;
    ...
};

الگوریتم

پرسش دوم: به اختصار آن‌چه هنگام صدا زدن تابع timer_sleep() رخ می‌دهد و همچنین اثر timer interrupt handler را توضیح دهید.

الگوریتم timer_sleep

۱. تمام interruptهای سیستم را disable می‌کنیم.

۲. صفت wake_up_tick از threadی که timer_sleep را صدا زده است مقداردهی می‌شود. این مقدار از رابطه زیر به دست می‌آید:

$$wake_up_tick = current_kernel_ticks + sleep_ticks$$

۳. سپس thread موردنظر به struct list sleeping_threads به‌صورت ordered اضافه می‌شود.

۴. این thread را block می‌کنیم.

۵. دوباره interruptهای سیستم را به level قبل برمی‌گردانیم.

الگوریتم timer interrupt handler

۱. ابتدا بررسی می‌کنیم که آیا sleeping_thread خالی‌ست یا نه. درصورتی‌که خالی بود برمی‌گردیم.

۲. سپس یک iteration روی sleeping_threads انجام می‌دهیم. درصورتی‌که wake_up_tick هنوز فرا نرسیده بود برمی‌گردیم. درصورتی‌که رسیده بود ابتدا interruptها را disable می‌کنیم، thread را unblock می‌کنیم و دوباره interruptها را به level قبلی باز می‌گردانیم.

پرسش سوم: مراحلی که برای کوتاه کردن زمان صرف‌شده در timer interrupt handler صرف می‌شود را نام ببرید.

۱. تنها یک‌بار timer_ticks را صدا می‌زنیم و در ادامه، از همان مقدار استفاده می‌کنیم.

۲. درصورتی‌که struct list sleeping_threads‍ خالی بود برمی‌گردیم.

۳. همواره sleeping_threds را مرتب نگه می‌داریم و به همین دلیل، لازم نیست تمام آن را iterate کنیم. هرجایی که wake_up_tick هنوز فرا نرسیده بود برمی‌گردیم.

همگام‌سازی

پرسش چهارم: هنگامی که چند ریسه به طور همزمان timer_sleep() را صدا می‌زنند، چگونه از race condition جلوگیری می‌شود؟

تنها محل بروز race condition زمان اضافه‌کردن thread به struct list sleeping_threads است که برای آن interruptها را disable کرده‌ایم.

در حقیقت، زمانی که thread دارد به sleeping_threads اضافه می‌شود هیچ مکانیزمی مانع اجرای کد نمی‌شود و مطمئنا بدون race condition این کد اجرا می‌شود.

پرسش پنجم: هنگام صدا زدن timer_sleep() اگر یک وقفه ایجاد شود چگونه از race condition جلوگیری می‌شود؟

تمام interruptها disable می‌شوند و درنتیجه هیچ مانعی برای اجرای کد وجود نخواهد داشت.

منطق

پرسش ششم: چرا این طراحی را استفاده کردید؟ برتری طراحی فعلی خود را بر طراحی‌های دیگری که مدنظر داشته‌اید بیان کنید.

یک طراحی جایگزین، می‌توانست این باشد:

struct sleeping_thread {
    struct thrad *thread;
    ticks_t wake_up_tick;
    struct list_elem elem;
};

که struct list sleeping_threads به‌جای struct threadها، struct sleeping_thread‍ ها را نگه دارد.

مزیت طراحی ما، سادگی و کم‌تربودن allocationهاست.

استفاده از یک لیست static برای نگه‌داری threadهای درحال sleep راه ساده‌ای است که مشابه راه‌حل‌ها در زمینه‌ی running threads است.

برای بهبود performance نیز struct list sleeping_threads را مرتب نگه می‌داریم.

زمان‌بند اولویت‌دار

داده ساختارها

پرسش اول: تعریف structهای جدید، structهای تغییر داده شده، متغیرهای گلوبال یا استاتیک، typedefها یا enumerationها را در اینجا آورده و برای هریک در ۲۵ کلمه یا کمتر توضیح بنویسید.

# define BASE_PRIORITY -1

# define MAX_DONATION_LEVEL 5

دو متغیر گلوبال داریم که BASE_PRIORITY همان الویت اولیه هر ترد و MAX_DONATION_LEVEL نیز برابر است با حداکثر تعداد donation های تو در تو.

struct lock
{
    
    int priority;
    struct list_elem lock_elem;
};

استراکت lock که برای مدیریت لاک‌ها تعریف شده است. priority در آن به معنای بالاترین الویت بین ترد‌هایی که منتظر این لاک هستند است. در ابتدا نیز مقدار آن برابر است با BASE_PRIORITY. lock_elem برای استفاده از ساختار‌های لیست آماده شده در pintos استفاده شده است.

struct thread
{

    int base_priority;

    int priority;

    struct list locks;

    struct lock *wait_lock;

};

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

در این آرگومان‌ها base_priorty برابر است با الویت اولیه ترد و priority نیز برابر است با الویت اصلی ترد که اسکجولینگ به وسیله‌ی آن انجام می‌شود و در هنگان donation کاربرد دارد.

لیست locks نیز برای نگداری قفل‌هایی است که این ترد در اختیار دارد.

آرگومان wait_lock نیز برای نگداری قفلی است که ترد برای گرفتن آن بلاک شده است.

پرسش دوم: داده‌ساختارهایی که برای اجرای priority donation استفاده شده‌است را توضیح دهید. (می‌توانید تصویر نیز قرار دهید)

تمام داده‌ساختار‌های تعریف شده در بالا در این اتفاق نقش دارند. بدین صورت که هنگامی که یک ترد قفلی را می‌گیرد، استراکت آن قفل به locks آن ترد اضافه می‌شود. و زمانی که آن قفل آزاد می‌شود هم از آن حذف می‌شود. حال توجه کنید که زمانی که قرار است یک ترد برای یک قفل صبر کند، آن قفل را در متغیر wait_lock نگه می‌داریم. در ادامه چک می‌کنیم تردی که در حال حاضر این قفل را در اختیار دارد الویتش از تردی که قفل را می‌خواد کمتر است یا نه. اگر کمتر بود عملیات donation انجام می‌شود و. توجه کنید که ممکن است خود آن ترد نیز در حال انتظار برای یک قفل دیگر باید که در این صورت donation به صورت تو در تو انجام می‌شود و عملیت عوض کردن الویت این ترد‌ها همگی با هم انجام می‌شود.

متغیر base_priority برای نگهداری الویت اصلی و اولیه ترد است و متغیرpriority نیز برای نگهداری الویتی است که پس از انچام donation ترد دارد است. در واقع عملیات‌ها با توجه به متغیر priority انجام می‌شوند و متغیر base_priority برای نگهداری مقدار اولیه‌ی الویت و بازگردانی ان پس از اتمام بلاک ترد‌ها است.

الگوریتم

پرسش سوم: چگونه مطمئن می‌شوید که ریسه با بیشترین اولویت که منتظر یک قفل، سمافور یا condition variable است زودتر از همه بیدار می‌شود؟

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

پرسش چهارم: مراحلی که هنگام صدازدن lock_acquire() منجر به priority donation می‌شوند را نام ببرید. دونیشن‌های تو در تو چگونه مدیریت می‌شوند؟

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

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

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

در انتها نیز interruptها را فعال می‌کنیم.

برای مدیریت donationهای تو در تو نیز لیستی از‌ ترد‌هایی که منتظر ترد اولی هستند (wait_lock) داریم که همین عملیات را با آنها نیز انجام می‌دهیم.

فقط توجه کنید که برای جلوگیری از سربار اضافی و بروز مشکلات این کار را حداکثر به اندازه‌ی MAX_DONATION_LEVEL انجام می‌دهیم.

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

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

در ابتدا interruptها را غیرفعال می‌کنیم.

در ادامه نگه‌دارنده‌ی این قفل را نال می‌کنیم و sema_up را صدا می‌زنیم. در ادامه لیست تمام قفل‌هایی(locks) که این ترد در اختیار دارد را چک می‌کنیم. اگر این لیست خالی بود الویت ترد را به اولویت اولیه‌اش برمی‌گردانیم. اما اگر این لیست خالی نبود، الویت ترد را برابر با بیشتر الویت قفل‌های آن قرار می‌دهیم.

در انتها interruptها را فعال می‌کنیم.

همگام‌سازی

پرسش ششم: یک شرایط احتمالی برای رخداد race condition در thread_set_priority را بیان کنید و توضیح دهید که چگونه پیاده‌سازی شما از رخداد آن جلوگیری می‌کند. آیا می‌توانید با استفاده از یک قفل از رخداد آن جلوگیری کنید؟

از جمله مشکلاتی که ممکن است رخ دهد ایت است که در هنگام عملیات donation الویت ترد از طریق دیگری بخواهد عوض شود. برای جلوگیری از این اتفاق در شروع عملیات هندل کردن donation تمام interrupt ها را غیر فعال می‌کنیم.

منطق

پرسش هفتم: چرا این طراحی را استفاده کردید؟ برتری طراحی فعلی خود را بر طراحی‌های دیگری که مدنظر داشته‌اید بیان کنید.

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

سوالات افزون بر طراحی

پرسش هشتم: در کلاس سه صفت مهم ریسه‌ها که سیستم عامل هنگامی که ریسه درحال اجرا نیست را ذخیره می‌کند، بررسی کردیم:‍‍ program counter ، ‍‍‍stack pointer و registers. بررسی کنید که این سه کجا و چگونه در Pintos ذخیره می‌شوند؟ مطالعه ‍switch.S و تابع ‍schedule در فایل thread.c می‌تواند مفید باشد.

پیش از هر چیز خوب است با ساختار کلاسthread در Pintos آشنا شویم.

struct thread
  {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    uint8_t *stack;                     /* Saved stack pointer. */
    ...
};

می‌بینیم که یکی از اعضای این کلاس، اشاره‌گر پشته برای ریسه مورد نظر است. پس از اطمینان از اینکه ترد مربوطه دیگر در حال اجرا نیست، و اشاره‌گر next نیز به یک ترد معتبر اشاره می‌کند، تابع switch_threads فراخوانی می‌شود.

در این تابع نیز، مقادیر چهار ثبات در پشته قرار داده می‌شوند.:

	pushl %ebx
	pushl %ebp
	pushl %esi
	pushl %edi

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

next (esp+24)
cur (esp+20)
RETURN ADDRESS (esp+16)
ebx (esp+12)
ebp (esp+8)
esi (esp+4)
edi (esp+0)

سپس، باید متغیر cur->thread را تغییر دهیم. البته از آنجا که نمی‌توانیم به اعضای یک استراکت در اسمبلی اشاره کنیم، از متغیر thread_stack_ofs به عنوان آفست استفاده می‌کنیم. طبق آنچه در switch.h آمده‌است، از SWITCH_CUR گه معادل 20 و SWITCH_NEXT که معادل 24 است استفاده می‌کنیم.

	# Save current stack pointer to old thread's stack, if any.
	movl SWITCH_CUR(%esp), %eax
	movl %esp, (%eax,%edx,1)

	# Restore stack pointer from new thread's stack.
	movl SWITCH_NEXT(%esp), %ecx
	movl (%ecx,%edx,1), %esp

اینگونه، مقادیر چهار رجیستر گفته شده، فریم استک ریسه، و ریترن آدرس (که بیانگر همان program counter است) در حافظه ذخیره می‌شوند. در نهایت نیز چون مقدار esp بروزرسانی می‌شود، به استک فریم و باقی منابع ترد جدید دسترسی خواهیم داشت.

پرسش نهم: وقتی یک ریسه‌ی هسته در ‍Pintos تابع thread_exit را صدا می‌زند، کجا و به چه ترتیبی صفحه شامل پشته و TCB یا struct thread آزاد می‌شود؟ چرا این حافظه را نمی‌توانیم به کمک صدازدن تابع ‍palloc_free_page داخل تابع ‍thread_exit آزاد کنیم؟

زمانی که تابع thread_exit صدا زده می‌شود، مقدار status این thread به THREAD_DYING تغییر می‌کند و سپس تابع schedule صدا زده می‌شود، سپس در انتهای این تابع وارد تابع thread_schedule_tail می‌شویم. در انتهای این تابع چک می‌شود که آیا status ترد قبلی THREAD_DYING است و اگر بود palloc_free_page انجام می‌شود.

دلیلی که نمی‌توانیم palloc_free_page را قبل از schedule انجام دهیم این است که ابتدا باید thread بعدی را مشخص کنیم و سپس ترد اجرایی را عوض کنیم و سپس ترد قبلی را آزاد کنیم چون تا قبل از عوض شدن ترد به اطلاعات آن نیاز داریم.

پرسش دهم: زمانی که تابع ‍thread_tick توسط timer interrupt handler صدا زده می‌شود، در کدام پشته اجرا می‌شود؟

به دلیل این که این تابع در حالت کرنل اجرا می‌شود، همواره داخل پشته‌ی کرنل اجرا خواهد شد.

پرسش یازدهم: یک پیاده‌سازی کاملا کاربردی و درست این پروژه را در نظر بگیرید که فقط یک مشکل درون تابع ‍sema_up() دارد. با توجه به نیازمندی‌های پروژه سمافورها(و سایر متغیرهای به‌هنگام‌سازی) باید ریسه‌های با اولویت بالاتر را بر ریسه‌های با اولویت پایین‌تر ترجیح دهند. با این حال پیاده‌سازی ریسه‌های با اولویت بالاتر را براساس اولویت مبنا Base Priority به جای اولویت موثر ‍Effective Priority انتخاب می‌کند. اساسا اهدای اولویت زمانی که سمافور تصمیم می‌گیرد که کدام ریسه رفع مسدودیت شود، تاثیر داده نمی‌شود. تستی طراحی کنید که وجود این باگ را اثبات کند. تست‌های Pintos شامل کد معمولی در سطح هسته (مانند متغیرها، فراخوانی توابع، جملات شرطی و ...) هستند و می‌توانند متن چاپ کنند و می‌توانیم متن چاپ شده را با خروجی مورد انتظار مقایسه کنیم و اگر متفاوت بودند، وجود مشکل در پیاده‌سازی اثبات می‌شود. شما باید توضیحی درباره این که تست چگونه کار می‌کند، خروجی مورد انتظار و خروجی واقعی آن فراهم کنید.

int main() { // we assume main has priority 1
	semaphore s1(1) , s2(0);
	thread_create(T1);
	thread_yield();
    thread_create(T3);
	thread_create(T2);
	thread_yield();
	return 0;
}

thread T1 with base priority 1:
	sema_down(s1);
	sema_up(s2);
    thread_yield();
	printf("1\n");
	sema_up(s1);

thread T2 with base priority 2:
	sema_down(s2);
	printf("2\n");
	
thread T3 with base priority 3:
	sema_down(s1);
	printf("3\n");

اگر تست بالا را در نظر بگیریم، ابتدا مقادیر سمافورهای s1 و s2 به ترتیب برابر 1 و 0 قرار داده شده‌اند و سپس ترد T1 داخل main ساخته می‌شود و thread_yield انجام می‌شود که باعث می‌شود ترد T1 اجرا شود که مقدار s1 را به 0 و مقدار s2 را به 1 تغییر می‌دهد، و سپس این ترد yield می‌کند ، سپس تردهای T3 و T2 ساخته می‌شوند که چون T3 در ابتدا sema_down(s1) را انجام می‌دهد نیاز دارد تا مقدار s1 مثبت باشد که یعنی T1 باید پایان یافته باشد و ترد T2 به طور مشابه نیاز دارد s2 مثبت باشد که این اتفاق پس از اجرای دو خط اول T1 می‌افتد. حال اگر priority donation به صورت درست پیاده‌سازی شده باشد و از effective priority برای انتخاب اولویت انتخاب شود انتظار داریم ابتدا ترد T1 کامل اجرا شود و سپس ترد T3 و سپس T2 اجرا شوند در نتیجه خروجی مطلوب به صورت زیر خواهد بود.

1
3
2

و اگر فقط از base priority استفاده شود و priority donation نداشته باشیم. پس از yield کردن T1 پس از مدتی چون ترد T3 هنوز blocked است T2 اجرا شده و سپس T1 و سپس T3 اجرا خواهد شد که در این صورت خروجی به صورت زیر خواهد بود.

2
1
3

سوالات نظرسنجی

پاسخ به این سوالات دلخواه است، اما به ما برای بهبود این درس در ادامه کمک خواهد کرد. نظرات خود را آزادانه به ما بگوئید—این سوالات فقط برای سنجش افکار شماست. ممکن است شما بخواهید ارزیابی خود از درس را به صورت ناشناس و در انتهای ترم بیان کنید.

به نظر شما، این تمرین گروهی، یا هر کدام از سه وظیفه آن، از نظر دشواری در چه سطحی بود؟ خیلی سخت یا خیلی آسان؟

چه مدت زمانی را صرف انجام این تمرین کردید؟ نسبتا زیاد یا خیلی کم؟

آیا بعد از کار بر روی یک بخش خاص از این تمرین (هر بخشی)، این احساس در شما به وجود آمد که اکنون یک دید بهتر نسبت به برخی جنبه‌های سیستم عامل دارید؟

آیا نکته یا راهنمایی خاصی وجود دارد که بهتر است ما آنها را به توضیحات این تمرین اضافه کنیم تا به دانشجویان ترم های آتی در حل مسائل کمک کند؟

متقابلا، آیا راهنمایی نادرستی که منجر به گمراهی شما شود وجود داشته است؟

آیا پیشنهادی در مورد دستیاران آموزشی درس، برای همکاری موثرتر با دانشجویان دارید؟

این پیشنهادات میتوانند هم برای تمرین‌های گروهی بعدی همین ترم و هم برای ترم‌های آینده باشد.

آیا حرف دیگری دارید؟