خلاصه فصل 7 سیستم عامل: هماهنگی فرآیندها

صفحه 1:


صفحه 2:


صفحه 3:
در فصل 4 مدلی از سیستم را اجرا کردیم که شامل تعدادی از فرآیندهای ترتیبی همکار بوده است که همگی به طور ناهماهنگ اجرا می شدند و احتمالا داده های مشترکی داشتند. این مدل را با استفاده از الگوی میانگیر (بافر) محدود , به عنوان نمایشی از سیستم های عامل » توضیح داریم. ‎Joely‏ حاقظه مفترکپراق مسئله: باقن محدود در انظیر مین گیریم : گفتیم که حداکثر یک سه ۵۵ قلم داده می تواند به طور همزمان در بافر وجود داشته باشد . برای برطرف گردن: این ‎at‏ از نک ‎xe orld sil al ye oni sled‏ اكنيم که دارای مقدار است با ورود هر قلم شمارنده اضافه و با 

صفحه 4:


صفحه 5:
این دو روال به طور جداگانه درست عمل می کنند اما به طور همزمان ممکن است به درستی عمل نکنند مثلا اگر ده و فرآیندهای تولیدکننده و مصرف کننده دستورات "سیون++۲ و *ییون--" را همزمان اجرا کنند مقدار جوم ممکن است 4 5 6 باشد ولی مقدار درست 5 و وقتی تولید می شود که هر کدام به طور جداگانه عمل کنند. #*علت رسیدن به حالت نادرست دسترسی همزمان فرآیندها به داده ی مشترک یوم است. 

صفحه 6:
چنین وضعیتی که چندین فرآیند به طور همزمان به داده ای دسترسی دارند و نتیجه اجرا به ترتیب دستیابی فرآیندها بستگی دارد » 029 ۲) می گوییم. Rue ‏حل مقابله با لین‎ ol, ‎sl,‏ مقابله با حالت مسابقه باید تضمین شود که در هر زمان تنها یک فرآیند به متغیر جح دسترسی داشته باشد که برای چنین کاری نیاز به هماهنگی فرآیندهاست. 

صفحه 7:
2-7 مسئله ناحیه بحرانی سیستمی با » فرآیند [ 4 , ... , 06 , ۵ ) را در نظر بگیرید. هر فرآیند بخشی کد به نام ناحیه بحرانی (-۵ ‎)0۳٩‏ دارد که فرآیند ممکن است در آن متغیرهای مشترک را تغییر دهد , جدولی را بروز کند , فایلی را بنویسد , و ... ۷ ویژگی مهم این است هنگامیکه یک فرآیند در حال اجرای ناحیه ی بحرانی خودش است , هیچ فرآیند دیگری نباید اجازه داشته باشد ناحیه بحرانی خودش را اجرا کند. بنابراین اجرای ناحیه ی بحرانی توسط فرآیندها , از نظر زمانی انحصار متقابل (بلسیه حصامج) است. 

صفحه 8:
مسئله ناحیه بحرانی طراحی پروتکلی است که فرآیندها می توانند به صورت همکار عمل کنند , هر فرآیند برای ورود به ناحیه ی بحرانی خودش + باید اجازه بگیرد. بخشی از ‎aS‏ که درخواست اجازه صادر می کند , ناحیه ی ورودی (بسح) نام دارد و بقیه کد را ناحیه باقیمانده می نامند. 

صفحه 9:
‎Jo ol,‏ مسئله ناحیه ی بحرانی باید 3 نیازمندی را برآورده کند : ‏عصاهه یه : لگر فرلیند 0© در حا لتاجرلى ناحيد ى بحرانی‌اش‌باشد , هیچ فرآیند دیگرین باید اجازم ی اجرای تاحیه ب حرلنیاش‌را داشته باشد. ‎so nin oll‏ : اگر هیچ فرآیندی در ناحیه ی بحرانی اش نباشد ولی فرآیندهایی باشند که بخواهند وارد ناحیه ی بحرانی خودشان شوند , آنگاه فقط فرآیندهایی که در حال اجرای ‎acl‏ ی باقیمانده خودشان نیستند می توانند برای ورود به ناحیه ی بحرانی خودشان انتخاب شوند و این اتفاق نمی ‏تواند بطور نامحدود به تعویق بیفتد. 

صفحه 10:
1-2-7 راه حل هاى دو فرآیندی در اين قسمت به الكوريتم هايى مى بردازيم كه در هر زمان فقط بروى دو فرآيند عمل مى كنند. فرآيندها با 0© و ‎٩۳‏ ‏ناحيه مشخص مى شوند براى سهولت وقتى از برای نشان دادن فرآیند بعدی از 6۱ است ‎ps)‏ whee ack ‏دادح‎ ساختار كلى فرآيند نمونه :03 ليا 

صفحه 11:
1-1-2-7 الگوریتم 1 اولین راه حل این است که از فتغیر هشترگی ‎wea pli as‏ استفاده فرآکنیمکه|مقدلر الیو آبار9 افتبه ی بحرانی خود شود مه ۷" این راه حل تضمین می کند که در هر زمان فقط یک فرآیند وارد ‎s acl‏ بحرانی اش شود اما نیازمندی پیشروی را برآورده نمی کند زیرا دقیقا مشخص می کند که چه فرآیندی باید وارد ‎acl‏ ی بحرانی خودش شود. 

صفحه 12:
2-1-2-7 الگوریثم 2 مشکل الگوریتم 1 این است که اطلاعات کافی در مورد حالت هر فرآیند نگهداری نمی کند بلکه فقط مشخص می کند کدام فرآیند اجازه ی ورود به ناحیه ی ورود ‎asl a:‏ ی بحرانی خودش را دارد که برای حل ایو سنکلبه جای متغیر مب از آرایه زیر استفاده می شود : مقدار اولیه عناصر آرایه طخ است [6] موس اگر صبد [۲۷ باشد نشان می دهد که ۵۱ آماده ورود به ناحیه فك معواتس. افق صل 

صفحه 13:
#*هر فرآیند برای ورود به ناحیه ی بحرانی منتظر می ماند تا ۲۱ مربوط به فرآیند ناحیه ی بحرانی ۳ شود و هر فرآیند هنگام خروج از ناحیه ی بحرانی پ۲۳ مربوط به خود را < می کند 

صفحه 14:
در اين روش: |« شرط انحصار متقابل برقرار است اا.ءشرط پیشروی برقرار نیست مثال: برای تشریج مسئله فوق اين دنباله را در نظر می گیریم : < [9 ]مط د 6۵ : 20 کنون ‎PO‏ و 4 در حلقه ‎Got Peed] = Tre eS cre oS hte‏ ¢@ :10 ** این الگوریتم به زمانبندی دقیق دو فرآیند بستگی دارد. اين دنباله می تواند در محیطی باشد که چندین فرآیند به طور همزمان در حال اجرا هستند و یا بلافاصله بعد از ۲۵ وقفه رخ دهد و 00 از یک فرآیند به فرآیند دیگر برود. 

صفحه 15:
3-1-2-7 الگوریتم 3 در اين روش فرآیندها دارای دو متغیر تعمد 44 

صفحه 16:
# فرآیند 6۷ براى ورود به ناحيه ى بحرانى ابتدا [8]0 را ص1 مى ‎iS‏ اكر هر دو فرآيند سعى كنند همزمان وارد ناحيه ى بحرانى شوند . دى؛ در آن واحد مى خواهد ؛ و شود. اما فقط یک دستور انتساب بعدى انجام مى شود و مقدار قبلى از بين مى رود. مقدار نهايى دى؛ مشخص مى كند كداميك از دو فرايند » زودتر اجازه ورود به ناحيه ى بحرانى را ييدا مى كنند. 

صفحه 17:
"اين روش ویژگی های زیر را دارا می باشد : حصاهه رلعی0: هر فرآیند 0 وقتی‌میتولند وارد ناحیه ی بحرانی‌اش‌شود که یا -ط ۳‏ [۲۳ با !مه . لگر دو فرآیند بخواهند همزمان‌وارد ناحیه ی بحرانی‌شوند آنگاه ع۲ > [۲]6 < [۱۳0 کم بدین‌ترتیب0؟ و 64 نمیتولنند همزمان‌حلقه طاب خود را اجرا کنند چرا کم مقدار موه میتولند در یک‌زمان0 یا 1 باشد. ‎all‏ شرط پیشروی ‏ااا.ءشرط انتظار محدود 

صفحه 18:
v برای اثبات ویژگی 2 و 3 در صورتی می توان مانع از 2939 فرآیند ۱ به ناحیه ی بحرانی اش شد که يا ۲7۷ 2 [۲۳ و سد ص18 - در حلقه عاب كير كند. 4. اكر :© آماده ورود به ناحيه ى بحرانى نباشد آنكاه - [إدع ‎ro Pig Pobre‏ تواند وارد ناحيه ى بحرانى مى شود. 8 اگر :موه باشد و 6 وارد ناحیه بحرانی می گردد. وقتی 6۱ وارد ناحیه بحرانی طخ 2 ‎Profi]‏ می گردد و ۲ اجازه ‎use Lay‏ کند تا وارد ناحیه ی بحرانی خود شود. 6 اگر ۵۱ مقدار [ب! را برابر صب قرار دهد باید 2۱ مه نیز باشد اما جون ,© در حين اجراى دستور طلب » مقدار مسب را تغییر نمی دهد , 6 حداکثر پس از یک بار ورود ‏ در ناحیه ی 

صفحه 19:
‎ol, 2-2-7‏ حل های چند فرآیندی الكوريتم نانوايى (موكللاجيك بوله) برای حل ناحیه ی بحرانی به اندازه ی » فرایند است که این الگوریتم را برای محیط توزیعی طراحی ‏این الگوریتم به هر مشتری هنگام ورود شماره ای می دهد و مشتری بعدی که باید خدمات بگیرد مشتری است که شماره ی کوچگعزیدارد در ضمن آلگوریتم بصمیننمی کید که سمارهی مشتریان یکسان نباشد اگر شماره ی مشتریان یکسان بود | مشتربى كه نإ كوجكهرة کاره زودتر دما می كيت ‎oh‏ ‏1 ‏شود 6 يكسان اكد 

صفحه 20:
ساختمان داده های مشترک عبارتند از : ۷مقدار اولیه ی این ساختمان داده ها به هه مس ترتیب ۳ و 0 است. [] اسب داز این الگوریتم شرط های سه گانه را داراست. ساختار فرآیند ۱ بر الگوریتم وله در شکل زیر نشان داده شده / Obovern( =r; ‏]ساديم ,... ,[ سه ,[© مسجت [] سس‎ 0[+0(: 

صفحه 21:
3-7 ویژگی های سخت افزاری برای هماهنگی فرآیند برای مسئله ی ناحیه بحرانی در محیط تک پردازنده ای کافی است اجازه ندهیم در حین تغییر متغییرهای عمومی ؛ وقفه ای رخ دهد. اولین روش در محیط چند پردازنده ای امکان پذیر نیست چرا که غیر فعال کردن وقفه ها در یک محیط چند پردازنده ای می تواند موجب اتلاف وقت شود زیرا پیام به ‎elas‏ پردازنده ها ارسال می شود ۷ بنابر این اغلب ماشین ها دستورات سخت افزاری خاصی را ‎coe a8 allen gue Sled‏ نوان كلمه: اى برا تست گنه یا محتویاتش را تغییر دهد يا اتمی محتویات دو کلمه را عوض کند. 

صفحه 22:
دستور 6 ۵ بو به طور اتمیک اجرا می شود یعنی به عنوان یک واحد بدون وقفه اجرا می شود بنابراین اگر دو دستور ۰۱6 2 همزمان , هر كدام در يى 00600 اجرا شوند , , ته ترتيبى اجرًا ضى يد 

صفحه 23:
0 اگر ماشین از دستور 720۱6 پشتیبانی کند برای پیاده سازی انحصاری یک متغیر بولین به نام ۲ تعریف می کنیم و مقدار اولیه آنرا عط۳ در نظر می گیریم. ساخت فرآیند 0۱ در اینجا آمده است. ط( ((سا)۲2)<:۵) دننز ناحیه ی بحرانی jlock = Pube ناحيه ى بآقيمانده 

صفحه 24:
دستور ‎Gun‏ ‏تور کین وی مجبونات دو كلمة کار می > کندا که ان دستور نیز مانند 0۰46 به د ۲ )4 & ان 6 تیلم ‎A‏ ن | ين الكوريتم ها 0 = ‎ioe twp‏ نيازمندى انتظار محدود را ‎web 8‏ براورده مى كنند. ‎ib = ewp { ‎ 

صفحه 25:
7 5 ce 15 الگوریتمی که در زیر آمده از دستور ۲226 استفاده می کند و تمام نیازمندیهای سه گانه ناحیه ی بحرانی را برآورده می کند. ساختمانر البلمبهای مظترک ربا لتیدمازنیج ست. [ از برای اثبات اینکه الگوریتم عمصاهمه بلعیی را رعایت ‎joke Oe‏ می دانیم که فرآیند ) وقتی می تواند وارد ناحیه ی بحرانی شود که ۳ < پجهن يا ۳1 < نوا باشد و بها وقتى مى تواند عط۳ باشد که دستور 26" اجرا شده باشد. اولین فرآیندی که دستور ‎ino US ino Io |, Test Oud Get‏ فهمد که ‎g hey = Pube‏ بقیه فرآیندها باید منتظر بمانند. متغیر [بهسب در صورتی عط۳ می شود که فرآیند دیگری از ناحیه ی ‎Cc Lee Illa. It.‏ 

صفحه 26:
4-7 سمافورها سمافور يك متغير صحيح است كه صرف نظر از مقداردهى اولیه , فقط از طریق دو عمل استاندارد اتمیک به نام های 

صفحه 27:
هنگامیکه یک فرآیند در حال تغییر مقدار سمافور است هیچ فرآیند دیگری نمی تواند مقدار همان سمافور را در همان زمان تغییر دهد. در حالت (ح)همب » تست مقدار سمافور ‎SO)‏ 0-7 )کر برون وقنمافل‌رنها. مسئله ی ناحیه ی بحرانی » فرآیند را می توانیم با استفاده از سمافورها حل کنیم» فرآیند دارای سمافور مشترکی به تام هی هستند که مقادیر اولیه آن 1 اس ه هر فر آنتد 

صفحه 28:
7 ee Oe 2-4-7 پیاده سازی سمافور ‎wus‏ عمده ی راه حل های انحصار متقابل و تعریف سمافوری که ارائه شد این است همه ی آن ها نیازمند انتظار مشغول هستند (بچهمب بصطا). انتظار مشغول در سیستم های چند برنامه ای با ‎OPO Ss‏ 1 زمان 060 را هدر می دهد اما اين روش در سیستم های چند پردازنده ای مفید است چرا که دیگر نیاز به صرف زمان زیادی برای تعویض بستر نیست و فرآیند تنها می بایست در مدت زمان قفل منتظر بماند. ‏۷ برای رفع مشکل پهست بط تعریف عملیات هب و ‎Loker‏ تغيير می دهیم. وقتی فرایندی عب را اجرا می کند , در صورتیکه مقدار سمافور مثبت نباشد , باید منتظر بماند و به جای ‎buoy‏ 

صفحه 29:
** عمليات انسداد , فرآیندی را در صف انتظار وابسته به آن سمافور قرار می دهد و حالت فرآیند به حالت انتظار تبدیل می شود. سپس کنترل به زمانبند 0060 می رود تا فرآیند دیگری را برای اجرا انتخاب کند. # فرآیندی که در انتظار سمافور 6 مسدود است ؛ در اثر عملیات اجه , توسط فرآیند دیگر , باید دوباره شروع ‎as‏ اجرا نماید که شروع دوباره ی فرآیند با عملیات جصلس انجام می شود که فرآیند را از حالت انتظار به حالت آمادگی می برد. سپس این فرآیند در صف آمادگی قرار می گیرد. هر سمافور دارای یک مقدار صحیح و لیستی از فرآیندهاست. وقتی فرآیندی باید منتظر سمافور بماند » به لیستی از فرآیندها ey 

صفحه 30:
عملیات سب سمافور مى تواند به صورت زیر پیاده سازی شود: (۵ سجن لاس( jouer }Oarke<0) ‎io OL‏ دصح هذا لوز عاعطط() ز ‎{ ‏ا 0 ‏فرخوانی کرده به تعویق می اندازد ‎ 

صفحه 31:
(۵ ساوسو لس( صلس 6+ + ز (ععسس. 8)م( irewove u process P Prow OL ‏(ماصحطسز‎ { نکته : عملیات سا و جحجلس به صورت فرخوان های سیستم در سیستم عامل پیاده سازی شده اند 

صفحه 32:
3-4-7 بن بست ها و حالت گرسنگی پیاده سازی سمافور با صف انتظار , ممکن است منجر به این شود که دو يا چند سمافور دائما منتظر رویدادی باشند که توسط یکی از فرآیندهای منتظر ناشی شود. رویداد مورد انتظار , اجرای عملیات است ( به این حالت بن بست مى كوييم ) قواسجکنت بو ‎Hidde‏ (0)وفرآرلدا 98 06 وجود داپیهی؟ دراک : jwea(Q); wat) ‏سیم(فون حقذللیک هستند.‎ : : ‏همینت رتیبوقتی0‎ a ules Ll 1 wa(Q) iGrqri(S); ‏(ه)سمت‎ تن | را اجرا من کند باید متتظر بماند نا ۵ عملیات اتويت | 

صفحه 33:
#امسعلة دیگر در نورد بن نست استداه با فرستنگی است: در این وضعیت , فرآیندها در داخل سمافور به طور نامحدود منتظر می ماند. انسداد نامحدود در صورتی اتفاق می افتد که فرآیندهایی را از صف مربوط به سمافور حذف یا اضافه کنیم که به ترتیب ۷۵ ws? siege ley Asp” سمافورهای دودویی بر خلاف سمافورهای شمارشی که در بخش قبل ‎od‏ شند: من جوانند ‎‘Leas‏ مغادیز 8 با 1 را ديرد (سمافورهای شمارشی می توانند هر مقدار صحیحی را بپذیرند) ‎sjlw ol,‏ سمافورهای شمارشی با استفاده از سمافور دودویی: 

صفحه 34:
عملیات ‎ore‏ در ۵ 

صفحه 35:
5-7 مسائل کلاسیک هماهنگی فرآیندها 1-5-7 مسئله بافر محدود ساختار کلی الگوی بافر محدود بدین صورت است که فرض می کنیم انبار بافرها حاوی ه بافر است و هر بافر می تواند یک قلم داده را ذخیره کند. © سمافور جضی انحصار متقابل را برای دستیابی به انبار بافر فراهم می کند و مقدار اولیه آن یک است. *** سمافورهاى بوجت و لذ به ترتيب تعداد بافرهاى خالى و پر را شمارش مى كنند. 

صفحه 36:
ساختار فرآیند تولید کننده : > > مقدار اولیه ۳۳ 0 < مقدار اولیه اد 

صفحه 37:


صفحه 38:
2-5-7 مسئله خوانندگان و نویسندگان ۷یک شی داده مثل فایل را رکورد : بین فرآیندهای همزمان به اشتراک گذاشته می شود که بعضی از فرآیند ها ممکن است نخواهند محتویات شی را بخوانند ولی بعضی دیگر است بخواهند شی داده را تغییر دهند. فرآیندهایی که فقط عمل خواندن را انجام می دهند را خوانندگان و بقیه نویسندگان می نامیم. ۷ گر دو خواننده همزمان به شی داده مشترک دستیابی داشته ببياشنن مشكلي ابجان نهى شود اما أكرئويسنده و فرآيند ‎of‏ بويسيدم يا حوانيدما ‎ae‏ ۳ قه باشند , مشكل ايجاد مى شود 

صفحه 39:
مسئله خوانندگان و نویسندگان شکل های گوناگونی دارد و شامل اولویت های نیز هستند. 1 اولین مسئله ی خوانندگان و نویسندگان , هیچ فرآیندی منتظر نماند مگر اينکه خواننده ای قبلا اجازه دستیابی به شی مشترک را کسب کرده باشد( منجر به گرسنگی نویسندگان می شود) 2 دومین مسئله خوانندگان - نویسندگان : وفتی نویسنده ای آماده ی نوشتن شد ء عمل نوشتن را هر چه زودتر انجام می دهد ( یعنی اگر نویسنده ای منتظر دستیابی به شی باشد , هیچ خواننده ای شروع به خواندن نمی کند) (منجر به گرستگی خواننده می شود) به همین دلیل شکل های دیگری از مسئله طراحی شد. 

صفحه 40:
: ‏حل برای اولین مسئله خوانندگان - نویسندگان‎ ol, ‏سمافور 0 2 بط ,سب‎ readout =O - : ‏ساختار فرایند نویسنده‎ : مشخص‌می‌ک ند چند فرآیند در حال‌خواندن شی 2300 ‎Durex‏ : تضمین‌می‌کند وقتی ‎ ‏کند انحصار متقابل‌برقرار 

صفحه 41:


صفحه 42:
3-5-7 مسئله غذا خوردن فیلسوفان % پنج فیلسوف را در نظر بگیرید که ‎b‏ © زندگی خود را صرف فکر 0 کردن و غذا خوردن می کنند. .سح ‎a)‏ ۳ فیلسوفان دارای یک میز دایره ای هستند که پنج صندلی دارد 76 و هرکدام متعلق به یک ور ۹ ۹ فيلسوف است . در مرکز یک 6 02 ‎١.‏ ديس از برنج قرار دارد و ينج ‎[١‏ 1 قاشق نيز بروى ميز واقع 

صفحه 43:
وقتی فیلسوفی در حال فکر کردن است , تعاملی با همکارانش ندارد. گاهی یک فیلسوف گرسنه ‎ro‏ شود و سعی می کند قاشق نزدیک خود (قاشق بین او و همکاران چپ و زاستا را بردارد.. فیلینتوف: در هر زمان فقط یک قاشق می تواند بردارد. بدیهی است که فیلسوف نمی تواند قاشقی که دست همکازانش است زا بردارد: اگر فیلسوف گرسنه , هر دو قاشق را در آن واحد در اختیار داشته باشد , بدون وقفه می تواند به خوردن ادامه دهد. هنگامیکه کار خوردن تمام شد هر دو قاشق را به روی میز مى گذارد و دوباره شروع به فکر كردن مى كند. 

صفحه 44:
ee #*تذکر : مسئله غذا خوردن فیلسوفان نمایش ساده ای از نیاز به تخصيص چندین منبع بین فرآیندهای مختلف است که بدون بست و گرسنگی انجام می شود. * یک راه حل سادهبرای مسئله غذا خوردن فیلسوفان اين است که هر قاشق با یک سمافور نمایش داده شود. هر فیلسوف برای بدست آوردن یک قاشق , عملیات سب را بروی آن سمافور اجرا می کند و با اجرای عملیات له بروی سمافور متاسب , قاشق را آزاد می کند لذا داده مشترک به میورب ربیاسب که مقداز اذلنه ی اعتامن اقب براي ركه است. iGewophore chopstch[S] 

صفحه 45:
ساختار فیلسوف : ura chopetch{i)); xt (chopatch| (#0) %S]; oot ([] اصس ديد ‎chopotch{(+0)%S]);‏ سیب تسا ())طاس( 

صفحه 46:
۷ اگرچه اين راه حل تضمین می کند که هیچ دو همسایه ای به طور همزمان نمی خورند اما منجر به بن بست می گردد. تشریح بن بست در ‎oly‏ حل فوق : اگر هر پنج فیلسوف همزمان گرسنه شوند و هر کدام قاشق سمت چپ خود را تصاحب کنند اکنون تمام عناصر 6د هبرابر با صفر خواهند بود. وقتى هر فيلسوفى سعى مى كند قاشق سمت راست خودش را بكيرد , به تعويق مى افتد. 

صفحه 47:
7 مناطق بحرانی استفاده نادرست از سمافورها ممکن است منجر به خطاهای تنظیم وقت شود که کشف آن ها مشکل | منال : اگر ترتیب اجرای عملیات عب ‎fF sted g‏ *** ممكن است چندین فرآیند به طور همز. ناحیه ی بحرانی باشد. 

صفحه 48:
* فرض کنید به جای (ضصضح)صيد از (صمامس. استفاده می کند که در این حالت بن بست اتفاق می افتد. * همچنین اگر (صمس يا (صملسبه يا هر دو را حذف کنیم , يا انحصار متقابل از بين مى رود يا بن بست رخ مى دهد. ساختار منطقه بحرانی يا ناحیه ی مشروط ‎Cniicd)‏ ‏2۳؟)) : یک ساختار هماهنگی سطح بالا می باشد که جهت جل .مشکلات مفرح شده:در بالاً ازائهاخی گزدید: در ساختار منطقه ی بحرانی و ساختار ناظر که در جلوتر بیان می شود. فرض بر این است که یک فرآیند حاوی داده ی محلی ؛ و یک برنامه ترتیبی است که می تواند بروی آن داده 

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

صفحه 50:


صفحه 51:
دستيابي انحصار متقابل ‎dy‏ ناحیه بحراني توسط بریی() فراهم مي‌شود. #اگر فرآيندي نتواند به دلیل نادارست بودن شرط منطقي 9) وارد ناحیه بحراني شود در سمافور ‎lays Proto‏ #فرآيندي كه در سمافور بوط بجو منتظر است. قبل از اجازمي ارزتيابي مجدد شرط منطقي 9 (عبارت 09» يك عبارت منطقي است كه دستيابي به ناحيدي بحراني را مشروط مي‌سازد وقتي فرآيندي سعي ميكند وارد ناحيه بحراني شود عبارت منطقي © را ارزيابي ميكند)؛ به سمافور مسج رواط منتقل ميكردد. 6 تعداد فرآيندهاي منتظر در سمافورهاي رواط لمح روط بد به ترتيب توسط رواط به و بواط ديد مشخص ميشوند. 

صفحه 52:
#وقتي فرآيندي از ناحیه بحراني خارج مي‌شود» ممکن است شرط صنعتي 9) را تغییر دهد که منجر به جلوگيري از ورود فرآیند دیگر به ناحیه بحرلني‌اش گردد. #فرآیند قبل از ورود به ناحیه بحراني عبارت منطقي 0 را تست مي‌کند که در صورت ارزش درستي وارد ناحیسه بحرانسي مي‌شود و در غیر اینصورت باید در سمافورهاي رواط- و۲ و رجاط یی منتظر بماند. 

صفحه 53:
جح ناظرها (0) ساختار سطح بالاي دیگر ناظر است که براي حل مسائل وایجاد دو به دو ناسازگاري پیشنهاد مي‌شود مونیتورمجموعه‌اي از زیربرنامه‌هاء متغيرها و ساختمان داده‌اي است که همگي در يك ماژول خاص بسته‌بندي شده‌اند. ۷ماجول مربوط به مونیتور» بين جندين فرآيند به اشترلك گذاشته مي‌شود. ساختار مویتور ی ناظر تضمین مي‌کند که در هر زمان فقط یه فرآیند در داخل ناظر فعال باشد. 

صفحه 54:
علاوه بر محتوياتي که در بالا براي مونيتور ذكر شدء مانيتور مي‌تواند حاوي متفيرهايي از نوع‌هاي مستفبی0 باشد که مي‌تران عمل لمیر و امد را بروي آن تعریف کرد. ‎gat AY”‏ که عمل ارس را بر ‎poet tle go‏ صدا زند بلوکه مي‌شود. ‏۷ گر فرآیند ديگري به این علت که فرآیند اول در داخل مونیتور قرار داشت متوقف شده بوده پس از رخداد بالاء مي‌تواند به اجراي خود ادامه داده و وارد مونیتور شود. ‏عمل اسسپ:0 دیق يك فرآيند به تعويق افتاده را از سركيري ميكند. اكر هيج فرآيندي به تعويق نيفتاده باشدء عمليات إدمب:98) تأثيري نخواهد داشت. 

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

صفحه 56:
شکل زیر مونیتور با متغيرهاي (ب) لبون را نشان مي‌دهد, 

صفحه 57:
AP word = ۵ ‏ما‎ wet (ew); Rewor — ew; ;0 - سوه > موه AP covet < 0 - 0 ۲! ‏مه‎ (Pd); /مقداردهی‌اولیه :0 < سوه دمب لعج 

صفحه 58:
ج-0 هماهنگي در سيستم‌هاي عامل 0۵-7 هماهنگي در سولارین 6 0سیستم عامل سولاریس 0 طراحي شد تا محاسبات بي‌درنگ را انجام دهد» چند بندي باشد و لز جند بردازندماي يشتيباني كند. ()براي کنترل دستيابي بسه نواحسي بحرانسي» سولاریس 6 انحصارهاي تطسبيقي ‎(ack pave wetex)‏ متغيرهاي شرطيء سمافورهاء قل‌هاي خواننده - نویسنده وصف ويه ‎(Turs vile)‏ را تدارك مي‌بیند. 0سولاریس ۰0 سمافورها و متغيرهاي شرطي را به روش يكساني پياد‌سازي مي‌کند. 

صفحه 59:
هه همگامي در ویندرز 6000 ویندوز 060000 يك هسته چندبندي است که از كاربردهاي بي‌درنگ و چندپردازنده نیز پشتيباني مي‌کند. وقتي هسته ویندوز 0000000 در يك سیستم تك پردازنده‌اي به يك منبع عمومي دستيابي دارد» موقتاً وقفه‌هايي را براي انجام اداره کنندگان وقفه‌اي مي‌فرستد که ممکن است به آن منبع عمومي دستيابي داشته باشند. #در سیستم چند پردازنده‌اي؛ ویندوز 000000 با استفاده از قفل‌هاي چرخشي منابع عمومي را محافظت مي‌کند. همانند سولاریس ‎<Q‏ هسته از قفل‌هاي چرخشي براي سگمنت‌هاي کد کوتاه استفاده مي‌کند. #علاوه بر اين» به دلایل كارآيي» هسته تضمین مي‌کند که تا زماني که بندي قفل چرخشي را در اختیار دارد» قبضه نخولهد شد. #براي همگامسي بنده در خارج از هسسته؛ ویندوز 0000000 از اشياي توزیع کننده ‎aS, 4 clita! (Dispatcher Obiert)‏ 

صفحه 60:
»9 تراکنش‌هاي اتمي انحصار متقایل ناحیه بحراني تضمین مي‌کند که ناحيه‌هاي بحراني به طور اتميك اجرا شوند يعني اگر دو ناحیه بحراني به طور همزمان اجرا شوند. حاصل آنها مثل حالتي است که آنها به طور تربيتي اجرا مي‌شوند. "" اين خاصيت براي آن است که اطمینان حاصل کنیم که هر ناحیه بحراني» يك واحد منطقي از کار را ایجاد مي‌کند که یا کاملاً اجرا مي‌شود یا اصلاً اجرا نمي‌شود. )0 مدل سیستم تراکنش: مجموعه‌ي از دستورات (عملیات) که يك عمل منطقي را انجام مي‌دهد تراککش ‎2h (ti (Drees)‏ نکته مهم در رابطه با پردازش تراکنش‌ها» حفظ ويژگي اتمي» صرفنظر از امکان خرابي سیستم کامپيوتري است. 

صفحه 61:
راهكارهاي تصمین اتمي بودن تراکنش: 1 محيطي که در هر زمان فقط يك تراکنش قابل انجام است. 1 حالتي که چندین تراکتش به طور همزمان مي‌توانند فعال باشند اثر تراكنش تصديق شده نمي‌تواند توسط لغو تراکنش» خنثي شود. ال نکته: هر تراکنش دنباله‌اي از عملیات لمح و عبر که توسط عملیات بسح با ببس خاتمه مي‌یاید. بسبو(): لطلم میند که ترلکنش‌با موفقیت‌اجرا شدم ببسر(): لعلام میک‌ند که لجرليت راکنش‌به دليل‌خطاهاينطقي متوقنشده لست تراکنش تصدیق شده/ لغو شده: تراكنشي که به طور کامل اجرا شده است» تصدیق شده و گرنه لغو شده است. 

صفحه 62:
براي تعيين اينكه سیستم چگونه باید خاصیت اتمي را تضمین کند مي‌بایست خواص دستگاههاي ذخیره كنندسي داده مورد نیاز تراکنش‌ها را شناسايي کنیم. دستگاههاي ذخیره داده‌ها بر حسب سرعت نسبي» ظرفیت و قابلیت ترمیم خرابي متمایز مي‌شوند. [] حافظه ناپایدار: اطلاعات موجود در حافظه ناپایدار بر ار خرابي سیستم ازبین مي‌روند. (حافظه اصلي و پنهان) [] حافظه پایدار: اطلاعات موجود در حافظه پایدار بر اثر خرابي سیستم از بین نمي‌روند. (ديسكهاء نوارها) [] حافظه ماندگار: حافظه‌اي که اطلاعات آن از بین نمي‌روند. براي این منظور باید کپي‌هاي متعددي از اطلاعات روي دیسك تهیه شود و اطلاعات تحت کنترل خاصي بروز شوند. 

صفحه 63:
6-0-8 ترمیم بر اساس سابقه يك روش حصول اطمينان از اتميبودن تراكنش اين است كاه سابقه تغبیرات اطلاعات توسط تراکنش» در حافظه ماندگار ذخیره شود. متداواتریسن انجام ایسن کار ایسن است که مساختمان داه‌اي به نام سابقه بر روي حافظه تشکیل شود. هر رکورد سابقهء يك عملیات از نوشتن تراکنش را توصیف مي‌کند و داراي فيلدهاي زي راست: [] نام تراکنش: نام منحصر به فرد تراكنشي که عمایات ‎rte‏ را انجام داد [] نام قلم داده: نام منحصر به فرد قلم داده‌اي که نوشته شده است [] مقدار قديمي: مقدار قلم داده قبل از عمل نوشتن [] مقدار جدید: مقدار قلم داده پس از عمل نوشتن 

صفحه 64:
0-0-2 نقاط كنترلي وقتي سیستم خراب شود باید با استفاده از سابقه؛ تراکنش‌هايي را که نیاز به داده‌هاي قديمي و تراكنش‌هايي که نیاز به داده‌هاي جدید دارنده تعيين كنيم. در واقع براي اینکار باید کل سابقه را جستجو کنیم. این روش دو عيب عمده دارد: 1 جستجو در سابقه منحصر به هدر رفتن وقت مي‌شود. 1 اغلب تراكنش‌هايي که بر اساس الگوریتم ما دوباره بايد اجرا شوند قبلاًداده‌هايي را بروز کرده‌اند و سابقه مي‌گوید که آنهاباید اصلاح شوند. گر چه این عمل ضرري ندارد اما زمان ترمیم طولاني مي شود. برلي كاهش اين سربارهاء مفهوم نقاط كنترلي را مطرح مي‌کنيم. در حين اجراء سیستم سابقه را تشکیل مي‌دهد. علاوه بر اين» سیستم متناوباً نقاط كنترلي را نیز اجرا مي‌کند. 

صفحه 65:
9-7 تراکنش‌هاي اتمي همزمان چون هر تراکنش اتمي است» نتایج اجراي همزمان تراکنش‌ها باید معادل حالتي باشد که آنها به ترتیب دلخواهي به طور سریال اجرا ميشوند؛ اين خاصيت که قابلیت سريال‌سازي (مسعسفببی9)) نام دارد؛ به اين ترتیب بدست مي‌آید که هر تراکنش در يك ناحیه بحراني اجرا شود. يعني تمام تراکنش‌ها در يك سمافور «سی() مشترك هستند که مقدار اولیه آن 4 است» وقتي تراكنشي شروع به اجرا مي‌کند؛ اولین کارش اجراي عملیات (مبسه(0) #مس است. پس از اينکه تراکنش تصدبق یا لفر شد» عملیات (محف)) لس را اجرا مي‌کند. 0-2 قابلیت سريال‌سازي سيستمي با اقلام داده‌اي 0) و 0 را در نظر بگیرید که هر دو توسط تراكلش‌هاي ,۳ و ‎Dy‏ خوانده و نوشته مي‌شوند. فرض کنید این تراکنش‌ها به طور دائمي اجرا مي‌شوند. به طوریکه ابتدا ,۳" و سپس اجرا ميشوند اين ترتیب اجرا زمانبندي نام دارد. 

صفحه 66:
شکل زیر زمانبندي سریال که در آن ‎Dy‏ و سپس ,۳ اجرا مي‌شود نشان مي‌دهد زمانبندي سریال: زمانبنديي که در آن» هر تراکنش به طور اتمي اجرا مي‌شود. هر زمانبندي سریال متشکل از دنباله‌اي از دستورات از تراكنش‌هاي مختلف است که دستورات مربوط به يك تراکنش با هم در آن زمانبندي ظاهر مي‌شود. *0* بنابراين براي يك مجموعه + تراكنشيء تعدلد زمانبندي سریال معتبر ب است. 

صفحه 67:
م6 پروتکل قفل كردن یيك روش براي حصول اطمینان از قابلیت سريال‌سازي اين است که به هر قلم داده يك قفل نسبت داده شود. در نتيجه نياز به بروتكل قفلكردن است تا شيوه قفل كردن و باز كردن قفل را مشخص ميكند. يك قلم داده به شكلهاي كوناكوني ميتواند قفل شود كه در اينجا © حالت اشاره شده: «حالت اشتراك: اكر تراكنش 58 داراي قفل حالت اشتراك بروي قلم داده © باشد كه با © نشان داده شود آنكاه 4 ميتولند © را بخواند ولي نميتواند بنويسيد. «حالت انحصاري: اكر تراكنش ,7 داراي قفل حالت انحصاري بروي قلم داده 9 باشد که با 7۷ نشان داده مي‌شوده آنگاه (» مي‌تواند 3 را بخواند و بنویسید. 

صفحه 68:
يك پروتکل که قابلیت سريالسازي را تضمین مي‌کند پروتکل قفل دو مرحله‌اي است. اين پروتکل مستلزم این است که هر تراکنش درخواست قفل کردن و بازکردن قفل را در دو مرحله انجام دهد: مرحله رشد: تراکنش ممکن است قفلي را ایجاد کند اما ممکن است قفلي را باز نکند. مرحله کوچك شدن: تراکنش ممکن است قفل‌هايي را باز کند ولي ققل‌هاي جديدي را ایجاد نمي‌کند. ههه من بروتكلهاي زماني روش ديكر براي تضمين ترتيب قابليت سريالسازي (علاوه بر اين حالت كه؛ در زمان اجرا با اولين قفلي كه هر دو تراكنش درخولست ميكنند و شامل حالتهاي ناسازكارياند؛ تعيين ميشود)؛ اين است که؛ از قبل ترتيبي بين تراكنشها انتخاب شود. *0* متداولترين انجام اين كار استفاده از الكوي زماني است. 

صفحه 69:
دو روش ساده براي پياد‌سازي اين الگو وجود دارد: 1._استفاده از ساعت سيستم به عنوان مهر زماني. يعني مهرزماني يك تراکنش برابر با مقدار ساعت سیستم در زمان ورود تراکنش به سیستم است. 11 . استفاده از شمارنده منطقي به عنوان مهر زماني. يعني مهرزماني يك تراكنش برابر با مقدار شمارنده در هنكام ورود تراكنش به سيستم است. ‎gla year‏ زماني تراكنشهاء ترتيب قابليت سريالسازي را مشخص ميكند. 

صه ی فصل 7سیستم عامل دانشگاه آزاد اسالمي واحد قائم‌شهر استاد :آقای عسکری ‏میالد ‏میالد قاسمپوری اعضای جعفری جعفری گروه : زاهدی رضا ‏ زاهدی رضا آذین ‏ آذین مهرپورشاد مهرپورشاد فصل هفتم هماهنگی فرآیندها دانشگاه آزاد اسالمي واحد قائم‌شهر LOGO فصل هفتم :هماهنگی فرآیندها در فص2ل 4مدل2ی از س2یستم را اجرا کردی2م ک2ه شامل تعدادی از فرآیندهای ترتیب2ی همکار بوده اس2ت ک2ه همگ2ی به طور ناهماهن2گ اجرا م2ی شدن2د و احتماال داده های مشترکی داشتند .ای2ن مدل را ب2ا اس2تفاده از الگوی میانگی2ر (بافر) محدود ،ب2ه عنوان نمایش2ی از س2یستم های عام2ل ،توضیح داریم. راه ح2ل حافظ2ه مشترک برای مس2ئله باف2ر محدود در نظ2ر می گیری2م :گفتی2م ک2ه حداکث2ر ی2ک Buffer- sizeقل2م داده م2ی تواند ب2ه طو2ر همزمان در باف2ر وجود داشت2ه باشد .برای برطرف کردن ای2ن عی2ب از ی2ک شمارنده برای باف2ر اس2تفاده م2ی کنیم ک2ه دارای مقدار اس2ت ب2ا ورود ه2ر قل2م شمارنده اضاف2ه و با LOGO هماهنگی: فصل هفتم فرآیندها کد مربوط به تولید کننده – مصرف کننده به صورت زیر تغییر می : کند while(1) { /* produce an item in nextproduced */ while (counter == buffersize) /* do nothing */ buffer[in] = nextproduced; in = (in+1)%buffer-size; Counter++; } { while(1) while (counter == 0) /* do nothing */ ;nextproduced = buffer[out] ;out = (out+1)%buffer-size ;--Counter /* consume the item in next consumed*/ } تولید کننده مصرف کننده LOGO فصل هفتم :هماهنگی فرآیندها ای2ن دو روال ب2ه طور جداگان2ه درس2ت عم2ل م2ی کنن2د ام2ا به طور همزمان ممکن است به درستی عمل نکنند مثال اگر Counter = 5و فرآیندهای تولیدکننده و مص2رف کننده دستورات “ ”++Counterو “ ”--Counterرا همزمان اجرا کنن2د مقدار Counterممک2ن است ،4 6 ،5باش2د ول2ی مقدار درس2ت 5و وقت2ی تولی2د م2ی شود ک2ه هر کدام به طور جداگانه عمل کنند. ‏عل2ت رس2یدن ب2ه حال2ت نادرس2ت دس2ترسی همزمان فرآینده2ا به داده ی مشترک Counterاست. LOGO فصل هفتم :هماهنگی فرآیندها حالت مسابقه ( ) Race Condition چنی2ن وضعیت2ی ک2ه چندی2ن فرآین2د ب2ه طو2ر همزمان به داده ای دس2ترسی دارن2د و نتیج2ه اجرا ب2ه ترتی2ب دس2تیابی فرآیندها بستگی دارد Rase Condition ،می گوییم. راه حل مقابله با Race Condition برای مقابل2ه ب2ا حال2ت مس2ابقه بای2د تضمی2ن شود ک2ه در هر زمان تنه2ا ی2ک فرآین2د ب2ه متغی2ر Counterدس2ترسی داشت2ه باش2د که برای چنین کاری نیاز به هماهنگی فرآیندهاست. LOGO فصل هفتم :هماهنگی فرآیندها 2-7مسئله ناحیه بحرانی س2یستمی ب2ا nفرآین2د { } P0 , P1 , … , Pn-1را در نظ2ر بگیرید .هر فرآین2د بخش2ی ک2د ب2ه نام ناحی2ه بحران2ی ( )Critical Sectionدارد که فرآین2د ممک2ن اس2ت در آ2ن متغیرهای مشترک را تغیی2ر دهد ، جدولی را بروز کند ،فایلی را بنویسد ،و ... ویژگ2ی مه2م ای2ن اس2ت هنگامیک2ه ی2ک فرآین2د در حال اجرای ناحیه ی بحران2ی خودش اس2ت ،هی2چ فرآین2د دیگری نبای2د اجازه داشته باش2د ناحی2ه بحران2ی خودش را اجرا کند .بنابرای2ن اجرای ناحیه ی بحران2ی توس2ط فرآینده2ا ،از نظ2ر زمان2ی انحص2ار متقابل (mutually )exclusiveاست. LOGO فصل هفتم :هماهنگی فرآیندها مسئله ناحیه بحرانی طراح2ی پروتکل2ی اس2ت ک2ه فرآینده2ا م2ی توانن2د ب2ه صورت همکار عمل کنند ،هر فرآیند برای ورود به ناحیه ی بحرانی خودش ، بای2د اجازه بگیرد .بخش2ی از ک2د ک2ه درخواس2ت اجازه ص2ادر می کن2د ،ناحی2ه ی ورودی ( )entryنام دارد و بقی2ه ک2د را ناحیه باقیمانده می نامند. LOGO فصل هفتم :هماهنگی فرآیندها راه ح2ل مس2ئله ناحی2ه ی بحران2ی باید 3نیازمندی را برآورده کند : .I : Mutual exclusiveا2گ2ر ف22رآ2ی2ن2د P1در حا22لتا2جرا2ی ن22احیه 2ی ب222حرا2ن2یا2شب22اش2د ،هی2چ ف22رآ2ی2ند د2ی2گرین22باید ا2جاز2ه 2ی ا2جرا2ی ن22احیه 2ب222حرا2ن2یا2شرا دا2ش2ته 2ب22اشد. .II پیشروی :اگ2ر هی2چ فرآیندی در ناحی2ه ی بحران2ی اش نباشد ول2ی فرآیندهای2ی باشن2د ک2ه بخواهن2د وارد ناحی2ه ی بحرانی خودشان شون2د ،آنگاه فق2ط فرآیندهای2ی که در حال اجرای ناحی2ه ی باقیمانده خودشان نیس2تند م2ی توانن2د برای ورود به ناحی2ه ی بحران2ی خودشان انتخاب شون2د و ای2ن اتفاق نمی تواند بطور نامحدود به تعویق بیفتد. LOGO فصل هفتم :هماهنگی فرآیندها 1-2-7راه حل های دو فرآیندی در ای2ن قس2مت ب2ه الگوریت2م های2ی م2ی پردازی2م ک2ه در هر زمان فق2ط بروی دو 2فرآین2د عم2ل م2ی کنند .فرآینده2ا با P0 {do و P1 ناحیهم2ی کنیم مشخ2ص م2ی شون2د برای س2هولت وقت2ی از Piاس2تفاده برای نشان دادن فرآین2د بعدی از Pj اس2تفاده م2ی کنی2م که ورودی ‏j==1-i ساختار کلی فرآیند نمونه Pi ناحیه بحرانی ناحیه خروج ناحیه باقیمانده LOGO فصل هفتم :هماهنگی فرآیندها 1-1-2-7الگوریتم 1 اولی2ن راه ح2ل ای2ن اس2ت ک2ه از متغی2ر مشترک2ی ب2ه نام turnاستفاده وارد است. اولیه آن 0 ناحیه ی بحرانی خود شود مقدار دارد کهاجازه کنیمPi فرآیند =i ‏ ای2ن راه ح2ل تض2می2ن م2ی کن2د که در ه2ر زمان فق2ط ی2ک فرآیند وارد ناحی22ه ی بحران22ی اش شود اما ;)while (turn!=0 ناحیه بحرانی نیازمندی پیشروی را برآورده 2نمی کن2د زیرا دقیق2ا مشخ2ص م2ی کن2د که چ22ه فرآیندی بای22د وارد ناحیه ی بحرانی خودش شود. ;turn=j ناحیه باقیمانده ‏turn اگر {do LOGO فصل هفتم :هماهنگی فرآیندها 2-1-2-7الگوریتم 2 مشک2ل الگوریت2م 1ای2ن اس2ت ک2ه اطالعات کاف2ی در مورد حال2ت هر فرآین2د نگهداری نم2ی کن2د بلک2ه فق2ط مشخ2ص م2ی کند کدام فرآین2د اجازه ی ورود ب2ه ناحی2ه ی ورود ب2ه ناحی2ه ی بحرانی خودش را دارد ک2ه برای ح2ل ای2ن مشک2ل ب2ه جای متغیر turnاز آرایه زیر استفاده می شود : مقدار اولیه عناص2ر آرای2ه falseاست ]boolean flag[2 ‏اگ2ر flag[i] =trueباش2د نشان م2ی ده2د ک2ه Piآماده ورود ب2ه ناحیه ی بحرانی اش است. LOGO فصل هفتم :هماهنگی فرآیندها ‏ه2ر فرآین2د برای ورود ب2ه ناحی2ه ی بحران2ی منتظ2ر م2ی مان2د تا flag مربوط ب2ه فرآین2د ناحی2ه ی بحران2ی falseشود و ه2ر فرآیند هنگام خروج از ناحیه ی بحرانی flagمربوط به خود را falseمی کند {do ;falg[i]=true ساختار فرآیند Piدر ;)]While (flag[j الگوریتم ناحیه2بحرانی ;falg[i]=false ناحیه باقیمانده ;)}while(1 LOGO فصل هفتم :هماهنگی فرآیندها ‏ در این روش: .I .IIشرط پیشروی برقرار نیست شرط انحصار متقابل برقرار است مثال :برای تشریح مسئله فوق این دنباله را در نظر می گیریم : اکنون P0و P1در حلقه whileگیر می کنند. ‏ ‏T0 : P0 Sets flag[0] = True ‏T1 : P1 Sets flag[1] = True ای2ن الگوریت2م ب2ه زمانبندی دقی2ق 2دو فرآین2د بس2تگی دارد .این دنبال2ه م2ی توان2د در محیط2ی باش2د ک2ه چندی2ن فرآین2د به طور همزمان در حال اجرا هس2تند و ی2ا بالفاص2له بع2د از T0وقفه رخ دهد و CPUاز یک فرآیند به فرآیند دیگر برود. LOGO فصل هفتم :هماهنگی فرآیندها 3-1-2-7الگوریتم 3 در این روش فرآیندها دارای دو متغیر مشترکند ;]Boolean flag[2 ;Int turn ‏در آغاز flag[0] = flag[1] = falseاست {do ;falg[i]=true ;turn=j ساختار فرآیند Piدر الگوریتم While (flag[j] && turn=j );3 ناحیه بحرانی ;falg[i]=false ناحیه باقیمانده ;)}while(1 LOGO فصل هفتم :هماهنگی فرآیندها ‏فرآین2د Piبرای ورود ب2ه ناحی2ه ی بحران2ی ابتدا ] flag[1را Trueمی کند .اگ2ر ه2ر دو فرآین2د س2عی کنن2د همزمان وارد ناحی2ه ی بحرانی شون2د turn ،در آ2ن واح2د م2ی خواه2د iو jشود .ام2ا فق2ط ی2ک دستور انتس2اب بعدی انجام م2ی شود و مقدار قبل2ی از بی2ن می رود. مقدار نهای2ی turnمشخ2ص م2ی کن2د کدامی2ک از دو فراین2د ،زودتر اجازه ورود به ناحیه ی بحرانی را پیدا می کنند. LOGO فصل هفتم :هماهنگی فرآیندها ‏ای2ن روش ویژگ2ی های زی2ر را دارا می باشد : .I :Mutually exclusiveهر ف22رآ2ی2ن2د Piو2ق2ت2یم2یت22وا2ن2د وارد ن22احیه2 ی ب222حرا2ن2یا2شش22ود ک22ه 2ی22ا flag[i] = falseی22ا . turn = iا2گر دو ف22رآ2ی2ن2د ب222خوا2هن2د همزمانوارد ن22احی2ه 2ی ب222حرا2ن2یش22وند آ2ن2گاه flag[0] = flag[1] = True 2ک22ه 2ب22دی2نت22رت2یب P0و P1 ن22م2یت22وا2ن2ند همزمانحلق2ه while 2خود را ا2جرا ک22نند چرا ک22ه2 م2قدار turnم2یت22وا2ند در ی22کز2مان 0ی22ا 1ب22اشد. .II .IIIشرط انتظار محدود شرط پیشروی LOGO فصل هفتم :هماهنگی فرآیندها برای اثبات ویژگ2ی 2و 3در ص2ورتی م2ی توان مانع از ورود فرآین2د Piب2ه ناحی2ه ی بحران2ی اش ش2د ک2ه یا flag[j] = Trueو turn = Trueدر حلقه whileگیر کند. .A اگ2ر Pjآماده ورود ب2ه ناحی2ه ی بحران2ی نباشد آنگاه = ]flag[j falseو Piمی تواند وارد ناحیه ی بحرانی می شود. .Bاگ2ر turn = jباش2د و Pjوارد ناحی2ه بحران2ی م2ی گردد .وقتی Pj وارد ناحی2ه بحران2ی flag[j] = falseم2ی گردد و Piاجازه پیدا می کند تا وارد ناحیه ی بحرانی خود شود. .Cاگ2ر Pjمقدار ] flag[jرا برابر Trueقرار ده2د بای2د turn = iنیز باش2د ام2ا چون Piدر حی2ن اجرای دستو2ر ، whileمقدار turnرا تغییر نمی دهد Pi ،حداکثر پس از یک بار ورود Pjدر ناحیه ی LOGO فصل هفتم :هماهنگی فرآیندها 2-2-7راه حل های چند فرآیندی الگوریت2م نانو2ای2ی ( )bakery algorithmبرای ح2ل ناحی2ه ی بحران2ی به اندازه ی nفراین2د اس2ت ک2ه ای2ن الگوریت2م را برای محی2ط توزیع2ی طراحی شد. ای2ن الگوریت2م ب2ه ه2ر مشتری هنگام ورود شماره ای م2ی دهد و مشتری بعدی ک2ه بای2د خدمات بگیرد مشتری اس2ت که شماره ی کوچکتری دارد در ضم2ن الگوریت2م تضمی2ن نم2ی کن2د که شماره ی مشتریان یکس2ان نباش2د اگ2ر شماره ی مشتریان یکسان بود مشتریی که نام کوچکتری دارد زودتر خدمات می گیرد. انتخاب می شود Pi i<jا2گر شماره یکسان Pjو Pi ا2گر LOGO فصل هفتم :هماهنگی فرآیندها ساختمان داده های مشترک عبارتند از : ‏مقدار اولیه ی این ساختمان داده ها به ترتیب falseو 0است. ];boolean choosing[n ];int number[n این الگوریتم شرط های سه گانه را داراست. ساختار فرآیند Piبر الگوریتم Backeryدر شکل زیر نشان داده شده است : {do ;Choosing[i]=true ;)Number[i]=max(number[0], number[1], …,number[n-1]+1 ;Choosing[i]=false {)For(j=0;j<n;j++ ;)]while(choosing[j ;))]while((number[j]!=0)&&(number[j,j]<number[i,i } ناحیه بحرانی ;number[i]=0 ناحیه باقیمانده ;)}while(1 LOGO فصل هفتم :هماهنگی فرآیندها 3-7ویژگی های سخت افزاری برای هماهنگی فرآیند برای مس2ئله ی ناحی2ه بحران2ی در محی2ط ت2ک پردازنده ای کافی است اجازه ندهیم در حین تغییر متغییرهای عمومی ،وقفه ای رخ دهد .اولی2ن روش در محی2ط چن2د پردازنده ای امکان پذیر نیس2ت چرا ک2ه غی2ر فعال کردن وقف2ه ه2ا در ی2ک محی2ط چند پردازنده ای م2ی توان2د موج2ب اتالف وق2ت شود زیرا پیام به تمام پردازنده ها ارسال می شود ‏ بنابر ای2ن اغل2ب ماشی2ن ه2ا دس2تورات س2خت افزاری خاصی را تدارک م2ی بینن2د ک2ه م2ی توان کلم2ه ای را تس2ت کن2د یا محتویات2ش را تغیی2ر ده2د ی2ا اتم2ی محتویات دو کلمه را عوض کند. LOGO فصل هفتم :هماهنگی فرآیندها دستور Test And Set ب2ه طور اتمی2ک اجرا م2ی شود یعن2ی ب2ه عنوان ی2ک واح2د بدون وقفه اجرا م2ی شود بنابرای2ن اگ2ر دو دس2تور Test And Setهمزمان ،هر کدام در یک CPUاجرا شوند ،به صورت ترتیبی اجرا می شوند. ){boolean Test And Set (boolean & target ;boolean rv = target ;target = true ;return rv } LOGO فصل هفتم :هماهنگی فرآیندها ‏o اگر ماشین از دستور Test And Setپشتیبانی کند برای پیاده سازی انحصاری یک متغیر بولین به نام lockتعریف می کنیم و مقدار اولیه آنرا falseدر نظر می گیریم .ساخت فرآیند Piدر اینجا آمده است. {do ));while (TestAndSet(lock ناحیه ی بحرانی ;lock = false ناحیه ی باقیمانده });while(1 LOGO فصل هفتم :هماهنگی فرآیندها دستور Swap دس2تور Swapبر روی محتویات دو کلم2ه کار م2ی کن2د ک2ه ای2ن دستور نیز مانند Test And Setبه طور اتمیک اجرا می شود. ){void swap(boolean & a ,boolean & b ‏این الگوریتم ها نیازمندی انتظار محدود را برآورده می کنند. ;Boolean temp = a ;a = b ;b = temp } LOGO فصل هفتم :هماهنگی فرآیندها الگوریتمی که در زی2ر آمده از دستور Test And Setاستفاده می کند و تمام نیازمندیهای س2ه گان2ه ناحی2ه ی بحران2ی را برآورده می کند. این مشترک اولیههای مقدار داده ساختمان ‏ ازfalse: عبارتندها ساختمان داده است. ];boolean waiting[n برای اثبات اینکه الگوریتم mutually exclusiveرا رعایت می کند : ;boolean lock می دانیم که فرآیند Piوقتی می تواند وارد ناحیه ی بحرانی شود که waiting = falseیا key = falseباشد و keyوقتی می تواند falseباشد که دستور Test And Set اجرا شده باشد .اولین فرآیندی که دستور Test And Setرا اجرا می کند می فهمد که key = falseو بقیه فرآیندها باید منتظر بمانند. متغیر ] waiting[iدر صورتی falseمی شود که فرآیند دیگری از ناحیه ی LOGO فصل هفتم :هماهنگی فرآیندها 4-7سمافورها س2مافور ی2ک متغی2ر ص2حیح اس2ت ک2ه ص2رف نظ2ر از مقداردهی اولی2ه ،فق2ط از طری2ق دو عم2ل اس2تاندارد اتمی2ک به نام های ){wait(s waitو signalقاب2ل دس2تیابی اس2ت ک2ه گاه2ی نام Pرا به waitو V )while(s≤0 را به signalنسبت می دهند تعاریف waitو signalبه صورت مقابل است : ;no-op// ;--s } ){signal(s ;++s } LOGO فصل هفتم :هماهنگی فرآیندها ‏ هنگامیک2ه ی2ک فرآین2د در حال تغیی2ر مقدار س2مافور اس2ت هیچ فرآین2د دیگری نم2ی توان2د مقدار همان سمافور را در همان زمان تغییر دهد. ‏ در حال2ت ) ، wait(sتس2ت مقدار س2مافور ) S (s≤0و تغیی2ر احتمالی {do شود. بدون وقفه انجام )-بایدآن (s سمافورها کاربرد 1-4-7 );wait(mutex ناحیه بحرانی مس2ئله ی ناحیه ی بحران2ی nفرآین2د را می توانیم با استفاده از س2مافورها ح2ل کنیم n.فرآیند دارای سمافور مشترکی به نام mutexهس2تند ک2ه مقادی2ر اولی2ه آن 1 است و هر فرآیند );signal(mutex ناحیه باقیمانده });while(1 LOGO فصل هفتم :هماهنگی فرآیندها 2-4-7پیاده سازی سمافور عی2ب عمده ی راه ح2ل های انحص2ار متقاب2ل و تعری2ف س2مافوری که ارائ2ه ش2د ای2ن اس2ت هم2ه ی آ2ن ه2ا نیازمن2د انتظار مشغول هستند ( .)busy waitingانتظار مشغول در س2یستم های چن2د برنام2ه ای با ی2ک ، CPUزمان CPUرا هدر م2ی ده2د ام2ا ای2ن روش در سیستم های چن2د پردازنده ای مفی2د اس2ت چرا ک2ه دیگ2ر نیاز ب2ه صرف زمان زیادی برای تعوی2ض بس2تر نیس2ت و فرآین2د تنه2ا م2ی بایست در مدت زمان قفل منتظر بماند. برای رف2ع مشک2ل busy waitingتعری2ف عملیات waitو signalرا تغییر م2ی دهیم .وقت2ی فرایندی waitرا اجرا م2ی کن2د ،در صورتیکه مقدار س2مافور مثب2ت نباش2د ،بای2د منتظ2ر بمان2د و به جای busy LOGO فصل هفتم :هماهنگی فرآیندها ‏عملیات انس2داد ،فرآیندی را در ص2ف انتظار وابس2ته ب2ه آ2ن سمافور قرار می دهد و حالت فرآیند ب2ه حال2ت انتظار تبدی2ل می شود .سپس کنترل ب2ه زمانبن2د CPUم2ی رود ت2ا فرآیند دیگری را برای اجرا انتخاب کند. ‏فرآیندی ک2ه در انتظار س2مافور Sمس2دود اس2ت ،در اثر عملیات ، signalتوس2ط فرآین2د دیگ2ر ،بای2د دوباره شروع ب2ه اجرا نمای2د که شروع دوباره ی فرآین2د ب2ا عملیات wakeupانجام م2ی شود ک2ه فرآیند را از حال2ت انتظار ب2ه حال2ت آمادگ2ی م2ی برد .س2پس ای2ن فرآیند در صف آمادگی قرار می گیرد. ‏ه2ر س2مافور دارای ی2ک مقدار ص2حیح و لیس2تی از فرآیندهاست. وقت2ی فرآیندی بای2د منتظ2ر س2مافور بمان2د ،ب2ه لیس2تی از فرآیندها LOGO فصل هفتم :هماهنگی فرآیندها عملیات waitسمافور می تو2اند به صورت زیر پیاده سازی شو2د: ){void wait(semaphore S ;--S.value ){if(S.value<0 ;add this process to S.L ;)(block } عملیات ، blockفرآیندی که آنرا فرخوانی کرده به تعویق می اندازد LOGO فصل هفتم :هماهنگی فرآیندها عملیات signalسمافور نیز می تواند به صورت زیر پیاده سازی شود: ){void signal(semaphore S عملیات )wakeup(p اجرای فرآیند مسدود شده Pرا از سر می گیرد ;++S.value ){if(S.value<=0 ;remove a process P from S.L );wakeup(p نکت2ه :عملیات blockو wakeupب2ه ص2ورت فرخوان های سیستم در سیستم عامل پیاده سازی شده اند } LOGO فصل هفتم :هماهنگی فرآیندها 3-4-7بن بست ها و حالت گرسنگی پیاده س2ازی س2مافو2ر ب2ا ص2ف انتظار ،ممک2ن اس2ت منج2ر ب2ه این شود ک2ه دو ی2ا چن2د س2مافور دائم2ا منتظ2ر رویدادی باشن2د ک2ه توس2ط یکی از فرآیندهای منتظ2ر ناشی شود .رویداد مورد انتظار ،اجرای عملیات است ( به این حالت بن بست می گوییم ) عملیات)wait(S را اجرا م2ی کن2د بای2د منتظ2ر بمان2د تا P0عملیات ) signal(Sرا اجرا ... ) wait(Qرا ا2جرا ن22ماید .ب222ه 2همی2نت22رت2ی2بو2ق2تیP1 ... ‏P1 وجود دارند و S اجرا و 1 فرآیند P0 مثال :دو بست با تشریح ب2ن ‏Pو کند ) wait(Sرا عملیات کنی2د P0 فرض )wait(Q )wait(S یک هستند. Pمقدار سمافور عملیات سپس 1 ‏P0 و Qدر ;);wait(S ;);wait(Q );Signal(S); Signal(Q );Signal(Q); Signal(S LOGO فصل هفتم :هماهنگی فرآیندها مس2ئله دیگ2ر در مورد ب2ن بس2ت انس2داد ی2ا گرس2نگی اس2ت .در این وضعی2ت ،فرآینده2ا در داخ2ل س2مافور ب2ه طو2ر نامحدود منتظ2ر می ماند .انس2داد نامحدود در ص2ورتی اتفاق م2ی افت2د ک2ه فرآیندهایی را از ص2ف مربوط ب2ه سمافور حذف ی2ا اضاف2ه کنیم ک2ه ب2ه ترتیب LIFO است.دودویی سمافورهای 4-4-7 سازماندهی شده س2مافورهای دودوی2ی بر خالف س2مافورهای شمارش2ی ک2ه در بخش قب2ل گفت2ه ش2د م2ی توان2د تنه2ا مقادی2ر 0یا 1را بپذیرد. (س2مافورهای شمارش2ی م2ی توانن2د ه2ر مقدار صحیحی را بپذیرند) پیاده س2ازی س2مافورهای شمارش2ی ب2ا استفاده از سمافور دودویی: LOGO هماهنگی: فصل هفتم فرآیندها S درWait عملیات wait(s); C-if(C<0){ signal(s1) wait(s2) } signal(s1) S درsignal عملیات ;wait(s1) ;++C if(C<=0) signal(s2) else signal(s1) LOGO فصل هفتم :هماهنگی فرآیندها 5-7مسائل کالسیک هماهنگی فرآیندها 1-5-7مسئله بافر محدود ساختار کلی الگوی بافر محدود بدین صو2رت است که فرض می کنیم انبار بافرها حاوی nبافر است و هر بافر می تواند یک قلم داده را ذخیره کند. ‏ سمافور mutexانحصار متقابل را برای دستیابی به انبار بافر فراهم می کند و مقدار اولیه آن یک است. ‏ سمافورهای emptyو fullبه ترتیب تعداد بافرهای خالی و پر را شمارش می کنند. LOGO هماهنگی: فصل هفتم فرآیندها {do … produce an item in next P … ;wait(empty) ;wait(mutex) … ;add nextP to buffer … ;signal(mutex) ;signal(full) ;while(1)} ساختار فرآیند تولید : کننده = م"قدار او"ل"یهn empty full = مقدار اولیه0 LOGO هماهنگی: فصل هفتم فرآیندها : ساختار فرآیند مصرف کننده {do ;wait(full) ;wait(mutex) … remove an item from buffer to nextC … ;signal(mutex) ;signal(empty) … ;consume the item in nextC … ;while(1)} LOGO فصل هفتم :هماهنگی فرآیندها 2-5-7مسئله خوانندگان و نویسندگان ی2ک شی داده مثل فای2ل را رکورد ،بین فرآیندهای همزمان به اشتراک گذاشت2ه م2ی شود ک2ه بعض2ی از فرآین2د ه2ا ممک2ن است نخواهن2د محتویات ش2ی را بخوانن2د ول2ی بعض2ی دیگ2ر ممکن اس2ت بخو2اهن2د ش2ی داده را تغیی2ر دهند .فرآیندهای2ی ک2ه فقط عم22ل خواندن را انجام م2ی دهن22د را خوانندگان و بقیه نویسندگان می نامیم. اگ2ر دو خواننده همزمان ب2ه ش2ی داده مشترک دس2تیابی داشته باشن2د مشکل2ی ایجاد نم2ی شود ام2ا اگ2ر نویس2نده و فرآیند برای رفع این مشکل الزم است نویسندگان دستیلبی دیگ2ر ( نویس2نده ی2ا خواننده ) ب2ه طور همزمان ب2ه شی مشترک انحصاری به شی مشترک داشته باشند ( مسئله خوانندگان – دستیابی داشته باشند ،مشکل ایجاد می شود. LOGO فصل هفتم :هماهنگی فرآیندها مس2ئله خوانندگان و نویس2ندگان شک2ل های گوناگون2ی دارد و شامل اولویت های نیز هستند. .1اولی2ن مس2ئله ی خو2انندگان و نویس2ندگان ،هی2چ فرآیندی منتظ2ر نماند مگ2ر اینک2ه خواننده ای قبال اجازه دس2تیابی ب2ه ش2ی مشترک را کسب کرده باشد( منجر به گرسنگی نویسندگان می شود) .2دومی2ن مس2ئله خوانندگان – نویس2ندگان :وقت2ی نویسنده ای آماده ی نوشت2ن ش2د ،عم2ل نوشت2ن را ه2ر چ2ه زودت2ر انجام م2ی ده2د ( یعن2ی اگر نویسنده ای منتظر دستیابی به شی باشد ،هیچ خواننده ای شروع به خواندن نمی کند) (منجر به گرستگی خواننده می شود) به همین دلیل شکل های دیگری از مسئله طراحی شد. LOGO فصل هفتم :هماهنگی فرآیندها راه حل برای اولین مسئله خوانندگان – نویسندگان : سمافور ‏wrt=1, mutex = 1 ‏readcount = 0 ساختار فرآیند نویسنده : : readcountم2شخ2ص م2یک22ن2د چند ف22رآ2ی2ن2د در حا22لخوا2ندن ش22ی م2شترکهستند : Mutexت222ضمی2ن م22یک22ن2د و2ق2تی م2تغی2ر readcount ت222غیی2ر م2ی ک22ن2د ا2ن2حص2ار م2تقاب2لب22رقرار );wait(wrt … ‏writing is performed … );signal(wrt LOGO هماهنگی: فصل هفتم فرآیندها ;wait(mutex) ++ readcount if(readcount ==1) ;wait(wrt) ;signal(mutex) ... reading is performed ... ;wait(mutex) -- readcount if(readcount ==0) ;signal(wrt) ;signal(mutex) : ساختار فرآیند خواننده LOGO فصل هفتم :هماهنگی فرآیندها 3-5-7مسئله غذا خوردن فیلسوفان پن2ج فیلس2وف را در نظ2ر بگیری2د که زندگ22ی خود را ص22رف فکر کردن و غذا خوردن می کنند. فیلس2وفان دارای ی2ک میز دایره ای هس2تند ک2ه پن2ج صندلی دارد و هرکدام متعل22ق ب22ه یک فیلس2وف اس2ت .در مرک2ز یک دی2س از برن2ج قرار دارد و پنج قاش2ق نی2ز بروی می2ز واقع ‏RI ‏CE LOGO فصل هفتم :هماهنگی فرآیندها • وقت2ی فیلس2وفی در حال فک2ر کردن اس2ت ،تعامل2ی با همکاران2ش ندارد .گاه2ی ی2ک فیلس2وف گرس2نه می شود و س2عی م2ی کن2د قاش2ق نزدی2ک خود (قاش2ق بین او و همکاران چ2پ و راس2ت) را بردارد .فیلس2وف در ه2ر زمان فق2ط یک قاشق می تواند بردارد. • بدیه2ی اس2ت ک2ه فیلس2وف نم2ی توان2د قاشق2ی ک2ه دست همکارانش است را بردارد. • اگ2ر فیلس2وف گرس2نه ،ه2ر دو قاش2ق 2را در آ2ن واحد در اختیار داشته باشد ،بدون وقفه می تواند به خوردن ادامه دهد. • هنگامیک2ه کار خوردن تمام ش2د ه2ر دو قاش2ق را ب2ه روی میز می گذارد و دوباره شروع به فکر کردن می کند. LOGO فصل هفتم :هماهنگی فرآیندها ‏تذک2ر :مس2ئله غذا خوردن فیلس2وفان نمای2ش ساده ای از نیاز ب2ه تخص2یص چندی2ن منبع بین فرآیندهای مختلف است که بدون بست و گرسنگی انجام می شود. ‏ ی2ک راه ح2ل س2ادهبرای مس2ئله غذا خوردن فیلس2وفان این است که هر قاشق 2با یک سمافور نمایش داده شود. ه2ر فیلس2وف برای بدس2ت آوردن ی2ک قاشق ، 2عملیات waitرا بروی آن سمافور اجرا می کند و با اجرای عملیات signalبروی س2مافور مناس2ب ،قاش2ق را آزاد م2ی کن2د لذا داده مشترک به ص2ورت زیر2اس2ت ک2ه مقدار اولی2ه ی عناص2ر chopstickبرابر یک است. ];Semaphore chopstick[5 LOGO هماهنگی: فصل هفتم فرآیندها :i ساختار فیلسوف do{ wait(chopstick[i]); wait(chopstick[(i+1)%5]; … eat ... signal(chopstick[i]); signal(chopstick[(i+1)%5]); … think … }while(1); LOGO فصل هفتم :هماهنگی فرآیندها اگرچ2ه ای2ن راه ح2ل تضمی2ن م2ی کن2د ک2ه هی2چ دو همس2ایه ای به طور همزمان نمی خورند اما منجر به بن بست می گردد. تشری2ح ب2ن بس2ت در راه ح2ل فوق :اگ2ر ه2ر پن2ج فیلسوف همزمان گرس2نه شون2د و ه2ر کدام قاش2ق س2مت چپ خود را تص2احب کنن2د اکنون تمام عناص2ر chopstickبرابر ب2ا ص2فر خو2اهند بود .وقت2ی ه2ر فیلس2وفی س2عی م2ی کن2د قاش2ق س2مت راست خودش را بگیرد ،به تعویق می افتد. LOGO فصل هفتم :هماهنگی فرآیندها 6-7مناطق بحرانی اس2تفاده نادرس2ت از س2مافورها ممک2ن اس2ت منج2ر به خطاهای تنظیم وقت شود که کشف آن ها مشکل است. ;)Signal(mutex مثال : … اگر ترتیب اجرای عملیات waitو signalعوض شود ناحیه بحرانی ‏ممکن است جندین فرآیند به طور همزمان در حال اجرای … ناحیه ی بحرانی باشد. ;)wait(muntex LOGO فصل هفتم :هماهنگی فرآیندها • فرض کنی2د ب2ه جای ) signal(mutexاز ) wait(mutexاس2تفاده می کند که در این حالت بن بست اتفاق می افتد. • همچنی2ن اگ2ر )wait(mutex ی2ا )signal(mutex ی2ا هر دو را حذف کنی2م ،ی2ا انحص2ار متقاب2ل از بی2ن م2ی رود ی2ا ب2ن بس2ت رخ می دهد. س2اختار منطق2ه بحران2ی ی2ا ناحیه ی مشروط (Critical : )Regionی2ک ساختار هماهنگ2ی س2طح باال می باشد ک2ه جهت حل مشکالت مطرح شده در باال ارائه می گردید. در س2اختار منطق2ه ی بحران2ی و س2اختار ناظ2ر ک2ه در جلوتر بیان م2ی شود .فرض بر ای2ن اس2ت ک2ه ی2ک فرآیند حاوی داده ی محل2ی ،و ی2ک برنام2ه ترتیب2ی اس2ت ک2ه م2ی توان2د بروی آن داده LOGO فصل هفتم :هماهنگی فرآیندها داده محلی فقط از طریق آن برنامه قابل دستیابی است که در همان فرآیند بسته بندی شده است یعنی هیچ فرآیندی نمی تواند مستقیما به داده ی محلی فرآیند دیگر دستیابی داشته باشد. پیاده سازی ساختار منطقه مشروط مقدار اولیه : ‏Mutex = 1 ‏First-delay = 0 ‏Second-delay = 0 LOGO هماهنگی: فصل هفتم فرآیندها wait(mutex); while(!B){ first-count ++; if(second-count>0) signal(second-delay); else signal(mutex); wait(first-delay); first-count --; second-count++; if( first-count>0) signal(first-delay); else signal(second-delay); wait(second-delay); second-count --; } ;S if(first-count>0) ;signal(first-delay) else if(second-count>0) ;signal(secind-delay) else ;signal(mutex) LOGO فصل هفتم :هماهنگی فرآیندها • •اگ__ر فرآيندي نتوان__د ب__ه دلي__ل نادرس__ت بودن شرط منطق__ي Bوارد ناحي__ه بحران__ي شود در س__مافور دستيابي انحصار متقابل به ناحيه بحراني توسط Mutexفراهم مي‌شود. first-delayمي‌ماند. • فرآيندي ك_ه در س_مافور first-delayمنتظ_ر اس_ت ،قب_ل از اجازه‌ي ارزتياب_ي مجدد شرط منطقي B يس_ازد وقتي فرآيندي (عبارت ،Bيك عبارت منطقي اس_ت ك_ه دس_تيابي ب_ه ناحيه‌ي بحران_ي را مشروط م ‌ س_عي مي‌كن_د وارد ناحي_ه بحران_ي شود عبارت منطق_ي Bرا ارزياب_ي مي‌كن_د) ،ب_ه س_مافور Second- delayمنتقل مي‌گردد. • تعداد فرآيندهاي منتظ_ر در س_مافورهاي first-delay second-delayب_ه ترتي_ب توس_ط first-delayو second-delayمشخص مي‌شوند. LOGO فصل هفتم :هماهنگی فرآیندها • وقت_ي فرآيندي از ناحي_ه بحران_ي خارج مي‌شود ،ممك_ن اس_ت شرط ص_نعتي Bرا تغيي_ر ده_د ك_ه منج_ر به جلوگيري از ورود فرآيند ديگر به ناحيه بحرا_ني‌اش گردد. • فرآين_د قب_ل ا_ز ورود ب_ه ناحي_ه بحران_ي عبارت منطق_ي Bرا تس_ت مي‌كن_د ك_ه در ص_ورت ارزش درس___تي وارد ناحي___ه بحران___ي مي‌شود و در غي___ر اينص___ورت باي___د در س___مافورهاي first-delayو second-delayمنتظر بماند. LOGO فصل هفتم :هماهنگی فرآیندها 7-7ناظرها ()Minitor ساختار سطح باالي ديگر ناظر است كه براي حل مسائل وايجاد دو به دو ناسازگاري پيشنهاد مي‌شود مونيتورمجموعه‌اي از زيربرنامه‌ها ،متغيرها و ساختمان داده‌اي است كه همگي در يك ماژول خاص بسته‌بندي شده‌اند. ‏ماجول مربوط به مونيتور ،بين چندين فرآيند به اشترا_ك گذاشته مي‌شود. ‏ساختار مونيتور يا ناظر تضمين مي‌كند كه در هر زمان فقط يك فرآيند در داخل ناظر فعال باشد. ‏Monitor monitor-name { ‏shared variable declaration {)Procedure body P1(…. …. } {)Procedure body P2(…. …. } . . . {)Procedure body Pn(…. …. } { ‏initialization code } } LOGO فصل هفتم :هماهنگی فرآیندها ‏عالوه بر محتويات__ي ك__ه در باال براي مونيتور ذك__ر ش__د ،مانيتور مي‌توان__د حاوي متغيرهاي__ي از نوع‌هاي Conditionباشد كه مي‌توان عمل waitو signalرا بروي آن تعريف كرد. ‏فرآيندي كه عمل waitرا بر روي متغير conditionصدا زند بلوكه مي‌شود. ‏اگ_ر فرآين_د ديگري ب_ه اي_ن عل_ت ك_ه فرآين_د ا_ول در داخ_ل_ مونيتور قرار داش_ت متوق_ف شده بود، پس از رخداد باال ،مي‌تواند به اجراي خود ادامه داده و وارد مونيتور شود. ‏عم_ل Signalدقيقا ً ي_ك فرآين_د ب_ه تعوي_ق افتاده را از س_رگيري مي‌كند .اگ_ر هي_چ فرآيندي ب_ه تعوي_ق نيفتاده باشد ،عمليات Signalتأثيري نخواهد داشت. LOGO فصل هفتم :هماهنگی فرآیندها ص ف ور و د ی داده های مشترک شك_ل رو ب_ه رو شماتي_ك ي_ك ناظ_ر را نشان مي‌ده_د ك_ه بيانگ_ر اي_ن اس_ت ك_ه در ه_ر زمان فق_ط ي_ك فرآين_د ...... در داخل ناظر فعال است. عملیات کد مقدار دهی اولیه LOGO فصل هفتم :هماهنگی فرآیندها ص ف ور و د ی داده های مشترک شكل زير مونيتور با متغيرهاي ()x,y Conditionرا نشان مي‌دهد. ‏x ‏y صف وابسته به شرایط ‏Xو Y ...... عملیات کد مقدار دهی اولیه LOGO هماهنگی: فصل هفتم فرآیندها :نحوه‌ي استفاده از مونيتور در فرآيندهاي توليد كننده – مصرف كننده Monitor produeer-consumer; Full, empty; condition Procedure enter; Begin If count=N then wait (full) Enter-item; Count=count+1; If count=1 signal (empty) End; Procedure remove; Begin If count = 0 then wait (empty); Remove – item; Count = count – 1; If count = N – 1 Then signal (full); End; Count = 0; 2يه2هياول2قدارد2م// end monitor; Procedure producer Begin While true do Begin ;Produce – item ;Producer-consumer. Enter ;End ;End Procedure consumer Begin While true Do Begin ;Producer-consumer. Remove ;Consume-item ;End ;End LOGO فصل هفتم :هماهنگی فرآیندها 8-7هماهنگي در سيستم‌هاي عامل 1-8-7هماهنگي در سوالريس 2 ‏oس_يستم عام_ل س_والريس 2طراحي ش_د ت_ا محاس_بات بي‌درنگ را انجام ده_د ،چن_د بندي باش_د و ا_ز چند پردازنده‌اي پشتيباني كند. ‏oبراي كنترل دس_____تيابي ب_____ه نواح_____ي بحران_____ي ،س_____والريس 2انحص_____ارهاي تط_____بيقي ( ،)adaptive metexمتغيرهاي شرط__ي ،س__مافورها ،قفل‌هاي خواننده – نويس__نده وص__ف ويژ__ه ( )Turn stileرا تدارك مي‌بيند. ‏oسوالريس ،2سمافورها و متغيرهاي شرطي را به روش يكساني پياده‌سازي مي‌كند. LOGO فصل هفتم :هماهنگی فرآیندها 2-8-7همگامي در ويندوز 2000 ويندوز 2000ي_ك هس_ته چندبندي اس_ت ك_ه از كاربردهاي بي‌درن_گ و چندپردازنده ني_ز پشتيبان_ي مي‌كند .وقت_ي هس_ته ويندوز 2000در ي_ك س_يستم ت_ك پردازنده‌اي ب_ه ي_ك منب_ع عموم_ي دس_تيابي دارد، موقتا ً وقفه‌هاي__ي را براي انجام ادا_ره كنندگان وقفه‌اي مي‌فرس__تد ك__ه ممك__ن اس__ت ب__ه آ__ن منب__ع عموم__ي دستيابي داشته باشند. • در س__يستم چن__د پردازنده‌اي ،ويندوز 2000ب__ا اس__تفاده از قفل‌هاي چرخش__ي مناب__ع عموم__ي را محافظ_ت مي‌كند .همانن_د س_والريس ،2هس_ته از قفل‌هاي چرخش_ي براي س_گمنت‌هاي ك_د كوتاه اس_تفاده مي‌كند. • عالوه بر اي_ن ،ب_ه دالي_ل كارآي_ي ،هس_ته تضمي_ن مي‌كن_د ك_ه ت_ا زمان_ي ك_ه بندي قف_ل چرخش_ي را در اختيار دارد ،قبضه نخوا_هد شد. • براي همگام_______ي بنده_______ا در خارج از هس_______ته ،ويندوز 2000از اشياي توزي_______ع كننده ( )Dispatcher Objectاستفاده مي‌كند. LOGO فصل هفتم :هماهنگی فرآیندها 9-7تراكنش‌هاي اتمي انحص_ار متقاب_ل ناحي_ه بحران_ي تضمين‌ مي‌كن_د ك_ه ناحيه‌هاي بحران_ي ب_ه طور اتمي_ك اجرا شون_د يعن_ي اگ_ر دو ناحي_ه بحران_ي ب_ه طور همزمان اجرا شون_د ،حاص_ل آنه_ا مث_ل حالت_ي اس_ت ك_ه آنه_ا ب_ه طور تربيت_ي اجرا مي‌شوند. ‏ اي_ن خاص_يت براي آ_ن اس_ت ك_ه اطمينان حاص_ل كني_م ك_ه ه_ر ناحي_ه بحران_ي ،ي_ك واح_د منطق_ي از كار را ايجاد مي‌كند كه يا كامالً اجرا مي‌شود يا اصالً اجرا نمي‌شود. 1-9-7مدل سيستم تراكن__ش :مجموعه‌ا_ي از دس___تورات (عمليات) ك__ه ي__ك عم___ل منطق__ي را انجام مي‌ده__د تراكن__ش ( )Transactionنام دارد. ‏ نكت_ه مه_م در رابط_ه ب_ا پردازش تراكنش‌ه_ا ،حف_ظ ويژگي‌ اتم_ي ،ص_رفنظر از امكان خراب_ي س_يستم كامپيوتري است. LOGO فصل هفتم :هماهنگی فرآیندها راهكارهاي تصمين اتمي بودن تراكنش: .I .IIحالتي كه چندين تراكنش به طور همزمان مي‌توانند فعال باشند محيطي كه در هر زمان فقط يك تراكنش قابل انجام است اثر تراكنش تصديق شده نمي‌تواند توسط لغو تراكنش ،خنثي شود. نكت__ه :ه__ر تراكن__ش دنباله‌اي از عمليات readو writeك__ه توس__ط عمليات Commitيا abort خاتمه مي‌يابد. ‌ك_ند ك_ه_ ت___را_كنشب___ا موفقيتا_جرا ش__ده_ :Commitا_عالم_ مي ي متوقفش__ده_ ا_ست ‌ك_ند ك_ه_ ا_جرا_يت___را_كنشب___ه_ دل_يلخطاهايمنطق ، :Abortا_عالم_ مي تراكن_ش تص_ديق شده /لغ_و شده :تراكنش_ي ك_ه ب_ه طور كام_ل اجرا شده اس_ت ،تص_ديق شده و گرن_ه لغو شده است. LOGO فصل هفتم :هماهنگی فرآیندها براي تعيي_ن اينك_ه س_يستم چگون_ه باي_د خاص_يت اتم_ي را تضمي_ن كن_د مي‌بايس_ت خواص دس_تگاههاي ذخيره كننده‌ي داده مورد نياز تراكنش‌ه__ا را شناس__ايي كنيم .دس__تگاههاي ذخيره داده‌ه__ا بر حس__ب سرعت نسبي ،ظرفيت و قابليت ترميم خرابي متمايز مي‌شوند. حافظ_ه ناپايدار :اطالعات موجود در حافظ_ه ناپايدار بر اث_ر خراب_ي س_يستم ازبي_ن مي‌روند. (حافظه اصلي و پنهان) حافظ_ه پايدار :اطالعات موجود در حافظ__ه پايدار بر اث__ر خراب__ي س__يستم از بي__ن نمي‌روند. (ديسك‌ها ،نوارها) حافظ_ه ماندگار :حافظه‌اي ك_ه اطالعات آ_ن ا_ز بي_ن نمي‌روند .برا_ي اي_ن منظور باي_د كپي‌هاي متعددي از اطالعات روي ديسك تهيه شود و اطالعات تحت كنترل خاصي بروز شوند. LOGO فصل هفتم :هماهنگی فرآیندها 2-9-7ترميم بر اساس سابقه ي__ك روش حص__ول اطمينان از اتمي‌بودن تراكن__ش اي__ن اس__ت ك__ه ،س__ابقه تغييرات اطالعات توس__ط تراكنش ،در حافظه ماندگار ذخيره شود. متداولتري____ن انجام اي___ن كار اي____ن اس____ت ك____ه س____اختمان داده‌اي ب____ه نام س____ابقه بر روي حافظ___ه تشكيل شود. هر ركورد سابقه ،يك عمليات از نوشتن تراكنش را توصيف مي‌كند و دارا_ي فيلدهاي زي راست: نام تراكنش :نام منحصر به فرد تراكنشي كه عمليات Writeرا انجام داد نام قلم داده :نام منحصر به فرد قلم داده‌اي كه نوشته شده است مقدار قديمي :مقدار قلم داده قبل از عمل نوشتن مقدار جديد :مقدار قلم داده پس از عمل نوشتن LOGO فصل هفتم :هماهنگی فرآیندها 3-9-7نقاط كنترلي وقت__ي س__يستم خراب شود ،باي__د ب__ا اس__تفاده ا_ز س__ابقه ،تراكنش‌هاي__ي را ك__ه نياز ب__ه داده‌هاي قديم__ي و تراكنش‌هايي كه نياز به داده‌هاي جديد دارند ،تعيين كنيم. در واقع براي اينكار بايد كل سابقه را جستجو كنيم .اين روش دو عيب عمده دارد: .I .IIاغل_ب تراكنش‌هاي_ي ك_ه بر اس_اس الگوريت_م م_ا دوباره باي_د اجرا شون_د ،قبالً داده‌هاي_ي را بروز جستجو در سابقه منحصر به هدر رفتن وقت مي‌شود. كرده‌ان_د و س_ابقه مي‌گوي_د ك_ه آنه_ا باي_د اص_الح شوند .گ_ر چ_ه اي_ن عم_ل ضرري ندارد ام_ا زمان ترميم طوالني مي شود. برا_ي كاه_ش اي_ن س_ربارها ،مفهوم نقاط كنترل_ي را مطرح مي‌كنيم .در حي_ن اجرا ،س_يستم س_ابقه را تشكيل مي‌دهد .عالوه بر اين ،سيستم متناوبا ً نقاط كنترلي را نيز اجرا مي‌كند. LOGO فصل هفتم :هماهنگی فرآیندها 4-9-7تراكنش‌هاي اتمي همزمان چون ه_ر تراكن_ش اتم_ي اس_ت ،نتاي_ج اجراي همزمان تراكنش‌ه_ا باي_د معادل حالت_ي باش_د ك_ه آنه_ا ب_ه ترتي_ب دلخواه_ي ب_ه طور س_لاير اجرا مي‌شون_د ،اي_ن خاص_يت ك_ه قابلي_ت س_لاير‌سازي ( )Serializationنام دارد ،ب_ه اين ترتيب بدست مي‌آيد كه هر تراكنش در يك ناحيه بحراني اجرا شود. يعن_ي تمام تراكنش‌ه_ا در ي_ك س_مافور Mutexمشترك هس_تند ك_ه مقدار اولي_ه آ_ن 1اس_ت ،وقت_ي تراكنش_ي شروع ب_ه اجرا مي‌كن_د ،اولي_ن كارش اجراي عمليات ) wait (Matexاس_ت .پ_س از اينك_ه تراكن_ش تص_ديق يا لغو شد ،عمليات ) Signal (Mutexرا اجرا مي‌كند. 1-4-9-7قابليت سلاير‌سازي س_يستمي ب_ا اقالم داده‌اي Aو Bرا در نظ_ر بگيري_د ك_ه ه_ر دو توس_ط تراكنش‌هاي T0و T1خوانده و نوشت_ه مي‌شوند .فرض كني_د اي_ن تراكنش‌ه_ا ب_ه طور دائم_ي اجرا مي‌شوند .ب_ه طوريك_ه ابتدا T0و س_پس T1اجرا مي‌شوند اين ترتيب اجرا زمانبندي نام دارد. LOGO فصل هفتم :هماهنگی فرآیندها شكل زير زمانبندي سلاير كه در آن T0و سپس T1اجرا مي‌شود نشان مي‌دهد زمانبندي س_لاير :زمانبندي_ي ك_ه در آ_ن ،ه_ر تراكن_ش ب_ه طور اتم_ي اجرا مي‌شود .ه_ر زمانبندي س_لاير متشك_ل از دنباله‌اي از دس_تورات از تراكنش‌هاي مختل_ف اس_ت ك_ه دس_تورات مربوط ب_ه ي_ك تراكنش ،با هم در آن زمانبندي ظاهر مي‌شود. ‏ بنابراين براي يك مجموعه nتراكنشي ،تعدا_د زمانبندي سلاير معتبر nاست. ‏T0 )Read (A )Write (A )Reud (B )Write (B ‏T1 1 1 1 1 )Read (A )Write (A )Reud (B )Write (B LOGO فصل هفتم :هماهنگی فرآیندها 2-4-9-7پروتكل قفل كردن ي_ك روش براي حص_ول اطمينان از قابلي_ت س_لاير‌سازي اي_ن اس_ت ك_ه ب_ه ه_ر قل_م داده ي_ك قف_ل نس_بت داده شود. در نتيج_ه نياز ب_ه پروتك_ل قفل‌كردن اس_ت ت_ا شيوه قف_ل كردن و باز كردن قف_ل را مشخ_ص مي‌كند .ي_ك قلم داده به شكل‌هاي گوناگوني مي‌تواند قفل شود كه در اينجا 2حالت اشاره شده: • حال_ت اشتراك :اگ_ر تراكن_ش Tiداراي قف_ل حال_ت اشتراك بروي قل_م داده Qباش_د ك_ه ب_ا Sنشان داده شود ،آنگاه Tiمي‌توا_ند Qرا بخواند ولي نمي‌تواند بنويسيد. • حال_ت انحص_اري :اگ_ر تراكن_ش Tiداراي قف_ل حال_ت انحص_اري بروي قل_م داده Qباش_د ك_ه با X نشان داده مي‌شود ،آنگاه Tiمي‌تواند Qرا بخواند و بنويسيد. LOGO فصل هفتم :هماهنگی فرآیندها ي_ك پروتكل ك_ه قابلي_ت سريالسازي را تضمي_ن مي‌كن_د پروتكل قف_ل دو مرحله‌اي اس_ت .اين پروتك_ل مستلزم اين است كه هر تراكنش درخواست قفل كردن و بازكردن قفل را در دو مرحله انجام دهد: مرحله رشد :تراكنش ممكن است قفلي را ايجاد كند اما ممكن است قفلي را_ باز نكند. مرحله كوچك شدن :تراكنش ممكن اس_ت قفل‌هايي را باز كند ولي قفل‌هاي جديدي را ايجاد نمي‌كند. 3-4-9-7پروتكل‌هاي زماني روش ديگ_ر براي تضمي_ن ترتي_ب قابلي_ت س_ريالسازي (عالوه بر اي_ن حال_ت ك_ه ،در زمان اجرا ب_ا اولي_ن قفل_ي ك_ه ه_ر دو تراكن_ش درخوا_س_ت مي‌كنن_د و شام_ل حالت‌هاي ناس_ازگاري‌اند ،تعيي_ن مي‌شود) ،اي_ن است كه ،از قبل ترتيبي بين تراكنش‌ها انتخاب شود. ‏ متداولترين انجام اين كار استفاده از الگوي زماني است. LOGO فصل هفتم :هماهنگی فرآیندها دو روش ساده براي پياده‌سازي اين الگو وجود دارد: .I اس_تفاده از س_اعت س_يستم ب_ه عنوان مه_ر زماني .يعن_ي مهرزمان_ي ي_ك تراكن_ش برابر ب_ا مقدار ساعت سيستم در زمان ورود تراكنش به سيستم است. .II اس_تفاده از شمارنده منطق_ي ب_ه عنوان مه_ر زماني .يعن_ي مهرزمان_ي ي_ك تراكن_ش برابر ب_ا مقدار شمارنده در هنگام ورود تراكنش به سيستم است. مهرهاي زماني تراكنش‌ها ،ترتيب قابليت سريالسازي را مشخص مي‌كند.