计算机操作系统（第4版）汤小丹、汤子瀛
2020-06-30 17:05:32 72 举报AI智能生成
登录查看完整内容
《计算机操作系统（第4版）》是汤小丹、汤子瀛编著的一本经典教材，全面介绍了计算机操作系统的基本概念、原理和实现方法。本书深入浅出地讲解了操作系统的内核管理、进程管理、内存管理、文件系统等核心内容，并通过丰富的实例和案例分析，帮助读者深入理解操作系统的工作原理和应用场景。此外，本书还介绍了现代操作系统的最新发展动态和技术趋势，为读者提供了广阔的学习视野和思考空间。无论是计算机专业的学生还是从事相关工作的专业人士，都可以从本书中获得宝贵的知识和经验。
作者其他创作
大纲/内容
第五章：虚拟存储器
常规存储管理方式的特征
一次性
作业一次性全部装入内存才能运行
驻留性
作业进入内存就不能换出
局部性原理
程序在执行时将呈现出局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域
时间局限性
如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作
空间局限性
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。
定义
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
优点
大程序：可在较小的可用内存中执行较大的用户程序；
大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)
并发：可在内存中容纳更多程序并发执行；
易于开发：不必影响编程时的程序结构
以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术
特征
离散性
指在内存分配时采用离散的分配方式，它是虚拟存储器的实现的基础
多次性
指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征
对换性
指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。
虚拟性
指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
实现方式
分页请求系统
硬件支持
请求页表机制
页表项
缺页中断机构
在指令执行期间产生并处理的中断
执行一条指令可能发生多次
地址变换机构
内存分配
最小物理块数的确定
即能保证进程正常运行所需的最小物理块数
与指令格式、功能、寻址方式有关
内存物理块分配策略
固定分配局部置换
一个进程分配的物理块数固定
可变分配全局置换
进程运行期间一个进程分配的物理块数可变
可变分配局部置换
频繁发生缺页中断再增加物理块
物理块分配算法
平均分配算法
按比例分配算法
根据进程页面数多少
考虑优先权的分配算法
页面调入策略
系统应在何时调入所需页面
预调页策略
一次调多页
请求调页策略
一次调一页
系统应该从何处调入这些页面
对换区
文件区
系统有足够对换空间时
全部从对换区
进程运行前先把相关文件放入对换区
系统没有足够
不会被修改的文件直接从文件区调入，所以换出的时候不用换到外存
可能被修改的文件从对换区
UNIX方式
未运行过的从文件区
运行过的从对换区
调入过程
缺页率
页面大小
进程分配的物理块的数目
页面置换算法
程序自身的特性
局部化程度
抖动
即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出
算法
最佳置换算法
理想状态最牛批的算法
先进先出页面置换算法（FIFO）
选择在内存中驻留时间最久的页面予以淘汰
最近最久未使用置换算法（LRU）
每个页面配备一个移位寄存器支持
栈支持
每次移除栈底的
最少使用置换算法（LFU）
clock置换算法NRU（LRU的近似算法）
普通
不需要硬件支持，只需要在页表项设置访问位
循环检索每个页表项，换出访问位为0的
若访问位为1，置为0
改进
再增加一个修改位，考虑到换出修改页的代价
空闲页面链表
空闲物理块
修改页面链表
减少修改页面换出的频率
抖动与工作集
多道程序度
CPU利用率先升后降
工作集
在单位时间间隔里，进程实际要访问的页面的集合。
抖动预防方法
采取局部置换
不允许从其他进程获取物理块
融合工作集算法
L=S准则
缺页平均时间=缺页服务时间
选择暂停进程
请求分段系统
请求分段的段表机制
缺段中断机构
分段的共享与保护
共享段表
分段保护
越界检查
存取控制检查
环保护机构
第六章：输入输出系统
I/O系统管理的对象是I/O设备和相应的设备控制器。
I/O系统的基本功能
隐藏物理设备的细节
与设备的无关性
提高处理机和I/O设备的利用率
对I/O设备进行控制
查询
中断
DMA
IO通道
确保对设备的正确共享
独占设备
共享设备
错误处理
临时性错误
永久性错误
I/O软件的层次结构
模块之间的层次视图
IO系统的上下接口
图
块设备接口
块设备
指以数据块为单位来组织和传送数据信息的设备
典型的块设备是磁盘、光盘
随机地读/写任意一块
隐藏磁盘的二维结构
将抽象命令映射为底层操作
流设备接口
字符设备
不可寻址
I/O常采用中断驱动方式
get、put操作
字符缓冲区
in-control命令
统一处理所有字符设备
互斥，需要打开与关闭
网络通信接口
I/O系统的分层
中断处理程序
设备驱动程序
设备独立性软件
IO软件独立于具体使用的物理设备
I/O设备和设备控制器
IO设备
执行IO操作的物理部分
设备控制器
执行控制IO的电子元件
分类
使用特性分
存储设备
I/O设备
输入
输出
交互
传输速率分
低速设备（几字节——几百字节）
典型的设备有键盘、鼠标、语音的输入
中速设备（数千——数万字节）
典型的设备有行式打印机、激光打印机
高速设备（数十万——千兆字节）
典型的设备有磁带机、磁盘机、光盘机
设备与控制器间的接口
数据信号
控制信号
状态信号
主要功能
控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
基本功能
接收和识别命令
控制寄存器、命令译码器
数据交换
实现CPU与控制器，控制器与设备间的数据交换
标识和报告设备的状态
地址识别
配置地址译码器，识别不同的设备
数据缓冲区
差错控制
设备控制器的组成
与CPU的接口
实现CPU与设备控制器之间的通信
与设备的接口
控制器可连接多个设备
I/O逻辑
实现对设备的控制
CPU利用该逻辑向控制器发送I/O命令
命令、地址译码
寻址方式
特殊IO指令
内存映像
I/O通道
目的
解放CPU，实现并行
是一种特殊的处理机，具有通过执行通道程序完成I/O操作的指令
指令单一(局限于与I/O操作相关的指令)，与CPU共享内存
基本过程
CPU向通道发出I/O指令
通道接收指令
从内存取出通道程序处理I/O
向CPU发出中断
通道类型
字节多路通道
低中速连接子通道时间片轮转方式共享主通道
字节多路通道不适于连接高速设备，这推动了按数组方式进行数据传送的数组选择通道的形成。
数组选择通道
这种通道可以连接多台高速设备，但只含有一个分配型子通道，在一段时间内只能执行一道通道程序， 控制一台设备进行数据传送， 直至该设备传送完毕释放该通道。这种通道的利用率很低。
数组多路通道
含有多个非分配型子通道，前两种通道的组合，通道利用率较好
瓶颈问题
原因;通道不足
解决办法：增加设备到主机间的通路，而不增加通道（结果类似RS触发器）
中断机构和中断处理程序
对外部I/O设备发出的中断信号的响应
陷入
由CPU内部事件引起的中断
中断向量表
中断程序的入口地址表
中断优先级
对紧急程度不同的中断处理方式
对多中断源的处理方式
屏蔽中断
嵌套中断
测定是否有未响应的中断信号
保护被中断进程的CPU环境
转入相应的设备处理程序
中断处理
恢复CPU 的现场并退出中断
是I/O进程与设备控制器之间的通信程序，又由于它常以进程的形式存在，故以后就简称为设备驱动进程
主要任务是接受来自它上一层的与设备无关软件的抽象请求，并执行这个请求。
功能
接收由I/O进程发来的命令和参数， 并将命令中的抽象要求转换为具体要求。例如，将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。
检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。
发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。
及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。
对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。
设备驱动程序的处理过程
将用户和上层软件对设备控制的抽象要求转换成对设备的具体要求，如对抽象要求的盘块号转换为磁盘的盘面、磁道及扇区。
检查I/O请求的合理性。
读出和检查设备的状态，确保设备处于就绪态。
传送必要的参数，如传送的字节数，数据在主存的首址等。
启动I/O设备，并检查启动是否成功，如成功则将控制返回给I/O控制系统，在I/O设备忙于传送数据时，该用户进程把自己阻塞，直至中断到来才将它唤醒，而CPU可干别的事。
对I/O设备的控制方式
I/O控制的宗旨
减少CPU对I/O控制的干预
充分利用CPU完成数据处理工作
I/O 控制方式
轮询的可编程I/O方式
中断驱动I/O方式
DMA控制方式
I/O通道控制方式
DMA控制器组成
主机与DMA控制器的接口
DMA控制器与块设备的接口
I/O控制逻辑
与设备无关的I/O软件
基本概念
应用程序独立于具体使用的物理设备。
驱动程序是一个与硬件(或设备)紧密相关的软件。为实现设备独立性，须在驱动程序上设置一层软件，称为设备独立性软件。
设备独立性(Device Independence)的优点
以物理设备名使用设备
引入了逻辑设备名
逻辑设备名称到物理设备名称的转换（易于实现I/O重定向）
与设备无关的软件
设备驱动程序的统一接口
缓存管理
对独立设备的分配与回收
独立于设备的逻辑数据块
设备分配中的数据结构
设备控制表DCT
记录设备的情况
控制器控制表COCT
通道控制表CHCT
显然，在有通道的系统中，一个进程只有获得了通道，控制器和所需设备三者之后，才具备了进行I/O操作的物理条件
系统设备表SDT
逻辑设备表LUT
分配的流程，从资源多的到资源紧张的:LUT->SDT->DCT->COCT->CHCT
在申请设备的过程中，根据用户请求的I/O设备的逻辑名，查找逻辑设备和物理设备的映射表；以物理设备为索引，查找SDT，找到该设备所连接的DCT；继续查找与该设备连接的COCT和CHCT，就找到了一条通路。
用户层的I/O软件
系统调用与库函数
OS向用户提供的所有功能，用户进程都必须通过系统调用来获取
在C语言以及UNIX系统中，系统调用（如read）与各系统调用所使用的库函数（如read）之间几乎是一一对应的。而微软的叫Win32API
假脱机系统（spooling）
spooling技术是对脱机输入/输出系统的模拟
主要组成
输入/输出井
输入/输出缓冲区
输入/输出进程
井管理程序
特点（体现操作系统的虚拟性）
提高了I/O的速度
对数据所进行的I/O操作，已从对低速设备演变为对输入井或输出井中的数据存取。
将独占设备改造为共享设备
实际分给用户进程的不是打印设备，而是共享输出井中的存储区域
实现了虚拟设备功能
将独占设备变成多台独占的虚拟设备。
缓冲区管理
引入原因
缓和CPU与I/O设备间速度不匹配的矛盾
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU和I/O设备之间的并行性
类型
单缓冲区
即在CPU计算的时候，将数据数据输入到缓冲区(大小取决与T和C的大小)
双缓冲区
即允许CPU连续工作（T不断）
环形缓冲区
组成
多个缓冲区
多个指针
使用
Getbuf过程
Releasebuf过程
同步问题
缓冲池
空白缓冲队列（emq）
由空缓冲区链接而成F(emq)，L(emq)分别指向该队列首尾缓冲区
输入队列（inq）
由装满输入数据的缓冲区链接而成F(inq)，L(inq)分别指向该队列首尾缓冲区
输出队列（outq）
由装满输出数据的缓冲区链接而成F(outq)， L(outq)分别指向该队列首尾缓冲
Getbuf和Putbuf过程
收容：缓冲池接收外界数据
提取：外界从缓冲池获得数据
缓冲区工作方式（从缓冲区的角度来看）
收容输入
提取输入
收容输出
提取输出
磁盘存储器的性能和调度
数据的组织和格式
物理盘片
存储面
磁道
扇区
间隙
结构与格式化
磁盘的类型
固定头磁盘（贵）
移动头磁盘
磁盘访问的时间
寻道时间Ts
启动磁臂的时间s
磁头移动n条磁道的时间m*n
旋转延迟时间Tr
子主题
传输时间Tt=b/rN
总时间Ta=Ts+1/2r+b/rN
磁盘的调度算法（掌握图表）
先来先服务（FCFS）
优点：公平，简单
缺点：可能导致某些进程的请求长期得不到满足
最短寻道时间优先（SSTF）
要求访问的磁道和当前磁头所在的磁道距离最近，以使每次的寻道时间最短
扫描算法（SCAN）
扫描算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁道当前的移动方向
电梯调度算法
可防止低优先级进程出现“饥饿”的现象
循环扫描算法（CSCAN）
算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描
NStepScan算法
N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次这些子队列。
FSCAN算法
是Nstepscan算法的简化，将磁盘请求队列分成两个子队列
第七章：文件管理
数据组织形式
数据项
基本数据项
描述一个对象的某种属性的字符集
组合数据项
记录
一组相关数据项的集合，用于描述一个对象在某个方面的属性
文件
文件属性
文件类型
文件长度
文件的物理位置
文件的建立时间
文件名和类型
文件名
扩展名
用途
系统文件
用户文件
库文件
数据形式
源文件
目标文件
可执行文件
存取控制属性
只执行文件
只读文件
读写文件
组织形式和处理方式
普通文件
目录文件
特殊文件
文件系统
层次
管理对象
目录
磁盘存储空间
软件集合
存储空间的管理
文件目录的管理
将文件的逻辑地址转换为物理地址
对文件读和写的管理
对文件的共享和保护
软件层次
IO控制层
磁盘驱动程序
基本文件管理层
处理内存和数据块之间的交换
基本IO管理程序
逻辑块号转换为物理块号
管理磁盘空闲盘块
IO缓冲指定
逻辑文件系统
处理与记录和文件相关的操作
文件系统接口
命令接口
键盘终端
程序接口
通过系统调用
文件操作
基本操作
创建文件
分配外存空间
建立目录项
删除文件
删除目录项
回收外存空间
读文件
根据用户名查找目录
使用指针读
写文件
使用指针写
设置文件读写的位置
可改为随机存取
打开与关闭
打开
系统将文件属性从外存拷贝到内存的一个表目中
返回表目的编号
关闭
断开连接
其他
设置文件属性
目录操作
文件共享
文件的逻辑结构
是否有结构
有结构文件
无结构文件
流式文件
组织方式
顺序文件
结构
串结构
顺序结构
记录寻址方式
隐式寻址
显式寻址
索引文件
索引表
每个记录一个表项
索引顺序文件
每组第一个记录一个表项
哈希文件
文件目录
目录管理要求
实现按名存取
提高目录检索速度
多用户共享
允许文件重名
不同用户
文件控制块（FCB）
基本信息
文件物理位置
设备名
盘块号
盘块数
文件逻辑结构
文件物理结构
链接式文件
存取控制信息类
使用信息类
索引结点
磁盘索引结点
内存索引结点
简单的文件目录
单级文件目录
查找慢
不允许重名
不便于实现文件共享
两级文件目录
提高检索速度，从M*N到M+N
树形结构目录
路径名
“..”是父目录
“/”是根目录
区别绝对路径和相对路径（../.../.../1/2/3/）
目录查询技术
线性检索法
哈希法
有向无循环图（DAG）
利用符号链接实现文件共享
实际上就是“快捷方式”
文件保护
保护域
访问权
访问矩阵
第八章：磁盘存储器的管理
外存的组织方式
连续组织方式
链接组织方式
隐式
显式
索引组织方式
混合索引方式
NTFS
文件存储空间的管理
空闲表法
连续分配方式
空闲链表法
离散分配
位示图法
成组链接法
提高磁盘IO速度的途径
磁盘高速缓存
内存中的一缓冲区
提前读
延迟写
优化物理块布局
虚拟盘
RAID
提高磁盘可靠性
第一级容错技术SFT-1
第二级容错技术SFT-2
基于集群技术的容错
后备系统
数据一致性控制
计算机操作系统（第4版）汤小丹、汤子瀛
一.操作系统引论
0.介绍
计算机上的第一层软件
对硬件功能的首次扩充
1.操作系统的目标和作用
目标
方便性
有效性
提高系统资源利用率
提高系统吞吐量
可扩充性
开放性
作用
OS作为用户与计算机硬件系统之间的接口用户不用直接与硬件打交道
命令方式
系统功能调用方式
图形化接口方式
OS是计算机资源的管理者
CPU
分配和控制
存储器
内存分配和回收
设备分配与操纵
文件（数据与程序）
存取、共享和保护
OS实现了对计算机资源的抽象
抽象物理接口
抽象文件系统
抽象图形界面
2.操作系统的发展过程
发展动力
提高资源利用率
多道批处理系统
方便用户，人机交互
分时系统
计算机体系结构发展
多CPU
引入网络功能
应用需求
实时系统
发展过程
未配置操作系统的计算机系统
人工操作方式
用户独占全机
CPU等待人工操作
严重降低了计算机资源的利用率
脱机输入/输出(Off–Line I/O)方式
减少了CPU的空闲时间
提高了I/O速度
效率仍然不理想
单道批处理系统
(宏观并行，微观交替)
人机交互
共享主机
及时接收
多路卡
及时处理
时间片轮转
作业直接进入内存，没有作业调度
微机操作系统的发展
单用户单任务
DOS
单用户多任务
WINDOWS
多用户多任务
UNIX
3.操作系统的基本特性
1.并发concurrence
区别并行和并发
并发是进程宏观一起运行，微观上交替运行，而并行是指同时运行
并行是指同时运行
引入进程
进程是指在系统中能独立运行并作为资源分配的基本单位由一组机器指令，数据和堆栈等组成，是一个能独立运行的活动实体
2.共享sharing
1.互斥共享方式
2.同时访问方式
并发和共享是多用户(多任务)OS的两个最基本的特征。它们又是互为存在的条件
3.虚拟virtual
时分复用技术
虚拟处理机
虚拟设备
空分复用技术
4.异步asynchronism
进程速度不可预知
结果可重现
4.操作系统的主要功能
1.处理机管理功能
进程控制
为作业创建进程、撤销进程
进程同步
进程互斥方式
临界资源访问
进程同步方式(协同)
合作完成任务时安排进程顺序
进程通信
调度
作业调度
调入内存
建立进程
进程调度
分配CPU
2.存储器管理功能
静态分配
内存空间确定
不允许申请新空间
不允许移动
动态分配
内存保护
进程在各自内存空间运行
内存保护机制
用户程序不能访问操作系统的数据
地址映射
逻辑地址转换
内存扩充
虚拟存储技术
机制
请求调入功能
置换功能
3.设备管理功能
缓冲管理
设备分配
设备处理
设备处理程序又称设备驱动程序
4.文件管理功能
目录管理
文件的读写管理和保护
5.操作系统与用户之间的接口
用户接口
联机用户接口
键盘操作命令
命令解释程序
脱机用户接口
图形用户接口
取得操作系统服务的唯一途径
由一组系统调用组成
6.现代操作系统的新功能
系统安全
认证技术
密码技术
访问控制技术
反病毒技术
网络的功能和服务
支持多媒体
5.OS结构设计
传统操作系统结构
无结构操作系统
模块化OS
分层式结构OS
微内核os结构
客户/服务器模式
面对对象的程序设计
第二章进程的描述与控制
程序并发执行时的特征
间断性
失去封闭性
不可再现性
进程的描述
进程的定义
进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
进程的特征
动态性
并发性
独立性
异步性
进程和程序的区别
进程是动态概念，而程序则是静态概念
程序是指令的有序集合，永远存在；进程强调是程序在数据集上的一次执行，有创建有撤销，存在是暂时的；
进程具有并发性，而程序没有
进程可创建其他进程，而程序并不能形成新的程序
进程是竞争计算机资源的基本单位，程序不是
进程和程序的联系
进程是程序在数据集上的一次执行
程序是构成进程的组成部分，一个程序可对应多个进程，一个进程可包括多个程序
进程的运行目标是执行所对应的程序
从静态看，进程由程序、数据和进程控制块（PCB）组成
进程的基本状态及转换
进程的三种基本状态
就绪状态ready
进程已经获得除了CPU的所有资源
执行状态running
每个处理机只能有一个
阻塞状态block
等待IO或其他事件
创建状态和终止状态
五状态进程模型
注意
阻塞态->运行态和就绪态->阻塞态这二种状态转换不可能发生
挂起操作和进程状态的转换
移出内存
挂起操作的目的
终端用户的需要: 修改、检查进程
父进程的需要：修改、协调子进程
对换的需要：缓和内存
负荷调节的需要：保证实时任务的执行
进程管理中的数据结构
进程控制块PCB的作用
作为独立运行基本单位的标志
能实现间断性运行方式
提供进程管理所需要的信息
提供进程调度所需要的信息
实现与其他进程的同步与通信
进程控制块的信息
进程标识符
外部标识符PID
内部标识符(端口)
处理机上下文
通用寄存器
指令计数器
下一条指令地址
程序状态字PSW
用户栈指针
进程调度信息
进程状态
进程优先级
进程调度所需的其他信息
等待CPU时间
已执行时间
事件
阻塞原因
进程控制信息
程序和数据的地址
进程同步和通信机制
消息队列指针
信号量
资源清单
链接指针
下一个PCB首地址
进程控制块的组织方式
线性方式
线性表
链接方式
执行指针
就绪队列
空白队列
阻塞队列
索引方式
建立几张索引表
操作系统内核
CPU状态
系统态、内核态
硬件相关的模块
常用设备的驱动程序
运行频率较高的模块
用户态
用户程序
两大功能
支撑功能
中断管理
时钟管理
原语操作
进程的管理，由若干原语（primitive）来执行
在系统态下执行
常驻内存
资源管理功能
进程管理
存储器管理
设备管理
进程的创建
进程的层次结构
父进程
子进程
继承所有资源
句柄
引起创建进程的事件
系统内核创建
分时系统用户登录
多道批处理系统作业调度
为新作业创建进程
提供服务
用户程序要求
用户创建
应用请求
进程的创建过程
1.申请空白PCB
申请数字标识符
2.为新进程分配其运行所需的资源
内存
CPU时间
3.初始化进程块PCB
标识信息
处理机状态信息
程序计数器
栈指针
处理机控制信息
进程就绪状态
优先级
4.如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列
进程的终止
引起进程终止的事件
1.正常结束
通过指令指出
2.异常结束
越界错
保护错
非法指令
特权指令错
运行超时
等待超时
算术运算错
IO故障
3.外界干预
操作员、操作系统干预
父进程请求
父进程终止
进程的终止过程
1.根据被终止进程的标识符，检索出PCB，读出进程状态
2、如果处于执行状态，立即结束，置调度标志为真，指示应该重新被调度
3、结束子孙进程
4、归还资源
5、移出PCB
进程的阻塞与唤醒
引起进程阻塞和唤醒的事件
请求共享资源
启动某种操作而阻塞当前进程
启动IO设备
新数据尚未到达
等待另一进程
无新工作可做
网络系统进程
进程阻塞过程(自己阻塞自己，主动行为)
阻塞原语block
进程唤醒过程(系统或其他进程唤醒自己)
wakeup
进程的挂起与激活
suspend
复制PCB
active
两种形式的制约关系
间接相互制约关系
资源共享
互斥——竞争
直接相互制约关系
进程合作
同步——协作
临界资源和临界区
分区
进入区enter section
临界区critical section
退出区exit section
剩余区remainder section
同步机制应遵循的规则
1.空闲让进
2.忙则等待
3.有限等待
需要保证有限时间内进程能够获取临界资源
4.让权等待
当进程不能进入临界区时，需要及时释放CPU
进程同步机制
硬件同步机制
关中断
无进程调度
多处理机不适用
利用Test-and-Set指令实现互斥
利用swap|XCHG指令实现进程互斥
信号量机制
整型信号量
表示资源数目的整型量S
除初始化， 仅能通过原子操作P、V访问
不可中断
记录型信号量
由于整型信号量没有遵循让权等待原则，记录型允许负数，即阻塞链表
AND型信号量
Swait
信号量集
理解:记录型信号量的wait和signal仅能对信号施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时，便要进行N次wait操作，这显然是低效的，甚至会增加死锁的概率。此外，在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配前，都必须测试资源数量，判断是否大于可分配的下限值，决定是否予以分配
操作
Swait(S1，t1，d1…Sn，tn，dn)
Ssignal(S1，d1…Sn，dn)
特殊情况
应用
实现进程互斥
实现前驱关系
管程
构成
名称
局部于管程的共享数据结构说明
共享变量
条件变量
链表
对该数据结构进行操作的 过程们
对局部的管程的共享数据设置初始值的语句
特性
模块化
抽象数据类型
信息掩蔽
经典进程的同步问题
生产者–消费者问题
哲学家进餐问题
读者–写者问题
进程的同步与互斥
低级进程通信
交换信息少
进程通信的类型
共享存储器系统
基于共享数据结构的通信方式
生产者和消费者
低级通信
基于共享存储区的通信方式
高级通信
管道通信系统(pipe)
一个共享文件
连接一个读进程和一个写进程
消息传递系统
方式分类
直接通信
对称
非对称
格式
同步方式
通信链路
间接通信
共享邮箱
客服机–服务器系统
网络环境
socket
RPC
线程的基本概念
线程的引入
提高进程内的并发程度
多进程并发的不足
进程的两个基本属性
一个拥有资源的独立单位，可独立分配系统资源
一个可独立调度和分派的基本单位，PCB
程序并发执行所需付出的时空开销
创建进程
撤销进程
进程切换
进程间通信效率低
将分配资源和调度两个属性分开
线程——作为调度和分派的基本单位
进程是系统资源分配的单位，线程是处理器调度的单位
线程表示进程的一个控制点，可以执行一系列的指令。通常，和应用程序的一个函数相对应
进程分解为线程还可以有效利用多处理器和多核计算机
线程与进程的比较
不同点
调度的基本单位
代价小
拥有资源
系统开销
支持多处理机
进程只能运行在一个处理机上
相似点
状态：运行、阻塞、就绪
线程具有一定的生命期
进程可创建线程，一个线程可创建另一个子线程
多个线程并发执行时仍然存在互斥与同步
线程的实现
线程的状态和线程控制块
线程运行的三个状态
执行状态
就绪状态
阻塞状态
线程控制块TCB
线程标识符
寄存器的值
状态寄存器
运行状态
线程专有存储区
信号屏蔽
堆栈指针
自己堆栈
核心栈
多线程OS中的进程属性
进程是一个可拥有资源的基本单位
多个线程可并发执行
进程已不是可执行的实体
线程的控制
程序启动创建第一个进程，然后为此进程创建第一个线程
线程创建线程
线程的实现方式
内核支持线程KST
内核能够同时调度多个线程
线程享有时间片
切换快
调度需要内核状态
用户级线程ULT
内核不知道该线程的存在
进程享有时间片
无法利用多处理机
系统调用阻塞进程内所有线程
组合方式
第三章:处理机调度与死锁
处理机调度层次
高级调度（作业调度）
分时和实时系统无需作业调度，因为需要交互
批处理系统需要作业调度
低级调度（进程调度）
方式
非抢占
进程完成或阻塞才调度
抢占
原则
优先权原则
短作业优先原则
时间片原则
中级调度（内存调度）
将挂起的进程调入内存
将阻塞的进程调入外存
应用于分时系统和有虚拟存储器的系统
处理机调度算法的目标
处理机调度算法的共同目标
资源利用率
其中CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
公平性
防止进程饥饿
平衡性
资源平衡
策略强制执行
安全策略
批处理系统的目标
平均周转时间短
包括
作业在外存等待调度的时间
进程在内存等待调度的时间
进程在CPU上运行的时间
进程等待IO的时间
计算
平均周转时间
平均带权周转时间
周转时间与系统提供服务的时间之比
系统吞吐量高
单位时间完成的作业数目
处理机利用率高
分时系统的目标
响应时间快
提交请求到结果响应的时间
均衡性
响应时间与用户要求相对应
实时系统目标
截止时间的保证
可预测性
作业与作业调度
作业
程序、数据和一份作业说明书
系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。
作业步
每个作业都必须经过若干相对独立，有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。往往上一个作业步的输入为下一个的输入
典型
编译
链接装配
运行
作业控制块JCB
为每个作业设置一个JCB，保存了对作业管理调度的全部信息。是作业存在的标志。
作业运行的三个阶段
收容阶段
输入硬盘
建立JCB
放入作业后备队列
运行阶段
被调度选中
分配资源、建立进程
放入作业就绪队列
完成阶段
运行完成、异常终止
回收资源、JCB
输出作业结果
作业运行的三个状态
后备状态
完成状态
作业调度的主要任务
接纳多少个作业
接纳哪些作业
调度算法
先来先服务(first–come first–served，FCFS)
短作业优先(short job first，SJF)
估计运行时间
人机无法交互
可以抢占也可以非抢占
优先级调度算法(priority–scheduling algorithm，PSA)
静态优先权
动态优先权
原理
在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行
特点
如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SJF算法，有利于短作业
当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法
对于长时间的优先级，可以为随等待时间的增加而提高，当等待时间足够长时，也可获得处理机
进程调度是最基本的调度，任何操作系统都有进程调度。
进程调度的任务
保存处理机的现场信息
按某种算法选取进程
把处理器分配给进程
机制的三个基本部分
排队器
排队所有就绪队列
分派器
上下文切换器
保留当前进程上下文，装入分派程序上下文
移出分派程序上下文，装入选出的进程的上下文
进程调度方式
非抢占方式
运行完毕或无法运行
IO请求阻塞
进程通信或同步时的原语操作
抢占方式
短进程优先原则
进程调度的算法
轮转调度算法RR
基本原理
根据FIFO策略将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔(如30ms)即产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行
进程切换时机
时间片未用完，进程完成
时间片到，进程未完成
时间片大小的确定
太小利于短作业，增加系统切换开销
太长就退化为FCFS算法
一般选择: q略大于一次交互所需要的时间，使大多数进程在一个时间片内完成
一般来说，平均周转时间将比SJF长，但是有较好的响应时间
优先级调度算法
非抢占式优先级调度算法
等当前进程执行完以后，再执行另一个优先权最高的进程
这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
抢占式优先级调度算法
不等当前进程结束，直接抢处理机
常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。
优先级的类型
静态优先级
动态优先级
在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
多队列调度算法
多级反馈队列调度算法
调度机制
设置多个就绪队列
每个队列都采用FCFS算法，一个时间片没运行完下移一个优先级的队列
按照队列优先级调度
第n个队列每次时间片长度为n个单位
调度算法的性能
对于终端型用户，由于作业小，感觉满意
对于短批处理作业用户，周转时间也较小
长批处理作业用户，也能够得到执行
基于公平原则的调度算法
保证调度算法
公平分享调度算法
实时调度
实现实时调度的基本条件
提供必要信息
就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
系统处理能力强
∑(Ci/Pi)≤1
N个处理机:∑(Ci/Pi)≤N
采用抢占式调度机制
具有快速切换机制
对中断的快速响应能力
快速的任务分派能力
实时调度算法的分类
非抢占式调度算法
非抢占式轮转调度算法
非抢占式优先调度算法
抢占式调度算法
基于时钟中断的抢占式优先级调度算法
立即抢占的优先级调度算法
最早截止时间优先EDF(Earliest Deadline First)算法
根据任务的开始截至时间来确定任务的优先级
截至时间越早，优先级越高
非抢占式调度方式用于非周期实时任务
抢占式调度方式用于周期实时任务
最低松弛度优先LLF(Least Laxity First)算法
类似EDF
算法根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。
松弛度例子
例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms
优先级倒置(Priority inversion problem)
优先级倒置的形成
高优先级进程被低优先级进程延迟或阻塞。
优先级倒置的解决方法
简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占
实用的:建立在动态优先级继承基础上的
死锁
资源问题
可重用性资源
计算机外设
消耗性资源
数据，消息
可抢占性资源
CPU，内存
不引起死锁
不可抢占性资源
光驱，打印机
如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件，那么该组进程是死锁的
死锁起因
竞争不可抢占性资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
产生死锁的必要条件
互斥条件
竞争的资源为互斥
请求和保持条件
拥有资源的进程仍能申请资源
不可抢占条件
进程拥有的资源不能被抢占
循环等待条件
如果每个资源只有一个实例，则环路等待条件是死锁存在的充分必要条件
处理死锁的方法
预防死锁
静态方法，在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个条件之一，防止发生死锁。
预防死锁的策略
破坏\"请求和保存\"条件
第一种协议
所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源
优点:简单，易行，安全
缺点
资源被严重浪费，严重地恶化了资源的利用率
使进程经常会发生饥饿现象
第二种协议
它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源
破坏\"不可抢占\"条件
当一个已经保存了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请
代价比较大
破坏\"循环等待\"条件
对系统所以资源类型进行线性排序，并赋予不同的序号例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等
所有进程对资源的请求必须严格按资源序号递增的次序提出。
避免死锁
动态的方法
在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁
如银行家算法
避免死锁的策略
系统安全状态定义
系统能按某种顺序依次为每个进程分配资源，不产生死锁
这个顺序叫一个安全序列
确保系统时刻处于安全状态
利用银行家算法避免死锁
银行家算法
每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。
当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。
若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待
数据结构
可用资源向量 Available[m]：系统中现有资源数
分配矩阵 Allocation[n，m]：进程i已获得j类资源的数目
过程
某个进程发出请求
检测是否超出总需求
检测是否超出现有资源数
尝试分配，计算数据结构
验证是否为安全状态，是就分配
解题
矩阵
work[j]
完成该进程后系统各资源数目
finish[j]
已选择该进程
死锁的检测与解除
死锁的检测
资源分配图
简化
选择一个没有阻塞的非独立进程p
将p移走，包括它的所有请求边和分配边
重复步骤1，2，直至不能继续下去
死锁定理
若一系列简化以后不能使所有的进程节点都成为孤立节点
死锁检测中的数据结构
类似银行家算法
检测时机
当进程等待时检测死锁 （其缺点是系统的开销大）
定时检测
系统资源利用率下降时检测死锁
死锁的解除
抢占资源
终止(或撤销)进程
终止所有死锁进程
逐个终止进程
代价最小
考虑因素
进程的优先级的大小
进程已执行了多少时间，还需时间
进程在运行中已经使用资源的多少，还需多少资源
进程的性质是交互式还是批处理的
付出代价最小的死锁解除算法
是使用一个有效的挂起和解除机构来挂起一些死锁的进程
第四章:存储器管理
存储器的层次结构
CPU寄存器
主存
高速缓存
磁盘缓存
辅存
磁盘
可移动存储介质
可执行存储器
寄存器和主存的总称
访问速度快，进程可以在很少的时钟周期内用一条load或store指令完成存取。
程序的装入和链接
步骤
源程序 ->目标模块（Object modules）--------Compiler
由编译程序对用户源程序进行编译，形成若干个目标模块
链接
一组目标模块 ->装入模块 （Load Module）----------Linker
由链接程序将编译后形成的一组目标模板以及它们所需要的库函数链接在一起，形成一个完整的装入模块
装入
装入模块 ->内存 --------Loader
由装入程序将装入模块装入内存
程序的链接
静态链接方式(lib)
程序运行之前
要求
修改各模块的相对地址
变换外部调用符号
装入时动态链接
边装入边链接
运行时动态链接(dll)
发现一个模块没在内存中时再装入内存链接
程序的装入
绝对装入方式
单道程序环境
在编译时，知道程序将驻留在内存中指定的位置
编译程序将产生绝对地址（物理地址）的目标代码。
可重定位装入方式
在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换(一般在装入内存时由软件完成)。
优点：不需硬件支持，可以装入有限多道程序。
缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。
动态运行时的装入方式
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行
优点：
OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。
能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。
缺点：需要硬件支持——重定位寄存器，OS实现较复杂。
它是虚拟存储的基础。
分配存储管理方式
连续分配存储管理方式
单一连续分配(MS-DOS)
单用户单任务系统
固定分区分配(浪费很多空间)
每个分区一道作业
装入时查找分区
内部碎片浪费
分区方式
分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。
动态分区分配
空闲分区表
空闲分区链
动态分区分配算法
基于顺序搜索的动态分区分配算法
顺序找，找到一个大小满足的就分配，但是可能存在浪费
倾向于优先使用低地址对应的小空间
空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序
循环首次适应算法（next fit，NF）
从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。
需要设置查询指针
空闲分区分布得更均匀，查找开销小
缺乏大空闲分区
最佳适应算法（best fit，BF）
空闲分区按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
找到最合适的，但是大区域的访问次数减少，每次切割剩下的都是最小的
这种方法能使外碎片尽量小。
最坏适应算法（worst fit，WF）
选择切割最大的分区
空闲分区按大小由大到小排序
产生碎片的可能最小
基于索引搜索的动态分区分配算法
快速适应算法|分类搜索算法（quick fit）
对每一种有相同空间大小的分区再各设一张空闲分区表
记录每张表的表头
根据进程长度寻找大小最小的适合分区
从链表上取下第一块分区
伙伴系统（buddy system）
所有分区大小均为2的n次幂
多次分割、多次合并
哈希算法
分区分配操作
分配内存
选择出一个适合大小的分区，划出足够的空间装入程序
回收内存
动态可重定位分区分配
紧凑
动态重定位分区分配算法
0、与动态分区分配基本相同
1、在某个分区被释放后立即进行紧凑，系统总是只有一个连续的分区而无碎片，此法很花费机时。
2、当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧凑，这样紧缩的次数比上种方法少得多，但管理复杂
地址映射和存储保护措施
基址寄存器：程序的最小物理地址
界限寄存器：程序的逻辑地址范围
物理地址 = 逻辑地址 + 基址
离散分配方式
对换
把内存中暂时不能运行的进程、暂时不用的程序与数据换到外存
把具备运行条件的进程和需要的程序与数据换到内存
提高CPU利用率与吞吐量
方法
设立对换进程
整体对换
以进程为单位
对换空间管理
设置在高速磁盘
采用简单的连续存储
进程换入
进程换出
首先选择阻塞、睡眠的优先级最低的进程
页面（分段）对换
以页或段为单位
虚拟存储技术的基础
方案
许多进程频繁缺页且内存紧张时才发生对换
分页存储管理方式
概念
页面
将进程的逻辑地址分成若干个大小相等的区域
物理块
内存空间分成与页面相同大小的存储块
由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”
地址结构
页表
系统为每个进程建立了一张页面映像表，简称页表
进程执行时，查找该表，即可知道进程在内存中的物理（块号）位置
页表的作用是实现从页面号到物理块号的地址映射
基本的地址变换机构
为了实现地址变换功能，在系统中设置页表寄存器（PTR），用来存放页表的始址和页表的长度。
在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。
页表大都驻留在内存中
要访问两次内存
具有快表的地址变换机构
如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。
在地址变换机构中增设一组具有并行查询功能的特殊的高速缓冲存储器，称为“联想存储器”，即快表
地址变换过程为：
1、CPU给出逻辑地址
2、地址变换机构自动地将其中的页号送入高速缓存，先确定所需要的页是否在快表中。
3、若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；
4、若快表中未找到对应的页表项，则需再访问内存中的页表
5、找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项。
多级页表
这里书上说每个页表项大小为1字节，根本没说大前提
解决方法
对页表再进行分页
只将当前需要的部分页表项调入内存，其余的仍存在磁盘上
增设外层页表寄存器，存放外层页表始址
仍未减少页表占用的内存空间
没有外碎片，每个内碎片不超过页大小。
一个程序不必连续存放。
便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。
缺点：程序全部装入内存。
反置页表
为每一个物理块设置一个页表项，并按物理块编号排序，其内容则是页号和其所属进程的标识。
地址变换
利用Hash算法进行检索
分段存储管理方式
方便编程
段名+段内地址
信息共享
段共享
信息保护
方便
动态增长
适合动态链接
分段
作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。
内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定
逻辑地址结构：段号+段内地址
段表
段表寄存器
存放段表始址和长度
增加联想寄存器
和分页的区别
页是信息的物理单位
页的大小固定且由系统固定
分页的用户程序地址空间是一维的
通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。
分页是系统管理的需要，分段是用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
分段最重要的优点
段页式存储管理方式
用户程序先分段，每个段再分页
逻辑地址格式：段号（S）+段内页号（P）+页内地址（W）
图
地址变换过程
需要三次访问过程
访问段表获取页表始址
访问页表获取物理块号
访问物理块
增设高速缓冲寄存器
0 条评论
回复 删除
下一页
