2023年7月3日发(作者：)

操作系统-CPU调度CPU调度 (CPU scheduling)：多个进程同时处于内存，当⼀个进程必须等待时，OS从该进程拿⾛CPU使⽤权交给其他进程。进程执⾏从⼀个IO区间(I/O burst)开始，随后进⼊⼀个CPU区间(CPU burst)并反复，进程循环地在CPU执⾏和I/O等待两个状态间切换，直到通过系统请求终⽌最后⼀个CPU burst。CPU burst的长度随进程和计算机的不同⽽变化，通常具有⼤量短CPU burst和少量长CPU burst。I/O约束程序通常具有很多短CPU burst，CPU约束程序可能有少量长CPU burst。

每当CPU空闲时，OS就使⽤短期调度程序(short-term scheduler) （或CPU scheduler）从就绪队列中选择⼀个能够执⾏的进程并为它分配CPU。就绪队列不⼀定是FIFO队列。就绪队列中的记录通常为PCB。

抢占&⾮抢占CPU调度决策发⽣在4种情况下：1) 进程从运⾏(running)状态切换到等待(waiting)状态；2) 进程从运⾏(running)状态切换到就绪(ready)状态；3) 进程从等待(waiting)状态切换到就绪(ready)状态；4) 进程终⽌⾮抢占(nonpreemptive)调度⽅案：a.k.a. 协作(cooperative)调度⽅案，⼀旦CPU分配给⼀个进程，该进程会⼀直使⽤CPU直到进程终⽌或切换到等待状态，该⽅案中调度只发⽣在1、4两种情况下。否则称为抢占(preemptive)调度⽅案。

分派程序分派程序(dispatcher)：每次进程切换时都要使⽤的⼀个模块，⽤于将CPU控制交给由short-term scheduler 所选的进程。功能包括1)切换上下⽂；2)切换到⽤户模式；3)跳转⽤户程序的合适位置来重启程序。分派延迟(dispatch latency)：dispatcher停⽌⼀个进程并启动另⼀个进程所⽤的时间。

调度准则⽤于分析⽐较CPU调度算法的准则可包括·CPU使⽤率(CPU utilization)：理论上为0%~100%，真实系统⼀般为40%~90%。·吞吐量(Throughput)：⼀个时间单位内所完成进程的数量。·周转时间(Turnaround time)：⼀个进程从提交到完成的所⽤时间。·等待时间(Waiting time)：进程在就绪队列中等待所⽤时间之和。·响应时间(response time)：从提交请求到产⽣第⼀响应的所⽤时间。需要使CPU utilization和throughput最⼤化，turnaround time、waiting time和response time最⼩化。绝⼤多数情况下需要优化平均值，有些情况下需要优化最⼤值、最⼩值或responsetime⽅差等。

调度算法FCFS （最简单，但会让短进程等待时间⾮常长）先到先服务调度算法(first-come, first-served (FCFS) scheduling algorithm)：先请求CPU的进程先分配到CPU，通常⽤FIFO队列实现。 [nonpreemptive]FCFS策略平均等待时间通常较长，不适⽤于time-sharing系统。护航效果(convoy effect)：所有其他进程都等待⼀个⼤进程释放CPU，相⽐让较短进程最先执⾏的情况，CPU和设备的使⽤率更低。

SJF （提供最短平均等待时间）最短作业有限调度算法(shortest-job-first (SJF) scheduling algorithm)：每个进程与其下⼀个CPU burst关联。当CPU空闲时，将它分配给具有最短CPU burst的进程。[preemptive ornonpreemptive]更适当的术语表⽰应该是 “the shortest-next-CPU-burst algorithm”，命名为SJF主要是因为惯例。难点：如何知道下⼀CPU burst的长度。1) 对于（batch system中的）long-term job scheduling，可将⽤户提交job时所指定的process time limit作为长度。2) 对于short-term CPU scheduling，下⼀CPU burst的长度⽆法知道。可对下⼀CPU burst长度进⾏预测，选择具有最短预测CPU burst的进程。下⼀CPU burst通常预测为以前CPU burst区间测量长度的指数平均(exponential average)。τn+1 = αtn + (1-α) τn

tn –

第n个CPU burst的长度（记录最近信息）；τn –

第n个CPU burst的预测值（记录过去历史）；τn+1 –

下⼀CPU burst的预测值；α –

控制最近和过去历史在预测中的相对加权，0≤α≤1。preemptive的SJF调度 – 最短剩余时间优先调度(shortest-remaining-time-first scheduling)，如果到达就绪队列的新进程有⽐当前运⾏进程更短的CPU burst，可抢占CPU。Nonpreemptive的SJF调度 – 允许当前运⾏的进程先完成。

优先级调度优先级调度算法(priority scheduling algorithm)：每个进程都与⼀个优先级(priority)关联，CPU被分配给具有最⾼priority的进程，相同priority的进程按FCFS顺序调度。[preemptive ornonpreemptive]SJF是优先级调度的⼀个特例，其priority为下⼀CPU burst的倒数。Priority通常为固定区间的数字，有的系统⽤⼩数字表⽰低priority，有的系统则⽤⼩数字表⽰⾼priority。Priority可通过内部或外部定义。内部priority通过对进程的测量数据（e.g. 时间极限、内存要求、打开⽂件数量、平均I/O burst和平均CPU burst之⽐）计算来定义；外部priority通过OS之外的准则（e.g. 进程重要性、使⽤计算机的费⽤类型和数量、赞助单位等因素）。Preemptive的priority调度 – 如果到达就绪队列的新进程有⽐当前运⾏进程更⾼的priority，可抢占CPU。Nonpreemptive的priority调度 – 将新进程加到就绪队列的头部。优先级调度和SJF调度会产⽣饥饿，可⽤⽼化技术解决。Problem – ⽆穷阻塞（indefinite blocking）/饥饿（starvation）：某个低priority进程可能会⽆穷等待CPU。Solution — ⽼化（aging）：逐渐增加在系统中等待很长时间的进程的priority，使得最终该进程拥有最⾼priority并能执⾏。

RR （适合分时/交互系统）时间⽚(time quantum, a.k.a. time slice)：⼀个较⼩的时间单元，通常为10~100ms。轮转法调度算法(round-robin (RR) scheduling algorithm)：专门为time-sharing系统设计，CPU调度程序循环就绪队列，为每个进程分配不超过⼀个time quantum的CPU。[preemptive]实现CPU调度程序每次从FIFO就绪队列中选择第⼀个进程，设置定时器在⼀个time quantum后终端，再dispatch该进程。1)

如果当前运⾏进程的CPU burst短于time quantum，则CPU由进程⾃动释放，调度程序再处理下⼀个进程；2)

如果当前运⾏进程的CPU burst长于time quantum，则到点后定时器向OS发送中断，执⾏上下⽂切换，进程被加⼊到就绪队列尾部，CPU调度程序再处理下⼀个进程。（被抢占）采⽤RR的平均waiting time通常较长。主要问题：选择时间⽚。RR算法的性能⾮常依赖于time quantum的⼤⼩。如果time quantum太⼤，则与FCFS⼀样；如果time quantum很⼩，则因上下⽂切换⽽引起的调度开销过⼤。Time quantum应该⽐context switch时间长。处理器共享(processor sharing)：如果time quantum很⼩，则RR可产⽣“n个进程都有它⾃⼰的处理器，各⾃速度都为真正处理器速度的1/n”的效果。

多级队列调度（允许多个不同算法⽤于各种类型的进程）多级队列调度算法(multilevel queue scheduling algorithm)：将就绪队列划分成多个独⽴队列，每个队列有⾃⼰的调度算法。进程根据⾃⾝属性被永久分配到对应的⼀个队列。常⽤模型：前台交互队列使⽤RR，和后台批处理队列使⽤FCFS。队列之间必须有调度。可采⽤1) 固定优先级抢占调度(fixed-priority preemptive scheduling) – 每个队列相⽐更低层队列有绝对的priority。对于⼀个队列，只有⾼层队列都为空时该队列内进程才可运⾏；如果有新进程进⼊⾼层队列则CPU会被抢占。[通常采⽤]2) 在队列间划分time-slice – 每个队列有固定的CPU时间，在⾃⼰的CPU时间内可调度队列内进程。

多级反馈队列调度对⽐多级队列调度 –允许进程在队列之间移动，相⽐开销更⼤，更灵活。多级反馈队列调度算法(multilevel feedback queue scheduling algorithm)：根据CPU burst的特点区分进程。如果进程使⽤过多CPU时间则转移到更低队列，在低priority队列中等待时间过长的进程可被转移到⾼priority队列（aging的⼀种形式）。可由以下参数定义：1)

队列数量；2)

每个队列的调度算法；3)

⽤于确定何时升级到更⾼priority队列的⽅法；4)

⽤于确定何时降级到更低priority队列的⽅法；5)

⽤于确定进程需要服务时应进⼊哪个队列的⽅法。e.g.队列0中，不能在8ms内完成的进程会被抢占，移到队列1尾部；队列1中，不能在16ms内完成的进程会被抢占，移到队列2尾部；只有队列0和1为空时，队列2内进程才可根据FCFS运⾏。

多处理器调度(multuiple-processor scheduling)同构(homogeneous)：processor功能相同。同构系统中，可将任何processor⽤于运⾏队列中的任何进程。当前许多计算机都⽀持multiprocessing，并允许每个processor独⽴调度⾃⼰。通常每个processor维护⾃⼰私有的进程或线程队列。多处理器调度的⽅法1) ⾮对称多处理(asymmetric multiprocessing)⽅法：让单独的⼀个processor (master server) 处理所有调度决策、I/O处理和其他系统活动，其它processor只执⾏⽤户代码。（简单，只有⼀个processor访问系统数据结构，减轻数据共享的需要）2) 对称多处理(symmetric multiprocessing, SMP)⽅法：每个processor是self-scheduling的，每个processor检查就绪队列并选择⼀个进程来执⾏。（所⽤进程可能处于⼀个共同的就绪队列中，或每个processor都有私有的就绪队列。）在绝⼤多数⽀持SMP的当代操作系统中，每个processor都有私有的就绪队列。⼏乎现代操作系统都⽀持SMP。

处理器亲和性处理器亲和性(Processor affinity)：进程对其运⾏所在的processor的亲和性，尽量使⼀个进程在同⼀个processor上运⾏，避免将进程在processors之间迁移。由于在processors之间迁移进程的代价(1. 使原processor的cache⽆效 2. 重新构建新processor的cache)⾼，⼤多数SMP系统都具有processor affinity。优点：进程可以利⽤它在原processor的cache中的数据。Processor affinity通常有两种形式：软亲和性(soft affinity)：OS具有让⼀个进程保持在同⼀个processor上的运⾏策略，但不能做任何保证，进程有可能移动。硬亲和性(hard affinity)：允许进程指定它不能迁移⾄其他processor上。E.g. Linux提供

负载平衡负载平衡(Load balancing)：设法将⼯作负载平均分配到SMP系统的所有processor上。对于“拥有⾃⼰私有的就绪队列”的processor来说是必需的，“具有共同就绪队列”的系统通常不需要。Load balancing通常有两种⽅法：Push migration：⼀个特定的task周期性地检查每个processor上的负载，如果发现不平衡就把进程从过载的processor push到空闲或不太忙的processor上。Pull migration：空闲的processor从忙碌的processor上pull⾛⼀个waiting task。Push migration和pull migration可以并⾏实现，不需要互斥。e.g. Linux scheduler, ULE scheduler for balancing通常会抵消掉processor affinity的好处，关于何种⽅式更好并没有绝对的规则。有些系统中只有当不平衡达到⼀定额度后才会移动进程。

SMT

对称多线程(Symmetric multithreading, SMT)：提供多个logical processors来实现多线程同时运⾏的策略。在intel processors中也称为超线程(hyperthreading)技术。

SMT在同⼀physical processor上⽣成多个logical processor，向OS呈现⼀个“多个logical processors”的视图。

每个logical processor都有⾃⼰的架构状态(architecture state)，包括general-purpose和machine-state registers。

每个logical processor负责⾃⼰的中断处理。SMT是由硬件（⽽不是软件）提供的。硬件应提供每个logical processor的架构状态的表⽰以及中断处理⽅法，OS不需要特殊设计。

线程调度(Thread Scheduling)对于⽀持多线程的OS，OS调度的是内核线程，⽽不是进程。竞争范围⽤户线程和内核线程所⽤调度⽅法的不同进程竞争范围(Process-contention scope, PCS)：在实现多对⼀或多对多模型的系统中，线程库调度⽤户级线程到可⽤的LWP上。i.e. CPU竞争发⽣在“属于相同进程的线程”之间。系统竞争范围(System-contention scope, SCS)：OS将内核线程调度到物理CPU上，该竞争发⽣在OS的所有线程中。采⽤⼀对⼀模型的OS的线程调度只采⽤SCS。PCS通常根据priority来完成调度 [preemptive] ，但在具有相同priority的线程间并不保证有time slicing。

Pthread线程调度POSIX Pthread API允许在线程⽣成中指定是PCS或SCS。竞争范围值PTHREAD_SCOPE_PROCESS表⽰“采⽤PCS调度”，PTHREAD_SCOPE_SYSTEM表⽰“采⽤SCS调度”。函数pthread_attr_setscope(pthread attr_t *attr, int scope)、pthread_attr_getscope(pthread_attr_t *attr, int *scope) ⽤于获取及设置竞争范围。某些OS只允许特定的竞争范围值。E.g. Linux, Mac OS X只允许PTHREAD_SCOPE_SYSTEM。

OS实例对于⽀持内核级线程的OS，必须调度线程（⽽不是进程）来执⾏。以下3种OS通常偏爱交互进程⽽不是批处理进程或CPU-bound进程。Solaris的内核线程调度（抢占、基于优先级、⽀持实时线程）传统Solaris使⽤多对多模型，Solaris 9使⽤⼀对⼀模型。Solaris按照优先级排序有4种调度类型： 实时(real time)、系统(System)、分时(Time sharing)和交互(Interactive)，每种类型有不同的priority和调度算法。Scheduler将特定类的priority转换为全局priority，再选择全局priority最⾼的线程来执⾏，直到该线程阻塞、⽤完time quantum或被更⾼priority的线程抢占。如果多个线程的priority相同，则采⽤循环队列。Solaris 9引⼊2种新的调度类型：1) 固定优先级(fixed priority) – 线程的priority与time sharing类型范围相同，但不能动态调节。2) 公平共享(fair share) – ⽤CPU shares代替priority来做调度决策。CPU shares：表明可⽤CPU资源的权利，并被分配到⼀个project(进程集)。

Time sharing类(默认调度类型)和Interactive类采⽤同样的调度策略(多级反馈队列)，Priority和time quantum默认成反⽐。通常Interactive进程的priority更⾼，CPU-bound进程的priority更低。Interactive和time sharing类包括60个优先级，在其调度中：时间⽚到期(Time quantum expired)（i.e. ⽤完其time-quantum⽽未堵塞）的线程将被认为是CPU-intensive的，并被降低优先级。从睡眠中返回(Return from sleep)（e.g. 从等待I/O中返回）的线程优先级将被提⾼。

System类专门保留给内核使⽤，⽤于运⾏内核进程。System进程⼀旦创建，其priority就不再改变。（在内核模式下运⾏的⽤户进程并不属于system类。）Real time类的进程具有最⾼priority，能在其他类型进程之前运⾏。通常只有少数进程属于real time类。

Windows XP的内核线程调度（基于优先级、抢占、⽀持实时线程）Dispatcher：Windows XP内核中⽤于处理调度的部分。（应该与前⾯所介绍的分派程序dispatcher不同）Dispatcher选择priority最⾼的线程来执⾏，直到该进程被更⾼priority的进程抢占、终⽌、⽤完time quantum或调⽤了blocking system call。Dispatcher使⽤32级priority⽅案，priority分为两⼤类型： Priority 0的线程⽤于内存管理Priority 1~15的线程属于可变类型(variable class)，此类线程的priority可以改变。Priority 16~31的线程属于实时类型(real-time class)Dispatcher为每个priority使⽤⼀个队列，并从⾼到低检查队列集，直到发现⼀个可以执⾏的线程。如果没有找到，则执⾏⼀个称为空闲线程(idle thread)的特别线程。

Win32 API定义了进程可能属于的priority类型：1) REALTIME_PRIORITY CLASS2) HIGH_PRIORITY_CLASS3) ABOVE_NORMAL_PRIORITY_CLASS4) NORMAL_PRIORITY_CLASS5) BELOW_NORMAL_PRIORITY_CLASS6) IDLE_PRIORITY_CLASS其中，REALTIME_PRIORITY_CLASS属于real-time class，其它类型属于variable class。进程通常属于NORMAL_PRIORITY_CLASS，除⾮其⽗进程为IDLE_PRIORITY_CLASS或在创建该进程时指定其他类型。每个线程的priority都基于其所属priority类型和它在该类型中的relative priority。Relative priority的值包括：1) TIME_CRITICAL2) HIGHEST3) ABOVE_NORMAL4) NORMAL5) BELOW_NORMAL6) LOWEST7) IDLE 基础优先级(base priority)：每个线程都有的⼀个（在其所属类型范围内的）priority值，默认为该类型中relative priority为NORMAL的值。线程的priority初始值通常为所属进程的base priority。

线程的time quantum⽤尽时将被中断，如果该线程属于variable class则其priority将降低，但绝不会低于其base priority。当属于variable class的线程被从等待操作中释放时，其priority将提升（提升多少取决于该线程等待的是什么）。e.g. 等待I/O⽐等待磁盘操作得到的提升更⼤，缩短交互线程的响应时间。为了给交互程序的进程提供优秀的性能，Windows XP对NORMAL_PRIORITY_CLASS的进程有⼀个特别调度规则 – 区分前台进程和后台进程，当进程进⼊前台时增加其time quantum的倍数（通常为3）。

Linux内核调度（基于优先级，抢占、提供实时⽀持）（Linux不区分进程和线程，使⽤task。）2.5版本前运⾏传统UNIX算法，存在问题：1) 对SMP系统没有提供⾜够⽀持 2) tasks数量增加时⽆法按⽐例调整。2.5版本提供了O(1)的调度算法和对SMP的⽀持。Linux两个独⽴的priority range：Real-time (0~99)：被分配静态priority。Nice (100~140)：具有动态priority，根据task的交互性决定+5还是-5。（交互性更强的任务通常-5，使priority更⾼）这两个ranges映射到global priority，数值越低priority越⾼。Linux中分配给task的time quantum与priority成反⽐。（与Solaris、Windows XP相反）

runque：内核所维护的⼀个数据结构，记录可运⾏tasks的列表。每个runque包括两个priority arrays，每个priority array都有⼀个根据priority索引的tasks列表。Active array包括所有在time quantum中还有剩余的tasks；Expired array包括所有已到期（耗尽time quantum）的tasks。因为⽀持SMP，每个processor都需维护⾃⼰的runque并⾃⾏调度。调度时，从active array中选择priority最⾼的task来在CPU上执⾏。Task到期被移⾄expired array后将重新计算动态优先级。当所有tasks都到期（I.e. active array为空）时，两个array互换。

调度算法评估分析评估法(analytic evaluation)：评估算法的⼀种主要⽅法，使⽤给定算法和系统负荷产⽣⼀个公式或数字来评估算法在该负荷下的性能。（使⽤数学分析）确定模型确定模型法(deterministic modeling)：analytic evaluation的⼀种。使⽤预先确定的特定负荷，计算每个算法在该负荷下的性能。主要⽤于描述调度算法和提供例⼦。缺点：要求输⼊精确数字，并且答案只适⽤于给定情况。

排队模型对于许多系统，进程集合并不是静态的但可以通过测量CPU burst分布和进程到达系统的时间分布来估计进程的到达率(arrival rates)和CPU的服务率(service rates)。排队⽹络分析(queueing-network analysis)：CPU可看做具有⼀个等待进程队列的服务器，从进程的到达率和服务率可计算CPU使⽤率、平均队列长度、平均等待时间等。主要⽤于⽐较调度算法。缺点：队列模型只是现实系统的近似，难以处理复杂算法或分布。Little formula: (可⽤于根据3个变量中的2个来计算另外1个)n – 平均队列长度； W – 队列平均等待时间；