8、同步互斥机制1(进程并发执行)(操作系统笔记)

一、进程并发执行

1.1问题的提出

并发是所有问题产生的基础,也是操作系统设计的基础。

1.2从进程的特征看待并发问题

  • 并发
    进程的执行是间断性
    进程的相对执行速度是不可预测的
  • 共享
    进程/线程之间的制约性
  • 不确定性
    进程执行的结果与其执行的相对速度有关,是不确定的。

二、进程互斥

2.1 竞争条件

下面看一个打印机的例子:

1

说明:在打印的时候需要维护上面这样一个打印的目录,有一个打印机的守护进程管理此目录,其中存放了所有要打印文件的信息,当缓冲区中有某个文件的文件名时,打印机就工作。这里我们需要使用in来表示缓冲区中哪个槽是空的。加入进程A、B都需要打印了,进程A首先独到了in=7,之后应该把in的值更新为8才对,但是在更新之前进程A被切换下cpu,同时进程B上了cpu,也要读取in=7,于是两个进程都将要打印的文件信息送到了7这个单元槽,于是就将进程A的文件信息给覆盖掉了,于是进程A就再也得不到自己所要的结果了。

竞争条件:两个或多个进程读写某些共享数据,而最后的结果取决于进程的运行的精确时序。

2.2 进程互斥

  • 由于各进程要求使用共享资源(变量、文件等),而这些资源需要排他性使用。个进程之间竞争使用这些资源,这一关系称为进程互斥。
  • 临界资源:系统中某些资源一次只允许一个进程使用,称这样的资源为临界资源或互斥资源或共享变量。
  • 临界区(互斥区):各个进程中对某个临界资源实施操作的程序片段。

2.3 临界区(互斥区)的使用原则

2
  • 没有进程在临界区时,想进入临界区的进程可进入
  • 不允许两个进程同时处于其临界区中
  • 临界区外运行的进程不得阻塞其他进程进入临界区
  • 不得使进程无限期等待进入临界区

2.4 实现进程互斥的方案

  • 软件方案
    Dekker解法、Peterson解法

  • 硬件方案
    屏蔽中断、TSL(XCHG)指令

2.4.1 软件解法1

3

说明:如果freetrue表示有进程在临界区,否则就没有进程在临界区,初值是false。假设进程P先上cpu,此时free初值为false,于是循环就结束了,此时如果P被切换下cpu,而进程Q上了cpu,判断之后free还是false,然后将free设置为true进入临界区;而此时如果Q被切换下cpuP上了cpu,此时Pfree还是设置为true后也进入临界区,于是在同一时刻这两个进程都在临界区中,就没有满足临界区的使用原则,是一个错误的解法。
解决: 如果我们将最开始的两条语句加锁,不允许在其中间中断。于是我们看到如果Pfree设置为true之后,Q是不能进入到临界区的,其一直处于while循环中。

2.4.2 软件解法2

4

说明:如果turnfalse,则P是不能进入临界区的,而Q恰恰相反,如果turntrue,则其也是不能进入临界区的。

2.4.3 软件解法3

5

说明:这里设置了两个标志位。当两个标志位的值是一样的时候就会让两个进程都不能进入临界区,这就会导致after you问题。

2.4.4 DEKKER算法

6

说明:在上个解法基础上增加了一个turn标志,用来解决after you问题。但是在最外层while内部还有一个while进行判断,用来判断是不是轮到自己执行了,一直循环直到其时间片被用完下cpu,这里有浪费的。如果都想进临界区,当turn1时,Q就让出cpu,否则进入临界区。如果一直为1,则Q就一直在内部循环,即一直不能进入临界区。

2.4.5 PETERSON算法

7

说明:在上面的算法中由于内部循环会导致浪费。任何一个进程要想进入临界区,首先执行函数enter_region(i),其中参数是进程号,如果运行完这个函数,则进入临界区,否则在函数内部等待。turn是一个共享的变量,如果两个进程都想进临界区,那么turn的值是后面进程的,于是while循环条件不成立,则先给turn赋值的进程先进临界区。

2.4.6 进程互斥的硬件解决方案1(中断屏蔽方法)

利用开关中断指令。即在进入临界区之前我们先把中断屏蔽掉,然后进入临界区进行相应的操作,出临界区时就开启中断(允许中断)。

  • 简单、高效
  • 代价高,限制cpu并发能力(临界区大小)
  • 不适用于多处理器
  • 适用与操作系统本身,不适于用户进程

2.4.7 进程互斥的硬件解决方案2(“测试加锁”指令)

8

说明:在这个指令中lock变量是一个共享变量,如果lock=0,则任何进程都可以将其置1,并进入临界区。如果lock=1,标明有其他进程在临界区中,不能进入临界区。如图所示,如果一个进程想进入临界区,则先复制lock的值并将其置为1,如果其为非零,则进入临界区,出临界区的时候将lock置为0。其本质是将总线锁住。而其中也有一个循环检测的过程,也是有点浪费时间的。

2.4.8 进程互斥的硬件解决方案3(“交换”指令)

9

说明:首先给寄存器中置1,然后交换锁变量和寄存器中的值,之后再判断寄存器中的值是否为零,如果是零,标明临界区中没有进程,可以进入。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容