操作系统笔记

[TOC]

参考资料

./2021王道操作系统.pdf
./操作系统.ppt
./2021王道操作系统.pdf
https://xiaolincoding.com/os/5_schedule/schedule.html 博客2.1、2.2、2.5、2.7、5.1、5.2、5.3，4.1
（王道考研）https://www.bilibili.com/video/BV1YE411D7nH
王道考研笔记：https://blog.csdn.net/weixin_43914604/article/details/104415990
核心知识点整理：https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/14.html

学习日期：2024年1月5日

学习大纲

概述
- 基本概念
  - 1.1.1 操作系统概念
  - ————— 操作系统特征
- 操作系统的运行环境
  - 1.3.1 操作系统运行机制
  - ————— 中断和异常
  - ————— 系统调用
进程管理
- 进程
  - 2.1.1 进程的概念和特征
  - ————— 进程的状态和转化
  - ————— 进程的控制
  - ————— 进程的组织
  - ————— 进程的通信
  - ————— 线程概念和多线程模型
- 处理机调度
  - 2.2.1 调度的概念
  - ————— 调度的时机、切换和过程
  - ————— 进程调度方式
  - ————— 调度的基本法则
  - ————— 典型的调度算法
- 同步
  - 2.3.1 进程同步的的基本概念
  - ————— 实现临界区互斥的基本方法
  - ————— 信号量
- 死锁
  - 2.4.1 死锁的概念
  - ————— 死锁的处理概念
  - ————— 死锁预防，避免，处理
内存管理
- 基本概念
  - 3.1.1 内存管理的基本原理和要求
  - ————— 覆盖和交换
  - ————— 连续分配管理方式
  - ————— 非连续分配管理方式
- 虚拟内存管理
  - 3.2.1 虚拟内存的基本概念
  - ————— 请求分页管理方式
  - ————— 页面配置算法

详细内容

操作系统

操作系统作为系统资源的管理者，提供的功能：处理机(CPU)管理、内存管理、文件管理、设备(显卡、摄像头)管理。

向上层（用户）提供方便易用的服务：GUI（图形操作界面）、联机命令接口=交互式命令行、脱机命令接口=批处理命令接口、程序接口（只能通过程序代码间接系统调用=广义指令）

并发、共享、虚拟、异步

并发（!=并行）：宏观上同时发生，微观上交替发生。并行取决于CPU有几核。

共享：资源共享——互斥共享、同时共享（微观上可能交替，也可能同时）

并发和共享互为前提，因为CPU资源的共享性是并发的前提

虚拟：虚拟存储器的空分复用，虚拟处理机的时分复用

异步：并发执行时由于系统资源有限，不是一贯到底，而是走走停停。（相对应的说串行）

内核程序+应用程序

内核（Kernel）：操作系统内核，最接近硬件的部分，最基础的部分。

Docker 容器在只有 Linux kernel 时就能用的

指令：分为特权指令，非特权指令 --> 对应两种状态：内核态和用户态（管态和目态） --> 两种程序：内核程序，应用程序 --> 通过CPU中的程序状态寄存器（PSW）区分。

内核态 --> 用户态：执行一条特权指令一一修改 PSW 的标志位为“用户态”，这个动作意味着操作系统将主动让出 CPU 使用权

用户态 --> 内核态：由**“中断”**“引发，硬件自动完成变态过程，触发中断号意味着操作系统将强行夺回 CPU 的使用权（程序完成中断，异常中断）

中断

内中断：与当前执行的指令有关，中断信号来源于CPU内部。指令非法或指令请求操作系统内核（陷入指令）用户态下应用程序主动交回CPU使用权。

外中断：时钟中断（时间片轮询，多线程并发），输入输出中断信号

一般中断指外中断，内中断称为异常

异常：陷入（trap），故障（fault），终止（abort）

中断机制的基本原理，中断处理依赖一个中断向量表。

系统调用

程序请求内核程序的服务，比库函数更底层的服务。为了更方便地对系统资源进行管理，程序只能通过系统调用请求系统资源，凡是对共享资源的访问必须用系统调用，防止非法操作。

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

进程

进程 = 进行中的程序；

最重要的功能是提供资源

如何区分一个程序的不同进程：PID

这些信息都被保存在一个数据结构 PCB（Process Control Block）中，即进程控制块操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中；

PCB内容：进程描述信息（PID；用户标识符UID），进程控制和管理信息，资源分配清单；处理机相关。

进程实体的组成：PCB --> 给操作系统的；程序段，数据段 --> 给自己用的；

每个进程是系统进行资源分配和调度的独立单位。

进程的特征：动态，并发，独立，异步，结构性（PCB）

进程的状态和转换

创建态(分配资源和PCB) --> 就绪态(等待处理机资源) --> 运行态 --> 阻塞态(主动请求等待某个时间的发生，但是不回收除了处理机资源外的系统资源) / 终止态(回收系统资源和PCB)

精简理解: 阻塞的发生是系统资源没准备好

进程的组织

将处于同一状态的不同进程的PCB有规律地组织起来，方便同一管理。

两种组织方式：

链式方式：执行指针，就绪队列指针，阻塞队列指针
索引方式：执行执政，就绪索引表，阻塞索引表（很少操作系统使用）

进程控制

进程控制实现进程的管理和状态转换，使用原语（不被中断的原子性指令）实现。

创建原语 --> 进程的创建
- 申请空白PCB / 分配系统资源 / 初始化PCB / 插入就绪队列
- 在用户登录 / 作业调度(多道批处理命令下有新作业加入内存时) / 用户向操作系统提出服务 / 应用请求创建子进程时
撤销原语 --> 进程的终止
- 找到PCB / 剥夺CPU / 终止子进程 / 归还系统资源(给父进程或者操作系统) / 删除PCB
- 正常结束 / 异常结束 / 外界干预
阻塞原语/唤醒原语 --> 进程请求wait和被唤醒，控制阻塞态<-->就绪态
- 原进程运行环境需要被保护
- 成对出现，由什么阻塞就必须由什么唤醒
切换原语 --> 控制运行态 <--> 就绪态，控制两个进程进出CPU（进程切换）
- 常见的是时间片轮询并发设计
- 需要对原进程的运行环境保存（一堆寄存器）
- 保存在PCB中

进程通信 IPC

操作系统的支持：因为各个进程的内存地址空间是不可以相互访问的。

方式；

共享存储：字面意思，申请一个共享内存，映射到自己的虚拟地址空间，保证各个进程的访问是互斥的。
- 基于共享存储区，共享方便，灵活性高，高级通信方式。
- 基于数据结构的共享，低级通信方式。
消息传递：格式化消息为单位（massage）传输
- 直接通信：需要PID，直接发给指定进程的PCB的消息队列。
- 间接通信：需要一个信箱的实体（信箱通信），需要接受的进程申请一个信箱，只能直接发给信箱，而不是发给进程。
- 一般系统允许多个进程从一个信箱读取消息，也允许多个进程向一个信箱发消息。
管道通信：通过一个队列管道（pipe）一对一队列通信
- 只能是单向的，速度非常快。
- pipe是一个大小固定的内存缓冲区（理解类似FIFO寄存器+循环队列）
- 一个管道只能通过半双工通信，全双工需要两个管道文件。
- 各个进程是互斥访问管道的，空 --> 阻塞read / 满 --> 阻塞write
- 管道读完即消失，不同的操作系统的实现方式，可以被允许多个写进程，多个读进程（Linux的轮流读pipe操作）

同主机的进程之间的通信: 借用操作系统作为媒介给不同的进程通信

线程

线程就是单个软件内的多进程并发。在引入线程之后，线程是操作系统的程序执行流的最小单位。提高了系统的并发性。

单个进程的不同线程在运行时共享进程运行环境，所以线程几乎不拥有系统资源。

线程运行环境直接依赖进程，减少了线程切换时的系统资源开销，进程内部的线程通信也不需要系统调用参与。

线程也有TCB，ready-wait-running 三种基本状态。

线程实现

用户级线程ULT（古早时期的线程实现方式）：
- 操作系统只能支持进程，程序在内部写线程库自主完成，线程实现全是软件完成的，不需要CPU变态的开销。
- 无法独立完成阻塞-就绪-运行三态切换，只能和进程一起切换状态，并发度不高。
- 无法多核并发。
内核级线程KLT：
- 这个时候的线程的实现基本和进程一样。
- 多线程不会互相因为阻塞相互影响
- CPU的开销大

多线程模型

基本是 ULT + KLT ：一对一（退化为KLT）；多对一（退化为ULT）；多对多（更灵活）

用户级线程是“代码逻辑”的载体，内核级线程是“运行机会”的载体

处理机调度

就是对系统资源按特定规则的安排。

调度的三个层次：

高级调度：作业调度（task）
- 依据后备作业队列
- 从作业后备队列中调用一个作业建立PCB，每个作业只能调入一次，调出一次
- 无进程 --> 创建态 --> 就绪态
低级调度：进程调度/处理机调度
- 依据CPU资源
- 频率很高
- 就绪态 --> 运行态
中级调度（程序的挂起，内存调度）
- 依据内存资源
- 挂起：将进程加入挂起队列，将数据全部调到外存。
  
  挂起 <--> 激活，挂起阻塞和挂起就绪其实就是在外存中的阻塞和就绪，挂起的依据是内存资源调度。
  
  挂起的进程无法直接进入运行态，必须激活才可以，但是挂起的进程可以在就绪和阻塞之间转换
- 挂起态 --> 激活态

进程调度时机

时机：

主动放弃：正常终止，请求阻塞，发生异常（内中断）
被动放弃：时间片结束，外中断，更有优先级的进程进入就绪队列
不能进行：中断处理，进程在操作系统内核程序的临界区，原语操作

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区：访问临界资源的那段代码，会将临界资源上锁拒绝其他进程访问，需要尽快处理。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）

因为进程调度是需要操作系统内核程序的临界资源，所以在操作系统内核临界区的代码无法进行调度。

普通的临界区无所谓，比如一般的摄像头，打印机这类的临界资源，直接阻塞就行，避免占用CPU又不做事。

进程调度方式

非剥夺调度方式（非抢占式）：早期，开销小

剥夺调度方式（抢占式）：分时操作系统，时间片轮询，可以处理更紧急的任务。

进程的切换与过程

“狭义的进程调度”与“进程切换”的区别：

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。进程切换的过程主要完成了：

对原来运行进程各种数据的保存
对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

调度算法的评级指标

CPU 利用率：忙碌时间/总时间
系统吞吐量：总完成多少作业/总时间
周转时间：作业被提交给系统开始，作业完成为止的时间
平均周转时间：周转时间/作业总数
带权周转时间：作业周转时间/作业实际运行时间 (鼓励等待时间长但运行时间短的先运行)
平均带权周转时间：带权周转时间/作业总数

等待时间：

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后各队列中等待的时间。

响应时间：

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。响应时间，指从用户提交请求到首次产生响应所用的时间。

调度算法——早期简单的非交互式

先来先服务（FCFS）
短作业优先（SJF）
高响应比优先（HRRN）

饥饿：指某一个作业/进程长时间得不到服务

响应比=(等待时间+要求服务时间)/要求服务时间 ≥ 1 (运行时间相同时鼓励带权周转时间高的先服务)

算法	先来先服务（FCFS）	短作业优先（SJF）	高响应比优先（HRRN）
算法思想	“公平”的角度，先到先得的队列思想	追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间	要综合考虑作业/进程的等待时间和要求服务的时间
算法规则	按照作业/进程到达的先后顺序进行服务	最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）	在每次调度时先计算响应比，选择响应比最高的为其服务;
用于作业调度	哪个作业先到达后备队	已经到达的最短的作业优先得到服务	\
用于进度调度	哪个进程先到达就绪队列	用于进程调度时称为“短进程优先 (SPF, Shortest Process First) 算法”	\
是否可抢占	非抢占式算法	SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本一一最短剩余时间优先算法（ SRTN, Shortest Remaining Time Next)	非抢占式
优点	公平，简单	在所有进程都几乎同时到达时，采用 SJF 调度算法的平均等待时间、平均周转时间最少	- 综合考虑了等待时间和运行时间（要求服务时间）; - 等待时间相同时，要求服务时间短的优先 (SJF的优点）; - 要求服务时间相同时，等待时间长的优先（FCFS的优点）; - 对于长作业，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥的问题
缺点	某些作业、进程带权周转时间有可能非常高	不公平。短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先	\
饥饿	不会导致饥饿	有可能导致长作业饥饿	不会没有饥饿

最短剩余时间优先算法（ SRTN, Shortest Remaining Time Next)

就绪队列改变，新就绪进程到达时，比较就绪进程的运行时间和当前进程的剩余时间，后按照最短剩余时间优先调度。

抢占式的短作业／进程优先调度算法（最短剩余时间优先， SRNT 算法）的平均等待时间、平均周转时间最少

注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS 算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

交互式系统的调度算法

时间片轮转调度算法(RR)
优先级调度
多级反馈队列调度

算法	时间片轮转调度算法(RR)	优先级调度
算法思想	公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应随着CPU新能的提升和分时操作系统的出现而产生的, 更考虑用户体验(系统响应时间)而不是操作系统的开销和性能	随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则	按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片 (如 100mS)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排。时间片的长短是可变的默认新到达的进程先进入就绪队列	每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
是否抢占式	由时间片引发中断抢夺	非抢占式的调度算法和抢占式的都有当就绪队列发生改变时会发生抢占
用于作业/进程调度	用于进程调动, 因为进程是程序执行的最小单位	既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的调度中
优点/缺点	用户体验好 (响应速度快) 不区分任务的紧急程度如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。(时间片切换开销不能超过总开销的1%)	用户体验好对CPU资源开销大
饥饿	不存在饥饿	低优先级的会饥饿

有关优先级调度算法的补充:

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置 (优先队列)

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时确定，之后一直不变。

动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

通常：

系统进程优先级高于用户进程

前台进程优先级高于后台进程

操作系统更偏好 I/O 型进程而不是计算型进程

(I/O繁忙型进程 <--> CPU繁忙型进程)

因为 I/O 设备可以和 CPU 并行, 所以 I/O 型进程早点触发 I/O 设备繁忙可以提高系统资源使用率, 提高性能

动态优先级的策略

可以从追求公平、提升资源利用率等角度考虑

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

如果某进程占用处理机运行了很长时间，则可适当降低其优先级

HRRN 算法就是一个简单的动态优先算法

多级反馈队列算法

一种权衡各种算法的比较适合的算法

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时己经在最下级的队列，则重新放回最下级队列队尾
只有第 k 级队列为空时，才会为 k+l 级队头的进程分配时间片
被抢占处理机的进程重新放回原队列队尾 (只有优先级抢占)

优点:

对各个进程相对公平 (FCFS)
响应时间短 (RR)
短进程只需要很少的时间就可以完成 (SPF)
不必估计进程的运行时间 (防止用户作假)
可以灵活的调整对各种类型的进程的友好程度 (是否调整至下一个队列)
可能导致饥饿 (SPF导致的)

多级优先级队列调度

根据不同的进程类型分为不同优先级的队列

P1 = 系统进程; P2 = 交互式进程/IO进程; P3 = 批处理进程 (后台模型渲染)

优先策略:

固定优先级: 高优先级先调用完才能调用低优先级
时间片划分: 依次时间片长度为 5:4:1 来分配时间片

对于不同的优先级队列内部采用不同的调度策略:

系统进程采用优先级调度
交互式采用 RR
批出理队列采用 FCFS

进程同步和互斥

进程具有异步性, 并发执行的进程推进顺序不可预知, 但是某些指令的推进顺序需要确定, 比如 pipe 写数据和读数据是并发执行的, 但是写数据必须要在读数据之前才正确

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

对临界资源的互斥访问导致进程互斥 (间接制约关系)

// 代码逻辑
do{
	entry section;		// 进入区: 上锁
	critical section;	// 临界区: 操作临界资源
	exit section;		// 退出区: 解锁
	remainder section;	// 剩余区: 处理后事
}while(true);

进程互斥的原则

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

进程互斥的软件实现方法

下面使用标志的方法: token 令牌 (互斥量) <--> semaphore 信号量 (并发量)

单标志法

// P0
while(turn !=0); // 进入区
critical section;
turn = 1;
remainder section;

// P1
while(turn != 1);
critical section;
turn = 0;
remainder section

采用谦让的方式, 各个进程都只能轮流使用, 违反空闲让进的原则

多标志法

// P0
while(flag[1]||...);	// 等待其他进程使用完成
flag[0] = true;		// 表达意愿进入上锁
critical section;
flag[0] = false;	// 推出
remainder section;

//P1
while(flag[0]||...);
flag[1] = true;
critical section;
flag[1] = false;
remainder section;

要求检查和上锁的连续性, 但是有可能在并发时进程切换时破坏连续性, 违背忙则等待

双标志后检查法 (就是先上锁后检查) 解决忙则等待问题, 违背闲则让进和有限等待原则

Peterson算法

bool flag[2]; // 表达意愿
int turn=0;	// 表达谦让

// P0
flag[0]=true; 
turn=1;
while(flag[1] && turn==1);
critical section;
flag[0] =false;
remainder section;

// P1
flag[1]=true;
turn=0;
while(flag[0] && turn == 0);
critical section;
flag[1] = false;
remainder section

没有实现让权等待原则: 自己不需要临界资源的时候还是在那一直while循环不让出CPU资源

进程互斥的软件实现方法

中断屏蔽

类似原语的思想, 简单高效, 但是不适合多核处理机, 并且关中断是特权指令, 只有系统进程才可以使用

TestAndSet 指令 (TSL/TSLR)

利用硬件保证执行的过程一步到位, 实现起来很简单, 没有异步的逻辑漏洞, 但是不满足让权等待的原则, 可在多核处理机上使用

Swap指令(Exchange/XCHC)

和TSL的指令逻辑上是一致的, 都是检查 old 记录是否被上锁, 再将 lock 设置为 true 然后检查临界区是否被上锁

互斥锁
acquire(){ // 请求
	while(available);		// 自旋忙等待
		available = false;	// 上锁
}
release(){ // 结束
	available = true; 	// 解锁
}
特性:

忙等待, 违反让权等待原则

等待期间不需要切换进程上下文, 多核处理系统中如果上锁时间短, 则等待代价很低

常用于多核处理器, 一个核忙等, 其他核照常工作并释放临界资源

不适用单核, 等待过程中临界资源不会释放

信号量

整型信号量
记录型信号量

信号量是一种变量: 表示系统中临界资源的量, 分为整型和记录型

信号量关乎两个原语操作 P(S)-->wait(S) 和 V(S)-->Signal(S)

// 整型信号量

int S = 1; 

void P(int S){
	while(S <= 0);
    S = S-1;
} // 原语操作

void V(int S){
    S = S+1;
} // 原语操作

没有并发异步的问题, 但是有让权等待的问题

// 记录型信号量
typedef struct {
	int value;
    struct process *L; // 阻塞等待队列
}semaphore;

semaphore S; // init S.value = 资源数量, S.L = null

void P(semaphore S){
    S.value--;		// 系统剩余资源-1
    if(S.value<=0)	// 系统没有剩余资源
        block(S.L); // 阻塞进程加入等待序列
}

void V(semaphore S){
    S.value++;		// 系统剩余资源+1
    if(S.value<=0)	// 等待队列中还有进程
        wakeup(S.L); // 唤醒一个阻塞进程加入就绪队列
}

阻塞的存在保证不会出现忙等待的情况

信号量完成进程同步

对不同的临界资源设置互斥信号量 mutex 实现进程互斥

通过同步信号量实现进程同步: 即只有某个特定操作完成之后才能继续另一个操作

semaphore S = 0; // 表示一开始没有这个资源

P0(){
    code 1;
    code 2; // 生产资源
    V(S);	// 释放信号唤醒消费者进程
    code 3;
}

P0{
    code 4;
    P(S); // 等待资源
    code 5; // 消费资源
    code 6;
}

前V后P

异步通知

同步通知: 自己轮询;

异步通知: 等别人通知;

管程

引入管程的目的无非就是要更方便地实现进程互斥和同步。

需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
需要在管程中定义用于访问这些共享数据的“入口”一一其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）
只有通过这些特定的“入口”才能访问共享数据
管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥性是由编器实现的，程序员不用关心）
可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口'）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    
    // synchronized 关键字保证每次只有一个进程可以调用这个函数
    public synchronized void insert ( Item item ){
        ...
    }
    
    public synchronized void remove ( Item item ){
        ...
    }
}

死锁

两辆车相向相遇

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源的现象，导致各个进程都阻塞, 都无法向前推荐, 就是“死锁”, 发生死锁后若无外力干涉，这些进程都将无法向前推进。

死锁产生的必要条件: (指不满足其中一个就可以解除死锁)

互斥条件: 有互斥的临界资源
不剥夺条件: 资源只能进程主动释放, 不能其他进程强行剥夺
请求和保持条件: 进程至少保持了一个资源且正在请求其他资源
循环等待: 存在一个资源的循环等待链, 链中每一个进程请求的资源都被下一个进程占有

发生死锁的情况: 对不可剥夺的资源的额分配不合理的时候

死锁处理的策略

预防死锁 (静态策略) 破坏必要条件
- 互斥条件: SPOOLing 技术将互斥的资源在逻辑上改造为共享设备。但是不是所有的独占资源都可以被改造，一部分系统核心资源为了安全也是必须保证互斥独占。
- 不剥夺条件：进程主动释放或者系统协助剥夺。
  - 实现起来比较复杂，考虑优先级策略
  - 为了避免中途剥夺导致的工作进度失效，还需要保存原来的工作，一部分资源也没有办法保存工作进度，会导致进程饥饿。
  - 不断剥夺申请也会导致系统开销过大
- 请求和保持条件：采用静态分配策略，必须所有的资源一次性申请完才能一起占用。
  - 如果进程运行期间一致保存所有资源，会造成严重资源浪费
  - 会导致进程饥饿，因为同时所有资源都空闲的概率很小
- 循环等待：顺序资源分配法。申请资源的顺序按从小到大的编号来，同编号的必须一次性申请完。
  - 保证只有拥有小编号的进程才能申请大编号，这样的单向链不可能成环
  - 对系统编号的分配很麻烦
  - 申请资源的顺序和实际使用的顺序不可能一直一样，往往会导致资源浪费
  - 对用户编程非常麻烦
避免死锁 （动态策略）--> 银行家算法
- 安全序列; 安全状态; 不安全状态
  - 死锁一定发生在不安全状态, 但是不安全状态不一定会导致死锁
- 假设一共 n 个进程, 系统有 m 个资源
  
  矩阵 Max[n,m] 表示进程需要的最大需求资源(这些都是进程自己提前申请的)
  
  矩阵 Allocation[n,m] 表示进程已经分配的资源状况
  
  矩阵 Need[n,m] 表示进程最多还需要的资源状况
  
  向量 Available[m] 表示剩余资源状况
  
  进程传递向量 Request_k[m] 表示第k个进程申请需要的资源
- 只有当分配资源后系统还处于安全状态时 (至少能找到一个安全序列时), 系统才会允许分配资源, 否则拒绝, 让进程阻塞等待
- 银行家算法步骤：
  - 检查此次申请是否超过了之前声明的最大需求数
  - 检查此时系统剩余的可用资源是否还能满足这次请求
  - 尝试分配策略，更改各数据结构
  - 用安全性算法检查此次分配是否会导致系统进入不安全状态
检测和解除死锁
- 利用资源分配图来完成
  - 资源分配图是一个包含进程节点和资源节点的有向图
  - 进程节点 --> 资源节点 == 请求边
  - 资源节点 --> 进程节点 == 分配边
- 死锁定理: 如果某时刻系统的资源分配图是不可完全简化的, 那么此时系统死锁
- 简化图: 找一个非孤立的非阻塞进程 P, 消除所有边, 循环此过程, 直到所有节点都成为孤点, 则图可简化。(如何判断阻塞: 阻塞表或者直接计算就行)
- 数据结构: G[n*m]: 表示 n 个进程节点和 m 个资源节点, 其中 G[i,j] > 0 表示P_i 向 R_j 申请的资源量, G[i,j] < 0 表示 R_j 向 P_i 申请的资源量
- 处理策略:
  - 资源剥夺: 对部分死锁资源强制挂起并且剥夺资源, 但是要防止挂起资源饥饿
  - 进程终止: 都杀了就没问题了, 就是后果惨烈自负
  - 进程回退: 回退到没有死锁的还原点, 需要系统记录进程的历史信息
  - 对谁动手:
    1. 进程优先级
    2. 己执行多长时间
    3. 还要多久能完成
    4. 进程己经使用了多少资源
    5. 进程交互式的还是批处理式

内存管理

内存空间扩展
地址切换 (物理地址-->逻辑地址)
- 绝对装入：固定地址（早期单道）
- 可重定位装入：装入程序负责地址转换（早期多道批处理阶段）
- 运行时装入：运行时才进行地址转换（现代操作系统）
内存保护
- 重定位寄存器+界地址寄存器
- 上下限寄存器

内存空间扩展

虚拟存储技术
覆盖技术(早期操作系统)
- 将程序分为多个段/模块, 常用的段/放在固定区, 其他不常用的放在覆盖区
- 必须由程序员声明覆盖结构，操作系统完成自动覆盖。
- 缺点：对用户不透明，增加了用户编程负担
交换技术(内存调度): 就是把进程直接调到外存

内存空间的分配与回收

连续分配

单一连续分配: 将内存分为系统区和用户区, 系统区常用于内存的低地址部分, 内存中只有一个用户程序, 可以不用内存保护, 有内存分配。

固定分区分配: 分区大小相等, 对内存的利用率不高, 并且没有灵活性, 只有在特殊固定场景下会很好用。分区大小不等: 一个固定分区表, 不会产生外部碎片, 但是依旧会有内部分区。

动态分区分配: 根据进程的大小动态建立分区

应该用什么数据结构 --> 空闲分区表和空闲分区链
新的进程进入哪个空闲分区;
如何进行分区的分配和回收, 链表操作;

动态分区分配没有内部碎片，但是有外部碎片。

内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。

外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

动态分区分配算法

首次适应: 依次查找直到找到
最佳适应: 优先使用最小的空闲分区 --> 会产生很多外部碎片
最坏适应: 优先使用最大的空闲分区 --> 减少外部碎片, 但是对大进程的适应降低
临近适应算法: 首次适应算法 + 上次邻近查找, 循环列表降低查找开销, 但是浪费高地址的大空闲分区

内存的实际分配

分页存储: 将内存空间分为固定大小的页框/页帧/内存块/物理块/物理页面

将进程按照页框大小细分为若干页面, 然后载入不同页框中

在 PCB 中记录一个页表(线性表), 页号隐含在偏移量中, 页框的物理地址字长需要自己计算

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。

分页与分段的比较（重点）

分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

页的大小不可变，段的大小可以动态改变

分页产生内部碎片，分段产生外部碎片

二级页表和 TLB快表

假设一个有 100万 页的进程

由于页表是通过线性表维护的，所以基本页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表

简单来说就是将一部分常用的二级页表扔到 CPU 里的 L1 cache L2 cache (L3 cache 是共享的)

虚拟内存

传统要求所有作业装入内存的一次性和驻留性, 导致内存资源的浪费, 根据局部性原理提出虚拟内存技术

时间局部性: 由于循环的存在, 某条指令可能再次循环。

空间局部性: 一些变量和周围的变量可能是连续的, 以及连续储存的数据结构, 连续存放的指令, 带来的空间上的局部性更容易访问。

虚拟内存可以多次调用和多次数据交换。

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

于是，这里就引出了两种地址的概念：

我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）

请求分页管理方式

页表机制(区别于基本页表)
- 状态位, 访问字段 (最近访问过几次或者上次访问的时间, 用于页面调换选择参考, 修改位, 外存地址)
缺页中断: 当进程的页不在内存中时, 触发缺页中断(内中断/故障), 请求调页, 并且缺页进程阻塞, 调页成功后就绪
- 请求调页 --> 是否有空闲内存块, 没有则触发页面调换机制

页面置换算法

OPT 最佳置换算法:

淘汰永不使用的页面/长时间不再被使用的页面; 理想化的算法, 实际无法使用
FIFO 先进先出:

每次悬着淘汰的页面是最早进入内存的页面; 可能会产生 Belady 异常, 当为进程分配的物理块增加时, 缺页次数不减反增
LRU 最近最久未使用

依靠访问字段的信息来参考, 或者直接逆向扫描, 看最远的页面是哪个就置换, 依赖硬件实现, 虽然很接近 OPT 算法, 但是硬件开销比较大

双向链表(便于维护和插入) + Hash表维护Node
CLOCK 时钟置换算法/NRU 最近未使用算法

给每个页面设置一个访问位, 1表示被访问过, 0表示没被访问过, 将访问位加入循环列表; 请求页面调换时触发扫描, 扫过的访问位置零, 扫到零位便调换
- 改进过的 CLOCK 算法
因为页面调换和页面覆盖的 I/O 开销不同, 设置一个修改位, 优先淘汰修改位为 0 的页面, 步骤如下:
1. 扫描未被访问且未被修改的页面 (这个时候不对访问位做任何修改) --> 淘汰(0,0)
2. 扫描未被访问但是被修改过的页面, 扫过的访问位置零, 扫到零位便调换 --> 淘汰(0,1)
3. 循环

页面配置算法

驻留集：指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

分配策略:

\	局部置换	全局置换
固定分配	最死板	*
可变分配	根据缺页率动态调度	空闲物理块 + 其他未锁定物理块

何时调入页面:

预调页策略: 根据局部性原理, 一般用于运行前首次调入
请求调入策略: 运行中用的策略

从何处调入:

外存的对换区的使用策略: 在对换区空间缺少时, 依照读写频率和是否第一次调入

抖动(颠簸)现象:

由于进程需要频繁访问的内存块数量多余可用的内存块数量, 导致进程的部分页面频繁换入换出。I/O 开销变大。

工作集: 指在某段时间间隔(时间窗口尺寸)里，进程实际访问页面的集合。作为分配驻留集的参考, 避免抖动。

如果觉得文章对你有用，请随意赞赏

操作系统学习笔记

https://blog.mydawn.space/archives/cb967901-cace-4397-bece-f1853aaa1ba5

作者

艾若Dawn

发布于

2024-06-09

更新于

2024-06-06

许可协议

CC BY 4.0

操作系统学习笔记

操作系统笔记

参考资料

学习大纲

详细内容

操作系统

并发、共享、虚拟、异步

内核程序+应用程序

中断

系统调用

进程

进程的状态和转换

进程的组织

进程控制

进程通信 IPC

线程

线程实现

多线程模型

处理机调度

进程调度时机

进程调度方式

进程的切换与过程

调度算法的评级指标

调度算法——早期简单的非交互式

交互式系统的调度算法

多级反馈队列算法

多级优先级队列调度

进程同步和互斥

进程互斥的软件实现方法

进程互斥的软件实现方法

信号量

信号量完成进程同步

异步通知

管程

死锁

死锁处理的策略

内存管理

内存空间扩展

内存空间的分配与回收

内存的实际分配

二级页表 和 TLB快表

虚拟内存

请求分页管理方式

页面置换算法

页面配置算法

作者

发布于

更新于

许可协议

评论

二级页表和 TLB快表