多线程冲突了怎么办
2023-12-18 19:08:05 #操作系统 #进程管理

1.竞争与协作

1.1.互斥的概念

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码成为临界区

临界区是访问共享资源的代码片段，一定不能给多线程同时执行

我们希望这段代码是互斥的，也就是说保证一个线程 在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程

image-20231217151039196

1.2.同步的概念

例：线程1负责读入数据，线程2负责处理数据，这两个线程是相互合作，相互依赖的。线程2没有收到线程1的唤醒通知是，就是一直阻塞等待，当线程1读完数据需要把数据传给线程2时，线程1会唤醒线程2，并把数据交给线程2处理

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与胡同信息称为进程/线程同步

1.3.概念不同

解释

  • 同步：操作A应该在操作B之前执行
  • 互斥：操作A和操作B不能在同一时刻执行

2.互斥与同步的实现和使用

为了实现进程/线程间正确的协作，操作系统必须提供进程协作的措施和方法，主要的方法有两种：

  • 锁：加锁，解锁操作
  • 信号量：P，V操作

这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步

2.1.锁

使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题

任何相进入临界区的线程，必须限制性加锁操作，若加锁操作顺利通过，则线程可进入临界区，在完成对临界资源的访问后再执行解锁操作，以释放临界资源

image-20231217154354255

根据锁的实现不同，可以分为忙等待锁和无忙等待锁

  • 忙等待锁：当获取不到锁时，线程就会一直while循环，不做任何事情，所以就被称为忙等待锁，也被称为自旋锁
  • 无等待锁：当没所获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把cpu让给其他线程执行

2.2.信号量

2.2.1.概述

信号量是操作系统提供的一种协调共享资源访问的方法

通常信号量表示资源的数量，对应的变量是一个整形（sem）变量

另外，还有两个原子操作的系统调用函数来控制信号量，分别是：

  • P操作：将sem减1,相减后，如果sem < 0,则进程/线程进入阻塞等待，否则继续，表明P操作可能会阻塞
  • V操作：将sem加1,相加后，如果sem <= 0 ,唤醒一个等待中的线程/进程，表明V操作不会阻塞

P操作是用在进入临界区之前，V操作是用在离开临界区之后，这两个操作是必须成对出现的

2.2.2.使用

信号量不仅可以实现临界区的互斥访问控制，还可以线程间的事件同步

信号量实现临界区的互斥访问

为每类共享资源设置一个信号量s,其初值为1，表示临界资源未被占用

只要把临界区设置于P(s)和V(s)之间，即可实现进程/线程互斥：

image-20231217161145144

此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在完成对临界资源的访问后再执行 V 操作。由于互斥信号量的初始值为 1，故在第一个线程执行 P 操作后 s 值变为 0，表示临界资源为空闲，可分配给该线程，使之进入临界区。

信号量实现事件同步

同步的方式是设置一个信号量，其初值为 0。

我们举例「吃饭-做饭」同步的例子，用代码的方式实现一下：

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
semaphore s1 = 0; //表示不需要吃饭
semaphore s2 = 0; //表示饭还没做完

//儿子线程函数
void son()
{
    while(TRUE)
    {
        肚子饿;
        V(s1); //叫妈妈做饭
        P(s2); //等待妈妈做饭
        吃饭;
    }
}

//妈妈线程函数
void mon()
{
    while(TRUE)
    {
        P(s1); //需不需要做饭
        做饭;
        V(s2); //做晚饭，通知儿子吃饭
    }
}

妈妈一开始询问儿子要不要做饭时，执行的是 P(s1) ，相当于询问儿子需不需要吃饭，由于 s1 初始值为 0，此时 s1 变成 -1，表明儿子不需要吃饭，所以妈妈线程就进入等待状态。

当儿子肚子饿时，执行了 V(s1)，使得 s1 信号量从 -1 变成 0，表明此时儿子需要吃饭了，于是就唤醒了阻塞中的妈妈线程，妈妈线程就开始做饭。

接着，儿子线程执行了 P(s2)，相当于询问妈妈饭做完了吗，由于 s2 初始值是 0，则此时 s2 变成 -1，说明妈妈还没做完饭，儿子线程就等待状态。

最后，妈妈终于做完饭了，于是执行 V(s2)，s2 信号量从 -1 变回了 0，于是就唤醒等待中的儿子线程，唤醒后，儿子线程就可以进行吃饭了

2.3.生产者-消费者问题

image-20231217163045153

生产者-消费者问题描述：

  • 生产者在生成数据后，放在一个缓冲区中；
  • 消费者从缓冲区取出数据处理
  • 任何适合，只能有一个生产者或消费者可以访问缓冲区

我们对问题分析可以得出：

  • 任何时刻只能有一个线程操作缓冲区，说明缓冲区是临界代码，需要互斥：
  • 缓冲区空时，消费者必须等待生产者生产数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步

那么我们需要三个信号量，分别是：

  • 互斥信号量mutex：用于互斥访问缓冲区，初始化值为1
  • 资源信号量fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为0（表明缓冲区一开始为空）
  • 资源信号量emptyBuffers：用于是生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为n（缓冲区大小）

具体的代码是实现：

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
semphore mutex = 1;        		//互斥信号量，用于临界区的互斥访问
semphore emptyBuffers = N; 		//表示缓冲区空槽的个数
semphore fullBuffers = 0;  		//表示缓冲区满槽的个数

//生产者线程函数
void producer()
{
    while(TRUE)
    {
        P(emptyBuffers);                //将空槽的个数 - 1;
        P(mutex);
        将生产的数据放入到缓冲区中;
        V(mutex);
        V(fullBuffers);                 //将满槽的个数 + 1;
    }
}

//消费者线程函数
void consumer()
{
    while(TRUE)
    {
        P(fullBuffers);                 //将满槽的个数 - 1;
        P(mutex);
        从缓冲区读取数据;
        V(mutex);
        V(emptyBuffers);                //将空槽的个数 + 1;
    }
}

3.经典同步问题

3.1.哲学家就餐问题

image-20231217170353785

问题描述：

  • 5个老大哥哲学家，围着一张圆桌吃饭
  • 这个桌子只有5个叉子，每两个哲学家之间放一个叉子
  • 哲学家围在一起先思考，思考中途饿了就会想起进餐
  • 这些哲学家需要两个叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐
  • 吃完后，会把两个叉子放回原处，继续思考

如何保证哲学家们动作有序进行，而不会出现永远有人拿不到叉子呢？

方案一：信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define N 5             //哲学家个数
semaphore fork[5];      //信号量初值为1
                        //也就是叉子的个数

void smart_person(int i)        //i 为哲学家编号 0 - 4
{
    while(TRUE)
    {   
        think();                //思考
        P(fork[i]);             //去拿左边的叉子
        P(fork[(i + 1) % N]);   //去拿右边的叉子
        eat();
        V(fork[i]);             //放下左边的叉子
        V(fork[(i + 1) % N]);   //放下右边的叉子
    }
}

方案一看似自然，但是存在一个极端的问题：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了，这样就没有人能够拿到他们右边的叉子，也就是说每一个哲学家都会在 P(fork[(i + 1) % N]);这条语句阻塞了，很明显发生了死锁的现象

方案二：信号量 + 互斥信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define N 5             //哲学家个数
semaphore fork[5];      //信号量初值为1
semaphore mutex;        //互斥信号量，初值为1

void smart_person(int i)        //i 为哲学家编号 0 - 4
{
    while(TRUE)
    {   
        think();                //思考
        P(mutex);               //进入临界区
        P(fork[i]);             //去拿左边的叉子
        P(fork[(i + 1) % N]);   //去拿右边的叉子
        eat();
        V(fork[i]);             //放下左边的叉子
        V(fork[(i + 1) % N]);   //放下右边的叉子
        V(mutex)；               //推出临界区
    }
}

方案二虽然能让哲学家按顺序吃饭，但是每次进餐只能由以为哲学家，而桌面上是有5把叉子，按道理是能可以有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案

方案三：信号量 + 奇偶法

  • 偶数编号的哲学家：先拿左边的叉子后拿右边的叉子
  • 奇数编号的哲学家：先拿右边的叉子后拿左边的叉子
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
#define N 5             //哲学家个数
semaphore fork[5];      //信号量初值为1

void smart_person(int i)        //i 为哲学家编号 0 - 4
{
    while(TRUE)
    {   
        think();                //思考
        
        if( i % 2 == 0)
        {
            P(fork[i]);             //去拿左边的叉子
            P(fork[(i + 1) % N]);   //去拿右边的叉子
        }
        else
        {
            P(fork[(i + 1) % N]);   //去拿右边的叉子
            P(fork[i]);             //去拿左边的叉子
            
        }
     
        eat();
        V(fork[i]);             //放下左边的叉子
        V(fork[(i + 1) % N]);   //放下右边的叉子
    }
}

方案三即不会出现死锁，也可以两人同时进餐；因为相邻的两个人会首先查看两人中间的叉子有没有人拿

方案四：信号量 + 互斥信号量 + state状态数组

在这里再提出另外一种可行的解决方案，我们用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。

那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。

第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：

  • LEFT : ( i + 5 - 1 ) % 5
  • RIGHT : ( i + 1 ) % 5

比如 i 为 2，则 LEFT 为 1，RIGHT 为 3。

具体代码实现如下：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#define N 5                     //哲学家个数
#define LEFT  (i + N - 1) % N   //i的左边邻居编号
#define RIGHT (i + 1) % N       //i的右边邻居编号

#define THINKING 0          //思考状态
#define HUNGER   1          //饥饿状态
#define EATING   2          //进餐状态

int state[N];               //数据记录每个哲学家的状态

semaphore s[5];             //每个哲学家一个信号量，初值0
semaphore mutex;            //信号量初值为1

void test(int i)
{
    //如果 i 号的左边右边哲学家都不是进餐状态，把i号哲学家标记为进餐状态
    if( state[i] == HUNGER &&
        state[LEFT] == THINKING &&
        state[RIGHT] == THINKING )  
    {
        state[i] = EATING   //两把叉子到手，进餐状态
        V[s[i]];            //通知第i哲学家可以进餐了
    }
}

//功能：要么拿到两把叉子，要么被阻塞起来
void take_forks(int i){
    P(mutex);           //进入临界区
    state[i] == HUNGER; //标记处于饥饿状态
    test(i);            //获取叉子
    V(mutex);           //离开临界区
    P(s[i]);            //没有叉子则阻塞，有叉子则继续正常执行
}

//功能：把两把叉子放回原处，并在需要的时候，去唤醒左邻右舍
void put_forks(int i)
{
    P(mutex);           //进入临界区
    state = THINKING;   //标记处于思考状态
    test(LEFT);         //检查左边的左邻右舍是否在进餐，没则唤醒
    test(RIGHT);        //检查右边的左邻右舍是否在进餐，没则唤醒
    V(mutex);           //离开临界区
} 

//哲学家主代码
void smart_person(int i)
{
    while(TRUE)
    {
        think();        //思考
        take_forks(i);  //拿叉子吃饭
        eat();          //吃饭
        put_forks(i);   //吃完放回叉子
    }
}


上面的程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。

方案四同样不会出现死锁，也可以两人同时进餐.

3.2.读者-写者问题

为数据库建立的模型，读者只会读取数据，不会修改数据，而写者既可以读也可以写数据。

读者-写着问题描述：

  • 读-读 允许：同一时刻，允许多个读者同时读
  • 读-写 互斥：没有写者时读者才能读，没有读者时写者才能写
  • 写-写 互斥：没有其他写者时，写者才能写

方案一：信号量 + 读者优先

  • 信号量 wMutex：控制写操作的互斥信号量，初始值为 1 ；
  • 读者计数 rCount：正在进行读操作的读者个数，初始化为 0；
  • 信号量 rCountMutex：控制对 rCount 读者计数器的互斥修改，初始值为 1；
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
31
32
33
34
35
36
37
38
39
40
41
semaphore wMutex;           //控制写操作的互斥信号量,初始值为1
semaphore rCountMutex;      //控制对rCount的互斥修改,初始值为1
int rCount = 0;             //正在进行读数据的读者个数, 初始值为0

//写者
void writer()
{
    while(TRUE)
    {
        P(wMutex);          //进入临界区
        write();            //写数据
        V(wMutex);;         //离开临界区
    }
}

//读者
void reader()
{
    while(TRUE)
    {
        P(rCountMutex);     //进入临界区
        if(rCount == 0)     
        {
            P(wMutex);      //如果有写者,则阻塞写者
        }
        rCount ++;          //读者加一
        V(rCountMutex);     //离开临界区
         
        read();             //读数据
            
        P(rCountMutex);     //进入临界区
        rCount --;          //读者减一
        if(rCount == 0)
        {
            V(wMutex);      //最后一个读者离开了，则唤醒写者
        }
        V(rCountMutex);     //离开临界区
    }
}


总结：

  • 读者优先的策略，因为只要有读者正在读的状态，后来的读者都可以直接进入
  • 如果读者持续不断的进入，则写者将会处于饥饿状态

方案二：信号量 + 写者优先

  • 信号量 wMutex：控制写者进入的互斥信号量，初始值为 1；
  • 信号量 rCount：记录读者数量，初始值为0；
  • 信号量 rCountMutex: 控制对rCount的互斥修改，初始值为 1；
  • 信号量 wDataMutex：控制写者写操作的互斥信号量，初始值为 1；
  • 写者计数 wCount：记录写者数量，初始值为 0；
  • 信号量 wCountMutex：控制 wCount 互斥修改，初始值为 1；
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
semaphore rMutex;           //控制写操作的互斥信号量,初始值为1
semaphore rCountMutex;      //控制对rCount的互斥修改,初始值为1

semaphore wDataMutex;       //控制写者写操作的互斥信号量,初始值为1
semaphore wCountMutex;      //控制对wwCount的互斥修改,初始值为1

int rCount = 0;             //正在进行读数据的读者个数,初始值为0
int wCount = 0;             //正在进行写数据的写者个数,初始值为0

//写者
void writer()
{
    while(TRUE)
    {
        P(wCountMutex);     //进入临界区
        if(wCount == 0)     
        {
            P(rMutex);      //如果有读者,则阻塞读者
        }
        wCount ++;          //写者加一
        V(rCountMutex);     //离开临界区
        
        P(wDataMutex);      //进入临界区
        write();             //写数据
        P(wDataMutex);      //离开临界区
        
        P(wCountMutex);     //进入临界区
        wCount --;          //写者减一
        if(wCount == 0)
        {
            V(rMutex);      //最后一个写者离开了，则唤醒读者
        }
        V(wCountMutex);     //离开临界区
    }
}

//读者
void reader()
{
    while(TRUE)
    {   
        P(rMutex);          //进入临界区    
        P(rCountMutex);     
        if(rCount == 0)     
        {
            P(wDataMutex);  //如果有写者,则阻塞写者
        }
        rCount ++;          //读者加一
        V(rCountMutex);     
        V(rMutex);          //离开临界区
         
        read();             //读数据
            
        P(rCountMutex);     //进入临界区
        rCount --;          //读者减一
        if(rCount == 0)
        {
            V(wDataMutex);      //最后一个读者离开了，则唤醒写者
        }
        V(rCountMutex);     //离开临界区
    }
}


注意：这里rMutex的作用，开始有多个读者，它们全部进入到读者队列；此时来了一个写者，执行了P(rMutex),之后所有的读者都阻塞在了rMutex上面，都不能进入读者队列，而写者的到来，则可以全部进入写者队列，因此保证了写者优先

同时，第一个写者执行了 P(rMutex) 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 V(wDataMutex) 唤醒写者的写操作。

总结：

  • 只要有写者准备写入，写者应尽快执行写操作，后来的读者就必须阻塞
  • 如果写着持续不断的写入，则读者就处于饥饿

方案三：公平策略

公平策略：

  • 优先级相同
  • 写者，读者互斥访问呢
  • 只能有一个写者访问临界区
  • 可以有多个读者同时访问临界区
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
semaphore flag;           //控制写操作的互斥信号量,初始值为1
semaphore rCountMutex;      //控制对rCount的互斥修改,初始值为1
semaphore wDataMutex;       //控制写者写操作的互斥信号量,初始值为1
int rCount = 0;             //正在进行读数据的读者个数,初始值为0

//写者
void writer()
{
    while(TRUE)
    {
        P(flag);     //进入临界区
        
        P(wDataMutex);      //进入临界区
        write();             //写数据
        P(wDataMutex);      //离开临界区
        
        V(flag);     //离开临界区
    }
}

//读者
void reader()
{
    while(TRUE)
    {   
        P(flag);          //进入临界区    
        P(rCountMutex);     
        if(rCount == 0)     
        {
            P(wDataMutex);  //如果有写者,则阻塞写者
        }
        rCount ++;          //读者加一
        V(rCountMutex);     
        V(flag);          //离开临界区
         
        read();             //读数据
            
        P(rCountMutex);     //进入临界区
        rCount --;          //读者减一
        if(rCount == 0)
        {
            V(wDataMutex);      //最后一个读者离开了，则唤醒写者
        }
        V(rCountMutex);     //离开临界区
    }
}


总结：主要就是实现公平排队的功能

3.3.概念不同

  • 哲学家就餐问题：互斥访问有限的竞争问题
  • 读者-写者问题：数据库访问问题
上一页
2023-12-18 19:08:05 #操作系统 #进程管理
下一页