Skip to content

About

Simulated Unix scheduler with 9 policies and example codes to explore latency, MTTF, response, etc. and design policies in sandbox. Inspired by CSC3150 of CUHKSZ.

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

1 Commit

Folders and files

Repository files navigation

Simduler · 调度与代码实验台

受 CUHKSZ CS专业课 CSC3150 启发的各种理想调度策略的跨代码探究实验台

本地运行的操作系统实验工具:左侧 UNIX 风格脚本,右侧调度回放、策略对照、C 实测与可解释规则搜索。它不需要 npm 安装依赖,不调用远程 AI,不上传源码。

启动

需要 Python 3.10+;浏览器支持 ES modules / Web Workers。测试和 CLI 需要 Node.js 18+(推荐 20+)。本机 C 测量需要 cc(macOS 开发工具或 Linux GCC)。

cd simduler
python3 server.py
# 打开 http://127.0.0.1:8765
# 或 python3 server.py --port 9000

只监听 loopback,不用直接双击 index.html(模块与测量 API 需要 HTTP)。基础功能不需要 Docker 或 Julia。

四种使用方式

  1. 教学回放:选场景,修改左侧脚本,运行;点击时间线或逐步播放。观察就绪队列、预算、状态和选择理由。
  2. 策略工具:同一负载下比较九种策略;选择目标,查看平均响应、P95 等待、周转、开销和 bootstrap CI。导出 JSON;导入时重新计算,不信任文件中的既有指标。
  3. C / UNIX 工作台:七个内置 C 示例可改输入规模、重复实测 wall / process CPU 时间,可查看并下载独立源码。Shell 卡片供手动复制,网页不会执行 shell。示意负载按钮会明确标识为人工建模。
  4. 规则探索:WAF 参数搜索(27 组)及不同 seed 的验证负载;另有独立 Min-Min / Max-Min 多机映射实验。

任务语言

policy mlfq quantum=2 switch=1 levels=2,4 boost=50 aging=8 wake=2
seed 7
job compiler at=0 cpu=20 tickets=10 weight=1
job terminal at=2 cpu=1,1,1 io=3,3 tickets=30 deadline=20
run
  • cpu=8,2 表示两段 CPU 工作,中间需有一段 io=4。所有值为整数 tick。
  • at 是绝对到达时间,deadline 是绝对截止时间。tickets 用于 Lottery,weight 用于 WAF。
  • quantum 用于 RR / Lottery / WAF;MLFQ 使用 levels 的预算;SJF/FCFS/HRRN 不抢占。
  • switch 是不同任务切换时的整数开销;最初选择、同一任务重选、空闲后恢复不收取成本。
  • Ctrl/Cmd + Enter 运行。参数可由右侧表单应用;实验源保存在当前浏览器 localStorage。

算法

FCFS、RR、SJF、SRTF、两至四级 MLFQ、Lottery、HRRN、EDF,以及实验性的 WAF(Wait-Aware Feedback)。

WAF 在每个时间片边界按以下分数选择 ready 任务,同分 FIFO:

ready_age / aging
+ wake_bonus × exp(−time_since_wakeup / 6)
+ weight / (1 + consumed_cpu)

它仅使用等待和既有 CPU 消耗,尝试在交互响应和等待老化之间折中;它不是已证明最优的新理论,也不保证硬实时或无限输入下无饥饿。搜索结果仅是当前模拟负载上的候选,不是自动分析任意 C 源码后推断的最佳内核策略。

原生测量与阶段插桩

python3 tools/benchmark.py sort --size 200000 --repeats 10 --output output/sort.json
node tools/simulate.mjs examples/mixed.sim
node tools/simulate.mjs examples/mixed.sim --compare --json > output/comparison.json
node tools/simulate.mjs examples/mixed.sim --tune

内置 C 示例:sort.c、matrix.c、prime.c、pipe.c、producer_consumer.c、timer.c、stream.c,公共计时头文件为 workload.h。下载按钮将头文件合并,生成单独可编译的 .c 文件。

另有单线程应用阶段插桩示例:

cc -std=c11 -O2 -I examples/c examples/c/instrumented.c -o /tmp/instrumented
/tmp/instrumented > output/my-profile.json
# 在网页导入 my-profile.json,或:
node tools/simulate.mjs output/my-profile.json

它测量程序显式声明的 CPU / I/O 阶段,以 1ms 向上取整为模拟 tick。这是应用阶段 profile,不是内核调度轨迹;过短阶段量化偏差明显。多线程 / 子进程需要另外定义测量口径。

可选:自定义 C 隔离执行

先启动 Docker:

docker build -t simduler-runner:local -f Dockerfile.runner .

然后在 C 工作台展开自定义 C,检查环境后运行。容器不挂载宿主目录,无网络,root filesystem 只读;以非 root 用户运行,所有 capabilities 删除,no-new-privileges;最多 32 个进程、256MB 内存、1 CPU,20 秒(含编译),最多 64KB 输出。工作区仅在临时内存文件系统中,结束后移除容器。该工作区可执行是运行编译产物的必要条件;其余隔离仍保留。

这是本地可信用户的教学工具,Docker 不等于独立内核 VM,不能直接暴露为公网代码运行服务。未准备镜像时会明确报错,绝不退回宿主机执行用户 C。宿主机运行的只有仓库内经过审阅的内置示例。

测试

npm test                # 调度、统计、多机映射;包含 1800 个随机负载/策略组合
npm run check           # JS 语法检查
npm run test:native     # C 编译/校验、超时/输出上限、HTTP 集成与请求保护

Docker 执行的实测与 GCC Linux 可移植性记录见 output/;详见 docs/VERIFICATION.md。

重要边界

  • 模型是单 CPU、整数 tick、独立并发 I/O,无真实设备争用、内存系统或缓存模型;不模拟真实 Linux 调度器。
  • SJF / SRTF / HRRN 使用下一段 burst 的已知长度,属理想化 oracle;WAF 不使用该信息。不同策略比较须考虑这一信息差异。
  • 真实毫秒、模拟 tick、Linux time/nice/perf 输出是三种不同层次,不能自动互换。
  • Lottery 的长期份额应在所有参与者持续 runnable 的共同窗口内观察,不能用有限任务全部完成后的 CPU 总量证明公平。内部 serviceJain 仅描述最终完成工作量,不是调度器公平性的证据。
  • 参数搜索会过拟合。应分离训练/验证负载;排名归一化依赖候选集,跨实验成本分不能直接比较。
  • Gaussian KDE 是平滑描述;可能出现负值区域的边界偏差。重复固定工作负载不代表对未知负载的置信度。
  • 基础应用只需标准 Python + 浏览器;本项目的计算规模不需要 Julia。以后可用 Julia 扩展统计,但必须与同一 workload schema 对齐。

架构和模型详见 docs/MODEL.md;下一步探索见 docs/ROADMAP.md。

About

Simulated Unix scheduler with 9 policies and example codes to explore latency, MTTF, response, etc. and design policies in sandbox. Inspired by CSC3150 of CUHKSZ.

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages