进程调度的原理和算法探析

进程,调度,原理,算法,探析 · 浏览次数 : 292

小编点评

**进程调度进程的调度是由操作系统完成的,其目的是为了在一个进程占用CPU执行自己的操作后,选择下一个进程来占用CPU。** 调度发生的原因很简单,每个进程都希望能够占用CPU进行工作。因此,调度程序会进行上下文切换,并选择一个进程来执行其功能。 **调度时调度的原则有以下五种:** 1. **CPU利用率:**调度程序应始终保持CPU处于繁忙状态运行,以提高CPU的利用率。 2. **系统吞吐率:**调度程序应尽量选择能够快速完成的进程,以提高系统的吞吐率。 3. **周转时间:**指一个进程从创建到完成的总时间。 4. **等待时间:**指用户与其交互这之间所产生的消耗时间越少,响应越好;就是一句话,进程越快越短越好。 5. **响应时间:**指用户与其交互这之间所产生的消耗时间越少,响应越好。 **调度算法分为非抢占式和抢占式两种类型,其中常见的算法包括:** * **先来先服务 (FIFO):**进程按照创建顺序进入就绪队列,执行完就放入后队列。 * **时间片轮转:**进程按创建顺序轮流使用CPU时间片,每个时间片只有一个进程。 * **最短作业优先:**进程按剩余执行时间进行排序,优先执行剩余时间最短的进程。 * **最短剩余时间优先:**进程按剩余执行时间进行排序,优先执行剩余时间最短的进程。 * **优先级调度:**根据进程的优先级进行排序,优先执行优先级高的进程。 * **多级反馈队列调度:**通过多个就绪队列按照优先级和时间片的不同来排列进程,以实现更加灵活和高效的调度。

正文

进程的调度

进程的调度是由操作系统完成的,其目的是为了在一个进程占用CPU执行自己的操作后,选择下一个进程来占用CPU。调度发生的原因很简单,每个进程都希望能够占用CPU进行工作。因此,调度程序会进行上下文切换,并选择一个进程来执行其功能。

那么,什么时候进行调度呢?调度的原则又是什么呢?

什么时候调度进程

进程的调度可以理解为在进程的状态发生变化时进行。以下是一些进程状态的示例:

  • 就绪态 -> 运行态:当一个进程被创建后,它进入就绪队列中等待执行。当操作系统从就绪队列中选择一个进程时,它进入运行态并开始执行。
  • 运行态 -> 阻塞态:当一个进程执行I/O操作时,它可能会进入阻塞态,等待I/O操作完成。此时,操作系统会将当前进程放入阻塞队列,并切换到其他可运行的进程继续执行。
  • 运行态 -> 结束态:当一个进程完成其任务或遇到终止指令时,它会进入结束态。操作系统会从就绪队列中选择下一个进程进行执行。

因为进程的状态发生变化时,操作系统需要考虑是否切换进程来占用CPU执行业务。因此,只要进程状态发生变化,就会触发进程调度。

以什么原则来调度进程

image

进程调度的原则主要有以下五种:

CPU利用率:调度程序应始终保持CPU处于繁忙状态运行,以提高CPU的利用率。

系统吞吐率:系统吞吐率是指在一定时间内完成的进程数量。调度程序应尽量选择能够快速完成的进程,以提高系统的吞吐率。

周转时间:指一个进程从创建到完成的总时间。调度程序应尽量减少进程的周转时间,以提高系统的效率。也可以这么理解:周转时间的计算公式为:周转时间 = 完成时间 - 创建时间;

等待时间:等待时间并不是所谓的阻塞时间,而是在就绪队列中等待被执行的时间;

响应时间:指用户发出请求后系统作出响应的时间。用户与其交互这之间所产生的消耗时间越少,响应越好;

就是一句话,进程越快越短越好;

进程调度算法

调度算法基本分为两类:非抢占式调度算法、抢占式的调度算法;

非抢占式调度算法:这个算法就是之前说的所有进程都进行排队等待,只有前面的进程都执行完了或者自己主动让出CPU,才可以轮到后面的进程执行。常见的非抢占式算法有:先来先服务(FCFS,First-Come, First-Served)和短作业优先(SJF,Shortest Job First)等。

抢占式调度算法:也就是时间片机制,每个进程都只占用CPU的一个时间片操作,执行完了就必须让出CPU使用权限给下一个进程使用。常见的抢占式算法有:轮转调度(Round Robin)、最短剩余时间优先(SRTF,Shortest Remaining Time First)和优先级调度等。

接下来我们详细看下各个调度算法的优劣:

先来先服务

这个是一种最简单的进程调度算法,所有进程按照到达时间的先后顺序排队,先到达的进程先被调度执行。这种调度算法类似于Java中的队列,采用先进先出(FIFO)的原则。

image

这种调度算法存在一个明显的问题,即如果一个进程执行时间较长,后面的进程就必须等待。

时间片轮转调度

时间片轮转调度是一种常见的进程调度算法,它将CPU时间划分为固定大小的时间片(也称为时间量),每个进程在一个时间片内执行,如果时间片用完后仍未执行完,则被移至就绪队列的末尾,等待下一轮调度。虽然解决了排队产生的问题,但是时间片如何划分呢?如果时间片过长,可能会导致资源浪费,因为某些进程可能只需要很短的时间就能执行完毕,但它们仍然会占用整个时间片。另一方面,如果时间片过短,会导致进程切换的频率增加,增加了上下文切换的开销,可能降低系统的性能。因此时间片的长度,需要有大致合理的数值。(《现代操作系统》的观点是建议时间片长度在20ms~50ms)。

image

最短作业优先

最短作业优先调度算法是一种非抢占式的调度算法,它根据进程的执行时间长短进行排队,将作业时间短的进程排在前面先执行。

image

我都不知道进程的执行时间长短的,系统咋知道的?其实系统通过预估进程的执行时间来进行调度,一般可以使用过去的历史执行时间进行估算。但是预估的准不准呢,那肯定不准,所以问题来了,预估的准确性是一个问题。如果预估不准确,可能会导致进程的等待时间增加或者执行时间不均衡。如果短时间的进程一直在排在前面执行,那么长时间的进程可能会一直等待执行的机会。

最短剩余时间优先

他是抢占式的调度算法,可以利用CPU的时间片机制,是基于最短作业优先算法的改进版本。该算法会根据进程的剩余执行时间进行排队,将剩余执行时间最短的进程优先执行。但是这个时间也是预估的而且每个进程的剩余执行时间需要进行实时监控和计算。

如果没有时间片的限制,SRTF算法会变成最短作业优先算法,因为每个进程都能从头到尾一次性执行完毕。

优先级调度

它根据进程的优先级来确定执行顺序。每个进程都有一个优先级值,通常在创建进程时由操作系统分配。如果多个进程的优先级相同,则按照先来先服务(FIFO)的方式依次执行。进程的优先级一般都已经由操作系统在创建的时候都已经设定好了的,如果硬要设置的话,可以去任务管理器看看;

image

优先级调度可以细分为抢占式和非抢占式;这个就不用说了,我单独说下抢占式,在抢占式优先级调度中,如果有高优先级的进程到达,当前正在执行的进程会被中断,让高优先级的进程先执行。

所以说他仍然有点问题,那就是低优先级的进程需要排很长时间的队才可以执行;

多级反馈队列调度

多级反馈队列调度是一种综合了优先级调度和时间片轮转调度的进程调度算法。它通过多个就绪队列按照优先级和时间片的不同来排列进程,以实现更加灵活和高效的调度,但是他并不是按照优先级依次进入就绪队列的,而是都在第一级队列开始执行,执行完就放入第二级队列,依次往下排而已,这个优先级只是单独对于就绪队列来讲的并不是进程的优先级;

image

他就兼顾了长短作业的场景,因为短作业很可能在前面的就绪队列中已经执行完了,而后面的长作业占用的CPU时间片也更长了。

这个算法类比银行办手续的场景:

image

  • 银行大厅中本身三个排队队列,队列1优先级最高但是办理的时间却是最短的,这也对应着优先级越高时间片越短;
  • 新来的客户都先进入队列1叫号排队,但是只办理1分钟的业务,办理不完的客户都去队列2依次排队,当队列1中的客户全办理完之后,工作人员开始处理队列2中的客户,然后依次排队,直至队列中的进程都处理完毕为止;
  • 但是如果在办理其他队列的过程中又有新客户来了,则会终止当前客户的办理并重新进入对尾排队,工作人员会立马处理队列1中的客户。

可以发现,对于要办理短业务的客户来说,可以很快的轮到并解决。对于要办理长业务的客户,一下子解决不了,就可以放到下一个队列,虽然等待的时间稍微变长了,但是轮到自己的办理时间也变长了,

多级反馈队列调度算法兼顾了优先级和时间片的特点,能够适应不同类型的进程和任务。通过合理设置每个队列的优先级和时间片长度,可以根据实际情况提高系统的执行效率和响应速度。

总结

进程调度是操作系统中重要的任务之一。调度程序根据进程的状态变化,选择下一个进程来占用CPU执行任务。调度的原则包括CPU利用率、系统吞吐率、周转时间、等待时间和响应时间等。调度算法分为非抢占式和抢占式两种类型,其中常见的算法包括先来先服务、时间片轮转、最短作业优先、最短剩余时间优先、优先级调度和多级反馈队列调度。每种算法都有其优点和缺点,

与进程调度的原理和算法探析相似的内容:

进程调度的原理和算法探析

本文探讨了进程调度的原理和算法,并提供了全面的概述。进程调度是操作系统中的重要组成部分,用于决定进程的执行顺序和分配CPU时间。我们讨论了优先级调度和时间片轮转调度算法。优先级调度根据进程的优先级确定执行顺序,可以分为抢占式和非抢占式。时间片轮转调度将CPU时间划分为固定大小的时间片,每个进程在一个时间片内执行。合理设置时间片长度能够避免资源浪费和频繁的上下文切换。最短作业优先和最短剩余时间优先是

【完全复现】基于改进粒子群算法的微电网多目标优化调度

主要内容 程序完全复现文献模型《基于改进粒子群算法的微电网多目标优化调度》,以微电网系统运行成本和环境保护成本为目标函数,建立了并网方式下的微网多目标优化调度模型,通过改进粒子群算法和原始粒子群算法进行对比,验证改进方法的优越性。虽然标题是多目标优化算法,实质指的是权值多目标,即通过不同目标权值相加

【单片机入门】(四)应用层软件开发的单片机学习之路-----ESP32开发板PWM控制电机以及中断的使用

引言 各位大佬,晚上好啊,在上一篇博客中,我们讲了什么是UART串口通讯,以及使用USB转TTL使得单片机可以和c#上位机做一个串口通讯,接下来,为大家带来PWM的概念原理,以及实际案例,使用PWM对电机进行速度调制,因为本课程的最后是做一个红外遥控的智能小车,所以是需要电机四个,驱动四个,轮胎四个

[转帖]性能调优要根据自己的情况逐渐调整,往往结合系统监控和性能压力测试一起进行。不可不调,不可乱调。

你可以在https://www.kernel.org/doc/html/latest/admin-guide/sysctl/index.html 官方去看也有文档 性能调优有两个原则:遵从由上之下,木板补板的原则。 性能调优遵循由上至下的原则。 业务逻辑->缓存服务器->调度器->网络容器->中间件

Android Media Framework(一)OpenMAX Spec阅读与框架简介

学习开源代码最快的方式是先阅读它的文档,再查看它的头文件,最后研读代码实现并进行编译调试。Android早期引入OpenMAX IL作为使用音视频编解码器的标准接口,了解Android Media框架的底层运行原理要从OMX IL开始。在这一节,我们将阅读整理OpenMAX IL Spec中的介绍和

[转帖]A-Ops性能火焰图——适用于云原生的全栈持续性能监测工具

https://www.modb.pro/db/610990 对于开发及运维人员来讲,火焰图是一个经典的定位性能问题的方法。利用火焰图可以可视化系统资源(cpu占用、内存占用、调度、IO等)的占用情况,从而帮助技术人员快速定位资源异常使用的代码级根因,或者观察潜在性能劣化趋势,进而优化系统和应用的性

FART 脱壳机原理分析

FART是一个基于Android 源码修改的脱壳机 可以脱整体壳和抽取壳 FART脱壳的步骤主要分为三步: 1.内存中DexFile结构体完整dex的dump 2.主动调用类中的每一个方法,并实现对应CodeItem的dump 3.通过主动调用dump下来的方法的CodeItem进行dex中被抽取的

debug技巧之使用Arthes调试

一、前言 大家好啊,我是summo,今天给大家分享一下我平时是怎么调试代码的,不是权威也不是教学,就是简单分享一下,如果大家还有更好的调试方式也可以多多交流哦。 前面我介绍了本地调试和远程调试,今天再加一种:利用Arthes进行调试。 二、Arthes是什么? 以下是Arthes官网原文: 通常,本

【RcoketMQ】RcoketMQ 5.0新特性(一)- Proxy

为了向云原生演进,提高资源利用和弹性能力,RcoketMQ在5.0进行了架构的调整与升级,先来看新特性之一,增加了Proxy层。 增加Proxy代理层 计算存储分离 计算存储分离是一种分层架构,将计算层与存储层分开。 计算层指的是一些消耗计算资源的功能模块比如协议解析、消费管理等,存储指的是数据存储

8.7 父进程检测反调试

首先这是一种比较奇特的反调试思路,通过检测自身父进程来判定是否被调试,原理非常简单,我们的系统在运行程序的时候,绝大多数应用程序都是由`Explorer.exe`这个父进程派生而来的子进程,也就是说如果没有被调试其得到的父进程就是`Explorer.exe`的进程PID,而如果被调试则该进程的父进程PID就会变成调试器的PID值,通过对父进程的检测即可实现检测是否被调试的功能。