Snowdream

Some notes on lock-free and wait-free algorithms

http://www.audiomulch.com/~rossb/code/lockfree/

NOBLE - a library of non-blocking synchronization protocols

http://www.cs.chalmers.se/~noble/

An optimistic approach to lock-free FIFO queues (Distributed Computing 2008)

http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

High performance dynamic lock-free hash tables and list-based sets

http://portal.acm.org/citation.cfm?id=564870.564881

Concurrent Programming Without Locks

http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

http://www.research.ibm.com/people/m/michael/podc-1996.pdf

1. On the criteria to be used in decomposing systems into modules – David Parnas
2. A Note On Distributed Computing – Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall
3. The Next 700 Programming Languages – P. J. Landin
4. Can Programming Be Liberated from the von Neumann Style? – John Backus
5. Reflections on Trusting Trust – Ken Thompson
6. Lisp: Good News, Bad News, How to Win Big – Richard Gabriel
7. An experimental evaluation of the assumption of independence in multiversion programming – John Knight and Nancy Leveson
8. Arguments and Results – James Noble
9. A Laboratory For Teaching Object-Oriented Thinking – Kent Beck, Ward Cunningham
10. Programming as an Experience: the inspiration for Self – David Ungar, Randall B. Smith

今年的ASPLOS '09上zhou yuanyuan也有一篇关于如何concurrent program中发现隐藏的atomicity violation bugs的paper，里面提到了这篇paper

2008-11-30

OSDI '08上MSR发的paper，针对并发编程中难以发现的bug问题。

paper的内容主要分两大块。

一是如何在发现bug的时候记录下线程的运行先后(thread interleaving)，途径是在线程API和用户程序多写一层wrapper functions，这里还有一些其他的问题，比如只记录下了thread interleaving的话出现data race怎么解决等。

另外一块内容是如何遍历出给定程序运行后所能产生的结果的集合，加入这个能实现的话那就能把所有隐藏的bug都找出来了。但是这个搜索空间很大，是 指数级的，的一个结论就是：给定一个程序有n个的线程，所有线程共完成k条指令，那么c次占先调度后线程的排列情况数的复杂度是的，所以在实现遍历代码的时候必须有效的降低k和c的值。

Bruce Eckel的一篇日志建议把self从方法的参数列表中移除，并把它作为一个关键字使用。
http://www.artima.com/weblogs/viewpost.jsp?thread=239003

Guido的这篇日志说明了self作为参数是必不可少的。
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html

第一个原因是保证foo.meth(arg)和C.meth(foo, arg)这两种方法调用的等价（foo是C的一个实例)，关于后者可以参见Python Reference Manual 3.4.2.3。这个原因理论上的意义比较大。

第二个原因在于通过self参数我们可以动态修改一个类的行为：

这样类C就新增了一个meth方法，并且所有C的实例都可以通过c.meth(newval)调用这个方法。

前面两个原因或许都可以通过一些workaround使得不使用self参数时实现同样的效果，但是在存在decorator的代码中Bruce的方法存在致命的缺陷。(关于decorator的介绍可以参见http://www.python.org/dev/peps/pep-0318/)

根据修饰对象，decorator分两种，类方法和静态方法。两者在语法上没有什么区别，但前者需要self参数，后者不需要。而Python在实 现上也没有对这两种方法加以区分。Bruce日志评论中有一些试图解决decorator问题的方法，但这些方法都需要修改大量底层的实现。

最后提到了另一种语法糖实现，新增一个名为classmethod的decorator，为每个方法加上一个self参数，当然这种实现也没必要把self作为关键字使用了。不过我觉得这么做还不如每次写类方法时手工加个self =_=

2008年评出了1998年最具影响力的PLDI论文，获奖论文的作者将分摊1000美元的奖金（还没一等奖学金多 -_-b）

2008 (for 1998): The Implementation of the Cilk-5 Multithreaded Language, Matteo Frigo, Charles E. Leiserson, and Keith H. Randall

Citation

“The 1998 PLDI paper “Implementation of the Cilk-5 Multithreaded Language” by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall introduced an efficient form of thread-local deques to control scheduling of multithreaded programs. This innovation not only opened the way to faster and simpler runtimes for fine-grained parallelism, but also provided a basis for simpler parallel recursive programming techniques that elegantly extend those of sequential programming. The stack-like side of a deque acts just like a standard procedure stack, while the queue side enables breadth-first work-stealing by other threads. The work-stealing techniques introduced in this paper are beginning to influence common practice, such as the Intel Threading Building Blocks project, an upcoming standardized fork-join framework for Java, and a variety of projects at Microsoft.”

另外前几年的获奖paper有：
2007 (for 1997): Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling, Glenn Ammons, Thomas Ball, and James R. Larus

2006 (for 1996): TIL: A Type-Directed Optimizing Compiler for ML, David Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert Harper, and Peter Lee

2005 (for 1995): Selective Specialization for Object-Oriented Languages, Jeffrey Dean, Craig Chambers, and David Grove

2004 (for 1994): ATOM: a system for building customized program analysis tools, Amitabh Srivastava and Alan Eustace

2003 (for 1993): Space Efficient Conservative Garbage Collection, Hans Boehm

2002 (for 1992): Lazy Code Motion, Jens Knoop, Oliver Rüthing, Bernhard Steffen.

2001 (for 1991): A data locality optimizing algorithm, Michael E. Wolf and Monica S. Lam.

2000 (for 1990): Profile guided code positioning, Karl Pettis and Robert C. Hansen.

运行a()会报UnboundLocalError: local variable ‘x’ referenced before assignment
但是运行c()会正确地显示3和4。

原因在于原因在于CPython实现closure的方式和常见的functional language不同，采用了flat closures实现。

“If a name is bound anywhere within a code block, all uses of the name within the block are treated as references to the current block.”

在第一个例子中，b函数x += 1对x进行赋值，rebind了这个对象，于是Python查找x的时候只会在local environment中搜索，于是就有了UnboundLocalError。

换句话说，如果没有修改这个值，比如b中仅仅简单的输出了x，程序是可以正常运行的，因为此时搜索的范围是nearest enclosing function region。

而d方法并没有rebind x变量，只是修改了x指向的对象的值而已。如果把赋值语句改成x = [4]，那么结果就和原来不一样了，因为此时发生了x的rebind。

所以Python中的closure可以理解为是只读的。

另外第二个例子也是这篇文章中提到的一种workaround：把要通过inner function修改的变量包装到数组里，然后在inner function中访问这个数组。

至于为什么Python中enclosed function不能修改enclosing function的binding，文中提到了主要原因还是在于Guido反对这么做。因为这样会导致本应该作为类的实例保存的对象被声明了本地变量。

参考网站：http://www.python.org/dev/peps/pep-0227/

-module(sequence1).
-export([make_sequence/0, get_next/1, reset/1]).
 
% Create a new shared counter.
make_sequence() ->
spawn(fun() -> sequence_loop(0)end).
 
sequence_loop(N) ->
receive
{From, get_next} ->
From!{self(), N},
            sequence_loop(N + 1)<SEMI>
        reset ->
sequence_loop(0)
end.
 
% Retrieve counter and increment.
get_next(Sequence) ->
Sequence!{self(), get_next},
receive
{Sequence, N} -> N
end.
 
% Re-initialize counter to zero.
reset(Sequence) ->
Sequence! reset.

初看这个程序自然是一头雾水，不过程序的函数式风格味还是很浓的。

前面提到，Erlang是基于message的，或者说message sending机制是包含在语言系统内部的，语法就是 pid ! message

接下来再来分析这个简单的程序。开头两行是模块和函数声明，略去。make_sequence开始这个进程，spawn/1内置函数创建一个新的进程，并返回pid到调用者。

初始时运行的函数是sequence_loop(0)，这个函数接收两种信息，用receive表达式声明：如果收到形式是{From, get_next}的信息，就返回当前的N并调用sequence_loop(N+1)，这样下一次收到同样的信息时就能返回N+1了；reset则等价 于Java版本中的n=0语句。

get_next/1则是发送给pid为Sequence的进程 {self(), get_next} 这样一个信息，上面解释的sequence_loop/1函数收到这个信息后会返回一个 {self(), N} 的tuple给get_next/1，收到这个信息后get_next/1就能返回N这个值了。

最后reset/1函数则是发送给Sequence一个reset信息。

这个简单的程序里能大致窥见一些Erlang的特点，尤其是它基于信息发送的本质。

依然是内网日志的汇总

1. sysenter的介绍
http://www.codeguru.com/cpp/w-p/system/devicedriverdevelopment/article.php/c8223

System Call Optimization with the SYSENTER Instruction
by John Gulbrandsen
Windows下的

2. The SLUB allocator
slab的改进版本

http://lwn.net/Articles/229984/

http://lwn.net/Articles/229096/

Christoph’s response is the SLUB allocator, a drop-in replacement for the slab code. SLUB promises better performance and scalability by dropping most of the queues and related overhead and simplifying the slab structure in general, while retaining the current slab allocator interface.

Wider use may be in the cards: the SLUB allocator is in the -mm tree now and could hit the mainline as soon as 2.6.22. The simplified code is attractive, as is the claimed 5-10% performance increase. If merged, SLUB is likely to coexist with the current slab allocator (and the SLOB allocator intended for small systems) for some time. In the longer term, the current slab code may be approaching the end of its life.

3. Compilers and More: Parallel Programming Made Easy?
http://www.hpcwire.com/features/Compilers_and_More_Parallel_Programming_Made_Easy.html

by Michael Wolfe, Compiler Engineer, The Portland Group, Inc.

4. OpenCL slides, SIGGRAPH '08
发信人: jjgod (while(!asleep()) sheep++;), 信区: CSArch
标  题: SIGGRAPH 08 上的 OpenCL slides
发信站: 水木社区 (Mon Sep 15 01:32:03 2008), 站内

※ 来源:·水木社区 newsmth.net·[FROM: 125.33.176.*]

附件: munshi-opencl.pdf (1338 KB) 链接:
http://att.newsmth.net/att.php?p.272.35430.226.pdf
全文链接：http://www.newsmth.net/bbscon.php?bid=272&id=35430

5. linux-gate.so
http://www.trilithium.com/johan/2005/08/linux-gate/
linux下使用sysenter的机制

Linux 2.4.18的linux/linkage.h文件定义了若干相关的宏

#define SYMBOL_NAME(X) X
#ifdef __STDC__
#define SYMBOL_NAME_LABEL(X) X##:
#else
#define SYMBOL_NAME_LABEL(X) X/**/:
#endif
 
#define __ALIGN .align 16,0x90
#define __ALIGN_STR ".align 16,0x90"
 
#define ALIGN __ALIGN
#define ALIGN_STR __ALIGN_STR
 
#define ENTRY(name) \
  .globl SYMBOL_NAME(name); \
  ALIGN; \
  SYMBOL_NAME_LABEL(name)

用ENTRY(name)就能定义函数了。后来发现Flux OSKit中本来就提供了类似功能的宏，定义在inc/asm.h中。
使用的时候需要再写一个c语言的wrapper function（至少2.4.18里面是这么做的）
asmlinkage void ret_from_fork(void) __asm__("ret_from_fork");

Time : 2008-08-22 15:56
OS Lab 4 debugging notes [1]
系统调用 fork()

用Simics跟踪一条条汇编分析页表映射、寄存器值还真是体力活啊。。

1. 实现Copy On Write时，如果某一个用户态页面有多个进程共享，其中一个进程修改该页面时需要创建一个新的页面。一开始偶忘了把原来页面的内容复制到新的页面了 =_= 另外由于新的页面要代替老的页面，或者说它们的物理地址不同，但虚拟地址相同，我的方法是在内核态开辟一个大小为一个页面的空间作为中转。

2. do_fork函数中，子进程复制父进程的页表的同时会把父进程页表项置为不可写，注意最后要flush tlb。因为一开始没有flush tlb，导致最后用户态fork返回以后读取的信息来自于tlb，直接改写了共享页面中fork的返回地址，导致切换到子进程时fork的返回地址丢失。这个bug让我郁闷了两三个小时。。

3. 使用两次fork时，第二次fork返回的pid会被改掉。查了下发现为用户空间分配物理页面的代码里居然在分配好以后没有把对应的struct置为已使用，结果导致第二个子进程COW创建新页面时得到了原来的父进程页面，改写了父进程页面内容。

Time : 2008-08-23 19:41
OS Lab4 debugging notes [2] 
系统调用 exec()

1. 清空页表的用户空间映射的函数一开始写得yts，bug到处都是，比如free的时候没使用指向内存块首地址的指针，记录内存地址的变量没有累加。

2. exec传递给内核态的两个参数必须先在内核态保存一个副本，否则清空用户态页表后就无法得到这两个参数信息了。

3. 分配给用户态的页面必须先清零，一方面考虑到安全性，另一方面不清零会隐藏一些潜在的bug。一开始我没有在内核执行exec的时候完整的复制所有的参数，而是直接指向了原进程的内存空间，由于清空页表后再次申请新页表时得到了原来的页面，结果正好原来那个保存参数的页面和新进程的该页面重合了 =_= 于是浪费了不少时间在这个bug上

Time : 2008-08-31 1:18
OS Lab5 debugging notes
还算顺利，不过这个lab蛮无聊的，等有空了把syscall改成类似linux的做法，单一中断号+寄存器选择syscall。

1. 最花时间的一个bug是ls返回值没有改成应用程序数，结果一开始一直以为是brk系统调用没写好，最后才发现问题出在这么小的地方。

2. brk的逻辑还不是很清楚，尽管通过了简单的测试，但是debug输出的信息显示brk增长的很快，经常是一个页一个页涨的，看来还得查下brk的具体行为。

3. 写了个比MAGIC_BREAK好用一点的宏，因为用户态的程序都是按二进制读入的，Simics无法得到函数信息（函数名、当前行数等），利用C99的宏写了个新的INFO_BREAK

#define INFO_BREAK \
    do {  \
        lprintf_kern("break in %s:%d", __FUNCTION__, __LINE__); \
        MAGIC_BREAK; \
    } while (0) \

没心思看离散，也不准备坚持看没有荷兰的欧洲杯决赛。闲着点好友的Q-Zone，原来Q-Zone首先会判断你的浏览器，如果是Firefox它会重定向到RSS阅读界面。

安然在开学后2个月写的一篇日志，“记忆里的名单”，惊喜的看到有我。也列出了一张属于我的名单。好，等待时间的遴选。

“于是想 如果有个妹妹 我要告诉她 好好放肆猖狂 做不可思议的事情 为友情和少年青涩的爱情花心思 做只是喜欢没有功利目的的事情 这么好的年华 就是用来这样浪费 和珍惜的~”

可惜我只保持了四五个月的这种疯狂，现在依然纠结于功利的选择。有时候曾想，或许那次失败更适合我，或许我终将把这么一条平淡无奇的路走到尽头。“表面强者”，或许还是很有道理的。

看到fofo的博的文字，“我要去杭州，把所有的事情抛掉，不管后果。这个地方太让人压抑，尽管有很玩得来的室友，有很好的足球队的队友，可以看很多以前爸妈不让看的喜欢的书还有过米的比赛，吃的东西也都很习惯，还是会在天气很好的星期天下午突然想起曾经在冬日的阳光照射下一家人在阳台上围着一张桌子吃饭的情景，还是会在一个人骑在去计算机协会的路上很难过地想着再也不会有那么四个或者五个人在一起吃完小炒放肆地在铺满夕阳的校园小路上勾肩搭背地行走了，还是会在一百多个人的课堂上怀念起那些艰苦却简单的日子里所有的笑声，还是会在网吧包夜的时候想起初中时捏着饭钱偷偷摸摸地去电脑房玩星际……想找找朋友们，调整一下自己的心情。”

真的找不回来了。在写这篇博文时也找不到以前写字的感觉了。

明天离散考试，某个记录或许将要因此打破。

不枉我周末练了那么多ZvP

不过总比分太惨了。。

#define sLog MaNGOS::Singleton<Log>::Instance()
#define sMaster MaNGOS::Singleton<Master>::Instance()

namespace MaNGOS
{
    template
        <
        typename T,
        class ThreadingModel = MaNGOS::SingleThreaded<T>,
        class CreatePolicy = MaNGOS::OperatorNew<T>,
        class LifeTimePolicy = MaNGOS::ObjectLifeTime<T>
        >
        class MANGOS_DLL_DECL Singleton
    {
        public:
            static T& Instance();

        protected:
            Singleton() {};

        private:

            // Prohibited actionsthis does not prevent hijacking.
            Singleton(const Singleton &);
            Singleton& operator=(const Singleton &);

            // Singleton Helpers
            static void DestroySingleton();

            // data structure
            typedef typename ThreadingModel::Lock Guard;
            static T *si_instance;
            static bool si_destroyed;
    };
}
#endif

不知道这里的注释Prohibited actions...this does not prevent hijacking.是什么意思，copy constructor和hijacking有什么关系呢？

另外注意这行typedef typename ThreadingModel::Lock Guard;，原来typedef还可以用在函数上。

Singleton的Instance方法用的是标准的double-checked lock方法，关于DCL可以参考这篇博文http://www.blogjava.net/zellux/archive/2008/04/07/191365.html

2. Explicit Constructors
game/WorkPacket.h中看到的语法，防止构造函数中参数的隐式转型
比如explicit String(int n); 用String('c')声明时就会报错

水木上有人贴了个有趣的程序

#include  < stdlib.h >
#include  < stdio.h >

void  print_forever( int  n)
{
    printf( " %d\n " , n);
    print_forever(n  +   1 );
}

int  main( int  argc,  char   * argv[])
{
    print_forever( 0 );
     return   0 ;
}

.L6:
        movl    %ebx, 4(%esp)
        addl    $1, %ebx
        movl    $.LC0, (%esp)
        call    printf
        jmp     .L6

<   -falign-loops                               [enabled]
>   -falign-jumps                               [enabled]
>   -falign-labels                              [enabled]
>   -fcaller-saves                              [enabled]
>   -fcrossjumping                              [enabled]
>   -fcse-follow-jumps                          [enabled]
>   -fdelete-null-pointer-checks                [enabled]
>   -fexpensive-optimizations                   [enabled]
>   -fforward-propagate                         [enabled]
>   -fgcse                                      [enabled]
>   -finline-small-functions                    [enabled]
>   -foptimize-register-move                    [enabled]
>   -foptimize-sibling-calls                    [enabled]
>   -fpeephole2                                 [enabled]
>   -fregmove                                   [enabled]
>   -freorder-blocks                            [enabled]
>   -freorder-functions                         [enabled]
>   -fschedule-insns2                           [enabled]
>   -fstrict-aliasing                           [enabled]
>   -fthread-jumps                              [enabled]
>   -ftree-pre                                  [enabled]
>   -ftree-store-ccp                            [enabled]
>   -ftree-vrp                                  [enabled]

Problem

Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more then P% conductors and less then Q% conductors. Your task is to determine a minimal possible number of Ekaterinburg citizens.

 1 #include <iostream>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     double dp, dq;
 9     cin >> dp >> dq;
10     int p = floor(dp * 100 + 0.5);
11     int q = floor(dq * 100 + 0.5);
12     for (int i = 1; ; i++) {
13         int a = p * i / 10000;
14         int b = q * i / 10000;
15         if ((a < b) && (q * i % 10000 > 0)) {
16             cout << i << endl;
17             return 0;
18         }
19     }
20     return 0;
21 }
22 

下午打球直到体力极限，一路淋雨跑回寝室，洗澡，感冒，低落。想回家。

有时候会想，几年后，真的就要在上海这个地方工作立足吗？

我想看一堆电影 想读一堆书 想学C# Lisp Python 想上ACM OJ网站切题 想参加一次TopCoder比赛 想学埙 想学钢琴 想睡觉 想看微经 想练英语 想看内核 想到处旅游

终会和现实冲突。于是我想退实验室。几个小时后又放弃这个决定。

终究是怕这怕那保守着缓慢前进的人。

计算机科学论坛最近举办了一个阅读样章，提交书评的活动，具体内容请见http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。

这里我想针对样章上的一个问题谈谈自己的理解。

问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中"1"的个数，要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法：

解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。

解法二，同样用到一个循环，只是里面的操作用位移操作简化了。

   1:  int Count(int v)  
   2:  {  
   3:      int num = 0;
   4:      while (v) {  
   5:          num += v & 0x01;  
   6:          v >>= 1;  
   7:      }  
   8:      return num;  
   9:  }

解法三，用到一个巧妙的与操作，v & (v -1 )每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };  
   2:     
   3:  int Count(int v) {  
   4:      return countTable[v];  
   5:  }
  
好了，这就是样章上给出的四种方案，下面谈谈我的看法。

首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。

查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。

其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。

再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。

   1:  int Count(unsigned x) {  
   2:     x = x - ((x >> 1) & 0x55555555);   
   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   
   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;   
   5:     x = x + (x >> 8);   
   6:     x = x + (x >> 16);   
   7:     return x & 0x0000003F;   
   8:  }
  
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;   
   3:     
   4:     n = (x >> 1) & 033333333333;   
   5:     x = x - n;  
   6:     n = (n >> 1) & 033333333333;  
   7:     x = x - n;   
   8:     x = (x + (x >> 3)) & 030707070707;  
   9:     x = modu(x, 63); 
   10:     return x;  
   11:  }
  
首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。

因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。

这个程序只需要十条左右指令，而且不访存，速度很快。

由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。

关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。

问题二是给定两个整数A和B，问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。

总体看来这本书还是很不错的，比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解，望大家指正 ;-)

(by ZelluX   http://www.blogjava.net/zellux)

转载请注明 作者 ZelluX    http://www.blogjava.net/zellux

看OOP教材时，提到了一个双检测锁定(Double-Checked Lock, DCL)的问题，但是书上没有多介绍，只是说这是一个和底层内存机制有关的漏洞。查阅了下相关资料，对这个问题大致有了点了解。

从头开始说吧。

在多线程的情况下Singleton模式会遇到不少问题，一个简单的例子

   1:  class Singleton {     
   2:      private static Singleton instance = null;     
   3:        
   4:      public static Singleton instance() {     
   5:          if (instance == null) {     
   6:              instance = new Singleton();     
   7:          }     
   8:          return instance;    
   9:      }    
   10:  }
  
假设这样一个场景，有两个线程调用Singleton.instance()，首先线程一判断instance是否等于null，判断完后一瞬间虚拟机把线程二调度为运行线程，线程二再次判断instance是否为null，然后创建一个Singleton实例，线程二的时间片用完后，线程一被唤醒，接下来它执行的代码依然是instance = new Singleton();
两次调用返回了不同的对象，出现问题了。

最简单的方法自然是在类被载入时就初始化这个对象：private static Singleton instance = new Singleton();

JLS(Java Language Specification)中规定了一个类只会被初始化一次，所以这样做肯定是没问题的。

但是如果要实现延迟初始化(Lazy initialization)，比如这个实例初始化时的参数要在运行期才能确定，应该怎么做呢？

依然有最简单的方法：使用synchronized关键字修饰初始化方法：

    public synchronized static Singleton instance() {       
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
   
这里有一个性能问题：多个线程同时访问这个方法时，会因为同步而导致每次只有一个线程运行，影响程序性能。而事实上初始化完毕后只需要简单的返回instance的引用就行了。

DCL是一个“看似”有效的解决方法，先把对应代码放上来吧：

    1 :   class Singleton {  
    2 :       private static Singleton instance = null ;  
    3 :     
    4 :       public static Singleton instance() {  
    5 :           if (instance == null ) {
    6 :               synchronized (this) {  
    7 :                   if (instance == null)
    8 :                      instance = new Singleton();
    9 :              }
    10 :          }
    11 :          return instance;
    12 :      }
    13 :  }

用JavaWorld上对应文章的标题来评论这种做法就是smart, but broken。来看原因：

Java编译器为了提高程序性能会进行指令调度，CPU在执行指令时同样出于性能会乱序执行（至少现在用的大多数通用处理器都是out-of-order的），另外cache的存在也会改变数据回写内存时的顺序[2]。JMM(Java Memory Model, 见[1])指出所有的这些优化都是允许的，只要运行结果和严格按顺序执行所得的结果一样即可。

Java假设每个线程都跑在自己的处理器上，享有自己的内存，和共享的主存交互。注意即使在单核上这种模型也是有意义的，考虑到cache和寄存器会保存部分临时变量。理论上每个线程修改自己的内存后，必须立即更新对应的主存内容。但是Java设计师们认为这种约束会影响程序性能，他们试着创造了一套让程序跑得更快、但又保证线程之间的交互与预期一致的内存模型。

synchronized关键字便是其中一把利器。事实上，synchronized块的实现和Linux中的信号量(semaphore)还是有区别的，前者过程中锁的获得和释放都会都会引发一次Memory Barrier来强制线程本地内存和主存之间的同步。通过这个机制，Java中的同步机制保证了synchronized块中指令的原子性(atomic)。

好了，回过头来看DCL问题。看起来访问一个未同步的instance字段不会产生什么问题，我们再次来假设一个场景：

线程一进入同步块，执行instance = new Singleton(); 线程二刚开始执行getResource();

按照顺序的话，接下来应该执行的步骤是 1) 分配新的Singleton对象的内存 2) 调用Singleton的构造器，初始化成员字段 3) instance被赋为指向新的对象的引用。

前面说过，编译器或处理器都为了提高性能都有可能进行指令的乱序执行，线程一的真正执行步骤可能是1) 分配内存 2) instance指向新对象 3) 初始化新实例。如果线程二在2完成后3执行前被唤醒，它看到了一个不为null的instance，跳出方法体走了，带着一个还没初始化的Singleton对象。

错误发生的一种情形就是这样，关于更详细的编译器指令调度导致的问题，可以参看这个网页 [4]。

[3] 中提供了一个编译器指令调度的证据

instance = new Singleton(); 这条命令在Symantec JIT中被编译成

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; 分配空间
02061074   mov         dword ptr [ebp],eax       ; EBP中保存了instance的地址

02061077   mov         ecx,dword ptr [eax]       ; 解引用，获得新的指针地址

02061079   mov         dword ptr [ecx],100h      ; 接下来四行是inline后的构造器
0206107F   mov         dword ptr [ecx+4],200h   
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

可以看到，赋值完成在初始化之前，而这是JLS允许的。
 
另一种情形是，假设线程一安稳地完成Singleton对象的初始化，退出了同步块，并同步了和本地内存和主存。线程二来了，看到一个非空的引用，拿走。注意线程二没有执行一个Read Barrier，因为它根本就没进后面的同步块。所以很有可能此时它看到的数据是陈旧的。

还有很多人根据已知的几种提出了一个又一个fix的方法，但最终还是出现了更多的问题。可以参阅[3]中的介绍。

[5]中还说明了即使把instance字段声明为volatile还是无法避免错误的原因。

由此可见，安全的Singleton的构造一般只有两种方法，一是在类载入时就创建该实例，二是使用性能较差的synchronized方法。

(by ZelluX  http://www.blogjava.net/zellux )

参考资料：

[1] Java Language Specification, Second Edition, 第17章介绍了Java中线程和内存交互关系的具体细节。
[2] out-of-order与cache的介绍可以参阅Computer System, A Programmer's Perspective的第四、五章。
[3] The "Double-Checked Locking is Broken" Declaration, http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[4] Synchronization and the Java Memory Model, http://gee.cs.oswego.edu/dl/cpj/jmm.html
[5] Double-checked locking: Clever, but broken, http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html?page=1
[6] Holub on Patterns, Learning Design Patterns by Looking at Code

翘课大半，作业一半不交一半抄，总之太不像学生了。
搞得现在Super Scalar都只知道个大概，tableaux也知其然而不知所以然。
下星期好好参与一次，上课、作业一个都不能少，恩。
至于之后么，再说咯。

(define (reverse items)
  (define (reverse-iter i k)
    (if (null? i)
        k
        (reverse-iter (cdr i)
                      (cons (car i) k))))
 
  (reverse-iter items ()))

(define (filter predicate sequence)
  (cond ((null? sequence) null)
        ((predicate (car sequence))
         (cons (car sequence) 
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (enumerate-interval low high)
  (if (> low high)
      null
      (cons low (enumerate-interval (+ low 1) high))))

(define (enumerate-tree tree)
  (cond ((null? tree) null)
        ((pair? tree)
         (append (enumerate-tree (car tree))
                 (enumerate-tree (cdr tree))))
        (else (list tree))))

(define (hornel-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

Ex 2.35
数出一棵树中的叶子数。这题我的做法比较土，没想到map-reduce操作上的递归，而是把叶子节点的值都改成1然后一个累加。

(define (count-leave tree)
  (accumulate +
              0
              (map (lambda (x) 1)
                   (enumerate-tree tree))))

其实只要递归调用主函数就行了

(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))

Ex 2.36
可以理解为计算矩阵各列之和吧

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      null
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

    火车缓缓地开着，混杂的人群。此时的我不属于两边世界中的任何一个，孤立于这种空间和从属感的交界处。理下思路，趁着记忆的新鲜，在手机上敲下这四天的感受，以弥补将来的某天可能发生的对这次旅行的淡忘。

Zijingang Campus: A Fudaner's Perspective

1. Abstract
一次课堂电影(话剧《暗恋桃花源》[5])
旁听两节课，图形学和线性代数。图形学课上回答一次问题 =_=
一场越剧，小百花越剧团的《春琴传》
一场话剧，黑白剧社[1]的《我在天堂等你》[2]
半天图书馆自修，读了半章SICP[4]和一篇paper
半天机房灌水，水木C版版主上任后的第一个操作居然是在浙大完成的
半天在“风雨操场”打球
一晚上在浙大战网打了十盘星际，九胜一负

2. Introduction
    K900到车管所，一站的路程后到达正门。紫金港的正门没有试图制造一种空间隔离感，宽敞的道路上横躺着一块刻有“浙江大学”的石块，构成了形式上的正门。步行百余部后，回头才意识到原来百余步前的所处位置竟是一个入口。
    这个入口给人一种宽广、松驰的感觉，与复旦的正门放置伟人像不同，紫金港的封面很平坦。除了草坪就无其他，可以望到天际。整个紫金港都给我这样的感觉：草坪、树、湖的世界中，点缀着几幢风格各异的建筑。

3. Details
3.1 上课
    其实到浙大吃完饭后做的第一件事就是旁听了一节数媒专业的图形学，上的是三维空间的坐标变换。老师上课进度偏慢，绝大部分学生上课都很认真。感到那么一点点的压力 >,<

3.2 图书馆
    一直觉得图书馆是大学的灵魂组成部分之一。甚至大一的时候觉得有个好的图书馆和一套优秀的借阅制度就足以成为一个好的大学了。也因此新到一个大学后总是特别关注那里的图书馆。
    紫金港图书馆依傍在高耸的行政楼旁，可以把它比成计算中心，行政楼对应于光华主楼，较之后者它们靠得更紧密些。浙大同学说外校同学来看图书馆时，第一反应总是误把行政楼当图书馆。喜欢图书馆的这种低调。
    图书馆的书架分类很笼统，所有的理工类书橱都被贴上了“自然科学”的标签，恐怕找书的时候要很依赖电脑。抽样调查了计算机类书籍，书目较小，重复率较大，甚至会有十几册同本书罢占一层书架的情况。阅读环境很不错，落地窗，明亮。窗外便是那片湖，一如图书馆般地平静。若是把座椅换成摇椅，再加上一杯咖啡，最愉悦的享受莫过于此。
    离开图书馆时还让同学代借了本SICP[4]，本想带回上海以此要胁该同学五一来复旦，到时候再还的。无奈多带本书太麻烦，回来之前还是还掉了。

3.3 付费
    住宿楼旁有几家小吃店，其中不少店都是设置了一个单独的付费窗，而这个付费机制里没有任何凭证，或者说点了吃的却不付钱是很容易做到。别的不多说，这样一种店与客之间的信任给人一种亲切感。当然这也和紫金港地理位置较偏远，外人较少有关。

3.4 话剧
    看了黑白剧社[1]的《我在天堂等你》[2]。话剧在一个可容纳百人左右的小书屋里进行。由于一个月前刚看过人艺的《榆树下的欲望》[3]，相比之下学生的功底自然略逊一筹，尤其是对老年人的刻划上。不过总体还是很不错的。
    记忆最深的是社员的那份激情，话剧结束后，演员和工作人员挨个自我介绍完毕，然后跑出书屋，站在门口等待出来的观众，齐喊“再见”“谢谢”。下楼走出百余米后，听到后面三声击掌，接着是社员们高喊“谢谢你们”，如此重复几遍，一阵高过一阵。被这种热情所震撼。

3.5 肆
    一位同学的寝室门口贴着一张记录着这个班级同学的奋斗目标之类的墙纸，中间是一个硕大的草体“肆”。奋斗目标都很直接，譬如要被Stanford商学院录取，要进入某某大公司云云。不怎么喜欢这种过于外露的上进心，更欣赏复旦略带散漫的风格。

3.6 还是课
    浙大课比较多。上下午各5节，每节45分钟，中间休息5/15分。同时周末有课也是很常见的现象，为了提高绩点而重修的同学通常周末的课表也很满。个人不喜欢这种课多的生活，喜欢兴趣驱动的学习，不喜欢自己的学习方向太受外力的牵引。

4. The End
    总是有一种声音提醒自己，我不属于这里，注定不属于。太多的不应该出现的巧合，太多的主观的或是客观的借口。我有自己的天地，那里与浙大没有交集，即便我希望会有。

5. Acknowledgements
    感谢浙大那些被我折腾、蹭吃蹭喝的同学。
    感谢版主的m或b。

6. References
[1] 黑白剧社 http://www.qsc.zju.edu.cn/heibai/
[2] 我在天堂等你 http://www.douban.com/subject/1310322/
[3] 榆树下的欲望 Desire Under the Elms, http://www.douban.com/subject/1297393/
[4] Structure and Interpretation of Computer Programs, http://www.douban.com/subject/1451622/
[5] 暗恋桃花源，富含搞笑因素却又错综复杂值得深深体味的一部话剧，推荐一看 http://www.douban.com/subject/1299889/
[6] 春琴传，较传统的日本爱情故事 http://www.douban.com/subject/1949657/

其实理解了 Regular Expression -> NFA -> DFA 这个过程，大致的复杂度确定也不难

发信人: styc (styc), 信区: Algorithm
标  题: Re: 请问一下大家正则表达式的时间复杂度
发信站: 水木社区 (Wed Mar 26 20:37:02 2008), 站内

NFA构造O(n)，匹配O(nm)
DFA构造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)
n=regex长度，m=串长，k=字母表大小，n'=原始的dfa大小
大概是这样子吧

本来想看完pagefault的处理的，不过实验室有事情了，只能先把这一半放上来了。

页面的分配与回收使用了一个叫做buddy allocator的机制，kernelnewbies上的解释
The memory allocation scheme used in the kernel. A vector of lists of free pages is kept, ordered by the size of the chunk (in powers of two). When a chunk is allocated, it is removed from the relevant list. When a chunk is freed back to the free pages pool, it is placed in the relevant list, starting from the top. If it is physically contiguous with a present chunk, they are merged and placed in the list above (i.e. where the chunks are twice the size), and this operation percolates up the vector. As regions are merged whenever possible, this design helps to reduce memory fragmentation.

首先在zone_struct{} 中保存了一个free_area_t数组，这个数组记录了各种大小的空闲内存块的信息。
include/linux/mmzone.h:

/**/ /*
 * On machines where it is needed (eg PCs) we divide physical memory
 * into multiple physical zones. On a PC we have 3 zones:
 *
 * ZONE_DMA      < 16 MB    ISA DMA capable memory
 * ZONE_NORMAL    16-896 MB    direct mapped by the kernel
 * ZONE_HIGHMEM     > 896 MB    only page cache and user processes
  */
typedef  struct  zone_struct  {
     /**/ /*
     * Commonly accessed fields:
      */
    spinlock_t         lock ;
    unsigned  long         free_pages;
    unsigned  long         pages_min, pages_low, pages_high;
     int             need_balance;

     /**/ /*
     * free areas of different sizes
      */
     //  数组中每个元素依次维护1个pagesize，2个pagesize，4个pagesize……的空闲块的链表
    free_area_t        free_area[MAX_ORDER];  

     /**/ /*
     * Discontig memory support fields.
      */
     struct  pglist_data     * zone_pgdat;
     struct  page         * zone_mem_map;
    unsigned  long         zone_start_paddr;
    unsigned  long         zone_start_mapnr;

     /**/ /*
     * rarely used fields:
      */
     char              * name;
    unsigned  long         size;
}  zone_t;

typedef struct free_area_struct {
    struct list_head    free_list;
    unsigned long        *map;       // 某个特定大小的页面块分配情况的位图
} free_area_t;

Welcome to Microsoft DreamSpark

Professional Developer and Designer tools

• Sign In with your Windows Live ID. If you don't have one, go get one here. Pretty basic stuff.
  
  
• Get verified as a student. The system is linked to schools and organizations around the world that can confirm student status. Simply choose your country and school, enter your info and hit submit.
  
  
• Download your products. Now remember these are professional tools. This means they are pretty big files so make sure you have the bandwidth and space to bring them to your machine. We support the latest versions of both Internet Explorer and Firefox for your download.

#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>

#define KEY 1234
#define SIZE 1024

int main()
{
    int shmid;
    char *shmaddr;
    struct shmid_ds buf;

    shmid = shmget(KEY, SIZE, IPC_CREAT | 0600);
    if (shmid == -1) {
        printf("Failed in creating shared memory: %s\n", strerror(errno));
        return 0;
    }

    if (fork() == 0) {
        shmaddr = (char *) shmat(shmid, NULL, 0);

        if (shmaddr == (void *) -1) {
            printf("Failed in connecting to the shared memory: %s\n", strerror(errno));
            return 0;
        }
        
        strcpy(shmaddr, "Hello, this is child process!\n");
        shmdt(shmaddr);
        return 0;
    } else {
        sleep(3);
        shmctl(shmid, IPC_STAT, &buf);
        
        printf("Size of the shared memory: ");
        printf("shm_segsz = %d bytes\n", buf.shm_segsz);
        printf("Process id of the creator: ");
        printf("shm_cpid = %d\n", buf.shm_cpid);
        printf("Process id of the last operator: ");
        printf("shm_lpid = %d\n", buf.shm_lpid);

        shmaddr = (char *) shmat(shmid, NULL, 0);

        if (shmaddr == (void *) -1) {
            printf("Failed in connecting the shared memory: %s\n", strerror(errno));
            return 0;
        }

        printf("The content of the shared memory: %s\n", shmaddr);

        shmdt(shmaddr);
        shmctl(shmid, IPC_RMID, NULL);
    }
}

/**//* Obsolete, used only for backwards compatibility and libc5 compiles */
struct shmid_ds {
    struct ipc_perm        shm_perm;    /**//* operation perms */
    int            shm_segsz;    /**//* size of segment (bytes) */
    __kernel_time_t        shm_atime;    /**//* last attach time */
    __kernel_time_t        shm_dtime;    /**//* last detach time */
    __kernel_time_t        shm_ctime;    /**//* last change time */
    __kernel_ipc_pid_t    shm_cpid;    /**//* pid of creator */
    __kernel_ipc_pid_t    shm_lpid;    /**//* pid of last operator */
    unsigned short        shm_nattch;    /**//* no. of current attaches */
    unsigned short         shm_unused;    /**//* compatibility */
    void             *shm_unused2;    /**//* ditto - used by DIPC */
    void            *shm_unused3;    /**//* unused */
};

/**//* Obsolete, used only for backwards compatibility and libc5 compiles */
struct ipc_perm
{
    __kernel_key_t    key;
    __kernel_uid_t    uid;
    __kernel_gid_t    gid;
    __kernel_uid_t    cuid;
    __kernel_gid_t    cgid;
    __kernel_mode_t    mode; 
    unsigned short    seq;
};

mode为该共享的内存的读写权限，和chmod的参数有点像。mode低九位定义了访问许可，解释如下：
0400 用户可读  0200用户可写  0040 组成员可读  0020 组成员可写  0004 其他用户可读  0002 其他用户可写
没有执行位 0100 0010 和 0001