第一部分：操作系统（Linux）
目录：
1. 进程与线程的区别
2. 进程间通信方式
3. 线程间通信的方式
4. 请你说一说Linux虚拟地址空间
4.1 虚拟内存的概念
4.2 虚拟内存的好处：
4.3 虚拟内存的代价：
5. 请你说一说死锁发生的条件以及如何解决死锁
6. 请你说一说操作系统中的结构体对齐，字节对齐
6.1 原因：
6.2 规则
6.3 定义结构体对齐
6.4 举例
7. 请你说一下虚拟内存置换的方式
7.1 FIFO（先进先出淘汰算法）
7.2 LFU（最不经常访问淘汰算法）
7.3 LRU（最近最少使用替换算法）
7.4 LRU-K（LRU-2、LRU-3）
7.5 2Q
1. 进程与线程的区别
一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
进程是资源分配的最小单位，线程是CPU调度的最小单位；
系统开销： 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。
通信： 由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。在有的系统中，线程的切换、同步和通信都无须操作系统内核的干预
进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉
进程适应于多核、多机分布；线程适用于多核
2. 进程间通信方式
进程间通信主要包括管道pipe、有名管道FIFO、消息队列MessageQueue、共享存储、信号量Semaphore、信号Signal、套接字Socket。
（1）管道
管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。
特点：
它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
（2）有名管道FIFO
FIFO，也称为命名管道，它是一种文件类型。
特点：
FIFO可以在无关的进程之间交换数据，与无名管道不同。
FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
（3）消息队列
消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。
特点：
消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
消息队列独立于发送与接收进程。进程终止时，消息队列及其内-容并不会被删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
（4）信号量
信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
特点：
信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
支持信号量组。
（5）共享内存
共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。
特点：
共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
因为多个进程可以同时操作，所以需要进行同步。
信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
（5）套接字
socket也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同主机之间的进程通信。
3. 线程间通信的方式
临界区： 通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问；
互斥量Synchronized/Lock： 采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问
信号量Semaphore： 为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。
事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作
4. 请你说一说Linux虚拟地址空间
4.1 虚拟内存的概念
为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。
虚拟内存技术使得不同进程在运行过程中，它所看到的是自己独自占有了当前系统的4G内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。 事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。
请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。
4.2 虚拟内存的好处：
扩大地址空间；
内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。
公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。
当进程通信时，可采用虚存共享的方式实现。
当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存
虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高
在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片
4.3 虚拟内存的代价：
虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存
虚拟地址到物理地址的转换，增加了指令的执行时间。
页面的换入换出需要磁盘I/O，这是很耗时的
如果一页中只有一部分数据，会浪费内存。
5. 请你说一说死锁发生的条件以及如何解决死锁
死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的下相互等待的现象。死锁发生的四个必要条件如下：
互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；
请求并保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源
不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放
环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链
解决死锁的方法即破坏上述四个条件之一，主要方法如下：
资源一次性分配，从而剥夺请求和保持条件
可剥夺资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可剥夺的条件
资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件
6. 请你说一说操作系统中的结构体对齐，字节对齐
6.1 原因：
1）平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
2）性能原因：数据结构（尤其是栈）应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。
6.2 规则
1）数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中，比较小的那个进行。
2）结构(或联合)的整体对齐规则：在数据成员完成各自对齐之后，结构(或联合)本身也要进行对齐，对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行。
3）结构体作为成员：如果一个结构里有某些结构体成员，则结构体成员要从其内部最大元素大小的整数倍地址开始存储。
6.3 定义结构体对齐
可以通过预编译命令#pragma pack(n)，n=1,2,4,8,16来改变这一系数，其中的n就是指定的“对齐系数”。
6.4 举例
7. 请你说一下虚拟内存置换的方式
比较常见的内存替换算法有：FIFO，LRU，LFU，LRU-K，2Q。
7.1 FIFO（先进先出淘汰算法）
思想：最近刚访问的，将来访问的可能性比较大。
实现：使用一个队列，新加入的页面放入队尾，每次淘汰队首的页面，即最先进入的数据，最先被淘汰。
弊端：无法体现页面冷热信息
7.2 LFU（最不经常访问淘汰算法）
思想：如果数据过去被访问多次，那么将来被访问的频率也更高。
实现：每个数据块一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。每次淘汰队尾数据块。
开销：排序开销。
弊端：缓存颠簸。
7.3 LRU（最近最少使用替换算法）
思想：如果数据最近被访问过，那么将来被访问的几率也更高。
实现：使用一个栈，新页面或者命中的页面则将该页面移动到栈底，每次替换栈顶的缓存页面。
优点：LRU算法对热点数据命中率是很高的。
缺陷：
1）缓存颠簸，当缓存（1，2，3）满了，之后数据访问（0，3，2，1，0，3，2，1。。。）。
2）缓存污染，突然大量偶发性的数据访问，会让内存中存放大量冷数据。
7.4 LRU-K（LRU-2、LRU-3）
思想：最久未使用K次淘汰算法。
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
实现：
1）数据第一次被访问，加入到访问历史列表；
2）如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
3）当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
4）缓存数据队列中被再次访问后，重新排序；
5）需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。
针对问题： LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
7.5 2Q
类似LRU-2。使用一个FIFO队列和一个LRU队列。
实现：
1）新访问的数据插入到FIFO队列；
2）如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；
3）如果数据在FIFO队列中被再次访问，则将数据移到LRU队列头部；
4）如果数据在LRU队列再次被访问，则将数据移到LRU队列头部；
5）LRU队列淘汰末尾的数据。
针对问题：LRU的缓存污染
弊端： 当FIFO容量为2时，访问负载是：ABCABCABC会退化为FIFO，用不到LRU。
第二部分：数据库
目录：
1. 索引的作用？和它的优点缺点是什么？
2. 四个ACID基本性质
二、在线编程题
1. 最长公共子串
2. 随机生成[0.m]间n个正整数,不重复。时间复杂度是多少?
3. 数据库：找出分数高于80分的学生名单
这部分我面试的时候，问的较多且我掌握的也不多，我就不详细总结写了，我也在参考这几篇学习。
1. 索引的作用？和它的优点缺点是什么？
索引就一种特殊的查询表，数据库的搜索可以利用它加速对数据的检索。它很类似与现实生活中书的目录，不需要查询整本书内容就可以找到想要的数据。索引可以是唯一的，创建索引允许指定单个列或者是多个列。缺点是它减慢了数据录入的速度，同时也增加了数据库的尺寸大小。
2. 四个ACID基本性质
1.原子性：要么都执行，要么都不执行。
2.一致性：合法的数据才可以被写入。
3.隔离性：允许多个用户并发访问。
4.持久性：事务结束后，事务处理的结果必须得到固化。即一旦提交，对数据库改变是永久的。
二、在线编程题
1. 最长公共子串
题目描述：给出两个字符串，求出这样的一 个最长的公共子序列的长度：子序列 中的每个字符都能在两个原串中找到， 而且每个字符的先后顺序和原串中的 先后顺序一致。
最长公共子序列(POJ1458)
算法思路：
把两个字符串分别以行和列组成一个二维矩阵。
比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下：
从上图可以看到，str1和str2共有5个公共子串，但最长的公共子串长度为5。
为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：
递推公式为：
实现源代码：
暴力法：
动态规划法：
简化一下递推公式：
行、列都多一行，更适应公式。
2. 随机生成[0.m]间n个正整数,不重复。时间复杂度是多少?
3. 数据库：找出分数高于80分的学生名单
分析： 要查询出每门课程都大于80分的学生姓名，因为一个学生有多门课程，可能所有课程都大于80分，可能有些课程大于80分，另外一些课程少于80分，也可能所有课程都小于80分，那么我们要查找出所有大于80分的课程的学生姓名，我们可以反向思考，找出课程小于80分(可以找出有一些课程小于80分，所有课程小于80分的学生)的学生姓名再排除这些学生剩余的就是所有课程都大于80分的学生姓名了.
实现源代码：
最后，给大家分享一些关于Linux2020年最新的面试题，总共23道，希望大家能够喜欢。
1) Linux 中主要有哪几种内核锁？
2) Linux 中的用户模式和内核模式是什么含义?
3) 怎样申请大块内核内存?
4) 用户进程间通信主要哪几种方式?
5) 通过伙伴系统申请内核内存的函数有哪些?
6) Linux 虚拟文件系统的关键数据结构有哪些?(至少写出四个)
7) 对文件或设备的操作函数保存在那个数据结构中?
8) Linux 中的文件包括哪些?
9) 创建进程的系统调用有哪些?
10) 调用 schedule()进行进程切换的方式有几种?
11) Linux 调度程序是根据进程的动态优先级还是静态优先级来调度进程的?
12) 进程调度的核心数据结构是哪个?
13) 如何加载、卸载一个模块?
14) 模块和应用程序分别运行在什么空间?
15) Linux 中的浮点运算由应用程序实现还是内核实现?
16) 模块程序能否使用可链接的库函数?
17) TLB 中缓存的是什么内容?
18) Linux 中有哪几种设备?
19) 字符设备驱动程序的关键数据结构是哪个?
20) 设备驱动程序包括哪些功能函数?
21) 如何唯一标识一个设备?
22) Linux 通过什么方式实现系统调用?
23) Linux 软中断和工作队列的作用是什么?
因为文章篇幅限制，所以小编在这里就不做过多的介绍了，需要Linux面试题答案的话，可以转发关注小编，私信小编“学习”来得到获取方式。
网友评论