فصل ۱ — مقدمه‌ای بر همزمانی

Concurrency کلمهٔ جالبی است چون برای افراد مختلف در حوزهٔ ما معانی متفاوت دارد. علاوه بر «concurrency»، شاید کلماتی مثل «asynchronous»، «parallel» یا «threaded» را شنیده باشید. بعضی این کلمات را مترادف می‌گیرند و بعضی دقیقاً بین هر کدام تمایز قائل می‌شوند. اگر قرار است یک کتاب کامل دربارهٔ concurrency صحبت کنیم، بهتر است ابتدا کمی دربارهٔ منظورمان از «concurrency» بحث کنیم.

در فصل ۲ فلسفهٔ concurrency را بررسی می‌کنیم، اما فعلاً تعریفی عملی بپذیریم که پایهٔ درک ما باشد.

وقتی بیشتر مردم از «concurrent» استفاده می‌کنند، معمولاً به فرایندی اشاره دارند که همزمان با یک یا چند فرایند دیگر رخ می‌دهد. معمولاً این هم implied است که همهٔ این فرایندها تقریباً هم‌زمان پیشرفت می‌کنند. تحت این تعریف، راه ساده برای تصور آن انسان‌ها هستند. شما هم‌اکنون این جمله را می‌خوانید در حالی که دیگران در جهان همزمان زندگی می‌کنند. آن‌ها concurrent با شما وجود دارند.

Concurrency موضوعی گسترده در علوم کامپیوتر است و از این تعریف انواع موضوعات منشعب می‌شود: نظریه، رویکردهای مدل‌سازی concurrency، صحت منطق، مسائل عملی — حتی فیزیک نظری! در طول کتاب به برخی موضوعات فرعی اشاره می‌کنیم، اما بیشتر روی مسائل عملی تمرکز می‌کنیم که درک concurrency در context Go را شامل می‌شوند: Go چگونه concurrency را مدل می‌کند، چه مسائلی از این مدل ناشی می‌شود، و چگونه می‌توانیم primitiveها را در این مدل ترکیب کنیم تا مشکلات را حل کنیم.

در این فصل نگاهی گسترده به برخی دلایل اهمیت concurrency در علوم کامپیوتر، چرایی دشوار بودن concurrency و نیاز به مطالعهٔ دقیق، و — مهم‌تر از همه — این ایده که با وجود این چالش‌ها، Go می‌تواند با primitiveهای همزمانی‌اش برنامه‌ها را واضح‌تر و سریع‌تر کند، می‌اندازیم.

مثل بیشتر مسیرهای فهم، با کمی تاریخ شروع می‌کنیم. ابتدا ببینیم concurrency چگونه موضوعی مهم شد.

قانون Moore، Web Scale و آشفتگی‌ای که در آن هستیم

در ۱۹۶۵، Gordon Moore مقاله‌ای سه‌صفحه‌ای نوشت که هم تثبیت بازار الکترونیک به سمت integrated circuitها و هم دو برابر شدن تعداد componentها در integrated circuit هر سال برای حداقل یک دهه را توصیف کرد. در ۱۹۷۵ این پیش‌بینی را اصلاح کرد و گفت تعداد componentها روی integrated circuit هر دو سال دو برابر می‌شود. این پیش‌بینی تا همین اواخر — حدود ۲۰۱۲ — تقریباً درست ماند.

چند شرکت کندی پیش‌بینی‌شدهٔ قانون Moore را پیش‌بینی کردند و راه‌های جایگزین برای افزایش توان محاسباتی را بررسی کردند. همان‌طور که می‌گویند، necessity مادر innovation است و به این ترتیب multicore processorها متولد شدند.

این راه‌حل هوشمندانه‌ای برای محدودیت‌های قانون Moore به نظر می‌رسید، اما computer scientistها به‌زودی با محدودیت قانون دیگری روبه‌رو شدند: قانون Amdahl، به نام معمار کامپیوتر Gene Amdahl.

قانون Amdahl روشی برای مدل‌سازی سود بالقوهٔ عملکرد از پیاده‌سازی راه‌حل یک مسئله به‌صورت parallel توصیف می‌کند. به‌طور خلاصه می‌گوود سودها به این محدود است که چه بخشی از برنامه باید sequential نوشته شود.

مثلاً تصور کنید برنامه‌ای عمدتاً GUI-based می‌نویسید: کاربر interface می‌بیند، دکمه‌ای می‌زند و اتفاقی می‌افتد. این نوع برنامه با یک بخش sequential بسیار بزرگ در pipeline محدود می‌شود: تعامل انسان. هر چند core در اختیار این برنامه بگذارید، همیشه با سرعت تعامل کاربر با interface محدود است.

حال مثال دیگری: محاسبهٔ رقم‌های pi. به‌لطف کلاسی از الگوریتم‌ها به نام spigot algorithm، این مسئله embarrassingly parallel نامیده می‌شود — با وجود نام عجیب، اصطلاح فنی است و یعنی به‌راحتی به taskهای parallel تقسیم می‌شود. در این حالت با در دسترس قرار دادن core بیشتر سود قابل‌توجهی حاصل می‌شود و مسئلهٔ جدید شما ترکیب و ذخیرهٔ نتایج می‌شود.

قانون Amdahl به درک تفاوت این دو مسئله کمک می‌کند و می‌تواند در تصمیم‌گیری اینکه parallelization راه درست برای نگرانی‌های عملکرد در سیستم شماست یا نه، کمک کند.

برای مسائلی که embarrassingly parallel هستند، توصیه می‌شود برنامه را طوری بنویسید که horizontally scale شود. یعنی instanceهای برنامه را روی CPU یا ماشین بیشتر اجرا کنید و runtime سیستم بهبود یابد. مسائل embarrassingly parallel با این مدل عالی جور می‌شوند چون ساختار برنامه را طوری می‌چینید که chunkهای مسئله را به instanceهای مختلف بفرستید.

horizontal scaling در اوایل ۲۰۰۰ها با paradigm جدیدی آسان‌تر شد: cloud computing. اگرچه نشانه‌هایی از استفادهٔ این عبارت از دههٔ ۱۹۷۰ وجود دارد، اوایل ۲۰۰۰ها زمانی است که ایده واقعاً در zeitgeist ریشه دواند. cloud computing به معنای scale و رویکرد جدیدی برای deploy برنامه و horizontal scaling بود. به‌جای ماشین‌هایی که با دقت انتخاب، نرم‌افزار نصب و نگهداری می‌کردید، cloud computing دسترسی به poolهای عظیم resource را implied می‌کرد که on-demand برای workloadها به ماشین provision می‌شدند. ماشین‌ها تقریباً ephemeral شدند و با ویژگی‌هایی provision می‌شدند که متناسب با برنامه‌هایی بود که اجرا می‌کردند. معمولاً (اما نه همیشه) این poolها در data center شرکت‌های دیگر میزبانی می‌شدند.

این تغییر نوع تفکر جدیدی را تشویق کرد. ناگهان developerها دسترسی نسبتاً ارزانی به توان محاسباتی عظیم برای حل مسائل بزرگ داشتند. راه‌حل‌ها می‌توانستند به‌سادگی روی ماشین‌های زیاد و حتی regionهای جهانی گسترش یابند. cloud computing مجموعهٔ جدیدی از راه‌حل‌ها برای مسائلی را ممکن کرد که قبلاً فقط برای غول‌های فناوری قابل حل بود.

اما cloud computing چالش‌های جدید زیادی هم آورد: provision این resourceها، ارتباط بین instanceهای ماشین، تجمیع و ذخیرهٔ نتایج — همه مسائلی برای حل شدند. اما سخت‌ترین‌شان figure out کردن نحوهٔ مدل‌سازی concurrent کد بود. اینکه بخش‌هایی از راه‌حل روی ماشین‌های مختلف اجرا می‌شوند، برخی مسائل رایج هنگام مدل‌سازی concurrent مسئله را تشدید کرد. حل موفق این مسائل به‌زودی به برند جدیدی برای نرم‌افزار منجر شد: web scale.

اگر نرم‌افزار web scale بود، از جمله انتظار می‌رفت embarrassingly parallel باشد؛ یعنی معمولاً باید صدها هزار (یا بیشتر) workload همزمان را با افزودن instance بیشتر از برنامه handle کند. این ویژگی‌هایی مثل rolling upgrade، معماری elastic horizontally scalable و توزیع جغرافیایی را ممکن می‌کرد. همچنین سطح جدیدی از پیچیدگی در درک و fault tolerance معرفی کرد.

و در این دنیای چند core، cloud computing، web scale و مسائلی که شاید parallelizable باشند یا نباشند، developer مدرن را پیدا می‌کنیم — شاید کمی overwhelmed. proverbial buck به ما پاس داده شده و انتظار می‌رود در محدودیت سخت‌افزاری که به ما داده شده مشکلات را حل کنیم. در ۲۰۰۵، Herb Sutter مقاله‌ای برای Dr. Dobb's با عنوان «The free lunch is over: A fundamental turn toward concurrency in software» نوشت. عنوان مناسب است و مقاله prophetic. در پایان Sutter می‌گوید: «We desperately need a higher-level programming model for concurrency than languages offer today.»

برای فهم چرایی زبان قوی Sutter باید ببینیم چرا concurrency را درست گرفتن این‌قدر سخت است.

چرا همزمانی سخت است؟

کد concurrent notoriously سخت است درست گرفته شود. معمولاً چند iteration لازم است تا طبق انتظار کار کند، و حتی آن‌گاه هم uncommon نیست bugها سال‌ها در کد بمانند تا تغییری در timing (استفادهٔ سنگین‌تر از disk، کاربران بیشتر logged in و غیره) bug پنهان قبلی را آشکار کند. در واقع برای همین کتاب، تا جایی که ممکن بود چشم روی کد گذاشتم تا این را mitigate کنم.

خوشبختانه همه هنگام کار با کد concurrent به همان مسائل برمی‌خورند. به‌خاطر این، computer scientistها توانستند مسائل رایج را label کنند که به ما اجازه می‌دهد بحث کنیم چگونه پیش می‌آیند، چرا، و چگونه حلشان کنیم.

پس شروع کنیم. در ادامه برخی از رایج‌ترین مسائلی که کار با کد concurrent را هم frustrating و هم interesting می‌کنند.

Race condition

race condition وقتی رخ می‌دهد که دو یا چند operation باید به ترتیب درست اجرا شوند، اما برنامه طوری نوشته نشده که این ترتیب تضمین شود.

بیشتر اوقات این در data race ظاهر می‌شود: یک operation concurrent سعی می‌کند متغیر را بخواند در حالی که در زمان نامشخصی operation concurrent دیگر سعی می‌کند روی همان متغیر بنویسد.

یک مثال پایه:

var data int
go func() {
    data++
}()
if data == 0 {
    fmt.Printf("the value is %v.\n", data)
}

در Go می‌توانید از keyword go برای اجرای concurrent یک function استفاده کنید. با این کار چیزی به نام goroutine ساخته می‌شود. در بخش «Goroutineها» (صفحه ۳۷) به‌تفصیل بحث می‌کنیم.

اینجا خطوط ۳ و ۵ هر دو سعی دارند به متغیر data دسترسی پیدا کنند، اما تضمینی نیست این به چه ترتیبی رخ دهد. سه outcome ممکن برای اجرای این کد وجود دارد:

• چیزی چاپ نمی‌شود. در این حالت خط ۳ قبل از خط ۵ اجرا شده.
• «the value is 0» چاپ می‌شود. در این حالت خطوط ۵ و ۶ قبل از خط ۳ اجرا شده‌اند.
• «the value is 1» چاپ می‌شود. در این حالت خط ۵ قبل از خط ۳ اجرا شده، اما خط ۳ قبل از خط ۶.

همان‌طور که می‌بینید، فقط چند خط کد نادرست می‌تواند variability عظیمی در برنامه معرفی کند.

بیشتر اوقات data raceها چون developerها sequential به مسئله فکر می‌کنند معرفی می‌شوند. فرض می‌کنند چون یک خط قبل از خط دیگر است، اول اجرا می‌شود. فرض می‌کنند goroutine بالا schedule و execute می‌شود قبل از اینکه متغیر data در if statement خوانده شود.

هنگام نوشتن کد concurrent باید meticulously سناریوهای ممکن را iterate کنید. مگر از تکنیک‌هایی که بعداً در کتاب پوشش می‌دهیم استفاده کنید، تضمینی ندارید کد به ترتیب فهرست‌شده در source code اجرا شود. گاهی کمک می‌کند تصور کنید فاصلهٔ زیادی بین operationها می‌گذرد. تصور کنید یک ساعت بین invoke شدن goroutine و اجرای آن می‌گذرد. بقیهٔ برنامه چگونه رفتار می‌کند؟ اگر یک ساعت بین اجرای موفق goroutine و رسیدن برنامه به if statement بگذرد چه؟ این‌گونه فکر کردن به من کمک می‌کند چون برای کامپیوتر scale متفاوت است، اما differentialهای زمانی نسبی تقریباً یکسان است.

در واقع بعضی developerها در trap پاشیدن sleep در سراسر کد می‌افتند چون به نظر می‌رسد مشکلات concurrency را حل می‌کند. بیایید در برنامهٔ قبلی امتحان کنیم:

var data int
go func() { data++ }()
time.Sleep(1*time.Second) // This is bad!
if data == 0 {
    fmt.Printf("the value is %v.\n" data)
}

data race را حل کردیم؟ نه. در واقع هنوز ممکن است هر سه outcome از این برنامه حاصل شود، فقط increasingly unlikely. هر چه بیشتر بین invoke کردن goroutine و بررسی مقدار data sleep کنیم، برنامه به correctness نزدیک‌تر می‌شود — اما این probability asymptotically به logical correctness نزدیک می‌شود؛ هرگز logically correct نخواهد بود.

علاوه بر این، inefficiency به الگوریتم معرفی کردیم. حالا یک ثانیه باید sleep کنیم تا احتمال کمتر دیدن data race باشد. اگر از ابزار درست استفاده می‌کردیم شاید اصلاً منتظر نمی‌ماندیم، یا wait فقط یک microsecond بود.

نتیجه این است که همیشه logical correctness را target کنید. گذاشتن sleep در کد می‌تواند برای debug برنامه‌های concurrent مفید باشد، اما راه‌حل نیست.

race conditionها از insidiousترین انواع bugهای concurrency هستند چون ممکن است سال‌ها بعد از قرار گرفتن کد در production ظاهر نشوند. معمولاً با تغییر environment اجرای کد یا رخداد بی‌سابقه precipitate می‌شوند. در این موارد کد درست به نظر می‌رسد، اما در واقع فقط احتمال بسیار بالایی دارد operationها به ترتیب اجرا شوند. دیر یا زود برنامه consequence ناخواسته خواهد داشت.

Atomicity

وقتی چیزی atomic در نظر گرفته می‌شود، یا property atomicity دارد، یعنی در contextی که در آن عمل می‌کند indivisible یا uninterruptible است. پس واقعاً یعنی چه، و چرا برای کار با کد concurrent مهم است بدانیم؟

اولین نکتهٔ بسیار مهم کلمهٔ «context» است. چیزی ممکن است در یک context atomic باشد و در context دیگر نباشد. operationهایی که در context process شما atomic هستند ممکن است در context سیستم‌عامل نباشند؛ operationهای atomic در context سیستم‌عامل ممکن است در context ماشین شما نباشند؛ و operationهای atomic در context ماشین شما ممکن است در context برنامهٔ شما نباشند. به‌عبارت دیگر atomicity یک operation بسته به scope فعلی تعریف‌شده می‌تواند تغییر کند. این fact می‌تواند هم به نفع و هم علیه شما کار کند!

وقتی به atomicity فکر می‌کنید، اغلب اولین کار تعریف context یا scope است که operation در آن atomic در نظر گرفته می‌شود. همه‌چیز از این follows می‌کند.

Fun Fact

در ۲۰۰۶، شرکت بازی Blizzard با موفقیت MDY Industries را به دلیل ساخت برنامه‌ای به نام «Glider» که بازی World of Warcraft را بدون دخالت کاربر به‌صورت خودکار بازی می‌کرد، به ۶٬۰۰۰٬۰۰۰ دلار محکوم کرد. این نوع برنامه‌ها معمولاً «bot» (مخفف robot) نامیده می‌شوند.

در آن زمان World of Warcraft برنامهٔ anti-cheating به نام «Warden» داشت که هر وقت بازی می‌کردید اجرا می‌شد. Warden بین چیزهای دیگر حافظهٔ ماشین host را scan می‌کرد و heuristic اجرا می‌کرد تا برنامه‌هایی که برای cheat به نظر می‌رسند را پیدا کند.

Glider با بهره‌گیری از مفهوم atomic context از این بررسی موفق اجتناب کرد! Warden scan حافظه روی ماشین را operation atomic در نظر می‌گرفت، اما Glider از hardware interrupt استفاده کرد تا قبل از شروع scan پنهان شود! scan حافظهٔ Warden در context process atomic بود، اما در context سیستم‌عامل نبود.

حال به «indivisible» و «uninterruptible» نگاه کنیم. یعنی در context تعریف‌شده، چیزی atomic به‌طور کامل رخ می‌دهد بدون اینکه در آن context همزمان چیزی اتفاق بیفتد. هنوز پیچیده است، پس مثالی ببینیم:

i++

ساده‌ترین مثال ممکن است، اما به‌راحتی مفهوم atomicity را نشان می‌دهد. ممکن است atomic به نظر برسد، اما تحلیل کوتاه چند operation نشان می‌دهد:

• مقدار i را retrieve کن.
• مقدار i را increment کن.
• مقدار i را store کن.

هر کدام از این operationها به‌تنهایی atomic است، اما ترکیب سه‌تایی ممکن است نباشد — بسته به context. این property جالبی از atomic operationها را آشکار می‌کند: ترکیب آن‌ها لزوماً operation atomic بزرگ‌تر تولید نمی‌کند. atomic کردن operation به contextی که می‌خواهید در آن atomic باشد بستگی دارد. اگر context برنامه‌ای بدون process concurrent باشد، این کد در آن context atomic است. اگر context goroutineی باشد که i را به goroutine دیگر expose نمی‌کند، این کد atomic است.

پس چرا اهمیت دارد؟ atomicity مهم است چون اگر چیزی atomic باشد، implicitly در contextهای concurrent safe است. این به ما اجازه می‌دهد برنامه‌های logically correct بسازیم — و همان‌طور که بعداً می‌بینیم — حتی راهی برای optimize برنامه‌های concurrent باشد.

بیشتر statementها atomic نیستند، چه برسد به function، method و program. اگر atomicity کلید compose کردن برنامه‌های logically correct است و بیشتر statementها atomic نیستند، چگونه این دو را reconcile کنیم؟ بعداً عمیق‌تر می‌رویم، اما خلاصه می‌توانیم با تکنیک‌های مختلف atomicity را force کنیم. هنر سپس تعیین کدام بخش‌های کد باید atomic باشند و در چه سطح granularity است. برخی این چالش‌ها را در بخش بعد بحث می‌کنیم.

Memory Access Synchronization

فرض کنید data race داریم: دو process concurrent سعی دارند به همان ناحیهٔ حافظه دسترسی پیدا کنند و نحوهٔ دسترسی atomic نیست. مثال سادهٔ data race قبلی با چند اصلاح کافی است:

var data int
go func() { data++}()
if data == 0 {
    fmt.Println("the value is 0.")
} else {
    fmt.Printf("the value is %v.\n", data)
}

else clause اضافه کردیم تا صرف‌نظر از مقدار data همیشه خروجی بگیریم. یادآوری: همان‌طور که نوشته شده data race وجود دارد و خروجی برنامه کاملاً nondeterministic است.

در واقع نامی برای بخشی از برنامه که به دسترسی انحصاری به resource مشترک نیاز دارد وجود دارد: critical section. در این مثال سه critical section داریم:

• goroutine ما که متغیر data را increment می‌کند.
• if statement ما که بررسی می‌کند مقدار data صفر است یا نه.
• statement fmt.Printf ما که مقدار data را برای خروجی retrieve می‌کند.

راه‌های مختلفی برای guard کردن critical sectionهای برنامه وجود دارد و Go ایده‌های بهتری برای این کار دارد، اما یک راه حل این مسئله synchronize کردن دسترسی به حافظه بین critical sectionهاست. ببینیم چگونه است.

کد زیر idiomatic Go نیست (و پیشنهاد نمی‌کنم data race را این‌طور حل کنید)، اما به‌سادگی memory access synchronization را نشان می‌دهد. اگر type، function یا methodهای این مثال برایتان ناآشناست، اشکالی ندارد. روی مفهوم synchronize کردن دسترسی به حافظه با دنبال کردن calloutها تمرکز کنید:

var memoryAccess sync.Mutex
var value int
go func() {
    memoryAccess.Lock()
    value++
    memoryAccess.Unlock()
}()

memoryAccess.Lock()
if value == 0 {
    fmt.Printf("the value is %v.\n", value)
} else {
    fmt.Printf("the value is %v.\n", value)
}
memoryAccess.Unlock()

اینجا متغیری اضافه می‌کنیم که به کد اجازه می‌دهد دسترسی به حافظهٔ متغیر data را synchronize کند. type sync.Mutex را در بخش «The sync Package» (صفحه ۴۷) به‌تفصیل بررسی می‌کنیم.

اینجا اعلام می‌کنیم تا خلافش اعلام نشود، goroutine ما باید دسترسی انحصاری به این حافظه داشته باشد.

اینجا اعلام می‌کنیم goroutine با این حافظه کارش تمام شده.

اینجا دوباره اعلام می‌کنیم statementهای conditional بعدی باید دسترسی انحصاری به حافظهٔ متغیر data داشته باشند.

اینجا اعلام می‌کنیم دوباره با این حافظه کارمان تمام شده.

در این مثال conventionی برای developerها ساختیم. هر وقت بخواهند به حافظهٔ متغیر data دسترسی پیدا کنند، باید ابتدا Lock و در پایان Unlock بزنند. کد بین این دو statement می‌تواند فرض کند دسترسی انحصاری به data دارد؛ دسترسی به حافظه را با موفقیت synchronize کردیم. همچنین توجه کنید اگر developerها این convention را رعایت نکنند، تضمینی برای دسترسی انحصاری نداریم! در بخش «Confinement» (صفحه ۸۵) به این ایده برمی‌گردیم.

شاید متوجه شده باشید که data race را حل کردیم، اما race condition را نه! ترتیب operationها در این برنامه هنوز nondeterministic است؛ فقط scope nondeterminism را کمی narrow کردیم. در این مثال یا goroutine اول اجرا می‌شود، یا هر دو بلوک if و else ما. هنوز نمی‌دانیم در هر اجرای برنامه کدام اول رخ می‌دهد. بعداً ابزار حل درست این نوع مسئله را بررسی می‌کنیم.

در ظاهر ساده به نظر می‌رسد: critical section پیدا کردید، نقطه‌ای برای synchronize کردن دسترسی به حافظه اضافه کنید! آسان است، نه؟ خب… sort of.

درست است که با synchronize کردن دسترسی به حافظه بعضی مسائل حل می‌شوند، اما همان‌طور که دیدیم، خودکار data race یا logical correctness را حل نمی‌کند. علاوه بر این می‌تواند مسائل maintenance و performance ایجاد کند.

قبلاً گفتیم conventionی برای اعلام نیاز به دسترسی انحصاری به حافظه ساختیم. convention عالی است، اما نادیده گرفتنش هم آسان است — به‌ویژه در software engineering جایی که گاهی demandهای business بر prudence غلبه می‌کند. با synchronize کردن دسترسی به حافظه به این شکل، روی این حساب می‌کنید همهٔ developerهای دیگر همین convention را الان و در آینده رعایت کنند. سفارش بلندی است. خوشبختانه بعداً در کتاب راه‌هایی می‌بینیم که به همکاران موفق‌تر بودن کمک کند.

synchronize کردن دسترسی به حافظه به این شکل repercussionهای performance هم دارد. جزئیات را برای بعد نگه می‌داریم وقتی package sync را در بخش «The sync Package» (صفحه ۴۷) بررسی می‌کنیم، اما callهای Lock که می‌بینید می‌توانند برنامه را کند کنند. هر بار یکی از این operationها را انجام می‌دهیم، برنامه برای مدتی pause می‌شود. این دو سؤال را مطرح می‌کند:

• آیا critical sectionهای من مکرراً enter و exit می‌شوند؟
• اندازهٔ critical sectionهای من چقدر باید باشد؟

پاسخ به این دو سؤال در context برنامه هنر است و difficulty synchronize کردن دسترسی به حافظه را افزایش می‌دهد.

synchronize کردن دسترسی به حافظه هم برخی مشکلات مشترک با تکنیک‌های دیگر مدل‌سازی مسائل concurrent دارد که در بخش بعد بحث می‌کنیم.

Deadlock، Livelock و Starvation

بخش‌های قبلی دربارهٔ correctness برنامه بودند: اگر این مسائل درست مدیریت شوند، برنامه هرگز پاسخ نادرست نمی‌دهد. متأسفانه حتی اگر این کلاس مسائل را handle کنید، کلاس دیگری برای مقابله وجود دارد: deadlock، livelock و starvation. این مسائل همه دربارهٔ اطمینان از اینکه برنامه همیشه کار مفیدی دارد. اگر درست handle نشوند، برنامه می‌تواند به حالتی برود که بدون مداخلهٔ خارجی هرگز recover نکند.

Deadlock

برنامهٔ deadlocked برنامه‌ای است که همهٔ processهای concurrent منتظر یکدیگرند. در این حالت برنامه بدون مداخلهٔ خارجی هرگز recover نمی‌شود.

اگر grim به نظر می‌رسد، چون همین‌طور است! Go runtime سعی می‌کند سهم خود را انجام دهد و بعضی deadlockها را detect می‌کند (همهٔ goroutineها باید blocked یا «asleep»¹ باشند)، اما در prevent کردن deadlock کمکی نمی‌کند.

برای solidify کردن deadlock، ابتدا مثالی ببینیم. باز هم اگر type، function، method یا package نمی‌شناسید نادیده بگیرید و فقط calloutهای کد را دنبال کنید.

type value struct {
    mu    sync.Mutex
    value int
}

var wg sync.WaitGroup
printSum := func(v1, v2 *value) {
    defer wg.Done()
    v1.mu.Lock()
    defer v1.mu.Unlock()

    time.Sleep(2*time.Second)
    v2.mu.Lock()
    defer v2.mu.Unlock()

    fmt.Printf("sum=%v\n", v1.value + v2.value)
}

var a, b value
wg.Add(2)
go printSum(&a, &b)
go printSum(&b, &a)
wg.Wait()

اینجا سعی می‌کنیم وارد critical section برای value ورودی شویم.

اینجا از statement defer استفاده می‌کنیم تا قبل از return شدن printSum از critical section خارج شویم.

اینجا برای مدتی sleep می‌کنیم تا کار را simulate کنیم (و deadlock را trigger کنیم).

اگر این کد را اجرا کنید، احتمالاً می‌بینید:

fatal error: all goroutines are asleep - deadlock!

چرا؟ با دقت نگاه کنید timing issue در این کد می‌بینید. در ادامه نمایش گرافیکی از آنچه رخ می‌دهد. جعبه‌ها functionها، خطوط افقی call به این functionها، و میله‌های عمودی lifetime function در بالای گرافیک را نشان می‌دهند (شکل ۱-۱).

شکل ۱-۱. نمایش timing issue که به deadlock منجر می‌شود

اساساً دو چرخ‌دنده ساختیم که نمی‌توانند با هم بچرخند: اولین call به printSum، a را lock می‌کند و سعی می‌کند b را lock کند، اما در این میان دومین call به printSum، b را lock کرده و سعی کرده a را lock کند. هر دو goroutine بی‌نهایت منتظر یکدیگرند.

Irony

برای ساده نگه داشتن مثال از time.Sleep برای trigger کردن deadlock استفاده کردم. با این حال race condition معرفی می‌کند! می‌توانید پیدایش کنید؟

deadlock منطقی «کامل» به synchronization درست نیاز دارد.²

وقتی گرافیکی این‌طور layout می‌کنیم چرا deadlock رخ می‌دهد pretty obvious است، اما از تعریف rigorous سود می‌بریم. چند condition برای arise شدن deadlock باید برقرار باشد و در ۱۹۷۱ Edgar Coffman در مقاله‌ای این conditionها را enumerate کرد. conditionها اکنون Coffman Conditions نامیده می‌شوند و پایهٔ تکنیک‌های detect، prevent و correct کردن deadlock هستند.

Coffman Conditions به شرح زیر است:

Mutual Exclusion process concurrent در هر لحظه حق انحصاری روی resource دارد.

Wait For Condition process concurrent باید همزمان resource را نگه دارد و منتظر resource اضافی باشد.

No Preemption resource نگه‌داشته‌شده توسط process concurrent فقط توسط همان process release می‌شود، پس این condition برقرار است.

Circular Wait process concurrent (P1) باید منتظر زنجیره‌ای از processهای concurrent دیگر (P2) باشد که به نوبت منتظر آن (P1) هستند، پس این condition نهایی هم برقرار است.

¹ proposal پذیرفته‌شده‌ای برای اجازهٔ detect کردن partial deadlock توسط runtime وجود دارد، اما implement نشده. برای اطلاعات بیشتر https://github.com/golang/go/issues/13759 را ببینید.

² در واقع تضمینی نداریم goroutineها به چه ترتیبی اجرا شوند یا چقدر طول می‌کشد start شوند. plausible است، اگرچه unlikely، یک goroutine هر دو lock را acquire و release کند قبل از اینکه دیگری شروع شود و از deadlock اجتناب کند!

برنامهٔ contrived ما را بررسی کنیم و ببینیم آیا هر چهار condition برقرار است:

1. function printSum به حق انحصاری a و b نیاز دارد، پس این condition برقرار است.
2. چون printSum یا a یا b را نگه می‌دارد و منتظر دیگری است، این condition برقرار است.
3. راهی برای preempt شدن goroutineها نداده‌ایم.
4. اولین invocation printSum منتظر دومین است و بالعکس.

بله، قطعاً deadlock داریم.

این قوانین به prevent کردن deadlock هم کمک می‌کنند. اگر حداقل یکی از conditionها true نباشد، می‌توانیم از arise شدن deadlock جلوگیری کنیم. متأسفانه در عمل reasoning دربارهٔ این conditionها سخت است و prevent کردن دشوار. وب پر از سؤالات developerهایی مثل ما است که می‌پرسند چرا snippet کد deadlock می‌کند. معمولاً وقتی کسی اشاره کند pretty obvious است، اما اغلب به چشم دیگری نیاز است. در بخش «Determining Concurrency Safety» (صفحه ۱۸) می‌گوییم چرا.

Livelock

livelock برنامه‌هایی هستند که actively operationهای concurrent انجام می‌دهند، اما این operationها state برنامه را جلو نمی‌برند.

آیا در راهرو به سمت شخص دیگری راه رفته‌اید؟ او به یک طرف می‌رود تا رد شوید، اما شما هم همین کار را کرده‌اید. پس به طرف دیگر می‌روید، او هم. تصور کنید برای همیشه ادامه دارد — livelock را فهمیدید.

بیایید کدی بنویسیم که این سناریو را نشان دهد. ابتدا چند helper function برای ساده‌سازی مثال. برای مثال کارکرد، کد از چند topic که هنوز پوشش نداده‌ایم استفاده می‌کند. تا grasp محکمی روی package sync ندارید، توصیه نمی‌کنم جزئیات را بفهمید. calloutها را دنبال کنید تا highlights را بگیرید، سپس به بلوک دوم کد — قلب مثال — توجه کنید.

cadence := sync.NewCond(&sync.Mutex{})
go func() {
    for range time.Tick(1*time.Millisecond) {
        cadence.Broadcast()
    }
}()

takeStep := func() {
    cadence.L.Lock()
    cadence.Wait()
    cadence.L.Unlock()
}

tryDir := func(dirName string, dir *int32, out *bytes.Buffer) bool {
    fmt.Fprintf(out, " %v", dirName)
    atomic.AddInt32(dir, 1)
    takeStep()
    if atomic.LoadInt32(dir) == 1 {
        fmt.Fprint(out, ". Success!")
        return true
    }
    takeStep()
    atomic.AddInt32(dir, -1)
    return false
}

var left, right int32
tryLeft := func(out *bytes.Buffer) bool { return tryDir("left", &left, out) }
tryRight := func(out *bytes.Buffer) bool { return tryDir("right", &right, out) }

tryDir به شخص اجازه می‌دهد در یک جهت حرکت کند و موفق بود یا نه برمی‌گرداند. هر جهت با count تعداد افرادی که می‌خواهند در آن جهت حرکت کنند، dir، نمایش داده می‌شود.

ابتدا قصد حرکت در یک جهت را با increment کردن آن جهت اعلام می‌کنیم. package atomic را در فصل ۳ به‌تفصیل بحث می‌کنیم. فعلاً فقط بدانید operationهای این package atomic هستند.

برای نشان دادن livelock در مثال، هر شخص باید با همان سرعت یا cadence حرکت کند. takeStep cadence ثابت بین همهٔ طرف‌ها را simulate می‌کند.

اینجا شخص می‌فهمد نمی‌تواند در این جهت برود و کنار می‌کشد. با decrement کردن آن جهت نشان می‌دهیم.

walk := func(walking *sync.WaitGroup, name string) {
    var out bytes.Buffer
    defer func() { fmt.Println(out.String()) }()
    defer walking.Done()
    fmt.Fprintf(&out, "%v is trying to scoot:", name)
    for i := 0; i < 5; i++ {
        if tryLeft(&out) || tryRight(&out) {
            return
        }
    }
    fmt.Fprintf(&out, "\n%v tosses her hands up in exasperation!", name)
}

var peopleInHallway sync.WaitGroup
peopleInHallway.Add(2)
go walk(&peopleInHallway, "Alice")
go walk(&peopleInHallway, "Barbara")
peopleInHallway.Wait()

محدودیت مصنوعی روی تعداد تلاش گذاشتم تا برنامه تمام شود. در برنامه‌ای با livelock شاید چنین محدودیتی نباشد — به همین دلیل مشکل است!

ابتدا شخص سعی می‌کند به چپ برود، اگر نشد به راست.

این متغیر راهی برای انتظار تا هر دو نفر بتوانند از کنار هم رد شوند یا تسلیم شوند.

خروجی:

Alice is trying to scoot: left right left right left right left right left right
Alice tosses her hands up in exasperation!
Barbara is trying to scoot: left right left right left right left right
left right
Barbara tosses her hands up in exasperation!

می‌بینید Alice و Barbara مدام سر راه یکدیگر می‌ایستند تا بالاخره تسلیم می‌شوند.

این مثال دلیل بسیار رایج نوشتن livelock را نشان می‌دهد: دو یا چند process concurrent سعی می‌کنند بدون coordination از deadlock جلوگیری کنند. اگر افراد راهرو توافق می‌کردند فقط یک نفر حرکت کند، livelock نبود: یکی می‌ایستاد، دیگری به طرف دیگر می‌رفت و راهشان را ادامه می‌دادند.

به نظرم livelockها سخت‌تر از deadlock تشخیص داده می‌شوند چون ممکن است برنامه در حال کار به نظر برسد. اگر برنامه livelocked روی ماشین اجرا شود و CPU utilization را برای فهمیدن آیا کاری انجام می‌دهد نگاه کنید، شاید فکر کنید بله. بسته به livelock، شاید signalهای دیگری هم emit کند که فکر کنید کار می‌کند. و در همین حال برنامه بازی بی‌پایان رد شدن در راهرو را بازی می‌کند.

livelock زیرمجموعهٔ مجموعهٔ بزرگ‌تری از مسائل به نام starvation است. بعد آن را می‌بینیم.

Starvation

starvation هر موقعیتی است که process concurrent نمی‌تواند همهٔ resourceهای لازم برای انجام کار را بگیرد.

وقتی livelock بحث کردیم، resourceای که هر goroutine از آن starved بود lock مشترک بود. livelock جدا از starvation بحث می‌شود چون در livelock همهٔ processهای concurrent به‌طور مساوی starved می‌شوند و هیچ کاری انجام نمی‌شود.

به‌طور گسترده‌تر، starvation معمولاً implied می‌کند یک یا چند process concurrent greedy هستند و unfair مانع یک یا چند process concurrent می‌شوند کار را به‌قدر ممکن efficient یا شاید اصلاً انجام دهند.

مثال برنامه با goroutine greedy و goroutine polite:

var wg sync.WaitGroup
var sharedLock sync.Mutex
const runtime = 1*time.Second

greedyWorker := func() {
    defer wg.Done()

    var count int
    for begin := time.Now(); time.Since(begin) <= runtime; {
        sharedLock.Lock()
        time.Sleep(3*time.Nanosecond)
        sharedLock.Unlock()
        count++
    }

    fmt.Printf("Greedy worker was able to execute %v work loops\n", count)
}

politeWorker := func() {
    defer wg.Done()

    var count int
    for begin := time.Now(); time.Since(begin) <= runtime; {
        sharedLock.Lock()
        time.Sleep(1*time.Nanosecond)
        sharedLock.Unlock()

        sharedLock.Lock()
        time.Sleep(1*time.Nanosecond)
        sharedLock.Unlock()

        sharedLock.Lock()
        time.Sleep(1*time.Nanosecond)
        sharedLock.Unlock()

        count++
    }

    fmt.Printf("Polite worker was able to execute %v work loops.\n", count)
}

wg.Add(2)
go greedyWorker()
go politeWorker()

wg.Wait()

خروجی:

Polite worker was able to execute 289777 work loops.
Greedy worker was able to execute 471287 work loops

greedy worker lock مشترک را برای کل work loop خود greedy نگه می‌دارد، در حالی که polite worker فقط وقتی لازم است lock می‌کند. هر دو worker همان مقدار کار شبیه‌سازی‌شده (sleep سه nanosecond) انجام می‌دهند، اما در همان زمان greedy worker تقریباً دو برابر کار انجام داده!

اگر فرض کنیم هر دو worker critical section هم‌اندازه دارند، به‌جای نتیجه‌گیری که الگوریتم greedy worker کارآمدتر است (یا callهای Lock و Unlock کندند — نیستند)، نتیجه می‌گیریم greedy worker hold روی lock مشترک را بی‌دلیل فراتر از critical section گسترش داده و (از طریق starvation) goroutine polite worker را از انجام کار کارآمد منع می‌کند.

technique ما برای شناسایی starvation: metric. starvation argument خوبی برای record و sample کردن metric است. یکی از راه‌های detect و حل starvation log کردن انجام کار و تعیین اینکه rate کار به اندازهٔ انتظار است.

یافتن تعادل

جالب است که مثال کد قبلی می‌تواند repercussionهای performance memory access synchronization را هم نشان دهد. چون synchronize کردن دسترسی به حافظه گران است، ممکن است گسترش lock فراتر از critical section سودمند باشد. از طرف دیگر — همان‌طور که دیدیم — با این کار خطر starve کردن processهای concurrent دیگر را می‌گیریم.

اگر memory access synchronization استفاده می‌کنید، باید بین coarse-grained synchronization برای performance و fine-grained synchronization برای fairness تعادل پیدا کنید. وقتی وقت tune کردن performance برنامه رسید، strongly توصیه می‌کنم ابتدا memory access synchronization را فقط به critical sectionها محدود کنید؛ اگر synchronization مشکل performance شد، همیشه می‌توانید scope را گسترش دهید. برعکس مسیر خیلی سخت‌تر است.

پس starvation می‌تواند برنامه را ناکارآمد یا نادرست رفتار کند. مثال قبلی ناکارآمدی نشان می‌دهد، اما اگر process concurrent آن‌قدر greedy باشد که کاملاً مانع کار process concurrent دیگر شود، مشکل بزرگ‌تری دارید.

حالت starvation از خارج process Go را هم در نظر بگیرید. starvation می‌تواند به CPU، حافظه، file handle، database connection هم apply شود: هر resourceی که باید share شود candidate starvation است.

تعیین ایمنی همزمانی

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

همان‌طور که کشف کردیم، کد concurrent به دلایل متعدد سخت است. اگر developer هستید و سعی می‌کنید همهٔ این مسائل را هنگام افزودن قابلیت جدید یا رفع bug مدیریت کنید، واقعاً سخت است کار درست را تعیین کنید.

اگر از صفر شروع می‌کنید و باید روش منطقی برای مدل‌سازی problem space بسازید و concurrency درگیر است، سخت است abstraction درست را پیدا کنید. concurrency را چگونه به callerها expose کنید؟ چه تکنیک‌هایی solutionی بسازید که هم استفاده از آن آسان و هم تغییرش آسان باشد؟ سطح concurrency درست برای این مسئله چیست؟ اگرچه راه‌های structured فکر کردن به این مسائل وجود دارد، هنر باقی می‌ماند.

به‌عنوان developer که با کد موجود کار می‌کند، همیشه واضح نیست کدام کد از concurrency استفاده می‌کند و چگونه safely از کد استفاده کند. این function signature را ببینید:

// CalculatePi calculates digits of Pi between the begin and end
// place.
func CalculatePi(begin, end int64, pi *Pi)

محاسبهٔ pi با precision بزرگ کاری است که concurrent بهتر انجام می‌شود، اما این مثال سؤالات زیادی مطرح می‌کند:

• چگونه با این function این کار را انجام دهم؟
• آیا مسئول instantiate کردن چند invocation concurrent از function هستم؟
• به نظر می‌رسد همهٔ instanceهای function مستقیماً روی instance Pi که آدرسش را می‌دهم operate می‌کنند؛ آیا مسئول synchronize کردن دسترسی به آن حافظه هستم، یا type Pi این را handle می‌کند؟

یک function همهٔ این سؤالات را مطرح می‌کند. برنامه‌ای با اندازهٔ متوسط را تصور کنید و پیچیدگی‌ای که concurrency می‌تواند ایجاد کند را می‌فهمید.

commentها اینجا معجزه می‌کنند. اگر CalculatePi این‌طور نوشته می‌شد:

// CalculatePi calculates digits of Pi between the begin and end
// place.
//
// Internally, CalculatePi will create FLOOR((end-begin)/2) concurrent
// processes which recursively call CalculatePi. Synchronization of
// writes to pi are handled internally by the Pi struct.
func CalculatePi(begin, end int64, pi *Pi)

حالا می‌فهمیم می‌توانیم function را به‌سادگی صدا بزنیم و نگران concurrency یا synchronization نباشیم. مهم این است comment این جنبه‌ها را پوشش دهد:

• مسئول concurrency کیست؟
• problem space چگونه روی primitiveهای concurrency map شده؟
• مسئول synchronization کیست؟

وقتی function، method و variable در problem spaceهایی که concurrency دارند expose می‌کنید، به همکاران و future self لطف کنید: در comment verbose err کنید و این سه جنبه را پوشش دهید.

همچنین در نظر بگیرید شاید ambiguity در این function نشان می‌دهد model اشتباه است. شاید به‌جای آن رویکرد functional بگیریم و function بدون side effect باشد:

func CalculatePi(begin, end int64) []uint

signature این function به‌تنهایی سؤالات synchronization را حذف می‌کند، اما هنوز سؤال استفاده از concurrency باقی است. می‌توانیم signature را دوباره تغییر دهیم تا signal دیگری از آنچه رخ می‌دهد بدهد:

func CalculatePi(begin, end int64) <-chan uint

اینجا اولین استفاده از چیزی به نام channel را می‌بینیم. به دلایلی که در بخش «Channels» (صفحه ۶۴) بررسی می‌کنیم، این نشان می‌دهد CalculatePi حداقل یک goroutine دارد و نباید خودمان بسازیم.

این تغییرها repercussionهای performance دارد که باید در نظر گرفته شود و دوباره به مسئلهٔ balance کردن clarity با performance برمی‌گردیم. clarity مهم است چون می‌خواهیم احتمال بیشتری داشته باشد کسانی که در آینده با این کد کار می‌کنند کار درست را انجام دهند، و performance به دلایل آشکار مهم است. دو تا mutually exclusive نیستند، اما ترکیبشان سخت است.

حال این دشواری‌های ارتباط را به پروژه‌های team-sized scale up کنید.

وای، این یک مشکل است.

خبر خوب این است که Go در آسان‌تر کردن حل این نوع مسائل پیشرفت کرده. خود زبان readability و simplicity را favor می‌کند. نحوهٔ encourage کردن model کردن کد concurrent، correctness، composability و scalability را encourage می‌کند. در واقع نحوهٔ handle کردن concurrency در Go می‌تواند کمک کند problem domainها را واضح‌تر بیان کنید! ببینیم چرا.

سادگی در برابر پیچیدگی

تا اینجا تصویر تیره‌ای کشیدم. concurrency قطعاً حوزهٔ سختی در علوم کامپیوتر است، اما می‌خواهم با امید ترکتان کنم: این مسائل غیرقابل‌حل نیستند و با primitiveهای concurrency Go می‌توانید الگوریتم‌های concurrent را ایمن‌تر و واضح‌تر بیان کنید. runtime و دشواری‌های ارتباطی که بحث کردیم به‌هیچ‌وجه توسط Go حل نشده‌اند، اما به‌طور قابل‌توجهی آسان‌تر شده‌اند. در فصل بعد ریشهٔ این پیشرفت را کشف می‌کنیم.

اینجا کمی وقت می‌گذاریم روی ایده‌ای که primitiveهای concurrency Go می‌توانند مدل‌سازی problem domain و بیان algorithm را آسان‌تر کنند.

runtime Go بیشتر کار سنگین را انجام می‌دهد و foundation بیشتر nicetyهای concurrency Go را فراهم می‌کند. بحث نحوهٔ کار همه‌چیز را برای فصل ۶ نگه می‌داریم، اما اینجا می‌گوییم چگونه زندگی‌تان را آسان‌تر می‌کنند.

ابتدا garbage collector concurrent و low-latency Go را بحث کنیم. اغلب debate بین developerهاست که آیا garbage collector در زبان چیز خوبی است. مخالفان می‌گویند garbage collector مانع کار در problem domainهایی است که real-time performance یا deterministic performance profile می‌خواهند — pause کردن همهٔ activity در برنامه برای cleanup garbage قابل‌قبول نیست.

با وجود وجه نظری این دیدگاه، کار عالی روی garbage collector Go audienceای که باید جزئیات نحوهٔ garbage collection Go را worry کنند را به‌شدت کاهش داده. از Go 1.8، pauseهای garbage collection معمولاً بین ۱۰ تا ۱۰۰ microsecond است!

چگونه کمک می‌کند؟ memory management domain سخت دیگری در علوم کامپیوتر است و وقتی با concurrency ترکیب شود، نوشتن کد correct فوق‌العاده سخت می‌شود. اگر در اکثریت developerهایی هستید که نباید pauseهای کوچک ۱۰ microsecond را worry کنند، Go با force نکردن مدیریت حافظه — چه برسد به across processهای concurrent — استفاده از concurrency در برنامه را بسیار آسان‌تر کرده.

runtime Go هم به‌صورت خودکار multiplexing operationهای concurrent روی threadهای سیستم‌عامل را handle می‌کند. جملهٔ طولانی است و در بخش «Goroutineها» (صفحه ۳۷) دقیقاً معنی آن را می‌بینیم. برای فهم کمک به شما، کافی است بدانید به شما اجازه می‌دهد مسائل concurrent را مستقیماً روی constructهای concurrent map کنید به‌جای درگیر شدن با جزئیات start و manage کردن thread و map کردن logic به‌طور یکنواخت روی threadهای available.

مثلاً web server می‌نویسید و می‌خواهید هر connection پذیرفته‌شده concurrent با هر connection دیگر handle شود. در بعضی زبان‌ها قبل از accept کردن connection، احتمالاً باید مجموعه‌ای از thread بسازید — معمولاً thread pool — و connectionهای incoming را روی thread map کنید. سپس در هر thread باید loop بزنید روی همهٔ connectionهای آن thread تا مطمئن شوید CPU time می‌گیرند. علاوه بر این باید connection-handling logic را pausable بنویسید تا با connectionهای دیگر به‌طور منصفانه share کند.

خسته‌کننده است! در مقابل، در Go function می‌نویسید و فراخوانی را با keyword go پیش می‌گذارید. runtime همهٔ چیزهایی که بحث کردیم را به‌صورت خودکار handle می‌کند! هنگام design برنامه، تحت کدام model بیشتر به concurrency reach می‌کنید؟ کدام بیشتر احتمال درست شدن دارد؟

primitiveهای concurrency Go compose کردن مسائل بزرگ‌تر را هم آسان‌تر می‌کنند. همان‌طور که در بخش «Channels» (صفحه ۶۴) می‌بینیم، channel primitive Go راه composable و concurrent-safe برای ارتباط بین processهای concurrent فراهم می‌کند.

بیشتر جزئیات نحوهٔ کار این چیزها را skim کردم، اما می‌خواستم حس بدهم Go چگونه شما را دعوت می‌کند concurrency را در برنامه برای حل مشکلات به‌شکل واضح و performant به‌کار ببرید. در فصل بعد فلسفهٔ concurrency و چرایی درست گرفتن Go را بحث می‌کنیم. اگر مشتاق پرش به کد هستید، شاید بخواهید به فصل ۳ بروید.