操作系统算法设计操作系统.doc

成绩

课程设计报告

题 目 操作系统算法设计

课 程 名 称 操作系统课程设计
院 部 名 称 计算机工程学院
专 业 计算机科学与技术
班 级 14计算机科学与技术单
学 生 姓 名 邵佳楠
学 号 141320100
课程设计地点 A107
课程设计学时 20学时
指 导 教 师 潘

金陵科技学院教务处制
目 录

摘 要 1
一、 课程设计的目的和要求 3
二、系统需求分析 3
三、总体设计 3
四、详细设计 4
五、测试、调试过程 7
六、结论与体会 16
附录：源程序 17
摘 要 32
一、 课程设计的目的和要求 33
二、系统需求分析 33
三、总体设计 33
四、详细设计 33
五、测试、调试过程 34
六、结论与体会 38
附录：源程序 39
摘 要 47
一、 设计的目的和要求 48
二、系统需求分析 48
三、总体设计 48
四、详细设计 48
五、测试、调试过程 50
六、结论与体会 54
附录：源程序 55

操作系统算法设计-进程调度程序

摘 要
随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和时间紧密结合，才能取得较好的学习效果。
本次课程设计师在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。
熟悉“最高优先级优先调度算法”、“基于时间片轮转法”、“多级反馈队列调度算法”、“最高优先级优先算法”，虽然不用全部每一个都弄清楚，但是了解其中的算法思想也是有好处的。

关键词：最高优先级优先调度算法、基于时间片轮转法、多级反馈队列调度算法、最高优先级优先算法

一、 课程设计的目的和要求
程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。
二、系统需求分析
在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度（又称高级调度或长程调度）和进程调度（又称低级调度或短程调度）两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程调度即可获得处理机。在较完善的操作系统中，为提高内存的利用率，往往还设置了中级调度（又称中程调度）。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。
三、总体设计
编写进程调度程序，“最高优先级优先”算法常用语批处理系统中，在进程调度中，每次调度时，系统把处理机给就绪队列中优先级最高的进程。在非抢占式优先级算法下系统一旦把处理机分配给就绪队列中优先级最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的理你个优先级最高的进程。静态优先级是在创建进程时确定的，并在整个运行期间不再改变。动态优先级是指进程的优先级在创建进程时可以给定一个初始值，并且可以按一定原则修改优先级。
“轮转法”算法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾;然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。
“多级反馈队列调度”算法中，进程在进入待调度的队列等待时，首先进入优先级最高的队列等待。先调度优先级高的队列中的进程，若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。对于同一个队列中的各个进程，按照时间片轮转法调度。在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
最高优先级优先算法:从键盘输入若干个进程，进程包括进程名，进程优先级，进程运行时间。就绪队列按照优先级从高到低排列，进程调度中，获取就绪队列队首进程，即优先级最高的进程，在进程获得一次CPU后，就将该进程的优先级减1。重新排列就绪队列，获取就绪队列队首进程进行调度。
四、详细设计
进程调度程序中，静态优先级算法的基本原理与简单轮转调度的算法还有多级反馈调度算法相似，都是先用户输入进程信息、对用户输入的进程按优先级排序，然后输出就绪队列中的进程、输出正在运行的进程、输出已完成的进程、静态优先级算法，区别在于简单轮转调度算法多一个对用户输入的进程按FCFS排序。动态优先级算法是根据静态优先级算法进行更改，总体差不多只是相对灵活性更加灵活。而多级反馈调度算法是按优先级排序，整体上差不多。
下面是各个算法的程序流程图：
初始化
是否开始
输入进程
按优先级高低排入就绪队列中
是否继续输入进程
就绪队列是否为空
获取就绪队列队首进程
进程获得一个CPU
该进程是否完成
按优先级高低插入就绪队列中

释放进程节点
结束
N
Y
Y
N
N
Y
Y
N

图1.1 最高优先级优先算法流程图

初始化
是否开始
输入进程
按先来先服务排入就绪队列中
是否继续输入进程
就绪队列是否为空
获取就绪队列队首进程
进程在时间片T内运行
该进程是否完成
排入就绪队列队尾
释放进程节点
结束
N
Y
Y
N
N
Y
Y
N

图1.2 简单轮转法优先算法流程图

初始化
退出系统
选择功能菜单
输入进程
是否继续输入
按先来先服务算法插入就绪第一队列
是否完成
获取最高优先队列队首进程，若为空，则，寻在下一队列
该进程获取CPU的一个时间片时间
释放进程节点
把该进程插入所在队列（n）的下一个队列（n+1）的队尾
是否找到进程

图1.3 多级反馈调度算法流程图
五、测试、调试过程
在静态优先级调度算法中，判断出了在运用getch()的时候需要头文件#include <conio.h>这一项的。动态优先级算法在根据静态优先级算法的基础上改的整体的框架没有改变，简单轮转调度算法、多级反馈调度算法和静态优先级调度算法都有一个通用的问题就是conio.h，在编写程序的过程中要熟悉系统文件的头文件对应的功能。
下面是各个程序的运行结果：
静态优先级调度算法：

动态优先级调度算法：

简单轮转调度算法：

多级反馈调度算法：

六、结论与体会
在运行的这几个程序中，普遍的问题就是缺少头文件，或者是系统的函数在没有弄清楚的情况下没有注意分开。操作系统这门课与实际运用联系也是很大的，比如银行家算法，虽然课程设计里面没有做到。在程序的几个调度算法中其实也可以看到现实的例子，比如进程调度，我们可以把他设计成一个公司内部管理调度，其性质和原理其实是一样的并没有什么太大的区别。在这门课上我学习到了如何独立自主的面对程序调试运行出现的问题。冷静的思考是很有必要的。
附录：源程序
进程调度程序
//静态优先级调度算法.c
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 24
struct pcb//建立进程控制块
{
char pname[10];
int priority;
int reachtime;
int needtime;
int usecputime;
char status;
};typedef struct pcb PCB;
void inputpcb(PCB pcb[],int *n)//用户输入进程信息
{
int i;
int num;
printf("\n请输入进程个数");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n请输入第%d个进程的名称:",i+1);
scanf("%s",pcb[i].pname);
printf("\n请输入第%d个进程的优先级:",i+1);
scanf("%d",&pcb[i].priority);
printf("\n进程的默认到达时间为O.\n");
printf("\n请输入第%d个进程的运行时间:",i+1);
scanf("%d",&pcb[i].needtime);
pcb[i].reachtime=0;
pcb[i].usecputime=0;
pcb[i].status='r';
}
*n=num;
}
void paixupcb(PCB pcb[],int n)//对用户输入的进程按优先级排序
{
int i,j;
PCB pcbtemp;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pcb[i].priority<pcb[j].priority)
{
pcbtemp=pcb[i];
pcb[i]=pcb[j];
pcb[j]=pcbtemp;
}
}
}
}
void printpcb(PCB pcb[],int n)//输出就绪队列中的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status!='F')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printRpcb(PCB pcb[],int n)//输出正在运行的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='R')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printFpcb(PCB pcb[],int n)//输出已完成的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='F')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void staPRI(PCB pcb[],int n,int times)//静态优先级算法
{
int i=0;
printf("\n当前的系统时间为:%d\n",times);
getch();
printf("\n按优先级排序，到达就绪队列中的进程为：");
paixupcb(pcb,n);
getch();
for(i=0;i<n;i++)
{
while(pcb[i].needtime>pcb[i].usecputime)
{
pcb[i].status='R';
printf("\n按静态优先级对进程调度，正在运行的进程为：");
pcb[i].usecputime++;
times++;
printRpcb(pcb,n);
getch();
printf("\n当前的系统时间为:%d\n",times);
getch();
pcb[i].status='r';
paixupcb(pcb,n);
if(pcb[i].needtime==pcb[i].usecputime)
{
pcb[i].status='F';
printf("\n此时刻，进程%s已经完成，进程%s被撤销!\n",pcb[i].pname,pcb[i].pname);
getch();
}
printf("\n按优先级排序，就绪队列中的进程为：");
printpcb(pcb,n);
getch();
}
}
printf("\n按优先级队列中已经没有进程，至此，所有的进程已经完成!\n");
getch();
printf("\n完成信息如下：");
printFpcb(pcb,n);
getch();
printf("\n\n进程调度完毕!请按任意键退出!");
}

//动态优先级算法
void dynPRI(PCB pcb[],int n,int times)
{
int i=0;
char temp[10];
int min; ;
printf("\n当前的系统时间为:%d\n",times);
getch();
printf("\n按优先级排序，到达就绪队列中的进程为：");
paixupcb(pcb,n);
printpcb(pcb,n);
getch();
for(i=0;i<n-1;i++)
{
if(pcb[i].reachtime>pcb[i+1].reachtime)
{
min=pcb[i].reachtime;
pcb[i].reachtime=pcb[i+1].reachtime;
pcb[i+1].reachtime=min;
min=pcb[i].needtime;
pcb[i].needtime=pcb[i+1].needtime;
pcb[i+1].needtime=min;
min=pcb[i].priority;
pcb[i].priority=pcb[i+1].priority;
pcb[i+1].priority=min;
strcpy(temp,pcb[i].pname);
strcpy(pcb[i].pname,pcb[i+1].pname);
strcpy(pcb[i+1].pname,temp);
}
}
for(i=0;i<n;i++)
{
if(pcb[i].priority<pcb[i+1].priority)
{
min=pcb[i].priority;
pcb[i].priority=pcb[i+1].priority;
pcb[i+1].priority=min;

min=pcb[i].reachtime;
pcb[i].reachtime=pcb[i+1].reachtime;
pcb[i+1].reachtime=min;

min=pcb[i].needtime;
pcb[i].needtime=pcb[i+1].needtime;
pcb[i+1].needtime=min;
strcpy(temp,pcb[i].pname);
strcpy(pcb[i].pname,pcb[i+1].pname);
strcpy(pcb[i+1].pname,temp);
// pcbs[i].usetime++;
} //按进程优先级排序，最高的排在最前面
}
printf("\n按优先级队列中已经没有进程，至此，所有的进程已经完成!\n");
getch();
printf("\n完成信息如下：");
printFpcb(pcb,n);
getch();
printf("\n\n进程调度完毕!请按任意键退出!");
}
void main()
{
PCB pcbr[MAX];
int pnum=0;
int systime=0;
printf("\t\t\t\t进程调度模拟演示程序");
inputpcb(pcbr,&pnum);
printf("\n用户输入的进程信息为：");
printpcb(pcbr,pnum);
staPRI(pcbr,pnum,systime);
}

//简单轮转法调度算法.c
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define MAX 24

struct pcb//建立进程控制块
{
char pname[10];
int reachtime;
int needtime;
int usecputime;
char status;
};
typedef struct pcb PCB;
void inputpcb (PCB pcb[],int *n)//用户输入进程信息
{
int i;
int num;
printf("\n请输入进程个数");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n请输入第%d个进程的名称:",i+1);
scanf("%s",&pcb[i].pname);
printf("\n请输入第%d个进程的提交时间:",i+1);
scanf("%d",&pcb[i].reachtime);
printf("\n请输入第%d个进程的运行时间:",i+1);
scanf("%d",&pcb[i].needtime);
pcb[i].usecputime=0;
pcb[i].status='r';
}
*n=num;
}
void fcfspcb(PCB pcb[],int n)//对用户输入的进程按FCFS排序
{
int i,j;
PCB pcbtemp;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pcb[i].reachtime>pcb[j].reachtime)
{
pcbtemp=pcb[i];
pcb[i]=pcb[j];
pcb[j]=pcbtemp;
}
}
}
}
void printpcb(PCB pcb[],int n)//输出用户输入的进程
{
int i;
printf("\n进程名 到达时间 需要运行时间");
for(i=0;i<n;i++)
{
printf("\n %s %d %d",pcb[i].pname,pcb[i].reachtime,pcb[i].needtime);
}
printf("\n");
}
void printrpcb(PCB pcb[],int n)//输出就绪队列中的进程
{
int i;
printf("\n进程名 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='r')
printf("\n %s %d %d %d %c",pcb[i].pname,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printRpcb(PCB pcb[],int n)//输出正在运行的进程
{
int i;
printf("\n进程名 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='R')
printf("\n %s %d %d %d %c",pcb[i].pname,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printFpcb(PCB pcb[],int n)//输出已完成的进程
{
int i;
printf("\n进程名 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='F')
printf("\n %s %d %d %d %c",pcb[i].pname,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void simTSC(PCB pcb[],int n)
{
int i=0;
int j;
PCB pcbtemp;
printf("\n按先来先服务排序，就绪队列中的进程:");
fcfspcb(pcb,n);
getch();
while(pcb[i].needtime>pcb[i].usecputime&&i<n)
{
pcb[i].status='R';
printf("\n按简单时间片轮转发对进程进行调度，正在运行的进程为:");
pcb[i].needtime++;
printRpcb(pcb,n);
getch();
if(pcb[i].needtime==pcb[i].usecputime)
{
pcb[i].status='F';
printf("\n此时刻，进程%s已经完成，进程%s被撤销!\n",pcb[i].pname,pcb[i].pname);
getch();
i++;
}
else
{
pcb[i].status='r';
pcbtemp=pcb[i];
for(j=i;j<n-1;j++)
{
pcb[j]=pcb[j+1];
}
pcb[j]=pcbtemp;
}
printf("\n本次调度完成!准备进行下一次调度.\n");
getch();
printf("\n就绪队列中的进程为:");
printrpcb(pcb,n);
getch();
}
printf("\n就绪队列中已经没有进程，致辞，所有的进程已经完成");
getch();
printf("\n完成信息如下:");
printFpcb(pcb,n);
getch();
printf("\n\n进程调度完毕!请按任意键退出!");
}
void main()
{
PCB pcbr[MAX];
int pnum=0;
printf("\t\t\t\t进程调度模拟演示程序");
inputpcb(pcbr,&pnum);
printf("\n用户输入的原始程序信息为:");
printpcb(pcbr,pnum);
simTSC(pcbr,pnum);
}

//多级反馈队列调度算法.c
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 24
struct pcb//建立进程控制块
{
char pname[10];
int priority;
int reachtime;
int needtime;
int usecputime;
char status;
};
typedef struct pcb PCB;

void inputpcb(PCB pcb[],int *n)//用户输入进程信息
{
int i;
int num;
printf("\n请输入进程个数");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n请输入第%d个进程的名称:",i+1);
scanf("%s",pcb[i].pname);
printf("\n请输入第%d个进程的优先级:",i+1);
scanf("%d",&pcb[i].priority);
printf("\n进程的默认到达时间为O.\n");
printf("\n请输入第%d个进程的运行时间:",i+1);
scanf("%d",&pcb[i].needtime);
pcb[i].reachtime=0;
pcb[i].usecputime=0;
pcb[i].status='r';
}
*n=num;
}
void paixupcb(PCB pcb[],int n)//对用户输入的进程按优先级排序
{
int i,j;
PCB pcbtemp;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pcb[i].priority<pcb[j].priority)
{
pcbtemp=pcb[i];
pcb[i]=pcb[j];
pcb[j]=pcbtemp;
}
}
}
}

void printpcb(PCB pcb[],int n)//输出就绪队列中的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status!='F')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printRpcb(PCB pcb[],int n)//输出正在运行的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='R')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void printFpcb(PCB pcb[],int n)//输出已完成的进程
{
int i;
printf("\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态");
for(i=0;i<n;i++)
{
if(pcb[i].status=='F')
printf("\n %s %d %d %d %d %c",pcb[i].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status);
}
printf("\n");
}
void staPRI(PCB pcb[],int n,int times)//静态优先级算法
{
int i=0;
printf("\n当前的系统时间为:%d\n",times);
getch();
printf("\n按优先级排序，到达就绪队列中的进程为：");
paixupcb(pcb,n);
getch();
for(i=0;i<n;i++)
{
while(pcb[i].needtime>pcb[i].usecputime)
{
pcb[i].status='R';
printf("\n按静态优先级对进程调度，正在运行的进程为：");
pcb[i].usecputime++;
times++;
printRpcb(pcb,n);
getch();
printf("\n当前的系统时间为:%d\n",times);
getch();
pcb[i].status='r';
paixupcb(pcb,n);
if(pcb[i].needtime==pcb[i].usecputime)
{
pcb[i].status='F';
printf("\n此时刻，进程%s已经完成，进程%s被撤销!\n",pcb[i].pname,pcb[i].pname);
getch();
}
printf("\n按优先级排序，就绪队列中的进程为：");
printpcb(pcb,n);
getch();
}
}
printf("\n就绪队列中已经没有进程，至此，所有的进程已经完成!\n");
getch();
printf("\n完成信息如下：");
printFpcb(pcb,n);
getch();
printf("\n\n进程调度完毕!请按任意键退出!");
}
void main()
{
PCB pcbr[MAX];
int pnum=0;
int systime=0;
printf("\t\t\t\t进程调度模拟演示程序");
inputpcb(pcbr,&pnum);
printf("\n用户输入的进程信息为：");
printpcb(pcbr,pnum);
staPRI(pcbr,pnum,systime);
}

操作系统算法设计-主存分配回收

摘 要
在内存初始化完成以后，内存中就常驻有内核映像（内核代码和数据）。以后，随着用户程序的执行和结束，就需要不断地分配和释放物理页面，内核应该为分配一组连续的页面而建立一种稳定、高效的分配策略。为此，必须解决一个比较重要的内存管理问题，即外碎片问题。频繁地请求和释放不同大小的一组连续页面，必然导致在已分配的内存块中分散许多小块的空闲页面。由此带来的问题是，即使这些小块的空闲页面加起来足以满足所请求的页面，但是要分配一个大块的连续页面可能就根本无法满足，Linux采用注明的