موضوع مقاله: مانیتور (همگام‌سازی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مانیتور (همگام‌سازی) | مقدمه: در برنامه‌نویسی همروند (یا همان برنامه‌نویسی موازی)، مانیتور یک ساختار همگام سازی است که به ریسمان‌ها این امکان را می‌دهد که هم، انحصار متقابل داشته باشند و هم، بتوانند برای یک وضعیت خاص منتظر بمانند (مسدود شوند) تا وضعیت غلط شود. | ## بخش 1: مانیتور (همگام‌سازی) | مانیتورها همچنین دارای یک مکانیسم هستند که به ریسمان‌های دیگر، از طریق سیگنال می‌فهمانند که شرایط آن‌ها برآورده شده‌است. مانیتورها برای ریسمان‌ها مکانیسمی را فراهم می‌کنند، تا به‌طور موقت، و با هدف منتظر ماندن برای برآورده شدن شرایط خاص، دسترسی انحصاری را رها کنند، و سپس دسترسی انحصاری را مجدداً به‌دست آورند و کار خود را از سر گیرند.یک تعریف دیگر برای مانیتور عبارت است از یک کلاس، شئ، یا ماژول امنیت-ریسمانی، که دور یک ریسمان می‌پیچد، تا به‌طور ایمن، به بیش از یک ریسمان اجازه دسترسی به یک متد یا متغیر را بدهد. مشخصهٔ تعریف کننده یک مانیتور این است که متدهای آن با انحصار متقابل اجرا می‌شوند: در هر لحظه، حداکثر یک ریسمان می‌تواند هر‌کدام از متدهای آن‌را اجرا کند. همچنین، با فراهم کردن یک یا بیش از یک متغیر شرطی، می‌تواند این قابلیت را به ریسمان ها بدهد تا، منتظر یک شرایط خاص بمانند (و بنابراین، از تعریف بالای یک مانیتور استفاده می‌شود). در ادامهٔ این مقاله، این مفهوم از «مانیتور» را، یک «ماژول/ کلاس/ شئ امنیت-ریسمانی» می‌نامیم. اشیاء امنیت-ریسمانی، به این منظور پیاده‌سازی می‌شوند که مطمئن شویم که در هر زمان حداکثر، یک ریسمان می‌تواند شئ مورد نظر را اشغال کند. قفل، که در ابتدا باز است، در زمان شروع هر متد عمومی بسته می‌شود و در زمان هر بازگشت از متد عمومی باز می‌شود. یک ریسمان، پس از فراخوانی یکی از متدها، و قبل از شروع اجرای متد خودش، باید منتظر بماند تا زمانیکه هیچ ریسمان دیگری، هیچ‌یک از متدهای شئ امنیت-ریسمانی را اجرا نکند. توجه داشته باشید که بدون این انحصار متقابل در مثال بالا، دو ریسمان می‌توانند موجب شوند تا، بدون هیچ دلیل خاصی، پولی از بین برود یا به دست آید. برای مثال، دو ریسمان، هرکدام با برداشت مقدار ۱۰۰۰ واحد از حساب می‌توانند هر دو، مقدار true را برگردانند، و در عین حال، موجب شوند تا مقدار باقی ماندهٔ حساب فقط به اندازه هزار واحد کاهش پیدا کند؛ به شکل زیر: ابتدا هر دو ریسمان مقدار کنونی حساب را دریافت می‌کنند و متوجه می‌شوند که بیشتر از هزار واحد است و هزار واحد را از آن برمی‌دارند، سپس هر دو ریسمان مقدار مانده حساب را ذخیره می‌کنند و بازمی‌گردند.کلاس «مانیتور» که در مثال بالا به شکل شکلات نحوی(syntactic sugar) نوشته شده‌است، در واقع کد زیر را با پیچیدن هر کدام از اجراهای تابع در میوتکس‌ها، پیاده‌سازی می‌کند. ممکن است لازم باشد تا ریسمان‌هایی که یک عملیات را اجرا می‌کنند، منتظر بمانند، تا برخی شرایط P صحیح(true) شود. راه‌حل های دیگری وجود دارند، نظیر: داشتن یک حلقه که قفل مانیتور را باز می‌کند، برای مدت زمان خاصی منتظر می‌ماند، مانیتور را قفل میکند و شرایط P را چک می‌کند. مشخص کردن مقدار زمان لازم برای انتظار، دشوار است؛ اگر خیلی کم باشد، پروسه‌ی مذکور بیشتر وقت CPU را می‌گیرد و اگر خیلی زیاد باشد، آشکارا بدون پاسخ خواهد بود. آنچه لازم است، شیوه‌ای است که در آن، وقتی‌که شرایط P صحیح شد (یا بتواند صحیح شود)، از طریق یک سیگنال، ریسمان را مطلع کند. | ## بخش 2: مانیتور (همگام‌سازی) | مطالعه موردی: مشکل تولید کننده مصرف کننده محدود کلاسیک یک مشکل همروندی کلاسیک، مسئله ی تولید کننده-مصرف کننده ی محدود شده است، که در آن یک صف یا بافر حلقوی از کارها وجود دارد که دارای یک گنجایش حداکثر است و در آن یک یا بیش از یک ریسمان نقش تولید کننده را ایفا می کند، یعنی کارهایی را به صف اضافه می‌کند و یک یا بیش از یک ریسمان نقش مصرف کننده را بازی می کند، یعنی کارهایی را از صف خارج می کند. فرض بر این است که خود صف امنیت-ریسمان ای ندارد و می تواند خالی، پر، یا چیزی بین خالی و پر باشد. زمانیکه صف از کارها پر می شود، آنگاه نیاز است تا ریسمان های تولید کننده مسدود شوند تا زمانیکه با خالی کردن کارها از صف توسط مصرف کننده ها، فضا خالی شود. از سوی دیگر، زمانیکه صف خالی است، لازم است تا ریسمان های مصرف کننده مسدود شوند، تا زمانیکه ریسمان های تولیدکننده آیتمی را به صف اضافه کنند تا در اختیار مصرف کننده قرار بگیرد. از آنجاییکه صف، یک شیء همروند مشترک بین ریسمان ها است، دسترسی به آن باید به صورت اتمیک باشد، زیرا در زمان دسترسی به آن (که هرگز نباید بین ریسمان ها نمایان شود)، می تواند در وضعیت ناسازگار قرار بگیرد. بنابراین، هر کدی که به صف دسترسی پیدا می کند، یک ناحیه بحرانی را تشکیل می دهد که باید به طریق انحصار متقابل همگام سازی شود. اگر تعویض های زمینه ای(context switch) دلخواه بین ریسمان هایی که در یک پردازنده قرار دارند، یا بین ریسمان های موجود در چندین پردازنده که به طور همزمان اجرا می شوند، بتوانند در لابلای کد و دستورالعمل های پردازنده در نواحی بحرانی کد، که به صف دسترسی پیدا می کنند، قرار گیرند، آنگاه خطر نمایان شدن وضعیت ناسازگار یا ایجاد شرایط رقابتی وجود دارد. } } این کد دارای یک مشکل جدی است و آن این است که دسترسی ها به صف ممکن است دچار وقفه شوند و سایر دسترسی های ریسمان ها به صف، در ما بین آن قرار گیرد. اگر این اجازه بدهیم که ریسمان‌های تولیدکننده/مصرف‌کننده در حین فراخوانی ها به enqueue/dequeue در لابلای هم قرار گیرند، آنگاه وضعیت ناسازگار درصف می توانند نمایان شود، که منجر به شرایط رقابتی می شود. علاوه بر این، اگر یک مصرف کننده در زمان بین خروج مصرف کننده دیگر از انتظار فعال و فراخوان dequeue، صف را تهی کند، آنگاه مصرف‌کننده ی دوم تلاش خواهد کرد تا یک صف خالی را، خالی کند، که منجر به یک خطا می شود. به همین شکل، اگر یک تولید کننده در زمان بین خروج تولیدکننده دیگر از انتظار فعال و فراخوانی enqueue، صف را پر کند، آنگاه مصرف‌کننده دوم تلاش خواهد کرد تا به صفی که پر است اضافه کند، که منجر به یک خطا می‌شود. انتظار چرخشی یک روش ناشیانه برای دستیابی به همگام سازی، که در بالا اشاره ی گذرا به آن شد، استفاده از انتظار چرخشی است که در آن از یک میوتکس برای محافظت از نواحی بحرانی کد استفاده می شود و همچنین از انتظار فعال نیز استفاده می شود و قفل، ما بین چک کردن های انتظار فعال، در اختیار قرار می گیرد و آزاد می شود. حتی اگر صف، خالی باشد و ریسمان های تولید کننده به مدت طولانی چیزی برای اضافه کردن نداشته باشند، باز هم ریسمان های مصرف کننده همیشه، و به طور غیرضروری در انتظار فعال هستند. به همین شکل، حتی اگر مصرف کننده ها برای مدت طولانی، روی پردازش کارهای کنونی خود مسدود شوند و صف پر باشد، باز هم تولیدکننده ها همیشه در انتظار فعال هستند. | ## بخش 3: مانیتور (همگام‌سازی) | در اینجا، نیاز به روشی داریم که تا زمانیکه صف غیر پر شود، ریسمان های تولید کننده مسدود شوند، و ریسمان های مصرف کننده را تا زمانیکه صف غیر خالی شود، مسدود کند. از نظر مفهومی، متغیر شرطی، صفی از ریسمان ها است همراه با یک میوتکس که ممکن است یک ریسمان، روی آن برای تحقق یک شرط منتظر بماند. زمانیکه یک ریسمان منتظر یک متغیر شرطی است، در واقع، آن ریسمان مانیتور را اشغال نمی کند و بنابراین ریسمان های دیگر می توانند وارد مانیتور شوند تا وضعیت مانیتور را تغییر دهند. در اکثر انواع مانیتور ها این ریسمان های دیگر ممکن است با استفاده از سیگنال به متغیر شرطی c نشان دهند که بررسی صحت(assertion, Pc)، در وضعیت کنونی صحیح است. بنابراین سه عملیات اصلی روی متغیرهای شرطی وجود دارد: wait c, m : که در آن c یک متغیر شرطی است و m یک میوتکس (قفل) است که به مانیتور مربوط است. این عملیات توسط یک ریسمان فراخوانی می شود که لازم است منتظر بماند تا زمانیکه بررسی سقم وصحت (assertion, Pc) صحیح شود و سپس به کارش ادامه دهد. به صورت اتمیک: الف) میوتکس m را آزاد کن، ب) این ریسمان را از صف اجرا به صف انتظار c (یا همان صف خواب) ریسمان ها منتقل کن و، ج) این ریسمان را خواب کن. هنگامی که این ریسمان بعداً آگاه سازی/ سیگنال دهی شد و از سر گرفته شد، آنگاه، به طور خودکار میوتکس m را مجدداً به دست آور. مرحله ۱-الف و ۱-ب می توانند به هر ترتیبی رخ دهند، و مرحله ۱-ج معمولاً بعد از آن ها رخ می دهد. هنگامی که ریسمان مذکور خوابیده است و در صف انتظار c قرار دارد، شمارنده برنامه بعدی که قرار است اجرا شود، در مرحله ۲، یعنی در وسط تابع ساب روتین انتظار است، بنابراین ریسمان مذکور می خوابد و بعداً در میانه عملیات انتظار بیدار می شود. اگر این ها به صورت اتمیک نباشند، یک مد شکست می تواند رخ دهد که از بین رفتن بیدار‌کردن (به انگلیسی: wakeup miss) نام دارد، در این نوع مد شکست، ریسمان مذکور می‌تواند، در حالی که میوتکس را آزاد کرده است، در صف خواب c باشد، اما یک تغییر ریسمان اجباری، قبل از اینکه ریسمان مذکور به خواب رود رخ دهد و ریسمان دیگری عملیات سیگنال دهی/آگاه‌سازی را روی c فراخوانی کند و باعث شود که ریسمان اول از صف c خارج گردد (عقب نشینی کند). به محض اینکه ریسمان اول (مورد بحث) به حالت اول برگردد، شمارنده ی برنامه آن در مرحله ی ۱-ج خواهد بود، و به خواب خواهد رفت و مجدداً قابل بیدار شدن نیست که این قانون را نقض می کند که، باید زمانی که به خواب رفت در صف خواب c قرار داشته باشد. | ## جمع‌بندی | سایر شرایط رقابتی بستگی به ترتیب مراحل ۱-الف و ۱-ب و همچنین بستگی به این دارد که در کجا تعویض زمینه رخ می دهد.