精华内容
下载资源
问答
  • Linux进程管理与调度-之-目录导航

    万次阅读 多人点赞 2016-05-19 19:57:29
    日期 内核版本 架构 作者 GitHub CSDN 2016-05-19 Linux-4.5 ... Linux进程管理与调度 进程的描述 CSDN GitHub Linux进程描述符task_struct结构体详解–Linux进程的管理与调度(一) study/kernel/p
    日期内核版本架构作者GitHubCSDN
    2016-07-21Linux-4.6X86 & armgatiemeLinuxDeviceDriversLinux进程管理与调度

    1 项目链接


    项目描述
    KernelInKernel一个运行在linux上的小巧内核, 修改了linux-kernel的start_kernel以启动我们自己的内核, 基于jserv/kernel-in-kernel(基于linux-4.1.0)和mengning/mykernel(基于linux-3.9.4), 适合学习和研究调度算法
    Linux进程管理与调度CSDN博客–Linux进程管理与调度
    LDD-LinuxDeviceDrivers与CSDN博客同步更新, 但是除了包含博客的内容, 还包含了一些以驱动方式实现的实验代码

    2 进程的描述


    CSDNGitHub
    Linux进程描述符task_struct结构体详解–Linux进程的管理与调度(一)study/kernel/01-process/01-task/01-task_struct
    Linux的命名空间详解–Linux进程的管理与调度(二)study/kernel/01-process/01-task/02-namespace
    Linux进程ID号–Linux进程的管理与调度(三)study/kernel/01-process/01-task/03-pid

    3 进程的创建


    CSDNGitHub
    Linux下的进程类别(内核线程、轻量级进程和用户进程)以及其创建方式–Linux进程的管理与调度(四) study/kernel/01-process/02-create/01-duplicate
    Linux下0号进程的前世(init_task进程)今生(idle进程)----Linux进程的管理与调度(五)study/kernel/01-process/02-create/02-idel
    Linux下1号进程的前世(kernel_init)今生(init进程)----Linux进程的管理与调度(六)study/kernel/01-process/02-create/03-init
    Linux下2号进程的kthreadd–Linux进程的管理与调度(七)study/kernel/01-process/02-create/04-kthreadd
    Linux下进程的创建过程分析(_do_fork/do_fork详解)–Linux进程的管理与调度(八)study/kernel/01-process/02-create/05-do_fork
    Linux进程内核栈与thread_info结构详解–Linux进程的管理与调度(九)study/kernel/01-process/02-create/06-thread_info
    Linux内核线程kernel thread详解–Linux进程的管理与调度(十)study/kernel/01-process/02-create/07-kernel_thead

    4 进程的加载与运行


    CSDNGitHub
    Linux进程启动过程分析do_execve(可执行程序的加载和运行)—Linux进程的管理与调度(十一)study/kernel/01-process/03-execute/01-do_execve
    LinuxELF文件格式详解–Linux进程的管理与调度(十二)study/kernel/01-process/03-execute/02-elf
    ELF文件的加载过程(load_elf_binary函数详解)–Linux进程的管理与调度(十三)study/kernel/01-process/03-execute/03-load_elf_binary

    5 进程的退出


    CSDNGitHub
    Linux进程退出详解(do_exit)–Linux进程的管理与调度(十四))study/kernel/01-process/04-exit/01-do_exit

    6 进程的调度


    CSDNGitHub
    Linux进程调度器概述–Linux进程的管理与调度(十五)study/kernel/01-process/05-schedule/01-introduction
    Linux进程调度策略的发展和演变–Linux进程的管理与调度(十六)study/kernel/01-process/05-schedule/02-develop
    Linux进程调度器的设计–Linux进程的管理与调度(十七)study/kernel/01-process/05-schedule/03-design
    Linux核心调度器之周期性调度器scheduler_tick–Linux进程的管理与调度(十八)study/kernel/01-process/05-schedule/03-design/02-periodic_scheduler
    Linux进程核心调度器之主调度器–Linux进程的管理与调度(十九)study/kernel/01-process/05-schedule/03-design/03-main_scheduler
    Linux用户抢占和内核抢占详解(概念, 实现和触发时机)–Linux进程的管理与调度(二十)study/kernel/01-process/05-schedule/03-design/04-preempt
    Linux进程上下文切换过程context_switch详解–Linux进程的管理与调度(二十一)study/kernel/01-process/05-schedule/03-design/05-context_switch
    Linux进程优先级的处理–Linux进程的管理与调度(二十二)study/kernel/01-process/05-schedule/03-design/06-priority
    Linux唤醒抢占----Linux进程的管理与调度(二十三)study/kernel/01-process/05-schedule/03-design/07-wakeup

    #7 调度普通进程-完全公平调度器CFS

    CSDNGitHub
    Linux进程调度之CFS调度器概述–Linux进程的管理与调度(二十四)study/kernel/01-process/05-schedule/07-cfs/01-cfs/
    Linux CFS调度器之负荷权重load_weight–Linux进程的管理与调度(二十五)study/kernel/01-process/05-schedule/07-cfs/02-load_weight/
    Linux CFS调度器之虚拟时钟vruntime与调度延迟–Linux进程的管理与调度(二十六)study/kernel/01-process/05-schedule/07-cfs/03-vruntime/
    Linux CFS调度器之队列操作–Linux进程的管理与调度(二十七)study/kernel/01-process/05-schedule/07-cfs/04-queue/
    Linux CFS调度器之pick_next_task_fair选择下一个被调度的进程–Linux进程的管理与调度(二十八)study/kernel/01-process/05-schedule/07-cfs/05-pick_next/
    Linux CFS调度器之task_tick_fair处理周期性调度器–Linux进程的管理与调度(二十九)study/kernel/01-process/05-schedule/07-cfs/06-task_tick_fair/
    Linux CFS调度器之唤醒抢占–Linux进程的管理与调度(三十)study/kernel/01-process/05-schedule/07-cfs/07-task_new_fair/
    Linux CFS调度器之唤醒WAKE_AFFINE 机制–Linux进程的管理与调度(三十一)study/kernel/01-process/05-schedule/07-cfs/08-wake_affine

    7 公众号


    工作以后,很长时间,没写博客了。近期准备重新拾起来,知识是无界的,我最喜欢的就是把技术当笔记一样分享出来跟大家一起讨论,一些思考。

    近期开了公众号和知乎, 刚开始运营,欢迎大家多多支持。

    推荐大家关注下我的公众号,内核干货,谢谢。

    后期所有博文都将在这些平台同步推送,大家选择自己关注的平台即可。当然推荐大家把公众号关注了,谢谢。

    CSDN公众号知乎自建站点
    kernel-csdn内核干货知乎oskernellsb
    kernel-csdn公众号 "内核干货"知乎在这里插入图片描述
    展开全文
  • 操作系统课件 第3章 进程管理与调度.ppt
  • linux进程管理与调度(一)

    千次阅读 2017-07-19 20:39:09
    从本节开始,将对linux内核的进程管理与调度子系统进行分析,其中使用的内核版本是4.4。1 进程描述在linux内核中,每一个进程唯一对应一个struct task_struct结构体,内核通过这些task_struct的管理实现对进程的管理...

    转载请标明出处floater的csdn blog,http://blog.csdn.net/flaoter

    进程的管理与调度是所有操作系统的核心功能。从内核的角度来看,进程是内核分配资源(CPU,Memory)的重要单元,是计算机用来管理这些资源的一种抽象。从本节开始,将对linux内核的进程管理与调度子系统进行分析,其中使用的内核版本是4.4。

    1 进程描述

    在linux内核中,每一个进程唯一对应一个struct task_struct结构体,内核通过这些task_struct的管理实现对进程的管理。此数据结构定义在./include/linux/sched.h中,结构太过庞大,下面作为实例只列出了前面几行。

    struct task_struct {
        volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
        void *stack;
        atomic_t usage;
        unsigned int flags; /* per process flags, defined below */
        unsigned int ptrace;
    
    #ifdef CONFIG_SMP
        struct llist_node wake_entry;
        int on_cpu;
        unsigned int wakee_flips;
        unsigned long wakee_flip_decay_ts;
        struct task_struct *last_wakee;
    
        int wake_cpu;
    #endif
        int on_rq;
    ....
    }

    按照结构成员的用途,大体上分成了如下的类别,
    (1) 基本信息。comm, pid, tgid, uid, gid, stack, on_cpu, on_rq, in_execve, in_iowait…
    (2) 进程关系。real_parent, children, sibling…
    (3) 状态相关。state, exit_state, exit_code…
    (4) 使用内存。mm, active_mm, min_flt, maj_flt…
    (5) 调度相关。prio, static_prio, normal_prio, rt_prio, sched_class, se, policy…
    (6) 事件相关。utime, stime, start_time, real_start_time…
    (7) 信号相关。signal, sighand, blocked, real_blocked, pending…
    (8)文件系统。fs, files, nameidata…
    (9) Misc

    2 进程状态

    进程的状态定义如下所示,

    #define TASK_RUNNING        0    //R态,进程正在运行或在rq中等待运行
    #define TASK_INTERRUPTIBLE  1    //S态,阻塞等待资源或者信号
    #define TASK_UNINTERRUPTIBLE    2  //D态,阻塞等待资源
    #define __TASK_STOPPED      4  //暂停状态
    #define __TASK_TRACED       8  //跟踪状态
    /* in tsk->exit_state */
    #define EXIT_DEAD       16
    #define EXIT_ZOMBIE     32
    #define EXIT_TRACE      (EXIT_ZOMBIE | EXIT_DEAD)
    /* in tsk->state again */
    #define TASK_DEAD       64
    #define TASK_WAKEKILL       128
    #define TASK_WAKING     256
    #define TASK_PARKED     512
    #define TASK_NOLOAD     1024
    #define TASK_STATE_MAX      2048

    状态转换的状态机如图所示,
    task_state

    3 进程初始化

    进程的初始化是在start_kernel中的reset_init中实现的,创建了两个进程init和kthreadd。

    kernel_thread(kernel_init, NULL, CLONE_FS);  //init进程创建
    
    pid = kernel_thread(kthreadd, NULL, CLONE_FS | CLONE_FILES); //kthread内核线程创建

    创建的init进程再通过解析init.rc等文件进行用户进程的创建。

    static int __ref kernel_init(void *unused)
    {
    ...
        if (!try_to_run_init_process("/sbin/init") ||   
            !try_to_run_init_process("/etc/init") ||
            !try_to_run_init_process("/bin/init") ||
            !try_to_run_init_process("/bin/sh"))        //执行init程序,parse init.rc,创建子进程
            return 0;
    ...
    }
    

    init进程与用户进程的关系如下:
    init-+-adbd-+-sh—busybox
    | -4*[{adbd}]
    |-cndaemon
    |-cp_diskserver---{cp_diskserver}
    |-debuggerd
    |-debuggerd64
    |-drmserver-+-{Binder_1}
    |
    -{Binder_2}
    |-gatekeeperd
    |-gnss_download—2*[{gnss_download}]
    |-gpsd—2*[{gpsd}]
    |-healthd
    |-installd
    |-keystore
    |-lmfs
    |-lmkd
    |-logd-+-{logd.auditd}
    | |-{logd.control}
    | |-{logd.daemon}
    | |-5*[{logd.reader.per}]
    | |-{logd.reader}
    | `-{logd.writer}
    |-main-+-.quicksearchbox-+-{ApplicationsPro}
    | | |-{Binder_1}
    | | |-{Binder_2}
    | | |-{FinalizerDaemon}
    | | |-{FinalizerWatchd}
    | | |-{HeapTaskDaemon}

    创建的kthreadd内核线程通过遍历kthread_create_list创建内核线程。

    int kthreadd(void *unused)
    {
    ...
        set_task_comm(tsk, "kthreadd");
        for (;;) {
    ...
            spin_lock(&kthread_create_lock);
            while (!list_empty(&kthread_create_list)) {
                struct kthread_create_info *create;
    
                create = list_entry(kthread_create_list.next,
                            struct kthread_create_info, list);   //遍历kthread_create_list,创建子线程
                list_del_init(&create->list);
                spin_unlock(&kthread_create_lock);
    
                create_kthread(create);
    
                spin_lock(&kthread_create_lock);
            }
            spin_unlock(&kthread_create_lock);
        }
    
        return 0;
    }
    

    kthreadd与内核线程的关系如下:
    kthreadd-+-VserTestWq
    |-adaptive_ts_wor
    |-agdsp_access
    |-ata_sff
    |-aud_sblock-1-3
    |-aud_sblock-1-4
    |-binder
    |-bioset
    |-bm_perf
    |-carveout_camera
    |-carveout_fb
    |-carveout_mm
    |-carveout_overla
    |-cfg80211
    |-cfinteractive
    |-compr drain
    |-compr monitor
    |-crypto
    |-deferwq
    |-devfreq_wq
    |-dhd_dpc
    |-dhd_rxf
    |-dhd_watchdog_th

    4 进程创建

    常用的进程创建方法如下:
    fork—————–用户进程
    pthread_create—- 用户线程
    kthread_create —-内核线程
    do_fork

    5 thread_info与内核栈

    thread_info保存了特定体系结构的汇编代码段需要访问的那部分进程的数据。内核栈供用户进程的内核代码或内核线程使用。arm 32bit 处理器thread_info和内核栈task->stack合用2页内存空间。

    union thread_union {
        struct thread_info thread_info;
        unsigned long stack[THREAD_SIZE/sizeof(long)];
    };
    

    常用的current指针指向了当前的thread_info的task成员。

    #define get_current() (current_thread_info()->task)
    #define current get_current()
    static inline struct thread_info *current_thread_info(void)
    {
        return (struct thread_info *)
            (current_stack_pointer & ~(THREAD_SIZE - 1));
    }
    

    current_thread_info就是当前sp屏蔽掉低12位。
    kernel_kstack

    展开全文
  • 收集的一篇论文 嵌入式软件模拟测试平台中进程管理与调度的研究实现
  • linux进程管理与调度

    千次阅读 2015-12-25 11:03:15
    进程管理  进程描述符及任务结构 进程存放在叫做任务队列(tasklist)的双向循环链表中。链表中的每一项包含一个具体进程的所有信息,类型为task_struct,称为进程描述符(process descriptor),该
    [日期:2014-08-10]来源:Linux社区  作者:walkerkalr[字体:  ]

    进程的管理与调度

    进程管理 

    进程描述符及任务结构

    进程存放在叫做任务队列(tasklist)的双向循环链表中。链表中的每一项包含一个具体进程的所有信息,类型为task_struct,称为进程描述符(process descriptor),该结构定义在<linux/sched.h>文件中。

    Linux通过slab分配器分配task_struct结构,这样能达到对象复用和缓存着色(cache coloring)的目的。另一方面,为了避免使用额外的寄存器存储专门记录,让像x86这样寄存器较少的硬件体系结构只要通过栈指针就能计算出task_struct的位置,该结构为thread_info,在文件<asm/thread_info.h>中定义。

    Linux中可以用ps命令查看所有进程的信息。

    Linux基础篇之内存管理机制 http://www.linuxidc.com/Linux/2014-03/98293.htm

    Linux内存管理之高端内存 http://www.linuxidc.com/Linux/2013-06/85693.htm

    Linux内存管理之分段机制 http://www.linuxidc.com/Linux/2012-11/74480.htm

    Linux内存管理伙伴算法 http://www.linuxidc.com/Linux/2012-09/70711.htm

    进程状态

    task_struct中的state描述进程的当前状态。进程的状态一共有5种,而进程必然处于其中一种状态:

    1)TASK_RUNNING(运行)——进程是可执行的,它或者正在执行,或者在运行队列中等待执行。这是进程在用户空间中执行唯一可能的状态;也可以应用到内核空间中正在执行的进程。

    2)TASK_INTERRUPTIBLE(可中断)——进程正在睡眠(也就是说它被阻塞)等待某些条件的达成。一旦这些条件达成,内核就会把进程状态设置为运行,处于此状态的进程也会因为接收到信号而提前被唤醒并投入运行。

    3)TASK_UNINTERRUPTIBLE(不可中断)——除了不会因为接收到信号而被唤醒从而投入运行外,这个状态与可打断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于处于此状态的任务对信号不作响应,所以较之可中断状态,使用得较少。

    4)TASK_ZOMBIE(僵死)——该进程已经结束了,但是其父进程还没有调用wait4()系统调用。为了父进程能够获知它的消息,子进程的进程描述符仍然被保留着。一旦父进程调用了wait4(),进程描述符就会被释放。

    5)TASK_STOPPED(停止)——进程停止执行,进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP,SIGTSTP,SIGTTIN,SIGTTOU等信号的时候。此外,在调试期间接收到任何信号,都会使进程进入这种状态。

    需要调整进程的状态,最好使用set_task_state(task, state)函数,在必要的时候,它会设置内存屏障来强制其他处理器作重新排序(SMP)。

    进程的各个状态之间的转化构成了进程的整个生命周期,

     

    进程的创建

    在Linux系统中,所有的进程都是PID为1的init进程的后代。内核在系统启动的最后阶段启动init进程。该进程读取系统的初始化脚本(initscript)并执行其他的相关程序,最终完成系统启动的整个进程。

    Linux提供两个函数去处理进程的创建和执行:fork()和exec()。首先,fork()通过拷贝当前进程创建一个子进程。子进程与父进程的区别仅仅在于PID(每个进程唯一),PPID(父进程的PID)和某些资源和统计量(例如挂起的信号)。exec()函数负责读取可执行文件并将其载入地址空间开始运行。

    fork()使用写时拷贝(copy-on-write)页实现。内核在fork进程时不复制整个进程地址空间,让父进程和子进程共享同一个拷贝,当需要写入时,数据才会被复制,使各进程拥有自己的拷贝。在页根本不会被写入的情况下(fork()后立即exec()),fork的实际开销只有复制父进程的页表以及给子进程创建唯一的task_struct。

    创建进程的fork()函数实际上最终是调用clone()函数。创建线程和进程的步骤一样,只是最终传给clone()函数的参数不同。比如,通过一个普通的fork来创建进程,相当于:clone(SIGCHLD, 0);创建一个和父进程共享地址空间,文件系统资源,文件描述符和信号处理程序的进程,即一个线程:clone(CLONE_VM | CLONE_FS | CLONE_FILES |CLONE_SIGHAND, 0)。

    在内核中创建的内核线程与普通的进程之间还有个主要区别在于:内核线程没有独立的地址空间,它们只能在内核空间运行。

    fork和vfork的区别

    fork()与vfock()都是创建一个进程,那他们有什么区别呢?总结有以下三点区别: 
    1. fork ():子进程拷贝父进程的数据段,代码段 
    vfork ( ):子进程与父进程共享数据段 
    2. fork ()父子进程的执行次序不确定 
    vfork 保证子进程先运行,在调用exec 或exit 之前与父进程数据是共享的,在它调用exec
    或exit 之后父进程才可能被调度运行。 
    3. vfork ()保证子进程先运行,在她调用exec 或exit 之后父进程才可能被调度运行。如果在
    调用这两个函数之前子进程依赖于父进程的进一步动作,则会导致死锁。


    进程终止

    进程在运行结束,或接受到它既不能处理也不能忽略的信号,或异常时,都会被终结。此时,依靠do_exit()(在kernel/exit.c文件中)把与进程相关联的所有资源都被释放掉(假设进程是这些资源的唯一使用者)。至此,与进程相关的所有资源都被释放掉了。进程不可运行(实际上也没有地址空间让它运行)并处于TASK_ZOMBIE状态。它占用的所有资源就是内核栈、thread_info和task_struct。此时进程存在的唯一目的就是想它的父进程提供信息。在父进程获得已终结的子进程的信息后,或者通知内核它并不关注那些信息后,子进程持有的task_struct等剩余内存才被释放。

    孤儿进程问题

    如果父进程在子进程之前退出,必须有机制保证子进程能找到一个新的父类,否则的话这些成为孤儿的进程就会在退出时永远处于僵死状态,白白的耗费内存。解决方法是给子进程在当前线程组内找一个线程作为父亲,如果不行,就让init做它们的父进程。

    进程调度

    什么是调度

    现在的操作系统都是多任务的,为了能让更多的任务能同时在系统上更好的运行,需要一个管理程序来管理计算机上同时运行的各个任务(也就是进程)。

    这个管理程序就是调度程序,它的功能说起来很简单:

    1.决定哪些进程运行,哪些进程等待

    2.决定每个进程运行多长时间

    此外,为了获得更好的用户体验,运行中的进程还可以立即被其他更紧急的进程打断。总之,调度是一个平衡的过程。一方面,它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程,进程切换过多,CPU的时间会浪费在切换上);另一方面,保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。

    策略

    I/O消耗型和处理器消耗型的进程

    I/O消耗型进程:大部分时间用来提交I/O请求或是等待I/O请求,经常处于可运行状态,但运行时间短,等待请求过程时处于阻塞状态。如交互式程序。

    处理器消耗型进程:时间大都用在执行代码上,除非被抢占否则一直不停的运行。

    调度策略要在:进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)之间寻找平衡。

    Linux为了保证交互式应用,所以对进程的相应做了优化,更倾向于优先调度I/O消耗型进程。

    进程优先级

    调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。优先级高的进程先运行,低的后运行,相同优先级的进程按轮转方式进行调度。

    Linux根据以上思想实现了一种基于动态优先级的调度方法。一开始,该方法先设置基本的优先级,然而它允许调度程度根据需要来加、减优先级。例如,如果一个进程在I/O等待上耗费的时间多于其运行时间,那么该进程明显属于I/O消耗型,它的优先级会被动态提高。相反,处理器消耗型进程的优先级会被动态降低。

    Linux内核提供两组独立的优先级范围。第一种是nice值,范围从-20到+19,默认值是0。nice值越大优先级越低。第二种是实时优先级,其值可配置,范围从0到99,任何实时进程的优先级都高于普通的进程。

    时间片

    时间片是一个数值,它表明进程在被抢占前所能持续运行的时间,I/O消耗型不需要长的时间片,而处理器消耗型的进程则希望越长越好。时间片的大小设置并不简单,设大了,系统响应变慢(调度周期长);设小了,进程频繁切换带来的处理器消耗。

    Linux调度程序提高交互程序的优先级,让它们运行得更频繁。于是,调度程序提供了比较长的默认时间片给交互程序。此外,Linux调度程序还能根据进程的优先级动态调整分配给它的时间片。从而保证优先级高的进程,假定也是重要性高的进程,执行的频率高,执行时间长。通过实现这样一种动态调整优先级和时间片长度的机制,Linux调度性性能不但非常稳定而且也很强健。

    注意,进程并不是一定非要一次就用完它所有的时间片,例如一个拥有100毫秒时间片的进程,可以通过重复调度,分5次每次20毫秒用完这些时间片。

    当一个进程的时间耗尽时,就认为到期了。没有时间片的进程不会再投入运行,除非等到其他所有的进程都耗尽了他们的时间片。那个时候,所有进程的时间片会被重新计算。

    进程抢占

    Linux是抢占式的。当一个进程进入TASK_RUNNING状态,内核会检查它的优先级是否高于当前正在执行的进程。如果是这样,调度程序会被唤醒,抢占当前正在运行的进程并运行新的可运行进程。此外,当一个进程的时间片变为0时,它会被抢占,调度程序被唤醒以选择一个新的进程。

     

    调度算法

    可执行队列

    调度程序中最基本的数据结构式运行队列(runqueue)。可执行队列是给定处理器上的可执行进程的链表,每个处理器一个。每个可投入运行的进程都唯一的归属于一个可执行队列。此外,可执行队列中还包含每个处理器的调度信息。所以,可执行队列也是每个处理器最重要的数据结构。

    为了避免死锁,要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁:按照可执行队列地址从低向高的顺序。

    优先级数组

    每个运行队列都有两个优先级数组,一个活跃的和一个过期的。优先级数组是一种能够提供O(1)级算法复杂度的数据结构。优先级数组使可运行处理器的每一种优先级都包含一个相应的队列,而这些队列包含对应优先级上的可执行进程链表。优先级数组还拥有一个优先级位图,当需要查找当前系统内拥有最高优先级的可执行进程时,它可以帮助提高效率。

    重新计算时间片

    许多操作系统在所有进程的时间片都用完时,都采用一种显示的方法来计算时间片。典型的实现是循环访问每个进程,这样可能会耗费相当长的时间,最坏情况为O(N);重算时必须考锁的形式来保护任务队列和每个进程描述符,这样做会加剧对锁的争用;重新计算时间的实际不确定。

    活跃数组内的可执行队列上的进程都还有时间片剩余,而过期数组内的都耗尽了时间片。当一个进程的时间片耗尽时,它会被移至过期数组,但在此之前,时间片已经给它重新计算好。重新计算时间片变得非常简单,只要在活跃和过期数组之间来回切换,这是O(1)级调度程序的核心。

    schedule()

    选定下一个进程并切换到它去执行是通过schedule()函数实现的。当内核代码想要休眠时,会直接调用该函数,另外,如果有哪个进程将被抢占,那么该函数也会被唤起执行。schedule()函数独立于每个处理器运行。

    首先要在活动优先级数组中找到第一个被设置的位,该位对于这优先级最高的可执行进程。然后,调度程序选择这个级别链表里的有一个进程。这就是系统中优先级最高的可执行程序。如果被选中的进程不是当前进程,就进行上下文切换。

    计算优先级和时间片

    nice值之所以起名为静态优先级,是因为它从一开始由用户指定后,就不能改变。动态优先级通过一个关于静态优先级和进程交互性的函数关系计算而来。effective_prio()函数可以返回一个进程的动态优先级。这个函数以nice值为基数,再加上-5到+5之间的进程交互性的奖励或罚分。

    怎么通过一些推断来获取准确反映进程到底是I/O消耗型的还是处理器消耗型的。最明显的标准莫过于进程休眠的时间长短了。如果一个进程的大部分时间都在休眠,那么它就是I/O消耗型的。如果一个进程执行的时间比休眠的时间长,那它就是处理器消耗型的。

    另一方面,重新计算时间片相对简单了。它只要以静态优先级为基础就可以了。在一个进程创建的时候,新建的子进程和父进程均分父进程剩余的进程时间片。这样的分配很公平并且防止用户通过不断创建新进程来不停地获取时间片。task_timeslice()函数为给定任务返回一个新的时间片。时间片的计算只需要把优先级按比例缩放,使其符合时间片的数值范围要求就可以了。进程的静态优先级越高,它每次执行得到的时间片就越长。

    调度程序还提供了另外一种机制以支持交互进程:如果一个进程的交互性非常强,那么当它时间片用完后,它会被放置到活动数组而不是过期数组中。

    睡眠与唤醒

    休眠(被阻塞)的进程处于一个特殊的不可执行状态。进程把它自己标记成休眠状态,把自己从可执行队列移出,放入等待队列,然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反:进程被设置为可执行状态,然后再从等待队列中移到可执行队列。

    休眠有两种相关的进程状态:TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用wake_queue_head_t来代表等待队列。等待队列可以通过DECLARE_WAITQUEUE()静态创建,也可以由init_waitqueue_head()动态创建。唤醒操作通过函数wake_up()进行,它会唤醒指定的等待队列上的所有进程。

    负载平衡

    Linux的调度程序为堆成多处理系统的每个处理器准备了单独的可执行队列和锁。为了使各个可执行队列上的负载平衡,提供了负载平衡程序。如果它发现了不平衡,就会把相抵繁忙的队列中的进程抽到当前的可自行队列中来。

    负载平衡程序有kernel/sched.c中的函数load_balance()来实现。它有两种调用方法。在schedule()执行的时候,只要当前的可执行队列为空,它就会被调用。此外,它还会被定时器调用:系统空闲时每隔1毫秒调用一次或者在其他情况下每隔200毫秒调用一次。负载平衡程序调用时需要锁住当前处理器的可执行队列并且屏蔽中断,以避免可执行队列被并发地访问。

    抢占和上下文切换

    上下文切换,也就是从一个可执行进程切换到另一个可执行进程。进程切换schedule函数调用context_switch()函数完成以下工作:

    1.调用定义在<asm/mmu_context.h>中的switch_mm(),该函数负责把虚拟内存从上一个进程映射切换到新进程中。

    2.调用定义在<asm/system.h>中的switch_to(),该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息。

    前面看到schedule函数调用有很多种情况,完全依靠用户来调用不能达到很好的效果。内核需要判断什么时候调用schedule,内核提供了一个need_resched标志来表明是否需要重新执行一次调度:

    1当某个进程耗尽它的时间片时,scheduler_tick()就会设置这个标志;

    2当一个优先级高的进程进入可执行状态的时候,try_to_wake_up()也会设置这个标志。

    每个进程都包含一个need_resched标志,这是因为访问进程描述符内的数值要比访问一个全局变量快

    用户抢占

    内核即将返回用户空间时候,如果need_resched标志被设置,会导致schedule函数被调用,此时发生用户抢占。

    用户抢占在以下情况时产生:

    1.从系统调返回用户空间。

    2.从中断处理程序返回用户空间。

    内核抢占

    只要重新调度是安全的,那么内核就可以在任何时间抢占正在执行的任务。

    什么时候重新调度才是安全的呢?只要没有持有锁,内核就可以进行抢占。

    锁是非抢占区域的标志。由于内核是支持SMP的,所以,如果没有持有锁,那么正在执行的代码就是可重新导入的,也就是可以抢占的。

    内核抢占会发生在:

    1.当从中断处理程序正在执行,且返回内核空间之前。

    2.当内核代码再一次具有可抢占性的时候。

    3.如果内核中的任务显式的调用schedule()。

    4.如果内核中的任务阻塞(这同样也会导致调用schedule())。



    from: http://www.linuxidc.com/Linux/2014-08/105366p3.htm

    展开全文
  • 文件系统模拟.ppt 进程管理与调度的模拟.ppt
  • 实验报告——Nachos 进程管理与调度

    千次阅读 2018-07-05 10:16:52
    1. 实验目的 (1) 掌握进程管理与同步:实现fork、exec、join 系统调用。 (2) 掌握进程调度:实现优先级调度。 2. 实验内容 运用理论课上学习的 fork、exec、waitpid / join 等系统调用的工作原理,在 Nachos...


    1.      实验目的

    (1) 掌握进程管理与同步:实现fork、exec、join 系统调用。

    (2) 掌握进程调度:实现优先级调度。

     

    2.      实验内容   运用理论课上学习的 fork、exec、waitpid / join 等系统调用的工作原理,在 Nachos 上实现进程的管理、同步与调度。主要包含以下几点: 1. 实现 fork、exec、join系统调用. 2. 实现进程优先级调度. 3. 编写一个简单的 Nachos shell. 

     

    3.      具体实现

    (1) part1——三种系统调用的实现

    i.     fork 的实现 function:创建一个子进程

    fork 在 exception.cc 的中断中的操作实际上就是调用了 SysFork(),然后写回返回值,更新 pc,这里略去代码,直接通过注释来讲解 SysFork()的关键代码。



    这里调用了 t->fork(),这个函数定义如下:

    void Thread::Fork(VoidFunctionPtr func, void *arg)

    看其注释:


     所以我们这里分配栈空间,直接调用了 forked(),如下

    void forked(int arg)

     {

        {

         kernel->currentThread->RestoreUserState(); //寄存器状态恢复

         kernel->currentThread->space->RestoreState(); //进程空间恢复

         kernel->machine->WriteRegister(2,0); //写返回值

         kernel->machine->PCplusPlus(); //PC 指向下一条指令

         kernel->machine->Run(); //执行用户空间的代码

         }

     }

              此外,为了使每个被创建的进程有不同的进程 ID,我在 thread.cc 增加了静态变量 idinit        在构造函数里添加代码:

    idinit++;

        tid = idinit;

     

    ii. Exec的实现function:载入并执行可执行程序 exec 的流程实际比较简单,通过注释讲解:


    助教提示了执行的部分到 main.cc里学习,我实际上是看到了一个例子,部分代码如下:

    if (space->Load(userProgName)) {

     // load the program into the space

     space->Execute(); // run the program

    ASSERTNOTREACHED(); // Execute never returns }


     可以看到是执行了 space->Execute();然后我将此借用到了自己代码当中。

     

     iii.      Join 的实现

    function:令父进程等待子进程执行结束

    join 和上面二者不同,基本功能实在 thread.cc 中实现的:

    voidThread::join(int tid)

        Thread *t;

        t=kernel->getThreadByID(tid);                          //获取子进程     if(t)

        {

            Semaphore *sem=newSemaphore("debug",0);             //新信号量         kernel->currentThread->joinSemMap_insert(tid,sem);      //插入joinSemMap

            sem->P()                                            //等待信号量       

    kernel->currentThread->joinSemMap_remove(tid);      //移除信号量     }

    }

    这里有两个操作比较关键:一是对joinSemMap 的操作,这个是通过数据类型map<int,Semaphore>存放线程 ID 和与之对应的信号量信号量,Join 必须通过管理这个 map,才能实现对子进程的信号量的管理。二是 P(),这个函数,实际上主要功能是阻塞当前进程,直到获得信号量。

     


    2 part2——进程优先级调度和 shell 的实现

     

     i.与调度相关的代码理解

     本实验中通过对 Scheduler类里的函数 FindNextToRun()进行修改来实现优先级调度的方

    法,这个函数的基本功能就是调整优先级,找到下一要运行的进程,并修改相关的进程状态。其具体实现后文结合代码详细介绍。

     我们可以发现在 thread.cc中有这样一个函数 Yield(),私以为这个函数相当重要,所以着重讲一下,可以看到,在这个函数中调用了上面说的 FindNextToRun()去找下一个要运行的进程,然后寻找成功,就会对当前进程执行 ReadyToRun(),即把当前进程添加到准备队列中,并且对

    nextThread 执行 run(),这个函数里保留了当前进程的上下文,然后 nextThread 的状态被置为 running,读取其上下文开始执行,此不做具体分析。


    至于调度的时机,显现要找对 Yield()的调用,这个我们在 interrupt.cc中可以找到。

    Interrupt::OneTick()

    然后看相关注释可以得知,OneTick()执行的时机有两种情况:1.中断被 re-enabled 时  2.每当一条用户指令被执行,所以这也就是调度的时机。

     

    ii.优先级调度的实现

     

     优先级调度是一种允许抢占的进程调度方式,每个进程有一个优先级,通过优先级判断谁先执行,为了避免死锁和饿死,这个优先级是动态变化的,其基本逻辑是,当前进程会随着执行时间变低,而等待队列的进程优先级别会不断增加,这样就确保每个进程都会被执行到。

     据此,本实验采用的优先级调整公式为:

             #调整当前进程优先级计算公式——priority= priority - (当前系统时间- lastSwitchTick ) /100      #调整所有就绪进程的优先级计算公式—— priority =priority + AdaptPace

                 下面通过注释的方式去分析优先级调度的代码,理解优先级调度算法的流程:

    Thread *Scheduler::FindNextToRun()

    {

        。。。。。。

        if (readyList->IsEmpty())//如果没有就绪进程,显然返回NULL

        {

            returnNULL;

        }     else {

            //更新当前线程的优先级

            Thread * t;

            t=kernel->currentThread;

            t->priority-=(kernel->stats->totalTicks-lastSwitchTick)/100;         t->setPriority(t->priority);//依照计算好的优先级进行设置

            //刷新所有就绪线程的优先级

            flushPriority();//下面会贴出         Print(); //打印当前进程状态

            // 计算最近调度与现在的间隔

            inttime=kernel->stats->totalTicks-lastSwitchTick;

            // 间隔太小,返回 NULL (避免过分频繁地调度)

            if(time<MinSwitchPace)              returnNULL;

            // 就绪队列为空,返回 NULL (没有就绪进程可以调度)

            if(readyList->IsEmpty())              returnNULL;

            // 找到优先级最高的就绪态进程t

            Thread *t1=readyList->Front();

            if(threadCompareByPriority(t,t1)==1)//把当前进程和就绪队列的第//一个进程进行比较,决定是否切 //

            {

                lastSwitchTick = kernel->stats->totalTicks;

            }//因为将要进行一次进程切换,所以上一次切换时间要用本次切换时间代替

            else

                returnNULL;

     

            return readyList->RemoveFront();//把就绪就列里的第一个进程移除

                                            //并且返回这个进程,即此为下一个

                                            //要调度的进程

           }}


      这里是刷新就绪队列进程优先级的代码,原理和公式上面已经讲过,没太多可分析的,作为关键代码贴出:

    iii.shell 的简单实现

    shell 的逻辑比较简单,首先是从控制台接受指令,通过字符串处理分解命令,得到一个序列,对于这个命令序列,依次创建进行子进程,装载相应的程序代码,这里父进程要等待所有创建的子进程完成之后再继续执行。很显然,只要对子进程调用Exec(),对父进程调用 Join()即可实现相应功能,下面是关键代码,可以看到,十分简单。

    iv.测试运行结果

     

      按照上面代码,这里 2进程最先创建,但是最后完成输出,而不是第一个完成,从这里其实就可以看到子进程不是依次执行的,而是有一个调度在里面,至于2 进程最后完成,这是由进程本身的耗时较长导致的(与add 等相比)。  

                      

    可以看到,刚开始只有 main 进程,然后创建子进程,执行 2,后来又变成 3 个进程,这里没有显示,第三个进程装载了 add 并执行,对应 for 循环里子进程被依次创建。然后我们观察进程的优先级pri,就绪队列里的进程,其优先级以2 的幅度增加,而执行中的进行优先级在不断降低,直到就绪队列优先级最高的进程比当前进程高,进程切换就发生了。

     

     v.part2 中遇到的问题

     1.刚开始没有仔细思考完成了 shell 的编写,大致如下:

     这样的 shell 是有问题的,可以看到,父进程 main创建了第一个子进程后,就执行 Join(),这样实际上要等第一个进程完成以后才能创建第二个子进程,如此优先级调度完全没有意义了。所以就修改成了上述的代码。

     

    2.关于检查的时候一个问题

    问题大致:查看进程切换,为什么执行到中间,main进程消失不见了?

    这个问题我之前没有注意到,所以一时间就没有回答上来,而且我注意力在“中间”这个词,理解为还在第一个 for 循环中,没有意识到这个时候进程创建已经完成了,所以回答得很不好。

    现在想来实际上比较简单,是因为子进程的创建已经完成了,父进程就执行 Join(),这和时候父进程 main 会阻塞自己,把自己从就绪队列中移出去。

    回去之后我又仔细的看了代码,可以发现在join()里调用了 p(),转到 synch.cc 中 p()的定义里,发现

    currentThread->Sleep(FALSE);

    然后在 sleep()里有:

    status = BLOCKED;

    这样就很清楚了。只怪自己实验时不够细致,没有意识到考虑到这个问题,然后一问就蒙圈了。

     

     

     


    展开全文
  • /* stacked block device info */ struct bio_list *bio_list;
  • 3.1.1 CPU 的构成基本工作方式 中央处理器(Central Processing Unit,CPU)是一台计算机的运算核心和控制核心。 处理器由运算器、控制器、一系列的寄存器以及高速缓存构成。 1)运算器 实现指令中的算术运算和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 223,630
精华内容 89,452
关键字:

进程管理与调度