操作系统算法整理+汇总
2021-05-29 07:01
标签：out 价值 first cpu 时间片 线程管理 系统 自己的 运行不了 就是 进程和线程管理中的算法 调度算法分类 下面我们分别来看一下这些操作系统中的算法。 批处理操作系统中的算法 在交互式用户环境中，因为为了用户体验，所以会避免长时间占用进程，所以需要抢占式算法。由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况，抢占式也是必须的。 在实时系统中，抢占式不是必须的，因为进程知道自己可能运行不了很长时间，通常很快的做完自己的工作并挂起。 关键指标 吞吐量(throughout) 是系统每小时完成的作业数量。综合考虑，每小时完成 50 个工作要比每小时完成 40 个工作好。 先来先服务 这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。 不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。 最短作业优先 未完待续... 操作系统算法整理+汇总 标签：out 价值 first cpu 时间片 线程管理 系统 自己的 运行不了 就是 原文地址：https://www.cnblogs.com/h694879357/p/14771247.html
进程和线程在调度时候出现过很多算法，这些算法的设计背景是当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争 CPU 时间片。 那么如何选择合适的进程/线程运行是一项艺术。当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个 CPU 可用，那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在，它就是做这件事儿的，调度程序使用的算法叫做 调度算法(scheduling algorithm) 。
针对不同的操作系统环境，也有不同的算法分类，操作系统主要分为下面这几种
设计目标
批处理系统广泛应用于商业领域，比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中，一般会选择使用非抢占式算法或者周期性比较长的抢占式算法。这种方法可以减少线程切换因此能够提升性能。
通常有三个指标来衡量系统工作状态：吞吐量、周转时间和 CPU 利用率
周转时间(Turnaround time) 是一种平均时间，它指的是从一个批处理提交开始直到作业完成时刻为止的平均时间。该数据度量了用户要得到输出所需的平均等待时间。周转时间越小越好。
CPU 利用率(CPU utilization) 通常作为批处理系统上的指标。即使如此，CPU 利用率也不是一个好的度量指标，真正有价值的衡量指标是系统每小时可以完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。
下面我们就来认识一下批处理中的算法。
很像是先到先得。。。它是一种非抢占式的算法。此算法将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。
批处理中的第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法