国际 网站制作公司,广告公司网络推广计划,做海报哪个网站好,成都建设监理协会网站关于LINUX资源调度
计算机系统中#xff0c;管理资源的方式一般有两种方法#xff0c;分别是时间分割和空间分割#xff0c;可以通过分割硬件的相似性#xff0c;让软件以一致的逻辑执行#xff0c;CPU运行特点是在时刻点A和时刻B运行机制是一样的#xff0c;不同的只是…关于LINUX资源调度
计算机系统中管理资源的方式一般有两种方法分别是时间分割和空间分割可以通过分割硬件的相似性让软件以一致的逻辑执行CPU运行特点是在时刻点A和时刻B运行机制是一样的不同的只是执行现场可以看作是在时间上有对称性的一种资源比较适合的管理方法就是分割时间。而对于内存这种资源不同时刻点的数据是不可预期的在时间尺度上没有相似性但是在空间尺度上A区和B区的晶体管作用基本上是一样的只是空间范围的起始不同就比较适合使用空间分割管理。
所以在操作系统实现中对于CPU分割时间的管理方式就是任务调度而对于内存这种进行空间管理的手段就是BUDDY系统。
CPU是否能在空间维度上管理呢或者内存是否可以在时间维度上进行管理呢应该是可以的比如CPU的多核和SMT/SMP设计就是物理上配置了多组处理器或者流水线资源实现空间维度的扩展。所以运行LINUX系统的当代处理器既支持时分也支持空分管理统统属于调度范畴。
那么内存在时间维度上管理的例子呢或许LINUX系统中的内存交换机制可以看作内存在时间管理上的一个实现为了在有限的内存提供尽量多的运行进程带宽LINUX支持在内存紧张的时刻将匿名页面交换到外部磁盘上在需要的时候在再交换回来实现对物理内存页面的分时复用。所以同CPU管理一样LINUX系统对物理内存的管理也同时支持时分和空分。
CFS调度和优先级队列调度的区别
LINUX内核同时支持CFS调度和优先级队列调度CFS调度算法用在选择SCHED_NORMAL策略的进程上而内核支持的SCHED_RR实时调度策略则采用优先级队列的方式调度下一个要运行的进程。
至于这两种调度策略在内核中的区别个人理解主要体现在对“优先级”的理解上。对于优先级队列这种方式来说优先级的高低是选择下一个运行进程的唯一标准在占有CPU这件事情上高优先级的进程具有绝对的优先权所以只要有高优先级的进程存在低优先级进程永远没有执行的机会所以会有线程饥饿情况的发生。
CFS调度策略对“优先级”的理解则不同对于CFS调度策略来说优先级只是代表进程在时间这个资源池中占据的“比重”或者“份数”而并不是一种绝对的优先权。所以即便就绪队列中存在优先级很低的线程但是仍然能够有一定的“比重”获取CPU。
所以对于优先级队列来说它的调度策略为 对于CFS调度算法来说它的调度策略是选择距离执行到“预期比重”进度最慢的任务。需要有一种指标来衡量这种进度同样的执行时间进度增量和权重成反比权重越大进度增量应该越慢。
假设有两个进程的权重为W1W2 W1 W2 选择W1作为其他任务的对照基准 以两个权重分别为2和5的线程举例按照CFS调度其调度过程中进度变化如下表所示进度最终得到相同。 所以CFS调度算法保证的是在持续调度的过程中所有任务的执行进度和参照任务保持一致其中参照任务是任意指定的一般选择被大多数线程使用的任务权重作为参考基准这样在计算过程中比例引子为1时间增量和进度增量相同便于计算。
在LINUX内核调度器中有一个专有名字表示进度指标叫做虚拟时间。观察上表可以看到对于高优先级进程由于其权重较大因此它的虚拟时间是按照比例缩小的也就是说基准权重的时间和正常时间流逝相同权重大于基准始终的任务其时间流逝会变慢CFS调度器会有限选择虚拟时间最慢的线程进行调度所以高权重的任务才有更多的运行机会。对于权重低于基准权重的低优先级任务来说前时间流逝会比正常的时间更快这样它只要执行较少的时间就可以满足对进度的要求这样在一个完整的调度周期内队列中所有进程都得到一次调度的时间比如上表中的W1W2每个任务都有执行的机会进入尽量在调度周期结束后对齐虚拟时间。
之所以说是尽量是因为内核中的调度点并不一定恰好在被权重整除的整数单位上在一个DELTA TIME中总会以有进程比预期多执行一会儿获得了较多的虚拟时间增量而其它进程少执行了一些。这就需要在下一个调度周期内进行补偿和奖励那些少运行的线程。因为调度周期是有限的而CFS调度能够保证每个调度周期内每个任务都有机会执行误差只会在不对齐的调度时刻出现所以任务的虚拟时间总体上不会相差太大CFS调度是一个不断追求公平的动态的过程它实现了程序上的公平并通过动态纠偏保证了结果的公平。
下面是参考内核CFS调度算法实现的算法模型仿真程序分别使用红黑数和链表两种方式管理任务队列支持动态添加任务
#include stdio.h
#include stdlib.h
#include stdint.h
#include float.h
#include unistd.h
#include pthread.h
#include time.h
#include math.h
#include rbtree.h#define CFS_USE_RB_TREE
// A CFS Scheduler CModel.
#define DBG(fmt, ...) do { printf(%s line %d, fmt, __func__, __LINE__, ##__VA_ARGS__); } while (0)
#define assert(expr) \if (!(expr)) { \printf(Assertion failed! %s,%s,%s,line%d\n,\#expr,__FILE__,__func__,__LINE__); \while(1); \}static pthread_mutex_t cfs_mutex;
double min_vruntime 0.0f;
void update_min_vruntime(double vruntime)
{min_vruntime vruntime;
}
/** Nice levels are multiplicative, with a gentle 10% change for every* nice level changed. I.e. when a CPU-bound task goes from nice 0 to* nice 1, it will get ~10% less CPU time than another CPU-bound task* that remained on nice 0.** The 10% effect is relative and cumulative: from _any_ nice level,* if you go up 1 level, its -10% CPU usage, if you go down 1 level* its 10% CPU usage. (to achieve that we use a multiplier of 1.25.* If a task goes up by ~10% and another task goes down by ~10% then* the relative distance between them is ~25%.)*/
const double sched_prio_to_weight[40] {
#if 1/* -20 */ 88761, 71755, 56483, 46273, 36291,/* -15 */ 29154, 23254, 18705, 14949, 11916,/* -10 */ 9548, 7620, 6100, 4904, 3906,/* -5 */ 3121, 2501, 1991, 1586, 1277,/* 0 */ 1024, 820, 655, 526, 423,/* 5 */ 335, 272, 215, 172, 137,/* 10 */ 110, 87, 70, 56, 45,/* 15 */ 36, 29, 23, 18, 15,
#else/* -20 */ 10, 10, 10, 10, 10,/* -15 */ 10, 10, 10, 10, 10,/* -10 */ 10, 10, 10, 10, 10,/* -5 */ 10, 10, 10, 10, 10,/* 0 */ 10, 10, 10, 10, 10,/* 5 */ 10, 10, 10, 10, 10,/* 10 */ 10, 10, 10, 10, 10,/* 15 */ 10, 10, 10, 10, 10,
#endif
};typedef struct sched_entity {struct rb_node node;int prio;int pid;double weight;double vruntime;double realtime;int ctx_switch;int on_rq;
} sched_entity_t;struct rb_root cfs_root_tree RB_ROOT;
int sched_period(void)
{return rand() % 10 1;
}#define MAX_ENTRY 80
//#define SCHED_PERIOD 100
#define SCHED_PERIOD sched_period()
static sched_entity_t *tasks;// https://zhuanlan.zhihu.com/p/673572911
// in linux kernel, cfs_rq-load used for statistic the total
// weight in rq, refer update_load_add / update_load_sub.
double caculate_total_weight(void)
{double total 0.0;
#if 1struct rb_node *node;sched_entity_t *task;for (node rb_first(cfs_root_tree); node; node rb_next(node)) {task rb_entry(node, sched_entity_t, node);total task-weight;}
#elseint i;for (i 0; i MAX_ENTRY; i ) {total tasks[i].weight;}
#endifreturn total;
}double caculate_realtime(int task)
{double real 0.0;real SCHED_PERIOD * tasks[task].weight / caculate_total_weight();//printf(%s line %d, real %f.\n, __func__, __LINE__, real);return real;
}double caculate_vruntime(sched_entity_t *task, int deltatime)
{double vruntime 0.0;vruntime deltatime * sched_prio_to_weight[20] / task-weight ;//printf(%s line %d, vruntime %f.\n, __func__, __LINE__, vruntime);return vruntime;
}#define MAX_TICKS_TEST 100000000UL
double vruntime_total(unsigned long worldtime)
{return worldtime * sched_prio_to_weight[20] / caculate_total_weight();
}double realtime_total(sched_entity_t *task, unsigned long worldtime)
{
#if 1return worldtime * task-weight / caculate_total_weight();
#elsereturn vruntime_total(worldtime) * task-weight / sched_prio_to_weight[20];
#endif
}static int compare_prio(sched_entity_t *task1, sched_entity_t *task2)
{
#if 0if (task1-vruntime task2-vruntime) {// task1 prior than task2.return -1;} else if (task1-vruntime task2-vruntime) {// task2 prior than task1.return 1;} else {if (task1-weight task2-weight) {return -1;} else {// task2 prior than task1.return 1;}}
#elsedouble res (task1-vruntime task2-vruntime) ? task1-weight - task2-weight : task2-vruntime - task1-vruntime;return res 0.0f ? -1 : 1;
#endif
}static int cfs_rq_delete(struct rb_root *root, sched_entity_t *task)
{rb_erase(task-node, root);return !RB_EMPTY_ROOT(root);
}static int cfs_rq_insert(struct rb_root *root, sched_entity_t *task)
{int ret;struct rb_node **tmp (root-rb_node), *parent NULL;/* Figure out where to put new node */while (*tmp) {sched_entity_t *this rb_entry(*tmp, sched_entity_t, node);parent *tmp;ret compare_prio(task, this);if (ret 0)tmp ((*tmp)-rb_left);else if (ret 0)tmp ((*tmp)-rb_right);elsereturn -1;}/* Add new node and rebalance tree. */rb_link_node(task-node, parent, tmp);rb_insert_color(task-node, root);return 0;
}static void cfs_rq_destroy(struct rb_root *root)
{struct rb_node *node, *next;sched_entity_t *task;node rb_first(root);while (node) {next rb_next(node);task rb_entry(node, sched_entity_t, node);rb_erase(node, root);node next;}if (!RB_EMPTY_ROOT(root)) {printf(%s line %d, rb is not empty.\n, __func__, __LINE__);}return;
}void print_rbtree(struct rb_root *tree)
{struct rb_node *node;sched_entity_t *task;for (node rb_first(tree); node; node rb_next(node)) {task rb_entry(node, sched_entity_t, node);printf(%s line %d, task(%d) prio %d,weight %f vruntime %f, on rq %d.\n,__func__, __LINE__, task-pid, task-prio, task-weight, task-vruntime, task-on_rq);}return;
}void init_cfs_rbtree(void)
{int i;for (i 0; i MAX_ENTRY; i ) {tasks[i].on_rq 1;cfs_rq_insert(cfs_root_tree, tasks[i]);}print_rbtree(cfs_root_tree);return;
}#ifdef CFS_USE_RB_TREE
// O(logn) scheduler base on rbtree.
sched_entity_t *schedule(void)
{struct rb_node *node;sched_entity_t *task;node rb_first(cfs_root_tree);task rb_entry(node, sched_entity_t, node);return task;
}#else
// A O(n) linear scheuler impl.
sched_entity_t *schedule(void)
{int i;int taskid -1;double minruntime DBL_MAX;// schedule policy:// 1.first find the task with the minum vruntime.// 2.if multiple task the the same minum vruntime, then// select the weighter one.for (i 0; i MAX_ENTRY; i ) {if (minruntime tasks[i].vruntime) {minruntime tasks[i].vruntime;taskid i;} else if (minruntime tasks[i].vruntime) {if (tasks[i].weight tasks[taskid].weight) {taskid i;}}}return tasks[taskid];
}
#endifdouble list_task_info(unsigned long worldtime)
{double total 0.0;printf(\n);
#if 1struct rb_node *node;sched_entity_t *task;for (node rb_first(cfs_root_tree); node; node rb_next(node)) {task rb_entry(node, sched_entity_t, node);total task-realtime;printf(task(pid%d) vuntime %f, realtime %f, prio %d, weight %f, switches %d, ideal real time %f.\n,task-pid, task-vruntime, task-realtime, task-prio, task-weight, task-ctx_switch,realtime_total(task, worldtime));}
#elseint i;for (i 0; i MAX_ENTRY; i ) {double ratio 0.0;if (i 0) {ratio (tasks[i - 1].realtime - tasks[i].realtime) / tasks[i].realtime;}total tasks[i].realtime;printf(task %d(pid%d) vuntime %f, realtime %f, prio %d, weight %f, incretio %f, switches %d, ideal real time %f.\n,i, tasks[i].pid, tasks[i].vruntime, tasks[i].realtime, tasks[i].prio, tasks[i].weight, ratio * 100, tasks[i].ctx_switch,realtime_total(tasks[i], worldtime));}
#endifdouble staticis(void);printf(fangcha %f.\n, staticis());printf(\n);return total;
}static void *fork_thread(void *arg)
{sched_entity_t *task;unsigned long *pworldtime (unsigned long *)arg;static unsigned int pid MAX_ENTRY;int i;while (1) {task malloc(sizeof(sched_entity_t));memset(task, 0x00, sizeof(sched_entity_t));i rand() % 40;pthread_mutex_lock(cfs_mutex);task-prio -20 i;task-weight sched_prio_to_weight[i];//task-vruntime vruntime_total(*pworldtime) 1.5f;task-vruntime min_vruntime 1.5f;task-realtime 0;task-ctx_switch 0;task-pid pid ;task-on_rq 0;cfs_rq_insert(cfs_root_tree, task);task-on_rq 1;pthread_mutex_unlock(cfs_mutex);sleep(1);}return NULL;
}static void *exit_thread(void *arg)
{unsigned long *pwordtime (unsigned long *)arg;while (1) {sleep(1);}return NULL;
}double staticis(void)
{double statics 0.0f;double average 0.0f;double total 0.0f;int count 0;struct rb_node *node;sched_entity_t *task;for (node rb_first(cfs_root_tree); node; node rb_next(node)) {task rb_entry(node, sched_entity_t, node);total task-vruntime;count ;}average total / count;for (node rb_first(cfs_root_tree); node; node rb_next(node)) {task rb_entry(node, sched_entity_t, node);statics (average - task-vruntime) * (average - task-vruntime);}return sqrt(statics / count);
}
int main(void)
{int i;unsigned long ticks;double total 0.0;unsigned long worldtime 0;pthread_t t1, t2;pthread_mutex_init(cfs_mutex, NULL);tasks malloc(sizeof(sched_entity_t) * MAX_ENTRY);memset(tasks, 0x00, sizeof(sched_entity_t) * MAX_ENTRY);if (!tasks) {printf(%s line %d, fatal errro, alloc failure.\n,__func__, __LINE__);return -1;}srand((unsigned int)time(0));for (i 0; i MAX_ENTRY; i ) {tasks[i].prio -20 i % 40;tasks[i].weight sched_prio_to_weight[i % 40];tasks[i].vruntime 0;tasks[i].realtime 0;tasks[i].ctx_switch 0;tasks[i].pid i;tasks[i].on_rq 0;}#ifdef CFS_USE_RB_TREEinit_cfs_rbtree();
#endif// should be first.printf(%s line %d, first schedule select %ld.\n, __func__, __LINE__, schedule() - tasks);pthread_create(t1, NULL, fork_thread, worldtime);pthread_create(t2, NULL, exit_thread, worldtime);for (ticks 0; /* ticks MAX_TICKS_TEST */ 1; ticks ) {double deltatime, vruntime;sched_entity_t *task;pthread_mutex_lock(cfs_mutex);task schedule();#ifdef CFS_USE_RB_TREEcfs_rq_delete(cfs_root_tree, task);task-on_rq 0;#endifdeltatime SCHED_PERIOD;vruntime caculate_vruntime(task, deltatime);task-vruntime vruntime;task-realtime deltatime;task-ctx_switch ;worldtime deltatime;update_min_vruntime(task-vruntime);#ifdef CFS_USE_RB_TREE// USE dequeue and enqueue to trigger the reorder of cfs rbtree ready queue.// this also the same in linux kernel, refer put_prev_entity(enqueue) and set_next_task(dequeue)// the only differenct is in linux kenrel the on_rq still keep no matter put_prev_entity/set_next_entity// involation.cfs_rq_insert(cfs_root_tree, task);task-on_rq 1;
#endifif (ticks % 1000 0) {list_task_info(worldtime);}pthread_mutex_unlock(cfs_mutex);}pthread_mutex_lock(cfs_mutex);total list_task_info(worldtime);assert(total worldtime);printf(vruntime %f.\n, vruntime_total(worldtime));pthread_mutex_unlock(cfs_mutex);pthread_join(t1, NULL);pthread_join(t2, NULL);#ifdef CFS_USE_RB_TREEprint_rbtree(cfs_root_tree);cfs_rq_destroy(cfs_root_tree);
#endiffree(tasks);return 0;
}
仿真结果按照CFS算法调度大约1000个进程VRUNTIME的方差始终控制在70左右下面截图中显示所有进程的VRUNTIME集中在[308177.014345,308736.000000]对照方差VRUNTIME表示的所有任务的执行进度是非常集中的说明CFS的调度策略确实照顾到了所有优先级的进程使大家的执行进度基本保持在一个动态的一致范围之内。 参考文章
五Linux进程调度-CFS调度器
吐血整理 | 肝翻 Linux 进程调度所有知识点 结束 文章转载自： http://www.morning.rzpkt.cn.gov.cn.rzpkt.cn http://www.morning.shyqcgw.cn.gov.cn.shyqcgw.cn http://www.morning.thbnt.cn.gov.cn.thbnt.cn http://www.morning.nytgk.cn.gov.cn.nytgk.cn http://www.morning.ishoufeipin.cn.gov.cn.ishoufeipin.cn http://www.morning.rhsr.cn.gov.cn.rhsr.cn http://www.morning.wjlrw.cn.gov.cn.wjlrw.cn http://www.morning.routalr.cn.gov.cn.routalr.cn http://www.morning.sfswj.cn.gov.cn.sfswj.cn http://www.morning.tyhfz.cn.gov.cn.tyhfz.cn http://www.morning.qggxt.cn.gov.cn.qggxt.cn http://www.morning.beiyishengxin.cn.gov.cn.beiyishengxin.cn http://www.morning.4r5w91.cn.gov.cn.4r5w91.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.wdqhg.cn.gov.cn.wdqhg.cn http://www.morning.zsrdp.cn.gov.cn.zsrdp.cn http://www.morning.rmqmc.cn.gov.cn.rmqmc.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.rykx.cn.gov.cn.rykx.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.klyzg.cn.gov.cn.klyzg.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.zmyhn.cn.gov.cn.zmyhn.cn http://www.morning.dnls.cn.gov.cn.dnls.cn http://www.morning.prlgn.cn.gov.cn.prlgn.cn http://www.morning.wbxrl.cn.gov.cn.wbxrl.cn http://www.morning.rmlz.cn.gov.cn.rmlz.cn http://www.morning.txtgy.cn.gov.cn.txtgy.cn http://www.morning.c7513.cn.gov.cn.c7513.cn http://www.morning.wmmtl.cn.gov.cn.wmmtl.cn http://www.morning.knwry.cn.gov.cn.knwry.cn http://www.morning.tymnr.cn.gov.cn.tymnr.cn http://www.morning.hwlk.cn.gov.cn.hwlk.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.bfbl.cn.gov.cn.bfbl.cn http://www.morning.nbnq.cn.gov.cn.nbnq.cn http://www.morning.hsjfs.cn.gov.cn.hsjfs.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.fzlk.cn.gov.cn.fzlk.cn http://www.morning.fbzdn.cn.gov.cn.fbzdn.cn http://www.morning.pngfx.cn.gov.cn.pngfx.cn http://www.morning.kwpnx.cn.gov.cn.kwpnx.cn http://www.morning.lfbzg.cn.gov.cn.lfbzg.cn http://www.morning.zxqqx.cn.gov.cn.zxqqx.cn http://www.morning.fcwxs.cn.gov.cn.fcwxs.cn http://www.morning.dblfl.cn.gov.cn.dblfl.cn http://www.morning.rcttz.cn.gov.cn.rcttz.cn http://www.morning.ohmyjiu.com.gov.cn.ohmyjiu.com http://www.morning.wgqtj.cn.gov.cn.wgqtj.cn http://www.morning.klpwl.cn.gov.cn.klpwl.cn http://www.morning.qbzfp.cn.gov.cn.qbzfp.cn http://www.morning.knmp.cn.gov.cn.knmp.cn http://www.morning.fywqr.cn.gov.cn.fywqr.cn http://www.morning.dmkhd.cn.gov.cn.dmkhd.cn http://www.morning.jcxgr.cn.gov.cn.jcxgr.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.qrqg.cn.gov.cn.qrqg.cn http://www.morning.tktcr.cn.gov.cn.tktcr.cn http://www.morning.mingjiangds.com.gov.cn.mingjiangds.com http://www.morning.yntsr.cn.gov.cn.yntsr.cn http://www.morning.kwnbd.cn.gov.cn.kwnbd.cn http://www.morning.ryyjw.cn.gov.cn.ryyjw.cn http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.wrbx.cn.gov.cn.wrbx.cn http://www.morning.qgjgsds.com.cn.gov.cn.qgjgsds.com.cn http://www.morning.bchgl.cn.gov.cn.bchgl.cn http://www.morning.rykmz.cn.gov.cn.rykmz.cn http://www.morning.jkdtz.cn.gov.cn.jkdtz.cn http://www.morning.ysllp.cn.gov.cn.ysllp.cn http://www.morning.ccphj.cn.gov.cn.ccphj.cn http://www.morning.lztrt.cn.gov.cn.lztrt.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.hsxkq.cn.gov.cn.hsxkq.cn http://www.morning.dlwzm.cn.gov.cn.dlwzm.cn http://www.morning.kybyf.cn.gov.cn.kybyf.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.hctgn.cn.gov.cn.hctgn.cn http://www.morning.nrlsg.cn.gov.cn.nrlsg.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn
