12.2 מבני נתונים ללא נעילה תרגול
תרגול: מבני נתונים ללא נעילה - lock-free data structures¶
תרגיל 1 - מונה אטומי עם CAS¶
ממשו מונה אטומי (atomic counter) ללא שימוש ב-atomic_fetch_add. השתמשו רק ב-atomic_compare_exchange_weak בלולאת retry.
ממשו:
- counter_increment(counter) - הגדל ב-1.
- counter_add(counter, value) - הוסף ערך.
- counter_get(counter) - קרא את הערך הנוכחי.
צרו 8 תהליכונים שכל אחד מגדיל את המונה 100,000 פעמים. בסיום, הערך צריך להיות בדיוק 800,000.
דרישות:
- אסור להשתמש ב-mutex או ב-atomic_fetch_add.
- רק CAS בלולאה.
- קמפלו עם -latomic.
תרגיל 2 - מחסנית Treiber¶
ממשו את מחסנית Treiber המלאה (push ו-pop) ובדקו אותה עם מספר תהליכונים.
צרו 4 תהליכונים שכל אחד עושה push של 10,000 מספרים, ובו-זמנית 4 תהליכונים שעושים pop.
דרישות:
- ממשו את stack_push ו-stack_pop עם CAS.
- ספרו כמה פריטים כל תהליכון pop הוציא.
- ודאו שסך כל הפריטים שנקראו + מה שנשאר במחסנית = סך כל הפריטים שנכתבו.
- הדפיסו את התוצאות לאימות.
תרגיל 3 - תור SPSC¶
ממשו תור SPSC מבוסס ring buffer עם C11 atomics.
כתבו benchmark: יצרן אחד דוחף 10,000,000 מספרים, צרכן אחד קורא אותם. מדדו את הזמן.
דרישות:
- השתמשו ב-memory_order_acquire ו-memory_order_release בלבד (לא sequential consistency).
- גודל ring buffer: 4096.
- אם התור מלא, היצרן עושה spin-wait (נסה שוב).
- אם התור ריק, הצרכן עושה spin-wait.
- מדדו עם clock_gettime(CLOCK_MONOTONIC) והדפיסו את מספר הפעולות לשנייה.
תרגיל 4 - השוואת ביצועים: mutex מול lock-free¶
כתבו benchmark שמשווה מחסנית עם mutex למחסנית Treiber (lock-free).
התרחיש: 4 תהליכונים, כל אחד עושה 100,000 פעולות push ואז 100,000 פעולות pop.
דרישות:
- ממשו שתי גרסאות: אחת עם pthread_mutex_lock/unlock ואחת עם CAS.
- מדדו את הזמן הכולל של כל גרסה.
- הריצו כמה פעמים וחשבו ממוצע.
- כתבו הסבר קצר (בתוך הערת קוד) מה התוצאות ולמה.
תרגיל 5 - זיהוי בעיית ABA¶
כתבו תוכנית שמדגימה את בעיית ABA במחסנית Treiber.
הרעיון:
1. דחוף A, B, C למחסנית.
2. תהליכון 1 מתחיל pop - קורא top = C, next = B, ואז נעצר (סמלצו עם usleep).
3. תהליכון 2 עושה pop של C, pop של B, ואז push של C בחזרה.
4. תהליכון 1 ממשיך - ה-CAS מצליח כי top עדיין C, אבל next (שהוא B) כבר שוחרר.
דרישות:
- אל תשחררו זכרון (אל תקראו ל-free) כדי שהתוכנית לא תקרוס, רק תדפיסו מה קרה.
- הדפיסו את מצב המחסנית בכל שלב כדי לראות את הבעיה.
- כתבו הערה שמסבירה איך tagged pointers היו פותרים את הבעיה.