WIL project 3 Virtual Memory(2)

๊น€์ง€์ˆ˜ยท2022๋…„ 12์›” 12์ผ
0

SW์‚ฌ๊ด€ํ•™๊ต์ •๊ธ€5๊ธฐ

๋ชฉ๋ก ๋ณด๊ธฐ
12/13

Demanding Paging

Supplement Page Table

๐Ÿ“’ Supplement Page Table ๋ž€?

  • supplement page table์€ ๊ฐ ํ”„๋กœ์„ธ์Šค๋งˆ๋‹ค ๋ณด์กฐ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ
  • ๊ฐ๊ฐ์˜ ํŽ˜์ด์ง€์— ๋Œ€ํ•ด์„œ ๋ฐ์ดํ„ฐ๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ณณ(frame, disk, swap ์ค‘์— ์–ด๋””์— ์กด์žฌํ•˜๋Š”์ง€)์— ์ •๋ณด ๋ณด์œ 
  • ์œ„์— ๋ฐ์ดํ„ฐ์— ์ƒ์‘ํ•˜๋Š” ์ปค๋„ ๊ฐ€์ƒ์ฃผ์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ ์ •๋ณด ๋“ฑ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค

๐Ÿ“’ Supplement Page Table ์‚ฌ์šฉ ๋ชฉ์ 

  • ๋ณด์กฐ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์€ ์ตœ์†Œํ™˜ ๋‘ ๊ฐ€์ง€ ๋ชฉ์ ์œผ๋กœ ์‚ฌ์šฉ
    • ํŽ˜์ด์ง€ ํดํŠธ๊ฐ€ ๋ฐœ์ƒ ํ–ˆ์„ ๋•Œ ๊ทธ๊ณณ์— ์–ด๋–ค ๋ฐ์ดํ„ฐ๊ฐ€ ์žˆ์—ˆ์–ด์•ผ ํ–ˆ๋Š”์ง€๋ฅผ ์•Œ์•„๋‚ด๊ธฐ ์œ„ํ•ด ์ปค๋„์€ ๋ณด์กฐ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์—์„œ ํดํŠธ๊ฐ€ ๋ฐœ์ƒํ•œ ๊ฐ€์ƒ ํŽ˜์ด์ง€๋ฅผ ํƒ์ƒ‰
    • ์ปค๋„์ด ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ข…๋ฃŒ๋  ๋•Œ ์–ด๋–ค ์ž์›์„ ํ•ด์ œ(free)ํ• ์ง€ ๊ณ ๋ฅด๊ธฐ ์œ„ํ•ด์„œ ๋ณด์กฐ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์„ ์กฐ์‚ฌ

๐Ÿ“’ Supplement Page Table ์ž๋ฃŒ ๊ตฌ์กฐ ์ข…๋ฅ˜

  • Arrays : ๊ฐ€์žฅ ๊ฐ„๋‹จํ•˜๊ฒŒ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜์ง€๋งŒ, ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋‚ญ๋น„ํ•˜๋Š” ๋ฐ€๋„๊ฐ€ ๋‚ฎ๋‹ค
  • Lists : ๊ฝค๋‚˜ ์‹ฌํ”Œํ•œ ํŽธ์ด์ง€๋งŒ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ˆœํšŒํ•˜๋Š”๋ฐ ์‹œ๊ฐ„์„ ๋งŽ์ด ์†Œ๋ชจํ•œ๋‹ค
  • Bitmaps : true ๋˜๋Š” false๊ฐ€ ๋  ์ˆ˜ ์žˆ๋Š” ๋น„ํŠธ ๋ฐฐ์—ด, ๋™์ผํ•œ ๋ฆฌ์†Œ์Šค ์ง‘ํ•ฉ์—์„œ ์‚ฌ์šฉ๋Ÿ‰์„ ์ถ”์ ํ•  ๋•Œ ์œ ์šฉ
  • Hash Tabbles : key-value 1 ๋Œ€ 1 ๋งค์นญ ๊ตฌ์กฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ์‚ฝ์ž…, ์‚ญ์ œ, ๊ฒ€์ƒ‰ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(1)์„ ๊ฐ€์ง„๋‹ค. ํ•˜์ง€๋งŒ ์ˆœ์„œ๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š๊ณ , ๊ฐ™์€ ์ธ๋ฑ์Šค์— ๋ชจ๋“  ํ‚ค๊ฐ’๊ณผ ๋ฐ์ดํ„ฐ๊ฐ€ ์ €์žฅ๋˜์–ด(์ „๋ถ€ ์ถฉ๋Œํ•œ ๊ฒฝ์šฐ) O(n)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

๐Ÿ“Œ Supplement Page Table ์„ ์–ธ

../thread.h
struct thread {
	/* Owned by thread.c. */
	'
    '
#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	'
    '
};

๐Ÿ“Œ Supplement Page Table ์ž๋ฃŒ ๊ตฌ์กฐ ์„ ์–ธ ๋ฐ ์ดˆ๊ธฐํ™”

  • supplemental_page_table ๊ตฌ์กฐ์ฒด ์•ˆ์— spt๋ฅผ ๊ด€๋ฆฌํ•  hash ๊ตฌ์ดˆ์ œ ์„ ์–ธ
../vm.h
/* supplemental_page_table ๊ตฌ์กฐ์ฒด ์•ˆ์— hash ๊ตฌ์กฐ์ฒด ์„ ์–ธ */ 
struct supplemental_page_table {
	struct hash hash;  
};
  • page ๊ตฌ์กฐ์ฒด ์•ˆ์— ์“ฐ๊ธฐ ๊ฐ€๋Šฅ ์—ฌ๋ถ€ ํ™•์ธ์šฉ writable์„ ์–ธ
  • hash ์ž๋ฃŒ๊ตฌ์กฐ์˜ elem์„ ์„ ์–ธ
../vm.h
struct page {
	'
    '
    
	/* Your implementation */
	bool writable;						// project 3 Virtual Memory ์ถ”๊ฐ€
	struct hash_elem hash_elem;			// project 3 Virtual Memory ์ถ”๊ฐ€
	'
    '
	};
};
  • supplemental_page_table์„ ์ดˆ๊ธฐํ™” ์‹œํ‚ฌ ๋•Œ์— hash ์ž๋ฃŒ๊ตฌ์กฐ๋กœ init์„ ํ•ด์คŒ
../vm.h
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->hash,page_hash,page_less, NULL);
}

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