## 软件设计师-第二章 操作系统

1. 操作系统概述

计算机系统由两部分组成：硬件，软件，通常把未配置软件的计算机称为裸机。

操作系统的作用： 通过资源管理提高计算机系统的效率 改善人机界面向用户提供友好的工作环境

操作系统的特征：并发性、共享性、虚拟性、不确定性

操作系统的功能：进程管理、存储管理、文件管理、设备管理、作业管理

操作系统的分类：

  • 批处理操作系统

  • 分时操作系统（轮流使用CPU工作片）

  • 实时操作系统（快速响应）

  • 网络操作系统 分布式操作系统（物理分散的计算机互联系统）

  • 微机操作系统（Windows）

  • 嵌入式操作系统

操作系统在计算机系统中的地位：

计算机启动的基本流程为：BIOS——>主引导记录——>操作系统

2. 程序与进程

程序顺序执行时的主要特征包括：顺序性、封闭性和可再现性。

程序并发执行时的主要特征包括：失去了程序的封闭性、程序和机器的执行程序的活动不再一一对应、并发程序之间的相互制约性。

3. 三态模型

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。

五态，是多了两种 状态：静止就绪和静止阻塞，需要人为的操作才会进入对应状态，活跃就绪即就绪，活跃阻塞即等待

  • 运行：当一个进程在处理机上运行时。
  • 就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行（还未得到）。
  • 阻塞（等待或睡眠）：一个进程正在等待某一事件发生而暂时停止运行，这时即使把处理机分配给进程也无法运行。
进程 CPU 资源
运行 √ √
就绪 × √
阻塞 × ×

4. 进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

4.1 同步和互斥

  • 同步：合作进程间的直接制约问题。

    进程间的同步：是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

    例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

  • 互斥：申请临界资源进程间的间接制约问题。

    进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。

    临界资源：在多道程序系统环境中，那些一次只能供一个进程使用的资源。如打印机、共享变量和表格等。

临界区管理的原则：

临界区：是进程中对临界资源实施操作的那段程序。

对互斥临界区管理的4条原则如下：

  • 有空即进：当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限 的时间。
  • 无空则等：当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
  • 有限等待：对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。
  • 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态

4.2 信号量机制

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

信号量机制主要有：

  • 整型信号量
  • 记录型信号量
  • 信号量集机制

整型信号量：

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类：

  • 公用信号量(互斥信号量)：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1
  • 私用信号量(同步信号量)：对共享资源的访问控制，初值一般是共享资源的数量

信号量 S 的物理意义：

  • S ≥ 0：表示某资源的可用数，此时有可用资源；
  • S＜0：则其绝对值表示阻塞队列中等待该资源的进程数，此时无可用资源，并且有进程被阻塞。

4.3 PV操作

PV操作：实现进程同步与互斥的常用方法。

P操作和V操作是低级通信原语，在执行期间不可分割。其中：

  • P操作（减）：表示申请一个资源；

    定义：S := S−1（S表示信号量）

    • S ≥ 0：执行P操作的进程继续执行；
    • S＜0：无可用资源，置该进程为阻塞状态，并将其插入阻塞队列。

  • V操作（加）：表示释放一个资源。

    定义：S := S+1

    • S ≥ 0：执行V操作的进程继续执行；
    • S＜0：表示释放前有程序被阻塞，从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

P减V加，P进V出。

利用PV操作实现进程的互斥：

  1. 令信号量mutex的初始值为1；
  2. 进入临界区：执行P操作；
  3. 推出临界区：执行V操作。

利用PV操作实现进程的同步：

实现进程的同步可用一个信号量与消息联系起来。

信号量的值：

  • 为0：表示希望的消息未产生；
  • 非0：表示希望的消息已经存在。

假定信号量S表示某条消息，进程可以：

  • 调用P操作：测试消息是否到达；

  • 调用V操作：通知消息已经准备好。

4.4 生产者消费者

三个信号量：

  • 互斥信号量S0(仓库独立使用权)

  • 同步信号量S1(仓库空闲个数)

  • 同步信号量S2(仓库商品个数)

4.5 死锁

死锁产生的四个必要条件：

  • 资源互斥
  • 每个进程占有资源并等待其他资源
  • 系统不能剥夺进程资源
  • 进程资源图是一个环路

当有 n 个进程，m个资源，且每个进程所需要的资源数为k，并且系统采用的分配策略是轮流地为每个进程分配资源时，判断是否发生死锁的公式如下：

m>=n∗(k−1)+1m >= n * (k-1)+1

死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

  • 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时 刻都不满足死锁的条件。
  • 死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法， 才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死 锁
  • 死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加 以解除。
  • 死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等

4.6 进程资源图

进程资源图：用来表示进程和资源之间的分配和请求关系

  • P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在图中，R1指向P1，表示R1有一个 资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行
  • 阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图 中P2
  • 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1、P3
  • 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态,不可优化

4.7 线程

线程是独立调度的最小单位，进程是拥有资源的最小单位，线程可以共享进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源，如线程的栈指针等标识数据

传统进程有两个基本属性：

  • 可拥有资源的独立单位；
  • 可独立调度和分配的基本单位。

引入线程的原因是，进程的系统必须付出较大的时空开销。引入线程后，将传统进程的两个基本属性分开：

  • 线程：作为调度和分配的基本单位；
  • 进程：作为独立分配资源的单位。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。

线程的特点：

  • 线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。
  • 线程也具有就绪、运行和阻塞3种基本状态。
  • 线程可创建另一个线程。
  • 同一个进程中的多个线程可并发执行。

线程因其具有许多传统进程所具有的特性，故称为"轻型进程"；而传统进程称为"重型进程"。

线程分为：

  • 用户级线程（User-Level Threads）：不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用来实现；
  • 内核支持线程（Kernel-Supported Threads）：依赖于内核，即无论是在用户进程中的线程，还是在系统中的线程，它们的创建、撤销和切换都利用系统调用来实现。

某些系统同时实现了两种类型的线程。

与线程不同的是，不论是系统进程还是用户进程，在进行切换时，都要依赖于内核中的进程调度。因此，不论是什么进程都是与内核有关的，是在内核支持下进行切换的。

5. 存储管理

5.1 程序局部性原理

程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也局限于某个区域内。

程序的局限性表现在以下两个方面：

  • 时间局限性：

    • 如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；
    • 如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。

    产生时间局限性的典型原因是在程序中存在着大量的循环操作。

  • 空间局限性：指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。

    即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型原因为程序是顺序执行。

5.2 分页存储管理

将进程空间分为一个个页，假设每个页大小为4K，同样的将系统的物理空间也分为一个个4K大小的物理块(页帧号)，这样，每次将需要运行的逻辑页装入物理块中，运行完再装入其他需要运行的页，就可以分批次运行完进 程，而无需将整块逻辑空间全部装入物理内存中

  • 页：将一个进程的地址空间划分成若干个大小相等的区域，称为页。
  • 块（页框）：将主存空间划分成与页相同大小的若干个物理块，称为块或页框。

在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。

分页的过程是由操作系统完成的，对用户是透明的，所以用户不必关心分页的过程，其优点是能有效地提高主存利用率，其缺点是不易实现共享。

  • 优点：利用率高、碎片小(只在最后一个页中有)、分配及管理简单

  • 缺点：增加了系统开销,可能产生抖动现象

页面置换算法

有时候，进程空间分为100个页面，而系统内存只有10个物理块，无法全部满足分配，就需要将马上要执行的页面 先分配进去，而后根据算法进行淘汰，使100个页面能够按执行顺序调入物理块中执行完

缺页表示需要执行的页不在内存物理块中，需要从外部调入内存，会增加执行时间，因此，缺页数越多，系 统效率越低

  • 最优算法：OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比 较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的

  • 先进先出算法：FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能 越多(即效率越低)

  • 最近最少使用：LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原 理，这种方式效率高，且不会产生抖动现象

快表

  • 块表是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容 并行查找，一般用来存放当前访问最频繁的少数活动页面的页号 快表是将页表存于cache中；

  • 慢表示将页表存于内存上。因此慢表需要访问两次内存才能取出页，而快表是访 问一次Cache和一次内存，因此更快

5.2 段式存储管理

将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑 整体分段的

地址表示：(段号，段内偏移)：其中段内偏移不能超过该段号对应的段长，否则越界错误，而此地址对应的真正 内存地址应该是：段号对应的基地址 + 段内偏移

  • 优点：程序逻辑完整，修改互不影响
  • 缺点：内存利用率低，内存碎片浪费大

5.3 段页式存储管理

结合分页和分段存储管理方式，形成一种新的存储管理方式，即段页式存储管理。段页式系统有两种系统的优点。对进程空间先分段，后分页

段页式系统的基本原理是：

  1. 将整个主存划分成大小相等的存储块（页框）。
  2. 将用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名。
  3. 将每个段划分成若干页，以页框为单位离散分配。

段页式地址空间的结构：

  • 优点：空间浪费小、存储共享容易、能动态连接
  • 缺点：由于管理软件的增加，复杂性和开销也增加，执行速度下降

6 设备管理

6.1 I / 0 软件层次结构：

6.2 输入输出技术

  • 程序控制（查询）方式：CPU主动查询外设是否完成数据传输，效率极低
  • 程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率相对较高。适用于键盘等 实时性较高的场景
    • 中断响应时间指的是从发出中断请求到开始进入中断处理程序
    • 中断处理时间指的是从中断处理开始到中断处理结束
    • 中断向量提供中断服务程序的入口地址
    • 多级中断嵌套，使用堆栈来保护断点和现场
  • DMA方式（直接主存存取）：CPU只需完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完 成，在主存和外设之间建立直接的数据通路，效率很高。适用于硬盘等高速设备
  • 在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束 时；区分指令执行结束和总线周期结束

6.3 缓冲技术

缓冲技术可提高外设利用率，尽可能使外设处于忙状态。缓冲技术可以采用两种方式：

  • 硬件缓冲：利用专门的硬件寄存器作为缓冲；
  • 软件缓冲：通过操作系统来管理的。

6.4 单缓冲

单缓冲工作过程图：

当第1块数据送入用户工作区后（进行数据处理），缓冲区是空闲的，可以传送第2块数据（输入）。即第1块数据的处理C1与第2块数据的输入T2是可以并行的，以此类推：

$$ （前提是c要小于T）计算公式为：（T + M）* n + c $$

单缓万能公式：n∗(max(C,T)+M)+min(C,T)n*(max(C,T)+M)+min(C,T)

6.5 双缓冲

双缓冲进一步加快I/O的速度，提高了设备的利用率。其工作基本过程是在设备输入时，先将数据输入到缓冲区1，装满后便转向缓冲2。

双缓冲工作过程图：

双缓冲的工作特点是，可以实现对缓冲中数据的输入T和提取M，与CPU的计算C，三者并行工作：

$$ （前提是M +c ＜T）计算公式为：T * n + M + c $$

双缓万能公式：n∗max(C+M,T)+min(C+M,T)n*max(C+M,T)+min(C+M,T)

6.6 磁盘调度算法

  • 先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。

    • 优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。
    • 缺点：此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

  • 最短寻道时间优先（SSTF，最短移臂算法）：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。

    • 优点：可能会出现饥饿现象。
    • 缺点：不能保证平均寻道时间最短。

  • 扫描算法（SCAN，电梯调度算法）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。

    在这种调度方法下磁头的移动类似于电梯的调度，所以它也称为电梯调度算法。

    • 优点：避免了饥饿现象的出现。
    • 缺点：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，再从外向里扫描完所有要访问的磁道后才处理该进程的请求，致使该进程的请求被严重地推迟。

  • 单向扫描算法（CSCAN，循环扫描算法）：为了减少上述SCAN缺点中存在的这种延迟，算法规定磁头只做单向移动。

    例如，只是自里向外移动，从当前位置开始沿磁头的移动方向去选择离当前磁头最近的那个柱面访问，如果沿磁头的方向无请求访问时，磁头立即返回到最里面的欲访问的柱面，再亦即将最小柱面号紧接着最大柱面号构成循环，进行循环扫描。

总结：

  1. 先来先服务（FCFS） ：根据进程请求访问磁盘的先后次序进行调度。
  2. 最短寻道时间优先(SSTF)：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
  3. 扫描算法/电梯调度算法（SCAN）：扫描算法不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
  4. 单向扫描调度算法（CSCAN）：为了减少这种延迟，算法规定磁头只做单向移动。

6.7 虚设备和SPOOLING技术

一台实际的物理设备，例如打印机，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印 机空闲，此时，极大的浪费了外设的工作效率 引入SPOOLING技术，就是在外设上建立两个数据缓冲区，分别称为输入井和输出井，这样，无论多少进程，都可 以共用这一台打印机，只需要将打印命令发出，数据就会排队存储在缓冲区中，打印机会自动按顺序打印，实现了 物理外设的共享，使得每个进程都感觉在使用一 个打印机,这就是物理设备的虚拟化。

6.8 旋转调度

公式：C+R+(A+C−R)∗(n−1)C+R+(A+C-R)*(n-1)

7 文件管理

7.1 多级索引结构

  1. 假设系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共 可存 4KBx10=40KB 数据
  2. 10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址， 假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存 1024x4KB=4098KB 数据
  3. 二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘 块，容量又扩大了一个数量级，为 1024x1024x4KB 数据

7.2 文件目录

  • 文件控制块（FCB）：用于文件的描述和控制的数据结构，实现了文件的“按名存取”。

    文件控制块至少要包括文件名和存放文件的物理地址。

    文件控制块也称为文件的说明或文件目录项（简称目录项）。

  • 文件目录：文件控制块的有序集合。

    即文件目录是由文件控制块组成的，专门用于文件的检索。

7.3 文件控制块

文件控制块中包含以下信息：

  • 基本信息类：例如文件名、文件的物理地址、文件长度和文件块数等。

  • 存取控制信息类：文件的存取权限。

    UNIX中，用户分成三类：

    • 文件主用户
    • 同组用户
    • 一般用户

    以上三类用户对文件的权限为：

    • 读
    • 写
    • 执行

  • 使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的 信息（如打开文件的进程数、在文件上的等待队列）等。

7.4 目录结构

组织好文件的目录是设计文件系统的重要环节，文件目录结构的组织方式直接影响到文件的存取速度，关系到文件的共享性和安全性。

常见的目录结构有：

  • 一级目录结构：一级目录的整个目录组织是一个线性结构，在整个系统中只需建立一张目录表，系统为每个文件分配一个目录项。

    优点：结构简单；

    缺点：查找速度慢，不允许重名和不便于实现文件共享等。

    主要用在单用户环境中。

  • 二级目录结构：为了克服一级目录结构存在的缺点引入了二级目录结构。

    二级目录结构的组成为：

    • 主文件目录（MFD）：每个用户文件目录都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针；
    • 用户目录（UFD）：由用户所有文件的目录项组成的。

    优点：提高了检索目录的速度，较好地解决了重名问题。

    缺点：该结构虽然能有效地将多个用户隔离开（这种隔离在各个用户之间完全无关时是一个优点），但当多个用户之间要相互合作去共同完成一个大任务，且一个用户又需要去访问其他用户的文件时，这种隔离便成为一个缺点，因为这种隔离使诸用户之间不便于共享文件。

  • 多级目录结构：在多道程序设计系统中常采用多级目录结构。

    多级目录结构是树型目录结构。从根结点向下，每一个结点是一个目录，叶结点是文件。

    在采用多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名：

    • 路径名：从某个目录开始到该文件的通路上所有各级目录名拼起来得到的。

      在各目录名之间、目录名与文件名之间需要用分隔符隔开。

    • 绝对路径名：指从根目录开始的完整路径。

      全文件名：指绝对路径名加上该文件的文件名。

    • 相对路径名：从当前所在目录开始到其他目录或文件的路径。

7.5 位示图

位示图是一种空闲空间管理方法。通过在外存上建立一张位示图，记录文件存储器的使用情况。

位示图用二进制的一位来表示一个物理块的使用情况：

  • 0：表示空闲；
  • 1：表示占用。

例如：

位示图的大小由磁盘空间的大小（物理块总数）决定。

位示图的描述能力强，适合各种物理结构。

公式：

  • 块号从0开始，字号从1开始，公式：

    (n−1)∗32～～～n∗32−1(n-1)*32 ～～～ n*32-1

  • 块号从0开始，字号从0开始，公式：

    n∗32～～～(n+1)∗32−1n*32 ～～～(n+1)*32-1

8 特殊的操作系统

8.1 微内核操作系统

微内核，顾名思义，就是尽可能的将内核做的很小，只将最为核心必要的东西放入内核中，其他能独立的东西都放 入用户进程中，这样，系统就被分为了用户态和内核态

8.2 嵌入式操作系统

  • 嵌入式操作系统特点：微型化、代码质量高、专业化、实时性强、可裁剪可配置
  • 实时嵌入式操作系统的内核服务：异常和中断、计时器、I / O管理
  • 常见的嵌入式RTOS(实时操作系统)：VxWorks、RT-Linux、QNX、pSOS
  • 嵌入式系统初始化过程按照自底向上、从硬件到软件的次序依次为：片级初始化——>板级初始化——>系统初 始化
  • 芯片级是微处理器的初始化，板卡级是其他硬件设备初始化，系统级初始化就是软件及操作系统初始化