多线程矩阵乘法

作者 Lao Yuan, 发布于 Lao-Yuan's Blog , 禁止转载.

操作系统课程多线程作业记录,学习windows和linux下的多线程编程方法

作业要求

利用多线程编程,分别在Windows和Linux下实现矩阵的乘法。

分析

Linux多线程和Windows下多线程实现原理基本相同,只是系统提供的API不同。事实上,Windows下如果不适用windows提供的API,而是使用GUN编译器自带的pthread接口API,其接口函数与linux是相同的。由于作业要求,windows下的程序使用windows.h提供的接口函数进行开发。

矩阵乘法的工作是一个O(n^4)时间复杂度的运算,运算量随n的增长急速上升,故在进行大规模矩阵乘法时可利用cpu的多线程来进行并行运算。

Windows下实验内容

  • 名称:Windows下的多线程矩阵乘法
  • 测试系统:windows10
  • IDE:codeblocks
  • 头文件:windows.h
  • 语言:c++格式进行代码,因为windows的API是为c++提供的,要用到引用概念

主函数核心代码

int main{
......
InitializeCriticalSection(&cs);
HANDLE thread1 = CreateThread(NULL, NULL, MultWork, NULL, NULL, NULL);
......
WaitForSingleObject(thread1, INFINITE);
......
}

主函数代码分析

InitializeCriticalSection(&cs) 为互斥锁的初始化函数,cs是CRITICAL_SECTION类型的锁变量,本程序中作为全局变量出现 其中:

  • thread1 为句柄对象的线程名,创建4个意味同时建立四个线程
  • CreatThread 函数为windowsAPI提供的线程创建函数,说明如下:

    • 第一个参数表示线程内核对象的安全属性,一般传入NULL表示使用默认设置。

    • 第二个参数表示线程栈空间大小。传入0表示使用默认大小(1MB)。

    • 第三个参数表示新线程所执行的线程函数地址,多个线程可以使用同一个函数地址。

    • 第四个参数是传给线程函数的参数。

    • 第五个参数指定额外的标志来控制线程的创建,为0表示线程创建之后立即就可以进行调度,如果为CREATE_SUSPENDED则表示线程创建后暂停运行,这样它就无法调度,直到调用ResumeThread()。

    • 第六个参数将返回线程的ID号,传入NULL表示不需要返回该线程ID号。 函数返回值:成功返回新线程的句柄,失败返回NULL。

  • WaitForSingleObject为等待对象函数,参数一为句柄类型的对象,参数二为最大等待时长。

工作函数核心代码


DWORD WINAPI MultWork(LPVOID pM){
......
EnterCriticalSection(&cs);
......
LeaveCriticalSection(&cs);
......
ExitThread(NULL);
}

工作函数说明

  • EnterCriticalSection(&cs)LeaveCriticalSection(&cs)为互斥锁的加锁和解锁函数,在这两个函数中间的代码或指令为临界值,用于保护读写。cs需要初始化。

  • ExitThread(NULL)函数是线程结束函数,参数为该线程调用的退出函数。

矩阵乘法功能实现–问题分析

为方便实现矩阵乘法,本程序配套矩阵创建函数、矩阵打印函数、矩阵C单个单元计算函数。创建矩阵使用用随机数填写空位的方法。在线程工作函数的代码中,需要解决的主要问题是乘法任务的分配问题.

对于本问题,程序有两种设计方法:

  • a:预先分配好任务.

    如在4线程下将任务强制划分为4部分,进行计算。这样分配有两个主要的问题:一是定态的分配任务在任务量较小、如只有三个单元需计算的情况下很难设计算法,使代码量增大;二是在大量数据需计算时,可能会出现线程未同步完成,先完成的线程等后线程的情况,浪费CPU资源。

  • b:动态分配任务。

    在已知C矩阵row和col之后生产C矩阵的同时,生成一个_C矩阵,将该矩阵所有单元置NULL。

    线程作业时采用方法b,循环以下步骤:

    • a.加互斥锁进入临界区,检查_C矩阵中离开头最近的NULL单元,将其置1;若没有这样的单元,置结束标flag为1,退出临界区去锁;
    • b.在C矩阵中对应位置,计算该位置数据值,并将该数据值更新到其位置;若无数据可计算,退出线程。 这种方法优势在于动态分配,劣势在于占用部分内存存放_C矩阵以及临界区计算占用CPU。在进行大规模运算时可以有效提高效率。

矩阵乘法功能–解决方法源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
  
  
typedef struct{
    int x;
}unit;
  
typedef struct{
    int row;
    int col;
    unit *x;
}matrix;
  
matrix A,B,C,_C;
CRITICAL_SECTION cs;
  
matrix CreatMatrix(int row, int col)      //row是行数,col是列数,即矩阵为row*col
{
    matrix target;
    int i,j;
    int data;
    //target = (matrix *)malloc(sizeof(matrix));
  
    target.row=row;
    target.col=col;
    target.x=(unit *)malloc(row*col*sizeof(unit));
    for(i=0;i<row;i++)
        for(j=0;j<col;j++)
        {
            data = rand()%100;
            (target.x+i*target.col+j)->x = data;
        }
    return target;
}
  
int CalcuOneUnit(int first,int second)
{
    int i,res = 0;
  
    //EnterCriticalSection(&cs);
    //printf("%d,%d is working\n",first,second);
    //LeaveCriticalSection(&cs);                    这里用于测试线程运行状态
    for(i = 0;i<A.col;i++)
        res += (A.x+first*A.col+i)->x * (B.x+i*B.col+second)->x;
    return res;
}
  
DWORD WINAPI MultWork(LPVOID pM)
{
    while(1)
    {
  
        int firstNum;
        int secondNum;
        int res,i,j,flag = 0,close = 0;
  
        EnterCriticalSection(&cs);
        for(i = 0;i<_C.row;i++)
        {
            for(j = 0;j<_C.col;j++)
            {
                if((_C.x+i*_C.col+j)->x == NULL)
                {
                    firstNum = i;
                    secondNum = j;
                    (_C.x+i*_C.col+j)->x = 1;
                    close = 1;
                    break;
                }
            }
            if(close == 1)
                break;
            else if(i == _C.row-1)
                flag = 1;
        }
        LeaveCriticalSection(&cs);
  
        if(flag == 1)
            ExitThread(NULL);
        res = CalcuOneUnit(firstNum,secondNum);
        (C.x+firstNum*C.col+secondNum)->x = res;
    }
    ExitThread(NULL);
}
  
void ShowMatrix(matrix shows)
{
    int row = shows.row;
    int col = shows.col;
    int i,j;
    for(i = 0;i<row;i++)
    {
        for(j = 0;j<col;j++)
            printf("%d\t",(shows.x+i*col+j)->x);
        printf("\n");
    }
}
  
int main()
{
    int row,col;
    int i;
    printf("     最简单的创建多线程实例\n");
  
    srand((unsigned)time(NULL));
    printf("请输入矩阵A的行列数:\n");
    scanf("%d %d",&row,&col);
    printf("________矩阵A为_______:\n");
    A=CreatMatrix(row,col);
    //ShowMatrix(A);
    printf("请输入矩阵B的行列数:\n");
    scanf("%d %d",&row,&col);
    printf("________矩阵B为_______:\n");
    B=CreatMatrix(row,col);
    //ShowMatrix(B);
    if(A.col != B.row)
    {
        printf("error input");
        return 1;
    }
  
    C = CreatMatrix(A.row,B.col);
    for(i = 0;i<C.col*C.row;i++)
        (C.x+i)->x = NULL;
    _C = CreatMatrix(A.row,B.col);
    for(i = 0;i<_C.col*_C.row;i++)
        (_C.x+i)->x = NULL;
  
    InitializeCriticalSection(&cs);
    HANDLE thread1 = CreateThread(NULL, NULL, MultWork, NULL, NULL, NULL);
    HANDLE thread2 = CreateThread(NULL, NULL, MultWork, NULL, NULL, NULL);
    HANDLE thread3 = CreateThread(NULL, NULL, MultWork, NULL, NULL, NULL);
    HANDLE thread4 = CreateThread(NULL, NULL, MultWork, NULL, NULL, NULL);
    WaitForSingleObject(thread1, INFINITE);
    WaitForSingleObject(thread2, INFINITE);
    WaitForSingleObject(thread3, INFINITE);
    WaitForSingleObject(thread4, INFINITE);
  
    printf("________矩阵C为_______:\n");
    //ShowMatrix(C);
    system("pause");
    return 0;
}

Linux下实验内容

  • Linux下的多线程矩阵乘法
  • 系统:Kali Linux
  • IDE:codeblocks
  • 语言:C

分析

Linux使用自己的多线程函数,程序整体逻辑与windows下没有区别,只需更换头文件为pthread.h并使用对应接口函数。

注意,cpp需要用g++编译,并加编译条件-lpthread,否则会找不到ptread相关的函数。

Linux下线程控制相关函数

  • pthread_t thread1 thread1变量为线程编号类型,一般为unsigned int类型,但在某些情况下会有区别。

  • pthread_mutex_t mutex mutex变量为互斥锁,需要初始化。

  • pthread_mutex_init(&mutex,NULL) 函数为互斥锁初始化函数,两个参数。第一个参数 mutex 是指向要初始化的互斥锁的指针;第二个参数 mutexattr 是指向属性对象的指针,该属性对象定义要初始化的互斥锁的属性。如果该指针为 NULL,则使用默认的属性。

  • pthread_mutex_lock(&mutex)pthread_mutex_unlock(&mutex) 用于给临界变量加锁和解锁,参数为互斥锁变量。

  • pthread_create(&thread1,NULL,MultWork,NULL) 用于创建线程,参数具体内容如下:

    • 第一个参数thread:线程标识符;
    • 第二个参数attr:线程属性设置;
    • 第三个参数start_routine:线程函数的起始地址;
    • 第四个参数arg:传递给start_routine的参数;
  • pthread_join(thread1,NULL) 等待一个线程结束,第一个参数为目标线程号,第二个参数为目标线程退出信息的存储位置。

  • pthread_exit(NULL) 结束当前线程,参数是pthread_exit()调用线程的返回值,可由其他函数如pthread_join来检索获取。

程序结构

Linux下函数结构和实现方式与windows下基本相同,不再赘述

程序源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
    
    
typedef struct{
    int x;
}unit;
    
typedef struct{
    int row;
    int col;
    unit *x;
}matrix;
    
matrix A,B,C,_C;
pthread_mutex_t mutex;
    
matrix CreatMatrix(int row, int col)      //row是行数,col是列数,即矩阵为row*col
{
    matrix target;
    int i,j;
    int data;
    //target = (matrix *)malloc(sizeof(matrix));
    
    target.row=row;
    target.col=col;
    target.x=(unit *)malloc(row*col*sizeof(unit));
    for(i=0;i<row;i++)
        for(j=0;j<col;j++)
        {
            data = rand()%100;
            (target.x+i*target.col+j)->x = data;
        }
    return target;
}
    
int CalcuOneUnit(int first,int second)
{
    int i,res = 0;
    
    //pthread_mutex_lock(&mutex);
    //printf("%d,%d is working\n",first,second);
    //pthread_mutex_unlock(&mutex);                    //这里用于测试线程运行状态
    for(i = 0;i<A.col;i++)
        res += (A.x+first*A.col+i)->x * (B.x+i*B.col+second)->x;
    return res;
}
    
void * MultWork(void *param)
{
    while(1)
    {
    
        int firstNum;
        int secondNum;
        int res,i,j,flag = 0,close = 0;
    
        pthread_mutex_lock(&mutex);
        for(i = 0;i<_C.row;i++)
        {
            for(j = 0;j<_C.col;j++)
            {
                if((_C.x+i*_C.col+j)->x == NULL)
                {
                    firstNum = i;
                    secondNum = j;
                    (_C.x+i*_C.col+j)->x = 1;
                    close = 1;
                    break;
                }
            }
            if(close == 1)
                break;
            else if(i == _C.row-1)
                flag = 1;
        }
        pthread_mutex_unlock(&mutex);
    
        if(flag == 1)
            pthread_exit(NULL);
        res = CalcuOneUnit(firstNum,secondNum);
        (C.x+firstNum*C.col+secondNum)->x = res;
    }
    pthread_exit(NULL);
}
    
void ShowMatrix(matrix shows)
{
    int row = shows.row;
    int col = shows.col;
    int i,j;
    for(i = 0;i<row;i++)
    {
        for(j = 0;j<col;j++)
            printf("%d\t",(shows.x+i*col+j)->x);
        printf("\n");
    }
}
    
int main()
{
    int row,col;
    int i;
    pthread_t thread1,thread2,thread3,thread4;
    printf("Simple example \n");
    
    srand((unsigned)time(NULL));
    printf("input row and col of Matrix A :\n");
    scanf("%d %d",&row,&col);
    printf("Matrix A is :\n");
    A=CreatMatrix(row,col);
    ShowMatrix(A);
    printf("input row and col of Matrix B :\n");
    scanf("%d %d",&row,&col);
    printf("Matrix B is :\n");
    B=CreatMatrix(row,col);
    ShowMatrix(B);
    if(A.col != B.row)
    {
        printf("error input");
        return 1;
    }
    
    C = CreatMatrix(A.row,B.col);
    for(i = 0;i<C.col*C.row;i++)
        (C.x+i)->x = NULL;
    _C = CreatMatrix(A.row,B.col);
    for(i = 0;i<_C.col*_C.row;i++)
        (_C.x+i)->x = NULL;
    
    pthread_mutex_init(&mutex, NULL);
    pthread_create(&thread1,NULL,MultWork,NULL);
    pthread_create(&thread2,NULL,MultWork,NULL);
    pthread_create(&thread3,NULL,MultWork,NULL);
    pthread_create(&thread4,NULL,MultWork,NULL);
    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);
    pthread_join(thread3,NULL);
    pthread_join(thread4,NULL);
    
    printf("Matrix C is :\n");
    ShowMatrix(C);
    return 0;
}