7.markdown

9. 杂项

• 关于GC
  • .Net的Generational GC第0代默认选择256K，因为这是L2的大小
  • JVM的分代GC概念
    • 三代
      • Young generation
        • Eden, 空间x8
        • Survivor from, 空间x1
        • Survivor to, 空间x1
      • Old generation
      • Permanent generation
    • 分配的时候，在Eden和Survivor from上，一旦满额，就应用Copying GC的机制拷贝到Survivor to中，如果Survivor to空间不足，则拷贝到Old generation中。典型的，Young generation的一次GC希望回收90%
    • 如果只对Young generation回收，则称为minor GC；否则称为major GC或full GC
    • Old/Permanent generation对Young generation的引用通过card table来标记
• 几种GC的对比
  • mark and sweep
    • 复杂度：标记阶段是O(a)，这里的a是活跃对象；清扫阶段是O(n)，需要遍历每个对象
    • 指针不被搬移，地址稳定，可以利用memory pool，比如tcmalloc
  • copying gc
    • 复杂度：O(a)，只处理存活的对象。因此对于第0代这种回收率极高的场合，非常适合
    • 指针搬移，GC完毕后需要更新所有对象、以及栈上寄存器/临时变量中的的指针；或者总是用Handle来访问
    • 分配迅速，只是freeOff的加法
  • mark and compaction
    • 一般4趟：
      1. 根据reachable graph，遍历标记
      2. 遍历整个堆，为每个存活对象计算新地址，保存在对象头的forward字段中
      3. 遍历整个堆，对于每个存活对象，遍历其中的每个引用字段，将字段值替换为旧指针对应的forward值
      4. compaction
    • 复杂度O(n)，因为需要多次遍历所有的块
    • 指针搬移
    • 分配迅速，加法
• 对于variant/any/object的概念，常见的实现方案包括，tagged union和tagged pointer，以及object指针
• C++中的转型
  • 对于有符号、无符号，姑且允许直接用C-style转换
  • 对于class/struct指针，一定要用static_cast等C++-style转型，因为后者包含了更多的类型信息，可以在编译期检测出逻辑错误
    • 比如，对于A和B这两个类型，你期望他们有继承关系，所以用static_cast来处理指针转换，但由于人为失误，他们没有继承关系，这时，C++编译器会检测出该static_cast使用非法；如果你确实要在两个没有继承关系的指针间转型，就应该确实的使用reinterpret_cast。此为利用类型信息发现逻辑错误的典型
• 在Scheme解释器中统一数据和代码的方式(跟quote有关)
  1. 代码和数据是同一格式，比如用Scheme、Python来写解释器，代码和数据都用list表示。浓浓的FP味儿
  2. 代码是经过词法寻址后的优化形式，而数据是纯粹的列表，(eval (quote ...))的时候，需要将列表编译优化过的代码形式。实际的高性能解释器方案
• 关于实现Scheme解释器的几个层次
  1. 递归解释器，宿主语言(解释器的实现语言)不支持尾调用优化(如Python/C#/Javascript): Scheme程序轻易栈溢出(尤其考虑到Scheme中用递归表达循环的风格)
  2. 递归解释器，宿主语言支持尾调用优化(如C++/Lua)，或者将eval手工改为尾递归优化形式(修改eval参数后goto到函数开始): Scheme程序中的尾递归函数不再栈溢出，但大量的非尾递归仍然溢出(如cons)
  3. 递归CPS解释器，或者用普通的递归解释器解释经过全文CPS变换后的Scheme程序：不再有栈溢出
     • 这里有一个考虑，用户自定义函数肯定是CPS风格了，那内置函数呢？DS风格？慢了。如果内置函数和自定义函数都需要作为高阶函数传给map等函数作为参数呢?
  4. 字节码解释器，使用ADT的stack来实现脚本栈而不再是复用native栈：不再溢出
     • 在输出的字节码中插入tail指令，进行tail call optimization，性能提高显著
• Python的tuple赋值左端，可以当做一个简单的模式匹配器使用
• 关于VCPS
  • 用于做迭代器很方便
  • 对于递归CPS解释器来说，要求宿主语言支持尾调用优化，如果不支持的话，如C#，就需要写成VCPS风格。但其实无需全文都写成VCPS风格，只需要在几个关键点，如求值application时将最后一步apply给换成(cons args k)即可
    • 经实测，这将VCPS的中间pair结构数量下降到1/4
• 全文CPS变换程序中用到的CPS本身的一个技巧：
  • k(result)的返回值仍然可以进一步处理！即还可以包裹一层ctx！如(ctx (k result))
  • 合理利用k的返回值，在特殊场合下可能大幅简化程序！
• 4类lambda环境模型
  1. 堆环境：如Scheme、Javascript的原始模型
     • 调用一个函数的时候创建一个新环境块儿，所有局部变量都放在里面；在该作用域内创建函数时，会保存整个局部环境作为free varaible寻址用
     • 没有块级作用域
  2. 堆变量
     • 每个局部变量都是Ref的引用，创建函数时，函数会引用它以及它内嵌的子函数需要的free varaible的Ref引用。Ref通过引入了一个间接层，让局部访问以及free variable访问都能共享的作用到其他作用域，因为只保存了一份数据，所以所有引用总是同步更新
     • 支持块级作用域
     • 相当于lua模型的一个简化
     • 栈环境+堆环境：如C#的lambda
       • 分析局部变量中会作为free varaible被引用的集合，在进入函数体过后就创建heapEnv对象，对于非free varaible局部变量，总是通过stack[i]来访问，而对于会被内层引用的变量，总是通过heapEnv[i]来访问。创建函数的时候保存heapEnv对象。
       • 该方案比堆环境模型更优化，但同样不支持块级作用域
     • 栈变量+堆变量：如Lua
       • 局部变量放在栈中；当创建函数时，对于函数及内嵌函数需要引用的free varaible，创建upValue对象，其内包含一个局部变量地址；当退出作用域时，利用close指令，将当前深度的作用域对应的所有的upValue给close掉，即将栈指针指向堆中
       • 支持块级作用域
     • 对于不支持块级作用域闭包的语言，如Scheme、C#
       • Scheme中的循环是递归风格，总是创建新环境，块级作用域的问题不明显
       • 对于C#、Go、Javascript，总是可以通过(function() {})()来模拟块级作用域。尤其是在动态语言/类型推导完备的静态语言中特别好用
     • 在一个经过CPS全文变换的程序中，有两类函数
       1. 原始代码中的函数，现在全为CPS风格，即总有一个k参数
       2. 变换引入的k函数。原始码中透明、无法访问
     • 递归的数据结构还是递归算法最自然
       • 比如parser
       • 比如迭代
     • C/C++的实参求值顺序不定！
     • 在一个Copying/Compaction GC系统中，保存裸指针是危险的，除了应该确保指针可达外，还应该总是通过类似Handle的间接层来访问指针
     • 加速解释器一个方法是为常用操作提供专门指令、降低解释开销。如
       • load0, load1, loadnil
       • loadlocal0, loadlocal1, loadfree1, loadfree2
       • tjmp, zerojmp, niljmp, eqjmp, lessjmp
       • inc, dec
     • 字节码解释器中，也可以将callstack隐式的放入evalstack中
     • 关于yield、async/await，可以通过实现first class stackframe来实现
       • 需要提供的支持:
         1. 原语stackframe: 利用函数对象及实参，创建stackframe对象
         2. 原语yield: 将callstack顶上的stackframe弹出
         3. apply时除需要支持native function、script function，还需要支持stackframe对象作为operator
       • 在该机制下，(+ 2 3)等价于((stackframe + 2 3))；对于不包含yield的函数，后者等价于前者，如果包含yield，那么就不同了，可以先(stackframe f 2 3)得到stackframe对象，再多次apply
       • 相对的，coroutine需要first class stack的支持。
     • 关于抽象解释
       • 将值域缩小到特定范围后的解释过程
       • 例子
         • 编译。环境是符号表，值域是代码
         • 静态分析。环境是符号表，值域是类型等规则
         • 类型系统。环境是符号表，值域是类型
         • 正负号的求值系统。环境是符号表，值域是+-0
         • 解释代码求evalstack深度。环境是符号表，值域是深度
         • CPS变换：环境是上下文，值域是变换后的代码
         • 寄存器分配: 环境是寄存器使用上下文，值域是寄存器名
     • 关于dynamic scoping
       • 作用域查找，即确定变量在哪个作用域，叫scoping
       • 作用域查找即变量位置查找，叫addressing
       • 所谓lexical adderssing，是指能够通过源码推断出变量的地址，即编译期寻址。是一种eager binding
       • dynamic scoping，是指在运行时进行变量定位，分两种:
         1. 基于execution context查找。这里的execution context即env chain。比如Javascript的with
         2. 基于calling context查找。即基于调用栈帧查找。比如Common lisp中的dynamic scoping
     • 在支持first class function的语言中编写递归，应该注意避免函数体依赖函数名，特殊用法除外(如memoize)
       • 对于javascript，有named function expression
       • 对于scheme，有named let；其他语言类似
     • Javascript经验
       • 少用for-in
         • 基于prototype的OB/OO用法，for-in会遍历prototype中的类方法，多半不是你想要的结果。必须结合hasOwnProperty
         • 用for-in遍历数组很慢，得到的索引i甚至可能是字符串！
       • 对于值类型Number/Bool，尽量不要扩展prototype，因为2.method可能会被处理成new Number(2).method，而2 === new Number(2)是false的，所以会有坑...
       • 在JS这种语言中，应该逆向遍历
         • a.length如果作为结束条件，那么每次迭代都要进行属性访问，哪怕是inline caching，都会更慢
         • 如果遍历的是IE中的NodeList，那么a.length是COM对象的属性访问，超慢...
       • Douglas Crockford的JS编码建议
         1. 只用===和!==，而不是==和!=
         2. 不用with。它会破坏lexical addressing，在v8中测试，会比普通的属性访问慢几百倍
         3. 小心eval，它有性能问题和安全问题
         4. 总是使用function expression而不是function declaration，因为后者会自动提升，可能成为坑
         5. 永远不要出现new String(), new Number(), new Boolean(), new Object(), new Array()
       • 总是使用'use strict'
     • npm install -g pkgname可以安装包到全局；再通过npm link pkgname加到本地供require

     9. Javascript高级程序设计，读书笔记

     • ECMAScript的诞生是因为浏览器厂商的竞争，多个Javascript的行为不一致导致上层开发困难，才标准化
     • ECMA-262定义的ECMAScript与Web没有依赖关系，它只定义了语言的基础，不包括IO。常见的平台包括：
       • Web。DOM+BOM
         • DOM的标准化也是因为IE和Netscape关于DHTML的竞争
           • DOM1: XML和HTML
           • DOM2: 鼠标和UI事件、范围、遍历、CSS、视图
           • DOM3: DOM文档的加载和保存；DOM验证
         • 还有几种对应DSL的DOM标准
           • SVG
           • MathML
           • SMIL
         • BOM本身没有标准，只能针对浏览器适配。HTML5解决了这一问题，包括操作浏览器窗口和cookies等功能
       • Node
       • Adobe flash
     • <script>标签最好放到body最后，这样，加载script之前可以先显示其他元素，而不至于空白
     • 外部<script>的优点:
       • 可维护。比如版本控制
       • 浏览器可缓存，避免重复下载
       • 不需要内部<script>的一些注释hack等(比如<到底应该被当做小于还是tag的一部分)
     • JS编码风格
       • 用''来表示字符串。这样，JS代码片段可以被插入html属性的""中
       • 总是用;而非换行来分割语句，为了JS源码可压缩(移除空格和换行)。也算是对运行时JS parser性能有所帮助
     • DOM、BOM中的对象都是宿主对象，其行为不受ECMA-262约束。比如IE中的DOM对象就是COM
     • ECMAScript的Number是IEEE754规定的双精度浮点，但bitwise op是作用在32bit整形上的，JS解释器自动转型
     • JS和Java一样通过>>>和<<<来处理逻辑移位
     • 引用未定义变量会抛错，但if/短路逻辑中的未定变量引用，只要没执行就不抛错
     • 没有goto label，但是有break label、continue label
     • 关于属性枚举
       • obj.hasOwnProperty(), Object.keys(), Object.getOwnPropertyNames()，访问的都是instance proprety
       • for-in, in访问的是instance + prototype的property
     • JS的switch相当于if/elseif，因此case中可以出现任何类型和表达式(甚至是运行时表达式)
       • switch的case匹配用的是===
       • switch(true)，然后每个case都是test，是典型用法，用来代替if/elseif列表
     • 总是可以用arguments来访问实参；如果形参太多，那么多余的形参是undefined
     • 没有返回的函数，实际返回undefined
     • String是基本类型，不是Object的派生，因此不能添加属性
     • typeof和instanceof
       • typeof依据type tag，可以识别基本类型和object；虽然function实际上是一种callable的object，但为了方便使用，会返回'function'
       • instanceof依据prototype chain，而对象隐藏的prototype，是在new时绑定的。因此instanceof多用于OO
     • ECMAScript的全局环境，在Web上可以通过window来访问，在Node中通过global访问
     • 注意字典literal也是在new Object，因此它的prototype就是Object.prototype
     • object的属性名总是string
     • 在API设计中，可以用字典来整合optinal参数
     • a.length = n；可以直接扩展/收缩数组
     • 如果存在多个window/global对象的话，instanceof用来判断Array/String/Date就不靠谱了，所以应该用内置函数Array.isArray, Date.isDate等
     • Array.prototype.sort默认是基于对象的toString比较，因此一般都应该传入特殊的比较器
     • JS中没有块级作用域，var声明都会自动提升，效果等同于C语言中只能在函数开始声明所有变量
     • 写递归时，通过arguments.callee来递归比直接引用函数名或者function expression名字要慢很多
     • this是lexical addressing的，它和arguments一样，是隐含参数。如果调用方不是dot expression的话，函数体中的this就被初始化为window(严格模式中是undefined)
     • 严格模式下不能访问arguments.caller是出于安全考虑，避免访问调用方的源码字符串
     • eval访问的是全局环境(window/global)
     • Object.defineProperty访问属性，可以定义writable，getter/setter等
     • Object.preventExtensions禁止添加属性；Object.seal，进一步，禁止修改property的属性；Object.freeze，再进一步，不允许写属性值
     • 构造函数也只是普通函数，如果不用new而是直接调用，结果是将属性绑定在了window/global对象上
     • 对象内部持有的是new时刻的prototype，因此修改旧的prototype对象，对象行为改变；而修改构造函数的prototype属性，早创建的对象不受影响
     • 闭包实现的OO有属性的受限访问这个好处
     • JS中的常见对象模型
       • OB：设置构造函数的prototype，然后new
       • OO: 将派生类的构造函数的prototype设置为基类的对象，或者从基类构造函数的prototype中Object.create出来；派生类的构造函数要base.call(...)来初始化基类属性；最后new
       • Object.create，访问链，有点像运行时的with
     • JS的声明提升和Scheme中的不一样，前者相当于语句直接出现在了函数开头，而后者是被define被拆成了开头的define以及后面的set!；从正确性上来说，后者更容易理解，没坑
     • JS不支持块级作用域；但似乎全局环境下的块却是有局部作用域的...
     • JS中obj.method返回的不是bound function，需要手工bind
     • module模式很常见，避免了全局名污染
     • 引用没有声明的全局变量会抛错，但是window.name却只是返回undefined
     • 如果允许注册回调，不应该用callback != null来判断，而应该typeof callback == 'function'；即，总是用typeof/instanceof来确认变量是你要的；更进一步说，想要什么，要说明的足够清楚，不要含糊！
     • Array的slice、concat都可以用于clone
     • 对于行为类似的Array但设计不是Array的对象，可以尝试用Array.property.method.call(obj, ...)来访问；比如arguments、NodeList
     • bind支持currying，即除了绑定this外，还可以绑定其他实参
     • 一个技巧：resize会连续触发大量事件，但我们只应该执行动作一次，因此，通过clearTimeout和setTimeout来确保动作只执行一次，在最后一次事件被触发后执行
     • chrome里有profile工具
     • chrome里的window.performance.now提供高精度计时
     • JS源码压缩的一个方法：通过parser将所有变量名替换成短串，根据出现频率来分配串长度，最高频的名字被替换成单字母a,b,c,d等...
     • 用eval可以parse JSON，更严格的应该用JSON.parse
       • 可以用toJSON定义序列化到JSON的方法

     10. Haskell趣学指南

     • 1. 简介
       • 纯函数式编程语言 (purely functional programming language)
       • 惰性(lazy)
       • 静态类型(statically typed)
     • 2. 从零开始
       • 内置函数: pred, succ, max, min, +, -, *, div, mod
       • 函数声明和变量声明，都是=，区别只是有无参数
       • if e1 then e2 else e3
       • list
         • []为空表，相当于scheme的empty
         • :为插入，相当于scheme的const；而car、cdr则用pattern matching完成
         • ++连接两个串
         • list !! i引用第i个元素
         • [x,y,z]是x:y:z[]的语法糖。这个完全能通过自定义类型(data)来办到！
         • 内置函数: head, tail, last, init, length, null, reverse, take, maximum, sum, elem, sum, product
         • 内置函数: take, drop, takewhile, dropwhile, repeat, replicate, cycle
       • 区间(range)
         • 要求[a]中的a是typeclass Enum的instance
         • [first..last]
         • [first,next..last]，通过first、next可以构造步进
         • [first..]无限列表，利用lazy evaluation的特点
       • list comprehension
         • [x|x<-[1..10]] 单一变量
         • [x|x<-[1..10], x>10] 添加条件(predicate)，也叫过滤(filtering)
         • [x|x<-[1..10],y<-[1..10]] 多变量
         • [[x2|x2<-[0..x]]|x<-[1..10]] 嵌套。非特殊语法
         • [y|x<-[1..10],let y=x*x] 用let引入中间变量，此处非let表达式，其隐含的in是后面及开头
       • tuple
         • list要求所有元素同类型，可变长；tuple允许不同类型，但数量固定
         • (x,y...)
         • 内置函数: fst, snd。再多元素的话，用pattern matching提取
         • 内置函数: zip, zipWith
     • 3. Types and Typeclasses
       • 在ghci中，用:t看类型，用:i看信息，用:k看类型的kind
       • 常见类型: Int, Integer(允许无限精度), Float, Double, Bool, Char
       • Type varaible: 比如 Maybe a, [a]
       • 注意，typeclass只是静态类型的约束，不是实体类，不能用作函数参数、返回值类型
       • 内置typeclass
         • Eq: ==, /=
         • Ord: < <= > >=。另外compare操作Ord返回GT,LT,EQ。Ord是Eq的派生类
         • Show: 允许通过show转换为字符串
         • Read: 从字符串反序列化。使用read时可能需要用::进行类型声明
         • Enum: 可用于[first..last]，每个元素都有successer和predcesor
         • Bounded: 有上下界。可以通过minBound :: Int和maxBound ::Int来访问
         • Num: 数字特征。一般要求Show和Eq。包含实数和整数
         • Integral: 整数，包含Int、Integer
           • fromIntegral可以将Integral转换为目标类型a
         • Floating: 包含Float, Double
     • 4. 函数的语法
       • pattern matching
         • 语法
           • True/False/1/2/3/"+"等字面值
           • (a,b....)元组
           • (x:rest)列表
           • (constructor a b c d)匹配data的构造器
         • 利用all@(...)的特殊语法来访问匹配整体
         • 对于函数匹配，如果内部用了guard但没有找到对应项，会尝试匹配下个模式
         • case exp of pattern1->... pattern2->...，也是模式匹配
       • guard
         • 语法
           • funcname args | boolexp1 = body1 | boolexp2 = body2 ...
         • 一般最后一个谓词用otherwise，它永真
         • 如果条件未能捕获，则进行下个模式匹配
         • 对比pattern matching和guard，前者用于匹配字面值(常用作递归边界)、拆结构，后者用于匹配区间
       • 用字母定义、调用前缀函数，通过id来定义和调用中缀形式
       • 用特殊字符定义、调用中缀形式，通过infixr 7 +的形式来指定结合律和优先级；通过(+)来中缀访问
       • 关键字where
         • 放在函数尾部，能作用到所有的guard，但只能影响所在的pattern matching
         • 可以从上到下定义多个局部变量/函数(就像scheme的let*)，还可以为变量/函数加类型声明，就像顶层声明一样
       • 关键字let in
         • 是表达式
         • let的出现场合
           • let in表达式
           • list comprehension引入单一值(而非集合)
           • 在ghci中定义顶层变量/函数必须用let
           • do语句中
       • case exp of patterns...
         • 同函数的pattern matching，但是是表达式，可以用在各个场合
     • 5. 递归
       • 例子: 实现maximum, replicate, take, reverse, repeat, zip, elem, quicksort
     • 6. 高阶函数
       • 所有的函数都是curried function
       • 两个primary expressoin之间的空格其实是调用! 即lambda application，且拥有最高优先级
       • 参数不够的情况下，返回partial application
       • 中缀函数可以根据提供的左值/右值生成对应的partial application。用括号括起来的话，按前缀语法来算
         • -号要小心，因为-n会被当做相反数而非partial application，所以改用subtract n
       • flip，交换参数顺序
       • map, filter。尽管都能直接用list compreshension代替
       • foldl, foldr, foldl1, foldr1。后面两个表示初始值直接用第0项
         • scanl, scanr, scanl1, scanr1，类似fold，但是会返回累计的所有元素构成列表。有点像scheme中的stream
       • lambda。语法是\。一般加括号：(\x y->x+y)
       • 符号$，优先级最低，右结合，用来简化代码写法，减少括号
       • 符号.，function composition，优先级低，右结合，用来生成新函数
         • point free style(pointless style): 将函数定义改写成无参数的变量赋值，通过连续的.生成partial application
     • 7. 模块
       • 装载
         • import Data.List: 在当前环境中直接可见
         • import Data.List(f1, f2...): 只有f1, f2...可见
         • import Data.List hiding(f1, f2...): 除f1,f2...之外可见
         • import qualified Data.List: 必须通过Data.List.f1来访问
         • import qualified Data.List as List: 通过别名List.f1来访问
       • Data.List
         • intersperse v l2: 将v插入l2的每两个元素之间
         • intercalate l1 l2: 将l1整体插入l2的每两个元素之间
         • transpose: 将list的list转置
         • foldl', foldl1': strict版本(非惰性版本)
         • concat: 连接一组list
         • concatMap: 先map再连接
         • and: list中全为true则true。类似的函数all，接收predicate
         • or: list中有true则true。类似的函数any，接收predicate
         • iterate: 将函数反复作用于上次的结果，产生无穷序列。如iterate (*2) 1将生成[1,2,4,8,...]
         • splitAt, takeWhile, dropWhile.
         • span，在predicate为false的时候断开链，返回两个链；break，为true的时候断开
         • sort
         • group, groupBy
         • inits, tails. isIndexOf, isInfixOf，搜索一个list看是否包含子list
         • isSuffixOf, isPrefixOf
         • elem, notElem，都返回Bool
         • patition，返回两个list，第1个都符合条件，第2个都不符合
         • find，返回第一个满足条件的结果。返回Maybe
         • elemIndex, elemIndices, findIndex, findIndices
         • lines, unlines, words, unwords: 处理String非常方便
         • nub, nubBy去掉重复元素
         • delete v list: 去掉v的首次出现
         • \\集合差集
         • union, intersection, insert：操作集合(有序list)
         • sortBy, insertBy, maximumBy, minimumBy
       • Data.Char
         • isControl, isSpace, isLower, isUpper, isAlpha, isAlphaNum, isPrint, isDigit等
         • genericCategory，接收char，返回枚举，表示Space/Control等类型
         • toLower, toUpper, toTitle
         • ord, chr
       • Data.Map
         • empty
         • fromList, insert, insertWith, null, size, singleton, lookup, member, map, fitler, keys, elems
       • Data.Set
         • fromList, difference, union, null, size, member, empty, singleton, insert, delete
         • isSubsetOf, isProperSubsetOf
       • 建立自己的模块
         • module Name (f1, f2, ...) where
         • module Dir.Name (f1, f2, ...) where：允许层级
         • module Name (Type1(C1, C2), Type2(..), f1, f2, ...) where: 导出类型, 其中Type1(C1, C2)表示为Type1导出C1,C2两个构造子；而Type2(..)表示导出Type2的所有构造子
           • 只导出创建对象的静态函数，而不导出构造子，也是一种风格，只是用户将无法进行模式匹配
     • 8. 构造自己的Types和TypeClasses
       • data Type = Constructor1 ArgT1 ArgT2 | Constructor2 deriving(Eq, Show, Read)
         • 这里的Type只能用于类型的场合
         • Constructor可以用于表达式场合，用于创建Type类型的对象；也可以用于pattern matching的场合
         • 其kind是具体类: *
       • 由于Haskell完备的类型系统，应该和C++一样，不需要携带运行时类型信息，Bool/Int/Float/String等的对象都是纯数据；而Type类型的对象，就是Constructor ID(或者atom) + fields，需要携带Constructor ID用于模式匹配；即类型静态，但constructor动态，对象需要携带用于运行时识别
       • True/False/1/2/3/3.14/1.414/"abcds"/'a'等都相当于是Constructor
       • Just和Nothing是Maybe的constructor
       • data Type a = Constructor1 a Type1 ...: 即data的类型可以参数化
         • 典型的例子是Maybe/Either/[]
         • 其kind是: ->，即输入一个具体类型返回一个具体类型
       • 可以在data声明前为某个中缀constructor定义infixr 3 constructor1
       • 为避免大量的pattern matching来访问字段，提供record syntax
         • data Type = { field1::FieldType1, field2::FieldTyp2...}
         • 然后对于Type类型的对象，可以直接用函数field1、field2访问字段
       • type A = B，即type关键字用于声明别名，比如String就是[Char]的别名
       • 用class TypeClass type where ops来定义新的type class
         • 它只是一种类型约束，描述了generic types应该具有的方法，实际用作函数参数和返回的都是具体类型
         • 函数主要声明函数名和类型签名(type signature)
         • 可以用交叉定义，如x == y = not (x /= y)来减少类型实例实际应该实现的方法
           • instance类型必须定义的最小方法集合，叫minimal complete definition
       • 对于内置type class，可以直接deriving来实现
       • 对于其他type class，用instance TypeClass Int where ops来实例化，Int类型的哪一组函数实现了该type class
       • 注意区别，[]是一个variadic type, 而Num是一个typeclass；[a]是一个具体类型(kind为*)，而Num a只是一个类型约束声明
       • 可以用cons/car/cdr定义出自己的list，而使用起来(包括模式匹配)却几乎像[]一样方便!
       • 考虑实现一个针对任意内置类型的toBool函数，输入False/0/[]/Nothing返回False，其余返回True:
         • Haskell是静态强类型的，完全没有类型泄露，因此，必须想办法把Bool/Int/String/[]等具体类型携带到toBool的参数
         • 有两个办法:
           1. 声明typeclass ToBool，每个具体类型去实例化它，实现ToBool的接口toBool
              • 该方案其实是实现了重载的多个版本的toBool，针对每个类型，都有一个专门的函数toBool
           2. 声明data ToBool，利用Constructor(或者说运行时type tag)来区别各个类型，然后以ToBool作为toBool的参数，通过Constuctor进行匹配...
              • 该方法的缺点是，必须toBool (FromInt 3)；而如果要透明的toBool 3，其实又需要typeclass了(输入typeclass, 输出带constructor的data type)...总之，这是个思路
       • 一个案例Functor typeclass，它实例化的不是具体类，仍然是参数类，kind是*->*
         • Functor可以作用域[]/Maybe/Either等
       • 对比C++
         • struct Vector {float x; float y; float z;}
           1. data Vector = Vector Float Float Float
           2. data Vector = Vector { x::Float, y::Float, z::Float}
         • enum Weekday { Monday, Tuesday};
           1. data Weeday = Monday | Tuesday
         • tagged union: struct Variant { int type; union{ int i; float f; char *str; };};
           1. data Variant = FromInt Int | FromFloat Float | FromStr String
           • 注意这里用FromInt等constructor ID来代替type tag
         • polymorphism: struct IShape{}; class Rect: public IShape{}; class Circle: public IShape{};
           1. data Shape = Rect Float Float Float Float | Circle Float Float Float
           • 这里同样利用Rect/Circle等constructor ID来代替运行时类型信息
       • 编译期多态用typeclass(重载，等同于C++的模板); 运行时多态用data，用constructor作为类型信息，用pattern matching进行类型分派；如果实在需要可扩展的多态，那么，用Associative array等做类型映射吧
     9. IO
        • main函数的类型是 IO ()，表示返回空tuple的IO action；getLine是IO String，即返回String的IO action
        • 从main函数出发的IO action构成了一棵树(do关键字可以携带子树, AST)，解释器只会求值树上的语句。换言之，只有从IO action可达的语句才会被force求值，而其他语句则被lazy放过
        • do关键字可以将多个IO action打包成一个IO action。这里的子IO action可以包括
          • getLine, putStr, putStrLn等内置函数
          • 类型为IO()或者IO a的自定义函数，如main
          • 在do语句中，要从IO action中取值，用name <- ioaction
          • 在do语句中，用声明中间变量，用let name = expression
        • 要从形如IO a的IO action中取得值a，需要name <- ioaction
          • 如果手误写成 name = ioaction，其实这是又声明了一个类型为IO a的变量
        • return关键字，以表达式构造一个IO action，供外层函数<-，或者作为程序返回值
          • 它只是一个普通的类型为IO a的表达式，不带跳转语义(不是控制流)，所以应该作为tail call。出现在do中段的return看起来会很奇怪，因为实际上不会跳转...
        • do将源码级的多个IO action打包，而sequence将运行时的一组IO action打包，即输入[IO a]返回IO a
        • mapM f = sequence . map f
          • mapM是先map再sequence打包IO actiion的惯用法
          • forM和mapM一样，只是参数顺序不同，第1个参数是列表，第2个是将元素映射为IO a的函数
        • 其他几个函数
          • when函数。出自Control.Monad
          • forever，出自Control.Monad。循环执行一个IO action
        • Lazy IO
          • getContens，从标准输入中返回所有内容，但是是惰性的，所以可以利用输入缓冲。结合lines、words等函数威力强大
          • interact，接收一个函数，传入所有的标准输入字符串，返回IO a。常用
          • openFile -> hGetContents -> putStrLn -> hClose
            • IO相关的函数都有对应的hXXX版本, 如hGetLine, hGetChar, hPutChar, hPutStr
          • withFile，类似interact，不过可以指定文件，它隐藏了文件的打开关闭，直接传给回调文本内容
          • readFile, writeFile, appendFile, 直接传入路径，返回或写入字符串(当然要用<-提取返回值)
          • hSetBuffering, hFlush
          • openTempFile, removeFile, renameFile
        • 命令行参数
          • System.Envrionment
          • getArgs, getProgName
        • 伪随机数
          • typeclass RandomGen是随机数发生器, 而typeclass Random可以是各种Num类型
          • 可以用mkStdGen创建一个类型是StdGen、满足RandomGen的发生器
          • random，输入一个RandomGen(比如StdGen类型)，返回Random约束类型，如果分别用::Int, ::Bool, ::Float，可以分别返回不同类型的随机值
            • random同时还返回一个新的RandomGen，因此，RandomGen其实是函数式结构
          • randoms，根据一个RandomGen生成无限随机序列
          • randomR，可以指定一个tuple作为上下界，结果将在这个范围内随机
          • randomRs, 生成指定范围的无限随机序列
          • getStdGen，返回一个全局变量的StdGen，每次启动程序的时候都会不同
          • newStdGen，创建一个新的StdGen，同时还会更新全局StdGen，影响getStdGen的返回值
        • Bytestrings
          • 在IO的时候，输入输出String这个惰性list，性能太差，因为相当于每个字节都有一个thunk，作为选择，可以改用Data.Bytestrings或者Data.Bytestrings.Lazy，前者是完全非惰性的，完整的加载进内存，后者是以64K为thunk单位的部分惰性数据结构
          • Data.Bytestrings以及Data.Bytestrings.Lazy中有IO相关的全套函数
            • 比如readFile, writeFile等
          • 当IO规模很大的时候，逐字节的lazy不划算，考虑用Bytestrings，可能有显著的性能上的提升
          • pack, unpack, 在Bytestring和Word8的[]间转换
          • fromChunks, toChunks，在惰性和strict版本间转换Bytestring
          • Bytestring有Data.List相似函数，比如head, tail, init, null等
        • Exception
          • 在pure functinal部分，建议用Maybe、Either来进行异常处理
          • doesFileExist可以判断文件存在
          • 在IO部分，用catch来处理异常
            • 可以用isFullError, isEOFError等谓词来进行异常过滤
            • 可以用ioeGetFileName从异常中抓取文件信息
            • 用userError、ioError来重新抛出异常
     10. 函数式地思考来解决问题
         • 逆波兰求值器，能求值"2 3 * 4 -"
     11. 函数式地思考来解决问题
         • Algebraic data types和typeclass，分别可以提供runtime polymorphism和compile time polymorphism
         • 所谓Functor
           • map/filter/fold可以用在[a]上，极有威力，能不能将这组操作延伸到任意类型呢？即将map/filter/fold作用到F a类型上? Functor、Applicative Functor、Monoid(针对mappend操作)、Foldable，就是干这些事的
           • Functor，就是指可以被应用map操作的类型，即，凡是能被map over的类型，就可以通过实例化(instance)Functor这个typeclass，来实现对fmap的支持
             • 在C++里，要实现fmap函数对不同类型进行不同操作，其实就是template specialization；在Haskell里，一个函数只能声明成针对约束类型(即参数类型是某typeclass的实例)的操作，如果要进行特化，那么，需要声明一个新的typeclass，将操作声明为typeclass的method，最后，不同类型分别去instance这个typeclass以实现函数的overload(或者说，类型的polymorphism)
           • Haskell中，用f <$> obj来表示将类型为a->b的函数f应用到类型为F a的对象obj上，返回值的类型为F b
           • 应用在函数上，等价于function composition
           • Functor laws
             1. 对一个Functor做fmap id，结果应该等于原Functor
             2. fmap (f1 . f2) functor，结果应该等于fmap f1 $fmap f2 functor
             • 一个简单的Functor laws的反例: Functor类型是F Int a，其中Int用来记录fmap被应用的次数，这样，该Functor有了状态，并会随fmap改变，所以破坏了Functor laws
         • 所谓Applicative
           • Applicative的目的是，在Functor支持的单参函数的map基础上，支持多参函数对任意类型的应用，比如，将a->b->c应用到F a和F b上返回F c。方法是，利用Haskell默认的curring特性，实现F a->b应用到F a返回F b
           • Applicative的操作符是<*>，常见用法是(+) <$> Just 2 <*> Just 3
           • 利用Applicative，对Maybe/List Functor等应用多参函数，相当于归并多路数据；如果对一组function Functor应用多参函数，会返回新函数，新函数现将参数分流到多路function Functor上，最后再利用多参函数汇总
           • 对List Applicative应用多参函数，很容易实现list comprehension的效果
             • 注意list comprehension的枚举list个数是编译期的，利用递归，我们可以做到运行时的枚举个数。比如permutation、combination、queens算法，既可以使用两项的list comprehension，也可以使用两参数的applicative style
             • 借助ZipList这个newtype，可以在applicative style中进行zipWith操作而非list comprehension
           • 在不拆包的情况下对容器类型表达式进行<$><*>的编码风格，叫做Applicative style
           • liftA2 f a b等价于f <$> a <*> b
         • 利用Functor、Applicative，很容易对任意类型应用操作，而不需借助模式匹配拆包
           • 换句话说，对Functor、Applicative应用单参、多参函数，输入、输出在原容器类型空间(即输入输出都在F a中的F中)。有没有看到Church numeral时的似曾相识感觉?
           • 用在Maybe/IO上特别方便！
         • data vs type vs newtype
           • data可以创建任意类型(用C++的观点来看，其实就是tagged union，其中constructor就是tag，而后缀的字段部分，是union)
           • type仅仅是为一个已有类型提供别名，文本级别的，对type system完全透明，即不会在类型系统中引入新类型(用C++的观点来看，就是typedef)
           • newtype，引入编译期类型，该类型仅存在于类型系统中，运行时完全透明，等价于原类型。目的是，让同一类型能够重载一个typeclass多次，分别提供不同实现；即完全是为了重载引入的机制
         • 所谓Monoid
           • Monoid是指针对某项操作满足结合律并且有一个0元的类型
           • 支持mempty和mappend两个操作，任意类型如果支持两个值的叠加，都可以instance Monoid的实例
           • 借助Monoid，可以通过foldMap实现fold
           • 常见的实例包括[a]、Sum a、Product a、Any(描述两个Bool结合的方式)、All、Ordering(a==EQ则返回b，否则返回a，用于字典序比较等)等
     12. 来看看几种Monad
         • 所谓Monad
           • Monad本意是为了给表达式中的值附加隐藏属性(计算上下文，ctx)，从而给计算提供额外可能；而不同的计算方式，通过类型来区别，每种类型通过instance一个Monad的实例，从而实现不同的计算方式
           • 在一个Monad computation序列中(通过>>=和>>连接，或者作为do notation中的语句)，拥有额外运行属性的值，叫做monadic value；特定序列中，monadic value的类型是固定的，在这个上下文中的其他类型都是非Monad类型(尽管在另一个计算中该类型可能作为monadic type)，不会有隐藏属性
           • 在特定序列中，针对非monadic value类型的操作，用空格、$、.来连接operator和operand；而针对monadic value的操作，要用<$><*>连接；对monadic value的操作，需要在该Monad类型的instance中定义隐藏属性的结合方式
           • 可以用return来将非monadic value转为monadic value，用<-来将monadic value转换为非monadic value
           • 一个>>=、>>序列的返回类型就是Monad类型；而do notation经过CPS变换后，也就是一个>>=序列，因此，一个do表达式本身也就是一个Monad类型的值
           • 相比普通的表达式计算，Monad提供了两种额外的能力
             1. Flow control的能力；因为>>=运算符其实是将前一个计算的结果应用到后续计算的continuation上，所以，通过不同类型的Monad实例，就可以提供不同的continuation的操纵方式
                • 比如，Maybe monad和Either monad(Error monad)，可以根据ctx的状态(即Monad类型的constructor)，判断是否还需要继续后续计算，它允许直接抛弃continuation从而结束后续计算；这实现了异常的控制流
                • 比如，List monad，可以将先前计算的所有结果，依次应用到后续计算上，从而提供non-deterministic的能力
                  • 还可以有其他变化，例如，简单的给每个可能值附加概率属性，只将概率大于0的值传给后续计算...
             2. 访问隐藏属性的能力
                • Maybe/Either/List monad的kind都是*->*，所以其隐藏属性是无状态的，而如果一个Monad的类型是*->*->*的话，那么其隐藏属性还可以持有状态，该状态可以被访问，包括读、写、读写访问
                  • 严格的说，Maybe/Either/List类型也是有状态的，只不过状态有限，只包括其constructor的枚举值；比如Maybe monad就是通过其constructor的枚举值来决定是否应该继续计算
                • 隐藏属性的只写能力(Writer monad)
                  • 该Monad类型至少应该是F s a，其中s是状态类型。于是>>=的类型就是F s a -> (a -> F s b) -> F s b。由于是只写，后续计算的continuation无需读隐藏属性，只需要输出隐藏属性，因此，在Writer monad的>>=实现中，只需要决定前导计算结果中的状态s1和continuation的输出中的s2，怎样结合到最终的monadic value中，默认的结合方式是mappend。
                  • 可以用于log等输出，比如记日志、记录函数调用次数等
                • 隐藏属性的只读能力(Reader monad)
                  • 该Monad类型至少应该是F s a，其中s是状态类型。由于>=的实现中，只能将值类型a传给continuation，没能显示的将状态一并传递，因此，要让continuation中的计算能够访问状态，只能是让continuation返回一个新函数，由该函数来接收隐藏状态作为参数，而该函数体中包含了后续计算的逻辑；由于隐藏状态不会更新，所以该函数的输出可以只是值类型b。因此，continuation的类型声明应该是a -> s -> b，而continuation的类型又在>>=中声明为a -> F s b，因此可以判断Reader monad的类型F s a应该是s -> a，即Reader monad应该是一个函数，它接收状态s并返回值a
                  • Reader monad其实只是隐藏了只读的状态，在计算能力上和为函数显示声明一个状态参数没区别，所以一般可以直接多声明一个状态参数来替代Reader monad的使用
                • 隐藏属性的读写访问能力(State monad)
                  • 在pure functional的环境中，更新一个状态，是通过输入旧状态并返回新状态来做的，即updateState操作的典型类型是s -> (s, a)
                  • 在ReaderWriter monad中，>>=的continuation需要访问状态，基于和Reader monad同样的理由，该continuation接收值类型a后应该返回一个函数，这个新的函数应该接收状态s并进行读写访问，由于状态可能更新，所以该新函数应该返回输出值和新的状态，于是，continuation的类型应该是a -> s -> (s, b)，由>>=的类型声明可以推断，ReaderWriter monad的类型F s a应该是s -> (s, a)，即他是一个函数，接收旧状态，输出值和新状态
                  • 在纯函数环境中，最繁琐的就是用immutable的数据结构来表达mutable的逻辑，因为这将涉及显示的状态更新和传递，而ReaderWriter monad通过将可更新状态类型隐藏起来，将状态的更新和传递动作放到>>=中，从而极大的简化了状态操作代码，提高了代码的可读、可维护性
                    • 这个动作用王垠wired、wireless的比喻来说，就是，纯函数中状态的更新、传递代码，被作为导线从地上埋到了地下(隐藏到了>>=中，也就是do notation的行与行之间)
                  • ReaderWriter monad可以被用来实现作用域，如this、global等，及其强大
                    • 用来隐藏随机数发生器
                    • IO monad可能也可以被实现为State monad
         • In functional programming, a monad is a structure that represents computations defined as sequences of steps. A type with a monad structure defines what it means to chain operations, or nest functions of that type together. This allows the programmer to build pipelines that process data in steps, in which each action is decorated with additional processing rules provided by the monad.[1] As such, monads have been described as "programmable semicolons"; a semicolon is the operator used to chain together individual statements in many imperative programming languages,[1] thus the expression implies that extra code will be executed between the statements in the pipeline
         • Many common programming concepts can be described in terms of a monad structure, including side effects such as input/output, variable assignment, exception handling, parsing, nondeterminism, concurrency, and continuations. This allows these concepts to be defined in a purely functional manner, without major extensions to the language's semantics
         • 在Monad的计算序列中(>>=和do notation)，如果pattern matching失败，会调用Monad instance的fail
         • guard的类型是(Monad m) => Bool->m，在为True时返回空tuple的Monad(即F ())，为False时返回fail；一般它被用于控制continuation
           • 当guard的predicate为False时，在Maybe/Either/Lis monad中，都会返回对应的中断控制流的monadic value
         • do notation的展开过程(CPS变换)
           • 将let的赋值号左边的ID和do剩余的语句组成一个函数(类型是a->F b，即>>=中的continuation)，以let赋值号右边的实参调用它。使用空格而非>>=调用，因此该行CPS不受>>=调度
           • 将<-左边的ID和do剩余的语句转换成一个continuation函数，以<-右边的表达式调用它，用>>=来调用。这里会应用monadic type定义的continuation控制，以及隐藏属性的更新、传递
           • 将expression的行(常见的是guard和tell等输出函数)，转换为expression >>= (\_ -> ...)。即，尽管continuation不会关心传递的值内容，但传与不传，还是重要的，这决定了continuation是否会被驱动，在Maybe/Either/List等Monad中比较明显。
         • Monad laws(单子律)
           • left identity: (return x) >>= f应该等价于f x。用monadic function来说，即return <=< f等价于f
           • right identity: m >> return(这里的m是monadic value)应该等价于m。用monadic function来说，即f <=< return等价于f
           • associativity: (m >>= f) >>= g应该等价于m >>= (\x-> f x >>= g)
             • 这意味着>>=满足结合律，所以直接使用>>=构造的左结合序列，和使用do notation的右结合序列，是等价的
         • monadic function composition: <=<
           • f <=< g = (\x -> f x >>= g)
         • Monad中的flow control、隐藏属性结合点，在>>=，或者说在do notation的行与行之间；因此do notation的行也就是属性访问、控制流的最小单元
     13. 再来看看更多Monad
         • Monad利用>>=和do notation来减轻我们对context的关注，而将精力放在value本身
         • 利用difference list来确保FP风格的linked list总是从后往前append(因为append每次会拷贝整个a链，因此在连续的append中将a链长度控制k而不是n，避免了算法空间复杂度退化到n^2)
           • 经测试，在Haskell中效果显著，而在Racket中效果不明显，为嘛？
         • 一些实用的monadic function
           • liftM: 相当于fmap，但不依赖于Functor的定义
           • lifetM2: 相当于liftA2，但不依赖于Applicative的定义
           • join: 用来减少context层次，减少层次的同时令外层的context和内层结合。用于List就是concat，用于Maybe/Either/Writer/State的时候...
           • mapM, forM:
           • filterM:
             • 一个典型用法, filterM (\x->[True,False]) [1..3]，就可以生成集合的所有子集啦
           • foldM:
         • 利用Maybe/Either monad进行错误处理. 书中的例子:
           • 走钢丝
           • Reverse polish notation中的错误处理，包括read失败、pattern matching失败等
     14. Zipper数据结构
         • 在纯FP中，对一个数据结构的任何一点的修改，都会生成一个新的结构(比如binary tree的insert会生成O(log n)个新节点)，而根据special locality原理，接下来的修改很可能还在上次修改点的附近，于是有了Zipper手法在FP语言中的应用
         • Zipper是一个pair，保存了结构的当前子结构，以及遍历信息(用于重建)；利用子结构和遍历信息，你可以继续任意方式的遍历、修改以及重建，这种手法降低了摊还的深访问、修改&重建开销
         • 考虑binary tree的zipper
           • 不使用Zipper，k次读开销是O(k * log n)；k次写的时间开销是O(k * log n)，空间开销是O(k * log n)
           • 使用Zipper，k次相邻位置读的开销是O(log n + k - 1); k次相邻位置写的时间开销是O(log n + k - 1)，空间开销是O(log n + k - 1)
         • 书中的例子(注意这里的错误处理又用了Maybe monad)
           • binary tree
           • list
             • 文本编辑器，一个line list，可以定位到某行，删除、添加、修改当前行。如果用IP中的array+index来访问，显然，增删就没有那么高效了
           • file system tree

     15. 杂项

     • Haskell
       • SPJ的说法：在OO中，设计是画UML图；在Haskell中，设计是写类型签名
       • 在类型声明中，(->)是一个type constructor，具体来说是函数构造子，它有两个参数，实参类型+返回值类型(返回值可能是另一个函数，即另一个(->)构造子)
       • (,)、(,,)都是tuple的构造子，是函数
       • list comprehension，只不过是List monad的语法糖，等价于do notation + guard(用作filtering)
       • 记住，Monad不过是一个typeclass，monadic value的类型本质上还是Maybe/Either/List/Writer/Reader/State/RWS等
       • RWS monad
         • 显然，其中的R意义不大，而WS可以用(W,S)来替代，因此RWS可以用State monad替换。单独提供一个RWS monad可能是出于使用方便的需要
       • FP中的immutable data structure，由于总是创建新结构而不改变老结构，可以用来做版本控制
     • 注意在FP中，当输入输出都是list的时候，考虑concatMap，即list comprehension

     25. 体系结构和OS

     • CPU
       • 指令集(instruction set architecture)
         • ISA只是硬件对软件的接口，其中的寄存器并不一定存在物理上对应的电路，硬件只要保证实现抽象即可
         • 对于NaN的运算非常慢，因为它作为罕见特例，硬件不做优化; 相反，如果整数/浮点操作的是2^n，哪怕是运行时值，由于硬件优化，都比一般值运算更快
         • 指令可能被进一步翻译成功能单一的微指令(Micro instruction)，比如在x86这样的RISC
       • 流水线、超标量和乱序(Pipeline & Super scalar & Out-of-order)
         • 优化编译器输出的指令序列，在执行的时候可能进一步被硬件乱序
       • 中断(Interrupt)
         • 中断的分类
           • 异常(Fault): 如Float overflow exception、Page fault等。主动
           • 错误(Abort): 如硬件错误。主动
           • 陷阱(Trap): 如系统调用，用于进入内核态，获得高权限。主动
           • IO中断或软中断(Interrupt): 被动，抢占(preempted)，需要中断调度器介入
         • x86的中断向量表前32个元素保留，用于调试、除0等硬件异常; 高位的中断处理器可能被用于实现系统调用(Trap)，也可能被注册为IO中断处理过程
         • 中断调度器
           • 中断处理的过程中可能再次发生中断，是否要将正在处理的中断挂起，取决于两个中断的优先级；如果挂起，当前中断的状态可能会被保存到内核栈，这个过程分为硬件部分和软件部分
         • 精确中断和非精确中断
           • 在流水线/超标量机上，发生中断的时刻，有一系列的指令在同时执行，每条指令执行的阶段都不同，甚至靠后的指令更接近执行完毕，因此无法简单的备份PC、挂起线程
           • 如果硬件能够在中断时刻准确的提供PC，保证大于PC的指令都还没开始执行，而小于PC的指令都已经执行完毕，那这样的中断叫精确中断
           • 流水线和精确中断是互斥的，为了在超标量机上实现精确中断，需要很高的代价
           • 为向后兼容8086，x86通过复杂的硬件来实现精确中断，OS的中断调度可以比较简单
         • BIOS中有默认的中断处理，不过在OS加载过后会被替换
       • 分支预测(Branch prediction)
         • 流水线机中，预测失败(predict miss)开销很大，比如x86中是20个cycles
         • 一般可预测的是逻辑，可以有90+%的hit rate，而数据驱动的算法难以预测，只能有50%的hit rate
         • 静态分支预测
           • 比如，backward taken, forward not taken，能够对循环提供高于50%的命中率
         • 动态分支预测
           • 针对每个分支点，输入PC，然后根据branch history buffer，提供TRUE/FALSE的prediction，甚至直接预测目标(target)
           • BPB(Branch prediction buffer): 能够对conditional jmp提供预测
           • BTB(Branch target buffer): 除了BPB的能力外，还能预测indirect jmp/call等的目标
             • Core i7有两个BTB
       • 高速缓存(Cache)
         • 一个现代CPU典型的参数是32K L1，256K L2，8M L3; 64字节的cache line; L1、L2是每个CPU核心独占，而L3是shared; TLB大概是32项(i7是512项)
         • Memory hierarchy中不同层次的典型访问时延
           • 访问寄存器需要0.52 ns, 而访问L1也只需要15 ns
           • 访问主存需要50~100 ns
           • 访问SSD需要100us
           • 访问磁盘需要10ms
         • 类似哈佛结构(Harvard architecture)，将指令和数据分开存储，所以有i-cache和d-cache
           • 在虚拟地址翻译部分，也分为i-TLB和d-TLB
         • 和page fault不同，cache miss后的cache line调度完全硬件负责，即cache对软件透明
           • 出于该原因，能够在OS中查看page fault次数，而cache miss看不到；除非硬件提供接口给OS?
         • 常见的cache miss类型
           • cold miss: 第一次执行一组指令或者访问一组数据时
             • 所以benchmark时应该先执行一次函数来预热，warm up the cache
           • capacity miss: working set相对某级cache太大，导致每次访问都需要换出
           • conflict miss: 连续的内存访问，地址被映射到相同的cache set上，导致必须换出
             • 比如特殊size的matrix transpose
       • Unaligned memory access
         • 一般从存储器读写n个字节时(n可能是2^m)，要求地址按n对齐，否则可能报硬件错误；部分CPU能够自动修复该硬件错误，但会比aligned access更慢
         • x86会自动修复错误，部分早期的arm会直接报错
         • 小心类型不安全的代码导致的对齐错误！
       • Byte order
         • 当将多个字节的数字保存在存储器中时，需要涉及字节序，高位保存到低地址的叫little endian, 否则叫big endian
         • x86是little endian，而某些服务器处理器是big endian; 还有的CPU可以配置成低端或者高端
         • 相关场合
           • machine code中的立即数等，因为超过1字节，所以有字节序的考虑
           • 通过网络协议传递数字，如TCP协议中的端口号
           • 存档文件中的数字
         • 小心类型补全的代码导致的字节序错误！
       • 用户态线程和内核态线程
         • 一般而言，线程被叫做lightweight process
         • 用户态线程
           • 优点
             • 针对相同的CPU编写的库代码，可以在不同的OS间移植
             • 线程调度不用切换到内核态，效率高
           • 缺点
             • 阻塞系统调用不知道用户态线程的存在，因此必须以某种方式支持非阻塞调用，从而让用户态调度器能够正常工作
             • OS的调度单位是进程，不知道用户态线程的存在
         • 内核态线程
           • 优点
             • 针对相同的OS编写的线程操作码，可以在不同的CPU间移植
             • 和系统调用合作密切，阻塞、中断时调度器都能正常工作
             • OS的调度单位是线程而非进程
           • 缺点
             • 调度开销大
         • 也可以在系统中混合内核态线程和用户态线程
       • 调度分类
         • 批处理作业(Batch jobs)
           • 一般是离线作业，调度要求是：高吞吐，短周期(避免让作业饥饿)
           • 调度算法
             1. 先来先服务(first come, first served)
             2. 最短作业优先(shortest job first)
             3. 最短剩余作业优先(shortest remaining time first)，是最短作业优先的抢占式版本
         • 交互任务的调度(Interactive)
           • 应该尽快相应用户交互，调度要求是：低时延/快速响应
           • 调度算法
             1. 轮转调度(round robin)
             2. 优先级调度
             3. 多级队列
         • 实时调度
           • 有明确的截止时间限制(如医疗软件、航空软件)，调度要求是：按时完成
           • 又可以分为硬实时(hard real time)和软实时(soft real time)，前者是截止日期刚性，后者允许一定滞后，比如视频/音频解码
             • 在病人监护装置、飞机自动驾驶、自动化工厂的机器人控制案例中，正确但迟到的应答往往比没有还糟
       • 调度时机: 1. 创建进程时 2. 退出进程时 3. 阻塞IO或者等待事件时 4. 中断处理返回时
       • Linux的调度
         • 进程是资源容器；线程是轻量级进程
         • 进程对象的状态(task_struct)
           • 管理CPU
             • 调度参数，如优先级、调度惩罚/奖励、绑定的CPU id
             • CPU相关的task状态，如GPR、XMM registers、status register和PC等；另外还有PTBR(切换它的时候往往还会刷新TLB)
             • 中断向量掩码
           • 管理存储器
             • Virtual memory space的管理信息，比如以链表或者树组织的area_struct，用以规划虚拟地址空间的代码段、数据段、堆/栈段等
             • Page table
           • 管理IO
             • file descriptor table，指向进程间共享的file对象，后者由引用计数管理
           • 其他
             • clock等统计信息
             • 内核栈
         • clone方法
           • linux用它来实现进程创建(fork)和线程创建(pthread_create), 它根据输入task_struct创建一个新的task_struct，并支持细粒度的状态拷贝控制。实际能力已经超过了进程、线程创建
             • 创建进程
               • 拷贝寄存器状态、调度参数和中断向量掩码
               • 拷贝页表，并修改源task和新task的页表项状态，都改为只读，从而支持COW(写只读页失败的时候检查area_struct发现读写属性，从而分配物理页、拷贝内容、修改页表指向和属性、取消只读共享属性)
               • 拷贝area_struct相关结构，从而得到fork要求的镜像内存布局；该布局可能在随后的exec中被销毁、重组
               • 拷贝文件描述符表
               • 创建新的内核栈和统计信息
             • 创建线程
               • 创建新的寄存器状态、调度参数和中断向量掩码
               • 共享页表和area_struct信息
               • 共享文件描述符表
               • 创建新的内核栈和统计信息
         • 调度算法
           • 等待事件的进程
             • 进程自身的task_struct被链接到事件的等待队列上，不参与调度
           • 活跃进程
             • 进程的task_struct被挂在对应CPU的调度队列上，以获得更好的CPU affinity，从而有更高的L1、L2缓存命中率等
             • 有两个队列，一个是待调度队列，时间片还没用完，一个是已调度队列，本轮时间片已经用完；时间片用完后，task_struct从待调度队列移往已调度队列；待调度队列为空后，交换两个队列
             • 待调度队列是个120项的数组，表示120个优先级，每个项是一个linked list，服务于指定优先级的进程；调度算法每次取最高优先级的队列中的一项，执行并减少时间片，依次从高优先级调度往低优先级
             • 高优先级的队列每轮被分配的时间片更长
             • 等待事件成功的进程直接被挂在待调度队列上，以期立即响应，从而可能立即发起下一次的IO请求
             • 调度算法会给与不同的进程一定的优先级奖惩(+-5)，对于有终端IO请求的进程，属于交互进程，因此给与正的优先级奖励；而耗尽时间片的进程，属于计算密集进程，给与负的优先级惩罚
     • 虚拟存储器(Virtual memory)
       • 分段
         • 相比分页提供的单个虚拟地址空间，或者直接访问物理地址空间，分段提供了多个线性的地址空间
         • 优点
           • 降低管理多个可增长内存空间的程序的复杂度，如，分别为代码、堆、栈提供不同的程序段，每个段都从0开始寻址，而不必考虑重叠
           • 保护。分别为每个段提供不同的访问级别(privilege level)，从而实现权限控制。
           • 简化链接器。链接器输出的目标码中，代码、全局数据都可以从0开始寻址，而不必考虑实际的物理内存布局，极大的简化了连接器
             • 如果目标码中直接输出物理地址，那么就会遇到DLL加载中类似的问题，地址空间可能重叠，需要relocation；针对重定位问题，也有PIC方案(position independent code)
           • 简化共享。可以将不同的进程的特定段映射到相同的offset+limit，从而实现共享(如果还有后续的分页步骤，那么是进程内共享)
         • 案例
           • MULTICS: 类似两级页表，但是第0级页表索引其实是段描述符
           • x86: 段页式下(PE=1,PG=1)，先将段选择子:段偏移映射到线性的虚拟地址空间，再经过页表将虚拟地址映射到物理地址
       • 分页和MMU
         • 分页的优点
           • 保护、简化链接器、简化共享，这些优点同分段
           • 简化分配，由于连续的虚拟内存对应的物理页可能不连续，这就为物理内存载荷过大时的连续大段虚拟内存分配提供了可能
           • 允许以磁盘作为后备存储，从而达到存储空间超过物理内存限制的要求
           • (在OS中，基本上分页能够代替分段了？linux对x86分段机制的使用非常有限)
         • 页表
           • 页表负责将虚拟地址翻译成物理地址，可能会经过多级翻译，它将虚拟地址中不同的位段作为相应页表的索引进行寻址，而根页表物理地址保存在CPU的PTBR(page table base register)中
           • 在概念上，页表叫page table，其中一项叫做page table entry
             • x86中，页可以是4k或4M；在4k的情况下，一个page table可以保存1024个entry，每个entry包括物理地址的offset(20位)，另外还保存读写/执行标记、脏标记、权限标记(ring3或者ring0/ring1/ring2)等
             • x86中支持3级页表及以上，比page table高一级的页表叫做page directory
           • linux的页表常驻物理内存
         • TLB
           • TLB用于加速MMU中的地址翻译。实际流程是，以VA(virtual address)作为输入，查看TLB，如果命中，则返回PA；否则再查找page table，如果命中，则返回PA并更新TLB，否则触发page fault；page fault处理程序可能检测到illegal memory access或者发起IO请求调度磁盘上的虚拟页，在IO完成中断中重新执行指令，再次进行虚拟地址翻译
           • TLB不大，比如32个slot(i7是512个), 因为TLB的缓存单位是page，至少有4k字节，够大了
           • TLB也可能分为i-TLB和d-TLB
           • 进程的context switch中置位PTBR会造成TLB失效，而线程切换却不会
         • 缺页错误(Page fault)
           1. 检查虚地址(x86中的CR2)是否合法，如果合法，那么应该能在类似area_struct的结构中找到对应的备份存储中的数据段；如果不合法触发非法访存异常
           2. 向VFS发起IO请求，调度后备存储中的块。该块可能被VFS缓存，也可能是在普通文件中(ELF中的代码段或者通过Memory mapped file共享的文件)，也可能在paging partition或者swap file中(比如栈、堆等内存，这里可能是动态后备存储，被换出时才分配；因为使用的是raw block file，绕过了文件系统，因此更高效)；然后分配并锁住物理页(pin)，挂起该线程，IO完成后会通过中断继续执行
           3. 驱动软件响应中断，此时虚拟页已经加载到物理页，恢复page fault中断程序的执行，更新页表，退出page fault中断程序，然后重新执行访存指令，这次应该在查页表成功并更新TLB
       • Linux的虚拟地址空间管理
         • 划分为文本、数据、栈、堆等不同的area_struct，其中.text、.rodata可能直接从ELF映射
         • area少的时候，用链表管理；多余32个后，用红黑树来维护
         • area_struct包括这些字段：只读/读写等属性，增长方向(栈向下，堆向上)，是否常驻主存，后备存储器的位置
       • 后备存储
         • 静态交换区: 每个虚拟内存页总是在磁盘上有对应的块，可能在swap file中
         • 动态后备存储: 只在虚拟页被换出的时候才在磁盘中的swap file中分配块，一旦被载入物理存储器，则释放磁盘上的后备块
         • 分页分区(Paging partition)和交换文件(Swap file)
           • 分页分区用于直接访问磁盘设备，作为虚拟页的后备存储，它绕过了文件系统，从而允许任意的块大小，以及连续的块分配，避免不必要的寻道(毕竟一般文件由于需要访问inode，可能至少需要2次磁盘寻址)
           • 这里的swap file可能是raw block file，结构简单，类似分页分区
         • Linux的策略: Write back
           • sync, fsync函数
             • flush脏Virtual page到静态后备缓冲
             • flush VFS中的Block cache(缓存最近访问的块)
             • flush磁盘驱动器内部的缓冲(缓存预读的块)
           • pdflush进程
             • 每隔30秒被激活，调用sync刷新各级脏页和cache
           • kswapd，页守护进程(pid=2)
             • 每次被激活，尝试备份VP到后备存储，从而释放PP，确保分配PP的快速响应
         • Windows的策略: Write through
       • Linux的COW和fork
         • 流程
           1. fork的时候，为子进程拷贝页表，但将父子页表标记为只读，并指向同样的物理页，在物理页管理结构中注明引用次数
           2. 当写只读页触发写保护后，检查area_struct为读写，则知该页处于COW状态；如果物理页引用次数大于1，则分配新物理页并拷贝内容，更新页表指向新物理页，更新PTE的读写属性，并减少旧物理页计数；如果物理页引用次数为1，则更新页表属性为读写
         • 当为.bss段分配内存，或者通过calloc分配内存时，由于内存内容为全0，因此将PTE置为只读并且指向预分配的全0物理页，该物理页计数+1，当写该全0页的时候触发COW，从而分配新页更新页表，结束COW的只读共享
       • x86的保护模式
         • x86有3种状态，实模式(real mode, 物理寻址)、分页保护模式(PE=1)、段页保护模式(PE=1,PG=1); 其中PE/PG标志位保存在CR0中，在ring0下可以通过mov来修改
           • 注意置位PG时，当前访问存储器的虚拟页、物理页应该有一对一映射
         • 分段模式下，可以提供用户、内核内存隔离
         • 分页模式下，页表本身可以提供进程隔离、用户/内核内存隔离的保护，而PTE上的标志可以提供读、写、执行保护，以及用户/内核内存的保护
         • x86有ring0~ring3这4个级别，基本设计是，内核在ring0，系统调用在ring1，系统工具在ring2，用户程序在ring3
           • PTE中的sys标志为1时表示该内存只允许来自ring0~ring2的访问
           • ring0下提供了访问特权指令(privilege instruction)的能力: 修改控制寄存器(mov CRn)，修改特权级(通过修改EFLAG寄存器完成)，加载/保存全局段描述符表和局部表(lgdt, sgdt, lldt, sldt)，开关可屏蔽中断(cli, sti)，关机(hlt)，软中断/系统调用(int n)
           • 开机时，CPU处在ring0的实模式下，需要手工进入保护模式；返回用户态时，置为ring3，进入内核态后(比如通过call/jmp gate段描述符来实现)，置为ring0
           • linux只区分用户态和内核态，分别对应ring3和ring0/ring1/ring2；windows也类似
         • 分页覆盖了分段大部分的功能，因此OS设计中一般不太涉及分段，而x86的分段，有历史的因素：早期8086有20位物理存储器，但只有16位地址线，因此通过分段，来访问所有物理存储器，此时分段用于扩大寻址空间；但从386起，地址线已经有32位，覆盖了全部的物理存储器，所以此时分段主要提供访问控制，寻址空间基本上总是线性的平台模式(flat address space)
         • x86在段页式下的寻址过程：段选择子:段偏移 -> 虚地址 -> 物理地址
           • 段选择子:段偏移到虚拟地址的映射过程：段选择子包括3重信息，ring0~ring3的权限级+表选择子(ldt或者gdt)+表内索引，根据段选择子中的表选择子和表内索引，从ldt或者gdt中取得段描述符，后者包含了段信息如该段的虚空间offset+limit，段offset+段偏移就是虚地址
           • 汇编下可以总是用段选择子:段偏移来寻址，所谓长跳转，也就是段间跳转(跳转目标是目标段选择子+偏移)
           • 由于C语言指针是标量，因此生成的地址值只能作为段内偏移，所以段选择子隐含在特殊寄存器中，在通过jmp/call寻址代码时，总是隐含以cs寄存器作为段选择子；通过push/pop访问栈时，隐含以ss作为段选择子；其他时候的访存以ds作为段选择子
             • 因为OS一般只将x86的分段用作权限控制，因此cs/ss/ds的加载一般由内核完成；比如linux下，用户态代码的cs和ds/ss分别指向gdt的两项，它们有相同的寻址范围(0~4G)，只有访问级别不同，cs的段是只读+ring3，ds/ss是读写+ring3；而linux内核态代码也类似的使用两个段，cs使用只读的ring0段，ds/ss使用读写的ring0段
         • x86提供了任务的概念，用于帮助OS平台相关部分实现线程
           • tss段作为task segment，里面装有CPU的寄存器等，OS实现线程切换的switch_to会以目标线程的tss段选择子作为jmp目标(call和jmp的不同在于前者还会返回，因此是nested的task切换)，从而完成context switch
           • ltr指令可以将当前的tss加载进tr寄存器，方便OS访问当前线程
     • 物理存储器(Physical memory)
       • Linux物理页管理
         • 物理地址空间的管理
           • 并不是所有物理内存都能作为DMA目标的，因此linux按能力将物理存储器分为3段，从低地址到高地址依次是DMA zone、Nomral zone、High zone
           • 虚拟地址空间中，内核在高端的最后1G；而在物理地址空间中，内核在0~n的低端
           • 物理地址空间中，最低部分是内核，稍高是物理内存管理器，余下的部分是3个zone的负载部分
           • 物理内存管理器中，每个zone有一个结构，包括这些字段
             • 该zone中的空闲PP数
             • 高低水位
             • 0~n个空闲页freelist；第i个freelist中的空闲页全是2^i个页那么大，这种安排是为Buddy allocator服务
             • 使用中的PP被链接在active list或者inactive list中；每次页引用，会使得使用中的PP activity增加，于是更倾向于放进active链表中；每次页守护进程kswapd被激活后，执行PP清理，它会造成使用中的PP的activity减少，于是可能被移进inactive list中；实际的一个PP有4种状态，两个属于active，两个属于inactive，一旦进入inactive的状态3，就有可能被备份到后备存储从而释放PP
         • Buddy allocator
           • 管理的最小单位是页；这也就注定了更小粒度的物理存储器分配还需要其他分配器，比如Slab allocator
           • 分配: 针对要分配的zone，从n->0，逐个检查freelist(第i个freelist中的空闲页是2^i个page大)，如果当前i==0或者2^(i-1)小于size，则分配，从freelist头上被移除的节点被加入active list中；如果当前i>0且2^(i-1)>=size，则分裂，分裂过后以i=i-1继续执行搜索
           • 回收: 根据当前size找到对应的freelist，以地址为序插入到freelist合适的位置中，检测同size的相邻块，看是否互为buddy，如果是的话，则合并；合并后，从当前freelist移除新块，再调用free(newblock)，后者会再次尝试插入、合并的逻辑
         • Slab allocator
           • 从Buddy allocator中分配页后，提供高速的小内存块分配服务
           • 针对几种常见内核对象，提供专门的对象池(freelist，即pool allocator)
           • 针对一般的分配请求，提供分配缓冲(stack allocator?)
         • 物理页换出算法
           • 页守护进程kswapd被调度激活，或者因为物理存储器不足被显示激活；被激活后，它根据物理页释放的难度(优先级)，从容易到困难的依次尝试释放物理页
           • 物理页释放优先级
             1. 部分页常驻物理内存，不会被释放；比如内核、页表
             2. 未被引用页可以直接释放PP
             3. .text、.rodata等以ELF为后备存储，或者以其他普通命名文件为后备存储的只读页，其PP可以直接释放
             4. 进程独占的物理页，尝试释放：在swap file中分配块，写出页内容，然后更新页表(如果是静态后备存储，则判断是否为脏页，然后写出到磁盘并更新页表)
             5. 进程间共享的页，写出到后备存储，并更新所有进程的页表
           • 一般情况下，kswapd每次释放不超过32个页，以减小IO压力
           • 每个物理页有4种状态，表示active<->inactive的程度，页被引用，内核会增加active指数，而kswapd会减少active指数；PP处在偏active的状态时，会被链接在active list中，否则被链接在inactive list中；只有处在inactive的状态3时，才可能被pswapd释放
         • linux内核代码中，会将用户态指针标记为__user，这意味着读写这个指针可能引起换页；而内核指针由于常驻内存，可以高效访问
     • IO
       • 设备的组成
         • 驱动器(机械部分，可能包括电子电路)
           • 对于磁盘驱动器，内部还包括缓冲区(典型的大小是8M)，进行预读缓存等
         • 控制器(可能是主板上的芯片)
           • 包括状态寄存器、命令寄存器、控制器数据缓冲等
           • 对于磁盘控制器，还会进行数据格式的转换：它接收来自驱动的0~n的逻辑磁盘号读写请求，转换成surface+track+sector的三元组，发给驱动器；然后将驱动器返还的带校验位的位序列，填充到控制器缓冲中的数据块中
         • 驱动(软件)
           • 对特定的设备类型，隐藏具体的控制器细节(包括寄存器数目、类型，命令协议等)，向OS层提供统一的驱动接口
           • 和中断打交道，可能利用事件来提供阻塞的接口
       • 访问IO方式
         1. 以IO port的方式访问控制器命令寄存器、状态寄存器和控制器缓冲；这要求处理器提供额外的IO指令，比如x86的in port,out port
         2. 以Memory mapped IO的方式，特定范围的物理地址被映射到设备控制器缓冲，然后以访存指令(比如x86的mov)读写这块物理地址，则能在设备和物理存储器间交换数据
            • 由于地址线被同时接到了物理存储器和设备控制器，而设备的速度跟不上内存，所以，设备控制器上往往还有信号过滤器，比如PCI的地址过滤器，用来屏蔽不属于该设备的地址范围的地址信号
            • x86中，用IO port访问控制器命令寄存器和状态寄存器，用Memory mapped IO访问控制器缓冲
       • IO编程方式
         • 一般这一层由驱动负责，隐藏具体设备的寄存器、通信协议等，向OS提供设备无关的驱动接口
         • Programable IO: 向控制器命令寄存器写命令，然后循环检测状态寄存器，一旦状态置位，表示IO完成，则开始读写控制器缓冲区。只在IO速度高、数据量小的情况下可用。典型的busy waiting
         • Interrupted IO: 向控制器命令寄存器写命令，然后挂起当前线程；中断触发后，恢复线程执行，然后CPU将数据从控制器缓冲区中拷贝到物理存储器中。不用忙等待，但仍然使用CPU周期来进行设备->物理存储器间的数据转移
         • DMA IO: 向DMA控制器写命令及要操作的设备，然后挂起当前线程；DMA控制器通知设备控制器要读写的设备区域，以及目标内存区域，后者开始执行IO请求；设备控制器将数据转移到存储器中后，通知DMA控制器，后者再触发中断通知CPU。没有忙等待，没有占用CPU周期
           • 虽然DMA IO相比Interrupted IO，没有占用CPU周期，但由于CPU一般比设备控制器/DMA控制器更快，所以，Interrupted IO可能比DMA IO更快完成IO任务；如果机器中compute-bound的任务比较少，而大部分都是IO-bound，那么，直接使用CPU来进行数据转移可能更好，即这种情况下可能用Interrupted IO更好；当然，一般的计算机当中，磁盘访问这种通信量大的IO请求，还是DMA IO比较合理
           • 设备->物理存储器的数据转移，可以由设备控制器来做；但如果由DMA控制器来做的话，比如，设备控制器总是将数据传输到DMA缓冲区中，然后DMA再来将它们传输到物理存储器中，甚至其他设备缓冲区中；这种采用DMA缓冲区作为中转的方式，不但可以实现设备<->物理存储器的数据传输，还可以实现设备<->设备的传输
           • 由于DMA机制下，DMA控制器或者设备控制器会占用存储总线，因此CPU访问内存时可能达不到最大带宽，这种现象叫cycle stealing
       • 设备类型
         • 时钟
           • 可编程时钟：用于提供固定周期的clock interrupt信号，比如典型的10ms。晶体振荡器以固定频率减小某个特殊寄存器中的计数，一旦减小到0，则触发中断，并且从另一个初始计数寄存器中拷贝计数值到计数寄存器中。晶体振荡器可以有10^8hz的频率，所以为了提供100hz的时钟中断，需要将初始计数器置为10^6
             • 进程统计信息的计数器，就是由晶体振荡器的计数器中拷贝来的，这样得到的精度很高
           • 软件定时器：OS想向应用层提供定时器服务，如果直接用时钟中断的话，精度太低(由于中断处理要切换到内核态，开销大，所以时钟中断频率不可能太高)，所以采用时钟中断+软件计时的方式: 每次从内核态返回用户态前(可能因为时钟中断、IO中断、系统调用或者page fault等异常)，检测定时器队列，判断有无到时的定时器，执行回调
         • 光盘
           • 光盘通过在螺旋线上刻凹槽和凸槽来表达信息，出于抗干扰考虑，以凹凸结合处作为1，其他作为0；早期的时候母盘用激光刻录，成本很高，一度只能生成CD-ROM
           • CD-ROM: 只读的，所以它的FS可以很优化(不需要保存空闲扇区等)，而且一个FS可以分步在多张盘上面
         • 磁盘
           • 组成: 面(surface)、磁道(track)、扇区(sector)；不同surface相同位置的track构成了柱面(cylinder)
             • track的偏移: 当磁盘寻道的时候，从track1切换到tracke2，此时磁盘仍然在rotate，所以，内层track2相比track1的第1扇区会有一定弧度上的偏移
             • 交叉存储: 由于磁盘数据传输会有一定的时延，因此同一track上相邻编号的sector在分步上可能不连续，比如间隔1个扇区存储
             • 多分区: 早期的磁盘无论是内层track还是外层track，其sector密度都相同；现代磁盘，track被分成多个zone，每个zone由多个track构成，同一个zone中sector密度相同，内层zone的track的sector密度更小
             • 磁盘臂上有N(surface)那么多个磁头
             • 重叠寻道(overlapped seek)：当控制器和驱动在等待磁盘驱动器寻道的时候，可以同时启动另一个磁盘驱动器进行寻道
           • 磁盘IO时延: 一般是10ms。主要构成是寻道时间(seek time)+旋转时间(rotate latency)+传输时间(transfer time)。其中寻道时间，由磁盘臂运动速度决定；旋转时间由转速决定(典型的是7200转/分钟，大概是10ms，这制约了磁盘IO时延的下限)；传输时间由track上的sector密度以及转速决定
           • 磁盘臂调度算法: 包括FCFS(first come first served)、SSF(shortest seek first)以及elevator algorithm(电梯调度算法，总是沿着相同方向寻道，直到该方向没有IO请求才转向)；其中电梯算法有时延上界，即2*full seek time
             • 调度算法的任务还包括，合并、重排序磁盘IO请求
           • 磁盘IO的优化
             1. VFS中的块缓存，缓存最近访问过的磁盘块
             2. 磁盘驱动器的内部缓存，预读，加速顺序访问
             3. 尽量将文件的连续块保存在连续扇区中，这可能要求FS在组织空闲块的时候，会将多个连续块组织在一起(因此就不能简单使用单块的freelist)
             4. inode存储优化: 直接的ext2，是将inode池集中保存在分区起始处，因此会布局在最外层track上；而读写一个文件，至少需要访问inode和某个扇区，这就导致必须访问外层track上的inode以及内层某track上的content sector，这就要求最少两次寻道。作为一种优化，可以将inode分成多段，分步在各个track上，每个track上的文件对应的inode就保存在该track上的inode扇区中，这样访问文件时就少了一次寻道
           • 格式化
             • low level format: 将磁盘格式化成很多扇区，在扇区之间添加gap；每个扇区分为扇区头、数据以及ECC校验部分；由于磁盘是高密度设备，不可避免有瑕疵，因此需要将坏扇区隔离，不给于逻辑编号；还需要准备备用扇区，供将来使用中的扇区坏损后的补充
               • OS可用的磁盘容量比厂商宣称的小20%：1. 扇区有校验等冗余部分 2. 坏扇区 3. 备用扇区 4. 厂商采用10进制而OS采用2进制
             • 分区: 为了使用安装多操作系统，需要准备多个分区；这里将分配引导扇区，其中包括分区表，以及活动分区记录
             • high level format: 将某个分区格式化，在上面安装特定的文件系统，设置超级块信息(包括支出该分区的FS类型)，准备空闲位图/链表/inode池，准备空的根目录
           • RAID(冗余磁盘阵列，redundant array of independent disk)
             • RAID0: 将文件的多个扇区分配到多个磁盘上，提高吞吐率；但由于完全没有冗余，单个磁盘坏损会破坏整个文件；结果是：吞吐上去了，但故障率也上去了
             • RAID1: 将磁盘分为两组，文件的多个扇区分配到组0的多个磁盘上，同时也拷贝到组1的对应磁盘上；高吞吐，有冗余备份，但是冗余率太高(50%)
             • RAID2、RAID3: 保留一个磁盘作为冗余，上面存储汉明码/奇偶校验位，单个磁盘坏损的话可以修复；由于在位的基础上操作，效率较低，但有冗余保障，冗余率也低
             • RAID4: 保留一个磁盘作为冗余，该磁盘以扇区为单位提供奇偶校验。比RAID3效率稍高。缺点是，修改任何一个磁盘上的扇区内容，都需要读取所有其他扇区，计算得到校验扇区并写校验磁盘，结果就是校验磁盘压力太大，成为瓶颈
             • RAID5: 将RAID4中的奇偶校验磁盘上的校验扇区均匀的分步到其他磁盘上，这样更新不同的扇区内容，需要同步更新的校验扇区在不同的磁盘上
         • 终端
           • 将键盘+显示器称为Terminal，是历史上大型机的惯例
           • 对于键盘输入，一般的应用都不需要立即响应，而是允许用户在行上进行编辑，这叫行模式，通过在键盘驱动和VFS接口间提供额外机制实现；对vi、emacs、GUI程序这样复杂的应用而言，他们需要严格控制输入，所以他们不需要行模式
           • 输出也有加工模式，会将\n替换成\r\n等
           • 行模式下的临时输入可能也会立即回显(echo)到屏幕
           • 早期没有图形适配器(图形控制器)，没有专门的GPU，输出到屏幕仅仅是通过out指令写内存到二维数组的显存，每个像素有颜色值和其他属性
       • Linux下利用VFS访问IO设备
         • /dev下的特殊文件的主版本号和次版本号: 主版本号标志了驱动，即设备类型和驱动版本；次版本号指出设备实例，会作为参数传给驱动接口函数
         • VFS提供的特殊文件访问，其实是提供访问设备驱动程序的手段；具体到某种设备上，可能会在VFS系统调用接口与设备驱动接口间插入缓存、行模式等中间层。
           • 特殊的，就磁盘访问来说，访问普通文件，是走的VFS接口 -> 块缓存 -> FS -> 磁盘驱动器的流程；而访问磁盘块设备，是走的VFS接口 -> 块缓存 -> 磁盘驱动器的流程，绕过了FS，直接以逻辑偏移作为输入来读写设备
           • 就MMU中的虚拟页后备存储而言，ELF和Memory mapped file，其磁盘后备页是普通文件；而Paging partition/Swap file，其后备存储可能是特殊块文件(raw block file)
         • 字符设备特殊文件
           • 终端(terminal): VFS -> 行模式(optional) -> 终端设备驱动 -> 终端控制器
           • Socket: VFS -> TCP/UDP协议(optional，不提供协议的时候，即raw socket) -> 网络驱动 -> 网络适配器(网络控制器)
             • 网络适配器有额外的缓冲，因为一旦开始在链路层发包，必须是匀速；如果直接从物理存储器发包的话，由于存储总线可能会和CPU以及其他设备竞争，不保证稳定，所以可能会破坏发包，因此网络适配器需要内置缓冲
         • 块设备特殊文件
           • 磁盘: VFS -> 块缓冲(+页缓冲) -> IO调度器(调度磁盘臂) -> 磁盘驱动 -> 磁盘控制器 -> 磁盘驱动器(带8M缓冲)
         • /proc特殊设备: VFS -> OS元信息访问程序
           • /proc/pid文件可以访问进程的信息，在这些文件内容被读取的时刻，OS访问task_struct并格式化输出
           • /proc/cpuinfo等文件可以访问硬件元数据，文件被读取的时候OS查询被输出相关内容
     • 文件系统
       • 磁盘的布局
         • 计算机启动和BIOS
           • 计算机启动后，BOIS被执行，它会注册中断向量表(包括访问终端的系统调用)，然后进行开机自检(POST, Power-on self test)并输出设备状态；然后根据CMOS中的启动顺序，读取启动设备的第一个扇区的启动代码，加载分区表中的活动分区的引导块(Boot block)代码，后者会尝试从分区的FS中加载OS kernel代码
         • 引导扇区(Boot sector): 它是设备的第1个扇区，典型的是512字节，它的内容被叫做主引导记录(MBR，Master boot record)，包括Boot loader代码、分区表(Disk partition table)以及MBR结束标志
         • 分区(Partition)
           • 多分区是出于多OS的需求
           • 它包括引导块(Boot block)、超级块(Super block，包括空闲块数目、文件系统类型等字段)
             • 典型的FS如ext2，除了引导块和超级块外，还包括空闲块位图、空闲inode池，inode表(可以用inode-no来索引)，以及文件内容
       • 文件的结构
         • 方案1，一组连续的块。优点是快，只需要一次寻道；缺点是无法增加块；而删除后会在FS中留下外部碎片(External fragmentation)
         • 方案2，链表，每个节点块的第一个4字节是下一个块的索引。优点，无碎片，文件允许无限大。缺点，只能线性访问无法快速寻址，访问相邻的块需要两次IO；由于链表指针的存在，导致负载块不能对齐，读写一个块需要访问磁盘中的2个块
         • 方案3，内存中的FAT(file allocation table)。在内存中保存所有块的表，每项4字节；文件以链表的方式链接起来(目录只是特殊的文件)；空闲块也以链表的方式链接起来。优点，寻址文件只是链表访问，虽然不是O(1)，但至少不再需要额外的IO了；缺点，FAT需要的内存与磁盘块的数目成正比，比如，对于4K的块，文件分配表的大小是磁盘的千分之一，所以，1T的磁盘需要1G的FAT，而如果改为以4M为块大小的话，对于FS中占绝对多数的小文件，会有大量的内部碎片(Internal fragmentation)
         • 方案4，inode。文件的属性及所占用的磁盘块，都通过一个叫inode的结构来描述，inode一般是128或256字节
           • inode中的属性，包括设备主/次版本号，最后访问、修改时间，文件大小等
           • inode中保存了头12个块的索引，并且有3个间接索引块，分别装有剩余的块；第1个间接块，保存了另外的(1024-1)个块(以4K的块大小来说)，第2个间接块作为2级间接保存了(1024*1024-1024-1)个块，第3个作为3级间接块保存了(1024^3-1024^2-1024-1)个块
           • 利用12个直接块索引以及1~3级间接索引块，能够快速的根据输入文件offset计算出需要访问的磁盘块索引以及块内偏移
           • 小文件(1~48K)只用inode本身就可以保存所有信息；而1、2、3级块索引分别可以保存4M、4G、4T以内的文件
       • 目录的结构
         • 方案1，FAT以及CD-ROM的方案，目录项包括文件名、文件属性(隐藏、系统、文档等)、文件大小等
           • DOS中的文档属性(Archive)，由OS在文件修改后置为0，在备份程序成功备份后置位1，表示已经备份无需再操作
         • 方案2，unix的inode方案，目录项只包括文件名和inode-no，文件属性都保存在inode中
         • 有一个技巧处理类似文件名这样的变长字段的存储：文件名字段位置只保存字符串池的索引。应用这个技巧过后，每个目录项都是定长(如果还有其他变长字段，可以类似的应用该技巧)，于是增删都很方便，不会有碎片
           • ELF文件内的字符串字段也应用了该技巧
           • 字符串池具有intern的效果，避免了保存重复串
           • 其他各种变长字段也可以应用该技巧
       • 文件系统的管理和优化
         • 磁盘空间管理
           • 块大小：VFS的逻辑块大小可以和实际的磁盘扇区大小无关。块越小，寻道时间更长，块表越大；块越大，寻道时间短，但小文件的内部碎片大。一则供参考的统计信息：大部分的文件在4K左右，所以块大小取4K是合理的
             • 小文件: 块越大，磁盘利用率越小(内部碎片)，有效传输率不变
             • 块连续的大文件：块越大，磁盘利用率不变，有效传输率不变
             • 块不连续的大文件：快越大，磁盘利用率不变，有效传输率越大(块小的话，不连续的大文件要用更多次寻道)
           • 空闲块管理
             • 方案1，位图
             • 方案2，freelist，但每个node上有多个块指针，相比单个块指针的做法，在分配多个磁盘块时更高效
         • 备份
           • 优点：灾难恢复；误操作恢复
             • 以为不常见就不做备份的人，他们也同样不买保险... 计算机上最重要的就是数据安全，硬件损失倒是其次
           • 增量备份
           • 压缩备份。有一定意义，但压缩算法的容错性比较差，几个字节的损坏就可能造成文件难以解压
           • 活动文件的备份比较困难，犹如给行进中的汽车换轮胎
           • 备份方案
             • 物理转储: 逐扇区的拷贝源磁盘到备份磁盘，优点是极快(达到磁盘IO上限)，缺点是无法增量备份和恢复单个文件
             • 逻辑转储: 只备份上次备份以来变动的文件，以及变动的目录或者包含深层变动项的目录。支持增量备份和单文件恢复，但速度比较慢(各种寻道)
               • 备份算法: 1. 递归要备份的目录，标记变动文件，以及变动目录或者包含深层变动项的目录 2. 备份标记目录(目录文件被存在了备份磁盘前半段) 3. 备份标记文件
               • 恢复算法: 1. 恢复备份目录，从而建立目录层次 2. 恢复备份文件
         • 一致性检查
           • 系统崩溃时，有的文件操作可能进行到一半，如果启动后不进行一致性检查和恢复的话，FS可能已经被破坏
             • OS怎么知道有崩溃发生？比如，启动后在CMOS中置位标记，正常退出OS会清除标记；如果某次启动OS发现CMOS标记已经置位，那么上次退出为非正常退出
             • linux中负责一致性检查的进程是fsck，windows是scandisk
           • 块一致性检查/恢复算法
             • 准备两个大小等于块数的计数表，表1表示该块出现在空闲表中的次数，表2表示块出现在inode的内部块索引或者间接索引块中的次数。扫描FS的空闲块表，每次块出现就在空闲技术表中加1；扫描FS的inode表，对inode中的每次块引用，在inode引用表中加1；如果某个块在两个表中的引用次数之和不为1，那么存在一致性错误，需要尝试恢复。可能的情况如下:
               1. 空闲表=0，inode引用表=0 => 将该块放入空闲链表
               2. 空闲表=2，inode引用表=0 => 从空闲链表删除该块的所有引用，并重新加入
               3. 空闲表=0，inode引用表=2 => 分配新块并拷贝内容，让其中一个对旧块的引用指向新块；打印错误报告给用户，要求用户处理这两个冲突文件
               4. 空闲表=1，inode引用表=1 => 从空闲链表中移除
           • 文件一致性检查/恢复算法
             • 分配大小等于inode个数的表，从根目录起遍历所有目录的内容，对出现在目录中的每个项，在inode引用表中增加计数；统计完毕后，将inode中的链接数字段置为统计表内的值
               • 如果没有这个流程，可以想象
                 1. 如果inode中的链接数大于实际hard link数，那么，所以hard link都被unlink/remove后，该inode仍然不会加入空闲inode池中，从而发生inode泄露
                 2. 如果inode中的链接数小于hard link数，那么inode会过早被置入空闲池，导致多次引用，修改这样被多次引用的inode将破坏文件系统
       • 共享文件
         • Unix分为软链接和硬链接，前者是weak reference
         • hard link是在另一个目录项中保存(文件名, inode-no)，并增加inode计数，这和源链接没有任何区别
           • 优点: 快
           • 缺点: 它是强引用，可能不满足需求
         • soft link(symbolic linking)只是一个文件，里面保存了源路径
           • 优点: 弱引用，不会有泄露
           • 缺点: 空间上，它需要一个额外的块来保存源路径，浪费磁盘(4K的块)；另外，访问源文件需要先寻道一次路径块，多出一次IO。作为一种优化，FS的实现可以将源路径保存到inode中
       • Linux的虚拟文件系统(VFS)
         • 将不同的文件系统mount到一起
           • windows中无法将不同的文件系统挂接到一起，只能通过不同的盘符(A:/, F:/)来访问
         • NFS(Network filesystem)
           • VFS诞生的初衷就是为支持NFS
           • NFS可以支持无磁盘工作站
           • NFS第4版以前，没有open，只有read/write，它是无状态的
           • 由于NFS会经过网络，所以它实际传输的块较大
           • VFS会cache住NFS的块，但这会带来一致性问题。比如多个用户修改同一文件，但单个用户的block被他自己的VFS cache住了，检查不到这个变化，故，需要定时丢弃cache
         • 利用open系统调用打开文件后的内核对象
           • file descriptor: 一个整数作为文件标识符，其实是文件描述符表的索引
           • file descriptor table: 每个进程独有，fork的时候会拷贝整个表，表项为file object；open、close、dup、dup2都会修改这个表
           • file object: 进程间共享，表示打开的文件
             • ref count: 被引用的次数，每一次在file descriptor table中的出现，都会增加计数，无论是进程间共享(比如通过fork)还是进程内的多次引用(dup2)
             • IO position: 文件的读写偏移量，通过lseek修改
             • vnode: 指向vnode对象
           • vnode
             • remote file: 对于远程文件，这里保存的是远程文件token，用以发起对远程文件的IO请求
             • local file: 对于本地文件，这里保存的是inode属性的拷贝；保存在内存中避免了每次到磁盘中索引inode
             • 指向read/write/open等操作的虚函数表
               • 对remote file，这里的read/write会发起网络请求
               • 对于特殊文件，这里的read/write会经过cache等中间层后请求设备无关的驱动接口
               • 对于普通文件，这里的read/write会经过block cache后，利用磁盘驱动访问文件系统
       • CD-ROM的FS
         • 特点: 只读，所以极简单，无需准备空闲块/inode池等，目录是文件，目录项内置属性(包括扩展名等，兼容DOS)；单一FS可以跨多个CD-ROM
           • 音乐CD允许损失位，所以在校验方面的要求比计算机CD-ROM低得多
         • 目录项: 文件名+扩展名、只读/系统/隐藏/存档等属性、最后访问/修改时间等、文件offset+size、文件?/目录?的标志
         • 遍历: 第1扇区是跟目录项；定位到根目录位置，遍历每个目录项；如果是文件，则文件内容在offset+size中；如果是目录，则定位到目录offset处，读取目录内容并递归遍历
       • FAT-32
         • 利用内存中的文件分配表来管理文件块链和空闲块链
         • 有FAT-12、FAT-16、FAT-32(实际是FAT-28)之分，其中n表示size的位数，而块大小可配置，所以在FAT-32在4K块下允许最大1T的文件
         • 目录是文件，目录项的格式类似上面的CD-ROM
       • ext2
         • 磁盘上有空闲块表/位图，inode池，以及已用inode表
         • 目录是文件，目录项是文件名+inode-no
         • inode包含各种属性，以及内置的12个磁盘块号，加上1级间接、2级间接、3级间接几个块来支持大文件存储
         • 特殊字符/块设备也是文件，也有inode项，inode中保存了设备的主/次版本号
         • 有一个path->inode-no的hash表(这里的(path, inode-no)名为Dentry)，作为cache用来加速路径访问
           • 比如，访问/home/scan/Github/f1过后，cache中就会有/home->inode-d1、/home/scan->inode-d2、/home/scan/Github->inode-d3的hash表项
         • 创建新目录过后，有两个初始的目录项，(".", inode-cur-dir)、("..", inode-parent-dir)，通过他们可以支持相对路径
       • ext3
         • ext3是在ext2的基础上增加IO事件日志，从而增加文件系统的健壮性
         • VFS发起的每个IO请求，先写IO日志(可能是通过raw block file)，一旦操作成功，则销毁相应日志；如果中途OS崩溃，则启动过后，根据日志回退或者完成剩余的操作

     25. 杂项

     • 在C/C++语言中，编译器根据类型提供了方法重载、内存对齐、字节序等适配，如果尝试用union、变参函数、reinterpret_cast等来绕过类型系统，需要谨慎又谨慎！
       • 几乎所有绕过类型系统的尝试，如果reinterpret_cast、union，都会伴随一些移植性方面的type safety问题，因此，避免这么做！尽量只写强类型、类型安全的代码！
       • 如果实在无法避免类型擦除，那请检查
         • 是否有对齐问题？
           • 部分CPU上unaligned memory access会触发硬件错误，或者导致低效
         • 是否有字节序问题？
         • 是否重载错误的方法？
     • 英国数学家Charles Babbage(1792-1871)设计了第一台计算机，由于他的时代无法制造高精度的轮子、齿轮和轮牙，他始终未能让他的"分析机"正常运转。由于Babbage认识到他的分析机需要软件，所以他雇佣了著名诗人Lord byron的女儿Ada lovelace作为世界上第一个程序员；程序设计语言Ada就是以她的名字命名的。
     • 从win95开始就已经是独立的windows是了，只将底层的MS-DOS用作执行老的DOS程序；win98、winMe类似。而win2000(NT 5.0)和win xp，已经是NT了。
     • CMOS是易失性设备，但它耗电非常少，一块原装电池能用若干年，当电池开始失效时，其中保存的信息如启动顺序就会开始丢失。
     • C/C++逆向压栈的原因：为支持可变参数"..."。被调函数必须能定位fixed arguments，所以fixed部分应该后压栈
     • 微内核的设计目的是健壮性，内核只包括中断调度、进程间通信等模块，其他常见内核模块如存储器管理、设备驱动都被实现为用户态进程
     • Symmetric multiprocessing(SMP，对称多处理)
       1. 有多个处理器
       2. 他们共享存储器和IO设备，处理器之间通过总线等方式连接
       3. 所有处理器执行相同功能(所谓对称)
     • Unix设计成fork+exec两步的目的是，给与机会重定向文件
       • Windows要在CreateProcess的同时重定向文件会麻烦点
     • 计算密集型(compute-bound)和IO密集型(IO-bound)
     • unix中的remove是通过unlink实现的，它减少inode中的计数，尝试释放inode
     • 如果是寻址并传输大块数据，磁盘比主存慢4倍以上；如果是小块数据如4字节，磁盘比主存慢百万倍(7200转的转速意味着10ms级的rotate latency)
     • 字符设备和块设备的区别，前者是字符流，后者可寻址
     • 瘦客户机: 分布式终端，用户只需要显示器和键盘
       • 小型机-> PC-> 瘦客户机，历史的重演?
     • win32的CriticalSection工作在用户态，如果enter成功无需阻塞的话，不需要进入内核态(指spin lock?)
     • 公钥密码的加密、破解运算量是非对称的，这构成了公钥密码体系的基础
       • 公钥密码(非对称密码)比私钥密码(对称密码)慢了千倍。典型的如RSA和AES
       • RSA具有E(D(x))== D(E(x))的性质，所以可以用于数字签名
     • Unix历史
       • Ritchie和Thomnpson开发了直到第10版的Unix；其中第6版被Lions注释并广泛传播；第7版是第一个可移植版本，影响了整整一代学生
       • Microsoft以XENIX的名义出售版本7好几年
       • BSD(Berkeley software distribution)起始于第6版，影响很大；包括首先实现分页、文件名长于14字符、引入TCP/IP，添加vi/csh/Pascall编译器/Lisp编译器等程序
         • Mach是BSD的后代
       • 1984年AT&T被美国政府拆分后，获得设立计算机子公司的许可，于是开发了System V系统
         • Sun Solaris是System V的后代
       • 1987年发布的Minix基于微内核设计
       • 1991年的linux基于Minix设计，0.01版直接使用的Minix文件系统
     • posix支持以共享或者互斥的方式锁住一段文件内容
     • 读文件内容，对比Memory mapped file和read buffer，如果read buffer被换页，那么，后者比前者多出一块的磁盘需求，用于交换文件，当然由于有写脏页的逻辑，后者也更慢
     • linux下的几个特殊进程
       • pid=0, idle
       • pid=1, init，它等待用户登录，一旦输入用户名，则fork子进程来校验密码并exec shell
       • pid=2, 页守护进程，kswapd，用于释放物理页
     • /dev/tty表示字符特殊设备——终端
     • lseek是一个不引起寻道的文件api
     • Unix中uid=0的超级用户，不受任何权限限制
     • GCC中的regparam(n)属性(仅限于x86)，可以指明最多使用几个寄存器来传参，从而实现MSVC中的fastcall等
     • GCC的__builtin_expect，可以辅助分支预测
     • 现代主板芯片中，北桥叫做MCH(Memory control hub)，南桥叫做ICH(IO control hub)
     • C/C++中取得整数的第1个bit 1
       1. x86指令bsr
       2. MSVC中的BitScanReverse
       3. GCC中的__builtin_clz，语义是，count leading zero

     31. 计算机网络——自顶向下方法

     • 概述
       • 计算机网络的概念已经过时，终端不只是计算机，还包括各种嵌入式设备等。所有终端被称为主机(host)或者端系统(end system)
       • 端系统通过通信链路(communication link)和分组交换机(packet switch)连接在一起；其中通信链路可以是各种物理媒介，包括同轴电缆、铜线、光纤和无线电频谱；而Internet中最著名的两种分组交换机是路由器(router，网络层分组交换机)和链路层交换机(link-layer switch)
       • 端系统通过因特网提供商(ISP，Internet service provider)进入Internet
         • 比如像AOL(美国在线)那样的住宅区ISP、电话公司、公司ISP、大学ISP以及各种公共场所的无线接入ISP
         • 每个ISP是有多个分组交换机和多段通信链路组成的网络
         • 每个ISP提供不同的接入服务，如56kbps拨号调制解调器、线缆调制解调器、DSL、无线接入
         • 低层ISP通过国家的、国际的高层ISP(如AT&T)互联起来。高层ISP是通过光纤链路互相连接的告诉路由器组成
         • 每个ISP，无论低层还是高层，都是独立管理的，运行IP协议
       • TCP(Transmission control protocol)和IP(Internet protocol)是Internet中最重要的两个协议
       • 因特网标准(Internet standard)由因特网工程组(Internet engineering task force, IETF)研发，IETF的标准文档称为请求评论(Request for comment, RFC)
         • RFC定义了如TCP、IP、HTTP、SMTP等协议
       • 一个协议定义了两个或多个通信实体之间交换的报文格式和次序，以及在报文传输、接收或其他事件方面所采取的动作
       • 网络边缘(应用层和运输层)
         • 端系统
           • 网络软件是一种分布式应用程序(distributed application)，往往包括客户机程序(client program)和服务器程序(server program)；在P2P应用中，应用程序可能是对等程序，同时起着client和server的作用
         • 接入网(access network): 将端系统连接到其边缘路由器(edge router)的物理链路
           • 住宅接入(residential access)
             • 拨号调制解调器(dial-up modem): 家用调制解调器将PC的数字信号转换成模拟信号并传输，通过模拟电话线(用于打普通电话的电话线)。允许的最高速率是56kbps
             • 数字用户线(digital subscriber line, DSL): 由电话公司或独立的ISP提供，是一种新的调制解调技术，通过限制用户和ISP调制解调器间的距离，DSL能够提供高得多速率。其传输速率在两个方向上是不对称的，下载更快。欧洲
             • 混合光纤同轴电缆(hybrid fiber-coaxial cable, HFC)：需要电缆调制解调器(cable modem)，它是共享广播媒体，如果只有少数用户在线，则他们可以获得较高的速度，对比DSL是专用带宽。美国和加拿大
           • 公司接入(company access)
             • 公司和大学使用LAN接入，而以太网(Ethernet)是LAN中最流行的技术
           • 无线接入(wireless access)
             • wireless LAN: 如wifi
             • wireless WAN: 如2G、3G、4G
         • 物理媒体(physical medium)
           • 导引型媒体(guided media)：电波沿着固体媒体被导引，如双绞铜线、同轴电缆、光纤
           • 非导引型媒体(unguided media)：电波在空气或外层空间中传播，如陆地无线电信道、卫星无线电信道(同步卫星或低地球轨道卫星)
       • 网络核心(网络层)
         • 电路交换(circuit switching): 端系统间的通信路径上，为通信所提供的资源(缓存、链路传输速率)会被预留，能够确保恒定速率向接收方传输数据，应用是电话网络
           • 两台主机要通信的时候，建立端到端连接(end-to-end connection)，只能够使用链路带宽的1/n
           • 通过频分多路复用(frequency-division multiplexing, FDM)或者时分多路复用(time-division multiplexing, TDM)实现
           • 效率较低，因为存在静默期(silent peroid)，此时专用的电路空闲。比如停止讲话，此时电路不能被复用
         • 分组交换(packet switching): 端系统间的通信路径上，为通信所提供的资源不会被预留，可能导致等待(排队)，典型应用是Internet
           • 报文(message)被划分为小的分组(packet)后通过分组交换机(packet switch)传送，分组能以链路的最大速率传输
           • 分组交换机采用存储转发传输(store-and-forward transmission)，分组交换机有一个输出缓冲(output buffer，也叫output queue)，这里可能引入排队时延(queue delay)，一个新的分组还可能遇上缓冲区满的情况导致丢包(packet lost)
           • 相比电路交换中的FDM、TDM，在分组交换中，链路传输能力被逐分组的共享，这样按需共享资源被称为资源的统计多路复用(statistical multiplexing)
           • 网络层分组交换机(即路由器，router)，以输入分组的目标地址(IP地址)作为参数，查询转发表(forwarding table)，得到输出链路
         • IPS和因特网主干
           • 因特网很复杂，由几十个第1层ISP和第2层ISP，以及数以千计的低层ISP组成
           • 低层ISP：接入ISP，如住宅ISP(提供拨号或者DSL)、公司/学校ISP(使用LAN)
           • 第1层ISP，也称为因特网主干(Internet backbone)网络，包括Sprint、AT&T、NTT等
           • 第2层ISP通常有区域性或者国家性覆盖规模
       • 分组交换网中的时延
         • 节点间的时延
           • 节点处理时延(nodal processing delay): 毫秒级或更小。路由器中的校验、forwarding等
             • LAN中的处理时延可能是几个微妙，而卫星链路路由器的时延可能是几百毫秒
           • 排队时延(queuing delay): 毫秒/微妙级。在路由器输出缓冲中排队，受网络负载的影响。
             • 分组长度是L，分组达到速率是a，R是节点传输速率，则：L*a/R是流量强度(traffic intensity)。如果流量强度>1，则需要无限长的路由器缓冲，不可能；在小于1的时候，越接近1，排队越久，时延越大，甚至丢包
           • 传输时延(transmission delay): 毫秒/微妙级。由报文长度和链路传输速率决定(比如1500字节的包在10M的LAN上传输)
             • 通过拨号网络传输大的IP报文可能需要几百个毫秒，而通过10Mbps或更高速的LAN传输则时延几乎可以忽略不计
           • 传播时延(propagation delay): 毫秒级。由节点间距离和物理媒体传输速率决定(比如相距1000KM的节点通过光纤传播)
             • 对比传输时延和传播时延：想象10辆车的车队经过两个收费站，每辆车经过收费站时停车缴费的时间*10得到传输时延，而1辆车从一个收费站到达下个收费站的时间称为传播时延
             • 相隔数千米的两个路由器之间传输，和LAN内两个主机间传输，传播时延大不相同
         • 端到端的时延
           • 一个重要的概念是往返时延RTT(round-trip time)
         • 吞吐量取决于瓶颈链路(bottleneck link)的传输速率
           • 目前Internet的吞吐量限制通常是接入网络
       • 协议层次
         • 各层的所有协议被称为协议栈(protocol stack)
         • 为下层协议添加上层协议头，使得下层协议packet称为payload的这个过程叫做封装(encapsulation)
         • 五层划分
           • 应用层(application layer)：传输报文(message)，创建和部署新的协议很容易。包括HTTP、FTP、SMTP、POP3、IMAP、DNS、SSL(包装TCP)、UPnP、SSDP、DHCP、Telnet、SSH、RIP
             • DNS的工作方式：主机的DNS模块向ISP的local DNS server发送UDP的查询请求(这叫递归查询)，本地DNS服务器通过迭代查询连续访问根DNS服务器(root DNS server)、TLD服务器(top-level-domain DNS server)、权威DNS服务器(authoritative DNS server)，最终得到目标IP并缓存。中间DNS服务器的域->IP也可以缓存，这叫DNS caching
             • DHCP工作方式：(1)新主机接入子网，广播UDP包(DHCP discover)，说请求IP (2)子网内所有DNS服务器应答并提供推荐IP和续约时间 (DHCP offer) (3)主机选择一个DHCP服务器并发送请求(DHCP request) (4)被选中DHCP服务器回应请求 (DHCP ACK)
             • SSDP(Simple service discovery protocol)服务于UPnP(universal plug and play)，用于实现PC和智能设备的自动对接
             • RIP作为routing协议，选用UDP作为下层，是出于在网络链路高负载的情况下也能通信，而TCP由于拥塞控制和重传带来了不必要的开销
           • 运输层(transport layer): 传输报文段(segment)，提供进程间的逻辑连接(logic connection)，典型的通过端口来标志进程。包括TCP、UDP
           • 网络层(network layer): 传输数据报(datagram)，提供端系统间的逻辑连接，典型的通过IP地址来标志端系统。包括IP、IPv6、ICMP、ICMPv6、IPsec、BGP、ARP、RARP
             • ARP工作方式：(1)主机的ARP模块找不到IP对应的MAC，于是广播，请求子网内相应IP的主机应答 (2)相应主机发送一对一应答，源主机更新本地ARP映射表
           • 链路层(link layer): 传输帧(frame)，提供节点间的链路传输。可能经过不同的链路，如LAN、WAN、wireless LAN/WAN，这些链路间的最大传输单元(maximum transmission unit, MTU)也可能不同。包括以太网、Wifi、ATM、PPP
           • 物理层(physical layer): 传输比特。物理介质可以是双绞铜线、单模光纤等
         • OSI(开放系统互联)的七层模型
           • 该模型设计时没有考虑Internet，实践中的表示层和会话层一般由应用层的用户自己按需实现
           • 表示层(presentation layer): 提供数据压缩、加密、描述等信息
           • 会话层(session layer): 提供连接、同步等功能
         • router实现网络层物理层，link-layer switch实现链路层物理层
       • 网络攻击
         • 自我复制(self replication)的恶意软件: 病毒(virus)、蠕虫(worm)
         • 拒绝服务攻击(denial of service, DoS)
           • 攻击类型
             • 弱点攻击：发送特殊包攻击应用或OS漏洞
             • 带宽泛洪攻击(bandwidth flooding attack): 发送大量分组，导致目标主机拥塞
             • 连接泛洪攻击(如SYN Flooding attack): 通过SYN包在目标主机中创建大量半开或全开的TCP连接，耗尽目标主机资源
           • 分布式DoS(distributed DoS, DDoS): 利用僵尸网络(botnet)以DoS攻击目标主机
         • 分组嗅探器(packet sniffer): 商业机密、隐私泄露
         • IP哄骗(IP spoofing)：冒充用户
           • 对策是端点鉴别(end-point authentication)
         • 中间人攻击(man-in-middle attack)：攻击者能修改或删除报文
     • 应用层
       • 网络应用程序体系结构
         • 客户端/服务器体系结构(client-server architecture)
           • 服务器总是有一个固定的、周知的地址，称为IP地址
           • 常用主机集群(server farm)创建强大的虚拟服务器。是基础设施密集(infrastructure intensive)的，需要投入巨额费用维护server farm
         • P2P体系结构(P2P architecture)
           • 有可能是CS、P2P混合结构
           • 是自扩展(self scalability)的
       • 因特网应用对传输层的要求
         • 电子邮件、文件传输、Web：数据不允许丢失、弹性带宽、时间不敏感。TCP
         • 音频、视频、交互式游戏：数据允许丢失、实时带宽、时间敏感。UDP或TCP
       • SSL(secure socket layer): 安全TCP
         • 用户态代码实现，工作在TCP之上，提供加密、数据完整性、端点鉴别等服务。它将报文加密过后交给TCP
       • Telnet可以用于调试各种TCP上的应用层协议(wget/curl也有帮助)
       • HTTP(hyper text transfer protocol)
         • HTTP等协议有RFC文档(如HTTP的RFC2616)，而很多P2P应用都使用专有协议
         • 正是WWW的广泛使用才让Internet成为了广域网标准
         • 流行的Web浏览器包括IE、Firefox等；流行的Web服务器包括Apache、MS IIS(microsft internet information server)，他们提供URL->Web对象的寻址。
         • HTTP是一个无状态协议(stateless protocol)
         • HTTP支持持久连接(persistent connection)和非持久连接(non-persistent connection)
           • 持久连接可以连续发出请求，即流水线
           • 持久连接大大减少了TCP连接建立开销(即three-way-handshake次数减少了)，每次建立TCP连接的RTT*2的时间成本和分配TCP缓冲的空间成本都很大
         • HTTP request包括request line + header line + entity body
           • request line -> method + url + http version, 其中method包括GET、POST、HEAD(类似GET，不过不返回entity body)、PUT、DELETE等
             • 一个经典的误用例子：删除按钮采用GET，结果爬虫爬网页的时候，导致文件被删掉
           • header line: 常见Connection、User-agent、Accept-language、Cookie、If-Modified-Since
             • host字段是用于Web cache(Web proxy)，只有借助它，Web cache才能判断目标(host+url)是否已被缓存
         • HTTP response包括status line + header line + entity body
           • status line -> http version + status code + status message
             • 常见status code:
               • 200，请求成功
               • 301，对象已经永久转移
               • 400，服务器不能理解请求
               • 404，文档不在服务器上
               • 505，HTTP版本不支持
               • 304，页面没有变化(需要request中带If-Modified-Since头)
           • header line: 常见Connection、Server、Last-Modified、Content-Length、Content-Type、Set-Cookie
         • Web cookie
           • 服务器通过Set-Cookie头在浏览器的特殊Cookie文件中添加一行，(主机, Cookie值)，之后浏览器访问主机的每个请求都会带上这个Cookie值
             • 例子: (1)没有登录Amazon账号，则第一次登录的时候服务器会分配一个临时账号，将临时账号ID作为Cookie返回，之后所有的浏览、搜索，都和这个临时账号关联 (2) 一旦登录，服务器会返回要登录账号的ID作为Cookie
           • Cookie的争议在于它可能侵犯用户隐私
         • Web cache(Web proxy)
           • 一般由ISP提供
           • 作用
             • 端系统连接到Web cache比直接访问公网Web服务器更快
             • 减少ISP访问WAN的流量
               • 典型的Web cache命中率是0.2~0.7；一个例子中，没使用Web cache，由于流量强度接近1，导致queuing delay很大，访问一个页面需要几分钟；使用Web cache后，流量强度降到0.6，排队时延变成了几十毫秒
             • 多个用户匿名访问同样的URL可以被缓存，即跨用户缓存
             • 对Web服务器来说，减少了访问量
       • FTP(file transfer protocol)
         • FTP使用两个并行的连接，分别是控制连接(control connection)和数据连接(data connection)，由于使用了分离的控制连接，所以称FTP的控制信息是带外的(out-of-band)
           • 音频、视频传输的RTSP协议的控制信息也是带外的
           • HTTP的控制信息是带内的(in-band)
         • FTP的控制链接是持久连接；而数据连接是非持久连接，每个文件使用一个数据连接来传输
         • FTP的控制链接保存了状态，比如当前目录等
       • SMTP(simple mail transfer protocol)
         • 邮件协议的几个参与方，user agent、mail server、SMTP协议。
         • 用户A将邮件发送到自己的mail server A(通过SMTP或HTTP，后者针对Web邮件服务)，然后由mail server A将邮件转发到mail server B(通过SMTP)，最后user agent B从mail server B上取邮件(通过POP3/IMAP或者HTTP，后者针对Web邮件服务)
           • 采用这种方式，由自己的服务器代发邮件，那么，只要自己的邮件服务器足够稳定，保证随时在线，即使对方的服务器不稳定、或者通信不畅(比如在GFW背后)，都可以顺利发送邮件
           • mail server A上有一个message queue，它每30分钟会尝试发送A的邮件，如果几天后都没成功，则放弃并通知A
         • SMTP很老，当时没有多媒体应用，所以它采用7位的ASCII来编码报文
           • 对比HTTP，HTTP的entity body可以是任意二进制数据
         • SMTP报文的控制头：HELO、MAIL FROM、RCPT TO、DATA、QUIT
           • HELO和QUITE之间可以有多组MAIL FROM~DATA，即SMTP中，一次TCP连接可以传送多封邮件
           • DATA中是邮件正文，它可以只是纯文本，也可以像HTTP那样，包含header line和body，header可以有From、To、Subject、Content-Type和Content-Transfer-Encoding
             • 出于传输二进制附件的需要，可以通过Content-Type和Content-Transfer-Encoding来传输MIME(Multipurpose Internet Mail Exntension)数据。典型Content-Type是image/jpeg，典型的Content-Transfer-Encoding是Base64
             • SMTP利用MIME来将多媒体内容嵌入正文，而HTTP却通过多个独立的文件来传输多媒体内容
             • 每个转发邮件的SMTP服务器都会添加Received : from xxx; 时间的header line，可以利用这个了解转发路径
       • POP3(Post office protocol-version 3)
         • 支持下载并删除、下载并保留两种模式，前者(retr, dele)对多设备用户不方便
         • 流程
           1. 特许(authorization)： user, pass
           2. 事务：list retr, dele
           3. 更新：quit
       • IMAP(Inernet mail access protocol)
         • IMAP比POP3复杂很多，但提供了操作远程文件夹的可能，包括收件箱、已读、已删除以及自定义文件夹
       • 电子邮件相关的应用程序使用SMTP、POP3、IMAP等协议，而Web邮件应用使用HTTP协议
       • DNS(Domain name system)
         • 概念
           1. 分层的DNS服务器实现的分布式数据库
           2. 一个允许主机查询分布式数据库的应用层协议
         • 通常是在UDP的53端口工作
         • DNS服务器在Unix下是BIND(Berkeley internet name domain)进程
         • DNS提供的服务
           • 主机别名(host aliasing)。其中包括一个规范主机名(canonical hostname)，主机别名通常比规范主机名好记
           • 邮件服务器别名(mail server aliasing)。人们希望在使用邮件地址如[email protected]的时候，能够尽量写得简单，所以这里使用的邮件服务器别名。通过一个别名可以同时关联到两台主机，一台普通主机，一台邮件服务器主机，因此在进行DNS查询的时候，需要指定查询的主机类型，规范主机(CNAME)或者邮件服务器(MX)
           • 负载均衡(load balance或者load distribution)。一个规范主机名关联一组IP，另外，每次查询的时候，返回的IP顺序会旋转
           • 总结: (可以用nslookup验证)
             1. 没有规范主机: hostname -> ip sets
             2. 有规范主机: hostname -> canonical hostname -> ip sets
             3. 查询邮件服务器(有规范主机名): hostname -> mail server hostname -> mail server cname -> ip sets
         • 如果采用单一DNS服务器可能出现的问题
           • 单点故障(a single point of failure)
           • 通信容量(traffic volume)
           • 远距离的集中式数据库(distant centralized database): 比如将DNS服务器放在纽约，则中国的访问会有巨大的propagation delay
           • 维护(maintenance): 该数据库会很庞大，并且频繁更新
         • DNS server的层次
           1. 根DNS服务器(root DNS server): 全球13台，冗余服务器集群
           2. 顶级域DNS服务器(Top-level-domain, TLD DNS server)：如com、org、net、edu、gov等域名服务器，以及uk、fr、ca、jp、cn等国家域名服务器
           3. 权威DNS服务器(authoritative DNS server): 公司和大学自己维护自己的权威DNS服务器
           4. 本地DNS服务器(local DNS server)：本地ISP维护，离用户主机很近，可能在一个局域网内或者不超过几个路由器距离；ISP通过DHCP分配主机IP的同时，也会通知local DNS server的IP
              • 往往主机对local DNS server进行递归查询(recursive query)，而后者对从上到下的其他各级DNS服务器进行迭代查询(iterative query)
              • 递归查询是有状态的，而迭代查询是无状态的，显然后者开销更小，因此一般是本地DNS服务器支持递归，而上级DNS服务器支持迭代
              • 递归查询的结果可能不在本DNS服务器中，因此可以进行DNS caching; 这个cache不仅包括主机->IP，还可能包括com/net/edu->TLD DNS server name的域项
         • DNS记录
           • DNS服务器里存储的entry叫资源记录(Resource record, RR)，格式是(Name, Value, Type, TTL)
           • RR的解释
             1. Type=A: Name->Value是主机->IP的映射，比如abc.foo.com->111.111.111.111
             2. Type=NS: Name->Value是域->DNS服务器的映射，比如foo.com->dns.foo.com。往往作为DNS cache被保存在local DNS server中
             3. Type=CNAME: Name->Value是主机->规范主机的映射，比如abc.foo.com->canonical.foo.com
             4. Type=MX: Name->Value是主机->邮件服务器的映射，比如abc.foo.com->mail.foo.com
         • DNS报文
           • request和response报文格式相同
           • 报文中有标志
             • 报文是request还是response
             • response报文：该报文来自权威DNS server
             • request报文：希望递归查询？ response报文：支持递归查询!
           • request中的问题是：主机名+类型。类型可以是A或者MX，即要查询主机的IP，或者主机名对应的邮件服务器IP
           • response中的回答的几种可能
             1. 简单的主机->IP映射：A
             2. 主机有规范名：CNAME, A
             3. 主机有两个规范名，最终的规范名对应3个IP: CNAME, CNAME, A, A, A
             4. 邮件服务器，并且有规范名和两个IP：MX, CNAME, A, A
         • 向DNS的分布式数据库中添加记录
           • 因特网名字和地址分配机构(Internet corporation for assigned names and numbers, ICANN，负责分配域名和IP)向各种注册登录机构(registrar)授权，后者验证域名唯一性，并将域名输入DNS数据库
           • 注册流程
             1. 提交权威DNS服务器和后备权威DNS服务器的主机名和IP，比如dns1.foo.com、dns2.foo.com、111.111.111.111、112.111.111.111
             2. 对上面的每个权威DNS服务器，registrar都向TLD DNS服务器中添加两项，分别是NS和A，比如(foo.com, dns1.foo.com, NS)、(dns1.foo.com, 111.111.111.111, A)
             3. 确保Web服务器和邮件服务器的RR在注册的权威DNS服务器中，比如(www.foo.com, 113.111.111.111, A)、(mail.foo.com, 114.111.111.111, A)
           • 假如现在要查询www.foo.com，过程(不考虑DNS cache)：请求本地DNS服务器，本地DNS服务器请求根服务器，根服务器请求com的TLD服务器，后者返回dns1.foo.com的IP，再请求dns1.foo.com，返回最终结果113.111.111.111
         • 迄今为止，针对根DNS服务器的DDoS攻击不太有效，因为DNS cache的存在(本地DNS服务器中的NS记录)，实际发往根服务器的查询很少；攻击TLD服务器效果稍好，不过同样由于DNS cache的存在，后果不严重
       • P2P
         • P2P文件分发
           • 将一个文件分发给N个客户端，CS结构的时间开销是O(N)的，而P2P的开销是O(k)的
           • BitTorrent
             • 参与分发一个文件的一系列对等方构成一个Torrent，每个对等方加入Torrent的时候，向Tracker注册，并周期性的通知Tracker它还在Torrent中
             • 关于BitTorrent分发算法的两个问题
               1. 应该向邻居请求哪个块? 请求最稀有快(rarest first)，即它邻居手中被拷贝最少的块
               2. 应该向哪个邻居请求块？能够提供最快上传速率的邻居
                  • 为避免P2P中常见的搭便车(free riding)行为，只有高速向邻居传输，邻居才会也高速回馈
             • BitTorrent只是文件分发协议，以文件构成Torrent，而不提供文件搜索功能
         • P2P中的信息搜索
           • 假设这里的索引是资源->能够提供该资源的IP
           1. 集中式索引
              • 一个统一的server farm来管理索引。历史上Napster是第一家大规模部署P2P文件共享服务的商业公司
              • 缺点
                1. 单点故障、性能瓶颈以及极高的维护费用等。同一般的单点服务一样的缺陷
                2. 版权问题。服务器运营商会因为P2P资源的版权而被起诉
           2. 查询泛洪(query flooding)
              • 所有的P2P节点(主机)被相互连接，每个节点直接和有限数目的节点相连。当发起一个查询的时候，如果该节点有被索引的资源，则返回自身的IP，否则将查询传递给他的邻居。这样的节点网络叫做覆盖网络(overlay network)
              • 一般会控制查询传递深度，叫做范围受限查询泛洪(scope limited query flooding)
              • 一个节点加入overlay network的时候也需要类似的广播来得到邻居
              • 缺点: 每个查询会引发大流量
           3. 层次覆盖(hierarchical overlay design)
              • 有高速因特网连接和高可用性的对等方被指明为超级对等方；每K个普通对等方一组，直接和一个超级对等方相连，将自身资源委托给超级对等方管理；超级对等方彼此相连，构成网络(这里可能需要服务器介入负责管理超级对等方)；普通对等方将查询交给超级对等方，如果后者有资源，则返回，否则向其他超级对等方传递查询
              • 该方法通过将资源分区域集中管理，将query flooding的大部分开销放在了一个主机内，提供了性能。根据需要，超级对等方头上还可以有2级超级对等方...
           4. 分布式哈希表(distributed hash table, DHT)
              • 产生一个全局性哈希表，将所有资源映射成标识符，然后分布式的管理标志符到文件的映射
              • eMule的核心组件Overnet就应用了DHT；Skype也用DHT来管理用户名到IP的映射
     • 运输层
       • 网络层提供端系统(end system)间的逻辑通信(logic communication)，而运输层在此基础上提供进程间的逻辑通信
       • 网络层IP协议的服务模型是尽力而为的交付服务(best-effort delivery service)，它不保证segment的交付、顺序、也不保证数据完整性，所以它是不可靠服务(unreliable service)
       • 将运输层的多路套接字数据归并到网络层中，叫做多路复用(multiplexing)；将网络层数据分派到不同的运输层套接字中叫多路分解(demultiplexing)
       • TCP对比UDP
         • TCP: reliable data transfer(运用校验、应答、重发、序号、定时器等技术), flow control, congestion control
         • UDP: unreliable data transfer。只在网络层之上提供了多路复用和校验服务，使用UDP几乎就是直接在IP层上编程。可靠传输/拥塞控制等服务，需要应用层去按需实现
         • UDP套接字通过(IP, UDP端口)来标志，而TCP套接字通过(源IP, 源TCP端口，目的IP，目的TCP端口)这样的四元组来标志；所以不同源发给同样的(IP, UDP端口)，会被派发到同一个UDP套接字，而不同源发给同样的(IP，TCP端口)会被分派到不同的目的TCP套接字
       • UDP(user datagram protocol)
         • 选UDP的理由
           • 用户能更好的控制发送的数据和时间。比如网络拥塞的时候，不会有重发和拥塞控制，这对实时通信来说很有意义
           • 无需建立连接。建立连接需要RTT*2的时间，这个开销对某些应用很成问题，比如DNS
           • 无连接状态。不需要TCP的缓冲、定时器等设施，每套接字开销更少，资源受限的主机上可以启动更多UDP套接字
           • 分组头小。TCP头是20字节，UDP是8字节。(IPv4是20字节，IPv6是40字节)
         • 常见的选用UDP的应用层协议: NFS、SNMP、RIP、DNS以及音频/视频等多媒体应用
           • RIP选用UDP的理由：需要周期性的更新路由转发表，包括在网络高负载的情况下
         • 关于UDP上的流媒体的争议：它没有congestion control，所以在拥塞的情况下会导致丢包，甚至挤压TCP回话
         • reliable data transfer和congestion control可以任意组合的实现在UDP之上的应用层中
           • 相对的，选TCP的话，就意味着强制性的选择两者
         • UDP报文
           • 4个字段：源端口+目的端口+长度+校验和，每个字段2字节
           • 校验和: 报文段中所有16bit字的和，再取反码；验证的时候，计算所有16bit字的和，和校验码相加应该得-1
           • 在运输层做校验的原因
             • 某些网络层(比如IPv6)和链路层可能不做校验
             • 路由器内存可能引入比特差错
       • TCP(transmission control protocol)
         • 可靠数据传输原理(reliable data transfer protocol)
           • 手段
             • 校验: 接受方校验数据完整性
             • 应答: 当接受方校验失败的时候，发送NAK(negative acknowledgement)应答；否则发送ACK(acknowledgement)
             • 重发: 收到的ACK包校验失败、或者收到NAK包时，重发
             • 序号(sequence number): 由于重发引入了冗余包(duplicate packet)，所以需要用序号来区分重发的包和新包
               • 当接收方收到乱序的包时，可以假设存在丢包，从而通过duplicate ACK进行快速重发(fast retransmit)等
             • 定时器(timer): 为应对丢包，接收方超过一定时间没收到ACK(可能是发送包丢包，也可能是ACK丢包)，则重发
               • 通过忽略NAK和校验失败的ACK包，应答-重发流程也可以复用超时-重发流程
               • 一般使用倒计时定时器(countdown timer)
             • 流水线(pipeline)和滑动窗口(sliding window)
               • 与其采用stop-and-wait方案，等到收到ACK才发下个包，采用发送窗口并发的发送多个包，可大大的提高链路利用率。pipeline其实是提高了(N*L/P)/RTT的比值
               • 发送窗口的存在，是为了重发。
                 • 发送窗口的前半段，是已发送、待应答，当然，中间会穿插已应答的包；后半段，是可发送包，等待填充应用层数据，如果后半段为空，则应用层再次请求填充可能被阻塞或返回失败
               • 接收窗口的存在，是为了处理顺序。即每次向应用层提交连续的N个包
                 • 允许乱序收报，并在得到连续前缀后提交和发送ACK，这叫做累积确认(cumulative acknowledgement)
             • TTL(time to live)
               • 单个包可能因为网络拥塞而在网络层滞留，到达接收端的时候被误以为是序号回绕过后的新包。对策就是给每个包加上TTL(IP头中)，表示允许的路由转发次数，减少到0的话可能通过ICMP通知源
           • 流水线可靠传输协议
             • GBN(go back N)
             • SR(选择重传)
               • 为发送窗口中的每个包安装独立的定时器，单个定时器到时重发那个包；发送窗口中的前K个包都应答，则滑动窗口
               • 需要考虑序号空间和窗口大小
                 • 由于接收窗口和发送窗口可能不同步(ACK包丢失)，重发的包可能被误认为是序号回绕过后的新包，所以窗口大小应该小于1/2的序号空间
         • TCP的特点
           • 面向连接(connection oriented)，不同于电路交换中的TDM和FDM，TCP的连接只存在于端系统中，在网络层中透明
           • 通过三次握手(three-way-handshake)建立连接
             • 前两次是SYN包和SYNACK包(TCP头中的SYN标志=1)，不能有payload
           • 全双工(full duplex)
           • 点对点(point to point)
           • 每次发送一个TCP segment，大小是MSS(maximum segment size)。其中MSS往往等于MTU(maximum transmission unit)，MTU等于端到端路径上最大链路frame
             • TCP给应用层message的一个MSS大小的片段加上TCP头从而形成一个TCP segment
             • MTU常见大小是1460/536/512字节
             • 因为segment大小是协商的MSS，所以TCP头中没有报文大小字段
           • 包含发送缓冲和接收缓冲
             • TCP的RFC没有说明接收到乱序包应该丢弃还是怎样，但实践上一般是累积确认(cumulative ACK)
           • sequence number的空间大小是2^32，单位是字节
             • 初始sequence number可以随便选，通过建立连接时的SYN包协商；通常出于安全考虑由特殊算法生成，这也能减少IP层中滞留的旧连接包带来的序号冲突
         • TCP报文
           • 源端口、目的端口
           • 校验和
           • 接收窗口: 用于实时的flow control，通知接收方接收窗口大小
           • Sequence number(32位)
           • Ack number(32位): 表示发送方可以接收的下个packet字节偏移
             • 一个TCP报文中，不但有发送方向的Sequence number，还有接收方向的Ack number，这叫捎带(piggybacked)
           • flag fields
             • ACK: 表示Ack number有效
             • SYN: 三次握手中的SYN包标志
             • RST: 三次握手中的第2步，接收方发现目标TCP端口无效，则返回RST包
             • FIN: 断开连接时的四次握手中，断开己方写通道用FIN，接收ACK
           • 变长的option fields
             • 握手时协商的MSS、窗口大小
             • 时间戳
         • TCP的RTT估计
           • 过程
             1. 每隔一段时间选定一个报文统计它的RTT，得到SampleRTT
             2. 用公式EstimatedRTT = (1-a)*EstimatedRTT + a*SampleRTT得到EstimatedRTT，RFC2988建议a=0.125
             3. 用公式DevRTT = (1-b)*DevRTT + b*abs(SampleRTT-EstimatedRTT)得到偏差DevRTT，建议b=0.25
           • 定时器的超时重传间隔为TimeoutInterval=EstimatedRTT + 4*DevRTT
         • TCP的可靠数据传输
           • 发送窗口不是packet构成的窗口，而是一个基于字节的循环缓冲
           • 基本算法
             • 发送方
               • 当应用层要求发送message时，以MSS为单位，从LastByteSent位置分块发送多个TCP segment，如果LastByteSent-LastByteAcked超过send buffer size，则返回失败或阻塞应用层
                 • 发送segment时，如果当前LastByteSent==LastByteAcked，则要安装定时器
               • 超时发生时，重发LastByteAcked位置的包，并重新安装定时器
                 • 重新安装定时器时，超时时间可设置为上次的2倍，这在一定程度上有congestion control的效果
                 • 收到ACK过后，TimeoutInterval会再次由EstimatedRTT得到
                 • 超时也可能意味着丢包，会影响拥塞控制
               • 收到Ack时，如果Ack number>LastByteAcked，则更新LastByteAcked并重新安装定时器；这会推进滑动窗口，允许应用层填充更多的message
                 • 如果Ack number==LastByteAcked，则意味着这是一个duplicate ACK；接收到3个duplicate ACK，则重发LastByteAcked位置的包并重置定时器，这叫快速重传(fast retransmit)
                 • 3个duplicate ACK可能意味着丢包，会影响拥塞控制
             • 接收方
               • 接收包，如果得到一个连续前缀，则返回最高偏移的ACK，这叫累积确认(cumulative ACK)
                 • 向应用层提交连续前缀，会使得接收缓冲增大，这个变化通过TCP头反馈，是flow control的一环
               • 接收包，如果是一个乱序包，则返回待接收的第1个包的ACK；这样连续接收多个乱序包，会导致发送多个ACK(first)，这是为了实现快速重传
           • 流量控制(flow control service)
             • 如果发送方一直发送数据，而接收方应用层一直不读取数据，则接收缓冲可能溢出；流量控制的作用就是在每个ACK报文中通知发送方接收缓冲的大小，当接收缓冲太小时，发送方停止发送
             • 接收窗口：RcvWindow = RcvBuffer - (LastByteRcvd - LastByteRead)
               • 会通过每个ACK的TCP报文头反馈
             • 流量控制：LastByteSent - LastByteAcked <= RcvWindow
         • TCP连接管理
           • 建立连接(三次握手)
             • 流程
               1. 客户端：Seq=client_isn, SYN=1
               2. 服务器: Seq=server_isn, Ack=client_isn+1, SYN=1, ACK=1
               3. 客户端: Ack=server_isn+1, ACK=1 (如果有负载的话，还有 Seq=client_isn+1)
             • 这里的client_isn和server_isn是客户端和服务器用特殊算法选择出来的initial sequence number
               • 为应对SYN flooding attack，有一种方案叫SYN cookies: 在第2步的时候，服务器不创建任何连接状态，而是通过(源IP、源端口、目的IP、目的端口)来hash得到一个server_isn
             • 为何不是两次握手？
               • 如果是2次握手，意味着服务器一收到请求就建立连接，那么：(1) 这容易收到SYN flooding attack的攻击 (2) 如果网络拥塞，客户端暂时没收到ACK，又重新发起SYN，则新/老两个SYN会导致服务器建立两个连接(甚至多个连接)
           • 断开连接(四次握手)
             • 流程
               1. 主动断开方: 发出FIN包，收到ACK包
                  • 这可能发生在shutdown/close调用后，主动方底层发送掉写缓冲过后，发出FIN包
                  • 被动方发出ACK后，再调用read会返回EOF
               2. 被动断开方：发送ACK后，允许一定的操作，然后发送FIN包，收到ACK包
                  • 对被动方应用层来说，可能是read返回EOF才调用close，发送第3次握手的FIN包的
                  • 主动方回应第4次握手的ACK后，会进入30秒的TIME_WAIT状态，确保被动方能接受到ACK
           • 一个TCP连接的生命周期
             • 客户端：CLOSED -(发送SYN)-> SYN_SENT -(接受SYN&ACK，并返回ACK)-> ESTABLISHED -(发送FIN)-> FIN_WAIT_1 -(接受ACK)-> FIN_WAIT_2 -(接受FIN，返回ACK)-> TIME_WAIT -(等待30秒)-> CLOSED
             • 服务器：CLOSED -(创建listen套接字)-> LISTEN -(接受SYN，并返回SYN&ACK)-> SYN_RCVD -(收到ACK)-> ESTABLISHED -(接受FIN，发送ACK)-> CLOSE_WAIT -(发送FIN)-> LAST_ACK -(接受ACK)-> CLOSED
         • 拥塞控制(congestion control)
           • 拥塞原因
             • 流量强度(traffic intensity)接近1时，queuing delay会非常大
             • 发送方的丢包重传会加剧拥塞
             • 发送方的超时重传会加剧拥塞
             • 对于多节点路由路径，packet lost会导致上游路由器的链路带宽被浪费
           • 拥塞控制方法
             • 运输层控制: 比如TCP的做法
             • 网络层控制
               • 路由器通过特殊包直接反馈给源主机拥塞发生: 比如ICMP可以用于通告拥塞。不过由于TCP运输层拥塞控制的存在，实际ICMP拥塞通告很少用
               • 路由器在packet中添加拥塞标志: ATM就是这么做的
         • TCP拥塞控制
           • 通过拥塞窗口(congestion window)来进行拥塞控制: LastByteSent - LastByteAcked <= min(RcvWindow, CongWindow)
           • 算法: 两种状态，以及响应丢包事件
             • 拥塞避免状态(congestion avoidance): CongWin线性增大，比如，每个RTT增大1 MSS
             • 慢启动状态(slow start): CongWin初始为1，然后每个RTT后翻倍，直到某个阈值
             • 事件
               • 初始化 => SS状态，直到某阈值，然后进入CA状态
               • 快速重发(收到3个duplicate ACK) => CongWin*=1/2，保持在CA状态
               • 超时重发 => 进入SS状态，直到CongWin=OldCongWin*1/2，然后进入CA
                 • 可以看见，超时的惩罚比duplicate ACK更大，这种对快速重发(FR)惩罚较轻的做法叫快速回复(fast recovery)
           • 其他拥塞控制方法：观测SampleRTT，如果它增大，则减小CongWin
         • TCP吞吐量: 偶尔丢包的情况下，平均吞吐量大概是CongWin/RTT
     • 网络层
       • 转发和路由
         • 转发(forwarding): 分组进入路由器，根据转发表(forwarding table)，被转移到目标输出链路上
           • 查表过程：取出分组IP的子网号(利用子网掩码)，查找该子网号在转发表中的最长匹配(longest prefix matching rule)的位序列
             • 注意，只有子网号用于路由器间路由；主机号用于子网内的路由器和主机间路由，如果是LAN的话，则不经过路由
           • 对于链路层的链路交换机(link-layer switch)，查表是以链路地址(MAC)作为输入
         • 路由(routing): 分组进行端到端传输时选择路径的过程
           • routing algorithm: 如RIP、BGP，通过选路算法更新路由器的转发表，每1~5分钟更新一次；也可以人工配置路由表项
       • 网络服务模型
         • 虚电路(virtual circuit): 网络层的连接服务。如ATM
         • 数据报网络(datagram network): 网络层的无连接服务。如Internet
       • 选路算法(routing algorithm)
         • 给定一组路由器和连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的"好"路径，图论被用于形式化选路问题
           • 和主机直连的路由器称为默认路由器(default router)或第1跳路由器(first-hop router)，也可以叫做源路由器(source router)，相应的有目标路由器(destination router)
         • 分类
           1. 全局/分布式(global/decentralized)
              • 全局选路算法: 以所有节点的连通性及链路费用作为输入。也叫链路状态(link state)算法
              • 分布式选路算法: 以迭代的、分布式的方式计算最低费用路径，每个节点仅有与之相连的链路费用知识
           2. 静态/动态(static/dynamic)
              • 静态选路算法: 随着时间推移，路由变化非常缓慢，通常由人工干预调整
              • 动态选路算法: 动态算法周期性运行或者响应拓扑变化、链路费用变化
           3. 负载敏感/负载迟钝(load sensitive/load insensitive)
              • 负载敏感算法：链路费用会动态的反映出底层链路拥塞
              • 负载迟钝算法：当今所有因特网选路算法(RIP、OSPF、BGP)都是负载迟钝的
       • IPv4报文(20字节的头+变长option)
         • 源、目的IP：每个4字节
         • 校验和: 因为可能和不进行校验的链路层协议合作，所以需要校验
           • 由于TTL每经过一个路由器就会变，所以每个路由器都要校验数据完整性并重新计算校验和
         • 运输层协议：TCP/UDP等
         • TTL: 运行经过的路由器跳数，减到0的时候会通过ICMP反馈给源主机
         • IP协议版本号：IPv4或者IPv6
         • 服务类型(TOS, Type of service)：由上层来区分IP包payload的类型，比如普通数据包或者实时通信包，路由器管理员有可能区别TOS而提供不同的服务
         • 数据报长度: 首部+数据的长度。2字节，所以不超过64K，但实际上往往不超过1.5K
         • IP分片相关字段
         • 变长的选项
       • IPv4地址
         • IP地址是与接口(interface)关联的，而不是主机；主机的每个网络适配器(network adapter)都有独立的IP地址；路由器的每个链路接口也有独立的IP地址
         • a.b.c.d/k是一个IP地址，其中k表示左边的k位是子网号，即repeat(1,k)是子网掩码(subnet mask)
         • 多个主机和1个路由器可以构成子网，它们之间的路由通过IP地址中的主机号来决定(如果这里的路由器是NAT路由器的话，这个LAN由链路交换机或者集线器来进行链路寻址); 多个路由器可以构成子网，它们间的路由通过IP地址中的子网号来决定(需要将子网掩码应用到IP地址上)
         • 曾经使用过A、B、C类的子网分类法，但因为粒度过大(子网掩码长度只能是8、16、24位)，现在该为使用无类别域间路由(classless interdomain routing, CIDR)，子网号可以任意位
         • 路由聚合(route aggregation)：一个ISP可以管理多个网络地址段，如111.111.111.0/24和111.112.0.0/16，而另一个ISP却管理着111.112.111.0/24，可以发现两个ISP管理的网段并不正交，后者导致前者的111.112.0.0/16内部出现一个空洞；即使多个ISP管理的IP段不正交，出现各种空洞，转发也能正常进行，这得益于转发表的位序列最长匹配
         • 255.255.255.255是广播地址，以它为目的IP地址将导致子网内每台主机都收到packet
         • 127.0.0.0/8是本机回环地址(loopback address)，表示主机本身
           • 常用127.0.0.1
         • 10.0.0.0/8、192.168.0.0/16都是私有地址，可以用于LAN等
       • IP地址分配和DHCP(dynamic host configuration protocol)
         • ISP向ICANN申请地址块，后者负责IP地址和DNS的注册；ICANN会授权地区性因特网注册机构(如ARIN、PIPE)分配地址
         • ISP可以为主机手工配置静态IP地址，或者通过DHCP协议来自动为加入的主机分配IP地址
           • 和IP地址一起分配的还有子网掩码、默认网关(default router, 或者叫gateway)、本地DNS服务器地址
           • 手工绑定的IP地址不能被复用，所以如果要求静态IP地址的话(比如作为服务器主机)，需要支付更昂贵的费用
         • DHCP是即插即用协议(plug and play protocol, PnPP)，优点是只需要为在线主机分配IP地址，而主机离线(DHCP租约过期)后，可以复用IP地址
         • DHCP协议的流程
           1. 加入子网的主机对子网广播UDP包(通过255.255.255.255)，这个包叫DHCP discovery message
           2. 子网内的所有DHCP服务器都应答DHCP offer message
              • 该message包括推荐IP地址和IP地址租用时间(IP address least time)等信息，当然也包括子网掩码等其他DHCP协议提供的信息
           3. 主机选择一个DHCP服务器，发送DHCP request message
              • 该message会包含之间推荐的配置
           4. DHCP服务器检查request中的配置可用，然后应答DHCP ACK message
       • NAT(network address translation)
         • 由于IPv4地址空间太有限，无法为每一台PC/设备都分配一个IPv4地址，所以通过NAT技术实现一组主机共享一个IP地址，这一组主机上的应用共享了该IP的端口空间
         • 在ISP看来，接入的是一个主机还是一台NAT路由器，没有区别，ISP都会通过DHCP向它提供IP、子网掩码、本地DNS服务器等
           • 因此，可以在任意位置将一台主机替换成NAT路由器，从而接入一组新的主机
         • NAT内部维护了一个NAT转换表(NAT translation table)，它一般惰性的生成映射项私有IP，端口1->公共IP，端口2
           • 也可以手动配置静态NAT规则，这在需要运行服务器向外开放wellkown-port的时候很有用
         • NAT路由器对内提供一个私有子网，比如192.168.0.0/16，它们构成一个LAN，在这个LAN中NAT路由器的身份是集线器/链路交换器
         • NAT通过私有DHCP服务为私有子网的每一台主机分配私有IP，NAT路由器本身作为私有子网的网关(gateway，或者说default router)
         • 考虑NAT子网1的一台主机通过WAN向另一个NAT子网2的主机发送一个UDP包:
           1. 主机发segment给私有网关(NAT路由器): (源(192.168.0.2,123),目的(174.200.98.23, 80))
           2. NAT路由器做NAT translate，得到新包，并发送给ISP的路由器：(源(171.221.145.74, 100),目的(174.200.98.23, 80))
           3. 目标ISP路由器将包交给目标NAT路由器，后者进行NAT translate得到新包，并交给LAN内主机(通过ARP查询私网主机的MAC)：(源(171.221.145.74, 100),目的(192.168.0.3, 4320))
         • 如果使用一个普通路由器将家里的所有设备接入因特网，则需要向ISP续租多个IP地址，个数必须大于等于设备数，每台设备直接和ISP的DHCP服务器相连；简单的将路由器换成NAT路由器，则没有前面的麻烦，区别是带宽共享
         • 支持UPnP的NAT路由器，允许应用程序动态的绑定NAT映射
       • ICMP(Internet control message protocol)
         • ICMP常用于反馈网络层错误(主机/端口不可达，TTL过期等)，以及实现ping
         • ICMP报文：类型+编码+IP头+8字节的IP数据
           • 常见类型：
             • ping请求
             • ping应答
             • 目标不可达：根据编码值的不同，区分网络不可达、主机不可达、协议不可达、端口不可达、网络未知、主机未知
             • 拥塞控制
               • 由于一般TCP在运输层实现拥塞控制，所以ICMP的拥塞控制相对少用
             • TTL过期
         • 常见的使用ICMP的应用
           • ping: 用于探测主机
             • 一般的OS会在内部运输层实现ping服务器，所以可以用ping命令向各种主机发起请求
           • traceroute: 用于追踪目标主机的路由路径
             • 发送一系列的UDP请求，地址为(目标IP, 无效UDP端口)，TTL分别为1~n；对于第i个节点，如果是路由器，则会向源回应ICMP报文，说TTL过期；如果是目标主机，则会回应端口不可达，traceroute程序收到端口不同可达后停止发送UDP包
           • 考虑IP/port sniffer的实现
             • IP sniffer: ping命令
             • TCP port sniffer: 确保IP合法的情况下(IP sniffer)，发起TCP连接：收到RST，表示无效的port；收到SYNACK，表示合法port；无回应，可能有防火墙
             • UDP port sniffer: 确保IP合法的情况下，发送UDP包：收到ICMP报告说port不可达，则无效port；收到其他应答(比如"无效的请求")，则合法port；无回应，可能有防火墙
       • IPv6
         • 提供更大的地址空间的同时(4字节地址增大到16字节)，对IPv4做出部分改进
         • 主要变化
           • 2^(8*16)的地址空间
           • 流类型：类似IPv4中的TOS，考虑将来为实时包、付费包提供高优先级的路由服务
           • 去掉变长的option部分，定长的40字节头能够高效处理
           • 去掉校验和，数据完整性交给链路层和运输层。在网络层做校验，由于TTL的存在，每级路由器都要更新校验和，很低效
           • 去掉IP分片的功能。认为每个节点路由器都有权组装、分片IP包的话，太低效。去掉过后，路由器发现包太大，则直接通过ICMPv6通知源"分组太大"
         • 报文(IPv6头是定长的40字节)
           • 源/目的IP地址：16+16=32字节
             • 除单播、多播地址外，还提供任意地址(anycast address)，可将报文交付给一组主机中任意一个(比如路由器可能自动选择最近的一个)
           • 下一个首部: options或者运输层协议
           • TTL
           • IP版本
           • 流类型
           • 报文长度
       • IPv4向IPv6迁移
         • IPv4部署量太大，不能简单的使用早期升级协议那种、在固定时间通知所有主机更新内核的做法
         • 显然支持IPv6的节点是可以向后兼容IPv4的
         • 如果两边端系统有任何一个是IPv4，则采用IPv4，否则采用IPv6。对于IPv6路径上的IPv4路由器节点，考虑如下方案:
           1. 双栈(dual stack): IPv6节点->IPv4节点，将IPv6 datagram转换成IPv4 datagram，这将导致IPv6报文中新添加的字段丢失；IPv4节点->IPv6节点，也做包换转换，IPv6报文的新字段随意填充
              • 缺点：源IPv6报文的新字段数据丢失
           2. 隧道(tunnel): 在IPv6 datagram经过IPv4节点时，创建新的IPv4 datagram，将原来的IPv6 datagram作为IPv4报文的payload
       • 应用层的新协议部署很简单，就像给房子刷新颜色的漆，剩下的就是等邻居跟风；网络层新协议的部署很困难，它不止要求使用协议的端系统更新内核，还要求更新所有ISP路由器的协议栈，就像给房子换地基，很困难
       • IPsec提供安全的网络层IP协议，被于VPN
         • 它将运输层报文加密后传递给IP层(很像SSL将应用层message加密后传递给TCP socket的做法)
     • 链路层
       • 链路层有两种截然不同的信道
         1. 广播信道: 许多主机被连接到相同的通信信道，需要媒体访问协议来协调传输和避免碰撞
            • 如LAN、wireless LAN、卫星网、HFC
         2. 点对点信道:
            • 如路由器之间的链路、拨号调制解调器与ISP路由器间的链路
       • 网络层datagram在链路路径上传输时，经过的链路可能有不同的协议，比如PPP、LAN、WAN；他们的MTU不同，提供的服务也可能不同，比如wireless LAN提供的是可靠交付，而以太网LAN是不可靠
       • 链路层主体一般在网络适配器(network adapter)上实现，尤其是网络控制器(network controler)
         • 网络控制器一般是主板上的电路，比如LOM(LAN-on-motherboard)
       • 作为分组交换机(packet switch)，路由器在网络层，链路交换机在链路层
         • 还有更简单的链路交换机如集线器(hub)，它简单的将数据广播到接入的每个接口；交换机比集线器更高级，支持过滤、碰撞管理等
       • ARP(address resolution protocol)和RARP(reverse address resolution protocol)
         • 每个节点的ARP模块的RAM中，都有一个ARP表(ARP table, 管理IP->MAC的映射)，如果一个IP在其中找不到映射项(MAC)，该节点会向子网广播ARP请求，IP匹配的主机会发起一对一的应答，告知MAC，于是节点在ARP table中缓存该结果

     31. 杂项

     • C++模板元编程: 将模板看作编译期的函数式语言
       • 使用cons，于是模板成为编译期的类似lisp的函数式语言。其中car可以是类型，用于类型操纵；也可以是int，用于编译期计算
     • Hotmail公司的成功归结于它的先发优势(first-mover advantage)和电子邮件的病毒营销(virus marketing)属性，前者为它带来了6个月时间的领先，后者使它快速传播
       • virus marketing: 用户会自动为产品做广告。如用Hotmail发出的邮件，收件者都知道了
     • 使用WireShark抓包，可以打印从链路层到应用层协议内容
     • nslookup可以直接指定DNS服务器(root/TLD/authoritative/local)来发起查询
     • 美国东西部的光速RTT大概是30ms
     • Internet发明之初，是单一的TCP/IP协议，后来才分成两个协议。它比以太网、PC、工作站、Web等都更早。发明者在2004年得到图灵奖
     • Linux下的nmap可以用来扫描TCP/UD端口、检查系统版本等
     • CDN(content distribution network)，内容分发网络
       • 原理是，对于通过主机名来发起的网络请求，CDN修改DNS解析规则，将请求引导到距主机最近的cache服务器(比如，如果是Web请求，这里可以是Web cache)，后者直接返回cache内容或请求真正的服务器后更新cache。该方案通过减小propagation delay来减小RTT，同时还实现了load balance，内容服务器却几乎可以不改动
         • 几乎就是DNS+Web cache的特殊用法
       • 步骤:
         1. 根据主机名返回一个新的规范主机名(CNAME的RR)，该规范主机名在CDN提供商的域下。这一步可以通过修改authoritative DNS server完成
         2. 以规范主机名请求CDN提供商的DNS服务器，后者会根据客户端IP返回就近的cache服务器IP地址(DNS RR是A)
            • 显然CDN提供商的权威DNS服务器有特殊算法在后面，根据客户端IP来选择cache服务器
         3. 以cache服务器IP作为请求目标，后者会读取cache或请求真正的内容服务器