男孩喜欢上了女孩,他向她表白,女孩拒绝了,她说:我整整比你大一岁。男孩说:我1个月时,你13个月。你是我的13倍。我2个月时,你14个月。你是我的7倍。我一岁时,你两岁,你是我的两倍。只要你愿意和我永远在一起,我们总在慢慢接近。
多美好的故事,居然被数学老师用来讲极限。
1、 并发进程之间的相互制约关系
a) 直接制约关系:若某一个进程收不到另一个进程给它提供的必要信息就不能继续运行下去,这种情况表明了两个进程之间在某些点上要交换信息,相互交流运行情况,这种制约关系是“进程-进程”
b) 间接制约关系:若某个进程要求使用某一资源,而该资源正被另外一个进程使用,并且这个资源不允许两个进程同时使用,那么该进程只好等待占用资源的进程释放资源后才能使用,这种制约关系是“进程-资源-进程”
2、 进程同步<低级进程通信方式>的定义:进程有上述的相互依赖又相互制约,相互合作又相互竞争的关系,意味着进程之间需要进行通信,主要表现为同步和互斥。进程同步是一种进程间的通信方式,于进程同步交换的信息较少且通信效率低,因此称为低级进程通信方式
3、 同步与互斥的基本概念
a) 临界资源与临界区
i. 临界资源的定义:我们把一次仅允许一个进程使用的资源称为临界资源
ii. 临界区的定义:进程中访问临界资源的那段代码称为临界区,临界段
iii. 临界资源访问的过程:
1. 进入区:为了进入临界区使用临界资源,进程在进入区要检查是否可以进入临界区,可以进入,设置临界区为“正在访问临界区”标识
2. 临界区:进程中访问临界资源的那段代码;
3. 退出区:清除“正在访问临界区”标识的部分;
4. 剩余区:除了以上三个区以外的部分内容。
iv. 进入临界区的进程的条件
1. 空闲让进:当没有进程处于临界区时,可以允许一个请求进入临界区
2. 忙则等待:当已有进程进入临界区,其他进程试图进入临界区必须等待;
3. 有限等待:要进入临界区的进程,应保证在有限时间内进入自己的临界区;
4. 让权等待:当进程不能进入临界区,应释放处理机。
b) 进程同步与互斥
i. 进程同步:多个相互合作的进程在一些关键点上可能需要互相等待或互相交换信息,这种相互制约关系称为进程同步。比如一个计算进程和一个打印进程,计算进程必须是在打印进程之前。
ii. 进程互斥:当一个进程正在使用某资源时,其他希望使用该资源的进程必须等待,当该进程用完资源并释放后,才允许其他进程去访问此资源,我们称进程之间的这种相互制约关系为进程互斥。比如两个计算进程都需要打印进程,这两个计算进程必须互斥
4、 进程互斥的实现方法
a) 互斥算法<软件实现进程互斥存在局限性,很少用了>:把临界资源状态的检查和修改没有作为一个整体来实现。缺点是算法太复杂、效率不高且不直观。
i. 算法1:设置一个公用整型变量turn,用来指示允许进入临界区的进程标识。若turn为0,则允许进程p0进入临界区,否则循环检查该变量,直到turn变为本进程标识,在退出区,修改允许进入进程的标识turn为1。
ii. 算法2:设置标识数组flag[]表示进程是否在临界区中执行,初值均为假。再每个进程访问临界资源之前,先检查另一个进程是否在临界区,如果不在,则修改本进程的标识为真并进入临界区,在退出区修改本进程临界区标识为假。
iii. 算法3:设置标识数组flag[]表示进程是否希望进入临界区。在每个进程访问临界资源之前,先将自己的标识设置为真,表示希望进入临界区,然后再检查另一个进程,若另一个进程为真,则本进程等待,否则进入临界区。
iv. 算法4:是算法3和算法1的结合。标识数组flag[]表示进程是否希望进入临界区或者是否正在临界区中执行,此外还设置了一个turn变量,用来表示允许进入临界区的进程标识。
b) 硬件方法:用一条指令完成临界资源状态的检查和修改。缺点是不能实现让权等待。
i. 禁止中断方法:当一个进程正在处理机上执行其临界区代码时,要防止其他进程再进入它们的临界区访问,最简单直接的方法是禁止一切中断发生,或称之为关中断
ii. 硬件指令方法:把标志的检查和修改操作结合成一个不可分割的整体,具体优点有:使用范围广、简单、支持多个临界区。具体缺点:耗费处理机时间、可能导致进程饥饿现象(有的进程一直未能进入临界区)
c) 锁机制:通过原语保证资源状态检查和修改作为一个整体来执行。缺点是不能实现让权等待。
i. 锁是一个代表资源状态的变量,通常用0表示资源可用(开锁),用1表示资源已被占用(关锁),利用上锁原语和开锁原语解决进程互斥的问题
d) 信号量:是在多个相互合作的进程之间使用简单的信号来同步。
i. 定义:信号量表示资源的实体,它由两个成员(s,q)构成。除信号量的初值外,信号量的值仅能由P操作(Wait操作)和V操作(Signal操作)改变
ii. 其中s是一个具有非负初值的整型变量,整型变量s表示系统中某类资源的使用情况,当值大于0时,表示系统中当前可用资源的数目,当值小于0时,其绝对值表示系统中因请求该类资源而阻塞等待的进程数目
iii. q是一个初始状态为空的队列
iv. P和V操作都作为原语来实现的,在执行的时候作为一个整体,不能分割。
v. P操作完成的功能:先执行s=s-1,若s>=0则进程需运行;若s<0则阻塞该进程,并将它插入该信号量的等待队列中
vi. V操作完成的功能:先执行s=s+1,若s>0则进程继续执行;若s<=0则从该信号量等待队列中移除第一个进程,使其变为就绪状态并插入就绪队列。
e) 管程:为每个共享资源设立一个“秘书”来管理对信号量的访问,一切来访者都要通过秘书,而秘书每次仅允许一个来访者(进程)访问共享资源,管程定义了一个数据结构和能为并发进程所执行的一组操作,这组操作能同步进程和改变管程中的数据。
i. 管程的组成
1. 局部于管程的共享数据结构说明
2. 对这些数据结构进行操作的一组过程
3. 对这些数据结构设置初值的语句组成
ii. 管程的特性
1. 局部于管程的数据只能被局部于管程内的过程所访问
2. 一个进程只能通过通用管程内的过程才能进入管程访问共享数据
3. 每次仅允许一个进程在管程内执行某个内部过程。
5、 同步的经典问题
a) 生产者-消费者问题:描述了一组生产者向一组消费者提供产品,生产者和消费者共享一个仓库
b) 读者-写者问题:多个进程对一个共享资源进行读写操作的问题
c) 哲学家进餐问题:多个进程对一个资源进行使用的问题
零测试