【OS】操作系统

操作系统是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。

• 0 相关概念
• 1 进程管理
  • 1.1 进程的特征
  • 1.2 进程状态
  • 1.3 进程调度算法
  • 1.4 进程同步
  • 1.5 进程通信
  • 1.6 死锁
• 2 内存管理
  • 2.1 内存连续分配管理方式
  • 2.2 内存非连续分配管理方式
    • 2.2.1 基本分页存储管理方式
    • 2.2.2 基本分段存储管理方式
    • 2.2.3 段页式管理方式
    • 2.2.5 分页与分段
  • 2.3 虚拟内存
• 3 文件管理
• 4 设备管理
  • 4.1 输入输出系统
  • 4.2 缓冲区
  • 4.3 磁盘

0 相关概念

• 并行（parallel）：指在同一时刻，有多条指令在多个处理器上同时执行。所以无论从微观还是从宏观来看，二者都是一起执行的。
• 并发（concurrency）：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

操作系统基本特征：

1. 并发
   • 并发是指宏观上在一段时间内能同时运行多个程序；
   • 并行则指同一时刻能运行多个指令。
2. 共享：系统中的资源可以被多个并发进程共同使用。
   • 互斥共享，互斥共享的资源称为临界资源
   • 同时共享
3. 虚拟：虚拟技术把一个物理实体转换为多个逻辑实体。
   • 时分复用
   • 空分复用
4. 异步：异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

由于需要限制不同的程序之间的访问能力，防止他们获取别的程序的内存数据，或者获取外围设备的数据，并发送到网络，CPU 划分出两个权限等级——用户态和内核态。

• 用户态：只能受限的访问内存，且不允许访问外围设备，占用 CPU 的能力被剥夺，CPU 资源可以被其他程序获取。
• 内核态：CPU 可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，CPU 也可以将自己从一个程序切换到另一个程序。
• 用户态切换到内核态：
  • 主动：系统调用 / 陷阱指令
  • 被动：异常、外围设备的中断

堆和栈的区别

1 进程管理

进程的定义：1）程序的一次执行；2）具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位；3）一个程序及其数据在处理机上顺序执行时所发生的活动。

1.1 进程的特征

• 动态性：进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的。
• 并发性：任何进程都可以同其他进程一起并发执行
• 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；
• 异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进
• 结构性：进程由程序段、数据段和进程控制块（PCB）三部分组成。

1.2 进程状态

1.3 进程调度算法

• 批处理系统
  • 先来先服务 first-come first-serverd（FCFS）
  • 短作业优先 shortest job first（SJF）
  • 最短剩余时间优先 shortest remaining time next（SRTN）
• 交互式系统
  • 时间片轮转
  • 优先级调度
  • 多级反馈队列

1.4 进程同步

• 临界区：对临界资源进行访问的那段代码。
• 信号量（Semaphore）：是一个整型变量，可以对其执行常见的 PV 操作。
• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定先后的执行顺序。
• 互斥：多个进程因为竞争产生的间接制约关系，在同一时刻只有一个进程能进入临界区。
• 管程：把控制的代码独立出来。数据结构 + 过程 = 管程。

规则：空闲让进、忙则等待、有限等待、让权等待

经典同步问题

• 生产者–消费者问题
• 哲学家进餐问题
• 读者–写者问题

1.5 进程通信

通信方式

1. 共享存储：在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。
2. 消息传递：通过操作系统的相应系统调用进行消息传递通讯。
   • 直接通信方式：点到点的发送
   • 间接通信方式：以信箱为媒介进行传递，可以广播
3. 管道通信：管道是一种信息流缓冲机构，基于文件系统，连接一个读进程和一个写进程以实现它们之间通信的一个共享文件。以先进先出方式组织数据传输。

1.6 死锁

产生原因

• 竞争资源
• 进程推进顺序不当

产生死锁的必要条件：

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
• 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
• 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
• 循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

处理方法：

1. 死锁检测与死锁恢复：不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
   • 死锁恢复：抢占、回滚、杀死进程
2. 死锁预防：破坏四个必要条件。
3. 死锁避免：银行家算法。

2 内存管理

2.1 内存连续分配管理方式

• 单一连续分配：无外部碎片
• 固定分区分配：无外部碎片
• 动态分区分配：无内部碎片

基于顺序搜索的动态分区分配算法

• 首次适应算法（first fit, FF）
• 循环首次适应算法（next fit, NF）
• 最佳适应算法（best fit, BF）
• 最坏适应算法（worst fit, WF）

2.2 内存非连续分配管理方式

2.2.1 基本分页存储管理方式

• 页面：将一个进程的逻辑地址空间分成若干个大小相等的片
• 页框（frame）：内存空间分成与页面相同大小的存储块
• 页表：实现从页面号到物理块号的地址映射
• 地址结构：页号 + 页内位移量

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）

1. 最佳（OPT, Optimal replacement algorithm）：一种理论上的算法
2. 最近最久未使用（LRU, Least Recently Used）
3. 最近未使用（NRU, Not Recently Used）
4. 先进先出（FIFO, First In First Out）
5. 时钟（Clock）

页面分配策略

1. 固定分配局部置换
2. 可变分配全局置换
3. 可变分配局部置换

2.2.2 基本分段存储管理方式

• 段表：段表实现了从逻辑段到物理内存区的映射
• 段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
• 地址结构：段号 + 段内偏移量

2.2.3 段页式管理方式

页式存储管理能有效地提高内存利用率，段式存储管理能反映程序的逻辑结构并有利于段的共享。段页式管理方式中，作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位。

• 地址结构：段号 + 页号 + 页内偏移量

2.2.5 分页与分段

• 段页式：程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
• 地址结构：段号（S）+ 段内页号（P）+ 页内地址（W）

2.3 虚拟内存

• 虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
• 内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
• 局部性原理：程序在执行时将呈现出局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。包括时间局部性和空间局部性。
• 技术实现
  1. 请求分页存储管理
     • 页表机制：页号 + 物理块号 + 状态位 P + 访问字段 A + 修改位 M + 外存地址
  2. 请求分段存储管理
  3. 请求段页式存储管理

3 文件管理

• 数据项：是最低级的数据组织形式。
• 记录：是一组相关数据项的集合，用于描述一个对象在某方面的属性。
• 文件：1）创建者所定义的、具有文件名的一组相关元素的集合；2）是操作系统中最大的数据单位。
• 文件控制块（FCB）：文件名 + inode（索引节点，即属性）

分类

• 无结构文件（流式文件）
• 有结构文件（记录式文件）
  • 顺序文件
  • 索引文件
  • 索引顺序文件
  • 直接文件（散列文件）

外存分配方式

• 连续分配
• 链接分配
• FAT 与 NTFS 技术
• 索引分配

存储空间管理

• 空闲表法
• 空闲链表法
• 位示图法
• 成组链接法

4 设备管理

设备并不是直接与 CPU 进行通信，而是与设备控制器通信。在设备与设备控制器之间应该有一个接口。设备控制器主要功能：控制一个或多个 I/O 设备，以实现 I/O 设备和计算机之间的数据交换。

4.1 输入输出系统

I/O 系统的基本功能

• 隐藏物理设备的细节
• 与设备的无关性
• 提高处理机和 I/O 设备的利用率
• 对 I/O 设备进行控制
• 确保对设备的正确共享
• 错误处理

I/O 软件的层次结构

1. 用户层 I/O 软件
   • 系统调用与库函数
   • 假脱机系统（Spooling）
     • 主要组成：输入/输出井、输入/输出缓冲区、输入/输出进程、井管理程序
2. 设备独立性软件：缓存管理、差错控制等。
3. 设备驱动程序：是 I/O 进程与设备控制器之间的通信程序，又由于它常以进程的形式存在，故就简称为设备驱动进程。
4. 中断处理程序
   • 中断：外部触发
   • 陷入：内部原因
5. 硬件

I/O 系统接口

• 块设备接口：指以数据块为单位来组织和传送数据信息的设备。典型的块设备是磁盘、光盘。
• 流设备接口：又称字符设备指以单个字符为单位来传送数据信息的设备。这类设备一般用于数据的输入和输出，有交互式终端、打印机。

4.2 缓冲区

缓冲的引入（原因）：缓和 CPU 与 I/O 设备间速度不匹配的矛盾。

分类

• 单缓冲区
• 双缓冲区
• 环形缓冲区（专为生产者和消费者打造）
• 缓冲池
  • 组成：空白缓冲队列（emq）、输入队列（inq）、输出队列（outq）

4.3 磁盘

• 盘面（Platter）：一个磁盘有多个盘面；
• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
• 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
• 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
• 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
• 主轴（Spindle）：使整个盘面转动。

磁盘调度算法

1. 先来先服务（FCFS, First Come First Served）
2. 最短寻道时间优先（SSTF, Shortest Seek Time First）
3. 电梯算法（SCAN）