字节跳动基础研发三面

今天是字节跳动三面，感觉有点凉，记录一下主要的问题防止以后再被问到。

请你自我介绍一下

老问题了，自报家们，然后说了一下自己做过的项目，就是DQEMU和ABA的那两个。其实在自我介绍的时候可以不用说的那么详细的，因为他后面还会再问。DQEMU这个项目用一句话来说应该是我们想把qemu拓展到了一个分布式的平台上，然后qemu也可以利用多个节点的计算资源。然后ABA那个项目确实不太好总结，我们应该说qemu在模拟arm到x86的原子指令时存在问题，社区上有很多种解决方法，但是会造成很大的overhead，或者是需要额外的硬件。qemu为了效率和portable没有解决这个问题。我们综合了社区上的解决方案和当前最好的解决方案，实现了两种自己的解决方案，并比当前最好的解决方案快两倍以上。

那么
面试官你好，我叫蒋璋，来自南开大学，目前就读于计算机学院的计科专业，预计在今年的6月毕业。我大概写了三年代码，最经常用的语言是C和Python。算上课内的大作业的话，大概有两年的项目经验。课内的话写过一个简易的C语言编译器，把简单的C程序编译成x86的汇编，支持函数声明和调用，结构体，指针，还有浮点数运算。还有一个建议的计算机系统，用C语言去模拟x86的cpu，然后再为其编写简单的硬件接口和操作系统，能够实现一些系统调用，内存管理还有文件系统进程调度之类的功能。从大三的开始到现在，我在实验室做实习生，期间经历了两个项目，一个是讲qemu，就是一个能模拟其它平台的指令的一个模拟器，把它拓展成分布式。另一个是解决了arm到x86上原子指令模拟的问题，我们评估了以往的解决方案，然后提出了一个正确又高效的解决方案，其中最好的一种比当前最好的解决方案平均快2倍以上。

我在项目中做的事情

在DQEMU，就是是那个分布式的qemu中，我参与了futex系统调用的实现，以及缺页中断的处理，还有线程在节点之间的调度，还有实验结果的测算和评估。比较困难的地方是由于安全方面的考虑，系统调用是交给主节点去完成的，但是futex会使得主节点进入睡眠，导致主节点不能再去响应请求。因此我们修改了futex的语义，仅用一个表将其保存，然后让发出futex指令的节点睡眠。缺页中断的处理用到了MESI协议，通过这个协议维持页面在节点之间的一致性。然后线程在节点之间的调度，因为如果节点之间如果存在数据依赖的话，就会频繁的在节点之间进行页面传输，如果把存在数据依赖的线程放到同一个节点上，就能减缓这种情况。我们做了一种基于用户提示的线程调度，允许用户加入一点提示信息，然后我们根据提示信息进行线程调度。

在ABA里面，我参与了两种策略的实现

请你仔细说一下这两个项目的细节

ABA

ABA应该这么说
arm上有原子指令Load Link，简称LL, 和Store Conditional, 简称SC。这对指令的功能是检测一个监视一个地址有没有被别的线程修改。使用的过程如下，首先Load Link一个地址，然后这个地址的值会被取出；接着我们使用这个值进行一系列的运算，即我们想修改这个值；然后进行SC操作，SC会检测这期间这个地址有没有被其它线程修改过，然后被其它线程修改过的话那么SC就会失败，如果没有被其它线程修改过的话SC就把新的值写回到原来的地址中。这样，LL/SC就能保证在读取和写回的过程中的原子性。LL/SC可以用来实现原子加一之类的操作，比如先LL a的地址到一个寄存器，然后在寄存器中++，接着SC寄存器值到a的地址。由于x86平台上面没有类似LL/SC的指令，但是有Compare And Swap(CAS)的指令。这个指令的作用是原子的比较一个地址处的值与给定的值是否相等，如果相等的话更改其为另一个值，否则不更改。可以看出LL/SC的原子性是比CAS要强的，因为LL/SC能够监测期间地址有没有被人写过，而CAS指令只要他的值没变就认为没有发生变化。比如说有一个变量a = 1, 如果他先变成2再变成1，LL/SC会认为这个地址别人修改过而失败，而CAS指令认为值没有发生变化而成功，这就是二者的区别。
因为ABA问题不太好解释，如果他这里问到了会有什么问题，再跟他说ABA问题。
然后ABA问题就是

C->B->A top = C

Push(obj)
{
  oldval = [top];
  obj->next = top;
  CAS(top, oldval, obj);
}

Pop()
{
  ret = top;
  if(ret == nullptr)
    return ret;
  if(CAS(top, ret, ret->next))
    return ret;
  return nullptr;
}


thread1:
ret = top;
if(ret == nullptr)
  return ret;
next_obj = ret->next
if(CAS(top, ret, next_obj))
  return ret;
return nullptr;

top = B

thread2:
C = pop()
B = pop()
push(C)

C->A

qemu社区也有很多对于这个问题的解决，比如在LL/SC的区域进行串行执行，这样会带来很大的性能开销，qemu权衡了性能，选择不解决这个问题。我们想做的是给出一种高效的解决RISC->CISC翻译LL/SC的方法。

然后我们给出了两种策略，一种是用全局的哈希表记录写的时候的线程id，我们把它叫做HST, 另一种是利用页面权限把LL的页面变成只读的，这样也能监测别人对于这个地址的写操作，叫PST。经过我们的实验，利用全局哈希表的实现能比之前最好的实现快两倍以上。我们还给出了了这两种策略的优化。HST可以使用硬件HTM进行优化。原因是在HST做SC的时候，可能会有其它线程在做store, 这就可能带来竞争，所以我们需要把其它CPU停下来，但是这降低了并行度。采用HTM以后，我们把sc的区域用HTM保护起来，如果其中其它线程对这个sc的地址进行了store，那么就会被捕捉到，然后让sc失败，这样不用停下其它的cpu，提高了并行度，缺点是需要用到额外的硬件支持。然后PST同样也有这种情况，不过PST可以不用到HTM的硬件就能解决，方法是把做SC时把原来的页面通过remap这个系统调用映射到一个新的地址上，这样对新的地址进行操作就不会影响到原来的地址了。

DQEMU

目的：利用多个节点的计算资源。比如有四台机器，每个四核。那么如果在一台机器上运行qemu，只能用到4个核心，如果能在多个节点上面同时运行，那就能用到16个核心的计算资源。

一致性：分布式共享内存MESI

跨节点系统调用：本地系统调用和全局系统调用

锁：节点内部用原本的锁节点之间使用MSI。

优化：

1. Page Split
2. Page Forwarding
3. hint base schedule

虚拟化

一开始没有理解他的问题，其实他一直在往虚拟化上面靠但是我没有听懂。做虚拟化的应该是system level的但是我们做的是user level的。