网站关键词代码怎么做,公司 网站建设,建设北京公司网站,网站开发logo一、c/c语言基础
1、基础
1、指针和引用的区别
指针是一个新的变量#xff0c;指向另一个变量的地址#xff0c;我们可以通过这个地址来修改该另一个变量#xff1b; 引用是一个别名#xff0c;对引用的操作就是对变量本身进行操作#xff1b;指针可以有多级 引用只有一…一、c/c语言基础
1、基础
1、指针和引用的区别
指针是一个新的变量指向另一个变量的地址我们可以通过这个地址来修改该另一个变量 引用是一个别名对引用的操作就是对变量本身进行操作指针可以有多级 引用只有一级传参的时候使用指针的话需要解引用才能对参数做修改 而使用引用可以直接对参数进行修改指针的大小一般是四个字节 引用的大小取决于被引用对象的大小指的是使用sizeof运算符得到的结果引用本质上还是使用指针因此所占内存和指针是一样的指针可以为空 引用不行
2、在函数传递参数时什么时候用指针什么时候用引用
需要返回函数内局部变量的地址的内存时使用指针。使用指针传参需要开辟内存用完要记得释放指针不然会有内存泄漏。而返回局部变量的引用是没有意义的对栈空间大小比较敏感如递归的时候使用引用。使用引用不需要创建临时变量开销更小类对象作为参数传递时使用引用这是C类对象传递的标准方式。
3、堆和栈有什么区别
定义上堆是由new和malloc开辟的一块内存由程序员手动管理 栈是编译器自动管理的内存存放函数的参数和局部变量。堆空间因为会有频繁的分配释放操作会产生内存碎片。堆的生长空间向上地址越来越大 栈的生长空间向下地址越来越小。
4、堆快一些还是栈快一些
栈快一些。操作系统在底层会对栈提供支持会分配专门的寄存器存放栈的地址栈的入栈出栈操作也十分简单并且有专门的指令执行所以栈的效率比价快也比较高。而堆的操作是由C/C函数库提供的在分配堆内存的时候需要一定的算法寻找合适的内存大小并且获取堆的内容需要两次访问第一次访问指针第二次根据指针保存的地址访问内存因此堆比较慢。
5、new和delete是如何实现的new和malloc的异同
在new一个对象的时候首先会调用malloc为对象分配内存空间然后调用对象的构造函数。delete会调用对象的析构函数然后调用free回收内存。new 和 malloc都会分配空间但是new还会根据调用对象的构造函数进行初始化malloc需要给定空间大小而new只需要对象名。
5.1、linux下brk、mmap、malloc和new的区别
brk是系统调用主要工作是实现虚拟内存到内存的映射可以让进程的堆指针增长一定的大小逻辑上消耗掉一块虚拟地址空间malloc向OS获取的内存大小比较小时将直接通过brk调用获取虚拟地址。mmap是系统调用也是实现虚拟内存到内存的映射可以让进程的虚拟地址区间切分出一块指定大小的虚拟地址空间vma_struct一个进程的所有动态库文件.so的加载都需要通过mmap系统调用映射指定大小的虚拟地址区间被mmap映射返回的虚拟地址逻辑上被消耗了直到用户进程调用unmap会回收回来。malloc向系统获取比较大的内存时会通过mmap直接映射一块虚拟地址区间。malloc是C语言标准库中的函数主要用于申请动态内存的分配其原理是当堆内存不够时通过brk/mmap等系统调用向内核申请进程的虚拟地址区间如果堆内部的内存能满足malloc调用则直接从堆里获取地址块返回。new是C内置操作符用于申请动态内存的分配并同时进行初始化操作。其实现会调用malloc对于基本类型变量它只是增加了一个cookie结构, 比如需要new的对象大小是 object_size, 则事实上调用 malloc 的参数是 object_size cookie 这个cookie 结构存放的信息包括对象大小对象前后会包含两个用于检测内存溢出的变量所有new申请的cookie块会链接成双向链表。 对于自定义类型new会先申请上述的大小空间然后调用自定义类型的构造函数对object所在空间进行构造。
6、既然有了malloc/free为什么还要new/delete
malloc/free是c/c中的标准库函数new/delete是c中的运算符。它们都用于申请动态内存和释放内存。对于非内部数据对象如类对象只用malloc/free无法满足动态对象的要求。这是因为对象在创建的同时需要自动执行构造函数对象在消亡之前要自动执行析构函数而由于malloc/free是库函数而不是运算符不在编译器的控制权限之内也就不饿能自动执行构造函数和析构函数。因此不能将执行构造函数和析构函数的任务强加给malloc/free。所以在c中需要一个能完成动态内存分配和初始化工作的运算符new以及一个能完成清理和释放内存工作的运算符delete。
7、C和C的区别
C面向过程 c面向对象。 c有封装继承和多态的特性。封装隐藏了实现细节使得代码模块化。继承通过子类继承父类的方法和属性实现了代码重用。多态则是“一个接口多个实现”通过子类重写父类的虚函数实现接口重用。C和C内存管理的方法不一样C使用malloc/freeC除此之外还用new/deleteC中还有函数重载和引用等概念C中没有
8、delete和delete[]区别
delete只调用一次析构函数delete[]会调用每个成员的析构函数用new分配的内存用delete释放用new[]分配的内存用delete[]释放调用new []之后释放内存使用delete[]没有指定需要析构的对象的个数自己设计编译器的话怎么实现operator delete。 就是申请内存时可以多分配几个字节用来存放对象个数delete[]的时候可以先调整指针位置来获取这个值。 《深入探索c对象模型》中解决方法为vec_new()所传回的每一个内存区块配置一个额外的word然后把元素个数藏在这个word当中
9、 C、Java的联系与区别包括语言特性、垃圾回收、应用场景等
C 和Java都是面向对象的语言C是编译成可执行文件直接运行的JAVA是编译之后在JAVA虚拟机上运行的因此JAVA有良好的跨平台特性但是执行效率没有C 高。C的内存管理由程序员手动管理JAVA的内存管理是由Java虚拟机完成的它的垃圾回收使用的是标记-回收算法C有指针Java没有指针只有引用JAVA和C都有构造函数但是C有析构函数但是Java没有
10、c和python区别
python是一种脚本语言是解释执行的而C是编译语言是需要编译后在特定平台运行的。python可以很方便的跨平台但是效率没有C高。python使用缩进来区分不同的代码块C使用花括号来区分C中需要事先定义变量的类型而python不需要python的基本数据类型只有数字布尔值字符串列表元组等等python的库函数比C的多调用起来很方便
11、Struct和class的区别
struct的成员的访问权限默认是public而class的成员默认是privatestruct的继承默认是publilc继承而class的默认继承是private继承class可以在作为模板而struct不可以
12、define和const的联系与区别
联系他们都是定义常量的一种方法。区别 define定义的变量没有类型只是进行简单的替换可能会有多个拷贝占用的内存空间大 const定义的常量是有类型的存放在静态存储区只有一个拷贝占用的内存空间小。define定义的常量实在预处理阶段进行替换而const在编译阶段确定它的值。define不会进行安全类型检查而const会进行类型安全检查安全性更高const可以定义函数而define不可以。
13、在c中const的用法定义、用途
const修饰类的成员变量目标是常量不能被修改const修饰类的成员函数表示该函数不会修改类的数据成员不会调用其他非const的成员函数。
14、C中static的用法和意义
static的意思是静态的用来修饰变量函数和类成员。
变量被static修饰的变量就是静态变量它会在程序运行过程中一直存在会被放在静态存储区。局部静态变量的作用域在函数体内全局静态变量的作用域在这个文件内。函数被static修饰过的函数就是静态函数静态函数只能在本文件中使用不能被其他文件调用也不会和其他文件中的同名函数冲突。类在类中被static修饰的成员变量是类静态成员这个静态成员会被类的多个对象共用。被static修饰的成员函数也属于静态成员不是属于某个对象的访问这个静态函数不需要引用对象名而是通过引用类名来访问。
补充
全局静态变量 定义在全局变量之前加上关键字static全局变量就被定义成为一个全局静态变量。 说明 1内存中的位置静态存储区静态存储区在整个程序运行期间都存在 2初始化未经初始化的全局静态变量会被程序自动初始化为0自动对象的值是任意的除非它被显示初始化 3作用域全局静态变量在声明它的文件之外是不可见的。 全局静态变量的好处 1不会被其他文件所访问修改 2其他文件中可以使用相同名字的变量不会发生冲突。局部静态变量 定义在局部变量之前加上关键字static局部变量就被定义成为一个局部静态变量。 说明 1内存中的位置静态存储区 2初始化未经初始化的局部静态变量会被程序自动初始化为0自动对象的值是任意的除非他被显示初始化 3作用域作用域仍为局部作用域当定义它的函数或者语句块结束的时候作用域随之结束。
注意当static用来修饰局部变量的时候它就改变了局部变量的存储位置从原来的栈中存放改为静态存储区。但是局部静态变量在离开作用域之后并没有被销毁而是仍然驻留在内存当中直到程序结束只不过我们不能再对它进行访问。 当static用来修饰全局变量的时候它就改变了全局变量的作用域在声明它的文件之外是不可见的但是没有改变它的存放位置还是在静态存储区中。
15、计算以下几个类的大小
class A {};
int main(){coutsizeof(A)endl;// 输出 1;A a; coutsizeof(a)endl;// 输出 1;return 0;
}空类的大小是1 在C中空类会占一个字节这是为了让对象的实例能够相互区别。具体来说空类同样可以被实例化并且每个实例在内存中都有独一无二的地址因此编译器会给空类隐含加上一个字节这样空类实例化之后就会拥有独一无二的内存地址。当该空白类作为基类时该类的大小就优化为0了子类的大小就是子类本身的大小。这就是所谓的空白基类最优化。
空类的实例大小就是类的大小所以sizeof(a)1字节,如果a是指针则sizeof(a)就是指针的大小即4字节。
class A { virtual Fun(){} };
int main(){coutsizeof(A)endl;// 输出 4(32位机器)/8(64位机器);A a; coutsizeof(a)endl;// 输出 4(32位机器)/8(64位机器);return 0;
}因为有虚函数的类对象中都有一个虚函数表指针 __vptr其大小是4字节
class A { static int a; };
int main(){coutsizeof(A)endl;// 输出 1;A a; coutsizeof(a)endl;// 输出 1;return 0;
}静态成员存放在静态存储区不占用类的大小, 普通函数也不占用类大小
class A { int a; };
int main(){coutsizeof(A)endl;// 输出 4;A a; coutsizeof(a)endl;// 输出 4;return 0;
}class A { static int a; int b; };;
int main(){coutsizeof(A)endl;// 输出 4;A a; coutsizeof(a)endl;// 输出 4;return 0;
}静态成员a不占用类的大小所以类的大小就是b变量的大小即4个字节
16、定义和声明的区别
声明是告诉编译器变量的类型和名字不会为变量分配空间 定义就是对这个变量和函数进行内存分配和初始化。需要分配空间同一个变量可以被声明多次但是只能被定义一次
17、typdef和define区别
#define是预处理命令在预处理是执行简单的替换不做正确性的检查 typedef是在编译时处理的它是在自己的作用域内给已经存在的类型一个别名
18、被free回收的内存是立即返还给操作系统吗为什么
不是的被free回收的内存会首先被ptmalloc使用双链表保存起来当用户下一次申请内存的时候会尝试从这些内存中寻找合适的返回。这样就避免了频繁的系统调用占用过多的系统资源。同时ptmalloc也会尝试对小块内存进行合并避免过多的内存碎片。
19、引用作为函数参数以及返回值的好处
对比值传递引用传参的好处
1在函数内部可以对此参数进行修改
2提高函数调用和运行的效率因为没有了传值和生成副本的时间和空间消耗
如果函数的参数实质就是形参不过这个形参的作用域只是在函数体内部也就是说实参和形参是两个不同的东西要想形参代替实参肯定有一个值的传递。函数调用时值的传递机制是通过“形参实参”来对形参赋值达到传值目的产生了一个实参的副本。即使函数内部有对参数的修改也只是针对形参也就是那个副本实参不会有任何更改。函数一旦结束形参生命也宣告终结做出的修改一样没对任何变量产生影响。
用引用作为返回值最大的好处就是在内存中不产生被返回值的副本。
但是有以下的限制
1不能返回局部变量的引用。因为函数返回以后局部变量就会被销毁
2不能返回函数内部new分配的内存的引用。虽然不存在局部变量的被动销毁问题可对于这种情况返回函数内部new分配内存的引用又面临其它尴尬局面。例如被函数返回的引用只是作为一 个临时变量出现而没有被赋予一个实际的变量那么这个引用所指向的空间由new分配就无法释放造成memory leak
3可以返回类成员的引用但是最好是const。因为如果其他对象可以获得该属性的非常量的引用那么对该属性的单纯赋值就会破坏业务规则的完整性。
20、友元函数和友元类
友元提供了不同类的成员函数之间、类的成员函数和一般函数之间进行数据共享的机制。通过友元一个不同函数或者另一个类中的成员函数可以访问类中的私有成员和保护成员。友元的正确使用能提高程序的运行效率但同时也破坏了类的封装性和数据的隐藏性导致程序可维护性变差。
21、说一下volatile关键字的作用
volatile的意思是“脆弱的”表明它修饰的变量的值十分容易被改变所以编译器就不会对这个变量进行优化CPU的优化是让该变量存放到CPU寄存器而不是内存进而提供稳定的访问。每次读取volatile的变量时系统总是会从内存中读取这个变量并且将它的值立刻保存。
22、STL中的sort()算法是用什么实现的stable_sort()呢
STL中的sort是用快速排序和插入排序结合的方式实现的stable_sort()是归并排序。
23、vector会迭代器失效吗什么情况下会迭代器失效
会当vector在插入的时候如果原来的空间不够会将申请新的内存并将原来的元素移动到新的内存此时指向原内存地址的迭代器就失效了first和end迭代器都失效当vector在插入的时候end迭代器肯定会失效当vector在删除的时候被删除元素以及它后面的所有元素迭代器都失效。
24、为什么C没有实现垃圾回收
首先实现一个垃圾回收器会带来额外的空间和时间开销。你需要开辟一定的空间保存指针的引用计数和对他们进行标记mark。然后需要单独开辟一个线程在空闲的时候进行free操作。垃圾回收会使得C不适合进行很多底层的操作。
25、有一个类A里面有个类B类型的b还有一个B类型的*b什么情况下要用到前者什么情况下用后者
一个具体的类和一个类的指针主要差别就是占据的内存大小和读写速度。类占据的内存大但是读写速度快。类指针内存小但是读写需要解引用。所以可知以搜索为主的场景中应当使用类。以插入删除为主的场景中应当使用类指针。
2、STL
2.1、C的STL介绍
C STL从广义来讲包括了三类算法容器和迭代器。
算法包括排序复制等常用算法以及不同容器特定的算法。容器就是数据的存放形式包括序列式容器和关联式容器序列式容器就是listvector等关联式容器就是setmap等。迭代器就是在不暴露容器内部结构的情况下对容器的遍历。
2.2、STL源码中的hash表的实现
STL中的hash表就unordered_map。使用的是哈希进行实现注意与map的区别。它记录的键是元素的哈希值通过对比元素的哈希值来确定元素的值。 unordered_map的底层实现是hashtable采用开链法也就是用桶来解决哈希冲突默认的桶大小是10.哈希表的底层实现和扩容 HashMap实现原理和扩容机制
2.3、解决哈希冲突的方式
参考哈希冲突及四种解决方法
开放地址方法 当发生地址冲突时按照某种方法继续探测哈希表中的其他存储单元直到找到空位置为止。 1线性探测 按顺序决定值时如果某数据的值已经存在则在原来值的基础上往后加一个单位直至不发生哈希冲突。 2再平方探测 按顺序决定值时如果某数据的值已经存在则在原来值的基础上先加1的平方个单位若仍然存在则减1的平方个单位。随之是2的平方3的平方等等。直至不发生哈希冲突。 3伪随机探测 按顺序决定值时如果某数据已经存在通过随机函数随机生成一个数在原来值的基础上加上随机数直至不发生哈希冲突。链式地址法HashMap的哈希冲突解决方法 对于相同的值使用链表进行连接。使用数组存储每一个链表。 优点 1拉链法处理冲突简单且无堆积现象即非同义词决不会发生冲突因此平均查找长度较短 2由于拉链法中各链表上的结点空间是动态申请的故它更适合于造表前无法确定表长的情况 3开放定址法为减少冲突要求装填因子α较小故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1且结点较大时拉链法中增加的指针域可忽略不计因此节省空间 4在用拉链法构造的散列表中删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。 缺点 指针占用较大空间时会造成空间浪费若空间用于增大散列表规模进而提高开放地址法的效率。再哈希法当发生哈希冲突时使用另一个哈希函数计算地址值直到冲突不再发生。这种方法不易产生聚集但是增加计算时间同时需要准备许多哈希函数。建立公共溢出区采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突再采用处理冲突方法处理。
2.4 STL中unordered_map和map的区别
unordered_map是使用哈希实现的占用内存比较多查询速度比较快是常数时间复杂度。它内部是无序的需要实现操作符。map底层是采用红黑树实现的插入删除查询时间复杂度都是O(log(n))它的内部是有序的因此需要实现比较操作符()。
2.5 STL中vector的实现
STL中的vector是封装了动态数组的顺序容器。不过与动态数组不同的是vector可以根据需要自动扩大容器的大小。具体策略是每次容量不够用时重新申请一块大小为原来容量两倍的内存将原容器的元素拷贝至新容器并释放原空间返回新空间的指针。 在原来空间不够存储新值时每次调用push_back方法都会重新分配新的空间以满足新数据的添加操作。如果在程序中频繁进行这种操作还是比较消耗性能的。
2.6 vector使用的注意点及其原因频繁对vector调用push_back()对性能的影响和原因
如果需要频繁插入最好先指定vector的大小因为vector在容器大小不够用的时候会重新申请一块大小为原容器两倍的空间并将原容器的元素拷贝到新容器中并释放原空间这个过程是十分耗时和耗内存的。频繁调用push_back()会使得程序花费很多时间在vector扩容上会变得很慢。这种情况可以考虑使用list。
2.7 C中vector和list的区别
vector和数组类似拥有一段连续的内存空间。vector申请的是一段连续的内存当插入新的元素内存不够时通常以2倍重新申请更大的一块内存将原来的元素拷贝过去释放旧空间。因为内存空间是连续的所以在进行插入和删除操作时会造成内存块的拷贝时间复杂度为o(n)。list是由双向链表实现的因此内存空间是不连续的。只能通过指针访问数据所以list的随机存取非常没有效率时间复杂度为o(n); 但由于链表的特点能高效地进行插入和删除。vector拥有一段连续的内存空间能很好的支持随机存取因此vector::iterator支持“”“”“”等操作符。list的内存空间可以是不连续它不支持随机访问因此list::iterator则不支持“”、“”、“”等vector::iterator和list::iterator都重载了“”运算符。总之如果需要高效的随机存取而不在乎插入和删除的效率使用vector; 如果需要大量的插入和删除而不关心随机存取则应使用list。
2.8、string的底层实现
string继承自basic_string,其实是对char进行了封装封装的string包含了char数组容量长度等等属性。string可以进行动态扩展在每次扩展的时候另外申请一块原空间大小两倍的空间2*n然后将原字符串拷贝过去并加上新增的内容。
2.9 setmap和vector的插入复杂度
map, set, multimap, and multiset 上述四种容器采用红黑树实现红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为: 插入: O(logN) 查看:O(logN) 删除:O(logN)hash_map, hash_set, hash_multimap, and hash_multiset 上述四种容器采用哈希表实现不同操作的时间复杂度为 插入:O(1)最坏情况O(N)。 查看:O(1)最坏情况O(N)。 删除:O(1)最坏情况O(N)。vector的复杂度 查看O1 插入ON 删除ONlist复杂度 查看ON 插入O1 删除O1
set,map的插入复杂度就是红黑树的插入复杂度是log(N)。
unordered_set,unordered_map的插入复杂度是常数最坏是O(N)。
vector的插入复杂度是O(N),最坏的情况下从头插入就要对所有其他元素进行移动或者扩容重新拷贝 2.10、set、map特性与区别
setset是一种关联式容器特性如下
set低层以红黑树为低层容器低层实现红黑树所得元素的只有key没有valuevalue就是key不允许出现键值重复所有元素都会被自动排序不能通过迭代器来改变set的值因为set的值就是键
mapmap是一种关联式容器特性如下
map以红黑树作为底层容器低层实现红黑树所有元素都是键key值value存在不允许键key重复所有元素是通过键进行自动排序的map的键是不能修改的但是其键对应的值是可以修改的
uunordered_map
低层实现哈希表
2.11、map、set为什么要用红黑树实现
红黑树是一种二叉查找树但在每个节点上增加一个存储为用于表示节点的颜色可以是红或者黑。通过对任何一条从根到叶子节点的路径上各个节点的着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因此红黑树是一种弱平衡树但又相对与要求严格的AVL树来说他的旋转次数较少所以对于搜索插入删除操作比较多的情况下通常使用红黑树。
2.12 STL里迭代器什么情况下失效具体说几种情况
对于序列式容器(如vector,deque)序列式容器就是数组式容器删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存删除一个元素导致后面所有的元素会向前移动一个位置。对于关联容器(如map, set,multimap,multiset)删除当前的iterator仅仅会使当前的iterator失效只要在erase时递增当前iterator即可。这是因为map之类的容器使用了红黑树来实现插入、删除一个结点不会对其他结点造成影响。对于链表式容器(如list)删除当前的iterator仅仅会使当前的iterator失效这是因为list之类的容器使用了链表来实现插入、删除一个结点不会对其他结点造成影响。
2.16、vector用swap来缩减空间
详见vector用swap来缩减空间
容器v1只有两个元素却有着很大的容量会造成存储浪费。
所以我们 1用v1初始化一个临时对象临时对象会根据v1的元素个数进行初始化 2交换临时对象和v1 3临时对象交换后销毁v1原来的空间也销毁了v1就指向现在的空间明显占用空间减少。
3、c特性
3.1、c的重载和重写
重载overload是指函数名相同参数列表不同的函数实现方法。它们的返回值可以不同但返回值不可以作为区分不同重载函数的标志。重写overwide是指函数名相同参数列表相同只有方法体不相同的实现方法。一般用于子类继承父类时对父类方法的重写。子类的同名方法屏蔽了父类方法的现象称为隐藏。
3.2、C 内存管理热门问题
详见C内存空间静态存储区、栈、堆、文字常量区、程序代码区
在c中内存被分为五个区分别是栈、堆、全局/局部静态存储区、常量存储区 和 代码区。
栈在执行函数时函数内局部变量的存储单元都可以在栈上创建函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中效率很高但分配的内存有限。堆由new分配的内存块们的释放编译器不去管由我们的应用程序去控制一般一个new就要对应一个delete。如果程序员没有释放掉那么在程序结束后操作系统会自动回收。局/静态存储区内存在程序编译的时候就已经分配好这块内存在程序的整个运行期间都存在。它主要存放静态数据局部static变量全局static变量、全局变量和常量。常量存储区这是一块比较特殊的存储区他们里面存放的是常量字符串不允许修改。代码区存放程序的二进制代码。
3.3、面向对象的三大特性
面向对象的三大特性是封装继承和多态。
封装隐藏了类的实现细节和成员数据实现了代码模块化如类里面的private和public继承使得子类可以复用父类的成员和方法实现了代码重用多态则是“一个接口多个实现”通过父类调用子类的成员实现了接口重用如父类的指针指向子类的对象。
3.4、多态的实现
C 多态包括编译时多态和运行时多态编译时多态体现在函数重载和模板上运行时多态体现在虚函数上。虚函数在基类的函数前加上virtual关键字在派生类中重写该函数运行时将会根据对象的实际类型来调用相应的函数。如果对象类型是派生类就调用派生类的函数如果对象类型是基类就调用基类的函数。
3.4.2、函数重载的时候怎么解决同名冲突
对于C同名函数会根据参数类型和数量的不同编译成不同的函数名这样在链接阶段就可以正确的区分从而实现重载。
3.5、c虚函数相关虚函数表虚函数指针虚函数的实现原理
参考 C虚函数表剖析 c虚函数详解你肯定懂了 C虚函数表剖析
C的虚函数是实现多态的机制。它是通过虚函数表实现的虚函数表是每个类中存放虚函数地址的指针数组类的实例在调用函数时会在虚函数表中寻找函数地址进行调用如果子类覆盖了父类的函数则子类的虚函数表会指向子类实现的函数地址否则指向父类的函数地址。一个类的所有实例都共享同一张虚函数表。虚表指针放在类的开头。通过对虚表指针的解引用找到虚表。如果多重继承和多继承的话子类的虚函数表长什么样子 多重继承的情况下越是祖先的父类的虚函数更靠前多继承的情况下越是靠近子类名称的类的虚函数在虚函数表中更靠前。虚表是一个指针数组其元素是虚函数的指针每个元素对应一个虚函数的函数指针。需要指出的是普通的函数即非虚函数其调用并不需要经过虚表所以虚表的元素并不包括普通函数的函数指针。 虚表内的条目即虚函数指针的赋值发生在编译器的编译阶段也就是说在代码的编译阶段虚表就可以构造出来了。虚表是属于类的而不是属于某个具体的对象一个类只需要一个虚表即可。同一个类的所有对象都使用同一个虚表。为了指定对象的虚表对象内部包含一个虚表的指针来指向自己所使用的虚表。为了让每个包含虚表的类的对象都拥有一个虚表指针编译器在类中添加了一个指针*__vptr用来指向虚表。这样当类的对象在创建时便拥有了这个指针且这个指针的值会自动被设置为指向类的虚表。上面指出一个继承类的基类如果包含虚函数那个这个继承类也有拥有自己的虚表故这个继承类的对象也包含一个虚表指针用来指向它的虚表。对象的虚表指针用来指向自己所属类的虚表虚表中的指针会指向其继承的最近的一个类的虚函数
3.6编译器处理虚函数
如果类中有虚函数就将虚函数的地址记录在类的虚函数表中。派生类在继承基类的时候如果有重写基类的虚函数就将虚函数表中相应的函数指针设置为派生类的函数地址否则指向基类的函数地址。 为每个类的实例添加一个虚表指针vptr虚表指针指向类的虚函数表。实例在调用虚函数的时候通过这个虚函数表指针找到类中的虚函数表找到相应的函数进行调用。
3.7、基类的析构函数一般写成虚函数的原因
首先析构函数可以为虚函数当析构一个指向子类的父类指针时编译器可以根据虚函数表寻找到子类的析构函数进行调用从而正确释放子类对象的资源。如果析构函数不被声明成虚函数则编译器实施静态绑定在删除指向子类的父类指针时只会调用父类的析构函数而不调用子类析构函数这样就会造成子类对象析构不完全造成内存泄漏。
3.8、构造函数为什么一般不定义为虚函数
1因为创建一个对象时需要确定对象的类型而虚函数是在运行时确定其类型的。而在构造一个对象时由于对象还未创建成功编译器无法知道对象的实际类型是类本身还是类的派生类等等2虚函数的调用需要虚函数表指针而该指针存放在对象的内存空间中若构造函数声明为虚函数那么由于对象还未创建还没有内存空间更没有虚函数表地址用来调用虚函数即构造函数了
3.9构造函数或者析构函数中调用虚函数会怎样
在构造函数中调用虚函数由于当前对象还没有构造完成此时调用的虚函数指向的是基类的函数实现方式。在析构函数中调用虚函数此时调用的是子类的函数实现方式。
3.10、纯虚函数
纯虚函数是只有声明没有实现的虚函数是对子类的约束是接口继承 包含纯虚函数的类是抽象类它不能被实例化只有实现了这个纯虚函数的子类才能生成对象 使用场景当这个类本身产生一个实例没有意义的情况下把这个类的函数实现为纯虚函数比如动物可以派生出老虎兔子但是实例化一个动物对象就没有意义。并且可以规定派生的子类必须重写某些函数的情况下可以写成纯虚函数。
3.11、静态绑定和动态绑定
详见C中的静态绑定和动态绑定
静态绑定也就是将该对象相关的属性或函数绑定为它的静态类型也就是它在声明的类型在编译的时候就确定。在调用的时候编译器会寻找它声明的类型进行访问。动态绑定就是将该对象相关的属性或函数绑定为它的动态类型具体的属性或函数在运行期确定通常通过虚函数实现动态绑定。
3.12、深拷贝和浅拷贝
浅拷贝就是将对象的指针进行简单的复制原对象和副本指向的是相同的资源。而深拷贝是新开辟一块空间将原对象的资源复制到新的空间中并返回该空间的地址。 深拷贝可以避免重复释放和写冲突。例如使用浅拷贝的对象进行释放后对原对象的释放会导致内存泄漏或程序崩溃。
3.13、对象复用的了解零拷贝的了解 对象复用指得是设计模式对象可以采用不同的设计模式达到复用的目的最常见的就是继承和组合模式了。 零拷贝指的是在进行操作时避免CPU从一处存储拷贝到另一处存储。在Linux中我们可以减少数据在内核空间和用户空间的来回拷贝实现比如通过调用mmap()来代替read调用。 用程序调用mmap()磁盘上的数据会通过DMA被拷贝的内核缓冲区接着操作系统会把这段内核缓冲区与应用程序共享这样就不需要把内核缓冲区的内容往用户空间拷贝。应用程序再调用write(),操作系统直接将内核缓冲区的内容拷贝到socket缓冲区中这一切都发生在内核态最后socket缓冲区再把数据发到网卡去。
3.14、c的所有构造函数
默认构造函数是当类没有实现自己的构造函数时编译器默认提供的一个构造函数。重载构造函数也称为一般构造函数一个类可以有多个重载构造函数但是需要参数类型或个数不相同。可以在重载构造函数中自定义类的初始化方式。拷贝构造函数是在发生对象复制的时候调用的。
3.15、什么时候调用拷贝构造函数
详见C拷贝构造函数详解 对象以值传递的方式传入函数参数 如 void func(Dog dog){}; 对象以值传递的方式从函数返回 如 Dog func(){ Dog d; return d;} 对象需要通过另外一个对象进行初始化
3.16 结构体内存对齐方式和为什么要进行内存对齐
因为结构体的成员可以有不同的数据类型所占的大小也不一样。同时由于CPU读取数据是按块读取的内存对齐可以使得CPU一次就可以将所需的数据读进来。
对齐规则
第一个成员在与结构体变量偏移量为0的地址其他成员变量要对齐到某个数字对齐数的整数倍的地址处。对齐数编译器默认的一个对齐数 与 该成员大小的较小值。linux 中默认为4vs 中的默认值为8结构体总大小为最大对齐数的整数倍每个成员变量除了第一个成员都有一个对齐数
3.17、内存泄露的定义如何检测与避免
动态分配内存所开辟的空间在使用完毕后未手动释放导致一直占据该内存即为内存泄漏。
几种原因
类的构造函数和析构函数中new和delete没有配套在释放对象数组时没有使用delete[]使用了delete没有将基类的析构函数定义为虚函数当基类指针指向子类对象时如果基类的析构函数不是virtual那么子类的析构函数将不会被调用子类的资源没有正确释放因此造成内存泄露没有正确的清楚嵌套的对象指针
避免方法
malloc/free要配套使用智能指针将基类的析构函数设为虚函数
3.18、c智能指针
C中的智能指针有auto_ptr,shared_ptr,weak_ptr和unique_ptr。智能指针其实是将指针进行了封装可以像普通指针一样进行使用同时可以自行进行释放避免忘记释放指针指向的内存地址造成内存泄漏。
auto_ptr是较早版本的智能指针在进行指针拷贝和赋值的时候新指针直接接管旧指针的资源并且将旧指针指向空但是这种方式在需要访问旧指针的时候就会出现问题。unique_ptr是auto_ptr的一个改良版不能赋值也不能拷贝保证一个对象同一时间只有一个智能指针。shared_ptr可以使得一个对象可以有多个智能指针当这个对象所有的智能指针被销毁时就会自动进行回收。内部使用计数机制进行维护weak_ptr是为了协助shared_ptr而出现的。它不能访问对象只能观测shared_ptr的引用计数防止出现死锁。
补充
share_ptr原理 shared_ptr是可以共享所有权的指针。如果有多个shared_ptr共同管理同一个对象时只有这些shared_ptr全部与该对象脱离关系之后被管理的对象才会被释放。 shared_ptr的管理机制其实并不复杂就是对所管理的对象进行了引用计数当新增一个shared_ptr对该对象进行管理时就将该对象的引用计数加一减少一个shared_ptr对该对象进行管理时就将该对象的引用计数减一如果该对象的引用计数为0的时候说明没有任何指针对其管理才调用delete释放其所占的内存。 参考[C] Boost智能指针——boost::shared_ptr使用及原理分析
3.19、 inline关键字说一下 和宏定义有什么区别
inline是内联的意思可以定义比较小的函数。因为函数频繁调用会占用很多的栈空间进行入栈出栈操作也耗费计算资源所以可以用inline关键字修饰频繁调用的小函数。编译器会在编译阶段将代码体嵌入内联函数的调用语句块中。
内联函数在编译时展开而宏在预编译时展开在编译的时候内联函数直接被嵌入到目标代码中去而宏只是一个简单的文本替换。内联函数可以进行诸如类型安全检查、语句是否正确等编译功能宏不具有这样的功能。宏不是函数而inline是函数宏在定义时要小心处理宏参数一般用括号括起来否则容易出现二义性。而内联函数不会出现二义性。inline可以不展开宏一定要展开。因为inline指示对编译器来说只是一个建议编译器可以选择忽略该建议不对该函数进行展开。宏定义在形式上类似于一个函数但在使用它时仅仅只是做预处理器符号表中的简单替换因此它不能进行参数有效性的检测也就不能享受C编译器严格类型检查的好处另外它的返回值也不能被强制转换为可转换的合适的类型这样它的使用就存在着一系列的隐患和局限性。
3.20、模板的用法与适用场景 实现原理
用template 关键字进行声明接下来就可以进行模板函数和模板类的编写了
编译器会对函数模板进行两次编译第一次编译在声明的地方对模板代码本身进行编译这次编译只会进行一个语法检查并不会生成具体的代码。第二次编译时对代码进行参数替换后再进行编译生成具体的函数代码。
3.21、 成员初始化列表的概念为什么用成员初始化列表会快一些性能优势
成员初始化列表就是在类或者结构体的构造函数中在参数列表后以冒号开头逗号进行分隔的一系列初始化字段。
class A{int id;string name;FaceImage face;A(int inputID,stringinputName,FaceImageinputFace):id(inputID),name(inputName),face(inputFace){} // 成员初始化列表
};因为使用成员初始化列表进行初始化的话会直接使用传入参数的拷贝构造函数进行初始化省去了一次执行传入参数的默认构造函数的过程否则会调用一次传入参数的默认构造函数。所以使用成员初始化列表效率会高一些。
另外有三种情况是必须使用成员初始化列表进行初始化的
常量成员的初始化因为常量成员只能初始化不能赋值引用类型没有默认构造函数的对象必须使用成员初始化列表的方式进行初始化
3.22、C的调用惯例简单一点C函数调用的压栈过程
函数的调用过程
1 从栈空间分配存储空间
2从实参的存储空间复制值到形参栈空间
3进行运算
形参在函数未调用之前都是没有分配存储空间的在函数调用结束之后形参弹出栈空间清除形参空间。 数组作为参数的函数调用方式是地址传递形参和实参都指向相同的内存空间调用完成后形参指针被销毁但是所指向的内存空间依然存在不能也不会被销毁。
当函数有多个返回值的时候不能用普通的 return 的方式实现需要通过传回地址的形式进行即地址/指针传递。
3.23 C的四种强制转换
四种强制类型转换操作符分别为static_cast、dynamic_cast、const_cast、reinterpret_cast 1static_cast 用于各种隐式转换。具体的说就是用户各种基本数据类型之间的转换比如把int换成charfloat换成int等。以及派生类子类的指针转换成基类父类指针的转换。 特性与要点 它没有运行时类型检查所以是有安全隐患的。在派生类指针转换到基类指针时是没有任何问题的在基类指针转换到派生类指针的时候会有安全问题。static_cast不能转换constvolatile等属性 2dynamic_cast 用于动态类型转换。具体的说就是在基类指针到派生类指针或者派生类到基类指针的转换。 dynamic_cast能够提供运行时类型检查只用于含有虚函数的类。 dynamic_cast如果不能转换返回NULL。 3const_cast 用于去除const常量属性使其可以修改 也就是说原本定义为const的变量在定义后就不能进行修改的但是使用const_cast操作之后可以通过这个指针或变量进行修改; 另外还有volatile属性的转换。 4reinterpret_cast 几乎什么都可以转用在任意的指针之间的转换引用之间的转换指针和足够大的int型之间的转换整数到指针的转换等。但是不够安全。
4、调试程序
4.1、调试程序的方法
通过设置断点进行调试打印log进行调试打印中间结果进行调试
4.2、 遇到coredump要怎么调试 coredump是程序由于异常或者bug在运行时异常退出或者终止在一定的条件下生成的一个叫做core的文件这个core文件会记录程序在运行时的内存寄存器状态内存指针和函数堆栈信息等等。对这个文件进行分析可以定位到程序异常的时候对应的堆栈调用信息。 使用gdb命令对core文件进行调试 gdb [可执行文件名] [core文件名] 4.3、一个函数或者可执行文件的生成过程或者编译过程是怎样的 预处理、编译、汇编、链接 1预处理 对预处理命令进行替换等预处理操作 主要处理源代码文件中的以“#”开头的预编译指令。处理规则见下 1、删除所有的#define展开所有的宏定义。 2、处理所有的条件预编译指令如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。 3、处理“#include”预编译指令将文件内容替换到它的位置这个过程是递归进行的文件中包含其他文件。 4、删除所有的注释“//”和“/**/”。 5、保留所有的#pragma 编译器指令编译器需要用到他们如#pragma once 是为了防止有文件被重复引用。 6、添加行号和文件标识便于编译时编译器产生调试用的行号信息和编译时产生编译错误或警告是能够显示行号。 2编译代码优化和生成汇编代码 把预编译之后生成的xxx.i或xxx.ii文件进行一系列词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。 1、词法分析利用类似于“有限状态机”的算法将源代码程序输入到扫描机中将其中的字符序列分割成一系列的记号。 2、语法分析语法分析器对由扫描器产生的记号进行语法分析产生语法树。由语法分析器输出的语法树是一种以表达式为节点的树。 3、语义分析语法分析器只是完成了对表达式语法层面的分析语义分析器则对表达式是否有意义进行判断其分析的语义是静态语义——在编译期能分期的语义相对应的动态语义是在运行期才能确定的语义。 4、优化源代码级别的一个优化过程。 5、目标代码生成由代码生成器将中间代码转换成目标机器代码生成一系列的代码序列——汇编语言表示。 6、目标代码优化目标代码优化器对上述的目标机器代码进行优化寻找合适的寻址方式、使用位移来替代乘法运算、删除多余的指令等。 3汇编将汇编代码转化为机器语言 将汇编代码转变成机器可以执行的指令(机器码文件)。 汇编器的汇编过程相对于编译器来说更简单没有复杂的语法也没有语义更不需要做指令优化只是根据汇编指令和机器指令的对照表一一翻译过来汇编过程有汇编器as完成。经汇编之后产生目标文件(与可执行文件格式几乎一样)xxx.o(Windows下)、xxx.obj(Linux下)。 4链接将目标文件彼此链接起来 将不同的源文件产生的目标文件进行链接从而形成一个可以执行的程序。链接分为静态链接和动态链接 1、静态链接 函数和数据被编译进一个二进制文件。在使用静态库的情况下在编译链接可执行文件时链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。 空间浪费因为每个可执行程序中对所有需要的目标文件都要有一份副本所以如果多个程序对同一个目标文件都有依赖会出现同一个目标文件都在内存存在多个副本 更新困难每当库函数的代码修改了这个时候就需要重新进行编译链接形成可执行程序。 运行速度快但是静态链接的优点就是在可执行程序中已经具备了所有执行程序所需要的任何东西在执行的时候运行速度快。
2、动态链接
动态链接的基本思想是把程序按照模块拆分成各个相对独立部分在程序运行时才将它们链接在一起形成一个完整的程序而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。
共享库就是即使需要每个程序都依赖同一个库但是该库不会像静态链接那样在内存中存在多分副本而是这多个程序在执行时共享同一份副本
更新方便更新时只需要替换原来的目标文件而无需将所有的程序再重新链接一遍。当程序下一次运行时新版本的目标文件会被自动加载到内存并且链接起来程序就完成了升级的目标。
性能损耗因为把链接推迟到了程序运行时所以每次执行程序都需要进行链接所以性能会有一定损失。
进程的加载过程 详见进程的加载过程 进程的执行过程需要经过三大步骤编译链接和装入。编译将源代码编译成若干模块链接将编译后的模块和所需的库函数进行链接。 链接包括三种形式静态链接装入时动态链接将编译后的模块在链接时一边链接一边装入运行时动态链接在执行时才把需要的模块进行链接装入将模块装入内存运行 将进程装入内存时通常使用分页技术将内存分成固定大小的页进程分为固定大小的块加载时将进程的块装入页中并使用页表记录。减少外部碎片。 通常操作系统还会使用虚拟内存的技术将磁盘作为内存的扩充。
4.4、vs2013检查内存泄漏
详见VS 查看是否有内存泄露的方法 定位位置
在main函数中调用下面的函数
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_LEAK_CHECK_DF);
执行后将在输出窗口出未释放的指针的位置。
5、c11新特性
5.1、C11新特性
自动类型推导autoauto的自动类型推导用于从初始化表达式中推断出变量的数据类型。通过auto的自动类型推导可以大大简化我们的编程工作。nullptrnullptr是为了解决原来C中NULL的二义性问题而引进的一种新的类型因为NULL实际上代表的是0而nullptr是void*类型的lambda表达式它类似Javascript中的闭包它可以用于创建并定义匿名的函数对象以简化编程工作。Lambda的语法如下 函数对象参数mutable或exception声明-返回值类型{函数体}thread类和mutex类新的智能指针 unique_ptr和shared_ptr
二、计算机网络基础
1、 计算机体系模型
1.1、各层模型
七层模型物理层、数据链路层、网络层、传输层、会话层、应用层
tcp/ip四层模型网络接口层、网络层、传输层、应用层
五层模型物理层、数据链路层、网络层、传输层、应用层1.2、各层常用的协议
网络层IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP
传输层TCP、UDP
应用层DNS、Telnet、SMTP、HTTP1.3、展开讲讲各个协议作用
IPInternet Protocol网际协议是为计算机网络相互连接进行通信而设计的协议。
ARPAddress Resolution Protocol地址解析协议
ICMPInternet Control Message Protocol网际控制报文协议
ICMP 是 TCP/IP 模型中网络层的重要成员ping 和 tracert是两个常用网络管理命令ping 用来测试网络可达性traceroute路由追踪 用来检测发出数据包的主机到目标主机之间所经过的网关数量的工具。
IGMPInternet Group Management Protocol网际组管理协议参考Linux命令traceroute命令路由跟踪
1.4、对路由协议的了解与介绍。内部网关协议IGP包括RIPOSPF和外部网关协议EGP和BGP. IGP内部网关协议是在一个自治网络内网关主机和路由器间交换路由信息的协议。路由信息能用于网间协议IP或者其它网络协议来说明路由传送是如何进行的。IGP协议包括RIP、OSPF、IS-IS、IGRP、EIGRP。 内部网关协议分类参考内部网关协议 距离矢量路由协议 距离矢量是指以距离和方向构成的矢量来通告路由信息。距离按跳数等度量来定义方向则是下一跳的路由器或送出接口。距离矢量协议通常使用贝尔曼-福特 (Bellman-Ford) 算法来确定最佳路径。尽管贝尔曼-福特算法最终可以累积足够的信息来维护可到达网络的数据库但路由器无法通过该算法了解网际网络的确切拓扑结构。路由器仅了解从邻近路由器接收到的路由信息。 距离矢量协议适用于以下情形 1 网络结构简单、扁平不需要特殊的分层设计。 2管理员没有足够的知识来配置链路状态协议和排查故障。 3特定类型的网络拓扑结构如集中星形Hub-and-Spoke网络。 4无需关注网络最差情况下的收敛时间。 链路状态路由协议 配置了链路状态路由协议的路由器可以获取所有其它路由器的信息来创建网络的“完整视图”即拓扑结构。并在拓扑结构中选择到达所有目的网络的最佳路径链路状态路由协议是触发更新就是说有变化时就更新。 链路状态协议适用于以下情形 1网络进行了分层设计大型网络通常如此。 2管理员对于网络中采用的链路状态路由协议非常熟悉。 3网络对收敛速度的要求极高。 RIP路由信息协议(Route Information Protocol)”的简写主要传递路由信息通过每隔30秒广播一次路由表维护相邻路由器的位置关系同时根据收到的路由表信息使用动态规划的方式计算自己的路由表信息。RIP是一个距离矢量路由协议,最大跳数为16跳,16跳以及超过16跳的网络则认为目标网络不可达。 OSPF:OSPF(Open Shortest Path First开放式最短路径优先是一个内部网关协议(Interior Gateway Protocol简称IGP用于在单一自治系统autonomous system,AS内决策路由。是对链路状态路由协议的一种实现隶属内部网关协议IGP故运作于自治系统内部.OSPF详解
1.5、介绍一下ping的过程分别用到了哪些协议
详见ping 原理与ICMP协议
ping通过ICMP协议来进行工作。ICMP网络报文控制协议
首先ping命令会构建一个ICMP请求数据包然后由ICMP协议将这个数据包连同目的IP地址源IP地址一起交给IP协议然后IP协议会构建一个IP数据包并在映射表中查找目的IP对应的MAC地址将其交给数据链路层。数据链路层会构建一个数据帧附上源mac地址和目的mac地址发送出去目的主机收到数据帧后会检查数据包上的mac地址和本机mac地址是否相符如果相符就把其中的信息提取出来交给IP协议IP协议提取信息后交给ICMP协议然后构建一个ICMP应答包用相同的过程发回去。
1.6、DNS的工作过程和原理
DNS解析有两种方式递归查询和迭代查询递归查询用户先向本地域名服务器查询如果本地域名服务器的缓存没有IP地址映射记录就向根域名服务器查询根域名服务器就会向顶级域名服务器查询顶级域名服务器向权限域名服务器查询查到结果后依次返回。迭代查询用户向本地域名服务器查询如果没有缓存本地域名服务器会向根域名服务器查询根域名服务器返回顶级域名服务器的地址本地域名服务器再向顶级域名服务器查询得到权限域名服务器的地址本地域名服务器再向权限域名服务器查询得到结果。
1.7、IP寻址的过程ARP协议工作
IP寻址的工作原理包括本地网络寻址和非本地网络寻址本地网络寻址 本地网络实现IP 寻址也就是我们所说的同一网段通信过程现在我们假设有2个主机他们是属于同一个网段。主机A和主机B首先主机A通过本机的hosts表或者wins系统或dns系统先将主机B的计算机名 转换为Ip地址然后用自己的 Ip地址与子网掩码计算出自己所出的网段比较目的主机B的ip地址与自己的子网掩码发现与自己是出于相同的网段于是在自己的ARP缓存中查找是否有主机B 的mac地址如果能找到就直接做数据链路层封装并且通过网卡将封装好的以太网帧发送有物理线路上去如果arp缓存中没有主机B的的mac地址主机A将启动arp协议通过在本地网络上的arp广播来查询主机B的mac地址获得主机B的mac地址厚写入arp缓存表进行数据链路层的封装发送数据。非本地网络寻址不同的数据链路层网络必须分配不同网段的Ip地址并且由路由器将其连接起来。主机A通过本机的hosts表或wins系统或dns系统先主机B的计算机名转换为IP地址然后用自己的Ip地址与子网掩码计算出自己所处的网段比较目的目的主机B的Ip地址发现与自己处于不同的网段。于是主机A将知道应该将次数据包发送给自己的缺省网关即路由器的本地接口。主机A在自己的ARP缓存中查找是否有缺省网关的MAC地址如果能够找到就直接做数据链路层封装并通过网卡 将封装好的以太网数据帧发送到物理线路上去如果arp缓存表中没有缺省网关的Mac地址主机A将启动arp协议通过在本地网络上的arp广播来查询缺省网关的mac地址获得缺省网关的mac地址后写入arp缓存表进行数据链路层的封装发送数据。数据帧到达路由器的接受接口后首先解封装变成ip数据包对ip 包进行处理根据目的Ip地址查找路由表决定转发接口后做适应转发接口数据链路层协议帧的封装并且发送到下一跳路由器次过程继续直至到达目的的网络与目的主机。 详见ARP协议的工作机制详解
2、TCP相关
2.1、TCP/UDP/IP 报文结构
TCP头部 TCP数据部分 TCP头部结构 源端口 目的端口 序号seq 确认号ack tcp flagACK SYN FIN 偏移位 校验和 TCP选项UDP头部结构 源端口 目的端口 长度 校验和IP数据报头部结构 ID域标识 标志 片位移 源IP地址 目的IP地址 协议 校验和 总长度等等参考 IP、TCP、UDP首部详解 2.2、TCP和UDP的区别
TCP是面向连接的协议提供的是可靠传输在收发数据前需要进行三次握手协议完成连接使用ACK对手发的数据进行正确性检验。// UDP是面向无连接的协议尽最大努力交付不管对方是否收到了数据或者收到的数据是否正确。TCP提供流量控制和拥塞控制。// UDP不提供。TCP是全双工的可靠信道 // UDP则是不可靠信道TCP对系统资源的要求高于UDP所以速度要慢于UDP。TCP包没有边界会出现黏包问题实际上TCP把数据看成是一连串无结构的字节流。// UDP面向报文不会出现黏包问题。在应用方面强调数据完整性和正确性用TCP // 要求性能和速度时使用UDP。
2.3、TCP和UDP相关的协议和端口号
TCP族的协议有 HTTPHTTPSSMTP,FTP,UDP族的协议有 DNS,DHCPTCP,UDP相关协议和端口号
2.4、TCP如何保证可靠传输
校验和 发送的数据包的二进制相加然后取反目的是检验数据在传输过程中是否有变化。如果收到段的校验和有差错TCP将丢弃这个报文段和不确认接收到此报文段。确认应答 序列号 TCP给发送的每一个数据包进行编号接收方对数据包进行排序把有序数据传递给应用层。超时重传 当TCP发出一个段后会启动一个计时器等待目的端口确认接收到这个报文段。如果不能及时收到一个接收确认将重传这个报文段。流量控制 TCP连接的每一方都有固定大小的缓冲空间TCP的接收端只允许发送端发送接收端缓冲区能够接纳的数据。当接收方来不及处理发送方的数据时能够提示发送方降低发送的速率防止包丢失。 TCP用的流量控制协议是可变大小的滑动窗口协议。接收方有即时窗口滑动窗口rwnd随ACK报文发送。拥塞控制 当网络拥塞时减少数据的发送。 发送方有拥塞窗口随ACK报文发送。
2.5、使用UDP如何实现可靠传输
UDP如何实现可靠传输 因为UDP是面向无连接到的协议在传输层上无法保证可靠传输。如果想要实现可靠传输只能在应用层下手。需要实现seq/ack机制重传机制和窗口确认机制。 即要接收方收到UDP之后回复个确认包发送方有个机制收不到确认包就要重新发送每个包有递增的序号接收方发现中间丢了包就要发重传请求当网络太差时候频繁丢包防止越丢包越重传的恶性循环要有个发送窗口的限制发送窗口的大小根据网络传输情况调整调整算法要有一定自适应性。
2.6、TCP拥塞控制算法名字极其重要TCP发送方 防止过多的数据注入到网络中这样可以是网络中的路由器或者链路不致过载拥塞控制是控制发送者的流量。拥塞控制有四种算法慢启动拥塞避免快速重传、快速恢复。发送方发送方维持一个拥塞窗口 cwnd ( congestion window )的状态变量。拥塞窗口的大小取决于网络的拥塞程度并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口和接受窗口的较小值。
慢启动思路是当主机开始发送数据时先以较小的拥塞窗口进行发送然后每次翻倍。即由小到大指数级别增加拥塞窗口的大小。此外为了防止拥塞窗口cwnd增长速度过快引起网络堵塞还需设置一个慢启动阈值ssthresh状态变量当拥塞窗口大于阈值ssthresh时停止使用慢启动改用拥塞避免算法。拥塞避免 让拥塞窗口cwnd慢慢增大即每经过一个往返时间RTT就让发送方的拥塞窗口cwnd加一。快速重传 当发送端连续收到三个重复的ack时表示该数据段已经丢失需要重发。此时慢启动阈值ssth变为原来一半拥塞窗口cwnd变为ssth然后11的发每一轮rtt1。快速恢复 当超过设定时间没有收到某个报文段的ack时表示网络拥塞慢启动阈值ssth变为原来一半拥塞窗口cwnd1进入慢启动阶段。
2.7、流量控制采用滑动窗口法存在的问题死锁可能糊涂窗口综合征
**定义**流量控制即让发送方发送速率不要过快让接收方有来得及接收可以通过TCP报文中的窗口大小字段来控制发送方的发送窗口不大于接收方发回的窗口大小这样就可以实现流量控制可能存在的问题 特殊情况下接收方没有足够的缓存可以使用就会发送零窗口大小的报文此时发送方接收到这个报文后停止发送。过了一段时间接收方有了足够的缓存开始接收数据了发送了一个非零窗口的报文这个报文在传输过程中丢失那么发送方的发送窗口一直为零导致死锁发生。解决方法 为了解决这个问题TCP为每一个连接设定一个持续计时器persistence timer只要TCP的一方接收到了对方的零窗口通知就会启动这个计时器周期性的发送零窗口探测报文段对方在确认这个报文时给出现在的窗口大小。注意TCP规定即便是在零窗口状况下也必须接收以下几种报文段零窗口探测报文、确认段报文、携带紧急数据的报文段。在什么情况下会减慢拥塞窗口增长的速度 到达慢开始门限ssthresh采用拥塞避免算法出现丢包现象就进入快速恢复当连续收到三个重复确认进入快速重传。
2.8、TCP滑动窗口协议
详见TCP-IP详解滑动窗口Sliding WindowTCP的滑动窗口协议用来控制发送方和接收方的发送速率避免拥塞的发生。滑动窗口即接收方缓冲区的大小用来告知发送方对它的接收还有多大的缓存空间。在接收方的滑动窗口已知的情况下当接收方确认了连续的数据序列之后发送方的滑动窗口向后滑动发送下一个数据序列。
2.9、拥塞控制和流量控制的区别
拥塞控制是防止过多的数据注入到网络中导致网络发生拥塞流量控制是防止发送方一下子发送过多的数据到接收方导致接收方缓存放不下。两种算法都是对发送方的行为进行控制。
2.10 TCP的三次握手和四次挥手热门问题
2.10.1. 三次握手
第一次握手client给server段发送建立连接请求在这个报文中包含了SYN1seq任意值x发送后client处于SYN_SNET状态第二次握手server段接收到这个请求后进行资源分配同时返回一个ACK报文这个报文中包含了ACK1SYN1ackx1seqy此时server端处于SYN-RCVD状态第三次握手 client接收到server发送的ACK信息后可以看到ackx1知道server接收到了消息也给server回一个ACK报文报文中包含ACK1acky1seqx1。这样三次握手以后连接建立了client端进入established 状态。
2.10.2. 四次挥手
TCP断开连接一般都是一方主动一方被动的。这里假设client主动server被动
第一次挥手当客户端没有数据要继续 发送给服务器端时会发送一个FIN报文报文中包含FIN1sequ告诉server“我已经没有数据要发给你了但是你要是还想给我发数据的话你就接着发但是你得告诉我你收到我的关闭信息了”然后进入FIN-WAIT-1状态**第二次挥手服务器在在接受到以上报文后会告诉客户端“我收到你的FIN消息了但是你等我发完的”。此时给client会回复一个ACK1seqvacku1的ACK报文。服务器进入CLOSE_WAIT状态。第三次挥手当server发完所有数据时他会给client发送一个FIN报文告诉client说“我传完数据了现在要关闭连接了”报文中包含ACK1FIN1seqwacku1。然后服务器端进入LAST-ACK状态。第四次挥手 当client收到这个消息时他会给server发ACK报文但是它不相信网络怕server收不到信息它会进入TIME_WAIT状态万一server没收到ACK消息它可以可以重传而当server收到这个ACK信息后就正式关闭了tcp连接处于CLOSED状态而client等待了2MSL这样长时间后还没等到消息它知道server已经关闭连接了于是乎他自己也断开了
2.10.3. 为什么使用三次握手两次握手可不可以重点热门问题
因为只使用两次握手的话服务器端无法确认客户端是否接收到上一个ACK报文是否做好准备进入接收状态。
2.10.4. TIME_WAIT的意义为什么要等于2MSL
TIME_WAIT是指四次挥手中客户端接收了服务端的FIN报文并发送ACK报文给服务器后仍然需要等待2MSL时间的过程。虽然按道理四个报文都发送完毕我们可以直接进入CLOSE状态了但是我们必须假象网络是不可靠的有可以最后一个ACK丢失。如果客户端发送的ACK发生丢失服务器会再次发送FIN报文给客户端所以TIME_WAIT状态就是用来重发可能丢失的ACK报文。
2.11、建立TCP服务器连接的各个系统调用
建立TCP服务器连接的过程中主要通过以下的系统调用序列来获取某些函数这些系统调用主要包括有 socket() 创建套接字 bind() 绑定本机端口 connent() 建立连接 TCP三次握手在调用这个函数时进行 lisiten() 监听端口 accept() 接收连接 recv()、read()、recvfrom() 数据接收 send()、write()、sendto() 数据发送 close()、shutdown() 关闭套接字 使用close()时只有当套接字的引用计数为0的时候才会终止连接而用shutdown()就可以直接关闭连接 参考 建立TCP 服务器的系统调用 网络编程Socket之TCP之close/shutdown详解 TCP连接与断开详解socket通信
2.12、TCP三次握手时第一次的seq序号是如何产生的
第一次的序号是随机序号但也不是完全随机它是使用一个ISN算法得到的。seq C H (源IP地址目的IP地址源端口目的端口)。其中C是一个计时器每隔一段时间值就会变大H是消息摘要算法输入是一个四元组源IP地址目的IP地址源端口目的端口。
2.13、一个机器能够使用的端口号上限是多少为什么可以改变吗那如果想要用的端口超过这个限制怎么办
65536.因为TCP的报文头部中源端口号和目的端口号的长度是16位也就是可以表示2^1665536个不同端口号因此TCP可供识别的端口号最多只有65536个。但是由于0到1023是知名服务端口所以实际上还要少1024个端口号。而对于服务器来说可以开的端口号与65536无关其实是受限于Linux可以打开的文件数量并且可以通过MaxUserPort来进行配置。
2.14、服务器出现大量close_wait的连接的原因以及解决方法
close_wait状态是在TCP四次挥手的时候服务器收到FIN但是没有发送自己的FIN时出现的服务器出现大量close_wait状态的原因有两种 服务器内部业务处理占用了过多时间都没能处理完业务或者还有数据需要发送或者服务器的业务逻辑有问题没有执行close()方法服务器的父进程派生出子进程子进程继承了socket收到FIN的时候子进程处理但父进程没有处理该信号导致socket的引用不为0无法回收。 解决方法 停止应用程序修改程序里的bug
2.15、TCP的黏包和避免
黏包因为TCP为了减少额外开销采取的是流式传输所以接收端在一次接收的时候有可能一次接收多个包。而TCP粘包就是发送方的若干个数据包到达接收方的时候粘成了一个包。多个包首尾相接无法区分。导致TCP粘包的原因有三方面 发送端等待缓冲区满才进行发送造成粘包接收方来不及接收缓冲区内的数据造成粘包由于TCP协议在发送较小的数据包的时候会将几个包合成一个包后发送 避免黏包的措施 发送定长包。如果每个消息的大小都是一样的那么在接收对等方只要累计接收数据直到数据等于一个定长的数值就将它作为一个消息。包头加上包体长度。包头是定长的 4 个字节说明了包体的长度。接收对等方先接收包头长度依据包头长度来接收包体。在数据包之间设置边界如添加特殊符号 \r\n 标记。FTP 协议正是这么做的。但问题在于如果数据正文中也含有 \r\n则会误判为消息的边界。使用更加复杂的应用层协议。
2.16、TCP的封包与拆包
封包封包就是在发送数据报的时候为每个TCP数据包加上一个包头将数据报分为包头和包体两个部分。包头是一个固定长度的结构体里面包含该数据包的总长度。拆包接收方在接收到报文后提取包头中的长度信息进行截取。
详见TCP的封包与拆包
3、HTTP协议
3.1、网页的解析过程与实现方法
浏览器解析服务器响应过程:首先是html文档解析浏览器会将html文档生成解析树也就是DOM树它由dom元素以及属性节点组成。然后浏览器加载过程中如果遇到了外部的css文件或者图片资源还会另外发送请求来获取css文件和资源这个请求通常是异步的不会影响html文档的加载。如果浏览器在加载时遇到了js文件则会挂起渲染的线程等js文件加载解析完毕才恢复html的渲染线程。然后是css解析将css文件解析为央视表对象来渲染DOM树。
3.2、在浏览器中输入URL后执行的全部过程如www.baidu.com重点热门问题(%2C)-1v1qvox82yopjcc250c/)
1、首先是域名解析客户端使用DNS协议将URL解析为对应的IP地址2、然后建立TCP连接客户端与服务器端通过三次握手建立TCP连接3、接着是http连接客户端向服务器发送http连接请求http连接无需额外连接直接通过已经建立的TCP连接发送4、服务器对客户端发来的http请求进行处理并返回响应5、客户端接收到http响应时将结果渲染展示给用户。
3.3、网络层分片的原因
因为在链路层中帧的大小通常都有限制如在以太网中最大大小MTU就是1500字节。如果IP数据包加上头部后大小超过1500字节就需要分片。IP分片和完整IP报文拥有差不多的IP头16位ID域对于每个分片都是一致的这样才能在重新组装时识别出来自同一报文的分片。在IP头中16标识号唯一记录了一个IP包的ID具有同一ID的IP分片将会重新组装起来而13位片位移则记录了某IP分片相对整个IP包的位置而这两个标识中间的三位标志则标志着该分片后是否还有新的分片。这三个标志就组成了IP分片的所有信息接收方就可以利用这些信息对IP数据进行重新组织。
3.4、http协议和TCP的区别和联系
联系HTTP是建立在TCP基础上的。当浏览器需要从服务器获取网页数据时会发出一次http请求。http会通过TCP建立从客户端到服务器的连接通道当本次请求的数据传输完毕后http会立即断开TCP连接这个过程非常短暂。区别两个协议位于不同的层次。tcp协议是传输层的定义了数据传输和连接的规范。http协议是应用层的。定义了数据的内容的规范。
3.5、http/1.0和http:1.1的区别。
HTTP 协议老的标准是 HTTP/1.0 目前最通用的标准是 HTTP/1.1 。HTTP1.0 只保持短暂的连接浏览器的每次请求都需要与服务器建立一个 TCP 连接但是最新的http/1.0加入了长连接只需要在客户端给服务器发送的http报文头部加入Connection:keep-aliveHTTP 1.1 支持持久连接默认进行持久连接在一个 TCP 连接上可以传送多个 HTTP 请求和响应减少了建立和关闭连接的消耗和延迟。
3.5、http的请求方法有哪些get和post的区别
HTTP的请求方法包括GET、POST、PUT、DELETE四种基本方法。GET和POST的区别 get方法不会修改服务器上的资源它的查询是没有副作用的而post有可能会修改服务器上的资源get可以保存为书签可以用缓存来优化而post不可以get把请求附在url上而post把参数附在http包的包体中浏览器和服务器一般对get方法所提交的url长度有限制一般是1k或者2k而对post方法所传输的参数大小限制为80k到4M不等post可以传输二进制编码的信息get的参数一般只支持ASCII 参考HTTP请求方式中8种请求方法
3.6、http状态码含义 -200 - 请求成功 -301 - 资源网页等被永久转移到其它URL -404 - 请求的资源网页等不存在 -500 - 内部服务器错误 -400 - 请求无效 -403 - 禁止访问 参考HTTP状态码的含义
3.7、 http和https的区别由http升级为https需要做哪些操作
区别
http 是超文本传输协议信息是明文传输 https 则是具有安全性的 ssl 加密传输协议http 和 https 使用的是完全不同的连接方式用的端口也不一样前者是 80 后者是 443http 的连接很简单是无状态的 HTTPS 协议是由 SSLHTTP 协议构建的可进行加密传输、身份认证的网络协议比http 协议安全。https 协议需要到 ca 申请证书一般免费证书较少因而需要一定费用
参考HTTP与HTTPS的区别
3.7.2、HTTP2.0有哪些改动
多路复用允许同时通过单一的 HTTP/2 连接发起多重的请求-响应消息。
二进制分帧在应用层(HTTP/2)和传输层(TCP or UDP)之间增加一个二进制分帧层。将所有传输的信息分割为更小的消息和帧frame,并对它们采用二进制格式的编码 其中 HTTP1.x 的首部信息会被封装到 HEADER frame而相应的 Request Body 则封装到 DATA frame 里面。二进制分帧主要作用是二进制码鲁棒性高增强了通信的稳定性。
首部压缩http1.x的header由于cookie和user agent很容易膨胀而且每次都要重复发送。http2.0使用encoder来减少需要传输的header大小
服务端推送http2.0能通过push的方式将客户端需要的内容预先推送过去
3.8、https的具体实现怎么确保安全性
SSL是传输层的协议
https包括非对称加密和对称加密两个阶段在客户端与服务器建立连接的时候使用非对称加密连接建立以后使用的是对称加密
客户端使用https的URL访问web服务器要求与服务器建立SSL连接服务器接收到客户端请求后发送一份公钥给客户端私钥自己保存客户端收到公钥后将自己生成的对称加密的会话密钥进行加密并传给网站网站收到秘文后用私钥解密出会话密钥Web服务器利用会话密钥加密与客户端之间的通信这个过程称为对称加密的过程。
注意服务器第一次传给客户端的公钥其实是CA对网站信息进行加密的数字证书
3.9、对称密码和非对称密码体系
对称加密加密和解密用相同的密钥 优点计算量小算法速度快加密效率高缺点密钥容易泄漏。不同的会话需要不同的密钥管理起来很费劲常用算法DES3DESIDEACR4CR5CR6AES 非对称加密需要公钥和私钥公钥用来加密私钥用来解密 优点安全不怕泄漏缺点速度慢常用算法RSAECCDSA
3.10、数字证书的了解高频
权威CA使用私钥将网站A的信息和消息摘要签名S进行加密打包形成数字证书。公钥给客户端。网站A将自己的信息和数字证书发给客户端客户端用CA的公钥对数字证书进行解密得到签名S与手动将网站的信息进行消息摘要得到的结果S*进行对比如果签名一致就证明网站A可以信任。 4、网络编程
4.1、epoll
详见如果这篇文章说不清epoll的本质那就过来掐死我吧 3 罗培羽 三、操作系统
1、进、线程
1.1、进程与线程的区别与联系
拥有资源进程时资源分配的基本单位而线程时CPU分配和调度的基本单位。 进程在执行过程中拥有独立的内存单元而多个线程共享进程的内存。资源分配给进程同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段代码和常量数据段全局变量和静态变量扩展段堆存储。但是每个线程拥有自己的栈段栈段又叫运行时段用来存放所有局部变量和临时变量。调度线程时实现独立调度的基本单位。在同一进程中线程的切换不会引起进程切换从一个进程中的线程切换到另一个进程中的线程时会引起进程切换。系统开销由于创建或撤销进程时系统都要为之分配或回收资源如内存空间、I/O 设备等所付出的开销远大于创建或撤销线程时的开销。类似地在进行进程切换时涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置而线程切换时只需保存和设置少量寄存器内容开销很小。通信程间可以通过直接读写同一进程中的数据进行通信但是进程通信需要借助 IPC (Inter-Process Communication)。
1.2、 Linux理论上最多可以创建多少个进程一个进程可以创建多少线程和什么有关
因为进程的pid是用pid_t来表示的pid_t的最大值是32768.所以理论上最多有32768个进程。至于线程。进程最多可以创建的线程数是根据分配给调用栈的大小以及操作系统32位和64位不同共同决定的。Linux32位下是300多个。
1.3、进程之间的通信方式
进程通信的方式主要有六种管道信号量消息队列信号共享内存套接字 管道 管道是半双工的双方需要通信的时候需要建立两个管道。管道的实质是一个内核缓冲区进程以先进先出的方式从缓冲区存取数据管道一端的进程顺序地将进程数据写入缓冲区另一端的进程则顺序地读取数据该缓冲区可以看做一个循环队列读和写的位置都是自动增加的一个数据只能被读一次读出以后再缓冲区都不复存在了。当缓冲区读空或者写满时有一定的规则控制相应的读进程或写进程是否进入等待队列当空的缓冲区有新数据写入或慢的缓冲区有数据读出时就唤醒等待队列中的进程继续读写。管道是最容易实现的 匿名管道pipe和命名管道除了建立打开删除的方式不同外其余都是一样的。匿名管道只允许有亲缘关系的进程之间通信也就是父子进程之间的通信命名管道允许具有非亲缘关系的进程间通信。 管道的底层实现 信号量 信号量是一个计数器可以用来控制多个进程对共享资源的访问。信号量只有等待和发送两种操作。等待(P(sv))就是将其值减一或者挂起进程发送(V(sv))就是将其值加一或者将进程恢复运行。 信号 信号是Linux系统中用于进程之间通信或操作的一种机制信号可以在任何时候发送给某一进程而无须知道该进程的状态。如果该进程并未处于执行状态则该信号就由内核保存起来直到该进程恢复执行并传递给他为止。如果一个信号被进程设置为阻塞则该信号的传递被延迟直到其阻塞被取消时才被传递给进程。 信号是开销最小的。 共享内存 共享内存允许两个或多个进程共享一个给定的存储区这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中就像由malloc()分配的内存一样使用。一个进程写入共享内存的信息可以被其他使用这个共享内存的进程通过一个简单的内存读取读出从而实现了进程间的通信。共享内存的效率最高缺点是没有提供同步机制需要使用锁等其他机制进行同步。 消息队列 消息队列就是一个消息的链表是一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息也可以向消息队列读取消息。 消息队列与管道通信相比其优势是对每个消息指定特定的消息类型接收的时候不需要按照队列次序而是可以根据自定义条件接收特定类型的消息。 可以把消息看做一个记录具有特定的格式以及特定的优先级。对消息队列有写权限的进程可以向消息队列中按照一定的规则添加新消息对消息队列有读权限的进程可以从消息队列中读取消息。 套接字 套接口也是一种进程间通信机制与其他通信机制不同的是它可用于不同设备及其间的进程通信。
1.4、进程调度方法
详见操作系统的常见进程调度算法
先来先服务FCFS按照作业到达任务队列的顺序调度FCFS是非抢占式的易于实现效率不高性能不好有利于长作业CPU繁忙而不利于短作业I/O繁忙短作业优先SHF次从队列里选择预计时间最短的作业运行。SJF是非抢占式的优先照顾短作业具有很好的性能降低平均等待时间提高吞吐量。但是不利于长作业长作业可能一直处于等待状态出现饥饿现象完全未考虑作业的优先紧迫程度不能用于实时系统。最短剩余时间优先该算法首先按照作业的服务时间挑选最短的作业运行在该作业运行期间一旦有新作业到达系统并且该新作业的服务时间比当前运行作业的剩余服务时间短则发生抢占否则当前作业继续运行。该算法确保一旦新的短作业或短进程进入系统能够很快得到处理。时间片轮转 用于分时系统的进程调度。基本思想系统将CPU处理时间划分为若干个时间片q进程按照到达先后顺序排列。每次调度选择队首的进程执行完1个时间片q后计时器发出时钟中断请求该进程移至队尾。以后每次调度都是如此。该算法能在给定的时间内响应所有用户的而请求达到分时系统的目的。优先级调度为每个进程分配一个优先级按优先级进行调度。为了防止低优先级的进程永远等不到调度可以随着时间的推移增加等待进程的优先级。多级反馈队列时间片轮转算法对于需要运行较长时间的进程很不友好假设有一个进程需要执行 100 个时间片如果采用时间片轮转调度算法那么需要交换 100 次。因此发展出了多级反馈队列的调度方式。 多级队列是为这种需要连续执行多个时间片的进程考虑它设置了多个就绪队列每个队列时间片大小都不同例如 1, 2, 4, 8, … 这样呈指数增长。如果进程在第一个队列没执行完就会被移到下一个队列。 在这种情况下一个需要 100 个时间片才能执行完的进程只需要交换 7 次就能执行完 (1 2 4 8 16 32 64 127 100。
1.5、进程的执行过程
详见进程的加载过程
进程的执行过程需要经过三大步骤编译链接和装入。
程序如何运行编译、链接、装入
编译将源代码编译成若干模块链接将编译后的模块和所需的库函数进行链接。 链接包括三种形式静态链接装入时动态链接将编译后的模块在链接时一边链接一边装入运行时动态链接在执行时才把需要的模块进行链接装入将模块装入内存运行 将进程装入内存时通常使用分页技术将内存分成固定大小的页进程分为固定大小的块加载时将进程的块装入页中并使用页表记录。减少外部碎片。 通常操作系统还会使用虚拟内存的技术将磁盘作为内存的扩充。
1.6 多线程和多进程的选择
详见:多进程多线程的区别和选择总结
频繁修改需要频繁创建和销毁的优先使用多线程计算量需要大量计算的优先使用多线程 因为需要消耗大量CPU资源且切换频繁所以多线程好一点相关性任务间相关性比较强的用多线程相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。多分布可能要扩展到多机分布的用多进程多核分布的用多线程。
1.7、孤儿进程、僵尸进程
详见[孤儿进程与僵尸进程总结]
孤儿进程是父进程退出后它的子进程还在执行这时候这些子进程就成为孤儿进程。孤儿进程会被init进程收养并完成状态收集。僵尸进程是指子进程完成并退出后父进程没有使用wait()或者waitpid()对它们进行状态收集这些子进程的进程描述符PCB仍然会留在系统中。这些子进程就成为僵尸进程。
1.8、协程
协程和微线程是一个东西。 大多数web服务跟互联网服务本质上大部分都是 IO 密集型服务IO 密集型服务的瓶颈不在CPU处理速度而在于尽可能快速的完成高并发、多连接下的数据读写。以前有两种解决方案 多进程存在频繁调度切换问题同时还会存在每个进程资源不共享的问题需要额外引入进程间通信机制来解决。 多线程高并发场景的大量 IO 等待会导致多线程被频繁挂起和切换非常消耗系统资源同时多线程访问共享资源存在竞争问题。 此时协程出现了协程 Coroutines 是一种比线程更加轻量级的微线程。类比一个进程可以拥有多个线程一个线程也可以拥有多个协程。可以简单的把协程理解成子程序调用每个子程序都可以在一个单独的协程内执行。协程就是子程序在执行时中断并转去执行别的子程序在适当的时候又返回来执行。 这种子程序间的跳转不是函数调用也不是多线程执行所以省去了线程切换的开销效率很高并且不需要多线程间的锁机制不会发生变量写冲突 协程运行在线程之上当一个协程执行完成后可以选择主动让出让另一个协程运行在当前线程之上。协程并没有增加线程数量只是在线程的基础之上通过分时复用的方式运行多个协程而且协程的切换在用户态完成切换的代价比线程从用户态到内核态的代价小很多一般在Python、Go中会涉及到协程的知识尤其是现在高性能的脚本Go。
1.9、那协程的底层是怎么实现的怎么使用协程
协程进行中断跳转时将函数的上下文存放在其他位置中而不是存放在函数堆栈里当处理完其他事情跳转回来的时候取回上下文继续执行原来的函数。
1.10、进程的状态和转换图
三态模型 三态模型包括三种状态
执行进程分到CPU时间片可以执行就绪进程已经就绪只要分配到CPU时间片随时可以执行阻塞有IO事件或者等待其他资源 五态模型
新建态进程刚刚创建。就绪态运行态等待态出现等待事件终止态进程结束 七态模型
新建态就绪挂起态就绪态运行态等待态挂起等待态终止态 1.10、fork和vfork fork基础知识 fork:创建一个和当前进程映像一样的进程可以通过fork( )系统调用 #include sys/types.h
#include unistd.h
pid_t fork(void);成功调用fork( )会创建一个新的进程它几乎与调用fork( )的进程一模一样这两个进程都会继续运行。在子进程中成功的fork( )调用会返回0。在父进程中fork( )返回子进程的pid。如果出现错误fork( )返回一个负值。 最常见的fork( )用法是创建一个新的进程然后使用exec( )载入二进制映像替换当前进程的映像。这种情况下派生fork了新的进程而这个子进程会执行一个新的二进制可执行文件的映像。这种“派生加执行”的方式是很常见的。 vfork的基础知识 在实现写时复制之前Unix的设计者们就一直很关注在fork后立刻执行exec所造成的地址空间的浪费。BSD的开发者们在3.0的BSD系统中引入了vfork( )系统调用。 #include sys/types.h
#include unistd.h
pid_t vfork(void);除了子进程必须要立刻执行一次对exec的系统调用或者调用_exit( )退出对vfork( )的成功调用所产生的结果和fork( )是一样的。vfork( )会挂起父进程直到子进程终止或者运行了一个新的可执行文件的映像。通过这样的方式vfork( )避免了地址空间的按页复制。在这个过程中父进程和子进程共享相同的地址空间和页表项。实际上vfork( )只完成了一件事复制内部的内核数据结构。因此子进程也就不能修改地址空间中的任何内存。 补充知识点写时复制 Linux采用了写时复制的方法以减少fork时对父进程空间进程整体复制带来的开销。 写时复制是一种采取了惰性优化方法来避免复制时的系统开销。它的前提很简单如果有多个进程要读取它们自己的那部门资源的副本那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了。只要没有进程要去修改自己的“副本”就存在着这样的幻觉每个进程好像独占那个资源。从而就避免了复制带来的负担。如果一个进程要修改自己的那份资源“副本”那么就会复制那份资源并把复制的那份提供给进程。不过其中的复制对进程来说是透明的。这个进程就可以修改复制后的资源了同时其他的进程仍然共享那份没有修改过的资源。所以这就是名称的由来在写入时进行复制。 写时复制的主要好处在于如果进程从来就不需要修改资源则不需要进行复制。惰性算法的好处就在于它们尽量推迟代价高昂的操作直到必要的时刻才会去执行。 在使用虚拟内存的情况下写时复制Copy-On-Write是以页为基础进行的。所以只要进程不修改它全部的地址空间那么就不必复制整个地址空间。在fork( )调用结束后父进程和子进程都相信它们有一个自己的地址空间但实际上它们共享父进程的原始页接下来这些页又可以被其他的父进程或子进程共享。 写时复制在内核中的实现非常简单。与内核页相关的数据结构可以被标记为只读和写时复制。如果有进程试图修改一个页就会产生一个缺页中断。内核处理缺页中断的方式就是对该页进行一次透明复制。这时会清除页面的COW属性表示着它不再被共享。 现代的计算机系统结构中都在内存管理单元MMU提供了硬件级别的写时复制支持所以实现是很容易的。 在调用fork( )时写时复制是有很大优势的。因为大量的fork之后都会跟着执行exec那么复制整个父进程地址空间中的内容到子进程的地址空间完全是在浪费时间如果子进程立刻执行一个新的二进制可执行文件的映像它先前的地址空间就会被交换出去。写时复制可以对这种情况进行优化. fork和vfork的区别
fork( )的子进程拷贝父进程的数据段和代码段vfork( )的子进程与父进程共享数据段fork( )的父子进程的执行次序不确定vfork( )保证子进程先运行在调用exec或exit之前与父进程数据是共享的在它调用exec或exit之后父进程才可能被调度运行。vfork( )保证子进程先运行在它调用exec或exit之后父进程才可能被调度运行。如果在调用这两个函数之前子进程依赖于父进程的进一步动作则会导致死锁。当需要改变共享数据段中变量的值则拷贝父进程。
i、多线程相关
i.1、多线程线程同步
线程之间通信的两个基本问题是互斥和同步。
线程同步是指线程之间所具有的一种制约关系一个线程的执行依赖另一个线程的消息当它没有得到另一个线程的消息时应等待直到消息到达时才被唤醒。线程互斥是指对于共享的操作系统资源指的是广义的”资源”而不是Windows的.res文件譬如全局变量就是一种共享资源在各线程访问时的排它性。当有若干个线程都要使用某一共享资源时任何时刻最多只允许一个线程去使用其它要使用该资源的线程必须等待直到占用资源者释放该资源。
i.1.2、C11多线程之条件变量
条件变量是线程的另外一种有效同步机制。这些同步对象为线程提供了交互的场所一个线程给另外的一个或者多个线程发送消息我们指定在条件变量这个地方发生一个线程用于修改这个变量使其满足其它线程继续往下执行的条件其它线程则等待接收条件已经发生改变的信号。当条件变量同互斥锁一起使用时条件变量允许线程以一种无竞争的方式等待任意条件的发生。为何引入条件变量 前一章介绍了多线程并发访问共享数据时遇到的数据竞争问题我们通过互斥锁保护共享数据保证多线程对共享数据的访问同步有序。但如果一个线程需要等待一个互斥锁的释放该线程通常需要轮询该互斥锁是否已被释放我们也很难找到适当的轮训周期如果轮询周期太短则太浪费CPU资源如果轮询周期太长则可能互斥锁已被释放而该线程还在睡眠导致发生延误。 这就引入了条件变量来解决该问题条件变量使用“通知—唤醒”模型生产者生产出一个数据后通知消费者使用消费者在未接到通知前处于休眠状态节约CPU资源当消费者收到通知后赶紧从休眠状态被唤醒来处理数据使用了事件驱动模型在保证不误事儿的情况下尽可能减少无用功降低对资源的消耗。
i.2、多线程互斥
同步机制
事件(Event);信号量(semaphore);互斥量(mutex);临界区(Critical section)。
i.3、多线程怎么实现线程安全
线程安全就是多线程访问时采用了加锁机制当一个线程访问该类的某个数据时进行保护其他线程不能进行访问直到该线程读取完其他线程才可使用。不会出现数据不一致或者数据污染。说说线程同步方式有哪些线程安全性 线程间的同步方式包括互斥锁、信号量、条件变量、读写锁 互斥锁采用互斥对象机制只有拥有互斥对象的线程才可以访问。因为互斥对象只有一个所以可以保证公共资源不会被多个线程同时访问。 信号量计数器允许多个线程同时访问同一个资源。 条件变量通过条件变量通知操作的方式来保持多线程同步。 读写锁读写锁与互斥量类似。但互斥量要么是锁住状态要么就是不加锁状态。读写锁一次只允许一个线程写但允许一次多个线程读这样效率就比互斥锁要高。
-如何实现线程安全
保证线程安全以是否需要同步手段分类分为同步方案和无需同步方案。 1、互斥同步阻塞同步 互斥同步是最常见的一种并发正确性保障手段。同步是指在多线程并发访问共享数据时保证共享数据在同一时刻只被一个线程使用同一时刻只有一个线程在操作共享数据。而互斥是实现同步的一种手段临界区、互斥量和信号量都是主要的互斥实现方式。因此在这4个字里面互斥是因同步是果互斥是方法同步是目的。 互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题因此这种同步也成为阻塞同步。从处理问题的方式上说互斥同步属于一种悲观的并发策略总是认为只要不去做正确地同步措施例如加锁那就肯定会出现问题无论共享数据是否真的会出现竞争它都要进行加锁。 非阻塞同步 随着硬件指令集的发展出现了基于冲突检测的乐观并发策略通俗地说就是先进行操作如果没有其他线程争用共享数据那操作就成功了如果共享数据有争用产生了冲突那就再采用其他的补偿措施。最常见的补偿错误就是不断地重试直到成功为止这种乐观的并发策略的许多实现都不需要把线程挂起因此这种同步操作称为非阻塞同步。
i.4、线程池
传统多线程方案中我们采用的服务器模型则是一旦接受到请求之后即创建一个新的线程由该线程执行任务。任务执行完毕后线程退出这就是是“即时创建即时销毁”的策略。尽管与创建进程相比创建线程的时间已经大大的缩短但是如果提交给线程的任务是执行时间较短而且执行次数极其频繁那么服务器将处于不停的创建线程销毁线程的状态。线程池采用预创建的技术在应用程序启动之后将立即创建一定数量的线程(N1)放入空闲队列中。这些线程都是处于阻塞Suspended状态不消耗CPU但占用较小的内存空间。当任务到来后缓冲池选择一个空闲线程把任务传入此线程中运行。当N1个线程都在处理任务后缓冲池自动创建一定数量的新线程用于处理更多的任务。在任务执行完毕后线程也不退出而是继续保持在池中等待下一次的任务。当系统比较空闲时大部分线程都一直处于暂停状态线程池自动销毁一部分线程回收系统资源。
2、操作系统内存管理
2.1、操作系统的内存管理
操作系统内存管理总的来说操作系统内存管理包括物理内存管理和虚拟内存管理。 操作系统的内存管理包括物理内存管理和虚拟内存管理
物理内存管理包括交换与覆盖分页管理分段管理和段页式管理等虚拟内存管理包括虚拟内存的概念页面置换算法页面分配策略等
物理内存管理
包括程序装入等概念、交换技术、连续分配管理方式和非连续分配管理方式分页、分段、段页式。
虚拟内存管理
虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。
这个系列主要使用linux内存管理来具体说明。 2.1.1、物理内存管理
程序装入概念 详见程序如何运行编译、链接、装入交换技术
**交换 (swapping)**技术在多个程序并发执行时可以将暂时不能执行的程序进程送到外存中从而获得空闲内存空间来装入新程序进程或读人保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中因为这些系统大多采用分区存储管理方式。与分区式存储管理配合使用又称作“对换”或“滚进滚出” (roll-inroll-out)。
原理暂停执行内存中的进程将整个进程的地址空间保存到外存的交换区中换出swap out而将外存中由阻塞变为就绪的进程的地址空间读入到内存中并将该进程送到就绪队列换入swap in。 交换技术优点之一是增加并发运行的程序数目并给用户提供适当的响应时间与覆盖技术相比交换技术另一个显著的优点是不影响程序结构。交换技术本身也存在着不足例如对换人和换出的控制增加处理器开销程序整个地址空间都进行对换没有考虑执行过程中地址访问的统计特性。 覆盖技术 引入覆盖 (overlay)技术的目标是在较小的可用内存中运行较大的程序。这种技术常用于多道程序系统之中与分区式存储管理配合使用。 覆盖技术的原理一个程序的几个代码段或数据段按照时间先后来占用公共的内存空间。将程序必要部分(常用功能)的代码和数据常驻内存可选部分(不常用功能)平时存放在外存(覆盖文件)中在需要时才装入内存。不存在调用关系的模块不必同时装入到内存从而可以相互覆盖。 连续分配管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 单一连续存储管理 在这种管理方式中内存被分为两个区域系统区和用户区。应用程序装入到用户区可使用用户区全部空间。其特点是最简单适用于单用户、单任务的操作系统。 分区式存储管理 为了支持多道程序系统和分时系统支持多个程序并发执行引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区操作系统占用其中一个分区其余的分区由应用程序使用每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发但难以进行内存分区的共享。 分区式存储管理引人了两个新的问题 内碎片和外碎片 。 内碎片是占用分区内未被利用的空间外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。 1.固定分区 固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小分配当前空闲的、适当大小的分区。 2.动态分区(dynamic partitioning) 动态分区的特点是动态创建分区在装入程序时按其初始要求分配或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是没有内碎片。但它却引入了另一种碎片——外碎片。动态分区的分区分配就是寻找某个空闲分区其大小需大于或等于程序的要求。若是大于要求则将该分区分割成两个分区其中一个分区为要求的大小并标记为“占用”而另一个分区为余下部分并标记为“空闲”。分区分配的先后次序通常是从内存低端到高端。 常用的分区方法 (1). 最先适配法(nrst-fit)按分区在内存的先后次序从头查找找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区每次分配时查找时间开销便会增大。 (2). 下次适配法(循环首次适应算法 next fit)按分区在内存的先后次序从上次分配的分区起查找(到最后{区时再从头开始}找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好使空闲分区分布得更均匀但较大空闲分区不易保留。 (3). 最佳适配法(best-fit)按分区在内存的先后次序从头查找找到其大小与要求相差最小的空闲分区进行分配。从个别来看外碎片较小但从整体来看会形成较多外碎片优点是较大的空闲分区可以被保留。 (4). 最坏适配法(worst- fit)按分区在内存的先后次序从头查找找到最大的空闲分区进行分配。基本不留下小空闲分区不易形成外碎片。但由于较大的空闲分区不被保留当对内存需求较大的进程需要运行时其要求不易被满足。 非连续分配管理方式分页、分段、段页式 在前面的几种存储管理方法中为进程分配的空间是连续的使用的地址都是物理地址。如果允许将一个进程分散到许多不连续的空间就可以避免内存紧缩减少碎片。基于这一思想通过引入进程的逻辑地址把进程地址空间与实际存储空间分离增加存储管理的灵活性。地址空间和存储空间两个基本概念的定义如下
地址空间将源程序经过编译后得到的目标程序存在于它所限定的地址范围内这个范围称为地址空间。地址空间是逻辑地址的集合。
存储空间:指主存中一系列存储信息的物理单元的集合这些单元的编号称为物理地址存储空间是物理地址的集合。
根据分配时所采用的基本单位不同可将离散分配的管理方式分为以下三种 页式存储管理、段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。 页式存储 基本原理将程序的逻辑地址空间划分为固定大小的页(page)而物理内存划分为同样大小的页框(page frame)。程序加载时可将任意一页放人内存中任意一个页框这些页框不必连续从而实现了离散分配。在页式存储管理方式中地址结构由两部构成前一部分是页号后一部分为页内地址w位移量。 优点 1没有外碎片每个内碎片不超过页大比前面所讨论的几种管理方式的最大进步是 2一个程序不必连续存放。 3便于改变程序占用空间的大小(主要指随着程序运行动态生成的数据增多所要求的地址空间相应增长)。 缺点是要求程序全部装入内存没有足够的内存程序就不能执行。 数据结构在页式系统中进程建立时操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间如果允许进程动态地申请空间操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能必须记录系统内存中实际的页框使用情况。操作系统还要在进程切换时正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能—个页式系统中一般要采用如下的数据结构。 进程页表完成逻辑页号(本进程的地址空间)到物理页面号(实际内存空间也叫块号)的映射。每个进程有一个页表描述该进程占用的物理页面及逻辑排列顺序。 物理页面表整个系统有一个物理页面表描述物理内存空间的分配使用状况其数据结构可采用位示图和空闲页链表。 请求表整个系统有一个请求表描述系统内各个进程页表的位置和大小用于地址转换也可以结合到各进程的PCB(进程控制块)里。 页式管理地址变换 在页式系统中指令所给出的地址分为两部分逻辑页号和页内地址。 原理CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号将物理页框号与页内地址相加形成物理地址(见图4-4)。 逻辑页号页内偏移地址查进程页表得物理页号物理地址 段式存储 基本原理在段式存储管理中将程序的地址空间划分为若干个段(segment)这样每个进程有一个二维的地址空间。在前面所介绍的动态分区分配方式中系统为整个进程分配一个连续的内存空间。而在段式存储管理系统中则为每个段分配一个连续的分区而进程中的各个段可以不连续地存放在内存的不同分区中。程序加载时操作系统为所有段分配其所需内存这些段不必连续物理内存的管理采用动态分区的管理方法。 在为某个段分配物理内存时可以采用首先适配法、下次适配法、最佳适配法等方法。 优点是没有内碎片外碎片可以通过内存紧缩来消除便于实现内存共享。 缺点与页式存储管理的缺点相同进程必须全部装入内存。 数据结构为了实现段式管理操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射并跟踪物理内存的使用情况以便在装入新的段的时候合理地分配内存空间。 进程段表描述组成进程地址空间的各段可以是指向系统段表中表项的索引。每段有段基址(baseaddress)即段内地址。 系统段表系统所有占用段已经分配的段。 空闲段表内存中所有空闲段可以结合到系统段表中。 段式管理地址变换在段式 管理系统中整个进程的地址空间是二维的即其逻辑地址由段号和段内地址两部分组成。为了完成进程逻辑地址到物理地址的映射处理器会查找内存中的段表由段号得到段的首地址加上段内地址得到实际的物理地址。 页式和段式管理区别 页式和段式系统有许多相似之处。比如两者都采用离散分配方式且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别主要表现在 1)、需求是信息的物理单位分页是为了实现离散分配方式以减少内存的碎片提高内存的利用率。或者说分页仅仅是由于系统管理的需要而不是用户的需要。段是信息的逻辑单位它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。 一条指令或一个操作数可能会跨越两个页的分界处而不会跨越两个段的分界处。 2)、大小页大小固定且由系统决定把逻辑地址划分为页号和页内地址两部分是由机器硬件实现的。段的长度不固定且决定于用户所编写的程序通常由编译系统在对源程序进行编译时根据信息的性质来划分。 3)、逻辑地址表示页式系统地址空间是一维的即单一的线性地址空间程序员只需利用一个标识符即可表示一个地址。分段的作业地址空间是二维的程序员在标识一个地址时既需给出段名又需给出段内地址。 4)、比页大因而段表比页表短可以缩短查找时间提高访问速度。
2.1.2、Linux的虚拟内存管理 1、基础概念 物理内存真实存在的插在主板内存槽上的内存条的容量的大小. 内存是由若干个存储单元组成的每个存储单元有一个编号这种编号可唯一标识一个存储单元称为内存地址或物理地址。我们可以把内存看成一个从0字节一直到内存最大容量逐字节编号的存储单元数组即每个存储单元与内存地址的编号相对应。 虚拟内存地址就是每个进程可以直接寻址的地址空间不受其他进程干扰。每个指令或数据单元都在这个虚拟空间中拥有确定的地址。 虚拟内存就是进程中的目标代码数据等虚拟地址组成的虚拟空间。 虚拟内存与物理内存的区别虚拟内存就与物理内存相反是指根据系统需要从硬盘虚拟地匀出来的内存空间是一种计算机系统内存管理技术属于计算机程序而物理内存为硬件。因为有时候当你处理大的程序时候系统内存不够用此时就会把硬盘当内存来使用来交换数据做缓存区不过物理内存的处理速度是虚拟内存的30倍以上。 逻辑地址 源程序经过汇编或编译后形成目标代码每个目标代码都是以0为基址顺序进行编址的原来用符号名访问的单元用具体的数据——单元号取代。这样生成的目标程序占据一定的地址空间称为作业的逻辑地址空间简称逻辑空间。 在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。即应用程序中使用的地址。要经过寻址方式的计算或变换才得到内存中的物理地址。 线性地址线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址或者说是段中的偏移地址加上相应段的基地址就生成了一个线性地址。如果启用了分页机制那么线性地址可以再经变换以产生一个物理地址。若没有启用分页机制那么线性地址直接就是物理地址。 跟逻辑地址类似它也是一个不真实的地址如果逻辑地址是对应的硬件平台段式管理转换前地址的话那么线性地址则对应了硬件页式内存的转换前地址。 CPU将一个虚拟内存空间中的地址转换为物理地址需要进行两步首先将给定一个逻辑地址其实是段内偏移量CPU要利用其段式内存管理单元先将为个逻辑地址转换成一个线程地址再利用其页式内存管理单元转换为最终物理地址。 3、地址映射 ** 虚拟地址向线性地址的转换 ** ** 线性地址向物理地址的转换 ** Linux的每个用户进程都可以访问4 GB的线 性地址空间 而实际的物理内存可能远远少于4GB 采用分页机制。Linux仅把可执行映像的一小部分 装入物理 内存。当需要访问未装入的页面时 系统产生一个缺页中断 把需要的页读入 物理内存。 4、虚拟地址管理 每个用户进程都可以有4 GB的虚存空 间 为了更好地管 理这部分虚存空间Linux主要定义了如下三个数据结构 struct vm_area_struct struct vm_operations_struct struct vmm_struct 虚存段( vm_area_struct ) 简称 vma是某个进程的一段 连续的虚存空间 一个进程通常占用几个vma段 例如代码段 、 数据段、 堆栈段等 。 vma不仅可以代表一段内存区间 也可 以对应于一个文件、 共享内存或者对换设备。 每一个进程的所有vma由一个双向链表管理。 为了提高对vma的查询、 插入、 删除等操作的效率 Linux把系统中所 有进程的 vma组成了一棵 AVL树。 这是一棵平衡二叉树 当 vma数量特别 大时。 利用这棵 AVL树查找 v ma的效率得到 明显提 高 。 不同的 vma可能需要不同的操作处理方式 但同时考虑到统接口的统 一 性 Linux采 用vm_operations_struct结 构和面向对象的思想来定义操作方式 一个vm_operations_struct结构体是一组 函数指针 对于不同的 vma 它可能指向 不同的处理 函数例如当发生缺页错误时 共 享内存和代码 段 的 readpage所 指 向的页面读入函数可能就不同 。 内存管理中另外 一个 非 常重要的数 据 结 构是vmm_struct 结构体 进程 的 task_struct中的mm成员指向 它 当前运行进程的整个虚拟空间都 由它来管理和描述 它不仅包含该进程的映像信 息 而且它的 mma p成员项指向该进 程所有vma组成的链 表 。 它的 mmap_avl 成 员 项 指 向整个系统 的 AVL树 。 5、swap对换空间 32位Linux系统的每个进程可以有4 GB的虚拟 内存空间 而且系统中还要同时存在多个进程 但是 事实上大多数计算机都没有这么多物理内存空间 当系统中的物理内存紧缺时 就需要利用对换空间把一部分未来可能不用的页面从物理内存中移 到对换设备或对换文件中。 Linux采用两种方式保存换出的页面 一种是利用整个块设备 如硬盘的一个分区 即对换设备 另一种是利用文件系统中固定长度的文件 即对换文件。 它们统称为对换空间。 6、分页机制管理 Linux使用分页管理机制来更加有效地利用物理内存当创建一个进程时仅仅把当前进程的一小部分真正装入内存其余部分需要访问时处理器产生一个页故障由缺页中断服务程序根据缺页虚拟地址和出错码调用写拷贝函数do—wp—page、此地址所属的vma的vm—ops指向的nopage、do—swap—pageswap—in等函数将需要的页换入物理内存。 缺页中断和页面换入 页面换入主要由缺页中断服务入口函数do—page—fault来实现。当系统中产生页面故障时如果虚拟内存地址有效则产生错误的原因有如下两种 虚拟内存地址对应的物理页不在内存中。那么它必然在磁盘或对换空间中如果在磁盘上那么我们调用do—nO—page函数而do—no—page调用vma一vm—ops一nopage()函数建立页面映射从对换空间或磁盘中调入页面或者通过do—swap—page()函数调用swap—in()来换入页面。 该虚拟地址对应的物理页在内存。但是被写保护如果这种情况发生在一个共享页面上则需要“写拷贝“函数do—wp—page来换入页面do—wp—page函数首先调用一get—free—page获得一新页面然后调用copy—COW—page拷贝页面的内容当然还要调用相应的刷新函数刷新TLB和缓存等。 页交换进程和页面换出 正如我们上面所描述的系统使用kswapd守护进程来定期地换出页面。使系统中有足够的空闲物理内存页。
2.2缺页中断
定义现代操作系统通过虚拟内存技术来扩大物理内存虚拟内存每一页都映射在物理内存或磁盘上所以虚拟内存会比物理内存大程序里访问的是虚拟地址当程序访问页映射在磁盘上时就会发生缺页中断调用中断处理程序将页载入物理内存。例如32位Linux的每个用户进程都可以访问4GB的线性地址空间 而实际的物理内存可能远远少于4GB 采用分页机制 Linux仅把可执行映像的一小部分装入物理内存。当需要访问未装入的页面时 系统产生一个缺页中断把需要的页读入物理内存。缺页中断*即指的是当应用程序试图访问已映射在虚拟地址空间中但是并未被加载在物理内存中的一个分页时产生一个页不存在的中断需要操作系统将其调入物理内存后再进行访问。在这个时候被内存映射的文件映像实际上成了一个分页交换文件。缺页中断的次数 中断次数进程的物理块数页面置换次数。 缺页中断率缺页中断次数 / 总访问页数 页面置换算法 当发生缺页中断时如果操作系统内存中没有空闲页面则操作系统必须在内存选择一个页面将其移出内存以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
几种缺页中断算法FIFOLRU与LFU
1)、先进先出FIFO 优先淘汰最早进入内存的页面亦即在内存中驻留时间最久的页面。该算法实现简单只需把调入内存的页面根据先后次序链接成队列设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应因为在进程中有的页面经常被访问。2)、最近最久未使用(LRU)置换算法 选择最近最长时间未访问过的页面予以淘汰它认为过去一段时间内未访问过的页面在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段来记录页面自上次被访问以来所经历的时间淘汰页面时选择现有页面中值最大的予以淘汰。3)、LFU最不经常访问淘汰算法 思想如果数据过去被访问多次那么将来被访问的频率也更高。 实现每个数据块一个引用计数所有数据块按照引用计数排序具有相同引用计数的数据块则按照时间排序。每次淘汰队尾数据块。
2.3、实现一个LRU算法
LRU是什么 详见 LRU原理和Redis实现——一个今日头条的面试题 按照英文的直接原义就是Least Recently Used,最近最久未使用法它是按照一个非常著名的计算机操作系统基础理论得来的最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制每次从内存中找到最久未使用的数据然后置换出来从而存入新的数据它的主要衡量指标是使用的时间附加指标是使用的次数。在计算机中大量使用了这个机制它的合理性在于优先筛选热点数据所谓热点数据就是最近最多使用的数据因为利用LRU我们可以解决很多实际开发中的问题并且很符合业务场景。
2.4、内核空间和用户空间是怎样区分的
在Linux中虚拟地址空间范围为0到4G最高的1G地址0xC0000000到0xFFFFFFFF供内核使用称为内核空间低的3G空间0x00000000到0xBFFFFFFF供各个进程使用就是用户空间。内核空间中存放的是内核代码和数据而进程的用户空间中存放的是用户程序的代码和数据。
2.5、进程内存结构操作系统中程序的内存结构说明
详见 操作系统3 ————PCB和进程控制 操作系统中程序的内存结构说明 C——程序的内存结构
PCB就是进程控制块是操作系统中的一种数据结构用于表示进程状态操作系统通过PCB对进程进行管理。 PCB中包含有进程标识符处理器状态进程调度信息进程控制信息
进程地址空间内有
代码段text存放程序的二进制代码。通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定并且内存区域通常属于只读, 某些架构也允许代码段为可写即允许修改程序。在代码段中也有可能包含一些只读的常数变量例如字符串常量等。初始化的数据Data已经初始化的变量和数据。通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。未初始化的数据BSS还没有初始化的数据。bss segment通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称。BSS段属于静态内存分配。bss段未进行初始化的数据的内容并不存放在磁盘上的程序文件中。其原因是内核在程序开始运行前将它们设置为0。需要存放在程序文件中的只有正文段和初始化数据段。text段和data段在编译时已经分配了空间而BSS段并不占用可执行文件的大小它是由链接器来获取内存的。堆堆是用于存放进程运行中被动态分配的内存段它的大小并不固定可动态扩张或缩减。当进程调用malloc等函数分配内存时新分配的内存就被动态添加到堆上当利用free等函数释放内存时被释放的内存从堆中被剔除。 这里区别 堆区用于动态分配内存位于BSS和栈中间的地址区域。由程序员申请分配和释放。堆是从低地址位向高地址位增长采用链式存储结构。频繁的malloc/free造成内存空间的不连续产生碎片。当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。栈栈又称堆栈 是用户存放程序临时创建的局部变量也就是说我们函数括弧“{}”中定义的变量但不包括static声明的变量static意味着在数据段中存放变量。除此以外在函数被调用时其参数也会被压入发起调用的进程栈中并且待到调用结束后函数的返回值也会被存放回栈中。由于栈的先进先出特点所以栈特别方便用来保存/恢复调用现场。从这个意义上讲我们可以把堆栈看成一个寄存、交换临时数据的内存区。 这里区别 栈区由编译器自动释放存放函数的参数值、局部变量等。每当一个函数被调用时该函数的返回类型和一些调用的信息被存放到栈中。然后这个被调用的函数再为他的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的是一块连续的内存区域最大容量是由系统预先定义好的申请的栈空间超过这个界限时会提示溢出用户能从栈中获取的空间较小。 一个程序在内存上有BSS段Date段、text段三个组成的。在没有调入内存前可执行程序分为代码段数据区和未初始化数据三部分。
2.6、在执行malloc申请内存的时候操作系统是怎么做的/内存分配的原理说一下/malloc函数底层是怎么实现的/进程是怎么分配内存的
详见进程分配内存的两种方式–brk() 和mmap()不设计共享内存
从操作系统层面上看malloc是通过两个系统调用来实现的 brk和mmap
brk是将进程数据段(.data)的最高地址指针向高处移动这一步可以扩大进程在运行时的堆大小mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存这一步可以获得一块可以操作的堆内存。 通常分配的内存小于128k时使用brk调用来获得虚拟内存大于128k时就使用mmap来获得虚拟内存。
进程先通过这两个系统调用获取或者扩大进程的虚拟内存获得相应的虚拟地址在访问这些虚拟地址的时候通过缺页中断让内核分配相应的物理内存这样内存分配才算完成。
2.6什么是字节序怎么判断是大端还是小端有什么用
详见字节序大端法和小端法
字节序是对象在内存中存储的方式大端即为最高有效位在前面小端即为最低有效位在前面。 判断大小端的方法使用一个union数据结构
3、锁
3.1死锁
产生的必要条件
互斥条件资源同时只能由一个进程占有。不可抢占不能抢占其他进程的资源只能等对方开放占有且申请 占有且申请申请其他资源时不放开自己已占有的资源。循环等待手中拿着对方想要的资源同时向对方要资源。
产生死锁的原因主要是
因为系统资源不足。进程运行推进的顺序不合适。资源分配不当等。
死锁的恢复
重新启动是最简单、最常用的死锁消除方法但代价很大因为在此之前所有进程已经完成的计算工作都将付之东流不仅包括死锁的全部进程也包括未参与死锁的全部进程。终止进程(process termination)终止参与死锁的进程并回收它们所占资源。 (1) 一次性全部终止(2) 逐步终止(优先级代价函数)剥夺资源(resource preemption):剥夺死锁进程所占有的全部或者部分资源。 (1) 逐步剥夺一次剥夺死锁进程所占有的一个或一组资源如果死锁尚未解除再继续剥夺直至死锁解除为止。 (2) 一次剥夺一次性地剥夺死锁进程所占有的全部资源。进程回退(rollback):让参与死锁的进程回退到以前没有发生死锁的某个点处并由此点开始继续执行希望进程交叉执行时不再发生死锁。但是系统开销很大 (1) 要实现“回退”必须“记住”以前某一点处的现场而现场随着进程推进而动态变化需要花费大量时间和空间。 (2) 一个回退的进程应当“挽回”它在回退点之间所造成的影响如修改某一文件给其它进程发送消息等这些在实现时是难以做到的
3.2、死锁预防
打破占有且申请 可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足则不分配任何资源此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时才一次性地将所申请的资源全部分配给该进程。打破循环等待 实行资源有序分配策略。采用这种策略即把资源事先分类编号按号分配使进程在申请占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源才能申请大号资源就不会产生环路从而预防了死锁。安全序列安全序列是指对当前申请资源的进程排出一个序列保证按照这个序列分配资源完成进程不会发生 “酱油和醋” 的尴尬问题。 我们假设有进程 P1, P2, … Pn则安全序列要求满足Pi (1in) 需要资源 剩余资源 分配给Pj(1 j i) 资源为什么等号右边还有已经被分配出去的资源想想银行家那个问题分配出去的资源就好比第二个开发商人家能还回来钱咱得把这个考虑在内。 银行家算法。
3.4、如何实现一个mutex互斥锁
详见互斥锁mutex的简单实现
实现mutex最重要的就是实现它的lock()方法和unlock()方法。我们保存一个全局变量flagflag1表明该锁已经锁住flag0表明锁没有锁住。
实现lock()时使用一个while循环不断检测flag是否等于1如果等于1就一直循环。然后将flag设置为1unlock()方法就将flag置为0
static int flag0;void lock(){while(TestAndSet(flag,1)1);//flag1;
}
void unlock(){flag0;
}
//因为while有可能被重入所以可以用TestandSet()方法。
int TestAndSet(int *ptr, int new) {int old *ptr;*ptr new;return old;
}3.5、互斥锁和读写锁区别
互斥锁mutex用于保证在任何时刻都只能有一个线程访问该对象。当获取锁操作失败时线程会进入睡眠等待锁释放时被唤醒。读写锁rwlock分为读锁和写锁。处于读操作时可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态直到写锁释放时被唤醒。 注意写锁会阻塞其它读写锁。当有一个线程获得写锁在写时读锁也不能被其它线程获取写者优先于读者一旦有写者则后续读者必须等待唤醒时优先考虑写者。适用于读取数据的频率远远大于写数据的频率的场合。互斥锁和读写锁的区别 1读写锁区分读者和写者而互斥锁不区分 2互斥锁同一时间只允许一个线程访问该对象无论读写读写锁同一时间内只允许一个写者但是允许多个读者同时读对象。
3.6、Linux的4种锁机制
互斥锁mutex用于保证在任何时刻都只能有一个线程访问该对象。当获取锁操作失败时线程会进入睡眠等待锁释放时被唤醒读写锁rwlock分为读锁和写锁。处于读操作时可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态直到写锁释放时被唤醒。 注意写锁会阻塞其它读写锁。当有一个线程获得写锁在写时读锁也不能被其它线程获取写者优先于读者一旦有写者则后续读者必须等待唤醒时优先考虑写者。适用于读取数据的频率远远大于写数据的频率的场合。自旋锁spinlock在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时不会进入睡眠而是会在原地自旋直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长则会非常浪费CPU资源。RCU即read-copy-update在修改数据时首先需要读取数据然后生成一个副本对副本进行修改。修改完成后再将老数据update成新的数据。使用RCU时读者几乎不需要同步开销既不需要获得锁也不使用原子指令不会导致锁竞争因此就不用考虑死锁问题了。而对于写者的同步开销较大它需要复制被修改的数据还必须使用锁机制同步并行其它写者的修改操作。在有大量读操作少量写操作的情况下效率非常高。
4、高并发
4.1、服务器高并发的解决方案
应用数据和静态资源分离 将静态资源图片视频jscss等单独保存到专门的静态资源服务器中在客户端访问的时候从静态资源服务器中返回静态资源从主服务器中返回应用数据。客户端缓存 因为效率最高消耗资源最小的就是纯静态的html页面所以可以把网站上的页面尽可能用静态的来实现在页面过期或者有数据更新之后再将页面重新缓存。或者先生成静态页面然后用ajax异步请求获取动态数据。集群和分布式 集群是所有的服务器都有相同的功能请求哪台都可以主要起分流作用 分布式是将不同的业务放到不同的服务器中处理一个请求可能需要使用到多台服务器起到加快请求处理的速度。 可以使用服务器集群和分布式架构使得原本属于一个服务器的计算压力分散到多个服务器上。同时加快请求处理的速度。反向代理 ag,1)1); //flag1; } void unlock(){ flag0; } //因为while有可能被重入所以可以用TestandSet()方法。 int TestAndSet(int *ptr, int new) { int old *ptr; *ptr new; return old; } #### 3.5、互斥锁和读写锁区别- **互斥锁**mutex用于保证在任何时刻都只能有一个线程访问该对象。当获取锁操作失败时线程会进入睡眠等待锁释放时被唤醒。
- **读写锁**rwlock分为读锁和写锁。处于读操作时可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态直到写锁释放时被唤醒。 注意写锁会阻塞其它读写锁。当有一个线程获得写锁在写时读锁也不能被其它线程获取写者优先于读者一旦有写者则后续读者必须等待唤醒时优先考虑写者。适用于读取数据的频率远远大于写数据的频率的场合。
- **互斥锁和读写锁的区别**1读写锁区分读者和写者而互斥锁不区分2互斥锁同一时间只允许一个线程访问该对象无论读写读写锁同一时间内只允许一个写者但是允许多个读者同时读对象。#### 3.6、Linux的4种锁机制- 互斥锁mutex用于保证在任何时刻都只能有一个线程访问该对象。当获取锁操作失败时线程会进入睡眠等待锁释放时被唤醒
- 读写锁rwlock分为读锁和写锁。处于读操作时可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态直到写锁释放时被唤醒。 注意写锁会阻塞其它读写锁。当有一个线程获得写锁在写时读锁也不能被其它线程获取写者优先于读者一旦有写者则后续读者必须等待唤醒时优先考虑写者。适用于读取数据的频率远远大于写数据的频率的场合。
- 自旋锁spinlock在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时不会进入睡眠而是会在原地自旋直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长则会非常浪费CPU资源。
- RCU即read-copy-update在修改数据时首先需要读取数据然后生成一个副本对副本进行修改。修改完成后再将老数据update成新的数据。使用RCU时读者几乎不需要同步开销既不需要获得锁也不使用原子指令不会导致锁竞争因此就不用考虑死锁问题了。而对于写者的同步开销较大它需要复制被修改的数据还必须使用锁机制同步并行其它写者的修改操作。在有大量读操作少量写操作的情况下效率非常高。### 4、高并发#### 4.1、服务器高并发的解决方案1. 应用数据和静态资源分离将静态资源图片视频jscss等单独保存到专门的静态资源服务器中在客户端访问的时候从静态资源服务器中返回静态资源从主服务器中返回应用数据。
2. 客户端缓存因为效率最高消耗资源最小的就是纯静态的html页面所以可以把网站上的页面尽可能用静态的来实现在页面过期或者有数据更新之后再将页面重新缓存。或者先生成静态页面然后用ajax异步请求获取动态数据。
3. 集群和分布式集群是所有的服务器都有相同的功能请求哪台都可以主要起分流作用分布式是将不同的业务放到不同的服务器中处理一个请求可能需要使用到多台服务器起到加快请求处理的速度。可以使用服务器集群和分布式架构使得原本属于一个服务器的计算压力分散到多个服务器上。同时加快请求处理的速度。
4. 反向代理在访问服务器的时候服务器通过别的服务器获取资源或结果返回给客户端。
