一个小型的操作系统设计与实现.doc

一个小型的操作系统设计与实现

71
2020年4月19日
文档仅供参考，不当之处，请联系改正。
南通大学计算机科学与技术学院

操作系统课程设计报告

专业：计嵌151
学生姓名：王志宏
学号：151305
时间： /6/28

设计一个小型的操作系统
设计要求
将本学期三次的实验集成实现：
1. 中断处理
2. 作业调度
3. PV原语
4. 死锁
5. 页面替换
6. 磁盘调度
(一)设计流程图
主流程图
开始的图形界面

作业调度
PV原语
死锁
页面替换
磁盘调度
中断处理

哲学家吃通心面

先来先服务
时钟

银行家算法
先进先出算法
LRU算法
先来先服务

1. 中断处理
模拟时钟中断的产生及设计一个对时钟中断事件进行处理的模拟程序。
计算机系统工作过程中，若出现中断事件，硬件就把它记录在中断寄存器中。中断寄存器的每一位可与一个中断事件对应，当出现某中断事件后，对应的中断寄存器的某一位就被置成―1‖。处理器每执行一条指令后，必须查中断寄存器，当中断寄存器内容不为―0‖时，说明有中断事件发生。硬件把中断寄存器内容以及现行程序的断点存在主存的固定单元，且让操作系统的中断处理程序占用处理器来处理出现的中断事件。操作系统分析保存在主存固定单元中的中断寄存器内容就可知道出现的中断事件的性质，从而作出相应的处理。本实习中，用从键盘读入信息来模拟中断寄存器的作用，用计数器加 1 来模拟处理器执行了一条指令。每模拟一条指令执行后，从键盘读入信息且分析，当读入信息=0 时，表示无中断事件发生，继续执行指令；当读入信息=1 时，表示发生了时钟中断事件，转时钟中断处理程序
2.作业调度
1)先来先服务FCFS

开始

初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队

调度数组中首个进程，并让数组中的下一位移到首位

计算并打印进程的完成时刻、周转时间、带权周转时间
其中：周转时间 = 完成时间 - 到达时间
带权周转时间=周转时间/服务时间

更改计时器的当前时间,即下一刻进程的开始时间
当前时间=前一进程的完成时间+其服务时间

数组为空

N

Y

结束

先来先服务算法流程

3.PV原语
1）哲学家吃通心面问题
哲学家吃通心面：在这道题目里，每把叉子必须互斥使用，当一位哲学家吃通心面之前必须执行两个P操作，获得自己左右两边的叉子，在吃完通心面后必须执行两个V操作，放下叉子。

4. 死锁
1） 银行家算法

5.页面替换
1)先进先出FIFO
开始FIFO的缺页中断处理

查主存分块表

有空闲块可用？

Y
分配一块

N

J=p[HEAD]

J的修改标志=1？

N

Y
输出“将J页复写入交换区”

输出“装入L页”

调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM)

修改主存分块表和页表

终止

FIFO淘汰算法流程

2）LRU
开始LRU的缺页中断处理

查主存分块表

有空闲块可用？

Y
分配一块

N

找到栈底元素：J=p[M-1]

J的修改标志=1？

N

Y
输出“将J页送到入交换区”

输出“装入L页”

调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L

修改主存分块表和页表

终止

LRU淘汰算法流程

6. 磁盘调度
1）先来先服务算法FCFS）

（二）实现原理
主界面
设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。

1. 中断

2.作业调度
1)先来先服务FCFS
（一） 任务
先来先服务的调度算法实现处理机调度。
（二） 要求
1. 实现对FCFS算法的模拟实现
2. 计算出该算法的平均作业周转时间、平均带权作业周转时间。
（三） 原理
按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。
（四） 数据结构
struct task_struct
{
char name; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];
int fcfs()/*先来先服务算法*/
进程名
链接指针
到达时间
估计运行时间
进程状态
进程控制块结构
（五） 实现方法
建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。
（六） 运行界面
测试数据：
作业名
到达时间
运行时间
A
0
28
B
0
9
C
0
3
执行FCFS算法如下：

3. 死锁
假定本系统中的各个所需资源均是独占型资源，在进程运行的过程中不再释放，故只需要遍历链表将各个进程中所需的资源统计出来，只要不大于系统中预设的即可，一旦进程所需的资源大于系统中的最大量，给予用户选择kill一进程，已达到释放资源的目的。
死锁检测函数：void sisuo()
死锁解除函数：void safe()

4.缺页调度
1)先进先出FIFO
（一） 任务
采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。
（二） 要求
1.实现对FIFO算法的模拟实现
2.输出每次执行的结果。
（三） 原理
基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。
（四） 数据结构
void FIFO(){
int length;
int fifo[100]={0};
int pageLength;
int fifoPage[100]={0};
int i,j;
cout<<" ***********************先进先出算法**************************"<<endl;
pageLength=3;
length=9;
for(i=1;i<=length;i++){
int flag=0;
for(j=1;j<=pageLength;j++){
if(fifo[i]==fifoPage[j]){
flag=1;
j=pageLength+1;
}else if(fifoPage[j]==0){
fifoPage[j]=fifo[i];
j=pageLength+1;
flag=1;
}
}
if(flag==1)
{
}
else
{
cout<<" →淘汰"<<fifoPage[1]<<endl;
for(j=1;j<=pageLength;j++){
fifoPage[j]=fifoPage[j+1];
}
fifoPage[pageLength]=fifo[i];
}
（五） 实现方法
当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为0.假设分配给每个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标志。
（六） 运行界面
测试数据：
页表长度：9；
页框长度：3；
页面请求数列：4,4,3,5,1,1,2,3,2
执行先进先出FIFO算法结果如下：
2）LRU
（一） 任务
采用先进先出LRU算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。
（二） 要求
1.实现对LRU算法的模拟实现
2.输出每次执行的结果。
（三） 原理
最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。如果主存中已无空闲块，可采用LRU算法进行缺页处理。
（四） 数据结构
void LRU()
{
int length;
int lru[100]={0};
int pageLength;
int lruPage[100]={0};
int i,j;
cout<<" ***********************最近最少使用LRU算法***********************"<<endl;
pageLength=3;
length=9;
for(i=1;i<=length;i++){
int flag=0;
for(j=1;j<=pageLength;j++){
if(lru[i]==lruPage[j]){
for(int cc=j;cc>0;cc--){
lruPage[cc]=lruPage[cc-1];
}
lruPage[1]=lru[i];
flag=1;
j=pageLength+1;
}else if(lruPage[j]==0){
for(int vv=j;vv>0;vv--){
lruPage[vv]=lruPage[vv-1];
}
lruPage[1]=lru[i];
j=pageLength+1;
flag=1;
}
}
if(flag==1)
{
}
else
{
cout<<" →淘汰"<<lruPage[pageLength]<<endl;
for(j=pageLength;j>0;j--){
lruPage[j]=lruPage[j-1];
}
lruPage[1]=lru[i];
}
（五） 实现方法
当采用LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为0.假定分配给每个进程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其它元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中时，还应调整页从当前位置到栈顶。
（六） 运行界面
测试数据：
页表长度：9；
页框长度：3；
页面请求数列：2,3,5,1,5,5,4,4,3
执行最近最少使用LRU算法结果如下：

5. 磁盘调度
1）先来先服务算法FCFS）
这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
（三）总结与体会
经过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近最少使用算法有了更详尽的认识。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我发现我对于c++掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。
另外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。
在设计此模拟操作系统的课设中，也加深了对c++知识的把握。解决了一些以往在编程中遇到了困难。经过此次的课程设计，不但提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计虽然主要问题是在编程上，可是经过不断的去调试，还是成功的调试了出来。可是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！

源代码：
#include<iostream>
#include<cstring>
#include <cstddef>
#include <windows.h>
#include <time.h>
#include <string>
#include <assert.h>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
int fcfsoutput(); /*调度结果输出*/
int fcfsinput(); //进程参数的初始化
void kaishi();
#define MAX 10
#define maxsize 1000

struct node //建立链表来存放进程数据
{
char name[5]; //进程名称
int need_time; //所需要的时间
int allocation; //占用cpu的情况
char state; //当前的状态 R为运行，E为运行完毕
node *next; //链表的尾结点
};
struct task_struct
{
char name; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];

int counter; /*实际进程个数*/
int fcfs()/*先来先服务算法*/
{
fcfsinput();
float time_temp = 0;
int i;
int number_schedul;
time_temp = tasks[0].come_time;
for (i = 0; i<counter; 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();
return 0;
}

int fcfsinput()
{
task_struct tt;
int i, j;
//初始化进程数
counter = 3;
//初始化每个到达系统的时间为5、7、8
tasks[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 << "************************先来先服务算法************************" << endl << endl;
for (i = 0; i<counter; i++)
{
tasks[i].run_begin_time = 0;
tasks[i].run_end_time = 0;
tasks[i].order = 0;
tasks[i].run_flag = 0;
}
return 0;
}

int fcfsoutput() /*调度结果输出*/
{
int i;
float turn_round_time = 0, f1, w = 0;
cout << " ***********************先来先服务**************************" << endl;
cout << "作业名 到达时间 运行时间 开始时间 停止时间 运行次序 周转时间" << endl;
for (i = 0; i<counter; i++)
{
f1 = tasks[i].run_end_time - tasks[i].come_time;
turn_round_time += f1;
w += (f1 / tasks[i].run_time);
cout << " " << tasks[i].name << '\t' << " " << tasks[i].come_time << '\t' << " "
<< tasks[i].run_time << '\t' << " " << tasks[i].run_begin_time << '\t' << " "
<< tasks[i].run_end_time << '\t' << tasks[i].order << '\t' << f1 << '\t' << endl;
}
cout << "平均周转时间：" << turn_round_time / counter << endl;
cout << "平均带权周转时间：" << w / counter << endl;
cout << " ";

return 0;
}

void zuoyediaodu()//作业调度
{
int n;
cout << "\t1.先来先服务算法\t 2.返回开始菜单" << endl;
cin >> n;
switch (n)
{
case 1: fcfs(); kaishi(); break;
case 2: kaishi(); kaishi(); break;
}
}
/*--------------------------------------------------------------------------------*/
void FIFO(){
int length;
int fifo[100] = { 0 };
int pageLength;
int fifoPage[100] = { 0 };
int i, j;
cout << " ***********************先进先出算法**************************" << endl;
pageLength = 3;
length = 9;
cout << "时刻t" << '\t';
for (i = 0; i<length; i++)
{
cout << i << '\t';
}cout << endl << "引用串" << '\t';
for (i = 1; i <= length; i++)
{
fifo[i] = rand() % 5 + 1;
cout << fifo[i] << '\t';
}

for (i = 1; i <= length; i++){
int flag = 0;
for (j = 1; j <= pageLength; j++){
if (fifo[i] == fifoPage[j]){
flag = 1;
j = pageLength + 1;
}
else if (fifoPage[j] == 0){
fifoPage[j] = fifo[i];
j = pageLength + 1;
flag = 1;
}
}
if (flag == 1)
{
}
else
{
cout << " →淘汰" << fifoPage[1] << endl;
for (j = 1; j <= pageLength; j++){
fifoPage[j] = fifoPage[j + 1];
}
fifoPage[pageLength] = fifo[i];
}

cout << endl << "t=" << i - 1 << "时" << '\t';
for (int jk = 1; jk <= pageLength; jk++)
{
cout << "P" << jk << '\t';
}
cout << endl << '\t';
for (int s = 1; s <= pageLength; s++){
cout << fifoPage[s] << '\t';
}
cout << endl;
}

}

void LRU()
{
int length;
int lru[100] = { 0 };
int pageLength;
int lruPage[100] = { 0 };
int i, j;
cout << " ***********************最近最少使用LRU算法***********************" << endl;
pageLength = 3;
length = 9;
cout << "时刻t" << '\t';
for (i = 0; i<length; i++)
{
cout << i << '\t';
}cout << endl << "引用串" << '\t';
for (i = 1; i <= length; i++)
{
lru[i] = rand() % 5 + 1;
cout << lru[i] << '\t';

}

for (i = 1; i <= length; i++){
int flag = 0;
for (j = 1; j <= pageLength; j++){
if (lru[i] == lruPage[j]){
for (int cc = j; cc>0; cc--){
lruPage[cc] = lruPage[cc - 1];
}
lruPage[1] = lru[i];
flag = 1;
j = pageLength + 1;
}
else if (lruPage[j] == 0){
for (int vv = j; vv>0; vv--){
lruPage[vv] = lruPage[vv - 1];
}
lruPage[1] = lru[i];
j = pageLength + 1;
flag = 1;
}
}
if (flag == 1)
{
}
else
{
cout << " →淘汰" << lruPage[pageLength] << endl;
for (j = pageLength; j>0; j--){
lruPage[j] = lruPage[j - 1];
}
lruPage[1] = lru[i];
}

cout << endl << "t=" << i - 1 << "时" << '\t';
for (int jk = 1; jk <= pageLength; jk++)
{
cout << "P" << jk << '\t';
}
cout << endl << '\t';
for (int s = 1; s <= pageLength; s++){
cout << lruPage[s] << '\t';
}
cout << endl;
}

}

void queye()//页面替换
{
int n;
cout << endl;
cout << "\t1.先进先出算法\t2.LRU算法\t3.返回开始菜单" << endl;
cin >> n;
switch (n)
{
case 1: FIFO(); kaishi(); break;
case 2: LRU(); kaishi(); break;
case 3: kaishi(); kaishi(); break;
}
}
/*----------------------------------------------------------------------------------*/
/*********************判断输入数据是否有效**************************/
int decide(char str[]) //判断输入数据是否有效
{
int i = 0;
while (str[i] != '\0')
{
if (str[i]<'0' || str[i]>'9')
{
return 0;
break;
}
i++;
}
return i;
}
/******************将字符串转换成数字***********************/
int trans(char str[], int a) //将字符串转换成数字
{
int i;
int sum = 0;
for (i = 0; i<a; i++)
{
sum = sum + (int)((str[i] - '0')*pow(10, a - i - 1));
}
return sum;
}
/*********************先来先服务调度算法************************/
void FCFS(int cidao[], int m) //磁道号数组，个数为m
{
int now;//当前磁道号
int sum = 0; //总寻道长度
int j, i;
int a;
char str[100];
float ave; //平均寻道长度
cout << " ***********************先来先服务**************************" << endl;
cout << "磁盘请求序列为：";
for (i = 0; i<m; i++) //按先来先服务的策略输出磁盘请求序列
{
cout << cidao[i] << " ";
}
cout << endl;
cout << "请输入当前的磁道号：";
B: cin >> str; //对输入数据进行有效性判断
a = decide(str);
if (a == 0)
{
cout << "输入数据的类型错误,请重新输入！" << endl;
goto B;
}
else
now = trans(str, a); //输入当前磁道号
sum += abs(cidao[0] - now);
cout << "磁盘扫描序列为：";
for (i = 0; i<m; i++) //输出磁盘扫描序列
{
cout << cidao[i] << " ";
}
for (i = 0, j = 1; j<m; i++, j++) //求平均寻道长度
{
sum += abs(cidao[j] - cidao[i]);
ave = (float)(sum) / (float)(m);
}
cout << endl;
cout << "平均寻道长度：" << ave << endl;
}

void cipandiaodu() //磁盘调度
{
int a;
int c; //菜单项
int cidao[maxsize];
int i = 0, count;
char str[100];
cout << endl;
cout << "\t1.先来先服务\t2.返回开始菜单" << endl;

F:cin >> str; //对输入数据进行有效性判断
a = decide(str);
if (a == 0)
{
cout << "输入数据的类型错误,请重新输入！" << endl;
goto F;//输入错误，跳转到F，重新输入
}
else
c = trans(str, a);
cout << "请输入磁道序列（0结束）：" << endl;
A:cin >> str; //对输入数据进行有效性判断
a = decide(str);
if (a == 0)
{
cout << "输入数据的类型错误,请重新输入！" << endl;
goto A;//输入错误，跳转到A，重新输入
}
else
cidao[i] = trans(str, a);
i++;
while (cidao[i - 1] != 0)
{
cin >> str; //对输入数据进行有效性判断
a = decide(str);
if (a == 0)
cout << "输入数据的类型错误,请重新输入！" << endl;
else
{
cidao[i] = trans(str, a);
i++;
}
}
count = i - 1; //要访问的磁道数
cout << "你输入的磁道序列为：";
for (i = 0; i<count; i++)
{
cout << cidao[i] << " "; //输出磁道序列
}
cout << endl;

switch (c)
{
case 1: //使用FCFS算法
FCFS(cidao, count); kaishi(); break;
case 2:
kaishi(); kaishi(); break;

}
}
/*----------------------------------------------------------------------------------*/
bool tools[5]; //全局变量，用餐工具
CRITICAL_SECTION cs; //信号量, 在线程中使用，临界区
class Philosopher
{
private:
int number;
int status; //标记当前哲学家的状态,0表示正在等待
// (即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思考
public:
Philosopher(int num = 0) : status(2