VC++6.0双电梯调度算法模拟器：多线程同步与MFC图形化实现

1. 项目概述与核心价值

最近在整理一些老项目的代码，翻出来一个十几年前用VC++6.0做的双电梯调度算法模拟器。现在看这个开发环境确实有点“古董”了，但当时为了完成这个课程设计，可是扎扎实实研究了好一阵子。这个项目虽然工具老，但里面关于调度算法的核心思想、多线程同步、以及用MFC做图形化模拟的思路，放到今天依然很有嚼头。特别是对于刚接触操作系统、数据结构或者想理解实时系统调度逻辑的朋友来说，自己动手实现一遍，比看十遍理论都管用。

简单来说，这个项目就是用VC++6.0这个经典的IDE，配合MFC（Microsoft Foundation Classes）框架，模拟一个有两部电梯的楼宇环境。你需要设计一个“大脑”（调度算法），来指挥这两部电梯如何响应楼内不同楼层用户的上下行请求。目标很明确：在有限的资源（两部电梯）下，尽可能快地运送乘客，减少他们的平均等待时间和电梯自身的空跑能耗。这听起来像是个简单的“指派”问题，但一旦深入进去，你会发现里面充满了权衡和策略选择，比如是让一部电梯专门服务高层，另一部服务低层？还是让它们协同作战？如何避免某部电梯“忙死”，另一部“闲死”？如何防止低楼层或高楼层用户的请求被无限期搁置（也就是“饥饿”现象）？这些都是调度算法要解决的核心问题。

2. 项目整体设计与思路拆解

2.1 为什么选择VC++6.0与MFC？

现在可能很多人会问，为什么不用更现代的VS Code、Visual Studio 2022或者Qt？这得回到项目的时代背景和教学目的。VC++6.0在21世纪初是Windows平台C++开发的绝对主流，其附带的MFC框架提供了完整的Windows GUI应用程序开发能力。对于这个项目而言，MFC有几个天然优势：一是它提供了完善的文档/视图架构，非常适合用来分离数据（电梯状态、请求队列）和显示（电梯运行动画、楼层按钮）；二是它的消息映射机制，能很自然地模拟电梯内外按钮的点击事件；三是其GDI绘图功能，足以绘制出电梯、楼层、运行箭头等简单的动态图形。

从学习角度，用VC++6.0和MFC迫使你去理解Windows消息循环、GDI绘图、多线程同步（如临界区、事件）这些底层机制。虽然现在有更多高级框架封装了这些细节，但理解它们对构建扎实的系统编程功底非常有帮助。当然，如果你今天要重做这个项目，我强烈建议用现代C++配合Qt或甚至用C# WPF，开发效率会高很多。但作为一次“考古”或深入理解原理的练习，原汁原味的VC++6.0环境依然有其价值。

2.2 核心调度策略选型与权衡

调度算法是项目的灵魂。你不能让电梯像无头苍蝇一样乱跑。当时我主要研究和实现了三种经典策略，并在此基础上做了混合改进。

2.2.1 先来先服务（FIFO）这是最简单的策略。系统维护一个全局请求队列，所有楼层的上行或下行请求都按到达时间顺序排队。电梯空闲时，就取队列头的请求去执行。

• 优点：实现极其简单，绝对公平，每个请求都会按顺序被处理，不会出现“饿死”。
• 缺点：性能可能是灾难性的。想象一下，电梯在1楼接到一个去20楼的请求，正在上升途中，5楼、10楼、15楼陆续有人按了上行按钮。按照FIFO，电梯必须先把20楼的乘客送到，然后再从20楼空降到5楼去接人，这中间产生了巨大的空驶距离。平均等待时间和电梯运行距离都会很长。

2.2.2 最短寻址时间优先（SSTF）这个策略试图优化电梯的运行效率。它总是让电梯选择下一个离它当前位置最近的请求去服务。

• 优点：显著减少了电梯的空跑距离和乘客的平均等待时间。因为电梯总是在服务“顺路”的请求。
• 缺点：公平性有问题，可能导致“饥饿”。比如电梯长时间在中间楼层（如10-15楼）运行，那么极端低层（1楼）或极端高层（30楼）的请求可能永远等不到电梯，因为总有更近的中间楼层请求插入进来。

2.2.3 扫描算法（SCAN，也称电梯算法）这是最像真实电梯行为的策略。电梯沿着一个方向（比如先向上）移动，服务沿途所有同方向的请求。当这个方向没有更远的请求时，就掉头，向反方向移动并服务沿途请求。

• 优点：兼顾了效率和一定的公平性。所有楼层的请求最终都会被扫描到，避免了饥饿。运行轨迹有规律，空驶距离相对可控。
• 缺点：响应时间不均衡。比如电梯刚从1楼扫到30楼，此时在2楼新发起的上行请求，必须等电梯从30楼掉头下来才能被服务，等待时间会很长。

2.2.4 双电梯下的策略融合单电梯的策略相对单纯，双电梯的复杂度是指数级上升的。你不能简单地把两个电梯独立运行上述算法。我的设计思路是引入一个集中调度器。

1. 请求分配：所有楼层按钮的请求先发送到集中调度器。
2. 成本计算：调度器根据当前两部电梯的位置、运行方向、轿厢内目标楼层，为每个新请求计算一个“成本”。成本函数可以考虑：电梯到达该请求楼层需要移动的距离、是否顺路（方向一致）、电梯当前负载等。
3. 动态指派：将请求分配给“成本”更低的那部电梯。例如，一部电梯正在5楼向上走，另一部在15楼向下走。此时8楼有一个上行请求，显然分配给5楼的电梯更合适。
4. 防饥饿与负载均衡：在成本函数中加入“等待时间权重”。如果一个请求等待时间过长，其成本会被动态调高，从而促使某部电梯去响应它。同时，也会监控两部电梯的负载（任务队列长度），避免一部过忙。

实操心得：成本函数的设计是核心中的核心，没有标准答案。我当时的版本是：成本 = 预估移动距离 + 方向不一致惩罚 * 10 + 等待时间因子。通过调整惩罚因子，你可以在效率和公平性之间找到平衡点。这个调参过程本身就是一个很好的优化问题练习。

3. 核心模块解析与MFC实现要点

3.1 数据模型设计

首先，我们需要用数据结构清晰地刻画整个系统的状态。

// 请求结构体 struct ElevatorRequest { int floor; // 请求发出的楼层 int direction; // 请求方向：1上行，-1下行，0轿厢内目标（无方向） DWORD requestTime; // 请求产生的时间戳（用于计算等待时间） bool isInternal; // true: 轿厢内按钮，false: 楼层上下行按钮 }; // 电梯状态类 class CElevator { public: int m_nCurrentFloor; // 当前楼层 (1~n) int m_nTargetFloor; // 当前目标楼层 int m_nDirection; // 运行方向：0停止，1上行，-1下行 bool m_bDoorOpen; // 门状态 CList<ElevatorRequest, ElevatorRequest&> m_requestList; // 本电梯的任务队列 // ... 其他成员函数，如移动、开关门、更新状态等 }; // 调度器类（核心） class CScheduler { private: CElevator m_elevatorA, m_elevatorB; // 两部电梯实例 CList<ElevatorRequest, ElevatorRequest&> m_globalRequestList; // 全局未分配请求（可选） CCriticalSection m_cs; // 临界区，用于保护共享数据（多线程访问） public: void OnFloorButtonPressed(int floor, int direction); // 楼层按钮按下 void OnElevatorButtonPressed(int elevatorId, int targetFloor); // 轿厢内按钮按下 void DispatchRequests(); // 核心调度函数，定时或被事件触发 int CalculateCost(CElevator& elevator, const ElevatorRequest& req); // 成本计算 };

使用CList来管理请求队列简单直接。注意，在多线程环境下（比如GUI线程和模拟运行线程），对共享队列m_globalRequestList或电梯内部队列的访问必须用CCriticalSection进行保护，否则会出现数据竞争，导致程序崩溃或逻辑错误。

3.2 多线程与模拟时钟

为了让电梯动画和调度逻辑能同时运行，必须使用多线程。

1. 主线程（GUI线程）：负责处理所有用户界面交互（按钮点击、绘图）。MFC的界面操作必须在主线程进行。
2. 模拟线程（工作线程）：这是一个独立的线程，它维护一个虚拟的“时钟”。在这个线程里，你用一个循环，每次循环代表一个时间片（比如100毫秒模拟1秒）。在这个时间片里：
   • 调用CScheduler::DispatchRequests()，执行调度逻辑。
   • 更新每部电梯的状态：如果电梯有目标且方向确定，就朝目标移动一层（m_nCurrentFloor += m_nDirection）；如果到达目标楼层，则停靠，开门（设置m_bDoorOpen = true），等待一段时间模拟上下客，然后关门，从任务队列中移除该请求。
   • 向主线程发送自定义消息（如WM_UPDATE_UI），通知界面重绘。

创建线程可以使用MFC的AfxBeginThread函数。关键点在于线程间通信不能直接操作UI，必须通过发送消息（PostMessage）或使用线程安全的方式更新数据后触发界面更新。

3.3 图形界面（GDI绘图）

在MFC的CView派生类的OnDraw函数中，使用GDI进行绘图。

1. 绘制楼层：用一个for循环画出代表楼层的横线和楼层数字。可以根据电梯当前所在楼层高亮显示。
2. 绘制电梯轿厢：用Rectangle函数画出两个矩形代表两部电梯，其Y坐标根据m_nCurrentFloor动态计算。可以用不同颜色区分运行（绿色）、停止（灰色）、开门（黄色）状态。
3. 绘制请求标记：在相应的楼层线旁边，用小圆圈或箭头表示该楼层有上行或下行请求。轿厢内的目标请求，可以在电梯矩形内用小数字标出。
4. 绘制状态信息：在窗口一侧用TextOut输出文本信息，如电梯当前楼层、方向、任务队列长度、平均等待时间等。

注意事项：GDI绘图要处理闪烁问题。频繁的OnDraw调用会导致画面闪烁。解决方案是使用双缓冲技术：先在内存设备上下文（Memory DC）中绘制完整图像，然后一次性拷贝到屏幕DC上。可以在OnDraw开始时创建一个兼容DC和位图，所有绘图操作针对这个内存DC，最后用BitBlt函数快速复制。

4. 详细实现步骤与核心代码剖析

4.1 工程创建与界面布局

1. 创建MFC工程：打开VC++6.0，选择File->New->Projects->MFC AppWizard (exe)。项目类型选择Single document（单文档），在最后一步的Base class中选择CScrollView，因为楼层较多时可能需要滚动视图。
2. 设计对话框资源：在资源视图中插入一个对话框，作为控制面板。上面放置：
   • 两个Group Box，分别代表电梯A和电梯B，内部放置静态文本显示其状态（IDC_STATIC_ELEVATOR_A, IDC_STATIC_ELEVATOR_B）。
   • 楼层选择下拉框（Combo Box）和“上行”、“下行”按钮，用于模拟楼层外呼。
   • 电梯选择单选按钮、目标楼层下拉框和“内呼”按钮，用于模拟电梯内选层。
   • 算法选择单选按钮组（FIFO, SSTF, SCAN, 自定义）。
   • “开始模拟”、“暂停”、“重置”按钮。
   • 一个列表框（List Box）用于显示实时日志。
3. 关联变量：使用ClassWizard为对话框上的控件关联成员变量（CString,int,CListBox等），并为按钮添加消息处理函数（BN_CLICKED）。

4.2 调度器核心算法实现

以自定义成本计算调度为例，剖析DispatchRequests()和CalculateCost函数。

void CScheduler::DispatchRequests() { // 1. 获取临界区锁，安全访问共享数据 CSingleLock lock(&m_cs, TRUE); // 2. 遍历全局请求队列（或直接从事件触发） POSITION pos = m_globalRequestList.GetHeadPosition(); while (pos != NULL) { POSITION currentPos = pos; ElevatorRequest req = m_globalRequestList.GetNext(pos); // 3. 为每个请求计算两部电梯的成本 int costA = CalculateCost(m_elevatorA, req); int costB = CalculateCost(m_elevatorB, req); // 4. 分配请求给成本更低的电梯 CElevator* pAssignedElevator = NULL; if (costA <= costB) { pAssignedElevator = &m_elevatorA; } else { pAssignedElevator = &m_elevatorB; } // 5. 将请求插入到被分配电梯的队列中，并排序 // 插入策略：对于SCAN算法，需按方向插入到合适位置 InsertRequestToElevatorQueue(*pAssignedElevator, req); // 6. 从全局队列移除已分配请求 m_globalRequestList.RemoveAt(currentPos); } // 7. 为每部电梯确定下一个目标楼层（驱动电梯移动） UpdateElevatorTarget(m_elevatorA); UpdateElevatorTarget(m_elevatorB); } int CScheduler::CalculateCost(CElevator& elevator, const ElevatorRequest& req) { int distance = abs(req.floor - elevator.m_nCurrentFloor); // 方向惩罚计算 int directionPenalty = 0; if (elevator.m_nDirection != 0) { // 电梯在运行中 // 请求方向与电梯运行方向是否一致？ bool isSameDirection = (req.direction == elevator.m_nDirection) || (req.direction == 0); // 请求楼层是否在电梯运行路径的前方？ bool isOnTheWay = (elevator.m_nDirection > 0 && req.floor >= elevator.m_nCurrentFloor) || (elevator.m_nDirection < 0 && req.floor <= elevator.m_nCurrentFloor); if (!isSameDirection || !isOnTheWay) { // 方向不一致或不在路径上，需要电梯完成当前方向所有任务后掉头才能服务 // 这里估算一个大的惩罚值，例如加上电梯到当前方向最远端再掉头回来的距离 directionPenalty = EstimateTurnAroundDistance(elevator, req); } } // 等待时间因子（防饥饿） DWORD waitTime = GetCurrentSimulationTime() - req.requestTime; int waitFactor = waitTime / 1000; // 假设每等待1秒，成本增加1 // 负载均衡因子（避免一部电梯任务过多） int loadFactor = elevator.m_requestList.GetCount() * 2; // 总成本 = 距离 + 方向惩罚 * 权重 + 等待因子 + 负载因子 int totalCost = distance + directionPenalty * 10 + waitFactor + loadFactor; return totalCost; }

EstimateTurnAroundDistance函数需要估算电梯完成当前方向所有既定任务后，再移动到请求楼层所需的距离。这需要扫描电梯的当前任务队列。InsertRequestToElevatorQueue函数则根据电梯当前的调度算法（如SCAN），将新请求插入到队列的合适位置，以维持电梯的运行扫描顺序。

4.3 模拟线程与动画驱动

// 在CMyView或CMyDoc中 UINT SimulationThreadProc(LPVOID pParam) { CMyDoc* pDoc = (CMyDoc*)pParam; while (!pDoc->m_bStopSimulation) { // 1. 更新模拟时间 pDoc->m_nSimTime += TIME_SLICE; // 2. 执行调度逻辑 pDoc->GetScheduler()->DispatchRequests(); // 3. 更新每部电梯状态（移动、停靠、开关门） pDoc->UpdateElevators(); // 4. 发送消息通知主线程更新UI ::PostMessage(pDoc->GetView()->GetSafeHwnd(), WM_USER_UPDATE_UI, 0, 0); // 5. 休眠，控制模拟速度 Sleep(REAL_TIME_PER_SLICE); // 例如 Sleep(100) 让100ms模拟1秒 } return 0; } // 在UpdateElevators函数中 void CMyDoc::UpdateElevators() { CScheduler* pScheduler = GetScheduler(); CElevator& elevA = pScheduler->m_elevatorA; CElevator& elevB = pScheduler->m_elevatorB; // 更新电梯A if (elevA.m_nCurrentFloor != elevA.m_nTargetFloor) { // 移动一层 elevA.m_nCurrentFloor += elevA.m_nDirection; // 检查是否到达目标层，或途中是否有同方向请求 if (elevA.m_nCurrentFloor == elevA.m_nTargetFloor || CheckFloorForRequest(elevA, elevA.m_nCurrentFloor)) { // 停靠，开门，启动定时器模拟停靠时间 elevA.m_bDoorOpen = true; elevA.m_nStopTimer = STOP_TIME; // 从队列中移除已完成请求... } } else if (elevA.m_bDoorOpen) { // 停靠时间处理 elevA.m_nStopTimer--; if (elevA.m_nStopTimer <= 0) { elevA.m_bDoorOpen = false; // 关门后，重新确定下一个目标楼层 pScheduler->UpdateElevatorTarget(elevA); } } // 同理更新电梯B... }

5. 调试、优化与常见问题实录

5.1 多线程同步崩溃问题

这是最常遇到的坑。症状是程序运行一段时间后随机崩溃，或在调试时提示内存读写错误。

• 根因：模拟线程和主线程（或多个模拟线程）同时读写同一个数据对象，比如CList请求队列，导致其内部状态混乱。
• 解决方案：对所有共享数据的访问进行加锁。
  • 使用CCriticalSection：在CScheduler类中声明一个CCriticalSection m_cs;成员。在任何函数中，需要访问共享数据（如m_globalRequestList,m_elevatorA.m_requestList）时，先创建CSingleLock lock(&m_cs, TRUE);。TRUE表示构造函数自动加锁，函数退出时析构函数自动解锁。
  • 注意锁的粒度：锁的粒度不能太粗（长时间锁住导致性能差），也不能太细（容易死锁）。在这个项目中，通常一次调度过程（DispatchRequests）或一次状态更新（UpdateElevators）作为一个临界区是比较合适的。
  • 死锁预防：确保加锁顺序一致。如果函数A先锁m_cs1再锁m_cs2，那么函数B也应按相同顺序加锁。

5.2 界面闪烁与卡顿

• 闪烁问题：如前所述，使用双缓冲。在CView::OnDraw(CDC* pDC)中：

  CRect rect; GetClientRect(&rect); CDC memDC; CBitmap memBitmap; memDC.CreateCompatibleDC(pDC); memBitmap.CreateCompatibleBitmap(pDC, rect.Width(), rect.Height()); CBitmap* pOldBitmap = memDC.SelectObject(&memBitmap); // 用memDC进行所有绘图操作... pDC->BitBlt(0, 0, rect.Width(), rect.Height(), &memDC, 0, 0, SRCCOPY); memDC.SelectObject(pOldBitmap);

• 卡顿问题：模拟线程的循环中，如果Sleep时间太短，会导致WM_USER_UPDATE_UI消息洪水般涌向主线程，主线程忙于重绘而卡死。
  • 解决：增加模拟时间片对应的真实休眠时间。或者，不在每个时间片都强制更新UI，而是记录电梯状态是否真正发生了变化，只有变化时才PostMessage。
  • 使用Invalidate(FALSE)代替Invalidate(TRUE)：FALSE参数表示不擦除背景，可以减少闪烁。更好的方法是只无效化发生变化的区域（InvalidateRect）。

5.3 调度逻辑Bug

• 电梯“抖动”：电梯在两个楼层间来回移动，无法确定目标。这通常是因为UpdateElevatorTarget逻辑有误，或者请求队列排序逻辑在电梯方向改变时没处理好。
  • 调试：在日志中输出每次调度决策的详细信息（电梯ID、当前楼层、方向、队列内容、新目标）。观察在什么情况下目标设置错误。
  • 检查SCAN算法实现：确保当电梯到达一个方向的尽头时，能正确清空该方向请求，并反转方向。队列插入函数InsertRequestToElevatorQueue必须保证请求按未来的服务顺序排列。
• 请求被遗漏或重复服务：从全局队列移除请求后，电梯自身的队列没有正确添加，或者反之。
  • 防御性编程：在请求被服务（电梯到达楼层并开门）后，不仅从电梯队列移除，也要检查并清除对应的楼层按钮状态（如果该请求是外呼）。

5.4 性能与扩展性思考

虽然这个模拟规模不大，但良好的设计习惯很重要。

• 请求队列的数据结构：CList对于教学和小规模模拟够用，但其查找效率是O(n)。如果楼层数非常多（比如100层），频繁的成本计算和队列插入排序可能成为瓶颈。可以考虑使用优先队列（priority_queue），但需要自定义比较函数来适应不同的调度策略。
• 成本计算的优化：CalculateCost函数会被频繁调用。如果计算非常复杂，可以考虑缓存一些中间结果，或者只在电梯状态（位置、方向）发生变化时重新计算所有未分配请求的成本。
• 更复杂的策略：可以尝试实现LOOK算法（SCAN的改进版，走到最远的请求层就回头，而不是走到物理尽头），或者预测算法，根据历史数据预测高峰期楼层，让电梯提前待命。

实现这个项目的过程，就像在设计和调试一个微型实时操作系统。你会深刻理解并发、同步、调度、状态机这些概念。尽管VC++6.0已经是过去式，但通过它打磨出的问题分析、系统设计和调试能力，是任何时候都不过时的。最后，别忘了在算法稳定后，设计一些测试用例，比如早高峰大量上行请求、晚高峰大量下行请求、随机请求等，用统计出的平均等待时间、电梯总行程等数据，量化地比较不同调度算法的优劣，这才是完整的工程闭环。