Liuye Notebook
0%

操作系统原理-同步机制1

发表于 更新于 分类于 ， 阅读次数： Valine：

阅读更多

1 程序并发执行

并发是所有问题产生的基础，同时并发是操作系统设计的基础

2 进程互斥

两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序

由于各进程要求使用共享资源（变量、文件等），而这些资源需要排他性使用各进程之间竞争使用这些资源——这一关系称为进程互斥

  • 临界资源 critical resource：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量
  • 临界区(互斥区) critical section(region)：各个进程中对某个临界资源（共享变量）实施操作的程序片段

临界区的使用原则

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

fig1

实现进程互斥的方案

  • 软件方案
    • Dekker解法、Peterson解法
  • 硬件方案
    • 屏蔽中断、TSL(XCHG)指令

3 进程互斥的软件解决方案

3.1 错误的解法

P

1
2
3
4
5
6
...
pturn = true;
while (qturn) ;
临界区
pturn = false;
...

Q

1
2
3
4
5
6
...
qturn = true;
while (pturn) ;
临界区
qturn = false;
...

如果进程P在执行完pturn = true;后时间片用完，且进程Q在执行完qturn = true;后时间片用完，那么之后P和Q将永远无法退出while循环了

3.2 DEKKER算法

DEKKER算法对上面那种错误的解法进行了改进，避免两个进程同时都无法退出while循环

P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
...
pturn = true;
while (qturn) {
    //进入while循环内部，此时说明进程Q已经执行过qturn = true;了
    //如果进程Q尚未修改tun的值，可能Q也卡在循环里面，那么此时需要放行进程Q，使得Q能够退出while循环
    if (turn == 2) {
        pturn = false;//放行进程Q
        while (turn == 2);//自旋等待Q进入临界区
        pturn = true;//此时Q已经进临界区，因此可以将pturn重新赋值为true
    }
}
临界区
turn = 2;
pturn = false;
...

Q

1
2
3
4
5
6
7
8
9
10
11
12
13
...
qturn = true;
while (pturn) {
    if (turn == 1) {
        qturn = false;
        while (turn == 1);
        qturn = true;
    }
}
临界区
turn = 1;
qturn = false;
...

3.3 PETERSON算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define FALSE 0
#define TRUE 1
#define N 2 //进程的个数
int turn; //轮到谁？
int interested[N];
//兴趣数组，初始值均为FALSE
void enter_region ( int process) //process = 0 或 1
{ 
    int other = 1 - process;//另外一个进程的进程号
    interested[process] = TRUE; //表明本进程感兴趣
    turn = process;//设置标志位
    while( turn == process && interested[other] == TRUE); //最有意思的一句
}

void leave_region ( int process)
{
    interested[process] = FALSE;
    //本进程已离开临界区
}

现在我们来分析一下while( turn == process && interested[other] == TRUE);这个while循环条件的作用

  1. interested[other] == TRUE这个条件不满足，说明并没有发生竞争，只需要放行当前进程即可
  2. interested[other] == TRUE这个条件如果在两个进程中都成立，说明两个进程存在竞争，那么接下来由turn的值来确定竞争的成功或失败。这里用的是turn == process这个条件，即阻塞后修改turn变量的进程

4 进程互斥的硬件解决方案

4.1 硬件解法1-中断屏蔽

开关中断指令

1
2
3
执行“关中断”指令
临界区操作
执行“开中断”指令

优缺点：

  • 简单，高效
  • 代价高，限制CPU并发能力（临界区大小）
  • 不适用于多处理器
  • 适用于操作系统本身，不适于用户进程

4.2 硬件解法2-测试并加锁指令

TSL指令是一种需要硬件支持的方案。许多计算机，特别是那些为多处理机设计的计算机，都有一条指令叫做测试并上锁(TSL)

1
TSL RX，LOCK

这条指令的含义是，读取内存单元LOCK中的内容到寄存器RX中，并且为内存单元LOCK重新设置一个非0值。TSL指令的操作被设计为不可分的，也就是说，整个读写操作都完成之前，其他进程是没办法访问LOCK这个内存单元的。这一点是通过锁定内存总线（lock memory bus）来实现的。

1
2
3
4
5
6
7
8
9
enter_region
    TSL REGISTER, LOCK //复制锁到寄存器，并将锁置1
    CMP REGISTER, #0 //判断寄存器内容是否为0
    JNE enter_region //若不是0，说明已经有人上锁了，此时需要自旋等待，跳转到enter_region
    RET //返回调用者，进入临界区

leave_region
    MOVE LOCK, #0 //在锁中置0
    RET //返回调用者

4.3 硬件解法3-交换指令

XCHG指令交换两个寄存器，或者寄存器和内存变量的内容，且保证操作的原子性

1
2
3
4
5
6
7
8
9
10
enter_region
    MOVE REGISTER, #1 //给寄存器置1
    XCHG REGISTER, LOCK //交换寄存器与锁变量的内容，反正无论如何LOCK的值都要设置为1（原来是0，那么加锁成功，设置为1；原来为1，那么继续等待，仍然是1）
    CMP REGISTER, #0 //判断寄存器内容是否是0
    JNE enter_region //若不是0，跳转到enter_region
    RET //返回调用者，进入临界区

leave_region
    MOVE LOCK, #0 //将锁变量置0
    RET //返回调用者

5 进程同步

进程同步：synchronization。指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体地说，一个进程运行到某一点时，要求另一伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态

5.1 生产者消费者问题

问题描述：

  • 一个或多个生产者生产某种类型的数据放置在缓冲区中
  • 有消费者从缓冲区中取数据，每次取一项
  • 只能有一个生产者或消费者对缓冲区进行操作

要解决的问题：

  • 当缓冲区已满时，生产者不会继续向其中添加数据
  • 当缓冲区为空时，消费者不会从中移走数据

fig2

6 信号量及P、V操作

什么是信号量

  • 一个特殊变量

  • 用于进程间传递信息的一个整数值

  • 定义如下：

  • struc semaphore
    {
    int count;
    queueType queue;
    }

  • 信号量说明：semaphore s;

  • 对信号量可以实施的操作：初始化、P和V（P、V分别是荷兰语的test(proberen)和increment(verhogen)）

6.1 PV操作的定义

PV操作必须是原语（原子性）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
P(s)
{
    s.count --;
    if (s.count < 0)
    {
        该进程状态置为阻塞状态
        将该进程插入相应的等待队列s.queue末尾
        重新调度
    }
}

V(s)
{
    s.count ++;
    if (s.count < = 0)
    {
        唤醒相应等待队列s.queue中等待的一个进程
        改变其状态为就绪态，并将其插入就绪队列
    }
}

6.2 用PV操作解决进程间互斥问题

具体的流程如下

  1. 分析并发进程的关键活动，划定临界区
  2. 设置信号量 mutex，初值为1
  3. 在临界区前实施 P(mutex)
  4. 在临界区之后实施 V(mutex)

7 生产者消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define N 100 /* 缓冲区个数 */
typedef int semaphore; /* 信号量是一种特殊的整型数据 */
semaphore mutex =1; /* 互斥信号量：控制对临界区的访问 */
semaphore empty =N; /* 空缓冲区个数 */
semaphore full = 0; /* 满缓冲区个数 */

void producer(void) {
    int item;
    while(TRUE) {
        item=produce_item();
        P(&empty);
        P(&mutex);
        insert_item(item);
        V(&mutex);
        V(&full);
    }
}

void consumer(void)
{ 
    int item;
    while(TRUE) {
        P(&full);
        P(&mutex);
        item=remove_item();
        V(&mutex);
        V(&empty);
        consume_item(item);
    }
}

交换过两个P操作的顺序可能造成死锁

8 读写者问题

问题描述：

  • 多个进程共享一个数据区，这些进程分为两组：
  • 读者进程：只读数据区中的数据
  • 写者进程：只往数据区写数据

要求满足条件：

  • 允许多个读者同时执行读操作
  • 不允许多个写者同时操作
  • 不允许读者、写者同时操作

8.1 第一类读写者问题：读者优先

如果读者执行：

  • 无其他读者、写者，该读者可以读
  • 若已有写者等，但有其他读者正在读，则该读者也可以读
  • 若有写者正在写，该读者必须等

如果写者执行：

  • 无其他读者、写者，该写者可以写
  • 若有读者正在读，该写者等待
  • 若有其他写者正在写，该写者等待

8.2 第一类读写者问题的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void reader(void)
{
    while (TRUE) {
    P(mutex);//保护rc变量的写互斥
    rc = rc + 1;
    if (rc == 1) P (w);
    V(mutex);
    读操作
    P(mutex);
    rc = rc - 1;
    if (rc == 0) V(w);
    V(mutex);
    其他操作
}

void writer(void)
{
    while (TRUE) {
    P(w);
    写操作
    V(w);
    }
}

9 参考

  • 《MOOC-操作系统原理-陈向群》