HCS08微控制器上有关内存分配
的几个问题
师英，shylion@https://www.doczj.com/doc/86647252.html, 这里讨论HCS08微控制器上的几个有关内存分配的问题，提及其存储器编
址模型；数据对齐；Tiny和Small两种内存模型的差异；以及堆和栈的分配。指正错误与讨论其中细节，请电邮到shylion@https://www.doczj.com/doc/86647252.html,。谢谢。
目录：
HCS08微控制器上有关内存分配的几个问题..............................................- 1 -
1.1. HCS08的存储器映射...............................................................................- 2 -
1.1外设寄存器.........................................................................................- 2 -
1.2 RAM....................................................................................................- 5 -
1.3 FLASH................................................................................................- 5 -
1.4 向量（Vectors）................................................................................- 6 -
1.2. 数据对齐....................................................................................................- 7 -
1.3. HCS08的存储器模型：Tiny和Small....................................................- 9 -
1.4. 堆（heap segment） (12)
1.5. 栈（stack segment） (13)
1.1. HCS08的存储器映射
每个HCS08微控制器的存储器映射（Memory Map ）都不一样，但是它们都有相同的分配结构——一个线性的统一编址的16bit （总共64K ）寻址空间。下面我们以MC9S08AW60为例认识它的存储器映射。
图1- AW60的存储器映射 1.1外设寄存器
外设寄存器的名称区别于CPU 寄存器。这些寄存器用来控制外设的行为和属性，或者获取外设的状态。微控制器的所有和真实世界的信息交互和对真实世界的“控制”在应用程序级都是通过操作这些寄存器完成的。
CPU08的所有外设寄存器都被映射在存储器中，因此不需要特别的I/O 指令完成对外设的操作。有些微控制器的外设寄存器没有被映射到存储空间来，所以对外设的操作完全依靠I/O 类指令完成，所以需要额外的代码长度和执行周期作为代价。例如，读取一个端口的状态，然后改变其中的某些位再写回去这样的操作，在CPU08上只需要一条指令BSET 。而在某个8bit 微控制器上，则需要如下的操作：
IOREAD PTA
OR 0b00000001 IOWRITE PTA
第一条指令读取PTA ，第二条指令把A 的第0位置位，第三条指令写回端口A 。这实际上是一个读取-修改-写回（Read-Modify-Write ）的过程，但是额外的
? 直接寻址页面 并且支持位操作
整个64K 寻址空间不分页访问
I/O 特殊的I/O 指令
存储空间和指令周期被浪费在一个本应该简单的操作上。同样的功能用CPU08的汇编语言这样写就可以了：
这条指令使用了2bytes 的指令长度和5个指令周期。
CPU08对并不是把所有的外设寄存器都逐个安排在一段连续的地址空间中，而是根据对它们访问的频率分别放在3个不同的位置。这是一种战略优化。
? 直接页面（Direct Page ）
? 高地址页面（
Hige Page ）
? FLASH
CPU08把大部分需要经常访问的外设寄存器都映射在寻址空间的直接页面（地址0x0100以前），使得对它们的访问更加高效，并且可以进行直接的位操作。对于AW60，0x0000~0x006F 的地址空间映射了这些外设寄存器。
另外一部分寄存器被映射在0x1800以后的扩展寻址范围中，这些寄存器叫做“High Page Registers ”。这部分空间被安排了一些不经常访问的寄存器，如SRS ，SBDFR ，SOPT ，SMCLK ，SDIDH:SDIDL ，SRTISC ，SPMSC1，
SPMSC2，背景调试用寄存器，FLASH 控制寄存器，I/O 端口内部上拉器件、摆率控制、输出能力选择寄存器等。一般来说，这些硬件级的选项在应用程序初始化的时候做一次设置，后面基本不用再去改动它，或者很少改动。关于这些寄存器的说明需要查阅各个微控制器的数据手册。这里我们来看其中的几个例子：
? System Reset Status Register (SRS)
这个只读寄存器包含了一些指示标志，用来显示上一次系统复位的原因。对于AW60，分别为上电复位（POR ），复位引脚（PIN ），看门狗（COP ），非法操作码（ILOP ），内部时钟发生器（ICG ）和低电压检测（LVD ）。这些标志位对于应用程序判断系统异常复位并给出不同的应对措施，或者对应硬件故障诊断很有用处。
向SRS 写入任何数据会导致看门狗定时器（COP ）复位（这个动作经常被叫做“喂狗”），而不会影响SRS 的内容。在CodeWarrior C 头文件中，喂狗被定义成这样一个宏（我们终于看到C 语言的代码了）：
在这些寄存器中，有一些设置位是“只写一次（Write-once ）”的。比如： ? System Option Register (SOPT)
这个寄存器包含了3个只写一次的控制位，分别控制看门狗使能或者关闭（COPE ），看门狗溢出周期选择（COPT ），休眠模式使能或者禁止
（STOPE ）等。应用程序只有一次机会可以改变这些设置，这有点像有些微控制器中的所谓“设置位（Configuration Bits ）”，只不过那些设置位并没有映射在内存地址中。
BSET 0, PTAD ; 机器码为0xb0（OPCODE ）, 0x00（operand ） #define __RESET_WATCHDOG() {asm sta SRS;}
有一些High Page Registers对于所有HCS08微控制器，其地址都是固定的。比如调试器强制复位（SBDFR），器件ID寄存器等。这是为了方便调试器和编程器厂商。
?System Background Debug Force Reset (SBDFR)
对于所有HCS08微控制器，其地址都是0x1801。这个寄存器只有一个有效位，第0位BDFR。向这一位写1会强制使系统复位。但是，用户程序并不能操作这个控制位，只有通过背景调试模块（BDM）的命令才能操作它。读这个寄存器永远得到0x00。
?System Device Identification Register (SDIDH:SDIDL)
对于所有的HCS08微控制器，其地址都是0x1806:0x1807。16bit中一共有12位是有效的（SDIDH的低4位和SDIDL的所有8位），它们指示出这个这个硬件的类型。AW60的ID是0x008。
还有一些叫做“非易失寄存器（Nonvolatile Register）”的单元被映射在
0xFFB0到0xFFBF的空间中。这些单元其实就是一些FLASH单元，被指定为安置一些系统配置的参数。如NVBACKKEY，NVPROT，NVOPT等。对这些寄存器的赋值可以通过定义一些指定地址的常数（const）来完成。这些寄存器其实比“只写一次”的寄存器在意义上更接近“配置位”。在HCS08中，这些寄存器主要用来设置系统存储器安全机制（Security）和保护机制（Protection）。
; 在汇编语言中给NVPROT赋值。Bit0为0，bit7~bit1作为保护地址高7位，低地址为
; 0x00FF，因此最后一个不受保护的地址单元为0xDFFF，也就是说，保护从0xE000d到
; 0xFFFF的空间。
ORG #$NVPROT
DB #$DE
// 在C语言中给NVPROT赋值。
const unsigned char _nvprot @ FFBF = 0xDE
?Flash Options Register，NVOPT，地址0xFFBF
在这个寄存器中，包含了FLASH加密的几个设置位。很多程序员在设计一个项目的时候，他们会考虑硬件的安全性，免得自己抓断很多头发才写出来的代码被人家几分钟之内给抠出来，复制自己的产品；另外一些例如认证和加密的应用，使得硬件的安全性尤为重要。HCS08提供了系统存储器的安全机制。这个安全机制的设置是被编程在FLASH地址0xFFBF，由其bit1和bit0，
SEC01:SEC00决定。在SEC01和SEC00的4种可能取值中，只有1:0这种组合禁止安全机制，其它的取值使能此机制——该地址被擦除后（所有bit全1），安全机制也是被打开的。
系统复位后，NVFOPT的内容被copy到高地址寄存器FOPT中，安全机制开始发挥作用。HCS08的安全机制使得微控制器的RAM和FLASH被作为安全资源，任何没有通过认证的访问都被禁止。直接页面寄存器，高地址寄存器和背景调试控制器不受安全机制的保护。在安全资源中运行的程序代码可以访问存储器空间的任何资源，而安全资源以外的应用程序或者背景调试接口试图访问安全资源都会被禁止。除了擦除整个FLASH。
?NVBACKKEY，地址0xFFB0~0xFFB7
如果FOPT寄存器中的bit7，KEYEN被置位，则安全机制的“后门密钥”被使能。这种情况下，应用程序可以通过校验8bytes的后门密钥来暂停安全机制。NVBACKKEY[8]这个常数数组的值为编程者预设的后门密码。
?NVPROT，地址0xFFBD
NVPROT和FLASH的保护机制相关。保护机制不同于安全机制，它用来防止FLASH的内容被误改写和擦除。HCS08的FLASH的一个页面包含512bytes。应用程序可以选择需要保护的FLASH的起始页面地址，从这个地址后面的所有页直到最高地址之内的所有页都被保护。为了启用FLASH保护，NVPROT的
bit0必须为0，bit7~bit1作为最后一个不受保护的FLASH地址的高7位，
A15~A9；低9位默认为1。在复位后，NVPROT的内容被copy到FPROT寄存器。
在程序中包含一个bootloader的时候，保护机制尤其有用。Bootloader将是程序代码中至关重要的部分，它首先需要被保护起来，在任何情况下不应被破坏，通过它可以恢复和更新别的程序模块。
只要FLASH保护被启用，则复位向量和中断向量区也一定被保护起来。为了使bootloader能够更新向量，中断向量可以被重定位（redirection）——把中断向量表搬移到没有保护的地址空间去。通过设置NVOPT的bit6，FNORED，可以使中断向量被重定位。
1.2 RAM
CPU08的RAM大小和器件类型相关。AW60有2048bytes的RAM提供应用程序使用，地址为0x0070~0x0870。在RAM里除了定义应用变量，栈也安排在RAM中。
地址小于0x0100的RAM是其中宝贵的资源，除了可以用高效的直接寻址方式访问，这部分单元还支持位操作。
1.3 FLASH
HCS08的程序存储器为0.25um工艺的FLASH，以512bytes为一个页组织。例如AW60有124页，共124×512 = 63,280bytes。HCS08的FLASH比
HC08在性能上有很大提升。和HC08相比，我认为最值得圈点的是下面几点：?更快的访问（读取，编程，擦除）速度
?更多擦写周期，100,000次
?内建的擦除和编程算法，全工作电压范围内可以工作
FLASH在微控制器中用来存储应用程序目标代码，常数表等内容。由于CPU08的FLASH可以实现自编程功能，所以也可以用作模拟EEPROM来存放数据。也可以实现bootloader这样的在线程序更新或者在线编程的功能。
如果HCS08器件FLASH大小超过57kbytes，那么它的编址可能和位于
0x1800的高地址寄存器发生冲突。为了避免这种冲突，在这些器件上，FLASH 空间被划分为两块，来绕开高地址寄存器。例如AW60，在0x870~0x17FF地址空间有3984bytes存储单元，在0x1860~0xFFFF地址空间有59,296bytes存储单元。除了地址不同，这些两部分FLASH在其它方面都是平等的。
1.4 向量（Vectors）
CPU08的向量包括复位向量（Reset Vector）和中断向量表（Interrupt Vector Table，IVT）。在系统复位后，复位向量（位于FLASH地址
0xFFFE:0xFFFF，其内容实际上是一个地址）被装载到PC中，应用程序从该地址开始执行。
在Bill Blunden的著作《虚拟机的设计与实现》中，Bill形象地把向量表比喻为电话号码簿。每一个中断源都有一个唯一的“电话号码”——中断向量将中断源和其中断服务程序关联，当中断条件发生时，CPU可以根据这个“电话号码”快速找到对应的中断服务程序（ISR）并转去执行。HCS08的向量映射在FLASH的地址0xFFC0~0xFFFF之间，由于每个向量都是一个指向特定程序段的地址，每个向量的长度为16bit。如果这个空间没有用完，剩余的存储空间可以被应用程序自由使用。
当中断发生时，CPU08的行为为：
?在栈中保存CPU寄存器
?将CCR寄存器中的I置位，屏蔽其它中断
?取得当前等待的中断请求中最高优先级的那个向量
?从该向量指向的程序段中取得头3个字节的操作码和操作数来填充被破坏的指令队列
在第一步中，CPU寄存器是被自动入栈的，顺序为：PCL，PCH，X，A，CCR——H没有入栈。
基本上每个外设都拥有至少一个中断源；IRQ用来接受外部事件的中断请求；SWI指令引起CPU的软件中断（一般用于调试）。
——前面我们提到，中断向量表可以被重定位。这是为了bootloader实现方便而增加的一个特别有用的功能。
1.2. 数据对齐
在一个硬件系统中，除非全部使用单字节的unsigned char类型的数据，否则会遇到数据存储单元对齐的问题，特别是当不同结构的CPU之间通信的时候，针对数据对齐的考虑变得不可避免。在Intel的平台上，一般采用所谓的低字节在后（Little Endian）的存储方式，即数据的最低字节数据存储在低地址中；而非Intel平台则大多采用高字节在后（Big Endian）的存储方式，即高字节数据存放在低地址中。在CodeWarrior提供的C08编译器中，默认的数据对齐顺序也是Big Endian的。考虑下面的测试程序，这段程序定义了一个long型的变量（4 bytes），然后顺序单独取出这4 bytes赋值给一个unsigned char型的变量。
void main(void) {
unsigned char temp;
long x = 0x12345678;
long *px = &x;
temp = (unsigned char) *((unsigned char *)px + 0);
temp = (unsigned char) *((unsigned char *)px + 1);
temp = (unsigned char) *((unsigned char *)px + 2);
temp = (unsigned char) *((unsigned char *)px + 3);
#ifdef __HCS08__
EnableInterrupts;/* enable interrupts */
/* include your code here */
for(;;) {
__RESET_WATCHDOG();/* feeds the dog */
}/* loop forever */
/* please make sure that you never leave main */
#endif
}
这些代码可以在HCS08上编译和运行，也可以在PC上编译和运行。在HCS08上，4次给temp赋值的结果分别为：0x12，0x34，0x56，0x78；而在PC上，4次赋值的结果分别为：0x78，0x56，0x34，0x12。
假如不考虑数据分配的定义，PC通过串行口分4次（每次只能发送1byte 数据）把x发送给一个HCS08微控制器，那么微控制器接收到的数字并不是
0x12345678，而是0x78563412，程序员必须在软件中把这些接收到的数据的顺序调整过来，重新组合成一个正确的值，或者在发送的时候就按照接收者的顺序发送。
1.3. HCS08的存储器模型：Tiny和Small
08 C编译器提供两种存储器模式给程序员选择：Tiny和Small。在Tiny模式下，可供直接使用的RAM空间为地址0x0100以前的单元（零页或者直接寻址页），对于AW60，可直接使用的RAM地址范围为0x0070到0x00FF，栈和全局变量、静态变量都映射在这部分空间中。虽然Tiny模式提供了较快的存取速度和较短的指令长度，但是可供直接使用的RAM空间太少，如果要在零页以外的地址空间安排变量，则必须使用#pragma通知链接器。我们创建一个使用Tiny模式的工程，首先来看它的PRM文件。
SEGMENTS
/* Here all RAM/ROM areas of the device are listed. Used in PLACEMENT below. */
ROM = READ_ONLY 0x1860 TO 0xFFAF;
Z_RAM = READ_WRITE 0x0070 TO 0x00FF;
RAM = READ_WRITE 0x0100 TO 0x086F;
ROM1 = READ_ONLY 0x0870 TO 0x17FF;
ROM2 = READ_ONLY 0xFFC0 TO 0xFFCB;
END
PLACEMENT
/* Here all predefined and user segments are placed into the SEGMENTS defined above. */
FAR_RAM INTO RAM;
DEFAULT_ROM, ROM_VAR, STRINGS INTO ROM;
/* ROM1,ROM2 In case you want to use ROM1,ROM2 as well, be sure the option -OnB=b is passed to the compiler. */
_DATA_ZEROPAGE, MY_ZEROPAGE, DEFAULT_RAM INTO Z_RAM;
END
STACKSIZE 0x50
VECTOR 0 _Startup/* Reset vector: this is the default entry point for an application. */
在PLACEMENT段里边，我们可以看到，默认的数据存储空间是Z_RAM，即地址范围0x0070到0x00FF之间，有144bytes。而地址范围0x0100到0x086F 之间的1904bytes被定义为FAR_RAM。在声明全局变量的时候，如果不做特别指定，链接器只在默认的Z_RAM中分配它们。另外，栈也被分配在Z_RAM 中，有80bytes被占用了，可供分配全局变量和静态变量的RAM空间实际上只剩下了64bytes。Startup代码通过宏INIT_SP_FROM_STARTUP_DESC()来初始化栈，这个宏在文件hidef.h中被定义为下面汇编语句的集合：
__asm LDHX @__SEG_END_SSTACK; __asm TXS;
这个宏取出__SEG_END_SSTACK，并把它赋值给SP。__SEG_END_SSTACK 是由链接器定义的对象。从map文件中可以找到它的值，被定义为0x100：OBJECT-ALLOCATION SECTION
Name Module Addr hSize dSize Ref Section RLIB
-------------------------------------------------------------------------------------------------
- LABELS:
__SEG_END_SSTACK 100 0 0 1
我们在main.c中写下下面的测试代码：
unsigned char auto_data[0x40]; /* auto_data[] will be allocated in the default Z_RAM*/
#pragma DATA_SEG FAR_RAM /* specify the allocation segment FAR_RAM */
unsigned char data1;
unsigned char data2;
#pragma DATA_SEG DEFAULT /*specify the default data segment Z_RAM*/
void main(void) {
// static unsigned char data3; /* static variable will also be allocated in Z_RAM /test 1 */
data1 = auto_data[0];
data2 = auto_data[1];
// data3 = 0xff; // test 2
EnableInterrupts; /* enable interrupts */
/* include your code here */
for(;;) {
__RESET_WATCHDOG(); /* feeds the dog */
} /* loop forever */
/* please make sure that you never leave main */
}
全局变量auto_data[]（一个数组）会被分配在默认的RAM中，即Z_RAM；
#pragma语句则告诉链接器data1和data2应该分配在FAR_RAM中，因为
auto_data[]已经占用了仅剩的64bytes（另外80bytes被栈占用）。如果去掉程序中的#pragma语句，或者去掉语句test 1和test 2的注释（定义了一个静态变量data3），或者使数据auto_data包含的元素数目大于0x40，都会导致一个链接期错误：
L1102: Out of allocation space in segment Z_RAM at address 0xb1
我们再来创建一个使用Small模式的工程，并观察它的prm文件。SEGMENTS
/* Here all RAM/ROM areas of the device are listed. Used in PLACEMENT below. */
ROM = READ_ONLY 0x1860 TO 0xFFAF;
Z_RAM = READ_WRITE 0x0070 TO 0x00FF;
RAM = READ_WRITE 0x0100 TO 0x086F;
ROM1 = READ_ONLY 0x0870 TO 0x17FF;
ROM2 = READ_ONLY 0xFFC0 TO 0xFFCB;
END
PLACEMENT
/* Here all predefined and user segments are placed into the SEGMENTS defined above. */
DEFAULT_RAM INTO RAM;
DEFAULT_ROM, ROM_VAR, STRINGS INTO ROM;
/* ROM1,ROM2 In case you want to use ROM1,ROM2 as well, be sure the option -OnB=b is passed to the compiler. */
_DATA_ZEROPAGE, MY_ZEROPAGE, INTO Z_RAM;
END
STACKSIZE 0x50
VECTOR 0 _Startup/* Reset vector: this is the default entry point for an application. */
和Tiny模式相比，区别是DEAFAULT_RAM段被放置在RAM中，而没有定义FAR_RAM段。在这种模式下，链接器会在整个可用的RAM空间中自由安排
全局变量和静态变量，并且栈也不会被放在Z_RAM中。在map文件中，我们发现__SEG_END_SSTACK被定义为0x150，使得栈被分配在0x0100到0x0150之间的空间中。
OBJECT-ALLOCATION SECTION
Name Module Addr hSize dSize Ref Section RLIB
-------------------------------------------------------------------------------------------------
- LABELS:
__SEG_END_SSTACK 150 0 0 1
在small模式下，默认的变量不会被分配在零页。如果为了提高程序的效率要把一个变量指定到零页，应该使用下面的#pragma语句：
#pragma DATA_SEG MY_ZEROPAGE
unsigned char dir_data1; /* dir_data1 will be allocated in Z_RAM */
#pragma DATA_SEG DEFAULT
unsigned char auto_data2; /* auto_data2 will be allocated in DEFAULT_RAM */从上面的分析可以看出，虽然tiny模式使链接器在分配变量时把所有未经特别指定的变量全都映射到零页而提高代码效率，但是零页的空间毕竟有限。
而small模式会把变量分配到0x0100以后的地址，使得默认的RAM空间更大。两种模式下，都可以通过使用适当的#pragma来指定变量分配的段。在编程实践中，可以根据变量的多少和优化的需要酌情使用这两种存储器模式。
还有一点区别特别值得注意：在Tiny模式下，指针的长度默认为8bit。那么假如程序员声明了一个指针变量，并且试图通过它来访问地址0x0100以后的存储器单元，一定会得到错误的结果。为了处理这种情况，必须用关键字__far 修饰该指针变量：
unsigned char * __far ptr;
在Small模式下，则因为指针长度默认为16bit，所以不用特别声明。不过为了提高访问效率，可以用关键字__near修饰一个指针变量，使其长度为8bit，来访问地址0x0100以前的存储器单元。
unsigned char * __near ptr;
1.4. 堆（heap segment）
回忆我们在大学里开始学习C语言的时候，老师和学长们总在说的难点，仿佛世界上最可怕的事情一样，就是C语言中的指针的使用。错误地使用指针确实会给导致系统崩溃，但是什么情况下这种危险才会出现呢？
动态内存分配技术给合理利用有限的资源提供了良好的解决方案，但这也导致上述的潜在危险。我们先来看一段代码：
#include
#include "derivative.h" /* include peripheral declarations */
#include
void main(void) {
unsigned char *ptrTest = NULL; // 定义一个指针。定义之初它并不指向任何有意义的内存unsigned char i;
i = *ptrTest; // (1) 在指针被初始化之前通过该指针访问内存
pTest = malloc(20);// 为指针pTest分配20bytes的内存
i = *ptrTest; // (2) 指针初始化，但是它指向的内存单元还没有被初始化
for (i = 0; i < 20; i++) {
*(ptrTest++) = i; // (3) 初始化这段内存
}
i = *ptrTest; // (4) 因为++操作符的影响，此时pTest已经指向有效内存范围之外 ptrTest--; // 使pTest回到有效内存的最后一个单元
i = *ptrTest; // (5) 访问有效内存的最后一个单元
free(ptrTest); // 释放内存
i = *ptrTest; // (6) 此时pTest指向的单元已经没有意义，成了所谓“野指针”
for(;;) {
__RESET_WATCHDOG(); /* feeds the dog */
} /* loop forever */
/* please make sure that you never leave main */
}
在这段代码中，首先声明了一个指向unsigned char类型的指针变量ptrTest。在定义之初，pTest并不指向任何有意义的内存单元。在CW5.1中编译上述代码不会产生任何的错误或者警告信息。在声明这个指针变量的时候，我把它初始化为一个空指针（赋值为NULL），这样做可以避免编译器产生的一个警告：“C5651: Local variable‘ptrTest’ may be not initialized”。在这些代码中，我在6个不同的位置试图通过ptrTest去访问内存，下面我们分别来分析这7处内存访问的情况：
(1)ptrTest还没有被初始化，通过它指向的内存单元没有意义；
(2)ptrTest已经被初始化，运行期库（run-time library）函数malloc()在数据
堆中分配出20bytes的空间，ptrTest指向这段空间。但此时这20bytes的内存单元都还没有被初始化，通过ptrTest读取到的仍然是没有意义的数据；
(3)将ptrTest指向的20bytes内存单元初始化；
(4)由于循环体中++操作符的影响，退出循环时，pTest指向了分配内存之外
的一个存储单元，这个单元的数据也是没有意义的；
(5)将ptrTest减去1后，它指向分配内存的最后一个单元；
(6)库函数free()将ptrTest指向的内存释放，这段内存从此变为一段自由的
空间，虽然先前给这些存储单元赋的值并没有被摧毁，下次调用malloc()可能会在这段空间中重新分配。空间被释放后，pTest的值也还没有改
变，成了一个所谓的“野指针”，通过它访问内存得到没有意义的数
据。
在上述6种情况下，只有(3)和(5)的操作是正确的。其它的操作都访问了没有意义的内存单元，然而无论是在编译期还是运行期都不会报错。在实际的程序中，程序员不光会通过指针ptrTest去读取内存，还会有改写的操作，甚至有多个这样的指针变量。程序员必须对自己要做什么，做过些什么，还有什么没有做等各种情况明察秋毫，一丝错误都不能犯，否则他立刻会尝到指针带来的苦果。
在内存管理的概念中，这样提供给程序在运行期动态分配的内存段叫做堆（Heap）。Heap实际上类似于一个大数组，它预留了一段空间，malloc()函数
在Heap中开辟出一段空间给一个指针变量，而free()则释放该指针变量指向的空间。对于08C，Heap实际上就是一段RAM，它一般会被安排在全局变量和
栈的中间。08C的Heap有一些简陋的出错处理机制，但是这些机制实在是太简陋了，我们刚刚看到了它的功能。
厂商们（包括硬件厂商和编译器厂商）都不建议用户在CPU08平台上使用Heap，即动态内存分配技术。幸运的是，用8bit微控制器处理的事务更多是和真实世界相关的控制功能，而没有什么庞大的算法，所以我们好像也不需要这种有点令人头疼的技术。
1.5. 栈（stack segment）
在C语言中，变量都被映射在数据段。
每一个变量都有其生存周期。在应用程序的整个生命周期都生存的变量，就是那些全局变量，它们是被映射在DEFAULT DATA_SEG里边，从最低地址顺序排列（在Small模式下，这个地址是0x0100）。在这一段存储器单元中映射的还有静态变量。不考虑堆的存在，在所有的全局变量和静态变量都安排出各自的空间后，紧接着就是栈的空间。
静态局部变量被static关键字修饰，它们一般是一些不希望在调用结束后被消灭的局部变量（静态全局变量呢？）。在为变量安排存储空间单元的时候，静态变量和全局变量享有同样的待遇，它也存在于DEFAULT DATA_SEG开头的一些空间里面，而不是在栈中。这样，在一个过程调用中改变了静态变量的
值，调用结束后，这个值仍然保留，在下次调用同一过程时，可以在原来继续获得上次的值。
静态局部变量和全局变量的区别在于其作用域。只有声明它的过程才可以使用它，别的过程则没有这种特权。可以说，静态局部变量是“私有的”。 在一个过程中定义的变量，叫做局部变量，它的生存周期和过程相同。也就是说，当过程被调用的时候，才为这些变量分配内存单元；而当调用结束时，为局部变量分配的内存单元被回收，局部变量也随之消亡。这个过程是依靠栈完成的——所有的局部变量都在栈中映射。
在C 语言的过程调用中，参数的传递和返回值依靠寄存器和栈完成。在内存映射的过程中，参数和返回值的地位和局部变量相同。
TSX 和TXS 指令使得H:X 可以和SP 交换16bit 的数据。当应用程序试图访问栈空间而又不想动SP 的时候，用H:X 作为指针指向栈空间是一个不错的办法。另外，在程序初始化的时候，对栈指针的初始化必须用TXS 指令来完成。
在上面的代码中，我们看到了如何初始化栈指针。__SEG_END_SSTACK 是由链接器定义的常数，在本例中，这个常数等于0x150（这是个常数是这么来的：在small 模式下，所有的全局变量都从地址0x100起。全局变量顺序安排完成之后——在本例中，一共有0个全局变量——下一个可用的地址加上STACK SIZE 得到的地址被指定为栈底）。执行完第一条指令后，H:X 的值为0x150，第二条指令把H:X 的值传送到
SP 中去，执行完成后，SP 的值为
0x14F 。我们可以发现，当一个指针值从H:X 传送到SP 的时候，这个值被减了
1。反之，把SP 传送到X 的时候，传送的值会被自动加上1，而SP 本身的值不被改变。这是因为，SP 永远指向下一个可用的内存单元，而索引寄存器应该直接指向目标单元。
16bit 字长的SP 用来维护栈。理论上，SP 可以指向HCS08寻址空间的任何单元，但实际上栈只能被安置在RAM 空间中，栈空间的大小可以是整个RAM 空间的大小。在使用BSR 或者JSR 调用子程序（routine ）的时候，下一条顺序指令的地址（返回地址）会自动保存在栈中，子程序返回时（RTS ），返回地址被取出，自动装载在PC 中。
_Startup:
LDHX #__SEG_END_SSTACK ; 初始化栈指针，__SEG_END_SSTACK 由链接器 TXS ; 定义。把H:X 的值传送到SP CLI ; enable interrupts
ORG $F000
_my_init:
F000 AD 02 BSR sub_dummy ; 调用子程序sub_dummy
return_address: ; 从调用返回的地址，0xF002
F002 A6 55 LDA #$55
; ......
sub_dummy: ; 子程序入口地址，0xF004
F004 9D NOP ; 进入后，0xF002被压入栈中
F005 81 RTS ; 从子程序返回，0xF002装载到PC中
正如前面所言，SP永远指向下一个可用的内存单元。栈在物理上是RAM的一部分，在系统初始化的时候，应该定空间，即指定SP的初始值和栈的大小。在前面我们看到如何初始化栈指针的例子，栈空间大小则应该在链接器参数文件（PRM）中定义：
STACKIZE0x50
那么栈被指定为从地址0x14F起，大小为0x50个byte的一段专有存储空间。当执行入栈指令时，入栈的值被保存在SP当前指向的单元中，然后SP自动减1（从而指向下一个可用单元）。出栈指令则先把SP加1，使其指向最后一个有效数据的保存地址，然后把这个数据弹出给目标地址。实际上，数据出栈后，原来的地址单元中的数据仍然存在，直到下次入栈的时候会被新数据覆盖。所以，栈空间是从高地址到低地址“向上”增长的。这有点像一个单独的汉诺塔，最后放上去的盘子只能最先被取下来。
为了和HC05兼容，CPU08在复位后被设置为0x00FF——HC05的RAM 只有256bytes，栈从它的RAM的最高地址0x00FF开始“向上”生长。栈指针复位指令RSP也使SP被赋值为0x00FF。对于CPU08，这实际上是一个不合理的值，因为从0x0000到0x00FF的空间，是宝贵的“零页”区域，在这个空间进行寻址只需要一个byte就可以表示操作数的地址，即所谓的直接寻址（DIR），DIR寻址模式可以节省一个字节的指令长度和一个指令周期的执行时间。并且，在直接页面，位操作也可以直接进行。因此，用户程序应该重新初始化SP，一般来说，应该使SP指向RAM的最后一个（最高）地址。
下一个盘子只能放在这里最后放上去的盘子总是最先被取出
图2. 栈（Stack）和汉诺塔
主存空间的分配与回收— 首次适应法 This manuscript was revised by the office on December 10, 2020.
南通大学操作系统实验课 实验报告 学生姓名 所在院系 专业 学号 指导教师 南通大学 2014年 5 月 16 日主存空间的分配与回收 ——首次适应法 一、实验目的 主存是中央处理机能直接存取指令和数据的存储器，能否合理而有效地使用它，在很大程度上将影响整个计算机系统的性能。 本实验主要熟悉主存的管理方法以及相应的分配与回收算法。所谓分配，就是解决多道程序或多进程如何共享主存空间的问题，以便各个进程能获得所希望的主存空间，正确运行。所谓回收，就是当进程运行完成时，将其所占用的主存空间归还给系统。 二、实验要求 采用空闲区链法管理空闲区，并增加已分配区表。分配算法采用首次适应法。 三、设计思路： （1）采用空闲区链法管理空闲区，并增加已分配区表。分配算法采用首次适应法（内存空闲区的地址按照从小到大的自然顺序排列），实现内存的分配与回收。 （2）设计一个进程申请序列以及进程完成后的释放顺序，实现主存的分配与回收。
（3）进行分配时应该考虑这样3种情况：进程申请的空间小于、等于或大于系统空闲区的大小。回收时应该考虑这样4种情况：释放区上邻、下邻、上下都邻和都不邻接空闲区。 （4）每次的分配与回收都要求把记录内存使用情况的各种数据结构的变化情况以及各进程的申请、释放情况显示出来。 四、主要思想 （1）输入主存空间的最大长度n创建最大长度总和为n的若干空闲区的主存空闲区链； （2）输入待存作业的长度x，从链头开始找第一个合适作业的空闲区：分区长度小于x时，指针后移，继续寻找；分区长度等于x时，分配空间， 修改作业分区；分区长度大于x时，分配空间，修改分区数据。 五、流程图 1.空闲区链的首次适应算法分配流程图 2.空闲区链的首次适应算法回收流程图 六、调试结果 1.内存的分配 2.内存的回收 3.内存清空 七、总结与感悟 说实话我操作系统学得不是很好，一开始看到题目觉得自己要完成这个实验有些难度。好在老师提醒书上有另一道类似题目的程序代码，另外书上也有首次适应法的流程图，可以给我们一些提示。之后我也参考了网上的相关资料，看看别人是如何实现的，他们都是怎么样的思路和方法，与我一开始的想法相比，比我精妙在哪里。最后自己调试时，遇到了许许多多问题和错误，请教了学得比较好的同学、经过不断的修改和完善之后，终于做完实验。 这次的实验使我了解到，平时对知识的积累相当重要，同时也要注重课上老师的讲解，老师在课上的延伸是课本上所没有的，这些知识对于我们对程序的编写有很大的作用，同时，编程也要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。操作系统这门课不但重要而且十分有用，我一定要下功夫把这门课学好。
课程设计 题目：主存空间的分配与回收 学生姓名： 学院：信息工程学院 系别：计算机系 专业：计算机科学与技术 班级：计算机 指导教师：副教授 副教授 2011年月日 内蒙古工业大学课程设计任务书（三） 学院（系）：信息学院计算机系课程名称：操作系统课程设计指导教师（签名）：专业班级：计算机09-2 学生姓名：学号：
目录 第一章背景研究 (1) 1.1课题简介 (1) 1.2 设计要求 (1) 1.3概念原理 (1) 1.4 环境说明和使用工具 (2) 第二章详细设计 (2) 2.1功能介绍 (2) 2.1.1分配函数发fenpei()的执行过程（最佳适应算法） (2) 2.1.2回收进程空间所占的函数free()的执行过程 (2) 2.2函数的规格说明 (3) 2.2.1打印分配表空闲表函数 print() (3) 2.2.2为进程分配空间函数 fenpei(char *c, struct node *p,struct node *f) (3) 2.2.3回收进程所占空间函数struct node * free(char *c, struct node *p,struct node *f) (3) 2.3 主要数据结构 (3) 2.4 流程图 (5) 第三章核心算法的实现 (6) 3.1 分配函数 (6) 3.2回收函数 (11) 第四章测试 (15) 4.1 预测试 (15) 4.2 实际运行结果（截图） (16) 第五章总结 (18) 参考文献 (25)
第一章背景研究 1.1课题简介 操作系统是当代计算机软件系统的核心，是计算机系统的基础和支撑，它管理和控制着计算机系统中的所有软、硬件资源，可以说操作系统是计算机系统的灵魂。操作系统课程是计算机专业学生必须学习和掌握的基础课程, 是计算机应用人员深入了解和使用计算机的必备知识, 是进行系统软件开发的理论基础，也是计算机科学与技术专业的一门理论性和实践性并重的核心主干课程。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。 通过本次课程设计熟悉主存空间的分配与回收，所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时，将作业或进程所占用的主存空间归还给系统。采用可变式分区管理，使用最佳适应算法实现主存的分配与回收。深入研究此算法有助于我们全面的理解内存的分配原理，培养我们逻辑思维能力。 1.2 设计要求 设计多个作业或进程动态请求内存资源的模拟系统，使用最佳适应算法实现内存的分配与回收，实现可变式分区管理；设计相应的内存分配算法，定义相关数据结构，以及输出显示每次请求分配内存的结果和内存的已分配和未分配的状况。 1.3概念原理 可变式分区管理的原理：区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。这样就会出现空闲区与占用区相互交错的情况。这样就需要P 表，F表来分别表示内存的占用区状态与空闲区的状态。
操作系统内存管理
操作系统内存管理 1. 内存管理方法 内存管理主要包括虚地址、地址变换、内存分配和回收、内存扩充、内存共享和保护等功能。 2. 连续分配存储管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 2.1 单一连续存储管理 在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP／M和 DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求内
存空间少的程序，造成内存浪费；程序全部装入，使得很少使用的程序部分也占用—定数量的内存。 2.2 分区式存储管理 为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。 分区式存储管理引人了两个新的问题：内碎片和外碎片。 内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。
分区式存储管理常采用的一项技术就是内存紧缩(compaction)。 2.2.1 固定分区(nxedpartitioning)。 固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 优点：易于实现，开销小。 缺点主要有两个：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。 2.2.2动态分区(dynamic partitioning)。 动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎
实验五可变分区存储管理方式的内存分配和回收 一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验属性 设计 三．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 四．实验背景材料 实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。 首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #define n 10 //假定系统允许的最大作业数量为n struct { float address; //已分分区起始地址 float length; //已分分区长度、单位为字节 int flag; //已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n]; //已分分区表 “空闲区表”的结构定义 #define m 10 //假定系统允许的空闲区最大为m struct
写代码的时候会碰到多维数组的内存分配和释放问题，在分配和释放过程中很容易出现错误。下面贴上一些示例代码，以供参考。 如果要给二维数组(m*n)分配空间，代码可以写成下面： char **a, i; // 先分配m个指针单元，注意是指针单元 // 所以每个单元的大小是sizeof(char *) a = (char **)malloc(m * sizeof(char *)); // 再分配n个字符单元， // 上面的m个指针单元指向这n个字符单元首地址 for(i = 0; i < m; i++) a[i] = (char *)malloc(n * sizeof(char)); （注意红色部分） 释放应该是： int i; for(i=0;i a = (char ***)malloc(m * sizeof(char **)); for(i = 0; i < m; ++i) a[i] = (char **)malloc(n * sizeof(char *)); for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) a[i][j] = (char *)malloc(p * sizeof(char)); 释放代码为逆过程，具体代码为： int i,j,; for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) free((void *)a[i][j]); for(i = 0; i < m; ++i) free((void *)a[i]); free((void *)a); 三维以上的多维数组的分配和释放，原理与上面的一样。 （转） C中如何为第二维长度固定的二维数组分配内存 实验四存分配算法 1.实验目的 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。 背景知识： 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。 2.实验容 采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。 由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。（即输出当时的空闲区说明表及其存分配表） 利用VC++6.0实现上述程序设计和调试操作。 3.实验代码 #include 浅析动态内存分配及Malloc/free的实现2011-03-18 22:47一、概述： 动态内存分配，特别是开发者经常接触的Malloc/Free接口的实现，对许多开发者来说，是一个永远的话题，而且有时候也是一个比较迷惑的问题，本文根据自己的理解，尝试简单的探究一下在嵌入式系统中，两类典型系统中动态内存分配以及Malloc/Free的实现机制。 二、内存分配方式 Malloc/Free主要实现的是动态内存分配，要理解它们的工作机制，就必须先了解操作系统内存分配的基本原理。 在操作系统中，内存分配主要以下面三种方式存在： （1）静态存储区域分配。内存在程序编译的时候或者在操作系统初始化的时候就已经分配好，这块内存在程序的整个运行期间都存在，而且其大小不会改变，也不会被重新分配。例如全局变量，static变量等。 （2）栈上的内存分配。栈是系统数据结构，对于进程/线程是唯一的，它的分配与释放由操作系统来维护，不需要开发者来 [url=javascript:;]管理[/url] 。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时，这些存储单元会被自动释放。栈内存分配运算内置于处理器的指令集中，效率很高，不同的操作系统对栈都有一定的限制。 （3）堆上的内存分配，亦称动态内存分配。程序在运行的期间用malloc申请的内存，这部分内存由程序员自己负责管理，其生存期由开发者决定：在何时分配，分配多少，并在何时用free来释放该内存。这是唯一可以由开发者参与管理的内存。使用的好坏直接决定系统的性能和稳定。 三、动态内存分配概述 首先，对于支持虚拟内存的操作系统，动态内存分配(包括内核加载,用户进程加载,动态库加载等等)都是建立在操作系统的虚拟内存分配之上的，虚拟内存分配主要包括： 1、进程使用的内存地址是虚拟的(每个进程感觉自己拥有所有的内存资源)，需要经过页表的映射才能最终指向系统实际的物理地址。 2、主内存和磁盘采用页交换的方式加载进程和相关数据，而且数据何时加载到主内存，何时缓存到磁盘是OS调度的，对应用程序是透明的。 3、虚拟存储器给用户程序提供了一个基于页面的内存大小，在32位系统中，用户可以页面大小为单位，分配到最大可以到4G(内核要使用1G或2G等内存地址)字节的虚拟内存。 4、对于虚拟内存的分配，操作系统一般先分配出应用要求大小的虚拟内存，只有当应用实际使用时，才会调用相应的操作系统接口，为此应用程序分配大小以页面为单位的实际物理内存。 5、不是所有计算机系统都有虚拟内存机制，一般在有MMU硬件支持的系统中才有虚拟内存的实现。许多嵌入式操作系统中是没有虚拟内存机制的，程序的动态分配实际是直接针对物理内存进行操作的。许多典型的实时嵌入式系统如Vxworks、Uc/OS 等就是这样。 四、动态内存分配的实现 由于频繁的进行动态内存分配会造成内存碎片的产生，影响系统性能，所以在不同的系统中，对于动态内存管理，开发了许多不同的算法（具体的算法实现不想在这里做详细的介绍，有兴趣的读者可以参考Glib C 的源代码和附录中的资料）。不同的操作系统有不同的实现方式，为了程序的可移植性，一般在开发语言的库中都提供了统一接口。对于C语言，在标准C库和Glib 中，都实现了以malloc/free为接口的动态内存分配功能。也就是说，malloc/free库函索包装了不同操作系统对动态内存管理的不同实现，为开发者提供了一个统一的开发环境。对于我们前面提到的一些嵌入式操作系统，因为实时系统的特殊要求（实 操作系统实验 内存的分配与回收 实验报告 一、实验题目：内存的分配与回收 二、实验内容：利用可变分区的首次适应算法，模拟内存的分配与回收。 三、实验目的：掌握可变分区首次适应算法的原理以及其编程实现。 四、实验过程： 1、基本思想：可变分区分配是根据进程的实际需求，动态地为之分配内存空间。首次适应算法要求空闲空间链以地址递增的次序链接。进行内存分配时，从链表头部开始依次检索，找到第一个不小于请求空间大小的空闲空间进行分配。分配时需考虑碎片问题，若分配会导致碎片产生则将整块分区分配。内存的回收需要考虑四种情况：⑴回收分区前后两个分区都空闲，则需要和前后两个分区合并；（2）回收分区只有前一分区空闲，则与前一分区合并；（3）回收分区只有后一分区空闲，则和后一分区合并；（4）回收分区独立，不考虑合并 。 2、主要数据结构： struct FreeArea{ 链结点包含的数据：分区号、大小、起址、标记 i nt ID; i nt size; l ong address; i nt sign; }; struct Node { 双链表结点结构体：数据区、前向指针、后继指针 F reeArea data; s truct Node *prior; s truct Node *next; }*DLinkList; 3、输入、输出： 输入： I.内存分配时由键盘输入分区ID和大小； II.内存回收时由键盘输入需要回收的分区ID； 输出：输出内存的分配情况（按照地址从低到高） 4、程序流程图： 5、实验结果截屏： 6、源程序代码： #include 西安邮电大学 （计算机学院） 课内实验报告 实验名称：内存管理 专业名称：软件工程 班级： 学生姓名： 学号（8位）： 指导教师： 实验日期： 实验五：进程 1.实验目的 通过深入理解区管理的三种算法，定义相应的数据结构，编写具体代码。充分模拟三种算法的实现过程，并通过对比，分析三种算法的优劣。 （1）掌握内存分配FF，BF，WF策略及实现的思路； （2）掌握内存回收过程及实现思路； （3）参考给出的代码思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。 2.实验要求： 1）掌握内存分配FF，BF，WF策略及实现的思路； 2）掌握内存回收过程及实现思路； 3）参考本程序思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。 3.实验过程： 创建进程： 删除其中几个进程：(默认以ff首次适应算法方式排列) Bf最佳适应算法排列方式： wf最差匹配算法排列方式： 4.实验心得： 这次实验实验时间比较长，而且实验指导书中对内存的管理讲的很详细，老师上课的时候也有讲的很详细，但是代码比较长，刚开始的时候也是不太懂，但是后面经过和同学一起商讨，明白几种算法的含义： ①首次适应算法。在采用空闲分区链作为数据结构时，该算法要求空闲分区链表以地址递增的次序链接。在进行内存分配时，从链首开始顺序查找，直至找到一个能满足进程大小要求的空闲分区为止。然后，再按照进程请求内存的大小，从该分区中划出一块内存空间分配给请求进程，余下的空闲分区仍留在空闲链中。 ②循环首次适应算法。该算法是由首次适应算法演变而形成的，在为进程分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给进程。 ③最佳适应算法将空闲分区链表按分区大小由小到大排序，在链表中查找第一个满足要求的分区。 ④最差匹配算法将空闲分区链表按分区大小由大到小排序，在链表中找到第一个满足要求的空闲分区。 实验中没有用到循环首次适应算法，但是对其他三种的描述还是很详细，总的来说，从实验中还是学到了很多。 5.程序源代码： #include 《动态分配内存与数据结构》习题 学号姓名 一、选择题 1、是一种限制存取位置的线性表，元素的存取必须服从先进先出的规则。 A．顺序表B．链表C．栈D．队列 2、是一种限制存取位置的线性表，元素的存取必须服从先进后出的规则。 A．顺序表B．链表C．栈D．队列 3、与顺序表相比，链表不具有的特点是。 A．能够分散存储数据，无需连续内存空间 B．插入和删除无需移动数据 C．能够根据下标随机访问 D．只要内存足够，没有最大长度的限制 4、如果通过new运算符动态分配失败，返回结果是。 A．-1 B．0 C．1D．不确定 5、实现深复制中，不是必须自定义的。 A．构造函数B．复制构造函数 C．析构函数D．复制赋值操作符函数 6、分析下列代码是否存在问题，选择合适的选项：。 int main(void) { int *p = new int [10]; p = new int [10]; delete [] p; p = NULL; return 0; } A．没有问题 B．有内存泄漏 C．存在空悬指针 D．存在重复释放同一空间 7、通过new运算符动态分配的对象，存储于内存中的。 A．全局变量与静态变量区 B．代码区 C．栈区 D．堆区 8、下列函数中，可以是虚函数。 A．构造函数 B．析构函数 C．静态成员函数 D．友元函数 9、关于通过new运算符动态创建的对象数组，下列判断中是错误的。 A. 动态创建的对象数组只能调用默认构造函数 B. 动态创建的对象数组必须调用delete []动态撤销 C. 动态创建的对象数组的大小必须是常数或常变量 D. 动态创建的对象数组没有数组名 10、顺序表不具有的特点是 A. 元素的存储地址连续 B. 存储空间根据需要动态开辟，不会溢出 C. 可以直接随机访问元素 D. 插入和删除元素的时间开销与位置有关 11、假设一个对象Ob1的数据成员是指向动态对象的指针，如果采用浅复制的方式复制该对象得到对象Ob2，那么在析构对象Ob1和对象Ob2时会的问题。 A. 有重复释放 B. 没有 C. 内存泄漏 D. 动态分配失败 12、假设对5个元素A、B、C、D、E进行压栈或出栈的操作，压栈的先后顺序是ABCDE，则出栈的先后顺序不可能是。 A. ABCDE B. EDCBA C. EDBCA D. BCADE 13、假设对4个元素A、B、C、D、E进行压栈或出栈的操作，压栈的先后顺序是ABCD，则出栈的先后顺序不可能是。 A. ABCD B. DCBA C. BCAD D. DCAB 14、通过new运算符动态创建的对象的存放在中。 A. 代码区 B. 栈区 C. 自由存储区 D. 全局数据区 15、链表不具有的特点是。 A. 元素的存储地址可以不连续 B. 存储空间根据需要动态开辟，不会溢出 C. 可以直接随机访问元素 D. 插入和删除元素的时间开销与位置无关 16、有关内存分配和释放的说法，下面当中错误的是 A．new运算符的结果只能赋值给指针变量 B．动态创建的对象数组必须调用delete []动态撤销 C．用new分配的空间位置是在内存的栈区 D．动态创建的对象数组没有数组名 17、关于栈，下列哪项不是基本操作 A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．把栈置空 18、关于链表，说法错误的是 内核态与用户态是操作系统的两种运行级别，intel cpu提供Ring0-Ring3三种级别的运行模式。Ring0级别最高，Ring3最低。 当一个任务(进程)执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态(或简称为内核态)。此时处理器处于特权级最高的(0级) 内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。当进程在执行用户自己的代码时，则称其处于用户运行态(用户态)。即此时处理器在特权级最低的(3级)用户代码中运行。 在内核态下CPU可执行任何指令，在用户态下CPU只能执行非特权指令。当CPU处于内核态，可以随意进入用户态；而当CPU处于用户态时，用户从用户态切换到内核态只有在系统调用和中断两种情况下发生，一般程序一开始都是运行于用户态，当程序需要使用系统资源时，就必须通过调用软中断进入内核态。 现象 1 压力测试过程中，发现被测对象性能不够理想，具体表现为： 进程的系统态CPU消耗20，用户态CPU消耗10，系统idle大约70 2 用ps -o majflt,minflt -C program命令查看，发现majflt每秒增量为0，而minflt每秒增量大于10000。 初步分析 majflt代表major fault，中文名叫大错误，minflt代表minor fault，中文名叫小错误。 这两个数值表示一个进程自启动以来所发生的缺页中断的次数。 当一个进程发生缺页中断的时候，进程会陷入内核态，执行以下操作： 检查要访问的虚拟地址是否合法 查找/分配一个物理页 填充物理页内容（读取磁盘，或者直接置0，或者啥也不干） 建立映射关系（虚拟地址到物理地址） 重新执行发生缺页中断的那条指令 如果第3步，需要读取磁盘，那么这次缺页中断就是majflt，否则就是minflt。 此进程minflt如此之高，一秒10000多次，不得不怀疑它跟进程内核态cpu消耗大有很大关系。 分析代码 查看代码，发现是这么写的：一个请求来，用malloc分配2M内存，请求结束后free这块内存。看日志，发现分配内存语句耗时10us，平均一条请求处理耗时1000us 。原因已找到！ 虽然分配内存语句的耗时在一条处理请求中耗时比重不大，但是这条语句严重影响了性能。要解释清楚原因，需要先了解一下内存分配的原理。 内存分配的原理 从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap （不考虑共享内存）。brk是将数据段(.data)的最高地址指针_edata往高地址推，mmap是在进程的虚拟地址空间中（一般是堆和栈中间）找一块空闲的。这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。 计算机操作系统内存分配实验报告记录 ————————————————————————————————作者：————————————————————————————————日期： 一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。 设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明 实习四 主存储器空间的分配和回收 一、实习内容 主存储器空间的分配和回收。 二、实习目的 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实习帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 三、实习题目 本实习模拟在两种存储管理方式下的主存分配和回收。 第一题：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。 [提示]： 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如： 为了 说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下： 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用 来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。 (2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。 (3) 采用最先适应算法（顺序分配算法）分配主存空间。 按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实习是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。 (4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。 (5) 请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。 第二题：在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。 [提示]： (1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。 (2) 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存 主存空间的分配与回收实验报告 实验报告 课程名称：操作系统 实验名称：主存空间的分配与回收学号： 110310014 学生姓名：于钊 班级：信管1101班 指导教师：吴联世 实验日期： 2013 年12月5日 3、采用最先适应算法（顺序分配算法）分配主存空间。 按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。 4、当一个作业执行完成撤离时，作业所占的分区应该归还给系统，归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在上述中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。 2）程序结构（流程图） 首次适应分配模拟算法 主存回收算法 3）实现步骤 实现动态分区的分配与回收，主要考虑三个问题：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。 1．设计记录主存使用情况的数据表格 由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时，空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区贬词空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配与回收主要时对空闲区的操作。这样为了便于对主存空间的分配与回收，就建立两张分区表记录主存的使用情况：“已分配区表”记录作业占用分区，“空闲区表”记录空闲区。 这两张表的实现方法一般由两种：链表形式、顺序表形式。在本实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因此在多数情况下，无论是“已分配表区”还是“空闲区表”都是空闲栏目。已分配区表中除了分区起始地址、长度 精心整理西安邮电大学 （计算机学院） 课内实验报告 1. （1 （2 （3 原因，写出实验报告。 2.实验要求： 1）掌握内存分配FF，BF，WF策略及实现的思路； 2）掌握内存回收过程及实现思路； 3）参考本程序思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。 3.实验过程： 创建进程： 删除其中几个进程：(默认以ff首次适应算法方式排列) Bf最佳适应算法排列方式： wf最差匹配算法排列方式： 4.实验心得： 明 实验中没有用到循环首次适应算法，但是对其他三种的描述还是很详细，总的来说，从实验中还是学到了很多。 5.程序源代码： #include #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 /*描述每一个空闲块的数据结构*/ struct free_block_type { }; /* /* { }; /* /* void display_menu(); int set_mem_size(); void set_algorithm(); void rearrange(int algorithm); int rearrange_WF(); int rearrange_BF(); int rearrange_FF(); int new_process(); int allocate_mem(struct allocated_block *ab); 动态内存申请与释放 （1）malloc方式 申请一维内存时，格式为： 类型表示符*变量名； 变量名= （类型标识符*）malloc(sizeof(类型标识符)*数组大小)； 在使用完该方式申请的内存后，必须用free()函数及时释放，格式为：free(变量名) 变量名= NULL； 当申请二维内存时，格式为： 类型标识符**变量名； 变量名= （类型标识符**）malloc（sizeof（类型标识符*）*数组行大小）； for(int i=0;i<数组行大小；i++) 变量名[i] = (类型标识符*)malloc(sizeof(类型标识符)*数组列大小)；释放格式： free（变量名）； 变量名= NULL； （2）new方式 当申请一维内存时，格式为： 类型标识符*变量名； 变量名= new 类型标识符[数组大小]； 使用该方式申请的内存后，必须用delete()函数及时释放格式： delete[] 变量名； 变量名= NULL； 当申请二维内存时，格式为： 类型标识符**变量名； 变量名= new 类型标识符*[数组行大小]； for(int i=0;i<数组行大小；i++) 变量名[i] = new 类型标识符[数组列大小]; 释放格式： delete[] 变量名； 变量名= NULL； 例子： 申请二维内存 代码： 1 #include 8 int col = 2; 9 cout<<"please input row:"<操作系统内存动态分配模拟算法
using namespace std; //定义存的大小 const int SIZE=64; //作业结构体，保存作业信息 struct Project{ int number; int length; }; //存块结构体，保存存块信息 struct Block{
动态内存分配
操作系统之内存分配与回收
操作系统实验内存分配
《动态分配内存与数据结构》课后习题
频繁分配释放内存导致的性能问题分析
计算机操作系统内存分配实验报告记录
内存的申请与释放
主存空间的分配与回收实验报告
操作系统实验内存分配
动态内存申请与释放
相关主题
文本预览