一个小型操作系统设计与实现.docx
《一个小型操作系统设计与实现.docx》由会员分享，可在线阅读，更多相关《一个小型操作系统设计与实现.docx（39页珍藏版）》请在冰点文库上搜索。
南通大学计算机科学与技术学院
操作系统课程设计报告
专 业：
计嵌151学生姓名：
王志宏学号：
1513052018
时间：
2017/6/28
设计一个小型的操作系统
设计要求
将本学期三次的实验集成实现：
1.中断处理
2.作业调度
3.PV原语
4.死锁
5.页面替换
6.磁盘调度
（一）设计流程图
主流程图
开始的图形界面
作业调度
中断处理
PV原语 死锁
页面替换
磁盘调度
银
先
LR
行
进
U
家算法
先出
算
算法
哲
时 先 学 先
钟 来 家 来
先
先
吃
服
服
通
务
务
心
计算并打印进程的完成时刻、周转时间、带
权周转时间
其中：
周转时间=完成时间-到达时间带权周转时间=周转时间/服务时间
更改计时器的当前时间,即下一刻进程的开始时间
当前时间=前一进程的完成时间+其服务时间
N
数组为空
1.中断处理
模拟时钟中断的产生及设计一个对时钟中断事件进行处理的模拟程序。
计算机系统工作过程中，若出现中断事件，硬件就把它记录在中断寄存器
中。
中断寄存器的每一位可与一个中断事件对应，当出现某中断事件后，对应的中断寄存器的某一位就被置成―1‖。
处理器每执行一条指令后，必须查中断寄存器，当中断寄存器内容不为―0‖时，说明有中断事件发生。
硬件把中断寄存器内容以及现行程序的断点存在主存的固定单元，且让操作系统的中断处理程序占用处理器来处理出现的中断事件。
操作系统分析保存在主存固定单元中的中断寄存器内容就可知道出现的中断事件的性质，从而作出相应的处理。
本实习中，用从键盘读入信息来模拟中断寄存器的作用，用计数器加1来模拟处理器执行了一条指令。
每模拟一条指令执行后，从键盘读入信息且分析，当读入信息=0时，表示无中断事件发生，继续执行指令；当读入信息=1时，表示发生了时钟中断事件，转时钟中断处理程序
2.作业调度
1）先来先服务FCFS
开始
初始化进程控制块，让进程控制块按进
程到达先后顺序让进程排队
调度数组中首个进程，并让数组中
的下一位移到首位
Y
结束
先来先服务算法流程
3.PV原语
1）哲学家吃通心面问题
哲学家吃通心面：
在这道题目里，每把叉子必须互斥使用，当一位哲学家吃通心面之前必须执行两个P操作，获得自己左右两边的叉子，在吃完通心面后必须执行两个V操作，放下叉子。
4.死锁
1）银行家算法
5.页面替换
1）先进先出FIFO
开始FIFO的缺页中
断处理
有空闲块
可用？
Y
N
J=p[HEAD]
N
J的修改
标志=1？
Y
输出“将J页复写入交换区”
分配一块
查主存分块表
输出“装入L页”
调整FIFO队列，将L插入队尾（HEAD=（HEAD+1）modM）
修改主存分块表和页表
终止
FIFO淘汰算法流程
2）LRU
开始LRU的缺页中断处理
输出“装入L页”
查主存分块表
有空闲块
可用？
Y
N
找到栈底元素：
J=p[M-1]
N
J的修改
标志=1？
Y
输出“将J页送到入交换区”
分配一块
调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L
修改主存分块表和页表
终止
LRU淘汰算法流程
6.磁盘调度
1）先来先服务算法FCFS）
（二）实现原理
主界面
设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。
1.中断
2.作业调度
1）先来先服务FCFS
（1）任务
先来先服务的调度算法实现处理机调度。
（2）要求
1.实现对FCFS算法的模拟实现
2.计算出该算法的平均作业周转时间、平均带权作业周转时间。
（3）原理
按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。
（4）数据结构
structtask_struct
{
charname; /*进程名称*/
intnumber; /*进程编号*/
floatcome_time; /*到达时间*/floatrun_begin_time; /*开始运行时间*/floatrun_time; /*运行时间*/floatrun_end_time; /*运行结束时间*/intpriority; /*优先级*/
intorder; /*运行次序*/
intrun_flag; /*调度标志*/
}tasks[MAX];
intfcfs（）/*先来先服务算法*/
进程名
链接指针
到达时间
估计运行时
间
进程状态
进程控制块结构
（5）实现方法
建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头
结点）依次调度到最后一个作业（尾结点）。
（6）运行界面测试数据：
作业名
到达时间
运行时间
A
0
28
B
0
9
C
0
3
执行FCFS算法如下：
3.死锁
假定本系统中的各个所需资源均是独占型资源，在进程运行的过程中不再
释放，故只需要遍历链表将各个进程中所需的资源统计出来，只要不大于系统中预设的即可，一旦进程所需的资源大于系统中的最大量，给予用户选择kill一进程，已达到释放资源的目的。
死锁检测函数：
voidsisuo（）
死锁解除函数：
voidsafe（）
4.缺页调度
1）先进先出FIFO
（1）任务
采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。
（2）要求
1.实现对FIFO算法的模拟实现
2.输出每次执行的结果。
（3）原理
基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。
（4）数据结构
voidFIFO（）{
intlength;
intfifo[100]={0};intpageLength;
intfifoPage[100]={0};inti,j;
cout<<" ***********************先进先出算法
**************************"<length=9;for（i=1;i<=length;i++）{
intflag=0;for（j=1;j<=pageLength;j++）{
if（fifo[i]==fifoPage[j]）{flag=1;j=pageLength+1;
}elseif（fifoPage[j]==0）{fifoPage[j]=fifo[i];j=pageLength+1;flag=1;
}
if（flag==1）
{
}
else
{
}
cout<<" →淘汰"<fifoPage[j]=fifoPage[j+1];
}
fifoPage[pageLength]=fifo[i];
}
（5）实现方法
当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为0.假设分配给每个进程的内存块数固定。
当队列满需淘汰时，淘汰最先进入主存的一页。
若该页修改过，还有存入磁盘。
然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标志。
（6）运行界面测试数据：
页表长度：
9；页框长度：
3；
页面请求数列：
4,4,3,5,1,1,2,3,2
执行先进先出FIFO算法结果如下：
2）LRU
（1）任务
采用先进先出LRU算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。
（2）要求
1.实现对LRU算法的模拟实现
2.输出每次执行的结果。
（3）原理
最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。
在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。
如
果主存中已无空闲块，可采用LRU算法进行缺页处理。
（4）数据结构
voidLRU（）
{
intlength;
intlru[100]={0};intpageLength;
intlruPage[100]={0};inti,j;
cout<<" ***********************最近最少使用LRU算法
***********************"<length=9;for（i=1;i<=length;i++）{
intflag=0;for（j=1;j<=pageLength;j++）{
if（lru[i]==lruPage[j]）{
for（intcc=j;cc>0;cc--）{lruPage[cc]=lruPage[cc-1];
}
lruPage[1]=lru[i];flag=1;j=pageLength+1;
}elseif（lruPage[j]==0）{for（intvv=j;vv>0;vv--）{
lruPage[vv]=lruPage[vv-1];
}
lruPage[1]=lru[i];j=pageLength+1;flag=1;
}
}
if（flag==1）
{
}
else
{
<cout<<" →淘汰"<for（j=pageLength;j>0;j--）{lruPage[j]=lruPage[j-1];
}
lruPage[1]=lru[i];
}
（5）实现方法
当采用LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为0.假定分配给每个进程的内存块数固定不变。
当队列满需淘汰时，操作系统选择栈底元素淘汰，其他元素向下移一个位置，将新调入页放栈指针指示的栈顶。
当访问的页在栈中时，还应调整页从当前位置到栈顶。
（6）运行界面
测试数据：
页表长度：
9；页框长度：
3；
页面请求数列：
2,3,5,1,5,5,4,4,3
执行最近最少使用LRU算法结果如下：
5.磁盘调度
1）先来先服务算法FCFS）
这是一种比较简单的磁盘调度算法。
它根据进程请求访问磁盘的先后次序进行调度。
此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。
此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
（三）总结与体会
通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近最少使用算法有了更详尽的认识。
在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。
从这次实验中我发现我对于c++掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。
此外我还更深入的理解了各个进程调度算法，及实现过程。
在编写程序时查询了很多资料，间接提高了我的搜索能力。
在此次课程设计过程中，对进程的相关知识有了一定的加深。
特别是对进程的进程控制块的存在和价值有了更进一步的认识。
在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。
特别是设计先来先服务调度算法和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。
对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。
在设计此模拟操作系统的课设中，也加深了对c++知识的把握。
解决了一些以往在编程中遇到了困难。
通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。
另外，我觉得此次课程设计虽然主要问题是在编程上，但是经过不断的去调试，还是成功的调试了出来。
但是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！
源代码：
#include#include#include
#include#include#include#include#include#include
usingnamespacestd;
intfcfsoutput（）;/*调度结果输出*/intfcfsinput（）;//进程参数的初始化voidkaishi（）;
#defineMAX10
#definemaxsize1000
structnode //建立链表来存放进程数据
{
charname[5]; //进程名称
intneed_time; //所需要的时间intallocation; //占用cpu的情况
charstate; //目前的状态R为运行，E为运行完毕node*next; //链表的尾结点
};
structtask_struct
{
charname; /*进程名称*/
intnumber; /*进程编号*/
floatcome_time; /*到达时间*/floatrun_begin_time; /*开始运行时间*/floatrun_time; /*运行时间*/floatrun_end_time; /*运行结束时间*/intpriority; /*优先级*/
intorder; /*运行次序*/
intrun_flag; /*调度标志*/
}tasks[MAX];
intcounter;/*实际进程个数*/intfcfs（）/*先来先服务算法*/
{
fcfsinput（）;
floattime_temp=0;inti;
intnumber_schedul;
time_temp=tasks[0].come_time;for（i=0;i{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;number_schedul=i;tasks[number_schedul].order=i+1;
}
fcfsoutput（）;return0;
}
intfcfsinput（）
{
task_structtt;inti,j;
//初始化进程数
counter=3;
//初始化每个到达系统的时间为5、7、8tasks[0].come_time=rand（）%9;tasks[1].come_time=rand（）%9;tasks[2].come_time=rand（）%9;
for（i=1;i<3;i++）
{
for（j=0;j<3-i;j++）
{
if（tasks[j].come_time>tasks[j+1].come_time）
{
tt=tasks[j];
tasks[j]=tasks[j+1];tasks[j+1]=tt;
}
}
}
//初始化每个进程估计运行的时间tasks[0].run_time=28;
tasks[1].run_time=9;
tasks[2].run_time=3;
//初始化每个进程的名字
tasks[0].name='A';
tasks[1].name='B';
tasks[2].name='C';
cout<<"************************先来先服务算法************************"<for（i=0;i{
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return0;
}
intfcfsoutput（）/*调度结果输出*/
{
inti;
floatturn_round_time=0,f1,w=0;
cout<<" ***********************先来先服务**************************"<{
f1=tasks[i].run_end_time-tasks[i].come_time;turn_round_time+=f1;
w+=（f1/tasks[i].run_time）;
cout<<" "<<<" "
<<" "
<}
<<cout<<"平均周转时间：
"<"<cout<<" ";
return0;
}
voidzuoyediaodu（）//作业调度
{
intn;
cout<<"\t1.先来先服务算法\t2.返回开始菜单"<>n;
switch（n）
{
case1:
fcfs（）;kaishi（）;break;case2:
kaishi（）;kaishi（）;break;
}
}
/*--------------------------------------------------------------------------------*/
voidFIFO（）{
intlength;
intfifo[100]={0};intpageLength;
intfifoPage[100]={0};inti,j;
cout<<" ***********************先进先出算法**************************"<<
endl;
pageLength=3;
length=9;
cout<<"时刻t"<<'\t';for（i=0;i{
cout<}cout<{
fifo[i]=rand（）%5+1;cout<}
for（i=1;i<=length;i++）{intflag=0;
for（j=1;j<=pageLength;j++）{if（fifo[i]==fifoPage[j]）{
flag=1;
j=pageLength+1;
}
elseif（fifoPage[j]==0）{fifoPage[j]=fifo[i];j=pageLength+1;flag=1;
}
}
if（flag==1）
{
}
else
{
cout<<" →淘汰"<fifoPage[j]=fifoPage[j+1];
}
fifoPage[pageLength]=fifo[i];
}
cout<{
cout<<"P"<}
cout<for（ints=1;s<=pageLength;s++）{cout<}
cout<}
}
voidLRU（）
{
intlength;
intlru[100]={0};intpageLength;
intlruPage[100]={0};inti,j;
cout<<"***********************最近最少使用LRU算法***********************"<<
endl;
pageLength=3;
length=9;
cout<<"时刻t"<<'\t';for（i=0;i{
cout<
升级会员 