现代操作系统 Chapter 7.ppt

《现代操作系统 Chapter 7.ppt》由会员分享，可在线阅读，更多相关《现代操作系统 Chapter 7.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 7 Case study:LinuxContentsvLinux内核结构内核结构vLinux的进程管理的进程管理vLinux的进程调度的进程调度vLinux的内存管理的内存管理27.1 Linux内核结构内核结构37.2 Linux的进程管理的进程管理一般来说，一般来说，Linux中的进程都具备以下四要素：中的进程都具备以下四要素：v有一段程序供其执行。有一段程序供其执行。v有起码的有起码的“私有财产私有财产”，这就是系统专用的系统堆，这就是系统专用的系统堆栈空间。栈空间。v有有“户口户口”，这就是在内核中的一个，这就是在内核中的一个task_struct数数据结构（在操作系统

2、教科书中常称为据结构（在操作系统教科书中常称为PCB）。）。v有独立的存储空间，意味着拥有专有的用户空间。有独立的存储空间，意味着拥有专有的用户空间。注：缺了其中任何一条就不成其为注：缺了其中任何一条就不成其为“进程进程”。如果只具备。如果只具备了前面了前面3 3条而缺第条而缺第4 4条，那就称为条，那就称为“线程线程”。特别地，如果。特别地，如果完全没有用户空间，就称为完全没有用户空间，就称为“内核线程内核线程”，而如果共享用，而如果共享用户空间则就称为户空间则就称为“用户线程用户线程”。4task与与process Linux系统中的系统中的“进程进程”(process)和和“任务任务”(

3、task)是同一个意思，在内核代码是同一个意思，在内核代码中也常混用这两个名词。中也常混用这两个名词。57.2.1 进程描述符及任务结构进程描述符及任务结构v在内核中，进程描述符是一个名为在内核中，进程描述符是一个名为task_struct的结构体，用于保存进程的属的结构体，用于保存进程的属性和其他信息，它在性和其他信息，它在include/linux/sched.h中定义。中定义。v内核用双向循环链表内核用双向循环链表task_list存放所有进程存放所有进程描述符；同时借助全局变量描述符；同时借助全局变量current保存当保存当前运行进程的前运行进程的task_struct。6进程描述符

4、进程描述符v进程描述符必须保存的信息类型有：进程描述符必须保存的信息类型有：进程的属性进程的属性进程间的关系进程间的关系进程的内存空间进程的内存空间文件管理文件管理信号量管理信号量管理进程的可信度进程的可信度资源限制资源限制与调度相关的域与调度相关的域77.2.2 进程状态进程状态task_struct结构中的结构中的state域描述了进程的当前域描述了进程的当前状态。系统中的每个进程都必然处于几种进程状态状态。系统中的每个进程都必然处于几种进程状态之一。其具体定义见之一。其具体定义见sched.h。#define TASK_RUNNING0#define TASK_INTERRUPTIBLE

5、1#define TASK_UNINTERRUPTIBLE2#define TASK_STOPPED4#define TASK_TRACED8#define EXIT_ZOMBIE16#define EXIT_DEAD328进程状态进程状态vTASK_RUNNING可执行状态，表示这个进程可以被调度执行而成为当前进程。可执行状态，表示这个进程可以被调度执行而成为当前进程。当进程处于这样的可执行状态时，内核就将该进程的当进程处于这样的可执行状态时，内核就将该进程的task_struct结构通过其队列头结构通过其队列头run_list挂入一个挂入一个“运行队列运行队列”。vTASK_INTERRU

6、PTIBLE进程睡眠，可因进程睡眠，可因“信号到来信号到来”而被唤醒而被唤醒vTASK_UNINTERRUPTIBLE进程深度睡眠，不受信号干扰进程深度睡眠，不受信号干扰vTASK_STOPPED挂起状态，主要用于调试目的挂起状态，主要用于调试目的vTASK_ZOMBIE进程已经结束，但资源未释放，进程结构还在（进程已经进程已经结束，但资源未释放，进程结构还在（进程已经“去世去世”但但“户口户口”尚未注销）尚未注销）9进程状态转换进程状态转换107.2.3 进程创建进程创建vLinux将进程的创建与目标程序的执行分成将进程的创建与目标程序的执行分成两步两步：第一步：第一步：从已经存在的从已经存

7、在的“父进程父进程”复制出一个复制出一个“子进程子进程”。复制出来的子进程有自己的。复制出来的子进程有自己的task_struct和系统空间堆栈，但与父进程共享和系统空间堆栈，但与父进程共享其它所有的资源。其它所有的资源。Linux为此提供了两个系统调用：为此提供了两个系统调用：fork()和和clone()。第二步：第二步：读取可执行文件并将其载入地址空间读取可执行文件并将其载入地址空间开始运行。开始运行。Linux为此提供了一个函数族：为此提供了一个函数族：exec()。11fork()与与clone()的区别的区别vfork()是全部复制，父进程所有的资源全都是全部复制，父进程所有的资源

8、全都通过数据结构的复制通过数据结构的复制“遗传遗传”给子进程。给子进程。vclone()则可以将资源有选择地复制给子进则可以将资源有选择地复制给子进程，而没有复制的数据结构则通过指针的复程，而没有复制的数据结构则通过指针的复制让子进程共享。在极端的情况下，一个进制让子进程共享。在极端的情况下，一个进程可以程可以clone()出一个线程。出一个线程。vfork()是无参数的，是无参数的，clone()是带有参数的。是带有参数的。12写时拷贝写时拷贝(copy_on_write)v传统的传统的fork()系统调用直接把所有的资源复制给新系统调用直接把所有的资源复制给新创建的进程。创建的进程。缺点：

9、效率低下缺点：效率低下vLinux的的fork()使用使用写时拷贝写时拷贝来实现。来实现。v写时拷贝写时拷贝是一种可以推迟甚至免除拷贝数据的技是一种可以推迟甚至免除拷贝数据的技术。术。新创建进程时，内核并不复制整个进程地址空间，新创建进程时，内核并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝；只有在而是让父进程和子进程共享同一个拷贝；只有在需要写入的时候，数据才会被复制，从而使各个需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。进程拥有各自的拷贝。13写时拷贝写时拷贝v写时拷贝技术使地址空间上的页的拷贝被推写时拷贝技术使地址空间上的页的拷贝被推迟到实际发生写入的时候

10、，在页根本不会被迟到实际发生写入的时候，在页根本不会被写入的情况下（如写入的情况下（如fork()后立即调用后立即调用exec()），它们就无需复制了。），它们就无需复制了。v一般情况下，进程创建后都会马上运行一个一般情况下，进程创建后都会马上运行一个可执行的文件，这种优化可以避免拷贝大量可执行的文件，这种优化可以避免拷贝大量根本就不会被使用的数据。根本就不会被使用的数据。147.3 Linux的进程调度的进程调度v调度程序是内核的组成部分，它负责选择下调度程序是内核的组成部分，它负责选择下一个要运行的进程。一个要运行的进程。v调度程序的基本工作调度程序的基本工作：在一组处于可运行状：在一组处

11、于可运行状态的进程中选择一个来执行。态的进程中选择一个来执行。vLinux提供提供抢占式抢占式的多任务模式。的多任务模式。157.3.1 调度策略调度策略(policy)调度策略决定调度程序在何时让什调度策略决定调度程序在何时让什么进程运行。么进程运行。16(1)I/O消耗型和处理器消耗型进程消耗型和处理器消耗型进程vI/O消耗型进程消耗型进程：进程的大部分时间用来提：进程的大部分时间用来提交交I/O请求或是等待请求或是等待I/O请求。请求。这样的进程经常处于可运行状态，但通常每这样的进程经常处于可运行状态，但通常每次运行时间很短。次运行时间很短。v处理器消耗型进程处理器消耗型进程：它把时间大

12、多用在执行：它把时间大多用在执行代码上。代码上。v对于对于处理器消耗型进程处理器消耗型进程，调度策略是尽量降，调度策略是尽量降低它们的运行频率。低它们的运行频率。17调度策略调度策略v调度策略通常要在两个矛盾中寻找平衡：调度策略通常要在两个矛盾中寻找平衡：进程响应时间短进程响应时间短系统吞吐量高系统吞吐量高vLinux为了保证交互式应用，更倾向于为了保证交互式应用，更倾向于优先优先调度调度I/O消耗型进程消耗型进程。18调度策略定义调度策略定义v在在include/linux/sched.h中有如下定义：中有如下定义：#define SCHED_NORMAL0 /默认类型，普通的用户进程，动态

13、优先调度策略默认类型，普通的用户进程，动态优先调度策略#define SCHED_FIFO1 /实时进程，先进先出调度规则实时进程，先进先出调度规则#define SCHED_RR2/实时进程，循环实时进程，循环round-robin调度规则调度规则vtask_struct中的成中的成员policy是是进程的程的调度策度策略，它的略，它的值为上述三种策略之一。上述三种策略之一。19(2)进程优先级进程优先级v基于优先级的调度：调度程序总是选择时间基于优先级的调度：调度程序总是选择时间片未用尽而且优先级最高的进程运行。片未用尽而且优先级最高的进程运行。vLinux实现了基于实现了基于动态优先级动

14、态优先级的调度方法。的调度方法。vLinux内核提供了两组独立的优先级：内核提供了两组独立的优先级：nice值：范围从值：范围从-2019，默认值是，默认值是0。值越大，。值越大，优先级越低。优先级越低。实时优先级：任何实时进程的优先级都高于普实时优先级：任何实时进程的优先级都高于普通进程。通进程。20(3)时间片时间片v时间片大小的确定时间片大小的确定太短太短 问题？问题？太长太长 问题？问题？vLinux的调度程序提供较长的默认时间片给的调度程序提供较长的默认时间片给交互式程序。交互式程序。v Linux还能根据进程的优先级动态调整分配还能根据进程的优先级动态调整分配给它的时间片，从而保证

15、优先级高的进程，给它的时间片，从而保证优先级高的进程，执行的频率高，执行时间长。执行的频率高，执行时间长。21时间片时间片v当一个进程的时间片耗尽时，就认为当一个进程的时间片耗尽时，就认为进程到进程到期了期了。v没有时间片的进程不会再投入运行，除非等没有时间片的进程不会再投入运行，除非等到其它所有的进程都耗尽了它们的时间片，到其它所有的进程都耗尽了它们的时间片，这时，会这时，会重新计算所有进程的时间片重新计算所有进程的时间片。22(4)进程抢占进程抢占v两种情况下会发生进程抢占：两种情况下会发生进程抢占：有一个进程进入有一个进程进入TASK_RUNNING状态，而它状态，而它的优先级高于当前正

16、在运行的进程的优先级高于当前正在运行的进程当正在运行的进程的时间片变为当正在运行的进程的时间片变为0时时237.3.2 Linux调度算法调度算法Linux的调度程序在的调度程序在kernel/sched.c中定义。中定义。24(1)可执行队列可执行队列v可执行队列是调度程序中最基本的数据结构，可执行队列是调度程序中最基本的数据结构，它定义于它定义于kernel/sched.c中，由结构中，由结构runqueue表示。表示。v可执行队列是给定处理器上的可执行进程的可执行队列是给定处理器上的可执行进程的链表，链表，每个处理器一个每个处理器一个。25可执行队列可执行队列runqueuestruct

17、 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*migratio

18、n_thread;struct list_head migration_queue;26(2)优先级数组优先级数组v每个运行队列有两个优先级数组，一个每个运行队列有两个优先级数组，一个活跃活跃的的，一个，一个过期的过期的。v优先级数组在优先级数组在kernel/sched.c中定义，是中定义，是prio_array类型的结构体。类型的结构体。v优先级数组是一种能够提供优先级数组是一种能够提供O(1)算法复杂度算法复杂度的数据结构。的数据结构。27prio_array结构体结构体vMAX_PRIO定义定义了系统拥有的优先级个数，默认了系统拥有的优先级个数，默认值是值是140，在，在sched.h

19、中定义如下：中定义如下：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)28prio_array结构体分析结构体分析vBITMAP_SIZE是优先级位图数组的大小，是优先级位图数组的大小，定义如下：定义如下：#define

20、 BITMAP_SIZE (MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)v由以上定由以上定义，计算出算出BITMAP_SIZE=5。v数数组bitmapBITMAP_SIZE为unsigned long型型，长32位，如果每位代表一个位，如果每位代表一个优先先级的的话，共，共有有32*5160位位，足足够表示前面提到的表示前面提到的140个个优先先级。29prio_array结构体分析结构体分析v每个优先级数组都包含一个这样的位图成员，至每个优先级数组都包含一个这样的位图成员，至少为每个优先级准备一位。初始时，所有的位都少为每个优先级准备一位。初始

21、时，所有的位都置置0；当拥有某个优先级的进程准备执行时，位图；当拥有某个优先级的进程准备执行时，位图中的相应位就被置中的相应位就被置1。v这样，查找系统中最高的优先级就变成了查找位这样，查找系统中最高的优先级就变成了查找位图中被设置的第一个位。因为优先级的个数是定图中被设置的第一个位。因为优先级的个数是定值值(140个个)，所以，所以查找时间恒定查找时间恒定，并不受系统到底，并不受系统到底有多少可执行进程的影响。有多少可执行进程的影响。30prio_array结构体分析结构体分析v每个每个prio_array包含一个叫作包含一个叫作queue的数组，的数组，该数组的每个元素都是一个该数组的每个

22、元素都是一个struct list_head类型的队列。每个队列与一个给类型的队列。每个队列与一个给定的优先级相对应。定的优先级相对应。vprio_array中还包含了一个计数器中还包含了一个计数器nr_active，记录该优先级数组内可执行进，记录该优先级数组内可执行进程的数目。程的数目。31(3)重新计算时间片重新计算时间片v重新计算时间片的老方法：重新计算时间片的老方法：for(系统中的每个任务系统中的每个任务)重新计算优先级重新计算优先级重新计算时间片重新计算时间片v存在的弊端：存在的弊端：耗费的时间长耗费的时间长必须靠锁来保护任务队列，加剧对锁的争用必须靠锁来保护任务队列，加剧对锁的

23、争用重新计算时间片的时机不确定重新计算时间片的时机不确定实现粗糙实现粗糙32新的新的Linux调度程序如何计算时间片调度程序如何计算时间片vLinux调度程序为每个处理器维护两个优先调度程序为每个处理器维护两个优先级数组：级数组：活动数组活动数组：其中的可执行队列上的进程都还有：其中的可执行队列上的进程都还有时间片剩余时间片剩余过期数组过期数组：其中的可执行队列上的进程都耗尽：其中的可执行队列上的进程都耗尽了时间片了时间片v当一个进程的时间片耗尽时，它会被移至当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已给它重过期数组，但在此之前，时间片已给它重新计算好了。新计算好了。33

24、活动数组和过期数组的切换活动数组和过期数组的切换现在，重新计算时间片只需要在活动数组和过现在，重新计算时间片只需要在活动数组和过期数组之间来回切换就行了。这个动作由期数组之间来回切换就行了。这个动作由schedule()完成，部分代码如下：完成，部分代码如下：prio_array_t*array;array=rq-active;if(!array-nr_active)rq-active=rq-expired;rq-expired=array;array=rq-active;34(4)调度程序调度程序schedule()vschedule()函数完成的工作：选定下一个函数完成的工作：选定下一个投

25、入运行的进程，并切换到这个进程。投入运行的进程，并切换到这个进程。v在在schedule()函数中首先要判断谁是优先函数中首先要判断谁是优先级最高的进程，代码见下页。级最高的进程，代码见下页。35判断谁是优先级最高的进程判断谁是优先级最高的进程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=

26、array-queue+idx;next=list_entry(queue-next,task_t,run_list);36(5)计算优先级和时间片计算优先级和时间片v进程有一个初始优先级进程有一个初始优先级(也称静态优先级也称静态优先级)，叫做，叫做nice值，范围从值，范围从-2019，默认为，默认为0，它由用户指定。，它由用户指定。vnice值越小，优先级越高值越小，优先级越高。vnice值通过转换后存放在值通过转换后存放在task_struct结构结构的的static_prio域中，转换方法见下页：域中，转换方法见下页：37如何将如何将nice转换成转换成static_priov经计算

27、得：经计算得：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);38动态优先级动态优先级priov调度程序要用到的动态优先级存放在调度程序要用到的动态优先级存放在task_struct结构的结构的prio域中。域中。v动态优先级动态优先级prio通过一个关于静态优先级和通过一个关于静态优先级和进程交互性的函

28、数关系计算而来。进程交互性的函数关系计算而来。39计算进程的动态优先级计算进程的动态优先级veffective_prio()函数可以返回一个进程的函数可以返回一个进程的动态优先级。动态优先级。v该函数以该函数以nice值为基数，再加上值为基数，再加上-5到到+5之间之间的的进程交互性的奖励或罚分进程交互性的奖励或罚分。v该函数在该函数在kernel/sched.c中实现，代码见下中实现，代码见下页。页。40effective_prio()函数函数static int effective_prio(task_t*p)int bonus,prio;if(rt_task(p)return p-pri

29、o;bonus=CURRENT_BONUS(p)-MAX_BONUS/2;prio=p-static_prio-bonus;if(prio MAX_PRIO-1)prio=MAX_PRIO-1;return prio;41bonus的计算中需要用到的宏和函数的计算中需要用到的宏和函数#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

30、_BONUS(p)(NS_TO_JIFFIES(p)-sleep_avg)*MAX_BONUS/MAX_SLEEP_AVG)42bonus的计算的计算v通过计算得：通过计算得：MAX_BONUS=10；MAX_SLEEP_AVG100*101000。v假设进程的休眠时间为假设进程的休眠时间为x，即即x=(p)-sleep_avg，则，则CURRENT_BONUS(p)=x/(1000000000/1000)10/1000=x/108。v因此因此bonus=CURRENT_BONUS(p)-MAX_BONUS/2x/108-5。43结论结论v通过以上分析可得出：通过以上分析可得出：休眠时间越长休

31、眠时间越长 bonus越大越大 prio越小越小进程的动态优先级越高。进程的动态优先级越高。因此因此进程的休眠时间长，它的优先级就能进程的休眠时间长，它的优先级就能得到提高得到提高。44调度程序如何了解进程的交互性强不强？调度程序如何了解进程的交互性强不强？v以以进程休眠的时间长短进程休眠的时间长短作为标准。作为标准。如果一个进程大部分时间都在休眠如果一个进程大部分时间都在休眠I/O消耗型，交互性强消耗型，交互性强如果一个进程执行时间比休眠时间长如果一个进程执行时间比休眠时间长处理器消耗型处理器消耗型v交互性强的进程，在运行过程中可得到奖励，交互性强的进程，在运行过程中可得到奖励，从而提高它的

32、优先级。从而提高它的优先级。45sleep_avg域域vLinux记录了一个进程用于休眠和用于执行记录了一个进程用于休眠和用于执行的时间。该值存放在的时间。该值存放在task_struct结构的结构的sleep_avg域中，其范围从域中，其范围从0MAX_SLEEP_AVG，默认值为，默认值为10毫秒。毫秒。v当一个进程从休眠状态恢复到执行状态时，当一个进程从休眠状态恢复到执行状态时，sleep_avg会根据它休眠时间的长短而增长，会根据它休眠时间的长短而增长，直至达到直至达到MAX_SLEEP_AVG为止；相反，为止；相反，进程每运行一个时钟节拍，进程每运行一个时钟节拍，sleep_avg就

33、做就做相应的递减，到相应的递减，到0为止。为止。46重新计算时间片重新计算时间片v重新计算时间片时，只需要以静态优先级重新计算时间片时，只需要以静态优先级为基础。为基础。v新创建的子进程与父进程平分父进程剩余新创建的子进程与父进程平分父进程剩余的时间片。的时间片。v当一个任务的时间片用完后，当一个任务的时间片用完后，task_timeslice()函数为给定任务返回一个新的时间片。函数为给定任务返回一个新的时间片。时间片的计算只需要把优先级按比例缩放，时间片的计算只需要把优先级按比例缩放，使其符合时间片的数值范围就可以了。使其符合时间片的数值范围就可以了。47task_timeslice()函

34、数函数#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);48时间片时间片v进程的优先级越高，获得的时间片越长。进程的优先级越高，获得的时间片越长。进程类型进程类型nicenice值值时间片长度时间片长度新创建的进程新创建的进程父进程的值父进

35、程的值父进程的一半父进程的一半优先级最低的进程优先级最低的进程195毫秒毫秒默认优先级的进程默认优先级的进程0100毫秒毫秒优先级最高的进程优先级最高的进程-20800毫秒毫秒49另一种支持交互进程的机制另一种支持交互进程的机制v如果一个进程的交互性非常强，那么当它的时间片如果一个进程的交互性非常强，那么当它的时间片用完后，它会被用完后，它会被再放置到活动数组再放置到活动数组而不是过期数组而不是过期数组中。中。v该逻辑在该逻辑在scheduler_tick()中实现，部分代码如下：中实现，部分代码如下：struct runqueue*rq=this_rq();struct task_struc

36、t*p=current;if(!-p-time_slice)if(!TASK_INTERACTIVE(p)|EXPIRED_STARVING(rq)enqueue_task(p,rq-expired);elseenqueue_task(p,rq-active);50scheduler_tick()分析分析v首先，这段代码减小进程时间片的值，再看它是首先，这段代码减小进程时间片的值，再看它是否为否为0。如果为。如果为0，说明其时间片已用完，需要将，说明其时间片已用完，需要将它插入到一个数组中。它插入到一个数组中。v然后该代码通过然后该代码通过TASK_INTERACTIVE()宏来查宏来查看这个进程是不是交互型进程。看这个进程是不是交互型进程。v接着，接着，EXPIRED_STARVING()宏负责检查过期宏负责检查过期数组内的进程是否处于饥饿状态，如果是，那么数组内的进程是否处于饥饿状态，如果是，那么再把当前进程放置到活动数组会进一步拖延切换再把当前进程放置到活动数组会进一步拖延切换时机，导致过期数组内的进程越来越饥饿。只要时机，导致过期数组内的进程越来越饥饿。只要不发生这种情况，进程就会被重新放置在活动数不发生这种情况，进程就会被重新放置在活动数组里；否则，进程会被放入过期数组里。组里；否则，进程会被放入过期数组里。515253