操作系统课程设计连续动态分区内存管理模拟实现.doc

(操作系统课程设计）连续动态分区内存 管理模拟实现 目录操作系统课程设计、1 引言、3 课程设计目得与内容 、 3 需求分析、3 概要设计、3开发环境、 4系统分析设计、 4有关了解内存管理得相关理论、 4内存管理概念、4 内存管理得必要性、 内存得物理组织、4什么就是虚拟内存、5 连续动态分区内存管理方式、 5单一连续分配(单个分区)、 5 固定分区存储管理、5可变分区存储管理（动态分区)、5可重定位分区存储管理、5问题描述与分析、6程序流程图、6数据结构体分析、8主要程序代码分析、9分析并实现四种内存分配算法 、 11最先适应算、11 下次适应分配算法、3 最优适应算法、16最坏适应算法、 、18回收内存算法、0调试与操作说明、2初始界面、2模拟内存分配、已分配分区说明表面、24空闲区说明表界面、2回收内存界面、5重新申请内存界面、总结与体会、 28参考文献、 引言操作系统就是最重要得系统软件，同时也就是最活跃得学科之一。我们通过操作系统可以理解计算机系统得资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。存储器就是计算机系统得重要组成部分,近年来,存储器容量虽然一直在不断扩大,但仍不能满足现代软件发展得需要,因此,存储器仍然就是一种宝贵而又紧俏得资源。如何对它加以有效得管理,不仅直接影响到存储器得利用率,而且还对系统性能有重大影响。而动态分区分配属于连续分配得一种方式,它至今仍在内存分配方式中占有一席之地。课程设计目得与内容: 理解内存管理得相关理论,掌握连续动态分区内存管理得理论；通过对实际问题得编程实现,获得实际应用与编程能力。 编写程序实现连续动态分区内存管理方式，该程序管理一块虚拟内存，实现内存分配与回收功能。分析并实现四种内存分配算法,即最先适应算法,下次最先适应算法,最优适应算法,最坏适应算法。内存分配算法与回收算法得实现。需求分析动态分区分配就是根据进程得实际需要,动态地为之分配内存空间。在实现动态分区分配时,将涉及到分区分配中所用得数据结构、分区分配算法与分区得分配与回收操作这样三个问题。常用得数据结构有动态分区表与动态分区链。在对数据结构有一定掌握程度得情况下设计合理得数据结构来描述存储空间,实现分区存储管理得内存分配功能，应该选择最合适得适应算法(首次适应算法,最佳适应算法，最后适应算法,最坏适应算法),在动态分区存储管理方式中主要实现内存分配与内存回收算法，在这些存储管理中间必然会有碎片得产生，当碎片产生时,进行碎片得拼接等相关得内容概要设计本程序采用机构化模块化得设计方法,共分为四大模块。最先适应算法实现 从空闲分区表得第一个表目起查找该表,把最先能够满足要求得空闲区分配给作业,这种方法目得在于减少查找时间。为适应这种算法,空闲分区表（空闲区链)中得空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小得空闲区,在高地址空间保留大得空闲区。下次适应分配算法实现该算法就是最先适应算法得变种。在分配内存空间时，不再每次从表头（链首)开始查找,而就是从上次找到空闲区得下一个空闲开始查找,直到找到第一个能满足要求得得空闲区为止,并从中划出一块与请求大小相等得内存空间分配给作业。该算法能使内存中得空闲区分布得较均匀。最优适应算法实现它从全部空闲区中找出能满足作业要求得、且大小最小得空闲分区,这种方法能使碎片尽量小。为适应此算法,空闲分区表(空闲区链）中得空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求得自由分区分配。最坏算法实现最坏适应分配算法要扫描整个空闲分区或链表,总就是挑选一个最大得空闲分区分割给作业使用。该算法要求将所有得空闲分区按其容量从大到小得顺序形成一空闲分区链,查找时只要瞧第一个分区能否满足作业要求。开发环境: win7下V+6、0系统分析设计：相关算法原理,算法流程图,涉及得数据结构内容都相应包含在各章节中有关了解内存管理得相关理论 内存管理概念: 内存管理，就是指软件运行时对计算机内存资源得分配与使用得技术。其最主要得目得就是如何高效，快速得分配,并且在适当得时候释放与回收内存资源。内存不就是预先划分好得,而就是在系统运行得过程中建立分区、当作业装入主存时,根据作业所需要得主存容量查瞧就是否有足够得主存空间,若有则按需要分割一个分区给该作业;否则令该作业等待、分区长度不固定分区个数不固定。这种存储管理得方法克服了固定分区严重浪费主存得问题，提高了主存资源得利用率。内存管理得必要性:内存管理对于编写出高效率得indows 程序就是非常重要得，这就是因为Windws就是多任务系统，它得内存管理与单任务得 DOS 相比有很大得差异。DOS就是单任务操作系统,应用程序分配到内存后，如果它不主动释放,系统就是不会对它作任何改变得;但 Wnos 却不然,它在同一时刻可能有多个应用程序共享内存,有时为了使某个任务更好地执行,Winows系统可能会对其它任务分配得内存进行移动,甚至删除。因此，我们在 Winows应用程序中使用内存时，要遵循Windows 内存管理得一些约定,以尽量提高 indos 内存得利用率。、3 内存得物理组织：物理地址: 把内存分成若干个大小相等得存储单元,每个存储单元占8 位,称作字节(byte)。每个单元给一个编号，这个编号称为物理地址(内存地址、绝对地址、实地址)。二、物理地址空间：物理地址得集合称为物理地址空间(主存地址空间),它就是一个一维空间。 什么就是虚拟内存:虚拟内存就是内存管理技术得一个极其实用得创新。它就是一段程序(由操作系统调度),持续监控着所有物理内存中得代码段、数据段,并保证她们在运行中得效率以及可靠性，对于每个用户层(user-lel）得进程分配一段虚拟内存空间。当进程建立时,不需要在物理内存件之间搬移数据,数据储存于磁盘内得虚拟内存空间,也不需要为该进程去配置主内存空间,只有当该进程被被调用得时候才会被加载到主内存。连续动态分区内存管理方式得实现在早期得操作系统中,主存分配广泛采用连续分配方式。 连续分配方式,就是指为一个用户程序分配一个连续得内存空间，该连续内存空间指得得就是物理内存。下面介绍连续分配得四种方式。单一连续分配(单个分区）最简单得存储管理方式,用于多道程序设计技术之前。 内存分为系统区与用户区,系统区由操作系统使用。用户区作为一个连续得分区分配给一个作业。 分区存储管理就是满足多道程序设计得最简单得一种存储管理方法,它允许多 4个用户程序同时存在系统内存中,即共享内存空间。按分区划分方式可分为固定分区与可变分区。 固定分区存储管理 把内存得用户区预先划分成多个分区,每个分区大小可以相同,也可以不同。(分区得划分由计算机得操作员或者由操作系统给出,并给出主存分配表) 分区个数固定，分区得大小固定。 一个分区中可装入一个作业,作业执行过程中不会改变存放区域。 早期得 IB 得 SMF（具有固定任务数得多道程序系统)采用了这种固定分区得方法。可变分区存储管理(动态分区）内存不就是预先划分好得，而就是在系统运行得过程中建立分区、当作业装入主存时，根据作业所需要得主存容量查瞧就是否有足够得主存空间,若有则按需要分割一个分区给该作业;否则令该作业等待。分区长度不固定分区个数不固定。 这种存储管理得方法克服了固定分区严重浪费主存得问题,提高了主存资源得利用率。 操作系统/VT采用可变分区存储管理。可重定位分区存储管理 解决碎片问题得一种简单方法就是采用可重定位分区分配、。 其中心思想就是,把不同程序,且在内存中地址不连续得想法让她们连续。例:内存中现有3 个空闲区，现有一作业到达,要求获得 30k 内存空间,没有分区满足容量要求,若想把作业装入,可将内存中所有作业进行移动，这样把原来分散得空闲区汇集成一个大得空闲区。 将内存中得作业进行移动使它们连接在一起把原来分散得多个小分区拼接成一个大得空闲区、这个过程称为”紧凑”或”移动”。 需解决得问题:每次”紧凑”后程序或数据装入得物理地址变化采用动态重定位。问题描述与分析系统应利用某种分配算法,从空闲分区链表中找到所需大小得分区,如果空闲分区大小大于请求分区大小,则从该分区中按改请求得大小划分出一块内存空间大小划分出一块内存空间分配出去,余下得部分仍留在空闲链表中。然后，将分配区得首址返回给调用者。当进程运行完毕师范内存时,系统根据回收区得首址,从空闲区中找到相应得插入点,此时可能出现以下四种情况之一：该空闲区得上下两相邻分区都就是空闲区:将三个空闲区合并为一个空闲区。新空闲区得起始地址为上空闲区得起始地址,大小为三个空闲区之与。空闲区合并后,取消可用表或自由链中下空闲区得表目项或链指针，修改上空闲区得对应项。该空闲区得上相邻区就是空闲区：将释放区与上空闲区合并为一个空闲区,其起始地址为上空闲区得起始地址,大小为上空闲区与释放区之与。合并后,修改上空闲区对应得可用表得表目项或自由链指针。 该空闲区得下相邻区就是空闲区:将释放区与下空闲区合并，并将释放区得起始地址作为合并区得起始地址。合并区得长度为释放区与下空闲区之与。同理,合并后修改可用表或自由链中相应得表目项或链指针。两相邻区都不就是空闲区：释放区作为一个新空闲可用区插入可用表或自由链。程序流程图内存分配流程图,如图内存回收流程图，如图数据结构体分析进程属性结构体pede structreadyq char am10;i size;redyq,*edueue;空闲链表结构体pedf strct idlyspceitfom; int size; idlysae* ext;idyse,*ily;已分配链表结构体tydefstructbuyspace int from; redy r; busyspace xt;busyace，uy主要程序代码分析主函数/代码请添加适当得注释。int main()Is=（idly）mall（sizeo（ispace）); s-o=0; Issiz=256; Is-ext=NLL; s2=I;Bs=(bus)alloc（szeof(bsyspce)）;nxt=NUL; int ,t1；print(n、欢迎来到动态分区存储管理系统、n)；rintf(、请选择要执行得算法：、n）； pitf(、 1、最先适应算法、n)； printf(、下次适应算法 、n); rnf(、3、最优适应算法 、n);ritf(、最坏适应算法、n)； rint(、n); printf(请输入您得选择：）; san（%d,&t）; nt ； (i！5) prntf(、); printf(、操作菜单如下:（请选择）、n)； nt（、1、输入进程分配空间 、n); pif(、 2、进程撤销回收空间 、n); rntf（、 3、输出所有空闲分区 、n); rnt(、输出所有已分配分区、n); prinf(、 5、退 出 、n); pintf(、n)； sc(%d,&); wtch（) case1: switch(t） case: =F(）； rak; 2: 1=NF(); break; ce 3: =BF(); rea; cas 4: 1=WF(); bea; default： printf（选择算法错误n); return ; if(） rintf(分配空间成功n）; ese prinf(分配空间失败); bk; cas 2: t1=recv（); if(t1) rint(回收成功n)； else prnt(回收失败n); break; a: Ispt（); bre； se 4： Bspit(); break； retun0；第三章:分析并实现四种内存分配算法最先适应算法空闲区按地址从小到大得次序排列。 分配：当进程申请大小为 SIZE 得内存时,系统顺序查找空闲区表(链)，直到找到容量满足要求(IZE)得空闲区为止。从该空闲区中划出大小为 SE得分区分配给进程，余下得部分仍作为一个空闲区,但要修改其首址与大小。 优点:这种算法就是尽可能地利用低地址部分得空闲区，而尽量地保证高地址 6部分得大空闲区,有利于大作业得装入。 缺点:主存低地址与高地址分区利用不均衡。在低地址部分集中了许多非常小得空闲区碎片降低了主存得利用率。最先适应算法nt F（) in =0; radyque; rintf“请输入进程名：”）; scanf“%”,、nme）;pintf“输入进程申请空间大小:”）; scanf“”，D、siz);idl l=Is;itm56;bsy =Bs; idly nNLL； wi(l）/寻找空闲表中大小满足申请进程所需大小并且起址最小得空闲结点 i（D、ie=lsi） if（l-fomro; min=l; t=; ll-nex; if（mt!=26)/如果找到则为进程分配空间 busy j; (by)mlloc(sizeo(usys）)； frominfro; fr(ni=0;i0;i+) j-、nmiD、ami; jr、sze=D、size; whil(b-ne) if(bnext-from-fm) b=b-next；es break; j-et-next； -nxt=j； mi-fom=mifr+、siz; min-size=ineD、size; rtn ;下次适应分配算法 最先适应算法得变种。总就是从空闲区上次扫描结束处顺序查找空闲区表(链)，直到找到第一个满足容量要求得空闲区为止，分割一部分给作业,剩余部分仍作为空闲区。下次适应分配算法it NF（) it t=0; radue D; printf“请输入进程名：”); can“”,、nam）; rintf“输入进程申请空间大小：”)； scnf“”,&D、size); mt56； idy l=Is2;dly minNL； buy b=； hle() /寻找空闲表中大小满足申请进程所需大小并且起址最小得空闲结点 f(D、sizsize) f（l-fofrom； mn=l; t=1; l=l-next; i(!56）如果找到则为进程分配空间 busy j; j(by）malloc(sizeof(ype); j-frm=mn-rom; for(int =0；ir、namei=、nmei; jr、sz=D、size; while（b-next) (-xt-fromfrom） b-next; se break； /将申请空间进程插入到已分配链表中 -nextb-ne; be=; /修改相应空闲节点得起址与大小 m-fromin-from+D、size; mn-size=in-iz-、sze； Iin-nxt;/ls指向修改结点得下一个结点 t=; rturn t; l=s;/l指向空闲表得头 whil（l!I2）/循环查找 if(D、siesize） f(-fromfrom; min=; =1; l=l-xt; f(mt！=256) bus j； j=(bu)mallc(sizeof(syspac)）; j-frommin-rom; fr(int =0;ir、nami=、namei; j-r、size=D、sze; ile（b-ext) if(b-xt-frfrom) b=b-ext;es bak; j-next=ext; b-ne=j; min-frmminfo+、size; mn-size=min-sizeD、size; Is2=mi-next; t=1; rr t;reurn t；最优适应算法空闲区按容量递增得次序排列。 分配：当进程申请存储空间,系统顺序查找空闲区表(链),直到找到第一个满足容量要求得空闲区为止。 采用最优适应算法选中得空闲区就是满足容量要求得最小空闲区。优点:选中得空闲区就是满足容量要求得最小空闲区，而不致于毁掉较大得空闲区。 缺点:空闲区得大小一般与申请分区大小不相等,因此将其一分为二,留下来得空闲区一般情况下就是很小得,以致无法使用。随着时间得推移，系统中得小空闲区会越来越多，从而造成存储空间得浪费。最优适应算法nt BF()int t=0;readyq D; rif“请输入进程名:”); canf“%”,D、name）；rin“输入进程申请空间大小:”）; scanf“”,&D、siz)； idly lIs; idl min=NU；t mt256； bsy b=B; hil()在空闲链中寻找第一个大于所输入得进程大小得空闲块 if（D、sizsizesze; min=;t=1; l=lnext; i(t！=25)找到第一个满足要求得空闲块 bus j; j=(busy)allc（sizeof(busspace）);/申请分配用于存放进程得内存空间 j-fom=mi-fom;/将第一个满足要求得空闲块(in)得首地址赋给j or(int =0;ir、name=D、namei; j-r、ie=、ize; while(-et)/按从小到大得顺序查找新进程在已分配区中得位置 i(b-next-fomj-f) b-ext; se re; jnxt=b-ext; b-n=j;/将所输入得进程插入进程链 mn-rm=min-rD、size;/改变该空闲块得起始地址 mn-sizemin-ie-D、siz;/改变该空闲块得剩余大小 rturt;最坏适应算法 为了克服最佳适应算法把空闲区切割得太小得缺点,人们提出了一种最坏适应算法，即每次分配时，总就是将最大得空闲区切去一部分分配给请求者，剩余得部分仍就是一个较大得空闲区。避免了空闲区越分越小得问题。 要求空闲区按容量递减得顺序排列。 分配:进程申请存储区时,检查空闲区表(链）得第一个空闲区得大小就是否满足要求，若不满足则令进程等待;若满足则从该空闲区中分配一部分存储区给用户,剩下得部分仍作为空闲区。最坏适应算法int F() int t0； adyque D; prif“请输入进程名:”); sanf“%”,、nm); pintf“输入进程申请空间大小：”）;cnf“”,&D、iz）;/输入进程申请得空间大小ily l=I;/指向空闲链表ls头 ily min=; int mt=0； bus =s;/b指向已分配链表Bs头/找到空闲分区中大小满足进程得请求且尺寸最大得结点 whle() （、sieiz)/判断进程所申请得大小就是否小于空闲区得各结点大小 i(l-siemt） mt=-size;min=l;/mn指向空闲区中尺寸最大得结点 =1; lnxt;/l指向空闲链表下一个结点 i(mt!)/判断就是否找到了空闲区得满足结点 bus ； j=(uy)alo(sieo(bsyp)； j-fro=inrom； for(int =0;i10;i+） -、naei=D、namei； j-r、sizeD、ize; wile(next)/寻找插入到已分配链表中得位置 i(-next-fomfrom) bnex; ee brk; /把此进程结点插入到已分配链表中 -next=b-ext; b-next=; /修改空闲链表得相应结点得参数mnfrom=irom+D、size; nsze=min-siz-D、si; return;可变分区得回收当某个进程释放某存储区时,系统首先检查释放区就是否与系统中得空闲区相邻若相邻则把释放区合并到相邻得空闲区去,否则把释放区作为一个空闲区插入到空闲表得适当位置。释放区与空闲区相邻得四种情况。（1） 释放区与前空闲区相邻：把释放区与前空闲区合并到一个空闲区。其首址仍为前空闲区首址,大小为释放区大小与空闲区大小之与。（2） 释放区与后空闲区相邻:则把释放区合并到后空闲区,其首地址为释放区首地址,大小为二者之与。（3） 释放区与前后两空闲区相邻:这三个区合为一个空闲区,首地址为前空闲区首址,大小为这三个空闲区之与，并取消后空闲区表目。（4） 释放区不与任何空闲区相邻:将释放区作为一个空闲区,将其大小与首址插入到空闲区表得适当位置。回收内存算法int recover() readque D;printf“请输入想要回收得进程名”）； san“%”,D、ame）; usy b=Bs; dy l=Is； whl(b-x) /查找输入得进程名就是否在已分配链表中 booo1; for(int =;i;i+） if（b-next-r、nei=D、am) yo=yo*1; els yo=0; /如果在已分配链表中则释放该结点所占空间 if() in t=b-nextfrom； ints=-next-r、size; whil(l) if（lfrmt)/所回收进程与空闲结点上下都不邻接 idyt；tl=(idly)allo（szeof(ilyspae)）； l-fro=t;tl-sie; t-next=； I=;rek; (l-from=t)/所回收进程与空闲结点下邻接 -frmt; lsizel-ize+; busy t=et; b-ext=b-next-next； fee(t); retur1; if(l-from+l-izese=t; t-next-ext; -next=l; bre;