《C++面试宝典》V1.0 冲刺大厂~持续更新(8)

分享面试总结,涉及C++、算法、数据结构、操作系统、计算机网络、Linux、数据库、设计模式等后面持续更新~

内容多为一问一答式,多数来自收集。整理总结,视频、书籍学习所得,如有错误请指出,万分感谢!!!
学习建议:针对八股文,不太了解的可以网上扩展,自己总结,拿来主义最好能消化成自己的。
※代表高频问题(参考)

# 操作系统篇---  √2

21. 什么时候用多进程?什么时候用多线程?

1) 需要频繁创建销毁的优先用线程;
2) 需要进行大量计算的优先使用线程;
3) 强相关的处理用线程,弱相关的处理用进程;
4) 可能要扩展到多机分布的用进程,多核分布的用线程。


22. 线程比进程具有哪些优势?

需要频繁创建销毁的优先用线程;可能要扩展到多机分布的用进程,多核分布的用线程。

1) 线程在程序中是独立的,并发的执行流,但是,进程中的线程之间的隔离程度要小;

2) 线程比进程更具有更高的性能,这是由于同一个进程中的线程都有共性:多个线程将共享同一个进程虚拟空间;

3) 当操作系统创建一个进程时,必须为进程分配独立的内存空间,并分配大量相关资源。

请网上自行扩展!

23. 协程是什么?

1) 是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样,一个线程可以拥有多个协程;协程不是被操作系统内核管理,而完全是由程序所控制。
2) 协程的开销远远小于线程;
3) 协程拥有自己寄存器上下文和栈。协程调度切换时,将寄存器上下文和栈保存到其他地方,在切换回来的时候,恢复先前保存的寄存器上下文和栈。
4) 每个协程表示一个执行单元,有自己的本地数据,与其他协程共享全局数据和其他资源。
5) 跨平台、跨体系架构、无需线程上下文切换的开销、方便切换控制流,简化编程模型;
6) 协程又称为微线程,协程的完成主要靠yeild关键字,协程执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行;
7) 协程极高的执行效率,和多线程相比,线程数量越多,协程的性能优势就越明显;
8) 不需要多线程的锁机制。


24. 了解哪些锁?

1) 互斥锁:线程同步能够保证多个线程安全访问竞争资源,最简单的同步机制是引入互斥锁。互斥锁为资源引入一个状态:锁定/非锁定。某个线程要更改共享数据时,先将其锁定,此时资源的状态为“锁定”,其他线程不能更改;直到该线程释放资源,将资源的状态变成“非锁定”,其他的线程才能再次锁定该资源。互斥锁保证了每次只有一个线程进行写入操作,从而保证了多线程情况下数据的正确性。

2) 读写锁:读写锁从广义的逻辑上讲,也可以认为是一种共享版的互斥锁。如果对一个临界区大部分是读操作而只有少量的写操作,读写锁在一定程度上能够降低线程互斥产生的代价。

3) 递归锁:Mutex可以分为递归锁(recursive mutex)和非递归锁(non-recursive mutex)。可递归锁也可称为可重入锁(reentrant mutex),非递归锁又叫不可重入锁(non-reentrant mutex)。二者唯一的区别是,同一个线程可以多次获取同一个递归锁,不会产生死锁。而如果一个线程多次获取同一个非递归锁,则会产生死锁。

这里总结的不好,后续会更新,包括代码实现。


25. 用户态到内核态的转化原理?

1) 系统调用
这是用户态进程主动要求切换到内核态的一种方式,用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作,比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现,例如Linux的int 80h中断。

2) 异常
当CPU在执行运行在用户态下的程序时,发生了某些事先不可知的异常,这时会触发由当前运行进程切换到处理此异常的内核相关程序中,也就转到了内核态,比如缺页异常。

3) 外围设备的中断
当外围设备完成用户请求的操作后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。


26. 中断的实现过程?

关中断,进入不可再次响应中断的状态,由硬件实现。
保存断点,为了在中断处理结束后能正确返回到中断点。由硬件实现。
将中断服务程序入口地址送PC,转向中断服务程序。可由硬件实现,也可由软件实现。
保护现场、置屏蔽字、开中断,即保护CPU中某些寄存器的内容、设置中断处理次序、允许更高级的中断请求得到响应,实现中断嵌套。由软件实现。
设备服务,实际上有效的中断处理工作是在此程序段中实现的。由软件程序实现
退出中断。在退出时,又应进入不可中断状态,即关中断、恢复屏蔽字、恢复现场、开中断、中断返回。

哪些由软件实现,哪些由硬件实现?


27. 用户态和内核态的区别?

1) 内核态与用户态是操作系统的两种运行级别,当程序运行在3级特权级上时,就可以称之为运行在用户态,因为这是最低特权级,是普通的用户进程运行的特权级,大部分用户直接面对的程序都是运行在用户态;反之,当程序运行在0级特权级上时,就可以称之为运行在内核态。运行在用户态下的程序不能直接访问操作系统内核数据结构和程序。当我们在系统中执行一个程序时,大部分时间是运行在用户态下的,在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态。

2) 这两种状态的主要差别是:处于用户态执行时,进程所能访问的内存空间和对象受到限制,其所处于占有的处理机是可被抢占的;而处于核心态执行中的进程,则能访问所有的内存空间和对象,且所占有的处理机是不允许被抢占的。


28. CPU中断?

1) CPU中断:
计算机处于执行期间;
系统内发生了非寻常或非预期的急需处理事件;
CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序;
处理完毕后返回原来被中断处继续执行;
2) CPU中断的作用:
可以使CPU和外设同时工作,使系统可以及时地响应外部事件;
可以允许多个外设同时工作,大大提高了CPU的利用率;
可以使CPU及时处理各种软硬件故障。

29. 执行一个系统调用时,OS发生的过程,越详细越好?

1.执行用户程序。(如:fork)
2.根据glibc中的函数实现,取得系统调用号并执行int $0x80产生中断。
3.进行地址空间的转换和堆栈的切换,执行SAVE_ALL。(进行内核模式)
4.进行中断处理,根据系统调用表调用内核函数。
5.执行内核函数。
6.执行RESTORE_ALL并返回用户模式。


30. 函数调用和系统调用的区别?

1) 系统调用
操作系统提供给用户程序调用的一组特殊的接口。用户程序可以通过这组特殊接口来获得操作系统内核提供的服务;
系统调用可以用来控制硬件;设置系统状态或读取内核数据;进程管理,系统调用接口用来保证系统中进程能以多任务在虚拟环境下运行;
Linux中实现系统调用利用了0x86体系结构中的软件中断;
2) 函数调用
函数调用运行在用户空间;
它主要是通过压栈操作来进行函数调用;

区别:

31. 经典同步问题解法:生产者与消费者问题,哲学家进餐问题,读者写者问题?

高频题,请网上逐个学习!


32. 虚拟内存?使用虚拟内存的优点?什么是虚拟地址空间?

1) 虚拟内存,虚拟内存是一种内存管理技术,它会使程序自己认为自己拥有一块很大且连续的内存,然而,这个程序在内存中不是连续的,并且有些还会在磁盘上,在需要时进行数据交换;
2) 优点:可以弥补物理内存大小的不足;一定程度的提高反应速度;减少对物理内存的读取从而保护内存延长内存使用寿命;
3) 缺点:占用一定的物理硬盘空间;加大了对硬盘的读写;设置不得当会影响整机稳定性与速度。
4) 虚拟地址空间是对于一个单一进程的概念,这个进程看到的将是地址从0000开始的整个内存空间。虚拟存储器是一个抽象概念,它为每一个进程提供了一个假象,好像每一个进程都在独占的使用主存。每个进程看到的存储器都是一致的,称为虚拟地址空间。从最低的地址看起:程序代码和数据,堆,共享库,栈,内核虚拟存储器。大多数计算机的字长都是32位,这就限制了虚拟地址空间为4GB,注意这里是2^10=1024。


33. 线程安全?如何实现?

1) 如果你的代码所在的进程中有多个线程在同时运行,而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是一样的,而且其他的变量的值也和预期的是一样的,就是线程安全的。

2) 线程安全问题都是由全局变量及静态变量引起的。

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

4)对于线程不安全的对象我们可以通过如下方法来实现线程安全:
加锁利用Synchronized或者ReenTrantLock来对不安全对象进行加锁,来实现线程执行的串行化,从而保证多线程同时操作对象的安全性,一个是语法层面的互斥锁,一个是API层面的互斥锁.
非阻塞同步来实现线程安全。原理就是:通俗点讲,就是先进性操作,如果没有其他线程争用共享数据,那操作就成功了;如果共享数据有争用,产生冲突,那就再采取其他措施(最常见的措施就是不断地重试,知道成功为止)。这种方法需要硬件的支持,因为我们需要操作和冲突检测这两个步骤具备原子性。通常这种指令包括CAS SC,FAI TAS等。
线程本地化,一种无同步的方案,就是利用Threadlocal来为每一个线程创造一个共享变量的副本来(副本之间是无关的)避免几个线程同时操作一个对象时发生线程安全问题。


34. linux文件系统?

层次分析:
1) 用户层,日常使用的各种程序,需要的接口主要是文件的创建、删除、读、写、关闭等;
2) VFS层,文件相关的操作都有对应的System Call函数接口,接口调用VFS对应的函数;
3) 文件系统层,用户的操作通过VFS转到各种文件系统。文件系统把文件读写命令转化为对磁盘LBA的操作,起了一个翻译和磁盘管理的工作;
4) 缓存层;
5) 块设备层,块设备接口Block Device是用来访问磁盘LBA的层级,读写命令组合之后插入到命令队列,磁盘的驱动从队列读命令执行;
6) 磁盘驱动层;
7) 磁盘物理层;

读取文件过程
1) 根据文件所在目录的inode信息,找到目录文件对应数据块;
2) 根据文件名从数据块中找到对应的inode节点信息;
3) 从文件inode节点信息中找到文件内容所在数据块块号;
4) 读取数据块内容


35. 常见的IO模型,异步IO应用场景?有什么缺点?

1) 同步IO
就是在发出一个功能调用时,在没有得到结果之前,该调用就不返回。也就是必须一件一件事做,等前一件做完了才能做下一件事。就是我调用一个功能,该功能没有结束前,我死等结果。
2) 异步IO
当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者。就是我调用一个功能,不需要知道该功能结果,该功能有结果后通知我(回调通知)
3) 阻塞IO
阻塞调用是指调用结果返回之前,当前线程会被挂起(线程进入非可执行状态,在这个状态下,cpu不会给线程分配时间片,即线程暂停运行)。函数只有在得到结果之后才会返回。对于同步调用来说,很多时候当前线程还是激活的,只是从逻辑上当前函数没有返回而已。就是调用我(函数),我(函数)没有接收完数据或者没有得到结果之前,我不会返回。
4) 非阻塞IO
指在不能立刻得到结果之前,该函数不会阻塞当前线程,而会立刻返回。就是调用我(函数),我(函数)立即返回,通过select通知调用者。
a) 阻塞I/O
应用程序调用一个IO函数,导致应用程序阻塞,等待数据准备好。如果数据没有准备好,一直等待….数据准备好了,从内核拷贝到用户空间,IO函数返回成功指示。
b) 非阻塞I/O
我们把一个SOCKET接口设置为非阻塞就是告诉内核,当所请求的I/O操作无法完成时,不要将进程睡眠,而是返回一个错误。这样我们的I/O操作函数将不断的测试数据是否已经准备好,如果没有准备好,继续测试,直到数据准备好为止。在这个不断测试的过程中,会大量的占用CPU的时间。
c) ※※※I/O复用
I/O复用模型会用到select、poll、epoll函数,这几个函数也会使进程阻塞,但是和阻塞I/O所不同的的,这三个函数可以同时阻塞多个I/O操作。而且可以同时对多个读操作,多个写操作的I/O函数进行检测,直到有数据可读或可写时,才真正调用I/O操作函数。
d) 信号驱动I/O
首先我们允许套接口进行信号驱动I/O,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个SIGIO信号,可以在信号处理函数中调用I/O操作函数处理数据。
e) 异步I/O
当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者的输入输出操作。


36. IO复用的原理?三个函数?epoll的LT和ET模式的理解?

1) IO复用是Linux中的IO模型之一,IO复用就是进程预先告诉内核需要监视的IO条件,使得内核一旦发现进程指定的一个或多个IO条件就绪,就通过进程进程处理,从而不会在单个IO上阻塞了。Linux中,提供了select、poll、epoll三种接口函数来实现IO复用。
2) select
select的缺点:
单个进程能够监视的文件描述符的数量存在最大限制,通常是1024。由于select采用轮询的方式扫描文件描述符,文件描述符数量越多,性能越差;
内核/用户空间内存拷贝问题,select需要大量句柄数据结构,产生巨大开销;
Select返回的是含有整个句柄的数组,应用程序需要遍历整个数组才能发现哪些句柄发生事件;
Select的触发方式是水平触发,应用程序如果没有完成对一个已经就绪的文件描述符进行IO操作,那么每次select调用还会将这些文件描述符通知进程。
3) poll
与select相比,poll使用链表保存文件描述符,一你才没有了监视文件数量的限制,但其他三个缺点依然存在
4) epoll
上面所说的select缺点在epoll上不复存在,epoll使用一个文件描述符管理多个描述符,将用户关系的文件描述符的事件存放到内核的一个事件表中,这样在用户空间和内核空间的copy只需一次。Epoll是事件触发的,不是轮询查询的。没有最大的并发连接限制,内存拷贝,利用mmap()文件映射内存加速与内核空间的消息传递。

区别总结:
1) 支持一个进程所能打开的最大连接数
Select最大1024个连接,最大连接数有FD_SETSIZE宏定义,其大小是32位整数表示,可以改变宏定义进行修改,可以重新编译内核,性能可能会影响;
Poll没有最大连接限制,原因是它是基于链表来存储的;
连接数限数有上限,但是很大;
2) FD剧增后带来的IO效率问题
因为每次进行线性遍历,所以随着FD的增加会造成遍历速度下降,效率降低;
Poll同上;
因为epool内核中实现是根据每个fd上的callback函数来实现的,只有活跃的socket才会主动调用callback,所以在活跃socket较少的情况下,使用epoll没有前面两者的现象下降的性能问题。
3) 消息传递方式
Select内核需要将消息传递到用户空间,都需要内核拷贝;
Poll同上;
Epoll通过内核和用户空间共享来实现的。

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

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


37. Linux是如何避免内存碎片的?

1) 固定式分区分配中,为将一个用户作业装入内存,内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业,由于一个作业的大小并不一定与分区大小相等,因此,分区中有一部分存储空间浪费掉了.由此可知, 固定式分区分配中存在内碎片.
2) 可变式分区分配中,为把一个作业装入内存,应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业,如果这个空闲分区的容量比作业申请的空间容量要大,则将该分区一分为二,一部分分配给作业,剩下的部分仍然留作系统的空闲分区。由此可知,可变式分区分配中存在外碎片。
3) 伙伴系统,请网上查阅。
4) 据可移动性组织页避免内存碎片。


38. 缺页中断,页表寻址?

1) 一个进程对应一个页表,分页存储机制,一个进程对应很多页,执行进程时并不是所有页装入内存中,部分装入内存,当需要的那页不存在内存中,将发生缺页中断,将需要的那页从外存中调入内存中;
2) 页表寻址,页分为页号(从0开始编号)与页内偏移地址,两个寄存器,页表基地址寄存器,页表长度寄存器,块表;页的大小相同,内存中的块与页大小相同,页大小相同,页在逻辑上连续在物理上不连续;
3) 调页算法:先进先出,最佳页面置换算法(OPT),最近最久未使用(NRU),最近最少使用置换算法(LRU),先进先出算法(FIFO)会导致Baley问题;抖动,页面在内存与外存中的频繁调页;
4) 程序局部性原理,时间局部性、空间局部性方面解释。


39. LRU的实现?

1) 用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据的时间戳自增,并将新数据时间戳置为0插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项时间戳置为0。当数组空间已经满时,将时间戳最大的数据项淘汰;
2) 利用一个链表来实现,每次新插入数据的时候将新数据插入到链表头部;每次缓存命中,则将数据移动到链表头部;那么当链表满时,就将链表尾部的数据丢弃;
3) 利用链表和hashmap。当需要插入新的数据项的时候,如果新数据命中,则把该节点放到链表头部,如果不存在,则将新数据放在链表头部。若缓存满了,则将链表尾部的节点删除。
手撕实现???

40. 内存分区?

1) 固定分区,分区大小固定,但并不一定相同。
2) 可变分区,分区大小动态变化,首先适配、最佳适配、最差适配、下一次适配。

未完待续~

需资料分享,可私聊哈。



#面经##C/C++#
全部评论
牛,大佬带带我😄
点赞 回复 分享
发布于 2021-03-13 09:24
m
点赞 回复 分享
发布于 2021-03-19 15:08
dalao
点赞 回复 分享
发布于 2021-03-19 15:21
大佬求资料
点赞 回复 分享
发布于 2021-11-15 23:06
大佬求资料啊
点赞 回复 分享
发布于 2021-11-25 23:45

相关推荐

拉丁是我干掉的:把上海理工大学改成北京理工大学。成功率增加200%
点赞 评论 收藏
分享
评论
9
54
分享
牛客网
牛客企业服务