操作系统-复习笔记-24春
软小宣（大作业的玩物版）
前言：操作系统是一门好课……期末占比低，只要完成好大作业就行，期末考试大致复习一下，然后拟合一下作业题和往年题。
本次复习笔记按照课程介绍、知识点大纲式复习、重点算法考点研究、题型速览来进行讲解。
题型：5单选、5填空、3简答、3应用
总而言之：Petri ！！
[toc]
课程介绍
-
考核方式：大作业
50%、随堂抽测课后作业10%、期末考试40% -
通讯录：
闻立杰 清华大学东配楼11区405 13681026629 wenlj@tsinghua.edu.cn
孟诗奥 清华大学东配楼11区401 15937308719 msa21@mails.tsinghua.edu.cn
马福崑 清华大学东配楼11区401 13051339001 thss15_mafk@163.com
-
课程大纲：
-
第一章-操作系统概述
-
第二章-进程管理+\(Petri\)网
进程管理、处理器调度与进程间通信、死锁、PN_CPN
-
第三章-存储管理
-
第四章-设备管理
-
第五章-文件系统
知识点大纲式复习
第一章：操作系统概述
大概会提及：计算机和计算机系统的基本概念和组成、计算机技术的发展、OS的定义作用组成和分类、一些OS相关的基本概念。
第一章能考啥呢？感觉最多到一个填空吧（sigh）
-
电子数字计算机：种能够自行按照已设定的程序进行数据处理的电子设备，是软件与硬件相结合、面向系统、侧重应用的自动化求解工具。
-
计算机系统组成：硬件子系统
CPU（==运算、控制、存储==）、主存储器、I/O控制系统、外围设备和软件子系统系统软件、支撑软件和应用软件
关键的系统软件：==操作系统和语言处理程序==
- 计算机技术的发展：
- 没有操作系统时期，一次完成一个功能。
- 串行的单通道批处理。CPU和I/O设备忙闲不均。
- 多通道批处理（现代意义的操作系统）。宏观上并行，微观上串行。等待I/O时可以使用CPU。
- 分时系统。多个用户通过终端分享一台计算机。CTSS、MULTICS、UNIX
-
现代操作系统：受保护指令、系统调用、内存保护、中断、I/O、时钟
-
操作系统（OS）
定义：OS是计算机系统最基础的系统软件，管理软硬件资源、控制程序执行、改善人机界面、合理组织计算机工作流程，为用户使用计算机提供良好的运行环境。
作用：操作系统是方便==用户管理==和==控制计算机软硬件资源==的系统程序集合，在整个计算机系统中具有承上启下的地位。管理计算机系统的各种资源、用户与机器的接口、大型软件系统。
组成：进程调度子系统、进程通信子系统、内存管理子系统、设备管理子系统、文件管理子系统、网络通信子系统
类型：多道批处理操作系统，脱机控制方式；分时操作系统，交互式控制方式；实时操作系统，即时响应方式
接口：操作接口——系统程序；两类作业级接口——脱机作业控制方式作业控制语言
、联机作业控制方式操作控制命令；程序接口——操作系统为程序运行扩充的编程接口
-
OS的其他深入性概念
-
驱动程序：最底层的、直接控制和监视各类硬件(或文件)资源的部分。
职责是屏蔽或隐藏底层硬件的具体细节，并向其他部分提供一个抽象的、通用的接口 -
资源共享的方式：独占、并发
-
资源分配策略：静态分配、动态分配、资源抢占
-
多道程序设计（指让多个程序同时进入计算机的主存储器运算）
特点：CPU与外部设备充分并行、外部设备之间充分并行、发挥CPU的使用效率、提高单位时间的算题量、单道程序的运算时间会增加
利用==进程==来实现，OS能管理各类资源在进程间的使用。实现要点：
调用操作系统提供的服务例程来使用资源，调用程序来复用CPU，用设备控制器与通道来使CPU和I/O设备充分并行，用中断来让正在运行的程序让出CPU -
OS规定了合理操作计算机的工作流程
-
系统调用：操作系统实现的完成某种特定功能的过程，为所有运行程序提供访问操作系统的接口
实现细节：陷入处理机制
计算机系统中控制和实现系统调用的机制；陷入指令也称访管指令或异常中断指令，计算机系统为实现系统调用而引起处理器中断的指令；每个系统调用事先规定了编号，并在约定寄存器中规定了传递给内部处理程序的参数实现要点：处理程序、入口地址表、现场保护区
第二章：进程管理
第二章的目录为：2.1 处理器；2.2 中断处理；2.3 进程管理；2.4 线程管理；2.5 处理器调度；2.6 进程间通信；2.7 死锁。
第二章算是操作系统的大头之一（真正的主人还是PETRI），在课上讲了三个PPT来阐释，我们将分节来进行快速回顾
2.1 处理器
-
控制与状态寄存器：用于控制处理器的操作，主要被具有特权的操作系统程序使用，以控制程序的执行
程序计数器PC、指令寄存器IR、条件码CC、标志位 -
程序状态字PSW：OS的概念，值记录当前程序运行的动态信息
程序计数器、中断字；也是计算机系统的寄存器 -
通用寄存器（8类，4个数据寄存器、4个指针寄存器及变址寄存器）
-
段寄存器（4个：CS
代码段寄存器、DS数据段寄存器、SS堆栈段寄存器、ES附加段寄存器） -
指令指针IP：指令指针IP是一个16位专用寄存器。（P指向的是指令地址的段内地址偏移量，又称偏移地址(Offset Address)或有效地址(EA，Effective Address)）
-
标志寄存器FR：在FR中有意义的有9位，其中6位是状态位，3位是控制位。
-
机器指令：是计算机系统执行的基本命令，是中央处理器执行的基本单位。由一个或多个字节组成
操作码字段、多个操作数地址、状态字和特征码。完成各种算术逻辑运算、数据传输、控制流跳转。 -
指令执行过程：取指
根据PC从存储器或高速缓冲存储器中取指令到IR、译码解译IR中的指令来决定其执行行为、执行连接到CPU部件，执行运算，产生结果并写回，同时在CC里设置运算结论标志；跳转指令操作PC，其他指令递增PC值
取指周期&执行周期
-
特权指令：只能被操作系统内核使用的指令（I/O指令、置PC指令）
-
处理器模式：内核模式（0模式
OS内核）、用户模式（3模式用户程序等保护级别）
模式切换：中断、异常或系统异常等事件导致用户程序向OS内核切换，触发用户模式→内核模式；OS内核处理完成后，调用中断返回指令（如Intel的iret）触发内核模式→用户模式
2.2 中断管理
- 中断的概念：暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。
OS是==中断驱动==的，中断是激活操作系统的唯一方式。
- 狭义的中断：处理器外的中断事件，即雨当前运行指令无关的中断事件
I/O中断、时钟中断、外部信号中断。
异常：运行指令引起的中断事件地址异常、算术异常、处理器硬件故障等
系统异常：指执行陷入指令而触发系统调用引起的中断事件请求设备、请求I/O、创建进程等
-
几类中断源：
-
硬件故障：由处理器、内存储器、总线等硬件故障引起的中断事件
保护现场、停止设备、停止CPU、报告等待人工
-
程序性：处理器执行机器指令引起的中断事件
算数异常简单处理报告用户、非法指令or存取等指令异常终止进程、虚拟地址异常调整内存重新执行
-
自愿性：处理器执行陷入指令请求OS服务引起的中断事件，又称作系统调用
请求分配外设、请求I/O陷入OS、保护现场、查入口地址、跳转处理程序
-
I/O：来源于外围设备，用于报告I/O状态的中断事件
I/O完成则调整进程状态、释放阻塞、加入就绪进程；I/O出错or异常等待人工
-
外部：由外围设备发出的信号引起的中断事件
-
中断系统：是计算机系统中响应和处理中断的系统，包括硬件子系统
中断响应和软件子系统中断处理两部分 -
中断装置：是计算机系统中发现并响应中断/异常的硬件装置
处理器外的中断：由中断控制器发现和响应
处理器内的异常：由指令的控制逻辑和实现线路发现和响应，相应机制称为==陷阱==
请求OS服务的系统异常：处理器执行陷入指令时直接触发，相应机制称为==系统陷阱==
- 中断控制器：是CPU中的一个控制部件，包括中断控制逻辑线路和中断寄存器
-
陷阱与系统陷阱：是指令的控制逻辑与实现线路的一部分
-
中断响应过程：1. 发现中断源，触发中断请求 2. 中断当前程序的执行 3. 转向操作系统的中断处理程序
- 中断屏蔽：当检测到中断时，中断装置通过中断屏蔽位决定是否响应已发生的中断（有选择的响应中断）
- 中断优先级：即中断装置响应中断顺序的
- 中断的嵌套处理：当响应中断后在处理中断的过程中还可以再响应其他中断。（有硬件需求，有限定层数）（嵌套可能改变处理次序，可能先响应后处理）
- 多中断的响应及处理原则：中断屏蔽可以使中断装置不响应某些中断；中断优先级决定了中断装置响应中断的次序；中断可以嵌套处理，但嵌套层数应有限制；中断的嵌套处理改变了中断处理的次序
2.3 进程管理
-
进程的概念：是具有一定独立功能的程序关于某个数据集合的一次运行活动。是操作系统进行资源分配和CPU调度的一个独立单位
-
进程的具体定义（包含以下实体部分）：(OS管理运行程序的)数据结构P；(运行程序的)内存代码C；(运行程序的)内存数据D；(运行程序的)通用寄存器信息R；(OS控制程序执行的)程序状态字信息PSW
-
进程的三态模型：运行态、阻塞态、就绪态
-
进程挂起：OS无法预期进程的数目与资源需求，计算机系统会在运行过程中出现资源不足的情况
运行资源不足：性能低和死锁。解决方案就是进程挂起：剥夺某些进程的内存及其他资源，调入OS管理的对换区，不再参加进程调度，待适当时候再调入内存、恢复资源、参与运行 -
挂起态与阻塞态有着本质区别，==后者占有已申请到的部分资源处于等待其他资源的状态，前者则没有任何资源==
-
进程的特性：动态性，独立性，并发性
-
进程的创建：在一个已经存在的进程（用户进程或系统进程）当中，通过系统调用来创建一个新的进程（Unix:fork；Windows:CreateProcess）
-
进程的数据结构：进程控制块PCB。用于记录和可画进程状态及环境信息的数据结构。
标识信息、现场信息、控制信息 -
进程映像：某一时刻进程的内容及其执行状态的集合。进程映像时内存级的物理实体又称为进程的内存映像。
-
进程上下文：进程的执行需要环境支持，包括CPU现场和高速缓存中的执行信息。
用户级上下文、寄存器上下文、系统级上下文。刻画了进程的执行情况。 -
队列管理模块：操作系统实现进程管理的核心模块
-
操作系统建立多个进程队列，包括就绪队列和阻塞队列
- 按需组织为先进先出队列与优先队列
- 队列中的进程可以通过PCB中的队列指引采用单/双向索引连接
-
出队和入队操作
-
原语：是由若干指令构成的完成某种特定功能的程序，执行时有不可分割性。进程使用的是进程控制原语。
-
进程切换：从正在运行的进程中收回处理器，让待运行进程来占有处理器运行。
保存被中断进程的上下文、转向进程调度、恢复待运行进程的上下文 -
模式切换：进程切换必须在操作系统内核模式下完成，必须切换模式（又称处理器状态切换）中断装置完成正向模式切换、中断返回指令完成逆向模式切换。
2.4 线程管理
-
并发程序设计：内核级、用户级、混合式
-
单线程在并发程序设计上的问题：进程切换开销大、进程通信开销大、限制进程并发的粒度、降低了并行计算的效率
-
线程的提出：把进程的两项功能，即独立分配资源与被调度分派执行分离开来。进程作为系统资源分配和保护的独立单位，不需要频繁地切换；线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换。
-
在多线程环境中，进程是操作系统中进行保护和资源分配的独立单位。
用来容纳进程映像的虚拟地址空间对进程、文件和设备的存取保护机制 -
线程是进程的一条执行路径，是调度的基本单位，同一个进程中所有进程共享进程获得的主存空间和资源。
-
线程状态：运行、就绪、阻塞。（挂起为资源相关，属于进程）
-
线程调度：1. OS感知线程环境下：处理器调度对象是线程、进程没用三种状态只有挂起；2. OS不感知线程环境下：调度对象仍是进程，用户空间中的用户调度程序调度线程。
-
并发多线程优点：快速线程切换、减少（系统）管理开销、（线程）通信易于实现、并行程度提高、节省内存空间
-
内核级线程KLT：线程管理的所有工作由OS内核来做，OS直接调度KLT
需要模式切换，系统开销较大 -
用户级线程ULT：用户空间运行的线程库，提供多线程应用程序的开发和运行支撑环境，内核未意识到线程的存在
仅有一个ULLT能执行、一个阻塞将引起整个进程阻塞 -
Jacketing技术：把阻塞式系统调用改造成非阻塞式；由jacketing程序来检查资源使用情况，从而决定是否执行进程切换或传递控制权给另一个线程
-
多线程实现的混合策略：单应用的多个ULT可映射成一些KLT，通过调整KLT数目，可以达到较好的并行效果
-
混合策略下的三态：KLT三态，系统调度负责；ULT三态，用户调度负责；活跃态ULT代表绑定KLT的三态；活跃态ULT运行时可激活用户调度；非阻塞系统调用可使用Jacketing启动用户调度，调整活跃态ULT
2.5 处理器调度
-
处理器调度层次
-
高级调度
长程调度、作业调度：决定是否能加入到执行的进程池中 - 中级调度
平衡负载调度：决定主存的可用进程集合；提供内存利用率和作业吞吐量 -
低级调度
短程调度、进程调度：决定哪个可用进程占用处理器执行；按照某种原则把处理器分配给就绪态进程或内核级线程 -
处理器调度算法的相关计算式
-
周转时间：\(T_i=E_i-S_i\)
- 平均周转时间：\(T=\frac{1}{N}\sum^N_{i=1}T_i\)
-
平均带权周转时间：\(W=\frac{1}{N}\sum^N_{i=1}\frac{T_i}{r_i}\)
-
调度算法
-
先来先服务算法FCFS
-
短作业有限SJF（属于优先级算法）
CPU运行时间：可以得到最小平均周转时间 -
时间片轮转调度算法RR：时钟中断中把现在执行的进程扔到队尾。（公平性、活动性）（时间片q太大退化为FCFS，太小系统开销大。）（一半设置为20-50ms）
-
优先级算法（分为可抢占、不可抢占）（分为静态、动态）
静态：创建进程的时候就确定进程优先级（缺点：高优先级一直占用CPU）
动态：创建进程时赋给进程的优先级，在进程运行过程中可以动态改变；每执行一个时间片就降低优先级，等待时间延长就提高优先级
优先级队列法：按照不同优先级分组，各级别之间使用优先级，统一级别之间使用时间片轮转。但是会出现优先级反转。
多级队列算法：先按照性质和类型（系统、用户、批处理）将就绪队列分为子队列，不同队列可以采用不同的调度算法。
-
多级反馈队列（RR和优先级算法综合发展）：优先级越高的队列时间片越短，如果用完了时间片还没进行完，则降级，如果提前用完，则升级。只有高优先级队列为空时才调度低优先级的。照顾短作业/IO繁忙/新进程。CPU繁忙进程采用最大时间片来执行，减少调度次数。
2.6 进程间通信
-
并发程序设计：把一个具体问题求解设计成若干个可同时执行的程序模块的方法。
并发性、共享性、交往性 -
进程互斥：并发进程之间因相互争夺独占性资源而产生的竞争制约关系
进程同步：并发进程之间为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
- 临界区：指并发进程中与互斥共享变量相关的程序段。（临界资源-互斥共享变量所代表的资源）
临界区管理的三个要求：1. 一次至多允许一个进程停留在相关的临界区内；2. 一个进程不能无限止地停留在临界区内；3. 一个进程不能无限止地等待进入临界区
（临界区的指令长度须短小精悍，这样才能保证系统效率）
-
记录型信号量：一种带数值的软资源；每个信号量建立一个阻塞进程队列；每个信号量相关一个整数值
正值表示资源可用资源个数或者可复用次数;零值表示无资源可用且无进程阻塞;负值的绝对值表示阻塞队列中进程个数 -
P原语（尝试减少、申请资源）：申请一个空闲资源(把信号量减1)，若成功，则退出；若失败，则该进程被阻塞
V原语（尝试增加、释放资源）：释放一个被占用资源(把信号量加1)，若发现有被阻塞的进程，则选择一个唤醒之。
- 管程：管程试图抽象相关并发进程对共享变量的访问，提供一个友好的并发程序设计开发环境；由若干
公共变量及说明和所有访问这些变量的进程所组成；管程的局部变量只能由该管程的过程存取；进程只能互斥地调用管程中的过程
管程的条件变量：条件变量、同步原语wait、同步原语signal
- 低级通信：只能传递状态与整数值（信号量
面对用户、信号面对OS）
高级通信：传递任意数量数据。（共享内存、管道、信息传递）
-
共享内存：把所有共享数据放在共享内存区域，任何想要访问该共享数据的进程都必须在本进程地址空间开辟一块内存区域，来映射存放共享数据的物理内存。
（三份缓冲区：共享区
存放共享变量、写入区、读取区）（读和写都需要先把共享区做一个映射， 映射到本地划出来的空间，在本地访问） -
消息传递：向中间件发送消息，订阅后获得消息。分为直接通信（利用套接字）和间接通信（利用消息队列）两种模式。
- 管道：一个进程的输出直接连接到另一个进程的输入。（本质是伪文件、内核缓冲区）
2.7 死锁
- 死锁：一组进程处于死锁状态是指：每一个进程都在等待被另一个进程所占有的、不能抢占的资源。
- 死锁产生：竞争资源产生死锁、PV操作不当产生死锁、同类资源分配不当引起死锁、对临时性资源使用不加限制引起死锁
- 解决死锁的三个思路：死锁防止、死锁避免、死锁检测和恢复
- 死锁产生的四个条件：互斥条件、持有和等待条件、不可剥夺条件、循环等待条件
- 死锁的防止（思路是破坏四个条件之一即可）
- 把独占型资源改造成共享性资源，使资源可被同时访问而不是互斥使用。（针对
互斥条件） - 采用剥夺式调度方法可以破坏第三个条件
- 静态分配：进程在执行中不再申请资源，因而不会出现持有了某些资源再等待另一些资源的情况，即破坏了第二个条件
- 在层次分配策略下，资源被分成多个层次（破坏了第四个条件）
- 死锁的避免：掌握并发进程中与每个进程有关的资源申请情况，避免死锁的发生
- 安全状态的两个条件：本身不存在死锁问题；存在着某种调度顺序，使得即使在最坏的情况下，每个进程仍都能够顺利的运行结束。
-
死锁的检测：此方法对资源分配不加限制，但系统定时运行一个死锁检测程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除
-
检测方法：设置两张表格来记录进程使用资源的情况。
等待资源表记录每个被阻塞进程等待的资源；占用资源表记录每个进程占有的资源。
检测等待占用关系\(W(P_i,P_j)\)，列出所有\(W\)，判断是否出现了循环等待问题。
- 资源分配图：进程、资源、进程占用资源、进程请求资源未果被阻塞
如没用环路、不会有死锁；有环路，每种资源实例数目，1必然死锁，n可能死锁
（多资源可以进行化简）
- 死锁检测后的方法：可以采用重新启动进程执行的办法，恢复工作应包含重启一个或全部进程，以及从哪一点开始重启动
特殊章节0：Petri Net
Petri在OS课上的重要性，无需多言
下图来自PPT：
0.0 概述术语
-
并发、顺序、冲突、同步、异步
-
网模型论（SNT）{模型部分}
有向网（模型基础）：结构特征、结构性质
网系统（资源+规则）：动态性质、分析方法、层次结构
- 通用网论（GNT）{理论部分}{借用SNT描述自然现象，具有普适性}
Synchrony（同步论，研究事件间的同步及定量描述，即同步距离）
Concurrency（并发公理，准确认识与定义并发现象，无传递性）
Enlogy（网逻辑，关注系统中无发生权的事件，来推导系统性质）
Net Topology （网拓扑，无向网，用于沟通离散与连续的工具）
Information Flow Net（信息流网，可逆信息元件，无信息丢失）
0.1 有向网
- 定义：三元组\(N=(S,T;F)\)称为有向网，如果$S ∪ T ≠ ∅ ~~~ ∧ ~~~S ∩ T = ∅ ~~~ ∧ ~~~F ⊆ S×T ∪ T×S ~~~∧ ~~~dom(F) ∪ cod(F)=S ∪ T $
- 有向网规则：不能有重复弧（基础概念定义金律：没有必要包含的，就有必要不包含）
有向网定义不包含：连通性、单纯性、简单性、有限性
- $X=S∪T $为有向网的节点集合
$^.x={y | (y,x)∈F} $：x的前集 \(x^·=\{y | (x,y)∈F\}\) ：x的后集
0.2 Petri网系统
-
Petri网定义（根据上下文决定）：1. 有向网；2. 以有向网为基础的网系统；3. 网系统：模型（SNT）+ 理论（GNT）；4. 模型 + 理论 + 应用。
-
Petri网系统：
-
EN系统：描述个体活动，有初始状态
- CE系统：描述自然活动，有当前状态
- P/T系统：描述同类个体
- 高级网系统：描述不同类个体（Pr/T系统）
-
C_net非线性系统
-
==EN系统==：\(\sum=(B,E;F,c_{in})\) 【条件：\((B,E;F)\)为有向网，且\(c_{in}\in2^B\)】
\(2^B\)：B的幂集合，即B的所有子集的集合
B的库所：两种状态-有托肯或无托肯，称为条件
E中的变迁称为事件，只与条件有关
\(c_{in}\)由真的条件组成（有托肯的库所），称为\(\sum\)的初始情态
-
丛：\(B\)的子集称为\(\sum\)的丛
-
变迁规则的定义：
\(e∈E\)，在丛\(c\) 有发生权，记为：\(c[e>\)，如果\(^.e⊆c ∧e^.∩c=\varnothing\)
\(c[e>\)，\(c'=(c−^.e)∪e^.\) 称为\(c\)的后继丛，记为\(c[e>c′\)，即e 在c 发生，并将c变成c′
- 同步与异步
同步（局部）：两组（个）事件反复发生呈现的规律如鼓掌、走路、四季系统
同步（全局）：任何两组事件都（加权）同步
异步（全局）：没有全局控制，局部确定
Petri网是异步并发系统 （局部确定，所以并发）
- 可达情态集：
从\(c_{in}\)（初始情态）开始，经有限多个事件发生所产生的所有后继丛构成的集合称为EN系统\(Σ=(B,E;F,c_{in})\)的可达集，用\(C_Σ\)表示。\(C_Σ\)中的丛称为\(Σ\)的情态。
- 基本现象
顺序关系、并发关系、冲突关系、冲撞关系
-
结构互补条件：\(b_1\)和\(b_2\)称为结构互补条件，如果一方前集后集为另一方后集前集，即 \(^.b_1=b_2^.~~~∧~~~b_1^.=^.b_2\)
-
条件补操作：将\(b\)的结构互补条件\(b^′\)添加到网上；如果\(b\)中有token，\(b^′\)中无token，否则\(b^′\)添一token
-
==条件/事件系统（C/E系统）==：区别是C为完全可达集，用来描述自然现象。
-
==库所/变迁系统（P/T系统）==：\(\sum=(S,T;F,K,W,M_0)\)
\(K\)：S元素的容量函数
\(W\)：F上的权函数，表示资源消耗或产生的量
\(M_0\)：初始标识
-
标识（资源分布）：\(M:S\rightarrow\{0,1,2,\dots\}\)称为\(\sum\)的表示，如果\(\forall s\in S:M(s)\le K(s)\)
-
发生权：t在M有发生权，记作\(M[t>\)
-
后继：若\(M[>\)，则t可以发生，M’为M的后继标识，后继关系记作\(M[t>M'\)
-
外延：\(^.t\cup t^.\)称为变迁t的外延
局部确定原理：每个变迁都有它的外延；变迁的发生只依赖其外延也只改变其外延
- 库所的物理意义：可观察的同类资源；同类资源在系统中作用相同
EN\(\in\)P/T，在EN中K=1，W=1，\(M_0\)是\(C_{in}\)的另一种表现形式
- 并发步：在同一标识可以并发的一个或多个变迁，称为该标识上的一个并发步
- 可达标识集： \([M_0⟩\)称为Σ的可达标识集 命题 \(M∈├ [M_0⟩\)，则$ [M⟩⊆├ [M_0⟩$
- 变迁序列：\(σ=τ_1τ_2…τ_n\)称为Σ的变迁序列，\(M_n\)称为σ的后继标识，记为\(M_0├ [σ⟩M_n\)。
- P/T系统的性质：活性、有界性、公平性
第三章：存储管理
大概内容为：3.1 存储管理基础、3.2 单连续分区存储管理、3.3 页式存储管理、3.4 段式存储管理、3.5 段页式存储管理
3.1 存储管理基础
-
逻辑地址：即用户变成所使用的地址空间
相对地址、虚地址从0开始编号 -
段式程序设计：把一个程序设计成多个段
代码段、数据段、堆栈段等；用户可以自己应用段覆盖技术扩充内存空间使用量这一技术是程序设计技术，不是OS存储管理的功能 -
物理地址：程序执行所用的地址空间
绝对地址、实地址 -
主存储器的复用：按照分区复用、按照页框复用
-
存储管理的基本模式：单连续存储管理
一维逻辑地址空间的程序占用一个主存固定分区或可变分区；段式存储管理段式二维逻辑地址空间的程序占用多个主存可变分区；页式存储管理一维逻辑地址空间的程序占用多个主存页框区；段页式存储管理段式二维逻辑地址空间的程序占用多个主存页框区 -
存储管理的功能：
-
地址转换：地址重定位，即把逻辑地址转成物理地址
静态重定位：在程序装入内存时进行地址转换，动态重地位：在CPU执行程序时进行地址转换 - 主存储器空间的分配与回收
- 主存储器空间的共享（多个进程共享主存储器资源、多个进程共享主存储器的某些区域）
- 存储保护（为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护；这一功能需要软硬件协同完成）
-
主存储器空间的扩充
-
虚拟存储器思想的提出：主存容量限制带来诸多不便；用户编程行为分析；因此可以考虑部分调入进程内容
-
虚拟存储器的基本思想：存储管理把进程全部信息放在辅存中，执行时先将其中的一部分装入主存，以后根据执行行为随用随调入；如果主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去
-
虚拟存储器的实现思路：(辅存)虚拟地址空间
容纳进程装入；(主存)实际地址空间承载进程执行 -
高速缓存存储器（Cache）：Cache是介于CPU和主存储器间的高速小容量存储器
由高速存储器、联想存储器、地址转换部件、替换逻辑等组成
分级：
- L1 Cache：分为数据缓存和指令缓存；内置；其成本最高，对CPU的性能影响最大；通常在32-256KB之间
- L2 Cache：分内置和外置两种，后者性能低一些；通常在512KB-8MB之间
-
L3 Cache：多为外置，在游戏和服务器领域有效；但对很多应用来说，总线改善比设置L3更加有利于提升系统性能
-
存储管理与硬件支撑：
-
鉴于程序执行与数据访问的局部性原理，存储管理软件使用Cache可以大幅度提升程序执行效率
- 动态重定位、存储保护等，若无硬件支撑在效率上是毫无意义的，即无实现价值
- 无虚拟地址中断，虚拟存储器无法实现
- 无页面替换等硬件支撑机制，虚拟存储器在效率上是毫无意义的
3.2 单连续分区存储管理
-
单连续分区存储管理：每个进程占用一个物理上完全连续的存储空间(区域)
单用户连续分区存储管理、固定分区存储管理、可变分区存储管理 -
单用户连续分区存储管理
-
主存区域划分为系统区与用户区
- 设置一个栅栏寄存器以分隔两个区域，硬件用它在执行时进行存储保护
- 一般采用静态重定位进行地址转换
- 硬件实现代价低
-
适用于单用户单任务操作系统，如DOS
-
主存分配表（固定分区存储管理）
支持多个分区、分区数量固定、分区大小固定、可用静态重定位、硬件实现代价低、早期OS采用
-
可变分区存储管理：按照进程的实际内存需求动态划分分区，并允许分区个数可变
-
按进程的内存需求来动态划分分区
- 创建一个进程时，根据进程所需主存量查看主存中是否有足够的空闲空间
若有，则按需要量分割一个分区；若无，则令该进程等待主存资源 - 由于分区大小按照进程实际需要量来确定，因此分区个数是随机变化的
- 可变分区方式的内存分配：最先适应(first-fit)分配算法；下次适应(next-fit)分配算法；最佳适应(best-fit)分配算法；最坏适应(worst-fit)分配算法
- 地址转换与存储保护：硬件实现机制与动态重定位。
- 可变分区方式的内存碎片：
- 固定分区方式会产生内存内碎片
- 可变分区方式会随着进程的内存分配产生一些小的不可用的内存分区，称为内存外碎片
- 最佳适应分配算法最容易产生外碎片
- 任何适应分配算法都不能避免产生外碎片
- 移动技术：用动态重定位，来用移动分区来解决内存外碎片
3.3 页式存储管理
- 基本原理：
分页存储器将主存划分成多个大小相等的页框；受页框尺寸限制，程序的逻辑地址也自然分成页；不同的页可以放在不同页框中，不需要连续；页表用于维系进程的主存完整性
页式存储管理的逻辑地址由两部分组成页号和页内偏移量；页式存储管理的物理地址由两部分组成页框号和页内偏移量；地址转换可以通过查页表完成
页的共享：页式存储管理能够实现多个进程共享程序和数据数据共享：不同进程可以使用不同页号共享数据页；程序共享：不同进程必须使用相同页号共享代码页
-
页表存储管理的地址转换：给定逻辑地址，计算逻辑页号和页内偏移量；查找页表，找到相应的物理页框号；计算最终的物理地址
-
逻辑地址划分：逻辑页号和页内偏移量。这种划分由系统自动完成。由于页面的大小一般为2的整数次幂，因此，地址的高位部分即为页号，低位部分即为页内偏移量。（PW）逻辑页号 ＝ 虚地址 / 页大小 页内偏移 ＝ 虚地址 % 页大小
-
转换代价：页表放在主存，每次转换必须访问两次主存；降低了存取速度；解决方案是利用Cache存放部分页表
-
页式存储管理的优缺点：优点-没有外碎片、一个程序不必连续存放、便于管理；缺点-一次性全部装入内存、为每个进程维护一张页表
-
局部性原理（共享物理空间，前提是程序执行遵从局部性原理）：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。
-
页表项的格式与内容：
-
驻留位（有效位）：表示该页是否在内存。若该位为1，表示该页位于内存中，即该页表项有效，可以使用；若该位为0，表示该页当前在外存中，此时若访问该页表项，将导致缺页中断；
-
保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等；
-
写回位（修改位）：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存；
-
引用位（访问位）：如果该页面被访问过，则设置此位。用于页面置换算法。
-
缺页处理：1.保护CPU现场2. 分析中断原因3. 转入缺页中断处理程序进行处理4. 恢复CPU现场，继续执行
-
页面调度：选择淘汰页的工作，目标：尽可能减少页面的换进换出次数。
-
缺页中断率：f = F / A （P运行中成功访问次数为S，不成功访问次数为F，总访问次数A = S + F）
影响因素：页框数、页面的大小、程序编制方式 -
==页面调度/置换算法==
-
最佳Opt页面调度算法
只可模拟、不可实现理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后才访问的页
-
最近较久未用LRU页面调度算法
实现代价大淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
-
最少使用LFU页面调度算法
淘汰最近一段时间内访问次数较少的页面，对Opt算法的模拟性比LRU更好
基于时间间隔中断，并给每一页设置一个计数器；时间间隔中断发生后，所有计数器清0；每访问页1次就给计数器加1；选择计数值最小的页面淘汰 -
先进先出FIFO页面调度算法
总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页(常驻的除外)
-
时钟Clock页面调度算法
FIFO + 跳过刚被访问的页面采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表；队列指针则相当于钟表面上的表针，指向可能要淘汰的页面；使用页引用标志位
-
二次机会EClock页面置换算法
FIFO + 跳过已经读|写的页面需要用到页表项当中的访问位(R)和修改位(M)。如果一个页面被读取，硬件自动将其R位置为1，如果一个页面被修改，则将M位置1。
-
工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W(t, Δ)来表示
是当前的执行时刻；Δ 称为工作集窗口，即一个定长的页面访问窗口；W(t, Δ)＝在当前时刻 t 之前的 Δ 窗口当中的所有逻辑页面所组成的集合 - 驻留集：驻留集是指在当前时刻，进程实际驻留在内存当中的逻辑页面集合。（驻留集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法）
- 缺页率：缺页率表示“缺页次数/内存访问次数”(比率)或“缺页的平均时间间隔的倒数”。
影响因素：页面置换算法、分配给进程的物理页面数目、页面本身的大小、程序的编制方法 - 反置页表：页号；进程标志符；标志位；哈希链
- 二级页表：由于不是所有的虚拟地址都会用到，所以不必把所有的页表项都保存在内存当中。缺省情形下，Windows采用了一种二级页表结构来实现逻辑地址到物理地址的映射。
- 一个32位的逻辑地址被划分为三个部分：页面目录索引（10位）、页表索引（10位） 、页内字节索引（即页内偏移地址，12位）。
3.4 段式存储管理
-
页式存储管理（和分区存储管理）只有一个逻辑地址空间，即一维的线性连续空间。
-
段表的具体实现
-
段表保存在内存当中；
-
设置一个段表基地址寄存器，用来指向内存当中段表的起始地址；
-
设置一个段表长度寄存器，用来指示段表的大小，即程序当中的段的个数；
段号+对应内存分区的起始地址+段长度
-
优缺点：
-
程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享
- 一个程序不必连续存放，没有内碎片
-
缺点：程序必须全部装入内存、外碎片等。
-
虚拟存储管理的段表扩充：
特征位：00(不在内存)、01(在内存)、11(共享段)存取权限：00(可执行)、01(可读)、11(可写)扩充位：0(固定长)、1(可扩充)标志位：00(未修改)、01(已修改)、11(不可移动)
3.5 段页式存储管理
- 基本思想：先把程序按逻辑划分为段，然后在段内等分为页
-
具体实现：
-
具体实现段表：记录每个段的页表起始地址和段长，而不是该段所在内存分区的起始地址
- 页表：记录逻辑页面号与物理页框号之间的对应关系。(每一段有一个，一个程序可有多个页表)
- 需要的硬件支持：段表基地址寄存器（STBR）和段表长度寄存器（STLR）
第四章：设备管理
评价为IO为考填空选择的点，应该会考一题计算题maybe。
第四章的知识点脉络是：4.1 设备管理基础 4.2 设备管理软件 4.3 独占型外设的分配 4.4 共享性外设的驱动 4.5 虚拟设备
其中4.1最重要，2345都是介绍性内容大致看一眼就行。
4.1 设备管理基础
- I/O的一些基本概述：
I/O设备定义：又称输入输出设备、外围设备、外部设备、外设,是用于计算机系统与外部世界的信息交换或存储
I/O操作：内存与外设之间的信息传送操作 会影响计算机系统的通用性与可扩充性 影响计算机系统的综合处理能力与性价比
I/O分类：信息传输角度：输入设备、输出设备、输入输出设备，交互功能角度：人机交互设备、存储设备、通信设备，设备管理角度：字符设备、块设备、网络设备
-
==设备管理的目标==：解决设备和CPU速度的不匹配，使主机和设备能充分并行工作，提高设备使用效率；屏蔽设备的物理细节和操作过程
-
设备管理的功能：设备中断处理、缓冲区管理、设备分配与回收、设备驱动调度、虚拟设备实现
-
缓冲区的作用：缓和CPU和I/O设备之间速度不匹配的矛盾；减少对CPU的中断频率；解决数据粒度不匹配的问题；提高⼆者之间的并行性
-
设备控制器：
背景：为达到模块化和通用性的设计目标，通常分开设置设备的机械部件和电子部件一个I/O设备由两部分组成：机械部分和电子部分（设备控制器或适配器）。电子部件称为设备控制器，又称为设备适配器、I/O控制器、I/O控制接口、I/O模块、I/O接口。
设备控制器的功能：是CPU与设备之间的接口
CPU与设备控制器通信的方法：
1. I/O 独立编址：给控制器中的每一个寄存器分配一个唯一的I/O端口编号, 称为I/O端口地址, 然后用专门的 I/O指令对端口进行操作。端口地址所构成的地址空间是完全独立的, 与内存的地址空间没有关系
2. 内存映像编址：把所有控制器当中的每个寄存器都映射为一个内存地址, 专门用于I/O操作（功能上）, 对这些单元的读写操作即为普通的内存访问操作。端口地址空间与内存的地址空间统一编址, 前者是后者的一部分, 一般位于后者的顶端部分。【不需要专门的I/O指令, 但不能对控制器中寄存器的内容进行Cache、每次都要判断访问的是内存还是I/O】
3. 混合编址：对于设备控制器中的寄存器, 采用独立编址的方法; 而对于设备的数据缓冲区, 采用内存映像编址的方法
- ==三种基本的I/O控制方式==
他们对CPU的依赖递减
轮询方式 (Polling I/O) 中断驱动方式 (Interrupt-driven I/O) 直接内存访问方式 (Direct Memory Access， DMA)
（还有个进阶的控制方式是通道） $$ \begin{array}{|c|c|c|} \hline \begin{array}{l} \text { CPU } \ \text { 作用 } \end{array} & \begin{array}{l} \text { 等待 } \ \text { 设备 } \end{array} & \begin{array}{l} \text { 内存数 } \ \text { 据交换 } \end{array} \ \hline \begin{array}{l} \text { 轮询 } \ \text { 方式 } \end{array} & \text { 需要 } & \text { 参与 } \ \hline \begin{array}{l} \text { 中断 } \ \text { 方式 } \end{array} & \text { 不需要 } & \text { 参与 } \ \hline \begin{array}{l} \text { DMA } \ \text { 方式 } \end{array} & \text { 不需要 } & \text { 渗与 } \ \hline \end{array} $$
- 轮询
基本思路：在设备驱动程序中通过不断检测I/O设备的当前状态，来控制I/O操作的完成。在进行I/O操作之前，要循环检测设备是否就绪；在I/O操作进行之中，要循环检测设备是否完成
步骤：处理器向控制器发送I/O命令，轮询I/O结果\(\Rightarrow\)若设备未就绪，则重复测试过程，直至设备就绪\(\Rightarrow\)执行内存数据交换\(\Rightarrow\)等待I/O操作完成后，处理器才可以继续其他操作
控制I/O的所有工作均由CPU来完成
- 中断驱动
基本思路：用户进程通过系统调用函数来发起I/O操作, 并在发起后阻塞该进程, 调度其他的进程使用CPU。在I/O操作完成时, 设备向CPU发出中断, 然后在中断处理程序中做进一步的处理。
步骤：处理器向控制器发出具体I/O命令，然后继续执行后续指令若进程支持异步I/O，后续指令仍可是该进程中的指令；否则，该进程在这个中断上挂起，处理器执行其他工作\(\Rightarrow\)控制器检查设备状态，就绪后发出中断\(\Rightarrow\)CPU响应中断，进行中断处理\(\Rightarrow\)中断处理执行内存数据交换
数据的每次读写还是通过CPU来完成, 但是当I/O设备在进行数据处理时, CPU不必等待, 可以继续执行其他的进程
- 直接访问内存
流程：处理器向DMA模块发出I/O 命令\(\Rightarrow\)处理器继续执行其他工作， DMA模块负责传送全部数据数据\(\Rightarrow\)传送结束后，DMA中断处理器
DMA控制器可以直接去访问系统总线，它能代替CPU去指挥I/O设备与内存之间的数据传送。
DMA控制器包含了：一个内存地址寄存器、一个字节计数器，以及一个或多个控制寄存器
- I/O通道（通道控制器、I/O处理器）
采用四级连接：处理器、通道、控制器、设备
处理器不再执行I/O指令，而是在主存中组织通道程序，由I/O通道执行
工作流程：CPU遇到I/O任务，组织通道程序，置通道程序地址字CAW，启动指定通道通道\(\Rightarrow\)从CAW获得通道程序，控制I/O设备进行操作，CPU执行其他任务\(\Rightarrow\)I/O操作完成后，I/O通道发出中断，CPU处理中断，并从通道程序状态字CSW获得通道执行情况，处理I/O操作
CPU与通道高度并行工作
与DMA的区别：两者都要完成地址加1减1的操作，两者都是硬件，但DMA不能执行指令，通道则可以；DMA的初始化工作仍由CPU完成，通道则是自己完成；与DMA相比，通道能够连接更多的外部设备。
- 通道三种类型:
- 字节多路通道
- 适用于字符类低速外围设备, 通道的数据宽度为单字节，以字节交叉方式轮流的为多台外部设备服务
- 选中一个设备后传一个字节, 然后换下一个设备（选择设备也需要时间
- 流量：各设备字节传送速率之和
- 选择通道
- 为优先级高的高速外围设备服务, 如磁盘, 数据传送以成块方式进行
- 每个选择通道只有一个以成组方式工作的子通道, 逐个为多台高速外围设备服务
- 选中一个设备后必须把该设备所有数据全传送完
- 流量：各设备字节传送速率的最大值
-
数组多路通道
- 把字节多路通道和选择通道的特性结合起来
- 连接多台高速外设, 每次为一台高速设备传送一个数据块, 轮流为多台外围设备服务
- 流量：各设备字节传送速率的最大值
-
总线：为了解决I/O速度不匹配
使主机和设备充分并行，提高系统效率 -
单线性结构模型：将CPU、主存和I/O模块连接到同一总线
优点：结构简单，易于扩充缺点：共用总线；设备多时总线压力大，传输时延长，且慢速外设占用带宽多
-
三级总线模型：主存和Cache通过主存总线连接，主存总线和扩展总线上的I/O设备间通过扩展总线接口缓冲
优点：主存与I/O之间的数据传送、处理器的内存活动分离；可以支持更多的I/O设备缺点：不适用于I/O设备数据速率相差太大的情形
-
南桥与北桥：通过存储总线、PCI总线、E(ISA)总线分别连接主存、高速I/O设备和低速I/O设备
优点：可以支持不同数据速率的I/O设备
-
一种基于通道的服务器总线模型：支持CPU、主存和多个I/O通道之间的数据传送；支持I/O通道和I/O控制器，及I/O控制器和设备之间的数据传送
4.2 设备管理软件
-
设计目标：高效性、通用性；设计思路：把软件组织成层次结构
-
设备分类：块设备、字符设备、网络设备
-
I/O缓冲区：在内存中开辟的存储区，专门用于临时存放I/O操作数据
操作过程：写操作：将数据送至缓冲区，直到装满或需要写出，等待适当时候系统将缓冲区内容写到设备上，读操作：系统将设备上的物理记录读至缓冲区，根据要求将当前所需要的数据从缓冲区中读出并传送给进程
目的：解决CPU与设备之间速度不匹配的矛盾、协调逻辑记录大小和物理记录大小不一致的问题、提高CPU和设备的并行性、减少I/O操作对CPU的中断次数、放宽对CPU中断响应时间的要求。
- 单缓冲技术、双缓冲技术、循环缓冲技术
4.4 共享性外设的驱动
- 磁盘结构：磁盘一般由多个盘片组成，每个盘片一般有两个盘面，盘面包括多个同心圆结构的磁道，不同盘面上位于相同位置的磁道构成柱面，每个磁道分为固定的多个扇区，相邻扇区组合成簇物理块地址
-
磁盘读写数据的方式：磁头必须定位到指定磁道上指定扇区的开始处。
-
寻道（柱面定位）：控制移动臂到达指定柱面
-
旋转延迟：等待要读写的扇区旋转到磁头下
-
选择磁头号，进行数据传送
-
磁盘存取时间：寻道时间、旋转延迟、传送时间的总和 $$ T_a=T_s+\frac{1}{2 r}+\frac{b}{r N} $$ \(\mathrm{Ta}\) ：存取时间 \(\mathrm{Ts}\) ：寻道时间 \(r\) : 磁盘旋转速度 (单位: 转/秒) b: 要传送的字节数 \(\mathrm{N}:\) 一个磁道中的字节数
-
磁盘格式化：低级格式化
标出磁道和扇区，在相邻的扇区之间有狭窄的间隙隔开\(\Rightarrow\)分区用分区软件把整个硬盘划分为若干个逻辑分区，每个分区可视为一个独立的磁盘\(\Rightarrow\)高级格式化对每一个逻辑分区，分别进行一种高级格式化（即通常的格式化操作），生成一个引导块、空闲存储管理结构、根目录和一个空白的文件系统 - 磁盘分类：固态硬盘
读写快耐用性差、机械硬盘随机读写慢顺序读写快耐用性好、混合硬盘 - 磁盘访问：磁盘的访问是以扇区作为最小的寻址和存取单位，在访问一个磁盘扇区时，所需的时间主要有：
- 柱面定位时间：磁头在磁头臂牵引下，移动到指定柱面的机械运动时间；
- 旋转延迟时间：等待指定的扇区旋转到磁头的正下方所需的机械运动时间；它与磁盘转速有关
-
数据传送时间：从指定扇区读写数据的时间。
-
磁盘调度：按照最佳次序执行处理访问磁盘的多个I/O请求, 以减少磁盘访问的总处理时间。包括移臂调度、旋转调度
-
移臂调度：FCFS（先来先服务）, SSTF（最短定位时间优先一一先执行查找时间最短的请求, 具有较好的寻道性能; 存在“饥饿”现象)，电梯算法（Elevator Algorithm，也叫扫描算法SCAN）
电梯算法: 磁头从当前的位置开始, 往一个方向移动, 依次执行这条路径上的所有访问请求, 直到前面已无任何访问请求, 然后反转方向继续进行（磁头移动的总距离有一个固定的上界，即柱面总数的两倍。）
-
旋转调度：循环排序、优化分布
第五章：文件管理
大概的组织架构：5.1 文件系统概念 5.2 文件的组织 5.3 文件目录 5.4 文件的共享与保护 5.5 文件的使用 5.6 文件系统的实现
5.1 文件系统概念
-
文件：以将其视为一个单独的、连续的逻辑地址空间
-
文件分类：普通文件（regular file）
包含用户信息的文件ASCII文件：由一行行的文本组成；二进制文件：非ASCII文件，通常会具有某种内部的逻辑结构，为相关的应用程序所了解目录文件（directory）管理文件系统结构的系统文件 -
文件系统：操作系统中负责存取和管理信息的模块，它用统一方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法
-
文件的结构：指的是逻辑结构，即文件系统提供给用户的文件结构形式，它独立于在外存上的物理存储结构。
物理结构：对于文件系统而言，整个文件是由无结构的字节流序列组成 -
文件系统的功能：
面向用户：件的按名存取、文件的共享与保护、文件的操作与使用 -
文件系统的组织：文件组织、文件存取、文件控制、文件使用
5.2 文件的组织
- 卷：是存储介质的物理单位，对应于一盘磁带、一块软盘、一个光盘片、一个硬盘分区
块：是存储介质上连续信息所组成的一个区域，也叫做物理记录
外围设备因启停机械动作或识别不同块的要求，两个相邻块之间必须留有间隙
-
逻辑文件（文件的逻辑结构）
独立于物理环境的、用户概念中的抽象信息组织方式用户能观察到的，并加以处理的数据集合分为两种形式：流式文件件内的数据不组织成记录，只是由一串连续字节组成的信息流序列、记录式文件有结构的文件，它是若干逻辑记录信息所组成的记录流文件逻辑记录是文件中按照信息在逻辑上的独立含义所划分的 -
一个物理记录只存放一个逻辑记录可能造成极大的浪费\(\Rightarrow\)提出了成组与分解
若干个逻辑记录合并成一组，写入一个块叫记录的成组，每块中的逻辑记录数称块因子。记录的成组在系统输出缓冲区进行，凑满一块再写入存储介质 当存储介质上的一个物理记录读进系统输入缓冲区后，把逻辑记录从块中分离出来的操作叫记录的分解操作
优点：记录成组与分解不仅节省存储空间，还能减少输入输出操作次数，提高系统效率
新特征：提前读、推迟写
- 物理文件：文件在物理存储空间中的存放方法和组织关系 顺序文件（放在依次相邻的块中）、连接文件（用连接字表示物理块先后顺序）、直接/散列文件（通过计算记录的关键字建立与其物理存储地址间的对应关系）、索引文件（为每个文件建立索引表，地址由文件目录指出，在存储器上分为索引区和数据区）
5.3 文件目录
- 文件目录：实现文件按名存取的数据结构。文件目录需要永久保存，因此也组织成文件存放于磁盘，称目录文件。
一级、二级（主～->用户～）、树形（倒向有根树）
5.4 文件的共享与保护
- 文件共享：系统调用Link连接实现无限制共享，os需要提供对共享文件的同步控制（同时读、一写一读）
- 文件保护：保证文件的完整性
- 文件保密：内容不可被未授权者窃取
5.5 文件的使用
- 文件的存取方法：顺序存取方法、直接存取方法、索引存取方法
- 用户通过两类接口与文件系统交互：
- 第一类是与文件有关的操作命令，如UNIX中的cat、cd、cp、find、mv、rm、mkdir、rmdir等
- 第二类是提供给用户程序使用的文件类系统调用，如建立、打开、读/写、定位、关闭、撤销等
5.6 文件系统的实现
-
文件的逻辑结构一般是字节流，FS需要将其保存在磁盘的扇区中
-
把磁盘空间划分为一个个大小相同的块（block），称为物理块；把该逻辑地址空间也分成大小相同的逻辑块，在文件系统的内部，以块为单位来进行操作； 一个物理块由一个或多个连续的扇区组成
-
文件控制块（FCB）：文件存在的标志，unix中叫inode
-
文件分配表FAT：在链表结构的基础上，把每一个物理块当中的链表指针抽取出来，单独组成一个表格FAT，将其放在内存中。
实现了链表指针与文件数据的分离，整个物理块都可以用来存放数据。
FAT在内存，可以先从FAT表中查到相应的物理块编号（地址），然后再去访问外存，这样只需访问一次外存，速度快。
FAT文件系统的三种版本：FAT-12、FAT-16和 FAT-32, 这取决于用多少位来表示一个物理块编号, 并决定了 FAT表项的宽度。FAT-32实际上仅使用了28位;
FAT表项的个数就等于物理块的个数, 即磁盘分区的大小除以每个块的大小。块的大小可以被设置为 512 的倍数, 如 \(1 \mathrm{~KB} 、 2 \mathrm{~KB} 、 4 \mathrm{~KB}\) 等;
FAT表的大小 \(=\) FAT表项的个数 \(\times\) 表项宽度；
FAT表所能表示的磁盘分区的最大容量：FAT表项的最大个数 \(\times\) 块的大小。
-
辅存空间管理：随着用户文件不断建立和撤销，文件存储空间会出现许多碎片。OS解决碎片的办法是整理碎片，在整理过程中，往往对文件重新组织，让其存放在连续存储区中
-
bitmap：磁盘的每一个物理块用1个bit来表示，若物理块是空闲的，则相应位的值为1；若物理块已分配，则相应位的值为0。第一个空闲物理块是：(值为0的字个数)×(字长)＋首个1的字内偏移量。bitmap本身存放在磁盘上
-
链表：每一个空闲物理块上都有一个指针，把所有的空闲块通过该指针链接起来，形成一个链表，文件系统只需记住该链表的首结点指针，摘下来分配
-
索引：由若干个空闲物理块组成一个链表，但这些物理块本身并不参与分配，而是专门用来记录系统中所有空 闲物理块的编号，动态维护。若该结点已满，且又有磁盘空间被释放；或者该结点已空，且又有文件申请磁盘空间，则将该结点写回磁盘，并调入新的结点
题型速览
这里将PPT、作业、参考题列出来分析。仅供过拟合用。
From PPT
T1（PPT1 p68）（处理器利用率计算）
第一个进程（单序程序工作）：\(利用率=\frac{(130-78)+(280-228)+(430-378)}{450}\times 100 \% =34.67\%\)
第二个进程（双序程序工作）：\(利用率=\frac{(62-20)+(212-170)+(362-320)+(130-78)+(280-228)+(430-378)}{450}\times 100 \% =62.67\%\)
T2 （PPT3 p101）（哲学家就餐问题）
//算法一：不完全正确可能死锁
#define N 5 // 哲学家个数
void philosopher(int i) // 哲学家编号：0-4
{
while (TRUE)
{
think( ); // 哲学家在思考
take_fork(i); // 去拿左边的叉子
take_fork((i + 1) % N); // 去拿右边的叉子
eat( ); // 吃面条中….
put_fork(i); // 放下左边的叉子
put_fork((i + 1) % N); // 放下右边的叉子
}
}
//算法二：改进了拿叉子的过程但是仍然不正确
while(1) // 去拿两把叉子
{
take_fork(i); // 去拿左边的叉子
if(fork((i + 1) % N)) { // 右边叉子还在吗
take_fork((i + 1) % N);// 去拿右边的叉子
break; // 两把叉子均到手
}
else { // 右边叉子已不在
put_fork(i); // 放下左边的叉子
wait_some_time( ); // 等待一会儿
}
}
//算法三：等待时间随机变化（可行但非万全之策）
while(1) // 去拿两把叉子
{
take_fork(i); // 去拿左边的叉子
if(fork((i + 1) % N)) { // 右边叉子还在吗
take_fork((i + 1) % N);// 去拿右边的叉子
break; // 两把叉子均到手
}
else { // 右边叉子已不在
put_fork(i); // 放下左边的叉子
wait_random_time( ); // 等待随机长时间
}
}
//算法四：互斥访问。正确但是每次只允许一个人进餐
semaphore mutex; // 互斥信号量，初值1
void philosopher(int i) // 哲学家编号i：0-4
{
while(TRUE){
think( ); // 哲学家在思考
P(mutex); // 进入临界区
take_fork(i); // 去拿左边的叉子
take_fork((i + 1) % N); // 去拿右边的叉子
eat( ); // 吃面条中….
put_fork(i); // 放下左边的叉子
put_fork((i + 1) % N); // 放下右边的叉子
V(mutex); // 退出临界区
}
}
T3（PPT5 P61）（EN系统，四季系统）
T4（PPT5 P89）（教堂问题之EN、PT图）
T5（PPT6 P81）（页面调度置换）
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为10^8^ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LFU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：
（1）依次访问上述三个虚地址，各需多久？（2）基于上述访问序列，则虚地址1565H的物理地址是多少？
（1）页面大小为4KB，即212，则得到页内偏移占虚地址的低12位
2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计： 10ns+100ns+100ns=210ns
1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计：10ns+100ns+10^8^ns+100ns
25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计： 10ns+100ns=110ns
（2）
当访问虚地址1565H 时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此 1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。
T6（PPT7 P48）（中断驱动问题）
T7（PPT7 P57）（DMA与直接访问内存）
解：
- 每条指令执行周期: \(1 / 500 / 10^6 * 10^9 * 2=4 \mathrm{~ns}\)中断程序80ns, 其他开销20ns 传输单位: 32 bit \(/ 8=4\) byte 4byte \(/ 0.5 \mathrm{MB} / \mathrm{s}=8000 \mathrm{~ns}\)
$$ 100 / 8000=1.25 \% $$ 2. 传输时间 \(5000 \mathrm{~B} / 5 \mathrm{MB} / \mathrm{s}=10^{\wedge} 6 \mathrm{~ns}\)处理前后开销 \(250 * 2=500 \mathrm{~ns}\)
T8（PPT7 P68）（三种通道类型与其流量）
T9（PPT7 P102）（设备驱动程序与中断处理程序）
设备驱动程序与中断处理程序如何协调工作，共同完成I/O操作？
方案一：当用户进程需要输入输出服务时，调用相应的系统调用函数(->sys_read)；该函数调用相应的设备驱动程序，驱动程序在启动I/O操作后被阻塞(->driver_read)；I/O操作完成后，产生一个中断，然后中断处理程序将接管CPU，并唤醒被阻塞的驱动程序。
方案二：数据结构：请求队列（request queue）；块设备驱动程序：上层函数，负责管理请求队列；底层函数，负责与硬件打交道，完成真正的I/O操作；I/O请求的提交与真正实现是分离的。各用户进程（通过内核）调用上层函数，先提交I/O请求(make_request)，然后阻塞；底层函数则从队列中取出每个I/O请求，并完成之。能对各I/O请求进行优化，如数据块重组。
T10（PPT7 P148）（磁盘访问时间）
(1)文件由同一个磁道上的 300 个连续扇区构成: $$ 6.9 \mathrm{~ms}+3 \mathrm{~ms}+6 \mathrm{~ms}=15.9 \mathrm{~ms} ; $$ (2)文件由 300 个随机分布的扇区构成: $$ (6.9 \mathrm{~ms}+3 \mathrm{~ms}+0.02 \mathrm{~ms})^* 300=2976 \mathrm{~ms} \text {; } $$
随机分布时的访问时间为连续分布时的 187 倍。
T11（PPT7 P152）（磁盘调度）
FCFS：SUM=640
SSTF：SUM=236
电梯：SUM=208
From HW
T1（hw002）（petri网建模练习）
Petri网建模练习（不可以使用重名变迁，即多个变迁有相同的标签名字）
给定自然语言文本描述的业务流程，手工进行Petri网建模与绘制（活动名称请使用文本描述中括号内包含的英文单词或者短语）。 1) 井下工作人员发现设备故障后，会首先发出维修申请（Apply for repairing）； 2) 维修人员对设备故障进行初步诊断后，将维修过程分为两类：井下直接维修 (Repair in mine)；上井地面维修。上井地面维修方式进一步分解描述如下: + 若设备很大，则先拆解设备（Decompose）； + 将设备升井 (Move up to ground) ； + 在地面进行设备维修 (Repair)； + 将设备下井 (Take down to mine)； + 若设备很大，还需要进行井下组装（Assemble）
解答：
点评：要注意变迁是动作，状态是状态。
T2（HW003）（哲学家就餐）（必背）
如果投影到考试中的话，就是给定一系列参数让你画一个哲学家的petri网。
比如：给定人数为5，叉子为5，画出哲学家的petri网。
T3 （HW004）（petri网计算问题）
由于多并发分支上的变迁可以任意次序执行，而同一并行分支上的多个变迁必须顺序执行。 且本petri网没有循环、互斥互斥结构。因此最终序列必定为 8 个变迁的排序，最终长度必定为 8 。由于A、H固定为首尾两点，不需要考虑其对序列类型种类产生的影响。
因此对于B、C、D、E、F、G六个变迁进行排序。 不考虑前后顺序的话，一共可能的排序方式有: \(6!=6 \times 5 \times 4 \times 3 \times 2 \times 1=720\)由于C、D为顺序关系， \(E 、 F 、 G\) 为顺序关系。故最终的排序数目为: \(720 \div 2!\div 3!=60\)综上所述，可产生长度为 8 的 60 种不同的完整发生序列。
T4（HW005）(页面调度)（感觉也是必考题）（这里的作答90/100应该不是满分答案慎看）
QUESTION
逻辑页号访问次序为：2, 3, 2, 1, 4, 5, 2, 4, 5, 1, 3, 2, 5, 2，共分配三个物理页面，请给出Opt、FIFO、LRU、LFU、Clock算法的每步置换过程。
解：
- Opt
最优替换算法Opt一种理论上的页面置换算法，其目的是最小化页面缺失（页错误）。在理想情况下，这种算法会预见未来对页面的请求，并做出最佳的替换决策以保证页面缺失率最低。
| 页号次序 | 2 | 3 | 2 | 1 | 4 | 5 | 2 | 4 | 5 | 1 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Page 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| Page 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 1 | 3 | 3 | 3 | 3 | |
| Page 3 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |||
| 缺页中断 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
2.FIFO
FIFO 页面置换算法是一种常用的内存管理策略，其核心思想简单直观：最早进入内存的页面，当发生页面置换时，也将最先被替换出去。这种方法模仿了现实生活中的队列操作，即“先进先出”。
| 页号次序 | 2 | 3 | 2 | 1 | 4 | 5 | 2 | 4 | 5 | 1 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Page 1 | 2 | 2 | 2 | 2 | 3 | 1 | 4 | 4 | 4 | 5 | 2 | 2 | 1 | 3 |
| Page 2 | 3 | 3 | 3 | 1 | 4 | 5 | 5 | 5 | 2 | 1 | 1 | 3 | 5 | |
| Page 3 | 1 | 4 | 5 | 2 | 2 | 2 | 1 | 3 | 3 | 5 | 2 | |||
| 缺页中断 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
- LRU
LRU 页面置换算法基于一个简单的假设：如果一个页面在最近一段时间内没有被访问，那么在未来它被访问的可能性也比较小。因此，这种算法的目标是为了优化内存中的页面管理，通过移除最长时间未被访问的页面来响应新的页面请求。
| 页号次序 | 2 | 3 | 2 | 1 | 4 | 5 | 2 | 4 | 5 | 1 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Page 1 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 2 | 2 | 2 |
| Page 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | 3 | |
| Page 3 | 1 | 1 | 1 | 2 | 2 | 2 | 1 | 1 | 1 | 5 | 5 | |||
| 缺页中断 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
- LFU
LFU页面置换算法基于这样一个假设：如果一个页面在过去被访问的次数较少，那么在未来被访问的可能性也会较低。
及记录每个页面在目前访问的次数，当面临缺页时，去除频率最低的页面即可。
当存在两个频率都是最低的时候，我们假使依据FIFO逻辑，即先进先出。
| 页号次序 | 2 | 3 | 2 | 1 | 4 | 5 | 2 | 4 | 5 | 1 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Page 1 | 2(1) | 2(1) | 2(2) | 2(2) | 2(2) | 2(2) | 2(3) | 2(3) | 2(3) | 2(3) | 2(3) | 2(4) | 2(4) | 2(5) |
| Page 2 | 3(1) | 3(1) | 3(1) | 1(1) | 4(1) | 4(1) | 4(2) | 4(2) | 5(2) | 5(2) | 5(2) | 5(3) | 5(3) | |
| Page 3 | 1(1) | 4(1) | 5(1) | 5(1) | 5(1) | 5(2) | 1(1) | 3(1) | 3(1) | 3(1) | 3(1) | |||
| 缺页中断 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
- Clock
Clock 页面置换算法，也称为 Second Chance 算法，是一种用于管理计算机内存的页面置换算法。Clock 算法通过一个循环队列（常比喻为时钟）和每个页面的访问位（reference bit）来实现，有效地结合了 FIFO 和 LRU 的特点。
| 页号次序 | 2 | 3 | 2 | 1 | 4 | 5 | 2 | 4 | 5 | 1 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Page 1 | 2(1) | 2(1) | 2(2) | 2(2) | 2(1) | 2(1) | 2(2) | 2(2) | 2(2) | 1(1) | 1(1) | 1(1) | 5(1) | 5(1) |
| Page 2 | 3(1) | 3(1) | 3(1) | 4(1) | 4(1) | 4(1) | 4(2) | 4(2) | 4(2) | 3(1) | 3(1) | 3(1) | 3(1) | |
| Page 3 | 1(1) | 1(1) | 5(1) | 5(1) | 5(1) | 5(2) | 5(2) | 5(2) | 2(1) | 2(1) | 2(2) | |||
| 指针位置 | →P1 | →P1 | →P1 | →P1 | →P3 | →P1 | →P1 | →P1 | →P1 | →P2 | →P3 | →P1 | →P2 | →P2 |
| 缺页中断 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |