转专业至今课表还没出来,先去上了节田老师的操作系统课,好评,最喜欢这种课上都是代码的课了。

转专业来之不易,今后更加好好珍惜机会,努力学习。

今天下午这节课讲的是进程同步,也算是并发程序启蒙课吧,听起来这有趣,打算将老师ppt上写的几个并发程序伪代码实现下,体会下并发程序的开发。

因为老师给出的例子是关于进程间共享资源产生的问题,以及如何去解决,我打算用线程(pthread库)来实现,因为线程的资源可以共享(共享全局区域、堆),容易写,和并发的进程大同小异,且思想是一样的。

争夺临界资源

下面第一个例子是并发程序争夺临界资源会出现的问题,这里的临界资源是

/*************************************************************************
    > File Name: parallel.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈

void printStack(int size) {
    for(int i=0; i<size; ++i)
        printf("%d ", stack[i]);
    printf("\n");
}

void *funA(void*) {
    while(true) {
        top = (++top) % n;
        usleep(10);
        stack[top] = 1;
        usleep(10);
    }
    return NULL;
}

void *funB(void*) {
    while(true) {
        top = (++top) % n;
        usleep(10);
        stack[top] = 2;
        usleep(10);
    }
    return NULL;
}


int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, funA, NULL);
    pthread_create(&t2, NULL, funB, NULL);
    while(top < 255);
    printStack(255);
    return 0;
}

输出结果:

0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 1 1 0 1 0 1 0 2 0 2 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 1 2 1 2 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

这里我用了usleep函数,它能让程序暂停微秒级,即(1000us = 1ms)。这样做是为了让程序程序浪费掉cpu执行的时间片,从而更容易调到另一个线程执行。

现在解释下运行的结果,当函数A执行++top的时候,正好cpu调到函数B执行++top,从而跳过了一个位置,这样就产生了并发程序对临界资源共享的问题。

下面我们来解决这些问题。

临界区访问控制模型

在临界区代码前后分别加上进入区、退出区,即临界区的一般访问模型。比如(引用ppt内容):

repeat                           repeat
    critical section;                entry section;
    remainder section;   =>                critical section;
until false;                         exit section;
                                          remainder section;
                                 until false;

下面给出老师ppt的几个解法的实现,以及其中隐含的问题。

软件解法1:按需访问

在程序加个变量free来标记资源是否空闲,很容易得出一下解法:

/*************************************************************************
    > File Name: parallel.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool free = false; // 资源空闲标志

void printStack(int size) {
    for(int i=0; i<size; ++i)
        printf("%d ", stack[i]);
    printf("\n");
}

void *funA(void*) {
    while(true) {
        // entry section
        while(free);
        free = true;
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 1;
        usleep(10);
        // exit section
        free = false;
        // remainder section
    }
    return NULL;
}

void *funB(void*) {
    while(true) {
        // entry section
        while(free);
        free = true;
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 2;
        usleep(10);
        // exit section
        free = false;
        // remainder section
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, funA, NULL);
    pthread_create(&t2, NULL, funB, NULL);
    while(top < 255);
    printStack(255);
    return 0;
}

程序看上去似乎是正确的,没什么大问题,我们来看看结果:

2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

嘛,看上去没什么大问题啊,那不妨多试几次吧。。。

2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 2 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0

果然经不起考验,3次就露出马脚了。

这段代码出现的错误在于,当我A函数执行到while(free),这时候freefalse自然不会循环,但是会出现cpu调到B函数执行,这时候while(free)也不会循环,结果到后面就会出现同时++top的情况了。这段代码违背了忙则等待的原则。

软件解法2:轮询

来看看第二个解法。

/*************************************************************************
    > File Name: parallel.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
int turn = 1; // 轮流标记

void printStack(int size) {
    for(int i=0; i<size; ++i)
        printf("%d ", stack[i]);
    printf("\n");
}

void *funA(void*) {
    while(true) {
        // entry section
        while(2 == turn);
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 1;
        usleep(10);
        // exit section
        turn = 2;
        // remainder section
    }
    return NULL;
}

void *funB(void*) {
    while(true) {
        // entry section
        while(1 == turn);
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 2;
        usleep(10);
        // exit section
        turn = 1;
        // remainder section
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, funA, NULL);
    pthread_create(&t2, NULL, funB, NULL);
    while(top < 255);
    printStack(255);
    return 0;
}

跑几下看看,没什么大问题:

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

是的,这段代码是正确的,但是它限制了资源访问顺序,所以你看到的结果永远是1 2 1 2...,这是没有必要的(限制访问顺序),PASS。

软件解法3:访前先看

show you the code:

/*************************************************************************
    > File Name: parallel.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool Aturn = false;
bool Bturn = false;

void printStack(int size) {
    for(int i=0; i<size; ++i)
        printf("%d ", stack[i]);
    printf("\n");
}

void *funA(void*) {
    while(true) {
        // entry section
        Aturn = true;
        while(Bturn);
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 1;
        usleep(10);
        // exit section
        Aturn = false;
        // remainder section
    }
    return NULL;
}

void *funB(void*) {
    while(true) {
        // entry section
        Bturn = true;
        while(Aturn);
        // critical section
        top = (++top) % n;
        usleep(10);
        stack[top] = 2;
        usleep(10);
        // exit section
        Bturn = false;
        // remainder section
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, funA, NULL);
    pthread_create(&t2, NULL, funB, NULL);
    while(top < 255);
    printStack(255);
    return 0;
}

猜猜结果是多少?我不知道,因为我至今没看到结果,如果你仔细看代码的话,你会发现很容易进入AturnBturn都为true的情况,所以2个函数都死循环了。

这段代码违背了空闲让进的原则。

面包坊算法(Peterson算法)

这个代码名叫Peterson算法,于1981年提出,这里给出只有2个线程并发的简化代码。毋庸置疑,我看到标题就不用怀疑其正确性了= =

/*************************************************************************
    > File Name: parallel.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool turn; // 轮到谁?线程个数为2
bool interested[2]; // 兴趣数组,初值为false
void enter_region(bool thread) {
    bool other = ~thread;
    interested[thread] = true;
    turn = thread;
    while(turn == thread && interested[other] == true);
}

void leave_region(bool thread) {
    interested[thread] = false;
}

void printStack(int size) {
    for(int i=0; i<size; ++i)
        printf("%d ", stack[i]);
    printf("\n");
}

void *funA(void*) {
    while(true) {
        // entry section
        enter_region(0);
        // critical section
        top = (++top) % n;
        stack[top] = 1;
        // exit section
        leave_region(0);
        // remainder section
    }
    return NULL;
}

void *funB(void*) {
    while(true) {
        // entry section
        enter_region(1);
        // critical section
        top = (++top) % n;
        stack[top] = 2;
        // exit section
        leave_region(1);
        // remainder section
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, funA, NULL);
    pthread_create(&t2, NULL, funB, NULL);
    while(top < 255);
    printStack(255);
    return 0;
}

运行结果:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

如果你仔细看的话,会发现我去掉usleep了,这样做是为了让结果更加明显,否则得到的结果几乎和轮询的结果一样的。

之所以也叫面包坊算法,老师的介绍是因为算法源于老外,老外喜欢吃面包,这个算法和面包坊加工一样,先进先出。

我觉得这个代码的精髓在于turn = thread,当初第一次看到这个代码的时候,我在想这个应该可以化简去繁,但是仔细一想,这个turn是全局变量,很巧妙,很可能因为其他线程而改变,第二个精髓的地方在于判断if(turn == thread,由于线程的id不一样,所以总能保证有一个在执行,其他线程就绪。

硬件解法1:TSL指令

因为TSL指令是一条原语(即不可中断),所以不好实现,这里略过,可看看书。

硬件解法2:SWAP指令

略过,理由如上。

以上几种解法,虽然有些满足同步要求,但是都违背了这样的原则:让权等待,据说信号量能很好解决这个问题,让我们拭目以待吧= =

参考资料

  • Linux/Unix系统编程手册(上册)第30章:线程同步
  • 合肥工业大学田老师操作系统课件:进程