学习笔记|操作系统

操作系统

第一章 操作系统引论

1.2 操作系统的发展过程

1.2.1 未配置操作系统的计算机系统

人工操作方式

早期的操作方式是由程序员将事先已穿孔的纸带（或卡片），装入纸带输入机（或卡片输入机），再启动它们将纸带（或卡片）上的程序和数据输入计算机，然后启动计算机运行。仅当程序运行完毕并取走计算结果后，才允许下一用户上机。

缺点：

1. 用户独占全机

   一台计算机的全部资源由上机用户独占

2. CPU等待人工操作

   当用户进行装带（卡）、卸带（卡）等人工操作时，CPU及内存等资源是空闲的。

人机矛盾、CPU和I/O设备速度不匹配

脱机输入/输出(Off-Line I/O)

事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围机的控制下，把纸带（卡片）上的数据（程序）输入到磁带上。当CPU需要这些程序和数据时，再从磁带上高速调入内存。当CPU需要输出时，先由CPU把数据直接从内存高速地输送到磁带上，然后在另一台外围机的控制下，再将磁带上的结果通过相应的输出设备输出。

优点：

1. 减少了CPU的空闲时间

   装卸带（卡）、将数据从低速I/O设备送到高速磁带（或盘）上都是在脱机情况下进行的，不占用主机时间，缓和了人机矛盾。

2. 提高了I/O速度

   当CPU在运行中需要数据时，是直接从高速的磁带或磁盘上将数据调入内存的，缓和了CPU和I/O设备速度不匹配的矛盾，进一步减少了CPU的空闲时间。

1.2.2 单道批处理系统

单道批处理系统(Simple Batch Processing System)处理过程

首先由监督程序将磁带上的第一个作业装入内存，并将运行控制权交给该作业；当该作业处理完成时，又把控制权交还给监督程序，再由监督程序吧磁带上的第二个作业调入内存。计算机系统就这样自动地一个作业紧接着一个作业地进行处理，直至磁带上的所有作业全部完成。

单道批处理系统的特征

1. 自动性

   顺利情况下，在磁带上的一批作业能自动地逐个地依次运行而无需人工干预。

2. 顺序性

   磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序，在正常情况下应完全相同，即先调入内存的作业先完成。

3. 单道性

   内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常情况时，才还如其后继程序进入内存运行。

单道批处理系统的缺点

系统中的资源得不到充分的利用。

1.2.3 多道批处理系统

基本概念

用户所提交的作业先存放在外存上，并排成一个队列，称为“后备队列”。然后由作业调度程序按一定算法，从后备队列中选中若干个作业调入内存，使它们共享CPU和系统中的各种资源。由于同时在内存中装有若干个作业调入内存，使它们共享CPU和系统中的各种资源。由于同时在内存中装有若干道程序，这样便可以在运行程序A时，利用其因I/O操作而暂停执行时的CPU空档时间，再调度另一道程序B运行，便可以保持CPU处于忙碌状态。

多道批处理系统优缺点

1. 资源利用率高

   引入多道批处理能使多道程序交替运行，以保证CPU处于忙碌状态；

   在内存中装入多道程序可提高内存的利用率；

   提高I/O设备的利用率

2. 系统吞吐量大

   • CPU和其它资源保持“忙碌”状态
   • 仅当作业完成时或运行不下去时才进行切换，系统开销小

   系统吞吐量：单位时间内完成作业的数量

3. 平均周转时间长

   作业要排队依次进行处理，因而作业的周转时间较长，通常需要几个小时，甚至几天。

   周转时间：从提交到完成作业的时间

4. 无交互能力

   用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，修改和调试程序极不方便。

多道批处理系统需要解决的问题

1. 处理机争用问题

   既要满足各道程序运行的需要，又要能提高处理机的利用率。

2. 内存分配和保护问题

   系统应能为每道程序分配必要的内存空间，使它们“各得其所”，且不会因某道程序出现异常情况而破坏其它程序。

3. I/O设备分配问题

   系统应采取适当的策略来分配系统中的I/O设备，以达到既能方便用户对设备的使用，又能提高设备利用率的目的。

4. 文件的组织和管理问题

   系统应能有效地组织存放在系统中的大量的程序和数据，使它们既便于用户使用，又能保证数据的安全性。

5. 作业管理问题

   系统中存在着各种作业（应用程序），系统应能对系统中所有的作业进行合理的组织，以满足这些作业用户的不同要求。

6. 用户与系统接口问题

   为使用户能方便地使用操作系统，OS还应提供用户与OS之间的接口。

1.2.4 分时系统

为了满足用户对人-机交互的需求。

分时系统是指，在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源。

分时系统实现中的关键问题

系统首先必须能提供多个终端，同时给多个用户使用；其次，当用户在自己的终端上键入命令时，系统应能及时接收、并及时处理该命令，再将结果返回给用户。

1. 及时接收

   要做到及时接收多个用户键入的命令或数据，只需在系统中配置一个多路卡即可。多路卡的作用是实现分时多路复用，使主机能同时接收各用户从终端上输入的数据。此外，还须为每个终端配置一个缓冲区，用来暂存用户键入的命令（或数据）。

2. 及时处理

   人-机交互的关键在于，用户键入命令后能对自己的作业机器运行及时地实施控制，或进行修改。因此，各个用户的作业都必须驻留在内存中，并能频繁地获得处理机运行。

   • 作业直接进入内存
   • 采用轮转运行方式

分时系统的特征

1. 多路性

   该特性是指系统允许将多台终端同时连接到一台主机上，并按分时原则为每个用户服务。多路性允许多个用户共享一台计算机，显著地提高了资源利用率，降低了使用费用，从而促进了计算机更广泛的应用。

2. 独立性

   该特性是指系统提供了这样的用机环境，即每个用户在各自的终端上进行操作，彼此之间互不干扰，给用户的感觉就像是他一人独占主机进行操作。

3. 及时性

   该特性是指用户的请求能在很短时间内获得相应。这一时间间隔是根据人们所能接收的等待时间确定的，通常仅为1~3秒钟。

4. 交互性

   该特性是指用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以请求系统提供多方面的服务。

1.2.5 实时系统

实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时系统的类型

1. 工业(武器)控制系统
2. 信息查询系统
3. 多媒体系统
4. 嵌入式系统

实时任务的类型

1. 周期性实时任务和非周期性实时任务

   周期性实时任务：外部设备周期性地发出激励信号给计算机，要求它按规定周期循环执行，以便周期性地控制某外部设备。

   非周期性实时任务：无明显周期性，但联系着一个截止时间，或称为最终期限。它可分为：

   • 开始截止时间：某任务在某时间以前必须开始执行
   • 完成介质时间：某任务在某时间以前必须完成

2. 硬实时任务和软实时任务

   硬实时任务：系统必须满足任务对截止时间的要求

   软实时任务：也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。

实时系统与分时系统特征的比较

1. 多路性

   实时系统的多路性指的是系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制

2. 独立性

   实时系统中，对信息的采集和对对象的控制都是彼此互不干扰的

3. 及时性

   实时系统的实时性是以控制对象所要求的的截止时间来确定的

4. 交互性

   实时系统中，人与系统的交互性仅限于访问系统中某些特定的专用服务程序

5. 可靠性

   分时系统要求系统可靠，实时系统要求系统高度可靠，因为任何差错都看带来无法预料的灾难性后果

1.3 操作系统的基本特性

1.3.1 并发

并行与并发

并行性：两个或多个事件在同一时刻发生

并发性：两个或多个事件在同一时间间隔发生

多道程序环境下，并发性是指在一段时间内有多个程序在同时运行；

单处理机系统中，每一时刻只有一道程序在运行，这些程序只能是分时交替执行

并发是操作系统基本特征之一，引入了进程这一概念

进程

进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。

1.3.2 共享

在OS环境下的资源共享或成为资源复用，是指系统中的资源可供内存中多个并发执行的进程共同使用。

• 互斥共享方式

  当进程A要访问某资源时，必须先提出请求。若此时该资源空闲，系统便可将之分配给请求进程A使用，此后若再有其它进程也要也要访问该资源，只要A未用完则必须等待。仅当A进程访问完并释放系统资源后，才允许另一进程对该资源进行访问。

  把在一段时间内只允许一个进程访问的资源，称为临界资源

• 同时访问方式

  允许在一段时间内由多个进程“同时”对它们进行访问。（分时交替）

  例：磁盘设备

并发和共享是多用户OS的两个最基本的特征，它们又是互为存在的条件

• 资源共享是以进程的并发执行为条件
• 系统不能对资源共享实时有效管理以协调好诸进程对共享的资源的访问，必然会影响到进程间并发执行的程度

1.3.3 虚拟

在OS中，把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为“虚拟”。

• 时分复用技术

  时分复用技术能够提高资源利用率，它利用某设备为一用户服务的空闲时间，又转去为其他用户服务，使设备得到了充分利用。

  • 虚拟处理机技术

    利用多道程序技术，把一台物理上的处理机虚拟为多台逻辑上的处理机，在每台逻辑处理机上运行一道程序。

  • 虚拟设备技术

    将一台物理I/O设备虚拟为多台逻辑上的I/O设备，并允许每个用户占用一台逻辑上的I/O设备，这样便可以在一段时间内允许多个用户同时访问共享设备。

• 空分复用技术

  空分复用技术利用存储器的空闲空间分区域存放和运行其它的多道程序，以此来提高内存的利用率。

  虚拟存储技术实际上是实现内存的分时复用，即它可以通过分时复用内存的方式，使一道程序仅在远小于它的内存空间中运行。

1.3.4 异步

对于内存中的每个进程，在何时能获得处理机运行，何时有因提出某种资源请求而暂停，以及进程以怎样的速度向前推进，每道程序总共需要多少时间才能完成等等， 都是不可预知的。

进程是以不可预知的速度向前推进的，这就是进程的异步性。

1.4 操作系统的主要功能

1.4.1 处理机管理功能

处理机的分配和运行都是以进程为基本单位的，因而对处理机的管理可归结为对进程的管理。

处理机管理的主要功能有：创建和撤销进程，对诸进程的运行进行协调，实现进程之间的信息交换，以及按照一定算法把处理机分配给进程。

• 进程控制

  进程控制的主要功能就是为作业创建进程、撤销（终止）已结束的进程，以及控制进程在运行过程中的状态转换。

• 进程同步

  进程同步机制的主要任务是为多个进程（含线程）的运行进行协调。

  • 进程互斥方式

    诸进程在对临界资源进行访问时，应采用互斥方式

    为每一个临界资源配置一把锁W，当锁打开时，进程可以对该临界资源进行访问。

  • 进程同步方式

    在相互合作去完成共同任务的诸进程间，由同步机构对它们的执行次序加以协调。

    信号量机制

• 进程通信

  进程通信的任务是实现相互合作进程之间的信息交换。

• 调度

  调度包括作业调度和进程调度两步：

  • 作业调度

    从后备队列中按照一定的算法选择出若干个作业，为它们分配运行所需的资源，在将这些作业调入内存后，分别为它们建立进程，使它们都成为可能获得处理机的就绪进程，并将它们插入就绪队列中。

  • 进程调度

    从进程的就绪队列中按照一定算法选出一个进程，将处理机分配给它，并未它设置运行现场，使进程投入执行。

1.4.2 存储器管理功能

存储器管理的主要任务是为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，并能从逻辑上扩充内存。

• 内存分配

  • 为每道程序分配内存空间，使它们各得其所
  • 提高存储器的利用率，尽量减少不可用的内存空间
  • 允许正在允许的程序申请附加的内存空间，以适应程序和数据动态增长的需要

  OS在实现内存分配时，可采取静态和动态两种方式

  • 静态分配方式

    每个作业的内存空间是在作业装入时确定的，在作业装入后的整个运行期间不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”

  • 动态分配方式

    每个作业所要求的的基本内存空间在装入时是确定，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存中“移动”

• 内存保护

  内存保护的主要任务是：

  • 确保每道用户程序都仅在自己的内存空间内允许，彼此互不干扰
  • 绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其他用户程序中去执行

  设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。在程序运行时，系统须对每条指令所要访问的地址进行检查，如果发生越界，便发出越界中断请求，以停止该程序的执行。

• 地址映射

  能够将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。该功能在硬件的支持下完成。

• 内存扩充

  借助虚拟存储技术，从逻辑上扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多，以便让更多的用户程序能并发运行。

  • 请求调入功能

    系统允许在仅装入部分用户和程序的情况下，便能启动该程序运行。

  • 置换功能

    若发现在内存中已无足够的空间来装入需要调入的程序和数据时，系统应能将内存中的一部分暂时不用的程序和数据调至硬盘上，以腾出内存空间，然后再将所需调入的部分装入内存。

1.4.3 设备管理功能

设备管理功能的主要任务：

1. 完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作
2. 提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备

• 缓冲管理

  在I/O设备和CPU之间引入缓冲，可以有效缓和CPU和I/O设备速度不匹配的矛盾，提高CPU的利用率，进而提高系统吞吐量。

• 设备分配

  根据用户进程的I/O请求、系统现有资源情况以及按照某种设备分配策略，为值分配其所需的设备。

• 设备处理

  用于实现CPU和设备控制器之间的通信，即由CPU向设备控制器发出I/O命令，要求它完成指定的I/O操作；反之，由CPU接收从控制器发来的中断请求，并给予迅速的响应和相应的处理。

  设备处理过程是：首先检查I/O请求的合法性，了解设备状态是否是空闲的，读取有关的传递参数及设置设备的工作方式。然后向设备控制器发出I/O命令，启动I/O设备完成指定的I/O操作。

1.4.4 文件管理功能

文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

• 文件存储空间管理

  为每个文件分配必要的外存空间，提高外存的利用率，进而提高文件系统的存取速度。

• 目录管理

  为每个文件建立一个目录项，目录项包括文件名、文件属性、文件在磁盘上的物理位置等，并对众多的目录项加以有效的组织，以实现方便的按名存取。

• 文件的读/写管理和保护

  • 文件的读/写管理

    根据用户请求，从外存中读取数据，或将数据写入外存。

  • 文件保护

    放置未经核准的用户存取文件；放置冒名顶替存取文件；放置以不正确的方式存取文件

1.4.5 操作系统与用户之间的接口

• 用户接口

  用户可以通过该接口向作业发出命令以控制作业的运行。

  • 联机用户接口
  • 脱机用户接口
  • 图形用户接口

• 程序接口

  程序接口是为用户程序在执行中访问系统而设置的，是用户程序取得操作系统服务的唯一途径。

1.5 OS结构设计

1.5.1 传统操作系统结构

• 无结构操作系统

• 模块化结构OS

  为使OS具有较清晰的结构，OS不再是由众多的过程直接构成的，而是按其功能精心地划分为若干个具有一定独立性和大小的模块。

  

  在模块-接口设计方法中，关键问题是模块的划分和规定好模块之间的接口。

  模块独立性越高，各模块间的交互就越少，系统的结构也就越清晰。

  • 内聚性：指模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越强。
  • 耦合度：模块间相互联系和相互影响的程度。耦合度越低，模块独立性越强。

  优点：

  • 提高OS设计的正确性、可理解性和可维护性
  • 增强OS的可适应性
  • 加速OS的开发过程

  问题：

  • 对各模块间的接口规定很难满足在模块设计完成后对接口的实际需求
  • 设计者必须做出一系列的决定，每一个决定必须建立在上一个决定的基础上。“无序”

• 分层式结构OS

  在目标系统A_n和裸机系统A₀之间，铺设若干个层次的软件A₁、A₂、A₃、…、A_n-1，使A_n通过A_n-1、A_n-2、…、A₂、A₁层，最终能在A₀上运行。

  自底向上的分层设计的基本原则是每一步设计都是建立在可靠的基础上，每一层仅能使用期底层所提供的功能和服务。

  优点

  • 易保证系统的正确性
  • 易扩充和易维护性

  缺点

  • 系统效率降低

1.5.2 客户/服务器模式简介

可简称为C/S模式。

• 客户机
• 服务器
• 网络系统

交互过程

• 客户发送请求消息
• 服务器接收消息
• 服务器回送消息
• 客户机接收消息

优点

• 数据的分布处理和存储
• 便于集中管理
• 灵活性和可扩充性
• 易于改编应用软件

1.5.4 微内核OS结构

• 足够小的内核

  微内核并非是一个完整的OS，而是将操作系统中最基本的部分放入微内核，其中包含

  • 与硬件处理紧密相关的部分
  • 一些较基本的功能
  • 客户和服务器之间的通信

• 基于客户/服务器模式

  

• 应用“机制与策略分离原理”

  机制是指实现某一功能的具体执行机构，通常处于系统基层，在微内核操作系统中，将机制放在OS的微内核中。

  策略是指在机制的基础上借助于某些参数和算法来实现该功能的优化，或达到不同的功能目标，通常处于系统高层。

• 采用面向对象技术

  基于面向对象技术中的“抽象”和“隐蔽”的原则控制系统的复杂性，在进一步利用"对象"、“封装”、“继承"等概念来确保操作系统的"正确性”、“可靠性”、“易修改性”、"易扩展性"等，并提高操作系统的设计速度。

基本功能

• 进程（线程）管理

  采用“机制与策略分离”原理

• 低级存储器管理

• 中端和陷入处理

优点

• 提高了系统的可扩展性
• 增强了系统的可靠性
• 可移植性强
• 提供了对分布式系统的支持
• 融入了面向对象技术

问题

• 微内核操作系统的运行效率有所降低

  

第二章 进程的描述与控制

2.1 前趋图和程序执行

2.1.1 前趋图

前趋图：一个有向无循环图，可记为DAG，用于描述进程之间执行的先后顺序。结点间的有向边则表示两个结点之间存在的偏序或前趋关系。

若P_i和P_j存在着前趋关系，克表示为(P_i，P_j)∈→，也可写成P_i→P_j，表示在P_j开始执行之前，P_i必须完成。

没有前趋的结点称为初始结点，没有后继的结点称为终止结点，每个结点具有一个重量，表示该结点所含有的程序量或程序执行时间。

下图a中存在前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9

前趋图是不允许存在循环的，图b是不可能实现的前趋图。

2.1.2 程序顺序执行

执行时需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。

程序顺序执行时的特征：

1. 顺序性

   处理机严格按照程序锁规定的顺序执行，每一操作必须在下一操作开始之前结束

2. 封闭性

   程序在封闭的环境下运行，程序运行时独占全机资源

3. 可再现性

   只要程序执行时的环境和初始条件相同，当程序重复执行时，无论停顿与否都可以获得相同的结果

2.1.3 程序并发执行

只有在不存在前趋关系的程序之间才有可能并发执行。

程序并发执行时的特征：

1. 间断性

   程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。

2. 失去封闭性

   当系统中存在着多个可以并发执行的程序时，系统中各种资源被共享，致使其中任一程序在运行时，环境都必然会受到其它程序的影响。

3. 不可再现性

   由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，使程序的执行失去了可再现性。

2.2 进程的描述

2.2.1 进程的定义和特征

进程：进程是程序的一次执行；进程是进程实体的运行过程，它是系统进行资源分配和调度的一个独立单位。

进程实体：程序段、相关的数据段和PCB

进程控制块PCB：描述进程的基本情况和活动过程，进而控制和管理进程。

进程的特征：

1. 动态性

   进程的实质是进程实体的执行过程。

   由创建而产生，由调度而执行，由撤销而消亡。

   进程是动态的，程序是静态的。

2. 并发性

   多个进程实体同存于内存中，且能在一段时间内同时运行。

3. 独立性

   进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。

4. 异步性

   按各自独立的、不可预知的速度向前推进。

2.2.2 进程的基本状态及转换

进程的三种基本状态

• 就绪(Ready)状态

  进程已处于准备好运行的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。

• 执行(Running)状态

  进程已获得CPU，其程序正在执行的状态。

• 阻塞(Block)状态

  正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行时的状态，亦即进程的执行受到阻塞。

三种基本状态的转换

创建状态和终止状态

进程是由创建而产生。

1. 向进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息
2. 为该进程分配运行时所必须的资源
3. 把该进程转入就绪状态并插入就绪队列之中

终止

1. 等待操作系统进行善后处理
2. 将其PCB清零，并将PCB空间返还系统

2.2.3 挂起操作和进程状态的转换

挂起操作，基于系统和用户以下需要：

1. 终端用户的需要
2. 父进程请求
3. 负荷调节的需要
4. 操作系统的需要

2.2.4 进程管理中的数据结构

进程控制块PCB的作用：

1. 作为独立运行基本单位的标志
2. 能实现间断性运行方式
3. 提供进程管理所需要的信息
4. 提供进程调度所需要的信息
5. 实现与其它进程的同步与通信

进程控制块PCB中的信息：

1. 进程标识符

   唯一地标识一个进程。

   • 外部标识符
   • 内部标识符

2. 处理机状态

   • 通用寄存器
   • 指令计数器
   • 程序状态字
   • 用户栈指针

3. 进程调度信息

   • 进程状态
   • 进程优先级
   • 进程调度所需的其它信息
   • 事件(阻塞原因)

4. 进程控制信息

   • 程序和数据的地址
   • 进程同步和通信机制
   • 资源清单
   • 链接指针

进程控制块的组织方式

• 线性方式

  将所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中

• 链接方式

  把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列

• 索引方式

  系统根据所有进程状态的不同，建立几张索引表

2.3 进程控制

操作系统内核

1. 支撑功能
   • 中断处理
   • 时钟管理（时间片）
   • 原语操作（由若干条指令组成，在执行过程中不允许被中断）
2. 资源管理功能
   • 进程管理
   • 存储器管理
   • 设备管理

进程图

用于描述进程间关系的一棵有向树。图中的结点代表进程。

引起创建进程的事件

1. 用户登录
2. 作业调度
3. 提供服务
4. 应用请求

进程的创建

• 申请空白PCB
• 为新进程分配其运行所需的资源
• 初始化进程控制块PCB
• 将新进程插入就绪列

进程的终止

• 正常结束
• 异常结束
• 外界干预

进程终止过程

1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
2. 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
3. 若该进程还有子孙进程，还应将子孙进程也终止
4. 将被终止进程所有全部资源或者归还给其父进程，或归还给系统
5. 将被终止进程从所在队列中移出

引起进程的阻塞与唤醒的事件

• 向系统请求共享资源失败
• 等待某种操作的完成
• 新数据尚未到达
• 等待新任务的到达

进程阻塞过程

阻塞原语：block

阻塞是进程自身的一种主动行为。

进程唤醒过程

调用唤醒原语wakeup，将等待该事件的进程唤醒。

wakeup的过程是：

• 把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中

进程的挂起

挂起原语：suspend

进程的**

挂起原语：active

2.4 进程同步

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

两种形式的制约关系

间接实现互斥，直接实现同步

• 间接相互制约关系

  多个程序在并发执行时，由于共享系统资源致使这些执行程序之间形成相互制约的关系。

• 直接相互制约关系

  前趋图

临界资源

诸进程间应采取互斥方式，实现对临界资源的共享。

临界区

程序代码中访问临界资源的部分。

while(TRUE)
{
	进入区
	临界区
	退出区
	剩余区
}

同步机制

• 空闲让进
• 忙则等待
• 有限等待：在有限时间内能进入自己的临界区，以免陷入“死等”状态
• 让权等待：进程不能进入临界区时应立即释放处理机

硬件同步机制

• 关中断

  在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。

• Test-and-Set指令实现互斥

  boolean TS(boolean *lock)
  {
  	boolean old;
  	old = *lock;
  	*lock = TRUE;
  	return old;
  }
  
  do{
  	…
  	while TS(&lock)
  	critical section;
  	lock = FALSE;
  	remainder section;
  }while(TRUE)
  

• 利用Swap指令实现进程互斥

  void swap(boolean *a, boolean *b)
  {
  	boolean temp;
  	temp = *a;
  	*a = *b;
  	*b = temp;
  }
  
  do{
  	key = TRUE;
  	do{
  		swap(&lock,&key);
  	}while(key!=FALSE)
  	临界区操作;
  	lock = FALSE;
  	…
  }while(TRUE)
  

信号量机制

• 整型信号量

  wait(S)和signal(S)被分别称为P、V操作。

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

• 记录型信号量

  代表资源数目的整型变量value，一个进程链表指针list，用于链接上述所有等待进程。

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

  S->value的初值表示系统某类资源的数目，它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个；当S->value<0时，表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S->list中。此时S->value的绝对值表示在该信号量链表中已阻塞的数目。

  若S->value++后S->value≤0，则表示该信号量链表中仍有等待该资源的进程被阻塞，故调用wakeup原语，唤醒链表中的第一个等待进程。

• AND型信号量

  将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放，只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。

• 信号量集

  进程对信号量S_i是该资源的分配下限值t_i，要求S_i≥t_i，否则不予分配。一旦允许分配，进程对该资源的需求值为d_i，即表示资源占用量，进行S_i=S_i-d_i操作。

  特殊情况

  • Swait(S,d,d)：只有一个信号量S，允许每次申请d个资源，当少于d时，不予分配
  • Swait(S,1,1)：一般的记录型信号量(S>1)或互斥信号量(S=1)
  • Swait(S,1,0)：S≥1，允许多个进程进入某特定区；S=0，将阻止任何进程进入特定区

利用信号量实现进程互斥

两个信号量互斥

1. 设mutex为互斥信号量，其初值为1，取值范围为(-1,0,1)。当mutex=1时，表示两个进程皆未进入需要互斥的临界区；当mutex=0时，表示有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列；当mutex=-1时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。

2. 代码描述

   semaphore mutex=1;
   PA(){
   	while(1){
   		wait(mutex);
   		临界区
   		signal(mutex);
   		剩余区
   	}
   }
   

利用信号量实现前趋关系

Var a,b,c,d,e,f,g：semaphore: =0,0,0,0,0,0,0；
p1(){S1;signal(a);signal(b);}
p2(){wait(a);S2;signal(c);signal(d);}
p3(){wait(b);S3;signal(e);}
p4(){wait(c);S4;signal(f);}
p5(){wait(d);S5;signal(g);}
p6(){wait(e);wait(f);wait(g);S6;}

管程机制

代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称之为管程。

• 管程的名称
• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部于管程的共享数据设置初始值的语句

管程和进程的不同

• 进程定义的是私有数据结构PCB，管程定义的是公共数据结构
• 进程是由顺序程序执行有关操作，管程进行同步操作和初始化操作
• 进程的设置目的在于实现系统的并发性，管程的设置目的则是解决共享资源互斥使用问题
• 进程为主动工作方式，管程为被动工作方式
• 进程具有动态性，管程是操作系统中的一个资源管理模块，供进程调用

2.5 经典进程的同步问题

设信号量→赋初值→编程（每一进程）

生产者-消费者问题

哲学家进餐问题

读者-写者问题

2.6 进程通信

低级进程通信（信号量）

• 效率低
• 通信对用户不透明

高级进程通信

• 使用方便
• 高效地传送大量数据

进程通信的类型

• 共享存储器系统

  相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。

  • 基于共享数据结构的通信方式
  • 基于共享存储区的通信方式

• 管道通信系统

  所谓“管道”，指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件

• 消息传递系统

  以格式化消息为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令，在进程间进行消息传递，完成进程间的数据转换

  • 直接通信方式

    发送进程利用OS所提供的发送原语，直接把消息发送给目标进程

  • 间接通信方式

    发送和接收进程，都通过共享中间实体的方式进行消息的发送和接收，完成进程间的通信。

• 客户机-服务器系统

  • 套接字
    • 基于文件型
    • 基于网络型
  • 远程过程调用
  • 远程方法调用

消息传递通信的实现方式

• 直接消息传递系统

  发送进程利用OS所提供的发送命令（原语），直接把消息发送给目标进程。

  1. 直接通信原语

     • 对称寻址方式

       send(receiver,message);

       receive(sender,message);

     • 非对称寻址方式

       send(P,message);

       receive(id,message);

  2. 消息的格式

  3. 进程的同步方式

  4. 通信链路

• 信箱通信

  1. 信箱的结构
     • 信箱头：用于存放有关信箱的描述信息
     • 信箱体：由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目已经每格的大小是在创建信箱时确定的
  2. 信箱通信原语
     • 邮箱的创建和撤销
     • 消息的发送和接收
  3. 信箱的类型
     • 私用邮箱
     • 公用邮箱
     • 共享邮箱

直接消息传递系统实例

2.7 线程的基本概念

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

线程与进程的比较

• 调度的基本单位

  进程是能独立运行的基本单位，在每次被调度时，都需要进行上下文切换，开销较大；

  线程切换仅需保存和设置少量寄存器内容，切换代价远低于进程

• 并发性

  都可以并发执行

• 拥有资源

  进程可以拥有资源，并作为系统中拥有资源的一个基本单位；

  线程并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源

• 独立性

  进程间地址空间和资源互相独立；

  线程间共享地址空间和资源

• 系统开销

  进程需要切换上下文；线程没什么资源，开销小

• 支持多处理机系统

  进程必须在单处理机上运行；

  单进程中的多线程可分配到不同处理机上执行

第三章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

处理机调度的层次

• 高级调度（作业调度）

  调度对象是作业，主要用于多道批处理系统中。

• 低级调度（进程调度）

  调度对象是进程，基本调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。

• 中级调度（内存调度）

  主要目的是提高内存利用率和系统吞吐量。

处理机调度算法的共同目标

• 资源利用率
  C P U 的 利 用 率 = C P U 有 效 工 作 时 间 C P U 有 效 工 作 时 间 + C P U 空 闲 等 待 时 间 CPU的利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间} CPU的利用率=CPU有效工作时间+CPU空闲等待时间CPU有效工作时间​

• 公平性

  诸进程都获得合理的CPU时间，不会发生进程饥饿现象。

• 平衡性

  CPU都能经常处于忙碌状态；系统资源的平衡性。

• 策略强制执行

  如安全策略。

批处理系统的目标

• 平均周期时间短

  周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔，包括作业在外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。

  平均周转时间最短，有效提高系统资源利用率，可使大部分用户满意。

  平均周转时间：
  T = 1 n [ ∑ i = 1 n T i ] T=\frac{1}{n}[\sum_{i=1}^{n}{T_i}] T=n1​[i=1∑n​Ti​]
  平均带权周转时间：
  W = 1 n ∑ i = 1 n T i T s W=\frac{1}{n}\sum_{i=1}^{n}{\frac{T_i}{T_s}} W=n1​i=1∑n​Ts​Ti​​
  作业周转时间 T T T，系统为其服务时间 T s T_s Ts​

• 系统吞吐量高

  吞吐量：在单位时间内系统所完成的作业数

• 处理机利用率高

分时系统的目标

• 响应时间快

  响应时间：从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。

• 均衡性

  均衡性：系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标

• 截止时间的保证

  截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间

• 可预测性

3.2 作业与作业调度

作业：包含程序、数据、作业说明书。

作业步：完成作业的每一个加工步骤。

作业控制块JCB：是作业在系统中存在的标志。

作业运行的三个阶段和三种状态

1. 收容阶段。 后备状态
2. 运行阶段。 运行状态
3. 完成阶段。 完成状态

作业调度的主要任务

1. 接纳多少个作业（允许多少个作业同时在内存中运行）
2. 接纳哪些作业（取决于所采用的调度算法）

先来先服务FCFS调度算法

作业调度√，进程调度√

系统按照作业到达的先后顺序来进行调度，优先考虑等待时间最长的作业。

有利于长作业(进程)，不利于短作业(进程)

有利于CPU繁忙型作业，不利于I/O繁忙型作业

短作业优先SJF调度算法

作业调度√，进程调度√

以作业长短来计算优先级，作业越短，优先级越高。作业的长短是以作业所要求的运行时间来衡量的。

缺点：

• 必须预知作业的运行时间
• 对长作业非常不利
• 人-机无法交互
• 未考虑作业的紧迫程度

优先级调度PSA算法

作业调度√，进程调度√

基于作业的紧迫度，由外部赋予作业相应的优先级。

高响应比优先调度HRRN算法

进程都到之后开始计算优先权。

动态优先级
优 先 权 = 等 待 时 间 + 要 求 服 务 时 间 要 求 服 务 时 间 = 响 应 时 间 要 求 服 务 时 间 = 响 应 比 R p 优先权=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}=响应比R_p 优先权=要求服务时间等待时间+要求服务时间​=要求服务时间响应时间​=响应比Rp​

• 作业等待时间相同，服务时间越短，优先级越高
• 要求服务时间相同，等待时间越长，优先级越高
• 厂作业优先级可以随等待时间的增加而提高

缺点：每次调度都需计算

3.3 进程调度

进程调度的任务

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

进程调度机制

• 排队器
• 分派器
• 上下文切换器

进程调度方式

• 非抢占方式：一旦分配给某进程，就一直让它运行下去。
  • 正在执行的进程运行完毕，或因发生某时间而使其无法再继续运行
  • 正在执行中的进程因提出I/O请求而暂停执行
  • 进程通信或同步过程中，执行了某种原语操作
• 抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程
  • 优先权原则
  • 短进程优先原则
  • 时间片原则

轮转调度RR算法

• 一个时间片尚未用完，正在允许的进程便已完成
• 在一个时间片用完时，计时器中断处理程序被**，若进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

多级反馈队列调度算法

• 设置多个就绪队列（优先级逐个降低，时间片逐个增大）
• 每个队列都采用FCFS算法（新进程进入，加入第一队列末尾，若未在时间片内完成，则到第二队列末尾）
• 按队列优先级调度

调度算法的性能

• 终端型用户
• 短批处理作业用户
• 长批处理作业用户

3.5 死锁概述

死锁产生原因：多个进程对资源的争夺

• 竞争不可抢占性资源引起死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。

产生死锁的必要条件：

• 互斥条件
• 请求和保持条件
• 不可抢占条件
• 循环等待条件

处理死锁的方法：

• 预防死锁
• 避免死锁
• 检测死锁
• 解除死锁

预防死锁

破坏四个必要条件之一，其中互斥不能破坏。

• 破坏“请求和保持”条件：进程在中间不会请求新的资源
• 破坏“不可抢占”条件：不可抢占→可抢占，影响进程执行效率
• 破坏“循环等待”条件：规定每个进程必须按序号递增的顺序请求资源

避免死锁

安全状态：系统能按某种进程推进顺序（ P 1 , P 2 , … , P n P_1,P_2,…,P_n P1​,P2​,…,Pn​）为每个进程 P i P_i Pi​分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。

银行家算法避免死锁

四个数据结构：

• 可利用资源向量Available

• 最大需求矩阵Max

• 分配矩阵Allocation

• 需求矩阵Need

  N e e d [ i , j ] = M a x [ i , j ] − A l l o c a t i o n [ i , j ] Need[i,j]=Max[i,j]-Allocation[i,j] Need[i,j]=Max[i,j]−Allocation[i,j]

银行家算法：

1. R e q u e s t i [ j ] ≤ N e e d [ i , j ] Request_i[j]≤Need[i,j] Requesti​[j]≤Need[i,j]，便转向步骤2；否则认为出错。

2. R e q u e s t i [ j ] ≤ A v a i l a b l e [ j ] Request_i[j]≤Available[j] Requesti​[j]≤Available[j]，便转向步骤3；否则表示尚无足够资源， P i P_i Pi​须等待。

3. 系统试探着把资源分配给进程 P i P_i Pi​，并修改下面数据结构中的数值：

   A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t i [ j ] ; Available[j]=Available[j]-Request_i[j]; Available[j]=Available[j]−Requesti​[j];

   A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t i [ j ] ; Allocation[i,j]=Allocation[i,j]+Request_i[j]; Allocation[i,j]=Allocation[i,j]+Requesti​[j];

   N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t i [ j ] ; Need[i,j]=Need[i,j]-Request_i[j]; Need[i,j]=Need[i,j]−Requesti​[j];

4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态，若安全才正式将资源分配 给进程 P i P_i Pi​，否则作废，恢复原来的资源分配状态。

安全性算法：

1. 设置两个向量：

   • 工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目， W o r k = A v a i l a b l e Work=Available Work=Available
   • Finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始时 F i n i s h [ i ] = f a l s e Finish[i]=false Finish[i]=false；当有足够资源分配给进程时， F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true

2. 从进程集合中找到一个能满足下述条件的进程

   • F i n i s h [ i ] = f a l s e Finish[i]=false Finish[i]=false
   • N e e d [ i , j ] ≤ W o r k [ j ] Need[i,j]≤Work[j] Need[i,j]≤Work[j]

   若找到，执行步骤3，否则执行4

3. 当进程 P i P_i Pi​获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

   W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i , j ] ; Work[j]=Work[j]+Allocation[i,j]; Work[j]=Work[j]+Allocation[i,j];

   F i n i s h [ i ] = t r u e ; Finish[i]=true; Finish[i]=true;

   go to step 2​

4. 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态。

3.8 死锁的检测与解除

资源分配图

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。

解除死锁

• 抢占资源
• 终止（或撤销）进程