操作系统之历程的调度与死锁

一. 操作系统引论

操作系统是一组能有效阻止和管理计算机硬件和软件资源，合理地把对各类作用进行调度，以及方便用户使用的程序的集合。

1. 操作系统的目标与作用

• 在计算机系统上配置操作系统，其主要目标就是：方便性、有效性、可扩充性和开放性。
  
  • 方便性：一个未配置的计算机系统是极难使用的。配置了操作系统之后，系统便可使用编译命令将用户采用高级语言编写的程序翻译成机器代码，或直接通过OS所提供的各种命令操纵计算机，极大地方便了用户。
  • 有效性：提高系统资源利用率以及洗脱嫩肉吞吐量。
  • 可扩充性：能方便的添加新的功能和模块，以及对原有的功能进行添加和修改。
  • 开放性：指系统能遵循世界标准规范。
• 操作系统的作用
  
  • 作为用户与计算机硬件操作系统之间的接口。用户可以通过OS来使用计算机硬件。
  • 作为计算机系统资源的管理者。这些资源主要分为：处理机、存储器、I/O设备以及文件（数据和程序）。
  • 实现了对计算机资源的抽象。

2. 操作系统的发展过程

• 人工操作方式：人工的输入输出，用户独占全机。
• 脱机输入/输出方式：引入了高速的磁带。减少了CPU的空闲时间，提高了I/O速度。
• 单道批处理系统：实现对作业的连续处理，系统中的资源得不到充分利用。
• 多道批处理系统：多道作业存放于外存的后备队列，有作业调度选择若干个作业调入内存，资源利用率高，系统吞吐量大，但是平均周转时间长，无交互能力。
• 分时系统：满足用户对人-机交互的需求。是指在一台主机连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互的方式使用计算机，共享主机中的资源。
• 实时系统：是指系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

3. 操作系统的基本特性

上面介绍的多道批处理系统、分时系统和实时系统各自有各自的特点，但同时，他们还共同具有并发、共享、虚拟和异步四个基本特征。

• 并发：系统中的程序能够并发的执行，使得OS能有效地提高系统的资源利用率，增加系统的吞吐量。
  
  • 并发性：是指两个或多个事件在同一时间间隔内发生。
  • 并行性：指两个或多个事件在同一时刻发生。倘若在计算系统中有多个处理机，这些可以并发执行的程序便可分配到多个处理机上实现并行执行。
  • 在未引入进程时，对于同属于一个应用程序中的两个程序只能顺序执行。引入进程，对内存中的多个程序分别建立一个进程，他们就可以并发的执行，极大地提高了系统资源利用率和系统吞吐量。
• 共享性：是指系统中的资源可供内存中 多个并发执行的进程共同使用。主要实现方式：
  
  • 互斥共享：在一段时间内，只允许一个进程访问该资源，我们成该种资源为临界资源。
  • 同时访问
  • 并发和共享是多用户OS的两个最基本的特征。
• 虚拟性：采用时分复用技术和空分复用技术实现。
  
  • 时分复用技术是通过利用处理机的空闲时间运行其他程序，提高了处理机的利用率。
  • 空分复用技术则是利用存储器的空闲时间分区域存放和运行其他的多道程序，以此来提高内存的利用率。
• 异步性：进程以人们不可预知的速度向前推进，也就是用户不知道进程在何时获得CPU。

4. 操作系统的主要功能

引入OS的目的是为多道程序的运行提供良好的运行环境，以保证多道程序能有条不紊的运行，并能最大程度的提高系统中各种资源的利用率，方便用户的使用。OS具有处理机管理、存储器管理、设备管理、文件管理以及用户接口五大功能。

• 处理机管理的主要功能：进程控制，进程同步，进程通信以及进程调度。
• 存储器管理的主要功能：内存分配，内存保护，地址映射，内存扩充。
• 设备管理的主要功能：缓冲管理，设备分配，设备处理。
• 文件管理的主要功能：文件存储空间的管理，目录管理，文件的读写管理和保护。
• 接口的主要功能：提供用户接口和程序接口。

二. 进程的描述与控制

1. 进程与线程

为了能使程序并发的执行，并且可以对并发执行的程序加以控制，引入进程。为了使参与并发执行的每个程序都能独立运行，为每个进程配置一个进程控制块PCB，用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。这样由程序段、相关的数据段和PCB三部分构成了进程实体。

• 进程的定义
  
  • 进程是程序的一次执行。
  • 进程是一个程序及其数据在处理上顺序执行时所发生的的活动。
  • 进程是具有独立功能的程序在一个数据集合上运行的过程它是系统进行资源分配的独立单位。

引入线程的目的是减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

• 进程创建，系统为它分配其所必需的、除处理机以外的所有资源，以及创建相应的PCB。
• 进程撤销，必须对其所占有的资源执行回收操作，然后撤销PCB。
• 进程切换，对进城进行上文切换时，需要保留当前进程的CPU，设置新选进程的CPU环境，因此需要花费不少的处理机时间。

进程是一个资源的拥有者，如果频繁的进行创建撤销切换会造成很大的时空开销。所以，引入线程，将线程作为调度和分派的基本单位，进程作为资源分配的独立单位。

2. 程序、进程、线程的比较

首先程序与进程的区别：

• 进程具有程序所没有的PCB，进程是程序的一次执行。
• 动态性：
  
  • 进程的实质是进程实体的执行过程，动态性表现在：进程由创建而产生，由调度而执行，由撤销而消亡。可见进程具有一定的生命周期。
  • 程序是一组有序指令的集合，并存放于某种介质智商，其本身并不具有活动的意义，是静态的。
• 并发性：
  
  • 多个进程同存在于内存中，且能在一段时间内同时运行。
  • 程序没有建立PCB不能参与并发执行。
• 独立性：
  
  • 进程实体是一个能独立运行、独立获得资源的基本单位。
  • 凡未建立PCB的程序都不能作为一个独立运行的单位参与运行。
• 异步性：
  
  • 进程是按异步的方式运行的，即按各自独立的、不可预知的速度向前推进。
  • 程序若参与并发执行，会产生其结果的不可再现性。

其次是进程与线程的区别：

• 调度的基本单位：
  
  • 进程是资源分配的基本单位。
  • 线程是调度和分派的基本单位。线程切换仅需要保存和设置少量的寄存器。在同一进程中线程的切换不会引起进程的切换，不同进程中线程的切换则会引起进程的切换。
• 并发性：
  
  • 不仅进程与进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行。
• 拥有资源：
  
  • 进程是系统中拥有资源的基本单位。
  • 线程并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源，比如TCB、用于PC、保留局部变量、少数状态参数和返回地址等的一组寄存器和栈。
• 独立性：
  
  • 每个进程都拥有独立的地址空间和其他资源。除了共享全局变量以外，不允许其他进程访问。
  • 线程除了拥有少量资源外，还可以属于同一个进程的所有线程都具有相同的地址空间。并且可以访问所属进程的所有资源。
• 系统开销：
  
  • 进程的创建、撤销所付出的开销远比线程大。
  • 同一进程里的线程具有相同的地址空间，线程的切换比进程的切换代价小。
• 支持多处理机系统：
  
  • 在多处理机系统上，对于传统的进程，不管有多少处理机，该进程只能运行在一个处理机上。
  • 但对于多线程进程，就可以将一个进程中的线程分配到多个处理机上，使他们并行执行，可以加速进程的完成。

3. 进程的状态

1) 进程的三种基本状态：

• 就绪状态：进程已经分到除CPU以外的所有必要的资源，只要在获得CPU，便可立即执行。
• 执行状态：指进程已经获得CPU，其程序正在执行。
• 阻塞状态：指正在执行的进程由于发生某件事（如I/O请求、申请缓冲区失败等）暂时无法继续执行时的状态。

进程的三种基本状态及其转换如下图：

2) 为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性，引入了创建状态和终止状态。

• 创建状态：保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。获得所需要的资源以及对PCB的初始化工作完成之后，便可由创建状态进入就绪状态。
• 终止状态：等待操作系统进行善后处理，最后将PCB清零，并将PCB空间返还系统。

进程的五种基本状态以及转换如下图：

3) 挂起状态的引入：增加内存容量，实现虚拟内存。挂起是将进程调至内存外，从而保证内存充足。

引入挂起状态之后的状态装换图如下：

4. 进程同步

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则共享系统资源，并能很好地相互合作，从而是程序的执行具有可再现性。

1) 两种形式的制约关系

• 间接相互制约关系：多个程序在并发执行时，由于共享系统资源，只是这些并发执行的程序之间形成相互制约的关系，多个进程互斥的访问这些资源。
• 直接相互制约关系：多个进程一同合作为了完成某个任务，这些进程在完成任务上有一定的时间顺序。有些进程要在其他进程的后才能开始。

2）同步机制应遵循的规则：

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

3) 硬件同步机制

• 关中断
• 利用Test-and-Set指令实现互斥
• 利用Swap指令实现进程互斥

4) 信号量机制

• 整型信号量：执行时不可中断。描述如下：

wait(S){
    while(S<=0);
    S--;
}
signal(S){
    S++;
}

wait(S)和signal(S)是两个原子操作，不符合“让权等待”原则。

• 记录型信号量：采用记录型数据结构。描述如下：

typedef struct{
    int value;
    struct process_control_block *list;
}semaphore;

wait(semaphore * S){
    S->value --;
    if(S-value < 0) block(S->list);
}
signal(semaphore * S){
    S->value ++;
    if(S->value <= 0) wakeup(S->list);
}

• AND型信号量：江金城在整个运行过程中所需要的所有资源，一次性全部地分给进程，带进程使用完后在一起释放。
• 信号量集

5) 信号量的应用

• 利用信号量实现进程互斥，使多个进程能互斥的访问某临界资源。
• 利用信号量实现前驱关系。

5. 进程经典同步问题

• 生产者-消费者问题
• 哲学家进餐问题
• 读者-写者问题

6. 进程通信

进程通信类型：

• 共享存储器系统
• 管道通信系统
• 消息传递系统
• 客户机-服务器系统

三. 处理机调度与死锁

1.处理机调度的层次与调度算法的目标

1) 处理机调度的层次

• 高级调度：又称长调度或作业调度，对象时作业，从后备队列中选择几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪列表。主要用于多道批处理系统中，分时和实时系统中并不设置高级调度。
• 低级调度：又称为进程调度或短程调度，对象是进程或线程，从就绪队列中选择一个进程获得处理机。在多道批处理、分时、实时系统中，都必须配置这级调度。
• 中级调度：又称内存调度，把那些暂时不能运行的程序调至外存等待。此时进程的状态称为挂起状态，当他们具备运行条件且内存有稍有空闲时，由中级调度来决定把外村上的那些具备运行条件的就绪进程重新调入内存，置为就绪状态。目的是：提高内存利用率和系统吞吐量。

2) 处理机调度算法的目标

• CPU利用率：
  

  $$CPU的利用率 = \dfrac{CPU有效工作时间}{CPU有效工作时间 + CPU空闲等待时间}$$

• 周转时间：是指作业被提交给系统开始，到作业完成为止的这段时间。

• 平均周转时间： $$T = \dfrac{各个作业的周转时间和}{作业的个数}$$
• 带权周转时间：作业的周转时间T与系统为它提供服务的时间Ts之比。
• 平均带权周转时间为：各个带权周转时间的和/作业个数。

2. 作业调度

1) 作业运行的三个阶段为收容、运行、完成。作业的三种状态对应为后备状态、运行状态、完成状态。

2) 作业调度的主要任务是决定接纳多少个作业以及接纳哪些作业这两个问题。

3) 作业调度的算法如下：

• 先来先服务（FCFS）
• 短作业优先（SJF）
• 优先级调度算法（PSA）：系统从后备队列中选择若干个优先级较高的装入内存。
• 高响应比优先调度算法（HRRN）：既考虑了作业的等待时间有考虑了作业的运行时间，引入一个动态优先级：
  $$优先权 = \dfrac{等待时间 + 要求服务时间}{要求服务时间}$$

由于等待时间与服务时间之和就是系统对该作业的响应时间，故优先级又相当于响应比Rp，Rp又可以如下表示：

$$Rp = 优先权 = \dfrac{响应时间}{要求服务时间}$$

3. 进程调度

1) 进程调度的任务有三如下：

• 保存处理机的现场信息。
• 按某种算法选取进程。
• 把处理器分配给进程。

2) 进程调度方式

• 非抢占方式：一旦把处理机分给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成，或者发生某件事而被阻塞时，才把处理机分配给其它进程。
• 抢占方式：允许调度进程根据某种原则去暂停正在执行的进程，将分配给该进程的处理及重新分配给另一进程。然而抢占要遵循的原则：
  
  • 优先权原则。
  • 短作业优先原则。
  • 时间片原则。

3) 调度算法

• 轮转调度算法：分时系统中较常用的调度方法，很公平，让就绪队列上的每一个进程每次仅运行一个时间片。
  
  • 系统将所有的就绪进程按FCFS策略排成一个就绪队列，系统设置每隔一定时间 便产生一次中断，去激活进程调度程序进行调度，把CPU分给队首进程，让他执行一个时间片。
  • 若时间片还没用完，进程便已经完成，则立即调度下一下进程。
  • 若时间片已经用完，而进程还没有完成，则把该进程送往就绪队列的队尾。
• 优先级调度算法：静态优先级和动态优先级。
• 多队列调度算法：设置多个就绪队列，对每个就绪队列实施不同的调度算法。
• 多级反馈队列：设置多个就绪队列，每个队列的优先级不一样，优先级越高的队列中其时间片就越小，每个队列采用FCFS算法。

4. 实时调度

1) 实时调度算法的分类

• 非抢占式调度算法：
  
  • 非抢占式轮转式调度算法。
  • 非抢占式优先调度算法。
• 抢占式调度算法：
  
  • 基于时钟终端的抢占式优先级调度算法。
  • 立即抢占的优先级调度算法。

2) 实时调度算法

• 最早截止时间优先EDF算法：
  
  • 根据任务的截止时间确定任务的优先级。任务的截止时间最早其优先级越高。
  • 分非抢占式和抢占式
• 最低松弛度优先LLF算法：
  
  • 根据任务的紧急程度，任务紧急程度越高，赋予该任务的优先级就越高。
  • 该算法主要用于可抢占式调度方式中。
  • 松弛度= 必须完成时间 - 其本身的运行时间 - 当前时间

5. 死锁概述

• 死锁的定义：
  
  • 如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。
• 产生死锁的原因：
  
  • 资源竞争。
  • 进程推进顺序不当。
• 产生死锁的必要条件：
  
  • 互斥条件。
  • 请求和保持。
  • 不可抢占。
  • 循环等待条件。
• 处理死锁的方法：
  
  • 预防死锁：设置某些限制条件去破坏产生死锁的四个必要条件中的一个或几个来预防产生死锁。
  • 避免死锁：同样是事先预防策略，在资源动态分配的过程中，用某种方法防止系统进入不安全状态。从而避免死锁。
  • 检测死锁：允许进程在运行过程中发生死锁，然后检测死锁。
  • 解除死锁：当检测到死锁的时候，采取相应措施，将进程从死锁状态中解脱出来。

6. 预防死锁

由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证。因此主要是破坏其他三个条件。

• 破坏请求和保持条件：比较现实
• 破坏不可抢占条件：会延长进程的周转时间，增加了系统开销，降低了系统吞吐量。
• 破坏循环等待条件：对所有资源类型进行线性排序。

7. 避免死锁

• 安全状态一定不会有死锁发生。
• 不安全状态不一定有死锁发生。
• 银行家算法

8. 死锁的检测与解除

• 死锁的检测
  
  • 资源分配图
  • 死锁定理：在资源分布图中，找出一个既不阻塞由非独立的进程节点让其运行。最终S为死锁的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。
• 死锁解除
  
  • 抢占资源。
  • 终止进程。