cpp-review

  • 好吧,这是为了面试而准备的,顺便查漏补缺
  • C++

成员变量初始化顺序

  • 成员变量在使用初始化列表初始化时,与构造函数中初始化成员列表的顺序无关,只与定义成员变量的顺序有关

  • 如果不使用初始化列表初始化,在构造函数内初始化时,此时与成员变量在构造函数中的位置有关

    • 变量的初始化顺序就应该是:

      1 基类的静态变量或全局变量

      2 派生类的静态变量或全局变量

      3 基类的成员变量

      4 派生类的成员变量

RTTI

  • 运行时类型信息,它提供了运行时确定对象类型的方法
  • 三个支持RTTI的元素
  • dynamamic_cast
    • 讲一个执行基类的指针转换为指向派生类的指针,负责返回空指针
  • typied运算符返回一个指出对象的类型的值,typeid是一个返回类型为type_info类型的函数
  • type_info结构存储了有关特定类型的信息

指针占用几个字节

  • 16为地址,指针即为2个字节,

    现在一般是32位系统,所以是4个字节,

    以后64位,则就为8个字节

  • 内存是由字节组成的,每个字节都有一个编号。指针变量主要是存放相同数据类型的变量的首地址。这里的这个地址其实就是内存的某个字节的编号。而这个编号的确定是与地址总线有关。如果地址总线是32位,则它的寻址范围是02^32(04G)。那么为一个字节的编址就会由32个0或者1组成。例如第一个字节的编址是32个0,最后一个的编址是32个1。一个字节有8位,32位则需要4个字节。

  • 简单的说32位的操作系统就是指:地址总线是32位的系统。那么,也就是说操作系统的位数决定了指针变量所占的字节数

strcpy strncpy

  • strcpy(dest,src); strcpy把src所指向以’\0’结尾的字符串复制到dest所指的数组中,返回指向dest的指针。
    • 当sizeof(dest)>=sizeof(src)时,拷贝正确,并在dest字符串后面加入’\0’;
    • 当sizeof(dest)<sizeof(src)时,拷贝出错。
  • strncpy(dest,src,n); strncpy把src所指向以’\0’结尾的字符串的前n个字符复制到dest所指的数组中,返回指向dest的指针。
    • 当n>=sizeof(src)时,拷贝正确,并在dest字符串后面加入’\0’;
    • 当n<sizeof(src)时,只拷贝src前n-1个字符串到dest,不会为dest字符串后面加入’\0’;

ASCII-utf-8-unicode

  • ASCII 英语字符与二进制位之间的关系,ASCII 码一共规定了128个字符的编码,这128个符号(包括32个不能打印出来的控制符号),只占用了一个字节的后面7位,最前面的一位统一规定为0
  • Unicode一种所有符号的编码
    • Unicode 只是一个符号集,它只规定了符号的二进制代码,却没有规定这个二进制代码应该如何存储
    • 这里就有两个严重的问题,第一个问题是,如何才能区别 Unicode 和 ASCII ?计算机怎么知道三个字节表示一个符号,而不是分别表示三个符号呢?第二个问题是,我们已经知道,英文字母只用一个字节表示就够了,如果 Unicode 统一规定,每个符号用三个或四个字节表示,那么每个英文字母前都必然有二到三个字节是0,这对于存储来说是极大的浪费,文本文件的大小会因此大出二三倍,这是无法接受的
  • UTF-8 就是在互联网上使用最广的一种 Unicode 的实现方式
    • 种变长的编码方式。它可以使用1~4个字节表示一个符号,根据不同的符号而变化字节长度
    • 对于单字节的符号,字节的第一位设为0,后面7位为这个符号的 Unicode 码。因此对于英语字母,UTF-8 编码和 ASCII 码是相同的。
    • 对于n字节的符号(n > 1),第一个字节的前n位都设为1,第n + 1位设为0,后面字节的前两位一律设为10。剩下的没有提及的二进制位,全部为这个符号的 Unicode 码。

为什么static函数不能const修饰和virtual修饰

  • 1
    这是C++的规则,const修饰符用于表示函数不能修改成员变量的值,该函数必须是含有this指针的类成员函数,函数调用方式为thiscall,而类中的static函数本质上是全局函数,调用规约是__cdecl或__stdcall,不能用const来修饰它。

判断一个对象调用是否经过虚函数表

  • 调用通过Memset把虚函数表指针置0

lambda实现原理

  • C++/C的类型安全

  • c的类型安全只在局部上下文中体现,例如试图将一种类型的指针转换成其他类型的指针时,编译器会报错,malloc和new相比也并不是类型安全的。

  • c++类型安全:

    • 操作符new返回的指针类型严格与对象匹配,而不是void*;
    • C中很多以void*为参数的函数可以改写为C++模板函数,而模板是支持类型检查的;
    • 引入const关键字代替#define constants,它是有类型、有作用域的,而#define constants只是简单的文本替换;
    • 一些#define宏可被改写为inline函数,结合函数的重载,可在类型安全的前提下支持多种类型,当然改写为模板也能保证类型安全;
    • C++提供了dynamic_cast关键字,使得转换过程更加安全,因为dynamic_cast比static_cast涉及更多具体的类型检查。

auto VS decltype

  • auto auto关键字来让编译器帮助我们分析表达式或者函数所属的类型,用一个对象的类型和值来初始化另一个对象。
  • auto VS const
    • auto会忽略掉顶层const, 保留底层const.
  • auto VS 引用
    • 如果表达式是引用类型, 那么auto的类型是这个引用的对象的类型.
    • 如果要声明一个引用, 就必须要加上&, 如果要声明为一个指针, 既可以加上也可以不加
  • decltype 只是为了推断出表达式的类型而不用这个表达式的值来初始化对象..
  • decltype vs const
    • 不论是顶层const还是底层const, decltype都会保留
  • decltype和引用
    • 如果表达式是引用类型, 那么decltype的类型也是引用
    • 如果表达式是引用类型, 但是想要得到这个引用所指向的类型, 需要修改表达式:
    • 对指针的解引用操作返回的是引用类型
    • 如果一个表达式的类型不是引用, 但是我们需要推断出引用, 那么可以加上一对括号, 就变成了引用类型了

访问权限

  • 访问范围:

    • private: 只能由该类中的函数、其友元函数访问,不能被任何其他访问,该类的对象也不能访问.
      protected: 可以被该类中的函数、子类的函数、以及其友元函数访问,但不能被该类的对象访问
      public: 可以被该类中的函数、子类的函数、其友元函数访问,也可以由该类的对象访问
    • 注:友元函数包括两种:设为友元的全局函数,设为友元类中的成员函数
      父类与其直接子类的访问关系如上,无论是哪种继承方式(private继承、protected继承、public继承)。
  • 对于三种继承关系的不同:

    • public继承:public继承后,从父类继承来的函数属性不变(private、public、protected属性不变,)。
      private继承:private继承后,从父类继承来的函数属性都变为private
      protected继承:protected继承后,从父类继承过来的函数,public、protected属性变为protected,private还是private。

程序优化

  • 编译优化
  • 位运算代替乘除法
  • 内联频繁调用的短小函数
  • 空间换时间
  • 提前计算
  • 字符数组的初始化

异常

  • C++ 通过 throw 语句和 try…catch 语句实现对异常的处理

    • 1
      throw 表达式;//抛出异常
    • try…catch 语句的执行过程是:

    • 1
      2
      3
      4
      5
      6
      try{

      }
      catch(异常类型){
      }
      catch(异常类型){}
      • 执行 try 块中的语句,如果执行的过程中没有异常拋出,那么执行完后就执行最后一个 catch 块后面的语句,所有 catch 块中的语句都不会被执行;
    • 如果 try 块执行的过程中拋出了异常,那么拋出异常后立即跳转到第一个“异常类型”和拋出的异常类型匹配的 catch 块中执行(称作异常被该 catch 块“捕获”),执行完后再跳转到最后一个 catch 块后面继续执行。

四种类型转换

  • static_cast 静态转换,也就是编译时转换。可以完成基础类型的转换,然后任意类型指针与void指针的转换,还可以完成同一个继承体系中类型的转换。上行转换(派生类—->基类)是安全的;下行转换(基类—->派生类)由于没有动态类型检查,所以是不安全的。
  • dynamamic_cast 是运行时转换,用于将基类的指针或引用安全的转换成派生类的指针或引用—向下转换。因为向上转换upcast是没有问题的(子类转换为父类),因为父类的行为(函数)都包含在子类中。
  • const_cast 去除掉常量属性或者增加常量属性
  • reinterpret_cast 对二进制形式重新解释,但不改变其值。

C/C++函数调用的压栈模型

  • 1568370381628

  • 对c++而言,以上几种调用惯例的名字修饰策略都略有所改变,因为c++支持函数重载以及命名空间和成员函数等等,因此实际上一个 函数名可以对应多个函数定义,那么上面提到的名字修饰策略显然无法区分各个不同同名函数定义的。所以c++有自己更加复杂的名字修饰策略。

    最后,c++还有自己一种特殊的调用惯例,称为thiscall,专门用于类成员函数的调用,其特点随编译器不同而不同,在vc里是将this指针存放于eax寄存器,

    参数从右到左压栈,而对于gcc、thiscall和cdecl完全一样,只是将this看作是函数的第一参数

  • 成员初始化列表

    • 在类构造函数中,不在函数体内对变量赋值,而在参数列表后,跟一个冒号和初始化列表
    • 必须
      • 需要初始化const修饰的类成员或初始化引用成员数据;
      • 子类初始化父类的私有成员;
      • 数据成员是对象,并且这个对象只有含参数的构造函数,没有无参数的构造函数;
    • 初始化顺序为申明顺序
    • 高效 少了1次默认构造过程
      • 对象成员变量的初始化动作发生在进入构造函数之前。当然对于内置类型没什么影响,但如果有些成员是类,那么在进入构造函数之前,会先调用一次默认构造函数,进入构造函数后所做的事其实是一次赋值操作(对象已存在),所以是一次默认构造加一次赋值

内存泄漏

  • 申请了一块内存空间,使用完毕后没有释放掉。内存泄漏并非指内存在物理上的消失,而是应用程序分配某段内存后,由于设计错误,失去了对该段内存的控制,因而造成了内存的浪费。
    • 堆内存泄漏 (Heap leak)。对内存指的是程序运行中根据需要分配通过malloc,realloc
      new等从堆中分配的一块内存,再是完成后必须通过调用对应的 free或者delete
      删掉。如果程序的设计的错误导致这部分内存没有被释放,那么此后这块内存将不会被使用,就会产生Heap Leak.
    • 系统资源泄露(Resource Leak).主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉,导致系统资源的浪费,严重可导致系统效能降低,系统运行不稳定。
  • 工具软件BoundsChecker
  • 解决内存泄漏最有效的办法就是使用智能指针(Smart Pointer)

结构体内存对齐

  • 数据成员对齐规则:数据成员对齐规则:结构(struct或联合union)的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员存储的起始位置: min(#pragma pack()指定的数,这个数据成员的自身长度)的倍数
  • 结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从min(#pragram pack() ,
    内部长度最长的数据成员)的整数倍地址开始存储。(struct a里存有struct
    b,b里有char,int,double等元素,那b应该从min(#pragram pack(), 8)的整数倍开始存储。)
  • 收尾工作:结构体的总大小,也就是sizeof的结果,.必须是 min(#pragram pack() , 长度最长的数据成员) 的整数倍
  • #pragram pack() 默认为4(32位), 8(64位)
    • 为了访问未对齐的内存,处理器需要作两次内存访问;而对齐的内存访问仅需要一次访问。
    • 平台原因(移植原因):不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。

构造函数

  • 默认构造函数。不需要任何参数
  • 拷贝构造
  • 赋值构造
  • 移动构造
  • 移动赋值

引用和指针实现多态

  • 子类指针赋值给父类指针,仅仅是让基类指针指向子类对象的地址,而子类对象的虚函数表中保存的是自己的子类虚函数的地址,已经对父类的虚函数进行过覆盖。
  • 子类对象赋值给父类对象。首先,普通的赋值函数不会进行虚函数表的赋值,其次,对象去访问成员的虚函数并不通过虚函数表。
  • 引用本质上也是通过指针的解引用(即*_point)来实现的
  • 引用在C++中的内部实现是一个常量指针
  • 一个空的class的对象的大小为1个字节, 编译器之所以要这么做,是为了区别同一个类类型的不同对象!

构造函数的几种关键字(default delete 0)

  • = default:将拷贝控制成员定义为=default显式要求编译器生成合成的版本
  • = delete:将拷贝构造函数和拷贝赋值运算符定义删除的函数,阻止拷贝(析构函数不能是删除的函数 C++Primer P450)
  • = 0:将虚函数定义为纯虚函数(纯虚函数无需定义,= 0只能出现在类内部虚函数的声明语句处;当然,也可以为纯虚函数提供定义,不过函数体必须定义在类的外部)

成员模板

  • 1
    2
    版权声明:本文为CSDN博主「醉美遇见你倾城」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/yy19961124/article/details/88562009
  • 一个类(普通类/模板类)都可以包含本身是模板的成员函数。成员模板不能是虚函数

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      template<typename T>
      class Blob{
      template<typename It> Blob(It a,It b);
      }
      //在类模板外部进行其成员模板的函数体定义时,需要同时为类模板和成员模板提供模板参数列表。
      template<typename T>
      template<typename It>
      Blob<T>::Blob(It a,It b)
      :
      {}

      Blob<int> s2(vi.begin(),vi.end());
  • 显示实例化。由于模板被使用时才会被实例化,但是有时候相同的实例可能在不同的对象文件中会使用到,当多个独立编译的源文件使用了相同的模板,并提供了相同的模板参数,每个文件中就都会有一个模板的实例,所产生的开销将会很大。

    • 1
      2
      3
      4
      5
      extern template class Blob<string>;             //声明
      template int comare(const int&, const int&); //定义
      /*
      编译器遇上extern模板声明时,不会再本文件中实例化。同时,将一个实例化声明为extern表示承诺在程序其他位置有该实例化的一个非extern声明(定义)。对于一个特定版本的实例化,可能有多个extern,但必须只有一个定义。
      */
  • 类型转换和模板类型参数。将实参传递给带模板类型的函数形参时,能够自动应用类型转换的只有const转换及数组或函数到指针的转换

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      /*
      const转换:可以将一个非const对象的引用(或指针)传递给一个const的引用(或指针)形参。
      数组或函数指针转换:如果函数形参不是引用类型,则可以对数组或函数类型的实参应用正常的指针转换。一个数组实参可以转化为一个指向其首元素的指针。类似,一个函数实参可以转化为一个指向该函数类型的指针。
      */
      template <typename T> T fobj(T, T); //实参将被拷贝
      template <typename T> T fref(const T&, const T&); //引用

      string s1("a value");
      const string s2("another value");
      fobj(s1, s2); //调用fobj(string, string);const被忽略
      fref(s1, s2); //调用fref(const string&, const string&);将s1转化为const是允许的

      int a[10], b[20];
      fobj(a, b); //调用fobj(int*, int*)
      fref(a, b); //错误,对于一个引用形参参数来说,数组不会转化为指针。
  • 函数模板显式实参。有时候希望允许用户控制模板的实例化,可以指定显式模板实参。

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      例如,定义一个sum函数,允许用户指定返回结果类型来控制精度
      template <typename T1, typename T2, typename T3>
      T1 sum(T2, T3); //没有任何实参类型给编译器去推断T1的类型
      //因此每次调用sum时都必须为T1提供一个显式模板实参
      auto val3 = sum<long,long>(i, lng); //通过指定和实参,编译器推断为long long sum(int, long)

      ##注意##
      显式模板实参按从左向右的顺序与对应的模板参数匹配。只有尾部的显式模板实参才可以忽略。
      //糟糕的设计:用于必须指定所有三个模板参数
      template <typename T1, typename T2, typename T3>
      T3 sum(T1, T2);
      auto val2 = sum<long long, int, long>(i, lng);
  • 除了用户指定模板实参类型,可以选择通过尾置返回类型来判定。

    • 1
      2
      3
      4
      5
      6
      7
      //使用尾置来声明返回类型
      template <typename T>
      auto fcn(T beg, T end) -> decltyp(*beg)
      {
      //处理序列
      return *beg; //返回一个元素的引用
      }
  • 进行类型转化的标准库模板类

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      有时候,我们希望返回一个元素的值,而并非引用。
      为了获得元素类型,我们可以使用标准库的类型转换模板,这些模板定义在头文件type_traits中。
      //为了使用模板参数的成员,必须typename
      template <typename T>
      auto fcn2(T beg, T end) -> typename remove_reference<decltype(*beg)>::type
      {
      //处理序列
      return *beg; //返回序列中一个元素的引用
      }
  • 当参数类型无法确定模板实参的唯一类型,必须显式指出实例化哪个类型。

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      template <typename T> int compare(const T&, const T&);
      //pf1指向实例int compare(const int&, const int&)
      int (*pf1)(const int&, const int&) = compare;
      pf1中参数的类型决定了T的模板实参的类型。例子中T的模板实参类型为int
      指针pf1指向compare的int版本
      当出现重载版本,每个版本接收一个不同的函数指针类型,则需要显式指出实例化哪个版本
      //func重载
      void func(int(*)(const string&, const string&));
      void func(int(*)(const int&, const int&));
      func(compare); //错误用法,产生歧义,无法确定使用哪个版本的compare
      //正确用法
      func(compare<int>); //显式指出T为int类型,即compare(const int&, const int&)
  • 引用折叠

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      某些函数需要将其一个或多个实参连同类型不变的转发给其他函数。
      //接收一个可调用对象和另外两个参数的模板
      //版本一
      template <typename F, typename T1, typename T2>
      void flip1(F f, T1 t1, T2 t2)
      {
      f(t1, t2);
      }
      版本一在一般情况下可以较好的工作,但当我们希望能用它调用一个接收引用的参数时,就会出现问题:
      void f(int v1, int &v2)
      {
      cout << v1 << " " << ++v2 << endl;
      }
      这段f函数,改变了绑定到v2上的实参的值;
      但是,通过flip1调用f时,f所作的改变不会影响到实参
      f(42, i); //f改变了实参i
      flip1(f, 42, j); //通过flip1调用f不会改变j
      #原因#
      从模板参数列表中可以看到,由实参j推断出T1为int类型,于是j被传递过去的是int而不是int&。
      模板被实例化为void flip1(void(*fcn)(int, int&), int t1, int t2);


      //版本二
      void f(int v1, int &v2)
      {
      cout << v1 << " " << ++v2 << endl;
      }

      template <typename F, typename T1, typename T2>
      void flip2(F f, T1 &&t1, T2 &&t2)
      {
      f(t1, t2);
      }
      此处模板参数列表为右值引用,如果我们调用flip2(f, 42, j),则会传递给参数t2一个左值j
      但是,在flip2中,推断出的T2类型为int&,意味着t2的类型会折叠为int&。
      由于是引用类型,t2被绑定到j上,flip2调用f时,f的引用参数v2也绑定到t2,即绑定到f上。
      因此f递增v2也同时改变了j的值。
      #Note#
      如果一个函数参数是指向模板类型参数的右值引用(如T&&),它对应的实参的const属性和左值/右值属性可以得到保持

      由于flip2解决了一般问题。它对于接收一个左值引用的函数工作的很好,但不能接收右值引用参数的函数
      即:
      void f(int &&i, int &j)
      {
      cout << i << " " << j << endl;
      }
      当试图通过flip2调用g,则参数t2将被传递给g的右值引用参数。
      flip2(g, 42, j); //错误,不能从一个左值实例化int&&
      42 为右值,传递给flip2时T1推到为T1&&&&=T1&& 但是,无论传递参数为左值还是右值,普通传参都会将参数作为左值进行转发。所以T1 作为T1& 传递给f,由于f的第一个参数为int&&右值引用,只能绑定到右值上,so,出错!!!!!


      //版本三
      使用forward的新标准库来爆出原始实参类型,类似move,forward定义在头文件utility中
      forward必须通过显式模板实参来调用,forward返回该显式实参类型的右值引用。即
      forward<T> 返回类型为T&&
      //重写flip
      template <typename F, typename T1, typename T2>
      void flip(F f, T1 &&t1, T2 &&t2)
      {
      f(std::forward<T2>(t2), std::forward<T1>(t1));
      }
      #Note#
      std::move一样,使用时不用using声明,直接加上std::使用,std::forward
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      #include <iostream>
      #include <utility>
      void reference(int& v) {
      std::cout << "左值引用" << std::endl;
      }
      void reference(int&& v) {
      std::cout << "右值引用" << std::endl;
      }
      template <typename T>
      void pass(T&& v) {
      std::cout << "普通传参:";
      reference(v);
      std::cout << "std::move 传参:";
      reference(std::move(v));
      std::cout << "std::forward 传参:";
      reference(std::forward<T>(v));

      }
      int main() {
      std::cout << "传递右值:" << std::endl;
      pass(1);

      std::cout << "传递左值:" << std::endl;
      int v = 1;
      pass(v);

      return 0;
      }
      /*
      传递右值:
      普通传参:左值引用
      std::move 传参:右值引用
      std::forward 传参:右值引用
      传递左值:
      普通传参:左值引用
      std::move 传参:右值引用
      std::forward 传参:左值引用
      */
  • 函数模板特例化

    • 必须为原函数模板的每个模板参数都提供实参,且使用关键字template后跟一个空尖括号对<>,表明将原模板的所有模板参数提供实参。

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      template<typename T>
      int compare(const T& t1,const T&t2)
      {https://www.cnblogs.com/inception6-lxc/p/8686156.html#4355778
      if(t1>t2) return 1;
      if(t1<t2) return -1;
      else return 0;
      }
      template<>
      int compare(const string& t1,const string&t2)
      {
      return strcmp(t1,t2);
      }
  • 模板类特例化

    • 在类中,我们可以对模板进行特例化,也可以对类进行部分特例化。对类进行特例化时,仍然用template<>表示是一个特例化版本

    • 参数个数的特例化

    • 参数范围的特例化

      • 1
        2
        3
        4
        5
        6
        template<typename T,typename Alloc=......>
        class vector{}

        template<typename Alloc=....>
        class vector<bool,Alloc>
        {}
      • 1
        2
        3
        4
        5
        template<typename T>
        class C{}

        template<Typename T>
        class C<T*>{}

final VS override

  • final 限定某个类不能被继承或某个虚函数不能被重写。(非虚函数不能final)

    • 1
      2
      3
      4
      5
      struct A{
      virtual void fun() final;
      }
      struct B final: A()
      {}
  • override关键字保证了派生类中声明重写的函数与基类虚函数有相同的签名

struct VS class

  • 1.默认的继承访问权。class默认的是private,strcut默认的是public。

  • 2.默认访问权限:struct作为数据结构的实现体,它默认的数据访问控制是public的,而class作为对象的实现体,它默认的成员变量访问控制是private的。

  • “class”这个关键字还用于定义模板参数,就像“typename”。但关键字“struct”不用于定义模板参数

  • 关于使用大括号初始化

  • class和struct如果定义了构造函数的话,都不能用大括号进行初始化

    • 如果没有定义构造函数,struct可以用大括号初始化。
    • 如果没有定义构造函数,且所有成员变量全是public的话,class可以用大括号初始化。
  • —–以{}的方式来赋初值,只是用一个初始化列表来对数据进行按顺序的初始化

指针和引用区别

  • 指针是一个变量,这个变量存储指向内存的一个地址;而引用跟原来的变量是同一个东西,是原变量的一个别名
  • 可以有const指针,没有const引用
  • 指针可以有多级,引用只能有一级(int**p,int&&a)
  • 指针的值可以为Null,可以不用初始化,而引用在定义时必须初始化
  • 指针在初始化后可以改变其所指向的内存,指向其他的存储单元,而对象一经绑定,不可更改
  • sizeof(引用)得到的是原来的变量的大小,而sizeof(指针)是指针本身的大小
  • 指针和引用自增意义不同

main函数之前

  • main函数执行之前,初始化系统资源
    • 设置栈指针
    • 初始化static静态和global全局变量,即data段内容
    • 将未初始化部分的全局变量赋值,数值型short,int,long等为0,bool为FALSE,指针为NULL,等等,即.bss段的内容

main返回值

  • main函数的返回值,用于说明程序的退出状态。
  • 如果返回0,则代表程序正常退出;返回其它数字的含义则由系统决定。
  • main函数的返回值将被操作系统用作进程的退出代码,利用这个特性,我们可以使用返回值来标识某项任务是否成功执行。

C++内存模型

  • 20180805132942260
  • 栈区->堆区->未初始化数据段(bss),由exec是初始化为0->初始化的数据(全局变量、静态变量和常量数据)->正文
  • 正文 CPU执行机器指令部分
  • 初始化数据段,程序中明确赋初值的变量(全局变量、静态变量、常量数据(虚函数表))
  • 未初始化数据。内核将此段中数据初始化为0或空指针
  • 栈,自动变量以及每次函数调用时所需要保存的信息。
  • 堆 动态内存分配

面向对象的四个特性

  • 抽象。将一些事物的共性和相似点剥离出来,并将这些属性归为一个类
  • 封装。为了隐藏内部实现细节。
  • 继承。继承是子类自动共享父类数据和方法的机制,这是类之间的一种关系,提高了软件的可重用性和可扩展性。
  • 多态。程序定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编译期并不确定,而是在程序运行期间才确定(称之为动态绑定),即一个引用变量指向的是哪个类的实例对象,在编译期间并不确定,在运行阶段才能决定。

堆和栈的区别

  • 堆由低地址向高地址扩展;栈由高地址向低地址扩展。
  • 堆中内存需要手动申请和释放,栈中内存OS自动申请和释放,存放着参数、局部变量等内存
  • 堆中频繁调用malloc和free,产生内存碎片,降低程序效率;栈由于先进后出特性不会产生内存碎片
  • 堆的内存分配效率低,栈的分配效率高
  • 栈效率高原因
    • 栈为操作系统提供的数据结构,OS提供了一系列支持:分配专门的寄存器存储栈的地址,压栈和入栈有专门的指令执行;而堆是由C++函数库提供的,机制复杂,需要有分配内存、合并内存和释放内存的算法,效率低。

volatile

  • 遇到这个关键字声明的变量,编译器对访问该变量的代码就不再进行优化,从而可以提供对特殊地址的稳定访问
  • 系统总是重新从它所在的内存读取数据。而且读取的数据立刻被寄存,而不是将数据拷贝到寄存器,再从寄存器中读。
  • volatile用在如下的几个地方:
    1. 中断服务程序中修改的供其它程序检测的变量需要加volatile;
    2. 多任务环境下各任务间共享的标志应该加volatile;
    3. 存储器映射的硬件寄存器通常也要加volatile说明,因为每次对它的读写都可能由不同意义;

内联函数VS宏定义

  • 都是代码的替换。

  • 代码的逻辑都应该是简短的

  • 宏定义函数不会进行类型检查,因为只是进行简单的字符串替换,所以如果不注意的话,执行顺序可能会和预想的不一样,因为不会制作传入参数的临时拷贝,而只是进行简单的替换

  • 在编译阶段,编译器将内联函数展开,替换为等效的实现代码,而不是进行函数调用。

  • 内联函数不一定会被替换,如果代码过于复杂,编译器将不进行替换。而宏定义一定会被替换。

C++ VS C最大特点

  • 面向对象
  • 引用代替指针
  • const/inline/template 代替宏常量
  • namespace解决重名问题
  • STL提供高效的数据结构和算法
  • 模板编程

static_assert

  • 1
    static_assert(sizeof(void *) == 4, "64-bit code generation is not supported.");
  • static_assert关键字,用来实现编译期间的断言,叫静态断言。编译器在遇到一个static_assert语句时,通常立刻将其第一个参数作为常量表达式进行演算,但如果该常量表达式依赖于某些模板参数,则延迟到模板实例化时再进行演算,这就让检查模板参数成为了可能。

  • assert是运行期的判断,并且会强制终止程序,一般要求只能用于debug版本中,是为了尽可能快的发现问题。assert是要从release版本中去掉。所以一般开发会重新定义assert宏。

c++11新特性

  • 线程库
  • 右值引用与移动语义
  • auto
  • decltype
  • lambda
  • nullptr
  • ranged_base for
  • initialist list
  • 新增STL容器

访问类的私有变量

  • 定义get/set接口
  • 友元函数
  • 友元变量
  • 通过类对象的首地址+偏移!!! ridiculous

二维数组

  • 1
    2
    3
    4
    5
    6
    7
    int aaa[2][3] = { 1,2,3,4,5,6 };// aaa = 0x004ff850 {0x004ff850 {1, 2, 3}, 0x004ff85c {4, 5, 6}}
    cout << aaa << endl;//004FF850
    cout << aaa+1<<endl;//004FF85C 一维数组指针相加
    cout << *aaa << endl;//004FF850 数组中第一个元素的地址
    cout << *aaa + 1 << endl;//004FF854 一个元素的指针+1
    cout << **aaa << endl;//1
    cout << **aaa +1<< endl;//2

虚基类表

  • 在类中增加一个指针(VBPTR)指向一个VBTBL,这个VBTBL的第一项记载的是从VBPTR 与本类的偏移地址,如果本类有虚函数,内存中第一项为虚函数表指针,第二项才是虚基类表指针,所以虚基类表中第一项是FF FF FF FC(也就是-4),如果没有则是零,第二项起是VBPTR与本类的虚基类的偏移值。
  • 虚基类中第一项父亲1的虚函数表指针地址-父亲1对象的首地址
  • 虚基类中第二项为父亲1的对象的首地址-爷爷虚基类表指针的地址

extern C

  • c++ 中函数签名是函数名称+函数参数,以此实现函数重载

  • c中函数签名只有函数名称

  • 告诉编译器,被extern “C”修饰的函数或者变量是按照C语言方式编译和链接的

  • C++中调用C

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      //c++ cpp文件
      extern "c"
      {
      #include "cexample.h"
      }
      int main()
      {
      add(2,3);
      }
    • 1
      2
      3
      //c .h文件中 extern声明函数
      extern int add(int x,int y);
      //c .c文件中定义add
  • C中调C++

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      //c++ .h文件
      extern "C" int add(int x,int y);
      //c .c文件
      #include <cppexample.h>
      extern int add(int x,int y)
      int main()
      {
      add(2,3)
      }

编译型VS解释型VS动态语言VS静态语言

  • 编译型语言首先是将源代码编译生成机器指令,再由机器运行机器码(二进制)。
  • 解释型语言的源代码不是直接翻译成机器指令,而是先翻译成中间代码,再由解释器对中间代码进行解释运行。
  • 动态类型语言,是指数据类型的检查是在运行时做的
  • 静态类型语言,是指数据类型的检查是在运行前(如编译阶段)做的。

构造函数 VS析构函数

  • 构造函数不可以通过对象、对象的指针、对象引用直接调用
  • 析构函数可以通过对象、对象的指针、对象引用直接调用

C++对象数组的删除

  • 1
    2
    3
    4
    5
    6
    A arr[]=new A[5];//调用5次构造函数
    delete []arr;//析构5次

    //不是动态创建时,对象离开作用域时,自动调用析构
    A arr3[3];
    //如果在作用域内自己手动依次调用析构,那么在离开作用域时,编译器还是会调用析构,切记切记!!!

拷贝构造VS 赋值构造

  • 拷贝构造函数是一个对象初始化一块内存区域,这块内存就是新对象的内存区,而赋值函数是对于一个已经被初始化的对象来进行赋值操作。

  • 一般来说在数据成员包含指针对象的时候,需要考虑两种不同的处理需求:一种是复制指针对象,另一种是引用指针对象。拷贝构造函数大多数情况下是复制,而赋值函数是引用对象

  • 实现不一样。拷贝构造函数首先是一个构造函数,它调用时候是通过参数的对象初始化产生一个对象。赋值函数则是把一个新的对象赋值给一个原有的对象,所以如果原来的对象中有内存分配要先把内存释放掉,而且还要检察一下两个对象是不是同一个对象,如果是,不做任何操作,直接返回

  • 应用场景

    • 拷贝构造
      • 一个对象需要通过另一个对象进行初始化
      • 函数形参值传递
      • 函数返回值值传递
    • 赋值构造
      • 调用operator=,且被赋值对象存在时(已分配内存)

overload VS override VS overwrite

  • overload 函数重载
    • 相同的范围(同一个类中)
    • 函数名字相同
    • 参数不同(参数类型,参数长度)
  • override 覆盖 派生类函数覆盖基类虚函数
    • 不同范围(一个父类,一个子类)
    • 函数名字相同
    • 参数相同
    • 父类有virtual标识
  • overwrite 重定义派生类屏蔽了与其同名的基类函数
    • 如果派生类与基类函数同名,但是参数不同。此时无论是否有virtual,基类函数被隐藏
    • 如果派生类与基类函数同名,参数相同。基类没有virtual,基类函数被隐藏。

变量的声明和定义

  • 声明一个变量:变量名前+extern,并且不要显示的初始化变量

    • 1
      2
      3
      extern int j;
      int j;//声明并定义j,定义会分配空间
      extern double pi=3.1416;//定义

new的变种

  • malloc free标准库函数,new delete C++语言关键字

  • malloc失败返回空,new失败抛异常

  • new/delete会调用构造、析构函数,malloc/free不会,所以他们无法满足动态对象的要求。

  • new返回有类型的指针,malloc返回无类型的指针

  • malloc是从堆上动态分配内存,new是从自由存储区为对象动态分配内存。 自由存储区的位置取决于operator new的实现。自由存储区不仅可以为堆,还可以是静态存储区,这都看operator new在哪里为对象分配内存

  • new

    • 调用operator new分配内存,
    • 在分配的内存上调用构造函数
  • operator new

    • 1
      void* operator new  ( std::size_t count );
  • placement new

    • 保持一块内存,反复构造析构,这样可以省略中间的多次分配内存。

    • 1
      2
      3
      4
      char* ptr = new char[sizeof(T)]; // allocate memory  
      T* tptr = new(ptr) T; // construct in allocated storage ("place")
      tptr->~T(); // destruct
      delete[] ptr; // deallocate memory

特殊对象构建

  • https://blog.csdn.net/hxz_qlh/article/details/13135433#

  • 一个只能在堆上建立的对象

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class A
    {
    protected:
    A(){}
    ~A(){}
    public:
    static A* create()
    {
    return new A();
    }
    void destory()
    {
    delete this;
    }
    };
    • 一个只能在栈上建立的对象
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class A
    {
    private:
    void* operator new(size_t t){} // 注意函数的第一个参数和返回值都是固定的
    void operator delete(void* ptr){} // 重载了new就需要重载delete
    public:
    A(){}
    ~A(){}
    };
  • 不能被继承的类

    • 1
      2
      3
      class A final{

      }//C++11实现
* 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T>
class Base{
friend T; //T为Base的友元 不需要class
private:
Base(){
cout << "base" << endl;
}
~Base(){}
};
class B:virtual public Base<B>{ //一定注意 必须是虚继承
public:
B(){
cout << "B" << endl;
}
};
* 某个继承B的类X,在构造的时候必须要构造Base,但是B虚继承至Base,X不能通过B的构造函数来构造Base,但是由于Base的构造是private的,所以X不能构造。 * 虚继承时,由最低层次的派生类的构造函数去初始化虚基类,由于虚基类的构造函数为private * 友元不可继承,不可传递

内存分配方式

  • 栈区,编译器自动分配释放,存放函数的参数,局部变量

  • 堆区,由程序员分配释放,

  • 全局/静态区,全局变量和静态变量存放在一起,编译时分配

  • 文字常量区,存放常量字符串

  • 程序代码区,存放函数体(类成员函数,全局函数)的二进制码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const char arr1[] = { "abcdef" };//arr1 = 0x00d8fdf0 "abcdef"
    const char arr2[] = { "abcdef" };//arr2 = 0x00d8fde0 "abcdef"
    char arr3[] = {"abcdef"};//arr3 = 0x00d8fdd0 "abcdef"
    char arr4[] = {"abcdef"};//arr4 = 0x00d8fdc0 "abcdef"

    char* arr5 = { "abcdef" };//arr5 = 0x00772cf0 "abcdef"
    char* arr6 = { "abcdef" };//arr6 = 0x00772cf0 "abcdef"

    const char* arr7 = { "abcdef" };//arr7 = 0x00772cf0 "abcdef"
    const char* arr8 = { "abcdef" };//arr8 = 0x00772cf0 "abcdef"
    /*
    字符串常量存放于文字常量区,指针只需要指向就可以。
    而数组需要另外开辟一段内存存放该字符串
    c字符串比较 strcmp
    =0 相等
    >0 前大
    <0 前小
    */

static const关键字

  • static和const关键字的作用可以从两个方面回答:一是和类的成员函数或者成员变量相关,二是不属于类的函数或者变量。

    • static关键字的作用:

      • 1
        2
        3
        4
        5
        6
        7
        /*
        1.static 修饰局部变量,该变量静态生存周期,且只被初始化一次
        2.static 修饰全局变量,该变量静态生存周期,以及内部连接性,只能该文件访问
        3.static 修饰全局函数,该函数内部连接性,只能本文件访问
        4.static 修饰成员函数,该成员函数为类所有,没有this指针,只能访问static成员变量
        5.static 修饰成员变量,该成员变量为类所有,对类的所有对象只是一份拷贝
        */
    • const关键字的作用–只读

      • 1
        2
        3
        4
        5
        6
        7
        /*
        1、想要阻止一个变量被改变,可以使用const关键字。在定义该const关键字是,通常要对它进行初始化,因为以后再也没有机会去改变它。
        2、对于指针来说,可以指定指针本身为const,也可以指定指针所指向的数据为const,或者二者同时指定为const。
        3、在一个函数声明中,const可以修饰形参,表明它是一个输入参数,在函数内部不能改变其值。
        4、对于类的成员函数,若指定为const,则表明其实一个常函数,不能修改类的成员变量。
        5、对于类的成员函数,有时候必须制定其返回值为const,以使得其返回值不能为左值。典型operator[]
        */

define 和const的区别

  • 区别

    • 1
      2
      3
      4
      5
      6
      /*
      (1)就起作用的阶段而言: #define是在编译的预处理阶段起作用,而const是在 编译、运行的时候起作用。
      (2)就起作用的方式而言: #define只是简单的字符串替换,没有类型检查。而const有对应的数据类型,是要进行判断的,可以避免一些低级的错误。
      (3)就存储方式而言:#define不分配内存,给出的是立即数,只是进行展开,有多少地方使用,就替换多少次,它定义的宏常量在内存中有若干个备份;const,在静态存储区中分配空间,定义的只读变量在程序运行过程中只有一份备份。
      (4)从代码调试的方便程度而言: const常量可以进行调试的,define是不能进行调试的,因为在预编译阶段就已经替换掉了。
      */
  • const 优点

    • 1
      2
      3
      4
      5
      /*
      (1)const常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换,没有类型安全检查,并且在字符替换可能会产生意料不到的错误。
      (2)有些集成化的调试工具可以对const常量进行调试,但是不能对宏常量进行调试。
      (3)const可节省空间,避免不必要的内存分配,提高效率
      */

智能指针

  • 指向的均为堆中对象,new出来的

  • unique_ptr

    • 独占方式,一次只能有一个指针指向对象,不允许拷贝和赋值
    • 可通过临时对象或者move语义实现赋值
    • get函数获取原生指针
    • release放弃内部对象的所有权,内部指针置空,此指针需要手动释放
    • reset函数,销毁内部对象并接受新的对象
    • 对象被销毁以及内存释放的时机
      • 当离开作用域或者reset时,释放
  • shared_ptr

    • 通过引用计数实现共享,使得多个指针可以同时指向一个对象
    • use_count查看资源的所有者个数
    • 对象被销毁以及内存释放时机
      • 最后一个拥有该资源的shared_ptr destored
      • 最后一个拥有该资源的shared_ptr 通过operator=赋值给其他,或者reset,即引用计数为0时
  • weak_ptr

    • 解决shared_ptr相互应用时的死锁问题

    • 对对象的一种弱引用,不会增加对象的引用计数。和shared_ptr可以相互转换,shared_ptr赋值给weak_ptr,weak_ptr通过lock获得shared_ptr

    • 通过lock返回是否是null或者shared_ptr判断,所指向的对象是否已经被释放

    • 也可通过expired 返回true

    • 以及use_count==0

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      class B;
      class A
      {
      public:
      shared_ptr<B> pb_;
      ~A()
      {
      cout<<"A delete\n";
      }
      };
      class B
      {
      public:
      shared_ptr<A> pa_;
      ~B()
      {
      cout<<"B delete\n";
      }
      };
      void fun()
      {
      shared_ptr<B> pb(new B());
      shared_ptr<A> pa(new A());
      pb->pa_ = pa;
      pa->pb_ = pb;
      cout<<pb.use_count()<<endl;
      cout<<pa.use_count()<<endl;
      }
      shared_ptr<B> pb(new B());
      shared_ptr<A> pa(new A());
      pb->pa_ = pa;
      pa->pb_ = pb;
      cout<<pb.use_count()<<endl;
      cout<<pa.use_count()<<endl;
      /*
      2
      2
      */

移动语义

  • 移动语义–右值引用

    • 1
      2
      3
      int c;
      int&& a=5;
      int && b=c;//error只能绑定右值
    • 在一个有动态内存分配的类中,其拷贝构造函数,一定要实现深拷贝,涉及内存的分配,内存的拷贝

    • 虽然右值引用参数绑定了右值,不过在函数内部,会当做左值来进行

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        X{
        private
        int* x;
        X(const X& other): // 1
        data(new int[1000000])
        {
        std::copy(other.data,other.data+1000000,data);
        }
        X (X&& other): // 2移动构造函数,实现浅拷贝
        data(other.data)
        {
        other.data=nullptr;
        }
        }
        void do_stuff(X&& x_)
        {
        X a(x_); // 拷贝
        X b(std::move(x_)); // 移动
        }
        do_stuff(X()); // ok,右值绑定到右值引用上
        X x;
        do_stuff(x);
      • unique_ptr 只支持移动构造不支持拷贝构造

    • 使用static_cast<X&&>或者move 将左值转换为右值

  • 如果函数模板参数以右值引用作为一个模板参数,当对应位置提供左值的时候,模板会自动将其类型认定为左值引用;当提供右值的时候,会当做普通数据使用

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      template<typename T>
      void foo(T&& t)
      {}

      foo(42); // foo<int>(42)
      foo(3.14159); // foo<double><3.14159>
      foo(std::string()); // foo<std::string>(std::string())

      int i = 42;
      foo(i); // foo<int&>(i)//引用的引用还是引用
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      template< class T >
      typename std::remove_reference<T>::type&& move( T&& t ) noexcept;
      //返回值
      static_cast<typename std::remove_reference<T>::type&&>(t)

      template< class T > struct remove_reference {typedef T type;};
      template< class T > struct remove_reference<T&> {typedef T type;};
      template< class T > struct remove_reference<T&&> {typedef T type;};
      //move本质上 是一个类型转换,本质上是通过static_cast实现的
  • forward

    • 解决在使用右值引用参数的函数模板中解决参数的完美转发问题。只有在它的参数绑定到一个右值上的时候,它才转换它的参数到一个右值

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      //常使用模式一个函数func1 去 转接 另一个函数func2时,直接去使用func2时问题不大
      template<typename T1,typename T2>
      void func1(T1&& t1,T2&& t2)
      {
      func2(forward<T1>(t1),forward<T2>(t2));
      }

      template <typename T>
      void CoreFun(T t)
      {
      cout << "CoreFun" << endl;
      }

      template <typename T>
      void ICoreFun(T&& t)
      {
      cout << "ICoreFun" << endl;
      CoreFun(t);
      }
      /*
      1. A& &变成A&
      2. A& &&变成A&
      3. A&& &变成A&
      4. A&& &&变成A&&
      */
      /*
      当我ICoreFun(lvalue);的时候ICoreFun的函数原型是ICoreFun(CMyString&)
      当我ICoreFun(rvalue);的时候ICoreFun的函数原型是ICoreFun(CMyString&&)的:
      虽然ICoreFun(CMyString("hello this is the rvalue")); 转换为了ICoreFun(CMyString&& t),但是,t是一个左值,所以CoreFun(t);的时候调用的是拷贝构造函数来构造t


      有没有办法,在上面的情况中,在CMyString&& t 传递给CoreFun(t)的时候,CoreFun(t)把t当作左值来处理呢?也就在t是CMyString&&类型的时候把t转换为右值,在t是CMyString& t类型的时候不转换。

      实现转发左值就调用拷贝构造函数,抓发右值就调用右值类型的拷贝构造函数,完美。
      */
      -------------------------------------
      template <typename T>
      void CoreFun(T t)
      {
      cout << "CoreFun" << endl;
      }

      template <typename T>
      void ICoreFun(T&& t)
      {
      cout << "ICoreFun" << endl;
      CoreFun(std::forward<T>(t));
      }
  • std::forward(u)有两个参数:T 与 u。当T为左值引用类型时,u将被转换为T类型的左值,否则u将被转换为T类型右值。如此定义std::forward是为了在使用右值引用参数的函数模板中解决参数的完美转发问题。

    std::move是无条件的转为右值引用,而std::forward是有条件的转为右值引用,更准确的说叫做Perfect forwarding(完美转发),而std::forward里面蕴含着的条件则是Reference Collapsing(引用折叠)。

    std::move不move任何东西。std::forward也不转发任何东西。在运行时,他们什么都不做。不产生可执行代码,一个比特的代码也不产生。

自定义函数

  • strcpy

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      char* strcpy(char* dst,const char* src)
      {
      if(dst==nullptr || src==nullptr)
      return nullptr;
      if(dst==src)
      return dst;
      char* temp=dstt;
      while((*dst++ = *src++)!='\0');
      return temp;
      }
  • 手写智能指针的实现(shared_ptr和weak_ptr实现的区别)

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      template<typename T> 
      class SmartPointer
      {
      public:
      SmartPointer(T* ptr)
      {
      ref=ptr;
      ref_count=(unsigned int*) malloc(sizeof(unsigned));
      *ref_count=1;
      }
      SmartPointer(const SmartPointer<T>& other)
      {
      ref=other.ref;
      ref_count=other.ref_count;
      ++*ref_count;
      }
      SmartPointer& operator=(SmartPointer<T>& other)
      {
      if(this==&other)
      return *this;
      if(--*ref_count==0)
      {
      clear();
      }
      ref=other.ref;
      ref_count=other.ref_count;
      ++*ref_count;

      return *this;
      }
      T& operator*()
      {
      return *ref;
      }
      T* operator->()
      {
      return ref;
      }
      ~SmartPointer()
      {
      if(--*ref_count==0)
      {
      clear();
      }

      }
      private:
      void clear()
      {
      delete ref;
      free(ref_count);
      ref=NULL;
      ref_count=NULL;
      }
      protected:
      T* ref;
      unsigned int* ref_count;
      };
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      template<typename T>
      class MyUniquePtr
      {
      public:
      explicit MyUniquePtr(T* ptr = nullptr)
      :mPtr(ptr)
      {}

      ~MyUniquePtr()
      {
      if(mPtr)
      delete mPtr;
      }

      MyUniquePtr(MyUniquePtr &&p) noexcept;
      MyUniquePtr& operator=(MyUniquePtr &&p) noexcept;

      MyUniquePtr(const MyUniquePtr &p) = delete;
      MyUniquePtr& operator=(const MyUniquePtr &p) = delete;

      T* operator*() const noexcept {return mPtr;}
      T& operator->()const noexcept {return *mPtr;}
      explicit operator bool() const noexcept{return mPtr;}

      void reset(T* q = nullptr) noexcept
      {
      if(q != mPtr){
      if(mPtr)
      delete mPtr;
      mPtr = q;
      }
      }

      T* release() noexcept
      {
      T* res = mPtr;
      mPtr = nullptr;
      return res;
      }
      T* get() const noexcept {return mPtr;}
      void swap(MyUniquePtr &p) noexcept
      {
      using std::swap;
      swap(mPtr, p.mPtr);
      }
      private:
      T* mPtr;
      };

      template<typename T>
      MyUniquePtr<T>& MyUniquePtr<T>::operator=(MyUniquePtr &&p) noexcept
      {
      swap(*this, p);
      return *this;
      }

      template<typename T>
      MyUniquePtr<T> :: MyUniquePtr(MyUniquePtr &&p) noexcept : mPtr(p.mPtr)
      {
      p.mPtr == NULL;
      }

STL

  • 六大部件,空间配置器,容器,迭代器,适配器,算法,仿函数

  • 不提供遍历行为的容器(不提供迭代器)

    • stack
    • queue
    • priority-queue
  • C++11新增

    • unordered 系列
    • array
    • forward_list
    • tuple

空间配置器

  • 构造和析构
    • 构造调用placement_new,调用相应类的构造函数
    • 析构根据是否trivial_destructor调用不同版本函数模板
  • 空间配置器
    • 第一级配置器,
      • allocate调用malloc,deallocate调用free
      • 模拟C++的set_new_handler处理内存不足情况(客户端责任)
      • 不断释放、配置,再释放、再配置
    • 二级空间配置器,当所申请的内存小于128字节时,调用
      • 避免小额区块带来的内存碎片以及额外负担(cookie)
      • 维护16个自由链表,负责16种(8-128)小型区块的次配置能力,内存池以malloc配置而得,如果内存不足,转而调用第一级配置器
        1. 如果需求块大于128byte,调用第一级配置器
        2. 如果freelist有可用的区块,直接返回节点,链表依次调整(链表头指向下一个可用的list节点)
        3. 如果没有可用区块,调整需求为8的倍数,从内存池中取默认20个区块(节点),可能小于20个
          1. 如果内存池剩余空间满足需求,直接返回
          2. 如果内存池只能够一个区块,返回
          3. 如果内存池一个区块都没有,调整内存池的剩余空间,并malloc配置heap空间补充内存池,期间自调用,确定是否已经完成内存空间的分配,如果不行,再调用第一级空间配置器,如果可以,直接返回
      • deallocate释放内存时,如果大于128字节,直接free,否则加入到链表中
    • 刚开始初始化内存池时,内存池中没有数据,同时所有链表均为空
    • 只有用户第一次向内存池申请内存,内存池才会完成内存池以及链表的首次填充,此时其他未使用的链表依然是空的

迭代器

  • 萃取机BIG FIVE
    • reference type
    • difference_type
    • value_type
    • pointer
    • iterator_category
  • 迭代器种类用struct表示, 输入迭代器,输出迭代器,前向迭代器,双向迭代器,随机迭代器
    • random-access
      • array/vector/deque
    • bidirectional
      • list/rb-tree
    • forward
      • forwared-list
    • hashtable
      • 根据底层链表实现

vector实现

  • 维护三个迭代器
    • start begin()
    • finish end()
    • end_of_storage 目前可使用空间的尾
  • 动态增加内存,而是以原大小2倍另外重新配置空间,迭代器失效问题
  • erase 或者insert 之后的迭代器失效,理论上,每次insert、erase后,所有的迭代器重新计算,所以都看作是失效的,原则是不能使用过期的内存。

list实现

  • 环状双向链表,用一个指针Node表示,insert、splice均不会引起迭代器失效,
  • 指针Node刻意置于尾端的一个空白节点
  • 以节点为单位存储数据,节点的地址在内存中不一定连续,每次插入或者删除一个元素,就配置或者释放一个元素空间
  • list merge 将两个list合并成一个,前提是必须经过递增排序
  • list sort 排序
    • 将前两个元素合并,再将后两个合并,然后合并这两个子序列为4个元素的子序列,重复,依次得到8,16,。。子序列,最后得到的就是排序后的序列 时间复杂度O(logN)
    • 归并排序

deque实现

  • 对deque的排序,可以复制到vector上进行排序,后续复制到deque
  • deque VS vector
    • deque允许常数时间内对头端进行元素的插入和移除操作
    • deque没有容量观念,它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并连接起来
  • deque以分段连续的空间组合构成,通过中控器map连接而成,map为一段连续空间,每个元素(节点)为指针,均指向另一段连续性空间(缓冲区,默认512字节)
  • deque迭代器
    • cur指向当前缓冲区,当前所指元素
    • first当前缓冲区的头
    • last当前缓冲区的尾
    • map_pointer node 指向中控器
  • deque 维护迭代器
    • iterator start 第一个缓冲区的第一个元素 begin()
    • iterator end 最后一个缓冲区的最后一个元素的下一个位置 end()
    • map_pointer map指向中控器
    • size_type map_size map中有几个指针
  • push_back时,在最后一个节点的缓冲区从左往右push,如果缓冲区剩余个数大于2个,直接填充,否则,填充一个,缓冲区满,再扩充map
  • push_front时,在第一个节点的缓冲区从右往左push,若有空间则填充,否则扩充map

priority_queue

  • 没有迭代器,最大堆实现(vector表现的完全二叉树)

set-map实现

  • 底层红黑树

  • set 迭代器 const iterator,不可以通过迭代器修改元素

  • set map 同list相同,当客户端对它进行元素insert和erase后,操作之前的所有迭代器在操作完成之后依然有效

  • 自定义类提供compare函数

  • 红黑树执行插入、删除、查找时间复杂度logN

  • set/map插入删除效率高

    • 不需要内存的拷贝和移动
  • set/map每次insert、erase后之前保存的iterator不会失效

    • 插入操作只是结点指针换来换去,结点内存不变,而iterator就像指向结点的指针,内存不变,指向内存的指针也不变

unordered-set/map实现

  • 底层 hashtable 不具有排序功能
  • 自定义类提供hash函数以及等于函数
  • unordered-map VS map
    • 构造函数:unordered-map 提供hash 函数和等于函数,map提供比较函数
    • 存储结构:unordered-map 底层 hashtable,不提供排序功能,map底层 rb-tree,提供排序功能
    • hash-map 查找速度快,查找速度和数据量大小无关,常数级别,map查找速度 logN
    • 考虑效率,当元素数量到达一定数量级时,用unordered-map
    • 考虑内存,或者元素数量较少用map
    • 选用unordered-map还是map,关键看关键字查询操作次数,以及所要保证的是查询总体时间还是单个查询的时间。如果很多次操作,要求其整体效率,使用hash-map,平均处理时间短。如果少数次操作,使用hash-map导致不确定的O(N)。map用在平均处理时间相对较慢,单次处理事件恒定,整体稳定性高于整体效率,前提是操作次数少。

算法

  • C++11 多线程

  • 线程安全队列

  • 线程池

  • 自旋锁spinlock VS 互斥锁mutex

    • 自旋锁是一种非阻塞锁,也就是说,如果某线程需要获取自旋锁,但该锁已经被其他线程占用时,该线程不会被挂起,而是在不断的消耗CPU的时间,不停的试图获取自旋锁。
    • 互斥量是阻塞锁,当某线程无法获取互斥量时,该线程会被直接挂起,该线程不再消耗CPU时间,当其他线程释放互斥量后,操作系统会激活那个被挂起的线程,让其投入运行。
      • 如果是多核处理器,如果预计线程等待锁的时间很短,短到比线程两次上下文切换时间要少的情况下,使用自旋锁是划算的。
        如果是多核处理器,如果预计线程等待锁的时间较长,至少比两次线程上下文切换的时间要长,建议使用互斥量。
        如果是单核处理器,一般建议不要使用自旋锁。因为,在同一时间只有一个线程是处在运行状态,那如果运行线程发现无法获取锁,只能等待解锁,但因为自身不挂起,所以那个获取到锁的线程没有办法进入运行状态,只能等到运行线程把操作系统分给它的时间片用完,才能有机会被调度。这种情况下使用自旋锁的代价很高。

    linux命令

    • chmod

      • 1
        2
        3
        rw-r--r--
        r:4 w:2 x:1
        //文件所有者权限+文件所属组的权限+其他用户的权限

操作系统

文件系统的理解(EXT4,XFS,BTRFS)

文件处理grep,awk,sed这三个命令必知必会

IO复用的三种方法(select,poll,epoll)深入理解,包括三者区别,内部原理实现?

Epoll的ET模式和LT模式(ET的非阻塞)

查询进程占用CPU的命令(注意要了解到used,buf,cache代表意义)

linux的其他常见命令(kill,find,cp等等)

shell脚本用法

硬连接和软连接的区别

文件权限怎么看(rwx)

文件的三种时间(mtime, atime,ctime),分别在什么时候会改变

Linux监控网络带宽的命令,查看特定进程的占用网络资源情况命令

内存管理

  • 内存的连续分配

    • 单一连续分配

      • 内存在此方式下分为系统区、用户区。
      • 系统区提供给操作系统使用,通常在低地址
      • 用户区给用户使用
      • 优点-简单,无内存碎片,可以采用覆盖技术,不需要额外的技术支持
      • 缺点-只能适用于单用户、单任务的操作系统中,有内部碎片,存储器的利用率极低
    • 固定分区分配

      • 最简单的一种多道程序存储管理方式
      • 将用户空间划分为若干个固定大小的区域,每个分区只装入一道作业
      • 当有空闲分区时,再从外存的后备作业队列中,选择合适大小的作业装入该分区,如此循环
      • 分区可以相等也可以不相等
      • 存在问题
        • 程序可能太大而放不进去任何一个分区,不得不采用覆盖技术来使用内存空间
        • 主存利用率低,当程序小于固定分区大小时,也占用了一个完整的内存分区空间,产生内部碎片。
    • 动态分区分配

      • 又称可变分区分配,不预先将内存划分,而是在进程装入内存时,根据进程的大小动态的建立分区,并使分区的大小正适合进程的需要,系统中分区的大小和数目是可变的
      • 动态分区分配算法
        • 首次适应算法:空闲分区以地址递增的次序连接。分配内存时顺序查找,找到第一个能满足要求的第一个空闲分区
        • 最佳适应算法:空闲分区按照容量递增的顺序连接,找到第一个满足要求的空闲分区
        • 临近适应算法:从当前位置开始,搜索第一个满足进程要求的内存空间
  • 内存的非连续分配

    • 页式存储

      • 基本思想:用户程序的地址空间划分为固定大小的区域,称为页,相应内存空间也分为若干个物理块或页帧,页和块大小相等。将用户程序的任一页放在内存的任一块中,实现了离散分配;物理块不一定连续。每个页对应一个物理块。

      • 逻辑地址结构:地址结构包含两部分。一个页表项占用四个字节,前20bit表示页号P,后12bit,表示页内偏移W。地址空间最多允许2^20页。

      • 页表:程序数据存放在不同的页面中,而页面又离散的分散在内存中,需要一个页表来记录逻辑地址和实际存储地址之间的映射关系,以实现页号到物理块号的映射。

      • PS

        • 每个进程也以块为单位进行划分。每一个进程都拥有一个自己的页表,PCB表中有指针指向页表。

          分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

      • 地址变换-将逻辑地址转换为内存中的物理地址,借助于页表

        • 当程序执行时,将页表起始地址F和长度M存入页表寄存器
        • 设页大小为L(一般4K(2^12B)),逻辑地址A-》物理地址E
        • 20190128164450968
        • 计算页号P=A/L和业内偏移量W=A%L;
        • 比较页号P和页表长度M,如P》=M产生越界中断,否则继续执行
        • 页表中页号P对应页表项地址b=页表起始地址F+页号P*页表项长度(4B),取出页表项中的内容,即为物理块号b
        • 计算E=b*L+M,用得到的物理地址E去访问内存
      • 存在问题

        • 每次访问内存操作都需要进行逻辑地址到物理地址的转换,地址转换必须非常快,否则访问内存效率低
        • 每个进程引入了页表,用于内存映射机制,页表不能太大,否则内存利用率低
      • 具有快表的地址变换结构

        • 若页表全部放在内存中,则取出一个数据或一条指令至少要访问两次内存
        • 一次:从内存中访问页表,从中找到指定的物理块号,加上页内偏移量得到实际物理地址
        • 二次:根据第一次得到的物理地址访问内存并取出数据
        • 为提高地址变换速度,增设一个具有并行查询能力的特殊高速缓冲存储区,称为联想存储器或快表。存放当前访问的页表项。于此对应,主存中的页表为慢表
        • 20190128165747507
        • 访问过程
          • 逻辑地址的页号P直接在快表中查找,如果找到,得到对应的块号,直接转换为物理块号,这样存取数据仅需要一次访问内存就可以实现
          • 若找不到,则访问慢表,在读出页表项后,同时将其存入块表
        • 理论依据:局部性原理
          • 时间上的局部性:最近访问的页在不久的将来还会被访问
          • 空间上的局部性:内存中被访问的页周围的页很可能也被访问
      • 二级页表

        • 解决问题:如果内存的逻辑地址很大,将会导致程序的页表项很多,而页表在内存中是连续存放的,所以就需要很大的连续空间。
        • 一个页表项负责一页到一块(一页帧)的转换
        • 一个进程占用2^32=4G字节,页表中每个条目是4字节(一个页表项4B),假设一页4K个字节,需要2^32/4K=2^20个页表项,需要2^20*4字节=4M字节大小
        • 外层页表一次调入且连续存放,内存页表离散存放
        • 一共需要访问3次内存:访问顶级页表-》二级页表-》访问内存中的数据
        • 20160425230849959
        • 两级页表中,第一级为页目录,存在一个4K=2^12字节的页面中。页目录表共有1K=2^10个表项,每个表项为4个字节,并指向二级页表。线性地址的最高10bit产生第一级的索引,由索引得到的表项中指定并选择了1k个二级表中的表。
        • 第二级为页表。也存在其一个4K字节的页面中,包含1K个字节的表项,每个表项包含一个页的物理基地址。第二级页表由线性地址的中间10bit进行索引,以获得包含页的物理地址的页表项,这个物理地址的高20bit与线性地址的第12bit形参了最后的物理地址。
        • 一级页目录存放的是,二级页表的表头的地址
        • 二级页表存放的是某页在内存中的物理块号
        • 1334370490_3589
    • 段氏存储

      • 分页为了提高内存利用率,提升计算机的性能,且分页通过硬件机制实现,对用户完全透明

      • 分段是为了满足程序员在编写代码的时候一些逻辑需求

      • 思想

        • 将用户程序地址空间分成若干个大小不等的端,每段定义一组相对完整逻辑信息,每个段内部从0开始编址。存储时,以段为单位,每个段内部连续分配内存,段与段在内存中不相临接,实现了离散分配。例如,用户进程,有主程序、两个子程序、栈和一段数据组成。
      • 逻辑地址结构:段号S与段内偏移量W组成。如果为32地址,段号为16,段内偏移为16,则一个作业最多有2^16=65536个段,最大段长65536B即64KB。

        • 20190128174333124
        • 页式系统中,逻辑地址的页号和页内偏移量对用户是透明的,但在段式系统中,段号和段内偏移量必须由用户显示提供,在髙级程序设计语言中,这个工作由编译程序完成
      • 段表:每个进程都有一张逻辑空间与内存空间映射的段表,其中每一段表项对应进程的一个段。

        • 20190128174734675
        • 访问内存的时候根据段号段表项的长度计算当前访问段在段表中的位置,然后访问段表,得到该段的物理地址,根据该物理地址以及段内偏移量就可以得到需要访问的内存
      • 地址变换

        • 段表寄存器存了段表始址F和段表长度M,逻辑地址A物理地址E之间的地址变换过程如下:
        • 从逻辑地址A中取出段号S,段内偏移量W
        • 比较段号S和段表长度M,若S多M,产生越界中断,否则继续执行
        • 计算段号S对应的段表项地址=段表起始地址F+段号S*段表项长度,取出该段表项的前几位得到段长C。若段内偏移量>=C,则产生越界中断,否则继续执行
        • 取出段表项中该段的起始地址b,E=b+W,用得到的物理地址E访问内存
        • 20190128174904564
      • 段的共享

        • 允许若干个进程共享一个或多个分段

        • 通过两个作业的段表中相应表项执行被共享的段的同一个物理副本来实现的

        • 不能修改的代码称为纯代码或可重入代码(不属于临界资源),这样的代码和不能修改的数据时可以共享的

        • 而可修改的代码和数据不可共享

        • 可重入代码:允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同,

          绝对不允许可重入代码在执行中有任何改变。因此,可重入代码是一种不允许任何进程对它进行修改的代码

        • 但事实上,大多数代码在执行时都可能有些改变,例如,用于控制程序执行次数的变量以及指针、信号量及数组等。为此,在每个进程中,都必须配以局部数据区,把在执行中可能改变的部分拷贝到该数据区,这样,程序在执行时,只需对该数据区(属于该进程私有)中的内容进行修改,并不去改变共享的代码,这时的可共享代码即成为可重入码

    • 分页与分段的区别

      • 段优点

        • 优点-没有内部碎片,因为段大小可变,改变段大小来消除内部碎片
        • 缺点-段换入换出时,产生外部碎片,(比如4k的段换5k的段)产生1k的外碎片
        • 优点-没有外部碎片(页大小相同)
        • 缺点-产生内部碎片(一个页可能填不满)
      • 区别

        • 目的不同:分页是由于系统管理的需要而不是用户的需要,它是信息的物理单位;分段的目的是为了更好的满足用户的需要,是信息的逻辑单位,含有一组意义相对完整的信息。

        • 大小不同:页的大小固定且由系统决定(一般4K),段的长度不固定,由所完成的功能决定

        • 地址空间不同:段向用户提供二维地址空间;页向用户提供一维地址空间;一个段在物理空间是连续的内存。分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需利用一个记忆符,即可表示一个地址;而分段的作业地址空间是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址

        • 信息共享:段是信息的逻辑单位,便于存储保护和信息的共享,页是信息的物理单位,保护和共享受限

        • 内存碎片:页没有外碎片,产生内部碎片。段没有内碎片,换入换出时产生外碎片

    • 段页式存储

      • 页存储能有效的提高内存利用率,而分段存储能反映程序的逻辑结构并有利于段的共享
      • 思想
        • 作业的地址空间首先被分为若干个逻辑段,每个段有自己的段号
        • 再将每一段分成若干个大小固定的页
        • 对内存空间的管理仍然和分页管理一样,将其分成若干个和页面大小相同的块,对内存的分配以块为单位
        • 20190128180745482
        • 每个进程建立一张段表,每个分段有一张页表
    • 虚拟内存

      • 思想
        • 在程序装入时,将程序的一部分装入内存,将其剩余部分留在外存,启动程序执行。在执行过程中,当所访问的信息不再内存中时,由操作系统将所需要的部分调入内存,然后继续执行
        • 虚拟内存容量=内存+外存
        • 原理-局部性原理
        • 实现方式
          • 请求分页式存储管理
          • 请求分段式存储管理
          • 请求段页式存储管理
      • 请求分页式存储管理
        • 地址变换
          • 将当前需要的一部分页面装入内存,便可以启动作业运行。在作业执行过程中,当所要访问的页面不在内存时,再通过调页功能将其调入,同时还可以通过置换功能将暂时不用的页面换出到外存上,以便腾出内存空间
          • 20190128185944131
          • 缺页中断处理
            • 如果内存中有空闲块,则分配一个块,将要调入的页装入该块
            • 若此时内存中没有空闲块,则要淘汰某页
            • 若被淘汰的页在内存期间被修改过,则要将其写回外存
        • 页面置换算法
          • 最近最久未使用页面置换算法LRU
          • 最优页面置换算法
            • 所选择的被淘汰页面将是最长时间内不再被访问的页面
          • 先进先出页面置换算法(FIFO)
            • 总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予淘汰。
            • 缺点:对于有些经常被访问的页面如含有全局变量、常用函数、例程等的页面,不能保证这些不被淘汰。
        • 页面抖动(颠簸
          • 频繁的页面调度行为,具体来讲,进程发生页面中断,这时,必须置换一页。然而,其他所有的页都在使用,它置换一页后,又立刻需要这个页。因此,会不断产生缺页中断,导致整个系统的效率急剧下降。
          • 解决策略
            • 如果是页面置换策略失误,修改页面置换算法
            • 如果是运行的程序太多,造成程序无法同时将所有频繁访问的页面调入内存,则要降低多道程序的数量
            • 终止该进程或者增加物理内存容量
        • 驻留集大小

可重入函数

  • 在实时系统的设计中,经常会出现多个任务调用同一个函数的情况,不同任务调用这个函数时可能修改其他任务调用这个函数的数据,从而导致不可预料的后果
  • 一个可重入的函数简单来说就是可以被中断的函数,也就是说,可以在这个函数执行的任何时刻中断它,转入OS调度下去执行另外一段代码,而返回控制时不会出现什么错误
  • 首先它意味着这个函数可以被中断,其次意味着它除了使用自己栈上的变量以外不依赖于任何环境(包括
    static),这样的函数就是purecode(纯代码)可重入,可以允许有该函数的多个副本在运行,由于它们使用的是分离的栈,所以不会互相干扰。如果确实需要访问全局变量(包括static),一定要注意实施互斥手段。可重入函数在并行运行环境中非常重要,但是一般要为访问全局变量付出一些性能代价。
  • 保证函数的可重入性的方法
    • 在写函数时候尽量使用局部变量(例如寄存器、堆栈中的变量);
    • 对于要使用的全局变量要加以保护(如采取关中断、信号量等互斥方法),这样构成的函数就一定是一个可重入的函数。
  • 满足下列条件的函数多数是不可重入(不安全)的:
    • 函数体内使用了静态的数据结构;
    • 函数体内调用了malloc() 或者 free() 函数;
    • 函数体内调用了标准 I/O 函数。
  • 将一个不可重入的函数改写成可重入函数
    • 不要使用全局变量。因为别的代码很可能改变这些变量值。
    • 在和硬件发生交互的时候,切记执行类似 disinterrupt() 之类的操作,就是关闭硬件中断。完成交互记得打开中断,在有些系列上,这叫做“进入/ 退出核心”
    • 不能调用其它任何不可重入的函数
    • 谨慎使用堆栈
  • 常见可重入函数
    • accept,socket,send,close,connect,fork,write,shutdown

copy on write

  • linux中fork后,子进程会调用exec函数,

  • P1 fork P2子进程

    • P2 (虚拟空间和物理空间)有自己的数据段,堆,栈,
    • P2的代码段的虚拟空间复制P1代码段的虚拟空间,P1 P2共享代码段的物理空间
    • 20180531111209270
  • 写时复制

    • P2的正文段,数据段,堆,栈有自己的虚拟空间,P1 P2共享物理空间
    • 2018053111122476
  • vfork

    • P2 P1共享虚拟空间,相应的也共享物理空间
    • 20180531111239523

页面置换算法

  • 地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法
  • 最优页面置换
  • LRU页面置换
  • 先进先出(FIFO)
  • 最近未使用(NRU)
  • 第二次机会算法
  • 时钟算法

进程调度

  • 先来先服务算法 FCFS

    • 有利于长作业,而不利于短作业,有利于CPU繁忙的作业,而不利于I/O繁忙的作业。
  • 最短作业优先(SJF)

    • 相比FCFS 算法,该算法可改善平均周转时间和平均带权周转时间,缩短进程的等待时间,提高系统的吞吐量。长进程可能一直得不到执行
  • 时间片轮转算法(RR)

    • 让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式,即将系统中所有的就绪进程按FCFS 原则,排成一个队列,每次调度时将CPU 分派给队首进程,让其执行一个时间片,时间片的长度从几个ms 到几百ms。在一个时间片结束时,发生时钟中断,调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程,进程可以未使用完一个时间片,就出让CPU(如阻塞)
    • 时间片轮转调度算法的特点是简单易行、平均响应时间短,不利于处理紧急作业,且时间片的选取是否合理也是一个问题
  • 多级反馈队列(MFQ)–根据先来先服务原则给就绪队列排序,为就绪队列赋予不同的优先级数,不同的时间片,按照优先级抢占CPU的调度算法

    • 按照先来先服务原则排序,设置N个就绪队列为Q1,Q2…QN,每个队列中都可以放很多作业
    • 为这N个就绪队列赋予不同的优先级,第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低;
    • 设置每个就绪队列的时间片,优先权越高,算法赋予队列的时间片越小。时间片大小的设定按照实际作业(进程)的需要调整
    • 进程在进入待调度的队列等待时,首先进入优先级最高的Q1等待。
    • 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程。例如:Q1,Q2,Q3三个队列,只有在Q1中没有进程等待时才去调度Q2,同理,只有Q1,Q2都为空时才会去调度Q3。
    • 对于同一个队列中的各个进程,按照时间片轮转法调度。比如Q1队列的时间片为N,那么Q1中的作业在经历了时间片为N的时间后,若还没有完成,则进入Q2队列等待,若Q2的时间片用完后作业还不能完成,一直进入下一级队列,直至完成。
    • 在低优先级的队列中的进程在运行时,又有新到达的作业,那么在运行完这个时间片后,CPU马上分配给新到达的作业即抢占式调度CPU。
  • linux 进程调度

    • O(n)调度器把时间分成大量的微小时间片(Epoch)。在每个时间片开始的时候,调度器会检查所有处在就绪状态的进程。调度器计算每个进程的优先级,然后选择优先级最高的进程来执行。如果进程没有用尽时间片,那么该时间片的剩余时间会增加到下一个时间片中。

      O(n)调度器在每次使用时间片前都要检查所有就绪进程的优先级。这个检查时间和进程中进程数目n成正比,这也正是该调度器复杂度为O(n)的原因。当计算机中有大量进程在运行时,这个调度器的性能将会被大大降低。也就是说,O(n)调度器没有很好的可拓展性。O(n)调度器是Linux 2.6之前使用的进程调度器。

    • O(1)调度器的创新之处在于,它会把进程按照优先级排好,放入特定的数据结构中。在选择下一个要执行的进程时,调度器不用遍历进程,就可以直接选择优先级最高的进程。

    • O(1)调度器会用两个队列来存放进程。一个队列称为活跃队列,用于存储那些待分配时间片的进程。另一个队列称为过期队列,用于存储那些已经享用过时间片的进程。

      O(1)调度器把时间片从活跃队列中调出一个进程。这个进程用尽时间片,就会转移到过期队列。当活跃队列的所有进程都被执行过后,调度器就会把活跃队列和过期队列对调,用同样的方式继续执行这些进程。

      操作系统会创建140个活跃队列和过期队列,对应优先级0到139的进程。一开始,所有进程都会放在活跃队列中。

      然后操作系统会从优先级最高的活跃队列开始依次选择进程来执行,如果两个进程的优先级相同,他们有相同的概率被选中。执行一次后,这个进程会被从活跃队列中剔除。如果这个进程在这次时间片中没有彻底完成,它会被加入优先级相同的过期队列中。当140个活跃队列的所有进程都被执行完后,过期队列中将会有很多进程。调度器将对调优先级相同的活跃队列和过期队列继续执行下去。

    • CFS调度器增加了一个虚拟运行时(virtual runtime)的概念。每次一个进程在CPU中被执行了一段时间,就会增加它虚拟运行时的记录。在每次选择要执行的进程时,不是选择优先级最高的进程,而是选择虚拟运行时最少的进程。用一种叫红黑树的数据结构取代了O(1)调度器的140个队列。红黑树可以高效地找到虚拟运行最小的进程。

内存分配方式及错误

  • 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static变量。

  • 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。

  • 从堆上分配,亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存,程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定,使用非常灵活,但问题也最多。

  • 常见的内存错误及其对策

    • 内存分配未成功,却使用了它
      • 在使用内存之前检查指针是否为NULL
    • 内存分配虽然成功,但是尚未初始化就引用它
    • 内存分配成功并且已经初始化,但操作越过了内存的边界
    • 忘记了释放内存,造成内存泄露
    • 释放了内存却继续使用它
  • 【规则1】用malloc或new申请内存之后,应该立即检查指针值是否为NULL。防止使用指针值为NULL的内存。

    【规则2】不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右值使用。

    【规则3】避免数组或指针的下标越界,特别要当心发生“多1”或者“少1”操作。

    【规则4】动态内存的申请与释放必须配对,防止内存泄漏。

    【规则5】用free或delete释放了内存之后,立即将指针设置为NULL,防止产生“野指针”。

内存溢出VS内存泄漏

  • 内存溢出—-系统已经不能再分配出你所需要的空间,比如你需要100M的空间,系统只剩90M了,这就叫内存溢出

  • 内存泄漏—-你用资源的时候为他开辟了一段空间,当你用完时忘记释放资源了,这时内存还被占用着,一次没关系,但是内存泄漏次数多了就会导致内存溢出

  • VS下检测内存泄漏方法:

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      #define CRTDBG_MAP_ALLOC    
      #include <stdlib.h>
      #include <crtdbg.h>
      //在入口函数中包含 _CrtDumpMemoryLeaks();
      //即可检测到内存泄露

      //以如下测试函数为例:
      int main()
      {
      char* pChars = new char[10];
      //delete[]pChars;
      _CrtDumpMemoryLeaks();
      system("pause");
      return 0;
      }
    • 1
      /在入口函数中包含 _CrtDumpMemoryLeaks();

虚拟内存VS swap分区

  • windows:虚拟内存
    linux:swap分区
  • windows即使物理内存没有用完也会去用到虚拟内存,而Linux不一样 Linux只有当物理内存用完的时候才会去动用虚拟内存(即swap分区)
  • Windows可以设置在windows的任何盘符下面,默认是在C盘,可以和系统文件放在一个分区里。而linux则是独立占用一个分区,方便由于内存需求不够的情况下,把一部分内容放在swap分区里,待内存有空余的情况下再继续执行,也称之为交换分区,交换空间是其中的部分

中断VS异常

  • 中断是由于外部设备事件所引起的中断
  • 异常——是指由于 CPU 内部事件所引起的中断,如程序出错
  • 异常是由于执行了现行指令所引起的。由于系统调用引起的中断属于异常。
  • 中断则是由于系统中某事件引起的,该事件与现行指令无关
  • 相同点:都是CPU系统发生的某个事情做出的一种反应
  • 区别:中断外因引起异常CPU本身原因引起。
  • 中断不是时钟同步的,这意味着中断可能随时到来;异常由于是CPU产生的,所以,它是时钟同步的
  • 当处理中断时,处于中断上下文中;处理异常时,处于进程上下文中

进程终止的方式

  • 20171208095645231

  • 5中正常终止

    • main函数执行return,等效于调用exit
    • 调用exit函数。标准C库中一个函数
    • 调用_exit、_Exit函数,系统调用
    • 进程的最后一个线程在启动例程中执行return
    • 进程的最后一个线程调用pthread_exit函数。
  • 3中异常终止

    • 调用abort。产生SIGABRT信号
    • 当进程收到某些信号时。信号可由进程自身、其他进程或内核产生
    • 最后一个线程对“取消”请求作出回应

特殊进程

  • 进程ID

    • PID,进程的唯一标识,同一个进程的所有线程getpid函数都返回同一值
    • PGID进程组ID,每个进程都会有进程组ID,表示该进程所属的进程组
    • SID,会话ID。默认情况下,新创建的进程会继承父进程的会话ID。
  • 孤儿进程

    • 一个父进程已终止的进程为孤儿进程,由Init进程进行收养,并由init进程对它们完成状态收集工作。
  • 僵尸进程

    • 一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中
    • ps 命令 有Z标识的进程
    • 通过信号机制
      • 子进程退出时向父进程发送SIGCHILD信号,父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程
    • 两次fork()
      • 原理是将子进程成为孤儿进程,从而其的父进程变为init进程,通过init进程可以处理僵尸进程
      • 对于父进程的第一个子进程,父进程仍然需要wait/wait_pid
  • 守护进程

    • 守护进程就是在后台运行,不与任何终端关联的进程,通常情况下守护进程在系统启动时就在运行,它们以root用户或其他特殊用户运行,并能处理一些系统级的任务。
    • 守护进程的名称通常以d结尾
    • 进程组和会话在进程之间形成了两级的层次:进程组是一组相关进程的集合,会话是一组相关进程组的集合
    • 当有新的用户登录linux时,登录进程为这个用户建立一个会话。用户的登录shell就是会话的首进程。会话的首进程ID会作为整个会话的ID。会话时一个或者多个进程组的集合,囊括了登录用户的所有活动。
    • 会话开始于用户登录,终止于用户退出。一个会话包括一个会话首进程、一个前台进程组(只有一个)和一个后台进程组(可以多个)
    • 20160624093011_365
    • 创建一个守护进程
      • fork创建一个子进程,父进程exit退出
        • 孤儿进程被Init收养
      • 在子进程调用setsid()创建新会话
        • 在调用fork之后,子进程全盘拷贝了父进程的会话期,进程组、控制终端等,虽然父进程退出了,但会话期、进程组、控制终端等并没有改变。setsid可以使进程完全独立出来。
        • setsid创建一个会话。调用进程担任新会话的首进程,其作用有
          • 使当前进程脱离原会话的控制
          • 使当前进程脱离原进程组的控制
          • 时当前进程脱离原控制终端的控制
      • 再fork一个子进程,父进程exit退出
        • 现在进程已经成为无终端的会话组长,但它可以重新申请打开一个控制终端,可以同故宫fork一个子进程,该子进程不是会话首进程,不能重新打开控制终端。退出父进程
        • 即,通过再次创建子进程结束当前进程,使进程不再是会话首进程来禁止进程重新打开控制终端。
      • 再子进程中调用chdir(“/“)使得”/“成为子进程的工作目录
        • 使用fork创建的子进程继承了父进程的当前工作目录
        • 当前目录所在的文件系统(如“/mnt/usb”)是不能卸载的
        • 避免原父进程当前目录带来的一些麻烦
      • 再子进程中调用umaks(0)重设文件权限码为0
        • 由于使用fork创建子进程继承了父进程的文件权限掩码,则会个就该子进程使用文件带来了诸多的麻烦。因此把文件权限掩码重新设置为0即清楚掩码(权限为777),增强了守护进程的灵活性
        • 相当于把权限开放
      • 在子进程中close不需要的文件描述符
        • 关闭失去价值的输入、输出、报错等对应的文件描述符
      • 守护进程的退出处理
        • kill

怎么回收线程

  • 单个线程可以通过3中方式退出,可以在不终止整个进程的情况下,停止它的工作流
    • 线程可以简单的从启动例程中返回,返回值为线程的退出码
    • 线程可以被同一进程中的其他线程取消
    • 线程调用pthread_exit
  • 线程分为可结合的(joinable)和 分离的(detached)两种,如果没有在创建线程时设置线程的属性为PTHREAD_CREATE_DETACHED,则线程默认是可结合的。 分离的线程在线程退出时系统会自动回收资源。可结合的线程在线程退出后不会立即释放资源,必须要调用pthread_join来显式的结束线程。
    • 子线程使用return退出,主线程中使用pthread_join回收线程。
    • 子线程使用pthread_exit退出,主线程中使用pthread_join接收pthread_exit的返回值,并回收线程。
    • 主线程中调用pthread_cancel,然后调用pthread_join回收线程。

进程/线程数量

  • Linux中有一个命令可以帮助我们查看系统中的进程上限
    • ulimit -u
    • 修改为 5120 ulimit -u 5120
    • cat /proc/sys/kernel/pid_max
  • 一个进程中最多可以有多少个线程
    • 创建一个线程会占用多少内存,这取决于分配给线程的调用栈大小,可以用ulimit -s命令来查看大小,显示的单位是KB(一般常见的有10M或者是8M,也可以临时修改)
    • 一个进程的虚拟内存是4G(32位系统,寻址指针4字节,2^32),在Linux32位平台下,内核分走了1G,留给用户用的只有3G,于是我们可以想到,创建一个线程占有了10M内存,总共有3G内存可以使用。于是可想而知,最多可以创建差不多300个左右的线程。

一个程序从开始运行到结束的完整过程

  • 预处理—-gcc -E test.c -o test.i,其中,参数E告诉gcc命令值经行编译,不做其他的处理,用参数o指明输出的文件名为test.i。命令运行完毕后就会产生一个名为test.i的文件。
    • 编译预处理主要是读取c源程序,对其中的伪指令(以#开头的指令)和特殊符号进行处理,条件编译,头文件包含,宏替换的处理。
  • 编译—–gcc - S test.i -o test.s,其中参数S告诉gcc命令只进行编译,不做其他处理
    • 预编译程序所要作得工作就是通过词法分析和语法分析,在确认所有的指令都符合语法规则之后,将其翻译成等价的中间代码表示或汇编代码。
  • 汇编—-“gcc -c test.s -o test.o”,其中,参数c告诉gcc命令只进行汇编
    • 汇编过程主要的作用是汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程
  • 链接—-“gcc test.o -o test”,运行完成后就会产生一个名为test的可执行文件。
    • 链接程序的主要工作就是将有关的目标文件彼此相连接,也即将在一个文件中引用的符号 同该符号在另外一个文件中的定义连接起来,使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。
    • 静态链接VS动态链接
      • 静态链接:后缀是.a,主要在编译的时候将库文件里面代码搬迁到可执行的文件中;
      • 动态链接:后缀是.so,主要在执行的时候将需要的库文件代码搬迁到可以执行的文件中;
      • 静态的链接产生的可执行的文件体积比较的大;而动态链接的可执行文件的体积比较小;
      • 动态的链接的编译的效率比较的高;
      • 静态链接的可执行的文件执行的效率高
      • 静态链接的可执行的文件的“布局”比较好一点;
      • 动态链接更加适合频繁更新的

用户态VS内核态

  • 当一个进程在执行用户自己的代码时处于用户运行态(用户态),只能受限的访问内存,且不允许访问外围设备,占用cpu的能力被剥夺,cpu资源可以被其他程序获取
  • 当一个进程因为系统调用陷入内核代码中执行时处于内核运行态(内核态),内核态:cpu可以访问内存的所有数据,包括外围设备
  • 切换
    • 系统调用
    • 异常
    • 外围设备的中断

死锁

  • 死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局。当进程处于这种僵局时,若无外力作用,都将无法在向前推进
  • 原因
    • 竞争资源。当系统中多个进程共享的资源数目不足以满足进程的需要时,引起进程对资源的竞争
    • 进程间的推进顺序非法。进程在运行过程中,请求和释放资源的顺序不当,也会造成死锁。
  • 必要条件
    • 互斥条件。进程要求对所分配的资源进行排他性控制,即在一段时间内某资源仅为一进程所有。
    • 请求和保持条件。当进程因请求资源而阻塞时,对已获得的资源保持不放。
    • 不可剥夺条件。进程已获得的资源在未使用完之前,不能剥夺,只能在使用完毕时自己释放。
    • 环路等待条件。在发生死锁时,必然存在一个进程–资源的环形链。
  • 解决方法
    • 避免死锁
      • 加锁顺序
      • 加锁时限
      • 死锁检测
    • 预防死锁
      • 资源一次性分配:一次性分配所有资源,这样就不会再有请求了:(破坏请求条件)
      • 只要有一个资源得不到分配,也不给这个进程分配其他的资源:(破坏保持条件)
      • 可剥夺资源:即当某进程获得了部分资源,但得不到其它资源,则释放已占有的资源(破坏不可剥夺条件)
      • 资源有序分配法:系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反(破坏环路等待条件)

进程间通信方式

  • 管道,半双工的通信方式,数据只能单向流动,而且只能在具有父子进程间使用。

  • 有名管道,半双工的通信方式,但是它允许无亲缘关系进程间的通信

  • 信号量,一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,
    防止某进程正在访问共享资源时,其他进程也访问该资源。因此,主要作为进程间以及同
    一进程内不同线程之间的同步手段 .当信号量为正,进程可以使用该资源。信号量-1.表示使用了一个资源单位。若为0,进程进入到休眠状态,直到信号量大于0,进程被唤醒。

  • 消息队列 ,由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。 一个消息由,一个正的长整型类型的字段,一个非负的长度以及实际的数据字节数组成。

  • 信号 ,通知接收进程某个事件已经发生。

  • 共享内存 ,映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多
    个进程都可以访问 ,共享内存是最快的 IPC 方式,它是针对其他进程间通信方式运行效率
    低而专门设计的。它往往与其他通信机制,如信号量,配合使用,来实现进程间的同步和
    通信。

  • 套接字,可用于不同设备及其间的进程通信。

  • 线程间通讯方式

    • 锁机制:包括互斥锁、条件变量、读写锁 ,
      • 互斥锁提供了以排他方式防止数据结构被并发修改的方法。 读写锁允许多个线程同时读共
        享数据,而对写操作是互斥的。 条件变量可以以原子的方式阻塞进程,直到某个特定条件
        为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
    • 信号量机制(Semaphore):
      • 包括无名线程信号量和命名线程信号量
    • 信号机制(Signal):类似进程间的信号处理
      • 线程间的通信目的主要是用于线程同步,所以线程没有像进程通信中的用于数据交换的通
        信机制。
  • mutex+condition_variable VS semaphore

    • 条件变量(condition variable)是利用线程间共享的全局变量进行同步的一种机制,主要包括两个动作:一个线程等待某个条件为真,而将自己挂起;另一个线程使的条件成立,并通知等待的线程继续。为了防止竞争,条件变量的使用总是和一个互斥锁结合在一起

    • 使用条件变量可以一次唤醒所有等待者,而这个信号量没有的功能,感觉是最大区别

    • 信号量是有一个值(状态的),而条件变量是没有的,没有地方记录唤醒(发送信号)过多少次,也没有地方记录唤醒线程(wait返回)过多少次。从实现上来说一个信号量可以是用mutex + counter + condition variable实现的。因为信号量有一个状态,如果想精准的同步,那么信号量可能会有特殊的地方。信号量可以解决条件变量中存在的唤醒丢失问题。

    • 在Posix.1基本原理一文声称,有了互斥锁和条件变量还提供信号量的原因是:“本标准提供信号量的而主要目的是提供一种进程间同步的方式;这些进程可能共享也可能不共享内存区。互斥锁和条件变量是作为线程间的同步机制说明的;这些线程总是共享(某个)内存区。这两者都是已广泛使用了多年的同步方式。每组原语都特别适合于特定的问题”。尽管信号量的意图在于进程间同步,互斥锁和条件变量的意图在于线程间同步,但是信号量也可用于线程间,互斥锁和条件变量也可用于进程间。应当根据实际的情况进行决定。信号量最有用的场景是用以指明可用资源的数量。

    • 唤醒操作(SetEvent和pthread_cond_signal)原本意图是唤醒一个等待的线程,但是在多核处理器下,可能会激活多个等待的线程,这种效应为“虚假唤醒”

  • 如果在等待条件变量(pthread_cond_wait)前,条件变量就被唤醒激活(pthread_cond_signal),那么这次唤醒就会丢失

linux IO模型

  • IO的本质是socket的读取,数据先拷贝到内核的缓冲区中,然后拷贝到应用程序的地址空间(进程)
  • 阻塞IO,所有套接字默认的都是阻塞的,以recvfrom系统调用为例子,它要等到有数据报到达且被复制到应用进程的缓冲区中或者发生了错误才返回。若没有数据到达那么将一直会阻塞。
  • 同步非阻塞IO,非阻塞等待,每隔一段时间就去检查IO时间是否就绪,没有就绪就可以做其他事。在I/O执行的第二个阶段(数据复制)被block了,而第一个阶段并未阻塞(数据准备),但是在第一个阶段中,用户进程需要盲等,不停的去轮询内核,看数据是否准备好了。
    • 设置套接字为非阻塞式,并在第一阶段IO准备时,不断去轮询查看IO是否准备就绪,准备就绪后,在IO数据拷贝阶段阻塞执行。
  • 信号驱动IO,linux使用套接口进行信号驱动IO,安装一个信号处理函数,进程继续运行并不阻塞,当IO时间就绪,进程收到SIGIO信号,然后处理IO事件。信号驱动I/O执行的第一阶段不阻塞,而第二阶段是阻塞的。用信号让内核在文件描述符准备就绪的时候通知用户进程,即是告知我们什么时候可以启动IO操作。就如数据准备好了,内核就会以一种形式通知用户进程。
    • 用信号让内核在文件描述符准备就绪的时候通知用户进程,即是告知我们什么时候可以启动IO操作。就如数据准备好了,内核就会以一种形式通知用户进程
  • IO复用(同步阻塞),linux用slelect epoll实现IO复用,也会使进程阻塞,但是和阻塞IO不同的是,IO复用可以同时阻塞多个IO操作,而且可以同时对多个读/写操作的IO函数进行检测。直到有数据可读、可写时,才调用IO操作函数。IO多路复用是阻塞在select,epoll这样的系统调用之上,而没有阻塞在真正的I/O系统调用如recvfrom之上。多路复用I/O执行的两个阶段用户进程都是阻塞的,但是两个阶段是独立的。
    • 通过系统调用select、poll、epoll、kqueue实现IO复用模型。进程就阻塞在这些系统调用上,而不是阻塞在真正的IO操作上,直到有就绪事件了,这些系统调用就会返回哪些套接字可读写,然后就可以进行把数据包复制到应用进程缓冲区了
  • 异步IO(异步非阻塞):相对于同步IO,异步IO不是顺序执行。用户进程进行aio_read系统调用之后,无论内核数据是否准备好,都会直接返回给用户进程,然后用户态进程可以去做别的事情。等到socket数据准备好了,内核直接复制数据给进程,然后从内核向进程发送通知IO两个阶段,进程都是非阻塞的
    • 由用户进程告知内核启动一个操作,并且由内核去操作,操作完后给用户进程发一个通知,通知用户进程操作完了(包括数据从内核缓冲区拷贝到用户缓冲区的过程)。该模型与信号驱动式IO模型不同的就是,异步IO模型中,是由内核通知IO操作什么时候完成,而信号驱动式IO是由内核告知何时启动IO操作
  • 1568374913878
  • 阻塞IO和非阻塞IO的区别:数据准备的过程中,进程是否阻塞。
  • 同步IO和异步IO的区别:数据拷贝的过程中,进程是否阻塞。
  • 阻塞,非阻塞:进程/线程要访问的数据是否就绪,进程线程是否需要等待
  • 同步,异步:访问数据的方式,同步需要主动读写数据,在读写数据的过程中还是会阻塞;异步只需要I/O操作的完成的通知,并不主动读写数据,由操作系统内核完成数据的读写。
  • 阻塞的读
    • 如果内核的接受缓冲区中没有数据到达,那么就会一直阻塞,read函数在没有数据的时候,被挂起不返回,如果有数据,那么就是有多少就读多少
  • 阻塞的写
    • 用户进程有多少数据就要将所有数据都写入到内核的可写缓冲区才返回,。如果内核可写缓冲区可以容纳N个字节,而要发送的字节为N+1的话,那么write不返回,它会一直阻塞到那多出来的一个字节装到内核缓冲区才返回。,所以在select中,返回可写条件时,将套接字设置为非阻塞,才可以说一次写操作返回一个正值。
  • 非阻塞的读
    • 如果没有数据,read调用不会挂起,会立即返回。有数据的话,就有多少就读多少
  • 非阻塞的写
    • 内核缓冲区够写多少就写多少,能够写多少根据网络阻塞情况为标准,当阻塞严重时,没有足够的缓冲区去写的话,就会出现写不完的情况。

select VS epoll

  • select 支持的fd数量有限,单个进程能够监视的文件描述符的数量存在限制,通常1024
  • 每次调用select,都会把fd从用户态拷贝到内核态
  • 使用轮询方式,需遍历所有fd
  • poll的实现和select非常相似,只是描述fd集合的方式不同,poll使用pollfd结构而不是select的fd_set结构,其他的都差不多。 select,poll实现需要自己不断轮询所有fd集合,直到设备就绪,期间可能要睡眠和唤醒多次交替。但是解决了select的文件描述符的最大文件描述符数量
  • 本身没有最大并发连接的限制,仅受系统进程能够打开的最多文件数目限制
  • 省去不必要的内存拷贝,epoll通过内核与用户空间map同一块内存实现
  • 效率提升,返回的是fd发生变化的fd

select 实现原理

  • 从用户空间拷贝fd_set到内核空间
  • 注册回调函数__pollwait;
  • 遍历所有fd,对全部指定设备做一次poll(这里的poll是一个文件操作,它有两个参数,一个是文件fd本身,一个是当设备尚未就绪时调用的回调函数__pollwait,这个函数把设备自己特有的等待队列传给内核,让内核把当前的进程挂载到其中)
  • 当设备就绪时,设备就会唤醒在自己特有等待队列中的【所有】节点,于是当前进程就获取到了完成的信号。poll文件操作返回的是一组标准的掩码,其中的各个位指示当前的不同的就绪状态(全0为没有任何事件触发),根据mask可对fd_set赋值;
  • 如果所有设备返回的掩码都没有显示任何的事件触发,就去掉回调函数的函数指针,进入有限时的睡眠状态,再恢复和不断做poll,再作有限时的睡眠,直到其中一个设备有事件触发为止。
  • 只要有事件触发,系统调用返回,将fd_set从内核空间拷贝到用户空间,回到用户态,用户就可以对相关的fd作进一步的读或者写操作了。

epoll 高效关键

  • 在调用epoll_create时,内核除了帮我们在epoll文件系统里建了个file结点,在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外,还会再建立一个list链表,用于存储准备就绪的事件,当epoll_wait调用时,仅仅观察这个list链表里有没有数据即可
  • 当我们执行epoll_ctl时,除了把socket放到epoll文件系统里file对象对应的红黑树上之外,还会给内核中断处理程序注册一个回调函数,告诉内核,如果这个句柄的中断到了,就把它放到准备就绪list链表里。
  • 应用场景

进程VS 线如果在并发量低,socket都比较活跃的情况下,select就不见得比epoll慢了(就像我们常常说快排比插入排序快,但是在特定情况下这并不成立)。

进程VS 协程

  • 一个线程属于一个进程,一个进程有多个线程,至少有一个线程,线程依赖于进程存在

  • 进程在执行过程中有独立的内存单元,而多个线程共享进程的内存

  • 进程为资源分配的最小单位,线程为CPU调度的最小单位

  • 进程创建、撤销进程时,系统都要为之分配或者回收资源,如内存空间、IO设备等。大于创建、撤销线程的开销。进程切换时,涉及到整个当前进程的CPU环境的保存和新进程的CPU环境的设置,大于线程切换

    • 进程切换,需要切换系统指令以及地址空间,而线程共享地址空间,不需要切换地址空间,只切换指令
  • 进程间通信IPC,线程间共享地址空间,线程间同步和通信实现简单

  • 进程调试简单可靠性高,线程调试复杂

  • 进程间不会相互影响,线程一个线程挂掉使得整个进程挂掉

  • 进程适合多核、多机分布,线程适用于多核

    网络服务器中,多进程VS多线程

    • 对比维度 多进程 多线程 总结
      数据共享、同步 数据共享复杂,需要IPC;数据分开,同步简单 共享进程数据,共享简单,同步复杂 各有优势
      内存、CPU 占用内存多,切换复杂,CPU利用率低 占用内存少,切换简单,CPU利用率高 线程win
      创建销毁、切换 创建销毁、切换复杂,速度慢 创建销毁、切换简单,速度快 线程win
      编程、调试 编程简单,调试简单 编程复杂,调试复杂 进程win
      可靠性 进程间不会相互影响 一个线程挂掉导致整个线程挂掉 进程win
      分布式 适应于多核、多机分布式;扩展多个机器简单 适应于多核分布式 进程win
      • 优先进程
        • 弱相关
        • 多机分布
      • 优先线程
        • 频繁创建销毁
        • 大量计算
        • 强相关
        • 多核分布
      • 最拿手的
  • 协程

    • 更轻量级的线程。用于解决线程间切换和进程间切换的通病(对内核开销过大),协程各个状态(阻塞、运行)的切换是由程序控制,而不是内核控制,减少了开销。
    • 一种用户态的轻量级线程,完全由用户调度控制,拥有自己的寄存器上下文和栈,协程调度切换的时候,先将寄存器上下文和栈保存到其他地方,切换回来的时候再恢复之前保存的寄存器上下文和栈。直接操作栈则基本没有内核切换的开销,可以不加锁的访问全局变量,所以上下文的切换非常快。
  • 协程VS线程

    • 一个线程可以多个协程,一个进程也可以单独拥有多个协程
    • 线程进程都是同步机制,而协程则是异步
    • 协程能保留上一次调用时的状态,每次过程重入时,就相当于进入上一次调用的状态
  • 协程的好处

    • 无需线程上下文切换的开销
    • 无需原子操作锁定及同步的开销
    • 方便切换控制流,简化编程模型
    • 高并发+高扩展性+低成本
  • 协程的缺点

    • 无法利用多核资源:协程的本质是个单线程,它不能同时将 单个CPU 的多个核用上,协程需要和进程配合才能运行在多CPU上.
    • 进行阻塞(Blocking)操作(如IO时)会阻塞掉整个程序:这一点和事件驱动一样,可以使用异步IO操作来解决
  • C++20 协程,go协程

    硬链接、软连接

    • 硬链接。硬链接是指通过索引节点来进行链接

    • 在Linux的文件系统中,保存在磁盘分区中的文件不管是什么类型都会给它分配一个编号,这个编号被称为索引节点编号号(InodeIndex)或者Inode,它是文件或者目录在一个文件系统中的唯一标识,文件的实际数据放置在数据区域(data block),它存储着文件重要参数信息,也就是元数据 (metadata),比如创建时间、修改时间、文件大小、属主、归属的用户组、读写权限、数据所在block号等

      • 在Linux系统中,多个文件名指向同一索引节点(Inode)是正常且允许的。一般这种链接就称为硬链接
      • 硬链接的作用之一是允许一个文件拥有多个有效路径名,这样用户就可以建立硬链接到重要的文件,以防止“误删”源数据
      • 文件建立了硬链接就会防止数据误删,是因为文件系统的原理是,只要文件的索引节点还有一个以上的链接(仅删除了该文件的指向),只删除其中一个链接并不影响索引节点本身和其他的链接(数据的实体并未删除),只有当最后一个链接被删除后,此时如果有新数据要存储到磁盘上,被删除的文件的数据块及目录的链接才会被释放,空间被新数据暂用覆盖
  • 软连接

    • 软链接(也叫符号链接),类似于windows系统中的快捷方式,与硬链接不同,软链接就是一个普通文件,只是数据块内容有点特殊,文件用户数据块中存放的内容是另一文件的路径名的指向,通过这个方式可以快速定位到软连接所指向的源文件实体。软链接可对文件或目录创建。

    image002

  • 软链接:

    • 1.软链接是存放另一个文件的路径的形式存在。
    • 2.软链接可以 跨文件系统 ,硬链接不可以。
    • 3.软链接可以对一个不存在的文件名进行链接,硬链接必须要有源文件。
    • 4.软链接可以对目录进行链接。

    硬链接:

    • 硬链接,以文件副本的形式存在。但不占用实际空间。
    • 不允许给目录创建硬链接。
    • 硬链接只有在同一个文件系统中才能创建。
    • 删除其中一个硬链接文件并不影响其他有相同 inode 号的文件。
  • 软链接 (符号链接) ln -s source target

  • 硬链接 (实体链接)ln -h source target

用户权限

  • rwxr-xr-x 5 root root 94 Jun 27 2017 xdg
  • rwx 文件所有者权限 u表示
  • r-x 所属组权限 g表示
  • r-x 其他人权限 o表示
  • r=4 w=2 x=1
  • chmod u+x a.txt 对所有者添加 x权限
  • chmod g-x,o-x a.txt,对所属用户组,其他减权限
  • chmod u=rwx,g=rwx,o=rwx a.txt
  • chomd a=wx a.txt a=all添加所有者,用户组,其他权限
  • chmod a=rw a.txt b.txt

用户态、内核态

  • linux命令

  • 系统信息

    • 1
      2
      3
      cat /proc/version :查看linux版本信息
      date :显示系统日期
      ifconfig :显示或设置网卡
  • 系统性能

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15

      top :动态实时显示cpu、内存、进程等使用情况(类似windows下的任务管理器)
      top -d 2 -p 7427 :-d为画面更新的秒数,默认5秒,-p为指定进程pid的信息
      vmstat 2 10 :每隔2秒采集一次服务器状态,采集10次(查看内存、io读写状态、cpu)
      free -h :查看系统内存及虚拟内存使用情况
      df -h :显示磁盘的空间使用情况
      iostat :可查io读写、cpu使用情况
      sar -u 3 5 :查看cpu使用情况(3秒一次,共5次)
      sar -d 2 3 :评估磁盘性能
      ps aux|grep firefox :获取火狐的进程号(PID)(可查看进程占用cpu、内存百分比及进程触发指令的路径)
      kill -9 进程号 :强制杀死进程
      systemctl :查看正在运行的服务
      ps –ef|grep tomcat 查看所有有关tomcat的进程
      find / -name filename.txt 根据名称查找/目录下的filename.txt文件。
      locate a.txt :在系统全局范围内查找文件名包含a.txt字样的文件(比find快);
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      ps命令

      (用于将某个时间点的进程运行情况选取下来并输出,process之意)
      -A :所有的进程均显示出来
      -a :不与terminal有关的所有进程
      -u :有效用户的相关进程
      -x :一般与a参数一起使用,可列出较完整的信息
      -l :较长,较详细地将PID的信息列出

      ps aux # 查看系统所有的进程数据
      ps ax # 查看不与terminal有关的所有进程
      ps -lA # 查看系统所有的进程数据
      ps axjf # 查看连同一部分进程树状态

    查看文件内容

    • 1
      2
      3
      4
      cat [-n] 文件名 :显示文件内容,连行号一起显示
      less 文件名 :一页一页的显示文件内容(搜索翻页同man命令)
      head [-n] 文件名 :显示文件头n行内容,n指定显示多少行
      tail [-nf] 文件名:显示文件尾几行内容,n指定显示多少行,f用于实时追踪文件的所有更新,常用于查阅正在改变的日志文件(如tail -f -n 3 a.log 表示开始显示最后3行,并在文件更新时实时追加显示,没有-n默认10行)

    任务

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      python3 test.py & 虽然会后台运行,但是会输出结果,如果关闭xshell窗口,进程会结束,也就是结束后台运行。
      nohup python3 test.py& 如果让程序始终在后台执行,即使关闭当前的终端也执行(之前的&做不到),这时候需要nohup。
      jobs 查看当前有多少在后台运行的命令

      后台进程的终止:
      方法一:
      通过jobs命令查看job号(假设为num),然后执行kill %num
      方法二:
      通过ps命令查看job的进程号(PID,假设为pid),然后执行kill pid

计算机网络

  • TCP/IP协议体系
  • 链路层
    • 以太网帧的格式
    • MTU
    • ARP/RARP
  • 网络层
    • IP首部格式
    • IP分片
    • IP选路
    • ICMP协议
      • 报文格式
      • 分类 查询+差错
      • 两种+五种
      • 传输层
  • 传输层
    • UDP
      • 特点
      • 首部字段
    • TCP
      • 特点
      • 首部字段
      • 可靠机制
      • 连接控制
      • 流量控制机制
      • 超时重传
  • 应用层
    • DNS
      • 命名空间
      • 指针查询(反向查找或逆向解析)基本原理
      • DNS缓存
    • FTP协议——————
      • 两条连接。控制流、数据流
      • 两种工作模式PASV PORT
      • 各种指令和相应码
      • 断点续传和匿名FTP概念
    • HTTP协议
      • 报文格式:请求报文,响应报文,请求各种字段,响应头各种字段
      • HTTP状态码
    • HTTPS协议
      • 握手具体过程
      • 摘要算法,数字签名,数字证书的原理和过程

TCP/IP协议体系

  • OSI 有哪几层,会画出来,知道主要几层的各自作用

    ​ 1. 应用层(数据):确定进程之间通信的性质以满足用户需要以及提供网络与用户应用

    1. 表示层(数据):主要解决用户信息的语法表示问题,如加密解密
    2. 会话层(数据):提供包括访问验证和会话管理在内的建立和维护应用之间通信的机
      制,如服务器验证用户登录便是由会话层完成的
    3. 传输层(段):实现网络不同主机上用户进程之间的数据通信,可靠
      与不可靠的传输,传输层的错误检测,流量控制等
    4. 网络层(包):提供逻辑地址(IP)、选路,数据从源端到目的端的传输
    5. 数据链路层(帧):将上层数据封装成帧,用 MAC 地址访问媒介,错误检测与修正
    6. 物理层(比特流):设备之间比特流的传输,物理接口,电气特性等
  • 知道各个层使用的是哪个数据交换设备。(交换机、路由器、网关)

    • 网关:应用层、传输层(网关在传输层上以实现网络互连,是最复杂的网络互连设
      备,仅用于两个高层协议不同的网络互连。网关的结构也和路由器类似,不同的是
      互连层。网关既可以用于广域网互连,也可以用于局域网互连)
    1. 路由器:网络层(路由选择、存储转发)
    2. 交换机:数据链路层、网络层(识别数据包中的 MAC 地址信息,根据 MAC 地址进

    行转发,并将这些 MAC 地址与对应的端口记录在自己内部的一个地址表中)

    1. 网桥:数据链路层(将两个 LAN 连起来,根据 MAC 地址来转发帧)
    2. 集线器(Hub):物理层(纯硬件设备,主要用来连接计算机等网络终端)
    3. 中继器:物理层(在比特级别对网络信号进行再生和重定时,从而使得它们能够在
      网络上传输更长的距离)

数据链路层

  • ARP
    • IP地址到对应的硬件地址之间提供动态映射。动态—自动完成
    • RARP被那些没有磁盘驱动器的系统使用,需要系统管理员进行手动设置
    • 点对点网络无需地址解析协议
    • ARP高效运行的关键是,每个主机都有一个ARP高速缓存/存放了最近Internet地址到硬件地址之间的映射记录。高速缓存每一项的生存时间一般为20分钟,起始时间从被创建时开始。
    • ARP报文
      • mark
      • 帧类型0800 IP 0806 ARP 0835 RARP
      • 硬件类型 以太网 =1
      • 协议类型 IPv4 0x0800
      • 硬件长度 以太网地址长度6 字节
      • 协议长度 IPv4=4字节
      • 操作码 1 request 2 reply 3 RARP请求 4 RARP 应答
  • ARP 协议有什么弱点?
    • 1)缓存:主机的地址映射是基于高速缓存的,动态更新的。地址刷新是有时间限制的。 可
      以通过下次更新之前修改计算机上的地址缓存,造成拒绝服务攻击或者 ARP 欺骗。
      2)广播: 攻击者可以伪装 ARP 应答。
      3) ARP 应答没有认证,都是合法的。可以在不接受到请求的时候就发出应答包。
  • ARP 代理的概念和应用场景
    • 若 ARP 请求是从一个网络的主机发送给另一个网络上的主机,那么连接这两个网络的路由
      器就可以回答该请求,这个过程叫做 ARP 代理。 ARP 代理路由器响应 ARP 请求的 MAC 地
      址为路由器的 MAC 地址而非 ARP 请求的主机的 MAC 地址。
    • ARP 代理的应用环境:
      两个物理网络之间的路由是使用相同的网络号,两个路由器设置成 ARP 代理,实现相互隐
      瞒物理网络
  • 免费 ARP
    • 主机发送 ARP 查找自己的 IP 地址,即数据链路层 SIP=DIP
    • 作用有两个:
      1)一个主机使用免费 ARP 确定是有存在有其他主机设置了相同的 IP 地址–检测IP冲突
      2)如果发送免费 ARP 的主机改变了 MAC 地址,可以通过发送免费 ARP 的方式告知其他
      主机端更新 ARP 表 –更新ARP表,网络设备冷备
  • 数据链路层 MTU 的最大值和最小值是多少
    • 数据链路层的最小 MTU 为 64 字节。
    • 数据链路层的最大 MTU 为 1500 字节,即数据字段的最大长
  • ARP请求过程
    • 假设主机A和主机B在同一个网段内
      • 主机A首先查看自己的ARP表,确定其中是否包含主机B对应的ARB表项,找到,对IP数据包进行帧封装,并将数据包发送给主机B
      • 如果A自己的ARP表没有,向局域网的所有主机广播一个ARP请求,寻找B主机,当B主机收到A主机广播的ARP请求后,一方面将主机A的IP-MAC存放在自己的缓存中,另外就会直接给A主机回复一个ARP数据包,当A主机收到B主机发送过来的请求后,将B的MAC地址写入高速缓存中
    • AB不在一个网段内
      • 就通过ARP询问默认网关对应的MAC地址, 将数据转发给网关, 网关进行与主机A类似的ARP解析过程,将数据发送给主机B,或者转发给下一个网关继续进行路由,直到到达主机B
    • ARP请求广播,ARP响应单播

IP

  • IP提供不可靠的无连接的数据报传送服务

    • 不可靠(unreliable)指的是不能保证IP数据报能成功到达目的地。如果发生某种错误。IP有一个简单的错误处理算法,丢弃该数据报,然后发送ICMP消息给信源端。任何要求的可靠性必须由上层来提供(tcp/ip)
    • 无连接(connectionless)IP并不维护任何关于后续数据报的状态信息。IP 数据可以不按顺序发送和接收。 A 发送连续的数据报,到达 B 不一定是连续的,来回路由选择可能不一样,路线也不一样,到达先后顺序也不一样。 TCP对数据包排序,顺序不对时,缓存。
  • IP报文格式

    • mark
    • 版本号:4-IPV4,6-IPV6
    • 首部长度:单位为4字节,即一行。最小为5(20字节,无可选项),最大为15(60字节)
    • Tos,忽略
    • 总长度,IP首部+数据部分,最大2^16=65536字节
    • 标识字段,16bit,四字节,用于分片重组
    • 标志,3bit,表示是否可分片,分片的情况下,是否是最后一片
    • 片位移:13bit,标识被分片的每一个片段相对于原始数据的位置,单位为8字节,是2^13=8192*8=65536,最多表示原始数据的65536字节的位置
    • TTL生存时间:可以中转多少个路由器,每经过一个路由就减1,防止环形路由
    • 协议:8bit,表示IP首部的下一个是什么协议,ICMP:1 | **TCP:6 | UDP:17 | GRE:47 | ESP:50 | AH:51**
    • 首部检验和:只校验IP首部,不校验数据部分
    • 可选项:最多40字节,
    • 填充pad,确保首部长度为32bit的整数倍
  • 为什么IP首部需要总长度字段

    • 因为一些数据链路(以太网)需要填充一些数据以达到最小长度。因为以太网帧的最小长度
      是 46 个字节,但是 IP 长度可能更短,所以需要总长度来确定 IP 数据部分的内容。
  • IP 首部校验和怎么计算的,与 ICMP, IGMP, TCP, UDP 的首部校验和有什么区
    别与共同点?

  • (1) 先把校验和字段置 0。
    (2) 对首部中每个 16 位比特进行二进制求和,多余4个字节的,把大于4字节的同剩下的四个字节继续相加。
    (3) 结果取反 保存在检验和字段中。
    (4) 收到一份 IP 数据包后,同样对首部中每个 16bit 二进制求和,同样大于四个字节的同剩下四个字节相加,并取反
    (5) 最后结果全为 1,表示正确,否则表示错误。
    (6) 如果是错误的, IP 就丢弃该数据报,但是不生成差错报文,由上层去处理。

    • 共同点:用到的算法都是一样的。
      区别: IP 计算的时候没有将数据包括在内。
      ICMP, IGMP, TCP, UDP 同时覆盖首部和数据检验码。
  • IP路由

    • IP路由选择的过程
      • 根据最长匹配原则,找到条目,发送到指定的路由器。如果不能找到,返回一个“主机不可
        达”或“网络不可达”的错误。
    • IP路由选择的特点
      • IP 路由选择是逐跳进行的。 IP 并不知道到达任何目的的完整路径,只提供下一跳地址。
      • 为一个网络指定一个路由器,而不是为每个主机指定一个路由器 ,这样可以缩小路由表规模。
    • IP搜索路由表的步骤
      • 搜索匹配的主机地址(网络号和主机号都要匹配) —-》搜索匹配的网络地址 —-》搜索默认选项
    • 如果路由表中没有默认项,而又没有找到匹配项,这时如何处理?
      • 数据报是由本机产生的,那么就给发送该数据报的应用程序返回一个差错,或者是“主
        机不可达差错”或者是“网络不可达差错”。
      • 如果是被转发的数据报,就给原始发送端发送一份 ICMP 主机不可达的差错报文。
  • IP地址分类

      1. A 类地址:首位为 0, 1.0.0.1~~126.255.255.254;主机号 24 位

      2. B 类地址:首位为 10, 128.0.0.1~~191.255.255.254;主机号 16 位

      3. C 类地址:首位为 110, 192.0.0.1~~223.255.255.254;主机号 8 位

      4. D 类地址(多播地址,也叫做组播地址):首位为 1110, 224.0.0.1~~239.255.255.254

      5. E 类地址:此类地址是保留地址,首位为 11110, 240.0.0.1~~254.255.255.254

    • 网络地址就是:把IP地址转成二进制和子网掩码进行与运算

    • 主机的数量=2^二进制位数的主机-2(1个网络地址,1个广播地址)

    • 广播地址:网络地址的主机位全部变成1

    • 网络地址+1即为第一个主机地址,广播地址-1即为最后一个主机地址

  • ICMP

    • ICMP报文前四个字节都相同,IP 首部20字节。
    • mark
    • ICMP 协议在 IP头部中 协议为1 ICMP:1 | TCP:6 | UDP:17 | GRE:47 | ESP:50 | AH:51
    • echo request 类型为8 代码为0
    • echo reply 类型为0 代码为0
    • 校验和:
      • 以太网管自己的,IP校验和–IP头部,TCP /ICMP 管自己头部和后面所有的
    • ICMP报文分类
      • 一类是 ICMP 查询报文,另一类是 ICMP 差错报文。
      • 1567476237158
      • ICMP 的主机不可达报文是在什么情况下发出的?
        • 三层设备(路由器)给该主机寻路时,没有找到相应路径,向源 IP 发回 ICMP 主机不可达
    • 什么情况不会导致产生 ICMP 差错报文?为了防止过去允许ICMP差错报文对广播分组响应所带来的广播风暴
      • ICMP差错报文,但是ICMP查询报文可能会产生差错报文
      • 目的地址是广播地址或多播地址的IP数据报
      • 作为链路层广播的数据报
      • 不是IP分片的第一片,因为只有第一片才有四层端口号的信息。
      • 源地址不是单个主机的数据报。即源地址不能为零地址、环回地址、广播地址、多播地址
    • ping
      • 第一个是看看是不是超时
      • 第二个看看是不是延迟太高
        • A 电脑( 192.168.2.135)发起 ping请求, ping192.168.2.179
        • A 电脑广播发起 ARP请求,查询 192.168.2.179的 MAC地址。
        • B 电脑应答 ARP请求,向 A电脑发起单向应答,告诉 A电脑自己的 MAC地址为 90:A4:DE:C2:DF:FE
        • 知道了 MAC地址后,开始进行真正的 ping请求,由于 B电脑可以根据A电脑发送的请求知道 源 MAC地址,所以就可以根据源 MAC地址进行响应了。
        • 发送ICMP ECHO request ( 类型为8 代码为0)报文,响应ICMP reply(类型为0 代码为0)报文

UDP

  • 1567391865764
  • UDP 长度:是 UDP 的报文总长度,是多于8的。 IP 总长度减去首部长度就是此值
  • UDP 校验和:注意点:校验和是可选的。 (TCP 是必选的)校验和覆盖 UDP 首部和数据
    (TCP 也一样覆盖首部和数据,但是 IP 只覆盖首部)
  • UDP校验和如何计算
    • UDP 的校验和要计算首部和数据部分。首部还包括伪首部
    • 1567391955508
    • 多了 12 个字节的伪首部。
    • 为什么加伪头部
      • 目的是让 UDP 两次检查数据是否已经正确到达目的地。IP 接受正确的目的地址,传送到正确的上层程序。所有伪首部包括:源 IP 地址,目的 IP 地址, 0,协议号, UDP 长度。
  • TCP、 UDP 为什么存在伪包头?
    • UDP(TCP)检验和:是根据 UDP(TCP)数据报和伪报头计算得到的差错检测值。
    • 伪报头包含源和目的 IP 地址,以及来自 IP 数据报报头的协议值。 IP 数据报在网络中传送时
      包含 UDP(TCP) 数据报。
    • 伪报头并不会在网络中传送,校验和中所包含的伪报头内容可以避免目的端错误地接收错误路由的数据报。校验和值的计算方法和 IP 报头检验和的计算方法类似
  • UDP实现可靠传输
    • RUDP RTP UDT
    • 传输层无法保证数据的可靠传输,只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式,只是实现不在传输层,实现转移到了应用层。
    • 实现确认机制,重传机制,窗口确认机制
    • 添加seq/ack机制,确保数据发送到对端
    • 添加发送和接收缓冲区,主要是用户超时重传
    • 添加超时重传机制

TCP

  • mark

  • TCP VS UDP

    • UDP 没有复杂控制,提供面向无连接通信服务的一种协议,将部分控制转移给应用程序
    • TCP 对传输、发送、通信进行控制的协议,仅在确认对端存在时才发送数据,控制通信流量,提供可靠的传输机制
  • TCP面向连接,UDP面向无连接

    • TCP面向报文,UDP面向字节流
    • TCP提供可靠传输服务,UDP传输不可靠
    • TCP协议速度慢,UDP快
    • TCP协议对资源要求多(头部开销大),UDP协议要求少
  • TCP的可靠性

    • 拥塞控制:应用数据被分割为TCP最为合适发送的大小
    • 超时重传:TCP发送一个字段后,启动一个定时器,等待目的端收到报文段,如果不能及时收到ACK,将重新发送
    • 延迟应答:TCP收到数据,发送延迟的ack(200ms),delayed_ack
    • 校验和:TCP保持首部和数据的校验和
    • 序列号:TCP会对收到的数据进行重新排序
    • TCP提供对流的控制。TCP连接的每一方都有固定大小的缓冲空间。TCP的接收端只允许另一端发送 接收端缓冲区所能容纳的数据。这将防止较快主机致使较慢主机的缓冲区溢出
  • 序号

    • 序号标识从TCP发送端到接收端的字节流,标识这个报文段中第一个数据字节的序号,不会从0开始,在建立连接时(发送SYN时),由计算机生成的随机数作为初始值。序号无符号32bit,达到2^32后,变为0重新开始
    • 确认序号是上次已成功收到数据字节序号加1(SYN占用一个序号)。只有ACK标志位1时确认序号字段才有效。
  • 窗口大小,16bit,用于通知从相同的TCP首部应答好所指位置开始能接受的数据大小,TCP不能发送超过次值大小的数据段,窗口为0表示可以发送窗口探测,以了解最新窗口大小。但这个数据必须为1个字节。

    • 接收端能够接收的字节数,(即允许当前发送端发送的字节数)
  • MSS,每个连接方通常在通信的第一个报文段(SYN段),设置本端所能接受的报文段的最大长度

  • 连接

    • 三次握手
      • 客户端发送SYN, 序列号 A,ACK号=0 进入SYN_SENT状态
      • 服务器发送SYN+ACK, 序列号B ACK号 A+1 进入 SYN_RCVD
      • 客户端发送ACK,序列号 A+1 ACK号B+1 进入ESTABLISHED
      • 服务器收到ACK后,进入 ESTABLISHED
  • 断开

    • 四次挥手
      • 客户端发送FIN 序列号A ACK 号 进入FIN_WAIT_1
      • 服务器发送ACK 序列号 B, ACK号 A+1 进入CLOSE_WAIT
      • 接收端收到ACK后,进入FIN_WAIT_2,继续接受来自服务器的数据
      • 服务器发送FIN 进入LAST_ACK
      • 客户端发送ACK 进入TIME_WAIT,等待2MSL后进入CLOSED状态
      • 服务器收到ACK后,进入CLOSED
  • 为什么三次?为什么四次

    • 3 次握手:防止已过期的连接请求报文突然又传送到服务器,因而产生错误
      • 为了实现可靠数据传输, TCP 协议的通信双方, 都必须维护一个序列号, 以标识发送出去的数据包中, 哪些是已经被对方收到的。 三次握手的过程即是通信双方相互告知序列号起始值, 并确认对方已经收到了序列号起始值的必经步骤
      • 如果只是两次握手, 至多只有连接发起方的起始序列号能被确认, 另一方选择的序列号则得不到确认
      • 如果只有两次确定一个连接的话。当客户端发送SYN后,丢失,再次发送SYN,服务器发送SYN +ACK,这时就已经建立好连接,之后传递数据并断开连接。这时,之前丢的那个SYN回来了,那么客户端知道这个连接已经结束了,但是服务器认为这是一个新的连接,于是为它建立连接(占据一定资源),并等待对方发送数据
      • 而如果采用三次的话,如果第三次ACK不来,服务器就会知道该SYN无效,释放资源。
      • 另一种情况是,由于种种原因,失败。客户端认为字节连接好了,会给服务器发送数据,而服务器由于没有收到ACK,发送RST给客户端,收到RST的客户端知道第三次握手没有成功,会重新连接。
    • 4 次挥手:确保数据能够完成传输,但关闭连接时,当收到对方的 FIN 报文通知时,它
      仅仅表示对方没有数据发送给你了;但未必你所有的数据都全部发送给对方了,所以你可以
      未必会马上会关闭 SOCKET,也即你可能还需要发送一些数据给对方之后,再发送 FIN 报文
      给对方来表示你同意现在可以关闭连接了,所以它这里的 ACK 报文和 FIN 报文多数情况下
      都是分开发送的
  • 状态变迁图

    • 201012122157476286

    • 201012122157494693

    • https://img-blog.csdn.net/20180208112533496

    • mark

    • 2MSL

      • TIME_WAIT状态又称2MSL状态。每个具体TCP实现选择一个报文段最大生存时间MSL,它是任何报文段被丢弃前在网络内的最长时间

      • 原因

        • 如果服务器在发送FIN后,没有收到ACK,超过超时重传时间后,服务器重新发送FIN,客户端再发送ACK。如果没有TIME_WAIT状态,服务器可能一直收不到ACK,一直保持该会话
        • 如果在第一个连接结束后,迅速建立第二个连接,而且是相同的四元组,那么TCP认为是同一个连接,上一个连接遗留的包会对下一个连接造成错误,所以等待一会时间。
        • 2MSL其中一个是被动段发送的ACK丢失时,另一个是主动段发送的FIN包丢失的最大生存时间。
      • 可靠的实现TCP全双工连接的终止

    • 允许老的重复连接在网络中消失

      • 效果

        • 等待2MSL期间,这个连接的插口(客户的IP地址和端口号,服务器的IP地址和端口号)不能在被使用。这个连接只能在2MSL结束后才能被使用
        • 连接处于2MSL等待时,任何迟到的报文段将被丢弃。因为处于2MSL等待的、由该插口对定义的连接在这段时间不能被再用
      • 客户执行主动关闭并进入TIME_WAIT状态是正常的。服务器通常执行被动关闭,不会进入TIME_WAIT状态。这暗示如果终止一个客户程序并重新启动这个客户程序,则这个新客户程序将不能重用相同的本地端口。

      • 对于服务器,使用熟知端口。如果我们终止一个已经建立连接的服务器程序,并试图立即重新启动这个服务器程序,服务器程序将不能把它的这个熟知端口赋值给它的端点,因为那个端口处于2MSL连接的一部分。

      • 解决

        • 1
          2
          3
              bool option=TRUE;
          int optlen=sizeof(option)
          setsocketopt(serv_sock,SOL_SOCKET,SO_REUSEADDR,(void*)&option,optlen)
  • FIN_WAIT_2

    • 长时间停在FIN_WAIT_2状态,对端停留在CLOSE_WAIT状态

    • 一般防火墙都有解决半关闭(FIN_WAIT_2)的超时时间设置,如果超时,防火墙会向双方发送RSET(伪装源)来踢掉连接。

    • 父进程打开了socket,然后用派生子进程来处理业务,父进程继续对网络请求进行监听,永远不会终止。客户端发FIN过来的时候,处理业务的子进程的read返回0,子进程发现对端已经关闭了,直接调用close()对本端进行关闭。实际上,仅仅使socket的引用计数减1,socket并没关闭。从而导致系统中又多了一个CLOSE_WAIT的socket。

    • 1
      2
      3
      4
      5
      //子进程的关闭处理应该是这样的:
      shutdown(sockfd, SHUT_RDWR);
      close(sockfd);
      //这样处理,服务器的FIN会被发出,socket进入LAST_ACK状态,等待最后的ACK到来,就能进入初始状态CLOSED。
      //在多进程中如果一个进程中shutdown(sfd, SHUT_RDWR)后其它的进程将无法进行通信. 如果一个进程close(sfd)将不会影响到其它进程.
* 一般情况下,当TCP连接主动关闭时,会向对端发送一个FIN,对端会获得一个读事件,调用read时返回0,表示读到一个EOF,读结束。
  • TCP交互式数据流

    • 延迟的ACK
      • 通常TCP在接收到数据后并不立即发送ACK,相反,它推迟发送,以便将ACK与需要沿该方向发送的数据一起发送(数据捎带ACK),绝大多数实现采用的时延为200ms,即,TCP将以最大200ms的时延等待是否有数据一起发送
    • Nagle算法
      • 要求一个TCP连接上最多只有一个未被确认的未完成的小分组,在该分组的确认到达前不能发送其他的小分组,这时可以缓冲接下来要发送的数据包,TCP收集这些少量的分组,并在确认到来时以一个分组的方式发出去。该算法的优越性在于它是自适应的:确认到达的越快,数据也就发送的越快。而在希望减少微小分组数目的低速广域网上,则会发送更少的分组
      • 关闭Nagle算法,实时预览的通讯程序而言,e.g.小消息必须无时延的发送
        • 将套接字描述符设置TCP_NODELAY选项可以禁止nagle算法
  • TCP成块的数据流

    • 正常数据流
      • 确认机制
        • 通常使用的“隔一个报文段确认”策略,A发送一个报文给B,A再发送一个报文给B,B发送ACK确认收到的两个报文给A
        • delay_ed ACK, 如果tcp对每个数据包都发送一个ack确认,那么只是一个单独的数据包为了发送一个ack代价比较高,所以tcp会延迟一段时间,如果这段时间内有数据发送到对端,则捎带发送ack,如果在延迟ack定时器触发(200ms)时候,发现ack尚未发送,则立即单独发送
    • 滑动窗口
      • 接受方的流控,发送方快,接收方慢,协调双方工作节奏
      • MSS 最大消息长度,在建立连接时确定,为IP中不会被分片的最大数据长度((MTU)1500-(IP头部)20-(TCP头部)20=1460)
      • 滑动窗口本质上是描述接受方的TCP数据报缓冲区大小的数据,发送方根据这个数据来计算自己最多能发送多长的数据。
      • 窗口左边右移
        • 发生在数据被发送(发送端)和确认时(接收端)
        • 发送端的slide window 左侧是自己发出,并被对方确认的字节序列号,右侧是左侧+ B通告window size。
      • 窗口右边右移
        • 收到已经确认的数据并释放了TCP接收缓存时
      • 发送端状态
        • 已发送已收到ACK,已发送未收到ACK,准备发送,未发送
      • 接收端状态
        • 已收到ACK,已收到未发送ACK,未收到
      • 发送方根据接收方的窗口连续发送数据窗口大小的数据不用收到ACK,收到ACK后窗口左边右移
      • 接收方则确认ACK 连续的数据分组,对于乱序的分组则先接收下来,避免网络重复传递,丢失的触发超时重传
    • 慢启动
      • 拥塞窗口是由发送方使用的流量控制,而通告窗口则是接收方使用的流量控制
      • TCP采用慢启动算法来降低一开始就发送过多的数据到网络,采用slow start 算法来快速摸到传输路径带宽的峰值。(一开始发送大量数据,在发送方和接收方之间存在多个路由器和速率较慢的链路时,就有可能出现一些问题。一些中间路由器必须缓存分组,并有可能耗尽存储器的空间,然后发生丢包)
      • 发送方有一个拥塞窗口(cwnd),拥塞窗口被初始化为1个报文段,每收到一个ACK,拥塞窗口就增加一个报文段(cwnd以字节为单位,但是慢启动以报文段为单位进行增加),收到一个ACK,1->2,收到两个ACK,2->4,指数增加,
      • 发送方取拥塞窗口与通告窗口中的最小值作为发送上限。
      • 不要一开始就发送大量的数据,先探测一下网络的拥塞程度,也就是说由小到大逐渐增加拥塞窗口的大小。这里用报文段的个数的拥塞窗口大小举例说明慢开始算法,实时拥塞窗口大小是以字节为单位的。
      • 为了防止 cwnd 增长过大引起网络拥塞,设置一个慢开始门限(ssthresh 状态变量)
        • 当 cnwd<ssthresh,使用慢开始算法
        • 当 cnwd=ssthresh,既可使用慢开始算法,也可以使用拥塞避免算法
        • 当 cnwd>ssthresh,使用拥塞避免算法
          • 拥塞避免并非完全能够避免拥塞,是说在拥塞避免阶段将拥塞窗口控制为按线性规律增长,使网络比较不容易出现拥塞。
          • 思路:让拥塞窗口 cwnd 缓慢地增大,即每经过一个往返时间 RTTI就把发送方的拥塞控制窗口加一。
          • 无论是在慢开始阶段还是在拥塞避免阶段,只要发送方判断网络出现拥塞(其根据就是没有收到确认,虽然没有收到确认可能是其他原因的分组丢失,但是因为无法判定,所以都当做拥塞来处理),就把慢开始门限设置为出现拥塞时的发送窗口大小的一半。然后把拥塞窗口设置为 1,执行慢开始算法。
          • 1567386917332
  • TCP的超时和重传

    • 对每个连接,TCP管理4个不同的定时器

      • 重传定时器用于当发送一个数据报文时,在规定时间内,发送方需要收到另一端发出的接收报文确认。
      • 坚持persist定时器使窗口大小信息保持不断流动,即使另一端关闭了其接收窗口 chapter23
      • 保活keepalive定时器用于检测一个空闲连接的另一端是否依然保持连接。chapter23
      • 2MSL定时器测量一个连接处于TIME_WAIT状态的时间。chapter18.6
    • 快重传算法

      • 要求接收方在收到一个失序的报文段后就立即发出重复确认(为的是使发送方及早知道有报文段没有到达对方)而不要等到自己发送数据时捎带确认。快重传算法规定,发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段,而不必继续等待设置的重传计时器时间到期。
      • 由于不需要等待设置的重传计时器到期,能尽早重传未被确认的报文段,能提高整个网络的吞吐量
      • 快速重传后执行的不是慢启动,而是拥塞避免算法
    • 快速恢复算法

      • 当发送方连续收到三个重复确认时,就执行“乘法减小”算法,把 ssthresh 门限减半。
        但是接下去并不执行慢开始算法
    • 考虑到如果网络出现拥塞的话就不会收到好几个重复的确认,所以发送方现在认为网络
      可能没有出现拥塞。所以此时不执行慢开始算法,而是将 cwnd 设置为 ssthresh 的大小,
      然后执行拥塞避免算法。

      • 1567388045381
  • TCP坚持定时器

    • 解决通告窗口的ACK丢失时,双方的死锁问题
    • 解决问题:接收端的缓存满的时候,接收端回向发送端回复一个窗口为0的ACK,而后接收端在向发送端发送窗口大于0的ACK报文,而此ACK的输出是不可靠的,如果此ack丢失了,那么,发送端永远不会向接收端发送数据,因为他认为接收端的缓存是满的,而接收端却在等待发送端发送数据(因为发送了一个大于0的窗口),这就产生了死锁。
    • 解决方案: 使用坚持定时器。当发送端接收到接收端窗口为0的回复,那么发送端启动坚持定时器,然后定期向接收端发送一个字节的报文段的,直到接收端回复缓存可用为止。(TCP总是允许在关闭连接前发送一个字节的数据)
    • 工作过程
      • 1.发送端收到0窗口通告后,启动坚持定时器,并在定时器溢出的时候向客户端查询窗口是否已经增大
      • 2在定时器未到,就收到非0通告,则关闭定时器。并发送数据
      • 3若定时器已到,还没有收到非0通告,就发送探查报文
      • 4如果探查报文ACK的通告窗口为0,将坚持定时器的值加倍,TCP的坚持定时器使用1,2,4,8,18。。64这样的普通指数退避来作为每一次的溢出时间,重复1,2,3步,直至通告窗口非0,发送数据,关闭定时器。
    • 糊涂窗口综合征
      • 可发生在两端中的任何一端:接收方可以通告一个小的窗口(而不是一直等到有大的窗口时才通告),而发送方也可以发送少量的数据(而不是等待其他的数据以便发送一个大的报文段)
      • 解决方案
        • 接收方不通告小窗口
        • 发送方避免出现糊涂窗口综合症的措施是仅在满足下列条件时才发送数据
          • 可以发送一个满长度的报文
          • 可以发送至少是接收方通告最大窗口大小一半的报文
          • 没有还未被确认的数据时或者TCP连接上禁止使用Nagle算法(能够发送手头的所有数据并且不希望接收ACK,或者该连接禁止了Nagle算法时,可以发送任意数据。)
  • TCP保活定时器

    • 许多时候一个服务器希望知道客户主机是否关机或者崩溃又重新启动。许多实现提供的保活定时器可以提供这种能力

DNS

  • 域名解析, www.xxx.com 转换成 ip
  • DNS 协议运行在 UDP 协议之上,使用端口号 53
  • 主机解析域名的顺序
    • 浏览器缓存
    • 找本机的 hosts 文件
    • 路由缓存
    • 找 DNS 服务器(本地域名、顶级域名、根域名)
      • 迭代查询、递归查询
  • 一、主机向本地域名服务器的查询一般都是采用递归查询。
    • 递归查询就是如果主机所询问的本地域名服务器不知道查询域名的IP,那么本地域名服务器已DNS客户的形式向其他跟域名服务器继续发出查询报文请求(替主机继续查询),而不是让主机自己进行下一步查询。因此,递归查询的查询结果或者是所要查询的IP,或者报错,表示找不到IP
  • 本地域名服务器向根域名服务器的查询为迭代查询
    • 当根域名服务器收到本地域名服务器发出的迭代查询报文时,要么给出所要查询的IP地址,要么告诉本地服务器,你下一步应当向哪一个域名服务器进行查询。然后让本地服务器进行后续查询。根域名服务器通常把自己知道的顶级域名服务器的IP地址告诉本地域名服务器,让本地域名服务器再向顶级域名服务器查询。顶级域名服务器再收到本地域名服务器的查询请求后,要么给出所要查询的IP地址,要么告诉本地服务器下一步应当向哪一个权限域名服务器进行查询。最后知道了所要解析的IP地址,然后把这个结果返回给发起查询的主机。
  • DNS_CLIENT客户端查看HOSTS文件以及本地DNS缓存,没有找到对应记录
  • DNS-CLIENT联系本地DNS服务器,查询域名www.google.com
  • DNS-Server 联系根域名服务器 查询 www.google.com
  • 根域名服务器返回 com顶级域名服务器的IP
  • DNS-Server联系 com DNS Server
  • com DNS Server 返回 google.com域的DNS服务器IP
  • DNS服务器联系 google.com DNS Server,
  • google.com DNS Server 返回IP地址
  • DNS Server 向DNS-Client 返回www.google.com的IP
  • DNS-Client向该IP发送数据传出请求

HTTP

  • 超文本传输协议,

    • 请求报文由请求行,请求头,空行,消息体实现
    • 响应报文由状态行,响应头,空行,消息体实现
  • 返回码

    • 1xx,指示信息-表示请求已接收,继续处理
    • 2xx,成功-表示请求已被成功接收、理解、接受
    • 3xx,重定向-要完成请求必须进行更进一步的操作
    • 4xx,客户端错误-请求有语法错误或者请求无法实现
    • 5xx,服务器错误=服务器未能实现合法的请求
    • 200 OK,客户端请求成功
    • 204 No Content。服务器聚堆对PUT POST或者DELETE请求返回任何状态信息或表示
    • 206 partial content 服务器已经正确处理部分GET请求,实现断点续传或同时分片下载,该请求必须包含Range请求头来指示客户端期望得到的范围
    • 300 multiple choice(可选重定向)若被请求的资源在服务器端存在多个表示,而服务器不知道客户端想要的是哪一个表示时,发送这个响应代码
    • 301 moved permanently(永久重定向),该资源已被永久移动到新位置,将来任何对该资源的访问都要使用本响应返回的若干个URI之一,服务器知道客户端试图访问的是哪个资源,但它不喜欢客户端用当前URI来请求该资源。它希望客户端记住另一个URI,并在今后的请求中使用那个新的URI
    • 302 move temporarily(临时重定向);请求的资源现在临时从不同的URI中获得
    • 304 not modified 如果客户端发送一个待条件的GET请求并且该请求已经被允许,而文档内容未改变,则返回304,响应不包含内容体
    • 403 forbidden 服务器收到请求,但是拒绝提供服务,
    • 400 :Bad Request,请求出错,由于语法格式有误,服务器无法理解此请求。不做修改,客户程序就无法重复
    • 401:Unauthorized,客户端对一个受保护的资源进行操作,却又没有提供正确的认证证书。
    • 404:Not Found,404表明服务器无法把客户端请求的URI转换为一个资源
    • 500:Internal Server Error。通用的服务器错误响应
    • 503(“Service Unavailable”)。响应代码表明HTTP服务器正常,只是下层web服务服务不能正常工作。最可能的原因是资源不足:服务器突然收到太多请求,以至于无法全部处理。由于此问题多半由客户端反复发送请求造成,因此HTTP服务器可以选择拒绝接受客户端请求而不是接受它,并发送503响应代码。
    • 505(“HTTP Version Not Supported”),当服务器不支持客户端试图使用的HTTP版本时发送此响应代码。
  • GET VS POST

    • get请求通过url传递,url中传递的参数有长度限制,只能进行url编码

    • post请求放在request body中,没有长度限制,安全,有多种编码方式

    • GET请求,产生一个TCP数据包,浏览器会将http header 和data一并发送出去,服务器响应200(返回数据)

    • POST请求,产生两个TCP数据包,浏览器首先发送header,服务器响应100,浏览器再发送data,服务器响应200

    • get请求参数会完整保留在浏览历史记录中,post参数不会

  • Cookie VS Session

    • cookie 是一种发送到客户浏览器的文本串句柄,并保存在客户机硬盘上,可以用来在
      某个 WEB 站点会话间持久的保持数据
    • session 其实指的就是访问者从到达某个特定主页到离开为止的那段时间。 Session 其
      实是利用 Cookie 进行信息处理的,当用户首先进行了请求后,服务端就在用户浏览器
      上创建了一个 Cookie,当这个 Session 结束时,其实就是意味着这个 Cookie 就过期了
    • cookie 数据保存在客户端, session 数据保存在服务器端
  • 一次完整的HTTP请求

    • 客户端浏览器通过DNS解析IP地址。
    • 发起TCP的3次握手
    • 建立TCP连接后发起http请求
    • 服务器响应http请求,浏览器得到html代码
    • 浏览器解析html代码,并请求html代码中的资源
    • 浏览器对页面进行渲染呈现给用户
  • HTTP VS HTTPS

    • HTTP协议以明文方式在网络中传输数据,HTTPS协议传输的数据经TLS加密后传输
    • HTTPS在经过TCP三次握手后,还要进行SSL的handshake,协商加密使用的对称加密秘钥
    • HTTPS需要服务端申请证书,浏览器安装相应证书
    • HTTP端口80,HTTPS端口443
    • HTTPS传输过程中使用秘钥加密,安全
    • HTTPS认证用户和服务器,确保数据发送到正确的用户和服务器
  • HTTP 1.0 VS HTTP1.1

    • 增加了缓存控制策略,Entity tag,If-Unmodified-Since, If-Match, If-None-Match
    • 带宽优化及网络连接的使用,请求头引入了range头域,允许只请求资源的某个部分,即返回码是206(Partial Content)。
    • 错误通知的管理,在HTTP1.1中新增了24个错误状态响应码。如409(Conflict)表示请求的资源与资源的当前状态发生冲突;410(Gone)表示服务器上的某个资源被永久性的删除
    • Host头处理,在HTTP1.0中认为每台服务器都绑定一个唯一的IP地址,因此,请求消息中的URL并没有传递主机名(hostname)。HTTP1.1的请求消息和响应消息都应支持Host头域,且请求消息中如果没有Host头域会报告一个错误(400 Bad Request)
    • 长连接,HTTP 1.1支持长连接(PersistentConnection)和请求的流水线(Pipelining)处理,在一个TCP连接上可以传送多个HTTP请求和响应,减少了建立和关闭连接的消耗和延迟
  • HTTP1.1 VS HTTP2.0

    • HTTP2.0采用二进制格式而不是文本格式
    • HTTP2.0完全的多路复用,非有序阻塞,只要有一个连接就可以实现并行
    • 使用报头压缩,HTTP2.0降低了开销
    • HTTP2.0让服务器可以将响应主动推送到客户端缓存中

    HTTPS

    • 非对称加密算法:RSA,DSA/DSS

      对称加密算法:AES,RC4,3DES 
      HASH算法:MD5,SHA1,SHA256
    • 握手过程

      • 客户端发送HTTP连接请求
        • 浏览器将自己支持的一套加密规则发送给网站
      • 服务器响应
        • 选择合适的加密算法,和hash算法,并将自己的身份信息已证书形式发送给浏览器。(证书包含,服务端加密的公钥,以及证书的颁发机构,证书的数字签名,网站地址,)
      • 客户端验证服务器端数字签名,发送秘钥给服务器
        • 验证证书中的数字签名
        • 生成随机数a,作为对称加密的秘钥,使用服务端公钥对a进行加密得到b
        • 生成握手消息,以a为秘钥进行对称加密得到c。
        • 计算握手消息的hash值,得到d
        • 将b,c,d发送给服务端
      • 服务端确认加密秘钥
        • 使用私钥解密b,得到a
        • 以a为秘钥,解密c得到握手消息
        • 计算握手消息的hash,验证是否与d相等
        • 生成新的握手消息,以a为秘钥进行对称加密,得到e
        • 计算新的握手消息的hash,得到f
        • 将e,f发送客户端
      • 握手过程完成,客户端发送加密数据给服务端
        • 以a为秘钥对e进行对称解密,得到握手消息
        • 计算握手消息的hash,验证是否与f相等
        • 至此,握手结束,之后所有数据已a为秘钥进行对称加密后传输
    • 客户端验证服务端数字签名

      • 获取对应证书颁发机构的公钥

        • 根据证书的数字签名,获取对应证书颁发机构的公钥,该公钥被根证书颁发机构使用其私钥加密过的
    • 解密并获得证书颁发机构的公钥

      • 使用本地根证书公钥,解密获得证书颁发机构的公钥。本地根证书公钥是在用户安装操作系统时,由操作系统写入浏览器

      • 解密数字签名,验证服务端公钥

        • 使用证书颁发机构的公钥,解密数字签名得到服务端公钥的hash,
      • 计算服务端公钥的hash,验证两者是否相同

KEEP-ALIVE

  • HTTP
    • 通过使用keep-alive机制,可以减少tcp连接建立次数,也意味着可以减少TIME_WAIT状态连接,以此提高性能和提高httpd服务器的吞吐率(更少的tcp连接意味着更少的系统内核调用,socket的accept()和close()调用)
    • keep-alive并不是免费的午餐,长时间的tcp连接容易导致系统资源无效占用。配置不当的keep-alive,有时比重复利用连接带来的损失还更大。所以,正确地设置keep-alive timeout时间非常重要
  • TCP
    • 链接建立之后,如果应用程序或者上层协议一直不发送数据,或者隔很长时间才发送一次数据,当链接很久没有数据报文传输时如何去确定对方还在线,到底是掉线了还是确实没有数据传输,链接还需不需要保持,这种情况在TCP协议设计中是需要考虑到的。
    • TCP协议通过一种巧妙的方式去解决这个问题,当超过一段时间之后,TCP自动发送一个数据为空的报文给对方,如果对方回应了这个报文,说明对方还在线,链接可以继续保持,如果对方没有报文返回,并且重试了多次之后则认为链接丢失,没有必要保持链接

套接字socket

  • 1
    2
    3
    int epoll_create(int size); 
    int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); //epoll的事件注册函数,注册监控的文件描述符以及所监控的事件
    int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);//等待事件产生,返回需要处理的时间的数目
  • 边缘触发

    • 设置socket非阻塞
    • epoll_ctl设置边缘触发
    • 在读取数据时需要读完,read返回-1,errno=EAGAIN

数据结构和算法

稳定排序

  • 有两个排序关键字的时候,稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。

各种树

  • rb tree VS AVL tree

    • AVL 树要求严格,对于任何一个节点,其左右子树的高度差最多等于1,

    • 对于有n个节点的红黑树,最差情况下,它的最大高度可能会达到2logn(仍是O(logn)级别的复杂度)

    • 对红黑树进行增删改查操作,复杂度都是O(logn)。 可以看出,在红黑树中查找元素其实比AVL要慢(因为AVL高度为O(logn),但是,在红黑树中增加和删除元素要比AVL快。

    • 红黑树不追求”完全平衡”,即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。

    • 就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)

    • 删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!

    • AVL的结构相较于RB-Tree更为平衡,插入和删除引起失衡,如2所述,RB-Tree复衡效率更高;当然,由于AVL高度平衡,因此AVL的Search效率更高啦。

    • 针对插入和删除节点导致失衡后的rebalance操作,红黑树能够提供一个比较”便宜”的解决方案,降低开销,是对search,insert ,以及delete效率的折衷,总体来说,RB-Tree的统计性能高于AVL.

    • AVL树适合用于插入与删除次数比较少,但查找多的情况;相对于要求严格的AVL树来说,红黑树的旋转次数少,所以对于搜索、插入、删除操作较多的情况下,我们就用红黑树

  • B tree B+ Tree

    • B-树 即B树
    • B 树=有序数组+二叉搜索树
    • B+树=有序链表+二叉搜索树
    • B+树比B树更适合数据库索引
      • B+树的磁盘读写代价更低,B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了
      • B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当
      • 由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引

hashtable 哈希表

  • 负载系数=元素个数/表格大小

  • 避免地址冲突

    • 线性探测:如果hash函数计算某个元素的插入位置后,如果该位置的空间已经被占据,则继续向下寻找,直到找到一个可用空间为止,尝试H+1,H+2,H+3,H+4

    • 二次探测:如果计算的位置被占用,依次尝试H+1^2,H+2^2,H+3^2,H+4^2,

      • 设置表格大小为质数,永远保持负载系数在0.5以下(超过0.5重新配置并整理表格),确定没插入一个元素所需要的探测次数不多于2
    • 开链,维护buckets,bucket个数为质数,每个表格元素bucket维护一个list,在那个list中执行插入,删除,前提list够短,负载>1,当元素个数大于bucket个数时,链表打散rehashing,bucket大小变为两倍大小左右的素数

      • vector 维护buckets
      • 通过hash函数%表长,获得bucket索引,之后再bucket所维护的链表中轮询,如果相等,直接插入前面,否则,新建节点添加到头部

        二叉树性质

  • ​ 性质1 : 二叉树的第 i 层上至多有 2^(i-1) 个结点 (i>=1)

    ​ 性质2 : 深度为 k 的二叉树至多有 2^k -1 个结点( k>=1)

    ​ 性质3 : 对任意的一颗二叉树 T ,若叶子结点数为 n0,而其度数为 2 的结点数为 n2,则 n0 = n2+1

    ​ 性质4 : 具有 n 个结点的完全二叉树的深度 [log2n]+1

    ​ 性质 5: 如果有一颗有n个节点的完全二叉树的节点按层次序编号,对任一层的节点i(1<=i<=n)有

    ​ (1).如果i=1,则节点是二叉树的根,无双亲,如果i>1,则其双亲节点为[i/2],向下取整

    ​ (2).如果2i>n那么节点i没有左孩子,否则其左孩子为2i

    ​ (3).如果2i+1>n那么节点没有右孩子,否则右孩子为2i+1

    • 具有n个结点的完全二叉树(包括满二叉树)的高度为[log2n+1] (向下取整)
      or{log2(n+1)}(向上取整)

平衡二叉树

  • 二叉搜索树

  • AVL-TREE

  • RB-tree 是二叉搜索树

    • 每个节点不是黑色就是红色
    • 根节点为黑色
    • 若节点为红色,子节点一定为黑
    • 任一节点到NULL(树尾端)的任何路径,所含黑节点个数必须相同
  • AA-TREE

排序算法

数据库

项目

  • epoll

    • 1
       
  • 线程池实现

    • 领导者跟随者模式
      • 在LF线程池中,线程可处在3种线程状态之一:leader、follower或processor。处于leader状态的线程负责监听网络端口,当有消息到达时,该线程负责消息分离,并从处于 follower状态中的线程中按照某种机制如FIFO或基于优先级等选出一个来当新的leader,然后将自己设置为processor状态去分配和处理该事件。处理完毕后线程将自身的状态设置为follower状态去等待重新成为leader。在整个线程池中同一时刻只有一个线程可以处于leader状态,这保证了同一事件不会被多个线程重复处理
      • 一个线程安全的queue维护一个任务队列,(类,有thread_handle函数)
      • 创建N个线程,每个线程的处理函数都process_task函数,
      • 在process_task中,提升一个领导者,然后从任务队列中pop一个,添加一个跟随者,执行线程处理函数

设计模式

singleton

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Singleton{
    private:
    Singleton(){}
    Singleton(const Singleton&){}
    ~Singleton();
    public:
    static Singleton& getInstance(){
    static Singleton ss;
    return ss;
    }
    }

观察者模式

  • 1570690570733

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    class Observer
    {
    public:
    virtual void Update(int) = 0;
    };

    class Subject
    {
    public:
    virtual void Attach(Observer *) = 0;
    virtual void Detach(Observer *) = 0;
    virtual void Notify() = 0;
    };

    class ConcreteObserver : public Observer
    {
    public:
    ConcreteObserver(Subject *pSubject) : m_pSubject(pSubject){}

    void Update(int value)
    {
    cout << "ConcreteObserver get the update. New State:" << value << endl;
    }

    private:
    Subject *m_pSubject;
    };

    class ConcreteObserver2 : public Observer
    {
    public:
    ConcreteObserver2(Subject *pSubject) : m_pSubject(pSubject){}

    void Update(int value)
    {
    cout << "ConcreteObserver2 get the update. New State:" << value << endl;
    }

    private:
    Subject *m_pSubject;
    };

    class ConcreteSubject : public Subject
    {
    public:
    void Attach(Observer *pObserver);
    void Detach(Observer *pObserver);
    void Notify();

    void SetState(int state)
    {
    m_iState = state;
    }

    private:
    std::list<Observer *> m_ObserverList;
    int m_iState;
    };

    void ConcreteSubject::Attach(Observer *pObserver)
    {
    m_ObserverList.push_back(pObserver);
    }

    void ConcreteSubject::Detach(Observer *pObserver)
    {
    m_ObserverList.remove(pObserver);
    }

    void ConcreteSubject::Notify()
    {
    std::list<Observer *>::iterator it = m_ObserverList.begin();
    while (it != m_ObserverList.end())
    {
    (*it)->Update(m_iState);
    ++it;
    }
    }

    int main()
    {
    // Create Subject
    ConcreteSubject *pSubject = new ConcreteSubject();

    // Create Observer
    Observer *pObserver = new ConcreteObserver(pSubject);
    Observer *pObserver2 = new ConcreteObserver2(pSubject);

    // Change the state
    pSubject->SetState(2);

    // Register the observer
    pSubject->Attach(pObserver);
    pSubject->Attach(pObserver2);

    pSubject->Notify();

    // Unregister the observer
    pSubject->Detach(pObserver);

    pSubject->SetState(3);
    pSubject->Notify();

    delete pObserver;
    delete pObserver2;
    delete pSubject;
    }

场景问题

  • N个有序的数组,每个都有M个元素,排序
文章目录
  1. 1. C++
    1. 1.1. 成员变量初始化顺序
    2. 1.2. RTTI
    3. 1.3. strcpy strncpy
    4. 1.4. ASCII-utf-8-unicode
    5. 1.5. 为什么static函数不能const修饰和virtual修饰
    6. 1.6. 判断一个对象调用是否经过虚函数表
    7. 1.7. lambda实现原理
    8. 1.8. C++/C的类型安全
    9. 1.9. auto VS decltype
    10. 1.10. 访问权限
    11. 1.11. 程序优化
    12. 1.12. 异常
    13. 1.13. 四种类型转换
    14. 1.14. C/C++函数调用的压栈模型
    15. 1.15. 成员初始化列表
    16. 1.16. 内存泄漏
    17. 1.17. 结构体内存对齐
    18. 1.18. 构造函数
    19. 1.19. 引用和指针实现多态
    20. 1.20. 构造函数的几种关键字(default delete 0)
    21. 1.21. 成员模板
    22. 1.22. final VS override
    23. 1.23. struct VS class
    24. 1.24. 指针和引用区别
    25. 1.25. main函数之前
    26. 1.26. main返回值
    27. 1.27. C++内存模型
    28. 1.28. 面向对象的四个特性
    29. 1.29. 堆和栈的区别
    30. 1.30. volatile
    31. 1.31. 内联函数VS宏定义
    32. 1.32. C++ VS C最大特点
    33. 1.33. static_assert
    34. 1.34. c++11新特性
    35. 1.35. 访问类的私有变量
    36. 1.36. 二维数组
    37. 1.37. 虚基类表
    38. 1.38. extern C
    39. 1.39. 编译型VS解释型VS动态语言VS静态语言
    40. 1.40. 构造函数 VS析构函数
    41. 1.41. 拷贝构造VS 赋值构造
    42. 1.42. overload VS override VS overwrite
    43. 1.43. 变量的声明和定义
    44. 1.44. new的变种
    45. 1.45. 特殊对象构建
    46. 1.46. 内存分配方式
    47. 1.47. static const关键字
    48. 1.48. define 和const的区别
    49. 1.49. 智能指针
    50. 1.50. 移动语义
    51. 1.51. 自定义函数
  2. 2. STL
    1. 2.1. 空间配置器
    2. 2.2. 迭代器
    3. 2.3. vector实现
    4. 2.4. list实现
    5. 2.5. deque实现
    6. 2.6. priority_queue
    7. 2.7. set-map实现
    8. 2.8. unordered-set/map实现
    9. 2.9. 算法
  3. 3. C++11 多线程
    1. 3.1. linux命令
  4. 4. 操作系统
    1. 4.1. 内存管理
    2. 4.2. 可重入函数
    3. 4.3. copy on write
    4. 4.4. 页面置换算法
    5. 4.5. 进程调度
    6. 4.6. 内存分配方式及错误
    7. 4.7. 内存溢出VS内存泄漏
    8. 4.8. 虚拟内存VS swap分区
    9. 4.9. 中断VS异常
    10. 4.10. 进程终止的方式
    11. 4.11. 特殊进程
    12. 4.12. 怎么回收线程
    13. 4.13. 进程/线程数量
    14. 4.14. 一个程序从开始运行到结束的完整过程
    15. 4.15. 用户态VS内核态
    16. 4.16. 死锁
    17. 4.17. 进程间通信方式
    18. 4.18. linux IO模型
    19. 4.19. select VS epoll
    20. 4.20. 进程VS 协程
    21. 4.21. 硬链接、软连接
    22. 4.22. 用户权限
    23. 4.23. linux命令
  5. 5. 计算机网络
    1. 5.1. TCP/IP协议体系
    2. 5.2. 数据链路层
    3. 5.3. IP
    4. 5.4. UDP
    5. 5.5. TCP
    6. 5.6. DNS
    7. 5.7. HTTP
    8. 5.8. HTTPS
    9. 5.9. KEEP-ALIVE
    10. 5.10. 套接字socket
  6. 6. 数据结构和算法
    1. 6.1. 稳定排序
    2. 6.2. 各种树
    3. 6.3. hashtable 哈希表
    4. 6.4. 二叉树性质
    5. 6.5. 平衡二叉树
    6. 6.6. 排序算法
  7. 7. 数据库
  8. 8. 项目
  9. 9. 设计模式
    1. 9.1. singleton
    2. 9.2. 观察者模式
  10. 10. 场景问题