pintOS | list_entry(), doubly linked-list

 

 

pintOS는 threads, user porgrams, virtual memory, file system 등 운영체제의 개념들을 직접 구현하면서 더 깊게 이해하는데 도움을 주는 교육용 운영체제다.

 

핀토스는 정글에서 공부하는 프로젝트 중 끝판왕이라고 불리는 만큼 험난하다. 프로젝트를 직접 구현할 때 내가 사용하는 함수들의 작동 원리도 제대로 파악하는 것 조차 너무 어려워서 내가 사용하는 코드들의 기능과 역할을 정리해보려고 한다. 조금은 두서없이 정리하겠지만 일단 내가 이해하는 것이 우선..!

 

 

list_entry()

Project1: THREADS에서 첫 번째 미션인 Alarm Clock을 할 때, block되어 있는 스레드를 wakeup해서 ready list에 넣어야 하는 함수를 구현해야 한다. 이 때 함수는 다음과 같다.

 

void thread_awake(int64_t wakeup_tick) {
	next_tick_to_awake = INT64_MAX;
	struct list_elem *e;
	e = list_begin(&sleep_list);
	while (e != list_end(&sleep_list)) {
		struct thread *t = list_entry(e, struct thread, elem);

		if (wakeup_tick >= t->wakeup_tick) {
			e = list_remove(&t->elem);
			thread_unblock(t);
		} else {
			e = list_next(e);
			update_next_tick_to_awake(t->wakeup_tick);
		}
	}
}

 

이 때 while문 바로 아래 struct thread *t = list_entry(e, struct thread, elem); 가 보인다.

여기서 list_entry함수가 의미하는 것이 뭘까? e = list_begin(&sleep_list); 를 보고 sleep list 안에 있는 구조체를 가리키는 것이구나~ 정도로만 이해하고 넘어갔었는데, 프로젝트를 진행하면서 list_entry가 자주 사용되는 것을 발견하게 되었다. 결국 저 함수에 대해서 제대로 이해해야 편히 잘 수 있을 것 같아서 한 번 파보려고 한다.

 

일단 list.h 파일에 정의된 list_entry는 이렇다.

/* Converts pointer to list element LIST_ELEM into a pointer to
   the structure that LIST_ELEM is embedded inside.  Supply the
   name of the outer structure STRUCT and the member name MEMBER
   of the list element.  See the big comment at the top of the
   file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
		- offsetof (STRUCT, MEMBER.next)))

list_entry는 내가 사용할 엔트리를 포함한 구조체를 불러오는 것이다. 파라미터로 설명 ㄱㄱ

• LIST_ELEM: 우리가 원하는 노드의 시작 포인터
• STRUCT: LIST_ELEM을 포함하고 있는 구조체
• MEMBER: 구조체에 포함된 LIST_ELEM의 멤버명

위의 void thread-awake 함수를 예시로 설명하겠다.

함수를 간단하게 설명하자면, block 상태에 있는 스레드가 일어나야 할 조건을 충족시켰을 때, 깨워서 ready 상태로 보내는 기능을 구현한 것이다.

 

asleep(block) state --> ready state

 

위 기능을 실현시키기 위해서 먼저 구조체 변수 e = list_begin(&sleep_list); 를 설정했다.

  * sleep_list: block 상태에 있는 스레드들을 모아둔 리스트 구조체

  * list_begin: 리스트 구조체의 가장 앞에 있는 요소 반환

 

그 후 while문을 이용하여 e가 sleep_list의 마지막 요소가 될 때까지 돌린다. 만약 리스트 내 thread가 깨워야 하는 조건을 충족한다면 unblock되면서 리스트에서 제거된다. 그렇지 않다면 e = list_next(e); 를 이용하여 다름 스레드를 깨우려고 시도할 것이다.

 

이 때 list_entry를 이용하여 sleep_list 안의 스레드들 순회가 가능하도록 한다. list_entry 함수를 보면

struct thread *t = list_entry(e, struct thread, elem);

이렇게 되어 있다. 즉 e는 구조체 thread 안에 elem이라는 이름의 구조체인 것이고, 이 e를 이용해서 sleep_list 안에 있는 스레드들을 찾을 수 있는 것이다.

 

사실 나도 이 부분이 잘 이해가 가지 않았다. 일단 thread 구조체 함수부터 파보자.

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          // Thread identifier.
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */

	int64_t sleep_ticks;

#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4;                     /* Page map level 4 */
#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	/* Owned by thread.c. */
	struct intr_frame tf;               // Information for switching
	unsigned magic;                     /* Detects stack overflow. */
};

 

list_entry에서 말하는 elem은 스레드 구조체 안에 있는 list_elem이라는 구조체의 멤버인 것을 알 수 있다. 그럼 list_elem은 뭘까?

/* List element. */
struct list_elem {
	struct list_elem *prev;     /* Previous list element. */
	struct list_elem *next;     /* Next list element. */
};

 

잘은 모르겠지만 리스트를 연결시키기 위해 필요한 element인 것 같다. 이를 이해하기 위해서는 결국 리눅스 커널의 자료구조가 어떻게 구현되어 있는지 접근해야 하고, 그 답은 doubly linked-list(이중 연결 리스트)이다. 

 

linked-list(연결 리스트)는 노드들을 하나의 리스트로 연결한 자료 구조이다. 

 

단일 연결 리스트

 

한 노드 안에 다음 노드의 시작 포인터를 next 인자에 넣어서 알 수 있다.

 

이중 연결 리스트는 다음 노드의 시작 포인터 뿐만 아니라, 이전 노드의 시작 포인터도 알 수 있도록 구현한 것이다.

 

이중 연결 리스트

 

즉 thread 구조체 안에 있는 list_elem 구조체를 이용하여 이전, 이후의 구조체들과 서로 연결할 수 있다는 것이다.

 

정리하자면, 커널의 데이터들은 구조체의 elem요소를 통해 doubly linked-list로 연결되어 있고, list_entry는 이 elem을 이용하여 리스트 내의 노드들을 순회할 수 있도록 한다.