操作系统—实现可变式分区分配算法

文章目录

  • 实现可变式分区分配算法
  • 1.实验环境
  • 2.如何在xv6中实现分区分配算法?
    • (1).xv6的内存管理机制
    • (2).实现思路
  • 3.最佳适应算法
    • (1).基本思路
    • (2).步骤
    • (3).测试&Debug
  • 总结
  • 参考资料

实现可变式分区分配算法

1.实验环境

  因为这一次的实验仍然是在xv6中进行,因此本次实验依旧直接采用Lab中使用的xv6内核实验环境:
在这里插入图片描述

2.如何在xv6中实现分区分配算法?

(1).xv6的内存管理机制

  xv6中通过sbrk机制完成内存的分配,可以在sysproc.c中找到sbrk系统调用的定义:

uint64 sys_sbrk(void) {int addr;int n;if (argint(0, &n) < 0) return -1;addr = myproc()->sz;if (growproc(n) < 0) return -1;return addr;
}

  代码比较简单,它只接受一个整数n,之后会调用proc.c中定义的growproc函数:

// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int growproc(int n) {uint sz;struct proc *p = myproc();sz = p->sz;if (n > 0) {if ((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {return -1;}} else if (n < 0) {sz = uvmdealloc(p->pagetable, sz, sz + n);}p->sz = sz;return 0;
}

  这串代码的阅读难度就相对要大一点,首先是从当前进程中读取出内存栈的大小,参数n的正负决定了内存是扩张还是收缩,对于扩张的情况,growproc会尝试调用uvmalloc完成扩张n字节的操作,而uvmalloc的函数定义可以在vm.c当中找到(uvdealloc也可以找到):

// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz) {char *mem;uint64 a;if (newsz < oldsz) return oldsz;oldsz = PGROUNDUP(oldsz);for (a = oldsz; a < newsz; a += PGSIZE) {mem = kalloc();if (mem == 0) {uvmdealloc(pagetable, a, oldsz);return 0;}memset(mem, 0, PGSIZE);if (mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W | PTE_X | PTE_R | PTE_U) != 0) {kfree(mem);uvmdealloc(pagetable, a, oldsz);return 0;}}return newsz;
}
// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
uint64 uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz) {if (newsz >= oldsz) return oldsz;if (PGROUNDUP(newsz) < PGROUNDUP(oldsz)) {int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);}return newsz;
}

  这里首先研究uvmalloc函数,它首先确定新的内存大小要大于等于之前的内存大小,之后通过riscv.h当中的宏函数PGROUNDUP将oldsz向上转换成页表大小整倍数的内存大小:

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))

  这个函数本身并不难理解,例如现在的PGSIZE被定为4096,则当sz为4094字节的时候,PGROUNDUP的结果就是:4096,而当sz为4097字节的时候结果是8192,所以它的行为的确是这样:先算出需要页表的数量,然后向上取整得到真正的字节数。
  这样做的目的也是显然的:因为内存分配是依靠kalloc每次分配一个页表完成的,因此如果不转换成对应的大小,后续操作会不太方便
  在这之后,uvmalloc的操作就很明确了:利用循环的方式,每一次都利用kalloc函数分配一页(4096字节)内存,每次都会尝试进行一次页表到物理内存的映射,如果成功,则继续下一轮循环继续分配,直到分配到最后达到了新的内存大小为止
  uvdealloc的操作更加简单,对于确实需要减少分配的情况,在计算出需要减少分配的页表的数量之后,使用uvunmap取消页表到物理内存的映射关系即可

  因此growproc的行为到这里也就明确了:利用uvmalloc和uvdealloc两个函数完成对于当前进程内存(本质是页表)的收缩和扩张,从而完成用户内存的变化。

  之后就可以回到sys_sbrk这个系统调用了,它的思路相当简单:利用growproc函数完成用户进程内存的扩张

(2).实现思路

  前面的分配过程基本上都与希望实现的几个算法无关,不过比较有必要注意的是sbrk,实际上xv6的动态内存分配应该是基于sbrk实现的,malloc的代码如下:

void *malloc(uint nbytes) {Header *p, *prevp;uint nunits;nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;if ((prevp = freep) == 0) {base.s.ptr = freep = prevp = &base;base.s.size = 0;}for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) {if (p->s.size >= nunits) {if (p->s.size == nunits)prevp->s.ptr = p->s.ptr;else {p->s.size -= nunits;p += p->s.size;p->s.size = nunits;}freep = prevp;return (void *)(p + 1);}if (p == freep)if ((p = morecore(nunits)) == 0) return 0;}
}

  它会以一个链表查找的方式一个个遍历查找,直到找到一个和需要分配的空间大小匹配的块,然后完成分配等等工作,在没有办法找到可供分配的块的情况下,malloc函数会调用morecore函数进行空间的扩张:

static Header *morecore(uint nu) {char *p;Header *hp;if (nu < 4096) nu = 4096;p = sbrk(nu * sizeof(Header));if (p == (char *)-1) return 0;hp = (Header *)p;hp->s.size = nu;free((void *)(hp + 1));return freep;
}

  morecore函数做的事情是:每一次利用sbrk函数将用户内存(堆空间)至少扩大4096个Header大小,之后再利用free函数将这个分配的新空间加入到当前进程的空闲链表当中

  因此基于这个思考,我们或许只需要在umalloc.c当中实现一个基于最佳适配算法的malloc函数即可。

3.最佳适应算法

(1).基本思路

  最佳适应算法比较简单,它的基本思路就是从分区表中依次遍历,直到找到一个与需要分配的空间为最佳适配的大小。

(2).步骤

  在umalloc.c当中增加一个函数myalloc:

void* myalloc(uint nbytes) {Header *p, *prevp, *best, *prevb;uint nunits;nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;if ((prevp = freep) == 0) {base.s.ptr = freep = prevp = &base;base.s.size = 0;}best = 0;prevb = 0;for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) {if (p->s.size >= nunits) {if (p->s.size == nunits) {prevb = prevp;best = p;break;}else {if (p->s.size < best->s.size) {prevb = prevp;best = p;}}if (p == freep)if ((p = morecore(nunits)) == 0) return 0;}if (best->s.size != nunits) {best->s.size -= nunits;best += p->s.size;p->s.size = nunits;}freep = prevb;return (void *)(best + 1);
}

  它的实现与malloc几乎完全一致,只是在搜索可用空间块的时候每次多维护一个best和prevb指针,用于找到能够与需要分配大小(对齐后的大小)最接近的块
  如果myalloc找到了与需要空间正好相等的大小,则直接中止循环,否则会继续尝试寻找更优的一块内存空间,在循环结束之后,如果待分配的空间大于需要的大小,则会进行一次切割,从最佳分配的块中切割出相等大小的内存,之后再将块的头部信息记录到freep当中,然后返回分配后空间的地址。

(3).测试&Debug

  首先在user.h中添加刚才增加的myalloc函数的原型:
在这里插入图片描述
  接下来可以编写一个用户态程序myalloctest来进行测试:

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"int main(int argc, char *argv[]) {if (argc != 2) {printf("Assertion: must have one argument\n");exit(1);}int arg = atoi(argv[1]);if (arg <= 0) {printf("Assertion: size cannot be less equal than 0\n");exit(2);}uint sz = (uint)arg;printf("==myalloctest==\n");char* addr = (char*)myalloc(sz);memset(addr, 'a', sz);addr[sz-1] = 0;printf("%s\n", addr);free(addr);exit(0);
}

  在Makefile文件中添加用户态程序:

  然后尝试运行,但是失败了:
在这里插入图片描述
  这种情况下连字符串都不会打印出来,但是当测试的字节数特别大的时候,这个程序能成功打印出应该是和分配字节数相匹配个数的a,但是最终程序会卡住,所以我或许要从usertrap的这个报错入手解决。

  这个报错和上次的自定义调度算法很像,都是在usertrap处理用户trap的时候发生了无法识别的外部中断或软中断,而实际上唯一能触发usertrap的就只有myalloc函数,因为myalloc其中可能会调用morecore,而之后会调用sbrk系统调用。

  经过一些printf测试之后发现,p和best在没有任何额外赋值的情况下总是一样的,此时大概可以确定:myalloc在持续使用morecore尝试分配更多内存,由此才导致了异常

  因此之后我尝试将代码修改成了下面这样:

void* myalloc(uint nbytes) {Header *p, *prevp, *best, *prevb;uint nunits;nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;if ((prevp = freep) == 0) {base.s.ptr = freep = prevp = &base;base.s.size = 0;}best = 0;prevb = 0;for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) {if (p->s.size >= nunits) {if (best == 0) {prevb = prevp;best = p;continue;}if (p->s.size == nunits) {prevb = prevp;best = p;break;}else {if (p->s.size < best->s.size) {ßprevb = prevp;best = p;}}}if (best == 0 && p == freep) {if ((p = morecore(nunits)) == 0) return 0;}else if (p == freep) break;}if (best->s.size != nunits) {best->s.size -= nunits;best += p->s.size;p->s.size = nunits;}freep = prevb;return (void *)(best + 1);
}

  与之对应的,将myalloctest函数修改为下面的样子:

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"int main(int argc, char *argv[]) {if (argc != 2) {printf("Assertion: must have one argument\n");exit(1);}int arg = atoi(argv[1]);if (arg <= 0) {printf("Assertion: size cannot be less equal than 0\n");exit(2);}uint sz = (uint)arg;printf("==myalloctest==\n");char* addr = (char*)myalloc(sz);memset(addr, 'a', sz);addr[sz-1] = 0;printf("%s\n", addr);free(addr);exit(0);
}

  经过运行测试之后发现,打印的步骤已经能够顺利完成了,但是内存的释放部分还不正常:
在这里插入图片描述
  打印的字符数量符合一开始输入的数字,但是在之后进行free的时候就会卡住,这里可以看一下free的代码:

void free(void *ap) {Header *bp, *p;bp = (Header *)ap - 1;for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) break;if (bp + bp->s.size == p->s.ptr) {bp->s.size += p->s.ptr->s.size;bp->s.ptr = p->s.ptr->s.ptr;} elsebp->s.ptr = p->s.ptr;if (p + p->s.size == bp) {p->s.size += bp->s.size;p->s.ptr = bp->s.ptr;} elsep->s.ptr = bp;freep = p;
}

  里面的确有一个for循环,或许就是在这里被卡住了,或许是因为我采用了malloc的free函数,在这个情况下可能会导致free需要的freep指针发生紊乱,因此可以直接仿照free写出myalloc对应的myfree函数:

void myfree(void *ap) {Header *bp, *p;bp = (Header *)ap - 1;for (p = freeb; !(bp > p && bp < p->s.ptr); p = p->s.ptr)if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) break;if (bp + bp->s.size == p->s.ptr) {bp->s.size += p->s.ptr->s.size;bp->s.ptr = p->s.ptr->s.ptr;} elsebp->s.ptr = p->s.ptr;if (p + p->s.size == bp) {p->s.size += bp->s.size;p->s.ptr = bp->s.ptr;} elsep->s.ptr = bp;freeb = p;
}

  修改myalloctest.c如下:

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"int main(int argc, char *argv[]) {if (argc != 2) {printf("Assertion: must have one argument\n");printf("==myalloctest failed==\n");  exit(1);}int arg = atoi(argv[1]);if (arg <= 0) {printf("Assertion: size cannot be less equal than 0\n");printf("==myalloctest failed==\n");exit(2);}uint sz = (uint)arg;printf("==myalloctest==\n");char* addr = (char*)myalloc(sz);memset(addr, 'a', sz);addr[sz-1] = 0;printf("%s\n", addr);myfree(addr);printf("==myalloctest success==\n");exit(0);
}

  之后再运行,就正常了:
在这里插入图片描述

  但我发现我实际上忘记把myalloc的最后一步改成freeb,当我改了之后,myfree处的死循环,它又出现了:
在这里插入图片描述
  结果还是没有成功,只能说:我只实现了按照最佳适应算法进行分配内存,但是没有实现对应的free函数,内存不能正常完成释放

总结

  实现分区分配算法算是一个比较困难的工作了,因为网络上的资料其实非常少,大部分能搜得到的内容都是借助编程语言模拟实现的算法,并不是真实在内核中实现的,因此做这个作业的确是花费了比较多的功夫。

  不过好在结果是好的,虽然到最后我也没有在内核中完全成功实现这个算法(free没有实现),但是整个作业过程当中我已经基本明白了xv6内核的内存管理机制,不过这应该也是因为我对内存管理的各种机制不了解,因此在未来学习完了内存管理之后,我应该还会继续尝试修复这些问题,完成一对真实能运行的myalloc-myfree函数。

参考资料

  • [CSDN]-xv6源码解析(三)——内存管理
  • [CSDN]-系统调用与内存管理(sbrk、brk、mmap、munmap)
  • [GitHub]-Vikalloc_xv6_Operating_System
  • [geeksforgeeks]-Program for Best Fit algorithm in Memory Management
  • [geeksforgeeks]-Best-Fit Allocation in Operating System

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2960287.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Adobe AE(After Effects)2021下载地址及安装教程

Adobe After Effects是一款专业级别的视觉效果和动态图形处理软件&#xff0c;由Adobe Systems开发。它被广泛用于电影、电视节目、广告和其他多媒体项目的制作。 After Effects提供了强大的合成和特效功能&#xff0c;可以让用户创建出令人惊艳的动态图形和视觉效果。用户可以…

vue的就地更新与v-for的key属性

vue的就地更新 Vue中的就地更新到底是怎么回事&#xff0c;为什么会存在就地更新的现象&#xff1f; 注意下面的例子&#xff0c;使用v-for指令时&#xff0c;没有绑定key值&#xff0c;才有就地更新的现象&#xff0c;因为Vue默认按照就地更新的策略来更新v-for渲染的元素列表…

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《基于用户生产场景辨识的电压暂降经济损失评估》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

十大远程控制软件排名

远程控制软件在现代计算环境中扮演着至关重要的角色&#xff0c;它们使得用户能够轻松地访问和管理远程计算机或设备。随着技术的不断进步&#xff0c;市场上涌现出许多优秀的远程控制工具。以下是对当前市场上十大远程控制软件的简要排名和介绍&#xff0c;以帮助您选择最适合…

Go Plugin:动态模块的加载与问题解析_go语言加载动态库的工具(1)

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

Linux环境如何端口映射?

在网络通信中&#xff0c;端口映射是一项重要的技术&#xff0c;在Linux系统中广泛应用。它的主要作用是实现不同网络设备之间的通信&#xff0c;使得远程访问成为可能。本文将介绍Linux端口映射的基本原理和应用场景&#xff0c;并重点介绍了一种名为【天联】的组网优势。 端口…

第47期 | GPTSecurity周报

GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区&#xff0c;集成了生成预训练Transformer&#xff08;GPT&#xff09;、人工智能生成内容&#xff08;AIGC&#xff09;以及大语言模型&#xff08;LLM&#xff09;等安全领域应用的知识。在这里&#xff0c;您可以找…

操作系统—GCC与编译全流程

文章目录 GCC与编译全流程1.GCC是什么&#xff1f;2.编译全流程(1).GCC到底做了哪些事情&#xff1f;(2).预处理I.预处理会做什么II.预处理器主要包含什么&#xff1f;III.宏的一些魔法 (3).编译I.基本流程II.编译优化III.一点例子 (4).汇编(5).链接(6).说到这里&#xff0c;为…

AIGC实战——VQ-GAN(Vector Quantized Generative Adversarial Network)

AIGC实战——VQ-GAN 0. 前言1. VQ-GAN2. ViT VQ-GAN小结系列链接 0. 前言 本节中&#xff0c;我们将介绍 VQ-GAN (Vector Quantized Generative Adversarial Network) 和 ViT VQ-GAN&#xff0c;它们融合了变分自编码器 (Variational Autoencoder, VAE)、Transformer 和生成对…

免费的 ChatGPT、GPTs、AI绘画(国内版)

&#x1f525;博客主页&#xff1a;白云如幻❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ ChatGPT3.5、GPT4.0、GPTs、AI绘画相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚…

Oracle 正则,开窗,行列转换

1.开窗函数 基本上在查询结果上添加窗口列 1.1 聚合函数开窗 基本格式: ..... 函数() over([partition by 分组列,...][order by 排序列 desc|asc][定位框架]) 1&#xff0c;partition by 字段 相当于group by 字段 起到分组作用2&#xff0c;order by 字段 即根据某个字段…

客诉技术架构:构建客户满意的数字化支持系统

随着数字化时代的到来&#xff0c;客户体验已经成为企业竞争的关键因素之一。而客诉技术架构作为支持客户服务和解决问题的关键系统&#xff0c;对于企业提升客户满意度和品牌声誉具有重要意义。本文将深入探讨客诉技术架构的重要性、关键要素以及如何构建一个有效的客户支持系…

女上司问我:误删除PG百万条数据,可以闪回吗?

作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验 擅长主流数据Oracle、MySQL、PG、openGauss运维 备份恢复&#xff0c;安装迁移&#xff0c;性能优化、故障应急处理等可提供技术业务&#xff1a; 1.DB故障处理/疑难杂症远程支援 2.Mysql/PG/Oracl…

vagrant 安装虚拟机,docker, k8s

第一步&#xff1a;安装虚拟机 1、安装 vagrant 本机是 mac, 但是这一步不影响&#xff0c;找对应操作系统的安装方式就行了。 vagrant 下载地址 brew install vagrant 2、下载 VirtualBox 虚拟机 VirtualBox 下载地址 找到对应系统下载&#xff0c;安装就可以。 尽量把…

【Rust日报】2024-04-15 拯救地球,请使用Rust编程

拯救地球&#xff0c;请使用Rust编程 本文讨论了如何通过在Rust编程语言中编码&#xff0c;可以更有效地利用现有资源以帮助保护我们的星球。 通过在实际项目中将PHP应用重写为Rust&#xff0c;作者体验到了Rust不仅在维护性、开发效率和错误减少方面有优势&#xff0c;还在性能…

「51媒体」媒体邀约新闻稿件发布应该如何筛选媒体?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 在媒体邀约新闻稿件发布的过程中&#xff0c;筛选媒体是一个至关重要的环节。我们需要考虑以下因素&#xff1a; 目标受众匹配度&#xff1a;首先&#xff0c;需要明确新闻稿件的目标受众…

汉字编码实验

Logisim的简介和安装 首先要知道什么是logisim? Logisim是一种用于数字电路设计和模拟的开源工具&#xff0c;Logisim在2014年10月11日无限期暂停。因它足够简单&#xff0c;可以帮助学习逻辑电路相关的基本概念而闻名。Logisim被世界各地大学的学生在课程中使用。 Logisim的…

屏幕录制软件Bandicam

一、软件特点 1. 屏幕录制功能Bandicam可以录制各种屏幕活动&#xff0c;包括软件操作、网络教学、在线视频等。它支持高清录制&#xff0c;确保录制内容的质量较高而文件大小相对较小。 2. 游戏录制能力该软件特别适用于游戏录制&#xff0c;支持2D和3D游戏视频的录制&#x…

【AIGC】AIGC在虚拟数字人中的应用:塑造未来互动体验的革新力量

&#x1f680; &#x1f680; &#x1f680;随着科技的快速发展&#xff0c;AIGC已经成为引领未来的重要力量。其中&#xff0c;AIGC在虚拟数字人领域的应用更是引起了广泛关注。虚拟数字人作为一种先进的数字化表达形式&#xff0c;结合了3D建模、动画技术、人工智能等多种先进…

Python-VBA函数之旅-eval函数

目录 一、eval函数的常见应用场景&#xff1a; 二、eval函数安全使用注意事项&#xff1a; 三、eval函数与exec函数对比分析&#xff1a; 1、eval函数&#xff1a; 1-1、Python&#xff1a; 1-2、VBA&#xff1a; 2、相关文章&#xff1a; 个人主页&#xff1a;ht…