下载文档原格式
进程调度算法总结所谓进程，简单来说是计算机中的各种任务，那么计算机如何分配系统资源以供这些任务使⽤呢？此篇博客⽬的就是为⼤家整理⼀下⼏种常见进程调度算法。
进度调度就是按照⼀定的策略，动态地把处理机分配给处于就绪队列的进程，使之执⾏。
常见的进程调度算法：1、先来先服务和短作业（进程）优先调度算法2、⾼优先权优先调度算法3、基于时间⽚的轮转调度算法下⾯细说：1、先来先服务和短作业优先调度算法1.1、先来先服务调度算法这种调度算法由字⾯意思理解很直观，所谓先来先服务，就是谁先来先服务谁。
结合进程，先来先服务调度算法就是对于优先到达就绪队列的进程采取优先服务的策略，直到该进程运⾏结束或发⽣某事件导致阻塞才放弃处理机。
这种调度算法是⼀种最简单的调度算法，适⽤于作业和进程。
当⽤于作业时，先进⼊后备队列的作业先运⾏。
1.2、短作业（进程）优先调度算法短作业（进程）优先调度算法，是对短作业或短进程进⾏得调度算法。
何为短？就是估计运⾏时间短。
该算法从后备队列或就绪队列选择估计运⾏时间较短的作业或进程，将他们调⼊内存运⾏，直到该进程运⾏结束或发⽣某事件导致阻塞才放弃处理机重新进⾏调度。
2、⾼优先权优先调度算法2.1、优先权调度算法上述所说的两种调度算法，过于简单，当系统中有紧急作业或进程，且不满⾜先进队列或运⾏时间短时，这些作业或进程将很难得到资源。
那么对于这些作业或进程，⼜该怎么办呢？因此，⼜有了优先权调度算法，所谓优先权调度算法，顾名思义就是谁的优先权⾼，谁就西安得到资源得以运⾏。
进⼀步将算法分为以下两种：2.1.1、⾮抢占式优先权算法在这种⽅式下，系统⼀旦把处理机分配给就绪队列中优先权最⾼的进程后，该进程便⼀直执⾏下去，直⾄完成；或因发⽣某事件使该进程放弃处理机时，系统⽅可再将处理机重新分配给另⼀优先权最⾼的进程。
这种调度算法主要⽤于批处理系统中；也可⽤于某些对实时性要求不严的实时系统中。
2.1.2、抢占式优先权算法在这种⽅式下，系统同样是把处理机分配给优先权最⾼的进程，使之执⾏。
优先权调度算法的类型
1.非抢占式优先权调度算法：
非抢占式优先权调度算法是指一旦一个进程开始执行，其他进程无法抢占其CPU资源，直到该进程完成或主动释放CPU。
这种类型的优先权调度算法具有简单和易于实现的特点，但容易导致饥饿问题，即一些低优先级的进程可能永远无法执行。
2.抢占式优先权调度算法：
抢占式优先权调度算法允许进程在执行过程中被其他优先级更高的进程抢占CPU资源。
这种类型的优先权调度算法可以有效解决饥饿问题，但实现相对复杂，需要考虑进程状态保存和恢复的问题。
3.静态优先权调度算法：
静态优先权调度算法是在进程创建时就给予每个进程一个优先级，之后不再改变。
这种类型的优先权调度算法适用于优先级相对固定、难以变化的场景。
但是，静态优先权调度算法可能导致低优先级进程无法获得足够的CPU使用时间。
4.动态优先权调度算法：
动态优先权调度算法是根据一定规则和策略不断调整进程的优先级。
这种类型的优先权调度算法可以根据进程的行为和状态来调整优先级，有助于提高系统的性能和公平性。
5.多级队列优先权调度算法：
多级队列优先权调度算法将进程按优先级划分为多个队列，每个队列拥有不同的优先级范围。
进程首先进入最高优先级队列，只有在该队列中
没有可运行的进程时，才会调度下一个优先级较低的队列。
这种类型的优先权调度算法可以根据不同的优先级范围进行调度，提高系统的资源利用率和响应速度。
综上所述，优先权调度算法可以根据是否抢占、是否静态、是否动态以及是否多级队列来进行划分。
不同类型的优先权调度算法在不同的场景下有各自的优势和适用性，选择合适的算法可以提高系统的性能和用户体验。
抢占式最高优先级算法抢占式最高优先级算法是一种常见的调度算法，用于在多进程或多线程的操作系统中，决定拥有高优先级的任务是否可以抢占当前正在执行的低优先级任务，以便让高优先级任务先执行。
本文将介绍抢占式最高优先级算法的原理、应用场景以及其优缺点。
原理抢占式最高优先级算法依据任务的优先级来进行调度。
每个任务都被赋予一个优先级，较高优先级的任务拥有更高的执行权。
如果一个高优先级的任务到达并请求执行，它会立即抢占正在执行的低优先级任务，使自身先执行。
一旦高优先级任务执行完毕或者被阻塞，低优先级任务会继续执行。
抢占式最高优先级算法的关键在于选择高优先级任务并进行抢占。
这一选择常常基于预定的策略，如固定优先级、动态优先级或抢占周期。
应用场景抢占式最高优先级算法在许多实时操作系统（RTOS）中被广泛应用，以确保高优先级任务能够及时响应。
1.实时任务：在实时系统中，某些任务需要及时响应来满足硬实时性要求。
比如，在飞行控制系统中，传感器数据的处理常常具有较高的优先级，以便实时调整飞行控制参数。
2.实时多媒体：在视频或音频播放中，保证实时性是非常重要的。
为了避免出现卡顿或延迟，实时多媒体任务通常具有相对较高的优先级，以确保及时进行数据解码和渲染。
3.紧急事件响应：在多任务的环境中，某些任务可能需要及时响应紧急事件。
比如，网络服务器在遇到高流量或攻击时需要迅速调整优先级以应对。
优点抢占式最高优先级算法具有以下优点：1.及时响应高优先级任务：算法能够保证高优先级任务的及时执行，使得系统能够满足实时性要求。
2.简单高效：算法的实现相对简单，可以高效地处理任务调度。
相比其他调度算法，抢占式最高优先级算法通常需要较少的计算和资源。
3.适用性广泛：算法可以应用于多种场景，可以根据具体需求进行灵活调整。
缺点抢占式最高优先级算法也存在一些局限性：1.低优先级任务饥饿：当高优先级任务过多时，低优先级任务可能被长时间地阻塞，无法得到充分执行。
在单片机系统中，优先级调度算法用于确定在有多个任务同时运行时，哪个任务具有更高的优先级，应该先执行。
这在实时系统和嵌入式系统中非常重要，因为这些系统通常需要对任务的响应时间和执行顺序进行精确控制。
以下是一些常见的单片机优先级调度算法：1. 固定优先级调度（Fixed Priority Scheduling）：- 每个任务被分配一个固定的优先级，由开发者在设计时确定。
- 任务按照它们的优先级进行调度，具有更高优先级的任务将在具有较低优先级的任务之前执行。
2. 轮转法（Round Robin Scheduling）：- 每个任务都有一个时间片（time slice）或执行时间的最大限制。
- 任务按照轮流的方式执行，每个任务在分配的时间片内运行，然后切换到下一个任务。
- 如果一个任务在其时间片结束之前未完成，它将被放回队列，等待下一个时间片。
3. 最短剩余时间优先（Shortest Remaining Time First，SRTF）：- 每个任务都有一个估计的执行时间。
- 在每个调度点，选择剩余执行时间最短的任务来执行。
- 这是一种抢占式调度算法，可能会在执行过程中切换到更紧急的任务。
4. 最早截止期限优先（Earliest Deadline First，EDF）：- 每个任务都有一个截止期限。
- 在每个调度点，选择截止期限最早的任务来执行。
- 这是一种抢占式调度算法，适用于实时系统，确保截止期限更早的任务先执行。
5. 多级队列调度（Multilevel Queue Scheduling）：- 将任务分为多个队列，每个队列有不同的优先级。
- 任务按照其优先级放置在相应的队列中，每个队列可以采用不同的调度算法。
- 任务可以在队列之间移动，例如，根据它们的执行历史或其他因素。
选择合适的调度算法取决于系统的需求和性能要求。
实时系统通常需要更为精确和可预测的调度，而通用用途的系统可能更关注性能和资源利用率。
抢占式优先级调度算法
抢占式优先级调度算法是一种常用的操作系统进程调度算法，其主要
原理是将进程按照优先级进行排序，然后选择优先级最高的进程进行执行，同时当出现更高优先级的进程时，正在执行的进程会被抢占，优先级更高
的进程得以执行。
这种调度算法的优点是能够优先执行重要性高的进程，尤其是对于实
时性要求高的系统而言，抢占式优先级调度算法确保了高优先级进程的及
时响应和执行。
其次，该算法在实现上相对简单，容易在多处理器系统中
进行实现。
然而，抢占式优先级调度算法也存在一些缺点。
首先，由于优先级的
设置需要有明确的标准，因此可能存在优先级过多或者优先级设计不合理
的问题。
其次，由于是按优先级进行调度，较低优先级的进程容易长时间
等待执行，降低了系统的资源利用率；同时，当出现优先级较高的进程时，抢占式调度会导致正在执行的进程被强制停止，造成不必要的系统开销。
为了克服抢占式优先级调度算法的缺陷，可以采用多种方法进行改进。
一种常见的方法是将进程的优先级根据时间的长短进行动态调整，即优先
级随时间而变化。
另外，可以通过引入多级反馈队列的方式，使得低优先
级的进程能够持续得到调度和执行的机会，从而提高系统资源利用率。
此外，还可以采用不同进程之间互相协作的方式，实现更加高效的进程调度
机制。
总之，抢占式优先级调度算法是一种适用于实时性要求高的系统的进
程调度算法，但其应用存在一定的局限性。
针对不同的应用场景和要求，
可以采用不同的调度算法进行优化和改进，从而实现更加高效、快速、可靠的进程调度和执行。
剥夺式优先级调度算法
剥夺式优先级调度算法（也称为抢占式优先级调度算法）是一种操作系统中用于进程调度的策略。
在这个算法中，系统将所有进程按照优先级排序，优先级高的进程获得CPU执行权的概率更高。
具体运行过程如下：
1. 每个进程都有一个优先级属性。
2. 当有多个进程等待CPU时，系统会选择优先级最高的进程投入运行。
3. 如果在运行过程中，有一个优先级更高的进程到达就绪队列，那么系统会立即停止当前正在运行的低优先级进程，并把CPU分配给新到达的高优先级进程，这就是“剥夺”或“抢占”的含义。
4. 进程在执行过程中，其优先级可能会发生变化，例如，有的系统会根据进程等待时间来动态调整优先级，防止优先级过高的进程长期占用CPU导致低优先级进程饥饿。
这种算法可以有效保证重要性较高的进程得到及时响应，提高了系统的响应速度和效率。
然而，如果设计不当，可能导致低优先级进程长时间得不到执行，即发生“进程饥饿”现象。
因此，在实际应用中，往往会对该算法进行改进，比如设置优先级aging（老化）机制等。
抢占式优先级调度算法是什么意思系统把处理机分配给优先权最⾼的进程，使之执⾏。
但在其执⾏期间，只要⼜出现了另⼀个其优先权更⾼的进程，进程调度程序就⽴即停⽌当前进程(原优先权最⾼的进程)的执⾏，重新将处理机分配给新到的优先权最⾼的进程。
本教程操作环境：windows7系统、C++17版本、Dell G3电脑。
抢占式优先权调度算法在这种⽅式下，系统把处理机分配给优先权最⾼的进程，使之执⾏。
但在其执⾏期间，只要⼜出现了另⼀个其优先权更⾼的进程，进程调度程序就⽴即停⽌当前进程(原优先权最⾼的进程)的执⾏，重新将处理机分配给新到的优先权最⾼的进程。
因此，在采⽤这种调度算法时，是每当系统中出现⼀个新的就绪进程i 时，就将其优先权Pi与正在执⾏的进程j的优先权Pj进⾏⽐较。
如果Pi≤Pj，原进程Pj便继续执⾏；但如果是Pi>Pj，则⽴即停⽌Pj的执⾏，做进程切换，使i 进程投⼊执⾏。
显然，这种抢占式的优先权调度算法能更好地满⾜紧迫作业的要求，故⽽常⽤于要求⽐较严格的实时系统中，以及对性能要求较⾼的批处理和分时系统中。
具体代码：1 #include #include #include using namespace std;using std::cout;struct PCB23 { // 进程名45string name; // 到达时间67int arrivetime; // 运⾏时间89int runtime;1011// 仍需运⾏时间1213int resttime; // 开始时间1415int starttime; // 完成时间1617int endtime; // 运⾏次数1819int runcount; // 周转时间2021int zhouzhuangtime; // 带权周转时间（周转时间/运⾏时间)2223double weightzhouzhuangtime; // 优先级（静态）2425int priority;26272829 PCB *next;3031 };// 进程数int num_process;// 记录所有进程的总时间int totaltime;// 记录所有进程的总带权周转时间double weighttotaltime;32333435 PCB *createPCB()3637 { int i; // 定义队⾸、队尾3839 PCB *head, *rear; // 初始化4041 head = rear = NULL; // 临时指针变量4243 PCB *p; cout<<"请输⼊进程数量："; cin>>num_process; for(i = 0; i < num_process; i++)4445 { // 初始化⼀个空间给进程4647 p = new PCB; cout<<"请依次输⼊第"<>p->name>>p->priority>>p->arrivetime>>p->runtime;4849 p->resttime = p->runtime;5051 p->runcount = 1;5253 totaltime += p->runtime;5455 p->starttime = 0;5657 p->endtime = 0;5859 p->zhouzhuangtime = 0;6061 p->weightzhouzhuangtime = 0;6263 p->next = NULL; // 存⼊链表中6465if(rear == NULL)6667 {69 head = p;7071 rear = p;7273 } else7475 {7677 rear->next = p;7879 rear = p;8081 }82838485 } return head;8687 }// 链表插⼊排序PCB *insertSort(PCB *head)8889 { /*9091 1、先在原链表中以第⼀个节点为⼀个有序链表，其余节点为待定节点；9293 2、从待定节点中取节点，插⼊到有序链表中相应位置；9495 3、实际上只有⼀条链表，在排序中，实际只增加了⼀个⽤于指向剩下需要排序节点的头指针。
