题目描述并行计算中处理器间通过发送S和接收R消息进行通信。每条指令可以是阻塞B或非阻塞N模式。阻塞发送要求目标处理器执行匹配的接收才能完成阻塞接收要求源处理器执行匹配的发送才能完成非阻塞操作立即返回但真正完成仍需匹配操作。消息按发送顺序接收并在匹配双方均执行对应操作后在当前时间步结束时完成。一个正确的程序在所有操作包括非阻塞操作完成后终止。给定若干处理器及其指令序列需要模拟执行过程判断每个处理器是否能在有限时间内完成其全部指令若不能则找出阻止其完成的处理器集合。输入格式第一行是数据集个数TTT随后一个空行。每个数据集第一行为正整数PPP表示处理器个数。接下来PPP个处理器每个先占一行包含处理器名称单个大写字母和指令条数MMM随后MMM行指令。每条指令格式为Mode Action Target(s)其中Mode为B或NAction为S或RTarget(s)为若干目标处理器名称单个大写字母。处理器不会与自己通信且目标不重复。输出格式对于每个数据集按处理器名称字母顺序输出。若处理器完成输出X finishes at tT若未完成输出X never finishes because of Y and Z其中Y、Z等为阻止该处理器完成的处理器名称按字母顺序排列多个之间用and连接。每个数据集输出后除最后一个空一行。样例输入1 4 I 5 B S B P C N S B P C N R B B R P B R C B 2 B R I B S I P 3 N S I N R I B R I C 4 N S I B R I B S P B R I输出B finishes at t4 C never finishes because of P I never finishes because of B and C P finishes at t5题目分析本题要求模拟并行执行过程核心挑战在于阻塞与非阻塞阻塞指令会挂起处理器直到匹配完成非阻塞指令立即前进但其未完成操作仍会阻塞程序终止。多目标通信一条发送或接收指令可指定多个目标必须等待所有目标的匹配操作完成该指令才算完成。死锁检测当所有未完成处理器都因等待对方而停滞且没有新的匹配可能发生时程序进入死锁。直接枚举时间步模拟是自然的思路。每个时间步分为“执行”和“匹配”两个阶段。执行阶段让所有未阻塞且未完成的处理器执行下一条指令生成对应的通信请求匹配阶段则尝试配对同时存在的发送与接收请求。若某时间步没有执行任何新指令也没有任何匹配发生则系统死锁。还需注意非阻塞操作即使立即返回其父操作仍需收集所有目标的匹配因此也需要维护其完成状态。解题思路数据结构设计处理器信息Processor结构体包含名称、指令列表、程序计数器ip、是否阻塞blocked、未完成的父操作列表pendingOps存储父操作ID\texttt{ID}ID、是否完成finished、完成时间finishTime。指令Instruction记录模式、动作、目标列表字符数组。父操作ParentOp记录所属处理器索引、指令索引、模式、动作、目标列表、每个目标是否已匹配matchedTargets布尔数组、已匹配数、所需匹配数、是否完成。每个处理器执行一条指令即产生一个父操作。子操作队列对于每一对方向(src, dst)分别维护发送队列sendQ[src][dst]和接收队列recvQ[src][dst]队列元素为SubOp包含父操作ID\texttt{ID}ID和该子操作的目标处理器。当处理器执行发送指令时为每个目标向sendQ[src][dst]添加一个子操作执行接收指令时为每个源处理器向recvQ[src][dst]添加子操作。模拟过程初始化读取所有处理器及其指令建立名称到索引的映射。时间步循环t从111开始递增执行阶段遍历所有未完成、未阻塞且程序未结束的处理器。创建ParentOp将其ID\texttt{ID}ID加入处理器的pendingOps。根据动作S或R和目标列表向对应的sendQ或recvQ添加子操作。若指令为阻塞置blocked true否则ip。匹配阶段遍历所有26×2626×2626×26个方向。若发送队列和接收队列均非空则分别取出队首子操作并配对。对于发送子操作其目标为dst接收子操作的目标为src。调用辅助函数finishParent(parentId, target)在父操作的目标列表中标记该target为已匹配若所有目标均已匹配则标记父操作完成从所属处理器的pendingOps中移除若该处理器正阻塞在该指令上则解除阻塞并ip。完成检查遍历所有处理器若其ip等于指令总数且pendingOps为空则标记为完成记录当前时间步t。终止判断若所有处理器均完成则退出循环若本时间步既没有执行新指令也没有发生任何匹配则判定为死锁退出循环。输出按字母顺序排序处理器。已完成者输出完成时间未完成者收集其所有未完成父操作中尚未匹配的目标处理器即matchedTargets为false的目标去重后按字母顺序输出。正确性说明每个时间步的执行顺序不影响匹配的正确性因为所有新生成的请求在同一时间步内均可参与匹配消息可在发送时间步结束时被接收。阻塞指令的解除发生在匹配完成后因此解除后的处理器能在下一时间步执行新指令。死锁检测条件“无执行且无匹配”成立时系统确实不可能再产生任何新的通信请求或完成已有匹配因此程序将永远停滞。复杂度分析设处理器数为PPPP≤26P \le 26P≤26每个处理器指令数不超过100100100总指令数为O(100P)O(100P)O(100P)。每个指令的目标数最多为PPP因此总通信子操作数为O(100P2)O(100P^2)O(100P2)。时间步数受限于总操作数和死锁检测实际模拟过程中每个处理器最多执行100100100条指令且每次匹配至少完成一个子操作因此时间步数不超过O(100P2)O(100P^2)O(100P2)。每一时间步遍历PPP个处理器和26226^2262个方向故总时间复杂度为O(100P2⋅(P262))O(100P^2 \cdot (P 26^2))O(100P2⋅(P262))在给定范围P≤26P \le 26P≤26下可接受。空间复杂度为O(100P2)O(100P^2)O(100P2)用于存储父操作和子操作队列。代码实现// Parallel Deadlock// UVa ID: 611// Verdict: Accepted// Submission Date: 2026-07-05// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structInstruction{charmode,action;vectorchartargets;};structProcessor{charname;vectorInstructionprog;intip;boolblocked;vectorintpendingOps;boolfinished;intfinishTime;};structParentOp{intprocIdx,instIdx;charmode,action;vectorchartargets;vectorboolmatchedTargets;intmatchedCount,requiredCount;boolcompleted;};structSubOp{intparentId;chartargetChar;};intmain(){intdatasetCnt;string line;cindatasetCnt;getline(cin,line);for(intds0;dsdatasetCnt;ds){while(getline(cin,line)line.empty());intKstoi(line);vectorProcessorprocs;unordered_mapchar,intnameIdx;vectorParentOpparentOps;queueSubOpsendQ[26][26],recvQ[26][26];for(inti0;iK;i){while(getline(cin,line)line.empty());istringstreamiss(line);charname;intn;issnamen;Processor p;p.namename;p.ip0;p.blockedfalse;p.finishedfalse;p.finishTime0;for(intj0;jn;j){while(getline(cin,line)line.empty());istringstreamiss2(line);string modeStr,actionStr;iss2modeStractionStr;Instruction inst;inst.modemodeStr[0];inst.actionactionStr[0];chartarget;while(iss2target)inst.targets.push_back(target);p.prog.push_back(inst);}procs.push_back(p);nameIdx[name]i;}intt0;while(true){boolhasExecutedfalse,hasMatchedfalse;t;// 执行阶段for(inti0;i(int)procs.size();i){Processorpprocs[i];if(p.finished||p.blocked||p.ip(int)p.prog.size())continue;hasExecutedtrue;Instructioninstp.prog[p.ip];ParentOp op;op.procIdxi;op.instIdxp.ip;op.modeinst.mode;op.actioninst.action;op.targetsinst.targets;op.matchedTargets.assign(inst.targets.size(),false);op.matchedCount0;op.requiredCount(int)inst.targets.size();op.completedfalse;intparentId(int)parentOps.size();parentOps.push_back(op);p.pendingOps.push_back(parentId);for(chartarget:inst.targets){SubOp sub;sub.parentIdparentId;sub.targetChartarget;if(inst.actionS){sendQ[p.name-A][target-A].push(sub);}else{recvQ[target-A][p.name-A].push(sub);}}if(inst.modeB)p.blockedtrue;elsep.ip;}// 匹配阶段autofinishParent[](intpid,chartarget){ParentOpopparentOps[pid];for(intidx0;idx(int)op.targets.size();idx)if(op.targets[idx]target!op.matchedTargets[idx]){op.matchedTargets[idx]true;op.matchedCount;if(op.matchedCount!op.requiredCount||op.completed)return;op.completedtrue;Processorpprocs[op.procIdx];autopendp.pendingOps;pend.erase(remove(pend.begin(),pend.end(),pid),pend.end());if(op.modeBp.blockedp.ipop.instIdx){p.blockedfalse;p.ip;}break;}};for(intsrc0;src26;src){for(intdst0;dst26;dst){if(sendQ[src][dst].empty()||recvQ[src][dst].empty())continue;SubOp sendSubsendQ[src][dst].front();sendQ[src][dst].pop();SubOp recvSubrecvQ[src][dst].front();recvQ[src][dst].pop();hasMatchedtrue;finishParent(sendSub.parentId,(char)(Adst));finishParent(recvSub.parentId,(char)(Asrc));}}// 检查完成for(inti0;i(int)procs.size();i){Processorpprocs[i];if(!p.finishedp.ip(int)p.prog.size()p.pendingOps.empty()){p.finishedtrue;p.finishTimet;}}boolallDonetrue;for(autop:procs)if(!p.finished){allDonefalse;break;}if(allDone)break;if(!hasExecuted!hasMatched)break;}sort(procs.begin(),procs.end(),[](constProcessora,constProcessorb){returna.nameb.name;});for(autop:procs){if(p.finished){coutp.name finishes at tp.finishTime\n;}else{setcharblockers;for(intpid:p.pendingOps){ParentOpopparentOps[pid];if(op.completed)continue;for(intidx0;idx(int)op.targets.size();idx)if(!op.matchedTargets[idx])blockers.insert(op.targets[idx]);}coutp.name never finishes because of ;vectorcharvec(blockers.begin(),blockers.end());for(inti0;i(int)vec.size();i){if(i0)cout and ;coutvec[i];}cout\n;}}if(ds!datasetCnt-1)cout\n;}return0;}总结本题通过逐时间步模拟并行通信过程并结合队列匹配机制正确处理了阻塞/非阻塞、多目标通信和死锁检测。关键点在于将每条指令视为一个父操作其多个目标子操作分别入队利用队列保证消息顺序。匹配阶段遍历所有方向仅当双方队列均非空时才配对避免遗漏。死锁检测条件简单有效无新执行且无匹配。阻止者收集需排除已匹配目标仅统计尚未匹配的目标处理器。该解法在题目给定约束下运行高效代码结构清晰适合作为并行死锁模拟的参考实现。
