Work For Tencent
一、进程、线程、(协程)、多进程、多线程、进程通信、线程通信
1、进程与线程,协程的区别联系
- (00)有了进程,为什么还要有线程?
- 原因:进程在早期的多任务操作系统中是基本的执行单元。每次进程切换,都要先保存进程资源然后再恢复,这称为上下文切换。但是进程频繁切换将引起额外开销,从而严重影响系统的性能。为了减少进程切换的开销,人们把两个任务放到一个进程中,每个任务用一个更小粒度的执行单元来实现并发执行,这就是线程。
- 线程与进程对比:(1)进程间的信息难以共享。由于除去只读代码段外,父子进程并未共享内存,因此必须采用一些进程间通信方式,在进程间进行信息交换。但多个线程共享进程的内存,如代码段、数据段、扩展段,线程间进行信息交换十分方便。
(0)基础概念:
进程:是资源调度的基本单位,(有独立的地址空间,线程无)运行一个可执行程序会创建一个或多个进程,进程就是运行起来的可执行程序
线程:是程序执行的基本单位,是轻量级的进程。每个进程中都有唯一的主线程,且只能有一个,主线程和进程是相互依存的关系,主线程结束进程也会结束。
协程:是用户态的轻量级线程,线程内部调度的基本单位(1)定义:
进程:资源分配和拥有的基本单位
线程:程序执行的基本单位
协程:用户态的轻量级线程,线程内部调度的基本单位(2)切换情况:
进程:进程CPU环境(栈,寄存器、页表和文件句柄等)的保存以及新调度的进程CPU环境的设置(切换者:操作系统)
线程:保存和设置程序计数器,少量计数器和栈的内容(切换者:操作系统)
协程:先将寄存器上下文和栈保存,等切换回来的时候再进行恢复;(切换者:用户)(3)拥有资源:
进程:CPU资源、内存资源、文件资源和句柄等
线程:程序计数器、寄存器、栈和状态字
协程:拥有自己的寄存器上下文和栈(4)系统开销:
进程:切换虚拟地址空间,切换内核栈和硬件上下文,CPU高速缓存失效、页表切换,开销很大(调用栈:内核栈)
线程:切换时只需要保存设置少量寄存器内容,因此开销很小(调用栈:内核栈)
协程:直接操作栈则基本没有内核切换的开销,可以不加锁的访问全局变量,所以上下文的切换非常快(调用栈:用户栈)(5)并发性:
进程:不同进程之间切换实现并发,各自占有CPU实现并行
线程:一个进程内部的多个线程并发执行
协程:同一时间只能执行一个协程,而其他协程处于休眠状态,适合对任务进行分时处理(6)通信方式:
进程:进程间通信需要借助操作系统
线程:线程间可以直接读写进程数据段(如全局变量)来进行通信
协程:共享内存、消息队列
2、进程线程模型
多线程:用户态的多线程模型,同一个进程内部有多个线程,所有的线程共享同一个进程的内存空间,进程中定义的全局变量会被所有的线程共享,比如有全局变量int i = 10,这一进程中所有并发运行的线程都可以读取和修改这个i的值,而多个线程被CPU调度的顺序又是不可控的,所以对临界资源的访问尤其需要注意安全。
- 【同一进程间的线程共享的资源有】
a. 堆 由于堆是在进程空间中开辟出来的,所以它是理所当然地被共享的;因此new出来的都是共享的(16位平台上分全局堆和局部堆,局部堆是独享的)
b. 全局变量 它是与具体某一函数无关的,所以也与特定线程无关;因此也是共享的
c. 静态变量 虽然对于局部变量来说,它在代码中是“放”在某一函数中的,但是其存放位置和全局变量一样,存于堆中开辟的.bss和.data段,是共享的
d. 文件等公用资源 这个是共享的,使用这些公共资源的线程必须同步。Win32 提供了几种同步资源的方式,包括信号、临界区、事件和互斥体。
- 【同一进程间的线程共享的资源有】
线程共享的环境包括:进程代码段、进程的公有数据(利用这些共享的数据,线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
- 【独享的资源有】
a. 栈 栈是独享的
b. 寄存器
- 【独享的资源有】
【个性】进程拥有这许多共性的同时,还拥有自己的个性,才能实现并发性
1.线程ID:每个线程都有自己的线程ID,这个ID在本进程中是唯一的。进程用此来标识线程。2.寄存器组的值:由于线程间是并发运行的,每个线程有自己不同的运行线索,当从一个线程切换到另一个线程上 时,必须将原有的线程的寄存器集合的状态保存,以便将来该线程在被重新切换到时能得以恢复。3.线程的堆栈:堆栈是保证线程独立运行所必须的。线程函数可以调用函数,而被调用函数中又是可以层层嵌套的,所以线程必须拥有自己的函数堆栈, 使得函数调用可以正常执行,不受其他线程的影响。
- 多进程:每一个进程是资源分配的基本单位。
进程结进程结构由以下几个部分组成:代码段、堆栈段、数据段。代码段是静态的二进制代码,多个程序可以共享。
实际上在父进程创建子进程之后,父、子进程除了pid外,几乎所有的部分几乎一样。
3、进程通信方式:
进程通信的方式主要有六种:管道,信号量,消息队列,信号,共享内存,套接字
管道:管道的实质是一个内核缓冲区,进程以先进先出的方式从缓冲区存取数据:管道一端的进程顺序地将进程数据写入缓冲区,另一端的进程则顺序地读取数据,该缓冲区可以看做一个循环队列,读和写的位置都是自动增加的,一个数据只能被读一次,读出以后再缓冲区都不复存在了。
匿名管道只允许有亲缘关系的进程之间通信,也就是父子进程之间的通信,命名管道允许具有非亲缘关系的进程间通信。信号量:信号量是一个计数器,可以用来控制多个进程对共享资源的访问。
信号:信号是Linux系统中用于进程之间通信或操作的一种机制,信号可以在任何时候发送给某一进程,而无须知道该进程的状态。如果该进程并未处于执行状态,则该信号就由内核保存起来,直到该进程恢复执行并传递给他为止。
共享内存:共享内存允许两个或多个进程共享一个给定的存储区,这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中。一个进程写入共享内存的信息,可以被其他使用这个共享内存的进程,通过一个简单的内存读取读出,从而实现了进程间的通信。
消息队列:消息队列就是一个消息的链表,是一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息,也可以向消息队列读取消息。
消息队列与管道通信相比,其优势是对每个消息指定特定的消息类型,接收的时候不需要按照队列次序,而是可以根据自定义条件接收特定类型的消息。socket:套接口也是一种进程间通信机制,与其他通信机制不同的是,它可用于不同设备及其间的进程通信
进程同步方式:
- (1)临界区
- (2)同步和互斥
- (3)信号量
- (4)管程
4、线程通信、同步方式
- 线程间的通信方式包括互斥量、信号量、条件变量、读写锁:
- 信号量:计数器,允许多个线程同时访问同一个资源。
- 条件变量:通过条件变量通知操作的方式来保持多线程同步。
- 锁机制:互斥锁、读写锁和自旋锁。读写锁:读写锁与互斥量类似。但互斥量要么是锁住状态,要么就是不加锁状态。读写锁一次只允许一个线程写,但允许一次多个线程读,这样效率就比互斥锁要高。
5、几种典型的锁
读写锁
多个读者可以同时进行读
写者必须互斥(只允许一个写者写,也不能读者写者同时进行)
写者优先于读者(一旦有写者,则后续读者必须等待,唤醒时优先考虑写者)互斥锁
一次只能一个线程拥有互斥锁,其他线程只有等待。
互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒,而操作系统负责线程调度,为了实现锁的状态发生改变时唤醒阻塞的线程或者进程,需要把锁交给操作系统管理,所以互斥锁在加锁操作时涉及上下文的切换。互斥锁实际的效率还是可以让人接受的,加锁的时间大概100ns左右,而实际上互斥锁的一种可能的实现是先自旋一段时间,当自旋的时间超过阀值之后再将线程投入睡眠中,因此在并发运算中使用互斥锁(每次占用锁的时间很短)的效果可能不亚于使用自旋锁。条件变量
互斥锁一个明显的缺点是他只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足,他常和互斥锁一起使用,以免出现竞态条件。当条件不满足时,线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量,他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制,条件变量则是同步机制。自旋锁
如果进线程无法取得锁,进线程不会立刻放弃CPU时间片,而是一直循环尝试获取锁,直到获取为止。如果别的线程长时期占有锁,那么自旋就是在浪费CPU做无用功,但是自旋锁一般应用于加锁时间很短的场景,这个时候效率比较高。
6、进程的创建
一般来说,当一个进程创建子进程时,该子进程需要一定的资源(CPU 时间、内存、文件、I/O 设备等)来完成任务。子进程可以从操作系统那里直接获得资源,也可以只从父进程那里获得资源子集。父进程可能要在子进程之间分配资源或共享资源(如内存或文件)。限制子进程只能使用父进程的资源,可以防止创建过多进程,导致系统超载。
当进程创建新进程时,可有两种执行可能:
父进程与子进程并发执行。
父进程等待,直到某个或全部子进程执行完。新进程的地址空间也有两种可能:
子进程是父进程的复制品(它具有与父进程同样的程序和数据)。
子进程加载另一个新程序。fork()函数功能——创建新进程
1、父子进程有独立的数据段、堆、栈,共享代码段
Linux中每个进程都有4G的虚拟地址空间(独立的3G用户空间和共享的1G内核空间),fork()创建的子进程也不例外。子进程资源的由来:
1、1G内核空间既然是所有进程共享,因此fork()创建的子进程自然也将拥有;
2、3G的用户空间是从父进程进程而来。
fork()创建子进程时继承了父进程的数据段、代码段、栈段、堆,注意从父进程继承来的是虚拟地址空间,同时也复制了页表(没有复制物理块)。因此,此时父子进程拥有相同的虚拟地址,映射的物理内存也是一致的(独立的虚拟地址空间,共享父进程的物理内存)。
由于父进程和子进程共享物理页面,内核将其标记为“只读”(类似mmap)的private的方式),父子双方均无法对其修改。无论父进程和子进程何时试图对一个共享的页面执行写操作,就产生一个错误,这时内核就把这个页复制到一个新的页面给这个进程,并标记为可写,同时修改页表,把原来的只读页面标记为“可写”,留给另外一个进程使用——写时复制技术。
注意:内核在为子进程分配物理内存时,并没有将代码段对应的数据另外复制一份给子进程,最终父子进程代码段映射的是同一块物理内存(代码段在单个进程内部本来就是只读的)。
每个进程的虚拟地址空间都可以是0到4G,只不过其中只有一部分有权访问,每个进程可以有不同的映射。两次运行同一个程序就是使用的相同的虚拟地址,但是映射到的物理地却是不一样的。每个进程都有自己的虚拟地址空间,不同进程的相同的虚拟地址显然可以对应不同的物理地址。因此地址相同(虚拟地址)而值不同没什么奇怪。fork()会产生一个和父进程完全相同的子进程,但子进程在此后多会exec系统调用,出于效率考虑,linux中引入了“写时复制“技术,也就是只有进程空间的各段的内容要发生变化时,才会将父进程的内容复制一份给子进程。由于写时复制,在fork之后exec之前两个进程有独立的虚拟地址空间,共享物理内存。只有其中一方需要写操作时,再为子进程的数据段、栈、堆分配物理空间。但在子进程上调用exec时,会清空栈、堆,以及和父进程共享的空间,重新加载新的代码段,这样避免了“写时复制”拷贝共享页面的机会,父进程也同时独自拥有了原来共享的物理内存(可对其读写操作)。
7、内核态与用户态的区别⭐⭐⭐⭐⭐
内核态与用户态:内核态(系统态)与用户态是操作系统的两种运行级别。内核态拥有最高权限,可以访问所有系统指令;用户态则只能访问一部分指令。
什么时候进入内核态:共有三种方式:a、系统调用。b、异常。c、设备中断。其中,系统调用是主动的,另外两种是被动的。
为什么区分内核态与用户态:在CPU的所有指令中,有一些指令是非常危险的,如果错用,将导致整个系统崩溃。比如:清内存、设置时钟等。所以区分内核态与用户态主要是出于安全的考虑。
二、 c++11新特性
- 自动类型推导auto:auto的自动类型推导用于从初始化表达式中推断出变量的数据类型。通过auto的自动类型推导,可以大大简化我们的编程工作。
- nullptr:nullptr是为了解决原来C++中NULL的二义性问题而引进的一种新的类型,因为NULL实际上代表的是0,而nullptr是void*类型的
- lambda表达式:它类似Javascript中的闭包,它可以用于创建并定义匿名的函数对象,以简化编程工作。Lambda的语法如下:
mutable或exception声明->返回值类型{函数体} - 新的智能指针 unique_ptr和shared_ptr
三、tcp/udp连接,区别
1、作者:牛客网
链接:https://www.zhihu.com/question/271701044/answer/1808988570
来源:知乎
2、补充 TCP三次握手时第一次的seq序号是如何产生的?
第一次的序号是随机序号,但也不是完全随机,它是使用一个ISN算法得到的。
seq = C + H (源IP地址,目的IP地址,源端口,目的端口)。其中,C是一个计时器,每隔一段时间值就会变大,H是消息摘要算法,输入是一个四元组(源IP地址,目的IP地址,源端口,目的端口)。
3、错误处理
TCP数据传输一个特点是,协议层在发送数据时不会关心数据形成的逻辑结构,不管上层协议如何组织数据,一旦数据抵达TCP协议层后,他们只会被当做数据流对待。TCP协议层在接收到上层协议传来数据时,它会将数据缓存在内存中,等到合适时机在选取一部分数据发送出去。
这种把数据缓存然后再发送的方式在传输文件时不会有问题,但在需要实时反馈的应用情景下就会出现严重问题。例如Telnet协议,也就是我们常用的远程登录窗口,此时用户希望每输入一个字符,窗口都必须有及时反馈,这就要求下层TCP不能积攒数据,一定要在收到数据后立刻发送出去。为了让TCP实现数据直接发送而不积攒,在TCP包中设置了PSH控制位,当我们把该为设置成1时,数据一旦传到TCP层就会被立即发送出去,这就是所谓TCP协议的“PUSH"功能。
通常情况下,数据会按次序发送,先输送给TCP层的数据会先被发送出去。但有情况下,后面提交给TCP层的数据需要比前面提交给TCP的数据提前发送出去。一个典型例子是,假设双方在相互发送大段文件信息,如果其中一端发现发送了错误的文件内容,那么它就必须赶紧通知对方停止发送和接收。此时如果有很多文件内容已经在TCP层等待,通常情况下通知对方终止接收的消息需要等排在前面的文件数据发送完后才获得发送的机会。
但是如果等到大量文件数据发送给对方后才通知对方内容错误显然会浪费宝贵时间,因此当前通知对方放弃接收的信息必须提前发送,此时我们只要将TCP数据包中的URG控制位设置成1,该数据包就能被TCP层提前发送出去而不要在队列中等待。
TCP协议要保证数据传输的稳定性,一个重要功能是他要能检测到丢包并重发丢失的数据包。前面我们看到,当一方发送出数据后,它必须等待对方回发ACK包才能保证数据被对方正确接收,但由于网络的不可控性,发出的数据有可能对方没有收到,或者对方回发的ACK包在传输过程中丢失,任何一种情况发送时,我们都无法确保数据是否安全发送,因此TCP协议层必须要有处理相关情况的机制。
TCP协议层的基本处理方法是,当一方发送出数据包时就启动一个定时器,当定时器时间片用完后还没有收到对应的ACK包,数据就会重新发送。在具体实现中,TCP会把发送出去的数据放置到一个重传队列中,然后启动时钟,如果在时钟触发前收到了ACK包那么数据就会从队列中拿掉,要不然时钟触发后排在队列中的数据就会再次被发送。
数据被重发时我们也不能保证他一定会被正常接收,因此即使重发后数据还依然保持在重发队列里,同时再次启动对应的重发时钟,只要一直接收不到对应的ACK包,这个过程就会反复进行,当然该过程不会无止境的循环,当重复一定次数后连接就会中断。
我们还需要深入了解TCP协议的回复机制。当一方向对方 发送三个数据包,对方并不是对接收到的三个数据包各自回复一个ACK包,例如A向B发送3个数据包,第一个数据包的seq字段为0,数据长度为100,第二个数据包seq为101,长度为100,第三个数据包seq为201,长度为100,如果对方成功接收3个数据包后,只需要向A发送一个ACK包,其中ack字段设置为301就可以表明对方成功接收了3个数据包。
假设三个数据包发送后,第二个数据包丢失,那么B接收到数据包1和3,但它只能返回一个包含ack字段为101的数据包,它不能对接收到的数据包3发送ack包,因为那样会让A以为B也接收到了数据包2。于是B就一直等待直到A再次将数据包2,3传送过来。然而这种机制会导致数据传递效率变得相当低下。例如服务器向客户端发送20个数据包,第一个数据包丢失但后面19个数据包被成功接收,但此时客户端不能向服务器发送ack包,因为如果发送就会被服务器误以为所有数据包都被成功接收,于是服务器就只能再次发送20个数据包。
面对这种情况TCP协议有多种处理方案。一种是对每个已经发送的数据包设置定时器,服务器只重传超时的数据包,例如在该例子中,由于第一个数据包最早发送因此它也会最早超时,此时服务器再将第一个数据包发送一次,如果这次客户端能成功接收,那么它就可以发送ACK包告诉服务器端数据全部正常接收,这种机制与我们前面描述的机制类似,另一种办法就是一下子全部重传,两种方法没有谁更好一说,协议的实现者可以根据需要自己选取合适的方案。
TCP协议为了处理这种情况,后来特别增添了所谓选择性回复的功能。双方在建立连接进行三次握手时必须协商是否使用该功能。该功能的特点在于回复ACK时数据包不是只包含一个数据,而是包含一个数字队列,队列中的数字对应已经接受到的数据包seq字段。于是服务器就可以知道哪些数据对方接收到,哪些数据包丢失,因此它可以把丢失的数据包重传即可。
TCP协议有太多的细节需要考虑。前面说到数据包一旦发送后,数据会存放在重传队列中,然后启动时钟在超时后将数据包再次发送。然而为了保证数据传输效率,我们必须谨慎选择时钟的长度,如果选得过长,有可能造成很多数据积累在队列中,如果选得过短,数据包发送过于频繁造成网络带宽下降。决定重传时钟长度是一个非常棘手问题,通常情况下重传时钟长度设置为数据在两台设备间一次来回所需要的时间,也称为round-trip-time,简称RTT。显然在实际情况中不存在固定的RTT,由于设备可能位于不同地理位置,数据包要经过很多不同地区不同性质的网络,因此确定数据包在两个设备之间来回所需时间根本不可能。
于是TCP采用一种动态决定重传时间片的机制。它通过不断估算数据包在两个设备中实现一个来回的时间来调整重传时间片。它采用一个小于1的系数a,然后通过如下公式计算时间片:本次重传时间片 = a * 前一次重传时间片 + (1-a)*上一次重传时间片。数据在两台设备间一个来回的时间计算主要依据数据包发送后收到ACK回复包的这段时间。这里又引出一个问题,如果数据发送重传,也就是数据包发送两次后才收到ACK包,那么如何确定这个包是对第二次发送的回应还是对第一次发送的回应?
处理这个问题引出了专门算法叫karn算法。它的基本思路是一开始设定一个重传时间片,如果数据包重传一次后下一次要再重传,它需要等待的时间是上一次的2倍,这种时间翻倍的行为一直重复到数据包收到对应的ACK回复为止。
原文链接:https://blog.csdn.net/tyler_download/article/details/102391634
4、补充二 错误处理
https://blog.csdn.net/cws1214/article/details/52430554
四、. 设计模式,单例模式
单例中哪个是线程安全的(饿汉模式)
单例模式:保证类的实例化对象仅有一个,并且提供一个访问他的全局访问点。
应用场景:
表示文件系统的类,一个操作系统一定是只有一个文件系统,因此文件系统的类的实例有且仅有一个。
打印机打印程序的实例,一台计算机可以连接好几台打印机,但是计算机上的打印程序只有一个,就可以通过单例模式来避免两个打印作业同时输出到打印机。实现方式:
默认的构造函数、拷贝构造函数、赋值构造函数声明为私有的,这样禁止在类的外部创建该对象;
全局访问点也要定义成 静态类型的成员函数,没有参数,返回该类的指针类型。因为使用实例化对象的时候是通过类直接调用该函数,并不是先创建一个该类的对象,通过对象调用。
懒汉模式:
#include <iostream> #include <pthread.h> using namespace std; class singleInstance{ public: static singleInstance* GetsingleInstance(){ if (instance == NULL){ pthread_mutex_t mutex;//mutex mlock; 加锁互斥 pthread_mutex_lock(&mutex);//mlock.lock(); if (instance == NULL){ instance = new singleInstance(); } pthread_mutex_unlock(&mutex);//mlock.unlock(); } return instance; }; ~singleInstance(){}; private:// 涉及创建对象的函数都设置为private singleInstance(){}; singleInstance(const singleInstance& other){}; singleInstance& operator=(const singleInstance& other){ return *this; }; static singleInstance* instance; }; //懒汉式 singleInstance* singleInstance::instance = nullptr; int main(){ // 因为没有办法创建对象,就得采用静态成员函数的方法返回静态成员变量 singleInstance *s = singleInstance::GetsingleInstance(); //singleInstance *s1 = new singleInstance(); // 报错 cout << "Hello World"; return 0; }
饿汉模式
#include <iostream> #include <pthread.h> using namespace std; class singleInstance{ public: static singleInstance* GetsingleInstance(){ // 饿汉式,直接创建一个对象,不需要加锁 static singleInstance instance; return &instance; }; ~singleInstance(){}; private:// 涉及创建对象的函数都设置为private singleInstance(){}; singleInstance(const singleInstance& other){}; singleInstance& operator=(const singleInstance& other){ return *this; }; }; int main(){ // 因为没有办法创建对象,就得采用静态成员函数的方法返回 singleInstance *s = singleInstance::GetsingleInstance(); //singleInstance *s1 = new singleInstance(); // 报错 cout << "Hello World"; return 0; }
五、物理地址和逻辑地址的映射
虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存,从而让程序获得更多的可用内存。
为了更好的管理内存,操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间,这个地址空间被分割成多个块,每一块称为一页。
这些页被映射到物理内存,但不需要映射到连续的物理内存,也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时,由硬件执行必要的映射,将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出,虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存,也就是说一个程序不需要全部调入内存就可以运行,这使得有限的内存运行大程序成为可能。
逻辑地址: 源程序经过汇编或编译后,形成目标代码,每个目标代码都是以0为基址顺序进行编址的,原来用符号名访问的单元用具体的数据——单元号取代。这样生成的目标程序占据一定的地址空间,称为作业的逻辑地址空间,简称逻辑空间。
在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。即应用程序中使用的地址。要经过寻址方式的计算或变换才得到内存中的物理地址。线性地址:线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址,或者说是段中的偏移地址,加上相应段的基地址就生成了一个线性地址。如果启用了分页机制,那么线性地址可以再经变换以产生一个物理地址。若没有启用分页机制,那么线性地址直接就是物理地址。
CPU将一个虚拟内存空间中的地址转换为物理地址,需要进行两步:首先将给定一个逻辑地址(其实是段内偏移量=),CPU要利用其段式内存管理单元,先将为个逻辑地址转换成一个线性地址,再利用其页式内存管理单元,转换为最终物理地址。
六、http连接,状态码
http1.0 / http1.1 / http2.0
###1、HTTP1.0、HTTP1.1的区别
长连接(Persistent Connection):HTTP1.1支持长连接和请求的流水线处理,在一个TCP连接上可以传送多个HTTP请求和响应,减少了建立和关闭连接的消耗和延迟。
- 什么是长连接
HTTP1.1规定了默认保持长连接(HTTP persistent connection ,也有翻译为持久连接),数据传输完成了保持TCP连接不断开(不发RST包、不四次握手),等待在同域名下继续用这个通道传输数据;相反的就是短连接。长连接的好处是效率高,缺点是占用资源。
2、HTTP2.0有哪些改动?
多路复用允许同时通过单一的 HTTP/2 连接发起多重的请求-响应消息。
3、状态码
-200 - 请求成功
-301 - 资源(网页等)被永久转移到其它URL 被请求的资源已永久移动到新位置,新的URL在Location头中给出,浏览器应该自动地访问新的URL。301为永久重定向。
-302 - 请求报文存在语法错误
-400 - 请求无效 请求报文存在语法错误
-403 - 禁止访问 表示对请求资源的访问被服务器拒绝
-404 - 请求的资源(网页等)不存在 表示在服务器上没有找到请求的资源
-500 - 内部服务器错误
-503 - 表明服务器暂时处于超负载或正在停机维护,无法处理请求
4、cookie
- HTTP 协议是无状态的,主要是为了让 HTTP 协议尽可能简单,使得它能够处理大量事务,HTTP/1.1 引入 Cookie 来保存状态信息。
- Cookie 是服务器发送到用户浏览器并保存在本地的一小块数据,它会在浏览器之后向同一服务器再次发起请求时被携带上,用于告知服务端两个请求是否来自同一浏览器。由于之后每次请求都会需要携带Cookie 数据,因此会带来额外的性能开销(尤其是在移动环境下)。
- cookie 的出现是因为 HTTP 是无状态的一种协议,换句话说,服务器记不住你,可能你每刷新一次网页,就要重新输入一次账号密码进行登录。这显然是让人无法接受的,cookie 的作用就好比服务器给你贴个标签,然后你每次向服务器再发请求时,服务器就能够 cookie 认出你。
- 抽象地概括一下:一个 cookie 可以认为是一个「变量」,形如 name=value,存储在浏览器;一个session 可以理解为一种数据结构,多数情况是「映射」(键值对),存储在服务器上。
5、session
- 除了可以将用户信息通过 Cookie 存储在用户浏览器中,也可以利用 Session 存储在服务器端,存储在服务器端的信息更加安全。
- Session 可以存储在服务器上的文件、数据库或者内存中。也可以将 Session 存储在 Redis 这种内存型数据库中,效率会更高。
- 使用 Session 维护用户登录状态的过程如下:
- 用户进行登录时,用户提交包含用户名和密码的表单,放入 HTTP 请求报文中;
- 服务器验证该用户名和密码,如果正确则把用户信息存储到 Redis 中,它在 Redis 中的 Key 称为
Session ID; - 服务器返回的响应报文的 Set-Cookie 首部字段包含了这个 Session ID,客户端收到响应报文之后
将该 Cookie 值存入浏览器中; - 客户端之后对同一个服务器进行请求时会包含该 Cookie 值,服务器收到之后提取出 Session ID,
从 Redis 中取出用户信息,继续之前的业务操作。
6、cookie 和 session对比
Cookie
Cookie是客户端保持状态的方法。
Cookie简单的理解就是存储由服务器发至客户端并由客户端保存的一段字符串。为了保持会话,服务器可以在响应客户端请求时将Cookie字符串放在Set-Cookie下,客户机收到Cookie之后保存这段字符串,之后再请求时候带上Cookie就可以被识别。Session
Session是服务器保持状态的方法。
首先需要明确的是,Session保存在服务器上,可以保存在数据库、文件或内存中,每个用户有独立的Session用户在客户端上记录用户的操作。我们可以理解为每个用户有一个独一无二的Session ID作为Session文件的Hash键,通过这个值可以锁定具体的Session结构的数据,这个Session结构中存储了用户操作行为。当服务器需要识别客户端时就需要结合Cookie了。每次HTTP请求的时候,客户端都会发送相应的Cookie信息到服务端。实际上大多数的应用都是用Cookie来实现Session跟踪的
七、stl容器
迭代器失效
容器底层的数据结构实现
对于序列式容器(如vector,deque),序列式容器就是数组式容器,删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。
对于关联容器(如map, set,multimap,multiset),删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。
对于链表式容器(如list),删除当前的iterator,仅仅会使当前的iterator失效,这是因为list之类的容器,使用了链表来实现,插入、删除一个结点不会对其他结点造成影响。
八、linux基础指令
1、查看进程状态 ps
- ps -aux | grep PID
- ps -aux 查看进程状态
USER:该进程属于那个使用者账号。
PID :该进程的进程ID号。
%CPU:该进程使用掉的 CPU 资源百分比;
%MEM:该进程所占用的物理内存百分比;
VSZ :该进程使用掉的虚拟内存量 (Kbytes)
RSS :该进程占用的固定的内存量 (Kbytes)
TTY :该进程是在那个终端机上面运作,若与终端机无关,则显示 ?。另外, tty1-tty6 是本机上面的登入者程序,若为 pts/0 等等的,则表示为由网络连接进主机的程序。
STAT:该程序目前的状态,
2、查看进程状态: top
可以查看操作系统的信息,如进程、CPU占用率、内存信息等;
https://www.cnblogs.com/gaoyuechen/p/8595258.html
https://blog.51cto.com/liuqun/2049656
3、strace
使用strace跟踪进程系统调用
常用来跟踪进程执行时的系统调用和所接收的信号。
strace作为一种动态跟踪工具,能够帮助运维高效地定位进程和服务故障。
查看程序运行时,内部运行的一些细节信息。
4、losf
lsof(List Open Files) 用于查看你进程开打的文件,打开文件的进程,进程打开的端口(TCP、UDP),找回/恢复删除的文件。
COMMAND:进程的名称
PID:进程标识符
USER:进程所有者
FD:文件描述符,应用程序通过文件描述符识别该文件。如cwd、txt等
TYPE:文件类型,如DIR、REG等
DEVICE:指定磁盘的名称
SIZE:文件的大小
NODE:索引节点(文件在磁盘上的标识)
NAME:打开文件的确切名称
https://blog.csdn.net/guoguo1980/article/details/2324454
5、netstat
Netstat 命令用于显示各种网络相关信息,如网络连接(tcp/udp),路由表,接口状态 (Interface Statistics),masquerade 连接,多播成员 (Multicast Memberships) 等等。
https://blog.csdn.net/dongl890426/article/details/86981901
6、chmod
该命令用于改变文件的权限,
九、内存结构/分布模型
一个程序在内存上有BSS段,Date段、text段三个组成的。在没有调入内存前,可执行程序分为代码段,数据区和未初始化数据三部分。
进程地址空间内有:
代码段text:存放程序的二进制代码。通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定,并且内存区域通常属于只读, 某些架构也允许代码段为可写,即允许修改程序。在代码段中,也有可能包含一些只读的常数变量,例如字符串常量等。
初始化的数据Data:已经初始化的变量和数据。通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
未初始化的数据BSS:未初始化的数据。(bss segment)通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称。BSS段属于静态内存分配。bss段(未进行初始化的数据)的内容并不存放在磁盘上的程序文件中。其原因是内核在程序开始运行前将它们设置为0。需要存放在程序文件中的只有正文段和初始化数据段。text段和data段在编译时已经分配了空间,而BSS段并不占用可执行文件的大小,它是由链接器来获取内存的。
堆:堆是用于存放进程运行中被动态分配的内存段,它的大小并不固定,可动态扩张或缩减。当进程调用malloc等函数分配内存时,新分配的内存就被动态添加到堆上;当利用free等函数释放内存时,被释放的内存从堆中被剔除。
这里区别** 堆区**:用于动态分配内存,位于BSS和栈中间的地址区域。由程序员申请分配和释放。堆是从低地址位向高地址位增长,采用链式存储结构。频繁的malloc/free造成内存空间的不连续,产生碎片。当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。栈:栈又称堆栈,** 是用户存放程序临时创建的局部变量,也就是说我们函数括弧“{}”中定义的变量(但不包括static声明的变量,static意味着在数据段中存放变量)。除此以外,在函数被调用时,其参数也会被压入发起调用的进程栈中,并且待到调用结束后,函数的返回值也会被存放回栈中。由于栈的先进先出特点,所以栈特别方便用来保存/恢复调用现场。从这个意义上讲,我们可以把堆栈看成一个寄存、交换临时数据的内存区。
这里区别 栈区**:由编译器自动释放,存放函数的参数值、局部变量等。每当一个函数被调用时,该函数的返回类型和一些调用的信息被存放到栈中。然后这个被调用的函数再为他的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的,是一块连续的内存区域,最大容量是由系统预先定义好的,申请的栈空间超过这个界限时会提示溢出,用户能从栈中获取的空间较小。
十、死锁
1、产生的必要条件:
互斥条件:资源同时只能由一个进程占有。
不可抢占:不能抢占其他进程的资源,只能等对方开放;
占有且申请: 占有且申请:申请其他资源时不放开自己已占有的资源。
循环等待:手中拿着对方想要的资源同时向对方要资源。
2、产生死锁的原因主要是:
因为系统资源不足。
进程运行推进的顺序不合适。
资源分配不当等。
3、死锁的恢复:
重新启动:是最简单、最常用的死锁消除方法,但代价很大,因为在此之前所有进程已经完成的计算工作都将付之东流,不仅包括死锁的全部进程,也包括未参与死锁的全部进程。
终止进程(process termination):终止参与死锁的进程并回收它们所占资源。
(1) 一次性全部终止;(2) 逐步终止(优先级,代价函数)
剥夺资源(resource preemption):剥夺死锁进程所占有的全部或者部分资源。
(1) 逐步剥夺:一次剥夺死锁进程所占有的一个或一组资源,如果死锁尚未解除再继续剥夺,直至死锁解除为止。
(2) 一次剥夺:一次性地剥夺死锁进程所占有的全部资源。
进程回退(rollback):让参与死锁的进程回退到以前没有发生死锁的某个点处,并由此点开始继续执行,希望进程交叉执行时不再发生死锁。但是系统开销很大:
(1) 要实现“回退”,必须“记住”以前某一点处的现场,而现场随着进程推进而动态变化,需要花费大量时间和空间。
(2) 一个回退的进程应当“挽回”它在回退点之间所造成的影响,如修改某一文件,给其它进程发送消息等,这些在实现时是难以做到的
4、死锁预防
打破占有且申请: 可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。
打破循环等待: 实行资源有序分配策略。采用这种策略,即把资源事先分类编号,按号分配,使进程在申请,占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源,才能申请大号资源,就不会产生环路,从而预防了死锁。
安全序列:安全序列是指对当前申请资源的进程排出一个序列,保证按照这个序列分配资源完成进程,不会发生 “酱油和醋” 的尴尬问题。
我们假设有进程 P1, P2, ..... Pn,则安全序列要求满足:Pi (1<=i<=n) 需要资源 <= 剩余资源 + 分配给Pj(1 <= j < i) 资源为什么等号右边还有已经被分配出去的资源?想想银行家那个问题,分配出去的资源就好比第二个开发商,人家能还回来钱,咱得把这个考虑在内。
银行家算法。
补充:
一、网络
1、网络的字节序
2、网络知识 tcp三次握手 各种细节 timewait状态
3、tcp 与 udp 区别 概念 适用范围
4、TCP四次挥手讲一下过程,最后一次ack如果客户端没收到怎么办,为什么挥手不能只有三次,为什么time_wait。
5、对于socket编程,accept方法是干什么的,在三次握手中属于第几次,可以猜一下,为什么这么觉得。
6、tcp怎么保证有序传输的,讲下tcp的快速重传和拥塞机制,知不知道time_wait状态,这个状态出现在什么地方,有什么用?
7、知道udp是不可靠的传输,如果你来设计一个基于udp差不多可靠的算法,怎么设计?
8、http与https有啥区别?说下https解决了什么问题,怎么解决的?说下https的握手过程。
9、tcp 粘包半包问题怎么处理?
10、keepalive 是什么东东?如何使用?
11、列举你所知道的tcp选项,并说明其作用。
12、socket什么情况下可读?
13、nginx的epoll模型的介绍以及io多路复用模型
14、SYN Flood攻击
15、流量控制,拥塞控制
16、TCP和UDP区别,TCP如何保证可靠性,对方是否存活(心跳检测)
17、tcpdump抓包,如何分析数据包
18、tcp如何设定超时时间
19、基于socket网络编程和tcp/ip协议栈,讲讲从客户端send()开始,到服务端recv()结束的过程,越细越好
20、http报文格式
21、http1.1与http1.0区别,http2.0特性
22、http3了解吗
23、http1.1长连接时,发送一个请求阻塞了,返回什么状态码?
24、udp调用connect有什么作用?
二、操作系统
- 进程和线程-分别的概念 区别 适用范围 它们分别的通讯方式 不同通讯方式的区别优缺点
- 僵尸进程
- 死锁是怎么产生的
- CPU的执行方式
- 代码中遇到进程阻塞,进程僵死,内存泄漏等情况怎么排查。
- 有没有了解过协程?说下协程和线程的区别?
- 堆是线程共有还是私有,堆是进程共有还是私有,栈呢
- 了解过协程吗(我:携程???不了解呜呜呜)
- 共享内存的使用实现原理(必考必问,然后共享内存段被映射进进程空间之后,存在于进程空间的什么位置?共享内存段最大限制是多少?)
- c++进程内存空间分布(注意各部分的内存地址谁高谁低,注意栈从高道低分配,堆从低到高分配)
- ELF是什么?其大小与程序中全局变量的是否初始化有什么关系(注意.bss段)
- 使用过哪些进程间通讯机制,并详细说明(重点)
- 多线程和多进程的区别(重点 面试官最最关心的一个问题,必须从cpu调度,上下文切换,数据共享,多核cup利用率,资源占用,等等各方面回答,然后有一个问题必须会被问到:哪些东西是一个线程私有的?答案中必须包含寄存器,否则悲催)
- 信号:列出常见的信号,信号怎么处理?
- i++是否原子操作?并解释为什么???????
- 说出你所知道的各类linux系统的各类同步机制(重点),什么是死锁?如何避免死锁(每个技术面试官必问)(各种锁)
- 列举说明linux系统的各类异步机制
- exit() _exit()的区别?
- 如何实现守护进程?
- linux的内存管理机制是什么?
- linux的任务调度机制是什么?
- 标准库函数和系统调用的区别?
- 补充一个坑爹坑爹坑爹坑爹的问题:系统如何将一个信号通知到进程?(这一题哥没有答出来)
- 常见线程之间的同步技术(何时该用那种技术)
三、Linux系统
- linux的各种命令 给你场景让你解决
- Linux了解么,查看进程状态ps,查看cpu状态 top。查看占用端口的进程号netstat grep
- Linux的cpu 100怎么排查,top jstack,日志,gui工具
- Linux操作系统了解么
- 怎么查看CPU负载,怎么查看一个客户下有多少进程
- Linux内核是怎么实现定时器的
- gdb怎么查看某个线程
- core dump有没有遇到过,gdb怎么调试
- linux如何设置core文件生成
- linux如何设置开机自启动
- linux用过哪些命令、工具
- 用过哪些工具检测程序性能,如何定位性能瓶颈的地方
- netstat tcpdump ipcs ipcrm (如果这四个命令没听说过或者不能熟练使用,基本上可以回家,通过的概率较小 ^_^ ,这四个命令的熟练掌握程度基本上能体现面试者实际开发和调试程序的经验)
- cpu 内存 硬盘 等等与系统性能调试相关的命令必须熟练掌握,设置修改权限 tcp网络状态查看 各进程状态 抓包相关等相关命令 必须熟练掌握
- awk sed需掌握
- gdb调试相关的经验,会被问到
17. 熟悉进程、线程状态查看命令(top、strace、pstack)
18. 熟悉内存状态查看命令memstat、free
19. 熟悉IO状态查看命令iostat、df、du
20. 解linux文件的权限、用户、时间(ctime、mtime、atime)、inode等文件基本属性,,熟练使用chmod、chown、chgrp等基本命令。
21. 熟悉文件传输命令scp、rz、sz命令、
22. 熟悉文件定位命令find、whereis命令。
23. 熟悉lsof命令
四、MySQL
- 索引的常见实现方式有哪些,有哪些区别?MySQL的存储引擎有哪些,有哪些区别?InnoDB使用的是什么方式实现索引,怎么实现的?说下聚簇索引和非聚簇索引的区别?
- mysql查询优化
- MySQL的索引,B+树性质。
- B+树和B树,联合索引等原理
- mysql的悲观锁和乐观锁区别和应用,ABA问题的解决
- 项目性能瓶颈在哪,数据库表怎么设计
- 假设项目的性能瓶颈出现在写数据库上,应该怎么解决峰值时写速度慢的问题
- 假设数据库需要保存一年的数据,每天一百万条数据,一张表最多存一千万条数据,应该怎么设计表
- 数据库自增索引。100台服务器,每台服务器有若干个用户,用户有id,同时会有新用户加入。实现id自增,统计用户个数?不能重复,好像是这样的。
- mysql,会考sql语言,服务器数据库大规模数据怎么设计,db各种性能指标
五. 算法题
ip地址点分十进制
https://leetcode-cn.com/problems/restore-ip-addresses/ class Solution { vector<string> res; vector<int> ip = vector<int>(4); public: void dfs(const string& s, int ipID, int ipPos) { if(ipID == 4) // 返回条件 { if(ipPos == s.size()) { string ipaddr; for(int i=0; i<4; i++) { ipaddr += to_string(ip[i]); if(i != 3) { ipaddr += "."; } } res.push_back(move(ipaddr)); } return ; } if(ipPos == s.size()) // 异常跳出,已经到尾了 { return ; } if(s[ipPos] == '0') //前缀为零 { ip[ipID] = 0; dfs(s, ipID+1, ipPos+1); } int addr = 0; for(int ipend = ipPos; ipend <s.size(); ipend++) { addr = addr*10 + (s[ipend] - '0'); if(addr >0 && addr <= 255) { ip[ipID] = addr; dfs(s, ipID+1, ipend+1); } else { break; } } } vector<string> restoreIpAddresses(string s) { dfs(s,0,0); return res; } };
根据中序遍历和后序遍历构造二叉树
leetcode105. 从前序与中序遍历序列构造二叉树
class Solution { public: TreeNode* helper(int in_root, int in_left, int int_right, vector<int>& preorder, vector<int>& inorder) { if(in_left > int_right) return nullptr; TreeNode* root = new TreeNode(preorder[in_root]); int idx = in_left; while(preorder[in_root] != inorder[idx]) idx++; root->left = helper(in_root+1, in_left, idx-1, preorder, inorder); root->right = helper(in_root+idx-in_left+1, idx+1, int_right, preorder, inorder); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return helper(0, 0, (int)preorder.size()-1, preorder, inorder); } };
leetcode106.从中序与后序遍历序列构造二叉树
class Solution { int post_idx; unordered_map<int, int> idx_map; public: TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){ // 如果这里没有节点构造二叉树了,就结束 if (in_left > in_right) { return nullptr; } // 选择 post_idx 位置的元素作为当前子树根节点 int root_val = postorder[post_idx]; TreeNode* root = new TreeNode(root_val); // 根据 root 所在位置分成左右两棵子树 int index = idx_map[root_val]; // 下标减一 post_idx--; // 构造右子树 root->right = helper(index + 1, in_right, inorder, postorder); // 构造左子树 root->left = helper(in_left, index - 1, inorder, postorder); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { // 从后序遍历的最后一个元素开始 post_idx = (int)postorder.size() - 1; // 建立(元素,下标)键值对的哈希表 int idx = 0; for (auto& val : inorder) { idx_map[val] = idx++; } return helper(0, (int)inorder.size() - 1, inorder, postorder); } }; //作者:LeetCode-Solution //链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/
数组中前k大的数
class Solution { public: int ans = 0; int partition(vector<int>& a, int i, int j) { int pivot = a[i]; int pos = i; while(i < j) { while(a[j] <= pivot && i < j) j--; while(a[i] >= pivot && i < j) i++; if( i < j ) swap(a[i], a[j]); } swap(a[i], a[pos]); return i; } void quickselect(vector<int>& a, int left, int right, int k) { if(left <= right) { int mid = partition(a, left, right); if( mid == k-1 ) { ans = a[mid]; } else if( mid < k-1) { quickselect(a, mid+1, right, k); } else { quickselect(a, left, mid-1, k); } } } int findKth(vector<int> a, int n, int K) { // write code here quickselect(a, 0, n-1, K); return ans; } };
- LRU缓存
class LRUCache{ int cap; list<pair<int, int>> cache; unordered_map<int, list<pair<int, int>>::iterator> map; public: LRUCache(int capacity) { cap = capacity; } int get(int key) { if (map.count(key) > 0) { auto tmp = *map[key]; //listnode cache.erase(map[key]); map.erase(key); cache.push_front(tmp); map[key] = cache.begin(); return tmp.second; } return -1; } void put(int key, int value) { if (map.count(key) > 0) { cache.erase(map[key]); map.erase(key); } else if (cap == cache.size()) { auto tmp = cache.back(); // nodelist cache.pop_back(); map.erase(tmp.first); } cache.push_front(pair<int, int>(key, value)); map[key] = cache.begin(); } }; int main() { LRUCache* cache = new LRUCache(5); (*cache).put(1, 1); (*cache).put(2, 2); (*cache).put(3, 3); (*cache).put(4, 4); (*cache).put(5, 5); (*cache).put(6, 6); cout << (*cache).get(1) << endl; cout << (*cache).get(3) << endl; system("pause"); return 0; }