互斥与同步
|
1、竞争条件 2.怎样避免竞争条件？ 3.甚么叫临界区？ 4.1个好的避免出现竞争条件的解决方案，需要满足以下4个条件： while(TRUE){
while (turn != 0);
critical_region();
turn = 1;
noncritical_region();
}进程1: while(TRUE){
while (turn != 1);
critical_region();
turn = 1;
noncritical_region();
} 可以看到，进程0在离开临界区前，它将turn的值设置为1，以便允许进程1进入临界区。 #define FALSE 0
#define TRUE 1
#define N 2
int turn;
int interested[N];
void enter_region(int process)
{
int other;
other = 1 - process;
interested[process] = TRUE;
turn = process;
while(turn == process && interested[other] == TRUE);
}
void leave_region(int process)
{
interested[process] = FALSE;
} 看看它是如何工作的：1开始，没有任何进程处于临界区中，现在进程0调用enter_region()，并传入自己的进程ID，它通过设置其数组元素和将turn设置为0来标识希望进入临界区。由于进程1其实不想进入临界区，所以enter_region()很快便返回。如果进程1现在调用enter_region()，进程1将在此处挂起直到interested[0]变成FALSE，该事件只有在进程0调用leave_region()退出临界区时才会产生。 enter_region:
TSL RX,LOCK ;复制锁变量到寄存器RX，并将锁变量设置为1
CMP RX,#0 ;锁变量是0吗？
JNE enter_region ;若不是零，说明已被设置，所以跳转到enter_region开始循环履行
RET ;若是零，返回调用者，可以进入临界区leave_region:
MOVE LOCK,#0 ;将0存入锁变量
RET ;返回调用者，离开临界区 缺点：进程在进入临界区前，先调用enter_region，这将致使忙等待，直到锁空闲为止。与基于临界区问题的所有解法1样，进程必须在正确的时间调用enter_region和leave_region，解法才能见效。如果1个进程有讹诈行动，则互斥将会失败。 enter_region:
MOVE RX,#1 ;在寄存器中放入1个1
XCHG RX,LOCK ;将LOCK和RX的值交换
CMP RX,#0 ;判断RX的值是不是为0？
JNE enter_region ;如果不为0，说明已被设置，跳转到enter_region循环履行
RET ;如果为0，则返回调用者，可进入临界区leave_region:
MOVE LOCK,#0 ;将LOCK设置为0
RET ;返回调用者，离开临界区缺点：和TSL指令1样，存在忙等待的问题。 7).总结 2.2.寻觅更加高效的解决方案 作为使用这个方案的1个例子，我们斟酌生产者和消费者问题：两个进程同享1个公共的固定大小的缓冲区，其中1个是生产者，将信息放入缓冲区；另外一个是消费者，从缓冲区中取出信息。当缓冲区为空时，消费者应当阻塞，直到生产者生产了1份数据并唤醒它；当缓冲区满了时，生产者应当阻塞，直到消费者消费了1份数据并重新唤醒它。 #define MAXN 100 //缓冲区的容量
int count = 0; //缓冲区中的数据项数量
void producer(void)
{
int item;
while(TRUE)
{
item = produce_item(); //产生1项新数据
if(count == N) sleep(); //缓冲区已满了，生产者阻塞
insert_item(item);
count = count + 1;
if(count == 1) wakeup(consumer); //缓冲区空吗？如果不空，则唤醒消费者
}
}
void consumer(void)
{
int item;
while(TRUE)
{
if(count == 0) sleep(); //缓冲区空吗？如果为空，消费者阻塞
item = remove_item();
count = count - 1;
if(count == N - 1) wakeup(producer);//缓冲区还满吗？如果不满了，唤醒生产者
consume_item(item);
}
}上述的代码是存在竞争条件的，其缘由是对count的访问未加任何限制。有可能出现以下情况：缓冲区为空，消费者进程刚刚读取count的值发现它为0。此时调度程序决定暂停消费者并启动运行生产者进程。生产者向缓冲区中加入1个数据项，count加1,。现在count的值为1，它推断由于刚才count的值为0，所以消费者此时1定在睡眠，因而生产者调用wakeup来唤醒消费者。但是，消费者此时在逻辑上并未睡眠，只不过是被调度程序转移到了就绪队列中，以等待下1次运行，所以wakeup信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，因而睡眠。生产者早晚会填满全部缓冲区，然后睡眠，这样1来，两个进程都将永久睡眠下去。 问题的实质在于发给1个（尚）未睡眠的进程的wakeup信号丢失了。如果它没有丢失，则1切都很正常。解决它的方法就是使用信号量。 2.3.信号量 对1个信号量履行down操作，则是检测其值是不是大于0，若大于0，则将其值减1（即用掉1个保存的唤醒信号）并继续；若其值为0，则进程将睡眠，而此时down操作并未结束。1个信号量的down和up操作都是原子操作。所谓原子操作，是指1组相干联的操作要末都不中断的履行，要末都不履行。 up操作对信号量的值增加1.如果1个或多个进程在该信号量上睡眠，没法完成1个先前的down操作，则由系统选择其中1个（如随机挑选）并允许该进程完成它的down操作。因而，对1个有进程在其上睡眠的信号量履行1次up操作后，该信号量的值仍旧是0，但在其上睡眠的进程却少了1个。 如果使用多个CPU，则每一个信号量应当由1个锁变量进行保护，以确保同1时刻只有1个CPU在对信号量进行操作。 试着用信号量来解决生产者和消费者问题： #define N 100 //缓冲区最大容量
typedef int Semaphore;
Semaphore mutex = 1; //提供互斥，控制对临界区的访问（2元信号量实现互斥）
Semaphore empty = N;
Semaphore full = 0;
void producer(void)
{
int item;
while(TRUE)
{
item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer(void)
{
int item;
while(TRUE)
{
down(&full);
down(&mutex);
item = remove_item();
up(&mutex);
up(&empty);
consume_item(item);
}
} 在上述的示例中，我们用信号量实现了两种操作：互斥和同步。mutex就是1个互斥信号量，它相当于1个锁变量，每一个进程在进入临界区前履行1个down操作，比在刚刚退出时履行1个up操作，就可以实现互斥了。信号量full和empty用来保证某种事件的顺序产生和不产生，例如当缓冲区满时生产者停止，和缓冲区空时消费者停止。 如果有可用的TSL或XCHG指令，要在用户空间实现互斥量就很简单了。 mutex_lock:
TSL RX,MUTEX
CMP RX,$0 //互斥量是0吗？
JE ok //如果是0，则跳转到ok处，此时加锁成功，可以进入临界区
CALL thread_yield //如果不是0，将自己阻塞挂起，并让出CPU以调度另外一个线程
JMP mutex_lock //稍后再试
ok:
RET //返回调用者，进入临界区mutex_unlock:
MOVE MUTEX,#0
RETmutex_lock与enter_region的代码很类似，但有1个关键的区分：当enter_region进入临界区失败时，它始终重复测试锁（忙等待）。实际上，如果是在进程中，由于时钟超时作用，会调度其他进程运行，这样早晚具有锁的进程会进入临界区运行并释放锁，而忙等待的进程会因此而取得锁。而在用户线程中，情况有所不同，由于没有时钟停止运行时间太长的线程，会致使通过忙等待的方式来试图取得锁的线程将永久循环下去，决不会得到锁，由于这个试图取得锁的线程不会让其他线程运行从而释放锁。 2.5.Pthread中的互斥 除互斥量以外，pthread还提供了另外一种同步机制：条件变量。互斥量在允许或阻塞对临界区的访问上是很有用的，条件变量则允许线程由于1些未到达的条件而阻塞。绝大部份情况下这两种方法是1起使用的。这里的条件变量实际上类似于信号量。它也有专门的调用来创建和撤消，也能够有属性。最重要的两个操作是pthread_cond_wait和pthread_cond_signal。前者阻塞调用线程直到另外一其他线程向它发送信号。被阻塞的线程常常是在等待发信号的线程去做某些工作、释放某些资源或是进行其他的1些操作，只有完成后被阻塞的线程才可以继续运行。当多个线程被阻塞并等待同1个信号时，可使用pthread_cond_broadcast调用去唤醒它们所有。 条件变量与互斥量常常1起使用。这类模式用于让1个线程锁住1个互斥量，然后当它不能取得它期待的结果时等待1个条件变量。最后另外一个线程会向它发送信号，使它可以继续运行。pthread_cond_wait方法原子性的调用并解锁它持有的互斥量,由于这个缘由，互斥量是它的参数之1。 值得1说的是，条件变量不同于信号量，虽然它们很类似。条件变量（不像信号量）不会存在于内存中。如果将1个信号发送给1个没有线程在等待的条件变量，那末这个信号就会丢失。即是说条件变量不是计数器，也不能像信号量那样累计信号以便以后使用。所以，如果向1个条件变量发送信号，但是在该条件变量上并没有等待的进程，则该信号会永久丢失。 #include <stdio.h>
#include <pthread.h>
#define MAX 10 //生产的数据数量
pthread_mutex_t the_mutex; //互斥锁
pthread_cond_t condC,condP; //消费者和生产者的条件变量
int buff = 0;
void *producer(void *ptr)
{
for (int i = 1; i <= MAX; ++i)
{
printf("生产者线程第【%d】次运行.n",i);
pthread_mutex_lock(&the_mutex);
while(buff != 0)
{
printf("生产者线程睡眠.n");
pthread_cond_wait(&condP,&the_mutex); //如果缓冲区中还有数据，则睡眠并等待消费者的唤醒信号
}
buff = i;
pthread_cond_signal(&condC); //通知消费者消费产品
pthread_mutex_unlock(&the_mutex);
}
printf("生产者线程运行终了！n");
pthread_exit(NULL);
return NULL;
}
void *consumer(void *ptr)
{
for (int i = 1; i <= MAX; ++i)
{
printf("消费者线程第【%d】次运行.n",i);
pthread_mutex_lock(&the_mutex);
while(buff == 0)
{
printf("消费者线程睡眠.n");
pthread_cond_wait(&condC,&the_mutex); //如果没有可消费的产品，则睡眠并等待生产者的唤醒信号
}
printf("%dn",buff);
buff = 0;
pthread_cond_signal(&condP); //通知生产者生产产品
pthread_mutex_unlock(&the_mutex);
}
printf("消费者线程运行终了！n");
pthread_exit(NULL);
return NULL;
}
int main(int argc,char const *argv[])
{
pthread_t pro,con;
pthread_mutex_init(&the_mutex,NULL);
pthread_cond_init(&condC,NULL);
pthread_create(&con,NULL,consumer,NULL);
pthread_create(&pro,producer,NULL);
pthread_join(con,NULL);
pthread_join(pro,NULL);
pthread_cond_destroy(&condC);
pthread_cond_destroy(&condP);
pthread_mutex_destroy(&the_mutex);
return 0;
}（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |