spinlock是multicore编程里面最基本的一个同步机制，关于spinlock，有以下事实

1) 为什么需要spinlock?

  spinlock需要忙等待，thread不能切换出去做其他事，这与其他一下同步机制，比如semaphore不太

一样。所以spinlock的用途和其他同步机制不同，比如从网卡收包，假设多个thread都可以从网卡收包，

并把收到的包放入一个队列，队列是用spinlock保护的，如果不忙等待，而是可以切换出去，就需要保存

当前thread的状态可以参数，也就是当前这个包需要找一个地方保存起来，然后这个thread才能切换出去

做其他事情，而新的thread调度进来之后，才能继续原来的工作（thread可以放到等待队列，然后被唤醒），

这个在realtime系统是不行的，因为packet需要被及时处理。如果处理的时间不能确定，latency就会很大，

会影响其他应用。

2) spinlock的各线程是相互竞争的，谁能获取锁是不确定的，但是机会是平等的。一个release lock，然后再

获取锁的thread，机会就比忙等待的线程小一点，因为cache flush也load instruct都需要时间。

3) 需要lock哪些东西？

使用spinlock的目的是为了在访问某个数据结构时，数据结构的状态是确定的，比如多个CPU同时执行

        a += 1

这段代码不是原子的，如果没有spinlock，每个CPU在访问a是，它的状态都不是确定的，那么，最后的结果就是

不确定的。所以需要这个动作顺序地执行。如果程序的执行不依赖于数据结构的状态，那么就不需要锁。比如在

一个数组里面查找某个数

    +--2--+--3--+-4---+-4---+

和大家share一下最近在网上收集到的资料和自己的体会，同时自己添加一个例子。

一、基础知识

1、位（bit）

来自英文bit，音译为“比特”，表示二进制位。位是计算机内部数据储存的最小单位，11010100是一个8位二进制数。一个二进制位只可以表示0和1两种状态（21）；两个二进制位可以表示00、01、10、11四种（22）状态；三位二进制数可表示八种状态（2^3）……。

2、字节（byte）(可以理解为物理单位)

字节来自英文Byte，音译为“拜特”，习惯上用大写的“B”表示。 字节是计算机中数据处理的基本单位。计算机中以字节为单位存储和解释信息，规定一个字节由八个二进制位构成，即1个字节等于8个比特（1Byte=8bit）。八位二进制数最小为00000000，最大为11111111；通常1个字节可以存入一个ASCII码，2个字节可以存放一个汉字国标码。

3、字 （可以理解为逻辑单位)

计算机进行数据处理时，一次存取、加工和传送的数据长度称为字（word）。一个字通常由一个或多个（一般是字节的整数位）字节构成。例如286微机的字由2个字节组成，它的字长为16；486微机的字由4个字节组成，它的字长为32位机。 计算机的字长决定了其CPU一次操作处理实际位数的多少，由此可见计算机的字长越大，其性能越优越。

另一种说法:

字

在计算机中，一串数码作为一个整体来处理或运算的，称为一个计算机字，简称宇。字通常分为若干个字节(每个字节一般是8位)。

Optimizing for instruction caches, part 1

Optimizing for instruction caches, part 2

Optimizing for instruction caches, part 3

ALG(application level gateway)的作用是什么？

1）connectivity，也就是允许application的traffic 通过。特别是在application使用动态端口的情况下，policy/acl一般是

无法静态配置的，所以需要ALG动态地打开协议端口，允许traffic通过。

2）NAT aware，如果application是穿过nat box，需要ALG改动payload里面的地址，并建立地址与地址直接的映射，否则

application还是无法建立连接。这里无法连通的原因是地址不匹配，而不是access control。

3) security，这里面有几个含义。一是protocol验证，对非法的协议验证；二是防止DoS攻击。网络层是不知道具体的协议

是什么，而application层知道，所以可能控制的更精细。网络层的access control/dos等等，是第一道门，在application层，

可以更精确，也更准确。让ALG做这个事是勉为其难，不过到了application level，功能都是相通的，谁做都一样。

操作系统分为preemptive(抢占式）和cooperative(协作式），这两种方式各有利弊，preemptive

的好处是系统对外部事件可以快速响应，缺点是编程复杂，因为可以抢占，所以程序里面需要保护的

数据结构就很多；cooperative实现简单，编程简单，但是对外部事件的响应比较迟钝。

在网络系统里面，cooperative用的比较多，原因就是编程比较简单。

网络系统，是一个实时系统。因为packet在queue里面，如果不能被及时处理，就会产生丢包。所以在

data plane，会有包处理线程去polling 包队列。这就会产生一个问题：如果只去poll包，那么就无法响应

其他事件，比如console输入，输出等。如果有多个CPU，可以用专门的CPU去运行control plane，专门

的CPU去运行data plane。如果只有一个CPU，就需要在control plane和data plane之间分配好CPU资源。

在任何时刻，系统应该是可管理的，否则系统就不可控。

为了保证data plane的线程不会运行超过时间限制。一般都会注册一个watchdog，定时去检查watchdog的

变量，如果这个变量没有被更新，就会将线程crash并生成coredump。这样做的目的是防治线程死锁，死循环，或者

占用CPU太长。因为系统中需要处理的事情很多，不能让一件事情占用了所有的CPU资源。如何分配CPU资源，就需要

协作。任务之间是相互影响的，我们的工作是使任务之间平衡，某一项指标高并不代表系统性能的提升，这一点很

重要。所以在线程里面手动toggle watchdog，可能会增加本线程的执行时间，但是对其他任务就会有影响。

在cooperative的系统里面，系统的平衡不是自动达到的，需要任务之间的协调，这也是需要优化的地方。

前几天同事碰到一个issue，spinlock死锁，原因是两个spinlock在定义的时候是紧挨着，也就是说，两个spinlock

在同一个cache line里面，在multicore系统里面，cacheline的更新需遵循MESI(Modified, Execlusive, Shared,

Invalid)协议。如果两个线程各得到其中一个锁而去获取另一个锁，这时就会出现死锁。

同一个Cache line的读写操作也会导致cache的颠簸，这里有一篇文章，描述了这种现象。

Cache is King -or- Things are about to get MESI

有关内存的话题，在mcore编程里面，永远都有新东西。

有没有一个工具，可以统计函数或变量引用的次数，在下面几种情况下，这个统计工具就很重要

1）inline函数统计。每个inline的调用次数，inline函数的长度等等。inline函数在编译时会被展开，这样会增加obj的大小。所以在

使用inline的时候，一定要控制inline函数的大小，10多行代码还可以接受，再多就不行了。如果inline在很多地方引用，展开之后的

规模也是很可观。obj文件增大，一个直接的后果就是增加了cache miss的机会，因为不可能把代码都load到cache里面。

2）宏的统计。最好是不要使用宏。如果一定要使用，最好不要用宏定义函数。宏的长度和引用计数也非常重要，它的影响与inline函数

类似。

3）函数的长度统计。每个函数有多少行代码。这个可能没有从obj文件里得到的代码长度有用，但是从源代码分析更方便一点，不用每次

都编译代码。

如果能从代码或者是obj文件里面发现重复的代码，这样对代码优化就很有帮助。尽量避免重复。这样对维护也有好处。

什么情况下，可以认为网络丢包了？
1：重传定时器超时，需要重传包。
2：收到重复的ACK。ACK是由packet触发的，如果后面的包收到了，而前面的包没收到，就会发重复的ACK，这种情况下，有可能中间的包丢了（也有可能是没到），所以ACK时就需要有个选择，是每个包都ACK，还是延迟ACK。

如果是重传定时器超时，就需要slow start。TCP connect刚开始发送数据的时候，也是slow start，这里面有几个参数。
1：rwnd：receiving window，就是接收方通告给发送方的window，告诉发送方本方能收多少字节。
2：cwnd: congest window, 发送方为避免引起拥塞而引入的window，控制发送方的速率。
3: ssthresh: slow start threshold size，slow start到达这个threshold后进入congest avoidance状态。
发送方的窗口取rwnd和cwnd里面的小的那个。
slow start：每个ACK都会cwnd都会加ACK的segment的大小，所以slow start增加是很快的，所以引入congest avoid，避免cwnd过快增长。

如果重传定时器超时，cwnd减到1个MSS，ssthreshold减到原来cwnd的一半，开始slow start。
如果是收到三个重复的ACK：
1：fast retransmit，快速重传，不要等重传定时器超时。
2：减小cwnd,ssthreshold，但不是进入slow start状态，而是有所保留。这应该是根据实际情况优化的，提高tcp的throughput。
3：如果重传包被ACK，则进入congest avoid状态。

在一个session based的device里面，一个high performance ager是必须的，试想一下，现在的高性能防火墙，动辄session数目都是百万级或者千万级，如果每个session同时都在有packet通过，每个packet都需要refresh session，那么在这个ager上将有多少remove/insert操作？如此巨大的工作量，对CPU，内存都是巨大的考验。如果再加上多线程环境，这个ager的设计，会影响系统性能。

www.cse.wustl.edu/~cdgill/courses/cs6874/TimingWheels.ppt

用UML的时序图分析多线程程序，个人感觉是非常实用，也很有帮助。时序图本意就是分析多个并发实体之间的消息传递，或者对象调用。对很多异步执行的消息传递，在多线程环境下，消息有哪个线程处理是不确定的。所以需要辅助工具来分析。MT环境下，最常见的问题：1，执行顺序的问题； 2，互斥。有时候从代码上去分析比较困难，画个图就简单多了。
贴一个自己画的一个草图，看看什么样子。