基于时间戳的死锁预防机制

来自计算思维百科
跳转至: 导航搜索
基于时间戳的死锁预防机制.jpg

当多个人做一件事情时,往往因为一些原因导致大家都做不下,例如:小明要等小王交了申请表,他才交;而小王说要等小明交了申请表他才交;这时就形成死锁,两个人的表都交不上去。基于时间戳的死锁预防机制通过判断事务申请时间的先后来确定优先级,让优先级较低的事务回滚,避免死锁的发生。

基本概念

死锁就是你等我释放数据项的锁,我也等着你释放另一个数据项的锁,僵持不下,就好像堵车一样,结果导致死锁。基于时间戳的死锁预防机制其实就是利用时间戳来判断当死锁出现的时候那个事务先让步。在每次事务开始之前,会根据事务开始的时间来给一个优先级,如果你来得早,我就给你一个较高的优先级,如果你来晚了,优先级就低。那么事务有了优先级之后,预防死锁可以利用下面这个原则:

如果两个事务发生冲突,优先级高的事务会杀死优先级低的事务(让它回滚,回到事务开始的位置),否则优先级低的就等待优先级高的事务执行完毕才能获得锁。

另外这种机制还可以避免饿死。因为任何时候都存在一个优先级较高的事务,这个事务是不会回滚的,而优先级的评定是根据你申请的时间来的,后面来的事务的优先级肯定低于回滚事务的优先级,所以没有事务会一直申请而得不到锁。

应用范围

这两种机制可以应用在发生冲突时的资源分配策略。

使用方法及步骤

在分配资源的时候,如果有两个人发生了冲突,你就选一个指标来评判他们的优先级,然后根据这个资源到底紧不紧,选用其中一种机制解决问题。

应用案例

应用1-过独木桥

假设有条小河,有一条独木桥连接小河两岸。同一时刻,有两个人(A、B)都想过河,他们两人分别在河的两岸。他们都非常谦虚。A说B先过,B说A先过,结果导致谁都不愿意过河了。死锁产生。那么我们可以通过双方现在正在做的事情的重要程度来确定优先级,比方说A要去上学,B要去找朋友玩,那就让A先过,因为A的事情比较紧,B等一下就好了。

应用2-导演拍电影

拍电影除了要钱以外还要场地和演员。现在假设导演A跟一号演员签约了,他们要去北京的长城拍电影,然后恰巧导演B正在长城拍电影,他们也需要一号演员,这时候就产生死锁了。因为导演A有演员而没有场地,导演B有场地没有演员,他们产生了资源的竞争。那么怎么解决这样的问题呢?我们可以根据导演在业界的口碑来确定到底谁先拍。也就是好的导演先享用所有资源,先拍电影。这样死锁就解决了。

可以体现的计算思维

基于时间戳的死锁预防机制体现了计算思维的调度特点。当资源分配发生冲突的时候,系统按照某种规则评判优先级,把资源分配给最有需要的人。