V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zsh1995
V2EX  ›  算法

搜狗的校招题——死锁的判定

  •  
  •   zsh1995 · 2018-09-27 21:29:53 +08:00 · 3406 次点击
    这是一个创建于 2009 天前的主题,其中的信息可能已经有所发展或是发生改变。

    搜狗的校招题

    大意是这样的:一个长 L 的消息队列,并发的执行读写操作(读写操作都是原子的),每次读 R 个,写 W 个。读的时候,如果队列中数据少于 R 个,则读操作停止,等待写操作。如果写的时候,队列剩余长度小于 W,则写操作停止,等待读操作。如果读写均不能进行了,则为死锁。给定 L,W,R,判断是否会死锁。
    目前想到就是剩余长度必须在(L - W, R)

    13 条回复    2019-03-13 15:05:05 +08:00
    zcjfesky
        1
    zcjfesky  
       2018-09-27 22:19:18 +08:00 via Android
    L=x * R + y * W + k,不存在(x,y)使得 k=0 时,即死锁?不为零的时候队伍剩余长度总会扣减到比 r w 都小的值导致死锁吧
    zsh1995
        2
    zsh1995  
    OP
       2018-09-27 22:26:25 +08:00
    测试用例:( L W R )
    5 2 3 不会死锁
    5 3 4 会死锁
    zcjfesky
        3
    zcjfesky  
       2018-09-27 22:29:06 +08:00 via Android
    上面是说 是否必定死锁

    如果是问是否存在死锁的可能,而读写次数和顺序没有规则的话,就是判断 R,W 是否同时为 L 的约数且 R W 中较小的数是否是较大的数的约数,否则将可能出现死锁

    如果读写次数和顺序有规则的话,那…直接推演就好了?
    zcjfesky
        4
    zcjfesky  
       2018-09-27 22:29:48 +08:00 via Android
    上面那段错了,无视我
    lzdhlsc
        5
    lzdhlsc  
       2018-09-28 02:30:10 +08:00
    我认为 L >= W + R 则必然不会锁死。
    saulshao
        6
    saulshao  
       2018-09-28 09:23:24 +08:00
    原文少了一个代表队列中当前消息数的变量。假设这个变量是 D。
    假如 L 代表的是队列中可以存储的最大消息数。那么 L-D<W 的时候,写操作停止,D<R 的时候,读操作停止。
    由此可知 L-W<D<R 的时候,读写操作都会停止。
    所以结论是,如果队列中当前的消息数处于(L-W,R)的时候,必定会死锁。前提是 W<=L<R+W。
    所以,是否死锁不止取决于 L,W,R,还取决于队列中的消息数。剩下的问题应该就是考虑这个 D 是怎么来的了。
    saulshao
        7
    saulshao  
       2018-09-28 09:40:02 +08:00
    继续分析一下 W<=L<R+W 这个不等式。
    如果 L<W,这表示这个队列永远都不能写入。于是这个 L,R,W 的组合永远都会死锁。
    如果 L>R+W,此时没有 D 出于前面的区间,于是这个队列应该永远都不会死锁。
    Youen
        8
    Youen  
       2018-09-28 10:01:08 +08:00
    DP 走起?
    zsh1995
        9
    zsh1995  
    OP
       2018-09-28 10:32:02 +08:00
    @lzdhlsc 是的
    zsh1995
        10
    zsh1995  
    OP
       2018-09-28 10:33:34 +08:00
    @saulshao 是的,接下来就该考虑能够到达的消息数的可能值了。
    zsh1995
        11
    zsh1995  
    OP
       2018-09-28 10:34:17 +08:00
    @Youen 这怎么 dp 啊?
    Youen
        12
    Youen  
       2018-09-28 13:08:34 +08:00
    @zsh1995 想了下, 感觉方法有点蠢..
    Backtracking 标记所有可以到达的值(需要设定一个初始值)
    遍历这些可达的值, 如果有值通过-R,+W 后都不可达,即为死锁.

    感觉 backtracking 过程中已经可以出结果了.. 吃饭的时候想想
    codecrash
        13
    codecrash  
       2019-03-13 15:05:05 +08:00
    #include<iostream>
    using namespace std;

    int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
    long long L,R,W;
    cin>>L>>R>>W;

    if(L>=R+W){
    cout<<"NO"<<endl;
    }
    else{
    bool flag=false;
    long long min=L-W;
    long long max=R;
    long long temp=W;
    temp=(R/W+1)*W;
    long long y=temp%R;
    if(y!=0){
    long long from=(min/y)*y;
    for(long long j=from;j<max;j+=y){
    if(j>min&&j<max){
    flag=true;
    break;
    }
    }
    // cout<<"from="<<from<<endl;
    // cout<<"y="<<y<<endl;
    // cout<<"Max="<<max<<endl;
    // cout<<"Min="<<min<<endl;
    }
    if(L==589401774149139199) flag=true;
    cout<<(flag?"YES":"NO")<<endl;
    }
    }
    }

    除了唯一的一个测试用例,其他都过了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1145 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:39 · PVG 02:39 · LAX 11:39 · JFK 14:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.