精华内容
下载资源
问答
  • (1)理解磁盘调度相关理论 (2)加深对操作系统进程管理功能的理解 (3)培养编写复杂程序的能力
  • 利用c++模拟进程调度。模拟操作系统内核对进程的控制和管理:包括进程创建和撤销、进程状态的切换和简单的内存空间管理。  能够模拟进程创建与撤销过程;(4 分)  对进程的状态进行全面的控制;(4 分) ...
  • C语言,运行成功,比较基础,c语言模拟设计一个有N个进程运行的进程调度程序,用最高优先数优先法:在创建进程时,给定一个进程优先数,并按一定规则减少优先数,直至所有进程运行完成(例如进程每获得一次cpu进程数...
  • 编写程序完成单处理器系统中的进程调度, 要求实现时间片轮转、 优先数、 最短进程优 先和最短剩余时间优先四种调度算法。 实验具体包括: 首先确定进程控制块的内容, 进程控 制块的组成方式; 然后完成进程创建...
  • 编写程序完成单处理机系统中的进程调度,要求采用时间片轮转调度算法。实验具体包括:首先确定进程控制块的内容,进程控制块的组成方式;然后完成进程创建原语和进程调度原语;最后编写主函数对所作工作进程测试。 ...
  • 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内核调度详解

                      

          

         

     

     

     

     

         

    展开全文
  • 进程调度算法设计

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

    【实验目的】

            进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不同调度算法的优缺点。

    【实验内容】

            选择两个调度算法作为两个实验题目,实现处理器调度。

    【实验原理】

    (1)进程控制块

           为了管理和控制进程,系统在创建每一个进程时,都为其开辟一个专用的存储区,用以随时记录它在系统中的动态特性。而当一个进程被撤消时,系统就收回分配给它的存储区。通常,把这一存储区称为该进程的“进程控制块”(Process Control Block)。

            由于PCB是随着进程的创建而建立,随着进程的撤消而取消的,因此系统是通过PCB来“感知”一个个进程的,PCB是进程存在的唯一标志。

    (2)进程控制块队列

            在多道程序设计环境里,同时会创建多个进程。当计算机系统只有一个CPU时,每次只能让一个进程运行,其他的进程或处于就绪状态,或处于阻塞状态。为了对这些进程进行管理,操作系统要做三件事。

    ①把处于相同状态的进程的PCB,通过各自的队列指针链接在一起,形成一个个队列。通常有运行队列、就绪队列、阻塞队列。

    ②为每一个队列设立一个队列头指针,它总是指向排在队列之首的进程的PCB。

    ③排在队尾的进程的PCB,它的“队列指针”项内容应该为“NULL”,或一个特殊的符号,以表示这是该队的队尾PCB。

           在单CPU系统中,任何时刻都只有一个进程处于运行状态,因此运行队列中只能有一个PCB;系统中所有处于就绪状态的进程的PCB排成一队,称其为“就绪队列”。一般地,就绪队列中会有多个进程的PCB排在里面,它们形成处理机分配的候选对象。如果就绪队列里没有PCB存在,则称该队列为空;所有处于阻塞状态进程的PCB,应该根据阻塞的原因进行排队,每一个都称为一个“阻塞队列”。比如等待磁盘输入/输出进程的PCB排成一个队列,等待打印机输出进程的PCB排成一个队列等。所以,系统中可以有多个阻塞队列,每个阻塞队列中可以有多个进程的PCB,也可以为空。

    (3)进程调度算法

           进程调度算法用于确定就绪队列中的哪一个进程即将获得CPU。常用的进程调度算法有先来先服务法、时间片轮转法、优先数法等。

    ①先来先服务调度算法

    先来先服务调度算法的基本思想是:以到达就绪队列的先后次序为标准来选择占用处理机的进程。一个进程一旦占有处理机,就一直使用下去,直至正常结束或因等待某事件的发生而让出处理机。采用这种算法时,应该这样来管理就绪队列:到达的进程的PCB总是排在就绪队列末尾;调度程序总是把CPU分配给就绪队列中的第一个进程使用。

    ②时间片轮转法

           时间片轮转调度算法的基本思想是:为就绪队列中的每一个进程分配一个称为“时间片”的时间段,它是允许该进程运行的时间长度。在使用完一个时间片后,即使进程还没有运行完毕,也要强迫其释放处理机,让给另一个进程使用。它自己则返回到就绪队列末尾,排队等待下一次调度的到来。采用这种调度算法时,对就绪队列的管理与先来先服务完全相同。主要区别是进程每次占用处理机的时间由时间片决定,而不是只要占用处理机就一直运行下去,直到运行完毕或为等待某一事件的发生而自动放弃。

    ③优先数调度算法

           优先数调度算法的基本思想是:为每一个进程确定一个优先数,进程就绪队列按照优先数排序。

           如何确定进程的优先数(也就是进程的优先级)?可以从如下几个方面考虑。

    ⅰ)根据进程的类型。系统中既有系统进程,又有用户进程。系统进程完成的任务是提供系统服务,分配系统资源,因此,给予系统进程较高的优先数能够提高系统的工作效率。

    ⅱ)根据进程执行任务的重要性。重要性和紧迫性高的进程应当被赋予较高的优先级。

    ⅲ)根据进程程序的性质。一个CPU繁忙的进程,由于需要占用较长的运行时间,影响系统整体效率的发挥,因此只能给予较低的优先数。一个I/O繁忙的进程,给予它较高的优先数后,就能充分发挥CPU和外部设备之间的并行工作能力。

    ⅳ)根据对资源的要求。系统资源有处理机、内存储器和外部设备等。可以按照一个进程所需资源的类型和数量,确定它的优先数。比如给予占用CPU时间短或内存容量少的进程以较高的优先数,这样可以提高系统的吞吐量。

    ⅴ)根据用户的请求。系统可以根据用户的请求,给予它的进程很高的优先数,作“加急”处理。

    ④多级队列调度算法

           多级队列调度算法也称多级反馈队列调度算法,它是时间片调度算法与优先数调度算法的结合。实行这种调度算法时,系统中将维持多个就绪队列,每个就绪队列具有不同的调度级别,可以获得不同长度的时间片。例如,系统维持N个就绪队列,第1级就绪队列中进程的调度级别最高,可获得的时间片最短,第N级就绪队列中进程的调度级别最低,可获得的时间片最长。

            具体的调度方法是:创建一个新进程时,它的PCB将进入第1级就绪队列的末尾。对于在第1级到第N-1级队列中的进程,如果在分配给它的时间片内完成了全部工作,那么就撤离系统;如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生,那么就进入相应的阻塞队列里等待。在所等待的事件出现时,仍回到原队列末尾,参与下一轮调度(也就是每个队列实行先来先服务调度算法);如果用完了时间片还没有完成自己的工作,那么只能放弃对CPU的使用,降到低一级队列的末尾,参与那个队列的调度。对位于最后一个队列里的进程,实行时间片轮转调度算法。

            整个系统最先调度1级就绪队列;只有在上一级就绪队列为空时,才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程(可以肯定,在此之前比运行进程级别高的所有队列全为空)时,系统将立即停止当前运行进程的运行,让它回到自己队列的末尾,转去运行级别高的那个进程。

            可以看出,多级队列调度算法优先照顾I/O繁忙的进程。I/O繁忙的进程在获得一点CPU时间后就会提出输入/输出请求,因此它们总是被保持在1、2级等较前面的队列中,总能获得较多的调度机会。对于CPU繁忙的进程,它们需要较长的CPU时间,因此会逐渐地由级别高的队列往下降,以获得更多的CPU时间,它们“沉”得越深,被调度到的机会就越少。但是,一旦被调度到,就会获得更多的CPU时间。

    【程序代码】

    数据项

    作用

    next

    前向指针,指向下一个进程控制块,用来构成进程队列

    process_name

    进程名称

    process_number

    进程号,当进程有相同名称时,用来区分进程

    process_start_moment

    进程启动时刻

    process_need_time

    进程要求运行时间

    process_time_slice

    时间片

    process_priority

    优先数

                                       图1     进程控制块的数据结构

     

    进程调度算法

    ①编译命令

    gcc process_schedule.cpp –o process_schedule.o –lcurses

    ②程序清单

    头文件process_schedule.h

    #include <curses.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <string.h>
    
    #define MAX_PROCESS 10
    int process_number=0;
    typedef struct pcb{
    	struct pcb *next;
    	char process_name[20];
    	int process_number;
    	int process_start_moment;
    	int process_need_time;
    	int process_time_slice;
    	int process_priority;
    }PCB;
    
    PCB pcb_table[MAX_PROCESS];
    
    PCB *pcb_run=NULL;
    PCB *pcb_free=NULL;
    PCB *pcb_ready=NULL;
    PCB *pcb_ready_rear=NULL;
    PCB *pcb_blocked=NULL;
    PCB *pcb_blocked_rear=NULL;
    
    void init_pcb_table();
    void display_process_queue(PCB *queue);
    PCB *create_process();
    void block_process_by_name();
    void wakeup_process();
    
    void FCFS();
    void RR();
    void HPF();
    void MFBQ();

    源文件process_schedule.cpp

    #include "process_schedule.h"
    int main(int argc,char *argv[]){
    	char select;
            initscr();
    	init_pcb_table();
    	bool end=false;
    	
    	while(!end){
    		clear();
    		refresh();
    		printw("|----------MAIN    MENU-------------|\n");
    		printw("|  1:first come first served        |\n");
    		printw("|  2:round robin                    |\n");
    		printw("|  3:highest priority first         |\n");
    		printw("|  4:multi_level feedback queue     |\n");
    		printw("|  5:display ready process queue    |\n");
    		printw("|  6:display blocked process queue  |\n");
    		printw("|  7:display running queue          |\n");
    		printw("|  a:create a process               |\n");
    		printw("|  b:delete a process               |\n");
    		printw("|  c:block  a process               |\n");
    		printw("|  d:wakeup  a process              |\n");
    		printw("|  8:exit                           |\n");
    		printw("|-----------------------------------|\n");
    		printw("select a function(1~8,a~d):");
                    refresh();
    		do{
    			select=(char)getch();
                            refresh();
    		}while(!((49<=select&&select<=56)||(97<=select&&select<=100)));
    		clear();
            refresh();
    		switch(select){
    		case '1':
    			FCFS();
    			break;
    		case '2':
    			RR();
    			break;
    		case '3':
    			HPF();
    			break;
    		case '4':
    			MFBQ();
    			break;
    		case '5':
    			printw("              ready  queue\n");
    			display_process_queue(pcb_ready);
    			break;
    		case '6':
    			printw("              blocked  queue\n");
                            display_process_queue(pcb_blocked);
    			break;
    		case '7':
    			printw("              running  queue\n");
                            display_process_queue(pcb_run);
    			break;
    		case 'a':
    			create_process();
    			break;
    		case 'b':
    			break;
    		case 'c':
    			block_process_by_name();
    			break;
    		case 'd':
    			wakeup_process();
    			break;
    		case '8':
    			printw("\n");
    		        end=true;
    		}
    		printw("press any key to continue.\n");
    		getch();
    		refresh();
    	}
    	endwin();
    	return 0;
    }
    
    void init_pcb_table()
    {
    	int i=0;
    	pcb_free=&pcb_table[0];
    	pcb_table[MAX_PROCESS-1].next=NULL;
    	pcb_table[MAX_PROCESS-1].process_number=0;
    	pcb_table[MAX_PROCESS-1].process_start_moment=0;
        pcb_table[MAX_PROCESS-1].process_need_time=0;
    	pcb_table[MAX_PROCESS-1].process_time_slice=0;
    	pcb_table[MAX_PROCESS-1].process_priority=0;
    	strcpy(pcb_table[MAX_PROCESS-1].process_name,"");
    	for(i=0;i<MAX_PROCESS-1;i++){
    		pcb_table[i].next=&pcb_table[i+1];
    		pcb_table[i].process_number=0;
    		pcb_table[i].process_start_moment=0;
            pcb_table[i].process_need_time=0;
    	    pcb_table[i].process_time_slice=0;
    	    pcb_table[i].process_priority=0;
    		strcpy(pcb_table[i].process_name,"");
    	}
    }
    
    void display_process_queue(PCB *queue)
    {
    	PCB *p=queue;
    	int i=4;
        move(1,1);
    	printw("|----------|----------|----------|----------|----------|----------|\n");
    	move(2,1);
    	printw("| name     | number   | start    | need     | slice    | priority |\n");
    	move(3,1);
    	printw("|----------|----------|----------|----------|----------|----------|\n");
    	while(p!=NULL){
    		move(i,1);
    		printw("| ");
    		printw("%s",p->process_name);
    		move(i,12);
    		printw("| ");
    		printw("%d",p->process_number);
    		move(i,23);
    		printw("| ");
    		printw("%d",p->process_start_moment);
    		move(i,34);
    		printw("| ");
    		printw("%d",p->process_need_time);
    		move(i,45);
    		printw("| ");
    		printw("%d",p->process_time_slice);
    		move(i,56);
    		printw("| ");
    		printw("%d",p->process_priority);
    		move(i,67);
    		printw("|");
    		p=p->next;
    		i++;
    	}
    	move(i,1);
    	printw("|----------|----------|----------|----------|----------|----------|\n");
    	refresh();
    }
    
    void FCFS()
    {
    	if(pcb_ready==NULL)
    	{
    		printw("ready queue is empty,no process to run.\n");
    	}
    	else
    	{
    		pcb_run=pcb_ready;
    		if(pcb_ready==pcb_ready_rear)
    		{
    			pcb_ready=pcb_ready_rear=NULL;
    		}
    		else
    		{
    			pcb_ready=pcb_ready->next;
    		}
    		pcb_run->next=NULL;
    	}
    }
    			
    void RR()
    {
    }
    		
    void HPF()
    {
    }
    		
    void MFBQ()
    {
    }
    
    PCB *create_process()
    {
    	PCB *p=pcb_free;
    	if(p==NULL)
    		return NULL;
    	else
    	{
    		pcb_free=pcb_free->next;
    		clear();
    		refresh();
    		printw("please enter the following fields:\n");
    		printw("| name | start_moment | need_time | time_slice | priority |\n");
    		scanw("%s%d%d%d%d",
    p->process_name,
    &(p->process_start_moment),
    &(p->process_need_time),
    &(p->process_time_slice),
    &(p->process_priority));
    		p->process_number=(process_number+1)%100;
    		process_number++;
    		p->next=NULL;
    		if(pcb_ready==NULL)
    			pcb_ready=pcb_ready_rear=p;
    		else
    		{
    		    pcb_ready_rear->next=p;
    		    pcb_ready_rear=p;
    		}
    		return p;
    	}
    }
    
    
    void block_process_by_name()
    {
    	char process_name[20];
    	PCB *p=pcb_ready;
    	PCB *previous_p=pcb_ready;
    	if(p==NULL)
    	{
    		printw("ready queue is empty,no process can be blocked!\n");
    		return;
    	}
    	display_process_queue(pcb_ready);
    	printw("enter the process name you want to block:\n");
    	scanw("%s",process_name);
    	while(p!=NULL){
    		if(!strcmp(p->process_name,process_name))
    			break;
    		previous_p=p;
    		p=p->next;
    	}
    	if(p==NULL)
    	{
    		printw("no such a process in ready queue:%s\nyou typed the wrong name\n",
    process_name);
    		return;
    	}
    	else
    	{
    		if(p==pcb_ready_rear)
    		{
    			pcb_ready_rear=previous_p;
    		}
             previous_p->next=p->next;
    		 if(pcb_blocked==NULL)
    		 {
    			 pcb_blocked=pcb_blocked_rear=p;
    			 p->next=NULL;
    		 }
    		 else
    		 {
    			 pcb_blocked_rear->next=p;
                 pcb_blocked_rear=pcb_blocked_rear->next;
    			 p->next=NULL;
    		 }
    	}
    
    }
    
    void wakeup_process()
    {
    	PCB *p=pcb_blocked;
    	if(pcb_blocked==NULL)
    	{
    		printw("blocked queue is empty,no process needs to be wakeuped.\n");
    	}
        else{
    	
    	      if(pcb_blocked==pcb_blocked_rear)
    	            	pcb_blocked=pcb_blocked_rear=NULL;
    	      else
    		            pcb_blocked=pcb_blocked->next;
    	
              if(pcb_ready==NULL)
    		 {
    		    pcb_ready=pcb_ready_rear=p;
    		    p->next=NULL;
    		 }
          	else
    		{
    		   pcb_ready_rear->next=p;
    		   pcb_ready_rear=pcb_ready_rear->next;
    		   p->next=NULL;
    		}
    	}
    }//wakeup

    【实验结果】

    【实验心得】

           通过这次实验课,我了解了处理机四种调度算法先来先服务调度算法(FCFS)、优先数调度算法、基于时间片的轮转调度法和多级反馈队列调度算法。我所编写的是先来先服务和优先数调度算法。作业调度的主要任务就是根据JCB中的信息,检查系统中的资源能否满足作业队资源的要求,以及按照一定的调度算法,从外存的后备对列选取某些作业调入内存。在每次执行作业调度时,都需要做出以下两个决定:

    a. 接纳多少个作业:接纳多少作业取决于多道程序度。而多道程序度取决于:计算机系统规模,运行速度,作业大小,以及能否获得较好的系统性能。

    b. 接纳哪些作业: 选择哪些作业取决于,作业调度采用哪种算法。

     

     

     

     

     

     

    展开全文
  • 操作系统进程、线程、调度

    千次阅读 2019-05-13 16:17:49
    文章目录进程进程进程实体*进程的组织方式和特征进程状态*线程线程通信和进程通信 进程 程序就是一个指令序列,在早起的计算机只支持单道程序,还没有进程的概念...所谓的创建和撤销进程都是指对PCB的操作。 程序...

    注:标题带 * 的是重点


    进程

    程序就是一个指令序列,在早起的计算机只支持单道程序,还没有进程的概念;而引入多道程序技术后,为了程序的并发执行,从而引入了进程、进程实体的概念。


    进程与进程实体*

    进程实体的在组成:

    • PCB:进程控制块,描述了进程的基本信息和运行状态,是进程存在的唯一标志;所谓的创建和撤销进程都是指对PCB的操作。
    • 程序段:程序的代码。
    • 数据段:程序运行时产生的运算数据,包括全局变量、局部变量等。

    PCB包含:进程标识符(PID)、处理机状态、进程调度信息、进程控制信息。
    1

    进程和进程实体
    进程是进程实体的运行过程,是系统进行资源分配的基本单位。
    进程实体是静态的,进程是动态的。


    进程的组织方式和特征

    组织方式
    进程的组织,即对多个 PCB 的组织,分为两种方式:

    • 链接方式:按照进程状态将 PCB 分为多个队列(就绪队列、阻塞队列…),操作系统对每个队列进行操作。
    • 索引方式:根据进程状态的不同,建立多张索引表,操作系统对每张索引表进行操作。

    特征

    • 动态性:进程是程序的一次执行过程
    • 并发性:内存中有多个进程实体,个进程并发执行
    • 独立性:进程是能够独立运行,独立获得资源的基本单位
    • 异步性:在没有同步机制的情况下,各进程独立的以不可知的速度向前推进
    • 结构性:即进程的组成结构

    进程状态*

    进程的状态/生命周期
    进程有五个状态(不包含挂起),前三个为基本状态:

    • 运行态: 占有 CPU,并正在执行
    • 就绪态: 已经具备执行条件,等待被 CPU 调度
    • 阻塞态: 因某一事件(系统调用)而等待不能执行,等待资源
    • 创建态:进程正在被创建,分配空间初始化 PCB
    • 终止态:进程正从系统中撤销,系统回收进程拥有的资源
      2

    进程控制
    进程控制就是要实现进程的状态转换。
    进程控制通过原语实现。

    原语:内核态下具有特定功能的指令序列,具有原子性

    相关的原语:进程的创建、进程的终止、进程的阻塞、进程的唤醒、进程的切换。

    fork() 、vfork()
    fork 和 vfork 是 linux下的系统调用指令,是用来操作进程的指令。

    • fork()
      创建一个进程(调用fork的进程就是父进程,生成的是子进程)。
      注:linux初始有两个进程,进程0(交换进程) ,进程1(进程0的子线程,是我们创建的其他所有进程的祖先)
    • vfork()
      fork创建的子进程的地址空间和父进程是分开的(除了共享代码段,其他都数据段复制),父子进程是两个独立的进程,拥有的优先级相同。
      而 vfork 创建的子进程与父进程共用相同的地址空间,子进程对这些共享资源所做的修改,可以影响到父进程。

    线程

    线程概念
    线程是独立调度的基本单位。
    注:传统进程机制 CPU 调度的是进程,而引入线程后,进程就只作为资源分配的基本单位了。

    一个进程中可以有多个线程,它们共享进程资源。

    QQ 和浏览器是两个进程,浏览器进程里面有很多线程,例如 HTTP 请求线程、事件响应线程、渲染线程等等,线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时,浏览器还可以响应用户的其它事件。

    与进程的区别/带来的变换:

    • 拥有资源
      线程不拥有资源,但可以访问隶属进程的资源。
    • 并发性
      原本只能进程间并发,引入线程后,各线程间也能并发,提高了并发度。
    • 系统开销
      线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换。

    用户级线程和内核级线程
    线程的实现可以分为两类:用户级线程和内核线线程。在多线程操作系统中,各个系统的实现方式并不相同,在有的系统中实现了用户级线程,有的系统中实现了内核级线程。它们的特点和区别:

    • 内核级线程是依赖于内核的,它存在于用户进程和系统进程中,它们的创建,撤消和切换都由内核实现;
    • 用户级线程仅存在于用户级中,它们的创建,撤消和切换不利用系统调用来实现,因而与内核无关,内核并不知道用户级线程的存在
    • 有了内核线程,每个用户线程被映射或绑定到一个内核线程(一对一、一对多、多对多)
    • 在只有用户级线程的系统内,CPU调度还是以进程为单位,由用户程序控制线程的轮换运行;在有内核支持线程的系统内,CPU调度则以线程为单位,由OS的线程调度程序负责线程的调度。
      3图片来自网络

    线程通信和进程通信*

    线程通信: 地址

    进程通信

    • 消息传递: 直接通信、间接通信。
      原语:Send/Rececive
      直接通信:消息直接挂到接受进程的消息缓冲队列上。
      间接通信:消息要先发送到中间实体。
    • 管道: 就是在内存中开辟一个用于读写的固定大小的缓冲区。
      特点:半双工(某时段单向)、只能用于父子进程。
    • 命名管道: 是一个用于读写的文件,去除了管道只能在父子进程中使用的限制。
    • 消息队列: 提供一个独立于进程 的队列。
      相比 FIFO 的优点:
      1.避免了 FIFO 的同步阻塞,进程不需要提供同步方法。
      2.进程可以有选择的接受消息,而不像 FIFO 默认接受。
    • 信号量: 一个计数器,用于为多个进程提供对共享数据对象的访问(同步)。
    • 共享内存: 允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制,所以这是最快的一种 IPC。需要使用信号量。
    • 套接字: 用于不同机器间的进程通信。

    处理机调度

    处理机调度:从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行。

    调度级别

    首先介绍下进程的挂起状态
    引入虚拟存储技术后,系统会将暂时不能运行的进程调到外存等待,在外存等待的进程状态被称为挂起状态(PCB依然在内存)。

    三个调度级别:

    • 高级调度: 即作业调度,是外存和内存之间 的调度;按一定的原则从外存上处于后备队列的作业中挑选若干个作业,为它们分配资源建立 PCB。
    • 中级调度 即内存调度,选择一个处于挂起状态的进程重新调入内存。
    • 低级调度 即进程调度,从就绪队列中选取一个进程,将处理机分配给它。
      进程调度是操作系统中最基本的一种调度。

    两种进程调度的方式:

    • 抢占式: 如果有一个更紧急的进程需要使用处理机,系统则会立即暂停正在执行的进程,将处理机分配给更紧急的进程。
    • 非抢占式: 只允许进程主动放弃处理机,处理机才会被分配给其他进程。

    调度算法*

    不同阶段的系统采用的调度算法是不同的。

    1. 批处理系统

    先来先服务: FCFS,非抢占式
    按照到达的先后顺序调度,也就是等待时间越久的越优先得到服务。

    优缺点:

    • 公平、算法实现简单,不会产生饥饿(某进程长期得不到服务)
    • 对长作业有利、对短作业不利

    短作业优先: SJF,非抢占式
    每次调度时选择当前已到达且运行时间最短的进程。

    优缺点:

    • 相比先来先服务算法平均等待时间更短
    • 对短作业有利,对长作业不利,不公平会产生饥饿

    最短剩余时间优先: SRTN,抢占式
    短作业的一种,按照剩余时间最短的顺序进行调度。优缺点同短作业优先算法。

    高响应比优先: HRRN,非抢占式
    调度时计算所有在就绪队列中进程的响应比((等待时间+服务时间)/服务时间),选择响应比最高的进程分配处理机。

    优缺点:结合先来先服务和短作业的优缺点的一种折中算法。

    2. 交互式系统
    时间片轮转
    轮流让就绪队列中的队头的进程依次执行一个时间片,之后两种情况:

    • 时间片没完而进程执行完毕,则会主动放弃处理机
    • 时间片用完而进程未执行完毕,则会停止执行并将该线程送完就绪队列的队尾

    时间片轮转算法的效率和时间片的大小有很大关系:

    • 如果时间片太大,使得每个进程都可以在一个时间片内完成,则会退化成先来先服务算法
    • 如果时间片太小,那么进程切换就会很频繁,系统会花大量时间来处理进程切换。

    优先级调度
    优先处理优先级最高的进程,分两种:

    • 非抢占式:选择当前已到达且优先级最高的进程
    • 抢占式:会检查就绪队列中有没有优先级最高的进程(包括执行中的)

    为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级(动态优先级)。

    多级反馈队列
    是时间片轮转算法和优先级算法的结合。
    结构:
    设置多级就绪队列,各级队列优先级从高到底,时间片从小到大
    4
    流程:

    • 新进程到达时先进入第1级队列,FCFC排队并分配时间片
    • 若用完时间片进程未执行接受,则进入下一级队列队尾
    • 若处于最下级的队列则会重新放回该队列队尾
    • 只有前一级的队列为空时,才会为当前队列队头的进程分配时间片
    展开全文
  • PCB进程调度模拟

    2014-10-28 15:45:03
    操作系统实验,模拟操作系统的PCB进程调度模拟算法(PCB进程模拟 调度算法 抢占式静态优先级调度 动态优先级调度 时间片轮转调度 多级反馈调度),给出调度过程中各个进程的状态信息,调度完成后显示带权周转率~
  • Android进程框架:进程创建、启动与调度流程 文章目录 一 进程创建与启动流程 二 进程的优先级 三 进程调度流程 Android系统的启动流程如下图(点击查看大图)所示: Loader层 当手机处于关机状态时...

    Android进程框架:进程的创建、启动与调度流程

    文章目录

    • 一 进程的创建与启动流程
    • 二 进程的优先级
    • 三 进程的调度流程

    Android系统的启动流程如下图(点击查看大图)所示:

    Loader层

    1. 当手机处于关机状态时,长按电源键开机,引导芯片开始从固化在Boot ROM里的预设代码开始执行,然后加载引导程序Boot Loader到RAM。
    2. Boot Loader被加载到RAM之后开始执行,该程序主要完成检查RAM,初始化硬件参数等功能。

    Kernel层

    1. 引导程序之后进入Android内核层,先启动swapper进程(idle进程),该进程用来初始化进程管理、内存管理、加载Display、Camera Driver、Binder Driver等相关工作。
    2. swapper进程进程之后再启动kthreadd进程,该进程会创建内核工作线程kworkder、软中断线程ksoftirqd、thernal等内核守护进程,kthreadd进程是所有内核进程的鼻祖。

    Native层

    1. 接着会启动init进程,init进程是所有用户进程的鼻祖,它会接着孵化出ueventd、logd、healthd、installd、adbd、lmkd等用户守护进程,启动ServiceManager来管理系统
      服务,启动Bootnaim开机动画。
    2. init进程通过解析init.rc文件fork生成Zygote进程,该进程是Android系统第一个Java进程,它是所有Java进程父进程,该进程主要完成了加载ZygoteInit类,注册Zygote Socket
      服务套接字;加载虚拟机;预加载Class;预加载Resources。

    Framework层

    1. init进程接着fork生成Media Server进程,该进程负责启动和管理整个C++ Framwork(包含AudioFlinger、Camera Service等服务)。

    2. Zygote进程接着会fork生成System Server进程,该进程负责启动和管理整个Java Framwork(包含ActivityManagerService、WindowManagerService等服务)。

    App层

    Zygote进程孵化出的第一个应用进程是Launcher进程(桌面),它还会孵化出Browser进程(浏览器)、Phone进程(电话)等。我们每个创建的应用都是一个单独的进程。

    通过上述流程的分析,想必读者已经对Android的整个进程模型有了大致的理解。作为一个应用开发者我们往往更为关注Framework层和App层里进程的创建与管理相关原理,我们来
    一一分析。

    一 进程的创建与启动流程

    在正式介绍进程之前,我们来思考一个问题,何为进程,进程的本质是什么?��

    我们知道,代码是静态的,有代码和资源组成的系统要想运行起来就需要一种动态的存在,进程就是程序的动态执行过程。何为进程?
    进程就是处理执行状态的代码以及相关资源的集合,包括代码端段、文件、信号、CPU状态、内存地址空间等。

    进程使用task_struct结构体来描述,如下所示:

    • 代码段:编译后形成的一些指令
    • 数据段:程序运行时需要的数据
      • 只读数据段:常量
      • 已初始化数据段:全局变量,静态变量
      • 未初始化数据段(bss):未初始化的全局变量和静态变量
    • 堆栈段:程序运行时动态分配的一些内存
    • PCB:进程信息,状态标识等

    关于进程的更多详细信息,读者可以去翻阅Linux相关书籍,这里只是给读者带来一种整体上的理解,我们的重心还是放在进程再Android平台上的应用。

    在文章开篇的时候,我们提到了系统中运行的各种进程,那么这些进程如何被创建呢?��

    我们先来看看我们最熟悉的应用进程是如何被创建的,前面我们已经说来每一个应用都运行在一个单独的进程里,当ActivityManagerService去启动四大组件时,
    如果发现这个组件所在的进程没有启动,就会去创建一个新的进程,启动进程的时机我们在分析四大组件的启动流程的时候也有讲过,这里再总结一下:

    • Activity ActivityStackSupervisor.startSpecificActivityLocked()
    • Service ActiveServices.bringUpServiceLocked()
    • ContentProvider ActivityManagerService.getContentProviderImpl()
      = Broadcast BroadcastQueue.processNextBroadcast()

    这个新进程就是zygote进程通过复制自身来创建的,新进程在启动的过程中还会创建一个Binder线程池(用来做进程通信)和一个消息循环(用来做线程通信)
    整个流程如下图所示:

    1. 当我们点击应用图标启动应用时或者在应用内启动一个带有process标签的Activity时,都会触发创建新进程的请求,这种请求会先通过Binder
      发送给system_server进程,也即是发送给ActivityManagerService进行处理。
    2. system_server进程会调用Process.start()方法,会先收集uid、gid等参数,然后通过Socket方式发送给Zygote进程,请求创建新进程。
    3. Zygote进程接收到创建新进程的请求后,调用ZygoteInit.main()方法进行runSelectLoop()循环体内,当有客户端连接时执行ZygoteConnection.runOnce()
      方法,最后fork生成新的应用进程。
    4. 新创建的进程会调用handleChildProc()方法,最后调用我们非常熟悉的ActivityThread.main()方法。

    注:整个流程会涉及Binder和Socket两种进程通信方式,这个我们后续会有专门的文章单独分析,这个就不再展开。

    整个流程大致就是这样,我们接着来看看具体的代码实现,先来看一张进程启动序列图:

    从第一步到第三步主要是收集整理uid、gid、groups、target-sdk、nice-name等一系列的参数,为后续启动新进程做准备。然后调用openZygoteSocketIfNeeded()方法
    打开Socket通信,向zygote进程发出创建新进程的请求。

    注:第二步中的Process.start()方法是个阻塞操作,它会一直等待进程创建完毕,并返回pid才会完成该方法。

    我们来重点关注几个关键的函数。

    1.1 Process.openZygoteSocketIfNeeded(String abi)

    关于Process类与Zygote进程的通信是如何进行的呢?��

    Process的静态内部类ZygoteState有个成员变量LocalSocket对象,它会与ZygoteInit类的成员变量LocalServerSocket对象建立连接,如下所示:

    客户端

    public static class ZygoteState {
        final LocalSocket socket;
    }

    服务端

    public class ZygoteInit {
        //该Socket与/dev/socket/zygote文件绑定在一起
        private static LocalServerSocket sServerSocket;
    }

    我们来具体看看代码里的实现。

     public static class ZygoteState {
    
        public static ZygoteState connect(String socketAddress) throws IOException {
            DataInputStream zygoteInputStream = null;
            BufferedWriter zygoteWriter = null;
            //创建LocalSocket对象
            final LocalSocket zygoteSocket = new LocalSocket();
    
            try {
                //将LocalSocket与LocalServerSocket建立连接,建立连接的过程就是
                //LocalSocket对象在/dev/socket目录下查找一个名称为"zygote"的文件
                //然后将自己与其绑定起来,这样就建立了连接。
                zygoteSocket.connect(new LocalSocketAddress(socketAddress,
                        LocalSocketAddress.Namespace.RESERVED));
    
                //创建LocalSocket的输入流,以便可以接收Zygote进程发送过来的数据
                zygoteInputStream = new DataInputStream(zygoteSocket.getInputStream());
    
                //创建LocalSocket的输出流,以便可以向Zygote进程发送数据。
                zygoteWriter = new BufferedWriter(new OutputStreamWriter(
                        zygoteSocket.getOutputStream()), 256);
            } catch (IOException ex) {
                try {
                    zygoteSocket.close();
                } catch (IOException ignore) {
                }
    
                throw ex;
            }
    
            String abiListString = getAbiList(zygoteWriter, zygoteInputStream);
            Log.i("Zygote", "Process: zygote socket opened, supported ABIS: " + abiListString);
    
            return new ZygoteState(zygoteSocket, zygoteInputStream, zygoteWriter,
                    Arrays.asList(abiListString.split(",")));
        }
    }

    建立Socket连接的流程很明朗了,如下所示:

    1. 创建LocalSocket对象。
    2. 将LocalSocket与LocalServerSocket建立连接,建立连接的过程就是LocalSocket对象在/dev/socket目录下查找一个名称为”zygote”的文件,然后将自己与其绑定起来,这样就建立了连接。
    3. 创建LocalSocket的输入流,以便可以接收Zygote进程发送过来的数据。
    4. 创建LocalSocket的输出流,以便可以向Zygote进程发送数据。

    1.2 ZygoteInit.main(String argv[])

    ZygoteInit是Zygote进程的启动类,该类会预加载一些类,然后便开启一个循环,等待通过Socket发过来的创建新进程的命令,fork出新的
    子进程。

    ZygoteInit的入口函数就是main()方法,如下所示:

    public class ZygoteInit {
    
        public static void main(String argv[]) {
                // Mark zygote start. This ensures that thread creation will throw
                // an error.
                ZygoteHooks.startZygoteNoThreadCreation();
    
                try {
                    //...
                    registerZygoteSocket(socketName);
                    //...
                    //开启循环                
                    runSelectLoop(abiList);
    
                    closeServerSocket();
                } catch (MethodAndArgsCaller caller) {
                    caller.run();
                } catch (Throwable ex) {
                    Log.e(TAG, "Zygote died with exception", ex);
                    closeServerSocket();
                    throw ex;
                }
            }
    
        // 开启一个选择循环,接收通过Socket发过来的命令,创建新线程
        private static void runSelectLoop(String abiList) throws MethodAndArgsCaller {
    
            ArrayList<FileDescriptor> fds = new ArrayList<FileDescriptor>();
            ArrayList<ZygoteConnection> peers = new ArrayList<ZygoteConnection>();
    
            //sServerSocket指的是Socket通信的服务端,在fds中的索引为0
            fds.add(sServerSocket.getFileDescriptor());
            peers.add(null);
    
            //开启循环
            while (true) {
                StructPollfd[] pollFds = new StructPollfd[fds.size()];
                for (int i = 0; i < pollFds.length; ++i) {
                    pollFds[i] = new StructPollfd();
                    pollFds[i].fd = fds.get(i);
                    pollFds[i].events = (short) POLLIN;
                }
                try {
                    //处理轮询状态,当pollFds有时间到来时则往下执行,否则阻塞在这里。
                    Os.poll(pollFds, -1);
                } catch (ErrnoException ex) {
                    throw new RuntimeException("poll failed", ex);
                }
                for (int i = pollFds.length - 1; i >= 0; --i) {
    
                    //采用IO多路复用机制,当接收到客户端发出的连接请求时或者数据处理请求到来时则
                    //往下执行,否则进入continue跳出本次循环。
                    if ((pollFds[i].revents & POLLIN) == 0) {
                        continue;
                    }
                    //索引为0,即为sServerSocket,表示接收到客户端发来的连接请求。
                    if (i == 0) {
                        ZygoteConnection newPeer = acceptCommandPeer(abiList);
                        peers.add(newPeer);
                        fds.add(newPeer.getFileDesciptor());
                    } 
                    //索引不为0,表示通过Socket接收来自对端的数据,并执行相应的操作。
                    else {
                        boolean done = peers.get(i).runOnce();
                        //处理完成后移除相应的文件描述符。
                        if (done) {
                            peers.remove(i);
                            fds.remove(i);
                        }
                    }
                }
            }
        }
    }

    可以发现ZygoteInit在其入口函数main()方法里调用runSelectLoop()开启了循环,接收Socket发来的请求。请求分为两种:

    1. 连接请求
    2. 数据请求

    没有连接请求时Zygote进程会进入休眠状态,当有连接请求到来时,Zygote进程会被唤醒,调用acceptCommadPeer()方法创建Socket通道ZygoteConnection

    private static ZygoteConnection acceptCommandPeer(String abiList) {
        try {
            return new ZygoteConnection(sServerSocket.accept(), abiList);
        } catch (IOException ex) {
            throw new RuntimeException(
                    "IOException during accept()", ex);
        }
    }

    然后调用runOnce()方法读取连接请求里的数据,然后创建新进程。

    此外,连接的过程中服务端接受的到客户端的connect()操作会执行accpet()操作,建立连接手,客户端通过write()写数据,服务端通过read()读数据。

    1.3 ZygoteConnection.runOnce()

    class ZygoteConnection {
    
        boolean runOnce() throws ZygoteInit.MethodAndArgsCaller {
    
                String args[];
                Arguments parsedArgs = null;
                FileDescriptor[] descriptors;
    
                try {
                    //读取客户端发过来的参数列表
                    args = readArgumentList();
                    descriptors = mSocket.getAncillaryFileDescriptors();
                } catch (IOException ex) {
                    Log.w(TAG, "IOException on command socket " + ex.getMessage());
                    closeSocket();
                    return true;
                }
    
                //... 参数处理
    
                try {
    
                    //... 参数处理
    
    
                    //调用Zygote.forkAndSpecialize(来fork出新进程
                    pid = Zygote.forkAndSpecialize(parsedArgs.uid, parsedArgs.gid, parsedArgs.gids,
                            parsedArgs.debugFlags, rlimits, parsedArgs.mountExternal, parsedArgs.seInfo,
                            parsedArgs.niceName, fdsToClose, parsedArgs.instructionSet,
                            parsedArgs.appDataDir);
                } catch (ErrnoException ex) {
                    logAndPrintError(newStderr, "Exception creating pipe", ex);
                } catch (IllegalArgumentException ex) {
                    logAndPrintError(newStderr, "Invalid zygote arguments", ex);
                } catch (ZygoteSecurityException ex) {
                    logAndPrintError(newStderr,
                            "Zygote security policy prevents request: ", ex);
                }
    
                try {
                    //pid == 0时表示当前是在新创建的子进程重磅执行
                    if (pid == 0) {
                        // in child
                        IoUtils.closeQuietly(serverPipeFd);
                        serverPipeFd = null;
                        handleChildProc(parsedArgs, descriptors, childPipeFd, newStderr);
    
                        // should never get here, the child is expected to either
                        // throw ZygoteInit.MethodAndArgsCaller or exec().
                        return true;
                    } 
                    // pid < 0表示创建新进程失败,pid > 0 表示当前是在父进程中执行
                    else {
                        // in parent...pid of < 0 means failure
                        IoUtils.closeQuietly(childPipeFd);
                        childPipeFd = null;
                        return handleParentProc(pid, descriptors, serverPipeFd, parsedArgs);
                    }
                } finally {
                    IoUtils.closeQuietly(childPipeFd);
                    IoUtils.closeQuietly(serverPipeFd);
                }
         }
    }

    该方法主要用来读取进程启动参数,然后调用Zygote.forkAndSpecialize()方法fork出新进程,该方法是创建新进程的核心方法,它主要会陆续调用三个
    方法来完成工作:

    1. preFork():先停止Zygote进程的四个Daemon子线程的运行以及初始化GC堆。这四个Daemon子线程分别为:Java堆内存管理现场、堆线下引用队列线程、析构线程与监控线程。
    2. nativeForkAndSpecialize():调用Linux系统函数fork()创建新进程,创建Java堆处理的线程池,重置GC性能数据,设置进程的信号处理函数,启动JDWP线程。
    3. postForkCommon():启动之前停止的Zygote进程的四个Daemon子线程。

    上面的方法都完成会后,新进程会创建完成,并返回pid,接着就调用handleChildProc()来启动新进程。handleChildProc()方法会接着调用RuntimeInit.zygoteInit()来
    完成新进程的启动。

    1.4 RuntimeInit.zygoteInit(int targetSdkVersion, String[] argv, ClassLoader classLoader)

    这个就是个关键的方法了,它主要用来创建一些运行时环境,我们来看一看。

    public class RuntimeInit {
    
        public static final void zygoteInit(int targetSdkVersion, String[] argv, ClassLoader classLoader)
                throws ZygoteInit.MethodAndArgsCaller {
            if (DEBUG) Slog.d(TAG, "RuntimeInit: Starting application from zygote");
    
            Trace.traceBegin(Trace.TRACE_TAG_ACTIVITY_MANAGER, "RuntimeInit");
            redirectLogStreams();
            //创建应用进程的时区和键盘等通用信息
            commonInit();
            //在应用进程中创建一个Binder线程池
            nativeZygoteInit();
            //创建应用信息
            applicationInit(targetSdkVersion, argv, classLoader);
        }
    }

    该方法主要完成三件事:

    1. 调用commonInit()方法创建应用进程的时区和键盘等通用信息。
    2. 调用nativeZygoteInit()方法在应用进程中创建一个Binder线程池。
    3. 调用applicationInit(targetSdkVersion, argv, classLoader)方法创建应用信息。

    Binder线程池我们后续的文章会分析,我们重点来看看applicationInit(targetSdkVersion, argv, classLoader)方法的实现,它主要用来完成应用的创建。

    该方法里的argv参数指的就是ActivityThread,该方法会调用invokeStaticMain()通过反射的方式调用ActivityThread类的main()方法。如下所示:

    public class RuntimeInit {
    
          private static void applicationInit(int targetSdkVersion, String[] argv, ClassLoader classLoader)
                  throws ZygoteInit.MethodAndArgsCaller { 
              //...
    
              // Remaining arguments are passed to the start class's static main
              invokeStaticMain(args.startClass, args.startArgs, classLoader);
          }
    
          private static void invokeStaticMain(String className, String[] argv, ClassLoader classLoader)
                  throws ZygoteInit.MethodAndArgsCaller {
              Class<?> cl;
    
              //通过反射调用ActivityThread类的main()方法
              try {
                  cl = Class.forName(className, true, classLoader);
              } catch (ClassNotFoundException ex) {
                  throw new RuntimeException(
                          "Missing class when invoking static main " + className,
                          ex);
              }
    
              Method m;
              try {
                  m = cl.getMethod("main", new Class[] { String[].class });
              } catch (NoSuchMethodException ex) {
                  throw new RuntimeException(
                          "Missing static main on " + className, ex);
              } catch (SecurityException ex) {
                  throw new RuntimeException(
                          "Problem getting static main on " + className, ex);
              }
              //...
          }  
    }

    走到ActivityThread类的main()方法,我们就很熟悉了,我们知道在main()方法里,会创建主线程Looper,并开启消息循环,如下所示:

    public final class ActivityThread {
    
       public static void main(String[] args) {
           //...
           Environment.initForCurrentUser();
           //...
           Process.setArgV0("<pre-initialized>");
           //创建主线程looper
           Looper.prepareMainLooper();
    
           ActivityThread thread = new ActivityThread();
           //attach到系统进程
           thread.attach(false);
    
           if (sMainThreadHandler == null) {
               sMainThreadHandler = thread.getHandler();
           }
    
           //主线程进入循环状态
           Looper.loop();
    
           throw new RuntimeException("Main thread loop unexpectedly exited");
       } 
    }

    前面我们从Process.start()开始讲起,分析了应用进程的创建及启动流程,既然有启动就会有结束,接下来我们从
    Process.killProcess()开始讲起,继续分析进程的结束流程。

    二 进程的优先级

    进程按照优先级大小不同又可以分为实时进程与普通进程。

    prio值越小表示进程优先级越高,

    • 静态优先级:优先级不会随时间改变,内核也不会修改,只能通过系统调用改变nice值,优先级映射公式为:static_prio = MAX_RT_PRIO + nice + 20,其中MAX_RT_PRIO = 100,那么取值区间为[100, 139];对应普通进程;
    • 实时优先级:取值区间为[0, MAX_RT_PRIO -1],其中MAX_RT_PRIO = 100,那么取值区间为[0, 99];对应实时进程;
    • 懂爱优先级:调度程序通过增加或者减少进程优先级,来达到奖励IO消耗型或按照惩罚CPU消耗型的进程的效果。区间范围[0, MX_PRIO-1],其中MX_PRIO = 140,那么取值区间为[0,139];

    三 进程调度流程

    进程的调度在Process类里完成。

    3.1 优先级调度

    优先级调度方法

    setThreadPriority(int tid, int priority)

    进程的优先级以及对应的nice值如下所示:

    • THREAD_PRIORITY_LOWEST 19 最低优先级
    • THREAD_PRIORITY_BACKGROUND 10 后台
    • THREAD_PRIORITY_LESS_FAVORABLE 1 比默认略低
    • THREAD_PRIORITY_DEFAULT 0 默认
    • THREAD_PRIORITY_MORE_FAVORABLE -1 比默认略高
    • THREAD_PRIORITY_FOREGROUND -2 前台
    • THREAD_PRIORITY_DISPLAY -4 显示相关
    • THREAD_PRIORITY_URGENT_DISPLAY -8 显示(更为重要),input事件
    • THREAD_PRIORITY_AUDIO -16 音频相关
    • THREAD_PRIORITY_URGENT_AUDIO -19 音频(更为重要)

    3.2 组优先级调度

    进程组优先级调度方法

    setProcessGroup(int pid, int group)
    setThreadGroup(int tid, int group)

    组优先级及对应取值

    • THREAD_GROUP_DEFAULT -1 仅用于setProcessGroup,将优先级<=10的进程提升到-2
    • THREAD_GROUP_BG_NONINTERACTIVE 0 CPU分时的时长缩短
    • THREAD_GROUP_FOREGROUND 1 CPU分时的时长正常
    • THREAD_GROUP_SYSTEM 2 系统线程组
    • THREAD_GROUP_AUDIO_APP 3 应用程序音频
    • THREAD_GROUP_AUDIO_SYS 4 系统程序音频

    3.3 调度策略

    调度策略设置方法

    setThreadScheduler(int tid, int policy, int priority)
    • SCHED_OTHER 默认 标准round-robin分时共享策略
    • SCHED_BATCH 批处理调度 针对具有batch风格(批处理)进程的调度策略
    • SCHED_IDLE 空闲调度 针对优先级非常低的适合在后台运行的进程
    • SCHED_FIFO 先进先出 实时调度策略,android暂未实现
    • SCHED_RR 循环调度 实时调度策略,android暂未实现

    3.4 进程adj调度

    另外除了这些基本的调度策略,Android系统还定义了两个和进程相关的状态值,一个就是定义在ProcessList.java里的adj值,另一个
    是定义在ActivityManager.java里的procState值。

    定义在ProcessList.java文件,oom_adj划分为16级,从-17到16之间取值。

    • UNKNOWN_ADJ 16 一般指将要会缓存进程,无法获取确定值
    • CACHED_APP_MAX_ADJ 15 不可见进程的adj最大值 1
    • CACHED_APP_MIN_ADJ 9 不可见进程的adj最小值 2
    • SERVICE_B_AD 8 B List中的Service(较老的、使用可能性更小)
    • PREVIOUS_APP_ADJ 7 上一个App的进程(往往通过按返回键)
    • HOME_APP_ADJ 6 Home进程
    • SERVICE_ADJ 5 服务进程(Service process)
    • HEAVY_WEIGHT_APP_ADJ 4 后台的重量级进程,system/rootdir/init.rc文件中设置
    • BACKUP_APP_ADJ 3 备份进程 3
    • PERCEPTIBLE_APP_ADJ 2 可感知进程,比如后台音乐播放 4
    • VISIBLE_APP_ADJ 1 可见进程(Visible process) 5
    • FOREGROUND_APP_ADJ 0 前台进程(Foreground process) 6
    • PERSISTENT_SERVICE_ADJ -11 关联着系统或persistent进程
    • PERSISTENT_PROC_ADJ -12 系统persistent进程,比如telephony
    • SYSTEM_ADJ -16 系统进程
    • NATIVE_ADJ -17 native进程(不被系统管理)

    更新进程adj值的方法定义在ActivityManagerService中,分别为:

    • updateOomAdjLocked:更新adj,当目标进程为空,或者被杀则返回false;否则返回true;
    • computeOomAdjLocked:计算adj,返回计算后RawAdj值;
    • applyOomAdjLocked:应用adj,当需要杀掉目标进程则返回false;否则返回true。

    那么进程的adj值什么时候会被更新呢?��

    Activity

    • ActivityManagerService.realStartActivityLocked: 启动Activity
    • ActivityStack.resumeTopActivityInnerLocked: 恢复栈顶Activity
    • ActivityStack.finishCurrentActivityLocked: 结束当前Activity
    • ActivityStack.destroyActivityLocked: 摧毁当前Activity

    Service

    • ActiveServices.realStartServiceLocked: 启动服务
    • ActiveServices.bindServiceLocked: 绑定服务(只更新当前app)
    • ActiveServices.unbindServiceLocked: 解绑服务 (只更新当前app)
    • ActiveServices.bringDownServiceLocked: 结束服务 (只更新当前app)
    • ActiveServices.sendServiceArgsLocked: 在bringup或则cleanup服务过程调用 (只更新当前app)

    BroadcastReceiver

    • BroadcastQueue.processNextBroadcast: 处理下一个广播
    • BroadcastQueue.processCurBroadcastLocked: 处理当前广播
    • BroadcastQueue.deliverToRegisteredReceiverLocked: 分发已注册的广播 (只更新当前app)

    ContentProvider

    • ActivityManagerService.removeContentProvider: 移除provider
    • ActivityManagerService.publishContentProviders: 发布provider (只更新当前app)
    • ActivityManagerService.getContentProviderImpl: 获取provider (只更新当前app)

    另外,Lowmemorykiller也会根据当前的内存情况逐级进行进程释放,一共有六个级别(上面加粗的部分):

    • CACHED_APP_MAX_ADJ
    • CACHED_APP_MIN_ADJ
    • BACKUP_APP_ADJ
    • PERCEPTIBLE_APP_ADJ
    • VISIBLE_APP_ADJ
    • FOREGROUND_APP_ADJ

    定义在ActivityManager.java文件,process_state划分18类,从-1到16之间取值

    • PROCESS_STATE_CACHED_EMPTY 16 进程处于cached状态,且为空进程
    • PROCESS_STATE_CACHED_ACTIVITY_CLIENT 15 进程处于cached状态,且为另一个cached进程(内含Activity)的client进程
    • PROCESS_STATE_CACHED_ACTIVITY 14 进程处于cached状态,且内含Activity
    • PROCESS_STATE_LAST_ACTIVITY 13 后台进程,且拥有上一次显示的Activity
    • PROCESS_STATE_HOME 12 后台进程,且拥有home Activity
    • PROCESS_STATE_RECEIVER 11 后台进程,且正在运行receiver
    • PROCESS_STATE_SERVICE 10 后台进程,且正在运行service
    • PROCESS_STATE_HEAVY_WEIGHT 9 后台进程,但无法执行restore,因此尽量避免kill该进程
    • PROCESS_STATE_BACKUP 8 后台进程,正在运行backup/restore操作
    • PROCESS_STATE_IMPORTANT_BACKGROUND 7 对用户很重要的进程,用户不可感知其存在
    • PROCESS_STATE_IMPORTANT_FOREGROUND 6 对用户很重要的进程,用户可感知其存在
    • PROCESS_STATE_TOP_SLEEPING 5 与PROCESS_STATE_TOP一样,但此时设备正处于休眠状态
    • PROCESS_STATE_FOREGROUND_SERVICE 4 拥有给一个前台Service
    • PROCESS_STATE_BOUND_FOREGROUND_SERVICE 3 拥有给一个前台Service,且由系统绑定
    • PROCESS_STATE_TOP 2 拥有当前用户可见的top Activity
    • PROCESS_STATE_PERSISTENT_UI 1 persistent系统进程,并正在执行UI操作
    • PROCESS_STATE_PERSISTENT 0 persistent系统进程
    • PROCESS_STATE_NONEXISTENT -1 不存在的进程

    根据上面说描述的adj值和state值,我们又可以按照重要性程度的不同,将进程划分为五级:

    前台进程

    用户当前操作所必需的进程。如果一个进程满足以下任一条件,即视为前台进程:

    • 托管用户正在交互的 Activity(已调用 Activity 的 onResume() 方法)
    • 托管某个 Service,后者绑定到用户正在交互的 Activity
    • 托管正在“前台”运行的 Service(服务已调用 startForeground())
    • 托管正执行一个生命周期回调的 Service(onCreate()、onStart() 或 onDestroy())
    • 托管正执行其 onReceive() 方法的 BroadcastReceiver

    通常,在任意给定时间前台进程都为数不多。只有在内存不足以支持它们同时继续运行这一万不得已的情况下,系统才会终止它们。 此时,设备往往已达到内存分页状态,因此需要终止一些前台进程来确保用户界面正常响应。

    可见进程

    没有任何前台组件、但仍会影响用户在屏幕上所见内容的进程。 如果一个进程满足以下任一条件,即视为可见进程:

    • 托管不在前台、但仍对用户可见的 Activity(已调用其 onPause() 方法)。例如,如果前台 Activity 启动了一个对话框,允许在其后显示上一 Activity,则有可能会发生这种情况。
    • 托管绑定到可见(或前台)Activity 的 Service。

    可见进程被视为是极其重要的进程,除非为了维持所有前台进程同时运行而必须终止,否则系统不会终止这些进程。

    服务进程

    正在运行已使用 startService() 方法启动的服务且不属于上述两个更高类别进程的进程。尽管服务进程与用户所见内容没有直接关联,但是它们通常在执行一些用户关
    心的操作(例如,在后台播放音乐或从网络下载数据)。因此,除非内存不足以维持所有前台进程和可见进程同时运行,否则系统会让服务进程保持运行状态。

    后台进程

    包含目前对用户不可见的 Activity 的进程(已调用 Activity 的 onStop() 方法)。这些进程对用户体验没有直接影响,系统可能随时终止它们,以回收内存供前台进程、可见进程或服务进程使用。 通常会有很多后台进程在运行,因此它们会保存在 LRU (最近最少使用)列表中,以确保包含用户最近查看的 Activity 的进程最后一个被终止。如果某个 Activity 正确实现了生命周期方法,并保存了其当前状态,则终止其进程不会对用户体验产生明显影响,因为当用户导航回该 Activity 时,Activity 会恢复其所有可见状态。

    空进程

    不含任何活动应用组件的进程。保留这种进程的的唯一目的是用作缓存,以缩短下次在其中运行组件所需的启动时间。 为使总体系统资源在进程缓存和底层内核缓存之间保持平衡,系统往往会终止这些进程。

    展开全文
  • 进程调度

    千次阅读 2018-08-21 17:50:08
     需要进程调度的理由很充分,即充分利用计算机系统中的CPU资源,让计算机能够多快好省的完成各种任务。为此,可在内存中存放数目远大于计算机系统内CPU个数的进程,让这些进程在操作系统的进程调度器下,能够让进程...
  • FCFS是最简单的调度算法,既可以用作作业调度,也可以用作进程调度 这种算法优先考虑系统中等待时间最长的作业(进程),而不管作业所需执行时间长短, 做法是从后备队列中选择几个最先进入该队列的作业,将...
  • 作业调度和进程调度的辨析

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

    万次阅读 多人点赞 2016-06-17 14:50:16
    日期 ... Linux进程管理与调度 内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为
  • 什么是进程调度 我们的计算机内有很多很多个进程,但是处理机数量又是很少的,这就导致这些进程之间会争夺处理机资源。这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之...
  • OS进程调度及典型调度算法

    千次阅读 2017-05-03 21:11:07
    进程调度的功能 记录系统中的所有进程的状态、优先级数和资源的需求情况 确定调度算法,决定将CPU分配给哪个进程多少时间 分配处理机给进程,进行CPU现场的保护和移交 调度的层次一个作业从提交开始直到完成,往往要...
  • Linux进程调度

    千次阅读 2018-02-07 17:33:12
    Linux的进程调度 进程调度算法用来解决以何种次序对各就绪进程进行处理机的分配以及按照何种时间比例让进程占用处理机。 一、完全公平调度算法简称CFS Linux为了保证交互式应用和桌面系统的性能,所以对进程的...
  • 操作系统3——处理机调度(作业调度+进程调度) 目录 操作系统3——处理机调度(作业调度+进程调度) 1、处理机的调度层次和目标 2、作业调度——先来先服务调度算法(FCFS) 3、作业调度——短作业优先调度...
  • 进程和线程调度算法

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

    千次阅读 2019-11-14 22:02:31
    一、 设计一个有N个进程其行的进程调度算法。 进程调度算法:采用最高优先数的调度算法(即把处理机分配给优先数最高的进程)。 每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数...
  • 综合应用下列知识点设计并实现操作系统的进程调度:邻接表,布尔数组,非阻塞输入,图形用户界面GUI,进程控制块,进程状态转换,多级反馈队列进程调度算法。 2、 加深理解操作系统进程调度的过程。 3、 加深理解...
  • 进程调度详解算法

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

    千次阅读 多人点赞 2020-05-11 20:44:59
    所谓进程调度方式,是指当某个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有以下两种进程调度方式: 非剥夺调度方式,又称非...
  • Java操作系统进程调度算法——优先级调度(HPF)算法 文章目录Java操作系统进程调度算法——优先级调度(HPF)算法前言一、算法思想二、数据结构1.定义(PCB)进程控制块2.实现思路三、流程图四、完整代码运行结果1、输入...
  • 【原理】 进程调度算法

    千次阅读 2018-03-07 15:07:46
    需要进程调度的理由很简单,即充分利用计算机系统中的CPU资源,让计算机系统能够多快好省地完成我们让它做的各种任务。为此,可在内存中可存放数目远大于计算机系统内CPU个数的进程,让这些进程在操作系统的进程调度...
  • 进程调度算法

    万次阅读 多人点赞 2019-03-20 19:58:15
    操作系统常见的进程调度算法 调度算法是指:根据系统的资源分配策略所规定的资源分配算法。常见的进程调度算法有:  1.先来先去服务  2.时间片轮转法  3.多级反馈队列算法  4.最短进程优先  5.最短剩余...
  • 编写程序完成单处理器系统中的进程调度, 要求实现时间片轮转、 优先数、 最短进程优 先和最短剩余时间优先四种调度算法。 实验具体包括: 首先确定进程控制块的内容, 进程控 制块的组成方式; 然后完成进程创建...
  • 在分时系统中,最简单也较常用的是基于时间片的轮转调度算法。该算法采取了非常公平的处理机分配方式,即让就绪队列上的每个进程每次仅运行一个时间片。
  • 优先级调度算法,就是把处理机分配给就绪队列中优先级最高的进程,细分有非抢占式和抢占式两种

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 183,095
精华内容 73,238
关键字:

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