进程并发性是指一组进程的执行在时间上是重叠的。所谓时间重叠是指一个进程执行第一条指令是在另一个进程执行完最后一条指令之前开始的。从宏观上来看,并发性反映一个时间段内有几个进程都处于运行态但尚未结束的状态。从微观上来看,任一时刻仅有一个进程的一个操作在处理器上执行。
现代计算机硬部件能同时进行工作,程序的编制决定不同硬部件并行工作的能力。好的程序能够充分发挥设备的并行工作能力,从而提高计算机系统的效率。
一个程序被分成若干可同时执行的小程序的程序设计方法称为并发程序设计。多个进程相互协作、相互制约。
并发进程可能是无关的,也可能是交互的,无关的并发进程是指它们分别在不同的变量集上操作,一个进程的执行与其他并发进程的进展无关。交互的进程共享某些变量,一个进程的执行可能会影响其他进程的执行结果,因此交互的并发进程之间具有制约关系,它们之间的执行必须有所控制,否则将会出现不正确的结果。
时间无关:多个进程执行的相对次序不影响最终结果。
并发进程的无关性是进程的执行与时间无关的一个充分条件,这由Bernstein提出,假设:
R(p1);程序p1执行期间所引用的变量集。
W(P1);程序p1执行期间所改变的变量集。
若两个进程能满足Bernstein条件,
R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)=φ,则称并发进程的执行与时间无关。
并发程序设计实在多道程序设计的基础上发展起来的,它可以充分发挥硬件的并行性,消除处理器和设备的互等现象,提高系统效率。计算机硬部件能并发工作仅具备提高效率的可能性,并行工作的实现还需要软件技术来发挥,这种技术就是并发程序设计。
两个交互的并发进程,一个进程对另一个进程的影响往往是不可预期的,甚至是无法再现,因为它们执行的相对速度不可预测,可以出现与时间有关的各种错误。有两种形式:一结果不唯一。二永远等待。
多道程序设计中的额进程存在两种基本的关系:竞争和协作。线程的关系也类似。
竞争又称互斥,是指若干进程因相互争夺独占资源而产生的竞争制约关系。由于竞争资源的独立进程不交换信息,一个进程的执行可能影响到竞争资源的其他进程。如果有一个正在访问独占资源,另一个进程不得不等待,极端的情况下,被阻塞的进程永远得不到访问权。资源竞争会引发两个问题:一是死锁:每个进程都获得部分资源而不释放,同时还需要其他进程所占有的资源,导致相互等待的现象。二是饥饿,一个进程由于其他进程总是优先于它,而被无限期拖延,不能执行。
协作又称同步,是指为完成共同任务的并发进程,基于某个条件来协调其活动,因为需要在某些位置上排定执行的而等待、传递信号或消息所产生的协作制约关系。当一个进程到达关键点后,在尚未得到伙伴进程发来的消息或信号之前阻塞自己,当协作者发来信息号或消息后方被唤醒并继续执行。
进程互斥关系是一种特殊的进程同步关系,即逐次使用互斥共享资源,也是对进程使用资源的次序的一种协调。信号量、锁、管程、消息及其他软硬件机制都可被用作进程和线程请求和释放的资源。多数同步机制主要用于内核层。
能解决进程同步问题的技术一定可以解决进程互斥。
并发进程中与共享变量有关的程序段称为临界区(Critical section)。共享变量所代表的资源成为临界资源。与共享变量有关的临界区分散在各个并发进程的程序段中,当一个进程在临界区执行时,就会阻止另一个进程进入相同的临界区。各进程对共享变量的访问是互斥的。
临界区是一段程序,针对每个进程而言,每个进程都有自己的临界区,互不相关。
临界区调度的原则:互斥使用,有空让进,忙则等待,优先等待,择一而入,算法可行。
著名的生产者消费者问题是计算机操作系统中并发进程内在关系的一种抽象,是典型的进程同步问题。
有n个生产者和m个消费者,在具有k个单位缓冲区内操作。Pi,ci都是并发进程,只要缓冲区未满,生产者进程pi就会不断生产产品到缓冲区。只要缓冲区非空,消费者进程就不断从缓冲区取产品。生产者和消费者共享缓冲区,但是出现错误的结果并不是因为此,而是它们访问缓冲区的速度不匹配。我们需要调整并发进程的推进速度,并发进程进程的这种制约关系称为进程同步。
当消费者发现缓冲区空时,即count==0后被调度程序暂停执行。生产者进程被调度往缓冲区内添加产品,当它发现此时counter==1,想当然的认为消费者进程是因为没有产品可取已经被挂起。于是唤醒消费者,由于消费者进程并未睡眠,唤醒信号丢失。当调度程序调度消费者进程执行时,由于已经判断过缓冲区为空,消费者进程睡眠。此后生产者不断往缓冲区添加产品,直到添加满后睡眠。两进程都在睡眠,造成所有进程永远处于睡眠状态。
最常用的同步机制是信号量、pv操作、管程和消息传递。
两个或更多进程通过信号量展开交互。一个进程在某一点上被迫停止执行直至接收到某一信号。p,v操作用来发送和接收信号量。
信号量在操作系统中主要用于封锁临界区,进程同步及维护资源计数。
信号量semaphore是一个结构体,
typedef struct semaphore { int value;//信号量值。 struct pcb*list;//信号量队列指针。存储pcb。 }; |
value为整型变量,初始化时赋值,list是等待使用此信号量的进程队列的头指针,初始状态为空队列 。
P(s):将信号量value值减一。若结果小于0,则执行此操作的进程被挂起,排入与此信号量有关的list所指的队列中。若结果仍大于0,则该进程继续执行 。
V(s):将信号量的值加一。若结果不大于0(说明有进程在等待),则执行此操作的进程从信号量s有关的队列中释放一个进程,使其转为就绪态。