0%

面经2

发表于 更新于 分类于 ，

同步互斥和通信的区别

同步是指多个线程之间存在的一种松散的协作关系，一个线程的执行与否依赖另一个线程的消息，当它没有得到另一个线程的消息时应等待，直到消息到达时才被唤醒。例如生产消费者模型中，消费者需要等待生产者释放信号的条件后才会有动作

互斥是指某个共享资源在某一时刻只能有一个线程对他进行读写，而其他想要获取它的线程只能休眠。线程互斥可以看做特殊的同步

什么是系统调用

系统调用是操作系统提供给用户的一组接口，用户程序工作在用户态只能受限的访问系统的资源。通过系统调用用户可以主动从用户态转到内核态，进而获得更高的权限，访问操作系统更多的资源。write fork 等都是系统调用

用户态切换到内核态的3种方式

系统调用 异常（例如缺页异常） 外部中断

从出发方式看，可以在认为存在前述3种不同的类型，但是从最终实际完成由用户态到内核态的切换操作上来说，涉及的关键步骤是完全一样的，没有任何区别，都相当于执行了一个中断响应的过程，因为系统调用实际上最终是中断机制实现的，而异常和中断处理机制基本上是一样的，用户态切换到内核态的步骤主要包括：

  1. 从当前进程的描述符中提取其内核栈的ss0及esp0信息。
  2. 使用ss0和esp0指向的内核栈 ； 将当前进程的cs,eip （CS+EIP = PC），eflags，ss(栈段地址), esp（栈顶指针）信息保存起来，这个过程也完成了由用户栈找到内核栈的切换过程，同时保存了被暂停执行的程序的下一条指令。
  3. 将先前由中断向量检索得到的中断处理程序的 cs，eip 信息装入相应的寄存器，开始执行中断处理程序，这时就转到了内核态的程序执行了。

软件调用 system_call 函数 触发 80H 中断，然后通过80H的中断向量找到系统调用的处理函数，在该函数中根据不同的系统调用号 找到内核中对应的函数去处理，系统调用号是不同调用函数独有的，用户空间通过CPU寄存器暂存调用号。处理完毕后返回值通过 CPU 寄存器暂存。

互斥锁机制，以及互斥锁和读写锁的区别

互斥锁： 用于保证在任何时刻，都只能有一个线程访问该对象。当获取锁操作失败时，线程会进入睡眠，等待锁释放时被唤醒。

读写锁：分为读锁 和 写锁。处于读操作时，可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态，直到写锁释放时被唤醒，优先唤醒写锁。适用于读取数据的频率远远大于写数据的频率的场合。

互斥锁和读写锁的区别：

  • 互斥锁 只允许一个进程访问 资源，不区分读写，因此不能多个线程同时读。
  • 读写锁区分读 和 写，而互斥锁不区分

Linux的四种锁机制

读写锁：

互斥锁：

自旋锁：spinlock 在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时，不会进入睡眠，而是会在原地自旋，直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗，在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长，则会非常浪费CPU资源。

RCU锁：在加上写锁后，所有的读操作都被阻塞了，RCU锁就是解决这个问题的。它支持在写的时候同时高并发读，只有多个同时写的线程需要加自旋锁，但是这个也是很高效的。本质是当线程要对临界资源修改时，创建数据副本，对副本修改，修改完毕后，等待所有的读线程退出临界区后（宽松区）才会将原始的数据指针指向修改后的数据副本。这个指针的修改过程是 原子的，不会发生线程调度和中断，同时只能有一个线程访问并修改数据指针的指向。

说一说进程状态转换图，动态就绪，静态就绪，动态阻塞，静态阻塞

  1. 创建状态：进程正在被创建
  2. 就绪状态：进程被加入到就绪队列，等到CPU调度运行
  3. 运行状态：进程获得时间片，正在CPU中运行，可以和就绪态相互转换
  4. 阻塞状态：进程因为等待某种 IO/系统 资源设备而被阻塞 而暂时不能运行，当获取资源后 会 转换为就绪态等待再次被调度
  5. 终止状态：进程运行结束

早期内存小，资源紧张，I/O设备访问速度慢，可能会出现很多进程都处于阻塞状态等待I/O，这时候可以通过交换技术把阻塞的进程换到外存，腾出内存空间。从而出现了进程的挂起状态：进程被交换到外存，进程状态就成为了挂起状态。而同进程中解决内存占用过大的问题是通过虚拟内存技术解决。

  1. 动态就绪：进程在内存，只要CPU调度就可以运行
  2. 静态就绪：进程在外存，处于就绪状态，换入到内存然后CPU给调度就可以运行
  3. 活动阻塞：进程在内存，但是由于某种原因被阻塞了
  4. 静止阻塞：进程在外存，同时被某种原因阻塞了

新的转换过程：

  1. 内存不够时：活动就绪 -> 静止就绪，调到外存
  2. 内存不够时：活动阻塞 -> 静止阻塞，调到外存
  3. 内存不够 且 时间片用完：运行态 -> 静止就绪，调到外存

A* a = new A; a->i = 10;在内核中的内存分配上发生了什么

可以首先介绍一下内存的模型 各个段的作用

  1. A *a 是一个局部指针变量，在栈区，开辟 4/8字节的空间分配给指针
  2. new A 是动态内存分配，在堆区分配，大小为类A的大小
  3. 将指针 a 的内存区域填入栈中类A申请到的地址的地址。即指针指向 new 分配的地址
  4. a->i：先找到指针a的地址 0x000m，通过a的值 0x000n和i在类a中偏移offset，得到a->i的地址0x000n + offset，进行*(0x000n + offset) = 10的赋值操作，即内存0x000n + offset的值是10

给你一个类，里面有static，virtual，之类的，来说一说这个类的内存分布

static修饰成员变量…. 在全局数据区分配内存；static修饰成员函数…..在代码区

如果一个类是局部变量则该类数据存储在栈区，如果一个类是通过new/malloc动态申请的，则该类数据存储在堆区。对于含有虚函数的对象，在首地址处有个虚函数表指针，指针指向了该类的虚函数表，虚函数表是个数组一样的表里面每一项存放的是该类的虚函数地址（虚函数指针），虚函数表存放在 代码段中的只读数据区，虚函数表中的函数指针指向的是代码段中的虚函数。

软链接和硬链接区别

链接除了解决了文件共享的问题，还可以隐藏文件的原本路劲，节省空间，提高安全性等。硬链接相当于一个 inode 有不同的文件名，删除源文件，文件实际不会从系统上删除，引用依然有效。软链接相当于创建了一个新的文件，新的 inode 只不过存储的是指向的文件的路径，使用 ln -s 创建，删除源文件，软连接就失效了。

什么是大端小端以及如何判断大端小端

大端是低字节存在高地址，小端是低字节存在低地址。联合体变量总是从低地址往高地址存储，所以使用联合体判断

1
2
3
4
5
6
7
8
9
10
union Test{
    int i;
    char a;
}
int main(){
	Test t;
    t.i = 0;
    t.i = 1;
    return (t.a == 1);  // 如果 a == 1 说明int的低地址存放的是 低字节 是小端
}

静态变量什么时候初始化

对于C语言，不存在类的构造问题，静态变量存放在 全局数据区，在编译时就可以初始化；而 c++ 的静态对象存在构造问题，全局静态对象在 main函数执行之前初始化，局部静态对象在第一次使用的时候初始化。

用户态和内核态区别

是操作系统的两种运行级别，二者权限不同。用户态的权限级别最低，运行在用户态的程序不能直接访问操作系统的数据结构，只能通过系统调用，异常（例如缺页异常），中断从用户态转向内核态。

两个进程访问临界区资源，会不会出现都获得自旋锁的情况？

???

单核cpu，并且开了抢占可以造成这种情况。

windows消息机制知道吗，请说一说

当用户有操作(鼠标，键盘等)时，系统会将这些时间转化为消息。每个打开的进程系统都为其维护了一个消息队列，系统会将这些消息放到进程的消息队列中，而应用程序会循环从消息队列中取出来消息，完成对应的操作。

C++的锁你知道几种?

锁包括互斥锁，自旋锁和读写锁, RCU锁

说一说你用到的锁

生产者消费者问题利用互斥锁和条件变量可以很容易解决，条件变量这里起到了替代信号量的作用

内存溢出和内存泄漏

内存溢出：指程序申请内存时，没有足够的内存供申请者使用。内存溢出就是你要的内存空间超过了系统实际分配给你的空间，此时系统相当于没法满足你的需求，就会报内存溢出的错误

  • 内存中加载的数据量过于庞大，如一次从数据库取出过多数据
  • 集合类中有对对象的引用，使用完后未清空，使得不能回收
  • 代码中存在死循环或循环产生过多重复的对象实体
  • 启动参数内存值设定的过小
  • 使用的第三方软件中的BUG

内存泄漏：内存泄漏是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。

  • 堆内存泄漏：
  • 系统内存泄漏：
  • 虚函数：

你都使用什么线程模型

OPEN MP

Future模型：Future是把结果放在将来获取，当前主线程并不急于获取处理结果。允许子线程先进行处理一段时间，处理结束之后就把结果保存下来，当主线程需要使用的时候再向子线程索取。在 c++ 中 使用 pakage_task 类 对可执行对象封装后 可以返回一个 future 对象，通过future 对象可以异步的获取 可执行对象在其他线程中执行后返回的结果。在线程池的实现中，就是通过 package_task 对函数和参数进行统一封装后返回future对象，用于异步获取任务的执行结果。

fork&join模型：该模型就是 递归的将一个大任务拆解为小任务。然后由单独的线程分别执行小任务，当每个子线程执行结束之后逐级回溯，返回结果进行汇总合并，最终得出想要的结果。在图像分块多线程中采用了fork join 的思路，最大线程数预先根据cpu核心数设置，如果输入图像大于1000 就分四个线程分别处理。让后汇总结果进入下一步。

actor模型：actor模型属于一种基于消息传递机制并行任务处理思想，它以消息的形式来进行线程间数据传输，避免了全局变量的使用，进而避免了数据同步错误的隐患。actor在接受到消息之后可以自己进行处理，也可以继续传递（分发）给其它actor进行处理。在使用actor模型的时候需要使用第三方Akka提供的框架。

生产者消费者模型：生产者消费者模型都比较熟悉，其核心是使用一个缓存来保存任务。开启一个/多个线程来生产任务，然后再开启一个/多个来从缓存中取出任务进行处理。这样的好处是任务的生成和处理分隔开，生产者不需要处理任务，只负责向生成任务然后保存到缓存。而消费者只需要从缓存中取出任务进行处理。使用的时候可以根据任务的生成情况和处理情况开启不同的线程来处理。比如，生成的任务速度较快，那么就可以灵活的多开启几个消费者线程进行处理，这样就可以避免任务的处理响应缓慢的问题。（线程池就是采用了这个模型，生产者为用户，用户通过GUI线程像 任务队列中放置 地标，多个消费者从 任务队列中取任务完成）

master-worker模型：master-worker模型类似于任务分发策略，开启一个master线程接收任务，然后在master中根据任务的具体情况进行分发给其它worker子线程，然后由子线程处理任务。如需返回结果，则worker处理结束之后把处理结果返回给master。

说一下微内核与宏内核

宏内核：除了最基本的进程、线程管理、内存管理外，将文件系统，驱动，网络协议等等都集成在内核里面，例如linux内核。

  • 优点：效率高。
  • 缺点：稳定性差，开发过程中的bug经常会导致整个系统挂掉。

微内核：内核中只有最基本的调度、内存管理。驱动、文件系统等都是用户态的守护进程去实现的。

  • 优点：稳定，驱动等的错误只会导致相应进程死掉，不会导致整个系统都崩溃
  • 缺点：效率低。典型代表QNX，QNX的文件系统是跑在用户态的进程，称为resmgr的东西，是订阅发布机制，文件系统的错误只会导致这个守护进程挂掉。不过数据吞吐量就比较不乐观了。

说一下僵尸进程

  • 正常进程：父进程和子进程是异步的，就是父进程在创建子进程后，子进程什么时候结束，运行到什么状态，父进程是不知道的。Unix中，子进程退出后，除了会释放子进程占用的系统资源，但是会保留子进程的进程号，退出状态，运行时间等这种基本信息。父进程可以通过 waitpid() 系统调用来获得这个信息，调用子进程信息才会完全从内核中删除。

  • 孤儿进程：就是父进程提前退出，子进程会被init初始进程托管，并在子进程退出后由它代为处理最后的信息。

  • 僵尸进程：就是子进程退出后，父进程未调用 waitpid 系统调用 获取 子进程的状态信息，那么子进程的进程描述符仍然保存在系统中，占用着进程号。

    • 因为系统的进程号是有限的，用完后就无法创建新的进程。
    • 僵尸进程是每个进程必经的阶段
    • 可以同过 ps 命令查看 进程，状态为 Z 的就是僵尸进程，可以通过 kill 命令清楚
    • 子进程在 退出的时候可以向父进程发送信号，告诉它及时处理，或者 fork 两次让他变成孤儿进程由init 进程接管

守护进程(daemon)是一类在后台运行的特殊进程，用于执行特定的系统任务。很多守护进程在系统引导的时候启动，并且一直运行直到系统关闭。

请问GDB调试用过吗，什么是条件断点

5种IO模型

  1. 阻塞式I/O：如果当前进程获取不到I/O时间，就进入休眠状态，会阻塞当前线程的其他任务，但是并不会增加cpu的负担
  2. 非阻塞式：类似于轮询，隔段时间检查一下时间是否就绪，中途可以区处理别的事物。但是反复轮询会降低cpu效率
  3. 多路复用：多路复用和阻塞式类似，也会阻塞当前线程，但是在一个线程中可以管理多个IO事件，原理就是统一管理一批文件描述符，当其中某一个有响应后就处理。
  4. 信号驱动：应用程序使用套接口进行信号驱动I/O，并安装一个信号处理函数，进程继续运行并不阻塞。当数据准备好时，进程会收到一个SIGIO信号，可以在信号处理函数中调用I/O操作函数处理数据
  5. 异步式：信号驱动I/O是由内核通知应用程序何时启动一个I/O操作，而异步I/O模型是由内核通知应用程序I/O操作何时完成

如何设计server，使得能够接收多个客户端的请求

多线程，线程池，io复用

死循环+来连接时新建线程的方法效率有点低，怎么改进？

提前创建好一个线程池，用生产者消费者模型，创建一个任务队列，队列作为临界资源，有了新连接，就挂在到任务队列上，队列为空所有线程睡眠。改进死循环：使用select epoll这样的技术

怎么实现线程池

  1. 设置一个生产者消费者队列，作为临界资源
  2. 初始化n个线程，并让其运行起来，加锁去队列取任务运行
  3. 当任务队列为空的时候，所有线程阻塞
  4. 当生产者队列来了一个任务后，先对队列加锁，把任务挂在到队列上，然后使用条件变量去通知阻塞中的一个线程

内存池

内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。

动态链接库与静态链接库的区别

如果可执行文件使用静态库编译，那么编译的时候会将静态库中的可执行代码编译进可执行文件中，而动态库是在程序运行时才加载的。

因此区别是：

  1. 使用静态库编出的可执行文件更大，但是运行执行效率更高。而动态库需要运行时加载所以慢一点
  2. 动态库是系统中所有进程共享的，如果两个程序使用了相同的动态库，那么只需加载进内存中一次，而使用静态库编译的文件则在每个程序中都有一份实现，因此动态库更节省内存
  3. 动态库方便后续维护，如果需要更新功能，更换动态库即可不用重新编译可执行文件，而静态库不行
  4. 静态库中不能再包含其他动态或静态库，而动态库可以

C语言函数调用的原理

image-20210617224928241

函数调用流程如下：

  1. 首先要将当前PC设置为下调用函数的下一条指令，便于调用完毕后返回。同时将PC设置为子函数地址
  2. 还要将调用者栈帧的 栈底 bp 指针压入栈中, 并将 sp 指针赋给 bp ， 即当前栈顶为子函数的栈底
  3. 将调用函数的入口参数 从右到左 依次入栈
  4. 通过PC跳转执行，最后返回值 可以通过eax保存，具体的返回值保存方法
    • 返回值类型的，如果所用内存较大 eax 寄存器无法直接保存下，那就预先在栈上开辟一个空间，然后将变量的地址作为第一个隐含的函数入口参数传入函数中；否则直接用 eax cpu寄存器作为媒介返回。

分页和分段存储管理有何区别

  1. 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
  2. 页的大小固定且由系统决定；而段的长度却不固定，决定于用户所编写的程序。
  3. 分页的地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

多重继承虚函数怎么实现

如果继承自多个类，并且每个类都有虚函数，那么实例化后的对象 就有N个虚表指针；如果虚表中最后一个是 星号 代表还有下一个虚表，否则无。

C++原子类型如何实现

  1. 单核系统中 简单的关中断 屏蔽任务调度即可
  2. 在多核系统中 不仅如此还存在多个核的缓存不一致性的问题 ，还需要结合CAS实现 原子操作。CAS一般有硬件指令级的支持，原理就是，首先从内存中读取要修改的变量，将他和期望值比较，如果和期望值不同，那么就说明它被修改了就什么都不做返回false，如果相同，则对变量修改并返回true。
1
2
3
4
5
6
7
8
9
// 比如我要执行 i++  首先是  从内存中读取 i 发现他等于 0 然后在cpu缓存中执行+1为1后要把它写回内存，这时候 CAS 作用就来了，如果回写的时候，我先读一遍发现 i 不是 0 而是 其他值，说明在我执行i+1过程中有其他人修改了内存值，因此此时 返回false 不能将自己cpu中缓存的1写给i；
bool compare_and_swap (int*accum, int*dest, intnewval)
{
  if( *accum == *dest ) {
      *dest = newval;
      return true;
  }
  return false;
}

进程调度算法详解

多个线程轮流打印1-100

思路

  1. 通过一个变量来控制线程同步的逻辑
  2. 如果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
std::mutex mtx;
std::condition_variable cv;
int ready = 0;
void PrintString_1()
{
    std::unique_lock<std::mutex> lk(mtx);
    int cnt = 0;
    while(cnt<10)
    {
        while(ready != 0)
            cv.wait(lk);
        std::cout<<"A"<<std::endl;
        ready = 1;
        cnt++;
        cv.notify_all();
    }
}

void PrintString_2()
{
    std::unique_lock<std::mutex> lk(mtx);
    int cnt = 0;
    while(cnt<10)
    {
        while(ready != 1)
            cv.wait(lk);
        std::cout<<"B"<<std::endl;
        ready = 2;
        cnt++;
        cv.notify_all();
    }
}

void PrintString_3()
{
    std::unique_lock<std::mutex> lk(mtx);
    int cnt = 0;
    while(cnt<10)
    {
        while(ready != 2)
            cv.wait(lk);
        std::cout<<"C"<<std::endl;
        ready = 0;
        cnt++;
        cv.notify_all();
    }
}
int main()
{
    std::thread  t1(PrintString_1);
    std::thread  t2(PrintString_2);
    std::thread  t3(PrintString_3);
    t1.join();
    t2.join();
    t3.join();
    return 0;
}

inline 和 define区别

define 是预处理阶处理的，只是简单的替换，并没有入口参数类型检查啥的。而Inline 在编译阶段将代码段直接擦插入到每个调用它的地方，但是并不是函数调用的形式，因此效率比较高且安全可靠 是一种空间换时间的手段。

两个线程对一个int a = 1 的变量同时进行 a++ 操作一万次，那么最后a的值是多少呢

10000 - 20000 之间 考虑多线程冲突

什么是闭包 lambda表达式

c++11 中 匿名函数 可以实现闭包，但是概念上 闭包是指 包含函数指针和上下文数据环境的一个结构体，相当于捕获的上下文数据+函数地址。如果一个函数没有捕捉自由变量那么其实就可以实现为一个函数指针，如果捕获了自由变量，他就是一个闭包，当他脱离当前的环境，依然可以正常执行。c98中没有匿名函数，但是可以通过仿函数来模拟闭包。

因此匿名函数返回的就是一个匿名的闭包实例，他是个右值，可以通过捕获的方式封装当前作用域的变量或者他们的引用。

C++11 vector库中有什么改进

有了移动拷贝构造函数 避免了很多不必要的对象内存赋值

模板类和泛型编程

C++这种语言不像python javascript这种动态语言一样，一个函数可以传入任何类型的参数。C++的模板弥补了这个缺点，在定义函数或者类时可以将参数类型设置为模板，当调用的时候编译器再根据调用的类型去实例化对应的参数类型。优点是更灵活，大大减少代码量。缺点是 模板的定义和声明必须放在同一个文件中 这点和c++常规的定义声明分开编写的原则不同。

磁盘IO的原理

操作系统使用DMA直接将数据从 磁盘 拷贝到 页缓存中，或者将数据写回磁盘，这个过程不需要处理。但是将应用程序地址空间和内核空间之间的拷贝需要 CPU 开销。

序执行 内存屏障 voliate

Linux的字符集

读写锁的实现原理

C++死锁检测

操作系统的内存映射是如何实现的 （共享内存如何实现的）

共享内存能放什么样的数据结构，是用什么数据结构实现的

进程在操作系统的存在方式

epoll原理和类似的中间件之间的区别（select，poll）

消息队列内核是如何实现的

信号量Linux是如何实现的，如何进行进程的通信

信号了解吗，进程的信号通信底层是如何实现的

讲讲I/O模型

PV操作如何实现的

什么是中断

liunx下如何shell下查看cpu内存资源使用情况用什么命令

介绍一下IO多路复用

缓存的管理方式（LRU，LFU）

将一个文件从内存中写入磁盘，设计一种数据结构来加速这个过程

（应该是LSM树）

负载均衡算法

CPU流水线

缓存一致性协议

程序中通过地址读取一个变量的过程

（虚拟地址到物理地址，MMU，CR3，转换的细节，这里问了一个我不懂的名词，说是MMU获取页目录地址的过程）

进程优先级和CPU的任务调度策略（优先级反转）

高并发下同时操作任务队列

Linux

Linux命令 awk，strace，gdb调试相关

Linux常用命令

Linux与Windows最大的区别