操作系统复习笔记

发表于 更新于 分类于 阅读次数：

操作系统引论

操作系统的定义

定义一：是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。

定义二：是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户使用的程序的集合。

操作系统的作用

  1. 作为用户与计算机硬件系统之间的接口；
  2. 作为计算机系统资源的管理者；
  3. 实现对计算机资源的抽象。

操作系统的基本特征

1. 并发*

两个或多个事件在同一时间间隔内发生。

2. 共享

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

两种共享方式：

  • 互斥共享：共享的资源称为临界资源，同一时间只允许一个进程访问。需要用同步机制来实现对临界资源的访问；
  • 同时访问：微观上交替进行。

3. 虚拟

把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时分复用技术（如分时系统）、空分复用技术（如虚拟内存）。

4. 异步

多个作业的执行顺序和每个作业的执行时间是不确定的。

操作系统的主要功能

  1. 处理器管理：处理器的运行和分配，以进程为基本单位，因此也被看作进程管理。包括进程控制、进程同步、进程通信、进程调度；
  2. 存储器管理：内存分配、内存保护（不相互干扰）、地址映射（逻辑 -> 物理）、内存扩充（虚拟存储技术）；
  3. 设备管理：包括缓存管理（I/O 设备和 CPU 之间）、设备分配、设备处理；
  4. 文件管理：包括文件存储空间的管理、目录管理、文件读写管理和保护；
  5. 提供用户接口：程序接口（如 API）和用户接口（如 GUI）。

多道批处理系统

  • 每次由作业调度算法，从外存的后备队列中选择若干作业调入内存，共享 CPU 和各种资源。程序 A 因 I/O 操作暂停执行时，调度另一道程序 B 运行。
  • 根本目的：提高 CPU 的利用率，充分发挥系统部件的并行性。
  • 优点：资源利用率高；系统吞吐量大。
  • 缺点：平均周转时间长；无用户交互能力。

分时系统

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

实时系统

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

进程与线程

顺序执行与并发执行

程序顺序执行时的特征：

  1. 顺序性：严格按照程序所规定的次序执行；
  2. 封闭性：程序在封闭环境下运行，系统中所有资源的状态只有本程序才能改变；
  3. 可再现性：只要初始条件相同，无论怎样执行，其结果都相同。

程序并发执行时的特征：

  1. 间断性
  2. 非封闭性
  3. 不可再现性

进程与线程

  • 进程是资源分配的基本单位。进程控制块（Process Control Block，PCB）描述进程的基本信息和运行状态。所谓的创建进程和撤销进程，都是指对 PCB 的操作。

  • 线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程的资源和内存地址空间。

区别

  • 拥有资源：进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

  • 调度：线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换；从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。

  • 系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

  • 通信方面：进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性。而线程间可以通过直接读/写同一进程中的数据段（如全局变量）来进行通信。

进程的状态及转换

进程的三种基本状态：

  1. 就绪状态：已分配除 CPU 外的所有必要资源
  2. 执行状态：获得 CPU，程序正在执行
  3. 阻塞状态：发生某事件（I/O 请求、申请缓冲空间等）暂时无法继续执行

process-state-i

引入挂起操作

挂起：当该操作用于某个进程时，意味着此时该进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂不接受调度。与挂起操作对应的操作是激活操作。

引入原因：

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

process-state-ii

进程同步

进程同步机制的主要任务：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效共享资源和相互合作，从而使程序执行具有可再现性。

两种形式的制约关系：间接相互制约关系（通过共享系统资源）、直接相互制约关系（源于相互合作）

临界资源：一段时间内仅允许一个进程使用的资源。

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

同步机制规则：空闲让进、忙则等待、有限等待、让权等待。

经典的进程同步问题：生产者-消费者问题、读者-写者问题、哲学家进餐问题（暂略，详见课本 p60）

信号量机制

信号量（Semaphore）是一个整型变量，可以对其执行P、V 原语操作：

  • P：如果信号量大于 0，执行 -1 操作；如果信号量等于 0，进程阻塞，等待信号量大于 0；
  • V：对信号量执行 +1 操作，唤醒阻塞的进程让其完成 P 操作。

原语操作意指不可分割，通常做法是执行这些操作时屏蔽中断。

如果信号量的取值只能为 0 或 1，那么即是互斥量（Mutex）。0 表示临界区已经加锁，1 表示临界区解锁。

发展过程：整型信号量 -> 记录型信号量 -> AND 型信号量 -> 信号量集

  • 整型信号量：P 申请，V 释放；
  • 记录型信号量：增加一个等待队列；
  • AND 型信号量：AND 同步机制将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后一起释放（要么全部分配，要么一个都不分配）；
  • 信号量集：对 AND 型信号量集进行扩充，允许一次申请多个资源，而且在分配之前，测试某资源的数量是否大于临界值。

信号量的应用：

  1. 实现进程互斥；
  2. 实现前趋关系。

进程通信

进程同步与进程通信的区别

  • 进程同步：控制多个进程按一定顺序执行；
  • 进程通信：进程间信息交换。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

信号量也属于进程通信的一种方式，但是属于低级进程通信，因为它传输的信息非常小。

进程通信方式

高级通信机制可归为以下四大类：

1. 共享存储器系统

又可分为以下两种类型：

  1. 基于共享数据结构的通信方式：仅适用于传递相对少量的数据，通信效率低下，属于低级通信；
  2. 基于共享存储区的通信方式：高级通信。
2. 管道通信系统

管道（pipe）：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件。写进程以字符流形式将大量数据送入管道，而读进程从管道中接收数据。管道机制必须提供互斥、同步和确定对方是否存在的协调能力。

3. 消息传递系统

在该机制中，以格式化的消息为单位，将通信的数据封装到消息中，并利用操作系统提供的一组通信命令（原语），在进程间进行消息传递。

优点：隐藏通信细节，使通信过程对用户透明化，降低了通信程序设计的复杂性和错误率。

该机制是多处理机系统、分布式系统和计算机网络领域最主要的通信工具。根据实现方式不同，可进一步分为直接通信方式（直接将消息发送给目标进程）和间接通信方式（通过共享中间实体[称为邮箱]）。

4. 客户机-服务器系统

网络环境的各种应用领域中的主流通信实现机制，主要实现方法分为：

  1. 套接字（Socket）：一个通信标识类型的数据结构，是进程通信和网络通信的基本构件；
  2. 远程过程调用（RPC）：一个通信协议，允许运行于本地系统上的进程调用远程系统上的进程，而对程序员表现为常规的过程调用，无需额外为此编程。

处理机调度与死锁

作业调度

又称高级调度。主要功能是根据某种算法，从外存上后备队列中选择多个作业调入内存，为其创建进程、分配必要的资源，并插入就绪队列。

主要用于多道批处理系统中，分时系统和实时系统无作业调度。

作业：用户提交给系统的一项相对独立的工作。操作员把其通过响应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。作业控制块是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。

作业调度算法：

1. 先来先服务（FCFS）

调度最先进入就绪队列的作业。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

2. 短作业优先（SJF）

调度估计运行时间最短的作业。

长作业可能处于一直等待短作业执行完毕的状态（饥饿）。因为如果一直有短作业到来，那么长作业永远得不到调度。

3. 优先级调度算法（PSA）

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

4. 高响应比优先调度算法（HRRN）

引入动态优先级：优先级随等待时间延长而增加。

进程调度

又称低级调度。主要功能是在保存处理机的现场信息后，根据某种算法，决定就绪队列获得处理机的进程，使其进入运行状态。

多道批处理系统、分时系统和实时系统都配置进程调度。

进程调度方式

1) 非抢占方式

一旦把处理机分配给某进程，则直至该进程完成或被阻塞时，才把处理机另外分配。

2) 抢占方式

允许调度程序根据某种原则，去暂停某个正在执行的进程，并将其处理机重新分配。

抢占必须遵循的原则：

  1. 优先权原则
  2. 短进程优先原则
  3. 时间片原则

进程调度算法：

1. 轮转调度（RR）

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时分配一个 CPU 时间片给队首进程。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

轮转调度算法中，效率和时间片大小有很大关系。时间片小意味着频繁执行进程调度和进程上下文的切换，增加系统开销；时间片长则退化为 FCFS 算法，无法满足短作业和交互式用户的需求。

2. 优先级调度

把处理机分配给就绪队列中优先级最高的进程。又可以分为非抢占式和抢占式两种。

3. 多队列调度

将进程就绪队列拆分为多个，不同的就绪队列采用不同的调度算法，也可以设置不同的优先级。

4. 多级反馈队列（multileved feedback queue）

multileved-feedback-queue

  1. 设置多个就绪队列。优先级逐个降低，时间片长度依次翻倍（1，2，4，…）；
  2. 每个队列采用 FCFS 算法。若在该队列中一个时间片中未完成，则转入下一队列的末尾等待调度。在最后一个队列则按 RR 运行；
  3. 按队列优先级调度。仅当优先级更高的所有队列均空时，才会调度下一个队列中的进程运行。

实时调度

又称中级调度。主要功能是将暂时不能运行的进程调至外存等待（此时进程状态为挂起），当其具备运行条件且内存有空闲时再调入（并将状态修改为就绪）。

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

死锁概述

定义：两个或多个进程由于资源竞争而造成的僵局。若无外力作用，这些进程将永远无法向前推进。

产生死锁的原因：

  1. 竞争不可抢占性资源引起死锁；
  2. 竞争可消耗资源引起死锁；
  3. 进程推进顺序不当引起死锁：申请和释放资源的顺序不当。

产生死锁的必要条件（任一不成立则死锁不发生）：

  1. 互斥条件：进程间必须互斥使用某些资源；
  2. 请求和保持条件：进程已经占有至少一个资源，但又提出了新的资源请求；
  3. 不可抢占条件：进程已获得的资源在未使用完前不得被抢占；
  4. 循环等待条件：在发生死锁时，必然存在一个进程-资源的循环链。

处理死锁的基本方法：

  1. 预防死锁：通过设置某些限制条件，破坏死锁四个必要条件中的一个或多个；
  2. 避免死锁：在资源动态分配时，用某种方法防止系统进入不安全状态，从而避免死锁；
  3. 检测和解除死锁：允许系统产生死锁，但能及时检测并通过某些措施解除。

从上到下对死锁的防范程度依次减弱，但资源利用率和并发程度提高。

顺便一提，大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

避免死锁

安全序列：指系统能够按照某种进程顺序，为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统能够找到这样一个安全序列，则称其处于安全状态；反之则处于不安全状态。

最有代表性的避免死锁算法是 Dijkstra 的银行家算法（暂略，详见课本 p111）。

存储器管理

程序的装入和链接

用户程序要在系统中运行需要经过以下几个步骤：

  1. 编译：由编译程序（Compiler）对用户源程序进行编译，形成若干个目标模块（Object Module）；
  2. 链接：由链接程序（Linker）将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块（Load Module）；
  3. 装入：由装入程序（Loader）将装入模块装入内存。

其中，程序装入方式有以下三种：

  1. 绝对装入方式：目标模块采用绝对地址。即逻辑地址和实际内存地址完全相同，装入时不需对地址进行变换；
  2. 可重定位装入方式（静态重定位）：在装入时，由重定位装入程序一次性完成；
  3. 动态运行时装入方式：重定位推迟到程序真正执行时进行。即装入内存后的所有地址都仍是相对地址。这种方式需要硬件支持，程序可以在内存中移动（对换/紧凑），可以实现虚拟存储。

其中，重定位是将装入模块中指令和数据的相对地址调整成相应内存单元的绝对地址。

程序链接方式也有三种：

  1. 静态链接：在程序运行前将目标模块和所需库函数链接，以后不再拆开；
  2. 装入时动态链接；
  3. 运行时动态链接：可加快装入过程，节省大量内存空间。

连续分配存储管理方式

  1. 单一连续分配：内存分为系统区和用户区，用户区仅一道用户程序独占。最简单，适用于单用户、单任务 OS；
  2. 固定分区分配：系统初启时将用户区划分为若干分区，大小和分界固定且每个分区只允许装入一道作业。程序道数、程序大小受限，且有较多内部碎片；
  3. 动态分区分配：见下；
  4. 动态可重定位分区分配：见下。

动态分区分配

分区个数、大小可变。常用空闲分区表或空闲分区链来管理可用内存。

动态分区分配算法：

  1. 首次适应（FF）：将空闲分区按地址递增的次序排列，找第一个满足大小要求的空闲分区。优点是保留了高地址的大空闲区，缺点是低地址产生碎片，增加查找开销；
  2. 循环首次适应（NF）：按地址递增的次序排列，从上次找到的空闲分区的下一个空闲分区开始查找。优点是空闲分区分布更均匀，缺点是缺乏大空闲区；
  3. 最佳适应（BF）：按容量大小递增排序，找满足大小要求的最小空闲分区。缺点是产生大量碎片；
  4. 最坏适应（WF）：按容量大小递减排序，找满足大小要求的最大空闲分区。

动态可重定位分区分配

在动态分区分配方式的基础上增加紧凑功能：将内存中的所有作业进行移动，将多个分散的空闲分区拼接成一个大分区。

对换

对换指把内存中暂时不能运行的进程或暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需的程序和数据调入内存。

优点：改善内存利用率，提高处理机利用率和系统吞吐量。

类型：

  • 整体对换：以进程为单位；
  • 页面（分段）对换：以页或段为单位。

离散分配方式

离散分配方式分为以下三种：

  • 分页存储管理方式
  • 分段存储管理方式
  • 段页式存储管理方式：程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页

分页和分段的比较

  1. 页是信息的物理单位，分页是为了实现离散分配，提高内存利用率；段是信息的逻辑单位，分段是为了满足用户需求。
  2. 页大小固定且由系统决定；段长度不固定，且由用户编写的程序决定。
  3. 分页的地址空间是一维线性的；分段的地址空间是二维的。

虚拟存储器

虚拟存储器概述

  • 理论基础：局部性原理
  • 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
  • 特性：
    • 离散性：实现的前提；
    • 多次性：一个作业被分多次调入内存；
    • 对换性：允许在作业运行过程中换入、换出；
    • 虚拟性：能从逻辑上扩充内存容量。
  • 实现：分页请求系统 / 分段请求系统

请求分页存储管理方式

为了支持虚拟存储器功能，在基本分页基础上增加请求调页功能和页面置换功能。

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

请求分段存储管理方式与其在实现原理及所需硬件支持上都十分相似。

页面置换算法

1. 最佳（Optimal）

将最长时间内不再被访问的页面换出。通常可以保证获得最低的缺页率，然而是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

2. 先进先出（FIFO）

将最先进入的页面换出。

该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。

3. 最近最久未使用（LRU）

将最近最久未使用的页面换出。

可以用栈来实现该算法，栈中存储页面的页面号。当进程访问一个页面时，将该页面的页面号从栈移除，并将它压入栈顶。这样，最近被访问的页面总是在栈顶，而最近最久未使用的页面总是在栈底。

4. Clock

clock

为每个页面设置一个访问位，当该页面被访问或首次调入内存时，将访问位置为 1。

首先，将内存中的所有页面链接成一个循环队列，当缺页中断发生时，检查当前指针所指向页面的访问位，如果访问位为 0，就将该页面换出；否则将该页的访问位设置为 0，给该页面第二次的机会，移动指针继续检查。

“抖动”

  • 根本原因：同时在系统中运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求；
  • 其他原因：置换算法选择不当；全局置换使抖动传播；
  • 现象：致使每个进程在运行时，频繁出现缺页；
  • 后果：排队等待页面调入/调出的进程数目增加，处理机利用率极具下降，有效工作停滞。
  • 预防方法：
    • 采取局部置换策略：缺页时只在分配给自己的内存空间进行置换，不从其他进程获得新的物理块，以限制抖动的传播；
    • 把工作集算法融入到处理机调度中：工作集指近期进程访问页面集合；
    • 利用“L=S”准则调节缺页率：L 是缺页之间的平均时间，S 是平均缺页服务时间；
    • 挂起某些优先级低的进程。

输入输出系统

管理对象：I/O 设备、相应的设备控制器、通道。

主要任务：完成用户提出的 I/O 请求，提高 I/O 速率，以及提高设备的利用率，并能为更高层的进程方便地使用这些设备提供手段。

I/O 系统的基本功能

  1. 隐藏物理设备的细节；
  2. 与设备的无关性；
  3. 提高处理机和 I/O 设备的利用率；
  4. 对 I/O 设备进行控制；
  5. 确保对设备的正确共享；
  6. 错误处理。

其中，对 I/O 设备进行控制有四种方式：

  1. 采用轮询的可编程 I/O 方式；
  2. 采用中断的可编程 I/O 方式；
  3. 直接存储器访问方式；
  4. I/O 通道方式。

中断

中断是指 CPU 对 I/O 设备发来的终端信号的一种响应。CPU 暂停正在执行的程序，保留 CPU 环境后，自动转去执行该 I/O 设备的中断处理程序。执行完后，再回到断点，继续执行原来的程序。

中断是多道程序实现的基础，因为进程之间的切换是通过中断来完成的；中断也是设备管理的基础，为了提高处理机的利用率和实现 CPU 与 I/O 设备并行执行，必须有中断的支持。

另外，还有异常（由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等）和陷入（在用户程序中使用系统调用）。

系统调用与库函数

由 OS 向用户提供的所有内核态的功能，用户进程（应用程序）都必须通过系统调用这个中介过程来获取。C 语言首先提供了与系统调用相对应的库函数。

假脱机（SPOOLING）系统

假脱机技术是对脱机输入/输出系统的模拟，建立在通道技术和多道程序技术的基础上，以高速随机外存（通常为磁盘）为后援存储器。通过假脱机技术，可将一台物理 I/O 设备虚拟为多台逻辑 I/O 设备，以允许多个用户共享一台物理 I/O 设备。

原理：用多道程序中的两道分别模拟输入/输出时的外围控制机功能，在高速磁盘和低速 I/O 设备间传送数据。

组成：

  1. 输入井和输出井：在磁盘上开辟的两个存储区域，模拟脱机输入/输出时的磁盘；
  2. 输入缓冲区和输出缓冲区：在内存中开辟的两个缓冲区，用于缓和 CPU 和磁盘间速度不匹配的矛盾；
  3. 输入进程和输出进程：模拟脱机输入/输出时的外围控制机；
  4. 井管理程序：用于控制作业与磁盘井之间信息的交换。

特点：

  1. 提高了 I/O 的速度；
  2. 将独占设备改造为共享设备；
  3. 实现了虚拟设备功能。

缓冲区

缓冲引入的原因：

  1. 缓和 CPU 与 I/O 设备间速度不匹配的矛盾；
  2. 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制；
  3. 解决数据粒度不匹配的问题；
  4. 提高 CPU 和 I/O 设备之间的并行性。

磁盘调度算法

磁盘访问时间包括寻道时间（主要）、旋转延迟时间和传输时间。当多个进程同时请求访问磁盘时，需要进行磁盘调度来控制对磁盘的访问。磁盘调度的目标是使磁盘的平均寻道时间最少。

1. 先来先服务（FCFS）

根据进程请求访问磁盘的先后次序来进行调度。优点是公平和简单，缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先（SSTF）

要求访问的磁道与当前磁头所在磁道距离最近的优先进行调度。这种算法并不能保证平均寻道时间最短，但是比 FCFS 好很多。

会出现饥饿现象。当新进程请求访问的磁道与磁头所在磁道的距离总是比一个在等待的进程来的近，那么等待的进程会一直等待下去。

3. 扫描算法

在 SSTF 算法之上考虑了磁头的移动方向，要求所请求访问的磁道在磁头当前移动方向上才能够得到调度。因为考虑了移动方向，那么一个进程请求访问的磁道一定会得到调度。

当一个磁头自里向外移动时，移到最外侧会改变移动方向为自外向里，这种移动的规律类似于电梯的运行，因此又常称 SCAN 算法为电梯调度算法。

4. 循环扫描算法

对 SCAN 进行了改动，要求磁头始终沿着一个方向移动。

文件管理

文件

由创建者所定义的、具有文件名的一组相关元素的集合。从逻辑结构角度分为有结构文件（由若干个相关记录组成）和无结构文件（被看成一个字符流），在文件系统中是一个最大的数据单位。

文件目录

  • 文件控制块（FCB）：OS 用于描述和控制文件的一个数据结构。
  • 目录：文件控制块的有序集合。
  • 索引节点：文件描述信息单独形成的数据结构（而不包含文件名）。由于检索目录文件只用到文件名，即用不到该文件的描述信息，因此检索目录时索引节点不用调入内存，从而大大节省了系统开销。

文件共享

常用的两种文件共享方法：

  1. 基于有向无环循环图（利用索引节点）；
  2. 利用符号链。

参考资料

主要参考西安电子科技大学出版社《计算机操作系统（第四版）》。

其他参考资料：