1 /* 2 * Copyright (c) 2018 Intel Corporation 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 */ 6 #ifndef ZEPHYR_INCLUDE_SCHED_PRIQ_H_ 7 #define ZEPHYR_INCLUDE_SCHED_PRIQ_H_ 8 9 #include <zephyr/sys/util.h> 10 #include <zephyr/sys/dlist.h> 11 #include <zephyr/sys/rb.h> 12 13 /* Two abstractions are defined here for "thread priority queues". 14 * 15 * One is a "dumb" list implementation appropriate for systems with 16 * small numbers of threads and sensitive to code size. It is stored 17 * in sorted order, taking an O(N) cost every time a thread is added 18 * to the list. This corresponds to the way the original _wait_q_t 19 * abstraction worked and is very fast as long as the number of 20 * threads is small. 21 * 22 * The other is a balanced tree "fast" implementation with rather 23 * larger code size (due to the data structure itself, the code here 24 * is just stubs) and higher constant-factor performance overhead, but 25 * much better O(logN) scaling in the presence of large number of 26 * threads. 27 * 28 * Each can be used for either the wait_q or system ready queue, 29 * configurable at build time. 30 */ 31 32 struct k_thread; 33 34 struct k_thread *z_priq_dumb_best(sys_dlist_t *pq); 35 void z_priq_dumb_remove(sys_dlist_t *pq, struct k_thread *thread); 36 37 struct _priq_rb { 38 struct rbtree tree; 39 int next_order_key; 40 }; 41 42 void z_priq_rb_add(struct _priq_rb *pq, struct k_thread *thread); 43 void z_priq_rb_remove(struct _priq_rb *pq, struct k_thread *thread); 44 struct k_thread *z_priq_rb_best(struct _priq_rb *pq); 45 46 /* Traditional/textbook "multi-queue" structure. Separate lists for a 47 * small number (max 32 here) of fixed priorities. This corresponds 48 * to the original Zephyr scheduler. RAM requirements are 49 * comparatively high, but performance is very fast. Won't work with 50 * features like deadline scheduling which need large priority spaces 51 * to represent their requirements. 52 */ 53 struct _priq_mq { 54 sys_dlist_t queues[32]; 55 unsigned int bitmask; /* bit 1<<i set if queues[i] is non-empty */ 56 }; 57 58 struct k_thread *z_priq_mq_best(struct _priq_mq *pq); 59 60 #endif /* ZEPHYR_INCLUDE_SCHED_PRIQ_H_ */ 61
