project1.1-design.md

تمرین گروهی ۱.۱ - مستند طراحی

گروه

نام و آدرس پست الکترونیکی اعضای گروه را در این قسمت بنویسید.

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

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

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

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

مقدمات

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

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

پاس‌دادن آرگومان

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

در این قسمت تعریف هر یک از struct ها، اعضای struct ها، متغیرهای سراسری یا ایستا، typedef ها یا enum هایی که ایجاد کرده‌اید یا تغییر داده‌اید را بنویسید و دلیل هر کدام را در حداکثر ۲۵ کلمه توضیح دهید.

#define MAX_ARGS 32;

#define MAX_FILENAME_SIZE 1024

char* argv[MAX_ARGS];

int argc;

الگوریتم‌ها

به‌طور خلاصه توضیح دهید چگونه آرگومان‌ها را پردازش کرده‌اید؟ چگونه اعضای argv[] را به ترتیب درست در پشته قرار داده‌اید؟ و چگونه از سرریز پشته جلوگیری کرده‌اید؟

ابتدا به وسیله تابع strtok_r() رشته ورودی را parse , tokenize می‌کنیم. در همین حال می‌توانیم مقدار argc را محاسبه کنیم. پس از این، به ترتیبی که در 8086 calling convention در مستند رفرنس پروژه (صفحه 14) آمده است، ابتدا آرگومان‌های argv را از راست به چپ در استک push می‌کنیم. حال برای اطمینان از aligned بودن پوینتر (که موجب تسریع دسترسی به آرگومان‌های بعد می‌شود) استک را align می‌کنیم. برای این کار باید استک پوینتر به یک آدرس مضرب 4 اشاره کند.

پس از اطمینان از این مورد، باید آدرس های المان های argv را (دوباره از راست به چپ) در استک قرار دهیم. حال بار دیگر استک را align می‌کنیم، ولی این بار با توجه به اینکه در 8086 ABI لازم است هر پوینتر استک به صورت 16 بایتی align شده باشد. با توجه به اینکه سه عنصر argv، argc، و return address نیز باید در استک قرار بگیرند، alignment مورد نیاز را انجام می‌دهیم.

توجه کنید که باید قبل از اجرای filesys_open در تابع load عملیات توکنایز رشته‌ی ورودی انجام شود و تنها نام فایل اجرایی به این تابع پاس داده شود. پوش‌ کردن آرگومان‌ها درون استک را نیز درون تابع stack_setup انجام می‌دهیم.

منطق طراحی

چرا Pintos به‌جای تابع‌ strtok() تابع‌ strtok_r() را پیاده‌سازی کرده‌است؟

تابع strtok_r بر خلاف strtok یک تابع thread safe است؛ به این معنی که در صورت استفاده در یک سیستم multithread دچار مشکل نمی‌شود. ولی strtok به دلیل استفاده از متغیر ایستا درون خود، در صورت فراخوانی روی چند رشته به صورت همزمان عملکرد مناسبی نخواهد داشت.

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

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

۲. انعطاف بیشتری هنگام نوشتن shell ها خواهیم داشت. از آنجا که parse کردن در شل ها انجام می‌شود، می‌توانیم پیش پردازش‌های پیچیده‌تری در این مرحله انجام دهیم.

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

فراخوانی‌های سیستمی

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

در این قسمت تعریف هر یک از struct ها، اعضای struct ها، متغیرهای سراسری یا ایستا، typedef ها یا enum هایی که ای.جاد کرده‌اید یا تغییر داده‌اید را بنویسید و دلیل هر کدام را در حداکثر ۲۵ کلمه توضیح دهید.

// defile this on thread.h for specify max of number of opend files.

#define MAX_OPEN_FILE 1024

// defile this on thread.h for specify structure of file descriptor.
struct FD { 
  int id;
  struct file * file_pointer;
}

// defile this on syscall.c for handling access of only one thread to file at the time.
static struct lock file_lock; 

struct thread {
  ...
#ifdef USERPROG
  ...

  // list of all the child threads
  struct list childrens;

  // status of this thread (beacause only one thread can run in a proccess)
  struct process_status *status;

  // list of all file descriptors for this thread
  struct FD *fd[MAX_OPEN_FILE];

#endif
  ...
};

struct thread_status { 

    // proccess of this thread
    pid_t pid;

    int exit_code;

    struct semaphore sema;

    struct list_elem elem;

    // we define this variable to dedicate number of threads that access to this status and use it for free space
    // at the begining this variable set to 2 (parent anc child)
    int ref_count;

    // for locking ref_count for Avoiding race condition
    struct lock lock; 

};

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

برای هندل کردن این کار به ساختار thread یک لیست از FD ها اضافه می‌کنیم که هر کدام اشاره‌گر به یک فایل باز شده و همچنین شماره‌ی file descriptor آن قایل دارد.

از ظرفی توجه کنید که برای کنترل هر thread یک متغیر به نام MAX_OPEN_FILE به صورت گلوبال تعریف می‌کنیم که نشان‌گر حداکثر تعداد فایلی هست که هر پردازه می‌تواند باز کند.

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

الگوریتم‌ها

توضیح دهید خواندن و نوشت ن داده‌های کاربر از داخل هسته، در کد شما چگونه انجام شده است.

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

۱. ابتدا چک می‌کنیم که تمام فایلی که قرار است open شود برای برنامه‌ی کاربر در دسترس است.

۲. در این قسمت چک می‌کنیم که کاربر قصد خواند از STDOUT و همچنین قصد نوشتن در STDIN را نداشته باشد چرا که این عملیات‌ها غیرمجاز و تعریف نشده اند.

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

فرض کنید یک فراخوانی سیستمی باعث شود یک صفحه‌ی کامل (۴۰۹۶ بایت) از فضای کاربر در فضای هسته کپی شود. بیشترین و کمترین تعداد بررسی‌‌های جدول صفحات (page table) چقدر است؟ (تعداد دفعاتی که pagedir_get_page() صدا زده می‌شود.) در‌ یک فراخوانی سیستمی که فقط ۲ بایت کپی می‌شود چطور؟ آیا این عددها می‌توانند بهبود یابند؟ چقدر؟

در حالت فایل ۴۰۹۶ بایتی:

در صورتی که کل فایل در یک page باشد با یک بار فراخوانی عملیات انجام می‌شود ولی اگر هر بایت از فایل در یک page متفاوت باشد نیاز داریم ۴۰۹۶ فراخوانی انجام دهیم. بنابراین در این حالت حداقل ۱ و حاکثر ۴۰۹۶ فراخوانی خواهیم داشت.

در حالت فایل ۲ بایتی:

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

پیاده‌سازی فراخوانی سیستمی wait را توضیح دهید و بگویید چگونه با پایان یافتن پردازه در ارتباط است.

هر باری که سیستم‌کال wait اجرا می‌شود ابتدا همانند بقیه سیستم‌کال‌ها ورودی‌ها(پوینترها) را ولیدیت می‌کنیم و پس از آن status ترد مورد نظر را پیدا کرده و ابتدا چک می‌شود که اگر ref_count آن کمتر از ۲ بود بدین معنی است که دیگر تردی به این status دسترسی ندارد و می‌توان آن را free کرد. در غیر این صورت نیز با استفاده از sema_down منتظر پایان‌یافتن ترد فرزند می‌شویم. همچنین توجه کتید که تر فرزند در process_exit مقدار semaphore را افزایش می‌دهد.

بنابراین ساختار سیستم‌کال wait با استفاده از thread_status و semaphore انجام می‌شود.

هر دستیابی هسته به حافظه‌ی برنامه‌ی کاربر، که آدرس آن را کاربر مشخص کرده است، ممکن است به دلیل مقدار نامعتبر اشاره‌گر منجر به شکست شود. در این صورت باید پردازه‌ی کاربر خاتمه داده شود. فراخوانی های سیستمی پر از چنین دستیابی‌هایی هستند. برای مثال فراخوانی سیستمی write‍ نیاز دارد ابتدا شماره‌ی فراخوانی سیستمی را از پشته‌ی کاربر بخواند، سپس باید سه آرگومان ورودی و بعد از آن مقدار دلخواهی از حافظه کاربر را (که آرگومان ها به آن اشاره می کنند) بخواند. هر یک از این دسترسی ها به حافظه ممکن است با شکست مواجه شود. بدین ترتیب با یک مسئله‌ی طراحی و رسیدگی به خطا (error handling) مواجهیم. بهترین روشی که به ذهن شما می‌رسد تا از گم‌شدن مفهوم اصلی کد در بین شروط رسیدگی به خطا جلوگیری کند چیست؟ همچنین چگونه بعد از تشخیص خطا، از آزاد شدن تمامی منابع موقتی‌ای که تخصیص داده‌اید (قفل‌ها، بافر‌ها و...) مطمئن می‌شوید؟ در تعداد کمی پاراگراف، استراتژی خود را برای مدیریت این مسائل با ذکر مثال بیان کنید.

برای این‌که بخش error handling در کد کوتاه بماند و باعث گم‌شدن هدف اصلی کد نشود برای آن یک تابع تعریف می‌کنیم.

int validate_memory_access(void *pointer, size_t size);

وظیفه‌ی این تابع این است که از NULLنبودن پوینتر اطمینان حاصل کند و سپس بررسی کند که آیا مقداری که این پوینتر به آن اشاره می‌کند در بازه‌ی مجاز برای دسترسی کاربر است یا نه. در نهایت خروجی تابع به ما نشان می‌دهد که آیا دسترسی به مقدار pointer به‌اندازه size یک دسترسی مجاز است یا خیر.

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

همگام‌سازی

فراخوانی سیستمی exec نباید قبل از پایان بارگذاری فایل اجرایی برگردد، چون در صورتی که بارگذاری فایل اجرایی با خطا مواجه شود باید -۱ برگرداند. کد شما چگونه از این موضوع اطمینان حاصل می‌کند؟ چگونه وضعیت موفقیت یا شکست در اجرا به ریسه‌ای که exec را فراخوانی کرده اطلاع داده می‌شود؟

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

بدین صورت که بعد از ساخته شدن درست thread تابع sema_down صدا زده می‌شود و سپس در زمانی که process می‌خواد شروع کند(start_process) تابع sema_up را صدا می‌زنیم. بنابراین با این کار اطمینان حاصل می‌کنیم که اگر فایل درست لود نشد exit کد مناسب برگردانده می‌شود .

پردازه‌ی والد P و پردازه‌ی فرزند C را درنظر بگیرید. هنگامی که P فراخوانی wait(C) را اجرا می‌کند و C هنوز خارج نشده است، توضیح دهید که چگونه همگام‌سازی مناسب را برای جلوگیری از ایجاد شرایط مسابقه (race condition) پیاده‌سازی کرده‌اید. وقتی که C از قبل خارج شده باشد چطور؟ در هر حالت چگونه از آزاد شدن تمامی منابع اطمینان حاصل می‌کنید؟ اگر P بدون منتظر ماندن، قبل از C خارج شود چطور؟ اگر بدون منتظر ماندن بعد از C خارج شود چطور؟ آیا حالت‌های خاصی وجود دارد؟

برای حل این مسئله از متغیر ref_count استفاده می‌کنیم. این متغیر بیان می‌کند که چند thread در حال حاضر به این status دسترسی دارند. از طرفی نیز برای جلوگیری کردن از race condition بر روی این متغیر از متغیر lock استفاده می‌کنیم.

بنابراین در زمانی که ref_count صفر شود منابع را آزاد می‌کنیم. چرا که دیگر thread ای از این status استفاده نمی‌کند.

منطق طراحی

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

همان‌طور که پیش‌تر اشاره کردیم، ابتدا از صحیح‌بودن پوینتری که برنامه سطح کاربر مقدار dereferenceشده آن را می‌خواهد اطمینان حاصل می‌کنیم و سپس این مقدار را dereference می‌کنیم و به کاربر برمی‌گردانیم. در این روش از فانکشن‌های فایل‌های pagedir.c و vaddr.h استفاده خواهیم کرد.

طبق داکیومنت انگلیسی warm-up یک روش دیگر این است که ابتدا تنها از این‌که پوینتر به محلی زیر PHYS_BASE اشاره می‌کند اطمینان حاصل کنیم و سپس اقدام به dereference کنیم. در این صورت پوینترهای invalid باعث page fault می‌شوند که بعدا می‌تواند توسط کرنل مدیریت شود.

روش اول ساده‌تر و روش دوم (به دلیل استفاده از MMU پردازنده) سریع‌تر است. ما به دلیل سادگی روش اول را برگزیدیم.

طراحی شما برای توصیف‌کننده‌های فایل چه نقاط قوت و ضعفی دارد؟

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

از نفاط ضعف می‌توان به این مسئله اشاره کرد که اولا به دلیل کمبود ریسورس تعداد‌ توصیف‌کننده‌ی هر thread محدود است. همچنین توجه کنید که چون توصیف‌کننده‌ها را در استراکت thread ذخیره می‌کنیم همین باعث می‌شود که این ساحتار خیلی بهینه از حافظه استفاده نکند و سنگین شود.

در حالت پیش‌فرض نگاشت tid به pid یک نگاشت همانی است. اگر این را تغییر داده‌اید، روی‌کرد شما چه نقاط قوتی دارد؟

چون single thread هستیم این نگاشت را عوض نکردیم.

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

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

تست مورد نظر، تست sc-bad-sp است. تنها خط این تست خط زیر است که یک دستور اسمبلی را اجرا می‌کند.

asm volatile ("movl $.-(64*1024*1024), %esp; int $0x30");

در این‌جا ابتدا دستور زیر اجرا می‌شود.

movl $.-(64*1024*1024), %esp

این دستور مقدار esp را به مقدار PC - 64 * 1024 * 1024 تغییر می‌دهد که مقداری نامعتبر است.

سپس دستور زیر اجرا می‌شود.

int $0x30

این دستور یک interrupt انجام می‌دهد که با توجه به نامعتبر بودن esp باید exit(-1) کند ولی با توجه به این که این قسمت هنوز پیاده‌سازی نشده با خطای page fault روبرو می‌شود.

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

تست مورد نظر، تست sc-bad-arg است. تنها خط این تست خط زیر است که یک دستور اسمبلی را اجرا می‌کند.

asm volatile ("movl $0xbffffffc, %%esp; movl %0, (%%esp); int $0x30": : "i" (SYS_EXIT));

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

movl $0xbffffffc, %%esp

movl %0, (%%esp)

int $0x30

دستور اول esp را به مکان 0xbffffffc می‌برد و دستور دوم مقدار SYS_EXIT را داخل آدرس esp قرار می‌دهد که آرگومان آن از آدرس PHYS_BASE = 0xc0000000 بیرون می‌زند و در این قسمت با توجه به این که از PHYS_BASE بیرون زدیم باید exit(-1) انجام شود. در نهایت آدرس سوم یک interrupt انجام می‌دهد.

توجه کنید که با سینتکس زیر می‌توانیم به دستور اسمبلی input و output بدهیم که دراینجا SYS_EXIT به عنوان %0 در کد اسمبلی جایگزین می‌شود.

asm ( "assembly code"
           : output operands                  /* optional */
           : input operands                   /* optional */
           : clobbered registers              /* optional */
);

در آخر توجه کنید که در هیچ تستی خواندن از STDERR که کاری اشتباه است چک نشده است که موجب به error شود.

سوالات نظرخواهی

پاسخ به این سوالات اختیاری است، ولی پاسخ به آن‌ها می‌تواند به ما در بهبود درس در ترم‌های آینده کمک کند. هر چه در ذهن خود دارید بگویید. این سوالات برای دریافت افکار شما هستند. هم‌چنین می‌توانید پاسخ خود را به صورت ناشناس در انتهای ترم ارائه دهید.

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

آیا شما بخشی را در تمرین یافتید که دید عمیق‌تری نسبت به طراحی سیستم عامل به شما بدهد؟

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

آیا توصیه‌ای برای دستیاران آموزشی دارید که چگونه دانشجویان را در ترم‌های آینده یا در ادامه‌ی ترم بهتر یاری کنند؟

اگر نظر یا بازخورد دیگری دارید در این قسمت بنویسید.