Linux操作系统实验报告 存储管理试验
电子信息学院
实验报告书
课程名：《Linux操作系统实验》
题 目： 实验三存储管理试验
实验类别 【验证】
班 级： BX0907
学 号： 09
姓 名： 吴沛儒
1、 实验内容或题目
(1)模拟初始内存页面分配（数组、结构体均可）
(2)实现Buddy heap算法
(3)通过键盘输入随机产生申请和释放操作
- 请求：r8代表申请8个页面。
- 释放：f4代表释放4个页面。
(4)每个申请或释放操作，都在屏幕上显示操作前与操作后的内存分配的对比图。
(5)实验假设申请和释放的页数都是2的整次幂。
(1)建立工作集页面模型。
(2)利用随机函数动态生成进程访问页面的序列号。
(3)实现FIFO页面淘汰算法。
(4)实现页故障率反馈模型。
2、 实验目的与要求
①(1) 用C语言是实现模拟Linux系统中连续内存分配用到的伙伴对算法。
(2) 通过链表的形式输出在内存申请和释放过程中内存状态的对比图。
②(1)了解工作集模型的原理及其特点。
(2)实现页故障率反馈模型。
3、 实验步骤与源程序
1. Buddy heap算法模拟
源程序;
#include <stdio.h>
#include <stdlib.h>
typedef struct block
{
int size;
int start;
int loc;
struct block *next;
struct block *prior;
}block;
int maxsize=512;
block *note;
block *id[10];
void printmem(){
int i;
for(i=9; i>=0;i--){
printf("%d ->",i);
block * temp = (struct block *)malloc(sizeof(struct block));
temp = id[i]->next;
while(temp!=NULL){
printf("%d(%s)(%d)->",temp->size,temp->loc==1?"占用":"空闲",temp->start); temp=temp->next;
}
printf("\n");
}
}
void init(){
int i;
for(i=0;i<9;i++){
id[i]=(struct block *)malloc(sizeof(struct block));
id[i]->prior=id[i];id[i]->next=NULL;
}
note=(struct block *)malloc(sizeof(struct block));
note->size=maxsize;
note->start=0;
note->loc=0;
note->next=NULL;
id[9]=(struct block *)malloc(sizeof(struct block));
id[9]->next=note;
id[9]->prior=id[9];
note->prior=id[9];
printmem();
}
int power(int x,int y){
int k=0,tmp=1;
for(;k<y;k++){
tmp=tmp*x;
}
return tmp;
}
int root(int x,int y){
int result=y,count=0;
while(result!=1){
result=result/x;
count++;
}
return count;
}
int split(int tempId){
block * pend=(struct block *)malloc(sizeof(struct block));
block * cend=(struct block *)malloc(sizeof(struct block));
block * newf=(struct block *)malloc(sizeof(struct block));
block * newu=(struct block *)malloc(sizeof(struct block));
pend=id[tempId]->next;
int flag=0,isFirst=0;
while(pend!=NULL){
if(pend->loc==0){
if(isFirst==0){
id[tempId]->next=pend->next;
}else {
pend->prior->next=pend->next;
}
int size=(pend->size)/2;
int start=pend->start;
newu->size=size;
newu->start=start;
newf->start=start+size;
newu->loc=0;
newf->size=size;
newf->loc=0;
newf->prior=newu;
newu->next=newf;
newf->next=NULL;
tempId--;
cend=id[tempId];
while(cend->next!=NULL){
cend=cend->next;
}
cend->next=newu;
newu->prior=cend;
flag=1;
return 1;
}else {
pend=pend->next;
isFirst++;
}
}
if(flag==0){
tempId=tempId+1;
if(tempId<=9){
free(pend);free(cend);free(newu);free(newf);
split(tempId);
}else {
return -1;
}
}
}
int merge(int tempId,block *first){
block * merger=(struct block *)malloc(sizeof(struct block));
block * second=NULL;
second=id[tempId]->next;
int nextStart=first->start+first->size;
int preStart=first->start-first->size;
int flag=0,isFirst=0;
while(second!=NULL){
if((second->start==nextStart || second->start==preStart) && second->loc==0){
merger->size=(first->size)+(second->size);
merger->loc=0;
merger->start=(first->start)<(second->start)?(first->start):(second->start);
if(first->next!=NULL){
first->next->prior=first->prior;
}
if((first->prior->prior)==first->prior){
id[tempId]->next=first->next;
}else {
first->prior->next=first->next;
}
if(second->next!=NULL){
second->next->prior=second->prior;
}
if(isFirst==0){
id[tempId]->next=second->next;
}else{
second->prior->next=second->next;
}
tempId++;
merger->next=id[tempId]->next;
merger->prior=id[tempId];
if(id[tempId]->next!=NULL) id[tempId]->next->prior=merger;
id[tempId]->next=merger;
if(tempId<9){
merge(tempId,merger);
}else {
return 0;
}
return 1;
}else {
second=second->next;
isFirst++;
}
}
return 1;
}
int freeb(int size){
block * first=(struct block *)malloc(sizeof(struct block));
int tempId=root(2,size);
first=id[tempId]->next;
int flag=0;
while(first!=NULL){
if(first->loc==1){
first->loc=0;
flag=1;
break;
}else {
first=first->next;
}
}
if(flag==1){
merge(tempId,first);
printmem();
}else {
printf("需要释放的内存块不存在!\n");
}
return 1;
}
int requestb(int size){
block * temp=(struct block *)malloc(sizeof(struct block));
int tempId = root(2,size);
int flag=0;
temp=id[tempId]->next;
while(temp!=NULL){
if(temp->loc==0 && temp->size==size){
temp->loc=1;
flag=1;
printf("分配成功!\n");
printmem();
return 1;
}else{
temp=temp->next;
}
}
if(flag==0){
tempId++;
if(tempId<=9){
int rs=split(tempId);
if(rs==-1) {
printf("没有合适的空间可分配!\n");
return -1;
}else {
requestb(size);
}
}else {
printf("没有合适的空间可分配!\n");
return -1;
}
}
free(temp);
}
int main(){
init();
int flag=1;
int size;
char order;
do{
printf("请输入命令:(以空格相隔,示例:r 8)\n");
scanf("%c %d",&order,&size);
if(order=='r'){
requestb(size);
}else if(order=='f'){
freeb(size);
}else{
printf("error!");
}
printf("是否继续?(1继续，0退出):");
scanf("%d",&flag);
getchar();
}while(flag==1);
}
结果图：
2. 页故障率反馈模型
源程序;
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAX_WORKSET 10
#define WINDOW_SIZE 20
int mempage=10;
int procArray[WINDOW_SIZE];
int win[MAX_WORKSET][2];
double maxRate=0.8,minRate=0.2;
double curRate;
int cur_workset=3;
int conflictCount=0;
void print(){
curRate=(double)conflictCount/(double)WINDOW_SIZE;
printf("缺页故障率：%g,故障率上限/下限：%g/%g\n",curRate,maxRate,minRate);
}
void changeArray(){
int i;
for(i=0;i<WINDOW_SIZE;i++){
procArray[i]=rand()%mempage;
}
printf("进程调用页面序列：");
for(i=0;i<WINDOW_SIZE;i++){
printf("%d|",procArray[i]);
}
printf("\n");
}
void init(){
int i,j;
//changeArray();
for(i=0;i<MAX_WORKSET;i++){
win[i][0]=-1;
win[i][1]=cur_workset;
}
}
void changePage(int number){
int i,flag=0;
for(i=1;i<cur_workset;i++){
if(win[flag][1] <= win[i][1]){
flag=i;
}
}
win[flag][0]=procArray[number];
win[flag][1]=1;
conflictCount++;
for(i=0;i<cur_workset;i++){
if(i!=flag && win[i][1]!=-1){
win[i][1]++;
}
}
}
void step(int number){
int i,hit=0;
for(i=0;i<cur_workset;i++){
if(procArray[number] == win[i][0]){
//number++;
hit=1;
break;
}
}
if(hit==0){
changePage(number);
}
}
void run(){
int i;
conflictCount=0;
changeArray();
for(i=0;i<WINDOW_SIZE;i++){
step(i);
}
printf("冲突次数：%d,",conflictCount);
}
void feedback(){
curRate=(double)conflictCount/(double)WINDOW_SIZE;
if(curRate>maxRate){
cur_workset++;
}else if(curRate<minRate){
cur_workset--;
}
}
int main(){
init();
char quit;
do{
run();
print();
feedback();
printf("输入任意字符继续，q退出\n");
scanf("%c",&quit);
getchar();
}while(quit != 'q');
}
4、 结果分析与实验体会
存储管理是操作系统中最重要的组成部分之一。在早期计算时代，由于人们所需要的内存数目远远大于物理内存，人们设计出了各种各样的策略来解决此问题，其中最成功的是虚拟内存技术。它使得系统中为有限物理内存竞争的进程所需内存空间得到满足。我们以Buddy Heap算法为例，实现模拟Linux系统中连续内存分配。BH算法具有速度快的明显特点，同时解决了外碎片问题，但带来内碎片，这是由于实际请求一般不能恰好与2i相对应，此时必须向上取整。对于更大块的请求内碎片的浪费更严重。为此Linux将剩余的内碎片按2j整数次幂切片并由二次分配器进行单独管理。此外当进程物理空间不要求连续时，内存分配由第三分配器完成。此外，这个实验还需要很好的理解FIFO算法，这是最简单的页面淘汰算法，在实现时，对应每一个页面需要有一个调入时间，该时间可设在内存中并用软件记录，不过最好设在寄存器中并由硬件记录。当内存空间紧张时，调入时间最早的页面将被淘汰。FIFO算法易于理解和编程，但它的效率不高。被置换的页面可能存有一个初始化程序段，很早以前曾用到，以后不会再用到；但也可能存有一组经常访问的全局变量，初始化时被调入内存，在整个程序运行过程中都将会用到。这次实验难点在理论方面，在理解了之后操作比较顺利。
第二篇：操作系统实验报告-存储管理实验
存储管理实验
一．实验目的及要求：
通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。
通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
二 . 实验环境：
操作系统：Windows XP
编译环境：Visual C++ 6.0
三．算法描述
由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。
作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。
每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。
各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。
每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。
四. 实验步骤：
核心源码：
void acceptment2(RECT *head,RECT *back1)
{
RECT *before,*after;
int insert ;
insert=0;
before=head;
after=head->next;
if(head->next==NULL) /*如果可利用区表为空*/
{
head->size=back1->size;
head->next=back1;
maxblocknum++;
back1->next=NULL;
}
else
{
while(after!=NULL) /*与上一块合并*/
if(back1->address==after->size+after->address)
{
before->next=after->next;
back->size=after->size+back1->size;
free(after);
after=NULL;
}
else
{
after=after->next;
before=before->next;
}
before=head;
after=head->next;
while(after!=NULL)
if(after->address==back1->size+back1->address) /*与下一块合并*/
{
back1->size=back1->size+after->size;
before->next=after->next;
free(after);
after=NULL;
}
else
{
before=before->next;
after=after->next;
}
before=head;/*将回收结点插入到合适的位置*/
after=head->next;
do{
if(after==NULL||(after->size>back1->size))
{
before->next=back1;
back1->next=after;
insert=1;
}
else
{
before=before->next;
after=after->next;
}
}while(!insert);
if(head->size<back1->size) /*修改最大块值和最大块数*/
{
head->size=back1->size;
maxblocknum++;
}
else
if(head->size==back1->size)
maxblocknum++;
}
}
/*分配函数*/
RECT *assignment(RECT *head,int application)
{
RECT *after,*before,*assign;
assign=(RECT*)malloc(sizeof(RECT)); /*分配申请空间*/
assign->size=application;
assign->next=NULL;
if(application>head->size||application<=0)
assign->address=-1; /*申请无效*/
else
{
before=head;
after=head->next;
while(after->size<application)/*查找适应的结点*/
{
before=before->next;
after=after->next;
}
if(after->size==application) /*结点大小等于申请大小则完全分配*/
{
if(after->size==head->size)
maxblocknum--;
before->next=after->next;
assign->address=after->address;
free(after);
}
else
{
if(after->size==head->size) maxblocknum--;
after->size=after->size-application; /*大于申请空间则截取相应大小分配*/
assign->address=after->address+after->size;
if(tolower(way)=='b')/*如果是最佳适应，将截取后剩余结点重新回收到合适位置*/
{
before->next=after->next;
back=after;
acceptment2(head,back);
}
}
if(maxblocknum==0) /*修改最大数和头结点值*/
{
before=head;
head->size=0;
maxblocknum=1;
while(before!=NULL)
{
if(before->size>head->size)
{
head->size=before->size;
maxblocknum=1;
}
else
if(before->size==head->size)
maxblocknum++;
before=before->next;
}
}
}
assign1=assign;
return assign1; /*返回分配给用户的地址*/
}
void acceptment1(RECT *head,RECT *back1)/*首先适应*/
{
RECT *before,*after;
int insert;
before=head;
after=head->next;
insert=0;
while(!insert) /*将回收区插入空闲区表*/
{
if((after==NULL)||
((back1->address<=after->address)&&
(back1->address>=before->address)))
{
before->next=back1;
back1->next=after;
insert=1;
}
else
{
before=before->next;
after=after->next;
}
}
if(back1->address==before->address+before->size)/*与上一块合并*/
{
before->size=before->size+back1->size;
before->next=back1->next;
free(back1);
back1=before;
}
if(after!=NULL&&(after->address==back1->address+back1->size))
{ /*与下一块合并*/
back1->size=back1->size+after->size;
back1->next=after->next;
free(after);
}
if(head->size<back1->size) /*修改最大块值和最大块个数*/
{
head->size=back1->size;
maxblocknum=1;
}
else
if(head->size==back1->size)
maxblocknum++;
}
/*检查回收块的合法性，back1为要回收的结点地址*/
int backcheck(RECT *head,RECT *back1)
{
RECT *before,*after;
int check=1;
if(back1->address<0||back1->size<0)
check=0;/*地址和大小不能为负*/
before=head->next;
while((before!=NULL)&&check)/*地址不能和空闲区表中结点出现重叠*/
if(((back1->address<before->address)
&&(back1->address+back1->size>before->address))
||((back1->address>=before->address)
&&(back1->address<before->address+before->size)))
check=0;
else
before=before->next;
if(check==0)
printf("输入回收空间地址错误或输入的回收空间是空闲状态。!!\n");
return check; /*返回检查结果*/
}
3.、实验截图：
- 《操作系统》存储管理实验报告
-
操作系统存储管理实验报告
北京邮电大学操作系统实验实验报告实验日期20xx1220实验名称存储管理一实验目的2二实验内容2三实验分析2对于伙伴算法2对于虚拟…
- 操作系统 内存管理实验报告
-
北邮大三上-操作系统-存储管理实验报告
操作系统实验三存储管理实验班级20xx211311学号姓名schnee目录1实验目的22实验内容21通过随机数产生一个指令序列共3…
-
实验四 操作系统存储管理实验报告
实验四操作系统存储管理实验报告一实验目的存储管理的主要功能之一是合理地分配空间请求页式管理是一种常用的虚拟存储管理技术本实验的目的…
- 操作系统实验报告-Linux基本操作命令
-
Linux操作系统实习报告
沈阳航空航天大学Linux系统操作实习报告院系计算机学院专业计算机科学与技术班级84010103学号20xx040101061姓名…
-
linux操作系统指令实验报告
实验一Linux的基本操作和常用命令的使用一实验目的1学会安装Linux操作系统2掌握Linux系统的一些基本操作3掌握常用Lin…
-
操作系统实验报告-Linux操作、使用、编程)
实验报告20xx20xx学年第二学期课程名称实验名称实验时间指导单位操作系统ALinux操作使用编程20xx年5月6日计算机学院计…
-
Linux操作系统实习报告
Linux系统操作实习报告院系班级学号姓名实习内容Linux的系统操作实习的第一天尚观科技长期开发高端UNIXLinux嵌入式开发…
-
操作系统实验报告
淮阴工学院实验报告20xx20xx学年第1学期学院计算机工程学院课程名称操作系统班级软件1101学号1101305114姓名王祥指…