本站首页    管理页面    写新日志    退出


«July 2019»
123456
78910111213
14151617181920
21222324252627
28293031


公告

戒除浮躁,读好书,交益友


我的分类(专题)

日志更新

最新评论

留言板

链接

Blog信息
blog名称:邢红瑞的blog
日志总数:523
评论数量:1142
留言数量:0
访问次数:9291110
建立时间:2004年12月20日




[linux kernel]深入Linux内核架构第二章学习笔记 
原创空间,  文章收藏,  软件技术,  科学研究

邢红瑞 发表于 2010-9-6 17:00:53

  深入linux内核架构是本根据Linux源代码讲述内核的书,比深入理解linux内核更加贴近代码,讲的更深入浅出一些。 本书第二章主要讲述Linux进程的调度,linux的进程都可以描述为task_struct的结构,这个结构包含进程运行的所有信息。 task_struct的有一个字段是 volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */ 来跟踪线程的运行状态,这个volatile 关键字很重要,它告诉编译器定义的变量随时都有可能改变,程序每次需要存储或读取这个变量的时候,直接从变量地址中读取数据。如果没有 volatile关键字,则编译器可能优化读取和存储,可能使用寄存器中的值,如果这个变量由别的程序更新了的话,将出现不一致的现象。 task_struct另外一个重要的字段是类型为pid_t的pid,它默认的最大值是32768。和windows 类似的是linux的线程id和进程id肯定不同,从内核来看,一个用户层创建的线程就是一个普通进程,从源码来看他们的实现非常类似,都调用了do_fork 函数,这是最后的两个参数不同。IA32 linux fork内核实现, arch/x86/kernel/process_32.c asmlinkage int sys_fork(struct pt_regs regs) { return do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL); }   线程的实现 arch/x86/kernel/process_32.c asmlinkage int sys_clone(struct pt_regs regs) { unsigned long clone_flags; unsigned long newsp; int __user *parent_tidptr, *child_tidptr; clone_flags = regs.ebx; newsp = regs.ecx; parent_tidptr = (int __user *)regs.edx; child_tidptr = (int __user *)regs.edi; if (!newsp) newsp = regs.esp; return do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr); } (parent_tidptr和child_tidptr是指向用户空间的指针,对应linux的线程实现,目前通用的linux实现有LinuxThreads和NPTL(Native Posix Thread Library)。 NPTL的支持是在glibc中实现的,与内核无关。 大家输入  getconf GNU_LIBPTHREAD_VERSION 便可以看到本机NPTL的版本。 如果是早期的glibc,使用以下命令查看 $(ldd /bin/ls | grep libc.so | awk '{print $3}') | grep  'Threads|threads' Linux 2.4 早期版本中使用linuxpthreads库,那么在多线程程序中,会产生一个用户线程来维护当前的线程,例如在main()中创建了2个线程,那么用 ps axm 查看进程表,程序应有4个线程。使用NPTL后大家就会看到一个进程在运行,通过/proc/pid/status产看当前进程的线程数。 由于每个task_struct都嵌入了一个schedule entity的实例,因此进程是可以调度的。 内核版本2.6.24之后的kernel在runqueue中以新增的cfs_rq红黑树结构存放schedule entity(SE),记录每个task执行相关的时间数据。Kernel在runqueue新增task的時候以SE中的vruntime作为比较依据,和红黑树各SE的vruntime相比,vruntime比较小的SE往左靠拢,反之大vruntime大的SE向右靠拢,直到这个SE成为最左边或最右边的节点为止。SE中的vruntime的类型为u64。 当新的task创建出来之后task_new_fair函数通过place_entity取得新task的vruntime。 static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {        u64 vruntime = cfs_rq->min_vruntime;          /*         * The 'current' period is already promised to the current tasks,         * however the extra weight of the new task will slow them down a         * little, place the new task so that it fits in the slot that         * stays open at the end.         */        if (initial && sched_feat(START_DEBIT))               vruntime += sched_vslice(cfs_rq, se);          /* sleeps up to a single latency don't count. */        if (!initial && sched_feat(FAIR_SLEEPERS)) {               unsigned long thresh = sysctl_sched_latency;                 /*                * Convert the sleeper threshold into virtual time.                * SCHED_IDLE is a special sub-class.  We care about                * fairness only relative to other SCHED_IDLE tasks,                * all of which have the same weight.                */               if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||                              task_of(se)->policy != SCHED_IDLE))                      thresh = calc_delta_fair(thresh, se);                 /*                * Halve their sleep time's effect, to allow                * for a gentler effect of sleepers:                */               if (sched_feat(GENTLE_FAIR_SLEEPERS))                      thresh >>= 1;                 vruntime -= thresh;        }          /* ensure we never gain time by being placed backwards. */        vruntime = max_vruntime(se->vruntime, vruntime);          se->vruntime = vruntime; } cfs_rq->min_vruntime就是整个红黑树最左边schedule entity的vruntime,在kernel调用__update_curr时更新,整个红黑树中所有的schedule entity的vruntime会随着时间而增加。 取得新task的vruntime之后task_new_fair函数间接调用enqueue_task_fair函数调用__enqueue_entity函式把新task的schedule entity放入cfs_rq,vruntime在__enqueue_entity函式中被用来決定新task该放在cfs_rq红黑树中的那个位置。 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;        struct rb_node *parent = NULL;        struct sched_entity *entry;        s64 key = entity_key(cfs_rq, se);        int leftmost = 1;          /*         * Find the right place in the rbtree:         */        while (*link) {               parent = *link;               entry = rb_entry(parent, struct sched_entity, run_node);               /*                * We dont care about collisions. Nodes with                * the same key stay together.                */               if (key < entity_key(cfs_rq, entry)) {                      link = &parent->rb_left;               } else {                      link = &parent->rb_right;                      leftmost = 0;               }        }          /*         * Maintain a cache of leftmost tree entries (it is frequently         * used):         */        if (leftmost)               cfs_rq->rb_leftmost = &se->run_node;          rb_link_node(&se->run_node, parent, link);        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);   }   时钟中断通过update_process_times调用scheduler_tick,在2.6.24以前的版本中 scheduler_tick通过减少当前task的time slice直到为0,或者到某个值(这个值可以通过TIMESLICE_GRANULARITY得到)。但是在2.6.24以后不再使用time slice。 void scheduler_tick(void) {         int cpu = smp_processor_id();         struct rq *rq = cpu_rq(cpu);         struct task_struct *curr = rq->curr;         u64 next_tick = rq->tick_timestamp + TICK_NSEC;           spin_lock(&rq->lock);         __update_rq_clock(rq);         /*          * Let rq->clock advance by at least TICK_NSEC:          */         if (unlikely(rq->clock < next_tick))                 rq->clock = next_tick;         rq->tick_timestamp = rq->clock;         update_cpu_load(rq);         if (curr != rq->idle) /* FIXME: needed? */                 curr->sched_class->task_tick(rq, curr);         spin_unlock(&rq->lock);   #ifdef CONFIG_SMP         rq->idle_at_tick = idle_cpu(cpu);         trigger_load_balance(rq, cpu); #endif } scheduler_tick调用task_tick函数,task_tick的实现方式取决于底层的实现。 SE的load是load_weight的结构体,struct load_weight { unsigned long weight, inv_weight; }; weight和inv_weight分別来自prio_to_weight和prio_to_wmult两个数组,如果task为real-time task或idle task,kernel直接把weight和inv_weight设为固定值,调用函数为set_load_weight。 static void set_load_weight(struct task_struct *p)  {          if (task_has_rt_policy(p)) {                  p->se.load.weight = prio_to_weight[0] * 2;                  p->se.load.inv_weight = prio_to_wmult[0] >> 1;                  return;          }            /*          * SCHED_IDLE tasks get minimal weight:          */          if (p->policy == SCHED_IDLE) {                  p->se.load.weight = WEIGHT_IDLEPRIO;                  p->se.load.inv_weight = WMULT_IDLEPRIO;                  return;          }            p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];          p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];  }    当task是普通task,它的load取决于static priority,static priority在创建task时就创建好了,在100到140之间。 static const int prio_to_weight[40] = {   /* -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,  };      static const u32 prio_to_wmult[40] = {   /* -20 */     48388,     59856,     76040,     92818,    118348,   /* -15 */    147320,    184698,    229616,    287308,    360437,   /* -10 */    449829,    563644,    704093,    875809,   1099582,   /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,   /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,   /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,   /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,   /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,  };  sched_slice根据runqueue中task的个数决定每个task的合理执行时间,当current task使用CPU超出合理执行时间时,kernel将current task置为重新调度。 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { u64 slice = __sched_period(cfs_rq->nr_running); slice *= se->load.weight; do_div(slice, cfs_rq->load.weight); return slice; } kernel判断每个task执行时间的取决于task的static priority和cfs_rq->nr_running(runqueue的task数量)。当runqueue中task小于等于5时,task的priority和执行时间由task的static priority决定,当runqueue中的task5时,runqueue中的task也成为影响因素之一。   static u64 __sched_period(unsigned long nr_running)  {          u64 period = sysctl_sched_latency;            unsigned long nr_latency = sched_nr_latency;            if (unlikely(nr_running > nr_latency)) {                  period *= nr_running;                  do_div(period, nr_latency);          }            return period;  }


阅读全文(3892) | 回复(0) | 编辑 | 精华
 



发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)



站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.047 second(s), page refreshed 144295701 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号