操作系统：同步互斥

2019-01-21  本文已影响0人  liuzhangjie

第9章：同步互斥

背景
现实生活中的同步问题
临界区
方法1：禁用硬件中断
方法2：基于软件的解决方法
方法3：更高级的抽象方法

9.1 背景

同步互斥是操作系统当中协调进程之间动作和相互关系的一种机制。

并发进程的正确性

并发创建新进程时的标识分配

原子操作（Atomic Operation）

defs：原子操作是指一次不存在任何中断或失败的操作
要么操作成功完成
要么操作没有执行
不会出现部分执行的状态
操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作

9.2 现实生活中的同步问题

9.3 临界区（critical section）

  1. 空闲则入：
    没有进程在临界区时，任何进程可进入
  2. 忙则等待：
    有进程在临界区时，其他进程均不能进入临界区
  3. 有限等待：
    等待进入临界区的进程不能无限等待
  4. 让权等待（可选）：
    不能进入临界区的进程应释放CPU（如转换到阻塞状态）

临界区的实现方法

  1. 禁用中断
  2. 软件方法
  3. 更高级的抽象方法

禁用中断

9.4 禁用硬件中断

9.5 基于软件的同步方法

在两个进程之间，通过共享变量的访问，来实现线程之间的同步
线程可通过共享一些共有变量之间来同步它们的行为

int turn = 0
turn == i//表示允许进入临界区的线程 
1
2
线程Ti的代码
do {
    while (turn != i);//条件不成立就可以进入临界区
    critical section
    trun = j;
    remainder section
}  while (1);
1
2
3
4
5
6

若turn不是i，则相当于我本身是i。允许另外一个线程进入临界区，i不允许进入临界区，这时它就一直等待，等待另一个线程把它改成i
当turn变成i之后，它能进去执行临界区的代码，执行完毕退出后，在退出区，它把turn改成j，也就是另一个线程的ID
满足“忙则等待”，但是有时不满足“空闲则入”
Ti不在临界区，Tj想要继续运行，但是必须等待Ti进入临界区后

int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示线程Ti是否在临界区
1
2
3
线程Ti的代码
do {
    while (flag[j] == 1);
    flag[i] = 1;
    critical section
    flag[i] = 0;
    remainder section 
} while (1);
1
2
3
4
5
6
7

如果flag[j]不是1，则另一个线程不在临界区，这时把自己的标识改成1，进入临界区，出来了把自己的标识置为0
不满足“忙则等待”

int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示线程Ti想要进入临界区
1
2
3

线程Ti的代码

do {
    flag[i] = 1;
    while (flag[j] == 1);
    critical section
    flag[i] = 0;
    remainder section
} whlie (1);
1
2
3
4
5
6
7

满足“忙则等待”，但是不满足“空闲则入”

Peterson算法

满足线程Ti和Tj之间互斥的基于软件的解决方法
共享变量

int turn;
boolean flag[];//表示进程是否准备好进入临界区
1
2
进入区代码
flag[i] = true;
turn = j;
while (flag[j] && turn ==j) //两个条件只要一个不满足就能进去
1
2
3
退出区代码
flag[i] = false;
1
线程Ti的代码
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
        critical section
    flag[i] = false;
        remainder section
} while (1);
1
2
3
4
5
6
7
8

Dekkers算法

线程Ti的代码

flag[0] := false; 
flag[1] := false;
turn := 0;//orl

do {
    flag[i] = true;
    while flag[j] == true {
        if turn != i {
            flag[i] := false
            while turn != i{}
                flag[i] := true
        }
    }
    critical section
    turn := j
    flag[i] = false;
    remainder section
} while (true);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

N线程的软件方法（Eisenberg 和 McGuire）



特点：

9.6 更高级的抽象方法

锁（lock）

锁是一个抽象的数据结构

使用锁来控制临界区访问

lock_next_pid -> Acquire();
new_pid = next_pid++;
lock_next_pid -> Release();
1
2
3

原子操作指令

使用TS指令实现自旋锁（spinlock）

class Lock {
    int value = 0;//初始化锁里的初值为0
}
Lock :: Acquire() {
    while （test-and-set（value））;//spin
    //构造它的请求操作原语，即用TS指令去把value的值读出来，并且往里写1。
    //如果是1，则这个操作就相当于是个检查，如果是0，则设为1，循环结束。
}
1
2
3
4
5
6
7
8

如果锁被释放，那么TS指令读取0并将值设置1

Lock :: Release() {
    value = 0;
}
1
2
3

无忙等待锁

Lock :: Acquire() {
    while （test-and-set（value））;//spin
}
Lock :: Release() {
    value = 0;
}
1
2
3
4
5
6

class Lock {
    int value = 0;
    WaitQueue q;//在锁的数据结构里加上一个等待队列，即等待这个锁的相应的进程所排的队列
}
Lock :: Acquire() {
    while （test-and-set（value））;{
        and this TCB to wait queue q;
        schedule();

    }
}
1
2
3
4
5
6
7
8
9
10
11

若查询一次之后，里面是1，就将当前线程放到等待队列，同时执行调度程序，此时其他程序可以继续执行
一旦切换回来，轮到该线程再运行时，即有释放锁操作，将该线程从等待状态变成就绪状态，此时再去查，若此时它的状态是解锁的状态，则请求完成，进入临界区

Lock :: Release() {
    value = 0;//表示释放锁
    remove one thread t from q;
    wakeup(t);//将线程从等待队列放到就绪队列。等待时，就处于放弃CPU使用权的状态，实现了让权等待
}
1
2
3
4
5

原子操作指令锁的特征

同步方法总结

上一篇下一篇

猜你喜欢

热点阅读