بخش بحرانی

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

نیاز به نواحی بحرانی

کدهای و پروسه های مختلف ممکن است شامل متغیرهای یکسان یا سایر منابعی باشند که قرار است خوانده یا نوشته شوند اما نتایج آن ها بستگی به ترتیب رخ دادن عمل ها دارد. برای مثال، اگر متغیر x قرار باشد که توسط پروسه‌ی A خوانده شود و پروسه B قرار باشد که در متغیر x به طور همزمان بنویسد، آنگاه پروسه ی A ممکن است مقدار قدیمی یا مقدار جدیدی از x به خود بگیرد.

Process A:

// Process A
.
.
b = x + 5;               // instruction executes at time = Tx
.

Process B:

// Process B
.
.
x = 3 + z;               // instruction executes at time = Tx
.

شکل ۱: گراف جریان که نشان دهنده ی لزوم وجود ناحیه ی بحرانی است

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

پیاده سازی نواحی بحرانی

پیاده سازی نواحی بحرانی در سیستم عامل های مختلف متفاوت است.

شکل ۲: قفل ها و نواحی بحرانی در ریسه های متعدد

معمولاً یک ناحیه بحرانی پس از یک زمان مشخص پایان می یابد^[۲] و یک ریسه، task یا پروسه مجبور است تا مدت زمان ثابتی را منتظر بماند تا وارد آن شود (انتظار محدود شده). برای اطمینان از استفاده ی انحصاری از نواحی بحرانی، برخی مکانیسم‌های همگام‌سازی در ورودی و خروجی برنامه مورد نیاز است. ناحیه بحرانی قطعه ای از برنامه است که نیاز به انحصار متقابل برای دسترسی به آن است. چنانکه در شکل ۲ نشان داده شده است،^[۳] در انحصار متقابل (mutex)، یک ریسه زمانیکه نیاز به دسترسی به منبع مشترک دارد، با استفاده از تکنیک های قفل کردن، ناحیه ی بحرانی را قفل می کند و سایر ریسه ها مجبورند تا منتظر بمانند تا نوبت آنها برای ورود به این ناحیه برسد. این فرایند زمانی که دو یا بیش از دو ریسه فضای حافظه مشابهی را در اشتراک دارند و می خواهند به یک منبع مشترک دسترسی پیدا کنند، مانع از تقابل می شود.

ساده ترین روش برای پیشگیری از هرگونه تغییر در کنترل پردازنده در داخل ناحیه بحرانی، پیاده سازی سمافور است. در سیستم های تک پردازنده ای، این هدف را می توان با غیر فعال کردن وقفه ها در هنگام ورود به ناحیه بحرانی ، اجتناب از فراخوانی هایی از سیستم که می تواند موجب تعویض زمینه(به انگلیسی: context switch) در حین حضور در داخل ناحیه شود و بازگرداندن وقفه به وضعیت قبل در هنگام خروج، عملی کرد. در این روش پیاده سازی، هر ریسه در حال اجرا که وارد هر ناحیه بحرانی در هر جایی از سیستم می شود مانع از این می‌شود که هر ریسه ی دیگر، از جمله یک وقفه، اجازه دریافت زمان پردازش در CPU پیدا کند. و همچنین به هیچ ریسه ی دیگری اجازه ورود به هیچ ناحیه بحرانی دیگری نمیدهد. این ممانعت تا زمانی ادامه پیدا می کند که ریسه ی اولیه از ناحیه بحرانی خودش خارج شود.

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

کاربردهای نواحی بحرانی

نواحی بحرانی در سطح کرنل

به طور معمول نواحی بحرانی مانع از مهاجرت ریسه ها و پروسه ها بین پردازنده ها و نیز مانع از وقفه ی اجباری پروسه ها و ریسه ها توسط وقفه ها(به انگلیسی: interrupt) و پروسه ها و ریسه های دیگر می شود.

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

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

به طور مشابه، اگر یک وقفه در ناحیه بحرانی رخ دهد، اطلاعات وقفه برای پردازش در آینده ثبت می‌شود و اجرا، به پروسه یا ریسه در ناحیه بحرانی برمی گردد. زمانی که پروسه یا ریسه از ناحیه بحرانی خارج شود و در برخی موارد، کوانتوم زماندهی شده کامل شود، وقفه ی در حال انتظار اجرا خواهد شد. مفهوم زماندهی کوانتوم مربوط به روش زمانبندی round-robin و خط مشی های زماندهی مشابه می شود.^[۴]

از آنجایی که نواحی بحرانی ممکن است فقط در پردازنده‌ای که در آن وارد شده اند اجرا شوند، بنابراین همگام‌سازی فقط در داخل پردازنده ی اجرا کننده لازم است. این کار باعث می شود تا ورود به و خروج از نواحی بحرانی بدون هزینه انجام شود. هیچگونه همگام سازی بین پردازنده ای لازم نیست. فقط همگام سازی جریان دستورالعمل لازم است.n^[۵] اکثر پردازنده ها با ایجاد وقفه در وضعیت اجرای کنونی، میزان لازم همگام سازی را به سادگی فراهم می کنند. این امر این امکان را فراهم می آورد تا نواحی بحرانی در اکثر موارد چیزی بیش از تعداد نواحی بحرانی مورد دخول به ازای پردازنده نباشد.

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

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

نواحی بحرانی در ساختمان های داده

در برنامه نویسی موازی، یک کد به ریسه هایی تقسیم می‌شود. متغیرهای دارای تقابل نوشتن-خواندن در بین این ریسه ها تقسیم می‌شوند و هر ریسه یک کپی از آن ها دارد. ساختمان های داده نظیر: لیست های پیوندی، درخت ها، جدول های درهم سازی و ... دارای متغیرهای داده ای هستند که به هم پیوند خورده اند و نمی توان آن ها را بین ریسه ها تقسیم کرد و از این رو، پیاده سازی موازی گرایی بسیار دشوار خواهد شد.^[۶] برای بهبود کارایی پیاده سازی ساختمان‌های داده، باید عملیات متعددی نظیر: قرار دادن، پاک کردن، و جستجو کردن به صورت موازی اجرا شوند. زمانیکه این عملیات انجام می شوند، ممکن است سناریوهایی به وجود آید که در آن یک عنصر به صورت همزمان توسط یک ریسه جستجو شود و توسط ریسه ای دیگر پاک شود. در چنین مواردی، خروجی ممکن است نادرست باشد. ریسه ای که عنصر را جستجو می کند ممکن است آن را پیدا کند، در حالیکه ریسه ی دیگر ممکن است، درست بعد از این زمان، آن را پاک کند. این سناریوها می ‌توانند باعث مشکل در اجرای برنامه، از طریق فراهم کردن داده غلط شوند. یک راه حل برای پیشگیری از این وضعیت این است که تمام ساختمان داده را داخل ناحیه بحرانی نگه داریم، به گونه ای که فقط یک عملیات در هر لحظه انجام شود. راه حل دیگر این است که، گره مورد استفاده را در ناحیه ی بحرانی قفل کنیم، به گونه ای که عملیات دیگر از همان گره استفاده نکنند. بنابراین، با استفاده از ناحیه بحرانی، خروجی های مورد انتظار فراهم می‌شوند.

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Critical section». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۰ مارس ۲۰۲۱.

↑ Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. p. 9. ISBN 978-3642320279.
↑ Jones, M. Tim (2008). GNU/Linux Application Programming (2nd ed.). [Hingham, Mass.]. Charles River Media. pp. 264. ISBN 978-1-58450-568-6.
↑ Chen, Stenstrom, Guancheng, Per (Nov 10–16, 2012). "Critical Lock Analysis: Diagnosing Critical Section Bottlenecks in Multithreaded Applications". High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference: 1–11. doi:10.1109/sc.2012.40. ISBN 978-1-4673-0805-2.
↑ "RESEARCH PAPER ON SOFTWARE SOLUTION OF CRITICAL SECTION PROBLEM". International Journal of Advance Technology & Engineering Research (IJATER). 1. November 2011.
↑ Dubois, Scheurich, Michel, Christoph (1988). "Synchronization, Coherence, and Event Ordering in Multiprocessors". Survey and Tutorial Series. 21 (2): 9–21. doi:10.1109/2.15.
↑ Solihin, Yan (17 November 2015). Fundamentals of Parallel Multicore Architecture. ISBN 9781482211184.

[1] Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. p. 9. ISBN 978-3642320279.

[:0-2] Jones, M. Tim (2008). GNU/Linux Application Programming (2nd ed.). [Hingham, Mass.]. Charles River Media. pp. 264. ISBN 978-1-58450-568-6.

[3] Chen, Stenstrom, Guancheng, Per (Nov 10–16, 2012). "Critical Lock Analysis: Diagnosing Critical Section Bottlenecks in Multithreaded Applications". High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference: 1–11. doi:10.1109/sc.2012.40. ISBN 978-1-4673-0805-2.

[4] "RESEARCH PAPER ON SOFTWARE SOLUTION OF CRITICAL SECTION PROBLEM". International Journal of Advance Technology & Engineering Research (IJATER). 1. November 2011.

[5] Dubois, Scheurich, Michel, Christoph (1988). "Synchronization, Coherence, and Event Ordering in Multiprocessors". Survey and Tutorial Series. 21 (2): 9–21. doi:10.1109/2.15.

[:1-6] Solihin, Yan (17 November 2015). Fundamentals of Parallel Multicore Architecture. ISBN 9781482211184.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]