فصل ۶ — Goroutineها و runtime Go

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

از میان همهٔ کارهایی که runtime Go برای شما انجام می‌دهد، spawn کردن و مدیریت goroutineها احتمالاً بیشترین سود را برای شما و نرم‌افزارتان دارد. Google، شرکتی که Go را به دنیا آورد، سابقه‌ای در به‌کارگیری نظریه‌ها و white paperهای علوم کامپیوتر دارد، پس جای تعجب نیست که Go چند ایده از academia را در خود دارد. آنچه شگفت‌انگیز است، میزان پیچیدگی پشت هر goroutine است. Go کار فوق‌العاده‌ای در به‌کارگیری ایده‌های قدرتمندی کرده که برنامهٔ شما را performant‌تر می‌کند، اما این جزئیات را abstract کرده و facade بسیار ساده‌ای برای developerها ارائه داده است.

Work Stealing

همان‌طور که در بخش‌های «این چطور به شما کمک می‌کند» در صفحهٔ ۲۹ و «Goroutineها» در صفحهٔ ۳۷ بحث کردیم، Go multiplex کردن goroutineها روی OS threadها را برای شما انجام می‌دهد. الگوریتمی که برای این کار استفاده می‌کند به‌نام استراتژی work stealing شناخته می‌شود. این یعنی چه؟

ابتدا بیایید به استراتژی ساده‌ای برای اشتراک‌گذاری کار بین چند processor نگاه کنیم، چیزی به‌نام fair scheduling. در تلاش برای اطمینان از استفادهٔ یکسان همهٔ processorها، می‌توانستیم بار را به‌طور مساوی بین همهٔ processorهای موجود توزیع کنیم. تصور کنید n processor و x task برای انجام داریم. در استراتژی fair scheduling، هر processor مقدار x/n task را می‌گرفت:

<Schedule Task 1>
<Schedule Task 2>
<Schedule Task 3>
<Schedule Task 4>

متأسفانه مشکلاتی با این رویکرد وجود دارد. اگر از بخش «Goroutineها» در صفحهٔ ۳۷ به یاد آورید، Go concurrency را با مدل fork-join مدل می‌کند. در paradigm fork-join، taskها احتمالاً به یکدیگر وابسته‌اند و معلوم می‌شود تقسیم سادهٔ آن‌ها بین processorها احتمالاً باعث می‌شود یکی از processorها کم‌استفاده بماند. نه‌تنها این، بلکه می‌تواند به cache locality ضعیف هم منجر شود چون taskهایی که به همان داده نیاز دارند روی processorهای دیگر schedule می‌شوند. بیایید مثالی ببینیم چرا.

برنامهٔ ساده‌ای را در نظر بگیرید که به توزیع کار قبلی منجر می‌شود. اگر task دو بیشتر از taskهای یک و سه با هم طول بکشد چه می‌شود؟

Time                                    P1            P2
                                        T1            T2
n+a                                     T3            T2
n+a+b                                   (idle)        T4

هرچقدر هم مدت زمان بین a و b باشد، processor یک idle خواهد بود.

اگر وابستگی متقابل بین taskها وجود داشته باشد — اگر taskی که به یک processor اختصاص یافته به نتیجهٔ taskی که به processor دیگر اختصاص یافته نیاز داشته باشد چه؟ مثلاً اگر task یک به task چهار وابسته بود چه می‌شد؟

Time                                      P1           P2
                                          T1           T2
n+a                                       (blocked)    T2
n+a+b                                     (blocked)    T4
n+a+b+c                                   T1           (idle)
n+a+b+c+d                                 T3           (idle)

در این سناریو، processor یک کاملاً idle است در حالی که taskهای دو و چهار محاسبه می‌شوند. در حالی که processor یک روی task یک blocked بود و processor دو مشغول task دو بود، processor یک می‌توانست روی task چهار کار کند تا خودش را unblock کند.

خب، این‌ها شبیه مشکلات پایه‌ای load-balancing به‌نظر می‌رسند که شاید یک FIFO queue کمک کند، پس بیایید آن را امتحان کنیم: work taskها در صف schedule می‌شوند و processorها وقتی ظرفیت دارند task را dequeue می‌کنند، یا روی joinها block می‌شوند. این اولین نوع الگوریتم work stealing است که نگاه می‌کنیم. آیا مشکل را حل می‌کند؟

[نمودار صف مرکزی با P1 و P2]

پاسخ شاید است. بهتر از تقسیم سادهٔ taskها بین processorهاست چون مشکل processorهای کم‌استفاده را حل می‌کند، اما اکنون ساختار دادهٔ متمرکزی معرفی کرده‌ایم که همهٔ processorها باید از آن استفاده کنند. همان‌طور که در «همگام‌سازی دسترسی به حافظه» در صفحهٔ ۸ بحث شد، می‌دانیم ورود و خروج مداوم از critical section بسیار پرهزینه است. نه‌تنها این، بلکه مشکلات cache locality ما بدتر شده: اکنون هر بار که processor بخواهد task را enqueue یا dequeue کند، صف متمرکز را در cache هر processor بارگذاری می‌کنیم. با این حال، برای عملیات coarse-grained، این می‌تواند رویکرد معتبری باشد. اما goroutineها معمولاً coarse-grained نیستند، پس صف متمرکز احتمالاً انتخاب خوبی برای الگوریتم work scheduling ما نیست.

گام بعدی که می‌توانیم برداریم، غیرمتمرکز کردن work queueهاست. می‌توانیم به هر processor thread و double-ended queue یا deque خودش را بدهیم، مثل این:

[نمودار dequeهای توزیع‌شده برای P1 و P2]

خب، مشکل ساختار دادهٔ متمرکز تحت contention بالا را حل کردیم، اما چه دربارهٔ مشکلات cache locality و استفاده از processor؟ و در این موضوع، اگر کار روی P1 شروع شود و همهٔ taskهای forkشده روی صف P1 قرار گیرند، کار چگونه به P2 می‌رسد؟ و آیا اکنون با جابه‌جایی taskها بین صف‌ها مشکل context switching نداریم؟ بیایید قوانین نحوهٔ عملکرد الگوریتم work-stealing با صف‌های توزیع‌شده را مرور کنیم.

به‌عنوان یادآوری، به یاد داشته باشید Go برای concurrency از مدل fork-join پیروی می‌کند. Forkها زمانی‌اند که goroutineها start می‌شوند و join pointها زمانی‌اند که دو یا چند goroutine از طریق channelها یا typeهای بستهٔ sync همگام می‌شوند. الگوریتم work stealing چند قانون پایه دارد. با فرض یک thread اجرا:

1. در نقطهٔ fork، taskها را به tail deque مرتبط با thread اضافه کن.
2. اگر thread idle است، کار را از head deque مرتبط با thread تصادفی دیگر steal کن.
3. در join pointی که هنوز محقق نشده (یعنی goroutineی که با آن همگام شده هنوز تمام نشده)، کار را از tail deque خود thread pop کن.
4. اگر deque thread خالی است، یا: a. در join stall کن. b. کار را از head deque مرتبط با thread تصادفی steal کن.

این کمی abstract است، پس بیایید کد واقعی ببینیم و این الگوریتم را در عمل مشاهده کنیم. برنامهٔ زیر را بگیرید که دنبالهٔ Fibonacci را به‌صورت بازگشتی محاسبه می‌کند:

var fib func(n int) <-chan int
fib = func(n int) <-chan int {
    result := make(chan int)
    go func() {
        defer close(result)
        if n <= 2 {
            result <- 1
            return
        }
        result <- <-fib(n-1) + <-fib(n-2)
    }()
    return result
}

fmt.Printf("fib(4) = %d", <-fib(4))

بیایید ببینیم این نسخه از الگوریتم work-stealing در این برنامهٔ Go چگونه عمل می‌کند. فرض کنیم این برنامه روی ماشین فرضی با دو processor تک‌هسته‌ای اجرا می‌شود. یک OS thread روی هر processor spawn می‌کنیم: T1 برای processor یک و T2 برای processor دو. هنگام مرور این مثال، برای ساختار بهتر بین T1 و T2 جابه‌جا می‌شوم. در واقعیت، هیچ‌کدام از این‌ها deterministic نیست.

پس برنامهٔ ما شروع می‌شود. در ابتدا فقط یک goroutine داریم، main goroutine، و فرض می‌کنیم روی processor یک schedule شده:

T1 call stack             T1 work deque              T2 call stack   T2 work deque
(main goroutine)

سپس به فراخوانی fib(4) می‌رسیم. این goroutine schedule می‌شود و روی tail deque کاری T1 قرار می‌گیرد و goroutine والد به پردازش ادامه می‌دهد:

T1 call stack               T1 work deque         T2 call stack        T2 work deque
(main goroutine)            fib(4)

در این نقطه، بسته به timing، یکی از دو اتفاق می‌افتد: یا T1 یا T2 goroutineی که فراخوانی fib(4) را host می‌کند را steal می‌کند. برای این مثال، برای نشان دادن واضح‌تر الگوریتم، فرض می‌کنیم T1 در steal برنده می‌شود؛ با این حال، مهم است توجه کنید هر thread می‌تواند برنده شود.

T1 call stack                               T1 work deque    T2 call stack   T2 work deque
(main goroutine) (unrealized join point)
fib(4)

fib(4) روی T1 اجرا می‌شود و — چون ترتیب عملیات برای جمع از چپ به راست است — fib(3) و سپس fib(2) را روی tail deque خود push می‌کند:

T1 call stack                               T1 work deque    T2 call stack   T2 work deque
(main goroutine) (unrealized join point)    fib(3)
fib(4)                                      fib(2)

در این نقطه، T2 هنوز idle است، پس fib(3) را از head deque کاری T1 برمی‌دارد. توجه کنید fib(2) — آخرین چیزی که fib(4) روی صف push کرد و بنابراین اولین چیزی که T1 احتمالاً باید محاسبه کند — روی T1 باقی می‌ماند. بعداً توضیح می‌دهیم چرا این مهم است.

T1 call stack                               T1 work deque    T2 call stack   T2 work deque
(main goroutine) (unrealized join point)    fib(2)           fib(3)
fib(4)

در همین حال، T1 به نقطه‌ای می‌رسد که نمی‌تواند روی fib(4) ادامه دهد چون منتظر channelهای برگشتی از fib(3) و fib(2) است. این unrealized join point در گام سوم الگوریتم ماست. به‌خاطر این، کار را از tail صف خودش pop می‌کند، اینجا fib(2):

T1 call stack                               T1 work deque    T2 call stack   T2 work deque
(main goroutine) (unrealized join point)                     fib(3)
fib(4) (unrealized join point)
fib(2)

اینجا کمی گیج‌کننده می‌شود. چون در الگوریتم بازگشتی از backtracking استفاده نمی‌کنیم، goroutine دیگری برای محاسبهٔ fib(2) schedule می‌کنیم. این goroutine جدید و جدا از آنچه تازه روی T1 schedule شد است. آنکه تازه روی T1 schedule شد بخشی از فراخوانی fib(4) بود (یعنی 4-2)؛ goroutine جدید بخشی از فراخوانی fib(3) است (یعنی 3-1). goroutineهای تازه scheduleشده از فراخوانی fib(3):

T1 call stack                                  T1 work deque     T2 call stack   T2 work deque
(main goroutine) (unrealized join point)                         fib(3)          fib(2)
fib(4) (unrealized join point)                                                   fib(1)
fib(2)

سپس T1 به base case الگوریتم بازگشتی Fibonacci (n <= 2) می‌رسد و 1 برمی‌گرداند:

T1 call stack                                  T1 work deque     T2 call stack   T2 work deque
(main goroutine) (unrealized join point)                         fib(3)          fib(2)
fib(4) (unrealized join point)                                                   fib(1)
(returns 1)

سپس T2 به unrealized join point می‌رسد و کار را از tail deque خودش pop می‌کند:

T1 call stack                              T1 work     T2 call stack              T2 work deque
                                           deque
(main goroutine) (unrealized join                      fib(3) (unrealized join    fib(2)
point)                                                 point)
fib(4) (unrealized join point)                         fib(1)
(returns 1)

اکنون T1 دوباره idle است پس کار را از head work deque کاری T2 steal می‌کند:

T1 call stack                              T1 work      T2 call stack               T2 work
                                           deque                                    deque
(main goroutine) (unrealized join                      fib(3) (unrealized join
point)                                                  point)
fib(4) (unrealized join point)                         fib(1)
fib(2)

سپس T2 دوباره به base case می‌رسد (n <= 2) و 1 برمی‌گرداند:

T1 call stack                              T1 work     T2 call stack                    T2 work
                                           deque                                        deque
(main goroutine) (unrealized join                      fib(3) (unrealized join
point)                                                 point)
fib(4) (unrealized join point)                         (returns 1)
fib(2)

سپس T1 هم به base case می‌رسد و 1 برمی‌گرداند:

T1 call stack                              T1 work      T2 call stack                   T2 work
                                           deque                                        deque
(main goroutine) (unrealized join                       fib(3) (unrealized join
point)                                                  point)
fib(4) (unrealized join point)                          (returns 1)
(returns 1)

فراخوانی fib(3) روی T2 اکنون دو realized join point دارد؛ یعنی فراخوانی‌های fib(2) و fib(1) نتایج را روی channelهایشان برگردانده‌اند و دو goroutine spawnشده به goroutine والدشان — آنکه فراخوانی fib(3) را host می‌کند — join شده‌اند. جمع را انجام می‌دهد (1+1=2) و نتیجه را روی channel برمی‌گرداند:

T1 call stack                                   T1 work deque        T2 call stack   T2 work deque
(main goroutine) (unrealized join point)                             (returns 2)
fib(4) (unrealized join point)

همان اتفاق دوباره می‌افتد: goroutineی که فراخوانی fib(4) را host می‌کند دو unrealized join point داشت: fib(3) و fib(2). join برای fib(3) را در گام قبلی تکمیل کردیم و join به fib(2) به‌عنوان آخرین taskی که T2 تکمیل کرد محقق شد. دوباره جمع انجام می‌شود (2+1=3) و نتیجه روی channel fib(4) برگردانده می‌شود:

T1 call stack                                   T1 work deque        T2 call stack   T2 work deque
(main goroutine) (unrealized join point)
(return 3)

در این نقطه، join point در main goroutine محقق شده (<-fib(4)) و main goroutine می‌تواند ادامه دهد. با چاپ نتیجه این کار را می‌کند:

T1 call stack         T1 work deque            T2 call stack   T2 work deque
(print 3)

اکنون بیایید چند ویژگی جالب این الگوریتم را بررسی کنیم. به یاد آورید thread اجرا هم به tail deque کاری خود push می‌کند و (در صورت لزوم) pop می‌کند. کاری که روی tail deque آن قرار دارد چند ویژگی جالب دارد:

• احتمالاً کاری است که برای تکمیل join والد لازم است. تکمیل سریع‌تر joinها یعنی برنامهٔ شما احتمالاً بهتر perform می‌کند و چیزهای کمتری در حافظه نگه می‌دارد.
• احتمالاً هنوز در cache processor ماست. چون کاری است که thread قبل از کار فعلی‌اش روی آن کار می‌کرد، احتمالاً این اطلاعات در cache CPUای که thread روی آن اجرا می‌شود باقی مانده. این یعنی cache miss کمتر!

به‌طور کلی، schedule کردن کار به این شکل مزایای عملکردی ضمنی زیادی دارد.

Stealing Taskها یا Continuationها؟

یک چیزی که تا حدی از آن گذشتیم این سؤال است که چه کاری را enqueue و steal می‌کنیم. در paradigm fork-join، دو گزینه وجود دارد: taskها و continuationها. برای اطمینان از درک روشن taskها و continuationها در Go، دوباره به برنامهٔ Fibonacci نگاه کنیم:

var fib func(n int) <-chan int
fib = func(n int) <-chan int {
    result := make(chan int)
    go func() {
        defer close(result)
        if n <= 2 {
            result <- 1
            return
        }
        result <- <-fib(n-1) + <-fib(n-2)
    }()
    return result
}

fmt.Printf("fib(4) = %d", <-fib(4))

در Go، goroutineها task هستند.

همه‌چیز بعد از فراخوانی goroutine، continuation است.

در مرور قبلی الگوریتم work-stealing با صف توزیع‌شده، taskها یا goroutineها را enqueue می‌کردیم. چون goroutine تابع‌هایی را host می‌کند که بدنهٔ کار را به‌خوبی encapsulate می‌کنند، این روش طبیعی فکر کردن است؛ با این حال، الگوریتم work-stealing Go واقعاً این‌طور کار نمی‌کند. الگوریتم work-stealing Go continuationها را enqueue و steal می‌کند.

پس چرا مهم است؟ enqueue و steal کردن continuation چه کاری برای ما انجام می‌دهد که enqueue و steal کردن taskها نمی‌کند؟ برای شروع پاسخ، بیایید به join pointهایمان نگاه کنیم.

در الگوریتم ما، وقتی thread اجرا به unrealized join point می‌رسد، باید اجرا را متوقف کند و به دنبال task برای steal بگردد. این stalling join نامیده می‌شود چون در join stall می‌کند در حالی که به دنبال کار می‌گردد. هر دو الگوریتم task-stealing و continuation-stealing stalling join دارند، اما تفاوت قابل‌توجهی در میزان رخ دادن stallها وجود دارد.

این را در نظر بگیرید: هنگام ساخت goroutine، احتمالاً برنامهٔ شما می‌خواهد تابع داخل آن goroutine اجرا شود. همچنین منطقی است که continuation از آن goroutine در نقطه‌ای بخواهد با آن goroutine join کند. و غیرمعمول نیست که continuation قبل از اتمام goroutine تلاش join کند. با این axiomها، هنگام schedule کردن goroutine، منطقی است فوراً روی آن کار شروع کنیم.

اکنون به ویژگی‌های thread که کار را به tail deque خود push و pop می‌کند و threadهای دیگر از head pop می‌کنند فکر کنید. اگر continuation را روی tail deque push کنیم، کمترین احتمال را دارد thread دیگری که از head چیزها pop می‌کند آن را steal کند، و بنابراین بسیار محتمل است وقتی goroutine را تمام کردیم دوباره آن را برداریم و از stall جلوگیری کنیم. این همچنین باعث می‌شود task forkشده شبیه function call به‌نظر برسد: thread به اجرای goroutine می‌پرد و پس از اتمام به continuation برمی‌گردد.

بیایید continuation-stealing را روی برنامهٔ Fibonacci اعمال کنیم. چون نمایش continuationها کمی کمتر از taskها واضح است، از قراردادهای زیر استفاده می‌کنیم:

• وقتی continuation روی work deque enqueue می‌شود، آن را به‌صورت cont. of X فهرست می‌کنیم.
• وقتی continuation برای اجرا dequeue می‌شود، به‌طور ضمنی continuation را به فراخوانی بعدی fib تبدیل می‌کنیم.

آنچه می‌آید نمایش نزدیک‌تری از کاری است که runtime Go انجام می‌دهد.

دوباره با main goroutine شروع می‌کنیم:

T1 call stack    T1 work deque       T2 call stack    T2 work deque
main

main goroutine fib(4) را فراخوانی می‌کند و continuation این فراخوانی روی tail work deque کاری T1 enqueue می‌شود:

T1 call stack         T1 work deque               T2 call stack              T2 work deque
fib(4)                cont. of main

T2 idle است پس continuation main را steal می‌کند:

T1 call stack         T1 work deque              T2 call stack               T2 work deque
fib(4)                                           cont. of main

فراخوانی fib(4) سپس fib(3) را schedule می‌کند که فوراً اجرا می‌شود و T1 continuation fib(4) را روی tail deque خود push می‌کند:

T1 call stack        T1 work deque                T2 call stack              T2 work deque
fib(3)               cont. of fib(4)              cont. of main

وقتی T2 تلاش می‌کند continuation main را اجرا کند، به unrealized join point می‌رسد؛ بنابراین کار بیشتری از T1 steal می‌کند. این بار continuation فراخوانی fib(4) است:

T1 call stack   T1 work deque       T2 call stack                                 T2 work deque
fib(3)                              cont. of main (unrealized join point)
                                    cont. of fib(4)

سپس فراخوانی fib(3) روی T1 goroutine fib(2) را schedule می‌کند و فوراً اجرای آن را شروع می‌کند. continuation fib(3) روی tail work deque خود push می‌شود:

T1 call stack       T1 work deque              T2 call stack                  T2 work deque
fib(2)              cont. of fib(3)            cont. of main
                                               cont. of fib(4)

اجرای continuation fib(4) روی T2 از جایی که T1 رها کرد ادامه می‌دهد، fib(2) را schedule می‌کند، فوراً اجرای آن را شروع می‌کند و دوباره fib(4) را enqueue می‌کند:

T1 call stack   T1 work deque        T2 call stack                                T2 work deque
fib(2)          cont. of fib(3)      cont. of main (unrealized join point)        cont. of fib(4)
                                     fib(2)

سپس فراخوانی fib(2) روی T1 به base case الگوریتم بازگشتی می‌رسد و 1 برمی‌گرداند:

T1 call stack   T1 work deque      T2 call stack                           T2 work deque
(returns 1)     cont. of fib(3)    cont. of main (unrealized join point)   cont. of fib(4)
                                   fib(2)

سپس T2 هم به base case می‌رسد و 1 برمی‌گرداند:

T1 call stack   T1 work deque      T2 call stack                           T2 work deque
(returns 1)     cont. of fib(3)    cont. of main (unrealized join point)   cont. of fib(4)
                                   (returns 1)

سپس T1 از صف خودش کار steal می‌کند و fib(1) را اجرا می‌کند. توجه کنید زنجیرهٔ فراخوانی روی T1 این بود: fib(3) → fib(2) → fib(1). این همان مزیت continuation stealing است که قبلاً بحث کردیم!

T1 call stack   T1 work deque     T2 call stack                            T2 work deque
fib(1)                            cont. of main (unrealized join point)    cont. of fib(4)
                                  (returns 1)

سپس T2 در انتهای continuation fib(4) است، اما فقط یک join point محقق شده: fib(2). فراخوانی fib(3) هنوز توسط T1 پردازش می‌شود. T2 idle می‌ماند چون کاری برای steal نیست:

T1 call stack   T1 work deque     T2 call stack                             T2 work deque
fib(1)                            cont. of main (unrealized join point)
                                  fib(4) (unrealized join point)

T1 اکنون در انتهای continuation خودش، fib(3)، است و هر دو join point از fib(2) و fib(1) برآورده شده‌اند. T1 مقدار 2 را برمی‌گرداند:

T1 call stack   T1 work deque     T2 call stack                             T2 work deque
(returns 2)                       cont. of main (unrealized join point)
                                  (returns 2)

اکنون هر دو join point برای fib(4)، fib(3) و fib(2) برآورده شده‌اند. T2 می‌تواند محاسبه را انجام دهد و نتایج را برگرداند (2+1=3):

T1 call stack        T1 work deque     T2 call stack                                   T2 work deque
                                       cont. of main (unrealized join point)
                                       (returns 3)

سرانجام، join point main goroutine محقق شده و مقدار فراخوانی fib(4) را دریافت می‌کند و می‌تواند نتیجه 3 را چاپ کند:

T1 call stack            T1 work deque               T2 call stack             T2 work deque
                                                     main (prints 3)

وقتی این را مرور کردیم، به‌طور مختصر دیدیم continuationها چگونه به اجرای سریالی روی T1 کمک کردند. اگر آمار این اجرا (با continuation stealing) را با اجرای task stealing مقایسه کنیم، تصویر واضح‌تری از مزایا ظاهر می‌شود:

آمار	Continuation stealing	Task stealing
# Steps	14	15
Max Deque Length	2	2
# Stalled Joins	2 (همه روی threadهای idle)	3 (همه روی threadهای busy)
Size of call stack	2	3

این آمارها شاید نزدیک به‌نظر برسند، اما اگر به برنامه‌های بزرگ‌تر extrapolate کنیم می‌توانیم ببینیم continuation stealing چگونه می‌تواند سود قابل‌توجهی داشته باشد.

بیایید هم ببینیم اجرای این با تنها یک thread اجرا چگونه است:

T1 call stack                                   T1 work deque
main

T1 call stack                                   T1 work deque
fib(4)                                          main

T1 call stack                                 T1 work deque
fib(3)                                        main
                                              cont. of fib(4)

T1 call stack                 T1 work deque
fib(2)                        main
                              cont. of fib(4)
                              cont. of fib(3)

T1 call stack                 T1 work deque
(returns 1)                   main
                              cont. of fib(4)
                              cont. of fib(3)

T1 call stack                 T1 work deque
fib(1)                        main
                              cont. of fib(4)

T1 call stack                 T1 work deque
(returns 1)                   main
                              cont. of fib(4)

T1 call stack                 T1 work deque
(returns 2)                   main
                              cont. of fib(4)

T1 call stack                   T1 work deque
fib(2)                          main

T1 call stack                   T1 work deque
(return 1)                      main

T1 call stack                   T1 work deque
(return 3)                      main

T1 call stack                    T1 work deque
main (print 3)

جالب است! runtime روی یک thread با استفاده از goroutineها همان است که اگر فقط از functionها استفاده کرده بودیم! این مزیت دیگری از continuation stealing است.

با در نظر گرفتن همهٔ موارد، steal کردن continuation از نظر نظری برتر از steal کردن taskها در نظر گرفته می‌شود و بنابراین بهتر است continuation را در صف قرار دهیم نه goroutine را. همان‌طور که از جدول زیر می‌بینید، steal کردن continuation چند مزیت دارد:

	Continuation	Child
Queue Size	Bounded	Unbounded
Order of Execution	Serial	Out of Order
Join Point	Nonstalling	Stalling

پس چرا همهٔ الگوریتم‌های work-stealing continuation stealing را پیاده‌سازی نمی‌کنند؟ خب، continuation stealing معمولاً به پشتیبانی کامپایلر نیاز دارد. خوشبختانه Go کامپایلر خودش را دارد و continuation stealing نحوهٔ پیاده‌سازی الگوریتم work-stealing Go است. زبان‌هایی که این مزیت را ندارند معمولاً task stealing یا به‌اصطلاح «child» stealing را به‌عنوان library پیاده‌سازی می‌کنند.

در حالی که این مدل به الگوریتم Go نزدیک‌تر است، هنوز کل تصویر را نشان نمی‌دهد. Go بهینه‌سازی‌های اضافی انجام می‌دهد. پیش از تحلیل آن‌ها، بیایید با شروع به استفاده از nomenclature scheduler Go همان‌طور که در source code آمده، زمینه را آماده کنیم.

scheduler Go سه مفهوم اصلی دارد:

• G — یک goroutine.
• M — یک OS thread (در source code به‌عنوان machine هم نامیده می‌شود).
• P — یک context (در source code به‌عنوان processor هم نامیده می‌شود).

در بحث work stealing، M معادل T است و P معادل work deque (تغییر GOMAXPROCS تعداد این‌ها را تغییر می‌دهد). G یک goroutine است، اما به یاد داشته باشید وضعیت فعلی goroutine را نشان می‌دهد، به‌ویژه program counter (PC) آن. این به G اجازه می‌دهد continuation را نشان دهد تا Go بتواند continuation stealing انجام دهد.

در runtime Go، Mها start می‌شوند که سپس Pها را host می‌کنند که سپس Gها را schedule و host می‌کنند:

[نمودار: M → P → G]

شخصاً وقتی فقط از این notation استفاده می‌شود، دنبال کردن تحلیل نحوهٔ کار این الگوریتم برایم دشوار است، پس در این تحلیل از نام‌های کامل استفاده می‌کنم. خب، حالا که اصطلاحات را داریم، بیایید ببینیم scheduler Go چگونه کار می‌کند!

همان‌طور که گفتیم، تنظیم GOMAXPROCS کنترل می‌کند چند context برای استفادهٔ runtime در دسترس باشد. تنظیم پیش‌فرض یک context به ازای هر CPU منطقی روی ماشین host است. برخلاف contextها، ممکن است OS threadها بیشتر یا کمتر از core باشند تا runtime Go در مدیریت چیزهایی مثل garbage collection و goroutineها کمک کند.

این را مطرح می‌کنم چون یک تضمین بسیار مهم در runtime وجود دارد: همیشه حداقل به اندازهٔ کافی OS thread برای host کردن هر context در دسترس خواهد بود. این به runtime اجازه می‌دهد بهینه‌سازی مهمی انجام دهد. runtime همچنین thread pool برای threadهایی که فعلاً استفاده نمی‌شوند دارد. حالا بیایید دربارهٔ آن بهینه‌سازی‌ها صحبت کنیم!

در نظر بگیرید اگر هر یک از goroutineها توسط input/output یا system call خارج از runtime Go block شوند چه می‌شود. OS threadی که goroutine را host می‌کند هم block می‌شود و نمی‌تواند پیشرفت کند یا goroutine دیگری host کند. از نظر منطقی این درست است، اما از منظر عملکرد، Go می‌تواند بیشتر کار کند تا processorهای ماشین تا حد امکان فعال بمانند.

کاری که Go در این موقعیت انجام می‌دهد جداسازی context از OS thread است تا context به OS thread دیگر unblockشده واگذار شود. این به context اجازه می‌دهد goroutineهای بیشتری schedule کند و runtime CPUهای ماشین host را فعال نگه دارد. goroutine blockشده با thread blockشده مرتبط می‌ماند.

وقتی goroutine سرانجام unblock شود، OS thread host تلاش می‌کند context را از یکی از OS threadهای دیگر steal کند تا بتواند goroutine قبلاً blockشده را ادامه دهد. با این حال، گاهی این همیشه ممکن نیست. در این حالت، thread goroutine خود را روی global context قرار می‌دهد، thread می‌خوابد و برای استفادهٔ آینده به thread pool runtime می‌رود (مثلاً اگر goroutine دوباره block شود).

global contextی که گفتیم در بحث‌های قبلی الگوریتم‌های abstract work-stealing جا نمی‌گیرد. جزئیات پیاده‌سازی است که به‌خاطر بهینه‌سازی استفاده از CPU در Go لازم شده. برای اطمینان از اینکه goroutineهای قرارگرفته در global context برای همیشه آنجا نمانند، چند گام اضافی به الگوریتم work-stealing اضافه شده. به‌طور دوره‌ای، یک context global context را بررسی می‌کند تا ببیند goroutineی آنجا هست یا نه، و وقتی صف یک context خالی است، ابتدا global context را برای steal کردن کار بررسی می‌کند قبل از بررسی contextهای OS threadهای دیگر.

علاوه بر input/output و system callها، Go اجازه می‌دهد goroutineها در هر function call preempt شوند. این با فلسفهٔ Go در ترجیح taskهای concurrent بسیار fine-grained هماهنگ است و اطمینان می‌دهد runtime بتواند کار را به‌طور کارآمد schedule کند. یک استثنای قابل‌توجه که تیم تلاش کرده حل کند، goroutineهایی است که هیچ input/output، system call یا function call انجام نمی‌دهند. در حال حاضر، این نوع goroutineها preemptable نیستند و می‌توانند مشکلات قابل‌توجهی مثل انتظار طولانی GC یا حتی deadlock ایجاد کنند. خوشبختانه، از منظر anecdotal، این اتفاق به‌ندرت رخ می‌دهد.

ارائهٔ همهٔ این‌ها به developer

اکنون که نحوهٔ کار goroutineها زیر پوست را می‌دانید، بیایید دوباره عقب بیاییم و تکرار کنیم developerها چگونه با همهٔ این‌ها interface دارند: کلیدواژهٔ go. همین!

کلمهٔ go را قبل از function یا closure بگذارید و به‌طور خودکار taskی schedule کرده‌اید که به کارآمدترین شکل برای ماشینی که روی آن اجرا می‌شود اجرا خواهد شد. به‌عنوان developer، هنوز با primitiveهای آشنایمان فکر می‌کنیم: functionها. نیازی نیست روش جدیدی از کار، ساختارهای دادهٔ پیچیده یا الگوریتم‌های scheduling را بفهمیم.

مقیاس‌پذیری، کارایی و سادگی. این چیزی است که goroutineها را این‌قدر جذاب می‌کند.

نتیجه‌گیری

اکنون کل منظر concurrency در Go را طی کرده‌ایم: از اصول اولیه، به استفادهٔ پایه، به الگوها و نحوهٔ کار runtime. صمیمانه امیدوارم این کتاب درک خوبی از concurrency در Go به شما داده باشد و در تکمیل همهٔ hackهای باشکوهتان کمک کند. متشکرم!