《并行程序设计导论》05openmp

生产者和消费者问题

生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。这个阻塞队列就是用来给生产者和消费者解耦的。

消息传递

生产者和消费者问题模型的另一个应用是在共享内存系统上实现消息传递。每一个线程有一个共享消息队列，当一个线程要向另一个线程发送消息时，它将消息放入目标线程的消息队列中，一个线程接收消息只需要从他的消息队列的头部取出消息。

for(sent_msgs=0;sent_msgs<send_max;sent_msgs++)
{
    send_msgs();
    try_recieve();
}
while (!done())
    try_recieve();

发送消息

访问消息队列并将消息入队可能是一个临界区。例如使用一个单链表来实现消息队列，链表的尾部对应队列的尾部。为了进行有效的入队操作，需要存储指向链表尾部的指针。当一个新消息入队时，需要检车和更新这个尾部指针。如果两个线程试图同时进行操作，就可能会丢失一条已经由其中一个线程入队的消息，因此入队操作形成了临界区。

接收消息

接收消息的同步问题与发送消息的不同。只有消息队列的拥有者可以读取消息。
如果消息队列中至少有两条消息，那么每次只出队一条消息，那么出队和入队操作就不可能有冲突。因此，如果队列中至少有两条消息，通过跟踪队列大小就可以避免任何同步。
现在的问题是如何存储队列大小。如果使用一个变量来存，又会产生临界区。可以使用两个变量enqueued和dequeued，那么队列中消息的数量可以表示为
queue_size=enqueued-dequeued

并且，唯一能够更新dequeued的线程是消息队列的拥有者。
这里看书吧！

终止检测

有如下程序done函数

queue_size=enqueued-dequeued;
if(queue_size==0)
    return true;
else 
    return false;

如果程序u执行以上代码，那么有可能是线程v在u计算出queue_size=0后向u发送消息，而u此时已经终止了，v给它发的消息永远都不能收到。然而在我们的程序中，每个线程在完成for循环后，就不再发送消息，因此可以添加一个计数器done_sending,每个线程在for循环结束后将该计数器加1

queue_size=enqueued-dequeued;
if(queue_size==0 && done_sending ==thread_count)
    return true;
else 
    return false;

启动

当程序开始执行时，主线程将得到命令行参数并且分配一个数组空间给消息队列，每个线程对应着一个消息队列。这个消息队列应该是共享的，因为每个线程可以向其它任意线程发送消息。

产生一个问题：
一个或者多个线程可能在其它线程之前完成他的队列分配。如果这种情况发生了，那么完成分配的线程可能会试图开始向那些还没有完成队列分配的线程发送消息，这将导致程序奔溃。因此，必须确保每个线程都必须在所有线程都完成队列分配后才开始发送消息。
一些openmp指令在结束时提供隐式路障，即任何一个线程都必须等到本组所有线程都完成某个程序块后才可以继续执行后续代码。我们这里处于parallel块的中间，可以使用显式的路障。

#pragma omp barrier

当线程遇到路障时，它将被阻塞，直到组中所有的线程都到达了这个路障。当组中所有的线程都到达了这个路障时，这些线程就可以接着往下执行。

atomic指令

atomic类似于critical指令，它只能保护由一条c语言赋值语句所形成的临界区。
#pragma omp atomic

x=//expression不能引用x
x++;
++x;
x–;
–x;
可以是以下任意的二元操作符：+,*,-,/,&,^,|,<<,or,>>

需要注意的是只有x的装载和存储可以确保是受保护的。

#pragma omp atomic
x+=y++;

其它线程对x的更新必须等到该线程对x的更新结束之后。但是对y的更新不受保护的。因此程序的结果是不可预测的。

临界区和锁

我们将在源代码中看到3个在critical或atomic指令后面的代码块。

done_sending++;
enqueue(q_p,my_rank,mesg);
dequeue(q_p,&src,&mesg);

在openmp看来，我们的程序有两个临界区：被atomic保护的done_sending++和“复合"临界区。在”复合“临界区中接收消息和发送消息。
强制线程间的互斥会使程序的执行串行化。openmp的默认做法是将所有的临界区代码块作为复合临界区的一部分。

这个意思是一个线程在读，另一个线程在写就不行，因为读和写分别用了critical指令

openmp提供了向critical指令添加名字的选项

#pragma omp critical(name)

两个用不同名字的critical指令保护的代码块就可以同时执行。需要在程序执行的过程中设置临界区的名字。当我i们想让访问不同队列的线程可以同时访问相同代码块时，被命名的critical指令就不能满足我们的要求了。
解决方案是用锁lock。锁由一个数据结构和定义在这个数据结构上的函数组成，这些函数是的程序员可以显示地强制对临界区进行互斥访问。锁的使用可以用如下的伪代码描述

//executed by one thread
initialize the lock data structure
...
//executed by mutiple threads
attempt to lock or set the lock data structure
critical section
unlock or unset the lock data structure;
...
//executed by one thread
destroy the lock data structure

锁的数据结构被执行临界区的线程所共享，这些线程中的某个线程会初始化所，而所有的线程都使用完锁后，某个线程应当负责销毁锁。
每个线程进入临界区之前，它尝试通过调用锁函数来上锁（set）。如果没有其它线程正在执行临界区代码，那么它将获得锁并且进入临界区。当线程执行完临界区代码，它调用解锁函数unset释放锁，而其它线程人被阻塞。
openmp有两种锁 简单(simple)和嵌套(nested)锁。简单锁在被释放前只能获得一次，而一个嵌套锁在被释放前可以被同一个线程获得多次。
简单锁的类型是omp_lock_t,定义简单锁的函数有
void omp_init_lock(omp_lock_t* lock_p);//初始化锁，此时锁处于解锁状态，意味着没有任何线程拥有这个锁
void omp_set_lock(omp_lock_t* lock_p);//尝试获得锁，如果成功，调用该函数的线程可以继续执行，如果失败，该线程警备阻塞，直到锁被其它线程释放
void omp_unset_lock(omp_lock_t* lock_p);//释放锁，以便其它线程可以获得该锁
void omp_destroy_lock(omp_lock_t* lock_p);//销毁锁

在消息传递程序中使用锁

在消息传递程序中，我们想要确保的是对每个消息队列进行互斥访问，而不是对于一个特定的代码块。
将omp_lock_t类型的数据成员包含在队列结构中

#pragma omp critical 
//q_p=msg_queues[dest]
enqueue(q_p,my_rank,mesg);
可以用以下代替
//q_p=msg_queues[dest]
omp_set_lock(&q_p->lock);
enqueue(q_p,my_rank,mesg);
omp_unset_lock(&q_p->lock);

类似的

#pragma omp critical 
//q_p=msg_queues[my_rank]
dequeue(q_p,&src,&mesg);
可以用以下代替
//q_p=msg_queues[my_rank]
omp_set_lock(&q_p->lock);
dequeue(q_p,&src,&mesg);
omp_unset_lock(&q_p->lock);

当一个线程试图发送或者接收消息是，它只可能被其它试图访问相同消息队列的线程阻塞，因为每个消息队列拥有不同的锁。因为我们已经将队列相应的锁包含在队列的结构中，所以我们可以把对锁的初始化的代码添加到初始化空队列中，而对锁的销毁则可以由拥有该队列的线程在销毁队列前完成。

critical指令、atomic指令、锁的比较
一般而言，atomic指令是实现互斥访问最快的方法。因此如果临界区由特定形式的赋值语句组成，则使用atomic指令至少不会比使用其它方法慢。然而openmp规范允许atomic指令对程序中所有的atomic指令标记的临界区进行强制互斥访问，这是未命名的critical指令的工作方式。例如在程序中有一个线程执行下面左边的代码，而另一个线程执行右边的代码：

#pragma omp atomic				#pragma omp atomic
x++;					        y++;

即使x和y拥有不同的内存地址，但可能一个线程在执行x++操作时，其它线程不能同时执行y++。

使用critical指令保护临界区与使用锁保护临界区在性能上没有太大的差别。所以，如果我们在无法使用atomic指令，却能够使用critical指令时，我们应当使用critical指令。锁机制适用于需要互斥的是某个数据结构而不是代码块的情况。

经验
（1）对同一个临界区不应当混合使用不同的互斥机制。
一个程序包含下面的两个代码片段

#pragma omp atomic				#pragma omp critical
x+=f(y);					    x=g(x);

右边的代码对x进行修改，但是不满足atomic指令要求的形式，所以程序员用了critical指令。由于critical指令和atomic指令不会互斥执行，所以程序可能会得到错误的结果。
解决办法看书
（2）互斥执行不保证公平性，也就是说可能某个线程会被一直阻塞以等待对某个临界区的执行。
（3）”嵌套“互斥结构可能会产生意料不到的结果。例如一个程序包含了以下的两个代码片段
#pragma omp critical
y=f(x);
…
double f(double x)
{
#pragma omp critical
z=g(x);//z是共享的
}

这段代码将产生死锁。当一个线程试图进入第二个临界区时，他将被永远阻塞。如果一个线程u在执行第一个临界区中的代码，就不可能有其它的线程执行第二个临界区中的代码。而然，如果线程u被阻塞以等待进入第二个临界区，那么1它将永远不会离开第一个临界区。
这么理解，critical指令对程序中所有的critical指令标记的临界区进行强制互斥访问，第一个代码的critical的临界区正在执行时，第二个就不可以使用，但是要完成第一个临界区，就必须调用函数f，但是f中有critical又用不了

在这里我们用name来解决

#pragma omp critical(one)
y=f(x);
...
double f(double x)
{
    #pragma omp critical(two)
    z=g(x);//z是共享的
}

如果一个程序有两个命名临界区，并且线程试图以不同的顺序进入临界区，那么死锁仍可能发生。仅仅使用命名临界区不足以解决上面的问题，程序员必须确保各个线程以相同的顺序进入临界区。