月度归档:2011年09月

JVM运行时数据区

当一个Java程序要启动时,操作系统会启动一个Java虚拟机(JVM)的实例来运行这个java程序。每个Java程序的运行总有一个JVM在支撑着它。

一个JVM的运行时数据区结构大致如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
                  +---------------+
  class文件 ----> |类装载器子系统 |
                  +---------------+
                      |        |
 +-------------------------------------------+
 |   ______   ______   ______   ________     |
 |  |      | |      | |      | |        |    |
 |  |方法区| |  堆  | |Java栈| |PC寄存器|    |
 |  |______| |______| |______| |________|    |
 |                  运行时数据区             |
 +-------------------------------------------+
                      |        |
                  +------------------+
                  |    执行引擎      |
                  +------------------+

图1 JVM运行时数据区
(Download ASCII Picture)

首先,JVM会将编译后的.class文件通过类装载子系统进行装载、连接和初始化。它会分析这个装载的类,并把类中不同的代码块按规则在内存中分配好。图中的运行时数据区就是由JVM管理的Java程序所使用的内存区域,也是我今天想要理清的内容。它的各部分功能介绍如下:

1、方法区
方法区中存储的是一个类的类型信息,包括public、private、protected等限定信息,以及当前类及其父类的全限定(路径)名等。此外,方法区中还存储着一个类的静态变量、实例变量、常量池、方法信息等。
2、堆
堆中存储的是Java程序中用关键字new出来的对象和数组。这部分内存的回收是由JVM的GC(Garbage Collection)来完成,堆中的对象可被当前程序的所有线程所共享。存在堆中的对象都有一个指向方法区中该对象所属类型的指针,这样才方便与运行时去执行该对象的方法。依据JVM的具体实现,方法区与堆可以在同一片内存区域,JVM会管理彼此之间的边界。
3、Java栈
Java栈中存储的是方法的局部变量和对堆中对象的引用,每个Java线程都会在这个Java栈中有一个属于自己的方法调用栈,栈中的内容以栈帧为单位进行存储,每个栈顶栈帧代表着一个线程当前正在执行的方法。
4、PC寄存器
PC寄存器其实不是寄存器,JVM中没有寄存器,它只是功能类似于PC寄存器,用于指示下一条执行代码的位置所在。每个线程都在这个PC寄存器中有一个属于自己的PC寄存器。

以一个实例说明Java程序运行过程中运行时数据区的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 衔山的博客 - http://fengchj.com
 * Copyright (c) 2011 All Rights Reserved.
 */
package cn.edu.zju.jvm;
 
/**
 * @author 衔山
 * @version $Id: JvmDataSegTest.java, v 0.1 2011-9-27 下午08:48:26
 */
class Demo {
    public static int static_var = 1;
    public String     non_static_var;
 
    public Demo(String var) {
        this.non_static_var = var;
    }
 
    public void echo() {
        System.out.println(non_static_var);
    }
}
 
public class JvmDataSegTest {
 
    public static void main(String[] args) {
        Demo demo = new Demo("hello world!");
        demo.echo();
    }
}

这里先略去PC寄存器,也不考虑多线程,因此,Java栈中仅存储着main方法所在的主线程的调用栈。运行Demo demo = new Demo("hello world!")语句后,运行时数据区的当前状态如下图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 +-----------------------------------------------------------------------------+
 |   ______________________________   ________________   ____________________  |
 |  |方法区                        | |堆              | |Java栈              | |
 |  |                              | |                | |                    | |
 |  | +--JvmDataSegTest类型信息--+ | | +------------+ | | +----------------+ | |
 |  | |      main()方法          | | | |  Demo实例  | | | | 指向Demo的引用 | | |
 |  | |    "hello world!"        | | | +------------+ | | +----------------+ | |
 |  | |        ……              | | |                | |                    | |
 |  | +--------------------------+ | |                | |                    | |
 |  |                              | |                | |                    | |
 |  | +-------Demo类型信息-------+ | |                | |                    | |
 |  | |      static_var=1        | | |                | |                    | |
 |  | |      non_static_var      | | |                | |                    | |
 |  | |        echo()方法        | | |                | |                    | |
 |  | |          ……            | | |                | |                    | |
 |  | +--------------------------+ | |                | |                    | |
 |  |______________________________| |________________| |____________________| | 
 |                                                                             |
 |                               运行时数据区                                  |
 +-----------------------------------------------------------------------------+

图2 测试程序的运行时数据区布局
(Download ASCII Picture)

从上图中应该可以很直观的看到这个运行时数据区的布局了。Demo类的类型信息和JvmDataSegTest类的类型信息都存在方法区中,其中还包括Demo类的静态变量(static_var)和实例变量(non_static_var)。main()方法中用于构造Demo类的字符串"hello world!"也是存储在方法区的常量池中。main()方法中new出来的Demo对象存储在堆中。此时的Java栈中,栈顶应该是主线程的main()方法栈帧,里面存着一个引用demo,它指向堆中的Demo对象。当main()方法执行到demo.echo()语句时,JVM先从栈中的demo引用出发,找到位于堆中的Demo实例,然后从这个Demo实例中找到echo()方法的引用,继而定位到方法区中Demo类型信息部分,从中获取echo()方法的字节码,执行echo()方法的指令。

Reference:
[1] Bill Venners 著, 曹晓钢 蒋靖 译. 深入Java虚拟机[M]. 机械工业出版社. 2003-09.

--EOF--

Java多线程的一些知识

今天零零碎碎地看了很多Java多线程的基础知识,感觉还是有点乱,在这里再整理一下。

Java的线程有两种生成方式:
1、继承Thread类
2、实现Runnable接口
用他们创建线程的方式分别为:

1
2
3
4
5
6
7
8
9
10
11
12
13
//方式一
class MyThread extends Thread{
    void run(){}
}
Thread thread = new MyThread();
thread.start();
 
//方式二
class MyThread implements Runnable{
    void run(){}
}
Thread thread = new Thread(new MyThread());
thread.start();

这两种方法都需要重写(@override)run()方法,线程要实现怎样的功能都些在这个run()方法里。线程的启动是调用其start()方法,当初有个疑问,start()方法是Thread类中的方法,对于第一种继承Thread类来创建的线程没什么问题,但是对于通过实现Runnable接口来创建的线程,它哪来的start()方法呢?因为Runnable接口中只包含一个run()方法。现在了解,其实这个start()方法还是来自于Thread类,因为即使是第二种创建线程的方法,也是通过向Thread类的构造方法传递实现了Runnable接口的实例这样的途径来实现的。

一个线程的整个生命周期分成新建、就绪、运行、阻塞和死亡5个状态。线程对象在调用start()方法之前属于新建状态,除了CPU之外所有条件均满足时属于就绪状态,CPU在执行线程的run()方法时属于运行状态,当线程在等待资源或者其他被阻塞的情况时属于阻塞状态,当run()方法执行结束后线程属于死亡状态。其中阻塞状态又可以分为三类情况:
1、锁池。
2、等待池。
3、其他阻塞状态
对于上述的第1点和第2点,要先知道对象的锁池和等待池。每个对象都有一个锁池和等待池,用于存放等待状态中的线程。假如当前对象O的一个锁被Thread A得到,那么Thread B也运行到这个同步(synchronized)方法或同步快时,因为得不到锁,就会被JVM放到对象O的锁池中,当Thread A释放锁以后,JVM再从锁池中随机取出一个线程,让它得到锁,并执行同步代码。被放入对象等待池中的线程是这样的情况:线程在同步代码中执行了对象的wait()方法,那么线程在释放锁(wait()方法只能在synchronized块中执行,由于要有权限执行同步块代码,前提是有锁,因此这个点上该线程肯定占有锁)的同时,也被JVM放入对象的等待池中,直到有另外线程发出notify()或notifyAll()通知,或者wait()超时,该线程才会被JVM放入对象的锁池中,剩下的流程就跟锁池一样了。第3点其他阻塞状态包括线程调用sleep()方法,或者在其他线程上面调用了join()方法,或者要进行I/O等。

Java多线程下进行同步主要采用synchronized来约束,synchronized可以用来修饰方法(这个方法可以是静态的),也可以用来修饰一个代码块。当用来修饰代码块时,必须为synchronized提供一个锁标记,表示线程要执行这个代码块中的代码必须先竞争锁。当一个线程在执行某个对象的同步代码时,并不能阻止其他线程执行这个对象的非同步代码,因此,要留意各个方法对共享资源的竞争。此外,一个对象方法的synchronized特性不会被继承。

--EOF--

Servlet的继承体系和生命周期

Servlet的继承体系分为4个层次,由上到下分别为:
1、javax.servlet.Servlet
2、java.servlet.GenericServlet
3、javax.servlet.http.HttpServlet
4、用户自定义的Servlet

Servlet是个接口,它包含了5个方法:init()、service()、destroy()、getServletConfig()和getServletInfo(),其中前三个方法是用于Servlet生命周期管理的方法。GenericServlet类是一个抽象类,它实现了Servlet接口中的方法,并且新增了自己的一些方法。HttpServlet也是一个抽象类,它实现了HTTP特性的service()方法,并且新增了几种处理特定HTTP请求的抽象方法,如doPost()、doGet()、doDelete()等等。这样的设计是为了方便用户专注于业务逻辑的编写,比如用户Servlet中只需覆盖HttpServlet中用得到的几种doXxx服务方法即可(至少需覆盖一种),而如何将当前请求映射为相应的doXxx方法则交给了HttpServlet的service()方法。此外,用户如果需要,也可以重写GenericServlet类中已实现的init()方法和destroy()方法。

Servlet的生命周期由容器(Servlet Container)来管理,当第一个浏览器请求到来时,容器调用init()方法来实例化这个Servlet类。init()方法在Servlet的整个生命周期中只被调用一次。当容器实例化了一个Servlet之后,会针对每一次用户请求运行一个线程,再在该线程中调用Servlet的service()方法,因此,Servlet也会面临多线程的安全问题,解决方案无非是加锁、避免用实例变量等。Servlet的生命周期会随着容器调用destroy()方法而结束,它同init()方法一样,整个生命周期中只会被调用一次。当所有调用service()方法的线程都退出时,或者超过了某个时间阈值后,容器就会调用destroy()方法结束这个Serlvet实例。

Reference:
[1] Bryan Basham, etc. Head First Servlet & JSP(中文版). 中国电力出版社. 2007.09.

--EOF--

二叉树根据前序中序得到后序序列

根据二叉树的前序和中序序列,能求得它的后序序列,同样道理,根据中序和后序序列,能求得它的前序序列。但是根据前序和后序序列,无法求得它的中序序列,因为单凭前序和后序序列无法唯一确定一颗二叉树。

以下是根据二叉树的前序和中序序列求其后序序列的算法思想和实现。
关于二叉树的题,最先想到的总是递归。根据二叉树的前序、中序和后序定义,可以找出规律:
1、前序序列的第一个元素肯定是根节点。
2、中序序列中,根节点左边的序列都属于左子树,根节点右边的序列都属于右子树。如此一来,中序序列都划分成三个部分:左子树节点集合、根节点、右子树节点集合。
3、根据中序的三个部分,前序的序列也可以划分成:根节点、左子树节点集合、右子树节点集合。
4、分别对前序和中序序列中的左子树节点集合和右子树节点集合重复步骤1~3。
5、根据后序定义,当左右子树处理完毕后,最后才输出根节点。

对于某前序序列(1245673),中序序列(4265713),根据以上步骤,首先,用根节点1将中序序列分成三个部分(42657-1-3),同时,这样一来,前序序列也可以分成三部分了(1-24567-3),然后分别对子序列(24567)和(3)重复以上步骤,最后输出根节点1。over~~

C++程序实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 *根据二叉树的前序、中序序列得到其后序遍历序列
 *preorder:前序序列 inorder:中序序列 len:序列长度
 */
void process(char* preorder, char* inorder, int len)
{
    int i;
    //当前层次为不再包含元素,退出递归
    if (len <= 0) {
        return;
    }
    //得到当前层次root节点(前序0号元素)在中序的位置
    for(i=0; inorder[i]!=preorder[0]; i++); 
    //递归处理左子树
    process(preorder+1, inorder, i);
    //递归处理右子树
    process(preorder+i+1, inorder+i+1, len-i-1);
    //打印根节点root。
    cout << preorder[0];
}

根据中序和后序序列求前序序列也一样道理,C++实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *根据二叉树的中序、后序序列得到其前序遍历序列
 *inorder:中序序列 postorder:后序序列 len:序列长度
 */
void process2(char*inorder, char* postorder, int len)
{
    int i;
    if(len <= 0){
        return;
    }
 
    for (i = 0; inorder[i]!=postorder[len-1]; i++);
    cout << postorder[len-1];
    process2(inorder, postorder, i);
    process2(inorder+i+1, postorder+i, len-i-1);
}

测试程序见附件: 源代码

--EOF--

二叉树遍历的非递归实现

二叉树的定义是递归的,因此要遍历二叉树,用递归方法最为简便和直观,但是,二叉树的遍历也可以用非递归方法实现。

 一、非递归前序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 前序遍历二叉树  非递归法
 * @param root
 */
public static void preOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            System.out.print(root.getValue());
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            root = root.getrChild();
        }
    }
}
 二、非递归中序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 中序遍历二叉树  非递归法
 * @param root
 */
public static void inOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            System.out.print(root.getValue());
            root = root.getrChild();
        }
    }
}
 三、非递归后序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 后序遍历二叉树  非递归法
 * @param root
 */
public static void postOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.peek();
            if (root.getTag() == false) {
                root.setTag(true);
                root = root.getrChild();
            } else {
                System.out.print(root.getValue());
                s.pop();
                root = null;
            }
        }
    }
}

非递归的后序遍历与前两者有些不同,它需要在二叉树的定义中加入一个tag标签,初始为false,只有当一个节点的右孩子已经遍历过之后,才将它置为true,表示下次可以访问它并输出值了。

附件提供的源代码是二叉树前序、中序、后序遍历的递归和非递归算法,以及一个层序遍历的Java实现:源代码

--EOF--