Kernel Space

March 11, 2007

STL 源码研读笔记(1)

Filed under: 编程珠玑 — agassi @ 1:31 am

    很久没上来写东西了,最近认真学习了一下C++,发现真是博大精深,以前可以说是白痴一个。当读到Template的时候,确实很好奇,因为自己确实想彻底弄清楚模板这块。看完后就想找个地方试试看自己看懂了没有,很自然的就想到了STL。
    STL确实是一个很实用的东西,最重要的是他写得通用而且已经作为了C++的标准放入了所有的C++ distribution中。想看看自己模板学好了没有,就去读STL。以前也想过研究这个library,后来发现自己被一大堆的”<“和”>”彻底打懵了。现在再钻进去看,觉得清楚多了。候先生的《STL源码剖析》确实是好书,可惜电子版只有前面四章,托国内同学买也未果,所以就有了这个“STL 研读笔记系列” -- 自己把感兴趣的部分读懂,然后做做笔记。

    一开始当然要从最简单的template class开始。什么最简单?vector? list? 我觉得是auto_ptr。 这个auto_ptr是一个非常简单的smart pointer类。说它简单是因为它只具有自动释放内存(析构)的功能,没有对象指针引用计数的功能。好,废话少说,这就来看看这个类。

    //一个wrapper class,这个类模拟了auto_ptr的reference类型。可以被一个传回auto_ptr值的函数赋值。
   template<typename _Tp1> struct auto_ptr_ref
     {
       _Tp1* _M_ptr;
explicit
       auto_ptr_ref(_Tp1* __p): _M_ptr(__p) { }
     }; 
   //下面这个是真正的auto_ptr模板类。它唯一的成员数据就是一个模板类型的指针,这个是真正指向需要“保护”的对象的指针
   template<typename _Tp> class auto_ptr
      {
      private:
        _Tp* _M_ptr;
      public:
        typedef _Tp element_type;
       
        //构造函数,explicit表示这是一个禁止constructor conversion的构造函数,传入的参数必须是_Tp*类型
        explicit auto_ptr(element_type* __p = 0) throw() : _M_ptr(__p) { }
        
        //同类型拷贝构造函数,参数是另外一个auto_ptr,但是这个auto_ptr要释放自己所包含的指针。正式这个move而不是copy的语义导致了“千万不要使用类型为auto_ptr的容器”!
        //这个模板类比较特殊,数据是指针,所以允许不同类型之间的拷贝
        auto_ptr(auto_ptr& __a) throw() : _M_ptr(__a.release()) { }
        
        //不同类型的拷贝构造函数,同样也是move的办法
        template<typename _Tp1> auto_ptr(auto_ptr<_Tp1>& __a) throw() : _M_ptr(__a.release()) {}
        //同类型的auto_ptr赋值操作符,__a释放自己包含的指针,本模板类用reset更新自己的指针为__a的指针
        auto_ptr& operator=(auto_ptr& __a) throw()
        {
        reset(__a.release());
        return *this;
        }

        //不同类型的auto_ptr赋值操作符
        template<typename _Tp1> auto_ptr& operator=(auto_ptr<_Tp1>& __a) throw()
        {
        reset(__a.release());
        return *this;
        }

        //析构函数,当auto_ptr走出scope的时候,自己释放对象。但是这里的局限就是delete,而不支持释放数组对象数组的delete []。所以决定了auto_ptr只能hold单一指针。
        ~auto_ptr() {delete _M_ptr;}

        //重载dereference操作符。
        element_type& operator* const throw()
        {
         _GLIBCXX_DEBUG_ASSERT(_M_ptr != 0);
         return *_M_ptr;
        }

        //重载“member access from a pointer” 操作符。注意这里的返回值和上面的dereference返回值不同,这里返回的是成员指针。当需要调用auto_ptr->func()的时候,实际上是调用了 auto_ptr->()->func(),这个是C++内部处理的。
        element_type* operator->() const throw()
        {
           _GLIBCXX_DEBUG_ASSERT(_M_ptr !=0 );
           return _M_ptr;
        }

        //获取成员指针函数
        element_type* get() const throw() {return _M_ptr; }

        //获取成员指针函数,同时将成员指针清零
        element_type* release() throw()
        {
           element_type* __tmp = _M_ptr;
           _M_ptr = 0;
           return __tmp;
        }

        //释放成员指针所指向的对象,同时给成员指针赋新值
        void reset(element_type* __p = 0) throw()
        {
         if (__p != _M_ptr)
           {
            delete _M_ptr;
           _M_ptr = __p;
         }
         }
          
        //从auto_ptr_ref构造auto_ptr的构造函数
        auto_ptr(auto_ptr_ref<element_type> __ref) throw() : _M_ptr(__ref._M_ptr) { }

        //从auto_ptr_ref的赋值操作符,包含self-assignment 检查。前面的赋值操作符没有这个检查,因为当时只是指针的赋值,不涉及内存的释放。
        auto_ptr& operator=(auto_ptr_ref<element_type> __ref) throw()
        {
          if (__ref._M_ptr != this->get())
         {
           delete _M_ptr;
           _M_ptr = __ref._M_ptr;
         }
          return *this;
        }

        //本auto_ptr到其他任意类型auto_ptr_ref的conversion操作符重载
        template<typename _Tp1>
          operator auto_ptr_ref<_Tp1>() throw()
          { return auto_ptr_ref<_Tp1>(this->release()); }

        //本auto_ptr到其他任意类型的auto_ptr的conversion操作符重载
        template<typename _Tp1>
          operator auto_ptr<_Tp1>() throw()
          { return auto_ptr<_Tp1>(this->release()); }
    };

    好了,写到这里自己也温习了一遍,也收获不小,下次再选一个稍微复杂一点的来分析一下。
   

Advertisements

February 6, 2007

编程点滴(1)

Filed under: 编程珠玑 — agassi @ 11:24 pm

自己写了一个传输层的library,结果没有经过仔细的测试就给别人用了,结果问题百出。其实自己写的Code就是烙上自己商标的商品,如果质量有问题,当然不能接受,同时也有损自己的“声誉”。更何况自己这个library用了自己以前从来没有用到的epoll和IOCP技术,就更有理由要仔细测试了。在编写测试程序的时候出现了一些问题,其实都是以前碰到过的问题,只是没有记录下来,现在又反复犯,看来这个Blog还是很重要的!!

  • 当要开大数组的时候最好用heap:今天要开一个16K的数组用于发送测试数据,结果图省事就开了一个16K的数组(因为栈比堆更高效的印象深深印在脑中)。后来程序就randomly的出现SEGFAULT(Under Linux)。dump出来的core file也没有任何信息含量。自己最终百思不得其解。结果问了高人才知道这个Linux有个系统堆栈大小,如果是内核编程应该在1K以内,这个用户模式也大不到哪去。后来换成heap就搞定了!! (好像修改 ulimit 的stack size也不管用)。
  • 跨module内存分配和释放最好使用global allocator:一直不明白STL的allocator自己什么时候用得到,今天就知道了。现在的程序分层很明显,然后一个层又是一个so文件或者dll文件,层和层之间需要传递数据。为了提高效率,通常不会使用频繁的数据拷贝,所以经常是一个内存块从底层开始引用到最高层。后果就是,上层模块在使用完内存后不能跨模块释放内存。今天就碰到了这个问题(至少malloc/free不行,M$的GlobalAlloc/GlobalFree好像可以,所以叫Global)。一个折中的办法就是分配内存的模块提供一个释放内存的函数,缺点就是这个函数需要被各个层包装起来。比较好的办法就是使用一个global的allocator,这个是个单独的模块,其他各个模块都可以引用,STL的容器就缺不了这个东东。以后有机会研究一下STL的allocator。(这里有个很好的讨论贴讨论跨模块内存分配释放 http://blogs.msdn.com/oldnewthing/archive/2006/09/15/755966.aspx这里再强调一下,跨module分配释放内存要特别注意,10天后的今天同样的bug发生在了别人身上,还浪费了几个小时去理解“Invalid Address specified to RtlValidateHeap”这个消息到底是什么意思。
  • 网络拆包要考虑周全:记得很久以前参加ACM比赛,一道训练题目就是模拟电梯程序。结果自己冥思苦想了N久才搞定,主要问题就是有太多逻辑分之需要考虑。其实拆包这个也不复杂,但是可能是自己退化比较严重,少考虑了一种情况,导致Access Violation。我考虑了收到部分payload的情况,漏掉了收到部分header的情况。可能是觉得header太小,估计不会分两次收到;而且Linux下确实没有出现这种情况,Windows的Socket就非得把缓冲填满了,然后通知程序,结果出现了这个问题。4个字节的header结果只有两个字节数据,还有另外两个字节在下一次接受。看来自己如果要做Testing还需要很多磨练啊。
  • 输出到屏幕和重定向到文件的区别(Linux):今天在调试的时候发现server端的输出重定向到文件总是不完全,发送100个包少输出2个,发送1000个少10个。。。但是如果只是输出到terminal屏幕不会出任何问题。而且每次运行同样的数据,输出文件总是break在同一行的中间。后来用了tee,让信息同时输出到屏幕和文件,结果还是同样的问题,而且屏幕输出都break了。看来是这个I/O重定向的问题,因为tee的输出还是会经过写文件。一怒之下,请出strace来帮忙。结果真相大白: 如果只是输出到屏幕,底层的write系统调用会把收到的信息马上输出到stdout上;反观I/O重定向,系统总是攒够了4K的字节才调用write写入到文件中,这是因为I/O操作本来就很慢,所以采用page size 大小作为缓冲。问题就出在server端最后调用了一个会sleep的函数,然后wait forever;结果就在系统准备把最后的几千个字节写入文件的时候,主线程进入了sleeping状态,导致写入失败(或者根本就是pending)。如果任务执行完后立刻退出,则输出文件就是完整的。看来sleeping的线程将停止一切活动,具体为什么有待查阅进程管理的内核有关章节!
  • High Speed Consecutive Sending:这个情况发生在Linux上。当连续不断的调用send的时候,系统会出现莫名其妙的SEGFAULT(莫名其妙表示corefile没有任何信息含量),个人认为可能程序flush了系统的socket buffer。所以我在每个send后面放了个usleep(1)。就是这一个microsecond,居然起了大作用。但是原因是什么自己还不清楚,也许这个usleep也是个治标不知本的办法。需要再多学习系统内核!!!

很多东西都是经验,自己真正动手写,动脑想才会真正理解一些别人的精妙的设计,才会使自己的编程能力有质的飞跃。

January 30, 2007

编程原语之三 — 线程池

Filed under: 编程珠玑 — agassi @ 12:04 pm

最近又需要实现一个线程池,所以说说这个topic。

当需要处理大量数据的时候,线程池是比较高效的办法。传统的方法是为每个任务创建一个线程,结果就是线程创建带来的开销。所以线程池采用的是线程的预创建技术。在开始处理数据之前,创建好一定数量的线程,同时在整个处理过程中,这些线程都一直存在不会退出。

在线程池内部,有一个queue用来维护等待处理的任务。在实现的过程中,我发现最主要的是做到这个线程的通用性,也就是和处理的具体任务无关。实际上跟具体任务有关的就是queue当中的元素类型和任务的处理函数。为了达到这个目的,我用如下结构和函数指针的定义:

typedef struct {
  int taskid;
  void* taskdata;
} task_t;
typedef void* (*disposer)(task_t);

 结构中使用了void*来表示一种通用的任务数据类型。disposer是具体的任务处理函数的一种抽象,参数就是一个任务。

运行的具体流程是:主线程调用线程池创建函数,所有工作线程处于等待信号的blocked的状态;主线程得到新任务,调用线程池的doWork函数将任务放入内部队列中,同时发出唤醒信号;其中一个工作线程被唤醒,利用函数指针disposer所指向的函数处理任务;任务处理完成后重新进入等待状态。(也可以让线程池内部维护一个线程状态的数组,每次有新任务,就检查这个数组,找出空闲的线程)

 以上是一个很标准的实现。但是在实现中也遇到了一些问题,比如说用signal好还是用broadcast好,后来认为broadcast会带来不必要的contention,所以没用。在测试的时候发现,当任务数量很少的时候几乎是同一个线程每次都拿到任务,而其他的线程都starve了(这个还没想清楚为什么);后来发现当任务多的时候,其他的线程还是有很多机会拿到任务的;同时发现printf会极大的影响多线程任务的输出结果,测试的时候还是多把stdout 重定向到一个文件当中比较好。

线程池的变形也有很多,其中比较著名的是Leader/Follower模式。这个模型进一步节省了主线程(Leader)给工作线程(Follower)分配工作的开销 (之前的模型可以叫做Boss/Worker模型)。 主要的思想就是线程池的线程中有一个是Leader,Leader每次拿到任务后不再分配,而是把自己变成follower,然后处理这个任务,同时再选出一个空闲线程作为Leader继续等待任务,这样就节省了Boss和worker之间的任务分配(找出空闲线程)和不必要的数据拷贝。(以后有机会就实现一下这个模型,可能还会遇到一些具体的问题。)

三个原语基本介绍完了,以后可能还会发现更多的原语,但是这三个原语基本上可以构成一个软件的核心了。对于数据处理型软件,第一步就是获得数据,通常是网络,所以处于最前端的是I/O模型,优秀的I/O模型能够高效的实现海量连接。同时处理I/O的线程也就成为了producer,这些数据被放入queue中等待多个consumer的处理,这里就是线程模型。为了高效的处理任务,在consumer一端通常使用线程池。所以,这几个原语是密不可分,相辅相成的(怎么读起来像中学政治教材。。。)。

January 19, 2007

牛角尖之二 — Binary Semaphore & Mutex

Filed under: 编程珠玑 — agassi @ 2:27 pm

关于semaphore和mutex的区别,网上有著名的厕所理论(http://koti.mbnet.fi/niclasw/MutexSemaphore.html):

Mutex:Is a key to a toilet. One person can have the key – occupy the toilet – at the time. When finished, the person gives (frees) the key to the next person in the queue.

Officially: “Mutexes are typically used to serialise access to a section of  re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.”
Ref: Symbian Developer Library

(A mutex is really a semaphore with value 1.)

Semaphore:

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count – the count of keys – is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Officially: “A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).”
Ref: Symbian Developer Library

 所以,mutex就是一个binary semaphore (值就是0或者1)。但是他们的区别又在哪里呢?主要有两个方面:

  • 初始状态不一样:mutex的初始值是1(表示锁available),而semaphore的初始值是0(表示unsignaled的状态)。随后的操作基本一样。mutex_lock和sem_post都把值从0变成1,mutex_unlock和sem_wait都把值从1变成0(如果值是零就等待)。初始值决定了:虽然mutex_lock和sem_wait都是执行V操作,但是sem_wait将立刻将当前线程block住,直到有其他线程post;mutex_lock在初始状态下是可以进入的。
  • 用法不一样(对称 vs. 非对称):这里说的是“用法”。Semaphore实现了signal,但是mutex也有signal(当一个线程lock后另外一个线程unlock,lock住的线程将收到这个signal继续运行)。在mutex的使用中,模型是对称的。unlock的线程也要先lock。而semaphore则是非对称的模型,对于一个semaphore,只有一方post,另外一方只wait。就拿上面的厕所理论来说,mutex是一个钥匙不断重复的使用,传递在各个线程之间,而semaphore择是一方不断的制造钥匙,而供另外一方使用(另外一方不用归还)。

前面的实验证明,mutex确实能够做到post和wait的功能,只是大家不用而已,因为它是“mutex”不是semaphore。

好了,这个问题就不要再钻牛角尖了,差不多了:)

January 18, 2007

牛角尖之一 — Condition Variable & Mutex

Filed under: 编程珠玑 — agassi @ 8:19 pm

看到了sodme的“孔乙己”系列,觉得自己跟他很像,都非常喜欢钻牛角尖。他那个a[1]的数组用a[10000]来访问问题确实经典值得挖掘,他也确实在这个问题上“孔乙己”了N次了,有时间一定好好研究研究。

这次说说这个CV。以前看pthread只注意了create, mutex, join, detach, exit等函数,每次看到这个CV和一系列围绕CV的函数确实没怎么感冒,只是朦胧的觉得有这么个咚咚。最近终于知道了他的本来面目,顿时让我对线程模型有了新的认识,所以有了前一篇文章。

其实大可以把CV看成Semaphore,这样想自己就清楚多了(面试的时候不知道被问了多少次什么是semaphore)。不过他们在实现上肯定是有区别的,我们就暂时先不钻这个牛角尖了。为了简单,就从简单的单producer单consumer说起。

通常有一个global的结构包括了一个state,一个mutex和一个CV。在producer这边,常用的代码是:

                       int dosignal;
                       pthread_mutex_lock(&m);
                       dosignal = (state == unsatified);
                       state = satisfied;
                       pthread_mutex_unlock(&m);
                       if(dosignal)
                             pthread_cond_signal(&cv);

 consumer通常的代码是:

                       pthread_mutex_lock(&m);
                       while(state!=unsatisfied)
                            {
                                 pthread_mutex_unlock(&m);
                                wait_on_cv(&cv);
                                    pthread_mutex_lock(&m);
       }
                        state = unsatisfied;   //consumed
      pthread_mutex_lock(&m);

上面的wait_on_cv函数是我自己编造了,实际上Pthread中没有提供专门的在CV上wait的函数,而只提供了与mutex捆绑的pthread_cond_wait和pthread_cond_timedwait函数(《Win32 System Programming》提到说这是一个wise的选择)。事实上,“CV必须和一个mutex一起使用”的原则决定了这个。同时为了避免前一篇中提到的信号丢失的情况,上面黑体的两个操作被实现为原子操作。上面斜体的三步操作就是pthread_cond_wait。所以,consumer的代码是:

                       pthread_mutex_lock(&m);
                       while(state!=unsatisfied)
                                  pthread_cond_wait(&cv, &m);
                        state = unsatisfied;   //consumed
      pthread_mutex_lock(&m);

CV实现了一种semaphore的机制。但是想到mutex,好像也可以wake up一个被lock住的thread。当一个线程unlock的时候,相当于通知了一个另外的调用lock的线程。

仔细研究UNP Vol2,终于发现了一段比较mutex,CV和Semaphore的文字。 

  • 一个mutex只能在同一个线程中被unblock,而且这个线程必须是曾经lock过这个mutex。
  • 另外还有CV和Semaphore的区别:Semaphore执行post操作后,Semaphore的状态保持signaled,直到有wait操作发生。而CV在调用pthread_cond_signal时如果没有线程调用了pthread_cond_wait,这个信号将丢失。这也是pthread_cond_wait中要原子化两个重要操作的原因。

 抱着对以上文字怀疑的态度,于是有了下面这个测试程序:

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void* producer(void *arg)
{
        sleep(2);   
        int ret = pthread_mutex_unlock(&mutex);
        printf(“producer return %d\n”,ret);
}
void* consumer(void *arg)
{
        printf(“consumer locking\n”);
        int ret = pthread_mutex_lock(&mutex);
        printf(“consumer return %d\n”,ret);
}
int main(int argc, char** argv)
{
        pthread_t tid1,tid2;
        pthread_mutex_lock(&mutex);
        pthread_create(&tid2,NULL,consumer,NULL);
        pthread_create(&tid1,NULL,producer,NULL);
        pthread_join(tid1,NULL);
        pthread_join(tid2,NULL);
        return 1;
}

实际的打印结果着实让我觉得意外。

consumer locking
(slept 2 sec here)
producer unlocking
consumer return 0
producer return 0

consumer线程被lock住了,这个是expected。但是producer依然可以用unlock函数来解锁,虽然之前它没有调用过lock。随后又做了一个试验,把上面两行斜体的代码交换一下,也就是先启动producer然后启动consumer,同时去掉sleep,输出结果为:

producer unlocking
producer return 0
consumer locking
consumer return 0

结果同样说明了,producer中的unlock依然可以将不是自己lock的mutex解锁,从而让consumer能够得到mutex,起到了signal的作用。

依此看来,pthread的mutex就是一个binary semaphore,可以在任何地方wait和post。当然实际应用当中还是应该遵循书中的规定,养成良好的使用mutex的习惯。

编程原语之二 — 线程模型

Filed under: 编程珠玑 — agassi @ 6:10 pm

最近需要实现一个跨Linux和Windows的线程库,所以仔细研究了一下这两个平台的线程模型,收获颇丰。

 其实在实际工作中,线程的使用就跟printf一样平常。可能是以前做的东西大多数都是course project 或者根本没有想到提高效率,所以基本上没有用到多线程,所以现在才有捉襟见肘的感觉。找工作的时候看过很多多线程的东西,脑子里堆积了很多概念,但是他们到底有什么区别,各有什么特点,什么时候用却根本处于一团乱麻的状态。

首先想到的当然是UNP Vol2 这本圣典,里面专门有一个Part(包括5个章节)是介绍同步的。当然这里面的东西比较杂,包括线程同步和进程同步,POSIX和非POSIX的标准。我主要注意看的是线程同步和POSIX标准,也就是Pthread标准。同时在Windows方面,参考了一下Win32 System Programming里面关于线程同步的章节(在Windows核心编程里面好像有细致到汇编和内核的叙述,有时间一定要补上)。

言归正传,两个平台下各有一些用于同步的原语:

  • Linux (Pthread) : Mutex和Condition Variable (CV)。Semaphore不是Pthread标准的一部分,但是CV在行为上跟semaphore很相似。
  • Windows:Windows很少服从什么其它的open source的标准,这次也不例外。Windows有一套Interlocked的API用于实现一些原子操作。线程同步用到的主要有MutexEvent(当然还有Semaphore和CriticalSection,因为Pthread里面没有,所以这里略之)。这里的Event就和Pthread里面的CV很相似。

多线程模型里面最著名的就是producer-consumer模型(记得大三的时候上操作系统的时候讲过,可惜当时没有认真听,不过当时也没有什么动力去理解透彻:-))。这个模型里面重要的资源就是一个limited buffer,这个buffer空的时候consumer不能读取,buffer满的时候producer不能放入数据。

  • 单producer单consumer模型:无论是什么模型,在修改共享资源的时候都必须锁住mutex。Event或者condition variable用来通知对方一定的事件,比如:新的product放入buffer了,或者product已经被取走了;或者用于producer在buffer满时候的等待和consumer在buffer空的时候等待。最近碰到的比较典型的应用就是一个共享内存区的通信(这个是进程间同步):一块共享内存,需要一个mutex和一对Event来实现互斥访问和数据取出和放入的通知。
  • 单producer多consumer模型:多个consumer使得它们之间形成了竞争关系。当producer放入数据后,会通知(signal)consumers。有的consumer可能被唤醒了,却发现没有数据available,这个就是 spurious wakeups现象。这个现象产生的原因就是因为多个consumer同时被唤醒,而其他的consumer被唤醒后率先处理掉了所有的数据,或者producer在没有锁住mutex的情况下发送了通知。所以当consumer被唤醒后检查状态是很必须的。Pthread提供了pthread_cond_wait函数用于做到释放mutex和等待CV的原子操作,Windows在 Windows 2000/NT 以后也提供了SignalObjectAndWait 这个API来实现类似的操作。这个原子操作避免了释放了mutex后wait on CV前发生context switch,producer这时发出了通知,而consumer将错过这个signal从而错过了这次通知。
  • 多producer单consumer模型:照常还是需要一个mutex和一对Event/CV(用于当buffer空或者满的时候等待)。通常需要一个index用于协调producer之间放入data的顺序,这样保证producer不会overwrite其他放入的数据。
  • 多producer多consumer模型:由于共享资源还是一个buffer,所以一个mutex和一对Event/CV是必需的。因为producer和consumer之间都会出现竞争,所以put和get操作都需要一个index来控制buffer的顺序存和取。

除了线程模型,这些同步原语和具体的应用也有关系。比如说如果使用的不是buffer,而是一个queue,producer和consumer就不用关心index的问题。如果consumer并不是homogenous的,也就是说它们对buffer/queue里面不同的数据类型感兴趣,这个时候可能就需要使用broadcast来一次唤醒所有的consumer,让他们决定是否处理当前到来的数据。(Windows没有专门的broadcast函数,用Windows下的SetEvent/Manual-reset(MR)来实现,但是会引起unfairness,因为pthread_cond_wait保证每个waiting线程都有机会awake然后检查状态,而SetEvent/MR却不是这样,从而导致starvation。) Douglas C. Schmidt 有两篇近乎论文的讨论Pthread on Win32的文章,非常透彻:http://www.cs.wustl.edu/~schmidt/win32-cv-1.html , http://www.cs.wustl.edu/~schmidt/win32-cv-2.html

 线程的使用通常是提高程序性能的关键,也是比较容易忽略的一部分。因为基本的线程同步可以很容易实现,但是不同的实现方式涉及的fairness和serialization overhead确是不尽相同。而且线程的使用还涉及到线程的预创建,比如说线程池和Leader/Follower模式(再次奉献Schmidt的 http://deuce.doc.wustl.edu/doc/pspdfs/lf.pdf )。

竞争是残酷的,同样功能的软件拼的大多时候就是性能了,特别是企业级别的应用。线程的使用和前面提到的I/O模型都是提高整体性能的关键。深入的理解这些概念将会将你的编程水平提高到另外一个档次。

 写得比较杂,因为刚看了很多书,一时难以理出很好的条理来,以后有了新的想法(或者说“发现”)再继续补充。

January 16, 2007

网球Tips

Filed under: Tennis — agassi @ 1:47 am

打网球也有2年半了,其间也看了不少的教学录像,也有不少高手指教过。自己的技术也有起伏,总的来说是不稳定,打球没准。忽而觉得自己悟到了什么,忽而又全部都不work了。最近仔细研究了Nick Bollettieri 和 James Jensen的教学录像,终于总结出了以下要点。其实这些要点也是平时经常提起的,但是最终James的录像告诉了我如何才算是真正做到了这些技术点,可谓画龙点睛之video,强烈推荐。

  • Forehand
    • 转身:这个道理很简单,网球不是靠手臂的力量,是靠转身的动量。如何才能做到充分转身?--右手后挥的时候,左手跟过去,自然整个身子就转过去了。
    • 下蹲 (low foundation):这样击球才能从下往上,增加spin。
    • 保持与球距离:正手离球比反手远,避免猛冲向球导致与球太近。
    • 上臂收紧:正如LJ同学所说,挥拍时,腋下应该能够夹住一个球;球只会在挥拍的最后阶段落下。这个非常helpful。
    • 随挥(follow-through):这个很重要,但是最容易被忽略。正如James所说,随挥充分是为了增加与球contact的时间,更好的控制球的走向。如何充分随挥?--挥拍结束后,elbow对准球飞行的方向!!万分有用!!!
    • 握拍:一定要在击球一瞬间握紧,其他时候随便。注意保持semi-western grip,这个是我习惯的方式,YMMV。
    • 后挥:James另外一个很重要的point就是,一定要提早挥拍,特别是在跑动中。打Running Forehand的时候,在跑动中拍子应该是已经挥好了!!底线相持的时候,来球过网的时候自己就应该挥好了。但是过网的时候球速可能不一样,会打乱自己的节奏,所以可以干脆在对方触球的时候就开始挥拍。
  • Backhand
    • 转身:这个相对容易,因为反手需要用closed stance,转身是很自然的。如果转身不充分,很容易打出没有力量的球,而且球直接飞向对方的反手的边线外,或者容易mis-hit。
    • 下蹲(Dip & Lift):这个平时没怎么注意,后来发现下蹲不仅增加了击球的力量,更重要的是那种从下往上brush球的击球方式,大大增加了球的上旋,是打反手angle shot的法宝 (这个还有待多多练习)。
    • 后挥:同正手同样的道理。当判断出球的来路后就应该立刻后挥,然后跑动中也保持后挥。如果需要打上旋球,后挥要尽量保持拍面是close face(也就是拍面略微朝下)。
    • 迎上:反手要求与球更近,所以大多时候都有一种迎上一击的感觉,但是太近了也不好。
    • 随挥:这部分的James录像我还没有看到,所以我猜应该也是按照elbow来确定是否充分的。
  • Net Play  (这部分我很差,所以打算略过,以后补充。现阶段先做一个完全的底线型选手)
  • Anticipation
    • 打球的时候有时容易分神,“Keep the eye on the ball”这条tip容易忘掉(就像星际里面,明明知道打仗的时候不要忘记造兵,但是最后还是忘了。。。)在自己不能专注的时候,可以学习Nick的办法:当对手击球的时候自己默念 “ball”,当自己击球的时候默念“hit”。这样慢慢就能找到比赛的节奏了。
  • Footwork & Positioning
    • 自己的Footwork不止是一般的烂了。这也是所有的运动我都不行的根本原因。所以Nick的录像教了我Positioning。当自己把球击向对方场地的一侧时,自己应该站在差不多对角线的位置,这样才能让我这样Footwork差的人减少跑动。
    • Footwork用crossover steps,这个基本没用到。。。。
  • Rhythm
    • 节奏很重要,它可以帮助你稳定情绪。我觉得更重要的是,让我面对来球的时候不会急着冲上去,而是等到球的下降期再打;有意让自己保持一定的节奏,非常有助于保持与来球的距离。

折腾真土(Gentoo)– 休眠功能

Filed under: 折腾电脑 — agassi @ 1:17 am

本以为装好了一个version的内核就万事大吉了。殊不知麻烦接踵而至。
想给本本装个suspend2,这样不用的时候就可以休眠了。但是suspend2需要patch内核,所以follow instructions编译好了内核。启动的时候结果出现了 “cardmgr [xxxxx]: no sockets found”的错误。随后eth0启动失败(”netmount” was not started)。这下蒙了。网上搜了很多,也又编译了几次内核,未果。

仔细一想,第一次build内核的时候用的是genkernel这个工具,所有的配置都是从LiveCD配置好的文件复制过来的,自己没怎么注意。但是Handbook有一个manual configuration的说明,当时图省事略过没看。现在需要重新看看了。先用”make menuconfig”打开内核配置程序,把PCMCIA的相应选项都勾上,尤其是PC-card bridges 的那些选项。重新编译内核,cardmgr的错误没了,但是eth0还是不能启动。网上的帖子显示应该是驱动的问题,但是原来的内核都有这个驱动,我新编译的这个怎么会没了?看来还是内核选项的问题。继续menuconfig,发现了Intel PRO/100+ 网卡的驱动,心中大喜,立刻勾上。再次编译内核,通过!!!!

这样看来当时省事,让genkernel代劳确实给自己添了不少麻烦。以后应该多manually操作!!!

折腾真土(Gentoo) — 安装

Filed under: 折腾电脑 — agassi @ 1:15 am

半年前写的了,一直放在硬盘上,现在放上来算是做个备份。

Gentoo 不同于RH,Debian,Ubuntu等基于binary得distribution。 Gentoo提供的是代码级别的distribution。也就是说,每台安装的机器都需要重新编译内核,从而获得最大的optimization。当然对于linux的学习也有很大帮助,因为整个安装过程都是manually的。

网上的Gentoo的文档做得很全。安装的部分主要参考Gentoo的官方Handbook. http://www.gentoo.org/doc/en/handbook/handbook-x86.xml

总的来说,Gentoo首先利用一个LiveCD用光盘、内存和临时磁盘空间构建一个Gentoo的运行环境。这个环境甚至还提供了X系统和installation wizard(我没有使用这个wizard,而是按照handbook一步一步走)。接下来的主要工作就是在这个环境中,利用shell命令一步一步构建真正的系统(Gentoo Base System)。

1.战前准备
  a) 先到mirror上抓个up-to-date的iso (我用的是livecd-i686-installer-2006.0.iso)。然后烧到cd-r上。
  b) 放到我的小笔记本的光驱里面,启动!  随后就进入了Gentoo的GNOME桌面,用户都是默认的。当然可以改改用户,或者提高磁盘性能等,我都略过。但是发现不能上网,笔记本的LAN和WLAN都没有连接上。dmesg一把,发现都fail了。于是试了一下Handbook建议的 “modprobe 8139too” 然后 ifconfig,果然搞定了那个网卡,wireless还没搞定(只好暂时先插上网线将就一下)。

2.文件系统
  a) 分区当然是首当其冲的事情。笔记本上还有windows NTFS分区,操作的时候就得小心一点。用fdisk的基本命令p,d,n,t等设置好/boot, /, swap分区。由于我还希望能够suspend系统,所以swap给了接近1G的空间。
  b) 创建文件系统。/和/boot都是ext3, 用mke2fs -j 就好。 mkswap和swapon用来初始化和激活swap分区。
  c) 最后把/和/boot分别mount到/mnt/gentoo下面,因为下一步就要chroot到/mnt/gentoo 进行基本系统的安装了。

3.继续准备
  a) 下载stage3 tarball: gentoo提供的links类似于以前用过的lynx,可以surf到网上抓个stage3的tarball下来。stage3 tarball是root目录的打包,解压后就是root目录的内容了。
  b) 安装Portage snapshot: Portage是从FreeBSD那里学来的东东。类似于Debian的APT。下载和安装module就全靠它了。在LiveCD的snapshot目录下有个tarball,直接cp过来解压。这个不是portage本身,而是一些可以安装的软件列表(为了通知portage)。
  c) 最后check一下/mnt/gentoo/etc/make.conf里面的编译选项,然后就准备正式安装系统了。(恩,比较累,干了这么久其实才刚开始安装系统)

4.安装开始!
  a) Chrooting: chroot之前首先用mirrorselect找一些近的mirrors。 我把所有USA的site都勾上了。随后就是保存dns信息(拷贝resolv.conf)。mount proc和dev到/mnt/gentoo下面。 随后 “chroot /mnt/gentoo /bin/bash” 一执行,我们就来到了新系统的root下了。
  b) 更新Portage Tree: 用 “emerge –sync” 获取最新的软件列表。我似乎选了太多的mirror,结果这里等了N久。
  c) 内核安装:用”USE=”-doc symlink” emerge gentoo-sources” 抓下来一个最新的内核。用 “zcat /proc/config.gz > /usr/share/genkernel/x86/kernel-config-2.6″直接把之前的内核配置复制过来,避免繁琐的手动配置。 随后emerge一个genkernel下来,用 “genkernel all” 命令编译内核,而不用make menuconfig + make && make modules_install 了。

5.系统配置
  a) 经过漫长的等待,内核已经编译完毕了。接下来就该为最后系统启动做准备了。首先当然是配置文件系统。handbook里面的命令是用nano编辑/etc/fstab。这个nano是gentoo自带的一个编辑器。用vi的我自然不会选择它。既然能够上网了,就emerge一个vim(好像搞到的还是6.4版本的,估计mirror上还没有7.0的)。按照example,为/boot,swap,/ 写好entry。
  b) 网络也要配置一下。那些啥domainname什么的就没管他们了。主要就是编辑一下/etc/conf.d/net,既然是用的dhcp自然就简单多了。然后用rc-update让系统启动的时候就启动eth0。
  c) 后面的步骤基本略过,除了那个CLOCK选项,因为我的本本上还有一个windows xp。
  d) 几个tools还是很重要的: udev 设备管理器;system logger; cron 我装了个dcron ; dhcp client 要是没这个,reboot后就连不上网了,那就郁闷了;
  e) bootloader的安装:装了那么多次linux还是第一次自己安装grub。 emerge了一个grub然后编译了半天。随后就跟以前一样了:编辑一下/boot/grub/grub.conf。设定好kernel和initramfs的路径。当然更重要的是给我的xp添加一个条目。

6.尾声
  a) 好了,基本上都搞定了。仔细检查一下几个配置文件,然后就exit到原来的root下,umount所有挂载的分区。然后reboot!!!!!!!!!!
  b) 取出光盘,满怀期待的等待 “localhost login:”的出现。结果,Oops,出了个错,说什么/dev/hda6 fsck.ext3的问题。郁闷,仔细看了看/etc/fstab愣是没看出问题来。到网上找了找,有类似的故障,但是solution都不work!!!更加郁闷。找来LiveCD重新启动(只有用LiveCD启动进入才能修改fstab),mount上我的/分区,打开/etc/fstab一看!我考,居然hda3,hda5,hda6都写成了dev3,dev5,dev6。马上改过来,然后umount,reboot!!!  搞定!!!  看来现在眼神不行了啊。。。。
  b’) 现在这个系统跟以前装的系统都不一样了,主要的区别就是这个linux“啥也没有”。vim是刚装的,连grub都是自己装的。以后可以根据自己的需要添加一些自己经常用的东东(比如gcc,gdb,xmms等)。在安装的过程也能够对文件系统,内核编译,网络基本配置等有一些上手的操作,对喜欢折腾的同学来说比较适合。现在这个系统,启动十分迅速,再加上强大的vim+ctags,是阅读和学习内核的利器。下一次,我会继续share一下安装X系统的体会。

January 12, 2007

编程原语之一 — I/O 模型

Filed under: 编程珠玑 — agassi @ 2:30 am

 工作了半年了,发现了一些概念性的东西在工作当中非常有用。这些概念几乎场场用到,无论是做什么应用(所以我称之为“原语 primitives”)。以前也略知一二,但是现在发现自己懂得实在是太浅显。最近看了以前找借口没有完成的书,受益匪浅。

 说起来接触网络编程也有很久了,但是始终觉得是混沌一坛。不过仔细一回想,自己确实很少写网络程序。再加上这两年都在学校混,主要也就写写course project,没有什么练手的机会。最近需要实现一个SDK的传输层,打开IDE发现无从下手,顿时觉得自己确实都还给老师了(好像没有老师教过这个:))。立刻找来UNP (3rd edition) 和 NPMW (2nd edition)。这两本书在前面有提到。是Unix 和 Windows下网络编程的圣典。对于这种大簿头的书,直接拣重点看。那些基本的API还是有印象的。

Unix: UNP这本书也是摆在书架很久了,一直觉得是手册,其实就是一个不去读的借口。翻到“I/O Models” 一章,立刻看到几个非常形象的图,顿时心里有了概念。

  • blocking : 最简单的模型
  • non-blocking: 看似节省时间,实际上poll会占用更多的资源,需要和其他模型配合使用
  • I/O multiplexing: 大名鼎鼎的select和poll。写网络程序第一个就会想到select。最大的特点其实就是可以同时wait在多个 I/O 上。从原理上讲还是blocking的,而且不太efficient,因为相比于blocking的I/O,select需要多一个系统调用。poll和select很相似,都是wait指定fd上特定事件的发生。select用fd_set把希望得到相同事件的fd放在一起,而poll是用pollfd 结构保存fd和对应感兴趣的信号。两者的设计大同小异。poll看似几乎被POSIX淘汰了。不过最近出现的epoll(一个对2.4 kernel的补丁,最终在2.6 kernel中正式加入),一跃成为Unix下处理海量连接的最佳方案。
  • signal-driven I/O: 真正的异步模式。(所谓异步,就是I/O事件发生的时候Kernel会利用Callback来通知处理数据的线程,然后该线程再去取数据。上面三个模式都是同步的,也就是说Kernel不会告诉用户程序什么时候I/O ready了。)这个模式利用的是sigaction来注册一个SIGIO的处理函数,然后系统通过SIGIO来callback 信号处理函数。
  • Asynchronous I/O: 另外一种异步模式。主要的区别是,Kernel不仅通知用户进程I/O时间,同时把数据从Kernel空间复制到用户空间,当用户空间进行处理的时候,I/O已经处于“完成”状态了。这个模型实际上就是Windows下的”完成端口”模型。书上说这个模型少有系统实现了,不过Linux是有实现的,不过据说在2.4的Kernel上不太稳定,不知2.6是否好很多。

Windows: “Windows 网络编程”一书,也是很久以前就有了,但是从来没有下功夫去看过。这次翻开,也首先翻到了 “Socket I/O Models”。简单的blocking, non-blocking 在Introduction中的connection-oriented和connection-less中就介绍了。

  • select : 上来就是select模型。这个blocking的模型基本上和Unix下的一模一样。
  • WSAAsyncSelect : Windows自然离不开它自己的东西。这个就是为Windows量身定做的函数。这个函数要求用CreateWindow创建一个窗口。然后在WSAAsyncSelect的参数中放上这个窗口的句柄。在Windows中,窗口就是一个等待处理时间的Entity,当有网络事件发生的时候,这个窗口就会收到一个在WSAAsyncSelect中指定的message,同时包括一个事件的类型。随后在窗口的消息处理函数中进行实际的网络操作。这个模型就是Windows消息句柄版本的signal-driven I/O。
  • WSAEventSelect : 这个其实是blocking的select模式的一种。Windows把Socket和著名的WaitForMultipleObjects结合起来了,利用Event来实现网络事件的通知。说到Event,自然就有signaled和non-signaled的状态以及manual和automatic的reset模式。这个也同样适用于WSAEvent。所有的Event函数都加了WSA的前缀。WaitForMultipleObjects有著名的64个Event的上限,这个WSAWaitForMultipleObjects也不例外,所以一个线程里面只能最多监视64个socket。如果要监视更多,就继续增加线程数量。看起来不是很promising哦。
  • Overlapped: 这个是书中推荐的模式。这个模型需要创建一个WSAOverlapped 结构,然后把这个结构的指针传给WSA函数,WSA函数就会自动把socket设置为non-blocking,然后进入overlapped模式。根据通知事件处理函数的方法不同,这个模型有两个形式:Event notification 和 Completion Routine。 前一个和WSAEventSelect几乎一样,主要是通过放入WSAOverlappped结构的Event句柄来唤醒等待这个I/O的线程,事件处理线程还是依旧使用WSAWaitForMultipleObjects等待;WSAGetOverlappedResult 最终用来取得事件的信息 (依旧有64的上限)。后面一个版本,表面上用到了WSAOverlapped结构,实际上只是初始化一个dummy结构,然后传给WSA函数,让其进入Overlapped模式。真正有用的是创建一个CALLBACK函数,然后把这个函数指针传给WSA函数。当有事件发生的时候,这个回调函数会被调用。这样就绕过了64个的限制。不过第二种方法要求主线程处于Alertable的状态,从而completion routine 有足够的时间处理事件。 Overlapped模型引入了完成的概念。在WSA函数中,会传入一个WSABUF结构,它里面包含了程序开辟的缓冲区,当事件被通知的时候,实际的数据已经放入这个buffer了,而不需要再复制一遍,从而提高了效率(一般的做法是把WSAOverlapped结构和一个WSABUF以及一个缓冲区做成一个PerIOData结构)。
  • Completion Port: 有名的”完成端口“模型。就是Windows版本的Asynchronous I/O。基本步骤就是创建少量的工作线程,然后创建完成端口,创建监听端口,绑定监听端口到完成端口,issue WSAAccept异步事件,在工作线程中接收连接,把新连接加入到完成端口中,在工作线程中处理已经建立的连接的IN/OUT I/O。当然,既然是完成端口,传输的数据在事件通知的时候就已经在buffer里面了。这个模型比Overlapped模型又更进了一步:每个完成端口都可以绑定一个整型的CompletionKey,这样就可以放入一个指针指向一个PerSocketData的结构,其中包括Socket的Handle,Peer的IP地址等等(类似于epoll当中的epoll_data,看到这里觉得有一种天下一统的感觉)。这个模型是目前Windows下处理海量连接的最高效的方法,稍后将讨论和比较它和epoll。

IMHO,其实就只有两种模型,至于blocking和non-blocking只是socket的本身的类型,blocking的socket函数本身就是一种blocking的模型,而non-blocking的socket是其他所有模型的基础:

  1. Synchronous,表示有一个线程处于blocked状态专门负责等待网络事件的到来(including blocking,select, poll, WSAAsyncSelect, WSAEventSelect, Overlapped with Event Notification, Completion Port); WSAAsyncSelect 其实比较特殊,用户本身不用专门创建一个线程来等待,但是Windows窗口本身有一个消息循环,在等待网络事件的时候,这个消息循环实际上帮助实现了blocked线程的工作,所以还是把它放在这个类别下。
  2. Asynchronous,表示只是提供一个回调函数,issue 网络动作后,不需要专门的线程进行等待,网络事件发生后,kernel会自动调用回调处理函数 (including signal-driven I/O, Asynchronous I/O,Overlapped with Completion Routine)。

暂时就想到这些,以后有新的想法再补充。

Older Posts »

Create a free website or blog at WordPress.com.