作业管理

• 一. 进程调度
• • １.1 进程调度概述
  • • １.１.１ 进程调度遵循的机制
  • 1.1.2 两大类调度
  • 1.2 进程调度算法
• 二.死锁
• • 2.1 死锁的产生
  • • 2.1.1 产生原因
    • 2.1.2 死锁的四个必要条件
  • 2.2 死锁的处理
  • • 2.2.1 预防死锁的方法
    • 2.2.2 银行家算法

一. 进程调度

１.1 进程调度概述

进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权，前提是多道程序设计。
进程调度有两个步骤：1.保留旧进程的运行信息,请出旧进程(收拾包袱)；2.选择新进程，准备运行环境并分配CPU(新进驻)
为理解上述两个步骤，我们要先知道三个机制。

１.１.１ 进程调度遵循的机制

• 就绪队列的排队机制
  将就绪进程按照一-定的方式排成队列，以便调度程序可以最快找到就绪进程。
• 选择运行进程的委派机制
  调度程序以一定的策略选择就绪进程，将CPU资源分配给它。
• 新老进程的上下文切换机制
  当需要把新的进程调度到CPU时，需要先把老进程的CPU环境备份出来，再把新进程的环境切换到CPU中。保存当前进程的上下文信息，装入被委派执行进程的运行上下文。

1.1.2 两大类调度

如果在进程调度时，老进程还没执行完，应该怎么办？

• 非抢占式调度
  处理器一旦分配给某个进程，就让该进程一-直使用下去，调度程序不以任何原因抢占正在被使用的处理器，直到进程完成工作或因为IO阻塞才会让出处理器。
• 抢占式调度
  允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。

1.2 进程调度算法

• 先来先服务调度算法
• 短进程优先调度算法
  调度程序优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程的执行。
• 高优先权优先调度算法
  进程附带优先权，调度程序优先选择权重高的进程，高优先权优先调度算法使得紧迫的任务可以优先处理
• 时间片轮转调度算法
  按先来先服务的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，时间片结束后，无论该进程是否执行完都会把该进程移到队列尾部并执行下一个进程，循环往复。是相对公平的调度算法，但不能保证及时响应用户。

二.死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

比如哲学家进餐问题。

2.1 死锁的产生

2.1.1 产生原因

死锁的产生有两种原因：

• 竞争资源
  主要是因为共享资源数量不满足各个进程需求，所以各个进程之间发生资源进程导致死锁。
  想象一下这种场景：传真机和打印机各有一台。进程一占用传真机，进程二占用打印机。进程一申请使用打印机但不释放传真机，进程二申请使用传真机但不释放打印机，等待请求的资源被释放，自身占用资源不释放，这种情况就会出现死锁。如果多一个传真机或多一个打印机，就不会出现因为竞争资源而导致的死锁了。
• 进程调度顺序不当
  还是上述的场景，如果将调度顺序改变一下就不会出现死锁，进程一先占用传真机和打印机，进程一结束后，进程二在占用。

2.1.2 死锁的四个必要条件

出现死锁就会出现下面四个情况：

• 互斥条件
  进程对资源的使用是排他性的使用，也就是说某资源只能由一个进程使用，其他进程需要使用只能等待。
• 请求保持条件
  进程至少保持一个资源， 又提出新的资源请求，新请求的资源被占用，请求被阻塞，而且被阻塞的进程不释放自己保持的资源。
• 不可剥夺条件
  进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
• 环路等待条件
  发生死锁时，必然存在进程资源环形链

2.2 死锁的处理

2.2.1 预防死锁的方法

• 破坏请求保持条件
  系统规定进程运行之前，-次性申请所有需要的资源，进程在运行期间不会提出资源请求，从而破坏请求保持条件。
• 破坏不可剥夺条件
  当一个进程请求新的资源得不到满足时，必须释放占有的资源。进程运行时占有的资源可以被释放,意味着可以被剥夺。
• 破坏环路等待条件
  可用资源线性排序，申请必须按照需要递增申请，线性申请不再形成环路,从而摒弃了环路等待条件。

2.2.2 银行家算法

银行家算法是可操作的著名的避免死锁的算法，以银行借贷系统分配策略为基础的算法。
先看一下银行借贷系统：客户申请的贷款是有限的，每次申请需声明最大资金量，银行家在能够满足贷款时，都应该给用户贷款，客户在使用贷款后，能够及时归还贷款。
类比如下：
进程申请的资源是有限的，每次申请需声明最大资源数量，系统在能够满足资源时，都应该给进程分配资源，进程在使用完资源后，能够及时归还资源。

作业管理

• 一. 进程调度
• • １.1 进程调度概述
  • • １.１.１ 进程调度遵循的机制
  • 1.1.2 两大类调度
  • 1.2 进程调度算法
• 二.死锁
• • 2.1 死锁的产生
  • • 2.1.1 产生原因
    • 2.1.2 死锁的四个必要条件
  • 2.2 死锁的处理
  • • 2.2.1 预防死锁的方法
    • 2.2.2 银行家算法

一. 进程调度

１.1 进程调度概述

进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权，前提是多道程序设计。
进程调度有两个步骤：1.保留旧进程的运行信息,请出旧进程(收拾包袱)；2.选择新进程，准备运行环境并分配CPU(新进驻)
为理解上述两个步骤，我们要先知道三个机制。

１.１.１ 进程调度遵循的机制

• 就绪队列的排队机制
  将就绪进程按照一-定的方式排成队列，以便调度程序可以最快找到就绪进程。
• 选择运行进程的委派机制
  调度程序以一定的策略选择就绪进程，将CPU资源分配给它。
• 新老进程的上下文切换机制
  当需要把新的进程调度到CPU时，需要先把老进程的CPU环境备份出来，再把新进程的环境切换到CPU中。保存当前进程的上下文信息，装入被委派执行进程的运行上下文。

1.1.2 两大类调度

如果在进程调度时，老进程还没执行完，应该怎么办？

• 非抢占式调度
  处理器一旦分配给某个进程，就让该进程一-直使用下去，调度程序不以任何原因抢占正在被使用的处理器，直到进程完成工作或因为IO阻塞才会让出处理器。
• 抢占式调度
  允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。

1.2 进程调度算法

• 先来先服务调度算法
• 短进程优先调度算法
  调度程序优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程的执行。
• 高优先权优先调度算法
  进程附带优先权，调度程序优先选择权重高的进程，高优先权优先调度算法使得紧迫的任务可以优先处理
• 时间片轮转调度算法
  按先来先服务的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，时间片结束后，无论该进程是否执行完都会把该进程移到队列尾部并执行下一个进程，循环往复。是相对公平的调度算法，但不能保证及时响应用户。

二.死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

比如哲学家进餐问题。

2.1 死锁的产生

2.1.1 产生原因

死锁的产生有两种原因：

• 竞争资源
  主要是因为共享资源数量不满足各个进程需求，所以各个进程之间发生资源进程导致死锁。
  想象一下这种场景：传真机和打印机各有一台。进程一占用传真机，进程二占用打印机。进程一申请使用打印机但不释放传真机，进程二申请使用传真机但不释放打印机，等待请求的资源被释放，自身占用资源不释放，这种情况就会出现死锁。如果多一个传真机或多一个打印机，就不会出现因为竞争资源而导致的死锁了。
• 进程调度顺序不当
  还是上述的场景，如果将调度顺序改变一下就不会出现死锁，进程一先占用传真机和打印机，进程一结束后，进程二在占用。

2.1.2 死锁的四个必要条件

出现死锁就会出现下面四个情况：

• 互斥条件
  进程对资源的使用是排他性的使用，也就是说某资源只能由一个进程使用，其他进程需要使用只能等待。
• 请求保持条件
  进程至少保持一个资源， 又提出新的资源请求，新请求的资源被占用，请求被阻塞，而且被阻塞的进程不释放自己保持的资源。
• 不可剥夺条件
  进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
• 环路等待条件
  发生死锁时，必然存在进程资源环形链

2.2 死锁的处理

2.2.1 预防死锁的方法

• 破坏请求保持条件
  系统规定进程运行之前，-次性申请所有需要的资源，进程在运行期间不会提出资源请求，从而破坏请求保持条件。
• 破坏不可剥夺条件
  当一个进程请求新的资源得不到满足时，必须释放占有的资源。进程运行时占有的资源可以被释放,意味着可以被剥夺。
• 破坏环路等待条件
  可用资源线性排序，申请必须按照需要递增申请，线性申请不再形成环路,从而摒弃了环路等待条件。

2.2.2 银行家算法

银行家算法是可操作的著名的避免死锁的算法，以银行借贷系统分配策略为基础的算法。
先看一下银行借贷系统：客户申请的贷款是有限的，每次申请需声明最大资金量，银行家在能够满足贷款时，都应该给用户贷款，客户在使用贷款后，能够及时归还贷款。
类比如下：
进程申请的资源是有限的，每次申请需声明最大资源数量，系统在能够满足资源时，都应该给进程分配资源，进程在使用完资源后，能够及时归还资源。