Project4

Lock Table

0.Project4

• 이번 프로젝트는 다수의 사용자가 서비스를 이용하는 멀트스레드 동작 중 동시성 제어를 위해 필요한 lock 테이블을 구현하는 것이 목적이다.

• 해시 테이블에 테이블아이디와 레코드아이디로 구분되는 노드들을 삽입한 후 각 노드마다 락 리스트를 구현하여 락 오브젝트를 생성하여 리스트에 넣어준다.

• 각 노드, 즉 데이터마다 락 리스트를 갖게 되는데 각각의 락들은 하나의 스레드에 매치된다.

• 만약 리스트에 락이 여러개, 즉 이미 다른 사용자(들)가 해당 데이터를 사용하고 있을 때는 스레드는 wait(sleep)상태로 대기한다.

• 사용을 끝낸 사용자는 해당 데이터에 대기자가 있는 경우 깨워주고 락 오브젝트를 해제한다.

• 락 테이블 접근을 동시에 여러명에서 하게 될경우 충돌이 발생하므로 mutex lock,unlock을 통해 함수전체가 온전히 실행될 수 있게 해준다.

---

1.해시

1)구조체

<1> 해시 테이블

• 해시 노드 배열(테이블)을 보유

• 테이블의 크기 변수

typedef struct HashTable {
	HashNode ** table;
	int size;
}HashTable;

<2> 해시 노드

• 해시 노드는 노드 링크드 리스트 보유

• 해시 키 값을 담는 변수

• 노드 리스트에 존재하는 노드의 개수를 알려주는 변수

typedef struct HashNode {
	Node * nodeList; 
	int key;
	int node_num;
}HashNode;

<3> 노드

• 각 노드는 테이블아이디+레코드아이디로 구별된다.

• 락 더블 링크드 리스트의 헤드와 테일을 가리키는 락 변수

• 노드의 링크드 리스트의 다음 노드를 가리키는 포인터 변수

typedef struct Node {
	int table_id;
	int record_id;//key
	lock_t * tail; 
	lock_t * head; 
	Node * next;
}Node;

---

2)함수

<1> create

• 해시 테이블 구조체 공간을 할당 후 hashnode 배열을 할당 후 구조체 변수들을 초기화 한다.

<2> insert

• 해시키를 통해 테이블에서 노드리스트를 가리키는 포인터를 가져온다.

• 삽입할 노드를 생성하고 구조체 변수들을 초기화 및 설정한다.

<3> search

• 빈 리스트가 아닌경우 링크드 리스트를 따라서 해당 레코드를 갖고 있는 노드를 탐색한다.

해시 오픈소스 참조 : https://makefortune2.tistory.com/71

---

2.Lock

1)구조체

<1> 락 오브젝트

• 락 더블링크드 리스트 구현을 위한 pre,next 포인터 변수

• conditional variable 사용을 통한 wait/signal 작동을 위해 cond 변수

• 해시 테이블을 가리키는 포인터 변수

typedef struct lock_t {
	
	lock_t *pre;
	lock_t *next;
	pthread_cond_t cond;
	HashTable * hash_ptr;

}lock_t;

---

2)함수

<1> init_lock_table

• 해시 테이블을 생성해주고 mutex init함수 호출한다.

<2> lock_acquire

• 뮤텍스 락,언락을 통해 함수가 온전히 실행될 수 있도록 한다.

• 새 lock 오브젝트를 생성 및 초기화 해준다.

• 해시 테이블에 해당 레코드를 가진 노드가 존재하지 않는다면 노드를 추가해준 후 락 리스트를 생성하고 lock 오브젝트를 연결시켜준다.

• 이미 해시 테이블에 존재하는 경우 그 노드의 락 리스트 뒤에 락을 연결해준다.

• 이미 해당 레코드를 다른 사용자(스레드)가 사용중이라면 sleep으로 대기한다.

• signal을 통해 깨워진 락은 뮤텍스를 풀고 락의 주소를 반환

<3> lock_release

• 락 리스트에서 제거해준다.

• 대기자가 있다면 깨워준다.

• 뮤텍스 언락과 락을 통해 함수가 온전히 실행되도록 해서 충돌을 막는다.