内存布局

首先，要先搞清楚垃圾回收回收的是什么？这要从进程的内存布局讲起。

上图是linux中的进程内存布局，其中：

• Stack是栈内存，存放函数出入参以及局部变量
• Head是堆内存，和数据结构中的堆没有关系，用于存放动态创建的对象
• Bss是静态内存分配，用于存放程序中未初始化的全局变量
• Data用于存放一些常量数据，程序中已经初始化的全局变量就存放在这
• Test用于存放程序代码

进程的栈内存是为函数准备的，函数调用完了之后就被释放，不需要程序GC，而堆内存是程序运行过程中动态申请的空间用于存放动态创建的对象，这个才是GC的对象。

GC的类型

各种语言GC的类型有2种：

1. 手动GC，比如C/C++
2. 自动GC，比如PHP、GO

手动GC的优点是可以由开发者控制内存的分配和销毁，GC更精确，不需要系统处理，效率高，但是由于程序的复杂性，容易出现指针悬挂和内存泄露的问题

自动GC则简化了开发者对内存的操作，可以由系统更好地管理内存，可以进行预分配，使用内存吃，不会产生内存碎片，但缺点也很明显，增加了系统的负担，降低系统的性能

自动GC的方案

主流的自动GC方案有2种：

1. 引用计数
2. 标记删除

PHP采用的就是引用计数的方案，而GO则采用了标记删除的方案

Go的GC

Go的标记删除GC方案称为三色标记法，具体步骤是：

1. 所有的对象初始都是白色
2. 从根对象开始，将找到的根对象都标记为灰色
3. 遍历灰色对象，将灰色对象引用的对象标记为灰色，将自身标记为黑色
4. 继续第3步，直到所有可达的对象都标记为黑色
5. 白色的对象即为不可达对象，被视为垃圾，是回收的对象

由于GC和代码逻辑是并行的，在GC过程中，代码逻辑会破坏当前标记好的引用关系，比如当前某条引用路径是黑-》灰-〉白，代码将灰色对象对白色对象的引用赋值给了黑色对象，导致灰色与白色的引用断开，黑色对象直接引用白色对象，而按照三色标记法，是不会直接检测黑色对象的引用的，导致无法找到这个白色对象，最终当作垃圾处理

所以Go的GC有一个在GC过程中暂停所有程序逻辑运行的机制：STW（stop the world），但是这样会导致GC的时候系统出现性能波动。

我们来分析下，不采用STW的会导致对象丢失的两个条件：

1. 白色对象被黑色对象引用
2. 灰色对象与白色对象的引用关系被破坏

如果可以解决这两个问题，则可以不需要STW，有两个方案可以采用：

1. 强不变式：不允许黑色对象引用白色对象
2. 弱不变式：黑色对象可以引用白色对象，但是白色对象必须直接或间接被灰色对象引用

GO语言对上述方案的两种实现：

1. 插入写屏障

   
   将一个对象引用另一个对象时，将另一个对象标记为灰色
   

2. 删除写屏障

   
   当一个白色对象被另一个对象解除引用解除时，被引用对象被标记为黑色
   
   

GO使用了两者混合的模式：

1. GC刚开始的时候，会将栈上的可达对象全部标记为黑色。
2. GC期间，任何在栈上新创建的对象，均为黑色。将栈上的可达对象全部标黑，最后无需对栈进行STW，就可以保证栈上的对象不会丢失
3. 堆上被删除的对象标记为灰色
4. 堆上新添加的对象标记为灰色

Go 的GC优化历程

1. go 1.3 之前采用标记清除法，需要STW
2. go 1.5 采用三色标记法，插入写屏障机制（只在堆内存中生效），最后仍需对栈内存进行STW
3. go 1.8 采用混合写屏障机制，屏障限制只在堆内存中生效。避免了最后节点对栈进行STW的问题，提升了GC效率

题目

已有函数 rand13() ⽣成从 1 到 13 均匀分布的随机整数。请使⽤这⼀函数实现 rand5() ⽣成
⼀个从 1 到 5 均匀分布的随机整数。反之，如已有 rand5()，请据此实现 rand13()

解答

rand13 生成1～13的随机数，每个随机数出现的概率相等，即1～5出现的概率相等，即只获取1～5的随机数等同于rand5

for {
    v := rand13()
    if v <= 5 {
    break
    }
}

rand5 生成1～5的随机数，也可生成[5,10,15,20,25] 的随机数，即5*rand5，[1-5]与[5,10,15,20,25]的组合为[1,2,3,4,5,6,7,8,9,10,10,11,12,13,14,15,15,16,17,18,19,10,20,21,22,23,24,25,25,26,27,28,29,30]，其中重复了[10,15,20,25]，考虑将[10,15,20,25]转为[9,14,19,24]，去除了重复值，随机数范围为[129]，获取其中[113]部分

//[1,2,3,4,5] + [4,9,14,19,24]
for {
    v := rand5() + 5 * (rand5()-1)
    if v <= 13 {
        break
    }
}

题目：

请根据以下框架代码，编写函数 perm() ，打印输⼊字符串的所有排列。即对于字符串
ABC ，打印输出以下内容，不需要按照特定顺序。
ABC
ACB
BAC
BCA
CBA
CAB

框架代码：

package main
import "fmt"
// Perm() 对 a 形成的每⼀排列调⽤ f().
func Perm(a []rune, f func([]rune)) {
perm(a, f, 0) }
// 对索引 i 从 0 到 len(a) - 1，实现递归函数 perm().
func perm(a []rune, f func([]rune), i int) {
// TODO
}
func main() {
Perm([]rune("ABC"), func(a []rune) {
 fmt.Println(string(a)) }) }

实现：

package main

import "fmt"

// Perm() 对 a 形成的每⼀排列调⽤ f().
func Perm(a []rune, f func([]rune)) {
    perm(a, f, 0)
}

// 对索引 i 从 0 到 len(a) - 1，实现递归函数 perm().
func perm(a []rune, f func([]rune), i int) {
    alen := len(a)
    if i == alen {
        f(a)
        return
    }
    aMap := make(map[rune]struct{})
    for index := i; index < alen; index++ {
        //去重
        if _, ok := aMap[a[index]]; ok {
            continue
        }
        aMap[a[index]] = struct{}{}
        swap(a, index, i)
        //求i+1 从 len(a) - 1的全排列
        perm(a, f, i+1)
        swap(a, index, i)
    }
}

func swap(b []rune, i int, j int) {
    if i == j || b[j] == b[i] {
        return
    }
    tmp := b[j]
    b[j] = b[i]
    b[i] = tmp
}

func main() {
    Perm([]rune("ABC"), func(a []rune) {
        fmt.Println(string(a))
    })
}