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

进程,调度,原理,算法,探析 · 浏览次数 : 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时间划分为固定大小的时间片,每个进程在一个时间片内执行。合理设置时间片长度能够避免资源浪费和频繁的上下文切换。最短作业优先和最短剩余时间优先是

[转帖]什么是CDN?CDN的工作原理是怎样的?

1.什么是CDN? CDN的全称是Content Delivery Network,即内容分发网络。CDN是构建在网络之上的内容分发网络,依靠部署在各地的边缘服务器,通过中心平台的负载均衡、内容分发、调度等功能模块,使用户就近获取所需内容,降低网络拥塞,提高用户访问响应速度和命中率。CDN的关键技术

处理机调度与死锁

一、处理机调度的层次 概念 按什么原则分配CPU:调度算法。 何时分配CPU:调度时机。 如何分配CPU:调度过程。 周转时间:完成时间-进入时间。(注意:从进入系统到执行完成包括在后备队列中等待调度、在就绪队列中等待进程调度、执行以及等待I/O操作完成四部分时间,作业进入是指作业准备好被调度的状态

[转帖]Linux下进程管理知识(详细)总结

一、简介 本文主要详细介绍进程相关的命令的使用、进程管理及调度策略的知识。 二、常用的命令解析 1、ps命令 命令选项解析-a显示一个终端所有的进程-u显示进程的归属用户和内存占用情况-x显示没有控制终端的进程-l长格式显示更详细的信息-e显示所有进程-w宽行显示,可以使用多个w进行加宽显示 进程常

[转帖]「Linux性能调优」磁盘I/O队列调度策略

https://zhuanlan.zhihu.com/p/450329513 傻瓜化说明 简单地说,对于磁盘I/O,Linux提供了cfq, deadline和noop三种调度策略 cfq: 这个名字是Complete Fairness Queueing的缩写,它是一个复杂的调度策略,按进程创建多个

[转帖]《Linux性能优化实战》笔记(六)—— Linux 软中断与对应故障分析方法

中断是系统用来响应硬件设备请求的一种机制,它会打断进程的正常调度和执行,然后调用内核中的中断处理程序来响应设备的请求。 一、 为什么要有中断 举个生活中的例子,让你感受一下中断的魅力。比如说你订了一份外卖,但是不确定外卖什么时候送到,也没有别的方法了解外卖的进度,但是,配送员送外卖是不等人的,到了你

[转帖]Linux 磁盘I/O 调度算法 说明

2022-08-23 13:031361转载Linux 1 Linux 4.0 IO协议栈框架图 I/O 调度算法在各个进程竞争磁盘I/O的时候担当了裁判的角色。他要求请求的次序和时机做最优化的处理,以求得尽可能最好的整体I/O性能。 Linux 4.0 IO协议栈框架图 I/O调度程序的总结 当向

7.6 实现进程挂起与恢复

挂起与恢复进程是指暂停或恢复进程的工作状态,以达到一定的控制和管理效果。在 Windows 操作系统中,可以使用系统提供的函数实现进程的挂起和恢复,以达到对进程的控制和调度。需要注意,过度使用进程挂起/恢复操作可能会造成系统性能的降低,导致死锁等问题,因此在使用时应该谨慎而慎重。同时,通过和其他进程之间协同工作,也可以通过更加灵活的方式,实现进程的协调、交互等相应的功能,从而实现更加高效和可靠的进

深入理解操作系统中进程与线程的区别及切换机制(下)

本文首先介绍了进程的控制结构,即进程控制块(PCB),它是表示进程的数据结构,包含了进程的相关信息和资源。PCB之间通过链表连接,形成就绪队列和阻塞队列,用于进程调度和资源管理。接着,文章详细探讨了进程的切换过程。进程切换是为了保证公平分配CPU时间片,涉及保存和恢复进程的执行上下文、更新进程状态和调度算法选择等步骤。文中还提到了进程上下文切换的场景,如时间片用完、内存不足、高优先级进程需求等。最

深入浅出线程池

线程(thread)是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际 运作单位。一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线 程并行执行不同的任务。