DeadlockDetector.cs
7.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Extensions.Logging;
using Rcs.Application.Services;
using Rcs.Application.Services.PathFind.Models;
namespace Rcs.Infrastructure.PathFinding.Services
{
/// <summary>
/// 死锁检测与解决服务（统一锁模式）
/// @author zzy
/// </summary>
public class DeadlockDetector
{
private readonly ILogger<DeadlockDetector> _logger;
private readonly IUnifiedTrafficControlService _unifiedTrafficControlService;
private readonly ConcurrentDictionary<Guid, RobotRuntimeState> _robotStates = new();
/// <summary>
/// 死锁检测间隔(毫秒)
/// </summary>
public int DetectionIntervalMs { get; set; } = 500;
public DeadlockDetector(ILogger<DeadlockDetector> logger, IUnifiedTrafficControlService unifiedTrafficControlService)
{
_logger = logger;
_unifiedTrafficControlService = unifiedTrafficControlService;
}
/// <summary>
/// 更新机器人状态
/// @author zzy
/// </summary>
public void UpdateRobotState(RobotRuntimeState state)
{
_robotStates[state.RobotId] = state;
}
/// <summary>
/// 移除机器人状态
/// @author zzy
/// </summary>
public void RemoveRobotState(Guid robotId)
{
_robotStates.TryRemove(robotId, out _);
}
/// <summary>
/// 检测死锁(基于等待图的环检测)
/// @author zzy
/// </summary>
public List<DeadlockInfo> DetectDeadlocks()
{
var deadlocks = new List<DeadlockInfo>();
var waitGraph = BuildWaitGraph();
var visited = new HashSet<Guid>();
var recursionStack = new HashSet<Guid>();
foreach (var robotId in waitGraph.Keys)
{
if (!visited.Contains(robotId))
{
var cycle = new List<Guid>();
if (DetectCycle(robotId, waitGraph, visited, recursionStack, cycle))
{
deadlocks.Add(new DeadlockInfo
{
DetectedAt = DateTime.Now,
InvolvedRobots = cycle.ToList(),
WaitGraph = waitGraph.Where(kv => cycle.Contains(kv.Key))
.ToDictionary(kv => kv.Key, kv => kv.Value)
});
}
}
}
return deadlocks;
}
/// <summary>
/// 解决死锁(返回需要退让的机器人)
/// @author zzy
/// </summary>
public DeadlockResolution ResolveDeadlock(DeadlockInfo deadlock)
{
var resolution = new DeadlockResolution { DeadlockInfo = deadlock };
var involvedRobots = deadlock.InvolvedRobots
.Select(id => _robotStates.TryGetValue(id, out var state) ? state : null)
.Where(s => s != null)
.ToList();
if (involvedRobots.Count < 2)
{
resolution.Success = false;
resolution.Reason = "无法获取足够的机器人状态信息";
return resolution;
}
// 选择退让机器人的优先级规则:
// 1. 任务优先级低让高
// 2. 空载让重载
// 3. 高电量让低电量
var robotToYield = involvedRobots
.OrderBy(r => r!.Priority)
.ThenBy(r => r!.IsLoaded ? 1 : 0)
.ThenByDescending(r => r!.BatteryLevel)
.First();
resolution.Success = true;
resolution.RobotToYield = robotToYield!.RobotId;
resolution.YieldReason = DetermineYieldReason(robotToYield!, involvedRobots!);
return resolution;
}
/// <summary>
/// 构建等待图（使用统一锁服务）
/// @author zzy
/// </summary>
private Dictionary<Guid, Guid> BuildWaitGraph()
{
var waitGraph = new Dictionary<Guid, Guid>();
foreach (var (robotId, state) in _robotStates)
{
// 优先使用带Code的路径信息
if (state.PlannedPathWithCode.Count > 0 && !string.IsNullOrEmpty(state.MapCode))
{
var nextNode = state.PlannedPathWithCode.FirstOrDefault();
if (nextNode == null || string.IsNullOrEmpty(nextNode.NodeCode)) continue;
// 使用统一锁服务检查节点是否被其他机器人锁定
var holder = _unifiedTrafficControlService.GetNodeLockHolderAsync(state.MapCode, nextNode.NodeCode).GetAwaiter().GetResult();
if (holder.HasValue && holder.Value != robotId)
{
waitGraph[robotId] = holder.Value;
}
}
// 回退到传统路径（如果没有带Code的路径）
else if (state.PlannedPath.Count > 0)
{
// 无法使用统一锁检查，跳过
_logger.LogDebug("机器人 {RobotId} 缺少 PlannedPathWithCode 或 MapCode，跳过死锁检测", robotId);
}
}
return waitGraph;
}
/// <summary>
/// DFS检测环
/// @author zzy
/// </summary>
private bool DetectCycle(Guid current, Dictionary<Guid, Guid> graph,
HashSet<Guid> visited, HashSet<Guid> recursionStack, List<Guid> cycle)
{
visited.Add(current);
recursionStack.Add(current);
cycle.Add(current);
if (graph.TryGetValue(current, out var next))
{
if (!visited.Contains(next))
{
if (DetectCycle(next, graph, visited, recursionStack, cycle))
return true;
}
else if (recursionStack.Contains(next))
{
// 找到环,裁剪cycle只保留环部分
var cycleStart = cycle.IndexOf(next);
if (cycleStart >= 0)
cycle.RemoveRange(0, cycleStart);
return true;
}
}
recursionStack.Remove(current);
cycle.Remove(current);
return false;
}
private string DetermineYieldReason(RobotRuntimeState yielder, List<RobotRuntimeState?> allRobots)
{
var others = allRobots.Where(r => r != null && r.RobotId != yielder.RobotId).ToList();
if (others.Any(r => r!.Priority > yielder.Priority))
return "任务优先级较低";
if (!yielder.IsLoaded && others.Any(r => r!.IsLoaded))
return "空载状态";
if (others.Any(r => r!.BatteryLevel < yielder.BatteryLevel))
return "电量较高";
return "综合评估";
}
}
}