庄周梦蝶

新爸爸指南

1、孩子刚出生一两个月内是睡觉的时间多，清醒的时间少，这是很正常的现象，不用担心。小毅一开始也是这样狂睡，我和他妈妈还有点担心，后来通过查看一些资料才知道这是正常现象。睡的多，长的快。现在7个月了，睡的少了，越来越会闹腾。
2、孩子出生后24小后出现新生儿黄疸，这也是正常现象，也就是脸色比较发黄，医生会做检测，含量在合理范围内就没有问题，两三天内就会推下去，如果超出正常范围，需要住院治疗。小毅那时候检测出来的含量偏高，本来担心还要住院，后来还是退下去了。
3、孩子出生后，应该尽快让他尝试吃奶，母乳比奶粉好多了。
4、孩子在6个月内，腿脚看起来都是弯的，也就是看起来好像会罗圈腿，其实这也是在正常现象，只要注意不要让孩子过早的站立增加腿的负担之外，在6个月之后会慢慢转为正常。不过小毅太喜欢站了，还是有点担心了，准备观察观察，现在他都能自己借助外物从坐到站。孩子补钙还是需要的，推荐冲剂类的补钙产品，小毅用的是爱尔钙，比较酸，还能接受。补钙不是吃东西就完事儿，每天晒一些太阳还是必要的。
5、孩子感冒，不要太紧张，如果是没有超过38度的低烧，先用洗热水澡的方式来降温，洗完热水澡通常会降下来，如果再次上升，采取同样手段，注意保暖。但是也不是衣服穿的越多越好。如果温度高于38.5，强烈建议上医院找专业大夫。但是不要盲目给孩子开药，低烧完全可以通过物理降温，小毅到现在就发烧过一次，他妈妈和爷爷太着急，给他开了药，我知道后“愤怒”地批评了他妈妈，38度以下的低烧物理降温就可以了，让他们停了药，按照我说的去做，没什么问题。当然，不仅仅要靠物理降温，也要观察孩子的精神好不好，精神比较打蔫，跟平常不一样，那还是上医院保险。
6、注意给孩子体检，6个月至少去4次，看看体重和身高是否在正常范围内。小毅同学的体重和身高都还不错，妈妈功劳巨大。
7、孩子的防疫计划是要按照通知去打的，千万不能忘。
8、孩子咳嗽不能小瞧，可能是呼吸道感染或者轻微感冒，如果不是很厉害，可以考虑食疗。风寒喝姜汤，风热榨梨汁给他喝。
9、孩子从5个月开始要吃蛋黄了，这是因为母乳和奶粉提供的铁元素不够了，蛋黄从1/8到一个，逐步添加。在6，7个月的时候，可以考虑将鸡蛋做成鸡蛋羹给他吃。小毅吃饭很闹腾，吃个饭也要又蹦又跳，几个人围着他转，无语啊，小皇帝。
10、孩子从2，3个月开始，最好开始榨一些新鲜果汁给他喝，我儿子很喜欢喝苹果汁和西瓜汁。

11、我儿子6个多月就开始会爬了，这时候要特别小心了，不要让孩子一个人呆在床上，他爬下床就得摔一跤了。小毅就摔了一次，他妈妈洗衣服，将他一个人放床上，没想到他会爬，还爬到床下去了：） 听他妈妈说，脑袋红了一块，哭了几分钟就没事儿了。要注意，如果摔了，不会哭起来，赶紧送医院。

暂时想到这些。。。待补充。

posted @ 2009-08-10 22:24 dennis 阅读(756) | 评论 (2) | 编辑收藏

最近一直在观察一个很有趣的现象，在国米超级杯失利后，魔力鸟同学发表的刺激“愤愤”的言论之后各大媒体网站的有趣新闻，这些新闻只是进一步验证了中国足球妓者的不专业，同样也让某些90后球迷兴奋地难以言喻，为什么说他们90后？因为只有脑残到一定程度才会为了这么一场无关宏旨的比赛意淫成那样。看看性浪网站的意假专题，AC米兰是祖国江山一片好，而国米的新闻却是凄凄惨惨切切，实际呢，AC米兰今年能进前4就知足吧，国米今年联赛冠军照拿不误，当然宇宙无敌王朝队的超超超新星太多了，30岁以上的新星暂时都不要了。魔力鸟同学捅了马蜂窝，说了大实话，中国就没一个专业的足球妓者嘛，除了编造新闻（以《体坛》最牛）、写写花边新闻、跟米卢合影上床（仅限女妓者）之外就不会干点别的，可魔力鸟同学不干了，不仅不合影，还说了实话，还不让足球妓者们提不专业的问题，你还不让不让足球妓者们活呀，全国的足球妓者们统一起来，全国的足球妓者们万岁，打倒魔力鸟主义，打倒国际米兰！

posted @ 2009-08-10 20:58 dennis 阅读(419) | 评论 (0) | 编辑收藏

参加公司半年会的几点感受

周六参加了公司的半年会，这是我第一次参加年会，2000多号人将学校的礼堂做的满满，舞台也搞的相当华丽。华丽之外的几点感受：

1、做人，做事，在公司上班工作，都需要使命感和责任感，一家没有使命感的公司是注定做不长久的。对一份工作没有使命感和热情，也是注定做不长久的。

2、我们总是做着自以为帮助别人的同时深深地伤害别人。成人们在感动小女孩的遭遇的同时，也在不断扯裂她心里的伤疤。一个孩子懂事早熟，这不是什么幸事，而是悲哀。什么时候大人们能不那么粗暴地强加自己的视角给孩子们？

3、老马果然很能说。

4、参加义工活动还是很有意义的事情，尽管我觉的形式化了。

5、在两千人面前求婚，事实证明不是那么靠谱的事情。

posted @ 2009-07-27 09:34 dennis 阅读(840) | 评论 (0) | 编辑收藏

我为什么说豆瓣脑残

豆瓣是我经常上的网站，我在上面维护我的读书列表、电影列表和照片，平常有什么想说，偶尔也去那广播吹水，再加上一帮同好在那，因此逛豆瓣也成了我每天的习惯。当三表说豆瓣是脑残的时候，俺心里还提它辩解了下，要说他的推荐功能确实非常强大，而且能有这么一个维护读书计划的地方还是很不错的。
不过豆瓣最近的行为，让我越来越觉它脑残，理由如下：
一、删除照片和删除日志，从来就是一封冷冰冰的邮件通知，“你的XX图片因不符合豆瓣的图片策略已被删除”。我想去看看是哪张照片，但因为照片太多，却不知道是删的是哪张了。你丫就不会提供一个回收站啊，或者自动隐藏你认为有问题的照片，你丫删得干脆，用户就郁闷了，想知道原因的话，人家豆瓣就是公务猿，一问三不知。

二、动不动就他妈地搞什么“此功能暂停使用”，经常不允许使用广播，不允许写日志。我知道不是技术问题，我知道你们迫不得已，但是你们就不知道改变策略，搞个敏感词过滤或者隐藏五毛们要求删除的日志或者广播，而不是停掉功能。靠，你一个网站连正常的功能都提供不了，我上豆瓣干嘛？奸尸啊我。

三、广告用户越来越多，经常是一些注册没超过一个月，活动记录没超过两条的在书评或者影评蹦跶，将一本垃圾书（比如《敏捷无敌》）或者垃圾电影（比如《赤壁》）夸的跟天上的星星一样亮晶晶。更甚者是到处加好友，加完了就不断邀请你参加一些脑残的广告活动，烦不胜烦。这个现象的出现一方面说明豆瓣越来越受人关注的，另一方面就不能搞个防骚扰机制？并且对评价结果也应该能做出自动修正，对一些广告账户的评价应该做极低权重处理。为什么是极低？你没看到吗，在某部电影的上映档期内，一大群马甲可以把他评的跟《教父》一样，大大误导广大人民群众。

posted @ 2009-07-13 10:56 dennis 阅读(1334) | 评论 (4) | 编辑收藏

os的进程调度（读书笔记）

    在多进程、多线程并发的环境里，从概念上看，有多个进程或者多个线程在同时执行，具体到单个CPU级别，实际上任何时刻只能有一个进程或者线程处于执行状态；因此OS需要决定哪个进程执行，哪些进程等待，也就是进程的调度。
一、调度的目标
1、首先要区分程序使用CPU的三种模式：IO密集型、计算密集型和平衡型。对于IO密集型程序来说，响应时间非常重要；对于CPU密集型来说，CPU的周转时间就比较重要；对于平衡型程序来说，响应和周转之间的平衡是最重要的。
2、CPU的调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处于繁忙状态和提供某种公平的机制。
3、对于实时系统来说，调度的目标就是要达到截止时间前完成所应该完成的任务和提供性能的可预测性。

二、调度算法

1、FCFS（First come first serve)，或者称为FIFO算法，先来先处理。这个算法的优点是简单，实现容易，并且似乎公平；缺点在于短的任务有可能变的非常慢，因为其前面的任务占用很长时间，造成了平均响应时间非常慢。

2、时间片轮询算法，这是对FIFO算法的改进，目的是改善短程序（运行时间短）的响应时间，其方法就是周期性地进行进程切换。这个算法的关键点在于时间片的选择，时间片过大，那么轮转就越接近FIFO，如果太小，进程切换的开销大于执行程序的开销，从而降低了系统效率。因此选择合适的时间片就非常重要。选择时间片的两个需要考虑的因素：一次进程切换所使用的系统消耗以及我们能接受的整个系统消耗、系统运行的进程数。
    时间片轮询看上起非常公平，并且响应时间非常好，然而时间片轮转并不能保证系统的响应时间总是比FIFO短，这很大程度上取决于时间片大小的选择，以及这个大小与进程运行时间的相互关系。

3、STCF算法（Short time to complete first)，顾名思义就是短任务优先算法。这种算法的核心就是所有的程序都有一个优先级，短任务的优先级比长任务的高，而OS总是安排优先级高的进程运行。
    STCF又分为两类：非抢占式和抢占式。非抢占式STCF就是让已经在CPU上运行的程序执行到结束或者阻塞，然后在所有的就绪进程中选择执行时间最短的来执行；而抢占式STCF就不是这样，在每进来一个新的进程时，就对所有进程（包括正在CPU上执行的进程）进行检查，谁的执行时间短，就运行谁。

    STCF总是能提供最优的响应时间，然而它也有缺点，第一可能造成长任务的程序无法得到CPU时间而饥饿，因为OS总是优先执行短任务；其次，关键问题在于我们怎么知道程序的运行时间，怎么预测某个进程需要的执行时间？通常有两个办法：使用启发式方法估算（例如根据程序大小估算），或者将程序执行一遍后记录其所用的CPU时间，在以后的执行过程中就可以根据这个测量数据来进行STCF调度。

4、优先级调度，STCF遇到的问题是长任务的程序可能饥饿，那么优先级调度算法可以通过给长任务的进程更高的优先级来解决这个问题；优先级调度遇到的问题可能是短任务的进程饥饿，这个可以通过动态调整优先级来解决。实际上动态调整优先级（称为权值）+时间片轮询的策略正是linux的进程调度策略之一的 SCHED_OTHER分时调度策略,它的调度过程如下：

（1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。

（2）将根据每个任务的nice值确定在cpu上的执行时间(counter)。

（3）如果没有等待资源，则将该任务加入到就绪队列中。

（4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

（5）此时调度程序重复上面计算过程，转到第4步。

（6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

linux还有两个实时进程的调度策略：FIFO和RR,实时进程会立即抢占非实时进程。

5、显然，没有什么调度算法是毫无缺点的，因此现代OS通常都会采用混合调度算法。例如将不同的进程分为几个大类，每个大类有不同的优先级，不同大类的进程的调度取决于大类的优先级，同一个大类的进程采用时间片轮询来保证公平性。

6、其他调度算法，保证调度算法保证每个进程享用的CPU时间完全一样；彩票调度算法是一种概率调度算法，通过给进程“发彩票”的多少，来赋予不同进程不同的调用时间，彩票调度算法的优点是非常灵活，如果你给短任务发更多“彩票”，那么就类似STCF调度，如果给每个进程一样多的“彩票”，那么就类似保证调度；用户公平调度算法，是按照每个用户，而不是按照每个进程来进行公平分配CPU时间，这是为了防止贪婪用户启用了过多进程导致系统效率降低甚至停顿。

7、实时系统的调度算法，实时系统需要考虑每个具体任务的响应时间必须符合要求，在截止时间前完成。
（1）EDF调度算法，就是最早截止任务优先（Earliest deadline first)算法，也就是让最早截止的任务先做。当新的任务过来时，如果它的截止时间更靠前，那么就让新任务抢占正在执行的任务。EDF算法其实是贪心算法的一种体现。如果一组任务可以被调度（也就是所有任务的截止时间在理论上都可以得到满足），那么EDF可以满足。如果一批任务不能全部满足（全部在各自的截止时间前完成），那EDF满足的任务数最多，这就是它最优的体现。EDF其实就是抢占式的STCF，只不过将程序的执行时间换成了截止时间。EDF的缺点在于需要对每个任务的截止时间做计算并动态调整优先级，并且抢占任务也需要消耗系统资源。因此它的实际效果比理论效果差一点。

（2）RMS调度算法，EDF是动态调度算法，而RMS（rate monotonic scheduling)算法是一种静态最优算法；该算法在进行调度前先计算出所有任务的优先级，然后按照计算出来的优先级进行调度，任务执行中间既不接收新任务，也不进行优先级调整或者CPU抢占。因此它的优点是系统消耗小，缺点就是不灵活了。对于RMS算法，关键点在于判断一个任务组是否能被调度，这里有一个定律，如果一个系统的所有任务的CPU利用率都低于ln2，那么这些任务的截止时间均可以得到满足，ln2约等于0.693147，也就是此时系统还剩下有30%的CPU时间。这个证明是Liu和Kayland在1973年给出的。

三、优先级反转
1、什么是优先级反转？
    优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。

2、解决方案：
（1）设置优先级上限，给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。

（2）优先级继承，当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。
    这里还有一个八卦，1997年的美国的火星探测器（使用的就是vxworks)就遇到一个优先级反转问题引起的故障。简单说下，火星探测器有一个信息总线，有一个高优先级的总线任务负责总线数据的存取，访问总线都需要通过一个互斥锁（共享资源出现了）；还有一个低优先级的，运行不是很频繁的气象搜集任务，它需要对总线写数据，也就同样需要访问互斥锁；最后还有一个中优先级的通信任务，它的运行时间比较长。平常这个系统运行毫无问题，但是有一天，在气象任务获得互斥锁往总线写数据的时候，一个中断发生导致通信任务被调度就绪，通信任务抢占了低优先级的气象任务，而无巧不成书的是，此时高优先级的总线任务正在等待气象任务写完数据归还互斥锁，但是由于通信任务抢占了CPU并且运行时间比较长，导致气象任务得不到CPU时间也无法释放互斥锁，本来是高优先级的总线任务也无法执行，总线任务无法及时执行的后果被探路者认为是一个严重错误，最后就是整个系统被重启。Vxworks允许优先级继承，然而遗憾的工程师们将这个选项关闭了。

（3）第三种方法就是使用中断禁止，通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。火星探路者正是由于在临界区中运行的气象任务被中断发生的通信任务所抢占才导致故障，如果有临界区的禁止中断保护，此一问题也不会发生。

posted @ 2009-06-28 13:28 dennis 阅读(8693) | 评论 (1) | 编辑收藏

最近的工作(mina vs. yanf4j)

     最近工作上是在处理一个线程安全的问题，如何保证对某个资源的访问是独占的，不会有并发的隐患。在此过程中接了checkthread，一个线程安全的静态分析工具，通过annotation标记在编译期检查可能的并发隐患，提供了一个eclipse插件，有兴趣可以看看他的 example。这个东西有个最不好的地方就是要依赖他的自定义annotation，如果不介意的话还是不错的选择，一些常见的隐患都能够标示出来。
    另外就是去了解了下netty3，jboss的子项目，netty2和mina作者的另一个作品，关注它是因为在他的benchmark中，netty3的表现很优秀，可以看这篇报告《Performance comparision between java nio framework》。大概看了下他的设计思路，其实与mina并无多大区别，不过使用了一些有意思的trick，例如对于write的处理，一般的nio框架都是放入一个队列，然后注册写事件（队列为空的时候），等待写，写通常也是单线程去写。而netty3做了一个优化，发送消息时同样有一个队列，在放入队列后判断当前是否正在写循环中，如果正在写，那么就注册一个WriteTask唤醒selector等待写；如果没有，那么发送线程立即就去执行这个写操作，这里的一个好处是少了两个开销：注册事件等待触发以及线程切换。Selector.wakeup的操作是比较昂贵的，netty3也做了优化。更多东西等待探索。

   山寨nio框架yanf4j已经挺久没有做出任何改进，这次索性将很多过去考虑不成熟、实践中证明不必要的代码删除和简化，然后做了个与mina 2.0 -M5的性能对比，采用的netty3作者的benchmark源码，yanf4j的Echo Server如下：

Echo Server

最后的分析报表，可以看到yanf4j的性能与mina2的性能相近，不过mina在内存使用上非常狠。此外，Xmemcached 1.1.3 将采用最新的yanf4j 0.7.0。

(横坐标是并发连接数，纵坐标是吞吐量，单位为M/s，测试JDK为1.6.4，具体硬件环境不再详细列出，与xmemcached的benchmark同)

四张图分别是在消息长度为64、256、1024、4096字节下的对比。

posted @ 2009-06-26 21:46 dennis 阅读(5651) | 评论 (4) | 编辑收藏

xmemcached发布1.1.2 (权重、noreply、spring集成）

XMemcached发布1.1.2版本，这一版本仍然是1.1.0版本以来的改进版本，主要的改进如下：

1.支持设置memcached节点权重，权重高的负载相应比较大。

2.为部分协议添加noreply选项，memcached 1.2.5引入了noreply支持，部分文本协议（如存储，删除，incr/decr等）允许附加设置一个noreply，表示客户端不要求memcached应答。这一特性利于批量处理。

3.支持与spring框架的集成。

4.添加verbosity协议，这个协议用于让客户端设置memcached的日志输出级别。

5.一些细节改进。XMemcached从0.5开始就有重连机制，在连接意外断开的情况下会不断地自动重连，不过间隔是10秒，现在改成将间隔缩小为0秒以便客户端能及时连接。改进了JMX支持，可以通过JMX查看节点权重和动态设置节点权重。

6.BUG修复，包括：Issue 35、Issue 36、Issue 37、Issue 38等，具体请看这里

7.去除了对spy-2.4.jar依赖，现在序列化部分已经不再需要spymemcached的这个jar包。

项目主页：http://code.google.com/p/xmemcached/
下载地址：http://code.google.com/p/xmemcached/downloads/list
wiki地址：http://code.google.com/p/xmemcached/w/list

下面是关于特性的详细说明，首先是权重的使用，看例子：

MemcachedClientBuilder builder = new XMemcachedClientBuilder(AddrUtil.getAddresses("localhost:12000 localhost:12001"),new int[]{1,3});
MemcachedClient memcachedClient=builder.build();

现在的XMemcachedClientBuilder允许传入了两个参数，一个是InetSocketAddress组成的列表，一个是权重的数组，权重数组的元素与列表中的地址一一对应，例如这里就是将"localhost:12000"节点的权重设置为1，而将"localhost:12001"的权重设置为3。同样在XMemcachedClientMBean中添加了两个新的方法：

    public void addOneServerWithWeight(String server, int weight)
            throws IOException;

    /**
     * Set a memcached server's weight
     *
     * @param server
     * @param weight
     */
    public void setServerWeight(String server, int weight);

用于动态添加和修改节点的权重。

其次，为了支持noreply选项，MemcachedClient接口引入了系列xxxWithNoReply方法，例如

public abstract void setWithNoReply(final String key, final int exp,
            final Object value) throws InterruptedException, MemcachedException;

    public abstract <T> void setWithNoReply(final String key, final int exp,
            final T value, final Transcoder<T> transcoder)
            throws InterruptedException, MemcachedException;

public abstract void addWithNoReply(final String key, final int exp,
            final Object value) throws InterruptedException, MemcachedException;
public abstract void replaceWithNoReply(final String key, final int exp,
            final Object value) throws InterruptedException, MemcachedException;
public void deleteWithNoReply(final String key)
            throws InterruptedException, MemcachedException;

完整的列表请看changelog.txt, noreply系列方法非常适合于批量处理，比之需要等待memcached应答的效率上提升很多。

第三，与spring的集成，通过XMemcachedClientFactoryBean可以很方便地与spring框架集成，最简单的配置如下：

   <bean name="memcachedClient"
        class="net.rubyeye.xmemcached.utils.XMemcachedClientFactoryBean">
        <property name="servers">
            <value>localhost:12000 localhost:12001</value>
        </property>
    </bean>

   只要设置servers属性，那么就可以在任何需要的地方引用memcachedClient这个Bean.更完整的配置参考wiki

   第四，引入了对verbosity协议的支持，通过两个新方法：

    public void setLoggingLevelVerbosity(InetSocketAddress address, int level)
            throws TimeoutException, InterruptedException, MemcachedException;

    public void setLoggingLevelVerbosityWithNoReply(InetSocketAddress address,
            int level) throws InterruptedException, MemcachedException;

   其中的level就是日志级别。请注意你的memcached版本是否支持这一协议。

    1.1.2是一个承前启后的版本，按俺的计划应该还有个1.1.3（专注性能改进和优化），之后才是实现了二进制协议的1.2.0。俺非常希望能有任何人给出任何建议和bug反馈。

posted @ 2009-06-21 14:19 dennis 阅读(3221) | 评论 (8) | 编辑收藏

Xmemcached实现权重memcached节点（更新）

在JavaMemCached这个memacched客户端，如果你有多个memcachd节点，你可以设置memcached server的权重，权重高的节点在存储、获取等操作就相应占的比重比较大。恰巧我最近也在实现一个类似这样流控的东西，因此在xmemcached实现了此feature。这个功能暂定在1.2.0的时候发布，但是现在已经可以从svn获取，只是你需要自己build。

使用方法，与通常调用的唯一区别就是在创建MemcachedClient的时候,

MemcachedClientBuilder builder = new XMemcachedClientBuilder (AddrUtil.getAddresses("localhost:12000 localhost:12001"),new int[]{1,3});
MemcachedClient memcachedClient = builder.build();

XMemcachedClientBuilder新增一个重载构造函数，除了传入地址列表之外，还可以传入一个权重数组表示列表中的memcached节点权重，权重数组与地址列表一一对应。这里将localhost:12001的权重设为3，而localhost:12000的权重设置为1。如果没有提供权重值，默认都是为1。这个feature已经进行了测试，在随机化测试下完全符合比例要求。这一feature对于是使用标准哈希，还是一致性哈希都有效。

实现原理是添加weight次相同的session存储在session查找集合里，但是注意这里仍然是只有一个连接的，只是在集合里存储了这个连接的多份引用，那么在查找session的过程中，找到权重大（引用多）的连接的几率相应就比较大。

posted @ 2009-06-14 15:25 dennis 阅读(2020) | 评论 (0) | 编辑收藏

sicp 5.1节习题尝试解答

5.1 图就不画在机器上了，麻烦

5.2 用寄存器语言描述5.1题中的阶乘机器，加上了读取和打印,这里的解答全部在实际的寄存机器中验证过，但是仍然按照该节的表示法表示。

(controller
fac-loop
   (assign n (op read))
   (assign product (const 1))
   (assign counter (const 1))
iter-loop
   (test (op >) (reg counter) (reg n))
   (branch (label iter-done))
   (assign product (op *) (reg product) (reg counter))
   (assign counter (op +) (reg counter) (const 1))
   (goto (label iter-loop))
iter-done
   (perform (op print) (reg product))
   (goto (label fac-loop)))

5.3 牛顿法求平方根，将这个过程转化为寄存器语言，第一个版本，假设good-enough?和improve都是基本过程，

;version1
(controller
   sqrt-loop
    (test (op good-enough?) (reg guess))
    (branch (label sqrt-done))
    (assign guess (op improve) (reg guess))
    (goto (label good-enough))
   sqrt-done)

第二个版本，展开good-enough?过程，

;version2
(controller
   good-enough
    (assign t (op square) (reg guess))
    (assign t (op -) (reg t) (reg x))
    (assign t (op abs) (reg t))
    (test (op <) (reg t) (const 0.001))
    (branch (label sqrt-done))
    (assign guess (op improve) (reg guess))
    (goto (label good-enough))
   sqrt-done)

最后，展开improve过程，

;version3
(controller
sqrt-init
   (assign guess (const 1.0))
   (assign x (op read))
good-enough
    ;good-enough
   (assign t (op square) (reg guess))
   (assign t (op -) (reg t) (reg x))
   (assign t (op abs) (reg t))
   (test (op <) (reg t) (const 0.001))
   (branch (label sqrt-done))
    ;improve
   (assign t (op /) (reg x) (reg guess))
   (assign t (op +) (reg guess) (reg t))
   (assign guess (op /) (reg t) (const 2.0))
   (goto (label good-enough))
sqrt-done)

在start之后，从寄存器guess中得到最后结果。

5.4
a)第一个是一个指数计算过程，用到了递归，因此需要引入continue寄存器来保存和恢复堆栈，实现与阶乘相似，如下

(controller
    (assign continue (label expt-done))
    expt-loop
      (test (op =) (reg n) (const 0))
      (branch (label expt-base-case))
      ;;保存continue
      (save continue)
      (assign n (op -) (reg n) (const 1))
      (assign continue (label after-expt))
      (goto (label expt-loop))
    after-expt
      ;;恢复continue
      (restore continue)
      (assign val (op *) (reg b) (reg val))
      (goto (reg continue))
    expt-base-case
      (assign val (const 1))
      (goto (reg continue))
    expt-done
      (perform (op display) (reg val)))

b) 迭代型的递归计算过程，尾递归调用，因此不需要continue寄存器来保存和恢复堆栈，这道习题就是希望能分辨非尾递归和尾递归带来的寄存机器语言的区别

(controller
    (assign product (const 1))
    (assign n (op read))
    (assign b (op read))
    (assign counter (reg n))
   expt-iter-loop
     (test (op =) (reg counter) (const 0))
     (branch (label expt-done))
     (assign counter (op -) (reg counter) (const 1))
     (assign product (op *) (reg b) (reg product))
     (goto (label expt-iter-loop))
   expt-done
      (perform (op display) (reg product)))

5.5 手工模拟就算了，5.2节就可以机器模拟了

5.6 是有一个多余的save和一个多余的restore操作，请看注释：

(
   (assign continue (label fib-done))
  fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
   ;;compute fib(n-1)
   (save continue)
   (assign continue (label after-fib-1))
   (save n)
   (assign n (op -) (reg n) (const 1))
   (goto (label fib-loop))
  after-fib-1
   ;;compute fib(n-2)
   (restore n)
   ;这里多余，(restore continue)
   (assign n (op -) (reg n) (const 2))
   ;这里多余，(save continue)
   (assign continue (label after-fib-2))
   (save val) ;;save fib(n-1)
   (goto (label fib-loop))
  after-fib-2
   (assign n (reg val))
   (restore val)
   (restore continue)
   (assign val (op +) (reg val) (reg n))
   (goto (reg continue))
immediate-answer
   (assign val (reg n))
   (goto (reg continue))

fib-done)

posted @ 2009-06-11 00:47 dennis 阅读(1800) | 评论 (1) | 编辑收藏

Scala Ring Benchmark

Scala实现的ring benchmark：

import scala.actors.Actor
import scala.actors.Actor._
import java.util.concurrent.CountDownLatch
case class Message()
class Process(m:Int,p:Actor,latch:CountDownLatch) extends Actor{
  var next=p
  def act{
   loop{
     recvAndSend(m)
   }
  }
  def recvAndSend(count:Int){
     if(count==0){
        latch.countDown()
        exit
     }else{
       react{
         case Message()=>
           next! Message()
           recvAndSend(count-1)
         }
       }
     }
}
object RingBenchmark{
  def main(args:Array[String]){
    start(args(0).toInt,args(1).toInt)
  }
  def start(n:Int,m:Int){
     val latch=new CountDownLatch(n)
     val first=new Process(m,null,latch)
     val p=createProcess(first,n-1,m,latch)
     first.next=p
     val start:Long=System.currentTimeMillis
     first.start
     first!Message()
     latch.await()
     println(System.currentTimeMillis-start)
  }
  def createProcess(p:Actor,n:Int,m:Int,latch:CountDownLatch):Actor={
    if(n==0)
      p
    else{
     val next=new Process(m,p,latch)
     next.start
     createProcess(next,n-1,m,latch)
    }
  }
}

与Erlang版本的比较（单位毫秒),scala版本2.7.4-final，erlang是R13B, windows xp