---

操作系统（Legacy 大杂烩）

[!info] related notes 操作系统 MOC

这份笔记是历史遗留汇总，内容很杂，建议以新原子笔记为准。

计算题：

PV操作

作业调度算法（算周转时间）（FCFS、SJF、HRRN）
银行家算法
地址转换
页面置换算法（OPT、FIFO、LRU）
磁盘调度算法（FCFS、SSFT、SCAN、CSCAN）
位示图

概述

操作系统是用户与计算机硬件系统之间的接口
是计算机系统资源（处理机、存储器、IO设备以及文件）的管理者

概念	描述
程序	是静态的，存放在磁盘里的可执行文件，是一系列的指令有序集合。
进程	具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的基本单位。
指令	是指示计算机执行某种操作的命令，是计算机运行的最小功能单位。
线程	进程的一个实体，是 CPU 调度和分配的基本单位，它是比进程更小的能独立运行的基本单位。
作业	指用户在一次解决或是一个事务处理过程中要求计算机系统所做的工作的集合。作业由三部分组成，即程序、数据和作业说明书。一个作业可以包含多个程序和多个数据集。

操作系统的发展过程

1. 未配置操作系统的计算机系统
   1945 诞生第一台计算机，到 50 年代中期的计算机，都属于第一代计算机。还没有出现 OS，对计算机的操作由人工实现。
2. 单道批处理系统
   系统资源得不到充分利用
3. 多道批处理系统
   资源利用率高、系统吞吐量大
   平均周转时间长、无交互能力
4. 分时系统
   多路性、独立性、及时性、交互性
5. 实时系统
   多路性、独立性、及时性、交互性、可靠性

实时系统与分时系统的比较

操作系统的基本特性

• 并发
  微观上分时进行
• 共享
  系统中的资源可供内存中多个并发执行的进程共同使用
• 虚拟
  物理实体变为若干个逻辑上的对应物
• 异步
  进程以人们不可预知的速度向前推进

操作系统的功能

存储器管理功能

为多道程序的运行提供良好的环境

• 内存分配
• 内存保护
• 地址映射
• 内存扩充

操作系统与用户之间的接口

CLI、GUI、API

• 用户接口
  联机用户接口
  脱机用户接口 图形用户接口
• 程序接口

进程管理

进程的定义

为了使参与并发执行的每个程序（含数据）都能独立运行，在操作系统中配置了一个专门的数据结构，进程控制块（Process Control Block， PCB）。

由 程序段、相关的数据段 和 PCB 三部分构成了进程实体

是进程实体的运行过程，是系统调度和资源分配的基本单位。

PCB

定义：
PCB（进程控制块）:系统中用来存放进程管理和控制信息的数据结构称为进程控制块（Process Control Block）。

PCB的作用： 使参与并发执行的每个程序（含数据）都能独立运行

进程控制块用来保存每个进程和资源的相关信息，包括进程标识、空间、运行状态、资源等相关信息。以便操作系统控制和管理进程和资源。因而它的作用是使一个在多道程序环境下不能独立运行的程序（含数据），称为一个能独立运行的基本单位，一个能和其他进程并发执行的进程。

保存 进程的运行状态、进程控制信息和系统资源信息等

PCB是进程存在的唯一标志：
创建一个进程的同时也会创建一个PCB，撤销一个进程时，也会回收它的PCB

进程的基本状态

进程&线程&协程

三种基本状态：

• 就绪状态
• 执行状态
• 阻塞状态

基本状态的转换

进程同步

并发执行的进程按照一定规则共享资源，使程序的执行具有可再现性。

两种形式的制约关系

间接相互制约
像打印机之类的资源，进程间只能互斥地访问。

直接相互制约关系
进程间相互合作地关系

临界资源

打印机、磁带机等属于临界资源，进程间采用互斥方式实现对这种资源地共享。

临界区

每个进程中访问临界资源地那段代码称为临界区。

同步机制应遵循的规则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

进程通信

进程之间的信息交换
进程间的互斥与同步需要在进程间交换一定的信息也被归为进程通信，但只是低级进程通信（效率低、通信对用户不透明）。

进程通信的类型

高级通信机制可归结为四大类： 共享存储器系统、管道通信系统、消息传递系统、客户机-服务器系统

共享存储器系统

相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间通信。

• 基于共享数据结构的通信方式
  操作系统仅提供共享存储器
  仅适合传递相对少量数据，通信效率低下，属于低级通信
• 基于共享存储区的通信方式
  高级通信

管道通信系统

管道，用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名 pipe 文件。
以字符流的形式写入和读取。

消息传递系统

不必借助任何共享存储区或数据结构，而是以格式化的消息（message）为单位，将通信的数据封装在消息中。
隐藏了通信实现细节，对用户透明化。
当前应用最广泛的一类进程间通信机制。在计算机网络中，消息又被称为报文。
属于高级通信方式。实现方式不同可分为：

• 直接通信方式
  发送进程利用 OS 所提供的发送原语，直接把消息发给目标进程
• 间接通信方式
  通过共享中间实体发送接收消息

处理机

处理及调度的层次和调度算法的目标

调度的层次

• 高级调度
  又称长程调度或作业调度，它的调度对象是作业。
  主要功能是根据算法决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要资源、放入就绪队列。
  主要用于多道批处理系统
  分时和实时系统没有
• 低级调度
  又称短程调度或进程调度，调度对象是进程。
  根据算法，决定就绪队列中哪个进程获得处理机，并由分派程序将处理机分配给被选中的进程。
  最基本的调度
  多道批处理系统、分时和实时系统都必须配置
• 中级调度
  又称内存调度。
  把暂时不能运行的进程调至外存等待（进程状态称为就绪驻外存状态或挂起状态），提高内存利用率和系统吞吐量。
  当它们具备运行条件且内存稍有空闲时，调入内存，修改状态为就绪状态。
  就是存储器管理中的对换功能

作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。
操作员吧用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备队列中。再由作业调度程序将其从外存调入内存。

批处理系统中的作业

作业（Job）。一个比程序更为广泛的概念，不仅包含通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行加以控制。

先来先服务调度算法

短作业优先调度算法

优先级调度算法

高相应比优先调度算法

进程调度

进程调度的任务、机制、方式

方式

• 非抢占方式
  一旦把处理机分配给某进程后，就一直让它进行下去，直到进程完成。
• 抢占方式
  允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机分配给另一个进程。

轮转调度算法

优先级调度算法

多级反馈队列调度算法

基于公平原则的调度算法

实时调度

P105

死锁概述

所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局；

当进程处于这种僵持状态，而且无外力作用时，它们都将无法再向执行任务。

产生死锁的原因：
可归结为如下两点：
竞争资源
进程间推进顺序非法

产生死锁的四个必要条件

• 互斥条件
• 请求和保持条件
• 不可抢占条件
• 循环等待条件

处理死锁的四种方法

• 预防死锁
  破环产生死锁的四个必要条件中的一个或几个
• 避免死锁
  在资源动态分配的过程中，用某种方法防止系统进入不安全状态，如银行家算法
• 检测死锁
• 解除死锁

存储器

主要对象是内存

存储器的层次结构

P129

程序的装入和连接

P131

连续分配存储管理方式

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。
连续分配方式是最早出现的一种存储器分配方式，该分配方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。
连续分配方式可分为四类：单一连续分配、固定分区分配、动态分区分配、可重定位分区分配

动态分区分配

数据结构

空闲分区表
空闲分区链

基于顺序搜索的动态分区分配算法（内存分配算法）

• 首次适应（first fit， FF）算法 优先使用低地址空闲分区
  为大作业分配大空间创造了条件
  留下很多无法利用的小碎片，也增加了查找开销
• 循环首次适应（next fit， NF）算法 从上次找到的空闲分区的下一个空闲分区开始查找
  使空间更均匀
  但缺乏大空间
• 最佳适应（best fit， BF）算法 使用把满足要求的最小空闲分区
  要排序，开销大；留下很多无法利用的小碎片
• 最坏适应（worst fit， WF）算法 使用最大的空闲分区

分页存储管理方式

页面和物理块
地址结构
页表
页表的作用是实现从页号到物理块号的地址映射
基本分页需要两次访问内存，解决方式是快表

已知页表，计算物理地址/。。。。。。 https://blog.csdn.net/m0_62064241/article/details/121701722

分段存储管理方式

需要两次访问内存，解决方式是快表

分页和分段的主要区别

1. 页是信息的物理单位。段是信息的逻辑单位
2. 页的大小是固定且由系统决定的。段的长度不固定。
3. 分页的用户程序的地址空间是一维的。在分段系统中，用户的地址空间是二维的。

段页式存储管理方式

需要三次访问内存，解决方式是快表

虚拟存储器

概述

常规存储器管理方式特点

• 一次性
• 驻留性

逻辑上实现对内存容量的扩充

虚拟存储器基本

基本工作情况
将要运行的程序段装入内存，其余留在盘中，，需要再调入，要访问的页（段）尚未调入内存就发出缺页中断请求，满了就把不运行的部分调出。

虚拟存储器的定义

具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

虚拟存储器的特征

• 多次性
• 对换性
• 虚拟性

页面置换算法

• 最佳（Optimal）置换算法
  淘汰以后不使用的页
• 先进先出（FIFO）置换算法
  淘汰最先进入内存的页面
• 最近最久未使用（LRU）置换算法
  淘汰最近最久未使用的页面
• 最少使用（LFU）置换算法

抖动

产生抖动的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，每个进程在运行时，频繁出现缺页，进程大部分事件用于页面换进/换出，处理机利用率下降趋于 0。

预防方法

1. 采取局部置换策略
2. 把工作集算法融入到处理机调度中
3. 利用“L=S”准则调节缺页率
4. 选择暂停的进程

输入输出系统

IO控制方式

• 程序控制方式
  适用于结构简单，只需少量硬件的电路
• 中断控制方式
  适用于高效场合
• DMA 方式
  不需要CPU干预介入的控制器来控制内存与外设之间的数据交流的场合
  并行
  
• 通道控制方式
  适用于以字节为单位的干预，同时实现CPU、通道和I/O设备三者并行操作的场合

缓冲区管理

磁盘存储器的性能和调度

磁盘调度算法

• 先来先服务（FCFS）
  按先后顺序
• 最短寻道时间优先（SSTF）
  距离磁道最近
• 扫描（SCAN）
  与扫描方向相同且最近
• 循环扫描（CSCAN）
  固定方向，扫描到最外后，回到原点开始找

文件管理

文件系统

存储单位

术语	说明
扇区（Sector）	磁盘硬件的最小读写单位（通常512B或4KB）。
块（Block）	文件系统管理的最小单位（如4KB），由多个扇区组成。
簇（Cluster）	FAT文件系统中的分配单位，类似“块”。最小单位
Extent（扩展块）	某些文件系统（如ext4）用于管理连续块的高效方式。

文件系统的组成

结构	作用
超级块（Superblock）	存储文件系统元数据（如大小、块大小、空闲块信息）。
inode（索引节点）	记录文件的元信息（权限、大小、数据块位置等）。
目录项（Dentry）	文件名与inode的映射关系。
数据块（Data Block）	实际存储文件内容。

文件系统的类型

类型	特点	常见文件系统
磁盘文件系统	管理硬盘、SSD等存储设备	ext4, NTFS, FAT32, APFS
网络文件系统	远程访问文件	NFS, SMB/CIFS
虚拟文件系统	抽象不同文件系统（如Linux的VFS）	procfs, sysfs
日志文件系统	记录操作日志，防止崩溃后数据损坏	ext4, NTFS, XFS

文件

文件系统管理的最小磁盘空间单位是

数据项、记录和文件

数据项是字段、记录是段+值、文件是很多个段+值

文件的逻辑结构

文件逻辑结构的类型

• 有结构文件
  记录式文件
  • 顺序文件
  • 索引文件
  • 索引顺序文件
• 无结构文件
  流式文件