ARTS-WEEK3

Algorithm

Lamport面包店算法

Lamport面包店算法是由Leslie Lamport发明，为解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。

Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购：

已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。

根据签到号码的由小到大的顺序依次入店购货。

完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。

同时进入面包店采购的两个或两个以上的顾客有可能得到相同的号码。

多个顾客如果抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的。



在计算机系统中, 顾客就相当于线程，每个进程有一个唯一的标识,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，这两个线程读到的号码是完全一样的。所以，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。

//Enter, Number: array [1..N] of integer = {0};
//logic used by each thread...s
// where "(a, b) < (c, d)"
// means "(a < c) or ((a == c) and (b < d))"  --> (a < c) || ((a == c) &&(b < d))
  Thread(i) {
   while (true) {
    Enter [i] = 1;
    Number[i] = 1 + max(Number[1],...,Number[N]);
    Enter [i] = 0;
    for (j=1; j<=N; ++j) {
      while (Enter[j] != 0) {
        // wait until thread j receives its number
      }
      while ((Number[j]!=0)
         && ((Number[j],j) < (Number[i],i))) {
        // wait until threads with smaller numbers
        // or with the same number, but with higher
        // priority, finish their work
      }
    }
    // critical section...
    Number[i] = 0;
    // non-critical section...
  }
}

这个算法解决了peterson算法的局限，使得多个线程能参与互斥竞争，并且不需要基于硬件的原子(atomic)操作实现，即它可以纯软件实现。 

Review

“How Linux Containers Work” http://kyleolivo.com/dev/2016/08/15/containers-how-do-they-work/

讲述了容器的概念和LXC的组成及如何工作

Tip

VxWorks中可以通过添加spy组件和配置辅助时钟来查看任务对CPU资源使用情况，方便对任务及内核进行优化

Share

1.坚持对事实和逻辑的尊重

2.囚徒困境(Prisoner'sDilemma):证明非零和博弈中，帕累托最优和纳什均衡是相冲突的，反映了个人最佳选择并非团体最佳选择，或者说在一个群体中，个人做出理性选择却往往导致集体的非理性