条件变量

用于协调想要访问共享资源的那些线程的

当共享资源的状态发生变化时 可以被用来通知被互斥锁阻塞的线程

条件变量的优势 效率方面的提升

初始条件离不开互斥锁 方法有的也是基于互斥锁

• 等待通知 wait
• 单发通知 signal
• 广播通知 broadcast

• go 语言的类型推断 可以带来哪些好处？

主要体现在代码重构上

• 变量的重声明是什么意思？

  短变量声明 通过使用 可以对同一个代码块中的变量进行重声明

sync 包 同步

用通讯的方式共享数据 通过共享数据的方式 传递信息和协调线程运行的做法更加主流

竞态条件 会破坏共享数据的一致性

没有协调线程的写入操作 难以发现和定位 排查的成本很高

避免多个线程在同一个时刻操作同一个数据块 另一个是协调多个线程 以避免在同一个时刻执行同一个代码块

多个并行运行的线程对这个共享资源的访问是完全串行的 临界区

Mutex 互斥量

互斥锁当作是针对某一个临界区的唯一访问令牌

致命错误 是无法被恢复的 recover 起不到作用

python 使用numpy的做法

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

import numpy as np

"""
    使用numpy的做法
    
"""


def fib_matrix(n):
    res = pow((np.matrix([[1, 1], [1, 0]])), n) * np.matrix([[1], [0]])
    return res[0][0]


for i in range(10):
    print(int(fib_matrix(i)), end=' ')

### 2
# 使用矩阵计算斐波那契数列
def Fibonacci_Matrix_tool(n):
    Matrix = np.matrix("1 1;1 0")
    # 返回是matrix类型
    return pow(Matrix, n)  # pow函数速度快于 使用双星好 **

def Fibonacci_Matrix(n):
    result_list = []
    for i in range(0, n):
        result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
    return result_list
# 调用
# Fibonacci_Matrix(10)

标准库的做法

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
31
32
33
34
35
36
37
38
39

# encoding=utf-8

from functools import reduce


"""
   标准库的做法
"""


class Solution(object):
    # 矩阵相乘
    def mul(self, a, b):
        r = [[0, 0], [0, 0]]
        r[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
        r[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
        r[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
        r[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]
        return r

    # 递归加速计算斐波那契数列 O(n^2) -> O(logn)
    def helper(self, n):
        if n == 0:
            return [[1, 0], [0, 1]]
        if n == 1:
            return [[1, 1], [1, 0]]
        if n&1 == 0 :
            return self.mul(self.helper(n/2), self.helper(n/2))
        else:
            return reduce(self.mul,[self.helper((n-1)/ 2),self.helper((n-1)/ 2),[[1, 1], [1, 0]]])
        
    def fib(self, N):
        return self.helper(N-1)[0][0]


if __name__ == "__main__":
    for i in range(1, 11):
        print(i-1, Solution().fib(i))

多线程

Python多线程机制是在GIL(Global Interpreter Lock)全局解释锁的基础上建立的。

要支持多线程的话，一个基本的要求就是不同线程对共享资源访问的互斥，所以Python中引入了GIL，当然这是第一个原因。

Python中的GIL是一个非常霸道的互斥实现，在一个线程拥有了解释器的访问权之后，其它的所有线程都必须等待它释放解释器的访问权，即使这些线程的下一条指令并不会互相影响。

这样的说法也就意味着，无论如何，在同一时间，只能有一个线程能访问Python提供的API。因为单处理器的本质是不可能并行的，这里的同一时间确实对于单处理器是毫无意义的，但是对于多处理器，同一时间，确实可以有多个时间独立运行。然而正是由于GIL限制了这样的情形，使得多处理器最终退化为单处理器，性能大打折扣。那么，为什么还要使用GIL呢？这里就要提到第二个原因。

当然，Python社区也早都认识到了这个问题，并且在不断探索，Greg Stein和Mark Hammond两位老兄曾经创建过一份去除GIL的branch，但是很不幸，这个分支在很多的基准测试中，尤其是在单线程的测试上，效率只有使用GIL的一半左右。

使用GIL时，保护机制的粒度比较大，也就是我们似乎只需要将可能被多个线程共享的资源保护起来即可，对于不会被多个线程共享的资源，完全可以不用保护。但是，如果使用更细粒度的锁机制进行保护，那么，会导致大量的加锁和解锁功能，加锁和解锁对于操作系统来说，是一个比较重量级的动作，同时，没有GIL的保护，编写Python的扩展模块的难度也大大增加。

所以，目前为止，GIL仍然是多线程机制的基石。

对于Python而言，字节码解释器是Python的核心所在，所以Python通过GIL来互斥不同线程对解释器的使用。这里举个例子进行说明：

假设，现在有三个线程A、B和C，它们都需要解释器来执行字节码，进行对应的计算，那么在这之前，它们必须获得GIL。那么现在假设线程A获得了GIL，其它线程只能等A释放GIL之后，才能获得。

对！是这样没错，于是，有两个问题：

1. 线程A何时释放GIL呢（如果A使用完解释器之后才释放GIL，那么，并行的计算退化为串行，多线程的意义何在？）

2. 线程B和C谁将在A释放GIL之后获得GIL呢？

所以毫无疑问的，Python拥有其自己的一套线程调度机制。

和操作系统的进程调度一样，线程调度机制主要解决两个问题：

1. 在何时挂起当前线程，选择处于等待状态的下一个线程？

2. 在众多处于等待状态的线程中，应该选择激活哪个线程？

对于何时进行线程调度的问题，是由Python自身决定的。我们可以联想操作系统进行进程切换的问题，当一个进程执行了一段时间之后，发生了时钟中断，于是操作系统响应时钟中断，并在这时开始进程的调度。

与此类似，Python中通过软件模拟了这样的中断，来激活线程的调度。Python的字节码解释器是按照指令的顺序一条一条的顺序执行从而工作的，Python内部维护着这样一个数值，作为Python内部的时钟，假设这个值为N，那么Python将在执行了N条指令之后立刻启动线程调度机制。

也就是说，当一个线程获得GIL后，Python内部的监测机制就开始启动，当这个线程执行了N条指令后，Python解释器将强制挂起当前线程，开始切换到下一个处于等待状态的线程。

下一个问题，Python会在众多等待的线程中选择哪一个呢？

答案是，不知道。因为这个问题是交给了底层的操作系统来解决的，Python借用了底层操作系统所提供的线程调度机制来决定下一个获得GIL进入解释器的线程是谁。

所以说，Python中的线程实际上就是操作系统所支持的原生线程。

Python中多线程常用的两个模块：Thread和在其之上的threading。其中Thread是使用C实现的，而Threading是用python实现。

首先从创建线程说起，在threadmodule.c中，thread_PyThread_start_new_thread()函数通过三个主要的动作完成一个线程的创建：

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

//创建bootstate结构
boot = PyMem_NEW(struct bootstate, 1);
if (boot == NULL)
return PyErr_NoMemory();
boot->interp = PyThreadState_GET()->interp;
boot->func = func;
boot->args = args;
boot->keyw = keyw;
boot->tstate = _PyThreadState_Prealloc(boot->interp);
if (boot->tstate == NULL) {
PyMem_DEL(boot);
return PyErr_NoMemory();
}
Py_INCREF(func);
Py_INCREF(args);
Py_XINCREF(keyw);
// 初始化多线程环境
PyEval_InitThreads(); 
//创建线程
ident = PyThread_start_new_thread(t_bootstrap, (void*) boot);
if (ident == -1) {
PyErr_SetString(ThreadError, "can't start new thread");
Py_DECREF(func);
Py_DECREF(args);
Py_XDECREF(keyw);
PyThreadState_Clear(boot->tstate);
PyMem_DEL(boot);
return NULL;
}
return PyInt_FromLong(ident);

1. 创建并初始化bootstate结构boot，在boot中，将保存关于Python的一切信息（线程过程，线程过程参数等)。

2. 初始化Python的多线程环境。

3. 以boot为参数，创建操作系统的原生线程。

从以上代码可以看出，Python在刚启动时，并不支持多线程，也就是说，Python中支持多线程的数据结构以及GIL都是没有创建的。当然这是因为大多数的Python程序都不需要Python的支持。

在Python虚拟机启动时，多线程机制并没有被激活，它只支持单线程，一旦用户调用thread.start_new_thread，明确的告诉Python虚拟机需要创建新的线程，这时Python意识到用户需要多线程的支持，这个时候，Python虚拟机会自动建立多线程需要的数据结构、环境以及GIL。

建立多线程环境，主要就是创建GIL。那么GIL是如何实现的呢？
打开”python/ceval.c”：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

static PyThread_type_lock interpreter_lock = 0; /* This is the GIL */
static PyThread_type_lock pending_lock = 0; /* for pending calls */
static long main_thread = 0;

int
PyEval_ThreadsInitialized(void)
{
return interpreter_lock != 0;
}

void
PyEval_InitThreads(void)
{
if (interpreter_lock)
return;
interpreter_lock = PyThread_allocate_lock();
PyThread_acquire_lock(interpreter_lock, 1);
main_thread = PyThread_get_thread_ident();
}

在这段代码中，iterpreter_lock就是GIL。

无论创建多少个线程，Python建立多线程环境的动作只会执行一次。在创建GIL之前，Python会检查GIL是否已经被创建，如果是，则不再进行任何动作，否则，就会去创建这个GIL。

在上述代码中，我们可以看到，创建GIL使用的是Pythread_allocate_lock完成的，下面看看该函数的内部实现：

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

PyThread_type_lock
PyThread_allocate_lock(void)
{
PNRMUTEX aLock;

dprintf(("PyThread_allocate_lock called\n"));
if (!initialized)
PyThread_init_thread();

aLock = AllocNonRecursiveMutex() ;

dprintf(("%ld: PyThread_allocate_lock() -> %p\n", PyThread_get_thread_ident(), aLock));

return (PyThread_type_lock) aLock;
}

GIL中的owned是指示GIL是否可用的变量，它的值被初始化为-1，Python会检查这个值是否为1，如果是，则意味着GIL可用，必须将其置为0，当owned为0后，表示该GIL已经被一个线程占用，不可再用；同时，当一个线程开始等待GIL时，其owned就会被增加1；当一个线程最终释放GIL时，一定会将GIL的owned减1，这样，当所有需要GIL的线程都最终释放了GIL之后，owned将再次变为-1，意味着GIL再次变为可用。

python 内置了dict list等

Python中的的PyListObject是对列表的一个抽象，内置了插入、添加、删除等操作。不同List中存储的元素的个数会是不同的，所以PyListObject是一个变长对象。而PyListObject中支持插入删除等操作，可以在运行时动态地调整其所维护的内存和元素，所以它又是一个可变对象。

我们知道，用户选用list正是为了可以频繁的执行插入或删除等操作，如果是需要存多少就申请多大的内存，这种内存管理显然是低效的。那么Python内部是怎么实现的呢？这就与刚才所提到的allocated有关了，我们知道，在PyObject_VAE_HEAD中有一个ob_size，在PyListObject中，每一次需要申请内存时，总会申请一大块内存存，这时申请的总内存的大小记录记录在allocated中，而其中实际被使用了的内存的数量则记录在ob_size中。

在列表对象的实现文件listObject.c文件中，我们可以看到，Python对于创建一个列表，提供了唯一的一条途径，就是PyList_New（）

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
static int initialized = 0;
if (!initialized) {
Py_AtExit(show_alloc);
initialized = 1;
}
#endif

if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
//进行溢出检查
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);
//为PyListObject对象申请空间，使用到缓冲池技术
if (numfree) {
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
count_reuse++;
#endif
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
#ifdef SHOW_ALLOC_COUNT
count_alloc++;
#endif
}
//为PyListObject对象中维护的元素列表申请空间
if (size <= 0)
op->ob_item = NULL;
else {
op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
memset(op->ob_item, 0, nbytes);
}
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}

首先，进行溢出检查。接下来，就是List对象的创建了，Python中的list对象实际上是分为两部分的，一是PyListObject对象本身，二是PyListObject对象维护的元素列表，而这两块内存是通过ob_item建立联系的。

　　在创建PyListObject对象时，首先检查缓冲池中free_list是否有可用的对象，如果有，则直接使用，若没有可用对象，则通过PyObject_GC_New在系统堆中申请内存， 　　

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

int
PyList_SetItem(register PyObject *op, register Py_ssize_t i,
register PyObject *newitem)
{
register PyObject *olditem;
register PyObject **p;
if (!PyList_Check(op)) {
Py_XDECREF(newitem);
PyErr_BadInternalCall();
return -1;
}
//索引检查
if (i < 0 || i >= Py_SIZE(op)) {
Py_XDECREF(newitem);
PyErr_SetString(PyExc_IndexError,
"list assignment index out of range");
return -1;
}
//存放元素
p = ((PyListObject *)op) -> ob_item + i;
olditem = *p;
*p = newitem;
Py_XDECREF(olditem);
return 0;
}

在创建PyListObject对象时，会首先检查缓冲区中的free_lists中是否有可用的对象。
　　在创建一个新的的对象时，实际也是分为两部，首先创建PyListObject对象，然后创建PyListObject对象所维护的元素列表，与之对应，在销毁一个list时，销毁的过程也是分离的，首先销毁PyListObject所维护的元素列表，然后释放PyListObject对象自身。。
　　在删除PylsitObject对象自身时，Python会先检查我们开始提到的那个缓冲池free_list，查看其中缓存的PyListObject的数量是否已经满了，如果没有，就将待删除的PyListObject对象放到缓冲池中，以备后用。
　　因此，那个在Python启动时空荡荡的缓冲池原来都是被本应该死去的PyListObject对象给填充了，在以后需要创建新的PyListObject的时候，Python会首先唤醒这些对象，重新分配Pyobject*元素列表占用的内存，重新拥抱新的对象。
　　
　　
insert 追加元素性能极差 谨慎使用
append 常数级别
pop 从头部弹出也需要挪动整个列表
pop 从尾部弹出元素 常数级别

list 对象可以根据元素个数进行自动扩容

内部结构在头文件 include/listobject.h 当中

变长对象 包含变长对象公共头部 内部维护了一个动态数组

尾部增删可以快速完成 无需挪动其他元素

如果list对象内部数组已经用满 再添加元素的时候 需要进行扩容

由于内部数组扩容时，需要将列表元素从旧数组拷贝到新数组，时间复杂度为 O(N)，开销较大，需要尽量避免。为此， Python 在为内部数组扩容时，会预留一定裕量，一般是

1/8 左右。假设为长度为 1000 的列表对象扩容， Python 会预留大约 125 个空闲位置，分配一个长度 1125 的新数组。 也就是基数上增加0.125

由于扩容操作的存在， append 方法最坏情况下时间复杂度为

O(n) 。由于扩容操作不会频繁发生，将扩容操作时的元素拷贝开销平摊到多个 append 操作中，平均时间复杂度还是 O(1) 。

拷贝

浅拷贝 只是对列表对象进行浅拷贝 对信列表可变元素的修改对旧列表依然可见

拷贝的是元素对象的指针