sherrylso

C++博客 首页 新随笔 联系 聚合 管理
  18 Posts :: 0 Stories :: 124 Comments :: 0 Trackbacks

#

摘要:
        在对多线程并发的编程环境下,死锁是我们经常碰到的和经常需要解决的问题。所谓死锁,即:由于资源占用是互斥的,当某个线(进)程提出申请资源后,使得有关进程在无外力协助下,永远分配不到必需的资源而无法继续运行,这就产生了一种特殊现象死锁,如下图:

        线程#1在获得Lock A后,需要获得Lock B,而同时,线程#2在Lock B后,需要获得Lock A。对于线程#1和#2,由于都不能获得满足的条件,而无法继续执行,死锁就形成了。
        死锁是多线程并发编程的大难题,我们可以通过Log Trace、多线程编程辅助工具、IDE调试环境等手段进行调试、跟踪。然而,另一个更难对付的问题是“假死锁”(我在这里暂且称为“假死锁”,实在找不到什么更好的称呼)。所谓的假死锁,我给出的定义是:在有限的时间内的死锁。与死锁不同的是,其持续的时间是有限的,而大家都知道,死锁持续的时间是无限的,如果碰到死锁,程序接下来是什么都干不了了。而正是由于假死锁的相对的持续时间,给我们编程人员会带来更大的麻烦。可以想象得到,我们想通过某些工具来Trace这样一个特定的时间段是非常困难的,更多的情况下,我们需要结合LOG进行合理的分析,使得问题得以解决。本文就假死锁产生的条件,环境,以及解决的办法做一个讨论。
一、假死锁的产生条件。

    考虑下面的例子(我只是给给出了伪代码),假设我们系统中的线程个数是确定的,有限的。在本例中,系统总的线程数目是3。如下图:

线程#1,#2,#3都可能被调度进入临界区A,我们假设线程#1执行临界区A时花费了10s的时间,而在这10s的时间里,线程#2与线程#3都处于等待的状态。也就是说:在这个10s的时间里,系统是没法响应任何的其他请求。我们称之为10s的假死锁。如果在这段时间里,系统需要一些关键的请求被执行,这些关键请求是需要real time地被处理,比如说是Timer事件,则后果是不堪设想的。(注意:我们的假定是系统中的线程只有#1,#2,#3)。
       以此,总结一下发生假死锁的条件,如下:
--〉临界区的代码在集中的时间段内,可能被系统中的任意线程执行,完全由操作系统决定。
--〉临界区的代码在某些情况下,可能是很耗时的。(比如:其执行时间大于100ms,或者,甚至是秒级别的)
二、在Proactor(IOCP)中的假死锁。
        在前面的文章中,我提到过在windows平台上,Proactor设计模式是基于IOCP的。在这里,本文不会用过多的语言来阐述Proactor是怎样的设计,重点放在Proactor的假死锁及其一些解决的办法。另外需要说明的是,我这里所说的Proactor,在技术层面上,等同于IOCP,我们也可以按照IOCP来理解我所阐释的概念。
        我们都知道,IOCP是靠工作者线程来驱动的。工作者线程与一个完成端口对象相关联,当IO 请求被投递到完成端口对象时,这些线程为完成端口服务。需要说明的是,应该创建多少个线程来为完成端口服务,是你的应用设计来决定的(很重要的的一点是:在调用CreateIoCompletionPort时指定的并发线程的个数,和创建的工作者线程的个数是有区别的,详细的技术细节,请参考其他资料)。但是总的来说,在你的系统交付运行后,工作者线程的线程数目是一个确定的值。其结构图,大致如下:

         我们假定使用了线程数目为4的工作者线程来为完成端口服务,它们通过调用来GetQueuedCompletionStatus方法来从完成端口中获取IO相关的packet,一旦获得,它们都会回调业务逻辑层的代码来进行相关的业务逻辑处理。到这里我们看到,假设,在业务逻辑层存在临界互斥区,并且在某一个集中的时间段内,工作者线程都可能被调度执行该临界互斥区,那么,假死锁的条件基本形成,如果某一个线程在该区域花费的时间比较长,假死锁就会发生。
        一般来说,解决这样的问题的关键就是打破形成假死锁的条件:
       第一、在回调函数里,尽量减少锁的使用。
       第二、减量减少临界互斥区的执行时间。对于一些慢速的操作尤其注意。比如:当你在临界互斥区访问慢速的IO操作时(打开文件,读写文件等),可能需要考虑Cache机制,通过使用内存来代替慢速的disk。
       第三、将临界互斥区代码委托给另外独立的线程(或线程组)执行,代价是增加这些线程间的通讯。
       第四、通过使用流控等手段,避免让所有的线程在集中的时间段内访问该临界互斥区。
三、结束语:

         事实上,类似这样的问题,一旦存在,是很难发现和调试的。不过对于多线程的编程,我们都应该遵守以下的基本原则,以最大化的防止死锁和假死锁的发生。

         --> 尽量减少锁的使用频率和保护范围。
         --> 当线程在互斥锁的保护范围内执行代码时,应该:尽量减少对慢速IO设备的访问(如:disk),尽量避免获得其它互斥资源。
         --〉正确使用各种锁,包括:原子操作原语,Read Lock, Write Lock, 和Recursive Lock等。这些锁在不同的场景下有着不同的作用。
posted @ 2007-08-12 15:41 爱上龙卷风 阅读(4034) | 评论 (9)编辑 收藏

     一般来说,基于CS(client-server)软件架构的开发技术有很多种。比较常用的有:基于socket的网络编程、RPC、基于Java技术的RMI(当然C#也有类似技术)、CORBA等。在这里我们只是对基于socket的网络编程与RMI作个对比,有助于我们了解它们各自的应用领域,帮助我们在面对一个具体问题的时候选用适合的技术。另外,本文所做的讨论可以认为是脱离了语言层面的东西,只是对技术的本身做一个讨论,无关乎你是用C++、C#或Java 在开发。
一、RMI技术简介
        本文就以Java为例,简单介绍一下RMI技术。
        从Java1.1开始,远程方法调用作为Java分布式对象技术成为Java核心的API之一(在java.rmi.* 包)。RMI的引入,使得Java程序之间能够实现灵活的,可扩展的分布式通信。RMI允许Java对象存在于多个不同的地址空间,分布在不同的Java虚拟机上。每一个地址空间可以在同一台主机上或者网络上不同的计算机上。由于远程方法调用跨越不同的虚拟机边界到不同的指定的地址空间,所以没有对象共享的全局变量,这就需要对象序列化(Object Serialization)API,它使得Java对象能够在不同的JVM之间传递。对象序列化是特别为Java的对象设计的,这就意味着Java程序中的对象可以作为对象参数存取(可序列化的对象必须实现Serializable接口)。结合RMI和对象序列化机制,就可以访问越过本地Java虚拟机边界的对象以及数据。通过RMI,可以调用远程对象的远程方法,而通过Java对象序列化机制可以将对象传递给这些方法。
        最基本的Java模型并没有提供将远程主机上的Java对象看作本地Java程序地址空间一部分的能力,而RMI祢补了这一不足。另外,由于Java与硬件平台无关的特性,无论是同构的系统还是异构的系统,RMI不需移植就可以顺利运行。
       RMI为Java平台的分布式计算提供了一个简单而直接的模型。因为Java的RMI技术是基于Java平台的,所以它将Java平台的安全性和可移植性等优点带到了分布式计算中。RMI大大扩展Java的网络计算能力,它为编写基于分布式对象技术的企业级Internet/Intranet应用提供了强大的系统平台支持。
      Java RMI体系结构如下图:


二、基于socket的网络编程
        当你使用socket进行网络应用开发的时候,一般的思路是“消息驱动逻辑”,即这样的软件系统一般具有以下特点:
       (1) 客户端与服务器端依靠消息进行通讯。
       (2) 客户端或者服务器端都需要一个消息派遣器,将消息投递给具体的massage handler
       (3) 客户端或者服务器端利用massage handler进行逻辑事务处理
 见下图:

        使用socket开发的软件系统,从技术的本质上来讲,有以下几个特点:
        (1) 基于TCP协议的通讯
        (2) 应用程序本身需要提供对消息的序列化处理(所谓的序列化指的是将消息输出到网络流中)
        (3) 客户端与服务器端需要事先商议好它们之间的通讯协议即它们交互的消息格式
        (4) 由于是消息驱动逻辑,从本质上决定了这样的编程模式很难面向对象化
三、RMI Vs Sochet
        RMI技术比较socket的网络编程主要有以下几个方面:
        第一、.RMI是面向对象的,而后者不是。
        第二、.RMI是与语言相绑定的。比如当你使用Java RMI技术的时候,客户端与服务器端都必须使用Java开发。而socket的网络编程是使用独立于开发语言的,甚至独立于平台。基于socket的网络编程,客户端与服务器端可以使用不同开发语言和不同的平台。
       第三、从网络协议栈的观点来看,RMI与socket的网络编程处于不同层次上。基于socket的网络编程位于TCP协议之上,而RMI在TCP协议之上,又定义了自己的应用协议,其传输层采用的是Java远程方法协议(JRMP)。可见,在网络协议栈上,基于RMI的应用位置更高一些,这也决定了,与socket的网络编程相比,RMI会丧失一些灵活性和可控性,但是好处是它带给了应用开发者更多的简洁,方便和易用。比如:如果你用的是RMI,你不需要关心消息是怎么序列化的,你只需要像本地方法调用一样,使用RMI。代价是:应用开发者无法很好地控制消息的序列化机制。
      第四、这是最后一点不同,我认为也是比较重要的一点,就是两种方法的性能比较,其往往决定着你将使用那种技术来开发你的应用。以下引用Adrian Reber在Network-programming with RMI文中对TCP和RMI所做的一个比较,其做的实验主要是对两者在网络传输的带宽上作的对比: 在网络上传输2 byte的有效数据,对于TCP而言,总共有478 byte被额外传输,而对于RMI, 1645byte被额外传输。
以下是两者的trace结果:
TCP:
46037 > 12345 [SYN] Seq=801611567 Ack=0 Win=5840 Len=0
12345 > 46037 [SYN, ACK] Seq=266515894 Ack=801611568 Win=10136 Len=0
46037 > 12345 [ACK] Seq=801611568 Ack=266515895 Win=5840 Len=0
12345 > 46037 [PSH, ACK] Seq=266515895 Ack=801611568 Win=10136 Len=1
46037 > 12345 [ACK] Seq=801611568 Ack=266515896 Win=5840 Len=0
12345 > 46037 [FIN, PSH, ACK] Seq=266515896 Ack=801611568 Win=10136 Len=1
46037 > 12345 [RST, ACK] Seq=801611568 Ack=266515898 Win=5840 Len=0
RMI:
42749 > rmiregistry [SYN, ECN, CWR]
Seq=3740552479 Ack=0 Win=32767 Len=0
rmiregistry > 42749 [SYN, ACK, ECN]
Seq=3749262223 Ack=3740552480 Win=32767 Len=0
42749 > rmiregistry [ACK] Seq=3740552480 Ack=3749262224 Win=32767 Len=0
JRMI, Version: 2, StreamProtocol
rmiregistry > 42749 [ACK] Seq=3749262224 Ack=3740552487 Win=32767 Len=0
JRMI, ProtocolAck
42749 > rmiregistry [ACK] Seq=3740552487 Ack=3749262240 Win=32767 Len=0
Continuation
rmiregistry > 42749 [ACK] Seq=3749262240 Ack=3740552506 Win=32767 Len=0
JRMI, Call
rmiregistry > 42749 [ACK] Seq=3749262240 Ack=3740552556 Win=32767 Len=0
JRMI, ReturnData
42749 > rmiregistry [ACK] Seq=3740552556 Ack=3749262442 Win=32767 Len=0
JRMI, Ping
JRMI, PingAck
42749 > rmiregistry [ACK] Seq=3740552557 Ack=3749262443 Win=32767 Len=0
JRMI, DgcAck
42749 > rmiregistry [FIN, ACK]
Seq=3740552572 Ack=3749262443 Win=32767 Len=0
rmiregistry > 42749 [FIN, ACK]
Seq=3749262443 Ack=3740552573 Win=32767 Len=0
42749 > rmiregistry [ACK] Seq=3740552573 Ack=3749262444 Win=32767 Len=0
        实验的结果是:RMI与TCP based socket相比,传输相同的有效数据,RMI需要占用更多的网络带宽(protocol overhead)。从这里,我们可以得出一个一般性的结论:RMI主要是用于远程方法的”调用“(RMI是多么的名符其实:)),其技术内涵强调的是“调用”,基于此,我能想到的是:移动计算,和远程控制,当你的应用不需要在client与server之间传输大量的数据时,RMI是较好的选择,它简洁、易于开发。但是,一旦你的应用需要在client与server之间传输大量的数据,极端的,比如FTP应用,则RMI是不适合的,我们应该使用socket。

四、参考资料:
Network-programming with RMI, by Adrian Reber, URL:
http://42.fht-esslingen.de/~adrian/master/rmi.pdf
posted @ 2007-07-28 19:06 爱上龙卷风 阅读(5596) | 评论 (2)编辑 收藏

     摘要: 在windows平台下,用于对多线程(包括进程)之间的同步保护机制,基本上有这么几种:
1)Critical Section对象 2)Event对象 3)Mutext 对象 4) Semaphore对象。网上已经有很多的文章在介绍这些对象是怎么使用的。本文的着眼点在于:总结出这些同步保护机制的一些明显的行为特征,而这些行为特征,也是我们再写程序时经常会碰到的。  阅读全文
posted @ 2007-07-22 21:10 爱上龙卷风 阅读(4863) | 评论 (6)编辑 收藏

不知道大家是否有同感,在开发软件应用系统的过程中我们经常面临一个非常tedious的问题,即如何分类和处理软件行为产生的错误值,大致有这样几个方面的问题:
        第一.错误值如何分类。参考microsoft的开放文档,按照错误值的严重程度分为critical、error、warning、information等四个级别。
        第二.错误值如何在各个软件子模块中有效的表示和沟通。
        第三.如何划分出用户所关心的错误值集合。
这篇文章对错误类型定义与处理作了很好的阐释。推荐给大家,大家如果有什么好的开发经验,欢迎探讨。
FYI:
Taxonomy of Error Types and Error Handling
Posted: Jun 21, 2007 8:13 PM

Most of what is written about error and exception handling is fairly abstract and vague. When specific recommendations are made, those usually consist of examples given for specific circumstances. Yet, error handling is a fundamental task for developers. This brief review attempts to categorize the different types of error conditions a program can encounter. By describing these categories, I also provide suggestions on how to handle each type of error condition.

In general, errors a program can encounter tend to be the result of one of three things:

  • Restrictions: Arguments to a routine that can never work, and always result in an error, define a restriction on the use of the routine. Ensuring that only correct arguments are passed to a routine is the type of thing that programming by contract is meant to address.
  • Inconsistencies: When values or resources are not what they are expected to be, or are missing, that creates an inconsistency between the expected state of the environment and the actual state. This may be the internal environment, such as a null pointer, or the external environment, such as a corrupt file. It doesn't encompass inconsistencies in the data model, which often needs to be temporarily inconsistent during an operation (e.g. adding a node to a linked list).
  • Failures When an operation simply does not work, and it's out of the program's control, this is a failure. For example, a pulled network cable.

These types of errors overlap to an extent (say, a working network could be considered part of the expected state, making it an inconsistency error). In general, though, most errors can fall into one of these categories.

Sometimes failures are not errors, and are just a way of detecting the current external state. For example, opening a file that doesn't exist may fail, but results in an error only when that file is actually needed.

Error Handling Responsibilities

Program code is responsible for the consistency of the internal program state. Generally certain code has primary (ideally, exclusive) responsibility for parts of the internal state. Inconsistency errors that occur within the code responsible for that state are bugs.

Sometimes the state management responsibility is shared between different sections of code. This is a bad idea, because it makes assigning responsibility for an inconsistency error harder, but it does happen in practice.

It's important to make a distinction between error detection and debugging. Often, data generated in the process of error handling is mixed together with diagnostic information. If possible, these types of information should be kept completely separate—at least conceptually, even if combined in a single data structure.

Safe Zones

Restrictions can be checked before calling a routine, or within a routine. It seems a waste of time to check arguments every time a routine is called when you already know those arguments are correct. One strategy is to separate parameter checking from parameter usage. This doesn't work reliably for library code, where anything can happen between the check and the use of the parameters, but within a base of code for a particular application or within a library, you can restrict the code to not change a value known to be safe.

The code between a parameter check and the next change to a parameter variable is a safe zone, where parameters don't have to be re-checked. This is only valid for restriction errors, because inconsistency and failure errors can be caused by things outside the code's safe zone. Things like critical sections (in multithreaded environments), semaphores and file locks are meant to create a very limited kind of safe zone for inconsistency and failure errors.

The code safe zones for parameters can overlap with others, and may not be well defined. One way to deal with this is to assign known safe values to variables which indicate this safety. Joel Spolsky wrote about one way to do this using variable naming conventions in Making Wrong Code Look Wrong. Safe values should be assigned to variables declared constant.

Reporting Errors

Code calling a routine needs to know three things to decide how to proceed: First, whether the data is returned, if any, or if the method invocation succeeded; second, whether an error occurred; and, third, whether the error is permanent or transitory. This defines the following possible error states returned from a routine:

  1. Successful
  2. Restriction error (always permanent)
  3. Permanent (bug) inconsistency
  4. Transitory (detected) inconsistency
  5. Failure (transitory for all we know)

It's often a bad idea to mix an error code with a return value, such as designating a specific values—say, 0 or -1—to be invalid. Some languages, like Python, allow multiple values to be returned from a method as tuples. A tuple is basically an anonymous class, and can be implemented in a language like Java by defining a class for objects returned by a method, or in C by defining a struct which is passed as a parameter and is updated by the function. But in many cases, exceptions are a much better way to separate error information from return values.

Exceptions transmit an object from the exception location to a handler in a scope surrounding it, or surrounding the point where the routine was called. The exception objects include information by the object type and class, and debugging information the data contained within that type. Exceptions by themselves don't indicate the error state, so that must be included as an attribute of the exception object, or the error state must be deduced from the debugging information (object type and data).

Java introduced the controversial notion of checked exceptions, which must either be caught or declared to be thrown by a method in order to compile, while unchecked (or runtime) exceptions behave like exceptions in other languages. The main cause of the controversy is that there has been no good definition of why there should be a difference and, as a result, no consistent strategy in the implementation in various libraries, including standard parts of the different Java runtime libraries.

In general, unchecked exceptions are meant for bugs, where an error indicates that the code is simply wrong and must be fixed (restriction and bug inconsistency errors). An example is a NullPointerException. Checked exceptions are for detected inconsistency and failure errors, where the program may have a strategy of handling the error. An example is an I/O error.

Transactional Operations

One strategy to handle errors is to make all operations transactional, so that if they fail, it's as if the operation was never tried. One way implement this is to define an "undo" operation for every change:

Ideal transactional function

In this example, the functions are also transactional, and thus don't need to be rolled back if they fail. This can be done with nested if/else blocks, or with nested try/catch blocks. If the "undo" operations themselves have errors, the result looks more like this:

Realistic transactional function

One way of dealing with this is to modify a copy of the program state, and if all operations succeed, only then commit the changes. The commit may fail, but this isolates the possible state changing errors to one point, and is similar how databases implement transactions. Another way to implement transactional operations is to make a copy of before any state is changed, and use that copy to restore the expected state, in case of an error.

In summary, having a clear taxonomy of error conditions that code may encounter helps develop better strategies for dealing with, and possibly recovering from, those errors.

posted @ 2007-07-15 18:31 爱上龙卷风 阅读(1124) | 评论 (0)编辑 收藏

一、异步IO
        对于应用程序而言,有两种类型的IO调用:即同步IO与异步IO。其本质的区别是:同步IO会block当前的调用线程,而异步IO则允许发起IO请求的调用线程继续执行,等到IO请求被处理后,会通知调用线程。在windows平台上,应用程序可以调用CreateFile API, 并通过设置FILE_FLAG_OVERLAPPED标志来决定是否发起异步IO请求。
        对于异步的IO请求,其最大的好处是:慢速的IO请求相对于应用程序而言是异步执行,这样可以极大提高应用程序的处理吞吐量。发起IO请求的应用程序需要关心的是IO执行完成的结果,而不必忙等IO请求执行的过程。
       事实上,无论对于同步IO,还是异步IO,当IO请求发送到device driver后,device driver的执行总是异步的,当它接到IO请求之后,总会马上返回给IO System。而IO System是否立即返回给调用线程,则取决于FILE_FLAG_OVERLAPPED标志的设置,如下图:


二、异步IO的同步问题。
        我们使用异步IO,是为了提高应用程序的处理吞吐量。但是,当异步IO不再异步时(无论你是否设置FILE_FLAG_OVERLAPPED标志),应用程序的性能会受到极大的影响。根据Microsoft Knowledge Base 156932, 在下列几种情况下,异步IO会失去它的异步性,而表现出同步的性质:
1)如果文件使用了NTFS compression压缩,则system driver不会异步地存取这样的文件。
2)扩展文件长度的IO操作不会是异步操作。
3)Cache机制。如果IO操作使用了file system cache,则这样的IO操作会被当成同步IO,而非异步IO。
即使你使用了FILE_FLAG_OVERLAPPED标志。在这种情况下,
a.如果需要读取的数据已经在Cache里,那么I/O drivers会认为这样的IO请求可以被立即处理,其结果是ReadFile 或者WriteFile调用返回TRUE,表示是:同步处理完成。
b.如果需要读取的数据不在Cache里,windows NT的file system是使用page-faulting机制来实现cache管理,而page-faulting总是被同步处理, Windows NT没有提供异步的page-faulting机制。的确, file system driver使用了线程池来缓解这一问题,但是,当应用程序发起的IO请求足够多时,线程池还是不能应付的。
        在我们开发基于异步IO应用程序时,应该避免上述问题的出现,因为它们会使程序的性能大打折扣。
那么,对于Cache,我们如何避免呢?答案是:请使用FILE_FLAG_NO_BUFFERING标志。这个标志会使异步IO真实地异步执行。
三、性能的测试数据(仅供参考)。
      我在我的机器上,简单地对使用FILE_FLAG_NO_BUFFERING标志的异步IO,与不使用FILE_FLAG_NO_BUFFERING标志的异步IO进行了对比。
操作:顺序读取1G的文件。
x轴表示:每次读取的字节数(单位:K/每次)
Y轴表示:读取完成所需要的时间。(单位:millisecond)
注意:每次测试读取的内容总数是相等的(1000M)。
例如:如果每次读取128k,则需要读取8000次(128k*8000 = 1000M)。
如果每次读取256k,则需要读取4000次(256k*4000 = 1000M)。
粉红色的线没有使用FILE_FLAG_NO_BUFFERING标志,而黄色的线使用了FILE_FLAG_NO_BUFFERING标志。

从以上的数据,我们可以得出以下结论:
1) 当使用FILE_FLAG_NO_BUFFERING标志,应用程序的性能会极大提高,大概有50%的提高。
2)在使用异步IO的时候,还有一个注意的问题是:当你每次读取的字节数增大的时候,性能也会提高。尤其在小于1024k时,当增大次读取的字节数,性能都有明显的提高。在混合了网络传输等复杂因素的应用程序开发过程中,建议将该值设置为可配置的参数,通过调整该参数,使你的应用达到最好的性能。

参考资料:

1) Microsoft Knowledge Base 156932

2)  Microsoft Windows Internals, Fourth Edition. 

posted @ 2007-07-01 18:45 爱上龙卷风 阅读(8933) | 评论 (6)编辑 收藏

        作为程序员,一直困扰我的一个问题是:一名优秀的程序员,应该是注重面向对象分析能力的培养,还是注重算法分析能力的培养。我相信,这也是一个很多人面临的问题。我的感觉是:很多system level的程序员更加侧重于算法,而application level的程序员,更多的倾向于讨论面向对象。大家也可以看到,很多知名IT公司的面试,比如google,比如微软,很喜欢考察程序员的算法方面的能力。而自从设计模式理论风靡IT界以来,好像这些状况有些改变,他们开始考察设计模式相关的问题,考察程序员面向对象的分析能力。不可否认的是,设计模式理论,其基于面向对象的理论技术,提供了开发者非常实效,有用的解决问题的模式。依赖于问题的上下文,应用设计模式,开发者可以开发出更加"面向对象"的系统。
   设计一个复杂的系统的本质,就是:将复杂的问题分解成小的,为我们所理解的问题,然后分而治之。人类的智力是有限的,当我们在面对一个复杂问题的时候,总会习惯于首先将他分解,分解到问题足够的简单,足够为我们所理解,解决。事实上,无论是面向对象,还是算法,它们都是分解复杂问题的方法与手段。是采用面向对象的方法去分析,还是使用算法的分析方法,完全是由客观的主体决定的。非常遗憾的是,这两类分析方法是互斥的,排他的,你是不可能同时使用这两种方法的分析解决问题。我们先看一个简单的例子:
问题的定义:client和server使用TCP/IP进行一个简单的交互。
算法的分解方法如下:


问题空间被分解成为几个执行步骤,accept,connet,send,recieve。
面向对象的分解方法如下:


问题空间被分解成为几个对象:c_connector, 主要负责建立TCP连接,在连接成功后,会得到一个c_socket_stream对象,该对象负责主要负责发送和接收网路数据。c_acceptor,负责监听网络连接请求,在一个TCP连接成功建立后,返回给调用者一个c_socket_stream。
两者的区别在于:两者分解方法的着重点是不同的,算法的分析方法强调的是事物内部各类事件之间的顺序,依赖,耦合关系。算法所关心的是事件本身,例如上例中:它关心的是send,recv这样发生在事物内部的事件,以及它们之间的调度关系。面向对象的分析方法在于强调的是事物内部各类客观的主体,以及它们之间的相互协助。
从这点上可以看到:在分解一个问题的时候,算法偏重于微观,面向对象侧重于宏观;算法偏重于细节,面向对象侧重于整体。可以看到,我们很容易得出这样的结论:当面对一个复杂的问题的时候,我们的直觉会告诉我们,我们会更加倾向于使用面向对象方法理论来分析问题。这也是几十年来面向对象的软件实践经验告诉我们的真理。在计算机应用开发领域,面向领域问题本身的复杂性(这包括许多方面:比如你的需求在不断变化,你的应用方式在不断变化等等),决定了其更适合使用面向对象的方法来分析问题。面向对象的软件系统会更加的富有弹性,更加的能适应这种快速的变化。
     如何做面向对象的设计分析?关键在于:
     1) 对复杂问题的抽象,将复杂的问题抽象成为一组对象,就是我们熟知的objects。object是面向对象软件系统的行为主体。抽象也意味着我们应该忽略细节的东西,注重整体的东西。
     2)组织这些objects,使他们形成具有一定结构的整体。比如:通过继承,使它们成为父子关系,通过组合,使它们具有合作依赖关系。通过组织这些objects,我们更加能清楚地看到这些这些objects公共的行为和属性。这就形成了面向对象软件服用的基础。
    很多人说:算法是程序设计的灵魂,但是我们也不能忘记;面向对象,帮助我们能够更加容易理解问题复杂性的本质。或许算法与面向对象的最佳的结合点在于: 使用面向对象的方法分解问题,而使用精良的算法解决问题。

posted @ 2007-06-24 22:31 爱上龙卷风 阅读(1848) | 评论 (7)编辑 收藏

一般来说,网络应用系统服务器的实现,我们从设计模式的角度看,有两种设计方案可供选择:
Reactor服务器,或者Proactor服务器。无论是Reactor,或者Proactor, 都是基于事件驱动的架构设计(Event-driven architecture), 它们的核心是思想是:分离网络事件的监视,驱动与事物本身的逻辑处理。我们能看到的是:对任何的网络应用而言,其对网络事件的监视,处理往往是大同小异的,是可以分离出来作为可复用组件而存在的。
对所有这些网络应用,所不用的是对网络请求的逻辑处理。不同于Proactor, 或者Reactor,一般的设计方法是:
 

而Proactor, 或者Reactor,设计的精髓是:


别看这一点小小的变化,这是所谓的Hollywood Principle: 'Don't call us, we'll call you'。这是Framework设计者惯用的设计技巧,依赖倒转(The Dependency-Inversion Principle):
a. 高层模块不应该依赖于低层模块,应当依赖于抽象。
b. 抽象不应该依赖于细节,细节依赖于抽象。
言归正传,我们来具体谈谈Reatctor and Proactor.
一 、Reactor服务器实现。
在Reactor的实现可分为两层:
a.Demultiplexing/Dispatching层:独立于应用逻辑层,捕获,分发网络请求给具体的网络请求处理器。
在这里注意的是,Demultiplexing和Dispatching是两个不同的概念,Demultiplexing指的是网络请求的侦听,及其侦听以后寻找适合的处理器。Dispatching指的是对处理器的回调。
b.应用逻辑层组件:主要处理与应用相关的事物处理。
其基本的结构图为


其各个组成模块的功能为:

--〉句柄: 调用操作系统API获得,用于identify事件源,如:网络连接,打开的文件。
--〉同步事件分离器:操作系统功能,通过API提供,典型的如: select调用,如windows平台上的WaitForMultileObj
--〉事件处理器:这是Demultiplexing/Dispatching层定义的抽象借口,是Demultiplexing/Dispatching层与应用逻辑层之间的协议约定。应用逻辑层依赖于该抽象借口。
--〉具体事件处理器:事件处理器的具体实现,一般来说,由应用逻辑层组件实现。
--〉Reactor:提供接口给应用逻辑层,注册或者反注册事件处理器,运行应用的事件循环(反复调用同步事件分离器),驱动Demultiplexing/Dispatching层。

二 、Proactor服务器实现。
在Proactor的实现也分为两层:
a.Demultiplexing/Dispatching层:独立于应用逻辑层,捕获,分发网络请求给具体的网络请求处理器,不同于Reactor的是,这一层的策略处理
基于异步操作,从实现的复杂度上,要复杂于Reactor。
b.应用逻辑层组件:主要处理与应用相关的事物处理。
Proactor基本的结构图为


--〉句柄: 调用操作系统API获得,用于identify事件源,如:网络连接,打开的文件。与Reactor不同的是,由于Proactor操作是异步的,所以,与每一个异步IO操作项关联的,有一个完成事件(Completion Event),当一个异步的IO操作执行完成后,一个操作系统的IO子系统会产生一个完成事件。
--〉异步操作:一个异步操作可以是一个服务请求的具体实现,如从连接的socket上读入数据,或者写入数据到本地磁盘。异步操作的发起执行,并不会由于慢速的IO而阻塞调用线程,调用线程在发起异步操作之后,可以去做别的事情。这是Proactor能增大服务器处理吞吐量的关键所在。我们付出的代价是,开发的复杂度要比Reactor。
--〉完成 事件处理器:Demultiplexing/Dispatching层定义的抽象借口。由应用逻辑层组件继承来实现这些接口
函数。
--〉具体完成事件处理器:事件处理器的具体实现。
--〉异步操作处理器:由native的操作系统实现。当一个异步操作完成执行时,异步操作处理器会产生一个完成事件,然后把这个完成事件插入到完成事件队列。
--〉完成事件队列:用于保存异步操作完成事件的队列。在windows平台上,就是我们所说的完成端口。
--〉异步事件分离器: 操作系统功能,通过API提供。在windows平台上,就是GetQueuedCompletionStatus()。异步事件分离器等待在完成事件队列上,当有完成事件被插入到完成事件队列,异步事件分离器会从完成事件队列取出该完成事件,返回给调用者。
--〉Proactor:运行应用的事件循环(反复调用异步操作处理器),驱动Demultiplexing/Dispatching层。
--〉发起者:用于发起异步IO操作。
三 、选择?是Reactor,还是Proactor。
在我们实现我们的服务器,是选择Reactor,还是Proactor,个人认为需要考虑的因素是:
1)对于Reactor而言,好的地方是开发的复杂度小于Proactor,但缺点同样明显:
第一,基于Reactor实现的服务器可扩展性不如Proactor,这是由其本质决定的。在wiondows平台上,无论是
Select,或者是WaitForMultiObj,其等待的最大handle数有一个最大的上限值(默认值是64)。
第二,基于Reactor实现的服务器服务请求处理的吞吐量不如Proactor好。特别是当对客户端的请求处理需要更长的时间时,在Reactor的Demultiplexing/Dispatching层,由于Demultiplexing和Dispatching被顺序化处理,这样的话,很容易成为服务器性能的瓶颈。
2)对于Proactor,如果你需要一个高性能的,高吞吐量的,并发服务器,Proactor绝对是首选的解决方案,它的问题主要在开发的难度比较大。
不过,总的来说,我们可以看到,基于模式设计的Reactor和Proactor,都很好地把Application-Specific的处理逻辑从网络,IO事件的Demultiplexing/Dispatching中分离出来,对应用程序而言,由于这样的松耦合关系,我们的应用完全可以在Reactor和Proactor中自由切换,而不需要修改任何的代码。、
四 、后记。
ACE Framework,对Reactor和Proactor设计模式给出了经典的实现。请参考:
http://www.cs.wustl.edu/~schmidt/
个人觉得是很好的学习材料。

posted @ 2007-06-10 20:19 爱上龙卷风 阅读(1030) | 评论 (1)编辑 收藏

     摘要: 1. 什么是Multi-methods. 在阐述这个概念之前,我们先看一下什么是多态(Polymorphisn)。多态是面向对 象程序设计的一个重要的特征, 多态是允许你将父对象的指针(或者引用)设置成为它的子对象的技术,赋值之后,该父对象指针(或者引用)就可以根据当前赋 值给它的子对象的特性以不同的方式运作。简单的说,就是一句话:允许将子类类型的指针赋值给父类类型的指针。多态性在...  阅读全文
posted @ 2007-05-06 22:28 爱上龙卷风 阅读(2174) | 评论 (4)编辑 收藏

仅列出标题
共2页: 1 2