补全:找出环

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

补全 find_cycle：顺着等待边走，走回走过的线程就找到环。

贯穿本节的等待图模型（判题机不靠时序，这是死锁的确定模型）：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 = {}
    for t, lk in wants.items():
        if lk in holds and holds[lk] != t:
            edges[t] = holds[lk]
    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]
        # TODO: 走回已经见过的线程，就把环截出来交回
        pass
    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))

print(",".join(find_cycle({"A": "B", "B": "A"})))

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

补全:找出环

更多题目

全部评论