基础知识(2)

容器和算法:

● 请你来说一下map和set有什么区别,分别又是怎么实现的?

参考回答:

map和set都是C++的关联容器,其底层实现都是红黑树(RB-Tree)。由于 map 和set所开放的各种操作接口,RB-tree 也都提供了,所以几乎所有的 map 和set的操作行为,都只是转调 RB-tree 的操作行为。

map和set区别在于:

(1)map中的元素是key-value(关键字—值)对:关键字起到索引的作用,值则表示与索引相关联的数据;Set与之相对就是关键字的简单集合,set中每个元素只包含一个关键字。

(2)set的迭代器是const的,不允许修改元素的值;map允许修改value,但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的,如果允许修改key的话,那么首先需要删除该键,然后调节平衡,再插入修改后的键值,调节平衡,如此一来,严重破坏了map和set的结构,导致iterator失效,不知道应该指向改变前的位置,还是指向改变后的位置。所以STL中将set的迭代器设置成const,不允许修改迭代器的值;而map的迭代器则不允许修改key值,允许修改value值。

(3)map支持下标操作,set不支持下标操作。map可以用key做下标,map的下标运算符[ ]将关键码作为下标去执行查找,如果关键码不存在,则插入一个具有该关键码和mapped_type类型默认值的元素至map中,因此下标运算符[ ]在map应用中需要慎用,const_map不能用,只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用,mapped_type类型没有默认值也不应该使用。如果find能解决需要,尽可能用find。

● 请你来介绍一下STL的allocaotr

参考回答:

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中,其内存配置和释放如下:

new运算分两个阶段:(1) 调用::operator new配置内存; (2) 调用对象构造函数构造对象内容

delete运算分两个阶段:(1) 调用对象希构函数;(2) 掉用 ::operator delete 释放内存

为了精密分工,STL allocator将两个阶段操作区分开来:内存配置有alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由::construct()负责,对象析构由::destroy()负责。

同时为了提升内存管理的效率,减少申请小内存造成的内存碎片问题,SGI STL采用了两级配置器,当分配的空间大小超过128B时,会使用第一级空间配置器;当分配的空间大小小于128B时,将使用第二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放,而第二级空间配置器采用了内存池技术,通过空闲链表来管理内存。

● 请你来说一说STL迭代器删除元素

参考回答:

这个主要考察的是迭代器失效的问题。

  1. 对于序列容器vector,deque来说,使用erase(itertor)后,后边的每个元素的迭代器都会失效,但是后边每个元素都会往前移动一个位置,但是erase会返回下一个有效的迭代器;
  2. 对于关联容器map set来说,使用了erase(iterator)后,当前元素的迭代器失效,但是其结构是红黑树,删除当前元素的,不会影响到下一个元素的迭代器,所以在调用erase之前,记录下一个元素的迭代器即可。
  3. 对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此上面两种正确的方法都可以使用。

● 请你讲讲STL有什么基本组成

参考回答:

STL主要由:以下几部分组成:
容器、迭代器、仿函数、算法、分配器、配接器
他们之间的关系:分配器给容器分配存储空间,算法通过迭代器获取容器中的内容,仿函数可以协助算法完成各种操

作,配接器用来套接适配仿函数

● 请你说一说vector和list的区别,应用,越详细越好

参考回答:

1、概念:
1)Vector

连续存储的容器,动态数组,在堆上分配空间

底层实现:数组

两倍容量增长:

vector 增加(插入)新元素时,如果未超过当时的容量,则还有剩余空间,那么直接添加到最后(插入指定位置),然后调整迭代器。

如果没有剩余空间了,则会重新配置原有元素个数的两倍空间,然后将原空间元素通过复制的方式初始化新空间,再向新空间增加元素,最后析构并释放原空间,之前的迭代器会失效。

性能:

访问:O(1)

插入:在最后插入(空间够):很快

在最后插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。

在中间插入(空间够):内存拷贝

在中间插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。

删除:在最后删除:很快

在中间删除:内存拷贝

适用场景:经常随机访问,且不经常对非尾节点进行插入删除。

2)List

动态链表,在堆上分配空间,每插入一个元数都会分配空间,每删除一个元素都会释放空间。

底层:双向链表

性能:

访问:随机访问性能很差,只能快速访问头尾节点。

插入:很快,一般是常数开销

删除:很快,一般是常数开销

适用场景:经常插入删除大量数据

2、区别:

1)vector底层实现是数组;list是双向链表。

2)vector支持随机访问,list不支持。

3)vector是顺序内存,list不是。

4)vector在中间节点进行插入删除会导致内存拷贝,list不会。

5)vector一次性分配好内存,不够时才进行2倍扩容;list每次插入新节点都会进行内存申请。

6)vector随机访问性能好,插入删除性能差;list随机访问性能差,插入删除性能好。

3、应用

vector拥有一段连续的内存空间,因此支持随机访问,如果需要高效的随即访问,而不在乎插入和删除的效率,使用vector。

list拥有一段不连续的内存空间,如果需要高效的插入和删除,而不关心随机访问,则应使用list。

● 请你来说一下STL中迭代器的作用,有指针为何还要迭代器

参考回答:

1、迭代器

Iterator(迭代器)模式又称Cursor(游标)模式,用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴

露该对象的内部表示。或者这样说可能更容易理解:Iterator模式是运用于聚合对象的一种模式,通过运用该模式,使得

我们可以在不知道对象内部表示的情况下,按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。

由于Iterator模式的以上特性:与聚合对象耦合,在一定程度上限制了它的广泛运用,一般仅用于底层聚合支持类,如

STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

2、迭代器和指针的区别

迭代器不是指针,是类模板,表现的像指针。他只是模拟了指针的一些功能,通过重载了指针的一些操作符,->、*、

++、--等。迭代器封装了指针,是一个“可遍历STL( Standard Template Library)容器内全部或部分元素”的对象, 本质

是封装了原生指针,是指针概念的一种提升(lift),提供了比指针更高级的行为,相当于一种智能指针,他可以根据不

同类型的数据结构来实现不同的++,--等操作。

迭代器返回的是对象引用而不是对象的值,所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。

3、迭代器产生原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来,使得不用暴露集合内部的结构而达到循环遍历集合的效

果。

● 请你回答一下STL里resize和reserve的区别

参考回答:

resize():改变当前容器内含有元素的数量(size()),会生成默认的元素,eg: vector<int>v; v.resize(len); v的size变为len,如果原来v的size小于len,那么容器新增(len-size)个元素,元素的值为默认为0.当v.push_back(3);之后,则是3是放在了v的末尾,即下标为len,此时容器是size为len+1;

reserve():改变当前容器的最大容量(capacity),它不会生成元素,只是确定这个容器允许放入多少对象,如果reserve(len)的值大于当前的capacity(),那么会重新分配一块能存len个对象的空间,然后把之前v.size()个对象通过copy construtor复制过来,销毁之前的内存;

测试代码如下:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> a;
    a.reserve(100);
    a.resize(50);
    cout<<a.size()<<"  "<<a.capacity()<<endl;
        //50  100
    a.resize(150);
    cout<<a.size()<<"  "<<a.capacity()<<endl;
        //150  200
    a.reserve(50);
    cout<<a.size()<<"  "<<a.capacity()<<endl;
        //150  200
    a.resize(50);
    cout<<a.size()<<"  "<<a.capacity()<<endl;
        //50  200    
}

● 请你来说一下C++中类成员的访问权限

参考回答:

参考回答:C++通过 public、protected、private 三个关键字来控制成员变量和成员函数的访问权限,它们分别表示公有的、受保护的、私有的,被称为成员访问限定符。在类的内部(定义类的代码内部),无论成员被声明为 public、protected 还是 private,都是可以互相访问的,没有访问权限的限制。在类的外部(定义类的代码之外),只能通过对象访问成员,并且通过对象只能访问 public 属性的成员,不能访问 private、protected 属性的成员。

对于 protected :基类对象不能访问基类的protected成员,派生类中可以访问基类的protected成员。也就是说private成员是不能被继承的,只有public,protected的成员才可以被继承。只有在派生类中才可以通过派生类对象访问基类的protected成员。

#include <iostream>
using namespace std;
class Base
{
public:
    Base(){};
    virtual ~Base(){};
protected:
    int int_pro;
};
class A : public Base
{
public:
    A(){};
    A(int da){int_pro = da;}
    void Print(A &obj){obj.int_pro = 24;}
    void PrintPro(){cout << "The proteted data is " << int_pro <<endl;}
};
int main()
{
    // Base base;
    // base.int_pro  这是不能访问的
    
    A aObj;
    A aObj2(5);
    aObj2.PrintPro();
    aObj.Print(aObj2);
    aObj2.PrintPro();

    //注释1
    //aObj.int_pro = 8;
}

● 请你来说一下C++中struct和class的区别

参考回答:

在C++中,可以用struct和class定义类,都可以继承。区别在于:structural的默认继承权限和默认访问权限是public,而class的默认继承权限和默认访问权限是private。

另外,class还可以定义模板类形参,比如template <class T, int i>。

● 请你回答一下C++类内可以定义引用数据成员吗?

参考回答:

可以,必须通过成员函数初始化列表初始化。

● 请你回答一下什么是右值引用,跟左值又有什么区别?

参考回答:

右值引用是C++11中引入的新特性 , 它实现了转移语义和精确传递。它的主要目的有两个方面:

1. 消除两个对象交互时不必要的对象拷贝,节省运算存储资源,提高效率。

2. 能够更简洁明确地定义泛型函数。

左值和右值的概念:

左值:能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。

右值:不能对表达式取地址,或匿名对象。一般指表达式结束就不再存在的临时对象。

右值引用和左值引用的区别:

1. 左值可以寻址,而右值不可以。

2. 左值可以被赋值,右值不可以被赋值,可以用来给左值赋值。

3. 左值可变,右值不可变(仅对基础类型适用,用户自定义类型右值引用可以通过成员函数改变)。

● 左值、右值、移动语义、完美转发 ?

强烈建议参考:

https://www.jianshu.com/p/d19fc8447eaa

右值引用和移动语义可以避免无谓的复制,提高程序性能。左值是表达式结束后依然存在的持久化对象,右值是表达式结束之后就不存在的临时对象。可以通过能不能对表达式取地址来判断左值和右值。

左值引用:

int a = 10; // a是左值

int& refA = a; // refA是a的别名, 修改refA就是修改a, a是左值,左移是左值引用

int& b = 1; //编译错误! 1是右值,不能够使用左值引用

右值引用:

右值引用的符号是 && ,比如:

int&& a = 1; //实质上就是将不具名(匿名)变量取了个别名

int b = 1;

int && c = b; //编译错误! 不能将一个左值复制给一个右值引用

常量左值引用:几乎万能的引用类型。

移动语义:

比如向一个 vector push很多个临时的类对象,这些类对象还要做一次拷贝构造,如果可以直接使用临时对象已经申请了的资源,就可以节约资源。移动语义可以做到这一点。C++ 11 提供了 std:move() 来将左值转换为右值,调用移动构造函数。

要实现移动语义就必须增加两个函数:移动构造函数和移动赋值构造函数。

c++11中的所有容器都实现了move语义,move只是转移了资源的控制权,本质上是将左值强制转化为右值使用,以用于移动拷贝或赋值,避免对含有资源的对象发生无谓的拷贝。move对于拥有如内存、文件句柄等资源的成员的对象有效,如果是一些基本类型,如int和char[10]数组等,如果使用move,仍会发生拷贝(因为没有对应的移动构造函数),所以说move对含有资源的对象说更有意义。

完美转发:就是通过一个函数将参数继续转交给另一个函数进行处理,原参数可能是右值,可能是左值,如果还能继续保持参数的原有特征,那么它就是完美的。

● 请你来说一下一个C++源文件从文本到可执行文件经历的过程?

参考回答:

对于C++源文件,从文本到可执行文件一般需要四个过程:

预处理阶段:对源代码文件中文件包含关系(头文件)、预编译语句(宏定义)进行分析和替换,生成预编译文件。

编译阶段:将经过预处理后的预编译文件转换成特定汇编代码,生成汇编文件(.s文件)

汇编阶段:将编译阶段生成的汇编文件转化成机器码,生成可重定位目标文件(.o或.obj文件)

链接阶段:将多个目标文件及所需要的库连接成最终的可执行目标文件(.out或.exe文件)

基础知识(2)
图源 leet-code

基础知识(2)
https://blog.csdn.net/qq_42441693/article/details/104180660

预处理阶段:

预处理(产生.i文件,-E)执行代码:gcc -E main.c -o main.i

主要规则如下:
(1) 将所以#define删除,并将宏定义展开。
(2) 处理一些条件预编译指令如#ifndef,#ifdef,#elif,#else,#endif等。将不必要的代码过滤掉。
(3) 处理#include预编译指令,将被包含的文件插入到该预编译指令的位置。这个过程是递归进行的,因为被包含的文件可能也包含其他文件。
(4) 预处理过程还会过滤掉所有注释/**/和//里面的内容。
(5) 另外还会添加行号和文件名标识。
(6) 最后会保留#pragma编译器指令,因为编译器需要使用它们。

ifndef,#ifdef,#endif的作用是什么?防止重复包含头文件。

尖括号和双引号的区别是什么?

include<>,从标准库中寻找头文件。

include"",从当前目录开始寻找头文件。

编译

编译(产生汇编.s文件,-s)执行代码:gcc -S main.i -o main.s
       编译就是将预处理的文件进行一系列的词法分析,语法分析,语义分析,以及优化后产生相应的汇编代码文件。进行相应的词法分析,语法分析,语义分析,源代码优化,代码生成和目标代码优化。

基础知识(2)
源自https://blog.csdn.net/qq_42441693/article/details/104180660

汇编

汇编(产生目标.o文件或.obj文件,-c)执行代码:gcc -c main.s -o main.o
       汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程,即生成目标文件。 对于被翻译系统处理的每一个C语言源程序,都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。
目标文件由段组成,通常一个目标文件中至少有两个段:
代码段: 该段中所包含的主要是程序的指令。该段一般是可读和可执行的,但一般却不可写。
数据段: 主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读,可写,可执行的。

UNIX环境下主要有三种类型的目标文件:
可重定位文件:其中包含有适合于其它目标文件链接来创建一个可执行的或者共享的目标文件的代码和数据。
共享的目标文件:这种文件存放了适合于在两种上下文里链接的代码和数据。第一种是链接程序可把它与其它可重定位文件及共享的目标文件一起处理来创建另一个目标文件;第二种是动态链接程序将它与另一个可执行文件及其它的共享目标文件结合到一起,创建一个进程映象。
可执行文件:它包含了一个可以被操作系统创建一个进程来执行之的文件。
  汇编程序生成的实际上是第一种类型的目标文件。对于后两种还需要其他的一些处理方能得到,这个就是链接程序的工作了。

编译前的文件格式是汇编文件,编译后的文件是可重定位文件

可重定位文件:https://blog.csdn.net/weixin_44735312/article/details/102056370

链接

链接(产生可执行.out或.exe文件,-o)执行代码:gcc main.o -o main

链接就是把每个源代码独立的编译,然后按照它们的要求将它们组装起来,链接主要解决的是源代码之间的相互依赖问题,链接的过程包括地址和空间的分配,符号决议,和重定位等这些步骤。

基础知识(2)
源自 :https://blog.csdn.net/qq_42441693/article/details/104180660

 每个目标文件除了拥有自己的数据和二进制代码外,还拥有三个表,未解决符号表,地址重定向表,导出符号表

● 动态链接库和静态链接库

1、静态链接库
  在链接阶段,会将汇编生成的目标文件.o与引用到的库一起链接打包到可执行文件中,因此对应的链接方式称为静态链接。
       静态库可以简单看成是一组目标文件(.o/.obj文件)的集合,即很多目标文件经过压缩打包后形成的一个文件。

静态库的缺点在于:浪费空间和资源,因为所有相关的目标文件与牵涉到的函数库被链接合成一个可执行文件。

基础知识(2)

2、动态链接/库
       动态库在程序编译时并不会被连接到目标代码中,而是在程序运行是才被载入。 不同的应用程序如果调用相同的库,那么在内存里只需要有一份该共享库的实例,规避了空间浪费问题。动态库在程序运行是才被载入,也解决了静态库对程序的更新、部署和发布页会带来麻烦。用户只需要更新动态库即可,增量更新。动态连接解决了共享的目标文件多个副本浪费磁盘和内存空间的问题。在内存中共享一个目标文件模块的好处不仅仅是节省内存,还可以减少物理页面的换入换出,亦可以增加CPU的cache hit。

动态链接也有其缺点:很常见的一个问题是,当程序所依赖的某个模块更新后,由于新的模块与旧的模块之间接口不兼容,导致原有的程序无法运行。

基础知识(2)

● 请你回答一下malloc的原理,另外brk系统调用和mmap系统调用的作用分别是什么?

参考回答:

Malloc函数用于动态分配内存。为了减少内存碎片和系统调用的开销,malloc其采用内存池的方式,先申请大块内存作为堆区,然后将堆区分为多个内存块,以块作为内存管理的基本单位。当用户申请内存时,直接从堆区分配一块合适的空闲块。Malloc采用隐式链表结构将堆区分成连续的、大小不一的块,包含已分配块和未分配块;同时malloc采用显示链表结构来管理所有的空闲块,即使用一个双向链表将空闲块连接起来,每一个空闲块记录了一个连续的、未分配的地址。

当进行内存分配时,Malloc会通过隐式链表遍历所有的空闲块,选择满足要求的块进行分配;当进行内存合并时,malloc采用边界标记法,根据每个块的前后块是否已经分配来决定是否进行块合并。

Malloc在申请内存时,一般会通过brk或者mmap系统调用进行申请。其中当申请内存小于128K时,会使用系统函数brk在堆区中分配;而当申请内存大于128K时,会使用系统函数mmap在映射区分配。

● 请你来说一下C++/C的内存分配

基础知识(2)

64位可达128T,32bitCPU可寻址4G线性空间,每个进程都有各自独立的4G逻辑地址,其中0~3G是用户态空间,3~4G是内核空间,不同进程相同的逻辑地址会映射到不同的物理地址中。其逻辑地址其划分如下:

各个段说明如下:

3G用户空间和1G内核空间

静态区域:

text segment(代码段): 包括只读存储区和文本区,其中只读存储区存储字符串常量,文本区存储程序的机器代码。

data segment(数据段):存储程序中已初始化的全局变量和静态变量

bss segment:存储未初始化的全局变量和静态变量(局部+全局),以及所有被初始化为0的全局变量和静态变量,对于未初始化的全局变量和静态变量,程序运行main之前时会统一清零。即未初始化的全局变量编译器会初始化为0

动态区域:

heap(堆): 当进程未调用malloc时是没有堆段的,只有调用malloc时采用分配一个堆,并且在程序运行过程中可以动态增加堆大小(移动break指针),从低地址向高地址增长。分配小内存时使用该区域。  堆的起始地址由mm_struct 结构体中的start_brk标识,结束地址由brk标识。

memory mapping segment(映射区): 存储动态链接库等文件映射、申请大内存(malloc时调用mmap函数)

stack(栈):使用栈空间存储函数的返回地址、参数、局部变量、返回值,从高地址向低地址增长。在创建进程时会有一个最大栈大小,Linux可以通过ulimit命令指定。

● 请你回答一下如何判断内存泄漏?

参考回答:

内存泄漏通常是由于调用了malloc/new等内存申请的操作,但是缺少了对应的free/delete。为了判断内存是否泄露,我们一方面可以使用linux环境下的内存泄漏检查工具Valgrind,另一方面我们在写代码时可以添加内存申请和释放的统计功能,统计当前申请和释放的内存是否一致,以此来判断内存是否泄露。

Valgrind 了解一下:

valgrind通常用来成分析程序性能及程序中的内存泄露错误

https://www.cnblogs.com/kex1n/p/11573526.html

常用的 memcheck 用来检测程序中的内存问题,如泄漏、越界、非法指针等。

● 请你来说一下什么时候会发生段错误

参考回答:

段错误通常发生在访问非法内存地址的时候,具体来说分为以下几种情况:

  • 使用野指针
  • 试图修改字符串常量的内容

● 请你来回答一下什么是memory leak,也就是内存泄漏

参考回答:

内存泄漏(memory leak)是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上的消失,而是应用程序分配某段内存后,由于设计错误,失去了对该段内存的控制,因而造成了内存的浪费。

内存泄漏的分类:

1. 堆内存泄漏 (Heap leak)。对内存指的是程序运行中根据需要分配通过malloc,realloc new等从堆中分配的一块内存,再是完成后必须通过调用对应的 free或者delete 删掉。如果程序的设计的错误导致这部分内存没有被释放,那么此后这块内存将不会被使用,就会产生Heap Leak.

2. 系统资源泄露(Resource Leak)。主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉,导致系统资源的浪费,严重可导致系统效能降低,系统运行不稳定。

3. 没有将基类的析构函数定义为虚函数。当基类指针指向子类对象时,如果基类的析构函数不是virtual,那么子类的析构函数将不会被调用,子类的资源没有正确是释放,因此造成内存泄露。

● 请你来回答一下new和malloc的区别

参考回答:

1、new分配内存按照数据类型进行分配,malloc分配内存按照指定的大小分配;

2、new返回的是指定对象的指针,而malloc返回的是void*,因此malloc的返回值一般都需要进行类型转化。

3、new不仅分配一段内存,而且会调用构造函数,malloc不会。

4、new分配的内存要用delete销毁,malloc要用free来销毁;delete销毁的时候会调用对象的析构函数,而free则不会。

5、new是一个操作符可以重载,malloc是一个库函数。

6、malloc分配的内存不够的时候,可以用realloc扩容。扩容的原理?new没用这样操作。

7、new如果分配失败了会抛出bad_malloc的异常,而malloc失败了会返回NULL。

8、申请数组时: new[]一次分配所有内存,多次调用构造函数,搭配使用delete[],delete[]多次调用析构函数,销毁数组中的每个对象。而malloc则只能sizeof(int) * n。

● 请你来说一下共享内存相关api

参考回答:

Linux允许不同进程访问同一个逻辑内存,提供了一组API,头文件在sys/shm.h中。

1)新建共享内存 shmget

int shmget(key_t key,size_t size,int shmflg);

key:共享内存键值,可以理解为共享内存的唯一性标记。

size:共享内存大小

shmflag:创建进程和其他进程的读写权限标识。

返回值:相应的共享内存标识符,失败返回-1

2)连接共享内存到当前进程的地址空间 shmat

void *shmat(int shm_id,const void *shm_addr,int shmflg);

shm_id:共享内存标识符

shm_addr:指定共享内存连接到当前进程的地址,通常为0,表示由系统来选择。

shmflg:标志位

返回值:指向共享内存第一个字节的指针,失败返回-1

3)当前进程分离共享内存shmdt

int shmdt(const void *shmaddr);

4)控制共享内存shmctl

和信号量的semctl函数类似,控制共享内存

int shmctl(int shm_id,int command,struct shmid_ds *buf);

shm_id:共享内存标识符

command: 有三个值

IPC_STAT: 获取共享内存的状态,把共享内存的shmid_ds结构复制到buf中。

IPC_SET: 设置共享内存的状态,把buf复制到共享内存的shmid_ds结构。

IPC_RMID: 删除共享内存

buf:共享内存管理结构体。

● 请你说一说C++ STL 的内存优化

参考回答:

1)二级配置器结构
STL内存管理使用二级内存配置器。

1、第一级配置器
第一级配置器以 malloc(),free(),realloc() 等C函数执行实际的内存配置、释放、重新配置等操作,并且能在内存需求不被满足的时候,调用一个指定的函数。
一级空间配置器分配的是大于128字节的空间,如果分配不成功,调用句柄释放一部分内存,如果还不能分配成功,抛出异常。

2、第二级配置器
在STL的第二级配置器中多了一些机制,避免太多小区块造成的内存碎片,小额区块带来的不仅是内存碎片,配置时还有额外的负担。区块越小,额外负担所占比例就越大。

3、分配原则
如果要分配的区块大于128bytes,则移交给第一级配置器处理。
如果要分配的区块小于128bytes,则以内存池管理(memory pool),又称之次层配置(sub-allocation):每次配置一大块内存,并维护对应的16个空闲链表(free-list)。下次若有相同大小的内存需求,则直接从free-list中取。如果有小额区块被释放,则由配置器回收到free-list中。
当用户申请的空间小于128字节时,将字节数扩展到8的倍数(内存对齐),然后在自由链表中查找对应大小的子链表

  • 如果在自由链表查找不到或者块数不够,则向内存池进行申请,一般一次申请20块
  • 如果内存池空间足够,则取出内存
  • 如果不够分配20块,则分配最多的块数给自由链表,并且更新每次申请的块数
  • 如果一块都无法提供,则把剩余的内存挂到自由链表,然后向系统heap申请空间,如果申请失败,则看看自由链表还有没有可用的块,如果也没有,则最后调用一级空间配置器

2)二级内存池
二级内存池采用了16个空闲链表,这里的16个空闲链表分别管理大小为8、16、24......120、128的数据块。这里空闲链表节点的设计十分巧妙,这里用了一个联合体既可以表示下一个空闲数据块(存在于空闲链表中)的地址,也可以表示已经被用户使用的数据块(不存在空闲链表中)的地址。

基础知识(2)

1、空间配置函数 allocate

首先先要检查申请空间的大小,如果大于128字节就调用第一级配置器,小于128字节就检查对应的空闲链表,如果该空闲链表中有可用数据块,则直接拿来用(拿取空闲链表中的第一个可用数据块,然后把该空闲链表的地址设置为该数据块指向的下一个地址),如果没有可用数据块,则调用 refill 重新填充空间。


2、空间释放函数 deallocate

首先先要检查释放数据块的大小,如果大于128字节就调用第一级配置器,小于128字节则根据数据块的大小来判断回收后的空间会被插入到哪个空闲链表。

3、重新填充空闲链表 refill

在用 allocate 配置空间时,如果空闲链表中没有可用数据块,就会调用refill来重新填充空间,新的空间取自内存池。缺省取20个数据块,如果内存池空间不足,那么能取多少个节点就取多少个。

从内存池取空间给空闲链表用是 chunk_alloc 的工作,首先根据 end_free - start_free 来判断内存池中的剩余空间是否足以调出 20 个大小为size的数据块出去,如果内存连一个数据块的空间都无法供应,需要用malloc取堆中申请内存。

假如山穷水尽,整个系统的堆空间都不够用了,malloc失败,那么chunk_alloc会从空闲链表中找是否有大的数据块,然后将该数据块的空间分给内存池(这个数据块会从链表中去除)。

总结:

  1. 使用allocate向内存池请求size大小的内存空间,如果需要请求的内存大小大于128bytes,直接使用malloc。
  2. 如果需要的内存大小小于128bytes,allocate根据size找到最适合的自由链表。
    a. 如果链表不为空,返回第一个node,链表头改为第二个node。
    b. 如果链表为空,使用blockAlloc请求分配node。
    x. 如果内存池中有大于一个node的空间,分配竟可能多的node(但是最多20个),将一个node返回,其他的 node 添加 到链表中。
    y. 如果内存池只有一个node的空间,直接返回给用户。
    z. 若果如果连一个node都没有,再次向操作系统请求分配内存。
    ①分配成功,再次进行b过程。
    ②分配失败,循环各个自由链表,寻找空间。
    I. 找到空间,再次进行过程b。
    II. 找不到空间,抛出异常。
  3. 用户调用deallocate释放内存空间,如果要求释放的内存空间大于128bytes,直接调用free。
  4. 否则按照其大小找到合适的自由链表,并将其插入。

● 请你说说select,epoll的区别,原理,性能,限制都说一说

参考回答:

select:

是最初解决IO阻塞问题的方法。用结构体fd_set来告诉内核监听多个文件描述符,该结构体被称为描述符集。由数组来维持哪些描述符被置位了。对结构体的操作封装在三个宏定义中。通过轮寻来查找是否有描述符要被处理。

存在的问题:

1. 内置数组的形式使得select的最大文件数受限与FD_SIZE;

2. 每次调用select前都要重新初始化描述符集,将fd从用户态拷贝到内核态,每次调用select后,都需要将fd从内核态拷贝到用户态;(内核态用户态两次文件描述符集拷贝

3. 轮寻排查当文件描述符个数很多时,效率很低;

poll:

通过一个可变长度的数组解决了select文件描述符受限的问题。数组中元素是结构体,该结构体保存描述符的信息,每增加一个文件描述符就向数组中加入一个结构体,结构体只需要拷贝一次到内核态。poll解决了select重复初始化的问题轮寻排查的问题未解决

epoll:

轮寻排查所有文件描述符的效率不高,使服务器并发能力受限。因此,epoll采用只返回状态发生变化的文件描述符,便解决了轮寻的瓶颈。

epoll对文件描述符的操作有两种模式:LT(level trigger)和ET(edge trigger)。LT模式是默认模式

  1. LT模式

LT(level triggered) 是缺省的工作方式,并且同时支持block和no-block socket。在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的。

2. ET模式

ET(edge-triggered)是高速工作方式,只支持 no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个 fd 作 IO 操作(从而导致它再次变成未就绪),内核不会发送更多的通知 (only once) ET模式在很大程度上减少了epoll事件被重复触发的次数,因此效率要比LT模式高。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

3、LT模式与ET模式的区别如下:

LT模式:当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序,应用程序可以不立即处理该事件。下次调用epoll_wait时,会再次响应应用程序并通知此事件。

ET模式:当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序,应用程序必须立即处理该事件。如果不处理,下次调用epoll_wait时,不会再次响应应用程序并通知此事件。

给TA打赏
共{{data.count}}人
人已打赏
计算机基础

基础知识(1)

2021-9-17 19:46:25

手机数码

JIMMY智能手持无线吸尘器1S开启预售 1.25KG轻便主机 吸尘更轻便支

2021-4-26 14:31:28

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索