Nimble scheduler

发表于 更新于 分类于 阅读次数： 评论数：

Nimble controller 的Scheduler是由一个32K的timer来驱动的，一个tick是30.52us，完全执行在timer的isr里，所以timer callback里要做的事情不能太耗时（超过一个tick），否则scheduler就不准确了，如下为scheduler的主函数：

1
2
/* Initialize cputimer for the scheduler */
   os_cputime_timer_init(&g_ble_ll_sched_timer, ble_ll_sched_run, NULL);

时间单位

  • Tick：由clock决定，对于32K clock来说，一个tick就是 1000000us/（32*1024） = 30.52us.
  • Slot：1250个毫秒
  • Period：N * Slot，N是可配置的
  • Epoch：M * Period，M是可配置的
    Scheduler在调度的时候，有时要将Connection event放在Period的边界，scanning/initiating/advertising是尽可能发生在没有被用到的Period内。
    1
    2
    3
    /* Time per BLE scheduler slot */
    #define BLE_LL_SCHED_USECS_PER_SLOT         (1250)
    #define BLE_LL_SCHED_32KHZ_TICKS_PER_SLOT   (41)    /* 1 tick = 30.517 usecs */

调度单位

每一个可被调度的单位叫做Sched item, 这些item放在FIFO的List中，每当timer到期后Scheduler就从List里拉一个出来做执行。
每一个item有如下几个属性：

  1. schedule type，类型
  2. enquened，是否入Q，入Q就代表是Ready，等待被执行
  3. remainder，剩余的执行时间
  4. start_time, 开始执行时间
  5. end_time, 结束执行时间
  6. cb_args, item执行函数的参数
  7. sched_cb, item被调度到的时候的执行函数
    如下是相关的code segment 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    struct ble_ll_sched_item
    {
        uint8_t         sched_type;
        uint8_t         enqueued;
        uint8_t         remainder;
        uint32_t        start_time;
        uint32_t        end_time;
        void            *cb_arg;
        sched_cb_func   sched_cb;
        TAILQ_ENTRY(ble_ll_sched_item) link;
    };

    /* Types of scheduler events */
    #define BLE_LL_SCHED_TYPE_ADV       (1)
    #define BLE_LL_SCHED_TYPE_SCAN      (2)
    #define BLE_LL_SCHED_TYPE_CONN      (3)
    #define BLE_LL_SCHED_TYPE_AUX_SCAN  (4)
    #define BLE_LL_SCHED_TYPE_DTM       (5)
    #define BLE_LL_SCHED_TYPE_PERIODIC  (6)
    #define BLE_LL_SCHED_TYPE_SYNC      (7)

调度原则

  1. Sched item之间没有优先级的关系，完全按照Sched item的start_time为序，一个一个的执行。
  2. 调度到某个item时就直接执行这个item的sched_cb，并将这个item从调度列表上删掉，callback执行完后，再起timer，等待下一个item的start_time到期。
  3. item在插入到调度列表的时候就已经排好序了。
  4. 在插入新的Adv Sched item的时候，新的Adv要避开每一个跟他有overlap的item，直到找到一个完全跟它没有overlap的位置，这意味着在有同样的start time的情况下，先入list的优先级高。
    • 以插入一个Adv Schedule为例，假如Scheduler的ReadyList里有4个item，它们的排列如下。那么下图中绿色的item就是可以直接插入的item，而红色的item则需要一直往后移动，一直移到一个能插入>的地方，也许到list最后才能有它的一席之地。
    • 在一个adv event执行完成后，需要再计算下一个adv event起来的时间，请参考下图。
      Item中的Delay（0～10ms）指的是这个adv event最大允许delay的时间。
  5. 但是对于type为CONN的Sched是有点优先级的
    • 正在execute的type为CONN的Sched的优先级最高，要新建立的conn的sched (ble_ll_sched_slave_new())如果刚好跟正在execute的conn overlap，那直接就取消新的这个conn。
      1
      2
      3
      4
      5
      /* The schedule item must occur after current running item (if any) */
        if (ble_ll_sched_overlaps_current(sch)) {
            OS_EXIT_CRITICAL(sr);
            return rc;
        }
  • 在收到CONN_IND的时候，为了能尽快在windowOffset到达时发包出去回应对方，会将跟他overlap的type为CONN的sched 给盖掉
  • 但这包如果type是其他的type，则会继续往后shift找合适的位置，但如果是回应CONN_IND的第一包的话，不在规定时间发包出去，link就建立不起来，这里还是有点问题。
    1
    2
    3
    4
    5
    6
    if (ble_ll_sched_is_overlap(sch, entry)) {
        /* If we overlap with a connection, we re-schedule */
        if (ble_ll_sched_conn_overlap(entry)) {
            break;
        }
    }

更正 #4

感谢jaydenh215的指导，上图中关于Adv reschedule的图例欠妥，正确的符合code行为的插入Sched的示意图如下。

如果超过了max_delay,那插入也是失败的，如下图，虽然在#3的前面有位置给sch插入，但是因为overdue了，所以插入会失败。