第八章 进程调度和时间

第八章进程调度和时间8.1进程调度•在分时系统中，内核给每个进程分配一段CPU时间，这个时间称为时间片。•一个进程的时间片用完时，内核抢先该进程并调度另一个进程。•每个进程都有一个调度优先权。在用户态的进程的优先权是它最近使用CPU时间的函数，最近使用过较多的CPU时间的进程得到较低的优先权。•当内核做上下文切换时，它选取有最高优先权的进程，切换到该进程的上下文。•当进程从核心态切换到用户态时，内核重新计算它的优先权，并定期调整在用户态“就绪”的每个进程的优先权。•系统通过一个硬件时钟计时。此硬件时钟以一个固定的，依赖于硬件的频率中断CPU，此频率一般在每秒钟50到100次之间。每次时钟中断称为时钟滴答。•unix系统上的调度程序叫做多级反馈循环调度。•内核给进程分一个CPU时间片，内核在剥夺一个时间片超时的进程时，把它反馈到若干优先级队列中的某一队列。•一个进程在它结束之前，可能要多次通过反馈循环。8.1.1算法上下文切换结束时，内核执行此算法来调度一个进程，从处于“在内存中就绪”和“被抢先”状态的进程中选取优先权最高的进程。选取一个尚未装入内存的进程是没有意义的，因为该进程不能运行。如果若干进程都具有最高优先权，内核按循环调度策略选择在“就绪”状态时间最长的进程。若无合格的进程，内核则休闲，直到下次中断，下次中断最迟发生在下一个时钟滴答时（时钟中断）。处理完中断后，内核再次调度一个进程去运行。8.1.2调度参数•进程优先权分为：用户优先权和核心优先权。•每种优先权有若干优先权值（优先数），每个优先权有一个逻辑上与它相关联的进程队列。•具有用户级优先权的进程在它们从核心态返回到用户态时被抢先，而得到它们的用户级优先权。•具有核心级优先权的进程是在算法sleep中得到核心级优先权的。用户级优先权低于一个阈值，核心级优先权高于该阈值。收到软中断信号时，具有低核心优先权的进程被唤醒；具有高核心优先权的进程继续睡眠。•内核在特定的进程状态下计算一个进程的优先权：•1.内核将优先权赋给一个即将进入睡眠的进程。•在低层算法中睡眠的进程的不活动的时间越长，就越容易引起系统瓶颈问题，因此，它们比可能引起较少系统瓶颈的进程得到较高的优先权。•例：一个睡眠等待磁盘I/O的进程比等待一个自由缓冲区的进程具有较高优先权。这是因为等待磁盘I/O的进程已经有了缓冲区，当它醒来时就有机会做足够的处理，从而释放该缓冲区以及可能的其他资源。它释放的资源越多，其他进程的运气就会越好，不用挤在那里等待资源。•其次，一个等待自由缓冲区的进程，可能正在等待由一个等待I/O完成的进程所占用的缓冲区。•2.内核调整从核心态返回到用户态的进程的优先权。•3.时钟处理程序以1秒钟的间隔调整用户态下的所有进程的优先权，并使内核运行调度算法防止某个进程垄断CPU的使用。•在一个进程的时间片中，时钟可能使它中断若干次，每次时钟中断时，时钟处理程序都要使该进程表中的一个字段增值。该字段记录了该进程的最近CPU使用时间。•时钟处理程序每秒一次地根据一个衰减函数来调整每个进程的最近CPU使用时间：•decay(CPU)=CPU/2•当时钟处理程序重新计算最近CPU使用时间时会重新计算在“被抢先”和“就绪”状态下的每个进程的优先权。•priority=(“recentCPUusage”/2)+(baseleveluserpriority)•优先权值最近CPU使用时间基级用户优先权值•优先级数越低，优先权越高。内核试图每秒一次计算所有活动进程的优先权，这个时间间隔可以稍有变化：当内核正在执行一段临界区代码时，如果时钟中断已经到来，内核并不重新计算优先权，因为那会使内核在临界区呆的时间过长。每个进程中访问临界资源的那段代码称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。8.1.3进程调度的例子初始优先数是60，时钟每秒中断系统60次CPU使用时间衰减值：CPU=decay(CPU)=CPU/2进程的优先数：priority=（CPU/2）+60内核可能会先于进程B而调度进程A，因为进程A在“就绪”状态的时间较长。这是对具有相同优先权的进程进行调度的原则。8.1.4进程优先权的控制•利用系统调用nice，进程可以自然地实行对它们的调度优先权的控制：•nice（value）•value被加到进程优先权值的计算公式中：•priority=（“recentCPUusage”/constant）+(basepriority)+(value)•系统调用fork，进程继承父进程的nice值。•nice仅作用于正在运行的进程，一个进程不能设置另一个进程的nice值。•只有超级用户才能提供提高进程优先权的nice值。•普通用户调用nice来降低他们进程优先权，对其他用户友好，故名nice。•nice值范围是[-20,19]，默认值是0。8.1.5公平共享调度•上述调度算法对不同类型的用户不做区分，不可能将CPU时间分一半给一组特殊的进程。•公平共享调度的原则是将用户团体分为一些公平共享组。每组成员相对于组中其他进程而言，受到常规进程调度的限制。公平共享组优先权•计算进程优先权值时加入“公平共享组优先权”。•每个进程在其u区有一个新字段，指向一个公平共享cpu使用字段，由该公平共享组中所有进程共享。•时钟中断处理程序就像它增加运行进程的cpu使用字段一样，增加运行进程的公平共享cpu使用字段，并每秒一次地衰减所有公平共享组cpu使用字段的值。进程A在一个组，进程B和C在另一个组。内核按A,B,A,C,A,B这样的次序进行调度。在第一组中的进程所得到的cpu时间是第二组中的进程的两倍。8.1.6实时处理•实时处理指的是对外部事件进行立即响应，在该事件发生后的一个指定时间内，调度指定的进程去运行。•目前还没有标准的UNIX系统具有“提供一种机制来通知内核处理进程的实时要求”这种能力。8.2有关时间的系统调用•stime设置系统日期和时间•stime（pvalue）•pvalue：以秒为单位的长整数时间（从1970年1月1日零点开始），时钟中断程序每秒一次地使该变量加1。•time查询系统时间•time（tloc）•tloc：返回的时间•times给出调用进程在用户态和核心态执行时所花费的累积时间，及它的所有僵死子进程在在用户态和核心态执行时曾花费的累积时间。•times（tbuffer）•structtms*tbuffer•tms含有查询到的时间。times返回“从过去的一个任意时刻”开始所经历的时间，通常是系统初启的时间。使用系统调用times的程序•一个进程创建了10个子进程，每个子进程循环10000次。•如果一个子进程已经终止，并且是一个僵死进程，则wait立即返回并取得该子进程的状态，否则wait使其调用者阻塞直到一个子进程终止。如调用者阻塞而且它有多个子进程，则在其一个子进程终止时，wait就立即返回。•因为wait返回终止子进程的进程ID，所以它总能了解是哪个子进程终止了。系统调用alarm来设置闹钟软中断信号。stat通过文件名fliename获取文件信息，保存在buf所指的结构体中。structstat{time_tst_atime}最后一次使用时间GIGALRM在用alarm函数设置的计时器超时时会产生此信号。•利用系统调用alarm来设置闹钟软中断信号。•程序每分钟检查一次一个文件的存取时间，如果文件被访问过，则打印出一条信息。•调用stat函数报告该文件上次被访问的时间，如果在上一分钟内文件被访问过，则打印出一条信息。•调用signal捕获闹钟信号，调用alarm来安排每60秒一次的闹钟信号，调用puase挂起它的活动，直到收到一个信号。•60秒后，闹钟信号响起，内核设置该进程的用户栈来调用信号捕获函数wakeup，该函数返回到pause之后的代码，从而，进程再次循环。8.3时钟8.3.2系统的内部定时•callout表：•用户不能直接控制callout表的表项，其由各种内核算法创建。•表项按照各自的“启动时间”进行排序。•各表项的时间字段记录的是前一表项启动后，到该表项被启动时的时间量。•对表中某一给定表项，其总的启动时间是从启动表中的第一项直到该表项的时间的总和。函数a的表项的时间字段为-2，意味着a在有资格被调用之后，系统已经过去了2个时钟中断的时间。•时钟中断处理程序在每次时钟中断时，检查callout表中是否有表项。•如果有，使第一个表项的字段减1.，相应的其他表项的时间字段也会减1.•如果表中第一项的时间字段小于或等于0，就调用对应函数。•如果该函数的运行时间超过一个时钟滴答，下次的时钟中断（以及所有其他发生的中断）就会被屏蔽掉。•时钟中断处理程序通过引起一个“软件中断”来调度该函数。软件中断的优先级比其他中断的优先级低。•在内核准备好调callout表中的某个函数时刻和软件中断发生的时刻之间，许多中断，包括时钟中断都可能发生。因此，callout表中第一项的时间字段可能被减为负值。•当软件中断发生时，中断处理程序清除时间字段已经过时的callout表项，并调用相应函数。8.3.3直方图分析•内核直方图分析给出了一种确定系统在用户态的执行时间与核心态执行时间之比，以及内核执行内核中各个子程序所花费的时间的度量方法。•直方图分析程序有一个用于采样的内核地址表，表中通常含有内核函数的地址。进程事先通过写直方图驱动程序来装入这些地址。•在允许内核进行直方图发分析时，时钟中断处理程序调用直方图驱动程序的中断处理程序，首先确定处理机是处于核心态还是用户态：•核心态：对应于程序计数器的一个内部计数器加1•用户态：用户执行计时器加1图中给出的是几个假象的内核子程序的地址，内核在用户态花费20%时间，在bread算法花费50%时间。由于内核不能中断临界区代码，不能在那里调用直方图中断处理程序。必须有保留地对待内核直方图分析结果。•用户可以在用户级使用系统调用profil来对进程的执行做统计。•profil（buff，bufsize，offset，scale）•buff是用户空间中的一个数组的地址，bufsize是该数组的大小，offset是一个用户子程序（通常是第一个）的虚地址，scale是将用户虚地址映射到数组中时使用的一个因子。•16进制0xffff给出程序计数器与buff中的字的一对一映射。8.3.4记账和统计•内核对每个处理机状态都保持一个内部计数值，在每个时钟中断期间，修改这些计数值，几下机器当前状态。•每个进程在u区都有字段，记录所消耗的内核时间和用户时间，记录内存使用情况。•如果一个进程和其他4个进程共享50k字节正文区，并使用25k数据区和40k字节栈区，内核按该进程使用了75k（50/5+25+40）字节的内存空间收费。8.3.5计时