OS: 同步机制及应用编程实现与比较

1 实验目的

探索、理解并掌握操作系统同步机制的设计和实现机理， 针对所谓的银行账户转账同步问题，构建基于 Peterson 算法的同步解决方案以及基于 Windows（或 Linux） 操作系统同步机制（主要是互斥机制） 的解决方案，并进行分析和比较。

2 实验内容

针对所谓的银行账户转账同步问题， 分析、设计和利用 C 语言编程实现基于 Peterson 算法的同步解决方案，以及基于 Windows（或 Linux）操作系统同步机制的相应解决方案，并就自编同步机制与操作系统自身同步机制的效率进行比较和分析。

3 实验要求

同步机制及应用编程实现与比较实验功能设计要求：
（1） 银行账户转账同步问题的抽象及未采取同步控制情况下的编程实现；
（2） 基于 Peterson 算法的银行账户转账同步问题解决方案；
（3） 基于 Windows（或 Linux）操作系统同步机制的银行账户转账同步问题解决方案；
（4） Peterson 算法同步机制和 Windows（或 Linux）操作系统同步机制的效率比较。这里，银行账户转账假定为两个账户 nAccount1、 nAccount2（均定义为初值是 0 的整型全局变量） 之间进行，一个转出、一个转入，转账金额随机产生。整个程序共设立该两个账户之间的转账线程两个，且线程功能设计逻辑完全一致，不妨设转账线程的主体逻辑结构为如下的循环：

int nLoop = 0; int nTemp1, nTemp2, nRandom; do { nRandom = rand(); nTemp1 = nAccount1; nTemp2 = nAccount2; nAccount1 = nTemp1 + nRandom; nAccount2 = nTemp2 - nRandom;2 nLoop++; } while ((nAccount1 + nAccount2) = = 0);

注意，在基于 Peterson 算法或 Windows（或 Linux）操作系统同步机制的银行账户转账同步问题解决方案中，上面的循环结束条件应修正为：while(nLoop < 1000000); 或 while(nLoop < 5000000);同时在该循环体中 nAccount2 = nTemp2 - nRandom;语句后插入如下条件语句：if (nAccount1 + nAccount2 != 0) break;

4 实验步骤

4.1 实验环境

4.2 未采取同步控制情况

主函数如下，使用pthread_cread函数创建线程，pthread_join函数回收线程资源。

线程函数如下,Nloop记录循环次数，nAccount储存两个银行账户的金额，pthread_self()获取当前线程的tid,而使用pthread_exit函数退出线程。

运行结果如下:

4.3 基于 Peterson 算法的同步

通过设置flag和turn来实现多线程银行转账同步。当另一线程的flag为真且turn指向另一线程则当前线程阻塞。

两个子线程函数如下,通过while空循环实现阻塞。同时为了与Linux互斥锁机制效率进行比较，调用gettimeofday()函数储存线程运行时间。


运行结果如下:

4.4 基于 Linux互斥锁的同步

互斥锁本质就是一个特殊的全局变量，拥有lock和unlock两种状态，unlock的互斥锁可以由某个线程获得，一旦获得，这个互斥锁会锁上变成lock状态，此后只有该线程由权力打开该锁，其他线程想要获得互斥锁，必须得到互斥锁再次被打开之后。Linux中互斥锁全局变量如下:

子线程函数func如下,通过pthread_mutex_lock()函数锁定互斥锁。使用临界资源后使用pthread_unlock()函数释放互斥锁。

运行结果如下:

5 Peterson算法与Linux互斥锁比较

Peterson算法和Linux互斥锁都是一种很好很简便的控制线程同步机制。对于临界资源有很严格的控制。从运行的结果来看，Peterson算法和Linux互斥锁都能实现并发线程同步。但是通过两者的运行时间来看，两种机制效率是不同的，相较而言Pterson算法的效率更高一筹，而Linux互斥锁机制略逊于Pterson算法。

6 实验总结

本实验研究了多线程同步机制及模拟银行转账进行应用编程。通过银行转账分别模拟了未采取同步机制、基于peterson算法的同步机制和基于Linux互斥锁的同步机制。并将基于peterson算法的同步机制与基于Linux互斥锁的同步机制二者效率进行了比较。通过模拟未采取同步机制的银行转账过程，我们深刻的理解了线程同步的重要性。剩下两个实验让我们对peterson算法有了更深的理解，并且对Linux互斥锁机制有所了解。这对理解操作系统线程控制措施有所促进。就实验难度而言，主要集中于对Linux平台的c编程技能上，当然很多API网上有很多教程和实例，这降低了实验难度。

7 实验源码

// 未采取控制措施
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<time.h>
#define RAND(x,y) (rand()%((y)-(x)+1)+x)
int nAccount1 = 0,nAccount2=0;
void *func() 
{
    int Nloop = 0;
    int Ntemp1, Ntemp2;
    int r;
    Ntemp1 = nAccount1;
    Ntemp2 = nAccount2;
    do {
        r = RAND(0, 1000);
        nAccount1 = Ntemp1 + r;
        nAccount2 = Ntemp2 - r;
        Ntemp1 = nAccount1;
        Ntemp2 = nAccount2;
        Nloop++;
    } while ((nAccount1 + nAccount2) == 0);
    printf("Thread: %ld  Loop: %d\n", pthread_self(), Nloop);
    pthread_exit((void *)1);
}
int main()
{
    pthread_t tids[2];
    srand(time(0));
    pthread_create(&tids[0],NULL,&func,NULL);
    pthread_create(&tids[1],NULL,&func,NULL);
    printf("未采取同步控制:\n");
    void *retv;
    pthread_join(tids[0],&retv);
    pthread_join(tids[1],&retv);
    return 0;
}

// peterson算法
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<time.h>
#include<sys/time.h>
#define RAND(x,y) (rand()%((y)-(x)+1)+x)
int nAccount1 = 0,nAccount2=0;
int flag[2] = { 0,0};
int turn = 0;
void *func1() {
    int Nloop = 0;
    int nTemp1, nTemp2;
    int r;
    nTemp1 = nAccount1;
    nTemp2 = nAccount2;
    struct timeval tv1,tv2;
        gettimeofday(&tv1,NULL);
    do {
        flag[0] = 1;
        turn = 1;
        while (flag[1]&& turn == 1);
        r = RAND(0, 1000);
        nAccount1 = nTemp1 + r;
        nAccount2 = nTemp2 - r;
        nTemp1 = nAccount1;
        nTemp2 = nAccount2;
        Nloop++;
        if ((nAccount1 + nAccount2) != 0 )
            break;
        flag[0] = 0;
    } while (Nloop < 1000000);
    gettimeofday(&tv2,NULL);
    printf("Thread: %ld  Loop: %d  %dms\n", pthread_self(), Nloop,(tv2.tv_usec-tv1.tv_usec)/1000);
    pthread_exit((void *)1);
}
void *func2() {
    int Nloop = 0;
    int nTemp1, nTemp2;
    int r;
    nTemp1 = nAccount1;
    nTemp2 = nAccount2;
    struct timeval tv1,tv2;
        gettimeofday(&tv1,NULL);
    do {
        flag[1] = 1;
        turn = 0;
        while (flag[0]&& turn == 0);
        r = RAND(0, 1000);
        nAccount1 = nTemp1 + r;
        nAccount2 = nTemp2 - r;
        nTemp1 = nAccount1;
        nTemp2 = nAccount2;
        Nloop++;
        if ((nAccount1 + nAccount2) != 0)
            break;
        flag[1] = 0;
    } while (Nloop < 1000000);
    gettimeofday(&tv2,NULL);
    printf("Thread: %ld  Loop: %d  %dms\n", pthread_self(), Nloop,(tv2.tv_usec-tv1.tv_usec)/1000);
    pthread_exit((void *)1);
}
int main()
{
    pthread_t tids[2];
    srand(time(0));
    pthread_create(&tids[0],NULL,&func1,NULL);
    pthread_create(&tids[1],NULL,&func2,NULL);
    printf("Peterson算法同步控制:\n");
    void *retv;
    pthread_join(tids[0],&retv);
    pthread_join(tids[1],&retv);
    return 0;
}

// Linux互斥锁机制
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<time.h>
#include<sys/time.h>
#define RAND(x,y) (rand()%((y)-(x)+1)+x)
int nAccount1 = 0,nAccount2=0;
pthread_mutex_t mutex_x=PTHREAD_MUTEX_INITIALIZER;
void *func() {
    int Nloop = 0;
    int nTemp1, nTemp2;
    int r;
    nTemp1 = nAccount1;
    nTemp2 = nAccount2;
    struct timeval tv1,tv2;
        gettimeofday(&tv1,NULL);
    do {
        pthread_mutex_lock(&mutex_x);
        r = RAND(0, 1000);
        nAccount1 = nTemp1 + r;
        nAccount2 = nTemp2 - r;
        nTemp1 = nAccount1;
        nTemp2 = nAccount2;
        Nloop++;
        if ((nAccount1 + nAccount2) != 0)
            break;
        pthread_mutex_unlock(&mutex_x);
    } while (Nloop < 1000000);
    gettimeofday(&tv2,NULL);
    printf("Thread: %ld  Loop: %d  %ldms\n", pthread_self(), Nloop,(tv2.tv_sec-tv1.tv_sec)*1000+(tv2.tv_usec-tv1.tv_usec)/1000);
    pthread_exit((void *)1);
}
int main()
{
    pthread_t tids[2];
    srand(time(0));
    pthread_create(&tids[0],NULL,&func,NULL);
    pthread_create(&tids[1],NULL,&func,NULL);
    printf("Linux互斥锁同步控制:\n");
    void *retv;
    pthread_join(tids[0],&retv);
    pthread_join(tids[1],&retv);
    return 0;
}