操作系统基础-进程同步(5)

2018-12-19 15:44:32 george518 ...

一、进程同步的概念

在多道程序环境下,系统中各进程以不可预测的速度向前推进,进程的异步性会造成了结果的不可再现性。为防止这种现象,异步的进程间推进受到二种限制:

资源共享关系

像打印机这类资源一次只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机、磁带机等,软件在消息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘等资源,它允许进程间共享,即可交替使用,所以它称为共享资源,而临界资源又称独享资源。
多进程之间如果共享资源,例如各进程争用一台打印机,这时各进程使用这台打印机时有一定的限制。每次只允许一个进程使用一段时间打印机,等该进程使用完毕后再将打印机分配给其它进程。这种使用原则称为互斥使用。

相互合作关系

在某些进程之间还存在合作关系,例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行,由于这三个进程间存在着相互合作的关系,即先输入再计算、最后再打印的关系,所以这三个进程在并发执行时推进序列受到限制,要保证其合作关系正确,进程间这种关系称为同步关系。

二、多进程之间的控制问题

  • 互斥( mutual exclusion )指多个进程不能同时使用同一个资源;
  • 死锁( deadlock )指多个进程互不相让,都得不到足够的资源;
  • 饥饿( starvation )指一个进程一直得不到资源(其他进程可能轮流占用资源)。
    进程在并发执行时为了保证结果的可再现性,各进程执行序列必须加以限制以保证互斥地使用临界资源,相互合作完成任务。多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。

三、进程同步应该遵循的四条原则

空闲让进

当无进程进入临界区时,相应的临界资源处于空闲状态,因而允许一个请求进入临界区的进程立即进入自己的临界区。

忙则等待

当已有进程进入自己的临界区时,即相应的临界资源正被访问,因而其它试图进入临界区的进程必须等待,以保证进程互斥地访问临界资源。

有限等待

对要求访问临界资源的进程,应保证进程能在有限时间进入临界区,以免陷入“饥饿”状态。

让权等待

当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入忙等。

四、硬件技术实现进程同步机制

1、提高临界区代码执行中断优先级(IRQL)

这种方法在UNIX和Windows 2000中都使用,它是在单机系统中有效地实现互斥的一种方法。因为在传统操作系统中,打断进程对临界区代码的执行只有中断请求、中断一旦被接受,系统就有可能调用其它进程进入临界区,并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽了其它中断,保证了临界段的执行不被打断,从而实现了互斥。

2、检测和设置(TS)硬件指令

许多大型机(如IBM370等)和微型机(如Intel x86等)中都提供了专用的硬件指令,这些指令全部允许对一个字中的内容进行检测和修正,或交换两个字的内容。特别要指出的是这些操作都是在一个存储周期中完成,或者说由一条指令来完成,用这些指令就可以解决临界区问题了。因为临界区问题在多道环境中之所以存在,是由于多个进程共同访问、修改同一公用变量。用这些硬件指令可以简单有效地实现互斥。其方法是为每个临界段或其它互斥资源设置一个布尔变量,例如称为lock。当其值为false则临界区末被使用,反之则说明正有进程在临界区中执行。

3、自旋锁

Windows2000 内核用来达到多处理器互斥的机制“自旋锁”,它类同于TS指令机制。自旋锁是一个与共用数据结构有关的锁定机制。在每个进程进入自己的临界区之前,内核必须获得与所保护的DPC(延迟过程调用)队列有关的自旋锁。如果自旋锁非空,内核将一直尝试得到锁直到成功。因为内核(处理器也如此)被保持在过渡状态“旋转”,直到它获得锁,“自旋锁”由此而得名。
自旋锁像它们所保护的数据结构一样,储存在共用内存中。为了速度和使用任何在处理器体系下提供的锁定机构,获取和释放自旋锁的代码是用汇编语言写的。例如在Intel处理器上,Windows2000使用了一个只在486处理器或更高处理器上运行的指令。
当线程试图获得自旋锁时,在处理器上所有其它工作将终止。因此拥有自旋锁的线程永远不会被抢先,但允许它继续执行以便使它尽快把锁释放。内核对于使用自旋锁十分小心,当它拥有自旋锁时,它执行的指令数将减至最少。

五、信号量机制

1965年,荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具,在长期广泛的应用中,信号量机制又得到了很大的发展,它从整型信号量机制发展到记录型信号量机制,进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。

信号量按联系进程的关系分类:
  • 公用信号量(互斥信号量)
    • 它为一组需互斥共享临界资源的并发进程而设置,它代表永久性的共享的临界资源,每个进程均可对它施加P、V操作,即都可申请和释放该临界资源,其初始值置为1。
  • 专用信号量(同步信号量)
    • 它为一组需同步协作完成任务的并发进程而设置,它代表消耗性的专用资源,只有拥有该资源的进程才能对它施加P操作(即可申请资源),而由其合作进程对它施加V操作(即释放资源)。
具体分类
1、整型信号量 整型信号量

最初由Dijkstra把整型信号量定义为一个整型量,除初始化外,仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为:
S .value>0 ;表示可供使用资源数
S .value=0 ;表示资源已被占用,无其它进程等待。
S .value<0(=-n) ;表示资源已被占用,还有n个进程因等待资源而阻塞。

2、记录型信号量

在整型信号量机制中的wait操作,只要是信号量S≤0, 就会不断地测试。因此,该机制并未遵循“让权等待”的准则, 而是使进程处于“忙等”的状态。记录型信号量机制,则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后,又会出现多个进程等待访问同一临界资源的情况。为此,在信号量机制中,除了需要一个用于代表资源数目的整型变量value外,还应增加一个进程链表L,用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。
在记录型信号量机制中,S.value的初值表示系统中某类资源的数目, 因而又称为资源信号量,对它的每次wait操作,意味着进程请求一个单位的该类资源,因此描述为S.value=S.value-1; 当S.value<0时,表示该类资源已分配完毕,因此进程应调用block原语,进行自我阻塞,放弃处理机,并插入到信号量链表S.L中。可见,该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作,表示执行进程释放一个单位资源,故S.value=S.value+1操作表示资源数目加1。 若加1后仍是S.value≤0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故还应调用wakeup原语,将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量。

3、AND型信号量

在两个进程中都要包含两个对Dmutex和Emutex的操作。 AND同步机制的基本思想是:将进程在整个运行过程中需要的所有资源,一次性全部地分配给进程,待进程使用完后再一起释放。只要尚有一个资源未能分配给进程,其它所有可能为之分配的资源,也不分配给他。亦即,对若干个临界资源的分配,采取原子操作方式:要么全部分配到进程,要么一个也不分配。 由死锁理论可知,这样就可避免上述死锁情况的发生。为此,在wait操作中,增加了一个“AND”条件,故称为AND同步,或称为同时wait操作, 即Swait(Simultaneous wait)。

六、利用信号量实现进程互斥

为使多个进程能互斥地访问某临界资源,只需为该资源设置一个互斥信号量mutex,并设其初值为1,并规定每个进程在进入临界区CS前必须申请资源,即对互斥信号量mutex施加P操作,在退出临界区CS后必须释放资源,即对互斥信号量mutex施加V操作;即将各进程的临界区CS置于P(mutex)和V(mutex)操作之间。

参考
https://blog.csdn.net/xiaokang123456kao/article/details/73773474

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。