针对多个程序的SMP CPU调度

针对多个程序的SMP CPU调度

SMP（对称多处理器）: 对称多处理器

SMP服务器的主要功能是共享. 系统中的所有资源（CPU，内存，I / O等）都是共享的. 也正是由于此功能，SMP服务器的主要问题是其扩展能力非常有限. 对于SMP服务器，

当SMP服务器扩展时，每个共享链接都可能导致瓶颈，并且最受限制的是内存. 由于每个CPU必须通过相同的内存总线访问相同的内存资源，所以随着CPU数量的增加，内存访问冲突将迅速增加，

最终将导致CPU资源的浪费，并大大降低CPU性能的有效性. 实验表明，SMP服务器的最佳CPU利用率是2到4个CPU. NUMA（非统一内存访问）: 非统一内存访问

NUMA服务器的基本功能是具有多个CPU模块，每个CPU模块由多个CPU（例如4个）组成，并具有独立的本地内存，I / O插槽等. 因为它的节点可以通过互连模块（例如Crossbar Switch）连接和交换信息，所以

因此，每个CPU都可以访问整个系统内存（这是NUMA系统和MPP系统之间的重要区别）. 显然，访问本地内存的速度将远远高于访问远程内存（系统中其他节点的内存）的速度，这也是非均匀存储访问NUMA的起源. 由于此功能，

为了更好地利用系统性能，在开发应用程序时必须最小化不同CPU模块之间的信息交换.

SMP应用程序

当前的SMP技术主要用于RISC服务器集中的多通道小型计算机，X86服务器集中的多处理系统，并采用虚拟CPU技术来部分实现单CPU（或多CPU）虚拟多处理器. 路径.

我们通常看到的双通道CPU系统是对称多处理系统中最常见的类型之一. 通常称为“ 2通道对称多处理”. 它在普通的商业和家庭应用中很少使用. 实际使用，但是在制作中，例如3DMax Studio，Photoshop和其他软件应用程序都取得了很好的性能，

建立廉价工作站的好伙伴. 随着用户应用程序水平的提高，仅使用单个处理器来满足实际应用的需求确实很困难，因此各种服务器制造商都采用了对称的多处理系统来解决这一矛盾. 在国内市场上，这些型号的处理器通常以4或8为主.

有16个处理器. 但是总的来说，SMP结构机的可扩展性很差，很难实现100个以上的多处理器，常规的通常是8到16个，但这对于大多数用户来说已经足够了. 这台机器的优点是它的使用与计算机或工作站没有太大区别，

编程方面的变化相对较小. 如果要将写在计算机工作站上的原始程序移植到SMP机器上，则修改起来相对容易. 具有SMP结构的模型的可用性相对较差. 由于4个或8个处理器共享一个操作系统和一个内存，因此一旦操作系统出现问题，

整个机器完全瘫痪了. 而且由于该机器的可伸缩性差，保护用户的投资并不容易. 但是，这种模型的技术比较成熟，并且有许多相应的软件. 因此，在国内市场上推出的大量并行机都是这种类型的. PC服务器中最常见的对称多处理系统通常采用2路，

4、6或8个处理器. 目前，UNIX服务器可以支持最多64个CPU的系统，例如SUN的Enterprise10000. SMP系统中最关键的技术是如何更好地解决多处理器的通信和协调问题.

SMP形成条件

构建SMP系统的第一个也是最重要的一点是需要合适的CPU. 我们通常看到的CPU都是单独使用的，因此我们看不到它们之间的区别. 但是，实际上，支持SMP功能并不是无条件的. 您只需花几个CPU进行日常通话就可以构建一个多处理系统.

要实现SMP功能，我们使用的CPU必须具有以下要求:

1，必须在CPU中内置APIC（高级可编程中断控制器）单元. 英特尔多处理规范的核心是使用高级可编程中断控制器（APIC）. CPU通过互相发送中断来完成它们

之间的通讯. 通过将操作添加到中断中，不同的CPU可以在某种程度上相互控制. 每个CPU都有自己的APIC（成为该CPU的本地APIC），并且还有一个I / O APIC来处理由I / O设备引起的中断. 该I / O APIC已安装在主板上，但每个在CPU上

APIC是必不可少的，否则它将无法处理多个CPU之间的中断协调.

2. 相同的产品型号和相同类型的CPU内核. 例如，尽管Xeon和Opteron都具有内置的APIC单元，但它们不可能一起构建SMP系统. 同时，即使它们属于相同的Xeon系列或Opteron系列CPU内核，并且属于相同的开发平台，也无法建立SMP系统多处理器调度，这是因为他

我们的运行说明并不完全相同，APIC中断协调也非常不同.

3. 完全相同的工作频率. 如果要构建双Xeon或双Opteron系统，则必须使用两个2.8 GHz或两个3.0 GHz处理器，不能使用一个2.8 GHz和另一个3.0 GHz来构建，否则系统将无法正常点亮.

4. 尽可能保留相同的产品序列号. 由于不同的生产批次，即使是具有相同内核的相同频率的处理器也可能导致难以置信的问题. 当两个CPU的生产批次用作双处理器时，可能会发生一个CPU负担过重，而另一个CPU负担过重的情况，并且无法实现最高性能，

更糟糕的是，它可能导致崩溃，因此您应该选择同一批处理器来构建SMP系统.

下面讨论单个CPU的调度问题.

查看多个程序并将多个进程同时导入到内存中，这样当一个进程在CPU中执行I / O时，将使用一个进程来填充CPU时间.

通常，进程在CPU间隔和I / O间隔之间切换.

CPU调度程序称为短期调度程序，它从内存调度到CPU.

在内存中等待的就绪队列的节点是PCB. 队列实现方法有很多.

抢占式调度和非抢占式调度（协作）: 前者是一个进程在进程结束之前已经抢占了CPU所有权，而后者则要求进程结束或等待I / O给予其他进程CPU所有权.

尽管现代操作系统使用抢先式调度，但存在同时访问一个数据的风险. 例如，一个进程正在尝试更新数据，但是另一个进程抢占并读取了该数据，从而使数据不一致. 这时，有必要使用进程同步的内容. 锁定

对于随时可能发生中断的情况，我们可以在执行特定代码段时禁用中断.

调度程序用于将CPU的所有权移交给短期调度程序选择的进程. 每次切换进程时使用.

分发延迟: 分发程序所花费的时间.

要考虑的CPU调度因素:

1. CPU使用率.

2. 吞吐量: 每单位时间完成的过程数.

3. 周转时间: 流程提交到流程完成. 也就是说，从等待磁盘进入的内存+就绪队列等待时间+ CPU执行时间+ I / O执行时间. 但是CPU调度算法只是其中的一部分.

4. 等待时间: 就绪队列中等待时间的总和.

5. 响应时间: 用于交互式系统.

CPU调度算法: 甘特图测试点等待时间

此算法适用于CPU的内存就绪队列的处理.

1. FCFS先到先得

一旦选择了一个进程，您将无法切换到另一个进程，直到结束.

2. SJF的最短优先级恰好是下一个CPU间隔最短的算法

如前所述，一个进程由CPU间隔和I / O间隔交替组成. SJF会查看哪个进程具有最短的CPU间隔.

（1）SRTF抢占: 也称为最短剩余优先级，当新进入进程的CPU间隔短于当前执行进程的剩余CPU间隔时，它将抢占.

（2）非抢占: 之所以称为下一个最短优先级，是因为在就绪队列中选择最短CPU间隔的进程位于队列的开头.

SJF用于长期调度而不是短期调度，因为该进程是一个整体，并且CPU无法知道该进程中第一个CPU间隔的长度.

SJF需要确定下一个CPU间隔的长度. 您可以近似估计下一个CPU间隔的长度，例如tn + 1 = atn +（1-a）rn tn是最近的CPU时间，rn是历史记录. a是给定的重量.

3. 优先级调度算法Pintos的优先级为0-63，0为最低优先级，63为最高优先级

SJF是一种特殊的优先级调度算法，将CPU间隔长度的倒数作为优先级.

（1）内部优先级: 通过内部数据（例如内存需求）.

（2）外部优先级: 由用户设置. set_priority

有抢占类型和非抢占类型，如果进入进程的优先级高于运行进程的优先级，则替换前一种；后者仅按优先级在就绪队列中排队.

缺点: 无线阻塞或饥饿. 前者是一个高优先级且长时间运行的进程，已被阻止，而后者是一个低优先级的进程，永远无法执行.

解决饥饿的方法是老龄化. 在每个时间间隔之后，等待进程的优先级都会降低.

4. Runner算法RR算法抢占型

用于分时系统. 每个过程占用一个时间片. 准备队列是FIFO循环队列. 如果一个进程的CPU时间间隔的长度小于时间片，则继续以下过程；如果大于时间片，则中断以切换到下一个流程执行.

时间片的长度通常为10ms-100ms，因此需要确定时间片的大小，以便上下文切换的数量适当减少.

5. 多级队列调度

根据一定的性质，就绪队列分为不同的独立队列，例如系统进程，交互式进程（前台进程），交互式编辑进程，批处理进程和学生进程.

每个队列都有不同的调度算法.

每个队列都有一个优先级. 例如，前台队列比后台队列具有绝对优先级，因此队列之间的分配方法为:

（1）只有当高优先级队列为空时，低优先级队列才能执行.

（2）将具有不同权重的CPU时间分配给队列，并且优先级更高的时间更多.

6. 多级反馈队列抢占

该过程是动态调整的. 该过程在不同的队列之间移动. 尽管在队列之间移动会消耗资源，但这是更合理的.

根据CPU间隔的大小来划分队列.

进程之间的划分是基于所花费的CPU时间. 例如，队列0是就绪队列，并指定时间上限. 如果某个进程未能在指定时间内完成，则将其放入队列1. 具有较大CPU间隔的进程将置于低优先级. 每个进程最初都会进入就绪队列.

多级反馈队列的参数:

1. 队列数.

2. 每个队列的调度算法.

3. 如何升级到优先级更高的队列.

4. 确定如何降级到优先级较低的队列.

5. 该过程需要确定要输入哪个队列.

接下来讨论多个CPU的负载平衡.

假定多个CPU是同构的，但是可能还存在一些特殊的限制，例如只有某个CPU连接到I / O设备.

（1）非对称多处理: 一个处理器专用于CPU调度决策等，另一个用于执行用户代码.

（2）对称多处理（SMP）: 每个处理器的自调度可能会导致多个处理器同时访问同一数据结构并引起冲突.

处理器亲和力: 一个进程只需要在一个处理器上执行，就不会转移到另一个处理器上执行，因为如果转移了，则处理器缓存的资源全部无效且浪费. 缓存存储该进程连续访问的数据.

软件亲和力: 耗时不会转移.

硬关联性: 操作系统不允许进程在多个处理器之间漫游.

负载均衡条件: 每个处理器都有一个专用的就绪队列.

负载均衡方法: 推拉. 也就是说，从高负载的处理器推向低负载的处理器，然后从低负载的处理器向高负载的处理器拉，但这缺乏处理器亲和力.

物理处理器可以分为逻辑处理器. SMT（对称多线程）允许多个线程在物理处理器上同时运行.

逻辑处理器就像物理线程，用于处理物理处理器. 多个逻辑处理器共享物理处理器资源，例如缓存和总线.

例如，就像分区一样，硬盘分为C盘，D盘等，但实际上并没有真正分成硬盘. 从理论上讲，例如的逻辑和物理关系.

系统调度内核线程，并且用户线程由线程库管理. 如果线程要在CPU上运行，则需要将其连接到内核线程.

用户线程需要连接到LWP（进程争用PCS）.

内核线程已连接到物理CPU（系统争用范围SCS）.

Linux使用抢占式和优先级调度算法，并且为优先级较高的进程分配了更多的CPU时间片. 每个处理器维护一个运行队列. 运行队列分为活动队列和过期队列. 前者是一个比时间片花费更少时间的过程多处理器调度，而后者是一个比时间片花费更多时间的任务.

活动队列为空时，交换两个队列.

调度算法评估:

1. 分析和评估方法. 预先确定负载和算法，即可以自己设置的一些数据，例如确定特定的算法FCFS，确定进程到达的时间和数量；根据不同模型比较效果. 缺点是它仅适用于特定情况.

2. 排队模型. 用于分析CPU和I / O的时间间隔分布，给定进程到达系统时的时间分布，排队网络分析的数学公式. 小公式: 进入队列的过程和离开队列的过程应该相等.

3. 模拟. 对计算机系统进行建模，模拟程序以及根据概率分布随机生成数据无法预测前后的事件. 但是通过跟踪磁带来记录实际系统的运行情况，然后按此顺序进行仿真.

4. 实现. 编程并观察后将其放入操作系统.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-186147-1.html