中断

中断或中断机制是实现多道程序设计与并发执行的基础和必要条件。如果没有中断，操作系统就无法获得系统的控制权，就不会将处理机（也作为一种资源）分派给不同的进程而实现并发执行。

中断响应的步骤

终止当前程序执行
保存断点信息
转相应中断处理程序

在并发环境下，用户程序不需要为添加任何特定代码中断。

为适应中断产生，在指令周期末端要增加一个中断阶段。

中断处理的类型

强迫性中断
- 时钟中断：如硬件实时时钟到时等；
- 输入输出中断：设备数据传输结束/设备出错等。
- 控制台中断：系统操作员通过控制台发出命令等。
- 硬件故障中断：如掉电、内存效验错等。
- 程序性中断：如地址越界、数据溢出，除零等。
自愿性中断

程序事先有意识安排的；通常执行访管指令（系统调用）而引起的，其目的要求系统提供某种服务。

中断处理过程

当中断事件发生时，中断装置根据中断类别自动地将对应的PSW和PC分别送入程序状态字和程序计数器中，如此便转入到对应的中断处理程序，如图6.4所示。

应当说明的是，图6.4所示的中断处理是比较典型的形式。对于系统的中断处理，硬件要保存哪些信息，保存到什么地方，这些随CPU（或系统）而不同。

时钟中断

时钟中断是现代操作系统不可或缺的控制手段，所以在此特别强调。时钟中断管理及维护的内容：

进程管理：用于时间片轮转处理机调度算法的系统中，记录进程已占用处理机时间等。
作业记录：记录作业在输入井中等待的时间等。
资源管理：动态统计运行进程占有和使用处理机等资源的时间等。
事件处理：实时系统中定时向被控制的对象发送控制信号。
系统维护：定时运行死锁检测程序等，定时运行系统记帐程序等。
实现软件时钟：利用硬件间隔时钟和一个存储单元可以实现软件时钟。例如，假设硬件间隔时钟每隔10ms产生一次中断，某一程序每隔1000ms执行一次，则可以这样确定该程序的执行时刻。

中断的应用使得系统的资源利用率得到提高，但即使利用了中断，在单道情况下处理机仍有可能未得到充分的利用。例如，如果I/O操作的时间比较长，则大部分时间处理机是空闲的。解决这个问题的方法是允许多道用户程序同时处于活动状态。

某程序（进程）等待I/O上，可调度另一程序，这时处理机与外设都在“忙”。

由此，说明多道程序设计是提高系统效率又一重要的技术思想。

进程调度

三个层次的进程调度

进程调度是把进程指定到一个处理机中执行。在许多系统中，这个调度活动分成三个层次：高级调度、中级调度和低级调度。

高级调度：

在创建新进程时，决定是否把进程添加到当前活跃的进程集合中。
中级调度：

是属于交换功能的一部分，它需要决定（部分）进程是否不再处于活动空间中。
低级调度：

真正决定下一次执行哪一个就绪进程。图6.6 给出了进程状态转换三个层次的调度。

高级调度

一个作业的处理可以分若干相对独立的作业步，每个作业步可能对应一个进程。例如，一个C语言程序，作为批作业处理大致应当包括如下步骤：

运行C语言编译程序对C代码进行编译。
对所编译产生的浮动程序进行连接装配。
执行所产生的目标代码程序。

以上三个步骤运行的是三个不同的程序，因而需要三个进程完成。

低级调度/处理机调度

处理机调度（CPU scheduling）是指CPU在可运行实体之间的分配。如图6.7中虚框的活动空间部分。处理机资源管理需要解决三个问题：

依什么原则分配处理机，即确定处理机调度算法。
什么时候分配处理机，即确定处理机调度时机。
如何分配处理机，即给出处理机调度过程。

中断和进程状态转换

中断作为引起进程状态转换的本质加以阐述。我们仍以进程的三个基本状态为例说明四条有向边所表明的状态转移。图6.9给出了由中断引起进程状态转移的形式描述（图中省略了关于中断仲裁或控制部分）。其中，虚线表示事件，或系统产生的操作。

申请I/O服务：

运行中进程需要在某处执行有关I/O指令以进行数据输入输出。此时用户利用的指令要么是访管指令，要么是某种系统调用，无论那种形式，都属于自愿性中断而进入中断处理；也可能由于没有所要求空闲I/O设备而进入阻塞状态，进入由于等待某类I/O的阻塞队列。

I/O完成

I/O外设数据传输完成产生一个I/O完成中断信号而进入I/O中断处理。当前进程状态信息被保存后，系统分析中断原因，检查是否有等待此次I/O完成的在阻塞队列中的进程，如果有，则通过某种算法从阻塞队列中摘出一个相关的进程而进入就绪队列。这就是I/O完成，是由于I/外设完成中断信号所引起的从阻塞到就绪状态的转移。

时间片到/抢占

这条边表明状态转移就比较明显了，就是由于系统定时间隔时钟中断所引起的当前进程的一个时间片用完而从运行状态转移到就绪状态。需要说明的是，这是分时系统所具有的最常见的状态转移。由于现代通用操作系统大多都具有分时特征，因而时钟在系统中是必不可少的。

调度

当我们清楚了以上状态转移原因，这条边所表明的状态转移也很容易理解。这涉及到调度的时机；如前面正在运行进程由于I/O申请自愿中断而进入阻塞状态时，系统就需要从就绪队列中选择一个就绪态进程投入运行而转换成运行态。产生调度的因素有很多，但基本都与中断有关。

进程状态变迁是由于中断，但中断不一定产生进程切换！

进程调度方式

调度方式

非抢占方式

进程被选中就一直运行下去（不会因为时钟中断而被迫让出CPU），直至完成工作、自愿放弃CPU、或因某事件而被阻塞才把CPU让出给其它进程。

抢占方式

抢占方式发生的情况可为：

新进程到达、出现中断且将阻塞进程转变为就绪进程、以及用完规定的时间片等。

调度算法

►系统中处于可运行状态进程的个数通常比处理机的个数要多，特别是在单处理机系统中尤为如此。这样就存在从就绪队列中选择哪一个进程，这就是调度算法问题。

衡量指标

► 调度算法要考虑到公平性和用户的满意程度，即考虑面向系统和面向用户的两个准则。

具体考虑有如下5个指标：

CPU利用率

CPU利用率就是使CPU尽量处于忙状态，是系统的一个很重要的目标。通常，在一定的I/O等待时间的百分比之下，运行程序的道数越多，CPU空闲时间的百分比越低。

吞吐率

吞吐率就是单位时间内所处理的计算任务的数目，也是面向系统的一个重要指标。

周转时间

考虑到作业调度，则为作业等待进入内存、进程在就绪队列中等待、进程在CPU上执行和完成有关I/O操作所花费的时间总和。对于个作业 $i$，其周转时间为：

$T_i=t_{ci}-t_{si}\\ t_{ci}为完成时间\\ t_{si}为到达系统的时间$

系统中 $n$ 个作业平均周转时间为:

$\bar{T}=\frac{1}{n}\sum_{i=1}^nT_i$

带权周转时间为:

$W=\frac{T}{R}\\ 其中 \quad R=\frac{实际服务时间}{运行时间}$

（带权周转时间衡量长短任务的差别），由此可以得到平均带权周转时间为:

$\bar{R}&=\frac{1}{n}\sum_{i=1}^n W_i\\ &=\frac{1}{n}\sum_{i=1}^n \frac{T_i}{R_i}$

响应时间

n响应时间就是从任务就绪到处理开始（也有的称为等待时间）。

► 在交互式系统中，周转时间不可能是最好的评价准则。因为不断请求与不断输出在同时发生。

► 通常，响应时间一般用于分时系统性能评价，指用户通过键盘或终端提出一个请求开始到系统给出相应的响应结果的时间（与上面有所不同）。

系统开销

系统开销就是系统调度任务的过程中所付出的时/空代价。

几种调度算法

先来先服务(FCFS, First come first served)

也称为先进先出（FIFO），或严格排队方式。

对于作业调度，该算法就是从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列。
对于进程调度，该算法就是从就绪队列中选择一个最先进入队列的进程，将CPU分配于它。

优缺点:

有利于长作业（进程）而不利于短作业（进程）
有利于CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进程）

短作业优先(SJF Shortest job first )

该算法从就绪队列中选出下一个“CPU执行期最短”的进程，将CPU分配于它。

优缺点:

对短作业有利，明显的作业E提前接受了服务，并且整体性能也得到了提高；
需要事先知道或至少需要估计每个作业所需的处理机时间。
只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。
SJF 偏向短作业，不利于分时系统（由于不可抢占性）。

最高响应比（HRP）

考虑响应比

$R=\frac{响应时间+运行时间}{运行时间}$

既考虑了在系统的等待时间，又考虑了作业自身所需的运行时间，综合了FCFS与SJP各自特点。在进行进程调度时，从中选择响应比高者的进程投入运行。

从平均周转时间及其平均带权周转时间来看，HRP 刚好介于FCFS与SJP之间，即好于FCFS，次于SJP。

最短剩余时（SRT ，Shortest remaining time）

►SRT是针对 SJF 增加了强占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。

► SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销。

► 必须记录过去的服务时间，从而增加了开销。

► 从周转时间来看，SRT 比SJF 有更好的性能。

平均周转时间和带权平均周转时间说明了SRT好于前面的任何一个算法（因为它具有抢占的特点）。其过程的另一种简单描述：

轮转（RR Round Robin）

$T=q\times n$

参数说明:

系统响应时间 $T$:在进程数目一定时，时间片的长短直接正比于系统响应时间。
就绪队列进程数目 $n$ :当系统要求的响应时间一定时，时间片反比于就绪队列中进程的数目。
时间片$q$ :时间片的长短，CPU运行指令的速度；CPU速度快，q可以小一些，反之亦然。

轮转法设计的问题是时间片的长度：

时间片设得太短会导致过多的进程切换，降低了 CPU效率
而得太长又可能引起对短的交互请求的响应时间变长
将设时间片设为 20ms~50ms 通常是一个比较合理的折中

优先级法(HPF)

轮转调度做了一个隐含的假设，即所有的进程同等重要，而拥有和操作多用户计算机系统的人对此常有不同的看法。

例如，在安卓操作系统里，等级顺序由高到低依次为前台进程，可视进程，服务进程，后台进程和空进程。

这就导致了优先级调度。其基本思想很清楚：每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。

如何确定进程优先级。有两种确定的方法：

静态优先级：进入系统时赋予一个优先级，在整个生命周期中一直固定不变（可能不公平）。
动态优先级：创建时赋予一个优先级，可以动态改变。如处于就绪状态时，进程的优先级应随着等待时间的增长而增高。
- 优点可使资源利用率得以提高，公平性比较好。
- 缺点是系统开销大，实现比较复杂。

可以很方便地将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用轮转调度。

下图给出了一个有4类优先级的系统，其调度算法如下：

只要存在优先级为第4类的可运行进程，就按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第4类进程为空，则按照轮转法运行第3类进程。若第4类和第3类均为空，则按轮转法运行第2类进程。

如果不偶尔对优先级进行调整，则低优先级进程很可能会产生饥饿现象。

多级队列(MQ——Multilevel Queue)

可根据进程某些特性，如优先级，类型等分成几个单独队列；每个队列可有各自调度算法。例如，前台利用 RR ，后台利用 FCFS 等。

►何时有可能调用到处理机调度程序呢？前提条件是必须进入操作系统，即处于系统态。

► 处于用户态运行的用户程序不可能直接调用操作系统中的任何模块（系统调用的例行服务程序除外）。

一般在以下事件发生后要执行进程调度：

创建进程；创建进程时。
进程终止；一个进程终止时必须进行调度。如果没有就绪进程，系统通常会启动一个空转进程(休闲进程)等待(硬/软)中断的发生。
等待事件；进程由于等待I/O、信号量或其它原因而放弃CPU，这样就必须选择另外一个进程。
中断发生；当发生I/O中断，原先等待I/O的进程就从阻塞态转变成就绪态，是否可强占。
运行到时；在分时系统中，当前进程用完给定的时间片，时钟中断使该进程让出CPU进入调度。

实时调度

实时系统是一种时间起着主导作用的系统。

实时系统通常可以分为硬实时和软实时，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。
在这两种情形中，实时性能都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前掌握的。这些进程一般寿命较短，并且极快地就运行完成。
在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。

实时系统的调度算法可以是静态或动态的，前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策

只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作。而动态调度算法不需要这些限制。