streamalism.org

1. סקירה כללית

במדריך זה, נסתכל על מושג של גניבת עבודה בג'אווה.

2. מהי גניבת עבודה?

גניבת עבודה הוצגה בג'אווה במטרה צמצום המחלוקת ביישומים מרובי-הברגה. זה נעשה באמצעות מסגרת המזלג / הצטרפות.

2.1. לחלק ולכבוש גישה

במסגרת המזלג / הצטרפות, בעיות או משימות מתחלקות רקורסיבית למשימות משנה. משימות המשנה נפתרות בנפרד, כאשר תוצאות המשנה משולבות ליצירת התוצאה:

פתרון תוצאה (בעיית בעיה) {אם (הבעיה קטנה) פותר ישירות את הבעיה אחרת {פיצול הבעיה לחלקים עצמאיים מזלג משימות משנה חדשות כדי לפתור כל חלק הצטרף לכל משימות המשנה היוצר תוצאה מתוצאות משנה}}

2.2. חוטי עובדים

המשימה המקולקלת נפתרת בעזרת חוטי עבודה המסופקים על ידי מאגר חוטים. לכל שרשור עובד יהיו משימות משנה שהוא אחראי עליהן. אלה מאוחסנים בתורים כפולים (דהקים).

כל חוט עובד מקבל משימות משנה מהדק שלו על ידי הצצה מתמדת של משימת משנה מעל לראש הדק. כאשר התיק של חוט העובד ריק, המשמעות היא שכל משימות המשנה הוצאו והושלמו.

בשלב זה, חוט העובד בוחר באופן אקראי חוט מאגר חוטים עמיתים ממנו הוא יכול "לגנוב" עבודה. לאחר מכן היא משתמשת בגישה הראשונה בהתחלה (FIFO) כדי לקחת משימות משנה מקצה הזנב של לוח הקורבן.

3. יישום מזלג / הצטרף למסגרת

אנו יכולים ליצור מאגר חוטים גונב עבודה באמצעות ה- ForkJoinPool כיתה או מוציאים לפועל מעמד:

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

ה מוציאים לפועל בכיתה יש עומס יתר newWorkStealingPool שיטה, אשר לוקח ארגומנט שלם המייצג את רמת מקבילות.

Executors.newWorkStealingPool הוא הפשטה של ForkJoinPool.commonPool. ההבדל היחיד הוא בכך Executors.newWorkStealingPool יוצר בריכה במצב אסינכרוני ו- ForkJoinPool.commonPool לא.

4. בריכות חוטים סינכרוניות לעומת אסינכרוניות

ForkJoinPool.commonPool משתמש בתצורת תור אחרונה, ראשונה (LIFO), ואילו Executors.newWorkStealingPool משתמש בגישה ראשונה, ראשונה (FIFO).

לדברי דאגה לאה, לגישת FIFO יתרונות אלה על פני LIFO:

• זה מפחית את הוויכוח בכך שגונבים פועלים בצד הנגדי של העגל כבעלים
• הוא מנצל את המאפיין של אלגוריתמי חלוקה − וכיבוש רקורסיביים של יצירת משימות "גדולות" מוקדם

הנקודה השנייה לעיל פירושה שאפשר לפרק עוד יותר משימה גנובה ישנה יותר על ידי חוט שגנב אותה.

בהתאם לתיעוד Java, הגדרה asyncMode ל נָכוֹן עשוי להתאים לשימוש עם משימות בסגנון אירוע שלעולם לא מצטרפות.

5. דוגמא לעבודה - מציאת מספרים ראשוניים

נשתמש בדוגמה של מציאת מספרים ראשוניים מאוסף מספרים כדי להראות את יתרונות זמן חישוב במסגרת גניבת העבודה. אנו נראה גם את ההבדלים בין שימוש בבריכות חוטים סינכרוניות ואסינכרוניות.

5.1. בעיית המספרים הראשוניים

מציאת מספרים ראשוניים מאוסף מספרים יכולה להיות תהליך יקר חישובית. זה נובע בעיקר מגודל אוסף המספרים.

ה מספרים ראשוניים הכיתה עוזרת לנו למצוא מספרים ראשוניים:

המעמד הציבורי PrimeNumbers מרחיב את RecursiveAction {private int lowerBound; פרטי int upperBound; פירוט אינטליגנטי פרטי; רשימה סופית סטטית GRANULARITIES = Arrays.asList (1, 10, 100, 1000, 10000); פרטי AtomicInteger noOfPrimeNumbers; PrimeNumbers (int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) {this.lowerBound = lowerBound; this.upperBound = upperBound; this.granularity = פירוט; this.noOfPrimeNumbers = noOfPrimeNumbers; } // בונים ושיטות אחרות פרטי רשימות משנה () {רשימת תת משימות = ArrayList חדש (); עבור (int i = 1; i <= this.upperBound / granularity; i ++) {int upper = i * granularity; int תחתון = (עליון - פירוט) + 1; subTasks.add (PrimeNumbers חדשים (תחתון, עליון, noOfPrimeNumbers)); } להחזיר משימות משנה; } @ מחשוב ריק מוגן @Override () {if (((upperBound + 1) - LowerBound)> פירוט) {ForkJoinTask.invokeAll (תת-משימות ()); } אחר {findPrimeNumbers (); }} בטל findPrimeNumbers () {for (int num = lowerBound; num <= upperBound; num ++) {if (isPrime (num)) {noOfPrimeNumbers.getAndIncrement (); }}} public int noOfPrimeNumbers () {return noOfPrimeNumbers.intValue (); }}

כמה דברים שחשוב לציין לגבי שיעור זה:

• זה מתארך רקורסיבית אקשן, המאפשר לנו ליישם את לְחַשֵׁב שיטה המשמשת במשימות מחשוב באמצעות מאגר שרשורים
• זה מפרק רקורסיבית משימות למשימות משנה המבוססות על ה- פירוט ערך
• הבונים לוקחים נמוך יותר ו עֶלִיוֹן ערכים מאוגדים השולטים בטווח המספרים שאנו רוצים לקבוע מספרים ראשוניים עבורם
• זה מאפשר לנו לקבוע מספרים ראשוניים באמצעות מאגר חוטים גונב עבודה או חוט יחיד

5.2. פתרון הבעיה מהר יותר עם בריכות הברגה

בואו נקבע מספרים ראשוניים בצורה של הברגה אחת וכן באמצעות מאגרי חוטים הגונבים עבודה.

ראשית, בוא נראה את גישה חד חוטית:

ראש הממשלה מספר ראשוני = ראשוני מספר חדש (10000); primes.findPrimeNumbers ();

ועכשיו, ה ForkJoinPool.commonPool גִישָׁה:

ראש הממשלה מספר ראשוני = ראשוני מספר חדש (10000); בריכת ForkJoinPool = ForkJoinPool.commonPool (); pool.invoke (ראשוני); pool.shutdown ();

לבסוף, נסתכל על ה- Executors.newWorkStealingPool גִישָׁה:

ראש הממשלה מספרים ראשוניים = ראשונים חדשים (10000); מקביליות int = ForkJoinPool.getCommonPoolParallelism (); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool (מקביליות); stealer.invoke (ראשוני); stealer.shutdown ();

אנו משתמשים ב- לעורר שיטת ה- ForkJoinPool בכיתה להעביר משימות למאגר החוטים. שיטה זו מתרחשת במקרים של מחלקות משנה של רקורסיבית אקשן. באמצעות רתמת ג'אווה מיקרובנק, אנו משווגים גישות שונות זו לזו מבחינת הזמן הממוצע לפעולה:

# הפעל הושלם. זמן כולל: 00:04:50 מצב מידוד Cnt ציון שגיאת יחידות PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark avgt 20 119.885 ± 9.917 ms / op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark avgt 20 119.791 ± 7.811 ms / op PrimeNumbersUnitTest.beng. ms / op

ברור ששניהם ForkJoinPool.commonPool ו Executors.newWorkStealingPool מאפשרים לנו לקבוע מספרים ראשוניים מהר יותר מאשר בגישה עם הברגה אחת.

מסגרת הבריכה מזלג / הצטרפות מאפשרת לנו לפרק את המשימה למשימות משנה. פירקנו את האוסף של 10,000 מספרים שלמים בקבוצות של 1-100, 101-200, 201-300 וכן הלאה. לאחר מכן קבענו מספרים ראשוניים עבור כל אצווה והעברנו את המספר הכולל של המספרים הראשוניים עם שלנו noOfPrimeNumbers שיטה.

5.3. גניבת עבודה לחישוב

עם מאגר חוטים סינכרוני, ForkJoinPool.commonPool מכניס חוטים לבריכה כל עוד המשימה עדיין בעיצומה.כתוצאה מכך, רמת גניבת העבודה אינה תלויה ברמת הפירוט של המשימה.

האסינכרוני Executors.newWorkStealingPoolמנוהל יותר, מה שמאפשר לרמת העבודה הגונבת להיות תלויה ברמת הפירוט של המשימה.

אנו מקבלים את רמת העבודה בגניבה באמצעות ה- getStealCount של ה ForkJoinPool מעמד:

גניבות ארוכות = forkJoinPool.getStealCount ();

קביעת ספירת גניבת העבודה ל Executors.newWorkStealingPool ו ForkJoinPool.commonPool נותן לנו התנהגות שונה:

Executors.newWorkStealingPool -> גרגיריות: [1], גניבות: [6564] גרעיניות: [10], גניבות: [572] גרוריות: [100], גניבות: [56] גרגריות: [1000], גניבות: [60] גרוריות : [10000], גניבות: [1] ForkJoinPool.commonPool -> גרגיריות: [1], גניבות: [6923] גרוריות: [10], גניבות: [7540] גרגריות: [100], גניבות: [7605] גרגריות: [1000], גניבות: [7681] גרגריות: [10000], גניבות: [7681]

כשגרגריות משתנה ממשובחת לגסה (1 עד 10,000) ל Executors.newWorkStealingPool, רמת העבודה בגניבה יורדת. לכן, ספירת הגניבות היא אחת כאשר המשימה לא מתפרקת (פירוט של 10,000).

ה ForkJoinPool.commonPool יש התנהגות אחרת. רמת הגניבה לעבודה היא תמיד גבוהה ולא מושפעת הרבה מהשינוי בגרעיניות המשימות.

מבחינה טכנית, דוגמת המספרים הראשוניים שלנו היא דוגמה שתומכת בעיבוד אסינכרוני של משימות בסגנון אירוע. הסיבה לכך היא שהיישום שלנו לא אוכף את הצטרפות התוצאות.

ניתן להביא מקרה לכך Executors.newWorkStealingPool מציע את השימוש הטוב ביותר במשאבים בפתרון הבעיה.

6. מסקנה

במאמר זה בחנו גניבת עבודה וכיצד ליישם אותה באמצעות מסגרת המזלג / הצטרפות. בדקנו גם את הדוגמאות של גניבת עבודה וכיצד היא יכולה לשפר את זמן העיבוד ואת השימוש במשאבים.

כמו תמיד, קוד המקור המלא של הדוגמה זמין ב- GitHub.