操作系统，但是成为内核✌🏻的第一步

本文章内容完全摘自期末帮，仅作为辅助通过大学课程操作系统期末考试使用。

后续学习请关注《操作系统，但是成为内核✌🏻的第二步》，内容会根据jyy老师的课程作为主色调结合其他非面向应试的知识总结逐步润色完整。

基本概念

在计算机系统中，操作系统是处于裸机之上的第一层软件。

计算机操作系统是指控制和管理计算机软硬件资源，合理组织计算机的工作流程，方便用户使用的程序集合。

操作系统的作用主要分为：处理机管理、存储管理、设备管理、文件管理、用户接口管理。

操作系统的特点

主要有以下四个特点：并发、共享、虚拟和异步。

并发：多个事件同一时间段。

{

并发：多个事件在同一时间间隔内发生；

并行：多个事件在同一时刻发生；

}

共享：系统资源可供并发执行进程共同使用。

{

互斥共享：某个进程访问时其他进程不能访问；

同时共享：多个进程可以同时访问（不一定所有）；

}

并发和共享是操作系统的两个最基本的特征，它们互为存在的条件。

虚拟：把一个物理实体变为若干个逻辑上的对应物。

异步：进程执行顺序和执行时间的不确定性。

异步的特点：

• 进程的运行速度不可预知；
• 无论快慢，结果应当相同；
• 难以重现系统在某一时刻的状态；

所以现代操作系统的基本特征是程序的并发执行、资源共享和操作的异步性。

操作系统的分类

批处理系统

优点：

• 资源利用率高；
• 单位时间内完成的工作总量大；

缺点：

• 无交互手段，不利于调试和修改；
• 短作业的周转时间长；

分时系统

分时是指将计算机的系统资源（尤其是CPU时间）进行时间上的分割，每个时间段称为一个时间片，每个用户一次轮流使用时间片。

特点：多路性（又称同时性，多个用户同时工作）、独立性（各用户互不干扰）、及时性（系统能够及时对用户操作响应）、交互性（分时系统基本属性）。

实时系统

细分为硬实时和软实时，分别对应必须在规定的时刻或时间范围完成任务和接受偶尔违反最终时限的情况。在实时计算中，系统的正确性不仅依赖于计算的逻辑结果，还依赖于结果产生的时间。

以上三类系统的注重点

分时操作系统设计首要考虑交互性和响应时间；

批处理操作系统设计首要考虑周转时间和系统吞吐量；

实时操作系统设计首要考虑实时性和可靠性；

分布式系统

以计算机网络为基础，实现了处理和控制的分散，其基本特征是处理上的分布，即功能和任务的分布。

特点：透明性（资源共享，分布对用户来讲是不知道的）、自治性（处于系统中的多个主机处于平等低位）。

优点：处理能力增强、速度更快、可靠性增强。

进程

进程的特点：动态性、并发性、独立性、异步性、交互性。

进程 = 程序（不可缺少的组成部分）+数据（处理的对象）+PCB（进程控制块，作为进程的控制结构）。

进程控制块与进程是一一对应的，进程控制块包含了进程描述信息、进程控制信息、资源占用信息、CPU现场保护结构。

进程的五种基本状态：创建态（刚被创建）、就绪态（获得了除处理机外的所有资源）、运行态（获得处理机运行）、阻塞态（等待某一资源而暂停运行）、终止态（进入该状态以被系统回收相关资源）。

创建与撤销

创建、撤销进程以及完成进程各状态之间的转换，由具有特定功能的进程控制原语完成。

“原语” 是由若干条机器指令构成、完成一种特定功能的程序段；这段程序在执行期间不允许被分割，必须一次执行完。

进程创建的基本过程：首先从空闲的 PCB 集合中申请一个新的 PCB，同时获得该进程的内部标识；然后向该 PCB 中填写各种参数；把该进程的状态设置成就绪状态，并将该 PCB 插入到就绪队列中。

进程撤销的基本过程：

• 找到相应进程的 PCB；
• 若进程正处于执行状态，则立即停止，设置重新调度标志；
• 撤消属于该进程的所有“子孙”进程；
• 释放被撤消进程的所有资源；
• 释放进程的 PCB；
• 若调度标志为真，则进行重新调度。

阻塞与唤醒

进程阻塞的基本过程：保护中断现场；置进程的状态为“阻塞态”；将其插入该事件的阻塞队列；转进程调度。
进程唤醒的基本过程：在等待队列中找到相应进程的 PCB，将其从等待队列中移出；置其状态为就绪状态，然后把该 PCB 插入就绪队列中；等待调度程序调度。

并发控制

进程同步与互斥

进程同步与互斥

进程同步指系统中一些进程需要相互合作，共同完成一项任务。

进程互斥是由于各进程要求共享资源，而有些资源需要互斥使用，即多个进程不能同时使用同一个资源，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。进程互斥实际上是进程同步的一种特殊情况。

进程互斥与同步的区别：进程互斥是进程间共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时在归还；对进程同步而言，共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。

临界资源和临界区

系统中某些资源一次只允许一个进程使用，这样的资源为临界资源或互斥资源或共享变量。

根据对临界资源访问的作用，将代码分为四个部分：进入区、临界区、退出区、剩余区。

由于存在临界资源，因此对临界资源的访问必须进行保护，当一进程访问临界资源时其它进程应处于等待状态。

锁

用锁是实现进程互斥的一种常用方法。锁即操作系统中的一个标志位，０表示资源可用，１表示资源已被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。通常锁用 w 表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。

信号量与PV操作

信号量机制是一种解决进程的同步与互斥的工具。

信号量是一个数据结构， 它由两个变量构成: 整型变量 V、指针变量S。初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”），若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数。

信号量 S 的值只能被 P、V 操作原语进行改变。P(S)表示申请一个资源，V(S)表示释放一个资源。

操作系统对信号量只能通过初始化和两个标准的原语来访问，对信号量的操作只有三种原子操作：初始化、P操作、V操作。

P操作会使信号量的值减1（申请一个单位的资源），如果使信号量的值变成负数，则执行 P 操作的进程被阻塞。

V操作会使信号量的值加1（释放一个单位的资源），如果信号量的值不是正数， 则使一个因执行 v 操作被阻塞的进程解除阻塞。

P、V 操作必须成对出现，有一个 P 操作就一定有一个 V 操作。当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。

P、V 操作的优缺点：
优点：

• 简单，而且表达能力强（用 P、V 操作可解决任何同步互斥问题）

缺点：

• 不够安全，P、V 操作使用不当会出现死锁
• 遇到复杂同步互斥问题时实现复杂

进程间通信

进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。进程间通信主要分为低级通信和高级通信两类。

低级通讯只能传递状态和控制信息，优点为速度快，缺点为传送信息小、编程复杂。

高级通信能够传送任意数量的数据，包括共享存储区、消息系统、管道通信等。

共享存储区

共享存储区是指相互通信的进程共享某些数据结构或存储区。一组进程向该公共区中写，另一组进程从公共区中读，又可进一步分为基于共享数据结构的通信方式和基于共享存储区的通信方式。

基于共享数据结构的通信方式，进程之间能够通过某种类型的数据结构交换信息。操作系统只负责提供共享存储区，共享数据结构和对进程间的同步处理都是程序员的事。因而，通信效率低，只适合于传递少量信息。

消息系统

消息系统中进程间的信息交换以消息或报文为单位，程序员利用系统提供的一组通信原语实现通信。操作系统隐藏了通信的实现细节，简化了编程的复杂性。具体又分为直接通信方式和间接通信方式两种。

直接通信方式（消息缓冲通信），发送进程发消息时要指定接收进程的名字，反过来，接收时要知名发送进程的名字。系统系统两条原语send（receiver， message）和receive（sender， message）。

间接通信方式，又称为信箱通信。收发双方进程通过某种中间实体，作为通信进程间的媒介，即信箱( MailBox)。发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介。通常收方和发方的数目可以是任意的。这种方式广泛应用于多机系统和计算机网络中。系统提供两条原语 send(MB，Message)和 receive(MB，Message)。

管道通信

管道是一条在进程间以字节流方式传送的通信通道，它由操作系统核心的缓冲区来实现，是单向的。在使用管道前要建立相应的管道，然后才可使用。如果进程间需要双向通信，通常需要两个管道。

死锁

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

死锁的特点：

• 参与死锁的进程最少是两个；
• 参与死锁的进程至少有两个已经占有资源；
• 参与死锁的所有进程都在等待资源；
• 参与死锁的进程是当前系统中所有进程的子集。

产生死锁的原因：

• 资源不足导致的资源竞争，多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁；
• 并发执行的顺序不当。进程运行过程中，请求和释放资源的顺序不当，而导致进程死锁。例如 P，V 操作的顺序不当。

发生条件：互斥条件、占有且等待、非抢占条件、循环等待条件。

处理方法：

• 出现死锁后排除：算法检测后进行恢复
• 不允许出现死锁：
  • 预防死锁：通过限制申请资源的方法来确保至少有一个条件不成立；
  • 避免死锁：根据有关进程申请资源和使用资源的额外信息，确定对于一个申请，进程是否应该等待。

预防：

将死锁的四个必要条件记做 C1，C2，C3，C4，死锁记做 D，则有逻辑公式：D→C1^C2^C3^C4。推导可得：¬C1∨¬C2∨¬C3∨¬C4→¬D。受此启发，预防死锁的具体方法就是破坏产生死锁的四个必要条件之一，此时一定不会出现死锁。

避免：

而死锁的避免是不那么严格地限制死锁必要条件的存在，其目的是提高系统的资源利用率。万一当死锁有可能出现时，就小心避免这种情况的发生。安全状态下一定不会发生死锁；不安全状态不一定会发生死锁，只是有很大可能会发生死锁。

破坏请求和保持条件有以下两种方法：

• 要求每个进程在运行前必须一次性申请它所要求的所有资源；
• 进程提出申请资源前必须释放已占有的一切资源。

破坏请求和保持条件的优点是简单、易于实现、安全；缺点是一个进程可能被阻塞很长时间并且资源严重浪费， 进程会延迟运行。

内存管理

内存管理概述

内存管理是为了充分地利用内存，为多道程序并发执行提供存储基础；尽可能方便用户使用；解决程序空间比实际内存空间大的问题。

内存管理的功能：

• 存储空间的管理、分配和回收
• 地址重定位
• 存储共享和保护（多个进程共用内存中相同区域）
• 存储器扩充

存储方式：

• 分区存储：分区存储是将内存分为一些大小相等或不等的分区，每个应用进程占用一个或几个分区，操作系统占用其中一个分区。

  分区存储适用于多道程序系统和分时系统。但是分区存储存在的问题是，可能存在内碎片和外碎片。

  • 内碎片：占用分区之内未被利用的空间；
  • 外碎片：占用分区之间难以利用的空闲分区。

  具体的分区方式分为固定分区和动态分区：

  • 固定分区方式将内存划分为若干个固定大小的连续分区。其优点是易于实现，开销小；缺点是容易有内碎片造成浪费，且分区总数固定，限制了并发执行的程序数目。
  • 动态分区是在装入程序时按其初始要求分配，或在执行过程中通过系统调用进行分配或改变分区大小。动态分区会存在外碎片。理想状态中，可以随意分配内存的大小，不会造成内碎片，但如果大小不是任意的（存在最小划分的限制），也可能出现内碎片。

  分区分配算法用于寻找某个大于等于程序要求的空闲分区：若是大于要求，就将该分区分割成两个分区，一个分区为要求的大小并标记为“占用”，而另一个分区被标记为“空闲”。分区的先后次序通常是从内存低端到高端。

  分区释放算法用于需要将相邻的空闲分区合并成一个空闲分区。

• 分页存储：分页存储将主存分成多个固定大小的块（称为块或内存块或物理页面），作业按照主存块大小分页，连续的页存放在离散的块中。逻辑上相邻的页，物理上不一定相邻。

  页式存储解决了碎片的问题，便于管理，但增加了处理成本，占用了更多的主存空间。

  页存储将作业分配到物理离散的内存区块中，需要使用逻辑地址来记录每一页的位置，该地址的高位部分为页号，低位部分为页内地址。

  将页号和页内地址转换成内存地址，必须要有一个数据结构，用来登记页号和块的对应关系和有关信息。这样的数据结构称为页表。系统为每个进程建立一个页表，页表的长度和首地址存放在该进程的PCB中。页表需要包含页号、块号和与存储信息保护有关的其他信息。

• 虚拟存储：操作系统统一管理各级存储器，内存中只存放当前要执行的程序部分，其余的保存在外存上。

  特点：不连续、部分交换、虚拟扩充、多次对换。

请求分页存储

作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由操作系统将其从辅存调入主存，如果内存无空块，则选择一个页淘汰。分页存储管理系统根据请求装入所需页面的方法称为请求分页存储管理。

在请求分页时，选择内存中哪个物理页面被置换，就需要使用页面置换算法，其目标是把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。

局部性原理：

• 时间局部性：如果一个数据正在被访问，那么在近期它很可能还会被再次访问。
• 空间局部性：在不久的将来将用到的数据很可能与现在正在使用的数据在空间地址上是临近的。

页面置换算法：

• 先进先出页面算法（FIFO）：选择在内存中驻留时间最长的页并淘汰之；
• 最近最久未使用置换算法（LRU）：淘汰没有使用的时间最长的页；
• 最佳页面算法（OPT）：淘汰以后不再需要的或最远的将来才会用到的页面；
• 最不经常使用（LFU）：选择访问次数最少的页面淘汰之。

处理机调度

处理机调度

处理机调度的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。

处理机调度要解决的核心问题是：

• 按什么原则分配CPU（进程调度的算法）；
• 何时分配CPU（进程调度的时机）；
• 如何分配CPU（进程调度的过程）。

处理机调度的目标是提高CPU的利用率，提升吞吐量，加快响应时间。

处理机调度可以分成高级调度、中级调度和低级调度。

实时调度

实时调度的分类：

• 硬实时任务：必须满足最后期限的限制，否则产生致命的错误；
• 软实时任务：希望满足最后期限，但并不是强制的，超过期限，调度完成任务仍有意义；
• 非周期任务：有一个必须结束或开始的最后期限；
• 周期任务：期限描述为“每隔周期T一次”。

实现条件：提供必要的信息、实时系统的任务是可调度的、采用抢占式调度机制、具有快速切换机制。

实时调度算法：

• 最早截止期优先（EDF）算法：在每一个新的就绪状态，调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该任务所需的资源分配给它。在有新任务到来时，调度器必须立即计算 EDF，排出新的定序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务。如果新任务的最后期限早于被中断的当前任务，就立即处理新任务。按照 EDF 算法，被中断任务的处理将在稍后继续进行。
• 最低松弛度优先（LLF）算法：根据任务紧急（或松弛）的程度，来确定任务的优先级。松弛度=必须完成时间-其本身的运行时间-当前时间。实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。

I/O设备管理

I/O设备

I/O设备，即计算机的输入输出设备，可以按照交互对象、交互方向、程序使用等不同角度对设备进行分类。

I/O设备的特点：I/O性能经常成为系统性能的瓶颈；操作系统庞大复杂，且资源均来自I/O；与其他功能联系密切，特别是文件系统；I/O设备具有独立性（操作系统把所有外部设备统一当做文件来看待）。

I/O设备管理的目的是为了提高效率、方便使用、方便控制。

I/O设备管理的功能有：

• 提供设备使用的用户接口；
• 设备分配和释放；
• 设备的访问和控制；
• I/O缓冲和调度。

I/O系统负责低速的 I/O 设备与高速 CPU 以及存储器之间的信息交互，当需要进行数据传输时，I/O 系统有如下的控制方式：

• 程序直接控制方式：CPU需要不断查询，浪费CPU资源，CPU利用率低；
• I/O中断方式：利用效率提高，但是数据缓冲寄存器每满一次都要中断一次，如果设备较多时，中断次数会很多，使 CPU 的计算时间大大减少；
• 直接存储器（DMA）方式：DMA 可以直接与内存相连，即 I/O 设备可以直接与内存交换数据，不再需要CPU 的中转。CPU 只需要在开始的时候，指定从内存和 I/O 设备中的哪些位置进行读写，进一步增加了 CPU 的利用率。DMA 可以一次性读取多个块，但是在内存和 I/O 设备中必须是连续的，如果牵扯到读写离散的块，CPU 必须发出多个 I/O 指令。

缓冲技术缓和了CPU与I/O设备间速度不匹配的矛盾、减少对CPU的中断频率，放宽对CPU中断响应时间的限制、提高CPU和I/O设备之间的并行程度，从而用来匹配CPU 与 I/O 设备速度的差异和负荷的不均匀，进而提高处理机与外设的并行程度。

常用的缓冲方式有：单缓冲、双缓冲、环形缓冲、缓冲池。

磁盘调度

几乎所有随机存储的文件都是存放在磁盘上，磁盘I/O速度的高低将直接影响文件系统的性能。

磁盘分为两种：

• 固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高；
• 移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低。

调度算法：

• 先来先服务算法（FCFS）：按访问请求到达的先后次序服务；
• 最短寻道时间优先算法（SSTF）：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先；
• 扫描算法（电梯算法 SCAN）：设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。
• 循环扫描调度算法（C-SCAN）：总是从 0 号柱面开始向里扫描。移动臂到达最后一个柱面后，立即带动读写磁头快速返回到 0 号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描。

FCFS SSTF SCAN