Loading...
/* * Copyright (c) 2018 Intel Corporation * * SPDX-License-Identifier: Apache-2.0 */ #ifndef _sched_priq__h_ #define _sched_priq__h_ #include <misc/util.h> #include <misc/dlist.h> #include <misc/rb.h> /* Two abstractions are defined here for "thread priority queues". * * One is a "dumb" list implementation appropriate for systems with * small numbers of threads and sensitive to code size. It is stored * in sorted order, taking an O(N) cost every time a thread is added * to the list. This corresponds to the way the original _wait_q_t * abstraction worked and is very fast as long as the number of * threads is small. * * The other is a balanced tree "fast" implementation with rather * larger code size (due to the data structure itself, the code here * is just stubs) and higher constant-factor performance overhead, but * much better O(logN) scaling in the presence of large number of * threads. * * Each can be used for either the wait_q or system ready queue, * configurable at build time. */ struct k_thread; struct k_thread *_priq_dumb_best(sys_dlist_t *pq); void _priq_dumb_remove(sys_dlist_t *pq, struct k_thread *thread); void _priq_dumb_add(sys_dlist_t *pq, struct k_thread *thread); struct _priq_rb { struct rbtree tree; int next_order_key; }; void _priq_rb_add(struct _priq_rb *pq, struct k_thread *thread); void _priq_rb_remove(struct _priq_rb *pq, struct k_thread *thread); struct k_thread *_priq_rb_best(struct _priq_rb *pq); /* Traditional/textbook "multi-queue" structure. Separate lists for a * small number (max 32 here) of fixed priorities. This corresponds * to the original Zephyr scheduler. RAM requirements are * comparatively high, but performance is very fast. Won't work with * features like deadline scheduling which need large priority spaces * to represet their requirements. */ struct _priq_mq { sys_dlist_t queues[32]; unsigned int bitmask; /* bit 1<<i set if queues[i] is non-empty */ }; void _priq_mq_add(struct _priq_mq *pq, struct k_thread *thread); void _priq_mq_remove(struct _priq_mq *pq, struct k_thread *thread); struct k_thread *_priq_mq_best(struct _priq_mq *pq); #endif /* _sched_priq__h_ */ |