为链表上的操作实现多线程的问题
Problem in implementing multiple threading for operations on a linked list
在下面的代码中,我尝试使用多线程处理各种链表操作。可以支持多个链表,所有函数都是通用的,除了我保留了一些 printf
语句来调试代码。
typedef void (*gen_fun_t)(void *);
ll_t thread[2];
int ret;
#define RWLOCK(lt, lk) (ret=(lt) == l_read)? pthread_rwlock_rdlock(&(lk)): pthread_rwlock_wrlock(&(lk))
#define RWUNLOCK(lk) pthread_rwlock_unlock(&(lk));
typedef enum locktype locktype_t;
enum locktype
{
l_read,
l_write
};
struct node
{
void *val;
struct node *next;
pthread_rwlock_t m;
};
struct ll
{
int len;
struct node *head;
pthread_rwlock_t m;
gen_fun_t val_teardown;
gen_fun_t val_printer;
};
typedef struct ll* ll_t;
typedef struct node * ll_node;
ll_t create( gen_fun_t val_teardown)
{
ll_t list=(ll_t)malloc(sizeof(struct ll));
list->head=NULL;
list->len=0;
list->val_teardown = val_teardown;
pthread_rwlock_init(&list->m, NULL);
return list;
}
ll_node new_node(void *val)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
node->val=val;
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
int remove_mid(ll_t list, int n)
{
printf("Before deletion \n");
print(list);
ll_node temp;
if(n==0)
{
temp=list->head;
list->head=temp->next;
printf("%d \n", *(int *)(list->head)->val);
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
printf("%d \n", *(int *)(it->next)->val);
temp=it->next;
it->next=it->next==NULL? NULL: temp->next;
printf("%d \n", *(int *)(it->next)->val);
}
(list->len)--;
list->val_teardown(temp->val);
free(temp);
return list->len;
}
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val);
if(n==0)
{
node->next=list->head;
list->head=node;
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
node->next=it->next;
it->next=node;
printf("After insertion \n");
print(list);
printf("\n");
}
(list->len)++;
return list->len;
}
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int v=rand()%100;
int pos=rand()%list[0]->len;
printf("The position inserted is %d \n",pos+1);
pos=insert_mid(list[0], &v, pos);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
else
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int pos=rand()%list[0]->len;
printf("The position to be deleted is %d \n", pos+1);
pos=remove_mid(list[0], pos);
print(list[0]);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
}
int main()
{
int thread_count=2;
long thread;
srand(time(0));
list[0]= create(int_tear);
list[0]->val_printer = int_printer;
list[1]=create(float_tear);
list[1]->val_printer= float_printer;
pthread_t *thread_handles;
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
double start, finish, elapsed;
start=clock();
thread_handles= (pthread_t *) malloc(thread_count*sizeof(pthread_t));
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
for(thread=0;thread<thread_count;thread++)
pthread_join(thread_handles[thread], NULL);
finish=clock();
elapsed =(finish-start)/CLOCKS_PER_SEC;
return 0;
}
输出为
Thread: 0
The position to be inserted is 3
After insertion
ll: 2 15 79 8
Thread: 1
The position to be deleted is 1
Before deletion
ll: 2 15 -2087655584 8
ll: 15 -2087655584 8
很明显,insert_mid
函数在位置2插入了79,但为什么变成了-2087655584呢?解决方法是什么?
如有需要,请告知
简短摘要:您将局部变量的地址存储在列表节点中,并且该变量超出范围,因此该地址无效。
您的函数 new_node(void *val)
获取一个地址作为参数并将该地址存储在节点结构中作为 node->val
。
在您的 main
函数中,您首先使用局部变量的地址创建 3 个节点。
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
这些变量一直有效到main
结束,所以这里没有问题。
在这个循环中
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
您创建线程 运行 thread_operation
并传递循环计数器,作为参数转换为 void*
。
在 thread_operation
中,当使用参数值 0 调用时,您使用局部变量的地址添加一个节点 v
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
/* ... */
int v=rand()%100;
int pos=rand()%list[0]->len;
/* ... */
pos=insert_mid(list[0], &v, pos); /* &v is the address of a local variable */
/* ... */
}
else
{
/* ... */
}
}
/* ... */
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val); /* The address is passed to the new node. */
/* ... */
}
当thread_operation
离开
的body时
if(id==0)
{
/* ... */
}
变量超出范围并变得无效。 (如果你在没有优化的情况下编译你的程序,它可能会保持它的值直到函数 returns,但这不能保证。)
当thread_operation
returns时,该变量所在的栈区被释放,用于后面的其他函数调用
当您打印列表的内容时,ID 为 0 的线程插入的节点指向堆栈中曾经保存变量 v
并且可能正在使用或可能已被使用的某个地址之后的其他事情。这就是价值被改变的原因。这是未定义的行为。
要解决此问题,您可以将节点结构更改为 将变量的值 存储为 int
而不是地址变量作为void *
或你必须分配内存并创建数据副本像这样
ll_node new_node(void *val, size_t size)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
/* TODO check that malloc did not return NULL */
node->val = malloc(size);
/* TODO check that malloc did not return NULL */
memcpy(node->val, val, size);
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
其他可能的问题:
您在每个列表节点中创建一个锁 object。如果你想用它来保护对节点中数据的访问,相应的线程必须(至少)获得一个列表的读锁,以防止其他线程删除该节点。
在下面的代码中,我尝试使用多线程处理各种链表操作。可以支持多个链表,所有函数都是通用的,除了我保留了一些 printf
语句来调试代码。
typedef void (*gen_fun_t)(void *);
ll_t thread[2];
int ret;
#define RWLOCK(lt, lk) (ret=(lt) == l_read)? pthread_rwlock_rdlock(&(lk)): pthread_rwlock_wrlock(&(lk))
#define RWUNLOCK(lk) pthread_rwlock_unlock(&(lk));
typedef enum locktype locktype_t;
enum locktype
{
l_read,
l_write
};
struct node
{
void *val;
struct node *next;
pthread_rwlock_t m;
};
struct ll
{
int len;
struct node *head;
pthread_rwlock_t m;
gen_fun_t val_teardown;
gen_fun_t val_printer;
};
typedef struct ll* ll_t;
typedef struct node * ll_node;
ll_t create( gen_fun_t val_teardown)
{
ll_t list=(ll_t)malloc(sizeof(struct ll));
list->head=NULL;
list->len=0;
list->val_teardown = val_teardown;
pthread_rwlock_init(&list->m, NULL);
return list;
}
ll_node new_node(void *val)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
node->val=val;
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
int remove_mid(ll_t list, int n)
{
printf("Before deletion \n");
print(list);
ll_node temp;
if(n==0)
{
temp=list->head;
list->head=temp->next;
printf("%d \n", *(int *)(list->head)->val);
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
printf("%d \n", *(int *)(it->next)->val);
temp=it->next;
it->next=it->next==NULL? NULL: temp->next;
printf("%d \n", *(int *)(it->next)->val);
}
(list->len)--;
list->val_teardown(temp->val);
free(temp);
return list->len;
}
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val);
if(n==0)
{
node->next=list->head;
list->head=node;
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
node->next=it->next;
it->next=node;
printf("After insertion \n");
print(list);
printf("\n");
}
(list->len)++;
return list->len;
}
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int v=rand()%100;
int pos=rand()%list[0]->len;
printf("The position inserted is %d \n",pos+1);
pos=insert_mid(list[0], &v, pos);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
else
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int pos=rand()%list[0]->len;
printf("The position to be deleted is %d \n", pos+1);
pos=remove_mid(list[0], pos);
print(list[0]);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
}
int main()
{
int thread_count=2;
long thread;
srand(time(0));
list[0]= create(int_tear);
list[0]->val_printer = int_printer;
list[1]=create(float_tear);
list[1]->val_printer= float_printer;
pthread_t *thread_handles;
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
double start, finish, elapsed;
start=clock();
thread_handles= (pthread_t *) malloc(thread_count*sizeof(pthread_t));
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
for(thread=0;thread<thread_count;thread++)
pthread_join(thread_handles[thread], NULL);
finish=clock();
elapsed =(finish-start)/CLOCKS_PER_SEC;
return 0;
}
输出为
Thread: 0
The position to be inserted is 3
After insertion
ll: 2 15 79 8
Thread: 1
The position to be deleted is 1
Before deletion
ll: 2 15 -2087655584 8
ll: 15 -2087655584 8
很明显,insert_mid
函数在位置2插入了79,但为什么变成了-2087655584呢?解决方法是什么?
如有需要,请告知
简短摘要:您将局部变量的地址存储在列表节点中,并且该变量超出范围,因此该地址无效。
您的函数 new_node(void *val)
获取一个地址作为参数并将该地址存储在节点结构中作为 node->val
。
在您的 main
函数中,您首先使用局部变量的地址创建 3 个节点。
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
这些变量一直有效到main
结束,所以这里没有问题。
在这个循环中
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
您创建线程 运行 thread_operation
并传递循环计数器,作为参数转换为 void*
。
在 thread_operation
中,当使用参数值 0 调用时,您使用局部变量的地址添加一个节点 v
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
/* ... */
int v=rand()%100;
int pos=rand()%list[0]->len;
/* ... */
pos=insert_mid(list[0], &v, pos); /* &v is the address of a local variable */
/* ... */
}
else
{
/* ... */
}
}
/* ... */
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val); /* The address is passed to the new node. */
/* ... */
}
当thread_operation
离开
if(id==0)
{
/* ... */
}
变量超出范围并变得无效。 (如果你在没有优化的情况下编译你的程序,它可能会保持它的值直到函数 returns,但这不能保证。)
当thread_operation
returns时,该变量所在的栈区被释放,用于后面的其他函数调用
当您打印列表的内容时,ID 为 0 的线程插入的节点指向堆栈中曾经保存变量 v
并且可能正在使用或可能已被使用的某个地址之后的其他事情。这就是价值被改变的原因。这是未定义的行为。
要解决此问题,您可以将节点结构更改为 将变量的值 存储为 int
而不是地址变量作为void *
或你必须分配内存并创建数据副本像这样
ll_node new_node(void *val, size_t size)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
/* TODO check that malloc did not return NULL */
node->val = malloc(size);
/* TODO check that malloc did not return NULL */
memcpy(node->val, val, size);
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
其他可能的问题:
您在每个列表节点中创建一个锁 object。如果你想用它来保护对节点中数据的访问,相应的线程必须(至少)获得一个列表的读锁,以防止其他线程删除该节点。