操作系统—河海大学文天学院

河海大学文天学院河海大学文天学院 操作系统课程设计操作系统课程设计 姓姓 名名 胡 德 伟 班班 级级 08 级计算机科学与技术四班 指导老师指导老师 邓老师 时时 间间 2010 12 10 实验一实验一 进程调度进程调度 一 实验目的一 实验目的 通过一个简单的进程调度模拟程序的实现 加深对进程调度算法 进程切 换的理解 二 实验内容二 实验内容 采用动态优先数的方法 编写一进程调度程序模拟程序 模拟程序只进行 相应的调度模拟操作 不需要实际程序 提示 1 假定系统有五个进程 每一个进程用一个进程控制块 PCB 来代表 进 程控制块的格式为 进程名 指针 要求运行时间 优先数 状态 其中 进程名 作为进程的标识 假设五个进程的进程名分别为 P1 P2 P3 P4 P5 指针 按优先数的大小把五个进程连成队列 用指针指出下一个进程的进程 控制块的首地址 最后一个进程中的指针为 0 要求运行时间 假设进程需要运行的单位时间数 优先数 赋予进程的优先数 调度时总是选取优先数大的进程先执行 状态 可假设有两种状态 就绪 状态和 结束 状态 五个进程的初始状 态都为 就绪 用 R 表示 当一个进程运行结束后 它的状态为 结束 用 E 表示 2 在每次运行你所设计的处理器调度程序之前 为每个进程任意确定它 的 优先数 和 要求运行时间 3 为了调度方便 把五个进程按给定的优先数从大到小连成队列 用一 单元指出队首进程 用指针指出队列的连接情况 4 处理器调度总是选队首进程运行 采用动态改变优先数的办法 进程 每运行一次优先数就减 1 由于本实习是模拟处理器调度 所以 对被选中 的进程并不实际的启动运行 而是执行 优先数 1 要求运行时间 1 来模拟进程的一次运行 提醒注意的是 在实际的系统中 当一个进程被选中运行时 必须恢复进 程的现场 让它占有处理器运行 直到出现等待事件或运行结束 在这里省去 了这些工作 5 进程运行一次后 若要求运行时间 0 则再将它加入队列 按优先数 大小插入 且置队首标志 若要求运行时间 0 则把它的状态修改成 结束 E 且退出队列 6 若 就绪 状态的进程队列不为空 则重复上面 4 和 5 的步骤 直到所有进程都成为 结束 状态 7 在所设计的程序中应有显示或打印语句 能显示或打印每次被选中进 程的进程名以及运行一次后进程队列的变化 8 为五个进程任意确定一组 优先数 和 要求运行时间 启动所设计 的处理器调度程序 显示或打印逐次被选中进程的进程名以及进程控制块的动 态变化过程 三 进程调度处理过程三 进程调度处理过程 否 是 是 否 计时中断 中断总处理过程 计时中断处理 当前进程 是否用完 修改 g needReschedule 为 true g needReschedule 执行调度算法选择下一 个进程 切换到下一个进程 此进程可以是原来的进 程也可以是调度算法选择的进程 四 源程序分析四 源程序分析 08 计算机 学号 08031421 操作系统 进程调度 用链表实现 include include include include typedef struct pcb 进程的 PCB 块 char id 进程名 char state 进程的状态 int prior 进程的优先级 int time 进程的时间 pcb next 指向结构体的指针 pcb plist void insert plist if head next NULL 如果 head 指针为空 则应该插入到对头 head next p p next NULL else s head r s next while r NULL r r next 找到新节点 q 的插入位置 循环后 q 节点应该处于结点 s r 之间 如果 r 为空 则未尾结点 p next r s next p pcb m cout endl cout endl plist p p head cout 进程 id 进程优先级 进程所需的运行时间 进程的状态 next p p next cout id prior time state cout next if m time 0 cout id 进程已经运行完毕 要从链表中删除 next head next next 将该结点从链表中删除 else head next m next 对头结点进行重新插入 insert head m cout endl endl void create plist pcb p for i 0 i n i p plist malloc sizeof pcb cout 请输入第 i 1 个进程名 字符型 优先级 整型 运行时间 整型 p id p prior p time p state r 初始的转台全部为 r insert head p 将结点插入到合理的位置 void yunxing plist cout 开始进程调度 cout next NULL m head next cout 进程 id prior m prior 1 m time m time 1 if m time 0 如果头结点已经运行完 将状态改为 e head next state e showjincheng head void main clock t start finish double shijian int a 进程数 int b 是否确认 do 确认用户的选择 如果输入错误 可以重新输入 do 控制进程的数目在合理的范围内 system cls cout endl endl cout endl 姓名 胡德伟 endl cout endl 学号 08031421 endl cout endl 班级 08 计算机四班 endl cout endl 指导老师 邓老师 endl cout endl 实验一 进程调度 endl cout endl endl cout a if a 10 a 10 cout 您所创建的进程数不能大于 10 请重新输入 endl else cout 您所创建的进程数不能为负数 请重新输入 10 a 0 cout 您所创建的进程数为 a endl cout 确认请按 1 重新输入进程数请按 0 b if b 0 system cls cout a while b 0 cout 尊敬的用户 您所创建的进程数为 a next NULL create head a 通过插入的方法构造链表 cout endl cout 初始化创建的进程为 endl start clock showjincheng head 显示链表的内容 yunxing head 对进程进行操作的过程 cout endl endl cout 所有的进程都已经运行结束了 endl cout endl finish clock shijian double finish start CLOCKS PER SEC cout 程序的执行时间为 shijian ms endl cout endl 实验二实验二 存储管理存储管理 一 实验目的一 实验目的 存储管理的主要功能之一是合理地分配空间 请求页式管理是一种常用的 虚拟存储管理技术 本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 了解虚 拟存储技术的特点 掌握请求页式存储管理的页面置换算法 二 实验内容二 实验内容 通过随机数产生一个指令序列 共320条指令 指令的地址按下述原则生成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点 m 顺序执行一条指令 在前地址 0 m 1 中随机选取一条指令并执行 该指令的地址为 m 顺序执行一条指令 其地址为 m 1 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行 320 次指令 1 将指令序列变换成为页地址流 设 页面大小为 1K 用户内存容量为 4 页到 32 页 用户虚存容量为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令 在虚存中的存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 按以上方式 用户指令可组成 32 页 2 计算并输出下述各种算法在不同内存容量下的命中率 先进先出的算法 FIFO 最近最久未使用算法 LRU 命中率 1 页面失效次数 页地址流长度 在本实验中 页地址流长度为 320 页面失效次数为每次访问相应指令时 该指令所对应的页不在内存的次数 三 虚拟内存实现原理图三 虚拟内存实现原理图 4 源程序分析源程序分析 08 计算机 4 班 include include 队列 include 获取系统的时间 using namespace std typedef struct 页面的结构体信息 int id 页面的 id 号 内存分配和回收机制 请求页机制 缓存和刷新机制 地址映射机制 交 换 机 制 int staytime 在内存中的停留的时间 int unusualtime 多久未被使用的时间 Cpage deque queue 可以直接的使用队列的方法 deque interPage 内存中的页面 deque exterPage 外存中页面 int xianzaiweizhi int lacknum 2 0 0 缺失的页面数 int getRandNum int range 返回 0 range 范围内的整数 return int rand range 根据 srand 函数得到随机数 void InitDevice 初始化运行队列 按照 25 50 25 的标准生 成 srand int time NULL 通过调用系统时间 产生随机数 并强制的转化成整型 int yehao getRandNum 320 随机选择第一条指令 queue push back yehao 将其插入队列 if yehao 319 queue push back yehao 1 顺序执行下一条指令 while queue size 320 一直运行到队列中的个数等于 320 yehao getRandNum yehao 跳转到 m1 属于 0 m 1 queue push back yehao 将 m1 插入队列 if yehao 319 queue push back yehao 1 将 m1 1 插入队列 int temp 320 yehao 2 yehao yehao 2 getRandNum temp 跳转到 m2 属于 m 2 319 queue push back yehao 插入队列 if yehao 320 如果队列中的个数大于 320 则把多余的队列进行出栈的操作 queue pop back void InitMemoryQueue 初始化页面 xianzaiweizhi 0 exterPage clear 对外存的页面进行清除 interPage clear 对内存的页面进行清除 for int i 0 i 32 i Cpage temp temp id i temp staytime 0 停留时间和未使用的时间都初始化未 0 temp unusualtime 0 exterPage push back temp 将产生的页面进行入队的操作 int shuyunageyemian int cmdId 通过强制转换成整数的形式判断指令属于哪个页面 return int cmdId 10 int yemianzhuantai int PageId bool sign 分别在内外存中查找页面存在返回位置不存在返回 1 if sign 在内存中进行查找 for int i 0 i interPage size i if PageId interPage i id return i else 在外存中进行查找 for int j 0 j exterPage size j if PageId exterPage j id return j return 1 如果内外存中都不在的话 返回 1 void directFlod int PageId 当内存空间还有剩余时直接调入 int status yemianzhuantai PageId false if status 1 return interPage push back exterPage status 向内存插入 exterPage erase exterPage begin status 从外存删除队列开始的位置加上偏移量 int fifo FIFO 算法中查找在内存中呆了最久的页面 int max 0 for unsigned i 1 iinterPage max staytime 找到在内存中停留时间时间最长 max i return max 返回停留时间最长的最大值 int lru LRU 算法中查找最久未使用的页面 int max 0 for int j 0 jinterPage max unusualtime 找到最久未被使用的算法 max j return max 返回未被使用的最大值 bool Manage int count int PageId 当内存已经满了需要按照算法调度 int status yemianzhuantai PageId false 获取执行页面在外存中的索引地址 if status 1 return false int targetStatus 0 if count 0 targetStatus fifo 根据 fifo 算法内存中需要交换的位 置 else if count 1 targetStatus lru 根据 lru 算法内存中需要交换的位置 interPage targetStatus staytime 0 将要交换的内存 页面的停留时间和最近多久未被使用的时间进行初始化为 0 interPage targetStatus unusualtime 0 swap exterPage status interPage targetStatus 内外层中的页面进行交换 return true void run int count while xianzaiweizhi 320 如果现在的位置在合理的范围内 for int i 0 i interPage size i 对内存中的页面进行操作 interPage i staytime 内存页面的停留时间 interPage i unusualtime 内存页面未使用的时间 int PageId shuyunageyemian queue xianzaiweizhi int status 1 找到当前将要执行的指令的页面号 初始化为 1 if status yemianzhuantai PageId true 1 如果查找的页面 在内存中 将最近最久时间标记为 0 并结束本次的操作 interPage status unusualtime 0 continue 如果不在内存中 所执行的操作 lacknum count 缺失的页面数 1 if interPage size 4 内存的队列未满 将该页面从外存中调入到内存中去 directFlod PageId 调入的操作 else Manage count PageId 内存的队列已满 则根据算法进行调换 void main cout endl endl cout endl 姓名 胡德伟 endl cout endl 学号 08031421 endl cout endl 班级 08 计算机四班 endl cout endl 指导老师 邓老师 endl cout endl 实验二 存储管理 endl cout endl endl InitDevice int i 循环的控制 int b 换行的控制 int flag 进行何种操作的控制 b 0 cout endl 产生的随机数为 endl for i 0 i 319 i cout queue i b if b 12 0 cout endl cout endl int count 0 while count 2 InitMemoryQueue run count count do 由用户选择输出的结果 cout 请输入您要进行的操作 endl cout 1 先进先出的算法调度 endl cout 2 最近最久未使用的算法调度 flag if flag 1 先进先出的算法调度 cout 先进先出的算法调度的缺页率为 endl cout double lacknum 0 320 100 endl else if flag 2 最近最久的算法调度 cout 最近最久未使用的算法调度的缺页率为 endl cout double lacknum 1 320 100 endl cout 是否继续 1 继续 0 退出 flag while flag 1 满足此条件 重新做里面的内容 system PAUSE 实验三实验三 文件系统设计文件系统设计 一 实验目的一 实验目的 通过一个简单多用户文件系统的设计 加深理解文件系统的内部功能及内 部实现 二 实验内容二 实验内容 为 Linux 系统设计一个简单的二级文件系统 要求做到以下几点 1 可以实现下列几条命令 至少 4 条 login 用户登录 dir 列文件目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 2 列目录时要列出文件名 物理地址 保护码和文件长度 3 源文件可以进行读写保护 三 程序流程图三 程序流程图 否 是 开始 选择操作 创建文件 打开文件 读文件写文件 删除文件 注销 结束 4 部分源程序部分源程序 1 Read 函数函数 函数功能 从系统文件上读取文件数据到文件缓冲区 函数参数 文件指针 缓冲区地址 需要读出文件的字节数 函数返回值 若读取成功 返回实际读取的文件数 Static int Reand struct File file void buf ulong t numBytes Struct PFAT file pfatfile struct PFAT file file fsData Struct PFAT Instance instance struct PAFT Instance File mountpoint fsData Ulong t start file filepos Ulong t end file filepos numBytes Ulong t startblock endblock curblock Ulong t i 若读的文件长度大于 INT MAX 则返回无效 If numBytes INT MAX Return EINVALID 确保读取的文件的长度是有效的 若读取的位置超出文件范围 则无效 If start file endpos end file endpos endfilepos numBytes file endpos Return EINVALID 检测需要读取的数据是否都在文件缓冲区中 Startblock start SECTOR SIZE SECTOR SIZE Endblock round up block end SECTOR SIZE 遍历文件系统 查取需要读取的文件块 Curlock pfatfile entry firstblock For i 0 i stratblock Int rc 0 对文件进行互斥锁 确保每次仅有一个进程对文件进行读取 Mutex lock If Is Bit set pfatfile validlockSet i 读一个磁盘快到文件数据缓冲区 Dubeg reading file bloock lu devic block lu n i curblock Rc block read file mountpoint dev curblock pfatfile fileDatecache i SECTOR SIZE If rc 0 置该块的已读标记 Set bit pfatfile validblockset i Mutex unlock If rc 0 Return rc 继续读下一块数据 Ulong t nextblock instance fat curblock Curblock nextblock 将缓冲区数据复制到调用读函数的进程缓冲区 Memcpy buf pfatfile filedatacache start numBytes Debug read satisfiled n Reurn numbytes 2 Write 函数函数 函数功能 将文件缓冲区的数据些入文件系统 函数参数 文件指针 缓冲区地址 写入文件的字节数 函数返回值 错误标志 EACCESS Static int write struct file file void buf ulong t numBytes 因为文件系统是只读的 所以不允许写入 直接返回标志 Return EACCESS 3 OPEN 函数函数 函数功能 打开文件系统文件 函数参数 文件系统加载点指针 路径名 打开方式 文件指针 Statitc int open struct mount point mountpoint const char path int mode struct file pfile Int