10操作系统原理实验指导Word文档下载推荐.docx
《10操作系统原理实验指导Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《10操作系统原理实验指导Word文档下载推荐.docx（45页珍藏版）》请在冰点文库上搜索。
然后完成进程创建原语和进程调度原语；
最后编写主函数对所做工作进行测试。
四、提示与讲解
这个实验主要需要考虑三个问题：
如何组织进程、如何创建进程和如何实现处理器调度。
考虑如何组织进程，首先就要设定进程控制块的内容。
进程控制块PCB记录各个进程执行时的情况。
不同的操作系统，进程控制块记录的信息内容不一样。
操作系统功能越强，软件也越庞大，进程控制块记录的内容也就越多。
这里的实验只是用了必不可少的信息。
一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类：
（1）标识信息
每个进程都要有一个唯一的标识符，用来标识进程的存在和区别于其他进程。
这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。
在后面给出的参考程序中，采用编号方式，也就是为每个进程依次分配一个不相同的正整数。
（2）说明信息
用于记录进程的基本情况，例如进程的状态、等待原因、进程程序存放的位置、进程数据存放位置等等。
实验中，因为进程没有数据和程序，仅使用进程控制块模拟进程，所以这部分内容仅包括进程状态。
（3）现场信息
现场信息记录各个寄存器的内容。
当进程由于某种原因让出处理器时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。
现场信息就是处理器的相关寄存器内容，包括通用寄存器、程序计数器和程序状态字等。
在实验中，可选取几个寄存器作为代表。
用大写的全局变量AX、BX、CX、DX模拟通用寄存器、大写的全局变量PC模拟程序计数器、大写的全局变量PSW模拟程序状态字。
（4）管理信息
管理信息记录进程管理和调度的信息。
例如进程优先数、进程队列指针等。
实验中，仅包括队列指针。
因此，可将进程控制块结构定义如下：
structpcb
{
intname;
//进程标识符
intstatus;
//进程状态
intAX,BX,CX,DX;
//进程现场信息，通用寄存器内容
intPC;
//进程现场信息，程序计数器内容
intPSW;
//进程现场信息，程序状态字内容
intnext;
//下一个进程控制块的位置
}
确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。
多道程序设计系统中，往往同时创建多个进程。
在单处理器的情况下，每次只能有一个进程处于运行态、其他的进程处于就绪状态或等待状态。
为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。
单处理器系统中，正在运行的进程只有一个。
因此，单处理器系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。
由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。
操作系统的实现中，系统往往在主存中划分出一个连续的专门区域存放系统的进程控制块，实验中应该用数组模拟这个专门的进程控制块区域，定义如下：
#definen10//假定系统允许进程个数为10
structpcbpcbarea[n];
//模拟进程控制块区域的数组
这样，进程控制块的链表实际上是数据结构中使用的静态链表。
进程控制块的链接方式可以采用单向和双向链表，实验中，进程控制块队列采用单向不循环静态链表。
为了管理空闲进程控制块，还应该将空闲进程控制块链接成一个队列。
实验示例程序中采用时间片轮转调度算法，这种算法是将进程控制块按照进入就绪队列的先后次序排成队列。
关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。
因此为就绪队列定义两个指针，一个头指针，指向就绪队列的第一个进程控制块；
一个尾指针，指向就绪队列的最后一个进程控制块。
实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下：
intrun;
//定义指向正在运行进程的进程控制块的指针
struct
inthead;
inttail；
}ready;
//定义指向就绪队列的头指针head和尾指针tail
intpfree;
//定义指向空闲进程控制块队列的指针
以上是如何组织进程，下面考虑如何创建进程。
进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括：
（1）申请进程控制块：
进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第二步；
（2）申请资源：
除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控制块；
如果申请成功，则执行第三步，实验无法申请资源，所以模拟程序忽略了申请资源这一步；
（3）填写进程控制块：
将该进程信息写入进程控制块内，实验中只有进程标识符、进程状态可以填写（模拟进程创建时，需输入进程标识符，进程标识符本应系统建立，并且是唯一的，输入时注意不要冲突），刚创建的进程应该为就绪态，然后转去执行第四步；
（4）挂入就绪队列：
如果原来的就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针；
如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完成。
进程创建流程图如图1所示。
多道程序设计的系统中，处于就绪状态的进程往往有多个，它们都要求占用处理器，可是单处理器系统的处理器只有一个，进程调度就是解决这个处理器竞争问题的。
进程调度的任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理器。
因此，进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理器给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理器的各个寄存器中。
实验参考程序中采用时间片轮转调度算法，这种算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占有处理器，但是规定只能使用一个“时间片”。
采用时间片轮转调度算法的进程调度流程图如图2所示。
完成上述功能后，编写主函数进行测试：
首先建立一个就绪队列，手工输入信息建立几个进程；
然后进行进程调度；
最后将指向正在运行进程的指针指向的进程控制块内容输出，察看结果。
四、参考程序
#include“stdio.h”
#definerunning1//用running表示进程处于运行态
#defineaready2//用aready表示进程处于就绪态
#defineblocking3//用blocking表示进程处于阻塞态
#definesometime5//用sometime表示时间片大小
#definen10//假定系统允许进程个数为n
intax,bx,cx,dx
;
intpc
intpsw;
//下一个进程控制块的位置
}pcbarea[n];
intPSW,AX,BX,CX,DX
PC
TIME
//模拟寄存器
inttail;
//定义就绪队列的头指针head和尾指针tail
scheduling（）//进程调度函数
inti;
if（ready.head==-1）//空闲进程控制块队列为空，退出
{
printf（“无就绪进程\n”）;
return;
i=ready.head;
//就绪队列头指针赋给i
ready.head=pcbarea[ready.head].next;
//就绪队列头指针后移
if（ready.head==-1）ready.tail=-1;
//就绪队列为空，修正尾指针ready.tail
pcbarea[i].status=running;
//修改进程控制块状态
TIME=sometime;
//设置相对时钟寄存器
//恢复该进程现场信息
AX=pcbarea[run].ax;
BX=pcbarea[run].bx;
CX=pcbarea[run].cx;
DX=pcbarea[run].dx;
PC=pcbarea[run].pc;
PSW=pcbarea[run].psw;
run=i;
}//进程调度函数结束
create（intx）//进程创建函数
if（pfree==-1）//空闲进程控制块队列为空
{
printf（“无空闲进程控制块，进程创建失败\n”）;
i=pfree;
//取空闲进程控制块队列的第一个
pfree=pcbarea[pfree].next;
//pfree后移
//填写该进程控制块的内容
pcbarea[i].name=x;
pcbarea[i].status=aready;
pcbarea[i].ax=x;
pcbarea[i].bx=x;
pcbarea[i].cx=x;
pcbarea[i].dx=x;
pcbarea[i].pc=x;
pcbarea[i].psw=x;
if（ready.head!
=-1）//就绪队列不为空时，挂入就绪队列的方式
pcbarea[ready.tail].next=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
else//就绪队列为空时，挂入就绪队列的方式
ready.head=i;
pcbarea[ready.tail].next=-1;
}//进程创建函数结束
main（）
{//系统初始化
intnum,i,j;
run=ready.head=ready.tail=-1;
pfree=0;
for（j=0;
j<
n-1;
j++）
pcbarea[j].next=j+1;
pcbarea[n-1].next=-1;
printf（“输入进程编号（避免编号冲突，以负数输入结束，最多可以创建10个进程）：
\n”）;
scanf（“%d”,&
num）;
while（num>
=0）
create（num）
scanf（“%d”,&
num）
scheduling（）;
//进程调度
if（run!
=-1）
printf（“进程标识符进程状态寄存器内容：
axbxcxdxpcpsw:
printf（“%8d%10d%3d%3d%3d%3d%3d%3d\n”,pcbarea[run].name,pcbarea[run].status,pcbarea[run].ax,pcbarea[run].bx,pcbarea[run].cx,pcbarea[run].dx,pcbarea[run].pc,pcbarea[run].psw）;
}//main（）结束
实验2模拟内存管理
深入了解可变分区存储管理方式主存分配回收的实现。
存储管理中的可变分区存储管理方式。
编写程序完成可变分区存储管理方式的主存分配回收的实现。
首先确定主存空间分配表；
然后采用首次适应算法、循环首次适应算法、最差适应算法完成主存空间的分配和回收；
四、提示与讲解
可变分区存储管理方式不预先将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。
当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间找到一个大于或等于该作业大小要求的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。
作业执行完后，它所占的主存分区被回收，成为一个空闲区。
如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。
第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；
第二，在设计的数据表格基础上设计主存分配算法；
第三，在设计的数据表格基础上设计主存回收算法。
首先，考虑第一个问题：
设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。
由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收而变动。
总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。
由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。
由于分配时空闲区有时会变成两个分区：
空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。
主存分配时查找空闲区进行分配，然后填写已分分区表，主要操作在空闲区；
某个作业执行完成后，将该分区变成空闲区，并将其与相邻空闲区合并，主要操作也在空闲区。
由此可见，主存分配和回收主要是对空闲区的操作。
这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的“已分分区表”；
一张是记录空闲区的“空闲区表”。
这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。
在实验中，采用顺序表形式，用数组模拟。
由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。
它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分分区表”还是“空闲区表”都有空闲栏目。
已分分区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；
空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。
在实际系统中，这两个表格的内容可能还要更多，实验中仅仅使用上述必须的数据。
为此，“已分分区表”和“空闲区表”在实验中有如下的结构定义：
已分分区表的定义：
#definen10//假定系统允许的作业数量最多为n
floataddress;
//已分分区起始地址
floatlength;
//已分分区长度，单位为字节
intflag;
//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名
}used_table[n];
//已分分区表
空闲区表的定义：
#definem10//假定系统允许的空闲区数量最多为m
//空闲区起始地址
//空闲区长度，单位为字节
//空闲区表登记栏标志，“0”表示空栏目，用“1”表示未分配
}free_table[m];
//空闲区表
其中分区起始地址和长度数值太大，超出了整型的表达范围，所以采用了float类型。
然后，就要考虑如何在设计的数据表格上进行主存的分配。
当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找到一个能容纳该作业的空闲区。
如果找到的空闲区正好等于该作业的长度，则把该分区全部分配给作业。
这时应该把该空闲区登记栏中的标志改为“空”，同时在已分分区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长度和作业名。
如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。
这时只要修改元空闲区的长度，且把新装入的作业登记到已分分区表中。
实验示例程序中主存分配算法采用最佳适应算法。
最佳适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。
但是最佳适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，影响了主存的使用。
为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成空闲区和已分分区两部分，而是将整个空闲区分配给作业。
在实现最佳适应算法时，可把空闲区按长度以递增方式登记在空闲区中。
分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区。
这样查找速度快，但是为使空闲区按长度以递增顺序登记在空闲分区表中，就必须在分配回收时进行空闲区表的调整。
空闲区表调整时移动表目的代价要高于查询整张表的代价，所以实验中不采用空闲区有序登记在空闲表中的方法。
动态分区方式的主存分配流程图如图3所示。
最后是可变分区方式下的主存回收问题。
可变分区方式下回收主存空间时，应该检查是否有与归还区相邻的空闲区。
若有，则应该合并成一个空闲区。
一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区又无下邻空闲区。
在实现回收时，首先将作业归还的区域在已分分区表中找到，将该栏目的状态变为“空”，然后检查空闲区表中标志为“未分配”的栏目，查找是否有相邻空闲区；
最后，合并空闲区，修改空闲区表。
假定作业归还得分区起始地址为S，长度为L，则：
（5）归还区有下邻空闲区
如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，则表明归还区有一个下邻空闲区。
这时只要修改第j栏登记项的内容：
起始地址=S；
第j栏长度=第j栏长度+L；
则第j栏指示的空闲区是归还区和下邻空闲区合并后的大空闲区。
（6）归还区有上邻空闲区
如果空闲区表中某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，则表明归还区有一个上邻空闲区。
这时要修改第k栏登记项的内容（起始地址不变）：
第k栏长度=第k栏长度+L；
则第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。
（7）归还区既有上邻空闲区又有下邻空闲区
如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，这表明归还区既有一个上邻空闲区，又有一个下邻空闲区。
这时对空闲区表的修改如下：
第k栏长度=第k栏长度+第j栏长度+L；
（第k栏起始地址不变）
第j栏状态=“空”；
（将第j栏登记项删除）
则第k栏指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区；
原来的下邻空闲区登记项（第j栏）被删除，置为“空”。
（8）归还区既无上邻空闲区又无下邻空闲区
如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。
这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下：
第t栏起始地址=S；
第t栏长度=L；
第t栏状态=“未分配”
这样，第t栏指示的空闲区是归还区。
按上述方法归还主存区域的流程图如图4所示。
由于是模拟实验，没有真正的主存要分配，所以在实验中，首先应建立一张空闲区表，初始状态只有一个空闲登记项（假定的主存空闲区）和一张所有状态都为“空”的已分分区表，假定主存空间为110KB，操作系统占用10KB，其余为空闲区；
然后，可以选择进行主存分配或主存回收，如果是分配，要求输入作业名和所需主存空间大小，如果是回收，输入回收作业的作业名，循环进行主存分配和回收后，如果需要，则显示两张表的内容，以检查主存的分配和回收是否正确。
五、参考程序
#defineminisize100
intflag;
allocate（charJ,floatxk）//采用最佳适应算法为作业J分配xk大小的主存空间
inti,k;
floatad;
k=-1;
for（i=0;
i<
m;
i++）//寻找主存空间中大于xk的最小空闲区登记项k
if（free_table[i].length>
=xk&
&
free_table[i].fl
升级会员 