数据结构与算法分析9.ppt

文档介绍：---线性结构、层次结构和网状结构中,使用高级语言描述了它们的内存映象但并没有涉及具体的存储分配实际上结构中的每个数据元素都占有一定的内存位置,在程序的执行过程中,数据元素的存取是通过对应的存储单元来进行的当计算机是被单个用户使用时,那么整个内存除操作系统占用一部分之外,都归这个用户的程序使用(如PDP—11/01的内存为32K字,系统占用4K,用户程序可用28K)。但在多用户分时并发系统中,多个用户程序共享一个内存区域,此时每个用户程序使用的内存就由操作系统来进行分配了。并且,在总的内存不够使用时,还可采用自动覆盖技术。“请求”分配内存如何回收那些用户不再使用而“释放”的内存,以备新的“请求”产生时重新进行分配在下面的讨论中,将统称已分配给用户使用的地址连续的内存区为“占用块”,称未曾分配的地址连续的内存区为“可利用空间块”或“空闲块”在系统运行的初期,整个内存区基本上分隔成两大部分:低地址区包含若干占用块;高地址区(即分配后的剩余部分)是一个“空闲块”。,设计内存的分配和回收方法时,必须考虑和确定以下几种策略和数据结构(1)分配结构(2)放置策略(3)交换策略(4)调入策略(5),可利用空间表可以有下列三种不同的结构形式:第一种情况是系统运行期间所有用户请求分配的存储量大小相同。第二种情况,系统运行期间用户请求分配的存储量有若干种大小的规格。第三种情况,系统在运行期间分配给用户的内存块的大小不固定,可以随请求而变。通常采用三种不同的分配策略。(1)首次拟合法(2)最佳拟合法(3):在整个动态存储管理过程中,不管哪个时刻,可利用空间都是一个连续的存储区,在编译过程中称为“堆”,每次分配都是从这个可利用空间中划出一块