从系统调用到LRU：OS课程实验的四大关键模块

简介东南大学《操作系统概念》课程作业代码与实验报告合集面向操作系统课程学习者、课程设计或需要参考同类实验的学生。四个实验依次涉及使用系统调用实现文件读写并完善错误处理在Linux内核中增加系统调用利用Mutex和信号量机制实现生产者消费者问题以及编写LRU算法及其近似算法并分析页错误率基本覆盖操作系统核心知识点。资源共27个文件以C/C源码、头文件、Word实验报告、CSV数据文件和说明文档为主压缩包整体14.63MB。代码与报告按实验分目录存放CSV文件记录随机页面访问序列及统计结果便于验证和对比不同算法的缺页情况。已有229人学习所有代码均测试运行成功Windows和Linux平台版本完整既可直接编译运行也可作为撰写实验报告的参考还是一份可套用的代码模板与实验报告范文能帮助理解文件I/O、内核调用、同步互斥和内存管理等关键机制。1. 从系统调用到LRU一份OS课程作业里的四个实验单元一份《操作系统概念》课程的源码包能翻出多少东西这套作业没有停留在“调通API”层面系统调用、内核源码级分析、进程同步、页面置换四块硬骨头各占一个实验。SystemCall.cpp、test.c、psta.c、LRU.h 加上多份统计csv每个文件对应一次能复现的验证。对课程设计卡住的人这些是可直接抄的基线对工作几年的工程师值得看的是另一层错误处理怎么做才不糊弄、生产者消费者为什么在Windows和Linux上写法不同、随机序列下LRU到底比FIFO强多少。这些参数判断正是OS实验报告最该写的内容。2. 系统调用文件拷贝read/write与双平台错误处理的正确姿势2.1 交互式输入比命令行参数更容易卡住这个实验第一项硬性要求是“使用者可输入源文件和目的文件的路径”。很多人习惯用scanf(%s)一次性读两个字符串代码在测试目录里跑得好好的直到有人给了带空格的路径——Windows 的Program Files、Linux 桌面环境里常见的带空格目录名都会让路径在第一个空格处被截断打开文件必然失败。我一般用fgets读整行再手工去掉换行符把路径当作一整行来处理而不是一个无空格的 token。// 交互式读入路径并去掉换行避免 scanf 被空格截断 char src[PATH_MAX], dst[PATH_MAX]; printf(Input source file path: ); if (fgets(src, sizeof(src), stdin) NULL) { fprintf(stderr, failed to read input\n); return -1; } src[strcspn(src, \n)] \0; // 去掉 fgets 留下的换行符 if (src[0] \0) { fprintf(stderr, source path is empty\n); return -1; }fgets最多读入sizeof(src) - 1个字符并把换行符也放进缓冲区strcspn(src, \n)返回第一个换行符的下标把它替换成\0就能得到干净的路径串。PATH_MAX在 Linux 下通常是 4096足够覆盖绝大多数绝对路径。这里还做了一个空串校验否则后续open会返回一个不太直观的ENOENT。2.2 用 open/read/write 而不是 fread/fwrite为什么要求用系统调用而不是fread/fwrite因为fopen系列会在用户态维护一块缓冲区底层的read/write调用细节被隐藏了而本实验考察的恰恰是“系统调用返回值怎么判断、部分写怎么处理”。read返回正整数表示实际读到的字节数返回 0 表示到达文件尾返回 -1 才是出错write同样不保证一次把缓冲区全部写出。真正容易翻车的是忽略了write的局部写。// Linux 侧打开输入文件逐块拷贝目标文件用追加/创建方式打开 int in_fd open(src, O_RDONLY, 0644); int out_fd open(dst, O_WRONLY | O_CREAT | O_TRUNC, 0644); if (in_fd 0 || out_fd 0) { perror(open failed); close(in_fd); close(out_fd); return -1; } char buf[4096]; ssize_t n; while ((n read(in_fd, buf, sizeof(buf))) 0) { char *p buf; while (n 0) { // 处理部分写 ssize_t w write(out_fd, p, n); if (w 0) { perror(write failed); goto fail; } p w; n - w; } }buf选 4096 字节正好对应一个内存页大小既不会因为缓冲区太小而频繁陷入内核态也不会因为太大挤占栈空间。内层while是关键磁盘满、管道阻塞、信号中断都可能导致返回值小于传入长度只有循环到n 0才算写完的一段数据真正落地。perror会根据当前errno打印具体错误文本比只输出 “error” 有信息量得多。2.3 错误处理不能只写一个 return -1交互式程序最忌讳“一错就退出”。源文件不存在、权限不够、目标路径是个目录、磁盘写满这四类错误应该分别提示用户怎么处理而不是抛出一个笼统的失败码。可以把错误场景整理成一张矩阵报告里直接照抄错误场景Linux 下的 errno处理惯例源文件不存在ENOENT提示重新输入源路径无读取权限EACCES提示检查文件权限或运行身份目标是目录EISDIR提示目标必须指向文件路径输出位置空间不足ENOSPC提示清理磁盘保留已写部分路径过长ENAMETOOLONG提示缩短路径或更换目录2.3.1 Windows 侧的错误码差异Windows 上这套判断完全不一样。CreateFileA失败返回INVALID_HANDLE_VALUE即(HANDLE)-1而不是 0 或负数ReadFile/WriteFile返回 BOOL失败时调用GetLastError()才能拿到错误码而且错误码取值范围和 errno 完全不重叠。// Windows 侧CreateFileA 打开文件失败统一走 GetLastError 分支 HANDLE hIn CreateFileA(src, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); if (hIn INVALID_HANDLE_VALUE) { fprintf(stderr, Open failed, code%lu\n, GetLastError()); return -1; }第三个参数FILE_SHARE_READ表示允许其他进程同时读这个文件不传的话文件被占用时CreateFileA会直接失败OPEN_EXISTING强制“文件必须已存在”正好对应 Linux 的O_RDONLY语义。写报告时可以强调一句两套 API 的返回值判据不同是双平台移植里最容易忽略的差异。提示Windows 侧路径分隔符是反斜杠但绝大多数底层 API 同时接受正斜杠进入CreateFileA之前先统一替换路径分隔符能少很多诡异错误。3. 从Linux内核源码到新系统调用Syscall表、注册与验证3.1 读内核代码不要从头到尾按调用链往下钻作业一的 part2 要求做 Linux 内核代码分析还要新增系统调用。很多同学的第一个问题是“内核源码那么大从哪读起”。我一般建议先写一个用户态的小工具确定要观测的系统调用再沿着“应用 →syscall()→ 平台入口 → 系统调用表 → 具体实现”这条链往下追。项目里的test.c、psta.c、psta.h就是这个思路psta负责封装调用和统计test.c负责触发这样分析内核时不用反复改用户态代码。分析内核代码不需要先找网盘里过时的 PDF 二手资料直接拉一份主线内核源码从最常被调用的open、read、write入手就足够了。主线源码的注释和宏定义都更新及时读它相当于站在最新实现上看问题比看旧版剖析书更接近真实代码。3.2 系统调用表syscall_64.tbl 是第一个入口x86_64 架构下新增系统调用最先要动的是arch/x86/entry/syscalls/syscall_64.tbl。这张表每一行把一个系统调用号映射到内核函数名编译脚本会把它生成 C 头文件entry_SYSCALL_64拿到用户态传入的调用号后直接在表里查函数指针并跳转。所以“增加系统调用”本质是四步步骤要改的文件内容分配编号syscall_64.tbl在表尾选一个空闲编号如 548声明原型include/linux/syscalls.h加入 asmlinkage 函数声明实现主体kernel/ 下新增文件用 SYSCALL_DEFINEn 宏包裹函数体编译注册重新编译内核并重启用户态测试前先确认 dmesg不同内核版本的系统调用号差异很大选号前先看表尾最大值别去猜一个固定号码。自己实验用的内核选一个空闲号即可如果提交到真实环境还要同步更新syscalls_64.h等由脚本生成的文件这些生成文件不要手工改。3.3 用 SYSCALL_DEFINEn 而不是直接写函数直接写一个long sys_hello_os(...)也能通过编译但少了参数类型校验和追踪点支持。SYSCALL_DEFINE1这组宏会把参数展开成合适的寄存器存取逻辑保证 64 位平台下指针参数能正确到达。内核态读用户态字符串还必须用strncpy_from_user不能直接解引用用户指针否则可能触发异常或读到不可信数据。// kernel/hello_os.c 自定义系统调用打印用户态传入的字符串 #include linux/kernel.h #include linux/syscalls.h #include linux/uaccess.h SYSCALL_DEFINE1(hello_os, const char __user *, name) { char buf[64]; if (strncpy_from_user(buf, name, sizeof(buf) - 1) 0) return -EFAULT; // 用户地址非法或越界 buf[sizeof(buf) - 1] \0; pr_info(hello_os: %s\n, buf); // 内核日志用 dmesg 查看 return 0; }函数名前的__user标记是给 sparse 静态检查工具看的提示这个指针来自用户态strncpy_from_user返回值小于 0 表示复制失败返回 -EFAULT 后用户态拿到的就是errno等于 14。pr_info打到内核日志用dmesg | tail能看到输出。调试时如果dmesg里什么都没有先确认调用号有没有真正注册进系统调用表。3.4 用户态验证syscall() 触发与 psta 统计3.4.1 用 syscall() 直接触发新调用glibc 不会为自定义系统调用生成包装函数所以测试代码里用syscall()最省事// test.c 用户态触发新系统调用返回值小于 0 表示 -errno #include unistd.h #include sys/syscall.h #include stdio.h #ifndef SYS_hello_os #define SYS_hello_os 548 // 与 syscall_64.tbl 保持一致 #endif int main(void) { long ret syscall(SYS_hello_os, OS Course); fprintf(stderr, ret%ld\n, ret); // 负数即 -errno return 0; }syscall()第一个参数是调用号后面跟着可变参数正好绕过 libc 包装层。unistd.h里没有这个宏时手动#define测试完记得删掉避免污染环境。3.4.2 psta.c/psta.h 把统计逻辑收敛起来psta这类辅助模块通常做三件事循环触发 N 次系统调用、记录每次返回值、最后输出平均耗时。这样换调用号时只改一处统计逻辑不用动。我在实验报告里把psta的输出整理成表格既展示了内核行为又说明了用户态观测手段比只贴一段dmesg更有说服力。4. 生产者/消费者Pthreads与Win32信号量的对称与差异4.1 为什么同一个题目要求写两遍生产者/消费者是《操作系统概念》第七版第六章后的经典 Project。它在 Linux 下的标准解法是pthread_mutex_t加sem_t在 Windows 下则是一组内核对象句柄CreateMutex、CreateSemaphore、WaitForSingleObject。两套 API 的抽象层级不一样Pthreads 把同步原语当作类型化的对象Windows 则统一用HANDLE操作。同一个算法写两遍的价值在于你能清楚看到“锁 信号量”是系统的资源管理手段而不是某个库特有的语法。4.2 Linux 侧互斥锁只保护缓冲数组不能包住信号量等待4.2.1 信号量初始值决定缓冲语义有界缓冲的核心是两个信号量empty_slots表示空闲槽位数量full_slots表示有数据的槽位数量。初始值一个等于缓冲区容量一个等于 0生产者和消费者对称操作才不会出现计数错乱。// 代码_Linux有界缓冲容量 8使用互斥锁 两个信号量 #define BUFFER_SIZE 8 sem_t empty_slots, full_slots; pthread_mutex_t mutex PTHREAD_MUTEX_INITIALIZER; sem_init(empty_slots, 0, BUFFER_SIZE); // 初始空闲槽位 容量 sem_init(full_slots, 0, 0); // 初始有数据槽位 0sem_init第二个参数传 0 表示线程间共享传非 0 才是进程间共享第三个参数是信号量初值。如果full_slots初值误写成容量消费者会立刻以为缓冲区里全是数据读到的却是未初始化的内存。4.2.2 持锁等信号量是一种典型的自锁死锁// 错误写法先拿互斥锁再等空闲槽位 pthread_mutex_lock(mutex); sem_wait(empty_slots); // 缓冲区满时生产者阻塞消费者拿不到锁 pthread_mutex_unlock(mutex);// 正确顺序先等信号量再进入临界区 sem_wait(empty_slots); pthread_mutex_lock(mutex); buffer[in] item; in (in 1) % BUFFER_SIZE; pthread_mutex_unlock(mutex); sem_post(full_slots);错误版本在缓冲区满时生产者阻塞在sem_wait上消费者想进临界区取数据却被互斥锁挡住双方互相等待。正确顺序的核心是锁只保护共享数组本身信号量负责“有没有空间/有没有数据”两者各司其职不要嵌套。4.3 Windows 侧句柄与 WaitForSingleObject 的对称写法Windows 版本的逻辑模型一样但 API 观感完全不同。WaitForSingleObject既是 P 操作也是锁获取一个函数通吃ReleaseSemaphore则对应 V 操作。生产者代码写成这样// 代码_WindowsCreateSemaphore CreateMutex WaitForSingleObject HANDLE g_hEmpty CreateSemaphore(NULL, BUFFER_SIZE, BUFFER_SIZE, NULL); HANDLE g_hFull CreateSemaphore(NULL, 0, BUFFER_SIZE, NULL); HANDLE g_hMutex CreateMutex(NULL, FALSE, NULL); DWORD WINAPI Producer(LPVOID param) { for (int i 0; i 100; i) { WaitForSingleObject(g_hEmpty, INFINITE); // 等待空闲槽位 WaitForSingleObject(g_hMutex, INFINITE); // 获取互斥锁 buffer[in] i; in (in 1) % BUFFER_SIZE; ReleaseMutex(g_hMutex); ReleaseSemaphore(g_hFull, 1, NULL); // 释放一个数据槽 Sleep(20); } return 0; }CreateSemaphore第二、三个参数分别是初始计数和最大计数这里empty和full的最大值都设为缓冲区容量ReleaseSemaphore第三个参数用于接收上一次计数不需要就传NULL。WaitForSingleObject第二个参数传INFINITE表示无限等待生产环境通常换成超时时间。Windows 版最常见的坑是线程函数写完后忘了CloseHandle句柄泄漏在长时间运行时非常明显。4.4 常见故障假死、消费者不醒、VS调试拦不住断点症状原因修法运行几秒后卡住持锁状态下等待 empty/full 信号量把信号量等待移出临界区消费者永远不醒full 信号量初值错给成容量检查CreateSemaphore初始计数两个生产者写同一个槽in 下标没按容量取模写入后立即(in 1) % BUFFER_SIZE主函数退出后子线程消失没回收线程句柄就 return先WaitForSingleObject(hThread)再退出VS 提示“当前不会命中断点”编译优化或 PDB 与 exe 版本不一致用 Debug 配置 F5 启动确认符号文件最新“当前不会命中断点”不是代码逻辑问题而是调试符号没对上。重新生成 exe 后PDB 时间戳必须一致断点才拦得住这条经验在双平台项目里同样适用Linux 侧对应的是-g编译选项和gdb的源码路径设置。注意如果生产者和消费者各自只跑固定次数就退出主线程一定要先join所有子线程再返回否则main结束会直接终止整个进程统计结果永远是残缺的。5. LRU实现与复杂度对比双向链表哈希不是唯一答案5.1 数据结构选型为什么是链表加哈希实验四要求实现 LRU 及其近似算法并分析时间复杂度、空间复杂度和实现难度。LRU 要解决三件事访问时快速定位页面、满时快速找出最久未用的页面、同时维护访问时间顺序。双向链表加哈希表正好覆盖这三个需求unordered_map页号, 链表迭代器提供 O(1) 定位链表头表示最近访问链表尾表示最久未用淘汰时删尾节点也是 O(1)。算法访问代价淘汰代价额外空间实现难度LRU链表哈希O(1)O(1)O(页框数)高维护双向链表和 map 同步CLOCK/二次机会O(1)最坏 O(n) 扫描O(页框数)中低只需环形数组FIFOO(1)O(1)O(页框数)最低但存在 Belady 异常CLOCK 算法用环形数组加引用位近似 LRU缺页时从指针位置扫描引用位为 1 就清零并继续遇到 0 就替换。最好情况 O(1)最坏情况要扫一整圈。实验报告里讲“实现难度”重点就写 CLOCK 对引用位的维护逻辑以及为什么它能近似 LRU。5.2 随机页面访问序列均匀分布与局部性main.cpp生成测试序列的方式会直接影响页错误率的结论。如果所有页面等概率出现工作集接近全部页面任何算法的表现都会被拉平真实程序有明显的局部性访问往往集中在少数页面附近。所以测试要生成两组序列一组均匀随机做 baseline一组带局部性模拟真实负载。// main.cpp 生成带局部性的访问序列ratio 控制局部性强弱 std::vectorint gen_trace(int length, int max_page, double locality) { std::vectorint seq(length); int cur rand() % max_page; for (int i 0; i length; i) { if (rand() % 100 (int)(locality * 100)) { // 90% 概率在当前位置 ±1 邻域内移动 cur (cur (rand() % 3) - 1 max_page) % max_page; seq[i] cur; } else { seq[i] rand() % max_page; // 瞬间跳出模拟切换 } } return seq; }locality取 0.9 时大约 90% 的访问落在当前页邻域10% 随机跳跃cur跳到随机页后下一轮依然有 90% 概率留在新邻域这模拟了进程切换后的重新聚集。访问长度建议不低于 10 万次太短的话随机波动会把算法差异淹没掉。5.3 页错误率计算口径要写死在第一行5.3.1 冷启动与预热页错误率的算法很简单缓存未命中次数除以总访问次数。容易产生歧义的是初始状态缓存为空时前几个页面必定缺页这部分“冷启动缺失”是否计入统计不同报告可能给出不同数字。// 缺页统计缓存从空开始缺页数累加 faults for (int page : seq) { if (cache_map.find(page) ! cache_map.end()) { touch(page); // LRU 中把该页移到链表头 continue; } faults; if (cache_map.size() capacity) evict(); // 淘汰链表尾部或 CLOCK 指针处 insert(page); // 新页加入链表头 } double miss_ratio (double)faults / seq.size();touch(page)在 LRU 里是 O(1) 的链表摘除和头插在 CLOCK 里只是把引用位置 1很多近似算法实现漏掉了这个操作导致“访问已有页面”没有更新热度信息结果错误率比真正的 LRU 差一大截。报告中要注明“统计口径为冷启动包含前capacity次缺页”再把不含预热的数字也列出来两条曲线都给读者看。注意evict()和insert()必须作用于同一个数据结构。如果 LRU.h 里链表和哈希表赋值不一致缺页率会出现“算出来的淘汰页号根本不在缓存里”这类诡异现象先用小容量单步调试。6. 用trace与统计csv交叉验证LRU时序数据怎么榨出结论实验四配套的OSC-Experiment4-Traces.zip和五份_statistics.csv是用来验证算法实现最直接的素材。trace 是原始页面访问序列csv 是跑完算法后的统计数据。拿到压缩包先别急着写报告第一步是解压并确认 trace 格式unzip -o OSC-Experiment4-Traces.zip -d traces head -n 5 traces/emacs.trace如果每行一个数字那就是页号总行数就是访问次数如果带逗号第二列通常是读/写类型或时间戳统计脚本要按列取值。wc -l traces/emacs.trace能快速确认访问规模测试时间也以这个数据量为准。五份_statistics.csv的表头不一定完全相同先用head -n 1看列名再决定用哪一列做缺页率计算。手头有多个 csv 时用 awk 压缩成一张横向对比表for f in *_statistics.csv; do faults$(tail -1 $f | cut -d, -f1) refs$(tail -1 $f | cut -d, -f2) awk -v name$f -v f$faults -v r$refs \ BEGIN { printf %s %.4f%%\n, name, f * 100 / r } done这段脚本假设 csv 最后一行的第一列是缺页次数、第二列是访问次数。实际文件列顺序可能不同跑之前先看表头按实际列号改-f参数不要照抄。验证近似算法时最好把 LRU.h 的淘汰逻辑抽象成touch()和evict()两个回调CLOCK、NFU 只改这两处统计代码一行不动。这样跑同一份 trace得到缺失率的差异才是算法本身带来的差异。把多个 csv 合并成比率曲线时横坐标建议用“可用页框数”而不是访问次数再和教材里经典曲线对比报告的说服力会强很多。本文还有配套的精品资源点击获取