鸿 网 互 联 www.68idc.cn

当前位置 : 主页 > 网络技术 > 路由器 > >

由swap看变量在内存中的分配

来源:互联网 作者:佚名 时间:2015-10-09 08:38
在排序问题中,我们必不可少的会用到交换操作。针对不同的语言,处理方式有所不同:或者单独写一个swap函数,或者直接在排序函数中实现交换操作。采用swap函数大多数人肯定会遇到不能交换的问题,其中的原理大家也应该都很清楚:swap函数交换的是局部变量,话

 

    在排序问题中,我们必不可少的会用到交换操作。针对不同的语言,处理方式有所不同:或者单独写一个swap函数,或者直接在排序函数中实现交换操作。采用swap函数大多数人肯定会遇到不能交换的问题,其中的原理大家也应该都很清楚:swap函数交换的是局部变量,话虽如此,但具体的机制其实远不是如此简单。

   要真正理解这个问题,就需要从程序的运行时刻环境来解释。一个程序在运行时内存会被划分成几部分:代码区、数据区、堆区和栈区。

    生成的目标代码的大小在编译时刻就已经固定下来了,因此编译器可以将可执行目标代码放在一个静态确定的代码区。这个区通常位于存储的低端。类似地,程序的某些数据对象的大小或者全局变量可以在编译时刻知道,它们可以被放置在另一个称为静态区的区域中,该区域可以被静态确定。放置在这个区域的数据对象进行静态分配,是因为这些对象的地址可以被编译到目标代码中。

   为了将运行时刻的空间利用率最大化,另外两个区域-----栈和堆被放在剩余地址空间的相对两端。这些区域是动态的,它们的大小会随着程序运行而改变。这两个区域根据需要向对方增长。栈区用来存放称为活动记录的数据结构,这些活动记录在函数调用过程中生成。有些数据的生命周期要比创造它的某此过程调用更长,这些数据通常被分配在堆区。局部变量在栈区中分配,和活动记录密切相关,所以我们只关注栈区。

   当一个方法被调用时,编译器会为其在栈区中分配一块空间,作为该方法的活动记录。活动记录中包括方法的形式参数,局部变量等数据以及方法结束时的返回地址。在该方法的生命周期中,其操作除了涉及全局的访问之外都在该空间中。活动记录的分配是随着程序的运行而逐渐分配和回收的:遇到方法调用即为该方法分配空间创建活动记录,方法结束则回收空间。

下面以用C语言写的冒泡排序为例来分析活动记录的构造。源代码BubbleSort.c为:

#include<stdio.h>
void swap(int*a,int* b)//正确的交换函数
{
         int temp=*a;
         *a=*b;
         *b=temp;
}
void swaps(inta,int b)//错误的交换函数
{
         int temp=a;
         a=b;
         b=temp;
}
voidBubbleSort(int a[],int length)
{
         int i,j;
         for(i=length-1;i>1;i--)
         {
                   for(j=0;j<i;j++)
                   {
                            if(a[j]>a[j+1])swap(&a[j],&a[j+1]);                    
                   }
         }
}
int main()
{
         int a[10];
         int i;
         for(i=0;i<10;i++)
         {
                   a[i]=rand()%100;
         }
         printf("---------------------------------------/n");
         for(i=0;i<10;i++)
         {
                   printf("%d ",a[i]);
         }
         printf("/n");
         BubbleSort(a,10);
         printf("---------------------------------------/n");
         for(i=0;i<10;i++)
         {
                   printf("%d ",a[i]);
         }
         printf("/n");
}

         用命令gcc –S BubbleSort.c生成源文件的部分汇编代码为:(注:此为AT&T汇编,源操作数和目的操作数与Intel汇编相反,细节请自行查阅)

         .file  "BubbleSort.c"
         .text
.globl swap
         .type         swap, @function
swap:
         pushl         %ebp                             ;%ebp保存父函数活动记录的基地址
         movl          %esp, %ebp                  ; %esp为当前函数活动记录基地址,保存在%ebp中
         subl  $16, %esp                               ;为当前函数的活动记录分配空间为16字节
         movl          8(%ebp), %eax             ;将&a存入eax
         movl          (%eax), %eax                ;将*a存入eax,我们可以看出指针操作就是间接寻址
         movl          %eax, -4(%ebp)             ;将eax的值存入temp(temp=*a)
         movl          12(%ebp), %eax            ;将&b存入eax
         movl          (%eax), %edx                ;将*b存入edx
         movl          8(%ebp), %eax              ;将&a存入eax
         movl          %edx, (%eax)                 ;将edx存入eax所指内存单元(*a=*b)
         movl          12(%ebp), %eax             ;将&b存入eax
         movl          -4(%ebp), %edx             ;将temp存入edx
         movl          %edx, (%eax)                 ;将edx存入eax所指内存单元(*b=*temp)
         leave
         ret
         .size swap, .-swap
 
.globl BubbleSort
         .type         BubbleSort, @function
BubbleSort:
         pushl         %ebp
         movl          %esp, %ebp
         subl  $24, %esp
         movl          12(%ebp), %eax             ;将length放到eax中
         subl  $1, %eax                                  ;eax=length-1
         movl          %eax, -4(%ebp)             ;i=length-1
         jmp  .L6
.L10:
         movl          $0, -8(%ebp)                  ;j=0
         jmp  .L7
.L9:
         movl          -8(%ebp), %eax            ;将j移到eax中
         sall   $2, %eax                                 ;将j扩大四倍
         addl 8(%ebp), %eax                       ;将数组的指针指向元素a[j],并将值放入eax
         movl          (%eax), %edx                ;将a[j]放到edx中
         movl          -8(%ebp), %eax             ;将j移到eax中
         addl $1, %eax                                 ;j=j+1
         sall   $2, %eax                                 ;将j扩大四倍
         addl 8(%ebp), %eax                       ;将数组指针指向下一个元素a[j+1],并将值放入eax
         movl          (%eax), %eax                ;将a[j+1]放到eax中
         cmpl          %eax, %edx                   ;比较a[j]和a[j+1]
         jle     .L8
         movl          -8(%ebp), %eax
         addl $1, %eax
         sall   $2, %eax
         movl          %eax, %edx
         addl 8(%ebp), %edx
         movl          -8(%ebp), %eax
         sall   $2, %eax
         addl 8(%ebp), %eax
         movl          %edx,4(%esp)               ;将edx (a[j])存入为swap的形式变量b分配的空间
         movl          %eax,(%esp)                 ;将eax(a[j+1])存入为swap的形式变量a分配的空间
         call   swap
.L8:
         addl $1, -8(%ebp)
.L7:
         movl          -8(%ebp), %eax
         cmpl          -4(%ebp), %eax
         jl       .L9
         subl  $1, -4(%ebp)
.L6:
         cmpl          $1, -4(%ebp)
         jg      .L10
         leave
         ret

     下面以swap函数的汇编代码来分析活动记录。在一般的机器中,栈都是由高地址向低地址变化,当执行swap时,由高地址向低地址为其形式参数和局部变量分配空间。首先是形式参数,在执行swap之前,编译器会按照输入参数的反向顺序为形式参数分配空间,我们所说的局部变量其实就是指的这个为形式参数分配的空间。函数执行分配空间,执行完毕释放空间,这就是局部变量的含义。然后再进入swap函数体,进入函数体第一步就是存函数的返回地址,这个过程由编译器隐式完成,在汇编代码中不存在。然后执行一个例程(the procedureprolog):pushl  %ebp   movl  %esp, %ebp,这两句的作用是保存调用者的活动记录的初始地址,当函数返回时,可以正确的跳到父函数的活动记录。最后才是为函数swap的局部变量分配空间。该空间的分配应该是采用回填方式分配,并不局限于函数中声明的变量个数,而是函数用到的空间。这些空间构成了swap函数的活动记录。

     通过分析汇编代码,我们可以明白为什么基本类型做形参的swap函数不起作用,而指针的swap函数可以实现交换功能。我们在执行swap函数时,编译器会为该方法分配一部分空间,将形式参数放在这个空间中,而这个空间是和方法调用时的实参空间不同的,所以我们所有的修改就不会触及到实参。虽说swap结束后,形参的空间还存在,但是我们在高级语言级无法访问,也就无法获得swap交换之后的值。

     基本类型不行,但是为什么指针就可以呢?虽说swap保存的不是实际的值,但是保存了实际变量的指针,这就意味着我们可以通过指针修改实参。象Java这种高级语言没有指针,怎样实现两数交换,一般可以采用的策略是将要交换的数声明为类的实例变量,这样就可以进行交换了。

     至此,我们已经对swap函数的原理有了比较深刻的认识。我们不妨再深一步,对C语言的变量布局再通过实例分析一下:

#include<stdio.h>
#define N 10
int a,b[N],*p;//全局变量
int add(inta,int b)
{
         return a+b;
}
int main()
{
         int a=3;//局部变量
         a=add(a,a);
         printf("a=%d/n",a);
}

汇编代码为:

         .file  "test.c"
         .comm      a,4,4                                 ;全局变量会单独存放,放在静态区
         .comm      b,40,32
         .comm      p,4,4
         .text
.globl add
         .type         add,@function
add:
         pushl         %ebp
         movl          %esp,%ebp
         movl          12(%ebp),%eax
         movl          8(%ebp),%edx
         leal   (%edx,%eax),%eax                 ;AT&T汇编,实现相加功能,将返回值放在eax中
         popl %ebp
         ret
         .size add,.-add
         .div    .rodata
.LC0:
         .string      "a=%d/n"                            ;字符串也会特殊处理
         .text
.globl main
         .type         main,@function
main:
         pushl         %ebp
         movl          %esp,%ebp
         andl $-16,%esp
         subl  $32,%esp
         movl          $3,28(%esp)             ;局部变量a放在28(%esp),属于main的活动记录
         movl          28(%esp),%eax
         movl          %eax,4(%esp)
         movl          28(%esp),%eax
         movl          %eax,(%esp)
         call   add
         movl          %eax,28(%esp)        ;从eax中读取函数的返回值,返回值不单独分配空间
         movl          $.LC0,%eax
         movl          28(%esp),%edx
         movl          %edx,4(%esp)
         movl          %eax,(%esp)
         call   printf
         leave
         ret

     我们由swap函数遇到的问题入手,来分析C语言变量的分配问题,其他高级语言也有类似的特点。希望通过该文章,大家对底层变量的分配和高级语言之间的关系能更加了解。

 

网友评论