导图社区 操作系统
- 426
- 44
- 13
- 举报
操作系统
操作系统整体框架思维导图，包括计算机系统概述、进程管理、输入/输出管理、文件管理、内存管理五部分内容。
编辑于2021-10-25 16:21:08
- 相似推荐
- 大纲
操作系统
计算机系统概述
疑难点： 1，并行性和并发性的区别和联系 并行性，是指两个或多个事件在同一时刻发生；并发性，是指两个或多个事件在同一时间间隔里发生，再多道程序环境下并发性是指在一段时间的宏观上有多个程序同时运行，但在单处理器系统中，每个时刻却仅能有一道程序执行，因此微观上，这些程序只能分时的交替执行 2，特权指令与非特权指令特权指令 特权指令，指有特殊权限的指令，如清内存，置时钟，分配系统资源，修改虚存的段表或页表，修改用户的访问权限，这些指令不直接提供给用户，因此特权指令必须在核心态执行，用户态下只能使用非特权指令，核心态下可以使用全部指令 3，访房管指令和访管中断 访管指令是一条可以在用户态下执行的指令 访管中断将操作系统转化为核心态
基本概念
题目内容： 1，系统软件包括操作系统，数据库管理系统，语言处理程序，服务性程序，标准库程序。 2，通道是独立于CPU的控制输入/输出的设备。 3，库函数是高级语言中提供与系统调用对应的函数，库函数属于用户程序而非系统调用，是系统调用的上层。 4，库函数是语言或应用程序的一部分，可以运行在用户空间中。而系统调用是操作系统的一部分，是内核为用户提供的程序接口运行在内核空间中，而且许多库函数都会使用系统调用来实现功能。
特征
并发和共享是操作系统两个最基本的特征，两者之间互为存在条件 1，资源共享是以程序的并发为条件的若系统不允许程序并发执行这个自然不存在资源共享问题 2，若系统不能对资源共享实施有效管理，这必将影响到程序的并发执行，甚至根本无法并发执行
并发
并发是指两个或多个时间在同一时间间隔内发生，并行制同一时刻。
共享
子系统中资源可供内存中多个并发执行的进程共同使用，
互斥共享
在一段时间内只允许一个进程访问该资源。
同时访问
这里说的“同时”通常是宏观上的,在微观上，这些进程可能是交替地对该资源进行访问即“分时共享”。
虚拟
虚拟技术可归纳为，时分复用技术，空分复用技术。
异步
多道程序环境允许多个程序并发执行，有并发才有异步。
目标与功能
计算机系统资源管理者
处理机管理
存储器管理
文件管理
设备管理
用户与计算机硬件系统之间的接口
命令接口（允许用户直接使用）
命令接口可分为： 联机命令接口又称交互式命令， 接口脱机命令接口又称批处理命令接口。
联机控制方式
脱机控制方式
程序接口（系统调用）
程序接口由一组系统调用也称广义指令组成，当前最流行的是图形用户界面（GUI），即图形接口，严格来说图形接口不是操作系统的一部分。
扩充机器
发展与分类
题目： 批处理操作系统的用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行交互能力差 分时操作系统可让多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独立性，系统响应及时 实时操作系统对控制对象做出及时反应，可靠性高，响应及时，但资源利用率低。
手工操作阶段
缺点：
用户独占全机，资源利用率低。
CPU等待手工操作，CPU利用不充分
批处理阶段
单道批处理系统
每次主机内存中仅存放一道作业，运行期间，高速的C P U变，处于等待低速I/o完成的状态。
自动性
顺序性
单道性
多道批处理系统
资源利用率高，多道程序共享计算机资源，各种资源利用率充分，系统吞吐量大，但不提供人机交互能力，用户响应时间较长。
多道
宏观上并行
微观上串行
分时操作系统（时间片，轮流）
同时性
交互性
独立性
及时性
实时操作系统（紧急任务，不排队）
硬实时系统（动作在规定时间）
飞机自动控制系统
软实时系统（偶尔可违反）
飞机订票，银行管理系统，股票交易系统。
网络操作系统和分布式计算机系统
个人计算机操作系统
运行环境
操作系统运行机制
CPU执行两种不同性质的程序，一种是操作系统内核程序，另一种是用户自编程序 特权指令是指不允许用户直接使用的指令如I/ｏ指令，置中断指令，存取用于内存保护的寄存器 大内核，将操作系统主要功能都作为系统类核，优点，高性能，缺点内核代码庞大结构混乱，难以维护 微内核，只把最基本的功能保留在内核，功能少结构清晰，方便维护，缺点，需要频繁地在核心态和用户态之间切换性能低
时钟管理
计时，向用户提供标准的系统时间。 通过时钟中断的管理，可以实现进程切换。
中断机制
提高CPU利用率
原语
特点： 属于操作系统的最低层最接近硬件的部分 这些程序的运行具有原始性去操作 只能一气呵成这些程序运行时间都比较短，而且调用频繁
系统控制的数据结构及处理
进程管理
存储器管理
设备管理
中断与异常
定义
内中断（异常）例外，陷入
源自CPU执行指令内部的事件，如程序的非法操作，地址越界，算术溢出，虚存系统的缺业，专门的陷入指令
自愿中断（指领中断）
强迫中断
硬件中断
软件中断
外中断（中断）
这一类中断通常是与当前指令执行无关的时间及他们与当前处理机制运行的程序无关。
外设请求
人的干预
处理过程
关中断
保存中断
中断服务程序寻址
保存现场和屏蔽字
开中断
恢复现场和屏蔽字
开中断和中断返回
前3为硬件完成，后面为中断程序完成
系统调用
用户程序不能直接执行对系统影响非常大的操作，必须通过系统调用的方式请求操作系统代为执行，以便保证系统的稳定性和安全性，防止用户程序随意更改和访问重要的资源影响其他进程运行。 用户态转向核心态的例子： 1，用户程序要求操作系统的服务及系统调用 2，发生一次中断 3，用户程序中产生了一个错误状态 4，用户程序中企图执行一条特权指令 5，核心态转向用户态的有一条指令实现这一条指令也是特权指令，一般是中断返回指令 外部中断处理过程，P C值由中断隐指令自动保存，而通用寄存器内容由操作系统保存。
设备管理（请求与释放）
文件管理（读写，创建删除）
进程控制（创建撤销，阻塞及唤醒）
进程通信（消息传递或信号传递）
内存管理（内存的分配回收以及获取作业占用内存区大小及始址）
体系结构
大内核
大内核系统将操作系统的主要功能模块都作为一个紧密联系的整体运行在核心态，从而为应用提供高性能的系统服务。
微内核
将内核中最基本的功能保留在内核，而将那些不需要再和心态执行的功能移到用户态从而降低的内核的设计复杂性。
进程管理
进程与程序之间的区别与联系：进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念，进程的运行实体是程序，离开程序的进程没有存在的意义，进程由程序，数据，进程控制块PCB三部分组成。程序是由一组有序的指令集合，是一种静态概念，一个进程可以执行一个或几个程序，一个程序也可构成多个进程 死锁：两个或多个进程无限地等待一个事件而该事件只能由这些等待进程之一来产生 饥饿：进程在信号量内无穷等待的情况 进程同步互斥：竞争使用临界资源只能让他们逐个使用称互斥，协同完成任务在关键点上等待另一个进程发来消息以便协同一致（同步）
进程（独立运行，资源分配和调度的基本单位）
概念
PCB（进程控制快）是进程存在的唯一标志
进程定义 进程是程序的一次执行过程进程 是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是具有独立功能的程序，在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。
由程序段，相关数据段和PCB三部的分构成的进程映像
特征
动态性
进程最基本特征
并发性
独立性
独立获得支援和独立接受调度的基本单位
异步性
进程按各自独立的，不可预知的速度向前推进
结构性
状态
一个进程，从运形态变成阻塞态是主动的行为，而从阻塞态变成就绪态是被动的行为，需要其他相关进程协助。
运行态
就绪态
进程获得了除处理机以外的一切所有资源
阻塞态
创建态
结束态
前3为基本状态
控制（程序段称原语）
进程的创建
引起进程创建的有终端用户登录系统，作业调度，系统提供服务，用户程序的应用请求。
为进程分配一个唯一的进程标识号，并申请一个空白的PCB
为进程分配资源，为新进程的程序和数据及用户占分配必要的内存空间，创建失败是处于阻塞态
初始化PCB，主要包括初始化标志信息，处理机状态信息，处理机控制信息，设置进程优先级。
插入就绪队列
进程的终止
终止过程：撤销原语 根据被终止进程的标识符检索P C B从中读出该进程的状态， 若被终止进程处于执行状态，立即终止该进程执行，将处理机资源分配给其他进程 若该进程还有子孙进程，则将其子孙进程全部终止 将该进程所拥有的全部资源或归还给其父进程或归还给操作系统， 将PCB从所在队列删除
正常结束
任务完成
异常结束
程序无法运行
如存储区越界，保护错，非法指令，特权指令错，运行超时，算术运算错，I/ｏ故障
外界干预
外界请求而终止
进程的阻塞与唤醒
唤醒原语
阻塞原语
成对出现
进程切换
调度与切换的区分：调度指决定资源分配给哪个进程的行为，是一种决策行为，切换是指实际分配的行为，是执行行为。
处理机从一个进程的运行转到另一个进程运行上，进程运行环境产生的实质性的变化。
组织
进程控制块（PCB）
一个系统通常存在着许多进程的P CB，为了方便进程调度和管理将PCB组织起来的方法有链接方式和索引方式。
进程描述信息
进程标识符（每个进程唯一）
用户标识符（共享和保护）
进程控制和管理信息
进程当前状态
进程优先级
资源分配清单
内存地址空间或虚拟地址空间的状况
处理机相关信息
寄存值
程序段
程序代码（可被多个进程共享）
数据段
可是原始数据，中间或最终结果
通信（PV操作是低级的通信方式）
共享存储
低级方式的共享是基于数据结构的共享
高级方式的共享则是基于存储区的共享
消息传递（数据的交换是以格式化的消息为单位）
进程通过系统提供的发送消息和接收消息两个原语进行数据交换。
直接通信方式
间接通信方式（信箱通信）
管道通信
共享文件，字符流形式，必有互斥、同步和确定对方的存在的协调能力
限制管道大小（固定缓冲区）读进程可能工作的比写进程快
3个为高级通信
线程
概念
引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的，是减小程序在并发执行时所付出的空间开销，提高操作系统的并发性能 线程是程序执行流的最小单位，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，一个进程内部有多个线程
进程与线程的比较
调度
线程是独立调度的基本单位，进程是拥有支援的基本单位
拥有资源
并发性
进程线程都有很好的并发行
系统开销（线程小）
地址空间和其他资源
同一进程的各线程之间共享进程的资源，某进程内的线程对于其他进程不可见
通信方面
进程同步和互斥手段线程直接读写进程数据段
线程属性
线程是一个轻型实体，他不拥有系统资源，不同线程可以执行相同的程序，同一进程中的各个线程共享该进程的拥有的资源，线程是处理机的独立调度单位，多个线程可以并发执行的，一个线程被创建后便开始了他的生命周期直接终止。
实现方式
用户级
内核级（内核支持的线程）
多线程模型
多对一（用户极线程对操作系统不可见）
一对一（并发性强）
多对多（克服了多对一并发都不高的缺点，一对一开销太大的缺点）
处理机调度
概念
对处理机进行分配
调度层次
作业调度（外到内，高级调度，调入一次调出一次）
中级调度（外到内，内存调度，提高内存利用率系统吞吐量）
将暂时不能运行的进程调至外存，挂起态
低级调度（内存到CPU，进程调度，最基本，频率高）
三级调度的联系
作业调度次数少，中级调度次数略多，进程调度频率最高
时机、切换、过程
不能
不能进行进程调度和切换的情况：在处理中断的过程中，近程在操作系统内核程序临界区中，其他需要完全屏蔽中断的原子操作过程中。
应该
应该进行进程调度与切换的情况：发生引起调度条件且当前进程无法进行继续下去，中断处理结束后或自陷处理结束后。
进程调度方式
非剥夺调度方式（非抢占方式）
剥夺调度方式（抢占方式）
调度基本准则
CPU利用率
系统吞吐量
周转时间
周转时间=作业完成时间-作业提交时间
带权周转时间=作业周转时间/作业实际运行时间
平均周转，平均带权周转
等待时间
响应时间
典型的调度算法
先来先服务（FCFS）
不可剥夺，算法简单，效率低对长作业有利，利于CPU繁忙型，不利于IO
短作业优先（SJF）
对长作业不利，未考虑作业的紧迫性，该算法不一定真正做到短作业优先调度，该算法平均等待时间，平均周转时间最少
优先级调度算法
优先级设置参照原则：系统进程>用户进程，交互进程>非交互型进程或前台进程>后台进程，IO进程>计算型进程
非剥夺式优先级调度算法
剥夺式优先级调度算法
静态优先级
在创建进程时确定运行期间保持不变
动态优先级
进程运行过程中，根据情况变化动态调整优先级
响应比优先（非剥夺）
响应比=（等待时间+要求服务时间）/要求服务时间
响应比越高，有利于短作业，响应比由等待时间决定等待时间越长响应比别越高，克服饥饿状态，兼顾长作业
时间片轮转
分时系统，剥夺，
时间片长短：系统的响应时间就是队列中的进程输入系统的处理能力
多级反馈队列
为提高系统吞吐量和缩短平均周转时间而照顾短进程，为获得较好的IO设备利用率和缩短响应时间而照顾IO型，不必事先估计进程的执行时间。
终端型作业用户：短作业优先
短批处理作业用户：周转时间短
长批处理：经过前面几个队列得到部分执行，不会长期得不到处理
进程同步
概念
临界资源（一次一进程，若干共享）
进入区 entry～
临界区（临界段）critical section
退出区 exit～
剩余区 remainder～
同步
直接制约关系，源于之间的相互合作
互斥（间接制约关系）
空闲让进
忙则等待
有限等待
让权等待
临界区互斥
软件实现方法
单标志法
设置一个公用整形变量用于指示被允许进入临界区的进程编号
违背 ，空闲让进
双标志法先检查
每个进程访问临界资源之前，先检查临界资源是否正在被访问
违背，忙则等待
双标志法后检查
先检测对方的进程状态标识再置自己的标志
有饥饿现象，违背空闲让进，有限等待
Peterson’s Algorithm
硬件实现方法
优点：适用于任意数目的进程，而不管是单处理机还是多处理机，简单容易验证，其正确性 缺点：进程，等待进入临界区时，要耗费处理机时间不能实现让全等待，可导致饥饿现象。
中断屏蔽方法，简单高效
硬件指令方法，执行过程中不允许被中断TSL
TestAndSet
Swap
信号量
整形信号量
整形量S，wait，signal（未遵循让权等待）
记录型
子主题
利用信号量实现同步
利用信号量实现进程互斥
利用信号量实现前驱关系
管程
定义（特性保证了进程互斥，提供了条件变量可实现进程同步）
管程把对共享资源的操作封装起来，每次仅允许一个进程进入管程,从而实现进程互斥｡
管程的名称
局部于管程内部的共享结构数据说明
对该数据结构进行操作的一组过程或函数
对局部于管程内部的共享数据设置初始值的语句
条件变量
条件变量与信号量的比较：条件变量wait/signal操作类似于信号量的P/v操作，可实现进程的阻塞/唤醒；不同点：条件变量是没有值的，仅实现排队等待的功能，而信号量是有值的，信号量的值反映了剩余资源数，而在管程中剩余资源数用共享数据结构记录。
wait（将自己插入条件的等待队列并释放管程）
signal（唤醒一个因条件而阻塞的进程）
经典同步问题
消费者～生产者
读者～写者
哲学家进餐问题
吸烟者问题
85
死锁
概念
定义
是指多个进程应竞争资源，造成一种僵局，若无外力作用这些进程将无法向前推进。
原因
系统资源的竞争
进程推进顺序非法
死锁产生的必要条件
互斥条件
不剥夺条件
请求并保持条件
循环等待条件
处理策略
死锁预防
破坏四个必要条件之一
破坏互斥条件：这个方法不太可行，而且在某些场合应该保护这种互斥性破坏 不剥夺条件：实践起来比较复杂，释放以后的资源可能造成前一段工作的失效，反复申请和释放资源会增加系统开销，降低系统吞吐量这种方法常用于状态易于保护和恢复的资源。 破坏请求并保持条件：在运行前一次性申请完它所需要的全部资源，这种方式简单，缺点，系统资源被严重浪费可能会导致饥饿现象。 破坏循环等待条件：采用顺序资源分配法进行编号，这种方式限制性类型设备的增加，造成资源浪费，编程带来麻烦。
死锁避免
系统安全状态
允许进程动态的申请资源在在系统进行资源分配之前，应先计算此次分配的安全性。
并非所有的不安全状态状态都是死锁,在进入不安全状态后，便可能进入死锁状态
银行家算法
可利用资源量
最大需求矩阵
分配矩阵
需求矩阵
检测与解除
资源分配图
从进程到资源的有向边称为请求边表示该进程申请一个单位的该类资源,从资源到进程的边称为分配边表示该类资源已有一个资源分配给了该进程
死锁定理
在资源分配图中，既不阻塞又不孤点的进程，消去它所有的请求边和分配边，使之成为孤立的节点 判断某种资源是否有空间应用他的资源数减去他在资源分配途中的出度
死锁解除
资源剥夺法
撤销进程法
进程回退法
输入/输出管理
I/O子系统概述
I/O设备
按使用特性分类
人机交互类外部设备（打印机显示器鼠标键盘）
存储设备（磁盘磁带光盘）
网络通信设备（网络接口）
按传输速率分类
低速设备（键盘鼠标）
中速设备（打印机）
高速设备（磁带机光盘机）
按信息交换的单位分类
块设备（磁盘）
字符设备（打印机）
I/O控制方式
程序直接控制方式
简单且易于实现，由于CPU和I/O只能串行工作，导致CPU利用率相当低
中断驱动方式
DMA方式
通道控制方式
I/O子系统的层次结构
用户层I/O软件
大部分在操作系统内部，小部分在用户层
设备独立性软件
执行所有设备的公有操作
向用户层提供统一接口
功能
设备驱动程序
与硬件直接相关，每类设备配备一个设备驱动程序，进程形式存在
中断处理程序
硬件设备
设备控制器功能： 接收和识别CPU或通道发来的命令 实现数据交换包括设备和控制器之间的数据传输 发现和记录设备及自身的状态信息供C P U处理使用 设备地址识别 设备控制器组成部分： 设备控制器与CPU的接口：数据线，地址线，控制线 设备控制器与设备的接口 I/O控制逻辑
I/O核心子系统
I/O子系统概述
提供服务主要有I/O调度，缓冲与高速缓存，设备分配与回收，假脱机，设备保护和差错处理
I/o调度概念
高速缓存与缓冲区
磁盘高速缓存
缓冲区
引入缓冲区的目的： 缓和C P U与I/O设备之间速度不匹配的矛盾 减少对C P U的中断频率，放宽对CPU中断响应时间的限制 解决基本数据单元大小不匹配的问题 提高CPU和I/O设备之间的并行性 实现方法： 采用硬件缓冲器 采用缓冲区：为空必冲满后取，非空，取后冲
单缓冲
双缓冲
循环缓冲
缓冲池
设备分配与回收
独占是使用设备，分时是共用使用设备，Spooling方式使用外部设备
设备控制表(DCT)(整个系统一张）。控制器控制表(COCT)通道控制表(CHCTJ系统设备表(SDT)
设备分配原则
发挥使用效率，避免造成死锁
设备分配方式
静态分配
动态分配
设备分配算法
先请求先分配优先级高者者优先
安全分配方式
不安全分配方式（可能产生死锁）
SPOOLing技术（假脱机技术）
为了缓和C P U的高速性和I/O设备低速性之间的矛盾，将独占设备改造成共享设备的技术
输入井和输出井
输入缓冲区和输出缓冲区
输入进程和输出进程
文件管理
文件系统基础
概念
定义
系统运行时，计算机已经成为基本单位进行支援的调度和分配，在用户进行输入输出中，以文件为基本单位 数据项，（是文件系统中最低的数据组织形式，基本数据项，组合数据项）记录，文件
文件属性
名称、标识符、类型、位置、大小、保护、时间日期和用户标识，所有文件的信息都保存在目录结构中而目录结构保存在外存上
文件的基本操作
创建、写、读、文件重定位、删除、截断
文件的打开与关闭
从外存复制到内存打开文件表的一个表目并将该表目编号也称索引所以反回给用户。 一个进程打开一个文件，系统打开文件表就会为打开的文件增加相应的条目，还有一个计时器记录进程打开了该文件，当计时器为零时表示，该文件不再被使用将被系统回收。 每个打开文件都有如下关联信息：文件指针，文件打开计数，文件磁盘位置，访问权限。
文件的逻辑结构
无结构文件（流式文件）
最简单的文件组织形式以字节为单位没有结构
通过穷举搜索的方式，源程序文件目标代码文件
有结构文件（记录式文件）
顺序文件：访问时需要顺序搜索文件，定长的可实现随机存取结构无法快速找到，顺序结构可以快速找到对半查找 索引文件：变长记录文件只能顺序查找系统开销较大，索引表本身是定长记录的顺序文件，通过索引可以提高访问，速度 索引顺序文件：每组中的第一条记录建立一个索引项，其中还有该记录的关键字和指向该记录的指针，索引文件和索引顺序文件都提高了存取的速度但因为配置索引表增加了存储空间。 直接文件或散列文件：给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址记录没有顺序，会引起冲突即不同关键字的散列函数值相同。
顺序文件
索引文件
所以顺序文件
顺序（记录N条，平均查找N/2次）索引（N条， 根号N组，根号N个表项，查找根号N次）
直接文件和散列文件
目录结构
文件控制块（FCB）
按名存取，一个文件控制块就是一个文件目录项
索引节点
存放在磁盘上的索引节点称为磁盘索引结点，UNIX的中的每个文件都有一个唯一的索引节点主要包括，文件主标识符文件类型，文件存取权限，文件物理地址，文件长度，文件链接计计数，文件存取节点编号，文件存取时间，状态，访问计算，逻辑设备号，链接指针
单级目录结构
整个系统文件中，只建立一张目录表每个文件在一个目录项
查找速度慢文件不允许重名不便于文件共享
多级目录结构
树形目录，访问相对路径标识文件应从当前目录出发，分隔符 /
按路径名逐级访问中间节点增加了磁盘访问次数影响查询速度
两极目录结构
文件目录分成主文件目录和用户文件目录
解决重命名问题，缺乏灵活性，不能对文件进行分类
无环图目录结构
树形目录结构能便于实现文件分类，但不便于实现文件共享，在树形目录结构基础上增加了一些指向同一节点的有向边使整个目录成为一个有向无环图。 防止删除时发生错误，可为每个共享节点设置一个共享计数器，每当图中增加对该节点的共享链时，计数器加1，删除时计数器减1，共享计数器为0才真正删除该节点。
文件共享
基于索引节点的共享方式（硬连接）
利用符号链接实现文件共享（软链接）
静态共享
文件保护
访问类型
读写，执行，添加删除，列表清单，重命名，复制，编辑等加以控制。
访问控制
访问控制列表：优点是可以使用复杂的访问方法，缺点是长度无法预计，并且可能导致复杂的空间管理。 精简的访问列表采用拥有者、组和其他三种用户类型。 若用户和拥有者在同一个用户组，按照同组权限访问，否则只能按其他用户权限访问。 口令指用户在建立文件时提供一个口令，密码指用户对文件进行加密。这两种并没有控制用户对文件的访问类型。 现代操作系统常用的文件保护方法是将访问控制列表与用户，组和其他成员访问控制方案一起组合使用。 对于多级目录结构而言，不仅需要保护单个文件，而且需要保护子目录的文件即需要提供目录保护机制目录操作与文件操作并不相同，因此需要不同的保护机制。
文件系统实现
文件系统层次结构
用户调用接口：文件系统为用户提供与文件及目录有关的调用。 文件目录系统：管理文件目录 程序控制验证模块：确认访问合法性 逻辑文件系统与文件信息缓冲区：逻辑记录转换成相应的块号 物理文件系统：逻辑记录所在的相对块号转换成实际的物理地址 辅助分配模块：管理辅存空间 设备管理程序模块：分配设备
目录实现
文件实现
文件分配方式
连续分配：一组连续的块，支持顺序访问和直接访问，实现简单存取速度快，长度不宜动态增加，增加移动大量盘块，反复增删文件后会产生外部碎片。 链接分配： 隐式链接，每个文件对应一个磁盘块的链表，分布在磁盘的任何地方，除最后一个盘块外每个盘块都有指向下一个盘块的指针，指针对用户是透明的目录包括文件第一个和最后一个指针，缺点是无法直接访问盘块，只能通过指针顺序访问文件且盘块指针会消耗一定的存储空间不稳定性。 显示链接，是指把用于链接文件各物理块的指针，从每个物理块的块末尾提取出来显示的存放在内存的一张列表中，支持随机访问。 索引分配：链接分配解决的连续分配的外部碎片和文件大小管理的问题以及分配不能有效支持直接访问（F A T除外）索引分配把每个文件的所有的盘块号都集中放在一起构成，索引块，支持直接访问且没有外部碎片，但增加了系统存储空间的开销。
连续分配
链接分配
索引分配
链接方案（一个索引块通常为一个磁盘块）
多层索引（一层指向二层，根据文件大小，要求可以继续增加）
混合索引
文件存储空间管理
文件卷可以是物理盘亏的一部分，也可以是整个物理盘，也可由多个物理盘组成 程序进行初始化划分好目录区和文件区
空闲表法
连续分配方式，每个空闲区对应一个空闲表项
空闲链表法
空闲盘块链
空闲盘区链
位示图法
二进制表示（0表示空闲1表示已分配）
I行j列（b=n(i-1)+j，字号:i =(b-1)/n+1，位号:(b-1)%n+1)
成组链接法
磁盘组织与管理
磁盘结构
柱面号*盘面号*扇区号
磁盘调度算法
先来先服务（最简单的调度算法）FCFS
最短寻找时间优先SSTF（产生饥饿，不能保证平均寻找时间最小）
扫描算法 SCAN（电梯调度算法）要移动到磁盘的端点
循环扫描算法 C-SCAN（LOOK调度）只需要到达最远端的一个请求即可返回
同柱面不同盘面的扇区错位编号
磁盘管理
磁盘初始化
引导块
坏块（操作系统不能修复）
内存管理
虚存实际容量<=内存容量和外存容量之和 虚存的最大容量<=计算机的地址位数的容纳的最大容量
概念
内存管理的基本原理和要求
功能
内存空间的分配与回收
地址转换
把逻辑地址转换成相应的物理地址
内存空间的扩充
存储保护
程序装入与链接
编译
链接
静态链接（运行之前链接完成）
装入时动态连接(边装入边链接)
运行时动态链接(需要该目标模块才进行)
装入
绝对装入（无操作系统时）
可重定位装入（早期多道批处理）一次完成
动态运行时装入
内存保护
CPU中设置一对上下限寄存器判断有无越界，采用重定位寄存器(最小的物理地址)界地址寄存器实现保护(含逻辑地址最大值)
连续分配管理方式
单一连续分配
优点:简单无外部碎片可采用覆盖技术，不需要额外的技术支持 缺点:适用于单用户、单任务的操作系统，有内部碎片存储器的利用率极低
固定分区分配
最简单的一种多道程序存储管理方式，划分成若干固定大小的区域每个分区只装入一道作业 方法：分区大小相等或分区大小不等 问题：程序可能太大而放不进任何一个分区中，利用率低，程序固定大小分区时可能存在浪费存在外部内部碎片，设计简单无外部碎片，不能实现进程共用一个组成，存储空间利用率低。
动态分区分配
导致内存中出现许多小的内存块内存利用率下降称这些小块为外部碎片通过紧凑技术解决 首次适应算法的效果最佳 最佳适应算法产生最多的外部碎片
首次适应算法(地址递增)
最佳适应算法(按容量递增)
最坏适应算法(最大)
邻近适应算法(循环首次适应算法）
非连续分配管理方式
1.动态重定位在执行过程中进行． 2.分页系统的页面是为操作系统所感知 3.页表的始地址存放在寄存器中 4.一个程序如何分段是在用户编程时决定的 5.可重入程序是通过减少对换数量改善系统性能 6.实现分区存储管理的代价最小 7.用分段方法来分配和管理用户地址空间、用分页方法管理存储空间 8.产生内部碎片：分页虛拟存储管理、段页式分区管理、固定式分区管理
基本分页存储管理方式（157）
以块为单位逐个申请主存中的块空间 进程中的块称页，内存中的块称为页框或页桢 页表一般存放在内存中 快表具有并行查找能力的高速缓冲存储器
页内偏移=逻辑地址%页面长度
页号=逻辑地址/页面长度
物理地址=页面始址+页内偏移量
基本分段存储管理方式（151）
分段：段内要求连续段间不要求连续，逻辑地址的页号和页内偏移量对用户是透明的 段表：每个进程都有一张逻辑空间与内存空间映射的段表，段表记录该段在内存中的始址和长度 段的共享与保护：存取控制保护另一种是地址越界保护
页表项=页面大小/页表项大小
页内偏移=页面大小
段页式管理方式
页式存储管理能有效地提高内存利用率而分段存储管理能反映程序的逻辑结构并有利于段的共享，结合起来便形成了段页式存储管理方式将逻辑地址分为段号、页号、页内偏移量 在一个进程中段表只有一个而页表可能有多个 进行一次访问，实际需要三次访问主存
虚拟内存管理
概念
传统存储管理方式的特征
一次性：必须一次性全部装入内存才能开始运行当作业很大而不能被全部装入是不能运行，当大量作业要求运行时内存不足，不足一容纳所有作业只能少数作业优先运行 驻留性：必须进行结束才能被换出
一次性
驻留性
局部性原理
时间局部性（一条指令执行后可能再次执行）
空间局部性（访问某个存储单元不久后附近的存储单元也将被访问）
虚拟存储器的定义和特征
基于局部性原理在程序装入时将程序的一部分装入内存而将其余部分留在外存 存储存储器的大小由计算机的地址结构决定并不是内存和外存的简单相加
多次性（无需一次装入）
对换性（无需长驻内存）
虚拟性（逻辑上扩充内存的容量）
虚拟内存技术的实现
硬件支持：一定容量的内存和外存、页表机制、主要的数据结构、中断机构、地址变换机构
请求分页存储管理
请求分段存储管理
请求段页式存储管理
请求分页管理方式
页表机制
状态位
访问字段
修改位
外存地址
缺页中断机构
在指令执行期间而非一条指令执行完后产生和处理中断信号属于内部中断，一条指令在执行期间可能产生多次缺页中断。
地址变换机构(184）
写指令需要重置修改位读不需要
页面置换算法
最佳置换算法(OPT)
淘汰永不使用或最长时间内不被访问
先进先出页面置换算法(FIFO)
产生所分配的物理块增大而页故障数不减反增的现象(belady)
最近最久未使用置换算法(LRU)
时钟置换算法(CLOCK)（187）
页面分配策略
驻留集大小
分配给一个进程的存储量越小任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用率，若一个进程在主存中的页数过少，有局部性原理页面错误率会相对较高，若页数过多给特定进程分配更多的主存空间，对该进程的错误率没有明显的影响。
固定分配局部置换（运行期间不变）
可变分配全局置换
为每个进程分配一定数目的物理块，缺页时系统从空闲物理块队列中取出一个物理快分配给的进程。他会盲目增加物理块，从而导致系统多道程序的并发能力下降。
可变分配局部置换
缺页时只允许从该进程在内存的页面中选出一页换出因此不会影响其他程序进行 实现复杂更大的开销
调入页面的时机
预调页策略
请求调页策略（每次调入一页，IO开销大）
从何处调入页面
系统拥有足够的对换区空间：可以全部从兑换区调入所需页面，提高调页速度 系统缺少足够的对换区空间：凡不会被修改的文件都直接从文件区调入 UNIX方式：与进程有关的文件都放在文件区，因此未运行过的页面都从文件区调入，曾经运行过但又被换出的页面从对换区调入
抖动
频繁的页面调度行为 原因：某个进程频繁访问的页面数高于可用的物理页面桢数目
工作集
某段时间间隔内进程要访问的页面集合 物理块数要大于工作集大小