中文模板

Size: px

Start display at page:

Download "中文模板"

晁郭
5 years ago
Views:

1 操作系统课程作业源码阅读报告 1 源码阅读报告 1. Linux 内核中进程管理模块的整体结构 Linux 内核的进程管理模块包括进程的数据结构表示进程的创建与终止进程调度进程间通信 CPU 调度进程同步死锁处理等整个进程管理模块以结构体 task_struct 为核心, 其他的操作都针对这个结构体及其各个成员进行操作比如, 创建一个进程就是新建一个 task_struct 结构体, 并将父子进程的结构体通过成员及指针连接起来终止一个进程实际是更改一个进程的状态并将其删除进程间通信是由结构体中 pipe 成员实现的进程调度需要使用与进程调度策略有关的成员 policy 和 sched_class 来决定使用何种方式进行调度在调度时, 还要更改进程状态, 将进程从就绪队列中移入移出本篇阅读报告将分析进程在 Linux 内核中的数据结构表示, 随后依次讨论进程的创建终止调度等操作在 Linux 内核中的具体实现 2. Linux 内核中进程的数据结构表示进程和线程在 Linux 内核中被视为任务 (task) 统一管理其数据结构 task_struct 定义于 \include\linux\sched.h 内由于这个结构体的定义大概有 500 行长, 针对不同的情况提供了不同的编译器指令以满足所有的要求, 故在此仅列举一些重要的成员 (1) state (volatile long state) 和 exit_state(int exit_state) 它提供了进程当前所处的状态一些状态值如下包括了正在运行已经终止处于中断状态处于僵尸进程状态等 #define TASK_RUNNING 0 // 正在运行, 或就绪 #define TASK_INTERRUPTIBLE 1 // 阻塞状态, 等待唤醒 #define TASK_UNINTERRUPTIBLE 2 // 类似于阻塞状态, 但只有资源可用才 // 会被唤醒 #define TASK_STOPPED 4 // 进程被停止执行 #define TASK_TRACED 8 // 进程被其他进程跟踪 // 下面三个状态既可以出现在 state 里, 也可以出现在 exit_state 里 #define EXIT_DEAD 16 // 进程终止的最终状态 - #define EXIT_ZOMBIE 32 // 僵尸进程状态 #define EXIT_TRACE (EXIT_ZOMBIE EXIT_DEAD) #define TASK_DEAD 64 // 以下是 Linux 实现的另一种睡眠状态的状态值 #define TASK_WAKEKILL 128 #define TASK_WAKING 256 #define TASK_PARKED 512 #define TASK_NOLOAD 1024 #define TASK_STATE_MAX 2048 (2) tgid) pid (pid_t pid) 和 tgid (pid_t

2 操作系统课程作业源码阅读报告 2 这两个成员的区别如下 :pid 是用于区分每一个进程和线程的任务编号然而, 某一个父进程下的所有线程应该具有相同的编号所以 tgid 里面存放的就是这个线程组里第一个线程的编号同时, 可以发现 getpid() 系统调用返回的是 tgid 而不是 pid 的值这个系统调用的操作涉及多层函数 ( 五层以上 ) 嵌套, 十分复杂, 故在此不讨论这两个成员的数据类型 pid_t 定义在 \include\linux\ types.h 中其定义为 : kernel_pid_t pid_t; 而 kernel_pid_t 的定义在 \include\uapi\asm-generic\posix_types.h 中其定义为 : typedef int kernel_pid_t; 也就是说,pid 的数据类型是 int (3) stack (void *stack) 它指向内核为该进程分配的栈 (4) flags (unsigned int flags) 它表示进程的状态值, 但不是运行状态操作系统内核可以通过查看这个成员来了解当前进程的更加具体的信息 (5) 一些表示进程间亲属关系的成员 : (a) real_parent (struct task_struct rcu *real_parent) 它是创建该进程的进程,parent (struct task_struct rcu * parent) 是该进程的父进程一般来说 real_parent 与 parent 相同, 但是如果父进程意外终止, 子进程被接管, 那么这两个变量将不同 real_parent 将指向 PID 为 1 的进程 (b) children (struct list_head children) 它是该进程的子进程列表 (c) sibling (struct list_head sibling) 它是该进程的兄弟进程列表 ( 即这些进程拥有相同的父进程 ) (6) ptrace (int ptrace) 和 ptraced (struct list_head ptraced) ptrace 是 Linux 提供的一个接口, 父进程可以通过这个接口来控制子进程的运行, 一般用于实现断点调试前者是该进程是否被跟踪的标志位如果为 0, 表示不需要被跟踪后者是该进程可以跟踪并控制的进程列表 (7) 一些与优先级有关的成员 : (a) 成员 prio, static_prio, 和 normal_prio (int prio, static_prio, normal_prio;) 这三个成员分别表示动态优先级静态优先级和在当前调度策略之下的优先级 (b) int rt_priority (unsigned int rt_priority) 这个成员中存储的是实时优先级 (8) 一些与进程调度有关的成员 : (a) policy (unsigned int policy) 表示当前进程使用哪一种调度策略来运行取值有以下几种 : #define SCHED_NORMAL 0 //CFS #define SCHED_FIFO 1 // 先到先服务调度方式 #define SCHED_RR 2 //ROUND-ROBIN, 时间片 + 优先级调度 #define SCHED_BATCH 3 // 带有动态优先级的 CFS 调度 /* SCHED_ISO: reserved but not implemented yet */ #define SCHED_IDLE 5 // 优先级最低, 只利用空闲资源

3 操作系统课程作业源码阅读报告 3 #define SCHED_DEADLINE 6 // 采用 EDF 调度方法的实时调度我们可以发现,Linux 系统支持多种调度策略, 包括普通调度 ( 利用 CFS) 实时调度 (FIFO) 轮转法调度(RR) 实时调度(DEADLINE) 等这几种调度策略将在后面介绍 (b) sched-class (const struct sched_class *sched_class) 是进程所处的调度类在这个成员里, 我们可以规定这个进程是静态进程优先级最高的可以打断所有进程的进程或者是实时进程一般进程等每一种调度策略都有一种调度器类与之对应 (c) spus_allowed (cpumask_t cpus_allowed) 规定了这个进程可以使用哪一个处理器来运行 (9) 一些表示时间的成员 : (a) 成员 utime 和 stime (cputime_t utime, stime) 分别是进程执行用户代码的时间和执行系统代码的时间 (b) 成员 start_time (struct timespec start_time) 是进程的创建时间 (10) mm 和 active_mm (struct mm_struct *mm, *active_mm) 它们分别指向进程所拥有的内存地址以及进程运行时的内存一般这两个值相等 (11) comm (char comm[task_]comm_len]) 它是进程所对应的程序名 (12) files (struct files_struct *files) 它表示进程当前打开的文件 (13) 此外, 还有进程中断管道 (struct pipe_inode_info *splice_pipe) 进程运行的当前目录 (struct fs_struct *fs) 各种信号等成员 3. Linux 内核中进程的创建 (fork) 的实现方式 Linux 4.3 内核提供了多种 fork 方式 :fork,vfork 和 clone 它们定义在\kernel\fork.c 下我们观察这三个系统调用的实现源码 (clone 源码过长, 不在此粘贴 ): #ifdef ARCH_WANT_SYS_FORK SYSCALL_DEFINE0(fork) { #ifdef CONFIG_MMU return _do_fork(sigchld, 0, 0, NULL, NULL, 0); #else /* can not support in nommu mode */ return -EINVAL; #endif #endif #ifdef ARCH_WANT_SYS_VFORK SYSCALL_DEFINE0(vfork) { return _do_fork(clone_vfork CLONE_VM SIGCHLD,0,0,NULL,NULL,0); #endif

4 操作系统课程作业源码阅读报告 4 可以发现, 它们都调用了 _do_fork 函数, 只是参数不同我们先来看一下 _do_fork 函数的执行流程 nr; _do_fork 的原型 : long _do_fork(unsigned long clone_flags,unsigned long stack_start, unsigned long stack_size,int user *parent_tidptr, int user *child_tidptr,unsigned long tls) clone_flags: 内存复制的参数该标志位有四个字节构成, 一些常见参数如下 : SIGCHILD: 决定子进程结束时发送给父进程的信号 CLONE_VFORK: 这次 _do_fork 操作是 vfork 操作 CLONE_VM: 父子进程共享内存可以看出,vfork 具有的功能的功能有 : 子进程在结束后父进程会收到信号 ; 父子进程共享内存另外的功能要考察 CLONE_VFORK 这个参数的含义 stack_start: 子进程用户态堆栈地址如果没有特殊需求, 一般设为 0. stack_size: 子进程的栈大小一般来说, 这个参数没有必要, 通常为 0 parent_tidptr: 父进程的 pid 地址 child_tidptr: 子进程的 pid 地址 tls: 线程局部存储的参数线程可以通过这个来申请属于自己的内存空间, 而不进行共享 _do_fork 的执行过程如下 : (1) 先执行函数 copy_process 来复制一个进程这个函数实现的操作有 : 初始化进程的各个参数 ( 比如运行时间等 ), 复制所有进程信息 ( 比如文件系统内存等 ), 然后初始化子进程栈空间, 分配新的 PID p=copy_process(clone_flags,stack_start,stack_size,child_tidptr, NULL, trace, tls); (2) 检查复制操作是否出错如果复制出错, 返回错误代码如果不出错, 就使用 get_task_pid() 函数获得其 pid( 刚才讲过, 这里获得的其实是 tgid), 并把它作为返回值返回 if (!IS_ERR(p)) { struct completion vfork; struct pid *pid; trace_sched_process_fork(current, p);// 使用 ptrace 跟踪子进程 pid = get_task_pid(p, PIDTYPE_PID); // 得到子进程的 pid nr = pid_vnr(pid); //( 以下省略 ) else nr = PTR_ERR(p); return

5 操作系统课程作业源码阅读报告 5 (3) 根据 clone_flags 参数选择是否共享内存等操作如果是 vfork, 就初始化 vfork 操作的参数, 比如 vfork_done 等 (4) 接下来就是调用 wake_up_new_task() 函数了这会使子进程加入调度器等待 CPU 调度如果是 vfork 的话, 父进程要被加入等待队列中, 等待子进程完成这一部分代码如下 : wake_up_new_task(p); // 将子进程加入调度器中 /* forking complete and child started to run, tell ptracer */ if (unlikely(trace)) ptrace_event_pid(trace, pid); // 用 ptrace 给父进程提供信号 if (clone_flags & CLONE_VFORK) { // 如果是 vfork, 父进程等待 if (!wait_for_vfork_done(p, &vfork)) ptrace_event_pid(ptrace_event_vfork_done, pid); // 如果等待结束, 利用 ptrace 向父进程发送 vfork 完毕的信号由上述内容发现,vfork 与 fork 的区别在于 :vfork 创建的子进程与父进程共享内存, 而且先于父进程运行而 clone 系统调用则更类似于直接调用 _do_fork 函数,_do_fork 函数中的参数由用户自行指定最后我们来比较一下 Linux 系统与 NachOS 系统进程创建过程的区别 Linux 系统功能繁多, 在 fork 的时候需要向父进程按照执行流程发出追踪信号, 使调试顺利 ; 提供了多种接口, 可以自定义父子进程之间数据的共享方式而 NachOS 则类似于一个最小系统, 只提供了最基本的操作在 NachOS 的 fork 操作中用到的复制用户名称空间复制寄存器值等操作在 Linux 中也有, 只不过被统一打包在了 copy_process 函数之内我们可以看一下 copy_process 中的一些过程 : *childregs = *current_pt_regs(); // 子进程复制得到当前寄存器信息 childregs->ax = 0; // 子进程的 fork 返回值设为 0 if (sp) childregs->sp = sp; p->thread.ip = (unsigned long) ret_from_fork; // 设置子进程的 PC 这与我们在 NachOS 中的实现何其相似! 4. Linux 内核中进程终止的实现方式在进程终止时, 操作系统内核里的 do_exit 函数会被执行, 使进程结束 SYSCALL_DEFINE1(exit, int, error_code) { do_exit((error_code&0xff)<<8); do_exit 的执行流程如下 : 先检查要结束的进程是否能被结束 if (unlikely(in_interrupt())) // 不能结束中断服务进程 panic("aiee, killing interrupt handler!"); if (unlikely(!tsk->pid)) // 不能结束 PID 为 0 的进程

6 操作系统课程作业源码阅读报告 6 panic("attempted to kill the idle task!"); 如果要结束的是中断服务进程, 就会报错如果要结束 PID 为 0 的进程 (IDLE), 也会报错检查完这些情况之后就可以开始真正的终止过程了操作系统会依次调用 exit_mm, exit_sem, exit_shm, exit_files, exit_fs, exit_task_namespaces, exit_task_work, exit_thread 函数来从内核里清除该进程的内存打开文件列表等一切信息, 最后还会把该进程的状态置为 TASK_DEAD 并进行一次进程调度 /* causes final put_task_struct in finish_task_switch(). */ tsk->state = TASK_DEAD; // 设置进程状态为 DEAD tsk->flags = PF_NOFREEZE; /* tell freezer to ignore us */ schedule(); // 进行一次调度, 之后会介绍这个函数至此, 进程就从操作系统上彻底的消失了 5. Linux 内核中进程调度的实现方式 Linux 系统有两种方法来激活进程调度 : 进程直接请求调度和操作系统周期性地检查是否需要调度具体时机有 : 直接调用 schedule() 时从内核态返回用户态时从中断返回用户态时发生抢占时这两种调度方式分别由主调度器和周期性调度器实现在调度时, 系统会从就绪列表中依次选择可以运行的实时进程普通进程 idle 进程来运行 6. Linux 主调度器的实现那么主调度器是如何实现的呢? 主调度器实际就是 schedule 函数, 它负责完成进程切换的操作这个函数定义在 kernel/sched/core.c 中 asmlinkage visible void sched schedule(void){ struct task_struct *tsk = current; sched_submit_work(tsk); // 检查死锁 do { preempt_disable(); // 关闭内核抢占 schedule(); // 调度 sched_preempt_enable_no_resched(); // 开启抢占 while (need_resched()); // 如果进程需要重新进行调度 // 就再调度一次 preempt_disable 函数的作用是 : 关闭内核抢占在 Linux 系统中, 在内核态下也可能发生进程的抢占如果在调度的时候发生了内核抢占, 那么在调度到一半时可能会发生终止, 出现异常因此, 调度之前一定要把内核抢占关闭真正的调度工作是 schedule 函数完成的 static void sched schedule(void){ struct task_struct *prev, *next; unsigned long *switch_count; *rq; struct rq

7 操作系统课程作业源码阅读报告 7 int cpu; // 获取该 CPU 上的就绪队列 rq, 并且将 prev 赋为正在运行的进程 cpu = smp_processor_id(); rq = cpu_rq(cpu); rcu_note_context_switch(); prev = rq->curr; // 省略一部分代码 // 使用互斥锁锁住就绪队列, 防止调度过程中就绪队列发生变化导致混乱 smp_mb before_spinlock(); raw_spin_lock_irq(&rq->lock); lockdep_pin_lock(&rq->lock); rq->clock_skip_update <<= 1; /* promote REQ to ACT */ switch_count = &prev->nivcsw; // 记录切换次数 if (prev->state &&!(preempt_count() & PREEMPT_ACTIVE)){ // 如果当前进程不能被切换, 就让它重新启动 if (unlikely(signal_pending_state(prev->state, prev))) prev->state = TASK_RUNNING; else {// 否则就将当前进程从运行队列中删除 deactivate_task(rq, prev, DEQUEUE_SLEEP); // 省略一部分代码 next = pick_next_task(rq, prev); // 从就绪队列里挑选下一个进程 clear_tsk_need_resched(prev);// 清除 prev 进程需要调度的标志位 clear_preempt_need_resched();// 清除抢占标志位 rq->clock_skip_update = 0; if (likely(prev!= next)) { rq->nr_switches++; rq->curr = next; ++*switch_count; // 如果下一个进程与当前进程不同, 就进行上下文切换, 否则不切换 rq = context_switch(rq, prev, next); /*unlocks the rq */ // 其余代码省略可以看到, schedule 函数主要完成的工作是 : 判断当前进程是否需要切换, 然后从就绪队列中挑选进程, 完成上下文切换的操作而挑选进程的操作是由 pick_next_task 函数实现的 : 这个函数遍历所有的调度器类, 选择优先级最高的进程开始执行上下文切换是 context_switch 函数实现的这个函数的作用是把当前进程挂起, 然后将内存和寄存器切换到下一个进程的状态上下文切换的主要操作由函数 switch_mm 和宏 switch_to 完成 : switch_mm(oldmm, mm, next);// 切换内存 switch_to(prev, next, prev);// 切换堆栈与寄存器至此,Linux 主调度器的大致框架介绍完毕接下来介绍周期性调度器的实现

8 操作系统课程作业源码阅读报告 8 7. Linux 周期性调度器的实现周期性调度器实际是 scheduler_tick 函数它也定义在 kernel/sched/core.c 中因为 Linux 系统中共有三个调度器类, 因此周期性调度器实际做的工作就是从当前进程对应的调度器类中选取下一个进程执行其核心操作是进程切换 : curr->sched_class->task_tick(rq, curr, 0); task_tick 函数的具体实现取决于调度器类因此接下来介绍各个调度器类, 并介绍其周期性切换进程的方式 8. Linux 系统实时调度类 (rt_sched_class) 的核心源码与实现方式首先介绍实时调度在 Linux 系统中, 实时进程是具有很强的调度需要的进程, 它们的响应时间需要尽可能地短这一类进程的优先级处于中等位置, 低于 EDF 而高于 CFS 因此, 采用 RR(Round-Robin) 和 FIFO 来进行调度这个调度类定义在 kernel/sched/rt.c 下其进程切换函数 task_tick_rt 如下 : static void task_tick_rt(struct rq *rq,struct task_struct *p,int queued){ struct sched_rt_entity *rt_se = &p->rt; if (p->policy!= SCHED_RR)// 检测是否是 FIFO 如果是, 无需调度 return; if (--p->rt.time_slice) // 检测是否到了切换的时间片, 否则不切换 return; p->rt.time_slice = sched_rr_timeslice;// 重置时间片 // 把当前进程插入就绪队列中, 并把就绪队列的队首提出来 for_each_sched_rt_entity(rt_se) if (rt_se->run_list.prev!= rt_se->run_list.next) { requeue_task_rt(rq, p, 0); resched_curr(rq); return; 由于 FIFO 是先到先服务, 因此在每一个时间片到达时并不需要进行进程调度而 RR 则是在每一个时间片都要进行一次调度这跟我们一般理解的 FIFO 与 RR 调的度方式相同另外, 我们在 nachos 中也实现了一个 RR 调度这个函数与实验中的 FindNexttoRun 函数十分相似 9. Linux 系统最早截止时间优先调度类 (dl_sched_class) 的核心源码与实现方式这个调度类是为了实现最早截止时间优先算法而特意增设的调度类这种调度类下只有一种调度策略 :EDF Linux 较高版本中新增的调度策略这种调度方法具有很高的实时性, 主要用于对时间要求很高的任务这个调度类定义在 kernel/sched/deadline.c 下 static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued) { update_curr_dl(rq); // 更新当前进程的截止时间

9 操作系统课程作业源码阅读报告 9 /* Even when we have runtime, update_curr_dl() might have * resulted in us not being the leftmost task anymore. In that * case NEED_RESCHED will be set and schedule() will start a new hrtick for the next task. */ if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 && is_leftmost(p, &rq->dl)) start_hrtick_dl(rq, p); // 从队列中挑选截止时间最近的进程切换我们发现,EDF 算法其实就是从等待队列中挑选截止时间最近的进程进行调度 10. Linux 系统完全公平调度类 (fair_sched_class) 的核心源码与实现方式完全公平调度类实现了 Linux 最普遍的调度方式 : 完全公平调度它有两种调度策略 : 普通的 CFS 调度策略 (SCHED_NORMAL) 和采用分时策略的 CFS 调度 (SCHED_BATCH) 两种调度策略的唯一不同点在于第二种调度策略不能抢占, 因此适用于成批处理的工作它们使用的算法是 CFS 算法这个调度器类定义在 kernel/sched/fair.c 中 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued){ struct cfs_rq *cfs_rq; //cfs_rq 是就绪队列 struct sched_entity *se = &curr->se; for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); // 获取当前运行的进程所在的 CFS 就绪队列 entity_tick(cfs_rq, se, queued);// 完成周期性调度 if (static_branch_unlikely(&sched_numa_balancing)) task_tick_numa(rq, curr); 根据源码可以看到,Linux 系统实际上是调用 entity_tick 函数完成了调度而这个函数主要是调用 check_preempt_tick 函数来进行切换进程的决策这个函数源码如下 : check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long ideal_runtime, delta_exec; struct sched_entity *se; s64 delta; // 计算当前进程应该运行的时间 */ ideal_runtime = sched_slice(cfs_rq, curr); // 计算当前进程实际运行时间 delta_exec=curr->sum_exec_runtime-curr->prev_sum_exec _runtime; // 如果实际运行时间高于应该运行的时间, 就应该切换 if (delta_exec > ideal_runtime) { resched_curr(rq_of(cfs_rq));

10 操作系统课程作业源码阅读报告 10 clear_buddies(cfs_rq, curr); return; // 其余代码略可以看出,CFS 是基于运行时间进行进程切换的操作系统统计该程序实际运行时间, 然后与通过 nice 值计算得到的应该运行的时间进行对比如果某一进程运行时间超过了应该运行的时间, 就将其切换 11. Linux 系统空闲进程调度类 (idle_sched_class) 的实现方式最后我们简单介绍一下 IDLE 调度类 (idle_sched_class) 这个调度类只有一种调度策略 : idle 调度策略这种调度类下的进程优先级最低, 只有在系统 CPU 空闲时才会运行一般只有 idle 进程和一些数学计算程序 ( 比如计算梅森素数的程序 ) 才会属于这个调度类这个调度类定义在 kernel/sched/idle_task.c 中我们观察这个文件, 发现函数很少, 而且很多函数都是空的我把这种现象解释为 : 这种进程其实根本不需要调度既然这种进程的优先级是最低的, 那么这种进程运行的必要性其实也不高既然这种进程运行与否都无所谓, 那么调度也没有必要了这种进程唯一需要的调度过程就是当这个进程结束之后换下一个进程运行至此, 进程调度模块也介绍完毕了 12. 总结此次报告总结了 Linux 进程管理的主要数据结构, 还分析了 Linux 系统中进程创建终止调度的源码, 大致掌握了各个操作的实现流程通过本次 Linux 源码阅读, 本人对 Linux 操作系统的进程管理模块有了大概的认识, 观察到了很多功能的具体实现方法, 了解了一个巨大的开源项目的维护与发展过程

Kernel Kernel Kernel Kernel load estimator runqueue kernel/sched.

Kernel Kernel Kernel Kernel load estimator runqueue kernel/sched. Linux Kernel 2.6 20321131 Kernel 2.4...3 Kernel 2.4...3 Kernel 2.4...3 Kernel 2.6...3...3 1....3 2....4 3. load estimator...4 4....4 5....4...4 1....4 2. runqueue kernel/sched.c...4 3. task_struct(include/linux/sched.h)...6...9