04_Block Module Design

Lock Object Layout

Lock Object Implementation

struct lock_t {
	hash_table_entry * sentinel;
	lock_t * prev;
	lock_t * next;
	pthread_cond_t cond;
};

Hash Table Entry Design

Hash Table Entry Implementation

struct hash_table_entry {
	int table_id;
	int64_t key;
	lock_t * head;
	lock_t * tail;
};

Hash Table Design

unordered_map is used for hash table.

Access to hash table entry by table_id and key.

Hash Table Implementation

unordered_map< int, unordered_map<int64_t, hash_table_entry> > lock_hash_table;

init_lock_table()

Initialize global mutex.

Global mutex is used to handle simultaneous requests to lock table sequentially.

So from now, it is called latch.

// lock_table_latch is global mutex
int init_lock_table() {
	pthread_mutex_init(&lock_table_latch, NULL);
	return 0;
}

lock_acquire(table_id, key)

Case 1 : No Predecessor

Initialize hash table entry and new lock object.

Add new lock object to lock list.

In this case, condition variable is not initialized. Because, new lock object does not wait to acquire the entry.

Case 2 : Predecessor is exist

Initialize new lock object.

In this case, condition variable must be initialized to wait until its turn.

Update hash table.

Add new lock object to lock list.

Make new lock object sleep until the predecessor to release its lock by pthread_cond_wait(&lock_obj->cond, &lock_table_latch).

lock_release(lock_obj)

Case 1 : No Successor

Delete lock_obj from lock list and update links.

Free lock_obj.

Case 2 : Successor's lock waiting is exist

Delete lock_obj from lock list and update links.

Send wake up signal to successor.

Free lock_obj.