王道考研--操作系统
2021-04-08 17:01:04 107 举报AI智能生成
登录查看完整内容
王道考研--操作系统，是一本针对计算机科学与技术专业考研学生编写的操作系统教材。本书全面系统地介绍了操作系统的基本概念、原理和实现技术，包括进程管理、内存管理、文件系统、设备管理等内容。同时，本书还注重实践操作，通过大量的实例和实验帮助学生深入理解和掌握操作系统的核心知识。此外，本书还提供了丰富的习题和解析，帮助学生巩固所学知识并提高解题能力。总之，王道考研--操作系统是一本内容全面、结构清晰、实用性强的操作系统教材，是考研学生备考操作系统科目的必备参考书。
作者其他创作
大纲/内容
操作系统
操作系统初识
定义和定位
定义
操作系统是控制管理计算机系统的硬软件，分配调度资源的系统软件
定位
计算机系统的层次结构
裸机（纯硬件）
负责调用硬件软件资源
用户程序/用户操作
操作系统扮演的角色
1、系统资源的管理者
需要提供的功能
1、处理机管理
2、存储器管理
3、文件管理
4、设备管理
目标
安全、高效
2、用户和计算机硬件间的接口
命令接口（允许用户直接使用）
联机命令接口
用户输入一条指令，操作系统干一件事
脱机命令接口（批处理命令接口）（.bat批处理文件）
用户输入一批指令，操作系统一条一条执行下去
程序接口（允许用户通过程序间接使用）（.dll文件）
程序接口 = 系统调用
GUI（图形用户界面）（现代操作系统最流行图形用户接口）
统称为“用户接口”
方便用户使用
操作系统的特征
并发
微观交替执行、宏观同时执行
并发和并行
并发是交替执行
用户看起来是每个程序都在运行，实际上是每个程序都交替执行，一个cpu同一时刻只有一个程序在运行
并行是同时执行
多核CPU可以实现并行
共享
两种资源共享方式
互斥共享方式
同时共享方式
虚拟
虚拟技术
空分复用技术
如虚拟存储技术
时分复用技术
如虚拟处理器
异步
多个程序的执行由于资源的限制而走走停停，以不可预知的速度推进，这就是进程的异步性
最基本的特征，互为存在条件
如果系统没有并发性，就谈不上虚拟和异步
操作系统的发展和分类
手工操作阶段
打孔机实现
打孔就是1，不打孔的就是0
缺点
用户独占全机，用户操作慢，机器处理快，资源利用率很低
批处理阶段
单道批处理系统
引入脱机输入/输出技术（用磁带完成），监督程序（操作系统的雏形）负责控制作业的输入、输出
外围机负责把纸带的信息写入到磁带中
cpu直接读磁带上的数据
优点
缓解了人机速度的矛盾
cpu大多时间在等待I/O完成，资源利用率依然很低
多道批处理系统
每次往内存里输入多道程序
操作系统正式诞生，并引入了中断技术，由操作系统负责管理程序的运行。各个程序并发执行
多道程序并发执行，共享计算机资源。资源利用率大幅提升，系统吞吐量增大
用户响应时间长，没有人机交互功能（不能中途控制作业的执行）
为何多道批处理系统可以使资源利用率大幅提升？
单道批处理
多道批处理
分时操作系统
以时间片为单位轮流为各个用户/作业服务
用户请求可以及时响应，解决了人机交互问题，允许多个用户同时使用一台计算机，并且用户感觉不到别人的存在
不能优先处理紧急的任务，操作系统对于每个用户/作业时绝对公平的，完全按照循环方式为每个用户分配时间片
实时操作系统
硬实时系统
如导弹控制系统、自动驾驶系统
严格要求在时限内处理完事件
软实时系统
12306订票系统
接受偶尔违反时间规定
能够优先响应一些紧急任务，某些紧急任务不需要排队获取时间片
网络操作系统
分布式操作系统
个人计算机操作系统
需要掌握
了解即可
操作系统的运行机制和体系结构
⭐运行机制
两种指令
特权指令
不允许用户程序使用
非特权指令
两种处理机状态
核心态（管态）
管态可以处理所有指令
用户态（目态）
目态只能处理非特权指令
使用程序状态字寄存器（PSW）中的标志位标识，0是目态，1是管态中断机制是CPU运行状态切换的唯一途径
两种程序
内核程序
操作系统的内核程序是系统的管理者，运行在管态
应用程序
普通的应用程序运行在目态
操作系统内核（是计算机的底层软件，是操作系统最基本、最核心的部分） 不同操作系统的内核划分不同
时钟管理
实现计时功能
中断处理
负责实现中断机制
原语
是一种特殊的程序，这种程序运行具有原子性
处于操作系统最底层，是最接近硬件的部分
运行时间段、调用频繁
对系统资源进行管理的功能
进程管理
存储器管理
设备管理
操作系统的体系结构
大内核
将操作系统的主要模块都作为操作内核，运行在管态
性能高
内核代码结构庞大，混乱，难以维护
微内核
只把最基本的功能保留在内核
内核功能少，结构清晰，方便维护
需要频繁的在目态和管态之间切换，性能低
结构图
中断和异常
中断机制的作用
为了在多道批处理系统中让用户进行交互
⭐中断产生
发生中断时，CPU立马切换到管态，开展管理工作
发生中断后，当前运行的进程回暂停运行，由操作系统内核对中断进行处理
对于不同的中断信号，会进行不同的处理
⭐中断的分类
内中断（也叫“异常”、“例外”、“陷入”）
自愿中断---指令中断
如系统调用时使用的访管指令（又称陷入指令、trap指令）
强迫中断
硬件故障
如缺页
软件中断
如整数除0
信号来源：CPU内部，与当前执行指令有关
外中断（中断）
外设请求
如I/O操作完成发出的中断信号
人工干预
如用户强行终止一个进程
信号来源：CPU外部，与当前执行指令无关
⭐外中断的处理过程
1、每执行完一个指令后，CPU都需要检查当前是否有外部中断 信号
2、如果检查到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW，程序计数器PC、各种通用寄存器）把他们存储在PCB（进程控制块中）
3、根据中断信号类型转入相应的中断处理程序
4、恢复原进程的CPU环境并退出中断，返回原进程继续执行
系统调用
什么是系统调用
可以被应用程序调用的特殊函数，提供给程序员使用的接口
系统调用的作用
应用程序通过系统调用请求操作系统的服务，由操作系统代为完成以防止多个程序同时调用造成混乱
系统调用的分类
凡是和资源有关的操作、会直接影响到其他进程的操作都需要通过系统调用实现，让操作系统介入
文件管理
进程通信
内存管理
系统调用和库函数的区别
应用程序使用高级编程语言封装好的库函数来调用操作系统的系统调用
系统调用背后的过程
高级语言编译成汇编语言指令
用户程序执行汇编语言指令（目态）
执行到int x指令（trap/陷入/访管指令），这里的int是interupt，中断请求
陷入指令只唯一一个只能在目态执行的指令
切换到核心态，处理系统调用的相关代码
切换回目态，用户程序继续执行后续的汇编指令
进程
⭐进程初识
⭐进程的定义
⭐进程是一段程序运行的过程
⭐进程是资源分配的基本单位
⭐PCB是进程存在的唯一标识
进程和进程实体一般可以认为是相等的
进程是动态的
进程实体是静态的
⭐进程的组成
程序段
存放的就是代码本身
数据段
存放程序运行的变量、常量
PCB
⭐定义
⭐操作系统管理进程的一种数据结构
组成
进程描述信息
进程标识符PID
用户标识符UID
进程控制和管理信息
进程当前状态
进程优先级
资源分配清单
程序段指针
数据段指针
各种设备
处理机相关
各种寄存器值
组织方式
链接方式（队列）
按照进程状态将PCB分为多个队列
操作系统持有指向各个队列的指针
索引方式（索引表）
根据进程状态的不同，建立几张索引表
操作系统草幽指向各个索引表的指针
特征
动态性
进程是程序的一次执行过程
并发性
内存中有多个进程，各个进程可以
独立性
进程是资源分配的基本单位
异步性
各进程以不可预知的速度向前推进，可能导致运行结果不确定
结构性
每个进程都由代码段、数据段、PCB组成
⭐进程的状态和转换
进程的状态
创建状态
⭐就绪态
已具备运行条件，但是没有拿到CPU
⭐运行态
占有CPU，并在CPU上运行
⭐阻塞态
因为等待某一时间而暂时不能运行
终止状态
进程间的转换
就绪 -> 运行
运行 -> 就绪
运行 -> 阻塞
阻塞 -> 就绪
图解
七状态转换
进程控制
基本概念
进程控制就是要实现进程状态的转换
进程控制用原语实现
原语用关/开中断实现
关/开中断是特权指令
相关原语
阻塞和唤醒要成对出现
进程的创建
进程的终止
进程的阻塞
进程的唤醒
进程的切换
共享存储
设置一个共享空间
互斥访问共享空间
两种方式
基于数据结构（低级）
基于存储区（高级）
管道通信
设置一个特殊的共享文件（管道），其实就是一个缓冲区
一个管道只能实现半双工通信
实现全双工通信需要建立两个管道
各进程要互斥访问管道
⭐写满时，不能再写。读空时，不能再读
⭐没写满，不能读。没读空，不能写
消息传递
传递结构化的消息（消息头、消息体）
系统提供“发送/接受”原语
直接通信方式
消息直接挂到接收方的消息队列后
间接（信箱）通信方法
消息先发送到中间体（信箱）
线程、多线程模型
什么是线程
轻量级的进程
资源调度的基本单位
为什么要引入线程
增加并发度，减少并发时进程切换带来的开销
线程的重要属性
处理机掉的的单位
同一进程的各线程共享该进程的资源
同一进程内线程的切换不会导致进程的切换
线程的实现方式
用户级线程
用户角度的线程
内核级线程
操作系统角度的线程（内核级线程才是处理机分配资源的单位）
组合方式
以上二种方式的组合
多线程模型
多对一模型
进程管理开销小效率高
一个线程阻塞，会导致整个进程阻塞
一对一模型
各个线程可分配到多核处理机并行执行，并发度高
进程管理开销大
多对多模型
集合二者
处理机调度
按某种算法选择一个进程将处理机分配给它
三层调度
高级调度（作业调度）
从后备队列中选择合适的作业调入内存，为其创建进程
中级调度（内存调度）
从挂起队列中选择合适的进程将其调回内存
低级调度（进程调度）
从就绪队列选择一个进程为其分配处理机
三层调度的联系和对比
外存 --> 内存
面向作业
发生频率
最低
面向进程
中等
内存 --> CPU
最高
补充知识
为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存变成“挂起态”
七状态模型
在五状态模型基础上添加就绪挂起和阻塞挂起状态
进程调度
时机
什么时候需要进程调度？
主动放弃
进程正常终止
运行过程中发生异常而终止
主动阻塞（如等待I/O）
被动放弃
分给进程的时间片用完
有更紧急的事情需要处理（如I/O中断）
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度
在处理中断过程中
进程在操作系统内核程序临界区中
原子操作过程中
切换和过程
狭隘的调度和切换的区别
切换过程
对原来运行进程各种数据进行保存
对新的进程各种数据的恢复
重要结论
进程调度、切换时有代价的，并不是调度越频繁，并发度就越高
方式
非剥夺调度方式（非抢占式）
只能由当前运行的进程主动放弃CPU
剥夺调度方式（抢占式）
可由操作系统剥夺当前进程的CPU使用权
⭐调度算法
先来先服务（First Come First Serve---FCFS）
非抢占式调度
不会导致饥饿
公平
对短作业不利
短作业优先（Shortest Job First---SJF）
分类
抢占式的SJF
非抢占式的SJF
SJF默认非抢占式
可能会导致饥饿
最短的平均等待时间、平均周转时间
不公平，可能存在进程饥饿
高响应比优先（Highest Response Ratio Next---HRRN）
响应比 = （等待时间 + 要求服务时间）/ 要求服务时间
非抢占式的调度算法
优缺点
集合上两种算法的权衡折中
时间片轮转（Round-Robin---RR）
抢占式的调度算法
如果时间片设置太大，就会退化成先来先服务算法
如果时间片设置太小，进程切换太频繁
公平、响应快
不区分紧急程度
优先级调度
抢占式
非抢占式
既可用于作业调度、又可用户进程调度
可以用优先级区分紧急程度
可能存在饥饿
多级反馈队列调度
其他各种算法的折中权衡
存在多个反馈队列来存储进程，优先级越高，时间片越短，新到达的进程优先级最高，随着进程执行时间的增长优先级会降低
调度算法衡量指标
周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 运行时间
等待时间 = 周转时间 - 运行时间
平均周转时间 = （所有进程的周转时间相加）/ 所有进程的个数
平均带权周转时间 = （所有进程的带权周转时间相加）/ 所有进程的个数
平均等待时间 = （所有进程的等待时间相加）/ 所有进程的个数
⭐进程同步
实现互斥的开始代码段
实现互斥的结束代码段
进入区
检查是否可以进入临界区，设置访问临界区资源标志
临界区
访问临界资源的代码块
退出区
解除访问临界区资源的标志
剩余区
做其他的操作
⭐进程互斥的原则
空闲让进
忙则等待
有限等待
让权等待
进程互斥的实现方法（了解）
软件层面
单标志法
在进入区检查，不上锁
在退出区把临界区的使用权交给另一个进程
主要问题
不遵循空闲让进
双标志先检查
在进入区先检查后上锁，退出区解锁
不遵循忙则等待
双标志后检查
进入区先检查后加锁，退出区解锁
不遵循有限等待
可能导致进程饥饿
Peterson算法
在进入区“主动争取-主动谦让-检查对方是否想进、己方是否谦让”
不遵循让权等待
会发生忙等
硬件层面
中断屏蔽
使用
关中断
访问临界区
开中断
简单、高效
不适合多处理机
只适用于操作系统内核进程
TestAndSet（TS指令/TSL指令）
与CAS机制相同
Swap指令（XCHG指令）
⭐信号量机制
整型信号量
wait
singal
资源数加一，进入退出区
记录型信号量
实现进程互斥
1、划分临界区
2、设置互斥信号量mutex，初始值为1
3、在临界区进去前，执行P（mutex）操作
4、在临界区执行结束后，执行V（mutex）操作
文件示例
pre style=\
实现进程同步
1、设置互斥信号量S，初始值为0
前驱图
生产者和消费者问题（多个类别对应多个类别）
哲学家问题
有5个哲学家，并且只有5只筷子在5个哲学家的中间
解决方法
先拿左边，再拿右边
可能导致死锁现象
每个哲学家拿到一个筷子，造成环路等待
先拿左边，再拿右边，并且只有4个哲学家在进程竞争
至少有一个哲学家是可以正常进餐的
偶数哲学家先拿左，奇数哲学家先拿右
拿左右筷子前后加PV操作，形成连贯的操作
管程
为什么要引入管程
解决信号量机制编程麻烦、易出错的问题
组成（类似Java中的类）
共享数据结构
对数据结构初始化的语句
一组用来访问数据结构的过程（函数）
基本特征
各外部进程/线程只能通过管程提供的特定的入口才能访问数据
每次仅允许一个进程在管程内执行某个内部过程
补充
各进程必须互斥访问管程的特性 是编译器实现的
可在管程中设置条件及等待/唤醒操作以解决同步问题
⭐死锁
进程死锁、饥饿、死循环的区别
死锁
各个进程互相等待对方手里的资源，导致每个进程都被阻塞
饥饿
由于长期得不到资源导致进程无法推进
死循环
代码逻辑BUG
死锁产生的必要条件
互斥条件
必须互斥使用资源才会产生死锁
不剥夺条件
资源只能由进程主动释放
请求和保持条件
进程已经至少保持一个资源，并同时请求别的已经被占用的资源
循环等待条件
资源等待形成环
⭐循环等待不一定造成死锁，但是死锁一定有循环等待
什么时候会发生死锁
对竞争资源分配不合理时会发生死锁
死锁的处理策略
不允许死锁发生
静态策略
预防死锁
破坏互斥条件
将临界资源改造成共享资源（Spooling池化技术）
可行性不高，很多时候无法破坏互斥条件
破坏不剥夺条件
方案一
申请到资源不满足时，立刻释放所有资源
方案二
申请的资源被占用时，由操作系统协助剥夺（考虑优先级）
实现复杂
剥夺资源可能导致部分工作失效
反复申请和释放造成额外的系统开销
破坏请求和条件
运行前分配所有需要的资源
资源利用率低
可能导致别的线程饥饿
破坏环路等待条件
顺序资源分配法
各资源编号，从小编号开始申请资源
不方便新增设备资源
进程实际使用资源顺序和编号顺序不同，会导致资源浪费
动态策略
⭐避免死锁
安全序列
银行家算法
检查当前资源剩余是否可以满足某个进程的最大需求
如果可以，就把该进程加入安全序列，等待进程允许完成，回收所有资源
重复1，2，直到当前没有线程等待资源
允许死锁发生
死锁的检测和解除
死锁的检测
数据结构
资源分配图
两种节点
进程节点
资源节点
两种边
进程节点--->资源节点
请求边
资源节点--->进程节点
分配边
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
注：所谓不阻塞线程是指其申请的资源数还足够的进程
死锁定理
如果资源分配图是不可完全简化的，说明发生了死锁
死锁的解除
资源剥夺法
撤销进程法（终止进程法）
进程回退法
基础知识
什么是内存、有何作用
存储单元、内存地址的概念和联系
按字编址 VS 按字节编址
进程允许的基本原理
指令的工作原理
操作码+参数（可能包含地址参数）
逻辑地址（相对地址）VS 物理地址（绝对地址）
从写程序到程序运行
编辑源代码
编译
由源代码文件生成目标模块，链接后形成玩着的逻辑地址
链接
由目标模块生成装入模块，链接后形成完整的逻辑地址
装入
将装入模块装入内存、装入后形成物理地址
三种链接方式
静态链接
装入前链接成一个完整 装入模块
装入时动态链接
运行前装入链接
运行时动态链接
运行时需要目标模块才装入并链接
三种装入方式
绝对装入
编译时产生绝对地址
可重定位装入（静态重定位）
装入时将逻辑地址转换成物理地址
动态运行时装入（动态重定位）
运行时将逻辑地址转换成物理地址，需要设置重定位寄存器
内存的分配与回收
连续分配管理方式
单一连续分配
特点
内存中只允许一个用户程序
实现简单
只能用于单用户、单任务的操作系统
存储器利用率低
固定分区分配
把内存区域分成若干个分区
分区大小相等
每个分区大小固定
适合控制多个相同作业的情况
缺乏灵活性
分区大小不等
每个分区大小不固定
增加了灵活性，可以满足不同大小进程的需求
子主题
实现
用数据结构的数组（或者链表）表示这个内存
动态分区分配
外部碎片可以使用\"紧凑\"技术解决
回收内存分区时，可能遇到的四种情况
回收区后面又相邻的空闲分区
回收区前面有相邻的空闲分区
回收区前、后都有相邻的空闲分区
回收区前、后都没有相邻的空闲分区
相邻的空闲分区需要合并
无外部碎片、有内部碎片
有外部碎片、无内部碎片
非连续分配管理方式
基本分页存储管理
思想
把内存分成一个个大小相等的小分区，再按照分区大小把进程拆分成一个个小部分
⭐地址转换
算出逻辑地址对应的页号、页内偏移量
判断页号是否越界
查询页表，找到页号对应的页表项，确定页面存放的内存块号
用内存块号和页内偏移量得到物理地址
访问目标内存单元
例题
⭐具有快表的地址变换
局部性原理
时间局部性
如果某个指令被执行过，那么这个指令不久之后还会被执行
空间局部性
如果某个空间被访问过，那么这个空间不久之后还会被访问
快表（TLB）
一种访问速度很快的高速缓冲
地址变换过程
CPU给出逻辑地址，算出页号、页内偏移量
查看页号是否越界
将页号和快表中的页号比较
如果快表命中，直接从快表中取出该页对应的内存块号，与页内偏移量组合形成物理地址，访问内存单元
如果快表没有命中，则需要访问内存的页表，找到对应的内存块号，拼接页内偏移量形成物理地址，访问内存单元，并把该页号存入快表
⭐如果快表命中，则只需要一次访问内存，否则需要两次
两级页表
单级页表存在的问题
问题概述
页表很大，需要很多页框
进程在一段时间内可能只需要访问几个特定的页面
建立页目录表
两级页表的原理、逻辑地址结构
原理
把长页表再次分页
逻辑地址结构
一级页号
二级页号
页面偏移量
如何实现地址变换
按照地址结构把逻辑地址拆分成3部分
从PCB中读出页目录表初始值，根据一级页号查页目录表，找到下一级页表在内存中存放的位置
根据二级页号查表，找到最终想要访问的内存块号
两级页表需要主要的细节
多级页表中，各级页表的大小不能超过一个页面，如果两级页表不够，可以分更多级
多级页表的访存次数（假设没有快表结构）——N级页表访问一个逻辑地址需要访问内存N+1次
基本分段存储管理
什么是分段
程序地址的空间会根据自身的逻辑关系划分成若干个段，每个段都有一个段名
什么是段表
段号
隐含的
段长
每个段的长度不固定
基址
⭐如何实现地址变换
根据逻辑地址得到段号、段内地址
判断段号是否越界
查询段表，找到对应的段表项
检查段内地址是否超过段长，如果大于等于也算越界
计算得到物理地址，访问目标内存单元
⭐分段、分页管理的对比
页是物理单位，段是逻辑单位
分页对用户不可见，分段对用户可见
页的大小是固定的，段的大小不固定
分段更容易实现信息的共享和保护
段页式存储管理
分页、分段管理方式的优缺点
分页管理
内存利用率高，不会产生外部碎片，只会产生少量的页内碎片
不方便按照逻辑模块实现信息共享和保护
分段管理
方便按照逻辑模块实现信息的共享和保护
如果段长过大，为其分配很大的连续空间会很不方便
段时管理会产生外部碎片
可以通过紧凑解决，但是需要付出较大的时间代价
分页、分段结合——段页式管理方式
段表、页表
段表
页表
根据逻辑地址获得段号、页号、页内偏移量
查询段表，找到对应页表项
检查页号是否越界，页号 >= 页表长度就发生了越界
根据页表存放的块号、页号查询页表找到对应页表项
访问一个逻辑地址需要访存次数
第一次
访问段表
第二次
访问页表
第三次
改进
可以引入快表机制
如果快表命中，只需要一次访存
动态分区分配算法
首次适应算法
算法思想
每次都从低地址开始查找、找到第一个满足大小的空闲分区
最佳适应算法
优先使用更小的空闲区
空闲分区按容量递增次序链接
会留下越来越多的内部碎片
最坏适应算法
优先使用最大的空闲分区
空闲分区按容量递减次序链接
大的空闲分区越来越少，导致大作业无处存放
邻近适应算法
每次都从上一次查找结束的位置继续查找
为用户进程分配的必须是一个连续的内存空间
为用户进程分配的可以是一些分散的内存空间
内存空间的扩充
覆盖与交换
覆盖技术
一个固定区
存放最活跃的程序段
固定区中读程序段在运行过程中不会调入调出
若干覆盖区
不可能被同时访问程序段可共享一个覆盖区
覆盖区中的程序端在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统自动完成覆盖
对用户不透明，增加了用户编程负担
交换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
磁盘分为文件区和对换区，换出的进程存放在对换区
覆盖和交换的区别
覆盖是在同一个程序或进程中的
交换是在不同进程（或作业）之间的
虚拟存储技术
传统存储方式的缺点
连续分配
非连续分配
基本段页式存储管理
一次性
作业必须一次性全部装入内存
大作业无法运行
多道程序并发度降低
驻留性
一旦作业被装入，就会一直驻留在加内存，浪费资源
高速缓存技术
对局部性原理最好的应用
虚拟内存的定义和特征
程序不需要全部装入就可以运行，运行时根据需要动态调入数据，如果内存不够，还需要换出一些数据
多次性
无需再作业运行时一次性全部装入内存，而是允许被分成多次调入内存
对换性
无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
虚拟性
从逻辑上扩充了内存的容量，使用户看到的内存用来，远大于实际的容量
如何实现虚拟内存技术
访问的信息不再内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
内存空间不够时，将内存中暂时用不到的信息换出外存（页面置换功能）
虚拟内存的实现
请求分页存储管理
基础
分页存储管理
扩展
请求调页功能
页面置换功能
页表机制
在基本分页的基础上添加了几个表项
状态位
标识页面是否在内存中
访问字段
记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面参考
修改位
标识页面调入内存后是否被修改过，只有被修改过的页面需要重新写回内存
外存地址
页面在外存中存放的位置
缺页中断机构
找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
缺页中断处理中，需要将目标页面调入内存，由必要时需要换出页面
缺页中断属于内中断，属于内中断中的故障，是可以被操作系统修复的
一条指令在执行过程中可能产生多次缺页中断
地址变换
根据逻辑地址查页号、页内偏移量
查询快表
快表命中，访问页表
修改快表标志位
形成物理地址
访问内存
如果快表未命中
页在内存
修改快表
修改访问标志位
页不在内存
产生缺页中断请求调页
调入页，修改快表
⭐⭐⭐页面置换算法
最佳置换算法（OPT）
选择以后最迟使用的页面置换出去
这是理想算法，但是暂时未实现
先进先出置换算法（FIFO）
每次淘汰最早进入的页面
最近最久未使用置换算法（LRU）
每次淘汰最近最久未被使用的页面
性能好，但是实现困难
时钟置换算法（CLOCK）
循环队列，每次缺页访问队列，把0次访问的页面淘汰，把所有的页面访问次数置0
淘汰一个页面最多会经历两轮扫描
改进型的时钟置换算法
优先淘汰未修改的页面
请求分段存储管理
请求段页式存储管理
页面分配策略
驻留集
请求分页存储管理中给进程分配的物理块集合
页面分配、置换策略
固定分配局部置换
系统给每个进程分配固定的物理块，缺页时只能置换改进程的物理块
可变分配全局置换
系统给每个进程分配一定数量的物理块，缺页时会分配未锁定的页面（可以是任何一个进程的物理块）给该进程
可变分配局部置换
系统给每个进程分配一定数量的物理块，缺页时置换自己的物理块，系统会动态给予收回物理块
调入页面的时机
预调页策略
运行前调入
请求调页策略
运行时调入
从何处调页
对换区空间够的时候，都是内存和对换区之间进行
对换区不够的时候，从文件区取，调回时需要写入内存区
抖动（颠簸）现象
各个换入的内存马上又要换出内存
产生的原因
进程频繁访问的页面数量高于可用的物理块数（分配给进程的物理块不够）
工作集
某段时间间隔内，进程实际访问页面集合
驻留集的大小需要大于工作集的大小
文件的逻辑结构
无结构文件
一系列的二进制流或者字符流组成，又称“流式文件”，如.txt文件
有结构文件
顺序文件
链式存储
不可随机访问，每次都需要从第一个记录开始往后找
顺序存储
可变长记录
无法实现随机存取，酶促只能从第一个记录开始往后依次查找
定长记录
可实现随机存取
索引文件
维护一张索引表
每个索引表项就是一条记录
索引顺序文件
维护一个瘦身的索引表
该索引表只存储主键信息（关键字信息）和目标地址
当记录过多时，可建立多级索引表
文件目录
文件目录的实现
一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
目录结构
单级目录结构
一个系统只有一个目录表，不允许文件重名
两级目录结构
一级目录是用户表项，二级目录才是FCB目录项，不同用户文件可以重名
多级目录结构（树形目录结构）
可以对文件进行分类，但是不方便文件共享
系统根据文件路径找到目标文件
无环图目录结构
在树形结构的基础上，增加一些指向同意节点的有向边，使整个目录成为一个有向无环图
为共享文件设置一个计数器，每次删除只删除目录项，计数器减一
索引结点
除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点
目录项只包含文件名、索引结点指针，因此每个目录项的长度都大幅减小
由于目录项长度减小，所以每个磁盘块都可以存放更多的目录项，因此检索文件的磁盘I/O的次数就减少了很多，大大提升文件检索速度
文件分配方式
顺序分配
为文件分配的必须是连续的磁盘块
目录项内容
起始块号，文件长度
顺序存取速度快
支持随机访问
会产生碎片
不利于文件扩展
链接分配
隐式链接（默认）
除文件最后一个盘块之外，每个盘块都存有指向下一个盘块的指针
起始块号，结束块号（最后一个为-1）
可解决碎片问题
外存利用率高
文件扩展实现方便
只能顺序访问
显式链接
建立一张文件分配表FAT，显示记录盘块的先后关系
起始块号
可以通过查询内存中的FAt实现随机访问
FAT需要占用一定的内存空间
索引分配
为文件数据库建立索引表，如果文件太大，可采用链接索引、多层索引、混合索引
链接方案
第一个索引块的块号
多层/混合方案
顶级索引块的块号
易于文件扩展
索引表需要占用空间
访问数据块前需要先读入索引块
如果使用链接方案，查找索引块需要很多次读磁盘操作
文件存储空间管理
存储空间的划分与初始化
文件卷（逻辑卷）的概念
目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
几种管理方法
空闲表法
空闲表中记录每个连续空闲区的起始盘块号、盘块数
分配时可采用首次适应、最佳适应等策略；回收时注意表项合并的问题
空闲链表法
空闲盘块链
以盘块为单位组成一条空闲链
分配时从链头一次取出空闲块，回收时将空闲块查到链尾
空闲盘区链
以盘区为单位组成一条空闲链
分配时可采用首次适应、最佳适应等策略；回收时注意盘区合并的问题
⭐位示图法
一个二进制位对应一个盘块。（字号、位号）或（行号、列号）与盘块号一一对应
重要考点
可以根据盘块号推算字号、位号
可以根据字号、位号推算出盘块号
成组链接法
UNIX采用的策略，适合大型文件系统
文件的基本操作
创建文件
分配外存空间
创建目录项
删除文件
回收外存空间
删除目录项
打开文件
将目录项中的信息复制到内存中的打开文件表中，把打开文件表的索引号返回给用户
打开文件后，对文件的操作不需要每次都查询目录，而已根据内存中的打开文件表进行操作
每个进程都有自己的打开文件表，系统中也有一张总的打开文件表
进程打开文件表的特有属性
读写指针
访问权限
系统打开文件表的特有属性
打开计数器
有多少进程打开了该文件
关闭文件
将进程的打开文件表中的对应表项删除
系统打开文件表计数减一，如果打开计数器为0，则删除系统表的该表项
读文件
根据读指针、读入数据量、内存位置将文件数据从外存读入内存
写文件
根据写指针、写出数据量、内存位置将文件数据从内存写出外存
文件共享
硬链接
各个用户的目录项指向同一个索引结点
索引结点中需要有链接计数
某用户想删除文件时，只是删除该用户的目录项，且count--
只有count == 0 时才能真的删除文件数据和索引结点
软链接
在一个Link型的文件中记录共享文件的存放路径（Windows快捷方式）
操作系统根据一层层查找目录，最终找到共享文件
Link的文件被删除，Link型文件依然存在，只是找不到对应共享文件
由于软链接发个文共享文件要查询多级目录，会有多次磁盘I/O，因此软链接访问速度比硬链接慢
文件保护
口令保护
实质
没有实际意义的一段字符串
为文件设置一个“口令”，用户访问文件需要提供口令。由操作系统验证口令是否正确
实现开销小，但口令一般存放在FCB或索引结点中，因此不太安全
加密保护
用特点的加密字符串和原文件做异或操作得到加密结果
用户输入特点的解密密码和加密后文件做操作得到原文件
用一个密码对文件加密，用户想要访问文件时，许哟啊提供密码解密
安全性高，但是加密/解密需要耗费一定的时间
访问控制
用一个访问控制表记录用户对文件的访问权限
对文件的访问类型可以分为：读/写/执行/删除 等
实现灵活，可以实现复杂的文件保护功能
文件系统的层次结构
例子
磁盘结构
磁盘、磁道、扇区的概念
磁盘由表面涂有磁性物质的圆形盘片组成
每个盘片被划分成一个个刺刀，每个磁道又划分成一个个扇区
如何在磁盘中读/写数据
磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写
盘面、柱面的概念
磁盘有多个盘片摞起来，每个篇盘片又两个盘面
所有盘面中相对位置相同的磁道组成柱面
磁盘的物理地址
柱面号、此面好、扇区号
磁盘的分类
根据磁头是否可以移动
固定头磁盘
每个磁道有一个磁头
移动头磁盘
每个盘面只有一个磁头
根据盘片是否可以更换
固定盘磁盘
可换盘磁盘
磁盘调度算法
一次磁盘读/写操作需要的时间
寻找时间
移动磁头到目标磁道花费的时间
延迟时间
移动磁头到开始扇区
减少延迟时间的方法
交替编号
具体做法
让编号相邻的扇区在物理上不相邻
读完一个扇区后需要一段时间的处理才能继续读入下一个扇区
错位命名
让相邻盘面的扇区编号“错位”
与交替编号原理相同
传输时间
读出或者写入数据需要的时间
先来先服务（FCFS）
按照请求到达的先后顺序进行处理
最短寻找时间优先（SSTF）
每次都优先响应距离磁头最近的磁道访问请求
贪心算法的思想，能保证眼前最有，但无法保证总的寻道时间最短
可能导致饥饿
扫描算法（SCAN）
只有磁头移动到最边缘磁道才能改变磁头移动方向
对各个位置磁道的响应频率不平均
循环扫描算法（C-SCAN）
只有磁头朝着某个方向移动才会响应请求，移动到边缘后立刻让磁头返回起点
返回的途中不响应任何请求
LOCK算法
SCAN算法的改进，只要在磁头方向不再有请求就立刻改变磁头方向
C-CLOCK算法
C-SCAN算法的改进，只要在磁头方向不再有请求就立刻改变磁头方向
磁盘的管理
磁盘初始化
低级格式化/物理格式化
划分扇区
磁盘分区（C盘、D盘、、、）
逻辑格式化
建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构）
引导化
计算机启动时需要运行初始化程序（自举程序）来完成初始化
ROM中存放很小的自举装入程序
完整的自举程序存放在初始快（引导块）中
坏块的处理
简单的磁盘
逻辑格式化时将坏块标记出来
复杂的磁盘
磁盘控制器维护一个坏块链，并管理备用扇区
I/O设备的基本概念
将数据输入输出计算机的外部设备
I/O控制器
主要功能
接受和识别CPU发出的命令（要有控制寄存器）
向CPU报告设备的状态（要有状态寄存器）
数据交换（要有数据寄存器，暂存输入/输出的数据）
地址识别（由I/O逻辑实现）
CPU与控制器之间的接口（实现控制器与CPU之间的通信）
I/O逻辑（负责 识别CPU发出的命令，并向设别发出命令）
控制器与设别之间的接口（实现控制器与设备之间的通信）
两种寄存器编制方式
内存映射I/O
控制器中的寄存器与内存同意编制
可以采用对内存进行操作的指令来对控制器进行操作
寄存器独立编制
控制器中的寄存器独立编制
需要设置专门的指令来操作控制器
I/O控制方式
程序直接控制方式
完成一次读/写的过程
CPU发出I/O指令后需要不断轮询
CPU干预频率
极高
每次I/O的数据传送单位
字
数据流向
设备 --> CPU --> 内存
内存 --> CPU --> 设备
中断驱动方式
CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号
高
DMA方式
CPU发出I/O命令后可以做其他事，本次I/O完成后DMA发出中断信号
中
块
设备 --> 内存
内存 --> 设备
通道控制方式
CPU发出I/O命令后可以做其他事，通道会执行通道程序完成I/O，完成后通道向CPU发出中断信号
低
一组块
假脱机技术（SPOOLing技术）
假脱机技术
输入井和输出井——模拟脱机输入输出的磁带
输入进程和输出进程——模拟脱机输入/输出的外围控制机
输入缓冲区和输出缓冲区——内存中的缓冲区，输入、输出的中转站
共享打印机
使用SPOOLing技术将独占式的打印机虚拟成共享打印机
设备的分配和回收
应考虑的因素
固有属性
独占设备、共享设备、虚拟设备
分配算法
先来先服务、优先级高者优先、短任务优先等
安全性
安全分配方式、不安全分配方式
静态分配和动态分配
静态分配
进程运行前分配好所有的资源
动态分配
进程运行过程中动态申请设备资源
设备分配管理中的数据结构
设备控制表（DCT）
每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针
控制器控制表（COCT）
每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针
通道控制表（CHCT）
每个控制器对应一张CHCT，关键字段：状态/等待队列指针
系统设备表（SDT）
记录整个系统中的设备情况，每个设备对应一个标目，关键字段：设备类型/标识符/DC他/驱动程序入口
设备分配的步骤
根据进程请求的物理设备名查找SDT
根据SDT找到DCT并分配设备
根据DCT找到COCT并分配控制器
根据COCT找到CHC他并分配通道
注意
只有设备、控制器、通道三者都分配成功才算设备分配成功
设备分配步骤改进
用户编程时使用逻辑设备名申请设备，操作系统负责从逻辑设备名到设备名的映射（通过LUT）
逻辑设备表的设置问题
整个系统只有一张LUT
各用户所用的逻辑设备名不可重复
每个用户一张LUT
各个用户的逻辑设备名可以重复
缓冲区管理
缓冲区的概念
一般利用内存做为缓冲区
缓解CPU与设别的速度矛盾、减少对CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与I/O设备之间的并行性
单缓冲
设备—Ｔ—缓冲区—Ｍ—工作区—Ｃ—处理
处理一块数据平均耗时Max（C，T） + Ｍ
分析问题的初始状态：工作区满，缓冲区空
双缓冲
处理一块数据平均耗时Max（C，T）
分析问题的初始状态：工作区空，一个缓冲区满，另一个缓冲区空
循环缓冲
多个缓冲区链接成循环队列，in 指针指向第一个空缓冲区，out 指针指向第一个满缓冲区
缓冲池
三个队列
空缓冲队列
输入队列
输出队列
四种工作缓冲区
用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区
用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区
0 条评论
回复 删除
下一页
