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

از ویکی‌پدیا، دانشنامهٔ آزاد

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

نیاز به همگام سازی[ویرایش]

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

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

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

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

همگام سازی ریسه یا پروسه[ویرایش]

شکل ۱: سه پروسه می‌خواهند به یک منبع مشترک(ناحیه ی بحرانی)بطور همزمان دسترسی پیدا کنند.

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

شکل ۲: بر اساس برخی تکنیک‌های همگام‌سازی یک پروسه به یک منبع مشترک در صورت وجود دسترسی پیدا می‌کند .

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

به حداقل رساندن همگام‌سازی[ویرایش]

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

مثالهای مرسوم از همگام سازی[ویرایش]

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

همگام سازی سخت‌افزار[ویرایش]

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

رویکردهای همگام سازی در زبان‌های برنامه‌نویسی[ویرایش]

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

پیاده‌سازی همگام سازی[ویرایش]

اسپین لاک (به انگلیسی: spinlock)[ویرایش]

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

سدها[ویرایش]

پیاده‌سازی سدها آسان است و پاسخ دهی خوبی را فراهم می‌آورد. آن‌ها بر پایهٔ مفهوم بکارگیری چرخه‌های انتظار برای فراهم آوردن همگام‌سازی بنا نهاده شده‌اند. سه ریسه را در نظر بگیرید که به‌طور همزمان در حال اجرا هستند و از سد ۱ شروع می‌شوند. بعد از زمان t، ریسه ۱ به سد ۲ می‌رسد، اما باید هنوز منتظر بماند تا ریسه ۲ و ۳ به سد ۲ برسند زیرا دادهٔ درست را در اختیار ندارد. هنگامی که تمام ریسه‌ها به سد ۲ می‌رسند، همه آنها دوباره شروع می‌شوند. بعد از زمان t، ریسه ۱ به سد ۳ می‌رسد اما باید هنوز منتظر ریسه ۲ و ۳ و مجدداً داده درست بماند.
بنابراین در همگام‌سازی سدی برای چندین ریسه، همیشه تعدادی ریسه وجود خواهند داشت که پایان می‌یابند اما باید منتظر سایر ریسه‌ها بمانند، شبیه مثال بالا که در آن ریسهٔ ۱ باید مکرراً منتظر ریسهٔ ۳ و ۲ بماند. این وضعیت منجر به افت شدید در عملکرد پروسه می‌شود.
تابع انتظار همگام سازی سدی برای ریسهٔ iام را می‌توان به شکل زیر نشان داد:
(Wbarrier)i = f ((Tbarrier)i, (Rthread)i)
در تابع بالا Wbarrier زمان انتظار برای یک ریسه است. Tbarrier تعداد ریسه‌هایی است که رسیده‌اند و Rthread میزان رسیدن ریسه‌ها است.
تجربه نشان می‌دهد که ۳۴ درصد از کل زمان اجرا صرف انتظار برای سایر ریسه‌های کندتر می‌شود.

سمافور[ویرایش]

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

منابع[ویرایش]

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