[pintOS] Project1-2. Priority Scheduling

์˜ˆ๋‹ˆยท2021๋…„ 2์›” 14์ผ
0

pintOSํ”„๋กœ์ ํŠธ

๋ชฉ๋ก ๋ณด๊ธฐ
2/6

๐Ÿ“… ๊ธฐ๊ฐ„ : 2021.02.06(ํ† )


1. ๊ณผ์ œ ๋ชฉํ‘œ

ํ˜„์žฌ ํ•€ํ† ์Šค์—์„œ๋Š” ์Šค๋ ˆ๋“œ๋ฅผ ์šฐ์„ ์ˆœ์œ„์— ์ƒ๊ด€์—†์ด ์‹คํ–‰ํ•˜๊ณ  ์žˆ๋‹ค. ์ด ๊ณผ์ œ์˜ ๋ชฉํ‘œ๋Š” ์šฐ์„ ์ˆœ์œ„ ์ˆœ์„œ๋Œ€๋กœ ์Šค๋ ˆ๋“œ๊ฐ€ ์‹คํ–‰๋˜๋„๋ก ํ•˜๋Š” ๊ฒƒ!

CPU๋Š” ready_list์— ์žˆ๋Š” ์Šค๋ ˆ๋“œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์‹คํ–‰ํ•œ๋‹ค. ํ˜„์žฌ ํ•€ํ† ์Šค์—์„œ๋Š” ready_list์— ์Šค๋ ˆ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•  ๋•Œ ๋ฆฌ์ŠคํŠธ์—์„œ ์šฐ์„ ์ˆœ์œ„์— ๋งž๊ฒŒ ์‚ฝ์ž…ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ๋‹จ์ˆœํžˆ ์ œ์ผ ๋’ค์— ์ถ”๊ฐ€ํ•˜๊ณ  ์žˆ๋‹ค. (ํ˜„์žฌ๋Š” list_push_back์ธ๋ฐ, list_insert_ordered๋กœ ๋ฐ”๊ฟ€๊ฒƒ์ž„)


* ์ƒˆ๋กœ ์•Œ๊ฒŒ ๋œ ์ 

1. ํ•จ์ˆ˜๊ฐ€ "๋‚ด๋ถ€์—์„œ ์‚ฌ์šฉํ•  ํ•จ์ˆ˜"์™€ "๊ทธ ํ•จ์ˆ˜๊ฐ€ ์‚ฌ์šฉํ•  ์ธ์ž"๋ฅผ ์ž์‹ ์˜ ์ธ์ž๋กœ ๋ฐ›์„ ์ˆ˜๋„ ์žˆ๋‹ค.

void
list_insert_ordered (struct list *list, struct list_elem *elem,
		list_less_func *less, void *aux) {
	struct list_elem *e;

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

	for (e = list_begin (list); e != list_end (list); e = list_next (e))
		if (less (elem, e, aux))
			break;
	return list_insert (e, elem);
}

์œ„์˜ ์ฝ”๋“œ์—์„œ ํ•จ์ˆ˜์˜ ์ธ์ž ๋ถ€๋ถ„์˜ list_less_func *less, void *aux๋ฅผ ๋ณด์ž.
์ด๋Š” list_insert_orderedํ•จ์ˆ˜์—์„œ less๋ผ๋Š” ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•  ๊ฒƒ์ด๊ณ , less์˜ ์ธ์ž๋กœ๋Š” aux๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค.

์•„๋ž˜ ์ฝ”๋“œ์™€ ๊ฐ™์ด ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);

2. ๊ตฌํ˜„

๐Ÿ”” ์•„์ด๋””์–ด

์ด ๋ฌธ์ œ๋Š” ready_list์— thread๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์ •๋ ฌ๋˜๋„๋ก ์‚ฝ์ž…ํ•˜๋„๋ก ์ˆ˜์ •ํ•ด์„œ ํ•ด๊ฒฐํ•˜์ž. (list_insert_ordered ํ•จ์ˆ˜์— ์ธ์ž๋กœ cmp_priority๋ผ๋Š” ์šฐ์„ ์ˆœ์œ„ ๋น„๊ต ํ•จ์ˆ˜๋ฅผ ๋„ฃ์–ด์ฃผ์ž)
ํ˜„์žฌ CPU๋ฅผ ์ ์œ ํ•˜๊ณ  ์žˆ๋Š” ์Šค๋ ˆ๋“œ์˜ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ready_list์—์„œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ์Šค๋ ˆ๋“œ๋ณด๋‹ค ์šฐ์„ ์ˆœ์œ„๋ณด๋‹ค ๋‚ฎ์œผ๋ฉด ์ด ์Šค๋ ˆ๋“œ๊ฐ€ CPU๋ฅผ ์„ ์ ํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์•ผํ•œ๋‹ค. (thread_yield)

๐Ÿ”” ๊ตฌํ˜„

  1. ready_list์— ์Šค๋ ˆ๋“œ๊ฐ€ ์šฐ์„ ์ˆœ์œ„๋Œ€๋กœ ์ •๋ ฌ๋˜๋„๋ก ํ•˜๊ธฐ ์œ„ํ•ด, ์Šค๋ ˆ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•  ๋•Œ ํ•€ํ† ์Šค ๋‚ด์žฅ๋œ ํ•จ์ˆ˜์ธ list_insert_ordered ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. ์ด๋•Œ ์‚ฌ์šฉํ•  ์šฐ์„ ์ˆœ์œ„ ๋น„๊ตํ•จ์ˆ˜ cmp_priority๋ฅผ ๋งŒ๋“ค์–ด์ค€๋‹ค.

  2. ์ด์ œ thread๊ฐ€ unblock ๋  ๋•Œ ์šฐ์„ ์ˆœ์œ„๋Œ€๋กœ ์ •๋ ฌ๋˜์–ด ready_list์— ์Šค๋ ˆ๋“œ๊ฐ€ ์ถ”๊ฐ€๋  ์ˆ˜ ์žˆ๋„๋ก, thread_unblockํ•จ์ˆ˜์—์„œ list_push_back์„ list_insert_orderd๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค.

  3. ํ˜„์žฌ CPU์ ์œ  ์ค‘์ธ ์Šค๋ ˆ๋“œ๊ฐ€ CPU ์ ์œ ๋ฅผ ์–‘๋ณดํ•˜๊ณ  ready_list์— ์Šค๋ ˆ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋Š” ํ•จ์ˆ˜์ธ thread_yield()์˜ ๋‚ด๋ถ€์—์„œ ready_list์— ์‚ฝ์ž…๋˜๋Š” ๋ถ€๋ถ„์˜ list_push_back์„ list_insert_orderd๋กœ ๊ต์ฒดํ•œ๋‹ค.

  4. ready_list์˜ ์ฒซ๋ฒˆ์งธ ์Šค๋ ˆ๋“œ๊ฐ€ CPU ์ ์œ  ์ค‘์ธ ์Šค๋ ˆ๋“œ๋ณด๋‹ค ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์œผ๋ฉด CPU์ ์œ ๋ฅผ ์–‘๋ณดํ•˜๋Š” ํ•จ์ˆ˜ test_max_priorityํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ ๋‹ค. (thread_yield ์ด์šฉ)


3. ๋Š๋‚€์ 

๋ณธ ๊ณผ์ œ๋Š” list_push_back์œผ๋กœ ๊ตฌํ˜„๋œ ๋ถ€๋ถ„์„ list_insert_ordered์™€ cmp_priority๋ฅผ ์ด์šฉํ•ด์„œ ๊ณ ์ณ์ฃผ๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.
thread ๊ตฌ์กฐ์ฒด๋Š” ๋ชจ๋‘ list, list_elem์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, list ๊ตฌ์กฐ์ฒด์—์„œ ์ œ๊ณตํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ž˜ ์‚ฌ์šฉํ•˜๋ฉด ํŽธํ•˜๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋ƒฅ ๊ฐ€์ ธ๋‹ค์“ฐ์ง€๋ง๊ณ  ํ•ญ์ƒ ๊ทธ ํ•จ์ˆ˜์˜ ์ธ์ž, ๊ตฌ์กฐ, ์ž‘๋™์›๋ฆฌ๋ฅผ ํŒŒ์•…ํ•˜๊ณ  ์‚ฌ์šฉํ•˜๋Š” ์Šต๊ด€์„ ๋“ค์ด์ž!

0๊ฐœ์˜ ๋Œ“๊ธ€