新書推薦：
《
课长，这不是恋爱，这就是性骚扰！
》
售價：NT$
208.0
《
人文与社会译丛：我们中的我（承认理论研究）
》
售價：NT$
359.0
《
（守望者·人间世）自我：与齐格蒙特·鲍曼对谈
》
售價：NT$
374.0
《
白蛇：浮生艺术画集
》
售價：NT$
874.0
《
没有一种人生是完美的：百岁老人季羡林的人生智慧（读完季羡林，我再也不内耗了）
》
售價：NT$
257.0
《
日耳曼通识译丛：复原力：心理抗逆力
》
售價：NT$
155.0
《
海外中国研究·未竟之业：近代中国的言行表率
》
售價：NT$
614.0
《
算法经济 ： 商业逻辑与人类生活的智能演进（生动呈现AI与算法的创新应用与商业价值）
》
售價：NT$
359.0
|
| 編輯推薦： |
|
1. 以问题为导向，以学生为中心为指导思想，突出学生应用知识思考和解决问题的能力是本教材的主线。通过典型例题解析启发学生的思维，加深对理论知识的理解。自测题全面且具代表性，对于重点、难点的问题既给出了解答又有解题分析。2. 通过自测题让学生独立思考，了解自己对知识的掌握程度，也可作为考研等的复习资料。实验内容包括：高响应比作业调度、时间片轮转进程调度、进程同步与互斥、 内存分配与回收、FIFO页面置换算法、LRU页面置换算法、独占设备分配与回收、银行家算法，共8个实验。每个实验首先给出了明确的实验目标和实验内容，然后讲明实验原理并给出相应的知识点提示，*后给出参考程序和运行效果图。通过这些典型实验让学生对理论问题有更直观的认识和体验，激发他们学习的兴趣和创新的动力。
|
| 內容簡介： |
本书根据作者多年的实际教学经验，在内容选择、理论深度等方面进行了深入的分析和研讨，使学生易于理解，注重对学生的启发。在本书编写过程中，力求做到准确性、系统性、通俗性、实用性，结构清晰，注重基础理论的阐述，强调理论与实践的结合。每一章的内容从一个问题开始，让学生带着问题开始知识的学习，促进学生的思考和参与。
全书共分为9章，主要内容包括： 操作系统引论、进程与线程、进程并发控制、内存管理、页式和段式内存管理、IO管理、文件管理、死锁、多处理机系统介绍。
本书可作为高等院校计算机相关专业的教材，也可供从事计算机工作的科技人员进行参考，对报考研究生的学生也具有一定的参考价值。
|
| 目錄：
|
目录
第1章操作系统引论
1.1计算机系统与操作系统
1.1.1计算机系统的组成
1.1.2OS在计算机系统中的位置
1.2什么是操作系统
1.2.1作为用户与计算机的接口
1.2.2作为系统资源的管理者
1.3操作系统的历史
1.3.1穿孔卡片
1.3.2简单批处理系统
1.3.3多道批处理系统
1.3.4分时系统
1.3.5实时系统
1.4操作系统的类型
1.4.1大型计算机操作系统
1.4.2服务器操作系统
1.4.3个人计算机操作系统
1.4.4多处理机操作系统
1.4.5移动设备操作系统
1.4.6嵌入式操作系统
1.4.7智能卡操作系统
1.5操作系统的功能和特征
1.5.1操作系统的功能
1.5.2操作系统的特征
1.6操作系统体系结构
1.6.1单体结构
1.6.2层次式结构
1.6.3虚拟机结构
1.6.4CS结构
1.6.5微内核架构
小结
第2章进程与线程
2.0问题导入
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.3.5多核和多线程
2.4处理器调度
2.4.1调度的功能与时机
2.4.2调度算法的目标
2.4.3批处理作业调度
2.4.4交互系统进程调度
2.4.5实时系统进程调度
2.4.6线程调度
小结
第3章进程并发控制
3.0问题导入
3.1并发概述
3.1.1并发的概念
3.1.2时序错误
3.1.3临界区
3.1.4进程的互斥
3.2PV操作
3.2.1信号量与PV操作
3.2.2用PV操作实现进程互斥
3.3进程同步
3.3.1同步的概念
3.3.2PV操作实现进程同步
3.3.3生产者消费者问题
3.3.4读者写者问题
3.3.5时间同步问题
3.4管程
3.4.1什么是管程
3.4.2使用信号量的管程
3.4.3使用通知和广播的管程
3.4.4用管程解决哲学家进餐问题
3.5进程间消息传递
3.5.1消息传递的类型
3.5.2直接传递
3.5.3间接传递
3.5.4消息格式
3.5.5解决生产者消费者问题
小结
第4章内存管理
4.0问题导入
4.1内存管理概述
4.1.1存储结构
4.1.2内存管理的目标
4.1.3操作系统在内存中的位置
4.1.4虚拟内存的概念
4.2内存管理的基础
4.2.1重定位
4.2.2保护与共享
4.2.3逻辑组织
4.2.4物理组织
4.3单道编程中的内存管理
4.4多道编程中的内存管理
4.4.1固定分区的多道编程内存管理
4.4.2地址翻译的方法
4.4.3动态地址翻译的优点
4.4.4非固定分区的内存管理
4.4.5交换
4.4.6重叠
4.4.7双基址
4.5空闲空间管理
小结
第5章页式和段式内存管理
5.0问题导入
5.1页式内存管理
5.1.1基本原理
5.1.2分页内存管理
5.1.3分页系统的优缺点
5.1.4快表
5.1.5页共享与保护
5.1.6内存抖动
5.2页面更新算法
5.2.1页面交换机制
5.2.2最优更新算法
5.2.3先进先出更新算法
5.2.4最近最久未使用更新算法
5.3段式内存管理
5.3.1基本原理
5.3.2分段内存管理
5.3.3段的共享与保护
5.3.4分页与分段管理的主要区别
5.3.5段页式内存管理
5.4虚拟内存
5.4.1虚拟内存
5.4.2请求分页式内存管理
5.4.3请求分段式内存管理
小结
第6章IO管理
6.0问题导入
6.1IO管理概述
6.2IO系统
6.2.1IO系统结构
6.2.2IO控制方式
6.3IO缓冲
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.6虚拟设备
6.6.1脱机外围设备操作
6.6.2联机外围设备操作
6.6.3SPOOLing技术应用
6.7磁盘管理
6.7.1磁盘结构与性能参数
6.7.2磁盘空间的管理
6.7.3磁盘调度策略
6.7.4RAID技术
6.8磁盘高速缓存
6.8.1设计考虑因素
6.8.2性能考虑因素
6.9磁盘讨论
6.9.1固态盘
6.9.2智能磁盘系统
小结
第7章文件管理
7.0问题导入
7.1文件管理概述
7.1.1文件和文件系统
7.1.2文件的分类和结构
7.1.3文件系统的功能
7.2文件组织和存取
7.3目录管理
7.3.1内容结构
7.3.2命名
7.4文件共享与安全
7.4.1访问权限
7.4.2同时访问
7.4.3文件安全
7.5辅存空间管理
7.5.1文件分配
7.5.2空闲空间管理
7.6文件的使用
小结
第8章死锁
8.0问题导入
8.1死锁原理
8.1.1资源分类
8.1.2资源分配图
8.1.3死锁的必要条件
8.2死锁检测
8.2.1死锁检测算法
8.2.2从死锁中恢复
8.3死锁避免
8.3.1安全状态与不安全状态
8.3.2银行家算法
8.4死锁预防
8.4.1破坏互斥
8.4.2破坏占有且等待
8.4.3破坏不可抢占
8.4.4破坏环路等待
8.5活锁与饥饿
小结
第9章多处理机系统介绍
9.0问题导入
9.1多处理机基本概念
9.1.1多处理器结构
9.1.2超线程结构
9.1.3多核结构
9.1.4多核超线程结构
9.2多处理机内存结构
9.2.1UMA结构
9.2.2NUMA结构
9.2.3COMA结构
9.2.4NORMA结构
9.3多处理机操作系统类型
9.4多处理器之间的通信
9.5多处理机同步
9.6多处理机调度
9.7多处理器、超线程和多核的比较
小结
参考文献
|
| 內容試閱：
|
前言
操作系统是计算机系统的重要组成部分，是用户使用计算机的基础。作为计算机专业的核心课程，不但高等学校计算机相关专业的学生必须学习，从事计算机行业的人员也需要深入了解。但是很多学生在学习的过程中都觉得操作系统这门课程比较抽象、枯燥，难以理解，只能采取死记硬背的方式来通过考试。故此，为了帮助学生更好地学习和透彻理解计算机系统的运行过程和操作系统的基本原理，一种适用的操作系统教材显得十分重要。作者在多年的教学实践和科学研究的基础上，结合操作系统教学大纲、研究生入学考试要求和全国计算机技术与软件专业技术资格考试大纲，在参考了国内外出版的众多操作系统教材的基础上编写了本书。1. 编写背景国家中长期教育改革和发展规划纲要20102020指出： 注重学思结合。倡导启发式、探究式、讨论式、参与式教学，帮助学生学会学习。激发学生的好奇心，培养学生的兴趣爱好，营造独立思考、自由探索、勇于创新的良好环境。适应经济社会发展和科技进步的要求，推进课程改革，加强教材建设，建立健全教材质量监管制度。本教材就是按照构建创新型、应用型人才培养模式的要求，突出对学生实践应用能力的培养，适应社会需求。从问题开始，按照提出问题分析问题明确目标学习知识解决问题总结提高的思路进行内容组织。激发学生学习的主动性，提高学生的思考能力和创新应用能力。2. 本书内容全书共分为9章，主要内容如下。第1章操作系统引论： 包括计算机系统与操作系统； 操作系统的概念； 操作系统的历史、类型、功能和特性； 操作系统体系结构。第2章进程与线程： 包括进程的概念、进程控制、线程、处理器调度。第3章进程并发控制： 包括并发概述、PV操作、进程同步、管程、进程间消息传递。第4章内存管理： 包括内存管理概述、内存管理的基础、单道编程中的内存管理、多道编程中的内存管理、空闲空间管理。第5章页式和段式内存管理： 包括页式内存管理、页面更新算法、段式内存管理、虚拟内存。第6章IO管理： 包括IO管理概述、IO系统、IO缓冲、独占设备的分配、设备处理、虚拟设备、磁盘管理、磁盘高速缓存、固态盘和智能磁盘讨论。第7章文件管理： 包括文件管理概述、文件组织和存取、目录管理、文件共享与安全、辅存空间管理。第8章死锁： 包括死锁原理、死锁检测、死锁避免、死锁预防、活锁与饥饿。第9章多处理机系统介绍： 包括多处理机基本概念； 多处理机内存结构； 多处理机操作系统类型； 多处理器之间的通信； 多处理机同步； 多处理机调度； 多处理器； 超线程和多核的比较。3. 本书特色（1） 充分研讨，适合教学。根据作者多年的实际教学经验，本书在内容选择、理论深度等方面进行了深入的分析和研讨，使本书易于学生理解，尽量满足高等院校学生的学习需要。（2） 由浅入深，通俗易懂。知识点的讲解尽量用简洁、形象的语言来表达，避免过于冗长和烦琐的表述。（3） 问题导入，以问开始。每一章的内容从一个问题开始，让学生带着问题开始知识的学习，促进学生的思考和参与，在知识的理解中去解开对问题的疑惑。（4） 结构清晰，注重基础。整体知识结构清晰明了，突出对基础理论的阐述，注重对学生的启发，使学生洞彻问题的核心。强调理论与实践的结合，让学生在实际问题的探讨中充满对操作系统理论的神往。（5） 配套完善，满足教学。提供对应的PPT课件，配套出版的《操作系统原理习题与实验指导》一书中包括： 例题解析、课后自测题、自测题答案及分析、实验指导。满足课堂教学、课后练习、课后自测、上机实验的一体化需要。本书第3、4章由于世东编写，第1、5章由张丽娜编写，第2、8章由董丽薇编写，第6、7章由穆宝良编写，第9章由于杨编写。高源副教授审阅了全稿并提出了许多有益的意见； 沈阳工业大学牛连强教授在本书编写过程中给予了指点和帮助，在此谨向他们表示衷心的感谢。感谢清华大学出版社在本书的出版过程中给予的支持。由于作者学识浅陋，见闻不广，书中必有不足之处，敬请读者提出批评、指正和建议。我们的Email地址是： ysd0510@sina.com，也欢迎大家与我们进行交流和探讨。编者2016年11月
第3章进程并发控制
多道程序设计技术大大提高了系统的资源利用率，但是使多个程序能正确地并发执行是相当困难的。并发是所有问题的基础，也是操作系统设计的基础。并发包括很多设计问题，其中有进程间通信、资源共享与竞争如内存、文件、IO访问、多个进程活动的同步以及分配给进程的处理器时间等。在本章我们将会看到这些问题不仅会出现在多处理器环境和分布式处理器环境中，也会出现在单处理器的多道程序设计系统中。3.0问 题 导 入当多个进程并发执行时，可能会同时访问一些共享资源，此时如何保证对共享资源的访问是正确有效的呢？例如，有多个售票点同时出售飞机票，如何设计一个正确的并发程序，使得同一航班的同一张票不被出售给多人呢？3.1并 发 概 述3.1.1并发的概念
我们把系统中可并发执行的进程称为并发进程，并发进程相互之间可能是无关的，也可能是有联系的。如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况不相关，即它们是各自独立的，则说这些并发进程相互之间是无关的。显然，无关的并发进程一定没有共享的变量，它们分别在各自的数据集合上操作。例如，为两个不同源程序进行编译的两个进程可以是并发执行的，但它们之间却是无关的。因为这两个进程分别在不同的数据集合上为不同的源程序进行编译，虽然这两个进程可交叉地占用处理器为各自的源程序进行编译，但是，任何一个进程都不依赖另一个进程。甚至当一个进程发现被编译的源程序有错误时，也不会影响另一个进程继续对自己的源程序进行编译，它们是各自独立的。然而，如果一个进程的执行依赖其他进程的进展情况，或者说一个进程的执行可能影响其他进程的执行结果，则说这些并发进程相互之间是有交往的、是有关的。例如，有三个进程，即读进程、处理进程和打印进程。其中，读进程每次启动外围设备读一批信息并把读入的信息存放到缓冲区，处理进程对存放在缓冲区中的信息加工处理，打印进程把加工处理后的信息打印输出。这三个进程中的每一个进程的执行都依赖另一个进程的进展情况： 只有当读进程把一批信息读入并存入缓冲区后，处理进程才能对它进行加工处理，而打印进程要等信息加工处理好后才能把它输出； 也只有当缓冲区中的信息被打印进程取走后，读进程才能把读入的第二批信息再存入缓冲区供加工处理； 如此循环，直至所有的信息都被处理且打印输出。可见，这三个进程相互依赖、相互合作，它们是一组有联系的并发进程。有联系的并发进程一定共享某些资源。在上例中从外围设备上读入的信息、经加工处理后的信息、存放信息的缓冲区等都是这组并发进程的共享资源。3.1.2时序错误一个进程运行时由于自身或外界的原因而可能被中断，且断点是不固定的。一个进程被中断后，哪个进程可以运行，被中断的进程什么时候再去占用处理器，这都是与进程调度算法有关的。所以，进程执行的速度不能由自己来控制，对于有联系的并发进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束另一个进程就已开始使用，形成交替使用共享资源的现象。如果对这种情况不加控制，就可能出现与时间有关的错误，在共享资源变量时就会出错，并得到不正确的结果。请观察下面的例子。例31飞机售票问题。假设一个飞机订票系统有两个终端，分别运行进程T1和T2。该系统公共数据区中的一些单元Bjj=1,2,分别存放某日某次航班机票的余数，而d1和d2表示进程T1和T2执行时所用的工作单元。飞机售票程序如下。
procedure Ti i = 1, 2
di ： integer ;
begin
［根据旅客订票要求找到Bj］ ;
di ∶= Bj ;
if di = 1 then begin
di ∶= di - 1 ;
Bj ∶= di ;
［打印一张票］
end;
else ［提示信息"票已售完"］
end ;
由于T1和T2是两个可同时执行的并发进程，它们在同一个计算机系统中运行，共享同一批票源数据，因此，可能出现如下所示的运行情况设Bj = m。
T1 ： d1 ∶= Bj ;即d1 = m m 0
T2 ： d2 ∶= Bj ;即d2 = m
T2 ： d2 ∶= d2 - 1 ;
Bj ∶= d2 ; ［打印一张票 ］ ;即Bj = m-1
T1 ： d1 ∶= d1 - 1 ;
Bj ∶= d1 ; ［打印一张票 ］ ;即Bj = m-1
显然，此时出现了把同一张票卖给了两个旅客的情况，两个旅客都买到一张同天同次航班的机票，可是，Bj的值实际上只减去了1，造成余票数的不正确。特别是当某次航班只有一张余票时，就可能把这一张票同时售给两位旅客，这是不允许的。例32主存管理问题。假定有两个并发进程Borrow和Return分别负责申请和归还主存资源，在算法描述中，x表示现有空闲主存总量，B表示申请或归还的主存量。并发进程算法描述如下。
x ： integer;
x ∶= 1000;
cobegin
procedure Borrow B ： integer
begin
if B x then ［进程进入等待队列，等待主存资源］;
x ∶= x - B;
［修改主存分配表，进程获得主存资源］;
end;
procedure Return B ： integer
begin
x ∶= x B;
［修改主存分配表］;
［释放等待主存资源的进程］;
end;
coend;
由于Borrow和Return共享了表示主存物理资源的临界变量x，若对并发执行不加限制会导致错误。例如，一个进程调用Borrow申请主存，在执行了比较B和x的指令后，发现B x，但在执行进程进入等待队列，等待主存资源前另一个进程调用Return抢先执行，归还了所借全部主存资源。这时，由于申请进程还未成为等待状态，Return中的释放等待主存资源的进程相当于空操作。以后当调用Borrow的进程被置成等待主存资源时，可能已经没有其他进程来归还主存资源了，从而，申请资源的进程处于永远等待状态。例33自动计算问题。某交通路口设置了一个自动计数系统，该系统由观察者Observer进程和报告者Reporter进程组成。观察者进程能识别汽车，并对通过的汽车计数，报告者进程定时可设为每隔一小时将观察者的计数值打印输出，每次打印后把计数值清0。两个进程的并发执行可完成对每小时汽车流量的统计，这两个进程的算法描述如下。
count ： integer;
count ∶= 0;
cobegin
procedure Observer
begin
L1 ： ［ observe a car ］;
count ∶= count 1;
goto L1;
end;
procedure Reporter
begin
print count;
count ∶= 0;
end;
coend;
进程Observer和Reporter并发执行时可能有如下两种情况。1 报告者进程执行时无汽车通过。在这种情况下，报告者进程把上一小时通过的汽车数打印输出后将计数器清0，完成了一次自己承担的任务。此后，有汽车通过时，观察者进程重新开始对一个新时间段内的流量进行统计。在两个进程的配合下，能正确统计出每小时通过的汽车数量。2 报告者进程执行时有汽车通过。当准点时，报告者进程工作，它启动了打印机，在等待打印机打印输出时恰好有一辆卡车通过，这时，观察者进程占用处理器，把计数器count的值又增加了1。之后，报告者进程在打印输出后继续执行count：＝0。于是，报告者进程在把已打印的count值清0时，同时把观察者进程在count上新增加的1也清除了。如果在报告者打印期间连续有车辆通过，虽然观察者都把它们记录到计数器中，但都因报告者执行count ∶= 0而把计数值丢失了，使统计结果严重失实。从以上例子可以看出，由于并发进程执行的随机性，一个进程对另一个进程的影响是不可预测的。由于它们共享了资源变量，当在不同时刻交替访问资源变量时就可能造成结果的不正确。造成不正确的因素与进程占用处理器的时间、执行的速度以及外界的影响有关。这些因素都与时间有关，所以把它们统称为时序错误。3.1.3临界区有联系的并发进程执行时出现与时间有关的错误，其根本原因是对共享资源变量的使用不加限制，当进程交叉使用了共享资源变量时就可能造成错误。为了使并发进程能正确地执行，必须对共享变量的使用加以限制。我们把并发进程中与共享变量有关的程序段称为临界区，共享变量所代表的资源称为临界资源，多个并发进程中涉及相同共享变量的那些程序段称为相关临界区。例如，在飞机售票系统中，进程T1的临界区为：
d1 ∶= Bj ;
if d1 = 1 then begin
d1 ∶= d1 - 1;
Bj ∶= d1;
［打印一张票］
end;
else ［ 提示信息"票已售完"］
进程T2的临界区为：
d2 ∶= Bj;
if d2 = 1 then begin
d2 ∶= d2 - 1;
Bj ∶= d2;
［打印一张票］;
end;
else ［提示信息"票已售完"］;
这两个临界区都要使用共享变量Bj，故属于相关临界区。而在自动计数系统中，观察者进程的临界区是：
count ∶= count 1;
报告者进程的临界区是：
print count;
count∶= 0;
这两个临界区都要使用共享变量count，也属于相关区。如果有进程在相关临界区执行时，不让另一个进程进入相关的临界区执行，就不会形成多个进程对相同共享变量的交叉访问，于是就可避免出现与时间有关的错误。例如，观察者和报告者并发执行时，当报告者启动打印机后，在执行count∶= 0之前，虽然观察者发现有汽车通过，应该限制它进入相关临界区即暂不执行count∶= count1，直到报告者执行了count∶= 0退出临界区。当报告者退出临界区后，观察者再进入临界区执行，这样就不会交替地修改count值，而观察到的汽车数被统计在下一个时间段内，也不会出现数据丢失。可见，只要对涉及共享变量的临界区互斥执行，就不会出现与时间有关的错误。因而，对若干进程共享某一资源变量的相关临界区的管理应满足如下三个要求。1 一次最多让一个进程在临界区执行，当有进程在临界区执行时，其他想进入临界区执行的进程必须等待。2 任何一个进入临界区执行的进程必须在有限的时间内退出临界区，即任何一个进程都不应该无限地逗留在自己的临界区中。3 不能强迫一个进程无限地等待进入它的临界区，即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区。3.1.4进程的互斥进程的互斥是指当有若干进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用，其他要使用该资源的进程必须等待，直到占用资源者释放该资源。实际上，共享资源的互斥使用就是限定并发进程互斥地进入相关临界区。如果能提供一种方法来实现对相关临界区的管理，则就可实现进程的互斥。实现对相关临界区管理的方法有多种，如可采用标志方式、上锁开锁方式、PV操作方式和管程方式等。在这里，先介绍几种硬件实现互斥的方案。在这些方案中，当一个进程在临界区中更新共享资源时，其他进程将不会进入其临界区，从而保证程序的正确执行。1. 中断禁用在单处理器机器中，并发进程不能重叠执行，只能交替执行。此外，一个进程将一直运行，直到它调用了一个系统服务或被中断。因此为保证互斥，只需要保证一个进程不被中断就可以了，这种能力可以通过系统内核为启用和禁用中断定义的原语来提供。一个进程可以通过下面的方法实施互斥。
while true {
* 禁用中断 *;
* 临界区 *;
* 启用中断 *;
* 其余部分*;
}
由于临界区不能被中断，故可以保证互斥，但是，该方法的代价非常高，由于处理器被限制于只能交替执行程序，因此执行的效率将会有明显的降低。另一个问题是该方法不能用于多处理器结构中，当一个计算机系统包括多个处理器时，就有可能有一个以上的进程同时执行，在这种情况下，禁用中断是不能保证互斥的。2. 其他处理方法在多处理器配置中，几个处理器共享内存。在这种情况下，不存在主从关系，处理器间的行为是无关的，表现出一种对等关系，处理器之间没有支持互斥的中断机制。在硬件级别上，对存储单元的访问排斥对相同单元的其他访问。基于这一点，处理器的设计者提出了一些机器指令，用于保证两个动作的原子性，如在一个取指令周期中对一个存储器单元的读和写是否唯一。在该指令执行的过程中，任何其他指令访问内存将被阻止，而且这些动作在一个指令周期中完成。本节给出了两种最常见的指令： 比较和交换指令、exchange指令。1 比较和交换指令比较和交换指令定义如下。
int compare_and_swap int *word, int testval, int newval
{
int oldval;
oldval = *word
if oldval == testval *word = newval;
return oldval;
}
该指令的一个版本是用一个测试值testval检查一个内存单元*word。如果该内存单元的当前值是testval，就用newval取代该值； 否则保持不变。该指令总是返回旧内存值，因此，如果返回值与测试值相同，则表示该内存单元已被更新。由此可见这个原子指令由两部分组成： 比较内存单元值和测试值； 如果值相同，则产生交换Swap，整个比较和交换功能按原子操作执行，即它不接受中断。该指令的另一个版本返回一个布尔Boolean值： 交换发生时为真True； 否则为假False。几乎所有处理器家族x86、IA64、SPARC和IBMZ系列机等中都支持该指令的某个版本，而且多数操作系统都利用该指令支持并发。图31a给出了基于使用这个指令的互斥规程。共享变量bolt被初始化为0。唯一可以进入临界区的进程是发现bolt等于0的那个进程。所以有试图进入临界区的其他进程进入忙等待模式。术语忙等待Busy Waiting或自旋等待Spin Waiting指的是这样一种技术： 进程在得到临界区访问权之前，它只能继续执行测试变量的指令来得到访问权，除此之外不能做其他事情。当一个进程离开临界区时，它把bolt重置为0，此时只有一个等待进程被允许进入临界区。进程的选择取决于哪个进程正好执行紧接着的比较和交换指令。2 exchange指令exchange指令定义如下。
void exchange int *register, int *memory
{
int temp;
temp = *memory;
*memory = *register;
*register = temp;
}
该指令交换一个寄存器的内容和一个存储单元的内容。Intel IA32Pentium和IA64Itanium体系结构都含有XCHG指令。
图31对互斥的硬件支持
图31b显示了基于exchange指令的互斥规程： 共享变量bolt被初始化为0，每个进程都使用一个局部变量key且初始化为1。唯一可以进入临界区的进程是发现bolt等于0的那个进程。它通过把bolt置为1排斥所有其他进程进入临界区。当一个进程离开临界区时，它把bolt重置为0，允许另一个进程进入它的临界区。注意，由于变量初始化的方式及exchange算法的本质，下面的表达式总是成立的。
bolt ikeyi= n
如果bolt = 0，则没有任何一个进程在它的临界区中； 如果bolt = 1，则只有一个进程在临界区中，即key的值等于0的那个进程。使用专门的机器指令实施互斥具有以下优点。1 适用于在单处理器或共享内存的多处理器上的任何数目的进程。2 非常简单且易于证明。3 可用于支持多个临界区，每个临界区可以用它自己的变量定义。但是，它也有一些严重的缺点。1 使用了忙等待： 当一个进程正在等待进入临界区时，它会继续消耗处理器时间。2 可能饥饿： 当一个进程离开一个临界区并且有多个进程正在等待时，选择哪一个等待进程是任意的，因此某些进程可能被无限地拒绝进入。3 可能死锁： 考虑单处理器中的下列情况。进程P1执行专门指令如compare & swap、exchange并进入临界区，然后P1被中断并把处理器让给具有更高优先级的P2。如果P2试图使用同一资源，由于互斥机制，它将被拒绝访问。因此，它会进入忙等待循环。但是，由于P1比P2的优先级低，它将永远不会被调度执行。3.2PV操作上面所介绍的硬件实现互斥属于忙等待的互斥，本节介绍怎样用PV操作来管理相关临界区，亦即用PV操作实现进程的互斥。3.2.1信号量与PV操作1. 信号量信号量的概念和PV操作是荷兰科学家E. W. Dijkstra提出来的。信号是交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。在操作系统中，信号量S是一个整数。当S大于等于零时，代表可供并发进程使用的资源实体数； 当S小于零时，则|S|表示正在等待使用资源实体的进程数。建立一个信号量必须说明此信号量所代表的意义并且赋初值。除赋初值外，信号量仅能通过PV操作来访问。信号量按其用途可分为以下两种。1 公用信号量，联系一组并发进程，相关的进程均可在此信号量上进行P操作和V操作，初值常常为1，用于实现进程互斥，也称为互斥信号量。2 私有信号量，联系一组并发进程，仅允许拥有此信号量的进程执行P操作，而其他相关进程可在其上施行V操作。初值常常为0或正整数，多用于实现进程同步，也称为资源信号量。2. PV操作PV操作是由两个操作，即P操作和V操作组成。P操作和V操作是两个在信号量上进行操作的过程，假定用S表示信号量，则把这两个过程记作PS和VS，它们的定义如下。
procedure PS： Semaphore
begin
S∶=S - 1;
if S = 1 then begin
di ∶= di -1;
Bj ∶= di;
VS;
［输出一张票］;
end;
else begin
VS;
［提示信息"票已售完"］;
end;
end;
coend;
例35用PV操作管理主存问题。
x： integer;
S： Semaphore;
x∶= 1000; S∶= 1;
cobegin
procedure Borrow B： integer
begin
PS;
if B x then ［进程进入等待队列，等待主存资源］;
x∶= x - B;
［修改主存分配表，进程获得主存资源］;
VS;
end;
procedure Return B： integer
begin
PS;
x∶= x B;
［修改主存分配表］;
VS;
［释放等待主存资源的进程］;
end;
coend;
例36用PV操作管理自动计数问题。
count： integer;
S： Semaphore;
count∶= 0;S∶= 1;
cobegin
procedure Observer
begin
L1： ［observer a car］;
PS;
count∶= count 1;
VS;
goto L1;
end;
procedure Reporter
begin
PS;
print count;
count ∶= 0;
VS;
end;
coend;
例37用PV操作解决5个哲学家吃通心面问题。
图345个哲学家进餐问题
有5个哲学家围坐在一张圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一根筷子。每个哲学家思考、饥饿，然后欲吃通心面。为了吃面，每个哲学家必须获得两根筷子，且每人只能直接从自己左边或右边取得筷子如图34所示。在这道经典题目中，每一根筷子都是必须互斥使用的，因此，应为每根筷子设置一个互斥信号量Sii=0，1，2，3，4，初值均为1，当一个哲学家吃通心面之前必须获得自己左边和右边的两根筷子，即执行两个P操作； 吃完通心面后必须放下筷子，即执行两个V操作。
S0, S1, S2, S3, S4 ： Semaphore;
S0∶= 1; S1 = 1; S2 = 1; S3 = 1; S4 = 1;
cobegin
procedure PHii = 0，1，2，3，4
begin
L1：
［思考］;
PSi;
PSi 1 mod 5 ;
［吃通心面］;
VSi;
VSi 1 mod 5 ;
goto L1;
end;
coend;
3.3进 程 同 步3.3.1同步的概念
利用信号量我们解决了进程的互斥问题，但互斥主要是解决并发进程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的，只要诸进程对临界区的执行时间互斥，每个进程就可忽略其他进程的存在和作用。此外，还需要解决异步环境下的进程同步问题。所谓异步环境，是指相互合作的一组并发进程，其中每一个进程都以各自独立的、不可预知的速度向前推进，但它们又需要密切合作以实现一个共同的任务，即彼此知道相互的存在和作用。例如，为了把原始的一批记录加工成当前需要的记录，创建了两个进程，即进程A和进程B。进程A启动输入设备不断地读记录，每读出一个记录就交给进程B去加工，直至所有记录都处理结束。为此，系统设置了一个容量为存放一个记录的缓冲器，进程A把读出的记录存入缓冲器，进程B从缓冲器中取出记录加工，如图35所示。
图35进程协作
进程A和进程B是两个并发进程，它们共享缓冲器，如果两个进程不相互制约就会造成错误。当进程A的执行速度超过进程B的执行速度时，可能进程A把一个记录存入缓冲器后，在进程B还没有取走前，进程A又把新读出的一个记录存入缓冲器，后一个记录就把前一个尚未取走的记录覆盖了，造成记录的丢失。当进程B的执行速度超过进程A的执行速度时，可能进程B从缓冲器取出一个记录并加工后，进程A还没有把下一个新记录存入缓冲器，而进程B却又从缓冲器中去取记录，造成重复地取同一个记录加工。用进程互斥的办法不能克服上述两种错误。事实上，进程A和进程B虽然共享缓冲器，但它们都是在无进程使用缓冲器时才向缓冲器存记录或从缓冲器取记录的。也就是说，它们在互斥使用共享缓冲器的情况下仍会发生错误，引起错误的根本原因是它们之间的相对速度。可以采用互通消息的办法来控制执行速度，使相互协作的进程正确工作。两个进程应该按照如下原则协作。1 进程A把一个记录存入缓冲区后，应向进程B发送缓冲器中有等待处理的记录的消息。2 进程B从缓冲器中取出记录后，应向进程A发送缓冲器中的记录已取走的消息。3 进程A只有在得到进程B发送来的缓冲器中的记录已取走的消息后，才能把下一个记录再存入缓冲器。否则进程A等待，直到消息到达。4 进程B只有在得到进程A发送来的缓冲器中有等待处理的消息后，才能从缓冲器中取出记录并加工。否则进程B等待，直到消息到达。由于每个进程都是在得到对方的消息后才去使用共享的缓冲器，所以不会出现记录的丢失和记录的重复处理。因此，进程的同步是指导并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达时才被唤醒。3.3.2PV操作实现进程同步要实现进程的同步就必须提供一种机制，该机制能把其他进程需要的消息发送出去，也能测试自己需要的消息是否到达。把能实现进程同步的机制称为同步机制，不同的同步机制实现同步的方法也不同，PV操作和管程是两种典型的同步机制。本节介绍怎样用PV操作实现进程间的同步。我们已经知道怎样用PV操作来实现进程的互斥。事实上，PV操作不仅是实现进程互斥的有效工具，而且还是一个简单而方便的同步工具。用一个信号量与一个消息联系起来，当信号量的值为0时表示期望的消息尚未产生，当信号量的值为非0时表示期望的消息已经存在。假定用信号量S表示某个消息，现在来看看怎样用PV操作达到进程同步的目的。1. 调用P操作测试消息是否到达任何进程调用P操作可测试到自己所期望的消息是否已经到达。若消息尚未产生则S=0，调用PS后，PS一定让调用者成为等待信号量S的状态，即调用者此时必定等待直到消息到达； 若消息已经存在则S0，调用PS后进程不会成为等待状态而可继续执行，即进程测试到自己期望的消息已经存在。2. 调用V操作发送消息任何进程要向其他进程发送消息时可调用V操作。若调用V操作之前S＝0，表示消息尚未产生且无等待消息的进程，这时调用VS后执行S∶=S 1使S0，即意味着消息已存在； 若调用V操作之前S 1，那么只要把信号量sPdt的初值定为n,sGet的初值仍为0。当缓冲器中没有放满n件物品时，生产者调用PsPdt后都不会成为等待状态而可以把生产出来的物品存入缓冲器。但当缓冲器中已经有n件物品时sPdt值为0，生产者再想存入一件物品将被拒绝。生产者每存入一件物品后，由于调用VsGet发送消息，故sGet的值表示缓冲器中可供消费的物品数。只要sGet0，消费者调用PsGet后总可以去取物品，每取走一件物品后调用VsPdt，便增加了一个可以用来存放物品的位置。由于缓冲器可存n件物品，因此，必须指出缓冲器中什么位置已有物品可供消费，什么位置尚无物品可供生产者存放物品。可以用两个指针pp和cp分别指示生产者往缓冲器存物品与消费者从缓冲器取物品的相对位置，它们的初值为0，生产者和消费者按顺序的位置去存物品和取物品。缓冲器被循环使用，即生产者在缓冲器中顺序存放了n件物品后，则以后继续生产的物品仍从缓冲器的第一个位置开始存放。于是，一个生产者和一个消费者共享容量为n的缓冲器时，可如下进行同步工作。
Buf：array ［ 0 . . n -1 ］ of integer;
sPdt, sGet ： Semaphore;
pp, cp： integer;
sPdt∶= n; sGet∶=0;pp∶=0; cp∶=0;
cobegin
procedure producer
begin
L1： ［produce a product］;
P sPdt;
Buf［ pp ］∶= product;
pp∶= pp1 mod n;
V sGet;
goto L1;
end;
procedure consumer
begin
L2： P sGet;
［Take a product from Buf［cp ］ ］;
cp ∶= cp 1mod n;
V sPdt;
［consume］;
goto L2;
end;
coend;
但是，要提醒注意的是，如果PV操作使用不当，仍会出现与时间有关的错误。例如，有p个生产者和q个消费者，它们共享可存放n件物品的缓冲器； 为了使它们能协调工作，必须使用一个互斥信号量S初值为1，以限制它们对缓冲器互斥地存取。另外，使用两个信号量sPdt初值为n和sGet初值为0来保证生产者不往满的缓冲器中存放物品，消费者不从空的缓冲器中取出物品。同步工作描述如下。
Buf： array ［0 . . n -1］ of integer;
sPdt, sGet, S ： Semaphore;
pp, cp： integer;
sPdt∶= n; sGet∶=0;pp∶=0; cp∶=0;S∶= 1;
cobegin
procedure producerii = 1, 2,,p
begin
L1：［produce a product］;
P sPdt;
PS;
Buf［ pp ］ ∶= product;
pp∶= pp 1mod n;
VsGet;
VS;
goto L1;
end;
procedure consumerjj = 1,2,,q
begin
L2：PsGet;
PS;
［Take a product from Buf［ cp ］］;
cp∶= cp 1mod n;
VsPdt;
VS;
［consume］;
goto L2;
end
coend;
在这个例子中，P操作的顺序是很重要的，如果把生产者和消费者进程中的两个P操作交换顺序，则会导致错误。而V操作的顺序却是无关紧要的。一般来说，用于同步的信号量上的P操作先执行，而用于互斥的信号量上的P操作后执行。生产者消费者问题是非常典型的问题，有许多问题可归结为生产者消费者问题，但要根据实际情况灵活运用。例如，现有4个进程R1、R2、P1、P2，它们共享可以存放一个数的缓冲器Buf。进程R1每次把来自键盘的一个数存入缓冲器Buf中，供进程P1打印输出； 进程R2每次从磁盘上读一个数存放到缓冲器Buf中，供进程P2打印输出。为防止数据的丢失和重复打印，怎样用PV操作来协调这4个进程的并发执行？先来分析一下这4个进程的关系，进程R1和进程R2相当于两个生产者，接收来自键盘的数或从磁盘上读出的数相当于这两个进程各自生产的物品。两个进程各自生产的不同物品要存入共享的缓冲器Buf中，由于Buf中每次只能存入一个数，因此进程R1和进程R2在存数时必须互斥。进程P1和进程P2相当于两个消费者，它们分别消费进程R1和进程R2生产的物品。所以进程R1或进程R2在把数存入缓冲器Buf后应发送消息通知进程P1或进程P2。进程P1或进程P2在取出数之后应发送消息通知R1或进程R2告知缓冲器中又允许放一个新数的消息。显然，进程R1与进程P1、进程R2与进程P2之间要同步。在分析了进程之间的关系后，应考虑怎样来定义信号量。首先，应定义一个是否允许进程R1或进程R2把数存入缓冲器的信号量S，其初值为1。其次，进程R1或进程R2分别要向进程P1和进程P2发送消息，应该要有两个信号量S1和S2来表示相应的消息，初值都应为0，表示缓冲器中尚未有数。至于进程P1或进程P2从缓冲器中取出数后要发送缓冲器中允许放一个新数的消息，这个消息不应该特定地发给进程R1或进程R2，所以只要调用VS就可达到目的。到底哪个进程可以把数存入缓冲器中，由进程R1或进程R2调用PS来竞争。因此，不必再增加新信号量了。现定义三个信号量，其物理含义如下。S： 表示能否把数存入缓冲器Buf。S1： 表示缓冲器中是否存有来自键盘的数。S2： 表示缓冲器中是否存有从磁盘上读取的数。例394个进程可如下协调工作。
Buf ： integer;
S,S1,S2 ： Semaphore;
S∶= 1; S1∶= 0; S2∶= 0;
cobegin
procedure R1
x： integer;
begin
L1：［接收来自键盘的数］;
x ∶=接收的数;
PS;
Buf∶= x;
VS1;
goto L1;
end;
procedure R2
y： integer;
begin
L2：［从磁盘上读一个数］;
y ∶= 读入的数;
PS;
Buf∶= y;
VS2;
goto L2;
end;
procedure P1
k： integer;
begin
L3： PS1;
k∶= Buf;
VS;
［打印k的值］;
goto L3;
end;
procedure P2
j： integer;
begin
L4： PS2;
j∶= Buf
VS;
［打印j的值］
goto L4;
end;
coend;
在这里，进程R1和进程R2在向缓冲器Buf中存数之前调用了PS，其有两个作用。1 由于S的初值为1，所以PS限制了每次至多只有一个进程可以向缓冲器中存入一个数，起到了互斥地向缓冲器中存数的作用。2 当缓冲器中有数且尚未被取走时S的值为0，当缓冲器中数被取走后S的值又为1，因此PS起到了测试允许存入一个新数的消息是否到达的同步作用。进程P1和进程P2把需要的数取走后，都调用VS发出可以存放一个新数的消息。可见，在这个问题中信号量S既被作为互斥的信号量，又被作为同步的信号量。在操作系统中进程同步问题是非常重要的，通过对一些例子的分析应该学会怎样区别进程的互斥和进程的同步。PV操作是实现进程互斥和进程同步的有效工具，但若使用不得当则不仅会降低系统效率而且仍会产生错误，希望读者在弄清PV操作作用的基础上，体会在各个例子中调用不同信号量上的P操作和V操作的目的，从而正确掌握对各类问题的解决方法。3.3.4读者写者问题读者写者问题也是一个经典的并发程序设计问题。有两组并发进程： 读者和写者共享一个文件F，要求： ①允许多个读者同时对文件执行读操作； ②只允许一个写者往文件中写信息； ③任一写者在完成写操作之前不允许其他读者或写者工作； ④写者执行写操作前，应让已有的写者和读者全部退出。单纯使用信号量不能解决读者写者问题，必须引入计数器rc记录读进程数，rmutex是用于对计数器rc操作的互斥信号量，W表示是否允许写的信号量，于是管理该文件的同步工作描述如下。
例310读者写者进程同步操作。
rmutex, W ： Semaphore;
rc： integer;
rmutex∶= 1;rc ∶= 0;W ∶= 1;
cobegin
procedure readi i = 1, 2,
begin
P rmutex;
rc∶= rc 1;
if rc == 1 then P W;
V rmutex;
［读文件］;
P rmutex;
rc∶= rc - 1;
if rc ==0 then V W;
V rmutex;
end;
procedure writej j = 1, 2,
begin
P W;
［写文件］;
V W;
end;
coend;
在上面的方法中，读者是优先的。当存在读者时，写操作将被延迟，并且只要有一个读者在访问文件，随后而来的读者都将被允许访问文件。从而导致了写进程长时间等待，并有可能出现写进程被饿死。增加信号量并修改上述程序可以得到写进程具有优先权的解决方案能保证当一个写进程声明想写时，不允许新的读进程再访问共享文件。对于写进程在已有定义的基础上还必须增加下列信号量和变量，引入计数器wc记录写进程数，wmutex是用于对计数器wc操作的互斥信号量。R表示是否允许读的信号，当至少有一个写进程准备访问文件时，用于禁止所有的读进程。对于读进程还需要一个额外的信号量。在R上不允许建造长队列，否则写进程将不能跳过这个队列，因此，只允许一个读进程在R上排队，而所有其他读进程在等待R之前，在信号量rlist上排队。例311写者优先，读者写者进程同步操作。
rmutex, wmutex, rlist, W, R： Semaphore;
rc, wc ： integer;
rmutex∶= 1; wmutex∶= 1; rlist ∶= 1;W ∶= 1; R ∶= 1;rc ∶= 0; wc ∶= 0;
cobegin
procedure readi i = 1, 2,
begin
Prlist;
PR;
P rmutex;
rc∶= rc 1;
if rc == 1 then P W;
V rmutex;
VR;
Vrlist;
［读文件］;
P rmutex;
rc∶= rc - 1;
if rc == 0 then V W;
V rmutex;
end;
procedure writej j = 1, 2,
begin
P wmutex;
wc ∶= wc 1;
if wc == 1 then PR;
Vwmutex;
P W;
［写文件］;
V W;
P wmutex;
wc ∶= wc - 1;
if wc == 0 then VR;
Vwmutex;
end;
coend;
3.3.5时间同步问题前面讲到的进程同步都属于空间上的同步问题，其实进程同步还有个时间上的同步问题。当一组有关的并发进程在执行时间上有严格的先后顺序时，就会出现时间上的进程同步问题。例如，有7个进程，它们的执行顺序如图36所示。
图367个进程的执行顺序
为了保证这7个进程严格按照顺序执行，可定义6个信号量，其物理含义如下。S2： 表示进程P2能否执行。S3： 表示进程P3能否执行。S4： 表示进程P4能否执行。S5： 表示进程P5能否执行。S6： 表示进程P6能否执行。S7： 表示进程P7能否执行。进程P1不需定义信号量，可随时执行。这些信号量的初值为0，表示不可执行，而当信号量大于等于1时，表示可执行。例312进程执行顺序同步工作描述如下。
S2, S3, S4, S5,S6, S7： Semaphore;procedure P4
S2∶= 0;S3∶= 0;S4∶= 0;begin
S5∶= 0;S6∶= 0;S7∶= 0;P S4;
cobegin
procedure P1V S6;
beginend;
procedure P5
V S2;begin
V S3;P S5;
V S4;
end;V S6
procedure P2end;
beginprocedure P6
P S2;begin
P S6;
V S7;P S6;
end;
procedure P3V S7;
beginend;
P S3;procedure P7
begin
V S5;PS7;
end;PS7;
end;
coend;
当P1执行完后，由于执行了VS2、VS3和VS4三个V操作，使P2、P3和P4在P1后可并发执行。P3执行完后，由于执行了VS5操作，则可启动P5执行。而P6要等P4与P5两个进程全部执行完，执行了两个VS6操作后，才能启动执行。P7要等P2与P6两个进程全部执行完，执行了两个VS7操作后才能启动执行。这样，就可以保证7个进程在时间上的同步。3.4管程3.4.1什么是管程
信号量机制为实现进程的同步与互斥提供一种原始、功能强大且灵活的工具，然而在使用信号量和PV操作实现进程同步时，对共享资源的管理分散于各个进程中，进程能够直接对共享变量进行处理，这样不利于系统对临界资源的管理，难以防止进程有意或无意地违反同步操作，且容易造成程序设计错误。因此，在进程共享主存的前提下，如果能集中和封装针对一个共享资源的所有访问并包括所需的同步操作，即把相关的共享变量及其操作集中在一起统一控制和管理，就可以方便地管理和使用共享资源，使并发进程之间的相互作用更为清晰，也更易于编写正确的并发程序。1973年，Hansen和Hoare正式提出了管程Monitor的概念，并对其做了如下的定义： 管程是关于共享资源的数据及在其上的操作的一组过程或共享数据结构及其规定的所有操作。管程的引入可以让我们按资源管理的观点，将共享资源和一般资源管理区分开来，使进程同步机制的操作相对集中。采用这种方法，对共享资源的管理可借助数据结构及其上所实施操作的若干进程来进行； 对共享资源的申请和释放可通过进程在数据结构上的操作来实现。管程被请求和释放资源的进程所调用，管程实质上是把临界区集中到抽象数据类型模板中，可作为程序设计语言的一种结构成分。对于同步问题的解决，管程和信号量具有同等的表达能力。3.4.2使用信号量的管程管程是由一个或多个过程、一个初始化序列和局部数据组成的软件模块，其主要特点如下。1 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。2 一个进程通过调用管程的一个过程进入管程。3 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。前两个特点让人联想到面向对象软件中对象的特点。的确，面向对象操作系统或程序设计语言可以很容易地把管程作为一种具有特殊特征的对象来实现。通过给进程强加规定，管程可以提供一种互斥机制： 管程中的数据变量每次只能被一个进程访问到。因此，可以把一个共享数据结构放在管程中，从而提供对它的保护。如果管程中的数据代表某些资源，那么管程为访问这些资源提供了互斥机制。为进行并发处理，管程必须包含同步工具。例如，假设一个进程调用了管程，并且当它在管程中时必须被阻塞，直到满足某些条件。这就需要一种机制，使得该进程不仅被阻塞，而且能释放这个管程，以便某些其他的进程可以进入。以后，当条件满足且管程再次可用时需要恢复该进程并允许它在阻塞点重新进入管程。管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问。有以下两个函数可以操作条件变量。1 cwaitc： 调用进程的执行在条件c上阻塞，管程现在可被另一个进程使用。2 csignalc： 恢复执行在cwait之后因为某些条件而阻塞的进程。如果有多个这样的进程，选择其中一个； 如果没有这样的进程，什么也不做。注意，管程的wait和signal操作与信号量不同。如果在管程中的一个进程发信号，但没有在这个条件变量上等待的任务，则丢弃这个信号。图37给出了一个管程的结构。尽管一个进程可以通过调用管程的任何一个过程进入管程，但我们仍可以把管程想象成具有一个入口点，并保证一次只有一个进程可以进入。其他试图进入管程的进程被阻塞并加入等待管程可用的进程队列中。当一个进程在管程中时，它可能会通过发送cwaitx把自己暂时阻塞在条件x上，随后它被放入等待条件改变以重新进入管程的进程队列中，在cwaitx调用的下一条指令开始恢复执行。
图37管程的结构
如果在管程中执行的一个进程发现条件变量x发生了变化，它将发送csignalx，通知相应的条件队列条件已改变。为给出一个使用管程的例子，我们再次考虑有界缓冲区的生产者消费者问题。例313给出了使用管程的一种解决方案，管程模块PC控制着用于保存和取回物品的缓冲区，管程中有两个条件变量使用结构condition声明： 当缓冲区中至少有增加一个物品的空间时，notfull为真； 当缓冲区中至少有一个物品时，notempty为真。生产者可以通过管程中的过程put往缓冲区中存放物品，它不能直接访问buffer。该过程首先检查条件notfull，以确定缓冲区是否还有可用空间。如果没有，执行管程的进程在这个条件上被阻塞。其他某个进程生产者或消费者现在可以进入管程。然后，当缓冲区不再满时，被阻塞进程可以从队列中移出，重新被激活，并恢复处理。在往缓冲区中放置一个物品后，该进程发送notempty条件信号。对消费者函数也可以进行类似的描述。这个例子指出，与信号量相比较，管程担负的责任不同。对于管程，它构造了自己的互斥机制： 生产者和消费者不可能同时访问缓冲区； 但是，程序员必须把适当的cwait和csignal原语放在管程中，用于防止进程往一个满缓冲区中存放数据项，或者从一个空缓冲区中取数据项。而在使用信号量的情况下，执行互斥和同步都属于程序员的责任。例313PC管程可描述如下。
* program producer_consumer *
Type PC = monitor
buffer：array［0..n-1］ of char;*分配n个字符型数据空间*
nextin, nextout ： int;* 缓冲区指针 *
count ： int;*缓冲区中数据项的个数*
notfull,notempty ： condition;*为同步设置的条件变量*
void put char x
{
if count = n thencwaitnotfull;*缓冲区满，防止溢出*
buffer［nextin］ ∶= x;
nextin ∶= nextin 1 mod n;
count;*缓冲区中数据项个数增1*
csignalnonempty;*释放任何一个等待的进程*
}
void take char x
{
if count = n cwait notfull; *缓冲区满，防止溢出*
buffer［nextin］ ∶= x;
nextin ∶= nextin1 % n;
count; *缓冲区中数据项个数增1*
cnotifynotempty;*通知正在等待的进程*
}
void take char x
{
while count {信箱大小}
count： integer;{现有消息数}
letter： array［ 1 . . n ］ of message;{信箱}
s1, s2： semaphore; {等信箱和等消息信号量}
end;
procedure send B： box, M：message
i ： integer;
begin
if B.count = B. size then w B. s1;
i ∶= B. count 1;
B. letter ［ i ］ ∶= M;
B. count ∶= i;
RB. s2;
end;
procedure receive B： box, X： message
i： integer;
begin
if B. count = 0 then WB. s2;
B. count∶= B. count - 1;
X∶= B. letter ［ 1 ］;
if B. count0 then for i = 1 to B. count do B. letter ［ i ］ ∶= B. letter ［ i 1 ］;
RB. s1;
end;
信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。1 私用信箱。用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取信息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路信箱实现。当拥有该信箱的进程结束时，信箱也随之消失。2 公用信箱。它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中取出发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。3 共享信箱。它由某进程创建，在创建时或创建后指明它是可共享的，同时需指出共享进程用户的名字。信箱的拥有者和共享者都有权从信箱中取走发送给自己的消息。在利用信箱通信时，在发送进程和接收进程之间存在着下述的4种关系。1 一对一关系。即可以为发送进程和接收进程建立一条专用的通信链路，使它们之间的交互不受其他进程的影响。2 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户服务器交互。3 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播形式向接收者发送消息。4 多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息，也可从信箱中取走属于自己的消息。3.5.4消息格式消息的格式取决于消息机制的目标及该机制是运行在一台计算机上还是运行在分布式系统中。对于某些操作系统，设计者优先选用短的、固定长度的消息，以减小处理和存储的开销。如果需要传递大量的数据，
图38一般消息格式
数据可以放置到一个文件中，消息可以简单地引用该文件。一种更为灵活的方法是允许可变长度的消息。图38给出了一种操作系统的支持可变长度消息的典型消息格式。该消息被划分成两部分： 包含相关信息的消息头和包含实际内容的消息体。消息头可以包含消息的源和目标的标识符、长度域，以及判定各种消息类型的类型域，还可能含有一些额外的控制信息，例如，用于创建消息链表的指针域、记录源和目标之间传递的消息的数目、顺序与序号，以及一个优先级域。3.5.5解决生产者消费者问题作为使用消息传递的一个例子，例316是解决有界缓冲区生产者消费者问题的一种方法。该例利用了消息传递的能力，除了传递信号之外还传递数据。它使用了两个信箱。当生产者产生了数据后，它作为消息被发送到信箱mayConsume，只要该信箱中有一条消息，消费者就可以开始消费。此后mayConsume用作缓冲区，缓冲区中的数据被组织成消息队列，缓冲区的大小由全变局变量capacity确定。信箱mayProduce最初填满了空消息，空消息的数量等于信箱的容量，每次生产使得mayProduce中的消息数减少，每次消费使得mayProduce中的消息数增长。这种方法非常灵活，可以有多个生产者和消费者，只要它们都访问这两个信箱即可。系统甚至可以是分布式系统，所有生产者进程和mayProduce信箱在一个站点上，所有消费者进程和mayConsume信箱在另一个站点上。例316使用消息解决有界缓冲区生产者消费者问题。
const int
capacity = * 缓冲区容量 * ;
null = * 空消息* ;
int i;
void producer
{
message pmsg;
while true {
receive mayProduce,pmsg ;
pmsg = produce ;
send mayConsume, pmsg ;
}
}
void consumer
{
message cmsg;
while true {
receive mayConsume, cmsg;
consume cmsg;
send mayProduce,null;
}
}
void main
{
create_mailbox mayProduce;
create_mailbox mayConsume;
for int i = 1;i
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
