实习一处理器调度.docx
《实习一处理器调度.docx》由会员分享，可在线阅读，更多相关《实习一处理器调度.docx（29页珍藏版）》请在冰点文库上搜索。
实习一处理器调度
实习一处理器调度
一.实习内容
选择一个调度算法，实现处理器调度。
二.实习目的
本实习模拟在单处理器环境下的处理器调度，加深了解处理器调度的工作。
三.实习题目
设计一个按优先数调度算法实现处理器调度的程序。
四.设计思想
1.设计思路
（1）假定系统有5个进程，每个进程用一个PCB来代表。
（2）开始运行之前，为每个进程确定它的“优先数”和“要求运行时间”。
通过键盘输入这些参数。
（3）按进程优先数排列进程，优先数最大的进程插入队首，否者比较进程优先数，插入适当位置。
（4）处理器总是选择队首进程运行。
采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。
（5）进程运行一次后，若要求运行时间不等于0，则将它加入就绪队列，否则，将状态改为“结束”，退出就绪队列。
（6）若就绪队列为空，结束，否则转到（4）重复。
2.主要数据结构
structpcb{/*定义进程控制块PCB*/
charname[10];/*进程名*/
charstate;/*状态*/
intsuper;/*优先数*/
intntime;/*要求运行时间*/
intrtime;/*周转时间*/
structpcb*link;/*下一个进程pcb首地址*/
}
3.主要代码结构及代码段分析
voidinput（）/*建立进程控制块函数*/
{inti,num;
system（"cls"）;/*清屏*/
for（i=1;i<=5;i++）
{printf（"\nprojectNo.%d:
\n",i）;
p=getpch（PCB）;
printf（"\npleaseinputprojectname:
"）;
scanf（"%s",p->name）;
printf（"\npleaseinputprojectpriority:
"）;
scanf（"%d",&p->super）;
printf（"\npleaseinputprojectrunningtime:
"）;
scanf（"%d",&p->ntime）;
printf（"\n"）;
p->rtime=0;p->state='W';
p->link=NULL;
sort（）;/*调用sort函数*/
}
}
voidsort（）/*建立对进程进行优先级排列函数*/
{
PCB*first,*second;
intinsert=0;
if（（ready==NULL）||（（p->super）>（ready->super）））/*优先级最大者,插入队首*/
{
p->link=ready;
ready=p;
}
else/*进程比较优先级,插入适当的位置中*/
{
first=ready;
second=first->link;
while（second!
=NULL）
{
if（（p->super）>（second->super））/*若插入进程比当前进程优先数大插入到当前进程前面*/
{
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else/*插入进程优先数最低,则插入到队尾*/
{
first=first->link;
second=second->link;
}
}
if（insert==0）first->link=p;
}
}
intspace（）/*求队列长度*/
{
intl=0;
PCB*pr=ready;
while（pr!
=NULL）
{l++;
pr=pr->link;
}
return（l）;
}
voiddisp（PCB*pr）/*建立进程显示函数,用于显示当前进程*/
{
printf（"\nproname\tstate\t\tpriority\tneedtime\tremaintime\n"）;
printf（"|%s\t\t",pr->name）;
printf（"|%c\t\t",pr->state）;
printf（"|%d\t\t",pr->super）;
printf（"|%d\t\t",pr->ntime）;
printf（"|%d\t\t",pr->rtime）;
printf（"\n"）;
}
voidcheck（）/*建立进程查看函数*/
{
PCB*pr;
printf（"\n****therunningprojectis:
\n"）;/*显示当前运行进程*/
disp（p）;
pr=ready;
printf（"\n****thereadyprojectstateis:
\n"）;/*显示就绪队列状态*/
while（pr!
=NULL）
{
disp（pr）;
pr=pr->link;
}
}
voiddestroy（）/*建立进程撤消函数（进程运行结束,撤消进程）*/
{printf（"\nproject[%s]hasfinished.\n",p->name）;
free（p）;
}
voidrunning（）/*建立进程就绪函数（进程运行时间到,置就绪状态*/
{（p->rtime）++;
if（p->rtime==p->ntime）
{p->state='E';
printf（"\n****thefinishedprojectis:
\n"）;
disp（p）;
destroy（）;
}/*调用destroy函数*/
else
{
（p->super）--;
p->state='W';
sort（）;/*调用sort函数*/
}
}
voidmain（）/*主函数*/
{
intlen,h=0;
charch;
input（）;
len=space（）;
while（（len!
=0）&&（ready!
=NULL））
{
ch=getchar（）;
h++;
printf（"-----------------------------------------------------"）;
printf（"\nnowis%drounds.\n",h）;
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check（）;
running（）;
printf（"\npressanykeytocontinue......\n"）;
}
printf（"\n\nallprojectshavefinished.\n"）;
getch（）;/*从键盘获得字符*/
}
五.上机实习所用平台及相关软件
本程序在windowsxp平台下，TC2.0编译器编译通过。
六.调试过程
调试数据：
进程名优先数要求运行时间
P123
P234
P342
P431
P512
测试结果：
七.总结
（1）处理机调度使用了队列存储结构，使执行更加方便。
（2）进程按优先数进行链表排序。
（3）通过本实验，我进一步加深了对处理机调度过程的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。
实习二主存空间的分配和回收
一.实习内容
主存储器空间的分配和回收。
二.实习目的
通过本实习帮助理解在不同的存储管理方式下应怎样进行存储空间的分配和回收。
三.实习题目
可变分区管理方式下采用首次适应算法实现主存分配和回收。
四.设计思想
1.设计思路
（1）可变分区方式是按作业需要的主存空间大小来分割分区的。
当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。
假定内存大小为128K。
（2）采用首次适应算法分配回收内存空间。
运行时，输入一系列分配请求和回收请求。
分区回收有四种情况：
1.待回收区（以下称为自由块）与自由主存队列中有上邻空闲区,回收时直接将其大小加到其上邻空闲区的大小上即可.
2.自由块有下邻空闲区,此时需要将前驱的next指针改为指向自由块首址,而将自由块的next指针指向其下邻空闲区中的下一节点,同时合并大小.
3.自由块既有上邻区也有下邻区,此时需要将其上邻区的next指针指向自由块下邻区的next指向的地址,同时合并三个可用分区的大小.
4.自由块不存在空闲邻区,是独立的一块.此时将其插入到自由主存队列中即可.由于在合并分区的时候已经是以按地址来放置队列的,故无须再对队列中元素进行排序了.
2.主要数据结构
structtable{
charjob;/*作业标号*/
floataddress;/*分区起始地址*/
floatlength;/*分区长度，单位为字节*/
intflag;/*分区表的状态位*/
structtable*FRlink;/*前向指针*/
structtable*RElink;/*后向指针*/
}*free_table=NULL,*place;/*已分配分区表,空闲分区表*/
3.主要代码结构及代码段分析
/*空间分区链表初始化*/
FRtable*init（FRtable*tb）
{
tb->FRlink=NULL;
tb->job=nl;
tb->address=1064;
tb->length=1192;
tb->flag=0;
tb->RElink=NULL;
returntb;
}
/*主存分配函数，为作业job分配大小为xk的分区空间*/
voidallocate（charjob,floatxk）
{/*采用FF,算法分配xk大小的空间,寻找到合适的空闲分区，开始分配。
若寻找到的合适的空闲分区大于作业申请的空间minisize大小，则分割该分区，产生一个将要分配的合适大小分区和一个新的空间分区，重新记在"空间分区链表"中*/
FRtable*tb,*link;
if（free_table->FRlink==NULL&&free_table->RElink==NULL）
{/*给首个作业分配空间，改写分区链表*/
free_table->job=job;
free_table->length=xk;
free_table->flag=1;
if（xk>maxisize）{/*未寻找到合适的空间分区，返回*/
printf（">>spaceapplyfail!
\n"）;
return;}
else
{/*当申请的空间小于内存空间时，才划分空间*/
tb=getspace（FRtable）;
free_table->RElink=tb;
tb->FRlink=free_table;
tb->job=nl;
tb->address=1064+xk;
tb->length=maxisize-xk;
tb->flag=0;
}
free_table->FRlink=NULL;
if（xk<=maxisize）tb->RElink=NULL;/*当申请的空间小于内存空间时，tb才被定义*/
}
/*主存回收函数，回收作业job所占用的分区空间*/
voidreclaim（charjob）
{intbool1=0,bool2=0;
FRtable*tb,*link;
tb=free_table;
link=NULL;
do
{if（job==tb->job&&1==tb->flag）break;/*寻找分配分区表中对应的登记项在分配分区表中，未找到作业job登记占用的分区空间,退出回收*/
tb=tb->RElink;
if（tb==link）
{printf（"\n>>sorry,thejobisnotexist%c!
\n",job）;
return;
}
}while（tb!
=link）;
bool1=（NULL==tb->FRlink||tb->FRlink==tb->RElink）?
1:
tb->FRlink->flag;
bool2=（NULL==tb->RElink||tb->FRlink==tb->RElink）?
1:
tb->RElink->flag;
if（bool1&&bool2）
{/*无上下相邻空闲空间，回收的分区信息直接填写入空闲分区表*/
tb->job=nl;
tb->flag=0;
}
elseif（（NULL==tb->FRlink||1==tb->FRlink->flag）&&0==tb->RElink->flag）
{/*回收分区与下相邻空闲空间相邻，与下相邻空闲空间合并；
回收区首地址作为新空闲去的首地址，大小为两者之和*/
link=tb->RElink;
tb->job=nl;
tb->length+=link->length;
tb->flag=0;
tb->RElink=link->RElink;
if（NULL!
=link->RElink）link->RElink->FRlink=tb;
free（link）;
}
elseif（0==tb->FRlink->flag&&1==tb->RElink->flag）
{/*回收分区与上相邻空闲空间相邻，与上相邻空闲空间合并；上相邻空闲空间首地址作为新空闲去的首地址，大小为两者之和*/
link=tb->FRlink;
link->length+=tb->length;
link->RElink=tb->RElink;
tb->RElink->FRlink=link;
if（free_table==tb）free_table=link;
free（tb）;
}
elseif（0==tb->FRlink->flag&&0==tb->RElink->flag）
{/*回收分区与上下相邻空闲空间相邻，与上下相邻空闲空间合并；上相邻空闲空间首地址作为新空闲去的首地址，大小为三者之和*/
link=tb->FRlink;
link->length=link->length+tb->length+tb->RElink->length;
link->RElink=tb->RElink->RElink;
if（NULL!
=tb->RElink->RElink）tb->RElink->RElink->FRlink=link;
if（free_table==tb）free_table=link;
free（tb）;
free（tb->RElink）;
}
}
/*显示空间分区链表*/
voiddisplay（FRtable*tb）
{FRtable*temp;
temp=NULL;
printf（"\n\tnumber\tspaceaddress\tspacesize（KB）\tstate\n"）;
printf（"\n\tsys\t1024.00\t40.00\t\t1\n"）;
do
{printf（"\n\t%c\t%.2f\t%.2f\t\t%d\n",tb->job,tb->address,tb->length,tb->flag）;
tb=tb->RElink;
}while（temp!
=tb）;
}
/*主函数*/
intmain（）
{FRtable*ta=getspace（FRtable）;
free_table=init（ta）;
menu（）;
}
intmenu（）
{inti,a;
floatxk;
charjob;
printf（"\nmenu:
\n\t0-Exit\n\t1-Allocation\n\t2-Reclaim\n"）;
printf（">>pleasechoseyouroperate（0-2）:
"）;
scanf（"%d",&a）;
switch（a）
{
/*a=0,程序结束*/
case0:
exit（0）;
/*a=1,分配主存空间*/
case1:
clrscr（）;
printf（">>pleaeinputjobnumberandneededallocation:
"）;
scanf（"%*c%c%f",&job,&xk）;
allocate（job,xk）;
display（free_table）;
getch（）;
menu（）;
/*a=2,回收主存空间*/
case2:
clrscr（）;
printf（">>pleaseinputthejobnumberyouwanttoreclaim:
"）;
scanf（"%*c%c",&job）;
reclaim（job）;
display（free_table）;
menu（）;
default:
printf（">>ERROR：
Nothiechoose!
\n"）;
menu（）;
}
}
}
五.上机实习所用平台及相关软件
本程序在windowsxp平台下，TC2.0编译器编译通过。
六.调试过程
调试数据：
作业号所需空间
12
110000
调试结果：
七.总结
（1）在程序中充分考虑到出错处理。
比如在功能选择菜单中，在用户申请磁盘空间时，若要求的空间大小大于空闲空间大小，则提示“spaceapplyfail!
”；在回收主存空间时，若用户输入的文件名不存在，则提示“sorry,thejobisnotexist!
”。
这样提高了程序的健壮性。
（2）在回收主存空间时，分情况讨论空闲块的合并。
先考虑和后面的空闲块或许会有合并的情况，再考虑是否可以和前面的块进行合并，如果没有和前面或者后面的空闲块进行合并，则新建一个表目。
这样程序结构清晰，逻辑性强。
（3）通过本实验，我进一步加深了对主存空间的分配回收过程的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。
实习三磁盘存储空间的分配和回收
一.实习内容
模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。
二.实习目的
磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。
用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。
一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。
怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。
三.实习题目
用位示图管理磁盘存储空间
四.设计思想
1.设计思路
（1）为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。
为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。
位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。
位示图的形式与实习二中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。
（2）申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。
假设现在有一个盘组共8个柱面，每个柱面有2个磁道（盘面），每个磁道分成4个物理记录。
那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：
柱面号=字节号
磁道号=位数/4
物理记录号=位数%4
（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。
按照
（2）中假设的盘组，归还块在位示图中的位置计算如下：
字节号=柱面号
位数=磁道号⨯4+物理记录号
2.主要数据结构
structFile
{
intzhumian;/*柱面号*/
intcidao;/*磁道号*/
intjilu;/*记录号*/
}*file;
3.主要代码结构及代码段分析
voidmain（）
{inta[8][8]={{1,1,1,0,1,1,1,0},{1,0,1,0,1,0,1,0},{1,1,1,0,0,1,1,0},{1,0,1,0,1,0,1,0},{1,0,0,0,1,0,1,0},{0,0,1,0,0,0,0,0},{1,1,1,0,0,1,1,0},{1,1,0,0,0,1,1,0}};/*位示图*/
inti,j;
charch;
intm=1;
inte,b,c;
printf（"displaythebit-map:
"）;/*打印位示图*/
printf（"\n\t-----------------------------------\t"）;
for（i=0;i<8;i++）
{
printf（"\n\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t",a[i][0],a[i][1],a[i][2],a[i][3],a[i][4],a[i][5],a[i][6],a[i][7]）;
}
while（m!
=0）{
printf（"\n\tmenu:
\n\t1.applyaspace\n\t2.reclaima
space\n\t3.exit\t\n"）;
printf（"pleaseinputyourchoice:
"）;
scanf（"%d",&m）;
switch（m）
{/*申请一个空间*/
case1:
clrscr（）;
for（i=0;i<8;i++）
{for（j=0;j<8;j++）
if（a[i][j]==0）
{file->zhumian=i;
file->cidao=j/4;
file->jilu=j%4;
a[i][j]=1;
break;
}
break;
}
printf（"\n\tzhumian\tcidao\tjilu\t\n"）;
prin
升级会员 