همگام‌سازی (علوم رایانه)

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

انشعاب و الحاق(fork-join): زمانی که یک کار به یک نقطه انشعاب می‌رسد به ریز کارهای متعددی تقسیم می‌شود که بعداً توسط تسک های (به انگلیسی: task) متعددی سرویس دهی می‌شوند. بعد از انجام سرویس دهی، هر ریز کار منتظر می‌ماند تا پردازش تمام ریز کارهای دیگر انجام شود. سپس ریز کارها مجدداً به هم ملحق می‌شوند و از سیستم خارج می‌گردند؛ بنابراین برنامه‌های موازی نیازمند همگام سازی هستند، زیرا تمام فرایند‌های موازی منتظر چندین فرایندٔ دیگر می‌مانند تا اجرا شوند.

تولیدکننده-مصرف کننده: در یک رابطهٔ تولیدکننده-مصرف کننده، فرایند مصرف‌کننده وابسته به فرایند تولیدکننده است تا زمانی که داده مورد نیاز تولید شود.

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

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

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

علاوه بر انحصار متقابل، همگام سازی با موارد زیر نیز سر و کار دارد:

• بن‌بست: زمانی رخ می‌دهد که فرایند‌های متعددی در انتظار یک منبع مشترک (بخش بحرانی) قرار می‌گیرند و این منبع مشترک توسط فرایندٔ دیگری در اختیار قرار گرفته‌است. در این حالت فرایند‌ها مجبورند تا منتظر بمانند و نمی‌توانند کاری انجام دهند.

• قحطی: زمانی رخ می‌دهد که یک فرایند منتظر است تا وارد بخش بحرانی شود اما سایر فرایند‌ها بخش بحرانی را در انحصار می‌گیرند و این فرایند مجبور است تا مدت نامتناهی منتظر بماند.

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

• انتظار فعال: زمانی رخ می‌دهد که یک فرایند به‌طور مکرر چک می‌کند که آیا به بخش بحرانی دسترسی دارد یا خیر و این چک کردن‌های مکرر باعث ربودن زمان پردازش از سایر فرایند‌ها می‌شود.

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

بعد از وجود آمدن یک آزمایش محک جدید با نام HPCG که برای رتبه‌بندی ۵۰۰ ابر رایانه برتر می‌باشد، این مسئله توجه زیادی را به خود جلب کرده‌است.

در زیر برخی مسئله‌های مرسوم از همگام سازی ذکر شده‌است:
مسئله تولیدکننده- مصرف‌کننده: یا همان مسئله بافر محدود
مسئله خواننده نویسنده
مسئله میز غذاخوری فیلسوفها
این مسئله‌ها برای آزمودن تقریباً هر روش همگام سازی پیشنهاد شدهٔ جدید استفاده می‌شوند.

بسیاری از سیستم‌ها قابلیت پشتیبانی سخت‌افزاری برای کد ناحیه بحرانی دارند.

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

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

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

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

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

قفل چرخشی (spinlock)

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

سدها

پیاده‌سازی سدها(barrier) آسان است و پاسخ دهی خوبی را فراهم می‌آورد. آن‌ها بر پایهٔ مفهوم بکارگیری چرخه‌های انتظار برای فراهم آوردن همگام‌سازی بنا نهاده شده‌اند. سه ریسمان را در نظر بگیرید که به‌طور همزمان در حال اجرا هستند و از سد ۱ شروع می‌شوند. بعد از زمان t، ریسمان ۱ به سد ۲ می‌رسد، اما باید هنوز منتظر بماند تا ریسمان ۲ و ۳ به سد ۲ برسند زیرا دادهٔ درست را در اختیار ندارد. هنگامی که تمام ریسمان‌ها به سد ۲ می‌رسند، همه آنها دوباره شروع می‌شوند. بعد از زمان t، ریسمان ۱ به سد ۳ می‌رسد اما باید هنوز منتظر ریسمان ۲ و ۳ و مجدداً داده درست بماند.

بنابراین در همگام‌سازی سدی برای چندین ریسمان، همیشه تعدادی ریسمان وجود خواهند داشت که پایان می‌یابند اما باید منتظر سایر ریسمان‌ها بمانند، شبیه مثال بالا که در آن ریسمان ۱ باید مکرراً منتظر ریسمان ۳ و ۲ بماند. این وضعیت منجر به افت شدید در عملکرد فرایند می‌شود.

تابع انتظار همگام سازی سدی برای ریسمان iام را می‌توان به شکل زیر نشان داد:

در تابع بالا Wbarrier زمان انتظار برای یک ریسمان است. Tbarrier تعداد ریسمان‌هایی است که رسیده‌اند و Rthread میزان رسیدن ریسمان‌ها است.

تجربه نشان می‌دهد که ۳۴ درصد از کل زمان اجرا صرف انتظار برای سایر ریسمان‌های کندتر می‌شود.

سمافور

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

مشارکت‌کنندگان ویکی‌پدیا. «Synchronization (computer science)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۹ آوریل ۲۰۲۱.

1. ↑ Gramoli, V. (2015). More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms (PDF). Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. pp. 1–10.
2. ↑ Shengxin, Zhu and Tongxiang Gu and Xingping Liu (2014). "Minimizing synchronizations in sparse iterative solvers for distributed supercomputers". Computers & Mathematics with Applications. 67 (1): 199–209. doi:10.1016/j.camwa.2013.11.008.
3. ↑ "HPCG Benchmark".
4. ↑ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (July 11, 2008). "Chapter 6: Process Synchronization". Operating System Concepts (Eighth ed.). John Wiley & Sons. ISBN 978-0-470-12872-5.
5. ↑ Hennessy, John L.; Patterson, David A. (September 30, 2011). "Chapter 5: Thread-Level Parallelism". Computer Architecture: A Quantitative Approach (Fifth ed.). Morgan Kaufmann. ISBN 978-0-123-83872-8.
6. ↑ "Synchronization Primitives in .NET framework". MSDN, The Microsoft Developer Network. Microsoft. Retrieved 23 November 2014.
7. ↑ Massa, Anthony (2003). Embedded Software Development with ECos. Pearson Education Inc. ISBN 0-13-035473-2.
8. ↑ Meng, Chen, Pan, Yao, Wu, Jinglei, Tianzhou, Ping, Jun. Minghui (2014). "A speculative mechanism for barrier sychronization". 2014 IEEE International Conference on High Performance Computing and Communications (HPCC), 2014 IEEE 6th International Symposium on Cyberspace Safety and Security (CSS) and 2014 IEEE 11th International Conference on Embedded Software and Systems (ICESS).
9. ↑ Rahman, Mohammed Mahmudur (2012). "Process synchronization in multiprocessor and multi-core processor". 2012 International Conference on Informatics, Electronics & Vision (ICIEV). pp. 554–559. doi:10.1109/ICIEV.2012.6317471. ISBN 978-1-4673-1154-0.
10. ↑ Li, Yao, Qing, Carolyn (2003). Real-Time Concepts for Embedded Systems. CMP Books. ISBN 978-1578201242.