多核CPU环境下进程的调度算法一般有全局队列调度和局部队列调度两种。（）属于全局队..

多内核是指在一枚处理器中集成两个或多个完整的计算引擎（内核）。多核技术的开发源于工程师们认识到，仅仅提高单核芯片的速度会产生过多热量且无法带来相应的性能改善，先前的处理器产品就是如此。通过多核芯片，可以使计算机满足“横向扩展”（而非“纵向扩充”），从而提高性能。多核技术实现了分治法的战略，通过划分任务，线程应用能够充分利用多个执行内核，并可在特定的时间内执行更多任务。多核处理器是单枚芯片（硅核），能够直接插入单一的处理器插槽中，但操作系统会利用所有相关的资源，将它的每个执行内核作为分立的逻辑处理器。通过在两个执行内核之间划分任务，多核处理器可在特定的时钟周期内执行更多任务。

多核体系结构能够使目前的软件更出色地运行，并创建一个促进未来的软件编写更趋完善的体系结构，现有软件无须被修改就可支持多核平台。操作系统专为充分利用多个处理器而设计，且无须修改就可运行。为了充分利用多核技术，应用开发人员需要在程序设计中融入更多思路，但设计流程与目前SMP系统的设计流程相同，并且现有的单线程应用也将继续运行。

多核技术能够使服务器并行处理任务，而在以前，这可能需要使用多个处理器，多核系统更易于扩充，并且能够在更纤巧的外形中融入更强大的处理性能，这种外形所用的功耗更低、计算功耗产生的热量更少。

多核技术是处理器发展的必然，是技术发展和应用需求的必然产物。这主要基于以下事实：

（1）晶体管时代即将到来。根据摩尔定律，微处理器的速度以及单片集成度每18个月就会翻一番。据估计，到2010年左右，芯片上集成的晶体管数目将超过10亿个。多核技术通过在一个芯片上集成多个简单的处理器核，充分利用这些晶体管资源，发挥其最大的能效。

（2）门延迟逐渐缩短，而全局连线延迟却不断加长。随着VLSI工艺技术的发展，晶体管特征尺寸不断缩小，使得晶体管门延迟不断减少，但互连线延迟却不断变大。当芯片的制造工艺达到0.18微米甚至更小时，线延迟已经超过门延迟，成为限制电路性能提高的主要因素。在这种情况下，由于单芯片多处理器的分布式结构中全局信号较少，与集中式结构的超标量处理器结构相比，在克服线延迟影响方面更具优势。

（3）符合Pollack规则。按照Pollack规则，处理器性能的提升与其复杂性的平方根成正比。如果一个处理器的硬件逻辑提高一倍，至多能提高性能40%，而如果采用两个简单的处理器构成一个相同硬件规模的双核处理器，则可以获得70%～80%的性能提升。同时在面积上也同比缩小。

（4）能耗不断增长。随着工艺技术的发展和芯片复杂性的增加，芯片的发热现象日益突出。多核处理器里单个核的速度较慢，处理器消耗较少的能量，产生较少的热量。同时，原来单核处理器里增加的晶体管可用于增加多核处理器的核。在满足性能要求的基础上，多核处理器通过关闭（或降频）一些处理器等低功耗技术，可以有效地降低能耗。

（5）设计成本的考虑。随着处理器结构复杂性的不断提高，和人力成本的不断攀升，设计成本随时间呈线性甚至超线性的增长。多核处理器通过处理器IP等的复用，可以极大地降低设计的成本。同时模块的验证成本也显著下降。

（6）体系结构发展的必然。超标量结构和超长指令字结构在目前的高性能微处理器中被广泛采用。但是它们的发展都遇到了难以逾越的障碍。超标量结构使用多个功能部件同时执行多条指令，实现指令级的并行（Instruction-Level Parallelism, ILP）。但其控制逻辑复杂，实现困难，研究表明，超标量结构的ILP一般不超过8。超长指令字结构使用多个相同功能部件执行一条超长的指令，但也有两大问题：编译技术支持和二进制兼容问题。

CPU

CPU即中央处理器，它是计算机系统的核心部分。刚才所列的系统性能评价指标都是围绕CPU的。当然，这些指标的评价结果是建立在CPU与其他系统部件（如内存）的协同工作的基础上的。单就CPU而言，考察它在系统中的工作性能要关注CPU利用率、队列长度、每秒中断次数，等。

调度算法

常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。

（1）先来先服务（FCFS）。FCFS按照作业提交或进程成为就绪状态的先后次序分配CPU，即进程调度总是将就绪队列队首的进程投入运行。FCFS的特点是比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。FCFS算法主要用于宏观调度。

（2）时间片轮转。时间片轮转算法主要用于微观调度，其设计目标是提高资源利用率。通过时间片轮转提高进程并发性和响应时间特性，从而提高资源利用率。时间片的长度可以从几毫秒到几百毫秒，选择的方法一般分为固定时间片和可变时间片两种。

（3）优先级调度。该算法是让每一个进程都拥有一个优先数，数值大的表示优先级高，系统在调度时总选择优先数大的占用CPU。优先级调度分为静态优先级和动态优先级两种。

（4）多级反馈调度。多级反馈队列调度算法是时间片轮转算法和优先级算法的综合与发展。其优点有三个方面：第一，照顾了短进程以提高系统吞吐量，缩短了平均周转时间；第二，照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；第三，不必估计进程的执行时间，动态调节优先级。

队列

队列的定义

队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。

由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out, FIFO）的原则组织数据的，因此，队列也被称为"先进先出"表。

下图是一个队列的进出示意图，通常用指针front指示队头的位置，用指针rear指向队尾的位置。

队列的进出示意图

队列的基本操作

队列的基本操作主要有以下6种。

.InitQueue（&Q）：初始化操作，构造一个队列Q。

.QueueEmpty（Q）：若栈Q为空队列，返回1，否则返回0。

.EQueue（&Q, e）：插入元素e到队列Q的尾部。

.OQueue（&Q,&e）：删除Q的队首元素，并用e返回其值。

.GetQhead（Q,&e）：用e返回Q的队首元素。

.ClearQueue（&Q）：将Q清空为空队。

队列的顺序存储结构

顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似）。

按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前提下，用front==（rear+1）% MAX表示队列满。在这种约定下，入队操作的语句为：rear=（rear+1）%MAX, MAX, Q[rear]=x；出队操作语句为：front=（front+1）% MAX。

顺序队列的类型定义如下：

顺序队列定义为一个结构类型，该类型变量有3个数据域：data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，这种顺序队列说明如下。

.初始化时，设置SQ.front=SQ.rear=0。

.队头指针的引用为SQ.front，队尾指针的引用为SQ.rear。

.队空的条件为SQ.front==SQ.rear；队满的条件为SQ.front=（SQ.rear+1）% QueueSize。

.入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。

.队列长度为（SQ.rear+QueueSize-SQ.front）% QueueSize。

特别应注意的是：在循环队列的操作中队头指针、队尾指针加1时，都要取模，以保持其值不出界。

在循环队列上队列的实现基本操作的函数如下。

1）初始化initqueue（SQueue *SQ）

2）判空QueueEmpty（SQueue SQ）

3）入队EQueue（SQueue *SQ, ElemType e）

4）出队OQueue（SQueue *SQ, ElemType *e）

5）取队首元素GetQhead（SQueue *SQ, ElemType *e）

6）清队列ClearQueue（SQueue *SQ）

队列的链式存储结构

队列的链接实现称为链队，链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点即单链表的最后一个节点。为了简便，链队设计成一个带头节点的单链表。

链队的类型定义如下：

链队列的说明如下。

.队列以链表形式出现，链首节点为队头，链尾节点为队尾。

.队头指针为LQ→front，队尾指针为LQ→rear，队头元素的引用为Q→front→data，队尾元素的引用为LQ→rear→data。

.初始化时，设置LQ→front=LQ→rear=NULL。

.进队操作与链表中链尾插入操作一样；出队操作与链表中链首删除操作一样。

.队空的条件为LQ→front==NULL。理论上，只要系统内存足够大，链队是不会满的。

在链队上实现队列基本操作的函数如下。

1）队列初始化InitQueue（LQueue *LQ）

2）入队EQueue（LQueue *LQ, ElemType e）

3）出队OQueue（LQueue *LQ, ElemType *e）

4）判空QueueEmpty（LQueue *LQ）

5）取队首元素GetQhead（LQueue *LQ, ElemType *e）

6）清队列ClearQueue（LQueue *LQ）

循环队列中的边界条件判别准则

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

双端队列的作用

双端队列是限定插入和删除操作在线性表的两端进行，可将其看成是栈底连在一起的两个栈，但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如下图所示。

双端队列的示意图

在实际应用中，可对双端队列的输出进行限制（即一个端点允许插入和删除，另一个端点只允许插入），也可对双端队列的输入进行限制（即一个端点允许插入和删除，另一个端点只允许删除）。可见，采用双端队列可增加应用中的灵活性。

多核CPU

CPU的核心又称为内核，是CPU最重要的组成部分。CPU中心那块隆起的芯片就是核心，是由单晶硅以一定的生产工艺制造出来的，CPU所有的计算、接收／存储命令、处理数据都由核心执行。各种CPU核心都具有固定的逻辑结构，一级缓存、二级缓存、执行单元、指令级单元和总线接口等逻辑单元都需要合理的布局。

多核即在一个单芯片上面集成两个甚至更多个处理器内核，其中每个内核都有自己的逻辑单元、控制单元、中断处理器、运算单元，一级Cache、二级Cache共享或独有，其部件的完整性和单核处理器内核相比完全一致。

起初，CPU的主要厂商AMD和Intel的双核技术在物理结构上有很大不同。AMD将两个内核做在一个Die（晶元）上，通过直连架构连接起来，集成度更高。Intel则是将放在不同核心上的两个内核封装在一起，因此有人将Intel的方案称为“双芯”，将AMD的方案称为“双核”。从用户端的角度来看，AMD的方案能够使双核CPU的管脚、功耗等指标跟单核CPU保持一致，从单核升级到双核，不需要更换电源、芯片组、散热系统和主板，只需要刷新BIOS软件即可。

多核CPU系统最大的优点（也是开发的最主要目的）是可满足用户同时进行多任务处理等要求。

单核多线程CPU是交替地转换执行多个任务，只不过交替转换的时间很短，用户一般感觉不出来。如果同时执行的任务太多，就会感觉到“慢”或者“卡”。而多核在理论上则是在任何时间内每个核分别执行各自的任务，不存在交替问题。因此，单核多线程和多核（一般每核也是多线程的）虽然都可以执行多任务，但多核的速度更快。

虽然采用了Intel超线程技术的单核可以视为双核，4核可以视为8核。然而，视为8核一般比不上实际是8核的CPU性能。

要发挥CPU的多核性能，就需要操作系统能够及时、合理地给各个核分配任务和资源（如缓存、总线、内存等），也需要应用软件在运行时可以把并行的线程同时交付给多个核心分别处理。

进程

简单而言，一个进程就是一个正在运行的程序。一般来说，一个进程至少应该包括以下几个方面的内容。

.相应的程序：进程既然是一个正在运行的程序，当然需要有相应程序的代码和数据。

.CPU上下文：指程序在运行时，CPU中各种寄存器的当前值，包括：程序计数器，用于记录将要取出的指令的地址；程序状态字，用于记录处理器的运行状态信息；通用寄存器，用于存放数据或地址；段寄存器，用于存放程序中各个段的地址；栈指针寄存器，用于记录栈顶的当前位置。

.一组系统资源：包括操作系统用来管理进程的数据结构、进程的内存地址空间、进程正在使用的文件等。

进程有动态性、独立性和并发行三个特性。

（1）动态性。进程是一个正在运行的程序，而程序的运行状态是在不断地变化的。例如，当一个程序在运行的时候，每执行完一条指令，PC寄存器的值就会增加，指向下一条即将执行的指令。而CPU中用来存放数据和地址的那些通用寄存器，它们的值肯定也不断地变化。另外，堆和栈的内容也在不断地变化，每当发生一次函数调用时，就会在栈中分配一块空间，用来存放此次函数调用的参数和局部变量。而当函数调用结束后，这块栈空间就会被释放掉。

（2）独立性。一个进程是一个独立的实体，是计算机系统资源的使用单位。每个进程都有自己的运行上下文和内部状态，在它运行的时候独立于其他的进程。

（3）并发性。从宏观上来看，在系统中同时有多个进程存在，它们相互独立地运行。

下图表示四个进程A、B、C、D在系统中并发地运行。从中可以看出，虽然从宏观上来说，这四个进程都是在系统中运行，但从微观上来看，在任何一个特定的时刻，只有一个进程在CPU上运行。从时间上来看，开始是进程A在运行，然后是进程B在运行，然后是进程C和进程D。接下来又轮到了进程A去运行。因此，在单CPU的情形下，所谓的并发性，指的是宏观上并发运行，而微观上还是顺序运行，各个进程轮流去使用CPU资源。

四个进程在并发运行

在具体实现上，以CPU中的程序计数器PC为例，真正物理上的PC寄存器只有一个。当四个进程在轮流执行时，PC取值的运动轨迹是先在进程A内部流动，然后再到进程B的内部流动，再到进程C和D。从进程的独立性角度来说，每个进程都有“自己”独立的PC寄存器，即逻辑上的PC寄存器，它们的取值相互独立、互不影响。所谓的逻辑PC，其实就是一个内存变量。例如，在上图中，当进程A要执行的时候，就把A的逻辑PC的值拷贝到物理PC中，然后开始运行。当轮到B运行的时候，先把物理PC的当前值保存到A的逻辑PC中，然后再把B的逻辑PC的值装入到物理PC中，即可运行。这样就实现了各个进程的轮流运行。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5