⇧
❮
❯
↻
🍀计算机基础🍀 12342字 62分钟

计算机基础综合速成（3）：操作系统

作者

操作系统（Operating System）相关内容。本篇是计组的延续，请在完成相关内容学习后继续阅读。

相关阅读：计算机公共基础知识（2）：操作系统

Hyplus目录

1 操作系统概述

特征：并发、共享、虚拟、异步（其中并发和共享最基本）

发展：批处理操作系统 → 分时操作系统 → 实时操作系统 → 网络和分布式操作系统

体系结构：大内核、微内核

1.1 操作系统的目标和功能

什么是操作系统？

  1. 操作系统是计算机资源的管理者：
    1. 处理机管理：进程控制、进程同步、进程通信、死锁处理、处理机调度。
    2. 存储器管理：提高内存利用率，内存的分配与回收、地址映射、内存保护与共享、内存扩充。
    3. 文件管理：计算机中的信息都是以文件的形式存在的。
    4. 设备管理：完成用户的I/O请求，方便用户使用设备，提高设备的利用率。
  2. 操作系统为用户提供使用计算机硬件系统的接口：
    1. 命令接口：用户通过控制台或终端输入操作命令，向系统提供各种服务要求。
    2. 程序接口：由系统调用组成，用户在程序中使用这些系统调用来请求操作系统为其提供服务。
    3. 图形接口：最常见的为图形用户界面（GUI）（最终仍是通过调用程序接口实现）
  3. 操作系统用作扩充机器
    • 没有任何软件支持的计算机称为裸机，实际呈现在用户面前的计算机系统是经过若干层软件改造的计算机。
    • 操作系统将裸机改造成功能更强、使用更方便的机器，常将覆盖了软件的机器称为扩充机器或虚拟机。

1.2 操作系统的运行机制

在计算机系统中，CPU通常执行两种不同性质的程序：操作系统内核程序（具体实现上位于核心态/管态）和用户自编程序或系统外层的应用程序（具体实现上位于用户态/目态）。内核程序是应用程序的“管理者”，可以执行一些特权指令（如I/O指令、置中断指令、存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等指令），而“被管理程序“出于安全考虑不能执行这些指令。

层次式结构：操作系统的各项功能分别设置在不同的层次上。一些与硬件关联较紧密的模块，诸如时钟管理、中断管理、设备驱动等处于最底层。其次是运行频率较高的程序，诸如进程管理、存储管理和设备管理等。上述这两部分内容构成了操作系统的内核，其指令操作位于核心态。

内核是计算机上配置的底层软件，是计算机功能的延伸，包括以下4个方面的内容：

  1. 时钟管理：时钟的第一功能是计时，操作系统需要通过时钟管理，向用户提供标准的系统时间。其次，通过时钟中断的管理，可以实现进程切换。在分时操作系统中，采用时间片轮转调度的实现；在实时系统中，按截至时间控制运行的实现。在批处理系统中，还可通过时钟管理来衡量一个作业的运行程度等。
  2. 中断机制：引入中断技术的初衷是提高多道程序运行环境中CPU的利用率，主要针对外部设备。之后逐步得到发展，形成了多种类型，成为操作系统各项操作的基础。例如键盘或鼠标信息的输入、进程的管理和调度、系统功能的调用、设备驱动、文件访问等，都依赖于中断机制。可以说，现代操作系统是靠中断驱动的软件。中断机制中，只有一小部分功能属于内核，负责保护和恢复中断现场的信息，转移控制权到相关的处理程序。这样可以减少中断的处理时间，提高系统的并行处理能力。
  3. 原语：操作系统底层的一些可被调用的公用小程序，其各自完成一个规定的操作。原语的特点如下：
    • 这些程序处于操作系统的最底层，是最接近硬件的部分。
    • 这些程序的运行具有原子性，其操作只能一气呵成。
      • 定义原语的直接方法是关闭中断，让其所有动作不可分割地进行完再打开中断。
    • 这些程序的运行时间都较短，而且调用频繁。
  4. 系统控制的数据结构及处理：系统中用于登记状态信息的数据结构很多，例如作业控制块、进程控制块、设备控制块、各类链表等。为了实现有效的管理，系统有如下三种常见的基本操作：
    1. 进程管理：进程状态管理、进程调度和分配、创建和撤销进程控制块等。
    2. 存储器管理：存储器的空间分配和回收、内存信息保护程序、代码对换程序等。
    3. 设备管理：缓冲区管理、设备分配和回收等。

1.3 中断和异常

中断（Interruption，外中断）指来自CPU执行指令以外的事件的发生，如设备发出的I/O结束中断、时钟中断等。这一类中断通常是与当前执行的指令无关的事件。

异常（Exception，内中断，例外，陷入）指源自CPU执行指令内部的事件，如程序的非法操作码、地址越界、算术溢出、缺页异常等。对异常的处理一般要依赖与当前程序的运行现场，不能被屏蔽。

中断的引入是为了支持CPU和设备之间的并行操作，异常的引入是为了表示CPU执行指令本身时出现的问题。

中断和异常的联系与区别：

  • 中断
    • 内中断
      • 自愿中断：指令中断
      • 强迫中断：硬件故障、软件中断
    • 外中断（强迫中断）：外设请求、人为干预

不同计算机的中断处理过程各具特色，大多数情况下，中断执行的一般流程如下：

  1. 关中断：CPU响应中断后，首先要保护程序的现场状态，在保护现场的过程中，CPU不应响应更高级中断源的中断请求。否则，若现场保存不完整，在中断服务程序结束后，也就不能正确地恢复并继续执行现行程序。
  2. 保存断点：为保证中断服务程序执行完毕后能正确地返回到原来的程序，必须将原来的程序的断点（即程序计数器PC）保存起来。
  3. 引出中断服务程序：其实质是取出中断服务程序的入口地址送入程序计数器PC。
  4. 保存现场和屏蔽字：进入中断服务程序后，首先要保存现场，现场信息一般是指程序状态字寄存器PSWR和某些通用寄存器的内容。
  5. 开中断：允许更高级中断请求得到响应。
  6. 执行中断服务程序：这是中断请求的目的。
  7. 关中断：保证在恢复现场和屏蔽字时不被中断。
  8. 恢复现场和屏蔽字：将现场和屏蔽字恢复到原来的状态。
  9. 开中断、中断返回：中断服务程序的最后一条指令通常是一条中断返回指令，使其返回到原程序的断点处，以便继续执行原程序。

以上是多重中断的流程，其中1〜3步由硬件（中断隐指令）完成，4〜9步由中断服务程序完成。

1.4 系统调用

计算机系统的各种硬件资源是有限的，为了更好地管理这些资源，进程不允许被直接操作，所有对这些资源的访问都必须由操作系统控制。即操作系统是使用这些资源的唯一入口，而该入口就是操作系统提供的系统调用。一般情况下系统调用都是通过中断实现（例如Linux系统的中断号0x80）。

系统调用是用户态进程与硬件设备进行交互的一组接口，优点如下：

  1. 把用户从底层的硬件编程中解放了出来。
  2. 极大地提高了系统的安全性，使用户程序具有可移植性；用户程序与具体硬件已经被抽象接口所替代。

系统调用流程图如下：

系统调用流程图

1.5 大内核和微内核

大内核结构将操作系统功能作为一个紧密结合的整体放到内核。由于各模块共享信息，因此性能较高。

由于操作系统不断复杂，因此需要将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。

在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

微内核示意图如下：

微内核示意图

2 进程管理

在多道程序环境下，允许多个进程并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。为此引入了进程的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。

进程是程序的运行过程，是系统进行资源分配和调度的一个独立单位。

在早期操作系统中能拥有资源和独立运行的基本单位是进程，然而随着计算机技术的发展，进程出现了很多弊端，一是由于进程是资源拥有者，创建、撤消与切换存在较大的时空开销，因此需要引入轻型进程；二是由于对称多处理机（SMP）出现，可以满足多个运行单位，而多个进程并行开销过大。

线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，每条线程执行不同的任务。

2.1 进程与线程

进程（Process）与线程（Thread）的区别：

  1. 进程是系统进行资源分配调度的基本单位，线程是CPU调度分派的基本单位。
  2. 线程依赖于进程而存在，一个进程至少有一个线程。
  3. 每个进程有独立的地址空间，线程共享所属进程的地址空间。
  4. 进程是拥有系统资源的一个独立单位，而线程本身几乎不拥有系统资源，只拥有一些在运行中必不可少的资源（如程序计数器、一组寄存器和栈），和其他线程共享本进程的相关资源（如内存、I/O、CPU等）。
  5. 进程切换涉及到整个当前进程CPU环境的保存环境的设置以及新被调度运行的CPU环境的设置，而线程切换只需保存和设置少量的寄存器内容，不涉及存储器管理方面的操作。可见，进程切换的开销远大于线程切换。
  6. 线程之间的通信更方便，同一进程下的线程共享全局变量等数据，而进程之间的通信需要以进程间通信（IPC）的方式进行。
  7. 多线程程序只要有一个线程崩溃，整个程序就崩溃；但多进程程序中一个进程崩溃不会对其他进程造成影响，因为每个进程有独立的地址空间。因此多进程程序更健壮。

进程和程序的区别：

  1. 程序是永存的；进程是暂时的，是程序在数据集上的一次执行，有创建有撤销，存在是暂时的。
  2. 程序是静态的观念，进程是动态的观念。
  3. 进程具有并发性，而程序没有；
  4. 进程是竞争计算机资源的基本单位，程序不是。
  5. 进程和程序不是一一对应的：一个程序可对应多个进程，即多个进程可执行同一程序；一个进程可以执行一个或几个程序。

2.2 进程的通信方式

进程常用的通信方式：

  1. 共享内存：两个进程同时共享一块内存，这块内存上的数据可以共同修改和读取，由此达到通信的目的。
  2. 无名管道：一种半双工的通信方式，只能在具有亲缘关系（父子关系、兄弟关系等）的进程之间使用。具有亲缘关系的进程在创建时同时拥有一个无名管道的句柄，可以进行读写；无名管道不存在磁盘节点，只存在于内存中，用完即销毁。
  3. 命名管道：亦是一种半双工的通信方式，可以在不具有亲缘关系的进程间通信。命名管道存在磁盘节点，有对应的FIFO文件，凡是可以访问该路径的文件的进程均可以进行通信。
  4. 消息队列：元素为消息的链表，存放于内核中，并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  5. 套接字：网络编程的API，可以实现不同的机器间的进程通信，常用于客户端进程和服务器进程的通信。
  6. 信号：Unix系统中使用的最古老的进程间通信方法之一。操作系统通过信号来通知进程系统中发生了某种预先规定的事件（一组事件中的一个）。信号也是用户进程之间通信和同步的一种原始机制。一个键盘中断或错误条件（例如进程试图访问其虚拟内存中不存在的位置等）都有可能产生一个信号。Shell也使用信号向其子进程发送作业控制信号。

2.3 进行的状态转换

进程的特征：动态性、并发性、独立性、异步性、结构性

进程的状态：运行、就绪、阻塞、创建、结束

进程的控制：创建、终止、阻塞和唤醒、切换

进程的组织：进程控制块（PCB）、程序段、数据段

进程状态

2.4 处理机调度

三级调度：作业调度、中级调度、进程调度

调度方式：剥夺式、非剥夺式

调度准则：CPU利用率、吞吐量、周转时间、等待时间、响应时间

常见的进程调度算法：

  1. 先来先服务（First-Come First-Served，FCFS）：按照请求的顺序进行调度。
    • 非抢占式，开销小，无饥饿问题，响应时间不确定（可能很慢）；对短进程、I/O密集型进程不利。
  2. 最短作业优先（Shortest Job First，SJF）：按估计运行时间最短的顺序进行调度。
    • 非抢占式，吞吐量高，开销可能较大，可能导致饥饿问题；为短进程提供良好的响应时间，对长进程不利。
  3. 优先级调度算法：为每个进程分配一个优先级进行调度。
    • 抢占式。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
  4. 时间片轮转：将所有就绪进程按FCFS的原则排成就绪队列，用完时间片的进程排到队列最后。
    • 抢占式（时间片用完时），开销少，无饥饿问题，为短进程提供良好的响应时间；
    • 若时间片小，进程切换频繁，吞吐量低；若时间片太长，实时性得不到保证。
  5. 最高响应比优先：响应比 = 1 + 等待时间 / 处理时间。同时考虑了等待时间和估计需要的执行时间，平衡了长短进程。
    • 非抢占式，吞吐量高，开销可能较大，提供良好的响应时间，无饥饿问题。
  6. 多级反馈队列调度算法：设置多个就绪队列，优先级递减，时间片递增。只有等到优先级更高的队列为空时才会调度当前队列中的进程。若某进程用完了当前队列的时间片还未被执行完，则被移至下一队列。
    • 抢占式（时间片用完时），开销可能较大，对I/O密集型进程有利，可能会出现饥饿问题。

2.5 进程同步

同步：多个进程因为合作而使得进程的执行有一定的先后顺序。例如某个进程需要另一个进程提供的消息，在获得消息之前进入阻塞态。

互斥：多个进程在同一时刻只有一个进程能进入临界区。

同步机制的4个准则：

  1. 空闲让进：当无进程处于临界区，可允许一个请求进入临界区的进程立即进入自己的临界区。
  2. 忙则等待：当已有进程进入自己的临界区，所有企图进入临界区的进程必须等待。
  3. 有限等待：对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区。
  4. 让权等待：若进程不能进入自己的临界区，则应释放处理机。

进程同步机制的意义：进程经常会和其他进程共享一些资源（内存、数据库等），当多个进程同时读写同一份共享资源时，可能会发生冲突。因此需要进程同步来协调多个进程按顺序访问资源。

相关概念：

  • 互斥量（Mutex）：内核对象，值为0或1，只有拥有互斥对象的线程才有权限访问互斥资源。因为互斥对象只有一个，所以可保证互斥资源不会被多个线程同时访问；当前拥有互斥对象的线程处理完任务后必须将互斥对象交出，以便其他线程访问该资源。
  • 信号量（Semaphore）：内核对象，允许同一时刻多个线程访问同一资源，但需要控制同一时刻访问此资源的最大线程数量。信号量对象保存了最大资源计数和当前可用资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就减1；只要当前可用资源计数大于0，就可以发出信号量信号；若为0，则将线程放入一个队列中等待。线程处理完共享资源后，应在离开的同时通过ReleaseSemaphore函数将当前可用资源数加1。若信号量的取值只能为0或1则成为互斥量。
  • 事件（Event）：允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。事件分为手动重置事件和自动重置事件。手动重置事件被设置为激发状态后，会唤醒所有等待的线程，且一直保持为激发状态，直至程序重新将其设置为未激发状态。自动重置事件被设置为激发状态后，会唤醒一个等待中的线程，然后自动恢复为未激发状态。
  • 临界区（Critical Section）：即代码中访问资源的部分，任意时刻只允许一个线程对临界资源进行访问。拥有临界区对象的线程可以访问该临界资源，其他试图访问该资源的线程将被挂起，直至临界区对象被释放。

2.6 死锁

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

死锁原因：

  1. 系统资源不足（对不可剥夺资源的竞争）
  2. 进程推进顺序不当（P1拥有A申请B，P2拥有B申请A）

产生死锁的必要条件：

  1. 互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。
  2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但又不释放自己持有的资源。
  3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  4. 环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链。

处理死锁的基本方法：

  1. 预防死锁：这是一种较简单和直观的事先预防方法。通过设置某些限制条件，破坏产生死锁的必要条件中的一个或几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用，但由于所施加的限制条件往往过于严格，可能降低系统资源利用率和系统吞吐量。
  2. 避免死锁：该方法同样属于事先预防策略，但它无需事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁。
  3. 检测死锁：这种方法无需事先采取任何限制性措施，也不必检查系统是否已进入不安全区。该方法允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，清除系统中即刻发生的死锁。
  4. 解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常见的实施方法为撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给正处于阻塞状态的进程，使之转为就绪状态，以继续运行。

死锁定理：若资源分配图可以被完全简化（能消去所有的边），则没有死锁。

2.7 饥饿

饥饿（Starvation）：指当等待时间给进程推进和响应带来明显影响称为进程饥饿。饥饿并不代表系统已经死锁，但至少有一个程序的执行被无限期推迟。

饥饿和死锁的区别：

  1. 进入饥饿的进程可以只有一个，但死锁必须大于等于两个。
  2. 出于饥饿状态的进程可以是就绪进程，但死锁状态的进程必定是阻塞进程。

2.8 银行家算法

主要思想：避免系统进入不安全状态。

算法流程：在每次进行资源分配时，首先检查系统是否有足够的资源满足要求，若足够，则先试行分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。

由此可以保证系统始终处于安全状态，从而避免死锁现象的发生。

3 内存管理

扩充内存：覆盖与变换

基本分页等内容另见计组篇

3.1 存储器管理的功能

存储器管理（Memory Management）是操作系统的职能之一，主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能：

  1. 内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。
  2. 地址变换：提供地址变换功能，将逻辑地址转换成物理地址。
  3. 扩充内存：借助于虚拟存储技术活其他自动覆盖技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。
  4. 存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。

3.2 程序执行过程

将用户程序变为可在内存中执行的程序的步骤：

  1. 编译：由编译程序将用户源代码编译成若干目标模块。
  2. 链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。程序的连接方式有如下几种——
    1. 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，之后不再拆开。
    2. 装入时动态链接：将程序编译后所得到的一组目标模块在装入内存时边装入边链接。
    3. 运行时动态链接：仅在程序运行过程中需要一些模块时，才对这些模块进行链接。
  3. 装入：由装入程序将装入模块装入内存中运行。程序的装入方式有如下几种——
    1. 绝对装入：在编译时就已知程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。
    2. 可重定位装入（静态重定位）：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变。在操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上该起始地址即可得物理地址。
    3. 动态运行装入（动态重定位）：允许程序运行时在内存中移动位置，把装入模块装入内存后的所有地址都是相对地址。在程序执行过程中，每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现依靠硬件地址变换机构。

程序执行过程

3.3 覆盖和交换技术

两种内存扩充技术：

  • 覆盖技术：要求开发人员把一个较大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位；把程序执行时无需同时装入内存的覆盖组成一组，称为覆盖段；将该覆盖段分配到一个存储区域，该存储区域称为覆盖区，每个覆盖区与覆盖段一一对应。覆盖段的大小由其中最大的覆盖来确定。
    • 覆盖技术一定程度上可以解決内存容量太小的问题，打破了必须将一个程序的全部信息装入内存后才能运行的限制。
  • 交换技术：把暂时不用的某程序或其数据部分从内存转移到外存，以腾出必要的内存空间；或把指定程序或数据从外存读到相应的内存中并给予控制权，让其在系统上运行。
    • 处理器的中级调度采用了交换技术。

高级调度：作业调度
中级调度：内存调度
低级调度：进程调度

（调度越低级，频率越高）

覆盖和交换技术的区别：

  1. 与覆盖技术相比，交换技术不要求开发人员提供程序段之间的覆盖结构。
  2. 交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行。
  3. 覆盖技术只能覆盖于相互之间没有调用关系（无关）的程序段之间，交换技术由换出和换入两个过程组成。

3.3 连续分配管理

四种常见的内存连续分配管理方式：

  1. 单一连续分配：内存在该方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区以外的内存空间。该方式无需进行内存保护。
    • 优点：简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持。
    • 缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。
  2. 固定分区分配：最简单的一种多道程序存储管理方式。将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业；当有空闲分区时，便可再从外存的后备作业队列中，选择适当大小的作业装入该分区，如此循环。划分分区时有两种不同的方法——
    1. 分区大小相等：仅适合用一台计算机控制多个相同对象的场合，缺乏灵活性。
    2. 分区大小不等：划分为含有多个较小分区、适量的中等分区及少量的大分区。
  3. 动态分区分配（可变分区分配）：一种动态划分内存的分区方法。该方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

动态分区分配算法：在进程装入或换入主存时，若内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，此时可考虑以下几种算法——

  1. 首次适应（First Fit）算法：空闲分区以地址递增的次序链接。分配内存时顺序查找大小满足要求的第一个空闲分区。
  2. 最佳适应（Best Fit）算法：空闲分区按容量递增形成分区链，寻找第一个满足要求的空闲分区。
  3. 最坏适应（Worst Fit，又称最大适应，Largest Fit）算法：空闲分区以容量递减的次序链接，寻找第一个满足要求的空闲分区，即挑选出最大的分区。
  4. 邻近适应（Next Fit，又称循环首次适应）算法：由首次适应算法演变而来，不同之处在于分配内存时从上次查找结束的位置开始继续查找。

3.4 非连续分配管理

页式存储管理：

  • 页面、地址结构、页表
  • 地址变换机构及变换过程
  • 快表

段式存储管理：段表、地址变换机构、段的共享与保护

段页式存储管理：段表、页表

（详见计组篇）

3.5 页面置换算法

虚拟内存技术基于局部性原理实现，特征为多次性、对换性、虚拟性。

常见的页面置换算法如下：

  1. 最佳（OPT）置换算法：从主存中移出永远不再需要的页面，若无这样的页面存在，则选择最长时间不需要访问的页面。被淘汰页面是今后永不使用或最长时间内不再访问的页面，由此可以保证获得最低的缺页率。（“往后看”）
  2. 先进先出（FIFO）置换算法：最简单的页面置换算法。当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰（优先淘汰最早进入内存的页面），即先进入主存的页面先淘汰，理由是最早调入主存的页面不再被使用的可能性最大。（“往前看”）
  3. 最近最久未使用（Least Recently Used，LRU）算法：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。该算法认为过去一段时间内不曾被访问过的页面，在最近的将来可能也不会再被访问。故当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰（淘汰最近最长时间未访问过的页面）。（“往前看”）
  4. 时钟（CLOCK）置换算法
    • 背景：LRU算法的性能接近于OPT，但是实现较为困难，且开销大；FIFO算法实现简单，但性能差。故操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这些算法都是CLOCK算法的变体。
    • 简单的CLOCK算法为给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，其使用位也置1。对于页替换算法，用于替换的候选帧集合视为一个循环缓冲区，并且有一个与之相关联的指针。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区查找使用位为0的一帧，每当遇到一个使用位为1的帧时，就将该位重新置0；若在该过程开始时缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；若所有帧的使用位均为1，则指针在缓冲区中完整循环一周，将所有使用位都置0，最终会停留在初始位置上，替换该帧中的页。由于该算法循环检查各页面的情况，故称为CLOCK算法，又称最近未用（Not Recently Used，NRU）算法。

3.6 页表和快表

辨析页表和快表：

  • 页表指出逻辑地址中的页号与所占主存块号的对应关系。页式存储管理在用动态重定位方式装入作业时，利用页表进行地址转换工作。
  • 快表（TLB）是存放在高速缓冲存储器的部分页表，起着与页表相同的作用。由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。通过同时查找快表，有时只需访问一次高速缓冲存储器和主存，由此可加速查找并提高指令执行速度。

地址翻译的过程：TLB → 页表（TLB不命中） → Cache → 主存（Cache不命中） → 外存

4 文件管理

文件的逻辑结构：

  • 无结构文件（流式文件）
  • 有结构文件（记录式文件）：顺序文件、索引文件、索引顺序文件

目录结构：

  • 组成：文件控制块（FCB）、索引结点
  • 分类：单级目录结构、两级目录结构、树形目录结构、图形目录结构

文件共享：基于索引结点（硬链接）、利用符号链实现（软链接）

文件保护：访问类型、访问控制

文件管理的实现：

  • 层次结构
  • 目录实现：线性列表、哈希表
  • 文件分配：连续分配、链接分配、索引分配（索引链接、多层索引、混合索引）
  • 文件存储空间管理：空闲表法、空闲链表法、位示图法、成组链接法

磁盘访问时间：寻道时间、延迟时间、传输时间

4.1 文件的基本操作

文件属于抽象数据类型。为了恰当地定义文件，需要考虑有关文件的操作。操作系统提供各种系统调用对文件进行创建、写、读、定位和截断：

  1. 创建文件：有两个必要步骤，一是在文件系统中为文件找到空间；二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能信息。
  2. 写文件：执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作，便更新写指针。
  3. 读文件：执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样地，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，故当前操作位置可作为每个进程的当前文件位置指针。读和写操作都使用同一指针，可以节省空间并降低系统复杂度。
  4. 文件重定位（文件寻址）：按某条件搜索目录，将当前文件位置设为给定值，不进行读、写文件。
  5. 删除文件：先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
  6. 截断文件：允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。

上述6个基本操作可以组合成更复杂的文件操作。例如要进行一个文件的复制，可以创建新文件、从旧文件读出并写入新文件。

4.2 磁盘调度算法

常用的磁盘调度算法：

  1. 先来先服务算法 （First Come First Service，FCFS）：一种比较简单的磁盘调度算法，根据进程请求访问磁盘的先后次序进行调度。该算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。该算法由于未对寻道进行优化，在对磁盘的访问请求较多的情况下，会降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
  2. 最短寻道时间优先算法（Shortest Seek Time First，SSTF）：该算法每次选择一个进程，该进程要求访问的磁道与当前磁头所在的磁道距离最近，由此使得每次的寻道时间最短。该算法可以实现较好的吞吐量，但无法保证平均寻道时间最短。其缺点是对各用户服务请求的响应机会不是均等的，可能导致响应时间的变化幅度较大。在服务请求极多的情况下，内外边缘磁道的请求将会被无限期延迟，部分请求的响应时间将不可预期。
  3. 扫描算法（SCAN，电梯调度）：该算法不仅考虑欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的既在当前磁道外、距离又最近的磁道。如此自里向外地访问，直至再无更外的磁道需要访问才将磁臂换向，自外向里移动。此时同样也是每次选择这样的进程来调度，即其要访问的磁道在当前磁道内，从而避免了饥饿现象的出现（由于该算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法）。该算法基本克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化较大的缺点，吞吐量较大，且平均响应时间较小，但由于是摆动式地扫描，两侧磁道被访问的频率仍低干中间磁道。
  4. 循环扫描算法（CSCAN）：对扫描算法的改进。若对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端并反向运动时，落在磁头后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求的等待时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环进行扫描。

5 输入输出管理

I/O设备分类：略

I/O层次结构：用户层I/O、设备独立性软件、设备驱动层、中断处理层、硬件层

缓冲区：单缓冲、双缓冲、循环缓冲、缓冲池

设备分配：

  • 类型及其策略：独占设备（独占式使用）、共享设备（分时式共享）、虚拟设备（SPOOLing方式）
  • 数据结构：DCT、COCT、CHCT、SDT
  • 策略：静态分配、动态分配
  • 映射：逻辑设备名 → 物理设备名

另见计组篇。

5.1 I/O控制方式

四种常见的输入输出控制方式：

  1. 程序I/O方式：早期的计算机系统中没有中断系统，故由CPU和I/O设备进行通信，传输数据时CPU速度远快于I/O设备，于是CPU需要不断测试I/O设备，看其是否完成了传输。如下图所示：

程序I/O方式

  1. 中断驱动方式：当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回，继续执行原来的任务。仅当输完一个数据后，才需CPU花费极短的时间去做中断处理。

中断驱动方式

  1. DMA（Direct Memory Access）：通过在I/O设备和内存之间开启一个可以直接传输数据的通路，采用DMA控制器来控制一个数据块的传输，CPU只需在数据块的传输开始阶段设置传输所需的控制信息，并在传输结束阶段做进一步处理。

DMA

  1. I/O通道控制方式：与DMA控制方式类似，也是一种以内存为中心，实现设备与内存直接交换数据的控制方式。
    • 背景：虽然DMA方式相比中断方式已经显著减少了CPU的干预，即从以字为单位的干预减少到以数据块为单位的干预。但CPU每发出一条I/O指令只能读/写一个连续的数据块，而当需要一次读多个数据块且将它们分别传送到不同的内存区域时（反之亦然），则需由CPU分别发出多条I/O指令及进行多次中断处理才能完成。
    • 与DMA控制方式相比，通道方式所需要的CPU干预更少，而且可以做到一个通道控制多台设备，从而进一步减轻了CPU负担。
    • 通道本质上是一个简单的处理器，专门负责输入、输出控制，具有执行I/O指令的能力，并通过执行通道I/O程序来控制I/O操作。
    • 通道的指令系统比较简单，一般只有数据传送指令、设备控制指令等。

5.2 SPOOLing技术

虚拟性是OS的四大特性之一。如果说可以通过多道程序技术将一台物理CPU虚拟为多台逻辑CPU，从而允许多个用户共享一台主机，那么通过SPOOLing技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。

SPOOLing技术是对脱机输入/输出系统的模拟。相应地，SPOOLing系统必须建立在具有多道程序功能的操作系统上，并且还应有高速随机外存的支持，通常采用磁盘存储技术。

SPOOLing系统主要有以下三部分：

  1. 输入井和输出井：在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据。
  2. 输入缓冲区和输出缓冲区：为了缓和和CPU和磁盘之间速度不匹配的矛盾，在内存中开辟两个缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井；输出缓冲区用与暂存从输出井送来的数据，以后再传送给输出设备。
  3. 输入进程SPi和输入进程SPo：利用两个进程来模拟脱机I/O时的外围控制机。其中进程SPi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU需要输入数据时，直接从输入井读入内存；进程SPo模拟脱机输出时的外围控制机，将用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。

SPOOLing技术的特点：

  1. 提高了I/O速度：从对低速1/0设备进行的1O操作变为对输入井或输出井的操作，如同脱机操作一样。提高了I/O速度，缓和了CPU与低速I/O设备速度不匹配的矛盾。
  2. 将独占设备改造为共享设备：因为在SPOOLing系统中，实际并未给任何进程分配设备，仅是在输入井或输出井中为进程分配一个存储区并建立一张I/O请求表。由此便将独占设备改造为了共享设备。
  3. 实现了虚拟设备功能：多个进程同时使用一台独享设备，而对于每一进程而言，它们都认为自己独占这一逻辑上的设备，从而实现了设备的虚拟分配。

发表评论