כתיבת קוד — שיעור 39

Multithreading ב-C

כל 2 משימות הקוד שנשמרו מהשיעור מופיעות כאן, עם דרישות, דוגמאות וקוד פתיחה. אפשר לכתוב פתרון בעורך המקומי וללחוץ על „בדיקת AI” לקבלת ציון, רמזים והערות.

T3 · בינוני400 נק'~25 דק'algorithmic

זיהוי Deadlock (Circular Wait)

ממש has_deadlock(threads) שמזהה אפשרות ל-deadlock. threads היא רשימה של רצפי-נעילה (שמות מנעולים לפי סדר תפיסה בכל thread). בנה גרף מכוון: לכל שני מנעולים עוקבים a,b ב-thread הוסף קשת a→b (מחזיק a, מבקש b). קיים מעגל בגרף ⇐ Circular Wait ⇐ deadlock פוטנציאלי. החזר True/False.

דוגמאות

has_deadlock([['A','B'], ['B','A']]) → True

has_deadlock([['A','B'], ['A','B']]) → False

פתרון-ייחוס זיהוי Deadlock (Circular Wait) ›

from collections import defaultdict
def has_deadlock(threads: list) -> bool:
    g = defaultdict(set)
    for locks in threads:                        # קשת a->b: מחזיק a ומבקש b
        for a, b in zip(locks, locks[1:]): g[a].add(b)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)
    def dfs(u):
        color[u] = GRAY
        for v in g[u]:
            if color[v] == GRAY: return True     # מעגל = deadlock פוטנציאלי
            if color[v] == WHITE and dfs(v): return True
        color[u] = BLACK; return False
    return any(color[n] == WHITE and dfs(n) for n in list(g))

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T3 · בינוני300 נק'~15 דק'analysis

Race Condition — הערך המינימלי

שני threads מריצים counter += 1 מיליון פעמים כל אחד, ללא נעילה (counter מתחיל ב-0). counter += 1 אינו אטומי (קריאה-שינוי-כתיבה). מהו הערך *המינימלי* האפשרי של counter בסיום, בהינתן שזירה עוינת? הגישו מספר.

דוגמאות

(פורמט) → מספר

פתרון-ייחוס Race Condition — הערך המינימלי ›

בשזירה הגרועה ביותר כמעט כל העדכונים 'אובדים'. המינימום התיאורטי לשני threads הוא 2 (כל thread מבצע לפחות כתיבה אחת שנספרת).

הפתרון שלךהפתרון נשמר מקומית אוטומטית.