操作系统实验一.doc

实验1. 进程调度算法1.1 实验目的：1. 掌握Linux2.6调度算法的原理与实现。2. 能够根据要求修改Linux2.6调度算法。3. 对Linux核心进行编译。4. 通过实验进一步熟悉操作系统的原理。1.2 实验学时2学时1.3 实验内容首先了解Linux系统的进程结构和调度原理，然后把Linux2.6的调度算法修改成为随机调度算法。最后对修改的调度算法进行编译，并使用新内核替换老内核。1.4 Linux调度分析PCB结构V2.6内核中，进程描述符task_struct(PCB)主要含有如下与调度有关的成员: policy：进程调度策略，有以下3种类型：SCHED_NORMAL 非实时进程。SCHED_FIFO 实时进程，采用先进先出的调度算法。SCHED_RR 实时进程，采用轮转法。 rt_priority：实时进程的优先级。MAX_RT_PRIO定义为100，故其rt_priority范围为099，且不参与优先级计算。 static_prio：非实时进程静态优先级。由nice值转换而来，nice值为-2019，公式static_prio=MAX_RT_PRIO+nice-20，故其范围为100139。 sleep_avg：进程平均等待时间。相当于进程等待时间与运行时间的差值，既反映该进程的交互程度，又表示进程需要运行的紧迫程度，该值越大，算出来的数据越小，进程的优先级就越高。 prio：进程动态优先级。在进程运行过程中动态计算，主要影响因素为sleep_avg。创建时子进程继承父进程的动态优先级、唤醒等待进程时对它进行优先级修正、时钟中断中重新计算进程优先级并进入相应队列、负载平衡/修改nice值/修改等待策略(setscheduler()都有可能改变进程动态优先级。 prio_array_t*array：进程优先级数组。以进程优先级为序号排列。 time_slice：进程时间片余额。进程默认时间片与static_prio有关，内核将100139优先级映射为800ms5ms的时间片区间。 load_weight：平衡负载用的权重。解决可运行队列出现的负载不均现象。 CONFIG_PREEMPT：内核可剥夺编译选项，当该开关开启时，v2.6内核将会在更多内核安全点上检测TIF_NEED_RESCHED位，从而让刚被唤醒的高优先级进程减少延迟而尽快获得CPU运行。运行队列Linux2.6的调度算法称为(1)算法，不论就绪进程与CPU的个数多少，调度程序的调度开销总是恒定的常数。每个CPU都有一个运行队列(runqueue),它是给定CPU上的可执行进程的链表，每个就绪进程都唯一归属于一个运行队列。此外，运行队列中还包含每个CPU的调度信息，运行队列的定义如下：struct runqueue spinlock_t lock;/*本CPU上的运行队列自旋锁*/ unsigned long nr_running; /*本CPU上活跃、过期队列就绪进程总数*/ unsigned long cpu_load; /*各处理器上的负载*/ unsigned long long nr_switches;/*本CPU上发生的上下文切换数*/ unsigned long long timestamp_last_tick; /*本就绪队列发生调度时间*/ unsigned long expired_timestamp; /*进程耗完时间片事件的时间*/ unsigned long nr_uninterruptible; /*本CPU上不可中断阻塞态的进程数*/ struct mm_struct *prev_mm; /*前面运行进程的active_mm指针*/ prio_array_t *active,*expired; /*指向活动、过期优先级数组的指针*/ prio_array_t arrays2; /*活跃、过期两类优先级数组*/ int best_expired_prio; /*过期队列中进程最高优先级(数值最小)*/ int active_balance; /*平衡CPU负载使用*/ int push_cpu; task_t *curr,*idle; /*该处理器当前运行和空进程*/ task_t*migration_thread; /*处理器上的迁移进程*/ struct list_head*migration_queue; /*处理器上的迁移进程队列*/ atomic_t *nr_iowait; /*本CPU上等待I/O的进程数*/ 内核为每个运行队列维持调度用的数据结构，称优先级数组arrays：一个是活跃的(active)、一个是过期的(expired)，每个成员内含140个双向链表，相同优先级的进程链接在同一个双向链表里，指针active和expired分别指向arrays的成员。进程调度时从指针active指向的arrays的成员里选择下个要运行的进程。当非实时进程的时间片用完后，就会被移到指针expired指向的arrays的成员的双向链表里。prio_array的定义如下： struct prio_array unsigned int nr_active; /*数组中的进程数*/ unsigned long bitmapBITMAP_SIZE; /*优先级位图*/ struct list_head queueMAX_PRIO; /*优先级队列*/ 在优先级数组中，有一个长度为MAX_PRIO(默认值为140)的数组，数组中的每一个元素是一个链表。链表中放入的是具有相同优先级的就绪态进程。优先级为n的进程将被放入queuen中。系统中定义的优先级为0139，0为最高优先级，139为最低优先级。Linux在进行调度时，将从活跃优先级队列中挑选一个优先级最高的进程执行。为了不扫描活跃优先级队列中的所有进程，优先级数组中提供了一个优先级位图，它能够帮助调度器在(1)时间内找到优先级最高的进程。位图中的每一位对应一个优先级链表，如果位图中该位为0，则说明链表为空；反之说明链表中有处于就绪态的进程。在优先级位图的定义中，BITMAP_SIZE的默认值为5，所以bitmap共含有5个长整型，在32位计算机上共有160位(其中20被放弃不用)。最后，nr_active指示该优先级数组内可执行的进程的个数。初始化时，位图都被设置为0，并且所有的运行队列都为空，当一个进程就绪时，将它放到合适的优先级队列，位图中相应位就被置1，这样，查找系统中最高优先级就变成了查找位图中被设置的第1个位。因为优先级个数是个定值，所以查找时间恒定，并不受系统到底有多少进程的影响，Linux对它支持的每一种体系结构都提供了对应的快速查找算法sched_find_first_bit()。 在运行队列中分别有活跃与过期优先级队列，这两个队列中放置的都是就绪态进程，它们的不同之处在于：时间片尚未用完的就绪态进程被放置在活跃优先级队列中，因此调度器只要在活跃优先级队列中取得的进程都是可运行、并且还有可用时间片的进程。当进程的时间片用完后，它会被放入过期优先级队列，并重新计算进程应该分得的时间片，当活跃优先级队列中的进程都执行完毕后，所有的就绪态进程都进入过期优先级队列，而在过期优先级队列中的进程都是计算完时间片的。调度器这时只需要将活跃队列与过期队列的指针交换，即原来的过期队列变成活跃队列，原来的活跃队列变成过期队列，重新在活跃队列上进行调度。通过以上算法，调度器能够在(1)时间完成进程调度，且对于SMP有良好的亲和性，达到了Linux2.6调度算法的设计目标。时间片时间片是进程一次最多可运行的时间长度。确定时间片的长度是比较困难的。如果时间片太长，进程切换速度太慢，系统的交互性就变得比较差；如果时间片太短，进程的频繁切换将花费系统较多的开销。在一般操作系统中，交互性较强的进程通常不需要较长的时间片，而交互性弱的进程希望能够得到较长的时间片(这样CPU能够有比较高的缓存命中率，可以提高系统性能)，但较长的时间片又会影响整个系统的交互性。在Linux2.6中，较好地解决了这个问题，根据进程优先级的不同，内核会给进程赋予不同的时间片长度；优先级高的时间片长，优先级低的时间片短。在Linux中，最短的时间片也是比较长的，这可以满足交互性弱的进程的要求。虽然采用的时间片长度较长，但是Linux并不会因此降低系统的交互性。在Linux中高优先级进程会剥夺低优先级进程的运行，同时交互性强的进程会自动提升优先级，因此交互性强的进程并不会因时间片长而受到影响。这样的时间片分配也保证高优先级进程能够有较多的机会而得到运行。当一个进程的时间片用完后，就要根据进程的动态优先级重新计算时间片。task_timeslice函数为给定进程返回一个新的时间片。时间片的计算只需要把优先级按比例缩放，使其符合时间片的数值范围要求即可。进程的优先级越高，它每次执行得到的时间片就越长。优先级最高的进程能获得的最大时间片长度(MAX_TIMESLICE)是800ms，而优先级最低的进程获得的最短时间片(MIN_TIMESLICE)是5ms。默认优先级(nice=0)的进程得到时间片长度为100ms。调度程序还提供另一种机制用于支持交互进程：如果一个进程的交互性非常强，那么当它的时间片用完后，它会被再放置到活动数组而不是过期数组中。重新计算时间片是通过活动数组与过期数组之间的切换来进行的，一般进程在用完它们的时间片后，都会被移至过期数组，当活动数组中没有剩余进程时，这两个数组就会被交换；活动数组变成过期数组，过期数组变成活动数组。这种操作提供了时间复杂度为(1)的时间片重新计算方法。但在这种交换发生之前，交互性很强的一个进程有可能已经处于过期数组中，当它需要交互时却无法执行，因此必须到数组交换发生为止才可执行。将交互式进程重新插入到活动数组可以避免这种问题。在时钟中断处理函数update_process_time()中会调用scheduler_tick()函数，它包含以下有关排队操作。void scheduler_tick(int user_ticks,int sys_ticks)int cpu=smp_processor_id(); /*当前CPU型号*/ task_t*p = current; /*当前进程task_struct*/ runqueue_t*rq=this_rq(); /*当前CPU运行队列*/ . spin_lock(&rq-lock); /*封锁当前运行队列*/ if(!-p-time_slice) dequeue_task(p,rq-active); /*当前进程出运行队列*/ set_tsk_need_resched(p); /*置need_resched标志*/ p-prio=effective_prio(p); /*计算优先级*/ p-time_slice=task_timeslice(p); /*优先级换算成时间片*/ if(!task_INTERACTIVE(p)EXPIRED_STARVING(rq) enqueue_task(p,rq-expired); if(p-static_prioexpired_prio) rq-best_expired_prio)=p-static_prio; /*修改过期队列最高优先级*/ else enqueue_task(task, rq-active); spin_unlock(&rq_lock); /*开放当前run queue*/ . 这段代码首先减小进程时间片的值，再看它是否为0。如果是0，说明进程的时间片已经用完，需要把它插入到一个数组中，所以该代码先通过TASK_INTERACTIVE()宏来查看这个进程是不是交互型进程，该宏主要基于进程的nice值来判定，nice值越小（优先级越高），越能说明该进程交互性越高。接着，EXPIRED_STARVING()宏负责检查过期数组内的进程是否处于饥饿状态，即是否已经有相对较长的时间没有发生数组切换。如果最近一直没有发生切换，那么再把当前的进程放置到活动数组会进一步拖延切换，过期数组内的进程会越来越饥饿。只要不发生这种情况，进程就会被重新放置在活动数组里。否则，进程会被放入过期数组里，这也是最普通的一种操作。调度程序在进程的创建、退出时也作了比较细致的考虑。在进程创建时，子进程被创建时并不分配自己的时间片，而是与父进程平分父进程的剩余时间片。也就是说，fork()结束后，两者时间片之和与原先父进程的时间片相等。这样防止进程通过不断创建子进程来窃取时间片。进程退出时，根据first_time_slice的值判断自己是否从未重新分配过时间片，如果是，则将自己的剩余时间片返还给父进程(保证不超过MAX_TIMESLICE)。这个动作使进程不会因创建短期子进程而受到惩罚。用户抢占内核即将返回用户空间时，如果TIF_NEED_RESCHED标志被设置，会导致调用schedule()，此时就会让刚被唤醒的高优先级进程尽快获得CPU，发生了用户抢占。这时内核知道自己是安全的，因为既然可以继续去执行当前进程，那么也可以选择一个新的进程运行。用户抢占发生在从系统调用返回用户空间时，以及从中断处理程序返回用户空间时。Linux 2.6完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时间抢占正在运行的进程。那么何时重新调度是安全的呢？只要没有持有锁，内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持SMP的，所以，如果没有持有锁，正在运行的代码是可重入的、也就是可以抢占的。为了支持内核抢占所作的修改是在每个进程的thread_info中引入preempt_count计数器，其初始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0时，内核就可执行抢占。从中断返回内核空间的时候，内核会检查TIF_NEED_RESCHED和preempt_count的值，如果TIF_NEED_RESCHED被设置，并且preempt_count为0，这说明有一个更为重要的进程需要运行并且可以安全地抢占，此时就会调用调度程序。如果preempt_count不为0，说明有当前进程持有锁，抢占是不安全的。这时，就会像通常那样直接从中断返回当前执行进程。如果当前进程持有的所有的锁都被释放了，那么preempt_count就会重新为0。此时，释放锁的代码会检查TIF_NEED_RESCHED是否被设置，如果是的话，就会调用调度程序。内核抢占会发生在：当从中断处理程序返回内核空间的时候。当内核代码再一次具有可抢占性的时候。如果内核中的进程显式调用schedule()。如果内核中的进程阻塞，同样会调用schedule()。有些内核代码需要允许或禁止内核抢占，可通过preempt_disable()和preempt_enable()实现。由于内核是可抢占的，内核中的进程在任何时刻都可能停下来以便另一个具有更高优先级的进程