[pintOS]-FIFO 궁금했던 점 분석

왜 less로 정렬하면 선입 선출이 안되는지?

배경

• 특정 조건의 순서대로 elem을 뽑으려면 뽑기 전에 리스트를 정렬하고 front나 back중 하나에서 뽑으면 될 것 같다.
  • 넣을 때부터 정렬을 해도 donate등 다른 요인들로 정렬이 깨질 수 있기 때문에, 어차피 뽑기 전에 정렬을 한 번 더 해야 한다.
  • 따라서 뽑기 전에’만’ 정렬을 하는 것이 효율적이다.
• 리스트에는 기존에 뒷쪽(list_push_back)부터 elem을 삽입해주고 있었다.
• 이 때 list에서 제공하는 함수에는 “less함수”, 즉 a,b의 property를 비교했을 때 a가 더 작은 경우 true를 반환하는 함수를 넣어주라고 한다.
• 이를 사용하기 위해 lesser_priority()를 이용해 오름차순으로 정렬하고 pop_back()을 하면 선입선출 케이스를 통과하지 못한다.

Merge는 stable sort

• 이유는 merge는 “stable sort”인 것과 관련이 있다.
  • merge는 정렬시 같은 값이 있으면 그 순서가 유지되도록 정렬한다.
  • 따라서 같은 priority를 작은순으로 정렬하고 뒤에서 빼면, 맨 뒤에 오는 elem은 가장 나중에 온 요소이다.
• 이를 해결하기 위한 방법은 두가지다.
  • bigger_priority()를 이용해 내림차순으로 정렬하고 앞의 요소를 뺀다.
  • 애초에 넣을 때부터 앞으로 넣고, 오름차순으로 정렬(lessor_priority)하고 뒤로 뺀다.
• 종합해보면 merge가 stable sort이므로 이를 활용해 FIFO를 위해 사용하는 자료구조인 큐처럼 연결리스트를 사용해야 하는 것이다.

less에서 ≤ (작거나 같다) 조건을 주면 왜 is_sorted에서 에러나는지?

• 아래 코드와 같이 비교시 ‘같다’ 조건을 추가하면 assertion failed가 나온다.

bool lesser_priority(const struct list_elem *a, 
				   const struct list_elem *b, 
				   void *aux UNUSED){
	struct thread *threadA = list_entry(a, struct thread, elem);
	struct thread *threadB = list_entry(b, struct thread, elem);
	if(threadA->priority <= threadB->priority){ //작거나 '같다'를 주는 부분
		return true;
	}else{
		return false;
	}
}

FAIL tests/threads/priority-donate-multiple Kernel panic in run: PANIC at ../../lib/kernel/list.c:413 in list_sort(): assertion `is_sorted (list_begin (list), list_end (list), less, aux)' failed. Call stack: 0x8004214f06 0x8004216162 0x80042085c6 0x8004208cad 0x8004208c6d 0x8004207366 0x8004207816 0x800420b47b 0x8004219819 0x8004208344

list_sort

• list_sort는 정렬을 한 후 마지막으로 is_sorted를 통해 정렬 여부를 확인한다.

void
list_sort (struct list *list, list_less_func *less, void *aux) {
	
	//정렬 로직...

	ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
}

is_sorted

• 이 때 is_sorted는 내부 함수를 통해서 현재 elem이 prev 보다 less인지 확인한다.
  • 이 값이 true인 경우, 정렬이 제대로 이루어지지 않았다고 판단하여 false를 반환한다.
  • less에 작거나 ‘같다’를 준 경우 값이 같은 elem들 사이에서는 less가 true가 나올 수 밖에 없어 ASSERT문을 통과하지 못한다.

static bool
is_sorted (struct list_elem *a, struct list_elem *b,
		list_less_func *less, void *aux) {
	if (a != b)
		while ((a = list_next (a)) != b)
			if (less (a, list_prev (a), aux))
				return false;
	return true;
}

정리

• 다시 생각해보면 ‘선입 선출’ 이므로 궁합이 가장 잘 맞는 ‘큐’ 자료구조처럼 들어온 방향과 반대 방향으로 pop을 해야 했다.
• 이를 도와주는 것이 정렬에도 순서가 깨지지 않는 ‘stable’한 정렬이였고, pintOS에서는 그 중 하나인 merge_sort를 지원한다.
• stable 정렬을 위해서는 비교함수에 ‘같다’ 조건을 주는 함수를 쓰면 안된다.

더 공부해 볼 것

• pintos의 merge코드 분석해보기

list_sort

/* Sorts LIST according to LESS given auxiliary data AUX, using a
   natural iterative merge sort that runs in O(n lg n) time and
   O(1) space in the number of elements in LIST. */
void
list_sort (struct list *list, list_less_func *less, void *aux) {
	size_t output_run_cnt;        /* Number of runs output in current pass. */

	ASSERT (list != NULL);
	ASSERT (less != NULL);

	/* Pass over the list repeatedly, merging adjacent runs of
	   nondecreasing elements, until only one run is left. */
	do {
		struct list_elem *a0;     /* Start of first run. */
		struct list_elem *a1b0;   /* End of first run, start of second. */
		struct list_elem *b1;     /* End of second run. */

		output_run_cnt = 0;
		for (a0 = list_begin (list); a0 != list_end (list); a0 = b1) {
			/* Each iteration produces one output run. */
			output_run_cnt++;

			/* Locate two adjacent runs of nondecreasing elements
			   A0...A1B0 and A1B0...B1. */
			a1b0 = find_end_of_run (a0, list_end (list), less, aux);
			if (a1b0 == list_end (list))
				break;
			b1 = find_end_of_run (a1b0, list_end (list), less, aux);

			/* Merge the runs. */
			inplace_merge (a0, a1b0, b1, less, aux);
		}
	}
	while (output_run_cnt > 1);

	ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
}

inplace_merge

/* Merges A0 through A1B0 (exclusive) with A1B0 through B1
   (exclusive) to form a combined range also ending at B1
   (exclusive).  Both input ranges must be nonempty and sorted in
   nondecreasing order according to LESS given auxiliary data
   AUX.  The output range will be sorted the same way. */
static void
inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
		struct list_elem *b1,
		list_less_func *less, void *aux) {
	ASSERT (a0 != NULL);
	ASSERT (a1b0 != NULL);
	ASSERT (b1 != NULL);
	ASSERT (less != NULL);
	ASSERT (is_sorted (a0, a1b0, less, aux));
	ASSERT (is_sorted (a1b0, b1, less, aux));

	while (a0 != a1b0 && a1b0 != b1)
		if (!less (a1b0, a0, aux))
			a0 = list_next (a0);
		else {
			a1b0 = list_next (a1b0);
			list_splice (a0, list_prev (a1b0), a1b0);
		}
}