手机端|
  • 手机版

  • Android APP

  • 微信公众号

您好,欢迎来到维库电子市场网  登录 | 免费注册

基于嵌入式Linux中进程调度实现方法

出处:21ic 发布于:2019-07-25 13:51:16 | 563 次阅读

  Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。
  1.前言
  处理机(CPU)是整个计算机系统的核心资源,在多进程的操作系统中,进程数往往多于处理机数,这将导致各进程互相争夺处理机。进程调度对系统功能的实现 及各方面的性能都有着决定性的影响,其实质就是把处理机公平、合理、高效地分配给各个进程。调度是实现多任务并发执行的必要手段,不同的操作系统有着不同 的调度目标。在传统的Unix类分时系统中,保证多个进程公平地使用系统资源,提供较好的响应时间是调度的主要目标;而在强实时操作系统中,总是优先级高 的任务优先获得处理机的使用权。


  Linux具有内核稳定、功能强大、可裁减、低成本等特点,非常适合嵌入式应用。但是Linux内核本身并不具备 强实时特性,且内核体积较大,因此,想要把Linux用于嵌入式系统,必须对Linux进行实时化、嵌入式化。Linux结合实时进程和非实时进程(普通 进程)自身的特点,综合了上述几种调度策略,实现了高效、灵活的进程调度。
  2.Linux进程调度分析
  2.1 Linux进程状态的描述
  Linux将进程状态描述为如下五种:
  TASK_RUNNING:可运行状态。处于该状态的进程可以被调度执行而成为当前进程。
  TASK_INTERRUPTIBLE:可中断的睡眠状态。处于该状态的进程在所需资源有效时被唤醒,也可以通过信号或定时中断唤醒。
  TASK_UNINTERRUPTIBLE:不可中断的睡眠状态。处于该状态的进程仅当所需资源有效时被唤醒。
  TASK_ZOMBIE:僵尸状态。表示进程结束且已释放资源,但其task_STruct仍未释放。
  TASK_STOPPED:暂停状态。处于该状态的进程通过其他进程的信号才能被唤醒。
  2.2 调度方式
  Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分:用户空间包含了进程本身的代码和数据;内核空间包含了操作系统的代码和数据。
  Linux采用“有条件的可剥夺”调度方式。对于普通进程,当其时间片结束时,调度程序挑选出下一个处于TASK_RUNNING状态的进程作为当前进程 (自愿调度)。对于实时进程,若其优先级足够高,则会从当前的运行进程中抢占CPU成为新的当前进程(强制调度)。发生强制调度时,若进程在用户空间中运 行,就会直接被剥夺CPU;若进程在内核空间中运行,即使迫切需要其放弃CPU,也仍要等到从它系统空间返回的前夕才被剥夺CPU。
  3.调度策略
  3.1 三种调度策略
  (1)SCHED_OTHER。SCHED_OTHER是面向普通进程的时间片轮转策略。采用该策略时,系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时,进程调度程序再选择下一个优先级相对较高的进程,并授予CPU使用权。
  (2)SCHED_FIFO。SCHED_FIFO策略适用于对响应时间要求比较高,运行所需时间比较短的实时进程。采用该策略时,各实时进程按其进入可 运行队列的顺序依次获得CPU。除了因等待某个事件主动放弃CPU,或者出现优先级更高的进程而剥夺其CPU之外,该进程将一直占用CPU运行。
  (3)SCHED_RR。SCHED_RR策略适用于对响应时间要求比较高,运行所需时间比较长的实时进程。采用该策略时,各实时进程按时间片轮流使用CPU。当一个运行进程的时间片用完后,进程调度程序停止其运行并将其置于可运行队列的末尾。
  3.2 进程调度依据
  Linux只有一个可运行队列,处于TASK_RUNNING状态的实时进程和普通进程都加入到这个可运行队列中。Linux的进程调度采用了动态优先级 和权值调控的方法,既可实现上述三种调度策略,又能保证实时进程总是比普通进程优先使用CPU。描述进程的数据结构task_struct中用以下几个数 据作为调度依据:
  Struct task_struct {
  ……
  volaTIle lONg need_resched; /*是否需要重新调度*/long counter; /*进程当前还拥有的时间片*/
  long nice; /*普通进程的动态优先级,来自UNIX系统*/unsigned long policy; /*进程调度策略*/
  unsigned long rt_priority; /*实时进程的优先级*/……
  };
  counter的值是动态变化的,进程运行时,每一个时钟滴答后,其值减1。当counter值为0时,表示该进程时间片已用完,该进程回到可运行队列中,等待再次调度。
  为保证实时进程优于普通进程,Linux采取加权处理法。在进程调度过程中,每次选取下一个运行进程时,调度程序首先给可运行队列中的每个进程赋予一个权 值weight。普通进程的权值就是其counter和优先级nice的综合,而实时进程的权值是它的rt_priority的值加1000,确保实时进 程的权值总能大于普通进程。调度程序检查可运行队列中所有进程的权值,选取权值最大者作为下一个运行进程,保证了实时 进程优先于普通进程获得CPU。 Linux使用内核函数goodness()对进程进行加权处理:
  StaTIc inline goodness (struct task_struct * pint this_cpu, struct mm_struct *this_mm){
  Int weight;
  Weight=-1;
  /*判断如果任务的调度策略被置为SCHED_YIELD的话,则置权值为-1,返回。系统调用SCHED_YIELD表示为“礼让”进程,其权值为最低*/If (p-》policy & SCHED_YIELD)
  goto out;
  /*先对普通进程进行处理(由于多数是普通进程,这样做有利于提高系统效率)*/If (p-》policy==SCHED_OTHER){
  weight=p-》counter; /*返回权值为进程的counter值*//*如果当前进程的counter为0,则表示当前进程的时间片已用完,直接返回*/If (! weight)
  Goto out;
  #Ifdef CONFIG_SMP
  If (p-》processor==this_cpu)
  Weight+=PROC_CHANGE_PENALTY;
  #Endif
  /*对进程权值进行微调,如果进程的内存空间使用当前正在运行的进程的内存空间,则权值额外加1*/If (p-》mm==this_mm||! p-》mm)
  Weight+=1;
  /*将权值加上20与进程优先级nice的差。普通进程的权值主要由counter值和nice值组成*/Weight+=20-p-》nice;
  Goto out;
  }
  /*对实时进程进行处理,返回权值为rt_priority+1000,确保优先级高于普通进程*/Weight=1000+p-》rt_priority;
  Out:
  return weight;
  }
  从goodness()函数可以看出,对于普通进程,其权值主要取决于剩余的时间配额和nice两个因素。nice的规定取值范围为19~-20,只有特 权用户才能把nice值设为负数,而表达式(20-p-》nice)掉转方向成为1~40。所以,综合的权值在时间片尚未用完时基本上是两者之和。 如果是内核进程,或者其用户空间与当前进程相同,则权值将额外加1作为奖励。对于实时进程,其权值为1000+p-》rt_priority,当 p-》counter达到0时该进程将移到队列的尾部,但其优先级仍不少于1000。可见当有实时进程就绪时,普通进程是没机会运行的。
  由此可以看出,通过goodness()函数,Linux从优先考虑实时进程出发,实现了多种调度策略的统一处理,其设计思想可谓非常巧妙。
  3.3 进程调度
  Linux的进程调度由调度程序schedule()完成,通过对schedule()的分析能更好理解调度的过程。schedule()首先判断当前运行进程是否具有SCHED_RR 标志,本文取一部分加以分析:
  if (prev-》policy==SCHED_RR) /*如果是轮转调度,先作goto特殊处理*/Goto move_rr_last;
  ……
  Move_rr_last:
  If (! prev-》counter){ /*如果counter减至0*/Prev-》counter=NICE_TO_TICKS (prev-》nice);Move_last_runqueue (prev);
  }
  Goto move_rr_back;
  prev-》counter代表当前进程的运行时间配额,其值逐渐减小。一旦减至0,就要从可执行队列runqueue中当前的位置移到末尾,宏操 作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额,即恢复其初始的时间配额。把该进程移到末尾意味着:如果没有 权值更高的进程,但是有一个权值与这相同的进程存在,那么,那个权值相同而排列在前的进程就会被选中,从而顾全了大局。
  接下来调度函数查询当前运行进程的状态是否改变:
  Move_rr_back:
  switch(prev-》state){ /*查看进程当前的状态*/Case TASK_INTERRUPTIBLE:
  if (signal pending(prev)){ /*判断运行期间是否收到信号*/Prev-》state=TASK_RUNNING;
  Break;
  }
  default: /*当前运行进程处于非TASK_RUNNING状态*/Del_from_runqueue (prev);
  Case TASK_RUNNING:
  }
  Prev-》need_resched=0;
  容易理解:如果发现进程处于TASK_INTERRUPTIBLE状态且有信号等待处理,则内核将其状态设为TASK_RUNNING,让其处理完信号, 接下来仍有机会获得CPU;如果没有信号等待,则将其从可运行队列中撤下来;如果处于TASK_RUNNING状态,则继续进行。然后,将 prev-》need_resched的值恢复成0,因为所需的调度已经在运行。
  Repeat schedule ():
  next=idle_task(this_cpu); /*next指向最佳候选进程*/c=-1000;  /*进程的综合权值,初始时是0号进程,-1000是可能的最低值*/If (prev-》state==TASK_RUNNING)
  Goto still_running;
  Still_running_back:
  List_for_each (tmp, &runqueue_head){
  P=list_entry (tmp, struct task_struct, run_list);if (can_schedule(p,this_cpu)){ /*计算p指向的进程的权值*/Int weight=goodness (p, this_cpu, prev-》active_mm);if (weight》c) /*比较权值大小*/
  C=weight, next=p;
  }
  }
  调度之前,将待调度的进程默认为0号进程,权值置为-1000。0号进程比较特别,既不会睡眠,又不能被杀死。接下来内核遍历可执行队列run queue中的每个进程,为每个进程通过goodness()函数计算出它当前所具有的权值,然后与当前的最高值c相比。如果两个进程具有相同权值的话, 那么排在前面的进程胜出。
  Still_running:
  C=goodness (prev, this_cpu, prev-》active_mm);Next=prev;
  Goto still_running_back;
  上面的代码告诉我们,如果当前进程想要继续运行,那么在挑选进程时以当前进程此刻的权值开始。这意味着,相对于权值相同的其他进程来说,当前进程优先。
  若发现当前已选进程的权值为0,则需要重新计算各个进程的时间配额,schedule()将转入recalculate部分。限于篇幅,在此不再展开。
  4.结束语
  以上结合代码简要介绍了Linux中进程调度的基本思想、依据和策略,容易发现Linux高效率和较强支持并发进程等特点。近年来,嵌入式Linux的研 究正在成为一个热点,理解Linux进程调度的原理,并在此基础上改进调度算法可能存在的缺陷,可以进一步增强其对实时性的支持,使之进一步适应在嵌入式 系统领域内的应用。

0次
关键词:嵌入式

版权与免责声明

凡本网注明“出处:维库电子市场网”的所有作品,版权均属于维库电子市场网,转载请必须注明维库电子市场网,http://www.dzsc.com,违反者本网将追究相关法律责任。

本网转载并注明自其它出处的作品,目的在于传递更多信息,并不代表本网赞同其观点或证实其内容的真实性,不承担此类作品侵权行为的直接责任及连带责任。其他媒体、网站或个人从本网转载时,必须保留本网注明的作品出处,并自负版权等法律责任。

如涉及作品内容、版权等问题,请在作品发表之日起一周内与本网联系,否则视为放弃相关权利。