操作系统课程设计任务书(2014级计算机、软件、网络)

1 2016 20172016 2017 学年第一学期学年第一学期 操作系统操作系统 课程设计任务书课程设计任务书 依照大纲和课程内容实践特点 结合 操作系统 LINUX 操作系统 和 嵌入式程序设计 课程主要内容 课设的具体要求及任务如下 一 设计成果的要求一 设计成果的要求 课程设计应严格按照要求完成 在系统调试成功后 需要提供 操作系统 课程设计报告 具体包括 1 设计目的 1 设计内容 3 设计准备 理论 技术 4 设计 过程 设计思想 代码实现 5 设计结果并分析 6 系统的结构 原理 框图和模块等的详细说明 7 用户使用说明书和参考资料 8 设计体会 注 注 1 1 1 1 7 7 项可以打印 项可以打印 8 8 设计体会必须手写 设计体会必须手写 2 2 报告的封皮 封底 采用给定的模板 报告的内容 在教师的指导报告的封皮 封底 采用给定的模板 报告的内容 在教师的指导 下 独立完成 自主排版 不做统一要求 下 独立完成 自主排版 不做统一要求 二 设计任务 每名同学选一题 独立完成 二 设计任务 每名同学选一题 独立完成 题目一题目一 进程与线程进程与线程 LinuxLinux 进程与线程通讯进程与线程通讯 1 1 设计目的设计目的 深刻理解线程和进程的概念 掌握线程与进程在组成成分上的差别以及与 其相适应的通讯方式和应用目标 Linux 系统的 fork 保持了 UNIX 的经典语义 被创建的进程具有独立于父 进程的地址空间 二者之间的通讯通常可采用 pipe 机制 clone 是 Linux 系统特有的系统调用 可以通过参数确定父子进程之间是否共享存储空间等资 源 在地址空间等资源共享的情况下 clone 实质相当于创建了一个轻进程或 线程 这是 clone 的通常用法 实际在 Linux 系统中 fork 以及用户级线程 pthread 都是基于 clone 实现的 2 2 设计内容设计内容 2 以 Linux 系统进程和线程机制为背景 掌握 fork 和 clone 系统调用 的 形式和功能以及与其相适应的高级通讯方式 由 fork 派生的子进程之间通过 pipe 通讯 由 clone 创建的线程之间通过共享内存通讯 对于后者需要考虑互 斥问题 以生产者 消费者问题为例 通过实验理解 fork 和 clone 两个系统 调用的区别 程序要求能够创建 4 个进程或线程 其中包括两个生产者和两个 消费者 生产者和消费者之间能够传递数据 题目二题目二 处理机调度处理机调度 实时调度算法实时调度算法 EDFEDF 和和 RMSRMS 1 1 设计目的设计目的 深入理解处理机调度算法 了解硬实时概念 掌握最早截止期优先调度算 法 EDF Earliest Deadline First 和速率单调调度算法 RMS Rate Monotonic Scheduling 的可调度条件 并能在可调度情况下给出具体调度结果 2 2 设计内容设计内容 在 Linux 环境中采用用户级线程模拟实现 EDF 和 RMS 两种实时调度算法 给 定一组实时任务 按照 EDF 算法和 RMS 算法分别判断是否可调度 在可调度的 情况下 创建一组用户级线程 分别代表各个实时任务 并按算法所确定的调 度次序安排各个线程运行 运行时在终端上画出其 Gantt 图 为避免图形绘制 冲淡算法 Gantt 图可用字符表示 题目三题目三 存储管理存储管理 动态异长存储资源分配算法动态异长存储资源分配算法 1 1 设计目的设计目的 理解动态异长存储分区资源管理 掌握所需数据结构和管理程序 了解各 种 存储分配算法的优点和缺点 2 2 设计内容设计内容 3 1 分析 UNIX 最先适应 First Fit FF 存储分配算法 即 map 数据结构 存储分配函数 malloc 和存储释放函数 mfree 找出与算法有关的成分 2 修改上述与算法有关的成分 使其分别体现 BF Best Fit 最佳适应 分配原则和 WF Worst Fit 最环适应 分配原则 题目四 文件系统题目四 文件系统 HashHash 结构文件结构文件 1 1 设计目的设计目的 理解 Linux 文件系统的内部技术 掌握 Linux 与文件有关的系统调用命令 并在此基础上建立面向随机检索的 Hash 结构文件 Linux 系统保持 UNIX 文件系统的风格 提供流式文件界面 这种结构具有 简洁灵活的特点 但并不直接支持记录式文件和关键字检索 本设计在 Linux 文件系统基础上 设计一组库函数 以提供对随机检索的支持 2 2 设计内容设计内容 1 参考教程中 Hash 文件构造算法 设计一组 Hash 文件函数 包括 Hash 文件创建 打开 关闭 读 写等 2 编写一个测试程序 通过记录保存 查找 删除等操作 检查上述 Hash 文件是否实现相关功能 题目五 设备管理题目五 设备管理 LinuxLinux 设备驱动程序安装设备驱动程序安装 1 1 设计目的设计目的 认识 Linux 设备的种类和设备工作方式 理解设备驱动程序的工作原理 掌 握设备驱动程序的编写规范 能编写并安装简单的设备驱动程序 2 2 设计内容设计内容 在 Linux 系统中 编写一个简单的字符型设备驱动程序模块 设备具有独 占特性 可执行读和写操作 相关系统调用为 open close read write Open 和 close 分别相当于请求和释放设备 read 和 write 将内容保存在设备模块内 4 的绥冲区中 设备模块可动态注册和卸载 并建立与之对应的特殊文件 dev mydev 题目六 题目六 BootloaderBootloader 引导程序设计与实现引导程序设计与实现 1 1 设计目的设计目的 认识 Bootloader 的作用 深入理解 Bootloader 的编程思想 以典型的引 导程序 vivi 为例 对 vivi 程序的架构 vivi 的启动流程 使用 vivi 完成系 统引导程序的设计方法形成深刻的理解和认识 2 2 设计内容设计内容 在嵌入式操作系统中 Bootloader 的作用与 PC 机上的 BIOS 类似 通过 Bootloader 可以完成对系统板上的主要部件如 CPU SDRAM Flash 串行口等 进行初始化 当运行操作系统时 它会在操作系统内核运行之前运行 通过它 可以分配内存空间的映射 从而将系统的软硬件环境带到一个合适的状态 以 便为最终调用操作系统准备好正确的环境 本设计要求同学首先分析老师提供的 vivi 程序源代码 理清 vivi 程序的 架构分为哪几个模块 然后根据分析 vivi 程序的执行流程具体分为哪几个阶段 各阶段的主要任务是什么 最后要求同学编写内存映射初始化函数 mem map init 和内存管理单元初始化函数 mmu init 题目七 嵌入式题目七 嵌入式 linuxlinux 下键盘驱动程序的设计与实现下键盘驱动程序的设计与实现 1 1 设计目的设计目的 通过完成对嵌入式 linux 下键盘驱动程序的设计和调试 掌握嵌入式 linux 驱动程序的编写方法 理解驱动程序动态模块的调试方法 掌握驱动程 序添加到内核的流程 2 2 设计内容设计内容 设备驱动程序是操作系统内核和机器硬件之间的接口 设备驱动程序为应用 程序屏蔽了硬件的细节 故在应用程序看来 硬件设备只是一个设备文件 应 用程序可以像操作普通文件一样对硬件设备进行操作 5 本设计要求同学按照标准设备驱动程序的步骤编写驱动程序 由于键盘的 设备驱动程序属于字符设备的驱动 因此 应当按照字符设备的规则编写 要 求同学编写键盘设备文件 file operations 结构 以及以下几个键盘操作函数 键盘控制函数 Kbd Ioctl 关闭键盘设备函数 Kbd Close 打开键盘设备函 数 Kbd Open 获取键值函数 Kbd Getkey 键盘服务子程序 Kbd ISR 键 盘设备的硬件初始化函数 Setup Kbd 注册键盘设备使用函数 KbdInit 和卸 载键盘设备函数 Kbd Exit 题目八 首次适应算法的动态分区分配方式模拟题目八 首次适应算法的动态分区分配方式模拟 1 设计目的设计目的 了解动态分区分配中使用的数据结构和分配算法 并进一步加深对动态分 区存储管理方式及其实现过程的理解 2 设计内容设计内容 1 用 C 语言实现采用首次适应算法的动态分区分配过程 alloc 和回收过程 free 其中 空闲分区通过空闲分区链表来管理 在进行内存分配时 系统 优先使用空闲区低端的空间 2 假设初始状态如下 可用的内存空间为 640KB 并有下列的请求序列 作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 6 请采用首次适应算法进行内存块的分配和回收 同时显示内存块分配和回 收后空闲内存分区链的情况 题目九 循环首次适应算法的动态分区分配方式模拟题目九 循环首次适应算法的动态分区分配方式模拟 1 设计目的设计目的 了解动态分区分配中使用的数据结构和分配算法 并进一步加深对动态分 区存储管理方式及其实现过程的理解 2 设计内容设计内容 1 用 C 语言实现采用循环首次适应算法的动态分区分配过程 alloc 和回收过 程 free 其中 空闲分区通过空闲分区链表来管理 在进行内存分配时 系 统优先使用空闲区低端的空间 2 假设初始状态如下 可用的内存空间为 640KB 并有下列的请求序列 作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用循环首次适应算法进行内存块的分配和回收 同时显示内存块分配 和回收后空闲内存分区链的情况 题目十 最佳适应算法的动态分区分配方式模拟题目十 最佳适应算法的动态分区分配方式模拟 1 设计目的 设计目的 7 了解动态分区分配中使用的数据结构和分配算法 并进一步加深对动态分 区存储管理方式及其实现过程的理解 2 设计内容 设计内容 1 用 C 语言分别实现采用最佳适应算法的动态分区分配过程 alloc 和回收过 程 free 其中 空闲分区通过空闲分区链表来管理 在进行内存分配时 系 统优先使用空闲区低端的空间 2 假设初始状态如下 可用的内存空间为 640KB 并有下列的请求序列 作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用最佳适应算法进行内存块的分配和回收 同时显示内存块分配和回 收后空闲内存分区链的情况 题目十一 最坏适应算法的动态分区分配方式模拟题目十一 最坏适应算法的动态分区分配方式模拟 1 设计目的 设计目的 了解动态分区分配中使用的数据结构和分配算法 并进一步加深对动态分 区存储管理方式及其实现过程的理解 2 设计内容 设计内容 1 用 C 语言分别实现采用最坏适应算法的动态分区分配过程 alloc 和回收过 程 free 其中 空闲分区通过空闲分区链表来管理 在进行内存分配时 系 统优先使用空闲区低端的空间 8 2 假设初始状态如下 可用的内存空间为 640KB 并有下列的请求序列 作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用最坏适应算法进行内存块的分配和回收 同时显示内存块分配和回 收后空闲内存分区链的情况 题目十二 题目十二 进程调度模拟算法进程调度模拟算法 1 设计目的 设计目的 通过算法的模拟加深对进程概念和进程调度过程的理解 掌握进程状态之 间的切换 同时掌握进程调度算法的实现方法和技巧 2 设计内容 设计内容 1 用 C 语言来实现对 N 个进程采用动态优先权优先算法的进程调度 2 每个用来标识进程的进程控制块 PCB 用结构来描述 包括以下字段 进程标识数 ID 进程优先数 PRIORITY 并规定优先数越大的进程 其优先权越高 进程已占用的 CPU 时间 CPUTIME 进程还需占用的 CPU 时间 ALLTIME 当进程运行完毕时 ALLTIME 变为 0 进程的阻塞时间 STARTBLOCK 表示当进程再运行 STARTBLOCK 个时间片后 进程将进入阻塞状态 进程被阻塞的时间 BLOCKTIME 表示已阻塞的进程再等待 BLOCKTIME 个时间片后 进程将转换成就绪状态 进程状态 STATE 队列指针 NEXT 用来将 PCB 排成队列 9 3 优先数改变的原则 进程在就绪队列中呆一个时间片 优先数增加 1 进程每运行一个时间片 优先数减 3 4 假设在调度前 系统中有 5 个进程 它们的初始状态如下 ID01234 PRIORITY93830290 CPUTIME00000 ALLTIME33634 STARTBLOCK2 1 1 1 1 BLOCKTIME30000 STATEREADYREADYREADYREADYREADY 5 为了清楚地观察进程的调度过程 程序应将每个时间片内的进程的情况 显示出来 参照的具体格式如下 RUNNING PROG i READY QUEUE id1 id2 BLOCK QUEUE id3 id4 ID01234 PRIORITYP0P1P2P3P4 CPUTIMEC0C1C2C3C4 ALLTIMEA0A1A2A3A4 STARTBLOCKT0T1T2T3T4 BLOCKTIMEB0B1B2B3B4 STATES0S1S2S3S4 题目十三 请求调页存储管理方式的模拟题目十三 请求调页存储管理方式的模拟 1 1 设计目的 设计目的 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系 统的原理和实现过程的理解 2 设计内容 设计内容 1 假设每个页面中可存放 10 条指令 分配给作业的内存块数为 4 2 用 c 语言模拟一个作业的执行过程 该作业共有 320 条指令 即它的地 址空间为 32 页 目前它的所有页都还未调入内存 在模拟过程中 如果所访 问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令 还未装入内存 则发生缺页 此时需记录缺页的次数 并将相应页调入内存 如果 4 个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有 320 指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 采用先进先出 FIFO 置换算法 提示提示 10 1 1 通过随机数产生一个指令序列 共 通过随机数产生一个指令序列 共 320320 条指令 指令的地址按下述原则生条指令 指令的地址按下述原则生 成 成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 即执行地址为 m 1 的指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 的指令 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 2 2 将指令序列变换为页地址流 将指令序列变换为页地址流 设页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容里为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存 中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 3 计算先进先出 FIFO 算法在不同内存容量下的命中率 其中 命中率 1 页面失效次数 页地址流长度 题目十四 请求调页存储管理方式的模拟题目十四 请求调页存储管理方式的模拟 2 1 设计目的 设计目的 11 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系 统的原理和实现过程的理解 2 设计内容 设计内容 1 假设每个页面中可存放 10 条指令 分配给作业的内存块数为 4 2 用 C 语言模拟一个作业的执行过程 该作业共有 320 条指令 即它的地 址空间为 32 页 目前它的所有页都还未调入内存 在模拟过程中 如果所访 问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令 还未装入内存 则发生缺页 此时需记录缺页的次数 并将相应页调入内存 如果 4 个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有 320 指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 最近最久未使用 LRU 算法 提示提示 1 1 通过随机数产生一个指令序列 共 通过随机数产生一个指令序列 共 320320 条指令 指令的地址按下述原则生条指令 指令的地址按下述原则生 成 成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 即执行地址为 m 1 的指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 的指令 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 2 2 将指令序列变换为页地址流 将指令序列变换为页地址流 设页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容里为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存 中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 12 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 3 计算最近最少使用 LRU 算法在不同内存容量下的命中率 其中 命中率 1 页面失效次数 页地址流长度 题目十五 请求调页存储管理方式的模拟题目十五 请求调页存储管理方式的模拟 3 1 设计目的 设计目的 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系 统的原理和实现过程的理解 2 设计内容 设计内容 1 假设每个页面中可存放 10 条指令 分配给作业的内存块数为 4 2 用 C 语言模拟一个作业的执行过程 该作业共有 320 条指令 即它的地 址空间为 32 页 目前它的所有页都还未调入内存 在模拟过程中 如果所访 问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令 还未装入内存 则发生缺页 此时需记录缺页的次数 并将相应页调入内存 如果 4 个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有 320 指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 最佳置换 OPT 算法 提示提示 1 1 通过随机数产生一个指令序列 共 通过随机数产生一个指令序列 共 320320 条指令 指令的地址按下述原则生条指令 指令的地址按下述原则生 成 成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 即执行地址为 m 1 的指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 的指令 13 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 2 2 将指令序列变换为页地址流 将指令序列变换为页地址流 设页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容里为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存 中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 3 计算最佳置换 OPT 算法在不同内存容量下的命中率 其中 命中率 1 页面失效次数 页地址流长度 题目十六 请求调页存储管理方式的模拟题目十六 请求调页存储管理方式的模拟 4 1 设计目的 设计目的 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系 统的原理和实现过程的理解 2 设计内容 设计内容 1 假设每个页面中可存放 10 条指令 分配给作业的内存块数为 4 2 用 C 语言模拟一个作业的执行过程 该作业共有 320 条指令 即它的地 址空间为 32 页 目前它的所有页都还未调入内存 在模拟过程中 如果所访 问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令 还未装入内存 则发生缺页 此时需记录缺页的次数 并将相应页调入内存 如果 4 个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有 320 指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 最少访问 LFU 算法 提示提示 14 1 1 通过随机数产生一个指令序列 共 通过随机数产生一个指令序列 共 320320 条指令 指令的地址按下述原则生条指令 指令的地址按下述原则生 成 成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 即执行地址为 m 1 的指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 的指令 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 2 2 将指令序列变换为页地址流 将指令序列变换为页地址流 设页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容里为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存 中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 3 计算最少访问 LFU 算法在不同内存容量下的命中率 其中 命中率 1 页面失效次数 页地址流长度 题目十七 请求调页存储管理方式的模拟题目十七 请求调页存储管理方式的模拟 5 1 设计目的 设计目的 15 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系 统的原理和实现过程的理解 2 设计内容 设计内容 1 假设每个页面中可存放 10 条指令 分配给作业的内存块数为 4 2 用 C 语言模拟一个作业的执行过程 该作业共有 320 条指令 即它的地 址空间为 32 页 目前它的所有页都还未调入内存 在模拟过程中 如果所访 问的指令已在内存 则显示其物理地址 并转下一条指令 如果所访问的指令 还未装入内存 则发生缺页 此时需记录缺页的次数 并将相应页调入内存 如果 4 个内存块均已装入该作业 则需进行页面置换 最后显示其物理地址 并转下一条指令 在所有 320 指令执行完毕后 请计算并显示作业运行过程中发生的缺页率 3 置换算法 最近最不经常使用 NRU 算法 提示提示 1 1 通过随机数产生一个指令序列 共 通过随机数产生一个指令序列 共 320320 条指令 指令的地址按下述原则生条指令 指令的地址按下述原则生 成 成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 即执行地址为 m 1 的指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 的指令 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 2 2 将指令序列变换为页地址流 将指令序列变换为页地址流 设页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容里为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存 中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 16 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 3 计算最近最不经常使用 NRU 算法在不同内存容量下的命中率 其中 命中率 1 页面失效次数 页地址流长度 题目十八 题目十八 P V 操作及进程同步的实现操作及进程同步的实现 1 1 设计目的 设计目的 掌握信号量通信方式的一般方法 了解系统实现 阻塞 和 唤醒 功能的方 法和技巧 同时掌握进程同步和互斥的概念及实现技术 2 设计内容 设计内容 1 用语言编程实现 P V 原语并用 P V 原语描述如下理发师 顾客问题 有一个理发师 一把理发椅和 n 把提供给等候理发的顾客座的椅子 如果 没有顾客 则理发师便在理发椅子上睡觉 当第一个顾客到来时 必须唤醒该 理发师进行理发 如果理发师正在理发时又有顾客到来 则如果有空椅子可坐 他就坐下来等待 如果没有空椅子 他就离开理发店 为理发师和顾客各编一段程序描述他们的行为 要求不能带有竞争条件 试用 P V 操作实现 2 实验要求及说明 定义信号量并将 P V 操作定义为带参数 以输出字符串的形式表示理发师和顾客的行为 设计适当的数据结构和函数描述顾客等待队列和 唤醒 理发师理发过程 以及没有顾客时的 阻塞 理发师过程 编程时需考虑理发师和顾客对应的程序是并发操作的 提示 可利用随机函数模拟并发操作 理发师和顾客两个进程各自调用一个函数模拟生产及消费的操作 题目十九 题目十九 P V 操作及进程同步的实现操作及进程同步的实现 2 1 设计目的 设计目的 掌握信号量通信方式的一般方法 了解系统实现 阻塞 和 唤醒 功能的方 法和技巧 同时掌握进程同步和互斥的概念及实现技术 2 设计内容 设计内容 用语言编程实现 P V 原语并用 P V 原语哲学家就餐问题 17 为每个哲学家各编一段程序描述他们的行为 试用 P V 操作实现 题目二十 银行家算法题目二十 银行家算法 1 设计目的 设计目的 1 了解多道程序系统中 多个进程并发执行的资源分配 2 掌握银行家算法 了解资源在进程并发执行中的资源分配情况 3 掌握预防死锁的方法 系统安全状态的基本概念 2 设计内容 设计内容 设计一个 n 个并发进程共享 m 个系统资源的程序以实现银行家算法 要求 1 简单的选择界面 2 能显示当前系统资源的占用和剩余情况 3 为进程分配资源 如果进程要求的资源大于系统剩余的资源 不与分配 并且提示分配不成功 4 撤销作业 释放资源 编写和调试一个系统动态分配资源的简单模拟程序 观察死锁产生的条 件 并采用适当的算法 有效地防止和避免死锁的发生 银行家算法分配资源的原则是 系统掌握每个进程对资源的最大需求量 当进程要求申请资源时 系统就测试该进程尚需资源的最大量 如果系统中现 存的资源数大于或等于该进程尚需求资源最大量时 就满足进程的当前申请 这样就可以保证至少有一个进程可能得到全部资源而执行到结束 然后归还它 所占有的全部资源供其它进程使用 银行家算法中的数据结构 1 可利用资源向量 Available 一维数组 是一个含有 m 个元素 其中的每一个元素代表一类可利用的资源数目 其初 值是系统中所配置的该类全部可用资源数目 如果 Available j k 表示系统中 现有 Rj类资源 k 个 2 最大需求矩阵 Max 二维数组 m 的矩阵 它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需 求 如果 Max i j k 表示进程 i 需要 Rj类资源的最大数目为 k 3 分配矩阵 Allocation 二维数组 m 的矩阵 它定义了系统中每一类资源当前已分配给每一进程的资源数 如果 Allocation i j k 表示进程 i 当前已分得 Rj类资源 k 个 4 需求矩阵 Need 二维数组 是一个含有 n m 的矩阵 用以表示每一个进程尚需的各类资源数 如果 Need i j k 表示进程 i 还需要 Rj类资源 k 个 方能完成其任务 Need i j Max i j Allocation i j 题目二十一 题目二十一 SPOOLING 技术技术 1 设计目的 设计目的 18 设计一个 SPOOLING 假脱机输出的模拟程序 更好地理解和掌握 SPOOLING 技术的实现原理 2 设计内容 设计内容 SPOOLING 技术广泛地应用于各种计算机的 I O 该技术通过预输出和缓 输出的方法 使用共享设备的一部分来模拟独占设备 1 设计一个实现 设计一个实现 SPOOLING 技术的进程技术的进程 设计一个 SPOOLING 输出服务进程 一个 SPOOLING 输出进程 两个用户 请求进程 用户进程请求输出一系列信息 调用输出服务进程 由输出服务进 程将该信息送入输出井 等待 SPOOLING 进程进行输出 SPOOLING 输出进程 工作时 根据请求块记录的各进程要输出的信息将其输出 2 设计进程调度算法 进程调度采用随机算法 两个请求输出的用户进程的调度概率各为 45 SPOOLING 输出进程为 10 这由随机数发生器产生的随机数来模拟决 定 1 进程状态 2 进程基本状态有可执行 等待 结束三种 可执行状态就是进程正在运 行或等待调度的状态 等待状态又分为等待状态 1 等待状态 2 等待状 态 3 状态变化的条件为 进程执行完成时 置为 结束 态 服务程序在将输出信息送输出井时 如发现输出井已满 将调用进程置 为 等待状态 1 SPOOLING 进程在进行输出时 若输出井空 则进入 等待状态 2 SPOOLING 进程输出一个信息块后 应立即释放该信息块所占的输出井 空间 并将正在等待输出的进程置为 可执行状态 服务程序在输出信息到输出井并形成输出请求信息块后 若 SPOOLING 进程处于等待态 则将其置为 可执行态 当用户进程申请请求输出块时 若没有可用请求时 调用进程进入 等 待状态 3 题目二十二 进程间通信题目二十二 进程间通信 1 设计目的 设计目的 Linux 系统的进程通信机构 IPC 允许在任意进程间大批量的交换数据 本实验的目的是了解和熟悉 Linux 支持的通信机制 共享存储区机制及信 号量机制 2 设计内容 设计内容 1 共享存储区的创建 链接和断开 2 消息的创建 发送和接收 3 编写程序 1 实现利用共享存储区进行进程通信 使用系统调用 shmget shmat shmdt 及 shmctl 编制一长度为 1k 的消息发送 和接收程序 19 4 编写程序 2 实现利用消息队列进行进程通信 使用系统调用 shmget shmat shmdt 及 shmctl 编制一长度为 1k 的消息发送 和接收程序 1 为了便于操作和观察结果 用一个程序作为 引子 先后 fork 两个子进程 SERVER 和 CLIENT 进行通信 2 SERVER 端建立一个 Key 为 75 的共享区 并将第一个字节置为 1 作为数据空的标志 等待其他进程发来的消息 当该字节的值发生 变化时 表示收到了消息 进行处理 然后再次把它的值设为 1 如 果遇到的值为 0 则视为结束信号 取消该队列 并退出 SERVER SERVER 每接收到一个消息后显示一句 server received 3 CLIENT 端使用 Key 为 75 的共享区 当共享取得第一个字节为 1 时 SERVER 端空闲 可发送请求 CLIENT 随即填入 9 到 0 期间等待 SERVER 端再次空闲 进行完这些操作后 CLIENT 退出 CLIENT 每发送一条信息后显示一句 client sent 4 父进程在 SERVER 和 CLIENT 均退出后结束 题目二十三 进程的管道通信和软中断通信题目二十三 进程的管道通信和软中断通信 1 设计目的 设计目的 加深对进程概念的理解 明确进程和程序的区别 进一步认识并发执行的 实质 并了解 Linux 系统中进程通信的基本原理 2 设计内容 设计内容 1 编制一段程序 实现进程的管道通信 使用系统调用 pipe 建立一条管道线 两个子进程 P1 和 P2 分别向管道各写一 句话 Child 1 is sending a message Child 2 is sending a message 而父进程则从管道中读出来自两个子进程的信息 显示在屏幕上 要求父进程先接收子进程 P1 发来的消息 再接收子进程 P2 发来的消息 2 编制一段程序 实现进程的软中断通信 使用系统调用 fork 创建两个子进程 再用系统调用 signal 让父进程捕捉键 盘上来的中断信号 即按 DEL 键 当捕捉到中断信号后 父进程用系统调用 Kill 向两个子进程发出信号 子进程捕捉到信号后分别输出下列信息后终止 20 Child 1 is killed by parent Child 2 is killed by parent 父进程等待两个子进程终止后 输出下列信息后终止 Parent is killed 题目二十四 题目二十四 linux 进程与线程通讯进程与线程通讯 1 设计目的 设计目的 深刻理解线程和进程的概念 掌握线程和进程在组成成分上的差别以及与 其相适应的通信方式和应用目标 2 设计内容 设计内容 以 Linux 系统进程和线程机制为背景 掌握 fork 和 clone 系统调用的 形式和功能以及与其相适应的高级通信方式 由 fork 派生的子进程之间通过 pipe 通信 由 clone 创建的线程之间通过共享内存通信 以生产者 消费者为例 通过实验理解 fork 和 clone 两个系统调用的区别 程 序要求能够创建 4 个进程或线程 其中包括两个生产者和两个消费者 生产者 和消费者之间能够传递数据 题目二十五 动态不等长存储资源分配算法题目二十五 动态不等长存储资源分配算法 1 设计目的 设计目的 理解动态异常存储分区资源管理 掌握所需数据结构和管理程序 了解各种存 储分配算法的优缺点 2 设计内容 设计内容 1 分析 Unix 最先适应 first fit ff 存储分配算法 即 map 数据结构 存 储分配函数 ma lloc 和存储释放函数 mfree 找出与算法有关的成分 2 修改上述算法有关成分 使其分别体现 BF best fit 最佳适应 分配原则 WF worst fit 最坏适应 分配原则 题目二十六 题目二十六 编程演示三种存储管理方式的地址换算过程编程演示三种存储管理方式的地址换算过程 1 设计目的 设计目的 21 理解页式 段式 段页式的逻辑地址向物理地址的转换过程 理解重定位的含 义 要求演示正确 清晰 编程所用工具不限 2 设计内容 设计内容 编程实现演示页式 段式 段页式的地址转换过程 1 分页方式的地址换算 2 分段方式的地址换算 3 段页式的地址换算 题目二十七 题目二十七 编程模拟多进程共享临界资源编程模拟多进程共享临界资源 1 设计目的 设计目的 理解多进程共享临界资源的原理 并编程实现 2 设计内容 设计内容 要求产生3 个进程 1 两个进程模拟需要进入临界区的用户进程 当需要进入临界区时 显示 进程x请求进入临界区 同时向管理进程提出申请 申请返回 表示进入了 临界区 在临界区中等待一段随机时间 并显示 进程x 正在临界区 当 时间结束 显示 进程x 退出临界区 同时向管理进程提出退出申请 当申 请返回 显示 进程x 已退出临界区 2 一个进程作为原语的管理进程 接受其他进程的临界区进入请求 如果允 许进入 则设置相应变量 然后返回 如果不允许进入 则进入循环等待 直 到允许为止 3 对临界区的访问应遵循空闲让进 忙则等待 有限等待 让权等待的准则 4 进程间通信可以采用信号 消息传递 管道或网络通信方式 题目二十八 题目二十八 文件系统的设计与实现文件系统的设计与实现 1 设计目的 设计目的 通过设计一个小型文件系统 进一步掌握文件管理的方法和技术 在实践 中去认识文件系统的实现原理 加深对文件系统存储 数据的安全性和一致性 理解 使学生初步具有研究 设计 编制和调试操作系统模块的能力 2 设计内容 设计内容 实现一个模拟文件系统 可为该文件系统设计相应的数据结构来管理目录 磁盘空闲空间 已分配空间等 提供文件的创建 删除 移位 改名等功能 提供良好的界面 可以显示磁盘文件系统的状态和空间的使用情况 提供 虚拟磁盘转储功能 可将信息存入磁盘 还可从磁盘读入内存 22 题目二十九 主存空间的分配与回收题目二十九 主存空间的分配与回收 1 设计目的 设计目的 本设计题目主要让大家熟悉主存的各种分配与回收 所谓分配 就是解决 多道作业或多进程如何共享主存空间的问题 所谓回收 就是当作业运行完成 时 将作业或进程所占用的主存空间归还给系统 主存的分配与回收的实现是 与主存储器的管理方式有关的 通过本次设计 帮助学生理解在不同的存储管 理方式下 如何实现主存空间的分配与回收 使学生初步具有研究 设计 编 制和调试操作系统模块的能力 2 设计内容 设计内容 采用可变式分区管理 使用首次或最佳适应算法实现主存的分配与回收 可以采用分区说明表或空闲区链来进行 设计多个作业或进程动态请求内存资 源的模拟系统 使用首次或最佳适应算法实现内存的分配与回收 实现可变式 分区管理 设计相应的内存分配算法 定义相关数据结构 以及输出显示每次 请求分配内存的结果和内存的已分配和未分配的状况 题目三十 题目三十 WindowsWindows 多线程控制台程序多线程控制台程序 1 1 设计目的设计目的 学习和掌握如何编写 Windows 多线程控制台程序 通过编写程序 加深对 进程和线程关系的理解 掌握多线程程序的执行和编写技巧 2 2 设计内容设计内容 写一个单进程多线程的 Windows 控制台程序 该程序在一个进程内建立 N 个线程来执行指定的任务 N 由命令行传递给系统 Win32 控制台程序中 主函数的格式如 Void main int argc char argv 可以获取命令行参数 通过 VC 工程 设置 的 C C 属性页设置应用程序为 MTD 多线程 利用 win32 API CreateThread 来生成线程 题目三十一 题目三十一 读者与写者问题 进程同步问题 1 设计目的 设计目的 了解进程同步的概念 理解信号量机制的原理 掌握运用信号量解决进程 同步问题的方法 进而学会运用进程的同步与互斥 设计要求 编程模拟读者与写者问题 要求显示结果 2 2 设计内容设计内容 1 多个进程共享一个文件 其中只读文件的称之为读者 其余只写文件的称 23 为写者 读者可以同时读 但是写者只能独立写 2 对 1 修改 使得它对写者优先 即一旦有写者到 后续的读者都必须 等待 而无论是否有读者在读文件 题目三十二 题目三十二 模拟文件管理系统 1 设计目的 设计目的 深入了解文件管理系统 初步掌握文件管理系统的实现方法 2 2 设计内容设计内容 编写一程序 模拟一个简单的文件管理系统 树型结构 目录下可以是目 录 也可以是文件 在此文件管理系统 可实现的操作有 改变目录 格式 cd 显示目录 格式 dir 创建目录 格式 md 删除目录 格式 rd 新建文件 格式 edit 删除文件 格式 del 退出文件系统 exit 实现参考 1 文件系统采用二叉树型存储结构 结点结构如下 Struct FileNode Char filename FILENAME LEN 文件名 目录名 Int isdir 目录 文件的识别标志 Int i nlink 文件链接数 Int adr 文件的地址 Struct FileNode parent child 指向父亲的指针和左孩子的指针 Struct FileNode sibling prev sibling next 指向前一个兄弟的指针和 后一个兄弟的指针 24 2 目录名和文件名支持全路径名和相对路径名 路径名各分量间用 隔 开 3 功能具体描述 改变目录 改变当前工作目录 目录不存在是给出出错信息 显示目录 显示指定目录下或当前目录下所有文件和一级目录 选做 带 s 参 数的 dir 命令 显示所有子目录 创建目录 在指定路径或当前路径下创建指定目录 重名时给出出错信息 删除目录 删除指定目录下所有文件和子目录 要删目录不空时 要给出提示 是否要删除 创建文件 创建指定名字的文件 只要创建表示文件的节点即可 内容及大小 不考虑 删除文件 删除指定文件 不存在时给出出错信息 退出文件系统 exit 4 总体流程 初始化文件目录 输出提示符 等待接受命令 分析键入的命令 对合法的命令 执行相应的处理程序 否则输出错误信息 继续等待新命令 直到键入 exit 退出为止 题目三十三题目三十三 内存的申请与释放内存的申请与释放 1 1 设计目的设计目的 了解操作系统内存分配的算法 2 2 设计内容设计内容 1 定义一个自由存储块链表 按块地址排序 表中记录块的大小 当请求 分配内存时 扫描自由存储块链表 址到找到一个足够大的可供分配的内存块 若找到的块大小正好等于所请求的大小时 就把这一块从自由链表中