C#写快速排序

时间:2022-02-03 16:00:43

C#写快速排序

一 . 运行时数据区

程序计数器是线程私有的,是一块很小的内存空间,是当前线程执行到字节码行号的计数指示器。每个CPU处理器核心 在任何一个时刻,都只可能运行着唯一的一个线程,执行着一条指令。所以在多线程的应用中,线程不断切换和分配时间片。在线程切换来切换去的过程中,就是靠程序计数器来了解,该如果继续恢复运行该线程。

    虚拟机栈和Native方法栈也是线程私有的。在Sun HotSpot虚拟机中虚拟机栈和Native方法栈是被合二为一的。虚拟机栈描述的是Java方法执行的内存模型,栈帧用于存储局部变量表,方法出口等信息。每一个方法调用到执行完成都对应着一个栈帧在虚拟机栈中的入栈和出栈的过程。局部变量表中存放了八种基本数据类型和对象引用,还有returnAddress类型。前两种不难理解,returnAddress实际上是指向一条字节码指令的地址,局部变量表所需的内存空间在编译期间完成分配,当进入某个方法时,需要在栈帧中分配多大的局部空间是完全确定的,方法运行期间是不会改变局部变量表的大小。本地方法栈和虚拟机栈作用相似,虚拟机栈执行我们的java方法,本地方法栈就是执行Native方法,所以就是Native方法栈。简单地讲,一个Native Method就是一个java调用非java代码的接口。

Java堆是所有线程共享的区域,虚拟机管理的内存中最大的一块。基础所有对象的实例都是在这里分配内存。Java堆是GC的主要回收对象,虚拟机栈上局部变狼表所存的对象引用,就是指向堆内存中的一块地址。详细内容后面垃圾回收会提到更多。

    方法区也是一块所有线程共享的区域,这里存储虚拟机加载的类信息,常量,静态变量,JIT编译后的代码等数据。运行时常量池是方法区的一部分。

接下来要说到JVM GC机制,在垃圾回收中堆内存上移动对象位置是很常见的, 所以对象的访问方式也要顺便提一下,也可以展示下方法区的类型是如何被引用的。我们都知道栈上的局部变量表中,有存储reference数据的引用,它可能是对象的直接地址,也可能是句柄地址。

C#写快速排序C#写快速排序

由于对象访问极其频繁,所以Hot Spot也使用第二种方式,直接存实例引用是效率比较高的。但是第一种句柄的方式,好处在于,垃圾回收中,不需要更改栈上所存储的地址,栈上的存储稳定,只需要修改句柄池。

二.垃圾回收GC

说到垃圾回收 ,就不得不说垃圾回收算法的思想, 说到回收算法, 又不得不想到,什么样的对象需要被回收?什么是存活对象,什么对象已死亡。判断对象的存活与死亡,通常有两种方法,引用计数法和可达性分析算法。引用计数算法的问题在于,无法解决两个对象间相互引用的问题,导致不得达的对象依然无法回收。下面是实例: 

A.b=B ;    //这里 B 引用计数+1   A对象在堆上   其属性b存着B的引用
B.a=A ; // 与上方同理
A=null;
B=null; //A B两对象栈上引用 给null AB堆上实例做到不可达
//此时导致 AB对象实例内存不会被回收

所以为了解决这个问题,Java虚拟机中 使用可达性分析算法。其思想是从可作为GC Root根结点的对象,向下搜索,搜索过的路成为引用链,凡事不能达到的对象,认为是可回收对象。有几种对象可以作为GC Root对象。

1. 虚拟机栈上(栈帧的本地变量表)引用的对象。   2. 方法区中类静态属性引用的对象。    3. 方法区中常量引用的对象      4.  本地方法栈上Native方法引用的对象。

试想一下,为什么这些对象可以作为GC Root,为什么其他对象无法作为GC Root。  比如你的一个接口,处理请求的时候,有很多线程本地变量 , 但是 处理完请求后,这些对象就都没用了,所以他们一般不能作为GC Root。什么时候本地变量会成为GC Root呢?  个人的猜测应该是在GC大面积回收,程序暂停的时候, 这个时候,不能把当前正在运行的数据和变量清理掉呀。这时候提升为GC Root是很恰当的我觉得。至于静态属性,常量什么的作为GC Root毋庸置疑了,他们本来生命周期就是整个应用程序生命周期。

    如何判断对象存活与死亡说过了,还需要了解的就是垃圾回收算法 。有四种思想需要提到, 其中有一种最基本的叫做 标记-清除算法。另外很重要的复制算法,是年轻代最合适的。还有一种标记整理算法,是老年代最合适的。最后一种就是分代这个思想。

    标记清除就是首先对所有需要回收的对象进行标记,最后统一进行清除。这样的做法效率不高,清理后内存碎片很多,可能导致后期大对象无法分配内存,会经常触发另一次垃圾回收。

    复制算法的思想是,将内存分为两块,其中一块保持为空,回收的时候,将存活的对象复制到空的一块,复制完成后,对原来那半内存全部清理。但是java虚拟机并不能留出一半的内存,这样太浪费资源,并且在Java堆中,年轻代里绝大部分内存都是要被回收的。所以Hot Spot中,将年轻代分为8:1:1的Eden,Survivor  * 2, 就是一块Eden , 两块Survivor。  所以年轻代的策略,优先使用大的Eden,必须保持一块Survivor为空。回收的时候,将存活的对象,复制到空的Survivor内存区域,清理Eden和刚才使用的Survivor。

如果Survivor放不下存活的对象了,和时候 就该有对象进入老年代了~     老年代使用标记—整理算法。标记整理思路就是,先标记,然后在回收的时候,将存活的对象移动到一端,将被清理的移动到另一端。然后清理端边界意外的内存。