04-21 19:13 电子科技大学算法工程师发布于四川

关注

Boost库中fibers协程的调度策略

第一章前情提要

这一篇文章是在源码分析完fibers协程的调用原理这篇文章之后，再进一步分析fibers协程的调度策略，前一文章的链接：Boost库对于fibers协程源码的个人理解在boost库中fibers协程的调度策略有三种，分别是1）round_robin（轮询），2）shared_work（共享调度策略），3）work_stealing（调度队列窃取策略），接下来就详细介绍一下这三种策略，只是从怎么进入调度队列和怎么出调度队列来分析这三种策略，协程怎么切换已经在上一篇文章中说过

第二章 round_robin（轮询策略）

1、单线程

通过boost::fibers::fiber构造每一个协程的时候，都会在堆上构造出一个work_context的上下文，在fiebr的最终构造函数中，通过make_worker_context_with_properties构造完impl_对象之后，worker_context就已经构造完成，然后就是进入start_函数中，在此函数中第一步就是获取当前线程正在活跃的上下文，在这个时候还没有活跃的上下文，因此就会构造一个main_context作为当前活跃的上下文，它不会像fiber对象一样在堆上构造一个空间，它的上下文入口地址就是当前普通栈的上下文，在构造完main_context之后，会在堆上构造出dispatcher_context上下文，同时把构造好的dispatcher_context上下文加入到round_robin轮询策略的就绪队列的末尾，然后把worker_context上下文也加入到就绪队列的末尾，接着就是把main_context放到协程的等待队列中，就可以开始调度协程，先是调度dispatcher_context上下文，然后切换到worker_context上下文，同时把dispatcher_context上下文放到就绪队列的末尾，最后如果worker_context执行完成，就会把他的等待队列上的main_context放到就绪队列的末尾

alt

2、单线程调度示意图

以以下代码作一个策略调用示意图

boost::fibers::fiber f1([]() {
        std::cout << "fiber 1 start" << std::endl;
        boost::this_fiber::yield();
        std::cout << "fiber 1 end" << std::endl;
    });
    boost::fibers::fiber f2([]() {
        for (int i = 0; i < 2; ++i) {
            std::cout << "fiber 2 start" << std::endl;
            boost::this_fiber::yield();
            std::cout << "fiber 2 end" << std::endl;
        }
    });
    f1.join();
    f2.join();

2.1、初始的策略调度队列

挂在worker_context等待队列上的main_context是同一个对象

alt

2.2、切换到f1协程

是由dispatcher_context切换到f1协程的，切换之后会把dispatcher_context放到就绪队列最后

alt

2.3、调度f1协程

因为f1协程中间调用boost::this_fiber::yield();切换

alt

2.4、调度f2协程

同f1一样，切换之后就会回到初始的状态，然后再次循环

alt

2.5、f1协程执行完

由dispatcher_context切换到f1协程，f1协程恢复现场，然后f1协程执行完成，就不会再次把f1的worker_context放回就绪队列中，只会把它的等待队列中的main_context放到就绪队列的末尾

alt

2.6、main_context的作用

接着就是轮询切换，当切换到main_context之后，main_context执行完成，相当于f1.join()代码执行完成，然后就是f2.join()执行，如此轮询下去直到所有的worker_context执行完成

3、多线程

对于round_robin轮询策略多线程和单线程没有任何区别，就是每个线程都有自己的轮询就绪队列线程之间互不影响

第三章 shared_work（共享调度策略）

1、思想

共享调度策略指的是，多个线程共享同一个工作就绪队列，而同时也拥有自己的私有队列，用于存放main_context和dispatcher_context两种上下文指针，共享工作就绪队列使用的是类中static实现的

2、源码分析

2.1、放入队列源码分析

首先判断是不是pinned_context，pinned_context包含main_context和dispatcher_context两种，如果包含这两种中的任意一种就把这个上下文放入到线程私有的队列lqueue中，如果不包含那就证明是worker_context，就要放入共享的就绪队列rqueue，放入之前要调用detach()函数，目的是去除和该上下文绑定的协程调度器，因为线程都会有自己私有的协程调度器，在共享队列中的协程并不知道自己接下来是会被哪个线程上的协程调度器调度

alt

2.2、取出协程源码分析

加锁，因为多线程共享工作就绪队列，所以会存在多个线程同时取共享就绪队列中去取，首先判断共享工作就绪队列是不是空，不是空就还有协程需要调度执行，就从共享队列中取出，然后调用attach()函数，因为加入的时候去除了协程和调度器的绑定关系，现在需要调度执行，则需要重新绑定关系，如果共享工作就绪队列为空表明没有协程需要调度，就去自己私有的队列中调度main_context或者dispatcher_context

alt

3、示意图

std::vector<std::thread> threads;
  const int num_threads = 2;
  const int tasks_per_thread = 1;

  for (int i = 0; i < num_threads; ++i) {
    threads.emplace_back([i, tasks_per_thread] {
      std::vector<boost::fibers::fiber> fibers;
      boost::fibers::use_scheduling_algorithm<boost::fibers::algo::shared_work>();
      fibers.emplace_back(1, task, j + i * (tasks_per_thread + 1));
      for (auto& f : fibers) {
        f.join();
      }
    });
  }

  for (auto& t : threads) {
    t.join();
  }

3.1、初始化队列示意图

alt

3.2、协程调度示意图

worker_context（f1）和worker_context（f2）被线程1还是线程2调度是不确定的，关键是看哪个线程抢到锁，现在假设worker_context（f1）一直是被线程1在调度执行，worker_context（f2）一直是被线程2在调度执行

alt

3.3、协程执行过程中切换示意图

线程各自执行协程，在执行过程去切换，但是发现共享就绪队列是空的，就会调用自己上的私有队列，就是调用dispatcher_context，在切换到dispatcher_context上下文的时候，同时会把worker_context放入到共享队列（因为协程还没有执行完成），由dispatcher_context切换到worker_context的时候，同时会把dispatcher_context放入到线程各自的私有调度队列，此时又回到了协程调度的初始示意图那样

alt

3.4、协程执行结束

线程又再次去共享队列中拿取worker_context进行执行，执行完worker_context，因为此时协程执行完成，首先要把挂载worker_context等待队列中的main_context放入到线程各自私有的队列中，然后去共享队列中找是否还有worker_context，如果没有就调用私有队列，也就是dispatcher_context，由dispatcher_context去调度切换到main_context执行，同时dispatcher_context入私有队列，main_context执行完成之后，就会返回到用户写的join，执行之后的代码，如果后面没有join了，结束当前所在的函数调用之前，会进行析构，在析构的过程中会释放内存，包括上下文，协程调度器，以及dispatcher_context上下文（本上下文是个死循环，所以需要设置一个标志位来辅助他跳出死循环，析构的时候就会设置这个标志位）

alt

第四章 work_stealing（工作窃取策略）

1、思想

每个线程都有各自私有的就绪队列，队列中存放所有类型的上下文，包括worker_context、dispatcher_context以及main_context，每个线程有各自的协程调度器，调度器有各自就绪队列句柄，所以有一个多线程共享的全局数据结构，用来存每个线程的调度器指针，使用vector来存取的

2、源码分析

2.1、放入队列源码分析

首先判断当前要入就绪队列的上下文是什么类型的上下文，如果是worker_context上下文，那么久就需要去除和调度器的绑定关系，因为它可能会被其他线程窃取，然后就入队列，本策略的就绪队列是一个循环队列，使用双“指针”，一个指向队头，一个指向队尾，不是真正的指针而是下标，当队列满的时候会以两倍的速度进行扩充

alt

2.2、队列取出源码分析

首先线程从自己的就绪队列中弹出一个，如果有可以调度的上下文，如果是worker_context就把它和当前线程的调度器进行绑定，prefetch_range这个函数只是一个在堆上预取的，用于告诉向上多少个字节（有个默认值）是接下来很快会要取到的；如果没有可调度的上下文就要去其他线程的就绪队列中盗取，随机在其他线程的就绪队列中找，找到之后然后和当前线程的调度器绑定

alt

3、示意图

std::vector<std::thread> threads;
  const int num_threads = 2;
  const int tasks_per_thread = 2;

  for (int i = 0; i < num_threads; ++i) {
    threads.emplace_back([i, tasks_per_thread, num_threads]() {
      std::vector<boost::fibers::fiber> fibers;
      boost::fibers::use_scheduling_algorithm<boost::fibers::algo::work_stealing>(num_threads);
      for (int j = 0; j < tasks_per_thread; ++j) {
        if (i == 0) {
          fibers.emplace_back(1, task, j + i * (tasks_per_thread + 1));
          break;
        } else
          fibers.emplace_back(2, task1, j + i * (tasks_per_thread + 1));
      }
      for (auto& f : fibers) {
        f.join();
      }
    });
  }

  for (auto& t : threads) {
    t.join();
  }