کاردزدی (Work Stealing) در جاوا — از صفر تا صد

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

کار دزدی در جاوا

مفهوم کاردزدی با هدف کاهش تنازع در اپلیکیشن‌های چندنخی در جاوا معرفی شده است. این کار با استفاده از فریمورک fork/join انجام می‌یابد.

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

رویکرد حل و تقسیم

در فریمورک fork/join، مسائل یا وظایف به طور بازگشتی به وظایف فرعی تجزیه می‌شوند. این در ادامه وظایف فرعی به صورت منفرد حل شده و نتایج هر یک با هم ترکیب می‌شوند تا نتیجه نهایی را تشکیل دهند:

1Result solve(Problem problem) {
2    if (problem is small)
3        directly solve problem
4    else {
5        split problem into independent parts
6        fork new subtasks to solve each part
7        join all subtasks
8        compose result from subresults
9    }
10}

نخ‌های کارگر

وظیفه‌ای که تجزیه شده است به کمک «نخ‌های کارگر» (worker threads) حل می‌شود که از سوی «استخر نخ» (thread pool) تأمین می‌شوند. هر نخ کارگر دارای برخی وظایف فرعی است که مسئولیتشان را بر عهده گرفته است. این موارد در «صف‌های دوطرفه» (deques) ذخیره می‌شوند.

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

در این زمان، نخ کارگر به صورت تصادفی یک نخ همتا را از استخر نخ انتخاب می‌کند تا بتواند کار آن را سرقت کند. سپس از رویکرد «ورودی اول-خروجی اول» (LIFO) برای برداشتن وظایف فرعی از انتهای deque قربانی استفاده می‌کند.

پیاده‌سازی فریمورک Fork/Join

ما می‌توانیم یک استخر نخ کاردزدی با استفاده از یکی از کلاس‌های ForkJoinPool (+) یا Executors (+) بسازیم:

1ForkJoinPool commonPool = ForkJoinPool.commonPool();
2ExecutorService workStealingPool = Executors.newWorkStealingPool();

کلاس Executors یک متد OVERLOAD-شده به نام newWorkStealingPool دارد که یک آرگومان عدد صحیح می‌گیرد که نماینده سطح «موازی‌سازی» (parallelism) است.

همچنین Executors.newWorkStealingPool یک تجرید از ForkJoinPool.commonPool است. تنها تفاوت در این است که Executors.newWorkStealingPool یک استخر در حالت ناهمگام می‌سازد که ForkJoinPool.commonPool این کار را انجام نمی‌دهد.

استخر‌های نخ همگام و ناهمگام

ForkJoinPool.commonPool از یک پیکربندی صف به روش «ورودی آخر-خروجی اول» (LIFO) بهره می‌گیرد، در حالی که Executors.newWorkStealingPool از رویکرد «ورودی اول-خروجی اول» (FIFO) استفاده می‌کند.

بر اساس گزارش Doug Lea، رویکرد FIFO مزیت‌های زیر را نسبت به رویکرد LIFO دارد:

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

نکته دوم به این معنی است که امکان تجزیه بیشتر یک وظیفه سرقت شده قدیمی از سوی نخی که آن را دزدیده است، وجود دارد.

بر اساس مستندات جاوا تعیین مقدار true برای asyncMode می‌تواند برای استفاده روی وظایف به سبک رویداد که هرگز join نمی‌شوند مناسب باشد.

مثال عملی: یافتن اعداد اول

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

فیلم آموزش ساخت ربات تلگرام با جاوا Java در فرادرس

کلیک کنید

مسئله اعداد اول

یافتن اعداد اول از یک مجموعه از اعداد می‌تواند از نظر محاسباتی کار سنگینی باشد. یکی از دلایل عمده آن اندازه مجموعه اعدادی است که جستجو می‌کنیم. کلاس PrimeNumbers به یافتن اعداد اول کمک می‌کند:

1public class PrimeNumbers extends RecursiveAction {
2 
3    private int lowerBound;
4    private int upperBound;
5    private int granularity;
6    static final List<Integer> GRANULARITIES
7      = Arrays.asList(1, 10, 100, 1000, 10000);
8    private AtomicInteger noOfPrimeNumbers;
9 
10    PrimeNumbers(int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) {
11        this.lowerBound = lowerBound;
12        this.upperBound = upperBound;
13        this.granularity = granularity;
14        this.noOfPrimeNumbers = noOfPrimeNumbers;
15    }
16 
17    // other constructors and methods
18 
19    private List<PrimeNumbers> subTasks() {
20        List<PrimeNumbers> subTasks = new ArrayList<>();
21 
22        for (int i = 1; i <= this.upperBound / granularity; i++) {
23            int upper = i * granularity;
24            int lower = (upper - granularity) + 1;
25            subTasks.add(new PrimeNumbers(lower, upper, noOfPrimeNumbers));
26        }
27        return subTasks;
28    }
29 
30    @Override
31    protected void compute() {
32        if (((upperBound + 1) - lowerBound) > granularity) {
33            ForkJoinTask.invokeAll(subTasks());
34        } else {
35            findPrimeNumbers();
36        }
37    }
38 
39    void findPrimeNumbers() {
40        for (int num = lowerBound; num <= upperBound; num++) {
41            if (isPrime(num)) {
42                noOfPrimeNumbers.getAndIncrement();
43            }
44        }
45    }
46 
47    public int noOfPrimeNumbers() {
48        return noOfPrimeNumbers.intValue();
49    }
50}

چند نکته مهم وجود دارند که باید در مورد این کلاس متذکر شویم:

• این کلاس، RecursiveAction را بسط می‌دهد که به ما امکان می‌دهد تا متد compute مورد استفاده در وظایف محاسباتی را با استفاده از یک استخر نخ پیاده‌سازی کنیم.
• این کلاس به صورت بازگشتی وظایف را بر مبنای مقدار گرانولاریتی (granularity) به وظایف فرعی تجزیه می‌کند.
• سازنده‌های کلاس مقادیر کران پایین و بالایی را دریافت می‌کنند که بازه اعدادی را که می‌خواهیم اعداد اولش را مشخص کنیم تعیین می‌کند.
• این کلاس به ما امکان می‌دهد که اعداد اول را با استفاده از استخر نخ کاردزدی یا یک نخ منفرد تعیین کنیم.

حل سریع‌تر مسئله با استخر‌های نخ

در این بخش اعداد اول را به روش نخ منفرد و همچنین استفاده از استخر‌های نخ کاردزدی حل می‌کنیم. ابتدا رویکرد تک‌نخی را بررسی می‌کنیم:

1PrimeNumbers primes = new PrimeNumbers(10000);
2primes.findPrimeNumbers();

و اینک از رویکرد ForkJoinPool.commonPool استفاده می‌کنیم:

1PrimeNumbers primes = new PrimeNumbers(10000);
2ForkJoinPool pool = ForkJoinPool.commonPool();
3pool.invoke(primes);
4pool.shutdown();

در نهایت به بررسی رویکرد بهره‌گیری از Executors.newWorkStealingPool می‌پردازیم:

1PrimeNumbers primes = new PrimeNumbers(10000);
2int parallelism = ForkJoinPool.getCommonPoolParallelism();
3ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool(parallelism);
4stealer.invoke(primes);
5stealer.shutdown();

ما از متد invoke کلاس ForkJoinPool برای ارسال وظایف به استخر نخ بهره گرفته‌ایم. این متد وهله‌های کلاس‌های فرعی RecursiveAction را می‌گیرد. سپس با استفاده از Microbench Harness (+) این رویکردهای مختلف را از نظر زمان میانگین هر عملیات با هم مقایسه می‌کنیم:

1# Run complete. Total time: 00:04:50
2 
3Benchmark                                                      Mode  Cnt    Score   Error  Units
4PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark           avgt   20  119.885 ± 9.917  ms/op
5PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark  avgt   20  119.791 ± 7.811  ms/op
6PrimeNumbersUnitTest.Benchmarker.singleThread                  avgt   20  475.964 ± 7.929  ms/op

روشن است که هر دو رویکرد ForkJoinPool.commonPool و Executors.newWorkStealingPool امکان تعیین اعداد اول را به روشی سریع‌تر از رویکرد تک‌نخی به ما می‌دهند.

فریمورک استخر fork/join امکان تجزیه وظیفه را به وظایف فرعی فراهم می‌سازد. به این ترتیب مجموعه 10،000 عدد صحیح را به دسته‌های 1 تا 100، 101 تا 200، 201 تا 300 و همین طور تا آخر تجزیه می‌کنیم. سپس اعداد اول هر دسته را مشخص ساخته و تعداد کل اعداد اول را با استفاده از متد noOfPrimeNumbers به دست می‌آوریم.

کاردزدی برای محاسبه

در زمان بهره‌گیری از یک استخر نخ ناهمگام، ForkJoinPool.commonPool نخ را تا زمانی که وظیفه در حال پردازش است در یک استخر قرار می‌دهد. در نتیجه سطح کاردزدی به سطح گرانولاریتی وظیفه ربطی ندارد.

از سوی دیگر Executors.newWorkStealingPool به صورت ناهمگام مدیریت بیشتری دارد و امکان وابستگی سطح کاردزدی به سطح گرانولاریتی وظیفه را فراهم ساخته است.

ما سطح کاردزدی را با استفاده از getStealCount در کلاس ForkJoinPool به دست می‌آوریم:

1long steals = forkJoinPool.getStealCount();

تعیین تعداد کاردزدی برای Executors.newWorkStealingPool و ForkJoinPool.commonPool رفتار نامشابهی را نشان می‌دهد:

1Executors.newWorkStealingPool ->
2Granularity: [1], Steals: [6564]
3Granularity: [10], Steals: [572]
4Granularity: [100], Steals: [56]
5Granularity: [1000], Steals: [60]
6Granularity: [10000], Steals: [1]
7 
8ForkJoinPool.commonPool ->
9Granularity: [1], Steals: [6923]
10Granularity: [10], Steals: [7540]
11Granularity: [100], Steals: [7605]
12Granularity: [1000], Steals: [7681]
13Granularity: [10000], Steals: [7681]

زمانی که گرانولاریتی از کم به زیاد (از 1 به 10،000) تغییر می‌یابد، سطح کاردزدی در Executors.newWorkStealingPool کاهش می‌یابد. از این رو تعداد سرقت چیزها برابر با زمانی است که وظیفه تجزیه نشده است. اما ForkJoinPool.commonPool رفتار متفاوتی دارد. سطح کاردزدی همواره بالا است و چندان تحت تأثیر تغییر در گرانولاریتی وظیفه قرار ندارد.

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

سخن پایانی

ما در این مقاله به بررسی کاردزدی در جاوا و شیوه استفاده از آن با استفاده از فریمورک fork/join پرداختیم. همچنین مثال‌های عملی کاردزدی و شیوه بهره‌گیری از آن برای بهبود پردازش از نظر زمان و منابع را بررسی کردیم.

فیلم مجموعه آموزش جاوا Java – مقدماتی تا پیشرفته در فرادرس

کلیک کنید