操作系统——处理机的调度与死锁

2024-02-22 07:40

本文主要是介绍操作系统——处理机的调度与死锁,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

处理机调度的层次和调度算法的目标

处理机调度的层次

处理机调度的基本概念

处理机调度的层次

  • 高级调度:又称为作业调度或长程调度(Long-Term Scheduling),用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后将新创建的进程排在就绪队列上,准备执行。 因此有时也称作业调度为接纳调度。主要用于多道批处理系统,而在分时和实时系统中不设置高级调度

在每次执行作业调度时,都须作出两个决定:
接纳多少作业——每次接纳多少作业进入内存,即允许多少个作业同时在内存中运行—多道程序度。其确定应根据系统的规模、运行速度等情况综合考虑。

接纳哪些作业——应接纳哪些作业从外存调入内存,取决于所采用的调度算法。如先来先服务,短作业优先等

  • 低级调度:通常也称为进程调度或短程调度(Short-Term Scheduling),用来决定就绪队列中的哪个进程应获得处理机,然后再由分派程序把处理机分配给该进程。**为最基本的一种调度,**三种OS中都有

进程调度可采用下述两种调度方式:

非抢占方式(Non-preemptive Mode)
一旦把处理机分配给某进程后,便让该进程一直执行,直至该进程完成或发生某事件而被阻塞时,才把处理机分配给其他进程,决不允许进程抢占已分配出去的处理机。
评价:实现简单、系统开销小;适用于大多数的批处理OS,但在要求比较严格的实时系统中,不宜采用这种调度方式

抢占方式(Preemptive Mode)
允许调度程序根据某种原则,去暂停某个正在执行的进程,将处理机重新分配给另一进程。

抢占的原则:

优先权原则:优先权高的可以抢占优先级低的进程的处理机。

短作业(进程)优先原则:短作业(进程)可以抢占长作业(进程)的处理机。

时间片原则:各进程按时间片运行,一个时间片用完时,停止该进程执行重新进行调度。

  • 中级调度:又称中程调度(Medium-Term Scheduling)。引入目的是为了提高内存利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存资源,而将它们调之外存去等待,把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时,由中级调度来决定把外存上的哪些又具备运行条件的就绪进程,重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待进程调度。
    中级调度实际上就是存储器管理中的对换功能

进程调度的运行频率最高,在分时系统中通常是10~100ms便进行一次进程调度,因而进程调度算法不能太复杂,以免占用太多的CPU时间。

作业调度是发生在一个作业运行完毕,退出系统,而需要重新调度一个作业进入内存时,故作业调度的周期较长,大约几分钟一次。因而也允许作业调度算法花费较多的时间。

中级调度的运行频率,基本上介于进程调度和作业调度之间。

调度队列模型

  1. 仅有进程调度的调度队列模型
    在分时系统中,通常仅设置进程调度。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表,形式取决于OS类型和所采用的调度算法。
    在分时系统中就绪进程组织成FIFO队列形式,按时间片轮转方式运行。

在这里插入图片描述

  1. 具有高级和低级调度的调度队列模型
    在批处理系统中,不仅需要进程调度,而且还需要作业调度,由作业调度按一定的调度算法,从外存的后备队列中选择一批作业调入内存,并为它们建立进程,送入就绪队列,然后才由进程调度算法按照一定的进程调度算法,选择一个进程,把处理机分配给该进程。

在这里插入图片描述

  1. 同时具有三级调度的调度队列模型
    当在OS中引入中级调度后,可以把进程的就绪状态分为内存就绪和外存就绪。也可以把阻塞状态分为内存阻塞和外存阻塞两种状态。在调出操作的作用下,可使进程状态由内存就绪转变为外存就绪,由内存阻塞转变为外存阻塞;在中级调度的作用下,又可使外存就绪转变为内存就绪。

在这里插入图片描述

处理机调度的算法的目标

  1. 处理机调度算法的共同目标
  • 资源利用率
  • 公平性
  • 平衡性
  • 策略强制执行
  1. 批处理系统的目标
  • 周转时间短
  • 系统吞吐量高
  • 处理机利用率好
  1. 分时系统的目标
  • 响应时间快
  • 均衡性
  1. 实时系统的目标
  • 截止时间的保证
  • 可预测性

实时调度的算法分类

分类:

  • 根据实时任务性质的不同,分为硬实时调度算法和软实时调度算法;
  • 按调度方式的不同,分为非抢占调度算法和抢占调度算法;
  • 根据调度程序调度时间的不同,分为静态调度算法和动态调度算法。
  • 多处理机环境下,可分为集中式调度和分布式调度两种算法

最早截止时间优先EDF算法

根据任务的截止时间来确定任务的优先级。截止时间越早,其优先级越高。该算法要求在系统中保持一个实时任务就绪队列,该队列按各任务截止时间的早晚排序,调度程序在选择任务时总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行。
EDF算法既可以用于抢占式调度,也可用于非抢占式调度。

在这里插入图片描述
抢占式调度方式用于周期实时任务
下图中有两个周期性任务,任务A的周期时间为20ms,每个周期的处理时间为10ms;任务B的周期时间为50ms,每个周期的处理时间为25ms
在这里插入图片描述

解:
在t=0时,A1和B1同时到达A1的开始截止时间为10,B1为25,所以A1执行,当A1执行完后,只有B1了,所以让B1执行10,然后A2到达,此时B1开始截止时间为35,A2为30,所以A2执行10,然后只有B1了,所以让B1继续执行10,此时A3到达,A3开始截止时间为50,B1为45,所以B1继续执行5(B1全部执行完),后只有A3了,所以让A3执行5,此时B2到了,但是B2开始截止时间为75,A3为55,所以A3继续执行5,然后只剩下了B2,所以让B2执行5,此时A4又到了,A4的开始截止时间为70,B2为80,所以A4执行10,然后又是只有B2了,所以B2执行执行10,然后A5到了,A5的开始截止时间为90,B2的也是90,为了符合实际和节省资源,所以让B2继续执行10,然后A5执行10。

最低松弛度优先LLF算法

该算法是根据任务紧急(或松弛)的程度,来确定任务的先级。任务的紧急程度越高,为之赋予的优先级就越高。
例如,任务A在200ms时必须完成,本身运行时间100ms,则必须在100ms之前调度执行,A任务的紧急(松弛)程度为100ms,又如任务B在400ms是必须完成,需运行150ms,其松弛程度为250ms.

该算法主要用于抢占调度方式中

假如在一个实时系统中,有两个周期型实时任务A,B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms;由此可得知A,B任务每次必须完成的时间分别为A1、A2、A3…和B1、B2、B3…

在这里插入图片描述

解:
做此题需要明白:松弛度 = 完成 截止时间 - 需要运行时间 - 当前时刻
当某一时刻算出某一进程的松弛度为0,代表着这个进程必须马上执行!!!!!
在t=0时,A1的松弛度为:20-10-0=10,B1的松弛度为50-25-0=25,所以让A1执行,然后剩下了B1,因为没得选所以让B1执行,在t=20时,B1的松弛度为50-25-20=15,A2到了,A2的松弛度为:40-10-20=10不为0,没有到达必须要运行的地步,所以B1继续运行,当t=30时,A2的松弛度为0,需要马上执行A2,然后A3到了,A3松弛度为10,B1松弛度为50-5-40=5,切换B1运行,后只剩下A3,运行A3,当t=50时B2到了,B2松弛度为100-25-50=25,A3松弛度为60-5-50=5,所以继续执行A3,然后只剩下B2了,所以执行B2, 当t=60时A4到了,A4松弛度为10,B2的松弛度为100-20-60=20,而A4的松弛度并未达到0,所以继续运行B2,当t=70时,A4的松弛度为0,所以运行A4,之后A5到达,A5的松弛度为10,B2的松弛度为100-10-80=10,两者相等,但是为了符合实际和节省资源,所以让B2继续执行10,然后A5执行10。

这篇关于操作系统——处理机的调度与死锁的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/734569

相关文章

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

springboot的调度服务与异步服务使用详解

《springboot的调度服务与异步服务使用详解》本文主要介绍了Java的ScheduledExecutorService接口和SpringBoot中如何使用调度线程池,包括核心参数、创建方式、自定... 目录1.调度服务1.1.JDK之ScheduledExecutorService1.2.spring

MySql死锁怎么排查的方法实现

《MySql死锁怎么排查的方法实现》本文主要介绍了MySql死锁怎么排查的方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录前言一、死锁排查方法1. 查看死锁日志方法 1:启用死锁日志输出方法 2:检查 mysql 错误

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

MYSQL事务死锁问题排查及解决方案

《MYSQL事务死锁问题排查及解决方案》:本文主要介绍Java服务报错日志的情况,并通过一系列排查和优化措施,最终发现并解决了服务假死的问题,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录问题现象推测 1 - 客户端无错误重试配置推测 2 - 客户端超时时间过短推测 3 - mysql 版本问

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器?Airflow 调度器工作机制配置Airflow调度器调优及优化建议最

高效管理你的Linux系统: Debian操作系统常用命令指南

《高效管理你的Linux系统:Debian操作系统常用命令指南》在Debian操作系统中,了解和掌握常用命令对于提高工作效率和系统管理至关重要,本文将详细介绍Debian的常用命令,帮助读者更好地使... Debian是一个流行的linux发行版,它以其稳定性、强大的软件包管理和丰富的社区资源而闻名。在使用

龙蜥操作系统Anolis OS-23.x安装配置图解教程(保姆级)

《龙蜥操作系统AnolisOS-23.x安装配置图解教程(保姆级)》:本文主要介绍了安装和配置AnolisOS23.2系统,包括分区、软件选择、设置root密码、网络配置、主机名设置和禁用SELinux的步骤,详细内容请阅读本文,希望能对你有所帮助... ‌AnolisOS‌是由阿里云推出的开源操作系统,旨

五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

《五大特性引领创新!深度操作系统deepin25Preview预览版发布》今日,深度操作系统正式推出deepin25Preview版本,该版本集成了五大核心特性:磐石系统、全新DDE、Tr... 深度操作系统今日发布了 deepin 25 Preview,新版本囊括五大特性:磐石系统、全新 DDE、Tree

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3