操作系统

操作系统概述

定义

能有效地组织和管理系统中的各种软硬件资源，合理地组织计算机系统工作流程，控制流程的执行，并且向用户提供一个良好的工作环境和友好的接口。

三个作用

1. 管理计算机中运行的程序和分配各种软硬件资源；
2. 为用户提供友善的人机界面；
3. 为应用程序的开发和运行提供一个高效率的平台；

四个特征

1. 并发性；
2. 共享性；
3. 虚拟性；
4. 不确定性（异步性）；

操作系统的分类

批处理操作系统

批处理操作系统分为单道批处理和多道批处理。

分时操作系统

分时操作系统是将 CPU 的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。尽管各个终端商的作业是断续运行的，但是由于操作系统每次对用户程序都能做出及时响应，因此用户感觉整个系统均归一人占用。分时操作系统的四个特性，多路性、独立性、交互性和及时性。

实时操作系统

实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高，但要求可靠性有保障。

网络操作系统

网络操作系统是使联网计算机能够方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。一个典型的网络操作系统的特征包括硬件独立性和多用户支持等。

分布式操作系统

分布式操作系统是由多个分散的计算机连接而成的计算机系统，系统中的计算机无主次之分。分布式操作系统是网络操作系统的更高级形式，它保持网络系统所拥有的全部功能，同时又有透明性、可靠性和高性能等特性。

微型计算机操作系统

微型计算机系统建成微机操作系统，如 Windows、Mac OS、Linux 等。

嵌入式操作系统

嵌入式操作系统的主要特点：

1. 微型化。
2. 可定制。
3. 实时性。
4. 可靠性。
5. 易移植性。

嵌入式系统初始化过程按照自底向上、从硬件到软件的次序为：片级初始化 -> 板级初始化 -> 系统初始化。

进程管理

进程由进程控制块 PCB（唯一标志）、程序（描述程序要做什么）和数据（存放进程执行时所需要的数据）组成。

进程的三态图和五态图

进程前驱图

反应了程序之间的并行和顺序关系。

进程资源图

如上图所示，

1. 资源 R1 总共有两个，资源 R2 总共有三个，资源 R3 总共有两个（看有几个圆圈）。
2. 进程 P1 拥有 1 个 R1 和 1 个 R2（看指向 P1 的箭头），还需要申请 1 个 R2（看从 P1 出去的箭头）；进程 P2 拥有 1 个 R2 和 1 个 R3，还需要申请 1 个 R1；进程P3拥有 1 个 R1 和一个 R2，还需申请 1 个 R3）。
3. 资源 R1 还剩 0 个，R2 还剩 0 个，R3 还剩 1 个。
4. 因为 P1 需要申请 R2，R2 无剩余，所以 P1 阻塞；因为 P2 需要申请 R1，R1 无剩余，所以 P2 阻塞；因为 P3 需要申请 R3，R3 还剩一个，所以 R3 非阻塞。
5. 所以 P3 可以顺利执行，当 P3 执行完成后，释放 R1 和 R2，此时 P1 和 P2 都可以申请到需要的资源，那么 P1 和 P2 都可以正常执行完成。
6. 如果所有的进程都是阻塞状态，那么此时发生死锁。

同步与互斥

几个概念：

• 临界资源：各进程之间需要以互斥方式对其进行访问的资源；
• 临界区：指进程中对临界资源实施操作的程序。本质是一段代码；
• 互斥：某临界资源在同一时间内只能由一个任务单独使用，使用时加锁，使用后释放锁；
• 同步：多个任务本身可以并发执行，但是执行速度有差异，所以会有等待，不存在资源是否单独或者共享的问题；
• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其它进程无法进行访问，初始值为 1；
• 同步信号量：对共享的资源进行访问控制，初始值一般是共享资源的数量；

信号量

P 操作，申请资源（S=S-1），如果 S<0，说明当前进程没有资源可以获取，需要阻塞；

V 操作，释放资源（S=S+1），如果 S<0，说明当前还有|S|（S的绝对值）个进程在等待资源释放，如果 S>0，说明当前有 S 个资源处于空闲状态；

生产者消费者问题

三个信号量：互斥信号量 S0（仓库独立使用权），同步信号量 S1（仓库空闲位置个数），同步信号量 S2（仓库商品个数）

生产者流程：生产一个商品 -> P(S0) 获取仓库使用权 -> P(S1) 申请一个空闲位置 -> V(S2)仓库商品个数增加一个 -> V(S0) 释放仓库使用权

消费者流程：P(S0) 申请使用仓库 -> P(S2) 申请一个商品 -> 取出一个商品 -> V(S1) 仓库空闲出一个位置 -> V(S0) 释放仓库使用权

进程调度

进程调度方式是指当有更高优先级的进程来到时如何分配 CPU。分为可剥夺和不可剥夺两种。

可剥夺指当有更高优先级的进程来到时，强行将正在运行中的进程的 CPU 分配给高优先级的进程；不可剥夺指就算高优先级的进程来到时，也需要等待当前进程完处理后自动释放 CPU。

三级调度

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

1. 高级调度。高级调度又称长调度、作业调度或接纳调度，它决定处于输入池中的哪个后背作业可以调入主系统做好运行准备，成为一个或一组就绪进程。在系统中一个作业调度只需要经历一次高级调度。
2. 中级调度。又称中程调度或对换调度，它决定处于交换区中的哪个就绪进程可以调入内存，以便直接参与对 CPU 的竞争。
3. 低级调度。又称短程调度或进程调度，它决定处于内存中的哪个就绪进程可以调入 CPU。低级调度是操作系统中最活跃、最重要的调度程序，对系统影响很大。

调度算法

• 先来先服务 FCFS：先来的进程优先分配 CPU；
• 时间片轮转：每个进程分配相同的 CPU 时间片，用于微观调度，很公平；
• 优先级调度：每个进程都有一个优先级，优先级大的先分配 CPU。
• 多级反馈调度：按优先级分成多个队列，每个队列里的进程分配相同的 CPU 时间片，优先级高的队列里的进程分配的 CPU 时间片较长；

死锁

发生死锁的必要条件

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

打破死锁的方法

1. 死锁预防。
2. 死锁避免。
3. 死锁检测。
4. 死锁解除。

死锁资源计算

系统内有 n 个进程，每个进程都需要 R 个资源，那么发生死锁的最大资源数为n*(R-1)，不会发生死锁的最小资源数为n*(R-1)+1。

线程

进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

为什么要引入线程

进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，所以进程的数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。

引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程只拥有运行中必不可少的一些资源，如程序计数器、一组寄存器和栈，它与同属于一个进程的其它线程共享进程的全部资源。（进程之间的数据是相互隔离的，线程独享的资源也是隔离的）。

存储管理

分区存储管理

整存是将某进程所需要的内存整体分配，有三种分区方式：

固定分区

这是一种静态分区方法。将主存分为若干个固定的分区，将要运行的作业装配进去。由于分区大小固定，就可能和作业需要的大小不同，从而浪费一些空间，产生内部碎片。

可变分区

这是一种动态分区算法。主存空间的分区是在作业转入时划分的，正好划分为作业需要的大小，这样就不会产生内部碎片。但是每个分区之间可能会产生许多无法分配的空间，这就是外部碎片。

可变分区算法

如果现在有一个进程需要分配8KB的内存空间，那么有如下几种分区算法：

1. 首次适应法：按内存地址顺序查找，找到第一个大于等于 8KB 的空闲块，切割出 8KB 分配给进程；
2. 最佳适应法：先给内存空闲空间的大小从小到大排序，找到第一个大于等于 8KB 的空闲块，切割出 8KB 分配给进程；
3. 最差适应法：与最佳适应法相反，先给内存空闲空间的大小从大到小排序，找到第一个大于等于 8KB 的空闲块，切割出 8KB 分配给进程，相比于最佳适应法，可以避免产生细小的空闲块；
4. 循环首次适应法：按首次适应法分配空间，如果后续还需要分配其他进程的内存空间，不会从头开始找，而是从当前地址往后找下一个满足大小的空闲块分配，避免每次从头查找；

可重定位分区

可重定位分区是在分配好作业需要的内存区域后，如果后续有作业请求申请区域但是空间无法满足，那么会移动已分配好的区域，使外部碎片成为一个连续的区域，凑出来新的区域用来分配给新的作业。

分页存储管理

逻辑页分为页号和页内地址。

如果内存有 4GB，每页大小为 4KB，那么总共有 4GB/4KB=2^20 页，页号有 20 位。因为4KB=2^12B，所以页内地址有 12 位。

页面置换算法

1. 最优算法 OPT：理论算法，无法实现的。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
2. 先进先出算法 FIFO：先调入内存的页被置换淘汰，会产生抖动现象，即分配的页数越多，效率越低。
3. 最近最少使用 LRU：过去最少使用的页面被置换淘汰，这种方式效率高，且不会被淘汰。
4. 淘汰原则：优先淘汰最近未访问的，后淘汰最近未被修改的页面。

快表

快表是一块小容量的相联存储器，有快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容进行查询，一般来存放当前访问最频繁的少数活动页面的页号。

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

分段存储管理

将进程空间分为一个个短，每段也有段号和段内地址。每段物理大小不同，分段式根据逻辑整体分段的。段表有段长和基址两个属性，才能确定一个逻辑段在物理段中的位置。

优点：多道程序共享内存，各段程序修改互不影响；

缺点：内存利用率低，内存碎片浪费大；

段页式存储管理

设备管理

设备又称为外设，是计算机系统与外界交互的工具，具体负责计算机与外部的输入、输出工作。

在计算机系统中，负责管理设备和输入输出的机构称为 I/O 系统。I/O 系统由设备、控制器、通道、总线和 I/O 软件组成。

设备管理的任务是保证在并发环境下，当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，控制设备的各种操作，完成 I/O 设备与主存之间的数据交互。

设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理 I/O 设备的操作、提供设备使用的用户接口及设备的访问和控制。

设备分类

• 按数据组织分类：块设备、字符设备；
• 按设备功能分类：输入设备、输出设备、存储设备、网络联网设备、供电设备；
• 按资源分配角度分类：独占设备、共享设备和虚拟设备；
• 按数据传输速率分类：低速设备、中速设备、高速设备；

I/O软件

• 用户层软件：实现与用户交互的接口，用户可直接调用在用户层提供的、与 I/O 操作有关的库函数，对设备进行操作。
• 设备无关软件：负责实现与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
• 设备驱动程序：与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序。
• 中断处理程序：用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处理完后再恢复被中断进程的现场后返回到被中断进程。

文件管理

文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

逻辑结构

1. 由结构的记录式文件
2. 无结构的流式文件

物理结构

1. 连续结构
2. 链接结构
3. 索引结构
4. 多个物理块的索引表

文件目录

文件控制块

文件控制块包含以下三类信息：基本信息、存取控制类信息和使用信息类

1. 基本信息：文件名、文件的物理地址、文件长度和文件块数；
2. 存取控制类信息：文件的存取权限，像 Unix 用户分成文件拥有者、同组用户和其他用户三类，这三类的读写执行（RWX）权限；
3. 使用信息类：文件建立日期、最后一次修改日期、最后一次访问日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。

文件控制块的有序集合称为文件目录。

相对路径：从当前路径开始的路径；

绝对路径：荣根目录开始的路径；

全文件名：全文件名=绝对路径+文件名；

需要注意的是，路径是不包括文件名的。

文件存储空间管理

文件存取方式是指读写文件存储器上的一个物理块的方法，通常有顺序存取和随机存取两种方式。

空闲区表

位示图

空闲块链

成组链接法

作业管理