1. 项目概述与核心价值最近在整理一些老项目的代码翻出来一个十几年前用VC6.0做的双电梯调度算法模拟器。现在看这个开发环境确实有点“古董”了但当时为了完成这个课程设计可是扎扎实实研究了好一阵子。这个项目虽然工具老但里面关于调度算法的核心思想、多线程同步、以及用MFC做图形化模拟的思路放到今天依然很有嚼头。特别是对于刚接触操作系统、数据结构或者想理解实时系统调度逻辑的朋友来说自己动手实现一遍比看十遍理论都管用。简单来说这个项目就是用VC6.0这个经典的IDE配合MFCMicrosoft Foundation Classes框架模拟一个有两部电梯的楼宇环境。你需要设计一个“大脑”调度算法来指挥这两部电梯如何响应楼内不同楼层用户的上下行请求。目标很明确在有限的资源两部电梯下尽可能快地运送乘客减少他们的平均等待时间和电梯自身的空跑能耗。这听起来像是个简单的“指派”问题但一旦深入进去你会发现里面充满了权衡和策略选择比如是让一部电梯专门服务高层另一部服务低层还是让它们协同作战如何避免某部电梯“忙死”另一部“闲死”如何防止低楼层或高楼层用户的请求被无限期搁置也就是“饥饿”现象这些都是调度算法要解决的核心问题。2. 项目整体设计与思路拆解2.1 为什么选择VC6.0与MFC现在可能很多人会问为什么不用更现代的VS Code、Visual Studio 2022或者Qt这得回到项目的时代背景和教学目的。VC6.0在21世纪初是Windows平台C开发的绝对主流其附带的MFC框架提供了完整的Windows GUI应用程序开发能力。对于这个项目而言MFC有几个天然优势一是它提供了完善的文档/视图架构非常适合用来分离数据电梯状态、请求队列和显示电梯运行动画、楼层按钮二是它的消息映射机制能很自然地模拟电梯内外按钮的点击事件三是其GDI绘图功能足以绘制出电梯、楼层、运行箭头等简单的动态图形。从学习角度用VC6.0和MFC迫使你去理解Windows消息循环、GDI绘图、多线程同步如临界区、事件这些底层机制。虽然现在有更多高级框架封装了这些细节但理解它们对构建扎实的系统编程功底非常有帮助。当然如果你今天要重做这个项目我强烈建议用现代C配合Qt或甚至用C# WPF开发效率会高很多。但作为一次“考古”或深入理解原理的练习原汁原味的VC6.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 双电梯下的策略融合单电梯的策略相对单纯双电梯的复杂度是指数级上升的。你不能简单地把两个电梯独立运行上述算法。我的设计思路是引入一个集中调度器。请求分配所有楼层按钮的请求先发送到集中调度器。成本计算调度器根据当前两部电梯的位置、运行方向、轿厢内目标楼层为每个新请求计算一个“成本”。成本函数可以考虑电梯到达该请求楼层需要移动的距离、是否顺路方向一致、电梯当前负载等。动态指派将请求分配给“成本”更低的那部电梯。例如一部电梯正在5楼向上走另一部在15楼向下走。此时8楼有一个上行请求显然分配给5楼的电梯更合适。防饥饿与负载均衡在成本函数中加入“等待时间权重”。如果一个请求等待时间过长其成本会被动态调高从而促使某部电梯去响应它。同时也会监控两部电梯的负载任务队列长度避免一部过忙。实操心得成本函数的设计是核心中的核心没有标准答案。我当时的版本是成本 预估移动距离 方向不一致惩罚 * 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; // 门状态 CListElevatorRequest, ElevatorRequest m_requestList; // 本电梯的任务队列 // ... 其他成员函数如移动、开关门、更新状态等 }; // 调度器类核心 class CScheduler { private: CElevator m_elevatorA, m_elevatorB; // 两部电梯实例 CListElevatorRequest, 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 多线程与模拟时钟为了让电梯动画和调度逻辑能同时运行必须使用多线程。主线程GUI线程负责处理所有用户界面交互按钮点击、绘图。MFC的界面操作必须在主线程进行。模拟线程工作线程这是一个独立的线程它维护一个虚拟的“时钟”。在这个线程里你用一个循环每次循环代表一个时间片比如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进行绘图。绘制楼层用一个for循环画出代表楼层的横线和楼层数字。可以根据电梯当前所在楼层高亮显示。绘制电梯轿厢用Rectangle函数画出两个矩形代表两部电梯其Y坐标根据m_nCurrentFloor动态计算。可以用不同颜色区分运行绿色、停止灰色、开门黄色状态。绘制请求标记在相应的楼层线旁边用小圆圈或箭头表示该楼层有上行或下行请求。轿厢内的目标请求可以在电梯矩形内用小数字标出。绘制状态信息在窗口一侧用TextOut输出文本信息如电梯当前楼层、方向、任务队列长度、平均等待时间等。注意事项GDI绘图要处理闪烁问题。频繁的OnDraw调用会导致画面闪烁。解决方案是使用双缓冲技术先在内存设备上下文Memory DC中绘制完整图像然后一次性拷贝到屏幕DC上。可以在OnDraw开始时创建一个兼容DC和位图所有绘图操作针对这个内存DC最后用BitBlt函数快速复制。4. 详细实现步骤与核心代码剖析4.1 工程创建与界面布局创建MFC工程打开VC6.0选择File-New-Projects-MFC AppWizard (exe)。项目类型选择Single document单文档在最后一步的Base class中选择CScrollView因为楼层较多时可能需要滚动视图。设计对话框资源在资源视图中插入一个对话框作为控制面板。上面放置两个Group Box分别代表电梯A和电梯B内部放置静态文本显示其状态IDC_STATIC_ELEVATOR_A, IDC_STATIC_ELEVATOR_B。楼层选择下拉框Combo Box和“上行”、“下行”按钮用于模拟楼层外呼。电梯选择单选按钮、目标楼层下拉框和“内呼”按钮用于模拟电梯内选层。算法选择单选按钮组FIFO, SSTF, SCAN, 自定义。“开始模拟”、“暂停”、“重置”按钮。一个列表框List Box用于显示实时日志。关联变量使用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的改进版走到最远的请求层就回头而不是走到物理尽头或者预测算法根据历史数据预测高峰期楼层让电梯提前待命。实现这个项目的过程就像在设计和调试一个微型实时操作系统。你会深刻理解并发、同步、调度、状态机这些概念。尽管VC6.0已经是过去式但通过它打磨出的问题分析、系统设计和调试能力是任何时候都不过时的。最后别忘了在算法稳定后设计一些测试用例比如早高峰大量上行请求、晚高峰大量下行请求、随机请求等用统计出的平均等待时间、电梯总行程等数据量化地比较不同调度算法的优劣这才是完整的工程闭环。