Chinaunix首页 | 论坛 | 博客
  • 博客访问: 216778
  • 博文数量: 53
  • 博客积分: 25
  • 博客等级: 民兵
  • 技术积分: 1550
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-27 07:54
  • 认证徽章:
个人简介

IT民工一枚,为学弟学妹造福是我一直写博文的动力!为媳妇提供技术支持是我学习新技术的动力!为自己脱离贫困线,买到心仪的摩托车,有饭吃,有床睡,有妹把,笔耕不辍~~

文章分类

全部博文(53)

文章存档

2013年(54)

分类: 信息化

2013-05-24 21:03:41

一、基本概念

(一)进程特征

经典的OS教材一般会讲到四点:并发,共享,异步,不确定。后两者有不可分割的关系,前两点是操作系统发展的灵魂。所以还是非常重要的概念。学过OS课程的,对于并发和并行的区别并不陌生,不再赘述。异步是什么意思呢?字面意思!对滴,就是不同步发生,这个特性在系统的实现中体现的淋漓尽致,因为我们不能给出同步的硬件解决方案,只能通过异步形式跟踪程序进行,监听变化,随之发生设定到的变化。那不确定性又是什么意思呢?不确定多适用于实验系统,良好的实验要求有可复现性,但是基于CPU运算中各种随机因素,进程的执行就有不确定性这个特点。也因此,我们的大计算机科学才没能够在创建初期迅速崛起。

基于进程的这些特点,我们如何实现进程之间的通信成为问题,当然我们可以通过简单的共享实现,但那种方式比价消耗资源,同时效率不是很高,还容易出错,最大的问题是进程间消息的协作,关键活动的独立性等都是要解决的问题。于是进程间的同步互斥机制就产生了。

在进行分析之前,先总结一下,可能用到同步互斥机制的问题:

1.带共享资源的读写问题,这类问题是很经典的,不需解释;具体的例子有读者写者问题,飞机订票,银行取款,哲学家进餐,过河问题等;

2.带共同目的的协作问题,这类问题可以做出进程协作图,不同进程之间通过通信进行同步。具体的例子比如各类工程管理驱动图,关键路径,spooling技术等;

3.带有竞争条件的上述问题的集合,是综合了同步互斥机制和实现过程的大问题。

于是乎,我们来简单介绍一下几个提到概念。

(二)同步互斥相关概念

竞争条件:几个进程并发访问一个共享资源,结果取决于进程的运行时序,而顺序是不确定的,所以出现不确定因素;

进程互斥:对于一个共享资源,一次只能被一个进程使用,使用这个资源的进程之间构成互斥关系;

临界资源:互斥中提到的共享资源便是临界资源;

临界区:对于临界资源进行操作的一段程序称作临界区,临界区有些使用的原则:任何两个进程不能同时进入临界区;不能对CPU的运行速度进行任何的假设,换句话说,使用临界区的进程不能估算出在临界区中的时间;临界区外的进程不能阻塞其他进程,也就是保证了竞争临界区条件的公平性;不能使临界区外的进程无限等待,要么不等,要么临界区内的程序限时出临界区,重新竞争;

(三)实现方案

实现互斥的可选方案有两类:硬件,软件。

硬件方案以中断为核心,方式有屏蔽中断,使用汇编指令关闭中断;软件以加锁形式进行互斥,保证资源在自己使用的过程中不被剥夺。具体的有Dekker、Petersion解法比较靠谱。

这里的锁当然仅是一个不可被打断的标志位。D童鞋使用两个标志位完成了加锁,一个是抛硬币,一个是共享锁标识;P同学的思路更切合于当前的加锁思路,将加锁过程抽象出来,给使用锁的用户抛出进入临界区和出临界区的函数接口。具体实现过程中,使用了D同学的思路。P同学算是使用软件方式真正完成加锁算法的第一人。

硬件解决方案就没什么可说的,进临界区关中断,出临界区开,简单明了。但是,关中断的过程中,限制了CPU的并发能力,不适用与多处理器系统。当然,更开关中断相类似的TSL汇编指令也有相同的弊端。

无论如何,反正是解决了互斥的问题,现在来尝试做一个例子:生产者消费者问题(隶属于第一类)专业一点,叫有限缓冲区问题

问题描述:N个生产者,N个消费者,每次只有一个生产者向缓冲区中加入新产品,每次只有一个消费者从缓冲区中取走产品,保证缓冲区满的时候停止放入,缓冲区空的时候停止取走;同时应该避免忙等待。

问题解决思路:生产者进程之间互斥向缓冲区放入,mutex1;消费者之间互斥从缓冲区中取,mutex2;缓冲区一次只能有一个人在操作,mutex;缓冲区内数量限制,为空不能取,为满不能放,count;为了避免忙等待,应该维护一个等待列表,waitList。然后画出逻辑关系图,开始写代码就行啦。具体的实现过程,可以参考网上其他资料,此处不再赘述。

(四)进程同步问题

系统中的多个进程之间为同一个目的,存在一定的时序问题,需要相互合作。具体讲,一个进程运行起来需要另一个进程输出的条件,等待这个进程的时候,该进程进入阻塞态。同步是互斥的特例,或者反过来讲也没有问题。

二、信号量

基于上述软件解决方案,65年Dijkstra提出了信号量的概念,NB一时。说白了,还是一个数据结构类型的变量,维护一个队列和一个计数器,同时包含对成员的PV操作。他的NB之处并非提出了这么一个改进版的变量,而是将原语的概念引入计算机,前边已经提到了这个概念。规定,我的PV操作是不可中断的,这就是霸气。

刚开始提出的时候用于解决互斥问题,就是二值信号量,随后将计数器改为多值,进而可以解决同步问题。然后给出了使用方案;

首先分析问题,画出逻辑关系图,划定临界区;设置二值信号量解决互斥问题,多值解决同步问题,给出初值;用PV操作包围临界区

尝试使用信号量解决读者写者问题,此处不再赘述,一定要按照上边给出的方案进行分析和设计。

三、管程

首先,管程是神马玩意?一贯风格,先猜一下,管理进程的玩意?NO

虽然猜错了,但猜测的过程是重要的,我们没猜准只能说明这名起的有问题,或者翻译有问题。monitor应该翻译成啥比较合适呢?我宁可翻译成班长。

重新认识一下:首先从根本上入手,引入信号量的时候,给出了一个数据结构和对数据结构的操作。随着OOAD的发展,类的概念貌似更适合这样一个类型,对滴,管程就是一个类。

还是正规一点,从头开始:

(一)为啥需要管程?

使用过信号量进行编程的童鞋可能有这样的体会,一定要小心翼翼的,一不小心设计不好,就死锁了,或者程序本来运行的不错,给老师一检查,就死机了。。。这不仅说明个人能力有问题,同时也说明了这个机制有问题,比如公司大部分人早上都会迟到,因为迟到扣工资的不胜枚举,一方面说明大家都比较懒,不太在乎迟到,同时说明,似乎迟到这个机制的标准定的有些不合理,比如7点上班。这是个分析问题的好思路,有点跑题。继续说管程的由来。

如上所述,信号量机制有问题,这么复杂的逻辑处理过程应该交给计算机来处理,保证编程的高效和规范正确;另外,同步机制应该给出固定的规范性的东西,让大家有法可依。当然NB的科学家们早就发现了这个问题,于是管程出现了,Hansen和Hoare比较出名。

(二)管程的定义

通过共享数据结构抽象的表示系统共享资源,并把对共享数据结构实施的操作定义为一个处理过程。我们把这个管理过程称作管程。Hansen给出了一个更加贴切的定义:一个管程定义了一个数据结构和能为并发进程调用的一组操作,这组操作用于同步进程并改变管程中的数据。之所以说这个定义比较好,是因为H从类的角度给出了定义,说明了管程中包含的四大部分:共享变量、条件变量、并行执行的进程、初始化类成员的构造函数。由此,并行执行的进程只能通过管程提供的方法访问共享变量,相当于把共享变量封装到管程中,完成了任务。有人会问,管程中如何实现开关中断或者锁这样的原语操作呢?PV操作是怎么实现的呢?这就是管程的NB之处,管程将具体的实现过程屏蔽,具体的实践过程由编译器自动完成,也就是我们一直讲的机制上,改进了同步互斥问题的解决方案。

(三)管程的任务

管程通过对共享变量的保护实现互斥问题;通过条件变量实现同步问题,条件变量好像有点陌生,下边会详细讲。首先要声明的是,条件变量这东西,只能由管程的wait() signal()等自己定义的方法访问,记住这一点,用起来就轻松一些了。

(四)管程使用过程中遇到的问题

当一个进程在管程中执行wait()操作后,他等待在管程中,并释放了共享变量的互斥权,其他进程可以使用管程,这时新进入的进程执行了signal()操作,唤醒了等待的老进程,此时,两个进程都在管程中,这如何是好?上边提到的两个大牛分别给出了解决方案。也就是我们说的条件变量的部分。

(五)Hoare管程

管程是互斥进入的,在管程外部等待的进程通过一个叫做入口等待队列的链表进行维护。进入管程而被迫的等待的进程加入叫做紧急等待队列的链表,后者的优先级要高于前者。条件变量就是维护这两个链表的变量,在条件变量上可以执行wait()signal()操作,具体可以参见度娘解释。

(六)Mesa管程

引入notify方法,当进程执行本方法时,使得等待队列接收可执行通知,发送信号的进程继续执行。

(七)两种管程的比较

Hoare管程:优先考虑被唤醒线程;执行signal操作的线程放弃锁,等待在管程中(紧急等待队列中);被唤醒进程得到管程的锁;执行signal操作的线程之后得到锁继续运行;

Mesa管程:让两个线程竞争管程的锁;动态调整每个进程获得管程锁的优先级;signal(x):线程在发出signal后释放锁,两个线程同时竞争该锁,谁获得谁先执行。

四、同步机制的实现例子

(一)linux中的同步机制

linux中实现了常见的大多数各种机制,作为亮点的话,就是自旋锁了,所谓自旋锁就是名字比较D,实际上就是忙等资源,因为他们觉得切换进程的开销比忙等要大,尤其是多核系统中。传统的自旋锁会导致死锁,改进版的排队自旋锁解决了这个问题,其来源是银行叫号系统。

(二)Pthread中的同步机制

POSIX中同步机制就比较传统了,实现的是最基本的信号量和锁机制,具体的话可以参看pthread函数列表。

阅读(1143) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册