补全:建等待边

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 waitfor：线程想要的锁被别人占着，就连一条「等的人→被等的人」的边。

贯穿本节的等待图模型（判题机不靠时序，这是死锁的确定模型）：holds={锁: 持有它的线程}、wants={线程: 想要的锁}。想要的锁被别人占着就连一条等待边。waitfor 交回等待边 {等的人: 被等的人}，find_cycle 交回环上的线程（没环 []），deadlocked 判有没有死锁，blocked 数几个在等；victim 从环里挑一个当牺牲者、after_abort 中止它后还有没有环、cycle_len 环有多长。

提交你的答案

请登录后提交答案。

去登录

← 谁在等谁补全:判有没有死锁 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

def waitfor(holds, wants):
    # holds: {锁: 持有它的线程}; wants: {线程: 它想要的锁}
    # 建等待边：线程 T 想要的锁被 U 持着 -> T 等 U
    edges = {}
    # TODO: 谁想要的锁被别人持有，就 edges[想要的线程] = 持有者
    pass
    return edges

def find_cycle(edges):
    # 有环就交回环上的线程（按遇到顺序），没有交回 []
    for start in edges:
        seen = []
        cur = start
        while cur in edges and cur not in seen:
            seen.append(cur)
            cur = edges[cur]
        if cur in seen:
            return seen[seen.index(cur):]
    return []

def deadlocked(holds, wants):
    return bool(find_cycle(waitfor(holds, wants)))

def blocked(holds, wants):
    # 有几个线程在等锁（等待图里有出边的）
    return len(waitfor(holds, wants))

def victim(edges):
    # 恢复：从环里挑一个当牺牲者（取环上第一个），交回它的名字；没环交回 ""
    c = find_cycle(edges)
    return c[0] if c else ""

def after_abort(edges, t):
    # 中止线程 t、去掉它的等待边后，还有没有环
    e = {k: v for k, v in edges.items() if k != t}
    return bool(find_cycle(e))

def cycle_len(edges):
    # 环有多长（几个线程绕成一圈）；没环 0
    return len(find_cycle(edges))

e = waitfor({"L1": "A", "L2": "B"}, {"A": "L2", "B": "L1"})
print(",".join(k + ">" + v for k, v in sorted(e.items())))

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

补全:建等待边

更多题目

全部评论