v5le0n9's garden

小凉的秘密基地

操作系统

发表于 更新于 分类于
本文字数： 46k 阅读时长 ≈ 42 分钟

这个笔记是基于 王道考研 操作系统 写的，我觉得前面会讲得有点枯燥，但后面结合图和例题讲算法时非常不错，可以一看。

1. 操作系统概述

操作系统（英语：Operating System，缩写：OS）是管理计算机硬件与软件资源的系统软件，同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

1.1 操作系统的功能

  1. 作为系统资源的管理者：文件管理、设备管理、内存管理、处理机制(进程管理)

    目标：安全、高效

  2. 作为用户和计算机硬件之间的接口：命令接口、程序接口(系统调用)、图形用户界面(GUI)

    目标：方便用户使用

  3. 作为最接近硬件层次：实现对硬件及其的扩展

1.2 操作系统的特征

1.2.1 并发

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

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

操作系统的并发性指计算机系统中同时存在着多个运行着的程序。操作系统通过引入进程与线程，使得程序能够并发运行。

1.2.2 共享

共享：指系统中的资源可供内存中多个并发执行的进程共同使用。

有两种共享方式：互斥共享和同时共享。

互斥共享：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

同时共享：系统中的某些资源，允许一个时间段内由多个进程并发对它们进行访问。

1.2.3 虚拟

虚拟：把物理上的实体转换为多个逻辑上的对应物。物理实体是实际存在的，而逻辑上的对应物是用户感受到的。

主要有两种虚拟技术：时分复用技术和空分复用技术。

多个进程在同一个处理器并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一个小时间片，并且这个时间片在进程之间互相切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间和物理内存使用页面进行交换。地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

1.2.4 异步

异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。

如果失去了并发性，则系统只能串行地处理各个进程，每个进程的执行会一贯到底。如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义。同样共享也是建立在并发的基础上的，如果没有并发，共享是无法实现的。所以并发是共享、虚拟、异步的前提。

1.3 操作系统的发展和分类

1.3.1 手工操作阶段

主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低

1.3.2 批处理系统

1.3.2.1 单道批处理系统

引入脱机输入/输出技术(用磁带完成)，并监督程序(操作系统的雏形)负责控制作业的输入、输出。

主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。

主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量时间是在空闲等待I/O完成。资源利用率依然很低。

1.3.3.2 多道批处理系统

主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其它资源保持“忙碌”状态，系统吞吐量增大。

主要缺点：用户响应时间长，没有人机交互功能(用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业运行)

1.3.3 分时操作系统

分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

主要优点：用户请求可以被及时响应，解决了人机交互的问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

1.3.4 实时操作系统

主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

1.4 操作系统的运行机制和体系结构

1.5 中断和异常

发生了中断，意味着需要操作系统的介入，开展管理工作。由于操作系统的管理工作(比如进程切换、分配I/O设备等)需要使用特权指令，因此CPU要从用户态转为核心态。中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。有了中断，才能实现多道程序并发执行。

用户态、核心态之间的切换是怎么实现的？

答：用户态 -> 核心态是通过中断实现的，并且中断是唯一途径。

​ 核心态 -> 用户态的切换是通过执行一个特权指令，将程序状态字的标志位设置为“用户态”。

1.5.1 中断的分类

内中断信号来源于CPU内部，与当前执行的指令有关；外中断信号来源于CPU外部，与当前执行的指令无关。

1.5.2 外中断的处理过程

  1. 每条指令执行结束后，CPU检查是否有外部中断信号
  2. 若有外部中断信号，则需要保护被中断进程的CPU环境
  3. 根据中断信号类型转入相应的中断处理程序
  4. 恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

1.6 系统调用

系统调用是操作系统提供给应用程序(程序员/编程人员)使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。

应用程序通过系统调用请求操作系统。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作(如存储分配、I/O操作、文件管理等)，都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用相关处理涉及到对系统资源的管理、对进程的控制，这些功能需要执行一些特权指令才能完成，因此系统调用的相关处理需要在核心态下完成。

1.6.1 系统调用和库函数的区别

系统调用是操作系统向上层提供的接口，有的库函数是对系统调用的进一步封装，当今编写的应用程序大多是通过高级语言提供的库函数间接地进行系统调用。

1.6.2 系统调用背后的过程

  1. 传递系统调用参数
  2. 执行陷入指令(如int 0x80)（用户态）
  3. 执行系统调用相应服务程序（核心态）
  4. 返回用户程序

陷入指令是唯一一个只能在用户态执行，而不可在核心态执行的指令。

2. 进程

程序段、数据段、PCB(进程控制块)三部分组成了进程实体(进程映像)。一般情况下，我们把进程实体就简称为进程。PCB是进程存在的唯一标志。

2.1 进程的组成

操作系统所需的数据在PCB中，程序本身运行所需的数据在程序段和数据段中。

2.2 进程的组织

在一个系统中，通常有数十、数百乃至数千个PCB。为了能对它们加以有效的管理，应该用适当的方式把这些PCB组织起来。

2.3 进程的特征

  • 动态性：进程最基本的特征，进程是程序的一次执行过程，是动态地产生、变化和消亡的
  • 并发性：内存中有多个进程实体，各进程可并发执行
  • 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
  • 异步性：各进程按各自独立的、不可预知的速度向前推进。异步性会导致并发程序执行结果的不确定性
  • 结构性：每个进程都会配置一个PCB，从结构上看，进程由程序段、数据段和PCB组成

2.4 进程的状态

单核处理机环境下，每一时刻最多只有一个进程处于运行态。如果是双核，则最多两个，以此类推。

注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态。因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求。

2.5 进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。原语采用“关中断指令”和“开中断指令”实现。

阻塞原语唤醒原语必须成对使用。

2.6 进程通信

进程通信就是指进程之间的信息交换。进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的，为了保证进程间的安全通信，操作系统提供了一些方法。

2.6.1 共享存储

两个进程对共享空间的访问必须是互斥的。

基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。

基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

2.6.2 管道通信

“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区。

  1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

  2. 各进程要互斥地访问管道。

  3. 数据以字符流的形式写入管道，当管道写满时，写进程的write() 系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read() 系统调用将被阻塞。（缓冲区的特性）

  4. 如果没写满，就不允许读。如果没读空，就不允许写。（缓冲区的特性）

  5. 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

2.6.3 消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

  • 直接消息传递：消息直接挂到接收进程的消息缓冲队列上
  • 间接消息传递：消息要先发送到中间实体(信箱)中，因此也称“信箱通信方式”。如：计网中的电子邮件系统

2.7 线程

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。可以把线程理解为“轻量级进程”。

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务。引入线程后，进程只作为除CPU之外的系统资源的分配单元。

2.7.1 线程的实现方式

用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责(包括线程切换)，用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

注意：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

2.7.2 多线程模型

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。

多对一模型：多个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行

缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多对多模型：n 用户级线程映射到m 个内核级线程（n >= m）。每个用户进程对应 m 个内核级线程。

优点：克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

2.8 处理机调度

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

2.8.1 调度的三个层次

2.8.1.1 高级调度(作业调度)

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。

高级调度（作业调度），按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

2.8.1.2 中级调度(内存调度)

引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。这么做的目的是为了提高内存利用率和系统吞吐量。

暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。

一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

2.8.1.3 低级调度(进程调度)

低级调度（进程调度），其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

2.8.2 进程的挂起态与七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）。

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

五状态模型 -> 七状态模型

注意“挂起”和“阻塞”的区别，两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

2.8.3 进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）。

进程在操作系统内核程序临界区不能进行调度与切换。（√）

进程处于临界区时不能进行处理机调度。（×）

2.8.4 进程调度的方式

  • 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

    实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。

  • 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

    可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

2.8.5 进程的切换与过程

“狭义的进程调度”与“进程切换”的区别：狭义的进程调度指的是从就绪队列中选中一个要运行的进程（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）；进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：

  1. 对原来运行进程各种数据的保存

  2. 对新的进程各种数据的恢复
    （如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

2.8.6 调度算法的评价指标

2.8.6.1 CPU利用率

CPU利用率：指CPU “忙碌”的时间占总时间的比例。

例：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？

2.8.6.2 系统吞吐量

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

例：某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？

2.8.6.3 周转时间

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

它包括四个部分：

  • 作业在外存后备队列上等待作业调度（高级调度）的时间
  • 进程在就绪队列上等待进程调度（低级调度）的时间
  • 进程在CPU上执行的时间
  • 进程等待I/O操作完成的时间

后三项在一个作业的整个处理过程中，可能发生多次。

对于用户来说，更关心自己的单个作业的周转时间：

对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值：

对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高：

平均带权周转时间：

2.8.6.4 等待时间

计算机的用户希望自己的作业尽可能少的等待处理机。

等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

2.8.6.5 响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。

响应时间：指从用户提交请求到首次产生响应所用的时间。

2.8.7 调度算法

Tips：各种调度算法的学习思路

  1. 算法思想
  2. 算法规则
  3. 这种调度算法是用于作业调度还是进程调度？
  4. 抢占式？非抢占式？
  5. 优点和缺点
  6. 是否会导致饥饿

饥饿：某进程 / 作业长期得不到服务。

2.8.7.1 FCFS(先来先服务)

算法思想：主要从“公平”的角度考虑

算法规则：按照作业 / 进程到达的先后顺序进行服务

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

是否可抢占：非抢占式的算法

优点：公平、算法实现简单

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

是否会导致饥饿：不会产生饥饿现象

例：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用FCFS调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

进程 到达时间 运行时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4

FCFS，所以调度顺序为：P1->P2->P3->P4

周转时间 = 作业完成时间 - 作业提交(到达)时间

平均周转时间 = 周转时间之和 / 作业数

带权周转时间 = 周转时间 / 作业实际运行的时间

平均带权周转时间 = 带权周转时间之和 / 作业数

等待时间 = 周转时间 - 运行时间 - I/O操作的时间(这里为0)

平均等待时间 = 总等待时间 / 作业数

2.8.7.2 SJF(短作业优先)

算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

算法规则：最短的作业 / 进程优先得到服务（所谓“最短”，是指要求服务时间最短）

用于作业 / 进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPF, Shortest Process First)算法”

是否可抢占：SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)

优点：“最短的”平均等待时间、平均周转时间

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

是否会导致饥饿：会产生饥饿现象。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

例：例题同上，使用非抢占式的短作业优先算法。

短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。所以，调度顺序为：P1->P3->P2->P4

例：例题同上，使用抢占式的短作业优先算法。

最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

需要注意的是，当有新进程到达时就绪队列就会改变，就要按照上述规则进行检查。以下表示当前进程剩余时间为m。各个时刻的情况如下：

0时刻(P1到达)：

2时刻(P2到达)：

4时刻(P3到达)：

5时刻(P3完成且P4到达)：

7时刻(P2完成)：

11时刻(P4完成)：

16时刻(P1完成)

周转时间 = 作业完成时间 - 作业提交(到达)时间：

带权周转时间 = 周转时间 / 作业实际运行的时间：

等待时间 = 周转时间 - 运行时间 - I/O操作的时间(这里为0)：

2.8.7.3 HRRN(高相应比优先)

算法思想：综合考虑作业/进程的等待时间和要求服务的时间

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

用于作业 / 进程调度：可用于作业调度，也可用于进程调度

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

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

是否会导致饥饿：不会

例：例题同上，使用高响应比优先算法。

0时刻：只有到达就绪队列，上处理机

7时刻(P1主动放弃CPU)：就绪队列中有响应比、响应比、响应比

8时刻(P3完成)：响应比、响应比

12时刻(P2完成)：就绪队列中只剩下

16时刻(P4完成)

2.8.7.4 时间片轮转调度算法(RR)

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

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

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

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

优点：公平、响应快，适用于分时操作系统

缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急程度

是否会导致饥饿：不会

例：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小分别是2、5时的进程运行情况。

时间片轮转常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间。

进程 到达时间 运行时间
P1 0 5
P2 2 4
P3 4 1
P4 5 6

时间片大小为2（注：以下括号内表示当前时刻就绪队列中的进程、进程的剩余运行时间）

0时刻(P1(5))：0时刻只有P1到达就绪队列，让P1上处理机运行一个时间片

2时刻(P2(4) -> P1(3))：2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。此时P2排在队头，因此让P2上处理机。（注意：2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列）

4时刻(P1(3) -> P3(1) -> P2(2))：4时刻P3到达，先插到就绪队尾，紧接着P2下处理机也插到队尾

5时刻(P3(1) -> P2(2) -> P4(6))：5时刻P4到达插到就绪队尾（注意：由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中）

6时刻(P3(1) -> P2(2) -> P4(6) -> P1(1))：6时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度

7时刻(P2(2) -> P4(6) -> P1(1))：虽然P3的时间片没用完，但是由于P3只需运行1各单位的时间。运行完了会主动放弃处理机，因此也会发生调度。队头进程P2上处理机

9时刻(P4(6) -> P1(1))：进程P2时间片用完，并刚好运行完，发生调度，P4上处理机

11时刻(P1(1) -> P4(4))：P4时间片用完，重新回到就绪队列。P1上处理机

12时刻(P4(4))：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机

14时刻()：就绪队列为空，因此让P4接着运行一个时间片

16时刻：所有进程运行结束

时间片大小为5

0时刻(P1(5))：只有P1到达，P1上处理机

2时刻(P2(4))：P2到达，但P1时间片尚未结束，因此暂不调度

4时刻(P2(4) -> P3(1))：P3到达，但P1时间片尚未结束，因此暂不调度

5时刻(P2(4) -> P3(1) -> P4(6))：P4到达，同时P1运行结束。发生调度，P2上处理机

9时刻(P3(1) -> P4(6))：P2运行结束，虽然时间片没用完，但是会主动放弃处理机，发生调度

10时刻(P4(6))：P3运行结束，虽然时间片没用完，但是会主动放弃处理机，发生调度

15时刻()：P4时间片用完，但就绪队列为空，因此会让P4继续执行一个时间片

16时刻：P4运行完，主动放弃处理机。所有进程运行结束

如果时间片太大，使得每个进程都可以在一个时间内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。所以时间片不能太大。

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

2.8.7.5 优先级调度算法

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

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

用于作业 / 进程调度：既可用于作业调度，也可用于进程调度。甚至还会用于I/O调度

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

优点：用优先级区别紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度

缺点：若源源不断地有高优先级进程到来，则可能会导致饥饿

是否会导致饥饿：会

例：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先级调度算法，分析进程运行情况。(注：优先数越大，优先级越高)

进程 到达时间 运行时间 优先数
P1 0 7 1
P2 2 4 2
P3 4 1 3
P4 5 4 2

非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

注：以下括号内表示当前处于就绪队列的进程

0时刻(P1)：只有P1到达，P1上处理机

7时刻(P2、P3、P4)：P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机

8时刻(P2、P4)：P3完成，P2、P4优先级相同，由于P2先到达，因此P2优先上处理机

12时刻(P4)：P2完成，就绪队列只剩P4，P4上处理机

16时刻()：P4完成，所有进程都结束

例题同上，采用抢占式的优先级调度算法。

抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是否会发生抢占。

注：以下括号内表示当前处于就绪队列的进程

0时刻(P1(7))：只有P1到达，P1上处理机

2时刻(P2(4)、P1(5))：P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机

4时刻(P3(1)、P2(2)、P1(5))：P3到达，优先级比P2更高，P2回到就绪队列，P3抢占处理机

5时刻(P2(2)、P4(4)、P1(5))：P3完成，主动释放处理机，同时P4到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机

7时刻(P4(4)、P1(5))：P2完成，就绪队列只剩P1和P4，P4上处理机

11时刻(P1(5))：P4完成，P1上处理机

16时刻()：P1完成，所有进程结束

补充：

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

  • 静态优先级：创建进程时确定，之后一直不变。
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

通常，系统进程优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好I/O型进程(或称I/O繁忙型进程)。

与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)。

2.8.7.6 多级反馈队列调度算法

算法思想：对其它调度算法的折中权衡

算法规则：

  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片

用于作业 / 进程调度：用于进程调度

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

优点：对各类进程相对公平(FCFS优点)；每个新到达的进程都可以很快就得到响应(RR优点)；短进程只用较少的时间就可完成(SPF优点)；不必实现估计进程的运行时间(避免用户作假)；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)

是否会导致饥饿：会

例：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用多级反馈队列调度算法，分析进程运行的过程。

进程 到达时间 运行时间
P1 0 8
P2 1 4
P3 5 1

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。只有第k级队列为空时，才会为k+1级队头的进程分配时间片。

2.9 进程同步与互斥

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

2.9.1 进程同步

读进程和写进程并发地执行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步”所讨论的内容。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2.9.2 进程互斥

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免地需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/O设备)。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

对临界资源的互斥访问，可以在逻辑上分为四个部分：

  • 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志(可理解为“上锁”)，以阻止其它进程同时进入临界区
  • 临界区：访问临界资源的那段代码
  • 退出区：负责解除正在访问临界资源的标志(可理解为“解锁”)
  • 剩余区：做其它处理

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

  1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
  2. 忙则等待。当已有进程进入临界区时，其它试图进入临界区的进程必须等待
  3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
  4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

2.9.2.1 进程互斥的软件实现方法

2.9.2.1.1 单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

1
int turn = 0;	//turn表示当前允许进入临界区的进程号

P0进程：

1
2
3
4
while (turn != 0);	①		//进入区
critical section;	②		//临界区
turn = 1;			③		//退出区
remainder section;	④		//剩余区

P1进程：

1
2
3
4
while(turn != 1);	⑤		//进入区
critical section;	⑥		//临界区
turn = 0;			⑦		//退出区
remainder section;	⑧		//剩余区

turn的初值为0，即刚开始只允许0号进程进入临界区，若P1先上处理机运行，则会一直卡在⑤，直到P1的时间片用完，发生调度，切换P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在⑤。

因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”。

turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按 P0 -> P1 -> P0 -> P1 -> … 这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。

因此，单标志法存在的主要问题是：违背“空闲让进”原则。

2.9.2.1.2 双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=true意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

1
2
3
bool flag[2];			//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;		//刚开始设置为两个进程都不想进入临界区

P0进程：

1
2
3
4
5
while(flag[1]);		①		
flag[0] = true;		②		
critical section;	③		
flag[0] = false;	④		
remainder section;

P1进程：

1
2
3
4
5
while(flag[0]);		⑤	//如果此时P0想进入临界区，P1就一直循环等待
flag[1] = true;		⑥	//标记为P1进程想要进入临界区
critical section;	⑦	//访问临界区
flag[1] = false;	⑧	//访问完临界区，修改标记为P1不想使用临界区
remainder section;

若按照①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区。因此，双标志位先检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

2.9.2.1.3 双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

1
2
3
bool flag[2];			//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;		//刚开始设置为两个进程都不想进入临界区

P0进程：

1
2
3
4
5
flag[0] = true;		①
while(flag[1]);		②				
critical section;	③		
flag[0] = false;	④		
remainder section;

P1进程：

1
2
3
4
5
flag[1] = true;		⑤	//标记为P1进程想要进入临界区
while(flag[0]);		⑥	//如果P0也想进入临界区，则P1循环等待
critical section;	⑦	//访问临界区
flag[1] = false;	⑧	//访问完临界区，修改标记为P1不想使用临界区
remainder section;

若按照①⑤②⑥…的顺序执行，P0和P1都将无法进入临界区。因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

2.9.2.1.4 Peterson算法

算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L·Perterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

1
2
bool flag[2];	//表示进入临界区意愿的数组，初始值都是false
int turn = 0;	//turn表示优先让哪个进程进入临界区

P0进程：

1
2
3
4
5
6
flag[0] = true;					①
turn = 1;						②
while(flag[1] && turn == 1);	③
critical section;				④
flag[0] = false;				⑤
remainder section;

P1进程：

1
2
3
4
5
6
flag[1] = true;					⑥	//表示自己想进入临界区
turn = 0;						⑦	//可以优先让对方进入临界区
while(flag[0] && turn == 0);	⑧	//对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;				⑨	
flag[1] = false;				⑩	//访问完临界区，表示自己已经不想访问临界区了
remainder section;

两种双标志法的问题都是由于进入区的几个操作不能一气呵成导致的。我们可以推理验证在Peterson算法中，两个进程进入区中的各个操作按不同的顺序穿插执行会发生什么情况：①⑥②③⑦⑧③④⑤…

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

2.9.2.2 进程互斥的硬件实现方法

2.9.2.2.1 中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)。

将临界区放在关/开中断之间，关中断后即不允许当前进程被中断，也必然不会发生进程切换，直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区。

优点：简单、高效

缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程(因为关/开中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)。

2.9.2.2.2 TestandSet指令

简称TS指令，也有地方称TestandSetLock指令，或TSL指令。

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true表示已加锁，false表示未加锁
bool TestAndSet(bool *lock){
    bool old;
    old = *lock;    //old用来存放lock，原来的值
    *lock = true;   //无论之前是否已加锁，都将lock设为true
    return old;     //返回lock原来的值
}
 
// 以下是使用 TSL 指令实现互斥的算法逻辑
while(TestAndSet(&lock)); //"上锁"并"检查"
//临界区代码段...
lock = false;       //"解锁"
//剩余区代码段...

若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则执行TSL后old返回值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比于软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否有逻辑漏洞；适用于多处理机环境。

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

2.9.2.2.3 Swap指令

有的地方也叫Exchange指令，或简称XCHG指令。

Swap指令也是用硬件实现的，执行过程不允许中断，只能一气呵成。以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Swap指令的作业是交换两个变量的值
Swap(bool *a, bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
// 以下是用Swap指令实现互斥的逻辑算法
// lock表示当前临界区是否被加锁
bool old = true;
while(old == true)
    Swap(&lock, &old);
//临界区代码段...
lock = false;
//剩余区代码段...

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

2.10 信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便地实现了进程互斥、进程同步。

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用原语实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作，因此通常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)。

2.10.1 整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整型变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作。

比如某计算机系统中有一台打印机：

1
2
3
4
5
6
7
8
9
10
11
12
int S = 1;	//初始化整型信号量S，表示当前系统中可用的打印机资源数

void wiat(int S)		//wait原语，相当于“进入区”
{
    while(S <= 0);		//如果资源数不够，就一直循环等待
    S = S - 1;			//如果资源数够，则占用一个资源
}

void signal(int S)		//signal原语，相当于“退出区”
{
    S = S + 1;			//使用完资源后，在退出区释放资源
}
1
2
3
4
5
进程P0：
...
wait(S);			//进入区，申请资源
使用打印机资源...		//临界区，访问资源
signal(S);			//退出区，释放资源

“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。

存在的问题：不满足“让权等待”原则，会发生“忙等”。

2.10.2 记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*记录型信号量的定义*/
typedef struct
{
    int value;			//剩余资源数
    struct process *L;	//等待队列
}semaphore;

/*某进程需要使用资源时，通过wait原语申请*/
void wait(semaphore S)
{
    S.value--;
    if(S.value < 0)
        block(S.L);
}
/**
如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列(即阻塞队列)中。
*/

/*进程使用完资源后，通过signal原语释放*/
void signal(semaphore S)
{
    S.value++;
    if(S.value <= 0)
        wakeup(S.L);
}
/**
释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
*/

对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--;，表示资源数减1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态 -> 阻塞态)，主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++;，表示资源数加1，若加1后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态 -> 就绪态)。

2.10.3 用信号量实现进程互斥、同步、前驱关系

2.10.3.1 实现进程互斥

  1. 分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)
  2. 设置互斥信号量mutex，初值为1
  3. 在临界区之前执行P(mutex)
  4. 在临界区之后执行V(mutex)

注意：对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现，缺少P(mutex)就不能保证临界资源的互斥访问；缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

2.10.3.2 实现进程同步

进程同步：要让各并发进程按要求有序地推进。

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
  2. 设置同步信号量S，初始为0
  3. 在“前操作”之后执行V(S)
  4. 在“后操作”之前执行P(S)

如何保证代码2在代码4之前？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore S = 0;	//初始化同步信号量，初始值为0
P1()
{
    代码1;
    代码2;
    V(S);
    代码3;
}

P2()
{
    P(S);
    代码4;
    代码5;
    代码6;
}

若先执行到V(S)操作，则S++后S=1。之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S—，S的值变回0，P2进程不会执行block原语，而是继续往下执行代码4。

若先执行到P(S)操作，由于S=0，S—后S=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行V(S)操作，S++，使S变回0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了。

2.10.3.3 实现前驱关系

进程P1中有句代码S1，P2中有句代码S2，…，P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：

2.10.4 生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中去除一个产品并使用。(注：这里的“产品”理解为某种数据)

生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。

如何用信号量机制(P、V操作)实现生产者、消费者进程的这些功能呢？信号量机制可实现互斥、同步、对一类系统资源的申请和释放。

互斥：设置初值为1的互斥信号量

同步：设置初值为0的同步信号量(实现“一前一后”)

对一类系统资源的申请和释放：设置一个信号量，初始值即为资源的数量(本质上也属于“同步问题”，若无空闲资源，则申请资源的进程需要等待别的进程释放资源后才能继续往下执行)

PV操作题目分析步骤：

  1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

  2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

    生产者每次要消耗(P)一个空闲缓冲区，并生产(V)一个产品；消费者每次要消耗(P)一个产品，并释放一个空闲缓冲区(V)。往缓冲区放入/取走产品需要互斥。

  3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

1
2
3
semaphore mutex = 1;		//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;		//同步信号量，表示空闲缓冲区的数量
semaphore full = 0;			//同步信号量，表示产品的数量，也即非空缓冲区的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
producer()
{
    while(1)
    {
        生产一个产品;
        P(empty);		//消耗一个空闲缓冲区
        P(mutex);		//实现互斥是在同一进程中进行一对PV操作
        把产品放入缓冲区;
        V(mutex);
        V(full);		//增加一个产品
        				//V(full)和下面的P(full)实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V
    }
}

consumer()
{
    while(1)
    {
        P(full);		//消耗一个产品(非空缓冲区)
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);		//增加一个空闲缓冲区
        使用产品;
    }
}

如果将生产者进程和消费者进程里面的两个P互换位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
producer()
{
    while(1)
    {
        生产一个产品;		
        P(mutex);		①
        P(empty);		②
        把产品放入缓冲区;
        V(mutex);
        V(full);		
    }
}

consumer()
{
    while(1)
    {	
        P(mutex);		③
        P(full);		④
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);		
        使用产品;
    }
}

若此时缓冲区内已经放满产品，也就是empty = 0，full = n。则生产者进程执行①使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。

同样的，若缓冲区中没有产品，即full = 0，empty = n。按③④①的顺序执行也会发生死锁。因此，实现互斥的P操作一定要在实现同步的P操作之后。

2.10.5 多类生产者-多类消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

  1. 关系分析。

    互斥关系：对缓冲区(盘子)的访问要互斥地进行

    同步关系(一前一后)：

    • 父亲将苹果放入盘子后，女儿才能取苹果
    • 母亲将橘子放入盘子后，儿子才能取橘子
    • 只有盘子为空时，父亲或母亲才能放入水果(“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果)

  2. 整理思路。

    互斥：在临界区前后分别PV

    同步：前V后P

  3. 设置信号量。

    1
    2
    3
    4
    semaphore mutex = 1;	//实现互斥访问盘子
    semaphore apple = 0;	//盘子中有几个苹果
    semaphore orange = 0;	//盘子中有几个橘子
    semaphore plate = 1;	//盘子中还可以放多少个水果

原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

但加上总没错，设置互斥信号量就对了。

2.10.6 吸烟者问题

假设一个系统有三个吸烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上，这个过程一直重复(让三个抽烟者轮流抽烟)。

本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”。

  1. 关系分析。

    互斥：桌子可以抽象为容量为1的缓冲区，要互斥访问

    • 组合一：纸+胶水
    • 组合二：烟草+胶水
    • 组合三：烟草+纸

    同步：

    • 桌上有组合一 -> 第一个抽烟者取走东西
    • 桌上有组合二 -> 第二个抽烟者取走东西
    • 桌上有组合三 -> 第三个抽烟者取走东西
    • 发出完成信号 -> 供应者将下一个组合放到桌上

  2. 整理思路。

    互斥：在临界区前后分别PV

    同步：前V后P

  3. 设置信号量。

    1
    2
    3
    4
    5
    semaphore offer1 = 0;		//桌上组合一的数量
    semaphore offer2 = 0;		//桌上组合二的数量
    semaphore offer3 = 0;		//桌上组合三的数量
    semaphore finish = 0;		//抽烟是否完成
    int i = 0;					//用于实现“三个抽烟者轮流抽烟”

2.10.7 读者-写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其它进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其它读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

两类进程：写进程、读进程

互斥关系：写进程-写进程，写进程-读进程。读进程与读进程不存在互斥问题

写者进程和任何进程都互斥，设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作。读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw执行P、V操作。如果所有读者进程在访问共享文件之前都执行P(rw)操作，那么会导致各个读进程之间也无法同时访问文件。Key：读者写者问题的核心思想——怎么处理该问题？

P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。

2.10.8 哲学家进餐问题

一张圆桌上坐着5名哲学家，每2个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

  1. 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
  2. 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
  3. 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。
1
2
3
4
5
6
7
8
9
10
11
12
13
semaphore chopstick[5] = {1,1,1,1,1};
Pi()
{
    while(1)
    {
        P(chopstick[i]);		//拿左
        P(chopstick[(i+1)%5]);	//拿右
        吃饭...
        V(chopstick[i]);		//放左
        V(chopstick[(i+1)%5]);	//放右
        思考...
    }
}

以上当5个进程并发执行，每个哲学家同时拿起自己左边的筷子，在拿起右边的筷子的时候会发生阻塞，因为每个右边的筷子都被邻居占据了，每个哲学家都等待邻居放下筷子，造成“死锁”。

如何防止死锁的发生呢？

①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两支筷子的。

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一支筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一支的情况。

③各个哲学家拿筷子这件事必须互斥地执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;		//互斥地取筷子
Pi()						//i号哲学家的进程
{
    while(1)
    {
        P(mutex);
        P(chopstick[i]);		//拿左
        P(chopstick[(i+1)%5]);	//拿右
        V(mutex);
        吃饭...
        V(chopstick[i]);		//放左
        V(chopstick[(i+1)%5]);	//放右
        思考...
    }
}

2.11 管程

信号量机制存在的问题：编写程序困难、易出错，由此引入“管程”成分——一种高级同步机制。

管程是一种特殊的软件模块，由这些部分组成：

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

管程的基本特征：

  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程

2.11.1 用管程解决生产者消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
monitor ProducerConsumer
    condition full, empty;		//条件变量用来实现同步(排队)
								//管程中设置条件变量和等待/唤醒操作，以解决同步问题
    int count = 0;				//缓冲区中的产品数
    void insert(Item item){		//把产品item放入缓冲区
        						//由编译器负责实现各进程互斥地进入管程中的过程
        if(count == N)
            wait(full);
        count++;
        insert_item(item);
        if(count == 1)
            signal(empty);
    }
    Item remove(){				//从缓冲区中取出一个产品
        if(count == 0)
            wait(empty);
        count--;
        if(count == N-1)
            signal(full);
        return remove_item();
    }
end monitor;

//生产者进程
producer(){
    while(1){
        item = 生产一个产品;
        ProducerConsumer.insert(item);
    }
}

//消费者进程
consumer(){
    while(1){
        item = ProducerConsumer.remove();
        消费产品item;
    }
}

每次仅允许一个进程在管程内执行某个内部过程。

引入管程的目的无非就是要更方便地实现进程互斥和同步。

  1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
  2. 需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
  3. 只有通过这些特定的“入口”才能访问共享数据
  4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心)
  5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”)；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒

程序员可以用某种特殊的语法定义一个管程(比如：monitor ProducerConsumer…end monitor;)，之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。

2.11.2 Java中类似于管程的机制

Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

1
2
3
4
5
6
7
8
9
10
11
static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    
    /**
    每次只能有一个线程进入insert函数，如果多个线程同时调用insert函数，则后来者需要排队等待
    */
    public synchronized void insert(Item item){
        ......
    }
}

2.12 死锁

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先(SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。

  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)
  • 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
  • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

什么时候会发生死锁？

  • 对系统资源的竞争。各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的
  • 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁
  • 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁(可以把互斥信号量、同步信号量也看作是一种抽象的系统资源)

2.12.1 死锁的处理策略——预防死锁

我们知道，死锁的产生必须是满足四个必要条件，只要其中一个或几个条件不满足，死锁就不会发生。

2.12.1.1 破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备。

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

2.12.1.2 破坏不剥夺条件

不可剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放。

破坏不剥夺条件：

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二：当某个进程需要的资源被其它进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)。

该策略的缺点：

  1. 实现起来比较复杂
  2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU
  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量
  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的哪些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿

2.12.1.3 破坏请求和保持条件

请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会在请求别的任何资源了。

该策略实现起来简单，但也有明显的缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

2.12.1.4 破坏循环等待条件

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源)一次申请完。

原理分析：一个进程只有已占有小编号资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点：

  1. 不方便增加新的设备，因为可能需要重新分配所有编号
  2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
  3. 必须按规定次序申请资源，用户编程麻烦

2.12.2 死锁的处理策略——避免死锁(银行家算法)

安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不到任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利地执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待，这也是“银行家算法”的核心思想。

2.12.3 检测和解除

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：

  1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
  2. 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来

2.12.3.1 死锁的检测

为了能对系统是否已发生了死锁进行检测，必须：

①用某种数据结构来保存资源的请求和分配信息；

②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

2.12.3.2 死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。

补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。

解除死锁的主要方法有：

  1. 资源剥夺法。挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其它的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
  2. 撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁的进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑
  3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点

如何决定牺牲哪个进程？

  1. 进程优先级
  2. 已执行多长时间
  3. 还要多久能完成
  4. 进程已经使用了多少资源
  5. 进程是交互式的还是批处理式的

3. 内存管理

3.1 基础知识

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么，如何区分各个程序的数据是放在什么地方的呢？给内存的存储单元编地址。

内存地址从0开始，每个地址对应一个存储单元。如果计算机“按字节编址”，则每个存储单元大小为1字节，即1B，即8个二进制位；如果字长为16位的计算机“按字编址”，则每个存储单元大小为1个字，每个字的大小为16个二进制位。

装入的三种方式(用三种不同的方法完成逻辑地址到物理地址的转换)：

  1. 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。绝对装入只适用于单道程序环境。
  2. 静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址(地址变换是在装入时一次完成的)。静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
  3. 动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。采用动态重定位时允许程序在内存中发生移动，并且可将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

链接的三种方式：

  1. 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行文件(装入模块)，之后不再拆开。
  2. 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
  3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

3.2 内存管理

操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么呢？

  1. 操作系统负责内存空间的分配与回收
  2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
  3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
  4. 操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行，互不干扰

内存保护可采取两种方法：

  1. 在CPU设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
  2. 采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

3.3 内存空间的扩充

3.3.1 覆盖技术

早期的计算机内存很小，比如IBM推出的第一台PC机最大只支持1MB大小的内存。因此经常会出现内存大小不够的情况。后来人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题。

覆盖技术的思想：将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)，不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。(按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区)

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担。

3.3.2 交换技术

交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)。

中级调度(内存调度)，就是要决定将哪个处于挂起状态的进程重新调入内存。(看2.8.1)

暂时换出外存等待的进程状态为挂起状态，挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。(看2.8.2)

3.3.3 连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

3.3.3.1 单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护。

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上，就是“内部碎片”。

3.3.3.2 固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

固定分区分配又分为分区大小相等和分区大小不相等：

  • 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合(比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)。
  • 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如：划分多个小分区、适量中等分区、少量大分区)。

操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)。

3.3.3.3 动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的。

思考：

  1. 系统要用什么样的数据结构记录内存的使用情况？
  2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
  3. 如何进行分区的分配与回收操作？

动态分区分配没有内部碎片，但是有外部碎片。

内部碎片：分配给某进程的内存区域中，有些部分没有用上。

外部碎片：内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑(拼凑)技术来解决外部碎片。

3.3.4 动态分区分配算法

3.3.4.1 首次适应算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

3.3.4.2 最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

3.3.4.3 最坏适应算法

又称最大适应算法。

算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

3.3.4.4 临近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)。

临近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)。

综合来看，四种算法中，首次适应算法的效果反而更好。

3.3.5 非连续分配管理方式

支持多道程序的两种连续分配方式：

  1. 固定分区分配：缺乏灵活性，会产生大量的内部碎片，内存利用率很低
  2. 动态分区分配：会产生很多外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”的时间代价很高

如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”。基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

3.3.5.1 基本分页存储管理

基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换？模块在内存中的“起始地址” + 目标内存单元相对于起始位置的“偏移量”。

结论：如果每个页面大小为B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。

因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量。

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

3.3.5.1.1 基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起始地址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

基本地址变换机构需要两次访问内存，第一次访问内存是查页表，第二次访问内存是访问目标内存单元。

3.3.5.1.2 具有快表的地址变换机构

是基本地址变换机构的改进版本。

局部性原理：

  • 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
  • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢？

快表，又称联想寄存器(TLB)，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

3.3.5.1.3 两级页表

单级页表存在的问题：①页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框；②没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问几个特定的页面。

解决问题一：

解决问题二：

3.3.5.2 基本分段存储管理

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址。

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

3.3.5.3 分段、分页管理的对比

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段存储中也可以引入快表机制。

3.3.5.4 段页式存储管理

3.3.5.4.1 分页、分段的优缺点
优点 缺点
分页管理 内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片 不方便按照逻辑模块实现信息的共享和保护
分段管理 很方便按照逻辑模块实现信息的共享和保护 如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片
3.3.5.4.2 段页式管理

3.3.6 虚拟内存

局部性原理：(看3.3.5.1.2)

高速缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。快表机构就是将近期常访问的页表项副本放到更高速的联想寄存器中。

虚拟内存有以下三个主要特征：

  • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
  • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
  • 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

3.3.6.1 请求分页管理方式

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。

一条指令在执行期间，可能产生多次缺页中断。(如：copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

3.3.6.2 页面置换算法

3.3.6.2.1 最佳置换算法(OPT)

最佳置换算法可以保证最低的缺页率，但实际上只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

3.3.6.2.2 先进先出置换算法(FIFO)
3.3.6.2.3 最近最久未使用置换算法(LRU)
3.3.6.2.4 时钟置换算法(CLOCK)

3.3.6.3 页面分配策略

抖动(颠簸)现象：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)。

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率。为了研究应该为每个进程分配多少个物理块，Denning提出了进程“工作集”的概念。

4. 文件

文件：一组有意义的信息/数据集合。

4.1 文件的属性

文件名：由创建文件的用于决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。

标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。

类型：指明文件的类型。

位置：文件的存放路径(让用户使用)、在外存中的地址(操作系统使用，对用户不可见)。

大小：指明文件的大小。

保护信息：对文件进行保护的访问控制信息。

还有打开文件(open系统调用)和关闭文件(close系统调用)。读/写文件之前，需要“打开文件”，读/写文件结束之后，需要“关闭文件”。

可用几个基本操作完成更复杂的操作，比如：“复制文件”，先创建一个新的空文件，再把源文件读入内存，再将内存中的数据写到新文件中。

4.2 文件的逻辑结构

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。

根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类：顺序文件、索引文件、索引顺序文件。

4.2.1 顺序文件

4.2.2 索引文件

4.2.3 索引顺序文件

4.3 文件目录

目录文件中的一条记录就是一个“文件控制块(FCB)”，FCB的有序集合称为“文件目录”。FCB中包含了文件的基本信息(文件名、物理地址、逻辑结构、物理结构等)，存取控制信息(是否可读/可写、禁止访问的用户名单等)，使用信息(如文件的建立时间、修改时间等)。FCB实现了文件名和文件之间的映射，使用户(用户程序)可以实现“按名存取”。所以最重要、最基本的还是文件名、文件存放的物理地址。

4.3.1 对目录的操作

搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项。

创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项。

删除文件：当删除一个文件时，需要在目录中删除相应的目录项。

显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性。

修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如：文件重命名)。

4.3.2 单级目录结构

4.3.3 两级目录结构

4.3.4 多级目录结构

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

4.3.5 无环图目录结构

4.3.6 FCB的改进

当找到文件名对应的目录项时，才需要将索引节点调入内存，索引节点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引节点称为“磁盘索引节点”，当索引节点放入内存后称为“内存索引节点”。相比之下，内存索引节点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

4.4 文件的物理结构(文件分配方式)

4.4.1 连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论：连续分配的文件在顺序读/写时速度最快。

优点：支持顺序访问和直接访问(即随机访问)；连续分配的文件在顺序访问时速度最快。

缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片。

4.4.2 链式分配

链式分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

4.4.2.1 隐式链接

隐式链接：除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高。

缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

4.4.2.2 显式链接

显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT File Allocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点：文件分配表需要占用一定的存储空间。

4.4.3 索引分配

如何实现文件的逻辑块号到物理块号的转换？

用户给出要访问的逻辑块号i操作系统找到该文件对应的目录项(FCB)。从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知道i号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块，并增加一个索引表项即可)，但是索引表需要占用一定的存储空间。

若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放1KB/4B=256个索引项。如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？

方法一：链接方案

方法二：多层索引

方法三：混合索引

4.5 文件存储空间管理

4.5.1 空闲表法

4.5.2 空闲链表法

4.5.3 位示图法

如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。

如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”。

位示图法连续分配、离散分配都适用。

4.5.4 成组链接法

4.6 文件的基本操作

4.6.1 创建文件

进行create系统调用时，需要提供的几个主要参数：

  1. 所需的外存空间大小(如：一个盘块，即1KB)
  2. 文件存放路径(“D:\Demo”)
  3. 文件名(默认为“新建文本文档.txt”)

操作系统在处理create系统调用时，主要做了两件事：

  1. 在外存中找到文件所需的空间(结合4.5，找到空闲空间)
  2. 根据文件存放路径的信息找到该目录对应的目录文件(“D:\Demo”)，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息

4.6.2 删除文件

进行delete系统调用时，需要提供的几个主要参数：

  1. 文件存放路径(“D:\Demo”)
  2. 文件名(“test.txt”)

操作系统在处理delete系统调用时，主要做了几件事：

  1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
  2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理)
  3. 从目录表中删除文件对应的目录项

4.6.3 打开文件

在很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用“打开文件”，需要提供的几个主要参数：

  1. 文件存放路径(“D:\Demo”)
  2. 文件名(“test.txt”)
  3. 要对文件的操作类型(如：r只读；rw读写等)

操作系统在处理open系统调用时，主要做了几件事：

  1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有特定的操作权限
  2. 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件

4.6.4 关闭文件

4.6.5 读文件

4.6.6 写文件

4.7 文件共享

4.7.1 基于索引节点的共享方式(硬链接)

4.7.2 基于符号链的共享方式(软链接)

由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问比硬链接速度慢。

4.8 文件保护

4.8.1 口令保护

4.8.2 加密保护

4.8.3 访问控制

4.9 文件系统的层次结构

4.10 磁盘的结构

磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。磁盘的盘面被划分成一个个磁道。一个磁道又被划分成一个个扇区，每个扇区就是一个“磁盘块”，各个扇区存放的数据量相同(如1KB)。

最内侧磁道上的扇区面积最小，因此数据密度最大。

盘片可以更换的称为可换盘磁盘；不可更换的称为固定盘磁盘。

4.11 磁盘调度算法

磁盘调度算法是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做的。其中寻道是磁盘较为耗时的部分，因此如果请求顺序得当，可以节省一些不必要的寻道时间。

4.11.1 先来先服务算法(FCFS)

4.11.2 最短寻找时间优先(SSTF)

4.11.3 扫描算法(SCAN)

4.11.4 LOOK调度算法

4.11.5 循环扫描算法(C-SCAN)

4.11.6 C-LOOK调度算法

4.12 减少磁盘延迟时间的方法

4.12.1 交替编号

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

4.12.2 错位命名

4.12.3 磁盘地址结构的设计

4.13 磁盘的管理

5. I/O

5.1 I/O设备基本概念

I/O就是输入/输出。I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

Write操作：向外部设备写出数据。

Read操作：从外部设备读入数据。

人机交互类外设：鼠标、键盘、打印机等——用于人机交互

存储设备：移动硬盘、光盘等——用于数据存储

网络通信设备：调制解调器等——用于网络通信

5.2 I/O控制器

I/O设备的机械部件主要用来执行具体的I/O操作。如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

值得注意的小细节：

  1. 一个I/O控制器可能会对应多个设备
  2. 数据寄存器、控制寄存器、状态寄存器可能有多个(如：每个控制/状态寄存器对应一个具体的设备)，且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址

5.3 I/O控制方式

5.3.1 程序直接控制方式

5.3.2 中断驱动方式

5.3.3 DMA方式

5.3.4 通道控制方式

5.4 I/O软件层次结构

5.4.1 用户层软件

假脱机技术(SPOOLing技术)在用户层软件实现。

5.4.2 设备独立性软件

设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。

主要实现的功能：

  1. 向上层提供统一的调用接口(如read/write系统调用)
  2. 设备的保护(原理类似于文件保护)
  3. 差错处理
  4. 设备的分配与回收
  5. 数据缓冲区管理，可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异
  6. 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序

设备独立性软件需要通过“逻辑设备表(LUT，Logical Unit Table)”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序。

操作系统可以采用两种方式管理逻辑设备表：

第一种方式，整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。

第二种方式，为每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中。

5.4.3 设备驱动程序

5.4.4 中断处理程序

I/O核心子系统提供的功能：I/O调度、设备保护、设备分配与回收、缓冲区管理(即缓冲与高速缓存)。

5.4.5 硬件

执行I/O操作，由机械部件、电子部件组成。(看5.2)

5.5 假脱机技术

脱机——脱离主机的控制进行的输入/输出操作。

独占式设备——只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。

共享设备——允许多个进程“同时”使用的设备(宏观上同时使用，微观上可能是交替使用)。可以同时满足多个进程的使用请求。

打印机是种“独占式设备”，但是可以用SPOOLing技术改造成“共享设备”。

独占式设备的例子：若进程1正在使用打印机，则进程2请求使用打印机时必然阻塞等待。

5.6 设备的分配与回收

虚拟设备——采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用(如采用SPOOLing技术实现的共享打印机)

从进程运行的安全性上考虑，设备分配有两种方式：

  • 安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒

    一个时段内每个进程只能使用一个设备

    优点：破坏了“请求和保持”条件，不会死锁

    缺点：对于一个进程来说，CPU和I/O设备只能串行工作

  • 不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞

    一个进程可以同时使用多个设备

    优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进

    缺点：有可能发生死锁(死锁避免、死锁的检测和解除)

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了“请求和保持”条件，不会发生死锁。

动态分配：进程运行过程中动态申请设备资源。

5.6.1 设备分配管理中的数据结构

5.6.2 设备分配的步骤

  1. 根据进程请求的物理设备名找到SDT(注：物理设备名是进程请求分配设备时提供的参数)
  2. 根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程
  3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
  4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送。

缺点：

①用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程；

②若换了一个物理设备，则程序无法运行；

③若改进请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待。

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。

  1. 根据进程请求的逻辑设备名找到SDT(注：用户编程时提供的逻辑设备名其实就是“设备类型”)
  2. 查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项
  3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
  4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

逻辑设备表(LUT)建立了逻辑设备名与物理设备名之间的映射关系。如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是那个物理设备了，并且也能知道该设备的驱动程序入口地址。

逻辑设备表的设置问题：

整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统。

每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统。

5.7 缓冲区管理

5.7.1 单缓冲

5.7.2 双缓冲

结论：采用双缓冲策略，处理一个数据块的平均耗时为。

5.7.3 单/双缓冲区的区别

5.7.4 循环缓冲区

5.7.5 缓冲池