基于Linux系统深入源码分析进程模型

进程&＃xff08;Process&＃xff09;是计算机中的程序关于某数据集合上的一次运行活动&＃xff0c;是系统进行资源分配和调度的基本单位&＃xff0c;是操作系统结构的基础。简而言之&＃xff0c;一个进程就是一个正在执行程序的实例。

windows的进程&＃xff1a;

　　Linux以它的高效性和灵活性著称&＃xff0c;Linux模块化的设计结构&＃xff0c;使得它既能在价格昂贵的工作站上运行&＃xff0c;也能够在廉价的PC机上实现全部的Unix特性&＃xff0c;具有多任务、多用户的能力。Linux是在GNU公共许可权限下免费获得的&＃xff0c;是一个符合POSIX标准的操作系统。Linux操作系统软件包不仅包括完整的Linux操作系统&＃xff0c;而且还包括了文本编辑器、高级语言编译器等应用软件。它还包括带有多个窗口管理器的X-Windows图形用户界面&＃xff0c;如同我们使用Windows NT一样&＃xff0c;允许我们使用窗口、图标和菜单对系统进行操作。

3.Linux系统组织进程

• Linux通过task_struct结构体来描述一个进程的所有信息&＃xff0c;结构体被定义在 include/linux/sched.h中。
• task_struct结构体即是PCB。PCB是进程的唯一标识&＃xff0c;PCB由链表实现&＃xff08;为了动态插入和删除&＃xff09;。进程创建时&＃xff0c;为该进程生成一个PCB&＃xff1b;进程终止时&＃xff0c;回收PCB。
• PCB相关&＃xff1a;

  • 进程状态&＃xff08;State&＃xff09;

  • 进程调度信息

  • 标识符

  • 进程通信有关信息

  • 进程链接信息

  • 时间和定时器信息

  • 文件系统信息

  • 虚拟内存信息

  • 页面管理信息

  • 对称多处理机&＃xff08;SMP&＃xff09;信息

  • 和处理器相关的环境&＃xff08;上下文&＃xff09;信息

  • 其它

4.进程的调度

4.1调度的定义&＃xff1a;

当计算机系统十多道程序设计系统时&＃xff0c;通常就会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态&＃xff0c;这种情形就会发生。如果只有一个CPU可用&＃xff0c;那么就必须选择下一个要运行的进程。在操作系统中&＃xff0c;完成选择工作的这一部分称为调度程序&＃xff0c;该程序使用的算法称为调度算法。

4.2Linux系统的两个调度算法

4.2.1LinuxO(1)调度器(O(1)scheduler)

       这个调度器能够在常数时间内执行任务调度&＃xff0c;例如从执行队列中选择一个任务或将一个任务加入执行队列&＃xff0c;这与系统中的任务总数无关。

      O(1)调度器优点&＃xff1a;能够在常数时间内执行任务调度

      O(1)调度器缺点&＃xff1a;使用启发式方法来确定一个任务的交互性&＃xff0c;会使该任务的优先级复杂且不完善&＃xff0c;从而导致在处理交互任务时性能很糟糕。

4.2.2CFS(完全公平调度器)

      它在Linux2.6.23版本中首次被集成到内核中     

      CFS的主要思想是使用一颗红黑树作为调度队列的数据结构。

      CFS的调度算法总结&＃xff1a;该算法总是优先调度那些使用CPU时间最少的任务&＃xff0c;通常是在树中最左边节点上的任务。CFS会周期性地根据任务已经运行的时间&＃xff0c;递增他的虚拟时间运行值&＃xff0c;并将这个值与树中当前最左节点的值进行比较&＃xff0c;如果正在运行的任务仍具有较小虚拟运行时间值&＃xff0c;那么它将继续运行&＃xff0c;否则&＃xff0c;它将被插入红黑树的适当位置&＃xff0c;并且CPU将执行新的最左边节点上的任务。 

5.关于vruntime

vruntime是CFS的重要概念&＃xff0c;简单地说&＃xff0c;vruntime是该进程的运行时间&＃xff0c;但这个时间是通过优先级等计算过的虚拟运行时间&＃xff0c;并非物理时间。之前在进程的转换中提到过CPU分配时间片&＃xff0c;在CFS中&＃xff0c;已经不再使用时间片&＃xff0c;而是按照虚拟运行时间来衡量进程此时是否该被调度。那么&＃xff0c;虚拟时间是如何被计算出来的呢?kernel/sched.c中有一个用于处理时钟中断的函数&＃xff0c;如下

void scheduler_tick(void) { … raw_spin_lock(&rq->lock); update_rq_clock(rq); update_cpu_load(rq); curr->sched_class->task_tick(rq, curr, 0); raw_spin_unlock(&rq->lock); … }

其中&＃xff0c;curr->sched_class->task_tick(rq, curr, 0);用于执行调度器&＃xff0c;更新vruntime值。task_tike_fair函数则会在循环语句中&＃xff0c;对所以有se变量调用entity_tick()&＃xff0c;代码如下

for_each_sched_entity(se) {cfs_rq &＃61; cfs_rq_of(se);entity_tick(cfs_rq, se, queued);//Look at this line}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) { /* * Update run-time statistics of the &＃39;current&＃39;. */ update_curr(cfs_rq); //Look at this line #ifdef CONFIG_SCHED_HRTICK /* * queued ticks are scheduled to match the slice, so don&＃39;t bother * validating it and just reschedule. */ if (queued) { resched_task(rq_of(cfs_rq)->curr); return; } /* * don&＃39;t let the period tick interfere with the hrtick preemption */ if (!sched_feat(DOUBLE_TICK) && hrtimer_active(&rq_of(cfs_rq)->hrtick_timer)) return; #endif if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT)) check_preempt_tick(cfs_rq, curr); }

重点是update_curr(cfs_rq);更新了就绪队列的vruntime值。ps:cfs_rq为普通进程的就绪队列&＃xff0c;声明如下

struct cfs_rq *cfs_rq;/* rq "owned" by this entity/group: */

static inline void __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, unsigned long delta_exec)
{unsigned long delta_exec_weighted;schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max)); curr->sum_exec_runtime &＃43;&＃61; delta_exec; schedstat_add(cfs_rq, exec_clock, delta_exec); delta_exec_weighted &＃61; calc_delta_fair(delta_exec, curr); curr->vruntime &＃43;&＃61; delta_exec_weighted; update_min_vruntime(cfs_rq); }

可以看到&＃xff0c;update_curr函数首先累计了实际的运行时间(Line:7)&＃xff0c;然后调用calc_delta_fair(delta_exec,curr)对delta_exec进行加权计算(Line:9)(至于如何进行加权计算没有再深入研究)&＃xff0c;然后再将加权计算的结果累计加入vruntime(Line:11)&＃xff0c;最后更新并保存cfs_rq队列中的的最小虚拟运行时间(Line:12)。由此&＃xff0c;我们可以大概看到vruntime产生的整个过程。