中南大学
计算机操作系统
实验报告
目 录
1.设计目的....................... 3
2.设计要求....................... 3
3.设计题目....................... 3
4.设计过程....................... 3
4.1 设计思路................... 3
4.2 实验过程................... 5
4.3 调度性能分析............... 9
5.总结.......................... 10
6.代码附录...................... 10
计算机操作系统
1.设计目的
1、增强学生对计算机操作系统基本原理、基本理论、基本算法的理解;
2、提高和培养学生的动手能力。
2.设计要求
1、每人至少选作1题,多做不限;
2、每人单独完成,可以讨论,但每人的设计内容不得完全相同,抄袭或有2人/多人设计完全一样者,不能通过;
3、设计完成后,应上交课程设计文档,文档格式应是学校课程设计的标准格式,所有学生的封面大小、格式也必须一样;
4、同时上交设计的软盘(或以班刻录光盘)。
3.设计题目
调度算法的模拟:模拟各种调度算法,并进行调度性能分析。
4.设计过程
4.1 设计思路
模拟了一个作业调度算法,其中用到了先来先服务算法(FCFS)、短作业优先算法(SJF)、最高响应比优先算法(HRN)三种算法。
如下,分别为三种算法的程序流程图。
4.2 实验过程
图1 - 开始界面
图2 – 输入作业的信息(名字、提交时间、运行时间)
图3 – 选择算法(FCFS、SJF、HRN)
图4、5 – 选择FCFS算法后输出结果
图6、7 – 选择SJF算法后输出结果
图8、9 – 选择HRN算法后输出结果
4.3 调度性能分析
1.先来先服务算法(FCFS)
优点:
能体现公平性;
缺点:
一旦一个较长的作业进入系统后就会长时间的占用系统的资源,这样如果有优先级较高的短作业需要执行的话需要等待很长时间。
2.短作业优先算法(SJF)
优点:
比前者改善了平均周转时间和平均带权周转时间,缩短作业的等待时间,提高系统的吞吐量;
缺点:
对长作业非常不利,可能长时间得不到执行,未能一句作业的紧迫程度来划分执行的优先级,难以准确估计作业的执行时间,从而影响调度性能。
3.最高响应比优先算法(HRN)
优点:
这种算法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考虑执行时间而未考虑等待时间的长短。因此,这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。
缺点:
由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF法,从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外,由于每次调度前要计算响应比,系统开销也要相应增加。
5.总结
在设计中,我构想在理想情况下将每个作业用一个结构体来存储其对应的信息,并将各个结构体用结构体数组的形式组织到一起。在每个结构体中将作业的作业名、进入时间、运行时间、周转时间、带权周转时间这些信息全部存入,以便后期的排序和输出等待队列信息。
通过这几次实验,我发现了自身的不足,比如没有很好的书写习惯,考虑问题不周到,对于调度算法的理解不够深入等。但在编程的过程中我体验到了一分耕耘一分收获的喜悦;多次调试后程序成功运行了,那时候的欢乐是我以前无法想象的。果然,学习任何一门课程,只要学得用心,都可以从中体会到学习的快乐。今后我的进步,想必都是从这一点一点敲入编译器的代码中获得的。
6.代码附录
#include <stdio.h>
#include <stdlib.h>
#define getpch(type)(type*)malloc(sizeof(type))
struct worktime
{
float Tb;//作业运行时刻
float Tc;//作业完成时刻
float Ti;//周转时间
float Wi;//带权周转时间
};
struct jcb
{ /*定义作业控制块JCB */
char name[10];//作业名
float subtime;//作业提交时间
float runtime;//作业所需的运行时间
char resource;//所需资源
float Rp;//后备作业响应比
char state;//作业状态
struct worktime wt;
struct jcb *link;//链指针
}*jcb_ready = NULL, *j;
typedef struct jcb JCB;
float T = 0;
void sort()/* 建立对作业进行提交时间排列函数*/
{
JCB *first, *second;
int insert = 0;
if ((jcb_ready == NULL) || ((j->subtime)<(jcb_ready->subtime)))/*作业提交时间最短的,插入队首*/
{
j->link = jcb_ready;
jcb_ready = j;
T = j->subtime;
j->Rp = 1;
}
else/* 作业比较提交时间,插入适当的位置中*/
{
first = jcb_ready;
second = first->link;
while (second != NULL)
{
if ((j->subtime)<(second->subtime))/*若插入作业比当前作业提交时间短,*/
{ /*插入到当前作业前面*/
j->link = second;
first->link = j;
second = NULL;
insert = 1;
}
else/* 插入作业优先数最低,则插入到队尾*/
{
first = first->link;
second = second->link;
}
}
if(insert == 0) first->link = j;
}
}
void SJFget()/* 获取队列中的最短作业 */
{
JCB *front, *mintime, *rear;
int ipmove = 0;
mintime = jcb_ready;
rear = mintime->link;
while (rear != NULL)
if ((rear != NULL) && (T >= rear->subtime) && (mintime->runtime)>(rear->runtime))
{
front = mintime;
mintime = rear;
rear = rear->link;
ipmove = 1;
}
else
rear = rear->link;
if(ipmove == 1)
{
front->link = mintime->link;
mintime->link = jcb_ready;
}
jcb_ready = mintime;
}
void HRNget()/* 获取队列中的最高响应作业 */
{
JCB *front, *mintime, *rear;
int ipmove = 0;
mintime = jcb_ready;
rear = mintime->link;
while (rear != NULL)
if((rear != NULL) && (T >= rear->subtime) && (mintime->Rp)<(rear->Rp))
{
front = mintime;
mintime = rear;
rear = rear->link;
ipmove = 1;
}
else
rear = rear->link;
if(ipmove == 1)
{
front->link = mintime->link;
mintime->link = jcb_ready;
}
jcb_ready = mintime;
}
void input()/* 建立作业控制块函数*/
{
int i,num;
printf("\nplese input the number of the job:");
scanf("%d", &num,2);
for(i = 0; i<num; i++)
{
printf("\nthe ordernumber of the job No.%d:\n", i);
j = getpch(JCB);
printf("\nplease input the name of the job:");
scanf("%s", j->name);
printf("\nplease input the time when the job was submitted:");
scanf("%f", &j->subtime);
printf("\nplease input the runtime of the job:");
scanf("%f", &j->runtime);
printf("\n");
j->state = 'w';
j->link = NULL;
sort();/* 调用sort函数*/
}
}
int space()
{
int l = 0;
JCB *jr = jcb_ready;
while(jr != NULL)
{
l++;
jr = jr->link;
}
return(l);
}
void disp(JCB* jr, int select)/*建立作业显示函数,用于显示当前作业*/
{
if(select == 3)
printf("\nwork service time response ratio runtime complete time turnover time weighted turnover time\n");
else
printf("\nwork service time runtime complete time turnover time weighted turnover time\n");
printf("|%s\t", jr->name);
printf("|%.2f\t", jr->runtime);
if(select == 3)
printf("|%.2f", jr->Rp);
if(j == jr)
{
printf("|%.2f\t", jr->wt.Tb);
printf("|%.2f", jr->wt.Tc);
printf("|%.2f\t", jr->wt.Ti);
printf("|%.2f", jr->wt.Wi);
}
printf("\n");
}
void check(int select)/* 建立作业查看函数 */
{
JCB* jr;
printf("\n **** the running job is:%s",j->name);/*显示当前运行作业*/
disp(j,select);
jr=jcb_ready;
printf("\n ****the current ready queue is:\n");/*显示就绪队列状态*/
while(jr!=NULL)
{
jr->Rp=(T-jr->subtime)/jr->runtime;
disp(jr,select);
jr=jr->link;
}
destroy();
}
int destroy()/*建立作业撤消函数(作业运行结束,撤消作业)*/
{
printf("\n job [%s] is completed.\n",j->name);
free(j);
}
void running(JCB* jr)/* 建立作业就绪函数(作业运行时间到,置就绪状态*/
{
if (T>=jr->subtime)
jr->wt.Tb=T;
else
jr->wt.Tb=jr->subtime;
jr->wt.Tc=jr->wt.Tb+jr->runtime;
jr->wt.Ti=jr->wt.Tc-jr->subtime;
jr->wt.Wi=jr->wt.Ti/jr->runtime;
T=jr->wt.Tc;
}
int main()/*主函数*/
{
int select=0,len,h=0;
float sumTi=0,sumWi=0;
input();
len=space();
printf("\n\t1.FCFS 2.SJF 3.HRN\n\nplease choose a Algorithm:");
scanf("%d",&select);
while((len!=0)&&(jcb_ready!=NULL))
{
h++;
printf("\n excute %d job \n",h);
j=jcb_ready;
jcb_ready=j->link;
j->link=NULL;
j->state='R';
running(j);
sumTi+=j->wt.Ti;
sumWi+=j->wt.Wi;
check(select);
if(select==2&&h<len-1)
SJFget();
if(select==3&&h<len-1)
HRNget();
printf("\n press any key to continue......\n");
getchar();
}
printf("\n\n the job is completed.\n");
printf("\t the turnover time of this group of work:%.2f\n",sumTi/h);
printf("\t the weighted turnover time of this group of work:%.2f\n",sumWi/h);
getchar();
}
第二篇:计算机操作系统-处理机调度实验报告
中南大学
实验名称:处理机调度
课程名称:计算机操作系统
学生姓名 盛 希 玲
学 号 0903060215
学 院 信息科学与工程学院
专业班级 电子信息工程0602
完成时间 20##年10月12日
目 录
一 实验内容... 2
二 实验目的... 2
三 实验题目... 2
四 基本思想... 2
五 算法分析... 2
六 流程图... 3
七 算法描述... 4
八 运行输出结果... 9
一 实验内容
选择一个调度算法,实现处理机调度。
二 实验目的
多道系统中,当就绪进程数大于处理机数时,须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度,以加深了解处理机调度的工作。
三 实验题目
设计一个按优先权调度和时间片轮转算法实现处理机调度的程序。
四 基本思想
先选择时间片的个数和每个时间片需要的时间,正在运行的进程每运行一秒其优先权数目加一,即其优先权减小。每个时间片运行结束后,选择进入时间片进程优先权数目最小的进程,开始下一个时间片的运行。如果有进程运行结束,则离开,再在就绪队列中选择优先权数目最小的进程进入。在运行期间,如果有新的进程来到,按优先权大小放入就绪队列中。
五 算法分析
定义一个结构体,此包含了PCB的信息:
struct PCB
{
char PID[5]; /*进程名*/
int needtime; /*要求运行的时间*/
int cputime; /*已运行时间*/
int priority; /*优先权(越小越高)*/
int starttime; /*进入就绪队列的时间*/
int overtime; /*运行完成的时间*/
int state; /*状态:1就绪2运行3完成*/
struct PCB *next;
};
子函数struct PCB *create(int num,int n)用来建立一个按优先级大小排列的就绪进程链表和一个按时间先后循序排列的将进入就绪进程的链表。
main()函数中用一while循环输出进入时间片的进程状态。
六 流程图
七 算法描述
#define NULL 0
#define LEN sizeof(struct PCB)
#include"stdio.h"
#include"stdlib.h"
struct PCB
{
char PID[5]; /*进程名*/
int needtime; /*要求运行的时间*/
int cputime; /*已运行时间*/
int priority; /*优先权(越小越高)*/
int starttime; /*进入就绪队列的时间*/
int overtime; /*运行完成的时间*/
int state; /*状态:1就绪2运行3完成*/
struct PCB *next;
};
struct PCB *create(int num,int n)
/*创建进程,并将进程按优先级顺序插入队列中*/
{
struct PCB *head,*p,*p1,*p2;
int i;
head=NULL; /*头指针指零*/
for(i=1;i<=num;i++) /*循环建立所有进程*/
{
printf("请输入第%d个进程的信息\n",i);
p=(struct PCB *)malloc(LEN); /*开辟一个空间*/
printf("进程名:"); /*输入进程名*/
scanf("%s",p->PID);
printf("要求运行的时间:"); /*输入要运行的时间*/
scanf("%d",&p->needtime);
p->cputime=0; /*占用处理机的时间赋为零*/
printf("优先权:"); /*输入优先权*/
scanf("%d",&p->priority);
if(n==1)
p->starttime=0; /*进入就绪队列的时间赋为零*/
else
{
printf("进入就绪队列时间:"); /*输入进入就绪队列的时间*/
scanf("%d",&p->starttime);
}
p->overtime=-1; /*运行没有结束所以运行完成的时间赋为-1*/
p->state=1; /*状态赋为就绪状态*/
p1=head; /*p1指针指向头指针*/
if(head==NULL) /*如果头指针为零将头指针指向新建立的进程*/
{head=p;head->next=NULL;}
else /*头指针不为零的情况*/
{
if(n==1)
while(p1!=NULL&&p->priority>p1->priority) /*查找插入点*/
{p2=p1;
p1=p1->next;
}
else
while(p1!=NULL&&p->starttime>p1->starttime) /*查找插入点*/
{p2=p1;
p1=p1->next;
}
if(head==p1) /*优先权的值最小作为表头*/
{p->next=head;p2=head=p;}
else /*否则的话插入*/
{p2->next=p;p->next=p1;}
}
}
return(head);
}
void main()
{
char now[5];
int cho,num,num1,timepiece,time,i,j,k,flag,choo,clock=0;
struct PCB *head,*head1,*over,*later,*l,*l1,*l2,*p,*p0,*p1,*p2,*q,*q1,*q2,*q3;
over=NULL;
printf("初始化进程...\n");
printf("输入总的就绪进程数:");
scanf("%d",&num);
head=create(num,1); /*建立就绪进程的链表*/
printf("输入将会就绪的进程数:");
scanf("%d",&num1); /*建立将会进入就绪进程的链表*/
later=create(num1,2);
printf("cpu是否开始运行:1是 2不是--");
scanf("%d",&cho);
if(cho==1) /*处理机开始进行调度*/
{
printf("现在的时间是:");
scanf("%s",now);
printf("显示所有就绪的进程:\n");
p2=head;
printf("进程名\t要求运行时间\t已运行时间\t优先权\t状态(1就绪2运行3结束)\n");
while(p2!=NULL)
{
printf("%s\t%d\t\t%d\t\t%d\t%d\n",p2->PID,p2->needtime,p2->cputime,p2->priority,p2->state);
p2=p2->next;
}
printf("请输入时间片总数:");
scanf("%d",&timepiece);
printf("请输入时间片的时间:");
scanf("%d",&time);
printf("运行正式开始!\n");
head1=head;
printf("\t\t进程名\t要求运行时间\t已运行时间\t优先权\t状态\n");
for(i=1;i<=timepiece;i++) /*将进入时间片运行的进程用头指针head1指示,并改变就绪进程头指针head的指向*/
{
if(head!=NULL)
{
p=head;
head=head->next;
}
else break;
}
p->next=NULL;
while(head1!=NULL) /*就绪进程头指针不为零就循环*/
{
head1->state=2; /*状态:1就绪2运行3完成*/
for(j=1;j<=time;j++) /*每个时间片所需时间的循环*/
{
clock++; /*定时器每秒加1*/
if(later!=NULL&&clock==later->starttime)
/*如果将进入就绪队列的进程时间到达加入就绪队列*/
{l=later;
l1=head;
later=later->next;
if(head==NULL)
{head=l;head->next=NULL;}
else
{
while(l1!=NULL&&l1->priority<=l->priority)
{l2=l1;l1=l1->next;}
if(l1==head)
{
l->next=head;
head=l;
}
else
{
l2->next=l;
l->next=l1;
}
}
}
flag=0;
printf("\n%3d秒 时间片第%d秒 ",clock,j);
q=head1;
if(head1->needtime>head1->cputime) /*以运行时间和优先权都加1*/
{
head1->cputime++;
head1->priority++;
while(q) /*运行队列不为零输出其信息*/
{if(q==head1)
printf("%s\t%d\t\t%d\t\t%d\t%d\n",q->PID,q->needtime,q->cputime,q->priority,q->state);
else
printf("\t\t %s\t%d\t\t%d\t\t%d\t%d\n",q->PID,q->needtime,q->cputime,q->priority,q->state);
q=q->next;
}
}
if(head1->needtime==head1->cputime)
/*运行完成将其放入over为头指针的链表中*/
{
head1->state=3;
head1->overtime=clock;
if(over==NULL)
{over=head1;head1=head1->next;over->next=NULL;}
else
if(over!=NULL&&head1!=NULL)
{
p1=head1->next;
p0=over;
over=head1;
over->next=p0;
head1=p1;
}
flag=1;
}
if(flag==1) break;
}
if(flag==1) /*有进程结束的情况*/
{
if(head!=NULL) /*就绪队列不为零将优先权最高的放入运行链表中*/
{q1=head;
head=head->next;
q2=head1;
while(q2!=NULL&&q2->priority<=q1->priority)
{q3=q2;q2=q2->next;}
if(q2==head1)
{
q1->next=head1;
head1=q1;
}
else
{
q3->next=q1;
q1->next=q2;
}
}
}
else /*无进程结束的情况,寻找优先权最高的运行*/
{
head1->state=1;
q1=head1;
head1=head1->next;
q2=head1;
while(q2!=NULL&&q2->priority<=q1->priority)
{q3=q2;q2=q2->next;}
if(q2==head1)
{q1->next=head1;head1=q1;}
else
{q3->next=q1;q1->next=q2;}
}
}
}
printf("cpu结束运行!\n");
printf("是否输出所有结束的进程:1是2不是--");
scanf("%d",&choo);
if(choo==1) /*输出所有完成运行的进程*/
{
printf("开始时间:%s\n",now);
printf("进程名\t要求运行时间\t进入就绪队列的时间\t运行完成的时间\n");
while(over!=NULL)
{
printf("%s\t%d\t\t%d\t\t\t%d\n",over->PID,over->needtime,over->starttime,over->overtime);
over=over->next;
}
}
}
八 运行输出结果
初始化进程如右图
显示现在的时间和所有就绪的进程
输入时间片的总数和每个时间片的时间
运行时显示的信息