گروه: ۶
نام و آدرس پست الکترونیکی اعضای گروه را در این قسمت بنویسید.
پارسا حسینی sp.hoseiny@gmail.com
علیرضا دهقانپور فراشاه alirezafarashah@gmail.com
آرمان بابایی 292arma@gmail.com
مهدی سلمانی صالح‌آبادی m10.salmani@gmail.com
مقدمات
اگر نکات اضافه‌ای در مورد تمرین یا برای دستیاران آموزشی دارید در این قسمت بنویسید.
لطفا در این قسمت تمامی منابعی (غیر از مستندات Pintos، اسلاید‌ها و دیگر منابع درس) را که برای تمرین از آن‌ها استفاده کرده‌اید در این قسمت بنویسید.
داده‌ساختار‌ها
در این قسمت تعریف هر یک از
structها، اعضایstructها، متغیرهای سراسری یا ایستا،typedefها یاenumهایی که ایجاد کرده‌اید یا تغییر داده‌اید را بنویسید و دلیل هر کدام را در حداکثر ۲۵ کلمه توضیح دهید.
در این قسمت نیازی به داده ساختار خاصی نیست. یک تابع tokenize پیاده میکنیم که file_name را ورودی گرفته و متغیرهای استاتیک argc (تعداد آرگومانهای ورودی) و argv (لیست آرگومان‌ها) را ست کند. برای تعریف این متغیرها در ابتدای کد process.c به شکل زیر عمل میکنیم:
#define MAX_ARGUMENTS 32;
char* argv[MAX_ARGUMENTS];
int argc;
bool tokenize(char* file_name);دقت کنید خروجی تابع tokenize اگر محدودیت‌ها رعایت شده باشد، True خواهد بود و در غیر این صورت False.
به دلایلی که در ادامه گفته‌ایم برای پیاده‌سازی tokenize از تابع strtok_r() استفاده میکنیم.
الگوریتم‌ها
به‌طور خلاصه توضیح دهید چگونه آرگومان‌ها را پردازش کرده‌اید؟ چگونه اعضای
argv[]را به ترتیب درست در پشته قرار داده‌اید؟ و چگونه از سرریز پشته جلوگیری کرده‌اید؟
برای این قسمت تنها باید دو تابع در فایل process.c عوض شود. در ادامه این دو تابع و تغییراتشان را توضیح داده‌ایم.
static bool load (const char *cmdline, void (**eip) (void), void **esp);در این تابع قبل از اینکه filesys_open صدا زده شود، باید تابع tokenize که زدیم صدا زده شده و argc و argv ست شوند. بعد باید به آن argv[0] پاس داده شود. (اسم فایل اجرایی) همچنین باید setup_stack هم در این تابع عوض شود که esp و argc و argv را به عنوان ورودی بگیرد.
static bool setup_stack (void **esp, int argc, char* argv);این تابعی است که تغییرات اصلی در آن صورت می‌گیرد. بعد از install_page در داخل if، باید آرگومان‌ها را به ترتیب درست در پشته قرار دهیم. برای اینکار ابتدا رشته tokenize شده دستور را در پشته قرار داده، و هر بار esp را کم میکنیم. سپس باید alignment را چک کرد و جای خالی در صورت لزوم قرار داد. (این فضای خالی به خاطر معماری x86 است که در داک انگلیسی پروژه در صفحه شماره 19 توضیح داده شده) حالا باید argv را قرار دهیم، برای این اول یک NULL قرار می‌دهیم. (منظور همان argv[argc] است) بعد به ترتیب از argv[argc-1] شروع کرده و آدرس کلمه متناظر آن که قبلا پوش کردیم را قرار داده و esp را کم میکنیم تا به argv[0] برسیم. و بعد هم خود آدرس argv را قرار می‌دهیم. argc بعد از آن قرار گرفته و در انتها return address (به صورت fake) را می‌گذاریم. در انتها مقدار esp به خانه return address اشاره خواهد کرد.
دقت کنید که تابع strtok_r() پوینتر به شروع هر توکن داده و بین توکن‌ها را هم با NULL پر میکند.
برای این پشته سرریز نکند هم مرتب چک میکنیم که مقادیر esp معتبر باشد. (اگر از محدوده مدنظر خارج شد، False برمی‌گرداند.)
منطق طراحی
چرا Pintos به‌جای تابع
strtok()تابعstrtok_r()را پیاده‌سازی کرده‌است؟
دلیل اصلی این نحوه پیاده‌سازی thread safe بودن strtok_r() است. حالتی را تصور کنید که از strtok() استفاده می‌کرد و دو ریسه همزمان آن را صدا می‌کردند. بخاطر اینکه آخرین توکن به صورت داخلی و استاتیک توسط خود تابع پیاده‌سازی شده،ممکن است race condition پیش بیاید و یک ریسه آخرین توکن ریسه دیگر را استفاده کند. در کل این نحوه پیاده‌سازی کمک میکند که بتوان از ریسه‌های مختلف و به صورت همزمان رشته‌ها را tokenize کرد.
در Pintos عمل جدا کردن نام فایل از آرگومان‌ها، در داخل کرنل انجام میشود. در سیستم عامل‌های برپایه‌ی Unix، این عمل توسط shell انجام میشود. حداقل دو مورد از برتری‌های رویکرد Unix را توضیح دهید.
این عمل باعث میشود که هسته دیگر درگیر parsing و چک کردن خطا نشده و در نتیجه زمان داخل هسته کم شود. بجای آن این چک‌ها در سمت کاربر انجام میشود. یعنی در سمت کاربر چک شود که فایل اجرایی است یا نه، یا مثلا تعداد آرگومان‌ها کمتر از حد مجاز است. پس اینکار هم پیاده‌سازی کرنل را ساده میکند، هم چک کردن دسترسی و موارد امنیتی را ساده میکند و قابلیت انعطاف بیشتری هم به ما می‌دهد. در این حالت می‌توان بدون تغییر هسته تعداد زیادی مفسر shell داشت، و این مفسرها می‌توانند پیش‌پردازش‌های پیشرفته‌تری روی دستورات اعمال کنند.
داده‌ساختار‌ها
در این قسمت تعریف هر یک از
structها، اعضایstructها، متغیرهای سراسری یا ایستا،typedefها یاenumهایی که ای.جاد کرده‌اید یا تغییر داده‌اید را بنویسید و دلیل هر کدام را در حداکثر ۲۵ کلمه توضیح دهید.
// pintos/src/threads/thread.h
#define MAX_FILE_DESCRIPTORS 128
struct child_parent_status {
pid_t pid;
int exit_code;
struct list_elem elem;
struct semaphore sema; // init to 0
int ref_count; // at first it is 2 showing number of threads working with this status
struct lock lock; // for locking ref_count
};
// An struct for keeping track of open files.
struct fd {
int fd;
struct file* file;
};
struct thread {
....
struct list children;
struct child_parent_status cps;
// This keeps track of what file descriptors thread has.
struct fd* descriptors[MAX_FILE_DESCRIPTORS];
};// pintos/src/userprog/syscall.c
struct lock file_lock; // The global lock for synchronization of all file operations.توضیح دهید که توصیف‌کننده‌های فایل چگونه به فایل‌های باز مربوط می‌شوند. آیا این توصیف‌کننده‌ها در کل سیستم‌عامل به‌طور یکتا مشخص می‌شوند یا فقط برای هر پردازه یکتا هستند؟
توضیف‌کننده‌ها تنها در سطح پردازه‌ها یکتا هستند. همان‌طور که در ساختارthread مشخص است، هر پردازه تعداد MAX_FILE_DESCRIPTORS پرونده در اختیار دارد. این پرونده‌ها بین پردازه‌های مختلف ممکن است مشترک باشند، با این وجود از طرق متفاوتی به آن‌ها دسترسی دارند.
الگوریتم‌ها
توضیح دهید خواندن و نوشتن داده‌های کاربر از داخل هسته، در کد شما چگونه انجام شده است.
برای هر دوی خواندن و نوشتن نیاز داریم که مطمئن شویم تمام بازه‌ی مشخص‌شده از ابتدا تا انتها برای پردازه قابل‌دسترسی است. در صورتی که این‌طور نبود خطای -1 را برمی‌گردانیم. در غیر این‌صورت قفل file_lock را در اختیار می‌گیریم.
از آن‌جایی که خواندن از STDOUT_FILENO و نوشتن در STDIN_FILENO مجاز نیست، در ابتدا چک میکنیم که برای خواندن از پرونده‌ی STDOUT_FILENO و برای نوشتن از پرونده‌ی STDIN_FILENO استفاده نشده باشد. در صورتی که این‌طور نبود عملیات خواندن و یا نوشتن را انجام می‌دهیم، قفل file_lock را آزاد میکنیم و نتیجه‌ی موفقیت‌آمیز (0) برمی‌گردانیم.
فرض کنید یک فراخوانی سیستمی باعث شود یک صفحه‌ی کامل (۴۰۹۶ بایت) از فضای کاربر در فضای هسته کپی شود. بیشترین و کمترین تعداد بررسی‌‌های جدول صفحات (page table) چقدر است؟ (تعداد دفعاتی که
pagedir_get_page()صدا زده میشود.) در یک فراخوانی سیستمی که فقط ۲ بایت کپی میشود چطور؟ آیا این عددها می‌توانند بهبود یابند؟ چقدر؟
در حالتی که کل اطلاعات در یک صفحه باشد به یک بار فراخوانی بیشتر نیاز نیست.
اگر هر بایت در یک صفحه جدا باشد باید ۴۰۹۶ بار این تابع صدا زده شود.
اگر دو بایت بخوانیم نیز حداکثر نیاز به ۲ بار فراخوانی داریم و حداقل ۱ بار.
پیاده‌سازی فراخوانی سیستمی
waitرا توضیح دهید و بگویید چگونه با پایان یافتن پردازه در ارتباط است.
این گونه پیاده سازی شده است که بعد از دستور wait پردازه فرزند را از لیست فرزندان پیدا میکند و سپس با sema down پدر منتظر پایان یافتن فرزند میشود و همواره فرزند در process_exit مقدار sema را زیاد میکند.
بنابراین با پایان یافتن ترد فرزند سمافور در فرزند
sema up
میشود و در صورت وجود
wait
ترد والد منتظر پایان یافتن ترد فرزند میشود.
هر دستیابی هسته به حافظه‌ی برنامه‌ی کاربر، که آدرس آن را کاربر مشخص کرده است، ممکن است به دلیل مقدار نامعتبر اشاره‌گر منجر به شکست شود. در این صورت باید پردازه‌ی کاربر خاتمه داده شود. فراخوانی های سیستمی پر از چنین دستیابی‌هایی هستند. برای مثال فراخوانی سیستمی
writeنیاز دارد ابتدا شماره‌ی فراخوانی سیستمی را از پشته‌ی کاربر بخواند، سپس باید سه آرگومان ورودی و بعد از آن مقدار دلخواهی از حافظه کاربر را (که آرگومان ها به آن اشاره می کنند) بخواند. هر یک از این دسترسی ها به حافظه ممکن است با شکست مواجه شود. بدین ترتیب با یک مسئله‌ی طراحی و رسیدگی به خطا (error handling) مواجهیم. بهترین روشی که به ذهن شما می‌رسد تا از گم‌شدن مفهوم اصلی کد در بین شروط رسیدگی به خطا جلوگیری کند چیست؟ همچنین چگونه بعد از تشخیص خطا، از آزاد شدن تمامی منابع موقتی‌ای که تخصیص داده‌اید (قفل‌ها، بافر‌ها و...) مطمئن می‌شوید؟ در تعداد کمی پاراگراف، استراتژی خود را برای مدیریت این مسائل با ذکر مثال بیان کنید.
برای این منظور ابتدا بررسی میکنیم که آرگومانهای ورودی نال نباشید سپس با استفاده از
is_user_addr
بررسی میکنیم که آیا به خانه ای درست در حافظه مجازی اشاره میکند یا نه.
این تابع در
threads/vaddr.h
که در انتهای صفحه ۱۶ در منابع به آن اشاره شده است آمده.
همچنین با استفاده از
look_page
با دادن
flag
مناسب بررسی میکنیم که آدرس مجازی داده شده به درستی به یک آدرس فیزیکی مپ شده باشد.
این تابع نیز در صفحه ۱۶ به محل قرارگیری اش که
userprog/pagedir.c
است اشاره شده است.
برای آزادسازی منابع نیز همواره بعد از پایان ترد چه پایان یابد چه از بین برود در
process_exit
به آزادسازی منابع آن میپردازیم.
همگام‌سازی
فراخوانی سیستمی
execنباید قبل از پایان بارگذاری فایل اجرایی برگردد، چون در صورتی که بارگذاری فایل اجرایی با خطا مواجه شود باید-۱برگرداند. کد شما چگونه از این موضوع اطمینان حاصل میکند؟ چگونه وضعیت موفقیت یا شکست در اجرا به ریسه‌ای کهexecرا فراخوانی کرده اطلاع داده میشود؟
در این بخش نیز از سمافور درون ترد فرزند استفاده میکنیم که قبل از
start_process
آن را
sema down
میکنیم و درون
start_process
بعد از لود کردن فایل
آن را
sema up
میکنیم.
بنابراین اجرا بعد از لود کردن اتفاق می افتد.
پردازه‌ی والد P و پردازه‌ی فرزند C را درنظر بگیرید. هنگامی که P فراخوانی
wait(C)را اجرا میکند و C هنوز خارج نشده است، توضیح دهید که چگونه همگام‌سازی مناسب را برای جلوگیری از ایجاد شرایط مسابقه (race condition) پیاده‌سازی کرده‌اید. وقتی که C از قبل خارج شده باشد چطور؟ در هر حالت چگونه از آزاد شدن تمامی منابع اطمینان حاصل می‌کنید؟ اگر P بدون منتظر ماندن، قبل از C خارج شود چطور؟ اگر بدون منتظر ماندن بعد از C خارج شود چطور؟ آیا حالت‌های خاصی وجود دارد؟
برای جلوگیری از
race
روی
ref_count
با استفاده از
lock
از استفاده همزمان والد و فزند از این متغیر جلوگیری میکنیم و هر زمانی که این متغیر ۰ شود منابع آن را آزاد میکنیم.
بقیه بخش ها فقط توسط یک ترد مورد استفاده قرار میگیرند به جز
semafor
که خودش به صورت
atomic
اجرا میشود.
منطق طراحی
به چه دلیل روش دسترسی به حافظه سطح کاربر از داخل هسته را این‌گونه پیاده‌سازی کرده‌اید؟
از روش اول که در صفحه ۱۶ منبع گفته شده است استفاده کردیم و دلیل آن راحتی و سادگی آن بود با این که روش دوم سریع تر است.
طراحی شما برای توصیف‌کننده‌های فایل چه نقاط قوت و ضعفی دارد؟
اصلی‌ترین مزیتی که می‌توان برای این روش عنوان کرد، سرعت بیشتر دسترسی به فایل است. چرا که با مشخص کردن شماره‌ی پرونده می‌توان به سرعت توصیف‌کننده‌ی پرونده را از ساختار thread استخراج کرد. مزیت دیگری که می‌توان برای این روش عنوان کرد، این است که مطمئن هستیم یک پردازه تنها به پرونده‌های مربوط به خود دسترسی دارد. علاوه بر این در این روش هر پردازه به سادگی تنها به پرونده‌های خود دسترسی دارد. علاوه بر این بستن پرونده‌ها پیچیدگی کمی دارد. همچنین با محدود شدن توصیف‌کننده‌ها، امکان حمله به سیستم‌عامل از طریق باز کردن پرونده‌های زیاد از بین رفته است.
از طرف دیگر، برای این طراحی، اندازه‌ی ساختار thread به طور فاحش بزرگ‌تر از قبل شد که می‌تواند موجب لختی سیستم شود. علاوه بر این هر پردازه به تعداد محدودی پرونده‌ی باز به طور همزمان دسترسی دارد که برای کاربر سیستم‌عامل محدودیت‌زا است.
در حالت پیش‌فرض نگاشت
tidبهpidیک نگاشت همانی است. اگر این را تغییر داده‌اید، رویکرد شما چه نقاط قوتی دارد؟
تغییری نداده‌ایم.
تستی را که هنگام اجرای فراخوانی سیستمی از یک اشاره‌گر پشته‌ی(esp) نامعتبر استفاده کرده است بیابید. پاسخ شما باید دقیق بوده و نام تست و چگونگی کارکرد آن را شامل شود.
// pintos/src/tests/userprog/sc-bad-sp.c
test_main (void)
{
asm volatile ("movl $.-(64*1024*1024), %esp; int $0x30");
fail ("should have called exit(-1)");
}در این آزمون تلاش میشود که مقدار نشانگر پشته به مقدار -64MB تغییر پیدا کند و پس از آن یک systemcall انجام میشود. با توجه به این که حافظه‌ی پشته اندازه‌ی کوچک‌تری دارد، این مقدار از اندازه‌ی حافظه‌ی پشته بیشتر است و در نتیجه برقرار کردن systemcall با این مقدار باید با خطا مواجه شود و برنامه با مقدار -1 خارج شود.
تستی را که هنگام اجرای فراخوانی سیستمی از یک اشاره‌گر پشته‌ی معتبر استفاده کرده ولی اشاره‌گر پشته آنقدر به مرز صفحه نزدیک است که برخی از آرگومانهای فراخوانی سیستمی در جای نامعتبر مموری قرار گرفته اند مشخص کنید. پاسخ شما باید دقیق بوده و نام تست و چگونگی کارکرد آن را شامل شود.یک قسمت از خواسته‌های تمرین را که توسط مجموعه تست موجود تست نشده‌است، نام ببرید. سپس مشخص کنید تستی که این خواسته را پوشش بدهد چگونه باید باشد.
// pintos/src/tests/userprog/sc-bad-arg.c
test_main (void)
{
asm volatile ("movl $0xbffffffc, %%esp; movl %0, (%%esp); int $0x30"
: : "i" (SYS_EXIT));
fail ("should have called exit(-1)");
}در این آزمون ابتدا استک به ابتدای خود (بیشتری مقدار) برده میشود و مقدار SYS_EXIT در آن نوشته میشود. از آن‌جایی که ورودی systemcall با این وضع، در بالای استک قرار می‌گیرد، لازم است که برنامه با کد خطای -1 خارج شود.
در مورد تستی که می‌توانست در مجموعه تست‌‌ها باشد نیز می‌توان به درستی مدیریت file descriptor (fd) های مربوط به یک فایل اشاره کرد. در واقع درست است که طبق توضیحات در پروژه اول یک global lock استفاده میشود ولی ممکن است در یک ترد از یک فایل دو fd تعریف شود. حال می‌توان چک کرد که آیا این fd ها وضعیت خود را با هم share میکنن یا خیر. برای مثال اگر در یک fd بنویسیم در fd دیگر با خواندن نباید این نوشته‌ها را دید. (مگر اینکه به مثلا از چیزی شبیه dup2 استفاده کنیم.) مثال دیگر نیز بررسی پیاده سازی درست global lock هست. (مثلا پس از close کردن fd توسط یک پراسس، پراسسی دیگر بتواند همان کار با فایل خود را انجام دهد.)
پاسخ به این سوالات اختیاری است، ولی پاسخ به آن‌ها می‌تواند به ما در بهبود درس در ترم‌های آینده کمک کند. هر چه در ذهن خود دارید بگویید. این سوالات برای دریافت افکار شما هستند. همچنین می‌توانید پاسخ خود را به صورت ناشناس در انتهای ترم ارائه دهید.
به نظر شما، این تمرین یا هر یک از سه بخش آن، آسان یا سخت بودند؟ آیا وقت خیلی کم یا وقت خیلی زیادی گرفتند؟
آیا شما بخشی را در تمرین یافتید که دید عمیق‌تری نسبت به طراحی سیستم عامل به شما بدهد؟
آیا مسئله یا راهنمایی خاصی وجود دارد که بخواهید برای حل مسائل تمرین به دانشجویان ترم‌های آینده بگویید؟
آیا توصیه‌ای برای دستیاران آموزشی دارید که چگونه دانشجویان را در ترم‌های آینده یا در ادامه‌ی ترم بهتر یاری کنند؟
اگر نظر یا بازخورد دیگری دارید در این قسمت بنویسید.