现代操作系统Cha.ppt

Chapter 7 Case study:Linux,Contents,Linux内核结构Linux的进程管理Linux的进程调度Linux的内存管理,7.1 Linux内核结构,7.2 Linux的进程管理,一般来说，Linux中的进程都具备以下四要素：有一段程序供其执行。有起码的“私有财产”，这就是系统专用的系统堆栈空间。有“户口”，这就是在内核中的一个task_struct数据结构（在操作系统教科书中常称为PCB）。有独立的存储空间，意味着拥有专有的用户空间。,注：缺了其中任何一条就不成其为“进程”。如果只具备了前面3条而缺第4条，那就称为“线程”。特别地，如果完全没有用户空间，就称为“内核线程”，而如果共享用户空间则就称为“用户线程”。,task与process,Linux系统中的“进程”(process)和“任务”(task)是同一个意思，在内核代码中也常混用这两个名词。,7.2.1 进程描述符及任务结构,在内核中，进程描述符是一个名为task_struct的结构体，用于保存进程的属性和其他信息，它在include/linux/sched.h中定义。内核用双向循环链表task_list存放所有进程描述符；同时借助全局变量current保存当前运行进程的task_struct。,进程描述符,进程描述符必须保存的信息类型有：进程的属性进程间的关系进程的内存空间文件管理信号量管理进程的可信度资源限制与调度相关的域,7.2.2 进程状态,task_struct结构中的state域描述了进程的当前状态。系统中的每个进程都必然处于几种进程状态之一。其具体定义见sched.h。,#define TASK_RUNNING0#define TASK_INTERRUPTIBLE1#define TASK_UNINTERRUPTIBLE2#define TASK_STOPPED4#define TASK_TRACED8#define EXIT_ZOMBIE16#define EXIT_DEAD32,进程状态,TASK_RUNNING可执行状态，表示这个进程可以被调度执行而成为当前进程。当进程处于这样的可执行状态时，内核就将该进程的task_struct结构通过其队列头run_list挂入一个“运行队列”。TASK_INTERRUPTIBLE进程睡眠，可因“信号到来”而被唤醒TASK_UNINTERRUPTIBLE进程深度睡眠，不受信号干扰TASK_STOPPED挂起状态，主要用于调试目的TASK_ZOMBIE进程已经结束，但资源未释放，进程结构还在（进程已经“去世”但“户口”尚未注销）,进程状态转换,7.2.3 进程创建,Linux将进程的创建与目标程序的执行分成两步：第一步：从已经存在的“父进程”复制出一个“子进程”。复制出来的子进程有自己的task_struct和系统空间堆栈，但与父进程共享其它所有的资源。Linux为此提供了两个系统调用：fork()和clone()。第二步：读取可执行文件并将其载入地址空间开始运行。Linux为此提供了一个函数族：exec()。,fork()与clone()的区别,fork()是全部复制，父进程所有的资源全都通过数据结构的复制“遗传”给子进程。clone()则可以将资源有选择地复制给子进程，而没有复制的数据结构则通过指针的复制让子进程共享。在极端的情况下，一个进程可以clone()出一个线程。fork()是无参数的，clone()是带有参数的。,写时拷贝(copy_on_write),传统的fork()系统调用直接把所有的资源复制给新创建的进程。缺点：效率低下Linux的fork()使用写时拷贝来实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。新创建进程时，内核并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝；只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。,写时拷贝,写时拷贝技术使地址空间上的页的拷贝被推迟到实际发生写入的时候，在页根本不会被写入的情况下（如fork()后立即调用exec()），它们就无需复制了。一般情况下，进程创建后都会马上运行一个可执行的文件，这种优化可以避免拷贝大量根本就不会被使用的数据。,7.3 Linux的进程调度,调度程序是内核的组成部分，它负责选择下一个要运行的进程。调度程序的基本工作：在一组处于可运行状态的进程中选择一个来执行。Linux提供抢占式的多任务模式。,7.3.1 调度策略(policy),调度策略决定调度程序在何时让什么进程运行。,(1)I/O消耗型和处理器消耗型进程,I/O消耗型进程：进程的大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，但通常每次运行时间很短。处理器消耗型进程：它把时间大多用在执行代码上。对于处理器消耗型进程，调度策略是尽量降低它们的运行频率。,调度策略,调度策略通常要在两个矛盾中寻找平衡：进程响应时间短系统吞吐量高Linux为了保证交互式应用，更倾向于优先调度I/O消耗型进程。,调度策略定义,在include/linux/sched.h中有如下定义：,#define SCHED_NORMAL0/默认类型，普通的用户进程，动态优先调度策略#define SCHED_FIFO1/实时进程，先进先出调度规则#define SCHED_RR2/实时进程，循环round-robin调度规则,task_struct中的成员policy是进程的调度策略，它的值为上述三种策略之一。,(2)进程优先级,基于优先级的调度：调度程序总是选择时间片未用尽而且优先级最高的进程运行。Linux实现了基于动态优先级的调度方法。Linux内核提供了两组独立的优先级：nice值：范围从-2019，默认值是0。值越大，优先级越低。实时优先级：任何实时进程的优先级都高于普通进程。,(3)时间片,时间片大小的确定太短 问题？太长 问题？Linux的调度程序提供较长的默认时间片给交互式程序。Linux还能根据进程的优先级动态调整分配给它的时间片，从而保证优先级高的进程，执行的频率高，执行时间长。,时间片,当一个进程的时间片耗尽时，就认为进程到期了。没有时间片的进程不会再投入运行，除非等到其它所有的进程都耗尽了它们的时间片，这时，会重新计算所有进程的时间片。,(4)进程抢占,两种情况下会发生进程抢占：有一个进程进入TASK_RUNNING状态，而它的优先级高于当前正在运行的进程当正在运行的进程的时间片变为0时,7.3.2 Linux调度算法,Linux的调度程序在kernel/sched.c中定义。,(1)可执行队列,可执行队列是调度程序中最基本的数据结构，它定义于kernel/sched.c中，由结构runqueue表示。可执行队列是给定处理器上的可执行进程的链表，每个处理器一个。,可执行队列runqueue,struct runqueue spinlock_t lock;unsigned long nr_running;unsigned long long nr_switches;unsigned long nr_uninterruptible;unsigned long expired_timestamp;unsigned long long timestamp_last_tick;task_t*curr,*idle;struct mm_struct*prev_mm;prio_array_t*active,*expired,arrays2;atomic_t nr_iowait;task_t*migration_thread;struct list_head migration_queue;,(2)优先级数组,每个运行队列有两个优先级数组，一个活跃的，一个过期的。优先级数组在kernel/sched.c中定义，是prio_array类型的结构体。优先级数组是一种能够提供O(1)算法复杂度的数据结构。,prio_array结构体,MAX_PRIO定义了系统拥有的优先级个数，默认值是140，在sched.h中定义如下：,struct prio_array unsigned int nr_active;/可执行进程数目unsigned long bitmapBITMAP_SIZE;struct list_head queueMAX_PRIO;,#define MAX_USER_RT_PRIO100#define MAX_RT_PRIOMAX_USER_RT_PRIO#define MAX_PRIO(MAX_RT_PRIO+40),prio_array结构体分析,BITMAP_SIZE是优先级位图数组的大小，定义如下：,#define BITMAP_SIZE(MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long),由以上定义，计算出BITMAP_SIZE=5。数组bitmapBITMAP_SIZE为unsigned long型，长32位，如果每位代表一个优先级的话，共有32*5160位，足够表示前面提到的140个优先级。,prio_array结构体分析,每个优先级数组都包含一个这样的位图成员，至少为每个优先级准备一位。初始时，所有的位都置0；当拥有某个优先级的进程准备执行时，位图中的相应位就被置1。这样，查找系统中最高的优先级就变成了查找位图中被设置的第一个位。因为优先级的个数是定值(140个)，所以查找时间恒定，并不受系统到底有多少可执行进程的影响。,prio_array结构体分析,每个prio_array包含一个叫作queue的数组，该数组的每个元素都是一个struct list_head类型的队列。每个队列与一个给定的优先级相对应。prio_array中还包含了一个计数器nr_active，记录该优先级数组内可执行进程的数目。,(3)重新计算时间片,重新计算时间片的老方法：,for(系统中的每个任务)重新计算优先级重新计算时间片,存在的弊端：耗费的时间长必须靠锁来保护任务队列，加剧对锁的争用重新计算时间片的时机不确定实现粗糙,新的Linux调度程序如何计算时间片,Linux调度程序为每个处理器维护两个优先级数组：活动数组：其中的可执行队列上的进程都还有时间片剩余过期数组：其中的可执行队列上的进程都耗尽了时间片当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已给它重新计算好了。,活动数组和过期数组的切换,现在，重新计算时间片只需要在活动数组和过期数组之间来回切换就行了。这个动作由schedule()完成，部分代码如下：,prio_array_t*array;array=rq-active;if(!array-nr_active)rq-active=rq-expired;rq-expired=array;array=rq-active;,这种交换是O(1)级调度程序的核心。,(4)调度程序schedule(),schedule()函数完成的工作：选定下一个投入运行的进程，并切换到这个进程。在schedule()函数中首先要判断谁是优先级最高的进程，代码见下页。,判断谁是优先级最高的进程,struct task_struct*prev,*next;struct runqueue*rq;struct prio_array*array;struct list_head*queue;int idx;prev=current;array=rq-active;idx=sched_find_first_bit(array-bitmap);queue=array-queue+idx;next=list_entry(queue-next,task_t,run_list);,(5)计算优先级和时间片,进程有一个初始优先级(也称静态优先级)，叫做nice值，范围从-2019，默认为0，它由用户指定。nice值越小，优先级越高。nice值通过转换后存放在task_struct结构的static_prio域中，转换方法见下页：,如何将nice转换成static_prio,经计算得：static_prio的范围为100139，值越小，优先级越高。,#define MAX_RT_PRIO100#define NICE_TO_PRIO(nice)(MAX_RT_PRIO+(nice)+20)struct task_struct*p;p-static_prio=NICE_TO_PRIO(nice);,动态优先级prio,调度程序要用到的动态优先级存放在task_struct结构的prio域中。动态优先级prio通过一个关于静态优先级和进程交互性的函数关系计算而来。,计算进程的动态优先级,effective_prio()函数可以返回一个进程的动态优先级。该函数以nice值为基数，再加上-5到+5之间的进程交互性的奖励或罚分。该函数在kernel/sched.c中实现，代码见下页。,effective_prio()函数,static int effective_prio(task_t*p)int bonus,prio;if(rt_task(p)return p-prio;bonus=CURRENT_BONUS(p)-MAX_BONUS/2;prio=p-static_prio-bonus;if(prio MAX_PRIO-1)prio=MAX_PRIO-1;return prio;,bonus的计算中需要用到的宏和函数,#define HZ1000#define NS_TO_JIFFIES(TIME)(TIME)/(1000000000/HZ)#define DEF_TIMESLICE(100*HZ/1000)#define MAX_SLEEP_AVG(DEF_TIMESLICE*MAX_BONUS)#define CURRENT_BONUS(p)(NS_TO_JIFFIES(p)-sleep_avg)*MAX_BONUS/MAX_SLEEP_AVG),bonus的计算,通过计算得：MAX_BONUS=10；MAX_SLEEP_AVG100*101000。假设进程的休眠时间为x，即x=(p)-sleep_avg，则CURRENT_BONUS(p)=x/(1000000000/1000)10/1000=x/108。因此bonus=CURRENT_BONUS(p)-MAX_BONUS/2x/108-5。,结论,通过以上分析可得出：休眠时间越长 bonus越大 prio越小进程的动态优先级越高。因此进程的休眠时间长，它的优先级就能得到提高。,调度程序如何了解进程的交互性强不强？,以进程休眠的时间长短作为标准。如果一个进程大部分时间都在休眠I/O消耗型，交互性强如果一个进程执行时间比休眠时间长处理器消耗型交互性强的进程，在运行过程中可得到奖励，从而提高它的优先级。,sleep_avg域,Linux记录了一个进程用于休眠和用于执行的时间。该值存放在task_struct结构的sleep_avg域中，其范围从0MAX_SLEEP_AVG，默认值为10毫秒。当一个进程从休眠状态恢复到执行状态时，sleep_avg会根据它休眠时间的长短而增长，直至达到MAX_SLEEP_AVG为止；相反，进程每运行一个时钟节拍，sleep_avg就做相应的递减，到0为止。,重新计算时间片,重新计算时间片时，只需要以静态优先级为基础。新创建的子进程与父进程平分父进程剩余的时间片。当一个任务的时间片用完后，task_timeslice()函数为给定任务返回一个新的时间片。时间片的计算只需要把优先级按比例缩放，使其符合时间片的数值范围就可以了。,task_timeslice()函数,#define SCALE_PRIO(x,prio)max(x*(MAX_PRIO-prio)/(MAX_USER_PRIO/2),MIN_TIMESLICE)static unsigned int task_timeslice(task_t*p)if(p-static_prio static_prio);elsereturn SCALE_PRIO(DEF_TIMESLICE,p-static_prio);,时间片,进程的优先级越高，获得的时间片越长。,另一种支持交互进程的机制,如果一个进程的交互性非常强，那么当它的时间片用完后，它会被再放置到活动数组而不是过期数组中。该逻辑在scheduler_tick()中实现，部分代码如下：,struct runqueue*rq=this_rq();struct task_struct*p=current;if(!-p-time_slice)if(!TASK_INTERACTIVE(p)|EXPIRED_STARVING(rq)enqueue_task(p,rq-expired);elseenqueue_task(p,rq-active);,scheduler_tick()分析,首先，这段代码减小进程时间片的值，再看它是否为0。如果为0，说明其时间片已用完，需要将它插入到一个数组中。然后该代码通过TASK_INTERACTIVE()宏来查看这个进程是不是交互型进程。接着，EXPIRED_STARVING()宏负责检查过期数组内的进程是否处于饥饿状态，如果是，那么再把当前进程放置到活动数组会进一步拖延切换时机，导致过期数组内的进程越来越饥饿。只要不发生这种情况，进程就会被重新放置在活动数组里；否则，进程会被放入过期数组里。,