操作系统学习(一):浅析操作系统进程调度算法

简介: 操作系统学习(一):浅析操作系统进程调度算法

0、前置知识



0.1 调度性能指标

     

周转时间:周转时间 = 完成时间 - 到达时间

响应时间:响应时间 = 首次运行时间 - 到达时间


0.2 上下文切换

     

当一个进程停止时,他的寄存器将被保存在这个内存位置。通过恢复这些寄存器(将他们的值放回实际的物理寄存器中),操作系统可以恢复运行该进程。这种技术叫做上下文切换


1、进程调度算法简单介绍



1.1 先进先出(FIFO


先进先出(First In First Out)调度是我们可以实现的最基本的算法,有时也被称为先到先服务(First Come First Served或FCFS)。


优点:简单,易于实现。


举个例子看看为什么FIFO不好:假设A(100s)、B(10s)、C(10s)三个工作几乎同时来到系统,A稍微比B早一点,B稍微比C早一点,那么,一定要等到A完成后,B才有机会运行。所以系统平均周转时间为:

(100+110+120)/ 3 = 110 s


这个问题通常被称作护航效应,简单来说,就是一些耗时较少的潜在资源消费者被排在重量级资源消费者之后。


那么如何解决这个问题呢?咱们接着往下看:


1.2 最短任务优先(SJF)


最短任务优先(Shortest Job First)很好地解决了这个问题。它的策略为:先运行最短的任务,然后运行次短的任务。


当在只考虑平均周转时间的情况下,SJF显然比FIFO要好的多,同样是上面的例子,平均周转时间为:

10+20+100)/ 3 = 50 s


事实上,考虑到所有工作同时到达的假设,我们几乎可以证明SJF确实是最优的调度算法。然而,当我们考虑实际:工作可以随时到达,这又会出现什么情况呢?


我们再用一个例子来说明:假设 A 在 t = 0 时到达,且需要运行 100s。而 B 和 C 在 t = 10 到达,且各需要运行 10s。用SJF,平均周转时间为:


(100 + (90+10)+ (100+10))/ 3 = 103.33


可以看到,SJF遭遇了同样的护航问题。


1.3 最短完成时间优先(STCF)

   

事实上,当 B 和 C 到达时,调度程序当然可以做其他事情:它可以抢占(preempt)工作 A,并决定运行另一个工作,或许稍后继续工作 A。那么,为了解决刚才遭遇的护航问题,我们可以向SJF添加抢占:称为最短完成时间优先(Shortest Time-to-Completion First,STCF)或抢占式最短作业优先(Preemptive Shortest Job First ,PSJF)调度程序。

 

他的做法是这样的:每当新工作进入系统时,它就会确定剩余工作和新工作中,谁的剩余时间最少,然后调度该工作。


补充一点:几乎所有现代化的调度程序都是抢占式的(preemptive),非常愿意停止一个进程以运行另一个进程。这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以进行上下文切换,临时停止一个运行进程,并恢复(或启动)另一个进程。


因此,在我们的例子中,STCF 将抢占 A 并运行 B 和 C 以完成。只有在它们完成后,才能调度 A 的剩余时间。平均周转时间为:

(120+10+20)/ 3 = 50 s


其实,考虑可抢占的假设,可以证明STCF为最优的调度算法。

那么,假如加入新的度量指标:响应时间呢?


还是使用刚才的例子:A 在时间 0 到达,B 和 C 在时间 10 达到,假如使用STCF,平均响应时间为:

(0 + 0 + 10)/ 3 = 3.33 s


而非抢占式的FIFO和SJF的响应时间都是0s,可以看出,STCF虽然有很好的周转时间,但对于响应时间和交互性上是糟糕的。就好像我们在终端按下回车,肯定不希望在10s之后才给我们显示内容。


为此,我们要引入一个新的调度算法。


1.4 轮转(RR)


轮转(RR)调度的基本思想很简单:RR 在一个时间片内运行一个工作,然后切换到运行队列中的下一个任务,而不是运行一个任务直到结束。它反复执行,直到所有任务完成。


请注意:时间片长度必须是时钟中断周期的倍数。


为了更详细地理解 RR,我们来看一个例子:假设 3 个任务 A(5s)、B (5s)和 C(5s) 在系统中同时到达。SJF 调度程序必须运行完当前任务才可运行下一个任务。相比之下,1s 时间片的 RR 可以快速地循环工作。


SJF的平均响应时间是:(0+5+10)/ 3 = 5 s


RR的平均响应时间是:(0+1+2)/ 3 = 1 s


如你所见,时间片长度对于 RR 是至关重要的。越短,RR 在响应时间上表现越好。然而,时间片太短是有问题的:突然上下文切换的成本将影响整体性能。因此,系统设计者需要权衡时间片的长度,使其足够长,以便摊销(amortize)上下文切换成本,而又不会使系统不及时响应。


可是,如果再回过头来看周转时间,我们会发现,RR几乎是最差的。但这并不奇怪,如果周转时间是我们的指标,那么 RR 确实是最糟糕的策略之一。直观地说,这应该是有意义的:RR 所做的正是延伸每个工作,只运行每个工作一小段时间,就转向下一个工作。而因为周转时间只关心作业何时完成。


2、多考虑一些情况



2.1 结合I/O

     

交互式作业正在执行 I/O 时,其他 CPU 密集型作业将运行,从而更好地利用处理器。


2.2 工作长度未知

     

事实上,在一个通用的操作系统中,操作系统通常对每个作业的长度知之甚少。因此,我们如何建立一个没有这种先验知识的 SJF/STCF?更进一步,我们如何能够将已经看到的一些想法与 RR 调度程序结合起来,以便响应时间也变得很好?这就是我们接下来要讲的问题:多级反馈队列(MLFQ)调度方法  操作系统学习(二):浅析多级反馈队列MLFQ


3、小结


     

按照我们介绍的顺序,几种调度算法可以这样串起来:


a2ea1260cf5d40238bfaeaa25c234731.png


3.1 各自的优缺点


       FIFO        优点:简单      


                       缺点:平均周转时间长(护航问题)


       SJF          优点:作业同时到达时,平均周转时间短


                        缺点:作业不同时到达时,同样面临护航问题


       STCF       优点:作业不同时到达时,平均周转时间短


                        缺点:响应时间长


       RR            优点:响应时间短


                        缺点:平均周转时间长


4、提到的其他技术



4.1 摊销(amortization)

     

摊销可以减少成本。


当系统某些操作有固定成本时,通常会使用摊销技术(amortization)。通过减少成本的频度(即执行较少次的操作),系统的总成本就会降低。例如,如果时间片设置为 10ms,并且上下文切换时间为 1ms,那么浪费大约 10%的时间用于上下文切换。如果要摊销这个成本,可以把时间片增加到 100ms。在这种情况下,不到 1%的时间用于上下文切换,因此时间片带来的成本就被摊销了。


4.2 重叠(overlap)


如有可能,重叠(overlap)操作可以最大限度地提高系统的利用率。重叠在许多不同的领域很有用,包括执行磁盘 I/O 或将消息发送到远程机器时。在任何一种情况下,开始操作然后切换到其他工作都是一个好主意,这也提高了系统的整体利用率和效率。


相关文章
|
30天前
|
算法 Linux 调度
深入理解Linux操作系统的进程管理
本文旨在探讨Linux操作系统中的进程管理机制,包括进程的创建、执行、调度和终止等环节。通过对Linux内核中相关模块的分析,揭示其高效的进程管理策略,为开发者提供优化程序性能和资源利用率的参考。
66 1
|
1月前
|
调度 开发者 Python
深入浅出操作系统:进程与线程的奥秘
在数字世界的底层,操作系统扮演着不可或缺的角色。它如同一位高效的管家,协调和控制着计算机硬件与软件资源。本文将拨开迷雾,深入探索操作系统中两个核心概念——进程与线程。我们将从它们的诞生谈起,逐步剖析它们的本质、区别以及如何影响我们日常使用的应用程序性能。通过简单的比喻,我们将理解这些看似抽象的概念,并学会如何在编程实践中高效利用进程与线程。准备好跟随我一起,揭开操作系统的神秘面纱,让我们的代码运行得更加流畅吧!
|
1月前
|
C语言 开发者 内存技术
探索操作系统核心:从进程管理到内存分配
本文将深入探讨操作系统的两大核心功能——进程管理和内存分配。通过直观的代码示例,我们将了解如何在操作系统中实现这些基本功能,以及它们如何影响系统性能和稳定性。文章旨在为读者提供一个清晰的操作系统内部工作机制视角,同时强调理解和掌握这些概念对于任何软件开发人员的重要性。
|
1月前
|
Linux 调度 C语言
深入理解操作系统:从进程管理到内存优化
本文旨在为读者提供一次深入浅出的操作系统之旅,从进程管理的基本概念出发,逐步探索到内存管理的高级技巧。我们将通过实际代码示例,揭示操作系统如何高效地调度和优化资源,确保系统稳定运行。无论你是初学者还是有一定基础的开发者,这篇文章都将为你打开一扇了解操作系统深层工作原理的大门。
|
1月前
|
存储 算法 调度
深入理解操作系统:进程调度的奥秘
在数字世界的心脏跳动着的是操作系统,它如同一个无形的指挥官,协调着每一个程序和进程。本文将揭开操作系统中进程调度的神秘面纱,带你领略时间片轮转、优先级调度等策略背后的智慧。从理论到实践,我们将一起探索如何通过代码示例来模拟简单的进程调度,从而更深刻地理解这一核心机制。准备好跟随我的步伐,一起走进操作系统的世界吧!
|
1月前
|
算法 调度 开发者
深入理解操作系统:进程与线程的管理
在数字世界的复杂编织中,操作系统如同一位精明的指挥家,协调着每一个音符的奏响。本篇文章将带领读者穿越操作系统的幕后,探索进程与线程管理的奥秘。从进程的诞生到线程的舞蹈,我们将一起见证这场微观世界的华丽变奏。通过深入浅出的解释和生动的比喻,本文旨在揭示操作系统如何高效地处理多任务,确保系统的稳定性和效率。让我们一起跟随代码的步伐,走进操作系统的内心世界。
|
11天前
|
Java Linux API
[JavaEE]———进程、进程的数据结构、进程的调度
操作系统,进程任务,PCB,PID,内存指针,文件描述符表,进程的调度,并发编程,状态,优先级,记账信息,上下文
|
1月前
|
运维 监控 Linux
Linux操作系统的守护进程与服务管理深度剖析####
本文作为一篇技术性文章,旨在深入探讨Linux操作系统中守护进程与服务管理的机制、工具及实践策略。不同于传统的摘要概述,本文将以“守护进程的生命周期”为核心线索,串联起Linux服务管理的各个方面,从守护进程的定义与特性出发,逐步深入到Systemd的工作原理、服务单元文件编写、服务状态管理以及故障排查技巧,为读者呈现一幅Linux服务管理的全景图。 ####
|
1月前
|
消息中间件 算法 调度
深入理解操作系统之进程管理
本文旨在通过深入浅出的方式,带领读者探索操作系统中的核心概念——进程管理。我们将从进程的定义和重要性出发,逐步解析进程状态、进程调度、以及进程同步与通信等关键知识点。文章将结合具体代码示例,帮助读者构建起对进程管理机制的全面认识,并在实践中加深理解。
|
12天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
145 80