条件变量与互斥量(2)

2023-10-18 17:19:52

因为线程的代码基本没怎么写过，leet-code出了线程题，刷下。

1116. 打印零与奇偶数

假设有这么一个类：

class ZeroEvenOdd {
public ZeroEvenOdd(int n) { ... } // 构造函数
public void zero(printNumber) { ... } // 仅打印出 0
public void even(printNumber) { ... } // 仅打印出偶数
public void odd(printNumber) { ... } // 仅打印出奇数
}
相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

线程 A 将调用 zero()，它只输出 0 。
线程 B 将调用 even()，它只输出偶数。
线程 C 将调用 odd()，它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。

示例 1：

输入：n = 2
输出："0102"
说明：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。
示例 2：

输入：n = 5
输出："0102030405"

VERSION 1:

　　三锁版，lock1, lock2, lock3. 线程a 激活线程b或者c，线程b， c 激活线程a

　　由于glibc的版本低，改了pthread_once

#define CHECK_VARIABLE(l,r) do{if(0 != r){fprintf(stderr,"[%s], err:[%d]\n",l,r);break;}}while(0);
#define L pthread_mutex_t
#define LOCK(t) pthread_mutex_lock(&t)
#define UNLOCK(t) pthread_mutex_unlock(&t)

#if 0
pthread_once_t tOnce = PTHREAD_ONCE_INIT;
#endif

int g_iOnce = 0;
L   tL0 = PTHREAD_MUTEX_INITIALIZER;
/* zero odd even */
L tL1;
L tL2;
L tL3;

void P(L* t)
{ 
    while (pthread_mutex_lock(t) != 0) {}
    return;
}

void V(L* t)
{ 
    if (pthread_mutex_unlock(t) == -1) {
        fprintf(stderr, "[%s].\n", "pthread_mutex_unlock error.");
    }
    return;
}


typedef struct {
    int n;
} ZeroEvenOdd;

ZeroEvenOdd* zeroEvenOddCreate(int n) {
    ZeroEvenOdd* obj = (ZeroEvenOdd*) malloc(sizeof(ZeroEvenOdd));
    obj->n = n;
    return obj;
}

void threadOnceInit(){
    int iRet = -1;

    iRet    = pthread_mutex_init(&tL1, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    iRet    = pthread_mutex_init(&tL2, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    iRet    = pthread_mutex_init(&tL3, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    P(&tL2); 
    P(&tL3); 

    return;
}

void zero(ZeroEvenOdd* obj) {   
    int             iRet                = 0;
    int             i                   = 0;

	P(&tL0);
	if (!g_iOnce)
	{
		threadOnceInit();
		g_iOnce++;
	}
	V(&tL0);
#if 0
    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
#endif

    for (; i < obj->n; i++)
    {
        P(&tL1);
        printNumber(0);
        if (i % 2) 
        {
            V(&tL3);
        }
        else
        {
            V(&tL2);
        }
    }
    
    pthread_exit(NULL);
}

void odd(ZeroEvenOdd* obj) { 
    int             iRet                = 0;
    int             i                   = 1;
	
	P(&tL0);
	if (!g_iOnce)
	{
		threadOnceInit();
		g_iOnce++;
	}
	V(&tL0);
	
#if 0
    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
#endif

    for (; i <= obj->n; i += 2)
    {
        P(&tL2);
        printNumber(i);
        V(&tL1);
    }

    pthread_exit(NULL); 
}


void even(ZeroEvenOdd* obj) {
    int             iRet                = 0;
    int             i                   = 2;

	P(&tL0);
	if (!g_iOnce)
	{
		threadOnceInit();
		g_iOnce++;
	}
	V(&tL0);
	
#if 0
    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
#endif

    for (; i <= obj->n; i += 2)
    {
        P(&tL3);
        printNumber(i);
        V(&tL1);
    }

    pthread_exit(NULL); 
}

void zeroEvenOddFree(ZeroEvenOdd* obj) {
    if (obj) 
    {
        free(obj);
        obj = NULL;
    }
    return; 
}

　　高版本glibc支持pthread_once的code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <math.h>
#include <pthread.h>

#include "leetcode.h"

/*
 *  leetcode 114:
 *  Level    : mid
 *  1116. Print Zero Even Odd
 *  realize by state var and semaphore
 */

#define CHECK_VARIABLE(l,r) do{if(0 != r){fprintf(stderr,"[%s], err:[%d]\n",l,r);break;}}while(0);
#define SET_BIT(x, y)  (x |= (1<<y))
#define NEG_BIT(x, y)  (x ^= (1<<y))
#define GET_BIT(x, y)  ((x)>>y & 0x1)
#define L pthread_mutex_t
#define LOCK(t) pthread_mutex_lock(&t)
#define UNLOCK(t) pthread_mutex_unlock(&t)

pthread_once_t tOnce = PTHREAD_ONCE_INIT;
/* zero odd even */
L tL1;
L tL2;
L tL3;

void P(L* t)
{ 
    while (pthread_mutex_trylock(t) != 0) {}
    return;
}

void V(L* t)
{ 
    if (pthread_mutex_unlock(t) == -1) {
        fprintf(stderr, "[%s].\n", "pthread_mutex_unlock error.");
    }
    return;
}

void printNumber(int x)
{
    printf("%d", x); 
    return;
}

typedef struct {
    int n;
} ZeroEvenOdd;

ZeroEvenOdd* zeroEvenOddCreate(int n) {
    ZeroEvenOdd* obj = (ZeroEvenOdd*) malloc(sizeof(ZeroEvenOdd));
    obj->n = n;
    return obj;
}

void threadOnceInit(){
    int iRet = -1;

    iRet    = pthread_mutex_init(&tL1, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    iRet    = pthread_mutex_init(&tL2, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    iRet    = pthread_mutex_init(&tL3, NULL);
    CHECK_VARIABLE("tL1 init error.", iRet);

    P(&tL2); 
    P(&tL3); 

    return;
}

void zero(ZeroEvenOdd* obj) {   
    int             iRet                = 0;
    int             i                   = 0;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    for (; i < obj->n; i++)
    {
        P(&tL1);
        printNumber(0);
        if (i % 2) 
        {
            V(&tL3);
        }
        else
        {
            V(&tL2);
        }
    }
    
    pthread_exit(NULL);
}

void odd(ZeroEvenOdd* obj) { 
    int             iRet                = 0;
    int             i                   = 1;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
    
    for (; i <= obj->n; i += 2)
    {
        P(&tL2);
        printNumber(i);
        V(&tL1);
    }

    pthread_exit(NULL); 
}


void even(ZeroEvenOdd* obj) {
    int             iRet                = 0;
    int             i                   = 2;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    for (; i <= obj->n; i += 2)
    {
        P(&tL3);
        printNumber(i);
        V(&tL1);
    }

    pthread_exit(NULL); 
}

void zeroEvenOddFree(ZeroEvenOdd* obj) {
    if (obj) 
    {
        free(obj);
        obj = NULL;
    }
    return; 
}

#define RETURN_IF_ERR(ret) \
    if (0 != ret) {printf("Get errorcode = [%d] line = [%d].\n", ret, __LINE__); return ret;}
int main()
{
    int             iRet            = 0;
    int*            pvRet           = NULL;
    pthread_t       tTid1           = 0;
    pthread_t       tTid2           = 0;
    pthread_t       tTid3           = 0;

    ZeroEvenOdd*    obj             = NULL;


    
#if 1
    obj = zeroEvenOddCreate(10);
    RETURN_IF_ERR(obj == NULL);

    iRet = pthread_create(&tTid1, NULL, zero, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid2, NULL, odd, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid3, NULL, even, obj);
    if (iRet) return iRet;

    iRet = pthread_join(tTid1, NULL);
    RETURN_IF_ERR(iRet);

    iRet = pthread_join(tTid2, NULL);
    RETURN_IF_ERR(iRet);

    iRet = pthread_join(tTid3, NULL);
    RETURN_IF_ERR(iRet);

    zeroEvenOddFree(obj);
    pthread_mutex_destroy(&tL1);
    pthread_mutex_destroy(&tL2);
    pthread_mutex_destroy(&tL3);
#endif
    return iRet;
}

VERSION 2：　　单锁 t + 状态 guide 　　线程 a，b，c 竞争 t, 根据 guide 来看当前是不是自己的执行区间，不是则释放。　　使用 pthread_mutex_t: 　　

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <math.h>
#include <pthread.h>

#include "leetcode.h"

#define CHECK_VARIABLE(l,r) do{if(0 != r){fprintf(stderr,"[%s], err:[%d]\n",l,r);break;}}while(0);

#define SET_BIT(x, y)  (x |= (1<<y))
#define NEG_BIT(x, y)  (x ^= (1<<y))
#define GET_BIT(x, y)  ((x)>>y & 0x1)

/*
 *  leetcode 114:
 *  Level    : mid
 *  1116. Print Zero Even Odd
 *  realize by state var and semaphore
 */

#define L pthread_mutex_t
#define LOCK(t) pthread_mutex_lock(&t)
#define UNLOCK(t) pthread_mutex_unlock(&t)

int             g_iGuide = 0;
L tMutex;
pthread_once_t tOnce = PTHREAD_ONCE_INIT;

void P(L* t)
{ 
    while (pthread_mutex_trylock(t) != 0) {}
    return;
}

void V(L *t)
{ 
    if (pthread_mutex_unlock(t) == -1) {
        fprintf(stderr, "[%s].\n", "pthread_mutex_unlock error.");
    }
    return;
}

void printNumber(int x)
{
    printf("%d", x); return;
}
typedef struct {
    int n;
} ZeroEvenOdd;

ZeroEvenOdd* zeroEvenOddCreate(int n) {
    ZeroEvenOdd* obj = (ZeroEvenOdd*) malloc(sizeof(ZeroEvenOdd));
    obj->n = n;
    return obj;
}

void threadOnceInit(){
    int iRet = -1;
    iRet    = pthread_mutex_init(&tMutex, NULL);
    if (iRet) printf("pthread_mutex_init error.\n");
    return;
}

/* do like this 0x000, 0x010, 0x100 */
void zero(ZeroEvenOdd* obj) {   
    int             iRet                = 0;
    int             i                   = 0;
    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
    
    while (1)
    {
        P(&tMutex);
        if (GET_BIT(g_iGuide, 0)) {
            V(&tMutex);
            continue;
        }

        if (i < obj->n){
            printNumber(0);
        }

        if (!GET_BIT(g_iGuide, 1)){ /* 000 -> 011 */
            SET_BIT(g_iGuide, 1);
        }
        else if (!GET_BIT(g_iGuide, 2)){ /* 010 -> 111 */
            SET_BIT(g_iGuide, 2);
        }
        else
        {
            sprintf(stderr, "[%s]\n", "zero error.");
            return;
        }
        SET_BIT(g_iGuide, 0);
        V(&tMutex);

        i = i + 1;
        if (i > obj->n) break;
    }
    
    pthread_exit(NULL);
}

void odd(ZeroEvenOdd* obj) { 
    int             iRet                = 0;
    int             i                   = 1;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    while (1)
    {
        P(&tMutex);
        if (!GET_BIT(g_iGuide, 0) || GET_BIT(g_iGuide, 2)) {
            V(&tMutex);
            continue;
        }

        if (i <= obj->n * 2)
        {
            printNumber((i + 1) / 2); 
        }
    
        NEG_BIT(g_iGuide, 0); /* TODO: 010 -> 111 */
        V(&tMutex);
        i = i + 4;
        if (i > obj->n * 2) break;
    }

    pthread_exit(NULL); 
}


void even(ZeroEvenOdd* obj) {
    int             iRet                = 0;
    int             i                   = 2;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    while (1)
    {
        P(&tMutex);
        if (!GET_BIT(g_iGuide, 0) || !GET_BIT(g_iGuide, 2)) {
            V(&tMutex);
            continue;
        }

        if (i < obj->n * 2)
        {
            printNumber((i + 2) / 2);
        }
    
        g_iGuide = 0;
        V(&tMutex);
        i = i + 4;
        if (i >= obj->n * 2) break;
    }

    pthread_exit(NULL); 
}

void zeroEvenOddFree(ZeroEvenOdd* obj) {
    if (obj) 
    {
        free(obj);
        obj = NULL;
    }
    return; 
}

#define RETURN_IF_ERR(ret) \
    if (0 != ret) {printf("Get errorcode = [%d] line = [%d].\n", ret, __LINE__); return ret;}
int main()
{
    int             iRet            = 0;
    int*            pvRet           = NULL;
    pthread_t       tTid1           = 0;
    pthread_t       tTid2           = 0;
    pthread_t       tTid3           = 0;

    ZeroEvenOdd*    obj             = NULL;
    
#if 1
    obj = zeroEvenOddCreate(10);
    RETURN_IF_ERR(obj == NULL);

    iRet = pthread_create(&tTid3, NULL, odd, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid2, NULL, even, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid1, NULL, zero, obj);
    if (iRet) return iRet;

    iRet = pthread_join(tTid3, NULL);
    RETURN_IF_ERR(iRet);
    iRet = pthread_join(tTid1, NULL);
    RETURN_IF_ERR(iRet);
    iRet = pthread_join(tTid2, NULL);
    RETURN_IF_ERR(iRet);

    zeroEvenOddFree(obj);
    pthread_mutex_destroy(&tMutex);
#endif
    return iRet;
}

　　使用 semaphore，不要问什么用这个，因为最早就是用semaphore，后发现测试机器不支持,才改用pthread_mutex_t

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <math.h>
#include <pthread.h>
#include <semaphore.h>

#include "leetcode.h"

#define CHECK_VARIABLE(l,r) do{if(0 != r){fprintf(stderr,"[%s], err:[%d]\n",l,r);break;}}while(0);

#define SET_BIT(x, y)  (x |= (1<<y))
#define NEG_BIT(x, y)  (x ^= (1<<y))
#define GET_BIT(x, y)  ((x)>>y & 0x1)

/*
 *  leetcode 114:
 *  Level    : mid
 *  1116. Print Zero Even Odd
 *  realize by state var and semaphore
 */

int             g_iGuide = 0;
sem_t           tSem;
pthread_once_t tOnce = PTHREAD_ONCE_INIT;

void P(sem_t* sem)
{ 
    while (sem_wait(sem) != 0) {}
    return;
}

void V(sem_t *sem)
{ 
    if (sem_post(sem) == -1) {
        fprintf(stderr, "[%s].\n", "sem_post error.");
    }
    return;
}

void printNumber(int x)
{
    printf("%d", x); return;
}
typedef struct {
    int n;
} ZeroEvenOdd;

ZeroEvenOdd* zeroEvenOddCreate(int n) {
    ZeroEvenOdd* obj = (ZeroEvenOdd*) malloc(sizeof(ZeroEvenOdd));
    obj->n = n;
    return obj;
}

void threadOnceInit(){
    int iRet = -1;
    iRet    = sem_init(&tSem, 0, 1);
    if (iRet) printf("sem_init error.\n");
    return;
}

/* do like this 0x000, 0x010, 0x100 */
void zero(ZeroEvenOdd* obj) {   
    int             iRet                = 0;
    int             i                   = 0;
    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);
    
    while (1)
    {
        P(&tSem);
        if (GET_BIT(g_iGuide, 0)) {
            V(&tSem);
            continue;
        }

        if (i < obj->n){
            printNumber(0);
        }

        if (!GET_BIT(g_iGuide, 1)){ /* 000 -> 011 */
            SET_BIT(g_iGuide, 1);
        }
        else if (!GET_BIT(g_iGuide, 2)){ /* 010 -> 111 */
            SET_BIT(g_iGuide, 2);
        }
        else
        {
            sprintf(stderr, "[%s]\n", "zero error.");
            return;
        }
        SET_BIT(g_iGuide, 0);
        V(&tSem);

        i = i + 1;
        if (i > obj->n) break;
    }
    
    pthread_exit(NULL);
}

void odd(ZeroEvenOdd* obj) { 
    int             iRet                = 0;
    int             i                   = 1;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    while (1)
    {
        P(&tSem);
        if (!GET_BIT(g_iGuide, 0) || GET_BIT(g_iGuide, 2)) {
            V(&tSem);
            continue;
        }

        if (i <= obj->n * 2)
        {
            printNumber((i + 1) / 2); 
        }
    
        NEG_BIT(g_iGuide, 0); /* TODO: 010 -> 111 */
        V(&tSem);
        i = i + 4;
        if (i > obj->n * 2) break;
    }

    pthread_exit(NULL); 
}

void even(ZeroEvenOdd* obj) {
    int             iRet                = 0;
    int             i                   = 2;

    iRet = pthread_once(&tOnce, threadOnceInit);
    CHECK_VARIABLE("pthread_once error. \n", iRet);

    while (1)
    {
        P(&tSem);
        if (!GET_BIT(g_iGuide, 0) || !GET_BIT(g_iGuide, 2)) {
            V(&tSem);
            continue;
        }

        if (i < obj->n * 2)
        {
            printNumber((i + 2) / 2);
        }
    

        g_iGuide = 0;
        V(&tSem);
        i = i + 4;
        if (i >= obj->n * 2) break;
    }

    pthread_exit(NULL); 
}

void zeroEvenOddFree(ZeroEvenOdd* obj) {
    if (obj) 
    {
        free(obj);
        obj = NULL;
    }
    return; 
}

#define RETURN_IF_ERR(ret) \
    if (0 != ret) {printf("Get errorcode = [%d] line = [%d].\n", ret, __LINE__); return ret;}
int main()
{
    int             iRet            = 0;
    int*            pvRet           = NULL;
    pthread_t       tTid1           = 0;
    pthread_t       tTid2           = 0;
    pthread_t       tTid3           = 0;

    ZeroEvenOdd*    obj             = NULL;
    
#if 1
    obj = zeroEvenOddCreate(10);
    RETURN_IF_ERR(obj == NULL);

    iRet = pthread_create(&tTid3, NULL, odd, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid2, NULL, even, obj);
    if (iRet) return iRet;

    iRet = pthread_create(&tTid1, NULL, zero, obj);
    if (iRet) return iRet;


    iRet = pthread_join(tTid3, NULL);
    RETURN_IF_ERR(iRet);
    iRet = pthread_join(tTid1, NULL);
    RETURN_IF_ERR(iRet);
    iRet = pthread_join(tTid2, NULL);
    RETURN_IF_ERR(iRet);

    zeroEvenOddFree(obj);
#endif
    return iRet;
}

VERSION 3:
　　cond + mutex 最早用的，线程abc执行当满足条件时，否则竞争测试条件满足否。

void printNumber(int x)
{
    printf("%d", x); return;
}
typedef struct {
    int n;
} ZeroEvenOdd;

ZeroEvenOdd* zeroEvenOddCreate(int n) {
    ZeroEvenOdd* obj = (ZeroEvenOdd*) malloc(sizeof(ZeroEvenOdd));
    obj->n = n;
    return obj;
}

int g_iCurIndex = -1;
pthread_mutex_t g_tMutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t g_tCond   = PTHREAD_COND_INITIALIZER;

void zero(ZeroEvenOdd* obj) {   
    int             iRet                = 0;

    while (1)
    {
        iRet = pthread_mutex_lock(&g_tMutex);
        if (iRet) continue;

        while (g_iCurIndex % 2 != 0)
        {
            pthread_cond_wait(&g_tCond, &g_tMutex);
        }

        if (g_iCurIndex == obj->n * 2) 
        {
            g_iCurIndex = 0;
            pthread_cond_broadcast(&g_tCond);
            pthread_mutex_unlock(&g_tMutex);
            /* free obj */
            zeroEvenOddFree(obj);
            break;
        }
        
        printNumber(0);
        g_iCurIndex++;
        pthread_mutex_unlock(&g_tMutex);
        pthread_cond_broadcast(&g_tCond);
    }
    
    pthread_exit(NULL);
}

void odd(ZeroEvenOdd* obj) { 
    int             iRet                = 0;
    while (1)
    {
        iRet = pthread_mutex_lock(&g_tMutex);
        if (iRet) continue;

        while ((g_iCurIndex % 2 == 0) 
            || (g_iCurIndex % 4 != 1))
        {
            pthread_cond_wait(&g_tCond, &g_tMutex);
        }
        iRet = g_iCurIndex;
        printNumber((iRet + 1) / 2);
        g_iCurIndex++;
        pthread_mutex_unlock(&g_tMutex);
        pthread_cond_broadcast(&g_tCond);

        if (iRet + 4 > obj->n * 2) break;
        
    }
    pthread_exit(NULL); 
}

void even(ZeroEvenOdd* obj) {
    int             iRet                = 0;

    while (iRet = pthread_mutex_lock(&g_tMutex) != 0);
    g_iCurIndex = 0;
    pthread_mutex_unlock(&g_tMutex);

    while (1)
    {
        iRet = pthread_mutex_lock(&g_tMutex);
        if (iRet) continue;

        while ((g_iCurIndex % 2 == 0) 
            || (g_iCurIndex % 4 != 3))
        {
            pthread_cond_wait(&g_tCond, &g_tMutex);
            if (g_iCurIndex == 0) 
            {
                pthread_exit(NULL); 
            }
        }

        printNumber((g_iCurIndex + 1 ) / 2);
        iRet = g_iCurIndex;
        g_iCurIndex++;
        pthread_mutex_unlock(&g_tMutex);
        pthread_cond_broadcast(&g_tCond);

        if (iRet + 4 > obj->n * 2) break;
    }

    pthread_exit(NULL); 
}

void zeroEvenOddFree(ZeroEvenOdd* obj) {
    if (obj) 
    {
        free(obj);
        obj = NULL;
    }
    return; 
}

码农公寓

1116. 打印零与奇偶数

相关文章