関小君刷题记

**一、概述
面向对象编程是软件开发中的一项利器，现已经成为大多数编程人员的编程思路。很多高级计算机语言也对这种编程模式提供了很好的支持，例如C++、Object Pascal、Java等。曾经有大量的软件工程师使用C语言作为他们的谋生工具，随着面向对象的深入人心，微软公司也对其C语言进行了扩充，形成了C++语言，全面支持面向对象的软件开发模式。
“面向对象”的主角即是“对象”，其良好的可充用性和对数据逻辑的封装成了它在当今计算机软件开发领域一炮走红的主要因素。程序开发人员也正是利用了对象的这些特点在程序中大量创建对象，以至于他们往往忽略了这种创建对象以及以后销毁对象是带来的系统开销之大是多么不可想象。特别是对于现在十分流行的Java语言，这更是一个不能避免的问题。下面，我们就从分析Java的内存管理机制入手，首先看看造成Java程序有些时候效率低下的症结所在，然后再讨论一下如何利用编程技巧改进我们的程序。

二、****Java****的内存管理机制
1****、垃圾回收与小对象
与C/C++语言相比，Java语言不需要程序员显式地为每个对象定义“析构函数”，Java虚拟机（JVM—Java Virtual Machine）会利用自身的“垃圾回收”机制在后台启动一个守护线程负责对不再被利用的对象进行内存清理工作。这种思路并不是Java的“原创”，早在20世纪60年代，自动垃圾回收就已经被提出并在其他语言中得到了应用。所有的垃圾回收机制都遵循一条统一的原则“利用不同的方法来判定程序中不再被引用的对象，销毁它们释放内存。”其不同之处也就在于“判定”过程（Java使用的是一种称为“可达性分析”的方法，这里不作主要介绍）。
Java的自动垃圾回收机制确实可以让程序员从繁重的开发工作中得以解脱，使他们不再关心自己曾经创造的对象在不用时如何处理，从而将精力主要集中在业务逻辑的开发上。但是一句富有哲理的中国的老话在它身上再次应验：“Java垃圾回收是一把双刃剑！”
首先我们注意到，“垃圾回收”是JVM支持的一项后台工作，是“时事”进行的。当它发现某个对象处于“不可达”状态时，理论上会去自动回收它而不必程序显式调用任何方法。注意我们所说的是“理论上”。也就是说并不能保证一个对象处于“不可达”状态时马上会被垃圾收集线程发现并对其进行回收，虽然Java API中提供了一些触发垃圾回收的方法，如System.gc（）等，但是即使我们显式调用了，还是不能保证垃圾回收器被触发工作，这点要特别注意。所以这就会导致一种极端情况出现，如果们的程序中在某个时刻突然出现了大量废弃对象，然而垃圾回收并没有及时对其作相应的处理，很可能造成垃圾对象充满内存，造成“OutOfMemoryError”。
其次，由于回收线程在后台是时事进行的，很可能在没有垃圾的时候做无谓的检查工作（更糟糕的情况就是像上面提到的那样有垃圾时反倒不能及时被触发），造成了时间上的浪费，其检查不可达对象的过程也势必造成了性能耗损。
除了造成时间上的浪费和无谓的性能耗损，垃圾回收器最让人担忧的一个隐患就是，为了保证垃圾回收的顺利进行，Java不得不为已创建的对象加上一些内部信息加以识别。另外，为了将这种回收机制对于每一个对象都同步，还需要一些额外的信息。因此，当JVM开始启动一个程序的时候，对象在内存中比我们实际创建时认为其所占的空间要大得多。下表显示了几种不同类型的Java对象的“内容空间”（也就是该类型的数据所占理论空间）与在JVM中实际空间的对比：

canvas.png

上面这组数字是针对每个对象平均而言的，所以对象越大，每个对象的这些额外信息的百分比也会越小。对于大对象来说，也许这些额外信息所占的比重微不足道，但是如果程序中有大量的小对象被创建，有多少空间是不在我们掌握之中的阿！而随着经济信息的发展，在实际的科学研究中，特别是在计算机仿真这一领域，我们的模拟环境中经常要出现大量小对象的情况，因此这是一个亟待解决的缺陷。

2****、与****C++****对比
Java在某些方面的性能低下使人不自觉地想到了它的主要竞争对手C++，两者的性能比较也就在所难免。仅对为对象分配内存这一性能测试中，由于Java要为对象初始化一些方便垃圾收集时的附加信息，以及两种语言本身的结构差异，Java处于了明显的下风。下表列出了Java在不同JVM中为对象分配内存时所花费的时间与C++的比较结果：

canvas1.png

通过上面对比，是不是就是说明Java在实际开发中没有办法克服上面的缺陷呢？实则不然，我们完全可以通过一些编程技巧对此加以性能优化。重要的是，作为一名程序员，必须注意对Java的这个“天生缺陷”时刻保持警惕。其实有很多简单实用的方法，比如尽量在程序中使用Java提供的基本类型、尽量实现“对象重用”，还可以利用一些设计模式提供的思路，比如“单例模式”（需要在特定的需求下）、“享元模式”（FlyWeight）。它们的思路大体一致，就是尽量使程序共享小对象。下面我们探讨一中解决方案——利用“对象池”来管理维护Java小对象。

三、“对象池”的设计和应用
1****、“对象池”的设计思想
用所谓的“对象池”来管理Java小对象可以让多个用户进程共享这些对象，以减少大量创建对象带来的内存开销。这种技巧适用于多个进程在不同时间对一些“行为相似”的小对象有大量需求的情况。它所带来的好处主要有以下两点：
1、  进程不再需要创建对象，节省了加载时间（Load Time）；
2、  进程在使用完对象之后将其归还给“对象池”继续保存管理，于是减少了“垃圾收集”(Garbage Collection)的开销。
“对象池”的思路类似于“图书馆借书”，当我们需要一本图书的时候，我们知道从图书馆借阅要比自己购买经济得多。同样，当一个进程需要一个对象时，它从一个已有的存储对象的容器中“借来”一个使用，比创建一个新对象要节省很多系统开销。也就是说，图书馆中的书相当于程序中的对象；现实中的借阅者相当于程序中需要对象的用户进程。当一个进程需要一个对象的时候，它从对象池中借出一个对象，使用完毕后将其交还对象池继续对其进行保存管理。
当然，对象池是为了更好地保证程序的鲁棒性而设计的，不能为了节省系统开销而完全照搬图书馆借书的思路。在现实中，如果我们要借阅的书已经全部借出（包括副本），我们不得不等其他读者将其归还再借。然而，在程序中有可能一个迫切需要该类对象的进程没有耐心等待其他进程将对象归还，这时，就要由对象池来创建一个新对象。

2****、“对象池”的实现
对象池（ObjectPool）的内部数据结构由两个HashTable对象来维护，它们分别是“locked”和“unlocked”。前者用于存储和管理已经“外借”的对象，后者用于存储和管理“在库”对象。它们的key值就是对象本身的引用，value值为“上次使用时间”（Last-Usage Time）。这里注意，对于locked，value值为“上次外借时间”；对于unlocked，value值为“上次归还时间”。
通过保存对象的“上次使用时间”信息，对象池在对象的上次使用时间与当前时间之差超出消亡期限的情况下，将该对象“消灭”，以减少保存“不再使用对象”带来的内存开销。这个消亡期限作为ObjectPool的一个成员变量在子类的构造器中初始化（在这里为了使程序简化，我们采用硬编码的方式人工给出消亡期限的值）。

下面是ObjectPool的程序骷架：
import java.util.;*

public abstract class ObjectPool{
**       private long expirationTime;**
**       protected HashTable locked, unlocked;**

**       abstract Object create( );**
**       abstract boolean validate(Object o);**
**       abstract void expire(Object o);**

**       ObjectPool(long time){**
**              expirationTime = time;**
**              locked = new HashTable( );**
**              unlocked = new HashTable( );**
**       }**

**       synchronized Object checkOut( ){**
**              long now = System.currentTimeMillis( );**
**              Object o;**
**              //****如果****unlocked****队列不为空，则遍历**
**              if (unlocked.size ( ) > 0){**
**                     Enumeration keys = unlocked.keys();**
**                     while (keys.hasMoreElements()){**
**                            o = keys.nextElement();**
**                            //****如果当前对象超出“消亡期限”，则将其消灭**
**                            if (now – ((Long)unlocked.get(o)).longValue( ) > expirationTime){**
**                                   unlocked.remove(o);**
**                                   expire(o);**
**                                   //****将****Object o****的引用赋空值是为了触发垃圾收集器对其回收**
**                                   o = null;**
**                            }**
**                            //****如果当前对象未超出“消亡期限”，则检查其是否满足用户进程的需求**
**                            else{**
**                                   //****如果满足，将其外借**
**                                   if (validate(o)){**
**                                          unlocked.remove(o);**
**                                          locked.put(o, new Long(now));**
**                                          return o;**
**                                   }**
**                                   else{**
**                                          //???****如果不满足，将其消灭**
**                                          unlocked.remove(o);**
**                                          expire(o);**
**                                          o = null;**
**                                   }**
**                            }**
**                     }**
**              }**
**              //****若到此为止还未找出可用对象，则创建新的对象实例**
**              o = create( );**
**              locked.put(o, new Long(now));**
**              return(o);**
**       }**

**       synchronized void checkIn(Object o){**
**              locked.remove(o);**
**              unlocked.put(o, new Long(System.currentTimeMillis( )));**
**       }**
}

3****、说明：
checkout（）方法是对象池的主要方法，它的作用是将用户进程需要的对象“外借”。它首先检查unlocked队列中是否有对象可借，如果有，它就遍历这些对象并找出其中一个可用的（validate）对象作为方法返回值。一个对象对于用户进程是否可用取决于两个因素。
首先，对象池检查它是否超出了消亡期限，如果是，则由该方法调用expire（）方法（由子类定义）将其消灭；其次，对于每一个在消亡期限内的对象，该方法调用validate（）方法（由子类定义），检查其是否满足用户进程的要求。
如果在非空的unlocked队列中找出一个对象满足上述两点要求，就将其传递给用户进程进行使用，并将其从unlocked队列中删除，同时添加到locked队列中（表明该对象已外借）；如果unlocked队列为空，或者其中没有一个对象满足上述的借出条件，则我们需要实例化一个新对象并将其引用作为整个方法的返回值。
checkIn（）方法相对简单，它的工作只是将用户进程返还的对象回收，并将其从locked队列中删除，同时添加到unlocked队列中，注意这里记录的是返回时间。
另外三个方法都要由继承自抽象类ObjectPool的子类来定义，下面我们举一个例子来证明使用对象池这种编程技巧是高效的。

4****、模拟测试
下面模拟一个蜂群工作的例子，我们设计一个蜂窝，里面住满了蜜蜂。每只蜜蜂如果在2秒的时间间隔内没有外出工作，则认为它已经丧失了工作能力（即“消亡期限”为2秒），在它的生命周期内，只能外出工作三次，每次工作采蜜量最多为10mg。很多个进程（由线程模拟）在一段时间内让蜜蜂外出工作。为了简单明了，我们的进程借出一只蜜蜂后只是简单地打印出一个随机生成的位移偏移量（假设在方圆100平方米内工作），并等待一段时间后（表示正在外出工作）将其返还给蜂窝。消灭一只蜜蜂对象时仅是打印出“该蜜蜂生命结束”的提示信息。当总采蜜量达到一定总量时程序结束。（程序代码省略）
注意：只要有若干蜜蜂对象进行了多次工作（不超过3次），就简单明了使用“对象池”技巧提高了程序的效率。
我们在模拟测试的时候发现了这样一个现象：如果很多线程BeeThread在很短的时间段内向对象池提出外借蜜蜂对象的申请，由于之前借出的蜜蜂对象处于外出工作状态，尚未返回蜂窝，所以不得不新创建蜜蜂对象。一段时间过后，一些工作完毕的蜜蜂飞回了蜂窝，但是此时总体工作已经完成，不再有进程外借蜜蜂，也就是说checkOut（）方法不再被调用（销毁过期对象和失效对象的工作是在checkOut方法中进行的，见上面代码），我们观察统计结果发现，在对象池中并没有销毁任何超出消亡期限的蜜蜂对象。
一般来说，对象池经常使用在持续时间较长的、由用户进程提出外借要求的程序中，以提高程序的效率。因此上述的这种反而“高消耗”情况出现的几率较小，但由于我们的测试硬件条件有限，只能用线程来模拟进程，因此出现这种情况也就不足为奇了。但这恰好说明了这种方法还存在缺陷。那就是我们将过期对象的消亡工作放在了checkOut（）方法中进行，也就是说消亡工作要依赖于用户进程直接或间接调用checkOut（）方法。如果出现了上述那种用户进程外借对象经历较长时间后才将其归还给对象池，而以后再也没有其他进程调用checkOut（）方法的情况时，过期对象得不到及时消灭的现象就很可能出现。

5****、改进
要解决上述问题，比较直观的想法是模仿JVM的垃圾收集器，将消亡过期对象的工作从对象池的checkOut（）方法中独立出来，交由一个线程去处理。这样就保证了在程序运行过程中，总有一个“清理线程”定时地针对过期对象进行清理工作。这个线程的工作周期就可以定为对象的“消亡期限”。它需要在ObjectPool的构造器中进行初始化。
需要在ObjectPool类中加入一个新的同步方法cleanUp（）来说明具体怎么清理：
**       synchronized void cleanUp( ){**
**              Object o;**
**              long now = System.currentTimeMillis( );**
**              Enumeration keys = unlocked.keys();**
**              while(keys.hasMoreElements()){**
**                     o = keys.nextElement();**
**                     if ((now – ((Long)unlocked.get(o)).longValue( ) )> expirationTime) {**
**                            unlocked.remove(o);**
**                            expire(o);**
**                            o = null;**
**                     }**
**              }**
**              System.gc( );**
**       }**

这时，被提炼出消亡工作的checkOut（）方法变为：
synchronized Object checkOut( ){
**       long now = System.currentTimeMillis( );**
**       Object o;**
**       //****如果****unlocked****队列不为空，则遍历**
**       if (unlocked.size( ) > 0){**
**              Enumeration keys = unlocked.keys();**
**              while (keys.hasMoreElements()){**
**                     o = it.next( );**
**                     if (validate(o)){**
**                            unlocked.remove(o);**
**                            locked.put(o, new Long(now));**
**                            return o;**
**                     }**
**                     else{**
**                            unlocked.remove(o);**
**                            expire(o);**
**                            o = null;**
**                     }**
**              }**
**              }**
**       //****若到此为止还未找出可用对象，则创建新的对象实例**
**       o = create( );**
**       locked.put(o, new Long(now));**
**       return(o);**
}

另外，还需要一个线程类CleanUpThread：
public class CleanUpThread extends Thread {
**       private ObjectPool pool;**
**       //****执行清理工作的周期**
**       private long sleepTime;**

**       CleanUpThread(ObjectPool pool, long sleepTime){**
**              this.pool = pool;**
**              this.sleepTime = sleepTime;**
**       }**

**       public void run( ){**
**              while(true){**
**                     try{**
**                            sleep(sleepTime);**
**                     }catch(InterruptedException e){};**
**                     pool.cleanUp( );**
**              }**
**       }**
}

这样，我们只需在ObjectPool的构造函数中添加初始化清理收集器的代码即可：
ObjectPool(long time){
**       expirationTime = time;**
**       locked = new Hashtable();**
**       unlocked = new Hashtable();**

**       cleanT = new CleanUpThread(this, expirationTime);**
**       cleanT.setDaemon(true);**
**       cleanT.start();**
}
注意一点这里的CleanUpThread线呈应该设置为“守护线程”，这是因为在这个测试中我们希望当所有的用户线呈结束后，即蜂群完成最终任务时，统计出目前尚留在对象池中的对象数目，用之与BeeThread的总调用次数作对比，因此希望此时的清理线呈不再做任何清理工作。否则可能会因为它对清理工作的过分“负责”，让我们的试验的不到预想的效果。
经过测试证明，一些过期的蜜蜂对象确实在程序执行的过程中被消灭。这样就大大节省了内存的开销。

6****、程序探讨：
看完了整个程序，可能不少人会对ObjectPool的validate（）方法耿耿于怀。对象是否有效实际上是取决于外部的调用进程对使对象状态发生的变化。例如，对象池的一种典型应用是维护数据库连接对象（当然，这个对象相对于“小”蜜蜂来说“大”得许多，这里只是为了举例方便），如果外部进行关闭了曾经调用的数据库连接（这也证明了其不再有用），并将其返还给对象池，下次再有其他进程要求对象池分配一个数据库连接对象的时候调用checkOut（）方法检查到刚才那个数据库连接已经关闭，为“不可用”的。实际上由checkOut（）方法对其管理、判断、删除使得我们的对象池的整体性能受到了影响。我们为什么不将这个判断删除过程交给外部进程去做而非要“多管闲事”呢？
实际上，这正是一个矛盾所在。如果交由外部进程判断处理，会减轻“对象池”的管理成本，我们在checkOut（）方法中不必再遍历unlocked队列，因为我们可以保证只要unlocked中有对象，就一定是“有效”的。但是这么做却破坏了程序的封装性。比如如果外部进程将从对象池中借出的对象判定为失效并将其销毁，就不得不通知对象池将其从locked队列中删除，由此看来一个销毁对象的功能模块跨越了外部进程和对象池本身两个实体，它们之间的同步通信会带来棘手的问题，而且这其中的开销也许更大（假设在网络环境下）。