操作系统
[操作系统]
1.并发 并行 多道特征（关键词固定 填空或者简答） |
系统综述
五个功能 |
中断
1.1.5 中断的概念和作用、内部中断、外部中断、中断机制的基本原理_处理器中断-CSDN博客
目标
如何提高内存利用率 |
- 便利性
- 有效性
- 扩展能力
概念
操作系统是指控制管理整个计算机系统的硬件和软件资源的程序集合，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件—-OS是由处理器执行的程序集合
- 系统资源的管理者
将进程放入内存进行执行
向上层提供方便易用的服务
作为最接近硬件的层次
特征
并发
最重要，其他特征的前提
- 并发：两个或者多个事件同一时间间隔内发生 宏观上同时发生，微观上交替发生
- 并行：两个或多个事件在同一时刻同时发生
- 程序：静态实体，无法并发
- 进程：动态实体，可以并发
- 单处理机系统：进程可并发执行，无法并行执行
- 多处理机系统：进程既可并发执行，又可并行执行
共享
系统中的资源可供内存中多个并发的进程共同使用
并发和共享互为存在条件
类型
- 临界资源：在一段时间内，只允许一个进程访问
- 非临界资源：在一段时间内，允许多个进程访问
共享方式
- 互斥访问共享：对临界资源的访问，如打印机
- 同时访问共享：对非临界资源的访问，如磁盘
虚拟
- 时分复用技术：虚拟处理器、虚拟设备（打印机：SPOOLING技术）
- 空分复用技术：虚拟磁盘、内存
异步
AKA：不确定性质
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
通常而言，操作系统的不确定性是指异步性，而非程序执行结果的不确定性。
易发展性
- 硬件升级和新型硬件的出现
- 新设备、服务的出现
- 错误修复、纠正
发展分类
吞吐量=总量/总时间 |
关心的目标
批处理：吞吐时间和周转时间 |
交互式和批处理
批处理：脱机控制或者自动控制，用户使用操作系统提供的作业控制语言写 控制说明书，连程序和数据一起交给OS |
串行处理
问题：调度、启动准备时间、无操作系统、控制台运行、输入设备（卡片阅读）载入计算机、顺序访问
简单批处理系统
监控程序、一次处理一道作业、运行模式：用户和内核；问题：CPU大量时间空闲 因为Io速度比CPU慢
监控程序的功能：
自动续接下一个作业
内存保护：保护监控程序所在的内存区域
定时器：防止作业独占系统
特权指令：监控程序的指令：IO
中断
多道批处理系统
- 多个作业并发执行
- 作业调度程序负责调度
- 硬件支持：I/O中断、直接存储器访问（DMA）
- 特征：多道性、调度性、无序性、无交互能力
- 会在内存中产生碎片
- 目的—–提高资源的利用率和系统吞吐量
分时操作系统
仍然采用多道程序设计技术
多用户各自独立、通过不同终端、同时共享处理器、各自不干扰
特征：多路性、独立性、及时性、交互性—-引入终端命令解释程序接受用户的命令，解释命令并执行还需要系统调用功能
第一个分时OS：CTSS
实时操作系统
- 及时响应
- 分类：如下，大多系统是二者结合
- 实时系统的特征**：实时性**、可靠性、多路性、独立性、交互性（比分时差）
主要功能
进程
- 一段可执行的程序
- 程序所需要的相关数据（变量、工作空间、缓冲区等）
- 程序的执行上下文（execution context）
➢ 也称进程状态（process state）
➢ 操作系统用来管理和控制进程所需的所有数据
内存管理
内存管理的任务
- 进程隔离：每个进程空间独立、互不干扰
- 自动分配和管理：OS动态分配、对程序员透明
- 模块化程序设计
- 保护和访问控制
- 永久存储
实现方式：文件管理+虚拟内存
文件管理
- 文件系统实现长期存储
- 文件：有名称的对象，保护和访问控制的基本单元
虚拟内存
- 程序以逻辑方式访问存储器
- 多作业同时驻留内存
- – 每个作业部分驻留
- – 换入、换出机制
信息保护安全
- 可用性
- 保密性
- 数据完整性
- 可靠性
调度和资源管理
- 公平性
- 有差别的响应性
- 有效性：吞吐量和响应时间的折中
目标功能
处理机功能：进程、调度
存储器管理：
设备管理
文件管理
用户接口：
- 命令接口：联机命令接口（实时）和脱机命令接口（批处理）
- 程序接口（系统调用–（广义指令））
体系结构
无结构
模块化结构
分层式结构
- 单向依赖关系：每层只能使用其直接下层所提供的服务 每层对其上层隐藏其下各层的存在
- 缺点：效率低
微内核
内核保留基本功能、C\S模式
进程
高级通信机制归结为三大类 |
进程切换一定发生模式切换 |
作业
状态
提交状态
后备状态：作业输入到OS缓冲池等待调度调入内存的状态
运行状态：在缓冲池中的作业由调度算法调入内存，创建为进程，变为运行态。
PS:内存中进程的调度是微观调度，对于作业来说只要被调入内存创建进程后宏观上就是运行状态
完成状态：运行结束或者错误终止
进程性质：动态性（最基本特征）、并发性、独立性、异步性（同步的原因） |
顺序执行和并发执行
顺序
- 顺序性
- 封闭性：执行的程序独占资源，不会被打断
- 可再现性
- 表示：有向无循环图
并发
两个或者多个事件同一时间间隔内发生 宏观上同时发生，微观上交替发生
- 间断性
- 失去封闭性
- 不可再现性
引入进程的目的是使多道程序能够正确地并发执行
概念
- 一个正在执行的程序。
- 一个正在计算机上执行的程序实例。
- 一个能够被调度到处理器上执行的实体。
- 由一串指令的执行、当前状态和一组正在使用的系统资源表征的活动单元
程序：静态的、存放在磁盘里的可执行文件，就是一组有序指令集合；永久
进程：动态的，程序的一次执行过程，同一个程序多次执行会对应多个进程；具有生命周期
进程和程序不是一一对应—-n:m
一个程序开始运行前,需要创建对应的进程,也就要创建相应的PCB
对比
- 动态性：进程具有动态性、生命周期；程序只是一组有序指令集合，静态实体。
- 并发性：进程可以并发；程序不可以
- 独立性：进程实体是一个能独立运行的基本单位，调度和资源分配的基本单位；未被建立进程的程序不能作为独立的单位参加运行
引入进程带来的开销：空间（数据结构）、时间、控制复杂性
组成
PCB：进程控制块—–由OS创建管理使用 常驻内存 进程存在的唯一标志 OS根据PCB来对并发执行的进程进行控制管理
标示符:pid
状态
优先级
程序计数器
内存指针
上下文数据
I/O状态信息
记账信息
PCB的属性可分为三类
- 进程标识符：PID、父id，Uid（创建进程的用户）
- 处理机状态信息：通用寄存器（用户可见寄存器）、控制和状态寄存器、栈
- 进程控制信息：优先级、数据结构、通信、特权、存储、资源使用权
程序段：程序的代码（指令序列）—-多个子进程的代码可能一样（3个qq）
数据段：运行过程中产生的各种数据
栈
特征
- 动态性：最基本、动态地产生变化消亡
- 并发性
- 独立性
- 异步性:各自独立的推进
状态
五状态模型
- 创建态（新建态）：关于该进程的信息、进程标识符在内存的进程表中，也没有为与这个程序相关的数据分配空间，但进程还在外存
- 就绪态：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行进程。
- 运行态：一个CPU只会有一个进程处于运行态，多核CPU才可以有多个进程处于运行态
- 阻塞态（等待态）：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行进程。
- 终止态：表格和其它信息暂时保留
交换技术
内存中没有就绪进程或内存空间非常紧张时，系统将内存中暂时不能运行的进程，或暂时不用的数据和程序，Swapping-out到外存，以腾出足够的内存空间，把已具备运行条件的进程或进程所需要的数据和程序，Swapping-in到内存。
挂起
概念：将内存中处于阻塞、就绪、甚至是执行状态的进程放到外存，不再参与CPU的竞争
原因
- 交换
- OS主动挂起
- 进程全部阻塞，CPU空闲
- 调试
- 父进程请求
激活挂起进程的进程就是实施挂起操作的进程——解铃还须系铃人
七状态模型
组织方式
- 链接方式：OS指针指向队列，多级队列和单一队列
- 索引方式：OS指针指向索引表
内核
内核态、系统态、特权态、管态
- 资源管理功能：进程管理、内存管理、IO管理
- 支撑功能：中断，记账、监视、时钟管理
- 可以执行指令系统的全集
用户态、常态、目态
双模式为了：保护操作系统和重要的操作系统表（如PCB）不受程序干扰
程序状态字PSR寄存器中存在指示执行模式的位
模式切换不一定会必然导致进程切换
控制
进程控制就是实现进程状态的转换、由原语来实现
创建
- 触发事件
- 用户登录
- 作业调度：为被调度的作业分配进程
- 提供服务：打印机
- 已有进程请求：由现有进程派生
2.过程
OS调用创建原语
分配唯一进程标识符
分配地址空间
初始化PCB
建立链接：插入就绪或者就绪挂起队列
建立或扩充其他数据结构
create（）
终止
- 触发事件
- 正常结束
- 异常错误：越界错误 • 保护错误 • 非法指令 • 特权指令错 • 运行超时 • 等待超时 • 算术运算错、被0除 • I/O故障
- 外界干预：Admin干预、父进程被终止、父进程终止
2.过程
OS调用撤销7原语
根据PCB读取状态
终止执行，调度下一个就绪进程执行
终结子进程，向系统或父进程归还资源
从对应的队列中移除PCB
阻塞
1.触发事件
- 请求的系统服务得不到满足
- 访问临界资源
- 等待另一进程执行结果
- 无新工作可做
阻塞原语block**()**
唤醒
1.触发事件
- 阻塞事件发生
唤醒原语wakeup()
挂起
suspend( )
激活
active()
切换
1.触发事件
- 时钟中断
- IO中断（不一定）
- 内存失效
- 陷阱：指令异常或错误
- 系统调用
2.过程
- 保存上下文 ，程序计数器和寄存器
- 更新当前执行的PCB，移动到新的队列
- 选择另外进程执行，更新PCB，移动队列
- 恢复上下文环境
执行态---就绪态：1.时间片用完 2.高优先级抢占 |
fork()
通信
inter-process communication（IPC）
- 各进程拥有的内存地址空间相互独立
共享存储—最快的
- 两个进程在内存中申请一片共享存储区，映射到自己的地址空间
- 需要保证两个进程对共享空间的访问是互斥的（P、V）操作
- 基于存储区共享：高级通信，速度快，数据形式以及位置由进程控制
- 基于数据结构：低级
- 没有用到操作系统
消息传递
- 报文格式化传递（消息头+消息体）
- 直接通信（标明ID）
- 间接通信（通过信箱）
管道通信
- 单向通信（半双工通信）
- pipe文件，实质是内存中开辟一个大小固定的内存缓冲区
- 管道中的信息先进先出，信息按队列式存储（区别与共享存储），循环队列
- 各进程的管道访问互斥（由OS实现）
- 管道满（空），写（读）进程阻塞
- 多个读会混乱->解决方案：1.（主）多个写一个读 2.多个写多个读，OS让各个读进程轮流读取（Linux）
线程
轻量级进程(LWP)
实现进程内部的并发
进程是资源分配的基本单位，线程是调度的基本单位，线程的切换开销较小
拥有少量私有资源
⚫ 线程控制块(含PC、寄存器、线程状态等信息)、栈等
相比进程的优点
进程可以并发不可以并行；进程可以并发也可以并行
创建、结束开销和时间
切换的速度块
相同的地址空间，通信快
有些进程的操作无需内核干预
状态
就绪、执行、阻塞
一般没有挂起态度
操作功能
- 派生：创建进程->线程、线程->线程
- 阻塞
- 解除阻塞
- 结束
实现方式
用户级线程：调度实体是线程映射到内核上的实体 |
用户级线程
- 早期
- 由应用程序通过线程库实现，非OS
- 线程切换只需要在用户态下，无需切换核心态，系统开销小效率高
- OS不能看到用户级线程存在，OS眼中只有进程，OS看操作以进程为单位
- 缺点：**并发度不高 ** 一个线程阻塞会造成整个进程阻塞，
- 即使多核CPU，一个进程对应一个CPU，线程无法并发
- 切换速度更快
- 线程数目增加，进程速度降低
调度时，系统调度执行时间只用一个时间片调度开始主要针对运行态
**内核级线程**
- 基于OS管理
- 线程的切换需要CPU变态
- 优点：并发性强，不会因为单个线程的阻塞影响进程
- 线程是CPU调度的基本单位，进程是分配资源的基本单位
- 缺点：一个进程占用多个内核线程，管理成本高，切换开销大
- 线程数目增加，进程速度增加
- 用户级线程即使多处理机也无法实现线程并行；内核级线程多处理机可以实现真正的线程并行
---
补充
- TCB（线程控制块）
-
## 调度
|
方式
非剥夺调度方式（非抢占方式）：早期，开销小，无法处理紧急任务、批处理
剥夺调度方式（抢占方式）：适合分时
抢占：1.优先级高 2.短进程到达 3.时间片用完 1、2必须通过运行的进程激活调度线程才可以重新调度，否则难以完成抢占 3由时间片用完后硬件中断进行调度 所以时间片轮转是绝对抢先的算法只进程调度：RR、优先级调度、多级反馈队列 进程&作业调度：FCFS、SJF/SPF、HRRN进程时间片用完可以降低其优先级；完成IO进程应提升其优先级；处于就绪队列等待调度的进程一般不会改变其优先级
### 评价指标
- CPU利用率：busy time/whole time
- 系统吞吐量：作业/时间
- 周转时间（For user，越小越好）：作业完成的时间-作业提交给系统的时间
- 平均周转时间：（For OS）各个作业周转时间之和/作业数
- 带权周转时间（>=1,越小越好）：周转时间/作业实际运行的时间
- 平均带权周转时间：各个作业带权周转时间之和/作业数
- 等待时间（越小越好）：等待CPU处理的时间之和（作业的等待时间因为包含等待I/O完成时间，**进程的等待时间不包括I/O**,所以大于进程的等待时间）
- 响应时间：user提出请求到响应的时间
---
面向用户的规则：响应时间、周转时间、截止时间
面向系统的规则：吞吐量、利用率、公平性、优先级
### 调度算法
FCFS（先来先服务）
- 考虑作业先到达**后备队列**（在外存），进程先到达**就绪队列**（在内存）
- 非抢占式算法
- 优点：公平简单
- 缺点：对于一个排在长进程或者作业的短作业或者进程，用户体验不好（奶茶店）
- 不会导致饥饿
SJF（SPF）（短作业（进程）优先）
- 非抢占
- 抢占式（SRTN）：**最短的平均等待、周转时间**
- 不断地短进程进入，可能会导致**饥饿**
HRRN（高响应比优先）-----**人机交互**
- 响应比：（等待时间+要求服务时间）/要求服务时间
- 非抢占
- 不会导致饥饿
时间片轮转（RR）
交互
- 用于进程调度，只有作业放入内存建立相应的进程才能被分配处理机的时间片
- 抢占式，由时钟中断剥夺时间
- 用于分时操作系统，关心响应时间，不计算周转时间
- 时间片不能太大，切换进程的开销不超过1%
- 优点：公平，响应快
- 缺点：增大开销，不区分紧急
- 不会导致饥饿
优先级调度算法
- 作业进程I/O调度
- 抢占|非抢占
- 抢占式就绪队列中的优先级不是由谁先到达决定，由优先权值决定
- 系统进程>用户进程
- 前台进程>后台进程
- I/O繁忙型进程>CPU繁忙型进程（计算型进程）
- 优点：灵活调整，实时操作系统，适合紧急重要
- 会导致饥饿
多级反馈队列调度算法
- 进程调度
- 抢占式
-
-
## 并发互斥
### 概念
- 临界区：把在每个进程中访问临界资源的那段代码称为临界区
- 临界资源：一个时间段内只允许一个进程使用的资源，eq：物理设备等
- ```
进程在操作系统内核程序临界区不能进行调度与切换，在普通临界区能够调度与切换并发进程之间存在信息交换时，一定共享某些资源semaphore offer1 = 0;//提供卷纸和火柴 semaphore offer2 = 0;//提供火柴和烟草 semaphore offer3 = 0;//提供卷纸和烟草 semaphore finish = 1;//通知供应者继续提供材料
- 互斥：当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问共享资源
- 死锁：两个或两个以上的进程相互等待导致都不能执行
- 竞争：多个进程读写一个共享变量，该变量的最终值依赖它们执行的相对速度
- 饥饿：一个进程已经完全具备了执行的条件，但是得不到CPU资源
-------
### 原则
- 空闲让进：当没有进程在临界区时，允许一个请求进入临界区的进程进入临界区
- 忙则等待：当临界区存在进程，其他想要进入临界区的的进程必须等待
- 有限等待：对于一个进入临界区的请求，应当在有限时间内得到满足
- 让权等待：进程不能进入临界区时，应当释放调处理机资源
### 软件算法
**单标志法**
**双标志先检查法**
**双标志后检查法**
**Peterson算法**
### 互斥的硬件实现方法
#### 中断屏蔽方法
- 优点：简单高效
- 缺点：不适用多处理机；只适用内核进程，不适用于用户进程
#### TestAndSet（Lock）TSL指令
- 一气呵成、**原子**操作，简单，适用于多处理机
- 不满足让权等待
-
#### Swap(Exchange)(XCHG)指令
### 信号量机制
**软件和硬件都需要循环等待**
- 原语+信号量
- 一对原语：wait(S) & signal(S) [proberen （尝试）& verhogen（增加）] [P(S) & V(S)]
#### 整型信号量
**未实现让权等待**
#### 记录型信号量（semaphore）
**满足四条准则**
单缓冲不用mutex进行互斥
### 生产者消费者
### 多生产消费者
### 吸烟者问题
//供应者进程
Provider(){
int rand;
while(true){
P(finish);
rand = getRandom()%3;
if(rand == 0){
V(offer1);
}else if(rand == 1){
V(offer2);
}else{
V(offer3);
}
}
}
//吸烟者1
Smoker1(){
while(true){
P(offer1);
制作香烟并消耗；
V(finish);//通知供应者继续提供材料
}
}
//吸烟者1
Smoker2(){
while(true){
P(offer2);
制作香烟并消耗；
V(finish);//通知供应者继续提供材料
}
}
//吸烟者3
Smoker3(){
while(true){
P(offer3);
制作香烟并消耗；
V(finish);//通知供应者继续提供材料
}
}
|
并发性：检测解除>避免死锁>预防死锁
|
动态重定位（动态运行时装入）
- 编译就是把高级语言翻译为机器语言
链接方式
工作：1.修改相对地址 2.变换外部调用符号
- 静态链接
- 装入时动态链接
- 运行时动态链接
内存管理
OS负责内存空间的分配回收
采用多种技术对内存空间扩充
实现地址转换，实现逻辑地址和物理地址的转换（三种装入方式）
内存保护—保护各个进程互补
设置上下限寄存器
- 利用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行判断
覆盖和交换
覆盖技术
早期使用
交换技术
对换区一般采用连续分配，换入及换出操作由内存管理模块完成，与程序结构无关
交换发生在进程或作业之间，覆盖发生在同一进程或作业内
连续分配管理方式
外部碎片和内部碎片是计算机系统中与内存管理相关的两个概念。
外部碎片（External Fragmentation）：
- 外部碎片指的是已分配的内存空间中，存在于已分配块之间的一些小块未被使用的内存。虽然总的可用内存可能足够，但由于空闲内存分散在已分配块之间，导致某些时候无法找到足够大的连续内存块来满足需要。这种情况会导致系统效率下降，因为不能有效地利用可用内存。
内部碎片（Internal Fragmentation）：
- 内部碎片是指已分配的内存块中，由于内存分配算法或数据结构的原因，实际使用的内存空间比分配的内存块大。这意味着分配的内存块中有一部分内存未被有效利用，造成了内存资源的浪费。
例子：
考虑一个内存中有两个已分配块：块 A 和块 B。块 A 的大小为 30KB，块 B 的大小为 50KB，释放块A。如果一个进程需要分配 40KB 的内存，由于没有足够大的连续内存块，系统无法满足请求，尽管总的可用内存是足够的。这就是外部碎片的例子。
另外，如果一个进程分配了一个 60KB 的内存块，但实际只使用了其中的 50KB，那么就会有 10KB 的内部碎片，因为有一部分内存被浪费了。
解决外部碎片和内部碎片的问题通常需要采用不同的内存管理策略和算法，例如使用紧凑算法来减少外部碎片，或者采用更灵活的内存分配策略来减少内部碎片。
单一连续分配
固定分区分配
动态分区分配
空间可以合并
首次适应算法
最佳适应算法
最坏适应算法
循环匹配算法
可重定位分区分配：采用动态重定位技术的分区分配方式
伙伴系统
- 递归查询使用
非连续分配管理方式
段页对比
1.页带来的内部碎片无法消除 |
基本分页存储
页框
- 内存空间分为大小相等的分区 页框=页帧=内存块=物理块=物理页面
- 每个页框有页框号=页帧号=内存块号=物理块=物理页号 从0开始
- 块越大，内/外存之间的数据交换效率越高。
页
将逻辑地址空间分为和页框大小相等的页or 页面，编号为页号
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。
各个页面不必连续存放，可以放到不相邻的各个页框中。
页表
页表通常在PCB中
OS为每个进程建立页表，存储在PCB中
页面内部连续，内存中离散存放
一个进程对应一个页表
反应 页和页框的映射
页表项大小=页号+块号 页号隐藏不占空间
页表项在内存中是连续的，块中不连续
虽然进程的各个页面是离散存放的，但是页面内部是连续存放的
段对用户可见，页对用户不可见
地址转换
- 逻辑地址A对应的物理地址=p号页面在内存中的起始地址+页内偏移量W
基本地址变换机构
快表
TLB、联想存储器、关联存储器、旁路存储器
按照内容寻址
TLB中只能放页表项的副本，cache中可以放其他数据
访问速度比内存快很多的缓存 不是内存
用于存放最近的页表项的副本，页被称为慢表
加入快表的地址转换过程 局部性原理
- 一次和两次
两级页表
存在的问题
建立页表的页表：页目录表
- 需要注意的细节
n级页表的访存次数是：n+1（没有快表的情况下）
基本分段存储管理
分段
段表
地址变换
- 和分页的区别：页大小固定，不需要进行页内偏移量和页长的越界比较
段页式管理
段页式管理的段表和分段储存管理的段表不一样，页表一样
地址变换过程
虚拟存储
虚拟存储器
虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
虚拟存储器允许程序访问比内存更大的地址空间；而不是访问比地址字长更大的空间 |
传统管理方式的缺点
- 一次性：作业必须一次性装入内存后才能开始运行，导致作业很大无法装入以及多道程序并发度下降
- 驻留性：作业被装入内存后会一直驻留在内存中
虚拟内存的定义和特征
物理内存大小没变，逻辑上进行扩充
离散性
局部性
对换性
虚拟性
请求分页存储管理
新增：
- 请求调页功能：将缺失页面从外存调入内存
- 页面置换：暂时用不到的页面换出外存
页表机制
缺页中断机构
普通中断：恢复后执行断点处下一条指令 |
- 当要访问的页面不在内存时，产生缺页中断，由操作系统中的缺页中断处理程序处理中断
- 此时该进程阻塞，进入阻塞队列，调页完成后再将其唤醒，进入就绪队列
分配情况
- 若有空闲块，则直接进行分配并装入，修改页表中的表项
- 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
特性
属于内中断
一条指令的执行可能产生多次缺页中断
地址变换机构
- 与基本分页的主要区别：访问的信息不在内存。需要从外存调入；内存空间不够时，由OS将内存中暂时不用的换出到外存
- 请求调页
- 页面置换
- 修改表项
在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是:
查快表(未命中)—―查慢表(发现未调入内存)――调页(调入的页面对应的表项会直接加入快表)―一查快表(命中)―一访问目标内存单元
页面置换算法
缺页率=缺页次数/访问次数
最佳置换算法OPT
belady提出
- 选择淘汰：以后永不使用或者长时间不再被访问，保证最低的缺页率
- 当满了后，选择内块中的所有往后寻找最后一个淘汰的页面然后淘汰
- 该算法无法实现
FIFO
- 性能很差，会发生Belady现象—–本质：局部性原理
最近最久未使用置换算法（LRU）
- OPT的逆推
- 需要硬件支持，性能好，开销大
时钟置换算法（CLOCK）（NRU）
用到了访问位（引用位）+修改位
访问大于优先
页面分配、置换策略
驻留集
- 概念：指请求分页存储管理中给进程分配的物理块的集合。
- 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
- 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少
- 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
分配策略：
- 固定分配
- 可变分配
置换策略：
- 局部置换
- 全局置换
WHEN
HOW
抖动
- 分配太多—-降低CPU利用率
- 分配太少—-降低整体并发度
- 产生原因：系统分配的物理块不够
工作集
- 根据工作集的大小确定驻留集的大小
- 驻留集>=工作集
内存映射文件
文件
- 一组由意义的信息或者数据的集合
文件系统：文件 和 对文件进行操纵管理的软件集合 |
实际上是对外存（辅存）管理 |
文件的属性
- 文件名：同一目录不允许有重名文件
- 标识符：对用户无可读性
- 类型：.xx
- 位置：绝对路径和外存地址（OS使用，对用户不可见）
- 大小
- 创建时间
- 上次修改时间
- 文件所有者信息
- 保护信息
组织
内部数据
无结构文件：如txt,由二进制或字符流组成，流式文件
有结构文件：如数据库表，由一组相似的记录组成，又称记录式文件——顺序文件、索引文件、索引顺序文件
访问基本单位是：记录
记录型文件是具有符号名并在逻辑上有完整意义的记录序列打开文件系统调用的基本操作是：将文件FCB从外存读到内存
文件之间的组织
- 树
- 目录：特殊的有结构文件
OS应该向上提供的功能
- 创建文件 create
- 删除文件 delete
- 读文件 read
- 写文件 write
- 打开文件 open
- 关闭文件 close
其他文件管理功能
- 文件共享
- 文件保护
逻辑结构
- 无结构文件不讨论
- 有结构文件：
- 由一组相似的记录组成，又称“记录式文件”。
- 每条记录又若干个数据项组成。如:数据库表文件。
- 一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID)
- 根据记录的长度，可以分为定长和可变长记录
顺序文件
- 链式存储：无论定长或者可边长，无法实现随机存取，每次只能从第一个记录开始依次往后查找
- 顺序存储
- 可变长：无法实现随机存取，每次只能从第一个记录开始依次往后查找
- 定长
- 可实现随机存储，记录长度为L，第i个记录的相对位置是：i*L
- 采用串结构，无法快速通过关键字检索
- 采用顺序结构，可快速通过关键字检索，顺序文件指的是物理上顺序，缺点是增删记录比较困难
索引文件
- 建立索引表
- 索引表:定长记录的顺序文件，连续存放 可变长记录文件不连续
- 可将多个不同的关键字作为索引号内容
- 用于对信息处理的及时性要求比较高的场合
缺点：索引表过大降低存储空间利用率
索引顺序文件
二者的集合，与索引文件不同，并不是每个记录建立一个索引表项，而是一组记录对应一个索引表项，对记录进行分组
- 建立多级索引顺序文件，大大减少
文件目录
文件控制块
- 一个FCB就是一个文件目录项，FCB的有序集合称为文件目录
- FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。
- 实现了文件名和文件之间的映射，让User实现按名存取
目录结构
单极目录结构
- 支持按名存取，不允许文件冲名
- 不适用于多用户系统
两级目录结构
主文件目录：记录用户名
用户文件目录：记录用户的文件
允许重名；可以实现访问限制；缺点不能进行分类
多级目录结构
- 树
- 从根目录出发的路径叫绝对路径
- 引入当前目录和相对路径
- 缺点：不便于实现文件的共享
无环图目录结构
索引节点 FCB的改进
- 当找到文件名对应的目录项时，才需要将索引结点调入内存
- 索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
- 存放在外存中的索引结点称为**“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。**
- 相比之下内存索引结点中需要增加一些信息，比如:文件是否被修改、此时有几个进程正在访问该文件等。
文件的物理结构
连续分配
要求每个文件在磁盘上占有一组连续的快
- 连续分配方式要求每个文件在磁盘上占有一组连续的块。
- 优点:支持顺序访问和直接访问（即随机访问)﹔连续分配的文件在顺序访问时速度最快
- 缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片
链接分配
隐式链接
- 隐式链接――除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
- 优点:很方便文件拓展，不会有碎片问题，外存利用率高。
- 缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
显式链接
- 优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
- 缺点:文件分配表的需要占用一定的存储空间。
考试题目默认隐式链接
索引分配
链接方案
多层索引
混合索引 unix采用
总结
文件存储管理
空闲表法
空闲链表
相关计算：寻址
- 计算所在的逻辑块号：当前地址除以磁盘块的大小，商是块号，余数是块内偏移量
- 计算索引块中的项目数：磁盘块的大小除以每个地址项（盘块号）的大小，在下面的题目中这个值是$$2^{8}=256$$
- 查找逻辑块号：在下面的题目中，$$0\sim9$$是直接块，$$10+0\sim10+2^8-1$$是一级间接块，分别对应索引块 428 的 $$0\sim2^8-1$$；$$10+2^8+0\sim10+2^8+2^8-1$$是二级索引第0个地址指向的二级间接块，分别对应索引块 331 的$$0\sim2^8-1$$，等。
- 位示图法
- 成组链接法
共享
硬链接
软链接
设备管理
I/O设备
input & output
分类
- 人机交互
- 存储设备
- 网络通信设备
速度
- 低俗
- 中速
- 高速
单位
- 块设备：磁盘，可寻址：随机读写
- 字符设备：鼠标 不可寻址，输入输出采用中断驱动；打印机 采用中断驱动
资源性能
独占设备静态分配 |
- 独占设备：打印机
- 共享设备：磁盘
- 虚拟设备
I/O控制器 AKA电子部件
扩展卡或者南桥芯片内
组成
程序直接控制方式
中断驱动方式
DMA 直接存储器存储
绕过cpu
通道
类型
- 字节多路通道
- 数组选择通道
- 数组多路通道
解决“瓶颈”问题的最有效的方法，便是增加设备到主机间的通路，而不增加通道。
I/O软件层次结构
用户层软件
- 实现用户交互的接口
- 通过调用相关的库函数队设备进行操作，然后翻译成格式化的I/O请求通过系统调用请求OS内核的服务
设备独立性软件
设备独立性是指用户程序独立于具体使用的设备 |
AKA:设备无关性软件
- 为上层提供系统调用接口：read/write
- 设备的保护：权限
- 差错处理
- 设备的分配与回收
- 数据缓冲器管理
- 建立：逻辑设备名到物理设备名的映射关系 逻辑设备表****LUT
设备驱动程序
- 负责对硬件设备的具体控制
中断处理程序
只有设备驱动程序和中断处理程序是直接和硬件打交道的
I/O核心子系统
IO重定向：调试过程中输出结果送到屏幕显示，不必正式输出到打印设备 |
SPOOLING假脱机技术
学名：在联机情况下实现同时外围操作的技术 |
目的：解决资源互斥和提高设备利用率
脱机：脱离主机的控制进行的输入/输出操作—缓解了CPU与慢速io设备的速度矛盾
共享打印机
独占——>共享
设备的分配与回收
分配考虑的因素
- 固有属性：独占、共享、虚拟
- 分配算法
- 安全性
- 设备无关性（独立）：只使用逻辑设备名管理设备，映射表；采用统一方式管理设备
缓冲区
在内存中建立I/O缓冲区，硬件内存比如快表
缓冲区管理中最重要的问题是：实现进程访问缓冲区的同步 |
单缓冲
单双工
双缓冲
全双工
循环缓冲
缓冲池
磁盘
基本概念
调度算法
FCFS
SSTF 最短寻找时间优先
SCAN扫描算法
LOOK调度算法
C-SCAN 循环扫描算法
C-LOOK
减少延迟时间
转两圈读一圈
交替编号
错位命名
磁盘管理
磁盘初始化
引导块
|
坏块管理
硬件故障
固态硬盘SSD
image-20231208122123162
微信- 支付宝
