操作系统

考研以左侧这本为主

1.1基本概念

这一小节的知识点有 2 个。
一是从资源管理的角度来说操作系统的几个主要功能，这部分其实就是我们这本书后面将要学习的各个章节，处理器管理、存储管理、设备管理等；
二是操作系统的四大基本特征：并发、共享、虚拟、异步。

这一小节基本理论部分教学慕课已经讲解的很清晰了，我们就挑两个比较重要的概念给大家进一步解析一下：**并发性**和**异步性**

并发性

1、并发和并行的区别：
并行是指两个或多个事件在同一时刻发生，
并发是指两个或多个事件在同一时间段内发生。

但在计算机组成原理课程中主要是从宏观的角度来看的，并发性在用户看来也是并行的，故并行性包含了并发性的。主要是看问题的角度和层面不同的。

这里大家不需要死抠概念，理解两者区别就可以了

2、并发里涉及到操作系统一个很重要的概念就是：进程

我们后面也会频繁接触到进程这个概念

先来了解一下为什么引入进程，多道程序系统中，我们熟悉的是程序这个实体，程序具有：并行、制约以及动态的特征。但程序概念难以便是和反映系统中的情况：
（1）程序是一个静态的概念
程序是完成某个功能的指令集和。系统实际上是出于不断变化的状态中，程序不能反映这种动态性。
（2）程序概念不能反映系统中的并行特性
例如：两个C语言源程序由一个编译程序完成编译，若用程序概念理解，内存中只有一个编译程序运行（两个源程序看作编译程序的输入数据），但是这样无法说明白内存中运行着两个任务。程序的概念不能表示这种并行情况，反映不了他们活动的规律和状态变化。就像不能用菜谱（程序）代替炒菜（程序执行的过程）一样

所以为了可以正确的描述并发，引入了进程这个概念

通过对慕课的学习我们知道，
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度运行的基本单位。

所以后面章节里系统中运行的实体均为进程而不是程序，具体关于进程的更详细介绍我们会在第三章中具体进行深入学习。

异步性

第二个我们要重点理解的概念是异步性

在多道程序环境下,允许多个进程并发执行，进程在使用资源时可能需要等待或放弃，进程的执行并不是一气成的,而是以走走停停的形式推进。如下举例：

![)N(0%KF3W]U9XN79OMXFDL.jpg

大家可以看到三个进程由于对资源的竞争造成的间断执行过程
进程以不可预知的速度向前推进。何时执行、何时暂停、何时完成都是未知的，这就是系统的异步性。
再比如如下实例
![W6JNM~A$BJ~21SD%X({19A.jpg

四道作业从投入系统到运行结束，大家只注意时间节点就好
显然也不是顺序不间断，而是走走停停无序的
这也是异步性的体现

1.2 操作系统的形成与发展

1.2这一小节主要了解各时期出现各种操作系统，我们重点提一下分时系统

分时系统简单解释就是使一台计算机同时为几个、几十个甚至几百个用户服务的一种操作系统。把计算机与许多终端用户连接起来，分时操作系统将系统处理机时间与内存空间按一定的时间间隔，轮流地切换给各终端用户的程序使用。由于时间间隔很短，每个用户的感觉就像他独占计算机一样。分时操作系统的特点是可有效增加资源的使用率。例如UNIX系统就采用剥夺式动态优先的CPU调度，有力地支持分时操作。

因为后面我们在调度算法里会介绍分时系统特有的算法，所以这里需要了解它的概念基本工作原理

发展过程中产生分时系统是为了满足用户需求所形成的一种新型 OS 。它与多道批处理系统之间，有着截然不同的性能差别，用户的需求具体表现在以下几个方面: 人—机交互、共享主机、便于用户上机 。

要了解分时系统的调度算法，首先要了解时间片的概念

时间片就是把计算机的系统资源（尤其是 CPU时间）进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流 使用时间片。

分时系统的工作原理或调度算法可以用以下简单流程图来说明

1.3 操作系统的结构设计

1.操作系统是什么？
是配置在计算机硬件的第一层软件，是对硬件系统的首次扩充；

2.操作系统的作用与功能？
作用：控制管理计算机的全部硬件资源，合理组织内部各部件协调工作，为用户提供和操作编写界面的集合；
功能：处理机管理、存储器管理、设备管理和文件管理；

首要明确os是一种系统软件

3.操作系统的发展：
1）人工操作方式
用户独占全机，CPU等待人工操作；人工操作严重降低了计算机资源的利用率，所谓人机矛盾。
2）脱机输入/输出（I/O）方式
引入磁带，将数据程序输入待磁带上，需要程序和数据时，再从磁带上高速调入内存。
输入输出方式：联机输入/输出方式，
优点：减少CPU的空闲时间；提高I/O速度。

3）单道批处理系统
流水线式的工作， 串行；
单道批处理系统是解决人机矛盾和CPU与I/O设备速度不匹配矛盾的过程中形成的；
批处理系统旨在提高系统资源的利用率和系统吞吐量。
缺点：系统资源不能够充分利用，造成内存的浪费。

4）多道批处理系统
设计概念：提高资源利用率和系统吞吐量，例如A、B、C程序执行，都有I/O操作而使CPU暂时停止行，A在I/O操作时，B执行，B在I/O操作时，C执行。使多道程序交替地运行。
优缺点：资源利用率高；系统吞吐量大。平均周转时间长；无交互能力。

![8B0NEYWEUOAKW)YZ7E97UG.jpg
比如图中三个进程I，C，P，分别为输入、计算、打印进程，三者在一个多道批处理系统里并发执行的情况
需要注意的是系统需要处理的是n批数据，不是只有一批数据，大家一会做题目时候可以继续分析多道环境下的并发执行的特点

5）分时系统
分时系统是指，在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机的资源。
特征：多路性、独立性、及时性、交互性。
分时系统的主要目标：对用户响应的及时性，即不至于用户等待每一个命令的处理时间过长。
多用户分时系统是当今计算机操作系统中最普遍使用的一类操作系统。

6）实时系统
系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时任务的协调一致运行。
特征：多路性（周期性信息采集，多个对象或执行机构进行控制）、独立性、及时性、交互性、可靠性（多级容错措施）。

4.并发
在单位时间内可以处理事情的能力，例如 8个窗口，30秒打饭，并发能力是每分钟16
5.并行
同一时刻，可以处理事情的能力，例如8个窗口，8个人打饭，并行能力是8

8.进程与程序
进程：是系统进行资源分配和调度的一个独立单位。其是动态的（产生->执行->消亡），可单独一个进程运行，也可以多个进程并发运行（参考百米赛跑，每个人就是一个进程），且运行方式是异步的。
程序：程序是一组有序指令的集合。是静态的，存放在某种介质上，不具有活动的含义

程序和进程主要区别：
程序是要执行的一组明确的有序操作。另一方面，正在执行的程序的实例是一个进程。
程序的本质是被动的，因为它在执行之前什么也不做，而进程本质上是动态的或活动的，因为它是执行程序和执行特定操作的实例。
程序具有更长的使用寿命，因为它存储在磁盘中，直到它不会被手动删除，而进程的生命周期较短且有限，因为它在进程完成后终止。
在进程中，资源需求要高得多; 它可能需要处理，内存，I / O资源才能成功执行。相反，程序只需要磁盘来存储

9、操作系统的基本共性：并发、共享、虚拟和异步；
1）并发
引入进程；引入线程；时间片轮转程度调用算法；
2）共享：操作系统中共享的两种方式：
互斥共享方式：在一段时间内只允许一个进程访问的资源成为临界资源或独占资源。
同时访问方式：允许一段时间内有多个进程同时对它们进行访问。
3）虚拟
时分复用技术：利用处理机的空闲时间运行其他程序，提高处理机的利用率。
空分复用技术：利用储存器的空闲时间存放其他程序，提高内存的利用率。
4）异步
进程已不可预知的速度向前推进。

2.1&22 进程及其实现、进程控制

先来了解一下进程引入的原因
我们最熟悉的概念是程序，那么在多道系统中程序能否并发执行呢 ？先来看一个例子

自行在纸上按不同的速度使ab两进程并发执行，写出并考察程序的结果和变量的值

写完可能已经发现了不同速度向前推进，最后程序和变量的结果值可能不同，这意味着程序的结果出现了不确定性，不可再现性，那显然这不是我们所需要的 。出现这种情况的原因是什么呢？大家考虑一下

大家应该可以分析出原因来自于ab两程序的一个共享变量n

显然程序并发执行时，多个程序共享系统中的各种资源，因而这些资源的状态由多个程序改变，致使程序运行失去了封闭性，也会导致其失去可再现性。

为了使程序在多道程序环境下能并发执行，并对并发执行的程序加以控制和描述，在操作系统中引入了进程概念，使程序的并发执行得以实行。

进程的概念是60年代初首先由麻省理工学院的MULTICS系统和IBM公司的CTSS/360系统引入的。

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。

进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念

从实现角度看，进程是一种数据结构，目的在于清晰地刻划动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。

我们在任务管理器里可以看到系统当前各个进程的情况

进程由程序、数据和进程控制块三部分组成。

我们接下来来看一下pcb

PCB记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息。使得一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

OS要调度某进程执行时，要从该进程PCB中查出其现行状态及优先级；在调度到某进程后，要根据PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据； 执行时，当需要完成进程间同步、通信或访问文件，也需要访问PCB；阻塞时，又必须将其断点的处理机环境保存在PCB中。

可见，在进程的整个生命周期中，系统总是通过PCB对进程进行控制的。所以我们会说pcb是进程存在的唯一标识

进程被创建时，系统为其分配PCB；进程结束时又回收PCB，进程于是也随之消亡（僵死进程）。PCB可以被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序以及监督和分析程序等读或修改。

我们可以看出PCB经常被系统访问，尤其是被运行效率很高的进程及分派程序访问，所以PCB是常驻内存的

接下来我们看一下进程的状态转换

大家需要注意图中箭头的方向
哪些状态转化是合法的哪些是不存在的
我们主要就挂起状态说一下加深了解

简单的说什么是挂起状态呢就是不接受调度的状态，指该进程的进程映像在磁盘上，挂起的目的是减少进程占用内存。

1.挂起： 把进程从内存转向外存
等待 -> 等待挂起
就绪 -> 就绪挂起
运行 -> 就绪挂起
2. 激活：从外存到内存
就绪挂起 -> 就绪
等待挂起 -> 等待

关于七态转化更多的解析我们下次课再继续给大家介绍 。以上重点解析供大家整理笔记

进程生命周期的状态转化

一个进程从创建而产生至撤销而消亡的整个生命周期，可以用一组状态加以刻划，最基本的是三态模型，进程的生命周期可分为如下三种进程状态：

1. 运行态(running):占有处理器正在运行
2. 就绪态(ready):具备运行条件，等待系统分配处理器以便运行

3. 等待态(blocked):不具备运行条件，正在等待某个事件的完成

   大家简单观察三态模型，可以分析出一些状态转化的发生原因，运行状态的进程将由于出现等待事件而进入等待状态，当等待事件结束之后等待状态的进程将进入就绪状态，而处理器的调度策略又会引起运行状态和就绪状态之间的切换。

   我们可以总结一下三态的基本转化
   

   引起三态图中进程状态转换的具体原因如下：
   运行态—→等待态：等待使用资源；如等待外设传输；等待人工干预。
   等待态—→就绪态：资源得到满足；如外设传输结束；人工干预完成。
   运行态—→就绪态：运行时间片到；出现有更高优先权进程。
   就绪态—→运行态：CPU 空闲时选择一个就绪进程。

   我们进一步引入新建态（new）和终止态（exit ）三态模型就变成五态模型，其状态转换图如下所示：
   
   ![{IUG942CEWS13%G07B7E~Q.jpg

   我们来解释一下新的五态图中的新增状态转化
   
   NULL—→新建态：执行一个程序，创建一个子进程。
   新建态—→就绪态：当操作系统完成了进程创建的必要操作，并且当前系统的性能和虚拟内存的容量均允许。
   运行态—→终止态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结。
   终止态—→NULL：完成善后操作。
   就绪态—→终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。
   等待态—→终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。

新建态对应于进程刚刚被创建的状态，我们来看一下创建一个进程的两个步骤，

1. 为一个新进程创建必要的管理信息，

2. 让该进程进入就绪态。此时进程将处于新建态，它并没有被提交执行，而是在等待操作系统完成创建进程的必要操作。需要注意的是，操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交

   进程的终止也要通过两个步骤，首先,是等待操作系统进行善后，然后,退出主存。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止态。进入终止态的进程以后不再执行，但依然临时保留在操作系统中等待善后 。 一旦其他进程完成了对终止态进程的信息抽取之后，操作系统将删除该进程。

到目前为止，我们总是假设所有的进程都在内存中。事实上，可能出现这样一些情况，例如由于进程的不断创建，系统的资源已经不能满足进程运行的要求，这个时候就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的。 所以就出现了七态转化图

上一节课我们也给大家解析了什么是挂起态

这里我们继续研究挂起，先来看一下引起进程挂起的原因，原因是多样的，主要的有：

1. 系统中的进程均处于等待状态，处理器空闲，此时需要把一些阻塞进程对换出去，以腾出足够的内存装入就绪进程运行。
2. 进程竞争资源，导致系统资源不足，负荷过重，此时需要挂起部分进程以调整系统负荷 ,保证系统的实时性或让系统正常运行。
3. 把一些定期执行的进程（如审计程序、监控程序、记账程序）对换出去，以减轻系统负荷。
4. 用户要求挂起自己的进程，以便根据中间执行情况和中间结果进行某些调试、检查和改正。
5. 父进程要求挂起自己的后代进程，以进行某些检查和改正。

6. 操作系统需要挂起某些进程，检查运行中资源使用情况，以改善系统性能;或当系统出现故障或某些功能受到破坏时，需要挂起某些进程以排除故障。

   我们回到七态转化图上，大家可以看到进程又增加了两个新状态：
   1、挂起就绪态（ready,suspend）
   挂起就绪态表明了进程具备运行条件但目前在二级存储器中，只有当它被对换到主存才能被调度执行
   2、挂起等待态（blocked,suspend）挂起等待态则表明了进程正在等待某一个事件且在二级存储器中。

   我们再观察新增两种状态之后的状态转化箭头

总结一下新增的状态转化

等待态—→挂起等待态：如果当前不存在就绪进程，那么至少有一个等待态进程将被对换出去成为挂起等待态；操作系统根据当前资源状况和性能要求，可以决定把等待态进程对换出去成为挂起等待态。
挂起等待态—→挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态。
挂起就绪态—→就绪态：当内存中没有就绪态进程，或者挂起就绪态进程具有比就绪态进程更高的优先级，系统将把挂起就绪态进程转换成就绪态。
就绪态—→挂起就绪态：操作系统根据当前资源状况和性能要求，也可以决定把就绪态进程对换出去成为挂起就绪态。
挂起等待态—→等待态：当一个进程等待一个事件时，原则上不需要把它调入内存。但是在下面一种情况下，这一状态变化是可能的。当一个进程退出后，主存已经有了一大块自由空间,而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化。
运行态—→挂起就绪态：当一个具有较高优先级的挂起等待态进程的等待事件结束后，它需要抢占 CPU，，而此时主存空间不够，从而可能导致正在运行的进程转化为挂起就绪态。另外处于运行态的进程也可以自己挂起自己。
新建态—→挂起就绪态：考虑到系统当前资源状况和性能要求，可以决定新建的进程将被对换出去成为挂起就绪态。

大家结合图自行查看

最后我们进一步总结一下挂起状态的特征

可以把一个挂起进程等同于不在主存的进程，因此挂起的进程将不参与进程调度直到它们被对换进主存。一个挂起进程具有如下特征：

1. 该进程不能立即被执行。
2. 挂起进程可能会等待一个事件，但所等待的事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。
3. 进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。
4. 结束进程挂起状态的命令只能通过操作系统或父进程发出。

进程的状态转化这块我们介绍得比较多，这部分是这章的一个重点

大家需要会画七态转化图，并且对图中每一种状态转化都可以解释说明

这部分也是各种考试必考的部分，希望课下大家根据课件和慕课以及老师课堂做的归纳总结，自行进一步学习记忆

接下来我们来学习下一小节处理机调度

2.3 处理器的调度

在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
这部分涉及到调度层次和很多算法
也是这章的重点
在多道程序系统中，进程的数量往往多于处理机的个数，进程争用处理机的情况就在所难免。处理机调度是对处理机进行分配，就是从就绪队列中，按照一定的算法（公平、髙效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。 相当于快到假期了，你列举了很多你想完成计划，但是没有办法同时完成所有的事情，你需要列一个时间表，把各种事情进行规划，执行的过程中也可能会有突发情况，你再根据突发情况进行解决。

下节课我们来详细介绍调度层次和算法

今天我们不继续往下讲，来把上节课的处理机调度加深一下，再做几个课堂练习
上节课学习了处理机调度，先来看这张调度层次图

大家在图中找一下上节课的三级调度

1.高级调度（作业调度）：按照某种规则，从后背队列中选择合适的作业将其调入内存，并为其创建进程
2.中级调度（内存调度）：按照某种规则，从挂起队列中农选择合适的进程将其数据调回内存
3.低级调度（进程调度）：按照某种规则，从就绪队列中选择一个进程为其分配处理机

我们来详细介绍下各级调度

按照上面的图中的顺序，我们先来看一下作业调度（高级调度/长程调度）。作业调度操作的对象是作业，此处的作业它表示的是一个比程序更广泛的意义，它既包含了程序和数据，同时还配有一份作业说明书，系统就是根据说明书来对程序的运行进行控制。每当一个作业进入系统时，便会有“作业注册”程序为这个作业创建一个 JCB（Job Control Block，作业控制块），JCB 中包含了系统对作业管理和调度所需的全部信息，其中也包含它的类型，系统就会根据这个类型将它放到相应的后备队列（外存）中等待作业调度。而且在批处理系统中，作业是从外存调入内存的基本单位。

作业调度就是按照一定的算法从后备队列中挑选一个或多个作业，给它们创建相应的进程（也即建立进程控制块 PCB）、分配内存等必要资源，然后将它们放入就绪队列（内存）中，以等待进程调度。作业调度主要任务就是接纳多少个作业，接纳哪些作业。接纳多少作业取决于内存中允许多少个作业同时运行，这个也称作多道程序度；而接纳哪些作业就涉及到调度的算法了，这里常用的调度算法有：

先来先服务（FCFS）
短作业优先（SJF）
优先级调度算法（PSA）
高响应比调度优先调度算法（HRRN）
具体的算法内容就先不在这里展开讲了，一会具体介绍算法我们再详细说明

作业调度主要用于多道批处理系统，在分时和实时系统中不设置作业调度。因为分时系统为了做到及时响应，用户通过键盘输入的命令或数据等会被直接送入内存，因而无需配置作业调度机制，但是它也需要设置某种接纳控制措施来限制进入系统的用户数目。类似地，实时系统中也不需要作业调度，但是必须要有接纳控制措施。

进程调度是运行频率最高的调度，分时系统中通常仅 10~100 ms 便进行一次，所以它也叫短程调度。进程调度操作的对象是进程（或内核级线程），它主要的功能是根据调度算法，决定就绪队列中的哪个进程应获得处理机，然后由分派程序将处理机分配给被选中的进程，因而它是最基本的一种调度，在多道批处理系统、分时、实时系统中都必须配置。

进程调度的任务大家可以看图理解

进程调度的方式有两种：抢占和非抢占方式。先来看非抢占方式，又称非剥夺调度方式：只允许进程主动放弃处理机，在运行过程中即使有更紧急的任务到达，当前进程依然会继续使用处理机，直到该进程终止或要求进入阻塞态。
它的优点是实现简单，系统开销小，但是却无法及时处理紧急任务，只适合早期批处理操作系统。

抢占方式，又称剥夺调度方式：当一个进程正在处理机上执行时，如果有一个更重要更紧急的进程要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧急的那个进程。但是抢占方式也不是随便就发生的，它也需要满足一定的条件或符合抢占原则，如：优先权原则、短进程优先原则、时间片原则等，
它的优点是可以优先处理更紧急的进程，但是抢占方式比较复杂，系统开销大，适合分时操作系统、实时操作系统。

由于进程调度的频率之高，应当避免调度本身占用 CPU 太多时间，所以一般不用太过于复杂的调度算法。作业调度算法的思想也都可以用在进程调度上，除此之外，进程调度还有一些特有的调度算法，综合起来，常见的进程调度算法有：

先来先服务(FCFS)
短进程优先(SPF)
优先级调度算法(PSA)
高响应比优先(HRRN)
时间片轮转调度算法(RR)
多级反馈队列(MFQ)

具体的算法内容就先不在这里展开讲了，一会具体介绍算法我们再详细说明

内存调度也称为中级调度，它的主要目的是提高内存的利用率和系统吞吐量，把那些暂时不能运行的进程调至外存，进程处于挂起状态，当它们具备运行条件并且内存又有空闲的时候，再由中级调度调回就绪队列。

进程一旦进入挂起状态（就绪挂起或阻塞挂起），就需要经过中级调度才能重新进入就绪队列，而且从图中我们也可很容易的看到，中级调度参与的双方是就绪挂起队列与就绪队列，那么如果一个进程从阻塞队列进入了阻塞挂起队列，它就必须等到相应事件出现并调入就绪挂起队列后，才能在下次事件出现时被调入就绪队列。

三级调度就介绍这些

接下来我们来加深一下各种调度算法 接下来我们来加深一下各种调度算法

1. 先来先服务（FCFS，first come first serve）

1.1 算法思想

主要从“公平”的角度考虑

1.2 算法规则

按照作业/进程到达的先后顺序进行服务。

1.3 用于作业/进程调度

用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列

1.4 是否可抢占

非抢占式的算法

1.5 优缺点

优点：公平，算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS对长作业有利，对短作业不利。

1. 短作业优先（SJF，shortest job first）

2.1 算法思想

追求最少的平均等待时间最少的平均周转时间，最少的平均带权周转时间

2.2 算法规则

最短的作业、进程优先得到服务（所谓“最短”，是指要求服务时间最短）

2.3 用于作业/进程调度

2种都可以。。 用于进程调度时被称为“短进程优先算法”（SPF，shortest process first）

2.4 是否可抢占

SJF和SPF是非抢占式算法，但也有抢占式的版本——最短剩余时间优先算法（SRTN，shortest remaining time next）

2.5 优缺点

优点：“最短的”平均等待时间，平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

![ICMZBJ47%3WGK`F77X)XRG.jpg

1. 高响应比优先（HRRN）

3.1 算法思想

综合考虑作业/进程的等待时间和要求服务的时间

3.2 算法规则

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。

响应比 = （等待时间 + 要求服务时间） / 要求服务时间

3.3 用于作业/进程调度

都可以

3.4 是否可抢占

是非抢占式算法，因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。

3.5 优缺点

综合考虑了等待时间和运行时间（要求服务时间）
等待时间相同是，要求服务时间短的优先（SJF的优点）
要求服务时间相同时，等待时间长的优先（FCFS的优点）
对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

这里大家注意响应比的计算，每一时刻的响应比都不同

这三种算法给出三个简单例题解析大家看一下

给十分钟大家自己大略看一下 熟悉一下算法

注意短作业优先的两种算法spf和srtn的区别

我们接着介绍最后两种算法
4 . 时间片轮转（RR，round-robin）

4.1 算法思想

公平的，轮流地为各个进程服务，让每一个进程在一定时间间隔内都可以得到相应。

4.2 算法规则

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

4.3 用于作业/进程调度

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

4.4 是否可抢占

可抢占式。若进程在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间已到。

4.5 优缺点

优点：公平，响应快，适用于分时操作系统。
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。

1. 优先级调度

5.1 算法思想

随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。

5.2 算法规则

每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

5.3 用于作业/进程调度

都可以。甚至，还会用于I/O调度中。

5.4 是否可抢占

抢占/非抢占都有。区别在于非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

5.5 优缺点

用优先级区分紧急程度，重要程度，适用于实时操作系统。可灵活的调整对各种作业/进程的偏好程度。
若源源不断地有高优先级进程到来，则可能导致饥饿。

![CD`F08Y$~U%H_8L_Q9M2N9.jpg

1. 多级反馈队列

6.1 算法思想

对其他调度算法的折中权衡。

6.2 算法规则

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第一队列……
只有第k即队列为空时，才会为第 k+1 级对头的进程分配时间片
6.3 用于作业/进程调度

用于进程调度。

6.4 是否可抢占

抢占式的算法。在k级队列的进程运行过程中，若更上级的队列（1-【k-1】级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

6.5 优缺点

对各类型进程相对公平（FCFS优点）
每个新到达的进程都可以很快得到相应（RR的优点）
短进程只用较少的时间就可完成（SPF的优点）
不必实现估计进程的运行时间（避免用户作假）
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程，I/O密集型进程

这三种算法我们也给出三个例题来熟悉一下，需要注意的是时间片轮转如果大家没太看懂不要紧，等十月份回到课堂可以当面提问答疑、这样讲解的会比较清晰。多级反馈队列不需要会计算，只了解原理即可

十分钟自己看一下例题，然后回到群里布置一题练习
我们来做一题练习

大家注意，这里的一些时间性概念我来说一下
平均周转时间：周转时间是指从作业被提交给系统开始，一直到作业完成为止的这段时间。周转时间由多个时间段组成：在后备队列中的等待时间、在就绪队列中的等待时间、在 CPU 中的执行时间、等待事件时间。平均周转时间就是所有作业周转时间之和再除以作业数目。
带权周转时间：是作业的周转时间与系统为它提供的服务时间之比。比如：A 作业的周转时间为 100，它的服务时间为 20，那么它的带权周转时间就是 100 / 20 = 5.
平均带权时间：就是对带权周转时间求平均值。

大家先自己做这个题目，15分钟后给大家答案和题解

我们来看一下解题过程

各作业运行情况如下图

注意，本题目规定的是优先数越小优先级越大

关于处理机调度的题目，慕课和群里的总结都不太直观，有的同学可能掌握得不太好，所以等10月份上课之后会安排一次两小节的习题课，关于处理机调度和pv操作的，给大家边讲边做练习

所以这块题目做得不太顺利的同学不要着急

上节课我们介绍了处理机调度
关于调度算法也做了一些练习

2.4 进程联系

我们来总结一下慕课里的知识点
先来看一下进程的制约关系，简单的说进程的制约关系就是并发进程之间彼此相关，相互影响，一个进程的执行可能影响其他进程的执行结果。制约关系的类型：根据共享资源性质的不同，可分为：
1、直接制约关系：也称”合作关系”，是指一个进程执行完后，另一个进程才能开始，否则不能开始。
2、间接制约关系：也称”竞争关系”，指一个进程访问共享资源时，其他需访问此资源的进程必须等待。

进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作

举一些例子大家理解一下
比如说进程A需要从缓冲区读取进程B产生的信息，当缓冲区为空时，进程B因为读取不到信息而被阻塞。而当进程A产生信息放入缓冲区时，进程B才会被唤醒。概念如图所示。

![7{9ZF_P}_MISEG_H)S0XUA.jpg
![)6[{3TSJO}%G{GT17JB)FW.jpg

在看司机和售票员之间的同步关系
再来看进程互斥，这是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。

比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。如图所示。

在举一些例子大家进一步了解互斥
![[Y5LBIOE]GP5V[CJUUHHKV.jpg
比如生产者和消费者共用一块缓冲区进行生产和消费
这里两者对缓冲区的访问就存在互斥关系

即一次只能一个进程进入缓冲区

大家可以自行分析下列活动分别属于哪种制约关系

若干同学去图书馆借书(互斥)
输入进程和计算进程(同步)
流水线生产的各道工序(同步)
若干进程使用一台打印机(互斥)
商品生产和社会消费(同步)

进程同步和互斥的关系
互斥反映了进程间的竞争关系，而同步则反映了进程间的合作关系。
进程互斥是进程同步的一种特殊情况
互斥所涉及的进程之间没有固定的必然的联系，它们只是竞争获得共享资源的使用权；而同步所涉及的并发进程之间有一钟必然的联系，即使资源可用，若没有获得同步消息，进程也不能去使用。

互斥和同步的比较：

2.5 临界区管理

最后总结一下临界资源

在操作系统中，进程是占有资源的最小单位（线程可以访问其所在进程内的所有资源，但线程本身并不占有资源或仅仅占有一点必须资源）。但对于某些资源来说，其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机，或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护，那么很有可能造成丢数据的问题)。

![N@8JQQ7(@L0P)$(5@{YJ.jpg

这个例子我们前面看过

P1、P2两个进程的执行顺序是随机的，P1、P2可能顺序执行或交错执行。由图可见，不同的执行顺序，COUNT值会不同，这是不允许的。

原因就是两个进程共享临界资源count

没有按规则对临界资源访问

对于临界资源的访问，必须是互斥进行。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。对于临界区的访问过程分为四个部分：

1.进入区:查看临界区是否可访问，如果可以访问，则转到步骤二，否则进程会被阻塞

2.临界区:在临界区做操作

3.退出区:清除临界区被占用的标志

4.剩余区：进程与临界区不相关部分的代码

临界区的访问管理准则如下：
1、空闲让进：当临界资源空闲时，可允许进入访问；
2、忙则等待：当临界区已有进程访问时，其他需进入临界区进程必须等待
3、有限等待：对于进入临界区的进程，应保证在有限时间内能进入临界区，以免陷入 “死等”状态；
4、让权等待：当进程不能进入临界区时，应立即释放CPU，以免进程陷入”忙等”。

需要注意系统中许多独占性硬件资源(如卡片输入机和打印机等)和软件资源(如变量、表格、队列、栈和文件等)均属于临界资源。

那么具体我们怎么样对临界资源实现互斥访问

下一次课我们会给大家重点介绍信号量实现对临界资源访问的方式。
这也是P V操作。通过设置一个表示资源个数的信号量S，通过对信号量S的P和V操作来实现进程的的互斥。P和V操作分别来自荷兰语Passeren和Vrijgeven，分别表示占有和释放。P V操作是操作系统的原语，意味着具有原子性。

这就不具体说明了

下次课我们再来学习

2.6 信息量与 P/V 操作

2.7 进程通信

今天我们来学习pv操作和进程之间的通信

pv操作这部分是这章的一个重点

我把教材相关页拍给大家配合慕课一起学习

在计算机操作系统中，PV操作是进程管理中的难点。首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

![Q{1}O9QEY(~AM(4NCVPEGO.jpg

s.value的值的含义定义如下

其中CR就是需求的资源

PV操作的意义是什么呢？我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

那么我们就来看一下互斥和同步各自如何用pv操作实现的

先来看互斥

利用信号量和PV操作实现进程互斥的一般模型是：
进程P1 进程P2
…… ……
P（S）； P（S）；
临界区； 临界区；
V（S）； V（S）；
…… ……

其中信号量S用于互斥，初值为1。

显然s初值为1，p1进程进入临界区之后s的值就为0

p2执行p（s）之后进入阻塞队列

实现了对临界区的互斥访问

再来看同步的实现模版

s初值为0，就意味着只能先做v操作，就是先执行p1

然后才能执行p2里的p操作

所以实现了p1

和p2的先后次序同步关系

这俩模版大家在做同步和互斥的题目的时候就可以套用了

再总结一下

使用PV操作实现进程互斥时应该注意的是：
（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。
（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
（3）互斥信号量的初值一般为1。

使用PV操作实现进程同步时应该注意的是：

（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。
（2）信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。
（3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。

我们来看一个生产者消费者经典问题的解决

我们为了更好地理解问题的实质，把生产者消费者问题由简至难分为三种类型，分别给大家分析

（1）一个生产者，一个消费者，公用一个缓冲区。

这是最简单的

两个进程之间的关系大家来分析，首先两进程互斥进入缓冲区，然后是需要同步，先生产再消费

（2）一个生产者，一个消费者，公用n个环形缓冲区。

分析一下和第一种情况的区别

区别就是需要设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指向下一个可用的缓冲区。

（3）一组生产者，一组消费者，公用n个环形缓冲区

再来分析这种情况下的关系

互斥关系如下

同步关系呢？

1、缓冲区为空，先生产再消费
2、缓冲区为满，先消费再生产

定义四个信号量：
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。
mutex1——生产者之间的互斥信号量，初值为1。
mutex2——消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

生产者进程：
while(TRUE){
生产一个产品;
P(empty);
P(mutex1)；
产品送往buffer（in）；
in=(in+1)mod n；
V(mutex1);
V(full);
}

消费者进程：
while(TRUE){
P(full)
P(mutex2)；
从buffer（out）中取出产品；
out=(out+1)mod n；
V（mutex2）；
V(empty);
消费该产品;
}

大家回去自己先看这两段程序分析能否实现我们提出的同步和互斥关系

这节课我们在慕课基础上继续加深对pv操作的理解，先回顾上节课的生产者消费者问题

问题描述：
⼀组⽣产者进程和⼀组消费者进程共享⼀个初始为空、固定⼤⼩为n的缓冲区。只有缓冲区没满时，⽣产者 才能把消息放⼊到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。 由于缓冲区是临界资源，它只允许⼀个⽣产者放⼊消息，或者⼀个消费者从中取出消息。


互斥和同步关系上节课已经介绍过如上图

这样定义三个信号量：
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。
mutex——生产者之间的互斥信号量，初值为1。

说明一下，每一对同步关系设置一个同步信号量，这样题目分析里两对同步关系，就设置两个同步信号量 empty和full 。需要注意同步信号量初值不一定为0，只要根据同步关系保证先后执行次序就可以了

对同一资源使用的一组进程可以设置一个互斥信号量，互斥信号量初值一般为1。再进一步解释操作过程

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

由于需要设缓冲区的编号为1～n-1，所以定义两个指针in和out，分别是生产者进程和消费者进程使用的指向下一个可用的缓冲区。

代码如下

生产者进程：
while(TRUE){
生产一个产品;
P(empty);
P(mutex)；
产品送往buffer（in）；
in=(in+1)mod n；
V(mutex);
V(full);
}

消费者进程：
while(TRUE){
P(full)
P(mutex)；
从buffer（out）中取出产品；
out=(out+1)mod n；
V（mutex）；
V(empty);
消费该产品;
}

大家观察分析这两段程序，之前讨论过的同步和互斥都是可以实现的

然后我们再考虑在两个进程里两个p操作能否交换顺序？两个v操作能否交换顺序？

我们一起来分析一下

需要注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 p(mutex) 再执行 p(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 p(empty) 操作，发现 empty = 0，也就是没有空的缓冲期可以放产品，此时生产者只能阻塞；但因为mutex的值已经为0，所以消费者不能进入临界区，消费者就永远无法执行 p(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

这就是下次课我们要讲的死锁现象
所以两个p操作不可以互换顺序
但两个v操作顺序任意，不影响
这也就是我们慕课里说的一般来说同步p操作要放在互斥p操作之前

再举个类似的例子进一步加深理解

有3个进程PA，PB和PC合作解决⽂件打印问题；
1、PA将⽂件记录从磁盘读⼊主存的缓冲区1，每执⾏⼀次读⼀个记录;
2、PB将缓冲区1的内容复制到缓冲区2，每执⾏⼀次复制⼀个记录；
3、PC将缓冲区2的内容打印出来，每执⾏⼀次打印⼀个记录。缓冲区的⼤⼩等于⼀个记录⼤⼩。 请⽤P，V操作来保证⽂件的正确打印。

在这里插入图片描述

![F8~Q@H4N2FV`}1%2S4~@UE.jpg

大家考虑这个题目和生产消费问题有什么相似之处

这是典型的双缓冲区问题，两个缓冲区⼤⼩均为1，其中PA为⽣产者，PB既是⽣产者又是消费者，PC为消费者， 故按照⽣产消费者问题的思路解决该题即可。但是需要注意的问题是：如果PA将数据放⼊缓冲区之后，PB没有及 时取的话，如果此时PA进程继续执⾏，那么会将之前的数据覆盖掉，缓冲区2也⼀样，因此这⾥还需要设置两个 信号量以限制缓冲区1和缓冲区2中记录的数量。

这是典型的双缓冲区问题，两个缓冲区⼤⼩均为1，其中PA为⽣产者，PB既是⽣产者又是消费者，PC为消费者， 故按照⽣产消费者问题的思路解决该题即可。但是需要注意的问题是：如果PA将数据放⼊缓冲区之后，PB没有及 时取的话，如果此时PA进程继续执⾏，那么会将之前的数据覆盖掉，缓冲区2也⼀样，因此这⾥还需要设置两个 信号量以限制缓冲区1和缓冲区2中记录的数量。

设置信号量full1，full2分别表⽰缓冲区1及缓冲区2是否有记录可供处理，初值均为0；
设置信号量empty1，empty2分别表⽰缓冲区1及缓冲区2是否还有空位可放记录，初值均为1；
设置互斥信号量mutex1，mutex2分别表⽰缓冲区1及缓冲区2的访问控制，初值均为1。

代码如下

semaphore full1 = 0;
semaphore full2 = 0;
semaphore empty1 = 1;
semaphore empty2 = 1;
semaphore mutex1 = 1;
semaphore mutex2 = 1;

PA() {
while (1) {
从磁盘读⼀一个记录；
P(empty1);
P(mutex1);
将记录存⼊入缓冲区1；
V(mutex1);
V(full1);
}
}

PB() {
while(1) {
P(full1);
P(mutex1);
从缓冲区1中读出⼀一个⽂文件记录；
V(mutex1);
V(empty1);
P(empty2);
P(mutex2);
将⼀一个记录读⼊入缓冲区2；
V(mutex2);
V(full2);
}
}

PC() {
while (1) {
P(full2);
P(mutex2);
从缓冲区2取⼀一个记录；
V(mutex2);
V(empty2);
打印记录;
}
}

大家可以自行分析一下

此类问题大家应该理解了，我们自己做两题练习一下

大家自己思考在纸上写一下

我们来看一下这两题
第一题

这个题目非常简单

就是考察信号量的含义
表示某类资源
初值为资源的初始数目

第二题
![V(B7U1X5XBC7QZNFQW~6$O.jpg

同样注意两个p操作的次序
登记表是互斥操作，seat是资源，进来一个就p操作减1，出去一个就v操作加1 ，也很好理解

接下来我们再来加深一个pv经典例题
读者写者问题，描述如下

有两组并发进程：读者和写者，共享文件F，要求：
（1）允许多个读者同时对文件进行读操作
（2）只允许一个写者对文件进行写操作
（3）任何写者在完成写操作前不允许其他读者或写者工作
（4）写者在执行写操作前，应让已有的写者和读者全部退出

先分析关系

读读不互斥，读写互斥，写写互斥

显然和生产消费不太一样 ，那怎么解决这个不同点呢？也就是不是所有进程都互斥进入缓冲区。我们可以这分析，把读者先来分类

把读者分三类

每一类所做的工作有所不同

为了区分三类读者就必须引入计数器rc对读进程计数，即做加1或减1操作。但大家都知道加1和减1操作在机器内部是三条语句完成的，为了不引起计数器的混乱，就必须对加减定义成原子操作，即需加1或减1一次性完成，mutex就是用于对计数器rc操作的互斥信号量，w则表示是否允许写的信号量，也就是写屏蔽开关

代码如下

 void reader(void)<br />{<br />while(TRUE)<br />{<br />P(mutex)；<br />rc = rc + 1;<br />if(rc == 1)  /*第一个读者*/<br />{<br />P(W);    /*不需要每给读者都做*/<br />}  <br />V(mutex)；                  <br />读操作；<br />P(mutex)；<br />rc = rc - 1;<br />if (rc == 0)/*最后一个读者*/<br />{<br />V(w)；<br />}<br />V(mutex)；<br />其他操作；<br />}<br />}

void writer(void)
{
while(TRUE)
{
……
P(W);
写操作；
V(w)；
……
}
}

类似读写问题我们再给出一个题目大家思考自己做一下

大家根据读写问题找异同，然后试着写一下

我们来看一下独木桥问题

![$Y%1`YATQ_9%B69ME6IP%8.jpg

![L(0VU23EOBV329O@W1AG4H.jpg

大家来分析 ，题目含义也就是同向不互斥，异向互斥，然后一次一个人过桥。其实相当于两个读者，但这个和读者又有区别，就是有一个互斥过桥的动作

所以其实我们是在读者进程基础上加了个过桥动作的互斥

大家可以回去自行分析

以上我们给大家介绍的都是记录型信号量的应用

接下来大家思考这个题目，看一下用常规的记录型信号量怎么描述

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。


大家试着写一下每位哲学家吃饭的过程
显然筷子是资源

给几分钟自己先写一下，写好检查能否正确执行
哲学家进餐问题可看作是并发进程并发执行时处理共享资源的一个有代表性的问题


代码大家应该都写出来了
注意这里wait就是p操作
signal就是v操作
但是这段代码看似没问题
仔细分析就会发现若五位哲学家每个人都同时饥饿而拿起了左边的筷子，这使五个信号量 chopstick 均为 0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁。

那怎么解决改进这个程序呢？

方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。
方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。
方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

方法一和三都可以通过算法设计解决
那么方法二呢？

下次课我们来研究方法二，给大家介绍and型信号量和信号量集机制