高并发►协程

C语言中支持golang中的协程

C语言协程库实现说明

在C语言中一步一步实现一个完整的协程框架.

代码实现

1. 当前支持的功能概览

1.1 创建任意数量协程并在协程中yield

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
#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#include "gtest/gtest.h"

#include "coroutine.h"
#include "asyncio.h"

static int g_run_sums = 0;
static pthread_mutex_t g_lock = PTHREAD_MUTEX_INITIALIZER;

static void co(void *args)
{
    int num = *((int *)args);

    pthread_mutex_lock(&g_lock);
    g_run_sums += num;  // 每个协程分别递增全局变量
    pthread_mutex_unlock(&g_lock);

    printf("coroutine:%d begin...\r\n", num);
    coroutine_yield();
    printf("coroutine:%d ended...\r\n", num);
}

TEST(coroutine_create, three_cos_run_success) 
{
    int a = 1, b = 2, c = 3; //a, b, c三个协程依次对全局变量g_run_sums增加1,2,3
    coroutine_init();
    coroutine_create(co, (void*)&a);
    coroutine_create(co, (void*)&b);
    coroutine_create(co, (void*)&c);

    coroutine_loop();

    EXPECT_EQ(g_run_sums, 6); // 最终全局变量为6
}

1.2 创建2个协程,其中一个睡眠100ms

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
  
#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#include "gtest/gtest.h"

#include "coroutine.h"
#include "asyncio.h"

static int seq = 0;
static int co_seq[2] = {0};

static void co_sleep(void *args)
{
    printf("co sleep begin.\r\n");
    asyncio_sleep(100); // 调用asyncio api睡眠100ms.
    co_seq[seq++] = 100;
    printf("co sleep end.\r\n");
}

static void co_nosleep(void *args)
{
    printf("co no sleep begin.\r\n");
    co_seq[seq++] = 200; 
    printf("co no sleep end.\r\n");
}

TEST(coroutine_run, co_sleep) 
{
    coroutine_init();
    coroutine_create(co_sleep, NULL);
    coroutine_create(co_nosleep, NULL);

    coroutine_loop();

    EXPECT_EQ(co_seq[0], 200); //验证未睡眠协程先完成了执行
    EXPECT_EQ(co_seq[1], 100);
}

2. COROUTINE状态

corouting有3种状态, RUNNALBE, RUNNING, WAITING.

  • WAITING: corouting暂停并等待一些条件以继续运行.比如:sleep, 系统调用,同步操作(原子或锁操作),这种延迟是性能差的根源.
  • RUNNABLE: corouting具备运行条件正在等待分配processor以执行指令
  • RUNNING: corouting已经分配到processor,并正在上面执行指令

3. 调度器实现

  • processor_t: 管理一个实际的os线程,内部使用队列维护分配给它的coroutine,使用epoll进行事件循环.
  • processors_t: 全局processor_t管理器,创建时会按照实际的cpu个数创建对应的processor_t, 它负责将新协程按照一定算法分配给某个processor_t.
    同时负责检测没有任何协程时退出进程.

3.1 主进程何时退出

当没有任何协程存在时,则退出主进程.

3.1.1 实现原理

模拟实现了Golang中的waitGroup, 用于等待所有协程退出.新协程创建会调用waitGroup_add,协程结束会调用waitGroup_del,当waitGroup空闲时
则说明所有协程都已经退出.

3.2 processor_t调度主循环处理

    1. 循环遍历coroutine就绪队列,依次运行coroutine.
    1. 如果没有就绪的coroutine且本地队列上coroutine个数为0,则进行步骤3,否则进行步骤4
    1. 通过条件变量等待分配新的coroutine,如果收到了条件变量且是退出指令,则进行步骤5,否则进行步骤1.
    1. 本地队列还有coroutine,但是coroutine都在等待事件,则进行事件循环以等待指定事件的到来,这样就会有coroutine就绪,进行步骤1.
    1. 退出主循环

3.3 上下文切换实现

3.3.1 原理

corouting在用户态进行上下文切换,上下文主要包括:堆栈,寄存器(IP, SP等).
上下文切换主要通过<ucontext.h>中定义的getcontext, setcontext, makecontext, swapcontext实现.

3.3.2 上下文切换时机

  • corouting主动调用coroutine_yield(),如果有其它待运行的coroutine则主动让出processor_t
  • 协程中调用了协程库asyncio API,则由API选择合适的时机进行上下文切换,如调用阻塞API,如corouting_sleep.
  • 如果你在协程中执行cpu密集型操作或直接调用阻塞的C api,那么会影响当前processor的调度和运行.

3.3.3 堆栈使用

  • 每个processor_t维护1M的堆栈空间M
  • 协程刚创建时为RUNNABLE状态,此时直接使用M作为堆栈,当协程需要放权时保存当前堆栈到协程自己的空间M0
  • 协程恢复运行时,将保存的堆栈M0还原到M中继续运行

这样每个协程最大都可以有1M的堆栈空间,且堆栈空间能够按需分配,每个processor_t上堆栈的消耗为所有协程
实际使用的堆栈内存+1M.

如果不这样实现,每个协程都需要初始分配1M空间,消耗为协程个数*1M.

4. 异步操作协程库asyncio实现

  • asyncio提供一系列api用于在协程环境中编写并发代码.
  • asyncio是coroutine框架提供的api可以用于实现高性能网络服务器,数据库连接库,分布式任务队列等.
  • asyncio适合IO密集型和高级别的结构化网络程序

4.1 当前支持的API

  • coroutine_sleep(long delay_ms): 当前协程休眠指定ms.
  • coroutine_yield(): 当前协程主动放权给其它就绪协程,由调度器选择合适时机再重新调度.

5. 代码说明

5.1 编译代码

1
2
3

cmake -H. -Bbuild
cmake --build ./build

5.2 运行测试

1
2
cd build
ctest --verbose
工作状态

记一次惨痛的编程考试经历

一次惨痛的编程考试经历

最近一个月,一直在刷leetcode来准备公司的上机编程考试,平均每天刷３道题左右,主要是中等题型,偶尔也刷困难题.
按照题目的类型在刷,如分治,递归回溯,二叉树,dfs,bfs,dp,前缀和这些.自以为准备的很充分,结果还是挂了.
心中的郁闷可想而知,俗话说,”大痛者必有大志”,从成长型思维来看,还是很有必要总结一下失败的经验的.
先来回顾一下考试题目:
1.一道系统设计题目,主要考查如何组织代码实现不同的排序策略,整体上比较简单,也做出来了
2.一道深度优先遍历题目,本来以为能轻松做出,可是没有ＡＣ,也一直没有想出原因,也因此而挂了
3.二维前缀和+合并区间,只想到了用二维前缀和,后面合并区间没有优化,造成超时

其中第２题还一直怀疑用例有问题,一直没有发现代码中的bug.直到几天后,才发现问题.代码其实仔细推敲就会发现不符合题目要求,没有考虑清楚　　
叶子节点的情形.

总结了下失利原因有以下几点:

  1. 准备考试要首先搞清楚考的是什么?算法一般不会考太难的,重点还是在于有没有好的编程习惯.编程习惯包括如何审题分析线索,如何设计用例,如何调试,如何熟练的使用语言等.
  2. 体会到了测试驱动开发的重要性,如何根据题目设计有效的用例和考虑清楚所有边界条件.
  3. 之前刷题只注重有没有解题思路和题目的难度上,用例不过也是直接看失败用例,造成思维逻辑有漏洞
  4. 完全没有练习如何对照题目的限制条件设计用例,如何调试代码验证符合预期,一味地追求刷题数量,忽略了本质.
  5. 做题不纯粹是速度,更重要的是准确,如果代码有bug和没有代码是一样的.
自我修养►数据结构与算法

分治法

分治法

常见算法

  1. 归并排序
  2. 快速排序
  3. 求N的N次方的最后一位数字
  4. 求数组的逆序度

Leetcode真题

  1. 查找第k大元素
  2. 查找两个有序数组的中位数
  3. 给表达式添加运算符
自我修养►数据结构与算法

求N的N次方的最后一位数字 

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

def get_last(N):
    return N%10

def last_number(N, n):
    if n == 0:
        return 1

    if n == 1:
        return get_last(N)

    s = last_number(N, n//2) 
    if n % 2 == 0:
        return get_last(s*s)

    return get_last(s*s*get_last(N))

if __name__ == "__main__":
    print(last_number(3, 3))
    print(last_number(4, 4))
    print(last_number(1, 0))
    print(last_number(0, 1))

自我修养►数据结构与算法

归并排序 

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

def merge_sort(a):
    def merge_array(a, i, j):
        if i >= j:
            return a

        def merge(a, left_i, left_j, right_i, right_j):
            new_a = []
            i, j = left_i, right_i
            while i <= left_j and j <= right_j:
                if a[i] <= a[j]:
                    pos = i
                    i += 1
                else:
                    pos = j
                    j += 1
                new_a.append(a[pos])

            if i <= left_j:
                new_a.extend(a[i:left_j+1])

            if right_i <= right_j:
                new_a.extend(a[j:right_j+1])

            a[left_i:right_j+1] = new_a

        mid = i + (j - i) // 2 
        merge_array(a, i, mid)
        merge_array(a, mid+1, j)
        merge(a, i, mid, mid+1, j)
        return a

    return merge_array(a, 0, len(a)-1)

if __name__ == "__main__":
    print(merge_sort([1, 3, 2, 4, 6, 8, 7]))
    print(merge_sort([8]))
    print(merge_sort([9, 8, 7, 4, 3, 2, 0]))
    print(merge_sort([9, 10, 12, 14, 13, 22, 100]))
自我修养►数据结构与算法

查找第k大元素 

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

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p215 file
Author: zhangxiaoan 00565442
Create: 2021/4/30 16:19
"""

def top_k(nums, k):
    def partition(nums, left, right):
        if left >= right:
            return 1

        sel = nums[right]
        pos = left-1
        start = left
        while start < right:
            if nums[start] > sel:
                pos += 1
                if start != pos:
                    tmp = nums[pos]
                    nums[pos] = nums[start]
                    nums[start] = tmp
            start += 1
        pos += 1
        nums[pos], nums[right] = sel, nums[pos]
        return pos - left + 1

    def quick_find(nums, left, right, k):
        m = partition(nums, left, right)
        if m == k:
            return nums[left + m - 1]

        if m > k:
            return quick_find(nums, left, left + m - 2, k)
        else:
            return quick_find(nums, left + m, right, k - m)
    return quick_find(nums, 0, len(nums)-1, k)

if __name__ == "__main__":
    print(top_k([1], 1))
    print(top_k([3, 1, 2, 4], 2))
    print(top_k([3, 2, 1, 5, 6, 4], 2))
    print(top_k([5, 2, 4, 1, 3, 6, 0], 4))
自我修养►数据结构与算法

给表达式添加运算符 

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
56
57
58
59
60
61
62
63
64
65
66
67
68
"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p282 file
Author: zhangxiaoan 00565442
Create: 2021/4/29 9:25
"""


def add_operators(num, target):
    n = len(num)
    ans = []

    def gen_expr(num, index, expr, prev_op, prev_value, value):
        nonlocal n, target, ans

        start = num[index]
        end = index
        while end < n:
            val = int(num[index:end + 1])
            expr.append(prev_op)
            expr.append(num[index:end + 1])


            if prev_op == '+':
                next_val = value + val
            if prev_op == '-':
                next_val = value - val
            if prev_op == '*':
                next_val = value + prev_value * val
                
            if end == n - 1:
                if next_val == target:
                    ans.append("".join(expr[1:]))
                
                expr.pop()
                expr.pop()
                return

            if prev_op == '+':
                gen_expr(num, end + 1, expr, "*", val, value)
            elif prev_op == '-':
                gen_expr(num, end + 1, expr, "*", -val, value)
            else:
                gen_expr(num, end + 1, expr, "*", prev_value * val, value)


            gen_expr(num, end + 1, expr, "+", 0, next_val)
            gen_expr(num, end + 1, expr, "-", 0, next_val)
            expr.pop()
            expr.pop()

            if start == '0':
                break

            end += 1

    gen_expr(num, 0, [], "+", 0, 0)
    return ans


if __name__ == "__main__":
    print(add_operators("123", 6))
    print(add_operators("232", 8))
    print(add_operators("105", 5))
    print(add_operators("00", 0))
    print(add_operators("3456237490", 9191))
    print(add_operators("134562379", 134562379))
    print(add_operators("123456789", 45))
自我修养►数据结构与算法

查找两个有序数组的中位数 


def find_media_sorted_arrays(nums1, nums2):
    m, n = len(nums1), len(nums2)

    def find_kth(nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        if m < n:
            return find_kth(nums2, nums1, k)

        if n == 0:
            return nums1[k-1] 

        if k == 1:
            return min(nums1[0], nums2[0])

        m2 = min(n, (k+1)//2)
        m1 = k - m2
        if nums1[m1-1] < nums2[m2-1]:
            return find_kth(nums1[m1:], nums2, k - m1)
        else:
            return find_kth(nums1, nums2[m2:], k - m2)
        

    total = m + n
    if total % 2 != 0:
        return find_kth(nums1, nums2, total//2 + 1)
    else:
        return (find_kth(nums1, nums2, total//2) + find_kth(nums1, nums2, total//2 + 1))/2

    
if __name__ == "__main__":
    print(find_media_sorted_arrays([1, 3], [2]))
    print(find_media_sorted_arrays([1, 2], [3, 4]))
自我修养►数据结构与算法

求数组的逆序度 

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

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p_offer_51 file
Author: zhangxiaoan 00565442
Create: 2021/4/28 17:38
"""
def merge_reverse(nums, i, j):
    if j < i:
        return [], 0

    if i == j:
        return nums[i:i+1], 0

    mid = i + (j-i)//2
    left, left_num = merge_reverse(nums, i, mid)
    right, right_num = merge_reverse(nums, mid+1, j)

    new_nums, reverse = [], 0
    n_left, n_right = len(left), len(right)
    n_i, n_j = 0, 0
    while n_i < n_left and n_j < n_right:
        if left[n_i] <= right[n_j]:
            new_nums.append(left[n_i])
            n_i += 1
        else:
            new_nums.append(right[n_j])
            reverse += n_left - n_i
            n_j += 1

    new_nums.extend(left[n_i:])
    new_nums.extend(right[n_j:])

    return new_nums, reverse + left_num + right_num


def reversePairs(nums):
    return merge_reverse(nums, 0, len(nums)-1)[1]

if __name__ == "__main__":
    print(reversePairs([7, 5, 6, 4]))
    print(reversePairs([1, 3, 2, 3, 1]))
自我修养►数据结构与算法

快速排序 

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

def quick_sort(a):
    def quick_sort_array(a, i, j):
        if i >= j:
            return a

        def partition(a, i, j):
            pos = i
            while i < j:
                if a[i] < a[j]:
                    if i != pos:
                        a[pos], a[i] = a[i], a[pos]
                    pos += 1
                i += 1
            a[pos], a[j] = a[j], a[pos]
            return pos


        k = partition(a, i, j)
        quick_sort_array(a, i, k-1)
        quick_sort_array(a, k+1, j)
        return a
    
    return quick_sort_array(a, 0, len(a)-1)
        
if __name__ == "__main__":
    print(quick_sort([1, 3, 2, 4, 5, 8, 7, 0]))
    print(quick_sort([1]))
    print(quick_sort([]))
    print(quick_sort([9, 8, 7, 3, 2, 0]))
    print(quick_sort([9, 18, 27, 33, 42, 50]))