システムプログラミング 演習6：スレッドセーフなデータ構造

2009年10月22日

スレッドセーフなデータ構造

スレッドセーフなデータ構造とは、 利用する側で explicit な lock, unlock を必要とすることなく、 マルチスレッドプログラムで利用できるデータ構造である。 データ競合の回避は自動的に行われる。

本演習では、良く利用される list 構造に関してスレッドセーフ版を作成する。

スレッドセーフな list 構造を作成するにあたり，以下の逐次版の linked list (FIFO)を利用する。

ll.h

typedef struct ll ll_t;

struct ll
{
	ll_t *n;	/* next data */
};

typedef struct llh
{
	ll_t *front;	/* pointer to the first entry */
	ll_t **back;	/* address of storage of the last entry */
} llh_t;

/*
 * +--------+------+
 * |  front | back +
 * +--------+------+
 *     |         \___
 *     V             \|
 *   +---+   +---+   +---+
 *   | n +---+>n |---+>n |
 *   +---+   +---+   +---+
 */

void ll_init(llh_t *head);
void ll_enqueue(llh_t *head, ll_t *data);
ll_t *ll_peek(llh_t *head);
ll_t *ll_dequeue(llh_t *head);
ll_t *ll_traverse(llh_t *head, int (*func)(void *, void *), void *user);
/* make sure the list isn't corrupt and returns number of list items */
int ll_check(llh_t *head);
llh_t は linked list (FIFO)を管理する構造体。 ll_t はそれぞれのデータをつなぐためのポインタ。 ll_init は linked list (llh_t)の初期化を行う。 ll_enqueue は linked list にデータのポインタ(ll_t)を追加する。 ll_peek は先頭のデータのポインタを返す。 ll_dequeue はデータを取り出し、そのポインタを返す。 ll_traverse は linked list のデータそれぞれについて func を順に実行する。 func には，データ(ll_t)と ll_traverse の第三引数の user が渡される。 func が 0 を返した場合、traverse は続行。1 を返した場合、そこで終了。 -1 を返した場合、そのデータを dequeue してそのデータのポインタを返す。

ll.c

#include <stdlib.h>
#include <assert.h>
#include "ll.h"

void
ll_init(llh_t *head)
{
	head->back = &head->front;
	head->front = NULL;
}

void
ll_enqueue(llh_t *head, ll_t *data)
{
	data->n = NULL;
	*head->back = data;
	head->back = &data->n;
}

ll_t *
ll_peek(llh_t *head)
{
	return (head->front);
}

ll_t *
ll_dequeue(llh_t *head)
{
	ll_t *ptr;

	ptr = head->front;
	if (ptr && ((head->front = ptr->n) == NULL))
		/* last data, change to the initial state */
		head->back = &head->front;
	return (ptr);
}

ll_t *
ll_traverse(llh_t *head, int (*func)(void *, void *), void *user)
{
	ll_t *ptr, **prev;

	prev = &head->front;
	ptr = head->front;
	while (ptr) {
		switch (func(ptr, user)) {
		case 0:
			/* continues */
			prev = &ptr->n;
			ptr = ptr->n;
			break;
		case -1:
			/* the item is deleted */
			if ((*prev = ptr->n) == NULL)
				head->back = prev;
			return (ptr);
		case 1:
		default:
			/* traversal stops */
			return (NULL);
		}
	}
	return (NULL);
}

/* make sure the list isn't corrupt and returns number of list items */
int
ll_check(llh_t *head)
{
	int i = 0;
	ll_t *ptr, **prev;

	prev = &head->front;
	ptr = head->front;
	while (ptr) {
		++i;
		prev = &ptr->n;
		ptr = ptr->n;
	}
	assert(head->back == prev);
	return (i);
}
上記の逐次版 linked list を用いて逐次版 list 構造を以下のように定義する。

slist.h

typedef struct list {
	int count;
	llh_t head;
} list_t;

int list_init(list_t *ptr);
int list_add(list_t *ptr, void *item);
int list_traverse(list_t *ptr, int (*func)(void *, void *), void *user);
int list_remove(list_t *ptr, void *item);
int list_destroy(list_t *ptr);
list 構造体は、list の要素数と linked list を管理する構造体からなる。 list_init は list 構造体の初期化を行う。 list_add は list に item (void のポインタ)を追加する。 list_traverse は、list のそれぞれの item について func を実行する。 func の第一引数は item、第二引数は list_traverse の第三引数の user である。 func が 0 を返した場合、traverse は続行。1 を返した場合、そこで終了。 -1 を返した場合、その item を消去して終了。 このとき list_traverse は -1 を返す。 list_remove は list から item を削除する。 list_destroy は list を解放する。

slist.c

#include <stdlib.h>
#include <assert.h>
#include "ll.h"
#include "slist.h"

typedef struct list_entry {
	ll_t list;
	void *data;
} list_entry_t;

int
list_init(list_t *ptr)
{
	ptr->count = 0;
	ll_init(&ptr->head);
	return (0);
}

int
list_add(list_t *ptr, void *item)
{
	list_entry_t *e = malloc(sizeof(*e));

	if (e == NULL)
		return (-1);
	e->data = item;
	++ptr->count;
	ll_enqueue(&ptr->head, &e->list);
	return (0);
}

struct wrap {
	int (*func)(void *, void *);
	void *user;
};

static int
wrapper(void *e, void *u)
{
	list_entry_t *q = e;
	struct wrap *w = u;
	return (w->func(q->data, w->user));
}

int
list_traverse(list_t *ptr, int (*func)(void *, void *), void *user)
{
	list_entry_t *ret;
	struct wrap wrap;

	wrap.func = func;
	wrap.user = user;
	ret = (list_entry_t *)ll_traverse(&ptr->head, wrapper, &wrap);
	if (ret) {
		free(ret);
		--ptr->count;
		return (-1);
	}
	return (0);
}

static int
matchit(void *data, void *compare)
{
	return (data == compare ? -1 : 0);
}

int
list_remove(list_t *ptr, void *item)
{
	return (list_traverse(ptr, matchit, item));
}

int
list_destroy(list_t *ptr)
{
	list_entry_t *e;

	while ((e = (list_entry_t *)ll_dequeue(&ptr->head)) != NULL)
		free(e);
	return (0);
}

#ifdef LIST_TEST
#include <stdio.h>

int
print_entry(void *entry, void *arg)
{
	printf("<%s>\n", (char *)entry);
	return (0);
}

int
main()
{
	list_t list;

	list_init(&list);
	list_add(&list, "first");
	list_add(&list, "second");
	list_add(&list, "third");
	list_traverse(&list, &print_entry, NULL);
	list_destroy(&list);

	exit(0);
}
#endif

Thread-safe List 構造

スレッドセーフ版 list 構造のヘッダファイルを以下のように定義する。

list.h

/* thread-safe verison of linked list */

typedef struct list {
	int count;
	pthread_mutex_t lock;
	llh_t head;
} list_t;

int list_init(list_t *ptr);
int list_add(list_t *ptr, void *item);
int list_traverse(list_t *ptr, int (*func)(void *, void *), void *user);
int list_remove(list_t *ptr, void *item);
int list_destroy(list_t *ptr);
スレッドセーフ版の list構造では、スレッド間で共有される変数のアクセス に対する競合状態を回避するため mutex lock を用いる。 list 構造の操作に関しては逐次版と同様である。 list.c の一部を示す。

list.c

#include <stdlib.h>
#include <assert.h>
#include <pthread.h>
#include "ll.h"
#include "list.h"

typedef struct list_entry {
	ll_t list;
	void *data;
} list_entry_t;

/* call while holding lock */
static int
list_check(list_t *ptr)
{
	assert(ptr->count == ll_check(&ptr->head));
	return (1);
}

int
list_init(list_t *ptr)
{}

int
list_add(list_t *ptr, void *item)
{}

struct wrap {
	int (*func)(void *, void *);
	void *user;
};

static int
wrapper(void *e, void *u)
{
	list_entry_t *q = e;
	struct wrap *w = u;
	return (w->func(q->data, w->user));
}

int
list_traverse(list_t *ptr, int (*func)(void *, void *), void *user)
{
	list_entry_t *ret;
	struct wrap wrap;
	int return_value = 0;

	wrap.func = func;
	wrap.user = user;
	pthread_mutex_lock(&ptr->lock);
	assert(list_check(ptr));
	ret = (list_entry_t *)ll_traverse(&ptr->head, wrapper, &wrap);
	if (ret) {
		free(ret);
		--ptr->count;
		return_value = -1;
	}
	assert(list_check(ptr));
	pthread_mutex_unlock(&ptr->lock);
	return (return_value);
}

int
list_remove(list_t *ptr, void *item)
{}

int
list_destroy(list_t *ptr)
{
	list_entry_t *e;

	while ((e = (list_entry_t *)ll_dequeue(&ptr->head)) != NULL)
		free(e);
	return (pthread_mutex_destroy(&ptr->lock));
}

演習問題

  1. list.cのlist_init(), list_add(), list_remove()を実装しなさい．
  2. スレッドセーフ版の list 構造を利用するマルチスレッドの サンプルプログラムを作成し，動作の確認を行いなさい．

提出締切は 10/28(水) 20:00とする． サブジェクトを SP6 学籍番号 とし，tatebe _at_ cs までメールすること．

Osamu Tatebe
Last modified: Thu Oct 22 07:07:04 JST 2009