首页 > 试题广场 >

死锁

[编程题]死锁
  • 热度指数：1262 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
试判断一个消息队列是否可能死锁。
消息队列的缓冲区长度为L单位，读操作为每次从缓冲区读取R单位，写操作为每次写入缓冲区W单位。
消息队列会持续进行读写操作。具体为写操作会在缓冲区还剩余大于等于W单位空间时保持进行，当缓冲区内空间小于W时，写操作停止，等待读操作进行；类似的，读操作会在缓冲区可读内容大于等于R时保持进行，当可读内容小于R时，读操作停止，等待写操作进行。读写都是原子操作。
若读写操作均无法进行，定义此时状态为死锁。
给定L,R,W，问消息队列是否可能进入死锁状态，若能，输出YES，否则输出NO

输入描述:
第1行输入N(N<=10)表示数据组数。
从第2行到第N+1行，每行三个整数L,R,W。


输出描述:
输出N行，每行输出'YES'或'NO'
示例1

输入

2
5 2 3
5 3 4

输出

NO
YES

备注:
50% L,R,W<=10^5
50% L,R,W<=10^18
算法知识视频讲解
添加回答
Python
白色纯度头像 白色纯度
我来抛砖引玉吧。
这道题目我们可以这么想，给定R和W时，能使消息不发生死锁的最小长度L应该是多少？
1. 理论上讲，死锁的情况不外乎 可读的数据量比R小，留下的缓冲区比W小，那么L为 R-1+W-1 时，是有可能发生死锁的。这似乎是个临界情况，因为只要 L大于 R-1+W-1 ，那么死锁基本不会出现。所以用 R-1+W-1 作为判定条件就可以了吗？ 显然不对，因为你根本无法保证 可读的数据量恰好就是 R-1。
2. 那么我们是否可以求出一个，在反复的读写操作中，数据量可以达到的最大长度length（长度在R以内）。在这个最大长度length的基础上，恰发生死锁，那么必有L=length+W-1.因此，恰好不发生死锁的长度就是length+W。
3. 最终问题指向了length的求解。请注意反复读写，反复的意思是什么？比如R=6，W=9，此时的length=3；R=3，W=4，此时的length=2；R=10，W=4，此时的length=8。这个过程中涉及到的思想就是辗转相除！辗转相除的目的是求最大公约数d，而本题目的不是求最大公约数d，而是求length，length=R-d。最大公约数d的本质就是，在R和W的操作中，可以抹除掉的数据量的最大数目d。那么R中留下来的一定就是length。
4. 所以L恰不发生死锁的长度就是length+W，即 R-d+W。其中的d用辗转相除法即可！
5. 留一个小问题：在（2）中为什么讨论的是R而不是W呢？欢迎大家留言讨论，过几天人多时，我再补充回复哈！ 
def is_ok(L,R,W):
    s=W+R
    d = W
    while True:
        if (d == 0):
            d = R
            break
        R = R % d
        if (R == 0):
            break
        d = d % R
    return "NO" if (L >= s-d) else "YES"
if __name__=='__main__':
    n = int(input().strip())
    for _ in range(n):
        l, r, w = list(map(int,input().split()))
        print(is_ok(l,r,w))
发表于 2019-08-20 10:48:23 回复(2)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 小米集团 模拟 搜狗 算法工程师 队列 测试工程师 2019 Java工程师
来自：搜狗2019秋招客户端...
上传者：小小
难度：
1条回答 5109浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号