最近因为新冠病毒长期宅在家里，决定开始一个很早就想做的项目：搭一个服务器机架。第一次搭经验不足，买错过几次零件，只能重新下单，前前后后花了不少时间。于是写了这篇博客介绍下用到的设备和配件，给有兴趣自己搭一个的朋友做参考。

机架

我选择的机架是 Raising 的 15U 机架。这个机架优点是够结实，深度可变，价格也比 StarTech 的便宜一点。如果预算足够可以考虑买 StarTech 的机架（12U, 25U）。这里 U 是用来衡量机架中组件高度的单位，1U 约等于 43.66 毫米。机架上每个 U 的高度都会对应的三个孔，如下图所示。

因为我有不少没法直接固定在机架上的设备，得把它们放在隔板上。我一共买了四块隔板：

• AC Infinity 1U 隔板：深度为 10” 。
• StarTech 2U 隔板：深度为 16”。就是底部放 NAS 的这块了。
• 2 x Raising 1U 隔板：深度为 12”。做工上的确比 AC Infinity 1U 差一点，但是一块 AC Infinity 1U 的价格几乎可以买两块 Raising 1U 了。

此外出于美观考虑还可以买挡板，StarTech 的 1U 挡板就挺好。

网线

配线架（Patch Panel）可以让前面板的网线看起来干净清爽。它的背面连接各种设备的背部网线口，正面用短网线连接路由器和其他网线口在正面的设备。网上大多数的配线架都是一面连 CAT 5/6 网线，另一面是打线柱，很少有两面都是网线口的配线架。于是我买了两条 TRENDnet 1U 24 口空白网络配线架，加上 48 个两端都是网线口的 Keystone。这个 Keystone 从用户评论来看，以太网供电（PoE）和网速都不会受到影响。

过长的网线用在前面板也不好看，我先试了 1ft (30cm) 的 Monoprice 网线，装上以后还是觉得网线太长。后来换成了 0.5ft (15cm) 的 网线，看起来干净好多。

设备

设备选择方面，我只是把原有的监控设备和服务器搬了过来，放在了层板上。犹豫过要不要买一个机架式服务器，但是考虑到机架式服务器的耗电量，加上已经有了视频监控机和独立 NAS，最后还是买了个翻新的 HP EliteDesk i7-4785T 用来跑智能家居服务和 Unifi Controller。除了 HP 以外，Dell 和 Lenovo 都有类似的微主机，买一个二手的很适合当智能家居服务器。另外推荐使用 Intel T 系列的 CPU，专门为了省电设计。

机架上的一些其他设备：

• StarTech 1U 条形插座：带过载保护，单一开关控制所有插口。
• Netgear 16 口交换机 (JGS516PE)：其中 8 个口支持 PoE，配合 Unifi 的无线路由。用了三年了，非常稳定。
• Unifi 安全网关：配合服务器上跑的 Unifi Controller，可以远程配置 / 监控家庭网络。
• Samsung SmartThings 中控：我买的第一个智能家居中控，现在主要用 Home Assistant，但是部分智能家居设备还是通过 SmartThings 中控 + MQTT 的方式连接刀 Home Assistant 上。
• Mac mini (2010 年中)：曾经的智能家居中控，买了 EliteDesk 后 Mac mini 处于闲置状态。
• LaView 监控录像机：买了一整套监控录像机 + 摄像头。它的风扇噪音有点大，是目前机架的主要噪音来源。
• Qnap TS-853 NAS：最多可以放八个硬盘。数据备份中心，同时跑了 Owncloud 同步服务和 Plex 视频播放。如果没买这个 NAS 的话我可能会直接上机架式服务器。
• Arlo 视频监控机：另外一套视频监控设备。Arlo 的好处是可以选择用电池不连电源。

具体的智能家居和监控的使用这篇文章就不细谈了，对它们感兴趣的朋友，可以参考我的另外两篇博文：

• 智能家居之计划篇
• 智能家居之实践篇

家里用的是三星的洗衣机和烘干机，买的时候为了完成时有提醒特地挑了带有「智能监控」功能的机型。然而对应的三星洗衣机的 app 几乎没法用，推送和状态更新都有问题。于是我打算自己实现一个类似的功能。

因为洗衣机和烘干机用电量比较大，通过监控用电量很容易判断出设备当前的运行状态，于是我决定用智能插座来实现这个功能。现在很多智能插座都有电量检测的功能，选择的时候要注意插座支持的最大电量，我用了 TP-Link 的 HS110，支持最多 1500 瓦的设备，对于一般的洗衣机和烘干机来说绰绰有余。和智能插座对接的系统依然是 Home Assistant，它对 HS110 的支持很好，可以方便地读出设备当前用电量。

接下来是 Home Assistant 的配置部分，主要分状态定义和自动化脚本。

为了简化我只用两种状态（空闲和运转）描述洗衣机和烘干机的状态（代码只给出了洗衣机部分，烘干机部分几乎一样）：

input_select:
  washer_status:
    name: Washer Status
    options:
      - Idle
      - Running
    initial: Idle

为什么要定义状态而不是直接通过用电量判断呢？因为这些机器运转过程里会有几次几乎不用电的阶段，如果只通过用电量很容易产生错误信号，用电量配合状态持续时间才能做出更精准的判断。

接下来定义虚拟的洗衣机传感器，我们会通过自动化脚本更新这个传感器的值：

sensor:
  - platform: template
    sensors:
      washer_status:
        value_template: '{{ states.input_select.washer_status.state}}'
        friendly_name: 'Washer Status'

自动化脚本分两块，一块是检测到电量后的更新洗衣机状态为运转。这里我用了 10 瓦作为运转开始的阈值。

automation:
  - alias: Set washer active when power detected
    trigger:
    - platform: numeric_state
      entity_id: switch.hs110_washer
      value_template: '{{ state.attributes.current_power_w }}'
      above: 10
    condition:
      condition: or
      conditions:
        - condition: state
          entity_id: sensor.washer_status
          state: Idle
    action:
    - service: input_select.select_option
      data:
        entity_id: input_select.washer_status
        option: Running

另一块是设备停止运转的检测，根据不同的设备可能要进行微调。我这里设置了洗衣机用电低于 3 瓦且超过 1 分钟以上后，把状态切换成空置并通过 Twilio 发送短信通知。

automation:
  - alias: Set washer inactive
    trigger:
    - platform: numeric_state
      entity_id: switch.hs110_washer
      value_template: '{{ state.attributes.current_power_w }}'
      below: 3
      for:
        minutes: 1
    condition:
      condition: or
      conditions:
        - condition: state
          entity_id: sensor.washer_status
          state: Running
    action:
    - service: input_select.select_option
      data:
        entity_id: input_select.washer_status
        option: Idle
    - service: notify.twilio_sms
      data:
        message: Washer finished at {{ now() }}
        target:
          - 15555555555

这个脚本用了一个多月没出现误报，虽然一开始折腾一点，最后还是省了我们不少时间。

关于智能家居和 Home Assistant 的更多信息，可以参考我写的其他文章。

来美国五年后绿卡终于批了，没有太大曲折，不过也干等了好久，中间还找了议员催绿。总结下流程，希望给后来的朋友有帮助。

时间线

• 2013 年 10 月入职，2014 年初提交 I-140 (EB-2)，排期 (PD) 在 2014 年 3 月。
• 2015 年中换了工作，重新提交 PERM，排期不变。
• 2017 年 5 月 EB-3 排期赶超了 EB-2，我的 PD 在 EB-3 下已经 current。于是提交了 EB-3 I-140 的申请，同时提交了 I-485 / I-765 / I-131。I-485 回执日期 (RD) 在 2017 年 5 月。
• 2017 年 7 月中收到 EAD / AP 卡。
• 2018 年 3 月中 EB-3 I-140 审核通过。
• 2018 年 4 月收到 case 转移的通知。
• 2018 年 6 月初面试，面试后被通知体检过期，重新办了以后月底寄出。
• 2018 年 7 月 EB-3 的排期倒退，我的 PD 不再 current，由于当时 EB-2 还是 current 的，就让律师 interfile EB-2。
• 2018 年 8 月初联系议员催绿，月中得到消息说我的 case 还在审核中，最起码要等 45 天。
• 2018 年 9 月底再次联系议员，三天后得到消息说 USCIS 还在解决我 case 中的一些问题。
• 2018 年 10 月底查询网站更新状态为「New Card Is Being Produced」，两天后变成「Case Was Approved」，又过了两天变成了「Card Was Mailed To Me」。

整个过程中 EB-3 的 I-140 拖了好久，因为律师说加急需要 9089 原件，而我的原件已经在第一份 I-140 申请中提交了，没法再次加急。另外比较后悔的一件事就是绿卡面试前没有再去准备一份体检卡。面试通知上写着体检要求「valid within last year」，我以为只要是前一年办过体检就行，律师也建议面试完了再看要不要补办。等重新做体检提交，第二个月正好排期倒退了。

另外一个经验就是即使绿卡面试完了，也得催律师重新申请 EAD / AP。我的律师觉得绿卡马上拿到了就没急着帮我重新申 AP，导致我在绿卡迟迟没下来加上 Visa 过期的情况下，年底出游计划受限不少，如果有一张 AP 就可以放心安排出国计划了。

议员催绿

催绿方面，我们研究过参议员和众议员两个方案。两者效果应该差不多，都是通过官方问一下进度，以免你的 case 堆积在某个角落没人管。我们只联系了众议员，具体的流程如下：

1. https://www.house.gov/htbin/findrep 上输入你的区号找到对应区的议员，可能会要求输入具体地址进一步筛选。
2. 在议员的主页上找到电话联系方式，负责我的区域的是议员 Jackie，她的联系方式在这个页面。
3. 接下来的步骤不同议员可能会有所区别，具体可以看主页上的说明。对于我所在区的议员，打电话后选移民相关问题，会转接给负责的工作人员。
4. 工作人员要了我的邮箱地址后给我寄了一份隐私授权书，因为他们向 USCIS 查询我的情况时可能会涉及我的隐私，填完表格后扫描回复即可。一般等几天才会收到 USCIS 的答复。

整个过程没等多久，而且工作人员态度很好，之后发邮件问都是一刻钟内会有回复。

后记

拿到绿卡后似乎还要去更新下 SSN，去掉上面的工作限制。另外就是可以办 Global Entry 啦。

祝愿等绿卡的各位早日顺利拿到绿卡。

最后一周讲定位 (localization)，也就是 SLAM 里面的 L。主要包括粒子滤波和迭代最近点。

里程计定位 (Odometry)

里程计定位法直接从设备里读取信息，更新当前的位置状态。例如要跟踪车子的位置状态，可以在车轮上安装计数器记录车轮转动的次数，从而了解车子前进了多少。对于转弯的情况，可以从内外轮子的计数差得到转弯的角度。假设内轮转了 \(e_i\) 圈，外轮转了 \(e_o\) 圈，内轮半径 \(r_i\)，外轮半径 \(r_o\)，则有 \[ e_i = \theta r_i \\ e_o = \theta r_o \] 这里 \(\theta\) 就是车子转动的角度，上面的方程可以解得 \[ \theta = \frac{e_o - e_i}{r_o - r_i} \] 然后就能根据转动角度更新车辆当前的位置了。

这种方法用车辆本身的坐标系统记录位置，虽然实现起来简单但是测量精度非常局限于测量误差。例如上例中轮子打滑或事漂移都会导致结果不准确。更成熟的方案需要结合地图信息。

地图定位 (Map Registration)

可以用下面三张图来来介绍地图定位问题，左图是当前的区域地图，中间是激光测距传感器得到的结果，地图定位的目的就是根据传感器返回的结果判断机器人当前坐标和朝向，右图就是一个理想的结果。

配合第三周讲的占据栅格地图障碍物的概率 \(m(x, y)\)，我们可以定义最佳定位结果应该满足 \[ \max_p \sum_r \delta(p_x + r\cos(p_{\theta} + r_{\theta}), p_y + r\sin(p_{\theta} + r_{\theta})) \cdot{m(x,y)} \] 接下来介绍两种解决地图定位的方法。

粒子滤波 (Particle Filters)

粒子滤波（有没有觉得这个术语的中文翻译很科幻）又称为序列蒙特卡洛 (Sequential Monte Carlo)，是一种非参数 (non-parametric) 模型。它用一系列样本（粒子）表示可能性分布。每一个粒子都是方差接近于 0 的高斯分布，这种分布又被称为狄拉克δ函数 (Dirac Delta)，采用这个分布好处之一是可以把连续数学中的工具应用到离散的结果中。

在地图定位问题中，粒子的状态代表位置和朝向，同时每个粒子分别有自己的权重。初始状态的粒子滤波分布由一开始的假设决定，可能是均匀分布，也可能是以某个点为中心的高斯分布。初始化完成后，重复以下步骤更新粒子的分布：

1. 根据里程计的信息更新粒子的状态。
2. 由于里程计本事有不确定，更新每个粒子状态的时候可以加入里程计带入的噪音，通常也是一个高斯分布。
3. 从每个粒子更新后带噪音的分布中采样。
4. 根据距离传感器得到的信息，更新每个粒子的权重（例如由传感器得知前方近距离有障碍物，而某个粒子并没有，那么这个粒子的权重都会大幅降低）。
5. 这样得到的结果可能会有有效粒子过少的问题，需要重新采样。有效粒子的数量可以用 \(n_{effective} = \frac{(\sum_i w_i)^2}{\sum_i w_i^2}\) 表示。
6. 重新采样的方法就是根据权重重新从粒子集中独立抽取同样数量的粒子，注意这里高权重的粒子可能会被多次抽取。重复抽取的粒子会在下一轮更新时因为里程计噪音再次分散。
7. 重复步骤，直到粒子集中在某一状态。

迭代最近点 (Iterative Closest Point)

粒子滤波的缺点之一在于高维度中，需要大量的粒子才能保证理想的分布。ICP 算法可以更好的适应高维度的场景。

如图所示，ICP 的目的在于已知测量结果和地图，要求出左侧测量结果如何旋转移动后，可以和右侧的地图局部吻合。这里主要有两个问题，一是旋转和移动矩阵，二是测量点和地图点的对应关系。具体的 ICP 算法可以参考这篇论文，它的大致思路和第一周提到的解高斯混合模型的 EM 算法很接近：

1. 初始化旋转 (R) 和移动 (t) 矩阵。
2. 固定 R 和 t，优化点的对应关系：\(y_i = \argmin_{y_j \in Y} \Vert x_i - y_j \Vert\)。
3. 固定点的对应关系，优化 R 和 t：\(R, t = \argmin \sum_{x_i, y_i \in C} \Vert d(x_i, y_i) \Vert ^2\)。
4. 重复 2 和 3，直到稳定。

作业

这次的作业是实现一个粒子滤波，应该是整个课程最麻烦的一次了。问题本身不算难，尤其简化了动力学模型之后。但是调参比较麻烦，尤其是最后提交的那个地图，容易卡在某个转角跑不出来。

动力学模型方面，我一开始假设机器人位置和朝向的变化量和前一次接近，移动一次粒子之后再添加噪音。这个方法在机器人变向的时候容易位置偏离过多导致粒子失效，后来注意到作业的 Tips 里面建议假设机器人不动，利用高斯噪音移动粒子，这样的话相当于就不需要针对动力学模型做任何操作了。

计算每个例子的得分时，一种做法是用上一周的作业中用到的 bresenham 函数计算发出点到障碍物中间所经历的空白格，然后对每个空白格计算加权，但是这个做法实在太慢了，我最后计算得分时只用了障碍物所在格的状态。

关于粒子的数量，我看到网上有一种做法是设置一个得分的阈值（例如 70% 的障碍物要正好打到墙上），如果所有的粒子都没法超过这个阈值，就重新再跑一次。这么做容易在测量不准时卡死，而且和书中的实现有出入，在现实中会导致粒子滤波每次估计位置时使用的时间不稳定。比较好的做法还是把粒子的数量和高斯分布的参数放在一起调，跑偏了可以看看是因为粒子不够还是分布参数有问题。

作业里其实有两个地图，样例地图比较容易过（可能是参数变化不大）。提交用的地图调参要不少时间，我看了自己的输出以后，发现有几个点的运动变化很大，有可能是这几个点的测量本身也不精确。另外两个地图用来标记墙和空白方格的数值也是不一样的。

小结

至此 Robotics Estimation and Learning 这门课就上完了。课程设置不错，但是讲解不够详细，尤其是第二周和第四周，这小哥讲得太简单了，slides 上还有不少错误。推荐《Probabilistic Robotics》这本书，在上课的时候参考了里面一部分章节，写得很详细，作者 Thrun 也是机器人领域的大神。

全课程的笔记链接

• Robotics Estimation and Learning 的课程主页
• 第一周笔记：高斯分布
• 第二周笔记：卡尔曼滤波
• 第三周笔记：地图
• 第四周笔记：定位

这一周的内容和地图有关，最后的作业就是通过传感器的数据创建一个地图。

地图类型

常见的题目类型有三种：

1. 度量地图 (Metric Map)：地点用坐标表示，例如用经纬度表示地点的世界地图。
2. 拓扑地图 (Topological Map)：表示地点之间的逻辑关系，例如图论中图的概念，以及地铁图。
3. 语义地图 (Semantic Map)：用标签描述的地图，通过位置关系描述被标记的地点，例如景点游览图。

在现实中绘制地图有几个难点，一是测量误差会导致坐标不精确，二是设备本身需要不断地移动才能绘制，三是地图本身是对现实世界的反应，会不断的变化。

占据栅格地图 (Occupancy Grid Map)

栅格地图用二维栅格表示整个环境，每个栅格都有一个概率值表示这个栅格是否有物体存在。绘制栅格地图常用的设备之一是测距传感器，通过发出激光并测量接受反射所用的时间，传感器可以了解前方障碍物的大致距离。

如图所示，传感器本身测量存在误差，我们只能认为在传感器正前方给定距离处有一定几率存在障碍物。对于这种测量有误差的环境，我们再次引入贝叶斯模型描述。记 \(p(m_{x, y})\) 为 (x, y) 格中存在障碍物的概率的先验知识，根据测量的设备模型我们可以得到条件概率 \(p(z | m_{x,y})\)。\(p(z=1|m_{x,y}=1)\) 就代表栅格中有障碍物，且检测成功的概率，而 \(p(z=1|m_{x,y}=0)\) 则代表栅格中不存在障碍物，但是却检测到障碍的概率（假阳性）。

根据贝叶斯公式，我们可以得到测量之后的后验概率 \[ p(m_{x,y}|z) = \frac{p(z | m_{x,y}) p(m_{x,y})}{p(z)} \] 为了简化计算，引入 \(Odd(X) = \frac{p(X)}{p(\neg{X})}\) ，则有 \[ Odd(m_{x,y} = 1 | z) = \frac{p(m_{x,y} = 1 | z)}{p(m_{x,y} = 0 | z)} = \frac{p(z | m_{x,y} = 1) p(m_{x,y} = 1)}{p(z | m_{x,y} = 0) p(m_{x,y} = 0)} \] 其中最后一步可以代入贝叶斯公式得到。对 \(Odd\) 求对数，则有 \[ \begin{align} \log \frac{p(m_{x,y} = 1 | z)}{p(m_{x,y} = 0 | z)} &= \log \frac{p(z | m_{x,y} = 1) p(m_{x,y} = 1)}{p(z | m_{x,y} = 0) p(m_{x,y} = 0)} \\ &= \log \frac{p(z | m_{x,y} = 1)}{p(z | m_{x,y} = 0)} + \log \frac{p(m_{x,y} = 1)}{p(m_{x,y} = 0)} \end{align} \] 令 \(\log{odd\ meas}\) 表示 \(\log \frac{p(z | m_{x,y} = 1)}{p(z | m_{x,y} = 0)}\) ，上式可以简化为 \[ \log odd(m_{x,y} = 1 | z) = \log{odd\ meas} + \log odd(m_{x,y} = 1) \] 如果用 \(\log{odd}\) 表示栅格的状态，这一状态可以简单的通过加减来维护。当检测到障碍物时，该栅格的 \(\log{odd}\) 增加 \(\frac{p(z=1 | m_{x,y} = 1)}{p(z=1 | m_{x,y} = 0)}\)，没有检测到障碍物时，该栅格的 \(\log{odd}\) 减少 \(\frac{p(z=0 | m_{x,y} = 0)}{p(z=0 | m_{x,y} = 1)}\)。初始状态为 0，即 \(odd = 1\)。

下图为一个具体的例子，第一个栅格地图为 t1 时刻的状态，做了一次探测后，经过的空闲栅格的 \(\log{odd}\) 减少 0.7（这个值由传感器决定），而最后的障碍物所在格的 \(\log{odd}\) 增加了 0.9。第三个栅格地图为 t2 时刻更新后的状态。

三维地图

常见的三维传感器：

• 三维测距传感器 (如 Lidar)
• 双目相机 (Stereo Camera)
• 深度相机 (Depth Camera)

地图的数据格式也有多个方案：

• 栅格表示：查询单个栅格的状态非常快，但是占用大量内存，而且因为离散化一部分信息会丢失。
• 列表表示：节省了内存，也不会因为离散化丢失信息，但是查询时需要线性扫描。
• 树状表示：查询比列表快 (O(logN))，同时内存占用不大。
• k-d tree：每次选择一条坐标轴，把空间对半分。查询和维护都能在 O(log n) 内完成。
• octree：把空间均等分成八块，在存在点的分块中继续递归细分。

作业

这次的作业是根据一组 Lidar 测量结果绘制一个二维地图。输入包含四个参数（这里 K 为扫描总次数，N 为 Lidar 光线数）：

1. t 数组记录每组数据的时间点，大小为 \(1 \times K\)。
2. ranges 数组记录每次测试各条激光线测得的距离，大小为 \(N \times K\)。
3. scanAngels 数组记录每条激光线相对机身的转角，大小为 \(N \times 1\)，每次测试时这个转角不会变化。
4. pose 数组记录每次测试时机器人在地图中的位置，大小为 \(3 \times K\)，三行数据分别是坐标 x y 和相对地图的转角。

我实现的方法没有用向量并行，用了两层循环依次处理每次测试的各条光线。在 i7 6700K 上大概 25 秒可以跑完最终测试，测试程序里会提到整个过程可能要五分钟，性能差一点的机器这个时间里面应该也能跑完了。

最后跑地图的时候，注意 example_test.m 里传给 occGridMapping 的参数只取了前 1000 次测量结果，所以要制作完整地图要把这个限制去掉。另外文档里面坐标转换时用了 ceil，我在本地测试时只能拿到 27/30 分，换成 round 就能到满分了。

全课程的笔记链接

• Robotics Estimation and Learning 的课程主页
• 第一周笔记：高斯分布
• 第二周笔记：卡尔曼滤波
• 第三周笔记：地图
• 第四周笔记：定位

这一周主要讲卡尔曼滤波 (Kalman Filter)，视频讲得比较简略，slides 做得里也有不少错误。最后看了一些其他网站的文章和视频才有了比较深刻的理解。参考资料推荐在本文结尾。

卡尔曼滤波 KF

卡尔曼滤波可以从一系列包含噪音的观测数据中，估计出每个时间点系统的状态。KF 有几个基本假设：

1. 当前状态只和前一状态有关，且和前一状态线性相关，即 \(x_{t+1}=A_t x_{t} + B_t u_t + \epsilon_t\)，这里 \(x_t\) 是状态向量，\(u_t\) 为控制向量，\(\epsilon_t\) 是均值为 0 的高斯分布噪音。
2. 测量结果和状态线性相关：\(z_t = C_t x_t + \delta_t\)。这里 \(z_t\) 是测量结果的向量，\(\delta_t\) 表示测量噪音。
3. 最初状态也呈正态分布。

基于高斯分布的假设，我们可以用贝叶斯模型描述状态 \[ p(x_{t+1}|x_t) = Ap(x_t) \\ p(z_t|x_t) = Cp(x_t) \]

加入运动和观测误差导致的不确定性 \(v_m\) 和 \(v_0\) \[ p(x_{t+1}|x_t) = Ap(x_t)+v_m \\ p(z_t|x_t) = Cp(x_t)+v_0 \]

假设误差基于高斯分布 \[ p(x_{t+1}|x_t) = A\mathcal{N}(x_t, P_t) + \mathcal{N}(0, \Sigma_m) \\ p(z_t|x_t) = C\mathcal{N}(x_t, P_t) + \mathcal{N}(0, \Sigma_0) \]

把线性变换 A 和 C 代入正态分布 \[ p(x_{t+1}|x_t) = \mathcal{N}(Ax_t, A P_t A^T) + \mathcal{N}(0, \Sigma_m) \\ p(z_t|x_t) = \mathcal{N}(Cx_t, C P_t C^T) + \mathcal{N}(0, \Sigma_0) \]

线性加和 \[ p(x_{t+1}|x_t) = \mathcal{N}(Ax_t, A P_t A^T+ \Sigma_m) \\ p(z_t|x_t) = \mathcal{N}(Cx_t, C P_t C^T + \Sigma_0) \]

接下来讲如何估计这两个高斯分布的参数。

最大后验概率估计卡尔曼滤波

最大后验概率估计的目的在于最大化后验概率 \(p(x_t | z_t)\)，即在对 \(x_t\) 有一个预测（先验），同时获得了观测结果 \(z_t\) 之后修正 \(x_t\) 的值，用符号表示有 \(\hat{x_t} = \argmax_{x_t} p(x_t | z_t)\)

由贝叶斯公式 \[ p(x_t | z_t) = \frac{p(z_t | x_t) p(x_t)}{P (z_t)} \] 代入正态分布得 \[ \hat{x_t} = \argmax_{x_t} \mathcal{N}(Cx_t, \Sigma_0) \mathcal{N}(Ax_t, A P_t A^T+ \Sigma_m) \] 令 \[ \begin{align} P &= A P_{t-1} A^T + \Sigma_m \\ R &= \Sigma_0 \end{align} \] 代入多元高斯分布（参考第一周笔记）把两个分布合并后求导，或者利用边界条件概率公式，可解得 \[ \begin{align} \hat{x_t} &= (P^{-1} + C^T R^{-1}C)^{-1} (C^T R^{-1} Z_t + P^{-1} A x_{t-1}) \\ \hat{P_t} &= (P^{-1} + C^T R^{-1}C)^{-1} \end{align} \]

接下来根据 Woodbury 矩阵求逆式 (Woodbury Matrix Identity)，可以得到 \[ \hat{P_t} = P - P C^T (R^{-1} + C P C^T)^{-1} C P \] 令 \(K = P C^T (R + C P C^T)^{-1}\)，有 \(\hat{P_t} = P - KCP\)，\(\hat{x_t}\) 简化过程如下 \[ \begin{align} \hat{x_t} &= (P^{-1} + C^T R^{-1}C)^{-1} (C^T R^{-1} z_t + P^{-1} A x_{t-1}) \\ &= (P - KCP) (C^T R^{-1} z_t + P^{-1} A x_{t-1}) \\ &= A x_{t-1} + P C^T R^{-1} z_t - K C A x_{t-1} - KCP C^T R^{-1} z_t \\ &= A x_{t-1} - K C A x_{t-1} + (P C^T R^{-1} - KCP C^T R^{-1}) z_t \\ &= A x_{t-1} - K C A x_{t-1} + K z_t \end{align} \]

这里 K 就是卡尔曼增益 (Kalman gain)。

扩展卡尔曼滤波 (Extended Kalman Filter)

KF 的局限之一在于假设了线性模型，EKF 去掉了线性模型的限制，可以处理更一般的状态变化函数 \[ \begin{align} x_{t+1} = A x_t + B u_t &=> x_{t+1} = f(x_t, u_k) \\ z_t = C x_t &=> z_t = h(x_t) \end{align} \]

于是协方差的预测变成了 \[ p(x_{t+1}|x_t) = \mathcal{N}(f(x_t), \frac{\partial{f}}{\partial{x}} P_t \frac{\partial{f^T}}{\partial{x}} + \Sigma_m) \] 卡尔曼增益为 \[ K = P \frac{\partial{h^T}}{\partial{x}} (\frac{\partial{h}}{\partial{x}} P_t \frac{\partial{h^T}}{\partial{x}})^{-1} \] 更新方程为 \[ \begin{align} \hat{x_t} &= f(x_{t-1}) + K(z_t - h(f(x_t))) \\ \hat{P_t} &= P - K \frac{\partial{h}}{\partial{x}} P \end{align} \]

无迹卡尔曼滤波 (Unscented Kalman Filter)

EKF 的局限之一在于只是对非线性的变换做了近似，用泰勒级数展开后取一阶项，容易产生导致较大的误差。UKF 采用了确定性的取样方法来近似高斯分布，这个取样方法又被称为无迹变换 (Unscented Transformation)。

Unscented Transformation

UT 可以用来计算非线形变换后随机变量的分布情况。考虑 L 维随机变量 x 和非线性的函数 \(\pmb{y} = f(\pmb{x})​\)，假设 x 的均值为 \(\bar{\pmb{x}}​\)，协方差矩阵 \(P_x​\)。为了计算 \(\pmb{y}​\) 的分布情况，我们根据下面三个式子创造一个维数为 2L + 1 的 sigma 矩阵 \(\pmb{\mathcal{X}}​\)： \[ \begin{align} \mathcal{X}_0 &= \bar{\pmb{x}} \\ \mathcal{X}_i &= \bar{\pmb{x}} + (\sqrt{(L + \lambda)\pmb{P}_x})_i && i = 1, \dots, L \\ \mathcal{X}_i &= \bar{\pmb{x}} + (\sqrt{(L + \lambda)\pmb{P}_x})_{i - L} && i = L + 1, \dots, 2L \end{align} \] 这里 \(\lambda = \alpha^2(L + \kappa) - L\) 为调节参数，\(\alpha\) 决定采样点围绕均值的扩散程度等参数。下标 i 表示矩阵的第 i 列。这里的 \(\mathcal{X}_i\) 也被称为 sigma 向量，通过非线性函数后转变到同一个矩阵中： \[ \mathcal{Y}_i = f(\mathcal{X}_i) \]

\(\pmb{y}\) 的均值和协方差就可以通过对 \(\mathcal{Y}\) 矩阵列的加权求和获得了 \[ \begin{align} \pmb{y} &\approx \sum_{i=0}^{2L} W_i^{(m)} \mathcal{Y}_i \\ \pmb{P}_y &\approx \sum_{i=0}^{2L} W_i^{(c)} \{\mathcal{Y}_i - \bar{\pmb{y}}\}\{\mathcal{Y}_i - \bar{\pmb{y}}\}^T \end{align} \] 其中权值 \(W_i\) 的定义为 \[ \begin{align} W_0^{(m)} &= \lambda / (L + \lambda) \\ W_0^{(c)} &= \lambda / (L + \lambda) + (1 - \alpha^2 + \beta) \\ W_0^{(c)} &= W_0^{(m)} = 1 / \{ 2(L + \lambda) \} & i = 1, \dots, 2L. \end{align} \] 下图很好地解释了上述几个式子的变换过程

Unscented Kalman Filter

接下来回到 UKF。介绍了 UT 之后 UKF 就容易多了。首先构造一个包含初始状态和噪音的矩阵 \(\pmb{x}_k^{\alpha} = [\pmb{x}_k^T \pmb{v}_k^T \pmb{n}_k^T ]^T\)，这里三个向量分别为状态向量、控制向量和噪音向量。接下来对这个矩阵应用无迹变换获得 sigma 矩阵 \(\mathcal{X}_k^{\alpha}\)，之后就回到了普通 KF 过程。具体的状态转移公式可以参考本文结尾参考资料《Kalman Filtering and Neural Networks》一书中的章节。

作业

这周的作业是用卡尔曼滤波预测一个小球运动 10 帧之后的位置。理解了卡尔曼滤波后做起来不难，定义好动力学矩阵 A 和测量矩阵 C，接着根据上面的公式计算卡尔曼增益 K、新状态的均值和协方差矩阵，再通过新状态的位置和速度计算 10 帧之后的位置就好。

调参方面有一些小技巧，一开始测试的时候可以先给 \(\Sigma_m\) 设一个很大的值，同时给 \(\Sigma_0\) 设一个很小的值，这样每次算出来的位置都应该是测量出来的位置，否则代码里可能有 bug。接下来就可以根据生成的预测图来调整 \(\Sigma_m\)，肉眼估一下坐标的误差范围（注意到 y 的变化速度比 x 的慢很多），然后根据坐标误差算一下速度误差。测量误差根据文档可以给一个 0.01 - 0.1 的参数。

参考资料

• How a Kalman filter works, in pictures：这篇是最推荐的，作者还用不同颜色标记各个变量，看起来一目了然。
• Kalman Filter 学习笔记：上文的中文版。
• 《Probabilistic Robotics》一书第三章，pdf 版可以在这里下到。
• Michel van Biezen 的 Kalman Filter 视频：https://youtu.be/CaCcOwJPytQ 比较长，一共有 55 集，但是讲得很细致。
• The Extended Kalman Filter: An Interactive Tutorial for Non-Experts：EKF 的介绍网站，只要求高中数学基础。
• The Unscented Kalman Filter for Nonlinear Estimation: UKF 论文。
• 《Kalman Filtering and Neural Networks》第七章：EKF 和 UKF 的详细介绍。

全课程的笔记链接

• Robotics Estimation and Learning 的课程主页
• 第一周笔记：高斯分布
• 第二周笔记：卡尔曼滤波
• 第三周笔记：地图
• 第四周笔记：定位

Prime Day 的时候入了一套 Sous Vide （真空低温烹饪，读作 soo veed）装备，周末在家尝试了龙虾，味道很不错。

先上最后的效果图：

烹饪过程并不麻烦，只是中间低温煮的时间比较长，具体步骤如下：

1. 剪开龙虾壳
2. 把龙虾肉从壳里推出，在肉中加入盐和胡椒
3. 把龙虾肉推回壳内
4. 放入真空袋中，加上黄油和柠檬，把袋抽成真空
5. 用 Sous Vide 控制水温在 140°F (60 °C)，放入龙虾煮 1 小时
6. 1 小时后取出龙虾，把袋口剪开，龙虾放在烤架上
7. 再次加上黄油后用火焰喷枪烧烤龙虾外层，完成美拉德反应
8. 加胡椒和葱，摆盘

装备 / 工具篇

这里用到的工具有

• Anova Culinary Sous Vide Precision Cooker：带 WiFi 和蓝牙连接。
• LIPAVI 水浴容器：只有容器不含盖子，我们买的是 12 夸脱的，因为烧不同东西要不同温度，没法放在一起煮，所以 12 夸脱绰绰有余了。容器、容器盖和架子分开买的时候注意大小要配套。
• LIPAVI 水浴容器盖：LIPAVI 的盖子和容器是分开卖的，盖子上有一个插 Sous Vide 的缺口。
• LIPAVI 水浴架：LIPAVI 三件套。注意尺寸。
• FoodSaver 真空包装机：我们买的是 2400 系列，做 Sous Vide 完全够用了。量大的也可以考虑 4800 系列。
• 烧烤架：我买的尺寸是 Large，但是到手后发现有点太大了不方便，估计 Medium 就可以。
• EurKitchen 的火焰喷枪：需要单独购买丁烷。加州不允许网购丁烷，但是 Walgreens 里面有卖丁烷瓶，可以在 Walgreen 官网上找到哪家店有以后跑过去问店员要（不在货架上）。
• Weston 的真空食品袋：真空包装机买来送了几个食品袋，用完了可以买这个。

其他可以考虑入手的工具

• Bernzomatic TS8000 火焰喷枪：前面 EurKitchen 的喷枪火力一般，尤其在处理牛排的时候不是很给力。这个喷枪配合下面的喷枪头特别适合处理牛排。
• Searzall 喷枪头：架在火焰喷枪上，煎烤效果更均匀。

二月中旬开始装修房子，做了不少智能家居的研究，分享一下。坐标湾区，项目目前还在计划和购买阶段，欢迎拍砖，欢迎种草。

家居中控

中控协议是要先决定的一项，因为选定以后就优先考虑支持这个协议的设备了。 现在比较热门的有 Z-Wave、Zigbee 和 Insteon。Zigbee 和 Z-Wave 走的是网状 (mesh) 网络，每一个设备都可以作为中继节点传播信号，所以家里支持这一协议的设备买得越多，信号覆盖就越好。Insteon 除了和 Z-Wave 类似的无线信号外，还可以从电力线直接发送信号，理论上会更稳定些。Insteon 的灯光控制开关做得比较好，不少人因为这个在灯光开关上选择了 Insteon。Zigbee 相比 Z-Wave 是一个更开放的协议，用的频段和 Z-Wave 互不冲突。Z-Wave 的最大优点在于支持的设备类型非常多，窗帘、门锁、灯光都有不少支持的设备。所以最后我还是决定用 Z-Wave 为主的无线控制。

选好协议后就是决定控制中心了，没有花太多时间研究，选了支持 Z-Wave 的 Smart Things，主要是因为它的用户社区很活跃，产品迭代也比较快。

语音控制我选了 Alexa (Echo)，出来早，支持的产品多，和 Smart Things 的对接做得也很好。Echo 目前有三个产品，语音功能上都一样，主要是携带性以及音响效果的差别。买几个 Dot 在常去的房间里保证语音控制覆盖就好。

另外可以考虑买一块平板挂在墙上当全屋的控制器，有个叫 SmartTiles 的应用，本质上是一个网页，可以用来控制 Smart Things 的各种功能。

照明

照明灯的远程控制主要有两种方案，一种基于智能开关，一种基于智能灯泡。

基于智能灯泡的方案的最大问题在于设备事实上一直都处于带电状态，对于多路开关控制电灯的场景，需要在每个开关位置边上放一个不走电的无线开关，同时还要避免和物理开关混用，导致设备电源被切断的情况。除非从一开始决定就只用假开关，不在墙上布置多路电开关，否则墙上开关的数量就会多不少，在使用时也容易按错。

而基于智能开关的方案则解决了这个问题，因为把无线开关做进了电开关，所以使用的时候就可以像用普通多路开关一样。智能开关的另一个好处在于成本相对便宜，一个无线调光开关的价格大概在 $50 左右，而一个智能灯泡价格在 $15 左右，对于装 6 个顶灯的大厅来说无线开关的方案会便宜点。

基于智能灯泡的方案的好处在于一些灯泡可以调色温，甚至不同颜色，此外每个灯泡还可以单独控制。对于卧室这种不需要多路开关，而且关灯可以只用手机或者语音的房间，我还是选择了黄白双色的 Hue，这样可以白天用白灯，晚上切换成昏黄的灯光。

具体选购方面，智能开关以前一般推荐 GE 的无线调光开关，不过最近 Homeseer 出了一款新的无线调光开关，相比 GE 的优势在于支持实时状态更新。多路无线开关要买配套的开关。此外不同的灯泡对无线调灯开关的支持不一样，Homeseer 官网上有一份兼容性列表可以参考。

Hue 还有个灯带产品，也挺好玩，可以考虑放在厨房橱柜的顶端做照明。

音响

我在大厅、饭厅、厨房和厕所的天花板都装了无线音响，厨房和厕所的音响需要注意买防潮的。

走线方面，楼上的音响线都绕到一个储物柜里，楼下的音响线都绕到储物间（有网关）。音响线记得要买 CL2 或者 CL3（出于防火考虑），同时如果音响线超过 50 尺，得换用 14 AWG 的厚度。

音源方面，我的计划是买几个 Sonos CONNECT:AMP 分别控制这几个房间的音乐。由于 Sonos 的功放太贵了，打算先把音响和走线搞定了，到时候再一个个买。另外可以考虑把相邻两个房间（比如饭厅和客厅）的音响连到一个 Sonos 功放，不过得确保音响的阻抗是 8 欧姆的。

另外 Sonos 现在有个问题是还不支持 Alexa，不过公司已经明确表明要好好做这个功能了。

Crutchfield 上有几片文章讲得很详细，分别关于音响和排线，可以参考。

电动窗帘

每天醒来能吼一声让 Alexa 拉开窗帘的感觉应该不错，所以我们很想装个可以远程控制的电动窗帘。做电动窗帘的小公司不少，但是大多数都是用传统的红外控制，这就意味着如果要把它接入到家里的控制网络，还得单独买一个 Z-Wave 到红外的发射器。

最后看下来 Lutron Serena 和 Somfy 两套系统比较靠谱。不过 Serena 不支持 Z-Wave，只好放弃。Somfy 似乎不直接卖窗帘杆，而是和一个专门卖窗帘的品牌 Bali 合作，在卖窗帘的同时提供电动控制的选项。

Bali 电动窗帘可以在两种供电模式里面选择，一是用 8 节 AA 电池，可以用12 到 18 个月；或者插座供电。虽然可以在窗帘杆边上加个新的插口，不过还是觉得接电线的方案太丑了，也没有理性的隐藏方案，所以决定还是用更折腾的电池方案。

无线覆盖

研究了三种解决方案：传统的无线扩展器，Eero 和 Orbi。传统的扩展器方案似乎稳定性不咋的，而且还要花时间设置。Eero 和 Orbi 的主要区别在于 Orbi 的主从设备之间用了独有的信道传输，所以理论上不会影响 WiFi 信道的性能；Eero 支持所有设备连接有限网络从而增强信号。因为是重新装修，每个房间本来就会提供网线接口，Eero 的这个特性就很有用。

家庭影音

没研究别的方案，家里本来就有个 Logitech Harmony，而且对 Smart Things 的支持也很好，所以就继续用了。Harmony 现在最大的好处就是看完电视不用再找遥控器了，用语音就能关掉。

另外推荐一个联想的迷你键鼠 N5902，很适合用来当 HTPC 的遥控，不过好像已经停产了。

安全与其他

视频监控方面选了 Arlo Pro，优点在于可以户外使用，有 7 天免费云存储，也可以备份视频到本地。Arlo Pro 有个延迟的问题，为了省电它会在红外感应到有人进入检测区域后才开始录像，所以可能会有几秒的延迟。网上也有很多人因为这个原因最后放弃了 Arlo。不过我在目前的租房里面试了下，放好相机的位置可以把延迟缩短到 1 秒左右。

门锁还没仔细研究，不过应该会用 Schlage 的电子锁。话说这套 193x 年的老房子，外面铁门的锁从来没换过，居然也是 Schlage 的。

车库门应该也有无线的选项，不过也还没仔细研究。

暖气控制应该会买 Ecobee3，因为家里的供暖系统是统一的，没法按房间分别控制。Ecobee3 可以在不同房间安装感应器保证有人在的房间的温度稳定。

最近一直用 iA Writer 做笔记，用不同的文件保存不同的主题，由于 iA Writer 并没有很好的管理和浏览功能，于是就想做个 Web 工具方便浏览和管理。

markdown-wiki 是我用 Sinatra 做的一个简单的预览工具，它可以把某个目录下的 Markdown 文件以 Wiki 的形式呈现出来。界面上借用了 Ghost 的 CSS，可以在 http://markdown-wiki-demo.herokuapp.com/ 预览（因为是非本地的内容，上方的 Edit 按钮没有作用）。

Markdown 语法方面，由于用了 redcarpet 所以有不少语法扩展，包括代码块、删除线、下划线、上标等，另外包含了 Wiki 内部链接支持。

安装说明

1. 下载源代码
2. 安装 Ruby 和 bundle
3. 在项目目录下运行 bundle install
4. 将 app.rb 中的 WIKI_ROOT 改成 Markdown 文档所在的目录
5. 运行 mac/webeditor opener.app

安装后在项目目录下运行 rackup（如果要限制只能本地访问可以运行 rackup -o localhost），并访问 http://localhost:9292 即可。

本地编辑器（目前只支持 Mac 系统）

在网页上打开本地编辑器的功能是通过 URL Scheme 实现的，mac/webeditor opener.app 会将 wikieditor:// 注册给一个 AppleScript，后者负责运行 iA Writer 并打开相应的文件。mac/ 下已经包含了预先打包好的 app 文件，如果你需要修改 AppleScript，可以打开 mac/webeditor opener.scpt，编辑完成后点击 File -> Export，在 File Format 中选择 Application，并将 mac/Info.plist 放到新生成的应用包中。

如果在打开 iA Writer 时提示权限问题，请先在 iA Writer 中手动打开一次需要编辑的文件，之后就能顺利编辑这个目录下的所有文件了。

其他功能

目前功能比较简单，有几个接下来考虑加入的功能：

• 文本搜索
• 目录支持
• 其他编辑器的支持

源代码在 GitHub 上，欢迎提供建议和 Pull Request。

北美求职记系列文章

• 北美求职记（一）：Microsoft
• 北美求职记（二）：Google & Facebook
• 北美求职记（三）：Hulu & Twitter

最近签掉了 offer，找工作的事情算是告一段落。在这里写一点面试体验和心得，希望对有兴趣去北美工作的朋友有所帮助。

先简单介绍下自己，国内硕士在读，明年毕业，没有牛 paper，也没参加过 ACM-ICPC 竞赛。在实验室做过内核、虚拟机和 Android 底层相关的研究工作，接过一些网页和移动开发的外包，2011 年开始在字节社兼职负责后台开发。另外也经常上 Stackoverflow 和 GitHub。

这次决定直接申请美国的职位后，由于心里没底，不知道国外公司招聘的难度，所以一开始投了很多公司。几个大公司都找人内推或者直接投了，小公司也投了不少，比如 Foursquare、Path、Pinterest 和 Square 等都试了。当时甚至在手机上找了一圈应用，把可能涉及后端开发的应用都投了一遍。不过大多数公司都没给我安排面试，最后 Microsoft、Google、Facebook、Twitter 和 Hulu 这五家公司愿意给我面试机会。

一般来说，国内毕业后直接投国外公司，会比出国留学毕业后找工作的难度大一些。除了语言因素之外，我了解到的主要原因在于工作签证，出国留学毕业后可以通过 OPT 签证入职，之后再过渡到 H-1B 签证。而国内毕业的学生只能通过 H-1B，这意味着要等到第二年的十月份才能入职。好在 Google、Facebook 等公司不太介意这个问题，还是会欢迎国内的应届生申请。

校招的 HR 一般会有各自的职责。比如 technical sourcer 负责发现有希望进入自己公司的应届生；recruiter coordinator 会帮助 recruiter 安排面试者的面试时间、面试官，以及 onsite 面试时帮助面试者订机票和酒店；staffing consultant 则负责发 offer 以及介绍公司的具体福利制度，并解释面试者相关的问题。不同公司的 HR 职责的分法自然也不一样，我在 Facebook 的面试过程中只和两位 HR 联系过，而在微软的面试过程中则联系过五六位 HR。

在面试流程方面，相比我了解到的国内公司的面试，国外公司的面试安排上会更人性化一些。例如安排面试时间时，HR 一般会先让你给出几个空闲的时间点，然后他们再从这些时间中给你安排面试。此外在为你安排 onsite 的住宿时，也会询问你有没有相关的要求。

关于面试题目，大多数公司都比较侧重面试者对基本的数据结构和算法的掌握程度，以及把这些内容实现为实际代码的能力（一般会要求你选一个语言实现，而不允许用伪代码）。越是规模大的公司越注重这些基本功，而小公司除此之外还会考察你的开发经验，例如对某个框架的了解和性能优化方面的技巧。关于这一点区别我的理解是大公司里面会有自己的框架和开发工具，面试者的基本功好就能比较快的上手；而小公司一般用社区现有的工具，所以已有的开发经验可以直接用在将来的工作中。

下面是这几个公司的面试细节，有些公司因为在 onsite 面试的时候签了 NDA，所以没法透露具体的面试题，还请见谅。

Microsoft

微软是我最早投的公司之一，托了在微软总部工作的一位学长帮忙内推。面试包括一轮 HR 面和四轮 onsite 面。

申请了一个多月后一直都没有反应，直到微软国内招聘的前一天，北京的 HR 打电话问我是不是投过微软的职位，要我参加第二天上海站的笔试。

笔试过后，又过了一个多月，收到了微软一位招聘人员的邮件，问我是不是对微软北美的职位有兴趣，要我填一份基本情况的问卷，里面有问到其他公司的面试进度。我当时已经收到了 Google 和 Facebook 的面试邀请，就如实填写了。回复第二天后就收到了邮件通知，告诉我会有 HR 进一步跟进。第三天有一位 HR 联系我和我约电面的时间。微软约电面的方式和其他公司不大一样，HR 会给出很多个选项，让你在里面选择几个空闲的时间。另外值得一提的是这些时间都转成北京时间了，这也是微软在安排面试时比较人性化的一个地方。

第一轮面试是 HR 面。HR 先问了一些技术无关的问题，比如喜欢做什么，工作地点的偏好，什么时候开始学的编程，为什么投了微软等等。接着是一些智力题，比如 9 个小球，8 个质量相等，另一个比其他的重，如何用天平称两次把它找出来；公司开发了一种新键盘，有哪些测试它的方法；在会议室内怎么估计室外的温度。都是些更像是考验英语水平而不是技术能力的问题。

面完第二天收到了 onsite 的通知。虽然是北美的职位，onsite 面试地点却是在上海。我参加的是周日的面试，和我一起参加面试的还有一位学生，他之前在微软实习，了解到这次有去北美工作的机会后也想尝试下。面试官是从总部飞过来的工程师，一共有四位，其中三位都已经是 principal 级的了。HR 提到一般技术面试要五轮，因为我们之前参加过一轮笔试，所以只需要面四轮。

onsite 面每一轮的过程都差不多，都是面试官自我介绍，接着我介绍自己和做过的一些项目，然后开始技术问题，最后是我提问的环节。微软的面试问题会考察面试者编码、设计和测试三方面的能力。

coding 环节要求直接在白板上写代码，我被问到两个 coding 问题。一是如何检查一棵二叉搜索树是否正确，二是写一个解数独的程序。第一个问题写起来很快，第二个问题因为时间有限，我先写了一个没啥剪枝的暴力搜索的版本，写完后和面试官分析了可以在此之上做的优化。

设计方面的问题有两个。第一个问题是设计一个分布式的数据管理系统。使用场景可以是一个连锁店信息的记录系统，每个分店都有可能更新自己的信息，并把这些改动传播到整个系统中。在设计这一系统的同时要考虑性能、容错、一致性等要求。我一开始想了一个基于 push 的机制，在面试官指点下逐步优化，最后还是有不少问题。于是干脆重新设计了一个基于 poll 的系统，优化改进之后面试官满意了。

另一个设计问题和类的设计有关，要求设计一个包含图形界面的棋盘游戏。因为之前做过不少相关的开发，所以这一部分我还挺擅长的。按照 Single Responsibility 的原则设计了几个分工明确的类，另外把网络对战和 AI 接口都考虑进去了。设计完成后面试官要求我从用户鼠标单击这一事件开始介绍整个控制流程，在某些类中还会问及这么设计的原因，以及和其他设计方案相比的优缺点。

测试部分的问题也有两个。第一个问题是如何测试一个随机函数。第二个问题和分布式系统有关，面试官先向我介绍了一个分布式系统，包括它的使用场景和基本的架构，然后问我其中某一个部件应该如何测试。提到正确性、可伸缩性、一致性和容错性后再给出相应的测试方法应该差不多了。

onsite 面试后的第二天后就收到了 HR 的邮件，祝贺我拿到了 offer，并和我约时间谈具体的 offer 细节。虽然微软一开始拖了两个多月才开始安排面试，但是一旦开始面试后他家的效率非常高，是这次面试的几家公司里效率最高的了。

The Definitive Guide to Xen Hypervisor 第二章的 Exercise，通过调用 hypercall page 中的 console_io 项输出Hello World。

void start_kernel(start_info_t * start_info)
{
    HYPERVISOR_console_io(CONSOLEIO_write,12,"Hello Worldn");
    while(1);
}

但是默认选项编译和启动的Xen是不会保留DomainU中输出的信息。参考 drivers/char/console.c，可以看到主要有两个选项控制了 DomainU 的 do_console_io 输出：

#ifndef VERBOSE
    /* Only domain 0 may access the emergency console. */
    if ( current->domain->domain_id != 0 )
        return -EPERM;
#endif

if ( opt_console_to_ring )
{
    for ( kptr = kbuf; *kptr != ''; kptr++ )
        putchar_console_ring(*kptr);
    send_guest_global_virq(dom0, VIRQ_CON_RING);
}

在编译 Xen 的时候开启 debug 选项即可置上 VERBOSE，而 opt_console_to_ring 则是一个启动选项，在 grub 的启动选项中增加 loglvl=all guest_loglvl=all console_to_ring 即可。

重启 Xen 后就能通过 xm dmesg 看到 Hello World 了。

1. 准备工作

在开始分析Support Code之前，先配置下我们的Source Insight，使它能够支持.s文件的搜索。

在Options->Document Options->Document Types中选择x86 Asm Source File，在File fileter中增加一个*.s，变成*.asm;*.inc;*.s 然后在Project->Add and Remove Project Files中重新将整个oslab的目录加入，这样以后进行文本搜索时.s文件也不会漏掉了。

2. Source Insight使用

接下来简单分析下内核启动的过程，在浏览代码的过程中可以迅速的掌握Source Insight的使用技巧。

lib/multiboot /multiboot.s完成了初始化工作，可以看到其中一句call EXT(multiboot_main)调用了C函数multiboot_main，使用ctrl+/搜索包含multiboot_main的所有文件，最终base_multiboot_main.c中找到了它的定义。依次进行cpu、内存的初 始化，然后开启中断，跳转到kernel_main函数，也是Lab1中所要改写的函数之一。另外 在这里可以通过ctrl+单击或者ctrl+=跳转到相应的函数定义处，很方便。

3. irq处理初始化工作

来看下Lab 1的重点之一，irq的处理。跟踪multiboot_main->base_cpu_setup->base_cp u_init->base_irq_init，可以看到这行代码

gate_init(base_idt,  base_irq_inittab,  KERNEL_CS);

继续使用ctrl+/找到base_irq_inittab的藏身之处：base_irq_inittab.s

4. base_irq_inittab.s

这个汇编文件做了不少重复性工作，方便我们在c语言级别实现各种handler。

GATE_INITTAB_BEGIN(base_irq_inittab)  /* irq处理函数表的起始，还记得jump
table 吗？ */
MASTER(0, 0) /* irq0 对应的函数  */

来看看这个MASTER(0, 0)宏展开后是什么样子：

#define MASTER(irq, num)
GATE_ENTRY(BASE_IRQ_MASTER_BASE + (num), 0f, ACC_PL_K|ACC_INTR_GATE)  ;
P2ALIGN(TEXT_ALIGN) ;
0: ;
pushl $(irq) /* error code = irq vector  */ ;
pushl $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;
pusha /*  save general registers */ ;
movl $(irq),%ecx /* irq vector number */  ;
movb $1 << num,%dl /* pic mask for this irq */ ;
jmp  master_ints

依次push irq号，trap号（0x20+irq号），通用寄存器（eax ecx等）入栈，把irq号保 存到ecx寄存器，然后跳转到master_ints，master_ints是所有master interrupts公用 的代码。

跳过master_ints的前几行，从第七行开始

/* Acknowledge the  interrupt */
movb $0x20,%al
outb %al,$0x20

/* Save the rest of the  standard trap frame (oskit/x86/base_trap.h). */
pushl %ds
pushl  %es
pushl %fs
pushl %gs

/* Load the kernel's segment registers.  */
movw %ss,%dx
movw %dx,%ds
movw %dx,%es

/* Increment the  hardware interrupt nesting counter */
incb EXT(base_irq_nest)

/* Load  the handler vector */
movl  EXT(base_irq_handlers)(,%ecx,4),%esi

注释写得很详细，首先发送0x20到0x20端口，也就是Lab1文档上所说的发送INT_CTL_DON E到INT_CTL_REG，看来这一步support code已经替我们完成了。接下来保存四个段寄存 器ds es fs gs，并读入kernel态的段寄存器信息。

最后一句很关键，把base_irq_handlers + %ecx * 4这个值保存到了esi寄存器中，%ecx 中保存了irq号，而*4则是一个函数指针的大小，那么base_irq_handlers是什么呢？继 续用ctrl+/搜索，可以在base_irq.c中找到这个数组的定义 unsigned int (*base_irq_handlers[BASE_IRQ_COUNT])(struct trap_state *ts) 且初始时这个数组的每一项都是base_irq_default_handler

看来这句汇编代码的功能是把处理irq对应的函数地址保存到了esi寄存器中。 为了证实这一点，继续看base_irq_inittab.s的代码：

#else
/*  Call the interrupt handler with the trap frame as a parameter */
pushl  %esp
call *%esi
popl  %edx
#endif

果然，在保存了esp值后，紧接着就调用了esi指向的那个函数。而从那个函数返回后， 之前在栈上保存的相关信息都被恢复了：

/*  blah blah blah */
/* Return from the interrupt */
popl %gs
popl  %fs
popl %es
popl %ds
popa
addl $4*2,%esp /* Pop trap number and  error code  */
iret

这样就恢复到了进入这个irq处理单元前的状态，文档中所要求的保存通用寄存器这一步 其实在这里也已经完成了，不需要我们自己写代码。

好了，这样一分析后，我们要做的事情就很简单，就是把base_irq_handlers数组中的对 应项改成相应的handler函数就行了。 注意index是相应的idt_entry号减去BASE_IRQ_SLAVE_BASE，或者直接使用IRQ号。

另外这个数组的初始值都是base_irq_default_handler，用ctrl+左键跳到这个函数的定 义，可以看到这个函数只有一句简单的输出语句： printf(“Unexpected interrupt %dn”, ts->err); 而这就是没有注册handler前我们所看到的那句Unexpected interrupt 0的来源了。

5. struct trap_state *ts

所有的handler函数的参数都是一个struct trap_state *ts，这个参数是哪来的呢？ 注意call *%esi的前一行

/* Call the interrupt handler with the  trap frame as a parameter */
pushl  %esp

这里把当前的esp当作指向ts的指针传给了handler，列一下从esp指向的地址开始的内容 ，也就是在此之前push入栈的内容：

pushl $(irq) /* error code = irq vector */ ;
pushl  $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;
pusha /* save general  registers */ ;
pushl %ds
pushl %es
pushl %fs
pushl %gs

再看一下trap_state的定义，你会发现正好和push的顺序相反：

/* Saved segment registers  */
unsigned int gs;
unsigned int fs;
unsigned int es;
unsigned int  ds;

/* PUSHA register state frame */
unsigned int edi;
unsigned  int esi;
unsigned int ebp;
unsigned int cr2; /* we save cr2 over esp for  page faults */
unsigned int ebx;
unsigned int edx;
unsigned int  ecx;
unsigned int eax;

/* Processor trap number, 0-31. */
unsigned  int trapno;

/* Error code pushed by the processor, 0 if none.  */
unsigned int err;

而这个定义后面的

/* Processor state frame  */
unsigned int eip;
unsigned int cs;
unsigned int eflags;
unsigned  int esp;
unsigned int ss;

则是发生interrupt时硬件自动push的五个数据（参见Understand the Linux Kernel）

也就是说，ts指针指向的是调用当前handler前的寄存器状态，也是当前handler结束后 用来恢复的寄存器状态，了解这一点对以后的几个lab帮助很大。

p.s. 另外提一句和这个lab无关的话，非vm86模式下栈上是不会有v86_es等四个寄存器 信息的，所以以后根据task_struct指针计算*ts的地址时使用的偏移量不应该是sizeof( struct trap_state)

6. The End

这样差不多就把support code中处理interrupt的方法过了一遍（另外还有base_trap_in ittab.s，不过和irq的处理很相似）

了解这些后Lab1就比较简单了，不需要任何内嵌汇编代码即可完成。

写fork函数的时候发现实际传给trap handler的ts地址和用(struct trap_state *) (KSTACK_TOP(old))) - 1

计算出来的结果不一样，后者比前者小0x10。另外ts的实际地址加上ts的大小(92个字节)后就超出了内核栈的范围。

/*
 * This structure corresponds to the state of user registers
 * as saved upon kernel trap/interrupt entry.
 * As always, it is only a default implementation;
 * a well-optimized kernel will probably want to override it
 * with something that allows better optimization.
 */
struct trap_state
{
	/* Saved segment registers */
	unsigned int	gs;
	unsigned int	fs;
	unsigned int	es;
	unsigned int	ds;

	/* PUSHA register state frame */
	unsigned int	edi;
	unsigned int	esi;
	unsigned int	ebp;
	unsigned int	cr2;	/* we save cr2 over esp for page faults */
	unsigned int	ebx;
	unsigned int	edx;
	unsigned int	ecx;
	unsigned int	eax;

	/* Processor trap number, 0-31.  */
	unsigned int	trapno;

	/* Error code pushed by the processor, 0 if none.  */
	unsigned int	err;

	/* Processor state frame */
	unsigned int	eip;
	unsigned int	cs;
	unsigned int	eflags;
	unsigned int	esp;
	unsigned int	ss;

	/* Virtual 8086 segment registers */
	unsigned int	v86_es;
	unsigned int	v86_ds;
	unsigned int	v86_fs;
	unsigned int	v86_gs;
};

可以看到在trap发生时硬件自动push的eip cs eflags esp ss后还有四个v86的数据，而通常的trap过程中这些数据是不会被push到内核栈的，而这四个数据的长度正好是0x10，也就解释了为什么计算出来的地址和实际的地址有偏差。

折腾了一下午加晚上，看了一堆包后总算把HTTPS协议搞定了，趁热写点心得。

这个Lab很强大，把11 12 13三章的内容全串起来了。

HTTP部分很简单，读个请求头把主机分析出来（有现成的函数），然后把客户端的所有请求传给Web服务器，再把服务器的所有反馈信息传给客户端就行了。另外注意传信息的时候不要使用Rio_readlineb之类的函数，而要用Rio_readnb，否则传图像时会碰到问题。

另外把版本统一成HTTP 1.0能明显的提高代理服务器的速度，具体原因还不清楚，明天再问问。

如果要把这个代理服务器写得健壮一点，要注意各种异常的处理，比如通常浏览器都能发送正确的报头，但是如果有人通过telnet发送了错误的报头也要能够正确的释放内存再结束线程。

然后是线程，这个问题也不大，使用信号量实现互斥锁，另外在即时free资源就好。

最后就是HTTPS协议的处理了，由于没正确理解文档的意思，在这上面花了很多时间，不过倒也接触了不少新东西。

首先是用gdb调试多线程程序，使用info threads查看当前所有线程，然后thread #切换到该线程就能查看那个线程的相关信息了。

然后来说下HTTPS协议的处理。一开始我有个错误的概念，就是代理服务器的责任是把所有客户端的信息转发到服务器端，把所有服务器端的信息转发到客户端，或者说在浏览器的眼中代理服务器和普通的Web服务器没有区别。其实并非如此，在我用OmniPeek截包看了半天后才意识到自己错了 =_=

浏览器不通过代理进行HTTPS连接时，只发送加密后的数据；而通过代理服务器时，先告诉代理服务器相关信息，然后再发送密文。另外，HTTPS的明码报头一般不会像文档中那样只有一行，代理服务器要记得所有的明文都读进来（但不转发给Web服务器），然后回复HTTP/1.0 200 Connection established，最后再负责密文的转发。

HTTPS的数据转发也和HTTP不一样，它需要客户端和服务器端多次的双向数据传输。而默认的read方法在没有信息读取和其他中断发生的时候是会block的。对于这个问题我的解决方法是结合I/O Multiplexing和Non-blocking I/O（搜资料的时候看到过这样处理的效率也比较高，见http://www.kegel.com/c10k.html）。用fcntl设置两个file descriptor的模式为O_NONBLOCK，然后再用select/poll实现multiplexing即可。不知道还有没有更好的方法。

另外测试HTTPS时建议使用https://mail.google.com，文档中的两个网页貌似firefox都打不开的。