操作系统同步互斥

发表于 | 分类于

TSL指令

类似于java的CAS。

Test and set lock.这是一个原子操作，他的读写操作是不分开的。

TSL指令实现锁机制：当lock为0时，任何进程都可以使用TSL指令将其设置为1，然后访问临界区，操作结束时，再将lock重新设置为0.

1
2
3
4
5
6
7
void acquire(int *lock){
    while(TestAndSet(*lock));
}

void release(int *lock){
    *lock = 0;
}

在acquire函数中，如果TestAndSet返回1，那么while循环就一直执行（也就是在这里等待），直到另一个线程调用release。当然，这个实现看起来不太好，主要是等待的线程会不停的检查，浪费CPU，这个问题称之为忙等待（busy-wait or spin-wait），所以这个lock的实现也叫自旋锁spinlock。解决办法是如果需要等待，那么该线程主动交出执行权，让其他线程有机会执行，这种方式称之为让权等待（yield-wait or sleep-wait），应用开发人员使用的互斥锁一都是指这种情况。

以上的这些机制都是忙等待。
当一个进程想进入临界区，先检查是否允许进入，若不允许，将会原地等待，直到允许为止。
浪费CPU。

信号量

可以同时多个线程访问临界区，有P,V两个原子操作。

P(): 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；

V(); 对信号量执行 +1 操作，唤醒睡眠的进程让其完成 P操作。

要是信号量的取值变为了1，那么就变成了互斥量。

1
2
3
4
mutex=new Semaphore(1)
mutex.P();
临界区
mutex.V();

信号量主要可以解决两类问题。

  • 互斥问题。同一时刻只可以有一个线程访问某一个临界资源。
  • 同步问题。线程A需要等待线程B执行完毕后才可以继续执行。

信号量解决生产者消费者问题

  • 同一时刻，只能有一个生产者或者是消费者访问缓冲区。(互斥问题)
  • 缓冲区满时，生产者需要等待消费者消费。(同步问题)
  • 缓冲区空时，消费者需要等待生产者生产。(同步问题)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//互斥量
mutex = new Semophore(1);
//代表缓冲区有多少产品
products = new Semophore(0);
//代表缓冲区里有多大位置
remainPosition = new Semophore(n);


//生产者
remainPosition->P();
mutex->P();
Add();
mutex->V();
products->V();

//消费者，先去申请产品，在空出一个位置
products->P();
mutex->P();
Remove();
mutex->V();
remainPosition-V();

注意，empty->P()和mutex->P()不可以交换顺序。

要是

1
2
mutex->P()
empty-P();

假设我们现在的empty已经是0了，mutex先执行也变为了0，但是当执行到下一步empty-P()，发现自己需要阻塞，但是mutex还未释放，会造成死锁。
两个V()操作可以交换顺序。

管程(Monitor)

管程=互斥量+条件变量。
互斥量：可以保证共享资源在同一时间只能有一个进程访问。
条件变量：正在管程内的线程可以放弃对管程的控制权，等待某些条件发生再继续执行。
每个条件变量实际上代表的是一个等待队列。
当wait时，进程释放锁，挂起，并插入该条件变量的等待队列。
signal时，唤醒条件变量等待队列中的进程。

任意时刻管程中只能有一个活跃进程。
条件变量：解决死锁问题，挂起进程。
条件变量。wait：释放锁，挂起 notify：唤醒等待队列中一个线程。防止死锁。

管程解决生产者消费者问题

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
mutex buffer;//互斥量，一次只能由一个进程访问
int count=0;
Condition full,empty;//条件变量

//生产者
void Produce(){
   //获取互斥量
   mutex.acquire();
   //容器满了，线程挂起
   while(count==n){
      wait(full);
   }
   Add c;
   count++;
   //唤醒因没有产品挂起的线程
   notify(empty);
   mutex.release();
}

//消费者
void Produce(){
   //获取互斥量
   mutex.acquire();
   //容器满了，线程挂起
   while(count==0){
      wait(empty);
   }
   Remove c;
   count--;
//唤醒因容器满了挂起的线程
   notify(full); 
   mutex.release();
}