基础篇

操作系统的演进

无操作系统

人工操作、用户独占。资源利用率很低。

批处理系统

无需等待人工操作、批量输入任务。多道程序设计（指计算机内存中同时存放多个程序，使得批处理系统可以一次处理多个任务），资源利用率提升。

分时系统

人——机交互、多用户共享。及时调试程序，资源利用率提升。

操作系统的功能

  • 进程管理
  • 存储管理
  • 作业管理
  • 文件管理
  • 设备管理

操作系统概览

What&Why

操作系统是管理计算机硬件和软件资源的计算机程序。

管理配置内存、决定资源供需顺序、控制输入输出设备等。

操作系统提供让用户和系统交互的操作界面。

操作系统的基本功能

操作系统统一管理计算机资源：处理器资源、存储器资源、I/O设备资源、文件资源。

操作系统实现了对计算机资源的抽象，用户无需面向硬件接口编程。

操作系统提供了用户与计算机之间的接口：图形窗口形式、命令形式、系统调用形式。

操作系统相关概念

  • 并发性

    image-20230930174616814

  • 共享性：操作系统中的资源可供多个并发的程序共同使用，这种共同使用的形式称之为资源共享。资源共享分为互斥共享形式和同时访问形式。

  • 虚拟性：虚拟性表现为把一个物理实体转变为若干个逻辑实体，物理实体是真实存在的，逻辑实体是虚拟的。虚拟的技术主要有时分复用技术和空分复用技术。

  • 异步性：在多道程序环境下，运行多个进程并发执行。进程在使用资源时可能需要等待或放弃。

进程管理

为什么需要进程

进程是系统进行资源分配和调度的基本单位。

进程作为程序独立运行的载体保障程序正常执行。

进程的存在使得操作系统资源的利用率大幅提升。

进程的实体

主存中的进程形态是进程控制块（PCB），包含：标识符、状态、优先级、程序计数器、内存指针、上下文数据、I/O 状态信息等。

线程是操作系统进行运行调度的最小单位，线程包含在进程之中，是进程中实际运行工作的单位。

image-20230930192920779

五状态模型

创建、就绪、阻塞、执行、终止。

  • 创建：创建进程时拥有 PCB 但其它资源尚未就绪的状态，操作系统提供 fork 函数接口创建进程。

  • 就绪：当进程被分配到除 CPU 时间片以外所有必要资源后处于就绪状态，只要再获得 CPU 的使用权，就可以立即运行。

  • 执行：进程获得 CPU 后程序正在执行称为执行状态，在单处理机中，在某个时刻只能有一个进程是处于执行状态。

  • 阻塞：进程因某种原因（其它设备未就绪）无法继续执行从而放弃 CPU 的状态称为阻塞状态。

  • 终止：进程结束由系统清理或归还 PCB 的状态。

    image-20230930194256301

进程同步

生产者消费者问题（有限缓冲区问题）

image-20231003105627354 image-20231003105330273

哲学家就餐问题

image-20231003110002876

上述两个问题产生的原因是彼此间没有通信（即进程间没有同步）。

进程间同步原则：

  • 空闲让进：资源无占用，允许使用。
  • 忙则等待：资源有占用，请求进程等待。
  • 有限等待：保证有限等待时间能够使用资源，避免其它等待的进程僵死。
  • 让权等待：等待时，进程需要让出 CPU，也就是进程由执行状态变为阻塞状态，这也是保证 CPU 可以高效使用的前提。

进程间同步的方法：

  • 消息队列
  • 共享存储
  • 信号量
  • Unix域套接字

线程间同步的方法：

  • 互斥量
  • 读写锁
  • 自旋锁
  • 条件变量

Linux 进程

进程的类型：

  • 前台进程：具有终端，可以和用户交互的进程。
  • 后台进程：没有占用终端的进程，基本上不和用户交互，优先级比前台进程低（使用<command> &启动后台进程）。
  • 守护进程：是特殊的后台进程，很多都是随系统一起启动，直到系统关闭（systemd、crond、sshd、mysqld）。

进程的标记：

进程 ID 是进程的唯一标记，表现为一个非负整数，最大值由操作系统限定。

ID 为 0 的进程为 idle 进程，是系统创建的第一个进程。ID 为 1 的进程为 init 进程，是 0 号进程的子进程，完成系统初始化。init 进程是所有用户进程的祖先进程。

image-20231003115155957

image-20231003115220962

进程的状态（man ps）：

image-20231003115706460

作业管理

进程调度

进程调度器是操作系统的一部分，决定了何时运行什么进程。它通常能够暂停一个运行中的进程，将它放回到运行队列当中，并运行一个新进程，我们把这样的调度器叫做抢占调度器。否则，它就是协同调度器。

进程调度算法

  • 先来先服务调度算法。
  • 短进程优先调度算法：优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程。
  • 高优先权调度算法：进程附带权重，调度程序优先选择权重高的进程，紧迫的任务可以优先处理。
  • 时间片轮转调度算法：按先来先服务的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行。是相对公平的调度算法，但不能保证及时响应用户。

死锁

两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通讯而造成的一种阻塞现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。

死锁产生的原因：

  • 竞争资源
  • 进程调度顺序不当

死锁的四个必要条件：

  • 互斥条件：资源只能同时分配给一个进程，无法多个进程共享。
  • 请求保持条件：进程至少持有一个资源，又提出新的资源请求。新资源被占用，请求被阻塞，被阻塞的进程不释放自己持有的资源。
  • 不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
  • 环路等待条件：发生死锁时，必然存在“进程—资源”环形链。一系列进程互相持有其他进程所需要的资源。

死锁的处理：

  • 鸵鸟策略（即不理睬策略）
  • 预防策略：
    • 预先静态分配法。破坏了“ 不可剥夺条件”，预先分配所需资源，保证不等待资源。
    • 资源有序分配法。破坏了“ 环路条件”，把资源分类按顺序排列，保证不形成环路。
  • 避免策略：Dijkstra 提出的银行家算法。
  • 检测与解除：
    • 资源剥夺法。从一些进程那里强行剥夺足够数量的资源分配给死锁进程。
    • 撇销进程法。根据某种策略逐个地撤销死锁进程，直到解除死锁为止。

存储管理

存储器管理的对象是主存存储器简称主存或内存。存储器管理的主要功能包括主存空间的分配和回收、提高主存的利用率、扩充主存、对主存信息实现有效保护。

内存分配的过程

内存分配的方式：

  • 单一连续分配，是最简单的内存分配方式，只能在单用户、单进程的操作系统中使用。
  • 固定分区分配，支持多道程序的最简单存储分配方式，内存空间被划分为若干个固定大小的区域，每个区域只提供给一个程序使用，互不干扰。
  • 动态分区分配，按照进程实际需要，动态分配内存空间。

动态分区分配算法：

  • 首次适应算法：每当用户作业申请一个空间时，系统总是从主存的低地址开始选择一个能装入作业的空白区。当用户释放空间时，该算法更易实现相邻的空白区合并。
  • 循环首次适应算法。与首次适应算法的不同之处是，每次分配都是从刚分配的空白区开始寻找一个能满足用户要求的空白区。
  • 最佳适应算法 。 假设系统中有 n 个空白区(自由区)，每当用户申请一个空间时，将从这n个空白区中找到一个最接近用户需求的分区。这种算法能保留较大的空白区，缺点是空闲区不可能刚好等于用户要求的区，所以必然要将一个分区一分为二，但是随着系统不断地释放空问，可能会使产生的小分区小到无法再继续分配，将这样的无用小分区称为外碎片。
  • 最差适应算法。系统总是将用户作业装入最大的空白分区 。这种算法将一个最大的分区一分为二，所以剩下的空白区通常也大，不容易产生外碎片。

段页式存储管理

段页式系统的基本原理是先将整个主存划分成大小相等的存储块 (页框)，将用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名，再将每个段划分成若干页，以页框为单位离散分配。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成。

虚拟内存

作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效地利用主存空间。从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器称为虚拟存储器。虚拟存储器是为了扩大主存容量而采用的一种设计方法，其容量是由计算机的地址结构决定的。

程序局部性原理，程序的局限性表现在时间局限性和空间局限性两个方面：

  • 时间局限性是指如果程序中的某条指令 一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
  • 空间局限性是指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型原因为程序是顺序执行的。

Linux 存储管理

Buddy 内存管理算法：

内存分配原则：向上取整为 2 的幂次大小。

此算法基于计算机处理二进制的优势具有极高的效率，主要解决了内存外碎片的问题（将内存外碎片转为内存内碎片）。

Linux 交换空间：

交换空间可以是磁盘的一个分区，也可以是一个文件。用户可以在安装时或安装后的任何时候创建交换空间。

交换空间有两种用途：

  • 将虚拟内存扩大到超过已安装的物理内存（RAM）的容量；
  • 用于 suspend-to-disk 支持。

image-20231003170910411

文件管理

文件的逻辑结构

文件的逻辑结构可分为两大类：一是有结构的记录式文件，它是由一个以上的记录构成的文件，故又称为记录式文件；二是无结构的流式文件，它是由一串顺序字节流构成的文件。

有结构的记录式文件：

  • 文件内容由定长记录和可变长记录组成。
  • 定长记录存储文件格式、文件描述等结构化数据项。
  • 可变长记录存储文件具体内容。

无结构文件：

  • 文件体为字节流，不划分记录。
  • 可以把流式文件看作是记录式文件的一个特例。

文件的物理结构

  • 连续结构：也称顺序结构，它将逻辑上连续的文件信息(如记录)依次存放在连续编号的物理块上。只要知道文件的起始物理块号和文件的长度，就可以很方便地进行文件的存取。
  • 索引结构：在采用索引结构时，将逻辑上连续的文件信息(如记录)存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。

文件存储空间的管理

外存空闲空间管理的数据结构通常称为磁盘分配表(Disk Allocation Table)。常用的空闲空间的管理方法有空闲区表、位示图、空闲块链和成组链接法 4 种。

  • 空闲区表。将外存空间上的一个连续的末分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数和状态等信息，它适用于连续文件结构。
  • 位示图。这种方法是在外存上建立一张位示图 (Bitmap)，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0 和1 分别表示空闲和占用。
  • 空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)，不需要磁盘分配表，节省空间。每次申请空闲物理块只需根据链表的头指针取出第一个空闲物理块，根据第一个空闲物理块的指针可找到第二个空闲物理块，依此类推。
  • 成组链接法。UNIX系统采用该方法。例如，在实现时系统将空闲块分成若干组，每 100 个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。 假如某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。

目录结构

多级日录结构像一棵倒置的有根树，所以也称为树型目录结构。从树根向下，每一个结点是一个目录，叶结点是文件。MS-DOS 和UNIX等操作系统均采用多级目录结构。在采用多级目录结构的文件系统中，用户要访问一个文件，必领指出文件所在的路径名， 路径名是从根目录开始到该文件的通路上所有各级日录名拼起来得到的。

Linux 文件的基本操作

Linux 目录结构：

image-20231003175317226

Linux 文件类型（ls 命令展示的内容）：

  • -：普通文件
  • d：目录文件
  • l：符号链接
  • d / c：设备文件
  • s：套接字
  • p：FIFO（具名管道）

Linux系统核心可以支持十多种文件系统类型。

设备管理

广义的 I/O 设备

对 CPU 而言，对 CPU 进行数据输入的称为输入设备，对 CPU 进行数据输出的称为输出设备。

  • 按照设备的功能分类：存储设备、输入设备、输出设备。
  • 按数据组织分类：块设备(BlockDevice)、字符设备(Character Device)。
  • 按资源分配角度分类：分为独占设备、共享设备和虚拟设备。
  • 按数据传输率分类。分为低速设备、中速设各和高速设备。

Spooling 技术

Spooling 是Simultaneous Peripheral Operations On Line (外围设备联机操作)的简称。所谓 Spooling 技术，实际上是用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的一种技术，也是一种速度匹配技术。

image-20231003185551014

Spooling系统的工作过程是操作系统初启后激活Spooling 预输入程序使它处于捕获输入请求的状态， 一旦有输入请求消息，Spooling输入程序立即得到执行，把装在输入设备上的作业输入到硬盘的输入井中并填写好作业表，以便在作业执行中要求输入信息时可以随时找到它们的存放位置。当作业需要输出数据时，可以先将数据送到输出井，当输出设备空闲时，由 Spooling 输出程序把硬盘上输出井的数据送到慢速的输出设备上。