面试中遇到一道调度模拟题：一个双臂机器人、两个检测工位、13 片晶圆，要求模拟完整检测流程并尽量提高效率。这篇文章记录我用「离散事件仿真 + 资源状态管理」的完整思路，以及过程中踩过的死锁坑。

一、题目描述

已知条件：

• 存放站点 C：盒子里装有 13 片晶圆；
• 检测站点 P、S：相互独立，可以同时工作，检测期间不影响机器人动作；
• 一个双臂机器人（Arm1、Arm2）：两个机械臂不会同时工作，但允许两个臂同时持片，以此提高运转效率；
• 每片晶圆的流转顺序固定：C -> Arm -> P -> Arm -> S -> Arm -> C。

各动作耗时（毫秒）：

参数	含义	耗时
t1	P 站点检测	3000
t2	S 站点检测	5000
t3	任意站点取片 / 放片	1000
t4	C -> P 搬运	1000
t5	P -> S 搬运	1000
t6	S -> C 搬运	2000

要求：打印每一步的开始 / 完成时刻，模拟全部 13 片的检测过程，效率越高越好。

二、整体思路：离散事件仿真

这道题不是简单的顺序执行，因为「检测」和「机器人动作」是并行的：晶圆放在 P 上检测的 3000ms 里，机械臂完全可以去搬别的片。如果用 sleep 或者写死流程，根本没法表达这种并行关系。

所以我把整个系统抽象成离散事件仿真（Discrete Event Simulation）：

• 每个动作（取片、搬运、放片、检测）都是一个事件，带上「发生时刻 + 地点 + 动作类型 + 哪个臂 + 哪片」；
• 用一个按时间排序的小顶堆优先队列存放所有未来事件，每次弹出时刻最早的事件处理；
• 处理完一个事件，再把它的后继事件压入队列；
• 队列为空，说明所有动作结束，堆顶时刻就是总耗时。

事件结构和比较器：

// 每一片的id、要花费的时间、据点、动作、哪个臂
struct Matter
{
    int id;
    int timmer;
    char base;     // 据点
    string action; // 取片/放片/搬运/检测
    int arm;       // 哪个臂
};

// 小顶堆：时刻小的事件先处理
struct MatterCmp
{
    bool operator()(const Matter &a, const Matter &b) const
    {
        return a.timmer > b.timmer;
    };
};

priority_queue<Matter, vector<Matter>, MatterCmp> q;

三、关键设计

1. Robot 类：用 freeTime 保证「双臂串行」

题目明确两个机械臂不能同时工作。我没有给每个臂单独维护时间轴，而是在 Robot 内部维护一个 freeTime，表示机器人整体最早空闲时刻。任何动作执行时，开始时间都取 max(当前时刻, freeTime)，执行完再把 freeTime 推进到完成时刻。这样无论事件怎么入队，机械臂动作天然串行，不会出现时间重叠。

long Robot::run(long now, int cost, const string &desc)
{
    int start = max(now, freeTime);   // 机器人忙就等到空闲
    int end = start + cost;
    cout << start << "：" << desc << "开始" << endl;
    cout << end << "：" << desc << "完成" << endl;
    freeTime = end;
    return end;
}

同时用 armWafer[2] 记录两个臂各自持哪片（-1 表示空闲）。这里有个重要细节：freeArm() 查找空闲臂时会立即标记占用再返回。如果只查询不标记，连续分配两片时会选到同一个臂上（一个臂持两片），这种错误编译完全不报错，只能靠回读输出发现。

int Robot::freeArm(int wafer)
{
    if (armEmpty(0)) { armWafer[0] = wafer; return 0; }
    if (armEmpty(1)) { armWafer[1] = wafer; return 1; }
    return -1;
}

2. 工位忙闲标记：pBusy / sBusy

P、S 每个工位同一时刻最多放一片。用两个布尔值标记占用状态：

• 放片前检查，若工位有片，本动作延后 1000ms 重新入队，机械臂继续持片等待；
• 工位空闲则立即占位、放片，检测完成被取走后再释放。

if (pBusy) {
    // 工位还在检测：延后再试，臂不释放
    q.push({e.id, e.timmer + 1000, 'P', "放片", e.arm});
    continue;
}
pBusy = true;
long endTime = robot.putP(e.timmer, e.arm, e.id);

3. 核心：activeCount 限制在途片数，防止死锁

这是我在调试中体会最深的一点。

一开始没有限制，程序可能出现这样的局面：两个臂各持一片、都想放进 P，但 P 上已经有片在检测；而 P 上的片检测完想被取走，却没有空闲臂——「臂持片等工位、工位等臂取片」，互相等待，直接死锁。

解决办法是引入 activeCount，表示「已经从 C 取出、还没放回 C」的在途片数，并限制最多 2 片（等于机械臂数量）：

// 在途片数：限制最多 2 片，防止死锁
int activeCount = 0;

void assign()
{
    while (!C.empty() && activeCount < 2) // 在途满 2 片就不再放新片
    {
        Matter e = C.front();
        C.pop();
        int arm = robot.freeArm(e.id);
        if (arm != -1) {
            q.push({e.id, e.timmer, e.base, "取片", arm});
        } else {
            C.push(e);
            break;
        }
    }
}

从 C 取片时 activeCount++，放回 C 时 activeCount--。只要在途片数不超过臂数，就永远至少有周转空间，死锁被从结构上消除。

4. 每个事件点重新触发调度

assign() 不能只在程序启动时调用一次。否则机械臂放片释放后，C 队列里等着的片再也没人调度，结果 13 片只处理了 2 片——同样是编译不报错的静默 bug。

我在主循环每处理一个事件前都重新调用 assign()，只要有臂空出来，就立刻把等待的片塞进来：

while (!q.empty())
{
    assign();          // 每轮重新触发调度
    Matter e = q.top();
    q.pop();
    // ...按 base + action 分发处理
}

这正是事件驱动调度的核心：在每个「资源可能释放」或「新任务就绪」的时间点，重新尝试分配。

四、完整代码

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;

// 每一片的id，要花费的时间，据点
struct Matter
{
    int id;
    int timmer;
    char base;     // 据点
    string action; // 什么动作：取片/放片/搬运/检测完成
    int arm;       // 哪个臂
};
struct MatterCmp
{
    bool operator()(const Matter &a, const Matter &b) const
    {
        return a.timmer > b.timmer;
    }
};

class Robot
{
private:
    int armWafer[2]; // 两个臂各持哪片，-1=空闲
    long freeTime;   // 机器人最早空闲时刻
    long run(long now, int cost, const string &desc); // 通用动作执行

public:
    Robot();
    void detect(int arm);
    long takeC(long now, int arm, int wafer); // C取片
    long moveCP(long now, int arm);           // 搬运 C->P
    long putP(long now, int arm, int wafer);  // P放片
    long takeP(long now, int arm, int wafer); // P取片
    long movePS(long now, int arm);           // 搬运 P->S
    long putS(long now, int arm, int wafer);  // S放片
    long takeS(long now, int arm, int wafer); // S取片
    long moveSC(long now, int arm);           // 搬运 S->C
    long putC(long now, int arm, int wafer);  // C放片
    bool armEmpty(int arm);
    int freeArm(int wafer);
    long getFreeTime() const;
};

Robot::Robot()
{
    for (int i = 0; i < 2; i++) armWafer[i] = -1;
    freeTime = 0;
}

long Robot::run(long now, int cost, const string &desc)
{
    int start = max(now, freeTime);
    int end = start + cost;
    cout << start << "：" << desc << "开始" << endl;
    cout << end << "：" << desc << "完成" << endl;
    freeTime = end;
    return end;
}

long Robot::getFreeTime() const { return freeTime; }

long Robot::takeC(long now, int arm, int wafer)
{
    armWafer[arm] = wafer;
    return run(now, 1000, "Arm" + to_string(arm + 1) + "从C取第" + to_string(wafer) + "片");
}
long Robot::moveCP(long now, int arm)
{
    return run(now, 1000, "Arm" + to_string(arm + 1) + "搬运C->P");
}
long Robot::putP(long now, int arm, int wafer)
{
    armWafer[arm] = -1;
    long endTime = run(now, 1000, "Arm" + to_string(arm + 1) + "在P放第" + to_string(wafer) + "片");
    cout << endTime << "：第" << wafer << "片P检测开始" << endl;
    cout << endTime + 3000 << "：第" << wafer << "片P检测完成" << endl;
    return endTime;
}
long Robot::takeP(long now, int arm, int wafer)
{
    armWafer[arm] = wafer;
    return run(now, 1000, "Arm" + to_string(arm + 1) + "从P取第" + to_string(wafer) + "片");
}
long Robot::movePS(long now, int arm)
{
    return run(now, 1000, "Arm" + to_string(arm + 1) + "搬运P->S");
}
long Robot::putS(long now, int arm, int wafer)
{
    armWafer[arm] = -1;
    long endTime = run(now, 1000, "Arm" + to_string(arm + 1) + "在S放第" + to_string(wafer) + "片");
    cout << endTime << "：第" << wafer << "片S检测开始" << endl;
    cout << endTime + 5000 << "：第" << wafer << "片S检测完成" << endl;
    return endTime;
}
long Robot::takeS(long now, int arm, int wafer)
{
    armWafer[arm] = wafer;
    return run(now, 1000, "Arm" + to_string(arm + 1) + "从S取第" + to_string(wafer) + "片");
}
long Robot::moveSC(long now, int arm)
{
    return run(now, 2000, "Arm" + to_string(arm + 1) + "搬运S->C");
}
long Robot::putC(long now, int arm, int wafer)
{
    armWafer[arm] = -1;
    return run(now, 1000, "Arm" + to_string(arm + 1) + "在C放第" + to_string(wafer) + "片");
}
void Robot::detect(int arm)
{
    if (arm >= 0 && arm < 2) armWafer[arm] = -1;
}
bool Robot::armEmpty(int arm)
{
    return arm >= 0 && arm < 2 && armWafer[arm] == -1;
}
int Robot::freeArm(int wafer)
{
    if (armEmpty(0)) { armWafer[0] = wafer; return 0; }
    if (armEmpty(1)) { armWafer[1] = wafer; return 1; }
    return -1;
}

priority_queue<Matter, vector<Matter>, MatterCmp> q;
map<char, map<char, int>> jv;
queue<Matter> C;
Robot robot;

bool pBusy = false;
bool sBusy = false;
// 在途片数：最多 2 片，防止死锁
int activeCount = 0;

void assign()
{
    while (!C.empty() && activeCount < 2)
    {
        Matter e = C.front();
        C.pop();
        int arm = robot.freeArm(e.id);
        if (arm != -1)
            q.push({e.id, e.timmer, e.base, "取片", arm});
        else { C.push(e); break; }
    }
}

int main()
{
    for (int i = 1; i <= 13; i++)
        C.push({i, 0, 'C', "取片", -1});

    assign();
    while (!q.empty())
    {
        assign();
        Matter e = q.top();
        q.pop();

        if (e.base == 'C')
        {
            if (e.action == "放片") {
                robot.putC(e.timmer, e.arm, e.id);
                activeCount--;
            } else if (e.action == "取片") {
                long endTime = robot.takeC(e.timmer, e.arm, e.id);
                activeCount++;
                q.push({e.id, endTime, 'C', "搬运", e.arm});
            } else if (e.action == "搬运") {
                long endTime = robot.moveCP(e.timmer, e.arm);
                q.push({e.id, endTime, 'P', "放片", e.arm});
            }
        }
        else if (e.base == 'P')
        {
            if (e.action == "放片") {
                if (pBusy) {
                    q.push({e.id, e.timmer + 1000, 'P', "放片", e.arm});
                    continue;
                }
                pBusy = true;
                long endTime = robot.putP(e.timmer, e.arm, e.id);
                q.push({e.id, endTime, 'P', "检测", e.arm});
            } else if (e.action == "检测") {
                q.push({e.id, e.timmer + 3000, 'P', "取片", -1});
            } else if (e.action == "取片") {
                int arm = e.arm;
                if (arm == -1) arm = robot.freeArm(e.id);
                if (arm == -1) {
                    q.push({e.id, e.timmer + 1000, 'P', "取片", -1});
                    continue;
                }
                long endTime = robot.takeP(e.timmer, arm, e.id);
                pBusy = false;
                q.push({e.id, endTime, 'P', "搬运", arm});
            } else if (e.action == "搬运") {
                long endTime = robot.movePS(e.timmer, e.arm);
                q.push({e.id, endTime, 'S', "放片", e.arm});
            }
        }
        else if (e.base == 'S')
        {
            if (e.action == "放片") {
                if (sBusy) {
                    q.push({e.id, e.timmer + 1000, 'S', "放片", e.arm});
                    continue;
                }
                sBusy = true;
                long endTime = robot.putS(e.timmer, e.arm, e.id);
                q.push({e.id, endTime, 'S', "检测", e.arm});
            } else if (e.action == "检测") {
                q.push({e.id, e.timmer + 5000, 'S', "取片", -1});
            } else if (e.action == "取片") {
                int arm = e.arm;
                if (arm == -1) arm = robot.freeArm(e.id);
                if (arm == -1) {
                    q.push({e.id, e.timmer + 1000, 'S', "取片", -1});
                    continue;
                }
                long endTime = robot.takeS(e.timmer, arm, e.id);
                sBusy = false;
                q.push({e.id, endTime, 'S', "搬运", arm});
            } else if (e.action == "搬运") {
                long endTime = robot.moveSC(e.timmer, e.arm);
                q.push({e.id, endTime, 'C', "放片", e.arm});
            }
        }
    }
    return 0;
}

五、运行结果与总耗时

程序共输出 286 行调度日志，前几步如下：

0：Arm1从C取第1片开始
1000：Arm1从C取第1片完成
1000：Arm2从C取第2片开始
2000：Arm2从C取第2片完成
2000：Arm1搬运C->P开始
3000：Arm1搬运C->P完成
...
155000：Arm1在C放第8片开始
156000：Arm1在C放第8片完成

13 片晶圆全部检测完成，总耗时 156000 毫秒（156 秒）。

可以看到：Arm1 在 P、S 之间搬运的同时，Arm2 会完成取片、放片等动作，两个工位的检测也始终尽量保持在并行状态，没有出现机械臂空转等待。

六、总结

回头看，这道题的难点不在语法，而在资源状态管理：

1. 离散事件仿真用优先队列表达并行，比写死流程灵活得多；
2. 单一 freeTime 简洁地保证了双臂动作串行；
3. 资源分配要「查找 + 立即标记」一体完成，否则会重复分配；
4. 在途片数限制为资源数（2），从结构上杜绝死锁；
5. 调度函数要在每个事件点重新触发，否则释放出来的资源没人用。

这几个问题在编译期都不会报错，全是「能跑但结果不对」的静默缺陷，必须回读实际输出、确认全部任务完成和资源归属才能发现。这也提醒我：写调度类程序，多问自己一句「这个资源释放之后，谁来接手？」

---

如果这篇文章对你有帮助，欢迎点赞、收藏，也欢迎在评论区交流更优的调度方案。