草庐IT

Linux进程调度算法

yytarget 2023-03-28 原文

进程的状态

进程的基本状态

  • 就绪：进程已获得除处理机以外的所需资源，等待分配处理机资源
  • 执行：进程正在占用处理机资源执行
  • 阻塞：进程等待某种条件，在条件满足之前无法执行。例如发起I/O系统调用，等待I/O中断发生

挂起

挂起指将暂不执行的进程换出到外存，节省内存空间。
与阻塞相比都是进程暂停执行的状态，但：

  • 阻塞表示进程正在等待一个事件的发生，阻塞状态下收到信号会切换为就绪状态
  • 挂起表示进程被换出到外存，挂起状态下被激活会被载入到内存，切换为非挂起状态

挂起状态进程按照是否阻塞分为：

  • 挂起就绪状态：进程在外存中，但只要被载入内存就可执行
  • 挂起阻塞状态：进程在外存中等待一个事件，即使被载入内存(激活)也无法执行

睡眠

Linux将进程的阻塞状态进一步细分为：

  • 暂停：不需要等待资源
  • 浅睡眠：需要等待资源且睡眠状态能被信号唤醒
  • 深睡眠：需要等待资源且睡眠状态不能被信号唤醒

进程调度算法

分类

  • 按照CPU分配方式：非抢占式，抢占式
  • 按照系统分时方式：批处理系统，交互系统，实时系统和多处理机调度

进程饥饿

  • 指某个进程无限等待，无法被调度

批处理系统调度算法

调度算法的目标：

  • 吞吐量(每小时最大作业数)
  • 周转时间(每作业从提交到完成时间的统计平均时间)
  • CPU利用率(最好令CPU始终忙碌)

1.先来先服务算法(FCFS)

  • 依据进程进入就绪状态的先后顺序排列，非抢占式 不公平
  • 优点：易于理解，便于实现，只需一个就绪队列
  • 缺点：平均等待时间波动大(例如短进程排在长进程后)；I/O与CPU资源利用率低(CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待)

2.最短进程优先算法(SPN或SJF)

  • 预知就绪队列中执行时间最短进程占用CPU进入运行状态，非抢占式 不公平
  • 优点：相对于FCFS提高了平均周转时间
  • 缺点：可能导致饥饿；对长作业不公平；需要预知未来(预估下一个CPU计算的持续时间：询问用户或用历史的执行时间来预估未来的执行时间)

3.最短剩余时间优先算法(SRT或SRTN)

  • 最短进程优先的抢占式版本，若新进程比正在执行的进程剩余时间短，则它优先执行， 抢占式 不公平
  • 优缺点同SPN

4.最高响应比优先算法(HRRN)

  • 响应比：作业等待时间/作业运行所需时间；响应比大的进程优先，非抢占式 不公平
  • 优先：同时考虑了等待时间和执行时间，既优先考虑短作业(进程)，也防止长作业(进程)无限等待的饥饿

交互系统(分时系统)调度算法

1.时间片轮转算法(RR)

  • 将所有就绪进程排成一个队列，按照时间片轮转调度，用完时间片的进程排到队列末尾，抢占式 公平
  • 优点：没有饥饿问题
  • 缺点：当时间片太小时，产生大量的上下文切换，吞吐量低；当时间片太长时，等待时间过长，不能保证实时性，极限情况退化成FCFS

2.多级队列调度算法(MQ)

  • 优先级高的进程先运行，同优先级的进程轮转。当高优先级队列中没有进程后，再调度下一级队列。
  • 将就绪队列划分为多个独立的子队列，且每个队列拥有自己的调度策略(上述)；队列间的调度采用固定的优先级：先处理前台队列，后处理后台队列。每个队列都得到一个确定的能够调度其进程的CPU总时间
  • 缺点：可能导致饥饿问题

3.多级反馈队列算法(MLFQ)

  • 进程可在不同队列间移动的多级队列算法(MQ)；优先级高的队列先执行，优先级越高，时间片越短；若一个进程在当前队列规定时间片内无法执行完毕，则移动到下一个队列的队尾
  • 特征：CPU密集型进程的优先级下降很快；I/O密集型进程停留在高优先级
  • 缺点：可能导致饥饿问题：不断有新更高优先级的进程加入

4.公平共享调度(FSS)

  • 保证不重要的组无法垄断资源：未使用的资源按比例分配；没有达到资源使用率目标的组获得更高的优先级 公平

5.彩票法

  • 向进程提供各种系统资源的彩票。调度时随机抽取彩票，拥有该彩票的进程得到资源
  • 可给重要进程更多的彩票；协作进程可能交换彩票

实时系统的调度算法

目标：满足任务的截止时间。即若有一个任务需要执行，实时系统会马上执行该任务，不会有较长的延时。

1.速率单调调度算法(RM)

  • 通过周期安排优先级，周期越短优先级越高
  • 执行周期最短的任务

2.最早截止时间优先算法(EDF)

  • 截止时间越早优先级越高
  • 执行截止时间最早的任务

多处理机的调度

特征：多个处理机组成一个多处理机系统；处理机间可负载共享

对称多处理机(SMP)调度

  • 截止时间越早优先级越高，每个处理器运行自己的调度程序
  • 调度程序对共享资源的访问需要进行同步

分为静态进程分配和动态进程分配(负载均衡)：

  • 静态进程分配：进程从开始到结束都被分配到一个固定的处理机上执行；每个处理机有自己的就绪队列；优点：调度开销小；缺点：但是各处理机可能忙闲不均
  • 动态进程分配(负载均衡)：进程在执行中可分配到任意空闲处理机执行；所有处理机共享一个公共的就绪队列；优点：各处理机的负载是均衡的；缺点：调度开销大

优先级反置

  • 操作系统出现高优先级进程长时间等待低优先级进程所占用资源的现象
  • 基于优先级的可抢占调度算法存在优先级反置

解决方法：

  1. 优先级继承：占用资源的低优先级进程继承申请资源的高优先级进程的优先级；
  • 这种情况只在占有资源的低优先级进程被阻塞时，才提高占有资源进程的优先级
  1. 优先级天花板协议(PCP)：占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同；
  • 不管是否发生等待，都提升占用资源进程的优先级
  • 优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会阻塞
Linux进程调度listrongul

有关Linux进程调度算法的更多相关文章

  1. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  2. ruby - 通过 ruby​​ 进程共享变量 - 2

    我正在编写一个gem，我必须在其中fork两个启动两个webrick服务器的进程。我想通过基类的类方法启动这个服务器，因为应该只有这两个服务器在运行，而不是多个。在运行时，我想调用这两个服务器上的一些方法来更改变量。我的问题是，我无法通过基类的类方法访问fork的实例变量。此外，我不能在我的基类中使用线程，因为在幕后我正在使用另一个不是线程安全的库。所以我必须将每个服务器派生到它自己的进程。我用类变量试过了，比如@@server。但是当我试图通过基类访问这个变量时，它是nil。我读到在Ruby中不可能在分支之间共享类变量，对吗？那么，还有其他解决办法吗？我考虑过使用单例，但我不确定这是

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. ruby - 无法在 Ruby 中将 ffmpeg 作为子进程运行 - 2

    我正在尝试使用以下代码通过将ffmpeg实用程序作为子进程运行并获取其输出并解析它来确定视频分辨率:IO.popen'ffmpeg-i'+path_to_filedo|ffmpegIO|#myparsegoeshereend...但是ffmpeg输出仍然连接到标准输出并且ffmepgIO.readlines是空的。ffmpeg实用程序是否需要一些特殊处理？或者还有其他方法可以获得ffmpeg输出吗？我在WinXP和FedoraLinux下测试了这段代码-结果是一样的。 最佳答案 要跟进mouviciel的评论，您需要使用类似pope

  5. Ruby 守护进程导致 ActiveRecord 记录器 IOError - 2

    我目前正在用Ruby编写一个项目，它使用ActiveRecordgem进行数据库交互，我正在尝试使用ActiveRecord::Base.logger记录所有数据库事件具有以下代码的属性ActiveRecord::Base.logger=Logger.new(File.open('logs/database.log','a'))这适用于迁移等(出于某种原因似乎需要启用日志记录，因为它在禁用时会出现NilClass错误)但是当我尝试运行包含调用ActiveRecord对象的线程守护程序的项目时脚本失败并出现以下错误/System/Library/Frameworks/Ruby.frame

  6. ruby - 在 ruby​​ 中生成一个进程，捕获 stdout，stderr，获取退出状态 - 2

    我想从ruby​​rake脚本运行一个可执行文件，比如foo.exe我希望将foo.exe的STDOUT和STDERR输出直接写入我正在运行rake任务的控制台.当进程完成时，我想将退出代码捕获到一个变量中。我如何实现这一目标？我一直在玩backticks、process.spawn、system但我无法获得我想要的所有行为，只有部分更新:我在Windows上，在标准命令提示符下，而不是cygwin 最佳答案 system获取您想要的STDOUT行为。它还返回true作为零退出代码，这可能很有用。$?填充了有关最后一次system调

  7. ruby-on-rails - 如何用不同的用户运行nginx主进程 - 2

    A/ctohttp://wiki.nginx.org/CoreModule#usermaster进程曾经以root用户运行，是否可以以不同的用户运行nginxmaster进程？ 最佳答案 只需以非root身份运行init脚本(即/etc/init.d/nginxstart)，就可以用不同的用户运行nginxmaster进程。如果这真的是你想要做的，你将需要确保日志和pid目录(通常是/var/log/nginx&/var/run/nginx.pid)对该用户是可写的，并且您所有的listen调用都是针对大于1024的端口(因为绑定(

  8. Ruby 守护进程和 JRuby - 备选方案 - 2

    我有一个应用程序正在从Ruby迁移到JRuby(由于需要通过Java提供更好的Web服务安全支持)。我使用的gem之一是daemons创建后台作业。问题在于它使用fork+exec来创建后台进程，但这对JRuby来说是禁忌。那么-是否有用于创建后台作业的替代gem/wrapper？我目前的想法是只从shell脚本调用rake并让rake任务永远运行......提前致谢，克里斯。更新我们目前正在使用几个与Java线程相关的包装器，即https://github.com/jmettraux/rufus-scheduler和https://github.com/philostler/acts

  9. ruby-on-rails - Rails - Carrierwave 进程抛出 ArgumentError : no images in this image list - 2

    在尝试实现应用auto_orient的过程之后!对于我的图片，我收到此错误:ArgumentError(noimagesinthisimagelist):app/uploaders/image_uploader.rb:36:in`fix_exif_rotation'app/controllers/posts_controller.rb:12:in`create'Carrierwave在没有进程的情况下工作正常，但在添加进程后尝试上传图像时抛出错误。流程如下:process:fix_exif_rotationdeffix_exif_rotationmanipulate!do|image|

  10. ruby-on-rails - Ruby 长时间运行的进程对队列事件使用react - 2

    我有一个将某些事件写入队列的Rails3应用。现在我想在服务器上创建一个服务，每x秒轮询一次队列，并按计划执行其他任务。除了创建ruby​​脚本并通过cron作业运行它之外，还有其他稳定的替代方案吗？ 最佳答案 尽管启动基于Rails的持久任务是一种选择，但您可能希望查看更有序的系统，例如delayed_job或Starling管理您的工作量。我建议不要在cron中运行某些东西，因为启动整个Rails堆栈的开销可能很大。每隔几秒运行一次它是不切实际的，因为Rails上的启动时间通常为5-15秒，具体取决于您的硬件。不过，每天这样做几

随机推荐