A09 工业以太网环网多任务防重调度器

摘要：本项目是一个基于《计算机程序设计艺术》（TAOCP）算法库的工业级任务调度系统实现。通过组合循环链表（带哨兵节点）和链地址哈希表（动态扩容）两种经典数据结构，构建了一个模拟工业以太网环网的多任务防重调度器。系统采用Round-Robin轮询调度机制，支持优先级权重，并通过哈希表实现O(1)复杂度的任务去重检测。项目强调工程哲学中的"可控可观"原则，要求对内存走向有绝对掌控力，并通过打点统计让算法瓶颈可视化。本文档提供了从算法历史、核心要求、新手四步上手路径到避坑锦囊的完整指导，旨在将TAOCP中的纯粹数学与指针魔术转化为工业级系统底盘。

项目概述

本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。

维度	内容
组合算法	循环链表（Circular Linked List） + 链地址哈希表（Chained Hash Table）
TAOCP出处	卷1 §2.2.4 (循环链表) + 卷3 §6.4 (链地址哈希)
难度	★★★
支撑目标	目标1（系统设计）、目标2（综合考虑）
核心目标	将TAOCP中的纯粹数学与指针魔术，转化为工业级系统底盘

---

算法史故事

1956年，AI先驱Newell等人为解决循环枚举问题发明了循环链表。1953年，IBM工程师Luhn利用"计算寻址"发明了链地址哈希表，通过拉链法解决哈希冲突，解决了无序数据的超快查找问题。

---

课程任务

模拟自动化设备中的令牌环协议或轮询调度器（Round-Robin）。用带有哨兵节点的循环链表存放任务队列，支持无终点轮询。为了防止重复任务积压，结合拉链法哈希表（采用动态扩容）对任务ID进行O(1)的查重检测。

---

核心要求

• 实现循环链表（带哨兵节点，支持无限轮询）
• 实现链地址哈希表（动态扩容，djb2/其他哈希函数）
• 实现任务调度器（Round-Robin轮询，支持优先级权重）
• 实现任务去重检测（哈希表查重，拒绝重复任务ID）
• 模拟工业以太网环网中的任务分发与调度
• 统计调度延迟、哈希冲突率、扩容次数

---

工程哲学：可控可观（Controllability-Observability）

• 可控：对每一字节内存走向有绝对掌控力，不允许不可预知的系统崩溃
• 可观：通过打点、日志和统计，让不可见的算法瓶颈变得清晰可见

工程伦理

理解工业网络中任务调度的实时性要求，培养对通信协议可靠性的严谨设计态度。

---

新手破冰指南：C语言视角的四步上手路径

如果把学习编程比作建设一座自动化无人工厂：

• 基础数据结构课：教你认识什么是传送带（链表）、什么是储物架（数组）。
• TAOCP 算法库：是存放着各种顶级工业标准件的仓库。库里的 taocp1_circular_linked_list.c 是一条首尾相连、永不停息的环形分拣线；而 taocp3_chained_hash_table.c 则是一套能在一秒内扫描并识别上万个条形码的极速安检闸机。
• A09 课程设计：要求你作为架构师，把"环形分拣线"和"极速安检闸机"组合起来，打造一个工业级的任务调度中心。它不仅要能让任务公平地轮转执行（不间断运行），还要能瞬间识别并拦截重复发送的冗余指令（防重积压）。

简而言之：算法库提供的是"极致单点性能"，而A09项目要求你实现"复杂系统整合"。

第一步：建立调度的"绝对可控性"（搭建永动机）

你的现状：习惯了单向链表遍历到 NULL 就结束程序。

你要做的：造一个没有终点的环。

复习循环链表。引入一个"哨兵节点（Sentinel）"，这是一个不装载任何真实任务的假节点，它的作用是作为你遍历的基准标尺。

让尾节点的 next 指向哨兵节点，哨兵节点的 next 指向第一个任务。

写一个 while(1) 循环，定义一个执行指针 current。它不断地 current = current->next。遇到哨兵就跳过，遇到真实任务就"执行"（这里可以用 printf 或延时函数模拟），这就是工业界大名鼎鼎的 Round-Robin（轮询调度） 的底层真相。

第二步：打造 O(1) 的拦截网（破解哈希黑盒）

你的现状：知道用 for 循环遍历整个链表去查找一个任务 ID 是否存在，但这种 O(n) 的做法在任务量大时会导致系统卡死。

你要做的：理解哈希（Hash）映射。

定义一个指针数组：TaskNode* hash_table[128];。

实现一个简单的哈希函数（比如 djb2）。它就像一个魔法公式，能把任何复杂的字符串（如 “Task_9527”）通过数学计算，瞬间变成一个 0~127 之间的整数下标。

核心挑战（拉链法）：如果有两个不同的任务算出了相同的下标怎么办（哈希冲突）？在这个数组的格子里，挂一条单向链表。每次新任务来，算好下标，直接去那条短短的链表里找有没有重复的兄弟即可。

第三步：双剑合璧（系统级装配）

你的现状：两套结构单独都能跑通，但不知道怎么结合。

你要做的：控制任务的"生命周期"。

当一个新任务到达系统时，必须严格遵守以下业务逻辑：

1. 过安检：先用哈希表查重。算下标 -> 搜链表。如果找到了，直接拦截并丢弃，打印"重复拦截"。
2. 上产线：如果在哈希表里没找到，说明是新任务。不仅要把它插入到哈希表里（为了以后防别人重），还要把它插入到循环链表里（准备排队执行）。

注：这里考验的是 C 语言指针的功底，同一个任务节点，既在哈希表的链条上，又在调度器的环形链条上，要理清两套 next 指针的关系。

第四步：构建系统状态的"可观性"（动态扩容与监控）

你的现状：只会把数据塞进去，不关心系统的健康度。

你要做的：为工业设备安装"仪表盘"。

• 监控装载率：每次加入新任务，计算 负载因子 = 任务总数 / 哈希表数组大小。
• 动态扩容（Resize）：一旦发现负载因子 > 0.75（意味着哈希冲突概率飙升），立即申请一个两倍大的新数组，把老哈希表里的任务重新计算下标挂上去。这保证了查询速度永远是极速的。
• 打点统计：在代码里加入全局变量，记录发生冲突的次数、扩容的次数、轮询一圈的平均耗时，并在控制台实时打印。

---

给新手的避坑锦囊

作为刚接触复杂指针关系的学生，在这个项目中你最容易踩中以下几个"地雷"：

1. "死循环"的终结条件（遍历陷阱）

普通单向链表的遍历是 while (p != NULL)。但在循环链表中，里面没有 NULL！如果你要打印环网上所有的任务，你的循环条件必须是 while (p->next != sentinel)。忘记这一点，你的控制台会被无限滚动的乱码瞬间淹没。

2. “请神容易送神难”（同步删除的灾难）

当一个任务执行完毕需要从系统中移除时，绝对不能只从循环链表里删。你必须同时通过计算它的哈希值，去哈希表的挂链里把它也摘除，最后才能调用 free(node)。如果漏删一处，就会产生经典的"野指针（Dangling Pointer）"导致系统崩溃（Segmentation Fault）。

3. 数据结构解耦（结构体设计技巧）

不要试图在一个结构体里把两套逻辑揉在一起。最佳实践是这样定义节点：

typedef struct Task {
    char task_id[32];      // 业务数据
    int priority;          // 优先级权重
    struct Task* hash_next;// 专供哈希表冲突拉链使用的指针
    struct Task* ring_next;// 专供环网轮询使用的指针
} Task;

画图时，用红色笔画 hash_next 的连线，用蓝色笔画 ring_next 的连线。

4. 先跑通"玩具模型"

不要一上来就写动态扩容，也不要一上来就模拟并发任务流。

先手写固定大小（比如 4）的哈希表，手动插入 Task_A, Task_B, Task_A。用 printf 打印出安检闸机（哈希表命中）的日志，再打印环形链表当前挂了哪些任务。确认"防重"和"轮询"100%正确后，再写一个 for 循环生成 1000 个随机任务进行极限压测。

---

目录结构

.
├── README.md          # 本文件（项目总览）
├── Makefile           # GCC编译脚本
├── .gitignore         # Git忽略规则
├── src/               # 源代码目录
│   ├── main.c         # 主程序入口
│   ├── algorithm_a.c  # 算法A实现
│   ├── algorithm_b.c  # 算法B实现
│   ├── utils.c        # 工具函数
│   └── include/       # 头文件目录
│       ├── algorithm_a.h
│       ├── algorithm_b.h
│       └── utils.h
├── docs/              # 文档目录
│   ├── 01-需求分析.md
│   ├── 02-算法史故事.md
│   ├── 03-功能框图.png
│   ├── 04-详细设计.md
│   └── 05-测试报告.md
├── report/            # 课程设计报告
│   └── 设计报告模板.md
└── test/              # 测试代码
    ├── unit_test.c    # 单元测试
    └── test_data/     # 测试数据集

---

快速开始

编译

make        # 编译主程序
make test   # 编译测试
make clean  # 清理

运行

./main
./unit_test

---

里程碑

里程碑	截止时间	状态
v0.1-方案确定	5月18日	⏳ 待开始
v0.2-详细设计	6月21日	⏳ 待开始
v0.3-编码完成	7月5日	⏳ 待开始
v0.4-验收演示	7月10日	⏳ 待开始
v1.0-最终提交	7月12日	⏳ 待开始

---

Git提交规范

[A-模块] 具体修改内容

示例：
[A-循环链表] 实现带哨兵节点的Round-Robin轮询调度
[A-哈希表] 实现链地址哈希表与djb2哈希函数
[A-任务调度] 实现任务查重与优先级调度
[A-动态扩容] 实现哈希表负载因子监控与动态扩容

---

源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。