MyOS

my操作系统

常见操作系统：

MacOS，iOS，Windows，Android，Linux，symbian（NOKIA使用）

什么是操作系统

一台电脑的诞生过程
1. 厂家组装裸机
2. 厂家出售前安装操作系统
3. 用户安装应用程序（eg：QQ）
4. 使用QQ聊天
操作系统（Operating System）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源分配，以提供给用户和其他软件方便的接口和环境

给每个软件分配合适的硬件资源
具体管理的内容
- 文件系统管理
  
  文件创建、删除、IO，目录管理，文件权限…
- 进程管理
  
  创建、调度和终止进程，分配和管理进程资源
- 内存管理
  
  管理物理内存，虚拟内存…
- IO设备管理
  
  IO缓冲区管理，异常和中断处理
- 网络管理
  
  协议栈的管理和实现、连接的创建和维护、数据包的转发和路由
- GUI呈现与管理
操作系统向上提供的接口（服务）
- 面向用户的：
  1. GUI
  2. cmd——分为交互式和文件式（.bat批处理文件——包含一些列命令的文本文件，命令按顺序被逐一执行）
- 面向软件开发/程序员
  
  即：系统调用
  
  系统调用（System Call）是操作系统提供给应用程序的一种编程接口，它允许应用程序请求操作系统执行特权操作，例如访问硬件设备、进行文件操作、创建和管理进程等。系统调用是应用程序与操作系统之间的通信桥梁，允许应用程序执行需要操作系统权限的操作，同时保持了操作系统的安全性和稳定性。

操作系统的特征

并发 | 共享 | 虚拟 | 异步

并发：
指多个事件再宏观上是同时发生，但微观上是交替发生的

单核CPU内多个程序的交替执行是并发，多核CPU分别执行多个程序是并行
共享：
指系统中的资源可供内存中多个并发执行的进程共同使用

资源共享方式：
- 互斥共享——一段时间内只允许一个进程访问
  
  例如：微信和摄像头互斥共享摄像头
- 同时共享——允许一个时间段内，多个进行“同时”访问
  
  例如：多个进程进行磁盘IO，微观上其实是交替进行访问磁盘
虚拟：
指把一个物理上的实体变为若干个逻辑上的对应物。物理实体实际存在，而对应物只是用户感受到的。

实现技术：
1. 空分复用技术（在有限的内存中运行更大的软件—-有点像硬件层面的并发）
2. 时分复用技术（在有限时间内同时执行多个事件）
异步：
在多道程序并发执行下，进程的执行并非十分通常/可以预知，而是走走停停，在未来的某一时刻才有可能执行

操作系统的运行机制

内核程序 | 应用程序

应用程序：常规程序

内核程序：内核程序控制硬件产生反映，一系列内核程序组成操作系统的内核（Kernel）

应用程序一般不会有权力跨隔离性操作，而内核程序作为管理者有此权力

例如：内存清空指令就不会暴露在内核以外
内核态（管态） | 用户态（目态）

指CPU运行的两种状态

内核态时，CPU运行内核程序——此时有权力执行特权指令

用户态时，CPU运行应用程序——此时只能执行非特权指令
- CPU中，通过程序状态寄存器管理状态切换

中断和异常

中断：

指CPU从执行应用程序时，停止执行，并切换回内核态

中断是让操作系统内核夺回CPU使用权的唯一途径

一般程序时分复用交替的流程为：程序A执行--被中断，切换回内核态--内核态处理中断信息，操作系统选取下一个执行的程序--程序B执行

分类：
- 内中断（内部异常）
  - 故障 fault：指可能被修复的小问题【例如缺页中断】
  - 终止 abort：不可恢复的致命问题【例如除0】
  - 陷入 trap （指由于应用程序需要主动调用操作系统而引起的中断）
- 外中断
  - 时钟中断（程序切换）
  - I/O中断请求

系统调用

是操作系统提供给应用程序（程序员）使用的接口，是可被调用的一种特殊函数–可以请求到操作系统内核的服务（一般指令似乎只在CPU用户态）。

凡是和共享资源有关的操作（如存储分配，IO操作，文件管理等）都必须通过系统调用的方式向操作系统内核提出请求服务，由操作系统内核代为完成（可以保证系统的稳定性和安全性）。

过程：

当高级语言代码中调用系统调用库函数：

传递系统调用参数
执行陷入执行（从用户态 -> 内核态）
内核态执行相应的调用
返回应用程序

操作系统体系结构

内核
非内核功能

操作系统引导（boot）

指开机后如何让操作系统运行

磁盘划分

虚拟机

早期在硬件设备上构造一个操作系统，此操作系统只能让一个进程进行分配
后来出现多道批处理系统：通过将任务加载到队列中，允许一台计算机在同一时刻处理多个任务
发展出虚拟机技术 - 允许多个操作系统和应用程序在同一台物理计算机上并行运行

虚拟机：

使用虚拟化技术，将一台物理机器虚拟化成多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统。

需要使用：虚拟机管理程序（Virtual Mechine Monitor / HyperVisor）/虚拟机监控程序

虚拟机管理程序

第一类：

运行在硬件和各个操作系统之间，负责给操作系统分配各个硬件的隔离使用

问题1：原本操作系统需要拥有内核态的执行权限，但运行在虚拟机之上的操作系统实则属于用户态，解决办法是用户态的操作系统调用VMM的API

第二类：

运行在宿主操作系统之上，调用宿主操作系统的API间接调用硬件

例如：Windows上安装的VirtualBox，VMware就是VMM，用VirtualBox安装的centOS镜像就是运行在其上的操作系统。

此时虚拟机管理程序和宿主操作系统是同一层的

第二种由于在虚拟的操作系统和真实的硬件之间存在多层代理，在代理实现接口功能的逻辑中可能存在曲线救国的行为

例如：VM1申请10GB的存储空间，请求到达管理程序，管理程序的内部逻辑或许会将宿主操作系统提供的分散的空间拼凑成10GB，向上提供好似连续的空间——就是虚拟。

但第一种直接操作硬件的VMM就没必要了。

进程与线程

PID（Process ID | 进程ID）

每一次新建进程，都会标识唯一自增的进程ID

事实证明未必自增，并且一个程序可能启动多个进程【多进程编程】

以进程为单位聚合和许多属性：
- 进程所属ID（UID）
- 进程分配了多少内存
- 进程CPU使用情况
- 进程的磁盘IO情况
- 进程的网络IO情况
- 正在使用哪些IO设备
- 正在使用哪些文件
- 当前运行状态：就绪 / 阻塞 / 运行
- …
以上总体分为四类：
1. 进程描述信息
2. 进程运行信息 | 资源利用情况 – CPU，磁盘，网络..
3. 进程状态信息 | 就绪，阻塞，运行
4. 资源分配清单 | 正在使用哪些文件，分配的内存空间，使用的IO设备
5. 处理机相关信息 | PSW，PC等寄存器值（用于实现进程切换）
PCB（Process Controller Block | 进程控制块）

操作系统对各个进程的管理信息，都被放置在PCB中

PCB是进程存在的唯一标识，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收PCB
进程的组成：
- PCB
- 程序段（进程具体执行的代码）程序的运行就是CPU读取程序段指令的过程
- 数据段（代码中临时变量存放在此处）
进程是动态的，而进程实体是进程的image，反应了某一时刻的状态

进程：是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程特点：

动态性：动态产生、变化、消亡
并发性：内存中多个进程实体，并发执行
独立性：进程独立运行，独立获得资源，接受调度
异步性：各个进行以独立的、不可预知的速度向前推进，结束时间不确定会有潜在问题，操作系统需要提供“进程同步机制”来解决异步问题
结构性：每个进程会配置一个PCB，程序段，数据段

进程的状态切换

创建态：正在被创建「操作系统将程序的可执行文件读入内存，并为之创建PCB，分配数据块和程序块」
就绪态：系统完成创建工作后，线程等待CPU资源
运行态：进程被CPU调度：单CPU情况下，同一时刻只会有一个进程处于运行态，多喝CPU可能有多个
阻塞态：原本处于运行的进程，通过“系统调用”尝试申请资源，但是资源被占用，线程本身pending
终止态：由运行态主动结束，或者遇到不可修复的错误

java API：

直接使用线程相关的方法来控制和转换线程的状态

例如：Java中Thread类下，yield()方法，显式的将线程由执行态转换为就绪态；wait()方法到达阻塞态，stop()进入终止态

进程的创建

// TODOS

进程的组织

链表：维护多个链表

将状态相同的进程统一管理

有点像mySQL缓存淘汰机制

链表：

执行指针
就绪队列指针
阻塞队列指针

有的会按照阻塞缘由/等待的资源分成多个链表，例如：等待打印机的阻塞队列 / 等待磁盘的阻塞队列

索引：

相较于链表用空间换时间尝试增加连续内存空间以减少寻址时间

进程控制

前置：

原语：特殊的程序，其执行具有原子性，通常用在较底层的，不可发生意外情况的逻辑中「如CPU切换，设备驱动…」

原语的实现逻辑原本CPU在执行每行指令后，都需要监听有无外部中断信号，如果有则被中断，原语通过两个更高权力的指令「特权指令」“关中断指令”，“开中断指令”来取消监听

前置：

mac中，进程间的关系是树形结构，由0号进程kernel_task和1号进程launchd创建其他进程，再由这些进程创建其他进程…

进程通信（IPC）

进程之间的通信必须通过操作系统

隔离是必要的，无法通信是隔离的代价

由于每个进程都分配有对应的进程内存空间，而不同进程不允许相互访问（用户空间访问隔离），所以跨进程的通信只能通过操作系统提供的API（内核空间访问自由）

三种方式：
共享存储
消息传递
管道通信

共享存储：

用于同一主机中，不同进程间的通信方式

在内存中申请一片共享内存区，并加一把互斥锁「P，V操作」，即可实现通信

int shm_open(); //系统调用，申请一片共享内存区
void * mmap(); //通过mmap系统调用，将共享内存区映射到进程自己的地址空间

mmap()：

原本的目的是：将文件keep在内核态，不用通过read复制到用户态再修改，而是用户态改用户态的，改了以后映射到内核态page cache上即可

共享存储中：两个进程映射同一个page cache的区域，本质上还是会向内核态写入数据，然后另一个线程从内核态的cache上读走（只不过，由于是映射，读的过程其实是自动执行）

具体分两类：

基于存储区的共享：操作系统只负责划出共享存储区，而数据的形式、存放位置等都由线程负责

– 速度较快，高级通信方式
基于数据结构等共享：操作系统分配的共享空间是确定类型的，例如：只能存放一个长度为10的数组

– 速度较慢，限制较多，低级通信方式

消息传递：

进程件的数据交换通过操作系统提供的“发送消息 / 接收消息”两个原语

发送方将消息发送到消息队列中，只不过这个队列可能在目标的PCB上，也可能在一个公共区域

交换的数据符合格式：消息头「发送进程ID，接收进程ID，消息长度…」；消息体

具体分两类：

直接通信方式

消息直接由发送方到达接收方

过程：进程P试图向进程Q发起消息msg
- P.send(Q,msg)，Q.receive(P,msg)
- 过程中异步解耦，P发起消息先到Q的PCB中维护的消息队列中「缓存，可能是链表」，在由Q搜索有无P的消息
间接通信方式

通过“信箱”间接通信

过程：进程P试图向进程Q发起消息msg
- 在操作系统内存中申请信箱空间A，P.send(A,msg)，Q.receive(A,msg)；

消息队列和管道都会将消息停留在一片公共区域，中间就有数据从用户态到内核态再到用户态的复制过程，比较费时

管道通信：

由一片共享的内存空间作为循环队列，并且是阻塞队列

channel / pipe

是一种特殊的文件，只存在于内存，不在文件系统中
管道只能采用半双工通信，某一时间只能实现单向数据传输
管道中的数据一旦被读出，就彻底消失，因此在多个进程读取同一管道时可能会错乱
运用：Linux中的管道符号——用于在两个任务间建立管道，上一个任务（进程）的结果通过管道传递给下一个任务的输入
问题：通信效率比较低

管道通信是同步通信，写方的信息没被读前写方只能等待

//TODO：netty基于Socket建立的全双工channel，和这个有啥关系，尚硅谷为什么安排在这里说netty？

线程：

还没有线程概念时，进程是程序执行的基本单位。CPU只需要在多个进程间切换，当切换到进程A时，顺序执行进行A轮到的代码

开出多线程后，CPU通过某种调度算法将资源分配个具体线程，此时线程就是程序执行的基本单位

将原本多个进程并发执行的任务给到一个进程，同时又要保证并发性 – 线程

但进程是除CPU外，系统资源的分配单元【打印机，网卡等设备只能被分配到进程级别】

变化：
1. 传统的进程间并发，需要切换进程的运行环境，系统开销很大
  - 尤其页表的切换成本很大 – 页表本身就很大，页表中存储的虚拟地址和物理地址的映射关系需要在将所有页加载完后才知道；另外页表通过快表加速访问，切换后缓存全部过期
  - 线程的上下文切换只需要将线程间隔离的寄存器信息和栈信息保存到TCB即可
2. 线程间的并发，当线程属于一个进程则不需要切换环境【上下文执行的是同一任务，环境变量不变】
  
  线程的创建时间比进程快
3. 进程在创建过程中，需要资源管理信息，比如内存信息，文件系统信息，而线程的创建只需要创建轻量级的TCB，之后便可共享进程的资源
线程的属性 / 特点
1. 线程是处理机调度的单位
2. 多CPU计算机中，各个线程可占用不同的CPU
3. 每个线程都有一个线程ID，线程控制块（TCB）
4. 线程也有就绪、阻塞、运行三种基本状态
5. 线程几乎不拥有系统资源
6. 同一进程的不同线程间共享进程的资源
7. 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干扰
8. 同一进程中的线程切换，不会引起进程切换，且系统开销较小
9. 不同进程中的线程切换，会引起进程切换，开销较大

线程的实现方式：

用户级线程（User-Level Thread）

早期操作系统只支持进程，不支持线程，当时的 “线程“ 概念是由”线程库“逻辑上实现的 – 即本质上是由程序员作为操作系统的用户将应该并发执行的任务写到一个进程中切换执行

例如：

早期程序员写好多个线程的任务后，线程库将多个线程的代码逻辑穿插到一起，挤到一个进程内交付给操作系统

现在的线程库有更强的功能，例如线程的创建，销毁，调度算法...

特点：
1. 线程的管理工作由开发线程库的开发者完成，并不需要依靠操作系统
2. 线程切换不需要CPU调度，甚至不需要用户态和内核态转变
3. 操作系统无法意识到用户级线程的存在 – 本质上还是以进程为CPU基本的调度单位

优点：

用户级线程的切换在用户空间即可完成，不需要切换到内核态，线程管理的系统开销比较小

缺点：
进程间不隔离，由于最后都会统一到一个进程中依次执行，假如其中一个线程被阻塞，其他线程也会受牵连
1. 内核级线程（Kernel-Level Thread）

由操作系统支持的线程

特点：

线程的调度、切换等工作都由内核负责，因此内核级线程的切换需要CPU在内核态才能完成
操作系统为每个内核级线程简历相应的TCB，通过TCB对线程进行管理。

优点：

当一个线程被阻塞后，别的线程还可以继续执行，并发能力较强。
多个线程可以被调度到多个CPU上并行执行

缺点：

一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到内核态，所以线程管理的成本较高

将用户级线程和内核级线程的思路相结合：

存在用户级线程，也存在内核级线程；于是二者需要有对应/转化关系

多线程模型

一对一模型：
一对多模型：
多对多模型：

要求：n个用户线程映射到m个内核线程，其中n>=m

特点：
- 克服了多对一模型并发度不高的缺点
- 客服了一对一模型占用太多内核级线程的开销大的缺点

多对多的模式中，可以通过灵活安排映射情况，实现类似一对一的效果【让忙的用户线程独占，让不忙的共享】

线程的状态与转化

和进程类似：

线程的组织与控制

类似进程通过PCB管理，线程通过TCB管理

TCB组成结构：

线程标识符：TID
程序计数器PC：用来标识线程目前执行到哪里
寄存器：存储运行的中间状态
堆栈指针：堆栈中保存函数调用信息、局部变量等，TCB中存储着指向该位置的指针
线程运行状态：运行 / 就绪 / 阻塞
优先级：与线程调度，资源分配相关

可以按照不同策略将线程的TCB串联成几张表，例如一个进程中的几个线程，处于就绪态的几个线程…

处理机调度

调度：当有一堆任务要处理，但由于资源有限，事情没法同时处理，这就需要确定某种规则来决定处理任务的顺序

高级调度 – 作业调度：

作业：用户交给操作系统的一项具体任务（例如：启动一个程序，加载一个文件…）

作业调度：指按照一定的原则从外存的作业后备队列中挑选出一个作业调入内存，并创建与之相对的进程

调度过程中需要确保内存不会泄露，以及其他偏好
低级调度 – 进程调度 / 处理机调度：

按照某种策略从就绪队列中选择一个进程，将处理机分配给它

进程调度的频率：十几毫秒一次
中级调度 – 内存调度：

当内存不够时，可能会将某些进程的数据调出外存，等内存空闲或者进程需要时再重新调入内存【关于内存空间与外存缓冲区间的调度】

所以按照某种策略决定将哪个进程挂起、将哪个处于挂起状态的进程重新调入内存，即内存调度

进程的七状态模型：

进程切换（调度）的时机：

需要进行进程调度与切换的情况：

当前运行的进程主动放弃CPU
- 程序正常终止
- 运行中发生异常而终止
- 进程IO阻塞
当前进程被动放弃CPU
- 分给此进程的时间片用完
- 有更加紧急的事情需要优先处理（例如IO中断）
- 有更优先级的进程进入就绪队列

不能进行进程调度的情况：

处理中断的过程中
进程在操作系统内核程序临界区中
在原子操作过程中

进程调度的方式：

非剥夺调度方式（非抢占方式）

只允许进程主动放弃处理机

在运行过程中即使有更紧迫的任务到达，当前进程依然会继续使用处理机，知道该进程终止或主动要求进入阻塞态
剥夺调度方式（抢占方式）

当一个进程正在处理机上执行时，如果有一个更加紧迫的进程需要使用处理机，则立即暂停正在执行的进程。

进程的切换过程：

从就绪队列中选中一个要运行的进程

让当前进程让出处理机，选出的进程进入处理机

具体的 2 过程：

对原来运行的进程中的数据进行保留（写入PCB），对新的进程的数据进行恢复（从PCB中读取）

调度器 / 调度程序（scheduler）

进程在就绪、运行、阻塞三种状态间的切换的具体handler

当创建新进程时，新进程加入就绪队列，调度器需要观测是否将这个新进程抢占CPU资源
当占用CPU的进程主动退出，调度器来运行调度程序（调度算法）
运行的进程阻塞，调度新进程进来
IO完毕，可能需要欢喜某些阻塞的进程

调度器决定：

让谁运行？
运行多长时间？

闲逛进程：

调度程序永远的备胎，当没有其他就绪进程时，运行闲逛进程

特点：

优先级最低
能耗低
闲逛进程周期性的执行0地址指令，在指令周期末尾例行检查中断（触发调度程序来检查有无就绪进程）

调度算法的评价指标

CPU的利用率
系统吞吐量

单位时间内完成作业的数量
周转时间

指从作业被提交给系统开始，到作业完成为止的时间间隔
- 时间包括四部分
  1. 作业在外存后备队列上等待作业调度
  2. 进程在就绪队列上等待进程调度
  3. 进程在CPU执行
  4. 进程等待IO的阻塞时间
带权周转时间

由于周转时间包括作业实际运行的时间和阻塞 / 等待调度的时间，理论上应该让实际运行时间比阻塞/等待时间多得多 – 带权周转时间

执行任务需要相同CPU时间的作业，需要等待的时间越少，带权周转时间越底，用户满意度越高
等待时间

指进程 / 作业处于等待处理机状态的时间之和

—– 等待时间过程会导致进程 / 作业饥饿
响应时间

指用户从提出请求到首次产生响应所用的时间

调度算法

FCFS（先来先服务）
算法思想：公平 - 参照原生队列的FIFO

是否可抢占：用于非抢占式的算法
- 最简单的调度模型 - 下一个任务等待上一个任务结束
优点：公平、实现简单

缺点：并没有合理的调度 – 排在长作业后的短作业需要等待很长时间，带权周转时间很大，对于短作业的用户体验不好
SJF（短作业优先 short job first）
算法思想：针对FCFS对短作业并不友好，SJF追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间

算法规则：最短的作业优先得到服务

是否可抢占：常规时非抢占，也有抢占式版本 – SRTN（最短剩余时间优先算法）
SRTN
算法思想：每当有进程加入就绪队列时就需要尝试调度；如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则有新进程抢占处理机

要求：每个任务 / 进程需要标志剩余时间 – 怎么估算剩余时间？
- 1. 1. 特点：
    不公平：对短作业有利，对长作业不利
    
    可能产生饥饿现象
- 另外：作业 / 进程的运行时间由用户提供，并不一定真实，所以不一定能做到真正的短作业优先

综上所属，FCFS优先选择等待时间最长的作业进行服务，但并不考虑作业需要的时间，SJF优先选择执行时间短的作业进行服务，但不考虑作业等待了多长时间。

HRRN（高响应比优先 Highest Response Ratio Next）
算法思想：综合考虑作业的等待时间和要求服务的时间

算法规则：每次调度时，先计算各个作业 / 进程的响应比，选择比率较高的为其服务

是否可抢占：非抢占的调度算法（避免在每个新任务进入后计算一遍执行中的任务的响应比）

感觉也可以做成抢占式
RR（时间片轮转 Round-Robin）
算法思想：公平的，轮流的为各个进程服务，让每个进程在一定时间内都可以得到响应

是否可抢占：抢占式算法：由时钟装置发出时钟中断来通知CPU时间片已到

问题：
- 当时间片太大，算法会退化为FCFS调度算法
  
  当用户的两个操作（任务）并不连续在一起执行【例如调试操作】，两次调试至少要等待一轮时间片才能回到当前线程
- 时间片太小时导致切换进程 / 任务的成本太高
优先级调度算法
算法思想：许多应用场景需要根据任务的紧急程度来决定处理顺序

算法规则：每个作业 / 进程标志自身优先级，调度时选择优先级高的作业 / 进程

是否抢占式：
- 非抢占实现：
- 抢占式实现：

优先级可以分为静态优先级和动态优先级，区分某些进程在创建后执行中优先级可以调整

问题：

如何合理设置进程的优先级：

普遍原则：
1. 系统进程优先级高于用户进程
2. 前台进程优先级高于后台进程
3. 操作系统更偏好I/O型进程（相比于计算型进程）：为了让IO更早启动，提高IO设备利用率
如何利用动态优先级：

使用动态优先级，就是为了让静态优先级策略更加灵活，能够在某些场景下追求更加合理的调度方案 – 更加公平 / 资源利用率更高

例如：

如果某个进程在就绪队列中等待了很长时间，则可以适当提升优先级

如果某个进程占用了处理机很长时间，可以适当降低其优先级
多级反馈队列调度算法：

对其他调度算法的折中权衡

算法规则：
- 设置多级就绪队列，各级队列的优先级从高到低，时间片从小到大
- 新的进程到达时，先进入第一级队列，按FCFS原则排队等待被分配时间片。假如用完时间片后进程还未结束，则进程进入下一级队列队尾（如果此时已经在最下级队列，则重新放回最下级队列队尾）
- 当第k级队列为空时，会调度 k+1 级队列的队头分配时间片
- 当CPU上有第K级的任务在执行，而突然来了小于K级的任务，则优先级别高的任务处理，被抢占的任务/进程放回原队列队尾

感觉：每个任务都有先执行一点的机会，但是随着任务时间拉长，其优先级降低，被执行的次序往后排

关于灵活调整优先级，此算法也可以实现：只需将跑过时间片后的任务不降级，重新放回原队列末尾即可

多级固定队列调度算法：
系统中，按进程类型设置多个队列，进程创建后加入某个队列

多个队列是按照优先级分类，例如：系统进程是第一优先级，交互式进程是第二优先级，批处理进程是第三优先级…

确认了进程优先级即明确了基本执行顺序，后续为了更加公平、避免饥饿、响应更快可以参考上述算法思想进行优化

例如：
- 系统进程队列采用优先级调度
- 交互式队列采用时间片轮询
- 批处理队列采用FCFS

进程同步

由于进程具有异步执行的特点：每个进程独立执行，相互不确定彼此是否完毕。但是当多个线程协同工作时，出于业务需求又要按照某种顺序执行。

同步 – 直接制约关系，指为完成某种任务而建立的两个或多个进程需要在某些位置上协调其工作次序而产生的制约关系。

同步机制准则：

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

进程互斥

当进程需要“共享”地访问某个资源时，可能无法实时共享

两种资源共享方式：

互斥共享：系统中的某些资源一个时间内只允许一个进程访问使用，例如打印机，摄像头
同时共享：系统中某些资源允许多个进程同时访问

把一个时间段内只允许一个进程使用的资源称为：临界资源

对临界资源的互斥访问过程：

进入区：负责检查进程是否可入（完成锁的管理）
临界区：临界资源相关代码
退出区：锁释放
剩余区：其他处理

进程互斥的实现方法（软件实现）

单标志法
算法思想：通过声明一个变量记录当前哪个进程拥有权限访问

具体逻辑：
- 进程在进入区通过while循环判断是否轮到自身
- 一旦进入while，在临界区执行自身逻辑
- 退出区更改变量的值

问题：

没有合适的超时机制，容易让权限被动的停在某个进程但不释放
1. 双标志先检查法 / 双标志后检查法

差不多，不太行

Peterson算法

基于两现场的并发互斥算法 – 本质时一种谦让模式

有一组Boolean变量 flag 表示各个进程对使用资源的意愿，也有一个变量 turn 表示此时哪个进程拥有锁

每个进程尝试访问临界区的过程：
1. 设置自身flag意愿为true
2. 让出turn的权力，设置为对方
3. 阻塞判断：其他进程如果有想进的，并且turn被占用；则while循环阻塞
  
  如果其他进程都不想进，turn自然没人占用，顺利进入临界区，或者当其他进程想进，但还没占用turn，进入的权力仍然属于自身线程

Peterson本质还是和单标志法一样用一个变量turn标识锁的归属，但是能并不像单标志法只能交替进行，而是自身可以决定是否继续占用资源：做决定需要其他线程的状态信息，额外设置了表示意愿的flag数组，通过”谦让“的行为，也能保证进程的顺次执行。

进程互斥的实现方法（硬件）

中断屏蔽方法
算法思想：利用”开 / 关中断指令“，保证过程中的指令不允许被中断，也就不允许发生线程切换，因此不会发生互斥访问

优点：简单高效

缺点：
- 只适用于操作系统内核程序，不适用于用户进程
- 并且不适合多处理机（因为不切换进程只能保证一个CPU上进程不变，但其他CPU上的进程仍然有可能并发）
TestAndSet / TestAndSetLock TSL指令

由硬件支持的单标志法（但是不局限在两个线程上），在硬件设备中使用TSL执行将checkAndSet原子化成一个指令，于是不怕并发

基本逻辑：

while循环中检查lock变量是否时true（表示被加锁）

没加则自身加锁，进入自身代码，其他进程阻塞在外

但是以上方法都存在while（true）循环check，理论上当某个进程无法进入临界区时，应该让出CPU，而不是循环检测

锁

上述使用变量表示权限归属的方法都是加互斥锁

互斥锁的缺点是：忙等待

即：如果某个资源被占用，其他尝试获取资源的进程只能循环查看锁的情况【自旋锁 spin lock】；

当多个进程共享一个CPU时，由于被阻塞的进程和正在使用资源的进程本质需要顺次执行，于是无法在释放锁第一时刻就获取到锁，而是等到释放锁后下一个自己的时间片才能获取锁。于是互斥锁只有多处理器才能承受。

互斥方法8：原语+信号量

操作系统用一个整数型的变量作为信号量，用来标识系统中某种资源的数量

本质也是用变量代表锁

操作系统提供一对原语：wait(s),和signal(s)

wait(s)：用来原子化原本轮询S是否空闲的操作

void wait(int S){
    while(S <= 0);
    S = S-1;
}

避免多个线程同时判断，同时减一的竞态问题

signal(s)释放资源
1
2
3
void signal(int S){ S = S+1; }

互斥方法9：原语+记录型信号量

记录型信号量：指不仅记录某个资源的剩余情况，还标记有等待该资源的进程队列

typedef struct{
    int value;
    struct process *L
} semaphore;

原本通过轮询的方式检测信号是否变化，现在反向通知信号量更新

void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L); 
//表示如果当前资源不足，将本线程挂载到等待队列中
    }
}void signal(semaphore S){
    s.value++;
    if(S.value <= 0){ //有进程在等待
        wakeup(S.L);
//表示当本进程释放资源后，尝试唤醒 / 通知等待队列的进程    
    }
}

互斥方法9：AND信号量：

思想：即使原本的记录型信号量四个同步原则都满足，但任然有可能导致死锁，AND信号量尝试解决死锁问题：

当一个进程同时想要获取到多个共享资源的情况，可能存在死锁的风险，AND基本思想L将进程在整个允许过程中需要的所有资源，一次性分配给进程，使用完后一起释放

只要有一个资源未能分配给进程，其他所有可能分配的资源也全都不分配给它

【容器化？】

管程

背景：虽然信号量机制方便有效管理同步，但每个进程都要独自管理PV操作完成同步，麻烦且容易死锁

管程：像是一个单例的令牌（拿着它才能执行它规定的操作）

实际上就是将PV操作封装到入口方法中

管程中定义了共享数据
定义了访问这些数据的入口（get / set …）
管程中有很多“入口”，但每次只能开放其中一个入口，让一个进程或线程进入【由编译器负责实现的互斥】
在管程的具体入口方法中，设置条件变量 & 等待/唤醒操作解决同步问题

信号量机制实现进程同步

方法：

明确哪些代码需要同步关系，假设A代码块需要先执行，B代码块需要后执行
设置同步信号量S，初始为0
在A操作后执行V(S)
在B操作前执行P(S)

S信号量代表“某种资源”，本质还是一把锁，通过在操作系统跨进程的全局声明这把锁，让两个进程完成间接的通信，彼此知道同步情况

PV操作本质上挂起等待，撤权唤醒其他进程；最直观想到的用处是进程同步，A挂起直到被B唤醒。也用来实现进程互斥，后到的进程被挂起，直到之前的进程唤醒它...比其他实现互斥关系的策略高级的点是：1. CheckAndSet两步为原子性操作，无竞态关系，2. 由wake反向唤醒而不是while轮询，节约CPU资源；

利用信号量的例子：

生产者 / 消费者模型

缓冲区的大小为n，要通过信号量实现阻塞队列模式

信号量的PV方法，能够监控某个资源是否有甚于，有则分配，无则挂起；但只能对某个变量判断其是否大于0，在缓冲队列场景中，既要判断队列中元素是否大于0，还要判断是否小于n，所以申请两个信号量full & empty，full初始化为6，越满越接近0.empty初始化为0，越空越接近0

PV逻辑:

producer(){
    while(1){
    //生产一个产品
    P(full);
    P(mutex);
    V(empty); //增加一个元素，empty离0报警差距增大
    V(mutex);    
}
}
consumer(){
    while(1){
    //消费一个产品
    P(full);
    V(empty);
    }
}

实现互斥的P操作需要在实现同步的P操作之后，否则会造成死锁

利用信号量解决文件读写锁

声明信号量rw = 1，表示一个文件要么在被读，要么在被写

如此解决读写的互斥行为
怎么解决读锁对读锁不互斥？

在加读锁时，判断当前进程是否是第一个尝试加锁的，是则加

即：多个读进程只在第一个进程加锁，用来屏蔽写进程。
但是在对P(rw)的逻辑处理中出现问题：
1
2
3
if(count == 0){ P(rw); }

将原本原子性的操作外包非原子性的逻辑，可能出现新竞态问题

解决方法：将整体再加互斥锁 – 声明范围更大的mutex信号量

死锁

经典场景：哲学家就餐

五个哲学家进程并发执行，首先都拿起左手边的筷子，接着尝试拿起右手边的筷子，但是右手边的筷子正在被别人拿着，而自己刚刚拿到的左手的筷子就是别人想要的右手边的筷子

A占用B等待的锁，同时等待B占用的锁

死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象

死锁、饥饿、死循环的区别：

产生死锁的条件：

互斥条件：资源不能是共享的
不剥夺条件：后来的进程只能等，不能抢
保持和请求：进程的状态需要一手保持资源，一手请求资源
循环等待条件：循环等待的进程构成一种链

对不可剥夺的资源的不合理分配，可能导致死锁

例如：进程请求和释放资源顺序不当：

P1，P2进程分别申请占用R1，R2，之后P1又申请R2，P2又申请R1

例如：信号量使用不当：

信号量在使用时，使用mutex同步也看作一种互斥资源，也可能产生死锁

死锁的处理策略

不允许死锁发生

静态策略（预防死锁）：

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

动态策略：

允许死锁发生 - 检测并解除

破坏互斥：

例如：

SPOOLing技术：

能够尝试将原本独占设备的逻辑改造成共享设备

例如：原本两个线程互斥使用打印机，SPOOLing使得两个线程的任务都能够被处理（初步地，由另一个任务管理，而非直接给打印机）

但是这种技术只是逻辑上的共享，某些设备根本不能共享一点
破坏不剥夺：

当某个进程需要的资源被其他进行所占有时，如果此进程优先级更高，则可以强行剥夺资源

缺点：
1. 被强行剥夺资源需要保证之前的内容被保存，而CPU天生支持此操作，其他资源在切换中不一定效率高
2. 引入优先级就会带来饥饿问题
破坏请求和保持条件

某个进程请求新的资源得不到满足时，它需要立即释放保存的所有资源，以后需要时重新申请。

or 静态资源分配法：进程在运行前申请完需要的全部资源，在未满足前，不投入运行

资源打包，有点像docker

缺点：
1. 资源和进程耦合绑定，导致资源的灵活程度不高 - 利用率不高
2. 隐性的饥饿问题
  
  由于进程的运行条件苛刻了，不运行的几率就增大了
  
  当进程A需要qwer四种资源，但qwer始终被其他进程以各种方式占用，A无法get all；
破坏循环等待：
顺序资源编号法
- 为了避免循环等待，尝试让拥有了某些资源的进程别去申请某些资源 – （打破环种某处）
- 为系统内的资源编号，规定每个进程必须按照编号递增的顺序请求资源
- 如此一来，假如原本ABCDE五个哲学家，E就不会拥有E而申请A，因为E会停留在申请A上
缺点：
1. 设备编号不好实现
2. 申请资源的顺序影响业务逻辑 - 资源按ABCD顺序来，但代码应该以DCBA使用资源，就会导致闲置时间长

动态策略：避免死锁

安全序列：

指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要找出一个安全序列，系统就是安全状态。

例如：银行家问题：只有给一家公司打满借款才能被还，否则公司无法偿还 - 银行决定如何将资源顺利分配给各个公司，某些顺序会导致资源锁死在公司，某些顺序可以完整执行
银行家算法：
思想：在某次资源分配之前，判断这次分配是否会导致系统进入不安全状态
- 操作系统判断基本流程：
  
  每个进程向操作系统申报需要的资源（用信号量表示的向量，来表示各个资源数目），操作系统判断是否安全 / 能否形成安全序列

死锁的检测和解除

检测：使用化简资源分配图【描述进程和资源的申请与占用的关系】，尝试找到某个进程可以得到申请，释放占用，可以让整张图运作起来

本质还是找到安全序列

如果找不到安全序列 - 进入不安全状态 - 即将死锁
解除：
1. 资源剥夺法：
  
  简单的将某个线程挂起，就可以让它空出资源
  
  但有些资源也不是说让就让
2. 撤销进程法：
  
  强行撤销部分进程。代价很大，导致进程之前的运行被浪费
3. 进程回退法：
  
  让某个死锁的进程尝试让出某个资源，只需要先让这个进程回退到还没申请此资源的状态。
如何决定对哪个进程动手？
1. 进程优先级
2. 进程执行了多长时间（撤销和回退的成本大）
3. 还需要多久能完成（期望大）
4. 进程已经占用了多少资源（释放多，期望大）
5. 进程是交互式还是批处理（交互式则优先级高…）

内存

回来吧我的TEG

内存的存储单元
内存存储数据的最小单元；从0开始编址。

按照单元大小分为：
- 按字节编址：每个存储单元的空间是8bit
- 按字编址：每个存储单元空间是1字（1字通常是16bit，但不同型号有所不同）
4GB的内存到底多大 -- 内存中可以存放 4*2^30个字节，即一共有 2^32个存储单元 -- 标识单位编号的数需要有32个二进制位。
CPU与内存的基本执行流程：

内存种，某个进程占据的内存空间分程序段、数据段、PCB。

CPU将程序段中的一条条指令读取，并按照指令码完成最基本的操作

例如：一次加法操作由读取某个地址的数到寄存器，加，将此数放回某位置三步
程序经过编译、链接后生成的指令中，指明的是逻辑地址（相对地址 / 局部变量内的地址），如何将逻辑地址转化成物理地址呢？

三种策略：绝对装入 / 可重定位装入 / 动态运行时装入
引理：程序从写代码到运行的过程
1. 源代码编译（将高级语言翻译成机器语言）
2. 将编译后的机器码和所需库函数链接，形成一个完整的装入模块
3. 装载（装入）：由装入程序将模块装入内存中
1. 绝对装入：
  
  在编译期间尝试修改相对地址到绝对地址
2. 可重定位装入：
  
  在装入过程中尝试修改相对地址到绝对地址
  
  将一个程序段中相对地址增加统一的偏移量 - 重定向
3. 动态重定位装入：
  
  并不尝试修改地址，而是把地址转换推迟到程序真正要执行时；
  
  需要一个重定位寄存器，用来记录程序段的偏移量；程序运行时只需要将相对地址+偏移量 = 绝对地址

链接的三种方法：

静态链接：程序运行之前将各个目标模块和需要的库函数链接成一个完整的可执行文件
装入时动态链接：在各个模块装入内存时，边装入边链接
运行时动态链接：程序执行中，当需要该模块时，才进行链接

内存管理
任务：
1. 内存空间的分配与回收
2. 内存空间的扩充（实现虚拟性）
3. 地址转换（由逻辑地址到物理地址的转换）
4. 存储保护：保证各进程在自身内存空间运行，不会越界访问
  两种实现方案：
  1. 设置上下限寄存器，当访问的地址越过边界则不允许
  2. 利用重定位寄存器，界地址寄存器记录边界
内存空间的扩充
1. 覆盖技术
  
  当程序大小超过物理内存总和时，能否只把核心程序段常驻性加载到内存，而不常用的段在需要时再调用内存
  
  内存中分出“固定区”和若干个“覆盖区”；程序分为若干个段，其中包括常用段和不常用段
  
  使用场景：
  
  当存在代码段之间互斥调用时效果最为显著
  
  确定：很难实现让操作系统感知哪些程序段是互斥的，只能人为设置互斥代码块
2. 交换技术
  
  思想：当内存空间紧张时，系统将内存中某些进程暂时换出外存，必要时将外存中某些已具备运行条件的进程换人内存（进程再内存与磁盘间动态调度）
  
  问题：
  1. 在磁盘的什么位置保存进程？
    
    通常将磁盘空间分为文件去和对换区；文件区用于存放文件，主要追求存储空间的利用率 - 因此对文件区空间的管理采用离散分配方式；
    
    对换区空间只占磁盘空间的小部分，被换出的进程数据存在对换区；对换区主要关注访问和加载速度 - 因此空间管理采用连续分配方式
  2. 什么时候交换？
    
    当内存吃紧，系统负荷增高，许多进程进程发生缺页
  3. 应该换出哪些进程？
    
    思考角度：
    - 换出阻塞的进程，反正一时也运行不了
    - 换出优先级低的进程（可能导致饥饿）
    - 换出驻留时间太长的进程
3. 虚拟内存技术
内存空间的分配与回收
- 连续分配方式 - 指为用户进程分配的是一个连续的内存空间
  - 单一连续分配
    
    当只有一个用户程序时，将整个内存中除了系统区外的空间全都给这个进程
    
    不需要存储保护，但内存利用率不高
  - 固定分区分配
    
    将整个用户空间划分成若干个固定大小的分区，每个分区运行一道作业
    
    分区大小可以相同（适合一台计算机控制多个同类任务的场景），也可以不同（适合执行不同任务的计算机，更加灵活）
    
    维护一张分区说明表，来实现各个分区的分配、回收、管理。
    
    问题：当程序太大 - 小空间放不下 - 需要覆盖技术才能放下
    
    当程序太小 - 会产生碎片
  - 动态分区分配
    
    不预先划分内存分区，而是在进程装入内存时，根据进程的大小动态建立分区，使得分区大小正好适合进程需要
    
    问题：
    1. 用什么数据结构记录内存使用情况：
      - 空闲分区表
      - 空闲分区链

    ![](file://C:\Users\吴松林\AppData\Roaming\marktext\images\2024-03-15-20-33-33-image.png?msec=1715927937190)

  2. 当很多个空闲分区都满足需求时，应该选择哪个分区进行分配？

    > 动态分区分配算法
    > 
    > - 首次适应：从头到尾找合适的分区
    >   
    > - 最佳适应：优先使用更小的分区
    >   
    > - 最坏适应：优先使用更大的分区
    >   
    > - 邻近适应：由首次适应演变而来，每次从上次查找结束位置开始查找
    >   
    > 
    > ![](file://C:\Users\吴松林\AppData\Roaming\marktext\images\2024-03-15-21-05-36-image.png?msec=1715927937255)

  3. 如何进行分区的分配与回收

    > 对于“空闲分区表”，通过管理表，实现对内存空间的逻辑管理
    > 
    > 表管理的API包括：释放某一进程空间将此空间合并 / 添加到表里；添加某一进程空间更新表中某个空间大小...


#### 内存碎片问题：

- 内部碎片：分配给某进程的内存区域中有些部分没用上

- 外部碎片：内存中某些空间分区由于太小无法被利用


外部碎片解决方案：

- 紧凑（拼凑）技术：将进程占用的空间往前移动

  紧凑技术会改变进程内指令的绝对地址，适合动态重定位装入方式，简单改变PCB中的重定向寄存器即可，而对于前面两种较死板的方案成本较大

非连续分配方式
- 基本分页存储管理
  分页存储：
  - 将内存空间分为一个个大小相等的分区，每个分区就是一个”页框 / 页帧 / 内存块 / 物理块 / 物理页面“
    
    每个页框有一个编号，即“页框号”
  - 将进程的逻辑地址空间也分为和页框大小相等的部分，每个部分称为一个“页 / 页面”，页面编号称为“页号”
  - 操作系统以页框为单位，为各个进程分配内存空间；进程的各个页面与内存的各个页框一一对应
  由页表管理每个进程的页面和具体页框的关系
  - 逻辑地址切换成物理地址：
    
    根据页表确定页面的起始地点，再加上由逻辑地址推算得出的页面内偏移量
    
    系统级优化：由于内存块大小，页面大小都是二的幂次，所以各种运算其实只是位运算，并无实际的乘除
  实际推算指令位置的流程：
  1. 由逻辑地址算出页号和页内偏移量
  2. 查找页表寄存器（记录此进程的页面记录在页表的何处）
  3. 查找页表，找到对应的页表项标明的内存块号
  4. 将内存块的起始位置 + 页内偏移量计算出实际物理地址
  5. 访问

  - 基于快表的优化查询方案

    > 快表：TLB（translation lookside buffer）部署在CPU内的高速缓存，用来存放最近访问的页表项的副本，为了比内存更快的访问
    > 
    > 既然是BUffer，类似Redis，也存在缓存命中、缓存过期等问题

    由于局部性原理，块表的命中率可以达到90&%以上

    > 局部性原理：
    > 
    > - 时间局部性：如果程序执行了某条指令，则不久后这条指令会被再次执行（因为程序中会有大量循环）
    >   
    >   对于内存中存放指令的空间而言
    >   
    > - 空间局部性：如果程序访问了某个存储单元，则不久后附件的存储单元也会被访问
    >   
    >   对于内存中存放变量的空间而言
    >   


  单级页表存在的问题：

  1. 用户进程占用空间可能会很大，导致页面很多，而页表需要是一片连续空间，当页面太多时空间太大

    > 解决方案令人无语：再将大页面分成小页面，由一个管理页表的页表（页目录表 / 一级页表）来维护每个页表块所在内存的具体位置

  2. 由于局部性原理，用户并不需要进程中的所有页面，可以考虑让某些不常访问的页面退出内存

    > 虚拟内存技术：通过在页表项增加标识字段，表示页面是否已经调入内存
    > 
    > 当用户态进程尝试访问在内存中不存在的内存块，会产生缺页中断（内中断），由操作系统将目标页面从外存中调入

- 基本分段存储管理

  > 分段存储：进程的地址空间按照自身逻辑关系划分成若干个段，段与段高内聚，每个段有一个段名，便于开发者调用
  > 
  > 例如：一个进程空间分成三段：
  > 
  > - MAIN：主函数段
  >   
  > - X：存储某个子函数
  >   
  > - D：存储全局变量
  >   
  > 
  > 于是逻辑地址由段号 + 段内地址组成

  访问过程：

  1. 当此进程要参与运行时，进程切换相关的内核程序负责恢复进程的运行环境；其中一步就是从进程的PCB中读取出 段表起始地址和段表长度，之后存储在段表寄存器中

  2. 根据指令的逻辑地址，推算出逻辑上所在段号和段内地址

  3. 访问段表寄存器，找到对应段表项对应的物理起始地址

  4. 将起始地址和段内地址相加，即真实物理地址


  过程中计算位置的操作可以内嵌检查是否越界

  #### 分页与分段的对比：

  1. 分页对用户不可见，分段对用户可见

  2. 分页的地址空间是一维的，分段的地址空间是二维的（对上层而言，而分段的上层就是开发者）

  3. 分段更容易实现代码保护（代码内聚程度较高，集权容易，而分页并不是按照逻辑拆分的每个代码块，较难隔离各种权限）

  4. 分页、分段访问一个逻辑地址都需要两次访问内存（引入二级分页则需要三次），分段存储也可以引入块表机制

- 段页式存储

  > 对于进程空间，先分段，再分页
  > 
  > 分段对与用户是可见的，开发者根据段号、段内地址进行开发；而分页对用户不可见，系统根据段内地址自动划分出页号和业内偏移量

  通过段表 + 页表明确对应物理空间的位置

  段表记录每个段对应的页号；页表记录每个页号对应的内存块号

虚拟内存

传统存储管理方式：
- 连续分配
  1. 单一连续分配
  2. 固定分区分配
  3. 动态分区分配
- 非连续分配
  1. 基于分页存储管理
  2. 基于分段存储管理
  3. 段页式存储管理

传统管理方式的缺点：

任务需要一次性全部装入内存后才能运行；导致当任务很大，空间很小时无法运行
同时任务中一些暂时用不到的数据也会长期占用内存，导致内存使用率不高

没有调度算法和淘汰算法

利用局部性原理可以设计调度算法和淘汰算法

调度：在程序装入时，将很快就会用到的部分装入内存，暂时用不到的部分留在外存

另外，当用户访问的信息不在内存时，操作系统负责将信息从外存调入内存

淘汰：内存不够时，由操作系统将蚕食用不到的信息换出外存

于是在用户看起来内存执行了更多的任务，看起来更大 – 虚拟内存

虚拟内存特征：

多次性：无需在作业执行前一次性全部装入内存，而是运行分成多次调入
对换性：存在作业的换入换出
虚拟性：…

虚拟内存计算要求内存管理使用离散分配

因为动态的调入调出代码块并不适合连续空间

请求分页存储管理

由于使用虚拟内存技术主要实现两点：

需要时调入、空间紧张时调出，所以每个页面需要额外的状态位标识状态，额外的统计指标用于被算法调度，额外的外存地址信息用户写回…

基本过程：

当想访问的页面不在内存中时，产生一个缺页中断；之后由操作系统的缺页中断处理程序处理中断

在中断过程中，缺页的进程阻塞，放入阻塞队列，调页完成后将其唤醒，放回就绪队列
缺页中断处理程序需要考察内存中有无空闲块，如果有，则占用，将外存中目的页面装入，并修改页表

如果没有，则需要有置换算法尝试淘汰一个页面；假如这个页面在内存期间被修改过，则要将其写回外存，未修改则直接淘汰

问题：

换入换出都是IO操作，都有不小的开销
一条指令可能会导致多次缺页中断，因为一条指令操作的数据可能分散在多个页中，【看来需要一次性加载…】
由于快表中有慢表的备份，更新慢表时任需更新快表

页面置换算法

由于换入换出成本较大，好的算法应该追求更少的缺页率

最佳置换算法（Optimal）

每次选择之后最长时间内不被访问的页面进行淘汰

需要预见未来，使用场景受限
先进先出置换算法（FIFO）

淘汰各个占用内存块上，最先进来的页面
最近最久未使用置换算法（LRU least recently used）

在页表中记录每个页面最近一次范围的时间，淘汰时挑选时间最长的页面
始终置换算法（CLOCK / 最近未用算法 Not Recently Used）

将内存中的页面链接成循环队列，要淘汰时从上次结束位置开选，选出使用次数少（通过在页表中加一个字段 - 访问位），且长时间没考虑的（一周没转到它）
改进型时钟置换算法

在修改过内容的页面和没修过过内容的页面之中，理论上应该让没修过过的淘汰，因为不用再IO没成本

所以此算法再添一个因素

用两个标志位（访问位、修改位）标识每个页面

策略优化 - - 局部置换

每个进程最开始会被分配一定数量的物理块，该进程缺页时，只允许从该进程自己的物理块中选出一个进程换出

避免置换算法导致页面管理太乱 - A的页面经常把B的页面顶掉…

对于经常切换的进程，更合理的策略是：多给几个块

策略优化 - - 可变分配

系统最开始分配给进程一定量的物理块，之后根据时期情况合理召回或者赋予物理块

策略优化 - - 何时调入页面

预调页策略

按照局部性原理，每次调用都尝试调入相邻的页面

实际测试发现成功率只有50%，所以更多的使用场景是：

进程首次运行时，开发者配置好要预调的页面
请求调页策略

缺页时才调

从何处调入页面：

磁盘中的对换区（采用连续分配方式来保证读写更快的区域）

但实际情况不同也有不同策略

对换区够大，万事大吉
对换区紧张：对于不会被修改的数据安置在文件区（因为后续不会再有modify的IO），对于可能被修改的部分，安置在对换区

策略优化 - - 抖动 / 颠簸

指：刚刚换出的页面马上又要换入，刚刚换入的页面马上又要换出

出现的主要原因是：给进程分配的物理块（驻留集）太少了

引理：如何确定进程应该拥有的驻留集数量？

测试，测试方法是：观察某个窗口尺寸下，工作集的大小

指：某个时间段内，实际使用了多少物理块

内存映射文件（Memory - Mapped Files）

通过在内存中声明一个和文件同等大小的空间，对此空间的修改只在必要时才装入对应文件

特点：

以访问内存的方式访问文件数据

和常规文件访问的主要区别是：没有全部的read操作和write操作，并且对于开发者而言无需关注read，write，就好像所有数据都在内存中一样。
可以实现文件共享

将文件映射到内存中后（并不属于任何一个进程的区域），多个进程都可以由页表将自身的虚拟地址空间和此MMF进行联系，以实现共享

文件管理

文件的属性：
1. 文件名
2. 标识符：一个系统内各文件标识符唯一，操作系统用于区分各个文件的一种内部名称
3. 类型
4. 位置：文件所在路径（逻辑地址），在磁盘中的地址（真实地址）
5. 大小
6. 创建时间、修改时间
7. 文件保护信息：将读、写、执行权分给不同的用户组
文件内部数据如何组织：

文件分类：
1. 无结构文件：纯粹的二进制流存储
2. 有结构文件：或许可以尝试用某种逻辑结构存储，空间越小越好
从需求出发考虑OS应该向上提供哪些功能
1. create 系统调用：表示创建文件
2. read
3. write
4. delete
5. open
6. close

文件的逻辑结构 & 物理结构

逻辑结构：指在用户看来，文件内部的数据是如何组织的。
物理结构：指在操作系统看来，文件发数据如何真实存放在磁盘

有结构文件的逻辑结构

对于无结构文件，没有太多技术压缩空间

有结构文件又称为“记录式文件”。根据各条记录的长度（占用的存储空间）是否相等，分为定长记录和可变长记录

对于可变长记录，真实存储方式就是类似InnoDB的B+树索引，在操作系统中叫做：索引顺序文件（index）

文件目录：

产生文件夹效果的手法：

在一个目录下的文件，首先对应一张目录控制块（一个二维表），刻画了每个子项的具体信息

对于文件而言，控制块直接指向文件真实地址，对于文件夹而言，控制块指向下一个文件控制块的地址

文件控制块（FCB）：

包含：

文件基本信息（文件名，物理地址，逻辑结构，物理结构）
存取控制信息（是否可读可写，访问用户白名单）
使用信息（文件的创建时间，修改时间）

问题：对于FCB的访问十分平常，但主要是访问文件名和引用地址两个字段，其余信息避免每次都加载到内存

方案：将Index文件中只存储文件名和路径信息，其余信息额外存储到索引节点中【冷热分离】

树形目录结构：

目录结构：

无环图目录结构：

原本树形结构可能存在问题：当不同路径下的文件相同，但也需要分别存储，无法共享

无环图试图将多个文件的引用指向同一个文件

文件的物理存储

核心完成：由逻辑地址（逻辑块号 + 块内地址）向真实地址（真实块号 + 块内地址）的转化

按照文件的分配方式划分：

连续分配

每个文件在磁盘上都占有一组连续的块

记录对应关系只需要在FCB中记录文件名，起始块号，长度

引理：

OS读取某个磁盘块时，需要移动磁头；当访问两个磁盘块相隔越远，移动磁头所需的时间越长

隐式链接

文件块之间通过链表形式存储

FCB中需要存储文件名，头节点块号
显示链接：

将用于链接文件物理块的指针信息显式的存储在另一张表中

FAT（File Allocation Table）

好处多多：
1. 只要将FAT预加载到内存，就可以避免链式查找导致的无法随机访问（只要沿着FAT走到对应位置即可）
2. 添加，删除的实现更是简单中的简单
索引分配：

允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录文件的各个逻辑块对应的物理块（metadata）

索引表存储在索引块中

将DFS中tracker内置到storage中一样

操作系统使用哪种存储方式，取决于选择的策略；策略取决于需求

文件存储空间管理

磁盘分区：

windows管理中，将整块磁盘分成C盘，D盘，E盘

每个盘中分成目录区和文件区

原本某个目录中可能有文件，也可能有目录，二者看似是交叉的；但是目录对子项的联系都是链表

即：逻辑上是树状结构层层分明，物理上也有结构用于管理
在某些场景下，多个物理磁盘可以组成一个文件卷

管理策略：

空闲表法：

维护一张表，记录磁盘中哪些块是空闲的

比较适合 “连续分配方式” – 空位也是连续的便于存储，再将空位添加连续数据也容易

考虑当回收磁盘时需要如何更新meta
空闲链表法：

分两种：空闲盘块链，空闲盘区链

考虑如何回收：
1. 将回收的盘块一次挂到链尾（可能导致链路太乱，磁头移动较慢）
2. 分前后有无空闲盘块
位示图法：

通过bit-map标记具体盘块有无占用
成组链接法：

每个组的头部标记了下一组中哪些是空白块的信息

设置一个超级块标记第一块的空白情况

分配空白块的方式就是沿着头部一个一个查看

文件的基本操作

创建文件：create
- 传入参数：文件大小（占用外存空间大小）、路径（外存的逻辑地址）、文件名（可能要对应一个uuid）
- 行为：
  1. 在外存中找到文件需要的空间【磁盘上确定哪些空间是被占用的，哪些块可用】
  2. 将实际占用哪些块记录在FAT中，或者其他元数据存储位置
  3. 将存放的路径尝试记录到目录文件中
打开文件：open
- 传入参数：路径+文件名
- 操作系统的打开和读取不同，打开就像是将元数据预加载，并且将用户对文件的权限先明确；
  
  即：read前的前置操作
  
  预加载到：打开文件表
读文件：read
- 传入参数：哪个文件、读取哪个位置的多少数据、读取到什么位置

文件系统的层次结构

OS in xiaolinCoding

内存管理：

单片机就是简单的单道操作系统
1. 相对于成熟的OS，没有内存地址转换
2. OS中内存地址转换就是将各自任务内的逻辑地址转化成真实的内存地址，根据所处时代背景分多种方式。早期类似单片机，逻辑就是物理；后期要执行多道任务，可以在装入程序时将逻辑修改位物理；在后期引入虚拟内存，要考虑页面/段/进程的调入调出，又有了动态逻辑地址转换
内存分段：

开发者将程序所在进程划分呈堆段、栈段、代码段、数据段
- 单纯的分段引发的问题：
  1. 划分粒度比较大，容易产生外部碎片
    
    解决碎片问题 - 整理 / 调出某个进程
    
    整理就像JVM中的老年代 major GC，为了避免多任务环境下并发的问题，通常会Stop The World，迫使其他任务阻塞
    
    调出某个程序：虽然后续的虚拟内存技术就是按照这个思路推进的，但粒度比较小，并且配合有更精妙的任务调出算法
内存分页：

把整个虚拟空间 / 物理空间切成一段段固定尺寸的大小
- 问题：
  
  虽然不会有外部碎片，但还有点点内部碎片，通常在程序最后一个页内
  
  内部碎片指：在一个页内没用到的空间
- 分页机制不仅是对内存碎片的优化，同时将分段机制加载的粒度降低，使得调入调出时更加灵活，更加快速，在与置换区调入调出页面能够做到”虚拟内存“，让用户感觉到更大的内存空间。而不是迫于空间不足强制让某个段下线。
- 问题：
  1. 分页为了灵活，灵活的成本是管理困难
    
    一页通常大小是4KB，虚拟地址空间可能有4GB，于是大约需要操作系统管理100万各页。每个页表至少要存储编号和对应物理地址，大概4字节，所以需4MB的内存用来存储页表
    
    一个进程有4MB，100各进程有400MB
    - 解决方案：
  2. 解决太大的问题：多级索引
  64位操作系统分四级目录
  1. 解决台难管理的问题：
  - 局部性原理
  - 快表（优化多级索引带来的额外时间消耗）
发展历程

早期Intel使用分段内存管理，后期用分页来优化分段（由=在分段内存管理上再添一层地址映射关系）

MyOS

https://13038032626.github.io/2024/05/17/MyOS/

Author

Ha_Ha_Wu

Posted on

May 17, 2024

Licensed under

MySQL Next

MyOS

my操作系统

什么是操作系统

操作系统的特征

并发：

共享：

虚拟：

异步：

操作系统的运行机制

中断和异常

系统调用

操作系统体系结构

操作系统引导（boot）

虚拟机

虚拟机管理程序

进程与线程

进程：是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程的状态切换

进程的创建

进程的组织

进程控制

进程通信（IPC）

共享存储：

消息传递：

管道通信：

线程：

线程的实现方式：

用户级线程（User-Level Thread）

内核级线程（Kernel-Level Thread）

多线程模型

线程的状态与转化

线程的组织与控制

处理机调度

进程切换（调度）的时机：

进程调度的方式：

进程的切换过程：

调度器 / 调度程序（scheduler）

闲逛进程：

调度算法的评价指标

调度算法

FCFS（先来先服务）

SJF（短作业优先 short job first）

SRTN

HRRN（高响应比优先 Highest Response Ratio Next）

RR（时间片轮转 Round-Robin）

优先级调度算法

多级反馈队列调度算法：

多级固定队列调度算法：

进程同步

进程互斥

进程互斥的实现方法（软件实现）

单标志法

双标志先检查法 / 双标志后检查法

Peterson算法

进程互斥的实现方法（硬件）

中断屏蔽方法

TestAndSet / TestAndSetLock TSL指令

锁

互斥方法8：原语+信号量

互斥方法9：原语+记录型信号量

互斥方法9：AND信号量：

管程

信号量机制实现进程同步

利用信号量解决文件读写锁

死锁

死锁的处理策略

SPOOLing技术：

动态策略：避免死锁

死锁的检测和解除

内存

虚拟内存

利用局部性原理可以设计调度算法和淘汰算法

请求分页存储管理

页面置换算法

策略优化 - - 局部置换

策略优化 - - 可变分配

策略优化 - - 何时调入页面

从何处调入页面：

策略优化 - - 抖动 / 颠簸

内存映射文件（Memory - Mapped Files）