导图社区 计算机操作系统(西电)
- 107
- 7
- 1
- 举报
计算机操作系统(西电)
计算机操作系统的思维导图，用于期末复习，考研知识总结。
编辑于2021-02-14 02:08:35- 相似推荐
- 大纲
计算机操作系统
第一章 引论
1.1 操作系统的目标与作用
操作系统的目标
方便性
方便用户操纵计算机硬件
有效性
提高系统资源利用率
提高系统吞吐量
可扩充性
适应硬件、体系结构及计算机应用的发展
开放性
软硬件兼容性
遵循世界标准规范
操作系统的作用
作为用户与软硬件之间的接口
命令接口
系统调用
图形界面
作为计算机系统资源的管理者
资源：处理机、存储器、I/O设备与文件
实现了对计算机资源的抽象
虚拟机
I/O管理软件
文件管理软件
用户窗口管理软件
操作系统发展的主要动力
不断提高的计算机资源利用率
资源昂贵
I/O设备利用率
CPU利用率
方便用户
人机交互
用户独占
感觉上
器件不断更新换代
芯片更新
外设换代
计算机体系结构的不断发展
不断提出新的应用需求
游戏\电影\音乐
大数据
1.2 操作系统的发展过程
未配置操作系统的计算机系统
人工操作方式
用户独占全机
CPU等待人工操作
人机矛盾:CPU速度速度快.I/O速度慢
脱机输入输出方式
减少了CPU的空闲时间
提高了I/O的速度
单道批处理系统
把一批作业以脱机的方式放入磁盘
通过监督程序(Monitor)按顺序调入内存并依次处理
主要缺点
系统资源得不到充分利用
旨在提高资源利用率系系统吞吐量
多道批处理系统
多个程序同时存在于内存中
利用程序I/O的空档,多个程序交替使用CPU
优点
资源利用率高
系统吞吐量大
缺点
平均运转时间长
无交互能力
需要解决的问题
处理机争夺
内存分配和保护
I/O分配问题
文件组织和管理
作业管理
用户与系统接口问题
操作系统： 是一组能有效的组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
分时系统
主要为了满足人机交互的需求
人机交互
用户对程序的控制和调试
共享主机
但是感觉像在独占主机
关键问题
及时接收
及时响应
作业直接进入内存
采用轮转方式运行
特征
多路性
允许多个终端同时链接到一台主机上
独立性
终端之间互不干扰
像是在独占主机
及时性
响应时间短
交互性
终端可以与系统进行实时的人机交互
实时系统
将时间作为关键参数
工业控制系统
信息查询系统
多媒体系统
嵌入式系统
与分时系统比较
多路性
系统周期性的对多路现场信息进行采集
独立性
对信息的采集和对对象的控制也都是彼此不干扰的
交互性
可靠性
多级容错措施来保障系统的安全性及数据的安全性
微机操作系统的发展
单用户单任务操作系统
CP/M
MS-DOS
单用户多任务操作系统
Windows
多用户多任务操作系统
UNIX OS
Solaris OS
Linux OS
1.3 操作系统的基本特征
并发性
并发与并行
并行
两个或多个事件在同一时刻发生
两个或多个事件在同一时间间隔内发生
引入进程
系统中能独立运行并作为资源分配的基本单位，是一个能独立运行的活动主体
共享性
资源共享或资源复用
指系统中的资源可供内存中多个并发执行的进行共同使用
互斥共享方式
资源虽然可以供过个进程使用，但是同时只能给一个资源使用
同时共享方式
允许在一段时间内由多个进程同时对其进行访问
虚拟性
时分复用
虚拟处理机
虚拟I/O设备
空分复用
虚拟存储
异步性
单处理机环境下
多个进程并发进行
但每次只能执行一个
运行情况不可预知
并发和共享是多用户OS的两个最基本特征
1.4 操作系统的主要功能
处理机管理功能
进程控制
为作业创建进程
撤销已结束的进程
控制进程运行过程中的的状态转换
进程同步
进程互斥方式
进程同步方式
进程通信
调度
作业调度
进程调度
存储器(内存)管理功能
内存分配
空间
利用率
内存保护
保证每道程序在自己的空间内运行
绝不允许用户程序访问操作系统的程序和数据
地址映射
逻辑地址和物理地址之间的映射
内存扩充
虚拟存储技术
请求调入功能
置换功能
设备管理功能
缓冲管理
设备分配
设备处理
驱动
文件管理功能
文件存储空间的管理
目录管理
文件的读/写管理和保护
操作系统与用户之间的接口
用户接口
联机用户接口
键盘操作命令 + 命令解释程序
脱机用户接口
为批处理作业用户提供
图形用户接口
程序接口
是用户程序取得操作系统服务的唯一途径
由系统调用组成
现代操作系统新功能
系统安全
认证技术
密码技术
访问控制技术
反病毒技术
网络功能和服务
网络通信
资源管理
应用互操作
支持多媒体
接纳控制功能
实时调度
多媒体文件的存储
1.5 操作系统结构设计
传统操作系统结构
无结构操作系统
此时的OS只是为数众多的一组过程的集合
模块化OS
优点:
提高OS设计的正确性\可理解性和可维护性
增强OS的可适应性
加速OS的开发过程
缺点:
设计阶段对各模块间的接口规定很难满足实际需求
分层式结构OS
自底向上分层设计
每一个层次仅能使用其底层所提供的功能和服务
优点:
易保证系统的正确性
易扩充和易维护
缺点:
系统效率降低
微内核OS结构
微内核 + 多个服务器
Windows
基于客户/服务器模式
将操作系统中最基本的部分放入内核中
操作系统中绝大部分功能都放在微内核外面的一组服务器(进程中)实现
微内核的基本功能
进程(线程)管理
低级存储器管理
中断和陷入处理
优点:
提高了系统的可扩展性
增强了系统的可靠性
可移植性强
提供了对分布式系统的支持
融入了面向对象技术
问题
系统运行效率有所降低
多次握手,导致多次上下文切换
第二章 进程的描述与控制
2.1 前驱图和程序执行
前驱图
描述程序执行的先后顺序
有向无循环图
结点表示一个进程、程序段、乃至一条语句
有向边表示两个结点之间存在的偏序关系
前驱
后继
初始节点
终止结点
权重
程序顺序执行
顺序性
每一个操作必须再下一个操作开始是之前结束
封闭性
程序运行时独占全机资源，只有本程序才能改变他
可再现性
重复执行，得到相同的结果
程序并发执行
共享和协作
间断性
程序执行“走走停停”
失去封闭性
抢资源
前驱后继关系
不可再现性
程序在并行执行时，由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，从而使程序的执行失去了可再现性
2.2 进程的描述
进程的定义及特征
进程定义
进程控制块（PCB）
操作系统利用PCB来描述进程的基本情况和活动过程
PCB+程序段+数据段 = 进程实体
不同角度的定义：
进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
进程时具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程的特性
动态性
进程实体是有生命周期的
并发性
多个进程实体同时存在于内存中，并且能在一段时间内同时运行
独立性
进程实体是一个能独立运行，独立获得资源和独立调度的进本单位
异步性
按照各自独立的不可预知的速度向前推进
进程vs程序
进程是动态的，程序是静态的
进程是暂时的，程序是永久的
进程与程序的组成不同
进程的基本状态及转换
三种基本状态
就绪态
万事俱备，只欠CPU
执行态
正在运行
阻塞态
缺少资源无法运行
创建状态和终止状态
创建
申请PCB
填写控制和管理信息
分配资源
插入就绪队列
终止
等待操作系统做善后处理
PCB清零，并将PCB空间返还系统
状态转换
创建--就绪
新进程资源分配完毕
就绪--运行
就绪进程获得CPU
运行--阻塞
执行受阻（需要I/O）
运行--就绪
CPU被剥夺(时间片到期)
阻塞--就绪
获得了等待得资源
终止
任何情况都能终止
挂起操作和进程状态得转换
挂起的引入
终端用户的需求
调式程序
父进程请求
符合调节的需要
将不重要的进程挂起
操作系统的需要
检查运行中的资源使用情况
引入挂起原语后的进程状态转换
活动j就绪--静止就绪
资源具备但不参与调度
活动阻塞--静止阻塞
不再继续分配支援
静止就绪--活动就绪
静止阻塞--活动阻塞
进程管理中的数据结构
用于管理控制的数据结构
内存表
设备表
文件表
进程表
进程控制块PCB的作用
使多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位
一个能与其他进程并发执行的进程
作为独立运行基本单位的标志.
系统创建进程为他建立了一个PCB,结束时又回收它
PCB是进程存在于系统的唯一标识
能实现间断性的运行方式
进程中断运行CPU现场保存在PCB中
提供进程管理需要的信息
进程状态
优先级
等待时间
执行时间
实现与其他进程的同步与通信
实现进程通信的区域或通信队列指针
PCB中的信息
进程标识符
用于唯一的标识一个进程
外部标识符
方便用户访问进程
字母_数组
内部标识符
方便系统对进程的使用
数字标识符
处理机状态
通用寄存器
用户可视寄存器
用于暂存信息
指令计数器
存放要访问的下一条指令的地址
程序状态字
条件码
执行方式
中断屏蔽标志
用户栈指针
存放过程和系统调用参数及调用地址
进程调度信息
进程状态
进程优先级
进程调度所需其它信息
与调度算法有关
事件
阻塞原因
进程控制信息
程序和数据的地址
进程同步和通信机制
消息队列指针\信号量
资源清单
已分配清单和未分配清单
链接指针
进程所在队列中下一个进程的PCB的首地址
进程控制块的组织方式
线性方式
所有PCB放在一个线性表中
实现j简单,开销小
查找时需要扫描整表
适合进程不多的系统
链接方式
把具有相同状态的进程连接成一个链表
索引方式
为不同状态的进程建立索引
2.3 进程控制
操作系统内核
处理机执行状态
系统态
内核态
执行一切指令,访问所有寄存器和存储区
用户态
目态
仅能执行规定的指令
支撑功能
中断处理
时钟管理
原语
由若干条指令组成, 用于完成一定功能的一个过程
不允许被中断
资源管理功能
进程管理
存储器管理
设备管理
进程的创建
进程的层次结构
父进程
创建进程的进程
子进程
被创建的进程称
可继承父进程所有的资料
进程组
进程与其子孙进程的集合
家族关系被记录在PCB中
进程图
进程树
引起进程创建的事件
用户登录
系统为用户创建进程
作业调度
作业被调进内存, 系统为其创建进程
提供服务
相应用户请求, 系统创建进程为用户进程提供服务
应用请求
用户进程创建进程\实现并发
创建过程
create原语
申请一个空白PCB
获得唯一数字标识
为新进程分配所需资源
物理\逻辑资源
内存\文件\I/O设备\CPU时间等
来自操作系统或者其父进程
初始化进程控制块PCB
1. 初始化标识信息
2. 初始化处理机状态信息
使程序计数器指向程序入口地址
栈指针指向栈顶
3. 初始化处理机控制信息
将进程状态置为就绪态
将进程优先级置为最低(一般情况)
4. 插入就绪队列
进程的终止
引起终止的事件
正常结束
用结束指令产生中断, 通知OS进程已经完成任务
异常结束
越界错
进程所访问的存储区, 已经超越该进程的区域
保护错
进程去访问不允许访问的资源或文件
非法指令
特权指令
用户进程执行了OS内核命令
运行超时
等待超时
算数运算错
I/O故障
外界干预
操作员或操作系统干预
父进程请求
父进程终止
终止过程
1. 根据被终止进程的标识符, 从PCB集合中检索出该进程的PCB
读取j进程状态
2. 若处于执行状态, 立即终止进程执行
置调度标志为真
指示进程将被重新调度
3. 若该进程有子孙进程
终止其子孙进程
4. 将被终止进程所拥有的所有资源归还给其父进程
或操作系统
5. 将被终止进程PCB从所在队列或链表中移除,等待其他程序来搜集信息
进程的阻塞与唤醒
引起阻塞或唤醒的事件
向系统请求共享资源失败
阻塞
获得所需资
被唤醒
等待某种操作的完成
阻塞
等待的操作完成
被唤醒
新数据尚未到达
阻塞
数据准备就绪
被唤醒
等待新任务的到达
阻塞
任务到达
被唤醒
阻塞过程
阻塞原语block
主动行为
过程
1. 停止执行状态的进程
PCB中的现行状态由执行改为阻塞
2. 将PCB插入阻塞队列
3. 转入调度程序进行重新调度
唤醒过程
唤醒原语wakeup
被动行为
过程
1. 将阻塞的进程从其等待队列中移出
2. 将其PCB的现行状态改为就绪
3. 将该PCB插入就绪队列
进程的挂起和激活
进程的挂起
挂起原语suspend
1. 检查被挂起进程的状态
2. 处于活动就绪的改为静止就绪
处于活动阻塞的改为静止阻塞
3. 把该进程的PCB复制到特定的内存区域
4. 若被挂起的进程正在执行, 转向进行调度
进程的激活
激活原语active
1.将进程从外存调入内存
2.检查进程状态
静止就绪变为活动就绪
静止阻塞变为活动阻塞
若采用抢占调度策略, 先比较当前运行进程与激活进程的优先级
决定是否重新调度,抢占CPU
2.4 进程同步
进程同步的基本概念
两种形式的制约关系
间接形式的制约关系
间接相互制约
互斥
抢
直接相互制约关系
同步
你先我后
临界资源
需要共享访问的资源
生产者消费者中的缓冲
临界区
进程中访问临界资源的代码
程序段
进入区
临界区
退出区
剩余区
同步机制应遵循的规则
空闲让进
无进程处于临界区，允许进入临界区
忙则等待
有程序进入临界区，禁止进入临界区
有限等待
在有限时间内处于等待状态，避免“死等”
让权等待
如果不能进入临界区，立即释放处理机，避免“忙等”
硬件同步机制
关中断
简单粗暴
进入临界区的时候屏蔽中断信号
阻止进程调度
缺点
导致系统瘫痪
关中断时间长，影响系统效率，限制并行性
不适用于多处理机系统
硬件锁
Test-and-Set
TS原语
lock为false表示资源空闲
Swap
SWAP原语
全局变量lock（初始false），局部变量key（初始true）
信号量机制
Dijkstra
Semaphore
整型信号量
一个用于表示资源数量的整型量S
操作
初始化
资源个数
P操作
wait操作
直至S>0, 执行S-- 操作
V操作
signal操作
执行S++操作
子主题 1
缺点
如果S<=0, 则不断测试
忙等
违背让权等待
记录型信号量
增加了等待进程的列表
P操作
S--
如果自减之后S<0, 则进程进入等待队列
V操作
S++
如果自加之后S依旧<=0, 则从就绪队列中唤醒一个进程
特点
S--后, 如果小于0, 则阻塞
满足让权等待
S, 表示可用资源的数量
S<0
没有资源可以分配
AND型信号量
针对需要两种或者多种共享资源的情况
相互等待
死锁
思想
将进程运行过程中所需要的资源, 一次性全部分配给进程
使用之后再一起全部释放
信号量集
记录型信号量的PV操作一次只能申请一个单位的临界资源
对AND型信号量机制加以扩充
在一次PV中完成所有资源的分配或释放
信号量的应用
实现进程互斥
设置互斥信号量
mutex
初始值为1
将各进程的临界区置于P(mutex) 和 V(mutex)之间
实现前驱关系
两个进程设置公用信号量S=0
进程P1，执行V(S)
进程P2, 执行P(S)
保证进程P2必须等待P1执行V(S)后才可以继续执行
管程机制
原因
信号量机制需要每个进程自行控制PV操作
系统管理复杂
容易产生死锁
定义
利用共享数据结构抽象的表示系统中的共享资源
将对该共享数据结构实施的特定操作定义为一组过程
申请
释放
其他操作
保证每次仅有一个进程进入管程
构成
管程名称
局部与管程的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句
代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了操纵系统的资源管理模块,我们称之为管程
特性
模块化
可以单独编译
抽象数据类型
既有数据, 又有对数据的操作
信息隐蔽
管程中的数据仅能通过管程访问
管程VS进程
数据结构
进程定义的是私有数据结构PCB
管程定义的是公共数据结构
操作
进程的操作与程序的顺序执行相关
管程进行同步和初始化等操作
目的
进程为了并发执行
管程为了解决共享资源的互斥操作
方式
进程是主动的工作方式
管程是被动工作
并发
进程之间并发执行
管程与调用者之间无法并发
动态性
进程有生命周期
管程一直存在, 供进程调用
同步工具
wait
signal
只有PV, 调用管程而被阻塞则其他进程无法进入管程
条件变量: condition
对条件变量的访问只能在管程中进行
形式
condition x, y;
只能使用PV操作对条件变量进行操作
条件变量也是一种抽象数据型
一个链表
该条件的阻塞队列
wait
将等待进程挂入队列, 释放管程
signal
重启阻塞队列中进程
2.5 经典同步问题
生产者消费者问题
利用记录型信号量
信号量
mutex
有人使用缓冲则其他阻塞
empty
空的资源数量
供生产者消耗, 由消费者产生
full
满的资源数量
供消费者消耗, 由生产者产生
生产者
wait(empty)
没有空资源, 则阻塞
wait(mutex)
signal(mutex)
signal(full)
full+1
消费者
wait(full)
没有满资源,则阻塞
signal(empty)
empty+1
利用AND型信号量
生产者
Swait(empty, mutex)
Ssignal(full, mutex)
消费者
Swait(full, mutex)
Ssignal(empty, mutex)
利用管程
名字
Producer-Consumer
过程
put(x)
生产者, 将产品放入缓冲中
count >= N 等待
get(x)
消费者, 将产品从缓冲中取出
count <= 0 等待
条件变量
notfull
notempty
哲学家就餐问题
利用记录型信号量
semaphore chopstick[5] = { 1, 1, 1, 1, 1}
哲学家i
P(chopstic[i])
P(chopstic[(i+1)%5])
eat
P(chopstic[i])
P(chopstic[(i+1)%5])
会发生死锁
解决方案
只允许最多4位哲学家同时去拿左边的筷子
只有左右两只筷子都可以用的时候才拿筷子
奇数哲学家先拿左边的筷子
偶数哲学家先拿右边的筷子
利用AND型信号量
Swait(chopstick[i] , chopstick[(i+1)%5])
Ssignal(chopstick[i] , chopstick[(i+1)%5])
读者-写者问题
利用记录型信号量
信号量
Wmutex
写互斥
Readcount=0
读者数量
rmutex
Readcount 写互斥
Reader
仅当Readcount==0时
wait(Wmutex)
Readcount+1
读者离开Readcount-1
仅当Readcont = 0时
signal(Wmutex)
Writer
wait(Wmutex)
开始写
写完毕
signal(Wmutex)
利用信号量集
信号量
L
限制读者数量
初始值为最大读者数量
Reader
Swait(L, 1, 1)
读者进入
L-1
Swait(mx, 1, 0)
read
Ssignal(L,1)
Writer
Swait(mx, 1, 1; L, RN, 0)
write
Ssignal(mx, 1)
2.6 进程通信
进程通信的类型
共享存储器系统(内存)
基于共享数据结构的通信方式
基于共享存储区的通信方式
管道通信系统
管道
一个文件
链接一个读进程和一个写进程以实现他们之间通信的一个共享文件
必须提供的协调能力
互斥
当一个进程对Pip执行读写操作的时候,其他进程必须等待
同步
写进程写一定数量的数据后等待
唤醒写进程
读进程读空数据后等待
唤醒读进程
确定对方存在时才进行通信
消息传递系统
以 格式化的消息为单位
数据封装在消息中
使用系统提供的原语在进程间进行消息传递
实现方式
直接通信
发送进程利用OS的发送原语
直接把消息发送给目标进程
间接通信
邮箱
客户机-服务器系统
不同计算机间的通信
实现方法
套接字
远程过程调用
远程方法调用
消息传递通信的实现方式
直接消息传递系统
直接通信原语
对称寻址
要求发送方和接收方必须以显示方式提供对方的标识符
一旦改编进程标识, 需查询其他所有进程是否与该进程有通信, 并修改
非对称寻址
接收进程的原语不需要发送进程的标识
消息的格式
比较短的定长消息
进程同步方式
发送阻塞
接收阻塞
发送不阻塞
接收阻塞
发送不阻塞
接收也不阻塞
通信链路
单向链路
双向链路
信箱通信
信箱的结构
信箱头
信箱体
若干个信箱格
传递方式
单向
双向
信箱通信原语
信箱的创建和撤销
信箱的发送和接收
信箱的类型
私用信箱
拥有者从邮箱中读取消息
单向通信链路
公用邮箱
系统创建
系统运行期间始终存在
所有进程使用
双向链路
共享邮箱
进程创建
指定共享进程(用户)
发送者和接收者关系
一对一
多对一
客户端/服务器交互
一对多
广播式
多对多
公用邮箱方式
直接消息传递系统实例
消息缓冲队列通信机制中的数据结构
消息缓冲区
PCB中有关通信的数据向
发送原语
接收原语
2.7 线程的基本概念
线程的引入
进程的两个基本属性
可拥有资源的独立单位
存储\I/O设备\文件\信号量等
可以独立调度和分派的基本单位
PCB
进程可并发执行的基础
进程并发执行所需付出时空开销大
创建\撤销\进程切换
线程
调度和分派的基本单位
线程与进程的比较
调度的基本单位
进程是资源分配的基本单位, 线程作为调度和分派的基本单位
并发性
不仅进程间可以并发执行, 进程中的多个线程也能并发执行
拥有资源
进程拥有系统资源
线程共享进程的资源
独立性
同进程中的线程之间与不同进程之间独立性要低得多
系统开销
线程切换的代价远远低于进程切换的代价
支持多处理机系统
线程状态和线程控制块
三状态
执行
就绪
阻塞
线程控制块(TCB)
线程标识符
一组寄存器
线程运行状态
优先级
专有存储区
信号屏蔽
堆栈指针
多线程OS中的进程属性
进程市可拥有资源的基本单位
多个线程可并发执行
进程已经不是可执行的实体
进程执行实际是其中的某一个线程正在执行
2.8 线程的实现
线程的实现方式
内核支持线程 KST
创建\阻塞\撤销和切换都在内核空间实现
优点
多处理机系统中,内核能够同时调度同一进程中的多个线程并行执行
如果进程中的一个线程被阻塞, 内核可以调度该进程中的其他线程占用处理器运行
KST具有很小的数据结构和堆栈, 线程切换较快, 开销小
内核本身也可以采用多线程技术, 提高系统的执行效率
缺点
对于用户的线程切换而言, 模式切换开销大
是由于用户进程的线程在用户态运行, 而线程的调度和管理是在内核实现的
用户级线程ULT
用户态实现, 无需内核支持
其调度仍是以进程为单位进程的
优点
线程切换无需转换到内核空间
调度算法是进程专用的
其实现方式与OS平台无关
缺点
一个线程被阻塞, 整个进程被阻塞
多线程应用无法利用多处理机进行多重处理
组合方式
多对一模型
将用户线程映射到一个内核控制线程
用户线程需要访问内核时, 将其映射到一个内核控制线程
优点
开销小, 效率高
缺点
一个被阻塞, 整个进程被阻塞
一对一模型
每个用户级线程都映射到一个内核支持线程上
优点
并发性更好
缺点
系统开销大
多对多
将多个用户级线程映射到同样数量或更少数量的内核线程上
线程的实现
内核支持线程的实现
用户级线程的实现
线程的创建和终止
创建
初始化线程
用于创建进程
终止
第三章 处理机调度与死锁
3.1 处理机调度的层次和算法调度的目标
处理机调度的层次
高级调度
长程调度
作业调度
调度对象是作业
功能
根据某种算法
将外存上处于后备队列中的某个作业调入内存
为他们创建进程、分配必要的资源
将其放入就绪队列
主要用于多道批处理系统
分时系统和实时系统中不设置高级调度
运行周期长
大约几分钟一次
低级调度
进程调度
短程调度
调度对象是进程或者内核级线程
功能
根据某种算法
决定就绪队列中哪个进程应获得处理机
由分派程序将处理机分配给选中的进程
最基本的调度
多道、分时和实时系统都必须配置
运行频率最高
通常10~100ms
中级调度
内存调度
主要目的
提高内存利用率和系统吞吐量
把暂时不能运行的进程，调至外存等待
挂起
具备运行条件后，再将进程调入内存等待运行
激活
处理机调度算法的目标
共同目标
资源利用率
CPU利用率
有效工作时间/(有效工作时间 + 空闲等待时间)
公平性
诸进程都应获得合理的CPU时间
相对性
相同类型的进程应获得相同的服务
不同类型的进程，根据重要性不同，提供不同的服务
平衡性
为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性
策略强制执行
对所制定的策略，只要有需要，就必须予以准确的执行
批处理系统的目标
平均周转时间短
周转时间
从作业被提交给系统开始，到作业完成为止
作业在后备队列中的等待时间
进程在就绪队列中的等待时间
进程在CPU上执行的时间
进程等待I/O操作的时间
平均带权周转时间
带权周转时间
W = 周转时间/ 系统提供服务时间
系统吞吐量高
吞吐量
单位时间内系统所完成的作业数
采用短作业，能提高吞吐量
处理机利用率高
单纯的提高处理机利用率，可以采用长进程
分时系统的目标
响应时间快
响应时间
从用户提交一个请求开始，系统给出响应的这段时间间隔
请求传到处理器的时间
处理器处理时间
响应信息传回的时间
均衡性
系统响应时间的快慢应与用户所请求服务的复杂度相适应
实时系统目标
截止时间的保证
截止时间
任务必须开始执行的最迟时间，或必须完成的最迟时间
可预测性
3.2 作业与作业调度
批处理系统中的作业
作业
程序+数据+说明书
从外存调入内存的基本单位
作业控制块
作业在系统中存在的标志
作业进入系统时，由“作业注册”程序为该作业建立JCB，挂到相应的后备队列中
三个阶段
收容阶段
执行阶段
结束
作业调度的主要任务
又称“接纳调度”
根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求
按照一定的调度算法，从外存的后备队列中选取某些作业调入内存
并为他们创建进程、分配必要的资源
决定
接纳多少个作业
取决于多道程序度
系统规模
运行速度
作业大小
等
接纳哪些调度
取决于调度算法
先来先服务
短作业优先
高响应比优先
先来先服务FCFS
既可用于作业调度也，可用于进程调度
按照到达的先后次序进行调度
优先考虑在系统中的等待时间最长的作业
很少单独使用
短作业优先SJF
既可用于作业调度也，可用于进程调度
按照作业运行时间长短进行调度
优先考虑预估运行时间最短的作业
缺点
必须预知作业运行时间
对长作业不利
饥饿
并未考虑道作业的紧迫程度
优先级调度算法PSA
即可用于作业调度，也可用于进程调度
FCFS 等待时间就是优先级
SJF 作业时间就是优先级
由外部赋予作业执行的紧迫程度作为优先级
高响应比优先调度算法HRRN
综合考虑了进程的等待时间和进程的执行时间
优先级 = （等待时间W + 要求服务时间R) / 要求服务时间R
响应比
3.3 进程调度
任务、机制和方式
任务
保存处理机的现场信息
按照某种算法选取进程
把处理机分配给进程
调度机制
排队器
给就绪的进程按照一定策略排队
优先级
分派器
取出就绪进程，进行上下文切换，将处理机分配给选出的进程
上下文切换器
①保存当前进程的上下文
②装配分派程序上下文
③将分派程序移出，新进程的CPU现场装入到处理机的各个寄存器中
调度方式
非抢占式
把处理机分配给某一个进程，直至其运行结束或者发生阻塞
优点
实现简单
系统开销小
适用于大多数批处理系统
不能用于分时系统和大多数实时系统
抢占式
允许调度程序暂停当前运行的程序，将处理机重新分配给另一个进程
抢占原则
优先权原则
短进程优先原则
时间片原则
轮转调度算法
基于时间片的轮转
让就绪队列上的每一个进程每次仅运行一个时间片，依次轮流使用处理机
原理
就绪进程按照FCFS排成就绪队列
系统每隔固定的时间激活调度程序进行调度
将CPU分配给就绪队列队首进程
未执行完的进程排到就绪队列的尾部
切换时机
程序在时间片内运行完毕
时间片用完
时间片大小
时间片小
系统开销增大
有利于短作业
时间片大
响应时间变长
最终退化为FCFS
优先级调度算法
算法类型
非抢占式优先级
程序结束后才能调度优先级最高的进程运行
抢占式优先级
进程执行期间，一旦出现优先级比其高的进程，就暂停当前进程，运行更高优先级的进程
优先级类型
静态优先级
整个进程运行期间保持不变
确定依据
进程类型
系统进程 > 用户进程
对资源的需求量
需求量小 > 需求量大
用户需求
付费用户 > 普通用户
简单易行\系统开销小
不够精准, 发生饥饿现象
动态优先级
进程创建之初赋予初始优先级
其后随着时间会发生改变
多队列调度算法
多个就绪队列
可采用不同的调度策略
多级反馈队列
调度机制
RR + FCFS + 优先级调度
多个就绪队列, 每个队列优先级不同
优先级越高的队列, 对应的时间片越短
被调度进程在时间片内没有完成, 进入下一级队列的队尾等待
算法性能
终端用户
响应时间快
快速处理交互
短作业
再较高优先级的队列中能快速处理完成
长作业
经过几个队列一定能完成
避免饥饿
减少进程切换次数
基于公平原则的调度算法
保证调度算法
跟踪进程执行时间
计算进程应进行的时间
计算进程获得CPU的时间比
选择时间比最小的进程将CPU分配给他
公平分享调度算法
针对用户
使每个用户拥有相同的处理机时间
3.4 实时调度
实时调度的基本条件
必要的信息
就绪时间
就绪状态的起始时间
开始截止时间和完成截止时间
处理时间
从开始执行到结束的时间
资源需求
优先级
系统处理能力强
采用单处理机
须增强其处理能
减少每个任务的处理时间
采用多处理机
采用抢占式调度
具有快速切换机制
对中断的快速响应能力
快速任务分派能力
实时调度算法的分类
非抢占式调度算法
非抢占式轮转调度算法
非抢占式优先调度算法
抢占式调度算法
基于时钟中断的抢占式优先级调度算法
延迟几十至几毫秒
立即抢占的优先级调度算法
几毫秒至100微秒
最早截止时间优先EDF
非抢占式调度方式用于非周期实时任务
抢占式调度方式用于周期实时任务
最低松弛度优先LLF
确定任务优先级时, 根据的是任务的紧急程度
松弛度
最晚完成时间 - 运行时间
优先级倒置
高优先级的进程被低优先级的进程延迟或阻塞
低优先级占用了高优先级的资源
解决办法
先进入临界区的低优先级进程继承高高优先级进程的优先级
优先执行
3.5 死锁概述
资源问题
可重用资源和消耗资源
可重用资源
资源的每个单元只能给一个进程使用
不能共享
使用过程
请求资源
使用资源
保持
释放资源
数量固定
不能被创建或销毁
消耗资源
进程运行期间动态的创建和消耗
特点
数量不断变化
有可能是0
资源用于消耗
使用后不再返回
可抢占资源和不可抢占资源
可抢占资源
进程获得资源后，还未释放，就被强制分配给其他进程
不可抢占资源
资源一旦分配，要等到进程主动释放，才能再分配给其他进程
计算机中的死锁
竞争不可抢占资源产生死锁
竞争可抢占资源产生死锁
死锁的根本原因
进程推进顺序不当导致死锁
死锁的主要原因
死锁的定义、必要条件和处理方法
定义
如果一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的事件，那么该组进程是死锁的
必要条件
互持条件
进程对资源需要互斥的使用
请求和保持条件
进程使用资源需要一定的时间，使用过程中不会释放
不可抢占条件
必须等进程主动释放，否则其他进程无法获取该资源
循环等待条件
必然存在一个相互等待的进程链
3.6 预防死锁
破坏死锁的四个必要条件
互持条件
对系统影响很大
不但不能破坏还应该加以保证
请求保持条件
第一协议
必须一次性申请所有资源，才能运行
简单
浪费资源
第二协议
允许获得初期资源后就开始运行
不可抢占条件
允许资源抢占
降低系统吞吐量
循环等待
给系统资源编号，申请时必须按顺序申请
3.7 避免死锁
系统安全状态
存在安全序列就是安全状态
安全感状态一定不死锁
不安全状态也未必发生死锁
银行家算法
分配资源前先检查如果分配会不会进入不安全状态
会
不分配资源
不会
正常分配资源
3.8 死锁的检测与解除
死锁的检测
资源分配图
死锁定理
S为死锁状态<==>资源分配图不能完全简化
死锁的解除
抢占资源
撤销进程
进程回退
第四章 存储器管理
4.1 存储器的层次结构
速度、容量、价格
4.1.1 多层结构的存储器系统
存储器的多层结构
至少有三层
寄存器
寄存器+高速缓存
主存
主存+磁盘缓存
辅存
固定磁盘+移动存储
可执行存储器
寄存器和主存
通过指令访问
辅存需要IO设备访问
4.1.2 主存储器与寄存器
主存储器
内存或主存
保存进程运行时的程序和数据
由于主存储器访问速度远低于CPU指令的执行速度，引入了寄存器和高速缓存
寄存器
具有与处理机相同的速度
价格却十分昂贵
4.1.3 高速缓存与磁盘缓存
高速缓存
介于寄存器和主存之间的存储器
主要用于备份主存中较常用的数据
速度越高，价格越贵
多级缓存
磁盘缓存
主存和IO设备之间
暂时存放频繁使用的部分磁盘数据和信息，以减少访问磁盘的次数
本身不是一种实际存在的存储器
而是利用主存中的部分空间
4.2 程序的装入和连接
编译（Compiler）
目标模块（Object Module）
链接（Linker）
Load Module
装入（Loader）
装入内存并运行
4.2.2 程序的链接（修改相对地址的过程）
程序经过编译后，可得到一组目标模块
链接程序的功能是将这组目标模块以及他们所需要的库函数装配成一个完整的装入模块
静态链接（static Linking）
程序运行之前，连成一个模块，以后不再拆开
相对地址的修改
变换外部调用符号
装入时动态链接（Load-time Dynamic Linking）
边装入边链接的方式
装入模块时发现它需要调用其他模块则将其他模块装入内存，并修改逻辑地址
优点
便于修改和更新
便于实现对目标模块的共享
运行时动态链接（Run-time Dynamic Linking）
对某些模块的链接推迟到程序执行时才进行
不仅能加快程序的安装过程
还可以节省大量的内存空间
4.2.1 程序的装入（修改物理地址的过程）
绝对装入方式（Absolute Loading Mode）
单道程序
知道程序在内存中的位置
逻辑地址和物理地址完全相同
可重定位装入方式（Relocation Loading Mode）
静态重定位
多道环境
逻辑地址从0开始
物理地址要等到装入时才知道
装入时对目标程序中指令和数据的地址进行修改
装入时，一次性修改
动态运行时的装入方式（Dynamic Run-time Loading）
程序在内存中移动
多次换入、换出
碎片整理
不立即把装入模块中的逻辑地址转换成物理地址
地址的转换推迟到程序真正运行的时候
需要一个重定位寄存器的支持
4.3 连续分配存储管理方式
4.3.1 单一连续分配
单道环境
内存=系统区+用户区
整个用户空间由用户独占
未采取保护措施
4.3.2 固定分区分配
多道环境
将用户空间划分为若干个固定大小的区域
分区大小相等
缺乏灵活性
分区大小不等
分区使用表
分区号
大小
起始地址
状态
通常按分区大小进行排序
内碎片，存储空间浪费
4.3.3 动态分区分配
又称可变分区分配
结构
空闲分区表
空闲分区链
分区分配操作
分配内存
①找到足够大的分区
②判断是否过于大了，如果太大，切割分区
回收内存
①根据回收区的首地址，从空闲表中找到相应的插入点
②开始回收
回收区与插入点前的一个空闲分区F1相邻
只需修改F1的大小
回收区与插入点后的一个空闲分区F2相邻
修改F2分区的起始地址和空间大小
回收区与插入点的前后两个分区都相邻
修改F1的大小，从分区表中删除F2分区
回收区与插入点的前后两个分区都不相邻
为回收区创建一个空闲分区表项
4.3.4 基于顺序搜索的动态分区分配算法 适用于不太大的系统
首次适应（first fit，FF）算法
从头查找，找到满足条件的分区为止
特点：
优先利用低地址部分内存
为以后的大作业的内存分配有利
产生大量不可利用的碎片
每次都从头找，增加查找开销
循环首次适应（next fit，NF）算法
从上次找到的分区向下查找，找到符合条件的分区为止
特点
使得内存中的空闲分区分布得更均匀
后期缺乏大的空闲空间
大作业无法执行
最佳适应（best fit，BF）算法
找到比当前分区大的最小的分区
特点
需要将分区表根据大小排序
存储器中会留下许多难利用的碎片
最坏适应（worst fit，WF）算法
总是挑选最大的分区
特点
产生碎片的可能性小
查询效率很高
每次找第一个
4.3.5 基于索引搜索的动态分区分配算法
快速适应（quick fit）算法
将空闲分区根据其容量大小进行分类
2K、4K、8K....
设立一张索引表，每个索引表对应一种分区类型
搜索方式
① 根据进程大小，从索引表中找到能容纳它的最小的分区链表
② 从链表中取下第一块进行分配即可
特点
效率高
不用分割
分区归还算法很复杂
系统开销大
存在内碎片
伙伴系统（buddy system）
哈希算法
利用哈希快速查找的优点
构造一张以空闲分区大小为关键字的哈希表
4.3.6 动态可重定位分区分配
紧凑
通过移动内存中作业的位置
把原来多个分散的小分区拼接成一个大分区
问题
经过紧凑后的程序在内存中的位置发生了变化
程序中的地址需要修改
动态重定位
重定位计数器
存放程序（数据）在内存中的起始地址
访问内存的地址=相对地址+重定位寄存器中的地址
动态重定位分区分配算法
增加了紧凑的功能
没有分区能满足要求的情况下，进行小分区的合并
外碎片
4.4 对换（Swapping）
4.4.1多道程序环境下的兑换技术
对换
把内存中暂时不能运行的进程或者展示不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程所需要的程序和数据换入内存
对换的类型
整体对换
挂起和激活
中程调度、内存调度
页面（分段）对换
部分对换
进程的换入与换出
换出
选择被阻塞或者睡眠状态的进程
选择优先级低的进程
申请对换空间
启动磁盘
回收内存空间
换入
找出“就绪”但是已经换出的进程
申请内存
成功
调入内存
修改PCB
失败
换出进程
4.5 分页存储管理方式
4.5.1 分页存储管理的基本方法
页面和物理块
将进程的逻辑空间分成若干页
页
把内存的物理地址空间也分成若干页
帧
页面大小相同 一般为2的整数次幂 windows页面大小为4K
地址结构
逻辑地址=页号+页内偏移
物理地址=帧号+帧内偏移
页表
实现页号到帧号的地址映射
4.5.2 地址变换机构
任务
将逻辑地址中的页号转换为内存中的物理块号
基本地址变换机构
硬件实现
页表驻留在内存中
页基址寄存器（PTR，Page-table Register）
页表的内存地址
表长
机构
① 越界判断
② 转换
物理地址=页表起始地址+页号*页表项长度 + 偏移量
具有快表的地址变换机构
起因
页表导致存取一个数据要访问两次内存
一次页表
第二次存取
快表
联想寄存器
TLB
访问页表前先访问快表
命中后则减少一次访存
据统计，快表命中率可达到90%以上
4.5.3 访问内存有效时间
从进程发出指定的逻辑地址的访问请求开始
经过地址变换
到内存中找到实际物理地址单元并取出数据
的总时间
EAT = a×λ + (t+λ)(1-a) + t = 2t + λ + t×a
4.5.4 两级和多级页表
引入
程序逻辑空间很大
导致页表项很多
导致页表很大
解决
将页表分页
建立页表的页表
逻辑地址分成三段：外层页号+外层页内地址+页内地址
页表的页表也可以分页
多级页表
4.5.5 反置页表
为每一个物理帧设置页表项
按照物理帧的编号排序
页表项中有进程号和页号
地址变换
根据进程号和页号检索页表的序号
页表的序号既是物理帧号
4.6 分段存储管理方式
4.6.1 目的
为了满足用户（程序员）再编程和使用上的多方面的要求
方便编程
将作业按逻辑关系分成若干段
信息共享
共享是以逻辑单位为基础的
分段的方式能极大的简化共享的实现
信息保护
可以根据段设置访问的权限
动态增长
动态链接
4.6.2 基本原理
分段
作业的地址空间被划分为若干个段
每个段定义了一组逻辑信息
用一个段号代替段名
每个段都从0开始编址
采用连续的地址空间
逻辑地址=段号 + 段内地址
段表
段号+段长+基址
地址变换机构
段表基址寄存器
段表的首地址+段表长度
① 越界判断
段号是否超过段表长
② 段内越接
段内偏移是否超过段长
③ 生成地址
段基址+段内偏移
两次访存
可加TLB
分段vs分页
页是信息的物理单位，段是信息的逻辑单位
页的大小由系统决定，段的大小由用户决定
分页程序的地址空间是一维的，分段程序的地址空间是二维的
4.6.3 段信息共享
4.6.4 段页式存储管理方式
基本原理
先将程序分成若干段
再把每个段分成若干页
系统中需要同时配置段表和页表
一个进程有一个段表和若干个页表
逻辑地址=短号+段内页号+页内地址
段表
段号 + 页表起始地址 + 页表大小
页表
页号 + 帧号
地址变换
段表基址寄存器
段表首地址 + 段表长度
① 段越接判断
段号是否超过段表长度
② 页越接判断
段内页号是否超过页表大小
③ 生成地址
帧号+页内偏移
三次访存
段表
页表
读取
第五章 虚拟存储
并非从物理上实际地扩大内存容量，而是从逻辑上实现对内存容量的扩充
5.1 虚拟存储器概述
原因：内存容量不够大
有的作业很大
存储要求大于物理内存
有大量作业要求运行
内存无法容纳所有进程
5.1.1 常规存储管理方式和局部性原理
传统的特征
一次性
想要运行必须一次性加载
驻留性
运行过程中不能调出内存
局部性原理
时间局部性
当前运行的不久还会再次被运行
空间局部性
当前使用的存储单元的附近的存储单元也即将被访问
虚拟存储器的基本工作情况
5.1.2 虚拟存储器的定义和特征
虚拟存储器的定义
具有调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
虚拟存储器的特征
多次性
多次调入调出
对换性
无需常驻内存
虚拟性
改善内存利用率
提高程序并发程度
增加系统的吞吐量
5.1.3 虚拟存储器实现方法
请求分页系统
分页页表机制
缺页中断机构
地址变换机构
请求分段系统
5.2 请求分页存储管理方式
5.2.1 请求分页中的硬件支持
请求页表机制
存在位P
访问位A
修改位M
缺页中断机构
在指令执行期间产生和处理中断信号
一条指令执行期间可能产生多次缺页中断
地址变换机构
越界判断
TLB
内存
外存
返回时内存调度算法
5.2.2 请求分页中的内存分配
最小物理块数
能让进行运行的最小的物理帧数
内存分配策略
固定分配局部置换
可变分配全局置换
可变分配局部置换
物理块分配算法
平均分配
按比例分配
考虑优先权的分配
5.2.3 页面调入策略
何时调入
预调页策略
一次调入若干相邻的页
请求调页策略
不在时发出请求，OS进行调入
从何处调入
从对换区调入
从文件区调入
UNIX方式
文件放在文件区
未运行过的页面从问件区调入
被换出的页面放入对换区
再次使用时从对换区调入
页面调入过程
子主题 1
缺页率
f=F/A
F缺页次数
A所有访存次数
缺页中断处理时间
t=β*t1 + （1-β）* t2
t1
缺页中断处理时间
t2
被置换的页面没有被修改的处理时间
β
被置换的页面被修改的概率
5.3 页面置换算法
最佳置换算法Optimal
选择以后永久不用或者最长时间内不会被访问的页面
先进先出FIFO
淘汰最先进入内存的页面
最近最久未使用LRU
局部性原理
选择最长时间没被使用的页面
最近最少使用LFU
近期使用最少的页面淘汰
时钟置换算法CLOCK
循环队列
简单时钟
检测访问位
淘汰下一个，访问位为0的页面
如果不为0，则访问位置0，下次再淘汰
改进时钟
检测访问位和修改位
第一轮
淘汰下一个访问位和修改位都是0的页面
第二轮
淘汰下一个访问位时0，修改位是1的页面，同时将访问位不是0的置零
重复第一步
重复第二轮
一定能找到淘汰页面
页面缓冲算法PBA
子主题 1
访存有效时间EAT
λ：查找快表时间
t：访问内存时间
快表命中
EAT = λ + t
快表不命中
页面在内存
EAT = λ + t + λ + t = 2 * (λ+t)
页面不在内存
EAT = λ + t + e + λ + t = e +2*(λ+t)
快表命中率a
缺页率f
EAT = λ + a*t + (1-a) * [ t + f * ( e + λ + t) + ( 1-f ) * ( λ + t )]
5.4 抖动与工作集
5.4.1 多道程序读与“抖动”
多道程序共享内存
适量
提高内存利用率
超量
提升各个进程缺页率
进程太多
分配的物理块太少
不能满足进程的正常运行需求
5.4.2 工作集
某段时间间隔Δ内，进程实际所要访问页面的集合
w( t , Δ )
t
时刻
Δ
窗口尺寸
5.4.3 抖动的预防
采取局部置换策略
把工作集算法融入到处理机调度中
利用“L=S”准测调节缺页率
L
缺页之间的平均时间
S
平均缺页处理时间
选择和暂停
5.5 请求分段存储管理方式
5.5.1硬件
请求段表机制
增补位
本段在运行中是否动态增长
缺段中断
段不在内存
内存是否有空闲
合并空闲区
淘汰几个段
读入
读入
地址变换
越接判断
权限判断
是否在内存
修改位、访问位
5.5.2 分段的共享与保护
共享段表
进程计数
分配与回收
读者写者
第六章 出入输入系统
6.1 I/O系统的功能模型和接口
I/O系统的基本功能
隐藏物理设备的细节
与设备无关性
提高处理机和I/O设备的利用率
对I/O设备进行控制
确保对设备的正确共享
错误处理
I/O系统的层次结构和模型
上层接口
系统接口
块设备结构
流设备接口
网络通信接口
4个层次
用户层I/O软件
设备独立性软件
设备驱动程序
中断处理程序
底层接口
软硬件接口
6.2 I/O设备和设备控制器
I/O设备
I/O设备类型
按使用特性
存储设备
外存、缓存
I/O设备
输入设备、输出设备、交互设备
按速率
低速设备
键盘鼠标
中速设备
打印机、扫描仪
高速设备
硬盘、光盘等
设备与控制器之间的接口
数据信号
控制信号
状态信号
设备控制器
基本功能
接收和识别命令
数据交换
标识和报告设备状态
地址识别
数据缓冲
差错控制
组成
设备控制器与处理机的接口
设备控制器与设备的接口
I/O逻辑
内存映像I/O
I/O通道
6.3 中断机构和中断处理程序
中断简介
中断和陷入
中断
外中断
指CPU对I/O设备发来的中断信号的一种响应
停止当前进程
进行中断处理程序
回到原来进程继续执行
陷入
程序内部出现错误
停止当前进程
处理陷入
中断向量表和中断优先级
中断向量表
每一个设备的初段处理程序的入口 的列表
中断优先级
多源中断处理方式
正在处理中断时又来中断信号
屏蔽中断
不处理其他中断
嵌套中断
判断优先级
中断处理程序
测定是否有未响应的中断信号
保护被中断进程的CPU环境
转入相应的设备处理程序
中断处理
恢复CPU现场并退出中断
6.4 设备驱动程序
设备驱动程序概述
功能
接收与设备无关的软件发来的命令和参数
转换成设备相关的底层序列
检查用户I/O请求的合法性
了解设备工作状态
设置设备工作方式
发出I/O命令
启动I/O设备
完成I/O操作
响应设备的中断请求
特点
联系与设备无关的软件和设备控制器
与硬件密切相关
与I/O控制方式密切相关
中断
DMA
允许可重入
设备处理方式
为每一类设备设置一个进程，专门用于执行这类设备的I/O操作
为整个系统设置一个I/O进程，专门用于执行系统中各类设备的I/O操作
不设专门的设备处理进程
设备驱动程序的处理过程
对I/O设备的控制方式
轮询的可编程I/O方式
使用中断的可编程I/O方式
直接存储器访问方式（DMA）
通道
6.5 与设备无关的I/O软件
子主题 1
6.6 用户层I/O软件
系统调用
库函数
假脱机系统
输入井和输出井
在磁盘上开辟出来的两个存储区域
输入缓冲区和输出缓冲区
内存中开辟的两个缓冲区
输入进程和输出进程
井管理程序
特点：
提高了I/O速度
将独占设备改造成了共享设备
实现了虚拟设备功能
6.7 缓冲区管理
引入原因
缓和CPU与I/O设备间速度不匹配的矛盾
减少对CPU的中断频率，放宽CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU与I/O设备的并行性
单缓冲区和双缓冲区
单缓冲区
每块数据处理时间=Max（C，T）+M
双缓冲区
每块数据处理时间=Max（C，T）
环形缓冲区
构成
多个缓冲区+多个指针
缓冲池
构成
空白缓冲队列
输入缓冲队列
输出缓冲队列
6.8 磁盘存储器的性能和调度
磁盘性能概述
数据的组织和格式
磁盘
盘面
磁道
扇区
磁盘访问时间
寻道时间
旋转延迟时间
数据传输时间
磁盘调度算法
FCFS
先来先服务
SSTF
最短寻道时间优先
SCAN
扫描算法
电梯调度算法
CSCAN
循环扫描算法
打字机
第七章 文件管理
7.1 文件和文件系统
数据项、记录和文件
数据项
最低级的数据组织形式
记录
一组相关数据项的集合
文件
由创建者定义的、具有文件名的相关元素的集合
在文件系统中的最大数据单位，描述了一个对象集
文件名和类型
文件名和扩展名
文件名，文件的标识
扩展名，文件类型标识
文件类型
按用途
系统文件
用户文件
库文件
按数据形式
源文件
目标文件
可执行文件
按存取控制属性
执行文件
只读文件
读写文件
按组织形式和处理方式
普通文件
目录文件
特殊文件
文件系统的层次结构
将对象及其属性
文件
目录
存储空间
对对象操纵和管理的软件集合
文件存储空间管理
文件目录管理
逻辑地址转物理地址的机制
文件读写管理
文件共享和保护
层次结构
I/O控制层
文件系统最底层
设备驱动层
基本文件系统层
处理内存与磁盘之间数据块的交换
基本I/O管理程序
地址转换
空闲空间管理
I/O缓冲区的指定
逻辑文件系统
处理与记录和文件相关的事物
接口
命令接口
用户与文件系统
程序接口
程序与文件系统
文件操作
基本操作
创建
删除
读
写
设置读写位置
7.2 文件的逻辑结构
逻辑结构的类型
按是否有结构
按组织方式
顺序文件
串结构
按先后顺序，无关键字
顺序结构
指定关键字
优缺点
存取效率最高
插入和删除比较困难
记录寻址
隐式方式
适用定长记录
边长记录需要指定记录长度
显示寻址
子主题 1
索引文件
按关键字建立索引
优点
将一个需要顺序查找的文件改造成一个可随机查找的文件
缺点
增加了存储开销
索引顺序文件
特征
引入了索引表
实现随机访问
增加了溢出文件
记录新增的、删除的和修改的记录
直接文件和哈希文件
7.3 文件目录
目录管理
实现“按名存取”
提高对目录的检索速度
文件共享
允许文件重名
文件控制块和索引节点
FCB
基本信息
文件名
文件物理位置
文件逻辑结构
文件物理结构
存取控制信息
读取权限
使用信息
创建时间
上次修改时间
已打开文件的进程数
索引节点inode
文件主标识
拥有者
文件类型
文件存取权限
文件物理地址
文件长度
文件链接计数
文件存取时间
简单文件目录
单级文件目录
优点：简单
缺点
查找速度慢
不允许重名
不便于共享
多级文件目录
提高了检索目录的速度
不同用户的目录中可以使用相同的文件名
不同用户还可以使用不同的文件名访问系统中的同一个共享文件
树形结构目录
当前目录
绝对路径与相对路径
目录操作
创建目录
删除目录
改变目录
移动目录
链接操作
查找
7.4 文件共享
基于有向无循环图实现文件共享
利用索引节点
硬链接
利用符号链接实现文件共享
软链接
7.5 文件保护
保护域
访问矩阵
第八章 磁盘存储器管理
8.1 外存的组织形式
连续组织方式
优点
顺序访问比较容易
顺序访问速度快
缺点
要求为一个文件分配连续的存储空间
必须事先知道文件的长度
链接组织方式
优点
消除外部碎片，提高内存利用率
对插入删除和修改记录都非常容易
能够适应文件的动态增长
索引组织方式
单级索引组织方式
多级索引组织方式
增量式索引组织方式
8.2 文件存储空间的管理
空闲表发和空闲链法
位示图法
组成链接法
8.3 提高磁盘I/O的速度途径
磁盘高速缓存
置换算法
其他方法
提前读
延迟写
优化物理块分布
虚拟盘
冗余磁盘阵列（RAID）
-0
条带化
-1
磁盘镜像
-3
奇偶校验
-5
分布式奇偶校验
第十章 多处理机系统
第11章 多媒体操作系统
第九章 操作系统接口
第12章 保护和安全