精华内容
下载资源
问答
  • 进程调度
    万次阅读
    2018-08-21 17:50:08

         这里简单介绍下,进程的调度原理,调度类型和常用的进程调度算法。

    进程调度

         说道进程调度,我们或许都有个疑问,为什么需要进程调度呢?进程调度的作用是什么?

         需要进程调度的理由很充分,即充分利用计算机系统中的CPU资源,让计算机能够多快好省的完成各种任务。为此,可在内存中存放数目远大于计算机系统内CPU个数的进程,让这些进程在操作系统的进程调度器下,能够让进程高效(高的吞吐量--throughput)、及时(低延迟--latency)、公平(fairness)地使用CPU。为此调度器可设计不同的调度算法来选择进程,这体现了进程调度的策略,同时还需并进一步通过进程的上下文切换(context switch)来完成进程切换,这体现了进程调度的机制。

        总体上说,我们需要何时调度(调度的时机)、是否能够在内核执行的任意位置进行调度(调度的方式)、如果完成进程切换(上下文切换)、如果选择“合适”的进程执行(调度策略/调度算法)、如果评价选择的合理性(进程调度的指标)。了解上述细节,也就可以说是了解了进程调度。

    调度的类型(操作系统的三级调度)

       1. 作业调度--高级调度

            用于决定将外存上处于后备队列中的哪些作业调入内存,处于内存的就绪队列,准备执行。

       2. 进程调度--低级调度

            决定就绪队列中那个进程将获得处理机

       3. 交换调度--中级调度

             目的是提高内存的利用率和系统的吞吐量

    调度的时机

        什么时候会发生进程调度呢,引起进程调度的因素有哪些,这些也就是进程的调度时机。

       1. 正在执行的进程执行完毕

       2. 执行中的进程因提出I/O请求或发生等事件而暂停执行。

       3. 时间片完成

       4. 在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)阻塞

       5. 高优先者进入

    调度的方式

         这里按照是否剥夺的方式分为两种调度方式。

        1. 非剥夺方式(非抢占方式)

             一旦占用CPU,直至完成或阻塞

            不利用实时任务,不利用短作业;使用于批处理系统   

        2. 剥夺方式(抢占方式)    

            在一定情况下,可剥夺一进程占有的处理机

            抢占的原则有:短作业(进程)优先原则、时间片原则、优先权原则。

    调度算法

    • 先来先服务调度算法(FCFS)

          处于就绪态的进程按先后顺序链入到就绪队列中,而FCFS调度算法按就绪进程进入就绪队列的先后次序选择当前最先进入就绪队列的进程来执行,直到此进程阻塞或结束,才进行下一次的进程选择调度。

         特点:FCFS调度算法利于长作业,不利于短作业。

    • 短作业优先调度算法(SJF)

          选择就绪队列中确切(或估计)运行时间最短的进程进入执行。它既可采用可抢占调度方式,也可采用不可抢占调度方式。

          特点:有效降低作业的平均等待时间和提高系统的吞吐量。

    • 时间片轮转调度算法(RR)

         RR调度算法定义了一个的时间单元,称为时间片(或时间量)。一个时间片通常在1~100 ms之间。当正在运行的进程用完了时间片后,即使此进程还要运行,操作系统也不让它继续运行,而是从就绪队列依次选择下一个处于就绪态的进程执行,而被剥夺CPU使用的进程返回到就绪队列的末尾,等待再次被调度。

         特点:简单易行、平均响应时间短。此算法不利于处理紧急作业

         注:时间片的大小可调整,如果时间片大到让一个进程足以完成其全部工作,这种算法就退化为FCFS调度算法;若时间片设置得很小,那么处理机在进程之间的进程上下文切换工作过于频繁,使得真正用于运行用户程序的时间减少。时间片可以静态设置好,也可根据系统当前负载状况和运行情况动态调整,时间片大小的动态调整需要考虑就绪态进程个数、进程上下文切换开销、系统吞吐量、系统响应时间等多方面因素。

    • 高响应比优先调度算法(HRRF)

         HRRF调度算法是介于先来先服务算法与最短进程优先算法之间的一种折中算法。先来先服务算法只考虑进程的等待时间而忽视了进程的执行时间,而最短进程优先调度算法只考虑用户估计的进程的执行时间而忽视了就绪进程的等待时间。为此需要定义响应比Rp: 

    • Rp=(等待时间+预计执行时间)/执行时间=响应时间/执行时间
      

     Rp较大的进程执行。

         特点:既考虑进程等待时间,又考虑进程的执行时间。 但HRRF调度算法需要每次计算各各个进程的响应比Rp,这会带来较大的时间开销(特别是在就绪进程个数多的情况下)。

    • 多级反馈队列调度算法(MLFQ)

        多级反馈队列调度算法是一种CPU处理机调度算法,UNIX操作系统采取的便是这种调度算法。设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二队次之,其余队列优先级依次降低。

       多级反馈队列调度算法描述:
      1、进程在进入待调度的队列等待时,首先进入优先级最高的Q1等待。
      2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程。例如:Q1,Q2,Q3三个队列,只有在Q1中没有进程等待时才去调度Q2,同理,只有Q1,Q2都为空时才会去调度Q3。
      3、对于同一个队列中的各个进程,按照时间片轮转法调度。比如Q1队列的时间片为N,那么Q1中的作业在经历了N个时间片后若还没有完成,则进入Q2队列等待,若Q2的时间片用完后作业还不能完成,一直进入下一级队列,直至完成。
      4、在低优先级的队列中的进程在运行时,又有新到达的作业,那么在运行完这个时间片后,CPU马上分配给新到达的作业(抢占式)。

    • 最高优先级优先调度算法

           进程的优先级用于表示进程的重要性及运行的优先性。一个进程的优先级可分为两种:静态优先级和动态优先级。

          静态优先级是在创建进程时确定的。一旦确定后,在整个进程运行期间不再改变。静态优先级一般由用户依据包括进程的类型、进程所使用的资源、进程的估计运行时间等因素来设置。一般而言,若进程需要的资源越多、估计运行的时间越长,则进程的优先级越低;反之,对于I/O bounded的进程可以把优先级设置得高。

          动态优先级是指在进程运行过程中,根据进程执行情况的变化来调整优先级。动态优先级一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间越长,则优先级越低,等待时间越长,优先级越高。那么进程调度器将根据静态优先级和动态优先级的总和现在优先级最高的就绪进程执行。

     

    这里简单的介绍进程的调度以及进程的调度算法。具体实现可详见下面的博客:

    https://chyyuu.gitbooks.io/simple_os_book/content/zh/chapter-4/process_schedule_principal.html

    https://blog.csdn.net/leex_brave/article/details/51638300

      

            

     

    更多相关内容
  • 利用c++模拟进程调度。模拟操作系统内核对进程的控制和管理:包括进程创建和撤销、进程状态的切换和简单的内存空间管理。  能够模拟进程创建与撤销过程;(4 分)  对进程的状态进行全面的控制;(4 分) ...
  • 编写程序完成单处理器系统中的进程调度, 要求实现时间片轮转、 优先数、 最短进程优 先和最短剩余时间优先四种调度算法。 实验具体包括: 首先确定进程控制块的内容, 进程控 制块的组成方式; 然后完成进程创建...
  • 进程创建、终止、阻塞、调度、唤醒原语有助于对操作系统中近程功能的了解,掌握操作系统模块的设计方法和工作原理
  • 编写一个单处理机下的进程调度程序,模拟操作系统对进程的调度。 要求: 1.能够创建指定数量的进程,每个进程一个进程控制块表示。 2.实现先来先服务调度算法:进程到达时间可由进程创建时间表示。 3.实现短作业...
  • C语言,运行成功,比较基础,c语言模拟设计一个有N个进程运行的进程调度程序,用最高优先数优先法:在创建进程时,给定一个进程优先数,并按一定规则减少优先数,直至所有进程运行完成(例如进程每获得一次cpu进程数...
  • 2. 用高级语言编写和调试一个进程调度程序,以加深对进程调度算法的理解。 【实验准备】 1. 几种进程调度算法  短进程优先调度算法  高优先权优先调度算法  先来先服务调度算法  基于时间片的轮转调度算法...
  • 它因创建而产生,因调度而运行,因等待资源或事件而被处于等待状态,因完成任务而被撤消,反映了一个程序在一定的数据集上运行的全部动态过程。  线程(Thread)是进程的一个实体,是CPU调度和分派的基本单位。...
  • 编写一个单处理机下的进程调度程序,模拟操作系统对进程的调度。 要求: 能够创建指定数量的进程,每个进程一个进程控制块表示。 实现先来先服务调度算法:进程到达时间可由进程创建时间表示。 实现短作业...
  • 编写程序完成单处理机系统中的进程调度,要求采用时间片轮转调度算法。实验具体包括:首先确定进程控制块的内容,进程控制块的组成方式;然后完成进程创建原语和进程调度原语;最后编写主函数对所作工作进程测试。 ...
  • 进程调度原理

    千次阅读 2018-07-18 10:22:03
    Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;  3.保证...

     Linux进程调度的目标

        1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;

        2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;

        3.保证公平和避免饥渴;

        4.SMP调度:调度程序必须支持多处理系统;

        5.软实时调度:系统必须有效的调用实时进程,但不保证一定满足其要求;

    Linux进程优先级

      进程提供了两种优先级,一种是普通的进程优先级,第二个是实时优先级。前者适用SCHED_NORMAL调度策略,后者可选SCHED_FIFO或SCHED_RR调度策略。任何时候,实时进程的优先级都高于普通进程,实时进程只会被更高级的实时进程抢占,同级实时进程之间是按照FIFO(一次机会做完)或者RR(多次轮转)规则调度的。

      首先,说下实时进程的调度

      实时进程,只有静态优先级,因为内核不会再根据休眠等因素对其静态优先级做调整,其范围在0~MAX_RT_PRIO-1间。默认MAX_RT_PRIO配置为100,也即,默认的实时优先级范围是0~99。而nice值,影响的是优先级在MAX_RT_PRIO~MAX_RT_PRIO+40范围内的进程。

      不同与普通进程,系统调度时,实时优先级高的进程总是先于优先级低的进程执行。知道实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。如果有数个 优先级相同的实时进程,那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a,而此时有个优先级为b的实时进程B进入可运行状态,那么只要b<a,系统将中断A的执行,而优先执行B,直到B无法执行(无论A,B为何种实时进程)。

       不同调度策略的实时进程只有在相同优先级时才有可比性:

       1. 对于FIFO的进程,意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。

       2. 对于RR的进程。一旦时间片消耗完毕,则会将该进程置于队列的末尾,然后运行其他相同优先级的进程,如果没有其他相同优先级的进程,则该进程会继续执行。

       总而言之,对于实时进程,高优先级的进程就是大爷。它执行到没法执行了,才轮到低优先级的进程执行。等级制度相当森严啊。

      重头戏,说下非实时进程调度

      引子 

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    将当前目录下的documents目录打包,但不希望tar占用太多CPU:

     

    nice -19 tar zcf pack.tar.gz documents

     

    这个“-19”中的“-”仅表示参数前缀;所以,如果希望赋予tar进程最高的优先级,则执行:

     

    nice --19 tar zcf pack.tar.gz documents

     

    也可修改已经存在的进程的优先级:

     

    将PID为1799的进程优先级设置为最低:

     

    renice 19 1799

     

    renice命令与nice命令的优先级参数的形式是相反的,直接以优先级值作为参数即可,无“-”前缀说法。

       言归正传

        Linux对普通的进程,根据动态优先级进行调度。而动态优先级是由静态优先级(static_prio)调整而来。Linux下,静态优先级是用户不可见的,隐藏在内核中。而内核提供给用户一个可以影响静态优先级的接口,那就是nice值,两者关系如下:

      static_prio=MAX_RT_PRIO +nice+ 20

      nice值的范围是-20~19,因而静态优先级范围在100~139之间。nice数值越大就使得static_prio越大,最终进程优先级就越低。

      ps -el 命令执行结果:NI列显示的每个进程的nice值,PRI是进程的优先级(如果是实时进程就是静态优先级,如果是非实时进程,就是动态优先级)  

      而进程的时间片就是完全依赖 static_prio 定制的,见下图,摘自《深入理解linux内核》,

      

       我们前面也说了,系统调度时,还会考虑其他因素,因而会计算出一个叫进程动态优先级的东西,根据此来实施调度。因为,不仅要考虑静态优先级,也要考虑进程的属性。例如如果进程属于交互式进程,那么可以适当的调高它的优先级,使得界面反应地更加迅速,从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。Linux2.6认为,交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多,则越有可能属于交互式进程。则系统调度时,会给该进程更多的奖励(bonus),以便该进程有更多的机会能够执行。奖励(bonus)从0到10不等。

      系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态,或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素:静态优先级,进程的平均睡眠时间也即bonus。计算公式如下,

         dynamic_prio = max (100, min (static_prio - bonus + 5, 139))

      在调度时,Linux2.6 使用了一个小小的trick,就是算法中经典的空间换时间的思想[还没对照源码确认],使得计算最优进程能够在O(1)的时间内完成。

      为什么根据睡眠和运行时间确定奖惩分数是合理的

      睡眠和CPU耗时反应了进程IO密集和CPU密集两大瞬时特点,不同时期,一个进程可能即是CPU密集型也是IO密集型进程。对于表现为IO密集的进程,应该经常运行,但每次时间片不要太长。对于表现为CPU密集的进程,CPU不应该让其经常运行,但每次运行时间片要长。交互进程为例,假如之前其其大部分时间在于等待CPU,这时为了调高相应速度,就需要增加奖励分。另一方面,如果此进程总是耗尽每次分配给它的时间片,为了对其他进程公平,就要增加这个进程的惩罚分数。可以参考CFS的virtutime机制.

    现代方法CFS

      不再单纯依靠进程优先级绝对值,而是参考其绝对值,综合考虑所有进程的时间,给出当前调度时间单位内其应有的权重,也就是,每个进程的权重X单位时间=应获cpu时间,但是这个应得的cpu时间不应太小(假设阈值为1ms),否则会因为切换得不偿失。但是,当进程足够多时候,肯定有很多不同权重的进程获得相同的时间——最低阈值1ms,所以,CFS只是近似完全公平。

        详情参考 《linux内核cfs浅析

    Linux进程状态机

     

      

     

      进程是通过fork系列的系统调用(fork、clone、vfork)来创建的,内核(或内核模块)也可以通过kernel_thread函数创建内核进程。这些创建子进程的函数本质上都完成了相同的功能——将调用进程复制一份,得到子进程。(可以通过选项参数来决定各种资源是共享、还是私有。)
    那么既然调用进程处于TASK_RUNNING状态(否则,它若不是正在运行,又怎么进行调用?),则子进程默认也处于TASK_RUNNING状态。
    另外,在系统调用clone和内核函数kernel_thread也接受CLONE_STOPPED选项,从而将子进程的初始状态置为 TASK_STOPPED。

       进程创建后,状态可能发生一系列的变化,直到进程退出。而尽管进程状态有好几种,但是进程状态的变迁却只有两个方向——从TASK_RUNNING状态变为非TASK_RUNNING状态、或者从非TASK_RUNNING状态变为TASK_RUNNING状态。总之,TASK_RUNNING是必经之路,不可能两个非RUN状态直接转换。

    也就是说,如果给一个TASK_INTERRUPTIBLE状态的进程发送SIGKILL信号,这个进程将先被唤醒(进入TASK_RUNNING状态),然后再响应SIGKILL信号而退出(变为TASK_DEAD状态)。并不会从TASK_INTERRUPTIBLE状态直接退出。

        进程从非TASK_RUNNING状态变为TASK_RUNNING状态,是由别的进程(也可能是中断处理程序)执行唤醒操作来实现的。执行唤醒的进程设置被唤醒进程的状态为TASK_RUNNING,然后将其task_struct结构加入到某个CPU的可执行队列中。于是被唤醒的进程将有机会被调度执行。

       而进程从TASK_RUNNING状态变为非TASK_RUNNING状态,则有两种途径:

      1、响应信号而进入TASK_STOPED状态、或TASK_DEAD状态;
      2、执行系统调用主动进入TASK_INTERRUPTIBLE状态(如nanosleep系统调用)、或TASK_DEAD状态(如exit系统调用);或由于执行系统调用需要的资源得不到满     足,而进入TASK_INTERRUPTIBLE状态或TASK_UNINTERRUPTIBLE状态(如select系统调用)。
      显然,这两种情况都只能发生在进程正在CPU上执行的情况下。

     通过ps命令我们能够查看到系统中存在的进程,以及它们的状态:

    R(TASK_RUNNING),可执行状态。

    只有在该状态的进程才可能在CPU上运行。而同一时刻可能有多个进程处于可执行状态,这些进程的task_struct结构(进程控制块)被放入对应CPU的可执行队列中(一个进程最多只能出现在一个CPU的可执行队列中)。进程调度器的任务就是从各个CPU的可执行队列中分别选择一个进程在该CPU上运行。
    只要可执行队列不为空,其对应的CPU就不能偷懒,就要执行其中某个进程。一般称此时的CPU“忙碌”。对应的,CPU“空闲”就是指其对应的可执行队列为空,以致于CPU无事可做。
    有人问,为什么死循环程序会导致CPU占用高呢?因为死循环程序基本上总是处于TASK_RUNNING状态(进程处于可执行队列中)。除非一些非常极端情况(比如系统内存严重紧缺,导致进程的某些需要使用的页面被换出,并且在页面需要换入时又无法分配到内存……),否则这个进程不会睡眠。所以CPU的可执行队列总是不为空(至少有这么个进程存在),CPU也就不会“空闲”。

    很多操作系统教科书将正在CPU上执行的进程定义为RUNNING状态、而将可执行但是尚未被调度执行的进程定义为READY状态,这两种状态在linux下统一为 TASK_RUNNING状态。

    S(TASK_INTERRUPTIBLE),可中断的睡眠状态。

    处于这个状态的进程因为等待某某事件的发生(比如等待socket连接、等待信号量),而被挂起。这些进程的task_struct结构被放入对应事件的等待队列中。当这些事件发生时(由外部中断触发、或由其他进程触发),对应的等待队列中的一个或多个进程将被唤醒。

    通过ps命令我们会看到,一般情况下,进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态(除非机器的负载很高)。毕竟CPU就这么一两个,进程动辄几十上百个,如果不是绝大多数进程都在睡眠,CPU又怎么响应得过来。

    D(TASK_UNINTERRUPTIBLE),不可中断的睡眠状态。

    与TASK_INTERRUPTIBLE状态类似,进程处于睡眠状态,但是此刻进程是不可中断的。不可中断,指的并不是CPU不响应外部硬件的中断,而是指进程不响应异步信号。
    绝大多数情况下,进程处在睡眠状态时,总是应该能够响应异步信号的。否则你将惊奇的发现,kill -9竟然杀不死一个正在睡眠的进程了!于是我们也很好理解,为什么ps命令看到的进程几乎不会出现TASK_UNINTERRUPTIBLE状态,而总是TASK_INTERRUPTIBLE状态。

    而TASK_UNINTERRUPTIBLE状态存在的意义就在于,内核的某些处理流程是不能被打断的。如果响应异步信号,程序的执行流程中就会被插入一段用于处理异步信号的流程(这个插入的流程可能只存在于内核态,也可能延伸到用户态),于是原有的流程就被中断了(参见《linux异步信号handle浅析》)。
    在进程对某些硬件进行操作时(比如进程调用read系统调用对某个设备文件进行读操作,而read系统调用最终执行到对应设备驱动的代码,并与对应的物理设备进行交互),可能需要使用TASK_UNINTERRUPTIBLE状态对进程进行保护,以避免进程与设备交互的过程被打断,造成设备陷入不可控的状态。(比如read系统调用触发了一次磁盘到用户空间的内存的DMA,如果DMA进行过程中,进程由于响应信号而退出了,那么DMA正在访问的内存可能就要被释放了。)这种情况下的TASK_UNINTERRUPTIBLE状态总是非常短暂的,通过ps命令基本上不可能捕捉到。

    linux系统中也存在容易捕捉的TASK_UNINTERRUPTIBLE状态。执行vfork系统调用后,父进程将进入TASK_UNINTERRUPTIBLE状态,直到子进程调用exit或exec。
    通过下面的代码就能得到处于TASK_UNINTERRUPTIBLE状态的进程:
    #include <unistd.h>
    void main() {
    if (!vfork()) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    4371 pts/0 D+ 0:00 ./a.out
    4372 pts/0 S+ 0:00 ./a.out
    4374 pts/1 S+ 0:00 grep a.out
    然后我们可以试验一下TASK_UNINTERRUPTIBLE状态的威力。不管kill还是kill -9,这个TASK_UNINTERRUPTIBLE状态的父进程依然屹立不倒。

    T(TASK_STOPPED or TASK_TRACED),暂停状态或跟踪状态。

    向进程发送一个SIGSTOP信号,它就会因响应该信号而进入TASK_STOPPED状态(除非该进程本身处于TASK_UNINTERRUPTIBLE状态而不响应信号)。(SIGSTOP与SIGKILL信号一样,是非常强制的。不允许用户进程通过signal系列的系统调用重新设置对应的信号处理函数。)
    向进程发送一个SIGCONT信号,可以让其从TASK_STOPPED状态恢复到TASK_RUNNING状态。

    当进程正在被跟踪时,它处于TASK_TRACED这个特殊的状态。“正在被跟踪”指的是进程暂停下来,等待跟踪它的进程对它进行操作。比如在gdb中对被跟踪的进程下一个断点,进程在断点处停下来的时候就处于TASK_TRACED状态。而在其他时候,被跟踪的进程还是处于前面提到的那些状态。
    对于进程本身来说,TASK_STOPPED和TASK_TRACED状态很类似,都是表示进程暂停下来。
    而TASK_TRACED状态相当于在TASK_STOPPED之上多了一层保护,处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒。只能等到调试进程通过ptrace系统调用执行PTRACE_CONT、PTRACE_DETACH等操作(通过ptrace系统调用的参数指定操作),或调试进程退出,被调试的进程才能恢复TASK_RUNNING状态。

    Z(TASK_DEAD - EXIT_ZOMBIE),退出状态,进程成为僵尸进程。

    进程在退出的过程中,处于TASK_DEAD状态。

    在这个退出过程中,进程占有的所有资源将被回收,除了task_struct结构(以及少数资源)以外。于是进程就只剩下task_struct这么个空壳,故称为僵尸。
    之所以保留task_struct,是因为task_struct里面保存了进程的退出码、以及一些统计信息。而其父进程很可能会关心这些信息。比如在shell中,$?变量就保存了最后一个退出的前台进程的退出码,而这个退出码往往被作为if语句的判断条件。
    当然,内核也可以将这些信息保存在别的地方,而将task_struct结构释放掉,以节省一些空间。但是使用task_struct结构更为方便,因为在内核中已经建立了从pid到task_struct查找关系,还有进程间的父子关系。释放掉task_struct,则需要建立一些新的数据结构,以便让父进程找到它的子进程的退出信息。

    父进程可以通过wait系列的系统调用(如wait4、waitid)来等待某个或某些子进程的退出,并获取它的退出信息。然后wait系列的系统调用会顺便将子进程的尸体(task_struct)也释放掉。
    子进程在退出的过程中,内核会给其父进程发送一个信号,通知父进程来“收尸”。这个信号默认是SIGCHLD,但是在通过clone系统调用创建子进程时,可以设置这个信号。

    通过下面的代码能够制造一个EXIT_ZOMBIE状态的进程:
    #include <unistd.h>
    void main() {
    if (fork())
    while(1) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    10410 pts/0 S+ 0:00 ./a.out
    10411 pts/0 Z+ 0:00 [a.out] <defunct>
    10413 pts/1 S+ 0:00 grep a.out

    只要父进程不退出,这个僵尸状态的子进程就一直存在。那么如果父进程退出了呢,谁又来给子进程“收尸”?
    当进程退出的时候,会将它的所有子进程都托管给别的进程(使之成为别的进程的子进程)。托管给谁呢?可能是退出进程所在进程组的下一个进程(如果存在的话),或者是1号进程。所以每个进程、每时每刻都有父进程存在。除非它是1号进程。

    1号进程,pid为1的进程,又称init进程。
    linux系统启动后,第一个被创建的用户态进程就是init进程。它有两项使命:
    1、执行系统初始化脚本,创建一系列的进程(它们都是init进程的子孙);
    2、在一个死循环中等待其子进程的退出事件,并调用waitid系统调用来完成“收尸”工作;
    init进程不会被暂停、也不会被杀死(这是由内核来保证的)。它在等待子进程退出的过程中处于TASK_INTERRUPTIBLE状态,“收尸”过程中则处于TASK_RUNNING状态。

    X(TASK_DEAD - EXIT_DEAD),退出状态,进程即将被销毁。

    而进程在退出过程中也可能不会保留它的task_struct。比如这个进程是多线程程序中被detach过的进程(进程?线程?参见《linux线程浅析》)。或者父进程通过设置SIGCHLD信号的handler为SIG_IGN,显式的忽略了SIGCHLD信号。(这是posix的规定,尽管子进程的退出信号可以被设置为SIGCHLD以外的其他信号。)
    此时,进程将被置于EXIT_DEAD退出状态,这意味着接下来的代码立即就会将该进程彻底释放。所以EXIT_DEAD状态是非常短暂的,几乎不可能通过ps命令捕捉到。

     

    一些重要的杂项

    调度程序的效率
    “优先级”明确了哪个进程应该被调度执行,而调度程序还必须要关心效率问题。调度程序跟内核中的很多过程一样会频繁被执行,如果效率不济就会浪费很多CPU时间,导致系统性能下降。
    在linux 2.4时,可执行状态的进程被挂在一个链表中。每次调度,调度程序需要扫描整个链表,以找出最优的那个进程来运行。复杂度为O(n);
    在linux 2.6早期,可执行状态的进程被挂在N(N=140)个链表中,每一个链表代表一个优先级,系统中支持多少个优先级就有多少个链表。每次调度,调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率,复杂度为O(1);
    在linux 2.6近期的版本中,可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

    那么,为什么从linux 2.6早期到近期linux 2.6版本,调度程序选择进程时的复杂度反而增加了呢?
    这是因为,与此同时,调度程序对公平性的实现从上面提到的第一种思路改变为第二种思路(通过动态调整优先级实现)。而O(1)的算法是基于一组数目不大的链表来实现的,按我的理解,这使得优先级的取值范围很小(区分度很低),不能满足公平性的需求。而使用红黑树则对优先级的取值没有限制(可以用32位、64位、或更多位来表示优先级的值),并且O(logN)的复杂度也还是很高效的。

    调度触发的时机
    调度的触发主要有如下几种情况:
    1、当前进程(正在CPU上运行的进程)状态变为非可执行状态。
    进程执行系统调用主动变为非可执行状态。比如执行nanosleep进入睡眠、执行exit退出、等等;
    进程请求的资源得不到满足而被迫进入睡眠状态。比如执行read系统调用时,磁盘高速缓存里没有所需要的数据,从而睡眠等待磁盘IO;
    进程响应信号而变为非可执行状态。比如响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等;

    2、抢占。进程运行时,非预期地被剥夺CPU的使用权。这又分两种情况:进程用完了时间片、或出现了优先级更高的进程。
    优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒,或因为释放互斥对象(如释放锁)而被唤醒;
    内核在响应时钟中断的过程中,发现当前进程的时间片用完;
    内核在响应中断的过程中,发现优先级更高的进程所等待的外部资源的变为可用,从而将其唤醒。比如CPU收到网卡中断,内核处理该中断,发现某个socket可读,于是唤醒正在等待读这个socket的进程;再比如内核在处理时钟中断的过程中,触发了定时器,从而唤醒对应的正在nanosleep系统调用中睡眠的进程;

    内核抢占
    理想情况下,只要满足“出现了优先级更高的进程”这个条件,当前进程就应该被立刻抢占。但是,就像多线程程序需要用锁来保护临界区资源一样,内核中也存在很多这样的临界区,不大可能随时随地都能接收抢占。
    linux 2.4时的设计就非常简单,内核不支持抢占。进程运行在内核态时(比如正在执行系统调用、正处于异常处理函数中),是不允许抢占的。必须等到返回用户态时才会触发调度(确切的说,是在返回用户态之前,内核会专门检查一下是否需要调度);
    linux 2.6则实现了内核抢占,但是在很多地方还是为了保护临界区资源而需要临时性的禁用内核抢占。

    也有一些地方是出于效率考虑而禁用抢占,比较典型的是spin_lock。spin_lock是这样一种锁,如果请求加锁得不到满足(锁已被别的进程占有),则当前进程在一个死循环中不断检测锁的状态,直到锁被释放。
    为什么要这样忙等待呢?因为临界区很小,比如只保护“i+=j++;”这么一句。如果因为加锁失败而形成“睡眠-唤醒”这么个过程,就有些得不偿失了。
    那么既然当前进程忙等待(不睡眠),谁又来释放锁呢?其实已得到锁的进程是运行在另一个CPU上的,并且是禁用了内核抢占的。这个进程不会被其他进程抢占,所以等待锁的进程只有可能运行在别的CPU上。(如果只有一个CPU呢?那么就不可能存在等待锁的进程了。)
    而如果不禁用内核抢占呢?那么得到锁的进程将可能被抢占,于是可能很久都不会释放锁。于是,等待锁的进程可能就不知何年何月得偿所望了。

    对于一些实时性要求更高的系统,则不能容忍spin_lock这样的东西。宁可改用更费劲的“睡眠-唤醒”过程,也不能因为禁用抢占而让更高优先级的进程等待。比如,嵌入式实时linux montavista就是这么干的。
    由此可见,实时并不代表高效。很多时候为了实现“实时”,还是需要对性能做一定让步的。

    多处理器下的负载均衡
    前面我们并没有专门讨论多处理器对调度程序的影响,其实也没有什么特别的,就是在同一时刻能有多个进程并行地运行而已。那么,为什么会有“多处理器负载均衡”这个事情呢?
    如果系统中只有一个可执行队列,哪个CPU空闲了就去队列中找一个最合适的进程来执行。这样不是很好很均衡吗?
    的确如此,但是多处理器共用一个可执行队列会有一些问题。显然,每个CPU在执行调度程序时都需要把队列锁起来,这会使得调度程序难以并行,可能导致系统性能下降。而如果每个CPU对应一个可执行队列则不存在这样的问题。
    另外,多个可执行队列还有一个好处。这使得一个进程在一段时间内总是在同一个CPU上执行,那么很可能这个CPU的各级cache中都缓存着这个进程的数据,很有利于系统性能的提升。
    所以,在linux下,每个CPU都有着对应的可执行队列,而一个可执行状态的进程在同一时刻只能处于一个可执行队列中。

    于是,“多处理器负载均衡”这个麻烦事情就来了。内核需要关注各个CPU可执行队列中的进程数目,在数目不均衡时做出适当调整。什么时候需要调整,以多大力度进程调整,这些都是内核需要关心的。当然,尽量不要调整最好,毕竟调整起来又要耗CPU、又要锁可执行队列,代价还是不小的。
    另外,内核还得关心各个CPU的关系。两个CPU之间,可能是相互独立的、可能是共享cache的、甚至可能是由同一个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要依据。关系越紧密,进程在它们之间迁移的代价就越小。参见《linux内核SMP负载均衡浅析》。

    优先级继承
    由于互斥,一个进程(设为A)可能因为等待进入临界区而睡眠。直到正在占有相应资源的进程(设为B)退出临界区,进程A才被唤醒。
    可能存在这样的情况:A的优先级非常高,B的优先级非常低。B进入了临界区,但是却被其他优先级较高的进程(设为C)抢占了,而得不到运行,也就无法退出临界区。于是A也就无法被唤醒。
    A有着很高的优先级,但是现在却沦落到跟B一起,被优先级并不太高的C抢占,导致执行被推迟。这种现象就叫做优先级反转。

    出现这种现象是很不合理的。较好的应对措施是:当A开始等待B退出临界区时,B临时得到A的优先级(还是假设A的优先级高于B),以便顺利完成处理过程,退出临界区。之后B的优先级恢复。这就是优先级继承的方法。

    中断处理线程化
    在linux下,中断处理程序运行于一个不可调度的上下文中。从CPU响应硬件中断自动跳转到内核设定的中断处理程序去执行,到中断处理程序退出,整个过程是不能被抢占的。
    一个进程如果被抢占了,可以通过保存在它的进程控制块(task_struct)中的信息,在之后的某个时间恢复它的运行。而中断上下文则没有task_struct,被抢占了就没法恢复了。
    中断处理程序不能被抢占,也就意味着中断处理程序的“优先级”比任何进程都高(必须等中断处理程序完成了,进程才能被执行)。但是在实际的应用场景中,可能某些实时进程应该得到比中断处理程序更高的优先级。
    于是,一些实时性要求更高的系统就给中断处理程序赋予了task_struct以及优先级,使得它们在必要的时候能够被高优先级的进程抢占。但是显然,做这些工作是会给系统造成一定开销的,这也是为了实现“实时”而对性能做出的一种让步。

     

    参考文献:《linux内核设计与实现》

           《现代操作系统》

           《进程调度的红黑树实现分析

         《linux内核SMP负载均衡浅析》(本文未引用可以做拓展参考)

         《linux内核cfs浅析

     

    转自http://www.cnblogs.com/zhaoyl/archive/2012/09/04/2671156.html

    展开全文
  • Linux进程管理与调度

    千次阅读 2019-04-27 19:15:51
    三、进程创建与终止 四、用户线程,内核线程和轻量级进程 五、三种线程模型和Linux线程实现 六、进程与线程的区别 七、实时线程与实时操作系统 八、进程(线程)调度 一、进程描述符 进程描述符保存了与...

    目录

    一、进程描述符     

    二、进程切换

    三、进程创建与终止

    四、用户线程,内核线程和轻量级进程

     五、三种线程模型和Linux线程实现

    六、进程与线程的区别

    七、实时线程与实时操作系统

    八、进程(线程)调度


    一、进程描述符     

         进程描述符保存了与进程相关的一切信息,其数据类型为task_struct,Linux用双向链表和类似HashMap的散列表来保存所有的进程描述符,前者用于调度按照进程优先级快速选择一个可执行的进程,后者用于按照进程pid或者tgid快速查找一个进程或者进程组,给其发送信号等操作。进程描述符中包含很多的字段,重点关注一下几个:

    (1) 、state字段

          表示进程的状态,共有6种:

          1、TASK_RUNNING,表示进程要么正在执行,要么准备执行,等待cpu时间片的调度

          2、TASK_INTERRUPTIBLE,表示进程被挂起(睡眠),直到某个条件成立触发CPU中断或者发送信号唤醒该进程,将其状态改成TASK_RUNNING,比如某个TASK_RUNNING的进程需要读取文件,发起系统调用从用户态进入内核态,内核将其状态改成TASK_INTERRUPTIBLE,然后调用磁盘驱动程序读取文件,CPU执行其他任务;待磁盘读取文件完毕,磁盘发送CPU中断信号,CPU将读取的文件内容传给进程,进程由内核态切换到用户态,处理文件内容。一般情况下,进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态,除非机器的负载很高。

          3、TASK_UNINTERRUPTIBLE,与TASK_INTERRUPTIBLE类似,区别是不能被外部信号唤醒,只能通过CPU中断唤醒。该状态总是非常短暂的,通过ps命令基本上不可能捕捉,主要用于避免内核某些处理过程被中断,如进程与设备交互的过程,中断会造成设备陷入不可控的状态。

         4、TASK_STOPPED,表示进程的执行已停止,向进程发送一个SIGSTOP,SIGTSTP,SIGTTIN,SIGTTOU信号,它就会因响应该信号而进入TASK_STOPPED状态,向进程发送一个向进程SIGCONT信号,可以让其恢复到TASK_RUNNING状态。

        5、TASK_TRACED,表示进程的执行已停止,等待跟踪它的进程对它进行操作,比如在gdb中对被跟踪的进程下一个断点,进程在断点处停下来的时候就处于TASK_TRACED状态。处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒,只能等到调试进程通过ptrace系统调用执行PTRACE_CONT、PTRACE_DETACH等操作或调试进程退出,被调试的进程才能恢复TASK_RUNNING状态。

        6、EXIT_ZOMBIE,表示进程已终止,正等待其父进程执行wait类系统调用收集关于它的一些统计信息如退出码,内核此时无法回收该进程的进程描述符。如果父进程未执行wait类系统调用并退出了,子进程会转交给上一级的父进程,直到最终的init进程,由上一级父进程执行wait类系统调用。

      7、EXIT_DEAD,表示进程已终止,父进程已经执行wait类系统调用,进程即将被内核删除,该状态非常短暂。

          Linux Kernel 2.6.25 引入了一种新的进程睡眠状态,TASK_KILLABLE:当进程处于这种可以终止的新睡眠状态中,它的运行原理类似于 TASK_UNINTERRUPTIBLE,只不过可以响应致命信号。     

    (2)、pid和tgid字段

       pid标识一个唯一的进程,从0开始逐渐递增,到最大值后就开始利用空闲的未分配pid;tgid标识当前进程所属的进程组的id,在Linux系统中,该ID就是该进程组的领头进程(该组中的第一个轻量级进程)相同的PID。

    (3)、stack字段

        该字段是一个指针变量,表示当前进程的thread_info的地址,thread_info和内核态堆栈紧挨着,存放在两个连续的页框中,通过thread_info中的进程描述符指针快速访问进程描述符,其结构如下图:

    图中,esp寄存器用来存放栈顶单元的地址。在80x86系统中,栈起始于顶端,并朝着这个内存区开始的方向增长。从用户态刚切换到内核态以后,进程的内核栈总是空的。因此,esp寄存器指向这个栈的顶端。一旦数据写入堆栈,esp的值就递减。为了快速获取当前CPU上运行进程的task_struct结构,内核提供了current宏, 该宏就是通过esp寄存器保存的栈顶地址快速获取对应的task_struct。

    (4)、mm和active_mm字段

           mm标识进程所拥有的用户空间内存描述符,内核线程无的mm为NULL;active_mm指向进程运行时所使用的内存描述符, 对于普通进程而言,这两个指针变量的值相同。但是内核线程kernel thread是没有进程地址空间的,所以内核线程的tsk->mm域是空(NULL)。但是内核线程需要访问内核空间,因为所有进程的内核空间都一样,所以它的active_mm成员被初始化为前一个运行进程的mm值,借此访问内核空间。

    (5)、thread 字段

            该字段是一个指针变量,数据结构为thread_struct,用于进程切换时保存除通用寄存器以外的寄存器的内容,用于恢复进程执行上下文使用,跟CPU架构强相关。通用寄存器的内容保存在内核堆栈中。

         参考:Linux进程状态解析 之 R、S、D、T、Z、X (主要有三个状态)

                   TASK_KILLABLE:Linux 中的新进程状态

                   Linux进程描述符task_struct结构体详解--Linux进程的管理与调度(一)

                   Linux进程地址管理之mm_struct

                   linux thread_info 与thread_struct

    二、进程切换

         因为所有进程共享CPU寄存器,所以在恢复一个进程的执行前,内核必须确保每个寄存器装入了挂起进程时的值。进程恢复执行前必须装入寄存器的一组数据称为硬件上下文,是进程的可执行上下文的子集。

         早期Linux以硬件方式切换进程:x86架构下,每个进程有一个TSS(task state segment)任务状态段,用来存放硬件上下文,还有一个特殊的寄存器TR(Task Register),指向当前进程的TSS。当TR更改,指向新进程的TSS时,将会触发硬件保存cpu所有寄存器的值到当前进程的TSS中,然后从新进程的TSS中读出所有寄存器值,加载到cpu对应的寄存器中。整个过程中cpu寄存器的保存、加载,无需软件参与。该方式由如下缺点:

    • 每个进程都需要一个TSS,全局段描述符表(GDT)支持的分段数量有限,从而限制了进程的数量;
    • 部分寄存器值并不会更改,更新全部寄存器效率低,而且全部更新无法校验装入寄存器的内容,有安全风险
    • 不能兼容其他CPU架构,代码可移植性差

         后面Linux改成用一组mov指令来逐一把寄存器的内容保存到进程描述中的theard字段中,即软件切换。因为x86架构下必须给TR提供一个TSS,Linux为每个CPU都创建了一个TSS,让TR永远指向该TSS,即对CPU而言,永远只有一个进程在运行,从而规避了硬件切换方式,TSS对应的描述符为tss_sruct。Linux只用到了TSS中的esp0和iomap字段,esp0是内核态栈指针,iomap是IO许可权位图,每次用户态进程访问I/O端口时会根据iomap检查进程是否有访问指定端口的权利。软件切换的大致流程如下:

        1、当A进程切换至B进程时,A进程从用户态进入内核态,内核从tss_sruct->x86_tss.sp0读取内核栈顶地址,把ESP寄存器的用户栈顶地址保存到内核栈,重置ESP寄存器为内核栈顶地址,接着利用汇编指令保存寄存器的内容至内核栈和thread字段中;

       2、A进程的硬件上下文保存完毕后,内核从B进程的thread.sp读取内核栈顶地址并重置ESP寄存器,重置TSS段中的tss_sruct->x86_tss.sp0字段,即内核栈顶地址,将内核栈和thread字段中的寄存器内容逐一恢复至对应的寄存器

      3、B进程的硬件上下文恢复后,执行必要的内核操作后,从内核态切换至用户态,内核弹出内核栈中的用户栈顶地址并重置ESP寄存器,即切换至用户栈,恢复用户态代码执行。注意此时内核栈中的内容都已弹出,所以内核栈是空的,所以从用户态切换到内核态时内核栈总是空的。

         进程切换的核心逻辑通过switch_to(prev, next, last)宏实现,注意这是一个宏,不是函数,它的参数prev, next, last不是值拷贝,而是它的调用者context_switch()的局部变量,当内核堆栈切换时取值会跟着改变。最后一个参数last是一个输出参数,指定将prev变量写入到next变量对应进程的内核栈的什么变量中,context_switch()调用时采用switch_to(prev, next, prev)的方式,以A切换至B为例说明,切换前prev和next都是A进程内核栈的内容,这两个变量是context_switch传递进来的,prev指当前进程描述符即A,next是切换至下一个的进程即B,将prev放到寄存器eax中;切换至B进程后,此时prev和next都是B进程的内核栈的变量,此时的取值是上一次调度完成后保留在内核栈的值,可能指向任何进程描述符,此时将eax寄存器中A进程描述符的地址写入到B进程内核栈的prev变量,保证prev变量准确指向从哪个进程切换过来的,后续操作会利用该变量。

         参考:TSS详解 ——《x86汇编语言:从实模式到保护模式》读书笔记33

                   【内核】进程切换 switch_to 与 __switch_to

                   linux进程切换(linux3.4.5,x86)

    三、进程创建与终止

          创建进程有三个函数,fork(),vfork()和clone(),fork创建的子进程地址空间与父进程独立,但是指向相同的物理页框,当父子进程任何一方想要修改其中的数据则将为子进程单独分配一个页框,并将对应的父进程的页复制到子进程新分配的页框中,即写时复制技术,并且内核确保子进程先于父进程被调度执行,从而避免父进程先执行修改数据造成不必要的页复制。vfork()创建的子进程共享父进程的地址空间,但是不共享打开文件表,信号处理程序表,根目录等其他进程资源,并且为了防止父进程重写子进程需要的数据,内核会阻塞父进程的执行,直到子进程执行完成。Linux中fork()和vfork()函数都是通过clone()函数实现的,区别在于传递的参数不同而已。Linux中的轻量级进程就是通常的线程,通过clone()函数创建,子进程与父进程共享一切进程资源。clone()函数通过do_fork()函数实现,do_fork()通过copy_process()函数完成进程描述符及其所需要的其他数据结构的创建,必要时从父进程拷贝对应数据结构的内容,并利用父进程的内核栈完成子进程内核栈的初始化。

        专门执行内核函数的进程称为内核线程,如kswapd进程执行内存回收,pdflush刷新缓冲区中的脏数据到磁盘中。有一个特殊的内核线程,进程0,又称idle进程,swapper进程,进程0是所有进程的祖先,是Linux内核初始化阶段创建的第一个进程。进程1时进程0创建的第一个普通进程,又称init进程,在系统关闭之前,该进程一直存活,用于创建和监控在操作系统外层执行的所有进程的活动。

        终止进程需要调用exit()函数,核心函数是do_exit(),该函数会回收目标进程的进程描述符,打开文件表等所有资源,并从内核数据结构中如进程链表删除对目标进程的引用。终止一个进程组调用exit_group(),核心函数是do_group_exit(),该函数向进程组的其他进程发送SIGKILL信号并调用do_exit() 杀死所有的线程。

        参考: 《深入理解Linux 内核》(第三版)

    四、用户线程,内核线程和轻量级进程

          用户线程指的是完全建立在用户空间的线程库,用户线程的建立,同步,销毁,调度完全在用户空间完成,不需要内核的帮助。内核线程就是直接由操作系统内核(Kernel)支持的线程,建立,同步,销毁,调度都在内核空间完成,内核通过操纵调度器(Scheduler)对线程进行调度,并负责将线程的任务映射到各个处理器上。每个内核线程可以视为内核的一个分身,这样操作系统就有能力同时处理多件事情,支持多线程的内核就叫做多线程内核(Multi-Threads Kernel),两者区别如下:

    1. 内核支持线程是OS内核可感知的,而用户级线程是OS内核不可感知的,OS内核看到的只有进程
    2. 用户级线程的创建、撤消和调度不需要OS内核的支持,是在语言(如Java)这一级由应用程序处理的;而内核支持线程的创建、撤消和调度都需OS内核提供支持,而且与进程的创建、撤消和调度大体是相同的。
    3. 用户级线程执行系统调用指令时将导致其所属进程被中断,因为该线程所属的进程内只有该线程被OS内核执行,而内核支持线程执行系统调用指令时,只导致该线程被中断,因为该线程所属的进程内可能多个线程同时被OS执行
    4. 在只有用户级线程的系统内,CPU调度还是以进程为单位,处于运行状态的进程中的多个线程,由用户程序控制线程的轮换运行;在有内核支持线程的系统内,CPU调度则以线程为单位,由OS的线程调度程序负责线程的调度。
    5. 用户级线程的程序实体是运行在用户态下的程序,而内核支持线程的程序实体则是可以运行在任何状态下的程序。

          轻量级进程,其本质仍然是进程,与普通进程相比,LWP与其父进程共享所有(或大部分)逻辑地址空间和系统资源,因为同父进程资源共享,创建TWP所需的执行上下文即资源更少,所以称为轻量级进程;一个进程可以创建多个LWP,每个LWP有独立的进程标识符,并和创建LWP的进程有着父子关系;LWP由内核管理并像普通进程一样被调度。Linux内核在 2.0.x版本就已经实现了轻量进程,应用程序可以通过一个统一的clone()系统调用接口,用不同的参数指定创建轻量进程还是普通进程,通过参数决定子进程和父进程共享的资源种类和数量,这样就有了轻重之分。在内核中, clone()调用经过参数传递和解释后会调用do_fork(),这个核内函数同时也是fork()、vfork()系统调用的最终实现。注意Linux系统没有线程的概念,只有轻量级进程,windows有线程概念。

     五、三种线程模型和Linux线程实现

         第一种多对一模型,进程内的多线程调度由应用程序负责,进程调度时只执行进程内的某一个线程,即同一进程内的多个线程对应一个与该进程绑定的内核线程,最大的问题是线程如果阻塞了则该线程所属的进程也会被阻塞。

        第二种一对一模型,与多对一模型相比,最大的区别是进程内的每个线程都对应一个内核线程,应用程序内的线程与内核中的线程生命周期一致,不同进程的多个不同线程调度等同于进程调度,最大的问题是内核线程频繁的创建销毁会占用大量的有限的内核资源。

        第三种是多对多模型,将上述两种混合起来,同一进程内的多个线程对应多个内核线程,线程销毁,与之对应的内核线程不会销毁而是为其他的线程继续提供服务。

       目前Linux是基于轻量级进程实现的一对一模型,即一个线程实体对应一个核心轻量级进程,而线程之间的管理在核外函数库中实现,最为理想的多对多模型因为实现复杂而被抛弃。

        对于Sun JDK来说,它的Windows版与Linux版都是使用一对一的线程模型实现的,一条Java线程就映射到一条轻量级进程之中,因为Windows和Linux系统提供的线程模型就是一对一的。而在Solari平台中,由于操作系统的线程特性可以同时支持一对一(通过Bound Threads或Alternate Libthread实现)及一对多(通过LWP/Thread Based Synchronization实现)的线程模型,因此在Solaris版的JDK中也对应提供了两个平台专有的虚拟机参数:-XX:+UseLWPSynchronization(默认值)和-XX:+UseBoundThreads来明确指定虚拟机使用哪种线程模型。

    详情参考: 线程的3种实现方式--内核级线程, 用户级线程和混合型线程

                       内核线程、轻量级进程、用户线程三种线程概念解惑(线程≠轻量级进程)

                       Linux 线程实现机制分析 Linux 线程模型的比较:LinuxThreads 和 NPTL

    六、进程与线程的区别

        进程是操作系统分配资源的最小单元,是程序执行的一个实例;线程是操作系统调度的最小单元,代表进程的一个执行流,Linux中线程就是轻量级进程,两者区别如下:

    1. 对Linux,进程采用fork创建,线程采用clone创建,clone是轻量级的fork,clone和fork都是基于父进程
    2. 进程fork创建的子进程的逻辑流位置在fork返回的位置,线程clone创建的KSE的逻辑流位置在clone调用传入的方法位置,比如Java的Thread的run方法位置
    3. 进程拥有独立的虚拟内存地址空间和内核数据结构(页表,打开文件表等),当子进程修改了虚拟页之后,会通过写时拷贝创建真正的物理页。线程共享进程的虚拟地址空间和内核数据结构,共享同样的物理页
    4. 多个进程通信只能采用进程间通信的方式,比如信号,管道,而不能直接采用简单的共享内存方式,原因是每个进程维护独立的虚拟内存空间,所以每个进程的变量采用的虚拟地址是不同的。多个线程通信就很简单,直接采用共享内存的方式,因为不同线程共享一个虚拟内存地址空间,变量寻址采用同一个虚拟内存
    5. 进程上下文切换需要切换页表等重量级资源,线程上下文切换只需要切换寄存器等轻量级数据,从进程演化出线程,最主要的目的就是更好的支持SMP(对称多处理器系统)以及减小(进程/线程)上下文切换开销
    6. 进程的用户栈独享栈空间,线程的用户栈共享虚拟内存中的栈空间,没有进程高效
    7. 一个应用程序可以有多个进程,执行多个程序代码,多个线程只能执行一个程序代码,共享进程的代码段
    8.  进程采用父子结构,线程采用对等结构

           参考: 计算机底层知识拾遗(二)深入理解进程和线程

    七、实时线程与实时操作系统

          实时操作系统(Real Time Operating System,简称RTOS)是指当外界事件或数据产生时,能够接受并以足够快的速度予以处理,其处理的结果又能在规定的时间之内来控制生产过程或对处理系统作出快速响应,并控制所有实时任务协调一致运行的操作系统。因而,提供及时响应和高可靠性是其主要特点。实时操作系统有硬实时和软实时之分,硬实时要求在规定的时间内必须完成操作,这是在操作系统设计时保证的,比如VxWorks ;软实时则只要按照任务的优先级,尽可能快地完成操作即可,比如Linux。

          分时操作系统(Time-sharing Operating System,简称TSOS)是指将系统CPU时间与内存空间按一定的时间分割(每个时间段称为时间片),轮流地切换给的程序使用的操作系统。由于时间间隔很短,每个用户的感觉就像他独占计算机一样。分时操作系统的特点是可有效增加资源的使用率。

         实时任务是指要求操作系统能够在规定的时间之内快速接受,处理并作出快速响应的任务,比如当车辆发生碰撞时要求安全气囊快速展开的任务,处理这类实时任务的线程(进程)就称为实时线程(进程)。与之相对的是分时任务,即对操作系统接收,处理任务并作出响应没有强制的时间要求,处理分时任务的线程(进程)就是分时线程(进程)。

         Linux同时支持实时进程和分时进程,默认参数下创建的都是分时进程,可以通过修改进程的调度策略等属性将其改成实时进程。Linux中实时进程和分时进程由不同的调度器调度,实时进程的调度器的优先级最高。Linux上JVM创建的线程默认是分时进程。

     详情参考: 什么是真正的实时操作系统

                        Linux操作系统实时性分析

    八、进程(线程)调度

          进程通常可以分为IO密集型和CPU密集型两种,前者频繁使用IO设备,花费很多时间等待IO操作完成,后者需要大量的CPU时间片完成计算。另一种分类法把进程分成三种:

    1、交互式进程,如命令行Shelll工具,文本编辑器等,这类进程经常与用户交互,花费很多时间等待键盘和鼠标操作。

    2、批处理进程,如数据库搜索引擎,通常的业务应用程序,这类进程不需要与用户交互,经常在后台运行。

    3、实时进程,如视频和音频应用程序,从物理传感器收集数据的程序,这类进程绝不会被优先级低的进程阻塞,要求在很短且比较稳定的时间范围内得到快速响应。

    Linux可以通过调度算法识别实时进程,无法准确识别交互式进程和批处理进程,只能通过基于进程过去行为的启发式算法做推测判断。

          进程调度整体上可以分为两种:

    1. 非抢占方式。采用这种调度方式,一旦把处理机分配给某进程后,便让该进程一直执行,直到该进程完成或发生某事件而被阻塞,才再把处理机分配给其他进程,决不允许某进程抢占已经分配出去的处理机。显然它难于满足紧急任务的要求,实时系统中不宜采用这种调度方式。

    2. 抢占方式。允许调度程序根据某种原则,去停止某个正在执行的进程,将已分配给该进程的处理机,重新分配给另一进程。抢占的原则有:

    - 时间片原则。各进程按时间片运行,当一个时间片用完后,便停止该进程的执行而重新进行调度,即CPU分时技术,依赖分时中断。时间片的长短对系统性能是很关键的,太短进程切换开销大,太长进程看起来不再是并发执行,降低系统的响应能力,Linux单凭经验选择尽可能长且响应时间良好的时间片

    - 优先权原则。当一个进程到来时,如果其优先级比正在执行的进程的优先级高,便停止正在执行的进程,将处理机分配给优先级高的进程,使之执行。Linux中进程的优先级是动态的,调度程序跟踪进程的运行,并周期调整他们的优先级,以避免进程饥饿现象,提升系统吞吐量。

         对抢占式调度,常见的调度策略有三种:

    - 优先级抢占式
        采用基于优先级的抢占式调度,系统中每个任务都有一个介于最高0到最低255之间的优先级。任一时刻,系统内核一旦发现一个优先级更高的任务转变为就绪态,内核就保存当前任务的上下文并把当前任务状态转换为阻塞态,同时切换到这个高优先级任务的上下文执行。
    - 轮转调度算法
        采用轮转调度算法,系统让处于就绪态的优先级相同的一组任务依次轮流执行预先确定长度的时间片。这是一种处理机平均分配的方法。如果不使用轮转调度算法,优先级相同的一组任务中第一个获得处理机的任务将不会被阻塞而独占处理机,如果没有阻塞或其他情况发生,它不会放弃处理机的使用权。
    - 抢占调度与轮转调度混合方式
        有时,基于优先级的抢占式调度可与轮转调度相结合。当优先级相同的一组任务依次轮流平均分配处理机时,若有高优先级的任务转变为就绪态则可抢占该组任务。直到再一次符合执行条件时,该组任务才可再次共享处理机。

         根据抢占式调度发生的位置可以分为两种:

      -用户抢占

          用户抢占是发生在用户空间的抢占现象,通常在从系统调用返回用户空间或者从中断(异常)处理程序返回用户空间时发生用户抢占,即上一个程序执行完成时执行用户抢占。

      -内核抢占

         内核抢占就是指一个在内核态运行的进程, 可能在执行内核函数期间,CPU被另一个进程抢占了。内核抢占主要是从实时系统中引入的, 在非实时系统中的确也能提高系统的响应速度,但是内核不能在任意点被中断,比如执行系统调度的时候就不能允许中断所以关闭了内核抢占,幸运的是, 大多数不能中断的点已经被底层硬件驱动实现标识出来了。linux内核抢占是在Linux2.5.4版本发布时加入的, 尽管使内核可抢占需要的改动特别少, 但是该机制不像抢占用户空间进程那样容易实现。

           linux内核目前实现了6中调度策略(即调度算法), 用于对不同类型的进程进行调度, 或者支持某些特殊的功能

    1. SCHED_NORMAL和SCHED_BATCH调度普通的非实时进程
    2. SCHED_FIFO和SCHED_RR和SCHED_DEADLINE则采用不同的调度策略调度实时进程
    3. SCHED_IDLE则在系统空闲时调用idle进程.

          而依据其调度策略的不同实现了5个调度器类, 一个调度器类可以用一种或者多种调度策略调度某一类进程, 也可以用于特殊情况或者调度特殊功能的进程.其所属进程的优先级顺序为:

         stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

         每个调度类都有自身的优先级,Linux调度管理基础代码会遍历在内核中注册了的调度类,选择高优先级的调度类,然后让此调度类按照自己的调度算法选择下一个执行的线程。内核中区分普通线程与实时线程是根据线程的优先级,实时线程拥有实时优先级(real-time priority),默认取值为0~99,数值越高优先级越高,而普通线程只具有nice值,nice值映射到用户层的取值范围为-20~+19,数值越高优先级越低,默认初始值为0 ,子线程会继承父线程的优先级。对于实时线程,Linux系统会尽量使其调度延时在一个时间期限内,但是不能保证总是如此,不过正常情况下已经可以满足比较严格的时间要求了。

         Linux上创建的java线程采用的是默认的SCHED_NORMAL策略。

    详情参考:Linux用户抢占和内核抢占详解(概念, 实现和触发时机)--Linux进程的管理与调度(二十)

                       Linux系统调度简介

                      linux内核调度详解

                      

          

         

     

     

     

     

         

    展开全文
  • 作业调度和进程调度的辨析

    万次阅读 多人点赞 2020-10-11 22:46:36
    但是在实际做题的时候,往往一不小心就把概念搞错,不容易区分“作业调度”和“进程调度”的区别。下面我主要针对这两个概念进行解析并给出经典习题解答。 PS:本博客并不详解每种调度算法的原理,因此有这方面需求...

    很多学习完《操作系统原理》这门课程的小伙伴都应该对“FCFS(先到先服务)”、“SJF(短作业优先)”等调度算法原理比较熟悉。但是在实际做题的时候,往往一不小心就把概念搞错,不容易区分“作业调度”和“进程调度”的区别。下面我主要针对这两个概念进行解析并给出经典习题解答。
    PS:本博客并不详解每种调度算法的原理,因此有这方面需求的小伙伴可以直接pass了。

    1、作业调度

    作业调度又称为高级调度,频度较低。其主要工作是将位于外存后备队列中的某个(或某几个)作业调入内存,排在就绪队列上。注意了,这个时候仅仅是将作业调入内存,并为作业创建进程、分配资源,此时进程处于就绪态,并没有执行


    2、进程调度

    进程调度又称为低级调度,是最基本的、频度最高的调度方式。其主要任务是从就绪队列中选取一个(或几个)进程,并分配处理机的过程,这时候才可以理解为“执行”。


    3、区别

    作业调度和进程调度最主要的区别在于,前者是为作业建立进程的过程,是将作业由外存调入内存的过程;而后者整个过程并没有跑出内存的范围,是将就绪态的进程变为运行态的过程。


    下面,我们就某个实例题目,给大家做进一步的辨析。
    ———————————————————————————
    题目:
    有一个两道批处理系统,它只有一个CPU(一次只能处理一个进程),在作业调度算法采用短作业优先调度、进程调度算法采用抢占式优先级调度。假设有四个作业J1、J2、J3、J4,其运行情况如下表所示,采用“优先数越小、优先级越高”的原则,计算平均周转时间。
    在这里插入图片描述

    解析:
    在做这种题的时候最好画一个就绪队列,或者脑海中想象一个就绪队列,以免思维混乱,初始情况下就绪队列为空:
    在这里插入图片描述

    还要注意一点的是,“单CPU两道批处理系统”的意思是,一次最多允许两道作业存在,并且一次只能处理一道作业。

    ① 首先8:00的时候作业J1到达(注意这里的“到达”不是指到达就绪队列,而是表明“J1这个任务来了,我们即将处理它”,很浅层的意思,不要多想),这个时候只有J1,那么毫无疑问直接调入内存,由于是两道批处理,我们假设这里的内存叫内存1,进入就绪队列,然后开始执行,也就是分配CPU
    此时的就绪队列如下(空),因为J1刚进入就绪队列就被分配了CPU,转为运行态:
    在这里插入图片描述


    ② 8:20的时候,J2到达,此时内存还有个位置空闲,显然将J2调入内存,我们叫内存2,进入就绪队列,那调入内存后要不要分配CPU呢?这就得看我们的进程调度算法了,使用抢占式优先级调度,J2的优先数要小于J1,因此优先级大,此时J1被迫暂停执行,重新回归就绪队列,而J2从就绪队列出去,分配CPU,进入运行态,而此时J1还剩下20min时间;
    此时的就绪队列如下:
    在这里插入图片描述


    ③ 8:30的时候,J3到达,但是内存此时已经没有位置了,即一道给了J1,另一道给了J2,因此J3只能在外存的后备队列里等着,进不了就绪队列;
    此时的就绪队列没变:
    在这里插入图片描述


    ④ 8:50,J2执行完毕,这样“内存2”就空出来了,此时J4正好也到达了,那到底是将J3还是J4调入内存就绪队列中呢?看我们的作业调度算法,短作业优先,J4需要的的时间要比J3短,因此J4先调入内存2;
    此时的就绪队列如下:
    在这里插入图片描述


    ⑤ 现在就绪队列里有J1、J4,谁先执行呢?比较优先级的大小!J1的优先级大,因此J1先执行。注意:此时两道内存仍然还有作业,因此J3还是要在外存中等着;
    此时的就绪队列如下:
    在这里插入图片描述


    ⑥ 9:10的时候,J1执行完毕了,内存1就空出来了,这个时候J3就可以调入内存1了,即进入就绪队列;
    此时的就绪队列如下:
    在这里插入图片描述


    ⑦ 同理,J3优先级高,先占用CPU开始执行,到10:00执行完毕,此时J4分配CPU开始执行20min,到10:20执行完毕。至此,全部作业都完成了。
    此时的就绪队列自然也清空了:
    在这里插入图片描述


    好了,以上就是整个过程的全部详解,只看文字略显枯燥,我们附上整个过程的Gantt图:
    在这里插入图片描述

    答案:
    J1的周转时间 = J1的等待时间 + J1的运行时间 = 30 + 40 = 70min;
    J2的周转时间 = 0 + 30 = 30min;
    J3的周转时间 = 40 + 50 = 90min;
    J4的周转时间 = 70 + 20 = 90min.

    最终的平均周转时间 = (70 + 30 + 90 + 90) / 4 = 70min.

    展开全文
  • 编写程序完成单处理器系统中的进程调度, 要求实现时间片轮转、 优先数、 最短进程优 先和最短剩余时间优先四种调度算法。 实验具体包括: 首先确定进程控制块的内容, 进程控 制块的组成方式; 然后完成进程创建...
  • 进程调度算法设计

    千次阅读 2019-08-06 19:10:29
    进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时...
  • 进程和线程调度算法

    千次阅读 2019-07-29 13:12:54
    调度算法是指:根据系统的资源分配策略所规定的资源分配算法,如任务A在执行完后,选择哪个任务来执行,使得某个因素(如进程总执行时间,或者磁盘寻道时间等)最小。对于不同的系统目标...
  • 操作系统进程、线程、调度

    千次阅读 2019-05-13 16:17:49
    文章目录进程进程进程实体*进程的组织方式和特征进程状态*线程线程通信和进程通信 进程 程序就是一个指令序列,在早起的计算机只支持单道程序,还没有进程的概念...所谓的创建和撤销进程都是指对PCB的操作。 程序...
  • 什么是进程调度 我们的计算机内有很多很多个进程,但是处理机数量又是很少的,这就导致这些进程之间会争夺处理机资源。这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之...
  • 进程调度的设计与实现 二、实验目的及要求 1综合应用下列知识点设计并实现操作系统的进程调度:邻接表,布尔数 组,非阻塞输入,图形用户界面GUI,进程控制块,进程状态转换,多级反馈队列进程调度算法。 2加深理解...
  • 操作系统3——处理机调度(作业调度+进程调度) 目录 操作系统3——处理机调度(作业调度+进程调度) 1、处理机的调度层次和目标 2、作业调度——先来先服务调度算法(FCFS) 3、作业调度——短作业优先调度...
  • Linux如何实现进程调度

    千次阅读 2021-12-13 19:43:39
    文章目录Linux如何实现进程的调度Linux进程的数据结构创建 task_struct 结构Linux 进程地址空间Linux 进程文件表Linux 进程调度进程调度实体进程运行队列调度实体和运行队列的关系调度器类Linux 的 CFS 调度器普通...
  • 【操作系统】进程和线程调度

    千次阅读 2020-03-20 13:38:38
    进程调度 进程调度的对象是进程或内核级线程,是最基本的一种调度。用于决定就绪队列中的哪个进程(或内核级线程,为叙述方便,以后只写进程)应获得处理机,然后再分派程序执行把处理机分配给该进程的具体操作。 ...
  • 进程调度详解算法

    千次阅读 多人点赞 2020-04-08 09:40:26
    进程调度详解算法及C语言实现引言原因进程调度的指标进程调度的时机进程调度的方式进程调度的策略/...需要进程调度的理由很简单,即充分利用计算机系统中的CPU资源,让计算机系统能够多快好省地完成我们让它做的各...
  • 进程调度介绍

    千次阅读 2018-04-17 19:00:43
    许多进程调度的处理方式对进程和线程都适用。这里首先讨论进程调度问题。 我们可以把调度算法分为两类:非抢占式调度以及抢占式调度。 非抢占式调度算法 这种算法挑选一个进程运行,并一直运行到阻塞(...
  • 操作系统 进程调度实验报告

    千次阅读 2020-06-19 09:25:07
    本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。 二、 实验内容 1. 优先权法、轮转法 简化假设 1) 进程为计算型的(无I/O) 2) 进程状态:ready、running、finish 3) 进程需要的CPU时间以...
  • 进程调度设计与实现

    2011-10-21 21:25:25
    1、 综合应用下列知识点设计并实现操作系统的进程调度:邻接表,布尔数组,非阻塞输入,图形用户界面GUI,进程控制块,进程状态转换,多级反馈队列进程调度算法。 2、 加深理解操作系统进程调度的过程。 3、 加深...
  • 进程调度实验,python实现

    千次阅读 2019-11-14 22:02:31
    一、 设计一个有N个进程其行的进程调度算法。 进程调度算法:采用最高优先数的调度算法(即把处理机分配给优先数最高的进程)。 每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数...
  • 进程调度算法(全网最细)

    千次阅读 多人点赞 2020-05-11 20:44:59
    所谓进程调度方式,是指当某个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有以下两种进程调度方式: 非剥夺调度方式,又称非...
  • 进程与线程及调度

    千次阅读 2018-12-28 19:11:14
    进程调度类似,CPU在线程之间快速切换,制造了线程并行运行的假象。 不同的进程之间有独立的地址空间,而线程之间有完全一样的地址空间 ,这意味着它们共享同样的全局变量。 由于各个线程都可以访问进程地址...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 190,367
精华内容 76,146
关键字:

创建进程是由什么调度完成