مشکلات همگام سازی در سیستم عامل مشکل آرایشگر خواب

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

مشکل ناهار خوردن فیلسوفان

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

زندگی یک فیلسوف شامل دوره های متناوب خوردن و تفکر است. (البته، این یک انتزاع است، حتی همانطور که در مورد فیلسوفان اعمال می شود، اما سایر فرآیندهای زندگی برای وظیفه ما بی اهمیت هستند.) وقتی یک فیلسوف گرسنه است، سعی می کند دو چنگال چپ و راست را به هر ترتیبی بدست آورد. اگر موفق شد دو چنگال به دست آورد، مدتی غذا می خورد، سپس چنگال ها را برمی گرداند و به فکر ادامه می دهد. سوال این است: آیا می توان الگوریتمی نوشت که این اعمال را برای هر فیلسوفی مدل کند و هرگز گیر نکند؟ (بعضی ها فکر می کنند نیاز به دو چنگال کمی مصنوعی است. شاید بهتر باشد غذاهای ایتالیایی را با غذاهای چینی، اسپاگتی را با برنج و چنگال ها را با چاپستیک های مشابه جایگزین کنیم).

می توانید برنامه را طوری تغییر دهید که پس از دریافت چنگال چپ، در دسترس بودن چنگال سمت راست بررسی شود. اگر چنگال سمت راست در دسترس نباشد، فیلسوف چنگال چپ را پس می دهد، مدتی صبر می کند و کل فرآیند را تکرار می کند. این رویکرد نیز کار نخواهد کرد، اگرچه به دلیل دیگری. اگر بدشانس باشید، هر پنج فیلسوف می توانند همزمان این فرآیند را شروع کنند، چنگال چپ را بردارند، کشف کنند که چنگال سمت راست گم شده است، چپ را دوباره روی میز بگذارند، چنگال چپ را همزمان بردارند. ، و غیره تا بی نهایت. وضعیتی که در آن همه برنامه ها به طور نامحدود به کار خود ادامه می دهند، اما حداقل نمی توانند پیشرفت کنند، فریز فرآیند نامیده می شود (در انگلیسی، starvation، به معنای واقعی کلمه «گرسنگی».

این اصطلاح حتی اگر مشکل در رستوران ایتالیایی یا چینی رخ ندهد، بلکه در رایانه ها رخ دهد، صدق می کند.

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

برای جلوگیری از بن‌بست و معلق شدن فرآیند، بهبودی ایجاد کنید: از پنج عبارت زیر درخواست فکر با یک سمافور باینری محافظت کنید. سپس فیلسوف باید قبل از رسیدن به چنگال ها، یک عملیات Down روی متغیر mutex انجام دهد. و پس از برگرداندن فورک ها به جای خود، عملیات Up را روی متغیر mutex انجام دهد. از نقطه نظر نظری، راه حل کاملا مناسب است. از نقطه نظر عملی، مشکلات کارآیی وجود دارد: فقط یک فیلسوف می تواند در هر بار اسپاگتی بخورد. اما پنج چنگال وجود دارد، بنابراین باید به دو فیلسوف اجازه داده شود در هر زمان معین غذا بخورند.

راه حل بن بست را از بین می برد و برای هر تعدادی از فیلسوفان بیشترین توازی ممکن را فراهم می کند. این از آرایه حالت برای ردیابی وضعیت ذهنی هر فیلسوف استفاده می کند: او یا در حال غذا خوردن، فکر کردن، یا گرسنگی است (تلاش برای گرفتن چنگال). فیلسوف تنها زمانی می تواند شروع به خوردن کند که هیچ یک از همسایگانش غذا نخورند. همسایگان فیلسوف با عدد i توسط ماکروهای LEFT و RIGHT تعیین می شوند (یعنی اگر i = 2 باشد، LEFT =

مشکل خوانندگان و نویسندگان

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

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

مشکل آرایشگر خواب

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

راه حل پیشنهادی از سه سمافور استفاده می کند: مشتریان، برای شمارش بازدیدکنندگان منتظر (مشتری که روی صندلی آرایشگر نشسته است در نظر گرفته نمی شود - او دیگر منتظر نیست). آرایشگرها، تعداد آرایشگران (0 یا 1) که در حالت بیکار ایستاده و منتظر مشتری هستند، و یک mutex برای اجرای حذف متقابل. از متغیر انتظار نیز برای شمارش بازدیدکنندگان در انتظار استفاده می شود.

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

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

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

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

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

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

شایان ذکر است که علیرغم عدم انتقال داده در مشکل Readers and Writers و مشکل Sleeping Barber، هر دوی این مشکلات مشکلات ارتباطی بین فرآیندی هستند زیرا نیاز به همگام سازی چندین فرآیند دارند.

مسئله

این قیاس بر اساس یک آرایشگاه فرضی با یک آرایشگر است. آرایشگاه یک ایستگاه کاری و یک پذیرایی با تعداد زیادی صندلی دارد. وقتی آرایشگر کوتاه کردن موهای مشتری را تمام می کند، مشتری را رها می کند و سپس به قسمت پذیرش می رود تا ببیند آیا مشتری منتظر است یا خیر. اگر هست یکی از آنها را دعوت می کند و موهایش را کوتاه می کند. اگر مشتری منتظر نباشد به صندلی خود برمی گردد و روی آن می خوابد.

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

همه مشکلات از این واقعیت ناشی می شود که کلیه اقدامات آرایشگر و مشتری (بررسی محل پذیرایی، ورود به آرایشگاه، نشستن در پذیرایی و ...) زمان نامشخصی می برد. مثلاً ممکن است مشتری وارد شود و متوجه شود که آرایشگر مشغول کار است، سپس به سمت پذیرایی می رود. همینطور که راه می‌رود، آرایشگر آرایش مو را که انجام می‌دهد تمام می‌کند و به اتاق پذیرایی می‌رود. از آنجایی که کسی آنجا نیست (مشکل هنوز نیامده است) به جای خود برمی گردد و می خوابد. آرایشگر در حال حاضر منتظر مشتری است و مشتری منتظر آرایشگر است. در مثالی دیگر، زمانی که تنها یک صندلی خالی در قسمت پذیرش وجود دارد، ممکن است دو مشتری همزمان وارد شوند. متوجه می شوند که آرایشگاه مشغول کار است، به پذیرایی می روند و هر دو سعی می کنند تنها صندلی را بگیرند.

مشکل آرایشگر خواب اغلب به Edsger Dijkstra (1965)، یکی از پیشگامان علوم کامپیوتر نسبت داده می شود.

راه حل

راه حل های ممکن زیادی وجود دارد. عنصر اصلی هر یک mutex است که تضمین می کند که تغییر حالت ( حالت) فقط یکی از شرکت کنندگان می تواند. آرایشگر باید این استثناء mutex را قبل از بررسی مشتریان خود بگیرد و هنگامی که شروع به خواب یا کار کرد آن را رها کند. مشتری باید قبل از ورود به فروشگاه موتکس را بگیرد و پس از نشستن در پذیرایی یا آرایشگاه آن را رها کند. این هر دو مشکل ذکر شده در بخش قبل را برطرف می کند. سمافورها نیز برای نشان دادن وضعیت سیستم مورد نیاز هستند. به عنوان مثال، تعداد افراد در اتاق انتظار می تواند حفظ شود.

گزینه چند آرایشگر پیچیدگی بیشتری در هماهنگی چند آرایشگر در بین مشتریان منتظر دارد.

همچنین ببینید

• مشکل سیگاری ها

پیوندها

• سیستم عامل های مدرن (ویرایش دوم)توسط Andrew S. Tanenbaum (ISBN 0-13-031358-0)
• کتاب کوچک سمافورهاتوسط آلن بی داونی، http://greenteapress.com/semaphores
• همکاری با فرآیندهای متوالیتوسط E.W. دایکسترا. گزارش فنی EWD-123، 1965، دانشگاه فناوری، آیندهوون، هلند.

بنیاد ویکی مدیا 2010.

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

راه حل پیشنهادی از سه سمافور استفاده می کند: مشتریان، برای شمارش بازدیدکنندگان منتظر (مشتری که روی صندلی آرایشگر نشسته است در نظر گرفته نمی شود). آرایشگرها، تعداد آرایشگران (0 یا 1) که در حالت بیکار ایستاده و منتظر مشتری هستند، و یک mutex برای اجرای حذف متقابل. از متغیر انتظار نیز برای شمارش بازدیدکنندگان در انتظار استفاده می شود.

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

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

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

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

تقریباً همه فرآیندها دوره های محاسباتی را با عملیات ورودی/خروجی (دیسک) جایگزین می کنند. به طور معمول، پردازنده برای مدتی بدون توقف کار می کند، سپس یک تماس سیستمی برای خواندن یا نوشتن روی یک فایل برقرار می شود. پس از اجرای فراخوانی سیستم، پردازنده دوباره شمارش می کند تا زمانی که به داده های جدید نیاز داشته باشد یا نیاز به نوشتن داده های دریافتی داشته باشد.

داده ها و غیره

موضوع کلیدی در برنامه ریزی زمان تصمیم گیری است. معلوم می شود که موقعیت های زیادی وجود دارد که در آن برنامه ریزی ضروری است.

ابتدا، هنگامی که یک فرآیند جدید ایجاد می شود، باید تصمیم بگیرید که کدام فرآیند را شروع کنید: والدین یا فرزند. از آنجایی که هر دو فرآیند در حالت آماده هستند، این وضعیت غیرعادی نیست و زمانبندی می تواند هر یک از دو فرآیند را شروع کند.

دوم، برنامه ریزی زمانی ضروری است که یک فرآیند خاتمه یابد. این فرآیند دیگر وجود ندارد، بنابراین، لازم است که یکی دیگر از مجموعه ای از فرآیندهای آماده انتخاب و راه اندازی شود. اگر هیچ فرآیندی در حالت آماده وجود نداشته باشد، معمولاً یک فرآیند غیرفعال ارائه شده توسط سیستم شروع می شود.

ثالثاً، وقتی فرآیندی در ورودی/خروجی، سمافور یا به دلایل دیگری مسدود می‌شود، باید فرآیند دیگری انتخاب و شروع شود. گاهی اوقات دلیل مسدود شدن می تواند بر انتخاب تأثیر بگذارد. به عنوان مثال، اگر A -

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

چهارم، نیاز به زمان بندی ممکن است زمانی ایجاد شود که یک وقفه I/O رخ دهد. اگر وقفه از یک دستگاه ورودی/خروجی می آید که اجرای آن به پایان رسیده است، می توانید فرآیندی را شروع کنید که در انتظار این رویداد مسدود شده است. زمانبند باید انتخاب کند که کدام فرآیند را شروع کند: یک فرآیند جدید، یکی که با یک وقفه متوقف شده است یا یک فرآیند دیگر.

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

1. سیستم های پردازش دسته ای داده ها.

2. سیستم های تعاملی.

3. سیستم های بلادرنگ.

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

سیستم‌های تعاملی نیاز به تغییر الگوریتم‌های زمان‌بندی دارند تا از یک فرآیند درگیر پردازنده جلوگیری شود. حتی اگر هیچ فرآیندی عمداً CPU را به طور نامحدود ربوده باشد، یک باگ در برنامه می‌تواند باعث شود که یکی از فرآیندهای دیگر را مسدود کند. برای حذف چنین موقعیت هایی، از زمان بندی سوئیچینگ استفاده می شود.

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

مشکلات الگوریتم های برنامه ریزی

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

برنامه ریزی در سیستم های پردازش دسته ای داده ها

"اول می آید، اولین خدمت"

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

مزیت اصلی این الگوریتم این است که درک آن آسان و به همان اندازه آسان برای برنامه ریزی است.

اشکال این است که برنامه ریزی کاملاً بهینه نیست.

"کوتاه ترین مشکل اولین مشکل است"

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

مزیت الگوریتم بهینه سازی مسئله است.

نقطه ضعف این است که این طرح فقط در صورت وجود وظایف همزمان کار می کند.

اطلاعات مربوطه.

1.cpp
bradobrej1.dsp
bradobrej1.dsw
bradobrej1.ncb
bradobrej1.opt
bradobrej1.plg
1.obj
bradobrej1.exe
bradobrej1.ilk
bradobrej1.pch
bradobrej1.pdb
vc60.idb
vc60.pdb
bradobrej1.exe
2.cpp
bradobrej2.dsp
bradobrej2.dsw
bradobrej2.ncb
bradobrej2.opt
bradobrej2.plg
2.obj
bradobrej2.exe
bradobrej2.ilk
bradobrej2.pch
bradobrej2.pdb
vc60.idb
vc60.pdb
bradobrej2.exe
	162 کیلوبایت	05.09.2008 12:01

همچنین ببینید:

Lr1.doc

سیستم عامل

کار آزمایشگاهی شماره 1

موضوع:زیر سیستم کنترل فرآیند مشکل خواب آرایشگاه

هدف:با روش های اصلی که در زیر سیستم های کنترل فرآیند استفاده می شود آشنا شوید.

مواد برای مطالعه اولیه:

1. مفهوم و سازماندهی فرآیندها.

2. پیاده سازی فرآیندها در سیستم عامل ویندوز.

3. ابزار زبان C برای کار با فرآیندها.

مطالب نظری

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

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

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

^ 1. شرایط مسابقه.

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

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

تصور کنید که دایرکتوری spooler از تعداد زیادی بخش با شماره های 0، 1، 2، ... تشکیل شده است که هر کدام می توانند یک نام فایل را ذخیره کنند. همچنین دو متغیر مشترک وجود دارد: بیرون،اشاره به فایل بعدی برای چاپ، و که در،به بخش آزاد بعدی اشاره می کند. این دو متغیر را می توان در یک فایل (متشکل از دو کلمه) ذخیره کرد که برای همه فرآیندها قابل دسترسی است. بگذارید قسمت های 0 تا 3 در حال حاضر خالی باشند (این فایل ها قبلاً چاپ شده اند) و بخش های 4 تا 6 اشغال شده باشند (این فایل ها منتظر نوبت چاپ هستند). فرآیندهای کم و بیش همزمان الف و بتصمیم بگیرید که فایل را برای چاپ در صف قرار دهید. وضعیت توصیف شده به صورت شماتیک در شکل 1 نشان داده شده است. 2.14.

مطابق با قانون مورفی (مطابق با چیزی شبیه به این است: "اگر اتفاق بدی رخ دهد، مطمئناً اتفاق خواهد افتاد")، وضعیت زیر ممکن است. روند آمقدار (7) متغیر را می خواند که درو آن را در یک متغیر محلی ذخیره می کند next_free_slot.پس از این، یک وقفه تایمر رخ می دهد و پردازنده به پردازش سوئیچ می کند که در.روند که در،به نوبه خود، مقدار متغیر را می خواند که درو آن را (دوباره 7) در متغیر محلی خود ذخیره می کند next_free_slot.در این لحظه، هر دو فرآیند معتقدند که بخش آزاد بعدی، قسمت هفتم است. روند که درنام فایل را در فهرست spooler ذخیره می کند و مقدار را جایگزین می کند که دردر 8 سپس به انجام وظایف غیر تایپ خود ادامه می دهد. در نهایت کنترل به فرآیند می رسد آ، و از همان جایی که رها کرده بود ادامه می دهد. به متغیر دسترسی پیدا می کند اسلات_بعدی_رایگان،مقدار آن را می خواند و نام فایل را در قسمت هفتم می نویسد (البته حذف نام فایل نوشته شده در آنجا توسط فرآیند که در).سپس مقدار را جایگزین می کند که درتوسط 8 (slot_free_next+1 = 8). ساختار دایرکتوری spooler دست نخورده است، بنابراین دیمون چاپ مشکوک به اشتباه نیست، اما فایل فرآیند که درچاپ نخواهد شد

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

مناطق بحرانی

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

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

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

1. غیرممکن است که یک فرآیند برای همیشه منتظر ورود به منطقه بحرانی باشد.

2. دو فرآیند نباید به طور همزمان در مناطق بحرانی باشند.

3. برنامه نباید در مورد سرعت یا تعداد پردازنده ها فرضیاتی داشته باشد.

4. فرآیندی که در خارج از منطقه بحرانی قرار دارد نمی تواند سایر فرآیندها را مسدود کند.

به صورت انتزاعی، رفتار فرآیند مورد نیاز در شکل 1 ارائه شده است. 2.15. فرآیند A در زمان وارد منطقه بحرانی می شود تی 1 . کمی بعد، در یک لحظه از زمان تی 2 , روند که درسعی می کند وارد منطقه بحرانی شود، اما شکست می خورد زیرا در حال حاضر یک فرآیند در منطقه بحرانی وجود دارد آ،و دو فرآیند نباید همزمان در مناطق بحرانی باشند. بنابراین روند که دربه طور موقت تا لحظه ای معلق است تی 3 زمانی که فرآیند آمنطقه بحرانی را ترک می کند. در یک لحظه از زمان تی 4 روند که درهمچنین از منطقه بحرانی خارج می شود و به حالت اولیه باز می گردیم، زمانی که هیچ فرآیندی در منطقه بحرانی وجود نداشت.

سمافورها

در سال 1965، E. W. Dijkstra استفاده از یک متغیر عدد صحیح را برای شمارش سیگنال های ماشه ذخیره شده برای استفاده در آینده پیشنهاد کرد. او نوع جدیدی از متغیرها را پیشنهاد کرد که به اصطلاح سمافورها, که مقدار آن می تواند صفر (در صورت عدم وجود سیگنال های فعال سازی ذخیره شده) یا تعدادی عدد مثبت مربوط به تعداد سیگنال های فعال سازی تاخیری باشد.

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

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

در نسخه اصلی Dijkstra به جای آن استفاده شد پایینو بالانامگذاری های P و V به ترتیب. ما در آینده از نام‌گذاری‌های اصلی استفاده نخواهیم کرد زیرا این نام‌گذاری‌ها برای کسانی که زبان دانمارکی را نمی‌دانند (و برای کسانی که این زبان را می‌دانند کمی می‌گویند) معنی ندارد. برای اولین بار نامگذاری پایینو بالادر الگول 68 ظاهر شد.

حل مشکل تولیدکننده و مصرف کننده با استفاده از سمافورها .

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

فهرست 2.4 مشکل تولید کننده و مصرف کننده با سمافورها

#تعریف N 100 /* تعداد بخش ها در بافر */

سمافور Typedef int; /* سمافورها نوع خاصی از متغیرهای عدد صحیح هستند */ semaphore mutex =1; /* کنترل دسترسی به منطقه بحرانی */

سمافور خالی = N ; /* تعداد بخش های بافر خالی /

سمافور پر است = در باره؛ /* تعداد قطعات بافر کامل */

تولید کننده خالی (باطل)

در حالی که (درست)

( /* TRUE - ثابت برابر با 1*/

Item = protiuce_item(); /* ایجاد داده برای بافر شدن */

پایین (&خالی)؛ /* کاهش شمارنده بخش های خالی بافر */

پایین (&mutex): /* ناحیه بحرانی را وارد کنید */

Insert_item(item); /* یک عنصر جدید را در بافر قرار دهید */

بالا (&mutex): /* خروج از منطقه بحرانی */

بالا (&full1); /* افزایش شمارنده قطعات بافر کامل */

مصرف کننده باطل (باطل)

( /* چرخه بی پایان */

پایین (&کامل)؛ /* تعداد قطعات بافر کامل را کاهش دهید */

پایین (&mutex); /* وارد منطقه بحرانی شوید */

آیتم = remove_item(); /* حذف عنصر از بافر */

بالا (&mutex); /* خروج از منطقه بحرانی */

بالا(&خالی): /* افزایش شمارنده بخش های خالی بافر */

Consume_item(item): /* پردازش عنصر */

راه حل ارائه شده از سه سمافور استفاده می کند: یکی برای شمارش بخش های بافر پر شده (پر شده)،دیگری برای شمارش بخش های خالی (خالی)و سومی برای جلوگیری از دسترسی همزمان تولید کننده و مصرف کننده به بافر طراحی شده است (mutex).ارزش متقابل پر شدهدر ابتدا برابر با صفر، شمارنده خالیبرابر با تعداد قطعات در بافر، a mutexمعادل 1 است. سمافورهایی که مقدار اولیه آنها برابر با 1 است که برای حذف همزمان دو فرآیند در منطقه بحرانی استفاده می شوند، نامیده می شوند. سمافورهای باینریدر صورتی که هر فرآیند عملیات را انجام دهد، طرد متقابل حاصل می شود پایینقبل از ورود به منطقه بحرانی وپس از خروج از آن

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

در مثال نشان داده شده در فهرست 2.4، سمافورها به دو روش مختلف مورد استفاده قرار گرفتند. این تفاوت به اندازه کافی قابل توجه است که ذکر ویژه را ایجاب می کند. سمافور mutexبرای پیاده سازی حذف متقابل، یعنی جلوگیری از دسترسی همزمان به بافر و متغیرهای مرتبط دو فرآیند استفاده می شود.

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

^ فرمول بندی مسئله:

مسئله آرایشگری که در حال خواب است، نمایش تمثیلی از زیرسیستم کنترل فرآیند است و توسط دایکسترا در سال 1968 فرموله شد. مسئله به صورت زیر فرموله شده است: آرایشگاه شامل یک اتاق انتظار O و اتاقی است که در آن یک صندلی آرایشگاه وجود دارد. Z. از طریق درهای D می توانید از اتاق O به اتاق Z و از اتاق Z به خیابان بروید. اگر آرایشگر وارد اتاق انتظار شود و کسی را آنجا پیدا نکند، به رختخواب می رود. اگر مشتری وارد آرایشگاه شود و آرایشگر را در خواب ببیند، او را بیدار می کند. تعداد صندلی های سالن انتظار محدود و برابر با N می باشد.

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

راه حل پیشنهاد می کند از سه سمافور استفاده کنید:

مشتریان،برای شمارش بازدیدکنندگان منتظر (مشتری که روی صندلی آرایشگر نشسته است شمارش نمی شود - او دیگر منتظر نیست).

آرایشگران،تعداد آرایشگران (0 یا 1) که بیکار ایستاده اند و منتظر مشتری هستند.

mutexبرای اجرای طرد متقابل

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

1. موضوع و هدف کار.

2. تکلیف آزمایشگاهی.

3. الگوریتم برنامه.

4. نتایج به دست آمده.

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

یک کار مهم و مکرر که حل آن نیاز به همگام سازی دارد، وظیفه "خوانندگان - نویسندگان" است. این کار دارای تغییرات زیادی است. می توان آن را به صورت زیر تعریف کرد. داده های مشترک بین تعدادی از فرآیندها وجود دارد. داده ها ممکن است در یک فایل در یک بلوک از حافظه اصلی یا حتی در رجیسترهای پردازنده قرار گیرند. چندین فرآیند وجود دارند که فقط این داده ها را می خوانند (Readers) و چندین فرآیند دیگر فقط داده ها را می نویسند (Writers). شرایط زیر باید رعایت شود: - هر تعداد خواننده می تواند همزمان فایل را بخواند - فقط یک Writer می تواند اطلاعات را در یک فایل بنویسد - وقتی یک Writer اطلاعات را در یک فایل می نویسد، هیچ Reader نمی تواند آن را بخواند. یک نمونه از استفاده کار با فهرست کتابخانه است. نمونه معمولی دیگر یک سیستم خودکار فروش بلیط است. فرآیندهای "خوانندگان" اطلاعات مرجعی را در مورد در دسترس بودن بلیط های رایگان برای یک پرواز خاص به ما ارائه می دهند. فرآیندهای "نویسندگان" زمانی از کنسول صندوقدار شروع می شود که وی بلیط خاصی را برای ما صادر می کند. تعداد زیادی "خوانندگان" و "نویسندگان" وجود دارد. معمول ترین حوزه استفاده از این کار در یک سیستم محاسباتی در ساخت سیستم های مدیریت فایل است. دو دسته از فرآیندها به برخی از منابع (منطقه حافظه، فایل ها) دسترسی دارند. "خواننده ها" فرآیندهایی هستند که می توانند اطلاعات را به صورت موازی از یک منطقه حافظه مشترک که یک منبع حیاتی است بخوانند. "نویسندگان" فرآیندهایی هستند که اطلاعات را در این ناحیه حافظه می نویسند، در حالی که یکدیگر و فرآیندهای "خواننده" را حذف می کنند. شرایط زیر گسترده است: 1. خواندن اولویت: اولویت در استفاده از منبع حیاتی فرآیند Readers تعیین می شود. این بدان معنی است که اگر حداقل یک Reader از یک منبع استفاده کند، آنگاه برای استفاده توسط همه Writers بسته شده و برای استفاده برای همه Readerها در دسترس است. هنگامی که درخواستی از یک Writer ظاهر می شود، لازم است دسترسی بیشتر به تمام آن فرآیندهای Reader که درخواست یک منبع حیاتی را پس از آن صادر می کنند مسدود کنید.

15 مشکل در مورد آرایشگر خواب. مشکل آرایشگر خواب. یک اقدام دیگر موقعیت مشکل ساز کلاسیک ارتباطات بین فرآیندی در یک آرایشگاه اتفاق می افتد. در آرایشگاه یک آرایشگر، صندلی او و nصندلی برای بازدیدکنندگان اگر افرادی حاضر به استفاده از خدمات او نباشند، آرایشگر روی صندلی خود می نشیند و می خوابد. اگر مشتری به آرایشگاه بیاید، باید آرایشگر را بیدار کند. اگر مشتری بیاید و ببیند آرایشگر مشغول است، یا روی صندلی می نشیند (اگر جا باشد) یا می رود (اگر جا نباشد). برنامه ریزی آرایشگر و بازدیدکنندگان به گونه ای ضروری است که از حالت رقابت جلوگیری شود. راه حل می تواند از سه سمافور استفاده کند: مشتریان، برای شمارش بازدیدکنندگان منتظر (مشتری که روی صندلی آرایشگر نشسته حساب نمی شود - او دیگر منتظر نیست). آرایشگران، تعداد آرایشگرها 0 یا 1 است)، بیکار در انتظار مشتری و mutexبرای اجرای طرد متقابل از متغیر نیز استفاده می شود در انتظار، برای شمارش بازدیدکنندگان منتظر طراحی شده است. این یک کپی از متغیر است مشتریان. وجود این متغیر در برنامه به این دلیل است که خواندن مقدار فعلی سمافور غیرممکن است. در این راه حل، بازدیدکننده ای که به آرایشگاه مراجعه می کند باید تعداد مشتریانی که در انتظار هستند را بشمارند. اگر تعداد بازدیدکنندگان کمتر از صندلی باشد، بازدیدکننده جدید می ماند و در غیر این صورت او را ترک می کند. صبح که آرایشگر سر کار می آید، عمل را انجام می دهد سلمانی، مسدود کردن روی سمافور مشتریان، از آنجایی که مقدار سمافور 0 است. سپس آرایشگر همانطور که در شکل نشان داده شده است به خواب می رود و تا رسیدن اولین مشتری می خوابد. با آمدن به آرایشگاه، بازدید کننده این روش را انجام می دهد مشتری، درخواست دسترسی به mutexبرای ورود به منطقه بحرانی اگر بازدیدکننده دیگری بعد از او ظاهر شود، تا زمانی که اولین بازدیدکننده دسترسی به آن را آزاد نکند، نمی تواند کاری انجام دهد mutex. سپس بازدیدکننده صندلی های رایگان را بررسی می کند، در صورت عدم موفقیت، دسترسی به آن را آزاد می کند mutexو برگ می کند. اگر صندلی رایگان وجود داشته باشد، بازدید کننده مقدار متغیر عدد صحیح را افزایش می دهد در انتظار. سپس این روش را انجام می دهد بالاروی سمافور مشتریان، در نتیجه جریان برادو بری فعال می شود. در این لحظه هم ویزیتور و هم آرایشگر فعال هستند. هنگامی که یک بازدیدکننده دسترسی به mutex، آرایشگر آن را می گیرد، کمی خانه داری می کند و شروع به کوتاه کردن موهای مشتری می کند. در پایان دوره هفتم، بازدیدکننده از رویه خارج شده و آرایشگاه را ترک می کند. برخلاف برنامه های قبلی، چرخه بازدید کننده وجود ندارد زیرا هر بازدیدکننده فقط یک بار موهای خود را کوتاه می کند. چرخه آرایشگر وجود دارد و آرایشگر برای یافتن بازدیدکننده بعدی تلاش می کند. اگر موفق شد موهای بازدید کننده بعدی را کوتاه می کند وگرنه آرایشگر خوابش می برد. شایان ذکر است که علیرغم عدم انتقال داده در مشکل خواننده-نویسنده و در مشکل آرایشگر خواب، هر دوی این مشکلات به مشکلات ارتباط بین فرآیندی مربوط می شوند، زیرا نیاز به همگام سازی چندین فرآیند دارند.

16 الگوریتم های برنامه ریزی فرآیند.

الگوریتم های برنامه ریزی فرآیند

برنامه ریزی فرآیند شامل حل وظایف زیر است:

1. تعیین لحظه زمانی برای تغییر فرآیند در حال انجام.

2. انتخاب یک فرآیند برای اجرا از یک صف فرآیندهای آماده.

3. تغییر زمینه فرآیندهای "قدیم" و "جدید".

FCFS- ساده ترین الگوریتم زمان بندی، الگوریتمی است که معمولا با علامت اختصاری FCFS بعد از حروف اول نام انگلیسی آن (first come, first serve) نشان داده می شود. بیایید تصور کنیم که فرآیندها در حالت آماده به صورت ردیفی هستند. هنگامی که یک فرآیند وارد حالت آماده می شود، آن، یا به طور دقیق تر، یک مرجع به PCB آن، در انتهای این صف قرار می گیرد. انتخاب یک فرآیند جدید برای اجرا از ابتدای صف انجام می شود و ارجاع به PCB آن از آنجا حذف می شود. صفی از این نوع در برنامه نویسی نام خاصی دارد - FIFO (اولین ورود، اولین خروج). این الگوریتم انتخاب فرآیند، زمان‌بندی غیر پیشگیرانه را انجام می‌دهد. مزیت الگوریتم FCFS سهولت اجرای آن است، اما در عین حال دارای معایب زیادی است. راند رابین (RR)اصلاح الگوریتم FCFS الگوریتمی به نام Round Robin (Round Robin نوعی چرخ فلک کودکان در ایالات متحده آمریکا است) یا به اختصار RR است. در اصل، این همان الگوریتم است که فقط در حالت زمان‌بندی پیشگیرانه اجرا می‌شود. می توانید کل مجموعه فرآیندهای آماده را که به صورت چرخه ای سازماندهی شده اند تصور کنید - فرآیندها روی چرخ فلک می نشینند. چرخ فلک طوری می چرخد ​​که هر فرآیند برای یک برش ثابت کوچک از زمان، معمولاً 10 تا 100 میلی ثانیه، نزدیک پردازنده باشد. در حالی که فرآیند نزدیک پردازنده است، پردازنده را در اختیار دارد و می تواند اجرا شود. این الگوریتم مانند الگوریتم قبلی با سازماندهی فرآیندهایی که در حالت آماده هستند در یک صف FIFO پیاده سازی می شود. زمان‌بند فرآیند را در ابتدای صف برای اجرای بعدی انتخاب می‌کند و یک تایمر تنظیم می‌کند تا پس از انقضای یک برش زمانی مشخص، وقفه ایجاد کند. هنگام انجام فرآیند دو گزینه وجود دارد. 1. زمان استفاده مداوم از پردازنده مورد نیاز فرآیند (باقیمانده انفجار CPU فعلی) کمتر یا برابر با مدت زمان برش است. سپس فرآیند به طور داوطلبانه پردازنده را قبل از انقضای زمان کوانتومی آزاد می کند، یک فرآیند جدید از ابتدای صف برای اجرا می رسد و تایمر شروع به شمارش مجدد کوانتوم می کند. 2. مدت زمان باقی مانده از فرآیند انفجار CPU فعلی بیشتر از برش زمانی است. سپس پس از انقضای این کوانتوم، فرآیند توسط یک تایمر قطع می شود و در انتهای صف فرآیندهای آماده اجرا قرار می گیرد و پردازنده در ابتدا برای استفاده توسط فرآیند تخصیص می یابد. عملکرد الگوریتم RR تا حد زیادی تحت تأثیر اندازه برش زمانی است. در مقادیر کوانتومی زمانی بسیار بزرگ، زمانی که هر فرآیند موفق می شود قبل از وقوع وقفه زمانی، انفجار CPU خود را کامل کند، الگوریتم RR به الگوریتم FCFS تبدیل می شود. در مقادیر بسیار کوچک، این توهم ایجاد می شود که هر یک از n فرآیند روی پردازنده مجازی خود با عملکرد ~1/n از عملکرد پردازنده واقعی (SJF) اجرا می شود. برنامه ریزی تضمینی هنگام در نظر گرفتن الگوریتم ها FCFSو R.R.ما دیدیم که ترتیب فرآیندها در صف فرآیندهای آماده اجرا برای آنها چقدر مهم است. اگر کارهای کوتاه نزدیکتر به ابتدای صف قرار گیرند، عملکرد کلی این الگوریتم ها به طور قابل توجهی افزایش می یابد. اگر زمان بعدی را می دانستیم CPU ترکیدبرای فرآیندهایی که در حالت آماده هستند، می‌توانند نه فرآیندی را در ابتدای صف، بلکه فرآیندی با حداقل مدت زمان را برای اجرا انتخاب کنند. CPU ترکید. اگر دو یا چند فرآیند از این قبیل وجود داشته باشد، برای انتخاب یکی از آنها می توانیم از قبلا شناخته شده استفاده کنیم الگوریتم FCFS. برش زمان در این مورد اعمال نمی شود. الگوریتم توصیف شده "اولین کار کوتاه" یا "اولین کار کوتاه" نامیده می شود. S.J.F.). الگوریتم برنامه ریزی کوتاه مدت SJFشاید مثل جابجایی، بنابراین غیر سرکوبگر. در SJF بدون جابجایی-برنامه ریزیپردازنده بدون توجه به رویدادهایی که در سیستم کامپیوتری رخ می دهد، برای تمام زمان مورد نیاز به فرآیند انتخاب شده ارائه می شود. در جابجایی SJF-برنامه ریزیظاهر فرآیندهای جدید در صف آماده برای اجرا (از بین آنهایی که تازه متولد شده یا مسدود شده اند) در حالی که فرآیند انتخاب شده در حال اجرا است در نظر گرفته می شود. برنامه ریزی تضمینی-وقتی N کاربر به صورت تعاملی در یک سیستم محاسباتی کار می کنند، می توان یک الگوریتم زمان بندی را اعمال کرد که تضمین می کند هر کاربر 1/N بخشی از زمان پردازشگر را در اختیار خود خواهد داشت. بیایید همه کاربران را از 1 تا N شماره گذاری کنیم. برای هر کاربر با شماره i، دو مقدار معرفی می کنیم: T i - مدت زمان حضور کاربر در سیستم یا به عبارت دیگر، مدت زمان جلسه ارتباط او با ماشین و τ i. - کل زمان پردازشگر که قبلاً به تمام فرآیندهای او در طول جلسه اختصاص داده شده است. عادلانه است که کاربر زمان پردازشگر T i/N را دریافت کند. اگر τ i<>T i /N سپس سیستم به وضوح از شماره کاربر i حمایت می کند. بیایید مقدار ضریب انصاف τ i N/T i را برای فرآیندهای هر کاربر محاسبه کنیم و برش دفعه بعدی را با کمترین مقدار این نسبت به فرآیند آماده ارائه کنیم. الگوریتم پیشنهادی، الگوریتم زمانبندی تضمینی نامیده می شود. از معایب این الگوریتم می توان به عدم توانایی در پیش بینی رفتار کاربر اشاره کرد. اگر کاربر برای چند ساعت برای صرف ناهار و خواب بدون وقفه در جلسه کاری خود بیرون برود، پس از بازگشت فرآیندهای او مقدار زیادی از زمان CPU را دریافت خواهد کرد.

برنامه ریزی اولویت دار الگوریتم های SJFو برنامه ریزی تضمینیموارد خاص را نشان می دهد برنامه ریزی اولویت دار. در برنامه ریزی اولویت داربه هر فرآیند یک مقدار عددی خاص اختصاص داده شده است - یک اولویت، که بر اساس آن یک پردازنده به آن اختصاص داده می شود. فرآیندها با همان اولویت هایبه ترتیب برنامه ریزی شده اند FCFS. برای الگوریتم SJFهمینطور اولویت استمدت زمان بعدی را تخمین بزنید CPU ترکید. هر چه مقدار این تخمین کمتر باشد، بالاتر است یک اولویتفرآیندی دارد. برای الگوریتم برنامه ریزی اولویت تضمین شدهبه عنوان ضریب عدالت محاسبه شده عمل می کند. هرچه کوچکتر باشد، فرآیند بیشتر است یک اولویت. الگوریتم های تعیین تکلیف اولویت هایفرآیندها می توانند هم بر پارامترهای داخلی مرتبط با آنچه در داخل سیستم محاسباتی اتفاق می افتد و هم به پارامترهای خارجی در رابطه با آن تکیه کنند. پارامترهای داخلی شامل ویژگی‌های کمی و کیفی مختلف فرآیند است، مانند: محدودیت‌های زمانی برای استفاده از پردازنده، اندازه حافظه مورد نیاز، تعداد فایل‌های باز و دستگاه‌های ورودی/خروجی استفاده‌شده، نسبت مدت زمان متوسط. I/O منفجر شدبه CPU ترکیدو غیره SJF و الگوریتم های زمان بندی تضمینی از پارامترهای داخلی استفاده می کنند. پارامترهای خارجی ممکن است شامل اهمیت فرآیند برای دستیابی به اهداف معین، هزینه زمان پرداختی پردازنده و سایر عوامل سیاسی باشد. خارجی بالا یک اولویتممکن است توسط یک سخنران یا شخصی که 100 دلار برای یک ساعت کار پرداخت کرده است به یک وظیفه اختصاص داده شود. برنامه ریزیاستفاده كردن اولویت هایشاید مثل جابجایی، بنابراین غیر سرکوبگر. در برنامه ریزی پیشگیرانهپردازش با بالاتر اولویت، که در صف فرآیندهای آماده ظاهر می شود، فرآیند اجرا را با یک پایین تر جابجا می کند اولویت. چه زمانی برنامه ریزی غیر پیشگیرانهبه سادگی به ابتدای صف فرآیندهای آماده می رود. بیایید نمونه هایی از استفاده از حالت های مختلف را بررسی کنیم برنامه ریزی اولویت دار. مشکل اصلی برنامه ریزی اولویت داراین است که اگر مکانیسم تخصیص و تغییر در اولویت هایفرآیندهای با اولویت پایین ممکن است به طور نامحدود اجرا نشوند. معمولا یکی از این دو اتفاق می افتد. یا هنوز منتظرند تا نوبت اجرا شود. یا سیستم کامپیوتری باید خاموش شود و آنها گم می شوند. راه حل این مشکل را می توان با افزایش ارزش در طول زمان به دست آورد اولویت فرآیند، در حالت آماده باش.