# ee /etc/ssh/sshd_config

PermitRootLogin yes              #允许root登录
PermitEmptyPasswords no     #不允许空密码
PasswordAuthentication yes  #需要密码认证

分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。

通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确限制for和while的使用，循环已经不能再用了。同样，递归函数也需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。

我们仍然围绕循环做文章。循环只是让相同的代码执行n遍而已，我们完全可以不用for和while达到这个效果。比如定义一个类，我们new一含有n个这种类型元素的数组，那么该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路：

class Temp
{
public:
      Temp() { ++ N; Sum += N; }

      static void Reset() { N = 0; Sum = 0; }
      static int GetSum() { return Sum; }

private:
      static int N;
      static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;

int solution1_Sum(int n)
{
      Temp::Reset();

      Temp *a = new Temp[n];
      delete []a;
      a = 0;

      return Temp::GetSum();
}

我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture（1）的时候调用第一个函数，false（0）的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：

class A;
A* Array[2];

class A
{
public:
      virtual int Sum (int n) { return 0; }
};

class B: public A
{
public:
      virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};

int solution2_Sum(int n)
{
      A a;
      B b;
      Array[0] = &a;
      Array[1] = &b;

      int value = Array[1]->Sum(n);

      return value;
}

这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为0时，执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些：

typedef int (*fun)(int);

int solution3_f1(int i) 
{
      return 0;
}

int solution3_f2(int i)
{
      fun f[2]={solution3_f1, solution3_f2}; 
      return i+f[!!i](i-1);
}

另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码：

template <int n> struct solution4_Sum
{
      enum Value { N = solution4_Sum<n - 1>::N + n};
};

template <> struct solution4_Sum<1>
{
      enum Value { N = 1};
};

solution4_Sum<100>::N就是1+2+...+100的结果。当编译器看到solution4_Sum<100>时，就是为模板类solution4_Sum以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为solution4_Sum<100>::N=solution4_Sum<99>::N+100。这个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大。

大家还有更多、更巧妙的思路吗？欢迎讨论^_^

博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。对解题思路有任何建议，欢迎在评论中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我讨论。谢谢。
from：
http://zhedahht.blog.163.com/blog/static/2541117420072915131422/

你可能没听说过“可汗学院”，但“可汗学院”的谜题被苹果采用一定是有其道理的。可汗学院由孟加拉裔美国人萨尔曼•可汗（Salman Kahan）创立，是一家由谷歌和比尔&梅琳达•盖茨基金会背后支持的教育性非营利组织，主旨在于利用网络影片进行免费授课，目前已经有关于数学、历史、金融、物理、化学、生物、天文学等科目的内容。

苹果在面试过程中随时都有可能向求职者抛出这些考验智商与逻辑的问题，因此如果你向往进入苹果工作，这些艰涩的问题在面试前必须谨慎对待仔细研究，因为苹果的原则是——不能出错，哪怕你已经级别很高，是冲着苹果的高级软件工程师职位而来也不例外。

幸运的是，这些问题虽然刁钻，但却都有唯一的答案，所以你只要有备而来，还是可以应对自如的，下面是8个苹果面试过程中求职者可能遇到的问题，以及已经被各路聪明的求职者破解的答案。

问题一：

“你面前有两扇门，其中一扇门内藏着宝藏，但如果你不小心闯入另一扇门，只能痛苦地慢慢死掉……”

这一听就是那种经典的最令人头痛的一类问题，但其实与其他问题相比，这只是个热身。在这两扇门后面，有两个人，这两个人都知道哪扇门后有宝藏，哪扇门擅闯者死，而这两个人呢，一个人只说真话，一个人只说假话。

谁说真话谁说假话？那就要看你有没有智慧自己找出来了，游戏规则是，你只能问这两个人每人一个问题。

那么，你问什么问题？问哪个人？根据他们的回答，你又该怎么做？

求职者的最佳答案：

随便问其中一个人：“如果我问另一个人，他会跟我说哪扇门后是宝藏？

如果你问的恰好是讲真话的那个人，那他指给你的答案就是那扇通向死亡的门，因为他会诚实地告诉你那个说谎的人会怎么说。

如果你问的是那个只说谎话的，你得到的也是错误的答案，因为另一个人是讲真话的，说谎话的人会告诉你与讲真话的人相反的答案。

所以你只要随便问一个人上述问题，然后选择与他们说的相反的门就行了。

问题二：

“你前面站了5个人，他们中间只有一个人讲真话……”

这个问题比上个问题难就难在，你只知道他们五个中有一个只讲真话，但其余四个，他们有时候讲真话，有时候讲假话，只有一点可以确定，这四个人将真话和假话有个规律：如果这次讲了真话，下次就会讲假话，如果这次讲假话，下次就讲真话。你的任务是，把五个人中那个只讲真话的人找出来。

你可以问两个问题，两个问题可以向同一个人发问，也可以分别问两个人。

你该问什么问题？

小提示：你可以这样安排两个问题承担的任务：首先你可以先问一个问题，不管得到的答案是什么，你都能从中知道下一个问题你将得到的答案是真是假。

求职者的最佳答案：

随便找一个人，首先问：“你是那个只讲真话的吗？”如果答案是肯定的，你再问这个人：“谁是只讲真话的？”；如果第一个问题你得到的答案是否定的，你就再问对方“谁不是只讲真话的？”

正如这个问题给出的提示，第一个问题的价值在于，如果你得到的答案是“我是”，那么你问的人要么是那个只讲真话的，要么是那个这一轮讲假话的“半真话半假话”者，不管是谁，他下一轮一定会说真话。所以你可以继续问这个人：“谁是只讲真话的？”对方的答案就是正确答案。

如果对第一个问题你得到的答案是“我不是”，那么回答者不可能是只讲真话的那个人，只能是一个此轮讲真话的“半真话半假话”者。此人下一轮将会说假话，所以你应该问他：“谁不是只讲真话的？”同样他告诉你的，只能是那个只讲真话的。

问题三：

“外星人打算将地球用来种蘑菇，并且已经抓了十个人类……”

外星人用这十个人代表地球60亿人口，将通过外星人的方式来测试这十个人，决定地球是不是有资格加入跨星际委员会，如果没有，就把地球变成一个蘑菇农场。

明天，这十个人将被关在一间漆黑的屋子里前后排成一队，外星人将给每个人戴一顶帽子，帽子为紫色或者绿色，然后外星人会将灯打开，这十个人每个人都无法看见自己头上的帽子是什么颜色，但可以看见排在你前面的每个人头上帽子的颜色。

帽子的颜色是随机的，可能全是紫的，也可能全是绿的，或者是任意的组合。

外星人会从后往前问每一个人:“你头上的帽子是什么颜色？”如果这个人答对了，这个人就安然无事，他所代表的地球上6亿人口也将获救。否则，这个人将被爆头，外星人将把他所代表的6亿人口变成蘑菇的肥料。每个人的答案屋子里所有人都可以听到。

现在，人类的命运在你手上，你可以设计一个方案，使这十个人提前制定一个计划，这个计划必须拯救尽可能多的人。

提示：有个方案可以让你拯救其中至少九个人。

求职者的最佳答案：

第十个人计算排在前面的所有人的绿帽子是奇数还是偶数并向前面的人发出一个信号，这样排在前面人就可以再通过排在更前面的所有人的绿帽子的奇偶数是否变化来判断自己帽子的颜色，因为如果绿帽子奇偶发生变化，那自己就是那个导致变化的“绿帽子”，如果没变化，自己就是“紫帽子”。

因为所有的人除了回答外星人的问题不能说话，所以第十个人的“信号”只能包含在自己的答案里，比如如果排在前面的九个人有奇数顶绿帽子，这个人类就告诉外星人自己的帽子是“绿色”，如果是偶数，就猜自己的帽子是“紫色”。这样等于给他前面的人一个暗号，排在他前面的这个人，可以通过计算自己前面的所有人的绿帽子的奇偶变化来判断自己的帽子是绿还是紫。

排在最后的那个人为了大众利益没有选择，根据前面的人的帽子情况告诉外星人自己是“绿帽子”还是“紫帽子”，他的答案有1/2的几率正确，但他前面的人一定都能答对。

还没懂？比如第十个人看到前面有奇数个绿帽子，他就告诉外星人自己的是绿色，这是他前面的人就知道他的意思是前面九个人中有奇数个绿帽子，这是第九个人再数前面八个人的，如果前面八个人中也有奇数个，那自己就是紫色帽子。第九个人告诉外星人自己是紫色帽子，第八个人就知道绿帽子没有减少还是奇数个，再数数前面七个人绿帽子数的奇偶，就可以判断自己帽子的颜色；反之，如果第九个人告诉外星人自己是绿色帽子，那第八个人就应该知道绿色帽子减少了一个由奇数变成了偶数，再看看前面所有的绿帽子情况作出判断。这样一个接一个，只要每个人都认真听后面的人的答案并在心里计算所剩绿帽子的奇偶变化，前面九个人都能获救。

当然，你也可以计算紫色帽子的奇偶。

问题四：

“100个完美的逻辑学家坐在一个房间里……”

这是一个电视真人秀节目，节目里100个拥有完美无瑕逻辑思维能力的人围成一圈坐在一个房间里。在进入房间前，这100个人被告知，100个人中至少有一个人的额头是蓝色的。你可以看见别人额头的颜色，但无法看到自己的，你需要对自己额头是不是蓝色进行猜测，在房间的灯被关掉时，如果你推测出你的额头是蓝色的，你需要站起来离开房间。

然后房间的灯被再次打开，那些认为自己额头是蓝色的人已经不在屋内。接下来灯会再次被关掉，剩下的人中推测自己额头是蓝色的离开房间，如此重复。

问题来了，假设这100个人的额头都是蓝色的，将会发生什么情况？注意，这100个人都有完美无瑕的逻辑推理能力，他们会根据其他人的额头颜色对自己进行合理的推理和猜测。

提示：想想看，如果100个人不全是蓝色额头，又会发生什么情况？

求职者的最佳答案：

将会出现的情况是：灯关了又开，开了又关，重复到第一百次时，所有人都同时离开。

这是为什么呢？想想看，每个人都看见其他99个人额头是蓝色的，灯关掉后再打开，发现这99个蓝色额头的同伴都没有离开，然后灯再次关掉后打开，如此重复100遍后，所有人同时离开了房间。

这么理解吧，假设只有一个人的额头是蓝色的，由于这100个人事先被告知至少有一个人额头是蓝色，所以这个人如果看到其他99个人额头都不是蓝色，立马就知道自己是蓝色，所以灯一关掉，这个人就会离开房间。

如果有两个人额头是蓝色呢？

其中一个蓝色额头的人会想：我的额头可能是蓝色也可能不是蓝色，现在其他99个人中有一个蓝色额头的人，如果我不是蓝色，那么就只有这一个人是，那么他看到我们都不是蓝色额头就能推断出他是，那么灯一关他就会离开，我先等一下，灯再打开如果他已经走了，那就证明我的额头不是蓝色的。

反之，如果我的额头是蓝色的，那个蓝色额头的人的想法会和我刚才的想法一样先等一等，第一次关灯他不会离开，这样如果灯开了那个蓝色额头的人还在，就证明我的额头也是蓝色的。这样第二次关灯我们俩会一起离开。

以此类推，如果有三个人额头是蓝色，你看到另外两个人额头是蓝色，应该推算出如果自己的额头不是蓝色的话，那么灯第二次关的时候他们俩会同时离开，如果他们俩没有同时离开，那就证明我的额头是蓝色的，我应该在第三次关灯的时候离开。结果是，三个蓝色额头的人在第三次关灯的时候同时离开。

把上述逻辑重复一百遍，你就得到了最上面的正确答案。

问题五：

“你有一个横6竖6的方格……”

你现在在左上第一个格子里，你的任务是移动到最右下脚的格子里，你每次只能向右或者向下移动，不能斜向移动，也不能后退。

你能找出几种方法移动到最右下脚的格子？

求职者的最佳答案：

252种。

从对称的角度思考这个问题。

随便挑选一个格子，假设你从出发点有n种方法从到达与所选格子上边相邻的格子，m种方法到达与它左边相邻的格子。

想想看，从出发点到达一个格子的方法与到达它左边和上边的格子的方法有什么关系？说对了，由于你只能向右和向下移动，到达一个格子，不是从它左边来，就是从它上边来。所以你从出发点到达一个格子的方法等于到达它上边格子的方法好到达它左边格子的方法的和相同，也就是n+m.

这样，参照上图，你就可以算出从出发点到达每一个格子的方法了。

问题六：

“逻辑学家们围成一圈坐着，他们的额头上面画有数字……”

又来一个逻辑学家围成一圈的问题，这次是这样的，三个拥有完美逻辑推理能力的人围成一圈坐在一个房间里，每个人的额头上都画着一个大于0的数字，三个人的数字各不相同，每个人都看得见其他两个人的数字，看不见自己的。

这三个数字的情况是，其中一个数字是其他两个数字的和，已知的情况还有，其中一个逻辑学家的数字是20，一个是30。

游戏组织者从这三个逻辑学家后面走过，并问三个人各自额头上的数字是什么。但第一轮每个逻辑学家都回答他们无法推测自己的数字是什么。游戏组织者只好进行第二轮的发问，这是为什么？你能据此猜出三个逻辑学家的数字吗？

求职者的最佳答案：

结果由第三个逻辑学家的答案而定。他们三个的数字分别是20，30和50。

假设第二个和第三个逻辑学家额头上的数字是20和30，这时候如果第一个逻辑学家的数字是10，那么第二个逻辑学家看到其他两个人一个是10，一个是30，会想：“我要么是20，要么是40.”

第三个逻辑学家看到其他两个人一个是10，一个是20，会想：“我要么是30，要么是10，但我不会是10，因为每个数字都不一样，所以我应该是30.”

这样第三个逻辑学家就会猜出自己的数字是30了，但他没有，第一轮谁也没有准确推测出自己的数字，这说明我们的前提不正确，第一个逻辑学家的数字不是10，那么他只能是50。

问题七：

“你面前有一百个灯泡，排成一排……”

一百个灯泡排成一排，第一轮你把他们全都打开亮着，然后第二轮，你每隔一个灯泡关掉一个，这样所有排在偶数的灯泡都被关掉了。

然后第三轮，你每隔两个灯泡，将开着的灯泡关掉，关掉的灯泡打开（也就是说将所有排在3的倍数的灯泡的开关状态改变）。

以此类推，你将所有排在4的倍数的灯泡的开关状态改变，然后将排在5的倍数的灯泡开关状态改变……

第100轮的时候，还有几盏灯泡亮着？

提示：如果你是第n轮（n大于1小于100），排在n的倍数位置的灯泡的开关状态就发生转变。

反过来，比如第8个灯泡，当你在8的因子轮（即第1，2，4和8轮）的时候，它就会改变开关状态。所以对于第m个灯泡，如果m有奇数个因子，你的开关状态就发生奇数次变化。

求职者的最佳答案：

10盏灯泡亮着，这10盏灯泡排位数都是平方数。

根据提示已经可以看出，这个问题的实质就是找出有多少个灯泡的排位数拥有奇数个因子。每拥有一个因子，到这个因子数的那一轮时，这个灯泡就会被转换开关状态。

比如第1轮，因为所有100个数字都有因数1，所以全部被打开；第2轮，只有那些拥有2这个因子、能被2整除的数字的灯泡转换状态被关掉；第3轮，只有那些拥有3这个因子、能被3整除的数字的灯泡被转换状态。以此类推，如果灯泡排位数拥有奇数个因子，意味着它被打开和关上奇数次，那它就最终还是被打开的状态，如果灯泡排位数拥有偶数个因子，那它最终就是被关上的状态。

比如第1个灯泡有奇数个因子，第2个有偶数个（1，2），第3个有偶数个（1，3）第4个有奇数个（1，2，4），所以 第4个灯泡最后还是亮着的。

最终计算得出，所有排位数为平方数的灯泡最终还是亮着的，因为这些数都拥有奇数个因子，1，4，9，16……

在100以内，共有10个平方数，分别是1，4，9，16，25，36，49，64，81，100。这10个排位数的灯泡，最终都还是亮着。

问题八：

“你有一个立方体，立方体的边长是3……”

这个问题比前面那个从左上格子走到右下格子的问题难，因为那毕竟是个平面问题。如图所示，这次的任务是从立方体的背面左上的小立方体走到完全相对的正面右下小立方体。

你可以往上移，也可以往下移，还可以往前移。You can move toward the front, you can move down, or you can move upward.

问题还是，你共有几种走法？

求职者的最佳答案：

90种，思路是将这个立方体分成“三层”。

上面平面图的那道题的思路就是个最好的提示。你可以将这个立方体分成“三层”，粉红色代表最上面那层，紫色代表中间那层，橘红色代表下面那层。

现在，我们把问题变成了：从左边、右边和上边到达目标小立方体的走法共有多少（如图所示，即到达紫色中间层最右下脚方块以及橘红色最右下脚左边以及上边相邻方块的方法）？假设从起点小立方体到达终点小立方体左边相邻小立方体共有m种方法，到达右边相邻小立方体共有n种方法，到达上边相邻小立方体有r种方法，那我们需要求出来的，就是n+m+r.

按照前面那道平面题的思路和方法，你就可以一点一点计算出来我们的正确答案。

from:
http://tech.qq.com/a/20120618/000071.htm?pgv_ref=aio2012&ptlang=2052 

一、活锁 
如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，

当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又

请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求，...，T2有可

能永远等待，这就是活锁的情形,避免活锁的简单方法是采用先来先服务的策略。

二、死锁 
如果事务T1封锁了数据R1，T2封锁了数据R2，然后T1又请求封锁R2，因T2已

封锁了R2，于是T1等待T2释放R2上的锁。接着T2又申请封锁R1，因T1已封锁了R1，

T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2，而T2又在等待T1的局面，

T1和T2两个事务永远不能结束，形成死锁。 
1. 死锁的预防
在数据库中，产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都

请求对已为其他事务封锁的数据对象加锁，从而出现死等待。防止死锁的发生其实就

是要破坏产生死锁的条件。预防死锁通常有两种方法： 
① 一次封锁法  
一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。

一次封锁法虽然可以有效地防止死锁的发生，但也存在问题，一次就将以后要用到的全

部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度。
② 顺序封锁法 
顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。

顺序封锁法可以有效地防止死锁，但也同样存在问题。事务的封锁请求可以随着事务的

执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的

顺序去施加封锁。
 
可见，在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点，因此DBMS在

解决死锁的问题上普遍采用的是诊断并解除死锁的方法。

 2. 死锁的诊断与解除
 
① 超时法

 如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。超时法实现简单，但

其不足也很明显。一是有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会

误认为发生了死锁。二是时限若设置得太长，死锁发生后不能及时发现。
 
② 等待图法
 
事务等待图是一个有向图G=(T,U)。 T为结点的集合，每个结点表示正运行的事务；U为

边的集合，每条边表示事务等待的情况。若T1等待T2,则T1、T2之间划一条有向边，从T1

指向T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如

每隔1分钟）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。
 
DBMS的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法是选择

一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务得以继续

运行下去。当然，对撤消的事务所执行的数据修改操作必须加以恢复。

System I/O can be blocking, or non-blocking synchronous, or non-blocking asynchronous [1, 2]. Blocking I/O means that the calling system does not return control to the caller until the operation is finished. As a result, the caller is blocked and cannot perform other activities during that time. Most important, the caller thread cannot be reused for other request processing while waiting for the I/O to complete, and becomes a wasted resource during that time. For example, aread() operation on a socket in blocking mode will not return control if the socket buffer is empty until some data becomes available.

By contrast, a non-blocking synchronous call returns control to the caller immediately. The caller is not made to wait, and the invoked system immediately returns one of two responses: If the call was executed and the results are ready, then the caller is told of that. Alternatively, the invoked system can tell the caller that the system has no resources (no data in the socket) to perform the requested action. In that case, it is the responsibility of the caller may repeat the call until it succeeds. For example, a read() operation on a socket in non-blocking mode may return the number of read bytes or a special return code -1 with errno set to EWOULBLOCK/EAGAIN, meaning "not ready; try again later."

In a non-blocking asynchronous call, the calling function returns control to the caller immediately, reporting that the requested action was started. The calling system will execute the caller's request using additional system resources/threads and will notify the caller (by callback for example), when the result is ready for processing. For example, a Windows ReadFile() or POSIX aio_read() API returns immediately and initiates an internal system read operation. Of the three approaches, this non-blocking asynchronous approach offers the best scalability and performance.

This article investigates different non-blocking I/O multiplexing mechanisms and proposes a single multi-platform design pattern/solution. We hope that this article will help developers of high performance TCP based servers to choose optimal design solution. We also compare the performance of Java, C# and C++ implementations of proposed and existing solutions. We will exclude the blocking approach from further discussion and comparison at all, as it the least effective approach for scalability and performance.

Reactor and Proactor: two I/O multiplexing approaches

In general, I/O multiplexing mechanisms rely on an event demultiplexor [1, 3], an object that dispatches I/O events from a limited number of sources to the appropriate read/write event handlers. The developer registers interest in specific events and provides event handlers, or callbacks. The event demultiplexor delivers the requested events to the event handlers.

Two patterns that involve event demultiplexors are called Reactor and Proactor [1]. The Reactor patterns involve synchronous I/O, whereas the Proactor pattern involves asynchronous I/O. In Reactor, the event demultiplexor waits for events that indicate when a file descriptor or socket is ready for a read or write operation. The demultiplexor passes this event to the appropriate handler, which is responsible for performing the actual read or write.

In the Proactor pattern, by contrast, the handler—or the event demultiplexor on behalf of the handler—initiates asynchronous read and write operations. The I/O operation itself is performed by the operating system (OS). The parameters passed to the OS include the addresses of user-defined data buffers from which the OS gets data to write, or to which the OS puts data read. The event demultiplexor waits for events that indicate the completion of the I/O operation, and forwards those events to the appropriate handlers. For example, on Windows a handler could initiate async I/O (overlapped in Microsoft terminology) operations, and the event demultiplexor could wait for IOCompletion events [1]. The implementation of this classic asynchronous pattern is based on an asynchronous OS-level API, and we will call this implementation the "system-level" or "true" async, because the application fully relies on the OS to execute actual I/O.

An example will help you understand the difference between Reactor and Proactor. We will focus on the read operation here, as the write implementation is similar. Here's a read in Reactor:

• An event handler declares interest in I/O events that indicate readiness for read on a particular socket
• The event demultiplexor waits for events
• An event comes in and wakes-up the demultiplexor, and the demultiplexor calls the appropriate handler
• The event handler performs the actual read operation, handles the data read, declares renewed interest in I/O events, and returns control to the dispatcher

By comparison, here is a read operation in Proactor (true async):

• A handler initiates an asynchronous read operation (note: the OS must support asynchronous I/O). In this case, the handler does not care about I/O readiness events, but is instead registers interest in receiving completion events.
• The event demultiplexor waits until the operation is completed
• While the event demultiplexor waits, the OS executes the read operation in a parallel kernel thread, puts data into a user-defined buffer, and notifies the event demultiplexor that the read is complete
• The event demultiplexor calls the appropriate handler;
• The event handler handles the data from user defined buffer, starts a new asynchronous operation, and returns control to the event demultiplexor.

Current practice

The open-source C++ development framework ACE [1, 3] developed by Douglas Schmidt, et al., offers a wide range of platform-independent, low-level concurrency support classes (threading, mutexes, etc). On the top level it provides two separate groups of classes: implementations of the ACE Reactor and ACE Proactor. Although both of them are based on platform-independent primitives, these tools offer different interfaces.

The ACE Proactor gives much better performance and robustness on MS-Windows, as Windows provides a very efficient async API, based on operating-system-level support [4, 5].

Unfortunately, not all operating systems provide full robust async OS-level support. For instance, many Unix systems do not. Therefore, ACE Reactor is a preferable solution in UNIX (currently UNIX does not have robust async facilities for sockets). As a result, to achieve the best performance on each system, developers of networked applications need to maintain two separate code-bases: an ACE Proactor based solution on Windows and an ACE Reactor based solution for Unix-based systems.

As we mentioned, the true async Proactor pattern requires operating-system-level support. Due to the differing nature of event handler and operating-system interaction, it is difficult to create common, unified external interfaces for both Reactor and Proactor patterns. That, in turn, makes it hard to create a fully portable development framework and encapsulate the interface and OS- related differences.

Proposed solution

In this section, we will propose a solution to the challenge of designing a portable framework for the Proactor and Reactor I/O patterns. To demonstrate this solution, we will transform a Reactor demultiplexor I/O solution to an emulated async I/O by moving read/write operations from event handlers inside the demultiplexor (this is "emulated async" approach). The following example illustrates that conversion for a read operation:

• An event handler declares interest in I/O events (readiness for read) and provides the demultiplexor with information such as the address of a data buffer, or the number of bytes to read.
• Dispatcher waits for events (for example, on select());
• When an event arrives, it awakes up the dispatcher. The dispatcher performs a non- blocking read operation (it has all necessary information to perform this operation) and on completion calls the appropriate handler.
• The event handler handles data from the user-defined buffer, declares new interest, along with information about where to put the data buffer and the number bytes to read in I/O events. The event handler then returns control to the dispatcher.

As we can see, by adding functionality to the demultiplexor I/O pattern, we were able to convert the Reactor pattern to a Proactor pattern. In terms of the amount of work performed, this approach is exactly the same as the Reactor pattern. We simply shifted responsibilities between different actors. There is no performance degradation because the amount of work performed is still the same. The work was simply performed by different actors. The following lists of steps demonstrate that each approach performs an equal amount of work:

Standard/classic Reactor:

• Step 1) wait for event (Reactor job)
• Step 2) dispatch "Ready-to-Read" event to user handler ( Reactor job)
• Step 3) read data (user handler job)
• Step 4) process data ( user handler job)

Proposed emulated Proactor:

• Step 1) wait for event (Proactor job)
• Step 2) read data (now Proactor job)
• Step 3) dispatch "Read-Completed" event to user handler (Proactor job)
• Step 4) process data (user handler job)

With an operating system that does not provide an async I/O API, this approach allows us to hide the reactive nature of available socket APIs and to expose a fully proactive async interface. This allows us to create a fully portable platform-independent solution with a common external interface.

TProactor

The proposed solution (TProactor) was developed and implemented at Terabit P/L [6]. The solution has two alternative implementations, one in C++ and one in Java. The C++ version was built using ACE cross-platform low-level primitives and has a common unified async proactive interface on all platforms.

The main TProactor components are the Engine and WaitStrategy interfaces. Engine manages the async operations lifecycle. WaitStrategy manages concurrency strategies. WaitStrategy depends on Engine and the two always work in pairs. Interfaces between Engine and WaitStrategy are strongly defined.

Engines and waiting strategies are implemented as pluggable class-drivers (for the full list of all implemented Engines and corresponding WaitStrategies, see Appendix 1). TProactor is a highly configurable solution. It internally implements three engines (POSIX AIO, SUN AIO and Emulated AIO) and hides six different waiting strategies, based on an asynchronous kernel API (for POSIX- this is not efficient right now due to internal POSIX AIO API problems) and synchronous Unix select(), poll(), /dev/poll (Solaris 5.8+), port_get (Solaris 5.10), RealTime (RT) signals (Linux 2.4+), epoll (Linux 2.6), k-queue (FreeBSD) APIs. TProactor conforms to the standard ACE Proactor implementation interface. That makes it possible to develop a single cross-platform solution (POSIX/MS-WINDOWS) with a common (ACE Proactor) interface.

With a set of mutually interchangeable "lego-style" Engines and WaitStrategies, a developer can choose the appropriate internal mechanism (engine and waiting strategy) at run time by setting appropriate configuration parameters. These settings may be specified according to specific requirements, such as the number of connections, scalability, and the targeted OS. If the operating system supports async API, a developer may use the true async approach, otherwise the user can opt for an emulated async solutions built on different sync waiting strategies. All of those strategies are hidden behind an emulated async façade.

For an HTTP server running on Sun Solaris, for example, the /dev/poll or port_get()-based engines is the most suitable choice, able to serve huge number of connections, but for another UNIX solution with a limited number of connections but high throughput requirements, aselect()-based engine may be a better approach. Such flexibility cannot be achieved with a standard ACE Reactor/Proactor, due to inherent algorithmic problems of different wait strategies (see Appendix 2).

In terms of performance, our tests show that emulating from reactive to proactive does not impose any overhead—it can be faster, but not slower. According to our test results, the TProactor gives on average of up to 10-35 % better performance (measured in terms of both throughput and response times) than the reactive model in the standard ACE Reactor implementation on various UNIX/Linux platforms. On Windows it gives the same performance as standard ACE Proactor.

Performance comparison (JAVA versus C++ versus C#).

In addition to C++, as we also implemented TProactor in Java. As for JDK version 1.4, Java provides only the sync-based approach that is logically similar to C select() [7, 8]. Java TProactor is based on Java's non-blocking facilities (java.nio packages) logically similar to C++ TProactor with waiting strategy based on select().

Figures 1 and 2 chart the transfer rate in bits/sec versus the number of connections. These charts represent comparison results for a simple echo-server built on standard ACE Reactor, using RedHat Linux 9.0, TProactor C++ and Java (IBM 1.4JVM) on Microsoft's Windows and RedHat Linux9.0, and a C# echo-server running on the Windows operating system. Performance of native AIO APIs is represented by "Async"-marked curves; by emulated AIO (TProactor)—AsyncE curves; and by TP_Reactor—Synch curves. All implementations were bombarded by the same client application—a continuous stream of arbitrary fixed sized messages via N connections.

The full set of tests was performed on the same hardware. Tests on different machines proved that relative results are consistent.

User code example

The following is the skeleton of a simple TProactor-based Java echo-server. In a nutshell, the developer only has to implement the two interfaces: OpRead with buffer where TProactor puts its read results, and OpWrite with a buffer from which TProactor takes data. The developer will also need to implement protocol-specific logic via providing callbacks onReadCompleted() and onWriteCompleted() in the AsynchHandler interface implementation. Those callbacks will be asynchronously called by TProactor on completion of read/write operations and executed on a thread pool space provided by TProactor (the developer doesn't need to write his own pool).

class EchoServerProtocol implements AsynchHandler
{
    AsynchChannel achannel = null;
    EchoServerProtocol(Demultiplexor m, SelectableChannel channel) throws Exception 
    {
        this.achannel = new AsynchChannel( m, this, channel );
    }

    public void start() throws Exception
    {
	// called after construction 
	System.out.println( Thread.currentThread().getName() + ": EchoServer protocol started" ); 
        achannel.read( buffer);
    }

    public void onReadCompleted( OpRead opRead ) throws Exception
    {
	if (opRead.getError() != null )
	{
   	// handle error, do clean-up if needed  
		System.out.println( "EchoServer::readCompleted: " + opRead.getError().toString());
		achannel.close();
		return;
	}
		
	if (opRead.getBytesCompleted () <= 0)
	{
		System.out.println( "EchoServer::readCompleted: Peer closed " + opRead.getBytesCompleted();
		achannel.close();
		return;
	}

	ByteBuffer buffer = opRead.getBuffer();
	achannel.write(buffer);
}
		
public void onWriteCompleted(OpWrite opWrite) throws Exception 
{
// logically similar to onReadCompleted         ...     
}
};

IOHandler is a TProactor base class. AsynchHandler and Multiplexor, among other things, internally execute the wait strategy chosen by the developer.

Conclusion

TProactor provides a common, flexible, and configurable solution for multi-platform high- performance communications development. All of the problems and complexities mentioned in Appendix 2, are hidden from the developer.

It is clear from the charts that C++ is still the preferable approach for high performance communication solutions, but Java on Linux comes quite close. However, the overall Java performance was weakened by poor results on Windows. One reason for that may be that the Java 1.4 nio package is based on select()-style API. � It is true, Java NIO package is kind of Reactor pattern based on select()-style API (see [7, 8]). Java NIO allows to write your own select()-style provider (equivalent of TProactor waiting strategies). Looking at Java NIO implementation for Windows (to do this enough to examine import symbols in jdk1.5.0\jre\bin\nio.dll), we can make a conclusion that Java NIO 1.4.2 and 1.5.0 for Windows is based on WSAEventSelect () API. That is better than select(), but slower than IOCompletionPort�s for significant number of connections. . Should the 1.5 version of Java's nio be based on IOCompletionPorts, then that should improve performance. If Java NIO would use IOCompletionPorts, than conversion of Proactor pattern to Reactor pattern should be made inside nio.dll. Although such conversion is more complicated than Reactor- >Proactor conversion, but it can be implemented in frames of Java NIO interfaces. (this the topic of next arcticle, but we can provide algorithm). At this time, no TProactor performance tests were done on JDK 1.5.

Note. All tests for Java are performed on "raw" buffers (java.nio.ByteBuffer) without data processing.

Taking into account the latest activities to develop robust AIO on Linux [9], we can conclude that Linux Kernel API (io_xxxx set of system calls) should be more scalable in comparison with POSIX standard, but still not portable. In this case, TProactor with new Engine/Wait Strategy pair, based on native LINUX AIO can be easily implemented to overcome portability issues and to cover Linux native AIO with standard ACE Proactor interface.

Appendix I

Engines and waiting strategies implemented in TProactor

Appendix II

All sync waiting strategies can be divided into two groups:

• edge-triggered (e.g. Linux RT signals)—signal readiness only when socket became ready (changes state);
• level-triggered (e.g. select(), poll(), /dev/poll)—readiness at any time.

Let us describe some common logical problems for those groups:

• edge-triggered group: after executing I/O operation, the demultiplexing loop can lose the state of socket readiness. Example: the "read" handler did not read whole chunk of data, so the socket remains still ready for read. But the demultiplexor loop will not receive next notification.
• level-triggered group: when demultiplexor loop detects readiness, it starts the write/read user defined handler. But before the start, it should remove socket descriptior from the set of monitored descriptors. Otherwise, the same event can be dispatched twice.
• Obviously, solving these problems adds extra complexities to development. All these problems were resolved internally within TProactor and the developer should not worry about those details, while in the synch approach one needs to apply extra effort to resolve them.

[1] Douglas C. Schmidt, Stephen D. Huston "C++ Network Programming." 2002, Addison-Wesley ISBN 0-201-60464-7

[2] W. Richard Stevens "UNIX Network Programming" vol. 1 and 2, 1999, Prentice Hill, ISBN 0-13- 490012-X 

[3] Douglas C. Schmidt, Michael Stal, Hans Rohnert, Frank Buschmann "Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, Volume 2" Wiley & Sons, NY 2000

[4] INFO: Socket Overlapped I/O Versus Blocking/Non-blocking Mode. Q181611. Microsoft Knowledge Base Articles.

[5] Microsoft MSDN. I/O Completion Ports.
http://msdn.microsoft.com/library/default.asp?url=/library/en- us/fileio/fs/i_o_completion_ports.asp

[6] TProactor (ACE compatible Proactor).
www.terabit.com.au

[7] JavaDoc java.nio.channels
http://java.sun.com/j2se/1.4.2/docs/api/java/nio/channels/package-summary.html

[8] JavaDoc Java.nio.channels.spi Class SelectorProvider 
http://java.sun.com/j2se/1.4.2/docs/api/java/nio/channels/spi/SelectorProvider.html

[9] Linux AIO development 
http://lse.sourceforge.net/io/aio.html, and
http://archive.linuxsymposium.org/ols2003/Proceedings/All-Reprints/Reprint-Pulavarty-OLS2003.pdf

See Also:

Ian Barile "I/O Multiplexing & Scalable Socket Servers", 2004 February, DDJ 

Further reading on event handling
- http://www.cs.wustl.edu/~schmidt/ACE-papers.html

The Adaptive Communication Environment
http://www.cs.wustl.edu/~schmidt/ACE.html

Terabit Solutions
http://terabit.com.au/solutions.php

About the authors

Alex Libman has been programming for 15 years. During the past 5 years his main area of interest is pattern-oriented multiplatform networked programming using C++ and Java. He is big fan and contributor of ACE.

Vlad Gilbourd works as a computer consultant, but wishes to spend more time listening jazz :) As a hobby, he started and runswww.corporatenews.com.au website.

http://goog-perftools.sourceforge.net/doc/tcmalloc.html

TCMalloc : Thread-Caching Malloc

Motivation

TCMalloc also reduces lock contention for multi-threaded programs. For small objects, there is virtually zero contention. For large objects, TCMalloc tries to use fine grained and efficient spinlocks. ptmalloc2 also reduces lock contention by using per-thread arenas but there is a big problem with ptmalloc2's use of per-thread arenas. In ptmalloc2 memory can never move from one arena to another. This can lead to huge amounts of wasted space. For example, in one Google application, the first phase would allocate approximately 300MB of memory for its data structures. When the first phase finished, a second phase would be started in the same address space. If this second phase was assigned a different arena than the one used by the first phase, this phase would not reuse any of the memory left after the first phase and would add another 300MB to the address space. Similar memory blowup problems were also noticed in other applications.

Another benefit of TCMalloc is space-efficient representation of small objects. For example, N 8-byte objects can be allocated while using space approximately 8N * 1.01 bytes. I.e., a one-percent space overhead. ptmalloc2 uses a four-byte header for each object and (I think) rounds up the size to a multiple of 8 bytes and ends up using 16N bytes.

Usage

To use TCmalloc, just link tcmalloc into your application via the "-ltcmalloc" linker flag.

You can use tcmalloc in applications you didn't compile yourself, by using LD_PRELOAD:

   $ LD_PRELOAD="/usr/lib/libtcmalloc.so" 

LD_PRELOAD is tricky, and we don't necessarily recommend this mode of usage.

TCMalloc includes a heap checker and heap profiler as well.

If you'd rather link in a version of TCMalloc that does not include the heap profiler and checker (perhaps to reduce binary size for a static binary), you can link in libtcmalloc_minimal instead.

Overview

TCMalloc treates objects with size <= 32K ("small" objects) differently from larger objects. Large objects are allocated directly from the central heap using a page-level allocator (a page is a 4K aligned region of memory). I.e., a large object is always page-aligned and occupies an integral number of pages.

A run of pages can be carved up into a sequence of small objects, each equally sized. For example a run of one page (4K) can be carved up into 32 objects of size 128 bytes each.

Small Object Allocation

A thread cache contains a singly linked list of free objects per size-class.

If the free list is empty: (1) We fetch a bunch of objects from a central free list for this size-class (the central free list is shared by all threads). (2) Place them in the thread-local free list. (3) Return one of the newly fetched objects to the applications.

If the central free list is also empty: (1) We allocate a run of pages from the central page allocator. (2) Split the run into a set of objects of this size-class. (3) Place the new objects on the central free list. (4) As before, move some of these objects to the thread-local free list.

Large Object Allocation

An allocation for k pages is satisfied by looking in the kth free list. If that free list is empty, we look in the next free list, and so forth. Eventually, we look in the last free list if necessary. If that fails, we fetch memory from the system (using sbrk, mmap, or by mapping in portions of /dev/mem).

If an allocation for k pages is satisfied by a run of pages of length > k, the remainder of the run is re-inserted back into the appropriate free list in the page heap.

Spans

A central array indexed by page number can be used to find the span to which a page belongs. For example, span a below occupies 2 pages, span b occupies 1 page, span c occupies 5 pages and span d occupies 3 pages.

Deallocation

If the object is large, the span tells us the range of pages covered by the object. Suppose this range is [p,q]. We also lookup the spans for pages p-1 andq+1. If either of these neighboring spans are free, we coalesce them with the [p,q] span. The resulting span is inserted into the appropriate free list in the page heap.

Central Free Lists for Small Objects

An object is allocated from a central free list by removing the first entry from the linked list of some span. (If all spans have empty linked lists, a suitably sized span is first allocated from the central page heap.)

An object is returned to a central free list by adding it to the linked list of its containing span. If the linked list length now equals the total number of small objects in the span, this span is now completely free and is returned to the page heap.

Garbage Collection of Thread Caches

We walk over all free lists in the cache and move some number of objects from the free list to the corresponding central list.

The number of objects to be moved from a free list is determined using a per-list low-water-mark L. L records the minimum length of the list since the last garbage collection. Note that we could have shortened the list by L objects at the last garbage collection without requiring any extra accesses to the central list. We use this past history as a predictor of future accesses and move L/2 objects from the thread cache free list to the corresponding central free list. This algorithm has the nice property that if a thread stops using a particular size, all objects of that size will quickly move from the thread cache to the central free list where they can be used by other threads.

Performance Notes

PTMalloc2 unittest

t-test1 (included in google-perftools/tests/tcmalloc, and compiled as ptmalloc_unittest1) was run with a varying numbers of threads (1-20) and maximum allocation sizes (64 bytes - 32Kbytes). These tests were run on a 2.4GHz dual Xeon system with hyper-threading enabled, using Linux glibc-2.3.2 from RedHat 9, with one million operations per thread in each test. In each case, the test was run once normally, and once with LD_PRELOAD=libtcmalloc.so.

The graphs below show the performance of TCMalloc vs PTMalloc2 for several different metrics. Firstly, total operations (millions) per elapsed second vs max allocation size, for varying numbers of threads. The raw data used to generate these graphs (the output of the "time" utility) is available in t-test1.times.txt.

• TCMalloc is much more consistently scalable than PTMalloc2 - for all thread counts >1 it achieves ~7-9 million ops/sec for small allocations, falling to ~2 million ops/sec for larger allocations. The single-thread case is an obvious outlier, since it is only able to keep a single processor busy and hence can achieve fewer ops/sec. PTMalloc2 has a much higher variance on operations/sec - peaking somewhere around 4 million ops/sec for small allocations and falling to <1 million ops/sec for larger allocations.
• TCMalloc is faster than PTMalloc2 in the vast majority of cases, and particularly for small allocations. Contention between threads is less of a problem in TCMalloc.
• TCMalloc's performance drops off as the allocation size increases. This is because the per-thread cache is garbage-collected when it hits a threshold (defaulting to 2MB). With larger allocation sizes, fewer objects can be stored in the cache before it is garbage-collected.
• There is a noticeably drop in the TCMalloc performance at ~32K maximum allocation size; at larger sizes performance drops less quickly. This is due to the 32K maximum size of objects in the per-thread caches; for objects larger than this tcmalloc allocates from the central page heap.

Next, operations (millions) per second of CPU time vs number of threads, for max allocation size 64 bytes - 128 Kbytes.

Here we see again that TCMalloc is both more consistent and more efficient than PTMalloc2. For max allocation sizes <32K, TCMalloc typically achieves ~2-2.5 million ops per second of CPU time with a large number of threads, whereas PTMalloc achieves generally 0.5-1 million ops per second of CPU time, with a lot of cases achieving much less than this figure. Above 32K max allocation size, TCMalloc drops to 1-1.5 million ops per second of CPU time, and PTMalloc drops almost to zero for large numbers of threads (i.e. with PTMalloc, lots of CPU time is being burned spinning waiting for locks in the heavily multi-threaded case).

Caveats

For some systems, TCMalloc may not work correctly on with applications that aren't linked against libpthread.so (or the equivalent on your OS). It should work on Linux using glibc 2.3, but other OS/libc combinations have not been tested.

TCMalloc may be somewhat more memory hungry than other mallocs, though it tends not to have the huge blowups that can happen with other mallocs. In particular, at startup TCMalloc allocates approximately 6 MB of memory. It would be easy to roll a specialized version that trades a little bit of speed for more space efficiency.

TCMalloc currently does not return any memory to the system.

Don't try to load TCMalloc into a running binary (e.g., using JNI in Java programs). The binary will have allocated some objects using the system malloc, and may try to pass them to TCMalloc for deallocation. TCMalloc will not be able to handle such objects.

http://health.msn.com.cn/healthcare/20110603/05001247621.shtml

http://health.msn.com.cn 2011-06-03 05:00:00 来源: 环球网健康频道

from:
http://blog.chinaunix.net/space.php?uid=233938&do=blog&cuid=211941

The DMA is another two chips on your motherboard (usually is an Intel 8237A-5 chips) that allow you (the programmer) to offload data transfers between I/O boards. DMA actually stands for 'Direct Memory Access'.

DMA can work: memory->I/O, I/O->memory. The memory->memory transfer doesn't work. It doesn't matter because ISA DMA is slow as hell and thus is unusable. Futhermore, using DMA for zeroing out memory would massacre the contents of memory caches.

What about caches and DMA? L1 and L2 caches work absolutely transparently. When DMA writes to memory, caches autmatically load or least invalidate the data that go into the memory. When DMA reads memory, caches supply the unwritten bytes so not old but new values are tranferred to the peripheral.

There are signals DACK, DRQ, and TC. When a peripheral wants to move a byte or 2 bytes into memory (is dependent on whether 8 bit or 16 bit DMA channel is in use -- 0,1,2,3 are 8-bit, 5,6,7 are 16-bit), it issues DRQ. DMA controller chats with CPU and after some time DMA controller issues DACK. Seeing DACK, the peripheral puts it's byte on data bus, DMA controller takes it and puts it in memory. If it was the last byte/word to move, DMA controller sets up also TC during the DACK. When peripheral sees TC, it is possible it will not want any more movements,

In the other direction, everything is the same, but first the byte/word is fetched from the memory and then DACK is generated and the peripheral takes the data.

DMA controller has only 8-bit address counter inside. There is external ALS573 counter for each chip so it makes programmer see it as DMA controller had 16 bits of address counter per channel inside. There are more 8 bits of address per channel of so called page register in LS612 that unfortunately do not increment as those in ALS573. All these 24 bits can address 16777216 of distict addresses.

Recapitulation: for each channel, independently, you see 16 bits of auto-incrementing counter, and 8 bits of page register which doesn't increment.

The difference between 16-bit DMA channels and 8-bit DMA channels is that the address bits for 16-bit channels are wired one bit left to the address bus so every address is 2 times bigger. The lowest bit is 0. The highest bit of page register would fit into bit 24 which is not on ISA so that it is left unconnected. The bus control logic is wired for 16-bit channels in a manner every single DMA transfer, a 16-bit cycle is generated, so ISA device puts 16 bits onto the bus at the time. I don't know what happens if you use 16-bit DMA channel with XT peripheral. I guess it could work but only be slower.

8-bit DMA: increments by 1, cycles inside 65536 bytes, addresses 16MB, moves 8 bits a time.

16-bit DMA: increments by 2, goes only over even addresses, cycles inside 131072 bytes, addresses 16MB, moves 16 bits a time. Uses 16-bit ISA I/O cycle so it takes less ticks to make one move that the 8-bit DMA.

An example of DMA usage would be the Sound Blaster's ability to play samples in the background. The CPU sets up the sound card and the DMA. When the DMA is told to 'go', it simply shovels the data from RAM to the card. Since this is done off-CPU, the CPU can do other things while the data is being transferred.

Enough basics. Here's how you program the DMA chip.

When you want to start a DMA transfer, you need to know several things:

• Number of DMA channel you want to use
• What page to use
• The offset in the page
• The length
• How to tell you peripheral to ask for DMA

• You cannot transfer more than 64K or 128K of data in one shot, and
• You cannot cross a page boundary. If you cross it, the lower 16 or 17 bits of address will simply wrap and you only suddenly jump 65536 or 131072 bytes lower that where you expected. It will be absolutely OK and no screw up will be performed. If you will take it in account in your program you can use it.

Restriction #1 is rather easy to get around. Simply transfer the first block, and when the transfer is done, send the next block.

For those of you not familiar with pages, I'll try to explain.

Picture the first 16MB region of memory in your system. It is divided into 256 pages of 64K or 128 pages of 128K. Every page starts at a multiple of 65536 or 131072. They are numbered from 0 to 255 or from 0 to 127.

In plain English, the page is the highest 8 bits or 7 bits of the absolute 24 bit address of our memory location. The offset is the lower 16 or 17 bits of the absolute 24 bit address.

Now that we know where our data is, we need to find the length.

The DMA has a little quirk on length. The true length sent to the DMA is actually length + 1. So if you send a zero length to the DMA, it actually transfers one byte or word, whereas if you send 0xFFFF, it transfers 64K or 128K. I guess they made it this way because it would be pretty senseless to program the DMA to do nothing (a length of zero), and in doing it this way, it allowed a full 64K or 128K span of data to be transferred.

Now that you know what to send to the DMA, how do you actually start it? This enters us into the different DMA channels.

The following chart will describe each channel and it's corresponding port number:

DMA 4. Doesn't exist. DMA 4 is used to cascade the two 8237A chips. When first 8237A wants to DMA, it issues "HRQ" to second chip's DRQ 4. The second chip thinks DMA 4 is wanna be made so issues DRQ 4 to the first chip's HLDA. First chip makes it's own DMA 0-3, then sends to the second "OK second chip, my DMA 4 is complete" and second chip knows it's free on the bus. If this mechanism would not work, the two chips could peck each other on the BUS and the PC would screw up. :+)

from: ibm developerworks