精华内容
下载资源
问答
  • 千次阅读 2020-12-08 17:06:42
    当我们添加或者删除元素的时候,只能从栈顶操作。 上图就是一个里面有三个元素。其中 3 号元素是栈顶,1 号元素底。只有当前元素是栈顶的时候才能出栈。所以上图只有 3 号元素可以出栈。如果 3 号元素出栈...

    ​ 栈是一种“先进后出”的线性数据结构。栈只有一端能够进出元素。能进出元素的一端叫栈顶,不能进出元素的一端叫栈底。当我们添加或者删除元素的时候,只能从栈顶操作。

    image-20201205151854875

    上图就是一个栈,栈里面有三个元素。其中 3 号元素是栈顶,1 号元素栈底。只有当前元素是栈顶的时候才能出栈。所以上图只有 3 号元素可以出栈。如果 3 号元素出栈,那么栈顶就会变成 2 号元素。

    我们也可以用数组来模拟栈:

    • 定义数组和栈顶元素的位置,1 为栈底 : int stack[SIZE], top = 0;
    • 入栈 x : stack[++top] = x
    • 访问栈顶元素: stack[top]
    • 出栈: top--

    一开始栈里面没有元素,所以 top 的值是 0top 可以代表栈顶所在的位置,也可以代表栈里面有多少个元素。

    访问栈顶元素的时候,需要提前判断一下栈里面有没有元素,如果有才能返回栈顶元素。

    例题

    ​ 实现一个栈,支持 Push(入栈)、Pop(出栈)和 GetMax (查询栈内元素的最大值)三个操作,要求时间复杂度均为 O(1).

    思路:

    ​ 要求时间复杂度为O(1), 所以每 Push 一个元素的时候就要立刻知道最大值,所以我们可以定义一个变量 y 来表示当前栈里面元素的最大值,如果有元素进来,就可以和 y 比较一下,取最大就可以了。

    image-20201205154625263

    ​ 具体来说,就是维护两个栈,栈 A 存储原本的数据,栈 B 存储栈 A 中以栈底开头的每段数据的最大值。如上图所示:

    ​ 当执行 Push(y) 的时候,在 A 中插入 y,在 B 中插入 max(y, B的栈顶数据)。在执行Pop操作时,在 A、B 两个栈中分别出栈。在执行 GetMax 操作时,取出 B栈的栈顶元素就可以了。

    class Stack {
    public:
        Stack() {
        	top = 0;  // 一开始栈为空, 所以 top = 0.
        }
        void Push(int value) {  
        	A[++top] = value; // 首先把元素放到 A 栈里面。
        	B[top] = value;   // 直接放到 B 栈里面。 
        	if (top - 1 > 0) B[top] = max(B[top], B[top - 1]); // 如果之前 B 栈有元素, 那么比较一下,取个最大值。
        }
        
        void Pop() {
        	if (top > 0) --top;  // 元素个数减一。
        }
        int GetMax(){
        	return B[top]; // 取出最大的值,去之前需要判断一下栈里面有没有元素,这里我没有写。
        }
        int A[SIZE];  // A 栈
        int B[SIZE];  // B 栈
        int top;      // 栈顶元素的位置, 即栈内元素的个数。 
    };
    

    单调栈

    单调栈内的元素是递增或者递减的。

    单调栈的作用:

    • 求左面第一个大于或者小于当前元素的位置
    • 求右面第一个大于或者小于当前元素的位置

    例题:

    ​ 一个数组 arr, 有 n 个数字, 对于每个位置的数字,求左边第一个小于当前数字的位置。

    示例:

    输入: arr = [2, 4, 6, 5, 3, 1, 8]
    输出: [-1, 0, 1, 1, 0, -1, 5]
    

    如果是暴力, 那就对每一个位置 i, 然后向前找,遇到大于等于当前数的接着找,直到找到一个小于的位置 j。

    int n = arr.size(); // 数组大小
    for (int i = 0; i < n; ++i){  // 枚举每一个值
        int pos = -1; // 初始化位置, 如果找不到就是 -1
        for (int j = i-1; j >= 0; --j){  // 枚举小于 i 的所有位置,一旦出现小于当前值的位置,就记录下来然后退出。
            if (arr[j] < arr[i]) {
                pos = j;
                break;
            }
        }
        ans.push_back(pos); // 记录答案
    }
    

    这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2) 的。一点都不优雅,下面我们来了解一下更优雅的单调栈做法:

    ​ 对于 ii-1 这两个位置。i 可以复用 i-1 的情况。如果 arr[i] > arr[i-1], 那么 i 这个位置的答案就是 i-1, 否则 i 就要向前找,这个时候 i 就可以复用 i-1 的情况了, 因为 i-1 跳过的值就是 >= arr[i-1] 的, arr[i-1] >= a[i],所以 跳过的值必然也是 >= arr[i] 的, 所以这些值也就可以直接跳过。

    ​ 知道了上面的流程,就可以来了解怎么使用单调栈了。

    ​ 栈里面维护的是每个值的位置。当加入一个新值的时候,用新值不断的和栈顶代表的元素进行比较,如果新值大于栈顶,那么栈顶就是我们要找的位置, 否则就是新值小于等于栈顶所代表的数字,那么栈顶就要出栈。新值接着和栈顶进行下一次的比较。直到新值大于栈顶或者栈里面没有数字了。

    ​ 上面的步骤结束之后,记录答案,然后让新值的位置进栈,

    总结一下就是: 每个值进栈的时候,都会弹掉前面那些大于等于自己的数字。

    由于每个值最多进栈一次,出栈一次,所以时间复杂度是 O ( n ) O(n) O(n)

    下面就是具体的代码:

    stack<int>stk;
    int sz = arr.size();
    for (int i = 0; i < sz; ++i){
       while(stk.size() && arr[i] <= arr[stk.top()]) stk.pop(); // 如果当前的值 小于等于栈顶所代表的值, 就不断的弹栈,直到遇见大于当前的值
       L[i] = stk.size() ? stk.top() : -1;   // L 记录的是答案, 如果栈里面有值,记录的是栈顶的值,否之是 -1. 
       stk.push(i);  // 把当前位置压栈。
    }
    

    总的来说,单调栈是很好写的,我们也不需要知道这个栈是单调递增的还是单调递减的,只需要关心我们的目的就好了。是要求左边第一大于当前元素的位置还是左边第一个小于当前元素的位置。明确目的就可以直接写了。

    训练题目:

    展开全文
  • 堆和的精华大总结

    万次阅读 多人点赞 2019-11-18 18:37:41
    :存放基本类型的数据和对象的引用,但对象本身不存放在栈中,而是存放堆中 ◆堆:存放用new产生的数据 ◆静态域:存放对象中用static定义的静态成员 ◆常量池:存放常量 ◆非RAM存储:硬盘...

    Java内存分配原理

    栈、堆、常量池虽同属Java内存分配时操作的区域,但其适用范围和功用却大不相同。

    一般Java在内存分配时会涉及到以下区域:

    ◆寄存器:我们在程序中无法控制

    ◆栈:存放基本类型的数据和对象的引用,但对象本身不存放在栈中,而是存放在堆中

    ◆堆:存放用new产生的数据

    ◆静态域:存放在对象中用static定义的静态成员

    ◆常量池:存放常量

    ◆非RAM存储:硬盘等永久存储空间

    Java内存分配中的栈

    在函数中定义的一些基本类型的变量数据和对象的引用变量都在函数的栈内存中分配。
      
    当在一段代码块定义一个变量时,Java就在栈中 为这个变量分配内存空间,当该变量退出该作用域后,Java会自动释放掉为该变量所分配的内存空间,该内存空间可以立即被另作他用。

    Java内存分配中的堆

    堆内存用来存放由new创建的对象和数组。 在堆中分配的内存,由Java虚拟机的自动垃圾回收器来管理。

    在堆中产生了一个数组或对象后,还可以 在栈中定义一个特殊的变量,让栈中这个变量的取值等于数组或对象在堆内存中的首地址,栈中的这个变量就成了数组或对象的引用变量。  引用变量就相当于是 为数组或对象起的一个名称,以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。引用变量就相当于是为数组或者对象起的一个名称。

    引用变量是普通的变量,定义时在栈中分配,引用变量在程序运行到其作用域之外后被释放。而数组和对象本身在堆中分配,即使程序 运行到使用 new 产生数组或者对象的语句所在的代码块之外,数组和对象本身占据的内存不会被释放,数组和对象在没有引用变量指向它的时候,才变为垃圾,不能在被使用,但仍 然占据内存空间不放,在随后的一个不确定的时间被垃圾回收器收走(释放掉)。这也是 Java 比较占内存的原因。

    实际上,栈中的变量指向堆内存中的变量,这就是Java中的指针!


     
    常量池 (constant pool)

    常量池指的是在编译期被确定,并被保存在已编译的.class文件中的一些数据。除了包含代码中所定义的各种基本类型(如int、long等等)和对象型(如String及数组)的常量值(final)还包含一些以文本形式出现的符号引用,比如:

    ◆类和接口的全限定名;

    ◆字段的名称和描述符;

    ◆方法和名称和描述符。

    虚拟机必须为每个被装载的类型维护一个常量池。常量池就是该类型所用到常量的一个有序集和,包括直接常量(string,integer和 floating point常量)和对其他类型,字段和方法的符号引用。

    对于String常量,它的值是在常量池中的。而JVM中的常量池在内存当中是以表的形式存在的, 对于String类型,有一张固定长度的CONSTANT_String_info表用来存储文字字符串值,注意:该表只存储文字字符串值,不存储符号引 用。说到这里,对常量池中的字符串值的存储位置应该有一个比较明了的理解了。
    在程序执行的时候,常量池 会储存在Method Area,而不是堆中。

    堆与栈

    Java的堆是一个运行时数据区,类的(对象从中分配空间。这些对象通过new、newarray、 anewarray和multianewarray等指令建立,它们不需要程序代码来显式的释放。堆是由垃圾回收来负责的,堆的优势是可以动态地分配内存 大小,生存期也不必事先告诉编译器,因为它是在运行时动态分配内存的,Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是,由于要在运行时动态 分配内存,存取速度较慢。

    栈的优势是,存取速度比堆要快,仅次于寄存器,栈数据可以共享。但缺点是,存在栈中的数据大小与生存期必须是 确定的,缺乏灵活性。栈中主要存放一些基本类型的变量数据(int, short, long, byte, float, double, boolean, char)和对象句柄(引用)。

    栈有一个很重要的特殊性,就是存在栈中的数据可以共享。假设我们同时定义:

    1. int a = 3;   
    2. int b = 3;  

    编译器先处理int a = 3;首先它会在栈中创建一个变量为a的引用,然后查找栈中是否有3这个值,如果没找到,就将3存放进来,然后将a指向3。接着处理int b = 3;在创建完b的引用变量后,因为在栈中已经有3这个值,便将b直接指向3。这样,就出现了a与b同时均指向3的情况。

    这时,如果再令 a=4;那么编译器会重新搜索栈中是否有4值,如果没有,则将4存放进来,并令a指向4;如果已经有了,则直接将a指向这个地址。因此a值的改变不会影响 到b的值。

    要注意这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的,因为这种情况a的修改并不会影响到b, 它是由编译器完成的,它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态,会影响到另一个对象引用变量。

    String是一个特殊的包装类数据。可以用:

    1. String str = new String("abc");   
    2. String str = "abc";  

    两种的形式来创建,第一种是用new()来新建对象的,它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str,然后通过符号引用去字符串常量池 里找有没有"abc",如果没有,则将"abc"存放进字符串常量池 ,并令str指向”abc”,如果已经有”abc” 则直接令str指向“abc”。

    比较类里面的数值是否相等时,用equals()方法;当测试两个包装类的引用是否指向同一个对象时,用==,下面用例子说明上面的理论。

    String str1 = "abc";   
    String str2 = "abc";   
    System.out.println(str1==str2); //true  

    可以看出str1和str2是指向同一个对象的。

    String str1 =new String ("abc");   
    
    String str2 =new String ("abc");   
    
    System.out.println(str1==str2); // false  

    用new的方式是生成不同的对象。每一次生成一个。

    因此用第二种方式创建多个”abc”字符串,在内存中 其实只存在一个对象而已. 这种写法有利与节省内存空间. 同时它可以在一定程度上提高程序的运行速度,因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str = new String("abc");的代码,则一概在堆中创建新对象,而不管其字符串值是否相等,是否有必要创建新对象,从而加重了程序的负担。

    另 一方面, 要注意: 我们在使用诸如String str = "abc";的格式定义类时,总是想当然地认为,创建了String类的对象str。担心陷阱!对象可能并没有被创建!而可能只是指向一个先前已经创建的 对象。只有通过new()方法才能保证每次都创建一个新的对象。
     
    由于String类的immutable性质,当String变量需要经常变换 其值时,应该考虑使用StringBuffer类,以提高程序效率。
     
    1. 首先String不属于8种基本数据类型,String是一个对象。因为对象的默认值是null,所以String的默认值也是null;但它又是一种特殊的对象,有其它对象没有的一些特性。

    2. new String()和new String(”")都是申明一个新的空字符串,是空串不是null;

    3. String str=”kvill”;String str=new String (”kvill”)的区别

    示例:

    String s0="kvill";   
    
    String s1="kvill";   
    
    String s2="kv" + "ill";   
    
    System.out.println( s0==s1 );   
    
    System.out.println( s0==s2 );  

    结果为:

    true 
    true

    首先,我们要知结果为道Java 会确保一个字符串常量只有一个拷贝。

    因为例子中的 s0和s1中的”kvill”都是字符串常量,它们在编译期就被确定了,所以s0==s1为true;而”kv”和”ill”也都是字符串常量,当一个字 符串由多个字符串常量连接而成时,它自己肯定也是字符串常量,所以s2也同样在编译期就被解析为一个字符串常量,所以s2也是常量池中” kvill”的一个引用。所以我们得出s0==s1==s2;用new String() 创建的字符串不是常量,不能在编译期就确定,所以new String() 创建的字符串不放入常量池中,它们有自己的地址空间。

    示例:

    String s0="kvill";   
    
    String s1=new String("kvill");   
    
    String s2="kv" + new String("ill");   
    
    System.out.println( s0==s1 );   
    
    System.out.println( s0==s2 );   
    
    System.out.println( s1==s2 );  

    结果为:

    false 
    false 
    false

    例2中s0还是常量池 中"kvill”的应用,s1因为无法在编译期确定,所以是运行时创建的新对象”kvill”的引用,s2因为有后半部分 new String(”ill”)所以也无法在编译期确定,所以也是一个新创建对象”kvill”的应用;明白了这些也就知道为何得出此结果了。

    4. String.intern()

    再补充介绍一点:存在于.class文件中的常量池,在运行期被JVM装载,并且可以扩充。String的 intern()方法就是扩充常量池的 一个方法;当一个String实例str调用intern()方法时,Java 查找常量池中 是否有相同Unicode的字符串常量,如果有,则返回其的引用,如果没有,则在常 量池中增加一个Unicode等于str的字符串并返回它的引用;看示例就清楚了

    示例:

    String s0= "kvill";   
    
    String s1=new String("kvill");   
    
    String s2=new String("kvill");   
    
    System.out.println( s0==s1 );   
    
    System.out.println( "**********" );   
    
    s1.intern();   
    
    s2=s2.intern(); //把常量池中"kvill"的引用赋给s2   
    
    System.out.println( s0==s1);   
    
    System.out.println( s0==s1.intern() );   
    
    System.out.println( s0==s2 );  

    结果为:

    false 
    false //虽然执行了s1.intern(),但它的返回值没有赋给s1 
    true //说明s1.intern()返回的是常量池中"kvill"的引用 
    true

    最后我再破除一个错误的理解:有人说,“使用 String.intern() 方法则可以将一个 String 类的保存到一个全局 String 表中 ,如果具有相同值的 Unicode 字符串已经在这个表中,那么该方法返回表中已有字符串的地址,如果在表中没有相同值的字符串,则将自己的地址注册到表中”如果我把他说的这个全局的 String 表理解为常量池的话,他的最后一句话,”如果在表中没有相同值的字符串,则将自己的地址注册到表中”是错的:

    示例:

    String s1=new String("kvill");   
    
    String s2=s1.intern();   
    
    System.out.println( s1==s1.intern() );   
    
    System.out.println( s1+" "+s2 );   
    
    System.out.println( s2==s1.intern() );  

    结果:

    false 
    kvill kvill 
    true

    在这个类中我们没有声名一个”kvill”常量,所以常量池中一开始是没有”kvill”的,当我们调用s1.intern()后就在常量池中新添加了一 个”kvill”常量,原来的不在常量池中的”kvill”仍然存在,也就不是“将自己的地址注册到常量池中”了。

    s1==s1.intern() 为false说明原来的”kvill”仍然存在;s2现在为常量池中”kvill”的地址,所以有s2==s1.intern()为true。

    5. 关于equals()和==:

    这个对于String简单来说就是比较两字符串的Unicode序列是否相当,如果相等返回true;而==是 比较两字符串的地址是否相同,也就是是否是同一个字符串的引用。

    6. 关于String是不可变的

    这一说又要说很多,大家只 要知道String的实例一旦生成就不会再改变了,比如说:String str=”kv”+”ill”+” “+”ans”; 就是有4个字符串常量,首先”kv”和”ill”生成了”kvill”存在内存中,然后”kvill”又和” ” 生成 “kvill “存在内存中,最后又和生成了”kvill ans”;并把这个字符串的地址赋给了str,就是因为String的”不可变”产生了很多临时变量,这也就是为什么建议用StringBuffer的原 因了,因为StringBuffer是可改变的。

    下面是一些String相关的常见问题:

    String中的final用法和理解

    final StringBuffer a = new StringBuffer("111");
    final StringBuffer b = new StringBuffer("222");
    a=b;//此句编译不通过
    final StringBuffer a = new StringBuffer("111");
    a.append("222");// 编译通过

    可见,final只对引用的"值"(即内存地址)有效,它迫使引用只能指向初始指向的那个对象,改变它的指向会导致编译期错误。至于它所指向的对象 的变化,final是不负责的。

    String常量池问题的几个例子

    下面是几个常见例子的比较分析和理解:

    String a = "a1";   
    
    String b = "a" + 1;   
    
    System.out.println((a == b)); //result = true  
    
    String a = "atrue";   
    
    String b = "a" + "true";   
    
    System.out.println((a == b)); //result = true  
    
    String a = "a3.4";   
    
    String b = "a" + 3.4;   
    
    System.out.println((a == b)); //result = true 

    分析:JVM对于字符串常量的"+"号连接,将程序编译期,JVM就将常量字符串的"+"连接优化为连接后的值,拿"a" + 1来说,经编译器优化后在class中就已经是a1。在编译期其字符串常量的值就确定下来,故上面程序最终的结果都为true。

    String a = "ab";   
    
    String bb = "b";   
    
    String b = "a" + bb;   
    
    System.out.println((a == b)); //result = false 

    分析:JVM对于字符串引用,由于在字符串的"+"连接中,有字符串引用存在,而引用的值在程序编译期是无法确定的,即"a" + bb无法被编译器优化,只有在程序运行期来动态分配并将连接后的新地址赋给b。所以上面程序的结果也就为false。

    String a = "ab";   
    
    final String bb = "b";   
    
    String b = "a" + bb;   
    
    System.out.println((a == b)); //result = true 

    分析:和[3]中唯一不同的是bb字符串加了final修饰,对于final修饰的变量,它在编译时被解析为常量值的一个本地拷贝存储到自己的常量 池中或嵌入到它的字节码流中。所以此时的"a" + bb和"a" + "b"效果是一样的。故上面程序的结果为true。

    String a = "ab";   

    final String bb = getBB();   

    String b = "a" + bb;   

    System.out.println((a == b)); //result = false   

    private static String getBB() {  return "b";   } 

    分析:JVM对于字符串引用bb,它的值在编译期无法确定,只有在程序运行期调用方法后,将方法的返回值和"a"来动态连接并分配地址为b,故上面 程序的结果为false。

    通过上面4个例子可以得出得知:String  s  =  "a" + "b" + "c"; 就等价于String s = "abc";  

    String  a  =  "a";   
    String  b  =  "b";   
    String  c  =  "c";   
    String  s  =   a  +  b  +  c; 

    这个就不一样了,最终结果等于: 
     

    StringBuffer temp = new StringBuffer();     

    temp.append(a).append(b).append(c);     

    String s = temp.toString(); 

    由上面的分析结果,可就不难推断出String 采用连接运算符(+)效率低下原因分析,形如这样的代码:

    public class Test {  
        public static void main(String args[]) {  
            String s = null;  
            for(int i = 0; i < 100; i++) {  
            s += "a";  
            }  
        }  
    } 

    每做一次 + 就产生个StringBuilder对象,然后append后就扔掉。下次循环再到达时重新产生个StringBuilder对象,然后 append 字符串,如此循环直至结束。如果我们直接采用 StringBuilder 对象进行 append 的话,我们可以节省 N - 1 次创建和销毁对象的时间。所以对于在循环中要进行字符串连接的应用,一般都是用StringBuffer或StringBulider对象来进行 append操作。

    String对象的intern方法理解和分析:

    public class Test4 {  
    
        private static String a = "ab";   
    
        public static void main(String[] args){  
    
        String s1 = "a";  
    
        String s2 = "b";  
    
        String s = s1 + s2;  
    
        System.out.println(s == a);//false  
    
        System.out.println(s.intern() == a);//true    
    
        }  
    
    } 

    这里用到Java里面是一个常量池的问题。对于s1+s2操作,其实是在堆里面重新创建了一个新的对象,s保存的是这个新对象在堆空间的的内容,所 以s与a的值是不相等的。而当调用s.intern()方法,却可以返回s在常量池中的地址值,因为a的值存储在常量池中,故s.intern和a的值相等。

    总结

    栈中用来存放一些原始数据类型的局部变量数据和对象的引用(String,数组.对象等等)但不存放对象内容

    堆中存放使用new关键字创建的对象.

    字符串是一个特殊包装类,其引用是存放在栈里的,而对象内容必须根据创建方式不同定(常量池和堆).有的是编译期就已经创建好,存放在字符串常 量池中,而有的是运行时才被创建.使用new关键字,存放在堆中。

     

    展开全文
  • 堆、栈在内存中的存储位置----详解

    万次阅读 多人点赞 2016-04-10 18:01:08
    1.什么变量堆内存里存放,什么变量在栈内存里存放 引自 一般认为c中分为这几个存储区 1 - 有编译器自动分配释放 2堆 - 一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收 3全局区(静态区)...

    1.什么变量在堆内存里存放,什么变量在栈内存里存放

    一般认为在c中分为这几个存储区
    1栈 - 有编译器自动分配释放
    2堆 - 一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收
    3全局区(静态区),全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 程序结束释放。
    4另外还有一个专门放常量的地方。 - 程序结束释放

    在函数体中定义的变量通常是在栈上,用malloc, calloc, realloc等分配内存的函数分配得到的就是在堆上。在所有函数体外定义的是全局量,加了static修饰符后不管在哪里都存放在全局区(静态区),在所有函数体外定义的static变量表示在该文件中有效,不能extern到别的文件用,在函数体内定义的static表示只在该函数体内有效。另外,函数中的 "adgfdf "这样的字符串存放在常量区。
    比如: 

    #include<stdio.h>
    
    int a = 0;					//全局初始化区
    char *p1;					//全局未初始化区
    main()
    {
    	int b;					//栈
    	char s[] = "abc ";		//栈
    	char *p2;				//栈
    	char *p3 = "123456 ";	//123456\0在常量区,p3在栈上。
    	static int c = 0;		//全局(静态)初始化区
    	p1 = (char *)malloc(10);
    	p2 = (char *)malloc(20);
    	//分配得来得10和20字节的区域就在堆区。
    	strcpy(p1, "123456 ");	//123456\0放在常量区,编译器可能会将它与p3所指向的 "123456 "优化成一块。 
    }

    还有就是函数调用时会在栈上有一系列的保留现场及传递参数的操作。栈的空间大小有限定,vc的缺省是2M。栈不够用的情况一般是程序中分配了大量数组和递归函数层次太深。有一点必须知道,当一个函数调用完返回后它会释放该函数中所有的栈空间。栈是由编译器自动管理的,不用你操心。堆是动态分配内存的,并且你可以分配使用很大的内存。但是用不好会产生内存泄漏。并且频繁地malloc和free会产生内存碎片(有点类似磁盘碎片),因为c分配动态内存时是寻找匹配的内存的。而用栈则不会产生碎片。在栈上存取数据比通过指针在堆上存取数据快些。

    一般大家说的堆栈和栈是一样的,就是栈(stack),而说堆时才是堆heap.
    栈是先入后出的,一般是由高地址向低地址生长。


    堆(heap)和栈(stack)是C/C++编程不可避免会碰到的两个基本概念。首先,这两个概念都可以在讲数据结构的书中找到,他们都是基本的数据结构,虽然栈更为简单一些。在具体的C/C++编程框架中,这两个概念并不是并行的。对底层机器代码的研究可以揭示, 栈是机器系统提供的数据结构 而堆则是C/C++函数库提供的 。具体地说,现代计算机(串行执行机制),都直接在代码底层支持栈的数据结构。这体现在,有专门的寄存器指向栈所在的地址,有专门的机器指令完成数据入栈出栈的操作。这种机制的特点是效率高,支持的数据有限,一般是整数,指针,浮点数等系统直接支持的数据类型,并不直接支持其他的数据结构。因为栈的这种特点,对栈的使用在程序中是非常频繁的。 对子程序的调用就是直接利用栈完成的 。机器的call指令里隐含了把返回地址推入栈,然后跳转至子程序地址的操作,而子程序中的ret指令则隐含从堆栈中弹出返回地址并跳转之的操作。C/C++中的自动变量是直接利用栈的例子,这也就是为什么当函数返回时,该函数的自动变量自动失效的原因(因为 颜换指戳说饔们暗 状态)。


    和栈不同,堆的数据结构并不是由系统(无论是机器系统还是操作系统)支持的,而是由函数库提供的。基本的malloc/realloc/free函数维护了一套内部的堆数据结构。当程序使用这些函数去获得新的内存空间时,这套函数首先试图从内部堆中寻找可用的内存空间,如果没有可以使用的内存空间,则试图利用系统调用来动态增加程序数据段的内存大小,新分配得到的空间首先被组织进内部堆中去,然后再以适当的形式返回给调用者。当程序释放分配的内存空间时,这片内存空间被返回内部堆结构中,可能会被适当的处理(比如和其他空闲空间合并成更大的空闲空间),以更适合下一次内存分配申请。这套复杂的分配机制实际上相当于一个内存分配的缓冲池(Cache),使用这套机制有如下若干原因:

    1. 系统调用可能不支持任意大小的内存分配。有些系统的系统调用只支持固定大小及其倍数的内存请求(按页分配);这样的话对于大量的小内存分类来说会造成浪费。
    2. 系统调用申请内存可能是代价昂贵的。系统调用可能涉及用户态和核心态的转换。
    3. 没有管理的内存分配在大量复杂内存的分配释放操作下很容易造成内存碎片。

    堆和栈的对比

    从以上知识可知,栈是系统提供的功能,特点是快速高效,缺点是有限制,数据不灵活;而堆是函数库提供的功能,特点是灵活方便,数据适应面广泛,但是效率有一定降低。栈是系统数据结构,对于进程/线程是唯一的;堆是函数库内部数据结构,不一定唯一。不同堆分的内存无法互相操作。栈空间分静态分配和动态分配两种。静态分配是编译器完成的,比如自动变量(auto)的分配。动态分配由alloca函数完成。栈的动态分配无需释放(是自动),也就没有释放函数。为可移植的程序起见,栈的动态分配操作是不被鼓励的!堆空间的分配总是动态的,虽然程序结束时所有的数据空间都会被释放回系统,但是精确的申请内存/释放内存匹配是良好程序的基本要素。


    可以放一块思考
    堆和栈的生长方向恰好相反,
    |--------------| 低地址
    | 堆 |
    |--------------|
    | | |
    | I |
    | |
    | ^ |
    | 栈 | 高地址
    -----------------
    所以计算机中的堆和栈经常时放一块讲的


    注: 一般不是必要就不要动态创建,最讨厌把new出来的东西当局部变量用,用完了马上delete 的做法.

    理由
    1.栈分配比堆快,只需要一条指令就呢给配所有的局部变量
    2.栈不会出现内存碎片
    3。栈对象好管理

    当然,某些情况下也要用堆,比如
    1.对象很大
    2.对象需要在某个特定的时刻构造或析够
    3.类只允许对象动态创建,比如VCL的大多数类
    当然,必须用堆对象时也不能躲避

    堆内存和栈内存各有什么作用?

    堆:顺序随意
    栈:先进后出
    堆和栈的区别

    一、预备知识—程序的内存分配

    一个由c/C++编译的程序占用的内存分为以下几个部分
    1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈
    2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。
    3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
    4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
    5、程序代码区—存放函数体的二进制代码。

    二、堆和栈的理论知识

    2.1申请方式
    stack:由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
    heap:需要程序员自己申请,并指明大小,在c中malloc函数如p1 = (char *)malloc(10);在C++中用new运算符如p2 = (char *)malloc(10);但是注意p1、p2本身是在栈中的
    2.2申请后系统的响应
    栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出
    堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中
    2.3申请大小的限制
    栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
    堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
    2.4申请效率的比较:
    栈由系统自动分配,速度较快。但程序员是无法控制的。
    堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便. 另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活
    2.5堆和栈中的存储内容
    栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。
    堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

    2.7小结:
    堆和栈的区别可以用如下的比喻来看出:使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。 使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
    堆和栈的区别主要分:
    操作系统方面的堆和栈,如上面说的那些,不多说了。还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。


    深入理解堆栈、堆在内存中的实现

    引自<http://www.cnblogs.com/tianzhiliang/archive/2010/09/19/1830763.html>

    3.1  栈vs堆:有什么不同?

    栈负责保存我们的代码执行(或调用)路径,而堆则负责保存对象(或者说数据,接下来将谈到很多关于堆的问题)的路径。

    可以将栈想象成一堆从顶向下堆叠的盒子。当每调用一次方法时,我们将应用程序中所要发生的事情记录在栈顶的一个盒子中,而我们每次只能够使用栈顶的那个盒子。当我们栈顶的盒子被使用完之后,或者说方法执行完毕之后,我们将抛开这个盒子然后继续使用栈顶上的新盒子。堆的工作原理比较相似,但大多数时候堆用作保存信息而非保存执行路径,因此堆能够在任意时间被访问。与栈相比堆没有任何访问限制,堆就像床上的旧衣服,我们并没有花时间去整理,那是因为可以随时找到一件我们需要的衣服,而栈就像储物柜里堆叠的鞋盒,我们只能从最顶层的盒子开始取,直到发现那只合适的。

    以上图片并不是内存中真实的表现形式,但能够帮助我们区分栈和堆。

    栈是自行维护的,也就是说内存自动维护栈,当栈顶的盒子不再被使用,它将被抛出。相反的,堆需要考虑垃圾回收,垃圾回收用于保持堆的整洁性,没有人愿意看到周围都是赃衣服,那简直太臭了!

    3.2 栈和堆里有些什么?

    当我们的代码执行的时候,栈和堆中主要放置了四种类型的数据:值类型(Value Type),引用类型(Reference Type),指针(Pointer),指令(Instruction)。

    1.值类型:


    在C#中,所有被声明为以下类型的事物被称为值类型:

    bool
    byte
    char
    decimal
    double
    enum
    float
    int
    long
    sbyte
    short
    struct
    uint
    ulong
    ushort


    2.引用类型:


    所有的被声明为以下类型的事物被称为引用类型:

    class
    interface
    delegate
    object
    string


    3.指针:

    在内存管理方案中放置的第三种类型是类型引用,引用通常就是一个指针。我们不会显示的使用指针,它们由公共语言运行时(CLR)来管理。指针(或引用)是不同于引用类型的,是因为当我们说某个事物是一个引用类型时就意味着我们是通过指针来访问它的。指针是一块内存空间,而它指向另一个内存空间。就像栈和堆一样,指针也同样要占用内存空间,但它的值是一个内存地址或者为空。

    4.指令:

    在后面的文章中你会看到指令是如何工作的...


    4 内存非配详解

    引自<http://www.cnblogs.com/skynet/archive/2011/03/07/1975479.html>


    为什么需要知道C/C++的内存布局和在哪可以可以找到想要的数据?知道内存布局对调试程序非常有帮助,可以知道程序执行时,到底做了什么,有助于写出干净的代码。本文的主要内容如下:

    • 源文件转换为可执行文件
    • 可执行程序组成及内存布局
    • 数据存储类别
    • 一个实例
    • 总结

    4.1源文件转换为可执行文件

    源文件经过以下几步生成可执行文件:

    • 1、预处理(preprocessor):对#include、#define、#ifdef/#endif、#ifndef/#endif等进行处理
    • 2、编译(compiler):将源码编译为汇编代码
    • 3、汇编(assembler):将汇编代码汇编为目标代码
    • 4、链接(linker):将目标代码链接为可执行文件

    编译器和汇编器创建的目标文件包含:二进制代码(指令)、源码中的数据;链接器将多个目标文件链接成一个;装载器吧目标文件加载到内存。


    4.2 可执行程序组成及内存布局

    通过上面的小节,我们知道将源程序转换为可执行程序的步骤,典型的可执行文件分为两部分:


    1. 代码段(Code),由机器指令组成,该部分是不可改的,编译之后就不再改变,放置在文本段(.text)。
    2. 数据段(Data),它由以下几部分组:
    • 常量(constant),通常放置在只读read-only的文本段(.text
    • 静态数据(static data),初始化的放置在数据段(.data);未初始化的放置在(.bss,Block Started by Symbol,BSS段的变量只有名称和大小却没有值)
    • 动态数据(dynamic data),这些数据存储在堆(heap)或栈(stack)
    源程序编译后链接到一个以0地址为始地址的线性或多维虚拟地址空间。而且每个进程都拥有这样一个空间,每个指令和数据都在这个虚拟地址空间拥有确定的地址,把这个地址称为虚拟地址(Virtual Address)。将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器(Virtual Memory)。典型的虚拟存储器中有类似的布局:

    • Text Segment (.text)
    • Initialized Data Segment (.data)
    • Uninitialized Data Segment (.bss)
    • The Stack
    • The Heap
    如下图所示:


    当进程被创建时,内核为其提供一块物理内存,将虚拟内存映射到物理内存,这些都是由操作系统来做的。

    4.3 数据存储类别

    讨论C/C++中的内存布局,不得不提的是数据的存储类别!数据在内存中的位置取决于它的存储类别。一个对象是内存的一个位置,解析这个对象依赖于两个属性:存储类别、数据类型。

    • 存储类别决定对象在内存中的生命周期。
    • 数据类型决定对象值的意义,在内存中占多大空间。
    C/C++中由(auto、 extern、 register、 static)存储类别和对象声明的上下文决定它的存储类别。

    1、自动对象(automatic objects)

    auto register 将声明的对象指定为自动存储类别。他们的作用域是局部的,诸如一个函数内,一个代码块{***}内等。操作了作用域,对象会被销毁。

    在一个代码块中声明一个对象,如果没有执行auto,那么默认是自动存储类别。
    声明为register的对象是自动存储类别,存储在计算机的快速寄存器中。不可以对register对象做取值操作“&”。

    2、静态对象(static objects)

    静态对象可以局部的,也可以是全局的。静态对象一直保持它的值,例如进入一个函数,函数中的静态对象仍保持上次调用时的值。包含静态对象的函数不是线程安全的、不可重入的,正是因为它具有“记忆”功能。
    • 局部对象声明为静态之后,将改变它在内存中保存的位置,由动态数据--->静态数据,即从堆或栈变为数据段或bbs段。
    • 全局对象声明为静态之后,而不会改变它在内存中保存的位置,仍然是在数据段或bbs段。但是static将改变它的作用域,即该对象仅在本源文件有效。此相反的关键字是extern,使用extern修饰或者什么都不带的全局对象的作用域是整个程序。
    #include <stdio.h>
    #include <stdlib.h>
     
    int a;
    static int b;
    void func( void )
    {
        char c;
        static int d;
    }
    int main( void )
    {
        int e;
        int *pi = ( int *) malloc ( sizeof ( int ));
        func ();
        func ();
        free (pi );
        return (0);
    }

    程序中声明的变量a、b、c、d、e、pi的存储类别和生命期如下所述:
    • a是一个未初始化的全局变量,作用域为整个程序,生命期是整个程序运行期间,在内存的bbs段
    • b是一个未初始化的静态全局变量,作用域为本源文件,生命期是整个程序运行期间,在内存的bbs段
    • c是一个未初始化的局部变量,作用域为函数func体内,即仅在函数体内可见,生命期也是函数体内,在内存的栈中
    • d是一个未初始化的静态局部变量,作用域为函数func体内,即仅在函数体内可见,生命期是整个程序运行期间,在内存的bbs段
    • e是一个未初始化的局部变量,作用域为函数main体内,即仅在函数体内可见,生命期是main函数内,在内存的栈中
    • pi是一个局部指针,指向堆中的一块内存块,该块的大小为sizeof(int),pi本身存储在内存的栈中,生命期是main函数内
    • 新申请的内存块在堆中,生命期是malloc/free之间
    用图表示如下:

    4.4 总结

    本文介绍了C/C++中由源程序到可执行文件的步骤,和可执行程序的内存布局,数据存储类别,最后还通过一个例子来说明。可执行程序中的变量在内存中的布局可以总结为如下:

    • 变量(函数外):如果未初始化,则存放在BSS段;否则存放在data段
    • 变量(函数内):如果没有指定static修饰符,则存放在栈中;否则同上
    • 常量:存放在文本段.text
    • 函数参数:存放在栈或寄存器中
    内存可以分为以下几段:
    • 文本段:包含实际要执行的代码(机器指令)和常量。它通常是共享的,多个实例之间共享文本段。文本段是不可修改的。
    • 初始化数据段:包含程序已经初始化的全局变量,.data。
    • 未初始化数据段:包含程序未初始化的全局变量,.bbs。该段中的变量在执行之前初始化为0或NULL。
    • 栈:由系统管理,由高地址向低地址扩展。
    • 堆:动态内存,由用户管理。通过malloc/alloc/realloc、new/new[]申请空间,通过free、delete/delete[]释放所申请的空间。由低地址想高地址扩展。

    展开全文
  • Linux 中的各种:进程 线程 内核 中断

    万次阅读 多人点赞 2016-09-01 21:52:02
    什么什么作用?首先, (stack) 是一种串列形式的 数据结构...这种数据结构的特点是 后入先出 (LIFO, Last In First Out),数据只能在串列的一端 (称为:栈顶 top) 进行 推入 (push) 和 弹出 (pop) 操作。

    转载请注明出处: http://kyang.cc/

    栈是什么?栈有什么作用?

    首先,栈 (stack) 是一种串列形式的 数据结构。这种数据结构的特点是 后入先出 (LIFO, Last In First Out),数据只能在串列的一端 (称为:栈顶 top) 进行 推入 (push) 和 弹出 (pop) 操作。根据栈的特点,很容易的想到可以利用数组,来实现这种数据结构。但是本文要讨论的并不是软件层面的栈,而是硬件层面的栈。

    栈结构

    大多数的处理器架构,都有实现硬件栈。有专门的栈指针寄存器,以及特定的硬件指令来完成 入栈/出栈 的操作。例如在 ARM 架构上,R13 (SP) 指针是堆栈指针寄存器,而 PUSH 是用于压栈的汇编指令,POP 则是出栈的汇编指令。

    【扩展阅读】:ARM 寄存器简介

    ARM 处理器拥有 37 个寄存器。 这些寄存器按部分重叠组方式加以排列。 每个处理器模式都有一个不同的寄存器组。 编组的寄存器为处理处理器异常和特权操作提供了快速的上下文切换。

    提供了下列寄存器:
    - 三十个 32 位通用寄存器:
    - 存在十五个通用寄存器,它们分别是 r0-r12、sp、lr
    - sp (r13) 是堆栈指针。C/C++ 编译器始终将 sp 用作堆栈指针
    - lr (r14) 用于存储调用子例程时的返回地址。如果返回地址存储在堆栈上,则可将 lr 用作通用寄存器
    - 程序计数器 (pc):指令寄存器
    - 应用程序状态寄存器 (APSR):存放算术逻辑单元 (ALU) 状态标记的副本
    - 当前程序状态寄存器 (CPSR):存放 APSR 标记,当前处理器模式,中断禁用标记等
    - 保存的程序状态寄存器 (SPSR):当发生异常时,使用 SPSR 来存储 CPSR

    上面是栈的原理和实现,下面我们来看看栈有什么作用。栈作用可以从两个方面体现:函数调用多任务支持

    一、函数调用

    我们知道一个函数调用有以下三个基本过程:
    - 调用参数的传入
    - 局部变量的空间管理
    - 函数返回

    函数的调用必须是高效的,而数据存放在 CPU通用寄存器 或者 RAM 内存 中无疑是最好的选择。以传递调用参数为例,我们可以选择使用 CPU通用寄存器 来存放参数。但是通用寄存器的数目都是有限的,当出现函数嵌套调用时,子函数再次使用原有的通用寄存器必然会导致冲突。因此如果想用它来传递参数,那在调用子函数前,就必须先 保存原有寄存器的值,然后当子函数退出的时候再 恢复原有寄存器的值

    函数的调用参数数目一般都相对少,因此通用寄存器是可以满足一定需求的。但是局部变量的数目和占用空间都是比较大的,再依赖有限的通用寄存器未免强人所难,因此我们可以采用某些 RAM 内存区域来存储局部变量。但是存储在哪里合适?既不能让函数嵌套调用的时候有冲突,又要注重效率。

    这种情况下,栈无疑提供很好的解决办法。一、对于通用寄存器传参的冲突,我们可以再调用子函数前,将通用寄存器临时压入栈中;在子函数调用完毕后,在将已保存的寄存器再弹出恢复回来。二、而局部变量的空间申请,也只需要向下移动下栈顶指针;将栈顶指针向回移动,即可就可完成局部变量的空间释放;三、对于函数的返回,也只需要在调用子函数前,将返回地址压入栈中,待子函数调用结束后,将函数返回地址弹出给 PC 指针,即完成了函数调用的返回;

    于是上述函数调用的三个基本过程,就演变记录一个栈指针的过程。每次函数调用的时候,都配套一个栈指针。即使循环嵌套调用函数,只要对应函数栈指针是不同的,也不会出现冲突。

    函数栈结构

    【扩展阅读】:函数栈帧 (Stack Frame)

    函数调用经常是嵌套的,在同一时刻,栈中会有多个函数的信息。每个未完成运行的函数占用一个独立的连续区域,称作栈帧(Stack Frame)。栈帧存放着函数参数,局部变量及恢复前一栈帧所需要的数据等,函数调用时入栈的顺序为:

    实参N~1 → 主调函数返回地址 → 主调函数帧基指针EBP → 被调函数局部变量1~N

    栈帧的边界由 栈帧基地址指针 EBP栈指针 ESP 界定,EBP 指向当前栈帧底部(高地址),在当前栈帧内位置固定;ESP指向当前栈帧顶部(低地址),当程序执行时ESP会随着数据的入栈和出栈而移动。因此函数中对大部分数据的访问都基于EBP进行。函数调用栈的典型内存布局如下图所示:

    函数调用栈的典型内存布局


    二、多任务支持

    然而栈的意义还不只是函数调用,有了它的存在,才能构建出操作系统的多任务模式。我们以 main 函数调用为例,main 函数包含一个无限循环体,循环体中先调用 A 函数,再调用 B 函数。

    func B():
      return;
    
    func A():
      B();
    
    func main():
      while (1)
        A();

    试想在单处理器情况下,程序将永远停留在此 main 函数中。即使有另外一个任务在等待状态,程序是没法从此 main 函数里面跳转到另一个任务。因为如果是函数调用关系,本质上还是属于 main 函数的任务中,不能算多任务切换。此刻的 main 函数任务本身其实和它的栈绑定在了一起,无论如何嵌套调用函数,栈指针都在本栈范围内移动。

    由此可以看出一个任务可以利用以下信息来表征:
    1. main 函数体代码
    2. main 函数栈指针
    3. 当前 CPU 寄存器信息

    假如我们可以保存以上信息,则完全可以强制让出 CPU 去处理其他任务。只要将来想继续执行此 main 任务的时候,把上面的信息恢复回去即可。有了这样的先决条件,多任务就有了存在的基础,也可以看出栈存在的另一个意义。在多任务模式下,当调度程序认为有必要进行任务切换的话,只需保存任务的信息(即上面说的三个内容)。恢复另一个任务的状态,然后跳转到上次运行的位置,就可以恢复运行了。

    可见每个任务都有自己的栈空间,正是有了独立的栈空间,为了代码重用,不同的任务甚至可以混用任务的函数体本身,例如可以一个main函数有两个任务实例。至此之后的操作系统的框架也形成了,譬如任务在调用 sleep() 等待的时候,可以主动让出 CPU 给别的任务使用,或者分时操作系统任务在时间片用完是也会被迫的让出 CPU。不论是哪种方法,只要想办法切换任务的上下文空间,切换栈即可。

    多任务模型

    【扩展阅读】:任务、线程、进程 三者关系

    任务是一个抽象的概念,即指软件完成的一个活动;而线程则是完成任务所需的动作;进程则指的是完成此动作所需资源的统称;关于三者的关系,有一个形象的比喻:
    - 任务 = 送货
    - 线程 = 开送货车
    - 系统调度 = 决定合适开哪部送货车
    - 进程 = 道路 + 加油站 + 送货车 + 修车厂



    Linux 中有几种栈?各种栈的内存位置?

    介绍完栈的工作原理和用途作用后,我们回归到 Linux 内核上来。内核将栈分成四种:

    • 进程栈
    • 线程栈
    • 内核栈
    • 中断栈

    一、进程栈

    进程栈是属于用户态栈,和进程 虚拟地址空间 (Virtual Address Space) 密切相关。那我们先了解下什么是虚拟地址空间:在 32 位机器下,虚拟地址空间大小为 4G。这些虚拟地址通过页表 (Page Table) 映射到物理内存,页表由操作系统维护,并被处理器的内存管理单元 (MMU) 硬件引用。每个进程都拥有一套属于它自己的页表,因此对于每个进程而言都好像独享了整个虚拟地址空间。

    Linux 内核将这 4G 字节的空间分为两部分,将最高的 1G 字节(0xC0000000-0xFFFFFFFF)供内核使用,称为 内核空间。而将较低的3G字节(0x00000000-0xBFFFFFFF)供各个进程使用,称为 用户空间。每个进程可以通过系统调用陷入内核态,因此内核空间是由所有进程共享的。虽然说内核和用户态进程占用了这么大地址空间,但是并不意味它们使用了这么多物理内存,仅表示它可以支配这么大的地址空间。它们是根据需要,将物理内存映射到虚拟地址空间中使用。

    Linux虚拟地址空间

    Linux 对进程地址空间有个标准布局,地址空间中由各个不同的内存段组成 (Memory Segment),主要的内存段如下:
    - 程序段 (Text Segment):可执行文件代码的内存映射
    - 数据段 (Data Segment):可执行文件的已初始化全局变量的内存映射
    - BSS段 (BSS Segment):未初始化的全局变量或者静态变量(用零页初始化)
    - 堆区 (Heap) : 存储动态内存分配,匿名的内存映射
    - 栈区 (Stack) : 进程用户空间栈,由编译器自动分配释放,存放函数的参数值、局部变量的值等
    - 映射段(Memory Mapping Segment):任何内存映射文件

    Linux标准进程内存段布局

    而上面进程虚拟地址空间中的栈区,正指的是我们所说的进程栈。进程栈的初始化大小是由编译器和链接器计算出来的,但是栈的实时大小并不是固定的,Linux 内核会根据入栈情况对栈区进行动态增长(其实也就是添加新的页表)。但是并不是说栈区可以无限增长,它也有最大限制 RLIMIT_STACK (一般为 8M),我们可以通过 ulimit 来查看或更改 RLIMIT_STACK 的值。

    【扩展阅读】:如何确认进程栈的大小

    我们要知道栈的大小,那必须得知道栈的起始地址和结束地址。栈起始地址 获取很简单,只需要嵌入汇编指令获取栈指针 esp 地址即可。栈结束地址 的获取有点麻烦,我们需要先利用递归函数把栈搞溢出了,然后再 GDB 中把栈溢出的时候把栈指针 esp 打印出来即可。代码如下:

    /* file name: stacksize.c */
    
    void *orig_stack_pointer;
    
    void blow_stack() {
        blow_stack();
    }
    
    int main() {
        __asm__("movl %esp, orig_stack_pointer");
    
        blow_stack();
        return 0;
    }
    $ g++ -g stacksize.c -o ./stacksize
    $ gdb ./stacksize
    (gdb) r
    Starting program: /home/home/misc-code/setrlimit
    
    Program received signal SIGSEGV, Segmentation fault.
    blow_stack () at setrlimit.c:4
    4       blow_stack();
    (gdb) print (void *)$esp
    $1 = (void *) 0xffffffffff7ff000
    (gdb) print (void *)orig_stack_pointer
    $2 = (void *) 0xffffc800
    (gdb) print 0xffffc800-0xff7ff000
    $3 = 8378368    // Current Process Stack Size is 8M

    上面对进程的地址空间有个比较全局的介绍,那我们看下 Linux 内核中是怎么体现上面内存布局的。内核使用内存描述符来表示进程的地址空间,该描述符表示着进程所有地址空间的信息。内存描述符由 mm_struct 结构体表示,下面给出内存描述符结构中各个域的描述,请大家结合前面的 进程内存段布局 图一起看:

    struct mm_struct {
        struct vm_area_struct *mmap;           /* 内存区域链表 */
        struct rb_root mm_rb;                  /* VMA 形成的红黑树 */
        ...
        struct list_head mmlist;               /* 所有 mm_struct 形成的链表 */
        ...
        unsigned long total_vm;                /* 全部页面数目 */
        unsigned long locked_vm;               /* 上锁的页面数据 */
        unsigned long pinned_vm;               /* Refcount permanently increased */
        unsigned long shared_vm;               /* 共享页面数目 Shared pages (files) */
        unsigned long exec_vm;                 /* 可执行页面数目 VM_EXEC & ~VM_WRITE */
        unsigned long stack_vm;                /* 栈区页面数目 VM_GROWSUP/DOWN */
        unsigned long def_flags;
        unsigned long start_code, end_code, start_data, end_data;    /* 代码段、数据段 起始地址和结束地址 */
        unsigned long start_brk, brk, start_stack;                   /* 栈区 的起始地址,堆区 起始地址和结束地址 */
        unsigned long arg_start, arg_end, env_start, env_end;        /* 命令行参数 和 环境变量的 起始地址和结束地址 */
        ...
        /* Architecture-specific MM context */
        mm_context_t context;                  /* 体系结构特殊数据 */
    
        /* Must use atomic bitops to access the bits */
        unsigned long flags;                   /* 状态标志位 */
        ...
        /* Coredumping and NUMA and HugePage 相关结构体 */
    };

    mm_struct 内存段

    【扩展阅读】:进程栈的动态增长实现

    进程在运行的过程中,通过不断向栈区压入数据,当超出栈区容量时,就会耗尽栈所对应的内存区域,这将触发一个 缺页异常 (page fault)。通过异常陷入内核态后,异常会被内核的 expand_stack() 函数处理,进而调用 acct_stack_growth() 来检查是否还有合适的地方用于栈的增长。

    如果栈的大小低于 RLIMIT_STACK(通常为8MB),那么一般情况下栈会被加长,程序继续执行,感觉不到发生了什么事情,这是一种将栈扩展到所需大小的常规机制。然而,如果达到了最大栈空间的大小,就会发生 栈溢出(stack overflow),进程将会收到内核发出的 段错误(segmentation fault) 信号。

    动态栈增长是唯一一种访问未映射内存区域而被允许的情形,其他任何对未映射内存区域的访问都会触发页错误,从而导致段错误。一些被映射的区域是只读的,因此企图写这些区域也会导致段错误。

    二、线程栈

    从 Linux 内核的角度来说,其实它并没有线程的概念。Linux 把所有线程都当做进程来实现,它将线程和进程不加区分的统一到了 task_struct 中。线程仅仅被视为一个与其他进程共享某些资源的进程,而是否共享地址空间几乎是进程和 Linux 中所谓线程的唯一区别。线程创建的时候,加上了 CLONE_VM 标记,这样 线程的内存描述符 将直接指向 父进程的内存描述符

      if (clone_flags & CLONE_VM) {
        /*
         * current 是父进程而 tsk 在 fork() 执行期间是共享子进程
         */
        atomic_inc(&current->mm->mm_users);
        tsk->mm = current->mm;
      }

    虽然线程的地址空间和进程一样,但是对待其地址空间的 stack 还是有些区别的。对于 Linux 进程或者说主线程,其 stack 是在 fork 的时候生成的,实际上就是复制了父亲的 stack 空间地址,然后写时拷贝 (cow) 以及动态增长。然而对于主线程生成的子线程而言,其 stack 将不再是这样的了,而是事先固定下来的,使用 mmap 系统调用,它不带有 VM_STACK_FLAGS 标记。这个可以从 glibc 的nptl/allocatestack.c 中的 allocate_stack() 函数中看到:

    mem = mmap (NULL, size, prot,
                MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0);

    由于线程的 mm->start_stack 栈地址和所属进程相同,所以线程栈的起始地址并没有存放在 task_struct 中,应该是使用 pthread_attr_t 中的 stackaddr 来初始化 task_struct->thread->sp(sp 指向 struct pt_regs 对象,该结构体用于保存用户进程或者线程的寄存器现场)。这些都不重要,重要的是,线程栈不能动态增长,一旦用尽就没了,这是和生成进程的 fork 不同的地方。由于线程栈是从进程的地址空间中 map 出来的一块内存区域,原则上是线程私有的。但是同一个进程的所有线程生成的时候浅拷贝生成者的 task_struct 的很多字段,其中包括所有的 vma,如果愿意,其它线程也还是可以访问到的,于是一定要注意。

    三、进程内核栈

    在每一个进程的生命周期中,必然会通过到系统调用陷入内核。在执行系统调用陷入内核之后,这些内核代码所使用的栈并不是原先进程用户空间中的栈,而是一个单独内核空间的栈,这个称作进程内核栈。进程内核栈在进程创建的时候,通过 slab 分配器从 thread_info_cache 缓存池中分配出来,其大小为 THREAD_SIZE,一般来说是一个页大小 4K;

    union thread_union {                                   
            struct thread_info thread_info;                
            unsigned long stack[THREAD_SIZE/sizeof(long)];
    };                                                     

    thread_union 进程内核栈 和 task_struct 进程描述符有着紧密的联系。由于内核经常要访问 task_struct,高效获取当前进程的描述符是一件非常重要的事情。因此内核将进程内核栈的头部一段空间,用于存放 thread_info 结构体,而此结构体中则记录了对应进程的描述符,两者关系如下图(对应内核函数为 dup_task_struct()):

    进程内核栈与进程描述符

    有了上述关联结构后,内核可以先获取到栈顶指针 esp,然后通过 esp 来获取 thread_info。这里有一个小技巧,直接将 esp 的地址与上 ~(THREAD_SIZE - 1) 后即可直接获得 thread_info 的地址。由于 thread_union 结构体是从 thread_info_cache 的 Slab 缓存池中申请出来的,而 thread_info_cachekmem_cache_create 创建的时候,保证了地址是 THREAD_SIZE 对齐的。因此只需要对栈指针进行 THREAD_SIZE 对齐,即可获得 thread_union 的地址,也就获得了 thread_union 的地址。成功获取到 thread_info 后,直接取出它的 task 成员就成功得到了 task_struct。其实上面这段描述,也就是 current 宏的实现方法:

    register unsigned long current_stack_pointer asm ("sp");
    
    static inline struct thread_info *current_thread_info(void)  
    {                                                            
            return (struct thread_info *)                        
                    (current_stack_pointer & ~(THREAD_SIZE - 1));
    }                                                            
    
    #define get_current() (current_thread_info()->task)
    
    #define current get_current()                       

    四、中断栈

    进程陷入内核态的时候,需要内核栈来支持内核函数调用。中断也是如此,当系统收到中断事件后,进行中断处理的时候,也需要中断栈来支持函数调用。由于系统中断的时候,系统当然是处于内核态的,所以中断栈是可以和内核栈共享的。但是具体是否共享,这和具体处理架构密切相关。

    X86 上中断栈就是独立于内核栈的;独立的中断栈所在内存空间的分配发生在 arch/x86/kernel/irq_32.cirq_ctx_init() 函数中(如果是多处理器系统,那么每个处理器都会有一个独立的中断栈),函数使用 __alloc_pages 在低端内存区分配 2个物理页面,也就是8KB大小的空间。有趣的是,这个函数还会为 softirq 分配一个同样大小的独立堆栈。如此说来,softirq 将不会在 hardirq 的中断栈上执行,而是在自己的上下文中执行。

    中断栈

    而 ARM 上中断栈和内核栈则是共享的;中断栈和内核栈共享有一个负面因素,如果中断发生嵌套,可能会造成栈溢出,从而可能会破坏到内核栈的一些重要数据,所以栈空间有时候难免会捉襟见肘。



    Linux 为什么需要区分这些栈?

    为什么需要区分这些栈,其实都是设计上的问题。这里就我看到过的一些观点进行汇总,供大家讨论:

    1. 为什么需要单独的进程内核栈?

      • 所有进程运行的时候,都可能通过系统调用陷入内核态继续执行。假设第一个进程 A 陷入内核态执行的时候,需要等待读取网卡的数据,主动调用 schedule() 让出 CPU;此时调度器唤醒了另一个进程 B,碰巧进程 B 也需要系统调用进入内核态。那问题就来了,如果内核栈只有一个,那进程 B 进入内核态的时候产生的压栈操作,必然会破坏掉进程 A 已有的内核栈数据;一但进程 A 的内核栈数据被破坏,很可能导致进程 A 的内核态无法正确返回到对应的用户态了;
    2. 为什么需要单独的线程栈?

      • Linux 调度程序中并没有区分线程和进程,当调度程序需要唤醒”进程”的时候,必然需要恢复进程的上下文环境,也就是进程栈;但是线程和父进程完全共享一份地址空间,如果栈也用同一个那就会遇到以下问题。假如进程的栈指针初始值为 0x7ffc80000000;父进程 A 先执行,调用了一些函数后栈指针 esp 为 0x7ffc8000FF00,此时父进程主动休眠了;接着调度器唤醒子线程 A1:
        • 此时 A1 的栈指针 esp 如果为初始值 0x7ffc80000000,则线程 A1 一但出现函数调用,必然会破坏父进程 A 已入栈的数据。
        • 如果此时线程 A1 的栈指针和父进程最后更新的值一致,esp 为 0x7ffc8000FF00,那线程 A1 进行一些函数调用后,栈指针 esp 增加到 0x7ffc8000FFFF,然后线程 A1 休眠;调度器再次换成父进程 A 执行,那这个时候父进程的栈指针是应该为 0x7ffc8000FF00 还是 0x7ffc8000FFFF 呢?无论栈指针被设置到哪个值,都会有问题不是吗?
    3. 进程和线程是否共享一个内核栈?

      • No,线程和进程创建的时候都调用 dup_task_struct 来创建 task 相关结构体,而内核栈也是在此函数中 alloc_thread_info_node 出来的。因此虽然线程和进程共享一个地址空间 mm_struct,但是并不共享一个内核栈。
    4. 为什么需要单独中断栈?

      • 这个问题其实不对,ARM 架构就没有独立的中断栈。

    大家还有什么观点,可以在留言下来 :-D



    文章写到这也就结束了,您要是还能看到这,我一定要表示忠心的感谢,文章是在太长了,我都写快一个星期了。好了,终于可以 Released 了,hexo deploy,再会!

    • K.Yang



    参考文章

    栈的作用

    C语言函数调用栈(一)

    函数调用栈 剖析+图解

    进程地址空间分布

    Linux 进程栈和线程栈的区别

    Linux基础:进程管理

    stackoverflow - How Process Size is determined?

    stackoverflow - RLIMIT_STACK seems to change according to setrlimit/getrlimit, but stack size doesn’t seem to actually change

    stackoverflow - Relation between stack limit and threads

    对 Linux 的进程内核栈的认识

    Linux进程内核栈

    Linux中的栈:用户态栈/内核栈/中断栈

    What Every Programmer Should Know About Memory? - Ulrich Drepper (Red Hat, Inc.)

    展开全文
  • 什么及其特点和应用详解

    万次阅读 2019-03-14 18:40:24
    同顺序表和链表一样,栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构,如图1 所示。 图 1 栈存储结构示意图 从图 1 我们看到,栈存储结构与之前所学的线性...栈只能从表的一端存取数据,另一...
  • 1.什么变量堆内存里存放,什么变量在栈内存里存放引自&lt;http://blog.chinaunix.net/uid-23860671-id-150568.html&gt;一般认为c中分为这几个存储区 1 - 有编译器自动分配释放 2堆 - 一般由程序员...
  • 和队列java中的实现

    千次阅读 2013-10-29 08:26:27
    和队列java中的实现
  • 什么

    千次阅读 2020-03-02 14:38:14
    什么是一种受限线性表,也就是说,元素具有线性关系,即前驱后继关系; 只不过它是 一种特殊的线性表而已; 的特性? 如图: 线性表是表尾进行插入和删除操作,而在栈中表尾是指栈顶,而不是...
  • 一文读懂堆与的区别

    万次阅读 多人点赞 2018-06-29 15:24:05
    堆(Heap)与(Stack)是开发人员必须面对的两个概念,理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与表示的是...
  • 什么是堆和,它们哪儿?

    千次阅读 2018-05-21 20:08:51
    问题描述编程语言书籍中经常解释值类型被创建在栈上,引用类型被创建堆上,但是并没有本质上解释这堆和什么。我仅有高级语言编程经验,没有看过对此更清晰的解释。我的意思是我理解什么,但是它们到底是...
  • 顺序/链式

    千次阅读 2018-04-09 00:30:44
    是是一种限定性的线性表,它将线性表的插入和删除限定为仅表的一端进行。将表中允许插入和删除的一端成为栈顶。所以栈顶的位置是不断动态变化的。它具有“后进先出”的特点。因为是由线性表实现的,所以,有...
  • 结构是一种非常常见的数据结构,并且很多场景下也被用到。其实结构跟数组结构很像,只是数组的基础...数据结构——一、什么二、结构的方法三、用代码实现一个结构(1)创建一个构造函数(2)实现push
  • 的实现

    千次阅读 2019-12-19 22:16:05
    文章目录的定义的抽象数据类型定义的顺序实现顺序的基本操作顺序的初始化判断顺序是否为空求顺序的长度清空顺序销毁顺序顺序的入栈顺序的出栈的链式实现 本篇将讲述的相关知识 之前的...
  • JAVA程序员技术、业务、工具

    千次阅读 2017-11-19 13:50:57
    1、技术 2、业务 3、工具
  • 链式

    千次阅读 2016-11-19 12:43:28
    2016年7月23日15:39:13 为什么需要链式?... 而事先指定的存贮空间分配的过小,会使得,程序运行时可能会发生存贮空间不够的情形,这就产生了的链式 存贮结构. 什么时候适合使用链式? 当数据元素的数目变化
  • (c++实现)

    千次阅读 2018-03-01 10:57:31
      对的操作(增/删/读)只能通过的一端进行,允许操作的一端称之为栈顶,不允许操作的一端称为底。的特性为先进后出。c++实现,可采用如下的设计思路:   Stack是一个接口类,封装了的所有操作:...
  • 的插入 删除

    千次阅读 2017-01-05 20:23:47
    只能在表尾进行插入和删除操作,也是线性表。元素先进后出,最先进只能在栈底,的插入称为:进栈、入栈,删除称为:出栈或弹。 顺序:以数组0下标为...top记录底元素数组中的位置,是变化的,top
  • 什么是堆和,它们哪儿?--堆栈

    千次阅读 2015-04-04 00:03:01
    编程语言书籍中经常解释值类型被创建在栈上,引用类型被创建堆上,但是并没有本质上解释这堆和什么。我仅有高级语言编程经验,没有看过对此更清晰的解释。我的意思是我理解什么,但是它们到底是什么...
  • 数据结构-和队列

    万次阅读 多人点赞 2012-06-19 12:53:15
    其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示: 结论:后进先出(Last In First Out),简称为LIFO线性表。 的基本运算有六种: 构造空栈:InitStack(S)、 判空: StackEmpty...
  • 1. 是一个特殊的线性表,只能在一端操作:栈顶(top):允许操作 的一端  底(bottom):不允许操作的一端 2. 特点:后进先出 二、顺序  1. 若存储的长度为StackSize,则栈顶位置top必须小于...
  • 对于LTE协议的一些理解

    千次阅读 2013-07-11 10:19:44
    这篇文档主要想和大家讨论下我对协议的理解,我觉得学习协议最重要的是了解我们需要什么功能,为什么我们需要这些功能。这是学习协议的关键。其次才是我们如何实现这些功能,也就是协议上规定的实现方式。对于...
  • 数据结构 —

    千次阅读 2020-06-21 18:23:48
    区别在于是后进先出的,而线性表允许任意位置插入和删除数据元素。所以,也被称作后进先出的线性表,或简称后进先出表。 的一种应用场景就是改变数据元素序列的顺序,其思路就是:顺序的将数据元素压栈,但...
  • 和队列测试题

    千次阅读 2016-05-19 20:26:05
    对于栈只能在 栈顶 插入和删除元素;对于队列只能 队尾 插入和  队首 删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为  栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. ...
  • 蓝牙协议初识

    千次阅读 多人点赞 2018-12-03 10:30:02
    蓝牙技术相对于它所替代的技术存在什么样的优势和劣势呢?蓝牙技术都做了些什么呢? 随着我们周围电子产品的增多电子产品之间的信息交互也越来越频繁,但是信息交互方式无线连接出现之前只能使用有线连接,比如...
  • 的实现:顺序

    千次阅读 2014-05-24 12:17:24
    (stack)是一种很常见的线性结构。它是只允许一端进行插入和删除操作的线性表,这一端我们称为栈顶。的特点常被称为:先进后出(filo-first int last out),或者是后进先出(lifo-last in first out)。这个描述从...
  • 如果需要堆上创建对象,要么使用new运算符,要么使用malloc系列函数。...此时,obj是在栈上分配的吗? 要回答这个问题,我们首先要理解这个语句是什么意思。这个语句就是代表着,在栈上创建对象吗? 其实,这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 186,141
精华内容 74,456
关键字:

对于栈只能在什么位置