多处理机调度问题的一种近似算法

蒙特卡洛算法组员李小兵周立冯俊李继华艾海提李日浩算法简介蒙特·卡洛方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。

是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

蒙特·卡洛方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。

与它对应的是确定性算法。

蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

背景知识1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。

它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算列?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。

在这里我们要假定豆子都在一个平面上，相互之间没有重叠。

蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。

生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。

算法描述以概率和统计理论方法为基础的一种计算方法。

将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。

比如，给定x=a，和x=b，你要求某一曲线f和这两竖线，及x轴围成的面积，你可以起定y轴一横线 y=c 其中c>=f(x)max，很简单的，你可以求出 y=c,x=a,x=b,及 x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：doteUpCount,nodeDownCount,然后所要求的面积可以近似为doteDownCounts所占比例*矩形面积。

多级调度算法什么是多级调度算法？多级调度算法（Multi-Level Feedback Queue，MLFQ）是一种操作系统中的进程调度算法。

它将进程队列分成多个级别，每个级别都有不同的时间片大小和优先级。

当一个进程被加入队列时，它被放置在最高优先级的队列中，如果它在该队列中运行了一段时间后仍未完成，则被降低到较低优先级的队列中继续运行。

这样可以使长时间运行的进程获得更多的CPU时间，并且能够保证短时间运行的进程能够快速响应用户请求。

多级调度算法的特点1. 多个队列：多级调度算法将进程队列分成多个级别，每个级别都有不同的时间片大小和优先级。

2. 时间片轮转：每个队列使用时间片轮转方式进行调度。

3. 优先级：每个队列都有自己的优先级，高优先级的队列会被更频繁地执行。

4. 抢占式：如果一个高优先级进程加入了队列，则当前正在执行的低优先级进程会被抢占。

5. 动态变化：根据当前系统负载情况动态改变各个队列之间切换所需的时间片大小。

多级调度算法的实现步骤1. 初始化队列：将所有进程按照优先级放入不同的队列中，每个队列都有自己的时间片大小。

2. 运行进程：从最高优先级队列开始运行进程，如果该进程在时间片内完成，则被移出队列，否则被降低到较低优先级的队列中继续运行。

3. 抢占式调度：如果一个高优先级进程加入了队列，则当前正在执行的低优先级进程会被抢占。

4. 动态变化：根据当前系统负载情况动态改变各个队列之间切换所需的时间片大小。

5. 结束进程：当一个进程完成或被杀死时，从相应的队列中移出该进程。

多级调度算法存在的问题1. 饥饿问题：如果系统中有大量长时间运行的高优先级进程，则低优先级进程可能会一直等待，导致饥饿问题。

2. 时间片大小选择问题：选择合适的时间片大小非常重要，如果时间片过小，则会导致频繁切换而浪费CPU资源；如果时间片过大，则会导致响应速度变慢。

3. 进程数目过多：当系统中存在大量进程时，多级调度算法的效率会降低。

处理机调度算法的模拟在计算机操作系统中，处理机调度算法决定了在多个进程或任务同时存在的情况下，哪个任务将获得处理机的使用权，以及在多个任务之间如何切换。

处理机调度算法可以按照多个指标进行优化，例如响应时间、吞吐量、周转时间和等待时间等。

以下是几种常见的处理机调度算法：1.先来先服务（FCFS）：先来先服务是最简单的调度算法之一，它按照任务到达的先后顺序分配处理机资源。

这种算法的优点是简单易实现，但是当存在长作业（任务）时，会导致其他短作业的等待时间过长。

2.短作业优先（SJF）：短作业优先调度算法根据任务的估计执行时间来进行调度，优先执行估计执行时间短的任务。

这种算法可以减少任务的等待时间，但对于长作业来说，可能会导致饥饿现象。

3.优先级调度：优先级调度算法根据任务的优先级进行调度，优先级高的任务先获得处理机的使用权。

这种算法可以根据不同任务的紧急性和重要性来确保任务得到适当的优先级处理。

但是，如果优先级设置不合理，可能会导致一些任务永远得不到执行。

4.时间片轮转调度：时间片轮转调度算法是一种公平的调度算法，它将处理机的使用权按照时间片划分给不同的任务，每个任务只能执行一个时间片的任务。

如果任务在时间片结束之前没有完成，它将被放回到任务队列的末尾继续等待。

这种算法可以确保每个任务都有机会获得处理机的使用权，但是可能会存在上下文切换的开销。

以上只是几种常见的处理机调度算法，实际上还有许多其他算法以及它们的变体，例如最短剩余时间优先（SRTF）、多级反馈队列调度（MFQ）等。

每种调度算法都有不同的优缺点，选择适合的调度算法取决于系统的需求和资源限制。

为了模拟处理机调度算法，可以使用计算机模拟软件或编写自己的模拟程序。

模拟程序可以模拟任务的到达和执行过程，按照指定的调度算法进行任务的分配和切换，并统计不同指标（如响应时间、吞吐量等）来评估算法的性能。

在模拟处理机调度算法时，需要考虑以下几个方面：1.任务的到达过程：任务可以按照随机分布的方式到达，模拟任务的到达时间和资源需求。

处理机调度的常用算法包括以下几种：
1. 先来先服务调度算法（FCFS，First Come First Service）：这是一种最简单的调度算法，按先后顺序进行调度。

既可用于作业调度，也可用于进程调度。

2. 短作业优先调度算法（SJF/SPF，Shortest Job First）：该算法根据作业长短进行调度，有利于短作业（进程）的完成。

3. 高响应比优先调度算法（HRRN，Highest Response Raito Next）：该算法综合考虑了作业长短和等待时间，能够适用于短作业较多的批处理系统中，但长作业的运行可能得不到保证。

4. 基于时间片的轮转调度算法（RR，Round Robin）：该算法将系统中所有的就绪进程按照FCFS原则，排成一个队列。

每次调度时将CPU 分派给队首进程，让其执行一个时间片。

时间片的长度从几个ms到几百ms。

在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。

进程阻塞情况发生时，未用完时间片也要出让CPU。

这些算法各有优缺点，需要根据实际应用场景选择合适的算法。

多级调度算法简介多级调度算法是操作系统中的一种调度算法，用于管理和分配系统中的各个任务和进程资源。

它根据任务的优先级不同，将系统中的任务划分为多个不同的队列，并分配不同的调度策略给每个队列。

多级调度算法可以更加有效地利用系统资源，提高系统的性能和响应速度。

基本原则多级调度算法通常包含以下的基本原则：1.任务分类：将系统中的任务按照不同的优先级划分为多个队列，通常包括高优先级队列、中优先级队列和低优先级队列等。

2.调度策略：为每个队列分配不同的调度策略，以满足不同优先级任务的特点和需求。

常见的调度策略包括先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（RR）等。

3.优先级继承：当一个任务需要等待一个优先级较低的任务执行完成时，可以将其临时提升到较高的优先级队列中执行，以避免优先级反转（PriorityInversion）问题。

4.任务迁移：根据系统中任务的负载情况，可以将任务从一个队列迁移到另一个队列，以实现负载均衡和资源利用的最大化。

常见的多级调度算法先来先服务（FCFS）先来先服务是一种最简单的调度策略，按照任务到达的顺序进行处理。

当一个任务到达系统时，被放入对应优先级队列的末尾。

如果当前正在执行任务，则新到达的任务必须等待前面的任务执行完毕后才能执行。

优点：实现简单，公平性好。

缺点：对长作业不利，容易产生饥饿现象。

最短作业优先（SJF）最短作业优先是根据任务的执行时间进行调度的策略。

具有最短执行时间的任务将被先执行，以减少平均等待时间。

优点：平均等待时间最短。

缺点：无法预测任务执行时间，不利于实时任务。

时间片轮转（RR）时间片轮转是一种基于时间片的调度策略。

每个任务分配一个固定长度的时间片，当时间片用完后，任务被暂停，放回队列尾部，并执行下一个任务。

通过轮转的方式，实现公平地分配每个任务的CPU时间。

优点：响应时间快，公平性好。

缺点：时间片长度的选择会影响系统的性能。

多级反馈队列（MLFQ）多级反馈队列是一种综合性的多级调度算法。

算法之多机调度问题用贪心法解决多机调度问题(1)问题的描述设有n个独立的作业｛1,乙…,n｝,由m台相同的机器｛Ml, M乙…,Mm｝进行加工处理，作业i所需的处理时间为ti (l<i<n),每个作业均可在任何一台机器上加工处理，但不可间断、拆分。

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

(2)算法设计思想解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。

(3)数据及解题过程设7个独立作业｛匕2, 3, 4, 5, 6, 7｝由3台机器｛M2, M2, M3｝加工处理,各作业所需的处理时间分别为｛2, 14, 4,16, 6, 5, 3｝。

贪心法产生的作业调度如下：(4)程序使用C++运行测试(5)代码如下：#include <iostream>#inelude vconio.h>using namespace std;〃冒泡法对作业时间t降序排列，作业编号P的顺序也随t的顺序改变而改变，这点很重要！void Dsc_Order_By_t(int t[],int p[],int n) 〃注意：数组元素下标从1 开始｛〃你的代码int i,j;for (i=l;i<=n;i++)for (j=l;j<=n-i;j++){{int b=t[j+l];t[j+i]=tU];tU)=b；int g=p[j+l]; P D+I]=P U]; P U]=S; }}}for (i=l;i<=n;i++){cout«t[i]«,,\t n;}cout«e ndl;for (i=l;i<=n;i++)cout«e ndl;}void Processing(int p[],int t[],int n’int s[],int d[],int m){ 〃你的代码，根据书中伪代码编写，P154,算法7.9〃其中s[i]={p[i]}ffl位集合表示，代码^:s[i]|=(l«(p[i]-l))〃s[j]=s[j]+{p[i]}实际代码是：s[j]|=(l«(p[i]-l))^懂问我，把它搞清楚！int i; intj; for(i=l;i<=m;i++){s[i]|=(l«(p[i]-D);d[i]=t[i];}for(i=m+l;i<=n;i++){for(int k=l;k<m;k++){int o=d[k];if (o>d[k+l])o=d[k+l];j=k+l;}}sU]|=(l«(p[i]-D)；d[j]二d[j]+t[i];}}void Output(int *p,int n,int *sjnt *d,int m) 〃阅读并理解这个函数{int max=0,k=l;cout«endl«"作业在各台机器上的安排如下："«endl;for(int i=l;i<=m;i++){cout«K机器,,«i«n：for(intj=l;j<=n;j++) if((s[i]»(p[j]-l))&l) cout«*作业*«p0]«" ”; 〃理解位值运算！cout«"总耗时：”《d[i]vvendl;if(max<d[i]) {max=d[i]; k=i;}coutvv“\n“vvnvv”个作业在” vvmvv”台机器上执行完毕最少需要时间H«d[k]«endl;}int main()intp[]={0,l, 2,3, 4,5,6,7}, 〃作业编号，p[0]不用t[]={0,2,14,4,16,6,5,3}, 〃对应作业时间，t[0]不用s[]={0,0,0,0}, 〃机器处理的作业集合，女口：s⑴存放机器处理过的作业号，s[0]不用d[]二{0,000}; 〃机器处理作业的总时间，女口：d[2]存放机器处理过的作业的总时间，d[0]不用int n=sizeof(p)/sizeof(int)-l,m=sizeof(s)/sizeof(int)-l; //n-作业总数，m••机器台数Dsc_Order_By_t(t,p,n); 〃对作业根据运行时间t进行降序排列Processing(p,t,n,s,d,m); 〃用最长运行时间优先算法处理作业Output(p,n,s,d,m); 〃输出结果_getch();return 0;}运行结果图:。

多机调度问题一、 问题描述设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。

作业i所需的处理时间为t i。

现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理，任何作业不能拆分成更小的子作业。

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

二、 问题分析这是一个NP完全问题，到目前为止还没有有效的解法。

本报告根据教材指导及实践经验，采用贪心算法进行分析求解，并进行简单评估。

使用贪心算法，能避免许多复杂的子问题分析，便于直观地剖析主要问题。

在选择贪心算法的基础上，进一步地，我们采用最长处理时间作业优先的贪心选择策略，以求设计出解多机调度问题的较好的近似算法。

预期效果：根据最长处理时间作业优先的原则，理应能够得出直观下比较高效的输出结果。

三、算法设计与分析1．算法输入和输出输入：作业数n，机器数m，作业i对应的处理时间t i（t i在测试时用一个一维数组time表示）输出：总耗费时间2．算法说明最长处理时间作业优先的贪心算法，顾名思义，就是将目前还未被处理的且需要处理时间最长的作业，分配给最先空闲的机器，直到分配完所有的作业为止。

3．算法描述（1）（处理1）：当n≤m时，只要将机器i的[0,t i]时间区间分配给作业i即可。

（2）（处理2）：当n＞m时：i.先将耗时最长的m个作业依次分配给m个机器ii.沿着时间轴，寻找最先得到空闲的机器。

将还未被处理且需要处理时间最长的那个作业分配给此机器iii.重复上一步直到所有作业都被处理完毕4．算法分析当n≤m时，算法需要O(1)时间。

当n＞m时，算法需要O(nlogn)时间。

四、算法流程图输入是否n≤m处理1 处理2输出图4-1 多机调度算法流程图五、测试数据及其结果分析1．测试数据当输入n=7, m=3, time={2,14,4,16,6,5,3}时（教材示例），经历处理2，输出结果为17 当输入n=7, m=3, time={4,5,13,9,4,11,2}时，经历处理2，输出结果为20当输入n=18, m=3, time={1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}时，经历处理2，输出结果为33当输入n=3, m=3, time={2,3,5}时，经历处理1，输出结果为52．结果分析观察可知，贪心算法解此问题，比直观感受要更高效。