Linux多线程实践(7) --多线程排序对比-阿里云开发者社区

开发者社区> 翡青> 正文

Linux多线程实践(7) --多线程排序对比

简介: 屏障 int pthread_barrier_init(pthread_barrier_t *restrict barrier, con...
+关注继续查看

屏障

int pthread_barrier_init(pthread_barrier_t *restrict barrier,
                         const pthread_barrierattr_t *restrict attr,
                         unsigned count);
int pthread_barrier_destroy(pthread_barrier_t *barrier);

int pthread_barrier_wait(pthread_barrier_t *barrier);

  屏障允许任意数量的线程等待, 直到所有的线程完成处理工作, 而线程不需要退出, 所有线程达到屏障之后可以接着工作.

  init:在初始化屏障时, 可以使用第三个参数count指定, 在允许所有线程继续运行之前, 必须到达屏障的线程数目.

  wait:可以使用pthread_barrier_wait函数来表明, 线程已经完成工作, 准备等所有其他线程赶上来;

    调用wait的线程在屏障计数未满足条件时, 会进入休眠状态. 如果该线程是最后一个调用wait的线程, 就满足了屏障计数, 所有的线程都被唤醒.

  对于一个任意线程, pthread_barrier_wait函数返回了PTHREAD_BARRIER_SERIAL_THREAD. 剩下的线程看到的返回值是0. 这使得一个线程可以作为主线程, 他可以工作在其他所有线程已完成的工作结果上.

 

单线程与多线程排序

单线程排序

bool compare(long a, long b)
{
    return a < b;
}

#define NUMNUM 8000000L
long int nums[NUMNUM];  //待排序数组(约32M)

int main()
{
    srandom(time(NULL));
    for (unsigned long i = 0; i < NUMNUM; i++)
        nums[i] = random();

    struct timeval  start, end;
    //计时开始
    gettimeofday(&start,NULL);
    sort(nums,nums+NUMNUM,compare); //单线程排序,快速排序
    gettimeofday(&end,NULL);

    //计算用时
    long long startusec = start.tv_sec * 1000000 + start.tv_usec;
    long long endusec = end.tv_sec * 1000000 + end.tv_usec;
    double elapsed = (double)(endusec - startusec) / 1000000.0;
    printf("sort took %.4f seconds\n", elapsed);

    //将排序后的结果写入文件, 以便查看是否已经排好序
    FILE *fp = fopen("save.txt", "w+");
    for (unsigned long i = 0; i < NUMNUM; i++)
        fprintf(fp, "%ld ", nums[i]);
}

三次排序用时如下:

  sort took 3.2435 seconds

  sort took 3.2221 seconds

  sort took 3.2134 seconds

(附-主机配置: 双核四线程(Intel(R) Core(TM) i3-2350M CPU @ 2.30GHz))

 

多线程排序(使用屏障同步)

#define NTHR   8                /* 线程数 */
#define NUMNUM 8000000L         /* 待排序数 */
#define TNUM   (NUMNUM/NTHR)    /* 每个线程分配到的需要排序的数 */
long nums[NUMNUM];
long snums[NUMNUM];
pthread_barrier_t b;    //屏障

bool compare(long a, long b)
{
    return a < b;
}
//排序线程
//对nums数组的从idx~idx+TNUM部分进行快速排序
void *workThread(void *arg)
{
    long    idx = (long)arg;

    sort(&nums[idx],&nums[idx+TNUM],compare);
    pthread_barrier_wait(&b);

    pthread_exit(NULL);
}

//对已经排好序数组nums的NTHR部分进行合并
void merge()
{
    long idx[NTHR];  //idx保存数组nums的NTHR部分的起始位置
    for (long i = 0; i < NTHR; i++)
        idx[i] = i * TNUM;

    for (long sidx = 0; sidx < NUMNUM; sidx++)
    {
        long minidx;
        long num = LONG_MAX;

        //从NTHR部分的数组中查找出最小的一个, 将其index保存到idx[minidx]中
        for (long i = 0; i < NTHR; i++)
        {
            //idx[i] < (i+1)*TNUM 确保是在一个部分之中,
            //不会产生两个部分相互比较的情况
            if ((idx[i] < (i+1)*TNUM) && (nums[idx[i]] < num))
            {
                num = nums[idx[i]];
                minidx = i;
            }
        }

        snums[sidx] = nums[idx[minidx]];
        idx[minidx]++;
    }
}

int main()
{
    srandom(time(NULL));
    for (unsigned long i = 0; i < NUMNUM; i++)
        nums[i] = random();

    //创建NTHR个线程分别对数组相邻的NTHR部分进行排序
    struct timeval  start, end;
    pthread_t       tid;
    gettimeofday(&start, NULL);
    pthread_barrier_init(&b, NULL, NTHR+1);
    for (unsigned long i = 0; i < NTHR; i++)
        pthread_create(&tid, NULL,workThread, (void *)(i * TNUM));
    pthread_barrier_wait(&b);
    merge();
    gettimeofday(&end, NULL);

    //计算用时
    long long startusec = start.tv_sec * 1000000 + start.tv_usec;
    long long endusec = end.tv_sec * 1000000 + end.tv_usec;
    double elapsed = (double)(endusec - startusec) / 1000000.0;
    printf("sort took %.4f seconds\n", elapsed);

    //将排序后的结果写入文件, 以便查看是否已经排好序
    FILE *fp = fopen("save.txt", "w+");
    for (unsigned long i = 0; i < NUMNUM; i++)
        fprintf(fp, "%ld ", snums[i]);
}

八线程排序:

  sort took 1.5556 seconds

  sort took 1.5676 seconds

  sort took 1.5719 seconds 

四线程排序:

  sort took 1.4132 seconds

  sort took 1.4315 seconds

  sort took 1.4738 seconds

二线程排序:

  sort took 2.0581 seconds

  sort took 2.2358 seconds

  sort took 1.7775 seconds

(附-主机配置: 双核四线程(Intel(R) Core(TM) i3-2350M CPU @ 2.30GHz))

 

总结: 可以看到尽管在分别进行排序之后还要有合并(merge)这一步,多线程排序(计算密集型任务)还是要优于单线程排序(在CPU为多核的情况下),而且在CPU为四线程下,使用四个线程对数组进行排序,所耗费时间是最少的!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
嵌入式 Linux线程同步读写锁rwlock示例
读写锁比mutex有更高的适用性,可以多个线程同时占用读模式的读写锁,但是只能一个线程占用写模式的读写锁。1. 当读写锁是写加锁状态时,在这个锁被解锁之前,所有试图对这个锁加锁的线程都会被阻塞;2. 当读写锁在读加锁状态时,所有试图以读模式对它进行加锁的线程都可以得到访问权,但是以写模式对它进行枷锁的线程将阻塞;3. 当读写锁在读模式锁状态时,如果有另外线程试图以写模式加锁,读写锁通常会阻塞随后的读模式锁请求,这样可以避免读模式锁长期占用,而等待的写模式锁请求长期阻塞;这种锁适用对数据结构进行读的次数比写的次数多的情况下,因为可以进行读锁共享。
839 0
Linux下多线程编程遇到的一些问题
今天在学习了Linux的多线程编程的基础的知识点。于是就试着做了一个简单的Demo。本以为会得到预期的结果。不成想却遇到了意想不到的问题。 代码展示 我的C 代码很简单,就是一个简单的示例程序,如下: #include #include #include i...
694 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
3956 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
5676 0
linux多线程下载工具mwget
linux多线程下载工具mwget 经常使用wget进行文件下载,然而wget的处理速度并不如人意。遇到一些国外的站点,经常慢得像蜗牛一般。然而为了解决这个问题,便有了mwget;m表示multi多线程的意思。
829 0
01.Java基础(多线程回顾,对比Linux多线程)
两个线程间通信,实现交替打印 public class Thread1 { public static void main(String[] args) { final Printer printer = new Printe...
599 0
+关注
翡青
阿里巴巴高级研发工程师
143
文章
34
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载