同步
在之前的学习中，了解了进程能与系统内其他执行进程相互影响。协作进程之间或能直接共享逻辑地址空间（代码和数据），或能通过文件或者消息来共享数据。前一种是通过线程来实现的。
这里以进程之间最常见的同步问题，生产者-消费者（也叫有界缓冲区）问题来开始讨论吧。
问题描述：假设有一个固定大小的缓冲区，生产者生产数据写入，消费者取出数据进行消费。当缓冲区满的时候，生产者必须等待；当缓冲区为空时，消费者必须等待。
对于这个问题，我们进行深入分析，首先有一个必须共享的缓冲区。所以先进行下面的定义。
typedef struct {
...
} Item;
#define BUFFER_SIZE 10
Item buffer[BUFFER_SIZE];
int count = 0; // 缓冲区中的数据量
int in = 0; // 用来标识生产者存放下一个数据位置
int out = 0; // 用来标识消费者取出下一个数据位置
我们假设缓冲区的数据为BUFFER_SIZE，则我们可以得到这样的伪代码:
// producer
while (true) {
A = producer();
// 缓冲区满,等待
while (BUFFER_SIZE == count) ;
buffer[in] = A;
in = (in + 1) % BUFFER_SIZE;
count++;
}
// cosumer
while (true) {
// 缓冲区空,等待
while (0 == count) ;
B = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
}
虽然以上代码在各自的程序中各自正确，但是在并发执行时，可能会存在问题，因为count 这个数据是两个程序共享的。
"count++" 可以按照机器语言分解：
regisetr1 = count;
register1 = register + 1
count = register;
相应的"count--" 可以分解为
register2 = count ;
register2 = register2 - 1;
count = register2;
在CPU交替执行的时候，会产生三种结果。
producer_cosumer.png
这样的并发执行，我们得到count = 4; 如果T4，T5交换顺序，那么将得到6；
像这种，多个进程并发访问和操作同一数据并且执行结果与特定顺序有关，称为竞争条件。
临界区问题
临界区： 假设某个系统有n个进程{P0, P1, P2 .... Pn-1} 每个进程有一段代码，进程在执行的过程中，可能修改公共变量，更新一个表，写一个文件。这段代码叫做临界区。
当有进程在临界区执行的时候，其他进程不允许在它们的临界区内执行。一般的临界区，我们会根据他们的结构分为进入区（entry section），退出区(exit section)，临界区(ctitical section) 和 剩余区(remainder section)。如图所示：
ctitical_section临界区结构.png
临界区问题的解决方案需要满足三个要求：
- 互斥：如果进程Pi在其临界区内执行，那么其他进程不能再其临界区执行。
- 进步： 如果没有进程在其临界区，并且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可以参选，以便确定谁能下次进入临界区，而且这种选择不能无限推迟。
- 有限等待： 从一个进程作出进入临界区的请求直到这个请求允许为止，其他进程进入临界区的次数具有上限。
PeterSon算法
针对临界区问题，PeterSon给出了自己的算法，只要适用于两个线程交错执行临界区和剩余区。
假设有两个线程，P0和P1，这里只有两个线程，所以这里用i，j来表示，如果线程Pi表示一个线程，那么Pj表示另一个线程，两个线程共享数据
int turn;
bool flags[2];
变量turn表示那个线程程可以进入到临界区，如果turn == 0;表示进程P0可以进入缓冲区。
数组flags表示那个线程可以进入临界区。判断一个线程能否进入缓冲区需要 其他线程不在临界区。比如Pi线程需要判断，Pj在不在临界区内。他需要两个条件来判断 flags[j] 和turn == j; 所以可以得到这样的伪码结构：
peterson.png
为了进入临界区，进程Pi 首先设置flags[i] = true;表示第i个线程准备进入临界区。
turn == j; 这个是一个在执行过程中，根据操作系统调度的顺序，来选择的线程的一个值。因为假设P0和P1两个线程同时执行到了这里，并且都对flags值进行了设置，那么根据操作系统的调度，有可能两个同时被执行了，虽然这里会有不同的结果，但是最后的 turn 只能有一个，要么为0，要么为1 。（根据语义，我们可以看出，这个值其实可以 可以用turn == i，我读到这里的一个疑问，但是请看下面的一个条件判断。）
while (flags[j] && turn == j ) ; 这个判断主要是看另外一个线程有没有在临界区，如果在临界区，那么忙等待它退出；(上一步的j不能被替换，因为他会使 这个循环直接退出)。
flags[i] = false; 当退出临界区的时候，设置这个值，会使另外一个忙等待的线程跳出循环，进入到临界区。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
// 线程同步之临界区问题
// PeterSon算法
// 共享count数据
int count = 0;
// turn表示哪个进程可以进入临界区，
// turn == i; 表示第i个线程允许在临界区内执行。
int turn = 0;
// 数组flags 表示哪个进程准备进入临界区。
// flags[i] 为true, 表示第i个线程准备进入临界区。
bool flags[2];
void* process0(void* arg) {
while (true) {
// 第0个线程准备进入临界区
flags[0] = true;
// 如果两个线程同时进去，那么turn 会几乎在同时设置为0和1;
// 但是只有一个赋值语句可以成功，因为一个会被另外一个覆盖。
// 变量turn 表示最后会去哪一个。
// 这里turn 不能设置为0，因为下面的while的第二个条件直接跑走了。
// 默认应该是进行忙等待的
turn = 1;
while (flags[1] && turn == 1);
// 临界区代码
{
count++;
sleep(1);
printf("process 0 in 临界区. count=%d\n", count);
}
//
flags[0] = false;
}
}
void* process1(void* arg) {
while (true) {
// 第1个线程准备进入临界区
flags[1] = true;
// 如果两个线程同时进去，那么turn 会几乎在同时设置为0和1;
// 但是只有一个赋值语句可以成功，因为一个会被另外一个覆盖。
// 变量turn 表示最后会去哪一个。
turn = 0;
while (flags[0] && turn == 0);
// 临界区代码
{
count++;
sleep(1);
printf("process 1 in 临界区. count=%d\n", count);
}
//
flags[1] = false;
}
}
int main() {
pthread_t t0, t1;
flags[0] = flags[1] = false;
int err;
turn = 0;
err = pthread_create(&t0, NULL, process0, NULL);
if (err != 0)
exit(-1);
err = pthread_create(&t1, NULL, process1, NULL);
if (err != 0)
exit(-1);
pthread_join(t0, NULL);
pthread_join(t1, NULL);
return 0;
}
网友评论