| 详解操作系统内核对线程的调度算法 | 您所在的位置：网站首页 › 内核级线程调度 › 详解操作系统内核对线程的调度算法 |
详解操作系统内核对线程的调度算法
|
操作系统内核对线程的调度非常有意思，因为他的一系列思想和方法论都能从生活和业务开发中找到影子，比如： 超市收银台会分多个收银通道，快速通道针对那些提篮子的客户，慢速通道针对那些推购物车的客户，从而减少提篮子客户的付款等待时间，设想一下，若某个客户只买了几件物品，但是不巧正好排到了购买了一车物品的客户后面，他的购物体验就会差一些。银行营业厅的叫号系统，他会按照VIP客户、普通客户分出多个号段的排队序号，VIP客户的响应速度会快一些，普通客户的响应速度会慢一些。在内容处理系统中，在处理能力一定的情况下，我们也会按照文章来源的不同进行调度处理，优先快速响应高优先级文章的处理。在融合存储系统中，会对不同业务的主机I/O请求设置不同的优先级，优先保证重要业务的I/O性能（并发和延迟）。两个有意思的场景 我们都知道：进程是操作系统进行”资源分配“的基本单位，线程是操作系统进行“调度”的基本单位，从这句话的字面解读，似乎进程和“调度”没有太多关系，但是实际上，内核在进行线程调度的时候会去参照线程是否属于同一个进程（当其他条件都一样的情况下，比如，优先级等）。在业务应用开发中，若涉及线程相关，一般会将Woker线程数目设置为CPU的逻辑核数以便最大限度利用CPU。若没有上面提到的策略，这样的设置实际并没有太多意义（或者说设置更多的线程，从而有提高业务线程被调度的整体次数），因为一台服务器中不可能只存在业务的那几个线程。操作系统提供了通用的调度能力，在某些特殊场景中，我们比操作系统更了解我们的线程该如何在多个CPU核之间进行分配。例如，在数据库系统中，为保证高优先级线程得到快速处理（比如，事务操作）、避免被其他线程中断（分片时间到）或者被迁移到其他CPU核（导致CPU cache失效），会将相关线程与部分CPU核绑定，只留剩余的CPU核参与通用调度分配。操作系统内核对CPU的绝对掌控 在详细谈操作系统内核对线程调度之前，还想提一下最前置的问题，即操作系统能否获得调度的权利，会不会出现CPU核被应用程序长期占用着呢？下面文章有提到，操作系统内核会借助硬件定时器的帮助，重新获得对CPU的控制权，然后按照一系列复杂的调度规则去决定是继续当前线程的执行还是切换到其他线程（可能是其他进程的）。 我这里也写了一个程序试了一下，程序同时开启8个线程，每个线程执行一个死循环的计算逻辑。我的笔记本的CPU型号是：2 GHz 四核Intel Core i7，1个CPU，4个核，因开启了超线程技术，可同时供8个线程并发执行。程序开启后，通过Top命令观看，这个程序的CPU使用率长时间维持在700%左右，我仍然能正常写文章、浏览网页，没有受到丝毫影响。 #include #include void infinite_loop() { int i = 0; for (;;){ ++i; } } // 我的笔记本的CPU型号是：2 GHz 四核Intel Core i7，1个CPU，4个核，因开启了超线程技术，可同时供8个线程并发执行 std::unique_ptr thread_array [8]; int main() { for(int i = 0; i此算法兼顾响应时间（ Responsiveness ）、低调度开销（Schedule overload）、饥饿避免（Starvation-Freedom）、公平（Fairness），在Windows，MacOS，Linux内核调度系统中都有使用。算法内容： 有多个Level，从上到下，优先级越来越低，分片时长越来越大。位于高优先级Level的任务可以抢占低优先级Level的任务。新任务首先位于高优先级Level，当一个时间片用完之后，若任务结束，则正常退出系统，若任务还没有结束，则下滑到低一等级的Level。若是因等待I/O而主动让出CPU处理，则停留在当前Level（或者提高一个Level）。同一Level的任务采用Round Robin算法。为避免系统中有太多的I/O任务而导致计算型任务迟迟得不到处理，MFQ算法会监控每个任务的处理耗时、确保其拥有公平的资源分配（按照最大最小公平算法）。在每个Level的所有任务，若有任务还没有用完分配给他的资源，则相应提高他的优先级，反之则降低其优先级。6、多CPU核场景下MFQ算法的考虑 在多CPU核的场景下，若共用一个MFQ，则会出现： 随着CPU核不断增长，对MFQ锁的争抢会越来越严重。因MFQ的最新状态都是存在上次执行的CPU核的Cache，当前CPU核需要从远端CPU核的Cache去拉取最新数据、然后存到Local Cache，这个行为会很耗时。为解决上述问题，会为每个CPU核分配一个MFQ，同时采用Affinity Scheduling策略，保证同一线程的执行尽量落在同一CPU核（挂起中断后重新执行）。若出现某些CPU核特别繁忙，会进行Rebalancing操作，将部分线程迁移到其他空闲的CPU核执行。线程在同一个CPU核处理可以最大化利用CPU Cache，避免频繁的从内存加载数据到CPU Cache。Golang语言处理多个协程并发的时候，也会尽量保证相关的协程由同一个底层线程进行处理，也是基于重用CPU Cache的因素。 操作系统内核层面的考量上面讲了具体的调度算法，调度粒度是任务（Job），可以映射成线程。那操作系统是不是就是按照上述调度算法对系统中所有的线程进行统一调度呢？篇首也提到了，会考虑进程的因素，即同一进程中的线程。有两个策略会将进程因素考虑进去： Gang Scheduling：尽量将同一进程中的线程同时调度，而不是随机从多个进程挑选内核数目的线程进行调度。 Space Sharing：将CPU核进行划分，若同时有多个进程运行，只让某个进程占用部分CPU核来进行并发，而不是在某一时间分片内所有CPU核被同一个进程的线程占满。 总结操作系统内核的调度系统非常复杂，综合了各种算法和Tradeoff，上面的总结只是一些皮毛，后面再不断增加！ 文章首发于微信公众号【jameswhale的技术人生】 
|
【本文地址】