来,我们一起复习下计算机相关基础知识吧~

大家好,我是@无所不能的魂大人,鸡年马上就要过去了,我在这里给大家拜个晚年!

冬天马上就要过去了,万物复苏,大地回春,出去找工作的日子又要到来了。

为了防止世界被破坏,为了维护世界的和平,为了年后出去面试不被喷,为了面试别人不被坑,为了和同事聊天的时候能够不留痕迹地掩饰自己的无知,特抽出时间整(fu)理(zhi)了一些计算机的相关基础知识,大概包括如下一些内容:

  • 数据编码

  • 数据结构

  • 程序算法

  • 设计模式

  • 操作系统

  • 网络通信


都是一些比较浅显的应知应会的东西,虽然我也没太看明白,复制的东西也不一定准确,反正凑合看吧,大概把常用的知识点串一串,也不至于出去面试的时候出现问啥啥不会,以及之前会的甚至熟练的知识点现在也忘光了的尴尬,之后还会陆续整理出如下相关内容,请勿期待:

  • 程序开发

  • 中间件

  • 云计算

  • 大数据

  • 信息安全

  • 人工智能

  • Devops

  • 架构设计

  • 研发管理

字符编码

编码范围00-7F,即采用7位二进制数(首位补0,共一字节)来表示(美国)常用字符,其中00-1F、FF为控制字符,其它为英文字母、数字、标点符号。

GB2312

为了满足国内在计算机中使用汉字的需要,中国国家标准总局发布了一系列的汉字字符集国家标准编码,统称为GB码,或国标码。也是ANSI编码里的一种,对ANSI编码最初始的ASCII编码进行扩充,其中最有影响的是于1980年发布的《信息交换用汉字编码字符集 基本集》,标准号为GB 2312-1980。

GBK

GBK即汉字内码扩展规范,K为扩展的汉语拼音中“扩”字的声母。

Unicode

同ASCII码类似,Unicode(统一码、万国码、单一码)是国际组织制定的可以容纳世界上所有文字和符号的字符编码方案,需要注意的是,Unicode 只是一个符号集,它只规定了符号的二进制代码,却没有规定这个二进制代码应该如何存储。

UTF-8

UTF-8是在互联网上使用最广的一种 Unicode 的实现方式,它以字节为单位对Unicode进行编码,对不同范围的字符使用不同长度的编码。如”严”的unicode是4E25(1001110 00100101),经过UTF-8编码的一坨规则一坨映射,最终得出其UTF-8编码为”11100100 10111000 10100101″, 转换成十六进制就是E4B8A5

utf8mb4

好像是mysql的坑,说mysql支持的 utf8编码最大字符长度为3字节,如果遇到4字节的宽字符就发生不可描述的事情,比如Emoji。于是为了兼容4字节utf8字符,就出现了utf8mb4,mb4就是most bytes 4的意思。

base64

主要是用来解决http环境下传输二进制数据的问题,采用基本的64个可见字符去描述任意二进制数据。它会将3个8Bit的字节转换为4个6Bit的字节(38 = 46 = 24),新的6bit字节前面补俩0,就可以对应到base64的可见字符表,当然,转换后的字符串理论上将要比原来的长1/3。同时,如果凑不够3个8Bit的字节,就用=去补,所以base64编码后面有可能会出现=号,但最多俩。

URL编码

也称作百分号编码,主要是为了解决HTTP中GET请求的传输问题,简单地说就是把每个字符的unicode码前面加%就OK了。

数据结构

线性结构

线性表
  • 线性表(Linear List)是由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。

  • 顺序表:顺序表示的线性表也称顺序表,指的是用一组地址连续的存储单元依次存储线性表的数据元素;其特点:逻辑上相邻的数据元素,其物理次序也是相邻的。

  • 链表:指用一组任意的存储单元存储线性表的数据元素;其特点:这组存储单元可连续可不连续,但每个结点除了存储对应的数据元素之外,还需存储一个直接后继的存储位置(最后一个结点也需指空即NULL)。其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。

  • 单链表:一般的普通链表。

  • 循环链表:最后一个结点的指针域并不指空,而是指向头结点,使整个链表形成一个环。

  • 双向链表:每个结点都有两个指针域,一个指向直接后继,一个指向直接前驱,克服了单链表单向性的缺点。

  • 双向循环链表:双向链表的最后结点的后继指针指向头结点的前继指针域,头结点的前继指针指向最后结点的数据域。

串就是字符串,串是一种特殊的线性表(结点由字符组成)。

限定仅在表尾进行插入或删除操作的线性表。表头端称为栈底(base),表尾端称为栈顶(top)。是一种后进先出的线性表。因此又称为”后进先出表”(Last in first out, 简称LIFO)。

队列

只允许在表的一端进行插入,在另一端删除元素;允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)(简直就像在饭堂排队打饭似的)。是一种先进先出的线性表。因此又称”先进先出表” (First in first out: 简称:FIFO)。

数组

由类型相同的数据元素构成的有序集合,其中每个元素称为数组元素。一旦建立了数组,结构中的数据元素个数和元素之间的关系就不再发生变动,故数组通常都采用顺序存储结构表示。

树形结构

二叉树

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉查找树(BST)

二叉查找树是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中,这种数据结构的好处是可以快速地对数据进行增删改查。

平衡二叉树(AVL树)

顾名思义,就是这个二叉树左右两个子树的高度相差不超过1,看起来比较匀称的那种二叉树,对于一个平衡了的二叉搜索树,整个树的高度会最低,二叉树的查找效率会比较高,当然为了保持平衡二叉树的性质,这个树插入删除的计算成本比较高。

红黑树(R-B Tree)

还是要解决维持二叉树的平衡问题,红黑树是一种弱平衡的二叉树,同时也是2-3树的一种只含2节点的表现形式,就是在节点相同的情况下,它的高度可能会略高于ALV树,但是综合效率也会略高于正常的二分查找树。实现的原理就是把节点抽象成红色和黑色两种,然后在对树进行操作的时候,通过一系列蛋疼的规则(如:若一个节点是红的,那么它的两儿子都是黑的)去限制这个树,最终让整个树比较平衡。相对于AVL而言,红黑树的优点是维护成本比较低,也就插入删除的时候为了满足红黑树的性质,所需的运算比AVL强些,当然查找略弱,所以如果有大量插入删除运算的时候,用红黑树。

B树(B-树)

B树的出现主要是为了解决磁盘的IO问题:比如我要找n,二叉树每个节点里都有两个子节点,我会依次比较然后向下搜索,每次读取节点的时候,都会产生磁盘IO,最多只能取出两个子节点的数据,太低效了,IO耗不起,于是就出现了B树,一个节点中可以有多个子节点,这样我只需要一次IO,就可以比较多次,IO就省下来了,所以B树也是一种用于查找的平衡树,但是它不是二叉树,可以拥有多于2个子节点。主要是

另:有些文章把B树等同于了AVL数,从而将B-树和B树相区分,但我查了查觉得好像不太对,B树好像就是B-树。

B+树

B树的升级版,其特征大概为:

  • 分支节点只存放索引,提升查找时IO效率

  • 所有数据都存放在叶子节点中,因此所有查询都要查找到叶子节点,查询性能稳定

  • B+树叶子节点的构成也是一个有序链表,便于范围查询或扫库操作。

B*树

在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3。

图形结构

存储
  • 邻接矩阵:用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称邻接矩阵)存储图中的边或弧的信息。

  • 邻接表:一种将数组与链表相结合的存储方法。其具体实现为:将图中顶点用一个一维数组存储,每个顶点Vi的所有邻接点用一个单链表来存储。

  • 十字链表:将邻接表和逆邻接表相结合的存储方法,它解决了邻接表(或逆邻接表)的缺陷,即求入度(或出度)时必须遍历整个图。

遍历
  • 深度优先遍历:Depth First Search,简称DFS,也成为深度优先搜索。

  • 广度优先遍历:Breadth First Search,简称BFS,又称为广度优先搜索。

最小生成树

我们要在n个城市中建立一个通信网络实现网络互通,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网,这就是最小生成树的问题:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。

  • Prim算法:从一个节点开始不断选择权值最小的边加入当前已有的树结构,最终遍历完所有的节点得到最小生成树,适合边数多的稠密图。

  • Kruskal算法:思想是按照边的权重顺序来生成最小生成树,首先将图中所有边加入优先队列,将权重最小的边出队加入最小生成树,保证加入的边不与已经加入的边形成环,直到树中有V-1到边为止,主要根据边来生成,边数少时效率比较高,适合稀疏图。

最短路径
  • 最短路径指两顶点之间经过的边上权值之和最少的路径,并且称路径上的第一个顶点为源点,最后一个顶点为终点。

  • Dijkstra算法:Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。注意该算法要求图中不存在负权边。

  • Bellman-Ford算法:Bellman-Ford算法是从DJ算法引申出来的,它可以解决带有负权边的最短路径问题。值得注意的是,DJ算法和下面的Floyd算法是基于邻接矩阵的,而Bellman-Ford算法是基于邻接表,从边的角度考量的。

  • SPFA算法:求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 很多时候,给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。有人称spfa算法是最短路的万能算法。

  • Floyd算法:Floyd算法(弗洛伊德算法)是解决任意两点间的最短路径的一种算法,可以正确处理有向(无向)图的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。

程序算法

思想(八大算法思想)

  • 枚举算法(暴力算法):将问题的所有可能答案一一列举,根据判断条件判断此答案是否合适,一般用循环实现。 经典运用:百钱买百鸡、填写运算符

  • 递推算法:1.顺推法:从已知条件出发,逐步推算出要解决问题的方法。2.逆推法:从已知结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。 经典运用:斐波那契数列(顺推法)、银行存款(逆推法)

  • 递归算法:1.递归过程一般通过函数或子过程实现;2.递归算法在函数或子过程的内部,直接或间接调用自己的算法。3.递归算法实际上是把问题转化为规模缩小了的同类问题的子问题,然后再递归调用函数或过程来表示问题的解。 经典运用:汉诺塔问题、阶乘问题

  • 分治算法:将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。 经典运用:大数相乘问题、比赛日程安排

  • 贪心算法:从问题的某一个初始解出发,逐步逼近给定的目标,以便尽快求出更好的解。 经典运用:装箱问题、找零方案

  • 试探算法(回溯法):在试探算法中,放弃当前候选解,并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。 经典运用:八皇后问题、29选7彩票组合

  • 迭代算法(辗转法):是一种不断用变量的旧值递推新值的过程,解决问题时总是重复利用一种方法。 经典运用:求平方根问题

  • 模拟算法:对真实事物或者过程的虚拟。 经典运用:猜数字游戏、掷骰子问题

查找(七大查找算法)

  • 顺序查找:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。。时间复杂度为O(n)。

  • 二分查找:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n)。

  • 插值查找:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。查找成功或者失败的时间复杂度均为O(log2(log2n))。

  • 斐波那契查找:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。最坏情况下,时间复杂度为O(log2n),且其期望复杂度也为O(log2n)。

  • 树表查找: 二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。

  • 分块查找: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,…… 时间复杂度为O(log(m)+N/m)。

  • 哈希查找:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。查找复杂度为O(1)。

排序(十大排序算法)

  • 冒泡排序(Bubble Sort):冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 选择排序(Selection Sort):选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  • 插入排序(Insertion Sort):插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  • 希尔排序(Shell Sort):希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。

  • 归并排序(Merge Sort):归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

  • 快速排序(Quick Sort):快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

  • 堆排序(Heap Sort):堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

  • 计数排序(Counting Sort):计数排序是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

  • 桶排序(Bucket Sort):假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。

  • 基数排序(Radix Sort):基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

设计模式

设计模式原则

  • 开放-封闭原则:对扩展开放,对修改封闭,可以用新的类来解决问题

  • 单一职责原则:设计目的单一的类。也就是降低程序的耦和程度

  • 李氏替换原则:用子类去替代父类

  • 依赖倒置原则:依赖于抽象,而不依赖于具体的实现;针对接口编程,不针对实现编程

  • 接口隔离原则:使用多个接口总比使用单个接口要好

  • 组合重用原则:尽量使用组合,而不是使用继承来达到重用的目的,因为继承是一种紧偶和

  • 最少知道原则:一个对象应当对其他对象有尽可能少的了解,即信息隐蔽

设计模式分类

  • 设计模式可以分为:创建型模式、结构型模式、行为型模式

  • 创建型模式作用:主要用于创建对象,为类实例化对象提供指南

  • 结构型模式作用:主要用于处理类和对象的组合,对类如何设计以形成更大的结构提供指南

  • 行为型模式作用:主要用于描述类或对象的交互以及职责的交互,对类之间交互以及分配责任提供指南

创建型模式:

  • 工厂方法模式(Factory Methord):定义一个创建对象的接口,有子类决定需要实例化哪一个类。工厂方法使得子类的实例化过程推迟。

  • 抽象工厂模式(Abstract Factory):提供一个接口,可以创建一系列对象,而不用制定它们具体的类。

  • 构建器模式(Builder):将一个复杂类的表示与其构造相分离,使得相同的构建过程能得到不同的表示。

  • 原型模式(Prototype):用原型实例指定创建对象的类型,并通过copy这个原型来创建新的对象。

  • 单例模式(Singleton):保证一个类只有一个实例,并提供一个访问它的全局访问点。

结构型模式

  • 适配器模式(Adapter):将一个类的接口转换成用户希望得到的另一种接口。

  • 桥接模式(Bridge):将类的抽象部分和实现部分分离开来,使它们可以独立地变化。也就是把一棵树拆成2棵树,再把两棵树连接起来。也就是继承与拆分。

  • 组合模式(Composite):将对象组合成树形结构以表示“整体-部分”的层次结构,使得用户对单个对象和组合对象的使用具有一致性。

  • 装饰模式(Decorator):动态给一个对象添加一些额外的职责。

  • 外观模式(Facade):定义一个高层接口,为子系统中的一组接口提供一个一致的外观。

  • 享元模式(Flyweight):提供支持大量细粒度对象共享的有效方法。

  • 代理模式(Proxy):为其他对象提供一种代理以控制这个对象的访问。

行为型模式

  • 职责链模式:通过给多个对象处理请求的机会,减少请求的发送者与接收者之间的耦合。将接收对象链接起来,在链中传递请求,直到有一个对象处理这个请求。

  • 命令模式(Command):将一个请求封装为一个对象,从而可用不同的请求对客户进行参数化,将请求排队或者记录请求日志,支持可4撤销操作。

  • 解释器模式(Interpreter):给定一种语言,定义它的文法表示,并定义一个解释器,该解释器用来根据文法表示来解释语言中的句子。

  • 迭代器模式(Iterator):提供一种方法来顺序访问一个聚合对象中的各个元素,而不需要暴露该对象的内部表示。

  • 中介者模式(Mediator):用一个中介对象来封装一系列的交互。它使各对象不需要显式地相互调用,从而达到低耦合,还可以独立地改变对象之间的交互。

  • 备忘录模式(Memento):保存一个对象的某个状态,以便在适当的时候恢复对象。

  • 观察者模式(Observer):定义对象之间的一种一对多的依赖关系,当一个对象的状态发生变化时,所有依赖于它的对象都得到通知并自动更新。

  • 状态模式(State):允许一个对象在其内部状态改变时改变他的行为。

  • 策略模式(Syategy):定义一系列算法,把它们一个个封装起来,并且使它们之间可相互替换,从而让算法可以独立于使用它的用户而变化。

  • 模版方法模式(Templatemethod):定义一个操作中的算法骨架,而将一些步骤延迟到子类中。

  • 访问者模式(Visitor):一种分离对象数据结构与行为的方法。通过这种分离,可达到一个被访问者动态添加新的操作而无需做其他的修改的效果。

操作系统

进程与线程

进程是资源拥有者。在创建、切换和撤销的操作需要较大的时空开销,限制了并发程度的进一步提高。引入线程将进程作为资源分配单位和资源调度单位这两个属性分开处理。进程任作为资源分配的基本单位;把调度执行和切换的任务交给线程。

区别
  • 进程:进程是资源(CPU、内存等)分配的基本单位,它是程序执行时的一个实例。程序运行时系统就会创建一个进程,并为它分配资源,然后把该进程放入进程就绪队列,进程调度器选中它的时候就会为它分配CPU时间,程序开始真正运行。

  • 线程:是CPU调度和分派的基本单位,一个进程可以由很多个线程组成,线程间共享进程的所有资源,每个线程有自己的堆栈和局部变量。线程由CPU独立调度执行,在多CPU环境下就允许多个线程同时运行。同样多线程也可以实现并发操作,每个请求分配一个线程来处理。

进程通信
  • 管道( pipe ):管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。有名管道(named pipe)也是半双工的通信方式,但是它允许无亲缘关系进程间的通信。

  • 信号量( semophore ):信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其他进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。

  • 消息队列( message queue ):消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

  • 信号( signal ):信号是比较复杂的通信方式,用于通知接受进程有某种事件发生,除了用于进程间通信外,进程还可以发送信号给进程本身;linux除了支持Unix早期信号语义函数sigal外,还支持语义符合Posix.1标准的信号函数sigaction(实际上,该函数是基于BSD的,BSD为了实现可靠信号机制,又能够统一对外接口,用sigaction函数重新实现了signal函数)。

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

  • 套接字( socket ):套解口也是一种进程间通信机制,与其他通信机制不同的是,它可用于不同及其间的进程通信。

线程同步
  • 互斥锁:提供对临界资源的保护,当多线程试图访问临界资源时,都必须通过获取锁的方式来访问临界资源。(临界资源:是被多线程共享的资源)

  • 条件变量:提供线程之间的一种通知机制,当某一条件满足时,线程A可以通知阻塞在条件变量上的线程B,B所期望的条件已经满足,可以解除在条件变量上的阻塞操作,继续做其他事情。

  • 信号量:提供对临界资源的安全分配。如果存在多份临界资源,在多个线程争抢临界资源的情况下,向线程提供安全分配临界资源的方法。如果临界资源的数量为1,将退化为锁。

  • 令牌:一种高级的线程同步的方法。它既提供锁的安全访问临界资源的功能,又利用了条件变量使得线程争夺临界资源时是有序的。

线程安全
  • 线程安全是指多线程访问同一代码,不会产生不确定的结果(即不会存在二义性)。编写线程安全的代码时依靠线程同步。

  • 线程安全问题都是由全局变量及静态变量引起的。 若每个线程中对全局变量、静态变量只有读操作而无写操作,一般来说,这个全局变量时线程安全的;若有多个线程同时执行写操作,一般都需要考虑线程同步,否则就可能影响线程安全。

僵尸进程与孤儿进程
  • 孤儿进程:一个父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养,并由init进程对它们完成状态收集工作。

  • 僵尸进程:一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

死锁*

IO模型

基本概念
  • 同步与异步:描述的是用户线程与内核的交互方式,同步指用户线程发起IO请求后需要等待或者轮询内核IO操作完成后才能继续执行;而异步是指用户线程发起IO请求后仍然继续执行,当内核IO操作完成后会通知用户线程,或者调用用户线程注册的回调函数。

  • 阻塞与非阻塞:描述是用户线程调用内核IO操作的方式,阻塞是指IO操作需要彻底完成后才返回到用户空间;而非阻塞是指IO操作被调用后立即返回给用户一个状态值,无需等到IO操作彻底完成。

5种IO模型
  • 阻塞I/O模型:进程会一直阻塞,直到数据拷贝完成

  • 非阻塞IO模型:非阻塞IO通过进程反复调用IO函数(多次系统调用,并马上返回);在数据拷贝的过程中,进程是阻塞的;

  • IO复用模型:主要是select和epoll;对一个IO端口,两次调用,两次返回,比阻塞IO并没有什么优越性;关键是能实现同时对多个IO端口进行监听; I/O复用模型会用到select、poll、epoll函数,这几个函数也会使进程阻塞,但是和阻塞I/O所不同的的,这两个函数可以同时阻塞多个I/O操作。而且可以同时对多个读操作,多个写操作的I/O函数进行检测,直到有数据可读或可写时,才真正调用I/O操作函数。

  • 信号驱动IO:两次调用,两次返回; 首先我们允许套接口进行信号驱动I/O,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个SIGIO信号,可以在信号处理函数中调用I/O操作函数处理数据。

  • 异步IO模型:数据拷贝的时候进程无需阻塞。 当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者的输入输出操作。

IO复用
select
  • 其参数是输入输出型参数,每次调用都重新将添加关心的描述符集。

  • 监视文件描述符有上限,默认只有1024。

  • 每次调用都会在用户空间和内核空间之间拷贝 fd 集。

  • 每次调用内核和开发者都要变量所有fd,复杂度 O(N),当数量很多时,开销比较大。

  • 性能高于多线程或多进程版本。

poll
  • poll 解决的 select 的文件描述符上限问题,上限是最大可以打开文件的数目,这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左右,具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。。

  • 同 select一样, 不论文件描述符是否就绪,都会将大量文件描述符的数组被整体复制于用户态和内核的地址空间之间。

  • 将关心事件与发生事件在 不同的 event中,避免了像 select一样每次都要重新赋值。

  • 每次调用内核和开发者都要遍历所有fd,复杂度 O(N),当数量很多时,开销比较大。

  • 可以说poll是加强版的 select,其使用模型也十分相似。

epoll
  • 上限和 poll 一样,不再受限于文件描述符的限制。

  • 不必在内核和用户空间多次拷贝fd 集合,只需要在使用前添加到集合即可,在不关心时删除即可。

  • 内核操作描述符从线性的 O(N)O(N) 提高到 O(log2n)O(log2n) 级别,比起 select 和 poll,效率更高。

  • 阻塞等待时,内核只需要检测就绪队列是否有事件就绪,当返回时候,如果有事件就绪,则用户可以根据返回值知道就绪事件的范围,不需像 另外两者,会变量所有描述符。

  • epoll 可以说是poll 的加强版,其缺陷是目前不支持跨平台只在 Linux支持,且当有大量活跃的描述符时效率不及另外两者。

网络通信

分层

  • OSI分层(7层):物理层、数据链路层、网络层、运输层、会话层、表示层、应用层

  • TCP/IP分层(4层):网络接口层、网络层、运输层、应用层

  • 五层协议(5层):物理层、数据链路层、网络层、运输层、应用层

协议

  • ARP/RARP协议:ARP(Address Resolution Protocol),是根据IP地址获取物理地址的一个TCP/IP协议。RARP,功能和ARP协议相对,其将局域网中某个主机的物理地址转换为IP地址。

  • ICMP协议:确认IP包是否成功送达目标地址,通知在发送过程中IP包被废弃的具体原因等等。

  • DHCP协议:动态主机配置协议常用于给主机动态地分配IP地址,它提供了即插即用联网的机制,这种机制允许一台计算机加入新的网络和获取IP地址而不用手工参与。DHCP是应用层协议,基于UDP的。

  • NAT协议:NAT是用于在本地网络中使用私有地址,在连接互联网时转而使用全局IP地址的技术。除转换IP地址外,还出现了可以转换TCP、UDP端口号的NAPT(窗口多路复用)技术,由此可以实现一个全局IP地址与多个主机的通信。

  • BGP协议:边界网关协议(BGP)是运行于 TCP 上的一种自治系统(AS)的路由协议,是唯一能够妥善处理不相关路由域间的多路连接的协议。

TCP

11种状态
  • LISTEN:等待从任何远端TCP 和端口的连接请求。

  • SYN_SENT:发送完一个连接请求后等待一个匹配的连接请求。

  • SYN_RECEIVED:发送连接请求并且接收到匹配的连接请求以后等待连接请求确认。

  • ESTABLISHED:表示一个打开的连接,接收到的数据可以被投递给用户。连接的数据传输阶段的正常状态。

  • FIN_WAIT_1:等待远端TCP 的连接终止请求,或者等待之前发送的连接终止请求的确认。

  • FIN_WAIT_2:等待远端TCP 的连接终止请求。

  • CLOSE_WAIT:等待本地用户的连接终止请求。

  • CLOSING:等待远端TCP 的连接终止请求确认。

  • LAST_ACK: 等待先前发送给远端TCP 的连接终止请求的确认(包括它字节的连接终止请求的确认)

  • TIME_WAIT:等待足够的时间过去以确保远端TCP 接收到它的连接终止请求的确认。

  • CLOSED:不在连接状态(这是为方便描述假想的状态,实际不存在)

TIME_WAIT 两个存在的理由:1.可靠的实现tcp全双工连接的终止;2.允许老的重复分节在网络中消逝。

三次握手

置位概念: 根据TCP的包头字段, 存在3个重要的表示。ACK: 表示验证字段;SYN: 位数置1, 表示建立TCP连接;FIN:位数置1,表示断开TCP连接。

  • 第一次握手:建立连接时,客户端发送syn包(syn=j)到服务器,并进入SYN_SENT状态,等待服务器确认;SYN:同步序列编号(Synchronize Sequence Numbers)。

  • 第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个SYN包(syn=k),即SYN+ACK包,此时服务器进入SYN_RECV状态;

  • 第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1),此包发送完毕,客户端和服务器进入ESTABLISHED(TCP连接成功)状态,完成三次握手。

四次挥手
  • 第一次挥手:客户端向服务端发送FIN包,表示客户端请求断开连接,此时客户端由ESTABLISHED状态进入FIN_WAIT_1状态。

  • 第二次挥手:服务端收到客户端的FIN包,回复ACK包,此时服务端也由ESTABLISHED状态进入CLOSED_WAIT状态。

  • 第二次挥手和第三次挥手之间:因为双方已经都知道了对方要离开的心意,所以要交代完全部的工作,也就是说,服务器要将客户端的数据全部传输到客户端以后,才会进行下一次挥手,客户端收到服务器端的ACK回复以后,与服务器进行最后的数据传输,而这段数据传输的时间,在客户端处于FIN_WAIT_2状态。

  • 第三次挥手:服务器端传输完数据以后,发送FIN+ACK包,同时自己进入LAST_ACK状态。

  • 第四次挥手:客户端收到服务器的FIN+ACK包,回复ACK包确定连接的结束。而后自己进入一个TIME_WAIT的等待时间,等待结束后客户端关闭连接,而服务器端收到客户端回复的ACK包以后就会关闭这个连接。

HTTPx

  • HTTP1.0:浏览器与服务器只保持短暂的连接,浏览器的每次请求都需要与服务器建立一个 TCP 连接(TCP 连接的新建成本很高,因为需要客户端和服务器三次握手),服务器完成请求处理后立即断开 TCP 连接,服务器不跟踪每个客户也不记录过去的请求;只能通过添加头信息——非标准的 Connection 字段 Connection: keep-alive解决。

  • HTTP1.1:新增PUT/DELETE/OPTIONS/TRACE/CONNECT请求方式,同时增加了持久连接与管道机制,但是同一个 TCP 连接里面,所有的数据通信是按次序进行的。服务器只有处理完一个请求,才会接着处理下一个请求。如果前面的处理特别慢,后面就会有许多请求排队等着。这将导致“队头堵塞”

  • HTTP2.0:采用二进制格式而非文本格式;完全多路复用,而非有序并阻塞的、只需一个连接即可实现并行;使用报头压缩,降低开销;允许服务器主动向客户端发送资源。

  • HTTPS:HTTP 协议通常承载于 TCP 协议之上,在 HTTP 和 TCP 之间添加一个安全协议层(SSL 或 TSL),这个时候,就成了我们常说的 HTTPS。

设备

  • 网卡:就是网卡,俗称网络适配器。

  • 中继器:中继器是在OSI模型的第一层–物理层面上的连接网络的设备。由电缆传过来的电信号或光信号经由中继器的波形调整和放大再传给另一个电缆。

  • 网桥/2层交换机:网桥是在OSI模型的第二层–数据链路层上连接两个网络的设备。它能够识别数据链路层中的数据帧,并将这些数据帧临时存储域内存,在重新生成信号作为一个全新的帧转发给相连的另一个网段。

  • 路由器/3层交换机:路由器是在OSI模型的第3层–网络层面上连接两个网络、并对分组报文进行转发的设备。网桥是根据物理地址进行处理,而路由器/3层交换机则是根据IP地址进行处理。

  • 4~7层交换机:4-7层交换机负责处理OSI模型中从传输层到应用层的数据,如果用TCP/IP分层模型来表述,4-7层就是TCP等协议的传输层及其上面的应用层为基础,分析收发数据,并对其进行特定的处理。

  • 网关:网关(Gateway)又称网间连接器、协议转换器。网关在网络层以上实现网络互连,是最复杂的网络互连设备,仅用于两个高层协议不同的网络互连。