一、线程调度 schedule
在操作系统中，调度器（Scheduler）的主要任务是管理CPU的时间分配给各个进程和线程，以优化特定的性能指标，如响应时间、吞吐量和CPU利用率。调度器通常分为三类：长期调度器、中期调度器和短期调度器，但在现代操作系统中，最常讨论的是短期调度器，即CPU调度器。下面是几种常见的调度算法：
1. 先来先服务（FCFS，First-Come, First-Served）
- 概念：最简单的调度算法，按照进程到达的顺序进行调度。
- 优点：简单易实现。
- 缺点：对于长任务可能导致短任务等待时间过长，不利于交互式任务。
2. 短作业优先（SJF，Shortest Job First）
- 概念：优先调度预计执行时间最短的进程。
- 优点：最小化平均等待时间，非常有效率。
- 缺点：需要预知进程的执行时间，实现复杂，可能导致长作业饥饿。
3. 最短剩余时间优先（SRTF，Shortest Remaining Time First）
- 概念：抢占式版本的SJF，如果新到达的进程有更短的剩余时间，则当前进程被挂起。
- 优点：响应速度快，有效地处理了短作业。
- 缺点：同样需要预知进程的执行时间，长任务可能遭受饥饿。
4. 时间片轮转（RR，Round Robin）
- 概念：每个进程分配一个固定的时间片，用完时间片后，如果进程尚未完成，则被放回队列末尾。
- 优点：响应时间快，适合交互式系统，所有进程得到公平处理。
- 缺点：时间片的大小选择对系统性能有显著影响。
5. 优先级调度（Priority Scheduling）
- 概念：每个进程分配一个优先级，高优先级的进程先执行。
- 优点：可以根据进程的重要性和紧急性来调度。
- 缺点：低优先级的进程可能遭受饥饿，需要额外的机制如老化（增加等待进程的优先级）来处理。
6. 多级队列（Multilevel Queue）
- 概念：将进程根据类型分配到多个队列，每个队列有自己的调度算法。
- 优点：可以根据进程类型优化调度，实现更细致的资源控制。
- 缺点：维护多个队列增加了调度的复杂性。
7. 多级反馈队列（Multilevel Feedback Queue）
- 概念：多级队列的改进，允许进程在队列间移动，以更动态地反映进程的需要和行为。
- 优点：结合了多种调度策略的优点，更灵活，可以适应进程的变化。
- 缺点：算法最复杂，参数调整困难，需要仔细配置以达到最佳性能。、
二、window 和 Linux 的对应thread schedule
Windows和Linux操作系统使用了不同的调度策略来管理进程和线程的执行，以适应它们各自的设计目标和应用场景。以下是这两个操作系统在进程和线程调度方面的一些主要策略和算法：
1) Windows 调度器
Windows操作系统使用的是基于优先级的抢占式调度算法，具体称为多级反馈队列调度（Multilevel Feedback Queue Scheduling）。这种算法非常适合于多任务环境，特别是在图形用户界面和交互性强的应用程序较多的情况下。
核心特点：
- 优先级级别：Windows定义了32个优先级级别，从0到31，其中0级为最低，31级为实时级别。系统进程通常运行在高优先级，而用户进程则在较低优先级。
- 抢占式调度：高优先级的线程总是会抢占低优先级线程的执行。只有当没有更高优先级的线程就绪时，当前运行的线程才能继续执行。
- 动态优先级调整：为了防止优先级反转和饥饿问题，Windows会根据线程的行为动态调整其优先级。例如，对于长时间等待I/O操作的线程，系统可能会暂时提升其优先级。
2) Linux 调度器
Linux操作系统中，调度策略经历了多次迭代和改进。从2.6内核版本开始，主要采用的是完全公平调度器（Completely Fair Scheduler，CFS）。CFS的目标是尽可能公平地分配CPU时间给每个运行的进程，以优化系统的响应时间和性能。
核心特点：
- 时间片：CFS不使用固定的时间片长度，而是基于所谓的“虚拟运行时间”的概念，该时间是动态计算的。每个进程获取的CPU时间与其权重成比例。
- 红黑树：CFS使用一种数据结构称为红黑树（红黑树是一种自平衡二叉查找树）来维护所有可运行的进程队列。每个进程的节点包含了其虚拟运行时间。
- 公平性：调度的决策基于进程的虚拟运行时间，意图是让每个进程获得公平的CPU时间。系统会选择虚拟运行时间最少的进程作为下一个运行的进程。
a) target latency
Linux 的完全公平调度器（CFS）确实使用了一个概念称为“目标延迟”（target latency），这是用来确定每个进程应该获得的公平时间片的长度。目标延迟是CFS的一个核心参数，它有助于调度器决定多长时间重新评估并调整进程的优先级，以保持调度的公平性。
目标延迟（Target Latency）
在CFS中，目标延迟是定义调度周期长度的一个重要参数，即系统尝试在该时间窗内运行所有可运行的任务各一次。目标延迟的总长度通常取决于系统上运行的可调度任务的数量。如果任务数量增多，为了保持每个任务在给定周期内都能被调度到，系统可能会缩短单个任务的时间片，但整体调度周期保持不变。
时间片的计算
在CFS中，并没有固定的时间片长度。相反，每个进程分配的时间片是动态计算的，基于目标延迟和系统上活动进程的数量。时间片的计算公式大致如下：
时间片=目标延迟活动进程的数量\text{时间片} = \frac{\text{目标延迟}}{\text{活动进程的数量}}时间片=活动进程的数量目标延迟
这意味着，如果系统中运行的进程数量增加，每个进程获得的时间片会相应减少，从而所有进程都有机会在目标延迟期间运行，保持调度的公平性。
目标延迟对系统的响应性有显著影响：
- 较短的目标延迟 可以提高系统的响应性，因为调度器更频繁地重新评估进程优先级，这对于交互式任务非常有利。
- 较长的目标延迟 可能提高了系统的吞吐量，因为减少了上下文切换的频率，但可能会牺牲一定的响应性。
Linux操作系统通过CFS的这种设计，试图在吞吐量、响应时间和公平性之间达到平衡，适应各种不同的工作负载和系统需求。这种基于目标延迟和动态时间片计算的方法，使得Linux调度器能够灵活地应对多种运行环境，特别是在多核处理器普遍存在的今天，这种调度策略显得尤为重要。
- 响应性 vs. 公平性：Windows的调度策略更侧重于快速响应用户的交互操作，而Linux的CFS则更侧重于在多任务处理中实现长期的公平性和效率。
- 优先级调整：Windows明显依赖于优先级制度，对线程优先级进行动态调整以处理不同场景，而Linux通过调整虚拟运行时间来尝试达到公平的CPU时间分配。
三、组织调度队列的问题
在多核CPU系统中，进程和线程调度的策略可以大大影响系统的整体性能和效率。尤其是在如何组织调度队列的问题上，存在两种主要的方法：单个全局队列和每个核心一个独立队列。这两种策略各有优势和局限，适用于不同的场景和需求。
多核CPU单个全局队列
在这种策略中，系统维护一个全局的调度队列，所有的CPU核心从这个队列中获取要执行的任务。调度器负责将任务分配给各个核心，尝试保持负载均衡并减少某个核心的空闲时间。
优点
- 简化的调度决策：因为只有一个队列，调度逻辑相对简单，容易实现。
- 全局优化：调度器可以全局观察所有待执行的任务，从而做出更优的调度决策，尤其是在任务负载相对均匀时。
缺点
- 潜在的性能瓶颈：所有核心访问同一个队列可能导致竞争和锁的问题，特别是在高负载时。
- 缓存一致性问题：任务在不同核心间迁移可能导致更频繁的缓存失效，影响性能。
多核CPU每个核心一个独立队列
每个CPU核心或每个核心组拥有一个独立的调度队列。每个队列独立管理分配给该核心的任务，调度器根据核心的负载和特性分配任务。
优点
- 减少锁竞争：由于每个核心管理自己的队列，减少了多个核心之间的锁竞争，提高了系统的扩展性。
- 优化局部性：任务更可能在同一个核心上连续运行，利用局部性原理，减少了缓存失效的情况，提高了效率。
缺点
- 负载不均可能性：如果任务不均匀分配，一些核心可能高负载而其他核心空闲，需要更复杂的负载均衡机制。
- 调度复杂性增加：需要更复杂的算法来决定任务分配到哪个队列，同时还要处理核心间的负载均衡问题。
选择哪一种调度策略取决于具体的应用场景、性能需求和系统架构。例如，对于需要高响应性和高局部性的实时或游戏应用，每核独立队列可能更合适；而对于负载相对均匀的通用应用，单一全局队列可能足够高效且易于管理。在现代操作系统如Linux中，通常会采用更复杂的混合调度策略，结合全局队列和局部队列的优势，以达到最优的性能和负载均衡。
四、多线程合作
在多核或多线程的计算环境中，线程的合作是提高程序性能和资源利用率的关键。"Space"和"Gang"是两种描述线程协作模式的术语，它们代表不同的并行处理策略：
1. Space Cooperation
"Space"在这里指的是多线程间在执行时空间上的协作，这通常涉及到数据分割（data partitioning）和工作分配（work distribution）。在这种模型中，每个线程或者处理器核心被分配到一个独立的任务或数据集上，各自负责处理其对应部分的计算。
- 数据并行性：适合于处理大规模数据集的应用，如向量和矩阵运算，在这些操作中数据可以被自然地分割并并行处理。
- 可扩展性：增加更多的处理器或线程可以直接提高处理能力，因为每个新增的单元都增加了处理能力。
- 实现简单：相比于其他并行模型，数据分割通常更容易实现和管理。
2. Gang Cooperation
"Gang"则是一种紧密协作的线程组模型，在这种模式下，所有的线程作为一个团队（"Gang"）一起工作，共同完成一个更大的任务。每个线程可能执行相同的代码，但在不同的数据集上，或者线程间可以有不同的角色和功能，共同协作处理复杂的任务。
- 功能并行性：适合于复杂的应用程序，其中不同的线程可能承担不同的处理角色。
- 同步要求高：线程间需要频繁的通信和同步，以确保协作的效率和正确性。
- 效率依赖于协调：如果线程间的协调做得好，可以极大提高效率；否则，过多的同步和等待可能会降低性能。
在设计和实现这两种合作模型时，开发者需要考虑多个因素：
- 负载均衡：确保每个线程或核心获得适量的工作负载，避免某些线程过载而其他线程空闲。
- 数据依赖性：处理好数据之间的依赖关系，尤其是在"Gang"模式中，不同线程可能需要访问和修改共享数据。
- 硬件特性：考虑目标硬件的特性，如内存访问模式、缓存一致性问题等，合理设计线程的工作方式和数据布局。
这两种模式可以单独使用，也可以组合使用，取决于具体应用的需求和性能目标。在现代软件开发中，多线程和多核心处理器的广泛应用使得对这些并行模型的理解和掌握变得尤为重要。
标签：优先级,操作系统,schedule,队列,调度,线程,进程,时间 From： https://blog.csdn.net/m0_74209411/article/details/143471647