文档章节

模拟linux内存管理代码

xueyi28
 xueyi28
发布于 2016/05/22 15:57
字数 2019
阅读 16
收藏 0

这个代码模拟实现了linux内存管理的三个算法ff、wf、bf。这三个算法都是连续分配的方式,这种方式的缺点就是内存碎片很难被再次利用。

 
#include <stdio.h>
#include <stdlib.h>
#define PROCESS_NAME_LEN 32   /*进程名长度*/
#define MIN_SLICE    10             /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024     /*内存大小*/
#define DEFAULT_MEM_START 0       /*起始位置*/
/* 内存分配算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm=MA_FF;           /*当前分配算法*/
static int pid=0;  /*初始pid*/
int flag = 0;/*设置内存大小标志*/
/*描述每一个空闲块的数据结构*/
struct free_block_type{
    int size;
    int start_addr;
    struct free_block_type *next;
};

/*指向内存中空闲块链表的首指针*/
struct free_block_type *free_block;
/*每个进程分配到的内存块的描述*/
struct allocated_block{
    int pid;
    int size;//大小
    int start_addr;//起始地址
   char process_name[PROCESS_NAME_LEN];//进程名字
    struct allocated_block *next;
    };
/*进程分配内存块链表的首指针*/
struct allocated_block *allocated_block_head = NULL;

void king(struct free_block_type *h)//为有参的函数
{
struct free_block_type *p;
//对相邻区的处理,和对size==0的处理
if(h->next!=NULL)//感觉这里不对
{
 if((h->start_addr+h->size)==h->next->start_addr)
 {
 p=h->next;
 h->size=h->size+p->size;
 h->next=p->next;
 free(p);
 king(h);
 }
else
if(h->next!=NULL)
king(h->next);
}
}


/*连表的销毁*/
void freenode(struct free_block_type *h)
{
 struct free_block_type *p;
 while(h!=NULL)
 {p=h;
 h=h->next;
  free(p);
 }
}
void freenode1(struct allocated_block *h)
{
 struct allocated_block *p;
 while(h!=NULL)
 {p=h;
 h=h->next;
  free(p);
 }
}


/*初始化空闲块,默认为一块,可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size){
    struct free_block_type *fb;

    fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
    if(fb==NULL){
        printf("No mem/n");
        return NULL;
        }
    fb->size = mem_size;
    fb->start_addr = DEFAULT_MEM_START;
    fb->next = NULL;
    return fb;
}

/*显示菜单*/
void display_menu(){
    printf("/n");
    printf("1 - Set memory size (default=%d)/n", DEFAULT_MEM_SIZE);
    printf("2 - Select memory allocation algorithm/n");
    printf("3 - New process /n");
    printf("4 - Terminate a process /n");
    printf("5 - Display memory usage /n");
    printf("0 - Exit/n");
}

/*设置内存的大小*/
int set_mem_size(){
    int size;
    if(flag!=0){  //防止重复设置
        printf("Cannot set memory size again/n");
        return 0;
        }
    printf("Total memory size =");
    scanf("%d", &size);
    if(size>0) {
        mem_size = size;
        free_block->size = mem_size;
        }
    flag=1;  return 1;
    }


/*按FF算法重新整理内存空闲块链表*/
void rearrange_FF()//按照地址递增顺序
{
struct free_block_type *head,*p,*q,*s,*m,*h;
h=free_block;
m=free_block;
// h=h->next;没有头节点这里为了处理方便,暂且申请头结点
head=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 head->next=NULL;
 s=head;//保存头结点地址
 p=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 p->size=h->size;
 p->start_addr=h->start_addr;
 s->next=p;
p->next=NULL;
 h=h->next;

 while(h!=NULL)
 {
  q=(struct free_block_type *)malloc(sizeof(struct free_block_type));
  q->size=h->size;
  q->start_addr=h->start_addr;
  h=h->next;//记录下一个节点
  head=s;
  p=head->next;
  while(head!=NULL)
  {
   if(head->next==NULL)
   {
    head->next=q;
 q->next=NULL;
    break;
   }
   else if(q->start_addr<p->start_addr)//这里可以修改排序顺序
   {
 
    head->next=q;
 q->next=p;
 
    break;
  }

   else
   {head=head->next;
   p=head->next;
   }
  }
 }
 freenode(m);
 m=s;
 s=s->next;
 free(m);
 free_block=s;
 
}
/*按BF算法重新整理内存空闲块链表*/
void rearrange_BF()//按照容量从小到大
{
    struct free_block_type *head,*p,*q,*s,*m,*h;
 h=free_block;
m=free_block;
// h=h->next;没有头节点这里为了处理方便,暂且申请头结点
head=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 head->next=NULL;
 s=head;//保存头结点地址
 p=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 p->size=h->size;
 p->start_addr=h->start_addr;
 s->next=p;
p->next=NULL;
 h=h->next;

 while(h!=NULL)
 {
  q=(struct free_block_type *)malloc(sizeof(struct free_block_type));
  q->size=h->size;
  q->start_addr=h->start_addr;
  h=h->next;//记录下一个节点
  head=s;
  p=head->next;
  while(head!=NULL)
  {
   if(head->next==NULL)
   {
    head->next=q;
 q->next=NULL;
    break;
   }
   else if(q->size<p->size)//这里可以修改排序顺序
   {
 
    head->next=q;
 q->next=p;
 
    break;
  }

   else
   {head=head->next;
   p=head->next;
   }
  }
 }
 freenode(m);
 m=s;
 s=s->next;
 free(m);
 free_block=s;
}
/*按WF算法重新整理内存空闲块链表*/
void rearrange_WF()//按照容量从大到小
{
    struct free_block_type *head,*p,*q,*s,*m,*h;
 h=free_block;
m=free_block;
// h=h->next;没有头节点这里为了处理方便,暂且申请头结点
head=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 head->next=NULL;
 s=head;//保存头结点地址
 p=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 p->size=h->size;
 p->start_addr=h->start_addr;
 s->next=p;
p->next=NULL;
 h=h->next;

 while(h!=NULL)
 {
  q=(struct free_block_type *)malloc(sizeof(struct free_block_type));
  q->size=h->size;
  q->start_addr=h->start_addr;
  h=h->next;//记录下一个节点
  head=s;
  p=head->next;
  while(head!=NULL)
  {
   if(head->next==NULL)
   {
    head->next=q;
 q->next=NULL;
    break;
   }
   else if(q->size>p->size)//这里可以修改排序顺序
   {
 
    head->next=q;
 q->next=p;
 
    break;
  }

   else
   {head=head->next;
   p=head->next;
   }
  }
 }
 freenode(m);
 m=s;
 s=s->next;
 free(m);
 free_block=s;
}


/*按指定的算法整理内存空闲块链表*/
void rearrange(int algorithm){
    switch(algorithm){
        case MA_FF:  rearrange_FF(); break;
        case MA_BF:  rearrange_BF(); break;
        case MA_WF: rearrange_WF(); break;
        }
}

/* 设置当前的分配算法 */
void set_algorithm(){
    int algorithm;
    printf("/t1 - First Fit/n");
    printf("/t2 - Best Fit /n");
    printf("/t3 - Worst Fit /n");
    scanf("%d", &algorithm);
    if(algorithm>=1 && algorithm <=3)
              ma_algorithm=algorithm;
    //按指定算法重新排列空闲区链表
    rearrange(ma_algorithm);
}
/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{

    struct free_block_type  *h;
    int request_size=ab->size;
 
 rearrange(ma_algorithm);//这里虽然能够排序,但是地址发生了变化
  h=free_block;
while(h!=NULL)
{
 if(h->size>=request_size)
  break;
 h=h->next;
}
if(h==NULL)
{
 printf("不符合分配条件");
 return -1;
}
else
{
 printf("符合分配条件");
 if(h->size-request_size<MIN_SLICE)
         h->size=0;//注意这里只是修改了链表中值的大小,链表的本体还在
 else
  h->size=h->size-request_size;
   ab->start_addr=h->start_addr;
   h->start_addr=ab->start_addr+ab->size;
 return 1;
}

}

struct allocated_block *find_process(int p)
{
 struct allocated_block *h;
 h=allocated_block_head;
while(h!=NULL)
{
 if(h->pid==p)
  break;
 else
  h=h->next;
}
return h;
}

/*删除进程,归还分配的存储空间,并删除描述该进程内存分配的节点*/
void kill_process(){
    struct allocated_block *ab;
    int p;//这里的pid和全局变量的pid怎么说
    printf("Kill Process, pid=");
    scanf("%d", &p);
    ab=find_process(p);//注意这个函数,可能是遗漏
    if(ab!=NULL){
        free_mem(ab); /*释放ab所表示的分配区*/
        dispose(ab);  /*释放ab数据结构节点*/
        }
}
/*将ab所表示的已分配区归还,并进行可能的合并*/
int free_mem(struct allocated_block *ab){
    int algorithm = ma_algorithm;//算法
    struct free_block_type *h,*fbt;
 h=free_block;
  fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
    fbt->size=ab->size;
 fbt->start_addr=ab->start_addr;

    // 进行可能的合并,基本策略如下
    // 1. 将新释放的结点插入到空闲分区队列末尾
    // 2. 对空闲链表按照地址有序排列
    // 3. 检查并合并相邻的空闲分区
    // 4. 将空闲链表重新按照当前算法排序
   // 请自行补充……
while(h->next!=NULL)
h=h->next;
h->next=fbt;
fbt->next=NULL;
rearrange_FF();//2
king(free_block);//3
rearrange(ma_algorithm);//4
 return 1;
}
/*创建新的进程,主要是获取内存的申请数量*/
int new_process(){
    struct allocated_block *ab;
    int size;
    int ret;
    ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
    if(!ab) exit(-5);
    ab->next = NULL;
    pid++;
    sprintf(ab->process_name, "PROCESS-%02d", pid);
    ab->pid = pid;
    printf("Memory for %s:", ab->process_name);
    scanf("%d", &size);
    if(size>0) ab->size=size;
    ret = allocate_mem(ab);  /* 从空闲区分配内存,ret==1表示分配ok*/
  /*如果此时allocated_block_head尚未赋值,则赋值*/
    if((ret==1) &&(allocated_block_head == NULL)){
        allocated_block_head=ab;
        return 1;        }
    /*分配成功,将该已分配块的描述插入已分配链表*/
    else if (ret==1) {
        ab->next=allocated_block_head;
        allocated_block_head=ab;
        return 2;        }
    else if(ret==-1){ /*分配不成功*/
        printf("Allocation fail/n");
        free(ab);
        return -1;
     }
    return 3;
    }


/*释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab){
    struct allocated_block *pre, *ab;
   if(free_ab == allocated_block_head) { /*如果要释放第一个节点*/
     allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
        }
    pre = allocated_block_head;
    ab = allocated_block_head->next;
    while(ab!=free_ab){ pre = ab;  ab = ab->next; }
    pre->next = ab->next;
    free(ab);
    return 2;
   }

/* 显示当前内存的使用情况,包括空闲区的情况和已经分配的情况 */
display_mem_usage(){
    struct free_block_type *fbt=free_block;
    struct allocated_block *ab=allocated_block_head;
    if(fbt==NULL) return(-1);
    printf("----------------------------------------------------------/n");

    /* 显示空闲区 */
    printf("Free Memory:/n");
    printf("%20s %20s/n", "      start_addr", "       size");
    while(fbt!=NULL){
  if(fbt->size==0)
  {
   fbt=fbt->next;
   continue;
  }
        printf("%20d %20d/n", fbt->start_addr, fbt->size);
        fbt=fbt->next;
        }
 /* 显示已分配区 */
    printf("/nUsed Memory:/n");
    printf("%10s %20s %10s %10s/n", "PID", "ProcessName", "start_addr", " size");
    while(ab!=NULL){
        printf("%10d %20s %10d %10d/n", ab->pid, ab->process_name, ab->start_addr, ab->size);
        ab=ab->next;
        }
    printf("----------------------------------------------------------/n");
    return 0;
    }

int main(){
    char choice;
     pid=0;
    free_block = init_free_block(mem_size); //初始化空闲区
    while(1)
 {
    display_menu();    //显示菜单
    fflush(stdin);//这里的这个函数,linux下可以用其他的代替
    choice=getchar();    //获取用户输入
    switch(choice){
        case '1': set_mem_size(); break;     //设置内存大小
        case '2': set_algorithm();flag=1; break;//设置算法
        case '3': new_process(); flag=1; break;//创建新进程
        case '4': kill_process(); flag=1;   break;//删除进程
        case '5': display_mem_usage();    flag=1; break;    //显示内存使用
        case '0': freenode(free_block);freenode1(allocated_block_head); exit(0);    //释放链表并退出
        default: break;      }  
 }
 return 0;
}

 

本文转载自:http://blog.csdn.net/kangqi7000/article/details/6002002

共有 人打赏支持
xueyi28
粉丝 7
博文 93
码字总数 33978
作品 0
南宁
Hypervisor, KVM, QEMU总结

Hypervisor 概念 作用 种类 特点 多Hypervisor QEMU和KVM KVM QEMU QEMU-KVM libvirt Hypervisor 1.概念 Hypervisor——一种运行在基础物理服务器和操作系统之间的中间软件层,可允许多个操作...

simpower
08/08
0
0
qemu,kvm,qemu-kvm,xen,libvir 区别

KVM:(Kernel-based Virtual Machine)基于内核的虚拟机 KVM是集成到Linux内核的Hypervisor,是X86架构且硬件支持虚拟化技术(Intel VT或AMD-V)的Linux的全虚拟化解决方案。它是Linux的一个很...

独钓渔
2015/05/04
0
0
openstack系列文章(一)

学习openstack的系列文章 虚拟化 KVM CPU 虚拟化 KVM 内存虚拟化 全虚拟化 I/O 设备 半虚拟化 I/O 设备 I/O PCI PCIe 设备直接分配 SR-IOV 在 kVM-QEMU 中,虚拟机使用的设备大致可以分为三类...

行者阿难
09/26
0
0
《云计算架构技术与实践》读书笔记(四):XEN/KVM虚拟化引擎介绍

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/a724888/article/details/75392862 4.1  XEN/KVM虚拟化引擎 4.1.1  虚拟化架构分类 计算虚拟化技术的实现形...

你的猫大哥
2017/07/19
0
0
openstack, kvm, qemu-kvm以及libvirt之间的关系

虚拟化类型 全虚拟化(Full Virtualization) 全虚拟化也成为原始虚拟化技术,该模型使用虚拟机协调guest操作系统和原始硬件,VMM在guest操作系统和裸硬件之间用于工作协调,一些受保护指令必...

神ge
06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mixin混入

①新建mixin.js文件 const mixin = { methods: { /** * 分页公共方法 */ handleSizeChange(val) { this.pageData.size = val; this.query(); }, hand......

不负好时光
昨天
0
0
ERC1155实践|区块链游戏的平行宇宙和为此而生的Enjin钱包

1 摘要 恩金(Enjin)花了大半年的时间一直在完善ERC-1155这个通证协议,毫不夸张地说,该标准是现有以太坊上最适用于游戏资产的通证标准,将主流游戏中道具涉及到的一切操作经过高度抽象之后...

HiBlock
昨天
1
0
Oracle发布开源的轻量级 Java 微服务框架 Helidon

近日,Oracle推出了一个新的开源框架Helidon,该项目是一个用于创建基于微服务的应用程序的Java库集合。和Payara Micro、Thorntail(之前的WildFly Swarm)、OpenLiberty、TomEE等项目一样,...

关注公众号_搜云库_每天更新
昨天
1
0
启动线程以及安全终止线程

启动 使用start()方法可以启动线程。 start()方法的含义是告知线程规划器线程已初始化完毕,可以分给这个线程时间片了(执行run()方法)。 安全终止线程 示例代码 import java.util.concurr...

karma123
昨天
1
0
Python+OpenCV 图像风格迁移(模仿名画)

现在很多人都喜欢拍照(自拍)。有限的滤镜和装饰玩多了也会腻,所以就有 APP 提供了模仿名画风格的功能,比如 prisma、versa 等,可以把你的照片变成 梵高、毕加索、蒙克 等大师的风格。 这...

crossin
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部