操作系统一个小型操作系统的设计与实现课程设计
- 格式：docx
- 大小：75.12 KB
- 文档页数：29
南通大学计算机科学与技术学院 操作系统课程设计报告 专业： 学生姓名： 学号： 时间： 操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。
设计流程图 主流程图
A.处理机调度 1)先来先服务FCFS
N Y
先来先服务算法流程 2)时间片轮转法 时间片轮转算法流程图 B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图
开始的图形界面 处理机管理 存储器管理 缺页调度
先
来先服务
时间片轮转
首次适应法
最佳适应法
先进先出
LRU算法
开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中
的下一位移到首位 计算并打印进程的完成时刻、周转时间、带
权周转时间 其中：周转时间=完成时间-到达时间 带权周转时间=周转时间/服务时间
更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空
结束 首次适应算法回收流程图
申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于 延链查找下一个空闲区 到链尾了？
作业等待 返回 是
否
登记已分配表 返回分配给进程的内存首地址
开始 2）最佳适应法
开始 输入完成进程的标号 在分配区表中查找 释放区p下邻分区空前一个空闲区的后向指针指向p的后一个分区，p的后一个分区的前向指针指向p的前一个分区，且p的前一个分区大小更改为加上p的大小，释放p 释放区p上邻分区空 前一个分区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个分区，且p的后一个分区大小更改为加上p的大小
释放区p上下均邻空闲区 前一个空闲区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个空闲分区，且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p的下下个分区，如果p的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和p的下一个分区
释放区p上下均不邻空闲区 将p放在链首， 并修改其状态位为空闲 回收内存流程 C.虚拟存储器的缺页调度 1)先进先出FIFO
2）LRU 开始FIFO的缺页中断处理
查主存分块表
有空闲块可用？ 分配一块
J的修改标志=1？
J=p[HEAD]
输出“将J页复写入交换区” 输出“装入L页”
调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM) 修改主存分块表和页表
终止
N
Y N Y
FIFO淘汰算法流程
开始 释放分区与上空闲分区相邻
释放分区与下空闲分区相邻 结束 释放分区与下空闲分区相邻
T F T F T F 摘除链表中上分区。合并释放分区与上分区，将上空闲区长度修改为这二分区的长度。
摘除链表中上下分区。合并这三个分区，将上空闲区长度修改为三个分区的长度。
摘除链表中下分区。合并释放分区与下分区，将释放分区中长度修改为这二分区的长度。
将合并的或释放的分区按长度升序重新插入到自由链表中。 实现原理 主界面 设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。 A.处理机调度 1)先来先服务FCFS （一）任务 先来先服务的调度算法实现处理机调度。 （二）要求 1.实现对FCFS算法的模拟实现 2.计算出该算法的平均作业周转时间、平均带权作业周转时间。 （三）原理 按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。 （四）数据结构 structtask_struct {
开始LRU的缺页中断处理
查主存分块表
有空闲块可用？ 分配一块
J的修改标志=1？
找到栈底元素：J=p[M-1]
输出“将J页送到入交换区” 输出“装入L页”
调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L 修改主存分块表和页表
终止
N Y N
Y
LRU淘汰算法流程 charname;/*进程名称*/ intnumber;/*进程编号*/ floatcome_time;/*到达时间*/ floatrun_begin_time;/*开始运行时间*/ floatrun_time;/*运行时间*/ floatrun_end_time;/*运行结束时间*/ intpriority;/*优先级*/ intorder;/*运行次序*/ intrun_flag;/*调度标志*/ }tasks[MAX]; intfcfs()/*先来先服务算法*/ 进程名 链接指针 到达时间 估计运行时间 进程状态 进程控制块结构 （五）实现方法 建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。 （六）运行界面 测试数据： 作业名 到达时间 运行时间 A 0 28 B 0 9 C 0 3
执行FCFS算法如下： 2)时间片轮转法 （一）任务 只对进程的运行模拟，将其运行时间加一，判断要求运行时间与已运行时间是否相等，若相等则表示进程结束，进程退出调度，释放资源。 （二）要求 1.实现对RR算法的模拟实现 2.显示执行完一个时间片的结果。 （三）原理 时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 （四）数据结构 temp->state='R';//初始状态每个进程均为运行态 temp->allocation=0; //初始时进程均不占用cpu num+=temp->need_time;//用num来限制循环的次数 （五）实现方法 处理器调度总是选择标志单元指示的进程运行。执行： 已运行时间+1 来模拟进程的一次运行，表示进程已经运行过一个单位的时间。当一个进程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。 进程名 链接指针 到达时间 估计运行时间 进程状态 进程控制块结构 （六）运行界面 测试数据： 作业号 执行时间/s A 1 B 2 C 1 执行时间片轮转算法RR如下： B.存储器管理(可变式分区管理） 1)首次适应法 （一）任务 通过采用首次适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。 （二）要求 1.实现对FF算法的模拟实现 2.输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入已运行的进程ID。 （三）原理 FF算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查找，直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先使用低地址的空间。 （四）数据结构 intconstMEMO=256;//初始化常类型MEMO，用MEMO表示内存大小（常类型的变量或对象的值是不能被更新的） structFreeMemory { intID;intStartAdd;intSize; boolState;//定义state为布尔型变量，其值只有真（TRUE)和假（FALSE) FreeMemory*Next; }; FreeMemory*AllocTable=newFreeMemory;//建立全局管理表用于内与回收 FreeMemory*PtrforCycleFit=AllocTable;//为循环首次适应定义的指针，此指针用于指向当前查找的起始地址; //初始化内存函数 voidMemoryInit(FreeMemory*&tempAdd) { tempAdd->ID=0;//初始化当前进程为空 tempAdd->Size=MEMO;//初始化可分配空间为内存大小 tempAdd->StartAdd=0;//初始化起始地址为0 tempAdd->State=false;//初始化状态为未分配 tempAdd->Next=NULL;//初始化下一个进程也为空 } //反馈内存现态 voidDispMemory() { FreeMemory*temp=AllocTable;//全局管理表反映内存状态 cout<<"系统总内存:"
