操作系统课程设计报告样本.doc

课 程 设 计 说 明 书

设计题目： 操作系统课程设计

班 级： 信息学管理与信息系统级

学 号： 01051012

姓 名： 李克乾

山 东 科 技 大 学
12 月 11 日
课 程 设 计 任 务 书
学院 信息科学与工程 专业 信息学管理与信息系统 班级 -2
姓名 李克乾
一、课程设计题目： 操作系统课程设计

二、课程设计重要参照资料
（1）Abraham Silberschatz & Peter Baer Galvin & Greg Gagne. Operating System Concepts（第七版 影印版）. 高等教诲出版社. .3.
（2） c++面向对象程序设计 电子工业出版社
（3）计算机操作系统（第三版） 西安电子科技大学出版社

三、课程设计应解决重要问题：
（1）CPU调度算法模仿实现
（2）死锁有关算法实现
（3）磁盘调度算法实现
四、课程设计有关附件（如：图纸、软件等）：
（1） 程序源代码
（2）

五、任务发出日期： -10-1 课程设计完毕日期： -1-1

指引教师签字：
指引教师对课程设计评语

成绩：

指引教师签字：
年 月 日
设计1 CPU调度算法模仿实现
一、设计目
运用C++编写CPU调度算法，实现先来先服务调度算法FCFS、优先级调度算法PS、短作业优先调度算法SJF、时间片轮转调度算法RR运营过程和实现成果，针对模仿进程，运用编写CPU调度算法对需要运营进程进行调度。进行算法评价，计算平均周转时间和平均等待时间。
二、设计规定
针对模仿进程，运用CPU调度算法进行调度，最后要进行算法评价，计算平均周转时间和平均等待时间，并且输出调度成果和输出算法评价指标。
调度所需进程参数由输入产生（手工输入或者随机数产生）。
三、设计阐明
时间片轮转算法需要输入相应时间片，因此独立编写一种程序，系统主体构造如下：
CPU调度算法
先
来
先
服
务
算
法
优
先
级
调
度
算
法

短
作
业
优
先
调
度
算
法
时
间
片
轮
转
调
度
算
法

实现构造体如下：
struct task_struct
{
char name[10]； /*进程名称*/
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];
运用switch语句对输入进程进行相应算法运营，进入相应算法函数后会对进程进行调度并输出成果，并对成果进行评估。
1. 先来先服务算法（FCFS）可用于作业调度，也可用于进程调度。每次调度都是从后备队列中选取一种或者各种最先进入队列作业或进程，将她们调入内存进行分派资源，创立进程，放入就绪队列并开始执行。实现函数：int fcfs() /*先来先服务*/
重要实现办法如下：
执行程序
输入进程有关信息
寻找第一进程
将进程保存至调度列，并进行调度
判断所有进程都被调度
在未调度算法中需找最先到达进程
是
否
打印成果信息

2. 短作业优先调度算法（SJF），即从后备队列中选取一种或几种预计运营时间最短作业或进程对其分派资源，并进行调度执行。实现函数：int sjf() /*短作业优先*/
重要实现办法如下：
执行程序
输入进程信息
判断最短服务时间进程
把进程储存在调度序列并执行
在未调度并已到达进程中寻找服务时间最短进程
打印调度成果
所有进程被调度
否
是

3. 优先级调度算法即在将第一种到达进程执行完毕后，会在此刻已经到达进程或作业中选取优先权最高一种或者几种进程对其进行资源分派并创立进程执行。实现函数：int ps() /*优先级调度*/
重要实现办法如下：

程序执行
输入进程信息
判断优先级最高进程
把进程存储在调度序列并执行
在未调度并已到达进程中寻找优先级最高进程
打印调度成果
所有进程被调度
否
是

4. 在时间片调度算法模仿实现中，时间片就是分派给进程运营一段时间。在轮转法中，系统将所有可运营（即就绪）进程按先来先服务原则，排成一种队列，每次调度时把CPU分派给队首进程，并令其执行一种时间片。当某进程执行时间片用完时，系统发出信号，告知调度程序，调度程序便据此信号来停止该进程执行，并将刚运营进程送到运营队列末尾，等待下一次执行；然后，把解决机分派给就绪队列中新队首进程，同步也让它执行一种时间片。这样就可以保证运营队列中所有进程，在一种给定期间内，均能获得一时间片解决机执行时间。实现函数（单独程序）
重要实现办法如下：

四、运营成果及分析
设有如下3个进程：
进程名称
到达时间
运营时间
优先级
A
4
5
3
B
6
10
1
C
5
8
2
注："优先级"一栏，数字大表达优先级越高。
依照本例来运营本算法，成果如下：
采用先来先服务算法:

采用优先级调度：

采用短作业优先：

时间片轮转算法：

本程序已通过测试阶段，未浮现进程调度错误状况。运营程序后，只需按照提示输入相应进程信息（进程名尽量输入单个字母）后选取需要调度算法即可得出相应成果，并且可以循环运营多次。后期进行相应美化加工，如需要，可进行可视化改造。

成果分析：
对于进程调度后得出各项数据基本精确，当输入时间或其她数据信息浮现精准度较高数值时也许会浮现某些误差，属于误差范畴之内。程序基本可以实现CPU调度算法过程解释。
五、总结
通过本次课程设计，更进一步理解了各个进程调度算法，及实现过程。在此过程中，遇到了困难，能及时请教同窗，查询有关资料，及时解决了问题，但仍有局限性之处，将会在此后学习中更加努力。
六．附录（完整代码）
#include<iostream>
using namespace std;
#define MAX 10
struct task_struct
{
char name[10]； /*进程名称*/
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()； /*先来先服务*/
int ps()； /*优先级调度*/
int sjf()； /*短作业优先*/
int hrrn()； /*响应比高优先*/
int pinput()； /*进程参数输入*/
int poutput()； /*调度成果输出*/

int main()
{
int option;
pinput();
printf("请选取调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf("3.短作业优先\n");
printf("0.退出\n");
scanf("%d",&option);
switch (option)
{
case 0:
printf("运营结束。\n");
break；
case 1:
printf("对进程按先来先服务调度。\n\n");
fcfs();
break;
case 2:
printf("对进程按优先级调度。\n\n");
ps();
break;
case 3:
printf("对进程按短作业优先调度。\n\n");
sjf();
break;
}
}
int fcfs() /*先来先服务*/
{
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;
}
poutput();
return main();
}

int ps() /*优先级调度*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter;
int max_priority;
max_priority=tasks[i].priority;
j=1;
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
}
/*查找第一种被调度进程*/
/*对第一种被调度进程求相应参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schedul=j;
}
}
/*查找下一种被调度进程*/
/*对找到下一种被调度进程求相应参数*/
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;

}
poutput();
return main();
}

int sjf() /*短作业优先*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter;
float run_time;
run_time=tasks[i].run_time;
j=1;
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
} /*查找第一种被调度进程*/
/*对第一种被调度进程求相应参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;
while (temp_counter<counter)
{
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{
run_time=tasks[j].run_time;number_schedul=j;break;}
}

for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{
run_time=tasks[j].run_time;
number_schedul=j;
}
}
/*查找下一种被调度进程*/
/*对找到下一种被调度进程求相应参数*/
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter；
}
poutput();
return main();
}

int pinput() /*进程参数输入*/
{
int i;
printf("please input the process counter:\n");
scanf("%d",&counter);
if(counter==0)
return 0;
else
{
for(i=0;i<counter;i++)
{ printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
}
return 0;
}
int poutput() /*调度成果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("name come_time run_time run_begin_time run_end_time priority order turn_round_time\n");
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);
printf(" %s， %5.3f， %5.3f， %5.3f， %5.3f， %d， %d， %5.3f\n",tasks[i].name,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
printf("weight_average_turn_round_timer=%5.2f\n",w/counter);
return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")
typedef struct PCB
{
int ID;
int ReachTime;
int TotalTime;
}PCB; //进程号，到达时间和服务时间
typedef struct NOTE //备份
{
int ID;
int TotalTime;
}NOTE;
PCB A[100]； //5个进程
PCB a[100];
NOTE temp;
int queue[50]；//记录调度进程
int K=0; //调度进程数组标记
void INIT(int M)//初始化
{
int i;
int m;
m=M;
for(i=0;i<m;i++)
{
A[i].ID=-1;
}
}
int GetNum(int M)//计算进程数
{int m;m=M;int i;int j=0;
for(i=0;i<m;i++)
{
if(A[i].ID!=-1)
{
j++;
}
}
return j;
}
int GetReach(int time,int M)//找出到达进程号
{
int i;
int m;
m=M;
for(i=0;i<m;i++)
{
if(a[i].ReachTime<=time)
{
a[i].ReachTime=100;
return i;
}
}
return -1;
}
int GetInsert(int M)//找出插入位置
{
int i;
int m;
m=M;
for(i=0;i<m;i++)
{
if(A[i].ID==-1)
return i;
}
return -1;
}
void Forward(int num)//前移
{
int i;
for(i=0;i<num-1;i++)
{
A[i].ID=A[i+1].ID;
A[i].TotalTime=A[i+1].TotalTime;
}
A[num-1].ID=-1;
}
void Process(int Jiange)//执行进程
{
int jiange;
jiange=Jiange;
queue[K]=A[0].ID;
K++;
A[0].TotalTime=A[0].TotalTime+jiange;
temp.ID=A[0].ID;
temp.TotalTime=A[0].TotalTime;
}
int main()
{
int i;
int time;
int t=0;
int reach;
int insert;
int num;
int M;
int Jiange;
printf("RR算法\n\n");
printf("请输入进程个数\n");
scanf("%d",&M);
printf("请输入R值\n");
scanf("%d",&Jiange);
INIT(M);
for(i=0;i<M;i++)
{
printf("请输入进程ID：");
scanf("%d",&a[i].ID);
printf("请输入到达时间：");
scanf("%d",&a[i].ReachTime);
printf("请输入服务时间：");
scanf("%d",&a[i].TotalTime);
}
for(i=0;i<M;i++)//运营时间
{
t=t+a[i].TotalTime;
}
for(i=0;i<50;i++)//初始化
{
queue[i]=-1;
}
for(time=0;time<=t;time++)
{
reach=GetReach(time,M);
if(reach!=-1)//有进程到达
{
insert=GetInsert(M);
A[insert].ID=a[reach].ID;
A[insert].TotalTime=a[reach].TotalTime;
num=GetNum(M);
if(num==1)
continue;//进程数为1
else
{
//进程数不为1
Process(Jiange);
Forward(num);
if(temp.TotalTime!=0)
{
A[num-1].ID=temp.ID;
A[num-1].TotalTime=temp.TotalTime;
}
}
}
else//没有进程到达
{
num=GetNum(M);
if(num==1)
{//进程数为1
Process(Jiange);
if(temp.TotalTime==0)
{
A[0].ID=-1;
}
}
else if(num==0)
continue;//进程数为0
else
{
Process(Jiange);
Forward(num);
if(temp.TotalTime!=0)
{
A[num-1].ID=temp.ID;
A[num-1].TotalTime=temp.TotalTime;
}
}
}
}
printf("\n");
printf("调度顺序为：\n");
Myprintf;
for(i=0;i<50;i++)
{
if(queue[i]!=-1)
printf("|%2d ",queue[i]);
}
printf("|\n");
Myprintf;
printf("\n");
return 0;
}
设计2 死锁有关算法实现
一、设计目
编写算法，实现银行家算法、安全性算法、死锁检测算法判断系统安全状态、判断进程资源祈求与否可以被满足、鉴定系统与否为死锁状态。银行家算法是避免死锁一种重要办法，通过编写一种简朴银行家算法程序，加深理解关于资源申请、避免死锁等概念，并体会和理解死锁和避免死锁详细实行办法。
二、设计规定
其中算法所需各种参数由输入产生（手工输入或者随机数产生）
本模块课程设计基本规定是可以输出各种鉴定成果（与否安全、安全序列、与否死锁、与否容许分派）。
三、 设计阐明
1、算法思路：先对顾客提出祈求进行合法性检查，即检查祈求与否不不大于需要，与否不不大于可运用。若祈求合法，则进行预分派，对分派后状态调用安全性算法进行检查。若安全，则分派；若不安全，则回绝申请，恢复到本来状态，回绝申请。
2、银行家算法环节：
（1）如果Requesti＜or =Need,则转向环节(2)；否则，以为出错，由于它所需要资源数已超过它所宣布最大值。
（2）如果Request＜or=Available,则转向环节（3）；否则，表达系统中尚无足够资源，进程必要等待。
（3）系统试探把规定资源分派给进程Pi,并修改下面数据构造中数值：
     Available=Available-Request[i];
     Allocation=Allocation+Request;
Need=Need-Request;
(4)系统执行安全性算法，检查本次资源分派后，系统与否处在安全状态。
3、安全性算法环节：
（1）设立两个向量
①工作向量Work。它表达系统可提供进程继续运营所需要各类资源数目，执行安全算法开始时，Work=Allocation;
②布尔向量Finish。它表达系统与否有足够资源分派给进程，使之运营完毕，开始时先做Finish[i]=false，当有足够资源分派给进程时，令Finish[i]=true。
（2）从进程集合中找到一种能满足下述条件进程：
①Finish[i]=false
②Need<or=Work
如找到，执行环节（3）；否则，执行环节（4）。
（3）当进程P获得资源后，可顺利执行，直至完毕，并释放出分派给它资源，故应执行：
Work=Work+Allocation;
Finish[i]=true；
转向环节（2）。
（4）如果所有进程Finish[i]=true,则表达系统处在安全状态；否则，系统处在不安全状态。
4、死锁检测和解除
编程实现死锁检测算法、死锁解除算法，数据动态输入，解锁采用释放最大死锁进程资源办法实现。

系统重要过程流程图

银行家算法流程图

安全性算法流程图

死锁检测并释放流程图：
输入进程数m和资源数n
输入已分派矩阵、最大需求矩阵、需求矩阵、祈求矩阵
Finish[i]=true;if(allocation[i][j]>0||request[i][j]>0)
Finish=false
判断
开始

运用c++实现对这三个算法进行实现，通过自定义进程数和进程资源各项数据状况对其进行分派，将其用函数分开，在实现每一步时进行调用。
重要函数如下：
showdata()//显示资源矩阵
int changdata(int i)//进行资源分派
int safe()//安全性算法
void share()//运用银行家算法对申请资源对进行鉴定
int compare(int **request,int *work,int N,int k) //如果Request[i]>work则返回false，即对需求与既有资源比较
int check(int *work,int **request,int **allocation,int *finish,int *p,int m,int n)//调用安全公式进行检测

void jiesuo(int *work,int **request,int **allocation,int *finish,int *p,int m,int n) //解锁函数
void  operate(int *work,int **request,int **allocation,int *finish,int *p,int m,int n)//操作函数
int main()//主函数

四、 运营成果及分析

假设系统中有三个进程{p，q，r}和三类资源{a，b，c}，各种资源数量分别为10,5,7，在T0时刻资源分派状况如图
资源状况

进程

Max

a b c
Allocation

a b c
Need

a b c
Available

a b c
P

7 5 3

0 1 0

7 4 3

3 3 2
Q

3 2 2

2 0 0

1 2 2

R

9 0 2

3 0 2

6 0 0

运营程序后输入数据如图

使用银行家算法所分派状况和安全检查状况为

死锁检测与排除运营成果为

这两个程序已经完毕了对进程以资源之间检测与分派功能，并且可以在给出资源分派状况后检测需求与否会发生死锁状况并给出解除方案。运营程序后只需按照提示操作即可观测到进程对资源调用状况。

五、 总结
各种进程同步运营时，系统依照各类系统资源最大需求和各类系统剩余资源为进程安排安全序列，使得系统能迅速且安全地运营进程，不至发生死锁。银行家算法是避免死锁重要办法，其思路在诸多方面都非常值得咱们来学习借鉴。通过对算法编写让我理解到计算机在调度进程时详细过程，也明白理解决死锁原理。
六、附录
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define False 0
#define True 1
int Max[1