计算机操作系统

1 实验一实验一 进程调度进程调度 实验目的 实验目的 通过这次实验 加深对进程概念的理解 进一步掌握进程状态的转变 进程调度的策 略及对系统性能的评价方法 预习内容 预习内容 阅读教材 计算机操作系统 第二章和第三章 掌握进程管理及调度相关概念和原理 计算机操作系统实验报告 2 基本实验内容 基本实验内容 进程调度算法 采用最高优先数优先的调度算法 即把处理机分配给优先数最高的进 程 和先来先服务算法 每个进程有一个进程控制块 PCB 表示 进程控制块可以包含如下信息 进程名 优先数 到达时间 需要运行时间 已用 CPU 时间 进程状态等等 进程的优先数及需要的运行时间可以事先人为地指定 也可以由随机数产生 进程的 到达时间为进程输入的时间 进程的运行时间以时间片为单位进行计算 每个进程的状态可以是就绪 W Wait 运行 R Run 或完成 F Finish 三种状态 之一 就绪进程获得 CPU 后都只能运行一个时间片 用已占用 CPU 时间加 1 来表示 如果运行一个时间片后 进程的已占用 CPU 时间已达到所需要的运行时间 则撤消该 进程 如果运行一个时间片后进程的已占用 CPU 时间还未达所需要的运行时间 也就是进 程还需要继续运行 此时应将进程的优先数减 1 即降低一级 然后把它插入就绪队列等 待 CPU 每进行一次调度程序都打印一次运行进程 就绪队列 以及各个进程的 PCB 以便进 行检查 重复以上过程 直到所要进程都完成为止 实现提示 实现提示 用 C 语言实现提示 程序中进程可用 PCB 表示 其类型描述如下 struct pcb 定义进程控制块 PCB char name 10 char state int priority int ntime 所需运行时间 int rtime 已经运行的时间 struct pcb link ready NULL p typedef struct pcb PCB 3 实验题实验题 1 编写并调试一个模拟的进程调度程序 采用 最高优先数优先 调度算法对五个进程进行 调度 最高优先数优先 调度算法的基本思想是把 CPU 分配给就绪队列中优先数最高 的进程 静态优先数是在创建进程时确定的 并在整个进程运行期间不再改变 动 态优先数是指进程的优先数在创建进程时可以给定一个初始值 并且可以按一定原则 修改优先数 例如 在进程获得一次 CPU 后就将其优先数减少 1 或者 进程等待的 时间超过某一时限时增加其优先数的值 等等 编写并调试一个模拟的进程调度程序 采用 轮转法 调度算法对五个进程进行调度 轮 转法可以是简单轮转法 可变时间片轮转法 或多队列轮转法 简单轮转法的基本思想是 所有就绪进程按 FCFS 排成一个队列 总是把处理机分配给队首的进程 各进程占用 CPU 的时间片相同 如果运行进程用完它的时间片后还为完成 就把它送回到就绪队列的末尾 把处理机重新分配给队首的进程 直至所有的进程运行完毕 源程序 源程序 4 clude include include include include using namespace std struct pcb pcb const string 进程名 int priority 优先级 int needtime 需要时间 int usedtime 已用时间 int runtime 运行时间 string w string state 进程状态 int main string a int p n deque vec cout please cin process name priority needtime five times a p n 创建五个进程 pcb process a p n vec push back process while vec empty 判断是否为空 sort vec begin vec end pcb a pcb b return a priority b priority 进程按优先级从高到底排序 pcb 提取优先级最高的进程 process usedtime 已运行时间 1 if process usedtime process needtime 判断是否运行完毕 cout process name endl 输出最先运行完的进 程 vec pop front 撤销进程 else process priority 优先级减一 5 return 0 实验二实验二 作业调度作业调度 实验目的 实验目的 通过这次实验 加深对作业调度算法的理解 预习内容 预习内容 阅读教材 计算机操作系统 第三章 掌握作业调度相关概念和原理 基本实验内容 基本实验内容 由于在单道批处理系统中 作业一投入运行 它就占有计算机的一切资源直到作业完 6 成为止 因此调度作业时不必考虑它所需要的资源是否得到满足 它所占用的 CPU 时限等 因素 作业调度算法 采用先来先服务 FCFS 调度算法 即按作业提交的先后次序进行调 度 总是首先调度在系统中等待时间最长的作业 每个作业由一个作业控制块 JCB 表示 JCB 可以包含如下信息 作业名 提交时间 所需的运行时间 所需的资源 作业状态 链指针等等 作业的状态可以是等待 W Wait 运行 R Run 和完成 F Finish 三种状态之一 每个作业的最初状态总是等待 W 各个等待的作业按照提交时刻的先后次序排队 总是首先调度等待队列中队首的作业 每个作业完成后要打印该作业的开始运行时刻 完成时刻 周转时间和带权周转时间 这 一组作业完成后要计算并打印这组作业的平均周转时间 带权平均周转时间 实验题实验题 1 编写并调试一个单道处理系统的作业等待模拟程序 作业等待算法 分别采用先来先 服务 FCFS 最短作业优先 SJF 响应比高者优先 HRN 的调度算法 对每种调 度算法都要求打印每个作业开始运行时刻 完成时刻 周转时间 带权周转时间 以 及这组作业的平均周转时间及带权平均周转时间 以比较各种算法的优缺点 2 编写并调度一个多道程序系统的作业调度模拟程序 作业调度算法 采用基于先来先 服务的调度算法 可以参考课本中的方法进行设计 对于多道程序系统 要假定系统 中具有的各种资源及数量 调度作业时必须考虑每个作业的资源要求 7 源程序 源程序 include include include include using namespace std int base time int begin time 0 struct jcb 定义作业块 jcb const string 作业名 int need time int arrive time 每次调用到 达时间 1 void FCFS deque vec 先来先服务 调度算法 double turn time 0 double with authority turn time 0 auto n vec size for auto iter vec begin iter vec end iter cout 进程名 name endl 开始时间 begin time endl 完成时间 need time endl 周转时间 need time iter arrive time endl 带权周转时间 need time iter arrive time iter need time need time iter arrive time 累加进程周转时间 with authority turn time double begin time iter need time iter arrive time iter need time 累 加进程带权周转时间 begin time iter need time cout 平均周转时间 turn time n endl 平均带权周转时间 with authority turn time n endl void SJF deque vec sort vec begin vec end jcb a jcb b return a need time b need time 按最短作业优先排序 FCFS vec 调用函数 FCFS int main cout please cin process name needtime endl string a int n 9 deque vec while cin a n 循环输入进程信息 jcb process a n vec push back process FCFS vec SJF vec return 0 10 实验三实验三 分区式存储管理分区式存储管理 实验目的 实验目的 了解动态分区分配方式中使用的数据结构和分配算法 并进一步加深对动态分区 存储管理方式及其实现过程的理解 通过这次实验 加深对内存管理的认识 进一步 掌握内存的分配 回收算法的思想 预习内容 预习内容 阅读教材 计算机操作系统 第四章 掌握存储器管理相关概念和原理 实验内容 实验内容 用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc 和回 收过程 free 其中 空闲分区通过空闲分区链来管理 在进行内存分配时 系统优先使用 空闲区低端的空间 假设初始状态下 可用的内存空间为 640KB 其中操作系统占用 64KB 并有下列的请 求序列 作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200KB 作业 3 释放 100KB 作业 1 释放 130KB 作业 5 申请 140KB 作业 6 申请 60KB 作业 7 申请 50KB 作业 6 释放 60KB 请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收 要求每次分配和 回收后显示出空闲内存分区链的情况 实现提示 实现提示 C 语言 语言 程序中自由链队列的结点类型可描述如下 struct freelink 11 int len address len 为分区长度 address 为分区起始地址 struct freelink next 内存占用区用链表描述 其结点类型描述如下 struct busylink char name 作业或进程名 name S 表示 OS 占用 int len address struct busylink next 并设全程量 struct freelink free head NULL 自由链队列 带头结点 队首指针 struct busylink busy head NULL 占用区队列队 带头结点 首指针 busy tail NULL 占用区队列队尾指针 源程序 源程序 include include include using namespace std vector Memory vec 576 首次适应分配算法 void alloc int n for auto iter Memory vec begin iter Memory vec end iter if n iter iter iter n break int num 0 for auto iter Memory vec begin iter Memory vec end iter cout 第 num 空闲块的空闲内存 iter endl num 回收算法 void free int n Memory vec push back n int num 0 for auto iter Memory vec begin iter Memory vec end iter cout 第 num 空闲块的空闲内存 iter endl 12 num int main cout Need Memory Please cin m Or Free Memory Please cin f tmp switch tmp case m cout please cin meed Memory num alloc num cout Need Memory Please cin m Or Free Memory Please cin f endl break case f cout please cin Free Memory nnn free nnn cout Need Memory Please cin m Or Free Memory Please cin f endl break return 0 13 14 实验五实验五 磁盘调度算法磁盘调度算法 实验目的 实验目的 本实验的目的是通过实验 对磁盘的调度算法有更好的理解 进一步掌握各种调度算 法 预习内容 预习内容 阅读教材 计算机操作系统 第五章 掌握磁盘调度相关概念和原理 实验内容 实验内容 磁盘调度算法 采用先来先服务算法 fcfs 最短寻道时间优先 sstf 扫描算法 scan 和 循环扫描算法 cscan 输入为一组作业的磁道请求 磁道号顺序为 55 58 39 18 90 160 38 184 从 100 号磁 道开始 输出为按选择的算法执行时的磁头移动轨迹 并能计算平均寻道长度 源程序 源程序 include include include include include include using namespace std 先来先服务算法实现 void FCFS vector vec double track seeking length 0 寻道长度 track seeking length abs vec begin 100 int n vec size cout FCFS 寻道路径 for auto iter vec begin iter vec end 1 iter track seeking length abs iter 1 iter abs 绝对值函数 cout iter cout vec end 1 endl cout FCFS 平均寻道时间 track seeking length n endl 最短寻道时间优先算法实现 void SSTF vector vec 15 double track seeking length 0 寻道时间 int key 100 int n vec size cout SSTF 寻道路径 map ma for auto c vec ma insert abs c key c cout second track seeking length ma begin first key ma begin second ma erase ma begin first while ma empty map tmp for auto iter ma begin iter ma end iter tmp insert abs iter second key iter second cout second key tmp begin second track seeking length tmp begin first for auto b ma begin b ma end b if b second key ma erase b first break cout endl cout SSTF 平均寻道时间 track seeking length n endl 扫描算法实现 void SCAN vector vec int begin track num 100 double track seeking length 0 int n vec size int tmp 0 cout SCAN 寻道路径 begin track num vector big tmp min tmp for auto c vec 16 if c begin track num big tmp push back c else min tmp push back c sort big tmp begin big tmp end sort min tmp begin min tmp end int a int b return a b track seeking length big tmp begin begin track num 计算开始和第一个磁 道之间的磁道数 track seeking length big tmp end 1 min tmp begin 计算磁道折回来时移 动的磁道数 for auto c big tmp cout c for auto c min tmp cout c for auto iter big tmp begin iter big tmp end 1 iter track seeking length iter 1 iter for auto iter min tmp begin iter min tmp end 1 iter track seeking length iter iter 1 cout endl SCAN 平均寻道时间 track seeking length n endl void CSCAN vector vec int begin track num 100 double track seeking length 0 int n vec size int tmp 0 cout CSCAN 寻道路径 begin track num vector big tmp min tmp for auto c vec if c begin track num big tmp push back c else min tmp push back c sort big tmp begin big tmp end 17 sort min tmp begin min tmp end int a int b return a b track seeking length big tmp begin begin track num 计算开始和第一个磁 道之间的磁道数 track seeking length big tmp end 1 min tmp begin 计算磁道折回来时移 动的磁道数 for auto c big tmp cout c for auto c min tmp cout c for auto iter big tmp begin iter big tmp end 1 iter track seeking length iter 1 iter for auto iter min tmp begin iter min tmp end 1 iter track seeking length iter 1 iter cout endl CSCAN 平均寻道时间 track seeking length n endl int main vector vec int a while cin a vec push back a FCFS vec SSTF vec SCAN vec CSCAN vec return 0 18 19 实验七实验七 位示图法磁盘存储空间分配和回收位示图法磁盘存储空间分配和回收 实验目的 实验目的 磁盘存储管理的主要功能之一是合理的分配空间和及时回收空间 位示图法是一种常 用的虚拟存储管理技术 本实验的目的是位示图算法模拟设计 了解磁盘存储的特点 掌 握位示图的管理方法 预习内容 预习内容 阅读教材 计算机操作系统 第六章 位示图的相关概念和原理 实验内容 实验内容 要求显示程序运行前和运行后的位示图 以及分配和回收磁盘的物理地址过程 实验提示 实验提示 假定现有一个磁盘组 共 40 个柱面 每个柱面 4 个磁道 每个磁道又划分成 4 个物理 记录 磁盘的空间使用情况用位示图表示 位示图用若干个字构成 每一位对应一个磁盘 块 1 表示占用 0 表示空闲 为了简单 假定字长为 16 位 其位示图如图所示 系统设 一个变量 S 记录磁盘的空闲块个数 位0123456789101112131415 01111110100111110 1 2 39 申请一个磁盘块时 由磁盘块分配程序查位示图 找出一个为 0 的位 并计算磁盘的 物理地址 由位示图计算磁盘的相对块号的公式如下 相对块号 字号 16 位号 之后再将相对块号转换成磁盘的物理地址 柱面号 相对块号 16 的商 即柱面号 字号 磁道号 相对块号 16 的余数 4 的商 即 位号 4 的商 物理块号 相对块号 16 的余数 4 的余数 即 位号 4 的余数 释放一个相对物理块时 运行回收程序 计算该块在位示图中的位置 再把相应位置 0 计算公式如下 20 先由磁盘地址计算相对块号 相对块号 柱面号 16 磁道号 4 物理块号 再计算字号和位号 字号 相对块号 16 的商 也即字号 柱面号 位号 磁道号 物理块数 每磁道 物理块号 按照用户要求 申请分配一系列磁盘块 运行分配程序 完成分配 然后将分配的相 对块号返回用户 并将相对块号转换成磁盘绝对地址 再