面经个人总结

摘要:

暂无摘要

序章

  • 你有哪些特长
  • 对于项目:
    1. 这是一个怎样的项目
    2. 用到了什么技术,为什么用这项技术(以及每项技术很细的点以及扩展)
    3. 过程中遇到了什么问题,怎么解决的
  • 自我介绍
  • 可以提问的问题:部门的业务,实习生的培养机制

算法

  • 快速排序:当基准数选择最左边的数字时,那么就应该先从右边开始搜索;当基准数选择最右边的数字时,那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序!否则会得到错误的结果。最好情况是基准数选得好,每次都能等分数列时,复杂度为O(nlogn)。最差情况是已经正序或者逆序,复杂度为O(n^2)。平均为O(nlogn)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //从小到大(如果是从大到小,只需要将代码中两个不等号改一下)
    void quick_sort(int left, int right, vector<int> & arr){
    if(left >= right) {
    return;
    }
    int i = left, j = right, base = arr[left], temp;
    while(i < j) {
    while(arr[j] >= base && i < j) { //如果是从大到小需要将>=改成<=
    j--;
    }
    while(arr[i] <= base && i < j) { //如果是从大到小需要将<=改成>=
    i++;
    }
    if(i < j) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    }
    }
    arr[left] = arr[i];
    arr[i] = base;
    quick_sort(left, i - 1, arr);
    quick_sort(i + 1, right, arr);
    }
    • 冒泡排序

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      for (i = 0; i< N - 1; i++) { //控制n-1趟冒泡
      for (j = 0; j < N - 1 - i; j++)
      {
      if (a[j] > a[j + 1]) { //如果是降序,将>改成<即可
      int tmp;
      tmp = a[j];
      a[j] = a[j + 1];
      a[j + 1] = tmp;
      }
      }
      }

数据结构

  • hashmap原理:

    首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

    1. 得到key 
    2. 通过hash函数得到hash值 
    3. 得到桶号(一般都为hash值对桶数求模) 
    4. 存放key和value在桶内。 

    其取值过程是:

    1. 得到key 
    2. 通过hash函数得到hash值 
    3. 得到桶号(一般都为hash值对桶数求模) 
    4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。 
    5. 取出相等的记录的value。
  • 前序遍历,中序遍历,后序遍历

    前序遍历(根左右),中序遍历(左根右),后序遍历(左右根)

    中序遍历非递归算法:

    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
    //中序遍历
    void InOrderWithoutRecursion2(BTNode* root)
    {
    //空树
    if (root == NULL)
    return;
    //树非空
    BTNode* p = root;
    stack<btnode*> s;
    while (!s.empty() || p)
    {
    if (p)
    {
    s.push(p);
    p = p->lchild;
    }
    else
    {
    p = s.top();
    s.pop();
    cout << setw(4) << p->data;
    p = p->rchild;
    }
    }
    }
  • 二叉树,平衡二叉树

    平衡二叉树:节点的平衡因子是节点的左右子树的深度之差,平衡二叉树是任意节点的平衡因子的绝对值小于等于1的二叉树。

    平衡化旋转:插入一个新节点后,需要从插入的新节点处沿通向根的方向回溯,如果在某一节点发现不平衡,就从发生不平衡的节点起,沿刚刚回溯的路径取直接下两层的节点,进行旋转。

    • b树,b+树:减少IO,速度快

      b树:各节点中最多的数据存储量为阶。每个节点可以存多个数据

      b+树:非叶子节点只存放索引,所有的数据都在叶子节点。

      b+树优点:

    1. 每个非叶子节点只充当索引,单一节点存储的元素更多,相同的内存可以存放更多索引数据

    2. 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。

    3. 所有的叶子节点形成了一个有序链表,更加便于查找。

  • map与unordered_map

    map通过红黑树实现,自动有序。unordered_map通过hash实现,无序但是查找的时间复杂度为O(1)

    map费空间,unordered_map构建时比较慢

操作系统

  • 进程是一个程序在给定的活动空间和初始环境下,在一个处理机上的执行过程。

  • 进程的三个基本状态:运行状态,等待状态(进程正在等待某一事件的发生,即使给他CPU控制权也无法执行),就绪状态(万事俱备,只欠CPU)

    线程的状态变迁图是一样的

  • 线程是比进程更小的活动单位,他是进程中的一个执行路径。

  • 进程同步反应的是合作关系,一般有严格的执行顺序。进程互斥反应竞争关系

  • PV操作:P操作,若相减结果为负值,则进程被阻,并插入该进程到等待队列。V操作,相加结果大于零,进程继续,否则唤醒等待队列中的一个进程

  • 进程与线程的关系

    1. 线程是进程中的一条执行路径
    2. 单个进程可以创建多个同时存在的线程
    3. 每个线程都有自己私用的堆栈和处理执行环境
    4. 同一进程中的多个线程共享分配给该进程的内存
  • fork()返回-1表示创建失败,返回0为从子进程返回,返回值>0为从父进程返回,返回值为子进程号

  • 进程调度算法:

    1. 先来先服务
    2. 短作业优先
    3. 最短剩余时间优先
    4. 时间片轮转
    5. 优先级调度
  • 中断

    中断是指CPU对系统发生的某个事件做出的一种反应,CPU暂停正在执行的程序,保存现场后自动去执行相应的处理程序,处理完该事件后再返回中断处继续执行原来的程序。中断一般三类,一种是由CPU外部引起的,如I/O中断、时钟中断,一种是来自CPU内部事件或程序执行中引起的中断,例如程序非法操作,地址越界、浮点溢出),最后一种是在程序中使用了系统调用引起的。而中断处理一般分为中断响应和中断处理两个步骤,中断响应由硬件实施,中断处理主要由软件实施。

  • 栈帧

    栈帧表示程序的函数调用记录,而栈帧又是记录在栈上面,很明显栈上保持了N个栈帧的实体,那就可以说栈帧将栈分割成了N个记录块,但是这些记录块大小不是固定的,因为栈帧不仅保存诸如:函数入参、出参、返回地址和上一个栈帧的栈底指针等信息,还保存了函数内部的自动变量(甚至可以是动态分配内存,alloca函数就可以实现,但在某些系统中不行),因此,不是所有的栈帧的大小都相同。下面通过一个简单的实例,来分析栈帧的记录活动

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void func(int m, int n) {
    int a, b;
    a = m;
    b = n;
    }
    main() {
    ...
    func(m, n);
    L: 下一条语句
    . ..
    }

    这里的main函数只是简单调用了一个函数func,那么在main调用func函数前,栈的情况是下面这个样子的:

    此时栈中只有一个main函数的栈帧,从低地址esp(栈顶指针)到高地址ebp(栈帧栈底指针)的这块区域,就是当前main函数的栈帧。当main中调用func时,写成汇编大致是:

    push m
    
    push n; 两个参数压入栈
    
    call func; 调用func,将返回地址(实际上是当前PC值的下一个值)填入栈,并跳转到func。

    当成功跳转到func函数中时,func函数的栈帧就已经形成了,但是形成新的栈帧之前,必须要重新记录当前栈帧的栈底指针ebp,下面的保存和切换ebp的几个动作是由系统自动完成的。

    1. push ebp; 函数调用之所以能够返回,单靠保持返回地址是不够的,这一步压栈动作很重要,因为我们要标记函数调用者栈帧的帧 底,这样才能找出保存了的返回地址,栈顶是不用保存的,因为上一个栈帧的顶部讲会是func的栈帧底部。(两栈帧相邻的)

    2. mov ebp, esp; 上一栈帧的顶部,就是这个栈帧的底部 ;

      暂时先看现在的栈的情况

      接下来就是func里面的临时变量局部变量入栈。

  • 虚拟内存

    虚拟内存的基本思想是:在程序装入时,可以将程序的一部分装入内存,而将其余部分留在外存,就可以启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。

    理论依据是程序的局部性

  • 页式系统:

    虚页:程序的地址空间被分成大小相等的片,称为虚页。

    实页:内存被分为大小相等的块,称为实页。

    页表:记录页与内存块之间的映射关系

    页式地址变换步骤:

    1. 首先CPU给出逻辑地址

    2. 逻辑地址的高几位对应虚页号,剩余的第几位为页内偏移地址

    3. 去页表缓存中看看是否有虚页号对应的块号,如果有,执行5;如果没有,执行4。

    4. 去页表中查找虚页号对应的块号(实页号)

    5. 将块号和页内偏移地址组合形成物理地址

      页面淘汰算法:OPT LRU FIFO 时钟

  • 段页式系统:

    分段是程序中自然划分的一组逻辑意义完整的信息集合,段长可变,依据逻辑划分。

    段页式系统是在一个分段内划分页面。

  • 大端模式和小端模式

    大端:是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中

    小端:是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中

  • 编译过程

  • 动态链接与静态链接

    静态链接:静态链接的时候,载入代码就会把程序会用到的动态代码或动态代码的地址确定下来,静态库的链接可以使用静态链接,动态链接库也可以使用这种方法链接导入库。

    动态链接:使用这种方式的程序并不在一开始就完成动态链接,而是直到真正调用动态库代码时,载入程序才计算(被调用的那部分)动态代码的逻辑地址,然后等到某个时候,程序又需要调用另外某块动态代码时,载入程序又去计算这部分代码的逻辑地址,所以,这种方式使程序初始化时间较短,但运行期间的性能比不上静态链接的程序

    简单的说,静态库和应用程序编译在一起,在任何情况下都能运行,而动态库是动态链接,顾名思义就是在应用程序启动的时候才会链接,所以,当用户的系统上没有该动态库时,应用程序就会运行失败。再看它们的特点:

    动态库:

    1.共享:多个应用程序可以使用同一个动态库,启动多个应用程序的时候,只需要将动态库加载到内存一次即可

    2.开发模块好:要求设计者对功能划分的比较好。

    3.采用动态链接的程序比静态链接的初始化速度更快,但是执行期间的性能更差

    静态库:代码的装载速度快,执行速度也比较快,因为编译时它只会把你需要的那部分链接进去,应用程序相对比较大。但是如果多个应用程序使用的话,会被装载多次,浪费内存

  • 进程通信

    1. 消息缓存通信(管道):在内存中开设缓冲区,发送进程将消息送入缓冲区,接收进程接受传递来的缓冲区

      无名管道:半双工,只能在有亲缘关系的进程间使用

      命名管道,半双工,可以在没有亲缘关系的进程间使用

    2. 消息队列:消息的链表

    3. 共享内存

    4. 信号量

    5. 套接字:一般用于不同主机之间进程的通信

  • C++线程通信:信号量,全局变量

计算机网络

  • TCP报文头:固定长度20字节+可变长度

    序列号:表示本报文段所发送数据的第一个字节的编号

    确认号:表示接收方期望收到发送方下一个报文段的第一个字节数据的编号

    数据偏移:由于TCP首部包含一个长度可变的选项部分,需要指定这个TCP报文段到底有多长

    ACK:表示前面确认号字段是否有效。只有当ACK=1时,前面的确认号字段才有效。TCP规定,连接建立后,ACK必须为1,带ACK标志的TCP报文段称为确认报文段

    SYN:在建立连接时使用,用来同步序号。当SYN=1,ACK=0时,表示这是一个请求建立连接的报文段;当SYN=1,ACK=1时,表示对方同意建立连接。SYN=1,说明这是一个请求建立连接或同意建立连接的报文。只有在前两次握手中SYN才置为1,带SYN标志的TCP报文段称为同步报文段

    FIN:表示通知对方本端要关闭连接了,标记数据是否发送完毕。

    最下面的长条是一个IP数据报,tcp报文是包含在IP数据报中的,并且是IP数据报的数据部分,tcp报文段只指定端口,具体与哪个机器通信会由IP首部中的ip地址指定。

    IP首部示意图:

    首部的前一部分是固定长度,和TCP报文同样是20字节,是所有IP数据报必须具有的。在首部的固定部分的后面是一些可选字段,其长度是可变的。

  • TCP的三次握手,为什么要三次握手

  • TCP去掉第三次握手会怎么样?

    如果仅两次连接可能出现一种情况:客户端发送完连接报文(第一次握手)后由于网络不好,延时很久后报文到达服务端,服务端接收到报文后向客户端发起连接(第二次握手)。此时客户端会认定此报文为失效报文,但在两次握手情况下服务端会认为已经建立起了连接,服务端会一直等待客户端发送数据,但因为客户端会认为服务端第二次握手的回复是对失效请求的回复,不会去处理。这就造成了服务端一直等待客户端数据的情况,浪费资源。

    另外一个角度:由于网络环境不好,客户端发送的连接请求过了很久才抵达服务端,这个连接请求此时实际上已经失效了。如果只有两次握手,那么服务端回复了这个失效的连接请求后,就会认为连接已经成功建立,并会一直等待客户端发来数据,这就导致服务端资源浪费。宏观一点讲,在网络中存在很多的失效的连接请求,服务端收到的请求中夹杂着失效的和有效的,服务端需要判断收到的请求到底有没有效,方法就是第三次握手,相当于问问客户端,“”这真的是你刚刚发送的有效请求吗?”

  • TCP的四次挥手(实际上就是终止TCP连接的过程)

    图中当server端收到client的断开请求时,可能涉及到传输的数据没有传完,因此server端不会立即同意断开请求,可以继续给client端发送数据。此阶段数据传输是单向的(半双工,半关闭)
    TIME-WAIT作用:

    1. 当server端同意断开请求连接时,client的网络状态并未立即切换,因为先发的报文并不一定比server同意断开请求先到,需要等待2MSL(报文最长存活时间)时间,确认server端的数据全部接收后,才会改变网络状态。一个MSL大概几十秒。
    2. 为了保证客户端发送的最后一个ACK报文段能够到达服务器。因为这个ACK有可能丢失,从而导致处在LAST-ACK状态的服务器收不到对FIN-ACK的确认报文。服务器会超时重传这个FIN-ACK,接着客户端再重传一次确认,重新启动时间等待计时器。最后客户端和服务器都能正常的关闭。假设客户端不等待2MSL,而是在发送完ACK之后直接释放关闭,一但这个ACK丢失的话,服务器就无法正常的进入关闭连接状态
  • http状态码

    200请求成功 301资源被永久转移到其他URL 404请求的资源未找到 400客户端请求的语法错误,服务器无法理解 401要求用户进行身份认证 403服务器理解客户端请求但是拒绝此请求 505服务器不支持请求的HTTP版本

  • 网络层传输数据的基本单元我们称为数据报,运输层传输数据的基本单元我们称作报文段

  • 为什么tcp为什么要建立连接

    保证数据的可靠传输

  • TCP与UDP的区别:前者建立连接,后者不。前者可靠,后者尽力而为。前者面向字节流,后者面向报文。TCP比UDP传输的数据量更大。UDP比TCP更快。

  • cookie:HTTP使用了cookie。HTTP响应报文中会有一个cookie首部行,HTTP请求报文中也会有一个cookie首部行,客户端会有一个cookie文件,由浏览器来管理,服务端会有一个后端数据库。小明访问亚马逊,发送一个HTTP请求,服务器返回的响应报文首部会给一个cookie号,服务器和浏览器都会记下这个cookie号,服务器会将这个号码与小明的信息绑定,存到数据库里面,之后小明再次访问亚马逊时,就会在自己的HTTP请求中加上这个cookie号,服务器之后就会认识这个号码,并从数据库中找到这个用户的信息。

  • DNS

    DNS缓存 -> 本地hosts文件 -> 向DNS服务器请求一个DNS查询(DNS查询一般使用UDP,因为快)

    发送DNS查询报文时,主机首先向本地的DNS服务器发送一个DNS查询报文,之后本地DNS服务器将这个查询报文转发到根DNS服务器,并得到下一级DNS服务器的IP,接着本地DNS服务器再向下一级DNS服务器发送查询请求,就这样一级一级向下查询,主体都是本地DNS服务器,最后查到之后,本地DNS服务器再将IP地址发送给主机

  • 浏览器中输入URL到页面返回的全过程

    大致分为8步

    1.根据域名,进行DNS域名解析;

    2.拿到解析的IP地址,建立TCP连接;

    3.向IP地址,发送HTTP请求;

    4.服务器处理请求;

    5.返回响应结果;

    6.关闭TCP连接;

    7.浏览器解析HTML;

    8.浏览器布局渲染;

  • HTTP1.0与HTTP1.1的区别:HTTP 1.0规定浏览器与服务器只保持短暂的连接,一个TCP连接对应一个HTTP请求,浏览器的每次请求都需要与服务器建立一个TCP连接,服务器完成请求处理后立即断开TCP连接,这会导致性能缺陷。例如一个包含有许多图像的网页文件中并没有包含真正的图像数据内容,而只是指明了这些图像的URL地址,当WEB浏览器访问这个网页文件时,需要多次建立TCP连接,非常耗时。HTTP 1.1支持持久连接,一个TCP连接可以对应多个HTTP请求

  • HTTP1.1与HTTP2.0的区别:

    HTTP1.1:若干个请求排队串行化单线程处理,后面的请求等待前面请求的返回才能获得执行机会,一旦有某请求超时等,后续请求只能被阻塞,毫无办法,也就是人们常说的线头阻塞;

    HTTP2.0:多个请求可同时在一个连接上并行执行。某个请求任务耗时严重,不会影响到其它连接的正常执行;

    多说一句:如果需要请求的页面上有很多图片,在HTTP1.1时代,虽然有piprlining技术,但是不好用所以一般被关闭,通常通过建立多个tcp连接来加速(例如chrome限定对于同一个页面最多开6个TCP),而在HTTP2.0时代,可以在一个TCP连接上同时发送多个HTTP请求

  • HTTPS

    http://www.360doc.com/content/20/0319/11/835902_900290660.shtml

    HTTPS在传输数据时用的是对称加密,只有在验证证书时用的是非对称加密。数据传输过程采用对称加密原因有二:首先是因为非对称加密效率太低,另外非对称加密是单向的,不适用于网络传输场景。

    为什么需要CA认证机构颁发证书?如果没有证书,可能会带来”中间人问题“,过程为,本地请求被中间人服务器劫持,中间人服务器向客户端发送自己未被验证过的证书,客户端会与中间人完成之后的HTTPS流程,此时中间人就已经有了客户端发出的随机数。接着中间人以客户端的请求向正规网站发出请求,理所当然被正常响应。中间人将拿到的数据进行加密,返回给客户端。虽然客户端也拿到了自己想要的数据,但是过程中所有的传输内容都被中间人窃取。

  • TCP拥塞控制(Reno)

    1. 当拥塞窗口小于门限值时,发送方处于慢启动阶段,窗口以指数速度增大
    2. 当拥塞窗口大于门限值时,发送方处于拥塞避免阶段,窗口线性增大
    3. 当收到三个重复的ACK时,门限值设为拥塞窗口的一半,而拥塞窗口设为门限值+3MSS(报文段数据部分的最大长度)
    4. 当超时事件发生时,门限值设为拥塞窗口的一半,而拥塞窗口设为一个MSS
  • TCP重传机制

    快速重传(三个冗余ACK)与超时重传

  • 流量控制:接收方在反馈时,将缓冲区剩余空间大小填充在报文段首部的窗口字段中,通知发送方

  • HTTP报文头有多少个字节

  • TCP可靠性的保证:序号 ACK 超时重传 流量控制 拥塞控制 三握四挥

  • OSI七层模型

    物理层: 通过媒介传输比特,确定机械及电气规范,传输单位为bit,主要包括的协议为:IEE802.3 CLOCK RJ45

    数据链路层: 将比特组装成帧和点到点的传递,传输单位为帧,主要包括的协议为MAC VLAN PPP

    网络层:负责数据包从源到宿的传递和网际互连,传输单位为包,主要包括的协议为IP ARP ICMP OSPF BGP

    传输层:提供端到端的可靠报文传递和错误恢复,传输单位为报文,主要包括的协议为TCP UDP

    会话层:建立、管理和终止会话,传输单位为SPDU,主要包括的协议为RPC NFS

    表示层: 对数据进行翻译、加密和压缩,传输单位为PPDU,主要包括的协议为JPEG ASII

    应用层: 允许访问OSI环境的手段,传输单位为APDU,主要包括的协议为FTP HTTP DNS

  • 网络层的几个协议

    • ICMP:ICMP主要用来发送错误报文,在某个位置,IP路由器不能找到一条通往HTTP请求中所指定的主机的路径,该路由器就会向你的主机生成并发送一个ICMP报文以指示这个错误
    • OSPF:使用OSPF时,一台路由器构建了一个关于整个自治系统的完整拓扑图,于是每台路由器在本地执行Dijkstra算法找到通向自治区域内每一个子网的最短路径。OSPF主要用于自治区域内的路由。
    • BGP:主要用于自治区域之间的选路。自治区域内的路由器通过iBGP连接,相邻两个自治区域的网关路由器通过eBGP连接。BGP可以用来通报不同的自治区域之间的某一子网的可达性信息。

数据库

  • mysql事务隔离级别

    未授权读取

    也称为读未提交(Read Uncommitted):允许脏读取,但不允许更新丢失。如果一个事务已经开始写数据,则另外一个事务则不允许同时进行写操作,但允许其他事务读此行数据。该隔离级别可以通过“排他写锁”实现。

    授权读取

    也称为读提交(Read Committed):允许不可重复读取,但不允许脏读取。读取数据的事务允许其他事务继续访问该行数据,但是未提交的写事务将会禁止其他事务访问该行。可以通过“瞬间共享读锁”和“排他写锁”实现。

    可重复读取(Repeatable Read)

    禁止不可重复读取和脏读取,但是有时可能出现幻读数据。读取数据的事务将会禁止写事务(但允许读事务),写事务则禁止任何其他事务。可以通过“共享读锁”和“排他写锁”实现。

    序列化(Serializable)

    提供严格的事务隔离。它要求事务序列化执行,事务只能一个接着一个地执行,不能并发执行。仅仅通过“行级锁”是无法实现事务序列化的,必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。

  • 事务:是指作为单个逻辑工作单元执行的一系列操作,要么完全地执行,要么完全地不执行。事务具有4个基本特征,分别是:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Duration),简称ACID。

    1)原子性(Atomicity)

    原子性是指事务包含的所有操作要么全部成功,要么全部失败回滚,因此事务的操作如果成功就必须要完全应用到数据库,如果操作失败则不能对数据库有任何影响。

    2)一致性(Consistency)

    一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态,也就是说一个事务执行之前和执行之后都必须处于一致性状态。

    拿转账来说,假设用户A和用户B两者的钱加起来一共是5000,那么不管A和B之间如何转账,转几次账,事务结束后两个用户的钱相加起来应该还得是5000,这就是事务的一致性。

    3)隔离性(Isolation)

    隔离性是当多个用户并发访问数据库时,比如操作同一张表时,数据库为每一个用户开启的事务,不能被其他事务的操作所干扰,多个并发事务之间要相互隔离。

    4)持久性(Durability)

    持久性是指一个事务一旦被提交了,那么对数据库中的数据的改变就是永久性的,即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。

  • 并发操作可能带来的数据不一致性:

    1. 丢失更新:两个以上事务从DB中读入同一数据并修改, 其中一事务(后提交的事务)的提交结果破坏 了另一事务(先提交的事务)的提交结果,导 致先前提交事务对DB的修改被丢失
    2. 读脏:事务1修改某一数据,并将其写回磁盘。事务2读取同一数据后,事务1由于某种原因被撤消. 这时事务1已修改过的数据被恢复原值。事务2读到的不稳定的瞬间数据就与数据库中的数 据不一致,是不正确的数据,又称为“脏”数据
    3. 不接重复读:事务1读取数据后,事务2执行更新操作,使事务1无 法再现前一次读取结果
  • 封锁:X锁(写锁)和S锁(读锁)

  • 三级封锁协议:事务T在修改数据R之前必须先对其加X锁,直 到事务结束才释放;事务T在读取数据R前必须先加S 锁,直到事务结束才释放

  • 三级封锁协议太严格,就又有了两段锁协议的内容

    1. 在对任何数据进行读、写操作之前,事务首先要 获得对该数据的封锁;

    2. 在释放一个封锁之后,事务不再获得任何其他封 锁。

  • 数据库索引,哪些地方需要索引,是否越多越好

    索引是一种数据结构,存储的是表上某一列的值以及这个值所在的那一行的地址。使用索引的全部意义就是通过缩小一张表中需要查询的记录/行的数目来加快搜索的速度。索引并非越多越好,无用的索引反而会拉低性能。

    1
    2
    CREATE INDEX name_index
    ON Employee (Employee_Name)
  • mysql的索引主要是B+树索引。为什么不用B树呢?B树的两个主要特点,一个是树内存储数据,另一个是叶节点之间没有指针相连;而B+树的两个主要特点,一个是数据全都存储在叶子节点,另外叶子节点全都用链表连在一起。数据库索引采用B+ tree的主要原因是B Tree在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+ tree应运而生。B+ tree只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,如果使用B Tree,则需要做局部的中序遍历,可能要跨层访问,效率太慢。

  • 常见的MySQL主要有两种结构:Hash索引和B+ Tree索引,我们使用的是InnoDB引擎,默认的是B+树。B+ Tree索引和Hash索引区别 哈希索引适合等值查询,但是不无法进行范围查询 哈希索引没办法利用索引完成排序,如果有大量重复键值得情况下,哈希索引的效率会很低,因为存在哈希碰撞问题。而B+ Tree是一种多路平衡查询树,所以他的节点是天然有序的(左子节点小于父节点、父节点小于右子节点),所以对于范围查询的时候不需要做全表扫描。

  • 聚簇索引和非聚簇索引:聚簇索引就是按照每张表的主键构造一颗B+树,同时叶子节点中存放的就是整张表的行记录数据,这个特性决定了索引组织表中数据也是索引的一部分,每张表只能拥有一个聚簇索引。聚簇索引的查询速度更快,因为索引树的叶子节点直接就是我们要查询的整行数据了。而非聚簇索引的叶子节点是主键的值,还需要根据主键值回表查询。

C++

  • 面向对象三大特点:封装 继承 多态

    封装即将客观事物封装成抽象的类,并且把私密数据进行隐藏,并提供一些公有接口

  • 重载与重写

    重载是指函数名字相同,参数列表不同。重写是指对父类的虚函数进行重新定义,函数名和参数列表都必须相同。所以说多态是通过重写来实现的。

  • 多态:发生多态的条件是,父类指针或引用指向子类对象,虚函数重写

  • 静态联编与动态联编:将源代码中的函数调用解释为执行特定的函数代码块称为函数名联编。在编译过程中进行联编称为静态联编,在程序运行时进行联编称为动态联编。如果使用虚函数则为动态联编。同样是基类指针或者引用指向子类对象,如果调用的函数没有声明为虚函数,则是静态联编。

  • 虚函数

    经常在基类中将派生类会重新定义的方法声明为虚方法。

    如果方法是通过引用或者指针调用的按下面的规则确定使用的是哪一个方法:如果方法没有使用关键字virtual,程序将根据引用类型或者指针类型来选择方法,如果使用了virtual,程序将根据指针或者引用指向的对象的类型来选择方法。

  • 虚函数的工作原理:给每个对象增加一个隐藏成员,隐藏成员中保存了一个指向虚函数表的指针,虚函数表是一个数组,数组中记录的是这个对象的虚函数们的地址。无论类中有多少个虚函数,其对象中都只有一个这个隐藏成员,区别只是这个成员指向的表的大小不同。调用虚函数时,程序将查看存储在对象中的虚函数表地址,然后得到相应虚函数的地址。类声明中定义的第n个虚函数,将位于虚函数表(数组)的第n个元素。

  • 虚析构函数:析构函数应该是虚函数,除非类不用作基类。虚析构函数是为了解决父类指针指向子类对象时,释放子类对象的资源时,释放不完全,造成的内存泄漏问题。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Father{
    public:
    Father(){}
    virtual ~Father(){
    std::cout << "~father" << std::endl;
    }
    }

    class Son{
    public:
    Son(){}
    virtual ~Son(){
    std::cout << "~Son" << std::endl;
    }
    }

    int main(){
    Father *demo = new Son();
    delete demo;
    }

    如果加上virtual,则delete demo的时候会先调用~Son()再调用~Father()。如果没有virtual,由于demo是Father指针,所以只调用~Father()。

  • new与malloc的区别

    1. 申请的内存所在的位置

      new操作符从自由存储区(free store)上为对象动态分配内存空间,而malloc函数从上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念,凡是通过new操作符进行内存申请,该内存即为自由存储区。而堆是操作系统中的术语,是操作系统所维护的一块特殊内存,用于程序的内存动态分配,C语言使用malloc从堆上分配内存,使用free释放已分配的对应内存。

    2. 返回类型安全性

      new操作符内存分配成功时,返回的是对象类型的指针,类型严格与对象匹配,无须进行类型转换,故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ,需要通过强制类型转换将void*指针转换成我们需要的类型。

    3. 使用new操作符申请内存分配时无须指定内存块的大小,编译器会根据类型信息自行计算,而malloc则需要显式地指出所需内存的尺寸。

    4. new/delete会调用对象的构造函数/析构函数以完成对象的构造/析构。而malloc则不会

    5. 对数组的处理

      C++提供了new[]与delete[]来专门处理数组类型,对数组的支持体现在它会分别调用构造函数函数初始化每一个数组元素,释放对象时为每个对象调用析构函数。至于malloc,它并不知道你在这块内存上要放的数组还是啥别的东西,反正它就给你一块原始的内存,在给你个内存的地址就完事。

    6. operator new /operator delete的实现可以基于malloc,而malloc的实现不可以去调用new。

  • C++内存模型

    C++内存分为5个区域:

    • 堆 heap :
      由new分配的内存块,其释放编译器不去管,由我们程序自己控制(一个new对应一个delete)。如果程序员没有释放掉,在程序结束时OS会自动回收。涉及的问题:“缓冲区溢出”、“内存泄露”
    • 栈 stack :
      是那些编译器在需要时分配,在不需要时自动清除的存储区。存放局部变量、函数参数。
      存放在栈中的数据只在当前函数及下一层函数中有效,一旦函数返回了,这些数据也就自动释放了。
    • 全局/静态存储区 (.bss段和.data段) :
      全局和静态变量被分配到同一块内存中。
    • 常量存储区 (.rodata段) :
      存放常量,不允许修改(通过非正当手段也可以修改)
    • 代码区 (.text段) :
      存放代码(如函数),不允许修改(类似常量存储区),但可以执行(不同于常量存储区)
  • C++11智能指针介绍

    使用头文件

    智能指针主要用于管理在堆上分配的内存,它将普通的指针封装为一个对象。当对象的生存周期结束后,会在析构函数中释放掉申请的内存,从而防止内存泄漏。

    • 为什么要使用智能指针

      智能指针的作用是管理一个指针,因为存在以下这种情况:申请的空间在函数结束时忘记释放,造成内存泄漏。使用智能指针可以很大程度上的避免这个问题,因为智能指针就是一个类,当超出了类的作用域是,类会自动调用析构函数,析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间,不需要手动释放内存空间。

    • unique_ptr

      (替换auto_ptr)unique_ptr实现独占式拥有或严格拥有概念,保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用。

    • shared_ptr

      shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象,该对象和其相关资源会在“最后一个引用被销毁”时候释放。从名字share就可以看出了资源可以被多个指针共享,它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。shared_ptr 是为了解决 auto_ptr 在对象所有权上的局限性(auto_ptr 是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。

    • 如何选择智能指针:如果需要多个指针指向同一个对象,就是用shared_ptr,否则使用unique_ptr

    • 使用方法

      1
      unique_ptr<Report> ps (new Report("using unique ptr"));

      Report是一个类,之后使用ps的方法和普通的指针一样。

  • 多态原理

  • STL

    • 优先队列

      定义优先队列 priority_queue<int, vector, greater > q;第一个为元素的类型,第二个为所使用的容器(vector或deque),第三个为一个比较的规则,决定是最大优先队列还是最小优先队列,默认的less为最大优先队列。第三个参数如果省略,默认为大顶堆,即降序排列,加上之后变成小顶堆。方法与栈差不多,有top()ppop()push()等等。

    • vector与list

      vector

       向量 相当于一个数组
       在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小, 当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
      优点:(1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组
                  进行动态操作。通常体现在push_back() pop_back()
                  (2) 随机访问方便,即支持[ ]操作符和vector.at()
                  (3) 节省空间。
      缺点:(1) 在内部进行插入删除操作效率低。
                  (2) 只能在vector的最后进行push和pop,不能在vector的头进行 push和pop。 
                   (3)  当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释
                        放 

      list

       双向链表
       每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
      优点: (1) 不使用连续内存完成动态操作。
                   (2) 在内部方便的进行插入和删除操作
                  (3) 可在两端进行push、pop
      缺点:(1)  不能进行内部的随机访问,即不支持[ ]操作符和vector.at() 
                  (2) 相对于verctor占用内存多 
  • 拷贝构造函数与赋值运算符重载

    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
    #include<iostream>
    #include<string>
    using namespace std;

    class MyStr
    {
    private:
    char *name;
    int id;
    public:
    MyStr():id(0),name(NULL) {}
    MyStr(int _id, char *_name) //constructor
    {
    cout << "constructor" << endl;
    id = _id;
    name = new char[strlen(_name) + 1];
    strcpy_s(name, strlen(_name) + 1, _name);
    }
    MyStr(const MyStr& str)
    {
    cout << "copy constructor" << endl;
    id = str.id;
    name = new char[strlen(str.name) + 1];
    strcpy_s(name, strlen(str.name) + 1, str.name);
    }
    MyStr& operator =(const MyStr& str)//赋值运算符
    {
    cout << "operator =" << endl;
    if (this != &str)
    {
    if (name != NULL)
    delete[] name;
    this->id = str.id;
    int len = strlen(str.name);
    name = new char[len + 1];
    strcpy_s(name, strlen(str.name) + 1, str.name);
    }
    return *this;
    }
    ~MyStr()
    {
    delete[] name;
    }
    };

    int main()
    {
    MyStr str1(1, "hhxx");
    cout << "====================" << endl;
    MyStr str2;
    str2 = str1;
    cout << "====================" << endl;
    MyStr str3 = str2;
    return 0;
    }

Java

  • hashmap和hashtable的区别

  • String StringBuilder StringBuffer区别,线程安全问题

    String是字符串常量,每次更改都是创建一个新的然后把旧的回收,所以最慢。另外两个都是字符串变量。buffe和Stringr线程安全,Builder线程不安全

  • 反射

    反射之中包含了一个「反」字,所以想要解释反射就必须先从「正」开始解释。

    一般情况下,我们使用某个类时必定知道它是什么类,是用来做什么的。于是我们直接对这个类进行实例化,之后使用这个类对象进行操作。

    1
    2
    Apple apple = new Apple(); //直接初始化,「正射」
    apple.setPrice(4);

    上面这样子进行类对象的初始化,我们可以理解为「正」。

    而反射则是一开始并不知道我要初始化的类对象是什么,自然也无法使用 new 关键字来创建对象了

    这时候,我们使用 JDK 提供的反射 API 进行反射调用:

    1
    2
    3
    4
    5
    Class clz = Class.forName("com.chenshuyi.reflect.Apple");
    Method method = clz.getMethod("setPrice", int.class);
    Constructor constructor = clz.getConstructor();
    Object object = constructor.newInstance();
    method.invoke(object, 4);

    上面两段代码的执行结果,其实是完全一样的。但是其思路完全不一样,第一段代码在未运行时就已经确定了要运行的类(Apple),而第二段代码则是在运行时通过字符串值才得知要运行的类(com.chenshuyi.reflect.Apple)。

    所以说什么是反射?

    反射就是在运行时才知道要操作的类是什么,并且可以在运行时获取类的完整构造,并调用对应的方法。

    完整示例代码:

    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
    public class Apple {

    private int price;

    public int getPrice() {
    return price;
    }

    public void setPrice(int price) {
    this.price = price;
    }

    public static void main(String[] args) throws Exception{
    //正常的调用
    Apple apple = new Apple();
    apple.setPrice(5);
    System.out.println("Apple Price:" + apple.getPrice());
    //使用反射调用
    Class clz = Class.forName("com.chenshuyi.api.Apple");
    Method setPriceMethod = clz.getMethod("setPrice", int.class);
    Constructor appleConstructor = clz.getConstructor();
    Object appleObj = appleConstructor.newInstance();
    setPriceMethod.invoke(appleObj, 14);
    Method getPriceMethod = clz.getMethod("getPrice");
    System.out.println("Apple Price:" + getPriceMethod.invoke(appleObj));
    }
    }
  • bean

  • Sprinng MVC :在SpringMVC的应用中,当一个请求到达服务器时,首先会被DispatchServlet获取,当然在此之前会被一些安全控制相关的拦截器处理,到了DispatchServlet之后,DispatchServlet会根据HandlerMapping的机制(比如常用的@RequestMapping),将请求分配给处理该请求的ControllerController会调用一个或多个Service完成具体的业务逻辑处理,而Service则会调用一个或多个Repository(即我们常说的Dao层)与数据库交互。然后Controller完成业务逻辑处理之后,将数据返回客户端,或者调用视图解析器将视图返回客户端。

  • hashMap

    与 JDK 1.7 相比,1.8 在底层结构方面做了一些改变,当每个桶中元素大于 8 的时候,会转变为红黑树,目的就是优化查询效率

    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
    public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
    if (key == null)
    return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    // 如果发现已有该键值,则存储新的值,并返回原始值
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public V get(Object key) {
    if (key == null)
    return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
    e != null;
    e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;
    }
    return null;
    }

双缓存算法

对于clean容器n,当他失效时,理想状态是,同一条带中比n小的容器都在cache中,我们只需要从磁盘读取比n大的那些容器。实际情况下,同一条带中比n小的容器可能会被挤出去,那么恢复n时就要重新读取比n小的那些容器。另外,当恢复n时,那些比n大的容器被存入缓存,这些比n大的容器在将来一定会被命中,但是可能在命中到来之前就被挤出去了,之后就需要再次从磁盘读。
为了避免上面的两种情况,增加clean cache,用来保护clean容器。dirty cache满了的时候,不能将clean cache中的容器替换出去。
对opt算法也进行了改进。假如接下来需要恢复容器n,将缓存中的容器按照下面的优先级排序:
1. (优先级最高)恢复n所需的容器
2. 在window中出现的容器(即不久将来会被用到),出现的越早优先级越高
3. 没有在window中出现的容器,但是在window中有和该容器在同一条带的容器(关联容器),在window中关联容器出现的越早,优先级越高
4. (优先级最低)在window中没有出现过,且window中也没有关联容器
排序后,首先考虑将优先级最低的容器替换掉

web服务器

  1. 功能

a) 可配置监听地址、监听端口和主目录 b) 能够在监听端口上进行监听
c) 支持服务的启动
d) 支持服务的关闭

e) 能够响应客户端的请求,并定位相应的 html 文件
f) 能够构造并发送可被客户端解析的响应报文
g) 以多线程或异步方式响应每个客户端请求,支持多个客户端的并发请求
h) 在服务器端的屏幕上输出每个请求的来源(IP 地址、端口号和 HTTP 请求命令行) i) 支持一定的异常处理能力
j) 支持多种类型文件的输出
k) 对于无法成功定位文件的请求,能够根据错 误原因,作相应错误提示
l) 在服务器端的屏幕上能够输出对每一个请求 处理的结果
m) 具备图形 GUI 界面

  1. 流程

    winsock初始化 -> 创建服务器套接字 -> 配置端口号 -> 配置本地资源路径 -> 解析用户输入的ip地址 -> 将服务器套接字与端口号绑定 -> 开始监听listen -> 每出现一个请求,就开一个新的线程,使用accept函数建立连接

rdt协议

GBN演示图

SR协议发送方有一个窗口,只要这个窗口中存在还没有发送过的分组,就发送,并且每个分组设置一个计时器。如果某个分组超时了,就重传。如果收到了ack,就对相应的分组进行标记,如果收到的ack是base序号,就把base序号推进到下一个还没有被ack的序号。接收方如果按序收到了分组,就提交,如果失序,就缓存。收到的如果是n,就ack n。

a-b剪枝算法

整个α-β剪枝的核心思想就是,当你知道你有一个选择A时,此时你知道了B选择不如A选择好,那么你就不需要知道B选择有多坏。

a-b 剪枝算法是一种基于剪枝的深度优先搜索算法,是对 Minmax 算法的优 化,同时 a-b 剪枝算法也是根据极大-极小规则进行的,基本思想是:根据倒推值 的计算方法,或中取大,与中取小,在扩展和计算过程中,剪掉不必要的分枝, 从而提高效率。

对于MIN层我们取所有情况的最小值和上一层的a比较,如果最小值小于a就意味着不会使得a更大,就剪掉

α值:有或后继的节点,取当前子节点中的最大倒推值为其下界,称为α值。节点倒推值>=α;

β值:有与后继的节点,取当前子节点中的最小倒推值为其上界,称为β值。节点倒推值<=β

a 剪枝是指,在对博弈树采取深度优先的搜索策略时,从左路分枝的叶节点 倒推得到某一层的 MAX 节点的值,可表示到目前为止得以落实的最大效用 值,记为 a。这个值可以作为 MAX 方效用值的下界。然后再搜索该 MAX 节 点的其他子节点,如果发现子节点的上界比自己的下界还要小,那么就直接 放弃还没有搜索的分枝,即进行剪枝。
b 剪枝是指,在对博弈树采取深度优先的搜索策略时,从左路分枝的叶节点 倒推得到某一层的 MIN 节点的值,可表示到目前为止得以落实的最小效用 值,记为 b。这个值可以作为 MIN 方效用值的上界。然后再搜索该 MIN 节 点的其他子节点,如果发现子节点的下界比自己的上界还要大,那么就直接 放弃还没有搜索的分枝,即进行剪枝。

系统调用

我们都知道,很多我们习以为常的C语言标准函数,在linux平台的实现都是通过系统调用完成的,例如我们在用户程序中使用open()或者write()函数时,函数执行过程中会通过中断进入到系统内核中检查系统调用号,这个号码代表进程请求哪种服务。然后,它查看系统调用表(sys_call_table)找到所调用的内核函数入口地址。接着,就调用内核函数来实现open()或者write()等函数的功能。我们要做的,就是在内核中增加一个内核函数,相应地也在系统调用表中增加一个表项,使得我们增加的功能永远的留存在系统中

然后找到/usr/src/linux-4.18.3/arch/x86/entry/syscalls/syscall_64.tbl,在编号为334的一行后面新加一行,编号为335,第二列为common,第三列为新增系统调用的名字,我命名为mycall,第四列为__x64_sys_mycall。

之后找到/usr/src/linux-4.18.3/include/linux/syscalls.h,从文件名字就能看出来,这里面的都是函数的声明,我们在文件的最后,#endif之前,添加我们自定义的函数的声明.

之后,找到/usr/src/linux-4.18.3/kernel/sys.c,我们将新增加的函数的定义添加在文件的末尾,#endif之前

首先需要注意的是,在内核中,我们只能使用内核函数,比如open()、write()函数都不能用了,需要用ksys_open()和ksys_write()

make编译内核,make modules_install安装模块,make install安装内核

编译器

抽象语法树采用孩子兄弟表示法来表示,每个节点为一个ASTTree结构体,结构体中有ScopeItem指针,用于指向符号表节点。每一个ScopeItem结构体中记录符号的详细信息,并且还有一个ScopeItem*的指针用于记录数组的内情向量。数组长度用vector记录,维度用dim记录。

朴素贝叶斯声音性别识别

  • 简化的贝叶斯公式为

  • 朴素贝叶斯基于的假设为

  • 概率的计算方法为

设备驱动

  • linux把所有的设备都当做文件来处理。我们的linux操作系统跟外部设备(如磁盘、光盘等)的通信都是通过设备文件进行的,linux为不同种类的设备文件提供了相同的接口,比如read(),write(),open(),close()。所以在系统与设备通信之前,系统首先要建立一个设备文件
  • 编写驱动程序 my_device.c,我们需要为驱动编写 my_open、my_release、 my_read、my_write 函数
  • 编写my_open函数时:从设备使用的角度出发,当需要打开、开始使用某个设备时,使用 try_module_get 去增加管理此设备的 owner 模块的使用计数,这样,在设备在使 用时,管理此设备的模块就不能被卸载
  • 编写try_release函数时:执行module_put函数
  • 编写my_read函数时:使用copy_to_user函数。Copy_to_user 函数的作用是将内核区的内容复制到用户空间,他的参数分别 为指向内核区的指针、指向用户缓冲区的指针和读取内容的长度,执行此操作后, 相应的内容就从内核区复制到用户空间,也就相当于完成了读操作。
  • 编写my_write函数。Copy_from_user 函数的作用是将用户空间的内容复制到内核,他的参数分别 为指向用户缓冲区的指针、指向内核区的指针和读取内容的长度,执行此操作后, 相应的内容就从用户复制到内核,也就相当于完成了写操作。
  • 注册设备时要用到 register_chrdev 这个函数,函数的第一个参数为为新设备 分配的主设备号,我们这里设置为 0,意味着允许系统自动为设备设置主设备号; 函数的第二个参数是设备名,第三个参数是 file_operations 结构体的指针,这个 结构体中有 my_open、my_release、my_read、my_write 这四个函数,意味着新的 设备具有这四个功能。
  • 执行make,执行insmod my_drive.ko指令,用于安装模块。进入/proc/device查看主设备号。之后使用mknod命令创建设备文件。

实习

目标:对锋刃的消费延迟,设置监控来发现,然后触发对应处理操作,尽可能实现自动化处理,不能自动化的,触达 到对应的负责人,以达到早发现,早处理。

锋刃作业并行度计算方式:

  1. 锋刃作业上游每秒的流量 / 锋刃作业的处理能力qps(留有40%buffer) = 最少需要的并行度;
  2. 最佳并行度 = 大于等于最少需要的并行度 AND 能被锋刃上游CDMQ的分区数整除的最小值 AND 小于等于锋刃上游CDMQ的分区数

翻转链表

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
#include <iostream>

using namespace std;

struct ListNode {
int val;
struct ListNode * next;
};

struct ListNode *reverseList(struct ListNode* head) {
if (head == nullptr) {
return nullptr;
}
struct ListNode *p0 = nullptr;
struct ListNode *p1 = head;
struct ListNode *p2 = head->next;
while (p1 != nullptr) {
p1->next = p0;

p0 = p1;
p1 = p2;
if (p2 != nullptr) {
p2 = p2->next;
}
}
return p0;
}

int main(){
int num[5] = {1, 2, 3, 4, 5};
ListNode *node = new ListNode, *head = node;
node->val = 1;
node->next = nullptr;
for(int i = 1; i < 5; i++) {
node->next = new ListNode;
node = node->next;
node->val = num[i];
node->next = nullptr;
}
cout << "原本的链表为" << endl;
node = head;
while(node) {
cout << node->val << " ";
node = node->next;
}
cout << endl << "翻转后的链表为" << endl;
node = reverseList(head);
while(node) {
cout << node->val << " ";
node = node->next;
}

}

赋值运算符重载与拷贝构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class String {
private:
char * str;
public:
String ():str(new char[1]) { str[0] = 0;}
const char * c_str() { return str; };
String & operator = (const char * s);
String::~String( ) { delete [] str; }
String( String & s){
str = new char[strlen(s.str)+1];
strcpy(str,s.str);
}
};
String & String::operator = (const char * s) {
//重载“=”以使得 obj = “hello”能够成立
if( this == & s)
return * this;
delete [] str;
str = new char[strlen(s)+1];
strcpy( str, s);
return * this;
}