Operating System Principles And Implementation

助教信息

教材

1. 教材主页：http://www.os-book.com/
2. 教材信息：英文原版的最新版为第10版；目前国内有第7版的影印版和翻译版。

其他参考书

Slides

1. 课程简介
2. 绪论(1), 绪论(2) CS Structure
3. Chapter 2: OS Structure
4. Chapter 3: Processes
5. 4 CPU Scheduling
6. 5 Threads
7. Chapter 6: Process Synchronization
8. Chapter 7: Deadlock
9. Chapter 8: Main Memory
10. Chapter 9: Virtual Memory
11. Chapter 10: File System Interface
12. Chapter 11: File system implementation(文件系统实现)
13. Chapter 12: Mass Storage Systems, RAID
14. Chapter 13: I/O systems

上机实验(上机时间：待定；地点：待定)

实验1：制作启动硬盘并启动一个操作系统映像[实验报告截止时间：待定]

• 例如dlxlinux，或其他
• 这里提供2个RTEMS操作系统的映像: hello.exe ticker.exe
• 也可以自己编译一个Linux内核、制作一个根文件系统，并启动之

实验2:任务管理和FCFS调度[实验报告截止时间：待定]

1. 设计任务数据结构，命名为myTCB
2. 实现任务创建原语（接口命名为createTsk()）和销毁原语（接口命名为destroyTsk()）功能
3. 实现任务上下文切换（接口命名为CTX_SW()）功能
4. 实现FCFS调度算法，调度接口命名为schedule()
5. 实现简单的就绪队列和入列/出列原语
6. 实现任务启动原语，接口命名为tskStart()
7. 实现任务终止原语，接口命名为tskEnd()
8. 创建idle任务，idle任务的主体是一个死循环，在循环体中，调用schedule
9. 创建init任务，init任务的主体（接口命名为initTskBody()）由测试用例提供。
10. 实现osStart原语
11. 测试用例[老师提供userApp目录]：创建一组任务，这组任务按照FCFS的方式先后运行并输出相关信息。
12. 必须提供的接口说明参见QQ群中文件“2-README-2019-task-fcfs”
13. 老师提供userApp目录参见QQ群中压缩文件“2_userApp.rar”
14. 老师提供的基础平台代码参见QQ群中压缩文件“2_boot2C.rar”，基础平台代码的运行环境和运行方法参见这里

1. 不考虑抢占。
2. 按照FCFS的方式组织就绪队列。
3. 在任务创建原语的最后，若创建成功直接调用tskStart()。
4. 在任务终止原语中，任务从就绪队列中出列，并调用销毁原语，最后调用调度接口(有bug)。
5. 上下文切换原语的要求是：支持本实验的正确运行
6. osStart完成idle、init的创建之后，调用上下文切换原语或者schedule完成控制权的第一次转移，进入多任务运行

1. 提供设计报告、测试计划和测试报告
2. 要求1：设计报告中提供每个数据结构和原语的接口说明、设计说明，给出原语流程
3. 要求2：测试报告中给出测试内容和测试计划，测试用例的设计、测试运行情况和测试结果分析

实验2可替代方案：进程管理源代码分析

1. 结合Linux-5.0.7内核源代码，分析fork()对应的系统调用及其实现
2. 若有同学已经完成实验二，可以找他（她）要一份，对他（她）的源代码进行分析（要分析所有必须实现的实验二接口）
3. 在实验二截止时间之后，老师会公布一个实验二的源代码，对这个源代码进行分析（要分析所有必须实现的实验二接口）

1. 说明实验二（1）进展情况（2）遇到了什么困难（要具体），导致无法完成实验二
2. 说明你采用替代方案中的哪一个？若使用的是同学的代码，要说明是哪个同学（该同学的实验分将增加0.1分/每人）。若你在分析过程中找到了同学代码的bug，请清楚说明（酌情加分）。
3. 源代码分析报告：可以贴你认为关键的代码（建议最好使用伪代码和流程图），但必须有文字说明；文字量必须大大多于代码量

1. 你原先实验二打包提交（不管是否完成），文件名为"self+你的学号"打头
2. 若使用同学的代码，提交同学给你的源代码包，文件名为“mate+同学的学号打头”打头
3. 老师提供的代码和Linux代码不必提交
4. 实验报告

实验3:优先级调度/RR调度/多级调度[实验报告截止时间：待定][待调整]

1. 实现任务参数设定原语setTskPara()，getTskPara()等，以支持设定优先级Priority/执行时长ExeTime/到达时间ArriveTime等参数
2. 修改任务创建原语，以设定任务参数
3. 实现SJF/优先级/时间片轮转/多级队列调度算法
4. 修改osStart原语，以增加相关功能的初始化
5. 测试用例[老师提供userApp目录]：创建一组运行时间较长的任务，运行过程中输出相关信息（要求能展现优先级/时长/时间片轮转的效果）。
6. 必须提供的接口说明参见QQ群中文件“3-README-2019-scheduler”[待提供]
7. 老师提供userApp目录参见QQ群中压缩文件“3_userApp.rar”[待提供]
8. 老师提供的基础实验平台（实验二+中断+时钟）[待提供]

1. 难度0：采用单一的FCFS调度算法
2. 难度1（最高3分）：采用单一的SJF调度算法（可抢占或者不可抢占）
3. 难度1（最高3分）：采用单一的RR调度算法
4. 难度1（最高3分）：采用单一的优先级调度算法（可抢占或者不可抢占）（每个优先级最多只有一个任务）
5. 难度2（最高8分）：优先级调度算法（可抢占或者不可抢占）。任务可以认定为可抢占或者不可抢占。同优先级的任务可以自由选择采用FCFS或RR。
6. 难度3（最高10分）：多级队列调度2级，实时任务和非实时任务。 实时任务的基本调度算法是优先级调度算法（可抢占或不可抢占）。任务可以认定为可抢占或者不可抢占。实时任务可以设定为SCHED_RT_FCFS或SCHED_RT_RR。 非实时任务是SCHED_RR。
7. 难度3(最高10分）：多级反馈调度算法。
8. 本实验至少完成难度1中的某1项。本实验没有替代实验。

1. 提供设计报告、测试计划和测试报告
2. 要求1：设计报告中提供每个数据结构和原语的接口说明、设计说明，给出原语流程
3. 要求2：测试报告中给出测试内容和测试计划，测试用例的设计、测试运行情况和测试结果分析

实验4:内存管理算法[实验报告截止时间：待定]

1. 检测物理内存：实现内存有效性检查方案以检查你所管理的动态内存。
• 为简单起见，允许直接从1MB开始。
• 接口：pMemStart（？=1MB）和pMemSize。
• 操作系统初始化过程中进行检查，并汇报pMemStart和pMemSize的值（要求16进制表示）
• 附加（非强制要求）：从0地址开始。
2. 实现动态分区算法：dPartition
• 给定任意大小的内存区域，按照动态分区算法对其进行初始化。接口：dPartitionInit()。（要求：若内存区域太小，小于最小大小，进行失败提示）
• 从动态分区中分配一个指定大小的分区（允许进行4字节、8字节或你自定义的某个大小对齐）。接口：dPartitionAlloc()
• 释放一个分区。接口：dPartitionFree()
• 将检测到的动态物理内存，按照动态分区的方式进行管理
• 重新封装动态物理内存的分配和回收接口，提供malloc和free接口给userApp。
3. 实现等大小固定分区算法：eFPartition
• 给定分区大小和分区个数，结合你的内部管理数据结构开销，计算出总大小。接口：eFPartitionTotalSize()
• 将给定内存区域初始化为若干个等大小固定分区。初始化接口：eFPartitionInit()
• 分配一个固定大小分区。接口：eFPartitionAlloc()
• 释放一个固定大小分区。接口：eFPartitionFree()
• 修改你的任务池分配算法：从动态物理内存中，分配一个动态分区，该动态分区能容纳指定个数的任务和内部数据管理开销，使用等大小固定分区算法管理这个动态分区。
4. 修改osStart原语，以增加内存管理功能
5. 测试用例[老师提供userApp目录]：创建一组任务，这组任务按照FCFS的方式先后运行，运行过程中进行内存管理测试并输出相关信息。
6. 必须提供的接口说明参见QQ群中文件“4-README-2019-mem”[待提供]
7. 老师提供userApp目录参见QQ群中压缩文件“4_userApp.rar”[待提供]

1. 说明你的内存有效性检查方案，提供参考文献
2. 说明你的动态分区算法和等大小固定分区算法
3. 要求1：设计报告中提供每个数据结构和原语的接口说明、设计说明，给出原语流程
4. 要求2：测试报告中给出测试内容和测试计划，测试用例的设计、测试运行情况和测试结果分析