12.1 דפוסי תכנות מקבילי תרגול
תרגול: דפוסי תכנות מקבילי - concurrency patterns¶
תרגיל 1 - יצרן-צרכן בסיסי¶
ממשו תוכנית עם 3 יצרנים ו-2 צרכנים. התור המשותף בגודל 8 פריטים.
כל יצרן ייצר 20 מספרים (הid שלו כפול 1000 ועוד מספר רץ, למשל יצרן 2 ייצר: 2000, 2001, 2002, ...).
כל צרכן יקרא מספרים מהתור, יחשב את הסכום של כל המספרים שהוא צרך, ובסיום ידפיס את הסכום.
דרישות:
- השתמשו בתור מוגבל עם mutex ו-condition variables.
- סה"כ ייוצרו 60 מספרים (3 יצרנים כפול 20). הצרכנים ביחד צריכים לצרוך בדיוק 60 מספרים.
- רמז: תוכלו להשתמש ב"הודעת רעל" (poison pill) - ערך מיוחד כמו -1 שמסמן לצרכן שנגמרו הנתונים.
תרגיל 2 - בריכת תהליכונים¶
ממשו בריכת תהליכונים (thread pool) עם 4 workers. שילחו לבריכה 100 משימות, כאשר כל משימה מקבלת מספר ומחזירה את הריבוע שלו.
דרישות:
- השתמשו ב-mutex ו-condition variable לתיאום.
- כאשר אין משימות, הworkers ישנים (לא busy-wait).
- בסיום, קראו ל-threadpool_destroy שמחכה עד שכל המשימות מסתיימות ואז מכבה את הworkers.
- הדפיסו את מזהה הthread שמבצע כל משימה כדי לראות את חלוקת העבודה.
תרגיל 3 - מטמון עם reader-writer lock¶
ממשו מטמון (cache) של מחרוזות עם pthread_rwlock. המטמון תומך ב:
- cache_get(key) - קריאה (rwlock לקריאה)
- cache_set(key, value) - כתיבה (rwlock לכתיבה)
צרו 8 תהליכוני קריאה שמבצעים 1000 חיפושים אקראיים, ו-2 תהליכוני כתיבה שמכניסים 100 פריטים כל אחד.
דרישות:
- השתמשו ב-pthread_rwlock_rdlock לקריאה ו-pthread_rwlock_wrlock לכתיבה.
- מדדו את זמן הריצה (עם clock_gettime) והשוו למימוש עם mutex רגיל.
- רמז: כשרוב הפעולות הן קריאה, reader-writer lock אמור להיות מהיר יותר מ-mutex.
תרגיל 4 - חישוב מקבילי עם barrier¶
ממשו חישוב ממוצע נע (moving average) על מערך גדול בשלבים מקביליים.
נתון מערך של 10,000 מספרים. בכל שלב, כל תא מתעדכן לממוצע של עצמו ושני השכנים שלו (שמאל וימין).
דרישות:
- השתמשו ב-4 תהליכונים, כל אחד אחראי על רבע מהמערך.
- ביצוע 100 שלבים.
- השתמשו ב-pthread_barrier_wait כדי לסנכרן בין שלבים.
- חשוב: צריך שני מערכים (קלט ופלט) שמתחלפים בכל שלב, אחרת תהליכון אחד יקרא ערכים שכבר עודכנו.
תרגיל 5 - מוניטור שומר סף¶
ממשו מוניטור בשם gate_monitor שמנהל "שער":
- הפונקציה gate_pass(gate) חוסמת את התהליכון עד שהשער פתוח, ואז מעבירה אותו ומקטינה מונה.
- הפונקציה gate_open(gate, n) פותחת את השער ומאפשרת ל-n תהליכונים בדיוק לעבור, ואז סוגרת אותו שוב.
צרו 10 תהליכונים שמנסים לעבור בשער. מהthread הראשי, קראו ל-gate_open(gate, 3) כדי לשחרר 3, חכו קצת, ואז gate_open(gate, 3) שוב, וכך הלאה.
דרישות:
- כל הסנכרון חייב להיות בתוך המוניטור (mutex + condition variable).
- התהליכונים שממתינים לא עושים busy-wait.
- הדפיסו כל מעבר כדי לאמת שבדיוק n תהליכונים עוברים בכל פתיחת שער.