Work Stealing Algorithm এর ব্যাখ্যা

Work Stealing Algorithm হলো একটি কার্যকর কনকারেন্সি মডেল, যা থ্রেডের মধ্যে কাজের ভারসাম্য (load balancing) নিশ্চিত করে। এটি বিশেষভাবে মাল্টি-প্রসেসর সিস্টেমে ব্যবহৃত হয়, যেখানে কাজগুলোকে সমানভাবে ভাগ করা এবং সুষ্ঠুভাবে সম্পন্ন করা হয়।

Work Stealing Algorithm কী?

Work Stealing Algorithm একটি পদ্ধতি যেখানে:

• প্রতিটি থ্রেড নিজের কাজের জন্য একটি পৃথক কাজের কিউ (queue) রাখে।
• যখন কোনো থ্রেড তার কিউতে কাজ খুঁজে পায় না (অর্থাৎ এটি খালি হয়ে যায়), তখন এটি অন্য থ্রেডের কিউ থেকে কাজ "চুরি" করে।

কীভাবে কাজ করে?

1. প্রাথমিক কাজ বরাদ্দ:
   • কাজগুলো (tasks) থ্রেডগুলোর মধ্যে ভাগ করা হয়, প্রতিটি থ্রেড তার নিজের কাজের কিউতে কাজ পায়।
2. স্বাধীন কাজ সম্পন্ন:
   • থ্রেডগুলো প্রথমে তাদের নিজস্ব কিউ থেকে কাজ সম্পন্ন করে।
3. কাজ চুরি:
   • যদি কোনো থ্রেডের কিউ খালি হয়ে যায়, তবে এটি অন্য একটি থ্রেডের কিউ থেকে কাজ নেয়।
   • সাধারণত, অন্য থ্রেডের কিউর শেষ থেকে (লাস্ট-ইন ফার্স্ট-আউট পদ্ধতি) কাজ চুরি করা হয়।

Java Work Stealing Framework

জাভাতে Work Stealing Algorithm সমর্থন করার জন্য ForkJoinPool ব্যবহার করা হয়। এটি Java 7 এ প্রবর্তিত হয়েছিল এবং Java 8 এর পরে parallel streams এর জন্য এটি ডিফল্ট পুল হিসেবে ব্যবহৃত হয়।

ForkJoinPool এর বৈশিষ্ট্য:

1. লক-ফ্রি ডেটা স্ট্রাকচার: এটি কাজের কিউ পরিচালনার জন্য লক-ফ্রি ডেটা স্ট্রাকচার ব্যবহার করে।
2. ডিপ কাজ ভাগাভাগি: বড় কাজগুলোকে ছোট ছোট সাবটাস্কে ভাগ করে।
3. প্যারালাল এক্সিকিউশন: মাল্টি-প্রসেসর কোরে সমানভাবে কাজ বিতরণ করে।

Work Stealing Algorithm উদাহরণ: ForkJoinPool ব্যবহার

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

public class WorkStealingExample {

    // RecursiveTask ব্যবহার করে কাজ বিভক্ত
    static class SumTask extends RecursiveTask<Integer> {
        private final int[] numbers;
        private final int start;
        private final int end;
        private static final int THRESHOLD = 10; // কাজ বিভক্ত করার থ্রেশোল্ড

        public SumTask(int[] numbers, int start, int end) {
            this.numbers = numbers;
            this.start = start;
            this.end = end;
        }

        @Override
        protected Integer compute() {
            if ((end - start) <= THRESHOLD) {
                // সরাসরি যোগফল গণনা
                int sum = 0;
                for (int i = start; i < end; i++) {
                    sum += numbers[i];
                }
                return sum;
            } else {
                // কাজ ভাগ করে দুইটি নতুন টাস্কে বিভক্ত করা
                int mid = (start + end) / 2;
                SumTask leftTask = new SumTask(numbers, start, mid);
                SumTask rightTask = new SumTask(numbers, mid, end);

                // সাবটাস্ক চালু এবং তাদের ফলাফল যোগ করা
                leftTask.fork(); // প্যারালাল এক্সিকিউশন
                int rightResult = rightTask.compute();
                int leftResult = leftTask.join();

                return leftResult + rightResult;
            }
        }
    }

    public static void main(String[] args) {
        // ডেটা ইনিশিয়ালাইজ
        int[] numbers = new int[100];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = i + 1;
        }

        // ForkJoinPool তৈরি
        ForkJoinPool forkJoinPool = new ForkJoinPool();

        // মূল টাস্ক শুরু
        SumTask task = new SumTask(numbers, 0, numbers.length);
        int result = forkJoinPool.invoke(task);

        // ফলাফল প্রদর্শন
        System.out.println("Sum of numbers: " + result);
    }
}

Work Stealing Algorithm এর উপকারিতা

1. লোড ব্যালেন্সিং: কাজ সমানভাবে ভাগ করা হয় এবং অনুপস্থিত থ্রেডকে কাজে লাগানো হয়।
2. উচ্চ পারফরম্যান্স: লক-ফ্রি অপারেশন এবং প্যারালাল এক্সিকিউশন নিশ্চিত করে।
3. স্কেলেবিলিটি: এটি মাল্টি-কোর সিস্টেমে স্কেল করে।

Work Stealing Algorithm এর সীমাবদ্ধতা

1. জটিলতা: ছোট কাজ বেশি হলে কাজ চুরির খরচ বৃদ্ধি পায়।
2. থ্রেড কনটেক্সট সুইচিং: কাজ চুরির সময় থ্রেড কনটেক্সট সুইচিং বেশি হলে পারফরম্যান্স কমে যেতে পারে।
3. মেমোরি ব্যবহার: প্রতিটি থ্রেডের জন্য পৃথক কিউ থাকার কারণে বেশি মেমোরি ব্যবহার হয়।

Work Stealing Algorithm জাভার কনকারেন্সি ব্যবস্থায় একটি অত্যন্ত কার্যকর পদ্ধতি। এটি থ্রেডগুলোর মধ্যে কাজের ভারসাম্য নিশ্চিত করে এবং মাল্টি-কোর প্রসেসরের সর্বোত্তম ব্যবহার নিশ্চিত করে। ForkJoinPool এবং parallel streams এর মাধ্যমে এই অ্যালগরিদম সহজে ব্যবহার করা যায়।