Jepson's Blog

已通过

• 自我介绍

• 问了编译器项目

• 着重问了那个超声的科研项目

  系统的设计啊、遇到的困难啊、解决的方案啊

• 马斯克的星链计划

  如果要实现地球的全覆盖至少需要几个卫星（答得不好）

• 从之前面试官问过的问题里找一些问题重新问

  • 重新问了一面的大鱼吃小鱼的问题，问一开始回答的思路是啥，以及回去之后有没有思考更优的算法
  • 假设题目变化，大鱼吃了小鱼之后变大了，上述算法还可用吗

• 曾经遇到的困难

  • 讲了搞科研、写论文以及实习之间的困难

• 从我github里找了一个很久之前fork的版本一键更新仓库，然后问到了抖音更新问题

  • 用户打开APP时弹窗版本更新是怎么实现的
  • 用户正在使用APP时怎么通知更新
  • 问了很多客户端和服务端http通信的问题
  • tcp长链接短连接
  • http是双攻的还是半工的
  • socket

• 设计一个APP需要考虑哪些部分

  • 答了UI、客户端编程、后台数据库、前后端之间的通信

• 介绍自己开发的APP

  • 三个大创的APP，然后主要选了那个请假APP介绍

• 开发APP时是怎么去学习的

  • 用到啥学啥，举了开发的位置模拟APP的例子

• activity是啥

• 介绍了飞书的一个黑科技，进入一个房间会电脑可以自动连上这个房间的投屏，问是怎么实现的

  • 诶，这个答得不好，说了半天wifi、NFC、蓝牙之类的，愣是没想起来自己做的超声，麻了

  • 面试官提醒超声之后问怎么实现的

• 对安卓开发的兴趣，后续是否愿意从事这个方向

• 安卓开发后续的学习规划

• 问了实习的计划，从几月到几月

• 反问环节

  • 问了一下实习生去了之后干什么，能学到什么？

动态类型语言和静态类型语言

• 动态类型语言：在程序运行时才检查数据类型。即在编程时不要要指定变量的类型，运行时会根据变量的赋值自动确定类型。比如JacvaScript,Python。
• 静态类型语言：在编译时检查数据类型。在编写程序时就需要指定变量的类型。比如C/C++,Java。

编译型语言和解释型语言

• 编译型语言：在运行前需要经过一个单独的编译，将程序翻译成机器语言，然后在机器上执行。优点是块，因为执行机器语言时不用再编译，缺点是平台关联性强。比如C/C++。
• 解释型语言：解释型语言不需要编译，可以直接运行，运行时由解释器负责解释。比如Python。
• 混合型语言：Java即是编译型的，也是解释型语言，总的来说Java更接近解释型语言。
  • 可以说它是编译型的。因为所有的Java代码都是要编译的，.java不经过编译就什么用都没有。
  • 可以说它是解释型的。因为Java代码编译后不能直接运行，它是解释运行在JVM上的，所以它是解释运行的。

脚本语言

• 源程序是文本格式，可以被解释执行的语言可以算作脚本语言。
• 解释语言是说解释执行的语言，但执行的代码并不一定是文本格式的。脚本语言的程序是文本文件，并且是解释执行的。

基于超声波的驾驶员头部朝向追踪和生命体征监控系统

项目内容

• 头部朝向追踪

  • 方案：基于超声波测距和定位算法。

  • 应用：估计驾驶员的意图用于智能驾驶。

• 生命体征监控

  • 方案：对2*8通道的超声信号一起进行主成分分析，从中提取驾驶员的呼吸和心跳信息。

  • 应用：检测驾驶员疲劳驾驶和危险动作识别。

项目难点

• 声波信号的多径问题

  • 原因：由于环境中物体的反射，无线信号普遍存在的多径问题，即从发射端到达接收端会有多个不同的路径，包括直达径和多个反射径。

  • 解决方案：采用Zadoff-Chu序列来调制超声信号，zc信号具有很好的多径分辨能力。

• 直达径被遮挡问题

  • 原因：超声波测距和定位算法基于直达径信号传播时间的估计，如果直达径被遮挡，那么测得的就是反射径的距离，无法用于定位。

  • 解决方案：理论上只需要三个接收端就可以根据三点定位算法完成发射端定位，通过布置更多的接收端保证头部不管怎样旋转都至少与三个接收端之间的直达径不被遮挡。

• 只能定位头部的两个坐标

  • 原因：理论上至少需要知道物体上三个点的坐标才能确定其在三维空间中的朝向，但是生活中大多数设备都只支持双声道，而且实验用的数据采集卡也只支持两发，所以只能完成两个点的定位。

  • 解决方案：提出“轴点”的假设，因为驾驶员在驾驶过程中头部动作十分有限，而且不会有复杂的动作，所以可以根据两个发射端的轨迹估计出驾驶员的动作，进而推算出轴点的位置。

基于C0文法的编译器设计与开发

项目背景

大三时编译原理课程，报名参加了试点班。试点班就是不用参加平常的理论课和实验课，只需要用一学期的时间开发出一个编译器。但是一共三四十名学生报名参加了试点班，最后我的成绩是最高的。

在上编译原理这门课之前对编译器可以说是一无所知，所以一开始上手很困难。老师给了我们一本编译原理的书，就是号称编译原理三大圣经之一的龙书，然后给了我们一个编译原理的网课让我们自学。看了一段时间书和网课然后慢慢开始一点点上手实践。

项目流程

编译器开发主要分为四大块：词法分析、语法分析、中间代码生成和汇编代码生成。

• 词法分析主要是将源代码的字符串划分为token，每个token都包含了一个划分出来的词以及这个词的类型。
• 语法分析就是按照定义好的语法规则将词法分析生成的tokens转换成抽象语法树的过程。
• 中间代码生成式在语法分析的过程中，将语法树转换成四元组的形式，使用四元组主要是为了方便后续汇编代码生成。
• 汇编代码生成就是将四元组转化成对应的汇编代码，比如我采用的mips指令集。

项目难点

• 寄存器优化

  不进行优化的方案就是，每次对变量进行操作的时候，都需要先将变量从内存读到寄存器，然后在寄存器上对变量进行操作，操作完成后再将变量写回寄存器，所以每次使用一个变量都会带来两次寄存器读写，这是很耗时间的，尤其是当对一个变量进行反复修改，就得不断的反复从内存读出写入。

  所以最好的解决方案是，给每个变量都分配一个寄存器，等到程序结束的时候再一起写回。但是实际中寄存器的数量是很有限的，以mips指令集为例，一般只有32位寄存器，除去一些有特殊用处的能够使用的寄存器可能只有十几二十几个，而一段代码内部的变量可能有很多，所以没办法给每个变量都分配一个寄存器。

  可以尽可能多的把寄存器分配给变量，但是当寄存器用完了而又来了新变量时，就必须做出一个抉择就是要把哪个旧的变量踢出寄存器。这个选择做的好坏非常影响编译器的性能。

  当时对这方面的算法了解不多，所以采取了一个比较简单的算法，就是引用计数法。即每次使用一个变量都对将它的计数器加一，然后需要踢出变量的时候就优先踢出计数器次数最小的那个。这种方法再大多数情况下是有效的，但是有些极端情况比如寄存器震荡等。

  后来慢慢接触到其它知识后，了解到这个问题其实跟很多其它问题类似，比如内存的页面置换等。有一些很好的算法，比如LRU等，这也是这个编译器后续可以继续优化的方向。

• 函数调用时的压栈和出栈设计

  每个函数都在内存中对应着一段栈帧，栈帧由栈顶和栈底两个寄存器确定，mips里叫做sp和fp。

  调用函数时，先将函数参数压栈压栈，再将返回地址压栈，再将栈底位置压栈，然后将栈底指向栈顶也就是当前位置，之后就是新函数的栈帧。

  函数调用结束后，出栈的顺序跟入栈的顺序相反，先让栈顶指向栈底，意味着将该函数的栈帧取消，再将栈底移到它指向的值，即回到上一个栈底的位置，从而恢复上一个函数的栈帧，然后再将放回地址出栈，让指令寄存器回到返回地址处继续执行程序。

• 多重for循坏的线性化

  通过mips的label和jump指令将for循环展开

后续的优化方向

• 增加一些功能，比如多维数组、结构体等。
• 改进寄存器优化算法，比如增加计数器衰减或者使用LRU算法等。

系统调用

系统调用就是调用操作系统提供的一系列内核功能函数，因为内核总是对用户程序持不信任的态度，一些核心功能不能直接交由用户程序来实现执行。用户程序只能发出请求，然后内核调用相应的内核函数来帮着处理，将结果返回给应用程序。如此才能保证系统的稳定和安全。

系统调用是给用户态下的程序使用的，但是用户程序并不直接使用系统调用，而是系统调用在用户态下的接口。这个用户接口就是操作系统提供的系统调用API，一般遵循POSIX标准。

每一个系统调用都唯一分配了一个整数来标识，通常的做法就是将这个系统调用号放进eax寄存器，当执行到系统调用入口程序的时候就会根据eax的值去调用具体的系统调用程序，比如说eax中存放的是1那么就会去调用fork这个系统调用的相关函数。

系统调用的实现

• 参数

  有些系统调用的是需要参数的，用户接口不真正干活，真正干活的是内核功能函数，但是需要的参数在用户态下，所以需要在用户接口部分向内核传递参数。传参有两种方法：

  • 直接传给寄存器，寄存器是通用的，在用户态将值传给寄存器，进入内核态之后就可以直接使用，这可以使用内联汇编来实现。

  • 压栈，压栈有个问题，系统调用使用中断/陷阱来实现，这期间会换栈，在用户态下压栈的参数对内核来说似乎没什么用处。所以要想使用用户态下栈中的参数，必须要获得用户栈的地址，这个值在哪呢？没错，在内核栈中的上下文保存着，从内核栈中取出用户栈的栈顶esp值，就可以取到系统调用的参数了，xv6就是这样实现的。

• 返回值

  函数的调用约定中规定了返回值应该放在eax寄存器里面。而在系统调用的一开始我们将系统调用号传进了eax寄存器，然后中断时保存上下文，将eax压入内核栈，系统调用处理程序将最后结果放到eax寄存器中。