★ FEATURED ARTICLE 离散事件模拟这道题第一次让我怀疑自己是不是没学懂操作系统。银行排队算法听起来像数学建模可实验要求偏偏用C语言写一个模拟器还要统计平均等待时间和窗口利用率。我当时对着“离散事件”四个字发了很久的呆直到把“到达”和“离开”这两种事件画在纸上才反应过来所谓模拟并不是把每一分钟都走一遍而是只关心那些让系统状态发生变化的瞬间。所以我想把这次实验的完整思路写出来里面有模型设计、数据结构选择、C语言关键代码、统计口径还有我实际踩过的几个坑。这个实验非常适合刚接触离散事件模拟的人尤其是操作系统课程里第一次写大型C程序的同学参考。1. 实验需求拆解银行排队模型里的“离散事件”到底在模拟什么1.1 离散事件模拟和时间步进模拟的本质区别很多人第一次接触“模拟”时脑子里的第一反应是“定时器驱动”让时间从0走到480分钟每过1分钟刷新一次窗口状态和队列状态。这种思路叫时间步进法实现起来确实直观但缺点也很明显如果步长取大中间发生的短事件会被漏掉如果步长取小窗口空闲时CPU也在白跑效率极低。离散事件模拟换了一个角度时间不是均匀推进的而是直接跳到下一个有意义的事件发生的时刻。两个事件之间系统状态完全不变所以不需要扫描那些空白区间。打个比方查快递记录时你不会每分钟刷新一次页面你只关心“揽收”“运输中”“派送”“签收”这些节点。事件就是这些节点中间跑了多少公里、过了多少小时对你要判断状态这件事来说没有影响。银行排队模拟也一样顾客到达、顾客服务完成这两个时刻决定了窗口忙闲和队列长度其余时间窗口不是忙着就是空着不需要逐分钟模拟。理解了这个区别后面的代码结构就顺理成章了模拟程序里永远保存一个“事件链表”每次从链表里取出时间最早的事件把当前模拟时钟拨到那个事件的时间然后修改状态再根据这次状态变化生成后续事件。循环直到事件链表为空。1.2 银行排队模型的两个顾客流到达与服务银行排队模型里有两个随机过程顾客到达过程和服务过程。顾客按一定的间隔到达银行如果窗口有空就直接办理如果所有窗口都忙就排进队列。服务时间也是随机的可能短到2分钟也可能长到15分钟。模拟器的职责就是在这两个随机过程的基础上计算出一段时间内系统的平均表现。这里有一个建模时很容易忽略的问题顾客到达后如果窗口空闲他是不是需要单独生成一个“开始服务”事件我的做法是不需要。因为“开始服务”总是在“到达事件”或“离开事件”的处理过程中立即发生的它不会让模拟时钟停留也不会让系统进入一个需要等待的中间状态。事件链表里只有两类事件就够用了到达事件顾客进入银行决定直接服务还是加入队列。离开事件顾客服务完成释放窗口并从队列里叫下一位顾客。窗口状态用一个数组维护队列用一个FIFO链表维护。到达事件发生时查一下窗口数组有空的就立刻把窗口标记为忙并生成对应的离开事件没有空的就把顾客节点放入队列。离开事件发生时把窗口标记为空闲然后看队列里有没有人有就弹出队首开始服务。1.3 营业时间边界到达截止与队列清空银行不能无限营业所以实验里一般会设置一个营业时间比如480分钟8小时。问题是营业时间到了之后队列里还有顾客在等怎么办很多初版实现直接在模拟时间超过营业时间时跳出循环结果发现大量顾客“凭空消失”统计数字完全不对。我给模型定的边界很明确SIM_TIME作为“停止接收新顾客”的时刻而不是“所有顾客必须离开银行”的时刻。到达事件只在当前时间小于SIM_TIME时继续生成一旦时间超过SIM_TIME不允许新顾客进入系统。但是已经在队列里排队的顾客以及正在服务窗口上的顾客必须继续模拟直到全部服务完成。这样整个模拟的结束条件就是“事件链表为空”而不是“当前时间大于SIM_TIME”。最后一位顾客的离开时间可能比SIM_TIME晚许多这是正常现象实验报告里要把这个设计思路写清楚。2. 数据结构选型事件链表、等待队列与服务窗口的三方配合2.1 事件链表的有序插入为什么不能每次遍历找最小事件事件链表的实现有两种常见路线一种是不排序每次取事件时遍历整个链表找最小时间另一种是插入时保持有序每次直接取链表头。前者代码写起来好像更少但有一个隐藏问题每次“查找最小并删除”都需要维护前驱指针还要处理多个事件时间相等的边界非常容易写错。更关键的是如果模拟时间长、顾客数多查找操作的O(n)会让运行时间呈平方级增长。我最后选择的是插入时排序。事件结构体设计如下typedef struct Event { double time; int type; // 0 表示到达1 表示离开 int window_id; // 离开事件记录哪个窗口空闲 struct Event *next; } Event;插入操作按时间升序进行时间相同的情况下让离开事件排在到达事件前面。具体比较时可以留一个很小的浮点误差阈值static int event_compare(Event *a, Event *b) { if (fabs(a-time - b-time) 1e-9) { return a-time b-time ? -1 : 1; } // 同一时刻离开事件排在到达事件前面 return (a-type b-type) ? -1 : 1; }这里把“离开优先于到达”写进了排序规则不是可有可无的小细节而是直接影响正确性的关键点。后面第5节我会专门讲这个坑。2.2 等待队列用单向链表还是循环数组顾客等待队列是标准的FIFO先进先出。两种常见实现单向链表和循环数组。循环数组的优点是内存连续、访问快但需要预先确定最大队列长度而营业时间内到底会有多少人同时排队程序跑完之前根本不知道。如果数组开小了还得自己实现扩容反而麻烦。单向链表天然支持动态增长代价是每个节点多一个指针字段在这种实验规模下完全不是问题。队列节点只需要保存顾客的“到达时间”因为计算等待时间时要用“开始服务时间 - 入队时间”。别小看这个字段没有它你后面统计平均等待时间只能干瞪眼。typedef struct QueueNode { double arrive_time; struct QueueNode *next; } QueueNode;入队时在链表尾部追加出队时从链表头弹出。这里要维护一个队列尾指针否则每次入队都要遍历到尾部又慢又容易粗心写错。2.3 随机数生成均匀分布和指数分布怎么选随机性是整个模拟的燃料。最简单的做法是用C标准库的rand()生成均匀分布随机数均匀分布也不是不行很多实验指导书为了降低难度会规定到达间隔和服务时间都在一个区间内均匀分布。但如果想让模型更贴近真实排队论会用指数分布到达间隔和服务时间都服从指数分布对应泊松到达过程和无记忆性的服务时长。这也是操作系统实验中比较经典的设计。指数分布随机数的生成公式非常短double random_exp(double mean) { double u (rand() 1.0) / (RAND_MAX 2.0); return -mean * log(u); }u一定要落在(0, 1)区间不能等于0否则log(0)会让程序直接崩掉。实际设置参数时我会把平均到达间隔设为5分钟平均服务时间设为8分钟窗口数设为4个营业时间480分钟。这样平均每分钟到达0.2人一个窗口平均每分钟服务0.125人4个窗口总服务能力是每分钟0.5人系统不会过载也不会长期空转统计数据比较好看。3. 主循环的C语言实现到达、排队、服务、离开的完整流转3.1 结构体定义与初始化第一个到达事件从哪来窗口状态用一个结构体数组表示每个窗口只关心三件事当前是否忙、累计服务时间、累计服务人数。total_service_time是用来算窗口利用率的不能漏掉。#define NUM_WINDOWS 4 #define SIM_TIME 480.0 typedef struct { int busy; double total_service_time; int serve_count; } Window; Window windows[NUM_WINDOWS];初始化函数要做三件事把所有窗口标记为空闲清空统计变量把第一个到达事件插入事件链表。第一个顾客可能在营业时间开始前就到了也可能营业开始时到达。为了简单我通常让第一个到达事件发生在0时刻让系统从营业一开始就进入正常状态。初始化代码如下void init_system() { event_head NULL; queue_head queue_tail NULL; queue_len 0; current_time 0.0; last_event_time 0.0; total_wait 0.0; served_customers 0; total_arrivals 0; queue_area 0.0; for (int i 0; i NUM_WINDOWS; i) { windows[i].busy 0; windows[i].total_service_time 0.0; windows[i].serve_count 0; } insert_event(make_event(0.0, 0, -1)); }3.2 处理到达事件先看窗口再决定入队还是直接服务到达事件处理的逻辑是整段程序的起点。顾客到达后先检查有没有空闲窗口。如果有空闲窗口顾客不需要排队直接开始服务服务时长用随机数生成然后安排一个离开事件。如果没有空闲窗口把顾客节点插入等待队列。处理完当前到达后还必须安排下一个到达事件。需要注意下一个到达时间如果已经超出SIM_TIME就不再插入事件了否则会出现“银行已经关门还一直有新顾客进来”的问题。void handle_arrival(double t) { total_arrivals; int wid find_free_window(); if (wid 0) { double svc random_exp(SERVICE_MEAN); windows[wid].busy 1; windows[wid].serve_count; windows[wid].total_service_time svc; insert_event(make_event(t svc, 1, wid)); } else { enqueue(t); queue_len; } double next_arr t random_exp(ARRIVE_MEAN); if (next_arr SIM_TIME) { insert_event(make_event(next_arr, 0, -1)); } }这里有个顺序问题容易让人困惑是先找空闲窗口还是先安排下一个到达其实都可以因为两件事互不影响。但先处理当前顾客的逻辑更清晰读代码的人一眼就能明白到达事件的核心是“这个顾客去哪”。3.3 处理离开事件从队列取人重新安排离开离开事件发生时对应窗口从忙变为空闲。紧接着看等待队列如果队列里有顾客就弹出队首用当前事件时间减去顾客入队时间得到等待时间累加到total_wait然后让这个顾客使用刚空出来的窗口并生成一个新的离开事件。如果队列为空窗口就继续闲着。void handle_leave(double t, int wid) { Window *w windows[wid]; w-busy 0; served_customers; if (queue_head ! NULL) { QueueNode *c dequeue(); queue_len--; total_wait t - c-arrive_time; double svc random_exp(SERVICE_MEAN); w-busy 1; w-serve_count; w-total_service_time svc; insert_event(make_event(t svc, 1, wid)); free(c); } }注意“开始服务”的动作是直接在离开事件处理函数里完成的没有单独生成事件。这样处理是合理的因为从离开到下一个顾客开始服务中间没有时间间隔系统状态变化是瞬时的。这也是事件驱动模拟和真实时间模拟的一个重要差异我们关心的是事件顺序而不是函数调用的时序。3.4 主循环的事件顺序同一时刻离开必须排在到达前面主循环本身不复杂每次取一个事件更新统计用的“队列面积”然后按类型分派。while (event_head ! NULL) { Event *e pop_event(); current_time e-time; // 事件发生之前队列长度一直保持上一段的值 queue_area queue_len * (current_time - last_event_time); last_event_time current_time; if (e-type 0) { handle_arrival(current_time); } else { handle_leave(current_time, e-window_id); } free(e); }循环终止条件就是event_head ! NULL。为什么不是current_time SIM_TIME因为停止生成新到达后已经排队和正在服务的顾客还需要被处理这些顾客会持续产生离开事件。只有所有事件都处理完事件链表空了模拟才算真正结束。如果提前按时间截断队列里剩下的顾客永远不会被“放出来”统计结果必然错误。4. 统计口径与结果验证平均等待时间、队长和窗口利用率怎么算4.1 平均队列长度的“事件面积法”平均等待时间最容易算累计等待总时间除以服务顾客数。但平均队列长度就没那么直观了不能把所有顾客出队时的队列长度加起来取平均。因为事件之间的时间间隔是不均匀的顾客A和B之间可能隔了0.5分钟B和C之间可能隔了10分钟不能把这两段时间里“队里都站着几个人”这件事等同看待。正确的做法是“事件面积法”在两个相邻事件之间队列长度是不变的所以每段队列长度乘以这段持续时间得到一个“人·分钟”的面积最后除以总模拟时间。用人话说就是计算队列长度这条曲线下的面积。主循环里那一行queue_area queue_len * (current_time - last_event_time)干的就是这件事。last_event_time记录的是上一个事件的发生时刻current_time是当前事件发生时刻两者之差就是“队列长度保持为queue_len”的时间长度。平均队长 queue_area / current_time。这里的分母current_time是最后一个事件的时刻也就是整个模拟持续的真实时间不是营业时间480分钟。因为队列的存在时间覆盖了整个模拟周期如果分母用480而模拟实际跑了560分钟就会低估平均队长。4.2 三个核心统计量的计算代码与输出样例统计输出的代码很简单但要注意先判断served_customers和current_time不为0避免除零崩溃。double avg_wait total_wait / served_customers; double avg_queue_len queue_area / current_time; double utilization 0.0; for (int i 0; i NUM_WINDOWS; i) { utilization windows[i].total_service_time; } utilization / NUM_WINDOWS * current_time;某次固定种子的运行结果大概长这样统计项数值总到达人数97实际服务人数97平均等待时间3.67 分钟时间加权平均队长2.51 人窗口利用率68.3%总模拟时长524.6 分钟给老师看时表格里最好再加上“最大等待时间”“最大队列长度”这类指标虽然实验要求可能没提但能给报告加分也说明你真的理解了系统状态变化。4.3 用固定序列做确定性验证先让程序“说真话”随机模拟最大的问题是不好验证。程序跑出一个平均等待时间3.67分钟你怎么知道它是真的还是错的正确的做法是先用一组写死的确定性数据让程序输出能手动算出来。我用过一个极简单的场景1个窗口3个顾客到达时间分别为0分钟、1分钟、4分钟服务时间固定为3分钟。手动推演一下顾客A在0到达直接服务0到3占据窗口等待0分钟。顾客B在1到达窗口正忙排队等到3开始服务等待2分钟。顾客C在4到达B还在服务3到6排队等到6开始服务等待2分钟。总等待时间4分钟平均等待1.333分钟总模拟时间9分钟窗口利用率100%因为窗口从0忙到9队列长度面积是2人·分钟平均队长0.222人。我用一个“测试模式”把随机函数替换成固定序列程序输出和手算完全一致。做到这一步才能证明主循环和统计逻辑本身没有大问题。4.4 多次运行观察波动随机模拟需要跑多少遍才可信确定性验证通过之后再回到随机模式。一次随机运行结果只是众多可能中的一种不代表模拟器正确。我习惯用命令行参数控制随机种子比如./bank_sim 42。调试时用固定种子比如42方便复现问题写报告时用多个种子各跑一遍观察统计值波动范围。顾客数越大平均等待时间越稳定。营业时间只有100分钟时可能某个种子结果波动很大营业时间拉到480分钟一般每种子的平均等待时间在3到4分钟附近波动。这说明系统进入稳态后统计结果才有意义。实验报告里能写出“我连续跑了10组随机种子平均等待时间均值3.54标准差0.21”这种话一眼就能看出实验做得到位。5. 我在这个实验里踩过的坑与排错过程5.1 事件链表插入顺序错误最小事件不在链表头我第一版代码写的插入逻辑是在链表尾部追加然后在取事件时遍历链表找最小事件。看起来没什么问题实际上每次取完最小事件都要处理“前驱节点指向下一节点”还要考虑最后一个节点的情况边界条件特别多。有一次顾客数量上了100运行结果开始出现诡异现象当前时间从20分钟突然跳回15分钟因为取事件时把旧节点又取了一遍。后来改成插入时排序每次直接取链表头问题一下子消失了。我的经验是如果你已经决定用链表实现事件队列就老老实实在插入时排序。别觉得取最小事件时遍历一次也行这种偷懒后面会让你花更多时间去查为什么状态更新顺序错了。5.2 同一时刻事件优先级不处理窗口会空转一个周期这是最隐蔽的坑。假设某个窗口在10.0分钟时完成服务与此同时一个新顾客在10.0分钟到达。由于浮点运算和事件插入顺序到达事件可能先被处理。这时候窗口还被标记为忙新顾客只能进入等待队列。紧接着离开事件被处理窗口变成空闲但代码只在离开事件处理时才从队列取人而这个离开事件已经被排在新顾客到达之后了窗口就只能空等直到下一个到达事件或离开事件发生时才发现队列里有人。结果是这个顾客明明可以10.0分钟立刻开始服务却要在队列里多等一段时间。这个错误对平均等待时间的影响可能不大但会让事件流日志变得不可解释而且如果你检查“窗口利用率”会发现窗口有一个不该出现的空闲时间段。解决办法就是在event_compare里规定时间相同时离开事件排在到达事件前面。理解也简单顾客只有等窗口释放后才能进去先释放窗口再让新顾客看到空闲窗口才是物理上正确的顺序。5.3 营业时间结束后提前终止队尾顾客全部蒸发有段时间我为了让程序“跑得快一点”把主循环条件写成了while (event_head ! NULL event_head-time SIM_TIME)。表面上看营业时间结束了模拟就该停但队列里还排着十几个顾客他们的离开事件时间都在SIM_TIME之后结果这些顾客永远等不到被服务的那一步。统计输出served_customers小于total_arrivals差额正好是队列里残存的顾客数。这个坑在实验报告里特别好解释营业结束意味着银行不再接收新顾客并不意味着已经进门的顾客会被赶走。所以正确逻辑是“只在生成下一个到达事件时判断是否超过SIM_TIME”主循环本身不要按时间截断。5.4 调试手段打印每一个事件而不是只看最终统计值刚开始我只打印最终统计结果出错了完全找不到原因。后来我在handle_arrival和handle_leave里各加了一行打印把事件时间、顾客编号、窗口状态、队列长度全部输出程序立刻“开口说话”了。打印样本如下[10.00] ARRIVE#15 窗口0空闲 开始服务 离开时刻17.35 [12.40] ARRIVE#16 无空闲窗口 入队 队尾等待 [17.35] LEAVE#15 窗口0释放 队列取#16 等待4.95拿这段输出和手算场景逐行对比很快就能定位是排序问题、窗口状态问题还是队列逻辑问题。调试时固定随机种子日志才能稳定复现。我建议这个实验一定先把事件流日志功能做出来再去做界面和美化输出。日志不用做得花哨fprintf(stderr, ...)就很好用。内存方面也要注意事件节点和队列节点都是动态分配的每次free之后如果还在别处引用就会出野指针问题。我在实验里加了一个内存检测工具跑了一遍发现有两个因为dequeue后忘记free造成的小泄露。虽然实验规模小程序跑完进程退出系统会回收但这个习惯到了后续更复杂的实验里会害人。如果让我重做这个实验我会在一开始就把事件流打印功能加上。你盯着最终平均等待时间3.67分钟根本不知道是哪一步错了但当你看到第17个顾客在t23.5到达后被塞进队尾直到t31.2才被窗口2叫走所有逻辑错误都一目了然。排错时先查数据结构再查事件顺序最后才去看随机数生成。顺序对了这个实验能让你少熬两个晚上还能顺带把“事件驱动模拟”这套思想彻底吃透。
阅读完成 · 觉得有帮助？
