【计算机系统】详解进程及进程调度算法(时间片管理、多级队列)

简介: 【计算机系统】详解进程及进程调度算法(时间片管理、多级队列)

详解进程及其调度算法

1 基本概念

进程与程序的关系是:程序是存储在文件中的、带有结构和顺序信息(用于控制指令执行次序)的指令列表,进程是程序的运行实例。通俗来讲,程序描述了如何处理一个事务,进程按程序的描述实际执行之。相同的程序可以多次执行,每次执行操作系统都将创建一个独立的进程,并开始读取指令列表。


image.png

进程更正式的定义是:计算机中的程序关于某数据集合的一次运行活动,是系统进行资源分配和调度的最小单位,是操作系统结构的基础。进程是线程的容器,同时包含了内存、句柄等计算机资源,如图1所示。


数据集合包括指令在内存中的版本、程序中使用的变量以及其他相关元数据。其中变量和元数据是可变的,称为进程状态。进程主要的五种状态如图2所示。


image.png

重点辨析就绪和阻塞状态。


就绪:进程分配的时间片已用完,或在中断机制下,有更高优先级的进程打入,此时进程进入就绪队列等待下一次被选中


阻塞:进程所需要的资源或某些事件不满足要求,如暂时不能访问某一资源、操作系统尚未完成服务、系统正在初始化I/O设备、等待用户的输入信息等,当这些系统资源被满足后,进程从阻塞队列出队而进入就绪队列等待CPU资源。


简言之,就绪状态等待CPU资源,而阻塞状态等待CPU以及所需的其他系统资源。


进程状态区分了同一程序的多道进程,操作系统级别用唯一进程标识符(Process IDentifier, PID)识别不同的进程。

2 进程调度

进程的运行,是其指令在CPU中执行的行为。CPU是系统最主要的资源,而操作系统最基本的作用是管理系统资源,因此操作系统负责管理系统进程,以及在任意给定的时间选择哪一个进程运行(仅考虑单核系统)。现代操作系统中,执行上述职能的部件是调度器。调度器选中某道进程后,由其子部件分派器将该进程由就绪状态引入到运行状态。因此调度是通过一定算法选择某道进程,并将其从就绪状态切换到运行状态的过程。


2.1 时间片管理

在抢占式调度器中,允许某个特定进程运行一段时间后,切换到就绪队列等待调度器下一次选中,而将另一个进程从就绪队列中引出,并设置为运行状态。这里的时间称为时间片。


image.png

由于调度器执行调度决策本身需要占用系统处理时间,这部分进程外的额外时间称为调度开销。调度开销中的最大成分是上下文切换,即CPU从执行一道进程或线程切换到执行另一道进程或线程的动作,如图3所示。上下文切换时要进行保护现场和恢复现场,即保存某道进程被抢占或阻塞前最后一次运行时的执行环境,和在下一次运行时复现,这里的执行环境包括堆栈、程序计数器以及其他操作系统结构等。


image.png

若时间片太短,由于调度开销的存在,操作系统将频繁执行调度活动,使系统处理资源被浪费;若时间片太长,则就绪队列的其他进程不得不在轮转期间等待更长的时间,表现出应用程序的未响应或缺乏响应状态。


时间片大小没有随看技术进步(主要指CPU处理速度)而大幅变化,原因在于:

(1) 人类对响应性的感知能力没有改变,没有必要为此缩短时间片;

(2) 系统的复杂性和在其上运行的应用程序的数量也在以高速率提升,以实现其丰富的功能,即相较原有系统多出的运算资源又被分配给了更多的进程,而非延长每一道进程的时间。


现代系统中时间片大小一般在大概10~200ms的范围内(Windows操作系统为10ms), 在非常快速的平台上时间片更小(低至约1ms)。


时间片大小的范围设定能够用作实现进程优先级的一种手段:高优先级的进程应该获得较大份额的可用处理资源。一种特例是,如果进程是IO密集型的,它们执行IO时会被堵塞而无视其优先级(分配的时间片再长也会进入阻塞队列)。

2.2 调度算法


image.png

image.png

在基础算法上,进行了调度算法的改进。


(1) 多级队列(MLQ, Multilevel Queue):按进程性质设置若干就绪队列,每个队列可执行不同调度算法。例如计算密集型进程队列中执行FCFS调度;系统进程队列执行RR调度等。根据系统的工作特点,为不同的进程队列分配不同的CPU处理时间。值得注意的是,每级队列执行的调度算法,不会影响到其他进程队列。


(2) 多级反馈队列(MLFQ, Multilevel Feed-back Queue):以MLQ为基础,但与之不同在于:进程能够在不同队列中移动以允许调度过程达到一种平衡——短期调度获得任务响应性,长期调度确保公平性和系统效率;队列按优先级组织。


进程移动的基本规则是:


①若进程用尽时间片仍未完成任务,则降到下一级进程队列;

②若进程在时间片内让出控制(如发生阻塞),则保留在该级队列;

③若进程因为执行IO而发生阻塞,则会提升到上一级进程队列。


image.png

以科学计算模拟为例,由于其计算时间较长以至于在若干个时间片内无法处理完毕,进程将逐次被降级,并留在较低级的进程队列中接受RR调度。当科学计算结束后,需要通过IO将结果反馈给用户,则该进程开始逐步回升到高优先级队列中。只有当最高优先级队列中进程临时用尽时,才有机会执行低级队列中的进程。由于进程的优先级根据其行为动态变化,因此该算法灵活性得到保证。


image.png

目录
相关文章
|
12天前
|
算法 调度 UED
深入理解操作系统:进程调度与优先级队列
【10月更文挑战第31天】在计算机科学的广阔天地中,操作系统扮演着枢纽的角色,它不仅管理着硬件资源,还为应用程序提供了运行的环境。本文将深入浅出地探讨操作系统的核心概念之一——进程调度,以及如何通过优先级队列来优化资源分配。我们将从基础理论出发,逐步过渡到实际应用,最终以代码示例巩固知识点,旨在为读者揭开操作系统高效管理的神秘面纱。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
9天前
|
算法 调度 UED
深入理解操作系统:进程管理与调度策略
【10月更文挑战第34天】本文旨在探讨操作系统中至关重要的一环——进程管理及其调度策略。我们将从基础概念入手,逐步揭示进程的生命周期、状态转换以及调度算法的核心原理。文章将通过浅显易懂的语言和具体实例,引导读者理解操作系统如何高效地管理和调度进程,保证系统资源的合理分配和利用。无论你是初学者还是有一定经验的开发者,这篇文章都能为你提供新的视角和深入的理解。
29 3
|
11天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
13天前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
46 4
|
14天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
11天前
|
算法 Linux 调度
深入理解操作系统之进程调度
【10月更文挑战第31天】在操作系统的心脏跳动中,进程调度扮演着关键角色。本文将深入浅出地探讨进程调度的机制和策略,通过比喻和实例让读者轻松理解这一复杂主题。我们将一起探索不同类型的调度算法,并了解它们如何影响系统性能和用户体验。无论你是初学者还是资深开发者,这篇文章都将为你打开一扇理解操作系统深层工作机制的大门。
22 0
|
4月前
|
运维 关系型数据库 MySQL
掌握taskset:优化你的Linux进程,提升系统性能
在多核处理器成为现代计算标准的今天,运维人员和性能调优人员面临着如何有效利用这些处理能力的挑战。优化进程运行的位置不仅可以提高性能,还能更好地管理和分配系统资源。 其中,taskset命令是一个强大的工具,它允许管理员将进程绑定到特定的CPU核心,减少上下文切换的开销,从而提升整体效率。
掌握taskset:优化你的Linux进程,提升系统性能
|
4月前
|
弹性计算 Linux 区块链
Linux系统CPU异常占用(minerd 、tplink等挖矿进程)
Linux系统CPU异常占用(minerd 、tplink等挖矿进程)
163 4
Linux系统CPU异常占用(minerd 、tplink等挖矿进程)
|
3月前
|
算法 Linux 调度
探索进程调度:Linux内核中的完全公平调度器
【8月更文挑战第2天】在操作系统的心脏——内核中,进程调度算法扮演着至关重要的角色。本文将深入探讨Linux内核中的完全公平调度器(Completely Fair Scheduler, CFS),一个旨在提供公平时间分配给所有进程的调度器。我们将通过代码示例,理解CFS如何管理运行队列、选择下一个运行进程以及如何对实时负载进行响应。文章将揭示CFS的设计哲学,并展示其如何在现代多任务计算环境中实现高效的资源分配。

热门文章

最新文章