浅谈鸿蒙内核代码调度队列
为何单独讲调度队列？
鸿蒙内核代码中有两个源文件是关于队列的，一个是用于调度的队列，另一个是用于线程间通讯的ipc队列。
本文详细讲述调度队列，详见代码: kernel_liteos_a/kernel/base/sched/sched_sq/los_priqueue.c
ipc队列后续有专门的博文讲述，这两个队列的数据结构实现采用的都是双向循环链表，los_dl_list实在是太重要了，是理解鸿蒙内核的关键，说是最重要的代码一点也不为过，源码出现在 sched_sq模块，说明是用于任务的调度的，sched_sq模块只有两个文件，另一个los_sched.c就是调度代码。
涉及函数
功能分类 接口名 描述
创建队列 ospriqueueinit 创建了32个就绪队列
获取最高优先级队列 ospriqueuetop 查最高优先级任务
从头部入队列 ospriqueueenqueuehead 从头部插入某个就绪队列
从尾部入队列 ospriqueueenqueue 默认是从尾部插入某个就绪队列
出队列 ospriqueuedequeue 从最高优先级的就绪队列中删除
ospriqueueprocessdequeue 从进程队列中删除
ospriqueueprocesssize 用进程查队列中元素个数
ospriqueuesize 用任务查队列中元素个数
ostaskpriqueuetop 查最高优先级任务
osdequeemptyschedmap 进程出列
osgettoptask 获取被调度选择的task
鸿蒙内核进程和线程各有32个就绪队列，进程队列用全局变量存放，创建进程时入队，任务队列放在进程的threadpriqueuelist中。
映射张大爷的故事：就绪队列就是在外面排队的32个通道，按优先级0-31依次排好，张大爷的办公室有个牌子，类似打篮球的记分牌，一共32个，一字排开，队列里有人时对应的牌就是1，没有就是0 ，这样张大爷每次从0位开始看，看到的第一个1那就是最高优先级的那个人。办公室里的记分牌就是位图调度器。
位图调度器
//*kfy 0x80000000u = 10000000000000000000000000000000(32位,1是用于移位的，设计之精妙，点赞) #define priqueue_prior0_bit 0x80000000u #ifndef clz #define clz(value) (__clz(value)) //汇编指令 #endif lite_os_sec_bss los_dl_list *g_priqueuelist = null; //所有的队列 原始指针 lite_os_sec_bss uint32 g_priqueuebitmap; // 位图调度 // priority = clz(bitmap); // 获取最高优先级任务队列 调度位 整个los_priqueue.c就只有两个全部变量，一个是los_dl_list *g_priqueuelist是32个进程就绪队列的头指针，在就绪队列中会讲另一个uint32 g_priqueuebitmap 估计很多人会陌生，是一个32位的变量，叫位图调度器。怎么理解它呢？
鸿蒙系统的调度是抢占式的，task分成32个优先级，如何快速的知道哪个队列是空的，哪个队列里有任务需要一个标识，而且要极高效的实现？答案是:位图调度器。
简单说就是一个变量的位来标记对应队列中是否有任务，在位图调度下,任务优先级的值越小则代表具有越高的优先级，每当需要进行调度时,从最低位向最高位查找出第一个置 1 的位的所在位置,即为当前最高优先级,然后从对应优先级就绪队列获得相应的任务控制块,整个调度器的实现复杂度是 o(1),即无论任务多少,其调度时间是固定的。
进程就绪队列机制
cpu执行速度是很快的，其运算速度和内存的读写速度是数量级的差异，与硬盘的读写更是指数级。鸿蒙内核默认一个时间片是 10ms,资源很宝贵，它不断在众多任务中来回的切换，所以绝不能让cpu等待任务，cpu时间很宝贵，没准备好的任务不要放进来。这就是进程和线程就绪队列的机制，一共有32个任务就绪队列，因为线程的优先级是默认32个， 每个队列中放同等优先级的task.
队列初始化做了哪些工作？详细看代码
#define os_priority_queue_num 32 uint32 ospriqueueinit(void) { uint32 priority; /* system resident resource */ g_priqueuelist = (los_dl_list *)los_memalloc(m_aucsysmem0, (os_priority_queue_num * sizeof(los_dl_list))); if (g_priqueuelist == null) { return los_nok; } for (priority = 0; priority < os_priority_queue_num; ++priority) { los_listinit(&g_priqueuelist[priority]); } return los_ok; } 因task 有32个优先级，在初始化时内核一次性创建了32个双向循环链表，每种优先级都有一个队列来记录就绪状态的tasks的位置，g_priqueuelist分配的是一个连续的内存块，存放了32个los_dl_list，再看一下los_dl_list结构体，因为它太重要了！越简单越灵活
typedef struct los_dl_list { struct los_dl_list *pstprev; /**< current node's pointer to the previous node */ struct los_dl_list *pstnext; /**pstnext == null); if (los_listempty(&priqueuelist[priority])) { *bitmap |= priqueue_prior0_bit >> priority;//对应优先级位 置1 } los_listtailinsert(&priqueuelist[priority], priqueueitem); } void ospriqueueenqueuehead(los_dl_list *priqueuelist, uint32 *bitmap, los_dl_list *priqueueitem, uint32 priority) { /* * task control blocks are inited as zero. and when task is deleted, * and at the same time would be deleted from priority queue or * other lists, task pend node will restored as zero. */ los_assert(priqueueitem->pstnext == null); if (los_listempty(&priqueuelist[priority])) { *bitmap |= priqueue_prior0_bit >> priority;//对应优先级位 置1 } los_listheadinsert(&priqueuelist[priority], priqueueitem); } void ospriqueuedequeue(los_dl_list *priqueuelist, uint32 *bitmap, los_dl_list *priqueueitem) { lostaskcb *task = null; los_listdelete(priqueueitem); task = los_dl_list_entry(priqueueitem, lostaskcb, pendlist); if (los_listempty(&priqueuelist[task->priority])) { *bitmap &= ~(priqueue_prior0_bit >> task->priority);//队列空了，对应优先级位 置0 } } 同一个进程下的线程的优先级可以不一样吗？
请先想一下这个问题。
进程和线程是一对多的父子关系，内核调度的单元是任务(线程)，鸿蒙内核中任务和线程是一个东西，只是不同的身份。一个进程可以有多个线程，线程又有各自独立的状态，那进程状态该怎么界定？例如：processa有 taska(阻塞状态)，taskb(就绪状态) 两个线程，processa是属于阻塞状态还是就绪状态呢？
先看官方文档的说明后再看源码。
进程状态迁移说明：
init→ready：
进程创建或fork时，拿到该进程控制块后进入init状态，处于进程初始化阶段，当进程初始化完成将进程插入调度队列，此时进程进入就绪状态。
ready→running：
进程创建后进入就绪态，发生进程切换时，就绪列表中最高优先级的进程被执行，从而进入运行态。若此时该进程中已无其它线程处于就绪态，则该进程从就绪列表删除，只处于运行态；若此时该进程中还有其它线程处于就绪态，则该进程依旧在就绪队列，此时进程的就绪态和运行态共存。
running→pend：
进程内所有的线程均处于阻塞态时，进程在最后一个线程转为阻塞态时，同步进入阻塞态，然后发生进程切换。
pend→ready / pend→running：
阻塞进程内的任意线程恢复就绪态时，进程被加入到就绪队列，同步转为就绪态，若此时发生进程切换，则进程状态由就绪态转为运行态。
ready→pend：
进程内的最后一个就绪态线程处于阻塞态时，进程从就绪列表中删除，进程由就绪态转为阻塞态。
running→ready：
进程由运行态转为就绪态的情况有以下两种：
有更高优先级的进程创建或者恢复后，会发生进程调度，此刻就绪列表中最高优先级进程变为运行态，那么原先运行的进程由运行态变为就绪态。
若进程的调度策略为sched_rr，且存在同一优先级的另一个进程处于就绪态，则该进程的时间片消耗光之后，该进程由运行态转为就绪态，另一个同优先级的进程由就绪态转为运行态。
running→zombies：
当进程的主线程或所有线程运行结束后，进程由运行态转为僵尸态，等待父进程回收资源。
注意看上面红色的部分，一个进程竟然可以两种状态共存！
uint16 processstatus; /**processstatus &= ~(status | os_process_status_pend);//取反后的与位运算 processcb->processstatus |= os_process_status_ready;//或位运算 一个变量存两种状态，怎么做到的？答案还是按位保存啊。还记得上面的位图调度g_priqueuebitmap吗，那可是存了32种状态的。其实这在任何一个系统的内核源码中都很常见，类似的还有左移 等等
继续说进程和线程的关系，线程的优先级必须和进程一样吗？他们可以不一样吗？答案是：可以不一样，否则怎么会有设置task优先级的函数。
线程调度器
真正让cpu工作的是线程，进程只是个装线程的容器，线程有任务栈空间，是独立运行于内核空间，而进程只有用户空间，具体在后续的内存篇会讲，这里不展开说，但进程结构体losprocesscb有一个这样的定义。看名字就知道了，那是跟调度相关的。
uint32 threadschedulemap; /**< the scheduling bitmap table for the thread group of the process */ los_dl_list threadpriqueuelist[os_priority_queue_num]; /**threadschedulemap; while (bitmap) { priority = clz(bitmap); los_dl_list_for_each_entry(newtask, &processcb->threadpriqueuelist[priority], lostaskcb, pendlist) { #if (loscfg_kernel_smp == yes) if (newtask->cpuaffimask & (1u threadpriqueuelist, &processcb->threadschedulemap, &newtask->pendlist); osdequeemptyschedmap(processcb); goto out; #if (loscfg_kernel_smp == yes) } #endif } bitmap &= ~(1u << (os_priority_queue_num - priority - 1)); } } processbitmap &= ~(1u << (os_priority_queue_num - processpriority - 1)); } out: return newtask; } 映射张大爷的故事：张大爷喊到张全蛋时进场时表演时，张全蛋要决定自己的哪个节目先表演，也要查下他的清单上优先级，它同样也有个张大爷同款记分牌，就这么简单。
CAMILLE BAUER可编程多功能变送器
一文解析钴酸锂生产工艺流程
超级电容器的分类以及储能原理的详细说明
无线WiFi覆盖的基础知识
便携式和固定式氧气浓度检测仪的使用方法
浅谈鸿蒙内核代码调度队列
戴尔新款平板真机图像泄露
GelSight触觉传感器：表面柔软、分辨率高，能复刻整块饼干的形状和纹理
未来芯片的发展对FPGA的要求将会越来越高
用于USB PD适配器的FFRZVS电路设计方案
垃圾收集器的JVM参数配置
远航合金从新三板换道创业板IPO
中兴通讯李自学表示全球5G产业链条必须以合作的心态来迎接
ocxo恒温晶振的参数
德索三大检验方法保证fakra连接器的安全
美信推出车用动态手势传感器
显示器应该如何排除故障及显示器的十大品牌
晶体管丝印标识与型号、原理图符号
罗德与施瓦茨基于华为巴龙5000成功调试5G NR手机信令测试方案
2018年4月湖南用电同比增长6.25%
鸿蒙内核代码中有两个源文件是关于队列的，一个是用于调度的队列，另一个是用于线程间通讯的ipc队列。
本文详细讲述调度队列，详见代码: kernel_liteos_a/kernel/base/sched/sched_sq/los_priqueue.c
ipc队列后续有专门的博文讲述，这两个队列的数据结构实现采用的都是双向循环链表，los_dl_list实在是太重要了，是理解鸿蒙内核的关键，说是最重要的代码一点也不为过，源码出现在 sched_sq模块，说明是用于任务的调度的，sched_sq模块只有两个文件，另一个los_sched.c就是调度代码。
涉及函数
功能分类 接口名 描述
创建队列 ospriqueueinit 创建了32个就绪队列
获取最高优先级队列 ospriqueuetop 查最高优先级任务
从头部入队列 ospriqueueenqueuehead 从头部插入某个就绪队列
从尾部入队列 ospriqueueenqueue 默认是从尾部插入某个就绪队列
出队列 ospriqueuedequeue 从最高优先级的就绪队列中删除
ospriqueueprocessdequeue 从进程队列中删除
ospriqueueprocesssize 用进程查队列中元素个数
ospriqueuesize 用任务查队列中元素个数
ostaskpriqueuetop 查最高优先级任务
osdequeemptyschedmap 进程出列
osgettoptask 获取被调度选择的task
鸿蒙内核进程和线程各有32个就绪队列，进程队列用全局变量存放，创建进程时入队，任务队列放在进程的threadpriqueuelist中。
映射张大爷的故事：就绪队列就是在外面排队的32个通道，按优先级0-31依次排好，张大爷的办公室有个牌子，类似打篮球的记分牌，一共32个，一字排开，队列里有人时对应的牌就是1，没有就是0 ，这样张大爷每次从0位开始看，看到的第一个1那就是最高优先级的那个人。办公室里的记分牌就是位图调度器。
位图调度器
//*kfy 0x80000000u = 10000000000000000000000000000000(32位,1是用于移位的，设计之精妙，点赞) #define priqueue_prior0_bit 0x80000000u #ifndef clz #define clz(value) (__clz(value)) //汇编指令 #endif lite_os_sec_bss los_dl_list *g_priqueuelist = null; //所有的队列 原始指针 lite_os_sec_bss uint32 g_priqueuebitmap; // 位图调度 // priority = clz(bitmap); // 获取最高优先级任务队列 调度位 整个los_priqueue.c就只有两个全部变量，一个是los_dl_list *g_priqueuelist是32个进程就绪队列的头指针，在就绪队列中会讲另一个uint32 g_priqueuebitmap 估计很多人会陌生，是一个32位的变量，叫位图调度器。怎么理解它呢？
鸿蒙系统的调度是抢占式的，task分成32个优先级，如何快速的知道哪个队列是空的，哪个队列里有任务需要一个标识，而且要极高效的实现？答案是:位图调度器。
简单说就是一个变量的位来标记对应队列中是否有任务，在位图调度下,任务优先级的值越小则代表具有越高的优先级，每当需要进行调度时,从最低位向最高位查找出第一个置 1 的位的所在位置,即为当前最高优先级,然后从对应优先级就绪队列获得相应的任务控制块,整个调度器的实现复杂度是 o(1),即无论任务多少,其调度时间是固定的。
进程就绪队列机制
cpu执行速度是很快的，其运算速度和内存的读写速度是数量级的差异，与硬盘的读写更是指数级。鸿蒙内核默认一个时间片是 10ms,资源很宝贵，它不断在众多任务中来回的切换，所以绝不能让cpu等待任务，cpu时间很宝贵，没准备好的任务不要放进来。这就是进程和线程就绪队列的机制，一共有32个任务就绪队列，因为线程的优先级是默认32个， 每个队列中放同等优先级的task.
队列初始化做了哪些工作？详细看代码
#define os_priority_queue_num 32 uint32 ospriqueueinit(void) { uint32 priority; /* system resident resource */ g_priqueuelist = (los_dl_list *)los_memalloc(m_aucsysmem0, (os_priority_queue_num * sizeof(los_dl_list))); if (g_priqueuelist == null) { return los_nok; } for (priority = 0; priority < os_priority_queue_num; ++priority) { los_listinit(&g_priqueuelist[priority]); } return los_ok; } 因task 有32个优先级，在初始化时内核一次性创建了32个双向循环链表，每种优先级都有一个队列来记录就绪状态的tasks的位置，g_priqueuelist分配的是一个连续的内存块，存放了32个los_dl_list，再看一下los_dl_list结构体，因为它太重要了！越简单越灵活
typedef struct los_dl_list { struct los_dl_list *pstprev; /**< current node's pointer to the previous node */ struct los_dl_list *pstnext; /**pstnext == null); if (los_listempty(&priqueuelist[priority])) { *bitmap |= priqueue_prior0_bit >> priority;//对应优先级位 置1 } los_listtailinsert(&priqueuelist[priority], priqueueitem); } void ospriqueueenqueuehead(los_dl_list *priqueuelist, uint32 *bitmap, los_dl_list *priqueueitem, uint32 priority) { /* * task control blocks are inited as zero. and when task is deleted, * and at the same time would be deleted from priority queue or * other lists, task pend node will restored as zero. */ los_assert(priqueueitem->pstnext == null); if (los_listempty(&priqueuelist[priority])) { *bitmap |= priqueue_prior0_bit >> priority;//对应优先级位 置1 } los_listheadinsert(&priqueuelist[priority], priqueueitem); } void ospriqueuedequeue(los_dl_list *priqueuelist, uint32 *bitmap, los_dl_list *priqueueitem) { lostaskcb *task = null; los_listdelete(priqueueitem); task = los_dl_list_entry(priqueueitem, lostaskcb, pendlist); if (los_listempty(&priqueuelist[task->priority])) { *bitmap &= ~(priqueue_prior0_bit >> task->priority);//队列空了，对应优先级位 置0 } } 同一个进程下的线程的优先级可以不一样吗？
请先想一下这个问题。
进程和线程是一对多的父子关系，内核调度的单元是任务(线程)，鸿蒙内核中任务和线程是一个东西，只是不同的身份。一个进程可以有多个线程，线程又有各自独立的状态，那进程状态该怎么界定？例如：processa有 taska(阻塞状态)，taskb(就绪状态) 两个线程，processa是属于阻塞状态还是就绪状态呢？
先看官方文档的说明后再看源码。
进程状态迁移说明：
init→ready：
进程创建或fork时，拿到该进程控制块后进入init状态，处于进程初始化阶段，当进程初始化完成将进程插入调度队列，此时进程进入就绪状态。
ready→running：
进程创建后进入就绪态，发生进程切换时，就绪列表中最高优先级的进程被执行，从而进入运行态。若此时该进程中已无其它线程处于就绪态，则该进程从就绪列表删除，只处于运行态；若此时该进程中还有其它线程处于就绪态，则该进程依旧在就绪队列，此时进程的就绪态和运行态共存。
running→pend：
进程内所有的线程均处于阻塞态时，进程在最后一个线程转为阻塞态时，同步进入阻塞态，然后发生进程切换。
pend→ready / pend→running：
阻塞进程内的任意线程恢复就绪态时，进程被加入到就绪队列，同步转为就绪态，若此时发生进程切换，则进程状态由就绪态转为运行态。
ready→pend：
进程内的最后一个就绪态线程处于阻塞态时，进程从就绪列表中删除，进程由就绪态转为阻塞态。
running→ready：
进程由运行态转为就绪态的情况有以下两种：
有更高优先级的进程创建或者恢复后，会发生进程调度，此刻就绪列表中最高优先级进程变为运行态，那么原先运行的进程由运行态变为就绪态。
若进程的调度策略为sched_rr，且存在同一优先级的另一个进程处于就绪态，则该进程的时间片消耗光之后，该进程由运行态转为就绪态，另一个同优先级的进程由就绪态转为运行态。
running→zombies：
当进程的主线程或所有线程运行结束后，进程由运行态转为僵尸态，等待父进程回收资源。
注意看上面红色的部分，一个进程竟然可以两种状态共存！
uint16 processstatus; /**processstatus &= ~(status | os_process_status_pend);//取反后的与位运算 processcb->processstatus |= os_process_status_ready;//或位运算 一个变量存两种状态，怎么做到的？答案还是按位保存啊。还记得上面的位图调度g_priqueuebitmap吗，那可是存了32种状态的。其实这在任何一个系统的内核源码中都很常见，类似的还有左移 等等
继续说进程和线程的关系，线程的优先级必须和进程一样吗？他们可以不一样吗？答案是：可以不一样，否则怎么会有设置task优先级的函数。
线程调度器
真正让cpu工作的是线程，进程只是个装线程的容器，线程有任务栈空间，是独立运行于内核空间，而进程只有用户空间，具体在后续的内存篇会讲，这里不展开说，但进程结构体losprocesscb有一个这样的定义。看名字就知道了，那是跟调度相关的。
uint32 threadschedulemap; /**< the scheduling bitmap table for the thread group of the process */ los_dl_list threadpriqueuelist[os_priority_queue_num]; /**threadschedulemap; while (bitmap) { priority = clz(bitmap); los_dl_list_for_each_entry(newtask, &processcb->threadpriqueuelist[priority], lostaskcb, pendlist) { #if (loscfg_kernel_smp == yes) if (newtask->cpuaffimask & (1u threadpriqueuelist, &processcb->threadschedulemap, &newtask->pendlist); osdequeemptyschedmap(processcb); goto out; #if (loscfg_kernel_smp == yes) } #endif } bitmap &= ~(1u << (os_priority_queue_num - priority - 1)); } } processbitmap &= ~(1u << (os_priority_queue_num - processpriority - 1)); } out: return newtask; } 映射张大爷的故事：张大爷喊到张全蛋时进场时表演时，张全蛋要决定自己的哪个节目先表演，也要查下他的清单上优先级，它同样也有个张大爷同款记分牌，就这么简单。
CAMILLE BAUER可编程多功能变送器
一文解析钴酸锂生产工艺流程
超级电容器的分类以及储能原理的详细说明
无线WiFi覆盖的基础知识
便携式和固定式氧气浓度检测仪的使用方法
浅谈鸿蒙内核代码调度队列
戴尔新款平板真机图像泄露
GelSight触觉传感器：表面柔软、分辨率高，能复刻整块饼干的形状和纹理
未来芯片的发展对FPGA的要求将会越来越高
用于USB PD适配器的FFRZVS电路设计方案
垃圾收集器的JVM参数配置
远航合金从新三板换道创业板IPO
中兴通讯李自学表示全球5G产业链条必须以合作的心态来迎接
ocxo恒温晶振的参数
德索三大检验方法保证fakra连接器的安全
美信推出车用动态手势传感器
显示器应该如何排除故障及显示器的十大品牌
晶体管丝印标识与型号、原理图符号
罗德与施瓦茨基于华为巴龙5000成功调试5G NR手机信令测试方案
2018年4月湖南用电同比增长6.25%