引言

Those who cannot remember the past are condemned to repeat it.
动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：自顶向下的备忘录法和自底向上。

小试牛刀-杠条切割问题

上图节选自算法导论。

经典朴素递归

1
2
3
4
5
6
7
8
9
10
11
12
13

int CutRod(const int *rodLen2Price, int curRodLen) {
    if (curRodLen == 0) {
        return 0;
    }
    int q = -1;
    for (int i = 1; i <=curRodLen; ++curRodLen) {
        int tmp = rodLen2Price[i] + CutRod(rodLen2Price, curRodLen-i);
        q = q < tmp ? tmp : q;
    }
    return q;
}

自顶向下递归实现的CutRod效率很差，原因在于CutRod反复地用相同的参数值对自身进行递归调用，即它反复求解相同的子问题。而且由于递归调用次数太多会栈溢出。

动态规划-自顶向下

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

int MemorizedCutRodAux(const int *rodLen2Price, int curRodLen, int *optimalRodTotalMoney) {
    cout << "调用MemorizedCutRodAux"<< endl;
    if (optimalRodTotalMoney[curRodLen] >= 0) {
        return optimalRodTotalMoney[curRodLen];
    }
    int q = -1;
    if (curRodLen == 0) {
        q = 0;
    } else {
        for (int i = 1; i <=curRodLen ; ++i) {
            int tmp = rodLen2Price[i] + MemorizedCutRodAux(rodLen2Price, curRodLen-i, optimalRodTotalMoney);
            q = (q < tmp ? tmp : q);
        }
    }
    optimalRodTotalMoney[curRodLen] = q;
    return q;
}
int MemorizedCutRod(const int *rodLen2Price, int curRodLen) {
    int * optimalRodTotalMoney = new int[curRodLen + 1];
    for (int i = 0; i <= curRodLen; ++i) {
        optimalRodTotalMoney[i] = -1;
    }
    return MemorizedCutRodAux(rodLen2Price, curRodLen, optimalRodTotalMoney);
}

此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。

动态规划-自底向上

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

void BUCutRod(const int *rodLen2Price, int curRodLen, int * optimalRodTotalMoney, int *optimalSolution) {
    optimalRodTotalMoney[0] = 0;
    for (int i = 1; i <=curRodLen; ++i) {
        int q = -1;
        for(int j = 1; j <= i; ++j) {
            int tmp = rodLen2Price[j] + optimalRodTotalMoney[i-j];
            if (q < tmp) {
                q = tmp;
                optimalSolution[i] = j;
            }
        }
        optimalRodTotalMoney[i] = q;
    }
}
void PrintBUCutRod(const int *rodLen2Price, int curRodLen, int * optimalRodTotalMoney, int *optimalSolution) {
    BUCutRod(rodLen2Price, curRodLen, optimalRodTotalMoney, optimalSolution);
    cout << "长度为" << curRodLen << "的杠条最大收益为:" << optimalRodTotalMoney[curRodLen] << endl;
    cout << "最优方案的杠条长度分别为:";
    while (curRodLen != 0) {
        cout << optimalSolution[curRodLen] << " ";
        curRodLen -= optimalSolution[curRodLen];
    }
    cout << endl;
}

恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此，我们可以将子问题按照规模顺序，由小至大顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。
由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂度函数通常具有更小的系数。

转自这里

转自这里

原子操作

Linux 中最简单的同步方法就是原子操作。原子 意味着临界段被包含在 API 函数中。不需要额外的锁定，因为 API 函数已经包含了锁定。由于 C 不能实现原子操作，因此 Linux 依靠底层架构来提供这项功能。各种底层架构存在很大差异，因此原子函数的实现方法也各不相同。一些方法完全通过汇编语言来实现，而另一些方法依靠 c 语言并且使用 local_irq_save 和 local_irq_restore 禁用中断。
当需要保护的数据非常简单时，例如一个计数器，原子运算符是种理想的方法。尽管原理简单，原子 API 提供了许多针对不同情形的运算符。

锁

信号量

信号量的本质也是一个计数器，用来记录对某个资源（如共享内存）的存取状况。用来协调不同进程间的数据对象，最主要的应用是共享内存方式的进程间通信。
Linux2.6.26下定义的信号量结构体：

1
2
3
4
5

struct semaphore {
	spinlock_t                lock;
    unsigned int             count;
	struct list_head        wait_list;
};

互斥锁

两种形式的制约关系

间接相互制约关系（互斥）

若某一进程要求使用某种资源，而该资源正好被另一进程使用，并且该资源不允许两个进程同时使用，那么该进程只好等待已占有的资源的进程释放资源后再使用。这种制约关系可以用“进程-资源-进程”的形式表示。例如，打印机资源，进程互斥经典问题中生产者-生产者问题。

直接相互制约关系（同步）

某一进程若收不到另一进程提供的必要信息就不能继续运行下去，表明了两个进程之间在某些点上要交换信息，相互交流运行情况。这种制约关系的进本形式是“进程-进程”。例如生产者与消费者问题，生产者生产产品并放入缓冲池，消费者从缓冲池取走产品进行消费。这两者就是同步关系。

区分互斥和同步只需记住，同类进程即为互斥关系，不同类进程即为同步关系。
临界资源：同时只允许一个进程使用的资源。
临界区：进程中用于访问临界资源的代码段，又称临界段。
每个进程的临界区代码可以不同，临界区代码由于要访问临界资源，因此要在进入临界区之前进行检查，至于每个进程对临界资源进行怎样的操作，这和临界资源及互斥同步管理是无关的。
Linux 2.6.26中mutex的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct mutex {
	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
	atomic_t                  count;//原子操作类型变量
	spinlock_t                wait_lock;//自旋锁类型变量
	struct list_head          wait_list;
#ifdef CONFIG_DEBUG_MUTEXES
	struct thread_info        *owner;
	const char                *name;
	void                      *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map         dep_map;
#endif
};

自旋锁

自旋锁也是实现保护共享资源的一种锁机制，与互斥锁比较类似，都是为了解决对某资源的互斥使用。无论是互斥锁还是自旋锁，在任何时刻最多只有一个保持者。也就是说，任何时刻最多只有一个执行单元获得锁。两者的不同之处是，对于互斥锁而言，如果资源已经被占用，其它的资源申请进程只能进入sleep状态。但是自旋锁不会引起调用者sleep，如果自旋锁已经被别的执行单元保持，调用者就一直循环在等待该自旋锁的保持者是否释放该锁。

自旋锁一般原理

跟互斥锁一样，一个执行单元要想访问被自旋锁保护的共享资源，必须先得到锁，在访问完共享资源后，必须释放锁。如果在获取自旋锁时，没有任何执行单元保持该锁，那么将立即得到锁；如果在获取自旋锁时锁已经有保持者，那么获取锁操作将自旋在那里，直到该自旋锁的保持者释放了锁。由此我们可以看出，自旋锁是一种比较低级的保护数据结构或代码片段的原始方式，这种锁可能存在两个问题：死锁和过多占用cpu资源。

自旋锁适用情况

自旋锁比较适用于锁使用者保持锁时间比较短的情况，正是由于自旋锁使用者一般保持较短的锁时间，因此选择自选而不是睡眠是非常必要的，因为自旋锁的效率远高于互斥锁。信号量和读写信号量适用于保持时间较长的情况，它们会导致调用者sleep，因此只能在进程上下文使用。而自旋锁适合于保持时间非常短的情况，它可以再任何上下文使用。如果被保护的共享资源只在进程上下文访问，使用信号量保护该共享资源非常合适，如果对共享资源的访问时间非常短，自旋锁也可以。但是如果被保护的共享资源需要在中断上下文访问（包括底半部即中断处理句柄和顶半部即软中断），就必须使用自旋锁。自旋锁保持期间是抢占失效的，而信号量和读写信号量保持期间是可以被抢占的。自旋锁只有在内核可抢占或SMP（多处理器）的情况下才真正需要，在单CPU且不可抢占的内核下，自旋锁的所有操作都是空操作。另外格外注意一点：自旋锁不能递归使用。

互斥锁和信号量与自旋锁的区别

信号量。互斥锁允许进程sleep属于睡眠锁，自旋锁不允许调用者sleep，而是让其循环等待

总结

在硬件层面，CPU提供了原子操作、关中断、锁内存总线的机制；OS基于这几个CPU硬件机制，就能够实现锁；再基于锁，就能够实现各种各样的同步机制（信号量等等）。
原子锁不仅提供了一种锁定机制，同时也提供了算术或 bitwise 操作。

转自这里
有时候有些纠结啊。觉得底层的东西太多，太麻烦，想专注上层开发;偏偏又对底层实现好奇而且有时候不知道底层实现又一头雾水。
嗯，顺其自然吧。。。。。

package main

import “fmt”

type Base struct {
Name string
Age int
}

func (b * Base) Test() {
fmt.Println(“test successfully”)
}

type Child struct {
Base // 匿名字段， 默认把Base的所有字段都继承过来了。 这样看起来才像真正的继承
Age int
}

func main() {
c := new(Child)
c.Name = “hello” // 可以直接使用Base中的字段
c.Age = 20 // 如果有重复的， 则最外的优先

fmt.Println(c.Name)     // hello
fmt.Println(c.Age)      // 20
fmt.Println(c.Base.Age) // 要访问Base中的，可以这样写 0
c.Test()

}
go语言中的”继承“并不是真正的意义上的继承，确切地说是组合。匿名字段让习惯了C++/java之类的程序员用go更加得心应手。
作为一门年轻的语言，不得不说go语言对程序员还是非常友好的.