操作系统是计算机系统的核心,是极其重要的组成部分,是计算机应用人员**的专业知识。同时,“操作系统”课程也成为计算机相关专业的必修课程。 本书是省级精品课程的主讲教材,由浅入深,**突出,系统地阐述了操作系统的基本概念、设计原理和实现技术; 书中在论述操作系统经典内容的基础上,介绍了操作系统的新技术以及发展趋势; 在主要章节的末尾,附有典型操作系统的案例分析。 经过多年的课程建设和经验积累,作者积累了丰富的课程资源,使得本书具有较强的可读性。本书可作为高校计算机及其相关专业的教材或参考书,也可供从事计算机相关工作的科技人员及各类自学人员参考。

第3章死锁
死锁是多道程序并发执行带来的另一个严重问题,它是操作系统乃至并发程序设计中*难处理的问题之一。进程死锁产生的根本原因有两个: 一是竞争资源; 二是进程间推进的顺序不合理。死锁处理不好将会导致整个系统运行效率下降,甚至不能正常运行。操作系统设计者必须高度重视死锁现象。死锁普遍存在,对于死锁,不存在**的、彻底的解决方案,只能在众多可行方案中选择一个折中方案。
本章主要讲解死锁的基本概念、死锁的处理策略、死锁的预防、死锁的避免以及死锁的检测和解除。本章需要**掌握:
 了解死锁的基本概念; 了解死锁的检测、死锁解除的方法;
 理解死锁的产生的原因; 理解死锁预防与死锁避免的区别;
 掌握死锁���生的4个必要条件; 掌握系统**状态及其判别方法; 掌握处理死锁的方法;
 学会银行家算法及其应用。
3.1死锁的定义和产生原因
3.1.1死锁的定义
死锁是指一组并发执行的进程彼此等待对方释放资源,而在没有得到对方占有的资源之前不释放自己所占有的资源,导致彼此都不能向前推进,称该组进程发生了死锁。
死锁产生后,若无外力干预,陷入死锁的各个进程都永远不能向前推进,导致这些进程不能正常结束。同时,要求共享使用死锁进程所占资源的其他进程,或者需要与死锁进行某种合作的其他进程也会受到牵连,也不能正常结束。*终可能导致系统瘫痪,给系统和用户带来极大损失。因此,操作系统设计者必须对死锁现象予以充分重视。
死锁问题不仅普遍存在于计算机系统中,在日常生活中也广泛存在。现实生活中交通死锁问题较为常见。例如,某交通路口恰有4辆汽车几乎同时到达,并相互交叉停了下来,如图31(a)所示。如果该路口没有采取任何交通管理措施,4辆车同时驶过十字路口,就会发生如图31(b)所示的场面。*终结果是4辆车都在等待对方车辆后退,但谁也不先让,所以都不能通过该路口,出现交通死锁现象。
图31交通阻塞导致死锁示意图
在该例中,可把每辆汽车行驶过十字路口看作一个进程,系统中共有4个这样的进程并发执行。十字路口可看作4个临界资源,如图31(a)中标注的a、b、c和d所示。每个汽车进程在过路口都要依次申请其中的两个资源。1号汽车申请a和b资源; 2号汽车申请b和c资源; 3号汽车申请c和d资源; 4号汽车申请d和a资源。出现死锁情况时,1号汽车占据a资源和申请b资源; 2号汽车占据b资源和申请c资源; 3号汽车占据c资源和申请d资源; 4号汽车占据d资源和申请a资源。此时,若不采取外力措施干预,如交通警察未赶到现场进行疏导管理,4辆汽车将永远互相等待。在死锁解除前,如果此后还有其他汽车想通过该十字路口,由于4个路口资源都已经分配,故也不能通过,因此造成更多进程阻塞。
在计算机系统中,凡是涉及临界资源(即互斥资源)申请的并发进程间都可能发生死锁。举一个计算机系统中的简单实例,如某系统中有P1和P2两个进程并发执行,P1和P2两个进程在执行过程中都需要使用一台打印机和一台CDROM驱动器。该系统中只有一台打印机和一台CDROM驱动器,两者均为临界资源。假设进程P1和P2的执行过程如图32所示。
图32两个并发进程的执行情况图
当进程P1申请打印机成功时,恰巧此时进程发生切换,调度程序选中P2执行,P1暂时变为就绪态等待调度程序调度。进程P2首先申请CDROM驱动器,此时该设备处于空闲状态,故系统把它分配给进程P2。这时,P1和P2两个进程都不能向前继续推进。进程P1申请CDROM驱动器,但CDROM驱动器已被P2占用,只能被阻塞,等待进程P2使用完毕后,释放CDROM驱动器给它; 进程P2向前推进时,申请打印机,但打印机此时被进程P1占用,P2也只好阻塞,等待进程P1使用完毕后释放。因此P1和P2两个进程都陷入了相互等待的状态,形成了死锁。
通过上面介绍的例子可以发现,死锁具有以下特点。
(1) 陷入死锁的进程是系统并发进程中的一部分,且至少要有两个进程,单个进程不会形成死锁。
(2) 陷入死锁的进程彼此都在等待对方释放资源,形成一个循环等待链。
(3) 死锁形成后,在没有外力干预时,陷入死锁的进程不能自己解除死锁,死锁进程无法正常结束。
(4) 如不及时解除死锁,死锁进程占有的资源不能被其他进程所使用,导致系统中更多进程阻塞,造成资源利用率下降。
3.1.2死锁产生的原因
产生死锁的原因可归结为两点。
(1) 竞争资源。当系统中供多个进程所共享的资源不足以同时满足它们的需要时,引起它们对资源的竞争而产生死锁。
(2) 进程推进顺序不当。进程在运行过程中,请求和释放资源的顺序不当,导致了进程死锁。
1. 竞争资源
死锁产生的根本原因是资源竞争且分配不当。因为多道程序并发执行,造成多个进程在执行过程中所需要的资源数远远大于系统能提供的资源数。如图32所示例子中的进程P1和P2两个进程之所以产生死锁,就是因为系统中的打印机和CDROM驱动器不够用,如果为了防止死锁而配置多台打印机和CDROM驱动器,从成本角度看是不现实的。由于各个进程对资源的需求量是动态变化的,虽然有多个并发执行的进程,但某个时刻它们对打印机提出的请求可能只有一个,甚至没有,系统配置多台打印机就造成了资源的浪费。
计算机系统中有很多资源,按照占用方式来分,可分为可剥夺资源与不可剥夺资源。
(1) 可剥夺资源。某进程在获得这类资源后,即使该进程没有使用完,该类资源也可以被其他进程剥夺使用。例如,优先级高的进程可以抢占优先级低的进程的处理器; 如可把一个进程从一个存储区转移到另一个存储区,在主存紧张时,还可将一个进程从主存调出到辅存上,即剥夺该进程在主存的空间。可见,CPU、主存和磁盘均属于可剥夺资源,竞争可剥夺资源不可能出现死锁。
(2) 不可剥夺资源。当系统把这类资源分配给某进程后,不能强行收回,只能在进程使用完后自行释放,然后其他进程才能使用。例如,当一个进程已开始刻录光盘时,如果突然将刻录机分配给另一个进程,其结果必然会损坏正在刻录的光盘,因此只能等刻录好光盘后由进程自身释放刻录机。另外,打印机、刻录机和CDROM驱动器等都属于不可剥夺资源。
2. 进程推进的顺序不当
并发执行的进程在运行中存在异步性,彼此之间相对执行速度不定,存在着多种推进顺序。并发进程间推进顺序不当时会引起死锁。
为了更好地描述进程P1和进程P2的推进顺序,图33给出了两者的推进顺序示意图。横轴表示进程P1的执行进展,纵轴表示进程P2的执行进展,R1和R2表示资源。从原点出发的不同路径分别表示两个进程以不同的速度向前推进。图中给出了4种不同的执行路径,表示4种不同的进程间推进顺序。
……

目录
引言
第1章操作系统引论
1.1操作系统概念
1.2操作系统的形成与发展历程
1.2.1计算机硬件发展简要介绍
1.2.2计算机操作系统的发展
1.3操作系统的功能
1.4操作系统的特征和作用
1.4.1操作系统的特征
1.4.2操作系统的作用
1.5操作系统体系结构
1.5.1单体内核结构
1.5.2层次结构
1.5.3微内核结构
1.6现代典型操作系统
1.6.1Windows
1.6.2UNIX
1.6.3Linux
1.6.4Android
1.6.5Mac OS
1.6.6iOS
1.7本章小结
习题1
第2章进程管理
2.1程序的顺序执行和并发执行
2.1.1程序的顺序执行
2.1.2程序的并发执行
2.2进程的概念
2.2.1进程的定义
2.2.2进程的基本状态和转换
2.2.3进程控制块
2.2.4进程队列
2.2.5线程
2.3进程控制
2.3.1进程创建
2.3.2进程撤销
2.3.3进程阻塞与唤醒
2.3.4进程挂起与激活
2.4进程互斥
2.4.1与时间有关的错误
2.4.2临界区
2.4.3进程的互斥
2.5进程同步
2.5.1进程的同步
2.5.2用PV操作实现进程的同步
2.5.3时间同步问题
2.6经典进程问题
2.6.1生产者消费者问题
2.6.2读者写者问题
2.7管程*
2.8进程通信
2.8.1进程通信的类型
2.8.2直接通信
2.8.3间接通信
2.9Linux进程管理机制
2.9.1进程的数据结构
2.9.2进程和线程
2.10本章小结
习题2
第3章死锁
3.1死锁的定义和产生原因
3.1.1死锁的定义
3.1.2死锁产生的原因
3.2产生死锁的必要条件
3.3死锁的处理方法
3.4死锁的预防
3.4.1破坏“请求”条件和“保持”条件
3.4.2破坏“不剥夺”条件
3.4.3破坏“循环等待”条件
3.5死锁的避免
3.5.1系统**状态
3.5.2银行家算法
3.6死锁的检测
3.6.1资源分配图
3.6.2死锁定理
3.6.3死锁检测算法
3.7死锁的解除
3.8死锁的综合处理策略
3.9线程死锁
3.10本章小结
习题3
第4章中断与处理机调度
4.1中断概述
4.1.1中断的概念
4.1.2中断优先级和中断屏蔽
4.1.3中断的处理过程
4.2三级调度体系
4.2.1低级调度
4.2.2中级调度
4.2.3**调度
4.2.4三级调度关系
4.3进程调度目标和调度方式
4.3.1进程调度目标
4.3.2进程调度方式
4.4调度算法的评价准则
4.4.1面向用户的评价准则
4.4.2面向系统的评价准则
4.5进程调度算法
4.5.1先来先服务调度算法
4.5.2短进程优先调度算法
4.5.3*短剩余时间优先调度算法
4.5.4时间片轮转调度算法
4.5.5优先级调度算法
4.5.6多级反馈队列调度算法
4.6线程的调度
4.6.1用户级线程调度
4.6.2核心级线程调度
4.7Linux进程的调度
4.7.1进程调度的数据结构
4.7.2进程调度的时机
4.7.3进程调度的策略
4.7.4Linux常用调度命令
4.8本章小结
习题4
第5章存储管理
5.1存储管理概述
5.1.1存储器的存储结构
5.1.2存储管理的功能
5.2程序的装入与链接
5.2.1物理地址和逻辑地址
5.2.2程序的装入
5.2.3程序的链接
5.3连续存储管理
5.3.1单一连续存储管理
5.3.2固定分区存储管理
5.3.3可变分区存储管理
5.3.4覆盖与交换技术
5.4页式存储管理
5.4.1基本原理
5.4.2存储空间的分配与去配
5.4.3页表与地址转换
5.4.4快表
5.4.5页的共享与保护
5.5段式存储管理
5.5.1基本原理
5.5.2空间的分配与去配
5.5.3地址转换与存储保护
5.5.4段的共享
5.5.5分页和分段存储管理的主要区别
5.6段页式存储管理
5.7虚拟存储管理方式
5.7.1虚拟存储器
5.7.2请求分页式存储管理
5.7.3请求分段式存储管理
5.8Linux存储管理
5.8.1Linux的请求分页存储管理
5.8.2Linux的多级页表
5.8.3Linux主存页的缺页中断
5.8.4Linux主存空间的分配与回收
5.8.5Linux的页面交换机制
5.9本章小结
习题5
第6章设备管理
6.1设备管理概述
6.2I/O系统
6.2.1I/O系统结构
6.2.2I/O控制方式
6.3缓冲技术
6.3.1缓冲的引入
6.3.2单缓冲
6.3.3双缓冲
6.3.4多缓冲
6.3.5缓冲池
6.4独占设备的分配
6.4.1设备的逻辑号和**号
6.4.2设备的独立性
6.4.3独占设备的分配
6.5磁盘管理
6.5.1磁盘结构
6.5.2磁盘空间的管理
6.5.3驱动调度
6.5.4提高磁盘I/O速度的方法
6.6设备处理
6.6.1设备驱动程序的处理过程
6.6.2设备的中断处理
6.7虚拟设备
6.7.1脱机外围设备操作
6.7.2联机同时外围设备操作
6.7.3SPOOLing应用例子
6.8Linux设备管理
6.8.1Linux设备管理概述
6.8.2Linux磁盘I/O调度算法
6.9本章小结
习题6
第7章文件管理
7.1文件管理概述
7.1.1文件和文件系统
7.1.2文件的分类
7.1.3文件系统的功能
7.1.4文件系统的层次结构
7.2文件的组织结构和存取方式
7.2.1文件的存储介质
7.2.2文件的存取方式
7.2.3文件的逻辑结构
7.2.4文件的物理结构
7.2.5记录的成组和分解
7.3目录管理
7.3.1文件目录
7.3.2文件目录结构
7.4辅存空间的管理
7.4.1空闲块表法
7.4.2空闲块链法
7.4.3位示图法
7.4.4成组链接法
7.5文件的使用
7.5.1主存打开文件表
7.5.2文件基本操作
7.5.3文件访问过程
7.6文件的共享
7.6.1目录链接法
7.6.2索引结点链接法
7.6.3符号链接法
7.7文件的保护与保密
7.7.1存取控制
7.7.2容错技术
7.7.3数据转储
7.8Linux文件系统
7.8.1Linux中常见文件系统格式
7.8.2虚拟文件系统
7.8.3EXT2文件系统
7.8.4日志文件系统
7.9本章小结
习题7
第8章作业管理与用户接口
8.1作业管理概述
8.2批处理作业的管理
8.2.1批处理作业输入
8.2.2批处理作业调度
8.2.3批处理作业控制
8.3批处理作业调度算法
8.3.1单道批处理作业调度算法
8.3.2多道批处理作业调度算法
8.4交互式作业的管理
8.4.1交互式作业的控制
8.4.2交互式作业的管理
8.5操作系统与用户的接口
8.5.1命令接口
8.5.2程序接口
8.5.3图形接口
8.6Linux系统接口
8.6.1Linux命令接口
8.6.2Linux程序接口
8.7本章小结
习题8
参考文献