计算机操作系统》课程设计指导书一、课程设计的目的和意义本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
, ■i、F、 / J - .11.* ［、-二、总体要求：1、课程设计总时间为五天（第十八周）。
2、课程设计地点是实验楼605 机房。
3、一个班分若干个组，每组 2 人，个别可以 3 人组（自由组合）课程设计题目由任课老师指定；4、人员分工：组长 1人、组员 1到 2 人。
组长可由小组人员自行选出或自荐，组长的职责是负责与老师交流，合理安排分配本组的各项任务，任务有：系统总体设计、编码、测试、写文档。
三、设计要求：本课程设计以 Linux 操作系统为实验平台，进行源代码分析和修改或应用。
通过该课程设计，使学生掌握 Linux 操作系统各部分结构、实现机理和各种典型算法；或使学生进行网络管理和系统管理，系统地了解操作系统的设计和实现思路，运用内核开发环境实现对内核的修改，培养学生的系统设计能力，并了解操作系统的发展动向和趋势。
要求如下：1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。
2、既要虚心接受老师的指导，又要充分发挥主观能动性。
结合课题，独立思考，努力钻研，勤于实践，勇于创新。
3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。
4、课程设计期间，无故缺席按旷课处理；缺席时间达四分之一以上者，其成绩按不及格处理。
5、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。
6、小组成员之间，分工明确，但要保持联系畅通，密切合作，培养良好的互相帮助和团队协作精神。
四、成绩评定1、同学平时表现占总成绩30％，若迟到扣 5 分，无故旷课每次扣 10 分，二次不到者总成绩以 0 分计。
2、课程设计报告占总成绩70％，在规定时间内上交。
3、严禁抄袭，复制设计内容，查出后相关同学设计成绩以零分处理。
五、设计内容（除特别注明外，每组 2 人，先自由组合，并选定1个题目，再由老师作适当调整）课题一、linux下C编程实现银行家算法通用程序，并检测所给状态的系统安全性。
1）银行家算法中的数据结构：可利用资源向量 Available 。
这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。
Available[j]=K ，则表示系统中现有 Rj 类资源 K 个。
最大需求矩阵 Max 。
这是一个 n*m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。
如果 Max[i ， j]=K ，则表示进程 i 需要 Rj 类资源的最大数目为 K 。
分配矩阵 Allocation 。
这也是一个 n*m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果 Allocation[i ，j]=K ，则表示进程 i 当前已分得 Rj 类资源的数目为K 。
需求矩阵Need。
这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。
如果 Need[i ，j]=K ，则表示进程 i 还需要 Rj 类资源 K 个，方能完成其任务。
上述三个矩阵存在如下关系：Need[i ， j]= Max[i ， j]- Allocation[i ， j]2）银行家算法设Request[i]是进程 Pi的请求向量，如果 Request"，j]=K，表示进程 Pi需要 K个Rj 类型的资源。
当 Pi 发出资源请求后，系统按下述步骤进行检查：如果Request"，j]<= Need[i，j]，便转向步骤 2;否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
3）运行结果的步骤可仿照课本的例子，初始值由系统随机生成（包括资源的个数和数量、进程的个数和每个进程获得的每种资源的数量）并类似于课本的表显示，但可不要表格线，然后完成：A .判断此时是否安全。
B •假设将给每一进程分配资源，检测是否能分配。
课题二、处理机调度程序：选择一个调度算法，实现处理机调度。
设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。
也就是说能运行的进程数大于处理机个数。
为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。
要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。
设计要求：1）先由用户输入进程数量（至少 5 个进程），再由系统随机生成一个进程序列（包括到达时间和服务时间）。
2）然后显示进程调度算法由用户选择，包括：时间片轮转法，短作业优先算法，动态优先级算法。
2）可选择进程数量3)显示结果包括每个进程的开始时间、完成时间、周转时间以及带权周转时间，显示界面可参考书本的例子以表格形式但可不要表格线。
课题三、用多进程同步方法解决生产者——费者问题设计目的：通过研究 Linux 的进程机制和信号量实现生产者消费者问题的并发控制 .说明：有界缓冲区内设有 20 个存储单元，放入 /取出的数据项设定为 1-20 这 20 个整型数。
设计要求：(1)每个生产者和消费者对有界缓冲区进行操作后，实时显示有界缓冲区的全部内容、当前指针位置和生产者 /消费者的标识符。
(2)生产者和消费者各有两个以上。
(3)多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码。
提示： (1) 有界缓冲区可用数组实现。
课题四：为LINUX 设计一个简单的二级文件系统。
要求做到以下几点：(可以3 人组)1、可以实现下列几条命令，但可不用参数。
注意，必须真正实现，不能模拟实现，如 Dir 类似于 Linux 的 ls 命令。
Login 用户登录Dir 列出文件夹内容Create 创建文件Delete 删除文件Open 打开文件Close 关闭文件Read 读文件Write 写文件2、列目录时要列出文件名、物理地址、保护码和文件长度。
3、源文件可以进行读写保护。
主要需完成以下子过程，但不一定全部要用到。
1、i 节点内容获取函数 iget( )2、i 节点内容释放函数 iput( )3、目录创建函数 mkdir( )4、目录搜索函数 namei( )5、磁盘块分配函数 balloc( )6、磁盘块释放函数 bfree( )7、分配 i 节点区函数 ialloc( )8、释放 i 节点区函数 ifree( )9、搜索当前目录下文件的函数 iname( )10、访问控制函数 access( )11、显示目录和文件用函数 _dir( )12、改变当前目录用函数 chdir( )13、打开文件函数 open( )14、创建文件函数 create( )15、读文件用函数 read( )16、写文件用函数 write( )17、用户登录函数 login( )18、用户退出函数 logout( )19、文件系统格式化函数 format( )20、进入文件系统函数 install( )21、关闭文件系统函数 close( )22、退出文件系统函数 halt( )23、文件删除函数 delete( )课题五：存储管理——动态分区分配算法的模拟：要求设计主界面以灵活选择某算法，以下算法都要实现：1、首次适应算法2、循环首次适应算法3、最佳适应算法；4、最坏适应算法；5、快速适应算法具体要求：1)首先由系统生成当前的内存状态，按照课本 P122图4-5 (a)所示，要求未分配的分区数量不少于 3 个，且空间大小随机，然后随机生成一个数，表示等待分配进程的大小。
2)然后显示上述算法由用户选择，结果显示分配后的状态。
3)课题六：编程演示三种存储管理方式的地址换算过程：1、分页方式的地址换算。
具体要求：1)随机生成页面大小，但一定为 2 的幂，系统随机生成一个至少有 10 行的页表，页号、块号从 0 开始。
2)用户给定一个逻辑地址，首先显示此地址的页号和页内地址，然后显示是第几块，最后显示其物理地址。
2、分段方式的地址换算。
具体要求：1)由系统随机生成 5个左右的段，并随机生成一个段表并显示。
2)由用户给定一个逻辑地址，包括段号和段内地址，最后显示其物理地址。
3、段页式的地址换算。
具体要求：1）先由系统随机生成 5 个左右的段，然后再由系统随机生成页面大小，但一定为2 的幂。
然后生成段表和页表，具体内容参照课本 P140 的图 4-22 。
2）由用户给定一个逻辑地址，包括段号和段内地址，最后显示其物理地址。
课题七：进程调度（可模拟实现）1、设计内容1）设计进程控制块 PCB 表结构，分别适用于优先权调度算法和时间片轮转调度算法。
2） PCB 结构包括以下信息：进程名、进程优先数（或轮转时间片），进程所占用的 CPU 时间，进程的状态，当前队列指针等。
根据调度算法的不同， PCB 结构的内容可以作适当的增删。
3）建立进程就绪队列。
对两种不同算法编制入链子程序。
4）编制两种进程调度算法：A、优先数调度；B、循环轮转调度。
2、具体设计要求及有关说明选用优先数算法和简单时间片轮转法对五个进程进行调度，每个进程可有三种状态：运行状态（ RUN ）、就绪状态（ READY ）和完成状态。
并假定初始状态为就绪状态。
设计进程控制块结构如下：PCB:NAMEPRIO/ROUNDCPUTIMECOUNTNEEDTIMESTATENEXT其中：NAME ——进程标识符；PRIO ――进程优先数；ROUND ——进程轮转时间片；CPUTIME ――进程占用 CPU 时间；COUNT ――计数器；NEEDTIME ――进程到完成还要的 CPU 时间；STATE ——进程的状态；NEXT ――链指针。
进程控制块链结构如插图。
其中：RUN ――当前运行进程指针；READY ――就绪队列头指针；TAIL ――就绪队列尾指针；FINISH ――完成队列头指针。
为了便于处理，程序中进程的运行时间以时间片为单位计算。
各进程的优先数或轮转时间片数以及进程需运行的时间片数的初值均由用户给定。
RUNFINISH________————人3、程序设计算法：(1)在优先数算法中，进程每执行一次，优先数减3, CPU时间片数加1,进程还需要的时间片数减1。
在轮转法中，采用固定时间片，时间片数为2,进程每执行一次，CPU时间片数加2，进程还需要的时间片数减 2，并排到就绪队列的尾上。
(2)程序结构说明如下：整个程序由 INSERT1, INSERT2, FIRSTIN, PRINT, CREATE, PRISCH 和 ROUNDSCH 过程组成。